Skip to content

Commit b87bc6c

Browse files
Abhisheklearn12Omega359
authored andcommitted
bench: add AND conjunction benchmarks to binary_op (apache#25870)
## Which issue does this PR close? - Part of apache#25035. Split out from apache#25771 as requested, so the evaluator change there can be benchmarked against `main`. ## Rationale for this change On `main`, a left-deep `AND` chain can be several times slower than the same chain built right-deep, once the prefix drops below the pre-selection threshold (apache#25035). The existing `binary_op` benchmarks don't cover this. ## What changes are included in this PR? A `conjunction` group in `datafusion/physical-expr/benches/binary_op.rs`: left-deep and right-deep `AND` chains of cheap comparisons, casts, `IN` lists and arithmetic, with and without unused columns, plus nullable and regex-suffix variants. Only this file changes; no engine code. ## What is the testing strategy for this PR? Benchmark only. All `binary_op` benchmarks run on `main` (`cargo test --bench binary_op`). Run with `cargo bench --bench binary_op -- conjunction`. ## Are there any user-facing changes? No.
1 parent af207b9 commit b87bc6c

1 file changed

Lines changed: 186 additions & 1 deletion

File tree

‎datafusion/physical-expr/benches/binary_op.rs‎

Lines changed: 186 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,18 +15,22 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18+
use arrow::array::{ArrayRef, Int32Array, Int64Array};
1819
use arrow::{array::StringArray, record_batch::RecordBatch};
1920
use arrow::{
2021
array::{BooleanArray, Date32Array, Date64Array},
2122
datatypes::{DataType, Field, Schema},
2223
};
2324
use criterion::{Criterion, criterion_group, criterion_main};
25+
use datafusion_common::ScalarValue;
2426
use datafusion_expr::{Operator, and, binary_expr, col, lit, or};
2527
use datafusion_physical_expr::{
2628
PhysicalExpr,
27-
expressions::{BinaryExpr, Column},
29+
expressions::{BinaryExpr, Column, Literal, cast, in_list},
2830
planner::logical2physical,
2931
};
32+
use rand::rngs::StdRng;
33+
use rand::{Rng, SeedableRng};
3034
use std::hint::black_box;
3135
use std::sync::Arc;
3236

@@ -234,6 +238,186 @@ fn benchmark_binary_op_in_short_circuit(c: &mut Criterion) {
234238
}
235239
}
236240

