Skip to content

Commit 24b4c54

Browse files
airborne12claude
andcommitted
[fix](inverted index) Compute each visible term frequency of a segment once
### What problem does this PR solve? Issue Number: None Related PR: #69698 Problem Summary: On a merge-on-write segment with hidden rows, the document frequency of a term without its hidden rows costs an intersection of the term's postings with the hidden rows. The terms a scored phrase prefix expands to were asked for twice: once to choose the terms to keep, and once to add up their frequencies, so with the default of 50 common expansions and dense hidden rows their postings were traversed twice per segment, and a read of the dictionary with a larger limit or a second prefix repeated the work again. cached_visible_doc_freq computes the frequency once per term for the segment and the field, and both steps use it, in CLucene and in SNII. ### Release note None ### Check List (For Author) - Test: Unit Test, Regression test, Manual test - phrase_prefix_query_test: the document frequency of each term is read once across choosing and counting. - test_match_phrase_prefix_score passes unchanged on V2, V3 and SNII. - Manual: the merge-on-write table with a hidden `apple ra` scores the same rows at 1.0498 before and after a full compaction. - Behavior changed: No - Does this need documentation: No Co-Authored-By: Claude Sonnet 5.5 <[email protected]>
1 parent 59f3dc7 commit 24b4c54

3 files changed

Lines changed: 67 additions & 18 deletions

File tree

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

Lines changed: 22 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -254,6 +254,24 @@ Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_vi
254254
return Status::OK();
255255
}
256256

257+
VisibleDocFreq cached_visible_doc_freq(index_query::IndexSource& source,
258+
std::span<const uint32_t> hidden_docs) {
259+
auto cache = std::make_shared<std::unordered_map<std::string, uint64_t>>();
260+
return [&source, hidden_docs, cache](const std::string& term,
261+
uint64_t* doc_frequency) -> Status {
262+
if (const auto cached = cache->find(term); cached != cache->end()) {
263+
*doc_frequency = cached->second;
264+
return Status::OK();
265+
}
266+
RETURN_IF_ERROR(source.scoring_doc_freq(term, doc_frequency));
267+
if (!hidden_docs.empty()) {
268+
RETURN_IF_ERROR(exclude_hidden_term_docs(source, term, hidden_docs, doc_frequency));
269+
}
270+
cache->emplace(term, *doc_frequency);
271+
return Status::OK();
272+
};
273+
}
274+
257275
} // namespace collection_statistics_detail
258276

259277
namespace {
@@ -575,15 +593,8 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
575593
collect_info.index_meta->properties())));
576594

577595
// The document frequency of a term in this segment, without its hidden rows.
578-
const auto visible_doc_freq = [&](const std::string& term,
579-
uint64_t* doc_frequency) -> Status {
580-
RETURN_IF_ERROR(source.scoring_doc_freq(term, doc_frequency));
581-
if (!hidden_docs.empty()) {
582-
RETURN_IF_ERROR(collection_statistics_detail::exclude_hidden_term_docs(
583-
source, term, hidden_docs, doc_frequency));
584-
}
585-
return Status::OK();
586-
};
596+
const auto visible_doc_freq =
597+
collection_statistics_detail::cached_visible_doc_freq(source, hidden_docs);
587598
std::vector<std::string> segment_terms;
588599
RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
589600
source, collect_info, visible_doc_freq,
@@ -719,15 +730,8 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
719730
scoring_stats.has_norms ? scoring_stats.token_count : scoring_stats.doc_count;
720731

721732
// The document frequency of a term in this segment, without its hidden rows.
722-
const auto visible_doc_freq = [&](const std::string& term,
723-
uint64_t* doc_frequency) -> Status {
724-
RETURN_IF_ERROR(source->scoring_doc_freq(term, doc_frequency));
725-
if (!hidden_docs.empty()) {
726-
RETURN_IF_ERROR(collection_statistics_detail::exclude_hidden_term_docs(
727-
*source, term, hidden_docs, doc_frequency));
728-
}
729-
return Status::OK();
730-
};
733+
const auto visible_doc_freq =
734+
collection_statistics_detail::cached_visible_doc_freq(*source, hidden_docs);
731735
std::vector<std::string> segment_terms;
732736
RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
733737
*source, collect_info, visible_doc_freq, &_prefix_expansions[ws_field_name],

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

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -300,6 +300,14 @@ Status segment_scoring_terms(index_query::IndexSource& source, const CollectInfo
300300
Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_view term,
301301
std::span<const uint32_t> hidden_docs, uint64_t* doc_frequency);
302302

303+
// The document frequency of a term in `source` without the rows of `hidden_docs`, computed once
304+
// per term for the lifetime of the returned function. With hidden rows every term costs an
305+
// intersection of its postings with them, and the terms a prefix expands to are asked for twice:
306+
// to choose the ones to keep, and to add up the frequencies of the ones kept.
307+
// `source` and `hidden_docs` must outlive the function.
308+
VisibleDocFreq cached_visible_doc_freq(index_query::IndexSource& source,
309+
std::span<const uint32_t> hidden_docs);
310+
303311
} // namespace collection_statistics_detail
304312

305313
} // namespace doris

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -569,6 +569,15 @@ class DictionaryOnlySource final : public index_query::IndexSource {
569569
return Status::OK();
570570
}
571571

572+
// Every term is held by 3 documents; the calls are counted.
573+
Status doc_freq(std::string_view, uint64_t* out) override {
574+
++doc_freq_calls;
575+
*out = 3;
576+
return Status::OK();
577+
}
578+
579+
int doc_freq_calls = 0;
580+
572581
Status expand_terms(index_query::TermPattern&, int32_t max_expansions,
573582
std::vector<std::string>* out) override {
574583
out->clear();
@@ -614,6 +623,34 @@ TEST_F(PhrasePrefixQueryV2Test, segment_statistics_skip_terms_without_a_wide_str
614623
StringHelper::to_wstring("rc")}));
615624
}
616625

626+
// With hidden rows every document frequency costs an intersection of the term's postings with
627+
// them. The terms a prefix expands to are asked for twice, to choose the ones kept and to add up
628+
// their frequencies, and the intersection is made once.
629+
TEST_F(PhrasePrefixQueryV2Test, visible_document_frequencies_are_computed_once_per_term) {
630+
DictionaryOnlySource source({"rb", "rc"});
631+
const auto doc_freq = collection_statistics_detail::cached_visible_doc_freq(source, {});
632+
633+
CollectInfo collect_info;
634+
TermInfo r;
635+
r.term = std::string("r");
636+
scoring_collection_detail::append_scoring_prefix(&collect_info, r, 2);
637+
FieldPrefixExpansions expansions;
638+
std::vector<std::string> terms;
639+
ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(source, collect_info, doc_freq,
640+
&expansions, &terms)
641+
.ok());
642+
ASSERT_EQ(terms, (std::vector<std::string> {"rb", "rc"}));
643+
EXPECT_EQ(source.doc_freq_calls, 2);
644+
645+
// The final count asks for the same terms again.
646+
for (const auto& term : terms) {
647+
uint64_t frequency = 0;
648+
ASSERT_TRUE(doc_freq(term, &frequency).ok());
649+
EXPECT_EQ(frequency, 3U);
650+
}
651+
EXPECT_EQ(source.doc_freq_calls, 2);
652+
}
653+
617654
// --- PhrasePrefixWeight scorer: nullable branch ---
618655

619656
TEST_F(PhrasePrefixQueryV2Test, scorer_nullable) {

0 commit comments

Comments
 (0)