Skip to content

Commit 7bff7b8

Browse files
airborne12claude
andcommitted
[fix](inverted index) Keep the phrase prefix expansion tablet-wide and bounded
### What problem does this PR solve? Issue Number: None Related PR: #69698 Problem Summary: Two findings of the review of the phrase prefix scoring change. 1. The terms a prefix expands to were capped per segment by inverted_index_max_expansions, and a term's document frequency was counted only in the segments that selected it. With a limit of 1, segment A holding "apple rose" selects rose, segment B holding "apple red" and "apple rose" selects red; the tablet union holds both, but rose was counted in A alone (1 instead of 2), which inflated its idf and every matching score. The tablet now keeps the `limit` smallest terms of the prefix over all segments (PrefixExpansionSet), as an index-wide expansion of Lucene does. A term of that set is among the smallest `limit` of every segment holding it, so every one of those segments expanded to it and counted its documents, whatever the order of the segments. In the example only red is scored. 2. The expansion terms are kept for the whole scan and copied to every scanner, without charging the query memory tracker, and a session limit of 0 could keep the whole vocabulary starting with the prefix. The kept terms are now at most the limit per prefix, and a session limit of 0 scores the default 50 terms: the sum of thousands of idfs ranks nothing. The document frequency map still holds the terms each segment selected, at most the limit per segment. ### Release note None ### Check List (For Author) - Test: Unit Test, Regression test - PrefixExpansionSetTest keeps the smallest terms in either segment order; the collector keeps the default limit under a session limit of 0. - The regression suite adds the two-segment case with a limit of 1: the scores equal the idf of apple and red (1.1144), and 1.5844 with rose under a limit of 50; checked by hand against the BM25 formula. - Behavior changed: No (corrects the previous change before release) - Does this need documentation: No Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent e3dfddb commit 7bff7b8

8 files changed

Lines changed: 158 additions & 24 deletions

File tree

‎be/src/storage/index/inverted/reader/collection_statistics.cpp‎

Lines changed: 15 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -120,8 +120,7 @@ void add_term_doc_frequency(
120120
}
121121

