ORDER BY in subqueries: keep the sorted order above the Sort; no compaction after ORDER BY - #152

Implements the paper's new rule (Pratyush/dbsnark-paper e048932, PIOP 20): no Compaction downstream of an ORDER BY. Compaction proves only that its output has its input's rows, not their order. While testing the one shape where this can arise, a filter over an ORDER BY … LIMIT subquery, I found that such queries failed to verify at all, for two separate reasons.

Compaction after ORDER BY

The planner no longer collects a compaction hint for a node with a Sort below it, and replaying such a hint is rejected (follows_order_by in ensure_compaction_target). This is the narrow form of what #94 attempted. #94 banned compaction in any plan with a Sort or Limit; this only forbids it above a Sort, which costs nothing on TPC-H. The #94 closing comment noted that the safety argument rested only on planner behaviour; now the verifier enforces it.

Bug 1: the Sort's hint lost its row order (completeness)

sort_df sorted the hint and then dropped __row_id__. DataFusion only keeps an ordering where an operator requires it, and it drops a sort that nothing above depends on. LIMIT's hint and the expression hints above it (here the filter predicate) therefore saw the rows in a different order from the committed columns, with the padding first. The comparison's predicate witness came out all false, and the Sign check failed.

Fix: the Sort hint's __row_id__ is now the output position, numbered by row_number() OVER (ORDER BY <the sort's keys>). A window requires that order, so DataFusion keeps it. The column is not committed. Nodes above already order their hints by __row_id__.

Bug 2: execution moved the filter below the top-k (completeness; a DataFusion 46 bug)

execute() ran DataFrame::collect, which re-runs DataFusion's default optimizer. In DataFusion 46, PushDownFilter pushes a filter below any Sort, even one with a fetch (a top-k), which changes the result. For SELECT n_name FROM (SELECT * FROM nation ORDER BY n_nationkey LIMIT 20) s WHERE n_regionkey = 1, the claimed result had 5 rows, including UNITED STATES (key 24). The proof had the correct 4, so the verifier rejected the proof.

Fix: FetchSafePushDownFilter backports the upstream guard from apache/datafusion#21057 (released in 54.0.0): a filter stays above any node with a fetch or skip. It replaces the stock PushDownFilter both in the proof planner and in execution's default pipeline. Before this, the proof planner avoided the bug only because NormalizeSortFetch turns Sort(fetch) back into Limit(Sort) in every pass. Two unit tests show stock DataFusion 46 pushing the filter below a top-k and the wrapper keeping it above. The DataFusion upgrade itself is #153.

Also

LIMIT had a debug_assert! that its payload already contained an activator. That is false for a LIMIT inside a subquery, so debug builds panicked. Removed: the code after it already handles an empty payload.

Tests

• e2e ordered_limit_in_subquery, filter_over_ordered_limit, limit_over_filter_over_ordered_limit, ordered_filter_over_ordered_limit. The three with a filter fail on main.
• Unit tests: a compaction hint on a plain filter applies; one on a filter over Sort/Limit is rejected.
• cargo test --release -p tt-exec --features test-utils: all 98 pass, including 17 TPC-H and 6 Poneglyph queries. Workspace unit tests, fmt and clippy are clean.

🤖 Generated with Claude Code