Разреженный индекс

ClickHouse не индексирует каждую строку. Вместо этого он хранит одну запись индекса на каждые 8192 строк — разреженный (sparse) индекс. Это радикально отличается от B-tree индекса PostgreSQL, который хранит по одной записи на строку.

Разреженный индекс — это осознанный архитектурный выбор. Он делает ClickHouse чрезвычайно эффективным для диапазонных запросов по ключевым столбцам, но бесполезным для точечных lookups и запросов по не-ключевым столбцам.

Как устроен primary.idx

primary.idx — это несжатый плоский массив значений ORDER BY ключа для первой строки каждой гранулы.

Пример: таблица с ORDER BY (event_date, user_id), 3 гранулы:

Гранула 0 (строки 0–8191):   первая строка = ('2024-01-01', 1001)
Гранула 1 (строки 8192–16383): первая строка = ('2024-01-03', 4521)
Гранула 2 (строки 16384–24575): первая строка = ('2024-01-07', 891)

primary.idx содержит три записи:

[('2024-01-01', 1001), ('2024-01-03', 4521), ('2024-01-07', 891)]

Данные в таблице отсортированы по (event_date, user_id), поэтому значения ключей в primary.idx монотонно не убывают. Это позволяет применять бинарный поиск.

primary.idx: разреженный индекс → гранулы → данные

primary.idx[0]2024-01-01 / uid=1001

primary.idx[1]2024-01-03 / uid=4521

primary.idx[2]2024-01-07 / uid=891

Выполнение запроса с разреженным индексом

Рассмотрим запрос: SELECT count() FROM events WHERE event_date BETWEEN '2024-01-02' AND '2024-01-05'

Шаг 1: анализ WHERE-условия

ClickHouse определяет, какие ключевые столбцы ORDER BY используются в WHERE. event_date — первый столбец ключа. Условие — диапазонный запрос. Индекс применим.

Шаг 2: бинарный поиск в primary.idx

ClickHouse ищет левую и правую границу диапазона:

Левая граница: первая гранула, где ключ может содержать дату ≥ ‘2024-01-02’ → гранула 0 (потому что key[0]=‘2024-01-01’ ≤ ‘2024-01-02’)
Правая граница: последняя гранула, где ключ может содержать дату ≤ ‘2024-01-05’ → гранула 1 (потому что key[2]=‘2024-01-07’ > ‘2024-01-05’)

Результат бинарного поиска: читаем гранулы 0 и 1. Гранула 2 полностью исключена.

Шаг 3: чтение данных

Для гранул 0 и 1 читаем:

.mrk2[0] и .mrk2[1] → байтовые смещения в .bin
Соответствующие CompressedBlock из event_date.bin
Применяем WHERE-фильтр BETWEEN '2024-01-02' AND '2024-01-05' к строкам

Строки гранулы 0, попавшие под фильтр, считаются. Строки вне диапазона отбрасываются.

Сравнение: B-tree (PostgreSQL) vs Sparse Index (ClickHouse)

Свойство	B-tree (PostgreSQL)	Sparse Index (ClickHouse)
Записей в индексе	Одна на строку	Одна на 8192 строк
Размер индекса (1B строк, UInt64)	~20–30 ГБ	~7,5 МБ
Точечный lookup (WHERE id=42)	Быстро: O(log N) по строкам	Медленно: читает гранулу 8192 строк
Диапазонный scan (WHERE date BETWEEN)	Относительно медленно: много random I/O	Очень быстро: читает только нужные гранулы
Годен для OLTP	Да	Нет
Годен для OLAP	Нет	Да

PostgreSQL B-tree хранит одну запись на строку → огромный индекс для больших таблиц. ClickHouse sparse index: одна запись на 8192 строк → 122 070 записей для 1 миллиарда строк. Трейдофф: нет эффективного точечного lookup, но диапазонные сканы кратно быстрее.

Layout B+tree-страницы: как PostgreSQL строит индекс BRIN-индекс PostgreSQL: sparse-индекс для sequential таблиц

WARNING

Добавление WHERE-условия на не-ключевые столбцы не даёт никакого выигрыша от sparse index. WHERE category = 'electronics', если category не входит в ORDER BY, вынуждает ClickHouse просканировать все гранулы таблицы. Используйте secondary indexes (skip indexes) или добавьте часто фильтруемые столбцы в ORDER BY ключ.

