airborne12 opened a new pull request, #69727:
URL: https://github.com/apache/doris/pull/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`.
### Check List (For Author)
- Test <!-- At least one of them must be included. -->
- [ ] Regression test
- [x] Unit Test
- Added SniiNullBitmap.RunsOfNullsSerializeAsRuns. All BE unit tests
matching *Snii* pass. With the production change reverted, the new case fails.
- [ ] Manual test (add detailed scripts or steps below)
- [ ] No need to test or manual test. Explain why:
- [ ] This is a refactor/code format and no logic has been changed.
- [ ] Previous test can cover this change.
- [ ] No code files have been changed.
- [ ] Other reason
- Behavior changed:
- [x] No. The bytes written for runs are smaller, and the standard
Roaring run containers they use were already readable.
- [ ] Yes.
- Does this need documentation?
- [x] No.
- [ ] Yes.
### Check List (For Reviewer who merge this PR)
- [ ] Confirm the release note
- [ ] Confirm test cases
- [ ] Confirm document
- [ ] Add branch pick label
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
