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/06/29 02:23:17 UTC
(datafusion) branch main updated: perf: share encoder/reservation across PartitionedTopKExec partition … (#23096)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new cae5f2ebf6 perf: share encoder/reservation across PartitionedTopKExec partition … (#23096)
cae5f2ebf6 is described below
commit cae5f2ebf64c1343b1d295f45c07b6b7bf68d2a2
Author: Subham Singhal <Su...@users.noreply.github.com>
AuthorDate: Mon Jun 29 07:41:23 2026 +0530
perf: share encoder/reservation across PartitionedTopKExec partition … (#23096)
## Which issue does this PR close?
Follow-up to #21479 (`PartitionedTopKExec` for `ROW_NUMBER ... PARTITION
BY ... LIMIT N`) toward closing #6899.
## Rationale for this change
`PartitionedTopKExec` today maintains a `HashMap<OwnedRow, TopK>` — one
full `TopK` per distinct partition key. Each `TopK` carries its own
`RowConverter`, `MemoryReservation` registered with the runtime pool,
`TopKMetrics`, and scratch `Rows` buffer. With high partition
cardinality every partition seen for the first time pays:
- `RowConverter::new` (parses `SortField` list, allocates per-encoder
state)
- `MemoryConsumer::register` with the pool (involves a global lock)
- per-counter `TopKMetrics` setup
- scratch `Rows::empty_rows` allocation
For the h2o window-TopN sweep on a 10M-row CSV (`id3 % N` partition
cardinality), this shows up as a regression at ≥10K partitions —
`PartitionedTopKExec` is slower than the unpartitioned `SortExec`
baseline that it's meant to replace.
## What changes are included in this PR?
Adds a `PartitionedTopK` sibling type to `topk/mod.rs` that holds the
shared encoder/reservation/metrics state once at the operator level and
a `HashMap<OwnedRow, TopKHeap>` of cheap per-partition heap state.
`PartitionedTopKExec` switches from `HashMap<OwnedRow, TopK>` to one
`PartitionedTopK`.
### Bench results
#### Today's default (main, flag-off) vs this PR (flag-on)
| Partitions | main flag-off | this PR flag-on | Delta |
|-----------:|--------------:|----------------:|-------|
| 100 | 282 ms | 105 ms | **2.7x faster** |
| 1,000 | 247 ms | 110 ms | **2.2x faster** |
| 10,000 | 250 ms | 137 ms | **1.8x faster** |
| 100,000 | 222 ms | 320 ms | 1.4x slower |
h2o `id3 % N` sweep, 10M-row CSV, 3 iterations per query, release build,
`enable_window_topn=true` on both sides:
| Partitions | `main` | this PR | Speedup |
|-----------:|-------:|--------:|--------:|
| 100 | 110 ms | 105 ms | ~1.0× |
| 1,000 | 117 ms | 110 ms | ~1.0× |
| 10,000 | 640 ms | 137 ms | **4.7×** |
| 100,000 | 4,327 ms | 320 ms | **13.5×** |
10K is the inflection point: on `main` it's a regression vs the sort
baseline (640 ms vs 234 ms); after this PR it's a win (137 ms vs 234 ms
— 1.7× faster than sort). 100K nearly catches up to the sort baseline
(320 ms vs 238 ms).
`enable_window_topn` default stays `false` per the #21479 discussion —
100K+ remains slower than sort on average, so this PR doesn't motivate
flipping the default. It's the prerequisite for further optimizations
that would attack the residual 100K+ cliff.
## Are these changes tested?
Yes
## Are there any user-facing changes?
No public API changes.
---
benchmarks/queries/h2o/window.sql | 31 ++
.../physical-plan/src/sorts/partitioned_topk.rs | 154 ++----
datafusion/physical-plan/src/topk/mod.rs | 539 ++++++++++++++++++++-
3 files changed, 600 insertions(+), 124 deletions(-)
diff --git a/benchmarks/queries/h2o/window.sql b/benchmarks/queries/h2o/window.sql
index fa16a3de32..346a8e4713 100644
--- a/benchmarks/queries/h2o/window.sql
+++ b/benchmarks/queries/h2o/window.sql
@@ -117,3 +117,34 @@ SELECT id2, largest2_v2 FROM (
ROW_NUMBER() OVER (PARTITION BY id2 ORDER BY v2 DESC) AS order_v2
FROM large WHERE v2 IS NOT NULL
) sub_query WHERE order_v2 <= 2;
+
+-- Window Top-N partition cardinality sweep (id3 % N gives N distinct partitions).
+-- These exercise PartitionedTopKExec across cardinalities to validate it stays
+-- competitive with the SortExec+Filter baseline as partition count grows.
+-- Window Top-N: 100 partitions
+SELECT pk, largest2_v2 FROM (
+ SELECT id3 % 100 AS pk, v2 AS largest2_v2,
+ ROW_NUMBER() OVER (PARTITION BY id3 % 100 ORDER BY v2 DESC) AS order_v2
+ FROM large WHERE v2 IS NOT NULL
+) sub_query WHERE order_v2 <= 2;
+
+-- Window Top-N: 1,000 partitions
+SELECT pk, largest2_v2 FROM (
+ SELECT id3 % 1000 AS pk, v2 AS largest2_v2,
+ ROW_NUMBER() OVER (PARTITION BY id3 % 1000 ORDER BY v2 DESC) AS order_v2
+ FROM large WHERE v2 IS NOT NULL
+) sub_query WHERE order_v2 <= 2;
+
+-- Window Top-N: 10,000 partitions
+SELECT pk, largest2_v2 FROM (
+ SELECT id3 % 10000 AS pk, v2 AS largest2_v2,
+ ROW_NUMBER() OVER (PARTITION BY id3 % 10000 ORDER BY v2 DESC) AS order_v2
+ FROM large WHERE v2 IS NOT NULL
+) sub_query WHERE order_v2 <= 2;
+
+-- Window Top-N: 100,000 partitions
+SELECT pk, largest2_v2 FROM (
+ SELECT id3 % 100000 AS pk, v2 AS largest2_v2,
+ ROW_NUMBER() OVER (PARTITION BY id3 % 100000 ORDER BY v2 DESC) AS order_v2
+ FROM large WHERE v2 IS NOT NULL
+) sub_query WHERE order_v2 <= 2;
diff --git a/datafusion/physical-plan/src/sorts/partitioned_topk.rs b/datafusion/physical-plan/src/sorts/partitioned_topk.rs
index fe876eeddf..1040abcb75 100644
--- a/datafusion/physical-plan/src/sorts/partitioned_topk.rs
+++ b/datafusion/physical-plan/src/sorts/partitioned_topk.rs
@@ -24,29 +24,26 @@
//! ```
//!
//! Instead of sorting the entire dataset, this operator maintains a
-//! [`TopK`] heap per partition (reusing the existing TopK implementation)
+//! [`TopK`](crate::topk::TopK) heap per partition (reusing the existing TopK implementation)
//! and emits only the top-K rows per partition in sorted order
//! `(partition_keys, order_keys)`.
use std::fmt::{self, Formatter};
use std::sync::Arc;
-use arrow::array::{RecordBatch, UInt32Array};
-use arrow::compute::{BatchCoalescer, take_record_batch};
use arrow::datatypes::SchemaRef;
-use arrow::row::{OwnedRow, RowConverter};
-use datafusion_common::{HashMap, Result};
+use arrow::row::SortField;
+use datafusion_common::Result;
use datafusion_execution::TaskContext;
+use datafusion_execution::runtime_env::RuntimeEnv;
use datafusion_physical_expr::PhysicalExpr;
-use datafusion_physical_expr::expressions::{DynamicFilterPhysicalExpr, lit};
use datafusion_physical_expr_common::sort_expr::LexOrdering;
use futures::StreamExt;
use futures::TryStreamExt;
-use parking_lot::RwLock;
use crate::execution_plan::{Boundedness, EmissionType};
use crate::metrics::ExecutionPlanMetricsSet;
-use crate::topk::{TopK, TopKDynamicFilters, build_sort_fields};
+use crate::topk::{PartitionedTopK, build_sort_fields};
use crate::{
DisplayAs, DisplayFormatType, Distribution, ExecutionPlan, ExecutionPlanProperties,
PlanProperties, SendableRecordBatchStream, stream::RecordBatchStreamAdapter,
@@ -93,7 +90,7 @@ use crate::{
/// ```
///
/// Instead of sorting the entire dataset, this operator reads unsorted input,
-/// maintains a [`TopK`] heap per distinct partition key, and emits only the
+/// maintains a [`TopK`](crate::topk::TopK) heap per distinct partition key, and emits only the
/// top-K rows per partition in sorted order `(partition_keys, order_keys)`.
///
/// Cost: O(N log K) time instead of O(N log N), and O(K × P × row_size)
@@ -342,8 +339,6 @@ impl ExecutionPlan for PartitionedTopKExec {
let partition_sort_fields =
build_sort_fields(&self.expr[..self.partition_prefix_len], &schema)?;
- let partition_converter = RowConverter::new(partition_sort_fields)?;
-
let partition_exprs: Vec<Arc<dyn PhysicalExpr>> = self.expr
[..self.partition_prefix_len]
.iter()
@@ -359,10 +354,11 @@ impl ExecutionPlan for PartitionedTopKExec {
let stream = futures::stream::once(async move {
do_partitioned_topk(
+ partition,
input,
schema,
- partition_converter,
partition_exprs,
+ partition_sort_fields,
order_expr,
fetch,
batch_size,
@@ -380,36 +376,20 @@ impl ExecutionPlan for PartitionedTopKExec {
}
}
-/// Create a no-op [`TopKDynamicFilters`] for a per-partition [`TopK`].
-///
-/// In normal `SortExec` top-K mode, dynamic filters push predicates down to
-/// the data source (e.g., telling Parquet to skip rows worse than the current
-/// K-th best). For per-partition heaps the data is already in memory and split
-/// by partition key, so there is no data source to push filters to. We pass
-/// `lit(true)` (accept everything) so the filter never rejects any row.
-fn create_noop_dynamic_filter() -> Arc<RwLock<TopKDynamicFilters>> {
- Arc::new(RwLock::new(TopKDynamicFilters::new(Arc::new(
- DynamicFilterPhysicalExpr::new(vec![], lit(true)),
- ))))
-}
-
-/// Read all input, split batches by partition key, feed each sub-batch
-/// to a per-partition [`TopK`], then emit results in partition-key order.
+/// Read all input, feed each batch into a [`PartitionedTopK`] (which
+/// maintains one heap per distinct partition key), then emit results
+/// ordered by `(partition_keys, order_keys)`.
///
/// # Phases
///
-/// 1. **Accumulation** — For each input batch:
-/// - Evaluate partition key expressions to get partition column arrays
-/// - Convert partition columns to binary [`arrow::row::Row`] format
-/// - Group row indices by partition key
-/// - Extract sub-batches via [`take_record_batch`] and insert into
-/// the partition's [`TopK`] heap
+/// 1. **Accumulation** — forward each input `RecordBatch` to
+/// [`PartitionedTopK::insert_batch`], which demultiplexes rows by
+/// partition key and dispatches them into the per-key heap. The
+/// `RowConverter` and `MemoryReservation` are shared across all
+/// partitions for this operator instance.
///
-/// 2. **Emission** — After all input is consumed:
-/// - Sort partition keys so output is ordered by partition key
-/// - For each partition in sorted order, call [`TopK::emit`] to get
-/// rows sorted by order-by key
-/// - Return all batches as a single stream
+/// 2. **Emission** — [`PartitionedTopK::emit`] drains all heaps in
+/// sorted partition-key order, returning a coalesced batch stream.
///
/// # Cost
///
@@ -417,99 +397,33 @@ fn create_noop_dynamic_filter() -> Arc<RwLock<TopKDynamicFilters>> {
/// - Memory: O(K × P × row_size) where P = number of distinct partitions
#[expect(clippy::too_many_arguments)]
async fn do_partitioned_topk(
+ partition_id: usize,
mut input: SendableRecordBatchStream,
schema: SchemaRef,
- partition_converter: RowConverter,
partition_exprs: Vec<Arc<dyn PhysicalExpr>>,
+ partition_sort_fields: Vec<SortField>,
order_expr: LexOrdering,
fetch: usize,
batch_size: usize,
- runtime: Arc<datafusion_execution::runtime_env::RuntimeEnv>,
+ runtime: Arc<RuntimeEnv>,
metrics_set: ExecutionPlanMetricsSet,
) -> Result<SendableRecordBatchStream> {
- let mut partitions: HashMap<OwnedRow, TopK> = HashMap::new();
- let mut partition_counter: usize = 0;
-
- // Macro-like helper: create a new TopK for a partition
- macro_rules! new_topk {
- () => {{
- let id = partition_counter;
- partition_counter += 1;
- TopK::try_new(
- id,
- Arc::clone(&schema),
- vec![],
- order_expr.clone(),
- fetch,
- batch_size,
- Arc::clone(&runtime),
- &metrics_set,
- create_noop_dynamic_filter(),
- )
- }};
- }
+ let mut state = PartitionedTopK::try_new(
+ partition_id,
+ schema,
+ partition_exprs,
+ partition_sort_fields,
+ order_expr,
+ fetch,
+ batch_size,
+ &runtime,
+ &metrics_set,
+ )?;
- // ---------- Accumulation phase ----------
while let Some(batch) = input.next().await {
- let batch = batch?;
- let num_rows = batch.num_rows();
- if num_rows == 0 {
- continue;
- }
-
- // Evaluate partition key columns
- let pk_arrays: Vec<_> = partition_exprs
- .iter()
- .map(|e| e.evaluate(&batch).and_then(|v| v.into_array(num_rows)))
- .collect::<Result<Vec<_>>>()?;
-
- let pk_rows = partition_converter.convert_columns(&pk_arrays)?;
-
- // Group row indices by partition key
- let mut groups: HashMap<OwnedRow, Vec<u32>> = HashMap::new();
- for row_idx in 0..num_rows {
- let pk = pk_rows.row(row_idx).owned();
- groups.entry(pk).or_default().push(row_idx as u32);
- }
-
- // For each partition group, create a sub-batch and feed to TopK
- for (pk, indices) in groups {
- if !partitions.contains_key(&pk) {
- partitions.insert(pk.clone(), new_topk!()?);
- }
- let topk = partitions.get_mut(&pk).unwrap();
- let indices_array = UInt32Array::from(indices);
- let sub_batch = take_record_batch(&batch, &indices_array)?;
- topk.insert_batch(sub_batch)?;
- }
+ state.insert_batch(&batch?)?;
}
- // Release the input pipeline now that accumulation is complete.
drop(input);
- // ---------- Emit phase ----------
- // Sort partition keys so output is ordered by (partition_keys, order_keys).
- let mut sorted_pks: Vec<OwnedRow> = partitions.keys().cloned().collect();
- sorted_pks.sort();
-
- let mut coalescer = BatchCoalescer::new(Arc::clone(&schema), batch_size);
-
- for pk in sorted_pks {
- if let Some(topk) = partitions.remove(&pk) {
- // TopK::emit() returns a stream of sorted batches
- let mut stream = topk.emit()?;
- while let Some(batch) = stream.next().await {
- coalescer.push_batch(batch?)?;
- }
- }
- }
- coalescer.finish_buffered_batch()?;
- let mut output_batches: Vec<RecordBatch> = Vec::new();
- while let Some(batch) = coalescer.next_completed_batch() {
- output_batches.push(batch);
- }
-
- Ok(Box::pin(RecordBatchStreamAdapter::new(
- schema,
- futures::stream::iter(output_batches.into_iter().map(Ok)),
- )))
+ state.emit()
}
diff --git a/datafusion/physical-plan/src/topk/mod.rs b/datafusion/physical-plan/src/topk/mod.rs
index 050732a380..ee8675d718 100644
--- a/datafusion/physical-plan/src/topk/mod.rs
+++ b/datafusion/physical-plan/src/topk/mod.rs
@@ -19,8 +19,11 @@
use arrow::{
array::{Array, AsArray},
- compute::{FilterBuilder, interleave_record_batch, prep_null_mask_filter},
- row::{RowConverter, Rows, SortField},
+ compute::{
+ BatchCoalescer, FilterBuilder, interleave_record_batch, prep_null_mask_filter,
+ take_record_batch,
+ },
+ row::{OwnedRow, RowConverter, Rows, SortField},
};
use datafusion_expr::{ColumnarValue, Operator};
use std::mem::size_of;
@@ -34,7 +37,7 @@ use super::metrics::{
use crate::spill::get_record_batch_memory_size;
use crate::{SendableRecordBatchStream, stream::RecordBatchStreamAdapter};
-use arrow::array::{ArrayRef, RecordBatch};
+use arrow::array::{ArrayRef, RecordBatch, UInt32Array};
use arrow::datatypes::SchemaRef;
use datafusion_common::{
HashMap, Result, ScalarValue, internal_datafusion_err, internal_err,
@@ -938,7 +941,7 @@ impl TopKHeap {
/// Returns the values stored in this heap, from values low to
/// high, as a single [`RecordBatch`], and a sorted vec of the
/// current heap's contents
- pub fn emit_with_state(&mut self) -> Result<(Option<RecordBatch>, Vec<TopKRow>)> {
+ fn emit_with_state(&mut self) -> Result<(Option<RecordBatch>, Vec<TopKRow>)> {
// generate sorted rows
let topk_rows = std::mem::take(&mut self.inner).into_sorted_vec();
@@ -1199,6 +1202,218 @@ impl RecordBatchStore {
}
}
+/// Top-K-per-partition operator state.
+///
+/// Sibling to [`TopK`]. Where `TopK` maintains a single global heap,
+/// `PartitionedTopK` maintains one [`TopKHeap`] per distinct partition
+/// key while sharing a single [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] across all partitions.
+///
+/// This sharing is the point of the type: with N distinct partition
+/// keys, a naive `HashMap<_, TopK>` pays N × constant overhead for
+/// `RowConverter::new`, `MemoryConsumer::register`, and metric
+/// counter setup. `PartitionedTopK` pays it once.
+pub(crate) struct PartitionedTopK {
+ schema: SchemaRef,
+ metrics: TopKMetrics,
+ reservation: MemoryReservation,
+ /// ORDER BY expressions (excludes PARTITION BY).
+ expr: LexOrdering,
+ /// Encoder for ORDER BY columns. Reused across partitions.
+ row_converter: RowConverter,
+ /// Scratch row buffer reused across `insert_batch` calls.
+ scratch_rows: Rows,
+ /// PARTITION BY expressions.
+ partition_exprs: Vec<Arc<dyn PhysicalExpr>>,
+ /// Encoder for the partition key.
+ partition_converter: RowConverter,
+ /// One heap per distinct partition key seen so far.
+ heaps: HashMap<OwnedRow, TopKHeap>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopK {
+ #[expect(clippy::too_many_arguments)]
+ pub(crate) fn try_new(
+ partition_id: usize,
+ schema: SchemaRef,
+ partition_exprs: Vec<Arc<dyn PhysicalExpr>>,
+ partition_sort_fields: Vec<SortField>,
+ order_expr: LexOrdering,
+ k: usize,
+ batch_size: usize,
+ runtime: &Arc<RuntimeEnv>,
+ metrics: &ExecutionPlanMetricsSet,
+ ) -> Result<Self> {
+ assert!(k > 0, "PartitionedTopK requires k > 0");
+ let reservation = MemoryConsumer::new(format!("PartitionedTopK[{partition_id}]"))
+ .register(&runtime.memory_pool);
+
+ let order_sort_fields = build_sort_fields(&order_expr, &schema)?;
+ let row_converter = RowConverter::new(order_sort_fields)?;
+ let scratch_rows =
+ row_converter.empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ let partition_converter = RowConverter::new(partition_sort_fields)?;
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ heaps: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Demultiplex `batch` rows by partition key, encode the ORDER BY
+ /// columns once for the whole batch, and feed each partition's
+ /// rows into its dedicated [`TopKHeap`].
+ pub(crate) fn insert_batch(&mut self, batch: &RecordBatch) -> Result<()> {
+ let baseline = self.metrics.baseline.clone();
+ let _timer = baseline.elapsed_compute().timer();
+
+ let num_rows = batch.num_rows();
+ if num_rows == 0 {
+ return Ok(());
+ }
+
+ // 1. Evaluate + encode partition columns.
+ let pk_arrays: Vec<ArrayRef> = self
+ .partition_exprs
+ .iter()
+ .map(|e| e.evaluate(batch).and_then(|v| v.into_array(num_rows)))
+ .collect::<Result<_>>()?;
+ let pk_rows = self.partition_converter.convert_columns(&pk_arrays)?;
+
+ // 2. Demultiplex row indices by partition key (per-batch).
+ let mut groups: HashMap<OwnedRow, Vec<u32>> = HashMap::new();
+ for i in 0..num_rows {
+ groups
+ .entry(pk_rows.row(i).owned())
+ .or_default()
+ .push(i as u32);
+ }
+
+ // 3. Evaluate ORDER BY columns on the full batch and encode ONCE.
+ let ob_arrays: Vec<ArrayRef> = self
+ .expr
+ .iter()
+ .map(|e| e.expr.evaluate(batch).and_then(|v| v.into_array(num_rows)))
+ .collect::<Result<_>>()?;
+ self.scratch_rows.clear();
+ self.row_converter
+ .append(&mut self.scratch_rows, &ob_arrays)?;
+
+ // 4. Per-partition: take the sub-batch, walk indices, dispatch
+ // qualifying rows into the partition's heap.
+ let k = self.k;
+ let mut replacements: usize = 0;
+ for (pk, indices) in groups {
+ let heap = self.heaps.entry(pk).or_insert_with(|| TopKHeap::new(k));
+
+ // Once a heap is full, most rows at high partition cardinality
+ // are rejected. Skip the gather + batch registration entirely
+ // when nothing in this partition group can improve the heap.
+ let any_qualify = indices.iter().any(|&orig_idx| {
+ let bytes = self.scratch_rows.row(orig_idx as usize);
+ match heap.max() {
+ Some(max_row) => bytes.as_ref() < max_row.row(),
+ None => true,
+ }
+ });
+ if !any_qualify {
+ continue;
+ }
+
+ let indices_arr = UInt32Array::from(indices);
+ let sub_batch = take_record_batch(batch, &indices_arr)?;
+ let mut entry = heap.register_batch(sub_batch);
+
+ for (sub_idx, &orig_idx) in indices_arr.values().iter().enumerate() {
+ let row = self.scratch_rows.row(orig_idx as usize);
+ match heap.max() {
+ Some(max_row) if row.as_ref() >= max_row.row() => {}
+ None | Some(_) => {
+ heap.add(&mut entry, row, sub_idx);
+ replacements += 1;
+ }
+ }
+ }
+
+ heap.insert_batch_entry(entry);
+ heap.maybe_compact()?;
+ }
+
+ if replacements > 0 {
+ self.metrics.row_replacements.add(replacements);
+ }
+ self.reservation.try_resize(self.size())?;
+ Ok(())
+ }
+
+ /// Drain all heaps in partition-key order and return the rows as
+ /// a stream of coalesced `RecordBatch`es ordered by
+ /// `(partition_keys, order_keys)`.
+ pub(crate) fn emit(self) -> Result<SendableRecordBatchStream> {
+ let Self {
+ schema,
+ metrics,
+ reservation: _,
+ expr: _,
+ row_converter: _,
+ scratch_rows: _,
+ partition_exprs: _,
+ partition_converter: _,
+ mut heaps,
+ k: _,
+ batch_size,
+ } = self;
+ let _timer = metrics.baseline.elapsed_compute().timer();
+
+ let mut sorted_pks: Vec<OwnedRow> = heaps.keys().cloned().collect();
+ sorted_pks.sort();
+
+ let mut coalescer = BatchCoalescer::new(Arc::clone(&schema), batch_size);
+
+ for pk in sorted_pks {
+ let mut heap = heaps.remove(&pk).expect("key from heaps.keys()");
+ if let Some(batch) = heap.emit()? {
+ (&batch).record_output(&metrics.baseline);
+ coalescer.push_batch(batch)?;
+ }
+ }
+ coalescer.finish_buffered_batch()?;
+
+ let mut out: Vec<Result<RecordBatch>> = Vec::new();
+ while let Some(b) = coalescer.next_completed_batch() {
+ out.push(Ok(b));
+ }
+
+ Ok(Box::pin(RecordBatchStreamAdapter::new(
+ schema,
+ futures::stream::iter(out),
+ )))
+ }
+
+ /// Total memory currently held by this operator, including all
+ /// per-partition heaps.
+ fn size(&self) -> usize {
+ size_of::<Self>()
+ + self.row_converter.size()
+ + self.partition_converter.size()
+ + self.scratch_rows.size()
+ + self.heaps.values().map(|h| h.size()).sum::<usize>()
+ + self.heaps.capacity() * (size_of::<OwnedRow>() + size_of::<TopKHeap>())
+ }
+}
+
#[cfg(test)]
mod tests {
use super::*;
@@ -1845,4 +2060,320 @@ mod tests {
Ok(())
}
+
+ /// Builds a `(pk Int32, val Int32)` schema and a `PartitionedTopK`
+ /// partitioned by `pk` with order `val ASC`. Helper for the
+ /// `PartitionedTopK` tests below.
+ fn build_partitioned_topk(k: usize) -> Result<(Arc<Schema>, PartitionedTopK)> {
+ build_partitioned_topk_with_opts(k, SortOptions::default(), false)
+ }
+
+ /// Variant of [`build_partitioned_topk`] that lets the test pick the
+ /// `val` column's `SortOptions` (direction, null ordering) and
+ /// nullability. Used by tests that exercise the shared encoder
+ /// across `ASC`/`DESC` and `NULLS FIRST/LAST` paths.
+ fn build_partitioned_topk_with_opts(
+ k: usize,
+ val_sort_options: SortOptions,
+ val_nullable: bool,
+ ) -> Result<(Arc<Schema>, PartitionedTopK)> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("pk", DataType::Int32, false),
+ Field::new("val", DataType::Int32, val_nullable),
+ ]));
+
+ let pk_expr: Arc<dyn PhysicalExpr> = col("pk", schema.as_ref())?;
+ let pk_sort_expr = PhysicalSortExpr {
+ expr: Arc::clone(&pk_expr),
+ options: SortOptions::default(),
+ };
+ let val_sort_expr = PhysicalSortExpr {
+ expr: col("val", schema.as_ref())?,
+ options: val_sort_options,
+ };
+
+ let partition_sort_fields = build_sort_fields(&[pk_sort_expr], &schema)?;
+ let order_expr = LexOrdering::from([val_sort_expr]);
+
+ let state = PartitionedTopK::try_new(
+ 0,
+ Arc::clone(&schema),
+ vec![pk_expr],
+ partition_sort_fields,
+ order_expr,
+ k,
+ 8, // batch_size
+ &Arc::new(RuntimeEnv::default()),
+ &ExecutionPlanMetricsSet::new(),
+ )?;
+ Ok((schema, state))
+ }
+
+ fn pk_val_batch(
+ schema: &Arc<Schema>,
+ pks: Vec<i32>,
+ vals: Vec<i32>,
+ ) -> Result<RecordBatch> {
+ Ok(RecordBatch::try_new(
+ Arc::clone(schema),
+ vec![
+ Arc::new(Int32Array::from(pks)),
+ Arc::new(Int32Array::from(vals)),
+ ],
+ )?)
+ }
+
+ /// Variant of [`pk_val_batch`] that accepts nullable `val`s. Used by
+ /// tests that exercise null-ordering through the shared encoder.
+ fn nullable_pk_val_batch(
+ schema: &Arc<Schema>,
+ pks: Vec<i32>,
+ vals: Vec<Option<i32>>,
+ ) -> Result<RecordBatch> {
+ Ok(RecordBatch::try_new(
+ Arc::clone(schema),
+ vec![
+ Arc::new(Int32Array::from(pks)),
+ Arc::new(Int32Array::from(vals)),
+ ],
+ )?)
+ }
+
+ /// Multiple distinct partition keys interleaved within a single
+ /// input batch — the per-batch demux, per-partition heap eviction,
+ /// and partition-key-ordered emit must all behave correctly.
+ #[tokio::test]
+ async fn test_partitioned_topk_multi_partition_within_batch() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk(2)?;
+
+ // pk=1 vals: 10, 5, 8 → top-2 ASC = [5, 8]
+ // pk=2 vals: 20, 15 → top-2 ASC = [15, 20]
+ // pk=3 vals: 7 → top-2 ASC = [7]
+ let batch =
+ pk_val_batch(&schema, vec![1, 2, 1, 2, 1, 3], vec![10, 20, 5, 15, 8, 7])?;
+ state.insert_batch(&batch)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | 5 |",
+ "| 1 | 8 |",
+ "| 2 | 15 |",
+ "| 2 | 20 |",
+ "| 3 | 7 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
+
+ /// State must accumulate across `insert_batch` calls: a partition
+ /// key seen in batch 1 should still own its heap when batch 2
+ /// arrives, and a row in batch 2 that beats the existing K-th
+ /// best should evict the loser.
+ #[tokio::test]
+ async fn test_partitioned_topk_cross_batch_eviction() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk(2)?;
+
+ // Batch 1: pk=1 fills the heap with [50, 40].
+ state.insert_batch(&pk_val_batch(&schema, vec![1, 1], vec![50, 40])?)?;
+
+ // Batch 2: pk=1 sees a smaller value (10) — it must evict 50.
+ // pk=2 appears for the first time mid-stream.
+ state.insert_batch(&pk_val_batch(
+ &schema,
+ vec![1, 2, 1],
+ vec![10, 99, 60], // 60 > 40 stays on top, gets discarded
+ )?)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | 10 |",
+ "| 1 | 40 |",
+ "| 2 | 99 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
+
+ /// Empty input must produce an empty output stream, not panic.
+ #[tokio::test]
+ async fn test_partitioned_topk_empty_input() -> Result<()> {
+ let (_schema, state) = build_partitioned_topk(3)?;
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert!(results.is_empty(), "empty input → empty output");
+ Ok(())
+ }
+
+ /// `fetch = 1` is a common case (rn = 1 filter). The heap should
+ /// hold exactly one row per partition: the partition's minimum.
+ #[tokio::test]
+ async fn test_partitioned_topk_fetch_one() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk(1)?;
+ state.insert_batch(&pk_val_batch(
+ &schema,
+ vec![1, 1, 2, 2, 3],
+ vec![3, 1, 9, 4, 7],
+ )?)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | 1 |",
+ "| 2 | 4 |",
+ "| 3 | 7 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
+
+ /// `ORDER BY val DESC` exercises the shared encoder's sort-direction
+ /// handling: the row converter must flip the sort sign for `val` so
+ /// that larger values compare smaller in row-encoded form. Each
+ /// partition should keep its top-K *largest* values.
+ #[tokio::test]
+ async fn test_partitioned_topk_desc_ordering() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk_with_opts(
+ 2,
+ SortOptions {
+ descending: true,
+ nulls_first: false,
+ },
+ false,
+ )?;
+
+ // pk=1 vals: 10, 5, 8, 12 → top-2 DESC = [12, 10]
+ // pk=2 vals: 20, 15, 25 → top-2 DESC = [25, 20]
+ let batch = pk_val_batch(
+ &schema,
+ vec![1, 2, 1, 2, 1, 1, 2],
+ vec![10, 20, 5, 15, 8, 12, 25],
+ )?;
+ state.insert_batch(&batch)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | 12 |",
+ "| 1 | 10 |",
+ "| 2 | 25 |",
+ "| 2 | 20 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
+
+ /// NULL sort values exercise the shared encoder's null-ordering
+ /// handling. With `ASC NULLS LAST`, NULLs sort *after* every
+ /// non-NULL value, so a partition whose only non-NULL value beats
+ /// a NULL must evict the NULL when `K = 1`. A partition that holds
+ /// only NULLs must still emit them.
+ #[tokio::test]
+ async fn test_partitioned_topk_nulls_last_ordering() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk_with_opts(
+ 1,
+ SortOptions {
+ descending: false,
+ nulls_first: false,
+ },
+ true,
+ )?;
+
+ // pk=1 vals: NULL, 7, NULL → top-1 ASC NULLS LAST = [7]
+ // pk=2 vals: NULL → top-1 = [NULL]
+ // pk=3 vals: NULL, 4, 2 → top-1 = [2]
+ let batch = nullable_pk_val_batch(
+ &schema,
+ vec![1, 2, 1, 1, 3, 3, 3],
+ vec![None, None, Some(7), None, None, Some(4), Some(2)],
+ )?;
+ state.insert_batch(&batch)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | 7 |",
+ "| 2 | |",
+ "| 3 | 2 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
+
+ /// `ASC NULLS FIRST` (the `SortOptions::default()`) sorts NULLs
+ /// *before* every non-NULL value, so under `fetch = K` a partition's
+ /// NULLs are kept preferentially over larger non-NULL values.
+ #[tokio::test]
+ async fn test_partitioned_topk_nulls_first_ordering() -> Result<()> {
+ let (schema, mut state) = build_partitioned_topk_with_opts(
+ 2,
+ SortOptions {
+ descending: false,
+ nulls_first: true,
+ },
+ true,
+ )?;
+
+ // pk=1 vals: NULL, 5, NULL, 8 → top-2 ASC NULLS FIRST = [NULL, NULL]
+ // pk=2 vals: 7, NULL → top-2 = [NULL, 7]
+ // pk=3 vals: 3, 1 → top-2 = [1, 3]
+ let batch = nullable_pk_val_batch(
+ &schema,
+ vec![1, 2, 1, 3, 1, 2, 1, 3],
+ vec![
+ None,
+ Some(7),
+ Some(5),
+ Some(3),
+ None,
+ None,
+ Some(8),
+ Some(1),
+ ],
+ )?;
+ state.insert_batch(&batch)?;
+
+ let results: Vec<_> = state.emit()?.try_collect().await?;
+ assert_batches_eq!(
+ &[
+ "+----+-----+",
+ "| pk | val |",
+ "+----+-----+",
+ "| 1 | |",
+ "| 1 | |",
+ "| 2 | |",
+ "| 2 | 7 |",
+ "| 3 | 1 |",
+ "| 3 | 3 |",
+ "+----+-----+",
+ ],
+ &results
+ );
+ Ok(())
+ }
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org