hhhizzz commented on PR #10141: URL: https://github.com/apache/arrow-rs/pull/10141#issuecomment-5236486859
> I think we are very close to being able to implement something like this > > * https://dl.acm.org/doi/10.1145/3589323 > > We probably already do it for unnested (leaf) nodes -- but need a bit more cleverness for structured nodes @alamb this comment sent me down a rabbit hole — I went and implemented the paper on top of this `Mask` infrastructure and measured it end to end. It didn't pay off, but the structured-node question you raised turned out to have a concrete answer, and two other things blocked me that I don't think are obvious from the outside. **On "a bit more cleverness for structured nodes":** the constraint is an ordering one. Admission has to be decided for the *entire* reader subtree **before any child produces output**. My first cut walked children in order and only discovered a mixed projection after an earlier child had already written compact, already-filtered data — at which point you're holding one filtered column and one unfiltered column destined for the same `RecordBatch`, and it cannot be unwound. It aborted a real ClickBench query (a `BYTE_ARRAY` column projected alongside an eligible integer one). The fix was a side-effect-free predicate answered for the whole subtree up front, before the first byte is decoded, plus a contract that a leaf may never decline mid-stream for anything it could have known statically. The interesting part is the corollary: anything a leaf *cannot* know statically has to be handled internally rather than by declining — a column chunk can switch from `RLE_DICTIONARY` to `PLAIN` partway through, and if a leaf declines there and the caller reads the short return as "chunk exhausted", you get the correct row count with values sourced from the wrong row group. That one only showed up under a full-value content check. **Two things blocked me that weren't the structured-node problem.** Both look identical to "the workload isn't eligible", so a coverage counter alone can't tell them apart: 1. `CachedArrayReader` wraps any column read by both a filter and the projection. It can't forward an admission predicate it doesn't know about, so it reports ineligible, and under an all-or-nothing subtree rule that one wrapper disqualifies the entire scan. Disabling the predicate cache moved TPC-H coverage from 10/22 to 14/22 queries and 3.9x the rows. It also explains exactly which ClickBench queries survived: q30/q31, whose filter column isn't in their output projection. 2. `ReadPlanBuilder::with_predicate_options` builds its reader via `ParquetRecordBatchReader::new`. Predicate *N* there reads under the selection accumulated from predicates *1..N-1* — which is the mechanism the paper is actually about. I wired the output path and not that constructor, so on TPC-H Q6 (the paper's own headline query) my implementation touched **under 2%** of the maskable rows: 711 filter-chain calls over ~6M rows, against 106 output-phase calls over 114K. (To be clear, neither is an upstream bug — the admission predicate is an addition on my branch, not an existing API. They're both "here's where a new `ArrayReader` capability silently loses coverage".) **Outcome, honestly:** the leaf kernel is fast — 2.6x–4.6x against stock `get_batch_with_dict` + `arrow::compute::filter` on captured low-survival pages — but I never established a query-level benefit. My two fully-covered queries ran at 100% coverage over 65M rows each and showed no reproducible direction across two rounds. And for sizing: the paper's 3.1x on Q6 is against a 2023 C++ baseline, while modern arrow-rs's full-decode path has already absorbed most of that headroom, so the residual against today's `main` should be expected to be much smaller. Write-up with the data and commit pins: https://github.com/hhhizzz/arrow-rs/blob/exp/v21-rle-selected-fill-20260807/experiments/shape-aware-selected-decoding/README.md — I've also filed the longer version on #7456 since the predicate-cache interaction lands squarely on that epic's second slow case. -- 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]
