Skip to content

fix(sort-pushdown): drop runtime row-group reorder hints on Inexact→Exact upgrade (correctness) - #2

Merged
zhuqi-lucas merged 3 commits into
zhuqi-lucas:fix/sort-elimination-after-stats-reorderfrom
adriangb:pr22493-rg-reorder-fix
May 24, 2026
Merged

zhuqi-lucas merged 3 commits into
zhuqi-lucas:fix/sort-elimination-after-stats-reorderfrom
adriangb:pr22493-rg-reorder-fix

Conversation

@adriangb

Copy link
Copy Markdown

Hi @zhuqi-lucas 👋 — this targets your PR branch for apache#22493 (not main), so you can merge it into your PR if you agree.

While reviewing apache#22493 I found a silent wrong-results bug in the new Inexact → Exact upgrade. Sharing a fix + regression test here.

The problem

When try_pushdown_sort upgrades the Inexact result back to Exact, the SortExec is removed — but the source rebuilt from the Inexact result still carries sort_order_for_reorder / reverse_row_groups. The parquet opener therefore still reorders row groups at runtime: reorder_by_statistics sorts row groups ASC-by-min, then reverse() flips them for DESC.

That runtime reorder is only approximate. For two row groups within a single file that share the same min but differ in max, the reverse() mis-orders them — even with a stable sort. Previously a SortExec masked it; once it's eliminated, the mis-ordered stream is the final answer.

Reproduction (DESC, multiple row groups per file)

A file declared WITH ORDER (id DESC) containing [10, 8, 8, 8] written at max_row_group_size = 2:

RG0 = [10, 8]   (min 8, max 10)
RG1 = [ 8, 8]   (min 8, max 8)

Both row groups have min = 8. reorder_by_statistics keeps [RG0, RG1] (ASC-by-min, tie), then reverse() → [RG1, RG0] → the file streams 8, 8, 10, 8. With files [b_high, a_low] and the SortExec gone:

SELECT id FROM t ORDER BY id DESC
  expected: 10, 8, 8, 8, 3, 2, 1
  actual:    8, 8, 10, 8, 3, 2, 1     ← id=10 in 3rd position, no error

This is covered by the existing tests only because their files are tiny (single row group each), so the reorder never actually permutes anything.

The fix

When we upgrade to Exact, the post-sort file groups are non-overlapping and each file's declared ordering re-validates — so reading the files in their natural (declared-sorted) order is already correct, and no runtime reorder is needed. Restore the original, hint-free source on upgrade. This mirrors the Unsupported → Exact path, which also reads files in natural order.

Net effect: the upgraded plans (4.1 / 6.1 / 8.1 / G.1 / G.2) shed the now-unnecessary sort_order_for_reorder / reverse_row_groups from their DataSourceExec — cleaner plans, identical query results.

Commits

  1. refactor: express the keep_ordering decision in rebuild_with_source as an explicit match (no behavior change).
  2. fix: drop the runtime reorder hints on the Inexact → Exact upgrade + update the 5 affected expected plans.
  3. test: Test 8b — DESC multi-row-group file with a shared min. Fails without the fix (returns 8,8,10,8,...), passes with it.

Verified

  • New Test 8b fails on your current branch tip and passes with the fix.
  • cargo test -p datafusion-sqllogictest --test sqllogictests -- sort_pushdown ✅
  • cargo test -p datafusion-datasource --lib (139) / -p datafusion-datasource-parquet --lib (123) / -p datafusion-physical-optimizer --lib (27) ✅
  • cargo fmt --all --check and cargo clippy -p datafusion-datasource --all-targets --all-features clean.

Note (out of scope)

The underlying reorder_by_statistics + reverse() mis-ordering of equal-min row groups is a latent issue in the opener. It stays correct in the genuine Inexact (SortExec-kept) TopK path because the SortExec re-sorts and pruning only loses a little efficiency — so fixing it at the opener level is a separate, optional follow-up and isn't needed here.

🤖 Generated with Claude Code

adriangb and others added 3 commits May 24, 2026 09:26
Replace the nested `if all_non_overlapping { if is_exact {..} else {..} }
else { false }` in `rebuild_with_source` with a `match (all_non_overlapping,
is_exact)`. No behaviour change — the three arms map one-to-one to the prior
branches and make the "overlap → drop", "exact → keep", "inexact →
re-validate" cases explicit.

Co-Authored-By: Claude Opus 4.7 (1M context) <[email protected]>
…xact upgrade

When `try_pushdown_sort` upgrades the `Inexact` result back to `Exact`
(post-sort file groups non-overlapping + declared ordering re-validates),
the `SortExec` is removed. But the source rebuilt from the `Inexact` result
still carried `sort_order_for_reorder` / `reverse_row_groups`, so the parquet
opener kept reordering row groups at runtime.

With the `SortExec` gone, that runtime reorder is no longer a harmless
optimisation — it is load-bearing for correctness, and it is wrong for DESC
requests. The opener sorts row groups ASC-by-min and then `reverse()`s them;
two row groups within a single file that share the same `min` but differ in
`max` get mis-ordered by the reverse. Example: a file declared `WITH ORDER
(id DESC)` containing `[10,8,8,8]` whose row groups are `[10,8]` and `[8,8]`
(both min 8) streams as `8,8,10,8`. Previously the `SortExec` re-sorted that;
once eliminated, the wrong order is the final result.

Because the upgrade only fires when each file's declared ordering re-validates
against the non-overlapping post-sort file groups, reading the files in their
natural (declared-sorted) order already yields the requested ordering — no
runtime reorder is needed. Restore the original, hint-free source on upgrade,
matching the `Unsupported → Exact` path which also reads files naturally.

Existing tests 4.1 / 6.1 / 8.1 / G.1 / G.2 lose the now-absent
`sort_order_for_reorder` / `reverse_row_groups` from their `DataSourceExec`
plans; data results are unchanged.

Co-Authored-By: Claude Opus 4.7 (1M context) <[email protected]>
Add Test 8b: a DESC scan over a file whose row groups share the same min
value (`[10,8,8,8]` → row groups `[10,8]` and `[8,8]`), listed out of order
on disk so the Inexact→Exact upgrade fires and SortExec is eliminated.

Without the fix this returns `8,8,10,8,...` (id=10 in third position): the
opener reorders row groups ASC-by-min then reverses, mis-ordering the two
min=8 row groups, and the eliminated SortExec no longer masks it. The test
asserts both the clean plan (no runtime reorder hints) and the correct
DESC result.

Co-Authored-By: Claude Opus 4.7 (1M context) <[email protected]>
@zhuqi-lucas
zhuqi-lucas merged commit f6408c4 into zhuqi-lucas:fix/sort-elimination-after-stats-reorder May 24, 2026
1 check passed
@zhuqi-lucas

Copy link
Copy Markdown
Owner

Thank you @adriangb merged to my branch.

zhuqi-lucas pushed a commit that referenced this pull request Aug 21, 2026
Hello,

Just reading the documentation and was confused by given example. They
are pretty similar. I was even thinking about merging them and only keep
one example with operator and one with SQL.

At least, example title should be renamed with `example 2` or `#2` to be
less confusing IMO.

What do you think?

Thanks for your work!

---------

Co-authored-by: Cursor <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants