Skip to content

Commit 8642154

Browse files
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/Cargo.toml‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -161,3 +161,7 @@ name = "bounded_window"
161161
[[bench]]
162162
harness = false
163163
name = "window_filter"
164+
165+
[[bench]]
166+
harness = false
167+
name = "range_repartition"

0 commit comments

Comments
 (0)