Skip to content

Commit 4016f20

Browse files
authored
[fix](be) Support BM25 scoring on keyword SEARCH indexes (apache#69051)
### What problem does this PR solve? Issue Number: None Related PR: apache#68758 Problem Summary: SEARCH can match a keyword inverted index, but projecting score() can drop matched rows or report an unsupported index. Keyword indexes omit norms and may omit frequencies; they still need usable BM25 defaults. Preserve whole keyword values, including case and whitespace. Use frequency and encoded norm 1 for docs-only/no-norm postings. Legacy indexes without total-term-frequency metadata use average length 1; SNII keeps its physical statistics. Analyzed segments missing required scoring metadata and numeric BKD scoring retain their existing restrictions. This branch incorporates master's unified MATCH/SEARCH engine from apache#68758. Keyword norm handling lives in the CLucene postings cursor, including partition switches and WAND bounds; SNII cursors provide docs-only frequencies and norms. The obsolete query_v2/SNII scoring implementations are removed with master. Keyword matching and missing-metadata behavior follow Elasticsearch while retaining Doris's existing BM25 formula and collection-statistics conventions. #### P1 follow-up: keyword filters and internal conjunctions 1. A keyword index explicitly declared with `parser=none` can inherit `support_phrase=true` from FE defaults. Ordinary MATCH filters then entered scoring although the statistics collector skipped that field. Both IndexReaderHelper query-type overloads now share the canonical analyzer-and-phrase eligibility check used by statistics collection. The implementation is out of line to keep analyzer dependencies out of the header. Named-analyzer and normalizer behavior is preserved. Equality and keyword MATCH filters keep the SEARCH-only baseline score. 2. Scored SNII AND grouped a docs-only keyword term into a path that counts positions. Such sources now use the existing individual term scorer with implicit unit frequency; position-bearing sources retain batched scoring. Internal `SEARCH('body:apple AND tag:x')` continues to score both fields.
1 parent 712f372 commit 4016f20

18 files changed

Lines changed: 930 additions & 84 deletions
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
#include "storage/index/index_reader_helper.h"
19+
20+
#include "storage/index/inverted/analysis/analyzer/analyzer.h"
21+
22+
namespace doris::segment_v2 {
23+
namespace {
24+
25+
bool can_score_match(const TabletIndex* index_meta) {
26+
const auto& properties = index_meta->properties();
27+
// parser=none can inherit support_phrase=true from FE defaults. MATCH statistics skip
28+
// these keyword indexes, so their filters must not request a scoring context either.
29+
return inverted_index::InvertedIndexAnalyzer::should_analyzer(properties) &&
30+
(get_parser_phrase_support_string_from_properties(properties) ==
31+
INVERTED_INDEX_PARSER_PHRASE_SUPPORT_YES ||
32+
IndexReaderHelper::is_normalizer_only(properties));
33+
}
34+
35+
} // namespace
36+
37+
bool IndexReaderHelper::is_need_similarity_score(InvertedIndexQueryType query_type,
38+
const TabletIndex* index_meta) {
39+
return (query_type == InvertedIndexQueryType::MATCH_ANY_QUERY ||
40+
query_type == InvertedIndexQueryType::MATCH_ALL_QUERY ||
41+
query_type == InvertedIndexQueryType::MATCH_PHRASE_QUERY ||
42+
query_type == InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY) &&
43+
can_score_match(index_meta);
44+
}
45+
46+
bool IndexReaderHelper::is_need_similarity_score(TExprOpcode::type query_type,
47+
const TabletIndex* index_meta) {
48+
return (query_type == TExprOpcode::MATCH_ANY || query_type == TExprOpcode::MATCH_ALL ||
49+
query_type == TExprOpcode::MATCH_PHRASE ||
50+
query_type == TExprOpcode::MATCH_PHRASE_PREFIX) &&
51+
can_score_match(index_meta);
52+
}
53+
54+
} // namespace doris::segment_v2

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

Lines changed: 3 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -103,36 +103,12 @@ class IndexReaderHelper {
103103
return iter->get_reader(InvertedIndexReaderType::STRING_TYPE) != nullptr;
104104
}
105105

106+
// MATCH filters score analyzed phrase indexes and single-term normalizers.
106107
static bool is_need_similarity_score(InvertedIndexQueryType query_type,
107-
const TabletIndex* index_meta) {
108-
if (query_type == InvertedIndexQueryType::MATCH_ANY_QUERY ||
109-
query_type == InvertedIndexQueryType::MATCH_ALL_QUERY ||
110-
query_type == InvertedIndexQueryType::MATCH_PHRASE_QUERY ||
111-
query_type == InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY) {
112-
const auto& properties = index_meta->properties();
113-
if (get_parser_phrase_support_string_from_properties(properties) ==
114-
INVERTED_INDEX_PARSER_PHRASE_SUPPORT_YES ||
115-
is_normalizer_only(properties)) {
116-
return true;
117-
}
118-
}
119-
return false;
120-
}
108+
const TabletIndex* index_meta);
121109

