Implementation:Apache Paimon BitmapDeletionVector

Knowledge Sources	Apache_Paimon
Domains	Deletion Vectors, Data Compression
Last Updated	2026-02-08 00:00 GMT

Overview

BitmapDeletionVector implements deletion vector functionality using RoaringBitmap for space-efficient tracking of deleted row positions in files with up to 2.1 billion rows.

Description

The BitmapDeletionVector class provides a concrete implementation of the DeletionVector interface using RoaringBitmap for compressed storage of deleted row positions. It limits row positions to 32-bit signed integers (maximum value 2,147,483,647), making it suitable for most file sizes while enabling efficient bitmap operations and serialization.

The class wraps a RoaringBitmap instance, delegating position tracking to the bitmap's optimized add() and contains() methods. It validates position values to ensure they don't exceed the 32-bit limit, throwing ValueError for oversized files. The is_deleted() method provides O(log n) lookup complexity, and merge() combines deletion vectors using bitmap union operations.

Serialization follows a custom format: a 4-byte size field, a 4-byte magic number (1581511376) identifying the format, the serialized bitmap data, and a 4-byte CRC32 checksum for integrity verification. The deserialize_from_bytes() static method reconstructs BitmapDeletionVector instances from this format. The implementation uses zlib.crc32() for checksum calculation and struct.pack() for binary encoding, ensuring consistent cross-platform serialization.

Usage

Use BitmapDeletionVector when implementing merge-on-read storage with deletion tracking, serializing deletion vectors to index files, or merging deletion sets from multiple operations with efficient bitmap representations.

Code Reference

Source Location

• Repository: Apache_Paimon
• File: paimon-python/pypaimon/deletionvectors/bitmap_deletion_vector.py

Signature

class BitmapDeletionVector(DeletionVector):
    """
    A DeletionVector based on RoaringBitmap, it only supports files with row count
    not exceeding 2147483647 (max value for 32-bit integer).
    """

    MAGIC_NUMBER = 1581511376
    MAGIC_NUMBER_SIZE_BYTES = 4
    MAX_VALUE = 2147483647

    def __init__(self, bitmap: RoaringBitmap = None):
        pass

    def delete(self, position: int) -> None:
        pass

    def is_deleted(self, position: int) -> bool:
        pass

    def is_empty(self) -> bool:
        pass

    def get_cardinality(self) -> int:
        pass

    def merge(self, deletion_vector: DeletionVector) -> None:
        pass

    def serialize(self) -> bytes:
        pass

    @staticmethod
    def deserialize_from_bytes(data: bytes) -> 'BitmapDeletionVector':
        pass

    def bit_map(self):
        pass

    def _check_position(self, position: int) -> None:
        pass

    @staticmethod
    def _calculate_checksum(data: bytes) -> int:
        pass

Import

from pypaimon.deletionvectors.bitmap_deletion_vector import BitmapDeletionVector

I/O Contract

Inputs

Name	Type	Required	Description
position	int	Yes	Row position to mark as deleted (0 to 2,147,483,647)
bitmap	RoaringBitmap	No	Pre-existing bitmap (creates empty if None)
data	bytes	Yes	Serialized deletion vector bytes for deserialization
deletion_vector	DeletionVector	Yes	Another deletion vector to merge

Outputs

Name	Type	Description
is_deleted	bool	Whether position is marked as deleted
cardinality	int	Number of deleted positions
serialized	bytes	Serialized deletion vector with checksum
deletion_vector	BitmapDeletionVector	Deserialized instance

Usage Examples

from pypaimon.deletionvectors.bitmap_deletion_vector import BitmapDeletionVector
from pypaimon.utils.roaring_bitmap import RoaringBitmap

# Create empty deletion vector
dv = BitmapDeletionVector()
print(dv.is_empty())  # True
print(dv.get_cardinality())  # 0

# Mark positions as deleted
dv.delete(10)
dv.delete(25)
dv.delete(100)
print(dv.get_cardinality())  # 3

# Check if positions are deleted
print(dv.is_deleted(10))   # True
print(dv.is_deleted(11))   # False
print(dv.is_deleted(25))   # True
print(dv.is_deleted(100))  # True

# Serialize to bytes
serialized = dv.serialize()
print(f"Serialized size: {len(serialized)} bytes")

# Deserialize from bytes
dv2 = BitmapDeletionVector.deserialize_from_bytes(
    serialized[4:-4]  # Skip size prefix and checksum suffix
)
print(dv2.is_deleted(10))  # True
print(dv2.get_cardinality())  # 3

# Merge deletion vectors
dv1 = BitmapDeletionVector()
dv1.delete(1)
dv1.delete(2)
dv1.delete(3)

dv2 = BitmapDeletionVector()
dv2.delete(3)
dv2.delete(4)
dv2.delete(5)

dv1.merge(dv2)
print(dv1.get_cardinality())  # 5 (positions 1,2,3,4,5)
print(dv1.is_deleted(1))  # True
print(dv1.is_deleted(5))  # True

# Create from existing RoaringBitmap
bitmap = RoaringBitmap()
bitmap.add(100)
bitmap.add(200)
bitmap.add(300)

dv = BitmapDeletionVector(bitmap)
print(dv.get_cardinality())  # 3

# Access underlying bitmap
bitmap = dv.bit_map()
for pos in bitmap:
    print(f"Deleted position: {pos}")

# Equality comparison
dv1 = BitmapDeletionVector()
dv1.delete(1)
dv1.delete(2)

dv2 = BitmapDeletionVector()
dv2.delete(1)
dv2.delete(2)

print(dv1 == dv2)  # True

# Handle large file with many deletions
dv = BitmapDeletionVector()
# Mark every 100th row as deleted in a 10M row file
for i in range(0, 10_000_000, 100):
    dv.delete(i)

print(f"Deleted {dv.get_cardinality()} rows")  # 100,000
serialized = dv.serialize()
print(f"Compressed size: {len(serialized)} bytes")  # Highly compressed

# Position validation
try:
    dv = BitmapDeletionVector()
    dv.delete(3_000_000_000)  # Exceeds MAX_VALUE
except ValueError as e:
    print(f"Error: {e}")  # "The file has too many rows..."

# Serialize with full format (size + magic + data + checksum)
dv = BitmapDeletionVector()
dv.delete(42)
full_serialized = dv.serialize()

# Parse format
import struct
size = struct.unpack('>I', full_serialized[0:4])[0]
magic = struct.unpack('>I', full_serialized[4:8])[0]
checksum = struct.unpack('>I', full_serialized[-4:])[0]

print(f"Size: {size}")
print(f"Magic: {magic}")  # 1581511376
print(f"Checksum: {checksum}")

# Empty deletion vector serialization
empty_dv = BitmapDeletionVector()
print(empty_dv.is_empty())  # True
serialized = empty_dv.serialize()
print(f"Empty DV size: {len(serialized)} bytes")

# Use in file operations
from pypaimon.common.file_io import FileIO

file_io = FileIO.get("/tmp/data")
dv = BitmapDeletionVector()
# ... mark deletions ...

# Write to file
with file_io.new_output_stream("/tmp/data/dv_index") as out:
    out.write(dv.serialize())

# Read from file
with file_io.new_input_stream("/tmp/data/dv_index") as inp:
    data = inp.read()
    # Parse and deserialize...

Related Pages

• Principle:Apache_Paimon_Deletion_Vectors