Skip to content

Commit 2a96e34

Browse files
committed
refactor: centralize TopK heap boundary handling
1 parent 9e68a86 commit 2a96e34

1 file changed

Lines changed: 88 additions & 73 deletions

File tree

  • datafusion/physical-plan/src/topk

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

Lines changed: 88 additions & 73 deletions
Original file line numberDiff line numberDiff line change
@@ -195,6 +195,65 @@ impl TopKThreshold {
195195
}
196196
}
197197

198+
#[derive(Clone, Copy)]
199+
struct TopKHeapBoundary<'a> {
200+
row: &'a TopKRow,
201+
}
202+
203+
impl<'a> TopKHeapBoundary<'a> {
204+
fn new(row: &'a TopKRow) -> Self {
205+
Self { row }
206+
}
207+
208+
fn row(&self) -> &'a TopKRow {
209+
self.row
210+
}
211+
212+
fn full_sort_key_row(&self) -> &[u8] {
213+
self.row.row()
214+
}
215+
216+
fn is_more_selective_than(&self, current: Option<&TopKThreshold>) -> bool {
217+
current
218+
.map(|current| self.full_sort_key_row() < current.full_sort_key_row())
219+
.unwrap_or(true)
220+
}
221+
222+
fn threshold_values(
223+
&self,
224+
heap: &TopKHeap,
225+
sort_exprs: &[PhysicalSortExpr],
226+
) -> Result<Vec<ScalarValue>> {
227+
let batch_entry = heap
228+
.store
229+
.get(self.row.batch_id)
230+
.ok_or(internal_datafusion_err!("Invalid batch ID in TopKRow"))?;
231+
232+
let mut scalar_values = Vec::with_capacity(sort_exprs.len());
233+
for sort_expr in sort_exprs {
234+
let expr = Arc::clone(&sort_expr.expr);
235+
let value = expr.evaluate(&batch_entry.batch.slice(self.row.index, 1))?;
236+
237+
let scalar = match value {
238+
ColumnarValue::Scalar(scalar) => scalar,
239+
ColumnarValue::Array(array) if array.len() == 1 => {
240+
ScalarValue::try_from_array(&array, 0)?
241+
}
242+
array => {
243+
return internal_err!("Expected a scalar value, got {:?}", array);
244+
}
245+
};
246+
scalar_values.push(scalar);
247+
}
248+
249+
Ok(scalar_values)
250+
}
251+
252+
fn threshold(&self, common_prefix_row: Option<Vec<u8>>) -> TopKThreshold {
253+
TopKThreshold::new(self.full_sort_key_row().to_vec(), common_prefix_row)
254+
}
255+
}
256+
198257
impl TopKDynamicFilters {
199258
/// Create a new `TopKDynamicFilters` with the given expression
200259
pub fn new(expr: Arc<DynamicFilterPhysicalExpr>) -> Self {
@@ -424,6 +483,10 @@ impl TopK {
424483
replacements
425484
}
426485

486+
fn current_heap_boundary(&self) -> Option<TopKHeapBoundary<'_>> {
487+
self.heap.max().map(TopKHeapBoundary::new)
488+
}
489+
427490
/// Update the filter representation of our TopK heap.
428491
/// For example, given the sort expression `ORDER BY a DESC, b ASC LIMIT 3`,
429492
/// and the current heap values `[(1, 5), (1, 4), (2, 3)]`,
@@ -436,42 +499,29 @@ impl TopK {
436499
/// ```
437500
fn update_filter(&mut self) -> Result<()> {
438501
// If the heap doesn't have k elements yet, we can't create thresholds
439-
let Some(max_row) = self.heap.max() else {
502+
let Some(boundary) = self.current_heap_boundary() else {
440503
return Ok(());
441504
};
442505

443-
let new_threshold_row = max_row.row();
444-
445506
// Fast path: check if the current value in topk is better than what is
446507
// currently set in the filter with a read only lock
447-
let needs_update = self
448-
.filter
449-
.read()
450-
.shared_threshold
451-
.as_ref()
452-
.map(|current_threshold| {
453-
// new < current means new threshold is more selective
454-
new_threshold_row < current_threshold.full_sort_key_row()
455-
})
456-
.unwrap_or(true); // No current threshold, so we need to set one
508+
let needs_update = {
509+
let filter = self.filter.read();
510+
boundary.is_more_selective_than(filter.shared_threshold.as_ref())
511+
};
457512

458513
// exit early if the current values are better
459514
if !needs_update {
460515
return Ok(());
461516
}
462517

463518
// Extract scalar values BEFORE acquiring lock to reduce critical section
464-
let thresholds = match self.heap.get_threshold_values(&self.expr)? {
465-
Some(t) => t,
466-
None => return Ok(()),
467-
};
519+
let thresholds = boundary.threshold_values(&self.heap, &self.expr)?;
468520

469521
// Build the filter expression OUTSIDE any synchronization
470522
let predicate = Self::build_filter_expression(&self.expr, &thresholds)?;
471-
let new_threshold = TopKThreshold::new(
472-
new_threshold_row.to_vec(),
473-
self.encode_topk_common_prefix_row(max_row)?,
474-
);
523+
let new_threshold =
524+
boundary.threshold(self.encode_topk_common_prefix_row(boundary.row())?);
475525

476526
// update the threshold. Since there was a lock gap, we must check if it is still the best
477527
// may have changed while we were building the expression without the lock
@@ -629,26 +679,32 @@ impl TopK {
629679
return Ok(());
630680
}
631681

632-
// Early exit if the heap is not full (`heap.max()` only returns `Some` if the heap is full).
633-
let Some(max_topk_row) = self.heap.max() else {
682+
// Early exit only from the local heap once it has a full boundary row.
683+
let Some(boundary) = self.current_heap_boundary() else {
634684
return Ok(());
635685
};
636686

637-
// Encode the local heap max row's common-prefix projection.
638-
let Some(heap_common_prefix_row) =
639-
self.encode_topk_common_prefix_row(max_topk_row)?
640-
else {
641-
return Ok(());
642-
};
643-
644-
// If the last row's prefix is strictly greater than the max prefix, mark as finished.
645-
if batch_common_prefix > heap_common_prefix_row.as_slice() {
687+
if self.batch_prefix_exceeds_heap_boundary(batch_common_prefix, boundary)? {
646688
self.finished = true;
647689
}
648690

649691
Ok(())
650692
}
651693

694+
fn batch_prefix_exceeds_heap_boundary(
695+
&self,
696+
batch_common_prefix: &[u8],
697+
boundary: TopKHeapBoundary<'_>,
698+
) -> Result<bool> {
699+
let Some(heap_common_prefix_row) =
700+
self.encode_topk_common_prefix_row(boundary.row())?
701+
else {
702+
return Ok(false);
703+
};
704+
705+
Ok(batch_common_prefix > heap_common_prefix_row.as_slice())
706+
}
707+
652708
fn encode_topk_common_prefix_row(
653709
&self,
654710
topk_row: &TopKRow,
@@ -951,47 +1007,6 @@ impl TopKHeap {
9511007
+ self.store.size()
9521008
+ self.owned_bytes
9531009
}
954-
955-
fn get_threshold_values(
956-
&self,
957-
sort_exprs: &[PhysicalSortExpr],
958-
) -> Result<Option<Vec<ScalarValue>>> {
959-
// If the heap doesn't have k elements yet, we can't create thresholds
960-
let max_row = match self.max() {
961-
Some(row) => row,
962-
None => return Ok(None),
963-
};
964-
965-
// Get the batch that contains the max row
966-
let batch_entry = match self.store.get(max_row.batch_id) {
967-
Some(entry) => entry,
968-
None => return internal_err!("Invalid batch ID in TopKRow"),
969-
};
970-
971-
// Extract threshold values for each sort expression
972-
let mut scalar_values = Vec::with_capacity(sort_exprs.len());
973-
for sort_expr in sort_exprs {
974-
// Extract the value for this column from the max row
975-
let expr = Arc::clone(&sort_expr.expr);
976-
let value = expr.evaluate(&batch_entry.batch.slice(max_row.index, 1))?;
977-
978-
// Convert to scalar value - should be a single value since we're evaluating on a single row batch
979-
let scalar = match value {
980-
ColumnarValue::Scalar(scalar) => scalar,
981-
ColumnarValue::Array(array) if array.len() == 1 => {
982-
// Extract the first (and only) value from the array
983-
ScalarValue::try_from_array(&array, 0)?
984-
}
985-
array => {
986-
return internal_err!("Expected a scalar value, got {:?}", array);
987-
}
988-
};
989-
990-
scalar_values.push(scalar);
991-
}
992-
993-
Ok(Some(scalar_values))
994-
}
9951010
}
9961011

9971012
/// Represents one of the top K rows held in this heap. Orders

0 commit comments

Comments
 (0)