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

[gortiz]

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:

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.

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.

[waterWang]

I've opened PR #19350 to fix this issue. The fix adds a DistributeConjunctsIntoOrFilterOptimizer that implements the planner-based approach (option 2 from the issue): selective conjuncts (EQUALS/IN on single columns) from an enclosing AND are distributed into each OR branch, so that P AND (A OR B) becomes P AND ((P AND A) OR (P AND B)). This ensures the OR subtree's scan-based predicates are only evaluated against documents matching the selective predicate P.

[alexch2000]

We hit the same cliff, from a different direction. Instead of a subquery inside the OR, the OR is on two time ranges (day-over-day comparison) and the scan appears only on segments that lack the configured range index.

Query shape (v1 engine, realtime table, ~134K segments):

SELECT <10-min bucket>, FUNNELCOUNT(...)
FROM events
WHERE (
    (name = 'A' AND flow_id = 'F' AND action_id = 'X')
    OR (name = 'B' AND flow_id = 'F')
  )
  AND device_os IN ('android', 'ios')
  AND (
    (ts >= :a0 AND ts < :a1)
    OR (ts >= :b0 AND ts < :b1)   -- b = a - 24h
  )
GROUP BY 1

name, flow_id, action_id, device_os have inverted indexes. ts is the time column and has rangeIndexColumns configured, but ~3% of segments are missing the index on disk (separate issue, being fixed by reload).

Numbers

	window A only	A OR B
numEntriesScannedInFilter	101,187	441,757,659
numDocsScanned	66,800	154,975
numSegmentsProcessed	1,384	4,541
realtimeThreadMemAllocatedBytes	684 MB	1.83 GB

~4,400× more filter work for ~2.3× more matched rows. Window B alone behaves like window A alone.

Verbose EXPLAIN on the OR query (all cohorts, 4,588 segments after pruning):

plan on the time predicate	segments
single FILTER_RANGE_INDEX under FILTER_AND	3,449
FILTER_OR → 2× FILTER_RANGE_INDEX	1,004
single FILTER_FULL_SCAN under FILTER_AND	44
FILTER_OR → 2× FILTER_FULL_SCAN	83
FILTER_EMPTY	8

The 83 segments account for essentially all of the 441M: ~2.7M docs × 2 predicates each, i.e. a full pass over the column per range predicate. The 44 unindexed segments whose scan sits directly under the AND cost almost nothing, because AndDocIdSet hands them the intersected inverted-index bitmap via ScanBasedDocIdIterator.applyAnd. The 83 get no candidate set because OrDocIdSet has no equivalent, and AndDocIdSet#iterator() calls iterator() on the OR child before it has computed anything.

Two details that made this particularly sharp for us:

• Per segment, a range predicate that can't match the segment's min/max becomes EmptyFilterOperator and is dropped from the OR, so the OR only survives on segments that overlap both windows.
• Each window on its own never exposes the missing index (~100K entries), so this was invisible until both windows were combined in one query.

On the two proposed fixes

+1 to option 1 (push applyAnd down into composite doc-id sets). For our shape, #19350 as currently scoped would help only marginally: the only conjunct it can distribute is device__os IN ('android','ios'), which matches most rows. The selective part of the outer AND is the OR(AND(name, flow_id, action_id), AND(name, flow_id)) block, which isn't a single-column EQ/IN and so wouldn't be pushed into the time-range branches.

[richardstartin]

@gortiz if you push the intersection down to the range index you can make use of RangeBitmap’s context parameter, which allows the range index evaluation to skip over unnecessary regions of the range index itself. This is typically much faster; RangeBitmap is being used for observability at Yandex and making use of the context parameter to push intersections down is critical to performance there.