|
| 1 | +# Adaptive Sorting 01: Prior Work |
| 2 | + |
| 3 | +Generated: 2026-10-13 |
| 4 | +Context: apache/datafusion PR #25358 (staged ORDER BY key evaluation), issue #25033 |
| 5 | + |
| 6 | +## Question |
| 7 | + |
| 8 | +Has adaptive or staged sort-key evaluation been tried before in apache/datafusion? Staged evaluation means computing later `ORDER BY` keys only for rows that tie on the earlier keys. |
| 9 | + |
| 10 | +## Answer |
| 11 | + |
| 12 | +No. I found no earlier issue or PR in apache/datafusion that evaluates later sort keys only for tied rows, adaptively or otherwise. #25033 (the issue behind PR #25358) seems to be the first; the author said the same when filing it, and it has no maintainer comments yet. Several nearby threads matter for the review, though. |
| 13 | + |
| 14 | +## Closest attempt |
| 15 | + |
| 16 | +- **[#22603](https://github.com/apache/datafusion/pull/22603), "Avoid TopK sort-key work for rejected batches" (closed without merging, 2026-05-28).** It skipped evaluating sort keys for whole batches that TopK's dynamic filter rejects. It worked per batch rather than per tie, and only in TopK. Benchmarks were run on it, but there's no maintainer comment saying why it was closed. #25033 cites it as its starting point. |
| 17 | + |
| 18 | +## Related threads that affect this PR's direction |
| 19 | + |
| 20 | +- **[#21543](https://github.com/apache/datafusion/issues/21543), "Revisit ExternalSorter sort strategy and sort_in_place_threshold_bytes" (open, 11 comments).** |
| 21 | + - It says the sort-each-batch-then-merge path dominates real workloads, because buffered data usually exceeds the 1 MiB threshold. |
| 22 | + - That matters here because the streaming merge re-evaluates every key for every row. In that path, staging saves only the evaluation done while sorting each batch, not the evaluation done during the merge. |
| 23 | + - It also reports that the existing `sort` benchmark never reaches the merge path, so a staged-sort benchmark has to use a larger input on purpose. |
| 24 | +- **[#16131](https://github.com/apache/datafusion/issues/16131) and [#7053](https://github.com/apache/datafusion/issues/7053), using Arrow's row format in `SortExec` (open).** |
| 25 | + - Row format encodes all sort keys into one array before sorting, which means evaluating every key up front, the opposite of this PR. |
| 26 | + - If row format becomes the default, staging would have to fit around it. |
| 27 | + - In #16131 a maintainer (Dandandan) notes that `lexsort_to_indices` is sometimes faster than row format. That fits the local benchmark result that single-column sorts per stage beat the multi-column sort. |
| 28 | +- **[#22883](https://github.com/apache/datafusion/issues/22883), "[EPIC] Adaptive predicate evaluation" (open, active).** |
| 29 | + - This is the closest precedent for making the decision at runtime. It measures filter cost and selectivity while running and reorders filters, instead of relying on fixed heuristics. |
| 30 | + - That is the same reasoning as the review's suggestion to choose stages automatically rather than through `sort_key_group_size`, so it's a natural thread to link. |
| 31 | +- **#6163, "Adaptive in-memory sort" (2023).** |
| 32 | + - Despite the name, it only introduced the 1 MiB concat-or-merge threshold. |
| 33 | + - Its author called that "a very rough heuristic," which shows how fixed sort settings have aged. |
| 34 | + |
| 35 | +## Implications for PR #25358 |
| 36 | + |
| 37 | +- Link #21543 when asking for a multi-batch benchmark above `sort_in_place_threshold_bytes`. It gives the request a maintainer-endorsed basis. |
| 38 | +- Link #22883 when suggesting that stages be chosen automatically instead of through `sort_key_group_size`. |
| 39 | +- Ask how staging would interact with the planned row-format sort (#16131). |
| 40 | +- Point to #22603 as the earlier TopK attempt, since the motivating `LIMIT` query in #25033 goes through TopK, which PR #25358 does not change. |
| 41 | + |
| 42 | +## Search limits |
| 43 | + |
| 44 | +- I used keyword queries through `gh search` on apache/datafusion only, so differently worded threads could be missed. Queries included "lazy sort", "lexsort", "sort tie", "skip sort key", "adaptive sort", "TopK sort keys", "sort expression evaluation", "row format sort", "sort comparator" and "adaptive". |
| 45 | +- I didn't search arrow-rs, where a lazy-comparator idea might live at the kernel level. |
0 commit comments