Skip to content

Commit 994b926

Browse files
authored
refactor: centralize TopK heap boundary handling (apache#23091)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> - Closes apache#23073. ## Rationale for this change TopK derives local heap-boundary data in multiple places. This refactor names that boundary and keeps full sort-key bytes, scalar threshold values, and prefix comparison tied to the same heap row. <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. --> ## What changes are included in this PR? - Add a private helper for the current local TopK heap boundary. - Use it when updating dynamic filter thresholds. - Use it for local prefix early-completion checks. - Remove the old duplicate scalar threshold extraction path. <!-- There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR. --> ## Are these changes tested? Yes <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> ## Are there any user-facing changes? No <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent 681ba9b commit 994b926

1 file changed

Lines changed: 114 additions & 81 deletions

File tree

  • datafusion/physical-plan/src/topk

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

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

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

489+
fn current_heap_boundary_row(&self) -> Option<TopKHeapBoundaryRow<'_>> {
490+
self.heap.max().map(TopKHeapBoundaryRow::new)
491+
}
492+
493+
fn current_heap_boundary(&self) -> Result<Option<TopKHeapBoundary<'_>>> {
494+
let Some(row) = self.heap.max() else {
495+
return Ok(None);
496+
};
497+
498+
self.heap_boundary(row).map(Some)
499+
}
500+
501+
fn heap_boundary<'a>(&'a self, row: &'a TopKRow) -> Result<TopKHeapBoundary<'a>> {
502+
let batch_entry = self
503+
.heap
504+
.store
505+
.get(row.batch_id)
506+
.ok_or_else(|| internal_datafusion_err!("Invalid batch ID in TopKRow"))?;
507+
508+
Ok(TopKHeapBoundary::new(row, &batch_entry.batch))
509+
}
510+
427511
/// Update the filter representation of our TopK heap.
428512
/// For example, given the sort expression `ORDER BY a DESC, b ASC LIMIT 3`,
429513
/// and the current heap values `[(1, 5), (1, 4), (2, 3)]`,
@@ -436,42 +520,31 @@ impl TopK {
436520
/// ```
437521
fn update_filter(&mut self) -> Result<()> {
438522
// If the heap doesn't have k elements yet, we can't create thresholds
439-
let Some(max_row) = self.heap.max() else {
523+
let Some(boundary_row) = self.current_heap_boundary_row() else {
440524
return Ok(());
441525
};
442526

443-
let new_threshold_row = max_row.row();
444-
445527
// Fast path: check if the current value in topk is better than what is
446528
// 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
529+
let needs_update = {
530+
let filter = self.filter.read();
531+
boundary_row.is_more_selective_than(filter.shared_threshold.as_ref())
532+
};
457533

458534
// exit early if the current values are better
459535
if !needs_update {
460536
return Ok(());
461537
}
462538

539+
let boundary = self.heap_boundary(boundary_row.row)?;
540+
463541
// 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-
};
542+
let thresholds = boundary.threshold_values(&self.expr)?;
468543

469544
// Build the filter expression OUTSIDE any synchronization
470545
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-
);
546+
let new_threshold =
547+
boundary.threshold(self.encode_topk_common_prefix_row(boundary)?);
475548

476549
// update the threshold. Since there was a lock gap, we must check if it is still the best
477550
// may have changed while we were building the expression without the lock
@@ -629,44 +702,45 @@ impl TopK {
629702
return Ok(());
630703
}
631704

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 {
634-
return Ok(());
635-
};
636-
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 {
705+
// Early exit only from the local heap once it has a full boundary row.
706+
let Some(boundary) = self.current_heap_boundary()? else {
641707
return Ok(());
642708
};
643709

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() {
710+
if self.batch_prefix_exceeds_heap_boundary(batch_common_prefix, boundary)? {
646711
self.finished = true;
647712
}
648713

649714
Ok(())
650715
}
651716

717+
fn batch_prefix_exceeds_heap_boundary(
718+
&self,
719+
batch_common_prefix: &[u8],
720+
boundary: TopKHeapBoundary<'_>,
721+
) -> Result<bool> {
722+
let Some(heap_common_prefix_row) =
723+
self.encode_topk_common_prefix_row(boundary)?
724+
else {
725+
return Ok(false);
726+
};
727+
728+
Ok(batch_common_prefix > heap_common_prefix_row.as_slice())
729+
}
730+
652731
fn encode_topk_common_prefix_row(
653732
&self,
654-
topk_row: &TopKRow,
733+
boundary: TopKHeapBoundary<'_>,
655734
) -> Result<Option<Vec<u8>>> {
656735
let Some(prefix_converter) = &self.common_sort_prefix_converter else {
657736
return Ok(None);
658737
};
659738

660-
let store_entry = self
661-
.heap
662-
.store
663-
.get(topk_row.batch_id)
664-
.ok_or(internal_datafusion_err!("Invalid batch id in topK heap"))?;
665739
let mut scratch = prefix_converter.empty_rows(1, ESTIMATED_BYTES_PER_ROW);
666740
self.append_common_prefix_row(
667741
prefix_converter,
668-
&store_entry.batch,
669-
topk_row.index,
742+
boundary.batch,
743+
boundary.row.index,
670744
&mut scratch,
671745
)?;
672746
Ok(Some(scratch.row(0).as_ref().to_vec()))
@@ -951,47 +1025,6 @@ impl TopKHeap {
9511025
+ self.store.size()
9521026
+ self.owned_bytes
9531027
}
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-
}
9951028
}
9961029

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

0 commit comments

Comments
 (0)