[PR] [core] Add adaptive BTree posting list encoding [paimon]

["JingsongLi (via GitHub)" <gi...@apache.org>]

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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

Re: [PR] [core] Add adaptive BTree posting list encoding [paimon]

["JingsongLi (via GitHub)" <gi...@apache.org>]

JingsongLi merged PR #9981:
URL: https://github.com/apache/paimon/pull/9981


-- 
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: issues-unsubscribe@paimon.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org