[FEA] Segmented Sorting

[jrhemstad]

Is your feature request related to a problem? Please describe.

Given a table and a set of offsets that demarcate "segments" of the table, I would like to be able to sort each segment.

Describe the solution you'd like

Implement a segmented_sort API like:

unique_ptr<table> segmented_sort(table_view table_to_sort, vector<size_type> key_columns, vector<size_type> segment_offsets, vector<order> column_order, vector<null_order> null_orders);

Describe alternatives you've considered
Alternatively, you can use slice to get a set of views and sort each view separately, but that's inefficient.

Additional context
I thought of this while testing partition in #4472. Since the ordering per partition is non-deterministic, it is difficult to unit test when there are multiple values per partition.

Unfortunately, CUB's segmented sort can't be used because we need a comparison sort for the lexicographic row ordering.

Instead, a straightforward way to implement this:

1. Prepend an integral dummy column of 0s to table_to_sort
2. Scatter 1s to every location indicated by segment_offsets
3. Compute exclusive_scan of dummy column
4. Do a lexicographic sort of dummy column + table_to_sort

[harrism]

Sorry, can you clarify: is the present use case just for unit testing?

[jrhemstad]

Sorry, can you clarify: is the present use case just for unit testing?

Yep, not high priority. I imagine it will be useful outside of unit testing since it's a somewhat common operation, but I don't have any other immediate need.

I just wanted to capture the idea while I was thinking of it.

[kkraus14]

I believe there's a desire to sort as a groupby operation in Python. I.E. something like groupby columns 0 and 1 of the input Table and then sort by columns 2 and 4 within each group.

[harrism]

But isn't that case just a lexicographic sort by columns 0, 1, 2, 4?

[devavret]

Feels like a generalization of sort_helper's sorted_values but for table values instead.

[kkraus14]

But isn't that case just a lexicographic sort by columns 0, 1, 2, 4?

Yes it is, but there's no easy way with the current APIs to compose that because I may be asking for additional aggregations as well where currently I'd have to redo the work of sorting by columns 0 and 1 in order to merge the two.