|
| 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); |
0 commit comments