[Question] why need this sort in Sort.rs

[Ted-Jiang]

@yjshen , Sorry for bothering you, Why need positions.sort_unstable() below
https://github.com/apache/arrow-datafusion/blob/807b7a5f7eb858e9f7162e1f00ffeeedd0bf2050/datafusion/core/src/physical_plan/sorts/sort.rs#L460-L469

I think we should keep the order of the adding index in positions , so we can keep the order from indices , the result has correctly order.
https://github.com/apache/arrow-datafusion/blob/807b7a5f7eb858e9f7162e1f00ffeeedd0bf2050/datafusion/core/src/physical_plan/sorts/sort.rs#L433-L435

[yjshen]

group_indices takes adjacent records in the same batch as input, and does best-effort grouping to make slices instead of individual positions for better extend performance (extend a range of records rather than individual record at a time).

sort_unstable is useful since the positions are generated from lexsort which is unstable itself. there would be a possibility that records with the same sort key appear randomly after lexsort. but extend takes start pos and length as input, so a sort to make records with the same sort key appears sequentially is needed.

[Ted-Jiang]

i mean in this situation

positions.sort_unstable(); will get wrong order

[Ted-Jiang]

@yjshen But i found you pre-sort all batches during insert,
https://github.com/apache/arrow-datafusion/blob/4d6428c19dd6333f31ccc12398f6720066bab3f7/datafusion/core/src/physical_plan/sorts/sort.rs#L123-L124
so this situation not exist.
If i miss something plz tell me.

[Jefffrey]

Not sure if this is still relevant, things have changed since; feel free to reopen if I'm wrong 🙂