Skip to content

Commit 9e36344

Browse files
hassaanch23Omega359
authored andcommitted
fix: ignore repeated sort keys in an ordered aggregate's ORDER BY (apache#25400)
## Which issue does this PR close? - Closes apache#25398. ## Rationale for this change If an ordered aggregate's `ORDER BY` names the same expression more than once, the query panics or fails with an internal Arrow error: ```sql CREATE TABLE t AS SELECT i % 3 AS b, i AS id FROM (SELECT unnest(range(0,10)) AS i); SELECT b, first_value(id ORDER BY b, b) FROM t GROUP BY b; -- panicked at datafusion/functions-aggregate/src/first_last.rs:602:13 -- assertion `left == right` failed left: 2 right: 1 ``` Repeating a key is legal SQL. `DISTINCT ON` is the easy way to hit this by accident, because its key has to lead the `ORDER BY`, and writing the key out again produces the duplicate: `SELECT DISTINCT ON (b) b FROM t ORDER BY b, b`. The two sides of the ordered aggregate count the sort keys differently: - `AggregateExprBuilder::build` derives the ordering state fields (`ordering_fields`) from the `ORDER BY` list as written, so `b, b` becomes two fields. - Every accumulator (`first_value`, `last_value`, `nth_value`, `array_agg`, `string_agg`) builds its ordering with `LexOrdering::new`, which drops a sort key whose expression already appeared, so `b, b` becomes one key. Depending on which consumer compares them first, the mismatch shows up as the `first_last.rs` assertion, `Incorrect number of arrays provided to RowConverter`, or a column-count mismatch in the state schema. ## What changes are included in this PR? `AggregateExprBuilder::build` now passes `order_bys` through `LexOrdering` before deriving the ordering types and fields. The state and the accumulators then agree on the number of sort keys. A repeated key can never break a tie the earlier one left, so dropping it doesn't change results. As with `LexOrdering` elsewhere, the first occurrence wins, so `ORDER BY b ASC, b DESC` orders like `ORDER BY b ASC`. ## What is the testing strategy for this PR? A new block in `aggregate.slt` next to the existing ordered `string_agg` tests. Its table has a unique sort key, so each expected value is decided by the ordering, not by a tie. It covers: - `first_value`, `last_value` and `nth_value`, with `nth_value` using an expression key (`k + 0, k + 0`) - `array_agg`, plus `string_agg` with `ORDER BY k DESC, k ASC` - `DISTINCT ON (g) ... ORDER BY g, g, k` Without the change, three of the new queries fail: the two panics and the RowConverter error from the issue. With it, they pass. The other `.slt` files that exercise ordered aggregates (`aggregate`, `array_agg`, `group_by`, `first_last_*`, `distinct_on`, `window`, `order`, `subquery_sort`) still pass. I also ran every query in the issue's matrix and compared it with the same query with the repeated key removed. All twelve return the same rows. ## Are there any user-facing changes? Queries that failed now return results. No API changes. ## Notes for reviewers - **`min`/`max` are no longer part of this.** The schema mismatch they hit was a separate bug, fixed by apache#25402 (merged). This PR is the duplicate-sort-key fix on top of it: `build()` now clears the ORDER BY for an order-insensitive aggregate, and otherwise drops repeated sort keys. - **`with_new_expressions` rebuilds `order_bys` by zipping the existing keys with new expressions.** In principle a rewrite could map two distinct sort keys onto the same expression and reintroduce a repeat. Checking the callers, the only production one that passes the order-by list is the physical planner (`core/src/physical_planner.rs`), and it passes the keys back unchanged; the window sliding-aggregate caller passes an empty list. Thanks to @haochunchang for independently going through these.
1 parent ba19bbf commit 9e36344

2 files changed

Lines changed: 59 additions & 4 deletions

File tree

‎datafusion/physical-expr/src/aggregate.rs‎

