Repository navigation
Expand file tree
/
Copy pathmod.rs
More file actions
3169 lines (2831 loc) · 111 KB
/
Copy pathmod.rs
File metadata and controls
3169 lines (2831 loc) · 111 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements. See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership. The ASF licenses this file
// to you under the Apache License, Version 2.0 (the
// "License"); you may not use this file except in compliance
// with the License. You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing,
// software distributed under the License is distributed on an
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, either express or implied. See the License for the
// specific language governing permissions and limitations
// under the License.
//! TopK: Combination of Sort / LIMIT
use arrow::{
array::{Array, AsArray},
compute::{
BatchCoalescer, FilterBuilder, interleave_record_batch, prep_null_mask_filter,
take_record_batch,
},
row::{OwnedRow, RowConverter, Rows, SortField},
};
use datafusion_expr::{ColumnarValue, Operator};
use std::mem::size_of;
use std::sync::atomic::{AtomicUsize, Ordering as AtomicOrdering};
use std::{cmp::Ordering, collections::BinaryHeap, sync::Arc};
use super::metrics::{
BaselineMetrics, Count, ExecutionPlanMetricsSet, MetricBuilder, MetricCategory,
RecordOutput,
};
use crate::spill::get_record_batch_memory_size;
use crate::{SendableRecordBatchStream, stream::RecordBatchStreamAdapter};
use arrow::array::{ArrayRef, RecordBatch, UInt32Array};
use arrow::datatypes::SchemaRef;
use datafusion_common::{
HashMap, Result, ScalarValue, internal_datafusion_err, internal_err,
};
use datafusion_execution::{
memory_pool::{MemoryConsumer, MemoryReservation},
runtime_env::RuntimeEnv,
};
use datafusion_physical_expr::{
PhysicalExpr,
expressions::{BinaryExpr, DynamicFilterPhysicalExpr, is_not_null, is_null, lit},
};
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
use parking_lot::RwLock;
/// TopK
///
/// # Background
///
/// "Top K" is a common query optimization used for queries such as
/// "find the top 3 customers by revenue". The (simplified) SQL for
/// such a query might be:
///
/// ```sql
/// SELECT customer_id, revenue FROM 'sales.csv' ORDER BY revenue DESC limit 3;
/// ```
///
/// The simple plan would be:
///
/// ```sql
/// > explain SELECT customer_id, revenue FROM sales ORDER BY revenue DESC limit 3;
/// +--------------+----------------------------------------+
/// | plan_type | plan |
/// +--------------+----------------------------------------+
/// | logical_plan | Limit: 3 |
/// | | Sort: revenue DESC NULLS FIRST |
/// | | Projection: customer_id, revenue |
/// | | TableScan: sales |
/// +--------------+----------------------------------------+
/// ```
///
/// While this plan produces the correct answer, it will fully sorts the
/// input before discarding everything other than the top 3 elements.
///
/// The same answer can be produced by simply keeping track of the top
/// K=3 elements, reducing the total amount of required buffer memory.
///
/// # Partial Sort Optimization
///
/// This implementation additionally optimizes queries where the input is already
/// partially sorted by a common prefix of the requested ordering. If subsequent
/// rows are guaranteed to be strictly greater (in sort order) than a known TopK
/// boundary on this prefix, the operator safely terminates early.
///
/// For a local TopK, that boundary comes from the local heap once it has K rows.
/// For a partitioned `SortExec`, a shared dynamic-filter threshold can provide
/// the same prefix boundary before a lagging partition has filled its local heap.
///
/// ## Example
///
/// For input sorted by `(day DESC)`, but not by `timestamp`, a query such as:
///
/// ```sql
/// SELECT day, timestamp FROM sensor ORDER BY day DESC, timestamp DESC LIMIT 10;
/// ```
///
/// can terminate scanning early once sufficient rows from the latest days have been
/// collected, skipping older data.
///
/// # Structure
///
/// This operator tracks the top K items using a `TopKHeap`.
pub struct TopK {
/// schema of the output (and the input)
schema: SchemaRef,
/// Runtime metrics
metrics: TopKMetrics,
/// Reservation
reservation: MemoryReservation,
/// The target number of rows for output batches
batch_size: usize,
/// sort expressions
expr: LexOrdering,
/// row converter, for sort keys
row_converter: RowConverter,
/// scratch space for converting rows
scratch_rows: Rows,
/// stores the top k values and their sort key values, in order
heap: TopKHeap,
/// row converter, for common keys between the sort keys and the input ordering
common_sort_prefix_converter: Option<RowConverter>,
/// Common sort prefix between the input and the sort expressions to allow early exit optimization
common_sort_prefix: Arc<[PhysicalSortExpr]>,
/// Filter matching the state of the `TopK` heap used for dynamic filter pushdown
filter: Arc<RwLock<TopKDynamicFilters>>,
/// If true, indicates that all rows of subsequent batches are guaranteed
/// to be greater (by byte order, after row conversion) than the top K,
/// which means the top K won't change and the computation can be finished early.
pub(crate) finished: bool,
}
/// For more background, please also see the [Dynamic Filters: Passing Information Between Operators During Execution for 25x Faster Queries blog]
///
/// [Dynamic Filters: Passing Information Between Operators During Execution for 25x Faster Queries blog]: https://datafusion.apache.org/blog/2025/09/10/dynamic-filters
#[derive(Debug)]
pub struct TopKDynamicFilters {
/// The current threshold shared by all TopK emitters that use this dynamic
/// filter. Any emitter may tighten it.
///
/// The full sort-key row and common-prefix row are stored together so they
/// always describe the same heap row.
shared_threshold: Option<TopKThreshold>,
/// The expression used to evaluate the dynamic filter
/// Only updated when lock held for the duration of the update
expr: Arc<DynamicFilterPhysicalExpr>,
/// Number of local TopK emitters that have not called `emit` yet.
///
/// A partition-preserving `SortExec` creates one local TopK per output
/// partition. The shared dynamic filter is complete only after every local
/// TopK has emitted.
///
/// `emit` only needs a read guard on the shared filter wrapper, so
/// concurrent emitters use this atomic counter instead of taking an
/// exclusive lock just to mark their partition done.
remaining_topk_emitters: AtomicUsize,
}
#[derive(Debug, Clone)]
struct TopKThreshold {
/// The full sort-key row bytes for efficient comparison.
full_sort_key_row: Vec<u8>,
/// The same heap row encoded with the common-prefix converter, when the
/// input ordering shares a prefix with the TopK ordering.
///
/// This lets each partition stop from a shared TopK threshold even if its
/// local heap has not filled yet.
common_prefix_row: Option<Vec<u8>>,
}
impl TopKThreshold {
fn new(full_sort_key_row: Vec<u8>, common_prefix_row: Option<Vec<u8>>) -> Self {
Self {
full_sort_key_row,
common_prefix_row,
}
}
fn full_sort_key_row(&self) -> &[u8] {
self.full_sort_key_row.as_slice()
}
fn common_prefix_row(&self) -> Option<&[u8]> {
self.common_prefix_row.as_deref()
}
fn is_more_selective_than(&self, current: &Self) -> bool {
self.full_sort_key_row() < current.full_sort_key_row()
}
}
#[derive(Clone, Copy)]
struct TopKHeapBoundaryRow<'a> {
row: &'a TopKRow,
}
impl<'a> TopKHeapBoundaryRow<'a> {
fn new(row: &'a TopKRow) -> Self {
Self { row }
}
fn full_sort_key_row(&self) -> &[u8] {
self.row.row()
}
fn is_more_selective_than(&self, current: Option<&TopKThreshold>) -> bool {
current
.map(|current| self.full_sort_key_row() < current.full_sort_key_row())
.unwrap_or(true)
}
}
#[derive(Clone, Copy)]
struct TopKHeapBoundary<'a> {
row: &'a TopKRow,
batch: &'a RecordBatch,
}
impl<'a> TopKHeapBoundary<'a> {
fn new(row: &'a TopKRow, batch: &'a RecordBatch) -> Self {
Self { row, batch }
}
fn threshold_values(
&self,
sort_exprs: &[PhysicalSortExpr],
) -> Result<Vec<ScalarValue>> {
let mut scalar_values = Vec::with_capacity(sort_exprs.len());
for sort_expr in sort_exprs {
let value = sort_expr
.expr
.evaluate(&self.batch.slice(self.row.index, 1))?;
let scalar = match value {
ColumnarValue::Scalar(scalar) => scalar,
ColumnarValue::Array(array) if array.len() == 1 => {
ScalarValue::try_from_array(&array, 0)?
}
array => {
return internal_err!("Expected a scalar value, got {:?}", array);
}
};
scalar_values.push(scalar);
}
Ok(scalar_values)
}
fn threshold(&self, common_prefix_row: Option<Vec<u8>>) -> TopKThreshold {
TopKThreshold::new(self.row.row().to_vec(), common_prefix_row)
}
}
impl TopKDynamicFilters {
/// Create a new `TopKDynamicFilters` with the given expression
pub fn new(expr: Arc<DynamicFilterPhysicalExpr>) -> Self {
Self::new_with_topk_emitter_count(expr, 1)
}
/// Create a new `TopKDynamicFilters` with the expected number of local
/// TopK emitters that share it.
pub fn new_with_topk_emitter_count(
expr: Arc<DynamicFilterPhysicalExpr>,
topk_emitter_count: usize,
) -> Self {
debug_assert!(topk_emitter_count > 0);
Self {
shared_threshold: None,
expr,
remaining_topk_emitters: AtomicUsize::new(topk_emitter_count),
}
}
pub fn expr(&self) -> Arc<DynamicFilterPhysicalExpr> {
Arc::clone(&self.expr)
}
fn mark_topk_emitted(&self) {
let previous = self
.remaining_topk_emitters
.fetch_update(
AtomicOrdering::AcqRel,
AtomicOrdering::Acquire,
|remaining| remaining.checked_sub(1),
)
.unwrap_or(0);
debug_assert!(
previous > 0,
"TopK dynamic filter emitter completed more times than expected"
);
if previous == 1 {
self.expr.mark_complete();
}
}
}
// Guesstimate for memory allocation: estimated number of bytes used per row in the RowConverter
const ESTIMATED_BYTES_PER_ROW: usize = 20;
/// Owned data of a row that was just evicted from a [`TopKHeap`].
///
/// Returned by [`TopKHeap::add`] so that callers (e.g. rank-aware
/// wrappers that retain boundary ties) can decide whether to retain
/// the evicted row externally. The underlying batch is captured
/// before the heap's internal `RecordBatchStore` decrements the
/// batch's use count, so the data remains accessible even if the
/// heap drops its internal reference to the batch.
#[derive(Debug, Clone)]
pub(crate) struct EvictedRow {
/// The record batch the evicted row came from.
pub batch: RecordBatch,
/// Row index within `batch`.
pub index: usize,
/// Encoded ORDER BY tuple for the evicted row, in [`arrow::row`] format.
pub row_bytes: Vec<u8>,
}
pub(crate) fn build_sort_fields(
ordering: &[PhysicalSortExpr],
schema: &SchemaRef,
) -> Result<Vec<SortField>> {
ordering
.iter()
.map(|e| {
Ok(SortField::new_with_options(
e.expr.data_type(schema)?,
e.options,
))
})
.collect::<Result<_>>()
}
impl TopK {
/// Create a new [`TopK`] that stores the top `k` values, as
/// defined by the sort expressions in `expr`.
// TODO: make a builder or some other nicer API
#[expect(clippy::too_many_arguments)]
#[expect(clippy::needless_pass_by_value)]
pub fn try_new(
partition_id: usize,
schema: SchemaRef,
common_sort_prefix: Vec<PhysicalSortExpr>,
expr: LexOrdering,
k: usize,
batch_size: usize,
runtime: Arc<RuntimeEnv>,
metrics: &ExecutionPlanMetricsSet,
filter: Arc<RwLock<TopKDynamicFilters>>,
) -> Result<Self> {
let reservation = MemoryConsumer::new(format!("TopK[{partition_id}]"))
.register(&runtime.memory_pool);
let sort_fields = build_sort_fields(&expr, &schema)?;
// TODO there is potential to add special cases for single column sort fields
// to improve performance
let row_converter = RowConverter::new(sort_fields)?;
let scratch_rows =
row_converter.empty_rows(batch_size, ESTIMATED_BYTES_PER_ROW * batch_size);
let common_prefix_row_converter = if common_sort_prefix.is_empty() {
None
} else {
let input_sort_fields = build_sort_fields(&common_sort_prefix, &schema)?;
Some(RowConverter::new(input_sort_fields)?)
};
Ok(Self {
schema: Arc::clone(&schema),
metrics: TopKMetrics::new(metrics, partition_id),
reservation,
batch_size,
expr,
row_converter,
scratch_rows,
heap: TopKHeap::new(k),
common_sort_prefix_converter: common_prefix_row_converter,
common_sort_prefix: Arc::from(common_sort_prefix),
finished: false,
filter,
})
}
/// Insert `batch`, remembering if any of its values are among
/// the top k seen so far.
#[expect(clippy::needless_pass_by_value)]
pub fn insert_batch(&mut self, batch: RecordBatch) -> Result<()> {
// Updates on drop
let baseline = self.metrics.baseline.clone();
let _timer = baseline.elapsed_compute().timer();
let mut sort_keys: Vec<ArrayRef> = self
.expr
.iter()
.map(|expr| {
let value = expr.expr.evaluate(&batch)?;
value.into_array(batch.num_rows())
})
.collect::<Result<Vec<_>>>()?;
let mut selected_rows = None;
// If a filter is provided, update it with the new rows
let filter = self.filter.read().expr.current()?;
let filtered = filter.evaluate(&batch)?;
let num_rows = batch.num_rows();
let array = filtered.into_array(num_rows)?;
let mut filter = array.as_boolean().clone();
if !filter.has_true() {
// The heap is unchanged, but a fully rejected batch can still prove
// that the shared sort prefix has passed the heap boundary.
self.attempt_early_completion(&batch)?;
return Ok(());
}
// only update the keys / rows if the filter does not match all rows
if filter.null_count() > 0 || filter.has_false() {
// Indices in `set_indices` should be correct if filter contains nulls
// So we prepare the filter here. Note this is also done in the `FilterBuilder`
// so there is no overhead to do this here.
if filter.nulls().is_some() {
filter = prep_null_mask_filter(&filter);
}
let filter_predicate = FilterBuilder::new(&filter);
let filter_predicate = if sort_keys.len() > 1 {
// Optimize filter when it has multiple sort keys
filter_predicate.optimize().build()
} else {
filter_predicate.build()
};
selected_rows = Some(filter);
sort_keys = sort_keys
.iter()
.map(|key| filter_predicate.filter(key).map_err(|x| x.into()))
.collect::<Result<Vec<_>>>()?;
}
// reuse existing `Rows` to avoid reallocations
let rows = &mut self.scratch_rows;
rows.clear();
self.row_converter.append(rows, &sort_keys)?;
let mut batch_entry = self.heap.register_batch(batch.clone());
let replacements = match selected_rows {
Some(filter) => {
self.find_new_topk_items(filter.values().set_indices(), &mut batch_entry)
}
None => self.find_new_topk_items(0..sort_keys[0].len(), &mut batch_entry),
};
if replacements > 0 {
self.metrics.row_replacements.add(replacements);
self.heap.insert_batch_entry(batch_entry);
// conserve memory
self.heap.maybe_compact()?;
// update memory reservation
self.reservation.try_resize(self.size())?;
// flag the topK as finished if we know that all
// subsequent batches are guaranteed to be greater (by byte order, after row conversion) than the top K,
// which means the top K won't change and the computation can be finished early.
self.attempt_early_completion(&batch)?;
// update the filter representation of our TopK heap
self.update_filter()?;
} else {
// The heap did not change, but this batch's prefix may still prove
// that no later rows can enter the TopK.
self.attempt_early_completion(&batch)?;
}
Ok(())
}
fn find_new_topk_items(
&mut self,
items: impl Iterator<Item = usize>,
batch_entry: &mut RecordBatchEntry,
) -> usize {
let mut replacements = 0;
let rows = &mut self.scratch_rows;
for (index, row) in items.zip(rows.iter()) {
match self.heap.max() {
// heap has k items, and the new row is greater than the
// current max in the heap ==> it is not a new topk
Some(max_row) if row.as_ref() >= max_row.row() => {}
// don't yet have k items or new item is lower than the currently k low values
None | Some(_) => {
self.heap.add(batch_entry, row, index);
replacements += 1;
}
}
}
replacements
}
fn current_heap_boundary_row(&self) -> Option<TopKHeapBoundaryRow<'_>> {
self.heap.max().map(TopKHeapBoundaryRow::new)
}
fn current_heap_boundary(&self) -> Result<Option<TopKHeapBoundary<'_>>> {
let Some(row) = self.heap.max() else {
return Ok(None);
};
self.heap_boundary(row).map(Some)
}
fn heap_boundary<'a>(&'a self, row: &'a TopKRow) -> Result<TopKHeapBoundary<'a>> {
let batch_entry = self
.heap
.store
.get(row.batch_id)
.ok_or_else(|| internal_datafusion_err!("Invalid batch ID in TopKRow"))?;
Ok(TopKHeapBoundary::new(row, &batch_entry.batch))
}
/// Update the filter representation of our TopK heap.
/// For example, given the sort expression `ORDER BY a DESC, b ASC LIMIT 3`,
/// and the current heap values `[(1, 5), (1, 4), (2, 3)]`,
/// the filter will be updated to:
///
/// ```sql
/// (a > 1 OR (a = 1 AND b < 5)) AND
/// (a > 1 OR (a = 1 AND b < 4)) AND
/// (a > 2 OR (a = 2 AND b < 3))
/// ```
fn update_filter(&mut self) -> Result<()> {
// If the heap doesn't have k elements yet, we can't create thresholds
let Some(boundary_row) = self.current_heap_boundary_row() else {
return Ok(());
};
// Fast path: check if the current value in topk is better than what is
// currently set in the filter with a read only lock
let needs_update = {
let filter = self.filter.read();
boundary_row.is_more_selective_than(filter.shared_threshold.as_ref())
};
// exit early if the current values are better
if !needs_update {
return Ok(());
}
let boundary = self.heap_boundary(boundary_row.row)?;
// Extract scalar values BEFORE acquiring lock to reduce critical section
let thresholds = boundary.threshold_values(&self.expr)?;
// Build the filter expression OUTSIDE any synchronization
let predicate = Self::build_filter_expression(&self.expr, &thresholds)?;
let new_threshold =
boundary.threshold(self.encode_topk_common_prefix_row(boundary)?);
// update the threshold. Since there was a lock gap, we must check if it is still the best
// may have changed while we were building the expression without the lock
let mut filter = self.filter.write();
let still_needs_update = filter
.shared_threshold
.as_ref()
.map(|current| new_threshold.is_more_selective_than(current))
.unwrap_or(true);
if !still_needs_update {
// some other thread updated the threshold to a better one while we
// were building so there is no need to update the filter
return Ok(());
}
filter.shared_threshold = Some(new_threshold);
// Update the filter expression
if let Some(pred) = predicate
&& !pred.eq(&lit(true))
{
filter.expr.update(pred)?;
}
Ok(())
}
/// Build the filter expression with the given thresholds.
/// This is now called outside of any locks to reduce critical section time.
fn build_filter_expression(
sort_exprs: &[PhysicalSortExpr],
thresholds: &[ScalarValue],
) -> Result<Option<Arc<dyn PhysicalExpr>>> {
// Create filter expressions for each threshold
let mut filters: Vec<Arc<dyn PhysicalExpr>> =
Vec::with_capacity(thresholds.len());
let mut prev_sort_expr: Option<Arc<dyn PhysicalExpr>> = None;
for (sort_expr, value) in sort_exprs.iter().zip(thresholds.iter()) {
// Create the appropriate operator based on sort order
let op = if sort_expr.options.descending {
// For descending sort, we want col > threshold (exclude smaller values)
Operator::Gt
} else {
// For ascending sort, we want col < threshold (exclude larger values)
Operator::Lt
};
let value_null = value.is_null();
let comparison = Arc::new(BinaryExpr::new(
Arc::clone(&sort_expr.expr),
op,
lit(value.clone()),
));
let comparison_with_null = match (sort_expr.options.nulls_first, value_null) {
// For nulls first, transform to (threshold.value is not null) and (threshold.expr is null or comparison)
(true, true) => lit(false),
(true, false) => Arc::new(BinaryExpr::new(
is_null(Arc::clone(&sort_expr.expr))?,
Operator::Or,
comparison,
)),
// For nulls last, transform to (threshold.value is null and threshold.expr is not null)
// or (threshold.value is not null and comparison)
(false, true) => is_not_null(Arc::clone(&sort_expr.expr))?,
(false, false) => comparison,
};
let mut eq_expr = Arc::new(BinaryExpr::new(
Arc::clone(&sort_expr.expr),
Operator::Eq,
lit(value.clone()),
));
if value_null {
eq_expr = Arc::new(BinaryExpr::new(
is_null(Arc::clone(&sort_expr.expr))?,
Operator::Or,
eq_expr,
));
}
// For a query like order by a, b, the filter for column `b` is only applied if
// the condition a = threshold.value (considering null equality) is met.
// Therefore, we add equality predicates for all preceding fields to the filter logic of the current field,
// and include the current field's equality predicate in `prev_sort_expr` for use with subsequent fields.
match prev_sort_expr.take() {
None => {
prev_sort_expr = Some(eq_expr);
filters.push(comparison_with_null);
}
Some(p) => {
filters.push(Arc::new(BinaryExpr::new(
Arc::clone(&p),
Operator::And,
comparison_with_null,
)));
prev_sort_expr =
Some(Arc::new(BinaryExpr::new(p, Operator::And, eq_expr)));
}
}
}
let dynamic_predicate = filters
.into_iter()
.reduce(|a, b| Arc::new(BinaryExpr::new(a, Operator::Or, b)));
Ok(dynamic_predicate)
}
/// If input ordering shares a common sort prefix with the TopK,
/// check if the computation can be finished early.
///
/// This is the case if the last row of the current batch is strictly
/// greater than either the shared dynamic-filter threshold prefix or the max
/// row in the local heap, comparing only on the shared prefix columns.
fn attempt_early_completion(&mut self, batch: &RecordBatch) -> Result<()> {
// Early exit if the batch is empty as there is no last row to extract from it.
if batch.num_rows() == 0 {
return Ok(());
}
// common_prefix_row_converter is only `Some` if the input ordering has a common prefix with the TopK,
// so early exit if it is `None`.
let Some(prefix_converter) = &self.common_sort_prefix_converter else {
return Ok(());
};
// Evaluate the prefix for the last row of the current batch.
let last_row_idx = batch.num_rows() - 1;
let mut batch_prefix_scratch =
prefix_converter.empty_rows(1, ESTIMATED_BYTES_PER_ROW); // 1 row with capacity ESTIMATED_BYTES_PER_ROW
self.append_common_prefix_row(
prefix_converter,
batch,
last_row_idx,
&mut batch_prefix_scratch,
)?;
let batch_common_prefix_row = batch_prefix_scratch.row(0);
let batch_common_prefix = batch_common_prefix_row.as_ref();
let finished_by_shared_threshold = self
.filter
.read()
.shared_threshold
.as_ref()
.and_then(TopKThreshold::common_prefix_row)
.map(|common_prefix_row| batch_common_prefix > common_prefix_row)
.unwrap_or(false);
if finished_by_shared_threshold {
self.finished = true;
return Ok(());
}
// Early exit only from the local heap once it has a full boundary row.
let Some(boundary) = self.current_heap_boundary()? else {
return Ok(());
};
if self.batch_prefix_exceeds_heap_boundary(batch_common_prefix, boundary)? {
self.finished = true;
}
Ok(())
}
fn batch_prefix_exceeds_heap_boundary(
&self,
batch_common_prefix: &[u8],
boundary: TopKHeapBoundary<'_>,
) -> Result<bool> {
let Some(heap_common_prefix_row) =
self.encode_topk_common_prefix_row(boundary)?
else {
return Ok(false);
};
Ok(batch_common_prefix > heap_common_prefix_row.as_slice())
}
fn encode_topk_common_prefix_row(
&self,
boundary: TopKHeapBoundary<'_>,
) -> Result<Option<Vec<u8>>> {
let Some(prefix_converter) = &self.common_sort_prefix_converter else {
return Ok(None);
};
let mut scratch = prefix_converter.empty_rows(1, ESTIMATED_BYTES_PER_ROW);
self.append_common_prefix_row(
prefix_converter,
boundary.batch,
boundary.row.index,
&mut scratch,
)?;
Ok(Some(scratch.row(0).as_ref().to_vec()))
}
fn append_common_prefix_row(
&self,
prefix_converter: &RowConverter,
batch: &RecordBatch,
row_idx: usize,
scratch: &mut Rows,
) -> Result<()> {
let row = batch.slice(row_idx, 1);
let prefix_columns: Vec<ArrayRef> = self
.common_sort_prefix
.iter()
.map(|expr| expr.expr.evaluate(&row)?.into_array(1))
.collect::<Result<_>>()?;
prefix_converter.append(scratch, &prefix_columns)?;
Ok(())
}
/// Returns the top k results broken into `batch_size` [`RecordBatch`]es, consuming the heap
pub fn emit(self) -> Result<SendableRecordBatchStream> {
let Self {
schema,
metrics,
reservation: _,
batch_size,
expr: _,
row_converter: _,
scratch_rows: _,
mut heap,
common_sort_prefix_converter: _,
common_sort_prefix: _,
finished: _,
filter,
} = self;
let _timer = metrics.baseline.elapsed_compute().timer(); // time updated on drop
// Mark this local TopK as emitted. For shared filters, the final
// local emitter marks the dynamic filter complete.
filter.read().mark_topk_emitted();
// break into record batches as needed
let mut batches = vec![];
if let Some(mut batch) = heap.emit()? {
(&batch).record_output(&metrics.baseline);
loop {
if batch.num_rows() <= batch_size {
batches.push(Ok(batch));
break;
} else {
batches.push(Ok(batch.slice(0, batch_size)));
let remaining_length = batch.num_rows() - batch_size;
batch = batch.slice(batch_size, remaining_length);
}
}
};
Ok(Box::pin(RecordBatchStreamAdapter::new(
schema,
futures::stream::iter(batches),
)))
}
/// return the size of memory used by this operator, in bytes
fn size(&self) -> usize {
size_of::<Self>()
+ self.row_converter.size()
+ self.scratch_rows.size()
+ self.heap.size()
}
}
struct TopKMetrics {
/// metrics
pub baseline: BaselineMetrics,
/// count of how many rows were replaced in the heap
pub row_replacements: Count,
}
impl TopKMetrics {
fn new(metrics: &ExecutionPlanMetricsSet, partition: usize) -> Self {
Self {
baseline: BaselineMetrics::new(metrics, partition),
row_replacements: MetricBuilder::new(metrics)
.with_category(MetricCategory::Rows)
.counter("row_replacements", partition),
}
}
}
/// This structure keeps at most the *smallest* k items, using the
/// [arrow::row] format for sort keys. While it is called "topK" for
/// values like `1, 2, 3, 4, 5` the "top 3" really means the
/// *smallest* 3 , `1, 2, 3`, not the *largest* 3 `3, 4, 5`.
///
/// Using the `Row` format handles things such as ascending vs
/// descending and nulls first vs nulls last.
struct TopKHeap {
/// The maximum number of elements to store in this heap.
k: usize,
/// Storage for up at most `k` items using a BinaryHeap. Reversed
/// so that the smallest k so far is on the top
inner: BinaryHeap<TopKRow>,
/// Storage the original row values (TopKRow only has the sort key)
store: RecordBatchStore,
/// The size of all owned data held by this heap
owned_bytes: usize,
}
impl TopKHeap {
fn new(k: usize) -> Self {
assert!(k > 0);
Self {
k,
inner: BinaryHeap::new(),
store: RecordBatchStore::new(),
owned_bytes: 0,
}
}
/// Register a [`RecordBatch`] with the heap, returning the
/// appropriate entry
pub fn register_batch(&mut self, batch: RecordBatch) -> RecordBatchEntry {
self.store.register(batch)
}
/// Insert a [`RecordBatchEntry`] created by a previous call to
/// [`Self::register_batch`] into storage.
pub fn insert_batch_entry(&mut self, entry: RecordBatchEntry) {
self.store.insert(entry)
}
/// Returns the largest value stored by the heap if there are k
/// items, otherwise returns None. Remember this structure is
/// keeping the "smallest" k values
fn max(&self) -> Option<&TopKRow> {
if self.inner.len() < self.k {
None
} else {
self.inner.peek()
}
}
/// Adds `row` to this heap. If inserting this new item would
/// increase the size past `k`, removes the previously smallest
/// item.
///
/// Returns `Some(EvictedRow)` if an existing row was evicted to
/// make room for `row`, or `None` if the row was inserted into a
/// non-full heap.
fn add(
&mut self,
batch_entry: &mut RecordBatchEntry,
row: impl AsRef<[u8]>,
index: usize,
) -> Option<EvictedRow> {
let batch_id = batch_entry.id;
batch_entry.uses += 1;
assert!(self.inner.len() <= self.k);
let row = row.as_ref();
// Reuse storage for evicted item if possible
if self.inner.len() == self.k {
let mut prev_min = self.inner.peek_mut().unwrap();
// Capture evicted row data before `unuse` (which may GC the
// batch from the store) and `replace_with` (which overwrites
// `prev_min` in place). The batch comes from `self.store` for
// cross-batch evictions, or directly from `batch_entry` when
// a row evicts another row from the same in-flight batch
// (entry not yet registered in the store).
let evicted_batch = if prev_min.batch_id == batch_entry.id {
batch_entry.batch.clone()
} else {
self.store
.get(prev_min.batch_id)
.map(|entry| entry.batch.clone())
.expect("evicted row's batch must be present in the store")
};
let evicted = EvictedRow {
batch: evicted_batch,
index: prev_min.index,
row_bytes: prev_min.row.clone(),
};
// Update batch use
if prev_min.batch_id == batch_entry.id {
batch_entry.uses -= 1;
} else {
self.store.unuse(prev_min.batch_id);
}
// update memory accounting
self.owned_bytes -= prev_min.owned_size();
prev_min.replace_with(row, batch_id, index);
self.owned_bytes += prev_min.owned_size();
Some(evicted)
} else {
let new_row = TopKRow::new(row, batch_id, index);
self.owned_bytes += new_row.owned_size();
// put the new row into the heap
self.inner.push(new_row);
None
}
}
/// Returns the values stored in this heap, from values low to
/// high, as a single [`RecordBatch`], resetting the inner heap
pub fn emit(&mut self) -> Result<Option<RecordBatch>> {
Ok(self.emit_with_state()?.0)
}
/// Returns the values stored in this heap, from values low to
/// high, as a single [`RecordBatch`], and a sorted vec of the
/// current heap's contents
fn emit_with_state(&mut self) -> Result<(Option<RecordBatch>, Vec<TopKRow>)> {
// generate sorted rows
let topk_rows = std::mem::take(&mut self.inner).into_sorted_vec();
if self.store.is_empty() {
return Ok((None, topk_rows));
}
// Collect the batches into a vec and store the "batch_id -> array_pos" mapping, to then
// build the `indices` vec below. This is needed since the batch ids are not continuous.
let mut record_batches = Vec::new();
let mut batch_id_array_pos = HashMap::new();