Skip to content

Commit bce729e

Browse files
committed
perf: optimize date_trunc in datafusion-functions
1 parent 3a29d6b commit bce729e

2 files changed

Lines changed: 182 additions & 81 deletions

File tree

‎datafusion/functions/benches/date_trunc.rs‎

Lines changed: 64 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -18,52 +18,64 @@
1818
use std::hint::black_box;
1919
use std::sync::Arc;
2020

21-
use arrow::array::{Array, ArrayRef, TimestampSecondArray};
21+
use arrow::array::{Array, ArrayRef, TimestampNanosecondArray, TimestampSecondArray};
2222
use arrow::datatypes::Field;
2323
use criterion::{Criterion, criterion_group, criterion_main};
2424
use datafusion_common::ScalarValue;
2525
use datafusion_common::config::ConfigOptions;
2626
use datafusion_expr::{ColumnarValue, ReturnFieldArgs, ScalarFunctionArgs};
2727
use datafusion_functions::datetime::date_trunc;
28-
use rand::Rng;
29-
use rand::rngs::ThreadRng;
28+
use rand::rngs::StdRng;
29+
use rand::{Rng, SeedableRng};
3030

31-
fn timestamps(rng: &mut ThreadRng) -> TimestampSecondArray {
32-
let mut seconds = vec![];
33-
for _ in 0..1000 {
34-
seconds.push(rng.random_range(0..1_000_000));
35-
}
31+
const NUM_ROWS: usize = 1000;
32+
const NANOS_PER_SECOND: i64 = 1_000_000_000;
33+
/// Roughly 30 years, so that values span many months, quarters and years.
34+
const RANGE_SECONDS: i64 = 30 * 365 * 24 * 60 * 60;
3635

37-
TimestampSecondArray::from(seconds)
36+
fn seedable_rng() -> StdRng {
37+
StdRng::seed_from_u64(42)
3838
}
3939

40-
fn criterion_benchmark(c: &mut Criterion) {
41-
c.bench_function("date_trunc_minute_1000", |b| {
42-
let mut rng = rand::rng();
43-
let timestamps_array = Arc::new(timestamps(&mut rng)) as ArrayRef;
44-
let batch_len = timestamps_array.len();
45-
let precision =
46-
ColumnarValue::Scalar(ScalarValue::Utf8(Some("minute".to_string())));
47-
let timestamps = ColumnarValue::Array(timestamps_array);
48-
let udf = date_trunc();
49-
let args = vec![precision, timestamps];
50-
let arg_fields = args
51-
.iter()
52-
.enumerate()
53-
.map(|(idx, arg)| {
54-
Field::new(format!("arg_{idx}"), arg.data_type(), true).into()
55-
})
56-
.collect::<Vec<_>>();
40+
fn second_timestamps() -> TimestampSecondArray {
41+
let mut rng = seedable_rng();
42+
(0..NUM_ROWS)
43+
.map(|_| Some(rng.random_range(0..1_000_000i64)))
44+
.collect()
45+
}
5746

58-
let scalar_arguments = vec![None; arg_fields.len()];
59-
let return_field = udf
60-
.return_field_from_args(ReturnFieldArgs {
61-
arg_fields: &arg_fields,
62-
scalar_arguments: &scalar_arguments,
63-
})
64-
.unwrap();
65-
let config_options = Arc::new(ConfigOptions::default());
47+
fn nanosecond_timestamps() -> TimestampNanosecondArray {
48+
let mut rng = seedable_rng();
49+
(0..NUM_ROWS)
50+
.map(|_| {
51+
let seconds = rng.random_range(-RANGE_SECONDS..RANGE_SECONDS);
52+
Some(seconds * NANOS_PER_SECOND + rng.random_range(0..NANOS_PER_SECOND))
53+
})
54+
.collect()
55+
}
56+
57+
fn run_benchmark(c: &mut Criterion, name: &str, granularity: &str, array: ArrayRef) {
58+
let batch_len = array.len();
59+
let precision =
60+
ColumnarValue::Scalar(ScalarValue::Utf8(Some(granularity.to_string())));
61+
let udf = date_trunc();
62+
let args = vec![precision, ColumnarValue::Array(array)];
63+
let arg_fields = args
64+
.iter()
65+
.enumerate()
66+
.map(|(idx, arg)| Field::new(format!("arg_{idx}"), arg.data_type(), true).into())
67+
.collect::<Vec<_>>();
6668

69+
let scalar_arguments = vec![None; arg_fields.len()];
70+
let return_field = udf
71+
.return_field_from_args(ReturnFieldArgs {
72+
arg_fields: &arg_fields,
73+
scalar_arguments: &scalar_arguments,
74+
})
75+
.unwrap();
76+
let config_options = Arc::new(ConfigOptions::default());
77+
78+
c.bench_function(name, |b| {
6779
b.iter(|| {
6880
black_box(
6981
udf.invoke_with_args(ScalarFunctionArgs {
@@ -79,5 +91,23 @@ fn criterion_benchmark(c: &mut Criterion) {
7991
});
8092
}
8193

94+
fn criterion_benchmark(c: &mut Criterion) {
95+
let seconds: ArrayRef = Arc::new(second_timestamps());
96+
run_benchmark(c, "date_trunc_minute_1000", "minute", Arc::clone(&seconds));
97+
run_benchmark(c, "date_trunc_month_second_1000", "month", seconds);
98+
99+
// Coarse granularities on an untimezoned array: these need calendar
100+
// arithmetic rather than a plain division.
101+
let nanos: ArrayRef = Arc::new(nanosecond_timestamps());
102+
for granularity in ["week", "month", "quarter", "year"] {
103+
run_benchmark(
104+
c,
105+
&format!("date_trunc_{granularity}_nanos_1000"),
106+
granularity,
107+
Arc::clone(&nanos),
108+
);
109+
}
110+
}
111+
82112
criterion_group!(benches, criterion_benchmark);
83113
criterion_main!(benches);

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

Lines changed: 118 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,6 @@ use std::sync::Arc;
2323

2424
use arrow::array::temporal_conversions::{
2525
MICROSECONDS, MILLISECONDS, NANOSECONDS, as_datetime_with_timezone,
26-
timestamp_ns_to_datetime,
2726
};
2827
use arrow::array::timezone::Tz;
2928
use arrow::array::types::{
@@ -462,6 +461,7 @@ const NANOS_PER_MILLISECOND: i64 = NANOSECONDS / MILLISECONDS;
462461
const NANOS_PER_SECOND: i64 = NANOSECONDS;
463462
const NANOS_PER_MINUTE: i64 = 60 * NANOS_PER_SECOND;
464463
const NANOS_PER_HOUR: i64 = 60 * NANOS_PER_MINUTE;
464+
const NANOS_PER_DAY: i64 = 24 * NANOS_PER_HOUR;
465465

466466
const MICROS_PER_MILLISECOND: i64 = MICROSECONDS / MILLISECONDS;
467467
const MICROS_PER_SECOND: i64 = MICROSECONDS;
@@ -591,52 +591,128 @@ where
591591

592592
fn _date_trunc_coarse_with_tz(
593593
granularity: DateTruncGranularity,
594-
value: Option<DateTime<Tz>>,
594+
value: DateTime<Tz>,
595595
) -> Result<Option<i64>> {
596-
if let Some(value) = value {
597-
let local = value.naive_local();
598-
let truncated = _date_trunc_coarse::<NaiveDateTime>(granularity, Some(local))?;
599-
let truncated = truncated.and_then(|truncated| {
600-
match truncated.and_local_timezone(value.timezone()) {
601-
LocalResult::None => {
602-
// This can happen if the date_trunc operation moves the time into
603-
// an hour that doesn't exist due to daylight savings. On known example where
604-
// this can happen is with historic dates in the America/Sao_Paulo time zone.
605-
// To account for this adjust the time by a few hours, convert to local time,
606-
// and then adjust the time back.
607-
truncated
608-
.sub(TimeDelta::try_hours(3).unwrap())
609-
.and_local_timezone(value.timezone())
610-
.single()
611-
.map(|v| v.add(TimeDelta::try_hours(3).unwrap()))
612-
}
613-
LocalResult::Single(datetime) => Some(datetime),
614-
LocalResult::Ambiguous(datetime1, datetime2) => {
615-
// Because we are truncating from an equally or more specific time
616-
// the original time must have been within the ambiguous local time
617-
// period. Therefore the offset of one of these times should match the
618-
// offset of the original time.
619-
if datetime1.offset().fix() == value.offset().fix() {
620-
Some(datetime1)
621-
} else {
622-
Some(datetime2)
623-
}
596+
let local = value.naive_local();
597+
let truncated = _date_trunc_coarse::<NaiveDateTime>(granularity, Some(local))?;
598+
let truncated = truncated.and_then(|truncated| {
599+
match truncated.and_local_timezone(value.timezone()) {
600+
LocalResult::None => {
601+
// This can happen if the date_trunc operation moves the time into
602+
// an hour that doesn't exist due to daylight savings. On known example where
603+
// this can happen is with historic dates in the America/Sao_Paulo time zone.
604+
// To account for this adjust the time by a few hours, convert to local time,
605+
// and then adjust the time back.
606+
truncated
607+
.sub(TimeDelta::try_hours(3).unwrap())
608+
.and_local_timezone(value.timezone())
609+
.single()
610+
.map(|v| v.add(TimeDelta::try_hours(3).unwrap()))
611+
}
612+
LocalResult::Single(datetime) => Some(datetime),
613+
LocalResult::Ambiguous(datetime1, datetime2) => {
614+
// Because we are truncating from an equally or more specific time
615+
// the original time must have been within the ambiguous local time
616+
// period. Therefore the offset of one of these times should match the
617+
// offset of the original time.
618+
if datetime1.offset().fix() == value.offset().fix() {
619+
Some(datetime1)
620+
} else {
621+
Some(datetime2)
624622
}
625623
}
626-
});
627-
Ok(truncated.and_then(|value| value.timestamp_nanos_opt()))
624+
}
625+
});
626+
Ok(truncated.and_then(|value| value.timestamp_nanos_opt()))
627+
}
628+
629+
/// Days from the Unix epoch to 0000-03-01, the epoch used by the civil calendar
630+
/// conversions below.
631+
const DAYS_EPOCH_SHIFT: i64 = 719_468;
632+
633+
/// Days in a 400 year era of the proleptic Gregorian calendar.
634+
const DAYS_PER_ERA: i64 = 146_097;
635+
636+
/// Splits a day count relative to the Unix epoch into a proleptic Gregorian
637+
/// year, month (1-12) and day of month (1-31).
638+
fn civil_from_days(days: i64) -> (i64, i64, i64) {
639+
let z = days + DAYS_EPOCH_SHIFT;
640+
let era = z.div_euclid(DAYS_PER_ERA);
641+
let day_of_era = z.rem_euclid(DAYS_PER_ERA);
642+
let year_of_era = (day_of_era - day_of_era / 1460 + day_of_era / 36524
643+
- day_of_era / 146_096)
644+
/ 365;
645+
let day_of_year =
646+
day_of_era - (365 * year_of_era + year_of_era / 4 - year_of_era / 100);
647+
// Month index with March as 0, so that the leap day falls at the end of the year.
648+
let month_index = (5 * day_of_year + 2) / 153;
649+
let day = day_of_year - (153 * month_index + 2) / 5 + 1;
650+
let month = if month_index < 10 {
651+
month_index + 3
628652
} else {
629-
_date_trunc_coarse::<NaiveDateTime>(granularity, None)?;
630-
Ok(None)
631-
}
653+
month_index - 9
654+
};
655+
let year = year_of_era + era * 400 + i64::from(month <= 2);
656+
(year, month, day)
632657
}
633658

659+
/// Inverse of [`civil_from_days`]: the day count relative to the Unix epoch for
660+
/// the given proleptic Gregorian date.
661+
fn days_from_civil(year: i64, month: i64, day: i64) -> i64 {
662+
let year = year - i64::from(month <= 2);
663+
let era = year.div_euclid(400);
664+
let year_of_era = year.rem_euclid(400);
665+
let month_index = if month > 2 { month - 3 } else { month + 9 };
666+
let day_of_year = (153 * month_index + 2) / 5 + day - 1;
667+
let day_of_era =
668+
year_of_era * 365 + year_of_era / 4 - year_of_era / 100 + day_of_year;
669+
era * DAYS_PER_ERA + day_of_era - DAYS_EPOCH_SHIFT
670+
}
671+
672+
/// Truncates a UTC nanosecond timestamp with integer arithmetic. Truncating on
673+
/// the calendar directly avoids converting every value to a `NaiveDateTime` and
674+
/// rebuilding it field by field.
675+
///
676+
/// Returns `None` when the truncated timestamp is no longer representable as
677+
/// nanoseconds since the epoch, which the caller reports as an out of range
678+
/// error.
634679
fn _date_trunc_coarse_without_tz(
635680
granularity: DateTruncGranularity,
636-
value: Option<NaiveDateTime>,
637-
) -> Result<Option<i64>> {
638-
let value = _date_trunc_coarse::<NaiveDateTime>(granularity, value)?;
639-
Ok(value.and_then(|value| value.and_utc().timestamp_nanos_opt()))
681+
value: i64,
682+
) -> Option<i64> {
683+
let truncate_to = |unit: i64| value.checked_sub(value.rem_euclid(unit));
684+
let days = || value.div_euclid(NANOS_PER_DAY);
685+
let nanos_from_days = |days: i64| days.checked_mul(NANOS_PER_DAY);
686+
687+
match granularity {
688+
// Sub-second granularities are applied by the caller, which rescales
689+
// the nanoseconds to the time unit of the array.
690+
DateTruncGranularity::Millisecond | DateTruncGranularity::Microsecond => {
691+
Some(value)
692+
}
693+
DateTruncGranularity::Second => truncate_to(NANOS_PER_SECOND),
694+
DateTruncGranularity::Minute => truncate_to(NANOS_PER_MINUTE),
695+
DateTruncGranularity::Hour => truncate_to(NANOS_PER_HOUR),
696+
DateTruncGranularity::Day => nanos_from_days(days()),
697+
DateTruncGranularity::Week => {
698+
let days = days();
699+
// `Weekday::num_days_from_monday` for the epoch (a Thursday) is 3.
700+
nanos_from_days(days - (days + 3).rem_euclid(7))
701+
}
702+
DateTruncGranularity::Month => {
703+
let days = days();
704+
let (_, _, day_of_month) = civil_from_days(days);
705+
nanos_from_days(days - (day_of_month - 1))
706+
}
707+
DateTruncGranularity::Quarter => {
708+
let (year, month, _) = civil_from_days(days());
709+
nanos_from_days(days_from_civil(year, 1 + 3 * ((month - 1) / 3), 1))
710+
}
711+
DateTruncGranularity::Year => {
712+
let (year, _, _) = civil_from_days(days());
713+
nanos_from_days(days_from_civil(year, 1, 1))
714+
}
715+
}
640716
}
641717

642718
/// Truncates the single `value`, expressed in nanoseconds since the
@@ -655,15 +731,10 @@ fn date_trunc_coarse(
655731
// and NaiveDateTime (ISO 8601) has no concept of timezones
656732
let value = as_datetime_with_timezone::<TimestampNanosecondType>(value, tz)
657733
.ok_or(exec_datafusion_err!("Timestamp {value} out of range"))?;
658-
_date_trunc_coarse_with_tz(granularity, Some(value))
659-
}
660-
None => {
661-
// Use chrono NaiveDateTime to clear the various fields, if we don't have a timezone.
662-
let value = timestamp_ns_to_datetime(value)
663-
.ok_or_else(|| exec_datafusion_err!("Timestamp {value} out of range"))?;
664-
_date_trunc_coarse_without_tz(granularity, Some(value))
734+
_date_trunc_coarse_with_tz(granularity, value)?
665735
}
666-
}?;
736+
None => _date_trunc_coarse_without_tz(granularity, value),
737+
};
667738

668739
value.ok_or_else(|| {
669740
exec_datafusion_err!(

0 commit comments

Comments
 (0)