adriangb commented on code in PR #25870:
URL: https://github.com/apache/datafusion/pull/25870#discussion_r4135985491
##########
datafusion/physical-expr/benches/binary_op.rs:
##########
@@ -234,6 +238,162 @@ 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;
+
+ // (conjuncts, pass rate, kind, null rate, regex suffix)
+ for (num_conjuncts, pass_rate, kind, null_rate, regex) in [
+ (4, 0.5, Lt, 0.0, false),
Review Comment:
Could we add a config with a selective first conjunct, e.g. pass rate ≤ 0.2
on c0, or mixed rates like `[0.1, 0.9, 0.9, …]`? Right now every conjunct
passes more than 20% of rows, so right_deep never pre-selects. Today that's the
case where pre-selection helps both shapes, and it's the one a rewrite of the
AND-chain evaluation is most likely to slow down without us noticing. This
probably means taking a per-conjunct pass rate instead of a single `pass_rate`.
##########
datafusion/physical-expr/benches/binary_op.rs:
##########
@@ -234,6 +238,162 @@ 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;
+
+ // (conjuncts, pass rate, kind, null rate, regex suffix)
+ for (num_conjuncts, pass_rate, kind, null_rate, regex) in [
+ (4, 0.5, Lt, 0.0, false),
+ (8, 0.7, Lt, 0.0, false),
+ (8, 0.9, Lt, 0.0, false),
+ (16, 0.7, Lt, 0.0, false),
+ (8, 0.7, Lt, 0.0, true),
+ (8, 0.7, CastLt, 0.0, false),
+ (8, 0.7, InList, 0.0, false),
+ (4, 0.5, Lt, 0.1, true),
Review Comment:
`check_short_circuit` returns None whenever the LHS contains any nulls, so
with nulls in every column neither shape ever pre-selects, and left_deep and
right_deep should time the same here. That's still a useful baseline for an
n-ary fix that has to handle three-valued logic, but could we note it so people
reading the results don't expect a gap?
```suggestion
// 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.
(4, 0.5, Lt, 0.1, true),
```
##########
datafusion/physical-expr/benches/binary_op.rs:
##########
@@ -234,6 +238,162 @@ 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;
+
+ // (conjuncts, pass rate, kind, null rate, regex suffix)
+ for (num_conjuncts, pass_rate, kind, null_rate, regex) in [
+ (4, 0.5, Lt, 0.0, false),
+ (8, 0.7, Lt, 0.0, false),
+ (8, 0.9, Lt, 0.0, false),
+ (16, 0.7, Lt, 0.0, false),
+ (8, 0.7, Lt, 0.0, true),
+ (8, 0.7, CastLt, 0.0, false),
+ (8, 0.7, InList, 0.0, false),
+ (4, 0.5, Lt, 0.1, true),
+ (8, 0.7, Plus, 0.0, false),
+ ] {
+ // `InList` draws values from 0..10, the others from 0..1000.
+ let domain = if kind == InList { 10 } else { 1000 };
+ let cutoff = (pass_rate * domain as f64) as i32;
+ 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>> = (0..num_conjuncts)
+ .map(|i| {
+ 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();
+
+ for payload_columns in [0, 32] {
+ let mut fields = conjunct_schema.fields().to_vec();
+ let mut columns: Vec<ArrayRef> = vec![];
+ for _ in 0..num_conjuncts {
+ columns.push(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)),
+ )
+ }));
+ }
Review Comment:
Nit: the conjunct columns are generated inside this loop, so the RNG keeps
advancing and _w0/_w32 run on different data. Generating them once before the
loop makes the comparison purely about width:
```suggestion
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();
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
