Abhisheklearn12 opened a new pull request, #25793: URL: https://github.com/apache/datafusion/pull/25793
## Which issue does this PR close? - Closes #20211. ## Rationale for this change Hashing a union column (in a `GROUP BY`, a hash join or hash repartitioning) did a lot of avoidable work: - Every row went through a `HashMap`, either to look up its child's hashes or to group rows by type. - Sparse unions with 1 or 2 types hashed every child in full. With 3 or more types, every selected value was copied with `take`. - `UnionArray::slice` doesn't slice dense children, so a sliced dense union hashed its children in full. This is the same problem #19500 and #20179 fixed for lists and maps. ## What changes are included in this PR? Sparse unions: - Rows are grouped by type id once, with an O(n) counting sort. - If every row picks the same child, that child is hashed directly. - Utf8, LargeUtf8, Binary and LargeBinary children that own at least 1/32 of the rows are hashed without copying their value buffers, by nulling out the other rows through `nullif`. This is the null buffer idea @Jefffrey raised in https://github.com/apache/datafusion/pull/20179#discussion_r2777750677. - All other children go through `take`. Masking was slower for fixed-width values, except about 10% faster for primitives with nulls, which wasn't worth a special case. It was also slower for children that own only a few rows, because building the mask costs O(len) per child. Masking still won at 1/32 of the rows and lost at 1/64 for short, medium and long strings alike, hence the cutoff. - The special case for 1 or 2 types is gone. Dense unions: - A lookup table indexed by type id replaces the per-row `HashMap`. - When the children's total length exceeds the union's, only the span their offsets reference gets hashed. Hash values are unchanged. Not done: a `create_hashes` variant that hashes by index list instead of `take` (the other idea from the issue). It would avoid the `take` copy, but I haven't built or measured it, so I left it out of this PR. Benchmarks: `with_hashes` gains `sparse_union (2 types)`, `sparse_union (utf8)` and `dense_union_sliced`. `sparse_union_array` now builds its array through a small `sparse_union_of` helper, and the data it produces is identical to before. ## What is the testing strategy for this PR? - New `create_hashes_for_union_arrays_match_selected_values` test. It checks that each row of a union used as the second column contributes the hash of its selected child value on its own, through both `create_hashes` and `create_hashes_with_hasher`. It covers: - sparse and sliced sparse unions, including a slice whose rows all select one child - a string child routed through `take` - dense and sliced dense unions - non-contiguous type ids - The existing union tests pass unchanged. - During development I compared the new code against the previous implementation on 12,000 random unions. They used 28 child types covering every category the hasher handles: primitives, decimals, temporal types, strings, binary, views, dictionaries, nested types, Null, run-end encoded and nested unions. Each union was sliced or unsliced, and was hashed alone and as the first and second column, with the fast and quality hash states and a custom `BuildHasher`. Every hash matched. That test isn't committed because it embeds the old code. Benchmarks (`cargo bench -p datafusion-common --bench with_hashes -- union`): medians averaged over two interleaved runs, one pinned core, i7-11700F. | benchmark | main | PR | speedup | |---|---|---|---| | sparse_union: single, no nulls | 93.3 µs | 27.7 µs | 3.37x | | sparse_union: multiple, no nulls | 268.2 µs | 79.8 µs | 3.36x | | sparse_union (2 types): single, no nulls | 81.5 µs | 28.8 µs | 2.83x | | sparse_union (2 types): multiple, no nulls | 248.3 µs | 87.2 µs | 2.85x | | sparse_union (utf8): single, no nulls | 176.6 µs | 61.3 µs | 2.88x | | sparse_union (utf8): multiple, no nulls | 536.4 µs | 189.1 µs | 2.84x | | sparse_union_sliced: 1/10 of 81920 rows | 95.9 µs | 27.6 µs | 3.47x | | sparse_union_sliced: 1/5 of 40960 rows | 93.2 µs | 26.8 µs | 3.47x | | sparse_union_sliced: 1/2 of 16384 rows | 92.6 µs | 28.0 µs | 3.30x | | dense_union: single, no nulls | 81.0 µs | 14.1 µs | 5.73x | | dense_union: multiple, no nulls | 244.9 µs | 40.1 µs | 6.11x | | dense_union_sliced: 1/10 of 81920 rows | 136.9 µs | 22.6 µs | 6.07x | | dense_union_sliced: 1/5 of 40960 rows | 101.0 µs | 22.0 µs | 4.58x | | dense_union_sliced: 1/2 of 16384 rows | 88.0 µs | 22.9 µs | 3.84x | I also measured 25 more cases: 1 to 127 types; int64 with and without nulls; short, medium and long strings; string view, bool, fixed size binary, dictionary, struct, list, and mixed children. The PR was faster than main in every one, from 1.3x to 7.5x. ## Are there any user-facing changes? No API or result changes. Queries that hash union columns can run faster. -- 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]
