Колоночные СУБД против строчных, как насчет компромисса?

Колоночные СУБД активно развивались в нулевых годах, на данный момент они нашли свою нишу и практически не конкурируют с традиционными, строчными системами. Под катом автор разбирается, возможно ли универсальное решение и насколько оно целесообразно.

«Во всём виден прогресс.… не надо бояться, что тебя вызовут в канцелярию и скажут: ”Мы тут посовещались, и завтра вы будете четвертованы или сожжены по вашему собственному выбору.“ Это был бы тяжелый выбор. Я думаю, многих из нас он бы поставил в тупик.»
Ярослав Гашек. Похождения бравого солдата Швейка.

Предыстория

Сколько существуют базы данных, столько и длится это идеологическое противостояние. Автор из любопытства нашел в закромах книгу Дж.Мартина из IBM [1] 1975 года и тут же наткнулся в ней на слова (стр.183): “В работах […] используются бинарные отношения, т.е. отношения только двух доменов. Известно, что бинарные отношения придают наибольшую гибкость базе. Однако в коммерческих задачах удобными являются отношения различных степеней.” Под отношениями здесь понимаются именно реляционные отношения. А упомянутые работы датированы 1967...1970 гг.

Пусть Sybase IQ была первой промышленно используемой колоночной СУБД, но по крайней мере на уровне идей, всё проговаривалось за 25 лет до неё.

На данный момент являются поколоночными или в той или иной мере поддерживают эту возможность следующие СУБД (взято в основном здесь):

Коммерческие

• 1010data's Tenbase database
• Alterian's Engine
• Aster Data Systems
• Calpont InfiniDB Enterprise Edition
• EXASOL
• FAME
• FluidDB
• Greenplum
• Hive Intelligence Ltd Hex Engine
• Infobright Enterprise Edition
• KDB
• Kickfire
• Microsoft SQL Server 2012+ (Enterprise Edition)
• Oracle Retail Predictive Application Server (RPAS)
• Paraccel Analytic Database
• SAND CDBMS
• SAP HANA
• SenSage
• Sybase IQ
• Vectorwise
• Vertica

Free & open source

• Calpont InfiniDB Community Edition
• ClickHouse
• Infobright Community Edition
• Greenplum Community Edition
• LucidDB
• Metakit
• MonetDB
• C-Store
• S programming language and GNU R incorporate column-oriented data structures for statistical analyses

Различия

Реляционное отношение есть набор кортежей, в сущности двумерная таблица. Соответственно имеются две возможности хранения — построчная или поколоночная. Разделение это немного искусственное, логическое. Разработчики баз данных давно уже не занимаются планированием записей по барабанам и дорожкам. Оптимально разложить данные СУБД по файловой системе(мам) — задача администраторов СУБД, а как как файловая система располагает данные на физических дисках известно в основном разработчикам файловых систем.

Было бы логично предоставить СУБД самой решать в каком порядке хранить данные. Здесь мы говорим о некоторой гипотетической СУБД, которая поддерживает оба варианта организации хранения данных и имеет возможность назначить таблице любой из них. Мы не рассматриваем вполне популярный вариант поддерживать две БД — одну для работы, вторую для аналитики/отчетов. Также как и колоночные индексы a la Microsoft SQL Server. Не потому что это плохо, а для проверки гипотезы что существует какой-то более изящный способ.

К сожалению, никакая самая гипотетическая СУБД не сможет выбрать как лучше хранить данные. Т.к. не обладает пониманием того, как мы эти данные собираемся использовать. А без этого выбор сделать невозможно, хотя он очень важен.

Самым ценным качеством СУБД является способность быстро обрабатывать данные (и требования ACID, само собой). Скорость работы СУБД в основном определяется числом дисковых операций. Отсюда возникают два крайних случая:

• Данные быстро изменяются/добавляются, надо успевать записывать. Очевидное решение — строка (кортеж) по возможности расположена на одной странице, быстрее не сделать.
• Данные меняются крайне редко или вообще не меняются, мы многократно читаем данные, причем единовременно задействовано лишь небольшое число колонок. В этой ситуации логично использовать поколоночный вариант хранения, тогда при чтении поднимется минимально возможное число страниц.

Но это крайние случаи, в жизни всё не так очевидно.

• Если требуется прочитать всю таблицу, то с точки зрения числа страниц не важно построчно или поколоночно расположены данные. Т.е некоторая разница, конечно есть, в поколоночном варианте мы имеем возможность лучше сжимать информацию, но в данный момент это не принципиально.
• А вот с точки зрения производительности разница есть т.к. при построчной записи чтение с диска будет происходить более линейно. Меньшее число пробросов головок жесткого диска заметно ускоряет чтение. Более предсказуемое чтение файла при построчной записи позволяет операционной системе (ОС) эффективнее использовать дисковый кэш. Это имеет значение даже для SSD дисков, т.к загрузка по предположению (read ahead) чаще приводит к успеху.
• Update далеко не всегда меняет запись целиком. Предположим, частый случай — изменение двух колонок. Тогда будет хорошо, если данные этих колонок окажутся на одной странице, ведь потребуется только одна блокировка страницы на запись вместо двух. С другой стороны, если данные разнесены по страницам, это даёт возможность разным транзакциям менять данные одной строки без конфликтов.
  
  Вот здесь повнимательнее. Гипотетический выбор — сделать таблицу строчной или колоночной, СУБД должна сделать в момент её создания. Но чтобы сделать этот выбор неплохо бы знать, например, каким образом мы собираемся эту таблицу менять. Может стоит подбросить монетку?
  
