Skip to content

Commit 6a79f95

Browse files
authored
[feat](inverted-index) Support configurable ngram size difference (#67917)
### What problem does this PR solve? Issue Number: Related PR: None Problem Summary: Custom ngram tokenizers hard-code the allowed difference between max_gram and min_gram to 1. This prevents valid wider ngram ranges while offering no explicit override. This PR adds max_ngram_diff, keeps 1 as the backward-compatible default, requires ASCII integer syntax, and validates the same 0 through 255 range in FE and BE. The upper bound limits per-position token fan-out. Newly created policies also cap absolute custom ngram sizes at 1024, while an explicit persisted compatibility marker preserves marker-less policies accepted before that cap during rolling upgrades. Invalid replayed policies cannot block valid replacements. Because max_ngram_diff controls policy admission but does not affect emitted tokens, valid policies exclude it from analyzer identity so equivalent analyzers cannot bypass duplicate-index detection. ### Release note Allow custom ngram tokenizers to configure the maximum difference between max_gram and min_gram with max_ngram_diff values from 0 through 255.
1 parent a7c0a78 commit 6a79f95

13 files changed

Lines changed: 531 additions & 23 deletions

File tree

‎be/src/storage/index/inverted/tokenizer/ngram/ngram_tokenizer.cpp‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -103,7 +103,8 @@ void NGramTokenizer::init(int32_t min_gram, int32_t max_gram, bool edges_only) {
103103
_min_gram = min_gram;
104104
_max_gram = max_gram;
105105
_edges_only = edges_only;
106-
_buffer.resize(4 * max_gram + 1024);
106+
const size_t buffer_size = static_cast<size_t>(max_gram) * 4 + 1024;
107+
_buffer.resize(buffer_size);
107108
}
108109

109110
void NGramTokenizer::update_last_non_token_char() {

‎be/src/storage/index/inverted/tokenizer/ngram/ngram_tokenizer.h‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,4 +75,4 @@ class NGramTokenizer : public DorisTokenizer {
7575
std::string _utf8_buffer;
7676
};
7777

78-
} // namespace doris::segment_v2::inverted_index
78+
} // namespace doris::segment_v2::inverted_index

‎be/src/storage/index/inverted/tokenizer/ngram/ngram_tokenizer_factory.cpp‎

Lines changed: 26 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -26,12 +26,35 @@ std::unordered_map<std::string, CharMatcherPtr> NGramTokenizerFactory::MATCHERS;
2626
void NGramTokenizerFactory::initialize(const Settings& settings) {
2727
_min_gram = settings.get_int("min_gram", NGramTokenizer::DEFAULT_MIN_NGRAM_SIZE);
2828
_max_gram = settings.get_int("max_gram", NGramTokenizer::DEFAULT_MAX_NGRAM_SIZE);
29+
if (_min_gram <= 0 || _max_gram <= 0) {
30+
throw Exception(ErrorCode::INVALID_ARGUMENT, "min_gram and max_gram must be positive");
31+
}
32+
if (_min_gram > _max_gram) {
33+
throw Exception(ErrorCode::INVALID_ARGUMENT, "min_gram must not be greater than max_gram");
34+
}
35+
const bool has_max_ngram_diff = !settings.get_string("max_ngram_diff").empty();
36+
if (has_max_ngram_diff && (_min_gram > MAX_NGRAM_SIZE || _max_gram > MAX_NGRAM_SIZE)) {
37+
throw Exception(ErrorCode::INVALID_ARGUMENT,
38+
"min_gram and max_gram must be less than or equal to " +
39+
std::to_string(MAX_NGRAM_SIZE));
40+
}
41+
int32_t max_ngram_diff = settings.get_int("max_ngram_diff", 1);
42+
if (max_ngram_diff < 0) {
43+
throw Exception(ErrorCode::INVALID_ARGUMENT,
44+
"max_ngram_diff must be greater than or equal to 0");
45+
}
46+
if (max_ngram_diff > MAX_NGRAM_DIFF) {
47+
throw Exception(
48+
ErrorCode::INVALID_ARGUMENT,
49+
"max_ngram_diff must be less than or equal to " + std::to_string(MAX_NGRAM_DIFF));
50+
}
2951
int32_t ngram_diff = _max_gram - _min_gram;
30-
if (ngram_diff > 1) {
52+
if (ngram_diff > max_ngram_diff) {
3153
throw Exception(
3254
ErrorCode::INVALID_ARGUMENT,
3355
"The difference between max_gram and min_gram in NGram Tokenizer must be less "
34-
"than or equal to: [ 1 ] but was [" +
56+
"than or equal to: [ " +
57+
std::to_string(max_ngram_diff) + " ] but was [" +
3558
std::to_string(ngram_diff) + "]");
3659
}
3760
_matcher = parse_token_chars(settings);
@@ -80,4 +103,4 @@ CharMatcherPtr NGramTokenizerFactory::parse_token_chars(const Settings& settings
80103
return builder.build();
81104
}
82105

83-
} // namespace doris::segment_v2::inverted_index
106+
} // namespace doris::segment_v2::inverted_index

