Repository navigation
Commit 709d859
authored
[feature](inverted index) approximate gram index for LIKE/REGEXP push-down via ngram tokenizer mode=sparse|dense on SNII (apache#67538)
### What problem does this PR solve?
Issue Number: close #xxx
Related PR: #xxx
Problem Summary:
`LIKE '%literal%'` and `REGEXP` on text columns always scan every row
today. This PR adds an **approximate gram index** for them, built on the
existing inverted-index machinery, so that a regex/LIKE first prunes
rows through the index and the original expression is then re-evaluated
only on the surviving candidates. Results are always identical to the
non-indexed evaluation: the index only ever produces a superset of the
matching rows, and every index-side failure degrades to "no
acceleration".
No new index type, tokenizer type or `parser` value is introduced. The
feature is switched on by giving the built-in `ngram` tokenizer a
`mode`:
```sql
CREATE INVERTED INDEX TOKENIZER gram_sparse_tok
PROPERTIES ("type" = "ngram", "mode" = "sparse", "min_gram" = "3", "max_gram" = "4");
CREATE INVERTED INDEX ANALYZER gram_sparse PROPERTIES ("tokenizer" = "gram_sparse_tok");
CREATE TABLE logs (id BIGINT, msg STRING,
INDEX idx_msg (msg) USING INVERTED PROPERTIES ("analyzer" = "gram_sparse"))
DUPLICATE KEY(id) DISTRIBUTED BY HASH(id) BUCKETS 8
PROPERTIES ("replication_num" = "1", "inverted_index_storage_format" = "SNII");
SELECT count(*) FROM logs WHERE msg REGEXP 'rpc error: code = (Unavailable|Internal)';
```
`max_gram` only sizes the dictionary (going from 16 to 4 cuts it by
about 60 % while the posting lists stay the same), so 4 is the value to
use. `density` may be given, but is normally solved per segment (see
below).
How it works (BE):
1. **Gram library** (`be/src/storage/index/inverted/gram/`):
`GramScheme` (parameters), `GramExtractor` (ASCII runs are cut into byte
grams — a dense sliding window, or sparse content-defined grams where a
byte pair is a boundary when its 16-bit hash falls below the density —
with duplicates within a row removed), `GramQuery` (AND/OR/ALL/NONE tree
with simplification), a RE2-subset regex parser, and `RegexGramCompiler`
(Cox 2012 style derivation of the grams a match *must* contain, for both
REGEXP and LIKE).
Non-ASCII text is not indexed. A non-ASCII code point contributes no
gram and separates the ASCII runs around it, on the write side and the
query side alike, so the non-ASCII part of a literal adds no constraint
(the candidate set only ever widens) and a wholly non-ASCII pattern runs
as a plain scan. An earlier revision indexed one term per code point; on
a CJK corpus each of those terms sits in a few percent of the rows,
which is above the stop-gram line described below, so they filtered
nothing while costing most of the index, and every measured alternative
(code-point pairs, content-defined chunks of code points) pushed the
dictionary alone past the size budget of the whole index.
The compiler's one hard contract is that it never drops a matching row.
Two tests hold it: a differential fuzz test against RE2, and a property
test that walks a corpus containing ill-formed UTF-8, NUL bytes, rows
around the `max_len` boundary and 4 KiB rows across a scheme matrix
varying `mode`, `lower_case`, `min_gram`, `max_gram` and `density`,
asserting for every row the engine matches that the compiled query still
keeps it a candidate.
Where the derivation cannot be made reliably the compiler degrades to
ALL and prunes nothing: an unparsable pattern, a lookbehind assertion,
an oversized character class or set, a literal that is not well-formed
UTF-8 (its grams would not line up with how the index split the row),
and a query tree carrying more gram leaves than the configured budget.
2. **Write path**: `NGramTokenizerFactory` returns a `GramTokenizer`
when `mode` is set; gram-family analyzers are recognised by the SNII
writer, which forces a docs-only index for them (`support_phrase` is
ignored). Analyzers that carry token filters or char filters are
deliberately treated as *not* gram-family, because their terms would no
longer correspond to the raw column value. The tokenizer is reused
across rows and the buffers it retains are charged to the writer's
memory reporter. Three decisions are taken per segment, from the
segment's own rows, and recorded with it:
- **The density is solved, not configured**
(`enable_gram_index_adaptive_density`, default on). Before the first row
is cut, the writer observes the first 4 MB of the column and picks the
sparsest boundary density at which 95 % of all 12-byte windows still
contain a whole gram (`gram_index_min_literal_bytes`,
`gram_index_density_coverage_permille`,
`gram_index_density_sample_bytes`). The promise is "a literal of 12
bytes can be found", and the density that keeps it is a property of the
column, not of the tokenizer: 0.31 on English log lines, 0.18 on URL
paths, 0.22 on JSON agent logs in the corpora below. The tokenizer's
`density` is the fallback when there is nothing to observe, and
whichever value was used is written into the segment's scheme.
- **Stop-gram.** A gram present in more than 0.15 % of a segment's rows
keeps its dictionary entry, with its df, but its posting list is not
written (`DictEntry::posting_dropped`). Such a gram reads as "every
row": an AND simply leaves it out, and an OR containing one is the whole
segment. That is what the query-side cost gate would have decided for it
anyway — reading that posting list costs more than the rows it removes —
so LIKE/REGEXP lose nothing, while the index keeps its dictionary and
sheds 80–92 % of its bytes on the three ASCII corpora measured below.
The line is derived from the same digest the gate reads, not configured,
and segments below 2,000 rows keep every posting. Query types that need
exact posting lists (`MATCH`, `EQUAL`, …) are guarded at the planner and
at the reader: a dropped posting there returns
`INVERTED_INDEX_EVALUATE_SKIPPED` and the predicate falls back to
row-level evaluation, rather than reading a zero-length posting as an
empty set. A metadata directory holding such an entry declares
`required_features = 2` (`kFeatureDroppedPostings`), so a reader without
this code refuses the container as unsupported and evaluates the
predicate without the index instead of misreading the locator-less
entry.
- **High-df digest.** A gram-family segment records the df of its most
common terms (keyed by the bloom hash, a few thousand entries at most)
together with the ceiling every unrecorded term sits below. The query
side derives its candidate budget from that ceiling and estimates a
query's result before touching any dictionary block, which on remote
storage is the difference between deciding for free and paying one round
trip per gram. It costs about 0.3 % of the index size and build time
within noise; non-gram indexes carry none of it.
3. **Query path**: a new `InvertedIndexQueryType::GRAM_BOOLEAN_QUERY`
evaluates a `GramQuery` on the SNII index. `FunctionLike` /
`FunctionRegexpLike` implement `evaluate_inverted_index`: constant
pattern → compile → gram query → candidate bitmap flagged as
**approximate**. Approximate results go into a separate table in
`IndexExecContext`; `SegmentIterator` only intersects them into
`_row_bitmap` when the conjunct root is the function itself, never marks
the column as "index evaluated", and keeps the conjunct for
re-evaluation. `NOT LIKE` / `NOT REGEXP` / OR-nested predicates are
therefore never pruned — and, because their approximate result could
never be read back, the index evaluation is skipped for them altogether
rather than performed and discarded. Push-down happens only for SNII
readers; CLucene-format readers reject the new query type.
Reads are issued per query node, not per gram: one batched dictionary
resolution (concurrent waves of DICT block reads, each term first
checked against the segment's resident bloom filter) whose entries are
memoised, then one batched posting plan/fetch. On a metered reader an OR
node costs a constant number of serial read rounds instead of two per
gram. A node is given up before any posting is read when its estimated
candidate count exceeds the budget: three times the digest's ceiling,
or, on a segment without a digest, `gram_index_max_candidate_ratio_bp`
basis points of its rows (default 15) once it has at least
`gram_index_candidate_ratio_min_rows` rows. The estimate for an AND is a
damped product of its grams' selectivities rather than its rarest gram
alone, and a sub-query's estimate feeds the AND that contains it. Giving
up yields the segment's whole docid range, so it can never prune a row.
4. **Metadata**: the writer records the gram scheme it actually used —
including the density the segment settled on — in
`SniiCoreMetadataPB.gram_scheme`, and the query side compiles a pattern
against the scheme read back from the physical index it is about to
read, so the two can never disagree: a policy dropped and recreated with
different properties does not affect segments already written. Analyzed
queries (`MATCH_*`) are held to the same rule: the reader compares the
scheme the current analyzer cuts with against the segment's persisted
scheme and returns `INVERTED_INDEX_EVALUATE_SKIPPED` when they differ,
and such queries bypass the result cache, whose key carries no scheme
identity.
5. **Compaction and schema change**: gram indexes are docs-only, so the
SNII index-merge fast path does not apply. Compaction and every
data-rewriting schema change rebuild the index from the converted
column, re-solving the density and re-deciding stop-gram for the new
segment; light schema changes carry the existing index files over.
`test_gram_compaction` and `test_gram_schema_change` pin both the
answers and the pruning across a full compaction and across light and
rewriting schema changes, including a change of the indexed column's own
length and type.
FE:
- `NGramTokenizerValidator` accepts and validates `mode`
(`auto|sparse|dense`, where `auto` is `sparse`), `density` `[0.001, 1]`,
`lower_case`, and the gram-family ranges of `min_gram`/`max_gram`
(`mode` absent keeps the legacy behaviour byte for byte). Numeric
properties must be spelled in ASCII, because BE parses them with
`strtol`/`strtod`.
- `IndexPolicyMgr` rejects gram tokenizers combined with a token filter
or a char filter, mirroring the BE rule exactly (use the tokenizer's own
`lower_case=true` instead of a `lowercase` filter, because folding must
happen before gram boundaries are computed).
- `InvertedIndexUtil` requires `inverted_index_storage_format = SNII`
for gram-family indexes, rejects `support_phrase = true` and index-level
char filters, and defaults `support_phrase` to `false` (also for `CREATE
INDEX` / `ALTER TABLE ADD INDEX`).
Observability: `RowsGramIndexFiltered`, `GramIndexCandidateRows` and
`GramIndexGateGaveUp` in the scan profile; BE config
`enable_gram_index_regexp` (default `true`) is the kill switch.
Measured on four corpora (cloud mode on S3 with a 16 GB file cache, one
BE; index size is `INDEX_LENGTH / DATA_LENGTH` from
`information_schema.tables`):
| corpus | rows | index / data, stop-gram off | index / data, as shipped
|
|---|---|---|---|
| English log lines (textbench) | 3 M | 1.10 | **0.28** |
| URL paths (httplogs) | 3 M | 0.87 | **0.05** |
| JSON agent logs, mixed script | 300 K | 0.85 | **0.09** |
| Chinese short text (weibo) | 500 K | 0.05 | **0.04** |
Query wall clock, index on against index off on the same table with the
SQL cache and the condition cache disabled: a selective pattern with an
indexable literal (`context deadline exceeded`, 13 rows out of 3 M) runs
14× faster with the column in the page cache, 5× when it has to come
from the file cache and 130× when every page has to be fetched from S3;
patterns that hit 1–10 % of the rows, or whose literals yield no gram,
run at 0.83–1.11× because the gate refuses them before a posting is
read. Loading with the gram index takes 1.3–4.4× the time of loading
with no index at all, which is between parity and about a third more
than a full-text inverted index on the same column.
Known limitations of this first step: a session with
`enable_function_pushdown` on does not use this index for LIKE at all:
the scan node turns the LIKE into a storage-layer `LikeColumnPredicate`
and, on a duplicate-key or merge-on-write table (where every column
counts as a key column), drops the conjunct from the expression tree, so
nothing is left for the index to answer -- on a table without an
NGRAM_BF index that leaves the predicate with no index at all, and
REGEXP is unaffected because only `like` is offered to that path;
non-ASCII literals are not indexed, so a query on a CJK column runs as a
scan; a literal too short for the solved density to cut a gram out of it
(typically under 8 bytes, e.g. `\.exe` on URL paths) yields no gram and
runs as a scan, and short-literal workloads should use `mode=dense`;
`(?i)` needs a `lower_case=true` tokenizer (with `lower_case=false` the
pattern is evaluated without the index); LIKE with a custom `ESCAPE`,
lookbehind assertions and patterns that are not well-formed UTF-8 are
evaluated without the index; the pattern is compiled once per segment;
stop-gram is a fixed policy with no switch, and a segment's dropped
postings come back only by rebuilding it; the speed-up depends on
pattern selectivity and on how much of the column would otherwise be
read (the index cuts scanned bytes by orders of magnitude on selective
patterns; on a fully page-cached single node the wall-clock gain is
smaller).
**Downgrading a cluster that has used this feature is not supported.** A
gram tokenizer policy sets `min_gram`/`max_gram` outside the range an
older BE accepts, and an older BE rejects the analyzer with
`INVALID_ARGUMENT` ("The difference between max_gram and min_gram in
NGram Tokenizer must be less than or equal to: [ 1 ]"). After a
downgrade, any write that has to build the index for that column (stream
load, insert, compaction, schema change) fails, and queries that analyse
a query string against that analyzer (`MATCH*`, `TOKENIZE`) fail; plain
`LIKE`/`REGEXP` still return correct results by scanning. The BE itself
still starts and other columns are unaffected. A policy that sets only
`mode` is worse rather than better: an older BE accepts it and silently
tokenizes with the legacy `ngram(1, 2)` semantics instead of failing.1 parent 0c2c2d5 commit 709d859
126 files changed
Lines changed: 23225 additions & 55 deletions
File tree
- be
- benchmark
- src
- common
- core
- exec
- operator
- scan
- exprs
- function
- runtime/index_policy
- storage
- index
- inverted
- analyzer
- gram
- tokenizer/ngram
- snii
- format
- query
- reader
- writer
- segment
- test
- exprs
- function
- storage
- index
- inverted
- ananlyzer
- gram
- tokenizer
- snii
- format
- query
- writer
- segment
- build-support
- fe/fe-core/src
- main/java/org/apache/doris
- alter
- analysis
- indexpolicy
- nereids/trees/plans/commands/info
- test/java/org/apache/doris/indexpolicy
- gensrc/proto
- regression-test
- data/inverted_index_p0/gram
- suites/inverted_index_p0/gram
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 | |
|---|---|---|---|
| |||
| 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 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
31 | 31 | | |
32 | 32 | | |
33 | 33 | | |
| 34 | + | |
34 | 35 | | |
35 | 36 | | |
36 | 37 | | |
| |||
92 | 93 | | |
93 | 94 | | |
94 | 95 | | |
95 | | - | |
| 96 | + | |
96 | 97 | | |
97 | 98 | | |
98 | 99 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1346 | 1346 | | |
1347 | 1347 | | |
1348 | 1348 | | |
| 1349 | + | |
| 1350 | + | |
| 1351 | + | |
| 1352 | + | |
| 1353 | + | |
| 1354 | + | |
| 1355 | + | |
| 1356 | + | |
| 1357 | + | |
| 1358 | + | |
| 1359 | + | |
| 1360 | + | |
| 1361 | + | |
| 1362 | + | |
| 1363 | + | |
| 1364 | + | |
| 1365 | + | |
| 1366 | + | |
| 1367 | + | |
| 1368 | + | |
| 1369 | + | |
| 1370 | + | |
| 1371 | + | |
| 1372 | + | |
| 1373 | + | |
| 1374 | + | |
| 1375 | + | |
| 1376 | + | |
| 1377 | + | |
| 1378 | + | |
| 1379 | + | |
| 1380 | + | |
| 1381 | + | |
| 1382 | + | |
| 1383 | + | |
| 1384 | + | |
| 1385 | + | |
| 1386 | + | |
| 1387 | + | |
| 1388 | + | |
| 1389 | + | |
| 1390 | + | |
| 1391 | + | |
| 1392 | + | |
| 1393 | + | |
| 1394 | + | |
| 1395 | + | |
| 1396 | + | |
| 1397 | + | |
| 1398 | + | |
| 1399 | + | |
| 1400 | + | |
1349 | 1401 | | |
1350 | 1402 | | |
1351 | 1403 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
1391 | 1391 | | |
1392 | 1392 | | |
1393 | 1393 | | |
| 1394 | + | |
| 1395 | + | |
| 1396 | + | |
| 1397 | + | |
| 1398 | + | |
| 1399 | + | |
| 1400 | + | |
| 1401 | + | |
| 1402 | + | |
| 1403 | + | |
| 1404 | + | |
| 1405 | + | |
| 1406 | + | |
| 1407 | + | |
| 1408 | + | |
| 1409 | + | |
| 1410 | + | |
| 1411 | + | |
| 1412 | + | |
| 1413 | + | |
| 1414 | + | |
| 1415 | + | |
| 1416 | + | |
| 1417 | + | |
| 1418 | + | |
| 1419 | + | |
| 1420 | + | |
| 1421 | + | |
| 1422 | + | |
| 1423 | + | |
| 1424 | + | |
| 1425 | + | |
| 1426 | + | |
| 1427 | + | |
| 1428 | + | |
| 1429 | + | |
| 1430 | + | |
| 1431 | + | |
| 1432 | + | |
| 1433 | + | |
| 1434 | + | |
| 1435 | + | |
| 1436 | + | |
| 1437 | + | |
| 1438 | + | |
| 1439 | + | |
| 1440 | + | |
| 1441 | + | |
| 1442 | + | |
| 1443 | + | |
| 1444 | + | |
| 1445 | + | |
| 1446 | + | |
| 1447 | + | |
1394 | 1448 | | |
1395 | 1449 | | |
1396 | 1450 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
573 | 573 | | |
574 | 574 | | |
575 | 575 | | |
576 | | - | |
577 | 576 | | |
578 | 577 | | |
579 | 578 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
300 | 300 | | |
301 | 301 | | |
302 | 302 | | |
| 303 | + | |
| 304 | + | |
| 305 | + | |
| 306 | + | |
| 307 | + | |
| 308 | + | |
303 | 309 | | |
304 | 310 | | |
305 | 311 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
272 | 272 | | |
273 | 273 | | |
274 | 274 | | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
275 | 279 | | |
276 | 280 | | |
277 | 281 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
877 | 877 | | |
878 | 878 | | |
879 | 879 | | |
| 880 | + | |
| 881 | + | |
| 882 | + | |
880 | 883 | | |
881 | 884 | | |
882 | 885 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
216 | 216 | | |
217 | 217 | | |
218 | 218 | | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
219 | 228 | | |
220 | 229 | | |
221 | 230 | | |
| |||
507 | 516 | | |
508 | 517 | | |
509 | 518 | | |
| 519 | + | |
| 520 | + | |
| 521 | + | |
| 522 | + | |
510 | 523 | | |
511 | 524 | | |
512 | 525 | | |
| |||
0 commit comments