241+
/// How each conjunct in [`benchmark_conjunction`] tests its column.
242+
#[derive(Clone, Copy, PartialEq)]
243+
enum ConjunctKind {
244+
/// `c < x`
245+
Lt,
246+
/// `CAST(c AS BIGINT) < x`
247+
CastLt,
248+
/// `c IN (...)`
249+
InList,
250+
/// `c + 1 < x`
251+
Plus,
252+
}
253+
254+
/// Benchmarks left- and right-deep `AND` chains across selectivity, expression
255+
/// types, NULLs, and unused columns (#25035).
256+
///
257+
/// Run with `cargo bench --bench binary_op -- conjunction`.
258+
fn benchmark_conjunction(c: &mut Criterion) {
259+
use ConjunctKind::*;
260+
const NUM_ROWS: usize = 8192;
261+
let mut rng = StdRng::seed_from_u64(25035);
262+
let urls = generate_test_strings(NUM_ROWS).0;
263+
264+
// (per-conjunct pass rates, label, kind, null rate, regex suffix)
265+
for (pass_rates, pass_rate_label, kind, null_rate, regex) in [
266+
(&[0.5; 4] as &[f64], "0.5", Lt, 0.0, false),
267+
(&[0.7; 8], "0.7", Lt, 0.0, false),
268+
(&[0.9; 8], "0.9", Lt, 0.0, false),
269+
(&[0.7; 16], "0.7", Lt, 0.0, false),
270+
(&[0.7; 8], "0.7", Lt, 0.0, true),
271+
(&[0.7; 8], "0.7", CastLt, 0.0, false),
272+
(&[0.7; 8], "0.7", InList, 0.0, false),
273+
// Nulls disable pre-selection (check_short_circuit returns None when the
274+
// LHS has nulls), so both shapes should match; baseline for an n-ary fix.
275+
(&[0.5; 4], "0.5", Lt, 0.1, true),
276+
(&[0.7; 8], "0.7", Plus, 0.0, false),
277+
// Selective c0 enables pre-selection in both shapes. Cover cheap and
278+
// expensive remaining work to catch regressions where it helps today.
279+
(
280+
&[0.1, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9],
281+
"0.1_then0.9",
282+
Lt,
283+
0.0,
284+
false,
285+
),
286+
(
287+
&[0.1, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9],
288+
"0.1_then0.9",
289+
Lt,
290+
0.0,
291+
true,
292+
),
293+
] {
294+
let num_conjuncts = pass_rates.len();
295+
// `InList` draws values from 0..10, the others from 0..1000.
296+
let domain = if kind == InList { 10 } else { 1000 };
297+
let conjunct_schema = Schema::new(
298+
(0..num_conjuncts)
299+
.map(|i| Field::new(format!("c{i}"), DataType::Int32, null_rate > 0.0))
300+
.collect::<Vec<_>>(),
301+
);
302+
let mut conjuncts: Vec<Arc<dyn PhysicalExpr>> = pass_rates
303+
.iter()
304+
.enumerate()
305+
.map(|(i, pass_rate)| {
306+
let cutoff = (pass_rate * domain as f64) as i32;
307+
let column = Arc::new(Column::new(&format!("c{i}"), i)) as _;
308+
match kind {
309+
Lt => Arc::new(BinaryExpr::new(
310+
column,
311+
Operator::Lt,
312+
Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff)))),
313+
)) as _,
314+
CastLt => Arc::new(BinaryExpr::new(
315+
cast(column, &conjunct_schema, DataType::Int64).unwrap(),
316+
Operator::Lt,
317+
Arc::new(Literal::new(ScalarValue::Int64(Some(cutoff as i64)))),
318+
)),
319+
Plus => Arc::new(BinaryExpr::new(
320+
Arc::new(BinaryExpr::new(
321+
column,
322+
Operator::Plus,
323+
Arc::new(Literal::new(ScalarValue::Int32(Some(1)))),
324+
)),
325+
Operator::Lt,
326+
Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff + 1)))),
327+
)),
328+
InList => in_list(
329+
column,
330+
(0..cutoff)
331+
.map(|v| {
332+
Arc::new(Literal::new(ScalarValue::Int32(Some(v)))) as _
333+
})
334+
.collect(),
335+
&false,
336+
&conjunct_schema,
337+
)
338+
.unwrap(),
339+
}
340+
})
341+
.collect();
342+
if regex {
343+
conjuncts.push(Arc::new(BinaryExpr::new(
344+
Arc::new(Column::new("url", num_conjuncts)),
345+
Operator::RegexMatch,
346+
Arc::new(Literal::new(ScalarValue::from(
347+
r#"^https://(\w+\.)?example\.(com|org)/"#,
348+
))),
349+
)));
350+
}
351+
let left_deep = conjuncts
352+
.iter()
353+
.cloned()
354+
.reduce(|l, r| Arc::new(BinaryExpr::new(l, Operator::And, r)))
355+
.unwrap();
356+
let right_deep = conjuncts
357+
.iter()
358+
.cloned()
359+
.rev()
360+
.reduce(|r, l| Arc::new(BinaryExpr::new(l, Operator::And, r)))
361+
.unwrap();
362+
363+
let conjunct_columns: Vec<ArrayRef> = (0..num_conjuncts)
364+
.map(|_| {
365+
Arc::new(if null_rate > 0.0 {
366+
Int32Array::from_iter((0..NUM_ROWS).map(|_| {
367+
let value = rng.random_range(0..domain);
368+
(!rng.random_bool(null_rate)).then_some(value)
369+
}))
370+
} else {
371+
Int32Array::from_iter_values(
372+
(0..NUM_ROWS).map(|_| rng.random_range(0..domain)),
373+
)
374+
}) as ArrayRef
375+
})
376+
.collect();
377+
378+
for payload_columns in [0, 32] {
379+
let mut fields = conjunct_schema.fields().to_vec();
380+
let mut columns = conjunct_columns.clone();
381+
if regex {
382+
fields.push(Arc::new(Field::new("url", DataType::Utf8, false)));
383+
columns.push(Arc::new(StringArray::from(urls.clone())));
384+
}
385+
for i in 0..payload_columns {
386+
fields.push(Arc::new(Field::new(
387+
format!("p{i}"),
388+
DataType::Int64,
389+
false,
390+
)));
391+
columns.push(Arc::new(Int64Array::from_iter_values(
392+
(0..NUM_ROWS).map(|_| rng.random()),
393+
)));
394+
}
395+
let batch =
396+
RecordBatch::try_new(Arc::new(Schema::new(fields)), columns).unwrap();
397+
398+
let suffix = [
399+
(kind == CastLt, "_cast"),
400+
(kind == InList, "_inlist"),
401+
(kind == Plus, "_plus"),
402+
(null_rate > 0.0, "_nulls"),
403+
(regex, "_regex"),
404+
]
405+
.into_iter()
406+
.filter_map(|(on, tag)| on.then_some(tag))
407+
.collect::<String>();
408+
for (shape, expr) in [("left_deep", &left_deep), ("right_deep", &right_deep)]
409+
{
410+
c.bench_function(
411+
&format!(
412+
"conjunction/k{num_conjuncts}_p{pass_rate_label}{suffix}_w{payload_columns}/{shape}"
413+
),
414+
|b| b.iter(|| expr.evaluate(black_box(&batch)).unwrap()),
415+
);
416+
}
417+
}
418+
}
419+
}
420+
237421
/// Generate test data with computationally expensive patterns
238422
fn generate_test_strings(num_rows: usize) -> (Vec<String>, Vec<String>) {
239423
// Extended URL patterns with query parameters and paths
@@ -385,6 +569,7 @@ fn benchmark_date64_subtract(c: &mut Criterion) {
385569
criterion_group!(
386570
benches,
387571
benchmark_binary_op_in_short_circuit,
572+
benchmark_conjunction,
388573
benchmark_date32_subtract,
389574
benchmark_date64_subtract
390575
);

0 commit comments

Comments
 (0)