Bitmap-операции и RoaringBitmap

Bitmap — компактное представление множества целых чисел. Каждый бит соответствует одному ID: бит 1 = ID присутствует, бит 0 = отсутствует. Операции AND, OR, XOR над бitmapами эквивалентны пересечению, объединению и симметрической разности множеств, но выполняются за микросекунды на миллионах элементов.

ClickHouse использует RoaringBitmap — сжатый формат bitset от Apache. RoaringBitmap хранит данные в контейнерах по 65536 бит (16-bit chunk): плотные диапазоны — как bitset, разреженные — как отсортированный массив. Это даёт сжатие до 100x по сравнению с наивным bitset.

Зачем нужны bitmaps в аналитике

Типичная задача: аудиторная сегментация. У рекламной платформы миллионы пользователей, десятки сегментов (посетил сайт, добавил в корзину, купил). Нужно быстро ответить:

• Сколько пользователей в пересечении сегментов A и B?
• Кто в A, но не в B?
• Объединение трёх сегментов — какой охват?

Без bitmaps: JOIN или IN с подзапросом на миллионах ID — тяжёлые операции. С bitmaps: AND/OR над сжатыми множествами — миллисекунды.

Тип столбца: AggregateFunction(groupBitmap, UInt32)

CREATE TABLE audience_segments (
    segment_name LowCardinality(String),
    event_date Date,
    user_bitmap AggregateFunction(groupBitmap, UInt32)
) ENGINE = AggregatingMergeTree()
ORDER BY (segment_name, event_date);

AggregateFunction(groupBitmap, UInt32) — столбец, хранящий RoaringBitmap. Тип ключа — UInt32 или UInt64. Для хранения в таблице bitmap создаётся через -State суффикс агрегатной функции.

Построение bitmaps: groupBitmapState

-- Агрегация: построить bitmap из user_id по каждому сегменту и дню
INSERT INTO audience_segments
SELECT
    segment_name,
    event_date,
    groupBitmapState(user_id) AS user_bitmap
FROM raw_events
GROUP BY segment_name, event_date;

groupBitmapState(column) — агрегатная функция с суффиксом -State. Собирает все значения столбца в RoaringBitmap и возвращает бинарное представление для хранения в AggregateFunction столбце.

Set-операции: groupBitmapAnd, groupBitmapOr, groupBitmapXor

Пересечение: пользователи в ОБОИХ сегментах

-- Кто посетил сайт И добавил в корзину?
SELECT groupBitmapAnd(user_bitmap) AS intersection_count
FROM audience_segments
WHERE segment_name IN ('visited_site', 'added_to_cart')
  AND event_date = '2025-01-15';

groupBitmapAnd выполняет побитовое AND над всеми bitmaps в GROUP BY. Результат — количество бит, установленных во ВСЕХ bitmap одновременно (пересечение множеств).

Объединение: пользователи в ЛЮБОМ сегменте

-- Общий охват трёх рекламных кампаний
SELECT groupBitmapOr(user_bitmap) AS union_count
FROM audience_segments
WHERE segment_name IN ('campaign_A', 'campaign_B', 'campaign_C')
  AND event_date >= '2025-01-01';

Симметрическая разность: пользователи ровно в одном из сегментов

-- Кто купил, но НЕ подписался на рассылку (или наоборот)
SELECT groupBitmapXor(user_bitmap) AS xor_count
FROM audience_segments
WHERE segment_name IN ('purchased', 'subscribed')
  AND event_date = '2025-01-15';

Утилитарные функции

bitmapBuild: создание bitmap из массива

-- Создать bitmap из массива ID (без агрегации)
SELECT bitmapBuild([1, 2, 3, 100, 200]) AS bm;

bitmapToArray: раскрытие bitmap в массив

-- Получить конкретные ID пользователей в пересечении
SELECT bitmapToArray(
    bitmapAnd(
        (SELECT groupBitmapMergeState(user_bitmap) FROM audience_segments WHERE segment_name = 'visited_site'),
        (SELECT groupBitmapMergeState(user_bitmap) FROM audience_segments WHERE segment_name = 'purchased')
    )
) AS user_ids;

bitmapContains: проверка наличия ID

-- Пользователь 42 в сегменте "purchased"?
SELECT bitmapContains(
    (SELECT groupBitmapMergeState(user_bitmap) FROM audience_segments WHERE segment_name = 'purchased'),
    toUInt32(42)
) AS is_in_segment;

bitmapCardinality: точный подсчёт

-- Размер bitmap (точный count, не приблизительный)
SELECT bitmapCardinality(bitmapBuild([1, 2, 3, 100, 200]));
-- Результат: 5

Практика: аудиторная сегментация для рекламного таргетинга

-- 1. Создать таблицу сегментов
CREATE TABLE ad_segments (
    segment_id UInt32,
    segment_name LowCardinality(String),
    dt Date,
    users AggregateFunction(groupBitmap, UInt32)
) ENGINE = AggregatingMergeTree()
ORDER BY (segment_id, dt);

-- 2. Наполнить из сырых событий
INSERT INTO ad_segments
SELECT
    segment_id,
    any(segment_name),
    event_date,
    groupBitmapState(toUInt32(user_id))
FROM raw_user_events
GROUP BY segment_id, event_date;

-- 3. Конверсионная воронка: visited -> cart -> purchased
SELECT
    groupBitmapOr(users) AS visited_total,
    groupBitmapAnd(users) AS all_three_steps
FROM ad_segments
WHERE segment_name IN ('visited', 'cart', 'purchased')
  AND dt = today();

-- 4. Lookalike: пользователи в "high_value" но не в "active_campaign"
SELECT bitmapToArray(
    bitmapAndnot(
        (SELECT groupBitmapMergeState(users) FROM ad_segments WHERE segment_name = 'high_value'),
        (SELECT groupBitmapMergeState(users) FROM ad_segments WHERE segment_name = 'active_campaign')
    )
) AS lookalike_ids;

bitmapAndnot(a, b) — разность множеств: элементы в A, но не в B.

Ключевые выводы

1. RoaringBitmap — сжатый bitset для set-операций над множествами целочисленных ID. Хранится в столбце AggregateFunction(groupBitmap, UInt32).
2. groupBitmapState — агрегатная функция для построения bitmap из столбца. Используется с AggregatingMergeTree для инкрементального хранения.
3. groupBitmapAnd (пересечение), groupBitmapOr (объединение), groupBitmapXor (симметрическая разность) — set-операции за миллисекунды на миллионах ID.
4. bitmapCardinality возвращает точное количество элементов (не приблизительное, в отличие от uniq). bitmapToArray раскрывает bitmap в массив ID.
5. Bitmap требует UInt32/UInt64 ключи. Для строковых ID используйте cityHash64() — но обратная конвертация невозможна (хеш необратим).