Skip to content

Commit 70dbd29

Browse files
Toby1009Omega359
authored andcommitted
fix: preserve sorts for non-monotonic temporal casts (apache#25526)
## Which issue does this PR close? - Closes apache#25506. ## Rationale for this change `ORDER BY CAST(ts AS TIME)` can return incorrectly ordered results when an already ordered timestamp input crosses midnight. A named timezone rollback can similarly make a timestamp-to-date conversion non-monotonic. In both cases, DataFusion may incorrectly reuse the input ordering and remove the sort required by the cast result. ## What changes are included in this PR? Replace the broad temporal-to-temporal ordering rule with an explicit list of order-preserving temporal casts. Keep the existing lossless cast check separate because it provides the stronger guarantees used for strict ordering and statistics propagation. Cast expressions that may turn conversion failures into NULL no longer propagate ordering unless the conversion is known to be lossless, since a new NULL can violate `NULLS FIRST` or `NULLS LAST`. ## What is the testing strategy for this PR? The unit tests cover safe and unsafe temporal cast combinations, both sort directions, both NULL placements, unknown input types, and NULL-on-failure casts. The cases added to `cast.slt` cover timestamp-to-time conversion across midnight, timestamp-to-date conversion across a named timezone rollback, and verify that reducing timestamp precision still avoids an unnecessary sort. ## Are there any user-facing changes? Queries that order by a non-monotonic temporal cast now retain the required sort and return correctly ordered results. There are no public API changes.
1 parent 4941f6a commit 70dbd29

2 files changed

Lines changed: 301 additions & 11 deletions

File tree

  • datafusion

‎datafusion/physical-expr/src/expressions/cast.rs‎

Lines changed: 212 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -283,26 +283,63 @@ impl CastExpr {
283283
}
284284
}
285285

