Skip to content

Commit 6b0b704

Browse files
mkleenclaudeadriangb
authored andcommitted
feat: DISTINCT handling for Aggregate UDFs (apache#25288)
## Which issue does this PR close? - Closes apache#22644. - Closes apache#11686 - Part of apache#24929 (the `min`/`max` case). ## Rationale for this change `SELECT g, min(DISTINCT x) FROM t GROUP BY g` is planned as if `DISTINCT` mattered. `SingleDistinctToGroupBy` rewrites it into an inner group by at `(g, x)` grain just to deduplicate `x`, even though `min` returns the same value with or without duplicates. On a 4M-row table with ~1M distinct `x` values, that extra stage makes the query **up to 10x slower** and reserves **~190 MB** where the plain `min(x)` needs less than 1 MB. The same applies to every aggregate whose result cannot change when duplicates are removed: `max`, `bool_and`, `bool_or`, `bit_and`, `bit_or`, `approx_distinct`. Nothing in DataFusion could say which aggregates those are. `SingleDistinctToGroupBy` identifies `sum`/`min`/`max` by lowercased function name, and a user-defined aggregate had no way to declare the property at all. ## What changes are included in this PR? **A new `AggregateUDFImpl::distinct_handling()` method** returning a new enum `DistinctHandling`: | Variant | Meaning | Built-ins | |---|---|---| | `Insensitive` | Duplicates cannot change the result (the merge is idempotent), so the planner may drop `DISTINCT`. | `min`, `max`, `bool_and`, `bool_or`, `bit_and`, `bit_or`, `approx_distinct`, `grouping` | | `Sensitive` *(default)* | `DISTINCT` is applied, either by the accumulator itself (`count`, `sum`, `avg`, `var_samp`, `array_agg`, `bit_xor`, ...) or by `SingleDistinctToGroupBy` deduplicating the input first (`stddev`, `approx_median`). | everything not listed | | `Unsupported` | The result depends on duplicates, but nothing deduplicates the input, so `f(DISTINCT ...)` errors or silently returns the non-distinct answer. Declaration only for now; rejecting these at planning time is a follow-up. | `corr`, `covar_samp`, `covar_pop`, `regr_*`, `nth_value`, `approx_percentile_cont`, `approx_percentile_cont_with_weight` | `first_value`, `last_value` and `any_value` stay at `Sensitive` with a TODO: whether `DISTINCT` is a no-op for them depends on `ORDER BY`. **A new logical optimizer rule, `EliminateAggregateDistinct`**, placed before `SingleDistinctToGroupBy`. It clears the `DISTINCT` flag on `Insensitive` aggregates and keeps the output column name with an alias: ```text Aggregate: groupBy=[[g]], aggr=[[min(DISTINCT x)]] -- becomes Aggregate: groupBy=[[g]], aggr=[[min(x) AS min(DISTINCT x)]] ``` ## What is the testing strategy for this PR? - **Unit tests** in `datafusion/optimizer/src/eliminate_aggregate_distinct.rs`: `min`, `min`+`max`, a non-distinct aggregate beside the distinct one, `FILTER`, the negative cases `sum` and `bit_xor`, a mixed node that must be left alone (on its own and followed by `SingleDistinctToGroupBy`), an `Sensitive` distinct aggregate in the group expressions, and a plan with no `Aggregate`. - **sqllogictest:** - `aggregates_simplify.slt` gets a new section. For each `Ignored` aggregate it checks the `EXPLAIN` plan and the query results, over data with duplicates and `NULL`s. It also covers the negative cases (`bit_xor`, `count`), a mixed node, and `FILTER`. - `single_distinct_to_groupby.slt` has an updated expectation for `min(DISTINCT v)`. - `explain.slt` lists the new rule. - **Documentation:** a new "Declaring how an Aggregate UDF treats `DISTINCT`" section in `adding-udfs.md`, and the rule in `optimizer_rule_reference.md`. ### Benchmark Here are some results from a local benchmark. Every query has the shape `SELECT g, <aggregate> FROM t GROUP BY g`, over 4M rows where `x` has about 1M distinct values and `b` has two. Speedup (`main` time / branch time): | query | 2k groups, 1 part | 2k groups, 10 parts | 500k groups, 1 part | 500k groups, 10 parts | |---|---:|---:|---:|---:| | min | 10.10x | 6.56x | 3.44x | 2.49x | | max | 10.37x | 7.19x | 3.35x | 2.44x | | bit_and | 10.36x | 7.73x | 3.50x | 2.53x | | bit_or | 10.25x | 7.10x | 3.33x | 2.52x | | bool_and | 1.66x | 1.53x | 1.51x | 2.36x | | bool_or | 1.50x | 1.65x | 1.50x | 1.71x | | approx_distinct | 1.97x | 1.77x | 1.77x | 1.77x | Peak memory-pool reservation in MB (`main` → branch): | query | 2k groups, 1 part | 2k groups, 10 parts | 500k groups, 1 part | 500k groups, 10 parts | |---|---:|---:|---:|---:| | min | 191.4 → 0.2 | 167.9 → 1.5 | 191.4 → 24.0 | 167.9 → 42.7 | | max | 191.4 → 0.2 | 167.9 → 1.5 | 191.4 → 24.0 | 167.8 → 42.9 | | bit_and | 191.4 → 0.2 | 168.2 → 1.5 | 191.4 → 24.0 | 167.5 → 41.8 | | bit_or | 191.4 → 0.2 | 167.6 → 1.5 | 191.4 → 24.0 | 167.5 → 42.0 | | bool_and | 0.3 → 0.1 | 2.7 → 1.3 | 28.2 → 20.0 | 34.1 → 26.0 | | bool_or | 0.3 → 0.1 | 2.7 → 1.3 | 28.2 → 20.0 | 35.4 → 26.9 | | approx_distinct | 191.4 → 31.5 | 170.5 → 41.5 | 191.4 → 62.5 | 168.0 → 88.5 | ## Are there any user-facing changes? - `AggregateUDFImpl::distinct_handling()` with default `DistinctHandling::Sensitive`, so existing implementations compile and behave as before. ## LLM-generated code disclosure This PR includes LLM-generated code and comments. All LLM-generated content has been manually reviewed. --------- Co-authored-by: Claude Opus 5 <[email protected]> Co-authored-by: Adrian Garcia Badaracco <[email protected]>
1 parent 368ab3f commit 6b0b704

26 files changed

Lines changed: 1110 additions & 34 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: 46 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,20 @@ 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::Insensitive`] for duplicate-insensitive
951+
/// functions so that `f(DISTINCT x)` is planned as `f(x)`.
952+
///
953+
/// Return [`DistinctHandling::Unsupported`] if the accumulator does not
954+
/// implement `DISTINCT`, that is, it does not read `is_distinct`, or it
955+
/// rejects `DISTINCT` with an error. The planner then has to deduplicate
956+
/// the input or reject the query. Nothing reads this variant yet:
957+
/// rejecting such queries at planning time is a follow-up change.
958+
fn distinct_handling(&self) -> DistinctHandling {
959+
DistinctHandling::Sensitive
960+
}
961+
943962
/// Returns the documentation for this Aggregate UDF.
944963
///
945964
/// Documentation can be accessed programmatically as well as
@@ -1687,6 +1706,10 @@ impl AggregateUDFImpl for AliasedAggregateUDFImpl {
16871706
self.inner.set_monotonicity(data_type)
16881707
}
16891708

1709+
fn distinct_handling(&self) -> DistinctHandling {
1710+
self.inner.distinct_handling()
1711+
}
1712+
16901713
fn documentation(&self) -> Option<&Documentation> {
16911714
self.inner.documentation()
16921715
}
@@ -1713,6 +1736,29 @@ pub enum SetMonotonicity {
17131736
NotMonotonic,
17141737
}
17151738

1739+
/// How an aggregate function treats the `DISTINCT` modifier.
1740+
///
1741+
/// Mathematically, `Insensitive` means the function's merge operation is
1742+
/// idempotent (its state forms a semilattice): f(S ⊎ S) = f(S), so
1743+
/// removing duplicates from the input cannot change the result.
1744+
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1745+
#[non_exhaustive]
1746+
pub enum DistinctHandling {
1747+
/// The result is the same with or without `DISTINCT`, so the planner
1748+
/// is free to drop it. `min`, `max`, `bool_and`, `bit_or`, ...
1749+
Insensitive,
1750+
/// The accumulator reads `AccumulatorArgs::is_distinct` and deduplicates
1751+
/// its input, so the planner must leave the flag alone. `count`, `sum`,
1752+
/// `avg`, `var_samp`, `array_agg`, ... This is the default.
1753+
Sensitive,
1754+
/// The accumulator does not implement `DISTINCT`: it does not read
1755+
/// `is_distinct`, or it rejects `DISTINCT` with an error. The planner has
1756+
/// to deduplicate the input first (today `SingleDistinctToGroupBy` does
1757+
/// that for single-argument functions) or reject the query. `stddev`,
1758+
/// `approx_median`, `corr`, `regr_*`, `nth_value`, ...
1759+
Unsupported,
1760+
}
1761+
17161762
#[cfg(test)]
17171763
mod test {
17181764
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::Insensitive` — 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+
// `Sensitive` 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::Insensitive
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
@@ -147,4 +147,10 @@ impl AggregateUDFImpl for ApproxMedian {
147147
fn documentation(&self) -> Option<&Documentation> {
148148
self.doc()
149149
}
150+
151+
fn distinct_handling(&self) -> datafusion_expr::DistinctHandling {
152+
// The accumulator rejects `DISTINCT` with `not_impl_err!`, so the
153+
// planner has to deduplicate the input first.
154+
datafusion_expr::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. Only XOR has a distinct accumulator.
327+
BitwiseOperationType::And | BitwiseOperationType::Or => {
328+
DistinctHandling::Insensitive
329+
}
330+
// XOR cancels duplicate pairs, so `DISTINCT` is meaningful.
331+
BitwiseOperationType::Xor => DistinctHandling::Sensitive,
332+
}
333+
}
321334
}
322335

323336
struct BitAndAccumulator<T: ArrowNumericType> {

0 commit comments

Comments
 (0)