122110
static bool is_need_similarity_score(TExprOpcode::type query_type,
123-
const TabletIndex* index_meta) {
124-
if (query_type == TExprOpcode::MATCH_ANY || query_type == TExprOpcode::MATCH_ALL ||
125-
query_type == TExprOpcode::MATCH_PHRASE ||
126-
query_type == TExprOpcode::MATCH_PHRASE_PREFIX) {
127-
const auto& properties = index_meta->properties();
128-
if (get_parser_phrase_support_string_from_properties(properties) ==
129-
INVERTED_INDEX_PARSER_PHRASE_SUPPORT_YES ||
130-
is_normalizer_only(properties)) {
131-
return true;
132-
}
133-
}
134-
return false;
135-
}
111+
const TabletIndex* index_meta);
136112
};
137113

138114
} // namespace doris::segment_v2

‎be/src/storage/index/inverted/clucene/spi/clucene_postings_cursor.h‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -155,7 +155,7 @@ class ClucenePostingsCursor final : public index_query::PostingsCursor,
155155
const int32_t last = _iter->getLastDocInBlock();
156156
_bound = {.last_doc = static_cast<uint32_t>(last),
157157
.max_freq = _iter->getMaxBlockFreq(),
158-
.max_norm = _iter->getMaxBlockNorm(),
158+
.max_norm = _has_norms ? _iter->getMaxBlockNorm() : 1,
159159
.last_doc_known = last >= 0 && last != INT_MAX};
160160
if (_bound->last_doc_known) {
161161
_bound->last_doc += _doc_base;
@@ -305,6 +305,8 @@ class ClucenePostingsCursor final : public index_query::PostingsCursor,
305305
}
306306

307307
private:
308+
// Keyword indexes omit norms even when CLucene supplies a zero-filled norm buffer.
309+
// Exposing no norms makes PostingsBlock use length one, including after partition switches.
308310
void _select_partition(size_t index) {
309311
_partition = index;
310312
_block = {};
@@ -314,8 +316,8 @@ class ClucenePostingsCursor final : public index_query::PostingsCursor,
314316
const auto& part = _partitions[index];
315317
_iter = part.iter.get();
316318
_raw_positions = part.positions;
317-
_doc_base = part.begin;
318319
_has_norms = part.has_norms;
320+
_doc_base = part.begin;
319321
}
320322
}
321323

