Skip to content

Commit 709d859

Browse files
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

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.
Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#pragma once
19+
20+
#include <benchmark/benchmark.h>
21+
22+
#include <cstdint>
23+
#include <string>
24+
#include <string_view>
25+
#include <vector>
26+
27+
#include "storage/index/inverted/gram/gram_extractor.h"
28+
29+
namespace doris::segment_v2::gram::benchmark_detail {
30+
31+
// Fixed corpora make repeated builds directly comparable. Corpus 0 has many distinct
32+
// ASCII grams, 1 represents repetitive log messages, and 2 includes UTF-8 boundaries.
33+
inline std::string make_row(size_t size, int64_t corpus) {
34+
std::string row;
35+
row.reserve(size);
36+
if (corpus == 0) {
37+
uint64_t seed = 0x67538;
38+
constexpr std::string_view alphabet =
39+
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 :_=/.-";
40+
while (row.size() < size) {
41+
seed = seed * 6364136223846793005ULL + 1442695040888963407ULL;
42+
row.push_back(alphabet[(seed >> 32) % alphabet.size()]);
43+
}
44+
return row;
45+
}
46+
const std::string_view chunk =
47+
corpus == 1 ? "2026-09-06 INFO rpc request completed service=Frontend latency_ms=17 "
48+
: "2026-09-06 INFO 查询完成 service=Frontend 手机日志 latency_ms=17 ";
49+
while (row.size() + chunk.size() <= size) {
50+
row.append(chunk);
51+
}
52+
row.append(size - row.size(), 'x');
53+
return row;
54+
}
55+
56+
inline uint64_t gram_digest(const std::vector<std::string_view>& grams) {
57+
uint64_t hash = 14695981039346656037ULL;
58+
for (auto gram : grams) {
59+
for (unsigned char byte : gram) {
60+
hash = (hash ^ byte) * 1099511628211ULL;
61+
}
62+
hash = (hash ^ 0xFF) * 1099511628211ULL;
63+
}
64+
return hash;
65+
}
66+
67+
// fresh=0 reuses one extractor and its output buffer across rows, as the index writers do;
68+
// fresh=1 constructs both for every row, a synthetic measure of per-row construction and
69+
// allocation cost. Scheme fields other than mode and lower_case keep the GramScheme defaults
70+
// in gram_scheme.h. This measures tokenization, not SQL throughput.
71+
inline void GramExtraction(benchmark::State& state) {
72+
GramScheme scheme;
73+
scheme.mode = state.range(1) == 0 ? GramMode::DENSE : GramMode::SPARSE;
74+
scheme.lower_case = state.range(2) != 0;
75+
const std::string row = make_row(state.range(0), state.range(3));
76+
GramExtractor reused(scheme);
77+
std::vector<std::string_view> grams;
78+
reused.extract(row, &grams);
79+
state.SetLabel("digest=" + std::to_string(gram_digest(grams)));
80+
state.counters["grams_per_row"] = static_cast<double>(grams.size());
81+
82+
for ([[maybe_unused]] auto _ : state) {
83+
if (state.range(4) != 0) {
84+
GramExtractor fresh(scheme);
85+
std::vector<std::string_view> fresh_grams;
86+
fresh.extract(row, &fresh_grams);
87+
benchmark::DoNotOptimize(fresh_grams);
88+
benchmark::ClobberMemory();
89+
} else {
90+
reused.extract(row, &grams);
91+
benchmark::DoNotOptimize(grams);
92+
benchmark::ClobberMemory();
93+
}
94+
}
95+
state.SetBytesProcessed(state.iterations() * static_cast<int64_t>(row.size()));
96+
state.SetItemsProcessed(state.iterations());
97+
}
98+
99+
BENCHMARK(GramExtraction)
100+
->ArgsProduct({{128, 4096, 65536, 1048576}, {0, 1}, {0, 1}, {0, 1, 2}, {0, 1}})
101+
->ArgNames({"bytes", "sparse", "lower_case", "corpus", "fresh"});
102+
103+
} // namespace doris::segment_v2::gram::benchmark_detail