‎be/src/storage/index/inverted/tokenizer/ngram/ngram_tokenizer_factory.h‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,11 @@ namespace doris::segment_v2::inverted_index {
2626

2727
class NGramTokenizerFactory : public TokenizerFactory {
2828
public:
29+
// A configured range can emit one token per gram size at every input position.
30+
static constexpr int32_t MAX_NGRAM_DIFF = 255;
31+
// Bound the per-stream buffer while retaining support for large application-specific grams.
32+
static constexpr int32_t MAX_NGRAM_SIZE = 1024;
33+
2934
NGramTokenizerFactory() = default;
3035
~NGramTokenizerFactory() override = default;
3136

@@ -65,4 +70,4 @@ class NGramTokenizerFactory : public TokenizerFactory {
6570
CharMatcherPtr _matcher;
6671
};
6772

68-
}; // namespace doris::segment_v2::inverted_index
73+
}; // namespace doris::segment_v2::inverted_index

‎be/test/storage/index/inverted/tokenizer/ngram_tokenizer_test.cpp‎

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,87 @@ TEST(NGramTokenizerTest, InvalidMinMaxDifference) {
8787
ASSERT_TRUE(exception_thrown);
8888
}
8989

90+
TEST(NGramTokenizerTest, ConfiguredMinMaxDifference) {
91+
NGramTokenizerFactory factory;
92+
std::unordered_map<std::string, std::string> args;
93+
args["min_gram"] = "1";
94+
args["max_gram"] = "8";
95+
args["max_ngram_diff"] = "7";
96+
Settings settings(args);
97+
factory.initialize(settings);
98+
auto tokens = tokenize(factory, "abcdefgh");
99+
100+
std::vector<std::string> expected {
101+
"a", "ab", "abc", "abcd", "abcde", "abcdef", "abcdefg", "abcdefgh", "b",
102+
"bc", "bcd", "bcde", "bcdef", "bcdefg", "bcdefgh", "c", "cd", "cde",
103+
"cdef", "cdefg", "cdefgh", "d", "de", "def", "defg", "defgh", "e",
104+
"ef", "efg", "efgh", "f", "fg", "fgh", "g", "gh", "h"};
105+
ASSERT_EQ(tokens, expected);
106+
}
107+
108+
TEST(NGramTokenizerTest, InvalidConfiguredDifferenceLimit) {
109+
NGramTokenizerFactory factory;
110+
std::unordered_map<std::string, std::string> args;
111+
args["max_ngram_diff"] = "-1";
112+
Settings settings(args);
113+
114+
EXPECT_THROW(factory.initialize(settings), Exception);
115+
}
116+
117+
TEST(NGramTokenizerTest, ExcessiveConfiguredDifferenceLimit) {
118+
NGramTokenizerFactory factory;
119+
std::unordered_map<std::string, std::string> args;
120+
args["max_ngram_diff"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_DIFF + 1);
121+
Settings settings(args);
122+
123+
EXPECT_THROW(factory.initialize(settings), Exception);
124+
}
125+
126+
TEST(NGramTokenizerTest, ConfiguredDifferenceLimitBoundary) {
127+
NGramTokenizerFactory factory;
128+
std::unordered_map<std::string, std::string> args;
129+
args["min_gram"] = "1";
130+
args["max_gram"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_DIFF + 1);
131+
args["max_ngram_diff"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_DIFF);
132+
Settings settings(args);
133+
134+
EXPECT_NO_THROW(factory.initialize(settings));
135+
}
136+
137+
TEST(NGramTokenizerTest, AbsoluteSizeBoundary) {
138+
NGramTokenizerFactory factory;
139+
std::unordered_map<std::string, std::string> args;
140+
args["min_gram"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_SIZE);
141+
args["max_gram"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_SIZE);
142+
args["max_ngram_diff"] = "1";
143+
Settings settings(args);
144+
145+
EXPECT_NO_THROW(factory.initialize(settings));
146+
EXPECT_NO_THROW(factory.create());
147+
}
148+
149+
TEST(NGramTokenizerTest, ExcessiveAbsoluteSize) {
150+
NGramTokenizerFactory factory;
151+
std::unordered_map<std::string, std::string> args;
152+
args["min_gram"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_SIZE);
153+
args["max_gram"] = std::to_string(NGramTokenizerFactory::MAX_NGRAM_SIZE + 1);
154+
args["max_ngram_diff"] = "1";
155+
Settings settings(args);
156+
157+
EXPECT_THROW(factory.initialize(settings), Exception);
158+
}
159+
160+
TEST(NGramTokenizerTest, LegacyFixedSizeAboveCurrentLimit) {
161+
NGramTokenizerFactory factory;
162+
std::unordered_map<std::string, std::string> args;
163+
args["min_gram"] = "2048";
164+
args["max_gram"] = "2048";
165+
Settings settings(args);
166+
167+
EXPECT_NO_THROW(factory.initialize(settings));
168+
EXPECT_NO_THROW(factory.create());
169+
}
170+
90171
TEST(NGramTokenizerTest, SymbolCharactersHandling) {
91172
NGramTokenizerFactory factory;
92173
std::unordered_map<std::string, std::string> args;
@@ -202,4 +283,4 @@ TEST(NGramTokenizerTest, WhitespaceTokenization) {
202283
ASSERT_EQ(tokens, expected);
203284
}
204285

205-
} // namespace doris::segment_v2
286+
} // namespace doris::segment_v2

