СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности?

2008 г.

СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности?

Дэниэль Абади, Сэмюэль Мэдден, Набил Хачем
Пересказ: Сергей Кузнецов
Оригинал: 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

В 2008 г. коллектив исследователей, идейно возглавляемый Майклом Стоунбрейкером, представил на конференции SIGMOD’2008 два доклада, которые продолжают серию публикаций, посвященных новым архитектурам систем управления данными (см. мою заметку Универсальность и специализация: время разбивать камни?, опубликованную в библиотеке CITForum.ru осенью 2007 г.). Пересказ текста первого из этих докладов, опубликован с моей небольшой вступительной заметкой под названием OLTP в Зазеркалье.

Если в первой статье продолжалась тема новых архитектур СУБД, предназначенных для поддержки приложений класса OLTP, то вторая статья посвящена архитектуре СУБД, основанной на хранении данных по столбцам и ориентированной на использование в приложениях категории OLAP. В опубликованном ранее на CITForum.ru переводе статьи Пригоден ли один размер для всех? Часть 2: результаты тестовых испытаний приводились впечатляющие сравнения производительности поколоночной СУБД C-Store с некоей продвинутой коммерческой СУБД. Но тогда сравнения производились на собственном тестовом наборе авторов, и, честно говоря, их результаты были не слишком убедительны.

Новая статья основывается на результатах, полученных при использовании публично опубликованного тестового набора The Star Schema Benchmark (SSB), который является упрощенным вариантом известного тестового набора TPC-H. Кроме того, авторы благоразумно отказались от прямого сравнения C-Store с одной из известных коммерческих СУБД со строчным хранением данных (в статье ее для конспирации называют System X). Они показали, что невозможна эффективная эмуляция колоночного хранилища на строчной System X, и что C-Store, лишенная существенных оптимизаций, не демонстрирует выдающихся результатов. Результаты, описанные в статье, кажутся мне обоснованными и вполне заслуживающими доверия.

Как всегда, я постарался дополнить список литературы ссылками на источники, свободно доступными в Internet. Кроме того, я включил в свой пересказ два приложения. В приложении 1 содержатся тексты на языке SQL запросов из тестового набора The Star Schema Benchmark (SSB), а в приложении 2 – определения таблиц базы данных этого тестового набора. При наличии этих приложений читать и понимать статью проще.

Сергей Кузнецов

Аннотация

Системы баз данных с хранением данных по столбцам («колоночные хранилища», «column-store») вызывают интерес у многих исследователей. Известно, что эти системы баз данных показывают на порядок лучшую производительность по сравнению с традиционными системами баз данных («строчными хранилищами», «row-store») на аналитических рабочих нагрузках, таких, которые возникают в хранилищах данных, приложениях поддержки принятия решений и интеллектуального анализа данных. В двух словах эта разница в производительности объясняется очень просто: колоночные хранилища позволяют выполнять меньше обменов с дисками при выполнении запросов на выборку данных, поскольку с диска (или из основной памяти) считываются значения только тех атрибутов, которые упоминаются в запросе.

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

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

1. Введение

В последние годы появился ряд систем баз данных с хранением данных по столбцам, включая MonetDB [9, 10] и C-Store [22]. Разработчики этих систем утверждают, что их подход обеспечивает выигрыш в производительности на порядки величин при некоторых рабочих нагрузках, в особенности, при аналитических рабочих нагрузках с большим числом запросов на чтение данных, подобных тем, которые встречаются в приложениях хранилищ данных.

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

Часто разработчики систем с хранением данных по столбцам говорят о наличии фундаментального различия между разработанным с нуля колоночным хранилищем и строчными хранилищами, в которых используется физическая схема, ориентированная на столбцы, в действительности, не анализируя альтернативные физические схемы в строчных хранилищах. Цель данной статьи &ndash на основе систематического подхода ответить на поставленный выше вопрос. Один из авторов статьи является профессиональным администратором баз данных, специализирующимся на одной из популярных коммерческих СУБД с хранением данных по строкам. Он разработал ряд физических схем базы данных для недавно предложенного эталонного тестового набора хранилищ данных – Star Schema Benchmark (SSBM) [18, 19], изыскивая схемы, которые были бы как можно в большей степени считать «ориентированными на столбцы». К числу основных использованных приемов относятся следующие:

вертикальное разделение таблиц базы данных в набор двухколоночных таблиц, состоящих из пар (ключ таблицы, атрибут), так чтобы при выполнении запроса требовалось считывать значения только требуемых столбцов;
использование планов выполнения запросов, основанных на использовании только индексов; для этого создавался набора индексов, которые покрывают все столбцы, упоминаемые в запросе; в этом случае система баз данных может выполнить запрос вообще без обращений к основным (ориентированным на строки) таблицам;
использование набора материализованных представлений, таких что для каждого запроса тестового набора имеется некоторое представление в точности с теми столбцами, которые упоминаются в этом запросе; хотя при применении этого подхода требуется очень много дисковой памяти, он предоставляет «наилучшую возможность» строчному хранилищу и обеспечивает полезную информацию для сравнения с колоночной реализацией.

