Skip to content

Commit f22f161

Browse files
committed
[fix](be) Support BM25 scoring on keyword SEARCH indexes
1 parent 97c2f1f commit f22f161

16 files changed

Lines changed: 536 additions & 142 deletions

File tree

‎be/src/exprs/function/function_search.cpp‎

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -902,13 +902,14 @@ Status FunctionSearch::build_leaf_query(const TSearchClause& clause,
902902
// of conditions the reader itself uses (its actual_similarity): the caller supplied a
903903
// similarity at all, and this query type scores on this index. Deciding it up front beats
904904
// inferring it afterwards from "the sink came back non-empty", and it keeps every clause
905-
// that cannot be scored -- wildcard, regexp, EQUAL_QUERY, and the WILDCARD "*" shortcut
905+
// that cannot be scored -- wildcard, regexp, and the WILDCARD "*" shortcut
906906
// that never calls the reader -- from allocating a CollectionSimilarity that reserves
907907
// 1024 entries in its constructor.
908908
const bool reader_will_score =
909909
context->collection_similarity != nullptr &&
910-
IndexReaderHelper::is_need_similarity_score(
911-
snii_query_type, &binding.inverted_reader->get_index_meta());
910+
IndexReaderHelper::is_need_snii_similarity_score(
911+
snii_query_type, &binding.inverted_reader->get_index_meta(),
912+
binding.inverted_reader->type());
912913
std::shared_ptr<segment_v2::IndexQueryContext> reader_context = context;
913914
std::shared_ptr<CollectionSimilarity> score_sink;
914915
if (reader_will_score) {

‎be/src/storage/index/index_reader_helper.h‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -103,6 +103,20 @@ class IndexReaderHelper {
103103
return false;
104104
}
105105

106+
// SEARCH and the native reader must agree before allocating the private score sink.
107+
static bool is_need_snii_similarity_score(InvertedIndexQueryType query_type,
108+
const TabletIndex* index_meta,
109+
InvertedIndexReaderType reader_type) {
110+
if (reader_type == InvertedIndexReaderType::STRING_TYPE &&
111+
(query_type == InvertedIndexQueryType::EQUAL_QUERY ||
112+
query_type == InvertedIndexQueryType::MATCH_ANY_QUERY ||
113+
query_type == InvertedIndexQueryType::MATCH_ALL_QUERY ||
114+
query_type == InvertedIndexQueryType::MATCH_PHRASE_QUERY)) {
115+
return true;
116+
}
117+
return is_need_similarity_score(query_type, index_meta);
118+
}
119+
106120
static bool is_need_similarity_score(TExprOpcode::type query_type,
107121
const TabletIndex* index_meta) {
108122
if (query_type == TExprOpcode::MATCH_ANY || query_type == TExprOpcode::MATCH_ALL ||

‎be/src/storage/index/inverted/query_v2/segment_postings.h‎

Lines changed: 21 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -49,19 +49,23 @@ class SegmentPostings : public Postings {
4949
public:
5050
using IterVariant = std::variant<std::monostate, TermDocsPtr, TermPositionsPtr>;
5151

52-
explicit SegmentPostings(TermDocsPtr iter, bool enable_scoring, SimilarityPtr similarity)
52+
explicit SegmentPostings(TermDocsPtr iter, bool enable_scoring, SimilarityPtr similarity,
53+
bool has_norms = true)
5354
: _iter(std::move(iter)),
5455
_enable_scoring(enable_scoring),
56+
_has_norms(has_norms),
5557
_similarity(std::move(similarity)) {
5658
if (auto* p = std::get_if<TermDocsPtr>(&_iter)) {
5759
_raw_iter = p->get();
5860
}
5961
_init_doc();
6062
}
6163

62-
explicit SegmentPostings(TermPositionsPtr iter, bool enable_scoring, SimilarityPtr similarity)
64+
explicit SegmentPostings(TermPositionsPtr iter, bool enable_scoring, SimilarityPtr similarity,
65+
bool has_norms = true)
6366
: _iter(std::move(iter)),
6467
_enable_scoring(enable_scoring),
68+
_has_norms(has_norms),
6569
_has_positions(true),
6670
_similarity(std::move(similarity)) {
6771
if (auto* p = std::get_if<TermPositionsPtr>(&_iter)) {
@@ -120,7 +124,7 @@ class SegmentPostings : public Postings {
120124
}
121125

122126
uint32_t norm() const override {
123-
if (!_enable_scoring || !_block.norm_many || _cursor == 0) {
127+
if (!_enable_scoring || !_has_norms || !_block.norm_many || _cursor == 0) {
124128
return 1;
125129
}
126130
return (*_block.norm_many)[_cursor - 1];
@@ -194,24 +198,28 @@ class SegmentPostings : public Postings {
194198
return _block_max_score_cache;
195199
}
196200
int32_t max_block_freq = _raw_iter->getMaxBlockFreq();
197-
int32_t max_block_norm = _raw_iter->getMaxBlockNorm();
201+
int32_t max_block_norm = _has_norms ? _raw_iter->getMaxBlockNorm() : 1;
198202
if (max_block_freq >= 0 && max_block_norm >= 0) {
199203
_block_max_score_cache = _similarity->score(static_cast<float>(max_block_freq),
200204
static_cast<int64_t>(max_block_norm));
201205
return _block_max_score_cache;
202206
}
203-
return _similarity->max_score();
207+
return max_score();
204208
}
205209

206210
float max_score() const {
207211
if (!_enable_scoring || !_similarity) {
208212
return std::numeric_limits<float>::max();
209213
}
214+
// Missing norms have a fixed length of one, including for WAND bounds.
215+
if (!_has_norms) {
216+
return _similarity->score(std::numeric_limits<float>::max(), 1);
217+
}
210218
return _similarity->max_score();
211219
}
212220

213221
int32_t max_block_freq() const { return _raw_iter->getMaxBlockFreq(); }
214-
int32_t max_block_norm() const { return _raw_iter->getMaxBlockNorm(); }
222+
int32_t max_block_norm() const { return _has_norms ? _raw_iter->getMaxBlockNorm() : 1; }
215223

216224
private:
217225
bool _refill() {
@@ -241,6 +249,7 @@ class SegmentPostings : public Postings {
241249
lucene::index::TermDocs* _raw_iter = nullptr;
242250
uint32_t _doc = TERMINATED;
243251
bool _enable_scoring = false;
252+
bool _has_norms = true;
244253
bool _has_positions = false;
245254

246255
DocRange _block;
@@ -253,13 +262,15 @@ class SegmentPostings : public Postings {
253262
using SegmentPostingsPtr = std::shared_ptr<SegmentPostings>;
254263

255264
inline SegmentPostingsPtr make_segment_postings(TermDocsPtr iter, bool enable_scoring,
256-
SimilarityPtr similarity) {
257-
return std::make_shared<SegmentPostings>(std::move(iter), enable_scoring, similarity);
265+
SimilarityPtr similarity, bool has_norms = true) {
266+
return std::make_shared<SegmentPostings>(std::move(iter), enable_scoring, similarity,
267+
has_norms);
258268
}
259269

260270
inline SegmentPostingsPtr make_segment_postings(TermPositionsPtr iter, bool enable_scoring,
261-
SimilarityPtr similarity) {
262-
return std::make_shared<SegmentPostings>(std::move(iter), enable_scoring, similarity);
271+
SimilarityPtr similarity, bool has_norms = true) {
272+
return std::make_shared<SegmentPostings>(std::move(iter), enable_scoring, similarity,
273+
has_norms);
263274
}
264275

265276
} // namespace doris::segment_v2::inverted_index::query_v2

‎be/src/storage/index/inverted/query_v2/weight.h‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -151,7 +151,9 @@ class Weight {
151151
const io::IOContext* io_ctx) const {
152152
auto t = make_term_ptr(field.c_str(), term.c_str());
153153
auto iter = make_term_doc_ptr(reader, t.get(), enable_scoring, io_ctx);
154-
return iter ? make_segment_postings(std::move(iter), enable_scoring, similarity) : nullptr;
154+
return iter ? make_segment_postings(std::move(iter), enable_scoring, similarity,
155+
reader->hasNorms(field.c_str()))
156+
: nullptr;
155157
}
156158

157159
SegmentPostingsPtr create_position_posting(lucene::index::IndexReader* reader,
@@ -168,7 +170,9 @@ class Weight {
168170
const io::IOContext* io_ctx) const {
169171
auto t = make_term_ptr(field.c_str(), term.c_str());
170172
auto iter = make_term_positions_ptr(reader, t.get(), enable_scoring, io_ctx);
171-
return iter ? make_segment_postings(std::move(iter), enable_scoring, similarity) : nullptr;
173+
return iter ? make_segment_postings(std::move(iter), enable_scoring, similarity,
174+
reader->hasNorms(field.c_str()))
175+
: nullptr;
172176
}
173177
};
174178

‎be/src/storage/index/inverted/similarity/bm25_similarity.h‎

Lines changed: 2 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -21,14 +21,8 @@
2121

2222
namespace doris::segment_v2 {
2323

24-
/**
25-
* BM25 similarity scoring implementation for inverted index queries.
26-
*
27-
* Note: Currently, BM25 scoring is only applied to tokenized indexes (e.g., standard, chinese analyzers)
28-
* and not to non-tokenized indexes (e.g., keyword analyzer). This differs from Elasticsearch,
29-
* which applies scoring to keyword indexes as well. In Doris, keyword/non-tokenized indexes
30-
* are primarily used for exact matching without relevance scoring.
31-
*/
24+
// BM25 scoring for analyzed and keyword indexes. Keyword indexes without norms
25+
// use the Lucene default encoded norm of one.
3226
class BM25Similarity : public Similarity {
3327
public:
3428
BM25Similarity();

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

Lines changed: 12 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -43,8 +43,9 @@ namespace collection_statistics_detail {
4343

4444
Result<SniiScoringSegmentStats> resolve_snii_scoring_segment(uint64_t index_doc_count,
4545
uint64_t sum_total_term_freq,
46-
bool has_positions, bool has_norms) {
47-
if (!has_positions || !has_norms) {
46+
bool has_positions, bool has_norms,
47+
bool is_analyzed) {
48+
if (is_analyzed && (!has_positions || !has_norms)) {
4849
return ResultError(Status::Error<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED, false>(
4950
"SNII scoring requires positions and norms; this segment was written without "
5051
"positions or without norms. Norms are left out when the index sets \"norms\" = "
@@ -249,7 +250,9 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
249250
RETURN_IF_ERROR(admit_snii_scoring_segment(
250251
ws_field_name, segment_doc_count, logical_reader->stats().sum_total_term_freq,
251252
logical_reader->has_positions(), logical_reader->has_norms(),
252-
&segment_accumulator));
253+
&segment_accumulator,
254+
segment_v2::inverted_index::InvertedIndexAnalyzer::should_analyzer(
255+
collect_info.index_meta->properties())));
253256

254257
::doris::snii::reader::DictBlockCache dict_block_cache;
255258
for (const auto& logical_term_bytes : collect_info.unique_terms) {
@@ -319,7 +322,8 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
319322
// them, together with the field's token count, in the norms. A segment written without
320323
// norms would feed a zero avgdl, or rank its rows as zero-length documents next to the
321324
// segments that have norms, so refuse to score the collection, as SNII does. An index
322-
// that is not analyzed never writes norms and is left as it is.
325+
// that is not analyzed never writes norms; use an average length of one when
326+
// legacy metadata cannot supply its total term frequency.
323327
const auto token_count = index_reader->sumTotalTermFreq(ws_field_name.c_str());
324328
if (!token_count.has_value() &&
325329
segment_v2::inverted_index::InvertedIndexAnalyzer::should_analyzer(
@@ -330,7 +334,7 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
330334
"for a variant path, when inverted_index_skip_norms_for_variant is on",
331335
seg_path, StringHelper::to_string(ws_field_name));
332336
}
333-
_total_num_tokens[ws_field_name] += token_count.value_or(0);
337+
_total_num_tokens[ws_field_name] += token_count.value_or(index_reader->maxDoc());
334338

335339
for (const auto& logical_term_bytes : collect_info.unique_terms) {
336340
const auto logical_term =
@@ -351,10 +355,11 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
351355

352356
Status CollectionStatistics::admit_snii_scoring_segment(
353357
const std::wstring& field_name, uint64_t index_doc_count, uint64_t sum_total_term_freq,
354-
bool has_positions, bool has_norms, SniiScoringSegmentAccumulator* segment_accumulator) {
358+
bool has_positions, bool has_norms, SniiScoringSegmentAccumulator* segment_accumulator,
359+
bool is_analyzed) {
355360
DORIS_CHECK(segment_accumulator != nullptr);
356361
auto segment_stats = collection_statistics_detail::resolve_snii_scoring_segment(
357-
index_doc_count, sum_total_term_freq, has_positions, has_norms);
362+
index_doc_count, sum_total_term_freq, has_positions, has_norms, is_analyzed);
358363
if (!segment_stats.has_value()) {
359364
clear();
360365
return segment_stats.error();

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

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -86,7 +86,8 @@ class CollectionStatistics {
8686
Status admit_snii_scoring_segment(const std::wstring& field_name, uint64_t index_doc_count,
8787
uint64_t sum_total_term_freq, bool has_positions,
8888
bool has_norms,
89-
SniiScoringSegmentAccumulator* segment_accumulator);
89+
SniiScoringSegmentAccumulator* segment_accumulator,
90+
bool is_analyzed = true);
9091
void commit_snii_scoring_segment(SniiScoringSegmentAccumulator&& segment_accumulator);
9192
void clear();
9293

@@ -119,12 +120,12 @@ struct SniiScoringSegmentStats {
119120
uint64_t token_count = 0;
120121
};
121122

122-
// SNII scoring requires positions (which provide term frequencies) and norms. The current writer
123-
// emits norms for every analyzed index with positions. Older segments without norms return
124-
// NOT_SUPPORTED until an index rebuild or compaction supplies them.
123+
// Analyzed SNII indexes need positions and norms. Keyword indexes can score with
124+
// implicit unit frequency and norm when those sections are absent.
125125
Result<SniiScoringSegmentStats> resolve_snii_scoring_segment(uint64_t index_doc_count,
126126
uint64_t sum_total_term_freq,
127-
bool has_positions, bool has_norms);
127+
bool has_positions, bool has_norms,
128+
bool is_analyzed = true);
128129

129130
void add_term_doc_frequency(
130131
std::unordered_map<std::wstring, std::unordered_map<std::wstring, uint64_t>>*

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

Lines changed: 4 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -279,12 +279,6 @@ Status validate_search_bm25_index(FieldType field_type, const TabletIndex& index
279279
"search field={}",
280280
field_name);
281281
}
282-
if (!InvertedIndexAnalyzer::should_analyzer(index_meta.properties())) {
283-
return Status::Error<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED>(
284-
"Index statistics collection failed: BM25 scoring requires an analyzed inverted "
285-
"index for search field={}",
286-
field_name);
287-
}
288282
return Status::OK();
289283
}
290284

@@ -552,13 +546,14 @@ Status SearchPredicateCollector::collect_from_leaf(const TSearchClause& clause,
552546
const auto* index_meta = *selected_index;
553547
RETURN_IF_ERROR(validate_search_bm25_index(candidates.field_type, *index_meta, field_name));
554548

555-
const auto& analysis_properties = index_meta->properties();
556-
auto analyzer_ctx = DORIS_TRY(analyzer_context_from_properties(analysis_properties));
557549
std::vector<TermInfo> term_infos;
558-
if (clause_type == "MATCH" ||
550+
if (!InvertedIndexAnalyzer::should_analyzer(index_meta->properties()) ||
551+
clause_type == "MATCH" ||
559552
(category == ClauseTypeCategory::NON_TOKENIZED && clause_type != "TERM")) {
553+
// Keyword indexes store the whole value, including whitespace and case.
560554
term_infos.emplace_back(value);
561555
} else {
556+
auto analyzer_ctx = DORIS_TRY(analyzer_context_from_properties(index_meta->properties()));
562557
term_infos = DORIS_TRY(analyze_plain_query(value, analyzer_ctx));
563558
}
564559

0 commit comments

Comments
 (0)