122122
Status segment_scoring_terms(index_query::IndexSource& source, const CollectInfo& collect_info,
123-
std::unordered_map<std::wstring, std::set<std::wstring>>* expansions,
124-
std::vector<std::string>* terms) {
123+
FieldPrefixExpansions* expansions, std::vector<std::string>* terms) {
125124
DORIS_CHECK(expansions != nullptr);
126125
DORIS_CHECK(terms != nullptr);
127126
*terms = collect_info.unique_terms;
@@ -136,8 +135,12 @@ Status segment_scoring_terms(index_query::IndexSource& source, const CollectInfo
136135
index_query::expansion_limit(index_query::TermPatternKind::kPrefix,
137136
scoring_prefix.max_expansions),
138137
&expanded));
139-
auto& prefix_terms = (*expansions)[segment_v2::inverted_index::StringHelper::to_wstring(
140-
scoring_prefix.prefix)];
138+
auto& prefix_terms =
139+
expansions
140+
->try_emplace(segment_v2::inverted_index::StringHelper::to_wstring(
141+
scoring_prefix.prefix),
142+
scoring_prefix.max_expansions)
143+
.first->second;
141144
for (auto& term : expanded) {
142145
prefix_terms.insert(segment_v2::inverted_index::StringHelper::to_wstring(term));
143146
if (listed.insert(term).second) {
@@ -742,8 +745,13 @@ void CollectionStatistics::commit_snii_scoring_segment(
742745
}
743746
}
744747
for (const auto& [field_name, prefixes] : segment_accumulator.prefix_expansions) {
745-
for (const auto& [prefix, terms] : prefixes) {
746-
_prefix_expansions[field_name][prefix].insert(terms.begin(), terms.end());
748+
for (const auto& [prefix, expansion] : prefixes) {
749+
auto& merged = _prefix_expansions[field_name]
750+
.try_emplace(prefix, expansion.limit())
751+
.first->second;
752+
for (const auto& term : expansion.terms()) {
753+
merged.insert(term);
754+
}
747755
}
748756
}
749757
_total_num_docs += segment_accumulator.doc_count;
@@ -859,7 +867,7 @@ std::vector<std::wstring> CollectionStatistics::get_prefix_expansions(
859867
// A merge-on-write scan hides rows: a term whose documents are all hidden was expanded in
860868
// its segment but has no document frequency left, and its idf would be that of an absent term.
861869
std::vector<std::wstring> terms;
862-
for (const auto& term : expansions->second) {
870+
for (const auto& term : expansions->second.terms()) {
863871
if (get_term_doc_freq_by_col(lucene_col_name, term) > 0) {
864872
terms.push_back(term);
865873
}

‎be/src/storage/index/inverted/reader/collection_statistics.h‎

Lines changed: 36 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919
#include <condition_variable>
2020
#include <cstdint>
2121
#include <functional>
22+
#include <iterator>
2223
#include <mutex>
2324
#include <optional>
2425
#include <set>
@@ -82,6 +83,37 @@ struct MowHiddenRows {
8283
bool use_page_cache = true;
8384
};
8485

86+
// The `limit` smallest terms, in dictionary order, that a prefix expanded to in the segments seen
87+
// so far: the terms an index-wide expansion of Lucene would take. A term only enters or stays
88+
// while fewer than `limit` smaller terms are known, and one dropped never returns, whatever
89+
// order the segments come in.
90+
//
91+
// That is what keeps the document frequencies whole. A term of the final set has fewer than
92+
// `limit` smaller terms in every segment holding it, so each of those segments expanded to it
93+
// and counted its documents. With a limit of 1, segment A holding {rose} and segment B holding
94+
// {red, rose} leave {red}: B's expansion is red alone, but rose is not scored, so its document
95+
// frequency, which only A counted, is not used.
96+
class PrefixExpansionSet {
97+
public:
98+
explicit PrefixExpansionSet(int32_t limit) : _limit(limit) { DORIS_CHECK_GT(limit, 0); }
99+
100+
void insert(const std::wstring& term) {
101+
_terms.insert(term);
102+
if (_terms.size() > static_cast<size_t>(_limit)) {
103+
_terms.erase(std::prev(_terms.end()));
104+
}
105+
}
106+
107+
int32_t limit() const { return _limit; }
108+
const std::set<std::wstring>& terms() const { return _terms; }
109+
110+
private:
111+
int32_t _limit;
112+
std::set<std::wstring> _terms;
113+
};
114+
// The terms each prefix expanded to, by prefix.
115+
using FieldPrefixExpansions = std::unordered_map<std::wstring, PrefixExpansionSet>;
116+
85117
class CollectionStatistics {
86118
public:
87119
explicit CollectionStatistics(PredicateCollectorPtr search_collector = nullptr)
@@ -119,9 +151,7 @@ class CollectionStatistics {
119151

120152
private:
121153
// The terms each collected prefix expanded to, by field and prefix.
122-
using PrefixExpansions =
123-
std::unordered_map<std::wstring,
124-
std::unordered_map<std::wstring, std::set<std::wstring>>>;
154+
using PrefixExpansions = std::unordered_map<std::wstring, FieldPrefixExpansions>;
125155

126156
struct SniiScoringSegmentAccumulator {
127157
uint64_t doc_count = 0;
@@ -247,13 +277,13 @@ Status exclude_hidden_docs(std::span<const uint32_t> hidden_docs, const roaring:
247277
// The terms whose document frequencies a segment adds for `collect_info`: its scoring terms, then
248278
// each term its prefixes expand to in `source`, so that a phrase prefix is scored on the same
249279
// tablet statistics as the other terms. A term met twice is listed once, as its documents count
250-
// once. The expansions of each prefix, of this segment alone, are added to `expansions`.
280+
// once. The terms each prefix expands to in this segment are added to `expansions`, which keeps
281+
// the smallest ones of the segments seen (PrefixExpansionSet).
251282
//
252283
// Example: "red r" collects red and, in a segment holding red, rose and run, the terms red (already
253284
// listed), rose and run, and records {red, rose, run} for the prefix "r".
254285
Status segment_scoring_terms(index_query::IndexSource& source, const CollectInfo& collect_info,
255-
std::unordered_map<std::wstring, std::set<std::wstring>>* expansions,
256-
std::vector<std::string>* terms);
286+
FieldPrefixExpansions* expansions, std::vector<std::string>* terms);
257287

258288
// Takes from a term's document frequency the documents of `hidden_docs` that hold it.
259289
Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_view term,

‎be/src/storage/index/inverted/reader/predicate_collector.cpp‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -399,7 +399,13 @@ Status MatchPredicateCollector::collect(RuntimeState* state, const TabletSchemaS
399399
RETURN_IF_ERROR(append_scoring_leaf(&iter->second, term_infos));
400400
}
401401
if (scoring_prefix.has_value()) {
402-
append_scoring_prefix(&iter->second, *scoring_prefix, index_query::max_expansions(state));
402+
// The terms of a prefix are kept for the whole scan and copied to every scanner, so their
403+
// number is bounded. Under a session limit of 0, which expands a prefix to every term,
404+
// "quick b" would keep the whole vocabulary starting with b, and a sum of thousands of
405+
// idfs ranks nothing; the default limit scores it instead.
406+
const int32_t session_limit = index_query::max_expansions(state);
407+
append_scoring_prefix(&iter->second, *scoring_prefix,
408+
session_limit > 0 ? session_limit : kDefaultScoringExpansions);
403409
}
404410

405411
return Status::OK();

‎be/src/storage/index/inverted/reader/predicate_collector.h‎

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -56,11 +56,14 @@ struct LogicalScoringLeaf {
5656
std::vector<LogicalScoringClause> clauses;
5757
};
5858

59-
// The last term of a scored phrase prefix, whose idf is the sum of the idfs of the terms it
60-
// expands to, as many as `max_expansions` in each segment.
59+
// The number of terms a scored phrase prefix expands to when the session sets no limit.
60+
inline constexpr int32_t kDefaultScoringExpansions = 50;
61+
62+
// The last term of a scored phrase prefix, whose idf is the sum of the idfs of the smallest
63+
// `max_expansions` terms it expands to over the tablet, which is positive.
6164
struct LogicalScoringPrefix {
6265
std::string prefix;
63-
int32_t max_expansions = 0;
66+
int32_t max_expansions = kDefaultScoringExpansions;
6467
};
6568

6669
struct CollectInfo {

‎be/test/storage/index/inverted/query/engine/phrase_prefix_query_test.cpp‎

Lines changed: 11 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -405,10 +405,14 @@ TEST_F(PhrasePrefixQueryV2Test, prefix_expansions_add_their_idf_to_the_score) {
405405
stats._term_doc_freqs[field][StringHelper::to_wstring("quick")] = 100;
406406
stats._term_doc_freqs[field][StringHelper::to_wstring("brother")] = 3;
407407
stats._term_doc_freqs[field][StringHelper::to_wstring("brown")] = 400;
408-
stats._prefix_expansions[field][StringHelper::to_wstring("bro")] = {
409-
StringHelper::to_wstring("brother"), StringHelper::to_wstring("brown")};
410-
stats._prefix_expansions[field][StringHelper::to_wstring("brot")] = {
411-
StringHelper::to_wstring("brother")};
408+
auto& bro = stats._prefix_expansions[field]
409+
.try_emplace(StringHelper::to_wstring("bro"), 50)
410+
.first->second;
411+
bro.insert(StringHelper::to_wstring("brother"));
412+
bro.insert(StringHelper::to_wstring("brown"));
413+
stats._prefix_expansions[field]
414+
.try_emplace(StringHelper::to_wstring("brot"), 50)
415+
.first->second.insert(StringHelper::to_wstring("brother"));
412416

413417
const auto score_of_brother = [&](const std::string& prefix) {
414418
PhrasePrefixQuery q(ctx, field, make_term_infos({"quick", prefix}));
@@ -486,17 +490,17 @@ TEST_F(PhrasePrefixQueryV2Test, segment_statistics_count_the_terms_a_prefix_expa
486490
quic.term = std::string("quic");
487491
scoring_collection_detail::append_scoring_prefix(&collect_info, quic, 50);
488492

489-
std::unordered_map<std::wstring, std::set<std::wstring>> expansions;
493+
FieldPrefixExpansions expansions;
490494
std::vector<std::string> terms;
491495
ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(*source, collect_info,
492496
&expansions, &terms)
493497
.ok());
494498
// quick is held twice, as a scoring term and as an expansion of quic, and listed once.
495499
EXPECT_EQ(terms, (std::vector<std::string> {"quick", "brother", "brown", "quickly"}));
496-
EXPECT_EQ(expansions[StringHelper::to_wstring("bro")],
500+
EXPECT_EQ(expansions.at(StringHelper::to_wstring("bro")).terms(),
497501
(std::set<std::wstring> {StringHelper::to_wstring("brother"),
498502
StringHelper::to_wstring("brown")}));
499-
EXPECT_EQ(expansions[StringHelper::to_wstring("quic")],
503+
EXPECT_EQ(expansions.at(StringHelper::to_wstring("quic")).terms(),
500504
(std::set<std::wstring> {StringHelper::to_wstring("quick"),
501505
StringHelper::to_wstring("quickly")}));
502506

‎be/test/storage/index/inverted/reader/collection_statistics_test.cpp‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2706,6 +2706,32 @@ TEST_F(CollectionStatisticsTest, CollectPhrasePrefixRegistersTheTailForExpansion
27062706
EXPECT_EQ(collect_info.scoring_prefixes[0].max_expansions, 50);
27072707
}
27082708

2709+
TEST_F(CollectionStatisticsTest,
2710+
CollectPhrasePrefixUnderNoSessionLimitScoresTheDefaultNumberOfTerms) {
2711+
TQueryOptions query_options;
2712+
query_options.inverted_index_max_expansions = 0;
2713+
runtime_state_->set_query_options(query_options);
2714+
auto tablet_schema = create_tablet_schema_with_inverted_index();
2715+
auto match_expr = std::make_shared<collection_statistics::MockVExpr>(TExprNodeType::MATCH_PRED);
2716+
match_expr->set_opcode(TExprOpcode::MATCH_PHRASE_PREFIX);
2717+
match_expr->_children.push_back(
2718+
std::make_shared<collection_statistics::MockVSlotRef>("content", SlotId(1)));
2719+
match_expr->_children.push_back(
2720+
std::make_shared<collection_statistics::MockVLiteral>("alpha gamma"));
2721+
2722+
MatchPredicateCollector collector;
2723+
CollectInfoMap collect_infos;
2724+
auto status =
2725+
collector.collect(runtime_state_.get(), tablet_schema, match_expr, &collect_infos);
2726+
2727+
ASSERT_TRUE(status.ok()) << status.msg();
2728+
const auto& collect_info = collect_infos.begin()->second;
2729+
// A limit of 0 expands the query's prefix to every term, but the statistics are kept for the
2730+
// whole scan and copied to each scanner, so they keep a bounded number.
2731+
ASSERT_EQ(collect_info.scoring_prefixes.size(), 1u);
2732+
EXPECT_EQ(collect_info.scoring_prefixes[0].max_expansions, kDefaultScoringExpansions);
2733+
}
2734+
27092735
TEST_F(CollectionStatisticsTest, CollectRepeatedPhrasePrefixRegistersTheTailOnce) {
27102736
auto tablet_schema = create_tablet_schema_with_inverted_index();
27112737
MatchPredicateCollector collector;
@@ -3343,4 +3369,26 @@ TEST(SearchPredicateCollectorTest, LucenePureExclusionAllowsFieldlessMatchAll) {
33433369
EXPECT_TRUE(infos.empty());
33443370
}
33453371

3372+
// With a limit of 1, segment A holding {rose} and segment B holding {red, rose} expand to rose and
3373+
// to red. The tablet scores red alone, whichever segment is counted first: rose's document
3374+
// frequency, which only segment A counted, would otherwise be too small.
3375+
TEST(PrefixExpansionSetTest, KeepsTheSmallestTermsWhateverTheSegmentOrder) {
3376+
const std::wstring red = L"red";
3377+
const std::wstring rose = L"rose";
3378+
for (const bool a_first : {true, false}) {
3379+
PrefixExpansionSet merged(1);
3380+
for (const bool is_a : {a_first, !a_first}) {
3381+
merged.insert(is_a ? rose : red);
3382+
}
3383+
EXPECT_EQ(merged.terms(), std::set<std::wstring> {red}) << "a_first=" << a_first;
3384+
}
3385+
3386+
PrefixExpansionSet three(3);
3387+
for (const std::wstring term : {L"d", L"b", L"e", L"a", L"c", L"b"}) {
3388+
three.insert(term);
3389+
}
3390+
EXPECT_EQ(three.terms(), (std::set<std::wstring> {L"a", L"b", L"c"}));
3391+
EXPECT_EQ(three.limit(), 3);
3392+
}
3393+
33463394
} // namespace doris

‎regression-test/data/inverted_index_p0/test_match_phrase_prefix_score.out‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,3 +63,12 @@
6363
2
6464
7
6565

66+
-- !capped_apple_r --
67+
1 1.1144
68+
2 1.1144
69+
70+
-- !uncapped_apple_r --
71+
1 1.5844
72+
2 1.5844
73+
3 1.5844
74+

‎regression-test/suites/inverted_index_p0/test_match_phrase_prefix_score.groovy‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,4 +100,30 @@ suite("test_match_phrase_prefix_score", "p0") {
100100
// The same rows without score().
101101
order_qt_v3_rows """ SELECT id FROM test_match_phrase_prefix_score_v3
102102
WHERE c1 MATCH_PHRASE_PREFIX 'apple gr' """
103+
104+
// A limit of one expansion over two segments. Segment A holds "apple rose", segment B holds
105+
// "apple red" and "apple rose"; each segment expands "r" to its smallest term, rose in A and
106+
// red in B. The tablet scores the prefix on red alone, the smallest term of the tablet, and
107+
// counts red in every segment that holds it. Counting rose from segment A only would give it
108+
// a document frequency of 1 instead of 2.
109+
sql "DROP TABLE IF EXISTS test_match_phrase_prefix_score_capped"
110+
sql """
111+
CREATE TABLE test_match_phrase_prefix_score_capped (
112+
id INT NULL,
113+
c1 TEXT NULL,
114+
INDEX idx_c1 (c1) USING INVERTED PROPERTIES("lower_case" = "true", "parser" = "english", "support_phrase" = "true")
115+
) ENGINE=OLAP
116+
DUPLICATE KEY(id)
117+
DISTRIBUTED BY HASH(id) BUCKETS 1
118+
PROPERTIES ("replication_allocation" = "tag.location.default: 1", "inverted_index_storage_format" = "V3");
119+
"""
120+
sql "INSERT INTO test_match_phrase_prefix_score_capped VALUES (1, 'apple rose')"
121+
sql "INSERT INTO test_match_phrase_prefix_score_capped VALUES (2, 'apple red'), (3, 'apple rose')"
122+
sql "sync"
123+
sql "set inverted_index_max_expansions = 1"
124+
order_qt_capped_apple_r """ SELECT id, round(score(), 4) s FROM test_match_phrase_prefix_score_capped
125+
WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER BY score() DESC LIMIT 10 """
126+
sql "set inverted_index_max_expansions = 50"
127+
order_qt_uncapped_apple_r """ SELECT id, round(score(), 4) s FROM test_match_phrase_prefix_score_capped
128+
WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER BY score() DESC LIMIT 10 """
103129
}

0 commit comments

Comments
 (0)