Skip to content

Commit d52523e

Browse files
committed
Modify bench
1 parent 6ae681d commit d52523e

4 files changed

Lines changed: 236 additions & 233 deletions

File tree

‎datafusion/core/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -205,6 +205,10 @@ name = "distinct_query_sql"
205205
harness = false
206206
name = "push_down_filter"
207207

208+
[[bench]]
209+
harness = false
210+
name = "pwmj_semi_anti_sql"
211+
208212
[[bench]]
209213
harness = false
210214
name = "sort_limit_query_sql"
Lines changed: 232 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,232 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Criterion benchmark for existence subqueries (`EXISTS` / `NOT EXISTS`) whose
19+
//! correlation is a range predicate (`lhs.key < rhs.key`). The query is planned end to
20+
//! end from SQL, with `datafusion.optimizer.enable_piecewise_merge_join` toggled to pick
21+
//! the operator under test:
22+
//!
23+
//! - **on**: the subquery is decorrelated to a `LeftSemi` / `LeftAnti` join and planned as
24+
//! `PiecewiseMergeJoin`, together with the `SortExec` the planner inserts on the
25+
//! buffered side. The sort is included because it is a real cost of that plan.
26+
//! - **off**: the same join falls back to `NestedLoopJoinExec`, which is O(n*m).
27+
//!
28+
//! Both arms compute the same result, so the comparison measures the win from routing an
29+
//! inequality-correlated `EXISTS` / `NOT EXISTS` to PWMJ instead of the nested-loop join.
30+
//!
31+
//! Each arm asserts up front that the operator it means to measure is actually in the
32+
//! physical plan. Without that check a planning change (or running this against a build
33+
//! where PWMJ does not accept existence joins) would silently compare
34+
//! `NestedLoopJoinExec` against itself and report a meaningless ~1.0x.
35+
//!
36+
//! ## Axes
37+
//! - **join type**: `EXISTS` (LeftSemi) and `NOT EXISTS` (LeftAnti).
38+
//! - **match regime**: the fraction of left rows that have at least one matching right
39+
//! row, set by shifting the right-side key range relative to the left one:
40+
//! `all_match` (100%), `no_match` (0%) and `half_match` (~50%, where the buffered side
41+
//! ends up only partially marked). Semi output size grows with that fraction; Anti
42+
//! output size shrinks.
43+
44+
use std::sync::Arc;
45+
46+
use arrow::array::{Int32Array, RecordBatch};
47+
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
48+
use criterion::{BatchSize, BenchmarkId, Criterion, criterion_group, criterion_main};
49+
use datafusion::datasource::MemTable;
50+
use datafusion::physical_plan::{ExecutionPlan, collect, displayable};
51+
use datafusion::prelude::{SessionConfig, SessionContext};
52+
use tokio::runtime::Runtime;
53+
54+
const LEFT_ROWS: usize = 20_000;
55+
const RIGHT_ROWS: usize = 20_000;
56+
const KEY_SPAN: i32 = 10_000;
57+
58+
/// Two-column schema: (`key`, `payload`).
59+
fn schema() -> SchemaRef {
60+
Arc::new(Schema::new(vec![
61+
Field::new("key", DataType::Int32, false),
62+
Field::new("payload", DataType::Int32, false),
63+
]))
64+
}
65+
66+
/// Build the batches for a single-partition table of `num_rows` rows. Keys are drawn from
67+
/// `[key_offset, key_offset + KEY_SPAN)` in a fixed, reproducible pattern (no RNG so the
68+
/// benchmark is deterministic).
69+
fn build_batches(
70+
num_rows: usize,
71+
key_offset: i32,
72+
schema: &SchemaRef,
73+
) -> Vec<RecordBatch> {
74+
let keys: Vec<i32> = (0..num_rows)
75+
.map(|i| {
76+
key_offset
77+
+ (i as i32)
78+
.wrapping_mul(2_654_435_761u32 as i32)
79+
.rem_euclid(KEY_SPAN)
80+
})
81+
.collect();
82+
let payload: Vec<i32> = (0..num_rows as i32).collect();
83+
let batch = RecordBatch::try_new(
84+
Arc::clone(schema),
85+
vec![
86+
Arc::new(Int32Array::from(keys)),
87+
Arc::new(Int32Array::from(payload)),
88+
],
89+
)
90+
.unwrap();
91+
92+
// Slice into 8192-row batches to mirror a realistic scan.
93+
let batch_size = 8192;
94+
let mut batches = Vec::new();
95+
let mut offset = 0;
96+
while offset < batch.num_rows() {
97+
let len = (batch.num_rows() - offset).min(batch_size);
98+
batches.push(batch.slice(offset, len));
99+
offset += len;
100+
}
101+
batches
102+
}
103+
104+
/// Register `lhs` and `rhs` in a context with PWMJ planning on or off.
105+
fn create_context(right_offset: i32, pwmj: bool, schema: &SchemaRef) -> SessionContext {
106+
let config = SessionConfig::new()
107+
// Pinned so results are comparable across machines, and so the comparison
108+
// isolates the join operator rather than how much repartitioning surrounds it.
109+
.with_target_partitions(1)
110+
.set_bool("datafusion.optimizer.enable_piecewise_merge_join", pwmj);
111+
let ctx = SessionContext::new_with_config(config);
112+
113+
for (name, key_offset, num_rows) in
114+
[("lhs", 0, LEFT_ROWS), ("rhs", right_offset, RIGHT_ROWS)]
115+
{
116+
let table = MemTable::try_new(
117+
Arc::clone(schema),
118+
vec![build_batches(num_rows, key_offset, schema)],
119+
)
120+
.unwrap();
121+
ctx.register_table(name, Arc::new(table)).unwrap();
122+
}
123+
ctx
124+
}
125+
126+
/// `EXISTS` / `NOT EXISTS` over the range correlation `lhs.key < rhs.key`.
127+
fn query(exists: bool) -> String {
128+
let negation = if exists { "" } else { "NOT " };
129+
format!(
130+
"SELECT lhs.key, lhs.payload FROM lhs \
131+
WHERE {negation}EXISTS (SELECT 1 FROM rhs WHERE lhs.key < rhs.key)"
132+
)
133+
}
134+
135+
fn physical_plan(
136+
ctx: &SessionContext,
137+
rt: &Runtime,
138+
sql: &str,
139+
) -> Arc<dyn ExecutionPlan> {
140+
rt.block_on(async {
141+
ctx.sql(sql)
142+
.await
143+
.unwrap()
144+
.create_physical_plan()
145+
.await
146+
.unwrap()
147+
})
148+
}
149+
150+
/// Fail loudly if the plan does not contain every expected fragment, so an arm can never
151+
/// silently measure an operator other than the one it is named after.
152+
fn assert_plan_contains(plan: &Arc<dyn ExecutionPlan>, expected: &[&str], label: &str) {
153+
let displayed = displayable(plan.as_ref()).indent(false).to_string();
154+
for fragment in expected {
155+
assert!(
156+
displayed.contains(fragment),
157+
"{label}: expected `{fragment}` in the physical plan, got:\n{displayed}"
158+
);
159+
}
160+
}
161+
162+
fn run(plan: Arc<dyn ExecutionPlan>, ctx: &SessionContext, rt: &Runtime) -> usize {
163+
rt.block_on(async {
164+
let batches = collect(plan, ctx.task_ctx()).await.unwrap();
165+
batches.iter().map(|b| b.num_rows()).sum()
166+
})
167+
}
168+
169+
fn bench_pwmj_semi_anti_sql(c: &mut Criterion) {
170+
let rt = Runtime::new().unwrap();
171+
let s = schema();
172+
173+
// An existence join needs only *one* match per left row, so all that matters is where
174+
// `max(rhs.key)` falls inside the left range: a left row survives `EXISTS` iff
175+
// `lhs.key < max(rhs.key)`. Shifting the right range up therefore saturates at
176+
// all-match; only shifting it *down* leaves part of the left side unmatched.
177+
let regimes: [(&str, i32); 3] = [
178+
// Right keys entirely above the left range: every left row matches.
179+
("all_match", KEY_SPAN),
180+
// Right keys entirely below the left range: no left row matches, so the scan
181+
// walks the whole buffered side without marking anything.
182+
("no_match", -KEY_SPAN),
183+
// Ranges half-overlap: ~50% of left rows match, so only a suffix of the buffered
184+
// side gets marked and the scan depth varies per streamed row.
185+
("half_match", -KEY_SPAN / 2),
186+
];
187+
188+
let mut group = c.benchmark_group("pwmj_vs_nlj_semi_anti_sql");
189+
// Nested-loop is O(n*m); keep sample counts modest so the suite finishes.
190+
group.sample_size(10);
191+
192+
for (regime, right_offset) in regimes {
193+
// Only the Semi/Anti half of the join type is pinned, not the side: with PWMJ
194+
// disabled the planner swaps the nested-loop inputs, so the same `EXISTS` plans as
195+
// `RightSemi` there and `LeftSemi` under PWMJ.
196+
for (exists, join_type) in [(true, "Semi"), (false, "Anti")] {
197+
let sql = query(exists);
198+
let label = if exists { "semi" } else { "anti" };
199+
200+
for (arm, pwmj, operator) in [
201+
("pwmj", true, "PiecewiseMergeJoin"),
202+
("nlj", false, "NestedLoopJoinExec"),
203+
] {
204+
let ctx = create_context(right_offset, pwmj, &s);
205+
let name = format!("{arm}_{label}_{regime}");
206+
assert_plan_contains(
207+
&physical_plan(&ctx, &rt, &sql),
208+
&[operator, join_type],
209+
&name,
210+
);
211+
212+
// Plan afresh in the untimed setup rather than reusing one plan: the
213+
// buffered side of `PiecewiseMergeJoinExec` (its visited-indices bitmap
214+
// and final-pass partition counter) is cached in a `OnceAsync` on the
215+
// exec, so a second `collect` over the same instance would not repeat
216+
// the work.
217+
group.bench_function(BenchmarkId::new(name, RIGHT_ROWS), |b| {
218+
b.iter_batched(
219+
|| physical_plan(&ctx, &rt, &sql),
220+
|plan| run(plan, &ctx, &rt),
221+
BatchSize::SmallInput,
222+
)
223+
});
224+
}
225+
}
226+
}
227+
228+
group.finish();
229+
}
230+
231+
criterion_group!(benches, bench_pwmj_semi_anti_sql);
232+
criterion_main!(benches);

‎datafusion/physical-plan/Cargo.toml‎

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -139,11 +139,6 @@ harness = false
139139
name = "hash_join_semi_anti"
140140
required-features = ["test_utils"]
141141

142-
[[bench]]
143-
harness = false
144-
name = "piecewise_merge_join_semi_anti"
145-
required-features = ["test_utils"]
146-
147142
[[bench]]
148143
harness = false
149144
name = "multi_group_by"

0 commit comments

Comments
 (0)