Skip to content

Commit e3dfddb

Browse files
airborne12claude
andcommitted
[fix](inverted index) Score MATCH_PHRASE_PREFIX on the tablet idf of the terms the prefix expands to
### What problem does this PR solve? Issue Number: None Related PR: #68758 Problem Summary: score() over MATCH_PHRASE_PREFIX gave scores that ignored the prefix and differed between inverted index storage formats. 1. The prefix of a phrase prefix never entered the idf. "apple r" scored on idf(apple) alone, and a rare expansion such as "rose" ranked like a common one such as "red". Lucene's multi-phrase query, and so Elasticsearch, sum the idf of the phrase terms and of every term the prefix expands to. The statistics collector now registers the prefix; every segment expands it, counts the document frequency of each expanded term in the tablet statistics, and records which terms the prefix expanded to. The scorer adds their idf to the phrase's, so all idfs come from the same tablet statistics and the score does not depend on how rows are split into segments. With the reported table, `apple r` now scores 1.4508328, the value Elasticsearch 9.5 gives; on a 10-row table, `apple r`, `apple ro` and `apple g` match Elasticsearch to four decimals, over one segment and over three. 2. A prefix of one token scored 0 on V2/V3 (CLucene did not publish scores for expansion leaves) and 1 on SNII. It now scores 1 on every format, as the constant score of Lucene and Elasticsearch prefix queries. At 0, `score() > 0` dropped every row the prefix matched. 3. No test covered score() over MATCH_PHRASE_PREFIX across storage formats. Add unit tests for the collector, the segment expansion, the tablet idf and the constant score, and a regression suite over V2, V3 and SNII. Two existing tests asserted the old behavior and are updated: the SNII public phrase prefix scoring test (the idf now counts the expanded term) and the CLucene one-token phrase prefix test (it asserted no score). A prefix collected by a SEARCH predicate has no recorded expansion and keeps scoring the phrase terms alone. ### Release note score() over MATCH_PHRASE_PREFIX counts the terms the prefix expands to, and a phrase prefix of one token scores 1 on every inverted index storage format. ### Check List (For Author) - Test: Unit Test, Regression test - BE unit tests: 3158 related tests pass; the new idf and segment expansion tests fail without the change. - Regression test test_match_phrase_prefix_score on a local cluster. - Behavior changed: Yes (scores of MATCH_PHRASE_PREFIX change) - Does this need documentation: No Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent 3d2d9aa commit e3dfddb

14 files changed

Lines changed: 504 additions & 13 deletions

File tree