‎be/src/storage/index/inverted/query/engine/boolean_query/operator_boolean_weight.h‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -209,6 +209,15 @@ class OperatorBooleanWeight : public Weight {
209209
if (source == nullptr || !(any_source || source->batches_reads())) {
210210
continue;
211211
}
212+
if (scoring && _type == OperatorType::OP_AND) {
213+
index_query::IndexScoringStats stats;
214+
THROW_IF_ERROR(source->scoring_stats(&stats));
215+
// Batched AND scoring counts positions. Docs-only keywords have none, so
216+
// keep their individual scorers, which supply implicit unit frequencies.
217+
if (!stats.has_positions) {
218+
continue;
219+
}
220+
}
212221
auto group = std::ranges::find_if(groups, [&source](const ListedTerms& candidate) {
213222
return candidate.source() == source;
214223
});

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

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

2525
namespace doris::segment_v2 {
2626

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

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

Lines changed: 19 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -44,9 +44,11 @@ namespace collection_statistics_detail {
4444
Result<SniiScoringSegmentStats> resolve_snii_scoring_segment(uint64_t index_doc_count,
4545
uint64_t sum_total_term_freq,
4646
bool has_positions, bool has_norms,
47+
bool is_analyzed,
4748
bool single_term_normalizer) {
48-
// Lowercase-normalized docs-only postings use unit frequency and length for scoring.
49-
if ((!has_positions || !has_norms) && !single_term_normalizer) {
49+
// Keywords and lowercase-only normalizers can omit both sections: a matched value
50+
// contributes one term with unit frequency and length. Other analyzed sources need both.
51+
if (is_analyzed && !single_term_normalizer && (!has_positions || !has_norms)) {
5052
return ResultError(Status::Error<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED, false>(
5153
"SNII scoring requires positions and norms; this segment was written without "
5254
"positions or without norms. Norms are left out when the index sets \"norms\" = "
@@ -264,10 +266,11 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
264266
const uint64_t segment_doc_count = scoring_stats.doc_count;
265267
RETURN_IF_ERROR(admit_snii_scoring_segment(
266268
ws_field_name, segment_doc_count, scoring_stats.token_count,
267-
scoring_stats.has_positions, scoring_stats.has_norms,
268-
segment_v2::IndexReaderHelper::is_normalizer_only(
269+
scoring_stats.has_positions, scoring_stats.has_norms, &segment_accumulator,
270+
segment_v2::inverted_index::InvertedIndexAnalyzer::should_analyzer(
269271
collect_info.index_meta->properties()),
270-
&segment_accumulator));
272+
segment_v2::IndexReaderHelper::is_normalizer_only(
273+
collect_info.index_meta->properties())));
271274

272275
for (const auto& logical_term_bytes : collect_info.unique_terms) {
273276
const auto logical_term =
@@ -337,12 +340,11 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
337340
// BM25 on an analyzed index needs the record length of every row, and CLucene keeps
338341
// them, together with the field's token count, in the norms. A segment written without
339342
// norms would feed a zero avgdl, or rank its rows as zero-length documents next to the
340-
// segments that have norms, so refuse to score the collection, as SNII does. A
341-
// single-term normalizer can instead use unit frequency and length.
342-
const bool single_term_normalizer = segment_v2::IndexReaderHelper::is_normalizer_only(
343-
collect_info.index_meta->properties());
344-
// Docs-only lowercase indexes have no norms, but each matching row has one term.
345-
if (!scoring_stats.has_norms && !single_term_normalizer &&
343+
// segments that have norms, so refuse to score the collection, as SNII does.
344+
// Keywords and lowercase-only normalizers instead use unit document length.
345+
if (!scoring_stats.has_norms &&
346+
!segment_v2::IndexReaderHelper::is_normalizer_only(
347+
collect_info.index_meta->properties()) &&
346348
segment_v2::inverted_index::InvertedIndexAnalyzer::should_analyzer(
347349
collect_info.index_meta->properties())) {
348350
return Status::Error<ErrorCode::INVERTED_INDEX_NOT_SUPPORTED>(
@@ -351,10 +353,8 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
351353
"for a variant path, when inverted_index_skip_norms_for_variant is on",
352354
seg_path, segment_v2::inverted_index::StringHelper::to_string(ws_field_name));
353355
}
354-
// CLucene omits term totals without norms; one token per row gives a unit-length estimate.
355-
_total_num_tokens[ws_field_name] += !scoring_stats.has_norms && single_term_normalizer
356-
? scoring_stats.doc_count
357-
: scoring_stats.token_count;
356+
_total_num_tokens[ws_field_name] +=
357+
scoring_stats.has_norms ? scoring_stats.token_count : scoring_stats.doc_count;
358358

359359
for (const auto& logical_term_bytes : collect_info.unique_terms) {
360360
const auto logical_term =
@@ -375,11 +375,12 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
375375

376376
Status CollectionStatistics::admit_snii_scoring_segment(
377377
const std::wstring& field_name, uint64_t index_doc_count, uint64_t sum_total_term_freq,
378-
bool has_positions, bool has_norms, bool single_term_normalizer,
379-
SniiScoringSegmentAccumulator* segment_accumulator) {
378+
bool has_positions, bool has_norms, SniiScoringSegmentAccumulator* segment_accumulator,
379+
bool is_analyzed, bool single_term_normalizer) {
380380
DORIS_CHECK(segment_accumulator != nullptr);
381381
auto segment_stats = collection_statistics_detail::resolve_snii_scoring_segment(
382-
index_doc_count, sum_total_term_freq, has_positions, has_norms, single_term_normalizer);
382+
index_doc_count, sum_total_term_freq, has_positions, has_norms, is_analyzed,
383+
single_term_normalizer);
383384
if (!segment_stats.has_value()) {
384385
clear();
385386
return segment_stats.error();

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

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

@@ -121,11 +122,12 @@ struct SniiScoringSegmentStats {
121122
uint64_t token_count = 0;
122123
};
123124

124-
// Single-term normalizers can score docs-only postings with frequency and length one.
125-
// Other analyzed indexes need positions and norms for accurate BM25 scores.
125+
// Analyzed SNII indexes need positions and norms. Keywords and lowercase-only
126+
// normalizers can use unit frequency and norm when those sections are absent.
126127
Result<SniiScoringSegmentStats> resolve_snii_scoring_segment(uint64_t index_doc_count,
127128
uint64_t sum_total_term_freq,
128129
bool has_positions, bool has_norms,
130+
bool is_analyzed = true,
129131
bool single_term_normalizer = false);
130132

131133
void add_term_doc_frequency(

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -202,6 +202,7 @@ uint64_t posting_row_checksum(uint32_t doc, float score, bool scoring) {
202202
uint64_t expected_posting_checksum(const PostingSpec& spec, uint32_t profile, bool sparse,
203203
bool scoring) {
204204
BM25Similarity similarity(2.0F, 8.0F);
205+
// The physical fixtures omit norms, so every document has unit length.
205206
const float term_score = similarity.score(1.0F, 1);
206207
uint64_t result = 0;
207208
for (uint32_t doc = 0; doc < kPostingRows; ++doc) {
@@ -255,6 +256,7 @@ PhysicalTruthRows expected_physical_truth(const PostingSpec& spec, uint32_t prof
255256
PhysicalTruthRows result;
256257
result.scores.resize(kPostingRows);
257258
BM25Similarity similarity(2.0F, 8.0F);
259+
// The physical fixtures omit norms, so every document has unit length.
258260
const float term_score = similarity.score(1.0F, 1);
259261
for (uint32_t doc = 0; doc < kPostingRows; ++doc) {
260262
bool required_true = true;

‎be/test/storage/index/inverted/query/engine/boolean_query/listed_terms_test.cpp‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -687,6 +687,32 @@ TEST_F(ListedTermsTest, AScoredConjunctionScoresTheRowsItLists) {
687687
EXPECT_TRUE(listed->opened.empty());
688688
}
689689

690+
// A batching keyword source has no positions: its term scorers use frequency and norm 1.
691+
TEST_F(ListedTermsTest, AScoredDocsOnlyConjunctionUsesUnitFrequencyWithoutPositions) {
692+
for (bool batches : {false, true}) {
693+
auto keyword = std::make_shared<FakeIndexSource>();
694+
keyword->batches = batches;
695+
keyword->has_positions = false;
696+
keyword->set_doc_count(10);
697+
keyword->add("a", std::vector<uint32_t> {1, 2, 3});
698+
keyword->add("b", std::vector<uint32_t> {2, 3, 4});
699+
auto expected = summed({"a", "b"}, keyword);
700+
expected.erase(1);
701+
expected.erase(4);
702+
keyword->opened.clear();
703+
const auto actual = scored(
704+
[&] {
705+
return boolean(OperatorType::OP_AND, {term("a"), term("b")});
706+
},
707+
keyword);
708+
expect_scores_eq(actual, expected);
709+
EXPECT_EQ(keys(actual), (std::vector<uint32_t> {2, 3}));
710+
EXPECT_GT(actual.at(2), 0.0F);
711+
EXPECT_EQ(keyword->opened, (std::vector<std::string> {"a", "b"}));
712+
EXPECT_TRUE(keyword->opened_together.empty());
713+
}
714+
}
715+
690716
// The chain lists the rarer term whole and the other on its rows; then both read the positions
691717
// of the rows holding every term, in one round.
692718
TEST_F(ListedTermsTest, AScoredConjunctionReadsTheListedRowsPositionsInOneRound) {

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -249,6 +249,7 @@ static void check_native_posting_block(const index_query::PostingsBlock& block,
249249
EXPECT_EQ(block.doc_at(0), doc);
250250
EXPECT_EQ(block.docs.front(), doc);
251251
EXPECT_EQ(block.freq_at(0), 1);
252+
// These segments omit norms; crossing a partition must retain unit length.
252253
EXPECT_TRUE(block.norms.empty());
253254
EXPECT_EQ(block.norm_at(0), 1);
254255
}
@@ -408,6 +409,7 @@ TEST_F(MultiSegmentCollectorTest, PhraseCandidatesRemainValidAfterWeightDestruct
408409
auto scorer = weight->scorer(segment, "");
409410
weight.reset();
410411
ASSERT_EQ(scorer->doc(), 3);
412+
// Materialized phrase postings retain the no-norm source's unit length.
411413
const float expected_score = scoring ? similarity->score(1.0F, 1) : 1.0F;
412414
EXPECT_FLOAT_EQ(scorer->score(), expected_score);
413415
EXPECT_EQ(scorer->seek(3), 3);

0 commit comments

Comments
 (0)