|
19 | 19 | #include <condition_variable> |
20 | 20 | #include <cstdint> |
21 | 21 | #include <functional> |
| 22 | +#include <iterator> |
22 | 23 | #include <mutex> |
23 | 24 | #include <optional> |
24 | 25 | #include <set> |
@@ -82,6 +83,37 @@ struct MowHiddenRows { |
82 | 83 | bool use_page_cache = true; |
83 | 84 | }; |
84 | 85 |
|
| 86 | +// The `limit` smallest terms, in dictionary order, that a prefix expanded to in the segments seen |
| 87 | +// so far: the terms an index-wide expansion of Lucene would take. A term only enters or stays |
| 88 | +// while fewer than `limit` smaller terms are known, and one dropped never returns, whatever |
| 89 | +// order the segments come in. |
| 90 | +// |
| 91 | +// That is what keeps the document frequencies whole. A term of the final set has fewer than |
| 92 | +// `limit` smaller terms in every segment holding it, so each of those segments expanded to it |
| 93 | +// and counted its documents. With a limit of 1, segment A holding {rose} and segment B holding |
| 94 | +// {red, rose} leave {red}: B's expansion is red alone, but rose is not scored, so its document |
| 95 | +// frequency, which only A counted, is not used. |
| 96 | +class PrefixExpansionSet { |
| 97 | +public: |
| 98 | + explicit PrefixExpansionSet(int32_t limit) : _limit(limit) { DORIS_CHECK_GT(limit, 0); } |
| 99 | + |
| 100 | + void insert(const std::wstring& term) { |
| 101 | + _terms.insert(term); |
| 102 | + if (_terms.size() > static_cast<size_t>(_limit)) { |
| 103 | + _terms.erase(std::prev(_terms.end())); |
| 104 | + } |
| 105 | + } |
| 106 | + |
| 107 | + int32_t limit() const { return _limit; } |
| 108 | + const std::set<std::wstring>& terms() const { return _terms; } |
| 109 | + |
| 110 | +private: |
| 111 | + int32_t _limit; |
| 112 | + std::set<std::wstring> _terms; |
| 113 | +}; |
| 114 | +// The terms each prefix expanded to, by prefix. |
| 115 | +using FieldPrefixExpansions = std::unordered_map<std::wstring, PrefixExpansionSet>; |
| 116 | + |
85 | 117 | class CollectionStatistics { |
86 | 118 | public: |
87 | 119 | explicit CollectionStatistics(PredicateCollectorPtr search_collector = nullptr) |
@@ -119,9 +151,7 @@ class CollectionStatistics { |
119 | 151 |
|
120 | 152 | private: |
121 | 153 | // The terms each collected prefix expanded to, by field and prefix. |
122 | | - using PrefixExpansions = |
123 | | - std::unordered_map<std::wstring, |
124 | | - std::unordered_map<std::wstring, std::set<std::wstring>>>; |
| 154 | + using PrefixExpansions = std::unordered_map<std::wstring, FieldPrefixExpansions>; |
125 | 155 |
|
126 | 156 | struct SniiScoringSegmentAccumulator { |
127 | 157 | uint64_t doc_count = 0; |
@@ -247,13 +277,13 @@ Status exclude_hidden_docs(std::span<const uint32_t> hidden_docs, const roaring: |
247 | 277 | // The terms whose document frequencies a segment adds for `collect_info`: its scoring terms, then |
248 | 278 | // each term its prefixes expand to in `source`, so that a phrase prefix is scored on the same |
249 | 279 | // tablet statistics as the other terms. A term met twice is listed once, as its documents count |
250 | | -// once. The expansions of each prefix, of this segment alone, are added to `expansions`. |
| 280 | +// once. The terms each prefix expands to in this segment are added to `expansions`, which keeps |
| 281 | +// the smallest ones of the segments seen (PrefixExpansionSet). |
251 | 282 | // |
252 | 283 | // Example: "red r" collects red and, in a segment holding red, rose and run, the terms red (already |
253 | 284 | // listed), rose and run, and records {red, rose, run} for the prefix "r". |
254 | 285 | Status segment_scoring_terms(index_query::IndexSource& source, const CollectInfo& collect_info, |
255 | | - std::unordered_map<std::wstring, std::set<std::wstring>>* expansions, |
256 | | - std::vector<std::string>* terms); |
| 286 | + FieldPrefixExpansions* expansions, std::vector<std::string>* terms); |
257 | 287 |
|
258 | 288 | // Takes from a term's document frequency the documents of `hidden_docs` that hold it. |
259 | 289 | Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_view term, |
|
0 commit comments