Skip to content

Commit bcfe457

Browse files
mkleenclaude
andcommitted
feat: teach AggregateUDFImpl how it treats DISTINCT, and strip the flag when it is a no-op
Nothing recorded whether an aggregate cares about duplicates in its input. `min(DISTINCT x)` already built a plain `MinAccumulator`, so the flag was a no-op at execution time, but `SingleDistinctToGroupBy` still saw it and rewrote `SELECT g, min(DISTINCT x) FROM t GROUP BY g` into an inner group by at `(g, x)` grain. Callers also had no way to ask the question: the rule identified sum/min/max by lowercased string name. Add `AggregateUDFImpl::distinct_handling`, returning a three-valued `DistinctHandling`: - `Ignored` - the merge is idempotent, so `DISTINCT` cannot change the result and the planner may drop it - `Honored` - the accumulator reads `is_distinct` and deduplicates - `Unsupported` - the accumulator does not implement `DISTINCT` `Honored` is the default, so external UDFs are unaffected. The property is forwarded from both the `AggregateUDF` wrapper and `AliasedAggregateUDFImpl`. Tag the built-ins. `Ignored`: min, max, bool_and, bool_or, approx_distinct, and the AND/OR arms of the bitwise operation (XOR cancels duplicate pairs and stays `Honored`). `Unsupported`: the aggregates that either reject `DISTINCT` already or silently return the non-distinct answer. first_value, last_value and any_value keep the default with a TODO, because whether they ignore duplicates depends on `ORDER BY`. Add `EliminateAggregateDistinct`, inserted immediately before `SingleDistinctToGroupBy`. It returns `Transformed::no` for every node that is not an `Aggregate`, and uses `NamePreserver` to keep the output schema intact, so the plan reads `min(t.v) AS min(DISTINCT t.v)`. `Unsupported` is declared but not yet enforced. Rejecting `corr(DISTINCT x, y)` fixes a silent wrong answer but turns queries that are accepted today into planning errors, which belongs in its own change. Over 4,000,000 rows in 2,000 groups, `min(DISTINCT x)` needed a 192M pool before this change and completes under 1M after it. Part of apache#24929, tracked as apache#11686. Co-Authored-By: Claude Opus 5 <[email protected]> Claude-Session: https://claude.ai/code/session_015YwFpxheiiUNMadTNyeHiu
1 parent 86ba5e0 commit bcfe457

27 files changed

Lines changed: 771 additions & 62 deletions

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 28 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -35,33 +35,34 @@ Rule order matters. The default pipeline may change between releases.
3535

3636
### Logical Optimizer Rules
3737

38-
| order | rule | summary |
39-
| ----- | ----------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
40-
| 1 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
41-
| 2 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
42-
| 3 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
43-
| 4 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
44-
| 5 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
45-
| 6 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
46-
| 7 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
47-
| 8 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
48-
| 9 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
49-
| 10 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
50-
| 11 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
51-
| 12 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
52-
| 13 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
53-
| 14 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
54-
| 15 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
55-
| 16 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
56-
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
57-
| 18 | `push_down_limit` | Moves literal limits to scans/unions, merges limits, and pushes `Sort(fetch=N)` onto a preserved join side only when every sort key is from it; the outer Sort stays. |
58-
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59-
| 20 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
60-
| 21 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
61-
| 22 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
62-
| 23 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
63-
| 24 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
64-
| 25 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
38+
| order | rule | summary |
39+
|-------| ----------------------------------------- | --------------------------------------------------------------------------------------------------------------------------- |
40+
| 1 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
41+
| 2 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
42+
| 3 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
43+
| 4 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
44+
| 5 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
45+
| 6 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
46+
| 7 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
47+
| 8 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
48+
| 9 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
49+
| 10 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
50+
| 11 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
51+
| 12 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
52+
| 13 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
53+
| 14 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
54+
| 15 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
55+
| 16 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
56+
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
57+
| 18 | `push_down_limit` | Moves literal limits closer to scans and unions and merges adjacent limits. |
58+
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59+
| 20 | `eliminate_aggregate_distinct` | Drops the `DISTINCT` modifier from aggregates whose result cannot change, such as `min`, `max` and `bit_or`. |
60+
| 21 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
61+
| 22 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
62+
| 23 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
63+
| 24 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
64+
| 25 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
65+
| 26 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
6566

