Skip to content

Commit 80c1a3a

Browse files
authored
[fix](be) Match SNII wildcards by UTF-8 code point (apache#66861)
### What problem does this PR solve? Issue Number: None Related PR: apache#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.
1 parent 7191837 commit 80c1a3a

7 files changed

Lines changed: 319 additions & 27 deletions

File tree

‎be/src/storage/index/snii/query/internal/wildcard_matcher.h‎

Lines changed: 62 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -20,20 +20,24 @@
2020
#include <algorithm>
2121
#include <cstddef>
2222
#include <cstdint>
23+
#include <cstring>
2324
#include <memory>
2425
#include <string_view>
2526
#include <vector>
2627

28+
#include "util/utf8_check.h"
29+
2730
namespace doris::snii::query::internal {
2831

29-
// Glob matcher with reusable scratch. '*' matches >=0 bytes, '?' matches exactly
30-
// one byte, every other byte is literal; matching is anchored at both ends (full
31-
// match). The matching result is bit-for-bit identical to the former per-call DP
32-
// in wildcard_query.cpp: the only change is that the two DP rows are constructed
33-
// once and reused (assign(), never reallocated once capacity is large enough)
34-
// across every term in a single expansion. A whole-dictionary scan therefore
35-
// performs O(1) heap allocations for scratch instead of O(2N) -- two small
36-
// std::vector<uint8_t> constructions per visited term.
32+
// UTF-8 glob matcher with reusable scratch. '*' matches zero or more code points,
33+
// '?' matches exactly one code point, and every other code point is literal. A
34+
// malformed raw dictionary term falls back to the legacy byte semantics because
35+
// keyword indexes can legally contain arbitrary VARCHAR bytes.
36+
// Matching is anchored at both ends. The DP rows are byte-addressed so they can
37+
// reuse their storage across dictionary terms, but transitions are written only
38+
// at validated UTF-8 boundaries. A whole-dictionary scan therefore performs O(1)
39+
// heap allocations for scratch instead of allocating a code-point representation
40+
// for every visited term.
3741
//
3842
// The allocator is templated only so deterministic allocation-counting tests can
3943
// inject a CountingAllocator; production constructs WildcardMatcher<> (default
@@ -43,37 +47,80 @@ namespace doris::snii::query::internal {
4347
template <class Alloc = std::allocator<uint8_t>>
4448
class WildcardMatcher {
4549
public:
46-
explicit WildcardMatcher(std::string_view pattern) : pattern_(pattern) {}
50+
explicit WildcardMatcher(std::string_view pattern)
51+
: pattern_(pattern), pattern_valid_(is_valid_utf8(pattern)) {}
4752

4853
bool operator()(std::string_view text) {
54+
if (!pattern_valid_) {
55+
return false;
56+
}
57+
const bool use_code_points = is_valid_utf8(text);
58+
4959
const size_t n = text.size() + 1;
5060
prev_.assign(n, 0); // reuses the buffer; no realloc once capacity >= n
5161
curr_.assign(n, 0);
5262
prev_[0] = 1;
53-
for (char p : pattern_) {
63+
64+
for (size_t pattern_begin = 0; pattern_begin < pattern_.size();) {
65+
const size_t pattern_width =
66+
use_code_points ? code_point_width(pattern_[pattern_begin]) : 1;
67+
const char pattern_lead = pattern_[pattern_begin];
5468
std::fill(curr_.begin(), curr_.end(), 0);
55-
if (p == '*') {
69+
if (pattern_lead == '*') {
5670
curr_[0] = prev_[0];
57-
for (size_t i = 1; i < n; ++i) {
58-
curr_[i] = prev_[i] || curr_[i - 1];
71+
for (size_t text_begin = 0; text_begin < text.size();) {
72+
const size_t text_end =
73+
text_begin + (use_code_points ? code_point_width(text[text_begin]) : 1);
74+
curr_[text_end] = prev_[text_end] || curr_[text_begin];
75+
text_begin = text_end;
5976
}
6077
} else {
61-
for (size_t i = 1; i < n; ++i) {
62-
curr_[i] = prev_[i - 1] && (p == '?' || p == text[i - 1]);
78+
for (size_t text_begin = 0; text_begin < text.size();) {
79+
const size_t text_width =
80+
use_code_points ? code_point_width(text[text_begin]) : 1;
81+
const size_t text_end = text_begin + text_width;
82+
curr_[text_end] = prev_[text_begin] &&
83+
(pattern_lead == '?' ||
84+
(pattern_width == text_width &&
85+
std::memcmp(pattern_.data() + pattern_begin,
86+
text.data() + text_begin, text_width) == 0));
87+
text_begin = text_end;
6388
}
6489
}
6590
prev_.swap(curr_);
91+
pattern_begin += pattern_width;
6692
}
6793
return prev_[text.size()] != 0;
6894
}
6995

96+
bool pattern_valid() const { return pattern_valid_; }
97+
7098
// Test-only debug accessor: the production path never depends on it. Reports
7199
// the larger of the two scratch-row capacities so perf tests can assert the
72100
// buffer stops reallocating after warmup.
73101
size_t scratch_capacity() const { return std::max(prev_.capacity(), curr_.capacity()); }
74102

75103
private:
104+
static bool is_valid_utf8(std::string_view text) {
105+
return text.empty() || validate_utf8(text.data(), text.size());
106+
}
107+
108+
static size_t code_point_width(char lead) {
109+
const auto byte = static_cast<uint8_t>(lead);
110+
if (byte < 0x80) {
111+
return 1;
112+
}
113+
if (byte < 0xE0) {
114+
return 2;
115+
}
116+
if (byte < 0xF0) {
117+
return 3;
118+
}
119+
return 4;
120+
}
121+
76122
std::string_view pattern_;
123+
bool pattern_valid_ = false;
77124
std::vector<uint8_t, Alloc> prev_;
78125
std::vector<uint8_t, Alloc> curr_;
79126
};

‎be/src/storage/index/snii/query/wildcard_query.cpp‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -69,6 +69,10 @@ Status wildcard_query(const reader::LogicalIndexReader& idx, std::string_view pa
6969
// visited dictionary term, so the whole-dictionary scan triggered by a
7070
// leading wildcard performs O(1) scratch allocations instead of O(2N).
7171
internal::WildcardMatcher<> matcher(pattern);
72+
if (!matcher.pattern_valid()) {
73+
return Status::Error<ErrorCode::INVALID_ARGUMENT, false>(
74+
"wildcard_query: pattern is not valid UTF-8");
75+
}
7276
return internal::emit_expanded_docid_union(
7377
idx, enum_prefix, [&matcher](std::string_view term) { return matcher(term); }, sink,
7478
max_expansions);

‎be/src/storage/index/snii/query/wildcard_query.h‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -26,9 +26,10 @@
2626
#include "storage/index/snii/query/query_profile.h"
2727
#include "storage/index/snii/reader/logical_index_reader.h"
2828

29-
// wildcard_query -- MATCH_WILDCARD semantics over dictionary terms. `*` matches
30-
// any byte sequence, `?` matches one byte, and all other bytes match literally.
31-
// Matching terms are executed as a sorted deduplicated docid union.
29+
// wildcard_query -- MATCH_WILDCARD semantics over UTF-8 dictionary terms. `*`
30+
// matches any code-point sequence, `?` matches one code point, and all other code
31+
// points match literally. Matching terms are executed as a sorted deduplicated
32+
// docid union.
3233
namespace doris::snii::query {
3334

3435
Status wildcard_query(const reader::LogicalIndexReader& idx, std::string_view pattern,

‎be/test/storage/index/snii/query/pattern_query_test.cpp‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -197,6 +197,51 @@ TEST(SniiPatternQuery, WildcardMatchesOracle) {
197197
std::remove(path.c_str());
198198
}
199199

200+
TEST(SniiPatternQuery, WildcardQuestionMarkMatchesUtf8CodePoint) {
201+
Corpus corpus;
202+
corpus.doc_count = 5;
203+
corpus.docs = {{"a猫b"}, {"a🔥b"}, {"a猫猫b"}, {"aéb"}, {"ascii"}};
204+
const std::string path = TempPath();
205+
WriteCorpus(corpus, path);
206+
207+
io::LocalFileReader file;
208+
SniiSegmentReader segment;
209+
LogicalIndexReader idx = OpenIndex(&file, &segment, path);
210+
211+
std::vector<uint32_t> got;
212+
ASSERT_TRUE(query::wildcard_query(idx, "a?b", &got).ok());
213+
EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 3}));
214+
215+
ASSERT_TRUE(query::wildcard_query(idx, "a??b", &got).ok());
216+
EXPECT_EQ(got, (std::vector<uint32_t> {2}));
217+
218+
std::remove(path.c_str());
219+
}
220+
221+
TEST(SniiPatternQuery, MalformedKeywordTermsRetainByteCompatibleWildcardMatching) {
222+
Corpus corpus;
223+
corpus.doc_count = 3;
224+
corpus.docs = {{std::string("a\xFF", 2)}, {"ab"}, {"zz"}};
225+
const std::string path = TempPath();
226+
WriteCorpus(corpus, path);
227+
228+
io::LocalFileReader file;
229+
SniiSegmentReader segment;
230+
LogicalIndexReader idx = OpenIndex(&file, &segment, path);
231+
232+
std::vector<uint32_t> got;
233+
ASSERT_TRUE(query::wildcard_query(idx, "a*", &got).ok());
234+
EXPECT_EQ(got, (std::vector<uint32_t> {0, 1}));
235+
236+
ASSERT_TRUE(query::wildcard_query(idx, "**", &got).ok());
237+
EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 2}));
238+
239+
ASSERT_TRUE(query::wildcard_query(idx, "*", &got).ok());
240+
EXPECT_EQ(got, (std::vector<uint32_t> {0, 1, 2}));
241+
242+
std::remove(path.c_str());
243+
}
244+
200245
TEST(SniiPatternQuery, RegexpMatchesOracle) {
201246
const Corpus corpus = BuildMixedCorpus();
202247
const std::string path = TempPath();

‎be/test/storage/index/snii_b2_t08_wildcard_test.cpp‎

Lines changed: 66 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -17,12 +17,12 @@
1717

1818
// T08 -- wildcard matcher scratch reuse.
1919
//
20-
// Proves the request-scoped internal::WildcardMatcher (a) matches bit-for-bit
21-
// identically to the former per-call DP in wildcard_query.cpp, and (b) reuses its
22-
// two DP scratch rows across every visited term so a whole-dictionary scan
23-
// performs O(1) heap allocations (<= 2) instead of O(2N). A header-only
24-
// CountingAllocator gives the deterministic allocation counts; a byte-for-byte
25-
// copy of the original DP serves as the equivalence oracle.
20+
// Proves the request-scoped internal::WildcardMatcher preserves the former ASCII
21+
// behavior while matching UTF-8 code points, and reuses its two DP scratch rows
22+
// across every visited term so a whole-dictionary scan performs O(1) heap
23+
// allocations (<= 2) instead of O(2N). A header-only CountingAllocator gives the
24+
// deterministic allocation counts; a byte-for-byte copy of the original DP
25+
// serves as the ASCII equivalence oracle.
2626

2727
#include <gtest/gtest.h>
2828

@@ -155,7 +155,7 @@ std::vector<std::string> make_varied_length_terms(size_t count, size_t max_len)
155155
return terms;
156156
}
157157

158-
// W-EQ-DP: the optimized matcher reproduces the reference DP bit-for-bit over an
158+
// W-EQ-DP: the optimized matcher reproduces the reference DP for ASCII over an
159159
// exhaustive small-alphabet battery (covers "", leading/trailing '*'/'?',
160160
// consecutive "**", '?' interplay) plus realistic dictionary patterns/terms. One
161161
// matcher is reused across all terms of a pattern, so this also proves scratch
@@ -212,12 +212,69 @@ TEST(SniiWildcardQueryTest, StarMatchesEverything) {
212212
EXPECT_TRUE(matcher("xyz"));
213213
}
214214

215-
// W-QMARK: "?" matches exactly one byte.
216-
TEST(SniiWildcardQueryTest, QuestionMarkMatchesExactlyOneByte) {
215+
// W-QMARK: "?" matches exactly one UTF-8 code point.
216+
TEST(SniiWildcardQueryTest, QuestionMarkMatchesExactlyOneUtf8CodePoint) {
217217
internal::WildcardMatcher<> matcher("?");
218218
EXPECT_FALSE(matcher(""));
219219
EXPECT_TRUE(matcher("a"));
220+
EXPECT_TRUE(matcher("猫"));
221+
EXPECT_TRUE(matcher("🔥"));
220222
EXPECT_FALSE(matcher("ab"));
223+
224+
internal::WildcardMatcher<> surrounded("a?b");
225+
EXPECT_TRUE(surrounded("a猫b"));
226+
EXPECT_TRUE(surrounded("a🔥b"));
227+
EXPECT_FALSE(surrounded("a猫猫b"));
228+
229+
internal::WildcardMatcher<> three("a???b");
230+
EXPECT_FALSE(three("a猫b"));
231+
EXPECT_TRUE(three("a猫🔥éb"));
232+
233+
internal::WildcardMatcher<> star_then_two("a*??b");
234+
EXPECT_FALSE(star_then_two("a猫b"));
235+
EXPECT_TRUE(star_then_two("a猫🔥b"));
236+
}
237+
238+
// W-UTF8-LITERAL: non-ASCII literals are compared as complete code points.
239+
TEST(SniiWildcardQueryTest, Utf8LiteralsMatchCompleteCodePoints) {
240+
internal::WildcardMatcher<> matcher("猫?火");
241+
EXPECT_TRUE(matcher("猫🔥火"));
242+
EXPECT_FALSE(matcher("猫🔥🔥火"));
243+
EXPECT_FALSE(matcher("狗🔥火"));
244+
}
245+
246+
// W-INVALID-UTF8: patterns remain strict UTF-8, while malformed raw keyword
247+
// terms retain the byte-wise semantics used before code-point matching.
248+
TEST(SniiWildcardQueryTest, MalformedTermsRetainByteCompatibleMatching) {
249+
const std::string invalid_lead("\xff", 1);
250+
const std::string truncated("\xe7\x8c", 2);
251+
const std::string invalid_continuation("\xe7x\xab", 3);
252+
253+
internal::WildcardMatcher<> any("*");
254+
EXPECT_TRUE(any(invalid_lead));
255+
EXPECT_TRUE(any(truncated));
256+
EXPECT_TRUE(any(invalid_continuation));
257+
258+
internal::WildcardMatcher<> two_bytes("??");
259+
EXPECT_FALSE(two_bytes(invalid_lead));
260+
EXPECT_TRUE(two_bytes(truncated));
261+
EXPECT_FALSE(two_bytes(invalid_continuation));
262+
263+
internal::WildcardMatcher<> invalid_pattern(invalid_lead);
264+
EXPECT_FALSE(invalid_pattern(invalid_lead));
265+
EXPECT_FALSE(invalid_pattern("猫"));
266+
}
267+
268+
TEST(SniiWildcardQueryTest, InvalidUtf8PatternReturnsInvalidArgument) {
269+
MemoryFile file;
270+
reader::SniiSegmentReader segment_reader;
271+
reader::LogicalIndexReader index_reader;
272+
assert_ok(build_reader(&file, &segment_reader, &index_reader));
273+
274+
const std::string invalid_pattern("\xff*", 2);
275+
std::vector<uint32_t> docids;
276+
EXPECT_TRUE(wildcard_query(index_reader, invalid_pattern, &docids)
277+
.is<doris::ErrorCode::INVALID_ARGUMENT>());
221278
}
222279

223280
// W-CONSEC-STAR: consecutive '*' degrade gracefully.
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
-- This file is automatically generated. You should know what you did if you want to edit this
2+
-- !malformed_keyword_wildcards --
3+
double_star 7 61FF
4+
prefix 7 61FF
5+
single_star 7 61FF
6+
7+
-- !utf8_single_code_point --
8+
SNII 1
9+
SNII 2
10+
SNII 4
11+
V3 1
12+
V3 2
13+
V3 4
14+
15+
-- !utf8_two_code_points --
16+
SNII 3
17+
V3 3
18+
19+
-- !utf8_three_code_points --
20+
SNII 0
21+
V3 0
22+

0 commit comments

Comments
 (0)