hi team, can some one let me know how starrocks is building count distinct using bitmap?

Hello @D K, my name is Srihith G. and I am a Database Systems Engineer that works on StarRocks. Roaring Bitmap (Core) So under the hood StarRocks uses Roaring Bitmaps using the CRoaring library. The intenal BitmapValue class has 4 storage modes to optimize for different cardinalities • EMPTY meaning no allocation • SINGLE meaning it stores the integer directly and is optimized for stream loads • SET - 2-31 elements and uses a phmap::flat_hash_set • BITMAP - 32+ elements (fully compressed Roaring64Map) This hybrid aporoach is mainly to avoid the overhead of a full bitmap structure when the cardinality is low StarRocks stores distinct values as compressed Roaring Bitmaps. So when you run

COUNT(DISTINCT bitmap_col)

, the optimizer rewrites it to

BITMAP_UNION_COUNT(bitmap_col)

, which merges bitmaps via bitwise OR and returns the count of set bits. This then replaces the expensive hash-based dedup + multi-node shuffles with cheap bitwise operations on compressed data. • Distributed Execution: ◦ each BE node runs

BITMAP_UNION

locally, then only the compressed bitmap results get shuffled across the network ◦ the final node runs

BITMAP_UNION_COUNT

to return the cardinality. ▪︎ This avoids the multiple data shuffles that traditional

COUNT DISTINCT

requires • With MV acceleration - you can pre-compute bitmap aggregations:

CREATE MATERIALIZED VIEW mv_uv AS
SELECT date, page, BITMAP_UNION(TO_BITMAP(user_id))
FROM visit_log GROUP BY date, page;

Then running

SELECT date, COUNT(DISTINCT user_id) FROM visit_log GROUP BY date

automatically reads from the MV instead of scanning the base table Docs: https://docs.starrocks.io/docs/using_starrocks/distinct_values/Using_bitmap/

thanks alot