6667
### Physical Optimizer Rules
6768

‎datafusion/expr/src/lib.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -137,10 +137,10 @@ pub use partition_evaluator::PartitionEvaluator;
137137
pub use sqlparser;
138138
pub use table_source::{TableProviderFilterPushDown, TableSource, TableType};
139139
pub use udaf::{
140-
AggregateUDF, AggregateUDFImpl, ReversedUDAF, SetMonotonicity, StatisticsArgs,
141-
UdafDisplayNameBuilder, UdafHumanDisplayBuilder, UdafSchemaNameBuilder,
142-
UdafWindowFunctionDisplayNameBuilder, UdafWindowFunctionSchemaNameBuilder,
143-
udaf_default_return_field,
140+
AggregateUDF, AggregateUDFImpl, DistinctHandling, ReversedUDAF, SetMonotonicity,
141+
StatisticsArgs, UdafDisplayNameBuilder, UdafHumanDisplayBuilder,
142+
UdafSchemaNameBuilder, UdafWindowFunctionDisplayNameBuilder,
143+
UdafWindowFunctionSchemaNameBuilder, udaf_default_return_field,
144144
};
145145
#[expect(deprecated)]
146146
pub use udaf::{

‎datafusion/expr/src/udaf.rs‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -360,6 +360,11 @@ impl AggregateUDF {
360360
self.inner.supports_within_group_clause()
361361
}
362362

363+
/// See [`AggregateUDFImpl::distinct_handling`] for more details.
364+
pub fn distinct_handling(&self) -> DistinctHandling {
365+
self.inner.distinct_handling()
366+
}
367+
363368
/// Returns the documentation for this Aggregate UDF.
364369
///
365370
/// Documentation can be accessed programmatically as well as
@@ -940,6 +945,17 @@ pub trait AggregateUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
940945
false
941946
}
942947

948+
/// How this function treats the `DISTINCT` modifier.
949+
///
950+
/// Return [`DistinctHandling::Ignored`] for duplicate-insensitive
951+
/// functions so that `f(DISTINCT x)` is planned as `f(x)`, and
952+
/// [`DistinctHandling::Unsupported`] if the accumulator does not
953+
/// read `is_distinct`, so that `DISTINCT` is rejected at planning
954+
/// time rather than silently ignored.
955+
fn distinct_handling(&self) -> DistinctHandling {
956+
DistinctHandling::Honored
957+
}
958+
943959
/// Returns the documentation for this Aggregate UDF.
944960
///
945961
/// Documentation can be accessed programmatically as well as
@@ -1687,6 +1703,10 @@ impl AggregateUDFImpl for AliasedAggregateUDFImpl {
16871703
self.inner.set_monotonicity(data_type)
16881704
}
16891705

1706+
fn distinct_handling(&self) -> DistinctHandling {
1707+
self.inner.distinct_handling()
1708+
}
1709+
16901710
fn documentation(&self) -> Option<&Documentation> {
16911711
self.inner.documentation()
16921712
}
@@ -1713,6 +1733,24 @@ pub enum SetMonotonicity {
17131733
NotMonotonic,
17141734
}
17151735

