Support date_bin / date_trunc satisfaction for multi-key Range partitioning
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### 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)
Contributor guide
Assessment
This issue has not been assessed yet.