Skip to content

Core: Add portable Roaring bitmap for row positions#11372

Merged
aokolnychyi merged 9 commits into
apache:mainfrom
aokolnychyi:serializeble-bitmap
Oct 28, 2024
Merged

Core: Add portable Roaring bitmap for row positions#11372
aokolnychyi merged 9 commits into
apache:mainfrom
aokolnychyi:serializeble-bitmap

Conversation

@aokolnychyi

@aokolnychyi aokolnychyi commented Oct 21, 2024 •
edited
Loading

Copy link
Copy Markdown
Contributor

This PR adds a Roaring bitmap implementation that follows the official "portable" serialization format from the library for row positions in preparation for V3 position deletes. We are still discussing the blob layout for DVs on the dev list but we agree we should serialize the bitmap according to the portable serialization spec.

We cannot rely on the Roaring64Bitmap from the library as it has undefined serialization behavior:

  /**
   * {@link Roaring64NavigableMap} are serializable. However, contrary to RoaringBitmap, the
   * serialization format is not well-defined: for now, it is strongly coupled with Java standard
   * serialization. Just like the serialization may be incompatible between various Java versions,
   * {@link Roaring64NavigableMap} are subject to incompatibilities. Moreover, even on a given Java
   * versions, the serialization format may change from one RoaringBitmap version to another
   */

Here are benchmarks comparing this implementation to the one from the library we use today.

Benchmark                                                         Mode  Cnt  Score   Error  Units
RoaringPositionBitmapBenchmark.addAndCheckPositionsIcebergBitmap    ss    5  0.535 ± 0.032   s/op
RoaringPositionBitmapBenchmark.addAndCheckPositionsLibraryBitmap    ss    5  1.124 ± 0.013   s/op
RoaringPositionBitmapBenchmark.addOrderedPositionsIcebergBitmap     ss    5  0.023 ± 0.003   s/op
RoaringPositionBitmapBenchmark.addOrderedPositionsLibraryBitmap     ss    5  0.165 ± 0.028   s/op
RoaringPositionBitmapBenchmark.addShuffledPositionsIcebergBitmap    ss    5  0.320 ± 0.006   s/op
RoaringPositionBitmapBenchmark.addShuffledPositionsLibraryBitmap    ss    5  0.338 ± 0.011   s/op

This is not a spec change but part of #11122.

Loading
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@amogh-jahagirdar amogh-jahagirdar amogh-jahagirdar left review comments
@rdblue rdblue rdblue approved these changes
@nastra nastra nastra approved these changes
@RussellSpitzer RussellSpitzer RussellSpitzer approved these changes
@danielcweeks danielcweeks danielcweeks approved these changes

Assignees

No one assigned

Labels

core

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@aokolnychyi @rdblue @nastra @RussellSpitzer @danielcweeks @amogh-jahagirdar