|
| 1 | +// Licensed to the Apache Software Foundation (ASF) under one |
| 2 | +// or more contributor license agreements. See the NOTICE file |
| 3 | +// distributed with this work for additional information |
| 4 | +// regarding copyright ownership. The ASF licenses this file |
| 5 | +// to you under the Apache License, Version 2.0 (the |
| 6 | +// "License"); you may not use this file except in compliance |
| 7 | +// with the License. You may obtain a copy of the License at |
| 8 | +// |
| 9 | +// http://www.apache.org/licenses/LICENSE-2.0 |
| 10 | +// |
| 11 | +// Unless required by applicable law or agreed to in writing, |
| 12 | +// software distributed under the License is distributed on an |
| 13 | +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| 14 | +// KIND, either express or implied. See the License for the |
| 15 | +// specific language governing permissions and limitations |
| 16 | +// under the License. |
| 17 | + |
| 18 | +//! Controlled reproduction for <https://github.com/apache/datafusion/issues/25035>. |
| 19 | +//! |
| 20 | +//! The benchmark changes one mechanism-relevant variable at a time: |
| 21 | +//! conjunction association, prefix selectivity, input batch width, number of |
| 22 | +//! conjuncts, and the cost of the final conjunct. All generated inputs are |
| 23 | +//! deterministic, and every left/right pair is checked for equal output before |
| 24 | +//! it is measured. |
| 25 | +
|
| 26 | +use std::{hint::black_box, sync::Arc, time::Duration}; |
| 27 | + |
| 28 | +use arrow::{ |
| 29 | + array::{ArrayRef, Int32Array, Int64Array, StringArray}, |
| 30 | + datatypes::{DataType, Field, Schema}, |
| 31 | + record_batch::RecordBatch, |
| 32 | +}; |
| 33 | +use criterion::{BenchmarkId, Criterion, Throughput, criterion_group, criterion_main}; |
| 34 | +use datafusion_expr::{ColumnarValue, Operator}; |
| 35 | +use datafusion_physical_expr::{ |
| 36 | + PhysicalExpr, |
| 37 | + expressions::{BinaryExpr, Column, lit}, |
| 38 | +}; |
| 39 | + |
| 40 | +const ROWS: usize = 8192; |
| 41 | + |
| 42 | +#[derive(Debug, Clone, Copy)] |
| 43 | +enum Suffix { |
| 44 | + Cheap, |
| 45 | + Regex, |
| 46 | +} |
| 47 | + |
| 48 | +#[derive(Debug, Clone, Copy)] |
| 49 | +struct Case { |
| 50 | + conjuncts: usize, |
| 51 | + pass_permille: u16, |
| 52 | + payload_columns: usize, |
| 53 | + suffix: Suffix, |
| 54 | +} |
| 55 | + |
| 56 | +impl Case { |
| 57 | + fn label(self) -> String { |
| 58 | + let suffix = match self.suffix { |
| 59 | + Suffix::Cheap => "cheap", |
| 60 | + Suffix::Regex => "regex", |
| 61 | + }; |
| 62 | + format!( |
| 63 | + "k{}_p{}_w{}_{}", |
| 64 | + self.conjuncts, self.pass_permille, self.payload_columns, suffix |
| 65 | + ) |
| 66 | + } |
| 67 | +} |
| 68 | + |
| 69 | +fn splitmix64(mut value: u64) -> u64 { |
| 70 | + value = value.wrapping_add(0x9e3779b97f4a7c15); |
| 71 | + value = (value ^ (value >> 30)).wrapping_mul(0xbf58476d1ce4e5b9); |
| 72 | + value = (value ^ (value >> 27)).wrapping_mul(0x94d049bb133111eb); |
| 73 | + value ^ (value >> 31) |
| 74 | +} |
| 75 | + |
| 76 | +fn make_batch(case: Case) -> RecordBatch { |
| 77 | + assert!(case.conjuncts >= 2); |
| 78 | + assert!(case.pass_permille <= 1000); |
| 79 | + |
| 80 | + let cheap_conjuncts = match case.suffix { |
| 81 | + Suffix::Cheap => case.conjuncts, |
| 82 | + Suffix::Regex => case.conjuncts - 1, |
| 83 | + }; |
| 84 | + let mut fields = Vec::with_capacity( |
| 85 | + cheap_conjuncts |
| 86 | + + usize::from(matches!(case.suffix, Suffix::Regex)) |
| 87 | + + case.payload_columns, |
| 88 | + ); |
| 89 | + let mut arrays: Vec<ArrayRef> = Vec::with_capacity(fields.capacity()); |
| 90 | + |
| 91 | + for column in 0..cheap_conjuncts { |
| 92 | + let values = (0..ROWS) |
| 93 | + .map(|row| { |
| 94 | + let hash = splitmix64((row as u64) ^ ((column as u64 + 1) << 32)); |
| 95 | + if hash % 1000 < u64::from(case.pass_permille) { |
| 96 | + 1 |
| 97 | + } else { |
| 98 | + -1 |
| 99 | + } |
| 100 | + }) |
| 101 | + .collect::<Vec<i32>>(); |
| 102 | + fields.push(Field::new( |
| 103 | + format!("predicate_{column}"), |
| 104 | + DataType::Int32, |
| 105 | + false, |
| 106 | + )); |
| 107 | + arrays.push(Arc::new(Int32Array::from(values))); |
| 108 | + } |
| 109 | + |
| 110 | + if matches!(case.suffix, Suffix::Regex) { |
| 111 | + let values = (0..ROWS) |
| 112 | + .map(|row| { |
| 113 | + if row % 2 == 0 { |
| 114 | + "https://api.example.com/v2/items/12345?source=benchmark" |
| 115 | + } else { |
| 116 | + "http://unrelated.invalid/plain-text" |
| 117 | + } |
| 118 | + }) |
| 119 | + .collect::<Vec<_>>(); |
| 120 | + fields.push(Field::new("regex_input", DataType::Utf8, false)); |
| 121 | + arrays.push(Arc::new(StringArray::from(values))); |
| 122 | + } |
| 123 | + |
| 124 | + for column in 0..case.payload_columns { |
| 125 | + let values = (0..ROWS) |
| 126 | + .map(|row| splitmix64((row as u64) ^ ((column as u64 + 101) << 32)) as i64) |
| 127 | + .collect::<Vec<_>>(); |
| 128 | + fields.push(Field::new( |
| 129 | + format!("payload_{column}"), |
| 130 | + DataType::Int64, |
| 131 | + false, |
| 132 | + )); |
| 133 | + arrays.push(Arc::new(Int64Array::from(values))); |
| 134 | + } |
| 135 | + |
| 136 | + RecordBatch::try_new(Arc::new(Schema::new(fields)), arrays).unwrap() |
| 137 | +} |
| 138 | + |
| 139 | +fn leaves(case: Case) -> Vec<Arc<dyn PhysicalExpr>> { |
| 140 | + let cheap_conjuncts = match case.suffix { |
| 141 | + Suffix::Cheap => case.conjuncts, |
| 142 | + Suffix::Regex => case.conjuncts - 1, |
| 143 | + }; |
| 144 | + let mut leaves = (0..cheap_conjuncts) |
| 145 | + .map(|column| { |
| 146 | + Arc::new(BinaryExpr::new( |
| 147 | + Arc::new(Column::new(&format!("predicate_{column}"), column)), |
| 148 | + Operator::Gt, |
| 149 | + lit(0_i32), |
| 150 | + )) as Arc<dyn PhysicalExpr> |
| 151 | + }) |
| 152 | + .collect::<Vec<_>>(); |
| 153 | + |
| 154 | + if matches!(case.suffix, Suffix::Regex) { |
| 155 | + leaves.push(Arc::new(BinaryExpr::new( |
| 156 | + Arc::new(Column::new("regex_input", cheap_conjuncts)), |
| 157 | + Operator::RegexMatch, |
| 158 | + lit(r"^https://([a-z]+\.)?example\.com/v[0-9]+/items/[0-9]+\?source=benchmark$"), |
| 159 | + ))); |
| 160 | + } |
| 161 | + leaves |
| 162 | +} |
| 163 | + |
| 164 | +fn left_deep(mut leaves: Vec<Arc<dyn PhysicalExpr>>) -> Arc<dyn PhysicalExpr> { |
| 165 | + let mut expression = leaves.remove(0); |
| 166 | + for leaf in leaves { |
| 167 | + expression = Arc::new(BinaryExpr::new(expression, Operator::And, leaf)); |
| 168 | + } |
| 169 | + expression |
| 170 | +} |
| 171 | + |
| 172 | +fn right_deep(mut leaves: Vec<Arc<dyn PhysicalExpr>>) -> Arc<dyn PhysicalExpr> { |
| 173 | + let mut expression = leaves.pop().unwrap(); |
| 174 | + while let Some(leaf) = leaves.pop() { |
| 175 | + expression = Arc::new(BinaryExpr::new(leaf, Operator::And, expression)); |
| 176 | + } |
| 177 | + expression |
| 178 | +} |
| 179 | + |
| 180 | +fn as_array(value: ColumnarValue) -> ArrayRef { |
| 181 | + value.into_array(ROWS).unwrap() |
| 182 | +} |
| 183 | + |
| 184 | +fn benchmark_issue_25035(c: &mut Criterion) { |
| 185 | + // The first case is the representative reproduction. The remainder are |
| 186 | + // controlled perturbations of one dimension around it. |
| 187 | + let cases = [ |
| 188 | + Case { |
| 189 | + conjuncts: 8, |
| 190 | + pass_permille: 700, |
| 191 | + payload_columns: 32, |
| 192 | + suffix: Suffix::Cheap, |
| 193 | + }, |
| 194 | + // Batch-width perturbation. |
| 195 | + Case { |
| 196 | + conjuncts: 8, |
| 197 | + pass_permille: 700, |
| 198 | + payload_columns: 0, |
| 199 | + suffix: Suffix::Cheap, |
| 200 | + }, |
| 201 | + Case { |
| 202 | + conjuncts: 8, |
| 203 | + pass_permille: 700, |
| 204 | + payload_columns: 8, |
| 205 | + suffix: Suffix::Cheap, |
| 206 | + }, |
| 207 | + Case { |
| 208 | + conjuncts: 8, |
| 209 | + pass_permille: 700, |
| 210 | + payload_columns: 64, |
| 211 | + suffix: Suffix::Cheap, |
| 212 | + }, |
| 213 | + // Selectivity perturbation, including a no-preselection negative control. |
| 214 | + Case { |
| 215 | + conjuncts: 8, |
| 216 | + pass_permille: 500, |
| 217 | + payload_columns: 32, |
| 218 | + suffix: Suffix::Cheap, |
| 219 | + }, |
| 220 | + Case { |
| 221 | + conjuncts: 8, |
| 222 | + pass_permille: 900, |
| 223 | + payload_columns: 32, |
| 224 | + suffix: Suffix::Cheap, |
| 225 | + }, |
| 226 | + Case { |
| 227 | + conjuncts: 8, |
| 228 | + pass_permille: 990, |
| 229 | + payload_columns: 32, |
| 230 | + suffix: Suffix::Cheap, |
| 231 | + }, |
| 232 | + // Conjunction-length perturbation. |
| 233 | + Case { |
| 234 | + conjuncts: 2, |
| 235 | + pass_permille: 700, |
| 236 | + payload_columns: 32, |
| 237 | + suffix: Suffix::Cheap, |
| 238 | + }, |
| 239 | + Case { |
| 240 | + conjuncts: 4, |
| 241 | + pass_permille: 700, |
| 242 | + payload_columns: 32, |
| 243 | + suffix: Suffix::Cheap, |
| 244 | + }, |
| 245 | + Case { |
| 246 | + conjuncts: 16, |
| 247 | + pass_permille: 700, |
| 248 | + payload_columns: 32, |
| 249 | + suffix: Suffix::Cheap, |
| 250 | + }, |
| 251 | + // Positive control: preselection can be worthwhile with an expensive suffix. |
| 252 | + Case { |
| 253 | + conjuncts: 8, |
| 254 | + pass_permille: 700, |
| 255 | + payload_columns: 0, |
| 256 | + suffix: Suffix::Regex, |
| 257 | + }, |
| 258 | + ]; |
| 259 | + |
| 260 | + let mut group = c.benchmark_group("issue_25035"); |
| 261 | + group.warm_up_time(Duration::from_secs(1)); |
| 262 | + group.measurement_time(Duration::from_secs(3)); |
| 263 | + group.sample_size(40); |
| 264 | + group.throughput(Throughput::Elements(ROWS as u64)); |
| 265 | + |
| 266 | + for case in cases { |
| 267 | + let batch = make_batch(case); |
| 268 | + let left = left_deep(leaves(case)); |
| 269 | + let right = right_deep(leaves(case)); |
| 270 | + |
| 271 | + let left_result = as_array(left.evaluate(&batch).unwrap()); |
| 272 | + let right_result = as_array(right.evaluate(&batch).unwrap()); |
| 273 | + assert_eq!( |
| 274 | + left_result.as_ref(), |
| 275 | + right_result.as_ref(), |
| 276 | + "{}", |
| 277 | + case.label() |
| 278 | + ); |
| 279 | + |
| 280 | + let label = case.label(); |
| 281 | + group.bench_with_input(BenchmarkId::new("left", &label), &batch, |b, batch| { |
| 282 | + b.iter(|| black_box(left.evaluate(black_box(batch)).unwrap())) |
| 283 | + }); |
| 284 | + group.bench_with_input(BenchmarkId::new("right", &label), &batch, |b, batch| { |
| 285 | + b.iter(|| black_box(right.evaluate(black_box(batch)).unwrap())) |
| 286 | + }); |
| 287 | + } |
| 288 | + group.finish(); |
| 289 | +} |
| 290 | + |
| 291 | +criterion_group!(benches, benchmark_issue_25035); |
| 292 | +criterion_main!(benches); |
0 commit comments