Авторы сравнивали производительность, обеспечиваемую применением этих различных методов, с базовым уровнем производительности СУБД с открытыми кодами C-Store [22] на тестовом наборе SSBM. Результаты сравнения показывают, что, несмотря на возможность применения перечисленных методов для эмуляции физической структуры колоночного хранилища внутри строчного хранилища, производительность обработки запросов в традиционных СУБД остается довольно низкой. Следовательно, основным вкладом этого исследования является демонстрация того, что архитектура систем с хранением данных по столбцам обладает фундаментальными особенностями, делающими такие системы более пригодными к обработке рабочей нагрузки хранилищ данных. Этот результат важен, поскольку позволяет отмести расхожее мнение, что поставщиками существующих СУБД с хранением данных по строкам было бы совсем нетрудно внедрить поколоночное хранение данных на физическом уровне.

Авторы подчеркивают, что их целью являлось не нахождение способа быстрейшего выполнения SSBM в системе, ориентированной на хранение по строкам, а оценка производительности конкретных «колоночных» физических реализаций, что приводит их ко второму вопросу. Какие из многочисленных предлагавшихся в литературе оптимизаций, которые предназначаются для систем с хранением данных по столбцам, играют основную роль в обеспечении преимуществ колоночных хранилищ над строчными хранилищами при выполнении рабочей нагрузки хранилищ данных?

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

отложенная материализация (в сочетании с описываемой ниже оптимизацией итерации по блокам это метод называют также векторизуемой обработкой запросов [9, 25]), когда в плане выполнения запроса столбцы, считанные с диска, соединяются в строки как можно позже;
итерация по блокам [25], когда несколько значений некоторого столбца передаются от одной операции к другой в виде блока, вместо того, чтобы использовать покортежные итераторы в стиле Volcano [11]; если значения имеют фиксированный размер, то они итерируются через массив;
методы сжатия, специфичные для столбцов, такие как продольное кодирование (run-length encoding), позволяющие производить операции прямо над сжатыми данными при использовании планов с отложенной материализацией [4];
кроме того, авторы предлагают новую оптимизацию, названную ими «скрытым соединением» («invisible join»), которая позволяет существенно повысить эффективность соединений в колоночных хранилищах с отложенной материализацией, в особенности, для схем баз данных, характерных для хранилищ данных.

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

Таким образом, тремя достижениями статьи являются следующие.

Показано, что попытки эмуляции колоночного хранилища на основе строчного хранилища не приводят к получению хорошей производительности, и что разнообразные методы, обычно считающиеся «хорошими» для повышения производительности хранилищ данных (планы с использованием только индексов, битовые индексы и т.д.), не слишком исправляют эту ситуацию.
Предложен новый метод повышения эффективности соединений, названный скрытым соединением. На основе экспериментов демонстрируется, что во многих случаях выполнение соединений с использованием этого метода может происходить не менее эффективно, чем поиск и выбор данных из одной денормализованной таблицы, уже содержащей материализованный результат соединения. На основе этого авторы заключают, что денормализация, являющаяся важным, но дорогостоящим (поскольку требует много дисковой памяти) и сложным (нужно заранее принять решение о том, какие таблицы имеет смысл денормализовывать) методом повышения производительности в строчных хранилищах (особенно, в хранилищах данных), не обязательно требуется в колоночных хранилищах (или ее можно использовать с существенно меньшими расходами и сложностью).
Выполнен анализ факторов, влияющих на производительность СУБД с хранением данных по столбцам при рабочих нагрузках хранилищ данных. Выяснено влияние на общую производительность отложенной материализации, сжатия, итерации по блокам и скрытых соединений. Полученные результаты подтверждают предыдущие утверждения о производительности колоночных хранилищ на новом тестовом наборе хранилищ данных (SSBM) и демонстрируют, что только лишь хранение данных по столбцам – без сжатия и отложенной материализации – не обеспечивает значительного выигрыша в производительности у хорошо оптимизированных систем с хранением данных по строкам.

Оставшаяся часть статьи организована следующим образом. Авторы начинают с описания предыдущих работ в области СУБД с хранением данных по столбцам, включая ранее производившиеся сравнения производительности и архитектурные инновации (разд. 2). В разд. 3 приводится обзор SSBM. После этого в разд. 4 описываются методы разработки физических схем базы данных, использовавшихся в системе с хранением данных по строкам, а в разд. 5 – физическая организация данных и методы выполнения запросов, применявшиеся в системе C-Store. В разд. 6 представлены результаты сравнения этих двух систем. Сначала сравнивается производительность оптимизированной СУБД с хранением данных по строкам с производительностью базового варианта C-Store, а затем изучается, какие методы эффективной обработки запросов, используемые в этой системе, оказались наиболее существенными при выполнении SSBM.

Вперёд