Implementation:Apache Paimon RoaringBitmap
| Knowledge Sources | |
|---|---|
| Domains | Data Structures, Compression |
| Last Updated | 2026-02-08 00:00 GMT |
Overview
RoaringBitmap provides space-efficient, high-performance bitmap implementations for 32-bit and 64-bit integer sets using the pyroaring library with full set operations and serialization support.
Description
The RoaringBitmap module provides two bitmap implementations: RoaringBitmap for 32-bit integers and RoaringBitmap64 for 64-bit integers. Both classes wrap the pyroaring library (BitMap and BitMap64) to provide efficient compressed storage of integer sets with O(log n) membership testing and fast set operations.
RoaringBitmap uses a hybrid compression scheme that automatically selects optimal storage based on data density: arrays for sparse sets, bitmaps for dense sets, and run-length encoding for consecutive values. This adaptive compression often achieves better space efficiency than traditional bitmaps while maintaining fast operations. The add(), add_range(), and contains() methods provide core functionality with iterator support for traversing sorted values.
Both classes support set operations through static methods: and_() for intersection, or_() for union, and remove_all() for difference. They implement Python protocols like __contains__() for membership testing, __len__() for cardinality, and __iter__() for iteration. The serialize() and deserialize() methods enable persistent storage and transmission. RoaringBitmap64 additionally provides to_range_list() for converting bitmaps into consecutive Range objects, useful for representing deletion ranges.
Usage
Use RoaringBitmap when implementing deletion vectors, tracking sparse integer sets like row IDs, or performing set operations on large collections of integers with efficient memory usage and serialization.
Code Reference
Source Location
- Repository: Apache_Paimon
- File: paimon-python/pypaimon/utils/roaring_bitmap.py
Signature
class RoaringBitmap:
"""
A 32-bit roaring bitmap implementation.
This class provides efficient storage and operations for sets of 32-bit integers.
It uses pyroaring.BitMap for better performance and memory efficiency.
"""
def __init__(self):
pass
def add(self, value: int) -> None:
pass
def add_range(self, from_: int, to: int) -> None:
pass
def contains(self, value: int) -> bool:
pass
def is_empty(self) -> bool:
pass
def cardinality(self) -> int:
pass
def clear(self) -> None:
pass
def to_list(self) -> list:
pass
@staticmethod
def and_(a: 'RoaringBitmap', b: 'RoaringBitmap') -> 'RoaringBitmap':
pass
@staticmethod
def or_(a: 'RoaringBitmap', b: 'RoaringBitmap') -> 'RoaringBitmap':
pass
@staticmethod
def remove_all(a: 'RoaringBitmap', b: 'RoaringBitmap') -> 'RoaringBitmap':
pass
def serialize(self) -> bytes:
pass
@staticmethod
def deserialize(data: bytes) -> 'RoaringBitmap':
pass
class RoaringBitmap64:
"""
A 64-bit roaring bitmap implementation.
This class provides efficient storage and operations for sets of 64-bit integers.
It uses pyroaring.BitMap64 for better performance and memory efficiency.
"""
def __init__(self):
pass
def to_range_list(self) -> list:
pass
# Similar methods to RoaringBitmap...
Import
from pypaimon.utils.roaring_bitmap import RoaringBitmap, RoaringBitmap64
I/O Contract
Inputs
| Name | Type | Required | Description |
|---|---|---|---|
| value | int | Yes | Integer value to add or check |
| from_ | int | Yes | Start of range (inclusive) |
| to | int | Yes | End of range (inclusive) |
| data | bytes | Yes | Serialized bitmap data |
| a, b | RoaringBitmap | Yes | Bitmaps for set operations |
Outputs
| Name | Type | Description |
|---|---|---|
| contains | bool | Whether value is in bitmap |
| cardinality | int | Number of elements in bitmap |
| list | list[int] | Sorted list of all values |
| bitmap | RoaringBitmap | Result of set operation |
| bytes | bytes | Serialized bitmap representation |
Usage Examples
from pypaimon.utils.roaring_bitmap import RoaringBitmap, RoaringBitmap64
# Create 32-bit bitmap
bitmap = RoaringBitmap()
bitmap.add(1)
bitmap.add(100)
bitmap.add(1000)
# Membership testing
print(1 in bitmap) # True
print(50 in bitmap) # False
print(bitmap.contains(100)) # True
# Cardinality
print(len(bitmap)) # 3
print(bitmap.cardinality()) # 3
# Add ranges
bitmap.add_range(10, 20) # Adds 10, 11, 12, ..., 20
print(len(bitmap)) # 14 (3 original + 11 new)
# Iteration (sorted order)
for value in bitmap:
print(value) # 1, 10, 11, 12, ..., 20, 100, 1000
# Convert to list
values = bitmap.to_list()
print(values) # [1, 10, 11, 12, ..., 20, 100, 1000]
# Set operations
bitmap1 = RoaringBitmap()
bitmap1.add(1)
bitmap1.add(2)
bitmap1.add(3)
bitmap2 = RoaringBitmap()
bitmap2.add(2)
bitmap2.add(3)
bitmap2.add(4)
# Union
union = RoaringBitmap.or_(bitmap1, bitmap2)
print(union.to_list()) # [1, 2, 3, 4]
# Intersection
intersection = RoaringBitmap.and_(bitmap1, bitmap2)
print(intersection.to_list()) # [2, 3]
# Difference (bitmap1 - bitmap2)
difference = RoaringBitmap.remove_all(bitmap1, bitmap2)
print(difference.to_list()) # [1]
# Serialization
bitmap = RoaringBitmap()
bitmap.add_range(1, 1000)
serialized = bitmap.serialize()
print(f"Serialized size: {len(serialized)} bytes")
# Deserialization
bitmap2 = RoaringBitmap.deserialize(serialized)
print(len(bitmap2)) # 1000
print(bitmap == bitmap2) # True
# Clear bitmap
bitmap.clear()
print(bitmap.is_empty()) # True
# 64-bit bitmap
bitmap64 = RoaringBitmap64()
bitmap64.add(1)
bitmap64.add(2**40) # Large 64-bit value
bitmap64.add(2**50)
print(len(bitmap64)) # 3
print(2**40 in bitmap64) # True
# Range list conversion (64-bit only)
bitmap64 = RoaringBitmap64()
bitmap64.add_range(10, 15)
bitmap64.add_range(20, 25)
bitmap64.add(30)
ranges = bitmap64.to_range_list()
for r in ranges:
print(f"Range: {r.start} to {r.end}")
# Range: 10 to 15
# Range: 20 to 25
# Range: 30 to 30
# Use in deletion vectors
deleted_rows = RoaringBitmap()
deleted_rows.add_range(100, 199) # Rows 100-199 deleted
deleted_rows.add(500) # Row 500 deleted
# Check if row should be filtered
def should_filter(row_num):
return row_num in deleted_rows
print(should_filter(150)) # True (in deleted range)
print(should_filter(250)) # False (not deleted)
# Efficient large sparse sets
bitmap = RoaringBitmap()
# Add 1 million scattered values
for i in range(0, 100_000_000, 100):
bitmap.add(i)
print(f"Count: {len(bitmap)}") # 1,000,000
serialized = bitmap.serialize()
print(f"Compressed size: {len(serialized)} bytes") # Much less than 4MB
# Equality and hashing
bm1 = RoaringBitmap()
bm1.add(1)
bm1.add(2)
bm2 = RoaringBitmap()
bm2.add(1)
bm2.add(2)
print(bm1 == bm2) # True
print(hash(bm1) == hash(bm2)) # True
# Use in sets/dicts
bitmap_set = {bm1, bm2}
print(len(bitmap_set)) # 1 (considered equal)
# String representation
bitmap = RoaringBitmap()
bitmap.add_range(1, 5)
print(repr(bitmap)) # "RoaringBitmap([1, 2, 3, 4, 5])"
large_bitmap = RoaringBitmap()
for i in range(1000):
large_bitmap.add(i)
print(repr(large_bitmap)) # "RoaringBitmap(1000 elements)"