Порядок столбцов в ORDER BY имеет значение

Разреженный индекс эффективен только для префикса ORDER BY ключа. Это важнейшее практическое следствие.

Рассмотрим таблицу: ORDER BY (event_date, user_id)

WHERE event_date = '2024-01-15' — ClickHouse эффективно pruneит гранулы по первому столбцу ключа
WHERE user_id = 12345 — бинарный поиск бесполезен: user_id — второй столбец, и значения user_id не монотонно возрастают в primary.idx без фиксированного event_date
WHERE event_date = '2024-01-15' AND user_id = 12345 — эффективно: оба столбца используются

Что это значит на практике:

Допустим, у вас есть dashboard, который фильтрует данные по user_id (конкретный пользователь) и диапазону дат. Текущий ORDER BY (event_date, user_id):

WHERE user_id = 42 AND event_date BETWEEN '2024-01-01' AND '2024-01-31' → сначала применяется фильтр по event_date (первый ключ), затем user_id фильтруется построчно внутри каждой гранулы. Если пользователей много, почти все гранулы будут прочитаны.

Изменив на ORDER BY (user_id, event_date):

WHERE user_id = 42 AND event_date BETWEEN '2024-01-01' AND '2024-01-31' → сначала бинарный поиск по user_id (первый ключ) — находим только гранулы пользователя 42. Затем фильтр по event_date внутри них. Разительный выигрыш.

ORDER BY: порядок столбцов меняет эффективность pruning

ORDER BY (date, user_id)Прунинг по date

ORDER BY (user_id, date)Прунинг по user_id

Правило: ставьте в начало ORDER BY столбцы с равенственными фильтрами (=, IN), затем — диапазонные (BETWEEN, >=, <=). Столбцы с высокой кардинальностью, по которым часто делают точечные lookups, должны идти первыми.

Как убедиться, что индекс используется

ClickHouse показывает, сколько гранул было прочитано:

TIP

Запрос с трассировкой использования granules:

SELECT count()
FROM events
WHERE event_date = '2024-01-15'
SETTINGS send_logs_level = 'trace'

-- В логах ищите строку вида:
-- Selected 1/12208 parts by partition key, 1 parts by primary key,
-- 3/12208 marks by primary key, 3 marks to read from 1 ranges

Строка “marks to read” показывает, сколько гранул реально читается из общего числа.

Также можно использовать EXPLAIN:

EXPLAIN indexes = 1
SELECT count()
FROM events
WHERE event_date = '2024-01-15'

Вывод покажет Granules: 3 — сколько гранул запрос планирует прочитать. Если это число близко к общему числу гранул, индекс не помогает.

Практический пример: выбор ORDER BY

Допустим, у нас есть таблица событий аналитики: event_date Date, user_id UInt32, event_type String, revenue Float64.

Типичные запросы на дашборде:

Суммарный доход за день: WHERE event_date = '2024-01-15' → нужен prune по event_date
История конкретного пользователя: WHERE user_id = 12345 → нужен prune по user_id
Доход пользователя за период: WHERE user_id = 12345 AND event_date BETWEEN ... → нужен prune по user_id, затем date

Анализ:

Запрос 1 эффективен при ORDER BY (event_date, user_id) или ORDER BY (event_date, ...)
Запросы 2 и 3 эффективны при ORDER BY (user_id, event_date)
При ORDER BY (event_date, user_id): запрос 2 потребует полного сканирования

Рекомендуемый ORDER BY: ORDER BY (user_id, event_date) — user_id имеет высокую кардинальность и используется в равенственных фильтрах, event_date используется в диапазонных.

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

primary.idx — несжатый плоский массив значений ORDER BY ключа для первой строки каждой гранулы. Одна запись на 8192 строк.
Бинарный поиск в primary.idx → диапазон гранул → .mrk2 → байтовые смещения → .bin → чтение CompressedBlock.
PostgreSQL B-tree: одна запись на строку → огромный индекс. ClickHouse sparse index: одна запись на 8192 строк → тривиально малый.
WHERE на не-ключевые столбцы = полное сканирование всех гранул. Нет “фонового” индекса по всем столбцам.
Порядок столбцов в ORDER BY критичен: ставьте столбцы с равенственными фильтрами первыми, диапазонными — следом. Неправильный порядок = нет прунинга по первому столбцу.