Skip to content

Commit 8bb2758

Browse files
authored
perf: skip wasted per-batch work in TopK insert_batch (apache#25657)
## Which issue does this PR close? - Related to apache#17098. ## Rationale for this change Once the TopK heap is full, most input batches are rejected outright by the threshold filter. `insert_batch` still evaluated every sort expression over the whole batch before checking the filter, then evaluated the same expressions again inside the filter, and cloned the batch even when nothing from it was kept. With an expression sort key that doubles the per-batch cost for no output. ## What changes are included in this PR? - The threshold filter runs before the sort keys are evaluated; fully rejected batches skip sort-key evaluation. - The batch moves into the heap entry instead of being cloned. The last row's common prefix is encoded before the move so early completion still compares against the same boundary at the same point. - The per-batch timer clones one metric instead of the whole baseline set, here and in `PartitionedTopK`, `PartitionedTopKRank`, and `PartitionedTopKDenseRank`. `SELECT l_orderkey, l_extendedprice FROM lineitem ORDER BY l_extendedprice + 0 DESC LIMIT 1` on TPC-H SF1, TopK `elapsed_compute`, median of five: 152 ms before, 94 ms after. `sort-tpch --limit 10` shows no change. One nuance: a sort-key expression that errors only on rows the threshold already rejects no longer raises, because those batches skip sort-key evaluation. The filter evaluates the same expression over the batch first, so this can only differ for a secondary key under short-circuit evaluation. ## What is the testing strategy for this PR? New unit tests in `datafusion/physical-plan/src/topk`: `test_batch_rejected_by_threshold_leaves_heap_untouched` and `test_expression_sort_key_matches_column_sort_key`. Existing TopK tests and the `topk`, `window` and `limit` sqllogictest files pass unchanged. ## Are there any user-facing changes? No.
1 parent 991fd23 commit 8bb2758

1 file changed

Lines changed: 231 additions & 24 deletions

File tree

  • datafusion/physical-plan/src/topk

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

Lines changed: 231 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -393,20 +393,10 @@ impl TopK {
393393

394394
/// Insert `batch`, remembering if any of its values are among
395395
/// the top k seen so far.
396-
#[expect(clippy::needless_pass_by_value)]
397396
pub fn insert_batch(&mut self, batch: RecordBatch) -> Result<()> {
398397
// Updates on drop
399-
let baseline = self.metrics.baseline.clone();
400-
let _timer = baseline.elapsed_compute().timer();
401-
402-
let mut sort_keys: Vec<ArrayRef> = self
403-
.expr
404-
.iter()
405-
.map(|expr| {
406-
let value = expr.expr.evaluate(&batch)?;
407-
value.into_array(batch.num_rows())
408-
})
409-
.collect::<Result<Vec<_>>>()?;
398+
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
399+
let _timer = elapsed_compute.timer();
410400

411401
let mut selected_rows = None;
412402

@@ -422,6 +412,17 @@ impl TopK {
422412
self.attempt_early_completion(&batch)?;
423413
return Ok(());
424414
}
415+
416+
// Sort keys are only needed once some row passes the threshold
417+
let mut sort_keys: Vec<ArrayRef> = self
418+
.expr
419+
.iter()
420+
.map(|expr| {
421+
let value = expr.expr.evaluate(&batch)?;
422+
value.into_array(num_rows)
423+
})
424+
.collect::<Result<Vec<_>>>()?;
425+
425426
// only update the keys / rows if the filter does not match all rows
426427
if filter.null_count() > 0 || filter.has_false() {
427428
// Indices in `set_indices` should be correct if filter contains nulls
@@ -449,7 +450,7 @@ impl TopK {
449450
rows.clear();
450451
self.row_converter.append(rows, &sort_keys)?;
451452

452-
let mut batch_entry = self.heap.register_batch(batch.clone());
453+
let mut batch_entry = self.heap.register_batch(batch);
453454

454455
let replacements = match selected_rows {
455456
Some(filter) => {
@@ -461,6 +462,10 @@ impl TopK {
461462
if replacements > 0 {
462463
self.metrics.row_replacements.add(replacements);
463464

465+
// The heap takes ownership of the batch (and compaction may drop
466+
// it), so encode its last row's prefix while it is still at hand.
467+
let last_row_prefix = self.last_row_common_prefix(&batch_entry.batch)?;
468+
464469
self.heap.insert_batch_entry(batch_entry);
465470

466471
// conserve memory
@@ -472,14 +477,14 @@ impl TopK {
472477
// flag the topK as finished if we know that all
473478
// subsequent batches are guaranteed to be greater (by byte order, after row conversion) than the top K,
474479
// which means the top K won't change and the computation can be finished early.
475-
self.attempt_early_completion(&batch)?;
480+
self.finish_if_prefix_past_boundary(last_row_prefix.as_ref())?;
476481

477482
// update the filter representation of our TopK heap
478483
self.update_filter()?;
479484
} else {
480485
// The heap did not change, but this batch's prefix may still prove
481486
// that no later rows can enter the TopK.
482-
self.attempt_early_completion(&batch)?;
487+
self.attempt_early_completion(&batch_entry.batch)?;
483488
}
484489

485490
Ok(())
@@ -685,15 +690,24 @@ impl TopK {
685690
/// greater than either the shared dynamic-filter threshold prefix or the max
686691
/// row in the local heap, comparing only on the shared prefix columns.
687692
fn attempt_early_completion(&mut self, batch: &RecordBatch) -> Result<()> {
693+
let last_row_prefix = self.last_row_common_prefix(batch)?;
694+
self.finish_if_prefix_past_boundary(last_row_prefix.as_ref())
695+
}
696+
697+
/// Encodes the shared sort prefix of the last row of `batch`.
698+
///
699+
/// Returns `None` when the batch is empty (there is no last row) or when
700+
/// the input ordering shares no prefix with the TopK.
701+
fn last_row_common_prefix(&self, batch: &RecordBatch) -> Result<Option<Rows>> {
688702
// Early exit if the batch is empty as there is no last row to extract from it.
689703
if batch.num_rows() == 0 {
690-
return Ok(());
704+
return Ok(None);
691705
}
692706

693707
// common_prefix_row_converter is only `Some` if the input ordering has a common prefix with the TopK,
694708
// so early exit if it is `None`.
695709
let Some(prefix_converter) = &self.common_sort_prefix_converter else {
696-
return Ok(());
710+
return Ok(None);
697711
};
698712

699713
// Evaluate the prefix for the last row of the current batch.
@@ -707,7 +721,19 @@ impl TopK {
707721
last_row_idx,
708722
&mut batch_prefix_scratch,
709723
)?;
710-
let batch_common_prefix_row = batch_prefix_scratch.row(0);
724+
Ok(Some(batch_prefix_scratch))
725+
}
726+
727+
/// Marks the TopK finished when a batch's last-row prefix, as produced by
728+
/// [`Self::last_row_common_prefix`], lies past the shared or local boundary.
729+
fn finish_if_prefix_past_boundary(
730+
&mut self,
731+
last_row_prefix: Option<&Rows>,
732+
) -> Result<()> {
733+
let Some(batch_prefix_rows) = last_row_prefix else {
734+
return Ok(());
735+
};
736+
let batch_common_prefix_row = batch_prefix_rows.row(0);
711737
let batch_common_prefix = batch_common_prefix_row.as_ref();
712738

713739
let finished_by_shared_threshold = self
@@ -1338,8 +1364,8 @@ impl PartitionedTopK {
13381364
/// columns once for the whole batch, and feed each partition's
13391365
/// rows into its dedicated [`TopKHeap`].
13401366
pub(crate) fn insert_batch(&mut self, batch: &RecordBatch) -> Result<()> {
1341-
let baseline = self.metrics.baseline.clone();
1342-
let _timer = baseline.elapsed_compute().timer();
1367+
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
1368+
let _timer = elapsed_compute.timer();
13431369

13441370
let num_rows = batch.num_rows();
13451371
if num_rows == 0 {
@@ -1655,8 +1681,8 @@ impl PartitionedTopKRank {
16551681
/// rows through the rank classifier into its dedicated heap and
16561682
/// ties Vec.
16571683
pub(crate) fn insert_batch(&mut self, batch: &RecordBatch) -> Result<()> {
1658-
let baseline = self.metrics.baseline.clone();
1659-
let _timer = baseline.elapsed_compute().timer();
1684+
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
1685+
let _timer = elapsed_compute.timer();
16601686

16611687
let num_rows = batch.num_rows();
16621688
if num_rows == 0 {
@@ -2152,8 +2178,8 @@ impl PartitionedTopKDenseRank {
21522178
/// by distinct ob value and merge each bucket into the partition
21532179
/// state as one [`GroupEntry`].
21542180
pub(crate) fn insert_batch(&mut self, batch: &RecordBatch) -> Result<()> {
2155-
let baseline = self.metrics.baseline.clone();
2156-
let _timer = baseline.elapsed_compute().timer();
2181+
let elapsed_compute = self.metrics.baseline.elapsed_compute().clone();
2182+
let _timer = elapsed_compute.timer();
21572183

21582184
let num_rows = batch.num_rows();
21592185
if num_rows == 0 {
@@ -2775,6 +2801,187 @@ mod tests {
27752801
Ok(())
27762802
}
27772803

2804+
/// An empty batch has no last row to prove early completion with, so it
2805+
/// must leave the TopK unchanged, both with an empty heap and a full one.
2806+
#[tokio::test]
2807+
async fn test_empty_batch_with_prefix_does_not_finish() -> Result<()> {
2808+
let schema = make_ab_schema();
2809+
let mut topk = make_ab_topk(Arc::clone(&schema), make_topk_filter())?;
2810+
let empty = RecordBatch::new_empty(Arc::clone(&schema));
2811+
2812+
topk.insert_batch(empty.clone())?;
2813+
assert!(!topk.finished);
2814+
assert_eq!(topk.heap.store.len(), 0);
2815+
2816+
topk.insert_batch(make_ab_batch(
2817+
Arc::clone(&schema),
2818+
&[Some(1), Some(1), Some(2)],
2819+
&[20.0, 15.0, 30.0],
2820+
)?)?;
2821+
let heap_before = heap_snapshot(&topk);
2822+
let store_len_before = topk.heap.store.len();
2823+
2824+
topk.insert_batch(empty)?;
2825+
assert!(!topk.finished);
2826+
assert_eq!(heap_snapshot(&topk), heap_before);
2827+
assert_eq!(topk.heap.store.len(), store_len_before);
2828+
2829+
let results: Vec<_> = topk.emit()?.try_collect().await?;
2830+
assert_batches_eq!(
2831+
&[
2832+
"+---+------+",
2833+
"| a | b |",
2834+
"+---+------+",
2835+
"| 1 | 15.0 |",
2836+
"| 1 | 20.0 |",
2837+
"| 2 | 30.0 |",
2838+
"+---+------+",
2839+
],
2840+
&results
2841+
);
2842+
2843+
Ok(())
2844+
}
2845+
2846+
/// Builds a `k = 3` TopK over `(a, b)` sorted by the single key `expr`,
2847+
/// with no input sort prefix.
2848+
fn make_single_key_topk(
2849+
schema: SchemaRef,
2850+
expr: Arc<dyn PhysicalExpr>,
2851+
metrics: &ExecutionPlanMetricsSet,
2852+
) -> Result<TopK> {
2853+
TopK::try_new(
2854+
0,
2855+
schema,
2856+
vec![],
2857+
LexOrdering::from([PhysicalSortExpr {
2858+
expr,
2859+
options: SortOptions::default(),
2860+
}]),
2861+
3,
2862+
2,
2863+
Arc::new(RuntimeEnv::default()),
2864+
metrics,
2865+
make_topk_filter(),
2866+
)
2867+
}
2868+
2869+
fn heap_snapshot(topk: &TopK) -> Vec<(Vec<u8>, u32, usize)> {
2870+
topk.heap
2871+
.inner
2872+
.iter()
2873+
.map(|r| (r.row.clone(), r.batch_id, r.index))
2874+
.collect()
2875+
}
2876+
2877+
#[tokio::test]
2878+
async fn test_batch_rejected_by_threshold_leaves_heap_untouched() -> Result<()> {
2879+
let schema = make_ab_schema();
2880+
let metrics = ExecutionPlanMetricsSet::new();
2881+
let mut topk =
2882+
make_single_key_topk(Arc::clone(&schema), col("a", &schema)?, &metrics)?;
2883+
2884+
topk.insert_batch(make_ab_batch(
2885+
Arc::clone(&schema),
2886+
&[Some(3), Some(1), Some(2)],
2887+
&[0.0, 1.0, 2.0],
2888+
)?)?;
2889+
2890+
let rejected = make_ab_batch(
2891+
Arc::clone(&schema),
2892+
&[Some(7), Some(5), Some(9)],
2893+
&[3.0, 4.0, 5.0],
2894+
)?;
2895+
// The heap is full, so the threshold must now reject every row.
2896+
let threshold = topk.filter.read().expr.current()?;
2897+
let passing = threshold
2898+
.evaluate(&rejected)?
2899+
.into_array(rejected.num_rows())?;
2900+
assert!(!passing.as_boolean().has_true());
2901+
2902+
let heap_before = heap_snapshot(&topk);
2903+
let store_len_before = topk.heap.store.len();
2904+
let replacements_before = topk.metrics.row_replacements.value();
2905+
2906+
topk.insert_batch(rejected)?;
2907+
2908+
assert_eq!(heap_snapshot(&topk), heap_before);
2909+
assert_eq!(topk.heap.store.len(), store_len_before);
2910+
assert_eq!(topk.metrics.row_replacements.value(), replacements_before);
2911+
2912+
let results: Vec<_> = topk.emit()?.try_collect().await?;
2913+
assert_batches_eq!(
2914+
&[
2915+
"+---+-----+",
2916+
"| a | b |",
2917+
"+---+-----+",
2918+
"| 1 | 1.0 |",
2919+
"| 2 | 2.0 |",
2920+
"| 3 | 0.0 |",
2921+
"+---+-----+",
2922+
],
2923+
&results
2924+
);
2925+
2926+
Ok(())
2927+
}
2928+
2929+
#[tokio::test]
2930+
async fn test_expression_sort_key_matches_column_sort_key() -> Result<()> {
2931+
let schema = make_ab_schema();
2932+
let column_metrics = ExecutionPlanMetricsSet::new();
2933+
let expr_metrics = ExecutionPlanMetricsSet::new();
2934+
let mut by_column = make_single_key_topk(
2935+
Arc::clone(&schema),
2936+
col("a", &schema)?,
2937+
&column_metrics,
2938+
)?;
2939+
let a_plus_one = Arc::new(BinaryExpr::new(
2940+
col("a", &schema)?,
2941+
Operator::Plus,
2942+
lit(1i32),
2943+
));
2944+
let mut by_expr =
2945+
make_single_key_topk(Arc::clone(&schema), a_plus_one, &expr_metrics)?;
2946+
2947+
let inputs: [&[Option<i32>]; 4] = [
2948+
&[Some(8), Some(5), Some(9)],
2949+
&[Some(4), Some(10), Some(2)],
2950+
&[Some(11), Some(12)],
2951+
&[Some(6), Some(1), Some(7)],
2952+
];
2953+
for a in inputs {
2954+
let b: Vec<f64> = a.iter().map(|v| f64::from(v.unwrap()) / 2.0).collect();
2955+
let batch = make_ab_batch(Arc::clone(&schema), a, &b)?;
2956+
by_column.insert_batch(batch.clone())?;
2957+
by_expr.insert_batch(batch)?;
2958+
assert_eq!(
2959+
by_expr.metrics.row_replacements.value(),
2960+
by_column.metrics.row_replacements.value()
2961+
);
2962+
}
2963+
2964+
let column_results: Vec<_> = by_column.emit()?.try_collect().await?;
2965+
let expr_results: Vec<_> = by_expr.emit()?.try_collect().await?;
2966+
let expected = [
2967+
"+---+-----+",
2968+
"| a | b |",
2969+
"+---+-----+",
2970+
"| 1 | 0.5 |",
2971+
"| 2 | 1.0 |",
2972+
"| 4 | 2.0 |",
2973+
"+---+-----+",
2974+
];
2975+
assert_batches_eq!(expected, &column_results);
2976+
assert_batches_eq!(expected, &expr_results);
2977+
assert_eq!(
2978+
output_batches_and_rows(&expr_metrics),
2979+
output_batches_and_rows(&column_metrics)
2980+
);
2981+
2982+
Ok(())
2983+
}
2984+
27782985
struct SharedPrefixCase {
27792986
name: &'static str,
27802987
a_nullable: bool,

0 commit comments

Comments
 (0)