Skip to content

Commit f99f277

Browse files
committed
perf: charge an in-batch key group its row share of the parent
get_sliced_size() allocates per column for every buffered key group, which made filtered semi/anti joins with many tiny key groups about 1.2x slower than main. Charge a group ending inside its inner batch parent_size.div_ceil(num_inner) per row instead: O(1), and it cannot overflow usize on 32-bit targets. Groups reaching the batch end are still charged the whole parent.
1 parent 460cb8c commit f99f277

2 files changed

Lines changed: 25 additions & 19 deletions

File tree

‎datafusion/physical-plan/src/joins/sort_merge_join/bitwise_stream.rs‎

Lines changed: 9 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -128,7 +128,7 @@ use crate::metrics::{
128128
BaselineMetrics, Count, ExecutionPlanMetricsSet, Gauge, MetricBuilder, Time,
129129
};
130130
use crate::spill::in_progress_spill_file::InProgressSpillFile;
131-
use crate::spill::spill_manager::{GetSlicedSize, SpillManager};
131+
use crate::spill::spill_manager::SpillManager;
132132
use crate::stream::{ObservedStream, RecordBatchStreamAdapter};
133133
use arrow::array::{Array, ArrayRef, BooleanArray, BooleanBufferBuilder, RecordBatch};
134134
use arrow::compute::{BatchCoalescer, SortOptions, filter_record_batch, not};
@@ -669,14 +669,16 @@ impl BitwiseSortMergeJoinStream {
669669

670670
let inner_batch = self.inner_batch.as_ref().unwrap();
671671
let slice = inner_batch.slice(from, group_end - from);
672-
// A group ending inside the batch shares the current inner batch,
673-
// so charge only its rows. A group reaching the batch end keeps
674-
// the whole parent alive once the cursor advances, so charge all
675-
// of it. View arrays still count their parent's data buffers.
672+
// A slice reports its parent's full buffers, so a group ending
673+
// inside the batch is charged its share of the parent by row
674+
// count (rounded up per row, which cannot overflow). A group
675+
// reaching the batch end keeps the whole parent alive once the
676+
// cursor advances, so charge all of it.
677+
let parent_size = slice.get_array_memory_size();
676678
self.inner_buffer_size += if group_end < num_inner {
677-
slice.get_sliced_size()?
679+
parent_size.div_ceil(num_inner) * slice.num_rows()
678680
} else {
679-
slice.get_array_memory_size()
681+
parent_size
680682
};
681683
self.inner_key_buffer.push(slice);
682684

‎datafusion/physical-plan/src/joins/sort_merge_join/tests.rs‎

Lines changed: 16 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ use crate::joins::{HashJoinExec, PartitionMode, SortMergeJoinExec};
3535
use crate::metrics::{ExecutionPlanMetricsSet, SpillMetrics};
3636
use crate::projection::{ProjectionExec, ProjectionExpr};
3737
use crate::sorts::sort::SortExec;
38-
use crate::spill::spill_manager::{GetSlicedSize, SpillManager};
38+
use crate::spill::spill_manager::SpillManager;
3939
use crate::test::TestMemoryExec;
4040
use crate::test::exec::{BarrierExec, PanicExec};
4141
use crate::test::{build_table_i32, build_table_i32_two_cols};
@@ -6487,12 +6487,12 @@ fn small_key_group_batches(
64876487
}
64886488

64896489
/// A buffered inner key group of a few rows is a slice of a much larger
6490-
/// inner batch. A group ending inside its batch must be charged for the
6491-
/// rows it holds, not for the parent batch's buffers, so a pool that fits
6492-
/// any one small group but not a whole inner batch spills at most once per
6493-
/// inner batch (for the group reaching that batch's end).
6490+
/// inner batch. A group ending inside its batch must be charged its row
6491+
/// share of the parent batch, not the parent's full buffers, so a pool that
6492+
/// fits any one small group but not a whole inner batch spills at most once
6493+
/// per inner batch (for the group reaching that batch's end).
64946494
#[tokio::test]
6495-
async fn bitwise_small_key_groups_charged_by_sliced_size() -> Result<()> {
6495+
async fn bitwise_small_key_groups_charged_by_row_share() -> Result<()> {
64966496
const NUM_BATCHES: i32 = 2;
64976497
const ROWS_PER_BATCH: i32 = 1024;
64986498

@@ -6505,8 +6505,8 @@ async fn bitwise_small_key_groups_charged_by_sliced_size() -> Result<()> {
65056505
let right_batches =
65066506
small_key_group_batches(("a2", "b1", "c2"), NUM_BATCHES, ROWS_PER_BATCH, 3, 7);
65076507

6508-
// Half of the smallest input batch: far above the sliced size of any
6509-
// key group ending inside its batch, but below what one whole parent
6508+
// Half of the smallest input batch: far above the row share charged to
6509+
// any key group ending inside its batch, but below what one whole parent
65106510
// batch reports.
65116511
let parent_batch_size = left_batches
65126512
.iter()
@@ -6515,10 +6515,14 @@ async fn bitwise_small_key_groups_charged_by_sliced_size() -> Result<()> {
65156515
.min()
65166516
.unwrap();
65176517
let memory_limit = parent_batch_size / 2;
6518-
let largest_group_size = left_batches[0]
6519-
.slice(0, 3)
6520-
.get_sliced_size()?
6521-
.max(right_batches[0].slice(0, 3).get_sliced_size()?);
6518+
// The largest group holds 3 rows, charged at the per-row share of the
6519+
// largest parent batch, matching how the stream charges it.
6520+
let largest_group_size = left_batches
6521+
.iter()
6522+
.chain(&right_batches)
6523+
.map(|b| b.get_array_memory_size().div_ceil(b.num_rows()) * 3)
6524+
.max()
6525+
.unwrap();
65226526
// Keep 10x headroom over a group's rows so the test turns on how a
65236527
// group is charged, not on landing near the limit.
65246528
assert!(

0 commit comments

Comments
 (0)