gortiz commented on issue #19339: URL: https://github.com/apache/pinot/issues/19339#issuecomment-5717906126
Thanks @Jackie-Jiang — that history is exactly the right frame, and I agree with your reading. I have worked through all three questions; #19408 has been updated. ## 2. Should deferral be limited to subtrees containing scan/expression predicates? Yes. Done. Deferral is now driven by `BlockDocIdSet#isScanBased()`, which the composites compute over their children; `isApplyAndDeferrable()` follows it. An index-only subtree returns the same bitmap either way, so handing it a candidate set only added an intersection per branch. Reading this off the DocIdSet rather than the operator tree turned out to be both simpler — no new constructor parameters anywhere — and more accurate. An operator that scans *internally* and hands back a bitmap, such as a non-exact range index or an H3 index, has already paid for that scan by the time its DocIdSet exists, so restricting it later would gain nothing; the DocIdSet-level view correctly reports `false`, where an operator-level flag would have said "scan-based". It also takes the last piece of policy out of `isApplyAndDeferrable()`, so the mode is enforced only by the parent `AndDocIdSet`. Measured neutral: `INDEXED_OR` below is 0.99–1.02x time and 1.00x allocation. ## 3. Can we validate with latency and allocation benchmarks? Done — `BenchmarkAndRestrictionPushdown` in `pinot-perf`. 2M documents, a real `SVScanDocIdIterator` over a fixed-bit forward index, `-prof gc` for allocation. Ratios of push-down on to push-down off, lower is better: | shape | consume | sel | time | alloc | |---|---|---|---|---| | SCAN_IN_OR | DRAIN | 0.01 | **0.03x** | 0.10x | | SCAN_IN_OR | DRAIN | 0.5 | 0.67x | 1.14x | | SCAN_IN_OR | LIMIT | 0.01 | **0.02x** | 0.10x | | SCAN_IN_OR | LIMIT | 0.5 | 0.64x | 1.14x | | SCAN_ONLY_OR | DRAIN | 0.01 | 0.28x | 21.95x | | SCAN_ONLY_OR | DRAIN | 0.5 | 0.34x | 231.14x | | SCAN_ONLY_OR | LIMIT | 0.01 | **144.77x** | 25.04x | | SCAN_ONLY_OR | LIMIT | 0.5 | **9431.50x** | 383.65x | | INDEXED_OR | all four | | 0.99–1.02x | 1.00x | `SCAN_IN_OR` is a scan next to an index-based predicate inside an OR branch — the shape reported here. `SCAN_ONLY_OR` is scans directly under the OR with no index-based sibling. `INDEXED_OR` has no scan anywhere. You were right to push on this: **the entries-scanned proxy understated the risk by three orders of magnitude.** What the PR previously described as "21–41% more entries scanned" for a limited selection is, in the worst shape, 9431x slower and 384x more allocation. That shape's OR is already lazy on master, so materializing it replaces a scan of a few dozen documents with a scan of the whole segment. Two other things fell out that I did not expect: - `SCAN_IN_OR` with a LIMIT is **faster** with the push-down, not slower. That OR is not lazy on master either — it is driven by `advance()`, and `SVScanDocIdIterator.advance` scans *forward from* the target until it finds a match. So the loss is not "selections" in general; it is specifically ORs that are genuinely lazy today. - The gain on the reported shape is largest exactly where the enclosing AND is selective, which is the production case in this issue. ## 1. Can candidate propagation preserve lazy evaluation and early termination? Yes, and there is now a spike with numbers rather than a design argument: **#19589** (draft, stacked on #19408). It adds a re-entrant per-chunk kernel, `ScanBasedDocIdIterator#matchDocIds(int[], int)`, and a `RestrictedScanDocIdIterator` that drives a scan from an upstream candidate stream a chunk at a time. The scan still never sees a document outside the candidate set, but nothing is materialized. The only thing that made `applyAnd` non-re-entrant was a trailing `close()` in `SVScanDocIdIterator` releasing one `ForwardIndexReaderContext`; `MVScanDocIdIterator#applyAnd` was already re-entrant. Same benchmark, three strategies, with a setup assertion that all three return identical documents: | shape | consume | sel | eager time | streaming time | eager alloc | streaming alloc | |---|---|---|---|---|---|---| | SCAN_IN_OR | DRAIN | 0.01 | 0.03x | 0.03x | 0.10x | 0.06x | | SCAN_IN_OR | DRAIN | 0.5 | **0.66x** | 1.21x | 1.14x | 0.27x | | SCAN_IN_OR | LIMIT | 0.01 | 0.02x | **0.01x** | 0.10x | 0.06x | | SCAN_IN_OR | LIMIT | 0.5 | 0.58x | **0.04x** | 1.14x | 0.26x | | SCAN_ONLY_OR | DRAIN | 0.01 | **0.32x** | 0.40x | 21.97x | 1.41x | | SCAN_ONLY_OR | DRAIN | 0.5 | **0.34x** | 0.53x | 232.27x | 1.17x | | SCAN_ONLY_OR | LIMIT | 0.01 | 138.85x | **2.23x** | 25.04x | 1.33x | | SCAN_ONLY_OR | LIMIT | 0.5 | 7925.64x | **3.27x** | 383.31x | 1.33x | Streaming removes the cliff — worst case 3.27x instead of 7926x, allocation 1.33x instead of 383x — and beats eager wherever the consumer stops early, because it keeps the early termination eager destroys. But **eager is still the better strategy for a full drain**: 0.66x against 1.21x on `SCAN_IN_OR` at high candidate density, where streaming is actually slower than master. Chunking costs more than it saves when every matching document will be read anyway. So my answer to your first question is: streaming does not let us drop the mode, it changes what the mode *chooses* — eager when the query will drain the filter, streaming when it may stop early. `AUTO` stops being a safety gate and becomes a strategy selector, and its excluded branch goes from merely safe to fast. I would still keep it as an explicit follow-up rather than folding it into #19408, for two reasons: the spike is not wired into `AndDocIdSet`, and the scan in the benchmark is an `SVScanDocIdIterator`. An `ExpressionScanDocIdIterator` — the `IN_SUBQUERY` case that opened this issue — builds a whole `ProjectionOperator` per call, so per chunk it will want a much larger chunk, and a larger chunk erodes the early-termination granularity that is the entire point. Measuring that trade-off is the entry criterion for doing it properly, and it is still open. ## The historical cases - **#10396** and **#9402** are both fixed by #19408 and both still open. #9402's `P AND ((A AND B) OR C)` is `SCAN_IN_OR` above; #10396's `advance()` scanning nearly the whole segment is the mechanism I describe under question 3. With this issue that is three independent reports of the same gap. - **#7597** is *not* covered. Pushing the restriction into the range index itself via `RangeBitmap`'s context parameter is a layer below this, and needs the restriction to arrive at the *operator* level — `AndFilterOperator#getTrues()` evaluates every child eagerly, so `BitSlicedRangeIndexReader` has already produced its bitmap by the time any `BlockDocIdSet` exists. `FilterPlanNode#wirePreFilterForVectorOperators` already does exactly that shape for vector indexes, so a `FilterAwareRangeIndexReader` looks like a fairly mechanical generalization. Happy to open that separately. - **#5833** I read as you do: a different scan strategy, closed for lack of time rather than on the evidence. The caution about workload dependence is fair, and the matrix above is my attempt to answer it directly — which is how the `SCAN_ONLY_OR` cliff surfaced at all. - **#12611 / #15756** is the one I took most seriously, since it is the same iterator contracts. #19408 adds a `release()` for children abandoned by a short-circuit (those iterators hold `ForwardIndexReaderContext`s and are otherwise closed only by reaching EOF), rejects a second consumption of a composite DocIdSet, and preserves the `[0, numDocs)` bound that `NotDocIdIterator` applies — the candidate set can carry ids past `numDocs` because `BitmapDocIdIterator#getDocIds()` hands out the raw bitmap while its `next()` clamps. An intersection cannot introduce such an id, but a complement can. The 200-tree randomized differential test is there to catch exactly the class of regression #15756 had to fix. - **#8453** is the one that most directly supports the design. The eager-for-aggregations, lazy-for-selections split you discussed there is what `AUTO` encodes, and the numbers above put a size on it. ## Adjustments made The default stays `NEVER`. `AUTO` is unchanged. What changed as a result of your comment: deferral is now limited to scan-bearing subtrees, the benchmark exists, and the PR description now states the `SCAN_ONLY_OR` risk in latency and allocation rather than in entries scanned — `ALWAYS` is genuinely dangerous on a selection workload, and the PR previously undersold that. -- 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]
