This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-4.2
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-4.2 by this push:
new da739613d35 branch-4.2: [fix](inverted index) Score
MATCH_PHRASE_PREFIX on the tablet idf of the terms the prefix expands to #69698
(#69801)
da739613d35 is described below
commit da739613d35b2197087c83ea2e0629dc75c0124f
Author: Jack <[email protected]>
AuthorDate: Fri Oct 30 09:38:12 2026 +0800
branch-4.2: [fix](inverted index) Score MATCH_PHRASE_PREFIX on the tablet
idf of the terms the prefix expands to #69698 (#69801)
### What problem does this PR solve?
Issue Number: None
Related PR: #69698, #69752
Problem Summary:
Backport of #69698 to branch-4.2. score() over MATCH_PHRASE_PREFIX
ignored the prefix and
differed between inverted index storage formats:
1. The idf of a phrase prefix now counts every term the prefix expands
to, as Lucene's
multi-phrase query and Elasticsearch do, and all idfs come from the
tablet statistics. The
statistics expand the prefix in every segment and keep the
`inverted_index_max_expansions`
smallest terms of the tablet that a returned row holds (a session limit
of 0 keeps 50), so a
term's document frequency is counted in every segment that holds it and
merge-on-write hidden
rows do not change the scores after a compaction. A term whose bytes are
not valid UTF-8 is not
scored.
2. A phrase prefix of one token scores 1 on every storage format; on
V2/V3 it read 0, so
`score() > 0` dropped every row it matched.
See #69698 for the full description and the review rounds.
This change builds on #69438 (BM25 statistics count only visible rows of
merge-on-write tables),
whose branch-4.2 backport #69752 is merged. The PR is rebased onto the
current branch-4.2 and
contains only the backport commit; its patch is identical to the one
validated below.
### Branch adaptations
- No production code adaptation. The automatic pick conflicted only
because #69438 was not on
branch-4.2 yet; on top of #69752 the change applies with one conflict,
in the context of
`collection_statistics_test.cpp`: branch-4.2 already has
`CollectConvertsAnalyzerFailureToStatus` elsewhere in the file, so the
copy that master shows
next to the renamed test is not added again.
### 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: Regression test, Unit Test
- Validated locally on branch-4.2 at 711db43b00, the commit before
#69625, with the same two
commits on top: the newest branch-4.2 calls a lance-c API that no
thirdparty build on the
machine used here provides. The PR branch itself is on the current
branch-4.2 and is built
by CI.
- test_match_phrase_prefix_score passes with the `.out` of master
unchanged (V2, V3, SNII and
the capped two-segment case).
- test_bm25_score, test_bm25_score_parallel_scan_statistics,
test_bm25_score_range_filter,
test_bm25_score_replica_statistics, test_bm25_score_variant,
test_score_filter_matrix,
test_score_filter_usage and test_search_score_topn_predicates pass.
- 1644 related BE unit tests pass (PhrasePrefixQueryV2Test,
CollectionStatistics*,
PrefixExpansionSetTest, SNII, InvertedIndexReaderTest,
MultiSegmentCollectorTest,
BM25SimilarityTest).
- Behavior changed: Yes (scores of MATCH_PHRASE_PREFIX change)
- Does this need documentation: No
🤖 Generated with [Claude Code](https://claude.com/claude-code)
Co-authored-by: Claude Opus 5.5 <[email protected]>
---
.../inverted/clucene/clucene_index_reader.cpp | 3 +-
.../phrase_prefix_query/phrase_prefix_query.h | 5 +-
.../inverted/query/scoring/bm25_similarity.cpp | 12 +
.../index/inverted/query/scoring/bm25_similarity.h | 9 +
.../inverted/reader/collection_statistics.cpp | 137 ++++++++++-
.../index/inverted/reader/collection_statistics.h | 74 ++++++
.../index/inverted/reader/predicate_collector.cpp | 35 ++-
.../index/inverted/reader/predicate_collector.h | 14 ++
.../query/engine/phrase_prefix_query_test.cpp | 267 +++++++++++++++++++++
.../inverted/reader/collection_statistics_test.cpp | 80 +++++-
.../snii/snii_index_reader_count_fallback_test.cpp | 14 +-
.../storage/segment/inverted_index_reader_test.cpp | 11 +-
.../test_match_phrase_prefix_score.out | 74 ++++++
.../test_match_phrase_prefix_score.groovy | 129 ++++++++++
14 files changed, 841 insertions(+), 23 deletions(-)
diff --git a/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
b/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
index 478601f6a19..eb2b20b624e 100644
--- a/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
+++ b/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
@@ -413,10 +413,9 @@ Status CluceneTextIndexReader::_run_leaf(const
IndexQueryContextPtr& context,
const logical::Node& leaf,
const roaring::Roaring* candidates,
bool scoring,
std::shared_ptr<roaring::Roaring>*
out) {
- const bool publish_scores = scoring && leaf.as<logical::Expand>() ==
nullptr;
auto result = std::make_shared<roaring::Roaring>();
RETURN_IF_ERROR(run_clucene_leaf(context,
StringUtil::string_to_wstring(column_name), leaf,
- candidates, publish_scores,
+ candidates, scoring,
static_cast<CluceneOpenedIndex&>(index).searcher, result));
result->runOptimize();
*out = std::move(result);
diff --git
a/be/src/storage/index/inverted/query/engine/phrase_prefix_query/phrase_prefix_query.h
b/be/src/storage/index/inverted/query/engine/phrase_prefix_query/phrase_prefix_query.h
index ec34e7b78b7..eb5f1e044db 100644
---
a/be/src/storage/index/inverted/query/engine/phrase_prefix_query/phrase_prefix_query.h
+++
b/be/src/storage/index/inverted/query/engine/phrase_prefix_query/phrase_prefix_query.h
@@ -72,14 +72,15 @@ private:
return nullptr;
}
- SimilarityPtr bm25_similarity;
+ std::shared_ptr<BM25Similarity> bm25_similarity;
if (enable_scoring) {
bm25_similarity = std::make_shared<BM25Similarity>();
std::vector<std::wstring> all_terms;
for (const auto& phrase_term : _phrase_terms) {
all_terms.push_back(StringHelper::to_wstring(phrase_term.second));
}
- bm25_similarity->for_terms(_context, _field, all_terms);
+ bm25_similarity->for_terms_and_prefix(_context, _field, all_terms,
+
StringHelper::to_wstring(_prefix.value().second));
}
return std::make_shared<PhrasePrefixWeight>(
diff --git a/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
b/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
index 63aa9b63e1b..0ca1409eba7 100644
--- a/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
+++ b/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
@@ -93,6 +93,18 @@ void BM25Similarity::for_terms(const IndexQueryContextPtr&
context, const std::w
compute_tf_cache();
}
+void BM25Similarity::for_terms_and_prefix(const IndexQueryContextPtr& context,
+ const std::wstring& field_name,
+ const std::vector<std::wstring>&
terms,
+ const std::wstring& prefix) {
+ std::vector<std::wstring> all_terms = terms;
+ for (auto& expansion :
+ context->collection_statistics->get_prefix_expansions(field_name,
prefix)) {
+ all_terms.push_back(std::move(expansion));
+ }
+ for_terms(context, field_name, all_terms);
+}
+
float BM25Similarity::score(float freq, int64_t encoded_norm) {
float norm_inverse = _cache[((uint8_t)encoded_norm) & 0xFF];
return _weight - _weight / (1.0F + freq * norm_inverse);
diff --git a/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
b/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
index 3adc0c3d850..a8e210f42a8 100644
--- a/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
+++ b/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
@@ -38,6 +38,15 @@ public:
void for_terms(const IndexQueryContextPtr& context, const std::wstring&
field_name,
const std::vector<std::wstring>& terms) override;
+ // for_terms of `terms` and of every term the tablet expanded `prefix` to,
so that a phrase
+ // prefix is scored on the idf of the terms it matches, as Lucene's
multi-phrase query does.
+ //
+ // Example: "quick bro" over a tablet holding brother and brown is scored
on
+ // idf(quick) + idf(brother) + idf(brown), so a row with the rare brother
ranks above one with
+ // the common brown.
+ void for_terms_and_prefix(const IndexQueryContextPtr& context, const
std::wstring& field_name,
+ const std::vector<std::wstring>& terms, const
std::wstring& prefix);
+
float score(float freq, int64_t encoded_norm) override;
float max_score() override;
void bind_norms(std::span<const float> lengths) override;
diff --git a/be/src/storage/index/inverted/reader/collection_statistics.cpp
b/be/src/storage/index/inverted/reader/collection_statistics.cpp
index 1f1d02154df..b73d80825af 100644
--- a/be/src/storage/index/inverted/reader/collection_statistics.cpp
+++ b/be/src/storage/index/inverted/reader/collection_statistics.cpp
@@ -22,6 +22,7 @@
#include <iterator>
#include <set>
#include <sstream>
+#include <unordered_set>
#include "common/exception.h"
#include "core/column/column_vector.h"
@@ -40,6 +41,7 @@
#include "storage/index/inverted/clucene/spi/clucene_index_source.h"
#include "storage/index/inverted/common/inverted_index_cache.h"
#include "storage/index/inverted/common/string_helper.h"
+#include "storage/index/inverted/query/exec/term_pattern.h"
#include "storage/index/inverted/snii/reader/snii_index_source.h"
#include "storage/index/inverted/snii/snii_doris_adapter.h"
#include "storage/iterators.h"
@@ -116,6 +118,65 @@ void add_term_doc_frequency(
(*logical_frequencies)[field][logical_term] += doc_frequency;
}
+Status segment_scoring_terms(index_query::IndexSource& source, const
CollectInfo& collect_info,
+ const VisibleDocFreq& visible_doc_freq,
+ FieldPrefixExpansions* expansions,
std::vector<std::string>* terms) {
+ DORIS_CHECK(expansions != nullptr);
+ DORIS_CHECK(terms != nullptr);
+ *terms = collect_info.unique_terms;
+ std::unordered_set<std::string> listed(terms->begin(), terms->end());
+ for (const auto& scoring_prefix : collect_info.scoring_prefixes) {
+ index_query::TermPattern pattern;
+
RETURN_IF_ERROR(index_query::TermPattern::create(index_query::TermPatternKind::kPrefix,
+
scoring_prefix.prefix, &pattern));
+ const auto wanted = static_cast<size_t>(scoring_prefix.max_expansions);
+ std::vector<std::string> visible;
+ for (int32_t limit = scoring_prefix.max_expansions;; limit *= 2) {
+ std::vector<std::string> expanded;
+ RETURN_IF_ERROR(source.expand_terms(pattern, limit, &expanded));
+ visible.clear();
+ for (auto& term : expanded) {
+ // The statistics are keyed by wide string, and
StringHelper::to_wstring drops the
+ // bytes that are not valid UTF-8, which SNII keeps in a
token. Two such terms,
+ // "ra\xFF" and "ra\xFE", would share the key "ra" and add
their document
+ // frequencies up, to more than the documents of the tablet
and a negative idf. A
+ // term without a key of its own is not scored, and takes no
place.
+ if (segment_v2::inverted_index::StringHelper::to_string(
+
segment_v2::inverted_index::StringHelper::to_wstring(term)) != term) {
+ continue;
+ }
+ uint64_t doc_freq = 0;
+ RETURN_IF_ERROR(visible_doc_freq(term, &doc_freq));
+ if (doc_freq > 0) {
+ visible.push_back(std::move(term));
+ }
+ }
+ // The dictionary ran out of terms, or the first `wanted` visible
ones are found.
+ if (expanded.size() < static_cast<size_t>(limit) || visible.size()
>= wanted) {
+ break;
+ }
+ }
+ // A read with doubled limit can find more visible terms than the
prefix keeps; the
+ // dictionary order puts the ones to keep first.
+ if (visible.size() > wanted) {
+ visible.resize(wanted);
+ }
+ auto& prefix_terms =
+ expansions
+
->try_emplace(segment_v2::inverted_index::StringHelper::to_wstring(
+ scoring_prefix.prefix),
+ scoring_prefix.max_expansions)
+ .first->second;
+ for (auto& term : visible) {
+
prefix_terms.insert(segment_v2::inverted_index::StringHelper::to_wstring(term));
+ if (listed.insert(term).second) {
+ terms->push_back(std::move(term));
+ }
+ }
+ }
+ return Status::OK();
+}
+
Status sum_non_null_norm_lengths(index_query::IndexSource& source,
std::span<const uint32_t> null_docs,
uint64_t* out) {
if (!null_docs.empty() && null_docs.back() >= source.doc_count()) {
@@ -192,6 +253,24 @@ Status exclude_hidden_term_docs(index_query::IndexSource&
source, std::string_vi
return Status::OK();
}
+VisibleDocFreq cached_visible_doc_freq(index_query::IndexSource& source,
+ std::span<const uint32_t> hidden_docs) {
+ auto cache = std::make_shared<std::unordered_map<std::string, uint64_t>>();
+ return [&source, hidden_docs, cache](const std::string& term,
+ uint64_t* doc_frequency) -> Status {
+ if (const auto cached = cache->find(term); cached != cache->end()) {
+ *doc_frequency = cached->second;
+ return Status::OK();
+ }
+ RETURN_IF_ERROR(source.scoring_doc_freq(term, doc_frequency));
+ if (!hidden_docs.empty()) {
+ RETURN_IF_ERROR(exclude_hidden_term_docs(source, term,
hidden_docs, doc_frequency));
+ }
+ cache->emplace(term, *doc_frequency);
+ return Status::OK();
+ };
+}
+
} // namespace collection_statistics_detail
namespace {
@@ -519,15 +598,18 @@ Status CollectionStatistics::process_segment(const
RowsetSharedPtr& rowset, int6
segment_v2::inverted_index::InvertedIndexAnalyzer::should_analyzer(
collect_info.index_meta->properties())));
- for (const auto& logical_term_bytes : collect_info.unique_terms) {
+ // The document frequency of a term in this segment, without its
hidden rows.
+ const auto visible_doc_freq =
+
collection_statistics_detail::cached_visible_doc_freq(source, hidden_docs);
+ std::vector<std::string> segment_terms;
+
RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
+ source, collect_info, visible_doc_freq,
+ &segment_accumulator.prefix_expansions[ws_field_name],
&segment_terms));
+ for (const auto& logical_term_bytes : segment_terms) {
const auto logical_term =
segment_v2::inverted_index::StringHelper::to_wstring(logical_term_bytes);
uint64_t doc_frequency = 0;
- RETURN_IF_ERROR(source.scoring_doc_freq(logical_term_bytes,
&doc_frequency));
- if (!hidden_docs.empty()) {
-
RETURN_IF_ERROR(collection_statistics_detail::exclude_hidden_term_docs(
- source, logical_term_bytes, hidden_docs,
&doc_frequency));
- }
+ RETURN_IF_ERROR(visible_doc_freq(logical_term_bytes,
&doc_frequency));
if (doc_frequency > segment_doc_count) {
return
Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED>(
"SNII term document frequency {} exceeds segment
document count {}",
@@ -651,15 +733,18 @@ Status CollectionStatistics::process_segment(const
RowsetSharedPtr& rowset, int6
_total_num_tokens[ws_field_name] +=
scoring_stats.has_norms ? scoring_stats.token_count :
scoring_stats.doc_count;
- for (const auto& logical_term_bytes : collect_info.unique_terms) {
+ // The document frequency of a term in this segment, without its
hidden rows.
+ const auto visible_doc_freq =
+ collection_statistics_detail::cached_visible_doc_freq(*source,
hidden_docs);
+ std::vector<std::string> segment_terms;
+ RETURN_IF_ERROR(collection_statistics_detail::segment_scoring_terms(
+ *source, collect_info, visible_doc_freq,
&_prefix_expansions[ws_field_name],
+ &segment_terms));
+ for (const auto& logical_term_bytes : segment_terms) {
const auto logical_term =
segment_v2::inverted_index::StringHelper::to_wstring(logical_term_bytes);
uint64_t doc_frequency = 0;
- RETURN_IF_ERROR(source->scoring_doc_freq(logical_term_bytes,
&doc_frequency));
- if (!hidden_docs.empty()) {
-
RETURN_IF_ERROR(collection_statistics_detail::exclude_hidden_term_docs(
- *source, logical_term_bytes, hidden_docs,
&doc_frequency));
- }
+ RETURN_IF_ERROR(visible_doc_freq(logical_term_bytes,
&doc_frequency));
collection_statistics_detail::add_term_doc_frequency(&_term_doc_freqs,
ws_field_name,
logical_term,
doc_frequency);
}
@@ -706,6 +791,16 @@ void CollectionStatistics::commit_snii_scoring_segment(
_term_doc_freqs[field_name][term] += doc_freq;
}
}
+ for (const auto& [field_name, prefixes] :
segment_accumulator.prefix_expansions) {
+ for (const auto& [prefix, expansion] : prefixes) {
+ auto& merged = _prefix_expansions[field_name]
+ .try_emplace(prefix, expansion.limit())
+ .first->second;
+ for (const auto& term : expansion.terms()) {
+ merged.insert(term);
+ }
+ }
+ }
_total_num_docs += segment_accumulator.doc_count;
_avg_dl_by_col.clear();
_idf_by_col_term.clear();
@@ -716,6 +811,7 @@ void CollectionStatistics::clear() {
_counted_hidden_docs = false;
_total_num_tokens.clear();
_term_doc_freqs.clear();
+ _prefix_expansions.clear();
_avg_dl_by_col.clear();
_idf_by_col_term.clear();
}
@@ -725,6 +821,7 @@ void CollectionStatistics::copy_collected_from(const
CollectionStatistics& other
_counted_hidden_docs = other._counted_hidden_docs;
_total_num_tokens = other._total_num_tokens;
_term_doc_freqs = other._term_doc_freqs;
+ _prefix_expansions = other._prefix_expansions;
_avg_dl_by_col.clear();
_idf_by_col_term.clear();
}
@@ -804,6 +901,22 @@ float CollectionStatistics::get_or_calculate_avg_dl(const
std::wstring& lucene_c
return avg_dl;
}
+std::vector<std::wstring> CollectionStatistics::get_prefix_expansions(
+ const std::wstring& lucene_col_name, const std::wstring& prefix) {
+ const auto field = _prefix_expansions.find(lucene_col_name);
+ if (field == _prefix_expansions.end()) {
+ return {};
+ }
+ const auto expansions = field->second.find(prefix);
+ if (expansions == field->second.end()) {
+ return {};
+ }
+ // Only terms that a returned row holds were expanded to
(segment_scoring_terms), so each has
+ // a document frequency.
+ const auto& terms = expansions->second.terms();
+ return std::vector<std::wstring>(terms.begin(), terms.end());
+}
+
float CollectionStatistics::get_or_calculate_idf(const std::wstring&
lucene_col_name,
const std::wstring& term) {
auto iter = _idf_by_col_term.find(lucene_col_name);
diff --git a/be/src/storage/index/inverted/reader/collection_statistics.h
b/be/src/storage/index/inverted/reader/collection_statistics.h
index 18b81312ce2..7f842e88be2 100644
--- a/be/src/storage/index/inverted/reader/collection_statistics.h
+++ b/be/src/storage/index/inverted/reader/collection_statistics.h
@@ -19,8 +19,10 @@
#include <condition_variable>
#include <cstdint>
#include <functional>
+#include <iterator>
#include <mutex>
#include <optional>
+#include <set>
#include <span>
#include <string>
#include <string_view>
@@ -81,6 +83,37 @@ struct MowHiddenRows {
bool use_page_cache = true;
};
+// The `limit` smallest terms, in dictionary order, that a prefix expanded to
in the segments seen
+// so far: the terms an index-wide expansion of Lucene would take. A term only
enters or stays
+// while fewer than `limit` smaller terms are known, and one dropped never
returns, whatever
+// order the segments come in.
+//
+// That is what keeps the document frequencies whole. A term of the final set
has fewer than
+// `limit` smaller terms in every segment holding it, so each of those
segments expanded to it
+// and counted its documents. With a limit of 1, segment A holding {rose} and
segment B holding
+// {red, rose} leave {red}: B's expansion is red alone, but rose is not
scored, so its document
+// frequency, which only A counted, is not used.
+class PrefixExpansionSet {
+public:
+ explicit PrefixExpansionSet(int32_t limit) : _limit(limit) {
DORIS_CHECK_GT(limit, 0); }
+
+ void insert(const std::wstring& term) {
+ _terms.insert(term);
+ if (_terms.size() > static_cast<size_t>(_limit)) {
+ _terms.erase(std::prev(_terms.end()));
+ }
+ }
+
+ int32_t limit() const { return _limit; }
+ const std::set<std::wstring>& terms() const { return _terms; }
+
+private:
+ int32_t _limit;
+ std::set<std::wstring> _terms;
+};
+// The terms each prefix expanded to, by prefix.
+using FieldPrefixExpansions = std::unordered_map<std::wstring,
PrefixExpansionSet>;
+
class CollectionStatistics {
public:
explicit CollectionStatistics(PredicateCollectorPtr search_collector =
nullptr)
@@ -106,15 +139,25 @@ public:
const std::wstring& term);
MOCK_FUNCTION float get_or_calculate_avg_dl(const std::wstring&
lucene_col_name);
+ // The terms the collected `prefix` expanded to in any segment of the
tablet and that some
+ // returned row holds, in dictionary order; their idfs are in
get_or_calculate_idf. None for a
+ // prefix that was not collected, as for a SEARCH predicate.
+ MOCK_FUNCTION std::vector<std::wstring> get_prefix_expansions(
+ const std::wstring& lucene_col_name, const std::wstring& prefix);
+
// Replaces the collected counters with those of `other`. The derived
idf/avgdl caches are
// reset rather than copied, so the copy can be used by another thread
without sharing them.
void copy_collected_from(const CollectionStatistics& other);
private:
+ // The terms each collected prefix expanded to, by field and prefix.
+ using PrefixExpansions = std::unordered_map<std::wstring,
FieldPrefixExpansions>;
+
struct SniiScoringSegmentAccumulator {
uint64_t doc_count = 0;
std::unordered_map<std::wstring, uint64_t> token_counts;
std::unordered_map<std::wstring, std::unordered_map<std::wstring,
uint64_t>> term_doc_freqs;
+ PrefixExpansions prefix_expansions;
};
Status extract_collect_info(RuntimeState* state,
@@ -143,6 +186,7 @@ private:
bool _counted_hidden_docs = false;
std::unordered_map<std::wstring, uint64_t> _total_num_tokens;
std::unordered_map<std::wstring, std::unordered_map<std::wstring,
uint64_t>> _term_doc_freqs;
+ PrefixExpansions _prefix_expansions;
std::unordered_map<std::wstring, float> _avg_dl_by_col;
std::unordered_map<std::wstring, std::unordered_map<std::wstring, float>>
_idf_by_col_term;
@@ -229,10 +273,40 @@ Status exclude_hidden_docs(std::span<const uint32_t>
hidden_docs, const roaring:
const SumNormLengthsOf& sum_norm_lengths_of,
index_query::IndexScoringStats* stats);
+// The terms whose document frequencies a segment adds for `collect_info`: its
scoring terms, then
+// each term its prefixes expand to in `source`, so that a phrase prefix is
scored on the same
+// tablet statistics as the other terms. A term met twice is listed once, as
its documents count
+// once. The terms each prefix expands to in this segment are added to
`expansions`, which keeps
+// the smallest ones of the segments seen (PrefixExpansionSet).
+//
+// Only terms that a returned row holds are expanded to, as `visible_doc_freq`
tells: the document
+// frequency of a term in this segment without its hidden rows. A term held by
hidden rows alone
+// must not take one of the `max_expansions` places, or the scores of the same
visible rows would
+// change when a compaction drops the hidden rows. With a limit of 1, and `ra`
held by hidden rows
+// and `rb` by visible ones, the prefix "r" expands to rb before and after the
compaction.
+// The dictionary is therefore read again, with twice the limit, while it
still has terms and the
+// terms found hold fewer than `max_expansions` visible ones. A term whose
bytes are not valid UTF-8
+// has no wide-string key of its own and is skipped like a hidden one.
+//
+// Example: "red r" collects red and, in a segment holding red, rose and run,
the terms red (already
+// listed), rose and run, and records {red, rose, run} for the prefix "r".
+using VisibleDocFreq = std::function<Status(const std::string& term, uint64_t*
doc_freq)>;
+Status segment_scoring_terms(index_query::IndexSource& source, const
CollectInfo& collect_info,
+ const VisibleDocFreq& visible_doc_freq,
+ FieldPrefixExpansions* expansions,
std::vector<std::string>* terms);
+
// Takes from a term's document frequency the documents of `hidden_docs` that
hold it.
Status exclude_hidden_term_docs(index_query::IndexSource& source,
std::string_view term,
std::span<const uint32_t> hidden_docs,
uint64_t* doc_frequency);
+// The document frequency of a term in `source` without the rows of
`hidden_docs`, computed once
+// per term for the lifetime of the returned function. With hidden rows every
term costs an
+// intersection of its postings with them, and the terms a prefix expands to
are asked for twice:
+// to choose the ones to keep, and to add up the frequencies of the ones kept.
+// `source` and `hidden_docs` must outlive the function.
+VisibleDocFreq cached_visible_doc_freq(index_query::IndexSource& source,
+ std::span<const uint32_t> hidden_docs);
+
} // namespace collection_statistics_detail
#include "common/compile_check_end.h"
diff --git a/be/src/storage/index/inverted/reader/predicate_collector.cpp
b/be/src/storage/index/inverted/reader/predicate_collector.cpp
index 615c8fc7b33..376e7af5604 100644
--- a/be/src/storage/index/inverted/reader/predicate_collector.cpp
+++ b/be/src/storage/index/inverted/reader/predicate_collector.cpp
@@ -19,6 +19,8 @@
#include <glog/logging.h>
+#include <algorithm>
+#include <optional>
#include <vector>
#include "common/exception.h"
@@ -31,6 +33,7 @@
#include "storage/index/index_reader_helper.h"
#include "storage/index/inverted/analysis/analyzer/analyzer.h"
#include "storage/index/inverted/common/string_helper.h"
+#include "storage/index/inverted/query/exec/term_pattern.h"
#include "storage/index/inverted/reader/inverted_index_selector.h"
#include "storage/tablet/tablet_schema.h"
#include "storage/utils.h"
@@ -116,6 +119,21 @@ Status append_scoring_leaf(CollectInfo* collect_info,
const std::vector<TermInfo
return Status::OK();
}
+void append_scoring_prefix(CollectInfo* collect_info, const TermInfo& prefix,
+ int32_t max_expansions) {
+ DORIS_CHECK(collect_info != nullptr);
+ DORIS_CHECK(prefix.is_single_term());
+ const auto& text = prefix.get_single_term();
+ const bool known = std::ranges::any_of(
+ collect_info->scoring_prefixes, [&](const LogicalScoringPrefix&
registered) {
+ return registered.prefix == text && registered.max_expansions
== max_expansions;
+ });
+ if (!known) {
+ collect_info->scoring_prefixes.push_back(
+ LogicalScoringPrefix {.prefix = text, .max_expansions =
max_expansions});
+ }
+}
+
InvertedIndexQueryType match_query_type(TExprOpcode::type opcode) {
switch (opcode) {
case TExprOpcode::MATCH_ANY:
@@ -356,7 +374,13 @@ Status MatchPredicateCollector::collect(RuntimeState*
state, const TabletSchemaS
auto options = DataTypeSerDe::get_default_format_options();
options.timezone = &state->timezone_obj();
auto term_infos =
DORIS_TRY(analyze_plain_query(right_literal->value(options), *analyzer_ctx));
+ // The prefix of a phrase prefix is scored by the terms it expands to, so
the statistics are
+ // collected for them per segment; a prefix alone scores a constant and
needs none.
+ std::optional<TermInfo> scoring_prefix;
if (expr->op() == TExprOpcode::MATCH_PHRASE_PREFIX && !term_infos.empty())
{
+ if (term_infos.size() > 1) {
+ scoring_prefix = term_infos.back();
+ }
term_infos.pop_back();
}
@@ -369,11 +393,20 @@ Status MatchPredicateCollector::collect(RuntimeState*
state, const TabletSchemaS
CollectInfo collect_info;
RETURN_IF_ERROR(append_scoring_leaf(&collect_info, term_infos));
preserve_selected_index_metadata(candidates, index_meta,
&collect_info);
- (*collect_infos)[ws_field_name] = std::move(collect_info);
+ iter = collect_infos->emplace(ws_field_name,
std::move(collect_info)).first;
} else {
RETURN_IF_ERROR(validate_same_physical_index(iter->second,
*index_meta));
RETURN_IF_ERROR(append_scoring_leaf(&iter->second, term_infos));
}
+ if (scoring_prefix.has_value()) {
+ // The terms of a prefix are kept for the whole scan and copied to
every scanner, so their
+ // number is bounded. Under a session limit of 0, which expands a
prefix to every term,
+ // "quick b" would keep the whole vocabulary starting with b, and a
sum of thousands of
+ // idfs ranks nothing; the default limit scores it instead.
+ const int32_t session_limit = index_query::max_expansions(state);
+ append_scoring_prefix(&iter->second, *scoring_prefix,
+ session_limit > 0 ? session_limit :
kDefaultScoringExpansions);
+ }
return Status::OK();
}
diff --git a/be/src/storage/index/inverted/reader/predicate_collector.h
b/be/src/storage/index/inverted/reader/predicate_collector.h
index 5adf3f7432c..77dd6c26163 100644
--- a/be/src/storage/index/inverted/reader/predicate_collector.h
+++ b/be/src/storage/index/inverted/reader/predicate_collector.h
@@ -56,9 +56,20 @@ struct LogicalScoringLeaf {
std::vector<LogicalScoringClause> clauses;
};
+// The number of terms a scored phrase prefix expands to when the session sets
no limit.
+inline constexpr int32_t kDefaultScoringExpansions = 50;
+
+// The last term of a scored phrase prefix, whose idf is the sum of the idfs
of the smallest
+// `max_expansions` terms it expands to over the tablet, which is positive.
+struct LogicalScoringPrefix {
+ std::string prefix;
+ int32_t max_expansions = kDefaultScoringExpansions;
+};
+
struct CollectInfo {
std::vector<std::string> unique_terms;
std::unordered_map<std::string, uint32_t> unique_term_slots;
+ std::vector<LogicalScoringPrefix> scoring_prefixes;
std::vector<LogicalScoringLeaf> logical_scoring_leaves;
std::shared_ptr<const TabletIndex> owned_index_meta;
const TabletIndex* index_meta = nullptr;
@@ -78,6 +89,9 @@ Result<std::vector<segment_v2::TermInfo>> analyze_plain_query(
const std::string& value, const InvertedIndexAnalyzerCtx&
analyzer_ctx);
Status append_scoring_leaf(CollectInfo* collect_info,
const std::vector<segment_v2::TermInfo>&
term_infos);
+// Registers the prefix of a scored phrase prefix once, however many
predicates repeat it.
+void append_scoring_prefix(CollectInfo* collect_info, const
segment_v2::TermInfo& prefix,
+ int32_t max_expansions);
Result<const TabletIndex*> select_index_meta(const std::vector<const
TabletIndex*>& index_metas,
FieldType field_type,
segment_v2::InvertedIndexQueryType query_type,
diff --git
a/be/test/storage/index/inverted/query/engine/phrase_prefix_query_test.cpp
b/be/test/storage/index/inverted/query/engine/phrase_prefix_query_test.cpp
index b2bc9aee74b..c39ecc840ed 100644
--- a/be/test/storage/index/inverted/query/engine/phrase_prefix_query_test.cpp
+++ b/be/test/storage/index/inverted/query/engine/phrase_prefix_query_test.cpp
@@ -21,11 +21,14 @@
#include <gtest/gtest.h>
#include <sys/resource.h>
+#include <algorithm>
#include <array>
+#include <cmath>
#include <memory>
#include <roaring/roaring.hh>
#include <set>
#include <string>
+#include <vector>
#include "io/fs/local_file_system.h"
#include "runtime/runtime_state.h"
@@ -36,6 +39,7 @@
#include "storage/index/inverted/common/string_helper.h"
#include "storage/index/inverted/query/engine/expand_query/expand_weight.h"
#include "storage/index/inverted/query/scoring/collection_similarity.h"
+#include "storage/index/inverted/query/spi/index_source.h"
#include "storage/index/inverted/reader/collection_statistics.h"
CL_NS_USE(store)
@@ -384,6 +388,269 @@ TEST_F(PhrasePrefixQueryV2Test, scorer_with_scoring) {
_CLDECDELETE(dir);
}
+// --- PhrasePrefixWeight scorer: the expanded terms count in the idf ---
+
+// "quick bro" expands to brother and brown, "quick brot" to brother alone: a
document holding
+// "quick brother" scores on the idf of the phrase terms plus that of every
term the prefix expands
+// to, all of them from the statistics of the tablet. Those statistics
describe 1000 documents
+// where the segment holds 20, so an idf read from the segment would differ.
+TEST_F(PhrasePrefixQueryV2Test, prefix_expansions_add_their_idf_to_the_score) {
+ auto ctx = std::make_shared<IndexQueryContext>();
+ ctx->collection_statistics = std::make_shared<CollectionStatistics>();
+ ctx->collection_similarity = std::make_shared<CollectionSimilarity>();
+
+ auto* dir = FSDirectory::getDirectory(kTestDir.c_str());
+ auto reader = make_shared_reader(lucene::index::IndexReader::open(dir,
true));
+ const std::wstring field = StringHelper::to_wstring("content");
+ auto& stats = *ctx->collection_statistics;
+ stats._total_num_docs = 1000;
+ stats._total_num_tokens[field] = 8000;
+ stats._term_doc_freqs[field][StringHelper::to_wstring("quick")] = 100;
+ stats._term_doc_freqs[field][StringHelper::to_wstring("brother")] = 3;
+ stats._term_doc_freqs[field][StringHelper::to_wstring("brown")] = 400;
+ auto& bro = stats._prefix_expansions[field]
+ .try_emplace(StringHelper::to_wstring("bro"), 50)
+ .first->second;
+ bro.insert(StringHelper::to_wstring("brother"));
+ bro.insert(StringHelper::to_wstring("brown"));
+ stats._prefix_expansions[field]
+ .try_emplace(StringHelper::to_wstring("brot"), 50)
+ .first->second.insert(StringHelper::to_wstring("brother"));
+
+ const auto score_of_brother = [&](const std::string& prefix) {
+ PhrasePrefixQuery q(ctx, field, make_term_infos({"quick", prefix}));
+ auto w = q.weight(true);
+ QueryExecutionContext exec_ctx;
+ exec_ctx.segment_num_rows = reader->maxDoc();
+ exec_ctx.field_sources.emplace(field, clucene_index_source(reader,
field, nullptr));
+ auto scorer = w->scorer(exec_ctx, "");
+ EXPECT_EQ(scorer->seek(10), 10);
+ return scorer->score();
+ };
+ const auto idf = [&](const std::string& term) {
+ return stats.get_or_calculate_idf(field,
StringHelper::to_wstring(term));
+ };
+ const float avgdl = stats.get_or_calculate_avg_dl(field);
+
+ BM25Similarity brother_only(idf("quick") + idf("brother"), avgdl);
+ BM25Similarity brother_and_brown(idf("quick") + idf("brother") +
idf("brown"), avgdl);
+ // The document holds the phrase once and the source reports no norms.
+ EXPECT_FLOAT_EQ(score_of_brother("brot"), brother_only.score(1.0F, 1));
+ EXPECT_FLOAT_EQ(score_of_brother("bro"), brother_and_brown.score(1.0F, 1));
+ EXPECT_GT(score_of_brother("bro"), score_of_brother("brot"));
+
+ _CLDECDELETE(dir);
+}
+
+// A statistics object that collected no expansion of the prefix, as for a
SEARCH predicate, scores
+// the phrase terms alone.
+TEST_F(PhrasePrefixQueryV2Test,
prefix_without_collected_expansions_scores_the_phrase_terms) {
+ auto ctx = std::make_shared<IndexQueryContext>();
+ ctx->collection_statistics = std::make_shared<CollectionStatistics>();
+ ctx->collection_similarity = std::make_shared<CollectionSimilarity>();
+
+ auto* dir = FSDirectory::getDirectory(kTestDir.c_str());
+ auto reader = make_shared_reader(lucene::index::IndexReader::open(dir,
true));
+ const std::wstring field = StringHelper::to_wstring("content");
+ auto& stats = *ctx->collection_statistics;
+ stats._total_num_docs = 1000;
+ stats._total_num_tokens[field] = 8000;
+ stats._term_doc_freqs[field][StringHelper::to_wstring("quick")] = 100;
+
+ PhrasePrefixQuery q(ctx, field, make_term_infos({"quick", "bro"}));
+ auto w = q.weight(true);
+ QueryExecutionContext exec_ctx;
+ exec_ctx.segment_num_rows = reader->maxDoc();
+ exec_ctx.field_sources.emplace(field, clucene_index_source(reader, field,
nullptr));
+ auto scorer = w->scorer(exec_ctx, "");
+ ASSERT_EQ(scorer->seek(10), 10);
+
+ BM25Similarity quick_only(stats.get_or_calculate_idf(field,
StringHelper::to_wstring("quick")),
+ stats.get_or_calculate_avg_dl(field));
+ EXPECT_FLOAT_EQ(scorer->score(), quick_only.score(1.0F, 1));
+
+ _CLDECDELETE(dir);
+}
+
+// --- segment statistics: the terms a prefix expands to ---
+
+// "quick bro" collects quick, then the terms of the segment starting with
bro. A term the scoring
+// terms already hold is listed once, and each prefix keeps the terms it
expanded to.
+TEST_F(PhrasePrefixQueryV2Test,
segment_statistics_count_the_terms_a_prefix_expands_to) {
+ auto* dir = FSDirectory::getDirectory(kTestDir.c_str());
+ auto reader = make_shared_reader(lucene::index::IndexReader::open(dir,
true));
+ const std::wstring field = StringHelper::to_wstring("content");
+ auto source = clucene_index_source(reader, field, nullptr);
+
+ CollectInfo collect_info;
+ TermInfo quick;
+ quick.term = std::string("quick");
+ ASSERT_TRUE(scoring_collection_detail::append_scoring_leaf(&collect_info,
{quick}).ok());
+ TermInfo bro;
+ bro.term = std::string("bro");
+ scoring_collection_detail::append_scoring_prefix(&collect_info, bro, 50);
+ TermInfo quic;
+ quic.term = std::string("quic");
+ scoring_collection_detail::append_scoring_prefix(&collect_info, quic, 50);
+
+ FieldPrefixExpansions expansions;
+ std::vector<std::string> terms;
+ const collection_statistics_detail::VisibleDocFreq doc_freq =
[&source](const std::string& term,
+
uint64_t* out) {
+ return source->doc_freq(term, out);
+ };
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(*source,
collect_info, doc_freq,
+
&expansions, &terms)
+ .ok());
+ // quick is held twice, as a scoring term and as an expansion of quic, and
listed once.
+ EXPECT_EQ(terms, (std::vector<std::string> {"quick", "brother", "brown",
"quickly"}));
+ EXPECT_EQ(expansions.at(StringHelper::to_wstring("bro")).terms(),
+ (std::set<std::wstring> {StringHelper::to_wstring("brother"),
+ StringHelper::to_wstring("brown")}));
+ EXPECT_EQ(expansions.at(StringHelper::to_wstring("quic")).terms(),
+ (std::set<std::wstring> {StringHelper::to_wstring("quick"),
+ StringHelper::to_wstring("quickly")}));
+
+ // At most max_expansions terms of the dictionary, in order.
+ CollectInfo limited;
+ scoring_collection_detail::append_scoring_prefix(&limited, bro, 1);
+ expansions.clear();
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(*source,
limited, doc_freq,
+
&expansions, &terms)
+ .ok());
+ EXPECT_EQ(terms, (std::vector<std::string> {"brother"}));
+
+ // A term held by hidden rows alone has no visible document and takes no
place: with a limit
+ // of 1 the prefix expands to brown, the next term, and the same after the
hidden rows are
+ // compacted away. All terms hidden leaves nothing, however far the
dictionary is read.
+ const auto brother_hidden = [&source](const std::string& term, uint64_t*
out) {
+ RETURN_IF_ERROR(source->doc_freq(term, out));
+ if (term == "brother") {
+ *out = 0;
+ }
+ return Status::OK();
+ };
+ expansions.clear();
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(
+ *source, limited, brother_hidden, &expansions, &terms)
+ .ok());
+ EXPECT_EQ(terms, (std::vector<std::string> {"brown"}));
+ EXPECT_EQ(expansions.at(StringHelper::to_wstring("bro")).terms(),
+ std::set<std::wstring> {StringHelper::to_wstring("brown")});
+
+ const auto all_hidden = [](const std::string&, uint64_t* out) {
+ *out = 0;
+ return Status::OK();
+ };
+ expansions.clear();
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(*source,
limited, all_hidden,
+
&expansions, &terms)
+ .ok());
+ EXPECT_TRUE(terms.empty());
+
EXPECT_TRUE(expansions.at(StringHelper::to_wstring("bro")).terms().empty());
+
+ _CLDECDELETE(dir);
+}
+
+namespace {
+
+// A dictionary alone: it lists the terms that start with a prefix, in byte
order.
+class DictionaryOnlySource final : public index_query::IndexSource {
+public:
+ explicit DictionaryOnlySource(std::vector<std::string> terms) :
_terms(std::move(terms)) {
+ std::ranges::sort(_terms);
+ }
+
+ uint32_t doc_count() const override { return 1; }
+
+ Status open_term(std::string_view, bool, bool,
+ std::unique_ptr<index_query::PostingsCursor>* out)
override {
+ out->reset();
+ return Status::OK();
+ }
+
+ // Every term is held by 3 documents; the calls are counted.
+ Status doc_freq(std::string_view, uint64_t* out) override {
+ ++doc_freq_calls;
+ *out = 3;
+ return Status::OK();
+ }
+
+ int doc_freq_calls = 0;
+
+ Status expand_terms(index_query::TermPattern&, int32_t max_expansions,
+ std::vector<std::string>* out) override {
+ out->clear();
+ for (const auto& term : _terms) {
+ if (max_expansions > 0 && out->size() ==
static_cast<size_t>(max_expansions)) {
+ break;
+ }
+ out->push_back(term);
+ }
+ return Status::OK();
+ }
+
+private:
+ std::vector<std::string> _terms;
+};
+
+} // namespace
+
+// SNII keeps the bytes of a token as they are, so its dictionary can hold
terms that are not valid
+// UTF-8. StringHelper::to_wstring drops those bytes, and "ra\xFF" and
"ra\xFE" would both get the
+// key "ra" and add their document frequencies up, to more than the documents
of the tablet. Such
+// terms are not scored and take no place: with a limit of 2 the prefix
expands to rb and rc.
+TEST_F(PhrasePrefixQueryV2Test,
segment_statistics_skip_terms_without_a_wide_string_key) {
+ DictionaryOnlySource source({"ra\xFF", "ra\xFE", "rb", "rc", "rd"});
+ CollectInfo collect_info;
+ TermInfo r;
+ r.term = std::string("r");
+ scoring_collection_detail::append_scoring_prefix(&collect_info, r, 2);
+
+ const collection_statistics_detail::VisibleDocFreq one_document = [](const
std::string&,
+
uint64_t* out) {
+ *out = 1;
+ return Status::OK();
+ };
+ FieldPrefixExpansions expansions;
+ std::vector<std::string> terms;
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(
+ source, collect_info, one_document, &expansions,
&terms)
+ .ok());
+ EXPECT_EQ(terms, (std::vector<std::string> {"rb", "rc"}));
+ EXPECT_EQ(expansions.at(StringHelper::to_wstring("r")).terms(),
+ (std::set<std::wstring> {StringHelper::to_wstring("rb"),
+ StringHelper::to_wstring("rc")}));
+}
+
+// With hidden rows every document frequency costs an intersection of the
term's postings with
+// them. The terms a prefix expands to are asked for twice, to choose the ones
kept and to add up
+// their frequencies, and the intersection is made once.
+TEST_F(PhrasePrefixQueryV2Test,
visible_document_frequencies_are_computed_once_per_term) {
+ DictionaryOnlySource source({"rb", "rc"});
+ const auto doc_freq =
collection_statistics_detail::cached_visible_doc_freq(source, {});
+
+ CollectInfo collect_info;
+ TermInfo r;
+ r.term = std::string("r");
+ scoring_collection_detail::append_scoring_prefix(&collect_info, r, 2);
+ FieldPrefixExpansions expansions;
+ std::vector<std::string> terms;
+ ASSERT_TRUE(collection_statistics_detail::segment_scoring_terms(source,
collect_info, doc_freq,
+
&expansions, &terms)
+ .ok());
+ ASSERT_EQ(terms, (std::vector<std::string> {"rb", "rc"}));
+ EXPECT_EQ(source.doc_freq_calls, 2);
+
+ // The final count asks for the same terms again.
+ for (const auto& term : terms) {
+ uint64_t frequency = 0;
+ ASSERT_TRUE(doc_freq(term, &frequency).ok());
+ EXPECT_EQ(frequency, 3U);
+ }
+ EXPECT_EQ(source.doc_freq_calls, 2);
+}
+
// --- PhrasePrefixWeight scorer: nullable branch ---
TEST_F(PhrasePrefixQueryV2Test, scorer_nullable) {
diff --git
a/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
b/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
index 436063235c3..afabc73b9d7 100644
--- a/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
+++ b/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
@@ -2612,7 +2612,7 @@ TEST_F(CollectionStatisticsTest,
CollectUsesMatchRequestAnalyzerProvider) {
EXPECT_EQ(collect_info.logical_scoring_leaves[0].clauses[1].df_slot, 1u);
}
-TEST_F(CollectionStatisticsTest, CollectPhrasePrefixExcludesScoringTail) {
+TEST_F(CollectionStatisticsTest,
CollectPhrasePrefixRegistersTheTailForExpansion) {
auto tablet_schema = create_tablet_schema_with_inverted_index();
auto match_expr =
std::make_shared<collection_statistics::MockVExpr>(TExprNodeType::MATCH_PRED);
match_expr->set_opcode(TExprOpcode::MATCH_PHRASE_PREFIX);
@@ -2634,6 +2634,60 @@ TEST_F(CollectionStatisticsTest,
CollectPhrasePrefixExcludesScoringTail) {
ASSERT_EQ(collect_info.logical_scoring_leaves[0].clauses.size(), 2u);
EXPECT_EQ(collect_info.logical_scoring_leaves[0].clauses[0].position, 1);
EXPECT_EQ(collect_info.logical_scoring_leaves[0].clauses[1].position, 2);
+ // The tail is no scoring term: segments expand it, and the terms it
expands to are scored.
+ ASSERT_EQ(collect_info.scoring_prefixes.size(), 1u);
+ EXPECT_EQ(collect_info.scoring_prefixes[0].prefix, "gamma");
+ EXPECT_EQ(collect_info.scoring_prefixes[0].max_expansions, 50);
+}
+
+TEST_F(CollectionStatisticsTest,
+ CollectPhrasePrefixUnderNoSessionLimitScoresTheDefaultNumberOfTerms) {
+ TQueryOptions query_options;
+ query_options.inverted_index_max_expansions = 0;
+ runtime_state_->set_query_options(query_options);
+ auto tablet_schema = create_tablet_schema_with_inverted_index();
+ auto match_expr =
std::make_shared<collection_statistics::MockVExpr>(TExprNodeType::MATCH_PRED);
+ match_expr->set_opcode(TExprOpcode::MATCH_PHRASE_PREFIX);
+ match_expr->_children.push_back(
+ std::make_shared<collection_statistics::MockVSlotRef>("content",
SlotId(1)));
+ match_expr->_children.push_back(
+ std::make_shared<collection_statistics::MockVLiteral>("alpha
gamma"));
+
+ MatchPredicateCollector collector;
+ CollectInfoMap collect_infos;
+ auto status =
+ collector.collect(runtime_state_.get(), tablet_schema, match_expr,
&collect_infos);
+
+ ASSERT_TRUE(status.ok()) << status.msg();
+ const auto& collect_info = collect_infos.begin()->second;
+ // A limit of 0 expands the query's prefix to every term, but the
statistics are kept for the
+ // whole scan and copied to each scanner, so they keep a bounded number.
+ ASSERT_EQ(collect_info.scoring_prefixes.size(), 1u);
+ EXPECT_EQ(collect_info.scoring_prefixes[0].max_expansions,
kDefaultScoringExpansions);
+}
+
+TEST_F(CollectionStatisticsTest,
CollectRepeatedPhrasePrefixRegistersTheTailOnce) {
+ auto tablet_schema = create_tablet_schema_with_inverted_index();
+ MatchPredicateCollector collector;
+ CollectInfoMap collect_infos;
+ for (const char* query : {"alpha gamma", "beta gamma", "alpha gamma"}) {
+ auto match_expr =
+
std::make_shared<collection_statistics::MockVExpr>(TExprNodeType::MATCH_PRED);
+ match_expr->set_opcode(TExprOpcode::MATCH_PHRASE_PREFIX);
+ match_expr->_children.push_back(
+
std::make_shared<collection_statistics::MockVSlotRef>("content", SlotId(1)));
+ match_expr->_children.push_back(
+ std::make_shared<collection_statistics::MockVLiteral>(query));
+ auto status =
+ collector.collect(runtime_state_.get(), tablet_schema,
match_expr, &collect_infos);
+ ASSERT_TRUE(status.ok()) << status.msg();
+ }
+
+ ASSERT_EQ(collect_infos.size(), 1u);
+ const auto& collect_info = collect_infos.begin()->second;
+ EXPECT_EQ(collect_info.unique_terms, std::vector<std::string>({"alpha",
"beta"}));
+ ASSERT_EQ(collect_info.scoring_prefixes.size(), 1u);
+ EXPECT_EQ(collect_info.scoring_prefixes[0].prefix, "gamma");
}
TEST_F(CollectionStatisticsTest,
CollectSingleTermPhrasePrefixHasEmptyScoringLeaf) {
@@ -2655,6 +2709,8 @@ TEST_F(CollectionStatisticsTest,
CollectSingleTermPhrasePrefixHasEmptyScoringLea
EXPECT_TRUE(collect_info.unique_terms.empty());
ASSERT_EQ(collect_info.logical_scoring_leaves.size(), 1u);
EXPECT_TRUE(collect_info.logical_scoring_leaves[0].clauses.empty());
+ // A prefix alone scores a constant and needs no statistics.
+ EXPECT_TRUE(collect_info.scoring_prefixes.empty());
}
TEST_F(CollectionStatisticsTest, SearchMatchCollectsRawExecutionTerm) {
@@ -3282,4 +3338,26 @@ TEST(SearchPredicateCollectorTest,
LucenePureExclusionAllowsFieldlessMatchAll) {
EXPECT_TRUE(infos.empty());
}
+// With a limit of 1, segment A holding {rose} and segment B holding {red,
rose} expand to rose and
+// to red. The tablet scores red alone, whichever segment is counted first:
rose's document
+// frequency, which only segment A counted, would otherwise be too small.
+TEST(PrefixExpansionSetTest, KeepsTheSmallestTermsWhateverTheSegmentOrder) {
+ const std::wstring red = L"red";
+ const std::wstring rose = L"rose";
+ for (const bool a_first : {true, false}) {
+ PrefixExpansionSet merged(1);
+ for (const bool is_a : {a_first, !a_first}) {
+ merged.insert(is_a ? rose : red);
+ }
+ EXPECT_EQ(merged.terms(), std::set<std::wstring> {red}) << "a_first="
<< a_first;
+ }
+
+ PrefixExpansionSet three(3);
+ for (const std::wstring term : {L"d", L"b", L"e", L"a", L"c", L"b"}) {
+ three.insert(term);
+ }
+ EXPECT_EQ(three.terms(), (std::set<std::wstring> {L"a", L"b", L"c"}));
+ EXPECT_EQ(three.limit(), 3);
+}
+
} // namespace doris
diff --git
a/be/test/storage/index/inverted/snii/snii_index_reader_count_fallback_test.cpp
b/be/test/storage/index/inverted/snii/snii_index_reader_count_fallback_test.cpp
index fedd6b8395a..27fa4026b81 100644
---
a/be/test/storage/index/inverted/snii/snii_index_reader_count_fallback_test.cpp
+++
b/be/test/storage/index/inverted/snii/snii_index_reader_count_fallback_test.cpp
@@ -342,10 +342,18 @@ public:
return avgdl;
}
+ // The tablet expanded every prefix to beta.
+ std::vector<std::wstring> get_prefix_expansions(const std::wstring&
/*field_name*/,
+ const std::wstring&
prefix) override {
+ prefixes.push_back(prefix);
+ return {L"beta"};
+ }
+
float avgdl = 3.0F;
std::unordered_map<std::wstring, float> idfs {{L"alpha", 1.0F}, {L"beta",
2.0F}};
std::vector<std::wstring> fields;
std::vector<std::wstring> idf_terms;
+ std::vector<std::wstring> prefixes;
};
std::vector<uint32_t> positive_score_docids(const CollectionSimilarity&
similarity,
@@ -1001,9 +1009,11 @@ TEST_F(SniiIndexReaderCountFallback,
PublicPhraseQueriesScoreOccurrenceFrequency
prefix_bitmap, &analyzer_ctx));
ASSERT_NE(prefix_bitmap, nullptr);
EXPECT_EQ(bitmap_docids(*prefix_bitmap), (std::vector<uint32_t> {1}));
- EXPECT_EQ(prefix_stats->idf_terms, (std::vector<std::wstring> {L"alpha"}));
+ // The phrase's idf counts alpha and the term the tablet expanded "be" to.
+ EXPECT_EQ(prefix_stats->prefixes, (std::vector<std::wstring> {L"be"}));
+ EXPECT_EQ(prefix_stats->idf_terms, (std::vector<std::wstring> {L"alpha",
L"beta"}));
EXPECT_EQ(prefix.stats.inverted_index_query_cache_lookup, 0);
- BM25Similarity prefix_similarity(1.0F, 3.0F);
+ BM25Similarity prefix_similarity(3.0F, 3.0F);
prefix_similarity.bind_norms(index_query::kByteNormLengths);
EXPECT_FLOAT_EQ(score_for_doc(*prefix.context->collection_similarity, 1),
prefix_similarity.score(2.0F,
doris::snii::query::encode_norm(4)));
diff --git a/be/test/storage/segment/inverted_index_reader_test.cpp
b/be/test/storage/segment/inverted_index_reader_test.cpp
index cf6fb3c63bf..5c34d184dc0 100644
--- a/be/test/storage/segment/inverted_index_reader_test.cpp
+++ b/be/test/storage/segment/inverted_index_reader_test.cpp
@@ -5216,8 +5216,10 @@ TEST_F(InvertedIndexReaderTest,
FulltextMatchPhraseAloneConsumesCandidateRows) {
EXPECT_FALSE(run.context->candidate_rows_consumed);
}
-// A phrase prefix of one token runs as a prefix of it and publishes no score.
-TEST_F(InvertedIndexReaderTest, FulltextOneTokenPhrasePrefixPublishesNoScore) {
+// A phrase prefix of one token runs as a prefix of it and scores every match
1, as SNII does. A
+// match left unscored would read 0, and `score() > 0` would then drop every
row the prefix
+// matched.
+TEST_F(InvertedIndexReaderTest,
FulltextOneTokenPhrasePrefixScoresMatchesAsAConstant) {
TabletIndex meta;
auto reader =
english_fulltext_reader("fulltext_prefix_score",
@@ -5225,7 +5227,10 @@ TEST_F(InvertedIndexReaderTest,
FulltextOneTokenPhrasePrefixPublishesNoScore) {
MatchContext run(/*scoring=*/true);
EXPECT_EQ(match(*reader, run.context,
InvertedIndexQueryType::MATCH_PHRASE_PREFIX_QUERY, "qui"),
rows({0, 1}));
- EXPECT_TRUE(run.context->collection_similarity->_bm25_scores.empty());
+ const auto& scores = run.context->collection_similarity->_bm25_scores;
+ EXPECT_EQ(scores.size(), 2U);
+ EXPECT_FLOAT_EQ(scores.at(0), 1.0F);
+ EXPECT_FLOAT_EQ(scores.at(1), 1.0F);
}
// A keyword MATCH_PHRASE takes a trailing " ~N" or " ~N+" as its slop, as
SNII does, and reading
diff --git
a/regression-test/data/inverted_index_p0/test_match_phrase_prefix_score.out
b/regression-test/data/inverted_index_p0/test_match_phrase_prefix_score.out
new file mode 100644
index 00000000000..c82a936aa6e
--- /dev/null
+++ b/regression-test/data/inverted_index_p0/test_match_phrase_prefix_score.out
@@ -0,0 +1,74 @@
+-- This file is automatically generated. You should know what you did if you
want to edit this
+-- !v2_apple_r --
+1 1.1093
+4 0.9415
+5 0.9415
+
+-- !v3_apple_r --
+1 1.1093
+4 0.9415
+5 0.9415
+
+-- !snii_apple_r --
+1 1.1093
+4 0.9415
+5 0.9415
+
+-- !v2_apple_gr --
+2 3.7009
+7 3.7009
+
+-- !v3_apple_gr --
+2 3.7009
+7 3.7009
+
+-- !snii_apple_gr --
+2 3.7009
+7 3.7009
+
+-- !v2_apple_red_g --
+4 5.4381
+
+-- !v3_apple_red_g --
+4 5.4381
+
+-- !snii_apple_red_g --
+4 5.4381
+
+-- !v2_prefix_only --
+1 1
+2 1
+4 1
+5 1
+7 1
+8 1
+
+-- !v3_prefix_only --
+1 1
+2 1
+4 1
+5 1
+7 1
+8 1
+
+-- !snii_prefix_only --
+1 1
+2 1
+4 1
+5 1
+7 1
+8 1
+
+-- !v3_rows --
+2
+7
+
+-- !capped_apple_r --
+1 1.1144
+2 1.1144
+
+-- !uncapped_apple_r --
+1 1.5844
+2 1.5844
+3 1.5844
+
diff --git
a/regression-test/suites/inverted_index_p0/test_match_phrase_prefix_score.groovy
b/regression-test/suites/inverted_index_p0/test_match_phrase_prefix_score.groovy
new file mode 100644
index 00000000000..9acca2adb61
--- /dev/null
+++
b/regression-test/suites/inverted_index_p0/test_match_phrase_prefix_score.groovy
@@ -0,0 +1,129 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// score() over MATCH_PHRASE_PREFIX: never fails, counts the terms the prefix
expands to in the
+// idf, and gives the same scores on every inverted index storage format. A
prefix that expands to
+// fewer documents than the other terms used to make 4.0/4.1 throw
"UnionTermIterator does not
+// support scoring".
+suite("test_match_phrase_prefix_score", "p0") {
+ sql "DROP TABLE IF EXISTS test_match_phrase_prefix_score_v2"
+ sql "DROP TABLE IF EXISTS test_match_phrase_prefix_score_v3"
+ sql "DROP TABLE IF EXISTS test_match_phrase_prefix_score_snii"
+
+ sql """
+ CREATE TABLE test_match_phrase_prefix_score_v2 (
+ id INT NULL,
+ c1 TEXT NULL,
+ INDEX idx_c1 (c1) USING INVERTED PROPERTIES("lower_case" = "true",
"parser" = "english", "support_phrase" = "true")
+ ) ENGINE=OLAP
+ DUPLICATE KEY(id)
+ DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES ("replication_allocation" = "tag.location.default: 1",
"inverted_index_storage_format" = "V2");
+ """
+ sql """
+ CREATE TABLE test_match_phrase_prefix_score_v3 (
+ id INT NULL,
+ c1 TEXT NULL,
+ INDEX idx_c1 (c1) USING INVERTED PROPERTIES("lower_case" = "true",
"parser" = "english", "support_phrase" = "true")
+ ) ENGINE=OLAP
+ DUPLICATE KEY(id)
+ DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES ("replication_allocation" = "tag.location.default: 1",
"inverted_index_storage_format" = "V3");
+ """
+ sql """
+ CREATE TABLE test_match_phrase_prefix_score_snii (
+ id INT NULL,
+ c1 TEXT NULL,
+ INDEX idx_c1 (c1) USING INVERTED PROPERTIES("lower_case" = "true",
"parser" = "english", "support_phrase" = "true")
+ ) ENGINE=OLAP
+ DUPLICATE KEY(id)
+ DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES ("replication_allocation" = "tag.location.default: 1",
"inverted_index_storage_format" = "SNII");
+ """
+
+ // One insert per table keeps every table to a single segment, so the
segment statistics that
+ // score the expanded terms are the table's.
+ def rows = """(1, 'apple red'), (2, 'apple green'), (3, 'banana yellow'),
(4, 'apple red green'),
+ (5, 'apple apple red'), (6, 'red red red'), (7, 'apple
gray'), (8, 'apple garden path')"""
+ sql "INSERT INTO test_match_phrase_prefix_score_v2 VALUES ${rows}"
+ sql "INSERT INTO test_match_phrase_prefix_score_v3 VALUES ${rows}"
+ sql "INSERT INTO test_match_phrase_prefix_score_snii VALUES ${rows}"
+ sql "sync"
+
+ // 'apple r': the reported query. 'apple red' is rarer than 'apple', so
the prefix is the
+ // shorter list of the phrase.
+ order_qt_v2_apple_r """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v2
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_v3_apple_r """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v3
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_snii_apple_r """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_snii
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER BY
score() DESC LIMIT 10 """
+
+ // 'apple gr' expands to green and gray, both rarer than apple.
+ order_qt_v2_apple_gr """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v2
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple gr' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_v3_apple_gr """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v3
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple gr' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_snii_apple_gr """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_snii
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple gr' ORDER
BY score() DESC LIMIT 10 """
+
+ // Two phrase terms before the prefix.
+ order_qt_v2_apple_red_g """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v2
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple red g'
ORDER BY score() DESC LIMIT 10 """
+ order_qt_v3_apple_red_g """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v3
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple red g'
ORDER BY score() DESC LIMIT 10 """
+ order_qt_snii_apple_red_g """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_snii
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple red g'
ORDER BY score() DESC LIMIT 10 """
+
+ // A prefix alone is a constant score on every format.
+ order_qt_v2_prefix_only """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v2
+ WHERE c1 MATCH_PHRASE_PREFIX 'app' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_v3_prefix_only """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_v3
+ WHERE c1 MATCH_PHRASE_PREFIX 'app' ORDER BY
score() DESC LIMIT 10 """
+ order_qt_snii_prefix_only """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_snii
+ WHERE c1 MATCH_PHRASE_PREFIX 'app' ORDER BY
score() DESC LIMIT 10 """
+
+ // The same rows without score().
+ order_qt_v3_rows """ SELECT id FROM test_match_phrase_prefix_score_v3
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple gr' """
+
+ // A limit of one expansion over two segments. Segment A holds "apple
rose", segment B holds
+ // "apple red" and "apple rose"; each segment expands "r" to its smallest
term, rose in A and
+ // red in B. The tablet scores the prefix on red alone, the smallest term
of the tablet, and
+ // counts red in every segment that holds it. Counting rose from segment A
only would give it
+ // a document frequency of 1 instead of 2.
+ sql "DROP TABLE IF EXISTS test_match_phrase_prefix_score_capped"
+ sql """
+ CREATE TABLE test_match_phrase_prefix_score_capped (
+ id INT NULL,
+ c1 TEXT NULL,
+ INDEX idx_c1 (c1) USING INVERTED PROPERTIES("lower_case" = "true",
"parser" = "english", "support_phrase" = "true")
+ ) ENGINE=OLAP
+ DUPLICATE KEY(id)
+ DISTRIBUTED BY HASH(id) BUCKETS 1
+ PROPERTIES ("replication_allocation" = "tag.location.default: 1",
"inverted_index_storage_format" = "V3");
+ """
+ sql "INSERT INTO test_match_phrase_prefix_score_capped VALUES (1, 'apple
rose')"
+ sql "INSERT INTO test_match_phrase_prefix_score_capped VALUES (2, 'apple
red'), (3, 'apple rose')"
+ sql "sync"
+ sql "set inverted_index_max_expansions = 1"
+ order_qt_capped_apple_r """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_capped
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER
BY score() DESC LIMIT 10 """
+ sql "set inverted_index_max_expansions = 50"
+ order_qt_uncapped_apple_r """ SELECT id, round(score(), 4) s FROM
test_match_phrase_prefix_score_capped
+ WHERE c1 MATCH_PHRASE_PREFIX 'apple r' ORDER
BY score() DESC LIMIT 10 """
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
