airborne12 commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r4001445072
##########
be/src/storage/index/snii/snii_index_reader.cpp:
##########
@@ -156,6 +164,27 @@ bool uses_phrase_frequency_scoring(InvertedIndexQueryType
query_type,
query_type == InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY);
}
+// Query types whose answer is decided by terms the current analyzer produced.
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. MATCH_REGEXP belongs here even
though its
+// pattern is raw: the scalar function matches that pattern against the terms
the current
+// analyzer cuts each row into, while the index matches it against the
persisted dictionary,
+// so the two answer the same question only when both were cut alike. A gram
query compiles
+// against the segment's own scheme, so it is not affected.
+bool analyzes_query_terms(InvertedIndexQueryType query_type) {
+ switch (query_type) {
+ case InvertedIndexQueryType::MATCH_ANY_QUERY:
Review Comment:
Confirmed, and it bites without any policy being recreated. Fixed in
580aaec6019.
Reproduced on a live cluster:
- Recovery, as you describe: a dense-3 table dropped, its analyzer recreated
under the same name as dense-4, then `RECOVER`, with two rows that only dense-3
grams match. SEARCH returned `[]` with the inverted index result cache off, and
`[1,2,5,6]` -- the bitmap cached before the recovery -- with it on, where
MATCH_ANY evaluated row by row answers `[1,2]`.
- A sparse index with adaptive density on (the default), 60,000
httplogs-like rows, nothing recreated. Each segment persists the density it
solved from its own rows, so its scheme differs from the policy's whenever the
two densities do. MATCH is fenced on such a segment and rescans, but EQUAL
looked the policy-density grams up in a dictionary cut at the segment's
density: `search('msg:images')` returned 0 rows, while MATCH_ANY returned
17,143 with the index off and on. A value that cuts no gram at all, such as
`download`, failed with `[E-6005] token parser result is empty`.
Fencing EQUAL alone would turn the sparse case into a hard error on every
segment whose density moved, because SEARCH has no row fallback
(`prevent_search_row_fallback`). A gram index only accelerates LIKE and REGEXP,
so the change has two parts:
- `FieldReaderResolver::resolve` refuses a gram-family reader for every
clause type, with INVERTED_INDEX_NOT_SUPPORTED: `SEARCH cannot use gram index
'<index>' on field '<field>': a gram index only accelerates LIKE and REGEXP`.
`is_gram_family()` is decided from the index properties and the in-memory
policy, without opening the index.
- The SNII reader treats EQUAL on a FULLTEXT reader as an analyzed query, so
a scheme mismatch returns EVALUATE_SKIPPED once the segment is open and such a
query is never cached; nothing scheme-blind lands in the result cache for
another caller.
One limit stays on the FE side: SEARCH binds a field to the first analyzed
index of its column (`OlapTable.getInvertedIndex`), so a column whose gram
index is declared before an ordinary analyzed index gets the error above
instead of using the second index. Declaring the ordinary index first works,
and `test_gram_index_order` covers that.
Tests: `FunctionSearchTest.TestFieldReaderResolverRejectsGramIndex`
(MATCH_ANY, EQUAL and WILDCARD against a gram-family reader), and
`SniiGramCacheTest.AnalyzedQueriesDeclineWhenTheAnalyzerNoLongerCutsGrams`,
which now includes EQUAL and requires EVALUATE_SKIPPED twice with neither a
cache insert nor a hit. Both failed against the previous code: the resolver
accepted the reader, and EQUAL returned OK. `test_gram_index_order` gained a
SEARCH phase: on a gram-only column `search('msg:deadline')` must fail with the
`gram index` error, which the previous build did not raise, and with an english
index declared before the gram index it returns `[10]`.
`test_gram_policy_recovery` runs SEARCH TERM and EXACT (`msg:abcdef`,
`msg:EXACT(abcdef)`) on the dense-3 table recovered under the dense-4 analyzer
and requires the same error. With both fixes, 1,651 BE unit tests from the
gram, SNII, SEARCH, MATCH and iterator suites ran: 1,646 passed, and the 5 that
need an external corpus skipped. On
the bench build all eight gram regression suites pass, including those two
SEARCH phases.
##########
be/src/storage/index/inverted/gram/regex_ast.cpp:
##########
@@ -0,0 +1,813 @@
+// 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);
+ }
+ // A sequence can be well-formed byte by byte and still be ill-formed as
UTF-8. Decoding one
+ // to the code point it spells would be worse than dropping it, because
the compiler would
+ // then demand grams of that code point's canonical encoding -- bytes the
row never held. The
+ // extractor treats these bytes as a separator and stores no gram across
them, so a row
+ // holding `C0 AF` stores nothing for `/`, while `C0 AF` decoded as U+002F
asks for `/`
+ // grams and would filter that row away. Three shapes are rejected here:
+ // - overlong: fewer bits set than the length promises (`C0 AF` for
U+002F);
+ // - surrogate halves U+D800..U+DFFF, which UTF-8 may not encode;
+ // - anything above U+10FFFF.
+ static constexpr uint32_t kOverlongFloor[5] = {0, 0, 0x80, 0x800, 0x10000};
+ if (v < kOverlongFloor[l] || (v >= 0xD800U && v <= 0xDFFFU) || v >
kMaxCodePoint) {
+ return 0x110000U + c;
+ }
+ *consumed = static_cast<size_t>(l);
+ return v;
+}
+
+// Encode one code point as UTF-8 and append it to out.
+void encode_cp(uint32_t cp, std::string* out) {
+ if (cp < 0x80) {
+ out->push_back((char)cp);
+ } else if (cp < 0x800) {
+ out->push_back((char)(0xC0 | (cp >> 6)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ } else if (cp < 0x10000) {
+ out->push_back((char)(0xE0 | (cp >> 12)));
+ out->push_back((char)(0x80 | ((cp >> 6) & 0x3F)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ } else {
+ out->push_back((char)(0xF0 | (cp >> 18)));
+ out->push_back((char)(0x80 | ((cp >> 12) & 0x3F)));
+ out->push_back((char)(0x80 | ((cp >> 6) & 0x3F)));
+ out->push_back((char)(0x80 | (cp & 0x3F)));
+ }
+}
+
+using NP = std::unique_ptr<RegexNode>;
+
+NP mk(RegexNode::Type t) {
+ auto p = std::make_unique<RegexNode>();
+ p->type = t;
+ return p;
+}
+
+// ASCII K and S also match the Kelvin sign and long s under the scalar
engines' Unicode
+// case-insensitive matching. Keep the same expansion for literals and small
character classes.
+void append_ascii_case_variants(uint32_t cp, std::vector<std::string>* items) {
+ items->emplace_back(1, static_cast<char>(cp));
+ const uint32_t lower = cp >= 'A' && cp <= 'Z' ? cp + ('a' - 'A') : cp;
+ if (lower < 'a' || lower > 'z') {
+ return;
+ }
+ items->emplace_back(1, static_cast<char>(cp == lower ? cp - ('a' - 'A') :
lower));
+ if (lower == 'k') {
+ items->emplace_back("K");
+ } else if (lower == 's') {
+ items->emplace_back("ſ");
+ }
+}
+
+// Recursive-descent parser for the supported regex subset.
+struct Parser {
+ std::string_view p;
+ size_t i = 0;
+ bool icase = false;
+ bool ok = true;
+ std::string err;
+ int depth = 0; // current group nesting depth, see kMaxNestingDepth
+
+ explicit Parser(std::string_view s) : p(s) {}
+
+ bool eof() const { return i >= p.size(); }
+ char peek() const { return eof() ? 0 : p[i]; }
+
+ uint32_t next_cp(std::string* utf8) {
+ if (eof()) {
+ // Defensive fallback: every normal call site checks that a
character is still
+ // available before entering next_cp; this merely distrusts the
caller and avoids an
+ // out-of-bounds p[i] read at i==size() on a string_view, which --
unlike the
+ // std::string the prototype used -- is not guaranteed to be
NUL-terminated.
+ utf8->clear();
+ return 0;
+ }
+ // Advance by however many bytes the decoder actually consumed, never
by the length
+ // guessed from the lead byte: an ill-formed sequence consumes exactly
one byte, and
+ // advancing further would swallow the bytes that follow it --
including a regex
+ // metacharacter that may sit there -- and compile a pattern the
engine never saw.
+ size_t consumed = 0;
+ const uint32_t cp = decode_one_cp(p.substr(i), &consumed);
+ *utf8 = std::string(p.substr(i, consumed));
+ i += consumed;
+ return cp;
+ }
+
+ NP parse() {
+ NP r = parse_alt();
+ if (!eof()) {
+ ok = false;
+ err = "trailing input at " + std::to_string(i);
+ }
+ return r;
+ }
+
+ NP parse_alt() {
+ std::vector<NP> branches;
+ branches.push_back(parse_cat());
+ while (peek() == '|') {
+ i++;
+ branches.push_back(parse_cat());
+ }
+ if (branches.size() == 1) {
+ return std::move(branches[0]);
+ }
+ NP a = mk(RegexNode::Type::ALT);
+ a->kids = std::move(branches);
+ return a;
+ }
+
+ NP parse_cat() {
+ NP c = mk(RegexNode::Type::CAT);
+ while (!eof() && peek() != '|' && peek() != ')') {
+ if (peek() == '\\' && i + 1 < p.size() && p[i + 1] == 'Q') {
+ append_quoted_literals(&c->kids);
+ if (!c->kids.empty()) {
+ // A quote adds individual literal atoms. If it is empty,
a following
+ // quantifier still applies to the preceding atom,
including a group or
+ // repeat. Keep this token boundary: '+\\Q\\E?' must not
become lazy '+?'.
+ c->kids.back() = parse_quant(std::move(c->kids.back()));
+ }
+ continue;
+ }
+ NP atom = parse_atom();
+ if (!ok) {
+ return c;
+ }
+ if (!atom) {
+ continue; // e.g. a flags-only empty atom such as (?i)
+ }
+ atom = parse_quant(std::move(atom));
+ c->kids.push_back(std::move(atom));
+ }
+ return c;
+ }
+
+ void append_quoted_literals(std::vector<NP>* atoms) {
+ i += 2; // '\\Q'
+ while (!eof() && !(peek() == '\\' && i + 1 < p.size() && p[i + 1] ==
'E')) {
+ std::string utf8;
+ atoms->push_back(make_lit(next_cp(&utf8)));
+ }
+ if (!eof()) {
+ i += 2; // '\\E'
+ }
+ }
+
+ NP parse_quant(NP a) {
+ while (!eof()) {
+ char c = peek();
+ if (c == '*') {
+ i++;
+ NP s = mk(RegexNode::Type::STAR);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '+') {
+ i++;
+ NP s = mk(RegexNode::Type::PLUS);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '?') {
+ i++;
+ NP s = mk(RegexNode::Type::QUEST);
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else if (c == '{') {
+ size_t save = i;
+ i++;
+ int mn = 0;
+ int mx = -1;
+ bool has = false;
+ while (!eof() && std::isdigit(static_cast<unsigned
char>(peek()))) {
+ mn = mn * 10 + (peek() - '0');
+ i++;
+ has = true;
+ }
+ if (!has) {
+ i = save;
+ break;
+ }
+ if (peek() == ',') {
+ i++;
+ if (std::isdigit(static_cast<unsigned char>(peek()))) {
+ mx = 0;
+ while (!eof() && std::isdigit(static_cast<unsigned
char>(peek()))) {
+ mx = mx * 10 + (peek() - '0');
+ i++;
+ }
+ }
+ } else {
+ mx = mn;
+ }
+ if (peek() != '}') {
+ i = save;
+ break;
+ }
+ i++;
+ NP s = mk(RegexNode::Type::REPEAT);
+ s->rmin = mn;
+ s->rmax = mx;
+ s->kids.push_back(std::move(a));
+ a = std::move(s);
+ } else {
+ break;
+ }
+ if (peek() == '?') {
+ i++; // a lazy quantifier does not change the match set
+ }
+ }
+ return a;
+ }
+
+ // Hex value of a `\x` escape in class_escape: on entry "\x" has already
been consumed (i
+ // points at the brace or at the first hex digit). Ruling R12: the
`\x{...}` form requires at
+ // least one hex digit inside the braces and the braces must be closed;
the bare `\xHH` form
+ // requires exactly two hex digits, and anything shorter (end of string,
or a non-hex
+ // character) is an error, matching RE2's rejection of `\x4`. On success
the value is written
+ // to *v and true is returned; on failure ok=false and err are set and
false is returned (the
+ // caller then returns immediately). Split out of class_escape to reduce
its
+ // complexity/length; the semantics are identical to the original inline
code.
+ bool parse_hex_escape_value(uint32_t* v) {
+ *v = 0;
+ if (peek() == '{') {
+ i++;
+ int cnt = 0;
+ while (!eof() && peek() != '}') {
+ if (!std::isxdigit(static_cast<unsigned char>(peek()))) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ *v = *v * 16 +
+ (std::isdigit(static_cast<unsigned char>(peek()))
+ ? peek() - '0'
+ : (std::tolower(static_cast<unsigned
char>(peek())) - 'a' + 10));
+ i++;
+ cnt++;
+ }
+ if (eof() || cnt == 0) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ i++; // consume '}'
+ return true;
+ }
+ for (int cnt = 0; cnt < 2; cnt++) {
+ if (eof() || !std::isxdigit(static_cast<unsigned char>(peek()))) {
+ ok = false;
+ err = "bad \\x escape";
+ return false;
+ }
+ *v = *v * 16 +
+ (std::isdigit(static_cast<unsigned char>(peek()))
+ ? peek() - '0'
+ : (std::tolower(static_cast<unsigned char>(peek()))
- 'a' + 10));
+ i++;
+ }
+ return true;
+ }
+
+ // Decode only character escapes whose meaning is shared by the scalar
engines. Other
+ // letter/digit escapes may denote assertions, classes or backreferences;
treating them as
+ // literals could exclude matching rows. Three-digit octal avoids short
numeric escapes'
+ // ambiguity with backreferences.
+ bool parse_character_escape(uint32_t* cp) {
+ const char c = p[i++];
+ switch (c) {
+ case 'a':
+ *cp = '\a';
+ return true;
+ case 'f':
+ *cp = '\f';
+ return true;
+ case 'n':
+ *cp = '\n';
+ return true;
+ case 'r':
+ *cp = '\r';
+ return true;
+ case 't':
+ *cp = '\t';
+ return true;
+ case 'x':
+ return parse_hex_escape_value(cp);
+ default:
+ if (c >= '0' && c <= '7' && i + 1 < p.size() && p[i] >= '0' &&
p[i] <= '7' &&
Review Comment:
Confirmed, and an ill-formed byte is not the only road to Boost. Fixed in
77c056136a2.
Boost runs a REGEXP pattern only with `enable_extended_regex` on, after
Hyperscan and RE2 have both rejected it, and the gram parser still sees that
pattern. Recall cases on the real scalar engine, each asserting that Boost is
the engine that ran:
- `\xFF` + `ab\0141cdtimeout`: Boost matched `\xFFabacdtimeout`, which was
not a candidate under any of the four dense/sparse x lower_case schemes.
- `\xFF` + `(x)ab\141cdtimeout`: Boost matched `\xFFxabx41cdtimeout` --
backreference 1, then `41` -- which was not a candidate under two of the four.
- `(x)ab\141cd++timeout`, every byte well-formed: Hyperscan and RE2 reject
the possessive quantifier, and Boost matched `xabx41cdtimeout`, not a candidate
under two of the four.
A rule keyed to ill-formed bytes would still lose the third row, and which
engine runs a pattern is decided outside the index. The parser now decodes a
numeric escape in one form only, `\0dd` with no octal digit after it, which
Hyperscan, RE2 and Boost read alike; any other numeric escape is unsupported
and the whole pattern compiles to ALL, whichever engine runs it. So `\141`,
`[\141]` and `\0141` stop pruning under Hyperscan and RE2 as well, while `\061`
and `[\061]` keep pruning and are pinned on all three engines.
Tests:
`RegexGramRecallTest.NumericEscapesBoostReadsDifferentlyFilterNothing` requires
ALL for the three cases above, and pruning for `\061` and `[\061]` behind an
ill-formed byte on Boost. `EscapesPreserveScalarRecall` now requires ALL for
`\141`, `[\141]` and `\0141` on Hyperscan, `Re2FallbackEngineMatrix` requires
it for `[\141]` on RE2, and both require pruning for the `\061` forms. Against
the previous parser the matched row was lost in 8 scheme runs, and none of the
ambiguous forms compiled to ALL. With both fixes, 1,651 BE unit tests from the
gram, SNII, SEARCH, MATCH and iterator suites ran: 1,646 passed, and the 5 that
need an external corpus skipped. On the bench build `test_gram_pattern_recall`,
which queries `ab\141cdtimeout` and `ab[\141]cdtimeout` on every scheme,
returns the same rows with the index on and off, and all eight gram suites pass.
--
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]
