zhuqi-lucas opened a new pull request, #25050:
URL: https://github.com/apache/datafusion/pull/25050
## Which issue does this PR close?
Closes #24771.
## Rationale for this change
`OptimizeAggregateOrder` already proves, via `with_beneficial_ordering`,
when the input
ordering satisfies the group-by prefix followed by a
`first_value`/`last_value` ordering
requirement, and the single-group accumulators consume that flag
(`first_last.rs`,
`get_first_idx`/`get_last_idx`). The grouped path never did:
`create_groups_accumulator`
dropped the flag, and `FirstLastGroupsAccumulator` ran the full per-row
lexicographic
tournament, per-winner ordering-key materialization, and cross-batch
`compare_rows` on
every batch even though the winner was already determined by position.
The motivating workload (a materialized `GROUP BY date, ticker` with three
`LAST_VALUE(... ORDER BY ts, seq)` over an NBBO table whose file sort order
is exactly
`(ticker, ts, seq)`, ~1.5B rows/day, ~1.8M groups) spends ~20% of on-CPU
time inside
`get_filtered_extreme_of_each_group` — all of it avoidable comparisons. The
same
ordering evidence is cashed twice by the planner but only once by the
executor.
## What changes are included in this PR?
- `is_input_pre_ordered` is threaded through `create_groups_accumulator` into
`FirstLastGroupsAccumulator`.
- When set, `update_batch` takes a comparison-free path: one pass over
`group_indices`
records each group's first (FIRST_VALUE) or last (LAST_VALUE) qualifying
row; later
batches unconditionally overwrite for LAST_VALUE and never overwrite for
FIRST_VALUE.
No `LexicographicalComparator` is built and `compare_rows` never runs on
this path.
- The winner's ordering values are still materialized into the partial
state: the final
stage merges states from partitions whose relative arrival order is not
guaranteed, so
`merge_batch` keeps comparing and is intentionally untouched, as are
`convert_to_state` and the skip-partial `is_set` handling.
- Drive-by: three stale comments still referring to the field's old name
(`min_of_each_group_buf`) are updated.
**Tie semantics note:** among rows whose ordering keys compare equal, this
path picks
the physically last qualifying row for LAST_VALUE (first for FIRST_VALUE),
matching the
single-group pre-ordered accumulator and `Iterator::max_by`. The tournament
path keeps
the first-seen row of a tie (its comparisons are strict), so the two paths
may pick
different — equally valid — rows on tied keys. Documented on the method and
pinned by a
dedicated test.
## Are these changes tested?
- 9 new unit tests: fast-vs-tournament full-state equivalence
(LAST/FIRST/DESC/FILTER
incl. null predicates/IGNORE NULLS/RESPECT NULLS with a null winner),
explicit
expected values, `EmitTo::First(n)` mid-stream draining with index
shifting, and a
partial→final merge in both arrival orders proving the emitted state
carries the
winning ordering keys.
- A new end-to-end `first_last_ordered.slt`: requirement proven through
declared
orderings, through a projection-alias equivalence, and through a
filter-induced
constant; FILTER interaction; and the reverse branch (FIRST over DESC).
- Existing suites pass: 215 crate tests, `aggregate.slt`,
`first_last_nested.slt`,
`group_by.slt`, `distinct_on.slt`, `array_agg.slt`, `subquery_sort.slt`.
## Are there any user-facing changes?
No API changes. Queries whose input ordering already satisfies a grouped
first_value/last_value requirement get faster; on the motivating workload the
aggregation stage improved by ~20% end-to-end wall time.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