Lines changed: 10 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@ use datafusion_functions_aggregate_common::accumulator::{
6161
};
6262
use datafusion_functions_aggregate_common::order::AggregateOrderSensitivity;
6363
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
64-
use datafusion_physical_expr_common::sort_expr::PhysicalSortExpr;
64+
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
6565

6666
#[derive(Debug, Clone)]
6767
struct AggregateHumanDisplay {
@@ -265,12 +265,18 @@ impl AggregateExprBuilder {
265265
assert_or_internal_err!(!args.is_empty(), "args should not be empty");
266266

267267
// An order-insensitive aggregate ignores its ORDER BY, so drop it here.
268-
// Everything derived from `order_bys` below, such as the ordering fields
269-
// in the aggregate's state, then agrees that there is no ordering.
268+
// Otherwise drop sort keys that repeat an earlier one: a repeated key can
269+
// never break a tie the earlier one left (`ORDER BY b ASC, b DESC` orders
270+
// like `ORDER BY b ASC`), and accumulators build their ordering with
271+
// `LexOrdering`, which drops such repeats. Everything derived from
272+
// `order_bys` below, such as the ordering fields in the aggregate's
273+
// state, then matches the sort keys the accumulators compare.
270274
let order_bys = if fun.order_sensitivity().is_insensitive() {
271275
vec![]
272276
} else {
273-
order_bys
277+
LexOrdering::new(order_bys)
278+
.map(Vec::from)
279+
.unwrap_or_default()
274280
};
275281

276282
let ordering_types = order_bys

‎datafusion/sqllogictest/test_files/aggregate.slt‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8230,6 +8230,55 @@ c,a,b,d d,b,a,c
82308230
statement ok
82318231
drop table t;
82328232

8233+
# A sort key repeated in an ordered aggregate's ORDER BY is redundant, and the
8234+
# query must behave as if the key were listed once (issue #25398). Each `k` is
8235+
# unique so every expected value is determined by the ordering.
8236+
statement ok
8237+
CREATE TABLE dup_sort_keys (g INT, k INT, v INT) AS VALUES
8238+
(1, 2, 20), (1, 1, 10), (2, 4, 40), (2, 3, 30);
8239+
8240+
query IIII
8241+
SELECT g,
8242+
first_value(v ORDER BY k, k),
8243+
last_value(v ORDER BY k, k),
8244+
nth_value(v, 2 ORDER BY k + 0, k + 0)
8245+
FROM dup_sort_keys GROUP BY g ORDER BY g;
8246+
----
8247+
1 10 20 20
8248+
2 30 40 40
8249+
8250+
query I?T
8251+
SELECT g,
8252+
array_agg(v ORDER BY k, k),
8253+
string_agg(CAST(v AS VARCHAR), ',' ORDER BY k DESC, k ASC)
8254+
FROM dup_sort_keys GROUP BY g ORDER BY g;
8255+
----
8256+
1 [10, 20] 20,10
8257+
2 [30, 40] 40,30
8258+
8259+
# With DISTINCT, the ORDER BY may only sort by the aggregated expression. The
8260+
# repeated key is dropped first, so these are accepted.
8261+
query I?
8262+
SELECT g, array_agg(DISTINCT k ORDER BY k, k) FROM dup_sort_keys GROUP BY g ORDER BY g;
8263+
----
8264+
1 [1, 2]
8265+
2 [3, 4]
8266+
8267+
query I?
8268+
SELECT g, array_agg(DISTINCT k ORDER BY k DESC, k ASC) FROM dup_sort_keys GROUP BY g ORDER BY g;
8269+
----
8270+
1 [2, 1]
8271+
2 [4, 3]
8272+
8273+
query II
8274+
SELECT DISTINCT ON (g) g, v FROM dup_sort_keys ORDER BY g, g, k;
8275+
----
8276+
1 10
8277+
2 30
8278+
8279+
statement ok
8280+
drop table dup_sort_keys;
8281+
82338282

82348283
# Tests for aggregating with NaN values
82358284
statement ok

0 commit comments

Comments
 (0)