airborne12 commented on code in PR #67538:
URL: https://github.com/apache/doris/pull/67538#discussion_r4012115547
##########
be/src/exprs/function/like.cpp:
##########
@@ -1107,6 +1114,78 @@ Status FunctionRegexpLike::open(FunctionContext* context,
return Status::OK();
}
+// R8 (unity build): file-scope helpers use a namespace private to this file.
+namespace like_gram_index_detail {
+
+// Index acceleration may be skipped, but cancellation and memory failures
stop the query.
+Status dispatch_query(bool is_like, const std::string& pattern,
segment_v2::IndexIterator* iter,
+ const IndexFieldNameAndTypePair& data_type_with_name,
uint32_t num_rows,
+ segment_v2::InvertedIndexResultBitmap* bitmap_result) {
+ segment_v2::InvertedIndexParam param;
+ param.column_name = data_type_with_name.first;
+ param.column_type = data_type_with_name.second;
+ param.query_value = Field::create_field<TYPE_STRING>(pattern);
+ param.query_type = is_like ?
segment_v2::InvertedIndexQueryType::LIKE_GRAM_QUERY
+ :
segment_v2::InvertedIndexQueryType::REGEXP_GRAM_QUERY;
+ param.num_rows = num_rows;
+ param.roaring = std::make_shared<roaring::Roaring>();
+
+ Status query_status = iter->read_from_index(¶m);
+ if (!query_status.ok()) {
+ if (query_status.is<ErrorCode::CANCELLED>() ||
+ query_status.is<ErrorCode::MEM_LIMIT_EXCEEDED>() ||
+ query_status.is<ErrorCode::MEM_ALLOC_FAILED>()) {
+ return query_status;
+ }
+ if (query_status.is<ErrorCode::INVERTED_INDEX_EVALUATE_SKIPPED>() ||
+ query_status.is<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED>()) {
+ return Status::OK();
+ }
+ // Every other error only degrades to "no acceleration". LOG_EVERY_N
rather than VLOG,
+ // because this path already means "the index could not be used" and
deserves a trace at
+ // the default log level, while still not flooding the log once per
segment.
+ LOG_EVERY_N(WARNING, 100) << "gram index push-down skipped,
read_from_index returned "
+ << query_status;
+ return Status::OK();
Review Comment:
Confirmed, and fixed in e38ae946518 and 7212cd27f21.
Before this change, no result was wrong: a failed index read only turned
into a silent full scan. That still skipped the policy every other index
push-down follows, and a user who set
`enable_fallback_on_missing_inverted_index` to false could not see a missing
index.
The gram push-down now handles only a declined index
(`INVERTED_INDEX_EVALUATE_SKIPPED`, `INVERTED_INDEX_NOT_SUPPORTED`) itself and
returns every other status. `SegmentIterator::_downgrade_without_index` then
applies the policy that MATCH, IN, comparison and SEARCH already get:
- `IO_ERROR` fails the query.
- `FILE_NOT_FOUND` follows `enable_fallback_on_missing_inverted_index` and
counts as a downgrade.
Two companion changes keep this from adding new failure paths:
- An SNII index that cannot be a gram index (no analyzer, a built-in
analyzer, or a built-in normalizer) declines a gram query before the result
cache and before any file IO. Without this, a column whose only index is a
keyword or tokenized SNII index would open that file just to decline, and a
storage fault there would fail a LIKE the index can never serve.
- For gram queries, a logical index missing from its SNII container
(`INVERTED_INDEX_SNII_NOT_FOUND`) is reported as
`INVERTED_INDEX_FILE_NOT_FOUND`, so the fallback variable governs it the same
way. MATCH is unchanged.
One visible change: with `enable_fallback_on_missing_inverted_index=false`,
LIKE or REGEXP on a segment written before an `ADD INDEX` that has not been
built yet now fails, as MATCH does. With the default setting it is downgraded,
logged and counted.
Tests:
- `LikeGramIndexTest.IndexFailuresReachTheSegmentIteratorPolicy`: six status
codes for both LIKE and REGEXP.
- `LikeGramIndexTest.DeclinedIndexLeavesTheRowsToThePredicate`
- `SniiGramCacheTest.NonGramIndexDeclinesGramQueriesWithoutOpeningItsFile`
and
`SniiGramCacheTest.BuiltinNormalizerOrAnalyzerIndexDeclinesGramQueriesWithoutOpeningItsFile`:
no result-cache lookup and no searcher-cache miss.
-
`SniiGramCacheTest.GramQueryReportsALogicalIndexMissingFromItsContainerAsAMissingFile`
##########
be/src/storage/index/inverted/gram/regex_ast.cpp:
##########
@@ -0,0 +1,819 @@
+// 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()))) {
Review Comment:
Confirmed, and fixed in 31ab93392ce and 1fca6733f8d.
The three engines disagree on this syntax. Boost 1.81 skips whitespace
around repeat bounds (`parse_repeat_range`), while Hyperscan and RE2 read `a{ 3
}` as literal text. The parser cannot know which engine will run the pattern,
so no single reading of such a brace is safe for the index.
A brace now becomes a repeat only in the form all three engines read alike:
- each bound has 1 to 9 digits;
- no bound has a leading zero;
- there is no whitespace or sign inside the braces.
A brace that no engine treats as a repeat, such as `{,3}`, stays literal.
Any other brace makes the parse fail, so the pattern compiles to ALL.
The sign case came up in our own review of this fix. Boost reads `a{+3}` as
`a{3}` and `a{1,-3}` as `a{1,}`, while Hyperscan and RE2 read both as text. We
then swept every printable byte at each position inside a brace, over all three
engine paths (3429 cases), and found no other brace form that loses rows.
Reproduced on a cluster before the fixes, with an SNII gram index under
dense and sparse schemes and `enable_extended_regex=true`:
- `a{ 3 }timeout++`, `a{3, 4}timeout++` and `a{3, }timeout++` each returned
0 rows with the index and 3 rows without it.
- `a{1,+4}timeout++` and `a{1,-3}timeout++` each returned 0 rows with the
index and 4 rows without it.
Tests:
- `RegexAstTest.BoundedRepeatWithWhitespaceIsRejected` and
`RegexAstTest.SignedRepeatCountsAreRejected`
- `RegexGramRecallTest.BoundedRepeatWithWhitespaceFiltersNothing` and
`RegexGramRecallTest.SignedRepeatCountsFilterNothing`, both checked against the
real scalar engine path.
- Index-on/index-off parity cases in `test_gram_pattern_recall`.
--
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]
