Коротко о главномРазвернутьСвернуть
- Когда вы пишете SELECT * FROM users WHERE age > 30, вы редко задумываетесь о том, как именно СУБД физически хранит эти данные на диске.
- А между тем, от архитектуры страницы данных зависит, сколько лишних байт будет прочитано, насколько эффективно используется кэш процессора, и во что обойдутся обновления и удаления.
- В этой статье разберём три классические модели — NSM, DSM и PAX, а также заглянем в будущее — формат FastLanes, созданный специально под SIMD и GPU.
Когда вы пишете SELECT * FROM users WHERE age > 30, вы редко задумываетесь о том, как именно СУБД физически хранит эти данные на диске. А между тем, от архитектуры страницы данных зависит, сколько лишних байт будет прочитано, насколько эффективно используется кэш процессора, и во что обойдутся обновления и удаления. В этой статье разберём три классические модели — NSM, DSM и PAX, а также заглянем в будущее — формат FastLanes, созданный специально под SIMD и GPU.
1. Классика всех времен: страница NSM
Традиционная и самая распространённая архитектура в OLTP-СУБД (PostgreSQL, Oracle) — слотированная страница, относящаяся к семейству NSM (N-ary Storage Model). Страница, как правило, имеет фиксированный размер, чаще всего 8 или 16 КБ (может настраиваться параметром БД), и делится на три логические области:
· Заголовок страницы — содержит метаданные: размер страницы, количество слотов, смещение до свободного пространства и флаги.
· Таблица слотов — массив записей фиксированной длины, каждая из которых хранит смещение (offset) до начала соответствующей строки. Слоты упорядочены по позиции строки в таблице.
· Область данных — сами кортежи, расположенные последовательно, но в обратном порядке относительно таблицы слотов (данные растут с конца страницы в начало, а слоты — с начала в конец). Это позволяет эффективно управлять фрагментацией.
Особенности работы с изменениями на уровне страницы:
При обновлении строки, если её новый размер превышает старый, на старом месте сохраняется указатель (forwarding pointer), а обновлённая запись перемещается в свободную область страницы (или даже на другую страницу, если свободного места недостаточно). Это порождает цепочки переадресации, которые могут замедлять чтение.
При удалении строки соответствующий слот помечается как недействительный (например, устанавливается флаг deleted или смещение становится отрицательным). Физическое освобождение места происходит позже — при сборке мусора (VACUUM в PostgreSQL) или при перестройке страницы.
Главный недостаток:
Для запросов, которые читают миллионы строк, но выбирают лишь 2–3 атрибута из 20, NSM необходимо просканировать всю страницу целиком. В результате в кэш CPU загружаются все атрибуты, включая ненужные. Это не только увеличивает время I/O, но и порождает промахи кэша (cache misses), поскольку полезные данные перемешиваются с не нужными.
2. Колоночная страница DSM:
Научная работа Джорджа П. Коупленда и Сетрага Н. Хошафяна «A Decomposition Storage Model» (ACM SIGMOD) [1] предложила кардинально иной подход к организации данных на странице, получивший название DSM (Decomposition Storage Model).
В классической реализации DSM каждый атрибут таблицы хранится в отдельном наборе страниц. При этом страницы внутри одного атрибута содержат только значения этого столбца, расположенные в порядке строк. Для восстановления полной записи используется либо позиционный идентификатор (порядковый номер строки в странице), либо служебные битовые маски.
Преимущества на уровне страниц:
· Страница заполняется данными одного типа — это даёт значительный прирост в сжатии (RLE, дельта-кодирование, битовые карты) по сравнению с NSM-архитектурой.
· При сканировании одного-двух столбцов читается ровно столько страниц, сколько нужно для этих атрибутов, без загрузки не используемых в запросе колонок.
Обратная сторона:
Вставка или обновление строки требуют записи в страницы всех атрибутов, что превращается в доступ к множеству файлов и их соединение. Запрос SELECT * для ограниченного числа строк также вынужден выполнять дорогостоящее соединение страниц разных столбцов, что делает DSM неэффективной для OLTP.
Первоначально модель не получила широкого распространения именно из-за высокой стоимости сборки строк. Однако с ростом мощностей процессоров и объёмов оперативной памяти она стала основой для колоночных СУБД (Vertica, Greenplum, ClickHouse), где основная нагрузка — аналитические запросы.
3. PAX: гибридная модель данных
В 2001 году на конференции VLDB была представлена работа Анастасии Аламаки, Дэвида ДеВитта, Марка Хилла и Муниратнама Сивакумара «Weaving Relations for Cache Performance» [2], в которой авторы предложили комбинированный подход — PAX (Partition Attributes Crosswise).
Ключевая идея модели:
Страница остаётся целостной (содержит все атрибуты таблицы, как в NSM), что позволяет избавиться от дорогостоящих соединений файлов данных. Но внутри страницы данные разбиты по атрибутам: все значения первого атрибута собираются в непрерывный мини-блок. Следом идёт мини-блок второго атрибута, затем третьего, и так далее. В начале страницы располагается каталог (directory), указывающий смещение и размер каждого мини-блока.
Как происходит выборка данных:
Для запроса, выбирающего два столбца, СУБД обращается к странице и читает только те два мини-блока — остальные не попадают в кэш процессора, что снижает количество промахов.
Обновление всей строки не требует записи в отдельные файлы (как в DSM) — достаточно перезаписать соответствующие мини-блоки внутри одной страницы.
4. Современные реализации на основе PAX
Apache Parquet
Прямой наследник PAX. Файл разбивается на Row Groups (группы строк, типично 128 МБ – 1 ГБ), каждая из которых действует как крупная «страница» PAX. Внутри Row Group данные организованы по Column Chunks — это и есть мини-блоки разных атрибутов, только теперь они могут быть сжаты независимо друг от друга. Parquet также добавляет индексы и статистику на уровне Column Chunk (min, max, null count), что позволяет при сканировании пропускать целые блоки без разжатия.
Apache ORC (Optimized Row Columnar)
Аналог Parquet, используемый в Hive, Presto и Trino. Внутри ORC-файла выделяются Stripes (полосы), которые выполняют ту же роль, что и Row Groups в Parquet. Внутри Stripe данные хранятся по колонкам с добавлением индексов и словарей. По сути, это тоже PAX, но с более агрессивным сжатием и встроенной фильтрацией.
5. FastLanes — PAX, оптимизированный под SIMD и GPU
PAX-архитектура значительно улучшила предыдущие модели хранения данных, но она не учитывала характеристики процессора. Именно в этом направлении происходит дальнейшее развитие архитектуры хранения данных. Петер Бонч, учёный из исследовательского центра CWI (Нидерланды), предложил новый формат FastLanes, который оптимизирует хранение данных под возможности современных процессоров.
Файл FastLanes состоит из двух главных компонентов: Footer (футер) и Data (данные). Футер содержит метаданные, описание данных и их местонахождение в файле и может храниться отдельно от блока «Данные».
На верхнем уровне блок «Данные» повторяет архитектуру PAX: данные делятся на группы строк и атрибуты. В отличие от существующих типов файлов, в FastLanes группы строк содержат количество записей, кратное 1024. Это позволяет избежать материализации данных в основной памяти и выполнять всю работу на уровне процессора. Следующим важным нововведением является использование сжатия LWC (Light-Weight-Compression). Вместо тяжеловесных алгоритмов по типу Zstd, которые не позволяют распараллелить обработку данных, применяются FSST, DICT, ALP при каскадном (рекурсивном) применении которых достигается уровень сжатия Snappy за более короткий промежуток времени [3]. Кроме этого, для каждой колонки данных могут применяться разные операторы кодирования. Сжатые данные хранятся в сегментах, в которых кроме самих данных хранятся смещения на отдельные вектора, что позволяет читать данные на уровне одного вектора вместо целого блока, как в старых форматах.
Когда данные читаются из оперативной памяти в процессор, закодированный вектор, содержащий 1024 значения, разжимается и полностью помещается в кэш процессора. Напротив, старые форматы файлов не только используют непараллельные алгоритмы сжатия, но и применяют их к целым Row Group, что влечёт за собой использование основной памяти и уменьшение скорости обработки [3].
Использованные источники:
- Copeland G.P., Khoshafian S.N. A Decomposition Storage Model. Proceedings of ACM SIGMOD, 1985.
- Ailamaki A., DeWitt D., Hill M., Sivakumar M. Weaving Relations for Cache Performance. Proceedings of VLDB, 2001.
- Boncz P., Afroozech A., et al. The FastLanes File Format: specification.
