gortiz opened a new pull request, #19408: URL: https://github.com/apache/pinot/pull/19408
Fixes #19339 ## Problem When a filter has the shape `P AND (A OR B)`, the `(A OR B)` subtree is evaluated independently of `P`. `AndDocIdSet#iterator()` is the only place a restriction is ever pushed anywhere: it merges the index-based children into a bitmap and hands it to each `ScanBasedDocIdIterator` via `applyAnd`. `OrDocIdSet` has no equivalent, so a predicate nested inside an OR branch never learns about `P`. That has two consequences: - A predicate with no usable index inside an OR branch — `IN_SUBQUERY` evaluated through `ExpressionScanDocIdIterator`, or a plain scan on a segment missing its range index — is evaluated on every document its branch matches, however selective `P` is. - **Adding an index to a column inside an OR branch can make a query much slower.** With no index-based sibling the branch stays lazy and is driven by the outer merged bitmap; add one and the branch takes the eager path in `AndDocIdSet#iterator()`, materializing over the whole segment before the outer AND intersects. In one deployment the same query returning the same two rows went from ~500 to ~17,000,000 `numEntriesScannedInFilter`, allocating 4.6 GB, after two columns in the branch gained a range index and an inverted index. ## Fix Generalize `applyAnd` from `ScanBasedDocIdIterator` up to `BlockDocIdSet`, so an AND can hand the document ids it has matched to its composite children: - `AndDocIdSet#applyAnd` adds the candidate set to its children as one more index-based child and runs `iterator()`. Everything `iterator()` already does — the sorted-range intersection, sorting bitmaps by cardinality, `AndScanReordering`, running every scan against the merged document ids — therefore applies to the restricted evaluation too, with a single implementation of AND. - `OrDocIdSet#applyAnd` unions the branches, each restricted to the candidates no earlier branch has matched, using `(A OR B) AND S == (A AND S) OR (B AND (S MINUS (A AND S)))`. A scan-based branch costs time linear in the candidate set it is handed, so narrowing avoids one full pass per branch. - `NotDocIdSet#applyAnd` returns the candidates the child does not match, so the child is only evaluated on the candidates. `AndDocIdSet#iterator()` defers `iterator()` on children that report `isApplyAndDeferrable()` and pushes its merged document ids into them instead. With no index-based child to seed the push-down it falls back to the lazy `AndDocIdIterator`, exactly as before. This needs no heuristic, adds no duplicated index lookups, works at any nesting depth, and removes the eager/lazy cliff rather than routing around it. ## This ships disabled The push-down **materializes** the filter result instead of streaming it, so a query that stops before reading every matching document ends up doing the full filter work. Measured on the existing query suite: aggregations scanned 7–19% fewer entries, while a selection with `LIMIT` scanned 21–41% more. It is therefore gated by `AndRestrictionPushdownMode`, defaulting to `NEVER`: | Mode | Behavior | |---|---| | `NEVER` (default) | Never push down. Provably identical to today. | | `ALWAYS` | Always push down. | | `AUTO` | Push down only for queries that read every matching document — aggregation and group-by. | `AUTO` excludes a selection query without ORDER BY (stops at its LIMIT), a DISTINCT query (`DistinctOperator` stops the same way, and DISTINCT is modelled as an aggregation function so it needs excluding explicitly), `LIMIT 0`, and — conservatively — a selection query *with* ORDER BY, because whether it can stop early is decided per segment in `SelectionPlanNode`, which picks `SelectionPartiallyOrderedBy*` from the segment's sorted column. - Server config: `pinot.server.query.executor.and.restriction.pushdown.mode` - Query option: `SET andRestrictionPushdownMode = 'always'` The mode is resolved once per query in `InstancePlanMakerImplV2#applyQueryOptions` and carried on `QueryContext`, so the filter operators only ever see the resolved flag. ## Known limitation `isApplyAndDeferrable()` is currently structural: an OR or NOT is deferred whether or not its subtree contains anything scan-based. When every branch is index-based there is nothing to save, and the incremental loop costs more bitmap work than the plain union does. Narrowing this to "the subtree contains a scan- or expression-based predicate" needs the flag plumbed from the filter operator tree at plan time; I would rather do it as a follow-up than grow this PR. It is dormant at the default. ## Test plan - `AndDocIdSetPushdownTest` — the reported shape (`AND(P, OR(AND(idx, scan), other))`): the scan visits 100 documents instead of 5000, with identical results. Plus the NOT case, the no-index-child fallback, sorted-range boundaries, the `numDocs` bound on NOT and MATCH-ALL, release of short-circuited OR branches, and 200 randomized filter trees over bitmap/scan/sorted/match-all/empty leaves asserting identical document ids with the push-down on and off. - `AndRestrictionPushdownModeTest` — mode resolution: every `AUTO` inclusion and exclusion, `ALWAYS`/`NEVER`, case-insensitivity, invalid values rejected, server default, and the query option overriding it. - `AndRestrictionPushdownQueriesTest` — end to end against a real segment in every mode: `ALWAYS` scans strictly fewer entries than `NEVER` with identical rows and `numDocsScanned`; `AUTO` matches `NEVER` for selections and `ALWAYS` for aggregations; the default is pinned to off. Covers filtered aggregations (`CombinedFilterOperator`) and null handling, where `getFalses()` wraps the push-down in a NOT over `OR(trues, nulls)`. - Full `org.apache.pinot.core.**` (6397) and `org.apache.pinot.queries.**` (1422) suites pass. No existing expectation changed, because the default leaves every existing query on its current plan. ## Release notes Two new user-facing configuration surfaces, both defaulting to the current behavior: the server config `pinot.server.query.executor.and.restriction.pushdown.mode` and the query option `andRestrictionPushdownMode`. Enabling either changes `numEntriesScannedInFilter` for affected queries. Old servers in a mixed-version cluster ignore the unknown query option, which matches the `NEVER` default. -- 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]
