stuhood opened a new pull request, #24598: URL: https://github.com/apache/datafusion/pull/24598
## Which issue does this PR close? - Closes #24597. - Related to [EPIC: Implement Range Partitioning #22395](https://github.com/apache/datafusion/issues/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 creates allocates per row, and has dynamic dispatch overhead, makin g range re-partitioning 15x–30x slower than hash re-partitioning on standard integer keys. This PR adds a vectorized, zero-allocation implementation, bringing range re-partitioning to near-parity with hash repartitioning (10x–22x 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 vectorized path using Arrow's `RowConverter` for strings, decimals, dictionary arrays, and composite keys. - Updates `BatchPartitioner` and `RangeExpr` to delegate partition routing to `RangeRouter`. - Adds a Criterion suite. ### Benchmark Comparison (8,192 Rows) | Workload | Partitions | `main` | `branch` | Speedup | | :--- | :--- | :--- | :--- | :--- | | `range_expr_routing_i64` (Isolated Primitive Routing) | 8 | 237.3 µs | 13.8 µs | 17.2x | | | 16 | 286.7 µs | 15.8 µs | 18.1x | | | 64 | 415.2 µs | 23.5 µs | 17.7x | | | 512 | 854.6 µs | 38.9 µs | 22.0x | | `range_repartition_i64_uniform` (End-to-End `BatchPartitioner`) | 8 | 264.8 µs | 24.5 µs | 10.8x | | | 16 | 313.5 µs | 27.0 µs | 11.6x | | | 64 | 462.1 µs | 40.3 µs | 11.5x | | | 512 | 872.0 µs | 69.8 µs | 12.5x | | `range_repartition_utf8_uniform` (String Keys via `RowConverter`) | 8 | 464.7 µs | 207.1 µs | 2.2x | | | 64 | 958.4 µs | 340.5 µs | 2.8x | | `range_repartition_composite_i64` (Composite `(i64, i64)` Keys) | 8 | 344.2 µs | 143.5 µs | 2.4x | | | 64 | 545.9 µs | 288.3 µs | 1.9x | ## Are these changes tested? Yes: - New tests in `datafusion/physical-plan/src/repartition/range.rs` covering ASC/DESC sort options, `nulls_first` / `nulls_last`, floats (with total order comparison), strings, and composite keys. - Criterion suite in `datafusion/physical-plan/benches/range_repartition.rs`. ## Are there any user-facing changes? No. -- 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]
