waterWang opened a new pull request, #19350:
URL: https://github.com/apache/pinot/pull/19350
Fixes #19339
## Description
When a filter has the shape `P AND (A OR B)`, Pinot evaluates the `(A OR B)`
subtree independently of `P`. If a branch of the OR contains a predicate with
no index (e.g. `IN_SUBQUERY` evaluated via `ExpressionScanDocIdIterator`), that
predicate is evaluated for every document matching the branch, not only for the
documents that satisfy `P`.
This PR adds a new `DistributeConjunctsIntoOrFilterOptimizer` that
distributes selective conjuncts (EQUALS/IN on single columns) from an enclosing
AND into each OR branch:
```
P AND (A OR B) → P AND ((P AND A) OR (P AND B))
```
This rewrite is sound because in three-valued logic, `P ∧ (A ∨ B) ≡ P ∧ ((P
∧ A) ∨ (P ∧ B))` when the filter only passes TRUE (SQL WHERE semantics).
## The bug in detail
The `AndDocIdSet#iterator()` method chooses between two strategies at the
eager/lazy threshold. When an OR subtree contains an AND with both index-based
and scan-based children, the eager path materializes the index-based children
into a bitmap over the **entire segment** before applying the scan-based
predicate. This means expensive predicates like `IN_SUBQUERY` are evaluated for
every document in the segment, not just those matching the enclosing AND's
selective predicate `P`.
Adding an index to a column inside an OR branch **makes the query slower**
because it triggers the eager path:
> With no index-based child in the AND under the OR: lazy path, outer merged
bitmap drives it. The expensive predicate is only evaluated at documents that
already match P.
> With one or more index-based children: eager path, branch is fully
materialized over the whole segment, ignoring P.
In production, the same query returning the same two rows went from ~500 to
~17,000,000 `numEntriesScannedInFilter` after adding indexes to two columns in
the OR branch.
## Test plan
- Added `DistributeConjunctsIntoOrFilterOptimizerTest` with 5 test cases:
- Basic distribution: `P AND (A OR B)` → `P AND ((P AND A) OR (P AND B))`
- No distribution when there is no OR child
- No distribution when the conjunct is not a simple column predicate
- Branch already contains the conjunct → no redundant AND(P, P) created
- No rewrite when there is no AND child (only OR)
- All existing optimizer tests should continue to pass (the optimizer is
added at the end of the pipeline, after all existing optimizers)
--
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]
