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 4c1e0ddfe21 [improvement](be) Read and collect SNII BKD range hits in
bulk (#69908)
4c1e0ddfe21 is described below
commit 4c1e0ddfe2174a8446081af3fb53d26013eb7a96
Author: Jack <[email protected]>
AuthorDate: Mon Nov 2 09:20:24 2026 +0800
[improvement](be) Read and collect SNII BKD range hits in bulk (#69908)
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: A range filter on a numeric SNII index reads the leaves
that lie wholly inside the
range one at a time, gathers their doc ids, radix-sorts them and adds
them to a roaring bitmap. On a
99M-row table, 71% of the SNII stack samples of a query with a wide
`latency_ms` range were in this
path: 15% in the sort, 9% in `addMany`, and about 27% in reading, mostly
per-call overhead, since a
leaf is a few KB and takes one positioned read of its own.
- Whole-leaf hits lie next to each other in `bkd_data`, so one read now
takes up to about 1 MiB of
them. The bytes read are the same, in far fewer calls, and sequentially
when they are not cached.
- A wide range sets the doc ids in a flat bitmap instead, which needs no
sort. It is loaded into a
Roaring through the portable format, a published spec, because CRoaring
2.1.2 has no call that
takes a bitset.
- A flat bitmap costs a pass over all its words, so it takes doc ids
only up to 256 per point, which
holds it to 32 bytes per point. The doc ids decide, not the index's
document count, which leaves
out rows with no value: a narrow range, or a range on a column that is
mostly NULL, keeps the
sort.
- The bitmap also stops at doc id 2^28, which is 32 MiB. The doc ids of
a leaf past that take the
sort as before, so a damaged leaf cannot make it allocate more.
- The leaf decoder reuses its vector of value runs instead of allocating
one per leaf.
The on-disk format and the write path do not change.
| Query (99M rows), new/previous | Hot | Cold |
|---|---|---|
| filters and `latency_ms BETWEEN 2000 AND 6000`, no text | 0.42 / 0.39
/ 0.37 (212 ms to 85 ms) | 0.87 |
| phrase with `latency_ms >= 3000` | 0.62 / 0.61 / 0.58 | 1.00 |
| phrase with `latency_ms >= 8000` | 0.90 / 0.89 / 0.87 | 1.00 |
| phrase with a 7-day date range | 1.01 / 0.98 / 1.00 | |
Hot: both versions interleaved in one BE process on a quiet host, three
runs each. The 21 queries of
the bench with no range do not reach this code and read 0.86-1.02 in one
run, which is the noise of
that run. Cold: BE restarted and the index files evicted before every
run, configuration order
alternated, 5 runs each; the wide range gains and the others wait on
other reads. All 25 queries
return the same results with both versions. The build also had #69879,
#69882, #69887, #69891 and
#69895.
A wide range briefly holds about three times its result in memory: the
flat bitmap, the portable
image and the bitmap loaded from it. That is one bit per row of the
segment each, and it is freed
when the range ends. The chunks of gathered doc ids it replaces took 8
MiB at most. Like those
chunks, the bitmap and the image are plain vectors that the memory
tracker does not see.
---
.../storage/index/inverted/snii/bkd/bkd_format.h | 2 +-
.../storage/index/inverted/snii/bkd/bkd_reader.cpp | 176 ++++++++++++++--
.../storage/index/inverted/snii/bkd/bkd_reader.h | 16 +-
.../storage/index/inverted/snii/bkd/leaf_codec.cpp | 13 +-
.../storage/index/inverted/snii/bkd/leaf_codec.h | 3 +
.../index/inverted/snii/bkd/bkd_reader_test.cpp | 223 ++++++++++++++++++++-
6 files changed, 399 insertions(+), 34 deletions(-)
diff --git a/be/src/storage/index/inverted/snii/bkd/bkd_format.h
b/be/src/storage/index/inverted/snii/bkd/bkd_format.h
index 749fdb22f7a..8382e629c49 100644
--- a/be/src/storage/index/inverted/snii/bkd/bkd_format.h
+++ b/be/src/storage/index/inverted/snii/bkd/bkd_format.h
@@ -100,7 +100,7 @@ inline constexpr uint32_t kBuiltWithSpill = 1U << 0;
// Two files, not the old implementation's three: bkd_meta is folded into the
// bkd_index header, where it gains a magic, a version and a framer checksum.
// bkd_index is HOT (read in full at open and kept resident); bkd_data is COLD
-// (one positioned read per touched leaf).
+// (positioned reads of the touched leaves, a run of whole-leaf hits in one
read).
inline constexpr std::string_view kBkdIndexFileName = "bkd_index";
inline constexpr std::string_view kBkdDataFileName = "bkd_data";
diff --git a/be/src/storage/index/inverted/snii/bkd/bkd_reader.cpp
b/be/src/storage/index/inverted/snii/bkd/bkd_reader.cpp
index f4fc8fe01f3..6cab3afd2ec 100644
--- a/be/src/storage/index/inverted/snii/bkd/bkd_reader.cpp
+++ b/be/src/storage/index/inverted/snii/bkd/bkd_reader.cpp
@@ -18,9 +18,13 @@
#include "storage/index/inverted/snii/bkd/bkd_reader.h"
#include <algorithm>
+#include <bit>
+#include <cstdint>
#include <cstring>
+#include <span>
#include <string_view>
#include <utility>
+#include <vector>
#include "common/check.h"
#include "roaring/roaring.hh"
@@ -75,6 +79,112 @@ void radix_sort_u32(std::vector<uint32_t>* values,
std::vector<uint32_t>* scratc
}
}
+// Whole-leaf hits lie next to each other in bkd_data, so one read takes many
of them: far fewer
+// calls when they are cached, and one sequential read when they are not.
+constexpr uint64_t kMaxLeavesReadBytes = 1U << 20;
+
+uint32_t leaves_in_one_read(const BkdIndexBlockReader& block, uint32_t first,
uint32_t end) {
+ const uint64_t begin = block.leaf(first).offset;
+ uint32_t next = first + 1;
+ while (next < end && block.leaf(next).offset - begin <
kMaxLeavesReadBytes) {
+ ++next;
+ }
+ return next;
+}
+
+// A flat bitmap needs no sort, but a pass over all its words however few bits
are set, which pays
+// up to about this many doc ids per point. The doc ids decide, not the
index's document count,
+// which leaves out rows with no value.
+constexpr uint64_t kDocIdsPerPointForDocBits = 256;
+// A doc id from here up goes through the sort whatever the points, which
holds the bitmap to 32 MiB
+// whatever a damaged leaf says.
+constexpr uint32_t kMaxDocBitsDocId = 1U << 28;
+constexpr size_t kWordsPerContainer = 1024;
+
+// Sets the doc ids in `bits`, which grows by whole containers. Returns false,
leaving `bits` as it
+// was, when one of them is not below `doc_id_end`.
+bool set_doc_bits(std::span<const uint32_t> doc_ids, uint32_t doc_id_end,
+ std::vector<uint64_t>* bits) {
+ uint32_t largest = 0;
+ for (const uint32_t doc_id : doc_ids) {
+ largest = std::max(largest, doc_id);
+ }
+ if (largest >= doc_id_end) {
+ return false;
+ }
+ const size_t words = (static_cast<size_t>(largest >> 16) + 1) *
kWordsPerContainer;
+ if (bits->size() < words) {
+ bits->resize(words);
+ }
+ uint64_t* const data = bits->data();
+ for (const uint32_t doc_id : doc_ids) {
+ data[doc_id >> 6] |= uint64_t {1} << (doc_id & 63);
+ }
+ return true;
+}
+
+// CRoaring 2.1.2 has no call that takes a bitset, so the bits go through
Roaring's published
+// portable format: a cookie, the number of containers, a key and cardinality
- 1 per container, an
+// offset per container, then the containers, up to 4096 doc ids as sorted
16-bit values and more as
+// their 1024 words.
+roaring::Roaring load_doc_bits(std::span<const uint64_t> bits,
std::vector<char>* image) {
+ constexpr uint32_t kPortableCookieNoRuns = 12346;
+ constexpr uint32_t kMaxArrayContainerDocs = 4096;
+ constexpr uint32_t kBitsetContainerBytes = kWordsPerContainer *
sizeof(uint64_t);
+ struct Container {
+ uint32_t key;
+ uint32_t cardinality;
+ uint32_t bytes() const {
+ return cardinality > kMaxArrayContainerDocs
+ ? kBitsetContainerBytes
+ : cardinality *
static_cast<uint32_t>(sizeof(uint16_t));
+ }
+ };
+ std::vector<Container> containers;
+ size_t image_bytes = sizeof(uint32_t) * 2;
+ for (size_t key = 0; key * kWordsPerContainer < bits.size(); ++key) {
+ uint32_t cardinality = 0;
+ for (const uint64_t word : bits.subspan(key * kWordsPerContainer,
kWordsPerContainer)) {
+ cardinality += std::popcount(word);
+ }
+ if (cardinality != 0) {
+ containers.push_back({static_cast<uint32_t>(key), cardinality});
+ image_bytes += sizeof(uint32_t) * 2 + containers.back().bytes();
+ }
+ }
+ image->resize(image_bytes);
+ char* out = image->data();
+ const auto put = [&out](auto value) {
+ std::memcpy(out, &value, sizeof(value));
+ out += sizeof(value);
+ };
+ put(kPortableCookieNoRuns);
+ put(static_cast<uint32_t>(containers.size()));
+ for (const Container& container : containers) {
+ put(static_cast<uint16_t>(container.key));
+ put(static_cast<uint16_t>(container.cardinality - 1));
+ }
+ auto offset = static_cast<uint32_t>(sizeof(uint32_t) * (2 +
containers.size() * 2));
+ for (const Container& container : containers) {
+ put(offset);
+ offset += container.bytes();
+ }
+ for (const Container& container : containers) {
+ const uint64_t* const words = bits.data() + container.key *
kWordsPerContainer;
+ if (container.cardinality > kMaxArrayContainerDocs) {
+ std::memcpy(out, words, kBitsetContainerBytes);
+ out += kBitsetContainerBytes;
+ continue;
+ }
+ for (size_t word = 0; word < kWordsPerContainer; ++word) {
+ for (uint64_t rest = words[word]; rest != 0; rest &= rest - 1) {
+ put(static_cast<uint16_t>(word * 64 + std::countr_zero(rest)));
+ }
+ }
+ }
+ return roaring::Roaring::readSafe(image->data(), image->size());
+}
+
// Validate section extents from the container before allocating read buffers.
Status bkd_reader_corrupted(std::string_view what) {
return Status::Error<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED,
false>("bkd_reader: {}", what);
@@ -304,14 +414,26 @@ Status BkdReader::range(Slice lower, bool
lower_inclusive, Slice upper, bool upp
// bound on its own side.
RETURN_IF_ERROR(
scan_boundary_leaf(first, lower, lower_inclusive, Slice(), true,
hits, scratch));
- // Gather doc IDs from fully covered leaves, sort them, and insert them in
bounded chunks. Leaf order follows values rather than doc IDs, and bounded
chunks limit memory for large ranges.
+ RETURN_IF_ERROR(add_whole_leaves(first + 1, last, hits, scratch));
+ return scan_boundary_leaf(last, Slice(), true, upper, upper_inclusive,
hits, scratch);
+}
+
+Status BkdReader::add_whole_leaves(uint32_t first, uint32_t end,
roaring::Roaring* hits,
+ BkdQueryScratch* scratch) const {
+ // Leaf order follows values rather than doc IDs. Doc IDs the flat bitmap
does not take are
+ // gathered, sorted and inserted in bounded chunks, which limit memory.
constexpr size_t kMaxGatheredDocIds = 1U << 20;
+ const auto doc_bits_end = static_cast<uint32_t>(
+ std::min(static_cast<uint64_t>(end - first) *
block_.header().points_per_leaf *
+ kDocIdsPerPointForDocBits,
+ static_cast<uint64_t>(kMaxDocBitsDocId)));
// The boundary-leaf decode holds Slices INTO scratch->leaf_bytes, which
the
// interior loop is about to overwrite and may reallocate. Cleared so
nothing
// can later read a struct that still looks populated but points at freed
// bytes.
scratch->decoded.clear();
scratch->gathered.clear();
+ scratch->doc_bits.clear();
const auto flush = [&] {
if (scratch->gathered.empty()) {
return;
@@ -320,19 +442,35 @@ Status BkdReader::range(Slice lower, bool
lower_inclusive, Slice upper, bool upp
hits->addMany(scratch->gathered.size(), scratch->gathered.data());
scratch->gathered.clear();
};
- for (uint32_t leaf = first + 1; leaf < last; ++leaf) {
- RETURN_IF_ERROR(read_leaf(leaf, &scratch->leaf_bytes));
- RETURN_IF_ERROR(decode_leaf_doc_ids(Slice(scratch->leaf_bytes),
- block_.header().bytes_per_dim,
block_.leaf(leaf).count,
- &scratch->doc_ids));
- scratch->gathered.insert(scratch->gathered.end(),
scratch->doc_ids.begin(),
- scratch->doc_ids.end());
- if (scratch->gathered.size() >= kMaxGatheredDocIds) {
- flush();
+ for (uint32_t leaf = first; leaf < end;) {
+ const uint32_t read_end = leaves_in_one_read(block_, leaf, end);
+ RETURN_IF_ERROR(read_leaves(leaf, read_end, &scratch->leaf_bytes));
+ const Slice leaves(scratch->leaf_bytes);
+ const uint64_t read_begin = block_.leaf(leaf).offset;
+ for (; leaf < read_end; ++leaf) {
+ const size_t begin = static_cast<size_t>(block_.leaf(leaf).offset
- read_begin);
+ const size_t stop =
+ leaf + 1 < read_end
+ ? static_cast<size_t>(block_.leaf(leaf + 1).offset
- read_begin)
+ : leaves.size();
+ RETURN_IF_ERROR(decode_leaf_doc_ids(
+ leaves.subslice(begin, stop - begin),
block_.header().bytes_per_dim,
+ block_.leaf(leaf).count, &scratch->doc_ids,
&scratch->runs));
+ if (set_doc_bits(scratch->doc_ids, doc_bits_end,
&scratch->doc_bits)) {
+ continue;
+ }
+ scratch->gathered.insert(scratch->gathered.end(),
scratch->doc_ids.begin(),
+ scratch->doc_ids.end());
+ if (scratch->gathered.size() >= kMaxGatheredDocIds) {
+ flush();
+ }
}
}
flush();
- return scan_boundary_leaf(last, Slice(), true, upper, upper_inclusive,
hits, scratch);
+ if (!scratch->doc_bits.empty()) {
+ *hits |= load_doc_bits(scratch->doc_bits, &scratch->bitmap_image);
+ }
+ return Status::OK();
}
Status BkdReader::lookup_many(const std::vector<Slice>& values,
roaring::Roaring* hits) const {
@@ -400,7 +538,7 @@ Status BkdReader::lookup_many(const std::vector<Slice>&
values, roaring::Roaring
std::vector<uint8_t> value_buffer(width);
for (const uint32_t leaf_index : leaves) {
- RETURN_IF_ERROR(read_leaf(leaf_index, &scratch->leaf_bytes));
+ RETURN_IF_ERROR(read_leaves(leaf_index, leaf_index + 1,
&scratch->leaf_bytes));
RETURN_IF_ERROR(decode_leaf_block(Slice(scratch->leaf_bytes), width,
block_.leaf(leaf_index).count,
&scratch->decoded));
const DecodedLeafBlock& leaf = scratch->decoded;
@@ -498,21 +636,21 @@ Status BkdReader::estimate_cardinality(Slice lower, bool
lower_inclusive, Slice
return Status::OK();
}
-Status BkdReader::read_leaf(uint32_t index, std::vector<uint8_t>* buffer)
const {
- const LeafRef leaf = block_.leaf(index);
+Status BkdReader::read_leaves(uint32_t first, uint32_t end,
std::vector<uint8_t>* buffer) const {
+ const uint64_t begin = block_.leaf(first).offset;
// Open-time validation bounds each leaf extent. The leaf decoder rejects
an empty last block.
- const uint64_t end = (index + 1 < block_.leaf_count()) ? block_.leaf(index
+ 1).offset
- :
sections_.data_length;
- const size_t length = static_cast<size_t>(end - leaf.offset);
+ const uint64_t stop =
+ end < block_.leaf_count() ? block_.leaf(end).offset :
sections_.data_length;
+ const auto length = static_cast<size_t>(stop - begin);
buffer->resize(length);
// Use a positioned read so concurrent queries need no shared cursor.
- return file_->read_into(sections_.data_offset + leaf.offset,
buffer->data(), length);
+ return file_->read_into(sections_.data_offset + begin, buffer->data(),
length);
}
Status BkdReader::scan_boundary_leaf(uint32_t index, Slice lower, bool
lower_inclusive, Slice upper,
bool upper_inclusive, roaring::Roaring*
hits,
BkdQueryScratch* scratch) const {
- RETURN_IF_ERROR(read_leaf(index, &scratch->leaf_bytes));
+ RETURN_IF_ERROR(read_leaves(index, index + 1, &scratch->leaf_bytes));
RETURN_IF_ERROR(decode_leaf_block(Slice(scratch->leaf_bytes),
block_.header().bytes_per_dim,
block_.leaf(index).count,
&scratch->decoded));
const DecodedLeafBlock& leaf = scratch->decoded;
diff --git a/be/src/storage/index/inverted/snii/bkd/bkd_reader.h
b/be/src/storage/index/inverted/snii/bkd/bkd_reader.h
index 60fbb13a086..f1709d4a604 100644
--- a/be/src/storage/index/inverted/snii/bkd/bkd_reader.h
+++ b/be/src/storage/index/inverted/snii/bkd/bkd_reader.h
@@ -40,19 +40,25 @@ namespace doris::snii::bkd {
// Caller-owned buffers reused across queries. A new scratch is also valid for
any query.
struct BkdQueryScratch {
- // Raw bytes of the leaf currently being examined, as read from bkd_data.
+ // Raw bytes of the leaves currently being examined, as read from bkd_data.
std::vector<uint8_t> leaf_bytes;
// The boundary-leaf decode (values + doc ids). Keeps its capacity across
// leaves.
DecodedLeafBlock decoded;
// The whole-leaf-hit decode (doc ids only).
std::vector<uint32_t> doc_ids;
+ std::vector<LeafValueRun> runs;
// Doc ids gathered across consecutive whole-leaf hits, SORTED before they
// reach the bitmap. Leaves are ordered by value, so their doc ids arrive
in
// arbitrary order, and roaring inserts sorted input far more cheaply.
std::vector<uint32_t> gathered;
// Ping-pong buffer for the radix sort of `gathered`.
std::vector<uint32_t> radix_scratch;
+ // A wide range sets the doc ids of its whole-leaf hits here instead of
sorting them: one bit
+ // per doc id, in whole roaring containers of 1024 words.
+ std::vector<uint64_t> doc_bits;
+ // The image `doc_bits` is loaded into a bitmap through.
+ std::vector<char> bitmap_image;
// lookup_many's probe values, ordered and deduplicated internally.
std::vector<Slice> probes;
};
@@ -111,8 +117,12 @@ public:
private:
BkdReader(io::FileReader* file, const BkdSections& sections);
- // Reads the leaf extent established by the validated directory.
- Status read_leaf(uint32_t index, std::vector<uint8_t>* buffer) const;
+ // Reads the extents of leaves [first, end), which lie next to each other
in bkd_data, as
+ // established by the validated directory.
+ Status read_leaves(uint32_t first, uint32_t end, std::vector<uint8_t>*
buffer) const;
+ // Decodes the whole-leaf hits between two boundary leaves into `hits`.
+ Status add_whole_leaves(uint32_t first, uint32_t end, roaring::Roaring*
hits,
+ BkdQueryScratch* scratch) const;
// Decodes and filters a boundary leaf, which may contain both matching
and non-matching values.
Status scan_boundary_leaf(uint32_t index, Slice lower, bool
lower_inclusive, Slice upper,
diff --git a/be/src/storage/index/inverted/snii/bkd/leaf_codec.cpp
b/be/src/storage/index/inverted/snii/bkd/leaf_codec.cpp
index 3a2829c9a1a..5f2a9772b59 100644
--- a/be/src/storage/index/inverted/snii/bkd/leaf_codec.cpp
+++ b/be/src/storage/index/inverted/snii/bkd/leaf_codec.cpp
@@ -460,7 +460,14 @@ Status decode_leaf_block(Slice block, uint32_t
bytes_per_dim, uint32_t expected_
Status decode_leaf_doc_ids(Slice block, uint32_t bytes_per_dim, uint32_t
expected_point_count,
std::vector<uint32_t>* doc_ids) {
+ std::vector<LeafValueRun> runs;
+ return decode_leaf_doc_ids(block, bytes_per_dim, expected_point_count,
doc_ids, &runs);
+}
+
+Status decode_leaf_doc_ids(Slice block, uint32_t bytes_per_dim, uint32_t
expected_point_count,
+ std::vector<uint32_t>* doc_ids,
std::vector<LeafValueRun>* runs) {
DORIS_CHECK(doc_ids != nullptr);
+ DORIS_CHECK(runs != nullptr);
DORIS_CHECK_GT(bytes_per_dim, 0U);
ByteSource src(block);
@@ -471,13 +478,13 @@ Status decode_leaf_doc_ids(Slice block, uint32_t
bytes_per_dim, uint32_t expecte
size_t docid_block_end = 0;
RETURN_IF_ERROR(decode_leaf_tail(block, &docid_block_offset,
&docid_block_end));
- std::vector<LeafValueRun> runs;
- RETURN_IF_ERROR(skip_value_area(&src, head, &runs));
+ runs->clear();
+ RETURN_IF_ERROR(skip_value_area(&src, head, runs));
if (src.position() != docid_block_offset) {
return leaf_codec_corrupted("docid_block_offset disagrees with the end
of the value area");
}
return decode_doc_id_block(
- block.subslice(docid_block_offset, docid_block_end -
docid_block_offset), head, runs,
+ block.subslice(docid_block_offset, docid_block_end -
docid_block_offset), head, *runs,
doc_ids);
}
diff --git a/be/src/storage/index/inverted/snii/bkd/leaf_codec.h
b/be/src/storage/index/inverted/snii/bkd/leaf_codec.h
index 8bed6c47239..3edd95ee7e0 100644
--- a/be/src/storage/index/inverted/snii/bkd/leaf_codec.h
+++ b/be/src/storage/index/inverted/snii/bkd/leaf_codec.h
@@ -101,5 +101,8 @@ Status decode_leaf_block(Slice block, uint32_t
bytes_per_dim, uint32_t expected_
// Decodes doc IDs from a fully covered leaf using the tail offset. Validates
the offset and returns the same IDs as decode_leaf_block.
Status decode_leaf_doc_ids(Slice block, uint32_t bytes_per_dim, uint32_t
expected_point_count,
std::vector<uint32_t>* doc_ids);
+// The same, with a caller-owned vector for the leaf's value runs when going
through many leaves.
+Status decode_leaf_doc_ids(Slice block, uint32_t bytes_per_dim, uint32_t
expected_point_count,
+ std::vector<uint32_t>* doc_ids,
std::vector<LeafValueRun>* runs);
} // namespace doris::snii::bkd
diff --git a/be/test/storage/index/inverted/snii/bkd/bkd_reader_test.cpp
b/be/test/storage/index/inverted/snii/bkd/bkd_reader_test.cpp
index f3db4a47ced..bdb13c8b1f4 100644
--- a/be/test/storage/index/inverted/snii/bkd/bkd_reader_test.cpp
+++ b/be/test/storage/index/inverted/snii/bkd/bkd_reader_test.cpp
@@ -22,7 +22,9 @@
#include <algorithm>
#include <cstdint>
#include <cstring>
+#include <limits>
#include <memory>
+#include <numeric>
#include <roaring/roaring.hh>
#include <string>
#include <thread>
@@ -94,6 +96,8 @@ public:
Status read_into(uint64_t offset, uint8_t* out, size_t out_len) override {
reads_.fetch_add(1);
+ bytes_read_.fetch_add(out_len);
+ last_offset_.store(offset);
if (out_len == 0) {
return Status::OK();
}
@@ -107,10 +111,14 @@ public:
uint64_t size() const override { return bytes_.size(); }
uint64_t reads() const { return reads_.load(); }
+ uint64_t bytes_read() const { return bytes_read_.load(); }
+ uint64_t last_offset() const { return last_offset_.load(); }
private:
std::vector<uint8_t> bytes_;
mutable std::atomic<uint64_t> reads_ {0};
+ mutable std::atomic<uint64_t> bytes_read_ {0};
+ mutable std::atomic<uint64_t> last_offset_ {0};
};
// ---------------------------------------------------------------------------
@@ -244,6 +252,10 @@ std::vector<uint32_t> to_sorted_vector(const
roaring::Roaring& bitmap) {
if (!status.ok()) {
return ::testing::AssertionFailure() << describe(interval) << "
failed: " << status;
}
+ const char* reason = "";
+ if (!roaring::api::roaring_bitmap_internal_validate(&hits.roaring,
&reason)) {
+ return ::testing::AssertionFailure() << describe(interval) << " built:
" << reason;
+ }
const std::vector<uint32_t> got = to_sorted_vector(hits);
const std::vector<uint32_t> expected = brute_force(points, interval);
if (got != expected) {
@@ -512,7 +524,7 @@ TEST(BkdReaderTest,
IntervalsEntirelyOutsideTheGlobalBoundsCostNoIo) {
EXPECT_EQ(opened.file->reads(), reads_after_open);
}
-TEST(BkdReaderTest, ReadsExactlyOnePositionedReadPerTouchedLeaf) {
+TEST(BkdReaderTest, ReadsOnlyTheTouchedLeavesAndWholeLeafHitsInOneRead) {
std::vector<Point> points;
for (uint32_t i = 0; i < 40; ++i) {
points.push_back(Point {static_cast<int64_t>(i), i});
@@ -521,16 +533,211 @@ TEST(BkdReaderTest,
ReadsExactlyOnePositionedReadPerTouchedLeaf) {
ASSERT_TRUE(open_index(points, 4, &opened).ok());
ASSERT_EQ(opened.reader->leaf_count(), 10U);
+ // One leaf, one read.
+ uint64_t touched_bytes = 0;
+ for (int64_t leaf = 2; leaf <= 6; ++leaf) {
+ const uint64_t reads_before = opened.file->reads();
+ const uint64_t bytes_before = opened.file->bytes_read();
+ EXPECT_TRUE(
+ matches_brute_force(*opened.reader, points, closed(4 * leaf +
1, 4 * leaf + 2)));
+ EXPECT_EQ(opened.file->reads() - reads_before, 1U);
+ touched_bytes += opened.file->bytes_read() - bytes_before;
+ }
+
// Leaf j holds values [4j, 4j+3], so [10, 25] spans leaves 2..6 -- two
- // boundary leaves plus three whole-leaf hits.
- const uint64_t before = opened.file->reads();
+ // boundary leaves plus three whole-leaf hits, which take one read
together.
+ const uint64_t reads_before = opened.file->reads();
+ const uint64_t bytes_before = opened.file->bytes_read();
EXPECT_TRUE(matches_brute_force(*opened.reader, points, closed(10, 25)));
- EXPECT_EQ(opened.file->reads() - before, 5U);
+ EXPECT_EQ(opened.file->reads() - reads_before, 3U);
+ EXPECT_EQ(opened.file->bytes_read() - bytes_before, touched_bytes);
+}
- // One leaf, one read.
- const uint64_t before_single = opened.file->reads();
- EXPECT_TRUE(matches_brute_force(*opened.reader, points, closed(13, 14)));
- EXPECT_EQ(opened.file->reads() - before_single, 1U);
+// One read takes at most about 1 MiB of whole-leaf hits, and all of them are
still read.
+TEST(BkdReaderTest, ReadsOfWholeLeafHitsAreBounded) {
+ Rng rng(7);
+ std::vector<Point> points;
+ for (uint32_t i = 0; i < 400000; ++i) {
+ points.push_back(Point {.value = rng.next_in(0, int64_t {1} << 40),
.doc_id = i});
+ }
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(points, 512, &opened).ok());
+ const uint64_t data_length = opened.container.sections.data_length;
+ ASSERT_GT(data_length, 2U << 20);
+
+ const uint64_t reads_before = opened.file->reads();
+ const uint64_t bytes_before = opened.file->bytes_read();
+ EXPECT_TRUE(matches_brute_force(*opened.reader, points, Interval {}));
+ const uint64_t reads = opened.file->reads() - reads_before;
+ EXPECT_EQ(opened.file->bytes_read() - bytes_before, data_length);
+ EXPECT_GE(reads, 2U + data_length / (1U << 20));
+ EXPECT_LE(reads, 4U + data_length / (1U << 20));
+}
+
+// Doc ids of whole-leaf hits go through a flat bitmap when the range is wide
and through a sort
+// when it is narrow, or when a doc id is too large for the bitmap.
+TEST(BkdReaderTest, WideAndNarrowRangesMatchBruteForceForEveryShapeOfDocIds) {
+ constexpr uint32_t kDocs = 60000;
+ constexpr int64_t kValues = 100000;
+ constexpr uint32_t kBitmapLimit = 1U << 28;
+ Rng rng(20261030);
+ const auto with_values = [&rng](const std::vector<uint32_t>& doc_ids) {
+ std::vector<Point> points;
+ for (const uint32_t doc_id : doc_ids) {
+ points.push_back(Point {.value = rng.next_in(0, kValues), .doc_id
= doc_id});
+ }
+ return points;
+ };
+
+ std::vector<std::vector<Point>> shapes;
+ std::vector<uint32_t> dense(kDocs);
+ std::iota(dense.begin(), dense.end(), 0U);
+ shapes.push_back(with_values(dense));
+ std::vector<uint32_t> sparse;
+ for (uint32_t i = 0; i < kDocs; ++i) {
+ sparse.push_back(i * 97);
+ }
+ shapes.push_back(with_values(sparse));
+ std::vector<uint32_t> many_values_per_doc;
+ for (uint32_t i = 0; i < kDocs / 3; ++i) {
+ many_values_per_doc.insert(many_values_per_doc.end(), 3, i);
+ }
+ shapes.push_back(with_values(many_values_per_doc));
+ // Doc ids on both sides of the bitmap's limit, in the same leaves.
+ std::vector<uint32_t> around_limit = dense;
+ for (uint32_t i = 0; i < 2000; ++i) {
+ around_limit.push_back(kBitmapLimit - 2000 + i);
+ }
+ for (uint32_t i = 0; i < 2000; ++i) {
+ around_limit.push_back(kBitmapLimit + i);
+ }
+ for (uint32_t i = 2000; i > 0; --i) {
+ around_limit.push_back(std::numeric_limits<uint32_t>::max() - i + 1);
+ }
+ shapes.push_back(with_values(around_limit));
+
+ for (size_t shape = 0; shape < shapes.size(); ++shape) {
+ SCOPED_TRACE("shape " + std::to_string(shape));
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(shapes[shape], 64, &opened).ok());
+ for (const Interval& interval :
+ {Interval {}, closed(0, kValues / 2), closed(kValues / 4,
kValues),
+ closed(kValues / 3, kValues / 3 + 40), closed(kValues / 3,
kValues / 3 + 400),
+ closed(kValues / 3, kValues / 3 + 2000)}) {
+ EXPECT_TRUE(matches_brute_force(*opened.reader, shapes[shape],
interval));
+ }
+ }
+}
+
+// Few points at high doc ids would make a long bitmap with hardly a bit set,
however wide the range
+// and however few documents the index counts, so they take the sort.
+TEST(BkdReaderTest, SparseDocIdsStayOutOfTheFlatBitmap) {
+ constexpr size_t kBytesPerPoint = 32;
+ constexpr size_t kContainerBytes = 8192;
+ constexpr uint32_t kBitmapLimit = 1U << 28;
+ Rng rng(20261031);
+ std::vector<std::vector<Point>> shapes;
+ // One document just below the bitmap's limit, its values spanning three
leaves.
+ std::vector<Point> one_document;
+ for (int64_t value = 0; value < 3 * 8; ++value) {
+ one_document.push_back(Point {.value = value, .doc_id = kBitmapLimit -
1});
+ }
+ shapes.push_back(one_document);
+ // A column with a value in one row of a thousand.
+ std::vector<Point> mostly_null;
+ for (uint32_t i = 0; i < 6000; ++i) {
+ mostly_null.push_back(Point {.value = rng.next_in(0, 100000), .doc_id
= i * 1000});
+ }
+ shapes.push_back(mostly_null);
+
+ for (size_t shape = 0; shape < shapes.size(); ++shape) {
+ SCOPED_TRACE("shape " + std::to_string(shape));
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(shapes[shape], 8, &opened).ok());
+ EXPECT_TRUE(matches_brute_force(*opened.reader, shapes[shape],
Interval {}));
+ BkdQueryScratch scratch;
+ roaring::Roaring hits;
+ ASSERT_TRUE(opened.reader->range(Slice(), true, Slice(), true, &hits,
&scratch).ok());
+ EXPECT_LE(scratch.doc_bits.size() * sizeof(uint64_t),
+ shapes[shape].size() * kBytesPerPoint + kContainerBytes);
+ }
+}
+
+// However many points pay for it, the bitmap stops at its limit. Values
follow doc ids here, so
+// whole leaves lie below the limit and whole leaves above it.
+TEST(BkdReaderTest, FlatBitmapStopsAtItsLimit) {
+ constexpr uint32_t kBitmapLimit = 1U << 28;
+ constexpr uint32_t kPoints = kBitmapLimit / 256 + 50000;
+ std::vector<Point> points;
+ points.reserve(kPoints);
+ for (uint32_t i = 0; i < kPoints; ++i) {
+ points.push_back(Point {.value = i, .doc_id = i * 256});
+ }
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(points, 512, &opened).ok());
+ EXPECT_TRUE(matches_brute_force(*opened.reader, points, Interval {}));
+ BkdQueryScratch scratch;
+ roaring::Roaring hits;
+ ASSERT_TRUE(opened.reader->range(Slice(), true, Slice(), true, &hits,
&scratch).ok());
+ EXPECT_FALSE(scratch.doc_bits.empty());
+ EXPECT_LE(scratch.doc_bits.size() * sizeof(uint64_t), kBitmapLimit / 8);
+}
+
+// A container holds up to 4096 doc ids as an array and more as a bitset.
+TEST(BkdReaderTest, WideRangesBuildBothKindsOfContainer) {
+ std::vector<Point> points;
+ const auto add_docs = [&points](uint32_t first, uint32_t count, int64_t
value) {
+ for (uint32_t i = 0; i < count; ++i) {
+ points.push_back(Point {.value = value + i, .doc_id = first + i *
3});
+ }
+ };
+ // These containers fill from whole leaves alone: exactly an array's
limit, one past it, a single
+ // document and many.
+ add_docs(0, 4096, 1000);
+ add_docs(1U << 16, 4097, 10000);
+ add_docs(2U << 16, 1, 20000);
+ add_docs(3U << 16, 20000, 30000);
+ // The lowest and highest values, so that the boundary leaves hold nothing
but these.
+ add_docs(5U << 16, 32, 0);
+ add_docs(6U << 16, 64, 100000);
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(points, 32, &opened).ok());
+ EXPECT_TRUE(matches_brute_force(*opened.reader, points, Interval {}));
+
+ roaring::Roaring hits;
+ ASSERT_TRUE(opened.reader->range(Slice(), true, Slice(), true,
&hits).ok());
+ roaring::api::roaring_statistics_t stats;
+ roaring::api::roaring_bitmap_statistics(&hits.roaring, &stats);
+ EXPECT_EQ(stats.n_array_containers, 4U);
+ EXPECT_EQ(stats.n_bitset_containers, 2U);
+ EXPECT_EQ(hits.cardinality(), points.size());
+}
+
+// A damaged leaf in the middle of one read is found like any other.
+TEST(BkdReaderTest, DamagedWholeLeafHitIsReportedFromInsideARead) {
+ std::vector<Point> points;
+ for (uint32_t i = 0; i < 400; ++i) {
+ points.push_back(Point {.value = static_cast<int64_t>(i), .doc_id =
i});
+ }
+ OpenedIndex opened;
+ ASSERT_TRUE(open_index(points, 4, &opened).ok());
+ // Measures one leaf: value 201 is inside leaf 50.
+ const uint64_t bytes_before = opened.file->bytes_read();
+ ASSERT_TRUE(matches_brute_force(*opened.reader, points, closed(201, 202)));
+ const uint64_t leaf_length = opened.file->bytes_read() - bytes_before;
+ const uint64_t leaf_offset = opened.file->last_offset();
+
+ Container damaged = opened.container;
+ damaged.image[leaf_offset + leaf_length - 1] = 0xFF;
+ CountingFileReader file(damaged.image);
+ std::unique_ptr<BkdReader> reader;
+ ASSERT_TRUE(BkdReader::open(&file, damaged.sections, &reader).ok());
+
+ const std::vector<uint8_t> lower = sortable_bigint(0);
+ const std::vector<uint8_t> upper = sortable_bigint(399);
+ roaring::Roaring hits;
+ const Status status = reader->range(Slice(lower), true, Slice(upper),
true, &hits);
+ EXPECT_TRUE(status.is<ErrorCode::INVERTED_INDEX_FILE_CORRUPTED>()) <<
status;
}
// ---------------------------------------------------------------------------
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
