Predicates outside an OR do not restrict its branches, and adding an index there can cause a large regression
- Dominant language
- Java
- Stars
- 6.1k
- Forks
- 1.5k
- Avg merge
- 2d 3h
- Merged PRs (30d)
- 195
Description
### 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.
Contributor guide
Research direction
Start with AndDocIdSet.java:121 and trace how OrDocIdSet, AndDocIdSet, ScanBasedDocIdIterator, and BlockDocIdSet combine document iterators. Reproduce the query with and without the range and inverted indexes, comparing numEntriesScannedInFilter and allocation; done means the selective outer predicate restricts nested OR branches without the eager/lazy regression, while accounting for NotDocIdSet and null handling.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java, sql
- Domain
- databases, performance
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100