Skip to content

Commit a67d64a

Browse files
authored
fix: charge semi/anti sort-merge join key groups by their sliced size (apache#25933)
## Which issue does this PR close? - Part of apache#25923 (the memory accounting half; the per-row filter cost is separate). ## Rationale for this change A filtered LeftSemi/LeftAnti sort-merge join under a tight memory pool spills once per matched key group, even when each group holds only a few rows. Each buffered inner key group is charged its parent batch's full size, so a group of at most 7 rows is charged 131,264 bytes (a whole 8192-row batch). On the benchmark from the issue, with a `GreedyMemoryPool` of 64 KB over 20K keys, every one of the 18,128 matched groups spilled to its own file. In a real plan the join shares the pool with the sorts in the same task, so this can start well before the data needs to spill. ## What changes are included in this PR? `buffer_inner_key_group` in `bitwise_stream.rs` now reserves `get_sliced_size()` for each buffered slice instead of `get_array_memory_size()`, the same measure sort uses. Only the reservation (and so the spill decision and `peak_mem_used`) was inflated; `spilled_bytes` counts serialized bytes and is unaffected. A group that reaches the end of its inner batch is still charged the whole parent batch: once the cursor moves on, that slice is the only thing keeping the parent alive. View arrays keep their parent's data buffers in the measure, so they can still be overcounted. Both are noted at the call site. ## What is the testing strategy for this PR? `bitwise_small_key_groups_charged_by_sliced_size` joins inputs with 2 and 3 row key groups under a pool of half a batch, for LeftSemi, LeftAnti, RightSemi and RightAnti. It checks that the join spills at most once per inner batch (for the group reaching each batch's end; 2, 2, 1 and 1 spills) and that the results match an unbounded run. On main it spills 683 times. `bitwise_key_group_at_inner_batch_end_charged_full_parent` uses unique keys, so the last row of every inner batch is such a group, and checks that `peak_mem_used` covers a whole inner batch. Five existing spill tests used a 100-byte pool to force a spill. A one-row slice is now charged about 12 bytes, so their pool is 1 byte; their assertions are unchanged. With the first version of this change on 55.1.0, the issue's 64 KB pool case went from 18,128 spills to none, and the join ran as fast as with an unbounded pool (11.9 ms both, where the 64 KB pool previously took 1,088 ms against 9.3 ms unbounded). Charging the batch-end group in full adds at most one spill per inner batch on top of that, since that pool is smaller than one batch. ## Are there any user-facing changes? No API changes. Filtered semi and anti sort-merge joins spill less under memory pressure.
1 parent 9fb986c commit a67d64a

2 files changed

Lines changed: 204 additions & 10 deletions

File tree

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

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -669,7 +669,17 @@ impl BitwiseSortMergeJoinStream {
669669

670670
let inner_batch = self.inner_batch.as_ref().unwrap();
671671
let slice = inner_batch.slice(from, group_end - from);
672-
self.inner_buffer_size += slice.get_array_memory_size();
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();
678+
self.inner_buffer_size += if group_end < num_inner {
679+
parent_size.div_ceil(num_inner) * slice.num_rows()
680+
} else {
681+
parent_size
682+
};
673683
self.inner_key_buffer.push(slice);
674684

675685
// Reserve memory for the newly buffered slice. If the pool

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

Lines changed: 193 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -6283,9 +6283,10 @@ fn filtered_bitwise_spill_fixture() -> Result<FilteredBitwiseSpillFixture> {
62836283

62846284
/// Exercises inner key group spilling under memory pressure.
62856285
///
6286-
/// Uses a tiny memory limit (100 bytes) with disk spilling enabled. Since our
6287-
/// operator only buffers inner rows when a filter is present, this test includes
6288-
/// a filter (c1 < c2, always true). Verifies:
6286+
/// Uses a 1-byte memory limit, below the size of any buffered slice, with
6287+
/// disk spilling enabled. Since our operator only buffers inner rows when a
6288+
/// filter is present, this test includes a filter (c1 < c2, always true).
6289+
/// Verifies:
62896290
/// 1. Spill metrics are recorded (spill_count, spilled_bytes, spilled_rows > 0)
62906291
/// 2. Results match a non-spilled run
62916292
#[tokio::test]
@@ -6299,7 +6300,7 @@ async fn bitwise_spill_with_filter() -> Result<()> {
62996300
} = filtered_bitwise_spill_fixture()?;
63006301

63016302
let runtime = RuntimeEnvBuilder::new()
6302-
.with_memory_limit(100, 1.0)
6303+
.with_memory_limit(1, 1.0)
63036304
.with_disk_manager_builder(
63046305
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
63056306
)
@@ -6409,7 +6410,7 @@ async fn bitwise_filtered_no_spill() -> Result<()> {
64096410

64106411
// Tiny memory pool with the DiskManager disabled: spilling is impossible.
64116412
let runtime = RuntimeEnvBuilder::new()
6412-
.with_memory_limit(100, 1.0)
6413+
.with_memory_limit(1, 1.0)
64136414
.with_disk_manager_builder(
64146415
DiskManagerBuilder::default().with_mode(DiskManagerMode::Disabled),
64156416
)
@@ -6463,6 +6464,189 @@ async fn bitwise_filtered_no_spill() -> Result<()> {
64636464
Ok(())
64646465
}
64656466

6467+
/// Builds `num_batches` batches of `rows_per_batch` rows each. Row `i`
6468+
/// (counted across batches) holds `(i, i / group_size, i * c_step % 10)`, so
6469+
/// every join key covers `group_size` consecutive rows.
6470+
fn small_key_group_batches(
6471+
names: (&str, &str, &str),
6472+
num_batches: i32,
6473+
rows_per_batch: i32,
6474+
group_size: i32,
6475+
c_step: i32,
6476+
) -> Vec<RecordBatch> {
6477+
(0..num_batches)
6478+
.map(|b| {
6479+
let rows: Vec<i32> = (b * rows_per_batch..(b + 1) * rows_per_batch).collect();
6480+
build_table_i32(
6481+
(names.0, &rows),
6482+
(names.1, &rows.iter().map(|i| i / group_size).collect()),
6483+
(names.2, &rows.iter().map(|i| i * c_step % 10).collect()),
6484+
)
6485+
})
6486+
.collect()
6487+
}
6488+
6489+
/// 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 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).
6494+
#[tokio::test]
6495+
async fn bitwise_small_key_groups_charged_by_row_share() -> Result<()> {
6496+
const NUM_BATCHES: i32 = 2;
6497+
const ROWS_PER_BATCH: i32 = 1024;
6498+
6499+
// Left key groups hold 2 rows, right key groups hold 3. Left keys past
6500+
// the right side's last key have no match, and c1 < c2 holds for only
6501+
// some rows within matching keys, so every join type returns some but
6502+
// not all of its outer rows.
6503+
let left_batches =
6504+
small_key_group_batches(("a1", "b1", "c1"), NUM_BATCHES, ROWS_PER_BATCH, 2, 1);
6505+
let right_batches =
6506+
small_key_group_batches(("a2", "b1", "c2"), NUM_BATCHES, ROWS_PER_BATCH, 3, 7);
6507+
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
6510+
// batch reports.
6511+
let parent_batch_size = left_batches
6512+
.iter()
6513+
.chain(&right_batches)
6514+
.map(|b| b.get_array_memory_size())
6515+
.min()
6516+
.unwrap();
6517+
let memory_limit = parent_batch_size / 2;
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();
6526+
// Keep 10x headroom over a group's rows so the test turns on how a
6527+
// group is charged, not on landing near the limit.
6528+
assert!(
6529+
memory_limit > 10 * largest_group_size,
6530+
"memory limit {memory_limit} too close to group size {largest_group_size}"
6531+
);
6532+
6533+
let left = build_table_from_batches(left_batches);
6534+
let right = build_table_from_batches(right_batches);
6535+
let on: JoinOn = vec![(
6536+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
6537+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
6538+
)];
6539+
let sort_options = vec![SortOptions::default(); on.len()];
6540+
let filter = build_c1_lt_c2_filter(left.schema().as_ref(), right.schema().as_ref());
6541+
let num_outer_rows = (NUM_BATCHES * ROWS_PER_BATCH) as usize;
6542+
6543+
let runtime = RuntimeEnvBuilder::new()
6544+
.with_memory_limit(memory_limit, 1.0)
6545+
.with_disk_manager_builder(
6546+
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
6547+
)
6548+
.build_arc()?;
6549+
6550+
for join_type in [LeftSemi, LeftAnti, RightSemi, RightAnti] {
6551+
let bounded_ctx =
6552+
Arc::new(TaskContext::default().with_runtime(Arc::clone(&runtime)));
6553+
let join = join_with_filter(
6554+
Arc::clone(&left),
6555+
Arc::clone(&right),
6556+
on.clone(),
6557+
filter.clone(),
6558+
join_type,
6559+
sort_options.clone(),
6560+
NullEquality::NullEqualsNothing,
6561+
)?;
6562+
let bounded_result = common::collect(join.execute(0, bounded_ctx)?).await?;
6563+
let metrics = join
6564+
.metrics()
6565+
.unwrap_or_else(|| panic!("metrics missing for {join_type:?}"));
6566+
let spill_count = metrics.spill_count().unwrap();
6567+
assert!(
6568+
spill_count <= NUM_BATCHES as usize,
6569+
"{spill_count} spills under a {memory_limit} byte pool for {join_type:?}"
6570+
);
6571+
6572+
let unbounded_join = join_with_filter(
6573+
Arc::clone(&left),
6574+
Arc::clone(&right),
6575+
on.clone(),
6576+
filter.clone(),
6577+
join_type,
6578+
sort_options.clone(),
6579+
NullEquality::NullEqualsNothing,
6580+
)?;
6581+
let unbounded_result =
6582+
common::collect(unbounded_join.execute(0, Arc::new(TaskContext::default()))?)
6583+
.await?;
6584+
assert_eq!(
6585+
bounded_result, unbounded_result,
6586+
"bounded and unbounded results differ for {join_type:?}"
6587+
);
6588+
6589+
let rows: usize = bounded_result.iter().map(|b| b.num_rows()).sum();
6590+
assert!(
6591+
rows > 0 && rows < num_outer_rows,
6592+
"expected some but not all outer rows for {join_type:?}, got {rows}"
6593+
);
6594+
}
6595+
6596+
Ok(())
6597+
}
6598+
6599+
/// A buffered inner key group that reaches the end of its inner batch is
6600+
/// the only thing keeping that batch alive once the cursor moves to the
6601+
/// next one, so it must be charged the whole parent batch, not just its
6602+
/// rows. Every key here is unique, so the last row of each inner batch is
6603+
/// such a group.
6604+
#[tokio::test]
6605+
async fn bitwise_key_group_at_inner_batch_end_charged_full_parent() -> Result<()> {
6606+
let left_batches = small_key_group_batches(("a1", "b1", "c1"), 2, 1024, 1, 1);
6607+
let right_batches = small_key_group_batches(("a2", "b1", "c2"), 2, 1024, 1, 7);
6608+
let parent_batch_size = left_batches
6609+
.iter()
6610+
.chain(&right_batches)
6611+
.map(|b| b.get_array_memory_size())
6612+
.min()
6613+
.unwrap();
6614+
6615+
let left = build_table_from_batches(left_batches);
6616+
let right = build_table_from_batches(right_batches);
6617+
let on: JoinOn = vec![(
6618+
Arc::new(Column::new_with_schema("b1", &left.schema())?) as _,
6619+
Arc::new(Column::new_with_schema("b1", &right.schema())?) as _,
6620+
)];
6621+
let sort_options = vec![SortOptions::default(); on.len()];
6622+
let filter = build_c1_lt_c2_filter(left.schema().as_ref(), right.schema().as_ref());
6623+
6624+
for join_type in [LeftSemi, LeftAnti, RightSemi, RightAnti] {
6625+
let join = join_with_filter(
6626+
Arc::clone(&left),
6627+
Arc::clone(&right),
6628+
on.clone(),
6629+
filter.clone(),
6630+
join_type,
6631+
sort_options.clone(),
6632+
NullEquality::NullEqualsNothing,
6633+
)?;
6634+
common::collect(join.execute(0, Arc::new(TaskContext::default()))?).await?;
6635+
6636+
let peak_mem = join
6637+
.metrics()
6638+
.and_then(|m| m.sum_by_name("peak_mem_used"))
6639+
.map(|m| m.as_usize())
6640+
.unwrap_or(0);
6641+
assert!(
6642+
peak_mem >= parent_batch_size,
6643+
"peak_mem_used ({peak_mem}) below one inner batch ({parent_batch_size}) for {join_type:?}"
6644+
);
6645+
}
6646+
6647+
Ok(())
6648+
}
6649+
64666650
/// A single inner key group spanning several inner batches can spill more
64676651
/// than once under memory pressure. Every spilled slice must still be
64686652
/// evaluated against the outer rows — an earlier spill file must not be
@@ -6498,10 +6682,10 @@ async fn bitwise_multi_spill_inner_key_group() -> Result<()> {
64986682
let sort_options = vec![SortOptions::default(); on.len()];
64996683
let filter = build_c1_lt_c2_filter(left.schema().as_ref(), right.schema().as_ref());
65006684

6501-
// 100-byte pool: every buffered slice fails its reservation, so each
6685+
// 1-byte pool: every buffered slice fails its reservation, so each
65026686
// inner batch of the key group spills separately.
65036687
let runtime = RuntimeEnvBuilder::new()
6504-
.with_memory_limit(100, 1.0)
6688+
.with_memory_limit(1, 1.0)
65056689
.with_disk_manager_builder(
65066690
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
65076691
)
@@ -6621,7 +6805,7 @@ async fn bitwise_spill_null_key_group() -> Result<()> {
66216805
let filter = build_c1_lt_c2_filter(left.schema().as_ref(), right.schema().as_ref());
66226806

66236807
let runtime = RuntimeEnvBuilder::new()
6624-
.with_memory_limit(100, 1.0)
6808+
.with_memory_limit(1, 1.0)
66256809
.with_disk_manager_builder(
66266810
DiskManagerBuilder::default().with_mode(DiskManagerMode::OsTmpDirectory),
66276811
)
@@ -7295,7 +7479,7 @@ async fn bitwise_spill_pending_stream() -> Result<()> {
72957479
);
72967480

72977481
let runtime = RuntimeEnvBuilder::new()
7298-
.with_memory_limit(100, 1.0)
7482+
.with_memory_limit(1, 1.0)
72997483
.with_disk_manager_builder(pending_disk_manager_builder())
73007484
.build_arc()?;
73017485

0 commit comments

Comments
 (0)