Performance degradation case in evaluation of nested AND-OR operators.
- Dominant language
- Java
- Stars
- 6.1k
- Forks
- 1.5k
- Avg merge
- 2d 55m
- Merged PRs (30d)
- 182
Description
Recently @vvivekiyer and @SabrinaZhaozyf found a case where
q2: `SELECT ... FROM ... WHERE type = 'type' AND date > 'date' AND (isSubnetOf('subnet1', ip) OR isSubnetOf('subnet2', ip))`
is significantly slower than
q1: `SELECT ... FROM ... WHERE type = 'type' AND date > 'date' AND (isSubnetOf('subnet1', ip))`
(type has inv index and date has range index)
The execution stats indicate that the `numEntriesScannedInFilter` for q2 is significantly larger than q1: nESI_q2 >> nESI_q1
However if we continue to increase the number of isSubnetOf('...', ip) to 3, then (nESI_q2-nESI_q1) ~ (nESI_q3-nESI_q2)
This means there's a performance degradation once we have the AND-OR structure. After some digging, we found that this is due to the current implementation of `AndDocIdSet` and `AndDocIdIterator`:
When we execute q2, `(isSubnetOf('subnet1', ip) OR isSubnetOf('subnet2', ip))`(->OrDocIdIterator) becomes `remainingDocIdIterators` in `AndDocIdSet` and produce a composite `AndDocIdIterator`, where the `next()` function uses a greedy algorithm for intersection. Meanwhile, the intersection result of `type = 'type' AND date > 'date' ` is not pushed down to the scanning in OR predicate. As the result, OR predicate could end up greedily scanning almost the entire dataset in [`advance()`](https://github.com/apache/pinot/blob/98faf2bfac7ec69ced93eec25cf57237a911c560/pinot-core/src/main/java/org/apache/pinot/core/operator/dociditerators/AndDocIdIterator.java#L51) if the matching doc ids in OR predicate is sparse.
One approach of resolving this is after evaluating `type = 'type' AND date > 'date'` to a bitmap, we wire it down to scanning operators so that they can skip the row ids not in the bitmap.
Please add if I'm missing anything @vvivekiyer @SabrinaZhaozyf. We can share some stats here as well.
Contributor guide
Assessment
This issue has not been assessed yet.