hhhizzz commented on issue #7456: URL: https://github.com/apache/arrow-rs/issues/7456#issuecomment-5236472864
I spent a while building and evaluating selection pushdown into Parquet dictionary decoding — the SIGMOD'23 "Selection Pushdown in Column Stores using Bit Manipulation Instructions" approach(https://dl.acm.org/doi/10.1145/3589323) — on top of the `Mask` selection infrastructure. The end-to-end conclusion is negative and I'm not proposing it as a feature, but two of the findings bear directly on this epic, especially on the second slow case in the description ("the filters are applied to columns which are also used in the query result"). Writing them up here in case they save someone the same weeks. ## What was built An opt-in reader path that decodes only the selected dictionary indices, rather than decoding every value and filtering afterwards. Five additive layers from the RLE/dictionary decoder up to `read_mask_batch`, admitted only when every projected column is flat, required and primitive, and execution is on the `Mask` path. Wired through both the sync and async/push-decoder paths, plus a DataFusion session option, and evaluated end to end on ClickBench, TPC-DS SF10 and TPC-H. ## The leaf kernel is genuinely fast Against the production-shaped comparator — stock `get_batch_with_dict` full decode followed by `arrow::compute::filter`, both arms digest-verified to produce identical output before any timing was recorded: | captured fixture | survival | selected vs production | |---|---|---| | ClickBench `hits.WatchID` | 2.8% | **4.55x** | | TPC-DS `cr_returned_date_sk` | 0.9% | 3.75x | | TPC-DS `cr_refunded_hdemo_sk` | 5.1% | 3.28x | | TPC-DS `cr_returned_date_sk` | 10.9% | 2.63x | | near-full survival (99.5%+) | ~100% | **inverts** — production 15–20% faster | The inversion at the top end is worth noting for this epic specifically: at high pass rates the selected path degenerates into the same full decode plus overhead, so it does nothing for the non-selective regime this issue targets. It helps the selective end, which is the opposite corner. ## Finding 1 — the predicate cache and selected decoding are mutually exclusive today This is the one most relevant here. `CachedArrayReader` exists to avoid decoding a column twice when it is read by both a filter and the output projection — the exact case in this issue's description. But a cache wrapper cannot participate in an admission check it does not forward: mine inherited the trait default and reported "not eligible", and under an all-or-nothing subtree rule that single wrapper disqualified the whole scan. So the two available answers to the same problem do not compose: - **caching** avoids the second decode entirely; - **selected decoding** makes the second decode cheap (only the surviving rows). Right now the cache silently wins, because the wrapped column is invisible to any admission predicate added to `ArrayReader`. Measured on TPC-H: disabling the predicate cache moved coverage from 10/22 to 14/22 queries and **3.9x the rows**. On ClickBench the only queries I ever covered at 100% were q30/q31 — whose filter column (`SearchPhrase`) is *not* in their output projection, so nothing was cached and nothing was disqualified. If someone pursues this direction, that choice probably wants to be made per column with knowledge of both costs, rather than decided implicitly by which wrapper got there first. ## Finding 2 — the filter chain is where selection pushdown actually earns its keep, and it is the easiest thing to leave out `ReadPlanBuilder::with_predicate_options` builds its reader with `ParquetRecordBatchReader::new`. That reader is not incidental: predicate *N* reads under the selection accumulated from predicates *1..N-1*, which is precisely the mechanism `RowFilter`'s doc comment describes ("as predicates eliminate rows, fewer rows from subsequent columns may be required"). I threaded my option through the output path and not through that constructor. The result, traced call by call on TPC-H Q6 — the original paper's own headline query, three chained predicates leaving ~1.9% of rows: | call class | calls | rows | |---|---|---| | filter chain, eligible columns | **711** | ~6,000,000 | | output phase | 106 | 114,160 | So the wiring reached **under 2%** of the maskable rows in the query the whole technique was designed around. Anyone building this should thread that constructor first, not last. ## Correctness: two traps, one of them silent An end-to-end differential gate over per-query output digests failed on its first run and surfaced both. 1. **Subtree admission must be decided before any child produces output.** Discovering a mixed projection after an earlier child has already written compact (already-filtered) data cannot be unwound — you hold one filtered and one unfiltered column destined for the same `RecordBatch`. Fixed with a side-effect-free predicate answered for the whole subtree before the first byte is decoded. 2. **A column chunk can change encoding mid-chunk.** Writers abandon dictionary encoding once the dictionary outgrows its page budget, so `RLE_DICTIONARY` pages can be followed by `PLAIN` ones in the same chunk. My decoder declined at the first `PLAIN` page and returned a short read; the layer above interpreted that as "chunk exhausted" and advanced to the next row group. **The row count still came out exactly right, with values taken from the wrong place.** Only a full-value content check caught it — row-count assertions and tolerance-based aggregate comparisons all passed. Fixed by never declining for a structurally eligible column and falling back to decode-then-filter internally. ## Why I stopped No query-level benefit was established, and I stopped at a pre-registered gate. Coverage under the conservative admission rule was 0/99 TPC-DS queries and 4/42 ClickBench queries (TPC-H, measured later, reaches 10/22). The two fully-covered queries ran at **100% coverage over 65M rows each and showed no reproducible direction across two rounds** — one swung 19% on identical binaries on dedicated hardware. Independently of the noise, the covered queries are 3.0–3.6% of suite runtime, so even pretending the entire covered portion were dictionary decode, a 2x–4x kernel bounds total improvement at roughly 1.4%–2.5%. I'd also temper expectations against the paper's numbers if anyone uses them for sizing. Its 3.1x for TPC-H Q6 is measured against a 2023 C++ baseline; a separate arm of this investigation found modern arrow-rs's existing full-decode path has already internalised most of that headroom (~2.8x geomean against the paper's own baseline shape). The residual against today's `main` should be expected to be substantially smaller. ## Possibly reusable - a regression case for reading across a mid-chunk dictionary→`PLAIN` change under `RowSelection`, validating the full value sequence rather than row counts. I'd want to check whether upstream already covers this before proposing it, and I'm not claiming it reproduces on unmodified `main`; - captured real-workload selection traces with provenance; - a coverage-counter methodology for proving an experimental path is actually executed — with the counter itself unit-tested, since a dead counter is indistinguishable from a dead path. Full write-up with data, commit pins, the reproduction notes and the caveats: https://github.com/hhhizzz/arrow-rs/blob/exp/v21-rle-selected-fill-20260807/experiments/shape-aware-selected-decoding/README.md It ran long and landed on "don't ship it", but the process turned out to have more in it than the verdict did, so I'd like to write the whole thing up as a blog post @alamb — the measurement design, the two traps, and why a fast kernel can reach almost none of its own benchmark. Happy to fold in anything people here think is worth emphasising, or to dig further into any of the numbers. -- 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]
