github-actions[bot] commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r3984903500
##########
be/src/storage/index/snii/snii_index_reader.cpp:
##########
@@ -402,6 +408,33 @@ Status execute_snii_query(const
::doris::snii::reader::LogicalIndexReader& logic
max_expansions);
emitted_to_sink = true;
break;
+ case InvertedIndexQueryType::LIKE_GRAM_QUERY:
+ case InvertedIndexQueryType::REGEXP_GRAM_QUERY: {
+ // Compile against the same physical dictionary that supplies the
postings. Current
+ // policies can differ from the scheme that was used when this segment
was written.
+ const auto& scheme = logical_reader.gram_scheme();
Review Comment:
[P1] Handle MATCH against each segment's persisted scheme. Adaptive
calibration mutates and persists a per-segment density, but MATCH terms are
still parsed with the unchanged current policy analyzer; different CDC
boundaries can therefore make an exact index bitmap omit rows that scalar MATCH
(current analyzer on both value and query) returns. Recovery creates the same
mismatch deterministically with old dense-3/new dense-4 rowsets, while only
LIKE/REGEXP use `logical_reader.gram_scheme()`. The cache lookup also precedes
the reader and omits analyzer/scheme identity. Please skip/recheck MATCH when
schemes differ (including cache handling), and add indexed/unindexed parity for
calibrated and recovered mixed segments.
##########
be/src/storage/index/snii/snii_index_writer.cpp:
##########
@@ -44,13 +46,97 @@
SniiIndexColumnWriter::SniiIndexColumnWriter(IndexFileWriter* index_file_writer,
_index_meta(index_meta),
_is_char(value_type == FieldType::OLAP_FIELD_TYPE_CHAR) {}
+// Gram-family detection (Rulings R21/R22): the scheme comes only from the
single analyzer
+// provider the writer created itself -- the same provider both produces the
actual tokenizer and
+// answers "am I gram family?", so the two cannot drift. A built-in analyzer
+// (standard/english/...) goes through BuiltinAnalyzerProvider and the base
class default, which
+// is always nullopt, and the policy manager is never consulted (consulting it
would throw
+// "Policy not found" and make every built-in-analyzer index impossible to
build).
+void SniiIndexColumnWriter::_apply_gram_family_scheme(
+ const inverted_index::AnalyzerProviderPtr& analyzer_provider) {
+ if (analyzer_provider != nullptr) {
+ _gram_scheme = analyzer_provider->gram_scheme();
+ }
+ // An index-level char_filter is wrapped around the reader by the writer
itself
+ // (create_reader) and is invisible to the provider: once one exists, the
stored term is no
+ // longer equal to GramExtractor.extract(raw column value), breaking the
row invariant the
+ // query side (phase C) relies on, so this is treated as "not gram family"
(fail-safe, for
+ // the same reason as R22).
+ if (!_analyzer_config.char_filter_map.empty()) {
+ _gram_scheme.reset();
+ }
+ DCHECK(!_gram_scheme.has_value() || _should_analyzer);
+ if (!_gram_scheme.has_value() || !_has_positions) {
+ return;
+ }
+ // R15: a gram-family hit forces a degradation to docs-only (the gram
index does not support
+ // phrase positions), and it has to happen before SpimiTermBuffer is fixed
by _has_positions.
+ LOG(INFO) << "gram-family analyzer forces docs-only index, ignoring
support_phrase for index "
+ << _index_meta->index_id();
+ _has_positions = false;
+ _config = ::doris::snii::format::IndexConfig::kDocsOnly;
+}
+
+// Arms the density solve for this segment. The configured density stays as
the fallback: it is
+// what a segment gets when the feature is off, when the sample carries no
window of the
+// promised length, or when nothing at all is written.
+void SniiIndexColumnWriter::_arm_density_calibration() {
+ if (!_gram_scheme.has_value() ||
!config::enable_gram_index_adaptive_density) {
Review Comment:
[P2] Avoid arming density calibration for `DENSE` schemes. Density is
consulted only by the sparse extractor, but this currently makes every dense
writer copy and retain the default 4 MiB sample, update the histogram, and
replay all held rows before emitting terms. With many concurrent tablet/index
writers that is avoidable per-writer memory and CPU for a mode whose output
cannot change. Please restrict calibration to sparse (or a genuinely unresolved
auto mode) and cover dense writers with a no-sampling test.
##########
be/test/storage/index/snii/writer/high_df_digest_cost_test.cpp:
##########
@@ -0,0 +1,178 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// What does building the high-df digest cost the writer?
+//
+// The digest earns its keep on the query side -- it lets the cost gate bound
a node without
+// the remote dictionary reads that were measured at 40 seconds on a cold
segment. That is
+// only a good trade if writing it is close to free, and "close to free" has
to be a number
+// rather than an assertion.
+//
+// The two builds below index the identical corpus with the identical settings
and differ in
+// exactly one field: whether a gram scheme is present, which is what decides
that a digest
+// is built at all. Everything else -- postings, dictionary blocks, term
hashes, statistics
+// -- is byte-for-byte the same work, so the difference in elapsed time is the
digest.
+//
+// The shape of the corpus matters to what is measured. Term frequencies
follow a Zipf-like
+// curve, as a real vocabulary does, so most terms fall below the digest's
floor and cost
+// only the one comparison that rejects them, while a small head clears it and
pays for a
+// bounded-heap insertion. Measuring on a flat corpus would either exercise no
heap at all
+// or exercise nothing but the heap; neither resembles a real index.
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <chrono>
+#include <cmath>
+#include <cstdint>
+#include <string>
+#include <vector>
+
+#include "storage/index/snii/format/format_constants.h"
+#include "storage/index/snii/reader/logical_index_reader.h"
+#include "storage/index/snii/reader/snii_segment_reader.h"
+#include "storage/index/snii/writer/logical_index_writer.h"
+#include "storage/index/snii/writer/snii_compound_writer.h"
+#include "storage/index/snii_query_test_util.h"
+
+namespace doris::snii::writer {
+namespace {
+
+using snii_test::assert_ok;
+using snii_test::make_term;
+using snii_test::MemoryFile;
+using snii_test::PostingDoc;
+
+constexpr uint32_t kDocCount = 200000;
+constexpr uint32_t kTermCount = 40000;
+constexpr int kRounds = 5;
+
+// A Zipf-like vocabulary over kDocCount documents: term i appears in roughly
+// kTermCount / (i + 1) documents, so a few hundred terms clear the digest
floor
+// (kDocCount / kHighDfDigestDivisor = 100) and the rest sit far below it.
+std::vector<TermPostings> BuildCorpus() {
+ std::vector<TermPostings> terms;
+ terms.reserve(kTermCount);
+ for (uint32_t i = 0; i < kTermCount; i++) {
+ const uint32_t df = std::max<uint32_t>(1, kTermCount / (i + 1));
+ const uint32_t stride = std::max<uint32_t>(1, kDocCount / df);
+ std::vector<PostingDoc> docs;
+ docs.reserve(df);
+ for (uint32_t docid = 0; docid < kDocCount && docs.size() < df; docid
+= stride) {
+ docs.push_back(PostingDoc {.docid = docid, .positions = {}});
+ }
+ // Zero-padded so the terms are already in lexicographic order.
+ char name[32];
+ snprintf(name, sizeof(name), "term_%06u", i);
+ terms.push_back(make_term(name, std::move(docs)));
+ }
+ return terms;
+}
+
+// One build of the whole index. with_digest selects it by supplying a gram
scheme, which is
+// the only thing that differs between the two arms.
+double BuildOnceMs(const std::vector<TermPostings>& corpus, bool with_digest,
+ uint64_t* digest_entries) {
+ SniiIndexInput input;
+ input.index_id = 31;
+ input.index_suffix = "body";
+ input.config = format::IndexConfig::kDocsOnly;
+ input.doc_count = kDocCount;
+ input.terms = corpus;
+ if (with_digest) {
+ segment_v2::gram::GramScheme scheme;
+ scheme.mode = segment_v2::gram::GramMode::SPARSE;
+ scheme.min_len = 3;
+ scheme.max_len = 4;
+ scheme.density_permille = 250;
+ input.gram_scheme = scheme;
+ }
+
+ MemoryFile file;
+ SniiCompoundWriter writer(&file);
+ const auto start = std::chrono::steady_clock::now();
+ assert_ok(writer.add_logical_index(input));
+ assert_ok(writer.finish());
+ const auto end = std::chrono::steady_clock::now();
+
+ if (digest_entries != nullptr) {
+ reader::SniiSegmentReader segment;
+ assert_ok(reader::SniiSegmentReader::open(&file, &segment));
+ reader::LogicalIndexReader index;
+ assert_ok(segment.open_index(31, "body", &index));
+ *digest_entries = index.high_df_terms().term_hash.size();
+ }
+ return std::chrono::duration<double, std::milli>(end - start).count();
+}
+
+double Median(std::vector<double> values) {
+ std::ranges::sort(values);
+ return values[values.size() / 2];
+}
+
+} // namespace
+
+// Reports the cost; asserts only that it is not a large fraction of the
build, so the case
+// records a number without becoming a tripwire for ordinary timing noise.
+TEST(SniiHighDfDigestCost, BuildingTheDigestIsANegligibleShareOfTheWrite) {
+ const std::vector<TermPostings> corpus = BuildCorpus();
+
+ uint64_t entries = 0;
+ std::vector<double> with_digest;
+ std::vector<double> without;
+ for (int round = 0; round < kRounds; round++) {
+ // Alternate the order so a warming effect cannot favour one arm
systematically.
+ if (round % 2 == 0) {
+ with_digest.push_back(BuildOnceMs(corpus, true, &entries));
+ without.push_back(BuildOnceMs(corpus, false, nullptr));
+ } else {
+ without.push_back(BuildOnceMs(corpus, false, nullptr));
+ with_digest.push_back(BuildOnceMs(corpus, true, &entries));
+ }
+ }
+
+ const double on = Median(with_digest);
+ const double off = Median(without);
+ const double overhead_pct = 100.0 * (on - off) / off;
+ // Spread of the two arms, so a reader can see whether the difference
above is signal.
+ const double on_spread =
+ *std::ranges::max_element(with_digest) -
*std::ranges::min_element(with_digest);
+ const double off_spread =
+ *std::ranges::max_element(without) -
*std::ranges::min_element(without);
+
+ printf("\n%u docs, %u terms, digest holds %llu entries\n", kDocCount,
kTermCount,
+ static_cast<unsigned long long>(entries));
+ printf("build with digest : %8.1f ms (median of %d, spread %.1f ms)\n",
on, kRounds,
+ on_spread);
+ printf("build without digest : %8.1f ms (median of %d, spread %.1f ms)\n",
off, kRounds,
+ off_spread);
+ printf("difference : %+8.1f ms (%+.2f%%)\n", on - off,
overhead_pct);
+ printf("per term : %+8.3f us\n", 1000.0 * (on - off) /
kTermCount);
+ // The work itself, which is deterministic and does not depend on the
machine: one
+ // comparison for every term, and a bounded-heap insertion only for those
above the
+ // floor. Reported alongside the timing because it is the number that
stays true.
+ printf("work : %u comparisons + at most %llu heap ops
(log2 K <= %.1f)\n",
+ kTermCount, static_cast<unsigned long long>(entries),
+ entries > 0 ? std::log2(static_cast<double>(entries)) : 0.0);
+
+ EXPECT_GT(entries, 0U) << "the corpus must actually populate the digest";
+ EXPECT_LT(overhead_pct, 5.0)
Review Comment:
[P2] Do not make BE UT success depend on this five-sample wall-clock ratio.
Independent medians and alternating order do not control scheduler preemption,
CPU throttling, sanitizer/allocator effects, or shared-runner contention; three
delayed `with_digest` samples can fail unchanged code above 5%, and delayed
baselines can hide a regression. Move the percentage gate to a controlled
benchmark/perf job or replace it with deterministic work/allocation invariants;
keep timing diagnostic-only in ordinary UT.
##########
be/src/storage/index/inverted/gram/gram_density.cpp:
##########
@@ -0,0 +1,125 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "storage/index/inverted/gram/gram_density.h"
+
+#include <algorithm>
+
+#include "storage/index/inverted/gram/gram_extractor.h"
+
+namespace doris::segment_v2::gram {
+
+DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len)
+ : _min_literal_len(min_literal_len),
+ _max_gram_len(max_gram_len),
+ _histogram(kHashValues, 0) {}
+
+void DensitySolver::observe(std::string_view value) {
+ if (_min_literal_len < _max_gram_len || _max_gram_len < 2) {
Review Comment:
[P2] Make the adaptive defaults satisfiable. A normal `mode=sparse`/`auto`
tokenizer with no optional properties gets `max_gram=16`, while
`gram_index_min_literal_bytes` defaults to 12, so this returns for every row.
Finalization sees zero windows, keeps density 0.25, and still pays the 4 MiB
buffering/replay cost; the advertised default-on per-column solve never occurs.
Please align the defaults (or explicitly disable an impossible solve) and add a
writer test with all optional gram properties omitted.
##########
be/src/storage/index/snii/snii_index_writer.cpp:
##########
@@ -211,6 +281,20 @@ Status SniiIndexColumnWriter::add_values(const std::string
/*name*/, const void*
}
const auto* v = reinterpret_cast<const Slice*>(values);
for (size_t i = 0; i < count; ++i) {
+ if (_density_calibrating) {
+ // Held back, not dropped: this row is tokenized once the rate is
known. Feeding
+ // the solver here costs one linear pass over the row and retains
nothing of it.
+ _density_solver->observe(std::string_view(v->data, v->size));
Review Comment:
[P2] Feed the solver the same canonical bytes that will be indexed. This
observes the raw `Slice`, but replay truncates CHAR at the first NUL and
`GramExtractor` lowercases before hashing when `lower_case=true`. Because the
solved density is a quantile of byte-pair hashes, padding and case can select a
rate for a different corpus, missing the advertised coverage target or
overgrowing the index. Please share the extraction preprocessing here and add
CHAR-padding/lowercase calibration tests.
##########
be/src/storage/index/snii/snii_index_writer.cpp:
##########
@@ -211,6 +281,20 @@ Status SniiIndexColumnWriter::add_values(const std::string
/*name*/, const void*
}
const auto* v = reinterpret_cast<const Slice*>(values);
for (size_t i = 0; i < count; ++i) {
+ if (_density_calibrating) {
+ // Held back, not dropped: this row is tokenized once the rate is
known. Feeding
+ // the solver here costs one linear pass over the row and retains
nothing of it.
+ _density_solver->observe(std::string_view(v->data, v->size));
+ _density_sample.emplace_back(_rid, std::string(v->data, v->size));
Review Comment:
[P2] Bound and report the retained sample allocation, not just string
payload bytes. Each row adds a `pair<uint32_t, string>`, but the threshold and
reporter advance only by `v->size`; an all-empty sample therefore never reaches
the 4 MiB limit while the vector keeps growing, and millions of one-byte values
can retain tens of bytes of vector/SSO state per reported byte. The solver's
256 KiB histogram and longest-row scratch are invisible too. This defeats the
build-RAM/spill signal across concurrent writers. Please cap/account actual
retained capacity (and/or row count), including empty/tiny-row tests.
##########
be/src/storage/index/inverted/gram/gram_density.cpp:
##########
@@ -0,0 +1,125 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "storage/index/inverted/gram/gram_density.h"
+
+#include <algorithm>
+
+#include "storage/index/inverted/gram/gram_extractor.h"
+
+namespace doris::segment_v2::gram {
+
+DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len)
+ : _min_literal_len(min_literal_len),
+ _max_gram_len(max_gram_len),
+ _histogram(kHashValues, 0) {}
+
+void DensitySolver::observe(std::string_view value) {
+ if (_min_literal_len < _max_gram_len || _max_gram_len < 2) {
+ return;
+ }
+ // Boundaries with a whole gram's room after them inside a window: a
boundary at k yields
+ // [k, k+max_gram_len) at worst, so k may not exceed len - max_gram_len.
That leaves
+ // `per_window` candidate positions in a window of the promised length.
+ const size_t per_window = _min_literal_len - _max_gram_len + 1;
+
+ size_t i = 0;
+ const size_t n = value.size();
+ while (i < n) {
+ // Only ASCII runs: they are the only bytes the extractor indexes, so
a window
+ // spanning anything else could never produce a gram.
+ if (static_cast<unsigned char>(value[i]) >= 0x80) {
+ ++i;
+ continue;
+ }
+ size_t j = i;
+ while (j < n && static_cast<unsigned char>(value[j]) < 0x80) {
+ ++j;
+ }
+ const std::string_view run = value.substr(i, j - i);
+ i = j;
+ if (run.size() < _min_literal_len) {
+ continue;
+ }
+ // Sliding minimum over the run's pair hashes, one window per start
position. The
+ // monotonic queue keeps this linear in the run rather than quadratic
in the window,
+ // which is what makes it affordable on the write path.
+ const size_t pairs = run.size() - 1;
+ _mono.clear();
+ size_t head = 0;
+ for (size_t p = 0; p < pairs; ++p) {
Review Comment:
[P2] Stop after the final real literal window. For an ASCII run of length
`n`, promised length `L`, and max gram `M`, there are `n-L+1` windows, but this
loop emits `n-L+M-1` minima because it continues through every byte pair—`M-2`
fictitious tail windows. With `n=L, M=4`, one real window is counted three
times, biasing the density quantile and its coverage promise. Limit `p` to
`run.size()-M` (or check `window_start+L`) and pin exact observed-window counts.
##########
be/src/storage/index/snii/format/format_constants.h:
##########
@@ -93,7 +93,14 @@ inline constexpr uint8_t kEnc = 1u << 1; // 0=slim /
1=windowed
inline constexpr uint8_t kHasSb = 1u << 2; // posting prelude includes
sub-block directory
inline constexpr uint8_t kHasChampion = 1u << 3; // v1 always 0
inline constexpr uint8_t kOffsetsRef = 1u << 4; // v1 always 0
-// bit5-7 reserved
+// The entry keeps its term key and df but carries no posting locator and no
payload: the
+// writer dropped a posting list too large for any reader to want.
bit0/bit1/bit2 are
+// meaningless when this is set, and nothing follows the term stats. A reader
that finds
+// this entry must treat the term as matching every document -- which is what
the query
+// side's cost gate already does for a df this high -- and must never confuse
it with a
+// term absent from the dictionary, which means the opposite: matching no
document.
+inline constexpr uint8_t kPostingDropped = 1u << 5;
Review Comment:
[P2] Fence this shortened entry from version-1 readers. The old decoder
ignores bit 5, treats these cleared low bits as a slim POD reference, and
unconditionally reads locator fields that this writer now omits, so it accepts
the v1 container and then reports truncation/body-length corruption. Ordinary
predicates can fall back to a scan, but automatic dropping makes
mixed-BE/shared-storage reads silently lose acceleration and leaves rollback
behavior dependent on that incidental corruption path. Please add a
required-feature/format gate plus a writer fleet fence, and cover
head-writer/frozen-old-reader behavior.
##########
be/src/storage/index/inverted/gram/gram_density.cpp:
##########
@@ -0,0 +1,125 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "storage/index/inverted/gram/gram_density.h"
+
+#include <algorithm>
+
+#include "storage/index/inverted/gram/gram_extractor.h"
+
+namespace doris::segment_v2::gram {
+
+DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len)
+ : _min_literal_len(min_literal_len),
+ _max_gram_len(max_gram_len),
+ _histogram(kHashValues, 0) {}
+
+void DensitySolver::observe(std::string_view value) {
+ if (_min_literal_len < _max_gram_len || _max_gram_len < 2) {
+ return;
+ }
+ // Boundaries with a whole gram's room after them inside a window: a
boundary at k yields
+ // [k, k+max_gram_len) at worst, so k may not exceed len - max_gram_len.
That leaves
+ // `per_window` candidate positions in a window of the promised length.
+ const size_t per_window = _min_literal_len - _max_gram_len + 1;
+
+ size_t i = 0;
+ const size_t n = value.size();
+ while (i < n) {
+ // Only ASCII runs: they are the only bytes the extractor indexes, so
a window
+ // spanning anything else could never produce a gram.
+ if (static_cast<unsigned char>(value[i]) >= 0x80) {
+ ++i;
+ continue;
+ }
+ size_t j = i;
+ while (j < n && static_cast<unsigned char>(value[j]) < 0x80) {
Review Comment:
[P2] Exclude NUL-bearing evidence that the extractor cannot realize.
`observe` treats NUL as ASCII and includes pair hashes around it, while sparse
extraction drops every candidate gram containing NUL. For `L=3`, `M=2`, value
`A\0B`, the solver records one covered window although extraction emits none at
any density; NUL-heavy rows can therefore skew the global quantile away from
real searchable windows. Model the extractor's NUL rule here and add an exact
solver/extractor case.
##########
be/src/common/config.cpp:
##########
@@ -1324,6 +1324,39 @@ DEFINE_Int32(inverted_index_query_cache_shards, "256");
// inverted index match bitmap cache size
DEFINE_String(inverted_index_query_cache_limit, "10%");
+namespace {
+
+bool valid_gram_index_candidate_ratio(int32_t value) {
+ return value >= 0;
+}
+
+bool valid_gram_index_candidate_min_rows(int32_t value) {
+ return value >= 0;
+}
+
+} // namespace
+
+// Whether LIKE/REGEXP tries to compile a constant pattern into a gram boolean
query pushed down
+// to a gram-family inverted index (master switch).
+DEFINE_mBool(enable_gram_index_regexp, "true");
+
+// Cost gate for the gram boolean query: give up pruning above this share (in
basis points) of a
+// segment's rows, and only on segments of at least this many rows. Giving up
returns the segment's
+// whole docid range, so it can never drop a candidate row.
+DEFINE_mInt32(gram_index_max_candidate_ratio_bp, "15");
+DEFINE_Validator(gram_index_max_candidate_ratio_bp,
valid_gram_index_candidate_ratio);
+DEFINE_mInt32(gram_index_candidate_ratio_min_rows, "65536");
+
+// On by default: a configured density is wrong on every column but the one it
was chosen for,
+// and the solve costs one pass over a bounded sample.
+DEFINE_mBool(enable_gram_index_adaptive_density, "true");
+// 12 bytes at 95% of windows. Both are the promise rather than a tuning pair
-- what a user
+// may reasonably change is how short a literal they expect to find, not the
boundary rate.
+DEFINE_mInt32(gram_index_min_literal_bytes, "12");
+DEFINE_mInt32(gram_index_density_coverage_permille, "950");
Review Comment:
[P1] Validate this mutable permille before it reaches writers. Unlike the
adjacent ratio settings, `gram_index_density_coverage_permille` accepts `-1`;
every default-armed gram writer then calls the checked `cast_set<uint32_t>`
during finalization (even with no observed windows), throws `INTERNAL_ERROR`,
and fails the load until the live config is repaired. Values above 1000 are
also outside the documented share and silently clamp to maximum density. Please
register the semantic range validator and test startup plus live-update
rejection.
##########
regression-test/suites/inverted_index_p0/gram/test_gram_stop_gram.groovy:
##########
@@ -0,0 +1,192 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// stop-gram end to end: an index built with the posting lists of very common
grams dropped
+// must still answer LIKE/REGEXP exactly, and must actually have dropped them.
+//
+// A dropped gram matches every document, so it can only ever widen the
candidate set the
+// index proposes, and the predicate is re-evaluated on those candidates. The
observable
+// contract is therefore equality: every pattern must return exactly what a
full scan
+// returns. The rows below are built so that the common grams really are
common -- a shared
+// prefix on every row -- while the patterns being searched for are rare,
which is the shape
+// where dropping matters.
+//
+// There is no switch to turn the feature off, so the control arm is the row
floor instead:
+// a segment under kHighDfDigestDivisor (2000) rows never drops a posting. The
same 4000 rows
+// are therefore loaded twice, once as a single segment (dropping active,
threshold
+// 4000 / 2000 * 3 = df 6) and once as five segments of 800 (dropping
inactive, every
+// posting kept). The two tables must agree on every answer, and the
single-segment index
+// must be much smaller -- that difference is the dropped postings, and it
also pins that
+// the floor holds.
+suite("test_gram_stop_gram", "p0") {
+ def waitAnalyzerInstalled = { String name ->
+ def deadline = System.currentTimeMillis() + 180_000
+ Exception lastNotFound = null
+ while (System.currentTimeMillis() < deadline) {
+ try {
+ sql """SELECT TOKENIZE('probe', '"analyzer"="${name}"')"""
+ return
+ } catch (Exception e) {
+ if (!e.message.contains("Policy not found")) {
+ throw e
+ }
+ lastNotFound = e
+ sleep(1000)
+ }
+ }
+ throw new IllegalStateException("analyzer ${name} was not installed on
BE", lastNotFound)
+ }
+
+ def backendId_to_backendIP = [:]
+ def backendId_to_backendHttpPort = [:]
+ getBackendIpHttpPort(backendId_to_backendIP, backendId_to_backendHttpPort)
+ def set_be_config = { key, value ->
+ for (String backend_id : backendId_to_backendIP.keySet()) {
+ def (code, out, err) =
update_be_config(backendId_to_backendIP.get(backend_id),
+ backendId_to_backendHttpPort.get(backend_id), key, value)
+ logger.info("update ${key}=${value}: code=${code}, out=${out},
err=${err}")
+ }
+ }
+
+ // The tables go first: a policy still referenced by a table left behind
by an earlier run
+ // cannot be dropped.
+ sql "DROP TABLE IF EXISTS test_gram_stop_gram_one"
+ sql "DROP TABLE IF EXISTS test_gram_stop_gram_five"
+ sql "DROP INVERTED INDEX ANALYZER IF EXISTS gram_stop_ana"
+ sql "DROP INVERTED INDEX TOKENIZER IF EXISTS gram_stop_tok"
+ sql """CREATE INVERTED INDEX TOKENIZER gram_stop_tok PROPERTIES (
+ "type"="ngram", "mode"="sparse", "min_gram"="3", "max_gram"="8",
"density"="0.5")"""
+ sql """CREATE INVERTED INDEX ANALYZER gram_stop_ana
+ PROPERTIES ("tokenizer"="gram_stop_tok")"""
+ waitAnalyzerInstalled("gram_stop_ana")
+
+ def rows = 4000
+ def values = []
+ for (int i = 0; i < rows; i++) {
+ // Every row shares "shared_prefix_", making its grams as common as a
gram gets. Four
+ // rows carry a rare marker (df 4, under the single segment's
threshold of 6, so its
+ // postings survive and the rare queries still filter); one row in
seven carries a
+ // mid-frequency tail whose grams sit above the line and are dropped.
+ def tail = (i % 1000 == 0) ? "rare_marker_${i}" : "filler_${i}"
+ values.add("(${i}, 'shared_prefix_common_text ${tail} tail_${i % 7}')")
+ }
+
+ def runAll = { String table, String label ->
+ def out = [:]
+ out["like_rare"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg LIKE
'%rare_marker_%'"
+ out["like_common"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg LIKE
'%shared_prefix_common%'"
+ out["regexp_rare"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg
REGEXP 'rare_marker_[0-9]+'"
+ out["regexp_common"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg
REGEXP 'shared_prefix_[a-z]+'"
+ out["regexp_mid"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg
REGEXP 'tail_3\$'"
+ out["regexp_alt"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg
REGEXP 'rare_marker_(0|1000|2000)\\\\b'"
+ out["regexp_absent"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg
REGEXP 'no_such_token_anywhere'"
+ out["like_tail"] = sql "SELECT COUNT(*) FROM ${table} WHERE msg LIKE
'%tail_3'"
+ logger.info("${label}: ${out}")
+ return out
+ }
+
+ def createTable = { String table ->
+ sql "DROP TABLE IF EXISTS ${table}"
+ sql """CREATE TABLE ${table} (
+ `id` bigint NULL,
+ `msg` text NULL,
+ INDEX idx_msg (`msg`) USING INVERTED
+ PROPERTIES('analyzer'='gram_stop_ana',
'support_phrase'='false')
+ ) ENGINE=OLAP DUPLICATE KEY(`id`)
+ DISTRIBUTED BY HASH(`id`) BUCKETS 1
+ PROPERTIES('replication_num'='1',
'inverted_index_storage_format'='SNII',
+ 'disable_auto_compaction'='true')"""
+ }
+
+ // information_schema reports a fresh table's sizes with a delay, and 0
there means "not
+ // yet" rather than "empty".
+ def indexBytes = { String table ->
+ def deadline = System.currentTimeMillis() + 180_000
+ while (System.currentTimeMillis() < deadline) {
+ def r = sql """SELECT INDEX_LENGTH FROM information_schema.tables
+ WHERE TABLE_SCHEMA = DATABASE() AND TABLE_NAME =
'${table}'"""
+ def bytes = r.isEmpty() ? 0L : (r[0][0] as long)
+ if (bytes > 0) {
+ return bytes
+ }
+ sleep(3000)
+ }
+ throw new IllegalStateException("index size of ${table} never
reported")
+ }
+
+ def oneSegment = "test_gram_stop_gram_one"
+ def fiveSegments = "test_gram_stop_gram_five"
+ try {
+ sql "SET enable_sql_cache=false"
+ sql "SET enable_condition_cache=false"
+
+ // One batch keeps all 4000 rows in a single segment: above the row
floor, dropping
+ // is in effect.
+ createTable(oneSegment)
+ sql "INSERT INTO ${oneSegment} VALUES ${values.join(',')}"
+
+ // The same rows in five batches of 800: each segment is under the
floor, so every
+ // posting list is kept. This is what the index looked like before
dropping existed.
+ createTable(fiveSegments)
+ for (int b = 0; b < 5; b++) {
+ sql "INSERT INTO ${fiveSegments} VALUES ${values.subList(b * 800,
(b + 1) * 800).join(',')}"
+ }
+
+ // Ground truth, taken with the index out of the picture entirely.
+ sql "SET enable_inverted_index_query=false"
+ def scanned = runAll(oneSegment, "full scan")
+ sql "SET enable_inverted_index_query=true"
+
+ def dropped = runAll(oneSegment, "one segment, postings dropped")
+ def kept = runAll(fiveSegments, "five segments, postings kept")
+ scanned.each { name, value ->
+ assertEquals(value[0][0], dropped[name][0][0],
+ "index and scan disagree on ${name} with postings dropped")
+ assertEquals(value[0][0], kept[name][0][0],
+ "index and scan disagree on ${name} with postings kept")
+ }
+
+ // The postings really were dropped. Measured: the single-segment
index is 0.36 of
+ // the five-segment one. Had nothing been dropped it would be about
0.9 -- the only
+ // difference left would be four fewer per-segment dictionaries -- so
a factor of two
+ // separates the two outcomes with margin on both sides.
+ def droppedBytes = indexBytes(oneSegment)
+ def keptBytes = indexBytes(fiveSegments)
+ logger.info("index bytes: one segment ${droppedBytes}, five segments
${keptBytes}")
+ assertTrue(droppedBytes * 2 < keptBytes,
+ "the single-segment index (${droppedBytes} bytes) should be
far smaller than " +
+ "the five-segment one (${keptBytes} bytes): its common
postings were not dropped")
+
+ // The gate could otherwise mask a broken dropped-gram path by giving
up first, so
+ // check again with its fallback ratio disabled. The gate's primary
budget comes from
+ // the segment itself and cannot be switched off -- that is the point
of deriving it
+ // rather than configuring it -- but zeroing the ratio removes the one
arm that a
+ // configuration could have been hiding behind.
+ set_be_config("gram_index_max_candidate_ratio_bp", "0")
Review Comment:
[P2] Make this phase prove a physical dropped entry reaches the query path.
It repeats the preceding raw queries with the inverted-index cache still
enabled, so these calls can all reuse old bitmaps without exercising the
updated gate. Even on a miss, ratio zero disables only the fallback budget; the
digest budget can still widen common-only predicates before `_resolve()`.
Disable/bust the cache, add a retained+common literal that stays under budget,
and assert a profile/counter proving dictionary resolution (also fail if the
config update failed).
##########
be/src/storage/index/inverted/gram/gram_density.cpp:
##########
@@ -0,0 +1,125 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+#include "storage/index/inverted/gram/gram_density.h"
+
+#include <algorithm>
+
+#include "storage/index/inverted/gram/gram_extractor.h"
+
+namespace doris::segment_v2::gram {
+
+DensitySolver::DensitySolver(size_t min_literal_len, size_t max_gram_len)
+ : _min_literal_len(min_literal_len),
+ _max_gram_len(max_gram_len),
+ _histogram(kHashValues, 0) {}
+
+void DensitySolver::observe(std::string_view value) {
+ if (_min_literal_len < _max_gram_len || _max_gram_len < 2) {
+ return;
+ }
+ // Boundaries with a whole gram's room after them inside a window: a
boundary at k yields
+ // [k, k+max_gram_len) at worst, so k may not exceed len - max_gram_len.
That leaves
+ // `per_window` candidate positions in a window of the promised length.
+ const size_t per_window = _min_literal_len - _max_gram_len + 1;
+
+ size_t i = 0;
+ const size_t n = value.size();
+ while (i < n) {
+ // Only ASCII runs: they are the only bytes the extractor indexes, so
a window
+ // spanning anything else could never produce a gram.
+ if (static_cast<unsigned char>(value[i]) >= 0x80) {
+ ++i;
+ continue;
+ }
+ size_t j = i;
+ while (j < n && static_cast<unsigned char>(value[j]) < 0x80) {
+ ++j;
+ }
+ const std::string_view run = value.substr(i, j - i);
+ i = j;
+ if (run.size() < _min_literal_len) {
+ continue;
+ }
+ // Sliding minimum over the run's pair hashes, one window per start
position. The
+ // monotonic queue keeps this linear in the run rather than quadratic
in the window,
+ // which is what makes it affordable on the write path.
+ const size_t pairs = run.size() - 1;
+ _mono.clear();
+ size_t head = 0;
+ for (size_t p = 0; p < pairs; ++p) {
+ const uint16_t h =
+ boundary_hash16(static_cast<uint8_t>(run[p]),
static_cast<uint8_t>(run[p + 1]));
+ while (_mono.size() > head &&
+ boundary_hash16(static_cast<uint8_t>(run[_mono.back()]),
+ static_cast<uint8_t>(run[_mono.back() +
1])) >= h) {
+ _mono.pop_back();
+ }
+ _mono.push_back(static_cast<uint32_t>(p));
+ if (p + 1 < per_window) {
+ continue;
+ }
+ const size_t window_start = p + 1 - per_window;
+ while (_mono[head] < window_start) {
+ ++head;
+ }
+ const uint16_t min_hash =
boundary_hash16(static_cast<uint8_t>(run[_mono[head]]),
+
static_cast<uint8_t>(run[_mono[head] + 1]));
+ ++_histogram[min_hash];
+ ++_windows;
+ }
+ }
+}
+
+uint16_t DensitySolver::solve(uint32_t coverage_permille) const {
+ if (_windows == 0 || coverage_permille == 0) {
+ // No evidence, or nothing asked for. Stay where a configured default
would have been
+ // rather than inventing a rate from nothing.
+ return kMaxSolvedDensityPermille;
+ }
+ // A window is covered exactly when its minimum is below the threshold, so
the prefix sum
+ // of the histogram IS the coverage curve: walk it until the requested
share is reached and
+ // the threshold that achieves it -- and nothing larger -- is one past
that hash.
+ const uint64_t need = (static_cast<uint64_t>(coverage_permille) * _windows
+ 999) / 1000;
+ uint64_t seen = 0;
+ uint32_t threshold = kHashValues;
+ for (size_t h = 0; h < kHashValues; ++h) {
+ seen += _histogram[h];
+ if (seen >= need) {
+ // `is_boundary` compares strictly, so the threshold has to clear
this hash.
+ threshold = static_cast<uint32_t>(h) + 1;
+ break;
+ }
+ }
+ // GramExtractor derives its threshold as density_permille * 65536 / 1000
with integer
+ // division; round up or the resolved density can land a notch below what
was solved for.
+ uint32_t permille =
+ static_cast<uint32_t>((static_cast<uint64_t>(threshold) * 1000 +
65535) / 65536);
+ permille = std::clamp<uint32_t>(permille, kMinSolvedDensityPermille,
kMaxSolvedDensityPermille);
Review Comment:
[P2] Do not persist a ceiling-clamped value as though it met the requested
coverage. With valid `L=max_gram=12`, coverage 950, and rows `!!!!!!!!!!!!`,
the only pair hash is 60807 (density 928 required); this cap persists 500
(threshold 32768), so extraction emits no gram and real coverage is 0%, not
95%. This is active calibration, not a no-evidence fallback. Either permit the
required density or explicitly handle/report an unsatisfied target, and test a
corpus whose quantile exceeds the cap.
--
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]
