This is an automated email from the ASF dual-hosted git repository.
airborne12 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new 21f37fe1822 [fix](inverted index) Score MATCH_PHRASE_PREFIX on the
tablet idf of the terms the prefix expands to (#69698)
21f37fe1822 is described below
commit 21f37fe182295601a774467857f315bd427a1ab3
Author: Jack <[email protected]>
AuthorDate: Wed Oct 28 16:01:17 2026 +0800
[fix](inverted index) Score MATCH_PHRASE_PREFIX on the tablet idf of the
terms the prefix expands to (#69698)
### What problem does this PR solve?
Issue Number: None
Related PR: #68758
Problem Summary:
score() over MATCH_PHRASE_PREFIX gave scores that ignored the prefix and
differed between inverted index storage formats.
1. The prefix of a phrase prefix never entered the idf. "apple r" scored
on
idf(apple) alone, and a rare expansion such as "rose" ranked like a
common
one such as "red". Lucene's multi-phrase query, and so Elasticsearch,
sum the idf of the phrase terms and of every term the prefix expands to.
The statistics collector now registers the prefix; every segment expands
it, counts the document frequency of each expanded term in the tablet
statistics, and records which terms the prefix expanded to. The scorer
adds their idf to the phrase's, so all idfs come from the same tablet
statistics and the score does not depend on how rows are split into
segments. With the reported table, `apple r` now scores 1.4508328, the
value Elasticsearch 9.5 gives; on a 10-row table, `apple r`, `apple ro`
and `apple g` match Elasticsearch to four decimals, over one segment and
over three.
2. A prefix of one token scored 0 on V2/V3 (CLucene did not publish
scores
for expansion leaves) and 1 on SNII. It now scores 1 on every format, as
the constant score of Lucene and Elasticsearch prefix queries. At 0,
`score() > 0` dropped every row the prefix matched.
3. No test covered score() over MATCH_PHRASE_PREFIX across storage
formats.
Add unit tests for the collector, the segment expansion, the tablet idf
and the constant score, and a regression suite over V2, V3 and SNII.
Two existing tests asserted the old behavior and are updated: the SNII
public phrase prefix scoring test (the idf now counts the expanded term)
and the CLucene one-token phrase prefix test (it asserted no score).
A prefix collected by a SEARCH predicate has no recorded expansion and
keeps
scoring the phrase terms alone.
---
.../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 6c569dafdf4..0e0661382b5 100644
--- a/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
+++ b/be/src/storage/index/inverted/clucene/clucene_index_reader.cpp
@@ -418,10 +418,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 0d29fce4564..db683061be9 100644
--- a/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
+++ b/be/src/storage/index/inverted/query/scoring/bm25_similarity.cpp
@@ -92,6 +92,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 73e74422edb..230d7c961d0 100644
--- a/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
+++ b/be/src/storage/index/inverted/query/scoring/bm25_similarity.h
@@ -37,6 +37,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 11a1a5d4bb0..c163133fbde 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"
@@ -117,6 +119,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()) {
@@ -193,6 +254,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 {
@@ -513,15 +592,18 @@ Status CollectionStatistics::process_segment(const
RowsetSharedPtr& rowset,
segment_v2::IndexReaderHelper::is_normalizer_only(
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 {}",
@@ -647,15 +729,18 @@ Status CollectionStatistics::process_segment(const
RowsetSharedPtr& rowset,
_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);
}
@@ -703,6 +788,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();
@@ -713,6 +808,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();
}
@@ -722,6 +818,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();
}
@@ -801,6 +898,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 ebd52ce91e4..3aac78df29a 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;
@@ -230,10 +274,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
} // namespace doris
diff --git a/be/src/storage/index/inverted/reader/predicate_collector.cpp
b/be/src/storage/index/inverted/reader/predicate_collector.cpp
index 27d65ef2a7b..6f1fab50075 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 "exec/common/variant_util.h"
@@ -30,6 +32,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 ef5107f14a8..211c7ca0f09 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 a6b52573770..6e00b652fd3 100644
--- a/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
+++ b/be/test/storage/index/inverted/reader/collection_statistics_test.cpp
@@ -2678,7 +2678,7 @@ TEST_F(CollectionStatisticsTest,
CollectConvertsAnalyzerFailureToStatus) {
EXPECT_TRUE(collect_infos.empty());
}
-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);
@@ -2700,6 +2700,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) {
@@ -2721,6 +2775,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) {
@@ -3313,4 +3369,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 9c7d2f9caf8..c057bc18914 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 11b560aabc2..1123bc6fb5a 100644
--- a/be/test/storage/segment/inverted_index_reader_test.cpp
+++ b/be/test/storage/segment/inverted_index_reader_test.cpp
@@ -5229,8 +5229,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",
@@ -5238,7 +5240,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]
