apache / apache/datafusion

Pin Range satisfaction vs advertised split-point domain

Open
#24,947 0 comments 1 reaction 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.