@@ -2377,16 +2377,36 @@ impl PartitionedTopKDenseRank {
23772377 // order, ob values ascending within a partition, entries in
23782378 // insertion order within an ob value — so the interleaved output
23792379 // is already ordered and needs no post-sort.
2380- let mut batch_refs = Vec :: with_capacity ( store. len ( ) ) ;
2381- let mut batch_id_pos = HashMap :: with_capacity ( store. len ( ) ) ;
2382- for ( array_pos, ( batch_id, entry) ) in store. batches . iter ( ) . enumerate ( ) {
2383- batch_refs. push ( & entry. batch ) ;
2384- batch_id_pos. insert ( * batch_id, array_pos) ;
2385- }
2380+ //
2381+ // `indices` carries the global `batch_id` rather than a position
2382+ // into a fixed `batch_refs` slice: for Dictionary columns,
2383+ // `interleave` does work proportional to the *number of input
2384+ // arrays*, not just the ones the indices reference, so passing
2385+ // every batch in the store on every chunk turns emit into
2386+ // O(chunks × total batches) instead of O(chunks × batches the
2387+ // chunk actually uses). Each chunk below rebuilds a batch slice
2388+ // scoped to just its own `batch_id`s.
2389+ let mut indices: Vec < ( u32 , usize ) > = Vec :: with_capacity ( batch_size) ;
2390+ let mut flush = |indices : & mut Vec < ( u32 , usize ) > | -> Result < ( ) > {
2391+ let mut batch_refs = Vec :: new ( ) ;
2392+ let mut local_pos = HashMap :: new ( ) ;
2393+ let mut local_indices = Vec :: with_capacity ( indices. len ( ) ) ;
2394+ for & ( batch_id, row) in indices. iter ( ) {
2395+ let pos = * local_pos. entry ( batch_id) . or_insert_with ( || {
2396+ batch_refs. push ( & store. batches [ & batch_id] . batch ) ;
2397+ batch_refs. len ( ) - 1
2398+ } ) ;
2399+ local_indices. push ( ( pos, row) ) ;
2400+ }
2401+ let b = interleave_record_batch ( & batch_refs, & local_indices) ?;
2402+ ( & b) . record_output ( & metrics. baseline ) ;
2403+ out. push ( Ok ( b) ) ;
2404+ indices. clear ( ) ;
2405+ Ok ( ( ) )
2406+ } ;
23862407
23872408 // Chunk at `batch_size` so the operator emits the same batch sizes
23882409 // as before and no single `interleave` output exceeds `batch_size`.
2389- let mut indices: Vec < ( usize , usize ) > = Vec :: with_capacity ( batch_size) ;
23902410 for pk in sorted_pks {
23912411 let DenseRankPartitionState {
23922412 groups,
@@ -2400,23 +2420,17 @@ impl PartitionedTopKDenseRank {
24002420 sorted_obs. sort_by ( |a, b| a. 0 . cmp ( & b. 0 ) ) ;
24012421 for ( _ob, entries) in sorted_obs {
24022422 for entry in entries {
2403- let array_pos = batch_id_pos[ & entry. batch_id ] ;
24042423 for row in entry. row_indices {
2405- indices. push ( ( array_pos , row as usize ) ) ;
2424+ indices. push ( ( entry . batch_id , row as usize ) ) ;
24062425 if indices. len ( ) == batch_size {
2407- let b = interleave_record_batch ( & batch_refs, & indices) ?;
2408- ( & b) . record_output ( & metrics. baseline ) ;
2409- out. push ( Ok ( b) ) ;
2410- indices. clear ( ) ;
2426+ flush ( & mut indices) ?;
24112427 }
24122428 }
24132429 }
24142430 }
24152431 }
24162432 if !indices. is_empty ( ) {
2417- let b = interleave_record_batch ( & batch_refs, & indices) ?;
2418- ( & b) . record_output ( & metrics. baseline ) ;
2419- out. push ( Ok ( b) ) ;
2433+ flush ( & mut indices) ?;
24202434 }
24212435
24222436 Ok ( Box :: pin ( RecordBatchStreamAdapter :: new (
@@ -2460,8 +2474,11 @@ impl PartitionedTopKDenseRank {
24602474mod tests {
24612475 use super :: * ;
24622476 use crate :: metrics:: MetricValue ;
2463- use arrow:: array:: { BooleanArray , Float64Array , Int32Array , StringArray } ;
2464- use arrow:: datatypes:: { DataType , Field , Schema } ;
2477+ use arrow:: array:: {
2478+ AsArray , BooleanArray , Float64Array , Int32Array , StringArray ,
2479+ StringDictionaryBuilder ,
2480+ } ;
2481+ use arrow:: datatypes:: { DataType , Field , Int32Type , Schema } ;
24652482 use arrow_schema:: SortOptions ;
24662483 use datafusion_common:: { assert_batches_eq, exec_datafusion_err} ;
24672484 use datafusion_execution:: memory_pool:: GreedyMemoryPool ;
@@ -3480,8 +3497,8 @@ mod tests {
34803497 let batches: Vec < RecordBatch > = stream. try_collect ( ) . await ?;
34813498 let mut rows: Vec < ( i32 , i32 ) > = Vec :: new ( ) ;
34823499 for b in & batches {
3483- let pk = b. column ( 0 ) . as_primitive :: < arrow :: datatypes :: Int32Type > ( ) ;
3484- let val = b. column ( 1 ) . as_primitive :: < arrow :: datatypes :: Int32Type > ( ) ;
3500+ let pk = b. column ( 0 ) . as_primitive :: < Int32Type > ( ) ;
3501+ let val = b. column ( 1 ) . as_primitive :: < Int32Type > ( ) ;
34853502 for i in 0 ..b. num_rows ( ) {
34863503 rows. push ( ( pk. value ( i) , val. value ( i) ) ) ;
34873504 }
@@ -4535,6 +4552,85 @@ mod tests {
45354552 Ok ( ( ) )
45364553 }
45374554
4555+ /// Regression test for the `emit` rewrite: passing the *entire* store
4556+ /// to every `interleave_record_batch` call made Dictionary columns
4557+ /// O(chunks × total batches) instead of O(chunks × batches the chunk
4558+ /// actually uses), since `interleave_dictionaries` does per-input-array
4559+ /// work for every array it's handed. `batch_size` is 8, so 20 retained
4560+ /// rows spread across 2 source batches emit in 3 chunks — with several
4561+ /// chunks mixing rows from both source batches — the exact shape that
4562+ /// exercises the per-chunk batch-slice rebuild.
4563+ #[ tokio:: test]
4564+ async fn test_partitioned_topk_dense_rank_emit_dictionary_spans_chunks ( ) -> Result < ( ) >
4565+ {
4566+ let schema = Arc :: new ( Schema :: new ( vec ! [
4567+ Field :: new( "pk" , DataType :: Int32 , false ) ,
4568+ Field :: new(
4569+ "val" ,
4570+ DataType :: Dictionary ( Box :: new( DataType :: Int32 ) , Box :: new( DataType :: Utf8 ) ) ,
4571+ false ,
4572+ ) ,
4573+ ] ) ) ;
4574+
4575+ let pk_expr: Arc < dyn PhysicalExpr > = col ( "pk" , schema. as_ref ( ) ) ?;
4576+ let partition_sort_fields = build_sort_fields (
4577+ & [ PhysicalSortExpr {
4578+ expr : Arc :: clone ( & pk_expr) ,
4579+ options : SortOptions :: default ( ) ,
4580+ } ] ,
4581+ & schema,
4582+ ) ?;
4583+ let order_expr = LexOrdering :: from ( [ PhysicalSortExpr {
4584+ expr : col ( "val" , schema. as_ref ( ) ) ?,
4585+ options : SortOptions :: default ( ) ,
4586+ } ] ) ;
4587+
4588+ let mut state = PartitionedTopKDenseRank :: try_new (
4589+ 0 ,
4590+ Arc :: clone ( & schema) ,
4591+ vec ! [ pk_expr] ,
4592+ partition_sort_fields,
4593+ order_expr,
4594+ 20 , // k: large enough to retain every distinct value below
4595+ 8 , // batch_size
4596+ & Arc :: new ( RuntimeEnv :: default ( ) ) ,
4597+ & ExecutionPlanMetricsSet :: new ( ) ,
4598+ ) ?;
4599+
4600+ let dict_batch = |vals : & [ & str ] | -> Result < RecordBatch > {
4601+ let mut builder = StringDictionaryBuilder :: < Int32Type > :: new ( ) ;
4602+ for v in vals {
4603+ builder. append_value ( v) ;
4604+ }
4605+ Ok ( RecordBatch :: try_new (
4606+ Arc :: clone ( & schema) ,
4607+ vec ! [
4608+ Arc :: new( Int32Array :: from( vec![ 1 ; vals. len( ) ] ) ) ,
4609+ Arc :: new( builder. finish( ) ) ,
4610+ ] ,
4611+ ) ?)
4612+ } ;
4613+
4614+ // Two source batches (two distinct `batch_id`s), 10 distinct values
4615+ // each, all under a single partition key so every output chunk
4616+ // draws from both.
4617+ state. insert_batch ( & dict_batch ( & [
4618+ "v00" , "v01" , "v02" , "v03" , "v04" , "v05" , "v06" , "v07" , "v08" , "v09" ,
4619+ ] ) ?) ?;
4620+ state. insert_batch ( & dict_batch ( & [
4621+ "v10" , "v11" , "v12" , "v13" , "v14" , "v15" , "v16" , "v17" , "v18" , "v19" ,
4622+ ] ) ?) ?;
4623+
4624+ let results: Vec < _ > = state. emit ( ) ?. try_collect ( ) . await ?;
4625+ assert_eq ! ( results. iter( ) . map( |b| b. num_rows( ) ) . sum:: <usize >( ) , 20 ) ;
4626+ assert_eq ! ( results. len( ) , 3 , "expected 3 chunks of batch_size=8" ) ;
4627+ let val_col = results[ 0 ] . column ( 1 ) . as_dictionary :: < Int32Type > ( ) ;
4628+ let dict_values = val_col. values ( ) . as_string :: < i32 > ( ) ;
4629+ let first_val = dict_values. value ( val_col. keys ( ) . value ( 0 ) as usize ) ;
4630+ assert_eq ! ( first_val, "v00" , "rows must still emit in ob-sorted order" ) ;
4631+ Ok ( ( ) )
4632+ }
4633+
45384634 /// DENSE_RANK-specific: eviction removes the entire max group when
45394635 /// a strictly-smaller distinct ob arrives. Multiple rows at the
45404636 /// evicted key all disappear.
0 commit comments