@@ -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