Skip to content

Commit 198ab43

Browse files
perf(pwmj): build output batches from buffered runs and one streamed … (#26287)
## Which issue does this PR close? - Part of #18221 (and the PiecewiseMergeJoin EPIC #17427). ## Rationale for this change On large inputs the classic `PiecewiseMergeJoin` (Inner/Left/Right/Full) can be slower than `NestedLoopJoin`. For example, before #25840, `l JOIN r ON l.a < r.b` over 100K×100K rows at the default `target_partitions` took 1.41s with PWMJ and 1.26s with NLJ. A profile of the 1K×1M case (`sample`, `target_partitions = 1`) shows the time goes to copying output rather than to comparisons: | where | share of busy samples | |---|---| | `take` repeating each matched streamed row | 32% | | `BatchCoalescer` `memmove` of every column | 30% | | downstream `sum` (the query itself) | 10% | | per-streamed-row fixed cost (`RecordBatch`, allocations, coalescer bookkeeping) | ~13% | For every matched streamed row, the join takes `UInt32Array::from_value(row, count)`, gathers the streamed row `count` times, slices the buffered suffix, and builds a `RecordBatch` from them. `BatchCoalescer` then copies all of it again, so the streamed columns are written twice. #25840 made finding each row's first match a binary search and settles never-matching rows before the sort, but it kept this emission path, so on current `main` the cost above is still paid for every matched streamed row. ## What changes are included in this PR? The classic join builds each output batch directly, and `BatchCoalescer` is removed from this path. Matched rows: - The output is kept as runs: `(buffered start, len)`, paired with one streamed row index per output row. - Once `batch_size` rows are pending, or the stream batch ends: - Buffered columns are copied run by run with `MutableArrayData::try_extend`, which is a `memcpy` for fixed-width types. - Streamed columns are gathered with one `take` per column. Rows that match nothing are emitted with null columns for the other side, in batches of at most `batch_size`: - Streamed rows that can never match (`Right`/`Full`), which #25840 settles before the sort, are selected with one `filter_record_batch` and emitted as slices of its output (`push_unmatched_streamed`). When every row of a stream batch is unmatched, `filter` returns the input columns as a slice and copies nothing. - Unmatched buffered rows (`Left`/`Full`), in the final pass, are the prefix before the `min_marked` watermark plus any trailing NULL keys (#26043). They are copied out of the buffered batch (`push_unmatched_buffered`), not sliced: a slice would keep the whole buffered batch alive and report its full buffers to downstream memory accounting once per output batch ## Benchmarks The pwmj suite from #25839 (100K buffered keys, 2M streamed rows, five match regimes × INNER/LEFT/RIGHT/FULL). Reproduce with: `cargo run -p datafusion-benchmarks --release --bin benchmark_runner -- pwmj` | regime | main (ms) | this PR (ms) | speedup | |---|---|---|---| | no_match, null_heavy: Inner, Left | 2.2–2.3 | 2.1 | 1.05× | | no_match, null_heavy: Right, Full | 3.2–3.3 | 2.4–2.5 | **1.29–1.33×** | | half_match | 231–233 | 27–29 | **8.1–8.4×** | | selective | 453–455 | 47–48 | **9.5–9.7×** | | all_match (200M output rows) | 167–168 | 159–161 | 1.05–1.06× | ## What is the testing strategy for this PR? Six new unit tests in `classic_join.rs`: - `join_full_less_than_splits_suffixes_across_batches`: at `batch_size = 4`, a buffered suffix straddles an output batch, and never-matching streamed rows, matched rows and unmatched buffered rows all appear. It asserts both the rows and the batch sizes `[1, 4, 2, 1]`. - `join_inner_less_than_one_row_completes_several_batches`: one streamed row whose buffered suffix fills several output batches. - `join_right_less_than_empty_buffered`: a Right join with an empty buffered side, where every streamed row is padded with nulls. - `join_right_less_than_never_matching_rows_split_by_batch_size`: more never-matching streamed rows than `batch_size`, which must be split into batches of at most `batch_size`, in input order, ahead of the matched rows. - `join_left_less_than_unmatched_prefix_and_trailing_nulls`: a Left join on `<` whose unmatched buffered rows are a prefix longer than `batch_size` plus trailing NULL keys, which sort last for `<`. - `join_left_unmatched_buffered_batches_report_own_memory`: each unmatched-buffered output batch reports only its own rows' memory, not the whole buffered batch. ## Are there any user-facing changes? No API changes. `EXPLAIN ANALYZE` reports a smaller `output_bytes` for `PiecewiseMergeJoin`, because output batches no longer share the coalescer's buffers (`explain_analyze.slt`: 128.0 KB → 96.0 B).
1 parent 2099174 commit 198ab43

3 files changed

Lines changed: 763 additions & 163 deletions

File tree

‎datafusion/core/tests/fuzz_cases/join_fuzz.rs‎

Lines changed: 132 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -8,9 +8,10 @@ use std::time::SystemTime;
88
use crate::fuzz_cases::join_fuzz::JoinTestType::{HjSmj, NljHj};
99

1010
use arrow::array::{
11-
Array, ArrayRef, BinaryArray, BooleanArray, Float64Array, Int32Array, UInt32Array,
11+
Array, ArrayRef, AsArray, BinaryArray, BooleanArray, Float64Array, Int32Array,
12+
StringArray, StringViewArray, UInt32Array,
1213
};
13-
use arrow::compute::{SortOptions, take_record_batch};
14+
use arrow::compute::{SortOptions, cast, take_record_batch};
1415
use arrow::datatypes::{DataType, Schema};
1516
use arrow::record_batch::RecordBatch;
1617
use arrow::util::pretty::pretty_format_batches;
@@ -1667,17 +1668,46 @@ impl PwmjFuzzKey for f64 {
16671668
}
16681669
}
16691670

