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 22:57:14 UTC
(datafusion) branch gh-readonly-queue/main/pr-25870-b9c8b3dce8038372c24a48525d2f1fc0e81c5e83 created (now 5ecf2915f1)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-25870-b9c8b3dce8038372c24a48525d2f1fc0e81c5e83
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 5ecf2915f1 bench: add AND conjunction benchmarks to binary_op (#25870)
This branch includes the following new commits:
new 5ecf2915f1 bench: add AND conjunction benchmarks to binary_op (#25870)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: bench: add AND conjunction benchmarks to binary_op (#25870)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25870-b9c8b3dce8038372c24a48525d2f1fc0e81c5e83
in repository https://gitbox.apache.org/repos/asf/datafusion.git
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