Columnstore Indexes

Columnstore index (столбцовый индекс) — это технология хранения и индексирования данных в реляционных базах данных, при которой данные физически группируются и сжимаются не по строкам, а по столбцам. Основное назначение columnstore index — значительное ускорение выполнения аналитических запросов (OLAP) и операций агрегации над большими объёмами данных за счёт векторизованной обработки, высокого коэффициента сжатия и пропуска ненужных столбцов.

История

Первые идеи столбцового хранения данных появились в 1970-х годах в контексте систем управления базами данных (СУБД) для аналитической обработки. Однако практическая реализация стала возможна только с развитием массово-параллельных архитектур и увеличением объёмов оперативной памяти. В 2000-х годах технологии columnstore начали внедряться в коммерческие СУБД, такие как Sybase IQ, Vertica, Amazon Redshift и Google BigQuery. В 2012 году компания Microsoft представила columnstore index для своей СУБД SQL Server, начиная с версии 2012. Впоследствии аналогичные механизмы появились в PostgreSQL (расширение cstore_fdw, затем нативная реализация в версии 12), MySQL (в виде движка InnoDB с поддержкой secondary columnstore), а также в СУБД с открытым исходным кодом, таких как ClickHouse и DuckDB.

Принцип работы

В отличие от традиционных rowstore index (строчных индексов), где данные каждой строки хранятся вместе, columnstore index хранит все значения одного столбца последовательно. Это позволяет:

• Сжимать данные: значения одного столбца часто имеют одинаковый тип и повторяющиеся значения, что даёт высокий коэффициент сжатия (в 5–15 раз по сравнению со строчным хранением).
• Выполнять векторизованную обработку: операции (суммирование, подсчёт, фильтрация) выполняются сразу над блоками значений, а не над каждой строкой, что снижает накладные расходы на интерпретацию.
• Пропускать ненужные столбцы: при выполнении запроса система загружает только те столбцы, которые упомянуты в SELECT, WHERE или GROUP BY, а не все столбцы таблицы.

Физически данные в columnstore index организуются в row groups (группы строк) — обычно по 1–10 миллионов строк. Каждая группа строк делится на column segments (сегменты столбцов), которые сжимаются независимо. Для ускорения поиска по условиям используется segment elimination (исключение сегментов): если в сегменте нет значений, удовлетворяющих условию, он пропускается.

Классификация

По типу хранения

• Clustered columnstore index: данные таблицы физически хранятся в столбцовом формате. Таблица не имеет традиционного строчного индекса; все операции вставки, обновления и удаления выполняются через механизм дельты (см. ниже). Применяется для аналитических таблиц с большими объёмами данных.
• Nonclustered columnstore index: создаётся поверх существующей строчной таблицы (rowstore). Данные дублируются в столбцовом формате, что позволяет ускорять аналитические запросы, не изменяя исходную структуру. Однако такой индекс требует дополнительного места и накладных расходов на синхронизацию.

По способу обновления

• Read-only columnstore index: данные загружаются один раз и не изменяются. Обеспечивает максимальное сжатие и производительность, но не поддерживает операции INSERT, UPDATE, DELETE. Используется для исторических данных.
• Updateable columnstore index: поддерживает модификацию данных через механизм delta store (хранилище дельты). Новые строки сначала помещаются в небольшую строчную структуру (delta rowgroup), а затем периодически перемещаются в основной столбцовый формат в фоновом режиме. Это позволяет сочетать высокую производительность запросов с возможностью оперативного обновления.

Характеристики

Сжатие

Columnstore index использует несколько алгоритмов сжатия, в том числе:

• Dictionary compression (словарное сжатие): для столбцов с небольшим числом уникальных значений (например, категории, статусы) создаётся словарь, а вместо значений хранятся их коды.
• Run-length encoding (кодирование длин серий): последовательные повторяющиеся значения заменяются парой (значение, количество повторений).
• Bit packing (упаковка битов): значения упаковываются в минимальное количество бит, необходимое для их представления.
• XPRESS (алгоритм, используемый в SQL Server): комбинация словарного сжатия и кодирования длин серий.

Тип сжатия выбирается автоматически на основе статистики данных. Коэффициент сжатия сильно зависит от характера данных: для столбцов с низкой кардинальностью (мало уникальных значений) он может достигать 20–30 раз, для столбцов с высокой кардинальностью (например, уникальные идентификаторы) — 2–4 раза.

Производительность

