Skip to content

Commit f1ecc4a

Browse files
authored
feat: reuse range partitioning for audited date_bin aggregation (apache#26835)
## Which issue does this PR close? Closes apache#25344. Closes apache#25345. This completes the initial single-key work alongside apache#26449. Explicit origins (apache#26913) and compound range keys (apache#24644) remain follow-ups. ## Rationale for this change Extend the aggregate-locality optimization from apache#26449 to `date_bin`. When bins stay within timestamp range partitions, aggregation can skip the hash shuffle. ## What changes are included in this PR? Pass literal argument values to the existing admission hook. `INTERVAL '1 hour'` and `INTERVAL '1 month'` have the same `IntervalMonthDayNano` type, so types alone cannot distinguish them. Inspecting the literal value lets `date_bin` require a positive fixed-duration stride without months, treating each day as 24 hours. `date_trunc` continues to rely only on argument types. Initially, admit only two-argument calls over timezone-less nanosecond timestamps, using that literal stride. Explicit origins and other types remain excluded. For example: ```sql SELECT date_bin(INTERVAL '1 hour', event_time) AS hour_bin, COUNT(*) FROM events GROUP BY hour_bin; ``` For ascending timestamp ranges: - A split at `01:00` separates hourly bins, so the shuffle can be skipped. - A split at `01:30` cuts through the `01:00` bin, so the shuffle remains. Every split must pass the existing boundary proof. Evaluation errors conservatively retain the shuffle. This follows the NULL-to-error fix in apache#26607. ## What is the testing strategy for this PR? Unit tests cover admission, hook forwarding, ascending/descending boundaries, and evaluation errors. SQLLogicTests verify plans and results for aligned bins, crossing bins, and excluded explicit origins. ## Are there any user-facing changes? Eligible `date_bin` aggregations can avoid a hash shuffle. Function results are unchanged. --- Note: This PR was developed with AI assistance. All changes have been reviewed, and I take full responsibility for this contribution.
1 parent 69a7fef commit f1ecc4a

8 files changed

Lines changed: 633 additions & 58 deletions

File tree

‎datafusion/expr/src/udf.rs‎

Lines changed: 23 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -355,9 +355,10 @@ impl ScalarUDF {
355355
pub fn supports_range_key_locality_analysis(
356356
&self,
357357
argument_types: &[DataType],
358+
literal_arguments: &[Option<&ScalarValue>],
358359
) -> bool {
359360
self.inner
360-
.supports_range_key_locality_analysis(argument_types)
361+
.supports_range_key_locality_analysis(argument_types, literal_arguments)
361362
}
362363

363364
pub fn preserves_lex_ordering(&self, inputs: &[ExprProperties]) -> Result<bool> {
@@ -979,8 +980,8 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
979980
Ok(inner(inputs))
980981
}
981982

982-
/// Returns whether this function and argument-type combination has been
983-
/// audited for range-partitioning locality analysis.
983+
/// Returns whether this function has been audited for range-key locality
984+
/// analysis with these argument types and literal values.
984985
///
985986
/// Range-boundary analysis has subtle correctness requirements, so the
986987
/// policy is default-deny. Functions may opt in only after individual audit.
@@ -998,7 +999,15 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
998999
/// This does not claim a concrete partition layout or cross-input
9991000
/// co-partitioning compatibility. Boundary evaluation errors cause the
10001001
/// analysis to return `false`. This capability is not transported across FFI.
1001-
fn supports_range_key_locality_analysis(&self, _argument_types: &[DataType]) -> bool {
1002+
///
1003+
/// `literal_arguments` has one entry per argument. `None` means the argument
1004+
/// is not a literal; `Some(value)` supplies its value, which may itself be
1005+
/// NULL. Non-literal expressions are not evaluated to obtain these values.
1006+
fn supports_range_key_locality_analysis(
1007+
&self,
1008+
_argument_types: &[DataType],
1009+
_literal_arguments: &[Option<&ScalarValue>],
1010+
) -> bool {
10021011
false
10031012
}
10041013

@@ -1224,9 +1233,13 @@ impl ScalarUDFImpl for AliasedScalarUDFImpl {
12241233
self.inner.output_ordering(inputs)
12251234
}
12261235

1227-
fn supports_range_key_locality_analysis(&self, argument_types: &[DataType]) -> bool {
1236+
fn supports_range_key_locality_analysis(
1237+
&self,
1238+
argument_types: &[DataType],
1239+
literal_arguments: &[Option<&ScalarValue>],
1240+
) -> bool {
12281241
self.inner
1229-
.supports_range_key_locality_analysis(argument_types)
1242+
.supports_range_key_locality_analysis(argument_types, literal_arguments)
12301243
}
12311244

12321245
fn preserves_lex_ordering(&self, inputs: &[ExprProperties]) -> Result<bool> {
@@ -1314,7 +1327,10 @@ mod tests {
13141327
#[test]
13151328
fn range_key_locality_analysis_is_disabled_by_default() {
13161329
let function = test_func("range_function", "a");
1317-
assert!(!function.supports_range_key_locality_analysis(&[DataType::Int64]));
1330+
assert!(!function.supports_range_key_locality_analysis(
1331+
&[DataType::Int64],
1332+
&[Some(&ScalarValue::Int64(Some(1)))],
1333+
));
13181334
}
13191335

13201336
fn test_func(name: &'static str, parameter: &'static str) -> ScalarUDF {

‎datafusion/functions/src/datetime/date_bin.rs‎

Lines changed: 170 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -276,6 +276,34 @@ impl ScalarUDFImpl for DateBinFunc {
276276
}
277277
}
278278

279+
fn supports_range_key_locality_analysis(
280+
&self,
281+
argument_types: &[DataType],
282+
literal_arguments: &[Option<&ScalarValue>],
283+
) -> bool {
284+
// With the epoch origin, a positive fixed-duration stride rounds down
285+
// monotonically. As in date_bin_impl, each day is 24 hours.
286+
// Timestamp binning preserves NULLs or returns an error.
287+
match (argument_types, literal_arguments) {
288+
(
289+
[
290+
DataType::Interval(MonthDayNano),
291+
Timestamp(Nanosecond, None),
292+
],
293+
[Some(ScalarValue::IntervalMonthDayNano(Some(stride))), None],
294+
) => {
295+
stride.months == 0
296+
&& TimeDelta::try_days(i64::from(stride.days))
297+
.and_then(|days| {
298+
days.checked_add(&Duration::nanoseconds(stride.nanoseconds))
299+
})
300+
.and_then(|stride| stride.num_nanoseconds())
301+
.is_some_and(|stride| stride > 0)
302+
}
303+
_ => false,
304+
}
305+
}
306+
279307
fn documentation(&self) -> Option<&Documentation> {
280308
self.doc()
281309
}
@@ -978,6 +1006,148 @@ mod tests {
9781006
);
9791007
}
9801008

1009+
#[test]
1010+
fn range_key_locality_requires_positive_fixed_duration_stride() {
1011+
use arrow::datatypes::DataType::Timestamp;
1012+
use arrow::datatypes::TimeUnit::Nanosecond;
1013+
1014+
let function = DateBinFunc::new();
1015+
let timestamp_type = Timestamp(Nanosecond, None);
1016+
let cases = [
1017+
(
1018+
"one nanosecond",
1019+
ScalarValue::new_interval_mdn(0, 0, 1),
1020+
true,
1021+
),
1022+
(
1023+
"one hour",
1024+
ScalarValue::new_interval_mdn(0, 0, 3_600_000_000_000),
1025+
true,
1026+
),
1027+
(
1028+
"largest nanosecond stride",
1029+
ScalarValue::new_interval_mdn(0, 0, i64::MAX),
1030+
true,
1031+
),
1032+
(
1033+
"NULL stride",
1034+
ScalarValue::IntervalMonthDayNano(None),
1035+
false,
1036+
),
1037+
("zero stride", ScalarValue::new_interval_mdn(0, 0, 0), false),
1038+
(
1039+
"negative stride",
1040+
ScalarValue::new_interval_mdn(0, 0, -1),
1041+
false,
1042+
),
1043+
(
1044+
"month stride",
1045+
ScalarValue::new_interval_mdn(1, 0, 0),
1046+
false,
1047+
),
1048+
("day stride", ScalarValue::new_interval_mdn(0, 1, 0), true),
1049+
(
1050+
"mixed day and nanosecond stride",
1051+
ScalarValue::new_interval_mdn(0, 1, 1),
1052+
true,
1053+
),
1054+
(
1055+
"day minus one nanosecond",
1056+
ScalarValue::new_interval_mdn(0, 1, -1),
1057+
true,
1058+
),
1059+
(
1060+
"negative day plus one nanosecond",
1061+
ScalarValue::new_interval_mdn(0, -1, 1),
1062+
false,
1063+
),
1064+
(
1065+
"combined zero stride",
1066+
ScalarValue::new_interval_mdn(0, 1, -86_400_000_000_000),
1067+
false,
1068+
),
1069+
(
1070+
"mixed month and day stride",
1071+
ScalarValue::new_interval_mdn(1, 1, 0),
1072+
false,
1073+
),
1074+
(
1075+
"combined stride overflows nanoseconds",
1076+
ScalarValue::new_interval_mdn(0, 1, i64::MAX),
1077+
false,
1078+
),
1079+
(
1080+
"day-time stride",
1081+
ScalarValue::new_interval_dt(0, 1000),
1082+
false,
1083+
),
1084+
];
1085+
for (description, stride, expected) in cases {
1086+
assert_eq!(
1087+
function.supports_range_key_locality_analysis(
1088+
&[stride.data_type(), timestamp_type.clone()],
1089+
&[Some(&stride), None],
1090+
),
1091+
expected,
1092+
"{description}",
1093+
);
1094+
}
1095+
}
1096+
1097+
#[test]
1098+
fn range_key_locality_rejects_unsupported_source_types() {
1099+
use arrow::datatypes::DataType::{Time64, Timestamp};
1100+
use arrow::datatypes::TimeUnit::{Microsecond, Millisecond, Nanosecond, Second};
1101+
1102+
let function = DateBinFunc::new();
1103+
let stride = ScalarValue::new_interval_mdn(0, 0, 3_600_000_000_000);
1104+
for source_type in [
1105+
Timestamp(Second, None),
1106+
Timestamp(Millisecond, None),
1107+
Timestamp(Microsecond, None),
1108+
Timestamp(Nanosecond, Some("UTC".into())),
1109+
Time64(Nanosecond),
1110+
] {
1111+
assert!(
1112+
!function.supports_range_key_locality_analysis(
1113+
&[stride.data_type(), source_type.clone()],
1114+
&[Some(&stride), None],
1115+
),
1116+
"source type {source_type:?}",
1117+
);
1118+
}
1119+
}
1120+
1121+
#[test]
1122+
fn range_key_locality_rejects_non_literal_stride() {
1123+
use arrow::datatypes::IntervalUnit::MonthDayNano;
1124+
1125+
let function = DateBinFunc::new();
1126+
let argument_types = [
1127+
DataType::Interval(MonthDayNano),
1128+
DataType::Timestamp(TimeUnit::Nanosecond, None),
1129+
];
1130+
assert!(
1131+
!function
1132+
.supports_range_key_locality_analysis(&argument_types, &[None, None])
1133+
);
1134+
}
1135+
1136+
#[test]
1137+
fn range_key_locality_rejects_explicit_origin() {
1138+
let function = DateBinFunc::new();
1139+
let stride = ScalarValue::new_interval_mdn(0, 0, 3_600_000_000_000);
1140+
let epoch = ScalarValue::TimestampNanosecond(Some(0), None);
1141+
assert!(!function.supports_range_key_locality_analysis(
1142+
&[
1143+
stride.data_type(),
1144+
DataType::Timestamp(TimeUnit::Nanosecond, None),
1145+
epoch.data_type(),
1146+
],
1147+
&[Some(&stride), None, Some(&epoch)],
1148+
));
1149+
}
1150+
9811151
#[test]
9821152
fn output_ordering_requires_constant_stride() {
9831153
use arrow::compute::SortOptions;

‎datafusion/functions/src/datetime/date_trunc.rs‎

Lines changed: 29 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -559,7 +559,11 @@ impl ScalarUDFImpl for DateTruncFunc {
559559
}
560560
}
561561

562-
fn supports_range_key_locality_analysis(&self, argument_types: &[DataType]) -> bool {
562+
fn supports_range_key_locality_analysis(
563+
&self,
564+
argument_types: &[DataType],
565+
_literal_arguments: &[Option<&ScalarValue>],
566+
) -> bool {
563567
// Across an America/Goose_Bay transition, ascending epoch seconds
564568
// 562129259 < 562129260 truncate to 562129200 > 562125600.
565569
// Keep the audited domain to timezone-less timestamp columns.
@@ -1400,19 +1404,30 @@ mod tests {
14001404
fn range_key_locality_analysis_requires_timezone_less_timestamp() {
14011405
let date_trunc = DateTruncFunc::new();
14021406

1403-
assert!(date_trunc.supports_range_key_locality_analysis(&[
1404-
DataType::Utf8,
1405-
DataType::Timestamp(TimeUnit::Nanosecond, None),
1406-
]));
1407-
assert!(!date_trunc.supports_range_key_locality_analysis(&[
1408-
DataType::Utf8,
1409-
DataType::Timestamp(TimeUnit::Nanosecond, Some("UTC".into())),
1410-
]));
1411-
assert!(!date_trunc.supports_range_key_locality_analysis(&[
1412-
DataType::Int64,
1413-
DataType::Timestamp(TimeUnit::Nanosecond, None),
1414-
]));
1415-
assert!(!date_trunc.supports_range_key_locality_analysis(&[DataType::Utf8]));
1407+
assert!(date_trunc.supports_range_key_locality_analysis(
1408+
&[
1409+
DataType::Utf8,
1410+
DataType::Timestamp(TimeUnit::Nanosecond, None),
1411+
],
1412+
&[None, None],
1413+
));
1414+
assert!(!date_trunc.supports_range_key_locality_analysis(
1415+
&[
1416+
DataType::Utf8,
1417+
DataType::Timestamp(TimeUnit::Nanosecond, Some("UTC".into())),
1418+
],
1419+
&[None, None],
1420+
));
1421+
assert!(!date_trunc.supports_range_key_locality_analysis(
1422+
&[
1423+
DataType::Int64,
1424+
DataType::Timestamp(TimeUnit::Nanosecond, None),
1425+
],
1426+
&[None, None],
1427+
));
1428+
assert!(
1429+
!date_trunc.supports_range_key_locality_analysis(&[DataType::Utf8], &[None])
1430+
);
14161431
}
14171432

14181433
fn invoke_date_trunc(

0 commit comments

Comments
 (0)