This is an automated email from the ASF dual-hosted git repository.
airborne12 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 80c1a3a2761 [fix](be) Match SNII wildcards by UTF-8 code point (#66861)
80c1a3a2761 is described below
commit 80c1a3a27618667548b9f1af6765747ca6da7c55
Author: Jack <[email protected]>
AuthorDate: Mon Aug 24 16:36:27 2026 +0800
[fix](be) Match SNII wildcards by UTF-8 code point (#66861)
### What problem does this PR solve?
Issue Number: None
Related PR: #66052
Problem Summary:
SNII evaluated wildcard question marks byte by byte, so `a?b` could not
match `a猫b`, while V3 converts `?` to a RE2 dot and matches one Unicode
code point. The SNII matcher now validates UTF-8 and advances its
existing reusable dynamic-programming rows only at code-point
boundaries. This preserves the bounded two-buffer scratch design, makes
invalid patterns return `INVALID_ARGUMENT`, and aligns SNII query
results with V3 without changing the writer or stored bytes.
### Release note
SNII wildcard question marks now match one UTF-8 code point, consistent
with V3.
---
.../index/snii/query/internal/wildcard_matcher.h | 77 +++++++++++---
be/src/storage/index/snii/query/wildcard_query.cpp | 4 +
be/src/storage/index/snii/query/wildcard_query.h | 7 +-
.../index/snii/query/pattern_query_test.cpp | 45 ++++++++
.../storage/index/snii_b2_t08_wildcard_test.cpp | 75 +++++++++++--
.../test_storage_format_snii_utf8_wildcard.out | 22 ++++
.../test_storage_format_snii_utf8_wildcard.groovy | 116 +++++++++++++++++++++
7 files changed, 319 insertions(+), 27 deletions(-)
diff --git a/be/src/storage/index/snii/query/internal/wildcard_matcher.h
b/be/src/storage/index/snii/query/internal/wildcard_matcher.h
index 78eec25097a..06840e2a1e0 100644
--- a/be/src/storage/index/snii/query/internal/wildcard_matcher.h
+++ b/be/src/storage/index/snii/query/internal/wildcard_matcher.h
@@ -20,20 +20,24 @@
#include <algorithm>
#include <cstddef>
#include <cstdint>
+#include <cstring>
#include <memory>
#include <string_view>
#include <vector>
+#include "util/utf8_check.h"
+
namespace doris::snii::query::internal {
-// Glob matcher with reusable scratch. '*' matches >=0 bytes, '?' matches
exactly
-// one byte, every other byte is literal; matching is anchored at both ends
(full
-// match). The matching result is bit-for-bit identical to the former per-call
DP
-// in wildcard_query.cpp: the only change is that the two DP rows are
constructed
-// once and reused (assign(), never reallocated once capacity is large enough)
-// across every term in a single expansion. A whole-dictionary scan therefore
-// performs O(1) heap allocations for scratch instead of O(2N) -- two small
-// std::vector<uint8_t> constructions per visited term.
+// UTF-8 glob matcher with reusable scratch. '*' matches zero or more code
points,
+// '?' matches exactly one code point, and every other code point is literal. A
+// malformed raw dictionary term falls back to the legacy byte semantics
because
+// keyword indexes can legally contain arbitrary VARCHAR bytes.
+// Matching is anchored at both ends. The DP rows are byte-addressed so they
can
+// reuse their storage across dictionary terms, but transitions are written
only
+// at validated UTF-8 boundaries. A whole-dictionary scan therefore performs
O(1)
+// heap allocations for scratch instead of allocating a code-point
representation
+// for every visited term.
//
// The allocator is templated only so deterministic allocation-counting tests
can
// inject a CountingAllocator; production constructs WildcardMatcher<> (default
@@ -43,37 +47,80 @@ namespace doris::snii::query::internal {
template <class Alloc = std::allocator<uint8_t>>
class WildcardMatcher {
public:
- explicit WildcardMatcher(std::string_view pattern) : pattern_(pattern) {}
+ explicit WildcardMatcher(std::string_view pattern)
+ : pattern_(pattern), pattern_valid_(is_valid_utf8(pattern)) {}
bool operator()(std::string_view text) {
+ if (!pattern_valid_) {
+ return false;
+ }
+ const bool use_code_points = is_valid_utf8(text);
+
const size_t n = text.size() + 1;
prev_.assign(n, 0); // reuses the buffer; no realloc once capacity >= n
curr_.assign(n, 0);
prev_[0] = 1;
- for (char p : pattern_) {
+
+ for (size_t pattern_begin = 0; pattern_begin < pattern_.size();) {
+ const size_t pattern_width =
+ use_code_points ?
code_point_width(pattern_[pattern_begin]) : 1;
+ const char pattern_lead = pattern_[pattern_begin];
std::fill(curr_.begin(), curr_.end(), 0);
- if (p == '*') {
+ if (pattern_lead == '*') {
curr_[0] = prev_[0];
- for (size_t i = 1; i < n; ++i) {
- curr_[i] = prev_[i] || curr_[i - 1];
+ for (size_t text_begin = 0; text_begin < text.size();) {
+ const size_t text_end =
+ text_begin + (use_code_points ?
code_point_width(text[text_begin]) : 1);
+ curr_[text_end] = prev_[text_end] || curr_[text_begin];
+ text_begin = text_end;
}
} else {
- for (size_t i = 1; i < n; ++i) {
- curr_[i] = prev_[i - 1] && (p == '?' || p == text[i - 1]);
+ for (size_t text_begin = 0; text_begin < text.size();) {
+ const size_t text_width =
+ use_code_points ?
code_point_width(text[text_begin]) : 1;
+ const size_t text_end = text_begin + text_width;
+ curr_[text_end] = prev_[text_begin] &&
+ (pattern_lead == '?' ||
+ (pattern_width == text_width &&
+ std::memcmp(pattern_.data() +
pattern_begin,
+ text.data() + text_begin,
text_width) == 0));
+ text_begin = text_end;
}
}
prev_.swap(curr_);
+ pattern_begin += pattern_width;
}
return prev_[text.size()] != 0;
}
+ bool pattern_valid() const { return pattern_valid_; }
+
// Test-only debug accessor: the production path never depends on it.
Reports
// the larger of the two scratch-row capacities so perf tests can assert
the
// buffer stops reallocating after warmup.
size_t scratch_capacity() const { return std::max(prev_.capacity(),
curr_.capacity()); }
private:
+ static bool is_valid_utf8(std::string_view text) {
+ return text.empty() || validate_utf8(text.data(), text.size());
+ }
+
+ static size_t code_point_width(char lead) {
+ const auto byte = static_cast<uint8_t>(lead);
+ if (byte < 0x80) {
+ return 1;
+ }
+ if (byte < 0xE0) {
+ return 2;
+ }
+ if (byte < 0xF0) {
+ return 3;
+ }
+ return 4;
+ }
+
std::string_view pattern_;
+ bool pattern_valid_ = false;
std::vector<uint8_t, Alloc> prev_;
std::vector<uint8_t, Alloc> curr_;
};
diff --git a/be/src/storage/index/snii/query/wildcard_query.cpp
b/be/src/storage/index/snii/query/wildcard_query.cpp
index e8313c49979..45282d6f58c 100644
--- a/be/src/storage/index/snii/query/wildcard_query.cpp
+++ b/be/src/storage/index/snii/query/wildcard_query.cpp
@@ -69,6 +69,10 @@ Status wildcard_query(const reader::LogicalIndexReader& idx,
std::string_view pa
// visited dictionary term, so the whole-dictionary scan triggered by a
// leading wildcard performs O(1) scratch allocations instead of O(2N).
internal::WildcardMatcher<> matcher(pattern);
+ if (!matcher.pattern_valid()) {
+ return Status::Error<ErrorCode::INVALID_ARGUMENT, false>(
+ "wildcard_query: pattern is not valid UTF-8");
+ }
return internal::emit_expanded_docid_union(
idx, enum_prefix, [&matcher](std::string_view term) { return
matcher(term); }, sink,
max_expansions);
diff --git a/be/src/storage/index/snii/query/wildcard_query.h
b/be/src/storage/index/snii/query/wildcard_query.h
index 66c08b18ae2..edd6c27a56b 100644
--- a/be/src/storage/index/snii/query/wildcard_query.h
+++ b/be/src/storage/index/snii/query/wildcard_query.h
@@ -26,9 +26,10 @@
#include "storage/index/snii/query/query_profile.h"
#include "storage/index/snii/reader/logical_index_reader.h"
-// wildcard_query -- MATCH_WILDCARD semantics over dictionary terms. `*`
matches
-// any byte sequence, `?` matches one byte, and all other bytes match
literally.
-// Matching terms are executed as a sorted deduplicated docid union.
+// wildcard_query -- MATCH_WILDCARD semantics over UTF-8 dictionary terms. `*`
+// matches any code-point sequence, `?` matches one code point, and all other
code
+// points match literally. Matching terms are executed as a sorted deduplicated
+// docid union.
namespace doris::snii::query {
Status wildcard_query(const reader::LogicalIndexReader& idx, std::string_view
pattern,
diff --git a/be/test/storage/index/snii/query/pattern_query_test.cpp
b/be/test/storage/index/snii/query/pattern_query_test.cpp
index 87e25299a54..be8f603f568 100644
--- a/be/test/storage/index/snii/query/pattern_query_test.cpp
+++ b/be/test/storage/index/snii/query/pattern_query_test.cpp
@@ -197,6 +197,51 @@ TEST(SniiPatternQuery, WildcardMatchesOracle) {
std::remove(path.c_str());
}
+TEST(SniiPatternQuery, WildcardQuestionMarkMatchesUtf8CodePoint) {
+ Corpus corpus;
+ corpus.doc_count = 5;
+ corpus.docs = {{"a猫b"}, {"a🔥b"}, {"a猫猫b"}, {"aéb"}, {"ascii"}};
+ const std::string path = TempPath();
+ WriteCorpus(corpus, path);
+
+ io::LocalFileReader file;
+ SniiSegmentReader segment;
+ LogicalIndexReader idx = OpenIndex(&file, &segment, path);
+
+ std::vector<uint32_t> got;
+ ASSERT_TRUE(query::wildcard_query(idx, "a?b", &got).ok());
+ EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 3}));
+
+ ASSERT_TRUE(query::wildcard_query(idx, "a??b", &got).ok());
+ EXPECT_EQ(got, (std::vector<uint32_t> {2}));
+
+ std::remove(path.c_str());
+}
+
+TEST(SniiPatternQuery,
MalformedKeywordTermsRetainByteCompatibleWildcardMatching) {
+ Corpus corpus;
+ corpus.doc_count = 3;
+ corpus.docs = {{std::string("a\xFF", 2)}, {"ab"}, {"zz"}};
+ const std::string path = TempPath();
+ WriteCorpus(corpus, path);
+
+ io::LocalFileReader file;
+ SniiSegmentReader segment;
+ LogicalIndexReader idx = OpenIndex(&file, &segment, path);
+
+ std::vector<uint32_t> got;
+ ASSERT_TRUE(query::wildcard_query(idx, "a*", &got).ok());
+ EXPECT_EQ(got, (std::vector<uint32_t> {0, 1}));
+
+ ASSERT_TRUE(query::wildcard_query(idx, "**", &got).ok());
+ EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 2}));
+
+ ASSERT_TRUE(query::wildcard_query(idx, "*", &got).ok());
+ EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 2}));
+
+ std::remove(path.c_str());
+}
+
TEST(SniiPatternQuery, RegexpMatchesOracle) {
const Corpus corpus = BuildMixedCorpus();
const std::string path = TempPath();
diff --git a/be/test/storage/index/snii_b2_t08_wildcard_test.cpp
b/be/test/storage/index/snii_b2_t08_wildcard_test.cpp
index 87ce313c99f..b071bc725ea 100644
--- a/be/test/storage/index/snii_b2_t08_wildcard_test.cpp
+++ b/be/test/storage/index/snii_b2_t08_wildcard_test.cpp
@@ -17,12 +17,12 @@
// T08 -- wildcard matcher scratch reuse.
//
-// Proves the request-scoped internal::WildcardMatcher (a) matches bit-for-bit
-// identically to the former per-call DP in wildcard_query.cpp, and (b) reuses
its
-// two DP scratch rows across every visited term so a whole-dictionary scan
-// performs O(1) heap allocations (<= 2) instead of O(2N). A header-only
-// CountingAllocator gives the deterministic allocation counts; a byte-for-byte
-// copy of the original DP serves as the equivalence oracle.
+// Proves the request-scoped internal::WildcardMatcher preserves the former
ASCII
+// behavior while matching UTF-8 code points, and reuses its two DP scratch
rows
+// across every visited term so a whole-dictionary scan performs O(1) heap
+// allocations (<= 2) instead of O(2N). A header-only CountingAllocator gives
the
+// deterministic allocation counts; a byte-for-byte copy of the original DP
+// serves as the ASCII equivalence oracle.
#include <gtest/gtest.h>
@@ -155,7 +155,7 @@ std::vector<std::string> make_varied_length_terms(size_t
count, size_t max_len)
return terms;
}
-// W-EQ-DP: the optimized matcher reproduces the reference DP bit-for-bit over
an
+// W-EQ-DP: the optimized matcher reproduces the reference DP for ASCII over an
// exhaustive small-alphabet battery (covers "", leading/trailing '*'/'?',
// consecutive "**", '?' interplay) plus realistic dictionary patterns/terms.
One
// matcher is reused across all terms of a pattern, so this also proves scratch
@@ -212,12 +212,69 @@ TEST(SniiWildcardQueryTest, StarMatchesEverything) {
EXPECT_TRUE(matcher("xyz"));
}
-// W-QMARK: "?" matches exactly one byte.
-TEST(SniiWildcardQueryTest, QuestionMarkMatchesExactlyOneByte) {
+// W-QMARK: "?" matches exactly one UTF-8 code point.
+TEST(SniiWildcardQueryTest, QuestionMarkMatchesExactlyOneUtf8CodePoint) {
internal::WildcardMatcher<> matcher("?");
EXPECT_FALSE(matcher(""));
EXPECT_TRUE(matcher("a"));
+ EXPECT_TRUE(matcher("猫"));
+ EXPECT_TRUE(matcher("🔥"));
EXPECT_FALSE(matcher("ab"));
+
+ internal::WildcardMatcher<> surrounded("a?b");
+ EXPECT_TRUE(surrounded("a猫b"));
+ EXPECT_TRUE(surrounded("a🔥b"));
+ EXPECT_FALSE(surrounded("a猫猫b"));
+
+ internal::WildcardMatcher<> three("a???b");
+ EXPECT_FALSE(three("a猫b"));
+ EXPECT_TRUE(three("a猫🔥éb"));
+
+ internal::WildcardMatcher<> star_then_two("a*??b");
+ EXPECT_FALSE(star_then_two("a猫b"));
+ EXPECT_TRUE(star_then_two("a猫🔥b"));
+}
+
+// W-UTF8-LITERAL: non-ASCII literals are compared as complete code points.
+TEST(SniiWildcardQueryTest, Utf8LiteralsMatchCompleteCodePoints) {
+ internal::WildcardMatcher<> matcher("猫?火");
+ EXPECT_TRUE(matcher("猫🔥火"));
+ EXPECT_FALSE(matcher("猫🔥🔥火"));
+ EXPECT_FALSE(matcher("狗🔥火"));
+}
+
+// W-INVALID-UTF8: patterns remain strict UTF-8, while malformed raw keyword
+// terms retain the byte-wise semantics used before code-point matching.
+TEST(SniiWildcardQueryTest, MalformedTermsRetainByteCompatibleMatching) {
+ const std::string invalid_lead("\xff", 1);
+ const std::string truncated("\xe7\x8c", 2);
+ const std::string invalid_continuation("\xe7x\xab", 3);
+
+ internal::WildcardMatcher<> any("*");
+ EXPECT_TRUE(any(invalid_lead));
+ EXPECT_TRUE(any(truncated));
+ EXPECT_TRUE(any(invalid_continuation));
+
+ internal::WildcardMatcher<> two_bytes("??");
+ EXPECT_FALSE(two_bytes(invalid_lead));
+ EXPECT_TRUE(two_bytes(truncated));
+ EXPECT_FALSE(two_bytes(invalid_continuation));
+
+ internal::WildcardMatcher<> invalid_pattern(invalid_lead);
+ EXPECT_FALSE(invalid_pattern(invalid_lead));
+ EXPECT_FALSE(invalid_pattern("猫"));
+}
+
+TEST(SniiWildcardQueryTest, InvalidUtf8PatternReturnsInvalidArgument) {
+ MemoryFile file;
+ reader::SniiSegmentReader segment_reader;
+ reader::LogicalIndexReader index_reader;
+ assert_ok(build_reader(&file, &segment_reader, &index_reader));
+
+ const std::string invalid_pattern("\xff*", 2);
+ std::vector<uint32_t> docids;
+ EXPECT_TRUE(wildcard_query(index_reader, invalid_pattern, &docids)
+ .is<doris::ErrorCode::INVALID_ARGUMENT>());
}
// W-CONSEC-STAR: consecutive '*' degrade gracefully.
diff --git
a/regression-test/data/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.out
b/regression-test/data/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.out
new file mode 100644
index 00000000000..5eb02995ec5
--- /dev/null
+++
b/regression-test/data/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.out
@@ -0,0 +1,22 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !malformed_keyword_wildcards --
+double_star 7 61FF
+prefix 7 61FF
+single_star 7 61FF
+
+-- !utf8_single_code_point --
+SNII 1
+SNII 2
+SNII 4
+V3 1
+V3 2
+V3 4
+
+-- !utf8_two_code_points --
+SNII 3
+V3 3
+
+-- !utf8_three_code_points --
+SNII 0
+V3 0
+
diff --git
a/regression-test/suites/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.groovy
b/regression-test/suites/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.groovy
new file mode 100644
index 00000000000..f069ea44c32
--- /dev/null
+++
b/regression-test/suites/inverted_index_p0/storage_format/test_storage_format_snii_utf8_wildcard.groovy
@@ -0,0 +1,116 @@
+// 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.
+
+suite("test_storage_format_snii_utf8_wildcard", "p0, nonConcurrent") {
+ sql "DROP TABLE IF EXISTS test_snii_utf8_wildcard"
+ sql "DROP TABLE IF EXISTS test_v3_utf8_wildcard"
+
+ sql """
+ CREATE TABLE test_snii_utf8_wildcard (
+ id INT,
+ body VARCHAR(100),
+ INDEX idx_body (`body`) USING INVERTED
+ ) ENGINE=OLAP
+ DUPLICATE KEY(`id`)
+ DISTRIBUTED BY RANDOM BUCKETS 1
+ PROPERTIES (
+ "replication_allocation" = "tag.location.default: 1",
+ "inverted_index_storage_format" = "SNII"
+ )
+ """
+
+ sql """
+ CREATE TABLE test_v3_utf8_wildcard (
+ id INT,
+ body VARCHAR(100),
+ INDEX idx_body (`body`) USING INVERTED
+ ) ENGINE=OLAP
+ DUPLICATE KEY(`id`)
+ DISTRIBUTED BY RANDOM BUCKETS 1
+ PROPERTIES (
+ "replication_allocation" = "tag.location.default: 1",
+ "inverted_index_storage_format" = "V3"
+ )
+ """
+
+ sql """
+ INSERT INTO test_snii_utf8_wildcard VALUES
+ (1, 'a猫b'),
+ (2, 'a🔥b'),
+ (3, 'a猫猫b'),
+ (4, 'aéb'),
+ (5, 'ascii'),
+ (6, NULL),
+ (7, CAST(UNHEX('61FF') AS STRING))
+ """
+ sql """
+ INSERT INTO test_v3_utf8_wildcard
+ SELECT * FROM test_snii_utf8_wildcard
+ """
+ sql "sync"
+
+ order_qt_malformed_keyword_wildcards """
+ SELECT pattern, id, HEX(body)
+ FROM (
+ SELECT 'prefix' AS pattern, id, body FROM test_snii_utf8_wildcard
+ WHERE id = 7 AND SEARCH('body:a*', '{"mode":"standard"}')
+ UNION ALL
+ SELECT 'double_star' AS pattern, id, body FROM
test_snii_utf8_wildcard
+ WHERE id = 7 AND SEARCH('body:**', '{"mode":"standard"}')
+ UNION ALL
+ SELECT 'single_star' AS pattern, id, body FROM
test_snii_utf8_wildcard
+ WHERE id = 7 AND SEARCH('body:*', '{"mode":"standard"}')
+ ) results
+ ORDER BY pattern, id
+ """
+
+ order_qt_utf8_single_code_point """
+ SELECT format, id
+ FROM (
+ SELECT 'SNII' AS format, id FROM test_snii_utf8_wildcard
+ WHERE SEARCH('body:a?b', '{"mode":"standard"}')
+ UNION ALL
+ SELECT 'V3' AS format, id FROM test_v3_utf8_wildcard
+ WHERE SEARCH('body:a?b', '{"mode":"standard"}')
+ ) results
+ ORDER BY format, id
+ """
+
+ order_qt_utf8_two_code_points """
+ SELECT format, id
+ FROM (
+ SELECT 'SNII' AS format, id FROM test_snii_utf8_wildcard
+ WHERE SEARCH('body:a??b', '{"mode":"standard"}')
+ UNION ALL
+ SELECT 'V3' AS format, id FROM test_v3_utf8_wildcard
+ WHERE SEARCH('body:a??b', '{"mode":"standard"}')
+ ) results
+ ORDER BY format, id
+ """
+
+ order_qt_utf8_three_code_points """
+ SELECT format, matched
+ FROM (
+ SELECT 'SNII' AS format, COUNT(*) AS matched FROM
test_snii_utf8_wildcard
+ WHERE SEARCH('body:a???b', '{"mode":"standard"}')
+ UNION ALL
+ SELECT 'V3' AS format, COUNT(*) AS matched FROM test_v3_utf8_wildcard
+ WHERE SEARCH('body:a???b', '{"mode":"standard"}')
+ ) results
+ ORDER BY format
+ """
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
