mbutrovich opened a new pull request, #9683: URL: https://github.com/apache/arrow-rs/pull/9683
# Which issue does this PR close? N/A. # Rationale for this change The existing `lexsort_to_indices` uses comparison sort on columnar arrays, which is O(n log n × comparison_cost) where comparison cost scales with the number of columns. The Arrow row format (`RowConverter`) produces memcmp-comparable byte sequences, making it a natural fit for radix sort — O(n × key_width) — which can overcome the encoding overhead by eliminating per-comparison column traversal. Inspired by [DuckDB's sorting redesign](https://duckdb.org/2025/09/24/sorting-again), which uses MSD radix sort on normalized key prefixes with a comparison sort fallback, this PR adds an `radix_sort_to_indices` kernel that operates directly on row-encoded keys. Like DuckDB, we limit radix depth to 8 bytes before falling back to comparison sort, balancing radix efficiency against diminishing returns on deep recursion. # What changes are included in this PR? * **`arrow-row/src/radix.rs`** (new): MSD radix sort on `Rows` with: * Ping-pong buffers to eliminate per-level memcpy * Byte extraction buffer for single-pass indirection through Rows * 256-bucket histogram + out-of-place scatter per byte position * Comparison sort fallback for small buckets (≤32 elements) or after 8 bytes of radix depth * Fallback compares from `byte_pos` onward via `Row::data_from()`, skipping the shared prefix * **`arrow-row/src/lib.rs`**: Exposes `pub mod radix`, adds `Row::byte_from()` and `Row::data_from()` APIs * **`arrow/benches/lexsort.rs`**: Adds `lexsort_radix` benchmark variant alongside existing `lexsort_to_indices` and `lexsort_rows` ## Benchmark results All three variants include the full pipeline (encoding + sort) so the comparison against `lexsort_to_indices` (which doesn't encode) is apples-to-apples. | Schema, N | lexsort_to_indices | lexsort_rows | lexsort_radix | |---|---|---|---| | [i32, i32_opt], 4096 | 88.156 µs | 117.32 µs | **76.358 µs** | | [i32, i32_opt], 32768 | 857.82 µs | 1.2250 ms | **331.26 µs** | | [i32, str_opt(16)], 32768 | 861.89 µs | 1.8851 ms | **488.62 µs** | | [str_opt(16), str(16)], 32768 | 2.4453 ms | 1.6565 ms | **972.92 µs** | | [3x str], 32768 | 2.4723 ms | 1.9196 ms | **1.1955 ms** | | [5x str], 32768 | 2.4513 ms | 2.2403 ms | **1.5101 ms** | | [i32_opt, dict], 32768 | 1.1853 ms | 1.3607 ms | **696.75 µs** | | [dict, dict], 32768 | **501.86 µs** | 726.90 µs | 985.69 µs | | [3x dict, str(16)], 32768 | 4.1119 ms | 2.0401 ms | **1.5996 ms** | | [3x dict, str_opt(50)], 32768 | 4.2241 ms | 2.1783 ms | **1.7227 ms** | | [i32_opt, i32_list], 32768 | 1.4701 ms | 2.9004 ms | **1.4326 ms** | | [i32, i32_list, str(16)], 32768 | 874.37 µs | 2.2616 ms | **1.1727 ms** | Radix sort is the fastest in the majority of cases. The main exception is pure low-cardinality dictionary columns where `lexsort_to_indices` avoids encoding overhead entirely. The module documentation provides guidance on when to use each approach. # Are these changes tested? 17 tests including: * Deterministic tests for integers, strings, multi-column, nulls, all-equal, empty, single-element * All 4 sort option combinations (ascending/descending × nulls_first) * Float64 with NaN/Infinity, booleans * Threshold boundary tests (sizes 1–1000 around the fallback threshold) * Fuzz test: 100 iterations × 1–4 random columns × random types × random sort options × 5–500 rows * Cross-validation: verifies radix output matches comparison sort on the same `Rows` # Are there any user-facing changes? New public APIs: * `arrow_row::radix::radix_sort_to_indices(&Rows) -> Vec<u32>` — sort with default parameters * `arrow_row::radix::radix_sort_to_indices_with(&Rows, max_depth, fallback_threshold) -> Vec<u32>` — sort with tunable radix depth and fallback threshold * `Row::byte_from(offset) -> u8` — single byte access at offset * `Row::data_from(offset) -> &[u8]` — suffix slice from offset -- 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]
