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 6979f7fa1e7 [improvement](be) Skip dictionary entry bodies of
non-matching terms in SNII term expansion (#69600)
6979f7fa1e7 is described below
commit 6979f7fa1e77d38099508409ac1c25a591155143
Author: Jack <[email protected]>
AuthorDate: Mon Oct 26 18:11:50 2026 +0800
[improvement](be) Skip dictionary entry bodies of non-matching terms in
SNII term expansion (#69600)
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: MATCH_REGEXP, wildcard, suffix and contains patterns
without a literal
prefix make SniiIndexSource::expand_terms enumerate the whole dictionary
of every segment.
LogicalIndexReader::visit_prefix_terms always passed an empty accept_key
to
DictBlockReader::visit_prefix_range, so the body of every dictionary
entry was decoded
(decode_dict_entry_rest) and the caller then rejected almost all of them
with the
required-text test and the pattern match. DictBlockReader already
supports a key-only
accept_key that skips the body of a rejected term.
visit_prefix_terms now takes an optional accept_key, and expand_terms
passes its term test
(required text, then pattern match) as that predicate. Terms are tested
exactly as before, only
earlier, and the visitor still sees only accepted terms, so
max_expansions and early stop count
the same terms. Other callers keep the default (accept all).
Measured on 99M AgentLogs rows (722 segments, tenant and status filters,
token regexp
'transi.*', hot median): SNII 6028 ms -> 945 ms, V3 unchanged at about
590 ms. Result counts
are identical to V3 for regexp, leading-wildcard regexp and
phrase-prefix queries. Patterns with
a literal prefix (for example '^transi.*') seek into the dictionary and
are unchanged: SNII and
V3 are level at about 100 ms before and after. Gdb sampling showed 58%
of the time in
decode_dict_entry_rest before and about 5% after.
---
.../inverted/snii/reader/logical_index_reader.cpp | 12 ++--
.../inverted/snii/reader/logical_index_reader.h | 9 ++-
.../inverted/snii/reader/snii_index_source.cpp | 17 +++---
.../index/inverted/snii/snii_query_test.cpp | 71 ++++++++++++++++++++++
4 files changed, 94 insertions(+), 15 deletions(-)
diff --git a/be/src/storage/index/inverted/snii/reader/logical_index_reader.cpp
b/be/src/storage/index/inverted/snii/reader/logical_index_reader.cpp
index e066a2aa707..d2919c6b19b 100644
--- a/be/src/storage/index/inverted/snii/reader/logical_index_reader.cpp
+++ b/be/src/storage/index/inverted/snii/reader/logical_index_reader.cpp
@@ -1007,9 +1007,9 @@ Status
LogicalIndexReader::dict_block_scan_memory(uint32_t ordinal,
return Status::OK();
}
-Status LogicalIndexReader::visit_prefix_terms(std::string_view prefix,
- const PrefixHitVisitor& visitor,
- DictBlockCache* cache) const {
+Status LogicalIndexReader::visit_prefix_terms(
+ std::string_view prefix, const PrefixHitVisitor& visitor,
DictBlockCache* cache,
+ const std::function<bool(std::string_view term)>& accept_key) const {
if (!visitor) {
return Status::Error<ErrorCode::INVALID_ARGUMENT, false>(
"logical_index: null prefix visitor");
@@ -1039,12 +1039,12 @@ Status
LogicalIndexReader::visit_prefix_terms(std::string_view prefix,
// Stream this block's prefix range: anchor-jump past pre-prefix
segments,
// decode only the bodies we keep, and stop at the first term past the
// range (decode_all materialized every entry of every scanned block).
- // The visitor still owns final term acceptance, so results are
identical;
- // `br`/`pin` stay alive across this synchronous call.
+ // `accept_key` rejects a term before its body is decoded; the visitor
sees only accepted
+ // terms. `br`/`pin` stay alive across this synchronous call.
bool prefix_exhausted = false;
bool visitor_stopped = false;
RETURN_IF_ERROR(br->visit_prefix_range(
- prefix, /*accept_key=*/ {},
+ prefix, accept_key,
[&](DictEntry&& e, bool* stop) -> Status {
PrefixHit hit;
hit.term = e.term;
diff --git a/be/src/storage/index/inverted/snii/reader/logical_index_reader.h
b/be/src/storage/index/inverted/snii/reader/logical_index_reader.h
index eed5a05c7e1..bb7a99a6d2a 100644
--- a/be/src/storage/index/inverted/snii/reader/logical_index_reader.h
+++ b/be/src/storage/index/inverted/snii/reader/logical_index_reader.h
@@ -194,8 +194,13 @@ public:
// the term-anchor layout was built for (MATCH_PHRASE_PREFIX / prefix /
range
// queries). The visitor form avoids materializing all hits when callers
only
// need a bounded expansion.
- Status visit_prefix_terms(std::string_view prefix, const PrefixHitVisitor&
visitor,
- DictBlockCache* cache = nullptr) const;
+ // `accept_key`, when set, is a key-only predicate: a term it rejects is
skipped before its
+ // dictionary entry body is decoded, so a caller that keeps few of the
terms (a regexp or
+ // wildcard expansion over the whole dictionary) does not pay a body
decode for every term.
+ Status visit_prefix_terms(
+ std::string_view prefix, const PrefixHitVisitor& visitor,
+ DictBlockCache* cache = nullptr,
+ const std::function<bool(std::string_view term)>& accept_key = {})
const;
Status visit_term_range(std::string_view lower_inclusive,
std::optional<std::string_view> upper_exclusive,
const PrefixHitVisitor& visitor, DictBlockCache*
cache = nullptr) const;
diff --git a/be/src/storage/index/inverted/snii/reader/snii_index_source.cpp
b/be/src/storage/index/inverted/snii/reader/snii_index_source.cpp
index ef219a734a2..c3131c987e2 100644
--- a/be/src/storage/index/inverted/snii/reader/snii_index_source.cpp
+++ b/be/src/storage/index/inverted/snii/reader/snii_index_source.cpp
@@ -265,15 +265,17 @@ Status
SniiIndexSource::expand_terms(index_query::TermPattern& pattern, int32_t
}
RETURN_IF_ERROR(_check_enumeration(pattern.enumeration_prefix()));
const std::string& required = pattern.required_text();
+ // The term test is key-only, so it runs before a dictionary entry body is
decoded: a regexp or
+ // wildcard expansion enumerates the whole dictionary and keeps almost
none of it.
+ const auto accept_key = [&](std::string_view term) {
+ if (!required.empty() && term.find(required) ==
std::string_view::npos) {
+ return false;
+ }
+ return pattern.matches(term);
+ };
return _idx.visit_prefix_terms(
pattern.enumeration_prefix(),
[&](LogicalIndexReader::PrefixHit&& hit, bool* stop) -> Status {
- if (!required.empty() && hit.term.find(required) ==
std::string::npos) {
- return Status::OK();
- }
- if (!pattern.matches(hit.term)) {
- return Status::OK();
- }
// The dictionary answered the term here, so its open needs no
lookup.
_terms[hit.term] = {.hit = {.found = true,
.entry = std::move(hit.entry),
@@ -283,7 +285,8 @@ Status
SniiIndexSource::expand_terms(index_query::TermPattern& pattern, int32_t
out->push_back(std::move(hit.term));
*stop = max_expansions > 0 && out->size() ==
static_cast<size_t>(max_expansions);
return Status::OK();
- });
+ },
+ /*cache=*/nullptr, accept_key);
}
// A prefix reaching the marker enumerates internal terms; an empty one does
when the dictionary
diff --git a/be/test/storage/index/inverted/snii/snii_query_test.cpp
b/be/test/storage/index/inverted/snii/snii_query_test.cpp
index f2922cfcee7..a69ca4457a6 100644
--- a/be/test/storage/index/inverted/snii/snii_query_test.cpp
+++ b/be/test/storage/index/inverted/snii/snii_query_test.cpp
@@ -21,6 +21,7 @@
#include <atomic>
#include <cstdlib>
#include <cstring>
+#include <functional>
#include <iostream>
#include <memory>
#include <mutex>
@@ -37,6 +38,7 @@
#include "storage/index/inverted/snii/encoding/byte_sink.h"
#include "storage/index/inverted/snii/encoding/byte_source.h"
#include "storage/index/inverted/snii/encoding/pfor.h"
+#include "storage/index/inverted/snii/format/dict_entry.h"
#include "storage/index/inverted/snii/format/format_constants.h"
#include "storage/index/inverted/snii/format/prx_pod.h"
#include "storage/index/inverted/snii/format/tail_pointer.h"
@@ -44,6 +46,7 @@
#include "storage/index/inverted/snii/io/file_writer.h"
#include "storage/index/inverted/snii/reader/dict_block_cache.h"
#include "storage/index/inverted/snii/reader/logical_index_reader.h"
+#include "storage/index/inverted/snii/reader/snii_index_source.h"
#include "storage/index/inverted/snii/reader/snii_segment_reader.h"
#include "storage/index/inverted/snii/snii_query_oracle.h"
#include "storage/index/inverted/snii/snii_query_test_util.h"
@@ -797,6 +800,74 @@ TEST(SniiRegexpQueryTest,
AnchoredPrefixEnumeratesSingleTerm) {
EXPECT_EQ(docids, all_docids_0_to(9000));
}
+// A term test handed to visit_prefix_terms runs on the key alone: the visitor
sees exactly the
+// accepted terms, and the dictionary decodes only their bodies.
+TEST(SniiRegexpQueryTest, AcceptKeySkipsBodiesOfRejectedTerms) {
+ MemoryFile file;
+ reader::SniiSegmentReader segment_reader;
+ reader::LogicalIndexReader index_reader;
+ assert_ok(build_reader(&file, &segment_reader, &index_reader));
+
+ auto visit = [&](const std::function<bool(std::string_view)>& accept_key,
+ std::vector<std::string>* terms, size_t stop_after = 0) {
+ terms->clear();
+ format::reset_dict_entry_counters();
+ assert_ok(index_reader.visit_prefix_terms(
+ "",
+ [&](reader::LogicalIndexReader::PrefixHit&& hit, bool* stop) {
+ terms->push_back(hit.term);
+ *stop = stop_after > 0 && terms->size() == stop_after;
+ return Status::OK();
+ },
+ /*cache=*/nullptr, accept_key));
+ return format::dict_entry_body_decode_count();
+ };
+
+ std::vector<std::string> all;
+ EXPECT_EQ(visit({}, &all), 11U);
+ EXPECT_EQ(all.size(), 11U);
+
+ const auto starts_with_ord = [](std::string_view term) { return
term.starts_with("ord"); };
+ std::vector<std::string> accepted;
+ EXPECT_EQ(visit(starts_with_ord, &accepted), 2U);
+ EXPECT_EQ(accepted, (std::vector<std::string> {"order", "ordinal"}));
+
+ const auto none = [](std::string_view) { return false; };
+ std::vector<std::string> rejected;
+ EXPECT_EQ(visit(none, &rejected), 0U);
+ EXPECT_TRUE(rejected.empty());
+
+ // The visitor's stop counts accepted terms only.
+ std::vector<std::string> first;
+ EXPECT_EQ(visit(starts_with_ord, &first, /*stop_after=*/1), 1U);
+ EXPECT_EQ(first, (std::vector<std::string> {"order"}));
+}
+
+// A regexp without a literal prefix enumerates the whole dictionary, but only
the terms it
+// matches pay for a body decode.
+TEST(SniiRegexpQueryTest, UnanchoredRegexpDecodesOnlyMatchedBodies) {
+ MemoryFile file;
+ reader::SniiSegmentReader segment_reader;
+ reader::LogicalIndexReader index_reader;
+ assert_ok(build_reader(&file, &segment_reader, &index_reader));
+
+ index_query::TermPattern pattern;
+
assert_ok(index_query::TermPattern::create(index_query::TermPatternKind::kRegexp,
"rdin",
+ &pattern));
+ ASSERT_EQ(pattern.enumeration_prefix(), "");
+
+ reader::SniiIndexSource source(index_reader);
+ std::vector<std::string> terms;
+ format::reset_dict_entry_counters();
+ assert_ok(source.expand_terms(pattern, 0, &terms));
+ EXPECT_EQ(terms, (std::vector<std::string> {"ordinal"}));
+ EXPECT_EQ(format::dict_entry_body_decode_count(), 1U);
+
+ std::vector<uint32_t> docids;
+ assert_ok(regexp_query(index_reader, "rdin", &docids));
+ EXPECT_EQ(docids, all_docids_0_to(9000));
+}
+
TEST(SniiPhraseQueryTest, MultiTailPhrasePrefixFiltersTailPrxByExpectedDocs) {
MemoryFile file;
reader::SniiSegmentReader segment_reader;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
