vb-dbrks opened a new pull request, #59295: URL: https://github.com/apache/spark/pull/59295
### What changes were proposed in this pull request? [SPARK-60085](https://issues.apache.org/jira/browse/SPARK-60085): mix Float/Double key bits before choosing a bucket for generated lookups into constant maps. Use Spark's existing `Murmur3_x86_32.hashInt` for canonical Float bits and `hashLong` for all 64 canonical Double bits, with matching calculations in table construction and generated lookup. Normalize both zero signs first to preserve SQL equality. Other key types, lookup strategy selection and the interpreted Java index are unchanged. **Draft for review of the hash choice.** This implements the measured Murmur3 reference candidate. It improves clustered-key workloads but has a repeatable cost for some already-distributed maps. Evaluating a cheaper full-bit mixer remains open before finalizing the implementation. ### Why are the changes needed? For a 1,000-entry map, Spark allocates 2,048 buckets and selects the initial bucket using the hash's lowest 11 bits. Every Float/Double key from `0.0` through `999.0` starts in bucket zero with the current hashes. Linear probing creates one long cluster, requiring **500.5 bucket checks on average** for uniformly distributed successful lookups. The candidate reduces this structural count to **1.442 for Float and 1.418 for Double**. The affected path is selected under the default threshold and code-generation settings. TargetEncoder uses constant Double-key maps for its category mappings. Hashing all Double bits also avoids retaining collisions between distinct doubles with the same old XOR-folded hash. The JIRA includes a short SQL reproduction and independently checked checksum. [SPARK-55959](https://issues.apache.org/jira/browse/SPARK-55959) introduced the general hash optimization; this PR addresses its floating-point distribution. The adjacent null-key correction in #58875 and TargetEncoder's repeated lookup are separate work. ### Does this PR introduce _any_ user-facing change? Yes: clustered-key queries improve, while some miss-heavy workloads become slower. Lookup results are preserved. No public API, configuration, dependency or persistence-format changes. The affected implementation is present in Spark 4.2.0 release source. Runtime validation and measurements used master `0c14861e323174452d42ffb7947d1c1158c39286` (`5.0.0-SNAPSHOT`); no 4.2.0 runtime benchmark is claimed. Local repeated-query results compare the candidate with unchanged baseline code: | Workload | Rows | Baseline ms | Candidate ms | Change across three paired JVM rounds | |---|---:|---:|---:|---| | Float map, 1,000 dense keys, successful lookups | 1,000,000 | 789.38 | 24.81 | 23.05–38.25× faster | | Double map, 1,000 dense keys, successful lookups | 1,000,000 | 617.50 | 23.61 | 24.47–27.41× faster | | Fitted TargetEncoder, 1,000 categories, successful lookups | 100,000 | 127.32 | 12.01 | 9.69–13.29× faster | | Random fractional Double map, 10,000 keys; all misses using −1 through −10,000 | 1,000,000 | 29.62 | 38.75 | 25.2–30.8% slower | Times are medians of three per-JVM medians; change ranges compare corresponding rounds. These are constructed workloads on one Apple M3 Pro with JDK 21, a 4 GiB heap and one local worker. They do not establish typical production speedups. The missing-key cost is about 8–10 ms per million rows in this experiment. Average probes do not increase (1.5332 → 1.5294), but the candidate adds hash arithmetic and touches a wider set of buckets; their individual timing contributions were not profiled. Float random-map misses also regress, and some random/sparse initialization cases add roughly 29–53 microseconds. These costs remain part of the design review. ### How was this patch tested? - Three new structural regressions fail on fresh baseline code and pass with the candidate: dense Float keys, dense Double keys, and distinct Double keys sharing the old folded hash. They inspect actual bucket clusters with no timing assertion or prescribed hash layout. - Two additional tests exercise `GetMapValue` and `ElementAt`, generated hash/linear paths, dense keys, signed zero, NaN payloads, infinities, subnormals, fractional keys, null values, missing keys and null inputs. - All **97 tests** in the two relevant expression suites and all **four style checks** passed locally: ```sh ./build/sbt "catalyst/testOnly org.apache.spark.sql.catalyst.expressions.ComplexTypeSuite org.apache.spark.sql.catalyst.expressions.CollectionExpressionsSuite" ./build/sbt "catalyst/scalastyle" "catalyst/Test/scalastyle" "sql/Test/scalastyle" "mllib/Test/scalastyle" ``` The committed source/test patch is identical to the validated patch. `git diff --check` also passed. Full repository tests were not run locally; fork CI is reported separately by GitHub Actions. [Benchmark harness, raw samples and reproduction instructions](https://github.com/vb-dbrks/spark/tree/e5325d7fbb7e991aad62b49b7b05e9c71079fe3e) provide the custom sources needed to reproduce the measurements. These are local measurements, not GitHub benchmark-workflow results. Each variant used three fresh JVMs, five measured samples per case, warmup of at least two seconds for TargetEncoder and five seconds for the million-row SQL controls, with variant and case order reversed in round two. Timed actions consume independently checked aggregates; input preparation and TargetEncoder fitting are excluded. Loaded Catalyst artifacts, plans, types and generated lookup paths were verified. The table uses cached Range inputs. Earlier SQL runs used local-collection inputs with partition-serialization overhead; those historical timings are not the SQL results quoted here. The known interpreted signed-zero discrepancy is separate; this change preserves generated signed-zero equality. No Databricks validation is claimed. ### Was this patch authored or co-authored using generative AI tooling? Generated-by: OpenAI Codex (tool version unavailable). Codex assisted with investigation, implementation, regression tests, benchmark harnesses, validation and this description. The recorded tests and measurements were executed locally. This is my original contribution, with the AI assistance disclosed above, and I license it to the project under the Apache License, Version 2.0. -- 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]
