gortiz opened a new pull request, #18692:
URL: https://github.com/apache/pinot/pull/18692
## Problem
For `SELECT ... ORDER BY <col> [DESC] LIMIT n` on a table range-partitioned
on `<col>`, `SelectionQuerySegmentPruner` prunes down to the handful of
segments the LIMIT needs (an unfiltered "latest n" query touches a couple of
segments). Adding **any** filter — even a trivially-true one on an unrelated
column — defeated that pruning, and the query engaged every matching segment.
The cause: `SelectionQuerySegmentPruner.isApplicableTo` only allowed the
order-by/LIMIT pruning when there was **no** filter, because the pruner sizes
its keep-set by accumulating the unfiltered `getTotalDocs()` until `LIMIT +
OFFSET` — which, with a filter, is an *upper* bound on matching rows and would
prune segments that still hold top-n matches (wrong results).
See #18685 for the full reproduction and analysis.
## Change
Extend `SelectionQuerySegmentPruner` to run with a filter by accumulating a
**lower bound** on each segment's matching rows instead of `getTotalDocs()`:
```
guaranteedMatchingDocs(S) = getTotalDocs(S) if S provably FULLY satisfies
the filter
0 otherwise
```
- "Provably full" is the dual of `ColumnValueSegmentPruner`'s no-match test,
computed from the predicate column's min/max for `>`, `>=`, `<`, `<=`, `=`,
`<>` (conjunction = all children full; OR = any child full; anything unprovable
= `false`).
- Because the accumulation only ever *under*-counts, the boundary is reached
only once ≥ LIMIT matching rows provably exist, so a segment is never pruned
when it might still hold a top-n row. Straddling/partially-matching segments
count 0 but are still kept (they overlap the boundary). An `AND (...)` with a
non-provable conjunct simply degrades to "no pruning" — never wrong.
- The optimization is **skipped when null handling is active** for a column
(nulls are stored as a default value that pollutes the min/max metadata and the
doc count), and a `NaN` min/max is never treated as a full match.
The execution-time `MinMaxValueBasedSelectionOrderByCombineOperator` skip
already worked with a filter; this restores the *plan-time* pruning that avoids
building/opening the pruned segments at all.
## Tests
`SelectionQuerySegmentPrunerTest` adds coverage for: each comparison
operator, ASC/DESC, the straddling-segment counterexample (the case the lower
bound exists to protect), the `AND`-with-non-provable-conjunct degradation, the
FLOAT/DOUBLE NaN guard, and the null-handling gate (incl. column-based null
handling: non-nullable column still optimizes, nullable does not).
## Benchmark
Adds `BenchmarkSelectionOrderByFilterPruning` (pinot-perf). It toggles
`enableNullHandling` to compare the optimized path against the pre-fix path
**within one build** (null handling gates the optimization off). On a
100-segment table (20k rows/segment), `LIMIT 10`:
| query | score |
|---|---:|
| filtered, optimized | **0.661 ± 0.051 ms/op** |
| filtered, null handling on (pre-fix) | 0.824 ± 0.117 ms/op |
| no filter (reference) | 0.661 ± 0.076 ms/op |
With the fix the filtered query reaches parity with the unfiltered one;
without it the same query is measurably slower. The gap widens with segment
count and per-segment cost.
Closes #18685
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