1670-
fn pwmj_kv_schema<K: PwmjFuzzKey>() -> Arc<Schema> {
1671+
/// The payload of row `id`, of `payload` type (`Utf8` or `Utf8View`), so the collectors can
1672+
/// check every output row carries its own row's payload. Even ids get a short string, which a
1673+
/// view stores inline, odd ids one over 12 bytes, which it stores in a data buffer.
1674+
fn pwmj_payload(id: i32) -> String {
1675+
if id % 2 == 0 {
1676+
format!("p{id}")
1677+
} else {
1678+
format!("payload of row {id:08}")
1679+
}
1680+
}
1681+
1682+
fn pwmj_payload_array(ids: &[i32], payload: &DataType) -> ArrayRef {
1683+
let values = ids.iter().map(|&id| pwmj_payload(id));
1684+
match payload {
1685+
DataType::Utf8 => Arc::new(StringArray::from_iter_values(values)),
1686+
DataType::Utf8View => Arc::new(StringViewArray::from_iter_values(values)),
1687+
other => panic!("not a string payload type: {other}"),
1688+
}
1689+
}
1690+
1691+
fn pwmj_kv_schema<K: PwmjFuzzKey>(payload: &DataType) -> Arc<Schema> {
16711692
Arc::new(Schema::new(vec![
16721693
arrow::datatypes::Field::new("id", DataType::Int32, false),
16731694
arrow::datatypes::Field::new("k", K::data_type(), true),
1695+
arrow::datatypes::Field::new("p", payload.clone(), false),
16741696
]))
16751697
}
16761698

1677-
fn pwmj_kv_batch<K: PwmjFuzzKey>(ids: &[i32], keys: &[Option<K>]) -> RecordBatch {
1699+
fn pwmj_kv_batch<K: PwmjFuzzKey>(
1700+
ids: &[i32],
1701+
keys: &[Option<K>],
1702+
payload: &DataType,
1703+
) -> RecordBatch {
16781704
RecordBatch::try_new(
1679-
pwmj_kv_schema::<K>(),
1680-
vec![Arc::new(Int32Array::from(ids.to_vec())), K::to_array(keys)],
1705+
pwmj_kv_schema::<K>(payload),
1706+
vec![
1707+
Arc::new(Int32Array::from(ids.to_vec())),
1708+
K::to_array(keys),
1709+
pwmj_payload_array(ids, payload),
1710+
],
16811711
)
16821712
.unwrap()
16831713
}
@@ -1686,10 +1716,11 @@ fn pwmj_kv_batch<K: PwmjFuzzKey>(ids: &[i32], keys: &[Option<K>]) -> RecordBatch
16861716
fn pwmj_single_exec<K: PwmjFuzzKey>(
16871717
ids: &[i32],
16881718
keys: &[Option<K>],
1719+
payload: &DataType,
16891720
) -> Arc<dyn ExecutionPlan> {
16901721
MemorySourceConfig::try_new_exec(
1691-
&[vec![pwmj_kv_batch(ids, keys)]],
1692-
pwmj_kv_schema::<K>(),
1722+
&[vec![pwmj_kv_batch(ids, keys, payload)]],
1723+
pwmj_kv_schema::<K>(payload),
16931724
None,
16941725
)
16951726
.unwrap()
@@ -1705,6 +1736,7 @@ fn pwmj_parts_exec<K: PwmjFuzzKey>(
17051736
keys: &[Option<K>],
17061737
nparts: usize,
17071738
stagger_seed: Option<u64>,
1739+
payload: &DataType,
17081740
) -> Arc<dyn ExecutionPlan> {
17091741
let nparts = nparts.max(1);
17101742
let mut part_rows: Vec<(Vec<i32>, Vec<Option<K>>)> = vec![Default::default(); nparts];
@@ -1717,18 +1749,20 @@ fn pwmj_parts_exec<K: PwmjFuzzKey>(
17171749
.enumerate()
17181750
.map(|(part, (ids, keys))| match stagger_seed {
17191751
// `stagger_batch_with_seed` panics on a batch with no rows.
1720-
_ if ids.is_empty() => vec![pwmj_kv_batch::<K>(&[], &[])],
1721-
Some(seed) => {
1722-
stagger_batch_with_seed(pwmj_kv_batch(ids, keys), seed + part as u64)
1723-
}
1752+
_ if ids.is_empty() => vec![pwmj_kv_batch::<K>(&[], &[], payload)],
1753+
Some(seed) => stagger_batch_with_seed(
1754+
pwmj_kv_batch(ids, keys, payload),
1755+
seed + part as u64,
1756+
),
17241757
None => ids
17251758
.iter()
17261759
.zip(keys)
1727-
.map(|(&id, key)| pwmj_kv_batch(&[id], &[*key]))
1760+
.map(|(&id, key)| pwmj_kv_batch(&[id], &[*key], payload))
17281761
.collect(),
17291762
})
17301763
.collect();
1731-
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema::<K>(), None).unwrap()
1764+
MemorySourceConfig::try_new_exec(&partitions, pwmj_kv_schema::<K>(payload), None)
1765+
.unwrap()
17321766
}
17331767

17341768
fn pwmj_plan(
@@ -1807,9 +1841,14 @@ fn pwmj_nlj_oracle_plan<K: PwmjFuzzKey>(
18071841
///
18081842
/// Concurrent rather than one partition at a time: the partitions share the watermark and race
18091843
/// to be the one that runs the final pass, which is the part a sequential drain cannot reach.
1844+
///
1845+
/// Every side present in the output also has its payload checked against its `id` (see
1846+
/// [`pwmj_check_payload`]), so a row paired with another row's payload fails here even though
1847+
/// the id pairs agree.
18101848
async fn pwmj_collect_id_pairs(
18111849
plan: Arc<dyn ExecutionPlan>,
18121850
task_ctx: Arc<TaskContext>,
1851+
payload: &DataType,
18131852
) -> Vec<(Option<i32>, Option<i32>)> {
18141853
let streams = (0..plan.output_partitioning().partition_count())
18151854
.map(|partition| plan.execute(partition, Arc::clone(&task_ctx)).unwrap())
@@ -1833,8 +1872,12 @@ async fn pwmj_collect_id_pairs(
18331872
for batches in per_partition {
18341873
for batch in batches.unwrap().unwrap() {
18351874
let left = id_column(&batch, 0);
1836-
// Left is (id, k), so the right side's `id` follows it -- when there is one.
1837-
let right = (batch.num_columns() > 2).then(|| id_column(&batch, 2));
1875+
pwmj_check_payload(&batch, 0, 2, payload);
1876+
// Left is (id, k, p), so the right side's `id` follows it -- when there is one.
1877+
let right = (batch.num_columns() > 3).then(|| {
1878+
pwmj_check_payload(&batch, 3, 5, payload);
1879+
id_column(&batch, 3)
1880+
});
18381881
for row in 0..batch.num_rows() {
18391882
pairs.push((
18401883
left.is_valid(row).then(|| left.value(row)),
@@ -1857,6 +1900,7 @@ async fn pwmj_collect_id_pairs(
18571900
async fn pwmj_collect_mark_pairs(
18581901
plan: Arc<dyn ExecutionPlan>,
18591902
task_ctx: Arc<TaskContext>,
1903+
payload: &DataType,
18601904
) -> Vec<(i32, bool)> {
18611905
let streams = (0..plan.output_partitioning().partition_count())
18621906
.map(|partition| plan.execute(partition, Arc::clone(&task_ctx)).unwrap())
@@ -1875,6 +1919,7 @@ async fn pwmj_collect_mark_pairs(
18751919
.as_any()
18761920
.downcast_ref::<Int32Array>()
18771921
.unwrap();
1922+
pwmj_check_payload(&batch, 0, 2, payload);
18781923
// `mark` is always the last column: it is appended after either side's own
18791924
// columns (see `build_join_schema`).
18801925
let mark = batch
@@ -1891,9 +1936,39 @@ async fn pwmj_collect_mark_pairs(
18911936
pairs
18921937
}
18931938

1939+
/// Asserts the payload column `payload_col` is of `payload` type and, row by row, holds the
1940+
/// payload of the `id` in `id_col`, or is NULL where that `id` is: a side the join filled with
1941+
/// NULLs.
1942+
fn pwmj_check_payload(
1943+
batch: &RecordBatch,
1944+
id_col: usize,
1945+
payload_col: usize,
1946+
payload: &DataType,
1947+
) {
1948+
let ids = batch
1949+
.column(id_col)
1950+
.as_primitive::<arrow::datatypes::Int32Type>();
1951+
let column = batch.column(payload_col);
1952+
assert_eq!(column.data_type(), payload);
1953+
let values = cast(column, &DataType::Utf8).unwrap();
1954+
let values = values.as_string::<i32>();
1955+
for row in 0..batch.num_rows() {
1956+
if ids.is_valid(row) {
1957+
assert!(
1958+
values.is_valid(row),
1959+
"NULL payload for id {}",
1960+
ids.value(row)
1961+
);
1962+
assert_eq!(values.value(row), pwmj_payload(ids.value(row)));
1963+
} else {
1964+
assert!(values.is_null(row), "payload on a NULL-filled row");
1965+
}
1966+
}
1967+
}
1968+
18941969
/// Differential test for every join type `PiecewiseMergeJoin` supports, against a
1895-
/// `NestedLoopJoin` oracle, run once over `i32` keys and once over `f64` keys via
1896-
/// [`run_pwmj_fuzz`].
1970+
/// `NestedLoopJoin` oracle, run over `i32` and `f64` keys, each with a `Utf8` and a `Utf8View`
1971+
/// payload, via [`run_pwmj_fuzz`].
18971972
///
18981973
/// `Left`/`Full` are the ones with teeth: their unmatched buffered rows are derived from the
18991974
/// shared `min_marked` watermark rather than materialized per row, and that encoding is only
@@ -1902,7 +1977,8 @@ async fn pwmj_collect_mark_pairs(
19021977
/// both run the streamed side at a single partition and the default batch size, so neither
19031978
/// covers several partitions racing to run the final pass, nor the mid-scan resume path a
19041979
/// small batch size forces. The `f64` pass adds `-0.0` and `NaN`, which `pwmj.slt` only
1905-
/// exercises via a handful of fixed rows.
1980+
/// exercises via a handful of fixed rows. The payloads check every output row carries its own
1981+
/// rows' strings, through the copy and gather paths that differ from fixed width.
19061982
#[tokio::test(flavor = "multi_thread")]
19071983
async fn fuzz_pwmj_matches_nested_loop() {
19081984
// A small batch size splits output across several coalesced batches even for these tiny
@@ -1913,11 +1989,16 @@ async fn fuzz_pwmj_matches_nested_loop() {
19131989
);
19141990
// `f64` keys run every dimension below a second time with `-0.0` and `NaN` mixed in, on
19151991
// top of what `i32` already covers with plain duplicates and NULLs.
1916-
run_pwmj_fuzz::<i32>(&task_ctx).await;
1917-
run_pwmj_fuzz::<f64>(&task_ctx).await;
1992+
for payload in [DataType::Utf8, DataType::Utf8View] {
1993+
run_pwmj_fuzz::<i32>(&task_ctx, &payload).await;
1994+
run_pwmj_fuzz::<f64>(&task_ctx, &payload).await;
1995+
}
19181996
}
19191997

1920-
async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskContext>) {
1998+
async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(
1999+
task_ctx: &Arc<TaskContext>,
2000+
payload: &DataType,
2001+
) {
19212002
let ops = [Operator::Lt, Operator::LtEq, Operator::Gt, Operator::GtEq];
19222003
let join_types = [
19232004
JoinType::Inner,
@@ -1965,9 +2046,15 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
19652046
// single-partition shape below never reaches.
19662047
let buffered = match join_type {
19672048
JoinType::RightSemi | JoinType::RightAnti | JoinType::RightMark => {
1968-
pwmj_parts_exec(&left_ids, &left_keys, buffered_nparts, None)
2049+
pwmj_parts_exec(
2050+
&left_ids,
2051+
&left_keys,
2052+
buffered_nparts,
2053+
None,
2054+
payload,
2055+
)
19692056
}
1970-
_ => pwmj_single_exec(&left_ids, &left_keys),
2057+
_ => pwmj_single_exec(&left_ids, &left_keys, payload),
19712058
};
19722059

19732060
// Mark joins output every row of their side with a `mark` column rather than
@@ -1982,28 +2069,31 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
19822069
&right_keys,
19832070
nparts,
19842071
stagger_seed,
2072+
payload,
19852073
),
19862074
op,
19872075
join_type,
19882076
),
19892077
Arc::clone(task_ctx),
2078+
payload,
19902079
)
19912080
.await;
19922081
let want = pwmj_collect_mark_pairs(
19932082
pwmj_nlj_oracle_plan::<K>(
1994-
pwmj_single_exec(&left_ids, &left_keys),
1995-
pwmj_single_exec(&right_ids, &right_keys),
2083+
pwmj_single_exec(&left_ids, &left_keys, payload),
2084+
pwmj_single_exec(&right_ids, &right_keys, payload),
19962085
op,
19972086
join_type,
19982087
),
19992088
Arc::clone(task_ctx),
2089+
payload,
20002090
)
20012091
.await;
20022092

20032093
assert_eq!(
20042094
got,
20052095
want,
2006-
"mismatch key_type={} seed={seed} op={op:?} join_type={join_type:?} \
2096+
"mismatch key_type={} payload={payload} seed={seed} op={op:?} join_type={join_type:?} \
20072097
nparts={nparts} buffered_nparts={buffered_nparts} \
20082098
left_keys={left_keys:?} right_keys={right_keys:?}",
20092099
std::any::type_name::<K>(),
@@ -2014,28 +2104,36 @@ async fn run_pwmj_fuzz<K: PwmjFuzzKey + std::fmt::Debug>(task_ctx: &Arc<TaskCont
20142104
let got = pwmj_collect_id_pairs(
20152105
pwmj_plan(
20162106
buffered,
2017-
pwmj_parts_exec(&right_ids, &right_keys, nparts, stagger_seed),
2107+
pwmj_parts_exec(
2108+
&right_ids,
2109+
&right_keys,
2110+
nparts,
2111+
stagger_seed,
2112+
payload,
2113+
),
20182114
op,
20192115
join_type,
20202116
),
20212117
Arc::clone(task_ctx),
2118+
payload,
20222119
)
20232120
.await;
20242121
let want = pwmj_collect_id_pairs(
20252122
pwmj_nlj_oracle_plan::<K>(
2026-
pwmj_single_exec(&left_ids, &left_keys),
2027-
pwmj_single_exec(&right_ids, &right_keys),
2123+
pwmj_single_exec(&left_ids, &left_keys, payload),
2124+
pwmj_single_exec(&right_ids, &right_keys, payload),
20282125
op,
20292126
join_type,
20302127
),
20312128
Arc::clone(task_ctx),
2129+
payload,
20322130
)
20332131
.await;
20342132

20352133
assert_eq!(
20362134
got,
20372135
want,
2038-
"mismatch key_type={} seed={seed} op={op:?} join_type={join_type:?} \
2136+
"mismatch key_type={} payload={payload} seed={seed} op={op:?} join_type={join_type:?} \
20392137
nparts={nparts} buffered_nparts={buffered_nparts} \
20402138
left_keys={left_keys:?} right_keys={right_keys:?}",
20412139
std::any::type_name::<K>(),
@@ -2141,17 +2239,19 @@ async fn pwmj_watermark_nulls_duplicates_multi_partition() {
21412239

21422240
let got = pwmj_collect_id_pairs(
21432241
pwmj_plan(
2144-
pwmj_single_exec(&left_ids, &left_keys),
2242+
pwmj_single_exec(&left_ids, &left_keys, &DataType::Utf8View),
21452243
pwmj_parts_exec(
21462244
&case.streamed_ids,
21472245
&case.streamed_keys,
21482246
nparts,
21492247
None,
2248+
&DataType::Utf8View,
21502249
),
21512250
Operator::Lt,
21522251
join_type,
21532252
),
21542253
Arc::clone(&task_ctx),
2254+
&DataType::Utf8View,
21552255
)
21562256
.await;
21572257

0 commit comments

Comments
 (0)