lakshaydevoo-arch opened a new pull request, #26966: URL: https://github.com/apache/datafusion/pull/26966
> [!IMPORTANT] > > **Fork CI setup:** For pull requests from a fork to `main`, enable workflows in your fork's **Actions** tab before you push. > See the [fork CI setup guide](https://datafusion.apache.org/contributor-guide/#pull-requests-from-forks). ## Which issue does this PR close? - Part of #26848. This covers the nullable-key path only. As discussed with @Rich-T-kid on the issue, I'll send the non-null path as a separate PR. ## Rationale for this change When `create_hashes` hashes a dictionary array, it hashes each dictionary value once and then scatters those hashes out to the rows through the keys. If the keys have nulls, that scatter loop goes through `keys().iter()`. It builds an `Option` for every row and branches on it, so the cost depends on the total number of rows, not the number of valid keys. The `with_hashes` benchmarks show this clearly. 97% null keys cost about as much as 3%, even though there's roughly 30x less real work to do. At 50% nulls the branch can't be predicted, so that case was the slowest of all. ## What changes are included in this PR? - In the null-keys branch of `hash_dictionary_scatter`, the loop now goes over `NullBuffer::valid_indices()` instead of `keys().iter()`. Only valid key slots are visited, so: - null slots keep their existing hash, as before; - the keys stored behind null slots are never read. Arrow allows those to be any value, including out of range; - null dictionary values, the multi-column `combine_hashes` path and the existing behaviour of stopping at `hashes_buffer.len()` are all unchanged. - The non-null branch is untouched. - No new `unsafe`. The existing `get_unchecked` on the dictionary hashes is now only reached from valid key slots. - Two new `with_hashes` benchmark densities: Int32 dictionaries with 50% and 97% null keys, single and multiple columns. 0% and 3% were already covered by the existing `dictionary_utf8_int32` cases. The existing seeded null mask still produces exactly the same output. I also tried handling validity in 64-row words, with a dense loop for fully-valid words, as the issue suggests. On these benchmarks it was within ±4–9% of the simpler version, in both directions, so I left it out to keep the change small. I also checked whether key width matters (Int8 / Int32 / UInt64) and couldn't find a consistent difference, so I didn't add key-width benchmarks. ## What is the testing strategy for this PR? Added `create_hashes_for_dict_arrays_with_null_keys` in `hash_utils.rs`. It compares dictionary hashes with the hashes of the equivalent `StringArray` across: - Int8, Int32 and Int64 keys; - dictionary values with and without a null value; - lengths 0, 1, 7, 8, 9, 63, 64, 65, 127, 128 and 129, at slice offsets 0, 3, 5 and 64 (covering offsets that aren't byte-aligned); - out-of-range keys (`-1`, `values.len()`, `127`) hidden behind null slots; - one column and two columns (an `Int32` column first, so "unchanged" can be told apart from "zero"); - a `hashes_buffer` shorter than the array; - an empty values array with all keys null. The test passes against the old loop too, so behaviour is unchanged. It fails if the loop is broken or loses the truncation. Checked locally: - `cargo fmt --all -- --check` - `cargo clippy --all-targets --workspace --features avro,integration-tests,extended_tests -- -D warnings` - `cargo test -p datafusion-common`, both with and without `force_hash_collisions` - the extended test suite (`cargo test --profile ci ... --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption`), sqllogictests included. I ran it before a couple of small test-only follow-ups. I couldn't run the `--all-features` clippy pass locally because `cmake` isn't installed in my environment, so I'm relying on CI for that one. ## Benchmarks `cargo bench -p datafusion-common --bench with_hashes -- dictionary`, 3 runs on each side, median. Intel i5-12500H (WSL2). From what I measured, anything under about 6% is run-to-run noise on this machine. | benchmark | main | this PR | change | |---|---|---|---| | single, no nulls | 2.90 µs | 3.00 µs | noise (code unchanged) | | multiple, no nulls | 9.29 µs | 9.53 µs | noise (code unchanged) | | single, 3% null keys | 7.60 µs | 6.04 µs | -21% | | multiple, 3% null keys | 22.95 µs | 19.29 µs | -16% | | single, 50% null keys | 12.97 µs | 3.58 µs | -72% | | multiple, 50% null keys | 73.57 µs | 10.92 µs | -85% | | single, 97% null keys | 7.22 µs | 1.35 µs | -81% | | multiple, 97% null keys | 20.20 µs | 2.51 µs | -88% | A few notes: - `main`'s multiple / 50% number was oddly slow, about 2x the same case with Int8 keys, and I couldn't work out why. So part of that -85% is that slowdown going away, not just this change. - 3% nulls is still around 2x the no-null case. There's probably more to gain there, but I didn't want to add complexity without numbers that clearly justify it. - These are all from one x86 machine. An ARM run from the benchmark bot would be great if someone can trigger it. ## Are there any user-facing changes? No. This is an internal performance change with no API changes. -- 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]
