Skip to content

Commit 290f57d

Browse files
Add controlled reproducer for apache#25035
1 parent 9082d6b commit 290f57d

2 files changed

Lines changed: 296 additions & 0 deletions

File tree

‎datafusion/physical-expr/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,10 @@ name = "is_null"
9696
harness = false
9797
name = "binary_op"
9898

99+
[[bench]]
100+
harness = false
101+
name = "issue_25035"
102+
99103
[[bench]]
100104
harness = false
101105
name = "simplify"
Lines changed: 292 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,292 @@
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

Comments
 (0)