xudong963 opened a new pull request, #27547:
URL: https://github.com/apache/datafusion/pull/27547
## Which issue does this PR close?
- Part of #25464.
## Rationale for this change
#25409 stopped `date_trunc` from propagating its input ordering for every
timezone-aware timestamp, because truncating in local time can go backwards
across a timezone transition (#25353).
That is broader than it needs to be. For `minute` and finer granularities
`date_trunc` never consults the timezone: it rounds the epoch value down to a
multiple of the granularity (`truncates_in_input_unit`), and rounding down
cannot reorder values. So since 56, sorting or grouping timezone-aware
timestamps by `date_trunc('minute', ts)` or `date_trunc('second', ts)` over
input ordered on `ts` adds a sort, or keeps every group in the hash table until
the input ends, where 55 streamed. Time-bucketed aggregation over sorted,
timezone-aware data is the common shape for this.
#25464 asks to restore the safe timezone-aware cases and notes that
particular granularities can be evaluated separately. #25635 covers one axis
(UTC and fixed offsets, every granularity). This PR covers the other (every
timezone, `minute` and finer). They are independent; both change the same
`match` arm, so whichever lands second needs a one-line merge.
## What changes are included in this PR?
`DateTruncFunc::output_ordering` now propagates the input ordering for a
timezone-aware timestamp when the precision is a known constant and
`truncates_in_input_unit` holds for it.
It uses the predicate that selects the arithmetic kernel, so ordering is
claimed exactly when that kernel runs. If a granularity is ever moved to the
local-time path (for example to make `minute` exact for historical sub-minute
offsets, which the kernel ignores today), the ordering claim goes away with it.
Hour and coarser granularities in a timezone, and precisions whose value is
not known, stay unordered.
## What is the testing strategy for this PR?
- `timestamps.slt` extends the existing `America/Goose_Bay` regression from
#25353. Across the same transition, `date_trunc('minute', ..)` returns
correctly ordered rows without a `SortExec`, and `GROUP BY` runs with
`group_clustering_mode=Full`. The existing `hour` case keeps its sort. The two
new `EXPLAIN` cases fail without the change.
- A unit test covers what is impractical to reach from SQL: each granularity
for each time unit, the literal's string type and case, and a constant
precision whose value is unknown.
As a check outside the test suite, I ran the kernel over every UTC-offset
transition between 1800 and 2037 of all 597 zones in the tz database, with a
few hundred instants around each one. `minute` and finer never reversed. `hour`
reversed in 43 zones and `day` in 21.
### Benchmarks
20M rows, one per second, in a `Timestamp(ns, "America/New_York")` column,
one Parquet file declared `WITH ORDER (ts ASC)`. `datafusion-cli` release build
on an Apple M4 Pro (12 cores), median of 5 runs, wall time and peak RSS of the
whole process.
| Query | `main` | This PR |
| --- | --- | --- |
| `SELECT date_trunc('minute', ts) AS d FROM t ORDER BY d` (`EXPLAIN
ANALYZE`) | 0.35 s, 333 MiB | 0.24 s, 106 MiB |
| `GROUP BY` minute, `ORDER BY m LIMIT 1` | 0.06 s, 144 MiB | 0.08 s, 119
MiB |
| `GROUP BY` minute (333k groups) | 0.06 s, 142 MiB | 0.24 s, 131 MiB |
| `GROUP BY` second (20M groups) | 0.17 s, 1172 MiB | 0.51 s, 151 MiB |
| `GROUP BY` minute, `target_partitions = 1` | 0.24 s, 66 MiB | 0.23 s, 36
MiB |
| `GROUP BY` second, `target_partitions = 1` | 0.80 s, 1454 MiB | 0.46 s, 37
MiB |
| `GROUP BY` hour (plan unchanged) | 0.37 s, 120 MiB | 0.36 s, 119 MiB |
The full `GROUP BY` queries are the part to look at. Memory no longer grows
with the number of groups, and on one partition the clustered aggregation is as
fast or faster. With 12 partitions it is slower in wall time, because the
order-preserving plan drains the sorted file ranges one after another and so
does not scale with cores the way the hash aggregation does. This is the effect
described in
https://github.com/apache/datafusion/pull/25635#discussion_r4176172834.
This is not a new trade-off: it is the plan `main` already picks for the
same queries over a timezone-less timestamp column, with the same numbers (0.24
s, 126 MiB for minute and 0.52 s, 151 MiB for second). The PR makes the
timezone-aware case consistent with it. Whether the planner should prefer the
clustered plan when it costs parallelism is a separate question, and not one
this PR changes.
<details>
<summary>Benchmark setup</summary>
```sql
COPY (
SELECT arrow_cast(
arrow_cast(arrow_cast(value * 1000000000, 'Timestamp(Nanosecond,
None)'),
'Timestamp(Nanosecond, Some("UTC"))'),
'Timestamp(Nanosecond, Some("America/New_York"))') AS ts
FROM generate_series(0, 19999999) ORDER BY value
) TO 'ny.parquet';
CREATE EXTERNAL TABLE t STORED AS PARQUET LOCATION 'ny.parquet' WITH ORDER
(ts ASC);
EXPLAIN ANALYZE SELECT date_trunc('minute', ts) AS d FROM t ORDER BY d;
SELECT date_trunc('minute', ts) AS m, count(*) FROM t GROUP BY m ORDER BY m
LIMIT 1;
SELECT count(*), max(c) FROM (SELECT date_trunc('minute', ts) AS m, count(*)
AS c FROM t GROUP BY m);
SELECT count(*), max(c) FROM (SELECT date_trunc('second', ts) AS s, count(*)
AS c FROM t GROUP BY s);
SELECT count(*), max(c) FROM (SELECT date_trunc('hour', ts) AS h, count(*)
AS c FROM t GROUP BY h);
```
</details>
## Are there any user-facing changes?
Queries that sort or group timezone-aware timestamps by `date_trunc` at
`minute` or finer granularity, over input ordered on the timestamp, no longer
add a sort and aggregate with clustered aggregation. Results are unchanged. No
API changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]