Repository navigation
Commit 14fde1c
authored
[refactor](be) Unify MATCH and SEARCH execution across inverted index formats (apache#68758)
### What problem does this PR solve?
Issue Number: None
Related PR: apache#67180, apache#67538, apache#67918
Problem Summary:
MATCH and SEARCH each had their own Boolean, phrase, term-expansion and
scoring executors, written separately for CLucene (V1/V2) and SNII
indexes. Every query optimization had to be implemented once per
executor, the formats drifted apart in behavior, and cross-field queries
could mix document IDs from different physical partitions.
This PR runs both on one engine:
- **One logical form.** MATCH (`query/logical`) and SEARCH
(`exprs/function/search`) lower their queries to the same logical nodes.
- **One query engine.** Boolean logic (AND/OR/NOT, minimum_should_match,
WAND), term expansion (prefix, wildcard, regexp), exact and sloppy
phrases and BM25 scoring are implemented once, independent of the index
format.
- **Formats behind an SPI.** CLucene and SNII only provide dictionaries,
postings, positions, norms, statistics and batched I/O through
`query/spi`. The old per-format executors are removed.
- **Layered source tree.** `be/src/storage/index/` is reorganized by
layer, and `build-support/check-header-deps.py` enforces the allowed
include directions.
Index formats and writers are unchanged, and existing indexes remain
readable. FE is unchanged.
#### Source layout
```text
be/src/storage/index/
├── index_*.h/.cpp shared index files: file reader/writer, compound reader, storage formats
├── ann/ bloom_filter/ zone_map/
└── inverted/
├── analysis/ analyzers, tokenizers, char and token filters, normalizers, gram schemes
├── common/ descriptors, caches, statistics, profiles, single flight
├── reader/ text index reader, index selection, collection statistics
├── query/ format-independent query engine
│ ├── logical/ MATCH lowering and logical nodes (gram/ builds gram queries)
│ ├── engine/ Query/Weight/Scorer: boolean, term, phrase, expansion, WAND, union, collect
│ ├── exec/ doc-id sets and sinks, term waves, chained conjunctions
│ ├── phrase/ exact and sloppy phrase matchers
│ ├── scoring/ BM25
│ └── spi/ the source interface each format implements
├── clucene/ CLucene (V1/V2) reader, searcher, writer, compaction
│ └── spi/ CLucene index source and postings cursor
└── snii/ SNII: format/, encoding/, io/, bkd/, reader/, writer/, compaction/, query/
be/src/exprs/
├── vsearch.h/.cpp VSearchExpr, the SEARCH expression node
└── function/search/
├── function_search.* SEARCH entry: Boolean assembly, DSL result cache, NULL handling
├── search_lowering.* SEARCH DSL to logical nodes; binds each field to an index
├── function_search_leaf.* compiles each leaf into a query on its bound index
├── search_predicate_collector.* collects scored leaves for BM25 statistics
└── variant_inverted_index_search.* SEARCH on VARIANT subcolumns and NESTED groups
```
#### Performance
The 18 production SQL cases (V2 and SNII: point, range, absent-term and
phrase queries) were compared with master on fresh dual-BE pairs: 8
pairs, 16 samples per case and binary, alternating order. Every case is
within the 5% limit for both `InvertedIndexFilterTime` and client wall
time; the largest ratios are 1.032 and 1.038. SNII phrase cases take
25-60% less FilterTime. TPC-H, TPC-DS and ClickBench are within noise.
<details><summary>Per-case median ratios (PR / master)</summary>
Run on 2026-10-14 against master 7ac0eb2 on a busy shared host
(median 90% CPU), which widens the intervals; all 4,608 result checks
pass.
| Case | FilterTime | Client wall |
| --- | ---: | ---: |
| `v2/long/early/full` | 1.030 | 1.024 |
| `v2/long/early/range` | 1.018 | 0.999 |
| `v2/long/absent/full` | 1.032 | 1.014 |
| `v2/long/absent/range` | 1.018 | 0.995 |
| `v2/long/mid/full` | 1.006 | 1.038 |
| `v2/long/mid/range` | 1.013 | 1.012 |
| `v2/short/tiny` | 0.965 | 1.018 |
| `v2/search/scored_phrase` | 1.010 | 0.990 |
| `v2/search/phrase_2` | 0.954 | 0.951 |
| `snii/long/early/full` | 0.950 | 0.994 |
| `snii/long/early/range` | 0.961 | 1.022 |
| `snii/long/absent/full` | 0.728 | 0.847 |
| `snii/long/absent/range` | 0.891 | 0.983 |
| `snii/long/mid/full` | 0.821 | 0.924 |
| `snii/long/mid/range` | 0.975 | 1.007 |
| `snii/short/tiny` | 1.020 | 0.985 |
| `snii/search/scored_phrase` | 0.404 | 0.971 |
| `snii/search/phrase_2` | 0.746 | 0.986 |
</details>1 parent 8f838a8 commit 14fde1c
1,013 files changed
Lines changed: 40483 additions & 35219 deletions
File tree
- .github
- be
- benchmark
- src
- cloud
- exec
- operator
- scan
- exprs
- function
- array
- search
- load
- channel
- delta_writer
- runtime
- index_policy
- storage
- compaction
- index
- ann
- inverted
- analysis
- analyzer
- basic
- icu
- ik
- cfg
- core
- dic
- kuromoji
- dict
- char_filter
- gram
- normalizer
- token_filter
- tokenizer
- basic
- char
- empty
- icu
- ik
- keyword
- ngram
- pinyin
- standard
- clucene
- spi
- common
- query_v2
- boolean_query
- collect
- phrase_prefix_query
- phrase_query
- prefix_query
- regexp_query
- scored_bit_set_query
- wildcard_query
- query
- engine
- all_query
- bit_set_query
- boolean_query
- collect
- const_score_query
- expand_query
- phrase_prefix_query
- phrase_query
- postings
- term_query
- union
- wand
- exec
- logical
- gram
- phrase_query
- phrase
- scoring
- spi
- reader
- snii
- bkd
- common
- compaction
- encoding
- format
- io
- query
- internal
- reader
- writer
- util
- snii
- io
- query
- internal
- predicate
- rowset
- schema_change
- segment
- tablet
- task
- tools
- test
- exec/scan
- exprs
- function
- search
- runtime/index_policy
- storage
- index
- ann
- inverted
- analysis
- analyzer
- kuromoji
- char_filter
- gram
- token_filter
- tokenizer
- clucene/compaction
- util
- common
- query_v2
- query
- engine
- boolean_query
- exec
- logical/gram
- phrase_query
- phrase
- scoring
- spi
- reader
- snii
- bench
- bkd
- common
- compaction
- encoding
- format
- io
- query
- reader
- stats
- writer
- util
- snii
- bench
- io
- query
- predicate
- rowset
- segment
- tablet
- variant
- testutil
- build-support
- compile-bench
- tests
- regression-test
- data
- inverted_index_p0
- search
- suites
- inverted_index_p0
- search
Some content is hidden
Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
8 | 8 | | |
9 | 9 | | |
10 | 10 | | |
11 | | - | |
| 11 | + | |
12 | 12 | | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
25 | 25 | | |
26 | 26 | | |
27 | 27 | | |
28 | | - | |
29 | | - | |
| 28 | + | |
30 | 29 | | |
31 | 30 | | |
32 | 31 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
126 | 126 | | |
127 | 127 | | |
128 | 128 | | |
129 | | - | |
| 129 | + | |
130 | 130 | | |
131 | 131 | | |
132 | 132 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
369 | 369 | | |
370 | 370 | | |
371 | 371 | | |
372 | | - | |
| 372 | + | |
373 | 373 | | |
374 | 374 | | |
375 | 375 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
75 | 75 | | |
76 | 76 | | |
77 | 77 | | |
78 | | - | |
| 78 | + | |
79 | 79 | | |
80 | 80 | | |
81 | 81 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
24 | 24 | | |
25 | 25 | | |
26 | 26 | | |
27 | | - | |
| 27 | + | |
28 | 28 | | |
29 | 29 | | |
30 | 30 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
33 | 33 | | |
34 | 34 | | |
35 | 35 | | |
36 | | - | |
| 36 | + | |
37 | 37 | | |
38 | 38 | | |
39 | 39 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
51 | 51 | | |
52 | 52 | | |
53 | 53 | | |
54 | | - | |
| 54 | + | |
55 | 55 | | |
56 | 56 | | |
57 | 57 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
46 | 46 | | |
47 | 47 | | |
48 | 48 | | |
49 | | - | |
| 49 | + | |
50 | 50 | | |
51 | 51 | | |
52 | 52 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
372 | 372 | | |
373 | 373 | | |
374 | 374 | | |
375 | | - | |
376 | 375 | | |
377 | 376 | | |
378 | 377 | | |
| |||
0 commit comments