Roaring versus plain bitmap versus sorted array

Measure your machineNeeds Python

Problem

A set of row IDs can be stored as a sorted array (4 bytes per member, small when the set is sparse) or a plain bitmap (one bit per possible row, fixed size, cheap to AND). Each wins at one end of the density range. Roaring splits the universe into chunks of 65,536 and stores each chunk in whichever form is smaller: an array when it holds fewer than 4,096 members, a bitmap above that. It follows the smaller of the two curves, and intersects chunk by chunk with the right algorithm for each pair.

Build sets of row IDs over a universe of 10⁸ rows with densities 0.001%, 0.1%, 1%, 10% and 50%. For each, record the serialized size of a plain uncompressed bitmap (always 12.5 MB), a sorted int32 array and a Roaring bitmap (pyroaring). Then time the intersection of two sets at 1% density with each representation.

The question. Does Roaring track the smaller of the two other formats at every density, and which representation intersects fastest?

Predict

Intersecting two 1% sets: which representation is fastest?

Sorted arrays (merge)Plain bitmaps (AND)Roaring (AND)

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

roaring-versus-plain-bitmap-versus-sorted.py50 linesDownload

View the code

roaring-versus-plain-bitmap-versus-sorted.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy", "pyroaring"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Roaring against a plain bitmap against a sorted array.

Sets of row ids over a universe of 10^8 rows at densities from 0.001% to
50%: serialized size of a plain bitmap, a sorted int32 array and a Roaring
bitmap. Then the intersection of two 1% sets with each.
"""
import argparse, json, time
import numpy as np
from pyroaring import BitMap

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--universe", type=int, default=100_000_000, help="Rows in the universe.")
p.add_argument("--densities", type=lambda s: [float(v) for v in s.split(",")], default=[0.00001, 0.001, 0.01, 0.1, 0.5], help="Densities.")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(args.seed)
U = args.universe

def ids(d): return np.flatnonzero(rng.random(U) < d).astype(np.uint32)

rows = []
for d in args.densities:
    s = ids(d)
    rows += [{"density_pct": d * 100, "format": "plain bitmap", "mb": U / 8 / 1e6},
             {"density_pct": d * 100, "format": "sorted int32 array", "mb": len(s) * 4 / 1e6},
             {"density_pct": d * 100, "format": "Roaring", "mb": len(BitMap(s).serialize()) / 1e6}]
    print(f"density {d:8.3%}: plain {U / 8 / 1e6:6.2f} MB   sorted array {len(s) * 4 / 1e6:8.3f} MB   Roaring {rows[-1]['mb']:8.3f} MB")

a, b = ids(0.01), ids(0.01)
ra, rb = BitMap(a), BitMap(b)
pa, pb = np.zeros(U, dtype=bool), np.zeros(U, dtype=bool); pa[a] = True; pb[b] = True
pa8, pb8 = np.packbits(pa), np.packbits(pb)
times = []
for name, fn in (("sorted arrays (merge)", lambda: np.intersect1d(a, b, assume_unique=True)),
                 ("plain bitmaps (AND)", lambda: np.bitwise_and(pa8, pb8)),
                 ("Roaring (AND)", lambda: ra & rb)):
    fn(); t = time.perf_counter(); [fn() for _ in range(5)]; dt = (time.perf_counter() - t) / 5
    times.append({"representation": name, "ms": dt * 1000}); print(f"intersect two 1% sets, {name:<22} {dt * 1000:8.2f} ms")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"sizes": rows, "intersections": times}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.

Terminal

uv run roaring-versus-plain-bitmap-versus-sorted.py
uv run roaring-versus-plain-bitmap-versus-sorted.py --help     # every knob

Knobs
Knob · default	What it changes
--universe100,000,000	Rows in the universe.
--densities1e-05, 0.001, 0.01, 0.1, 0.5	Densities.
--seed0	Random seed.

Our run

Serialized size against densityApple M2 · 8 cores · 8 GB

plain bitmapsorted int32 arrayRoaring

Data table

Serialized size against density
Density (%)	series	Size (MB)
0.001	plain bitmap	12.5
0.001	sorted int32 array	0.004
0.001	Roaring	0.008
0.1	plain bitmap	12.5
0.1	sorted int32 array	0.401
0.1	Roaring	0.213
1	plain bitmap	12.5
1	sorted int32 array	4
1	Roaring	2.01
10	plain bitmap	12.5
10	sorted int32 array	40
10	Roaring	12.5
50	plain bitmap	12.5
50	sorted int32 array	200
50	Roaring	12.5

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · pyroaring 1.2.0 · run 2026-10-20

Intersecting two 1% sets

Intersecting two 1% sets
Representation	Time (ms)
sorted arrays (merge)	28.3
plain bitmaps (AND)	2.2
Roaring (AND)	6.97

Output · uv run roaring-versus-plain-bitmap-versus-sorted.py

density   0.001%: plain  12.50 MB   sorted array    0.004 MB   Roaring    0.008 MB
density   0.100%: plain  12.50 MB   sorted array    0.401 MB   Roaring    0.213 MB
density   1.000%: plain  12.50 MB   sorted array    4.004 MB   Roaring    2.014 MB
density  10.000%: plain  12.50 MB   sorted array   40.001 MB   Roaring   12.513 MB
density  50.000%: plain  12.50 MB   sorted array  200.015 MB   Roaring   12.513 MB
intersect two 1% sets, sorted arrays (merge)     28.31 ms
intersect two 1% sets, plain bitmaps (AND)        2.20 ms
intersect two 1% sets, Roaring (AND)              6.97 ms

What we found

Roaring followed the smaller curve at the ends and beat both in the middle: at 0.001% it took 0.008 MB against the array's 0.004; at 1%, 2.01 MB against 4, half the array, because inside a chunk it stores only the low 16 bits of each ID; from 10% up it matched the plain bitmap (12.5 MB). Intersecting two 1% sets took 28.3 ms by merging sorted arrays, 6.97 ms with Roaring and 2.2 ms with plain bitmaps.

Read it

Adapting per chunk is what lets one format serve every density: no global choice is right when a column's selectivity varies by value. Roaring also wins where neither pure form does, because it pays only 2 bytes per member in sparse chunks.

The plain bitmap's AND is the fastest operation in the lab, and it costs 12.5 MB per set whatever the set holds; that is the trade Roaring makes adaptive.