Skip to content

Commit 96a0b49

Browse files
author
Shivam Gupta
committed
[fix](inverted index) Keep no CLucene norms for BM25 statistics
Asking a CLucene segment reader for a field's norms makes it keep them for the cached searcher's lifetime, uncharged to the searcher cache, and the merge-on-write statistics visit every segment of the read set, including the segments the scan prunes and never scores. Read the norms into a buffer of the statistics' own, one segment at a time, and keep only sums with the searcher: the field's non-NULL norm lengths, and the hidden rows' lengths for the last few sets of hidden rows, so queries at one read version read no norms. Count the hidden rows a term's postings list by walking both ascending lists together instead of zeroing a bitset as large as the largest hidden row, and skip terms without postings.
1 parent 7830cb1 commit 96a0b49

8 files changed

Lines changed: 194 additions & 46 deletions

File tree

‎be/src/storage/index/inverted/clucene/searcher_cache_value.h‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,15 +17,19 @@
1717

1818
#pragma once
1919

20+
#include <cstdint>
2021
#include <functional>
2122
#include <mutex>
23+
#include <span>
2224
#include <string>
2325
#include <unordered_map>
2426
#include <utility>
27+
#include <vector>
2528

2629
#include "common/status.h"
2730
#include "storage/index/inverted/clucene/inverted_index_searcher.h"
2831
#include "storage/index/inverted/common/inverted_index_cache.h"
32+
#include "util/hash_util.hpp"
2933

3034
namespace doris::segment_v2 {
3135

@@ -49,11 +53,50 @@ struct CluceneSearcherCacheValue final : InvertedIndexSearcherCache::CacheValue
4953
return Status::OK();
5054
}
5155

56+
// The sum of the lengths the norms of `docs`, ascending rows of the index, stand for, computed
57+
// by `compute` the first time the field meets that set of rows. Queries at one read version
58+
// hide the same rows, so they read no norms; a few sets per field are kept for queries at
59+
// different versions.
60+
Status hidden_norm_length_sum(const std::wstring& field, std::span<const uint32_t> docs,
61+
const std::function<Status(uint64_t*)>& compute, uint64_t* out) {
62+
const RowSetKey key {
63+
.fingerprint = HashUtil::xxHash64WithSeed(
64+
reinterpret_cast<const char*>(docs.data()), docs.size_bytes(), 0),
65+
.count = docs.size(),
66+
.first = docs.empty() ? 0 : docs.front(),
67+
.last = docs.empty() ? 0 : docs.back()};
68+
std::lock_guard lock(_norm_length_sums_mutex);
69+
auto& sums = _hidden_length_sums[field];
70+
for (const auto& [cached_key, sum] : sums) {
71+
if (cached_key == key) {
72+
*out = sum;
73+
return Status::OK();
74+
}
75+
}
76+
RETURN_IF_ERROR(compute(out));
77+
if (sums.size() == kHiddenSetsPerField) {
78+
sums.erase(sums.begin());
79+
}
80+
sums.emplace_back(key, *out);
81+
return Status::OK();
82+
}
83+
5284
IndexSearcherPtr searcher;
5385

5486
private:
87+
struct RowSetKey {
88+
uint64_t fingerprint;
89+
size_t count;
90+
uint32_t first;
91+
uint32_t last;
92+
bool operator==(const RowSetKey&) const = default;
93+
};
94+
static constexpr size_t kHiddenSetsPerField = 4;
95+
5596
std::mutex _norm_length_sums_mutex;
5697
std::unordered_map<std::wstring, uint64_t> _norm_length_sums;
98+
std::unordered_map<std::wstring, std::vector<std::pair<RowSetKey, uint64_t>>>
99+
_hidden_length_sums;
57100
};
58101

59102
} // namespace doris::segment_v2

‎be/src/storage/index/inverted/clucene/spi/clucene_index_source.cpp‎

Lines changed: 28 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -243,21 +243,22 @@ std::span<const float> CluceneIndexSource::norm_lengths() const {
243243
return BM25Similarity::lucene_norm_lengths();
244244
}
245245

