apache / apache/pinot

Performance degradation case in evaluation of nested AND-OR operators.

Open
#10,396 1 comment 1 reaction 0 assignees View on GitHub
performance
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.