Skip to content

Commit d4c6299

Browse files
committed
perf: move a final table of unique groups into buckets at a quarter of the threshold
1 parent 3d77feb commit d4c6299

4 files changed

Lines changed: 67 additions & 6 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1129,7 +1129,13 @@ config_namespace! {
11291129
/// state of its table and starts over, as long as the emitted groups
11301130
/// do not come back. A final aggregation splits the groups seen so
11311131
/// far and all further input into hash buckets, which are aggregated
1132-
/// one after another and can be spilled and released independently.
1132+
/// one after another and can be spilled and released independently;
1133+
/// it does so at a quarter of this number when its input holds about
1134+
/// one row per group. Aggregations of millions of groups per partition
1135+
/// run faster and with less memory. Moving rows into buckets has a
1136+
/// cost of its own, so aggregations that end at a few times this
1137+
/// number of groups, string keys in particular, can run a few percent
1138+
/// slower, and input that repeats its groups can use more memory.
11331139
/// Set to 0 to disable.
11341140
pub hash_aggregate_bucket_threshold: usize, default = 0
11351141

‎datafusion/physical-plan/src/aggregates/hash_stream.rs‎

Lines changed: 58 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -385,6 +385,31 @@ enum HandleInputResult {
385385
SwitchToSkipAggregation,
386386
}
387387

388+
/// A final table whose input is [`BARELY_REDUCING`] moves into buckets once
389+
/// it holds this share of the bucket threshold.
390+
///
391+
/// Moving a table into buckets aggregates its groups a second time. An input
392+
/// of about one row per group never earns that back unless the table is
393+
/// small compared to the input, and such an input gains nothing from a larger
394+
/// first table either.
395+
const EARLY_BUCKETS_DIVISOR: usize = 4;
396+
397+
/// Share of the rows seen so far that started a new group above which the
398+
/// input is taken to hold about one row per group, the same ratio as the
399+
/// default of `skip_partial_aggregation_probe_ratio_threshold`.
400+
const BARELY_REDUCING: f64 = 0.8;
401+
402+
/// Whether a final table of `groups` groups built from `rows` rows moves into
403+
/// buckets.
404+
///
405+
/// An input that repeats its groups keeps its table up to the full threshold:
406+
/// the table reduces that input, which buckets only do by compacting.
407+
fn starts_buckets(groups: usize, rows: usize, threshold: usize) -> bool {
408+
groups >= threshold
409+
|| (groups >= (threshold / EARLY_BUCKETS_DIVISOR).max(1)
410+
&& groups as f64 >= BARELY_REDUCING * rows as f64)
411+
}
412+
388413
/// Number of flushed groups whose hashes are kept to detect recurring groups.
389414
const FLUSH_SAMPLE_SIZE: usize = 1024;
390415

@@ -1128,7 +1153,11 @@ impl FinalHashAggregateStream {
11281153
// bucketing only starts from a table that has never spilled.
11291154
if let Some(bucketing) = &self.bucketing
11301155
&& !spilled
1131-
&& hash_table.building_group_count() >= bucketing.threshold()
1156+
&& starts_buckets(
1157+
hash_table.building_group_count(),
1158+
table_rows,
1159+
bucketing.threshold(),
1160+
)
11321161
{
11331162
let kept =
11341163
hash_table.building_group_count() as f64 / table_rows.max(1) as f64;
@@ -2040,13 +2069,39 @@ mod tests {
20402069
assert_eq!(splits, 1);
20412070
assert_eq!(spills, 0);
20422071

2043-
// A table that never reaches the threshold is left alone
2044-
let (rows, splits, _) = run_final_hash_aggregate(50_000, 3, 50_001, None).await?;
2072+
// A table that does not reach a quarter of the threshold is left alone
2073+
let (rows, splits, _) =
2074+
run_final_hash_aggregate(50_000, 3, 200_004, None).await?;
20452075
assert_eq!(rows, expected);
20462076
assert_eq!(splits, 0);
20472077
Ok(())
20482078
}
20492079

2080+
#[test]
2081+
fn starts_buckets_early_only_when_groups_do_not_repeat() {
2082+
// One row per group: a quarter of the threshold is enough
2083+
assert!(!starts_buckets(249, 249, 1_000));
2084+
assert!(starts_buckets(250, 250, 1_000));
2085+
// Groups repeat: only the full threshold
2086+
assert!(!starts_buckets(999, 10_000, 1_000));
2087+
assert!(starts_buckets(1_000, 10_000, 1_000));
2088+
// A threshold below the divisor
2089+
assert!(starts_buckets(1, 1, 2));
2090+
}
2091+
2092+
#[tokio::test]
2093+
async fn final_hash_aggregate_starts_buckets_early_for_unique_groups() -> Result<()> {
2094+
let (expected, _, _) = run_final_hash_aggregate(50_000, 1, 0, None).await?;
2095+
2096+
// Every group arrives once, so the table moves into buckets at a
2097+
// quarter of the threshold, which the 50,000 groups never reach.
2098+
// Buckets of ~780 groups are not split again.
2099+
let (rows, splits, _) = run_final_hash_aggregate(50_000, 1, 60_000, None).await?;
2100+
assert_eq!(rows, expected);
2101+
assert_eq!(splits, 1);
2102+
Ok(())
2103+
}
2104+
20502105
#[tokio::test]
20512106
async fn final_hash_aggregate_splits_large_buckets_again() -> Result<()> {
20522107
let (expected, _, _) = run_final_hash_aggregate(50_000, 2, 0, None).await?;

‎datafusion/sqllogictest/test_files/information_schema.slt‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -384,7 +384,7 @@ datafusion.execution.enable_migration_aggregate true Whether aggregation uses th
384384
datafusion.execution.enable_nlj_coordinated_fallback true Enables the memory-limited fallback for `NestedLoopJoinExec` join types that emit unmatched left rows in the final output (LEFT, LEFT SEMI, LEFT ANTI, LEFT MARK, FULL) when the right side has multiple partitions. This fallback coordinates per-chunk left state (visited bitmap and probe-thread counter) across all right-side partitions, which assumes every partition runs in the same process. Distributed engines that execute each output partition as an independent task (e.g. Ballista, datafusion-distributed) build a separate coordinator per task and poll only one partition, so the cross-partition counter never reaches zero and the fallback would stall. Such engines should set this to `false`: the coordinated fallback is then disabled for left-emitting multi-partition joins, which instead fail with a resource-exhaustion error under memory pressure rather than deadlocking. Single-partition and non-left-emitting joins are unaffected and always keep the fallback.
385385
datafusion.execution.enable_recursive_ctes true Should DataFusion support recursive CTEs
386386
datafusion.execution.enforce_batch_size_in_joins false Should DataFusion enforce batch size in joins or not. By default, DataFusion will not enforce batch size in joins. Enforcing batch size in joins can reduce memory usage when joining large tables with a highly-selective join filter, but is also slightly slower. Note: this option currently only applies to the symmetric hash join.
387-
datafusion.execution.hash_aggregate_bucket_threshold 0 (experimental) Number of groups above which a hash aggregation stops growing a single hash table, so that its tables stay small enough to be cache friendly. A partial aggregation then emits the state of its table and starts over, as long as the emitted groups do not come back. A final aggregation splits the groups seen so far and all further input into hash buckets, which are aggregated one after another and can be spilled and released independently. Set to 0 to disable.
387+
datafusion.execution.hash_aggregate_bucket_threshold 0 (experimental) Number of groups above which a hash aggregation stops growing a single hash table, so that its tables stay small enough to be cache friendly. A partial aggregation then emits the state of its table and starts over, as long as the emitted groups do not come back. A final aggregation splits the groups seen so far and all further input into hash buckets, which are aggregated one after another and can be spilled and released independently; it does so at a quarter of this number when its input holds about one row per group. Aggregations of millions of groups per partition run faster and with less memory. Moving rows into buckets has a cost of its own, so aggregations that end at a few times this number of groups, string keys in particular, can run a few percent slower, and input that repeats its groups can use more memory. Set to 0 to disable.
388388
datafusion.execution.hash_join_buffering_capacity 0 How many bytes to buffer in the probe side of hash joins while the build side is concurrently being built. Without this, hash joins will wait until the full materialization of the build side before polling the probe side. This is useful in scenarios where the query is not completely CPU bounded, allowing to do some early work concurrently and reducing the latency of the query. Note that when hash join buffering is enabled, the probe side will start eagerly polling data, not giving time for the producer side of dynamic filters to produce any meaningful predicate. Queries with dynamic filters might see performance degradation. Disabled by default, set to a number greater than 0 for enabling it.
389389
datafusion.execution.keep_partition_by_columns false Should DataFusion keep the columns used for partition_by in the output RecordBatches
390390
datafusion.execution.listing_table_factory_infer_partitions true Should a `ListingTable` created through the `ListingTableFactory` infer table partitions from Hive compliant directories. Defaults to true (partition columns are inferred and will be represented in the table schema).

‎docs/source/user-guide/configs.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -140,7 +140,7 @@ The following configuration settings are available:
140140
| datafusion.execution.enable_file_stream_work_stealing | true | When `true` (the default), DataFusion's built-in file scans dynamically rebalance files across partitions at query execution time: a partition that goes idle reads files (or byte-range morsels) originally assigned to a sibling partition, which keeps all partitions busy in a single process. Executors that depend on the plan-time partition assignment — such as Ballista and datafusion-distributed, which run each partition as an isolated task and never poll the siblings — should set this to `false` so each partition reads only its own file group and no runtime reassignment occurs. |
141141
| datafusion.execution.skip_partial_aggregation_probe_ratio_threshold | 0.8 | Aggregation ratio (number of distinct groups / number of input rows) threshold for skipping partial aggregation. If the value is greater then partial aggregation will skip aggregation for further input |
142142
| datafusion.execution.skip_partial_aggregation_probe_rows_threshold | 100000 | Number of input rows partial aggregation partition should process, before aggregation ratio check and trying to switch to skipping aggregation mode |
143-
| datafusion.execution.hash_aggregate_bucket_threshold | 0 | (experimental) Number of groups above which a hash aggregation stops growing a single hash table, so that its tables stay small enough to be cache friendly. A partial aggregation then emits the state of its table and starts over, as long as the emitted groups do not come back. A final aggregation splits the groups seen so far and all further input into hash buckets, which are aggregated one after another and can be spilled and released independently. Set to 0 to disable. |
143+
| datafusion.execution.hash_aggregate_bucket_threshold | 0 | (experimental) Number of groups above which a hash aggregation stops growing a single hash table, so that its tables stay small enough to be cache friendly. A partial aggregation then emits the state of its table and starts over, as long as the emitted groups do not come back. A final aggregation splits the groups seen so far and all further input into hash buckets, which are aggregated one after another and can be spilled and released independently; it does so at a quarter of this number when its input holds about one row per group. Aggregations of millions of groups per partition run faster and with less memory. Moving rows into buckets has a cost of its own, so aggregations that end at a few times this number of groups, string keys in particular, can run a few percent slower, and input that repeats its groups can use more memory. Set to 0 to disable. |
144144
| datafusion.execution.use_row_number_estimates_to_optimize_partitioning | false | Should DataFusion use row number estimates at the input to decide whether increasing parallelism is beneficial or not. By default, only exact row numbers (not estimates) are used for this decision. Setting this flag to `true` will likely produce better plans. if the source of statistics is accurate. We plan to make this the default in the future. |
145145
| datafusion.execution.enforce_batch_size_in_joins | false | Should DataFusion enforce batch size in joins or not. By default, DataFusion will not enforce batch size in joins. Enforcing batch size in joins can reduce memory usage when joining large tables with a highly-selective join filter, but is also slightly slower. Note: this option currently only applies to the symmetric hash join. |
146146
| datafusion.execution.objectstore_writer_buffer_size | 10485760 | Size (bytes) of data buffer DataFusion uses when writing output files. This affects the size of the data chunks that are uploaded to remote object stores (e.g. AWS S3). If very large (>= 100 GiB) output files are being written, it may be necessary to increase this size to avoid errors from the remote end point. |

0 commit comments

Comments
 (0)