246-
// Each segment reader keeps a field's norms once they are read, the copy scoring reads. A reader of
247-
// several segments would build and keep one more copy of them all, so read the norms of each
248-
// segment, a segment without the field's norms reading as zero lengths, as that reader would.
246+
// The statistics read a field's norms into a buffer of their own, freed after use: asking a reader
247+
// for its norms makes it keep them, uncharged to the searcher cache, for every segment the
248+
// statistics visit, scored or not. Reading per segment also avoids the copy of all segments' norms
249+
// a reader of several segments would keep. A segment without the field's norms reads as zero
250+
// lengths, as that reader would.
249251
std::vector<CluceneIndexSource::ReaderPartition> CluceneIndexSource::_norm_partitions() const {
250252
if (!_partitions.empty()) {
251253
return _partitions;
252254
}
253255
return {{.reader = _reader.get(), .begin = 0, .end = doc_count()}};
254256
}
255257

256-
const uint8_t* CluceneIndexSource::_norms_of(lucene::index::IndexReader* reader) const {
257-
if (!reader->hasNorms(_field.c_str())) {
258-
return nullptr;
259-
}
260-
return reader->norms(_field.c_str());
258+
void CluceneIndexSource::_read_norms(const ReaderPartition& partition,
259+
DorisVector<uint8_t>* norms) const {
260+
norms->assign(partition.end - partition.begin, 0);
261+
partition.reader->norms(_field.c_str(), norms->data());
261262
}
262263

263264
Status CluceneIndexSource::sum_norm_lengths(uint64_t* out) {
@@ -268,13 +269,11 @@ Status CluceneIndexSource::sum_norm_lengths(uint64_t* out) {
268269
"field {} has no norms", inverted_index::StringHelper::to_string(_field));
269270
}
270271
const auto lengths = norm_lengths();
272+
DorisVector<uint8_t> norms;
271273
for (const ReaderPartition& partition : _norm_partitions()) {
272-
const uint8_t* norms = _norms_of(partition.reader);
273-
if (norms == nullptr) {
274-
continue;
275-
}
276-
for (uint32_t doc = 0, count = partition.end - partition.begin; doc < count; ++doc) {
277-
*out += static_cast<uint64_t>(lengths[norms[doc]]);
274+
_read_norms(partition, &norms);
275+
for (const uint8_t norm : norms) {
276+
*out += static_cast<uint64_t>(lengths[norm]);
278277
}
279278
}
280279
} catch (CLuceneError& e) {
@@ -295,21 +294,23 @@ Status CluceneIndexSource::sum_norm_lengths_of(std::span<const uint32_t> docs, u
295294
}
296295
const auto lengths = norm_lengths();
297296
const uint32_t count = doc_count();
298-
const auto partitions = _norm_partitions();
299-
size_t partition = 0;
300-
const uint8_t* norms = _norms_of(partitions[0].reader);
301-
for (const uint32_t doc : docs) {
302-
if (doc >= count) {
303-
return Status::Corruption("document {} is beyond the {} documents of the index",
304-
doc, count);
297+
if (docs.back() >= count) {
298+
return Status::Corruption("document {} is beyond the {} documents of the index",
299+
docs.back(), count);
300+
}
301+
DorisVector<uint8_t> norms;
302+
// `docs` ascend, so each partition's documents are contiguous in them.
303+
size_t next = 0;
304+
for (const ReaderPartition& partition : _norm_partitions()) {
305+
if (next == docs.size()) {
306+
break;
305307
}
306-
// `docs` ascend, so the partitions are visited in order.
307-
while (doc >= partitions[partition].end) {
308-
++partition;
309-
norms = _norms_of(partitions[partition].reader);
308+
if (docs[next] >= partition.end) {
309+
continue;
310310
}
311-
if (norms != nullptr) {
312-
*out += static_cast<uint64_t>(lengths[norms[doc - partitions[partition].begin]]);
311+
_read_norms(partition, &norms);
312+
for (; next < docs.size() && docs[next] < partition.end; ++next) {
313+
*out += static_cast<uint64_t>(lengths[norms[docs[next] - partition.begin]]);
313314
}
314315
}
315316
} catch (CLuceneError& e) {

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
#include <vector>
2626

2727
#include "common/status.h"
28+
#include "core/custom_allocator.h"
2829
#include "storage/index/inverted/query/spi/index_source.h"
2930

3031
namespace lucene::index {
@@ -70,8 +71,9 @@ class CluceneIndexSource final : public index_query::IndexSource {
7071
void _append_partitions(lucene::index::IndexReader* reader, uint32_t begin);
7172
// The partitions whose norms make up the field's, the whole reader when it has no others.
7273
std::vector<ReaderPartition> _norm_partitions() const;
73-
// A partition's encoded norms of the field, one per document, or null when it has none.
74-
const uint8_t* _norms_of(lucene::index::IndexReader* reader) const;
74+
// Reads a partition's encoded norms of the field, one per document, into `norms`, without the
75+
// reader keeping them.
76+
void _read_norms(const ReaderPartition& partition, DorisVector<uint8_t>* norms) const;
7577

7678
std::shared_ptr<lucene::index::IndexReader> _reader;
7779
std::wstring _field;

‎be/src/storage/index/inverted/query/exec/index_source.cpp‎

Lines changed: 19 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -51,30 +51,34 @@ namespace {
5151
// How many postings a scan decodes in the time a seek costs.
5252
constexpr uint64_t kPostingsPerSeek = 32;
5353

54-
// Decodes every posting once and tests it against a bitset of `docs`.
54+
// Decodes every posting once and walks `docs` alongside, both ascending.
5555
Status count_listed_docs_by_scan(PostingsCursor& cursor, std::span<const uint32_t> docs,
5656
uint64_t* out) {
57-
std::vector<uint64_t> bits(docs.back() / 64 + 1, 0);
58-
for (const uint32_t doc : docs) {
59-
bits[doc / 64] |= uint64_t {1} << (doc % 64);
60-
}
61-
const auto is_set = [&bits](uint64_t doc) {
62-
return doc / 64 < bits.size() && ((bits[doc / 64] >> (doc % 64)) & 1) != 0;
63-
};
57+
size_t next = 0;
6458
PostingsBlock block;
6559
bool eof = false;
66-
while (true) {
60+
while (next < docs.size()) {
6761
RETURN_IF_ERROR(cursor.next_block(&block, &eof));
6862
if (eof) {
6963
break;
7064
}
7165
if (block.dense) {
72-
for (uint64_t doc = block.range_begin; doc < block.range_end; ++doc) {
73-
*out += is_set(doc) ? 1 : 0;
66+
const auto begin = std::lower_bound(docs.begin() + next, docs.end(), block.range_begin);
67+
const auto end = std::lower_bound(begin, docs.end(), block.range_end);
68+
*out += static_cast<uint64_t>(end - begin);
69+
next = end - docs.begin();
70+
continue;
71+
}
72+
for (const uint32_t doc : block.docs) {
73+
while (next < docs.size() && docs[next] < doc) {
74+
++next;
7475
}
75-
} else {
76-
for (const uint32_t doc : block.docs) {
77-
*out += is_set(doc) ? 1 : 0;
76+
if (next == docs.size()) {
77+
break;
78+
}
79+
if (docs[next] == doc) {
80+
++*out;
81+
++next;
7882
}
7983
}
8084
}
@@ -85,7 +89,7 @@ Status count_listed_docs_by_scan(PostingsCursor& cursor, std::span<const uint32_
8589

8690
Status count_listed_docs(PostingsCursor& cursor, std::span<const uint32_t> docs, uint64_t* out) {
8791
*out = 0;
88-
if (docs.empty()) {
92+
if (docs.empty() || cursor.doc_freq() == 0) {
8993
return Status::OK();
9094
}
9195
// Leaping seeks once per wanted document, scanning decodes every posting: leap only over

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

Lines changed: 30 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -133,6 +133,18 @@ Status sum_non_null_norm_lengths(index_query::IndexSource& source,
133133
Status exclude_hidden_docs(index_query::IndexSource& source, std::span<const uint32_t> hidden_docs,
134134
const roaring::Roaring& null_docs, uint64_t non_null_length_sum,
135135
index_query::IndexScoringStats* stats) {
136+
return exclude_hidden_docs(
137+
hidden_docs, null_docs, non_null_length_sum,
138+
[&source](std::span<const uint32_t> docs, uint64_t* out) {
139+
return source.sum_norm_lengths_of(docs, out);
140+
},
141+
stats);
142+
}
143+
144+
Status exclude_hidden_docs(std::span<const uint32_t> hidden_docs, const roaring::Roaring& null_docs,
145+
uint64_t non_null_length_sum,
146+
const SumNormLengthsOf& sum_norm_lengths_of,
147+
index_query::IndexScoringStats* stats) {
136148
DORIS_CHECK(stats != nullptr);
137149
if (!hidden_docs.empty() && hidden_docs.back() >= stats->doc_count) {
138150
return Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED>(
@@ -153,7 +165,9 @@ Status exclude_hidden_docs(index_query::IndexSource& source, std::span<const uin
153165
std::ranges::copy_if(hidden_docs, std::back_inserter(hidden_non_null_docs),
154166
[&null_docs](uint32_t doc) { return !null_docs.contains(doc); });
155167
uint64_t hidden_lengths = 0;
156-
RETURN_IF_ERROR(source.sum_norm_lengths_of(hidden_non_null_docs, &hidden_lengths));
168+
if (!hidden_non_null_docs.empty()) {
169+
RETURN_IF_ERROR(sum_norm_lengths_of(hidden_non_null_docs, &hidden_lengths));
170+
}
157171
DORIS_CHECK(hidden_lengths <= non_null_length_sum);
158172
stats->token_count = non_null_length_sum - hidden_lengths;
159173
return Status::OK();
@@ -580,8 +594,22 @@ Status CollectionStatistics::process_segment(const RowsetSharedPtr& rowset,
580594
&non_null_length_sum));
581595
#endif
582596
}
597+
// The statistics keep no norms, so the lengths of a segment's hidden rows are summed
598+
// once per set of hidden rows and kept with the searcher.
599+
auto sum_hidden_lengths = [&](std::span<const uint32_t> docs, uint64_t* out) {
600+
auto sum = [&source, docs](uint64_t* lengths) {
601+
return source->sum_norm_lengths_of(docs, lengths);
602+
};
603+
#ifdef BE_TEST
604+
return sum(out);
605+
#else
606+
return inverted_index_cache_handle.get<CluceneSearcherCacheValue>()
607+
->hidden_norm_length_sum(ws_field_name, docs, sum, out);
608+
#endif
609+
};
583610
RETURN_IF_ERROR(collection_statistics_detail::exclude_hidden_docs(
584-
*source, hidden_docs, *null_docs, non_null_length_sum, &scoring_stats));
611+
hidden_docs, *null_docs, non_null_length_sum, sum_hidden_lengths,
612+
&scoring_stats));
585613
}
586614
total_segment_docs =
587615
std::max(total_segment_docs, static_cast<int32_t>(scoring_stats.doc_count));

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

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -221,6 +221,15 @@ Status exclude_hidden_docs(index_query::IndexSource& source, std::span<const uin
221221
const roaring::Roaring& null_docs, uint64_t non_null_length_sum,
222222
index_query::IndexScoringStats* stats);
223223

224+
// Sums the lengths the norms of ascending rows of a segment's index stand for.
225+
using SumNormLengthsOf = std::function<Status(std::span<const uint32_t> docs, uint64_t* out)>;
226+
227+
// exclude_hidden_docs, the lengths of the hidden non-NULL rows summed by `sum_norm_lengths_of`.
228+
Status exclude_hidden_docs(std::span<const uint32_t> hidden_docs, const roaring::Roaring& null_docs,
229+
uint64_t non_null_length_sum,
230+
const SumNormLengthsOf& sum_norm_lengths_of,
231+
index_query::IndexScoringStats* stats);
232+
224233
// Takes from a term's document frequency the documents of `hidden_docs` that hold it.
225234
Status exclude_hidden_term_docs(index_query::IndexSource& source, std::string_view term,
226235
std::span<const uint32_t> hidden_docs, uint64_t* doc_frequency);

‎be/test/storage/index/inverted/reader/collection_statistics_test.cpp‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1225,6 +1225,24 @@ TEST(CollectionStatisticsHiddenRowsTest, CountListedDocsOfNothing) {
12251225
const std::vector<uint32_t> docs {1, 2};
12261226
ASSERT_TRUE(index_query::count_listed_docs(empty, docs, &listed).ok());
12271227
EXPECT_EQ(listed, 0);
1228+
EXPECT_EQ(empty.seeks, 0);
1229+
}
1230+
1231+
// Scanning walks the wanted documents alongside the postings, however large their IDs, and stops
1232+
// once every wanted document is passed.
1233+
TEST(CollectionStatisticsHiddenRowsTest, CountListedDocsScansFarDocsWithoutWalkingEveryBlock) {
1234+
BlockListCursor cursor({std::vector<uint32_t> {3}, std::pair<uint32_t, uint32_t> {10, 20},
1235+
std::vector<uint32_t> {9999999}, std::vector<uint32_t> {10000005}});
1236+
const std::vector<uint32_t> docs {3, 15, 19, 9999999};
1237+
uint64_t listed = 0;
1238+
ASSERT_TRUE(index_query::count_listed_docs(cursor, docs, &listed).ok());
1239+
EXPECT_EQ(listed, 4);
1240+
EXPECT_EQ(cursor.seeks, 0);
1241+
1242+
BlockListCursor far({std::vector<uint32_t> {1}});
1243+
const std::vector<uint32_t> far_docs {9999999};
1244+
ASSERT_TRUE(index_query::count_listed_docs(far, far_docs, &listed).ok());
1245+
EXPECT_EQ(listed, 0);
12281246
}
12291247

12301248
TEST(CollectionStatisticsHiddenRowsTest, ExcludeHiddenDocsSumsNormsOfReturnedRows) {

‎be/test/storage/segment/inverted_index_searcher_cache_test.cpp‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,7 @@
2424
#include <memory>
2525
#include <string>
2626
#include <thread>
27+
#include <vector>
2728

2829
#include "common/status.h"
2930
#include "gtest/gtest_pred_impl.h"
@@ -350,4 +351,46 @@ TEST(CluceneSearcherCacheValueTest, NonNullNormLengthSumIsComputedOncePerField)
350351
EXPECT_EQ(computed, 4);
351352
}
352353

354+
// The norm length sum of a set of hidden rows is computed once per field and set, and a few sets
355+
// per field are kept, the oldest given up first.
356+
TEST(CluceneSearcherCacheValueTest, HiddenNormLengthSumIsComputedOncePerRowSet) {
357+
CluceneSearcherCacheValue value(FulltextIndexSearcherPtr(nullptr), 0, 0);
358+
int computed = 0;
359+
auto compute = [&computed](uint64_t sum) {
360+
return [&computed, sum](uint64_t* out) {
361+
++computed;
362+
*out = sum;
363+
return Status::OK();
364+
};
365+
};
366+
const std::vector<uint32_t> rows {1, 5, 9};
367+
const std::vector<uint32_t> other_rows {1, 5, 10};
368+
uint64_t sum = 0;
369+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", rows, compute(7), &sum).ok());
370+
EXPECT_EQ(sum, 7);
371+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", rows, compute(8), &sum).ok());
372+
EXPECT_EQ(sum, 7);
373+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", other_rows, compute(8), &sum).ok());
374+
EXPECT_EQ(sum, 8);
375+
ASSERT_TRUE(value.hidden_norm_length_sum(L"b", rows, compute(9), &sum).ok());
376+
EXPECT_EQ(sum, 9);
377+
EXPECT_EQ(computed, 3);
378+
379+
auto fail = [](uint64_t*) { return Status::Corruption("bad norms"); };
380+
const std::vector<uint32_t> failing_rows {2};
381+
EXPECT_FALSE(value.hidden_norm_length_sum(L"a", failing_rows, fail, &sum).ok());
382+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", failing_rows, compute(4), &sum).ok());
383+
EXPECT_EQ(sum, 4);
384+
EXPECT_EQ(computed, 4);
385+
386+
// Field "a" holds {1,5,9}, {1,5,10} and {2}; two more sets give up {1,5,9}.
387+
const std::vector<uint32_t> fourth {3};
388+
const std::vector<uint32_t> fifth {4};
389+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", fourth, compute(1), &sum).ok());
390+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", fifth, compute(1), &sum).ok());
391+
ASSERT_TRUE(value.hidden_norm_length_sum(L"a", rows, compute(6), &sum).ok());
392+
EXPECT_EQ(sum, 6);
393+
EXPECT_EQ(computed, 7);
394+
}
395+
353396
} // namespace doris::segment_v2

0 commit comments

Comments
 (0)