Pin Range satisfaction vs advertised split-point domain
- 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 or challenge?
Child of epic #22395 and leftover from #24501 ([comment](https://github.com/apache/datafusion/pull/24501#issuecomment-5462528890)).
#24501 lets `Range([ts], [S])` **satisfy** `KeyPartitioned([f(ts)])` (Exact / Subset) when `f` is monotonic and bins do not straddle splits (`date_bin` / `date_trunc`).
`project` and satisfaction treat that layout differently:
```text
project: Range([ts], [S]) → Range([f(ts)], [f(S)]) // split rewritten
satisfaction: Range([ts], [S]) vs KeyPartitioned([f(ts)]) → Exact
// still advertises ordering ts and split S
```
After `Exact`, the plan claims the input is partitioned by `f(ts)`, but `Partitioning::Range` still reports key `ts` and split `S`. The effective boundary in required-key space is `f(S)`, not `S`.
Disjointness for aggregation in #24501 is sound. The mismatch matters for callers that compare **raw split-point values** across two `Range`s:
```rust
// datafusion/physical-plan/src/distribution_requirements.rs
// compatible_co_partitioning_layout
(Partitioning::Range(left), Partitioning::Range(right)) => {
left.split_points() == right.split_points() && ...
}
```
`co_partitioning_satisfied` uses `satisfaction(..., allow_subset = false)`, which is the `Exact` path. A join can decide two inputs are co-partitioned by comparing boundaries that were never in the same domain as the join keys. `InterleaveExec` also requires identical `Range` metadata (same split values).
**Not a live bug today.** Transforms that clear `check_monotonic_transform` with an unbounded source:
| transform | monotonic? | satisfaction | `f(split) == split`? |
|---|---|---|---|
| `date_bin` / `date_trunc`, aligned split | yes | Exact | **yes** |
| `CAST(ts AS Timestamp(Second))` | yes | Exact | **no** (different `ScalarValue` variant) |
| `CAST(ts AS Date32)` | yes | NotSatisfied | n/a |
| `ts + INTERVAL '1 hour'`, `x + 1` | no | NotSatisfied | n/a |
Two things save current code:
1. For aligned `date_bin` / `date_trunc`, `f(split) != f(split-1)` means the split **starts** its bin, so `f(split) == split`. Translated and untranslated boundaries coincide.
2. Shift-style transforms never reach this path (`Plus` is `Unordered` on unbounded ranges).
The cast row already breaks the invariant: `CAST(ts AS Timestamp(Second))` can be Exact while the advertised split stays `TimestampNanosecond`. Those variants never compare equal, so the layout check returns false. That is luck, not a designed contract.
### Describe the solution you'd like
Do one of the following (options from the #24501 review), plus a pin test:
1. **Document** the assumption on `range_monotonic_fn_satisfaction` / `monotonic_fn_keeps_partitions_disjoint`: callers may compare `RangePartitioning::split_points()` across two partitionings (`compatible_co_partitioning_layout`). Those values stay in the range-key domain, while satisfaction is granted in the transformed domain. That is consistent only because every transform that reaches this point is a flooring function: disjointness at `split` implies `f(split) == split`.
2. **Enforce** the fixed point, at the cost of dropping the narrowing-cast case:
```rust
let Some(at_split) = evaluate_expr_on_key(fn_expr, range_key, split_value) else {
return false;
};
// The split must be a fixed point of `f`. Otherwise the boundary in
// the transformed domain is `f(split)`, not `split`, and callers that
// compare raw split points are reasoning about the wrong value.
if at_split != *split_value {
return false;
}
```
#24501's tests still pass with that guard (60s `date_bin` and `date_trunc('hour')` splits are fixed points).
Either way, add a unit test for `CAST(ts AS Timestamp(Second))` so a future transform cannot change this silently.
### Describe alternatives you've considered
- Leave it undocumented. Fine for #24501's `date_bin` / `date_trunc` aggregation, but the next monotonic transform (or a join/union that reads split values) can break the layout check without a failing test.
- Always rewrite advertised splits through `f` in satisfaction, like `project` does. That would change `Range` identity for consumers that still see the source key.
### Additional context
- Review: https://github.com/apache/datafusion/pull/24501#issuecomment-5462528890 (@jayzhan211; non-blocking)
- PR: #24501
- Sibling leftover: #24644 (multi-key Range satisfaction — different issue)
- Epic: #22395
- Parent: #23569
Contributor guide
Research direction
Read datafusion/physical-plan/src/distribution_requirements.rs, especially compatible_co_partitioning_layout and co_partitioning_satisfied, then trace range_monotonic_fn_satisfaction and monotonic_fn_keeps_partitions_disjoint from PR #24501. Decide whether the contract should be documented or fixed with the fixed-point check, and add the requested CAST(ts AS Timestamp(Second)) unit test; done means the invariant is explicit and tested.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases, distributed-systems
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100