apache / apache/pinot

Predicates outside an OR do not restrict its branches, and adding an index there can cause a large regression

Open
#19,339 5 comments 1 reaction 0 assignees View on GitHub
bug performance query
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.