Repository navigation
Speed up nullable dictionary hash scattering #26848
Description
Is your feature request related to a problem or challenge?
Related to #26780.
create_hashes hashes each dictionary value once and then scatters those hashes through the keys. For nullable dictionaries, the scatter currently decodes an Option and branches for every row. Once dictionary value hashes are reused, this O(rows) work becomes a larger share of the hashing cost.
On the existing 8,192-row with_hashes benchmark with 3% null keys, nullable dictionary scatter takes about 5.9 us for one column and 17.0 us for three columns on an Apple M4 Max. The no-null cases take about 2.0 us and 6.1 us respectively.
Describe the solution you would like
Process key validity in 64-row words:
- reuse the current dense loop for all-valid words
- pipeline small groups of dictionary hash loads for mostly-valid words
- walk only set bits for sparse words
- leave null output slots unchanged, including when dictionary values themselves are null
The benchmark should cover single and composite keys, several dictionary key widths, null densities, slices, and 8/64-row boundaries.
Metadata
Metadata
Assignees
Labels
No labels
Activity
lakshaydevoo-arch commentedon Oct 29, 2026
Hi, I noticed the previous PR exploring dictionary hash scatter optimization was closed without merging.
Is the nullable dictionary scatter optimization still open for contributions? I'm interested in investigating the 64-row validity bitmap approach and benchmarking it against the current implementation.
Rich-T-kid commentedon Oct 29, 2026
@lakshaydevoo-arch feel free to pick it up. there was a 2x speed up for the null path but I was looking for improvements on the non-null path.
lakshaydevoo-arch commentedon Oct 29, 2026
Thanks for the clarification! I'll investigate both the nullable and non-null paths, review the approach from #26849, and benchmark potential improvements before submitting a PR.
lakshaydevoo-arch commentedon Oct 29, 2026
@Rich-T-kid how would i assign this issue to myself , because it may take me a day or two to investigate and figure out a fix
Rich-T-kid commentedon Oct 29, 2026
comment
takeby itself as a commentlakshaydevoo-arch commentedon Oct 29, 2026
take
lakshaydevoo-arch commentedon Oct 30, 2026
Hi @Rich-T-kid, thanks for letting me take this up!
I've started working on #26848 and have prepared benchmarks covering different null densities, dictionary key widths, and sliced arrays.
Before proceeding with the optimization, I wanted to clarify one thing: would you prefer a separate benchmark-only PR first, followed by the optimization PR, or a single PR containing both benchmarks and the optimization?
I want to keep the changes focused and aligned with the project's contribution guidelines.
Thanks!
lakshaydevoo-arch commentedon Oct 30, 2026
Before proceeding with the implementation, I wanted to clarify two points about the benchmark coverage:
Rich-T-kid commentedon Oct 30, 2026
Thank you for driving this! 🚀
lakshaydevoo-arch commentedon Oct 30, 2026
I compared Int8, Int32, and UInt64 dictionary keys across 0%, 3%, 50%, and 97% null densities, using the same 8,192-row workloads and three benchmark runs.
The results showed no consistent performance advantage for smaller key types. Most differences were within the observed benchmark variation, so I don't think additional key-width benchmarks are justified upstream.
Separately, I've implemented and tested a focused optimization for nullable dictionary hash scattering. On my x86 setup, it reduces execution time by approximately 16–21% for the main 3% null-key cases, with larger improvements at higher null densities.
Would a PR focused on this nullable-path improvement be useful, keeping non-null-path optimization separate?
Rich-T-kid commentedon Oct 30, 2026
yeah I think so. two seperate focused PRs would be better in my opinion