JingsongLi opened a new pull request, #9981:
URL: https://github.com/apache/paimon/pull/9981
### Purpose
BTree index V1 stores the absolute row IDs for every key. This is efficient
to read partially, but can consume substantially more space and requires adding
every row ID individually when point and range predicates produce a bitmap.
This change adds an opt-in adaptive BTree file format. Each posting list is
self-describing and uses one of:
- a dedicated singleton encoding;
- a delta-encoded row ID list;
- a portable 64-bit Roaring bitmap.
The writer chooses the strictly smaller serialized representation between
Delta and Roaring. It first computes a conservative Roaring size lower bound so
sparse postings can skip constructing a bitmap entirely. Roaring postings are
merged directly into query results instead of adding row IDs one by one.
Compatibility is preserved:
- `btree-index.file-version` defaults to `1`;
- existing writer constructors continue to produce V1 files;
- the reader supports both V1 and V2 files;
- V2 must be explicitly enabled after all readers have been upgraded.
The hot paths were also optimized to avoid validation boxing, build long
contiguous Roaring runs as ranges, avoid an extra payload copy, and extract
bounded Roaring values through a primitive iterator.
#### Performance compared with V1
Environment: Corretto JDK 8 on arm64. Results are medians after warmup
across five measured rounds. Times are microseconds per operation. The
benchmark validates that V1 and V2 return identical row IDs before timing.
Encoding and serialized size:
| Distribution | V2 encoding | V1 bytes | V2 bytes | V1 encode | V2 encode |
| --- | --- | ---: | ---: | ---: | ---: |
| Contiguous 65K | Roaring | 180,099 | 28 | 91.094 | 80.070 |
| Random 50%, 65K rows | Roaring | 188,355 | 16,421 | 93.871 | 729.799 |
| Random 13%, 8.5K rows | Roaring | 23,396 | 8,221 | 11.877 | 82.833 |
| Random 10%, 65K rows | Delta | 194,967 | 65,540 | 98.528 | 81.864 |
| Stride 100, 65K rows | Delta | 241,009 | 65,540 | 137.771 | 80.037 |
| Contiguous 65K above 2^32 | Roaring | 327,683 | 28 | 163.157 | 118.360 |
Point/range bitmap merge and TopN(20):
| Distribution | V1 bitmap merge | V2 bitmap merge | V1 TopN | V2 TopN |
| --- | ---: | ---: | ---: | ---: |
| Contiguous 65K | 399.884 | 0.212 | 0.019 | 0.220 |
| Random 50%, 65K rows | 515.879 | 10.906 | 0.017 | 10.105 |
| Random 13%, 8.5K rows | 74.540 | 5.537 | 0.017 | 5.105 |
| Random 10%, 65K rows | 646.550 | 462.098 | 0.018 | 0.023 |
| Stride 100, 65K rows | 653.134 | 440.257 | 0.024 | 0.023 |
| Contiguous 65K above 2^32 | 577.532 | 0.215 | 0.050 | 0.218 |
Range query across 64 postings and 65,536 total row IDs:
| Posting layout | V1 bytes | V2 bytes | V1 encode | V2 encode | V1 range
merge | V2 range merge |
| --- | ---: | ---: | ---: | ---: | ---: | ---: |
| Clustered contiguous postings | 180,224 | 1,792 | 112.828 | 126.266 |
407.188 | 10.690 |
| Interleaved postings | 180,224 | 65,728 | 114.003 | 82.673 | 548.877 |
483.942 |
Roaring provides the largest benefit for bitmap-producing point/range
queries and run-rich postings. Random dense Roaring postings trade slower
construction and TopN deserialization for smaller files and much faster bitmap
queries. Delta postings retain partial-read behavior close to V1.
### Tests
```shell
mvn -pl paimon-common -DwildcardSuites=none \
-Dtest=BTreePostingListTest,BTreeIndexReaderTest,BTreeIndexReaderCloseTest,BTreeBloomFilterTest,BTreeIndexOptionsTest,BTreeThreadSafetyTest,RoaringNavigableMap64Test
\
test
```
140 tests passed. Checkstyle and Spotless also passed.
--
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]
