Skip to content

Commit 8370d7d

Browse files
perf: evaluate AND chains as one n-ary conjunction (#25035)
1 parent e8e41ae commit 8370d7d

2 files changed

Lines changed: 825 additions & 170 deletions

File tree

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

Lines changed: 162 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,162 @@ 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+
// (conjuncts, pass rate, kind, null rate, regex suffix)
265+
for (num_conjuncts, pass_rate, kind, null_rate, regex) in [
266+
(4, 0.5, Lt, 0.0, false),
267+
(8, 0.7, Lt, 0.0, false),
268+
(8, 0.9, Lt, 0.0, false),
269+
(16, 0.7, Lt, 0.0, false),
270+
(8, 0.7, Lt, 0.0, true),
271+
(8, 0.7, CastLt, 0.0, false),
272+
(8, 0.7, InList, 0.0, false),
273+
(4, 0.5, Lt, 0.1, true),
274+
(8, 0.7, Plus, 0.0, false),
275+
] {
276+
// `InList` draws values from 0..10, the others from 0..1000.
277+
let domain = if kind == InList { 10 } else { 1000 };
278+
let cutoff = (pass_rate * domain as f64) as i32;
279+
let conjunct_schema = Schema::new(
280+
(0..num_conjuncts)
281+
.map(|i| Field::new(format!("c{i}"), DataType::Int32, null_rate > 0.0))
282+
.collect::<Vec<_>>(),
283+
);
284+
let mut conjuncts: Vec<Arc<dyn PhysicalExpr>> = (0..num_conjuncts)
285+
.map(|i| {
286+
let column = Arc::new(Column::new(&format!("c{i}"), i)) as _;
287+
match kind {
288+
Lt => Arc::new(BinaryExpr::new(
289+
column,
290+
Operator::Lt,
291+
Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff)))),
292+
)) as _,
293+
CastLt => Arc::new(BinaryExpr::new(
294+
cast(column, &conjunct_schema, DataType::Int64).unwrap(),
295+
Operator::Lt,
296+
Arc::new(Literal::new(ScalarValue::Int64(Some(cutoff as i64)))),
297+
)),
298+
Plus => Arc::new(BinaryExpr::new(
299+
Arc::new(BinaryExpr::new(
300+
column,
301+
Operator::Plus,
302+
Arc::new(Literal::new(ScalarValue::Int32(Some(1)))),
303+
)),
304+
Operator::Lt,
305+
Arc::new(Literal::new(ScalarValue::Int32(Some(cutoff + 1)))),
306+
)),
307+
InList => in_list(
308+
column,
309+
(0..cutoff)
310+
.map(|v| {
311+
Arc::new(Literal::new(ScalarValue::Int32(Some(v)))) as _
312+
})
313+
.collect(),
314+
&false,
315+
&conjunct_schema,
316+
)
317+
.unwrap(),
318+
}
319+
})
320+
.collect();
321+
if regex {
322+
conjuncts.push(Arc::new(BinaryExpr::new(
323+
Arc::new(Column::new("url", num_conjuncts)),
324+
Operator::RegexMatch,
325+
Arc::new(Literal::new(ScalarValue::from(
326+
r#"^https://(\w+\.)?example\.(com|org)/"#,
327+
))),
328+
)));
329+
}
330+
let left_deep = conjuncts
331+
.iter()
332+
.cloned()
333+
.reduce(|l, r| Arc::new(BinaryExpr::new(l, Operator::And, r)))
334+
.unwrap();
335+
let right_deep = conjuncts
336+
.iter()
337+
.cloned()
338+
.rev()
339+
.reduce(|r, l| Arc::new(BinaryExpr::new(l, Operator::And, r)))
340+
.unwrap();
341+
342+
for payload_columns in [0, 32] {
343+
let mut fields = conjunct_schema.fields().to_vec();
344+
let mut columns: Vec<ArrayRef> = vec![];
345+
for _ in 0..num_conjuncts {
346+
columns.push(Arc::new(if null_rate > 0.0 {
347+
Int32Array::from_iter((0..NUM_ROWS).map(|_| {
348+
let value = rng.random_range(0..domain);
349+
(!rng.random_bool(null_rate)).then_some(value)
350+
}))
351+
} else {
352+
Int32Array::from_iter_values(
353+
(0..NUM_ROWS).map(|_| rng.random_range(0..domain)),
354+
)
355+
}));
356+
}
357+
if regex {
358+
fields.push(Arc::new(Field::new("url", DataType::Utf8, false)));
359+
columns.push(Arc::new(StringArray::from(urls.clone())));
360+
}
361+
for i in 0..payload_columns {
362+
fields.push(Arc::new(Field::new(
363+
format!("p{i}"),
364+
DataType::Int64,
365+
false,
366+
)));
367+
columns.push(Arc::new(Int64Array::from_iter_values(
368+
(0..NUM_ROWS).map(|_| rng.random()),
369+
)));
370+
}
371+
let batch =
372+
RecordBatch::try_new(Arc::new(Schema::new(fields)), columns).unwrap();
373+
374+
let suffix = [
375+
(kind == CastLt, "_cast"),
376+
(kind == InList, "_inlist"),
377+
(kind == Plus, "_plus"),
378+
(null_rate > 0.0, "_nulls"),
379+
(regex, "_regex"),
380+
]
381+
.into_iter()
382+
.filter_map(|(on, tag)| on.then_some(tag))
383+
.collect::<String>();
384+
for (shape, expr) in [("left_deep", &left_deep), ("right_deep", &right_deep)]
385+
{
386+
c.bench_function(
387+
&format!(
388+
"conjunction/k{num_conjuncts}_p{pass_rate}{suffix}_w{payload_columns}/{shape}"
389+
),
390+
|b| b.iter(|| expr.evaluate(black_box(&batch)).unwrap()),
391+
);
392+
}
393+
}
394+
}
395+
}
396+
237397
/// Generate test data with computationally expensive patterns
238398
fn generate_test_strings(num_rows: usize) -> (Vec<String>, Vec<String>) {
239399
// Extended URL patterns with query parameters and paths
@@ -385,6 +545,7 @@ fn benchmark_date64_subtract(c: &mut Criterion) {
385545
criterion_group!(
386546
benches,
387547
benchmark_binary_op_in_short_circuit,
548+
benchmark_conjunction,
388549
benchmark_date32_subtract,
389550
benchmark_date64_subtract
390551
);

0 commit comments

Comments
 (0)