github-actions[bot] commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r3986191672
##########
be/src/storage/index/snii/snii_index_reader.cpp:
##########
@@ -651,6 +737,12 @@ Status SniiIndexReader::_query(const IndexQueryContextPtr&
context, const std::s
const ::doris::snii::reader::LogicalIndexReader* logical_reader = nullptr;
RETURN_IF_ERROR(_get_logical_reader(context, &searcher_cache_handle,
&uncached_reader,
&logical_reader));
+ if (analyzed_query && logical_reader->gram_scheme().has_value() &&
Review Comment:
[P1] Treat an absent persisted scheme as a mismatch when the current
analyzer has a gram scheme. Legacy ngram tokenizers without `mode` write
`gram_scheme=nullopt`; after recovering the table with the same policy name
recreated in gram mode, `current_gram_scheme` is populated, but this
`has_value()` guard skips the comparison. MATCH then analyzes `abcdef` into
current dense grams and looks them up in the old legacy dictionary (for
example, fixed bigrams), so it can return no rows before fallback even though
current-analyzer evaluation matches. LIKE/REGEXP already refuse a reader with
no scheme. Please compare the optionals directly when the current scheme is
populated and add legacy-ngram-to-gram recovery coverage for MATCH_ANY/ALL.
##########
be/src/storage/index/inverted/gram/regex_gram_compiler.cpp:
##########
@@ -0,0 +1,720 @@
+// 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/regex_gram_compiler.h"
+
+#include <algorithm>
+#include <cstdint>
+#include <memory>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include "common/logging.h"
+#include "storage/index/inverted/gram/regex_ast.h"
+
+namespace doris::segment_v2::gram {
+
+// Storage is a unity build: other .cpp files in this directory also define
file-level helpers
+// named utf8_len / codepoint_len, so this file's helpers live in a
file-specific namespace
+// wrapped in an anonymous one.
+namespace regex_gram_compiler_detail {
+namespace {
+
+// An exact set whose strings are all already >= n yields useful grams more
often, so it is
+// demoted past 4 entries; together with kMaxExact (the cap that demotes
regardless of length)
+// these are the prototype simplify's two thresholds.
+constexpr size_t kMaxLongExact = 4;
+// Recursion depth cap for analyze. parse_regex only bounds group nesting (64
levels), while
+// stacked quantifiers such as `a++++...` build an equally deep PLUS/REPEAT
chain; past the cap
+// we degrade to info_any_match (no constraint at all, conservative and safe)
so a user-supplied
+// pattern cannot blow the stack.
+constexpr int kMaxAnalyzeDepth = 200;
+// Maximum number of copies a REPEAT is unrolled into: x{m,..} is expanded
exactly min(m, 4)
+// times and then handled as a plus.
+constexpr int kMaxRepeatUnroll = 4;
+
+// Byte length (1/2/3/4) of the UTF-8 sequence starting with lead byte c; an
illegal lead byte
+// counts as 1.
+inline int utf8_len(unsigned char c) {
+ if (c < 0x80) {
+ return 1;
+ }
+ if ((c >> 5) == 0x6) {
+ return 2;
+ }
+ if ((c >> 4) == 0xE) {
+ return 3;
+ }
+ if ((c >> 3) == 0x1E) {
+ return 4;
+ }
+ return 1;
+}
+
+// Byte length of one valid UTF-8 code point starting at p; returns 1 for a
truncated sequence or
+// a stray continuation byte. Exactly the rule GramExtractor uses: on the
index side a non-ASCII
+// code point is a whole 1-gram.
+inline size_t codepoint_len(const char* p, size_t remain) {
+ int l = utf8_len((unsigned char)p[0]);
+ if (l == 1 || (size_t)l > remain) {
+ return 1;
+ }
+ for (int k = 1; k < l; k++) {
+ if (((unsigned char)p[k] & 0xC0) != 0x80) {
+ return 1;
+ }
+ }
+ return l;
+}
+
+// The leading <= k bytes of s, always stopping on a code point boundary.
Cutting a multi-byte
+// code point in half would forge "fake grams" that do not exist in the index
and cause false
+// negatives, so we would rather keep a few bytes fewer.
+std::string head_units(const std::string& s, size_t k) {
+ size_t i = 0;
+ while (i < s.size()) {
+ size_t l = codepoint_len(s.data() + i, s.size() - i);
+ if (i + l > k) {
+ break;
+ }
+ i += l;
+ }
+ return s.substr(0, i);
+}
+
+// The trailing <= k bytes of s, always starting on a code point boundary
(same reason as
+// head_units).
+std::string tail_units(const std::string& s, size_t k) {
+ if (s.size() <= k) {
+ return s;
+ }
+ size_t i = 0;
+ while (i < s.size() && s.size() - i > k) {
+ i += codepoint_len(s.data() + i, s.size() - i);
+ }
+ return s.substr(i);
+}
+
+// Strict UTF-8 well-formedness test, the guard in front of "a literal becomes
mandatory grams".
+//
+// The invariant it protects is the one the whole feature rests on: every gram
the query side
+// derives from a literal must be a gram the index side could have produced
from a row that
+// really matches. GramExtractor splits a row position-dependently -- an ASCII
run is windowed,
+// and every byte >= 0x80 is consumed as one whole code point -- so the same
bytes are split
+// differently depending on whether they start on a code point boundary. A
literal that is not
+// itself well-formed UTF-8 therefore yields grams that need not exist in a
matching row, and
+// requiring them prunes the row away.
+//
+// Rejected: a stray continuation byte (0x80-0xBF) as a lead byte, an illegal
lead byte
+// (0xF8-0xFF), a sequence that runs past the end of s, a bad continuation
byte, an overlong
+// encoding, a surrogate (U+D800-U+DFFF), and anything above U+10FFFF -- the
last of which also
+// catches whatever fake code point may still slip past the degradations in
regex_ast.cpp.
+bool is_well_formed_utf8(const std::string& s) {
+ size_t i = 0;
+ while (i < s.size()) {
+ const auto c = static_cast<unsigned char>(s[i]);
+ if (c < 0x80) {
+ i++;
+ continue;
+ }
+ size_t len = 0;
+ uint32_t cp = 0;
+ uint32_t lowest = 0; // smallest code point this length may legally
encode
+ if ((c & 0xE0) == 0xC0) {
+ len = 2;
+ cp = c & 0x1FU;
+ lowest = 0x80;
+ } else if ((c & 0xF0) == 0xE0) {
+ len = 3;
+ cp = c & 0x0FU;
+ lowest = 0x800;
+ } else if ((c & 0xF8) == 0xF0) {
+ len = 4;
+ cp = c & 0x07U;
+ lowest = 0x10000;
+ } else {
+ return false; // continuation byte used as a lead, or 0xF8-0xFF
+ }
+ if (i + len > s.size()) {
+ return false; // the sequence is not fully contained in s
+ }
+ for (size_t k = 1; k < len; k++) {
+ const auto cc = static_cast<unsigned char>(s[i + k]);
+ if ((cc & 0xC0) != 0x80) {
+ return false;
+ }
+ cp = (cp << 6) | (cc & 0x3FU);
+ }
+ if (cp < lowest || cp > 0x10FFFF || (cp >= 0xD800 && cp <= 0xDFFF)) {
+ return false;
+ }
+ i += len;
+ }
+ return true;
+}
+
+// Cartesian-product concatenation; sets *too_big and returns an empty set
once the result would
+// exceed kMaxSet (the caller then takes the demotion path).
+std::set<std::string> cross(const std::set<std::string>& a, const
std::set<std::string>& b,
+ bool* too_big) {
+ std::set<std::string> r;
+ *too_big = a.size() * b.size() > RegexGramCompiler::kMaxSet;
+ if (*too_big) {
+ return r;
+ }
+ for (const auto& x : a) {
+ for (const auto& y : b) {
+ r.insert(x + y);
+ }
+ }
+ return r;
+}
+
+std::set<std::string> uni(const std::set<std::string>& a, const
std::set<std::string>& b) {
+ std::set<std::string> r = a;
+ r.insert(b.begin(), b.end());
+ return r;
+}
+
+// Byte length of the shortest string in the set; an empty set counts as 0.
+size_t min_str_len(const std::set<std::string>& s) {
+ size_t m = SIZE_MAX;
+ for (const auto& x : s) {
+ m = std::min(m, x.size());
+ }
+ return m == SIZE_MAX ? 0 : m;
+}
+
+// Cox's five-tuple: a finite approximation of the string set a regex subtree
can match.
+// can_empty the subtree can match the empty string
+// has_exact the match set is fully enumerated by exact (prefix/suffix are
then meaningless)
+// exact the fully enumerated set of matching strings
+// prefix the possible beginnings of every matching string (nothing
outside the set can
+// start a match)
+// suffix the possible endings of every matching string
+// match the gram condition already known to hold inside every matching
string
+// Invariant: exact is non-empty when has_exact; otherwise prefix and suffix
are both non-empty
+// ("" meaning no constraint).
+struct Info {
+ bool can_empty = false;
+ bool has_exact = false;
+ std::set<std::string> exact;
+ std::set<std::string> prefix;
+ std::set<std::string> suffix;
+ GramQuery match; // defaults to ALL
+};
+
+// Matches the empty string only.
+Info info_empty() {
+ Info i;
+ i.can_empty = true;
+ i.has_exact = true;
+ i.exact = {""};
+ return i;
+}
+
+// Matches exactly one unknown character (`.`, a big class, a non-indexable
literal with NUL).
+Info info_any_char() {
+ Info i;
+ i.prefix = {""};
+ i.suffix = {""};
+ return i;
+}
+
+// Matches any string (`x*`, or a subtree we cannot reason about): imposes no
constraint.
+Info info_any_match() {
+ Info i;
+ i.can_empty = true;
+ i.prefix = {""};
+ i.suffix = {""};
+ return i;
+}
+
+const std::set<std::string>& pre(const Info& x) {
+ return x.has_exact ? x.exact : x.prefix;
+}
+
+const std::set<std::string>& suf(const Info& x) {
+ return x.has_exact ? x.exact : x.suffix;
+}
+
+// The body of the Cox derivation. Every place that can produce grams goes
through q_of_string /
+// q_of_set, both of which return ALL when no gram is available, which
guarantees "rather not
+// filter at all than filter a match away".
+class CoxAnalyzer {
+public:
+ explicit CoxAnalyzer(GramExtractor& extractor)
+ : _extractor(extractor), _scheme(extractor.scheme()) {}
+
+ // Whole tree -> gram query.
+ GramQuery compile(const RegexNode* root) {
+ Info info = _analyze(root, 0);
+ GramQuery m = std::move(info.match);
+ if (info.has_exact) {
+ m = GramQuery::and_(std::move(m), q_of_set(info.exact));
+ } else {
+ m = GramQuery::and_(std::move(m), q_of_set(info.prefix));
+ m = GramQuery::and_(std::move(m), q_of_set(info.suffix));
+ }
+ return m;
+ }
+
+ // AND of every gram of the literal s. Returns ALL when s yields no gram
(too short, or no
+ // CDC boundary).
+ GramQuery q_of_string(const std::string& s) {
+ // The index side never produces a gram containing NUL, and neither
may we (Ruling R9).
+ // analyze already treats a literal node holding NUL as anyChar; this
is the fallback for
+ // other entry points such as compile_like.
+ //
+ // The UTF-8 test guards the same kind of mismatch for multi-byte
content: this function
+ // is the single place where a literal turns into mandatory grams, so
an ill-formed
+ // literal -- a LIKE segment that starts in the middle of a code
point, raw illegal bytes
+ // in either kind of pattern -- has to degrade here rather than demand
grams that a
+ // matching row may not hold.
+ if (s.find('\0') != std::string::npos || !is_well_formed_utf8(s)) {
+ return GramQuery::all();
+ }
+ std::vector<std::string> g;
+ _extractor.grams_of_literal(s, &g);
+ if (g.empty()) {
+ return GramQuery::all();
+ }
+ GramQuery q;
+ q.op = GramQuery::Op::AND;
+ q.grams = std::move(g);
+ std::sort(q.grams.begin(), q.grams.end());
+ q.grams.erase(std::unique(q.grams.begin(), q.grams.end()),
q.grams.end());
+ return q;
+ }
+
+ // Any one string of the set suffices -> OR. An empty set means "nothing
can match", hence
+ // NONE.
+ GramQuery q_of_set(const std::set<std::string>& ss) {
+ if (ss.empty()) {
+ return GramQuery::none();
+ }
+ GramQuery r = GramQuery::none();
+ for (const auto& s : ss) {
+ r = GramQuery::or_(std::move(r), q_of_string(s));
+ }
+ return r;
+ }
+
+private:
+ // How much of prefix/suffix to keep: a SPARSE gram is at most max_len
long, so a whole gram
+ // has to fit; DENSE has fixed length n, so n-1 is enough (anything longer
only repeats grams
+ // already folded into match).
+ size_t _keep() const {
+ if (_scheme.mode == GramMode::SPARSE) {
+ return _scheme.max_len;
+ }
+ return _scheme.min_len >= 1 ? _scheme.min_len - 1 : 0;
+ }
+
+ // Whether every string in the set is long enough (>= n). Folding the
whole set into match is
+ // only worth it when they all are: if a single string yields no gram, the
OR collapses to
+ // ALL and the fold constrains nothing.
+ bool _all_long(const std::set<std::string>& s) const {
+ return std::ranges::all_of(s,
+ [this](const auto& x) { return x.size() >=
_scheme.min_len; });
+ }
+
+ // With scheme.lower_case the index side already folds ASCII letters to
lower case, so
+ // literals must fold the same way. The whole pattern string must not be
lowercased -- that
+ // would break the case-sensitive escapes `\E \B \W \D \S \P \A` -- so
folding happens only
+ // on AST leaves (LIT / CLASS elements).
+ std::string _fold(const std::string& s) const {
+ if (!_scheme.lower_case) {
+ return s;
+ }
+ std::string r = s;
+ for (auto& ch : r) {
+ if (ch >= 'A' && ch <= 'Z') {
+ ch = static_cast<char>(ch - 'A' + 'a');
+ }
+ }
+ return r;
+ }
+
+ // Fold the set's grams into match (only meaningful when every string is
>= n, otherwise it
+ // carries no information), then trim the strings to keep bytes; if the
set still exceeds
+ // kMaxSet after trimming, keep shrinking keep until it is small enough or
trimmed to empty.
+ void _trim_set(std::set<std::string>* s, GramQuery* match, bool is_suffix)
{
+ if (s->empty()) {
+ return;
+ }
+ if (_all_long(*s)) {
+ *match = GramQuery::and_(std::move(*match), q_of_set(*s));
+ }
+ size_t keep = _keep();
+ for (;;) {
+ std::set<std::string> t;
+ for (const auto& x : *s) {
+ t.insert(is_suffix ? tail_units(x, keep) : head_units(x,
keep));
+ }
+ *s = std::move(t);
+ if (s->size() <= RegexGramCompiler::kMaxSet || keep == 0) {
+ break;
+ }
+ keep--;
+ }
+ }
+
+ // Demote exact to prefix/suffix: the full enumeration can no longer be
maintained, but
+ // "every matching string starts with one of the exact strings and ends
with one of them"
+ // still holds; fold the grams into match first so that information is not
lost.
+ void _demote(Info* x) {
+ if (!x->has_exact) {
+ return;
+ }
+ if (_all_long(x->exact)) {
+ x->match = GramQuery::and_(std::move(x->match),
q_of_set(x->exact));
+ }
+ x->prefix = x->exact;
+ x->suffix = x->exact;
+ x->exact.clear();
+ x->has_exact = false;
+ }
+
+ // Demote exact once the set size / string length crosses a threshold, and
trim
+ // prefix/suffix. The prototype's simplify also takes a `force` parameter,
but every call
+ // site passes false, so it is omitted here.
+ Info _simplify(Info x) {
+ if (x.has_exact) {
+ const size_t ml = min_str_len(x.exact);
+ const bool all_long = _all_long(x.exact);
+ // Three demotion conditions: too many enumerated strings
(kMaxExact); not too many,
+ // but each one already yields a gram, so enumerating further only
multiplies OR
+ // branches (kMaxLongExact); the strings have grown to >= 2n, so
more concatenation
+ // only makes exact longer without adding grams. In all three
cases demoting to
+ // prefix/suffix and landing the grams we have in match pays off
more.
+ if (x.exact.size() > RegexGramCompiler::kMaxExact ||
+ (all_long && x.exact.size() > kMaxLongExact) ||
+ ml >= static_cast<size_t>(2) * _scheme.min_len) {
+ _demote(&x);
+ }
+ }
+ if (!x.has_exact) {
+ _trim_set(&x.prefix, &x.match, false);
+ _trim_set(&x.suffix, &x.match, true);
+ }
+ return x;
+ }
+
+ // Concatenation xy.
+ Info _concat_info(Info x, Info y) {
+ Info r;
+ if (x.has_exact && y.has_exact) {
+ bool big = false;
+ std::set<std::string> c = cross(x.exact, y.exact, &big);
+ if (!big) {
+ r.has_exact = true;
+ r.exact = std::move(c);
+ } else {
+ _demote(&x);
+ _demote(&y);
+ }
+ }
+ if (!r.has_exact) {
+ if (x.has_exact) {
+ bool big = false;
+ std::set<std::string> c = cross(x.exact, y.prefix, &big);
+ if (big) {
+ _demote(&x);
+ r.prefix = x.prefix;
+ if (x.can_empty) {
+ r.prefix = uni(r.prefix, y.prefix);
+ }
+ } else {
+ r.prefix = std::move(c);
+ }
+ } else {
+ r.prefix = x.prefix;
+ if (x.can_empty) {
+ r.prefix = uni(r.prefix, pre(y));
+ }
+ }
+ if (y.has_exact) {
+ bool big = false;
+ std::set<std::string> c = cross(x.suffix, y.exact, &big);
+ if (big) {
+ _demote(&y);
+ r.suffix = y.suffix;
+ if (y.can_empty) {
+ r.suffix = uni(r.suffix, x.suffix);
+ }
+ } else {
+ r.suffix = std::move(c);
+ }
+ } else {
+ r.suffix = y.suffix;
+ if (y.can_empty) {
+ r.suffix = uni(r.suffix, suf(x));
+ }
+ }
+ // Boundary grams: some suffix of x and some prefix of y are
necessarily adjacent in
+ // a matching string, so their concatenation is necessarily a
substring of it and can
+ // be folded straight into match.
+ if (!x.has_exact && !y.has_exact) {
+ bool big = false;
+ std::set<std::string> c = cross(x.suffix, y.prefix, &big);
+ if (!big && !c.empty() && _all_long(c)) {
+ r.match = GramQuery::and_(std::move(r.match), q_of_set(c));
+ }
+ }
+ }
+ r.match = GramQuery::and_(std::move(r.match),
+ GramQuery::and_(std::move(x.match),
std::move(y.match)));
+ r.can_empty = x.can_empty && y.can_empty;
+ return _simplify(std::move(r));
+ }
+
+ // Alternation x|y.
+ Info _alt_info(Info x, Info y) {
+ Info r;
+ if (x.has_exact && y.has_exact) {
+ std::set<std::string> u = uni(x.exact, y.exact);
+ if (u.size() <= RegexGramCompiler::kMaxSet) {
+ r.has_exact = true;
+ r.exact = std::move(u);
+ } else {
+ _demote(&x);
+ _demote(&y);
+ }
+ }
+ if (!r.has_exact) {
+ _demote(&x);
+ _demote(&y);
+ r.prefix = uni(x.prefix, y.prefix);
+ r.suffix = uni(x.suffix, y.suffix);
+ }
+ r.can_empty = x.can_empty || y.can_empty;
+ r.match = GramQuery::or_(std::move(x.match), std::move(y.match));
+ return _simplify(std::move(r));
+ }
+
+ // x+: the repetition count is unknown, so all we can keep is "starts with
one of x's
+ // strings and ends with one of x's strings".
+ Info _plus_info(Info x) {
+ _demote(&x);
+ return _simplify(std::move(x));
+ }
+
+ // Bounded quantifier REPEAT `{m}` / `{m,}` / `{m,n}`: unroll exactly
+ // min(m, kMaxRepeatUnroll) times (which captures the boundary grams
across copies); when
+ // there may be more repetitions (rmax has no upper bound, or exceeds the
unrolled count)
+ // fall back to plus and keep only the two ends. Split out of _analyze to
reduce its
+ // complexity/length; the semantics are identical to the original switch
case.
+ Info _repeat_info(const RegexNode* n, int depth) {
+ // rmin < 0 can only come from a counter overflow during parsing; the
range is then
+ // untrustworthy, so be conservative.
+ if (n->kids.empty() || n->rmin < 0) {
+ return info_any_match();
+ }
+ if (n->rmin == 0 && n->rmax == 0) {
+ return info_empty();
+ }
+ if (n->rmin == 0) {
+ return info_any_match();
+ }
+ Info acc = info_empty();
+ const int reps = std::min(n->rmin, kMaxRepeatUnroll);
+ for (int k = 0; k < reps; k++) {
+ acc = _concat_info(std::move(acc), _analyze(n->kids[0].get(),
depth + 1));
+ }
+ if (n->rmax == n->rmin && n->rmin <= kMaxRepeatUnroll) {
+ return acc;
+ }
+ return _plus_info(std::move(acc));
+ }
+
+ Info _analyze(const RegexNode* n, int depth) {
+ if (n == nullptr || depth > kMaxAnalyzeDepth) {
+ return info_any_match();
+ }
+ switch (n->type) {
+ case RegexNode::Type::EMPTY:
+ return info_empty();
+ case RegexNode::Type::LIT: {
+ std::string lit = _fold(n->lit);
+ // Ruling R9: a literal containing NUL is not indexable; treat the
whole node as one
+ // unknown character.
+ if (lit.find('\0') != std::string::npos) {
+ return info_any_char();
+ }
+ Info i;
+ i.has_exact = true;
+ i.exact.insert(std::move(lit));
+ return _simplify(std::move(i));
+ }
+ case RegexNode::Type::CLASS: {
+ DCHECK(!n->big_class || n->cls.empty());
+ if (n->big_class || n->cls.empty()) {
+ return info_any_char();
+ }
+ Info i;
+ i.has_exact = true;
+ for (const auto& s : n->cls) {
+ std::string f = _fold(s);
+ // A single non-indexable element degrades the whole class to
an unknown
+ // character: dropping just that element would stop exact from
covering every
+ // possibility, and that is exactly where false negatives come
from.
+ if (f.find('\0') != std::string::npos) {
+ return info_any_char();
+ }
+ i.exact.insert(std::move(f)); // folding may create
duplicates; the set dedups
+ }
+ return _simplify(std::move(i));
+ }
+ case RegexNode::Type::ANY:
+ return info_any_char();
+ case RegexNode::Type::CAT: {
+ Info acc = info_empty();
+ for (const auto& k : n->kids) {
+ acc = _concat_info(std::move(acc), _analyze(k.get(), depth +
1));
+ }
+ return acc;
+ }
+ case RegexNode::Type::ALT: {
+ if (n->kids.empty()) {
+ return info_any_match();
+ }
+ Info acc = _analyze(n->kids[0].get(), depth + 1);
+ for (size_t k = 1; k < n->kids.size(); k++) {
+ acc = _alt_info(std::move(acc), _analyze(n->kids[k].get(),
depth + 1));
+ }
+ return acc;
+ }
+ case RegexNode::Type::STAR:
+ return info_any_match();
+ case RegexNode::Type::PLUS:
+ if (n->kids.empty()) {
+ return info_any_match();
+ }
+ return _plus_info(_analyze(n->kids[0].get(), depth + 1));
+ case RegexNode::Type::QUEST:
+ if (n->kids.empty()) {
+ return info_any_match();
+ }
+ return _alt_info(_analyze(n->kids[0].get(), depth + 1),
info_empty());
+ case RegexNode::Type::REPEAT:
+ return _repeat_info(n, depth);
+ }
+ return info_any_match();
+ }
+
+ GramExtractor& _extractor;
+ const GramScheme& _scheme;
+};
+
+} // namespace
+} // namespace regex_gram_compiler_detail
+
+RegexGramCompiler::RegexGramCompiler(const GramScheme& scheme) :
_extractor(scheme) {}
+
+void RegexGramCompiler::apply_gram_budget(GramQuery* q) {
+ if (q->leaf_count() > kMaxQueryGrams) {
+ *q = GramQuery::all();
+ }
+}
+
+Status RegexGramCompiler::compile_regexp(std::string_view pattern, GramQuery*
out) {
+ // Hyperscan compiles a C string, while scalar string fast paths and RE2
use the full
+ // length. No constraints after a raw NUL are universally required across
those paths.
+ if (pattern.find('\0') != std::string_view::npos) {
+ *out = GramQuery::all();
+ return Status::OK();
+ }
+ std::unique_ptr<RegexNode> root;
+ bool case_insensitive = false;
+ // A parse failure always falls back conservatively to ALL; never return
an error and fail
+ // the caller's query.
+ if (!parse_regex(pattern, &root, &case_insensitive).ok() || root ==
nullptr) {
+ *out = GramQuery::all();
+ return Status::OK();
+ }
+ // case_insensitive itself needs no extra handling: with lower_case=false
parse_regex has
+ // already expanded ASCII letter literals under `(?i)` into CLASS{c,C}
(Cox's approach); with
+ // lower_case=true both index and query fold to lower case, so it is
enough for CoxAnalyzer
+ // to fold on the AST leaves.
+ regex_gram_compiler_detail::CoxAnalyzer analyzer(_extractor);
+ *out = analyzer.compile(root.get());
Review Comment:
[P1] Apply the gram/work budget during compilation, before constructing the
full query. Once a long high-entropy regexp literal is demoted, every following
byte adds a boundary gram and `GramQuery::and_` copies/deduplicates/sorts the
entire growing vector; LIKE has the same issue when many literal segments are
repeatedly flushed and ANDed. Only after all of that does this shared call
collapse >64 leaves to `ALL`. A user-supplied pattern can therefore incur
superlinear, non-cancellable CPU once per segment even though the result is
discarded. Please carry a budget through both compiler paths (or combine
literal runs linearly) and stop as soon as the conservative result must be
`ALL`.
##########
be/src/storage/index/snii/snii_index_reader.cpp:
##########
@@ -156,6 +164,23 @@ bool uses_phrase_frequency_scoring(InvertedIndexQueryType
query_type,
query_type == InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY);
}
+// Query types whose terms come out of the current analyzer. On a gram-family
index those
+// terms are grams, and they only mean what the segment's own grams mean when
both were cut
+// by the same scheme; a gram query compiles against the segment's scheme
itself and a raw
+// pattern query never analyzes, so neither is affected.
Review Comment:
[P1] Include `MATCH_REGEXP_QUERY` in the gram-scheme fence. Its pattern is
raw, but its semantics still depend on analyzer output: scalar
`FunctionMatchRegexp` regex-matches terms produced from each row by the current
analyzer, whereas SNII regex-matches the persisted segment dictionary. For an
explicit dense-3/3 segment recovered under dense-4/4, row `abcd` with pattern
`^abcd$` matches scalar token `abcd`, but the old dictionary has only
`abc`/`bcd`, so the index returns an empty exact bitmap. This subtype also
keeps the scheme-blind result cache enabled. Please classify it by
analyzer-dependent data terms, skip on mismatch (including a missing persisted
scheme), and add indexed/unindexed recovery parity.
##########
be/src/storage/index/inverted/gram/regex_ast.cpp:
##########
@@ -0,0 +1,800 @@
+// 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/regex_ast.h"
+
+#include <algorithm>
+#include <cctype>
+#include <cstdint>
+
+namespace doris::segment_v2::gram {
+
+// The BE storage target enables CMake unity builds (several .cpp files are
compiled together,
+// see UNITY_BUILD_BATCH_SIZE in be/src/storage/CMakeLists.txt), so every
anonymous namespace in
+// a batch is merged into one translation unit. A bare anonymous namespace
then redefines any
+// symbol whose name another file of the same batch happens to reuse (even in
a different .cpp),
+// and the batching changes as files are added to or removed from the
directory, so "this batch
+// only holds these files" cannot be assumed for long. Hence the extra named
namespace private
+// to this file, which isolates this file's anonymous namespace; the symbols
inside it still
+// have internal linkage (anonymous-namespace semantics are unaffected by a
named enclosing
+// namespace).
+namespace regex_ast_detail {
+
+namespace {
+
+// Maximum recursion nesting depth of `(...)` groups: every extra group level
adds one more
+// recursion through the parse_alt/parse_cat/parse_atom call chain. A
malformed (or maliciously
+// crafted) regex can drive that chain very deep with a pile of nested
parentheses and blow the
+// stack; this repository has already seen a stack overflow from deep
recursion (CIR-21633), so
+// there is a hard cap here that errors out instead of recursing further.
+constexpr int kMaxNestingDepth = 64;
+
+// The parser derives conservative literal constraints for the scalar regex
engines.
+// Unsupported syntax fails parsing so the caller can skip gram filtering.
+
+// Infer the byte length of a UTF-8 sequence from its lead byte; an illegal
lead byte counts as a
+// single byte.
+int utf8_len(unsigned char c) {
+ if (c < 0x80) {
+ return 1;
+ }
+ if ((c >> 5) == 0x6) {
+ return 2;
+ }
+ if ((c >> 4) == 0xE) {
+ return 3;
+ }
+ if ((c >> 3) == 0x1E) {
+ return 4;
+ }
+ return 1; // illegal lead byte: treat it as a single byte
+}
+
+// The largest legal Unicode code point. Anything above it can only be a fake
code point minted
+// by decode_one_cp for an ill-formed byte, and must never reach encode_cp:
the four-byte sequence
+// encode_cp would produce encodes a value above U+10FFFF, so it is a byte
string no encoder can
+// emit and no index can hold, and demanding it as a gram would filter every
row away.
+constexpr uint32_t kMaxCodePoint = 0x10FFFF;
+
+// Decode the code point starting at s[0]; s must not be empty. A well-formed
UTF-8 sequence
+// yields its code point and its byte length; any ill-formed byte (an illegal
lead byte, a
+// truncated sequence or a bad continuation byte) yields the fake code point
0x110000+byte (still
+// < 2^21, so it cannot collide with a legal one) and consumes exactly one
byte.
+//
+// *consumed is what keeps a caller's cursor in sync with the decoder.
Advancing by the length
+// guessed from the lead byte instead would swallow the bytes following an
ill-formed sequence --
+// regex metacharacters among them -- and silently compile a different pattern
than the engine
+// sees.
+uint32_t decode_one_cp(std::string_view s, size_t* consumed) {
+ const auto c = static_cast<unsigned char>(s[0]);
+ const int l = utf8_len(c);
+ *consumed = 1;
+ if (l == 1) {
+ return c < 0x80 ? c : 0x110000U + c;
+ }
+ if (static_cast<size_t>(l) > s.size()) {
+ return 0x110000U + c;
+ }
+ uint32_t v = 0;
+ if (l == 2) {
+ v = c & 0x1FU;
+ } else if (l == 3) {
+ v = c & 0x0FU;
+ } else {
+ v = c & 0x07U;
+ }
+ for (int k = 1; k < l; k++) {
+ const auto cc = static_cast<unsigned char>(s[k]);
+ if ((cc & 0xC0) != 0x80) {
+ return 0x110000U + c;
+ }
+ v = (v << 6) | (cc & 0x3FU);
+ }
+ *consumed = static_cast<size_t>(l);
Review Comment:
[P1] Treat overlong UTF-8 as ill-formed here instead of normalizing it. For
example, `C0 AF` is decoded as U+002F and later re-encoded as `/`, so a regexp
literal `abc<C0 AF>def` asks the dense gram index for slash-bearing grams that
a row containing the original bytes never stored (the extractor treats those
bytes as a non-ASCII separator). Hyperscan/RE2 reject this pattern, but with
extended-regex fallback enabled the byte-oriented Boost path can match the
original bytes; intersecting the approximate bitmap then drops a true row
before scalar recheck. The later UTF-8 guard sees only the normalized `/`.
Please reject overlong/surrogate/out-of-range sequences in the decoder and
cover the real Boost fallback path.
##########
fe/fe-core/src/main/java/org/apache/doris/indexpolicy/NGramTokenizerValidator.java:
##########
@@ -103,4 +145,80 @@ protected void validateSpecific(Map<String, String> props)
throws DdlException {
}
}
}
+
+ /**
+ * Validates the gram-family (auto/sparse/dense) parameters: the value
domain of mode itself, the
+ * defaults and the ordering of min/max_gram, the value domains of
density/lower_case, and the
+ * mutual exclusion of the token_chars family with mode.
+ * An empty mode string (which the allow-list stage does not catch) is
rejected here too, for not
+ * belonging to VALID_MODES.
+ *
+ * <p>Every value domain mirrors BE's
`gram_scheme.cpp::GramScheme::from_properties` entry by entry:
+ * min_gram in [1, 64], max_gram in [1, 256], density in [0.001, 1].
+ * FE rejects out-of-range values up front, so a DDL cannot pass only for
BE to report
+ * InvalidArgument when it parses the gram scheme.
+ */
+ private void validateGramMode(Map<String, String> props, String mode)
throws DdlException {
+ if (!VALID_MODES.contains(mode)) {
+ throw new DdlException("ngram tokenizer mode must be one of " +
VALID_MODES
+ + ", got: '" + mode + "'" + (mode.isEmpty() ? " (empty)" :
""));
+ }
+ int minGram = parseIntInRange(props, "min_gram", 3,
MIN_GRAM_LOWER_BOUND, MIN_GRAM_UPPER_BOUND);
+ int maxGram = parseIntInRange(props, "max_gram", 16,
MAX_GRAM_LOWER_BOUND, MAX_GRAM_UPPER_BOUND);
Review Comment:
[P1] Keep the omitted `max_gram` default consistent with BE. This validator
substitutes 16 but does not persist it, while `GramScheme` now defaults the
same missing property to 4. As a result, `mode=sparse,min_gram=5` passes FE DDL
validation and is stored without `max_gram`, then BE rejects `max_len(4) <
min_len(5)` when the SNII writer initializes, so the first load/index build
fails after apparently valid DDL. This is a follow-on to the earlier default
change, not the same issue: please validate against 4 (or persist one canonical
default) and add the omitted-max case.
##########
be/src/storage/index/snii/writer/snii_compound_writer.cpp:
##########
@@ -576,6 +576,9 @@ Status SniiCompoundWriter::write_tail() {
LogicalIndexMetadataRef entry;
entry.index_id = w.index_id();
entry.index_suffix = w.index_suffix();
+ // Inherited groups above never carry this: only a positional index
can be inherited
Review Comment:
[P2] Preserve the dropped-posting feature fence for inherited indexes.
`BUILD INDEX` can put any unchanged docs-only gram index in `inherit_keys`; its
physical dictionary (including locator-less bit-5 entries) and metadata group
are copied verbatim, but `InheritedLogicalIndex`/`InheritedGroup` carries no
dropped-posting or source-feature state, so this reconstructed entry leaves
`dropped_postings=false` and the new directory omits `kFeatureDroppedPostings`.
That reintroduces the old-reader misparse the feature bit was added to prevent.
The inheritance tests use only three rows, below the stop-gram floor. Please
retain the source feature (or per-index state) through the snapshot and cover
an inherited >=2,000-row stopped-posting index.
##########
be/src/storage/index/snii/reader/logical_index_reader.h:
##########
@@ -176,11 +176,23 @@ class LogicalIndexReader {
const format::SectionRefs& section_refs() const { return
core_.section_refs; }
const format::StatsBlock& stats() const { return core_.stats; }
+ // Bounds on the df of this index's most common terms, resident since the
segment was
+ // opened. Lets a caller decide a term is too common to be worth reading
without issuing
+ // the dictionary read that would tell it exactly how common. Empty on
indexes written
+ // before the digest existed, in which case there is no bound and df must
be read.
+ const format::HighDfTerms& high_df_terms() const { return
core_.high_df_terms; }
Review Comment:
[P2] Include the resident high-DF digest in `memory_usage()`. Core-metadata
decode owns up to 4,096 `uint64_t` hashes plus parallel `uint32_t` dfs (about
49 KiB before capacity slack) for the full logical-reader lifetime, but the
searcher-cache charge currently counts the other resident metadata and omits
both vectors. With one reader per cached segment/index this can materially
overrun the configured cache capacity. Please add both capacities with
saturating arithmetic and test that a populated digest increases the cache
charge.
--
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]
