NGA-TRAN opened a new issue, #24644:
URL: https://github.com/apache/datafusion/issues/24644
### Is your feature request related to a problem?
Child of epic #22395 and leftover work from #23569 / #24501.
#23569 asked that both of these layouts skip a hash shuffle for
```sql
SELECT a, date_bin(INTERVAL '1 hour', timestamp) AS binned, SUM(x)
FROM t
GROUP BY a, binned
```
1. `Range([timestamp])` with splits aligned to the bin — **done in #24501**.
Extra GROUP BY keys (`a`, …) are a superset of the transformed range key, so
`range_monotonic_fn_satisfies_keys` can use `.any()`.
2. `Range` on `timestamp` **and** `a` (compound / multi-key range) — **not
done**.
#24501 fail-closes on compound range:
```rust
// datafusion/physical-expr/src/partitioning.rs
if range.ordering().len() != 1 {
return false;
}
```
A unit test asserts `Range([key, timestamp])` does **not** satisfy `GROUP BY
(key, date_bin(timestamp))` via that path.
Jayant asked on #24501 whether this expands in a follow-up:
https://github.com/apache/datafusion/pull/24501#discussion_r3831572505
### Why this is not “drop the `len() != 1` check”
`Range([key, timestamp])` with a lex split `(k2, 01:00)` is not the same as
`Range([timestamp])`.
- Partition 0: rows `< (k2, 01:00)`, including `(k1, 02:00)`
- Partition 1: rows `>= (k2, 01:00)`
The same `date_bin(timestamp)` can appear on both sides if `key` is **not**
in the GROUP BY. Example: `(k1, 02:00)` and `(k2, 02:00)` share hour `02:00`
but sit in different partitions.
So this is **unsafe**:
```rust
required.iter().any(|e| {
check_monotonic_transform(e, some_range_key) &&
disjoint_on_that_component(...)
})
```
`GROUP BY (key, date_bin(timestamp))` **is** partition-disjoint on that
layout: `key` is the lex prefix, and an aligned `date_bin` is disjoint on the
timestamp component of the split. `GROUP BY date_bin(timestamp)` alone is
**not**.
### Proposed rule
A group-key set `G` is partition-disjoint for a multi-key range only if no
group can appear on both sides of every lex split.
For each split, either:
- the full lex prefix of the range key is in `G`, and the remaining key has
a disjoint monotonic transform in `G`, or
- the first differing range key has a disjoint monotonic transform in `G`.
Compound split-point “predecessor” is not “predecessor of column `i` only.”
Adjacent partitions are defined by the full lex compare.
`RangePartitioning::project` can already rewrite `Range([key, timestamp])` →
`Range([key, time_bin])` when the projection keeps `key` and
`date_bin(timestamp)`. That only preserves **output** metadata. It does not
skip the shuffle. Satisfaction is the missing piece.
### Describe the solution you'd like
- Implement the lex-prefix + disjoint-transform check in
`range_monotonic_fn_satisfies_keys` (or a dedicated helper).
- Tests:
- `Range([key, timestamp])` + `GROUP BY (key, date_bin(aligned))` →
satisfied (no shuffle).
- `Range([key, timestamp])` + `GROUP BY date_bin(...)` only → **not**
satisfied.
- Unaligned / straddling bin (e.g. `date_trunc('day')` or `date_bin(70
minutes)` on an hour split) → not satisfied.
- Optional SLT table that **declares** compound range metadata (today’s
listing fixtures are single-key).
### Describe alternatives you've considered
- Leave the `len() != 1` guard forever. Fine if nobody declares `Range([key,
timestamp])`. #23569 still lists case (2).
- Treat any extra group key as enough. Incorrect for `GROUP BY date_bin`
only on a compound range.
### Additional context
- PR: https://github.com/apache/datafusion/pull/24501
- Epic: #22395
- Parent: #23569 (item 2)
--
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]
