airborne12 commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r3988883883
##########
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:
Confirmed and fixed in d2615d864129c3656abf08e541a84c0563c33845.
Reproduced at SQL level on a live cluster: a tokenizer created with only
`type=ngram, mode=sparse, min_gram=5` passes FE DDL and the table is created,
then the first load fails on the backend with `[E-6011] ... max_gram(4) <
min_gram(5)` and the table stays at 0 rows. So the damage is a table that looks
created and cannot be written, which matches the description.
The validator now substitutes the same defaults `GramScheme` applies --
`min_gram` 3, `max_gram` 4, as named constants rather than literals -- so a DDL
that cannot be written is refused where it is written. Test:
`GramDdlValidationTest#testOmittedMaxGramIsValidatedAgainstTheDefaultBackendApplies`:
the omitted-`max_gram` case is rejected naming `min_gram (5) must be <=
max_gram (4)`, while a spelled-out `max_gram=8` and a `min_gram=3` under the
default both stay accepted.
##########
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:
Confirmed and fixed in b873d817752034eebd3e9ecd233c7e6df82f69c7.
Reproduced at compiler level: `abc<C0 AF>def` compiled to exactly what
`abc/def` compiles to -- `("/de" & "abc" & "bc/" & "c/d" & "def")` -- while a
row holding the original bytes stores only `"xxa" "xab" "abc" "def" "efy"
"fyy"`, none of them slash-bearing. The index therefore answers empty and the
intersection drops a row the byte-oriented fallback would have matched.
The decoder now returns a non-code-point sentinel (`0x110000 + lead byte`)
for overlong, surrogate and out-of-range sequences, so those bytes stay
separators exactly as every other invalid byte does, which is also what the
extractor does with them on the write side. `*consumed` stays 1 on that path,
so the cursor still steps one byte and cannot swallow a following metacharacter.
Test:
`RegexGramCompilerTest.IllFormedUtf8IsNotDecodedIntoTheCodePointItSpells`,
covering the overlong two- and three-byte forms, a surrogate half and a value
above U+10FFFF. To be explicit about what it does not cover: it asserts at
compiler level that the ill-formed pattern no longer compiles to the same query
as `abc/def`, rather than driving a query through the Boost fallback. Getting
those raw bytes into a row and back out through the regression harness is not
something I could make deterministic, and the compiled query is where the
defect lives -- the fallback only makes it observable.
##########
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:
Confirmed, quantified and fixed in b873d817752034eebd3e9ecd233c7e6df82f69c7.
One compile of a single high-entropy literal, ASAN build (absolute numbers
inflated; the shape is the point):
| pattern bytes | before | after |
| --- | --- | --- |
| 256 | 15 ms | 18 ms |
| 512 | 143 ms | 39 ms |
| 1024 | 458 ms | 85 ms |
| 2048 | 2.99 s | 156 ms |
| 4096 | 4.36 s | 335 ms |
| LIKE, 1024 literal segments | 1.98 s | 47 ms |
Before: quadratic, once per segment, non-cancellable, result discarded.
After: 0.082 ms per byte at 1 KiB and 0.082 ms per byte at 4 KiB, so it is
linear.
`GramQuery::and_` and `or_` now return ALL as soon as a merged result passes
`kMaxLeaves`, so neither operand can ever exceed the cap and each step's copy /
dedupe / sort is bounded instead of growing with the pattern.
`RegexGramCompiler::kMaxQueryGrams` now aliases that constant so the two cannot
drift apart.
One consequence worth flagging, because it changes behaviour rather than
only cost: `and_(ALL, x)` is `x`, so an AND that crosses the cap restarts from
the next gram instead of poisoning everything after it. The 4 KiB pattern above
now compiles to a 56-leaf query where it used to compile to ALL. That is still
conservative -- every gram kept is one the pattern requires -- so it filters
where the old code gave up. For OR, ALL is absorbing, so an OR that crosses the
cap stays ALL, which is the only sound answer there.
Test: `GramQueryTest.CombiningStopsOnceThePlanIsPastTheSizeAnyoneWouldUse`
drives both combinators past the cap and requires neither to grow beyond it.
##########
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:
Confirmed and fixed in fd3990cf5cfeec2e972f886790005363947f14ce. Tracing it
turned up two defects, not one:
1. `MetadataDirectory::decode` never set `dropped_postings` on a decoded
entry at all. The flag was only consumed on the encode side, so **every** entry
read back reported `false`, inherited or not.
2. `InheritedLogicalIndex` / `InheritedGroup` carried no such state, so the
re-emitted directory omitted `kFeatureDroppedPostings` exactly as described.
I took the "per-index state" option rather than "retain the source feature",
because retaining the feature is not precise enough: it is raised for the
directory, so carrying it back on every inverted entry makes a rewrite that
keeps only the *non*-dropping indexes declare it anyway, fencing an old reader
off a container that holds nothing it cannot parse. A first attempt did exactly
that and the new inheritance test caught it.
So the fact is now recorded per index, as
`SniiLogicalIndexMetadataPB.dropped_postings` (field 8), written only when true
so a directory that drops nothing keeps its pre-feature bytes -- the same byte
gate `kind` has. The directory-wide required feature stays as the old-reader
fence, and decode now requires the two to agree in both directions, exactly as
the blob feature already does. The snapshot carries the per-index bit through
`load_inherited_index` and `inherit()`, and the stale comment at the new-writer
loop that claimed inherited groups were handled there is corrected.
Tests:
`SniiCompoundWriterInherit.InheritedIndexKeepsTheDroppedPostingDeclaration`
builds a `kHighDfDigestDivisor`-row gram source that really does drop a posting
(asserted, so the test cannot pass for the wrong reason), inherits it alongside
a freshly written index, and requires the first to keep the declaration and the
second not to acquire it.
`SniiMetadataDirectory.ADecodedEntryReportsItsOwnDroppedPostingState` and
`.TheDroppedPostingFeatureAndTheEntriesMustAgree` pin the format half. On your
point that the inheritance suite ran three rows: `test_gram_metadata_inherit`
gained a second table of 4,000 rows in one segment, where the commonest grams
really are over the line, and it compares index-on against index-off on both
sides of a `BUILD INDEX`.
--
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]
