Repository navigation
Commit 8642154
authored
Range partition on primitives. (apache#24598)
## Which issue does this PR close?
- Closes apache#24597.
- Related to apache#22395.
## Rationale for this change
In query plans that use range re-partitioning (such as matching the
range partitioning of underlying base data, or evaluating dynamic range
filters in hash joins), range re-partitioning can represent a
significant fraction of total query execution time.
As detailed in the issue, the existing implementation in
[`RepartitionExec`](https://github.com/apache/datafusion/blob/6fe001d4baf5c6089d24b5634a23b1345797fb14/datafusion/physical-plan/src/repartition/mod.rs#L100-L150)
/
[`BatchPartitioner`](https://github.com/apache/datafusion/blob/6fe001d4baf5c6089d24b5634a23b1345797fb14/datafusion/physical-plan/src/repartition/mod.rs#L623-L640)
and
[`RangeExpr`](https://github.com/apache/datafusion/blob/6fe001d4baf5c6089d24b5634a23b1345797fb14/datafusion/physical-plan/src/joins/hash_join/shared_bounds.rs#L180-L240)
assigns rows to partitions on a row-by-row basis using
[`extract_row_at_idx_to_buf`](https://github.com/apache/datafusion/blob/6fe001d4baf5c6089d24b5634a23b1345797fb14/datafusion-common/src/utils/mod.rs)
and dynamic
[`ScalarValue`](https://github.com/apache/datafusion/blob/6fe001d4baf5c6089d24b5634a23b1345797fb14/datafusion-common/src/scalar/mod.rs)
comparisons. This allocates per row and has dynamic dispatch overhead,
making range re-partitioning 15x–30x slower than hash re-partitioning on
standard integer keys.
This PR adds a zero-allocation, vectorizable implementation, achieving
10x–16x speedup on primitive numeric keys and 2x–3x speedup on string
and composite keys.
## What changes are included in this PR?
- Adds an internal `RangeRouter` with specialized routing paths:
- A zero-allocation path for single primitive numeric, temporal, and
float columns that binary searches directly over Arrow buffer slices.
- A (more) vectorizable path using Arrow's `RowConverter` storing flat
`Rows` buffers for strings, decimals, dictionary arrays, and composite
keys.
- Updates `RepartitionExec` to construct and share an `Arc<RangeRouter>`
across input partitions, avoiding redundant split-point encoding.
- Updates `BatchPartitioner` and `RangeExpr` to delegate partition
routing to `RangeRouter`.
- Adds `BatchPartitioner::try_new_range_partitioner` and deprecates
`BatchPartitioner::new_range_partitioner`.
- Adds a Criterion suite.
### Benchmark Results (vs `main` baseline)
| Benchmark | Partitions | Baseline (`main`) | This PR | Speedup |
| :--- | :--- | :--- | :--- | :--- |
| **`range_repartition_i64_uniform`** | 8 | 275.3 µs (29.8 Melem/s) |
23.4 µs (349.5 Melem/s) | **11.7x** |
| | 64 | 459.8 µs (17.8 Melem/s) | 40.9 µs (200.4 Melem/s) | **11.2x** |
| | 512 | 1,194.6 µs (6.86 Melem/s) | 89.9 µs (91.2 Melem/s) | **12.2x**
|
| **`range_repartition_i64_sequential`** | 8 | 291.8 µs (28.1 Melem/s) |
23.2 µs (353.6 Melem/s) | **12.6x** |
| | 64 | 478.6 µs (17.1 Melem/s) | 38.5 µs (212.9 Melem/s) | **12.4x** |
| | 512 | 989.9 µs (8.28 Melem/s) | 83.9 µs (97.6 Melem/s) | **11.8x** |
| **`range_repartition_utf8_uniform`** | 8 | 543.5 µs (15.1 Melem/s) |
184.2 µs (44.5 Melem/s) | **3.0x** |
| | 64 | 964.7 µs (8.49 Melem/s) | 330.5 µs (24.8 Melem/s) | **2.9x** |
| | 512 | 1,333.2 µs (6.14 Melem/s) | 551.7 µs (14.8 Melem/s) | **2.4x**
|
| **`range_repartition_composite_i64`** | 8 | 344.2 µs (23.8 Melem/s) |
114.3 µs (71.7 Melem/s) | **3.0x** |
| | 64 | 516.9 µs (15.8 Melem/s) | 249.7 µs (32.8 Melem/s) | **2.1x** |
| | 512 | 985.3 µs (8.31 Melem/s) | 473.6 µs (17.3 Melem/s) | **2.1x** |
## Are these changes tested?
Added unit and integration tests.
## Are there any user-facing changes?
- Added `BatchPartitioner::try_new_range_partitioner(&RangePartitioning,
&Schema, Time) -> Result<Self>`, which takes the input `&Schema` to
infer column data types and coerce split points.
- Deprecated `BatchPartitioner::new_range_partitioner` in favor of
`try_new_range_partitioner`.
- **`RangeExpr`**:
- Added `RangeExpr::try_new_with_schema(Vec<PhysicalExprRef>,
&RangePartitioning, &Schema) -> Result<Self>`, ensuring routing matches
key column data types (precision, scale, timezone).
- Deprecated `RangeExpr::try_new(Vec<PhysicalExprRef>,
&RangePartitioning)` in favor of `try_new_with_schema`.1 parent 3266eaa commit 8642154
6 files changed
Lines changed: 1857 additions & 118 deletions
File tree
- datafusion
- physical-plan
- benches
- src
- joins/hash_join
- repartition
- proto/tests/cases/plans
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
161 | 161 | | |
162 | 162 | | |
163 | 163 | | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
0 commit comments