You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/07/31 21:16:23 UTC
(datafusion) branch gh-readonly-queue/main/pr-24032-285559e44f4ddd6303e3d6e5c873f9e1075fdada created (now 7547280712)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-24032-285559e44f4ddd6303e3d6e5c873f9e1075fdada
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 7547280712 bench: extend BoundedWindowAggExec many-partitions benchmark (#24032)
This branch includes the following new commits:
new 7547280712 bench: extend BoundedWindowAggExec many-partitions benchmark (#24032)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: bench: extend BoundedWindowAggExec many-partitions benchmark (#24032)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-24032-285559e44f4ddd6303e3d6e5c873f9e1075fdada
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 754728071255f01590ffdbf52079af02ca8b977e
Author: Neil Conway <ne...@gmail.com>
AuthorDate: Fri Jul 31 17:16:01 2026 -0400
bench: extend BoundedWindowAggExec many-partitions benchmark (#24032)
## Which issue does this PR close?
- Related to #23982
## Rationale for this change
The existing cases measure COUNT over a RANGE frame on round-robin
partition keys: Linear mode over 100 and 10000 partitions, plus
Sorted-mode over the 10000 partitions. Each batch contains rows for most
of the partition set, and every case exercises a single window
expression over one frame type.
Add Linear-mode shapes that stress the operator's per-partition state
differently:
- linear, 32768 partitions, sparse: each batch introduces a block of
2048 previously unseen keys (4 rows each) and never revisits them, so
the live partition set grows for the whole run while each batch touches
only its newest partitions.
- linear, 10000 partitions, ROWS frame, round-robin partition layout.
- linear, 10000 partitions, two window expressions, round-robin
partition layout.
## What changes are included in this PR?
See above.
## Are these changes tested?
Tested manually.
## Are there any user-facing changes?
No.
---
datafusion/physical-plan/benches/bounded_window.rs | 229 +++++++++++++++------
1 file changed, 163 insertions(+), 66 deletions(-)
diff --git a/datafusion/physical-plan/benches/bounded_window.rs b/datafusion/physical-plan/benches/bounded_window.rs
index f704a86287..56e195afbd 100644
--- a/datafusion/physical-plan/benches/bounded_window.rs
+++ b/datafusion/physical-plan/benches/bounded_window.rs
@@ -15,16 +15,27 @@
// specific language governing permissions and limitations
// under the License.
-//! Benchmark for `BoundedWindowAggExec` with many partitions.
+//! Benchmarks for `BoundedWindowAggExec` with many partitions.
//!
//! The streaming window operator keeps per-partition state keyed by
-//! `PartitionKey` (`Vec<ScalarValue>`) and probes it for every buffered
-//! partition on every batch, so its performance is sensitive to both the
-//! number of live partitions and the cost of hashing the keys. `Linear`
-//! mode (input sorted by the ORDER BY column but not by the partition
-//! columns) keeps every partition live until the input is exhausted and is
-//! the stress case; `Sorted` mode prunes finished partitions eagerly and
-//! serves as the control.
+//! `PartitionKey` (`Vec<ScalarValue>`) and, in `Linear` mode (input sorted
+//! by the ORDER BY column but not by the partition columns), visits every
+//! live partition on every batch while never retiring partitions until the
+//! input is exhausted. The cases here stress that path in different ways:
+//!
+//! - `linear N partitions`: dense round-robin keys -- every partition
+//! receives rows in every batch, so per-visit fixed costs dominate.
+//! - `linear sparse N partitions`: keys are clustered in time, so each
+//! batch touches only a small, fresh subset of keys while the set of live
+//! partitions keeps growing -- per-batch work on quiet partitions
+//! dominates.
+//! - `linear rows N partitions`: the dense layout with a ROWS frame, whose
+//! results can only be finalized as more rows of the same partition
+//! arrive.
+//! - `linear multi N partitions`: two window expressions over the dense
+//! layout, doubling the per-partition evaluation sweeps.
+//! - `sorted N partitions`: control; input sorted by partition key, so
+//! finished partitions are pruned eagerly and the state maps stay small.
use std::sync::Arc;
@@ -38,6 +49,7 @@ use datafusion_expr::{
WindowFrame, WindowFrameBound, WindowFrameUnits, WindowFunctionDefinition,
};
use datafusion_functions_aggregate::count::count_udaf;
+use datafusion_functions_aggregate::sum::sum_udaf;
use datafusion_physical_expr::expressions::col;
use datafusion_physical_expr::{LexOrdering, PhysicalSortExpr};
use datafusion_physical_plan::test::TestMemoryExec;
@@ -46,6 +58,10 @@ use datafusion_physical_plan::{ExecutionPlan, InputOrderMode, collect};
const BATCH_SIZE: usize = 8192;
const N_BATCHES: usize = 16;
+/// Distinct partition keys per batch in the sparse layout. Each batch
+/// introduces this many previously-unseen keys, so the total partition count
+/// is `N_BATCHES * SPARSE_KEYS_PER_BATCH`.
+const SPARSE_KEYS_PER_BATCH: usize = 2048;
fn schema() -> SchemaRef {
Arc::new(Schema::new(vec![
@@ -54,24 +70,14 @@ fn schema() -> SchemaRef {
]))
}
-/// Batches with `ts` ascending across the whole input. When
-/// `partitions_sorted` is false, partition keys round-robin over
-/// `n_partitions` (the `Linear` layout); when true, the input is laid out
-/// partition-by-partition (the `Sorted` layout).
-fn make_batches(n_partitions: usize, partitions_sorted: bool) -> Vec<RecordBatch> {
- let total = BATCH_SIZE * N_BATCHES;
- let rows_per_partition = total / n_partitions;
+/// Batches with `ts` ascending across the whole input and partition keys
+/// chosen by `pk_of_row`.
+fn make_batches(pk_of_row: impl Fn(usize) -> u64) -> Vec<RecordBatch> {
(0..N_BATCHES)
.map(|b| {
let start = b * BATCH_SIZE;
let pk: UInt64Array = (start..start + BATCH_SIZE)
- .map(|i| {
- if partitions_sorted {
- Some((i / rows_per_partition) as u64)
- } else {
- Some((i % n_partitions) as u64)
- }
- })
+ .map(|i| Some(pk_of_row(i)))
.collect();
let ts: UInt64Array = (start..start + BATCH_SIZE)
.map(|i| Some(i as u64))
@@ -81,6 +87,29 @@ fn make_batches(n_partitions: usize, partitions_sorted: bool) -> Vec<RecordBatch
.collect()
}
+/// Round-robin over `n_partitions`: every partition receives rows in every
+/// batch (when `n_partitions <= BATCH_SIZE`).
+fn dense_batches(n_partitions: usize) -> Vec<RecordBatch> {
+ make_batches(move |i| (i % n_partitions) as u64)
+}
+
+/// Keys clustered in time: batch `b` only contains keys in
+/// `[b * SPARSE_KEYS_PER_BATCH, (b + 1) * SPARSE_KEYS_PER_BATCH)`, cycled so
+/// that consecutive rows belong to different partitions. Previously-seen
+/// keys never recur, but `Linear` mode cannot know that, so the live
+/// partition set grows for the whole run.
+fn sparse_batches() -> Vec<RecordBatch> {
+ make_batches(|i| {
+ ((i / BATCH_SIZE) * SPARSE_KEYS_PER_BATCH + (i % SPARSE_KEYS_PER_BATCH)) as u64
+ })
+}
+
+/// Input laid out partition-by-partition (the `Sorted` layout).
+fn sorted_batches(n_partitions: usize) -> Vec<RecordBatch> {
+ let rows_per_partition = BATCH_SIZE * N_BATCHES / n_partitions;
+ make_batches(move |i| (i / rows_per_partition) as u64)
+}
+
fn sort_expr(name: &str) -> PhysicalSortExpr {
PhysicalSortExpr {
expr: col(name, &schema()).unwrap(),
@@ -88,12 +117,32 @@ fn sort_expr(name: &str) -> PhysicalSortExpr {
}
}
-/// `COUNT(ts) OVER (PARTITION BY pk ORDER BY ts
-/// RANGE BETWEEN CURRENT ROW AND 10 FOLLOWING)`
+/// `RANGE BETWEEN CURRENT ROW AND 10 FOLLOWING`
+fn range_frame() -> WindowFrame {
+ WindowFrame::new_bounds(
+ WindowFrameUnits::Range,
+ WindowFrameBound::CurrentRow,
+ WindowFrameBound::Following(ScalarValue::UInt64(Some(10))),
+ )
+}
+
+/// `ROWS BETWEEN CURRENT ROW AND 2 FOLLOWING`
+fn rows_frame() -> WindowFrame {
+ WindowFrame::new_bounds(
+ WindowFrameUnits::Rows,
+ WindowFrameBound::CurrentRow,
+ WindowFrameBound::Following(ScalarValue::UInt64(Some(2))),
+ )
+}
+
+/// `<agg>(ts) OVER (PARTITION BY pk ORDER BY ts <window_frame>)` for each
+/// aggregate in `aggregates`.
fn window_exec(
batches: Vec<RecordBatch>,
mode: InputOrderMode,
input_ordering: Vec<PhysicalSortExpr>,
+ window_frame: &WindowFrame,
+ aggregates: &[(WindowFunctionDefinition, &str)],
) -> Arc<dyn ExecutionPlan> {
let schema = schema();
let source = TestMemoryExec::try_new(&[batches], Arc::clone(&schema), None)
@@ -107,42 +156,48 @@ fn window_exec(
expr: col("ts", &schema).unwrap(),
options: Default::default(),
}];
- let window_frame = WindowFrame::new_bounds(
- WindowFrameUnits::Range,
- WindowFrameBound::CurrentRow,
- WindowFrameBound::Following(ScalarValue::UInt64(Some(10))),
- );
- let window_expr = create_window_expr(
- &WindowFunctionDefinition::AggregateUDF(count_udaf()),
- "count".to_string(),
- &args,
- &partitionby_exprs,
- &orderby_exprs,
- Arc::new(window_frame),
- input.schema(),
- false,
- false,
- None,
- )
- .expect("window expr");
+ let window_expr = aggregates
+ .iter()
+ .map(|(fun, name)| {
+ create_window_expr(
+ fun,
+ name.to_string(),
+ &args,
+ &partitionby_exprs,
+ &orderby_exprs,
+ Arc::new(window_frame.clone()),
+ input.schema(),
+ false,
+ false,
+ None,
+ )
+ .expect("window expr")
+ })
+ .collect::<Vec<_>>();
Arc::new(
- BoundedWindowAggExec::try_new(vec![window_expr], input, mode, true)
+ BoundedWindowAggExec::try_new(window_expr, input, mode, true)
.expect("bounded window exec"),
)
}
+fn count() -> (WindowFunctionDefinition, &'static str) {
+ (
+ WindowFunctionDefinition::AggregateUDF(count_udaf()),
+ "count",
+ )
+}
+
+fn sum() -> (WindowFunctionDefinition, &'static str) {
+ (WindowFunctionDefinition::AggregateUDF(sum_udaf()), "sum")
+}
+
fn bounded_window_benchmark(c: &mut Criterion) {
let rt = tokio::runtime::Runtime::new().unwrap();
let mut group = c.benchmark_group("bounded_window_partitions");
group.sample_size(10);
- for n_partitions in [100, 10_000] {
- let plan = window_exec(
- make_batches(n_partitions, false),
- InputOrderMode::Linear,
- vec![sort_expr("ts")],
- );
- group.bench_function(format!("linear {n_partitions} partitions"), |b| {
+ let mut run_case = |name: String, plan: Arc<dyn ExecutionPlan>| {
+ group.bench_function(name, |b| {
b.iter(|| {
let task_ctx = Arc::new(TaskContext::default());
let batches = rt
@@ -154,27 +209,69 @@ fn bounded_window_benchmark(c: &mut Criterion) {
);
})
});
+ };
+
+ for n_partitions in [100, 10_000] {
+ run_case(
+ format!("linear {n_partitions} partitions"),
+ window_exec(
+ dense_batches(n_partitions),
+ InputOrderMode::Linear,
+ vec![sort_expr("ts")],
+ &range_frame(),
+ &[count()],
+ ),
+ );
}
+ run_case(
+ format!(
+ "linear sparse {} partitions",
+ N_BATCHES * SPARSE_KEYS_PER_BATCH
+ ),
+ window_exec(
+ sparse_batches(),
+ InputOrderMode::Linear,
+ vec![sort_expr("ts")],
+ &range_frame(),
+ &[count()],
+ ),
+ );
+
+ run_case(
+ "linear rows 10000 partitions".to_string(),
+ window_exec(
+ dense_batches(10_000),
+ InputOrderMode::Linear,
+ vec![sort_expr("ts")],
+ &rows_frame(),
+ &[count()],
+ ),
+ );
+
+ run_case(
+ "linear multi 10000 partitions".to_string(),
+ window_exec(
+ dense_batches(10_000),
+ InputOrderMode::Linear,
+ vec![sort_expr("ts")],
+ &range_frame(),
+ &[count(), sum()],
+ ),
+ );
+
// Control: the same query over partition-sorted input, where finished
// partitions are pruned eagerly and the state maps stay small.
- let plan = window_exec(
- make_batches(10_000, true),
- InputOrderMode::Sorted,
- vec![sort_expr("pk"), sort_expr("ts")],
+ run_case(
+ "sorted 10000 partitions".to_string(),
+ window_exec(
+ sorted_batches(10_000),
+ InputOrderMode::Sorted,
+ vec![sort_expr("pk"), sort_expr("ts")],
+ &range_frame(),
+ &[count()],
+ ),
);
- group.bench_function("sorted 10000 partitions", |b| {
- b.iter(|| {
- let task_ctx = Arc::new(TaskContext::default());
- let batches = rt
- .block_on(collect(Arc::clone(&plan), task_ctx))
- .expect("execution");
- assert_eq!(
- batches.iter().map(|b| b.num_rows()).sum::<usize>(),
- BATCH_SIZE * N_BATCHES
- );
- })
- });
group.finish();
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org