@@ -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+
198257impl 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