airborne12 opened a new pull request, #67538:
URL: https://github.com/apache/doris/pull/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" = "16", "density" = "0.25");
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)';
```
How it works (BE):
1. **Gram library** (`be/src/storage/index/inverted/gram/`): `GramScheme`
(parameters), `GramExtractor` (ASCII runs are cut into byte grams — dense
sliding window or sparse content-defined-boundary grams, `density` selects
boundary probability — while every non-ASCII code point becomes its own 1-gram,
so CJK text works without a language tokenizer), `GramQuery` (AND/OR/ALL/NONE
tree with simplification and a text serialization), a RE2-subset regex parser,
and `RegexGramCompiler` (Cox 2012 style derivation of the grams a match *must*
contain, for both REGEXP and LIKE). A differential fuzz test checks the
compiler against RE2 over hundreds of thousands of random pattern/text pairs
and asserts it never drops a matching row.
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.
3. **Query path**: a new `InvertedIndexQueryType::GRAM_BOOLEAN_QUERY`
evaluates a serialized `GramQuery` on the SNII index (df-first AND with early
exit, OR union). `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.
Push-down happens only for SNII readers; CLucene-format readers reject the new
query type.
4. **Metadata**: `SniiCoreMetadataPB.gram_scheme` is reserved
(encoded/decoded, not yet written) for a later per-segment adaptive mode.
FE:
- `NGramTokenizerValidator` accepts and validates `mode`
(`auto|sparse|dense`), `density` `[0.001, 1]`, `stop_gram_df` `[0, 1]`,
`lower_case`, and the gram-family ranges of `min_gram`/`max_gram` (`mode`
absent keeps the legacy behaviour byte for byte).
- `IndexPolicyMgr` rejects gram tokenizers combined with token filters (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` and `GramIndexCandidateRows` in the
scan profile; BE config `enable_gram_index_regexp` (default `true`) is the kill
switch.
Known limitations of this first step: `mode=auto` currently behaves as
`sparse`; `stop_gram_df` is validated and persisted but does not prune
high-frequency grams yet; `(?i)` patterns and LIKE with a custom `ESCAPE` are
evaluated without the index; 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).
### Release note
Regex / LIKE predicates on text columns can be accelerated by an inverted
index built with the `ngram` tokenizer in `mode=sparse|dense` (SNII storage
format). Query results are unchanged; unsupported patterns fall back to the
normal evaluation.
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [x] Regression test (`inverted_index_p0/gram/test_gram_regexp_like`:
139 REGEXP/RLIKE/LIKE/NOT/compound queries compared with the index enabled and
disabled, before and after DELETE, across two rowsets and three coexisting
indexes on one column; profile asserts the gram index pruned rows)
- [x] Unit Test (BE: gram scheme/extractor/query/regex AST/compiler +
differential fuzz vs RE2, tokenizer, SNII writer gram family, core metadata,
gram boolean query incl. an end-to-end test over a real SNII segment vs brute
force, like/regexp index evaluation, IndexExecContext isolation; FE:
PolicyValidatorTests, GramDdlValidationTest, InvertedIndexPropertiesTest)
- [ ] 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. New `ngram` tokenizer properties (`mode`, `density`,
`stop_gram_df`, `lower_case`); new `GRAM_BOOLEAN_QUERY` inverted index query
type; `LIKE`/`REGEXP` may use a gram-family SNII index (results unchanged); new
BE config `enable_gram_index_regexp`; new profile counters
`RowsGramIndexFiltered` / `GramIndexCandidateRows`. Existing `ngram` tokenizers
without `mode` are unaffected.
- Does this need documentation?
- [ ] No.
- [x] Yes. <!-- Add document PR link here. eg:
https://github.com/apache/doris-website/pull/1214 -->
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label <!-- Add branch pick label that this PR should
merge into -->
🤖 Generated with [Claude Code](https://claude.com/claude-code)
https://claude.ai/code/session_01METuP3aVRn8dfCU62PivnF
--
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]
