Skip to content

Commit 9b9817f

Browse files
peterxcliclaude
andcommitted
fix: make the dense null shape actually dense, and restore the clock equivalence checks
Review of #5771 found that `DENSE_NULLS = (0.875, "dense")` degenerated to an all-null shape. `common::is_null` derives a stride as `round(1 / ratio)`, which is 1 for any ratio above two thirds, so every row came back null: 8192 nulls and zero valid rows rather than the intended 7168 and 1024. The dense clock cases were therefore a second copy of the all-null case and never exercised valid values in a mostly-null batch. `is_null` now takes the stride over the valid rows when the ratio is above half, so 0.875 yields one valid row in eight. Ratios at or below half are unchanged, and no existing caller passes a ratio in that range -- `NULL_RATIOS` is 0.0, 0.1 and 1.0 -- so no other benchmark's shapes move. `assert_density` checks the realised null count against the requested ratio before timing, so a shape that silently degenerates fails instead of being measured. Folding the clock benchmark into extract_date_part.rs also dropped `assert_matches_arithmetic` without replacing it, leaving that harness with no pre-timing comparison, which the PR body incorrectly claimed it had. Every clock shape now gets a null-aware check: the result must be null exactly where the input is and every value must sit inside the field's range. Shapes eligible for the fast path additionally get an exact oracle, recomputed from the generator rather than from arrow, so it validates the baseline implementation as well as this one. Dictionary and offset-session controls get the null-aware half, since no arithmetic oracle applies to them. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent bb8a048 commit 9b9817f

2 files changed

Lines changed: 171 additions & 45 deletions

File tree

‎native/spark-expr/benches/common/mod.rs‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,11 +36,20 @@ pub const ROW_COUNTS: [usize; 3] = [8_192, 65_536, 524_288];
3636

3737
pub const NULL_RATIOS: [(f64, &str); 3] = [(0.0, "no_nulls"), (0.1, "sparse"), (1.0, "all_null")];
3838

