sunchao opened a new pull request, #25434: URL: https://github.com/apache/datafusion/pull/25434
## Which issue does this PR close? Closes #25392. ## Rationale for this change A join with many build rows but few keys can run out of memory reserving hash buckets even though its row data and useful lookup index fit. The lookup table stores one entry per distinct hash; a separate row-index chain already preserves every duplicate needed for join multiplicity. For example, 65,536 rows joined by two state codes and NULL can fit within a 2 MiB memory pool, while the old bucket reservation alone exceeds that limit. ## What changes are included in this PR? Start the generic build lookup table with a bounded chunk of capacity and grow it as needed. On growth, try full row-count preallocation once to keep construction fast for mostly unique keys; if admission fails, grow from the observed hashes and next chunk. When the replacement fits but overlapping tables do not, release the partial index and rebuild from the buffered input, preserving duplicate chains and row ordering. Charge the row-index chain, hash scratch, and overlapping table allocations to the memory pool, and include temporary allocations in the build-memory peak. Flat column keys use bounded hash scratch; dictionary, nested, and computed keys retain whole-batch evaluation. The perfect-hash `ArrayMap` and auxiliary null-aware scope maps keep their existing paths. No spilling or final table compaction is added. Moderate-cardinality builds can still reach full preallocation, and accounting for previously uncharged allocations can increase reservations for mostly unique builds. Build-payload concatenation accounting is outside this change. ## What is the testing strategy for this PR? Six new regressions in `joins::hash_join::compact_hash_map::tests` cover exact duplicate/NULL results under a 2 MiB limit, FIFO chains across uneven batches, dictionary and computed expressions, constrained growth/rebuild accounting, failed admission cleanup, both index widths, and empty/all-NULL keys. Five 1M-row Criterion cases cover duplicate-heavy, mostly unique, unique, and opposing key-order distributions. Local validation on Rust 1.98.1: - 2,262 physical-plan tests and 2,479 core/CLI tests and doctests passed (57 doctests ignored). - All 521 SQL logic files completed successfully. - The new 2 MiB regression fails on unchanged base `62f039f0d` with `ResourcesExhausted` and passes with this change. - `cargo fmt --all` and strict all-target/all-feature Clippy passed. - The required extended workspace suite passed 11,919 tests (8 ignored), including all 521 SQL logic files. - All six new tests also passed with forced hash collisions. - The full `./dev/rust_lint.sh` suite passed, including documentation compilation with warnings denied. The five benchmark cases passed in Criterion smoke mode on both revisions. For the 1M-row / 64-key case, reported `build_mem_used` fell from **45.45 MiB to 15.59 MiB (65.7%)**. This is reservation accounting, not RSS; it does not establish a timing improvement. More complete accounting raises the reported peak for mostly unique builds. Local registry availability required building from main immediately before the sqlparser 0.63 update and using compatible patch versions of four dependencies (`async-compression` 0.4.44, `compression-codecs` 0.4.40, `toml` 1.1.5, `uuid` 1.26.0). These lockfile adjustments are not included in the PR. Upstream CI still needs to validate the published lockfile and merge with current main. ## Are there any user-facing changes? Low-cardinality generic hash joins can complete with smaller memory pools while preserving results and row multiplicity. No configuration or public 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]
