gortiz opened a new issue, #19339: URL: https://github.com/apache/pinot/issues/19339
### Description When a filter has the shape `P AND (A OR B)`, Pinot evaluates the `(A OR B)` subtree independently of `P`. If `P` is highly selective, and a branch of the OR contains a predicate with no index — for example `IN_ID_SET(...)`, produced by `IN_SUBQUERY`, which is evaluated per document through `ExpressionScanDocIdIterator` — that predicate is evaluated for every document matching the branch, not only for the documents that satisfy `P`. Duplicating `P` inside the OR branch by hand is a sound rewrite (`P ∧ (A∨B) ≡ P ∧ ((P∧A) ∨ (P∧B))`, and it holds under three-valued logic because the filter only passes TRUE). Doing so makes such queries several times faster, which shows the restriction is simply not being applied. ### The cost also depends on whether the branch columns have indexes `AndDocIdSet#iterator()` chooses between two strategies at [`AndDocIdSet.java:121`](https://github.com/apache/pinot/blob/master/pinot-core/src/main/java/org/apache/pinot/core/operator/docidsets/AndDocIdSet.java#L121): ```java if ((numIndexBasedDocIdIterators > 0 && numScanBasedDocIdIterators > 0) || numIndexBasedDocIdIterators > 1) { // eager: merge the index bitmaps, then scanIterator.applyAnd(docIds) } else { return new AndDocIdIterator(allDocIdIterators); // lazy } ``` - With **no** index-based child in the AND under the OR, the subtree stays lazy. `OrDocIdSet` keeps it lazy, the outer `AndDocIdSet` places it in `remainingDocIdIterators`, and the outer merged bitmap — which includes `P` — drives it. The expensive predicate is only evaluated at documents that already match `P`. - With **one or more** index-based children, the eager path is taken. The branch is fully materialized as a bitmap over the whole segment, ignoring `P`, before the outer AND intersects. So adding an index to a column that appears inside an OR branch can make a query orders of magnitude slower. In a production deployment, the same query returning the same two rows went from ~500 to ~17,000,000 `numEntriesScannedInFilter`, and allocated 4.6 GB, after the only change was two columns in the branch gaining a range index and an inverted index respectively. ### Reproduction sketch Table `events(tenant_id INT, ts LONG, kind STRING, id LONG, value DOUBLE)`, one selective tenant among many. ```sql SELECT sum(value) FROM events WHERE tenant_id = 42 AND ( ( ts >= :t0 AND ts <= :t1 AND kind = 'a' AND IN_SUBQUERY(id, 'SELECT ID_SET(id) FROM events WHERE tenant_id = 42 AND ts >= :t2') = 0 ) OR ( ts >= :t2 AND kind = 'b' ) ) ``` Run it twice: once with no index on `ts` or `kind`, once with a range index on `ts` and an inverted index on `kind`. The second configuration is far slower and scans far more entries in the filter. ### Suggested fixes 1. **Push the restriction down at execution time (preferred).** Generalize `applyAnd` from `ScanBasedDocIdIterator` to `BlockDocIdSet`, so `AndDocIdSet` can pass its merged index bitmap into composite children: `OrDocIdSet.applyAnd(b)` = union of `child.applyAnd(b)`, `AndDocIdSet.applyAnd(b)` = intersect starting from `b`. This needs no heuristic, adds no duplicated index lookups, works at any nesting depth, and removes the eager/lazy cliff. Needs care with `numEntriesScannedInFilter` accounting, `NotDocIdSet`, and null handling. 2. **Rewrite in the planner.** Add a `FilterOptimizer` that distributes selective conjuncts (EQ/IN on dictionary-encoded columns) from an enclosing AND into each OR branch. Cheaper to implement and gateable behind a query option, but it is a heuristic: duplicating a predicate on a raw column doubles a scan. -- 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]
