You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/29 23:06:20 UTC
(datafusion) branch main updated: bench: add AND conjunction benchmarks to binary_op (#25870)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git
The following commit(s) were added to refs/heads/main by this push:
new 5ecf2915f1 bench: add AND conjunction benchmarks to binary_op (#25870)
5ecf2915f1 is described below
commit 5ecf2915f1c8a682b4da9bd55acb128e3780bbc3
Author: Abhishek <16...@users.noreply.github.com>
AuthorDate: Tue Sep 29 22:56:51 2026 +0000
bench: add AND conjunction benchmarks to binary_op (#25870)
## Which issue does this PR close?
- Part of #25035. Split out from #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 (#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.
---
datafusion/physical-expr/benches/binary_op.rs | 187 +++++++++++++++++++++++++-
1 file changed, 186 insertions(+), 1 deletion(-)
diff --git a/datafusion/physical-expr/benches/binary_op.rs b/datafusion/physical-expr/benches/binary_op.rs
index f170561652..acb5ceae31 100644
--- a/datafusion/physical-expr/benches/binary_op.rs
+++ b/datafusion/physical-expr/benches/binary_op.rs
@@ -15,18 +15,22 @@
// specific language governing permissions and limitations
// under the License.
+use arrow::array::{ArrayRef, Int32Array, Int64Array};
use arrow::{array::StringArray, record_batch::RecordBatch};
use arrow::{
array::{BooleanArray, Date32Array, Date64Array},
datatypes::{DataType, Field, Schema},
};
use criterion::{Criterion, criterion_group, criterion_main};
+use datafusion_common::ScalarValue;
use datafusion_expr::{Operator, and, binary_expr, col, lit, or};
use datafusion_physical_expr::{
PhysicalExpr,
- expressions::{BinaryExpr, Column},
+ expressions::{BinaryExpr, Column, Literal, cast, in_list},
planner::logical2physical,
};
+use rand::rngs::StdRng;
+use rand::{Rng, SeedableRng};
use std::hint::black_box;
use std::sync::Arc;
@@ -234,6 +238,186 @@ fn benchmark_binary_op_in_short_circuit(c: &mut Criterion) {
}
}
+/// How each conjunct in [`benchmark_conjunction`] tests its column.
+#[derive(Clone, Copy, PartialEq)]
+enum ConjunctKind {
+ /// `c < x`
+ Lt,
+ /// `CAST(c AS BIGINT) < x`
+ CastLt,
+ /// `c IN (...)`
+ InList,
+ /// `c + 1 < x`
+ Plus,
+}
+
+/// Benchmarks left- and right-deep `AND` chains across selectivity, expression
+/// types, NULLs, and unused columns (#25035).
+///
+/// Run with `cargo bench --bench binary_op -- conjunction`.
+fn benchmark_conjunction(c: &mut Criterion) {
+ use ConjunctKind::*;
+ const NUM_ROWS: usize = 8192;
+ let mut rng = StdRng::seed_from_u64(25035);
+ let urls = generate_test_strings(NUM_ROWS).0;
+
+ // (per-conjunct pass rates, label, kind, null rate, regex suffix)
+ for (pass_rates, pass_rate_label, kind, null_rate, regex) in [
+ (&[0.5; 4] as &[f64], "0.5", Lt, 0.0, false),
+ (&[0.7; 8], "0.7", Lt, 0.0, false),
+ (&[0.9; 8], "0.9", Lt, 0.0, false),
+ (&[0.7; 16], "0.7", Lt, 0.0, false),
+ (&[0.7; 8], "0.7", Lt, 0.0, true),
+ (&[0.7; 8], "0.7", CastLt, 0.0, false),
+ (&[0.7; 8], "0.7", InList, 0.0, false),
+ // Nulls disable pre-selection (check_short_circuit returns None when the
+ // LHS has nulls), so both shapes should match; baseline for an n-ary fix.
+ (&[0.5; 4], "0.5", Lt, 0.1, true),
+ (&[0.7; 8], "0.7", Plus, 0.0, false),
+ // Selective c0 enables pre-selection in both shapes. Cover cheap and
+ // expensive remaining work to catch regressions where it helps today.
+ (
+ &[0.1, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9],
+ "0.1_then0.9",
+ Lt,
+ 0.0,
+ false,
+ ),
+ (
+ &[0.1, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9, 0.9],
+ "0.1_then0.9",
+ Lt,
+ 0.0,
+ true,
+ ),
+ ] {
+ let num_conjuncts = pass_rates.len();
+ // `InList` draws values from 0..10, the others from 0..1000.
+ let domain = if kind == InList { 10 } else { 1000 };
+ let conjunct_schema = Schema::new(
+ (0..num_conjuncts)
+ .map(|i| Field::new(format!("c{i}"), DataType::Int32, null_rate > 0.0))
+ .collect::<Vec<_>>(),
+ );
+ let mut conjuncts: Vec<Arc<dyn PhysicalExpr>> = pass_rates
+ .iter()
+ .enumerate()
+ .map(|(i, pass_rate)| {
+ let cutoff = (pass_rate * domain as f64) as i32;
+ let column = Arc::new(Column::new(&format!("c{i}"), i)) as _;
+ match kind {
+ Lt => Arc::new(BinaryExpr::new(
+ column,
+ Operator::Lt,
+ Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff)))),
+ )) as _,
+ CastLt => Arc::new(BinaryExpr::new(
+ cast(column, &conjunct_schema, DataType::Int64).unwrap(),
+ Operator::Lt,
+ Arc::new(Literal::new(ScalarValue::Int64(Some(cutoff as i64)))),
+ )),
+ Plus => Arc::new(BinaryExpr::new(
+ Arc::new(BinaryExpr::new(
+ column,
+ Operator::Plus,
+ Arc::new(Literal::new(ScalarValue::Int32(Some(1)))),
+ )),
+ Operator::Lt,
+ Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff + 1)))),
+ )),
+ InList => in_list(
+ column,
+ (0..cutoff)
+ .map(|v| {
+ Arc::new(Literal::new(ScalarValue::Int32(Some(v)))) as _
+ })
+ .collect(),
+ &false,
+ &conjunct_schema,
+ )
+ .unwrap(),
+ }
+ })
+ .collect();
+ if regex {
+ conjuncts.push(Arc::new(BinaryExpr::new(
+ Arc::new(Column::new("url", num_conjuncts)),
+ Operator::RegexMatch,
+ Arc::new(Literal::new(ScalarValue::from(
+ r#"^https://(\w+\.)?example\.(com|org)/"#,
+ ))),
+ )));
+ }
+ let left_deep = conjuncts
+ .iter()
+ .cloned()
+ .reduce(|l, r| Arc::new(BinaryExpr::new(l, Operator::And, r)))
+ .unwrap();
+ let right_deep = conjuncts
+ .iter()
+ .cloned()
+ .rev()
+ .reduce(|r, l| Arc::new(BinaryExpr::new(l, Operator::And, r)))
+ .unwrap();
+
+ let conjunct_columns: Vec<ArrayRef> = (0..num_conjuncts)
+ .map(|_| {
+ Arc::new(if null_rate > 0.0 {
+ Int32Array::from_iter((0..NUM_ROWS).map(|_| {
+ let value = rng.random_range(0..domain);
+ (!rng.random_bool(null_rate)).then_some(value)
+ }))
+ } else {
+ Int32Array::from_iter_values(
+ (0..NUM_ROWS).map(|_| rng.random_range(0..domain)),
+ )
+ }) as ArrayRef
+ })
+ .collect();
+
+ for payload_columns in [0, 32] {
+ let mut fields = conjunct_schema.fields().to_vec();
+ let mut columns = conjunct_columns.clone();
+ if regex {
+ fields.push(Arc::new(Field::new("url", DataType::Utf8, false)));
+ columns.push(Arc::new(StringArray::from(urls.clone())));
+ }
+ for i in 0..payload_columns {
+ fields.push(Arc::new(Field::new(
+ format!("p{i}"),
+ DataType::Int64,
+ false,
+ )));
+ columns.push(Arc::new(Int64Array::from_iter_values(
+ (0..NUM_ROWS).map(|_| rng.random()),
+ )));
+ }
+ let batch =
+ RecordBatch::try_new(Arc::new(Schema::new(fields)), columns).unwrap();
+
+ let suffix = [
+ (kind == CastLt, "_cast"),
+ (kind == InList, "_inlist"),
+ (kind == Plus, "_plus"),
+ (null_rate > 0.0, "_nulls"),
+ (regex, "_regex"),
+ ]
+ .into_iter()
+ .filter_map(|(on, tag)| on.then_some(tag))
+ .collect::<String>();
+ for (shape, expr) in [("left_deep", &left_deep), ("right_deep", &right_deep)]
+ {
+ c.bench_function(
+ &format!(
+ "conjunction/k{num_conjuncts}_p{pass_rate_label}{suffix}_w{payload_columns}/{shape}"
+ ),
+ |b| b.iter(|| expr.evaluate(black_box(&batch)).unwrap()),
+ );
+ }
+ }
+ }
+}
+
/// Generate test data with computationally expensive patterns
fn generate_test_strings(num_rows: usize) -> (Vec<String>, Vec<String>) {
// Extended URL patterns with query parameters and paths
@@ -385,6 +569,7 @@ fn benchmark_date64_subtract(c: &mut Criterion) {
criterion_group!(
benches,
benchmark_binary_op_in_short_circuit,
+ benchmark_conjunction,
benchmark_date32_subtract,
benchmark_date64_subtract
);
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org