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]

Reply via email to