Основное преимущество columnstore index — скорость выполнения аналитических запросов. По данным Microsoft, для типовых OLAP-нагрузок (агрегация по миллиардам строк) columnstore index может быть в 10–100 раз быстрее, чем эквивалентный rowstore index. Это достигается за счёт:

• Batch mode execution (пакетный режим выполнения): операции обрабатываются блоками по 64–1024 строки, а не по одной строке.
• Column elimination: считываются только необходимые столбцы.
• Segment elimination: пропускаются сегменты, не содержащие релевантных данных.
• Predicate pushdown: условия фильтрации применяются на уровне чтения данных, до передачи в процессор.

Ограничения

• Операции с одной строкой: SELECT * или UPDATE одной строки выполняются медленнее, чем в rowstore, из-за необходимости декомпрессии и сборки строки из столбцов.
• Индексы: columnstore index не поддерживает создание дополнительных индексов (кроме самого себя). Для ускорения поиска по конкретным значениям требуется использовать segment elimination или строчные индексы.
• Память: при выполнении запросов columnstore index требует значительного объёма оперативной памяти для хранения сжатых данных и промежуточных результатов.
• Транзакции: в updateable columnstore index операции модификации могут приводить к фрагментации delta store, что требует периодической перестройки (rebuild) индекса.

Применение

Columnstore index широко используется в системах, где требуется быстрая обработка больших объёмов данных:

• Хранилища данных (Data Warehouses): агрегация продаж, финансовые отчёты, анализ клиентской базы.
• Системы бизнес-аналитики (BI): построение отчётов, дашбордов, кубов данных.
• Логирование и телеметрия: хранение и анализ событий, логов, метрик производительности.
• Научные и инженерные расчёты: обработка результатов моделирования, сенсорных данных, геномных последовательностей.

Примеры использования

• Microsoft SQL Server: columnstore index поддерживается во всех редакциях, начиная с SQL Server 2012. В версии 2016 появилась поддержка updateable clustered columnstore index.
• PostgreSQL: начиная с версии 12, поддерживается columnstore через расширение cstore_fdw (для внешних таблиц) и нативный механизм CREATE TABLE ... USING columnstore (в версии 14+).
• ClickHouse: СУБД с открытым исходным кодом, изначально спроектированная для столбцового хранения. Используется для анализа логов, веб-аналитики и мониторинга.
• Amazon Redshift: облачное хранилище данных, основанное на столбцовом хранении. Поддерживает columnstore index через распределение данных по столбцам и сжатие.
• Google BigQuery: бессерверная аналитическая СУБД, автоматически использующая столбцовое хранение и векторизованную обработку.

Интересные факты

• В columnstore index сжатие может быть настолько эффективным, что таблица размером 100 ГБ в строчном формате может занимать 5–10 ГБ в столбцовом.
• В SQL Server columnstore index использует batch mode только для операций, поддерживающих пакетную обработку (агрегации, фильтры, соединения). Операции с одной строкой выполняются в строчном режиме.
• В ClickHouse столбцовое хранение реализовано на уровне движка таблиц (MergeTree), что позволяет комбинировать сжатие, партиционирование и репликацию.
• В PostgreSQL нативная поддержка columnstore появилась относительно поздно (версия 12, 2019 год), что связано с архитектурой, изначально ориентированной на строчное хранение.

Критика

Несмотря на преимущества, columnstore index не является универсальным решением. Критики отмечают:

• Непригодность для OLTP-нагрузок: операции с одной строкой (например, поиск по первичному ключу) выполняются медленнее, чем в rowstore.
• Сложность администрирования: для поддержания производительности требуется периодическая перестройка индекса, особенно при частых обновлениях.
• Зависимость от характера данных: эффективность сжатия и скорость запросов сильно варьируются в зависимости от распределения значений и типов данных.
• Ограниченная поддержка в некоторых СУБД: не все реляционные СУБД имеют полноценную реализацию columnstore index, а в некоторых (например, MySQL) она доступна только в коммерческих версиях.

Источники

• Microsoft Docs. Columnstore Indexes. SQL Server 2012–2022.
• PostgreSQL Documentation. Columnar Storage. Version 12–16.
• ClickHouse Documentation. MergeTree Engine.
• Amazon Redshift Documentation. Columnar Storage and Compression.
• Google Cloud BigQuery Documentation. Storage and Query Execution.
• Stonebraker, M. et al. (2005). C-Store: A Column-oriented DBMS. VLDB.
• Abadi, D. et al. (2013). The Design and Implementation of Modern Column-Oriented Database Systems. Foundations and Trends in Databases.