39+
/// Whether row `i` is null for the requested null ratio.
40+
///
41+
/// The density is approximated by a stride. Below half, every `round(1/ratio)`-th row is null;
42+
/// above half the stride is taken over the *valid* rows instead, because `round(1/ratio)`
43+
/// collapses to 1 for any ratio above 2/3 and would make every row null. A dense ratio such as
44+
/// 0.875 therefore yields one valid row in eight rather than a second all-null shape.
3945
pub fn is_null(i: usize, null_ratio: f64) -> bool {
4046
if null_ratio <= 0.0 {
4147
false
4248
} else if null_ratio >= 1.0 {
4349
true
50+
} else if null_ratio > 0.5 {
51+
let stride = (1.0 / (1.0 - null_ratio)).round() as usize;
52+
!(stride != 0 && i.is_multiple_of(stride))
4453
} else {
4554
let stride = (1.0 / null_ratio).round() as usize;
4655
stride != 0 && i.is_multiple_of(stride)

‎native/spark-expr/benches/extract_date_part.rs‎

Lines changed: 162 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,8 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
use arrow::array::{ArrayRef, DictionaryArray, Int32Array, TimestampMicrosecondArray};
18+
use arrow::array::{Array, ArrayRef, DictionaryArray, Int32Array, TimestampMicrosecondArray};
19+
use arrow::compute::cast;
1920
use arrow::datatypes::{DataType, Field, Int32Type};
2021
use criterion::{criterion_group, criterion_main, BenchmarkId, Criterion};
2122
use datafusion::common::config::ConfigOptions;
@@ -30,49 +31,129 @@ use common::{is_null, timestamp_micros_array, NULL_RATIOS, ROW_COUNTS};
3031

3132
const TZ: &str = "America/Los_Angeles";
3233
/// A zero-offset session zone. Only in such a session is a timezone-aware timestamp eligible for
33-
/// the integer fast path, so both branches of the dispatch need a session zone of their own.
34+
/// the integer fast path, so each branch of the dispatch needs a session zone of its own.
3435
const UTC_TZ: &str = "UTC";
3536
const SMALL_ROWS: usize = 8_192;
3637

3738
/// `NULL_RATIOS` covers none / sparse / all. Dense is added because that is where a kernel which
3839
/// evaluates every slot can lose to arrow's `unary_opt`, which visits only valid indices.
3940
const DENSE_NULLS: (f64, &str) = (0.875, "dense");
4041

42+
const MICROS_PER_DAY: i64 = 86_400_000_000;
43+
4144
/// Instants either side of the epoch, roughly 1875 to 2064 at 8192 rows. Pre-epoch values are the
4245
/// ones that matter: `-1` us is 1969-12-31 23:59:59.999999, so truncating toward zero instead of
4346
/// dividing Euclidean-style would give the wrong field.
4447
fn spanning_epoch(i: usize, rows: usize) -> i64 {
4548
(i as i64 - (rows as i64) / 2) * 730_000_000_000 + 12_345_678
4649
}
4750

48-
fn udfs(session_tz: &str) -> Vec<(&'static str, Box<dyn ScalarUDFImpl>)> {
49-
vec![
50-
("hour", Box::new(SparkHour::new(session_tz.to_string()))),
51-
("minute", Box::new(SparkMinute::new(session_tz.to_string()))),
52-
("second", Box::new(SparkSecond::new(session_tz.to_string()))),
53-
]
51+
fn hour_of_day(micros: i64) -> i32 {
52+
(micros.rem_euclid(MICROS_PER_DAY) / 3_600_000_000) as i32
53+
}
54+
fn minute_of_hour(micros: i64) -> i32 {
55+
micros.div_euclid(60_000_000).rem_euclid(60) as i32
56+
}
57+
fn second_of_minute(micros: i64) -> i32 {
58+
micros.div_euclid(1_000_000).rem_euclid(60) as i32
5459
}
5560

56-
fn args_of(arr: ArrayRef) -> Vec<ColumnarValue> {
57-
vec![ColumnarValue::Array(arr)]
61+
struct Part {
62+
name: &'static str,
63+
kernel: fn(i64) -> i32,
64+
max: i32,
5865
}
5966

60-
fn run(udf: &dyn ScalarUDFImpl, args: &[ColumnarValue], rows: usize) {
61-
black_box(
62-
udf.invoke_with_args(ScalarFunctionArgs {
63-
args: args.to_vec(),
64-
arg_fields: vec![],
65-
number_rows: rows,
66-
return_field: Arc::new(Field::new("result", DataType::Int32, true)),
67-
config_options: Arc::new(ConfigOptions::default()),
68-
})
69-
.unwrap(),
70-
);
67+
const PARTS: [Part; 3] = [
68+
Part {
69+
name: "hour",
70+
kernel: hour_of_day,
71+
max: 23,
72+
},
73+
Part {
74+
name: "minute",
75+
kernel: minute_of_hour,
76+
max: 59,
77+
},
78+
Part {
79+
name: "second",
80+
kernel: second_of_minute,
81+
max: 59,
82+
},
83+
];
84+
85+
fn udf_for(part: &str, session_tz: &str) -> Box<dyn ScalarUDFImpl> {
86+
match part {
87+
"hour" => Box::new(SparkHour::new(session_tz.to_string())),
88+
"minute" => Box::new(SparkMinute::new(session_tz.to_string())),
89+
_ => Box::new(SparkSecond::new(session_tz.to_string())),
90+
}
91+
}
92+
93+
fn invoke(udf: &dyn ScalarUDFImpl, args: &[ColumnarValue], rows: usize) -> ArrayRef {
94+
udf.invoke_with_args(ScalarFunctionArgs {
95+
args: args.to_vec(),
96+
arg_fields: vec![],
97+
number_rows: rows,
98+
return_field: Arc::new(Field::new("result", DataType::Int32, true)),
99+
config_options: Arc::new(ConfigOptions::default()),
100+
})
101+
.unwrap()
102+
.to_array(rows)
103+
.unwrap()
104+
}
105+
106+
/// A dictionary result stays dictionary-encoded; flatten so every shape is compared the same way.
107+
fn as_int32(array: &ArrayRef) -> Int32Array {
108+
let flat = if matches!(array.data_type(), DataType::Dictionary(_, _)) {
109+
cast(array, &DataType::Int32).unwrap()
110+
} else {
111+
Arc::clone(array)
112+
};
113+
flat.as_any().downcast_ref::<Int32Array>().unwrap().clone()
114+
}
115+
116+
/// Validates a shape before it is timed. Every shape gets a null-aware check: the result must be
117+
/// null exactly where the input is, and every non-null value must be inside the field's range.
118+
/// Shapes eligible for the fast path additionally get an exact oracle -- the field recomputed
119+
/// from the generator, independent of arrow -- since no session offset applies to them.
120+
fn check(
121+
part: &Part,
122+
array: &ArrayRef,
123+
udf: &dyn ScalarUDFImpl,
124+
rows: usize,
125+
oracle: Option<&dyn Fn(usize) -> Option<i32>>,
126+
) {
127+
let out = as_int32(&invoke(
128+
udf,
129+
&[ColumnarValue::Array(Arc::clone(array))],
130+
rows,
131+
));
132+
let input_nulls = array.logical_nulls();
133+
assert_eq!(out.len(), rows, "{}: length", part.name);
134+
for i in 0..rows {
135+
let input_null = input_nulls.as_ref().is_some_and(|n| n.is_null(i));
136+
assert_eq!(
137+
out.is_null(i),
138+
input_null,
139+
"{}: null flag at row {i} ({:?})",
140+
part.name,
141+
array.data_type()
142+
);
143+
if !input_null {
144+
let v = out.value(i);
145+
assert!(
146+
(0..=part.max).contains(&v),
147+
"{}: value {v} out of range at row {i}",
148+
part.name
149+
);
150+
if let Some(f) = oracle {
151+
assert_eq!(Some(v), f(i), "{}: value at row {i}", part.name);
152+
}
153+
}
154+
}
71155
}
72156

73-
/// A dictionary-encoded timestamp column, the shape a partition column arrives in. Dictionaries
74-
/// deliberately stay on the general path, so this is also a control for code the change does not
75-
/// touch.
76157
fn dict_timestamps(rows: usize, cardinality: usize, null_ratio: f64) -> ArrayRef {
77158
let values = Arc::new(TimestampMicrosecondArray::from(
78159
(0..cardinality)
@@ -91,58 +172,94 @@ fn dict_timestamps(rows: usize, cardinality: usize, null_ratio: f64) -> ArrayRef
91172
Arc::new(DictionaryArray::<Int32Type>::new(keys, values))
92173
}
93174

175+
fn null_ratios() -> impl Iterator<Item = (f64, &'static str)> {
176+
NULL_RATIOS
177+
.iter()
178+
.copied()
179+
.chain(std::iter::once(DENSE_NULLS))
180+
}
181+
182+
/// The stride approximation in `common::is_null` has to actually produce the density each shape
183+
/// claims, or a "dense" case silently becomes a second all-null case.
184+
fn assert_density(rows: usize, null_ratio: f64, tag: &str) {
185+
let nulls = (0..rows).filter(|&i| is_null(i, null_ratio)).count();
186+
let expected = (rows as f64 * null_ratio).round() as usize;
187+
assert!(
188+
nulls.abs_diff(expected) <= rows / 100,
189+
"{tag}: expected about {expected} nulls of {rows}, generator produced {nulls}"
190+
);
191+
}
192+
94193
fn criterion_benchmark(c: &mut Criterion) {
95-
// hour/minute/second all route through extract_date_part. The dispatch picks an integer fast
194+
// hour/minute/second all route through extract_date_part. The dispatch takes an integer fast
96195
// path when no timezone offset applies -- TimestampNTZ, or a timezone-aware value in a
97196
// zero-offset session -- and otherwise shifts to the session zone and reads a calendar
98-
// datetime. Sweep both session zones so each branch is measured.
197+
// datetime. Both session zones are swept so each branch is measured.
99198
for (session_tz, session_tag) in [(TZ, "la_session"), (UTC_TZ, "utc_session")] {
100-
for (part, udf) in &udfs(session_tz) {
101-
let mut group = c.benchmark_group(*part);
199+
for part in &PARTS {
200+
let udf = udf_for(part.name, session_tz);
201+
let mut group = c.benchmark_group(part.name);
102202

103203
for (tz, tz_tag) in [(Some("UTC"), "tz"), (None, "ntz")] {
104-
// The full row sweep runs for the session zone the benchmark shipped with; the
105-
// second session zone and the dictionary shapes stay at one size to keep the
106-
// matrix affordable.
204+
// The full row sweep stays on the session zone the benchmark shipped with; the
205+
// second zone and the dictionary shapes use one size to bound the matrix.
107206
let sizes: &[usize] = if session_tz == TZ {
108207
&ROW_COUNTS
109208
} else {
110209
&[SMALL_ROWS]
111210
};
211+
// No offset applies to NTZ in any session, nor to a stored UTC instant read in a
212+
// zero-offset session, so those shapes have an exact oracle.
213+
let eligible = tz.is_none() || session_tz == UTC_TZ;
112214
for &rows in sizes {
113-
for (null_ratio, tag) in NULL_RATIOS
114-
.iter()
115-
.copied()
116-
.chain(std::iter::once(DENSE_NULLS))
117-
{
215+
for (null_ratio, tag) in null_ratios() {
216+
assert_density(rows, null_ratio, tag);
118217
let arr = timestamp_micros_array(rows, null_ratio, tz, |i| {
119218
spanning_epoch(i, rows)
120219
});
121-
let args = args_of(arr);
220+
let oracle = |i: usize| {
221+
if is_null(i, null_ratio) {
222+
None
223+
} else {
224+
Some((part.kernel)(spanning_epoch(i, rows)))
225+
}
226+
};
227+
check(
228+
part,
229+
&arr,
230+
udf.as_ref(),
231+
rows,
232+
if eligible { Some(&oracle) } else { None },
233+
);
234+
let args = vec![ColumnarValue::Array(arr)];
122235
group.bench_with_input(
123236
BenchmarkId::from_parameter(format!(
124237
"{session_tag}/{tz_tag}/{rows}/{tag}"
125238
)),
126239
&args,
127-
|b, args| b.iter(|| run(udf.as_ref(), args, rows)),
240+
|b, args| {
241+
b.iter(|| black_box(invoke(udf.as_ref(), args, rows)));
242+
},
128243
);
129244
}
130245
}
131246
}
132247

133248
for cardinality in [8usize, 1024] {
134-
for (null_ratio, tag) in NULL_RATIOS
135-
.iter()
136-
.copied()
137-
.chain(std::iter::once(DENSE_NULLS))
138-
{
139-
let args = args_of(dict_timestamps(SMALL_ROWS, cardinality, null_ratio));
249+
for (null_ratio, tag) in null_ratios() {
250+
let arr = dict_timestamps(SMALL_ROWS, cardinality, null_ratio);
251+
// Dictionaries stay on the general path in every session, so there is no
252+
// arithmetic oracle; the null-aware and range checks still apply.
253+
check(part, &arr, udf.as_ref(), SMALL_ROWS, None);
254+
let args = vec![ColumnarValue::Array(arr)];
140255
group.bench_with_input(
141256
BenchmarkId::from_parameter(format!(
142257
"{session_tag}/dict{cardinality}/{SMALL_ROWS}/{tag}"
143258
)),
144259
&args,
145-
|b, args| b.iter(|| run(udf.as_ref(), args, SMALL_ROWS)),
260+
|b, args| {
261+
b.iter(|| black_box(invoke(udf.as_ref(), args, SMALL_ROWS)));
262+
},
146263
);
147264
}
148265
}

0 commit comments

Comments
 (0)