andygrove opened a new pull request, #6937: URL: https://github.com/apache/datafusion-comet/pull/6937
## Which issue does this PR close? Closes #6914. Part of #6911. ## Rationale for this change Before a partition's first rows reach the native Iceberg writer, `DictionaryChooser` replays parquet-mr's first-page dictionary decision for every column. In the profile of the end-to-end Iceberg benchmark (#6910) that pre-pass is 1.7% of all CPU for nested types and 2.4% for primitives, and a fanout write pays it once per partition. Most of it was overhead around the accounting rather than the accounting itself: - every value went through a boxed `dyn Fn` to get its bytes, and every nested entry through a chain of boxed iterators (about a third of the pre-pass for nested types); - every value, fixed-width ones included, was hashed and compared as a byte slice; - each column built its set from empty, so the set rehashed its way up again for every column (7% of the pre-pass for nested types, 22% for primitives). ## What changes are included in this PR? The decision logic (`FirstPage::add`, `keeps_dictionary`, `HybridRuns`) is unchanged; how values reach it is rewritten: - **Typed keys.** The column's Arrow type, known from the schema, picks the key once per column. Fixed-width values of up to 8 bytes become a `u64` of their bits, 16-byte values such as decimals a `u128`, and strings, binaries and wider values a byte slice that carries its hash. Byte keys are hashed once, with the set's own randomly seeded hasher as before, and two values whose hashes differ are told apart without comparing their bytes. - **No boxed iterators.** `Leaf::path` resolves, per batch, the arrays on the way to the leaf. Rows are then visited one at a time by a small recursive walk that iterates the last level's range directly, so the page still reads nothing past where it ends. - **Sized, reused sets.** One set per kind of key, emptied for each column and reused. Each is sized up front from the leaf entries under the rows the page can take (an `O(levels)` walk over offsets per batch), capped at the most values the column's dictionary limit lets it hold and at 65,536, past which a set grows only as distinct values arrive. - **Repeats skip the set.** A value equal to the one before it is already in the dictionary, so it skips the hash insert. - A criterion benchmark, `native/core/benches/iceberg_dictionary_chooser.rs`, times one partition's choice over the column groups of `CometIcebergEndToEndBenchmark`: 20,000-row samples in 8192-row batches at Iceberg's default page and dictionary sizes, plus a 1000-row primitives sample for the small partitions of a fanout write. `DictionaryChooser` is re-exported `#[doc(hidden)]` for it, as the shuffle crate does with `bench_support`. Results on an Apple M3 Ultra, criterion against a baseline saved from unmodified `main`: | Shape | `main` | This PR | Speedup | | --------------- | -------- | ------- | ------- | | `primitives` | 3.55 ms | 1.42 ms | 2.5x | | `primitives_1k` | 192 µs | 63 µs | 3.1x | | `structs` | 3.14 ms | 1.33 ms | 2.4x | | `arrays` | 5.58 ms | 2.48 ms | 2.3x | | `maps` | 5.24 ms | 3.12 ms | 1.7x | | `nested` | 11.37 ms | 7.24 ms | 1.6x | With the pre-pass at 1.7% (nested) to 2.4% (primitives) of the end-to-end benchmark's CPU, that should take roughly 0.6% to 1.4% off its total. That is an estimate from the profile, not an end-to-end measurement. The method follows the `optimize-comet-expression` skill: baseline from unmodified source, decisions identical to `main`, and every shape faster. ## How are these changes tested? The existing tests pass, including the ones that pin answers recorded from parquet-mr. Two of them changed: - `a_column_is_read_only_as_far_as_its_first_page` counted the top-level iterator's rows, which no longer exists. It now counts the values the page reads: exactly the 819,200 of its first 100 rows. - `values_under_a_null_list_are_not_counted` put its null list in row 0. A column whose dictionary overflows within its first row has a page of no rows and is left as configured, on `main` as here, so the test passed even when the values under a null list were counted. A valid row now comes first, and the test fails if the null check on an intermediate level is removed. New test `reads_every_leaf_type` covers every leaf type the dispatch handles (ints, longs, floats, doubles, dates, times, timestamps, `Decimal128` at both physical widths, `Decimal256`, and the string, binary and view types), flat and under large and fixed-size lists, in each of which ten values keep their dictionary and distinct values do not. To check that the rewrite makes the same decisions as `main`, I also ran a differential test, not included here, that compared this implementation with `main`'s over 50,000 random cases: random nestings of structs, lists, large lists, fixed-size lists and maps over every leaf type, random cardinalities, run lengths and null densities at every level (including null lists that span child values), samples sliced at an offset and cut into random batches (some empty), and random page row, page size and dictionary limits. Every column got the same answer (130,742 kept their dictionary, 62,538 did not), and removing the intermediate null check made it fail. -- 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]
