You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "SubhamSinghal (via GitHub)" <gi...@apache.org> on 2026/07/24 15:28:39 UTC
[PR] perf: Extend WindowTopN to dense rank [datafusion]
SubhamSinghal opened a new pull request, #23869:
URL: https://github.com/apache/datafusion/pull/23869
## Which issue does this PR close?
- Related to #6899. Completes the ROW_NUMBER + RANK + DENSE_RANK trio requested by the issue (ROW_NUMBER shipped in #21479; RANK is in flight as PR A).
## Rationale for this change
Naive plan for `Filter(dr <= K) → BoundedWindowAggExec(DENSE_RANK) → SortExec(pk, ob) → input` sorts the full input even though only rows at the K distinct-smallest ob values per partition are needed. DENSE_RANK is stable under tail-pruning, so the rewrite preserves ranks for every retained row.
## What changes are included in this PR?
## Are these changes tested?
Yes
**h2o bench** — Q24–Q29 added; top-2 on 10M-row `large`, 3-iter avg vs `enable_window_topn=false`:
| # | Cardinality | OFF (ms) | ON (ms) | Δ |
|-----|------------------|---------:|--------:|:-------------|
| Q24 | ~100 parts | 308.19 | 114.45 | 2.20× faster |
| Q25 | ~1K, low ties | 261.24 | 113.85 | 2.13× faster |
| Q26 | ~1K, heavy ties | 296.54 | 124.42 | 2.09× faster |
| Q27 | ~10K, low ties | 250.83 | 131.85 | 1.70× faster |
| Q28 | ~10K, heavy ties | 281.00 | 149.00 | 1.76× faster |
| Q29 | ~100K parts | 264.32 | 304.37 | 1.40× slower |
## Are there any user-facing changes?
No breaking changes. Rule fires on DENSE_RANK when `datafusion.optimizer.enable_window_topn = true`; flag stays
`false` by default
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3689760010
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,433 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+#[derive(Default)]
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
+ /// INVARIANT: `keys` and `groups.keys()` hold the same set. Every
+ /// insertion into / removal from `groups` must mirror into `keys`.
+ keys: BinaryHeap<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead = self.groups.capacity()
+ * (size_of::<Vec<u8>>() + size_of::<Vec<GroupEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<GroupEntry>()
+ + entries
+ .iter()
+ .map(|e| e.row_indices.capacity() * size_of::<u32>())
+ .sum::<usize>()
+ })
+ .sum();
+ // `keys` duplicates every key's bytes; charge for them plus the
+ // heap's backing Vec (one `Vec<u8>` slot per reserved element).
+ let keys_overhead: usize = self.keys.capacity() * size_of::<Vec<u8>>()
+ + self.keys.iter().map(|k| k.capacity()).sum::<usize>();
+ table_overhead + contents + keys_overhead
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance. So is the
+/// [`RecordBatchStore`]: retained rows are held as `(batch_id, indices)`
+/// so each source batch is charged once for the whole operator, however
+/// many partitions and ob groups reference it.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `GroupEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `GroupEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, read from the `state.keys` max-heap
+/// in O(1):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ /// Source batches referenced by the retained `GroupEntry`s, held once
+ /// for the whole operator with a use count per batch. This is what
+ /// keeps the reservation proportional to the batches actually pinned
+ /// rather than to the number of entries pointing at them.
+ store: RecordBatchStore,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ store: RecordBatchStore::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`GroupEntry`].
+ 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(());
+ }
+
+ // Register this batch with the store up front. `uses` is bumped
+ // once per `GroupEntry` created below but lives on this local
+ // entry, so the store sees a single insert per batch rather than
+ // one per group — and `insert` drops batches that retained
+ // nothing without ever charging for them.
+ let mut batch_entry = self.store.register(batch.clone());
+ let batch_id = batch_entry.id;
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `GroupEntry`.
+ for (pk, indices) in groups.drain() {
+ let state = self
+ .states
+ .entry(pk)
+ .or_insert_with(DenseRankPartitionState::default);
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `GroupEntry` (one entry per contributing batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ batch_entry.uses += 1;
+ entries.push(GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ batch_entry.uses += 1;
+ state.keys.push(ob_key.clone());
+ state.groups.insert(
+ ob_key,
+ vec![GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ }],
+ );
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. The largest tracked
+ // ob value is the admission boundary.
+ let max_key = state.keys.peek().expect("state.groups has k >= 1 keys");
+ if ob_key.as_slice() < max_key.as_slice() {
+ // Evict the entire max-key group, from both the map
+ // and its ordered mirror.
+ let evicted_key = state.keys.pop().expect("max key present");
+ let evicted = state
+ .groups
+ .remove(&evicted_key)
+ .expect("keys mirrors groups");
+ for e in &evicted {
+ replacements += e.row_indices.len();
+ if e.batch_id == batch_id {
+ // Admitted earlier in this same call, so the
+ // store has not seen `batch_entry` yet — drop
+ // the pending use rather than calling `unuse`,
+ // which panics on an unregistered id.
+ batch_entry.uses -= 1;
+ } else {
+ self.store.unuse(e.batch_id);
+ }
+ }
+ batch_entry.uses += 1;
+ state.keys.push(ob_key.clone());
+ state.groups.insert(
+ ob_key,
+ vec![GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ }],
+ );
+ }
+ // else: ob >= max — drop the whole run.
+ }
+
+ // Return the drained scratch map (capacity retained) for the
+ // next partition to reuse.
+ self.ob_runs = runs;
+ }
+
+ // Return the drained scratch map (capacity retained) for the next
+ // batch to reuse.
+ self.partition_groups = groups;
+
+ // Charges `batch` once if any group retained rows from it.
+ self.store.insert(batch_entry);
+
+ if replacements > 0 {
+ self.metrics.row_replacements.add(replacements);
+ }
+ self.reservation.try_resize(self.size())?;
+ Ok(())
+ }
+
+ /// Drain all per-partition maps in partition-key order and return
+ /// the rows as a stream of coalesced [`RecordBatch`]es ordered by
+ /// `(partition_keys, order_keys)`. Within a partition the distinct
+ /// ob keys are sorted (byte-comparable encoding == sort order) so
+ /// emitted rows are in ob-sorted order.
+ pub(crate) fn emit(self) -> Result<SendableRecordBatchStream> {
+ let Self {
+ schema,
+ metrics,
+ reservation: _,
+ expr: _,
+ row_converter: _,
+ scratch_rows: _,
+ partition_exprs: _,
+ partition_converter: _,
+ partition_scratch_rows: _,
+ mut states,
+ partition_groups: _,
+ ob_runs: _,
+ store,
+ k: _,
+ batch_size,
+ } = self;
+ let _timer = metrics.baseline.elapsed_compute().timer();
+
+ let mut sorted_pks: Vec<Vec<u8>> = states.keys().cloned().collect();
+ sorted_pks.sort();
+
+ let mut coalescer = BatchCoalescer::new(Arc::clone(&schema), batch_size);
+
+ for pk in sorted_pks {
+ let DenseRankPartitionState { groups, keys: _ } =
+ states.remove(&pk).expect("key from states.keys()");
+ // Sort the <= K distinct ob keys so rows emit ascending
+ // (byte-comparable encoding == sort order).
+ let mut sorted_obs: Vec<(Vec<u8>, Vec<GroupEntry>)> =
+ groups.into_iter().collect();
+ sorted_obs.sort_by(|a, b| a.0.cmp(&b.0));
+ for (_ob, entries) in sorted_obs {
+ for entry in entries {
+ let batch = &store
+ .get(entry.batch_id)
+ .expect("retained batch_id present in store")
+ .batch;
+ let indices = UInt32Array::from(entry.row_indices);
+ let sub = take_record_batch(batch, &indices)?;
+ (&sub).record_output(&metrics.baseline);
+ coalescer.push_batch(sub)?;
+ }
+ }
+ }
+ 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, including all per-partition states.
+ fn size(&self) -> usize {
+ size_of::<Self>()
+ + self.row_converter.size()
+ + self.partition_converter.size()
+ + self.scratch_rows.size()
+ + self.partition_scratch_rows.size()
+ + self.states.values().map(|s| s.size()).sum::<usize>()
Review Comment:
@kumarUjjawal Fixed in c7e67c9f42330563ad21f8ee8e9d82de360b6b6c.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158056503
@kumarUjjawal can you run benchmark?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5174771151
@kumarUjjawal can we merge this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5334771119
🚀
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3667311772
##########
datafusion/physical-optimizer/src/window_topn.rs:
##########
@@ -172,10 +182,10 @@ impl WindowTopN {
return None;
}
- // For RANK: an empty ORDER BY makes every row tie at rank 1 —
- // the optimization is degenerate (we'd retain the entire input)
- // and tie storage would be unbounded.
- if matches!(fn_kind, WindowFnKind::Rank)
+ // For RANK / DENSE_RANK: an empty ORDER BY makes every row tie
+ // at rank 1 — the optimization is degenerate (we'd retain the
+ // entire input) and tie storage would be unbounded.
+ if matches!(fn_kind, WindowFnKind::Rank | WindowFnKind::DenseRank)
Review Comment:
Fixed in 4530bba18ccbf135cf2b1ef85e37fd321cb946d7. Replaced order_by().is_empty() with a structural guard: sort_exec.expr().len() <= partition_prefix_len → bail. Catches `PARTITION BY pk ORDER BY pk` (and no-ORDER-BY ROW_NUMBER). Added SLT regression.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155932052
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23869#issuecomment-5155862734)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing window-topn-dense-rank (c7e67c9f42330563ad21f8ee8e9d82de360b6b6c) to 582453b (merge-base) [diff](https://github.com/apache/datafusion/compare/582453b680e7a9b927d659753edb8f33a444a3c8..c7e67c9f42330563ad21f8ee8e9d82de360b6b6c)
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o_small_window
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and window-topn-dense-rank
--------------------
Benchmark h2o_window.json
--------------------
┏━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ HEAD ┃ window-topn-dense-rank ┃ Change ┃
┡━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 140.25 ms │ 138.68 ms │ no change │
│ QQuery 2 │ 1959.66 ms │ 1948.36 ms │ no change │
│ QQuery 3 │ 2608.72 ms │ 2663.85 ms │ no change │
│ QQuery 4 │ 446.65 ms │ 448.37 ms │ no change │
│ QQuery 5 │ 1228.23 ms │ 1242.50 ms │ no change │
│ QQuery 6 │ 2890.11 ms │ 2896.88 ms │ no change │
│ QQuery 7 │ 2568.40 ms │ 2727.36 ms │ 1.06x slower │
│ QQuery 8 │ 9509.75 ms │ 9583.44 ms │ no change │
│ QQuery 9 │ 413.64 ms │ 393.92 ms │ no change │
│ QQuery 10 │ 591.04 ms │ 537.79 ms │ +1.10x faster │
│ QQuery 11 │ 495.43 ms │ 539.91 ms │ 1.09x slower │
│ QQuery 12 │ 1067.79 ms │ 1084.89 ms │ no change │
│ QQuery 13 │ 316.17 ms │ 191.78 ms │ +1.65x faster │
│ QQuery 14 │ 396.79 ms │ 164.49 ms │ +2.41x faster │
│ QQuery 15 │ 344.12 ms │ 164.48 ms │ +2.09x faster │
│ QQuery 16 │ 320.97 ms │ 192.04 ms │ +1.67x faster │
│ QQuery 17 │ 311.42 ms │ 512.62 ms │ 1.65x slower │
│ QQuery 18 │ 431.59 ms │ 165.70 ms │ +2.60x faster │
│ QQuery 19 │ 368.18 ms │ 162.13 ms │ +2.27x faster │
│ QQuery 20 │ 401.14 ms │ 164.95 ms │ +2.43x faster │
│ QQuery 21 │ 343.74 ms │ 186.03 ms │ +1.85x faster │
│ QQuery 22 │ 388.89 ms │ 203.33 ms │ +1.91x faster │
│ QQuery 23 │ 369.97 ms │ 528.95 ms │ 1.43x slower │
└───────────┴────────────┴────────────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━┩
│ Total Time (HEAD) │ 27912.63ms │
│ Total Time (window-topn-dense-rank) │ 26842.46ms │
│ Average Time (HEAD) │ 1213.59ms │
│ Average Time (window-topn-dense-rank) │ 1167.06ms │
│ Queries Faster │ 10 │
│ Queries Slower │ 4 │
│ Queries with No Change │ 9 │
│ Queries with Failure │ 0 │
└───────────────────────────────────────┴────────────┘
Distribution per query (min / mean ±stddev / max):
Comparing HEAD and window-topn-dense-rank
--------------------
Benchmark h2o_window.json
--------------------
┏━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ HEAD ┃ window-topn-dense-rank ┃ Change ┃
┡━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 140.25 / 143.46 ±4.03 / 149.14 ms │ 138.68 / 142.82 ±3.63 / 147.52 ms │ no change │
│ QQuery 2 │ 1959.66 / 1969.53 ±8.62 / 1980.66 ms │ 1948.36 / 1961.95 ±9.68 / 1970.17 ms │ no change │
│ QQuery 3 │ 2608.72 / 2707.63 ±99.87 / 2844.39 ms │ 2663.85 / 2877.99 ±151.43 / 2987.13 ms │ 1.06x slower │
│ QQuery 4 │ 446.65 / 485.82 ±27.71 / 506.04 ms │ 448.37 / 462.84 ±11.69 / 477.00 ms │ no change │
│ QQuery 5 │ 1228.23 / 1247.93 ±13.97 / 1259.05 ms │ 1242.50 / 1255.92 ±14.75 / 1276.45 ms │ no change │
│ QQuery 6 │ 2890.11 / 2910.50 ±14.66 / 2923.93 ms │ 2896.88 / 2907.44 ±7.95 / 2916.06 ms │ no change │
│ QQuery 7 │ 2568.40 / 2595.59 ±23.14 / 2624.96 ms │ 2727.36 / 2739.33 ±9.26 / 2749.92 ms │ 1.06x slower │
│ QQuery 8 │ 9509.75 / 9559.75 ±35.67 / 9590.54 ms │ 9583.44 / 9689.18 ±76.74 / 9763.18 ms │ no change │
│ QQuery 9 │ 413.64 / 434.05 ±15.16 / 449.94 ms │ 393.92 / 439.29 ±35.64 / 480.99 ms │ no change │
│ QQuery 10 │ 591.04 / 612.35 ±15.64 / 628.14 ms │ 537.79 / 554.54 ±18.52 / 580.35 ms │ +1.10x faster │
│ QQuery 11 │ 495.43 / 504.66 ±7.43 / 513.63 ms │ 539.91 / 570.18 ±23.72 / 597.85 ms │ 1.13x slower │
│ QQuery 12 │ 1067.79 / 1074.50 ±4.86 / 1079.17 ms │ 1084.89 / 1089.07 ±4.41 / 1095.17 ms │ no change │
│ QQuery 13 │ 316.17 / 322.69 ±6.68 / 331.87 ms │ 191.78 / 207.06 ±13.73 / 225.09 ms │ +1.56x faster │
│ QQuery 14 │ 396.79 / 398.29 ±1.23 / 399.82 ms │ 164.49 / 174.18 ±6.86 / 179.51 ms │ +2.29x faster │
│ QQuery 15 │ 344.12 / 365.83 ±22.52 / 396.86 ms │ 164.48 / 170.69 ±4.40 / 173.96 ms │ +2.14x faster │
│ QQuery 16 │ 320.97 / 326.39 ±4.38 / 331.71 ms │ 192.04 / 199.76 ±5.53 / 204.71 ms │ +1.63x faster │
│ QQuery 17 │ 311.42 / 329.41 ±24.62 / 364.22 ms │ 512.62 / 544.55 ±35.76 / 594.48 ms │ 1.65x slower │
│ QQuery 18 │ 431.59 / 441.26 ±7.35 / 449.40 ms │ 165.70 / 167.57 ±1.98 / 170.31 ms │ +2.63x faster │
│ QQuery 19 │ 368.18 / 376.24 ±8.35 / 387.75 ms │ 162.13 / 166.18 ±4.95 / 173.16 ms │ +2.26x faster │
│ QQuery 20 │ 401.14 / 430.25 ±24.58 / 461.27 ms │ 164.95 / 169.45 ±3.56 / 173.64 ms │ +2.54x faster │
│ QQuery 21 │ 343.74 / 358.85 ±11.49 / 371.58 ms │ 186.03 / 191.61 ±4.87 / 197.89 ms │ +1.87x faster │
│ QQuery 22 │ 388.89 / 412.16 ±28.70 / 452.60 ms │ 203.33 / 207.50 ±3.14 / 210.90 ms │ +1.99x faster │
│ QQuery 23 │ 369.97 / 372.38 ±2.92 / 376.48 ms │ 528.95 / 562.11 ±33.85 / 608.59 ms │ 1.51x slower │
└───────────┴───────────────────────────────────────┴────────────────────────────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━┩
│ Total Time (HEAD) │ 28379.53ms │
│ Total Time (window-topn-dense-rank) │ 27451.21ms │
│ Average Time (HEAD) │ 1233.89ms │
│ Average Time (window-topn-dense-rank) │ 1193.53ms │
│ Queries Faster │ 10 │
│ Queries Slower │ 5 │
│ Queries with No Change │ 8 │
│ Queries with Failure │ 0 │
└───────────────────────────────────────┴────────────┘
```
</p>
</details>
<details><summary>Resource Usage</summary>
**h2o_small_window — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 90.0s |
| Peak memory | 4.3 GiB |
| Avg memory | 1.0 GiB |
| CPU user | 386.4s |
| CPU sys | 13.0s |
| Peak spill | 0 B |
**h2o_small_window — branch**
| Metric | Value |
|--------|-------|
| Wall time | 85.0s |
| Peak memory | 4.1 GiB |
| Avg memory | 1.0 GiB |
| CPU user | 356.8s |
| CPU sys | 12.3s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5147570352
run benchmark h2o
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5151739772
Thanks @alamb! The rule is **default-off** (`datafusion.optimizer.enable_window_topn = false`), so a plain benchmark run measures the same plan on both sides. Set `DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN=true` to see it.
target benchmark queries live in `benchmarks/queries/h2o/window.sql`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5156096137
@kumarUjjawal benchmark PR: https://github.com/apache/datafusion/pull/24050
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158097741
run benchmark h2o_small_window
```yaml
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683250208
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
Review Comment:
Fixed in 8e97623c98969a34d9991c4920e479985b0b89e8.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3681020879
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
Review Comment:
I think there is a memory accounting issue here. `DenseRankPartitionState::size()` adds `e.batch_bytes` for every `TieEntry`, but the new dense-rank path creates one `TieEntry` per retained ORDER BY group while each entry only holds an `Arc` clone of the same source `RecordBatch` (see the insertions at lines 2056, 2068, and 2104).
That means a single input batch with K retained distinct values is charged roughly `K * get_record_batch_memory_size(batch)`, even though the Arrow buffers are only retained once. The existing rank tie path has some precedent for conservative duplicate charging, but for dense-rank this becomes the common case because one batch can contribute many retained groups.
I reproduced this with datafusion-cli using the script below. With `enable_window_topn=true`, `target_partitions=1`, `--batch-size 2000`, and `--memory-limit 50M`, the query fails trying to allocate about 2001.6 MiB for `PartitionedTopKDenseRank[0]`. Running the same query with `enable_window_topn=false` succeeds and returns 200 rows.
```bash
python3 - <<'PY'
with open('/tmp/df_dr.csv','w') as f:
f.write('pk,val,payload\n')
payload='x'*10000
for g in range(1,1001):
f.write(f'{g%2},{g},{payload}\n')
PY
cargo run -q -p datafusion-cli -- \
--batch-size 2000 --memory-limit 50M \
--command "
SET datafusion.optimizer.enable_window_topn = true;
SET datafusion.execution.target_partitions = 1;
CREATE EXTERNAL TABLE dr(pk INT, val INT, payload VARCHAR)
STORED AS CSV LOCATION '/tmp/df_dr.csv'
OPTIONS (format.has_header true);
SELECT count(pk), count(val), count(payload)
FROM (
SELECT pk, val, payload,
DENSE_RANK() OVER (PARTITION BY pk ORDER BY val) AS drnk
FROM dr
)
WHERE drnk <= 100;
"
```
Could we account for retained batches uniquely instead? For example, by reusing or extending the existing `RecordBatchStore` style accounting, or by storing batch IDs with ref-counted byte accounting. It would also be great to add a regression test covering the case where one batch contributes multiple retained dense-rank groups.
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
Review Comment:
Small naming suggestion. The dense-rank implementation currently describes the retained groups as `HashMap<Vec<u8>, Vec<TieEntry>>`. After fixing the memory accounting, it might be worth introducing a type name that reflects retained batch slices instead of reusing `TieEntry`, since these entries represent more than just boundary ties. I think that would make the ownership and accounting invariant a bit clearer.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155824800
> Actually writing a specific post just about topk per partition would probably be neat too if you are interested 🤔 (I likely don't have time to help for a while just FI)
That sound great. If you have the structure in mind I can give it a try. I can't promises though.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5253420710
Sorry I haven't had a chance to review this but the idea sounds great to me
I am hoping to have a chance to mess around with this as part of writing the 55 blog.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5147611749
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23869#issuecomment-5147570352)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5147570352-1334-wkpln 6.12.85+ #1 SMP Mon May 11 08:17:35 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing window-topn-dense-rank (c7e67c9f42330563ad21f8ee8e9d82de360b6b6c) to 582453b (merge-base) [diff](https://github.com/apache/datafusion/compare/582453b680e7a9b927d659753edb8f33a444a3c8..c7e67c9f42330563ad21f8ee8e9d82de360b6b6c)
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683430470
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,435 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
+ /// INVARIANT: `keys` and `groups.keys()` hold the same set. Every
+ /// insertion into / removal from `groups` must mirror into `keys`.
+ keys: BinaryHeap<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead = self.groups.capacity()
+ * (size_of::<Vec<u8>>() + size_of::<Vec<GroupEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<GroupEntry>()
+ + entries
+ .iter()
+ .map(|e| e.row_indices.capacity() * size_of::<u32>())
+ .sum::<usize>()
+ })
+ .sum();
+ // `keys` duplicates every key's bytes; charge for them plus the
+ // heap's backing Vec (one `Vec<u8>` slot per reserved element).
+ let keys_overhead: usize = self.keys.capacity() * size_of::<Vec<u8>>()
+ + self.keys.iter().map(|k| k.capacity()).sum::<usize>();
+ table_overhead + contents + keys_overhead
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance. So is the
+/// [`RecordBatchStore`]: retained rows are held as `(batch_id, indices)`
+/// so each source batch is charged once for the whole operator, however
+/// many partitions and ob groups reference it.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `GroupEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `GroupEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, read from the `state.keys` max-heap
+/// in O(1):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ /// Source batches referenced by the retained `GroupEntry`s, held once
+ /// for the whole operator with a use count per batch. This is what
+ /// keeps the reservation proportional to the batches actually pinned
+ /// rather than to the number of entries pointing at them.
+ store: RecordBatchStore,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ store: RecordBatchStore::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`GroupEntry`].
+ 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(());
+ }
+
+ // Register this batch with the store up front. `uses` is bumped
+ // once per `GroupEntry` created below but lives on this local
+ // entry, so the store sees a single insert per batch rather than
+ // one per group — and `insert` drops batches that retained
+ // nothing without ever charging for them.
+ let mut batch_entry = self.store.register(batch.clone());
+ let batch_id = batch_entry.id;
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
Review Comment:
fixed in afc931c10aa0d15445bb8b49f4779e03a7d79ac0 using `BinaryHeap::new()`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683242879
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
Review Comment:
Renamed it to `GroupEntry`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3667324958
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ state.groups.insert(
+ ob_key,
+ vec![TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ }],
+ );
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. Find the current
+ // max (K-th distinct-best) via an O(K) scan — cold path.
+ // Scoped so the immutable borrow ends before mutation.
+ let evict_key: Option<Vec<u8>> = {
+ let max_key = state
+ .groups
+ .keys()
+ .map(|key| key.as_slice())
+ .max()
Review Comment:
I had kept it unoptimised thinking K will be small. Fixed in 4530bba18ccbf135cf2b1ef85e37fd321cb946d7. Cache the admission boundary (max_key); the O(K) scan runs only when stale (after eviction/fill), so the common "worse than boundary → drop" path is O(1).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155866967
show benchmark queue
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5147717884
Benchmark for [this request](https://github.com/apache/datafusion/pull/23869#issuecomment-5147570352) failed.
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o
```
</details>
Last 20 lines of output:
<details><summary>Click to expand</summary>
```
# Micro-Benchmarks (specific operators and features)
cancellation: How long cancelling a query takes
nlj: Benchmark for simple nested loop joins, testing various join scenarios
hj: Benchmark for simple hash joins, testing various join scenarios
smj: Benchmark for simple sort merge joins, testing various join scenarios
dict: Benchmark for dictionary-encoded group-by scenarios
compile_profile: Compile and execute TPC-H across selected Cargo profiles, reporting timing and binary size
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Supported Configuration (Environment Variables)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DATA_DIR directory to store datasets
CARGO_COMMAND command that runs the benchmark binary
DATAFUSION_DIR directory to use (default /workspace/datafusion-base)
RESULTS_NAME folder where the benchmark files are stored
PREFER_HASH_JOIN Prefer hash join algorithm (default true)
SIMULATE_LATENCY Simulate object store latency to mimic S3 (default false)
DATAFUSION_* Set the given datafusion configuration
```
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5323322305
Thank you everyone!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3667294420
##########
datafusion/physical-optimizer/src/window_topn.rs:
##########
@@ -325,6 +336,7 @@ fn supported_window_fn(
match udf.fun().name() {
"row_number" => Some(WindowFnKind::RowNumber),
"rank" => Some(WindowFnKind::Rank),
+ "dense_rank" => Some(WindowFnKind::DenseRank),
Review Comment:
Fixed in 4530bba18ccbf135cf2b1ef85e37fd321cb946d7. The rewrite now bails unless every window expr is ROW_NUMBER/RANK/DENSE_RANK over the same PARTITION BY/ORDER BY. LEAD and aggregates are excluded. Added EXPLAIN + correctness SLT regressions for SUM and LEAD siblings.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5115572903
@2010YOUY01 Can you take a look at this whenever you get the chance.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "jayzhan211 (via GitHub)" <gi...@apache.org>.
jayzhan211 commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3792003354
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
Review Comment:
Could `RecordBatchStore` be useful for cases beyond TopK? If so, we could move it to common in a separate PR.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158210623
🤖 Benchmark completed (GKE) | [trigger](https://github.com/apache/datafusion/pull/23869#issuecomment-5158097741)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB)
Comparing window-topn-dense-rank (ee8b7c219efbcb384fe5bc7314f3fad8f6a9054d) to 66c3840 (merge-base) [diff](https://github.com/apache/datafusion/compare/66c3840c029e839eb8d49d5dd721a4d1735152aa..ee8b7c219efbcb384fe5bc7314f3fad8f6a9054d)
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o_small_window
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
</details>
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
<details><summary>Details</summary>
<p>
```
Comparing HEAD and window-topn-dense-rank
--------------------
Benchmark h2o_window.json
--------------------
┏━━━━━━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ HEAD ┃ window-topn-dense-rank ┃ Change ┃
┡━━━━━━━━━━━╇━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 139.90 ms │ 139.28 ms │ no change │
│ QQuery 2 │ 1976.63 ms │ 1957.91 ms │ no change │
│ QQuery 3 │ 2597.51 ms │ 2774.57 ms │ 1.07x slower │
│ QQuery 4 │ 464.49 ms │ 448.37 ms │ no change │
│ QQuery 5 │ 1246.66 ms │ 1230.89 ms │ no change │
│ QQuery 6 │ 2889.29 ms │ 2867.77 ms │ no change │
│ QQuery 7 │ 2632.05 ms │ 2647.95 ms │ no change │
│ QQuery 8 │ 9522.73 ms │ 9478.67 ms │ no change │
│ QQuery 9 │ 413.19 ms │ 403.21 ms │ no change │
│ QQuery 10 │ 537.38 ms │ 540.51 ms │ no change │
│ QQuery 11 │ 515.82 ms │ 513.04 ms │ no change │
│ QQuery 12 │ 1069.46 ms │ 1081.66 ms │ no change │
│ QQuery 13 │ 309.51 ms │ 188.20 ms │ +1.64x faster │
│ QQuery 14 │ 398.30 ms │ 159.92 ms │ +2.49x faster │
│ QQuery 15 │ 339.33 ms │ 161.54 ms │ +2.10x faster │
│ QQuery 16 │ 329.24 ms │ 204.81 ms │ +1.61x faster │
│ QQuery 17 │ 309.06 ms │ 500.74 ms │ 1.62x slower │
│ QQuery 18 │ 418.62 ms │ 155.64 ms │ +2.69x faster │
│ QQuery 19 │ 373.29 ms │ 157.84 ms │ +2.36x faster │
│ QQuery 20 │ 404.65 ms │ 168.67 ms │ +2.40x faster │
│ QQuery 21 │ 340.14 ms │ 191.72 ms │ +1.77x faster │
│ QQuery 22 │ 362.01 ms │ 194.66 ms │ +1.86x faster │
│ QQuery 23 │ 343.43 ms │ 513.71 ms │ 1.50x slower │
│ QQuery 24 │ 449.15 ms │ 164.73 ms │ +2.73x faster │
│ QQuery 25 │ 372.74 ms │ 172.98 ms │ +2.15x faster │
│ QQuery 26 │ 395.08 ms │ 168.96 ms │ +2.34x faster │
│ QQuery 27 │ 343.92 ms │ 189.73 ms │ +1.81x faster │
│ QQuery 28 │ 356.34 ms │ 190.04 ms │ +1.88x faster │
│ QQuery 29 │ 346.17 ms │ 432.66 ms │ 1.25x slower │
└───────────┴────────────┴────────────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━┩
│ Total Time (HEAD) │ 30196.09ms │
│ Total Time (window-topn-dense-rank) │ 28000.38ms │
│ Average Time (HEAD) │ 1041.24ms │
│ Average Time (window-topn-dense-rank) │ 965.53ms │
│ Queries Faster │ 14 │
│ Queries Slower │ 4 │
│ Queries with No Change │ 11 │
│ Queries with Failure │ 0 │
└───────────────────────────────────────┴────────────┘
Distribution per query (min / mean ±stddev / max):
Comparing HEAD and window-topn-dense-rank
--------------------
Benchmark h2o_window.json
--------------------
┏━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓
┃ Query ┃ HEAD ┃ window-topn-dense-rank ┃ Change ┃
┡━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩
│ QQuery 1 │ 139.90 / 143.66 ±3.43 / 148.20 ms │ 139.28 / 142.80 ±3.18 / 146.98 ms │ no change │
│ QQuery 2 │ 1976.63 / 1980.17 ±3.94 / 1985.67 ms │ 1957.91 / 1962.06 ±4.13 / 1967.69 ms │ no change │
│ QQuery 3 │ 2597.51 / 2749.04 ±168.11 / 2983.46 ms │ 2774.57 / 3113.06 ±246.04 / 3352.12 ms │ 1.13x slower │
│ QQuery 4 │ 464.49 / 501.36 ±26.07 / 520.05 ms │ 448.37 / 481.20 ±23.41 / 501.32 ms │ no change │
│ QQuery 5 │ 1246.66 / 1253.43 ±7.41 / 1263.75 ms │ 1230.89 / 1251.83 ±15.18 / 1266.37 ms │ no change │
│ QQuery 6 │ 2889.29 / 2894.52 ±7.22 / 2904.73 ms │ 2867.77 / 2873.52 ±4.07 / 2876.71 ms │ no change │
│ QQuery 7 │ 2632.05 / 2636.70 ±4.48 / 2642.75 ms │ 2647.95 / 2654.70 ±6.21 / 2662.94 ms │ no change │
│ QQuery 8 │ 9522.73 / 9541.24 ±13.18 / 9552.40 ms │ 9478.67 / 9483.52 ±3.73 / 9487.74 ms │ no change │
│ QQuery 9 │ 413.19 / 431.06 ±14.26 / 448.09 ms │ 403.21 / 448.26 ±31.89 / 472.65 ms │ no change │
│ QQuery 10 │ 537.38 / 556.03 ±23.46 / 589.13 ms │ 540.51 / 547.57 ±5.56 / 554.08 ms │ no change │
│ QQuery 11 │ 515.82 / 529.36 ±17.49 / 554.05 ms │ 513.04 / 539.16 ±18.57 / 554.65 ms │ no change │
│ QQuery 12 │ 1069.46 / 1099.26 ±25.80 / 1132.40 ms │ 1081.66 / 1111.81 ±31.52 / 1155.31 ms │ no change │
│ QQuery 13 │ 309.51 / 323.54 ±10.12 / 333.00 ms │ 188.20 / 195.06 ±7.86 / 206.06 ms │ +1.66x faster │
│ QQuery 14 │ 398.30 / 406.38 ±7.66 / 416.67 ms │ 159.92 / 169.64 ±13.54 / 188.80 ms │ +2.40x faster │
│ QQuery 15 │ 339.33 / 362.11 ±16.65 / 378.65 ms │ 161.54 / 166.26 ±5.24 / 173.57 ms │ +2.18x faster │
│ QQuery 16 │ 329.24 / 348.97 ±18.51 / 373.73 ms │ 204.81 / 210.42 ±6.58 / 219.65 ms │ +1.66x faster │
│ QQuery 17 │ 309.06 / 329.14 ±16.55 / 349.60 ms │ 500.74 / 504.33 ±3.22 / 508.55 ms │ 1.53x slower │
│ QQuery 18 │ 418.62 / 446.08 ±29.89 / 487.64 ms │ 155.64 / 160.35 ±3.73 / 164.75 ms │ +2.78x faster │
│ QQuery 19 │ 373.29 / 382.81 ±6.92 / 389.52 ms │ 157.84 / 167.99 ±9.39 / 180.48 ms │ +2.28x faster │
│ QQuery 20 │ 404.65 / 414.08 ±11.30 / 429.97 ms │ 168.67 / 171.72 ±3.78 / 177.04 ms │ +2.41x faster │
│ QQuery 21 │ 340.14 / 342.90 ±2.93 / 346.96 ms │ 191.72 / 194.52 ±3.29 / 199.14 ms │ +1.76x faster │
│ QQuery 22 │ 362.01 / 366.22 ±5.86 / 374.50 ms │ 194.66 / 200.31 ±7.07 / 210.29 ms │ +1.83x faster │
│ QQuery 23 │ 343.43 / 355.84 ±12.77 / 373.40 ms │ 513.71 / 528.97 ±14.61 / 548.66 ms │ 1.49x slower │
│ QQuery 24 │ 449.15 / 468.43 ±21.05 / 497.71 ms │ 164.73 / 167.90 ±4.44 / 174.18 ms │ +2.79x faster │
│ QQuery 25 │ 372.74 / 383.80 ±8.07 / 391.78 ms │ 172.98 / 177.50 ±4.04 / 182.80 ms │ +2.16x faster │
│ QQuery 26 │ 395.08 / 410.34 ±18.35 / 436.14 ms │ 168.96 / 177.40 ±6.14 / 183.38 ms │ +2.31x faster │
│ QQuery 27 │ 343.92 / 355.08 ±12.58 / 372.66 ms │ 189.73 / 190.84 ±0.94 / 192.02 ms │ +1.86x faster │
│ QQuery 28 │ 356.34 / 367.34 ±8.91 / 378.15 ms │ 190.04 / 204.76 ±11.52 / 218.17 ms │ +1.79x faster │
│ QQuery 29 │ 346.17 / 371.98 ±20.81 / 397.13 ms │ 432.66 / 441.51 ±7.14 / 450.13 ms │ 1.19x slower │
└───────────┴────────────────────────────────────────┴────────────────────────────────────────┴───────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━┓
┃ Benchmark Summary ┃ ┃
┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━━┩
│ Total Time (HEAD) │ 30750.88ms │
│ Total Time (window-topn-dense-rank) │ 28638.96ms │
│ Average Time (HEAD) │ 1060.38ms │
│ Average Time (window-topn-dense-rank) │ 987.55ms │
│ Queries Faster │ 14 │
│ Queries Slower │ 4 │
│ Queries with No Change │ 11 │
│ Queries with Failure │ 0 │
└───────────────────────────────────────┴────────────┘
```
</p>
</details>
<details><summary>Resource Usage</summary>
**h2o_small_window — base (merge-base)**
| Metric | Value |
|--------|-------|
| Wall time | 95.0s |
| Peak memory | 4.2 GiB |
| Avg memory | 1.0 GiB |
| CPU user | 457.0s |
| CPU sys | 15.7s |
| Peak spill | 0 B |
**h2o_small_window — branch**
| Metric | Value |
|--------|-------|
| Wall time | 90.0s |
| Peak memory | 4.2 GiB |
| Avg memory | 1016.9 MiB |
| CPU user | 408.8s |
| CPU sys | 13.7s |
| Peak spill | 0 B |
</details>
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155871748
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23869#issuecomment-5155862734)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5155862734-1341-mw5sq 6.12.85+ #1 SMP Mon May 11 08:17:35 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing window-topn-dense-rank (c7e67c9f42330563ad21f8ee8e9d82de360b6b6c) to 582453b (merge-base) [diff](https://github.com/apache/datafusion/compare/582453b680e7a9b927d659753edb8f33a444a3c8..c7e67c9f42330563ad21f8ee8e9d82de360b6b6c)
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o_small_window
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3689341455
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,433 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+#[derive(Default)]
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
+ /// INVARIANT: `keys` and `groups.keys()` hold the same set. Every
+ /// insertion into / removal from `groups` must mirror into `keys`.
+ keys: BinaryHeap<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead = self.groups.capacity()
+ * (size_of::<Vec<u8>>() + size_of::<Vec<GroupEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<GroupEntry>()
+ + entries
+ .iter()
+ .map(|e| e.row_indices.capacity() * size_of::<u32>())
+ .sum::<usize>()
+ })
+ .sum();
+ // `keys` duplicates every key's bytes; charge for them plus the
+ // heap's backing Vec (one `Vec<u8>` slot per reserved element).
+ let keys_overhead: usize = self.keys.capacity() * size_of::<Vec<u8>>()
+ + self.keys.iter().map(|k| k.capacity()).sum::<usize>();
+ table_overhead + contents + keys_overhead
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance. So is the
+/// [`RecordBatchStore`]: retained rows are held as `(batch_id, indices)`
+/// so each source batch is charged once for the whole operator, however
+/// many partitions and ob groups reference it.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `GroupEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `GroupEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, read from the `state.keys` max-heap
+/// in O(1):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ /// Source batches referenced by the retained `GroupEntry`s, held once
+ /// for the whole operator with a use count per batch. This is what
+ /// keeps the reservation proportional to the batches actually pinned
+ /// rather than to the number of entries pointing at them.
+ store: RecordBatchStore,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ store: RecordBatchStore::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`GroupEntry`].
+ 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(());
+ }
+
+ // Register this batch with the store up front. `uses` is bumped
+ // once per `GroupEntry` created below but lives on this local
+ // entry, so the store sees a single insert per batch rather than
+ // one per group — and `insert` drops batches that retained
+ // nothing without ever charging for them.
+ let mut batch_entry = self.store.register(batch.clone());
+ let batch_id = batch_entry.id;
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `GroupEntry`.
+ for (pk, indices) in groups.drain() {
+ let state = self
+ .states
+ .entry(pk)
+ .or_insert_with(DenseRankPartitionState::default);
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `GroupEntry` (one entry per contributing batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ batch_entry.uses += 1;
+ entries.push(GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ batch_entry.uses += 1;
+ state.keys.push(ob_key.clone());
+ state.groups.insert(
+ ob_key,
+ vec![GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ }],
+ );
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. The largest tracked
+ // ob value is the admission boundary.
+ let max_key = state.keys.peek().expect("state.groups has k >= 1 keys");
+ if ob_key.as_slice() < max_key.as_slice() {
+ // Evict the entire max-key group, from both the map
+ // and its ordered mirror.
+ let evicted_key = state.keys.pop().expect("max key present");
+ let evicted = state
+ .groups
+ .remove(&evicted_key)
+ .expect("keys mirrors groups");
+ for e in &evicted {
+ replacements += e.row_indices.len();
+ if e.batch_id == batch_id {
+ // Admitted earlier in this same call, so the
+ // store has not seen `batch_entry` yet — drop
+ // the pending use rather than calling `unuse`,
+ // which panics on an unregistered id.
+ batch_entry.uses -= 1;
+ } else {
+ self.store.unuse(e.batch_id);
+ }
+ }
+ batch_entry.uses += 1;
+ state.keys.push(ob_key.clone());
+ state.groups.insert(
+ ob_key,
+ vec![GroupEntry {
+ row_indices: run_indices,
+ batch_id,
+ }],
+ );
+ }
+ // else: ob >= max — drop the whole run.
+ }
+
+ // Return the drained scratch map (capacity retained) for the
+ // next partition to reuse.
+ self.ob_runs = runs;
+ }
+
+ // Return the drained scratch map (capacity retained) for the next
+ // batch to reuse.
+ self.partition_groups = groups;
+
+ // Charges `batch` once if any group retained rows from it.
+ self.store.insert(batch_entry);
+
+ if replacements > 0 {
+ self.metrics.row_replacements.add(replacements);
+ }
+ self.reservation.try_resize(self.size())?;
+ Ok(())
+ }
+
+ /// Drain all per-partition maps in partition-key order and return
+ /// the rows as a stream of coalesced [`RecordBatch`]es ordered by
+ /// `(partition_keys, order_keys)`. Within a partition the distinct
+ /// ob keys are sorted (byte-comparable encoding == sort order) so
+ /// emitted rows are in ob-sorted order.
+ pub(crate) fn emit(self) -> Result<SendableRecordBatchStream> {
+ let Self {
+ schema,
+ metrics,
+ reservation: _,
+ expr: _,
+ row_converter: _,
+ scratch_rows: _,
+ partition_exprs: _,
+ partition_converter: _,
+ partition_scratch_rows: _,
+ mut states,
+ partition_groups: _,
+ ob_runs: _,
+ store,
+ k: _,
+ batch_size,
+ } = self;
+ let _timer = metrics.baseline.elapsed_compute().timer();
+
+ let mut sorted_pks: Vec<Vec<u8>> = states.keys().cloned().collect();
+ sorted_pks.sort();
+
+ let mut coalescer = BatchCoalescer::new(Arc::clone(&schema), batch_size);
+
+ for pk in sorted_pks {
+ let DenseRankPartitionState { groups, keys: _ } =
+ states.remove(&pk).expect("key from states.keys()");
+ // Sort the <= K distinct ob keys so rows emit ascending
+ // (byte-comparable encoding == sort order).
+ let mut sorted_obs: Vec<(Vec<u8>, Vec<GroupEntry>)> =
+ groups.into_iter().collect();
+ sorted_obs.sort_by(|a, b| a.0.cmp(&b.0));
+ for (_ob, entries) in sorted_obs {
+ for entry in entries {
+ let batch = &store
+ .get(entry.batch_id)
+ .expect("retained batch_id present in store")
+ .batch;
+ let indices = UInt32Array::from(entry.row_indices);
+ let sub = take_record_batch(batch, &indices)?;
+ (&sub).record_output(&metrics.baseline);
+ coalescer.push_batch(sub)?;
+ }
+ }
+ }
+ 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, including all per-partition states.
+ fn size(&self) -> usize {
+ size_of::<Self>()
+ + self.row_converter.size()
+ + self.partition_converter.size()
+ + self.scratch_rows.size()
+ + self.partition_scratch_rows.size()
+ + self.states.values().map(|s| s.size()).sum::<usize>()
Review Comment:
size() still omits the encoded key buffers owned by self.states and the backing tables retained by partition_groups and ob_runs after draining. With many or large partition keys, these long-lived allocations can be substantial but remain outside the memory reservation. Could we include these buffers and capacities in size(), or release the scratch capacities?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3795747684
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
Review Comment:
sure, I can look into it as followup.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kosiew (via GitHub)" <gi...@apache.org>.
kosiew commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683256216
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,435 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
Review Comment:
I think this still over-counts retained memory. Each `TieEntry` only holds an `Arc` clone of a `RecordBatch`, but `size()` adds `e.batch_bytes` for every entry. In dense-rank processing, a single input batch can contribute several retained ORDER BY groups, so the same underlying batch bytes may be charged multiple times.
The insertion sites around lines 2062, 2075, and 2100 also continue to assign the full `input_batch_bytes` value to each entry. This can inflate the reservation and cause a false `ResourcesExhausted` error when `enable_window_topn=true`.
Could we account for each shared batch allocation only once, for example by tracking unique batch allocations or moving ownership of the batch-level charge outside individual tie entries?
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,435 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
+ /// INVARIANT: `keys` and `groups.keys()` hold the same set. Every
+ /// insertion into / removal from `groups` must mirror into `keys`.
+ keys: BinaryHeap<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead = self.groups.capacity()
+ * (size_of::<Vec<u8>>() + size_of::<Vec<GroupEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<GroupEntry>()
+ + entries
+ .iter()
+ .map(|e| e.row_indices.capacity() * size_of::<u32>())
+ .sum::<usize>()
+ })
+ .sum();
+ // `keys` duplicates every key's bytes; charge for them plus the
+ // heap's backing Vec (one `Vec<u8>` slot per reserved element).
+ let keys_overhead: usize = self.keys.capacity() * size_of::<Vec<u8>>()
+ + self.keys.iter().map(|k| k.capacity()).sum::<usize>();
+ table_overhead + contents + keys_overhead
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance. So is the
+/// [`RecordBatchStore`]: retained rows are held as `(batch_id, indices)`
+/// so each source batch is charged once for the whole operator, however
+/// many partitions and ob groups reference it.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `GroupEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `GroupEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, read from the `state.keys` max-heap
+/// in O(1):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ /// Source batches referenced by the retained `GroupEntry`s, held once
+ /// for the whole operator with a use count per batch. This is what
+ /// keeps the reservation proportional to the batches actually pinned
+ /// rather than to the number of entries pointing at them.
+ store: RecordBatchStore,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ store: RecordBatchStore::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`GroupEntry`].
+ 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(());
+ }
+
+ // Register this batch with the store up front. `uses` is bumped
+ // once per `GroupEntry` created below but lives on this local
+ // entry, so the store sees a single insert per batch rather than
+ // one per group — and `insert` drops batches that retained
+ // nothing without ever charging for them.
+ let mut batch_entry = self.store.register(batch.clone());
+ let batch_id = batch_entry.id;
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
Review Comment:
Could we avoid allocating capacity for all `k` heap entries as soon as a partition is first seen? With a large `k` and many partitions, `BinaryHeap::with_capacity(k)` front-loads roughly `O(partitions * k)` heap-slot allocation even when most partitions retain only a few distinct keys.
Using `BinaryHeap::new()` or a smaller initial capacity would let the heap grow with actual usage and reduce reservation pressure for high-cardinality partition workloads.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5156025159
@kumarUjjawal Q17/Q23 are the 100K-partition ROW_NUMBER/RANK queries which are known regression and due to this feature is gated behind flag. Dense rank queries(Q24-Q29) are not run in this benchmark, shall I create a separate PR for dense rank benchmark queries?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5174781386
> @kumarUjjawal can we merge this?
This looks good to me. I'm waiting if @alamb has more thoughts on this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to dense rank [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5071893220
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23869?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `87.94727%` with `64 lines` in your changes missing coverage. Please review.
:warning: Please [upload](https://docs.codecov.com/docs/codecov-uploader) report for BASE (`main@95de385`). [Learn more](https://docs.codecov.io/docs/error-reference?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#section-missing-base-commit) about missing BASE report.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23869?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [datafusion/physical-plan/src/topk/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/23869?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Ftopk%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy90b3BrL21vZC5ycw==) | 87.84% | [13 Missing and 49 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23869?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...fusion/physical-plan/src/sorts/partitioned\_topk.rs](https://app.codecov.io/gh/apache/datafusion/pull/23869?src=pr&el=tree&filepath=datafusion%2Fphysical-plan%2Fsrc%2Fsorts%2Fpartitioned_topk.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1wbGFuL3NyYy9zb3J0cy9wYXJ0aXRpb25lZF90b3BrLnJz) | 87.50% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23869?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23869 +/- ##
=======================================
Coverage ? 80.72%
=======================================
Files ? 1090
Lines ? 370869
Branches ? 370869
=======================================
Hits ? 299391
Misses ? 53617
Partials ? 17861
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23869?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal merged PR #23869:
URL: https://github.com/apache/datafusion/pull/23869
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3672678798
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
Review Comment:
that will leaves the normal dense-rank path counting one shared batch once per retained group across every partition. This can greatly inflate the reservation and cause false ResourcesExhausted errors. Could we fix the shared-batch accounting here, or keep this rewrite disabled until #23326 is fixed?
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents + self.max_key.as_ref().map_or(0, |k| k.capacity())
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, cached in `max_key` (recomputed via
+/// an O(K) scan of `state.groups.keys()` only when the cache is stale):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ max_key: None,
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ state.groups.insert(
+ ob_key,
+ vec![TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ }],
+ );
+ // A new distinct key may raise the boundary; drop the
+ // cached max so it is recomputed on the next Case C.
+ state.max_key = None;
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. The largest tracked
+ // ob value is the admission boundary; it is cached in
+ // `max_key` and recomputed via an O(K) scan only when the
+ // cache is stale, so the common "ob >= max → drop" path is
+ // O(1). Scoped so the immutable borrow ends before mutation.
+ if state.max_key.is_none() {
+ state.max_key = state.groups.keys().max().cloned();
+ }
+ let is_smaller = state
+ .max_key
+ .as_deref()
+ .map(|max_key| ob_key.as_slice() < max_key)
+ .expect("state.groups has k >= 1 keys");
+
+ if is_smaller {
+ // Evict the entire max-key group and drop the cached
+ // max (recomputed on the next Case C).
+ let evicted_key = state.max_key.take().expect("max key present");
Review Comment:
The cache only makes rejected candidates O(1). Every accepted candidate invalidates it, so input arriving from worst to best still scans all K keys for each new value and remains O(N × K). The benchmarks use K=2 and do not exercise this case. Could we use an ordered structure or add a large-K improving-order benchmark?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5317947160
resolved merge conflict.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to dense rank [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5071741380
<!-- semver-check-comment -->
Thank you for opening this pull request!
Reviewer note: [cargo-semver-checks](https://github.com/obi1kenobi/cargo-semver-checks) reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).
<details>
<summary>Details</summary>
```
Cloning apache/main
Building datafusion v54.1.0 (current)
Built [ 84.879s] (current)
Parsing datafusion v54.1.0 (current)
Parsed [ 0.028s] (current)
Building datafusion v54.1.0 (baseline)
Built [ 84.435s] (baseline)
Parsing datafusion v54.1.0 (baseline)
Parsed [ 0.031s] (baseline)
Checking datafusion v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.720s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 173.027s] datafusion
Building datafusion-physical-optimizer v54.1.0 (current)
Built [ 31.410s] (current)
Parsing datafusion-physical-optimizer v54.1.0 (current)
Parsed [ 0.018s] (current)
Building datafusion-physical-optimizer v54.1.0 (baseline)
Built [ 31.928s] (baseline)
Parsing datafusion-physical-optimizer v54.1.0 (baseline)
Parsed [ 0.019s] (baseline)
Checking datafusion-physical-optimizer v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.125s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 64.511s] datafusion-physical-optimizer
Building datafusion-physical-plan v54.1.0 (current)
Built [ 29.258s] (current)
Parsing datafusion-physical-plan v54.1.0 (current)
Parsed [ 0.121s] (current)
Building datafusion-physical-plan v54.1.0 (baseline)
Built [ 29.046s] (baseline)
Parsing datafusion-physical-plan v54.1.0 (baseline)
Parsed [ 0.117s] (baseline)
Checking datafusion-physical-plan v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.715s] 223 checks: 222 pass, 1 fail, 0 warn, 30 skip
--- failure enum_variant_added: enum variant added on exhaustive enum ---
Description:
A publicly-visible enum without #[non_exhaustive] has a new variant.
ref: https://doc.rust-lang.org/cargo/reference/semver.html#enum-variant-new
impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.49.0/src/lints/enum_variant_added.ron
Failed in:
variant WindowFnKind:DenseRank in /home/runner/work/datafusion/datafusion/datafusion/physical-plan/src/sorts/partitioned_topk.rs:76
Summary semver requires new major version: 1 major and 0 minor checks failed
Finished [ 60.388s] datafusion-physical-plan
Building datafusion-sqllogictest v54.1.0 (current)
Built [ 145.699s] (current)
Parsing datafusion-sqllogictest v54.1.0 (current)
Parsed [ 0.017s] (current)
Building datafusion-sqllogictest v54.1.0 (baseline)
Built [ 145.289s] (baseline)
Parsing datafusion-sqllogictest v54.1.0 (baseline)
Parsed [ 0.019s] (baseline)
Checking datafusion-sqllogictest v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.090s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 293.788s] datafusion-sqllogictest
```
</details>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5147584937
Thanks @SubhamSinghal and @kumarUjjawal -- Is there a good canonical writeup of what queries this helps / benchmarks I can run to see its benefit? I am thinking ahead to writing a blog about the 55 release and I think the topK per partition optimization is quite a good one and want to call it out directly
Actually writing a specific post just about topk per partition would probably be neat too if you are interested 🤔 (I likely don't have time to help for a while just FI)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155862734
run benchmark h2o_small_window
```yaml
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5156033344
> shall I create a separate PR for dense rank benchmark queries?
That would be great. Thanks!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3667302959
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
Review Comment:
This is the DENSE_RANK instance of #23326 (same TieEntry/size() shared-buffer over-count as RANK). Keeping storage consistent so one fix in #23326 covers both operators.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5155867038
Hi @kumarUjjawal, you asked to view the benchmark queue (https://github.com/apache/datafusion/pull/23869#issuecomment-5155866967).
| Comment | Repo | PR | User | Benchmarks | Status |
| --- | --- | --- | --- | --- | --- |
| [#5155862734](https://github.com/apache/datafusion/pull/23869#issuecomment-5155862734) | apache/datafusion | #23869 | kumarUjjawal | ["h2o_small_window"] | running |
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "adriangbot (via GitHub)" <gi...@apache.org>.
adriangbot commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158112483
🤖 Benchmark running (GKE) | [trigger](https://github.com/apache/datafusion/pull/23869#issuecomment-5158097741)
**Instance:** `c4a-highmem-16` (12 vCPU / 65 GiB) | `Linux bench-c5158097741-1346-6rgvq 6.12.85+ #1 SMP Mon May 11 08:17:35 UTC 2026 aarch64 GNU/Linux`
<details><summary>CPU Details (lscpu)</summary>
```
Architecture: aarch64
CPU op-mode(s): 64-bit
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: ARM
Model name: Neoverse-V2
Model: 1
Thread(s) per core: 1
Core(s) per cluster: 16
Socket(s): -
Cluster(s): 1
Stepping: r0p1
BogoMIPS: 2000.00
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm sb paca pacg dcpodp sve2 sveaes svepmull svebitperm svesha3 svesm4 flagm2 frint svei8mm svebf16 i8mm bf16 dgh rng bti
L1d cache: 1 MiB (16 instances)
L1i cache: 1 MiB (16 instances)
L2 cache: 32 MiB (16 instances)
L3 cache: 80 MiB (1 instance)
NUMA node(s): 1
NUMA node0 CPU(s): 0-15
Vulnerability Gather data sampling: Not affected
Vulnerability Indirect target selection: Not affected
Vulnerability Itlb multihit: Not affected
Vulnerability L1tf: Not affected
Vulnerability Mds: Not affected
Vulnerability Meltdown: Not affected
Vulnerability Mmio stale data: Not affected
Vulnerability Reg file data sampling: Not affected
Vulnerability Retbleed: Not affected
Vulnerability Spec rstack overflow: Not affected
Vulnerability Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Vulnerability Spectre v1: Mitigation; __user pointer sanitization
Vulnerability Spectre v2: Mitigation; CSV2, BHB
Vulnerability Srbds: Not affected
Vulnerability Tsa: Not affected
Vulnerability Tsx async abort: Not affected
Vulnerability Vmscape: Not affected
```
</details>
Comparing window-topn-dense-rank (ee8b7c219efbcb384fe5bc7314f3fad8f6a9054d) to 66c3840 (merge-base) [diff](https://github.com/apache/datafusion/compare/66c3840c029e839eb8d49d5dd721a4d1735152aa..ee8b7c219efbcb384fe5bc7314f3fad8f6a9054d)
<details><summary>Run configuration</summary>
```yaml
run benchmark h2o_small_window
changed:
env:
DATAFUSION_OPTIMIZER_ENABLE_WINDOW_TOPN: "true"
```
</details>
Results will be posted here when complete
---
[File an issue](https://github.com/adriangb/datafusion-benchmarking/issues) against this benchmark runner
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158320016
Q17, Q23,Q29 are 100k partitions benchmark for `row_number`, `rank` and `dense_rank` which is known regression.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5158268454
apart from the q29 others look good.
cc @alamb
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683241123
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
Review Comment:
Fixed in 8e97623c98969a34d9991c4920e479985b0b89e8. Using `RecordBatchStore` as suggested.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3683382117
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,435 @@ impl PartitionedTopKRank {
}
}
+/// A run of rows from a single source [`RecordBatch`] sharing one
+/// distinct ORDER BY value. Materialized at emit time via
+/// [`take_record_batch`].
+///
+/// The batch is referenced by `batch_id` rather than held directly, so the
+/// operator-scoped [`RecordBatchStore`] can charge each distinct source
+/// batch once however many entries reference it. Holding a batch per entry
+/// and charging its bytes per entry would inflate the reservation by a
+/// factor of (partitions × K), since a single batch contributes an entry to
+/// every partition and ob group it touches.
+#[derive(Debug)]
+struct GroupEntry {
+ /// Indices into the batch identified by `batch_id`. Always non-empty
+ /// by construction.
+ row_indices: Vec<u32>,
+ /// Key into `PartitionedTopKDenseRank::store`.
+ batch_id: u32,
+}
+
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<GroupEntry>>` keyed by the row-encoded ORDER
+/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
+/// holds every row seen at that ob value, one entry per contributing
+/// source `RecordBatch`.
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<GroupEntry>>,
+ /// The same keys as `groups`, in a max-heap: the admission boundary
+ /// (the largest tracked ob value) is an O(1) `peek()` check, and
+ /// admission / removal are O(log K).
+ ///
Review Comment:
@kosiew are you referring to RANK code? at line 2100 I can see:
```
state.groups.insert(
ob_key,
vec![GroupEntry {
row_indices: run_indices,
batch_id,
}],
);
```
which is referring to batch_id. Looks like stale comment but please confirm.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3681727153
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,394 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+ /// Cached admission boundary: the largest tracked ob value once
+ /// `groups` is full. A `HashMap` is unordered, so finding it otherwise
+ /// costs an O(K) scan of the keys on *every* new distinct ob value —
+ /// O(N·K) overall on mostly-distinct input. Caching makes the common
+ /// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
+ /// is paid only when the cache is stale (`None`) — after a fill or an
+ /// eviction changes the key set.
+ max_key: Option<Vec<u8>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents + self.max_key.as_ref().map_or(0, |k| k.capacity())
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
+/// value is the admission boundary, cached in `max_key` (recomputed via
+/// an O(K) scan of `state.groups.keys()` only when the cache is stale):
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ max_key: None,
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ state.groups.insert(
+ ob_key,
+ vec![TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ }],
+ );
+ // A new distinct key may raise the boundary; drop the
+ // cached max so it is recomputed on the next Case C.
+ state.max_key = None;
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. The largest tracked
+ // ob value is the admission boundary; it is cached in
+ // `max_key` and recomputed via an O(K) scan only when the
+ // cache is stale, so the common "ob >= max → drop" path is
+ // O(1). Scoped so the immutable borrow ends before mutation.
+ if state.max_key.is_none() {
+ state.max_key = state.groups.keys().max().cloned();
+ }
+ let is_smaller = state
+ .max_key
+ .as_deref()
+ .map(|max_key| ob_key.as_slice() < max_key)
+ .expect("state.groups has k >= 1 keys");
+
+ if is_smaller {
+ // Evict the entire max-key group and drop the cached
+ // max (recomputed on the next Case C).
+ let evicted_key = state.max_key.take().expect("max key present");
Review Comment:
Fixed in a74ed66cf4381094ffea4d44ee5ee25a9b02fbf8. Replaced with binaryHeap so that worst case will be 0(Nxlog(K)) instead 0(NxK)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "SubhamSinghal (via GitHub)" <gi...@apache.org>.
SubhamSinghal commented on PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#issuecomment-5100487295
@kumarUjjawal @kosiew can you please review this PR?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] perf: Extend WindowTopN to `dense_rank` [datafusion]
Posted by "kumarUjjawal (via GitHub)" <gi...@apache.org>.
kumarUjjawal commented on code in PR #23869:
URL: https://github.com/apache/datafusion/pull/23869#discussion_r3663303926
##########
datafusion/physical-optimizer/src/window_topn.rs:
##########
@@ -325,6 +336,7 @@ fn supported_window_fn(
match udf.fun().name() {
"row_number" => Some(WindowFnKind::RowNumber),
"rank" => Some(WindowFnKind::Rank),
+ "dense_rank" => Some(WindowFnKind::DenseRank),
Review Comment:
Could we skip this rewrite when another expression in the same window operator needs following rows? The input is pruned before all window expressions run, so a sibling lead() returns the wrong value at the retained boundary. We can add a dense_rank with lead regression and only rewrite when every sibling expression is safe under tail pruning.
##########
datafusion/physical-optimizer/src/window_topn.rs:
##########
@@ -172,10 +182,10 @@ impl WindowTopN {
return None;
}
- // For RANK: an empty ORDER BY makes every row tie at rank 1 —
- // the optimization is degenerate (we'd retain the entire input)
- // and tie storage would be unbounded.
- if matches!(fn_kind, WindowFnKind::Rank)
+ // For RANK / DENSE_RANK: an empty ORDER BY makes every row tie
+ // at rank 1 — the optimization is degenerate (we'd retain the
+ // entire input) and tie storage would be unbounded.
+ if matches!(fn_kind, WindowFnKind::Rank | WindowFnKind::DenseRank)
Review Comment:
This guard misses orderings that become empty after partition keys are removed. DENSE_RANK() OVER (PARTITION BY pk ORDER BY pk) reaches PartitionedTopKExec without order expressions and panics. Please validate the effective order keys and add a regression.
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
Review Comment:
records the full source-batch size for every retained group even though the batch clones share Arrow buffers. With many partitions, memory reservation is heavily inflated and can fail with ResourcesExhausted. This expands #23326 to the normal dense-rank path; please account each source batch once or compact the retained rows.
##########
datafusion/physical-plan/src/topk/mod.rs:
##########
@@ -1811,6 +1811,376 @@ impl PartitionedTopKRank {
}
}
+/// Per-partition state for `DENSE_RANK()` semantics.
+///
+/// A `HashMap<Vec<u8>, Vec<TieEntry>>` keyed by the row-encoded ORDER BY
+/// bytes, capped at `k` distinct keys. Each key's `Vec<TieEntry>` holds
+/// every row seen at that ob value, one entry per contributing source
+/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
+struct DenseRankPartitionState {
+ groups: HashMap<Vec<u8>, Vec<TieEntry>>,
+}
+
+impl DenseRankPartitionState {
+ fn size(&self) -> usize {
+ let table_overhead =
+ self.groups.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<TieEntry>>());
+ let contents: usize = self
+ .groups
+ .iter()
+ .map(|(key, entries)| {
+ key.capacity()
+ + entries.capacity() * size_of::<TieEntry>()
+ + entries
+ .iter()
+ .map(|e| {
+ e.row_indices.capacity() * size_of::<u32>() + e.batch_bytes
+ })
+ .sum::<usize>()
+ })
+ .sum();
+ table_overhead + contents
+ }
+}
+
+/// Sibling to [`PartitionedTopK`] / [`PartitionedTopKRank`] implementing
+/// `DENSE_RANK()` semantics.
+///
+/// Per partition, retains every row whose ORDER BY value is among the K
+/// distinct-smallest ob values seen for that partition. The total row
+/// count kept per partition is unbounded in `rows_per_distinct_value`
+/// (unlike `RANK`, which is bounded above by K + boundary ties).
+///
+/// Like [`PartitionedTopK`], the [`RowConverter`], [`MemoryReservation`],
+/// scratch [`Rows`] buffer, and [`TopKMetrics`] are shared across all
+/// partitions for this operator instance.
+///
+/// # Algorithm (per batch)
+///
+/// Evaluate + encode partition-by and order-by columns once, then group
+/// the batch's row indices by partition key. For each partition, bucket
+/// that partition's rows by distinct ob value (a within-call
+/// accumulation), then merge each bucket into the partition state. Every
+/// bucket is built from the current batch's rows, so each `TieEntry` is
+/// pinned to the batch its `row_indices` point into.
+///
+/// For each partition, for each distinct `ob_key` run in this batch:
+/// - `ob_key` already in `state.groups` → push this batch's run as a
+/// new `TieEntry` (one entry per contributing batch).
+/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
+/// group.
+/// - `ob_key` new, `state.groups.len() == k` → find the current max via
+/// an O(K) scan of `state.groups.keys()`:
+/// - `ob_key < max` → remove the max key (evict the entire max-key
+/// group — up to many rows) and insert the run. The evicted group's
+/// row count is added to the `row_replacements` metric.
+/// - `ob_key >= max` → drop the whole run; no map mutation.
+pub(crate) struct PartitionedTopKDenseRank {
+ 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,
+ /// Scratch row buffer for partition-key encoding. Reused across
+ /// `insert_batch` calls (cleared + appended each batch).
+ partition_scratch_rows: Rows,
+ /// One state per distinct partition key seen so far. Keyed by the
+ /// row-encoded PARTITION BY bytes (byte-comparable encoding, so the
+ /// `Vec<u8>` hashes, compares, and sorts identically to an
+ /// `OwnedRow`) which lets `insert_batch` look partitions up with
+ /// `entry_ref` — allocating a key only on first sight of a partition
+ /// rather than once per row.
+ states: HashMap<Vec<u8>, DenseRankPartitionState>,
+ /// Scratch map reused across `insert_batch` calls to group a batch's
+ /// row indices by partition key. Drained (not reallocated) each batch
+ /// so its backing table is allocated once, not per batch.
+ partition_groups: HashMap<Vec<u8>, Vec<u32>>,
+ /// Scratch map reused across partitions within a batch to bucket a
+ /// partition's rows by distinct ORDER BY value. Drained (not
+ /// reallocated) per partition so its backing table is allocated once,
+ /// not once per distinct partition key.
+ ob_runs: HashMap<Vec<u8>, Vec<u32>>,
+ k: usize,
+ batch_size: usize,
+}
+
+impl PartitionedTopKDenseRank {
+ #[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, "PartitionedTopKDenseRank requires k > 0");
+ let reservation =
+ MemoryConsumer::new(format!("PartitionedTopKDenseRank[{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)?;
+ let partition_scratch_rows = partition_converter
+ .empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
+
+ Ok(Self {
+ schema,
+ metrics: TopKMetrics::new(metrics, partition_id),
+ reservation,
+ expr: order_expr,
+ row_converter,
+ scratch_rows,
+ partition_exprs,
+ partition_converter,
+ partition_scratch_rows,
+ states: HashMap::new(),
+ partition_groups: HashMap::new(),
+ ob_runs: HashMap::new(),
+ k,
+ batch_size,
+ })
+ }
+
+ /// Encode PARTITION BY and ORDER BY columns once, demultiplex the
+ /// batch's rows by partition key, then per partition bucket the rows
+ /// by distinct ob value and merge each bucket into the partition
+ /// state as one [`TieEntry`].
+ 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(());
+ }
+
+ // Captured once so every `TieEntry` push from this batch can
+ // reuse it (avoids `get_record_batch_memory_size` per push).
+ let input_batch_bytes = get_record_batch_memory_size(batch);
+
+ // 1. 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<_>>()?;
+ self.partition_scratch_rows.clear();
+ self.partition_converter
+ .append(&mut self.partition_scratch_rows, &pk_arrays)?;
+
+ // 2. Group this batch's row indices by partition key.
+ // `partition_groups` is a reused scratch map: taken out here
+ // and drained below, so its backing table is allocated once
+ // for the operator, not once per batch. `entry_ref` owns the
+ // key only on Vacant, so it allocates one `Vec<u8>` per
+ // distinct partition rather than one per row.
+ let mut groups = std::mem::take(&mut self.partition_groups);
+ groups.clear();
+ {
+ let pk_rows = &self.partition_scratch_rows;
+ for i in 0..num_rows {
+ groups
+ .entry_ref(pk_rows.row(i).as_ref())
+ .or_default()
+ .push(i as u32);
+ }
+ }
+
+ // 3. Evaluate ORDER BY columns 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)?;
+
+ let k = self.k;
+ let mut replacements: usize = 0;
+
+ // 4. Per-partition: bucket this batch's rows by distinct ob value
+ // (within-call accumulation), then merge each bucket into the
+ // partition state as a single `TieEntry`.
+ for (pk, indices) in groups.drain() {
+ let state =
+ self.states
+ .entry(pk)
+ .or_insert_with(|| DenseRankPartitionState {
+ groups: HashMap::new(),
+ });
+
+ // Bucket by ob key. `ob_runs` is a reused scratch map (taken
+ // out and drained below) so its backing table is allocated
+ // once, not once per distinct partition key. `entry_ref` owns
+ // the key only on Vacant, so repeated rows of the same ob
+ // value don't re-allocate.
+ let mut runs = std::mem::take(&mut self.ob_runs);
+ runs.clear();
+ for &orig_idx in &indices {
+ let ob_row = self.scratch_rows.row(orig_idx as usize);
+ runs.entry_ref(ob_row.as_ref()).or_default().push(orig_idx);
+ }
+
+ for (ob_key, run_indices) in runs.drain() {
+ // Case A: ob already tracked — push this batch's run as a
+ // new `TieEntry` (one entry per contributing batch, exactly
+ // like RANK pushing one tie entry per batch).
+ if let Some(entries) = state.groups.get_mut(&ob_key) {
+ entries.push(TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ });
+ continue;
+ }
+
+ // Case B: new ob, room available.
+ if state.groups.len() < k {
+ state.groups.insert(
+ ob_key,
+ vec![TieEntry {
+ batch: batch.clone(),
+ row_indices: run_indices,
+ batch_bytes: input_batch_bytes,
+ }],
+ );
+ continue;
+ }
+
+ // Case C: new ob, at K distinct keys. Find the current
+ // max (K-th distinct-best) via an O(K) scan — cold path.
+ // Scoped so the immutable borrow ends before mutation.
+ let evict_key: Option<Vec<u8>> = {
+ let max_key = state
+ .groups
+ .keys()
+ .map(|key| key.as_slice())
+ .max()
Review Comment:
Finding the maximum scans all K keys for every new distinct value. On mostly distinct input this makes the rewrite O(N × K) and can be much slower for large K than the sort it replaces.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org