1736+
/// How an aggregate function treats the `DISTINCT` modifier.
1737+
///
1738+
/// Mathematically, `Ignored` means the function's merge operation is
1739+
/// idempotent (its state forms a semilattice): f(S ⊎ S) = f(S), so
1740+
/// removing duplicates from the input cannot change the result.
1741+
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1742+
pub enum DistinctHandling {
1743+
/// The result is the same with or without `DISTINCT`, so the planner
1744+
/// is free to drop it. `min`, `max`, `bool_and`, `bit_or`, ...
1745+
Ignored,
1746+
/// The accumulator honours `AccumulatorArgs::is_distinct` and
1747+
/// deduplicates its input. `count`, `sum`, `avg`, `array_agg`, ...
1748+
Honored,
1749+
/// The accumulator does not implement `DISTINCT`. Planning
1750+
/// `f(DISTINCT ...)` is an error. `corr`, `regr_*`, `nth_value`, ...
1751+
Unsupported,
1752+
}
1753+
17161754
#[cfg(test)]
17171755
mod test {
17181756
use crate::{AggregateUDF, AggregateUDFImpl};

‎datafusion/functions-aggregate/src/any_value.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -122,4 +122,9 @@ impl AggregateUDFImpl for AnyValue {
122122
fn documentation(&self) -> Option<&Documentation> {
123123
self.doc()
124124
}
125+
126+
// TODO: this is arguably `DistinctHandling::Ignored` — the accumulator
127+
// ignores `is_distinct` and returns an unspecified input value either
128+
// way. Grouped with `first_value`/`last_value` and left at the default
129+
// `Honored` until that family is settled together.
125130
}

‎datafusion/functions-aggregate/src/approx_distinct.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -38,6 +38,7 @@ use datafusion_common::{
3838
DataFusionError, Result, downcast_value, internal_datafusion_err, internal_err,
3939
not_impl_err,
4040
};
41+
use datafusion_expr::DistinctHandling;
4142
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
4243
use datafusion_expr::utils::format_state_name;
4344
use datafusion_expr::{
@@ -870,6 +871,11 @@ impl AggregateUDFImpl for ApproxDistinct {
870871
fn documentation(&self) -> Option<&Documentation> {
871872
self.doc()
872873
}
874+
875+
fn distinct_handling(&self) -> DistinctHandling {
876+
// Updating an HLL register with a value already seen is a no-op.
877+
DistinctHandling::Ignored
878+
}
873879
}
874880

875881
fn is_fixed_domain_type(data_type: &DataType) -> bool {

‎datafusion/functions-aggregate/src/approx_median.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ use std::fmt::Debug;
2525
use std::sync::Arc;
2626

2727
use datafusion_common::{Result, not_impl_err};
28+
use datafusion_expr::DistinctHandling;
2829
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
2930
use datafusion_expr::utils::format_state_name;
3031
use datafusion_expr::{
@@ -147,4 +148,9 @@ impl AggregateUDFImpl for ApproxMedian {
147148
fn documentation(&self) -> Option<&Documentation> {
148149
self.doc()
149150
}
151+
152+
fn distinct_handling(&self) -> DistinctHandling {
153+
// The accumulator rejects `DISTINCT` with `not_impl_err!`.
154+
DistinctHandling::Unsupported
155+
}
150156
}

‎datafusion/functions-aggregate/src/approx_percentile_cont.rs‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ use datafusion_common::{
3131
DataFusionError, Result, ScalarValue, downcast_value, internal_err, not_impl_err,
3232
plan_err,
3333
};
34+
use datafusion_expr::DistinctHandling;
3435
use datafusion_expr::expr::{AggregateFunction, Sort};
3536
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
3637
use datafusion_expr::utils::format_state_name;
@@ -324,6 +325,13 @@ impl AggregateUDFImpl for ApproxPercentileCont {
324325
fn documentation(&self) -> Option<&Documentation> {
325326
self.doc()
326327
}
328+
329+
fn distinct_handling(&self) -> DistinctHandling {
330+
// Duplicate-sensitive, but the accumulator does not read
331+
// `is_distinct` and today silently returns the non-distinct answer.
332+
// The tag records the intent; enforcement is a follow-up change.
333+
DistinctHandling::Unsupported
334+
}
327335
}
328336

329337
#[derive(Debug)]

‎datafusion/functions-aggregate/src/approx_percentile_cont_with_weight.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,7 @@ use arrow::{array::ArrayRef, datatypes::DataType};
2626
use datafusion_common::ScalarValue;
2727
use datafusion_common::types::{NativeType, logical_float64};
2828
use datafusion_common::{Result, not_impl_err, plan_err};
29+
use datafusion_expr::DistinctHandling;
2930
use datafusion_expr::expr::{AggregateFunction, Sort};
3031
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
3132
use datafusion_expr::{
@@ -281,6 +282,11 @@ impl AggregateUDFImpl for ApproxPercentileContWithWeight {
281282
fn documentation(&self) -> Option<&Documentation> {
282283
self.doc()
283284
}
285+
286+
fn distinct_handling(&self) -> DistinctHandling {
287+
// The accumulator rejects `DISTINCT` with `not_impl_err!`.
288+
DistinctHandling::Unsupported
289+
}
284290
}
285291

286292
#[derive(Debug)]

‎datafusion/functions-aggregate/src/bit_and_or_xor.rs‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@ use datafusion_common::hash_utils::RandomState;
3131

3232
use datafusion_common::cast::as_list_array;
3333
use datafusion_common::{Result, ScalarValue, not_impl_err};
34+
use datafusion_expr::DistinctHandling;
3435
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
3536
use datafusion_expr::utils::format_state_name;
3637
use datafusion_expr::{
@@ -318,6 +319,18 @@ impl AggregateUDFImpl for BitwiseOperation {
318319
fn documentation(&self) -> Option<&Documentation> {
319320
Some(self.documentation)
320321
}
322+
323+
fn distinct_handling(&self) -> DistinctHandling {
324+
match self.operation {
325+
// Bitwise AND/OR are idempotent: duplicates cannot change the
326+
// result, so building a per-group `HashSet` buys nothing.
327+
BitwiseOperationType::And | BitwiseOperationType::Or => {
328+
DistinctHandling::Ignored
329+
}
330+
// XOR cancels duplicate pairs, so `DISTINCT` is meaningful.
331+
BitwiseOperationType::Xor => DistinctHandling::Honored,
332+
}
333+
}
321334
}
322335

323336
struct BitAndAccumulator<T: ArrowNumericType> {

‎datafusion/functions-aggregate/src/bool_and_or.rs‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ use arrow::datatypes::{DataType, FieldRef};
2929
use datafusion_common::internal_err;
3030
use datafusion_common::{Result, ScalarValue};
3131
use datafusion_common::{downcast_value, not_impl_err};
32+
use datafusion_expr::DistinctHandling;
3233
use datafusion_expr::function::{AccumulatorArgs, StateFieldsArgs};
3334
use datafusion_expr::utils::{AggregateOrderSensitivity, format_state_name};
3435
use datafusion_expr::{
@@ -183,6 +184,11 @@ impl AggregateUDFImpl for BoolAnd {
183184
fn documentation(&self) -> Option<&Documentation> {
184185
self.doc()
185186
}
187+
188+
fn distinct_handling(&self) -> DistinctHandling {
189+
// Boolean AND/OR are idempotent: duplicates cannot change the result.
190+
DistinctHandling::Ignored
191+
}
186192
}
187193

188194
#[derive(Debug, Default)]
@@ -313,6 +319,11 @@ impl AggregateUDFImpl for BoolOr {
313319
fn documentation(&self) -> Option<&Documentation> {
314320
self.doc()
315321
}
322+
323+
fn distinct_handling(&self) -> DistinctHandling {
324+
// Boolean AND/OR are idempotent: duplicates cannot change the result.
325+
DistinctHandling::Ignored
326+
}
316327
}
317328

318329
#[derive(Debug, Default)]

0 commit comments

Comments
 (0)