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 12f49adad21 [improvement](be) Add sorted docids to roaring bitmaps a
container at a time (#69895)
12f49adad21 is described below
commit 12f49adad21275637b5230dd195c0ad557956c4d
Author: Jack <[email protected]>
AuthorDate: Mon Nov 2 09:20:47 2026 +0800
[improvement](be) Add sorted docids to roaring bitmaps a container at a
time (#69895)
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: An equality filter on an indexed string column, such as
`tenant = 'x'`, collects
its whole posting list into a roaring bitmap, and a value can cover tens
of percent of the table.
`RoaringDocIdSink::append_sorted` gets those documents in sorted windows
that mostly fall in one 64K
container, but `Roaring::addMany` goes through the container's type for
every document. On a 99M-row
table that was about 20% of the SNII stack samples of a filtered phrase
prefix query.
`append_sorted` now splits a span at container boundaries and fills each
container directly:
- A bitset container gets one write per 64-bit word, with the bits
gathered in a register, because
neighbouring documents mostly share a word and a store per document
would wait on the one before
it.
- An array container gets its tail appended in one loop, up to its limit
of 4096. The next document
turns it into a bitset, which then takes the rest.
- Anything else goes through `addMany` as before: run containers,
documents that fall inside an
existing array, and spans that are not strictly ascending, which the
sink does not rule out and a
damaged posting could produce.
The containers end up the same as with `addMany`.
Two things to look at in review:
- The sink is shared by every inverted index format, so V3 queries take
the same path.
- The code writes to CRoaring's container structs. `null_bitmap.cpp`
already includes those headers,
but only reads their sizes, so an upgrade of CRoaring has to keep this
code in mind. CRoaring 2.1.2
has no public call that adds a sorted run to a container.
| Query (99M rows), new/previous | SNII hot | V3 hot | SNII cold |
|---|---|---|---|
| phrase with tenant, app, type and status | 0.80 / 0.80 / 0.78 | 0.90 |
0.95 |
| phrase with a latency filter | 0.78 / 0.77 / 0.78 | 0.78 | |
| MATCH_ALL with the same four filters | 0.79 / 0.77 / 0.81 | 0.95 |
0.98 |
| filters and a latency range, no text | 0.83 / 0.87 / 0.88 | 0.80 | |
| phrase prefix with tenant and app | 0.93 / 0.92 / 0.92 | 0.93 | 0.98 |
| top-50 with tenant and payload equalities | 0.77 | 0.82 | |
| top-50 tool failures | 0.93 | 0.77 | |
| the other 18 queries | 0.89-1.04 | 0.91-1.04 | |
Hot: both versions interleaved in one BE process, three runs where three
are shown, on a host with a
load of about 100 to 140 from other builds. An earlier round at a load
of 230 to 400 read up to 1.41
on some queries that do not gain; their reruns gave 0.95-1.07. Cold: BE
restarted and the index files
evicted before every run, configuration order alternated, 5 runs each;
the change only saves CPU, so
cold runs stay about level. The build also had #69879, #69882, #69887
and #69891, with
`snii_inline_read_max_segments` at 16.
---
.../inverted/query/exec/roaring_docid_sink.cpp | 131 +++++++++++++++
.../index/inverted/query/exec/roaring_docid_sink.h | 7 +-
.../query/exec/roaring_docid_sink_test.cpp | 184 +++++++++++++++++++++
3 files changed, 316 insertions(+), 6 deletions(-)
diff --git a/be/src/storage/index/inverted/query/exec/roaring_docid_sink.cpp
b/be/src/storage/index/inverted/query/exec/roaring_docid_sink.cpp
new file mode 100644
index 00000000000..87ad0b97d40
--- /dev/null
+++ b/be/src/storage/index/inverted/query/exec/roaring_docid_sink.cpp
@@ -0,0 +1,131 @@
+// 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.
+
+#include "storage/index/inverted/query/exec/roaring_docid_sink.h"
+
+#include <algorithm>
+#include <bit>
+#include <cstddef>
+
+// clang-format off
+// CRoaring's public header defines ROARING_CONTAINER_T; its internal headers
undefine it.
+#include "roaring/roaring.hh"
+#include "roaring/containers/containers.h"
+// clang-format on
+
+namespace doris::index_query {
+namespace {
+
+using roaring::api::roaring_bitmap_add_bulk;
+using roaring::api::roaring_bitmap_add_many;
+using roaring::api::roaring_bitmap_t;
+using roaring::api::roaring_bulk_context_t;
+using roaring::internal::array_container_t;
+using roaring::internal::bitset_container_t;
+
+// A sink only promises sorted spans. Equal neighbours, or an unsorted span
from a damaged posting,
+// would break a sorted array container and could put a document in the wrong
chunk.
+bool all_strictly_ascending(std::span<const uint32_t> docids) {
+ uint32_t out_of_order = 0;
+ for (size_t i = 1; i < docids.size(); ++i) {
+ out_of_order |= static_cast<uint32_t>(docids[i - 1] >= docids[i]);
+ }
+ return out_of_order == 0;
+}
+
+// Gathers the bits of one 64-bit word in a register and writes it once:
consecutive documents
+// mostly share a word, and a store per document would wait on the one before
it.
+void set_sorted_bits(bitset_container_t* bitset, std::span<const uint32_t>
docids) {
+ uint64_t* const words = bitset->words;
+ int32_t added = 0;
+ size_t i = 0;
+ while (i < docids.size()) {
+ const uint32_t word = (docids[i] & 0xFFFF) >> 6;
+ uint64_t bits = 0;
+ do {
+ bits |= uint64_t {1} << (docids[i] & 63);
+ ++i;
+ } while (i < docids.size() && ((docids[i] & 0xFFFF) >> 6) == word);
+ added += std::popcount(bits & ~words[word]);
+ words[word] |= bits;
+ }
+ bitset->cardinality += added;
+}
+
+// Appends to the tail of an array container, which must stay sorted and
within its size limit.
+void append_sorted_to_array(array_container_t* array, std::span<const
uint32_t> docids) {
+ const int32_t cardinality = array->cardinality;
+ const auto total = cardinality + static_cast<int32_t>(docids.size());
+ if (total > array->capacity) {
+ roaring::internal::array_container_grow(array, total,
/*preserve=*/true);
+ }
+ uint16_t* const out = array->array + cardinality;
+ for (size_t i = 0; i < docids.size(); ++i) {
+ out[i] = static_cast<uint16_t>(docids[i]);
+ }
+ array->cardinality = total;
+}
+
+// Adds strictly ascending documents of one 64K chunk. roaring_bitmap_add_bulk
finds or makes the
+// container, and changes its type when the document needs that; the rest go
straight into it.
+void add_sorted_chunk(roaring_bitmap_t* bitmap, std::span<const uint32_t>
docids) {
+ while (!docids.empty()) {
+ roaring_bulk_context_t context {};
+ roaring_bitmap_add_bulk(bitmap, &context, docids.front());
+ docids = docids.subspan(1);
+ if (context.typecode == BITSET_CONTAINER_TYPE) {
+ set_sorted_bits(CAST_bitset(context.container), docids);
+ return;
+ }
+ if (docids.empty()) {
+ return;
+ }
+ auto* array = CAST_array(context.container);
+ if (context.typecode != ARRAY_CONTAINER_TYPE ||
+ array->array[array->cardinality - 1] >=
static_cast<uint16_t>(docids.front())) {
+ roaring_bitmap_add_many(bitmap, docids.size(), docids.data());
+ return;
+ }
+ // Up to the limit of an array: the next document, if any, turns the
container to a bitset.
+ const size_t room = roaring::internal::DEFAULT_MAX_SIZE -
array->cardinality;
+ const size_t count = std::min(docids.size(), room);
+ append_sorted_to_array(array, docids.first(count));
+ docids = docids.subspan(count);
+ }
+}
+
+} // namespace
+
+// addMany goes through the container's type for every document, while a
posting list is decoded in
+// windows of documents that are mostly in one container.
+Status RoaringDocIdSink::append_sorted(std::span<const uint32_t> docids) {
+ if (!all_strictly_ascending(docids)) {
+ bitmap_.addMany(docids.size(), docids.data());
+ return Status::OK();
+ }
+ while (!docids.empty()) {
+ const uint32_t chunk = docids.front() >> 16;
+ const auto chunk_end = std::ranges::partition_point(
+ docids, [chunk](uint32_t docid) { return docid >> 16 == chunk;
});
+ const auto count = static_cast<size_t>(chunk_end - docids.begin());
+ add_sorted_chunk(&bitmap_.roaring, docids.first(count));
+ docids = docids.subspan(count);
+ }
+ return Status::OK();
+}
+
+} // namespace doris::index_query
diff --git a/be/src/storage/index/inverted/query/exec/roaring_docid_sink.h
b/be/src/storage/index/inverted/query/exec/roaring_docid_sink.h
index dfa07cea0d1..7290eecbdc6 100644
--- a/be/src/storage/index/inverted/query/exec/roaring_docid_sink.h
+++ b/be/src/storage/index/inverted/query/exec/roaring_docid_sink.h
@@ -32,12 +32,7 @@ public:
void append(uint32_t docid) { bitmap_.add(docid); }
- Status append_sorted(std::span<const uint32_t> docids) override {
- if (!docids.empty()) {
- bitmap_.addMany(docids.size(), docids.data());
- }
- return Status::OK();
- }
+ Status append_sorted(std::span<const uint32_t> docids) override;
Status append_range(uint32_t first, uint64_t last_exclusive) override {
if (last_exclusive >
static_cast<uint64_t>(std::numeric_limits<uint32_t>::max()) + 1) {
diff --git
a/be/test/storage/index/inverted/query/exec/roaring_docid_sink_test.cpp
b/be/test/storage/index/inverted/query/exec/roaring_docid_sink_test.cpp
new file mode 100644
index 00000000000..088884fb957
--- /dev/null
+++ b/be/test/storage/index/inverted/query/exec/roaring_docid_sink_test.cpp
@@ -0,0 +1,184 @@
+// 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.
+
+#include "storage/index/inverted/query/exec/roaring_docid_sink.h"
+
+#include <gtest/gtest.h>
+
+#include <algorithm>
+#include <cstdint>
+#include <limits>
+#include <numeric>
+#include <random>
+#include <span>
+#include <string>
+#include <vector>
+
+namespace doris::index_query {
+namespace {
+
+using Spans = std::vector<std::vector<uint32_t>>;
+
+// The sink must leave exactly what adding the documents one by one leaves, in
containers that hold
+// to CRoaring's own invariants: sorted arrays, cardinalities that match their
bits.
+void ExpectSameAsAddingOneByOne(const roaring::Roaring& start, const Spans&
spans) {
+ roaring::Roaring expected = start;
+ roaring::Roaring actual = start;
+ RoaringDocIdSink sink(actual);
+ for (const auto& span : spans) {
+ for (const uint32_t docid : span) {
+ expected.add(docid);
+ }
+ ASSERT_TRUE(sink.append_sorted(span).ok());
+ }
+ EXPECT_EQ(actual.cardinality(), expected.cardinality());
+ EXPECT_TRUE(actual == expected);
+ const char* reason = "";
+
EXPECT_TRUE(roaring::api::roaring_bitmap_internal_validate(&actual.roaring,
&reason)) << reason;
+}
+
+Spans Batches(const std::vector<uint32_t>& docids, size_t batch) {
+ Spans spans;
+ for (size_t off = 0; off < docids.size(); off += batch) {
+ const size_t end = std::min(docids.size(), off + batch);
+ spans.emplace_back(docids.begin() + off, docids.begin() + end);
+ }
+ return spans;
+}
+
+std::vector<uint32_t> Iota(uint32_t first, uint32_t count) {
+ std::vector<uint32_t> docids(count);
+ std::iota(docids.begin(), docids.end(), first);
+ return docids;
+}
+
+roaring::api::roaring_statistics_t StatsOf(const roaring::Roaring& bitmap) {
+ roaring::api::roaring_statistics_t stats;
+ roaring::api::roaring_bitmap_statistics(&bitmap.roaring, &stats);
+ return stats;
+}
+
+// Densities on both sides of the array limit, documents spread evenly or in
bursts, batches from one
+// document to the whole posting.
+TEST(RoaringDocIdSinkTest, MatchesSingleAddsForRandomPostings) {
+ std::mt19937 rng(20261030);
+ for (const double density : {0.0005, 0.02, 0.0625, 0.07, 0.125, 0.4, 0.9})
{
+ std::bernoulli_distribution take(density);
+ for (const bool bursts : {false, true}) {
+ const uint32_t step = bursts ? 2000 : 1;
+ std::vector<uint32_t> docids;
+ for (uint32_t doc = 0; doc < 400000; doc += step) {
+ if (take(rng)) {
+ for (uint32_t i = 0; i < step; ++i) {
+ docids.push_back(doc + i);
+ }
+ }
+ }
+ for (const size_t batch : {size_t {1}, size_t {7}, size_t {1024},
docids.size() + 1}) {
+ SCOPED_TRACE("density=" + std::to_string(density) + " bursts="
+
+ std::to_string(bursts) + " batch=" +
std::to_string(batch));
+ ExpectSameAsAddingOneByOne({}, Batches(docids, batch));
+ }
+ }
+ }
+}
+
+// An array holds at most 4096 documents. One batch that ends at the limit
leaves an array; one that
+// crosses it, at any point, leaves a bitset holding every document.
+TEST(RoaringDocIdSinkTest, TurnsAnArrayIntoABitsetAtItsLimit) {
+ roaring::Roaring at_limit;
+ RoaringDocIdSink at_limit_sink(at_limit);
+ ASSERT_TRUE(at_limit_sink.append_sorted(Iota(0, 4096)).ok());
+ EXPECT_EQ(StatsOf(at_limit).n_array_containers, 1U);
+ EXPECT_EQ(at_limit.cardinality(), 4096U);
+
+ for (const uint32_t count : {4097U, 4098U, 5000U, 65536U}) {
+ const std::vector<uint32_t> docids = Iota(0, count);
+ ExpectSameAsAddingOneByOne({}, {docids});
+ roaring::Roaring crossed;
+ RoaringDocIdSink sink(crossed);
+ ASSERT_TRUE(sink.append_sorted(docids).ok());
+ EXPECT_EQ(StatsOf(crossed).n_bitset_containers, 1U);
+ }
+ // The limit is reached by the document that the bulk add puts in on its
own.
+ ExpectSameAsAddingOneByOne({}, {Iota(0, 4095), {5000}, {5001}, Iota(6000,
3000)});
+ ExpectSameAsAddingOneByOne({}, {Iota(0, 4096), {5000, 5001}});
+}
+
+TEST(RoaringDocIdSinkTest, MergesIntoExistingContainers) {
+ const std::vector<uint32_t> docids = Iota(1000, 3000);
+
+ // Array with documents after the batch, and one with a document inside it.
+ roaring::Roaring array_after;
+ array_after.add(60000);
+ ExpectSameAsAddingOneByOne(array_after, {docids});
+ roaring::Roaring array_inside;
+ array_inside.add(1500);
+ ExpectSameAsAddingOneByOne(array_inside, {docids});
+ roaring::Roaring array_before;
+ array_before.add(999);
+ ExpectSameAsAddingOneByOne(array_before, {docids});
+
+ // Bitset that already holds some of the batch: those must not be counted
twice.
+ roaring::Roaring bitset;
+ for (uint32_t doc = 0; doc < 20000; doc += 3) {
+ bitset.add(doc);
+ }
+ ASSERT_EQ(StatsOf(bitset).n_bitset_containers, 1U);
+ ExpectSameAsAddingOneByOne(bitset, {docids});
+
+ // Run container.
+ roaring::Roaring runs;
+ runs.addRange(500, 40000);
+ runs.runOptimize();
+ ASSERT_EQ(StatsOf(runs).n_run_containers, 1U);
+ ExpectSameAsAddingOneByOne(runs, {docids, Iota(39000, 3000)});
+}
+
+// A streamed union hands over independently sorted spans, so documents repeat
across them.
+TEST(RoaringDocIdSinkTest, UnionsIndependentlySortedSpans) {
+ std::mt19937 rng(7);
+ Spans spans;
+ for (int term = 0; term < 20; ++term) {
+ std::vector<uint32_t> docids;
+ for (uint32_t doc = rng() % 50; doc < 200000; doc += 1 + rng() % 30) {
+ docids.push_back(doc);
+ }
+ spans.push_back(std::move(docids));
+ }
+ ExpectSameAsAddingOneByOne({}, spans);
+}
+
+TEST(RoaringDocIdSinkTest, KeepsDocumentsOfNeighbouringChunksApart) {
+ ExpectSameAsAddingOneByOne({}, {{65534, 65535, 65536, 65537, 131071,
131072}});
+ constexpr uint32_t kLast = std::numeric_limits<uint32_t>::max();
+ ExpectSameAsAddingOneByOne({}, {{0, 1, kLast - 65536, kLast - 65535, kLast
- 1, kLast}});
+ ExpectSameAsAddingOneByOne({}, {{}, {kLast}, {}});
+}
+
+// A sink only promises sorted spans, and a damaged posting may not even be
that: every document
+// must still land in its own chunk, and an array must stay free of repeats.
+TEST(RoaringDocIdSinkTest, AcceptsSpansThatAreNotStrictlyAscending) {
+ ExpectSameAsAddingOneByOne({}, {{5, 5, 6, 6, 6, 7}});
+ ExpectSameAsAddingOneByOne({}, {{70000, 3, 140000, 2, 2, 70001}});
+ std::vector<uint32_t> repeated = Iota(0, 5000);
+ repeated.insert(repeated.begin() + 2500, 2499);
+ ExpectSameAsAddingOneByOne({}, {repeated});
+}
+
+} // namespace
+} // namespace doris::index_query
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
