airborne12 commented on code in PR #68661:
URL: https://github.com/apache/doris/pull/68661#discussion_r4201463064
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +44,165 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+bool match_phrase_tokens(const std::vector<segment_v2::TermInfo>& data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ bool matched = false;
+ auto data_it = data_tokens.begin();
+ while (data_it != data_tokens.end()) {
+ data_it = std::find_if(data_it, data_tokens.end(), [&](const
segment_v2::TermInfo& info) {
+ return info.get_single_term() == query_tokens[0].get_single_term();
+ });
+ if (data_it != data_tokens.end()) {
+ matched = true;
+ auto data_it_next = ++data_it;
+ auto query_it = query_tokens.begin() + 1;
+ while (query_it != query_tokens.end()) {
+ if (data_it_next == data_tokens.end() ||
+ data_it_next->get_single_term() !=
query_it->get_single_term()) {
+ matched = false;
+ break;
+ }
+ query_it++;
+ data_it_next++;
+ }
+
+ if (matched) {
+ break;
+ }
+ }
+ }
+
+ return matched;
+}
+
+bool match_phrase_prefix_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ if (data_tokens[j].get_single_term() ==
query_tokens[0].get_single_term() ||
+ query_tokens.size() == 1) {
+ bool match = true;
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool match_phrase_edge_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ bool match = true;
+ if (query_tokens.size() == 1) {
+ if
(data_tokens[j].get_single_term().find(query_tokens[0].get_single_term()) ==
+ std::string::npos) {
+ match = false;
+ }
+ } else {
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == 0) {
+ if (!data_token.ends_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ return 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 (callback(tokens)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+using PhraseMatcher = bool (*)(const std::vector<segment_v2::TermInfo>&,
+ const std::vector<segment_v2::TermInfo>&);
+
+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,
+ const std::vector<segment_v2::TermInfo>&
query_tokens,
+ PhraseMatcher matcher) {
+ std::vector<segment_v2::TermInfo> window;
+ window.reserve(query_tokens.size());
+ return for_each_data_element_tokens(
+ function, column_name, analyzer_ctx, string_col, row,
array_offsets,
+ array_element_null_map, [&](std::vector<segment_v2::TermInfo>&
tokens) {
+ for (auto& token : tokens) {
+ if (window.size() == query_tokens.size()) {
+ window.erase(window.begin());
+ }
+ window.emplace_back(std::move(token));
+ if (window.size() == query_tokens.size() &&
matcher(window, query_tokens)) {
+ return true;
Review Comment:
The repeated-token case reproduced the P1: on the prior head, 10,000 `alpha`
data tokens with a query of 999 `alpha` tokens followed by `beta` did not
finish within 12 seconds. Commit `46a454423312` replaces the rescanned phrase
window with incremental bitset state. The same
`FunctionMatchTest.long_repeated_phrase_miss` case now passes in 26 ms;
`FunctionMatchTest.*` passes 35/35 and the BE build passes.
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +44,165 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+bool match_phrase_tokens(const std::vector<segment_v2::TermInfo>& data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ bool matched = false;
+ auto data_it = data_tokens.begin();
+ while (data_it != data_tokens.end()) {
+ data_it = std::find_if(data_it, data_tokens.end(), [&](const
segment_v2::TermInfo& info) {
+ return info.get_single_term() == query_tokens[0].get_single_term();
+ });
+ if (data_it != data_tokens.end()) {
+ matched = true;
+ auto data_it_next = ++data_it;
+ auto query_it = query_tokens.begin() + 1;
+ while (query_it != query_tokens.end()) {
+ if (data_it_next == data_tokens.end() ||
+ data_it_next->get_single_term() !=
query_it->get_single_term()) {
+ matched = false;
+ break;
+ }
+ query_it++;
+ data_it_next++;
+ }
+
+ if (matched) {
+ break;
+ }
+ }
+ }
+
+ return matched;
+}
+
+bool match_phrase_prefix_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ if (data_tokens[j].get_single_term() ==
query_tokens[0].get_single_term() ||
+ query_tokens.size() == 1) {
+ bool match = true;
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool match_phrase_edge_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ bool match = true;
+ if (query_tokens.size() == 1) {
+ if
(data_tokens[j].get_single_term().find(query_tokens[0].get_single_term()) ==
+ std::string::npos) {
+ match = false;
+ }
+ } else {
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == 0) {
+ if (!data_token.ends_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ return 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 (callback(tokens)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+using PhraseMatcher = bool (*)(const std::vector<segment_v2::TermInfo>&,
+ const std::vector<segment_v2::TermInfo>&);
+
+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,
+ const std::vector<segment_v2::TermInfo>&
query_tokens,
+ PhraseMatcher matcher) {
+ std::vector<segment_v2::TermInfo> window;
+ window.reserve(query_tokens.size());
+ return for_each_data_element_tokens(
+ function, column_name, analyzer_ctx, string_col, row,
array_offsets,
+ array_element_null_map, [&](std::vector<segment_v2::TermInfo>&
tokens) {
+ for (auto& token : tokens) {
+ if (window.size() == query_tokens.size()) {
+ window.erase(window.begin());
+ }
Review Comment:
Commit `46a454423312` removes the vector window and `erase(begin())`. Each
data token now advances a fixed-size bitset state without moving `TermInfo`
values. The 65-term `FunctionMatchTest.long_phrase_modes_cross_bitset_word`
case passes for phrase, prefix, and edge matching; the full MATCH suite passes
35/35.
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +44,165 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+bool match_phrase_tokens(const std::vector<segment_v2::TermInfo>& data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ bool matched = false;
+ auto data_it = data_tokens.begin();
+ while (data_it != data_tokens.end()) {
+ data_it = std::find_if(data_it, data_tokens.end(), [&](const
segment_v2::TermInfo& info) {
+ return info.get_single_term() == query_tokens[0].get_single_term();
+ });
+ if (data_it != data_tokens.end()) {
+ matched = true;
+ auto data_it_next = ++data_it;
+ auto query_it = query_tokens.begin() + 1;
+ while (query_it != query_tokens.end()) {
+ if (data_it_next == data_tokens.end() ||
+ data_it_next->get_single_term() !=
query_it->get_single_term()) {
+ matched = false;
+ break;
+ }
+ query_it++;
+ data_it_next++;
+ }
+
+ if (matched) {
+ break;
+ }
+ }
+ }
+
+ return matched;
+}
+
+bool match_phrase_prefix_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ if (data_tokens[j].get_single_term() ==
query_tokens[0].get_single_term() ||
+ query_tokens.size() == 1) {
+ bool match = true;
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool match_phrase_edge_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ bool match = true;
+ if (query_tokens.size() == 1) {
+ if
(data_tokens[j].get_single_term().find(query_tokens[0].get_single_term()) ==
+ std::string::npos) {
+ match = false;
+ }
+ } else {
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == 0) {
+ if (!data_token.ends_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ return 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 (callback(tokens)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+using PhraseMatcher = bool (*)(const std::vector<segment_v2::TermInfo>&,
+ const std::vector<segment_v2::TermInfo>&);
+
+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,
+ const std::vector<segment_v2::TermInfo>&
query_tokens,
+ PhraseMatcher matcher) {
+ std::vector<segment_v2::TermInfo> window;
+ window.reserve(query_tokens.size());
+ return for_each_data_element_tokens(
Review Comment:
Commit `46a454423312` constructs the phrase matcher once per query and
reuses its state across rows. It resets state only when a row actually yields a
token, so empty array rows no longer reserve or free a query-sized window. The
MATCH suite passes 35/35 and the BE build passes.
##########
be/src/exprs/function/match.cpp:
##########
@@ -44,6 +44,165 @@ const InvertedIndexAnalyzerCtx*
get_match_analyzer_ctx(FunctionContext* context)
return analyzer_ctx;
}
+bool match_phrase_tokens(const std::vector<segment_v2::TermInfo>& data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ bool matched = false;
+ auto data_it = data_tokens.begin();
+ while (data_it != data_tokens.end()) {
+ data_it = std::find_if(data_it, data_tokens.end(), [&](const
segment_v2::TermInfo& info) {
+ return info.get_single_term() == query_tokens[0].get_single_term();
+ });
+ if (data_it != data_tokens.end()) {
+ matched = true;
+ auto data_it_next = ++data_it;
+ auto query_it = query_tokens.begin() + 1;
+ while (query_it != query_tokens.end()) {
+ if (data_it_next == data_tokens.end() ||
+ data_it_next->get_single_term() !=
query_it->get_single_term()) {
+ matched = false;
+ break;
+ }
+ query_it++;
+ data_it_next++;
+ }
+
+ if (matched) {
+ break;
+ }
+ }
+ }
+
+ return matched;
+}
+
+bool match_phrase_prefix_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ if (data_tokens[j].get_single_term() ==
query_tokens[0].get_single_term() ||
+ query_tokens.size() == 1) {
+ bool match = true;
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+bool match_phrase_edge_tokens(const std::vector<segment_v2::TermInfo>&
data_tokens,
+ const std::vector<segment_v2::TermInfo>&
query_tokens) {
+ if (data_tokens.size() < query_tokens.size()) {
+ return false;
+ }
+ const auto dis_count = data_tokens.size() - query_tokens.size();
+
+ for (size_t j = 0; j < dis_count + 1; j++) {
+ bool match = true;
+ if (query_tokens.size() == 1) {
+ if
(data_tokens[j].get_single_term().find(query_tokens[0].get_single_term()) ==
+ std::string::npos) {
+ match = false;
+ }
+ } else {
+ for (size_t k = 0; k < query_tokens.size(); k++) {
+ const std::string& data_token = data_tokens[j +
k].get_single_term();
+ const std::string& query_token =
query_tokens[k].get_single_term();
+ if (k == 0) {
+ if (!data_token.ends_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else if (k == query_tokens.size() - 1) {
+ if (!data_token.starts_with(query_token)) {
+ match = false;
+ break;
+ }
+ } else {
+ if (data_token != query_token) {
+ match = false;
+ break;
+ }
+ }
+ }
+ }
+ if (match) {
+ return true;
+ }
+ }
+ return 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 (callback(tokens)) {
+ return true;
Review Comment:
Commit `46a454423312` skips elements whose analyzer yields no tokens before
invoking MATCH_ANY or MATCH_ALL membership logic. Keyword empty strings still
yield an empty-string token and remain matchable; the updated array test
asserts this behavior. The MATCH suite passes 35/35.
--
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]