‎fe/fe-core/src/main/java/org/apache/doris/analysis/invertedindex/AnalyzerIdentityBuilder.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,8 @@
2828
import java.util.TreeMap;
2929

3030
public final class AnalyzerIdentityBuilder {
31+
private static final String PROP_MAX_NGRAM_DIFF = "max_ngram_diff";
32+
3133
private AnalyzerIdentityBuilder() {
3234
}
3335

@@ -169,6 +171,9 @@ private static String resolveComponentIdentity(String name, IndexPolicyTypeEnum
169171
if (policy == null || policy.getType() != expectedType) {
170172
return name;
171173
}
174+
if (policy.isInvalid()) {
175+
return "invalid-policy:" + policy.getId() + ":" + policy.getName();
176+
}
172177

173178
Map<String, String> props = policy.getProperties();
174179
if (props == null || props.isEmpty()) {
@@ -177,6 +182,11 @@ private static String resolveComponentIdentity(String name, IndexPolicyTypeEnum
177182

178183
// Build identity from sorted properties
179184
TreeMap<String, String> sortedProps = new TreeMap<>(props);
185+
if (expectedType == IndexPolicyTypeEnum.TOKENIZER
186+
&& "ngram".equals(sortedProps.get(IndexPolicy.PROP_TYPE))) {
187+
// This setting only limits policy creation; it does not change emitted tokens.
188+
sortedProps.remove(PROP_MAX_NGRAM_DIFF);
189+
}
180190
return sortedProps.toString();
181191
} catch (RuntimeException e) {
182192
return name;

‎fe/fe-core/src/main/java/org/apache/doris/indexpolicy/IndexPolicy.java‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -129,8 +129,13 @@ public List<String> getShowInfo() {
129129
ImmutableSet.of("common_grams");
130130

131131
public boolean isInvalid() {
132-
return type == IndexPolicyTypeEnum.TOKEN_FILTER
132+
boolean hasUnsupportedTokenFilter = type == IndexPolicyTypeEnum.TOKEN_FILTER
133133
&& properties != null
134134
&& LEGACY_UNSUPPORTED_TOKEN_FILTER_TYPES.contains(properties.get(PROP_TYPE));
135+
boolean hasInvalidNgramTokenizer = type == IndexPolicyTypeEnum.TOKENIZER
136+
&& properties != null
137+
&& "ngram".equals(properties.get(PROP_TYPE))
138+
&& !NGramTokenizerValidator.isValidPolicy(properties);
139+
return hasUnsupportedTokenFilter || hasInvalidNgramTokenizer;
135140
}
136141
}

‎fe/fe-core/src/main/java/org/apache/doris/indexpolicy/IndexPolicyMgr.java‎

Lines changed: 35 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -110,22 +110,32 @@ public void validateAnalyzerExists(String analyzerName) throws DdlException {
110110
if (policy.isInvalid()) {
111111
throw new DdlException("Analyzer '" + analyzerName + "' is invalid");
112112
}
113-
validateReferencedTokenFiltersUsableLocked(analyzerName, policy);
113+
validateReferencedComponentsUsableLocked(analyzerName, policy);
114114
} finally {
115115
readUnlock();
116116
}
117117
}
118118

119119
/**
120-
* Older metadata may retain token filter types no longer supported by BE, such as common_grams.
121-
* Load these policies so a single obsolete policy cannot prevent FE startup, but reject any
122-
* analyzer that references them at use time, before BE reports an unknown token filter during
123-
* index construction or querying.
120+
* Older metadata may retain components that current validation rejects. Load these policies so
121+
* one obsolete policy cannot prevent FE startup, but reject analyzers that reference them before
122+
* BE tries to construct the analyzer during index construction or querying.
124123
*/
125-
private void validateReferencedTokenFiltersUsableLocked(String analyzerName, IndexPolicy analyzer)
124+
private void validateReferencedComponentsUsableLocked(String analyzerName, IndexPolicy analyzer)
126125
throws DdlException {
127-
String tokenFilterNames = analyzer.getProperties() == null
128-
? null : analyzer.getProperties().get(IndexPolicy.PROP_TOKEN_FILTER);
126+
Map<String, String> analyzerProperties = analyzer.getProperties();
127+
if (analyzerProperties == null) {
128+
return;
129+
}
130+
String tokenizerName = analyzerProperties.get(IndexPolicy.PROP_TOKENIZER);
131+
IndexPolicy tokenizer = tokenizerName == null
132+
? null : nameToIndexPolicy.get(normalizeKey(tokenizerName));
133+
if (tokenizer != null && tokenizer.isInvalid()) {
134+
throw new DdlException("Analyzer '" + analyzerName + "' references invalid tokenizer '"
135+
+ tokenizerName + "'");
136+
}
137+
138+
String tokenFilterNames = analyzerProperties.get(IndexPolicy.PROP_TOKEN_FILTER);
129139
if (tokenFilterNames == null || tokenFilterNames.isEmpty()) {
130140
return;
131141
}
@@ -186,8 +196,16 @@ public void createIndexPolicy(boolean ifNotExists, String policyName,
186196

187197
writeLock();
188198
try {
189-
validatePolicyProperties(type, properties);
190-
IndexPolicy indexPolicy = IndexPolicy.create(policyName, type, properties);
199+
Map<String, String> storedProperties = properties == null
200+
? null : Maps.newHashMap(properties);
201+
validatePolicyProperties(type, storedProperties);
202+
if (type == IndexPolicyTypeEnum.TOKENIZER
203+
&& "ngram".equals(storedProperties.get(IndexPolicy.PROP_TYPE))) {
204+
// Presence distinguishes policies created with the absolute-size limit from
205+
// compatible policies replayed from a version before max_ngram_diff existed.
206+
storedProperties.putIfAbsent("max_ngram_diff", "1");
207+
}
208+
IndexPolicy indexPolicy = IndexPolicy.create(policyName, type, storedProperties);
191209

192210
if (nameToIndexPolicy.containsKey(normalizedName)) {
193211
if (ifNotExists) {
@@ -337,6 +355,9 @@ private void validatePolicyReference(String name, IndexPolicyTypeEnum expectedTy
337355
throw new DdlException("Referenced policy '" + name + "' is of type "
338356
+ policy.getType() + " but expected " + expectedType);
339357
}
358+
if (policy.isInvalid()) {
359+
throw new DdlException("Referenced " + expectedType + " policy '" + name + "' is invalid");
360+
}
340361
}
341362

342363
private void validateTokenizerProperties(Map<String, String> properties) throws DdlException {
@@ -667,10 +688,10 @@ public void gsonPostProcess() throws IOException {
667688

668689
private static void warnIfUnsupported(IndexPolicy indexPolicy) {
669690
if (indexPolicy.isInvalid()) {
670-
LOG.error("Index policy '{}' (id={}) uses token filter type '{}', which this version"
671-
+ " no longer supports; analyzers referencing it will be rejected. Drop the"
672-
+ " indexes and policies that depend on it.", indexPolicy.getName(),
673-
indexPolicy.getId(), indexPolicy.getProperties().get(IndexPolicy.PROP_TYPE));
691+
LOG.error("Index policy '{}' (id={}, type={}) is not valid in this version; analyzers"
692+
+ " referencing it will be rejected. Drop the indexes and policies that depend"
693+
+ " on it.", indexPolicy.getName(), indexPolicy.getId(),
694+
indexPolicy.getProperties().get(IndexPolicy.PROP_TYPE));
674695
}
675696
}
676697

‎fe/fe-core/src/main/java/org/apache/doris/indexpolicy/NGramTokenizerValidator.java‎

Lines changed: 54 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -27,14 +27,38 @@
2727
import java.util.Set;
2828

2929
public class NGramTokenizerValidator extends BasePolicyValidator {
30+
// A configured range can emit one token per gram size at every input position.
31+
static final int MAX_NGRAM_DIFF = 255;
32+
// NGramTokenizer keeps four code-point slots per configured gram plus a refill margin.
33+
static final int MAX_NGRAM_SIZE = 1024;
34+
3035
private static final Set<String> ALLOWED_PROPS = ImmutableSet.of(
31-
"type", "min_gram", "max_gram", "token_chars", "custom_token_chars");
36+
"type", "min_gram", "max_gram", "max_ngram_diff", "token_chars", "custom_token_chars");
3237

3338
private static final Set<String> VALID_TOKEN_CHARS = ImmutableSet.of(
3439
"letter", "digit", "whitespace", "punctuation", "symbol", "custom");
3540

41+
private final boolean enforceAbsoluteSizeLimit;
42+
3643
public NGramTokenizerValidator() {
44+
this(true);
45+
}
46+
47+
private NGramTokenizerValidator(boolean enforceAbsoluteSizeLimit) {
3748
super(ALLOWED_PROPS);
49+
this.enforceAbsoluteSizeLimit = enforceAbsoluteSizeLimit;
50+
}
51+
52+
static boolean isValidPolicy(Map<String, String> properties) {
53+
try {
54+
// Policies created before max_ngram_diff existed have no compatibility marker and
55+
// must retain the absolute-size behavior accepted by the previous release.
56+
boolean hasCompatibilityMarker = properties.containsKey("max_ngram_diff");
57+
new NGramTokenizerValidator(hasCompatibilityMarker).validate(properties);
58+
return true;
59+
} catch (DdlException | RuntimeException e) {
60+
return false;
61+
}
3862
}
3963

4064
@Override
@@ -76,6 +100,35 @@ protected void validateSpecific(Map<String, String> props) throws DdlException {
76100
throw new DdlException("max_gram [" + maxGram + "] "
77101
+ "cannot be smaller than min_gram [" + minGram + "]");
78102
}
103+
if (enforceAbsoluteSizeLimit
104+
&& (minGram > MAX_NGRAM_SIZE || maxGram > MAX_NGRAM_SIZE)) {
105+
throw new DdlException("min_gram and max_gram must be less than or equal to " + MAX_NGRAM_SIZE);
106+
}
107+
108+
int maxNgramDiff = 1;
109+
if (props.containsKey("max_ngram_diff")) {
110+
String value = props.get("max_ngram_diff");
111+
if (!value.matches("-?[0-9]+")) {
112+
throw new DdlException("max_ngram_diff must be a non-negative integer");
113+
}
114+
try {
115+
maxNgramDiff = Integer.parseInt(value);
116+
if (maxNgramDiff < 0) {
117+
throw new DdlException("max_ngram_diff must be greater than or equal to 0");
118+
}
119+
if (maxNgramDiff > MAX_NGRAM_DIFF) {
120+
throw new DdlException("max_ngram_diff must be less than or equal to " + MAX_NGRAM_DIFF);
121+
}
122+
} catch (NumberFormatException e) {
123+
throw new DdlException("max_ngram_diff must be a non-negative integer");
124+
}
125+
}
126+
127+
int ngramDiff = maxGram - minGram;
128+
if (ngramDiff > maxNgramDiff) {
129+
throw new DdlException("The difference between max_gram and min_gram in NGram Tokenizer must be less "
130+
+ "than or equal to: [ " + maxNgramDiff + " ] but was [" + ngramDiff + "]");
131+
}
79132

80133
if (props.containsKey("token_chars")) {
81134
String tokenChars = props.get("token_chars");

0 commit comments

Comments
 (0)