286-
pub(crate) fn is_order_preserving_cast_family(
287-
source_type: &DataType,
288-
target_type: &DataType,
289-
) -> bool {
290-
(source_type.is_numeric() || *source_type == Boolean) && target_type.is_numeric()
291-
|| source_type.is_temporal() && target_type.is_temporal()
292-
|| source_type.eq(target_type)
286+
/// UTC and fixed offsets have no timezone transitions.
287+
fn is_fixed_offset(tz: &str) -> bool {
288+
tz == "UTC" || tz.starts_with(['+', '-'])
289+
}
290+
291+
/// Whether successful casts preserve order when conversion failures return errors.
292+
/// Unlike `check_bigger_cast`, this allows precision loss and is not sufficient
293+
/// for propagating distinct counts or the ordering of subsequent sort keys.
294+
fn is_order_preserving_cast(source_type: &DataType, target_type: &DataType) -> bool {
295+
use arrow::datatypes::TimeUnit::*;
296+
if source_type == target_type
297+
|| (source_type.is_numeric() || *source_type == Boolean)
298+
&& target_type.is_numeric()
299+
{
300+
return true;
301+
}
302+
// Temporal casts are not generally monotonic: extracting time-of-day wraps
303+
// at midnight, and timezone transitions can reverse the local date.
304+
match (source_type, target_type) {
305+
(Date32 | Date64, Date32 | Date64)
306+
| (Date32 | Date64, Timestamp(_, None))
307+
| (Timestamp(_, None), Date32) => true,
308+
(Timestamp(_, Some(tz)), Date32) => is_fixed_offset(tz),
309+
// Arrow converts timestamps to Date64 by scaling the epoch value,
310+
// whereas Date32 extracts the date in the timestamp's timezone.
311+
(Timestamp(_, _), Date64) => true,
312+
// Only admit scaling that cannot wrap on overflow. Time64 widening
313+
// and narrowing to Time32 do not currently check overflow in Arrow.
314+
(Time32(Second | Millisecond), Time32(Second | Millisecond))
315+
| (Time32(Second | Millisecond), Time64(Microsecond | Nanosecond))
316+
| (Time64(Nanosecond), Time64(Microsecond))
317+
| (Duration(_), Duration(_)) => true,
318+
(Timestamp(_, from_tz), Timestamp(_, to_tz)) => {
319+
// Adding a timezone to naive timestamps interprets local times;
320+
// other timezone changes only change metadata on the epoch value.
321+
from_tz.is_some() || to_tz.as_deref().is_none_or(is_fixed_offset)
322+
}
323+
_ => false,
324+
}
293325
}
294326

295327
pub(crate) fn cast_expr_properties(
296328
child: &ExprProperties,
297329
target_type: &DataType,
330+
null_on_failure: bool,
298331
) -> Result<ExprProperties> {
299332
let unbounded = Interval::make_unbounded(target_type)?;
300333
let source_type = child.range.data_type();
301334
// A lossless cast recognized by check_bigger_cast is one-to-one, so it is
302335
// strictly order-preserving; a narrowing cast may collapse distinct values,
303336
// breaking the ordering of subsequent sort keys.
304337
let bigger_cast = CastExpr::check_bigger_cast(target_type, &source_type);
305-
if is_order_preserving_cast_family(&source_type, target_type) || bigger_cast {
338+
// New NULLs from failed conversions may violate NULLS FIRST/LAST, even
339+
// if the successfully converted values remain ordered.
340+
if bigger_cast
341+
|| (!null_on_failure && is_order_preserving_cast(&source_type, target_type))
342+
{
306343
Ok(child
307344
.clone()
308345
.with_range(unbounded)
@@ -396,10 +433,9 @@ impl PhysicalExpr for CastExpr {
396433
]))
397434
}
398435

399-
/// A [`CastExpr`] preserves the ordering of its child if the cast is done
400-
/// under the same datatype family.
436+
/// Propagate ordering only for supported order-preserving conversions.
401437
fn get_properties(&self, children: &[ExprProperties]) -> Result<ExprProperties> {
402-
cast_expr_properties(&children[0], self.cast_type())
438+
cast_expr_properties(&children[0], self.cast_type(), self.cast_options.safe)
403439
}
404440

405441
fn fmt_sql(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
@@ -1693,6 +1729,171 @@ mod tests {
16931729
}
16941730
}
16951731

1732+
#[test]
1733+
fn test_temporal_cast_ordering() {
1734+
use TimeUnit::*;
1735+
use arrow::compute::SortOptions;
1736+
use datafusion_expr_common::sort_properties::SortProperties;
1737+
1738+
let timezone = Some("America/Goose_Bay".into());
1739+
// Expected ordering is independent of strictness: discarding precision
1740+
// may merge values, but must not reverse them.
1741+
let cases = [
1742+
(Date32, Date64, true),
1743+
(Date64, Date32, true),
1744+
(Date32, Timestamp(Nanosecond, None), true),
1745+
(Date64, Timestamp(Second, None), true),
1746+
(Timestamp(Second, None), Date32, true),
1747+
(Timestamp(Second, Some("UTC".into())), Date32, true),
1748+
(Timestamp(Second, Some("+08:00".into())), Date32, true),
1749+
(Timestamp(Second, timezone.clone()), Date32, false),
1750+
(Timestamp(Second, timezone.clone()), Date64, true),
1751+
(Timestamp(Second, None), Timestamp(Nanosecond, None), true),
1752+
(Timestamp(Nanosecond, None), Timestamp(Second, None), true),
1753+
(
1754+
Timestamp(Second, None),
1755+
Timestamp(Second, timezone.clone()),
1756+
false,
1757+
),
1758+
(
1759+
Timestamp(Second, None),
1760+
Timestamp(Second, Some("+08:00".into())),
1761+
true,
1762+
),
1763+
(
1764+
Timestamp(Second, timezone.clone()),
1765+
Timestamp(Second, None),
1766+
true,
1767+
),
1768+
(
1769+
Timestamp(Second, timezone.clone()),
1770+
Timestamp(Millisecond, Some("UTC".into())),
1771+
true,
1772+
),
1773+
(Timestamp(Second, None), Time32(Second), false),
1774+
(Timestamp(Nanosecond, timezone), Time64(Nanosecond), false),
1775+
(Time32(Second), Time32(Millisecond), true),
1776+
(Time32(Millisecond), Time32(Second), true),
1777+
(Time32(Second), Time64(Nanosecond), true),
1778+
(Time64(Nanosecond), Time64(Microsecond), true),
1779+
(Time64(Microsecond), Time64(Nanosecond), false),
1780+
(Time64(Nanosecond), Time32(Second), false),
1781+
(Duration(Second), Duration(Nanosecond), true),
1782+
(Duration(Nanosecond), Duration(Second), true),
1783+
(Null, Timestamp(Second, None), false),
1784+
];
1785+
for (source, target, preserves_order) in cases {
1786+
let schema = Schema::new(vec![Field::new("a", source.clone(), true)]);
1787+
let expr = CastExpr::new(
1788+
col("a", &schema).expect("column exists"),
1789+
target.clone(),
1790+
None,
1791+
);
1792+
for descending in [false, true] {
1793+
for nulls_first in [false, true] {
1794+
let ordered = SortProperties::Ordered(SortOptions {
1795+
descending,
1796+
nulls_first,
1797+
});
1798+
let child = ExprProperties::new_unknown()
1799+
.with_range(
1800+
Interval::make_unbounded(&source)
1801+
.expect("supported interval type"),
1802+
)
1803+
.with_order(ordered)
1804+
.with_strictly_order_preserving(true);
1805+
let properties =
1806+
expr.get_properties(&[child]).expect("cast properties");
1807+
assert_eq!(
1808+
properties.sort_properties,
1809+
if preserves_order {
1810+
ordered
1811+
} else {
1812+
SortProperties::Unordered
1813+
},
1814+
"{source} -> {target}, descending={descending}, nulls_first={nulls_first}"
1815+
);
1816+
assert_eq!(properties.range.data_type(), target);
1817+
assert!(!properties.strictly_order_preserving);
1818+
}
1819+
}
1820+
}
1821+
}
1822+
1823+
#[test]
1824+
fn test_cast_ordering_with_null_on_failure() {
1825+
use arrow::array::TimestampSecondArray;
1826+
use arrow::compute::SortOptions;
1827+
use datafusion_expr_common::sort_properties::SortProperties;
1828+
1829+
// Overflow introduces a trailing NULL even though the input satisfies
1830+
// ASC NULLS FIRST. Successful values alone are still in order.
1831+
let source = Timestamp(TimeUnit::Second, None);
1832+
let target = Timestamp(TimeUnit::Nanosecond, None);
1833+
let schema = Arc::new(Schema::new(vec![Field::new("a", source.clone(), true)]));
1834+
let batch = RecordBatch::try_new(
1835+
Arc::clone(&schema),
1836+
vec![Arc::new(TimestampSecondArray::from(vec![
1837+
None,
1838+
Some(0),
1839+
Some(i64::MAX),
1840+
]))],
1841+
)
1842+
.expect("valid input batch");
1843+
let child = ExprProperties::new_unknown()
1844+
.with_range(
1845+
Interval::make_unbounded(&source).expect("supported interval type"),
1846+
)
1847+
.with_order(SortProperties::Ordered(SortOptions::default()))
1848+
.with_strictly_order_preserving(true);
1849+
let expr = CastExpr::new(
1850+
col("a", &schema).expect("column exists"),
1851+
target.clone(),
1852+
Some(DEFAULT_SAFE_CAST_OPTIONS),
1853+
);
1854+
let actual = expr
1855+
.evaluate(&batch)
1856+
.expect("safe cast succeeds")
1857+
.into_array(batch.num_rows())
1858+
.expect("array result");
1859+
let expected = TimestampNanosecondArray::from(vec![None, Some(0), None]);
1860+
assert_eq!(actual.as_ref(), &expected);
1861+
let properties = expr
1862+
.get_properties(std::slice::from_ref(&child))
1863+
.expect("safe cast properties");
1864+
assert_eq!(properties.sort_properties, SortProperties::Unordered);
1865+
assert_eq!(properties.range.data_type(), target);
1866+
assert!(!properties.strictly_order_preserving);
1867+
1868+
let expr = CastExpr::new(col("a", &schema).expect("column exists"), target, None);
1869+
assert!(expr.evaluate(&batch).is_err());
1870+
assert_eq!(
1871+
expr.get_properties(&[child])
1872+
.expect("cast properties")
1873+
.sort_properties,
1874+
SortProperties::Ordered(SortOptions::default())
1875+
);
1876+
1877+
// A lossless cast preserves ordering even in NULL-on-failure mode.
1878+
let schema = Schema::new(vec![Field::new("a", Int32, true)]);
1879+
let child = ExprProperties::new_unknown()
1880+
.with_range(
1881+
Interval::make_unbounded(&Int32).expect("supported interval type"),
1882+
)
1883+
.with_order(SortProperties::Ordered(SortOptions::default()))
1884+
.with_strictly_order_preserving(true);
1885+
let expr = CastExpr::new(
1886+
col("a", &schema).expect("column exists"),
1887+
Int64,
1888+
Some(DEFAULT_SAFE_CAST_OPTIONS),
1889+
);
1890+
let properties = expr
1891+
.get_properties(std::slice::from_ref(&child))
1892+
.expect("safe lossless cast properties");
1893+
assert_eq!(properties.sort_properties, child.sort_properties);
1894+
assert!(properties.strictly_order_preserving);
1895+
}
1896+
16961897
#[test]
16971898
fn test_check_bigger_cast_precision_loss() {
16981899
use DataType::*;

‎datafusion/sqllogictest/test_files/cast.slt‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -90,6 +90,95 @@ select * from t0 where v0<1e100;
9090
statement ok
9191
drop table t0;
9292

93+
# A timestamp ordering cannot satisfy a time-of-day ordering across midnight.
94+
# LIMIT keeps the inner sort as a required part of the input plan.
95+
statement ok
96+
CREATE VIEW cast_midnight AS
97+
SELECT column1 AS ts
98+
FROM (VALUES
99+
(TIMESTAMP '1970-01-01 23:59:59'),
100+
(TIMESTAMP '1970-01-02 00:00:00'),
101+
(TIMESTAMP '1970-01-02 00:00:01'),
102+
(CAST(NULL AS TIMESTAMP))
103+
);
104+
105+
query PD
106+
SELECT ts, CAST(ts AS TIME) AS time_of_day
107+
FROM (SELECT ts FROM cast_midnight ORDER BY ts ASC NULLS FIRST LIMIT 4)
108+
ORDER BY time_of_day ASC NULLS FIRST;
109+
----
110+
NULL NULL
111+
1970-01-02T00:00:00 00:00:00
112+
1970-01-02T00:00:01 00:00:01
113+
1970-01-01T23:59:59 23:59:59
114+
115+
query PD
116+
SELECT ts, CAST(ts AS TIME) AS time_of_day
117+
FROM (SELECT ts FROM cast_midnight ORDER BY ts ASC NULLS LAST LIMIT 4)
118+
ORDER BY time_of_day ASC NULLS LAST;
119+
----
120+
1970-01-02T00:00:00 00:00:00
121+
1970-01-02T00:00:01 00:00:01
122+
1970-01-01T23:59:59 23:59:59
123+
NULL NULL
124+
125+
query PD
126+
SELECT ts, CAST(ts AS TIME) AS time_of_day
127+
FROM (SELECT ts FROM cast_midnight ORDER BY ts DESC NULLS FIRST LIMIT 4)
128+
ORDER BY time_of_day DESC NULLS FIRST;
129+
----
130+
NULL NULL
131+
1970-01-01T23:59:59 23:59:59
132+
1970-01-02T00:00:01 00:00:01
133+
1970-01-02T00:00:00 00:00:00
134+
135+
query PD
136+
SELECT ts, CAST(ts AS TIME) AS time_of_day
137+
FROM (SELECT ts FROM cast_midnight ORDER BY ts DESC NULLS LAST LIMIT 4)
138+
ORDER BY time_of_day DESC NULLS LAST;
139+
----
140+
1970-01-01T23:59:59 23:59:59
141+
1970-01-02T00:00:01 00:00:01
142+
1970-01-02T00:00:00 00:00:00
143+
NULL NULL
144+
145+
# A named timezone rollback can also reverse the local date.
146+
query ID
147+
SELECT arrow_cast(ts, 'Int64') AS epoch, CAST(ts AS DATE) AS d
148+
FROM (
149+
SELECT arrow_cast(column1, 'Timestamp(Second, Some("America/Goose_Bay"))') AS ts
150+
FROM (VALUES (562129259::bigint), (562129260::bigint))
151+
ORDER BY ts LIMIT 2
152+
)
153+
ORDER BY d;
154+
----
155+
562129260 1987-10-24
156+
562129259 1987-10-25
157+
158+
# Reducing timestamp precision remains order-preserving, even when values merge.
159+
statement ok
160+
SET datafusion.explain.physical_plan_only = true;
161+
162+
query TT
163+
EXPLAIN SELECT arrow_cast(ts, 'Timestamp(Second, None)') AS truncated
164+
FROM (
165+
SELECT column1 AS ts
166+
FROM (VALUES
167+
(TIMESTAMP '1970-01-01 00:00:00.001'),
168+
(TIMESTAMP '1970-01-01 00:00:00.002'),
169+
(TIMESTAMP '1970-01-01 00:00:01.000')
170+
)
171+
ORDER BY ts LIMIT 3
172+
)
173+
ORDER BY truncated;
174+
----
175+
physical_plan
176+
01)ProjectionExec: expr=[CAST(column1@0 AS Timestamp(s)) as truncated]
177+
02)--SortExec: TopK(fetch=3), expr=[column1@0 ASC NULLS LAST], preserve_partitioning=[false]
178+
03)----DataSourceExec: partitions=1, partition_sizes=[1]
179+
180+
statement ok
181+
SET datafusion.explain.physical_plan_only = false;
93182

94183
# Regression for https://github.com/apache/datafusion/issues/25523.
95184
statement ok

0 commit comments

Comments
 (0)