Repository navigation
Commit 47b2e1d
authored
[improvement](inverted index) Push the candidate row bitmap down into phrase queries (apache#67180)
### What problem does this PR solve?
Problem Summary:
The cost of a phrase-family inverted index query (MATCH_PHRASE /
MATCH_PHRASE_PREFIX multi-term path) is proportional to the whole
segment's
postings and positions, regardless of how small the surviving candidate
set
already is. On a production log table a 9-minute time window left only
22.4%
of each segment's rows after short-key pruning, yet every phrase
conjunct
still walked the full segment: per-query profile showed 2,657 segments,
11,913s of InvertedIndexSearcherSearchExecTime (99.7% of scan cost) and
125 GiB of index reads for a query whose final result was 0 rows. A
microbenchmark against the same code path calibrates the cost model to
~0.9µs per co-occurrence candidate, so evaluation cost tracks
candidates,
not results.
Fix: expose the scan's current candidate row bitmap to index queries
through
IndexQueryContext (the same SegmentIterator -> reader handshake channel
the
count-on-index fast path already uses):
- `IndexQueryContext::candidate_rows`: set by SegmentIterator around the
index-apply phase when the candidate bitmap is smaller than
`num_rows * inverted_index_candidate_pushdown_ratio` (new BE config,
default 0.3). Non-positive finite values disable the feature; values
above 1
or non-finite values are rejected by the config validator. The use site
checks
the domain before arithmetic. The pointer is reset on every exit path
via the
existing DEFER. `_row_bitmap` only shrinks during the applies, so
restricting
to its current state stays correct for every later conjunct.
- `RoaringDocIdIterator`: a read-only DISI adapter over the candidate
bitmap. PhraseQuery joins it into the leapfrog intersection (its
doc_freq() is the cardinality, so a small candidate naturally becomes
the
lead), while matchers keep only real term iterators -- a classic
two-phase iterator: candidates drive the approximation, terms keep the
position semantics. The single-term path is unchanged (no restriction,
same semantics).
- Query cache: only a query that actually consumes the candidate
produces a
partial bitmap and skips cache insertion. Cache lookups stay enabled --
a
cached full-segment bitmap intersected later is still correct and
cheaper.
Non-consuming queries continue filling the cache (see review round 2/3).
SNII indexes take the same candidates (added after the CLucene path
above):
- The snii::query phrase and phrase-prefix entry points accept a Roaring
candidate bitmap. After term planning, a candidate set within 8x of the
rarest term drives the docid intersection through SNII's existing
prefilter
path, so windowed postings are decoded only for windows covering
candidates;
a far larger candidate set filters the intersection result before PRX
decode, so a rare phrase never pays for every candidate.
- Phrase-prefix keeps or enables its tail-union prefilter under
candidates
when the union is cheaper than repeated leading-term candidate probes;
small candidate sets bypass it when candidate probes are cheaper.
- SniiIndexReader consumes candidates only for multi-term MATCH_PHRASE
and
MATCH_PHRASE_PREFIX, follows the same consumption-keyed cache policy,
and
keeps candidate-restricted bitmaps out of single-flight.
- SEARCH roots are evaluated without the candidate, like compound roots.
Measured effect (`PhraseCandidatePushdownBench`, committed as a
DISABLED_ UT:
one synthetic log corpus indexed through the production column writer as
CLucene V2 and as SNII, queried through the production readers with the
result
cache disabled for both lookup and insertion; RELEASE build,
1,000,000-row
segment. Each speedup is the ratio of medians from three independent
runs, with
ten thread-CPU samples per query in each run; every point asserts
restricted ==
full ∧ candidates):
| format | query | full ms | random 1% | random 10% | random 30% | range
1% | range 10% | range 30% |
|---|---|---:|---:|---:|---:|---:|---:|---:|
| SNII | exact_2 | 11.470 | 2.22x | 1.56x | 1.12x | 36.53x | 8.93x |
3.27x |
| SNII | exact_4 | 22.331 | 2.74x | 2.00x | 1.54x | 40.02x | 8.47x |
3.20x |
| SNII | prefix_2 | 3.799 | 1.28x | 1.47x | 1.11x | 11.73x | 3.45x |
2.15x |
| SNII | prefix_5 | 1.634 | 3.01x | 2.28x | 2.11x | 3.77x | 2.94x |
1.95x |
| SNII | rare_exact | 0.150 | 1.12x | 0.95x | 1.10x | 1.00x | 1.01x |
1.01x |
| V2 | exact_2 | 18.606 | 3.02x | 1.70x | 1.06x | 64.16x | 7.72x | 2.92x
|
| V2 | exact_4 | 21.953 | 2.90x | 1.59x | 1.12x | 65.14x | 9.30x | 3.19x
|
| V2 | prefix_2 | 4.584 | 3.14x | 1.54x | 1.15x | 23.39x | 7.58x | 3.11x
|
| V2 | prefix_5 | 1.529 | 2.78x | 1.40x | 1.18x | 6.51x | 4.09x | 2.14x
|
| V2 | rare_exact | 0.064 | 1.14x | 0.98x | 1.07x | 1.02x | 1.02x |
1.00x |
`range` candidates model a time range over time-sorted rows, `random` a
selective non-index predicate. The exact and prefix queries improved at
the
0.3 default in this corpus; the rare exact query stayed near break-even.
The
previous V2 rare-query speedup included a cache insertion that should
have been
disabled. The machine is shared, so small differences near 1x can move
between
runs. The earlier single-shape table (200k-doc CLucene segment, phrase
`big
red`) is superseded by this reproducible benchmark:
BUILD_TYPE_UT=RELEASE PHRASE_CANDIDATE_BENCH_DOCS=1000000 \
PHRASE_CANDIDATE_BENCH_ITERATIONS=10 GTEST_ALSO_RUN_DISABLED_TESTS=1 \
./run-be-ut.sh --run \
--filter='PhraseCandidatePushdownBench.DISABLED_RestrictedVersusFullPhrase'
-j <N>
### Release note
Inverted index: phrase and phrase-prefix queries on CLucene and SNII
indexes
now restrict doc-list intersection and position verification to the
scan's
surviving candidate rows when the candidate set is small (BE config
inverted_index_candidate_pushdown_ratio, default 0.3).
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [x] Regression test
- [x] Unit Test
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason <!-- Add your reason? -->
- Behavior changed:
- [ ] No.
- [x] Yes. <!-- Same query results; phrase evaluation cost now tracks
the candidate set. Only candidate-restricted phrase results skip
fulltext query-cache insertion. -->
- Does this need documentation?
- [x] No.
- [ ] Yes.
---
Review round 1 (automated review, addressed in the second commit):
1. Scoring norm source: `_norm_source` is pinned to the first real
postings
iterator, so BM25 norms never come from the candidate adapter. Red-first
test: under a candidate, two documents of different lengths scored
identically (2.9729729) before the fix vs. the correct distinct baseline
scores after it.
2. Engage-gate timing: the decision is extracted into
`_refresh_candidate_pushdown()` and re-evaluated after column-level
index
predicates, so an entry bitmap above the ratio that indexed predicates
shrink below it still publishes `candidate_rows` (threshold-crossing
test
added).
3. Config domain safety: validator (finite, <= 1.0) plus a use-site
`std::isfinite`/domain guard before the multiply and integer conversion.
4. Default calibration: 0.1 -> 0.3. The motivating workload keeps 22.4%
of
each segment after short-key pruning; the previous default never engaged
the pushdown for exactly that case. A finer crossover sweep is planned
as
a follow-up benchmark.
Review round 2/3 (automated review, addressed in the follow-up commits):
5. Cache policy is now keyed to actual candidate consumption: a
reply-direction
`candidate_rows_consumed` flag is set only by the candidate-joining
phrase
path and reset per search, so non-consuming queries (MATCH_ANY/ALL,
term,
regexp, single-term phrase, untokenized range) keep filling the query
cache
with their full-segment bitmaps while a candidate is engaged. Red-first
tests: cold-miss/second-hit for MATCH_ANY under a published candidate,
plus
a cross-reader stale-flag case (phrase then untokenized range).
6. Three-valued correctness: a candidate-restricted TRUE bitmap paired
with the
full-segment null bitmap could spuriously trigger VCompoundPred's AND
shortcut (NOT(A AND B) with nullable A: FALSE mis-typed as NULL, row
dropped). Compound roots are now evaluated with the candidate suppressed
in
both the conjunct and virtual-column loops; top-level single-predicate
consumption keeps the restriction (exact within the candidate). A
SQL-level
nullable-compound regression case is planned as a follow-up.
7. The `_norm_source` invariant check moved out of the per-document
scoring
loop (release-mode checks stay out of hot loops per AGENTS.md).
Update (SNII support, benchmark, regression test; rebased onto current
master):
8. Rebase fix: on current master
`segment_iterator_candidate_pushdown_test.cpp`
no longer expands `#define protected public` (the segment headers arrive
through column_reader.h first), so -Wunused-macros failed the BE UT
build;
the unused macro is removed.
9. SNII candidate pushdown, as described above. Red-first unit tests:
restricted SNII phrases returned the full-segment result, consumed
nothing,
were cached and shared through single-flight; a dense candidate set
turned
off the phrase-prefix tail-union prefilter (10,156 vs 1,143 leading
candidates decoded). The benchmark then drove two refinements: filtering
instead of driving when candidates vastly outnumber the rarest term (no
O(candidates) cost for rare phrases) and retaining affordable tail-union
prefilters under candidates.
10. Follow-ups from earlier rounds are done: the crossover benchmark
above,
and the SQL-level nullable-compound case in
`test_phrase_candidate_pushdown` (V2 and SNII tables, pushdown on, off,
and on again over cached full-segment results, plus a merge-on-write
table
with deletes).
11. Review of the SNII change: candidate suppression now checks the
whole
expression tree, so a compound predicate or SEARCH below another root
(for example `search(...) IS NOT NULL`) no longer runs its leaves under
the candidate (red-first test); the SNII streaming exact verifier and
the
repeated-term route, which fail loudly on a leftover non-candidate doc,
are
now exercised with driving and filtering candidates.
12. CLucene full-result cache insertions now use the existing
option-aware
helper in both fulltext and string readers. A disabled-cache test failed
before the fix because a later enabled query hit the entry from the
disabled run; it passed afterward. This also makes V2 benchmark samples
symmetric when the result cache is disabled.
13. The symmetric benchmark exposed an SNII phrase-prefix regression at
sparse
random candidates. A profile test showed 1,998 leading candidates under
a 10% candidate set versus 1,143 with the unrestricted tail-union
prefilter. The planner now retains that prefilter when its postings cost
no more than bounded candidate probes; the profile test passed, and
three
RELEASE runs moved `prefix_5` at 1% random candidates from 0.19–0.29x
to 2.93–3.04x. The one-candidate bypass test still passes.1 parent ef72b93 commit 47b2e1d
35 files changed
Lines changed: 4077 additions & 307 deletions
File tree
- be
- src
- common
- storage
- index
- inverted
- query
- util
- snii
- query
- internal
- segment
- test
- common
- storage
- index
- inverted/query
- snii
- bench
- query
- segment
- regression-test
- data
- inverted_index_p0
- variant_p0/predefine
- suites
- inverted_index_p0
- cloud_build_index
- variant_p0/predefine
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
24 | 24 | | |
25 | 25 | | |
26 | 26 | | |
| 27 | + | |
27 | 28 | | |
| 29 | + | |
28 | 30 | | |
29 | 31 | | |
30 | 32 | | |
| |||
1320 | 1322 | | |
1321 | 1323 | | |
1322 | 1324 | | |
| 1325 | + | |
| 1326 | + | |
| 1327 | + | |
| 1328 | + | |
| 1329 | + | |
| 1330 | + | |
| 1331 | + | |
| 1332 | + | |
| 1333 | + | |
| 1334 | + | |
| 1335 | + | |
1323 | 1336 | | |
1324 | 1337 | | |
1325 | 1338 | | |
| |||
2321 | 2334 | | |
2322 | 2335 | | |
2323 | 2336 | | |
| 2337 | + | |
| 2338 | + | |
2324 | 2339 | | |
2325 | 2340 | | |
2326 | 2341 | | |
| |||
2369 | 2384 | | |
2370 | 2385 | | |
2371 | 2386 | | |
| 2387 | + | |
| 2388 | + | |
| 2389 | + | |
| 2390 | + | |
| 2391 | + | |
| 2392 | + | |
| 2393 | + | |
2372 | 2394 | | |
2373 | 2395 | | |
2374 | 2396 | | |
2375 | 2397 | | |
2376 | 2398 | | |
2377 | | - | |
2378 | | - | |
2379 | | - | |
2380 | 2399 | | |
2381 | 2400 | | |
2382 | 2401 | | |
| |||
2394 | 2413 | | |
2395 | 2414 | | |
2396 | 2415 | | |
2397 | | - | |
| 2416 | + | |
2398 | 2417 | | |
2399 | 2418 | | |
2400 | 2419 | | |
| |||
2418 | 2437 | | |
2419 | 2438 | | |
2420 | 2439 | | |
| 2440 | + | |
| 2441 | + | |
2421 | 2442 | | |
2422 | 2443 | | |
2423 | 2444 | | |
2424 | 2445 | | |
2425 | 2446 | | |
2426 | | - | |
2427 | | - | |
2428 | | - | |
2429 | | - | |
2430 | | - | |
| 2447 | + | |
2431 | 2448 | | |
2432 | 2449 | | |
2433 | 2450 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1371 | 1371 | | |
1372 | 1372 | | |
1373 | 1373 | | |
| 1374 | + | |
| 1375 | + | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
1374 | 1380 | | |
1375 | 1381 | | |
1376 | 1382 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
48 | 48 | | |
49 | 49 | | |
50 | 50 | | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
51 | 64 | | |
52 | 65 | | |
53 | 66 | | |
| |||
66 | 79 | | |
67 | 80 | | |
68 | 81 | | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
69 | 91 | | |
70 | 92 | | |
71 | 93 | | |
72 | 94 | | |
| 95 | + | |
73 | 96 | | |
74 | 97 | | |
75 | 98 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
347 | 347 | | |
348 | 348 | | |
349 | 349 | | |
| 350 | + | |
| 351 | + | |
| 352 | + | |
| 353 | + | |
350 | 354 | | |
351 | 355 | | |
352 | 356 | | |
| |||
477 | 481 | | |
478 | 482 | | |
479 | 483 | | |
480 | | - | |
| 484 | + | |
| 485 | + | |
| 486 | + | |
| 487 | + | |
| 488 | + | |
| 489 | + | |
| 490 | + | |
481 | 491 | | |
482 | 492 | | |
483 | 493 | | |
| |||
543 | 553 | | |
544 | 554 | | |
545 | 555 | | |
| 556 | + | |
| 557 | + | |
| 558 | + | |
| 559 | + | |
546 | 560 | | |
547 | 561 | | |
548 | 562 | | |
| |||
601 | 615 | | |
602 | 616 | | |
603 | 617 | | |
604 | | - | |
| 618 | + | |
605 | 619 | | |
606 | | - | |
| 620 | + | |
| 621 | + | |
| 622 | + | |
607 | 623 | | |
608 | 624 | | |
609 | 625 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
53 | 53 | | |
54 | 54 | | |
55 | 55 | | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
56 | 64 | | |
57 | 65 | | |
58 | 66 | | |
| |||
64 | 72 | | |
65 | 73 | | |
66 | 74 | | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
67 | 81 | | |
68 | 82 | | |
69 | 83 | | |
| |||
160 | 174 | | |
161 | 175 | | |
162 | 176 | | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
163 | 182 | | |
164 | 183 | | |
165 | 184 | | |
| |||
168 | 187 | | |
169 | 188 | | |
170 | 189 | | |
171 | | - | |
| 190 | + | |
172 | 191 | | |
173 | 192 | | |
174 | 193 | | |
| |||
285 | 304 | | |
286 | 305 | | |
287 | 306 | | |
288 | | - | |
| 307 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
74 | 74 | | |
75 | 75 | | |
76 | 76 | | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
77 | 80 | | |
78 | 81 | | |
79 | 82 | | |
| |||
82 | 85 | | |
83 | 86 | | |
84 | 87 | | |
85 | | - | |
| 88 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
21 | 21 | | |
22 | 22 | | |
23 | 23 | | |
| 24 | + | |
24 | 25 | | |
25 | 26 | | |
26 | 27 | | |
27 | 28 | | |
28 | | - | |
| 29 | + | |
29 | 30 | | |
30 | 31 | | |
31 | 32 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
0 commit comments