gene-bordegaray opened a new issue, #25569:
URL: https://github.com/apache/datafusion/issues/25569
Epic: #25421
## Is your feature request related to a problem or challenge?
Currently, `RangePartitioning`'s first and last partitions always extend to
infinity:
```text
ordering = [x ASC]
split_points = [10, 20, 30]
P0: (-inf, 10)
P1: [10, 20)
P2: [20, 30)
P3: [30, +inf)
```
This correctly describes a range layout that may contain any value in the
key space. It cannot represent an output whose keys are known to lie within
finite outer bounds.
This distinction matters when a table provider or optimizer rule has proved
a finite output domain. DataFusion currently discards that proof and replaces
it with a weaker, unbounded property.
For example, #25437 proposes statically pruning range partitions. Consider
the following layout:
```text
P0: (-inf, 10)
P1: [10, 20)
P2: [20, 30)
P3: [30, 40)
P4: [40, 50)
P5: [50, +inf)
```
The predicate `x >= 20 AND x < 40` keep only `P2` and `P3`:
```text
P0: (-inf, 10) -> pruned
P1: [10, 20) -> pruned
P2: [20, 30) -> keep
P3: [30, 40) -> keep
P4: [40, 50) -> pruned
P5: [50, +inf) -> pruned
```
When partition-index stability is required, #25437 can preserve the original
layout by replacing pruned streams with `EmptyExec`. When alignment is not
required, it can compact and renumber the two surviving streams as local
partitions 0 and 1.
The current API can describe that compacted output only as:
```text
split_points = [30]
local P0: (-inf, 30)
local P1: [30, +inf)
```
This property is safe, but it is weaker than what the optimizer proved. The
output is bounded by `[20, 40)`, but `RangePartitioning` cannot retain that
fact. With explicit outer bounds, it could advertise:
```text
domain = [20, 40)
split_points = [30]
local P0: [20, 30)
local P1: [30, 40)
```
## Why retain this information?
An unbounded domain forces downstream optimizer rules to assume that
endpoint partitions may contain values outside the actual output domain. This
can prevent them from proving useful range relationships.
Continuing the #25437 example, suppose a downstream operator requires the
original six-partition layout. With the current unbounded property, a
range-layout comparison concludes:
```text
local P0: (-inf, 30) -> may overlap original P0, P1, or P2
local P1: [30, +inf) -> may overlap original P3, P4, or P5
```
With explicit bounds, the relationship is exact:
```text
local P0: [20, 30) -> original P2: [20, 30)
local P1: [30, 40) -> original P3: [30, 40)
```
We are going to see more downstream consumer such as #25483 that could use
that proof to connect each input only to its actual destination. When an input
has one destination, execution can forward whole batches instead of evaluating
the range key and routing every row.
This issue only is only the introduction of the domain. It is just meant to
make this informatioin available. It is things like #25437 which removes empty
streams, and consumers such as #25483 may use the new domain to add
optimizations.
## Desired behavior
`RangePartitioning` should optionally describe the outer bounds of its
output key domain:
```text
ordering = [x ASC]
domain = [20, 40)
split_points = [30]
P0: [20, 30)
P1: [30, 40)
```
Existing construction should preserve the current semantics by defaulting
both bounds to unbounded.
## Proposed solution
Add outer bounds to `RangePartitioning`, conceptually:
```rust
struct RangePartitioning {
ordering: LexOrdering,
domain: RangeDomain,
split_points: Vec<SplitPoint>,
}
struct RangeDomain {
start: Bound<SplitPoint>,
end: Bound<SplitPoint>,
}
```
`start` and `end` are interpreted according to the declared lexicographic
ordering, including sort direction and null ordering.
Existing constructors should create an unbounded domain. A new constructor
should accept explicit bounds and validate the bounds.
Projections and other property-preserving operators should retain the
domain. A rewrite may narrow it only when it proves the new bounds and updates
the physical streams and split points consistently. Otherwise fall back to an
unbounded domain or another appropriate partitioning property.
--
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]
