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 31a2697f213 [improvement](be) Run-optimize the SNII NULL bitmap before
serializing it (#69727)
31a2697f213 is described below
commit 31a2697f21307e287026f3341287b00f3a1e7678
Author: Jack <[email protected]>
AuthorDate: Thu Oct 29 09:07:14 2026 +0800
[improvement](be) Run-optimize the SNII NULL bitmap before serializing it
(#69727)
### What problem does this PR solve?
Issue Number: None
Related PR: None
Problem Summary: `NullBitmapWriter` never ran `runOptimize()` before
serializing the NULL bitmap, while the V2 inverted index writer does.
Runs of NULL rows, which is the usual shape of a path that is absent
from most rows of a sparse VARIANT column, were stored as plain array or
bitset containers: up to 8 KiB per 65536 rows instead of a few bytes,
once per index. `serialization_sizes()` now optimizes first, and
`finish()` sizes itself through it, so the sizes that callers reserve
against and the bytes written still agree.
For a 20-million-row segment, an all-NULL bitmap goes from 2.5 MB to 4.3
KB, and a bitmap of alternating NULL and non-NULL runs of 1 to 5000 rows
goes from 2.5 MB to 19.8 KB. A random bitmap is unchanged. Opening the
all-NULL section goes from 1.04 ms to 0.01 ms. The cost is one pass over
the containers per call, about 0.5 ms for a random 20-million-row
bitmap, and it is paid twice per index at finish.
### Release note
SNII indexes on columns with long runs of NULL rows take less space.
### Compatibility
- The bytes are the standard Roaring portable serialization, as before.
The only difference is that a container may now be a run container
(cookie 12347), which the V2 writer's NULL bitmaps have always been
allowed to contain.
- A reader needs nothing new. `parse_null_bitmap` already accepts both
portable cookies, `decoded_memory_bytes` already sizes
`run_container_t`, and the SNII readers call `runOptimize()` on the
in-memory copy after loading, so a reader holds the same structure
whether or not the file had runs. `null_bitmap.cpp` and `null_bitmap.h`
are identical on master and on the branch-4.2 tip, so a released BE
reads files written with this change, and the change backports without
conflicts.
- Sizing: `serialization_sizes()` optimizes before it measures and
`finish()` sizes itself through it, so the `DORIS_CHECK_EQ` between the
sizes and the bytes written holds. The new unit test serializes runs
through both and reads them back.
### Performance
Offline benchmark of the real `null_bitmap.cpp` (`-O3`, one pinned core,
20-million-row bitmap, best of 3 interleaved rounds):
| shape | bytes old -> new | `serialization_sizes` (new) | `finish` old
-> new | reader `open` old -> new | `copy_to` old -> new | `col IS NOT
NULL` row set (and-not) old -> new |
|---|---|---|---|---|---|---|
| all NULL | 2,509,225 -> 4,340 | 0.68 ms | 2.53 -> 0.02 ms | 1.04 ->
0.01 ms | 0.48 -> 0.01 ms | 0.41 -> 0.02 ms |
| alternating runs of 1 to 5000 rows | 2,509,225 -> 19,810 | 0.77 ms |
2.49 -> 0.05 ms | 1.04 -> 0.03 ms | 0.48 -> 0.02 ms | 0.73 -> 0.03 ms |
| random 1% | 402,379 (same) | 0.05 ms | 0.37 -> 0.42 ms | 0.18 -> 0.20
ms | 0.09 -> 0.09 ms | 0.33 -> 0.39 ms |
| random 10% | 2,503,417 (same) | 0.45 ms | 2.39 -> 2.87 ms | 1.03 ->
1.11 ms | 0.48 -> 0.49 ms | 0.74 -> 0.70 ms |
| random 50% | 2,509,225 (same) | 0.48 ms | 2.50 -> 2.98 ms | 1.04 ->
1.11 ms | 0.48 -> 0.50 ms | 0.74 -> 0.71 ms |
- Write side: one pass over the containers per `serialization_sizes()`
call, 0.05 to 0.8 ms for 20 million rows. It runs twice per index at
finish: `LogicalIndexWriter::finalize_build` sizes the section to
reserve memory for it, then `finish()` sizes it again. For a bitmap with
runs the second pass has nothing left to convert (`finish` above is 0.02
to 0.05 ms); for a random one it repeats the scan. On a random bitmap,
where there are no runs to find, that is the whole effect: about +0.5 ms
per pass, per index and segment.
- Read side: no change for bitmaps without runs. Bitmaps with runs are
smaller to read from disk and cheaper to open and combine.
- One operation is slower on run containers: `NullBitmapReader::is_null`
(1,000,000 random probes, 48.9 -> 77.0 ms for the alternating shape,
since a run container is searched, not indexed). It has no production
caller; the readers use `copy_to` and `append_docids`.
---
.../index/inverted/snii/format/null_bitmap.cpp | 6 +++++
.../inverted/snii/format/null_bitmap_test.cpp | 31 ++++++++++++++++++++++
2 files changed, 37 insertions(+)
diff --git a/be/src/storage/index/inverted/snii/format/null_bitmap.cpp
b/be/src/storage/index/inverted/snii/format/null_bitmap.cpp
index 12d35c8b4e4..78eb5c55a6d 100644
--- a/be/src/storage/index/inverted/snii/format/null_bitmap.cpp
+++ b/be/src/storage/index/inverted/snii/format/null_bitmap.cpp
@@ -182,6 +182,12 @@ Status NullBitmapWriter::serialization_sizes(uint32_t
doc_count,
return Status::Error<ErrorCode::INVALID_ARGUMENT, false>(
"null bitmap: null serialization size output");
}
+ // Rewrites the containers into their smallest form, as the V2 writer does
before it serializes.
+ // Runs of NULL rows (a path that is absent from most rows of a sparse
column) are the common
+ // case, and as plain array or bitset containers they cost about 8 KiB per
65536 rows instead
+ // of a few bytes. This is the one place that fixes the serialized size,
and finish() sizes
+ // itself through here, so the sizes reported to callers and the bytes
written always agree.
+ bitmap_->runOptimize();
const size_t roaring_bytes = bitmap_->getSizeInBytes();
const size_t prefix_bytes = varint_len(doc_count) +
varint_len(roaring_bytes);
if (roaring_bytes > std::numeric_limits<size_t>::max() - prefix_bytes) {
diff --git a/be/test/storage/index/inverted/snii/format/null_bitmap_test.cpp
b/be/test/storage/index/inverted/snii/format/null_bitmap_test.cpp
index 9cea5338ee1..6ad1bd78f34 100644
--- a/be/test/storage/index/inverted/snii/format/null_bitmap_test.cpp
+++ b/be/test/storage/index/inverted/snii/format/null_bitmap_test.cpp
@@ -22,6 +22,7 @@
#include <algorithm>
#include <cstdint>
#include <limits>
+#include <numeric>
#include <span>
#include <string>
#include <vector>
@@ -80,6 +81,36 @@ TEST(SniiNullBitmap, RoundTripPerDoc) {
}
}
+// A long run of NULL rows -- the usual shape of a path that is absent from
most rows of a sparse
+// column -- must be written as run containers: a few bytes per 65536 rows
instead of 8 KiB of
+// bitset. The size reported ahead of the write must be the size written.
+TEST(SniiNullBitmap, RunsOfNullsSerializeAsRuns) {
+ constexpr uint32_t kRows = 1'000'000;
+ std::vector<uint32_t> nulls(kRows);
+ std::iota(nulls.begin(), nulls.end(), 0U);
+ NullBitmapWriter writer;
+ writer.add_many(nulls);
+
+ doris::snii::format::NullBitmapSerializationSizes sizes;
+ ASSERT_TRUE(writer.serialization_sizes(kRows, &sizes).ok());
+ // 16 containers of one run each; as bitsets they would take 16 * 8 KiB.
+ EXPECT_LT(sizes.roaring_bytes, 256U);
+
+ ByteSink sink;
+ ASSERT_TRUE(writer.finish(kRows, &sink).ok());
+ EXPECT_EQ(sink.size(), sizes.framed_bytes);
+
+ NullBitmapReader reader;
+ ASSERT_TRUE(NullBitmapReader::open(sink.view(), &reader).ok());
+ EXPECT_EQ(reader.null_count(), kRows);
+ EXPECT_TRUE(reader.is_null(0));
+ EXPECT_TRUE(reader.is_null(kRows - 1));
+ EXPECT_FALSE(reader.is_null(kRows));
+ uint64_t decoded_bytes = 0;
+ ASSERT_TRUE(NullBitmapReader::decoded_memory_bytes(sink.view(),
&decoded_bytes).ok());
+ EXPECT_GT(decoded_bytes, 0U);
+}
+
// Writer null_count reflects the number of distinct null docids added.
TEST(SniiNullBitmap, WriterNullCount) {
NullBitmapWriter writer;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