• Предположим, мы используем для хранения древовидную структуру (ex:clustered index). В этом случае добавление данных или даже их изменение могут привести к пере-балансировке дерева или его части. При строчном хранении возникает (минимум одна) блокировка на запись, которая может затронуть значительную часть таблицы. В поколоночном варианте такие истории происходят гораздо чаще, но наносят гораздо меньше ущерба т.к. касаются только конкретной колонки.
  
• Рассмотрим выборку с фильтрацией по индексу. Предположим, выборка достаточна разреженная. Тогда построчная запись имеет предпочтение, ведь в этом случае лучше соотношение полезной информации к прочитанной за компанию.
• Если же фильтрация даёт более плотный поток и требуется лишь небольшая часть колонок, дешевле становится поколоночный вариант. Где водораздел между этими случаями, как его определить?

Иными словами, ни при каких обстоятельствах наша гипотетическая СУБД не возьмет на себя ответственность выбора между строчным и поколоночным вариантами хранения, это должен сделать проектировщик БД.

Впрочем, учитывая вышесказанное, и проектировщик БД окажется в ситуации очень тяжелого выбора. Многих из нас он бы поставил в тупик.

А что если

В сущности и поколоночный и строчный варианты — крайние случаи одной идеи — нарезать таблицу на “ленточки“ и внутри каждой ленты хранить данные построчно. Просто в одном случае лента одна, в другом ленты вырождаются до одной колонки.

Так почему бы не допустить и промежуточные варианты — если данные некоторых колонок приходят/читаются вместе, пусть и окажутся на одной ленте. А если в ленте не оказалось данных (NULL-ы), то и хранить ничего не надо. Заодно снимается проблема максимального размера строки — можно расщепить таблицу, когда есть риск, что строка не поместится на одной странице.

Идея эта не так чтобы особо оригинальная, автору доводилось и видеть подобное и самому применять. Элемент новизны в том, чтобы дать возможность проектировщику БД возможность самому определять как именно его таблица будет разбита на части и в каком виде данные попадут на диск.

Мы для себя это сделали следующим образом:

• при создании таблицы информация о наших предпочтениях передаётся SQL-процессору с помощью прагм
• изначально при создании таблицы предполагается, что строка целиком будет расположена на одной странице В-дерева
• однако можно использовать — — #pragma page_break
  для того, чтобы сообщить SQL-процессору, что следующие колонки будут расположены на другой странице (в другом дереве)
• использование — — #pragma column_based
  позволяет лаконично сказать, что идущие далее колонки расположены каждая на своём дереве
• — — #pragma row_based
  отменяет действие column_based
• таким образом, таблица состоит из одного или более B-дерева, первым элементом ключа которого является скрытое IDENTITY поле. Есть мнение, что порядок, в котором создаются записи (вполне может коррелировать с порядком, в котором записи будут читать) тоже имеет значение и не стоит им пренебрегать. Первичный ключ является отдельным деревом, впрочем, это уже не относится к теме.

Как это может выглядеть на практике?

Например, так:

CREATE TABLE twomass_psc (
    ra double precision,
    decl double precision,
    …
    -- #pragma page_break
    j_m real,
    j_cmsig real,
    j_msigcom real,
    j_snr real,
    h_m real,
    h_cmsig real,
    h_msigcom real,
    h_snr real,
    k_m real,
    k_cmsig real,
    k_msigcom real,
    k_snr real,
    -- #pragma page_break
    …
    coadd_key integer,
    coadd smallint
);

Для примера взята основная таблица атласа 2MASS, легенда здесь и здесь.
J, H, K — инфракрасные под-диапазоны, данные по ним есть смысл хранить вместе, поскольку в исследованиях они обрабатываются вместе. Вот, например:


Первая попавшаяся картинка.

Или вот, даже красивее:

Самое время подтвердить, что это имеет какой-то практический смысл.

Результаты

Ниже представлена:

• фазовая диаграмма (X-номер записываемой страницы, Y-номер последней записанной ранее) порядка записи страниц (логических номеров) на диск при создании таблицы в двух вариантах
• поколоночном, он обозначен как by_1
• и для таблицы, порезанной по 16 колонок, он обозначен как by_16
• всего колонок 181

Рассмотрим повнимательнее как она устроена:

• Вариант by_16 заметно компактнее, что логично, предельный — строчный вариант дал бы просто прямую линию (с выбросами).
• Треугольные выбросы — запись промежуточных страниц В-деревьев.
• Показана запись данных, очевидно, чтение будет выглядеть примерно так же.
• Выше говорилось, что все варианты записывают одно и тоже количество информации и поток, который надо вычитать, примерно одинаков (± эффективность сжатия).
  Но здесь очень наглядно показано, что в поколоночном варианте деревья растут с разной скоростью за счет специфики данных (в одной колонке они часто повторяются и сжимаются очень хорошо, в другой колонке — шум с точки зрения компрессора). В результате одни деревья забегают вперед, другие запаздывают, при чтении мы объективно получаем очень неприятный для файловой системы “рваный” режим чтения.
• Так вот, вариант by_16 намного предпочтительнее для чтения чем поколоночный, он практически равен в комфорте по-строчному варианту.
• Но при этом вариант by_16 обладает основными плюсами поколоночного варианта в случае, когда требуется небольшое к-во колонок. Особенно если расщеплять таблицу не механически по 16 штук, а осмысленно, после анализа вероятностей их совместного использования.

Источники

[1] Дж.Мартин. Организация баз данных в вычислительных системах. “Мир”, 1978
[2] Колоночные индексы, особенности использования
[3] Daniel J. Abadi, Samuel Madden, Nabil Hachem. ColumnStores vs. RowStores: How Different Are They Really?, Proceedings of the ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, June 2008
[4] Michael Stonebraker, Uğur Çetintemel. «One Size Fits All»: An Idea Whose Time Has Come and Gone, 2005