ranflarion opened a new issue, #10965: URL: https://github.com/apache/arrow-rs/issues/10965
### Is your feature request related to a problem or challenge? When a column has a bloom filter enabled, the writer hashes every value into the filter as it is encoded (`ColumnValueEncoderImpl::write_slice` in `column/writer/encoder.rs`, and the free `encode` function in `arrow/arrow_writer/byte_array.rs`), regardless of whether the value is going through the dictionary encoder. While a dictionary is in use the interner already deduplicates the values, so for a low-cardinality column with N rows and D distinct values the filter receives N inserts where D would carry exactly the same information. Low-cardinality columns are precisely the ones that stay dictionary encoded, so the per-row hashing cost lands where the filter is worth the least. This came up in the review of #10963 (skip the bloom filter for chunks whose data pages are all dictionary encoded): with that option on, a dictionary-only chunk still pays N inserts for a filter that is then discarded. ### Describe the solution you'd like Defer bloom filter population while a dictionary encoder is active: - `write` paths insert into the filter only when no dictionary encoder is active (the fallback / plain encoder is in use). - `flush_dict_page`, which runs both when the writer falls back from dictionary encoding and when the column chunk is closed, inserts every distinct value held by the interner (`KeyStorage::uniques` for the primitive encoder, `ByteArrayStorage` slices for the byte array encoder) before handing the dictionary page over. After a fallback the dictionary page keeps covering the already written index-encoded pages and later plain pages insert per value as today, so the filter ends up containing the same set of values. Folding (#9628) decides from the final fill rate, so the serialized filter is byte-identical to what is written now; the change is purely on the write-side cost, from one hash per row to one hash per distinct value for dictionary-encoded columns. Combined with #10963, a chunk that stays dictionary encoded with that option set costs one pass over its distinct values, which is then dropped, rather than one pass over its rows. ### Describe alternatives you've considered - Keep per-row insertion. Simple, but it is the one part of writing a dictionary-encoded column that still does per-row work proportional to the value bytes. - Reuse the interner's hash for the bloom filter. The interner hashes with a different function (and the SBBF hash is fixed by the format), so the two cannot share work. - Have the column writer tell the encoder whether the filter will be written before flushing the dictionary, to avoid even the per-distinct-value pass when #10963 drops the filter. That needs a change to the `ColumnValueEncoder` trait; left out here as the remaining cost is one pass over the distinct values. ### Additional context Suggested by @etseidl while reviewing #10963. I have an implementation with round-trip tests for the dictionary-only and the fallback case and will open a PR once #10963 lands, since both touch the encoder flush path. -- 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]