‎be/src/storage/index/inverted/clucene/clucene_index_reader.cpp‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -418,10 +418,9 @@ Status CluceneTextIndexReader::_run_leaf(const IndexQueryContextPtr& context,
418418
const logical::Node& leaf,
419419
const roaring::Roaring* candidates, bool scoring,
420420
std::shared_ptr<roaring::Roaring>* out) {
421-
const bool publish_scores = scoring && leaf.as<logical::Expand>() == nullptr;
422421
auto result = std::make_shared<roaring::Roaring>();
423422
RETURN_IF_ERROR(run_clucene_leaf(context, StringUtil::string_to_wstring(column_name), leaf,
424-
candidates, publish_scores,
423+
candidates, scoring,
425424
static_cast<CluceneOpenedIndex&>(index).searcher, result));
426425
result->runOptimize();
427426
*out = std::move(result);

‎be/src/storage/index/inverted/query/engine/phrase_prefix_query/phrase_prefix_query.h‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -72,14 +72,15 @@ class PhrasePrefixQuery : public Query {
7272
return nullptr;
7373
}
7474

75-
SimilarityPtr bm25_similarity;
75+
std::shared_ptr<BM25Similarity> bm25_similarity;
7676
if (enable_scoring) {
7777
bm25_similarity = std::make_shared<BM25Similarity>();
7878
std::vector<std::wstring> all_terms;
7979
for (const auto& phrase_term : _phrase_terms) {
8080
all_terms.push_back(StringHelper::to_wstring(phrase_term.second));
8181
}
82-
bm25_similarity->for_terms(_context, _field, all_terms);
82+
bm25_similarity->for_terms_and_prefix(_context, _field, all_terms,
83+
StringHelper::to_wstring(_prefix.value().second));
8384
}
8485

8586
return std::make_shared<PhrasePrefixWeight>(

‎be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -92,6 +92,18 @@ void BM25Similarity::for_terms(const IndexQueryContextPtr& context, const std::w
9292
compute_tf_cache();
9393
}
9494

95+
void BM25Similarity::for_terms_and_prefix(const IndexQueryContextPtr& context,
96+
const std::wstring& field_name,
97+
const std::vector<std::wstring>& terms,
98+
const std::wstring& prefix) {
99+
std::vector<std::wstring> all_terms = terms;
100+
for (auto& expansion :
101+
context->collection_statistics->get_prefix_expansions(field_name, prefix)) {
102+
all_terms.push_back(std::move(expansion));
103+
}
104+
for_terms(context, field_name, all_terms);
105+
}
106+
95107
float BM25Similarity::score(float freq, int64_t encoded_norm) {
96108
float norm_inverse = _cache[((uint8_t)encoded_norm) & 0xFF];
97109
return _weight - _weight / (1.0F + freq * norm_inverse);

‎be/src/storage/index/inverted/query/scoring/bm25_similarity.h‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,15 @@ class BM25Similarity : public Similarity {
3737
void for_terms(const IndexQueryContextPtr& context, const std::wstring& field_name,
3838
const std::vector<std::wstring>& terms) override;
3939

40+
// for_terms of `terms` and of every term the tablet expanded `prefix` to, so that a phrase
41+
// prefix is scored on the idf of the terms it matches, as Lucene's multi-phrase query does.
42+
//
43+
// Example: "quick bro" over a tablet holding brother and brown is scored on
44+
// idf(quick) + idf(brother) + idf(brown), so a row with the rare brother ranks above one with
45+
// the common brown.
46+
void for_terms_and_prefix(const IndexQueryContextPtr& context, const std::wstring& field_name,
47+
const std::vector<std::wstring>& terms, const std::wstring& prefix);
48+
4049
float score(float freq, int64_t encoded_norm) override;
4150
float max_score() override;
4251
void bind_norms(std::span<const float> lengths) override;

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

Lines changed: 68 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@
2222
#include <iterator>
2323
#include <set>
2424
#include <sstream>
25+
#include <unordered_set>
2526

2627
#include "common/exception.h"
2728
#include "core/column/column_vector.h"
@@ -40,6 +41,7 @@
4041
#include "storage/index/inverted/clucene/spi/clucene_index_source.h"
4142
#include "storage/index/inverted/common/inverted_index_cache.h"
4243
#include "storage/index/inverted/common/string_helper.h"
44+
#include "storage/index/inverted/query/exec/term_pattern.h"
4345
#include "storage/index/inverted/snii/reader/snii_index_source.h"
4446
#include "storage/index/inverted/snii/snii_doris_adapter.h"
4547
#include "storage/iterators.h"
@@ -117,6 +119,35 @@ void add_term_doc_frequency(
117119
(*logical_frequencies)[field][logical_term] += doc_frequency;
118120
}
119121

122+
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) {
125+
DORIS_CHECK(expansions != nullptr);
126+
DORIS_CHECK(terms != nullptr);
127+
*terms = collect_info.unique_terms;
128+
std::unordered_set<std::string> listed(terms->begin(), terms->end());
129+
for (const auto& scoring_prefix : collect_info.scoring_prefixes) {
130+
index_query::TermPattern pattern;
131+
RETURN_IF_ERROR(index_query::TermPattern::create(index_query::TermPatternKind::kPrefix,
132+
scoring_prefix.prefix, &pattern));
133+
std::vector<std::string> expanded;
134+
RETURN_IF_ERROR(source.expand_terms(
135+
pattern,
136+
index_query::expansion_limit(index_query::TermPatternKind::kPrefix,
137+
scoring_prefix.max_expansions),
138+
&expanded));
139+
auto& prefix_terms = (*expansions)[segment_v2::inverted_index::StringHelper::to_wstring(
140+
scoring_prefix.prefix)];
141+
for (auto& term : expanded) {
142+
prefix_terms.insert(segment_v2::inverted_index::StringHelper::to_wstring(term));
143+
if (listed.insert(term).second) {
144+
terms->push_back(std::move(term));
145+
}
146+
}
147+
}
148+
return Status::OK();
149+
}
150+
120151
Status sum_non_null_norm_lengths(index_query::IndexSource& source,
121152
std::span<const uint32_t> null_docs, uint64_t* out) {
122153
if (!null_docs.empty() && null_docs.back() >= source.doc_count()) {
@@ -513,7 +544,11 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
513544
segment_v2::IndexReaderHelper::is_normalizer_only(
514545
collect_info.index_meta->properties())));
515546

516-
for (const auto& logical_term_bytes : collect_info.unique_terms) {
547+
std::vector<std::string> segment_terms;
548+
RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
549+
source, collect_info, &segment_accumulator.prefix_expansions[ws_field_name],
550+
&segment_terms));
551+
for (const auto& logical_term_bytes : segment_terms) {
517552
const auto logical_term =
518553
segment_v2::inverted_index::StringHelper::to_wstring(logical_term_bytes);
519554
uint64_t doc_frequency = 0;
@@ -647,7 +682,10 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
647682
_total_num_tokens[ws_field_name] +=
648683
scoring_stats.has_norms ? scoring_stats.token_count : scoring_stats.doc_count;
649684

650-
for (const auto& logical_term_bytes : collect_info.unique_terms) {
685+
std::vector<std::string> segment_terms;
686+
RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
687+
*source, collect_info, &_prefix_expansions[ws_field_name], &segment_terms));
688+
for (const auto& logical_term_bytes : segment_terms) {
651689
const auto logical_term =
652690
segment_v2::inverted_index::StringHelper::to_wstring(logical_term_bytes);
653691
uint64_t doc_frequency = 0;
@@ -703,6 +741,11 @@ void CollectionStatistics::commit_snii_scoring_segment(
703741
_term_doc_freqs[field_name][term] += doc_freq;
704742
}
705743
}
744+
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());
747+
}
748+
}
706749
_total_num_docs += segment_accumulator.doc_count;
707750
_avg_dl_by_col.clear();
708751
_idf_by_col_term.clear();
@@ -713,6 +756,7 @@ void CollectionStatistics::clear() {
713756
_counted_hidden_docs = false;
714757
_total_num_tokens.clear();
715758
_term_doc_freqs.clear();
759+
_prefix_expansions.clear();
716760
_avg_dl_by_col.clear();
717761
_idf_by_col_term.clear();
718762
}
@@ -722,6 +766,7 @@ void CollectionStatistics::copy_collected_from(const CollectionStatistics& other
722766
_counted_hidden_docs = other._counted_hidden_docs;
723767
_total_num_tokens = other._total_num_tokens;
724768
_term_doc_freqs = other._term_doc_freqs;
769+
_prefix_expansions = other._prefix_expansions;
725770
_avg_dl_by_col.clear();
726771
_idf_by_col_term.clear();
727772
}
@@ -801,6 +846,27 @@ float CollectionStatistics::get_or_calculate_avg_dl(const std::wstring& lucene_c
801846
return avg_dl;
802847
}
803848

