Skip to content

Commit 5833e7f

Browse files
committed
perf: bound the timestamp classifier's fixed-width digit scans
1 parent 77f7e06 commit 5833e7f

2 files changed

Lines changed: 64 additions & 18 deletions

File tree

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

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,12 @@ fn criterion_benchmark(c: &mut Criterion) {
120120
}),
121121
),
122122
("invalid", create_batch(|_| "not a timestamp".to_string())),
123+
// A long malformed value. Rejecting it must cost a bounded prefix, not a scan of every
124+
// digit before and again after the `Z` is stripped.
125+
(
126+
"long_digits_zone",
127+
create_batch(|_| format!("{}Z", "1".repeat(1024))),
128+
),
123129
// The parser only runs for non-null slots, so a mostly-null batch must not get slower.
124130
(
125131
"dense_nulls",
@@ -202,8 +208,10 @@ fn criterion_benchmark(c: &mut Criterion) {
202208
// ANSI raises on the first value the parser rejects, so timing it against a
203209
// batch that holds one would measure the error path rather than the parser.
204210
// `timestamp_ntz_parser` additionally rejects time-only strings.
205-
let ansi_raises = matches!(*name, "mixed" | "invalid" | "date_only_zone")
206-
|| (*name == "time_only" && target_name == "timestamp_ntz");
211+
let ansi_raises = matches!(
212+
*name,
213+
"mixed" | "invalid" | "date_only_zone" | "long_digits_zone"
214+
) || (*name == "time_only" && target_name == "timestamp_ntz");
207215
if mode == EvalMode::Ansi && ansi_raises {
208216
continue;
209217
}

‎native/spark-expr/src/conversion_funcs/string.rs‎

Lines changed: 54 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1711,35 +1711,53 @@ fn classify_timestamp_pattern(value: &str) -> Option<TimestampPattern> {
17111711
[b'+' | b'-', rest @ ..] => (true, rest),
17121712
_ => (false, bytes),
17131713
};
1714-
let digits = digit_run(rest);
1714+
let digits = digit_run(rest, MAX_YEAR_DIGITS + 1);
17151715
let after_digits = &rest[digits..];
17161716
match after_digits.first() {
17171717
// Year only.
1718-
None => (4..=6).contains(&digits).then_some(TimestampPattern::Year),
1718+
None => (4..=MAX_YEAR_DIGITS)
1719+
.contains(&digits)
1720+
.then_some(TimestampPattern::Year),
17191721
// A year of 4-6 digits followed by the date separator.
1720-
Some(b'-') if (4..=6).contains(&digits) => classify_date_tail(&after_digits[1..]),
1722+
Some(b'-') if (4..=MAX_YEAR_DIGITS).contains(&digits) => {
1723+
classify_date_tail(&after_digits[1..])
1724+
}
17211725
// Bare time-only shapes take a 1-2 digit hour and no sign.
17221726
Some(b':') if !signed && (1..=2).contains(&digits) => classify_time(rest, false),
17231727
_ => None,
17241728
}
17251729
}
17261730

1727-
/// Number of leading ASCII digits in `bytes`.
1728-
fn digit_run(bytes: &[u8]) -> usize {
1731+
/// The most year digits Spark's `isValidDigits` accepts (`maxDigitsYear`).
1732+
const MAX_YEAR_DIGITS: usize = 6;
1733+
1734+
/// The most digits Spark's `isValidDigits` accepts in a month, day, hour, minute or second.
1735+
const MAX_SEGMENT_DIGITS: usize = 2;
1736+
1737+
/// Number of leading ASCII digits in `bytes`, counting no more than `limit`.
1738+
///
1739+
/// The fixed-width segments pass one more than their widest valid length, which is enough to
1740+
/// reject an overlong run. Stopping there keeps a long malformed value, such as thousands of
1741+
/// digits followed by `Z`, from being scanned end to end, and then again after the zone is
1742+
/// stripped; the regexes this replaced also gave up after a bounded prefix.
1743+
fn digit_run(bytes: &[u8], limit: usize) -> usize {
17291744
bytes
17301745
.iter()
1731-
.position(|b| !b.is_ascii_digit())
1732-
.unwrap_or(bytes.len())
1746+
.take(limit)
1747+
.take_while(|b| b.is_ascii_digit())
1748+
.count()
17331749
}
17341750

17351751
/// `bytes` past a leading 1-2 digit segment, or `None` when it does not start with one.
17361752
///
17371753
/// Taking the whole digit run is equivalent to the regexes' `[0-9]{1,2}`: every segment is
17381754
/// followed by a separator or the end of the string, so a run of three or more digits can
1739-
/// never match.
1755+
/// never match, and counting to three is enough to tell.
17401756
fn skip_segment(bytes: &[u8]) -> Option<&[u8]> {
1741-
let digits = digit_run(bytes);
1742-
(1..=2).contains(&digits).then(|| &bytes[digits..])
1757+
let digits = digit_run(bytes, MAX_SEGMENT_DIGITS + 1);
1758+
(1..=MAX_SEGMENT_DIGITS)
1759+
.contains(&digits)
1760+
.then(|| &bytes[digits..])
17431761
}
17441762

17451763
/// Classifies `[0-9]{1,2}(:[0-9]{1,2}(:[0-9]{1,2}(\.[0-9]*)?)?)?`, the time-only shapes. A bare
@@ -1758,12 +1776,12 @@ fn classify_time(bytes: &[u8], t_prefixed: bool) -> Option<TimestampPattern> {
17581776
if bytes.is_empty() {
17591777
return Some(if t_prefixed { TimeOnlyHms } else { BareHms });
17601778
}
1779+
// A fraction may be any length, so it is the one run that has to be scanned in full.
17611780
let fraction = bytes.strip_prefix(b".")?;
1762-
(digit_run(fraction) == fraction.len()).then_some(if t_prefixed {
1763-
TimeOnlyHmsu
1764-
} else {
1765-
BareHmsu
1766-
})
1781+
fraction
1782+
.iter()
1783+
.all(u8::is_ascii_digit)
1784+
.then_some(if t_prefixed { TimeOnlyHmsu } else { BareHmsu })
17671785
}
17681786

17691787
/// Classifies `[0-9]{1,2}(-[0-9]{1,2}([T ][0-9]{1,2}(:[0-9]{1,2}(:[0-9]{1,2}(\.[0-9]*)?)?)?)?)?`,
@@ -1794,7 +1812,10 @@ fn classify_date_tail(bytes: &[u8]) -> Option<TimestampPattern> {
17941812
return Some(Second);
17951813
}
17961814
let fraction = bytes.strip_prefix(b".")?;
1797-
(digit_run(fraction) == fraction.len()).then_some(Microsecond)
1815+
fraction
1816+
.iter()
1817+
.all(u8::is_ascii_digit)
1818+
.then_some(Microsecond)
17981819
}
17991820

18001821
/// Parses `value` according to the shape already determined for it by
@@ -2206,6 +2227,8 @@ mod tests {
22062227
"-002020-1-2 3:4",
22072228
"T1:2:3.",
22082229
"1:2:3.4",
2230+
"0000000002020-01-01T12:34:56Z",
2231+
"2020-01-01T12:34:56.123456789012",
22092232
] {
22102233
check(seed);
22112234
for i in 0..seed.len() {
@@ -2264,6 +2287,21 @@ mod tests {
22642287
classify_timestamp_pattern("2020-01-01 12:34:56."),
22652288
Some(Microsecond)
22662289
);
2290+
// An overlong run is rejected however long it is, while a fraction may be any length.
2291+
let long = "1".repeat(8192);
2292+
assert_eq!(classify_timestamp_pattern(&long), None);
2293+
assert_eq!(classify_timestamp_pattern(&format!("{long}Z")), None);
2294+
assert_eq!(classify_timestamp_pattern(&format!("-{long}-01")), None);
2295+
assert_eq!(classify_timestamp_pattern(&format!("2020-{long}")), None);
2296+
assert_eq!(classify_timestamp_pattern(&format!("T1:{long}")), None);
2297+
assert_eq!(
2298+
classify_timestamp_pattern(&format!("2020-01-01 12:34:56.{long}")),
2299+
Some(Microsecond)
2300+
);
2301+
assert_eq!(
2302+
classify_timestamp_pattern(&format!("1:2:3.{long}")),
2303+
Some(BareHmsu)
2304+
);
22672305
}
22682306

22692307
#[test]

0 commit comments

Comments
 (0)