Skip to content

Commit 07f24b6

Browse files
committed
Treat an unanswered groups accumulator question as no permission
`AggregateUDFImpl::groups_accumulator_supported_for_types` returned `bool` with a `false` default, and `rewrite_pays_for_count` read `false` as "the rewrite pays". Every aggregate that did not override the method was therefore waved through the gate, which is the permissive answer rather than the safe one. Return `Option<bool>` instead, defaulting to `None`, and rewrite only on `Some(false)`. `None` says the aggregate does not answer the question, and silence is not evidence that the rewrite pays. Measured on unmodified upstream, over 4,000,000 rows in 2,000 groups, `SELECT g, count(*), sum(DISTINCT int_col) FROM t GROUP BY g` reached the gated path and regressed 3.15x: 71.0 MiB unrewritten against 223.4 MiB rewritten. `min(DISTINCT x)` reached it too, and regresses much further, because `min(DISTINCT x)` is `min(x)` and the unrewritten plan keeps one scalar per group. `Count` is the only implementor and its answers are unchanged, so no plan that the gate already allowed changes shape.
1 parent b28c289 commit 07f24b6

4 files changed

Lines changed: 199 additions & 25 deletions

File tree

‎datafusion/expr/src/udaf.rs‎

Lines changed: 17 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -258,7 +258,7 @@ impl AggregateUDF {
258258
&self,
259259
arg_types: &[DataType],
260260
is_distinct: bool,
261-
) -> bool {
261+
) -> Option<bool> {
262262
self.inner
263263
.groups_accumulator_supported_for_types(arg_types, is_distinct)
264264
}
@@ -638,19 +638,25 @@ pub trait AggregateUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
638638
/// changing its mind over: the adapter's per-group state can be orders of
639639
/// magnitude larger.
640640
///
641-
/// The default is `false`, matching the default of
642-
/// [`Self::groups_accumulator_supported`]. An implementation that
643-
/// overrides that one and whose answer is decided by the argument types
644-
/// and `DISTINCT` alone should override this one too, and have the
645-
/// physical method call it so the two cannot disagree. An implementation
646-
/// whose answer needs more than the argument types should leave this at
647-
/// `false`, which claims nothing.
641+
/// The default is `None`, which means the implementation does not answer
642+
/// this question. An implementation that overrides
643+
/// [`Self::groups_accumulator_supported`], and whose answer is decided by
644+
/// the argument types and `DISTINCT` alone, should override this one too,
645+
/// and have the physical method call it so the two cannot disagree. An
646+
/// implementation whose answer needs more than the argument types should
647+
/// leave this at `None`.
648+
///
649+
/// `None` is not a third answer to the question. A caller must not read it
650+
/// as either `Some(true)` or `Some(false)`, because both readings are
651+
/// wrong for some implementation that returns it. A caller that has to act
652+
/// on an unanswered question must take the action that is safe when either
653+
/// answer turns out to be the true one.
648654
fn groups_accumulator_supported_for_types(
649655
&self,
650656
_arg_types: &[DataType],
651657
_is_distinct: bool,
652-
) -> bool {
653-
false
658+
) -> Option<bool> {
659+
None
654660
}
655661

656662
/// Return a specialized [`GroupsAccumulator`] that manages state
@@ -1592,7 +1598,7 @@ impl AggregateUDFImpl for AliasedAggregateUDFImpl {
15921598
&self,
15931599
arg_types: &[DataType],
15941600
is_distinct: bool,
1595-
) -> bool {
1601+
) -> Option<bool> {
15961602
self.inner
15971603
.groups_accumulator_supported_for_types(arg_types, is_distinct)
15981604
}

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

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -354,21 +354,22 @@ impl AggregateUDFImpl for Count {
354354
.map(|field| field.data_type().clone())
355355
.collect::<Vec<_>>();
356356
self.groups_accumulator_supported_for_types(&arg_types, args.is_distinct)
357+
.unwrap_or(false)
357358
}
358359

