airborne12 commented on code in PR #68661:
URL: https://github.com/apache/doris/pull/68661#discussion_r4201824805
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +48,128 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+enum class PhraseMode { EXACT, PREFIX, EDGE };
+
+class StreamingPhraseMatcher {
+public:
+ StreamingPhraseMatcher(const std::vector<segment_v2::TermInfo>&
query_tokens, PhraseMode mode)
+ : _mode(mode),
+ _query_size(query_tokens.size()),
+ _last_word((_query_size - 1) / 64),
+ _last_bit(uint64_t {1} << ((_query_size - 1) % 64)),
+ _state(_last_word + 1, 0),
+ _first_term(query_tokens.front().get_single_term()),
+ _last_term(query_tokens.back().get_single_term()) {
+ for (size_t pos = 0; pos < _query_size; ++pos) {
+ if ((_mode == PhraseMode::PREFIX && pos == _query_size - 1) ||
+ (_mode == PhraseMode::EDGE && (pos == 0 || pos == _query_size
- 1))) {
+ continue;
+ }
+ auto& words = _exact_masks[query_tokens[pos].get_single_term()];
+ const size_t word = pos / 64;
+ const uint64_t bit = uint64_t {1} << (pos % 64);
+ if (!words.empty() && words.back().first == word) {
+ words.back().second |= bit;
+ } else {
+ words.emplace_back(word, bit);
+ }
+ }
+ }
+
+ void reset_row() { _has_tokens = false; }
+
+ bool feed(const std::string& term) {
+ if (!_has_tokens) {
+ std::fill(_state.begin(), _state.end(), 0);
+ _has_tokens = true;
+ }
+ const auto mask_it = _exact_masks.find(term);
+ const auto* mask_words = mask_it == _exact_masks.end() ? nullptr :
&mask_it->second;
+ size_t mask_index = 0;
+ const bool first_matches = _mode == PhraseMode::EDGE &&
+ (_query_size == 1 ? term.find(_first_term)
!= std::string::npos
+ :
term.ends_with(_first_term));
+ const bool last_matches =
+ (_mode == PhraseMode::PREFIX || (_mode == PhraseMode::EDGE &&
_query_size > 1)) &&
+ term.starts_with(_last_term);
+
+ uint64_t carry = 1;
+ for (size_t word = 0; word < _state.size(); ++word) {
+ uint64_t mask = 0;
+ if (mask_words && mask_index < mask_words->size() &&
+ (*mask_words)[mask_index].first == word) {
+ mask = (*mask_words)[mask_index++].second;
+ }
+ if (word == 0 && first_matches) {
+ mask |= 1;
+ }
+ if (word == _last_word && last_matches) {
+ mask |= _last_bit;
+ }
+ const uint64_t next_carry = _state[word] >> 63;
+ _state[word] = ((_state[word] << 1) | carry) & mask;
+ carry = next_carry;
+ }
+ return (_state[_last_word] & _last_bit) != 0;
+ }
+
+private:
+ PhraseMode _mode;
+ size_t _query_size;
+ size_t _last_word;
+ uint64_t _last_bit;
+ std::vector<uint64_t> _state;
+ std::string _first_term;
+ std::string _last_term;
+ std::unordered_map<std::string, std::vector<std::pair<size_t, uint64_t>>>
_exact_masks;
+ bool _has_tokens = false;
+};
+
+template <typename Callback>
+bool for_each_data_element_tokens(const FunctionMatchBase& function, const
std::string& column_name,
+ const InvertedIndexAnalyzerCtx* analyzer_ctx,
+ const ColumnString* string_col, size_t row,
+ const ColumnArray::Offsets64* array_offsets,
+ const ColumnUInt8::Container*
array_element_null_map,
+ Callback&& callback) {
+ const size_t begin = array_offsets ? (row == 0 ? 0 : (*array_offsets)[row
- 1]) : row;
+ const size_t end = array_offsets ? (*array_offsets)[row] : row + 1;
+ int32_t unused_array_offset = 0;
+ for (size_t element = begin; element < end; ++element) {
+ if (array_element_null_map && (*array_element_null_map)[element]) {
+ continue;
+ }
+ auto tokens = function.analyse_data_token(column_name, analyzer_ctx,
string_col, element,
+ nullptr,
unused_array_offset);
+ if (tokens.empty()) {
+ continue;
+ }
+ if (callback(tokens)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool match_phrase_data_tokens(const FunctionMatchBase& function, const
std::string& column_name,
+ const InvertedIndexAnalyzerCtx* analyzer_ctx,
+ const ColumnString* string_col, size_t row,
+ const ColumnArray::Offsets64* array_offsets,
+ const ColumnUInt8::Container*
array_element_null_map,
+ StreamingPhraseMatcher& matcher) {
+ matcher.reset_row();
+ return for_each_data_element_tokens(function, column_name, analyzer_ctx,
string_col, row,
+ array_offsets, array_element_null_map,
+ [&](const
std::vector<segment_v2::TermInfo>& tokens) {
+ for (const auto& token : tokens) {
+ if
(matcher.feed(token.get_single_term())) {
Review Comment:
Fixed in `94238af417b5fb964a68296075ea8dc19c7d89a6`. The new
`FunctionMatchTest.array_phrase_respects_analyzer_positions` reproduced the
false positive on the previous head (result 1 instead of 0) with `char_group`
and `word_delimiter(preserve_original)`. The matcher now combines tokens at the
same analyzer position and advances once per position. The reported phrase
misses, while `foo bar baz` still matches. The MATCH suite passes 37/37 and the
BE Release build passes.
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +48,128 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+enum class PhraseMode { EXACT, PREFIX, EDGE };
+
+class StreamingPhraseMatcher {
+public:
+ StreamingPhraseMatcher(const std::vector<segment_v2::TermInfo>&
query_tokens, PhraseMode mode)
+ : _mode(mode),
+ _query_size(query_tokens.size()),
+ _last_word((_query_size - 1) / 64),
+ _last_bit(uint64_t {1} << ((_query_size - 1) % 64)),
+ _state(_last_word + 1, 0),
+ _first_term(query_tokens.front().get_single_term()),
+ _last_term(query_tokens.back().get_single_term()) {
+ for (size_t pos = 0; pos < _query_size; ++pos) {
+ if ((_mode == PhraseMode::PREFIX && pos == _query_size - 1) ||
+ (_mode == PhraseMode::EDGE && (pos == 0 || pos == _query_size
- 1))) {
+ continue;
+ }
+ auto& words = _exact_masks[query_tokens[pos].get_single_term()];
+ const size_t word = pos / 64;
+ const uint64_t bit = uint64_t {1} << (pos % 64);
+ if (!words.empty() && words.back().first == word) {
+ words.back().second |= bit;
+ } else {
+ words.emplace_back(word, bit);
+ }
+ }
+ }
+
+ void reset_row() { _has_tokens = false; }
+
+ bool feed(const std::string& term) {
+ if (!_has_tokens) {
+ std::fill(_state.begin(), _state.end(), 0);
+ _has_tokens = true;
+ }
+ const auto mask_it = _exact_masks.find(term);
+ const auto* mask_words = mask_it == _exact_masks.end() ? nullptr :
&mask_it->second;
+ size_t mask_index = 0;
+ const bool first_matches = _mode == PhraseMode::EDGE &&
+ (_query_size == 1 ? term.find(_first_term)
!= std::string::npos
+ :
term.ends_with(_first_term));
+ const bool last_matches =
+ (_mode == PhraseMode::PREFIX || (_mode == PhraseMode::EDGE &&
_query_size > 1)) &&
+ term.starts_with(_last_term);
+
+ uint64_t carry = 1;
+ for (size_t word = 0; word < _state.size(); ++word) {
Review Comment:
Fixed in `94238af417b5fb964a68296075ea8dc19c7d89a6`. The matcher now skips
bitset work for positions with no matching query mask and scans only active
words plus the next word when a position can advance.
`FunctionMatchTest.long_unrelated_phrase_miss` covers a 1,000-term query across
unrelated, matching, and unrelated rows. The MATCH suite passes 37/37 and the
BE Release build passes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
