Skip to content

Commit 2c76116

Browse files
committed
PartitionedTopKDenseRank: scope emit's interleave batch slice per chunk
1 parent e580f21 commit 2c76116

1 file changed

Lines changed: 116 additions & 20 deletions

File tree

  • datafusion/physical-plan/src/topk

‎datafusion/physical-plan/src/topk/mod.rs‎

Lines changed: 116 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -2377,16 +2377,36 @@ impl PartitionedTopKDenseRank {
23772377
// order, ob values ascending within a partition, entries in
23782378
// insertion order within an ob value — so the interleaved output
23792379
// is already ordered and needs no post-sort.
2380-
let mut batch_refs = Vec::with_capacity(store.len());
2381-
let mut batch_id_pos = HashMap::with_capacity(store.len());
2382-
for (array_pos, (batch_id, entry)) in store.batches.iter().enumerate() {
2383-
batch_refs.push(&entry.batch);
2384-
batch_id_pos.insert(*batch_id, array_pos);
2385-
}
2380+
//
2381+
// `indices` carries the global `batch_id` rather than a position
2382+
// into a fixed `batch_refs` slice: for Dictionary columns,
2383+
// `interleave` does work proportional to the *number of input
2384+
// arrays*, not just the ones the indices reference, so passing
2385+
// every batch in the store on every chunk turns emit into
2386+
// O(chunks × total batches) instead of O(chunks × batches the
2387+
// chunk actually uses). Each chunk below rebuilds a batch slice
2388+
// scoped to just its own `batch_id`s.
2389+
let mut indices: Vec<(u32, usize)> = Vec::with_capacity(batch_size);
2390+
let mut flush = |indices: &mut Vec<(u32, usize)>| -> Result<()> {
2391+
let mut batch_refs = Vec::new();
2392+
let mut local_pos = HashMap::new();
2393+
let mut local_indices = Vec::with_capacity(indices.len());
2394+
for &(batch_id, row) in indices.iter() {
2395+
let pos = *local_pos.entry(batch_id).or_insert_with(|| {
2396+
batch_refs.push(&store.batches[&batch_id].batch);
2397+
batch_refs.len() - 1
2398+
});
2399+
local_indices.push((pos, row));
2400+
}
2401+
let b = interleave_record_batch(&batch_refs, &local_indices)?;
2402+
(&b).record_output(&metrics.baseline);
2403+
out.push(Ok(b));
2404+
indices.clear();
2405+
Ok(())
2406+
};
23862407

23872408
// Chunk at `batch_size` so the operator emits the same batch sizes
23882409
// as before and no single `interleave` output exceeds `batch_size`.
2389-
let mut indices: Vec<(usize, usize)> = Vec::with_capacity(batch_size);
23902410
for pk in sorted_pks {
23912411
let DenseRankPartitionState {
23922412
groups,
@@ -2400,23 +2420,17 @@ impl PartitionedTopKDenseRank {
24002420
sorted_obs.sort_by(|a, b| a.0.cmp(&b.0));
24012421
for (_ob, entries) in sorted_obs {
24022422
for entry in entries {
2403-
let array_pos = batch_id_pos[&entry.batch_id];
24042423
for row in entry.row_indices {
2405-
indices.push((array_pos, row as usize));
2424+
indices.push((entry.batch_id, row as usize));
24062425
if indices.len() == batch_size {
2407-
let b = interleave_record_batch(&batch_refs, &indices)?;
2408-
(&b).record_output(&metrics.baseline);
2409-
out.push(Ok(b));
2410-
indices.clear();
2426+
flush(&mut indices)?;
24112427
}
24122428
}
24132429
}
24142430
}
24152431
}
24162432
if !indices.is_empty() {
2417-
let b = interleave_record_batch(&batch_refs, &indices)?;
2418-
(&b).record_output(&metrics.baseline);
2419-
out.push(Ok(b));
2433+
flush(&mut indices)?;
24202434
}
24212435

24222436
Ok(Box::pin(RecordBatchStreamAdapter::new(
@@ -2460,8 +2474,11 @@ impl PartitionedTopKDenseRank {
24602474
mod tests {
24612475
use super::*;
24622476
use crate::metrics::MetricValue;
2463-
use arrow::array::{BooleanArray, Float64Array, Int32Array, StringArray};
2464-
use arrow::datatypes::{DataType, Field, Schema};
2477+
use arrow::array::{
2478+
AsArray, BooleanArray, Float64Array, Int32Array, StringArray,
2479+
StringDictionaryBuilder,
2480+
};
2481+
use arrow::datatypes::{DataType, Field, Int32Type, Schema};
24652482
use arrow_schema::SortOptions;
24662483
use datafusion_common::{assert_batches_eq, exec_datafusion_err};
24672484
use datafusion_execution::memory_pool::GreedyMemoryPool;
@@ -3480,8 +3497,8 @@ mod tests {
34803497
let batches: Vec<RecordBatch> = stream.try_collect().await?;
34813498
let mut rows: Vec<(i32, i32)> = Vec::new();
34823499
for b in &batches {
3483-
let pk = b.column(0).as_primitive::<arrow::datatypes::Int32Type>();
3484-
let val = b.column(1).as_primitive::<arrow::datatypes::Int32Type>();
3500+
let pk = b.column(0).as_primitive::<Int32Type>();
3501+
let val = b.column(1).as_primitive::<Int32Type>();
34853502
for i in 0..b.num_rows() {
34863503
rows.push((pk.value(i), val.value(i)));
34873504
}
@@ -4535,6 +4552,85 @@ mod tests {
45354552
Ok(())
45364553
}
45374554

4555+
/// Regression test for the `emit` rewrite: passing the *entire* store
4556+
/// to every `interleave_record_batch` call made Dictionary columns
4557+
/// O(chunks × total batches) instead of O(chunks × batches the chunk
4558+
/// actually uses), since `interleave_dictionaries` does per-input-array
4559+
/// work for every array it's handed. `batch_size` is 8, so 20 retained
4560+
/// rows spread across 2 source batches emit in 3 chunks — with several
4561+
/// chunks mixing rows from both source batches — the exact shape that
4562+
/// exercises the per-chunk batch-slice rebuild.
4563+
#[tokio::test]
4564+
async fn test_partitioned_topk_dense_rank_emit_dictionary_spans_chunks() -> Result<()>
4565+
{
4566+
let schema = Arc::new(Schema::new(vec![
4567+
Field::new("pk", DataType::Int32, false),
4568+
Field::new(
4569+
"val",
4570+
DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8)),
4571+
false,
4572+
),
4573+
]));
4574+
4575+
let pk_expr: Arc<dyn PhysicalExpr> = col("pk", schema.as_ref())?;
4576+
let partition_sort_fields = build_sort_fields(
4577+
&[PhysicalSortExpr {
4578+
expr: Arc::clone(&pk_expr),
4579+
options: SortOptions::default(),
4580+
}],
4581+
&schema,
4582+
)?;
4583+
let order_expr = LexOrdering::from([PhysicalSortExpr {
4584+
expr: col("val", schema.as_ref())?,
4585+
options: SortOptions::default(),
4586+
}]);
4587+
4588+
let mut state = PartitionedTopKDenseRank::try_new(
4589+
0,
4590+
Arc::clone(&schema),
4591+
vec![pk_expr],
4592+
partition_sort_fields,
4593+
order_expr,
4594+
20, // k: large enough to retain every distinct value below
4595+
8, // batch_size
4596+
&Arc::new(RuntimeEnv::default()),
4597+
&ExecutionPlanMetricsSet::new(),
4598+
)?;
4599+
4600+
let dict_batch = |vals: &[&str]| -> Result<RecordBatch> {
4601+
let mut builder = StringDictionaryBuilder::<Int32Type>::new();
4602+
for v in vals {
4603+
builder.append_value(v);
4604+
}
4605+
Ok(RecordBatch::try_new(
4606+
Arc::clone(&schema),
4607+
vec![
4608+
Arc::new(Int32Array::from(vec![1; vals.len()])),
4609+
Arc::new(builder.finish()),
4610+
],
4611+
)?)
4612+
};
4613+
4614+
// Two source batches (two distinct `batch_id`s), 10 distinct values
4615+
// each, all under a single partition key so every output chunk
4616+
// draws from both.
4617+
state.insert_batch(&dict_batch(&[
4618+
"v00", "v01", "v02", "v03", "v04", "v05", "v06", "v07", "v08", "v09",
4619+
])?)?;
4620+
state.insert_batch(&dict_batch(&[
4621+
"v10", "v11", "v12", "v13", "v14", "v15", "v16", "v17", "v18", "v19",
4622+
])?)?;
4623+
4624+
let results: Vec<_> = state.emit()?.try_collect().await?;
4625+
assert_eq!(results.iter().map(|b| b.num_rows()).sum::<usize>(), 20);
4626+
assert_eq!(results.len(), 3, "expected 3 chunks of batch_size=8");
4627+
let val_col = results[0].column(1).as_dictionary::<Int32Type>();
4628+
let dict_values = val_col.values().as_string::<i32>();
4629+
let first_val = dict_values.value(val_col.keys().value(0) as usize);
4630+
assert_eq!(first_val, "v00", "rows must still emit in ob-sorted order");
4631+
Ok(())
4632+
}
4633+
45384634
/// DENSE_RANK-specific: eviction removes the entire max group when
45394635
/// a strictly-smaller distinct ob arrives. Multiple rows at the
45404636
/// evicted key all disappear.

0 commit comments

Comments
 (0)