849+
std::vector<std::wstring> CollectionStatistics::get_prefix_expansions(
850+
const std::wstring& lucene_col_name, const std::wstring& prefix) {
851+
const auto field = _prefix_expansions.find(lucene_col_name);
852+
if (field == _prefix_expansions.end()) {
853+
return {};
854+
}
855+
const auto expansions = field->second.find(prefix);
856+
if (expansions == field->second.end()) {
857+
return {};
858+
}
859+
// A merge-on-write scan hides rows: a term whose documents are all hidden was expanded in
860+
// its segment but has no document frequency left, and its idf would be that of an absent term.
861+
std::vector<std::wstring> terms;
862+
for (const auto& term : expansions->second) {
863+
if (get_term_doc_freq_by_col(lucene_col_name, term) > 0) {
864+
terms.push_back(term);
865+
}
866+
}
867+
return terms;
868+
}
869+
804870
float CollectionStatistics::get_or_calculate_idf(const std::wstring& lucene_col_name,
805871
const std::wstring& term) {
806872
auto iter = _idf_by_col_term.find(lucene_col_name);

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -21,6 +21,7 @@
2121
#include <functional>
2222
#include <mutex>
2323
#include <optional>
24+
#include <set>
2425
#include <span>
2526
#include <string>
2627
#include <string_view>
@@ -106,15 +107,27 @@ class CollectionStatistics {
106107
const std::wstring& term);
107108
MOCK_FUNCTION float get_or_calculate_avg_dl(const std::wstring& lucene_col_name);
108109

110+
// The terms the collected `prefix` expanded to in any segment of the tablet and that some
111+
// returned row holds, in dictionary order; their idfs are in get_or_calculate_idf. None for a
112+
// prefix that was not collected, as for a SEARCH predicate.
113+
MOCK_FUNCTION std::vector<std::wstring> get_prefix_expansions(
114+
const std::wstring& lucene_col_name, const std::wstring& prefix);
115+
109116
// Replaces the collected counters with those of `other`. The derived idf/avgdl caches are
110117
// reset rather than copied, so the copy can be used by another thread without sharing them.
111118
void copy_collected_from(const CollectionStatistics& other);
112119

113120
private:
121+
// 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>>>;
125+
114126
struct SniiScoringSegmentAccumulator {
115127
uint64_t doc_count = 0;
116128
std::unordered_map<std::wstring, uint64_t> token_counts;
117129
std::unordered_map<std::wstring, std::unordered_map<std::wstring, uint64_t>> term_doc_freqs;
130+
PrefixExpansions prefix_expansions;
118131
};
119132

120133
Status extract_collect_info(RuntimeState* state,
@@ -143,6 +156,7 @@ class CollectionStatistics {
143156
bool _counted_hidden_docs = false;
144157
std::unordered_map<std::wstring, uint64_t> _total_num_tokens;
145158
std::unordered_map<std::wstring, std::unordered_map<std::wstring, uint64_t>> _term_doc_freqs;
159+
PrefixExpansions _prefix_expansions;
146160

147161
std::unordered_map<std::wstring, float> _avg_dl_by_col;
148162
std::unordered_map<std::wstring, std::unordered_map<std::wstring, float>> _idf_by_col_term;
@@ -230,6 +244,17 @@ Status exclude_hidden_docs(std::span<const uint32_t> hidden_docs, const roaring:
230244
const SumNormLengthsOf& sum_norm_lengths_of,
231245
index_query::IndexScoringStats* stats);
232246

247+
// The terms whose document frequencies a segment adds for `collect_info`: its scoring terms, then
248+
// each term its prefixes expand to in `source`, so that a phrase prefix is scored on the same
249+
// 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`.
251+
//
252+
// Example: "red r" collects red and, in a segment holding red, rose and run, the terms red (already
253+
// listed), rose and run, and records {red, rose, run} for the prefix "r".
254+
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);
257+
233258
// Takes from a term's document frequency the documents of `hidden_docs` that hold it.
234259
Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_view term,
235260
std::span<const uint32_t> hidden_docs, uint64_t* doc_frequency);

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

Lines changed: 28 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,8 @@
1919

2020
#include <glog/logging.h>
2121

22+
#include <algorithm>
23+
#include <optional>
2224
#include <vector>
2325

2426
#include "exec/common/variant_util.h"
@@ -30,6 +32,7 @@
3032
#include "storage/index/index_reader_helper.h"
3133
#include "storage/index/inverted/analysis/analyzer/analyzer.h"
3234
#include "storage/index/inverted/common/string_helper.h"
35+
#include "storage/index/inverted/query/exec/term_pattern.h"
3336
#include "storage/index/inverted/reader/inverted_index_selector.h"
3437
#include "storage/tablet/tablet_schema.h"
3538
#include "storage/utils.h"
@@ -116,6 +119,21 @@ Status append_scoring_leaf(CollectInfo* collect_info, const std::vector<TermInfo
116119
return Status::OK();
117120
}
118121

122+
void append_scoring_prefix(CollectInfo* collect_info, const TermInfo& prefix,
123+
int32_t max_expansions) {
124+
DORIS_CHECK(collect_info != nullptr);
125+
DORIS_CHECK(prefix.is_single_term());
126+
const auto& text = prefix.get_single_term();
127+
const bool known = std::ranges::any_of(
128+
collect_info->scoring_prefixes, [&](const LogicalScoringPrefix& registered) {
129+
return registered.prefix == text && registered.max_expansions == max_expansions;
130+
});
131+
if (!known) {
132+
collect_info->scoring_prefixes.push_back(
133+
LogicalScoringPrefix {.prefix = text, .max_expansions = max_expansions});
134+
}
135+
}
136+
119137
InvertedIndexQueryType match_query_type(TExprOpcode::type opcode) {
120138
switch (opcode) {
121139
case TExprOpcode::MATCH_ANY:
@@ -356,7 +374,13 @@ Status MatchPredicateCollector::collect(RuntimeState* state, const TabletSchemaS
356374
auto options = DataTypeSerDe::get_default_format_options();
357375
options.timezone = &state->timezone_obj();
358376
auto term_infos = DORIS_TRY(analyze_plain_query(right_literal->value(options), *analyzer_ctx));
377+
// The prefix of a phrase prefix is scored by the terms it expands to, so the statistics are
378+
// collected for them per segment; a prefix alone scores a constant and needs none.
379+
std::optional<TermInfo> scoring_prefix;
359380
if (expr->op() == TExprOpcode::MATCH_PHRASE_PREFIX && !term_infos.empty()) {
381+
if (term_infos.size() > 1) {
382+
scoring_prefix = term_infos.back();
383+
}
360384
term_infos.pop_back();
361385
}
362386

@@ -369,11 +393,14 @@ Status MatchPredicateCollector::collect(RuntimeState* state, const TabletSchemaS
369393
CollectInfo collect_info;
370394
RETURN_IF_ERROR(append_scoring_leaf(&collect_info, term_infos));
371395
preserve_selected_index_metadata(candidates, index_meta, &collect_info);
372-
(*collect_infos)[ws_field_name] = std::move(collect_info);
396+
iter = collect_infos->emplace(ws_field_name, std::move(collect_info)).first;
373397
} else {
374398
RETURN_IF_ERROR(validate_same_physical_index(iter->second, *index_meta));
375399
RETURN_IF_ERROR(append_scoring_leaf(&iter->second, term_infos));
376400
}
401+
if (scoring_prefix.has_value()) {
402+
append_scoring_prefix(&iter->second, *scoring_prefix, index_query::max_expansions(state));
403+
}
377404

378405
return Status::OK();
379406
}

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

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,9 +56,17 @@ 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.
61+
struct LogicalScoringPrefix {
62+
std::string prefix;
63+
int32_t max_expansions = 0;
64+
};
65+
5966
struct CollectInfo {
6067
std::vector<std::string> unique_terms;
6168
std::unordered_map<std::string, uint32_t> unique_term_slots;
69+
std::vector<LogicalScoringPrefix> scoring_prefixes;
6270
std::vector<LogicalScoringLeaf> logical_scoring_leaves;
6371
std::shared_ptr<const TabletIndex> owned_index_meta;
6472
const TabletIndex* index_meta = nullptr;
@@ -78,6 +86,9 @@ Result<std::vector<segment_v2::TermInfo>> analyze_plain_query(
7886
const std::string& value, const InvertedIndexAnalyzerCtx& analyzer_ctx);
7987
Status append_scoring_leaf(CollectInfo* collect_info,
8088
const std::vector<segment_v2::TermInfo>& term_infos);
89+
// Registers the prefix of a scored phrase prefix once, however many predicates repeat it.
90+
void append_scoring_prefix(CollectInfo* collect_info, const segment_v2::TermInfo& prefix,
91+
int32_t max_expansions);
8192
Result<const TabletIndex*> select_index_meta(const std::vector<const TabletIndex*>& index_metas,
8293
FieldType field_type,
8394
segment_v2::InvertedIndexQueryType query_type,

0 commit comments

Comments
 (0)