|
15 | 15 | // specific language governing permissions and limitations |
16 | 16 | // under the License. |
17 | 17 |
|
| 18 | +use arrow::array::{ArrayRef, Int32Array, Int64Array}; |
18 | 19 | use arrow::{array::StringArray, record_batch::RecordBatch}; |
19 | 20 | use arrow::{ |
20 | 21 | array::{BooleanArray, Date32Array, Date64Array}, |
21 | 22 | datatypes::{DataType, Field, Schema}, |
22 | 23 | }; |
23 | 24 | use criterion::{Criterion, criterion_group, criterion_main}; |
| 25 | +use datafusion_common::ScalarValue; |
24 | 26 | use datafusion_expr::{Operator, and, binary_expr, col, lit, or}; |
25 | 27 | use datafusion_physical_expr::{ |
26 | 28 | PhysicalExpr, |
27 | | - expressions::{BinaryExpr, Column}, |
| 29 | + expressions::{BinaryExpr, Column, Literal, cast, in_list}, |
28 | 30 | planner::logical2physical, |
29 | 31 | }; |
| 32 | +use rand::rngs::StdRng; |
| 33 | +use rand::{Rng, SeedableRng}; |
30 | 34 | use std::hint::black_box; |
31 | 35 | use std::sync::Arc; |
32 | 36 |
|
@@ -234,6 +238,186 @@ fn benchmark_binary_op_in_short_circuit(c: &mut Criterion) { |
234 | 238 | } |
235 | 239 | } |
236 | 240 |
|
| 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 | + |
237 | 421 | /// Generate test data with computationally expensive patterns |
238 | 422 | fn generate_test_strings(num_rows: usize) -> (Vec<String>, Vec<String>) { |
239 | 423 | // Extended URL patterns with query parameters and paths |
@@ -385,6 +569,7 @@ fn benchmark_date64_subtract(c: &mut Criterion) { |
385 | 569 | criterion_group!( |
386 | 570 | benches, |
387 | 571 | benchmark_binary_op_in_short_circuit, |
| 572 | + benchmark_conjunction, |
388 | 573 | benchmark_date32_subtract, |
389 | 574 | benchmark_date64_subtract |
390 | 575 | ); |
|
0 commit comments