‎be/benchmark/benchmark_main.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -31,6 +31,7 @@
3131
#include "benchmark_column_array_view_distance.hpp"
3232
#include "benchmark_fastunion.hpp"
3333
#include "benchmark_fmod.hpp"
34+
#include "benchmark_gram_extractor.hpp"
3435
#include "benchmark_hll_merge.hpp"
3536
#include "benchmark_hybrid_set.hpp"
3637
#include "benchmark_json_extract.hpp"
@@ -92,7 +93,7 @@ static void Example1(benchmark::State& state) {
9293
state.ResumeTiming();
9394

9495
// do test
95-
for (auto _ : state) {
96+
for ([[maybe_unused]] auto _ : state) {
9697
auto str_col = ColumnString::create();
9798
for (auto& v : vals) {
9899
str_col->insert_data(v.data(), v.size());

‎be/src/common/config.cpp‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1346,6 +1346,58 @@ double get_inverted_index_candidate_pushdown_ratio() {
13461346
// inverted index match bitmap cache size
13471347
DEFINE_String(inverted_index_query_cache_limit, "10%");
13481348

1349+
namespace {
1350+
1351+
bool valid_gram_index_candidate_ratio(int32_t value) {
1352+
return value >= 0;
1353+
}
1354+
1355+
bool valid_gram_index_candidate_min_rows(int32_t value) {
1356+
return value >= 0;
1357+
}
1358+
1359+
bool valid_gram_index_min_literal_bytes(int32_t value) {
1360+
return value >= 1;
1361+
}
1362+
1363+
// A share of windows: (0, 1000]. 0 would ask for nothing and a negative value used to reach
1364+
// the writer's checked cast and fail every gram-index load until the config was repaired.
1365+
bool valid_gram_index_density_coverage_permille(int32_t value) {
1366+
return value >= 1 && value <= 1000;
1367+
}
1368+
1369+
bool valid_gram_index_density_sample_bytes(int64_t value) {
1370+
return value >= 0;
1371+
}
1372+
1373+
} // namespace
1374+
1375+
// Whether LIKE/REGEXP tries to compile a constant pattern into a gram boolean query pushed down
1376+
// to a gram-family inverted index (master switch).
1377+
DEFINE_mBool(enable_gram_index_regexp, "true");
1378+
1379+
// Cost gate for the gram boolean query: give up pruning above this share (in basis points) of a
1380+
// segment's rows, and only on segments of at least this many rows. Giving up returns the segment's
1381+
// whole docid range, so it can never drop a candidate row.
1382+
DEFINE_mInt32(gram_index_max_candidate_ratio_bp, "15");
1383+
DEFINE_Validator(gram_index_max_candidate_ratio_bp, valid_gram_index_candidate_ratio);
1384+
DEFINE_mInt32(gram_index_candidate_ratio_min_rows, "65536");
1385+
1386+
// On by default: a configured density is wrong on every column but the one it was chosen for,
1387+
// and the solve costs one pass over a bounded sample.
1388+
DEFINE_mBool(enable_gram_index_adaptive_density, "true");
1389+
// 12 bytes at 95% of windows. Both are the promise rather than a tuning pair -- what a user
1390+
// may reasonably change is how short a literal they expect to find, not the boundary rate.
1391+
// A literal shorter than the scheme's max_gram cannot hold a whole gram, so the writer
1392+
// raises the promise to max_gram where a tokenizer sets a longer one.
1393+
DEFINE_mInt32(gram_index_min_literal_bytes, "12");
1394+
DEFINE_mInt32(gram_index_density_coverage_permille, "950");
1395+
DEFINE_mInt64(gram_index_density_sample_bytes, "4194304");
1396+
DEFINE_Validator(gram_index_candidate_ratio_min_rows, valid_gram_index_candidate_min_rows);
1397+
DEFINE_Validator(gram_index_min_literal_bytes, valid_gram_index_min_literal_bytes);
1398+
DEFINE_Validator(gram_index_density_coverage_permille, valid_gram_index_density_coverage_permille);
1399+
DEFINE_Validator(gram_index_density_sample_bytes, valid_gram_index_density_sample_bytes);
1400+
13491401
// condition cache limit
13501402
DEFINE_Int16(condition_cache_limit, "512");
13511403

‎be/src/common/config.h‎

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1391,6 +1391,60 @@ DECLARE_String(inverted_index_query_cache_limit);
13911391
// it affects only writers created after the transition and never changes query/cache semantics.
13921392
// Release-calibrated query-planner coefficients. Both remain mutable for controlled recalibration.
13931393

1394+
// Whether LIKE/REGEXP tries to compile a constant pattern into a gram boolean query pushed down
1395+
// to a gram-family inverted index (master switch). Turning it off behaves as if the index did
1396+
// not exist -- it only gives up the speedup, it never changes query results.
1397+
//
1398+
// A pattern is compiled against the gram scheme the segment itself carries, read back from the
1399+
// core metadata of the physical index the query is about to read, so the scheme can never
1400+
// disagree with the one the writer used -- a policy that was dropped and recreated with different
1401+
// properties does not affect segments already written.
1402+
DECLARE_mBool(enable_gram_index_regexp);
1403+
1404+
// Cost gate for the gram boolean query, in basis points (1/10000) of a segment's rows: give up
1405+
// pruning once the candidate set is larger than that share. 0 disables the gate, 10000 or more can
1406+
// never fire. This is a COST switch, never a semantic one -- a gram index only produces a superset
1407+
// of the candidate rows and the expression above re-verifies each of them, so giving up means the
1408+
// query returns the whole docid range of the segment and prunes nothing. It can therefore only
1409+
// cost speed, never correctness, whatever value it is set to.
1410+
//
1411+
// The unit is basis points rather than percent because the useful range is far below one percent.
1412+
// Pruning only pays when the surviving candidates are sparse enough that whole pages of the column
1413+
// can be skipped: with B rows per remote read unit and candidates spread uniformly, the fraction of
1414+
// units still touched is 1 - (1 - C/N)^B, which is already ~1 by C/N = 1%. Measured on a 34.46M row
1415+
// httplogs table against remote object storage, cold-read speedup by candidate count was 14.1x at
1416+
// 2 candidates, 5.5x at 128, 1.5x at 25K, 1.2x at 46K, and turned into a regression from 56K
1417+
// upwards, bottoming out at 0.70x. 15 bp (0.15%) is the largest share that admitted no regression
1418+
// in that sweep while keeping every double-digit win.
1419+
DECLARE_mInt32(gram_index_max_candidate_ratio_bp);
1420+
1421+
// Row floor below which the candidate ratio gate above is not applied at all. A small segment's
1422+
// entire gram index is a few KB and one or two requests, so giving up there saves nothing
1423+
// measurable while throwing away the pruning the index really does deliver; the ratio only starts
1424+
// to mean something at a size where the skipped index IO can outweigh the rows it stops
1425+
// eliminating. The default is one Roaring container's worth of rows (65536). 0 applies the ratio
1426+
// at every segment size.
1427+
DECLARE_mInt32(gram_index_candidate_ratio_min_rows);
1428+
1429+
// Adaptive gram density: solve the boundary rate from each segment's own bytes instead of
1430+
// taking the rate configured on the tokenizer.
1431+
//
1432+
// A configured rate cannot mean the same thing on two columns. Measured at a nominal 0.25 the
1433+
// realised grams per byte were 0.204 on log text, 0.287 on URL paths and 0.182 on agent
1434+
// traces, and the coverage it bought ranged from 91.7% of 12-byte literals to 98.9% -- under
1435+
// serving one column while overpaying on another, in every posting list. Solving instead
1436+
// makes the promise the constant and the rate the variable.
1437+
DECLARE_mBool(enable_gram_index_adaptive_density);
1438+
// The promise the solve keeps, not a tuning pair: literals of at least this many bytes are
1439+
// findable, for this share of the column's own windows of that length. Both are dimensionless
1440+
// and the same on every dataset; what varies is the density they resolve to.
1441+
DECLARE_mInt32(gram_index_min_literal_bytes);
1442+
DECLARE_mInt32(gram_index_density_coverage_permille);
1443+
// How much of a segment is held back to solve on. The sample is buffered rather than
1444+
// tokenized, so this is a transient memory cost and a bound on how long the write path waits
1445+
// before it can cut anything; the histogram behind the solve is a fixed 256 KB regardless.
1446+
DECLARE_mInt64(gram_index_density_sample_bytes);
1447+
13941448
// condition cache limit
13951449
DECLARE_Int16(condition_cache_limit);
13961450

‎be/src/core/types.h‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -573,7 +573,6 @@ struct NativeType<Decimal256> {
573573
using Type = wide::Int256;
574574
};
575575

576-
// NOLINTEND(readability-function-size)
577576
} // namespace doris
578577

579578
/// Specialization of `std::hash` for the Decimal<T> types.

‎be/src/exec/operator/olap_scan_operator.cpp‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -300,6 +300,12 @@ Status OlapScanLocalState::_init_profile() {
300300
ADD_COUNTER_WITH_LEVEL(_segment_profile, "InvertedIndexDowngradeCount", TUnit::UNIT, 1);
301301
_inverted_index_conjuncts_short_circuited_counter = ADD_COUNTER_WITH_LEVEL(
302302
_segment_profile, "InvertedIndexConjunctsShortCircuited", TUnit::UNIT, 1);
303+
_gram_index_filter_counter =
304+
ADD_COUNTER_WITH_LEVEL(_segment_profile, "RowsGramIndexFiltered", TUnit::UNIT, 1);
305+
_gram_index_candidate_counter =
306+
ADD_COUNTER_WITH_LEVEL(_segment_profile, "GramIndexCandidateRows", TUnit::UNIT, 1);
307+
_gram_index_gate_gave_up_counter =
308+
ADD_COUNTER_WITH_LEVEL(_segment_profile, "GramIndexGateGaveUp", TUnit::UNIT, 1);
303309
_inverted_index_analyzer_timer =
304310
ADD_TIMER_WITH_LEVEL(_segment_profile, "InvertedIndexAnalyzerTime", 1);
305311
_inverted_index_lookup_timer =

‎be/src/exec/operator/olap_scan_operator.h‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -272,6 +272,10 @@ class OlapScanLocalState final : public ScanLocalState<OlapScanLocalState> {
272272
RuntimeProfile::Counter* _inverted_index_searcher_cache_miss_counter = nullptr;
273273
RuntimeProfile::Counter* _inverted_index_downgrade_count_counter = nullptr;
274274
RuntimeProfile::Counter* _inverted_index_conjuncts_short_circuited_counter = nullptr;
275+
// Approximate (gram) index: rows pruned / candidate rows left for expression re-verification.
276+
RuntimeProfile::Counter* _gram_index_filter_counter = nullptr;
277+
RuntimeProfile::Counter* _gram_index_candidate_counter = nullptr;
278+
RuntimeProfile::Counter* _gram_index_gate_gave_up_counter = nullptr;
275279
RuntimeProfile::Counter* _inverted_index_analyzer_timer = nullptr;
276280
RuntimeProfile::Counter* _inverted_index_lookup_timer = nullptr;
277281

‎be/src/exec/scan/olap_scanner.cpp‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -877,6 +877,9 @@ void OlapScanner::_collect_profile_before_close() {
877877
stats.inverted_index_downgrade_count);
878878
COUNTER_UPDATE(local_state->_inverted_index_conjuncts_short_circuited_counter,
879879
stats.inverted_index_conjuncts_short_circuited);
880+
COUNTER_UPDATE(local_state->_gram_index_filter_counter, stats.rows_gram_index_filtered);
881+
COUNTER_UPDATE(local_state->_gram_index_candidate_counter, stats.gram_index_candidate_rows);
882+
COUNTER_UPDATE(local_state->_gram_index_gate_gave_up_counter, stats.gram_index_gate_gave_up);
880883
COUNTER_UPDATE(local_state->_inverted_index_analyzer_timer,
881884
stats.inverted_index_analyzer_timer);
882885
COUNTER_UPDATE(local_state->_inverted_index_lookup_timer, stats.inverted_index_lookup_timer);

‎be/src/exprs/function/function.h‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -216,6 +216,15 @@ class IFunctionBase {
216216
}
217217
}
218218

219+
// True when this function's index push-down can only ever answer with an approximate
220+
// (superset) candidate set instead of the exact row set. Such a result is usable in one
221+
// place only -- narrowing the candidate rows of a conjunct that stays pushed down for
222+
// row-level re-verification -- so VExpr skips the push-down entirely wherever it would be
223+
// computed and then dropped, rather than paying for the index reads first.
224+
virtual bool index_result_is_approximate() const { return false; }
225+
226+
// VExpr calls this after binding the indexed fields to storage-compatible types and
227+
// iterators; the arguments carry the call's literals, in child order.
219228
virtual Status evaluate_inverted_index(
220229
const ColumnsWithTypeAndName& arguments,
221230
const std::vector<IndexFieldNameAndTypePair>& data_type_with_names,
@@ -507,6 +516,10 @@ class DefaultFunction final : public IFunctionBase {
507516
return function->close(context, scope);
508517
}
509518

519+
bool index_result_is_approximate() const override {
520+
return function->index_result_is_approximate();
521+
}
522+
510523
Status evaluate_inverted_index(
511524
const ColumnsWithTypeAndName& args,
512525
const std::vector<IndexFieldNameAndTypePair>& data_type_with_names,

0 commit comments

Comments
 (0)