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 25caa3a5c4e [improvement](be) Tokenize english and basic with a
vectorized byte classifier (#70264)
25caa3a5c4e is described below
commit 25caa3a5c4e20fa531987f959e1aac1d922e0ed9
Author: Jack <[email protected]>
AuthorDate: Thu Nov 19 11:45:12 2026 +0800
[improvement](be) Tokenize english and basic with a vectorized byte
classifier (#70264)
### What problem does this PR solve?
Issue Number: None
Related PR: #70263
Problem Summary: Tokenize english and basic with a SIMD byte classifier:
about 3.8x and 7.4x as fast as master, with the same tokens.
---
.../index/inverted/analysis/analyzer/analyzer.cpp | 23 +-
.../analysis/tokenizer/basic/basic_tokenizer.cpp | 142 ++++++++++---
.../analysis/tokenizer/basic/basic_tokenizer.h | 43 ++--
.../tokenizer/basic/basic_tokenizer_factory.h | 6 +-
.../inverted/analysis/tokenizer/byte_classifier.h | 107 ++++++++++
.../tokenizer/english/english_tokenizer.cpp | 103 +++++++++
.../analysis/tokenizer/english/english_tokenizer.h | 73 +++++++
be/src/util/simd/bits.h | 10 +
.../inverted/analysis/component_stream_test.cpp | 68 +++++-
.../analysis/tokenizer/basic_tokenizer_test.cpp | 236 +++++++++++++++++++++
.../analysis/tokenizer/byte_classifier_test.cpp | 172 +++++++++++++++
.../analysis/tokenizer/english_tokenizer_test.cpp | 231 ++++++++++++++++++++
be/test/util/simd/bits_test.cpp | 20 ++
13 files changed, 1175 insertions(+), 59 deletions(-)
diff --git a/be/src/storage/index/inverted/analysis/analyzer/analyzer.cpp
b/be/src/storage/index/inverted/analysis/analyzer/analyzer.cpp
index 7cf3046eea6..8e09388e7d6 100644
--- a/be/src/storage/index/inverted/analysis/analyzer/analyzer.cpp
+++ b/be/src/storage/index/inverted/analysis/analyzer/analyzer.cpp
@@ -47,11 +47,12 @@
#include "storage/index/inverted/analysis/token_filter/lower_case_filter.h"
#include
"storage/index/inverted/analysis/token_filter/lower_case_filter_factory.h"
#include
"storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer_factory.h"
+#include "storage/index/inverted/analysis/tokenizer/byte_classifier.h"
+#include
"storage/index/inverted/analysis/tokenizer/english/english_tokenizer.h"
#include
"storage/index/inverted/analysis/tokenizer/icu/icu_tokenizer_factory.h"
#include "storage/index/inverted/analysis/tokenizer/ik/ik_tokenizer_factory.h"
#include
"storage/index/inverted/analysis/tokenizer/kuromoji/kuromoji_tokenizer_factory.h"
#include "storage/index/inverted/clucene/lucene_backed_text_analyzer.h"
-#include "util/string_util.h"
namespace doris::segment_v2::inverted_index {
namespace {
@@ -142,7 +143,10 @@ std::string normalize_builtin_term(InvertedIndexParserType
parser_type, bool low
}
return text;
default:
- return lower_case ? to_lower(text) : text;
+ if (lower_case) {
+ ascii_lower(text);
+ }
+ return text;
}
}
@@ -238,8 +242,11 @@ TextAnalyzerPtr
build_builtin_analyzer(InvertedIndexParserType parser_type,
builtin_lowercase(lower_case, true));
}
if (parser_type == InvertedIndexParserType::PARSER_BASIC) {
- return tokenizer_chain(std::make_shared<BasicTokenizerFactory>(),
- builtin_lowercase(lower_case, true));
+ // The tokenizer lowercases its own tokens, which are all a lowercase
filter would change.
+ return std::make_shared<ChainAnalyzer>(
+ std::vector<CharFilterFactoryPtr> {},
+
std::make_shared<BasicTokenizerFactory>(builtin_lowercase(lower_case, true)),
+ std::vector<TokenFilterFactoryPtr> {});
}
if (parser_type == InvertedIndexParserType::PARSER_IK) {
// lower_case only applies to the words: IK always matches its
dictionary in lowercase.
@@ -277,9 +284,11 @@ TextAnalyzerPtr
build_builtin_analyzer(InvertedIndexParserType parser_type,
builtin_lowercase(lower_case, true), dict),
std::vector<TokenFilterFactoryPtr> {});
}
- // english, and the default for an unknown parser
- return
lucene_builtin_analyzer(std::make_shared<lucene::analysis::SimpleAnalyzer<char>>(),
- lower_case, stop_words);
+ // english, and the default for an unknown parser; neither has stop words.
+ return std::make_shared<ChainAnalyzer>(
+ std::vector<CharFilterFactoryPtr> {},
+
std::make_shared<EnglishTokenizerFactory>(builtin_lowercase(lower_case, true)),
+ std::vector<TokenFilterFactoryPtr> {});
}
} // namespace
diff --git
a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.cpp
b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.cpp
index 8bd117e0d50..c4085c951e2 100644
--- a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.cpp
+++ b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.cpp
@@ -22,27 +22,56 @@
#include <algorithm>
+#include "common/compiler_util.h"
+#include "common/logging.h"
#include "storage/index/inverted/analysis/common/rune.h"
#include "storage/index/inverted/analysis/scratch.h"
+#include "storage/index/inverted/analysis/tokenizer/byte_classifier.h"
namespace doris::segment_v2::inverted_index {
-#define IS_IN_RANGE(c, start, end) ((uint32_t)((c) - (start)) <= ((end) -
(start)))
+namespace {
-#define IS_CHINESE_CHAR(c) \
- (IS_IN_RANGE(c, 0x4E00, 0x9FFF) || IS_IN_RANGE(c, 0x3400, 0x4DBF) || \
- IS_IN_RANGE(c, 0x20000, 0x2A6DF) || IS_IN_RANGE(c, 0x2A700, 0x2EBEF) || \
- IS_IN_RANGE(c, 0x30000, 0x3134A))
+bool in_range(UChar32 c, uint32_t start, uint32_t end) {
+ return static_cast<uint32_t>(c) - start <= end - start;
+}
-namespace {
+// The five ranges of Chinese characters the basic tokenizer makes a token of
each.
+bool is_chinese_char(UChar32 c) {
+ return in_range(c, 0x4E00, 0x9FFF) || in_range(c, 0x3400, 0x4DBF) ||
+ in_range(c, 0x20000, 0x2A6DF) || in_range(c, 0x2A700, 0x2EBEF) ||
+ in_range(c, 0x30000, 0x3134A);
+}
-bool is_ascii_alnum(uint8_t c) {
- return (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c >= 'a' && c
<= 'z');
+// Decode each lead byte from the source. CJK characters do not need ASCII
case folding.
+ALWAYS_INLINE inline void push_chinese_char(TokenBatch& batch, const char*
src, int64_t position,
+ size_t size) {
+ auto next = static_cast<int32_t>(position);
+ UChar32 c = U_UNASSIGNED;
+ U8_NEXT(src, next, static_cast<int32_t>(size), c);
+ if (c >= 0 && is_chinese_char(c)) {
+ batch.push({src + position, static_cast<size_t>(next - position)}, 1);
+ }
+}
+
+// The run [start, end), cut to MAX_WORD_LEN bytes.
+template <bool kLower>
+void push_run(TokenBatch& batch, const char* src, int64_t start, int64_t end) {
+ const auto length = static_cast<size_t>(std::min<int64_t>(end - start,
MAX_WORD_LEN));
+ // Lower only the retained prefix; separators and a long run's discarded
suffix need no copy.
+ if constexpr (kLower) {
+ char* lowered = batch.allocate_term(length);
+ ascii_lower(src + start, lowered, length);
+ batch.push({lowered, length}, 1);
+ } else {
+ batch.push({src + start, length}, 1);
+ }
}
} // namespace
void BasicTokenizer::initialize(const std::string& extra_chars) {
+ DORIS_CHECK(!_lowercase || extra_chars.empty());
_extra_char_set.fill(false);
_has_extra_chars = !extra_chars.empty();
@@ -53,31 +82,82 @@ void BasicTokenizer::initialize(const std::string&
extra_chars) {
}
}
-bool BasicTokenizer::next_token(TokenRef& token) {
- if (_buffer_index >= _tokens_text.size()) {
- return false;
+void BasicTokenizer::reset(std::string_view text) {
+ _text = text;
+ if (_has_extra_chars) {
+ _next = 0;
+ _tokens_text.clear();
+ release_oversized_scratch(_tokens_text);
+ cut_with_extra_chars(text);
+ return;
}
- const std::string_view token_text = _tokens_text[_buffer_index++];
- token = {.data = token_text.data(),
- .size = static_cast<uint32_t>(
- std::min(token_text.size(),
static_cast<size_t>(MAX_WORD_LEN))),
- .position_increment = 1};
- return true;
+ _block = 0;
+ _carry = 0;
+ _run_start = -1;
}
-void BasicTokenizer::on_reset(std::string_view text) {
- _buffer_index = 0;
- _tokens_text.clear();
- release_oversized_scratch(_tokens_text);
+bool BasicTokenizer::next_batch(TokenBatch& batch) {
if (_has_extra_chars) {
- cut<true>(text);
- } else {
- cut<false>(text);
+ return hand_out(batch);
}
+ return _lowercase ? scan<true>(batch) : scan<false>(batch);
}
-template <bool HasExtraChars>
-void BasicTokenizer::cut(std::string_view text) {
+template <bool kLower>
+bool BasicTokenizer::scan(TokenBatch& batch) {
+ batch.clear();
+ const size_t size = _text.size();
+ const char* const src = _text.data();
+ const size_t blocks = (size + BYTE_CLASS_BLOCK - 1) / BYTE_CLASS_BLOCK;
+ while (_block < blocks && batch.size() < kBatchTokens) {
+ const size_t offset = _block * BYTE_CLASS_BLOCK;
+ const ByteClasses classes =
+ offset + BYTE_CLASS_BLOCK <= size
+ ? classify_block<false>(src + offset, nullptr)
+ : classify_tail<false>(src + offset, size - offset,
nullptr);
+ const uint64_t alnum = classes.alnum;
+ // A bit where a run starts or where the byte after a run is.
+ const uint64_t edges = alnum ^ ((alnum << 1) | _carry);
+ _carry = alnum >> 63;
+ // Visit events in byte order so an ASCII run precedes a following CJK
token.
+ uint64_t events = edges | classes.lead;
+ while (events != 0) {
+ const int bit = __builtin_ctzll(events);
+ const uint64_t one = 1ULL << bit;
+ events &= events - 1;
+ const auto position = static_cast<int64_t>(offset) + bit;
+ if ((edges & one) != 0) {
+ if (_run_start < 0) {
+ _run_start = position;
+ } else {
+ push_run<kLower>(batch, src, _run_start, position);
+ _run_start = -1;
+ }
+ }
+ if ((classes.lead & one) != 0) {
+ push_chinese_char(batch, src, position, size);
+ }
+ }
+ ++_block;
+ }
+ // A run that reaches the end of a value of whole blocks has its end edge
in no block.
+ if (_block == blocks && _run_start >= 0) {
+ push_run<kLower>(batch, src, _run_start, static_cast<int64_t>(size));
+ _run_start = -1;
+ }
+ return batch.size() != 0;
+}
+
+bool BasicTokenizer::hand_out(TokenBatch& batch) {
+ batch.clear();
+ while (_next < _tokens_text.size() && batch.size() < kBatchTokens) {
+ const std::string_view token = _tokens_text[_next++];
+ batch.push(token.substr(0, MAX_WORD_LEN), 1);
+ }
+ return batch.size() != 0;
+}
+
+void BasicTokenizer::cut_with_extra_chars(std::string_view text) {
const auto* s = reinterpret_cast<const uint8_t*>(text.data());
const auto length = static_cast<int32_t>(text.size());
@@ -99,16 +179,14 @@ void BasicTokenizer::cut(std::string_view text) {
continue;
}
- if (IS_CHINESE_CHAR(c)) {
+ if (is_chinese_char(c)) {
const int32_t len = i - prev_i;
_tokens_text.emplace_back(reinterpret_cast<const char*>(s +
prev_i), len);
}
- if constexpr (HasExtraChars) {
- if (c < 128 && _extra_char_set[c]) {
- const int32_t len = i - prev_i;
- _tokens_text.emplace_back(reinterpret_cast<const char*>(s
+ prev_i), len);
- }
+ if (c < 128 && _extra_char_set[c]) {
+ const int32_t len = i - prev_i;
+ _tokens_text.emplace_back(reinterpret_cast<const char*>(s +
prev_i), len);
}
}
}
diff --git
a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.h
b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.h
index de64718e668..b9fcc43c52d 100644
--- a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.h
+++ b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.h
@@ -18,36 +18,55 @@
#pragma once
#include <array>
+#include <cstddef>
+#include <cstdint>
#include <string>
#include <string_view>
#include <vector>
-#include "storage/index/inverted/analysis/per_token_stream.h"
+#include "storage/index/inverted/analysis/text_token_stream.h"
namespace doris::segment_v2::inverted_index {
-// Runs of ASCII letters and digits, each Chinese char, and each extra char as
tokens.
-class BasicTokenizer final : public PerTokenTokenizer {
+// Runs of ASCII letters and digits, cut to MAX_WORD_LEN bytes with the rest
of the run dropped;
+// each character of five CJK ranges; and each extra char. Invalid bytes and
other characters are
+// skipped. With `lowercase`, A-Z is folded to a-z, which is all a lowercase
filter does to these
+// tokens.
+//
+// Without extra chars it classifies the value a block of BYTE_CLASS_BLOCK
bytes at a time, cuts the
+// runs at the edges of the letter-and-digit bits and decodes a character only
at a byte that can
+// start one: only the lead byte is visited. A batch is handed over at the end
+// of the block that fills it. With extra chars it runs the scalar loop, which
has no performance
+// target. The terms are views of the value or of the batch's storage for
lowercased tokens.
+class BasicTokenizer final : public TextTokenizer {
public:
- BasicTokenizer() : PerTokenTokenizer(TermLifetime::kUntilReset) {}
+ explicit BasicTokenizer(bool lowercase = false) : _lowercase(lowercase) {}
+ // ASCII characters that are tokens of their own; none together with
`lowercase`.
void initialize(const std::string& extra_chars = "");
- // The tokens are views of the value; the list of them is kept.
+ void reset(std::string_view text) override;
+ bool next_batch(TokenBatch& batch) override;
+ // The token list of the scalar loop; lowercased terms live in the output
batch.
size_t reserved_bytes() const override {
return _tokens_text.capacity() * sizeof(std::string_view);
}
-protected:
- void on_reset(std::string_view text) override;
- bool next_token(TokenRef& token) override;
-
private:
- template <bool HasExtraChars>
- void cut(std::string_view text);
+ template <bool kLower>
+ bool scan(TokenBatch& batch);
+ void cut_with_extra_chars(std::string_view text);
+ bool hand_out(TokenBatch& batch);
+
+ const bool _lowercase;
+ std::string_view _text;
+ size_t _block = 0; // the next block to classify
+ uint64_t _carry = 0; // 1 when the last byte of the previous block is
a letter or digit
+ int64_t _run_start = -1; // the offset of the run being read, or -1
between runs
- size_t _buffer_index = 0;
+ // The scalar loop cuts the whole value in reset().
std::vector<std::string_view> _tokens_text;
+ size_t _next = 0;
std::array<bool, 128> _extra_char_set {};
bool _has_extra_chars = false;
diff --git
a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer_factory.h
b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer_factory.h
index 147b359bd91..4a7c3743a12 100644
---
a/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer_factory.h
+++
b/be/src/storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer_factory.h
@@ -23,7 +23,8 @@
namespace doris::segment_v2::inverted_index {
class BasicTokenizerFactory : public TokenizerFactory {
public:
- BasicTokenizerFactory() = default;
+ // A custom basic tokenizer does not lowercase; the builtin basic parser
follows lower_case.
+ explicit BasicTokenizerFactory(bool lowercase = false) :
_lowercase(lowercase) {}
~BasicTokenizerFactory() override = default;
void initialize(const Settings& settings) override {
@@ -38,12 +39,13 @@ public:
}
std::unique_ptr<TextTokenizer> create() const override {
- auto tokenizer = std::make_unique<BasicTokenizer>();
+ auto tokenizer = std::make_unique<BasicTokenizer>(_lowercase);
tokenizer->initialize(_extra_chars);
return tokenizer;
}
private:
+ const bool _lowercase;
std::string _extra_chars;
};
diff --git a/be/src/storage/index/inverted/analysis/tokenizer/byte_classifier.h
b/be/src/storage/index/inverted/analysis/tokenizer/byte_classifier.h
new file mode 100644
index 00000000000..edc17157a74
--- /dev/null
+++ b/be/src/storage/index/inverted/analysis/tokenizer/byte_classifier.h
@@ -0,0 +1,107 @@
+// 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.
+
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+#include <cstring>
+#include <string>
+
+#include "util/simd/bits.h"
+
+namespace doris::segment_v2::inverted_index {
+
+// The byte classes the english and basic tokenizers cut by, one bit per byte
of a block of
+// BYTE_CLASS_BLOCK bytes, bit i for byte i.
+inline constexpr size_t BYTE_CLASS_BLOCK = 64;
+
+struct ByteClasses {
+ uint64_t alnum = 0; // ASCII letters and digits
+ uint64_t lead = 0; // 0xC0 and above: the bytes that can start a
multi-byte character
+};
+
+inline bool is_ascii_upper(uint8_t c) {
+ return static_cast<uint8_t>(c - 'A') < 26;
+}
+
+inline bool is_ascii_alnum(uint8_t c) {
+ return static_cast<uint8_t>(c - '0') < 10 || static_cast<uint8_t>((c |
0x20) - 'a') < 26;
+}
+
+inline char ascii_lower(char c) {
+ const auto byte = static_cast<uint8_t>(c);
+ return static_cast<char>(byte +
(static_cast<uint8_t>(is_ascii_upper(byte)) << 5));
+}
+
+// Fold A-Z to a-z while copying the bytes. The source and destination may be
the same buffer.
+inline void ascii_lower(const char* src, char* dst, size_t size) {
+ for (size_t i = 0; i < size; ++i) {
+ dst[i] = ascii_lower(src[i]);
+ }
+}
+
+inline void ascii_lower(std::string& text) {
+ ascii_lower(text.data(), text.data(), text.size());
+}
+
+namespace byte_classifier_detail {
+
+inline uint64_t to_bits64(const uint8_t* bytes) {
+ return static_cast<uint64_t>(simd::bytes32_mask_to_bits32_mask(bytes)) |
+ (static_cast<uint64_t>(simd::bytes32_mask_to_bits32_mask(bytes +
32)) << 32);
+}
+
+} // namespace byte_classifier_detail
+
+// Classifies the BYTE_CLASS_BLOCK readable bytes at `src`. With kLower,
`lowered` receives them
+// with A-Z folded; without, it is not touched. A plain loop the compiler
vectorizes on every
+// target, the byte masks turned into bits the way the Doris filters turn
theirs.
+template <bool kLower>
+inline ByteClasses classify_block(const char* src, char* lowered) {
+ uint8_t alnum[BYTE_CLASS_BLOCK];
+ uint8_t lead[BYTE_CLASS_BLOCK];
+ for (size_t i = 0; i < BYTE_CLASS_BLOCK; ++i) {
+ const auto c = static_cast<uint8_t>(src[i]);
+ const auto upper = static_cast<uint8_t>(static_cast<uint8_t>(c - 'A')
< 26);
+ const auto lower = static_cast<uint8_t>(static_cast<uint8_t>(c - 'a')
< 26);
+ const auto digit = static_cast<uint8_t>(static_cast<uint8_t>(c - '0')
< 10);
+ alnum[i] = upper | lower | digit;
+ lead[i] = static_cast<uint8_t>(c >= 0xC0);
+ if constexpr (kLower) {
+ lowered[i] = static_cast<char>(c + (upper << 5));
+ }
+ }
+ return {.alnum = byte_classifier_detail::to_bits64(alnum),
+ .lead = byte_classifier_detail::to_bits64(lead)};
+}
+
+// classify_block() for the last `size` bytes of a value, 0 < `size` <
BYTE_CLASS_BLOCK. The bytes
+// go through a stack buffer, so nothing past the value is read, and the bits
past `size` are 0.
+template <bool kLower>
+inline ByteClasses classify_tail(const char* src, size_t size, char* lowered) {
+ char block[BYTE_CLASS_BLOCK] = {};
+ std::memcpy(block, src, size);
+ char block_lowered[BYTE_CLASS_BLOCK];
+ const ByteClasses classes = classify_block<kLower>(block, block_lowered);
+ if constexpr (kLower) {
+ std::memcpy(lowered, block_lowered, size);
+ }
+ return classes;
+}
+
+} // namespace doris::segment_v2::inverted_index
diff --git
a/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.cpp
b/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.cpp
new file mode 100644
index 00000000000..62d545303a2
--- /dev/null
+++
b/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.cpp
@@ -0,0 +1,103 @@
+// 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/analysis/tokenizer/english/english_tokenizer.h"
+
+#include <algorithm>
+
+#include "storage/index/inverted/analysis/common/rune.h"
+#include "storage/index/inverted/analysis/tokenizer/byte_classifier.h"
+
+namespace doris::segment_v2::inverted_index {
+
+namespace {
+
+// The run [start, end) as tokens of at most MAX_WORD_LEN bytes.
+template <bool kLower>
+void push_run(TokenBatch& batch, const char* src, int64_t start, int64_t end) {
+ while (start < end) {
+ const auto length = static_cast<size_t>(std::min<int64_t>(end - start,
MAX_WORD_LEN));
+ // Only emitted bytes need storage; separators must not allocate a
row-sized copy.
+ if constexpr (kLower) {
+ char* lowered = batch.allocate_term(length);
+ ascii_lower(src + start, lowered, length);
+ batch.push({lowered, length}, 1);
+ } else {
+ batch.push({src + start, length}, 1);
+ }
+ start += length;
+ }
+}
+
+} // namespace
+
+void EnglishTokenizer::reset(std::string_view text) {
+ _text = text;
+ _block = 0;
+ _carry = 0;
+ _run_start = -1;
+}
+
+bool EnglishTokenizer::next_batch(TokenBatch& batch) {
+ return _lowercase ? scan<true>(batch) : scan<false>(batch);
+}
+
+template <bool kLower>
+bool EnglishTokenizer::scan(TokenBatch& batch) {
+ batch.clear();
+ const size_t size = _text.size();
+ const char* const src = _text.data();
+ const size_t blocks = (size + BYTE_CLASS_BLOCK - 1) / BYTE_CLASS_BLOCK;
+ while (_block < blocks && batch.size() < kBatchTokens) {
+ const size_t offset = _block * BYTE_CLASS_BLOCK;
+ const ByteClasses classes =
+ offset + BYTE_CLASS_BLOCK <= size
+ ? classify_block<false>(src + offset, nullptr)
+ : classify_tail<false>(src + offset, size - offset,
nullptr);
+ const uint64_t alnum = classes.alnum;
+ // A bit where a run starts or where the byte after a run is.
+ uint64_t edges = alnum ^ ((alnum << 1) | _carry);
+ _carry = alnum >> 63;
+ while (edges != 0) {
+ const auto position = static_cast<int64_t>(offset) +
__builtin_ctzll(edges);
+ edges &= edges - 1;
+ if (_run_start < 0) {
+ _run_start = position;
+ } else {
+ push_run<kLower>(batch, src, _run_start, position);
+ _run_start = -1;
+ }
+ }
+ ++_block;
+ // Emit complete pieces before the run ends so an uninterrupted value
can yield a batch.
+ if (_run_start >= 0) {
+ const auto end = static_cast<int64_t>(std::min(_block *
BYTE_CLASS_BLOCK, size));
+ while (end - _run_start >= MAX_WORD_LEN) {
+ push_run<kLower>(batch, src, _run_start, _run_start +
MAX_WORD_LEN);
+ _run_start += MAX_WORD_LEN;
+ }
+ }
+ }
+ // A run that reaches the end of a value of whole blocks has its end edge
in no block.
+ if (_block == blocks && _run_start >= 0) {
+ push_run<kLower>(batch, src, _run_start, static_cast<int64_t>(size));
+ _run_start = -1;
+ }
+ return batch.size() != 0;
+}
+
+} // namespace doris::segment_v2::inverted_index
diff --git
a/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.h
b/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.h
new file mode 100644
index 00000000000..bfc1b0cee2f
--- /dev/null
+++
b/be/src/storage/index/inverted/analysis/tokenizer/english/english_tokenizer.h
@@ -0,0 +1,73 @@
+// 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.
+
+#pragma once
+
+#include <cstddef>
+#include <cstdint>
+#include <memory>
+#include <string_view>
+
+#include "storage/index/inverted/analysis/text_token_stream.h"
+#include "storage/index/inverted/analysis/tokenizer/tokenizer_factory.h"
+
+namespace doris::segment_v2::inverted_index {
+
+// The tokenizer of the english parser and of an unknown one: the runs of
ASCII letters and digits,
+// a run longer than MAX_WORD_LEN bytes cut into pieces of at most
MAX_WORD_LEN bytes, each one
+// position after the last; with `lowercase`, A-Z folded to a-z. CLucene's
SimpleTokenizer<char>
+// made the same tokens.
+//
+// It classifies the value a block of BYTE_CLASS_BLOCK bytes at a time and
cuts at the edges of the
+// letter-and-digit bits. A batch is handed over at the end of the block that
fills it, so it may
+// hold a few dozen tokens more than kBatchTokens. The terms are views of the
value or of the
+// batch's storage for lowercased tokens.
+class EnglishTokenizer final : public TextTokenizer {
+public:
+ explicit EnglishTokenizer(bool lowercase) : _lowercase(lowercase) {}
+
+ void reset(std::string_view text) override;
+ bool next_batch(TokenBatch& batch) override;
+ size_t reserved_bytes() const override { return 0; }
+
+private:
+ template <bool kLower>
+ bool scan(TokenBatch& batch);
+
+ const bool _lowercase;
+ std::string_view _text;
+ size_t _block = 0; // the next block to classify
+ uint64_t _carry = 0; // 1 when the last byte of the previous block is
a letter or digit
+ int64_t _run_start = -1; // the next run fragment's offset, or -1 between
runs
+};
+
+// The tokenizer of the builtin english parser; english is no custom tokenizer.
+class EnglishTokenizerFactory final : public TokenizerFactory {
+public:
+ explicit EnglishTokenizerFactory(bool lowercase) : _lowercase(lowercase) {}
+
+ void initialize(const Settings& settings) override {}
+
+ std::unique_ptr<TextTokenizer> create() const override {
+ return std::make_unique<EnglishTokenizer>(_lowercase);
+ }
+
+private:
+ const bool _lowercase;
+};
+
+} // namespace doris::segment_v2::inverted_index
diff --git a/be/src/util/simd/bits.h b/be/src/util/simd/bits.h
index b0bc7c1f654..609d922630c 100644
--- a/be/src/util/simd/bits.h
+++ b/be/src/util/simd/bits.h
@@ -80,6 +80,16 @@ inline uint32_t bytes32_mask_to_bits32_mask(const uint8_t*
data) {
_mm_loadu_si128(reinterpret_cast<const __m128i*>(data +
16)), zero16)))
<< 16) &
0xffff0000);
+#elif defined(__ARM_NEON) && defined(__aarch64__)
+ // Each set byte keeps its bit weight, and every eight weights add up to
one byte of the mask.
+ const uint8x16_t weights = {1, 2, 4, 8, 16, 32, 64, 128, 1, 2, 4, 8, 16,
32, 64, 128};
+ const auto bits16 = [&weights](const uint8_t* half) {
+ const uint8x16_t set =
+ vandq_u8(vcgtq_s8(vreinterpretq_s8_u8(vld1q_u8(half)),
vdupq_n_s8(0)), weights);
+ return static_cast<uint32_t>(vaddv_u8(vget_low_u8(set))) |
+ (static_cast<uint32_t>(vaddv_u8(vget_high_u8(set))) << 8);
+ };
+ uint32_t mask = bits16(data) | (bits16(data + 16) << 16);
#else
uint32_t mask = 0;
for (std::size_t i = 0; i < 32; ++i) {
diff --git a/be/test/storage/index/inverted/analysis/component_stream_test.cpp
b/be/test/storage/index/inverted/analysis/component_stream_test.cpp
index fb1d2de5626..0c995dc84a1 100644
--- a/be/test/storage/index/inverted/analysis/component_stream_test.cpp
+++ b/be/test/storage/index/inverted/analysis/component_stream_test.cpp
@@ -48,6 +48,7 @@
#include "storage/index/inverted/analysis/token_filter/token_filter_factory.h"
#include "storage/index/inverted/analysis/token_filter/word_delimiter_filter.h"
#include "storage/index/inverted/analysis/tokenizer/basic/basic_tokenizer.h"
+#include
"storage/index/inverted/analysis/tokenizer/english/english_tokenizer.h"
#include "storage/index/inverted/analysis/tokenizer/icu/icu_tokenizer.h"
#include "storage/index/inverted/analysis/tokenizer/ngram/gram_tokenizer.h"
#include "storage/index/inverted/analysis/tokenizer/ngram/ngram_tokenizer.h"
@@ -63,7 +64,7 @@ constexpr size_t kLongRowBytes = 2 * 1024 * 1024;
constexpr size_t kReservedAfterShortRowLimit = 1024 * 1024;
Settings settings_of(std::unordered_map<std::string, std::string> args) {
- return Settings(std::move(args));
+ return {std::move(args)};
}
std::string repeat_to(std::string_view unit, size_t bytes) {
@@ -221,16 +222,64 @@ TEST(ComponentStreamTest, CharGroupTokenizerKeepsNothing)
{
[] { return size_t {0}; });
}
-TEST(ComponentStreamTest, BasicTokenizerReleasesItsTokenList) {
+size_t basic_member_bytes(const BasicTokenizer& basic) {
+ return basic._tokens_text.capacity() * sizeof(std::string_view);
+}
+
+TEST(ComponentStreamTest, LowercaseTokenizersBoundScratchWithinRow) {
+ std::vector<std::unique_ptr<TextTokenStream>> streams;
+ streams.push_back(std::make_unique<EnglishTokenizer>(true));
+ streams.push_back(std::make_unique<BasicTokenizer>(true));
+ constexpr size_t kMaxScratchBytes = 256 * 1024;
+ for (auto& stream : streams) {
+ for (char fill : {' ', 'A'}) {
+ SCOPED_TRACE(fill);
+ const std::string row(10 * 1024 * 1024, fill);
+ stream->reset(row);
+ ASSERT_LE(stream->reserved_bytes(), kMaxScratchBytes);
+ TokenBatch batch;
+ size_t tokens = 0;
+ while (stream->next_batch(batch)) {
+ ASSERT_LE(stream->reserved_bytes() + batch.capacity_bytes(),
kMaxScratchBytes);
+ tokens += batch.size();
+ }
+ EXPECT_EQ(tokens == 0, fill == ' ');
+ EXPECT_LE(stream->reserved_bytes() + batch.capacity_bytes(),
kMaxScratchBytes);
+ }
+ }
+}
+
+TEST(ComponentStreamTest, BasicTokenizerReleasesItsBuffers) {
Components components;
+ // The block loop keeps nothing in proportion to the value; the scalar
loop of extra chars
+ // keeps its token list.
for (const Settings& settings : {Settings {}, settings_of({{"extra_chars",
"-_"}})}) {
expect_text_stream_contract([&] { return components.tokenizer("basic",
settings); },
contract_texts());
auto tokenizer = components.tokenizer("basic", settings);
auto& basic = as<BasicTokenizer>(*tokenizer);
- expect_released_at_next_row(
- *tokenizer, repeat_to("ab ", kLongRowBytes), "short", true,
- [&] { return basic._tokens_text.capacity() *
sizeof(std::string_view); });
+ expect_released_at_next_row(*tokenizer, repeat_to("ab ",
kLongRowBytes), "short",
+ basic._has_extra_chars,
+ [&] { return basic_member_bytes(basic); });
+ }
+ // The builtin basic parser keeps lowercased terms in the output batch.
+ expect_text_stream_contract([] { return
std::make_unique<BasicTokenizer>(true); },
+ contract_texts());
+ BasicTokenizer lowering(true);
+ lowering.initialize();
+ expect_released_at_next_row(lowering, repeat_to("Ab ", kLongRowBytes),
"short", false,
+ [&] { return basic_member_bytes(lowering); });
+}
+
+TEST(ComponentStreamTest, EnglishTokenizerKeepsNoRowSizedScratch) {
+ for (bool lowercase : {true, false}) {
+ SCOPED_TRACE(lowercase);
+ expect_text_stream_contract(
+ [lowercase] { return
std::make_unique<EnglishTokenizer>(lowercase); },
+ contract_texts());
+ EnglishTokenizer english(lowercase);
+ expect_released_at_next_row(english, repeat_to("Ab ", kLongRowBytes),
"short", false,
+ [] { return size_t {0}; });
}
}
@@ -441,7 +490,7 @@ TEST(ComponentStreamTest,
AValueAChainFoldsToNothingMakesNoToken) {
EXPECT_TRUE(collect_checked(*stream, "").empty());
}
-TEST(ComponentStreamTest, StrictUtf8ThrowsInIcuAndNGramOnly) {
+TEST(ComponentStreamTest, StrictUtf8ThrowsInIcuAndNGram) {
DictPathScope dict_path;
Components components;
const std::string invalid =
@@ -462,6 +511,13 @@ TEST(ComponentStreamTest,
StrictUtf8ThrowsInIcuAndNGramOnly) {
strict->set_strict_utf8(false);
EXPECT_EQ(collect_terms(*strict, invalid), lenient_terms);
}
+}
+
+TEST(ComponentStreamTest, StrictUtf8LeavesTheOtherTokenizersAlone) {
+ Components components;
+ const std::string invalid =
+ "ab\xFF"
+ "cd";
for (const char* name : {"standard", "keyword", "basic", "char_group"}) {
SCOPED_TRACE(name);
auto lenient = components.tokenizer(name);
diff --git
a/be/test/storage/index/inverted/analysis/tokenizer/basic_tokenizer_test.cpp
b/be/test/storage/index/inverted/analysis/tokenizer/basic_tokenizer_test.cpp
new file mode 100644
index 00000000000..51b038bc1b3
--- /dev/null
+++ b/be/test/storage/index/inverted/analysis/tokenizer/basic_tokenizer_test.cpp
@@ -0,0 +1,236 @@
+// 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/analysis/tokenizer/basic/basic_tokenizer.h"
+
+#include <gtest/gtest.h>
+#include <sys/mman.h>
+#include <unicode/uchar.h>
+#include <unicode/utf8.h>
+#include <unistd.h>
+
+#include <algorithm>
+#include <cstring>
+#include <random>
+#include <string>
+#include <string_view>
+#include <vector>
+
+#include "storage/index/inverted/analysis/analyzer/analyzer.h"
+#include "storage/index/inverted/analysis/text_stream_contract.h"
+
+namespace doris::segment_v2::inverted_index {
+namespace {
+
+// The basic parser as production builds it.
+TextAnalyzerPtr basic_analyzer(bool lowercase) {
+ return
InvertedIndexAnalyzer::create_builtin_analyzer(InvertedIndexParserType::PARSER_BASIC,
"",
+ lowercase ? "true" :
"false", "");
+}
+
+bool reference_chinese(UChar32 c) {
+ const auto in = [c](UChar32 lo, UChar32 hi) { return c >= lo && c <= hi; };
+ return in(0x4E00, 0x9FFF) || in(0x3400, 0x4DBF) || in(0x20000, 0x2A6DF) ||
+ in(0x2A700, 0x2EBEF) || in(0x30000, 0x3134A);
+}
+
+bool reference_alnum(uint8_t c) {
+ return (c >= '0' && c <= '9') || (c >= 'a' && c <= 'z') || (c >= 'A' && c
<= 'Z');
+}
+
+// The run of letters and digits at `i`, which moves past it, cut to 255 bytes
and lowered the
+// way the lowercase filter lowered it.
+std::string reference_run(const uint8_t* s, int32_t& i, int32_t length, bool
lowercase) {
+ const int32_t start = i;
+ while (i < length && reference_alnum(s[i])) {
+ ++i;
+ }
+ std::string term(reinterpret_cast<const char*>(s + start), std::min(i -
start, 255));
+ if (lowercase) {
+ for (char& c : term) {
+ c = static_cast<char>(c >= 'A' && c <= 'Z' ? c - 'A' + 'a' : c);
+ }
+ }
+ return term;
+}
+
+// The tokens of the scalar loop the basic tokenizer had, lowercased the way
the lowercase filter
+// that followed it lowercased them.
+std::vector<CollectedToken> reference_basic(std::string_view text, bool
lowercase) {
+ std::vector<CollectedToken> tokens;
+ const auto* s = reinterpret_cast<const uint8_t*>(text.data());
+ const auto length = static_cast<int32_t>(text.size());
+ for (int32_t i = 0; i < length;) {
+ if (reference_alnum(s[i])) {
+ tokens.push_back(
+ {.term = reference_run(s, i, length, lowercase),
.position_increment = 1});
+ } else {
+ const int32_t start = i;
+ UChar32 c = U_UNASSIGNED;
+ U8_NEXT(s, i, length, c);
+ if (c >= 0 && reference_chinese(c)) {
+ tokens.push_back(
+ {.term = std::string(reinterpret_cast<const char*>(s +
start), i - start),
+ .position_increment = 1});
+ }
+ }
+ }
+ return tokens;
+}
+
+std::string random_value(std::mt19937_64& random) {
+ static const std::vector<std::string> kPieces = {
+ "a", "Bc", "9", " ", "中", "文", "\xF0\xA0\x80\x80",
+ "é", "\xE4\xB8", "\x80", "\xFF", "-", "\n"};
+ const size_t size = random() % 700;
+ std::string value;
+ switch (random() % 3) {
+ case 0:
+ for (size_t i = 0; i < size; ++i) {
+ value.push_back(static_cast<char>(random()));
+ }
+ break;
+ case 1:
+ while (value.size() < size) {
+ value += kPieces[random() % kPieces.size()];
+ }
+ break;
+ default:
+ while (value.size() < size) {
+ value.append(random() % 400, static_cast<char>('A' + random() %
26));
+ value += random() % 2 == 0 ? "中" : " ";
+ }
+ break;
+ }
+ return value;
+}
+
+TEST(BasicTokenizerTest, MatchesTheScalarLoopOnRandomBytes) {
+ for (bool lowercase : {true, false}) {
+ SCOPED_TRACE(lowercase);
+ const TextAnalyzerPtr analyzer = basic_analyzer(lowercase);
+ const std::unique_ptr<TextTokenStream> reused =
analyzer->create_stream();
+ std::mt19937_64 random(lowercase ? 31 : 32);
+ for (int round = 0; round < 20000; ++round) {
+ const std::string value = random_value(random);
+ const std::vector<CollectedToken> expected =
reference_basic(value, lowercase);
+ ASSERT_EQ(collect_checked(*analyzer, value), expected);
+ ASSERT_EQ(collect_checked(*reused, value), expected);
+ }
+ }
+}
+
+TEST(BasicTokenizerTest, CutsAtBlockBoundaries) {
+ const TextAnalyzerPtr analyzer = basic_analyzer(true);
+ const std::string spaces63(63, ' ');
+ for (const std::string& value :
+ {spaces63 + "中", spaces63 + "\xF0\xA0\x80\x80", spaces63 + "Abc",
spaces63 + "abc中",
+ std::string("abc中"), std::string(64, 'x'), std::string(62, ' ') +
"中x",
+ std::string(60, ' ') + "CrossThe64", std::string(128, 'Q') + "中" +
std::string(127, 'R'),
+ std::string(64, ' ') + "start"}) {
+ EXPECT_EQ(collect_checked(*analyzer, value), reference_basic(value,
true));
+ }
+ EXPECT_EQ(collect_terms(*analyzer, spaces63 + "中"),
std::vector<std::string> {"中"});
+ EXPECT_EQ(collect_terms(*analyzer, "abc中"), (std::vector<std::string>
{"abc", "中"}));
+}
+
+TEST(BasicTokenizerTest, ALongRunIsCutToMaxWordLenAndTheRestDropped) {
+ EXPECT_EQ(collect_terms(*basic_analyzer(true), std::string(300, 'a')),
+ std::vector<std::string> {std::string(255, 'a')});
+}
+
+TEST(BasicTokenizerTest, BatchesLoseNoTokenAroundTheBatchSize) {
+ const TextAnalyzerPtr analyzer = basic_analyzer(true);
+ for (size_t count : {size_t {255}, size_t {256}, size_t {257}, size_t
{512}}) {
+ std::string value;
+ for (size_t i = 0; i < count; ++i) {
+ value += i % 2 == 0 ? "文" : "w" + std::to_string(i) + " ";
+ }
+ const std::vector<CollectedToken> tokens = collect_checked(*analyzer,
value);
+ ASSERT_EQ(tokens.size(), count);
+ EXPECT_EQ(tokens, reference_basic(value, true));
+ }
+}
+
+TEST(BasicTokenizerTest, WithoutLowercaseTheTermsAreViewsOfTheValue) {
+ const std::string value = "Mixed CASE 中文 words 123";
+ BasicTokenizer tokenizer(false);
+ tokenizer.initialize();
+ tokenizer.reset(value);
+ TokenBatch batch;
+ size_t count = 0;
+ while (tokenizer.next_batch(batch)) {
+ for (const TokenRef& token : batch.tokens()) {
+ EXPECT_GE(token.data, value.data());
+ EXPECT_LE(token.data + token.size, value.data() + value.size());
+ ++count;
+ }
+ }
+ EXPECT_EQ(count, 6); // Mixed, CASE, two CJK characters, words, and 123.
+ EXPECT_EQ(tokenizer.reserved_bytes(), 0);
+}
+
+TEST(BasicTokenizerTest, ReadsNothingPastTheValue) {
+ const size_t page_size = sysconf(_SC_PAGESIZE);
+ void* mapping = mmap(nullptr, page_size * 3, PROT_NONE, MAP_PRIVATE |
MAP_ANONYMOUS, -1, 0);
+ ASSERT_NE(mapping, MAP_FAILED);
+ auto* page = static_cast<char*>(mapping) + page_size;
+ ASSERT_EQ(mprotect(page, page_size, PROT_READ | PROT_WRITE), 0);
+ for (bool lowercase : {true, false}) {
+ BasicTokenizer tokenizer(lowercase);
+ tokenizer.initialize();
+ for (size_t size = 1; size <= 200; ++size) {
+ char* const value = page + page_size - size;
+ // A truncated UTF-8 character must not read past the value.
+ std::memset(value, 'K', size);
+ value[size - 1] = '\xE4';
+ const std::string_view text(value, size);
+ EXPECT_EQ(collect_checked(tokenizer, text), reference_basic(text,
lowercase));
+ }
+ }
+ EXPECT_EQ(munmap(mapping, page_size * 3), 0);
+}
+
+TEST(BasicTokenizerTest, ExtraCharsKeepTheScalarLoop) {
+ BasicTokenizer tokenizer;
+ tokenizer.initialize("-_");
+ EXPECT_EQ(collect_terms(tokenizer, "a-b_c 中"),
+ (std::vector<std::string> {"a", "-", "b", "_", "c", "中"}));
+ expect_text_stream_contract(
+ [] {
+ auto stream = std::make_unique<BasicTokenizer>();
+ stream->initialize("-");
+ return stream;
+ },
+ {"", "x-y", std::string(300, 'b') + "-", std::string(600, '-')});
+}
+
+TEST(BasicTokenizerTest, KeepsTheStreamContract) {
+ for (bool lowercase : {true, false}) {
+ const TextAnalyzerPtr analyzer = basic_analyzer(lowercase);
+ std::string many_batches;
+ for (int i = 0; i < 2000; ++i) {
+ many_batches += "Word" + std::to_string(i % 97) + "中";
+ }
+ expect_text_stream_contract([&] { return analyzer->create_stream(); },
+ {"", "Hello World", "a", std::string(300,
'Z'),
+ "中文 mixed ÄÖÜ 123", many_batches});
+ }
+}
+
+} // namespace
+} // namespace doris::segment_v2::inverted_index
diff --git
a/be/test/storage/index/inverted/analysis/tokenizer/byte_classifier_test.cpp
b/be/test/storage/index/inverted/analysis/tokenizer/byte_classifier_test.cpp
new file mode 100644
index 00000000000..3f70981f3fc
--- /dev/null
+++ b/be/test/storage/index/inverted/analysis/tokenizer/byte_classifier_test.cpp
@@ -0,0 +1,172 @@
+// 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/analysis/tokenizer/byte_classifier.h"
+
+#include <gtest/gtest.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+#include <array>
+#include <cstdint>
+#include <cstdlib>
+#include <cstring>
+#include <random>
+#include <string>
+
+namespace doris::segment_v2::inverted_index {
+namespace {
+
+// The classes byte by byte, written without any of the tricks of the
classifier.
+ByteClasses reference_classes(const char* src, size_t size, char* lowered) {
+ ByteClasses classes;
+ for (size_t i = 0; i < size; ++i) {
+ const auto c = static_cast<unsigned char>(src[i]);
+ const bool upper = c >= 'A' && c <= 'Z';
+ const bool alnum = upper || (c >= 'a' && c <= 'z') || (c >= '0' && c
<= '9');
+ if (alnum) {
+ classes.alnum |= uint64_t {1} << i;
+ }
+ if (c >= 0xC0) {
+ classes.lead |= uint64_t {1} << i;
+ }
+ lowered[i] = static_cast<char>(upper ? c - 'A' + 'a' : c);
+ }
+ return classes;
+}
+
+void expect_block_matches(const char* src) {
+ char lowered[BYTE_CLASS_BLOCK];
+ char expected_lowered[BYTE_CLASS_BLOCK];
+ const ByteClasses classes = classify_block<true>(src, lowered);
+ const ByteClasses expected = reference_classes(src, BYTE_CLASS_BLOCK,
expected_lowered);
+ EXPECT_EQ(classes.alnum, expected.alnum);
+ EXPECT_EQ(classes.lead, expected.lead);
+ EXPECT_EQ(std::string(lowered, BYTE_CLASS_BLOCK),
+ std::string(expected_lowered, BYTE_CLASS_BLOCK));
+ // Without lowering, the classes are the same and the output buffer is not
touched.
+ char untouched[BYTE_CLASS_BLOCK];
+ std::memset(untouched, 0x5A, sizeof(untouched));
+ const ByteClasses unlowered = classify_block<false>(src, untouched);
+ EXPECT_EQ(unlowered.alnum, expected.alnum);
+ EXPECT_EQ(unlowered.lead, expected.lead);
+ for (char c : untouched) {
+ ASSERT_EQ(c, 0x5A);
+ }
+}
+
+TEST(ByteClassifierTest, EveryByteValueInEveryPosition) {
+ std::array<char, BYTE_CLASS_BLOCK> block {};
+ for (int value = 0; value < 256; ++value) {
+ // The value alone in each position, among spaces, and filling the
whole block.
+ for (size_t position = 0; position < BYTE_CLASS_BLOCK; ++position) {
+ block.fill(' ');
+ block[position] = static_cast<char>(value);
+ expect_block_matches(block.data());
+ }
+ block.fill(static_cast<char>(value));
+ expect_block_matches(block.data());
+ }
+}
+
+TEST(ByteClassifierTest, RandomBlocks) {
+ std::mt19937_64 random(20261103);
+ std::array<char, BYTE_CLASS_BLOCK> block {};
+ for (int round = 0; round < 20000; ++round) {
+ for (char& c : block) {
+ c = static_cast<char>(random());
+ }
+ expect_block_matches(block.data());
+ }
+}
+
+TEST(ByteClassifierTest, EveryTailLength) {
+ std::mt19937_64 random(7);
+ std::array<char, BYTE_CLASS_BLOCK> source {};
+ for (size_t size = 1; size < BYTE_CLASS_BLOCK; ++size) {
+ for (int round = 0; round < 200; ++round) {
+ for (char& c : source) {
+ c = static_cast<char>(random());
+ }
+ char lowered[BYTE_CLASS_BLOCK];
+ std::memset(lowered, 0x5A, sizeof(lowered));
+ char expected_lowered[BYTE_CLASS_BLOCK];
+ const ByteClasses classes = classify_tail<true>(source.data(),
size, lowered);
+ const ByteClasses expected = reference_classes(source.data(),
size, expected_lowered);
+ ASSERT_EQ(classes.alnum, expected.alnum) << "size " << size;
+ ASSERT_EQ(classes.lead, expected.lead) << "size " << size;
+ ASSERT_EQ(std::string(lowered, size),
std::string(expected_lowered, size));
+ // Nothing past the tail is written.
+ for (size_t i = size; i < BYTE_CLASS_BLOCK; ++i) {
+ ASSERT_EQ(lowered[i], 0x5A);
+ }
+ }
+ }
+}
+
+TEST(ByteClassifierTest, TailReadsNothingPastTheValue) {
+ const size_t page_size = sysconf(_SC_PAGESIZE);
+ void* mapping = mmap(nullptr, page_size * 3, PROT_NONE, MAP_PRIVATE |
MAP_ANONYMOUS, -1, 0);
+ ASSERT_NE(mapping, MAP_FAILED);
+ auto* page = static_cast<char*>(mapping) + page_size;
+ ASSERT_EQ(mprotect(page, page_size, PROT_READ | PROT_WRITE), 0);
+ // A tail that ends at the guard page after the readable one: reading past
it would fault.
+ for (size_t size = 1; size < BYTE_CLASS_BLOCK; ++size) {
+ char* const value = page + page_size - size;
+ std::memset(value, 'A', size);
+ char lowered[BYTE_CLASS_BLOCK];
+ const ByteClasses classes = classify_tail<true>(value, size, lowered);
+ EXPECT_EQ(classes.alnum, (uint64_t {1} << size) - 1);
+ EXPECT_EQ(std::string(lowered, size), std::string(size, 'a'));
+ }
+ EXPECT_EQ(munmap(mapping, page_size * 3), 0);
+}
+
+TEST(ByteClassifierTest, AsciiLowerFoldsOnlyUpperCaseAscii) {
+ std::string all;
+ for (int value = 0; value < 256; ++value) {
+ all.push_back(static_cast<char>(value));
+ }
+ std::string lowered = all;
+ ascii_lower(lowered);
+ for (int value = 0; value < 256; ++value) {
+ const char expected =
+ value >= 'A' && value <= 'Z' ? static_cast<char>(value - 'A' +
'a') : all[value];
+ EXPECT_EQ(lowered[value], expected) << value;
+ }
+}
+
+// The build that runs the unit tests without AVX2 (USE_AVX2=0, its own
CMAKE_BUILD_DIR) sets
+// EXPECT_NO_AVX2 when it runs them, so a CMake cache that kept AVX2 on fails
here instead of
+// passing as a second AVX2 run.
+TEST(ByteClassifierTest, BuiltWithTheExpectedVectorWidth) {
+ const char* expect_no_avx2 = std::getenv("EXPECT_NO_AVX2");
+#ifdef __AVX2__
+ constexpr bool kAvx2 = true;
+#else
+ constexpr bool kAvx2 = false;
+#endif
+ if (expect_no_avx2 != nullptr && std::string(expect_no_avx2) == "1") {
+ EXPECT_FALSE(kAvx2);
+ } else {
+ GTEST_SKIP() << "AVX2 is " << (kAvx2 ? "on" : "off") << "; set
EXPECT_NO_AVX2=1 to check "
+ << "a build without it";
+ }
+}
+
+} // namespace
+} // namespace doris::segment_v2::inverted_index
diff --git
a/be/test/storage/index/inverted/analysis/tokenizer/english_tokenizer_test.cpp
b/be/test/storage/index/inverted/analysis/tokenizer/english_tokenizer_test.cpp
new file mode 100644
index 00000000000..f9436a7df6d
--- /dev/null
+++
b/be/test/storage/index/inverted/analysis/tokenizer/english_tokenizer_test.cpp
@@ -0,0 +1,231 @@
+// 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/analysis/tokenizer/english/english_tokenizer.h"
+
+#include <CLucene.h> // IWYU pragma: keep
+#include <gtest/gtest.h>
+#include <sys/mman.h>
+#include <unistd.h>
+
+#include <algorithm>
+#include <cstring>
+#include <memory>
+#include <random>
+#include <string>
+#include <string_view>
+#include <vector>
+
+#include "storage/index/inverted/analysis/analyzer/analyzer.h"
+#include "storage/index/inverted/analysis/common/rune.h"
+#include "storage/index/inverted/analysis/golden/golden_driver.h"
+#include "storage/index/inverted/analysis/text_stream_contract.h"
+
+namespace doris::segment_v2::inverted_index {
+namespace {
+
+// The english parser as production builds it.
+TextAnalyzerPtr english_analyzer(bool lowercase) {
+ return
InvertedIndexAnalyzer::create_builtin_analyzer(InvertedIndexParserType::PARSER_ENGLISH,
+ "", lowercase ?
"true" : "false", "");
+}
+
+// CLucene's SimpleAnalyzer<char>, which made the english tokens before.
+std::unique_ptr<golden::GoldenDriver> clucene_english(bool lowercase) {
+ return golden::make_lucene_driver([lowercase] {
+ auto analyzer =
std::make_shared<lucene::analysis::SimpleAnalyzer<char>>();
+ analyzer->set_lowercase(lowercase);
+ return analyzer;
+ });
+}
+
+// Values that stress the cuts: any byte, letters and digits in long runs,
UTF-8 between them.
+std::string random_value(std::mt19937_64& random) {
+ static const std::vector<std::string> kPieces = {"a", "B", "z9", "Q", " ",
+ "-", "\n", "中", "é",
"\xF0\x9F\x98\x80"};
+ const size_t size = random() % 700;
+ std::string value;
+ switch (random() % 3) {
+ case 0:
+ for (size_t i = 0; i < size; ++i) {
+ value.push_back(static_cast<char>(random()));
+ }
+ break;
+ case 1:
+ while (value.size() < size) {
+ value += kPieces[random() % kPieces.size()];
+ }
+ break;
+ default:
+ // Runs long enough to be cut at MAX_WORD_LEN, with a separator now
and then.
+ while (value.size() < size) {
+ value.append(random() % 400, static_cast<char>('a' + random() %
26));
+ value.push_back(random() % 2 == 0 ? ' ' : static_cast<char>(0x80 +
random() % 128));
+ }
+ break;
+ }
+ return value;
+}
+
+void expect_same_as_clucene(const std::string& value, golden::GoldenDriver&
candidate,
+ golden::GoldenDriver& oracle) {
+ ASSERT_EQ(candidate.fresh(value), oracle.fresh(value))
+ << golden::format_line(oracle.fresh(value));
+ ASSERT_EQ(candidate.reused(value), oracle.reused(value));
+}
+
+TEST(EnglishTokenizerTest, MatchesSimpleTokenizerOnRandomBytes) {
+ for (bool lowercase : {true, false}) {
+ SCOPED_TRACE(lowercase);
+ auto oracle = clucene_english(lowercase);
+ auto candidate = golden::make_text_driver(english_analyzer(lowercase));
+ std::mt19937_64 random(lowercase ? 20261103 : 20261104);
+ for (int round = 0; round < 20000; ++round) {
+ expect_same_as_clucene(random_value(random), *candidate, *oracle);
+ }
+ }
+}
+
+TEST(EnglishTokenizerTest, CutsAtBlockBoundaries) {
+ auto oracle = clucene_english(true);
+ auto candidate = golden::make_text_driver(english_analyzer(true));
+ const std::string spaces63(63, ' ');
+ for (const std::string& value :
+ {spaces63 + "中", spaces63 + "Abc", spaces63 + "abc中",
std::string("abc中"),
+ std::string(64, 'x'), std::string(64, 'x') + "Y", std::string(60, '
') + "CrossThe64",
+ std::string(128, 'q') + " " + std::string(127, 'r'), std::string(63,
'a') + " b",
+ std::string(64, ' ') + "start", std::string(255, 'a'),
std::string(256, 'a'),
+ std::string(510, 'a'), std::string(511, 'a')}) {
+ expect_same_as_clucene(value, *candidate, *oracle);
+ }
+ EXPECT_EQ(collect_terms(*english_analyzer(true), spaces63 + "Abc"),
+ std::vector<std::string> {"abc"});
+}
+
+TEST(EnglishTokenizerTest, ALongRunIsCutEveryMaxWordLenBytes) {
+ const std::vector<std::string> terms =
+ collect_terms(*english_analyzer(true), std::string(300, 'a'));
+ EXPECT_EQ(terms, (std::vector<std::string> {std::string(255, 'a'),
std::string(45, 'a')}));
+}
+
+TEST(EnglishTokenizerTest, LongRunsUseBoundedBatches) {
+ const std::string value(10 * 1024 * 1024, 'A');
+ for (bool lowercase : {true, false}) {
+ SCOPED_TRACE(lowercase);
+ EnglishTokenizer tokenizer(lowercase);
+ tokenizer.reset(value);
+ TokenBatch batch;
+ size_t bytes = 0;
+ size_t tokens = 0;
+ while (tokenizer.next_batch(batch)) {
+ ASSERT_LE(batch.size(), TextTokenStream::kBatchTokens + 64);
+ for (const TokenRef& token : batch.tokens()) {
+ const size_t length = std::min<size_t>(MAX_WORD_LEN,
value.size() - bytes);
+ ASSERT_EQ(token.term(), std::string(length, lowercase ? 'a' :
'A'));
+ EXPECT_EQ(token.position_increment, 1);
+ bytes += length;
+ ++tokens;
+ }
+ }
+ EXPECT_EQ(bytes, value.size());
+ EXPECT_EQ(tokens, (value.size() + MAX_WORD_LEN - 1) / MAX_WORD_LEN);
+ }
+}
+
+TEST(EnglishTokenizerTest, LongRunsResumeAcrossBatchAndRunBoundaries) {
+ const size_t boundary = TextTokenStream::kBatchTokens * MAX_WORD_LEN;
+ for (bool lowercase : {true, false}) {
+ auto oracle = clucene_english(lowercase);
+ auto candidate = golden::make_text_driver(english_analyzer(lowercase));
+ for (size_t length : {boundary - 1, boundary, boundary + 1, boundary +
64}) {
+ SCOPED_TRACE(length);
+ expect_same_as_clucene("Lead " + std::string(length, 'Z') + "
Tail", *candidate,
+ *oracle);
+ }
+ }
+}
+
+TEST(EnglishTokenizerTest, BatchesLoseNoTokenAroundTheBatchSize) {
+ auto oracle = clucene_english(true);
+ auto candidate = golden::make_text_driver(english_analyzer(true));
+ for (size_t count : {size_t {255}, size_t {256}, size_t {257}, size_t
{512}}) {
+ std::string value;
+ for (size_t i = 0; i < count; ++i) {
+ value += "w" + std::to_string(i) + " ";
+ }
+ const std::vector<CollectedToken> tokens =
collect_checked(*english_analyzer(true), value);
+ ASSERT_EQ(tokens.size(), count);
+ for (size_t i = 0; i < count; ++i) {
+ EXPECT_EQ(tokens[i].term, "w" + std::to_string(i));
+ EXPECT_EQ(tokens[i].position_increment, 1);
+ }
+ expect_same_as_clucene(value, *candidate, *oracle);
+ }
+}
+
+TEST(EnglishTokenizerTest, WithoutLowercaseTheTermsAreViewsOfTheValue) {
+ const std::string value = "Mixed CASE words 123 and Ünïcode-ish ASCII";
+ EnglishTokenizer tokenizer(false);
+ tokenizer.reset(value);
+ TokenBatch batch;
+ size_t count = 0;
+ while (tokenizer.next_batch(batch)) {
+ for (const TokenRef& token : batch.tokens()) {
+ EXPECT_GE(token.data, value.data());
+ EXPECT_LE(token.data + token.size, value.data() + value.size());
+ ++count;
+ }
+ }
+ EXPECT_EQ(count, 9); // Mixed CASE words 123 and n code ish ASCII
+ EXPECT_EQ(tokenizer.reserved_bytes(), 0);
+}
+
+TEST(EnglishTokenizerTest, ReadsNothingPastTheValue) {
+ const size_t page_size = sysconf(_SC_PAGESIZE);
+ void* mapping = mmap(nullptr, page_size * 3, PROT_NONE, MAP_PRIVATE |
MAP_ANONYMOUS, -1, 0);
+ ASSERT_NE(mapping, MAP_FAILED);
+ auto* page = static_cast<char*>(mapping) + page_size;
+ ASSERT_EQ(mprotect(page, page_size, PROT_READ | PROT_WRITE), 0);
+ for (bool lowercase : {true, false}) {
+ EnglishTokenizer tokenizer(lowercase);
+ for (size_t size = 1; size <= 200; ++size) {
+ char* const value = page + page_size - size;
+ std::memset(value, 'K', size);
+ const std::vector<std::string> terms =
+ collect_terms(tokenizer, std::string_view(value, size));
+ ASSERT_EQ(terms.size(), (size + MAX_WORD_LEN - 1) / MAX_WORD_LEN);
+ EXPECT_EQ(terms[0][0], lowercase ? 'k' : 'K');
+ }
+ }
+ EXPECT_EQ(munmap(mapping, page_size * 3), 0);
+}
+
+TEST(EnglishTokenizerTest, KeepsTheStreamContract) {
+ for (bool lowercase : {true, false}) {
+ const TextAnalyzerPtr analyzer = english_analyzer(lowercase);
+ std::string many_batches;
+ for (int i = 0; i < 2000; ++i) {
+ many_batches += "Word" + std::to_string(i % 97) + " ";
+ }
+ expect_text_stream_contract([&] { return analyzer->create_stream(); },
+ {"", "Hello World", "a", std::string(300,
'Z'),
+ "中文 mixed ÄÖÜ 123", many_batches});
+ }
+}
+
+} // namespace
+} // namespace doris::segment_v2::inverted_index
diff --git a/be/test/util/simd/bits_test.cpp b/be/test/util/simd/bits_test.cpp
index 4034980baa7..8b54ee90cda 100644
--- a/be/test/util/simd/bits_test.cpp
+++ b/be/test/util/simd/bits_test.cpp
@@ -220,6 +220,26 @@ TEST(BitsTest, BytesMaskToBitsMask) {
EXPECT_EQ(full_mask, bits_mask_all());
}
+// Every branch of bytes32_mask_to_bits32_mask (AVX2, SSE2, NEON, scalar)
against the scalar rule:
+// bit i is set when byte i is 1.
+TEST(BitsTest, Bytes32MaskToBits32MaskSetsTheBitOfEveryOneByte) {
+ uint8_t data[32] = {};
+ for (size_t bit = 0; bit < 32; ++bit) {
+ std::ranges::fill(data, 0);
+ data[bit] = 1;
+ EXPECT_EQ(bytes32_mask_to_bits32_mask(data), uint32_t {1} << bit) <<
bit;
+ }
+ std::mt19937 random(20261103);
+ for (int round = 0; round < 10000; ++round) {
+ uint32_t expected = 0;
+ for (size_t i = 0; i < 32; ++i) {
+ data[i] = static_cast<uint8_t>(random() & 1);
+ expected |= static_cast<uint32_t>(data[i]) << i;
+ }
+ ASSERT_EQ(bytes32_mask_to_bits32_mask(data), expected);
+ }
+}
+
TEST(BitsTest, CountZeroNum) {
// Case 1: empty
const int8_t* empty = nullptr;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]