359360
fn groups_accumulator_supported_for_types(
360361
&self,
361362
arg_types: &[DataType],
362363
is_distinct: bool,
363-
) -> bool {
364+
) -> Option<bool> {
364365
if arg_types.len() != 1 {
365-
return false;
366+
return Some(false);
366367
}
367368
if !is_distinct {
368-
return true;
369+
return Some(true);
369370
}
370371
// Keep in step with `create_distinct_count_groups_accumulator`.
371-
matches!(
372+
Some(matches!(
372373
arg_types[0],
373374
DataType::Int8
374375
| DataType::Int16
@@ -378,7 +379,7 @@ impl AggregateUDFImpl for Count {
378379
| DataType::UInt16
379380
| DataType::UInt32
380381
| DataType::UInt64
381-
)
382+
))
382383
}
383384

384385
fn create_groups_accumulator(

‎datafusion/optimizer/src/single_distinct_to_groupby.rs‎

Lines changed: 129 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -81,10 +81,12 @@ use datafusion_expr::{
8181
/// empty input the inner group by produces no rows at all, and a `sum` of no
8282
/// rows is NULL where `count` is 0.
8383
///
84-
/// That `count` is allowed only when the distinct argument has no specialized
85-
/// `GroupsAccumulator` of its own, so that the rewrite is taking the distinct
86-
/// aggregate off `GroupsAccumulatorAdapter` rather than only adding an inner
87-
/// group by. See `rewrite_pays_for_count` for the measurements behind that.
84+
/// That `count` is allowed only when the distinct aggregate reports that it has
85+
/// no specialized `GroupsAccumulator` for its argument types, so that the
86+
/// rewrite is taking the distinct aggregate off `GroupsAccumulatorAdapter`
87+
/// rather than only adding an inner group by. A function that does not report
88+
/// on this at all keeps the previous behaviour and is left alone. See
89+
/// `rewrite_pays_for_count` for the measurements behind that.
8890
#[derive(Default, Debug)]
8991
pub struct SingleDistinctToGroupBy {}
9092

@@ -190,6 +192,19 @@ fn is_single_distinct_agg(
190192
/// Q22, whose `count(DISTINCT "UserID")` is over an `Int64`, measured a 132%
191193
/// increase in peak memory pool reservation when the rewrite applied to it.
192194
///
195+
/// `Some(false)` is the only answer that buys anything. `Some(true)` says the
196+
/// call never reaches the adapter. `None` says the function does not answer the
197+
/// question from the argument types, which is the default and so the answer for
198+
/// almost every function. Silence is not evidence, and reading it as `Some(false)`
199+
/// would open this path to every such function: `sum(DISTINCT int_col)` beside a
200+
/// `count(*)` measured 3.15x the peak memory once rewritten, over 4,000,000 rows
201+
/// in 2,000 groups.
202+
///
203+
/// The predicate is a proxy, not the true discriminator. What decides the
204+
/// outcome is the cost per distinct value on each side, which this rule cannot
205+
/// see. The proxy is deliberately conservative in the direction that leaves a
206+
/// plan alone.
207+
///
193208
/// The existing tolerance of a non-distinct `sum`, `min` or `max` predates this
194209
/// and is left alone: narrowing it would change plans that have always been
195210
/// rewritten, which no measurement here calls for.
@@ -202,7 +217,7 @@ fn rewrite_pays_for_count(
202217
.iter()
203218
.map(|arg| arg.get_type(input_schema))
204219
.collect::<Result<Vec<_>>>()?;
205-
if !func.groups_accumulator_supported_for_types(&arg_types, true) {
220+
if func.groups_accumulator_supported_for_types(&arg_types, true) == Some(false) {
206221
return Ok(true);
207222
}
208223
}
@@ -446,7 +461,9 @@ mod tests {
446461
use datafusion_common::config::ConfigOptions;
447462
use datafusion_expr::ExprFunctionExt;
448463
use datafusion_expr::expr::GroupingSet;
464+
use datafusion_expr::function::AccumulatorArgs;
449465
use datafusion_expr::registry::{FunctionRegistry, MemoryFunctionRegistry};
466+
use datafusion_expr::{Accumulator, AggregateUDFImpl, Signature, Volatility};
450467
use datafusion_expr::{
451468
lit,
452469
logical_plan::builder::{LogicalPlanBuilder, table_scan},
@@ -467,6 +484,65 @@ mod tests {
467484
))
468485
}
469486

487+
fn sum_distinct(expr: Expr) -> Expr {
488+
Expr::AggregateFunction(AggregateFunction::new_udf(
489+
sum_udaf(),
490+
vec![expr],
491+
true,
492+
None,
493+
vec![],
494+
None,
495+
))
496+
}
497+
498+
/// An aggregate that leaves
499+
/// [`AggregateUDFImpl::groups_accumulator_supported_for_types`] at its
500+
/// default, which is what almost every function in the wild does.
501+
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
502+
struct SilentUdaf {
503+
signature: Signature,
504+
}
505+
506+
impl SilentUdaf {
507+
fn new() -> Self {
508+
Self {
509+
signature: Signature::any(1, Volatility::Immutable),
510+
}
511+
}
512+
}
513+
514+
impl AggregateUDFImpl for SilentUdaf {
515+
fn name(&self) -> &str {
516+
"silent"
517+
}
518+
519+
fn signature(&self) -> &Signature {
520+
&self.signature
521+
}
522+
523+
fn return_type(&self, _arg_types: &[DataType]) -> Result<DataType> {
524+
Ok(DataType::UInt32)
525+
}
526+
527+
fn accumulator(
528+
&self,
529+
_acc_args: AccumulatorArgs,
530+
) -> Result<Box<dyn Accumulator>> {
531+
unimplemented!("not needed for this test")
532+
}
533+
}
534+
535+
fn silent_distinct(expr: Expr) -> Expr {
536+
Expr::AggregateFunction(AggregateFunction::new_udf(
537+
Arc::new(AggregateUDF::from(SilentUdaf::new())),
538+
vec![expr],
539+
true,
540+
None,
541+
vec![],
542+
None,
543+
))
544+
}
545+
470546
fn count_star() -> Expr {
471547
Expr::AggregateFunction(AggregateFunction::new_udf(
472548
count_udaf(),
@@ -808,6 +884,54 @@ mod tests {
808884
)
809885
}
810886

887+
#[test]
888+
fn distinct_over_a_function_with_no_opinion_is_not_rewritten() -> Result<()> {
889+
let table_scan = test_table_scan()?;
890+
891+
let plan = LogicalPlanBuilder::from(table_scan)
892+
.aggregate(
893+
vec![col("a")],
894+
vec![silent_distinct(col("b")), count(col("c"))],
895+
)?
896+
.build()?;
897+
898+
// Should not work: `silent` leaves
899+
// `groups_accumulator_supported_for_types` at its default, so it
900+
// reports nothing about `GroupsAccumulatorAdapter`. Silence is not
901+
// evidence that the rewrite pays, and the rule must not read it as
902+
// permission
903+
assert_optimized_plan_equal!(
904+
plan,
905+
@r"
906+
Aggregate: groupBy=[[test.a]], aggr=[[silent(DISTINCT test.b), count(test.c)]] [a:UInt32, silent(DISTINCT test.b):UInt32;N, count(test.c):Int64]
907+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
908+
"
909+
)
910+
}
911+
912+
#[test]
913+
fn distinct_sum_and_count_is_not_rewritten() -> Result<()> {
914+
let table_scan = test_table_scan()?;
915+
916+
let plan = LogicalPlanBuilder::from(table_scan)
917+
.aggregate(
918+
vec![col("a")],
919+
vec![sum_distinct(col("b")), count(col("c"))],
920+
)?
921+
.build()?;
922+
923+
// Should not work: `sum` reports nothing about
924+
// `GroupsAccumulatorAdapter` either, and measurement says this shape
925+
// costs 3.15x the peak memory once rewritten
926+
assert_optimized_plan_equal!(
927+
plan,
928+
@r"
929+
Aggregate: groupBy=[[test.a]], aggr=[[sum(DISTINCT test.b), count(test.c)]] [a:UInt32, sum(DISTINCT test.b):UInt64;N, count(test.c):Int64]
930+
TableScan: test [a:UInt32, b:UInt32, c:UInt32]
931+
"
932+
)
933+
}
934+
811935
#[test]
812936
fn group_by_with_expr() -> Result<()> {
813937
let table_scan = test_table_scan().unwrap();

‎datafusion/sqllogictest/test_files/single_distinct_to_groupby.slt‎

Lines changed: 47 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -21,10 +21,12 @@
2121
# (`datafusion.optimizer.max_passes = 0`, so the aggregate runs as written) and
2222
# once with it enabled. The two must agree.
2323
#
24-
# A non-distinct `count` may only join the distinct aggregate when the distinct
25-
# argument has no specialized `GroupsAccumulator` of its own. `x` is the
26-
# `VARCHAR` that qualifies, `xi` the `INT` that does not; both hold the same
27-
# values so the two sides can be compared directly.
24+
# A non-distinct `count` may only join the distinct aggregate when that
25+
# aggregate reports that it has no specialized `GroupsAccumulator` for its
26+
# argument types. `x` is the `VARCHAR` that qualifies, `xi` the `INT` that does
27+
# not; both hold the same values so the two sides can be compared directly.
28+
# An aggregate that reports nothing, which is every aggregate but `count`, also
29+
# does not qualify.
2830

2931
statement ok
3032
CREATE TABLE t(g INT, x VARCHAR, xi INT, v INT);
@@ -109,6 +111,29 @@ logical_plan
109111
02)--Aggregate: groupBy=[[t.g]], aggr=[[count(Int64(1)), count(DISTINCT t.xi)]]
110112
03)----TableScan: t projection=[g, xi]
111113

114+
# `sum` reports nothing about `GroupsAccumulator` support from the argument
115+
# types, and neither does any aggregate but `count`. Silence is not evidence
116+
# that the rewrite pays, so the count keeps this plan unrewritten as well.
117+
# Rewritten, this shape measured 3.15x the peak memory over 4,000,000 rows in
118+
# 2,000 groups
119+
query TT
120+
EXPLAIN SELECT g, count(*) AS records, sum(DISTINCT v) AS distinct_v FROM t GROUP BY g;
121+
----
122+
logical_plan
123+
01)Projection: t.g, count(Int64(1)) AS count(*) AS records, sum(DISTINCT t.v) AS distinct_v
124+
02)--Aggregate: groupBy=[[t.g]], aggr=[[count(Int64(1)), sum(DISTINCT CAST(t.v AS Int64))]]
125+
03)----TableScan: t projection=[g, v]
126+
127+
# `min(DISTINCT v)` is the same value as `min(v)`, so the unrewritten plan keeps
128+
# one scalar per group while the rewrite would build a row per distinct pair
129+
query TT
130+
EXPLAIN SELECT g, count(*) AS records, min(DISTINCT v) AS distinct_min_v FROM t GROUP BY g;
131+
----
132+
logical_plan
133+
01)Projection: t.g, count(Int64(1)) AS count(*) AS records, min(DISTINCT t.v) AS distinct_min_v
134+
02)--Aggregate: groupBy=[[t.g]], aggr=[[count(Int64(1)), min(DISTINCT t.v)]]
135+
03)----TableScan: t projection=[g, v]
136+
112137
# The gate covers only the count. A plan that already qualified through sum,
113138
# min or max is still rewritten over the same INT column
114139
query TT
@@ -365,6 +390,15 @@ SELECT count(*) AS records, count(DISTINCT xi) AS distinct_xi FROM empty_t;
365390
----
366391
0 0
367392

393+
# gated: the count keeps a distinct aggregate that reports nothing unrewritten
394+
query III
395+
SELECT g, count(*) AS records, sum(DISTINCT v) AS distinct_v
396+
FROM t GROUP BY g ORDER BY g;
397+
----
398+
1 4 112
399+
2 2 3
400+
3 1 1
401+
368402
statement ok
369403
set datafusion.optimizer.max_passes = 3;
370404

@@ -400,6 +434,15 @@ SELECT count(*) AS records, count(DISTINCT xi) AS distinct_xi FROM empty_t;
400434
----
401435
0 0
402436

437+
# gated: the count keeps a distinct aggregate that reports nothing unrewritten
438+
query III
439+
SELECT g, count(*) AS records, sum(DISTINCT v) AS distinct_v
440+
FROM t GROUP BY g ORDER BY g;
441+
----
442+
1 4 112
443+
2 2 3
444+
3 1 1
445+
403446
statement ok
404447
DROP TABLE failed;
405448

0 commit comments

Comments
 (0)