СУБД с хранением данных по столбцами и по строкам
Анализ преимуществ колоночных хранилищ
Как говорилось в разд. 5, все три оптимизации, ориентированные на системы с хранением данных по столбцам, существенно повышают производительность соответствующих систем баз данных. Это сжатие, отложенная материализация и итерация по блокам. Кроме того, авторы расширили возможности C-Store методом скрытых соединений, который, как они ожидали, также будет способствовать повышению производительности. По-видимому, именно эти оптимизации являются причиной показанного на рис. 5 различия в производительности между колоночным хранилищем и вариантом строчного хранилища с материализованными представлениями, для которого имелся такой же объем ввода-вывода, что и для колоночного хранилища. Чтобы проверить это предположение, авторы последовательно удаляли оптимизации из базового варианта C-Store и после каждого шага измеряли производительность.Удалить сжатие из C-Store было просто, поскольку в C-Store имеется специальный флаг, управляющий включением и отключением этого режима. Удалить метод скрытого соединения было тоже просто, потому что это новая операция, включенная в систему самими авторами. Для удаления отложенной материализации авторам пришлось вручную кодировать планы запросов, чтобы кортежи конструировались в начале выполнения плана. Удалить итерацию по блокам оказалось несколько труднее, чем перечисленные три оптимизации. В C-Store доступ к данным возможен через два интерфейса: «getNext» и «asArray». При применении первого метода требуется вызов функции для каждого очередного значения, в то время как во втором случае возвращается указатель на массив, который можно итерировать напрямую. Для операций, используемых в планах запросов SSBM и производящих доступ к блокам через интерфейс «asArray», авторы написали их альтернативные версии с использованием «getNext». Это привело только к существенному замедлению выполнения операций ограничения.
На рис. 7(a) показаны детальные (для каждого запроса) результаты последовательного удаления этих оптимизаций из C-Store; на рис. 7(b) эти результаты усреднены по всем запросам SSBM.
Следовательно, оптимизацию «перепись в предикат between» можно было использовать не менее одного раза для каждого запроса.
Понятно, что наиболее существенными оптимизациями являются сжатие и отложенная материализация. Сжатие повышает производительность в среднем в два раза. Однако, как отмечалось в разд. 5, авторы не поддерживают избыточного хранения таблицы фактов с несколькими порядками сортировки для получения полного преимущества от сжатия (отсортирован только один столбец – orderdate, и два столбца – quantity и discount – вторично отсортированы). Столбцы таблицы фактов, используемые в запросах SSBM, не очень хорошо сжимаются, если они не упорядочены, поскольку они являются либо ключами (и их множество обладает большой мощностью), либо случайными значениями. Первое звено запросов, в котором имеется доступ ко всем трем упорядоченным столбцам, демонстрирует преимущество по производительности, получаемое при использовании в запросах сильно сжатых столбцов. В этом случае сжатие приводит к повышению производительности на порядок. Так происходит из-за того, что последовательности значений в этих упорядоченных столбцах могут быть продольно закодированы (run length encoded, RLE). Продольное кодирование не только обеспечивает хороший коэффициент сжатия и, тем самым, сокращает накладные расходы ввода-вывода, но также и позволяет очень просто выполнять операции над сжатыми данными (например, предикат или агрегатную функцию можно применить сразу ко всей последовательности). Первично отсортированный столбец orderdate содержит всего 2405 уникальных значений, и поэтому средняя длина последовательности для этого столбца составляет 25000. Для его хранения требуется менее 64 килобайт дискового пространства.
Другой существенной оптимизацией является отложенная материализация. Эта оптимизация удалялась последней, поскольку в процессе конструирования кортежей данные требуется распаковывать, и ранняя материализация приводит к выполнению, ориентированному на строки, что препятствует применению скрытых соединений.
Отложенная материализация обеспечивает почти трехкратное повышение производительности. Так происходит, прежде всего, из-за селективных предикатов в некоторых запросах SSBM. Чем более селективен предикат, тем расточительнее конструировать кортежи в начале выполнения плана запроса, поскольку большинство этих кортежей немедленно отфильтруется.
Заметим, что после удаления всех оптимизаций колоночное хранилище ведет себя подобно строчному хранилищу. Столбцы немедленно «сшиваются» и обрабатываются после этого так же, как в строчном хранилище. Поэтому можно было бы ожидать, что колоночное хранилище будет выполнять запросы подобно строчному хранилищу с материализованными представлениями, поскольку требования к вводу-выводу и обработка запросов у них аналогичны – единственным различием является необходимость конструирования кортежей в начале выполнения плана запроса в колоночном хранилище. В подразделе 6.1 авторы предостерегали против прямых сравнений с System X, но при сравнении этих показателей со случаем CS Row-MV с рис. 5 можно видеть, насколько дорогостоящим может быть конструирование кортежей. Это согласуется с предыдущими результатами авторов.
Аннотация
Системы баз данных с хранением данных по столбцам («колоночные хранилища», «column-store») вызывают интерес у многих исследователей. Известно, что эти системы баз данных показывают на порядок лучшую производительность по сравнению с традиционными системами баз данных («строчными хранилищами», «row-store») на аналитических рабочих нагрузках, таких, которые возникают в хранилищах данных, приложениях поддержки принятия решений и интеллектуального анализа данных. В двух словах эта разница в производительности объясняется очень просто: колоночные хранилища позволяют выполнять меньше обменов с дисками при выполнении запросов на выборку данных, поскольку с диска (или из основной памяти) считываются значения только тех атрибутов, которые упоминаются в запросе.Такое упрощенное представление может навести на мысль, что можно получить выгоду от хранения данных по столбцам, просто воспользовавшись строчным хранилищем с вертикально разделенной схемой, либо проиндексировав все столбцы, чтобы обеспечить к ним независимый доступ. В этой статье демонстрируется, что подобное предположение неверно. Сравнивается производительность коммерческого строчного хранилища в различных конфигурациях с производительностью колоночного хранилища и показывается, что строчное хранилище обладает существенно меньшей производительностью на недавно предложенном эталонном тестовом наборе для хранилищ данных. Затем анализируется эта разница в производительности и демонстрируется, что между системами имеются существенные различия на уровне выполнения запросов (кроме очевидных различий на уровне хранения).
Эти различия обсуждаются более детально, и выявляется воздействие на производительность колоночных хранилищ различных методов выполнения запросов, включая векторизуемую обработку запросов, сжатие и новый алгоритм соединения, описываемый в этой статье. В заключение подчеркивается, что хотя при использовании системы баз данных с хранением данных по строкам можно добиться некоторого выигрыша в производительности, который обеспечивают колоночные хранилища, для получения всех преимуществ последнего подхода необходимо внести изменения и на уровне хранения данных, и на уровне исполнения запросов.
Благодарности
Авторы благодарны Ставросу Харизопулосу (Stavros Harizopoulos) за его комментарии к этой статье и Национальному научному фонду (NSF) за финансирование данного исследования по грантам 0704424 и 0325525.Детали соединений
При использовании метода скрытых соединений соединения выполняются в три этапа. Сначала каждый предикат применяется к соответствующей таблице измерений для извлечения списка ключей таблицы измерений, удовлетворяющих данному предикату. Эти ключи используются для построения хэш-таблицы, которую можно использовать для проверки того, удовлетворяет ли предикату некоторое значение ключа (эта хэш-таблица должна легко поместиться в основной памяти, поскольку таблицы измерений обычно являются небольшими, и хэш-таблица содержит только ключи). Пример выполнения этого первого этапа для приведенного выше запроса на некоторых примерных данных показан на рис. 2.
Рис. 2. Первый этап выполнения соединений, требуемых для обработки Запроса 3.1 из SSBM на некоторых примерных данных
На следующем этапе эти хэш-таблицы используются для извлечения позиций тех записей из таблицы фактов, которые удовлетворяют соответствующему предикату. Это делается путем поиска в хэш-таблице каждого значения столбца внешнего ключа таблицы фактов и создания списка всех позиций в этом столбце внешнего ключа, значения которых удовлетворяют предикату. Затем списки позиций от всех предикатов пересекаются, и генерируется список позиций P таблицы фактов, значения которых удовлетворяют всем предикатам. Пример выполнения этого второго этапа показан на рис. 3. Заметим, что список позиций может быть явным списком позиций или же битовой строкой, как показано в примере.
Рис. 3. Второй этап выполнения соединений, требуемых для обработки Запроса 3.1 из SSBM на некоторых примерных данных
На третьем этапе соединения используется список P позиций таблицы фактов, значения которых удовлетворяют всем предикатам. Для каждого столбца C, являющегося внешним ключом к некоторой таблице измерений, данные которой требуются для формирования результата запроса (например, ссылка на столбец этой таблицы измерений имеется в списке выборки, разделе GROUP BY или в вызове агрегатной функции), значения внешнего ключа из C выбираются с использованием P, и производится поиск в соответствующей таблице измерений.
Заметим, что если ключи таблицы измерений образуют отсортированный, непрерывный список идентификаторов, начинающийся с единицы (что является распространенным случаем), то значение внешнего ключа в действительности задает позицию нужного кортежа в таблице измерений. Это означает, что требуемые столбцы таблицы измерений могут быть извлечены напрямую с использованием этого списка позиций (и это просто быстрый поиск в массиве).
Эта прямая выборка из массива (наряду с тем фактом, что таблицы размерностей обычно являются небольшими, так что столбец, в котором осуществляется поиск, часто может поместиться в кэше L2) является причиной того, что методу скрытых соединений не присущи описанные выше недостатки подходов соединений с отложенной материализацией [5], где завершающая беспорядочная выборка по списку позиций является очень дорогостоящей. Кроме того, минимизируется число значений, которые требуется выбирать, поскольку число позиций в списке P зависит от селективности всего запроса, а не только той части, которая была выполнена к моменту выборки.
Пример выполнения этого третьего этапа показан на рис. 4. Заметим, что для таблицы DATE столбец ключа не является отсортированным непрерывным списком, начинающимся с единицы, так что для него требуется выполнять полное соединение (а не всего лишь позиционную выборку). Заметим также, что, поскольку это соединение вида внешний-ключ/первичный-ключ, и все предикаты уже применены, гарантируется, что в каждой таблице измерений для каждой позиции окончательного списка позиций таблицы фактов будет обнаружен один и только один результат. Это означает, что на этом третьем этапе при соединении с каждой таблицей измерений получается одно и то же число результатов, так что каждое соединение может выполняться по отдельности, и результаты могут объединяться (сшиваться) в более поздней точке плана выполнения запроса.
Рис. 4. Третий этап выполнения соединений, требуемых для обработки Запроса 3.1 из SSBM на некоторых примерных данных
Детальный анализ производительности строчного хранилища
В этом пункте авторы представляют детальный анализ производительности строчного хранилища, используя в качестве ориентира планы выполнения запроса 2.1 из SSBM, сгенерированные System X (выбран именно этот запрос, потому что он один из немногих, для которых разделение по orderdate не обеспечивает выигрыша, и поэтому он предоставляет более равные возможности для сравнения традиционного подхода с подходом вертикального разделения). Хотя планы для других запросов не анализировались настолько же тщательно, их общая структура является такой же. Вот формулировка этого запроса на языке SQL:SELECT sum(lo.revenue), d.year, p.brand1 FROM lineorder AS lo, dwdate AS d, part AS p, supplier AS s WHERE lo.orderdate = d.datekey AND lo.partkey = p.partkey AND lo.suppkey = s.suppkey AND p.category = ‘MFGR#12’ AND s.region = ‘AMERICA’ GROUP BY d.year, p.brand1 ORDER BY d.year, p.brand1
Селективность этого запроса равняется 8.0?10-3. Здесь подход с вертикальным разделением работает почти так же хорошо, как и традиционный подход (65 секунд по сравнению с 43 секундами), но подход с использованием только индексов показывает существенно худшие результаты (360 секунд). Причины этого обсуждаются ниже.
Итерация по блокам
Для обработки последовательностей кортежей в строчных хранилищах просматриваются все кортежи, и из них выбираются требуемые атрибуты через интерфейс представления кортежей [11]. Во многих случаях, например, в MySQL, это приводит к покортежной обработке запросов, где для каждой операции требуется 1-2 вызова функций для извлечения из кортежа требуемых данных (и если эта операция связана с вычислением простого выражения или условия, то стоимость ее выполнения мала по сравнению с расходами на вызов функции) [25].В недавних исследованиях показано, что некоторые накладные расходы обработки кортежей в строчных хранилищах можно сократить, если одновременно доступны блоки кортежей, которые можно обрабатывать путем вызова одной операции [24, 15]. Подобный подход реализован в IBM DB2 [20]. В отличие от выборочной реализации блочного подхода в строчных хранилищах, во всех колоночных хранилищах (насколько это известно авторам) операции над блоками значений одного и того же столбца выполняются на счет одного вызова функции. Кроме того, не требуется извлечение атрибутов, и, если данный столбец содержит значения фиксированного размера, то данные можно представлять в виде массива. Обработка данных, представленных в виде массива, не только минимизирует покортежные накладные расходы, но также дает возможность использовать средства распараллеливания современных процессоров, позволяя применять методы конвейеризации циклов [9].
Эксперименты
В этом разделе с использованием тестового набора SSBM сравнивается производительность реализаций, основанных на использовании строчного хранилища, с производительностью C-Store. Целью экспериментов является обеспечение ответов на следующие четыре вопроса:Отвечая на эти вопросы, авторы статьи предоставляют разработчикам СУБД, заинтересованным в применении подхода с хранением данных по столбцам, информацию относительно того, какие методы оптимизации наиболее плодотворно действуют на производительность. Кроме того, эти ответы помогут понять, какие изменения требуется сделать на уровнях менеджера хранения данных и исполнителя запросов строчных хранилищ, чтобы в них можно было успешно моделировать колоночное хранилище.
Все эксперименты поводились с использованием рабочей станции с двухядерным процессором Pentium, работающим на частоте 2.8 GHz, с тремя гигабайтами оперативной памяти. В качестве операционной системы использовалась ОС RedHat Enterprise Linux 5. Машина была оснащена дисковым массивом с четырьмя дисками, управляемым как одним логическим томом. Файлы «расслаивались» между дисками. Типичная пропускная способность ввода/вывода составляла 40-50 мегабайт в секунду на один диск, или 160-200 мегабайт в секунду для расслоенных файлов. Приводимые числовые результаты усреднены на основе нескольких прогонов и основываются на использовании «разогретого» буферного пула (на практике авторы обнаружили, что для обоих видов систем это приводит примерно к тридцатипроцентному повышению производительности; этот выигрыш не очень велик, поскольку объем данных, считываемых с диска при выполнении каждого запроса, превышает размер буферного пула).
Материализованные представления.
В третьем подходе, рассматриваемом авторами, используются материализованные представления. При применении этого подхода для каждого звена запросов рабочей нагрузки создается оптимальный набор материализованных представлений, в котором оптимальное представление для данного звена содержит только столбцы, требуемые в запросах этого звена. В этих представлениях не выполняется соединение столбцов разных таблиц. Цель этой стратегии состоит в том, чтобы дать возможность System X производить доступ только к тем данным на диске, которые действительно требуются, избегая накладных расходов явного хранения идентификаторов записей или позиций и сохраняя заголовки кортежей только по одному для каждого кортежа. Поэтому авторы рассчитывали, что этот подход будет работать лучше первых двух подходов, хотя для его применения требуется предварительное знание рабочей нагрузки, что позволяет использовать его только в ограниченном числе ситуаций.Моделирование колоночного хранилища в строчном хранилище
В этом подразделе описывается производительность различных конфигураций System X на тестовом наборе Star Schema Benchmark. System X конфигурировалась таким образом, чтобы таблица LINEORDER разделялась на столбце orderdate по годам (это значит, что для каждой группы кортежей с одинаковым значением года принятия заказа создавался отдельный физический раздел). Как было сказано в подразделе 6.1, это разделение существенно ускоряет выполнение запросов из SSBM, включающих предикат на столбце LINEORDER (в запросах 1.1, 1.2, 1.3, 3.4, 4.2 и 4.3 требуются данные за период в пределах одного года, а в менее селективных запросах 3.1, 3.2 и 3.3 запрашиваются данные за период с 1992-го по 1997-й гг., т.е. за половину всего временого промежутка, зафиксированного в базе данных). К сожалению, дела обстоят не так хорошо для представлений данных, ориентированных на хранение данных по столбцам. System X не разрешает горизонтально разделять по orderdate двухколоночные вертикальные разделы (поскольку они не содержат столбца orderdate, за исключением, конечно, вертикального раздела orderdate). Это означает, что для тех звеньев запросов, которые ограничивают столбец orderdate, подходы, ориентированные на хранение данных по столбцам, находятся в менее выигрышном положении, чем базовый вариант.Тем не менее, авторы решили использовать разделение для базового варианта, потому что хороший администратор баз данных непременно воспользовался бы этой стратегией для повышения производительности при выполнении этих запросов в строчном хранилище. При использовании базового варианта без разделения система демонстрировала производительность, меньшую в среднем в два раза (хотя это зависело от селективности предиката на столбце orderdate). Таким образом, авторы полагают, что разделение таблицы LINEORDER позволило бы повысить производительность в среднем в два раза, если бы было можно разделять таблицы на основе двух уровней косвенности (по первичному ключу, или идентификатору записи достается значение столбца orderdate, а через orderdate получается значение года).
К числу других уместных конфигурационных параметров System X относится следующее: размер дисковых страниц – 32 килобайта, максимальный размер оперативной памяти для выполнения сортировок, соединений и хранения промежуточных результатов – 1.5 гигабайт, размер буферного пула – 50 мегабайт. Авторы экспериментировали с другими размерами буферного пула и обнаружили, что изменение его размера не сильно влияет на время выполнения запросов (поскольку в этом тестовом наборе преобладает использование просмотров большой таблицы), если только не использовать совсем маленький буферный пул. Авторы включили режимы сжатия и упреждающего чтения при последовательном сканировании и обнаружили, что оба эти приема способствуют повышению производительности, опять же, из-за того, что при обработке запросов требуется большой объема ввода-вывода. В System X также поддерживается метод звездообразного соединения, и оптимизатор может использовать фильтры Блюма, если по его оценкам это может повысить производительность выполнения запроса.
Как говорилось в разд. 4, авторы при прогоне запросов SSBM проводили эксперименты с пятью конфигурациями System X:
Детальные результаты для каждого потока запросов показаны на рис. 6(a), а усредненные результаты для всех запросов – на рис. 6(b). Во всех случаях лучшую производительность демонстрирует подход с материализованными представлениями, поскольку в этом случае для обработки запроса требуется чтение минимального объема данных. Второе место по производительности занимает традиционный подход (или традиционный подход с использованием битовых индексов). В среднем традиционный подход работает почти в три раза быстрее наилучшего варианта эмуляции колоночного хранилища в строчном хранилище. Как уже говорилось выше, это особенно характерно для запросов, при выполнении которых используется разделение по orderdate. Для второго звена запросов (для выполнения которых разделение не обеспечивает преимуществ) подход с вертикальным разделением успешно конкурирует с традиционным подходом; подход с использованием только индексов работает плохо по причинам, объясняемым ниже. Прежде чем более детально обсудить эффективность выполнения отдельных запросов, авторы резюмируют две высокоуровневые проблемы, ограничивающие эффективность колоночного подхода: покортежные накладные расходы и неэффективная реконструкция кортежей.
Рис. 6(a). Показатели производительности по звеньям запросов для различных вариантов конфигурирования строчного хранилища. Здесь T – соответствует традиционному варианту, T(B) – традиционному варианту с ориентацией на битовые индексы, MV – варианту с материализованными представлениями, VP – варианту с вертикальным разделением и AI – варианту с использованием только индексов.
Рис. 6(b). Средняя производительность по всем запросам.
Обсуждение
Приведенные результаты показывают, что ни одна из попыток авторов эмулировать колоночное хранилище в строчном хранилище не привела к сколько-нибудь эффективным результатам. Подход вертикального разделения может обеспечить производительность, сравнимую с производительностью традиционного подхода (или немного более высокую) при выборке всего нескольких столбцов. Однако при выборке более чем четверти от общего числа столбцов непроизводительные затраты дискового пространства на хранение заголовков кортежей и избыточных копий идентификаторов кортежей приводят к производительности, худшей, чем у традиционного подхода. Для применения этого подхода также требуется выполнение дорогостоящих операций хэш-соединения для реконструкции кортежей таблицы фактов. Возможно, от System X можно было бы добиться хранения столбцов на диске в отсортированном порядке и использования для реконструирования кортежей соединения со слиянием (без сортировки), но соавтор-администратор баз данных не смог убедить систему вести себя таким образом.Планы с доступом только к индексам обладают низкими покортежными накладными расходами, но порождают другую проблему – система вынуждена соединять столбцы таблицы фактов с использованием дорогостоящих операций хэш-соединения до того, как будет произведена фильтрация таблицы фактов на основе столбцов измерений. Как представляется авторам, System X не может отложить выполнение этих соединений на более позднюю фазу плана (как это делается в подходе вертикального разделения), потому что не может удержать идентификаторы записей из таблицы фактов после ее соединения с другой таблицей. Эти гигантские хэш-соединения приводят к исключительно низкой производительности.
Что касается традиционных планов, очевидным победителем является подход материализованных представлений, поскольку он позволяет System X считывать с диска именно то подмножество данных из таблицы фактов, которое требуется для выполнения запроса, без потребности в соединении столбцов. Иногда помогают битовые индексы – особенно при низкой селективности запросов, – поскольку они позволяют системе пропускать некоторые страницы таблицы фактов при ее сканировании. В ряде других случаев они приводят к снижению производительности, поскольку слияние битовых последовательностей добавляет накладные расходы к плану выполнения запроса, и сканирование через битовый индекс может быть медленнее чисто последовательного сканирования.
Наконец, авторы замечают, что реализация этих планов в System X была довольно тягостным делом. Для использования подхода вертикального разделения пришлось переписывать все запросы, авторы были вынуждены интенсивно использовать подсказки оптимизатору и другие хитрости, чтобы убедить систему делать то, что они хотели.
В следующем подразделе описывается, как в разработанной с нуля системе с хранением данных по столбцам удалось избежать этих ограничений и анализируется вклад разных механизмов в общую производительность системы C-Store при выполнении тестового набора SSBM.
Оценка повторяемости результатов
Все рисунки, содержащие числовые показатели, полученные на основе экспериментов с прототипом C-Store (рис. 7a, рис. 7b и рис. 8), проверены комитетом по проверке повторяемости результатов SIGMOD. Авторы благодарны Иоанне Манолеску и комитету по проверке повторяемости результатов за их отзывы.Отложенная материализация
В колоночном хранилище информация о любой логической сущности (например, о человеке) сохраняется на диске в нескольких местах (например, имя, адрес электронной почты, номер телефона и т.д. хранятся в отдельных столбцах), в то время как в строчном хранилище такая информация обычно сосредотачивается в одной строке таблицы. Однако в большинстве запросов требуется значения нескольких атрибутов некоторой сущности. Кроме того, в большинстве стандартных интерфейсов доступа к базам данных (например, в ODBC и JDBC) ответ на запрос выдается сущность за сущностью (а не столбец за столбцом). Таким образом, в некоторой точке большинства планов запросов данные из разных столбцов должны собираться в «строки» информации о соответствующей сущности. Поэтому эта подобная соединению материализация кортежей (называемая также «конструированием кортежей») является исключительно распространенной операцией в колоночном хранилище.В упрощенных колоночных хранилищах [13, 14] данные хранятся на диске (или в основной памяти) столбец за столбцом; считываются только столбцы, существенные для данного запроса; из этих атрибутов конструируются кортежи; и над полученными строками выполняются обычные операции обработки данных строчного хранилища (например, выборка, агрегация и соединение). Хотя и при использовании такого подхода колоночное хранилище, вероятно, превзойдет по производительности строчное хранилище на рабочих нагрузках хранилищ данных, раннее конструирование кортежей в плане выполнения запроса («ранняя материализация») не позволяет использовать весь потенциал систем баз данных с хранением данных по столбцам для достижения высокой производительности.
В более современных колоночных хранилищах, таких как MonetDB/X100, C-Store и, в меньшей степени, Sybase IQ, данные сохраняются в формате столбцов гораздо дольше, и операции выполняются прямо над этими столбцами. Для этого часто требуется построение промежуточных списков «позиций», чтобы можно было находить соответствие между результатами операций, выполненных над разными столбцами.
Например, рассмотрим запрос, в котором к двум столбцам применяются предикаты, и из всех кортежей, удовлетворяющих этому условию, выбирается некоторый третий атрибут. В колоночных хранилищах с отложенной материализацией предикаты применяются к столбцам по отдельности, и формируется список позиций (порядковых смещений в столбце) значений, удовлетворивших данному условию. В зависимости от селективности предиката этот список позиций может представляться в виде простого массива, битовой строки (в которой наличие единицы в i-том бите означает, что i-тое значение удовлетворяет предикату) или множества диапазонов позиций. Затем над этими представлениями позиций выполняется операция пересечения (при использовании битовых строк можно использовать поразрядную операцию AND) для создания единого списка позиций. И, наконец, этот список применяется к третьему столбцу для выборки значений из нужных позиций.
У поздней материализации есть четыре основных преимущества. Во-первых, для выполнения операций выборки и агрегации конструирование некоторых кортежей может вообще не понадобиться (если компонент выполнения запросов откладывает конструирование кортежа достаточно надолго, то он может вообще избежать его конструирования). Во-вторых, если данные сжаты с использованием некоторого метода, ориентированного на хранение данных по столбцам, то их придется распаковывать до комбинирования этих значений со значениями других столбцов. Это устраняет описанные выше преимущества выполнения операций прямо над сжатыми данными. В третьих, при выполнении операций прямо над данными столбцов повышается эффективность использования кэша, поскольку блоки кэша не засоряются данными атрибутов, не существенными для данной операции (как показано в PAX [6]). В четвертых, на эффективность обработки атрибутов со значениями постоянного размера сильное воздействие оказывает оптимизация итерации по блокам, описываемая в следующем подразделе. В строчном хранилище, если у какого-нибудь атрибута допускаются значения разного размера, то и все кортежи имеют переменный размер.В колоночном хранилище с отложенной материализацией столбцы со значениями постоянного размера могут обрабатываться отдельно.
Перезапись в предикат between
Алгоритм скрытых соединений в том виде, как он описан выше, во многом заимствует идеи полусоединения с учетом хранения данных по столбцам и хэш-соединения с отложенной материализацией. Хотя в методе скрытых соединений хэш-часть соединения выражается в виде предиката на столбце таблицы фактов, способы вычисления этого предиката и выполнения хэш-соединения (с отложенной материализацией) практически почти не различаются. Преимущество от представления соединения в виде предиката становится существенным в очень распространенном случае (для соединений в базе данных со звездообразной схемой), когда множество ключей в таблице измерений, остающееся после применения предиката, является непрерывным. В этом случае можно использовать метод, называемый авторами перезаписью в предикат between, когда предикат на таблице фактов, вычисляемый на основе хэш-поиска, переписывается в предикат between, ограничивающий внешний ключ диапазоном значений. Например, если непрерывным множеством значений ключа после применения предиката является отрезок [1000, 2000], то вместо вставки каждого из этих ключей в хэш-таблицу и проверки на основе этой хэш-таблицы каждого значения внешнего ключа таблицы фактов можно просто проверять вхождение очередного значения внешнего ключа в этот отрезок. Если эта проверка удается, соответствующий кортеж входит в результат соединения, иначе – нет. Очевидно, что предикаты between обрабатываются быстрее, поскольку для этого не требуется какой-либо поиск.Возможность применения этой оптимизации зависит от того, непрерывны ли множества допустимых ключей таблиц измерений. Во многих случаях это свойство не выполняется. Например, при применении к неотсортированному полю предиката, задающего условие вхождения в диапазон значений, получается не непрерывное множество позиций. И даже для предикатов на отсортированных полях процесс сортировки таблицы измерений по такому атрибуту, вероятно, переупорядочит первичные ключи, так что они перестанут образовывать упорядоченное, непрерывное множество идентификаторов.
Однако последнюю проблему легко преодолеть за счет использования кодирования по словарю (dictionary encoding) с целью переназначения ключей (а не сжатия). Поскольку ключи уникальны, кодирование столбца по словарю приводит к тому, что словарные ключи образуют упорядоченный, непрерывный список, начинающийся с нуля. Если столбец внешнего ключа таблицы фактов кодируется с использованием той же словарной таблицы, то можно производить перепись предиката с поиском по хэш-таблице в предикат between.
Кроме того, утверждение, что эта оптимизация работает только для предикатов на отсортированном столбце таблицы измерений, является не совсем верным. На самом деле, таблицы измерений в хранилище данных часто содержат наборы атрибутов с повышающимися уровнями детализации. Например, в таблице DATE базы данных SSBM имеются столбцы year, yearmonth и столбец полной даты date. Если таблица отсортирована по столбцу year, вторично отсортирована по столбцу yearmonth и на третьем уровне отсортирована по полной дате, то применение предиката сравнения по равенству к любому из этих трех столбцов приведет к формированию непрерывного набора результатов (или предиката проверки вхождения в диапазон значений на отсортированном столбце). Другой пример: в таблице SUPPLIER имеются столбцы region, nation, и city (в регион входит много стран, а в стране имеется много городов). Снова при сортировке слева направо применение предиката к любому из этих трех столбцов приведет к формированию непрерывного диапазона. В запросах к хранилищу данных часто используются такие столбцы, поскольку распространенной практикой OLAP является детализация данных при последовательном применении запросов (получить величину прибыли по регионам, получить величину прибыли по странам, получить величину прибыли по городам). Таким образом, перезапись в предикат between может использоваться чаще, чем может показаться сначала, и часто приводит к существенному выигрышу в производительности (что демонстрируется в следующем разделе).
Заметим, что для применения этого вида оптимизации не требуется изменять оптимизатор запросов. При вычислении предикатов над таблицами измерений можно проверить, является ли результирующее множество непрерывным. Если это так, то предикат над таблицей фактов переписывается во время выполнения.
Планы с доступом только к индексам.
У подхода вертикального разделения имеются две проблемы. Во-первых, требуется хранение в каждой таблице столбца позиции, что приводит к излишним затратам дисковой памяти и дополнительным обменам с диском. Во-вторых, в большинстве строчных хранилищ вместе с каждым кортежем хранится относительно крупный заголовок, что также вызывает излишние расходы дисковой памяти (в колоночных хранилищах обычно – а, возможно, даже и по определению – заголовки хранятся в отдельных столбцах во избежание этих накладных расходов).Для преодоления этих проблем авторы пытались использовать второй подход, при котором базовые отношения хранятся в обычном строчном виде, но на каждом столбце каждой таблицы определяется дополнительный некластеризованный индекс в виде B-дерева. Планы выполнения запросов с доступом только к индексам (index-only plan), для которых требуется специальная поддержка со стороны СУБД, имеющаяся в System X, выполняются путем построения списков пар (record-id, value), удовлетворяющих предикатам, и слиянием этих списков в основной памяти, если для одной таблицы имеется несколько предикатов. Если для требуемых полей в запросе отсутствуют предикаты, то производятся полные списки пар (record-id, value) для всех значений соответствующих столбцов.
При выполнении таких планов никогда не производится доступ к реальным кортежам на диске. Хотя индексы явно хранят идентификаторы хранимых записей, каждое значение соответствующего столбца сохраняется только один раз, и обычно доступ к значениям столбцов через индексы сопровождается меньшими накладными расходами, поскольку в индексе не хранятся заголовки кортежей.
Одной из проблем этого подхода является то, что если в запросе отсутствует предикат на некотором столбце, то для выборки требуемых значений требуется последовательное сканирование индекса, которое может выполняться медленнее сканирования неупорядоченного файла (как было бы при применении подхода вертикального разделения).
Оптимизацией подхода является создание индексов с составными ключами, в которых вторичные ключи берутся из столбцов без предикатов. Например, рассмотрим запрос SELECT AVG(salary) FROM emp WHERE age>40. Если имеется составной индекс с ключом (age, salary), то ответ на этот запрос может быть получен прямо через этот индекс. Если же имеются отдельные индексы с ключами (age) и (salary), то план с доступом только к индексам будет вынужден найти все идентификаторы записей, удовлетворяющих условию age>40, а потом слить полученный список с полным списком пар (record-id, salary), построенным по индексу с ключом (salary), что будет выполняться гораздо медленнее.
В своей реализации авторы используют эту оптимизацию путем хранения первичного ключа каждой таблицы измерений в качестве вторичного ключа индексов на столбцах этой таблицы. За счет этого обеспечивается эффективный доступ к значениям первичных ключей таблиц измерений, требуемым для соединения с таблицей фактов.
В этих планах доступ ко всем столбцам производится через некластеризованные B-деревья, и столбцы одной и той же таблицы соединяются по идентификаторам записей (переход по указателям к хранимым отношениям никогда не производится). В плане для запроса 2.1 выполняется полное индексное сканирование столбцов suppkey, revenue, partkey и orderdate таблицы фактов, и затем результаты соединяются методом хэш-соединений. В этом случае индексное сканирование обеспечивает относительно быстрый просмотр всего индексного файла, и при этом не требуется подвод дисковых головок при переходе от одной листовой страницы к другой. Однако хэш-соединения выполняются довольно медленно, поскольку приходится комбинировать пары из 60 миллионов экземпляров столбцов, каждый из которых занимает сотни миллионов мегабайт дискового пространства. Заметим, что для этого случая хэш-соединение, по-видимому, является наилучшим методом, поскольку результаты индексного сканирования не упорядочены по идентификаторам записей, и выполнение сортировки списков идентификаторов записей или применение индексных вложенных циклов, вероятно, были бы гораздо медленнее. Как обсуждается ниже, авторам не удалось найти способ принудить System X отложить выполнение этих соединений на более позднюю фазу плана, что позволило бы приблизить эффективность этого подхода к эффективности подхода с вертикальным разделением.
После соединения столбцов таблицы фактов в плане используется индексное сканирование в диапазоне значений ключа для извлечения отфильтрованного столбца part.category, и результат хэш-соединяется со столбцами part.brand1 и part.part-key (доступ к которым производится путем полного индексного сканирования). Затем полученный результат хэш-соединяется с уже соединенными столбцами таблицы фактов. После этого выполняется хэш-соединение столбца supplier.region (отфильтрованного путем индексного сканирования в диапазоне значений ключа) со столбцом supplier.suppkey (доступ к которому производится путем полного индексного сканирования), и результат этого соединения хэш-соединяется с таблицей фактов. Наконец, используется полное индексное сканирование столбцов dwdate.datekey и dwdate.year, они хэш-соединяются, и результат этого соединения хэш-соединяется с таблицей фактов.
Побудительные мотивы выбора экспериментальной установки
На рис. 5 приведено сравнение производительности C-Store и System X на тестовом наборе Star Schema Benchmark. Авторы призывают читателей не обращать слишком пристального внимания на абсолютные показатели производительности этих двух систем. Как обсуждается в этом разделе, реализации этих систем существенно различаются (даже если не принимать во внимание основное различие в строчной или колоночной ориентации), и эти различия влияют на числовые показатели производительности.
Рис. 5. Базовая производительность C-Store (CS) and System X (RS) в сравнении со случаями применения в каждой системе материализованных представлений
На этом рисунке «RS» соответствует числовым показателям базового варианта System X, «CS» – показателям базового варианта C-Store. «RS (MV)» соответствует показателям System X при использовании оптимального набора материализованных представлений, которые содержат минимальные проекции таблиц, требуемых для выполнения каждого запроса (см. разд. 4). Как видно, C-Store превосходит по производительности System X в шесть раз в базовом варианте и в три раза, когда в System X используются материализованные представления. Это согласуется с результатами предыдущих исследований, которые показывают, что колоночные хранилища существенно превосходят по производительности строчные хранилища на рабочих нагрузках хранилищ данных [2, 9, 22].
Однако четвертый набор показателей, представленный на рис. 5, показывает, что к числовым показателям, которые используются для сравнения производительности систем, нужно относиться осторожно. Для получения четвертого набора показателей авторы использовали внутри C-Store те же самые (строчные!) материализованные представления. Можно было бы ожидать, что менеджер хранения данных C-Store не сможет сохранить строчные данные, потому что, в конце концов, он ориентирован на хранение данных в столбцах. Однако это можно легко сделать путем использования таблиц с единственным столбцом типа символьных строк.
Значениями этого столбца являются полные кортежи. Можно было бы также ожидать, что компонент выполнения запросов C-Store не сможет работать со строками, поскольку он ориентирован на использование столбцов в качестве вводных данных. Однако, как пояснялось в подразделе 5.2, в C-Store строки являются законным внутренним представлением; в некоторой точке плана выполнения запроса C-Store конструирует строки из столбцов-компонентов (поскольку пользовательский интерфейс с РСУБД является покортежным). После выполнения этого конструирования кортежей продолжается выполнение оставшейся части плана запроса с использованием стандартных операций строчного хранилища [5]. Таким образом, оба варианта систем CS (Row-MV) и RS (MV) выполняли одни и те же запросы над одними и теми же данными, хранимыми одинаковым образом. Следовательно, можно было бы ожидать, что показатели производительности также окажутся одинаковыми.
Вопреки этим ожиданиям производительность System X оказалась существенно выше (более чем в два раза) производительности C-Store. Если немного задуматься, то это перестает быть удивительным – в компании, производящей System X, имеются специальные группы, отвечающие за поиск и устранение в коде узких мест производительности, в то время как в C-Store имеется несколько известных узких мест производительности, которые еще не устранены [3]. Более того, в CStore, как в простом прототипе, не реализованы развитые средства повышения производительности, содержащиеся в System X. К числу таких средств относятся разделение (partitioning) и многопотоковость (multi-threading). System X может оптимально разделить каждое материализованное представление в расчете на звено запросов, для которого оно предназначается. При работе системы на одной машине разделение повышает производительность за счет уменьшения объема данных, которые нужно просканировать для выполнения запроса. Например, материализованное представление, используемое для первого звена запросов, разделяется по годам даты принятия заказа, что полезно, поскольку в каждом запросе этого звена имеется предикат на столбце orderdate.
Чтобы определить, какие преимущества в производительности получает System X от разделения, авторы пропустили тот же тестовый набор над теми же материализованными представлениями без их разделения. В этом случае среднее время выполнения запроса составило 20.25 секунд. Тем самым, разделение обеспечило System X двухкратный выигрыш в производительности (хотя это зависит от конкретного запроса; дальнейшее обсуждением см. в подразделе 6.2). Кроме того, в C-Store отсутствует поддержка многопотокового режима, и, следовательно, невозможно использование второго ядра процессора.
Таким образом, между двумя системами, с которыми экспериментировали авторы, имеется много различий. Некоторые из них являются фундаментальными различиями между колоночными и строчными хранилищами, другие связаны с особенностями реализации. Поскольку трудно придти к полезным заключениями при сравнении показателей производительности настолько разных систем, авторы выбрали другую тактику, анализируя производительность выполнения тестового набора с двух точек зрения. В подразделе 6.2 описывается попытка моделирования колоночного хранилища внутри строчного хранилища. В этом подразделе обсуждаются эксперименты с использованием только System X, и поэтому удается избежать проблем кросс-системного сравнения производительности. В подразделе 6.3 описываются эксперименты по удалению из C-Store оптимизаций, воздействующих на производительность. Этот процесс «разгрузки» C-Store продолжался до тех пор, пока она не начала показывать производительность строчного хранилища. И здесь эксперименты проводились только над одной системой.
Выполнение экспериментов в такой манере позволяет авторам придти к некоторым выводам о преимуществах колоночных хранилищ в отношении производительности, не полагаясь на сравнение систем. Например, интересно отметить, что на рис. 5 производительность вариантов CS и CS Row MV различается более чем в шесть раз, несмотря на то, что используется одна и та же система, и в обоих вариантах с диска считывается минимальный набор столбцов, требуемых для обеспечения ответа на запрос.Из этого ясно видно, что преимущество в производительности колоночное хранилище получает далеко не только потому, что с диска не считываются лишние данные. Причины этой разницы в производительности вариантов CS и CS Row MV разъясняются в подразделе 6.3.
Покортежные накладные расходы и стоимость соединений
В современных колоночных хранилищах явно не сохраняются идентификаторы записей (или первичные ключи), требуемые для соединения столбцов одной и той же таблицы. Вместо этого для реконструкции кортежей используются неявные позиции значений в столбцах (i-тое значение из каждого столбца принадлежит i-тому кортежу таблицы). Кроме того, заголовки кортежей хранятся в собственных отдельных столбцах, так что к ним возможен доступ отдельно от реальных значений столбцов. Следовательно, столбец в колоночном хранилище содержит только соответствующие данные, а не заголовок кортежа, идентификатор записи и данные, как это происходит в вертикально разделенном строчном хранилище.В колоночном хранилище файлы данных хранятся в порядке позиций (i-тое значение всегда располагается за (i-1)-м значением), в то время как порядок в файлах данных многих строчных хранилищ (даже кластеризованных по некотором атрибуту) гарантируется только при доступе через некоторый индекс. Очевидно, что это приводит к предпочтительности использования для реконструкции кортежей в колоночном хранилище соединения со слиянием (без сортировки). В строчном хранилище слияние на основе индексов является медленным способом реконструкции кортежей, поскольку итерирование отсортированного файла должно производиться через индекс, что может приводить к дополнительному передвижению дисковых головок при переходе от одного листа индекса к другому.
Следует заметить, что ни одно из упомянутых выше различий не является фундаментальным. Нет причин, по которым в строчном хранилище нельзя было бы отдельно хранить заголовки кортежей, использовать виртуальные идентификаторы записей для соединения данных и поддерживать файлы данных в позиционном порядке. Приведенное наблюдение всего лишь выделяет некоторые важные реализационные соображения, которые были бы уместны при желании построить строчное хранилище, успешно моделирующее колоночное хранилище.
Покортежные накладные расходы.
Как отмечалось в [16], одной из проблем подхода с полным вертикальным разделением в строчном хранилище является то, что могут стать довольно большими покортежные накладные расходы. Эту проблему отягчает тот факт, что для обеспечения реконструирования кортежей вместе с каждым столбцом требуется хранить идентификаторы записей или первичные ключи. Авторы сравнивали размеры колоночных таблиц, возникающих при применении подхода с вертикальным разделением, с размерами традиционных таблиц строчного хранилища и обнаружили, что для хранения одной колоночной таблицы для столбцов таблицы LINEORDER из базы данных SSBM с коэффициентом масштабирования 10 (около 60 миллионов кортежей) требуется от 0.7 до 1.1 гигабайт данных после сжатия – это означает, что для каждой строки требуется 8 байт в дополнение к 4 байтам для каждого идентификатора записи и каждого значения самого столбца (в зависимости от типа данных столбца и эффективности сжатия (16 байт ? 6 ? 107 кортежей = 960 мегабайт). По сравнению с этим, таблица LINEORDER целиком, со всеми семнадцатью столбцами при применении традиционного подхода занимает без сжатия около шести гигабайт, а в сжатом виде – 4 гигабайта. Тем самым, сканирование всего лишь четырех столбцов вертикально разделенной таблицы займет столько же времени, что сканирование всей таблицы фактов при использовании традиционного подхода. Для сравнения, в C-Store для хранения одного столбца целого типа требуется всего 240 мегабайт (4 байта ? 6 ? 107 кортежей = 240 мегабайт), а вся таблица в сжатом виде занимает 2.3 гигабайта.Предыдущие работы
В этом разделе авторы приводят краткий обзор предыдущих родственных работ, в которых сравнивалась производительность колоночных и строчных хранилищ. Хотя идея вертикального разделения таблиц базы данных для повышения производительности была популярна в течение долгого времени [1, 7, 16], разработка современных систем баз данных, ориентированных на хранение данных по столбцам, и методов векторизованного выполнения запросов началась с проектов MonetDB [10] и MonetDB/X100 [9]. Эти проекты показали, что системы, ориентированные на хранение по столбцам, благодаря более эффективному использованию процессора и кэша (в дополнение к сокращенному объему ввода-вывода), могут на тестовых наборах типа TPC-H значительно превосходить в производительности коммерческие и доступные в исходных кодах СУБД. Однако в исследованиях, связанных с MonetDB, не предпринимались попытки оценить, какую производительность могли бы показать строчные хранилища при использовании методов, ориентированных на работу со столбцами, и, насколько это известно авторам данной статьи, оптимизации, применяемые в MonetDB, никогда не оценивались в том же контексте, как оптимизация C-Store для выполнения операций напрямую над сжатыми данными.В другой недавней системе с хранением данных по столбцам применяется подход «треснувшего заркала» (fractured mirror) [21]. Здесь используется гибридная схема с поддержкой и строчного, и колоночного хранилищ. В строчном хранилище, главным образом, обрабатываются обновления базы данных, а над колоночным хранилищем выполняются операции чтения. Фоновый процесс переносит измененные данные из строчного хранилища в колоночное. В этом проекте также исследовалось несколько представлений данных для поддержки стратегии полного вертикального разделения в строчном хранилище (Shore). Авторы пришли к выводу, что существенной проблемой являются накладные расходы на поддержку кортежей, и что для сокращения времени реконструкции кортежей разумно производить упреждающее чтение с диска крупных блоков колоночных данных.
C-Store – это более молодая СУБД, поддерживающая хранение данных в столбцах. В ней поддерживаются многие возможности, присутствующие в MonetDB/X100, а также используются оптимизации для выполнения операций прямо над сжатыми данными [4]. Как и в случае двух ранее упоминавшихся проектов, проект C-Store показывает, что колоночное хранилище может существенно превзойти по производительности строчное хранилище на рабочих нагрузках хранилищ данных, но и в этом проекте раньше не исследовались возможные варианты организации физических схем баз данных с хранением по строкам. В данной статье авторы анализируют производительность C-Store, отмечая, как различные оптимизации, предложенные в литературе (например, [4, 5]), способствуют общей производительности системы по сравнению со строчным хранилищем на полном тестовом наборе хранилищ данных. Это также не делалось в предыдущих работах, посвященных C-Store.
В [14] Харизопулос и др. сравнивают производительность строчного и колоночного хранилищ, построенных с нуля, изучая простые планы, в соответствии с которыми данные последовательно считываются с диска, и немедленно реконструируются кортежи («ранняя материализация»). Эта работа демонстрирует, что в тщательно управляемой среде с использованием простых планов колоночные хранилища превосходят по производительности строчные хранилища в пропорции, зависящей от доли столбцов таблицы, считываемых с диска. Но в этой работе не обсуждались ни оптимизации, позволяющие повысить производительность строчных хранилищ, ни развитые методы повышения производительности колоночных хранилищ.
В [13] Хальверсон и др. описывают реализацию колоночного хранилища в Shore и сравнивают исходную (основанную на хранении данных по строкам) версию Shore с вариантом системы, в котором использовалось вертикальное разделение таблиц. В этой работе предлагается оптимизация, называемая «супертаблицами» («super tuples»), которая позволяет избежать дублирования информации о заголовках таблиц и приводит к группировке кортежей в блоки.В результате сокращаются накладные расходы на поддержку полностью разделенной схемы, и на использованных авторами тестовых наборах система вертикально разделенных баз данных успешно конкурирует по производительности с колоночным хранилищем. Авторы приходят к выводу, что оптимизации, подобные введению «супертаблиц», потребуются в строчных хранилищах при их использовании для эмуляции колоночных хранилищ. Однако в этой статье не исследуются преимущества многих последних оптимизаций колоночных хранилищ, включая различные методы сжатия и отложенную материализацию.
Определение таблиц базы данных SSBM
LINEORDER Table Layout (SF*6,000,000 are populated) ORDERKEY numeric (int up to SF 300) first 8 of each 32 keys used LINENUMBER numeric 1-7 CUSTKEY numeric identifier foreign key reference to C_CUSTKEY PARTKEY identifier foreign key reference to P_PARTKEY SUPPKEY numeric identifier foreign key reference to S_SUPPKEY ORDERDATE identifier foreign key reference to D_DATEKEY ORDERPRIORITY fixed text, size 15 (5 Priorities: 1-URGENT, etc.) SHIPPRIORITY fixed text, size 1 QUANTITY numeric 1-50 (for PART) EXTENDEDPRICE numeric, MAX about 55,450 (for PART) ORDTOTALPRICE numeric, MAX about 388,000 (for ORDER) DISCOUNT numeric 0-10 (for PART) - (Represents PERCENT) REVENUE numeric (for PART: (extendedprice*(100-discount))/100) SUPPLYCOST numeric (for PART, cost from supplier, max = ?) TAX numeric 0-8 (for PART) COMMITDATE Foreign Key reference to D_DATEKEY SHIPMODE fixed text, size 10 (Modes: REG AIR, AIR, etc.) Compound Primary Key: ORDERKEY, LINENUMBERPART Table Layout (200,000*[l+log2SF] populated) PARTKEY identifier NAME variable text, size 22 (Not unique per PART but never was) MFGR fixed text, size 6 (MFGR#l-5, CARD = 5) CATEGORY fixed text, size 7 (‘MFGR#’l-5l-5: CARD = 25) BRAND1 fixed text, size 9 (CATEGORY1-40: CARD = 1000) COLOR variable text, size 11 (CARD = 94) TYPE variable text, size 25 (CARD = 150) SIZE numeric 1-50 (CARD = 50) CONTAINER fixed text(10) (CARD = 40)
Primary Key: PARTKEY
SUPPLIER Table Layout (SF*10,000 are populated) SUPPKEY identifier NAME fixed text, size 25: ‘Supplier’SUPPKEY ADDRESS variable text, size 25 (city below) CITY fixed text, size 10 (10/nation: nation_prefix(0-9)) NATION fixed text(15) (25 values, longest UNITED KINGDOM) REGION fixed text, size 12 (5 values: longest MIDDLE EAST) PHONE fixed text, size 15 (many values, format: 43-617-354-1222) Primary Key: SUPPKEY
CUSTOMER Table Layout (SF*30,000 are populated) CUSTKEY numeric identifier NAME variable text, size 25 ‘Customer’CUSTKEY ADDRESS variable text, size 25 (city below) CITY fixed text, size 10 (10/nation: NATION_PREFIX(0-9) NATION fixed text(15) (25 values, longest UNITED KINGDOM) REGION fixed text, size 12 (5 values: longest MIDDLE EAST) PHONE fixed text, size 15 (many values, format: 43-617-354-1222) MKTSEGMENT fixed text, size 10 (longest is AUTOMOBILE) Primary Key: CUSTKEY
DATE Table Layout (7 years of days: 7366 days) DATEKEY identifier, unique id - e.g. 19980327 (what we use) DATE fixed text, size 18, longest: December 22, 1998 DAYOFWEEK fixed text, size 8, Sunday, Monday Saturday) MONTH fixed text, size 9: January, …, December YEAR unique value 1992-1998 YEARMONTHNUM numeric (YYYYMM) - e.g. 199803 YEARMONTH fixed text, size 7: Marl998 for example DAYNUMINWEEK numeric 1-7 DAYNUMINMONTH numeric 1-31 DAYNUMINYEAR numeric 1-366 MONTHNUMINYEAR numeric 1-12 WEEKNUMINYEAR numeric 1-53 SELLINGSEASON text, size 12 (Christmas, Summer,...) LASTDAYINWEEKFL 1 bit LASTDAYINMONTHFL 1 bit HOLIDAYFL 1 bit WEEKDAYFL 1 bit Primary Key: DATEKEY
Производительность C-Store
Беглый взгляд на среднее время выполнения запросов SSBM (около 4 секунд) в C-Store сразу позволяет понять, что эта система работает быстрее не только колоночных хранилищ, моделируемых в строчном хранилище (от 80 до 220 секунд), то также и наилучших для строчного хранилища сценариев, когда запросы известны заранее, и в строчном хранилище созданы материализованные представления, подогнанные под планы выполнения запросов (10.2 секунд). Эту разницу в производительности можно частично объяснить безо всяких экспериментов – в колоночных хранилищах отсутствуют покортежные накладные расходы, и не требуются соединения столбцов (это более подробно объясняется в п. 6.3.1). Однако это наблюдение не объясняет причину того, что колоночное хранилище оказывается быстрее варианта с материализованными представлениями (случая CS Row-MV из подраздела 6.1), в котором имеется аналогичный объем ввода-вывода, и в обеих системах не требуется соединение столбцов одной и той же таблицы. Чтобы понять, откуда взялась эта разница в производительности, авторы выполнили ряд дополнительных экспериментов с использованием колоночного хранилища, из которого последовательно удалялись специфические для этой организации оптимизации до тех пор, пока колоночное хранилище не начало моделировать строчное хранилище. Таким образом, удалось исследовать влияние этих разнообразных оптимизаций на эффективность обработки запросов. Эти результаты представлены в п. 6.3.2.Схема.
База данных SSBM состоит из одной таблицы фактов LINEORDER, в которой объединяются таблицы LINEITEM and ORDERS TPC-H. В таблице имеется 17 столбцов, содержащих информацию об отдельных заказах. Cоставной первичный ключ состоит из атрибутов ORDERKEY и LINENUMBER. Другие атрибуты таблицы LINEORDER являются внешними ключами к таблицам CUSTOMER, PART, SUPPLIER и DATE (для даты принятия заказа и даты завершения его обработки), а также таблица включает атрибуты приоритета заказа, его размера, стоимости и размера скидки. Таблицы измерений содержат информацию о соответствующих сущностях. На рис. 1 (основанном на рис. 2 из [19]) показана схема таблиц.
Рис. 1. Схема базы данных SSBM
Как и в TPC-H, в SSBM имеется базовый «масштабный коэффициент», который можно использовать для масштабирования размера базы данных. Размеры всех таблиц определяются относительно этого масштабного коэффициента. В работе авторов использовался масштабный коэффициент 10 (означающий, например, что в таблице LINEORDER содержалось 60000000 кортежей).
Скрытое соединение
Запросы к хранилищам данным, в частности, к хранилищам данных со звездообразной схемой часто имеют следующую структуру: ограничить множество кортежей в таблице фактов, используя предикаты ограничения над одной или несколькими таблицах измерений; затем выполнить некоторое агрегирование ограниченной таблицы фактов, часто с группировкой по атрибутам другой таблицы измерений. Таким образом, требуется выполнять соединения таблицы фактов и таблиц измерений для каждого предиката и каждой агрегатной группировки. Хорошим примером является Запрос 3.1 из Star Schema Benchmark.SELECT c.nation, s.nation, d.year, sum(lo.revenue) as revenue FROM customer AS c, lineorder AS lo, supplier AS s, dwdate AS d WHERE lo.custkey = c.custkey AND lo.suppkey = s.suppkey AND lo.orderdate = d.datekey AND c.region = 'ASIA' AND s.region = 'ASIA' AND d.year >= 1992 and d.year <= 1997 GROUP BY c.nation, s.nation, d.year ORDER BY d.year asc, revenue desc;
Этот запрос находит величины общего дохода от заказчиков, проживающих в Азии и покупавших некоторый продукт, который поставлялся азиатским поставщиком, в период между 1992-м и 1997-м гг.. Эти величины группируются по стране заказчика, стране поставщика и году выполнения данной транзакции.
Традиционный план выполнения таких типов запросов состоит в организации конвейера соединений в порядке уменьшения селективности предикатов. Например, если c.region = ‘ASIA’ является наиболее селективным предикатом, то первым будет выполняться соединение таблиц LINEORDER и CUSTOMER по столбцу custkey, ограничивая таблицу LINEORDER таким образом, что в ней останутся только заказы от азиатских заказчиков. После выполнения этого соединения к соединенной таблице customer-order добавляется столбец nation. Эти результаты отправляются по конвейеру в операцию соединения с таблицей SUPPLIER, где применяется предикат s.region = ‘ASIA’ и выбирается s.nation. За этим следует соединение с таблицей DATE, к которой применяется предикат, ограничивающий временной период.
Результаты этих соединений группируются, вычисляется агрегатная функция, и полученные кортежи сортируются в соответствии со спецификацией раздела ORDER BY.
В качестве альтернативы традиционному плану можно использовать метод отложенной материализации соединений [5]. В этом случае к столбцу c.region применяется предикат c.region = ‘ASIA’, и из ограниченной таблицы CUSTOMER извлекаются значения столбца custkey. Затем эти ключи соединяются со столбцом custkey таблицы фактов. Результатом этого соединения являются два набора позиций – один для таблицы фактов, другой для таблицы измерений. Эти наборы позиций показывают, какие пары кортежей соответствующих таблиц прошли через предикат соединения. Вообще говоря, не более чем один из этих наборов является упорядоченным списком (набор позиций внешней таблицы соединения, обычно таблицы фактов). Затем по неотсортированному набору позиций извлекаются значения из столбца c.nation, а по отсортированному списку позиций – значения других столбцов таблицы фактов (suppkey, orderdate и revenue). Аналогичные соединения выполняются с таблицами SUPPLIER и DATE.
У каждого из этих планов имеются свои недостатки. В первом (традиционном) случае конструирование кортежей до выполнения соединений сводит на нет все преимущества отложенной материализации, описанные в подразделе 5.2. Во втором случае требуется извлекать значения из таблицы размерностей не в порядке позиций, что вызывает значительные накладные расходы [5].
В качестве альтернативы этих планов авторы предлагают метод, названный ими методом скрытых соединений, который можно использовать в системах баз данных с хранением данных по столбцам для соединений внешний-ключ/первичный-ключ таблиц в базе данных со звездообразной схемой. Это соединение с отложенной материализацией, но в нем минимизируется число значений, которые требуется извлекать не в порядке позиций. Тем самым, метод устраняет оба отмеченных выше недостатка. Метод основывается на переписи соединений в предикаты на столбцах внешних ключей таблицы фактов.
Эти предикаты могут вычисляться либо путем использования хэш-поиска (в этом случае моделируется хэш-соединение), либо на основе более совершенных методов, таких как метод, называемый авторами переписыванием в предикат between и обсуждаемый в п. 5.4.2.
За счет переписи соединений в виде предикатов ограничения на столбцах таблицы фактов они могут выполняться в то же время, что и другие предикаты ограничения, которые применяются к таблице фактов, и можно использовать любой алгоритм применения предикатов, описанный в предыдущей статье авторов [5]. Например, все предикаты могут применяться параллельно, а результаты – сливаться с использованием быстрых операций над битовыми строками. Или же результаты применения одного предиката могут передаваться по конвейеру в операцию применения другого предиката для сокращения числа вычислений второго предиката. Только после применения всех предикатов соответствующие кортежи извлекаются из таблиц измерений, имеющих отношение к данному запросу (это также можно делать параллельно). За счет откладывания извлечения данных из таблиц измерений минимизируется число выборок, производимых не в порядке позиций.
Метод скрытых соединений расширяет результаты предыдущих работ по повышению эффективности соединений в звездообразных схемах [17, 23] (напоминающих методы полусоединений [8]) за счет использования преимуществ колоночной организации базы данных и методов переписи предикатов, позволяющих избежать хэш-поиска.
Следствия эффективности соединений
При профилировании кода авторы заметили, что в случае базового варианта C-Store основная часть команд выполняется на ранних стадиях плана (применение предикатов), и что использование метода скрытых соединений делает выполнение соединений осносительно дешевым. Для дальнейшего анализа этого наблюдения была создана денормализованая версия таблицы фактов, в которой таблица фактов и ее таблицы измерений были заранее соединены, так что вместо внешнего ключа к таблице измерений таблица фактов содержала все значения таблицы измерений, повторяющиеся для каждой записи таблицы фактов (например, вся информация о заказчике содержится к каждом кортеже таблицы фактов, соответствующем заказу, который сделал этот заказчик). Понятно, что в строчном хранилище эта полная денормализация была бы более пагубной с точки зрения производительности, поскольку привела бы к существенному расширению таблицы. Однако можно было бы ожидать, что это ускорит выполнение запросов в колоночном хранилище, поскольку нужно было бы считывать только столбцы, имеющие отношение к запросу, и можно было бы избежать выполнения соединений.К своему удивлению, авторы обнаружили, что часто эти ожидания не оправдываются. На рис. 8 сравнивается производительность варианта C-Store с использованием скрытых соединений, обсуждавшегося в предыдущем пункте, с производительностью на том же рабочем наборе трех вариантов единой денормализованной таблицы, для которой соединения были выполнены заранее. В первом случае в денормализованную таблицу включались без изменения полные строки, такие как названия регионов и стран. В этом случае производительность оказалась в пять раз ниже производительности базового варианта. Это связано с тем, что скрытое соединение преобразует предикаты на атрибутах таблицы измерений в предикаты на значениях внешнего ключа таблицы фактов. Когда таблица денормализуется, предикаты применяются к реальному атрибуту символьных строк таблицы фактов. В обоих случаях применение предиката является доминирующим шагом.
Однако предикат на целочисленном внешнем ключе может вычисляться быстрее предиката на атрибуте со значениями-строками символов, поскольку целочисленный атрибут короче.
Конечно, атрибуты типа символьных строк можно было бы легко перекодировать по словарю в целые числа до денормализации. Когда авторы проделали это (случай «PJ, Int C» на рис. 8), разница в производительности между базовым и денормализованным вариантами стала гораздо меньше. Тем не менее, для довольно многих запросов базовый вариант по-прежнему работал быстрее. Для этого имеются две причины. Во-первых, в некоторых запросах SSBM присутствуют два предиката на одной таблице измерений. Метод скрытых соединений может обобщить результат этого двойного применения предиката как один предикат на атрибуте внешнего ключа таблицы фактов. Однако в денормализованном варианте предикаты должны полностью применяться к обоим столбцам таблицы фактов (напомним, что в хранилищах данных таблица фактов, вообще говоря, гораздо крупнее таблиц измерений, и поэтому применение предикатов к таблице фактов обходится намного дороже, чем их применение к таблице измерений).
Рис. 8. Сравнение производительности основного варианта C-Store с исходной схемой базы данных SSBM с той же C-Store с денормализованным вариантом схемы. Денормализованные столбцы могут быть несжатыми («PJ, No C»), сжатыми по словарю в целые числа («PJ, Int C») или предельно сжатыми («PJ, Max C»).
Во-вторых, во многих запросах имеются предикат на одном атрибуте таблицы измерений и группировка по другому атрибуту той же таблицы измерений. При использовании скрытого соединения для этого требуется одна итерация по столбцу внешнего ключа для применения предиката и еще одна итерация (после применения всех предикатов из всех таблиц и выполнения пересечения) для извлечения атрибута группировки. Но, поскольку в C-Store используется конвейерное исполнение, ко времени второго доступа блоки значений столбца внешнего ключа останутся в основной памяти.
В денормализованном случае столбец предиката и столбец группировки являются разными столбцами таблицы фактов, и по ним обоим требуется производить итерирование, что удваивает объем требуемого ввода-вывода.
В действительности, многие столбцы таблиц измерений базы данных SSBM содержат достаточно мало значений, и их можно сжать до размеров, меньших размеров целочисленных внешних ключей. При использовании в S-Store полного сжатия метод денормализации оказался полезным в большем числе случаев (что показано на рис. 8 как случай «PJ, Max C»).
У этих результатов имеются интересные следствия. Денормализация в течение долгого времени использовалась в системах баз данных для повышения эффективности выполнения запросов за счет уменьшения числа соединений во время исполнения. Вообще говоря, школа мудрости учит нас, что при денормализации за эффективность выполнения запросов приходится платить расширением таблицы и повышением уровня избыточности данных (увеличением размера таблицы на диске и повышением риска появления аномалий обновлений). Можно было бы ожидать, что этот компромисс будет более благоприятным для колоночного хранилища (и денормализация будет использоваться более часто), поскольку при использовании схемы хранения по столбцам перестает быть проблемой один из недостатков денормализации – расширение таблицы. Однако результаты авторов показывают нечто противоположное: денормализация не слишком полезна в колоночных хранилищах (по крайней мере, при использовании звездообразных схем). Это объясняется тем, что скрытые соединения выполняются настолько хорошо, что сокращение числа соединений путем денормализации не дает существенного выигрыша. На самом деле, похоже, что денормализация полезна только в тех случаях, когда атрибуты таблицы измерений, включаемые в таблицу фактов, отсортированы (либо вторично отсортированы) или могут быть сильно сжаты.
Соединения столбцов.
Как отмечалось выше, для слияния двух столбцов одной и той же таблицы требуется операция соединения. В System X для выполнения этих операций предпочитается использование хэш-соединений. Авторы проводили эксперименты по принуждению System X к использованию соединений с помощью индексных вложенных циклов и соединений со слиянием, но обнаружили, что это не способствует повышению производительности, поскольку доступ через индексы вызывает высокие накладные расходы, а при выполнении соединения со слиянием System X не может обойтись без сортировки.СУБД с хранением данных по столбцами и по строкам: насколько они отличаются в действительности?
Дэниэль Абади, Сэмюэль Мэдден, Набил ХачемПересказ:
Оригинал: 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, то вторая статья посвящена архитектуре СУБД, основанной на хранении данных по столбцам и ориентированной на использование в приложениях категории OLAP. В опубликованном ранее на CITForum.ru переводе статьи приводились впечатляющие сравнения производительности поколоночной СУБД 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 – определения таблиц базы данных этого тестового набора. При наличии этих приложений читать и понимать статью проще.
Сергей Кузнецов
Сжатие
Для сжатия данных используются алгоритмы сжатия, ориентированные на хранение данных по столбцам. Показано [4], что выполнение операций над данными в сжатом формате позволяет на порядок повысить производительность обработки запросов. Интуитивно понятно, что данные, хранимые в столбцах, сжимаются лучше, чем данные, хранимые в строках. Алгоритмы сжатия лучше работают над данными с низкой энтропией информации (высоким уровнем локальности значений данных). Возьмем для примера таблицу базы данных, содержащую информацию о заказчиках (имя, номер телефона, адрес электронной почты, почтовый адрес и т.д.). При хранении данных по столбцам вместе хранятся все имена, все номера телефонов и т.д. Конечно, номера телефонов больше похожи один на другой, чем адреса электронной почты или имена. Кроме того, если данные отсортированы по значениям одного из столбцов, то этот столбец будет суперсжимаемым (например, последовательность одинаковых значений может кодироваться длиной этой серии).Но, конечно, приведенное наблюдение непосредственно влияет только на степень сжатия. Дисковая память является дешевой и быстро еще более дешевеет (хотя сокращение числа требуемых дисков снижает уровень энергопотребления, фактор стоимости, становящийся все более важным). Однако сжатие способствует повышению производительности (в дополнение к снижению уровня требований к дисковой памяти), поскольку при наличии сжатых данных меньше времени занимают операции ввода-вывода при чтении данных с диска в основную память (или записи из основной памяти на диск). Следовательно, «тяжеловесные» схемы сжатия, оптимизирующие степень сжатия, такие как алгоритмы Лемпеля-Зива (Lempel-Ziv), Хаффмана (Huffman) или арифметического кодирования, могут оказаться менее пригодными, чем «легковесные» схемы, жертвующие степенью сжатия в пользу эффективности распаковки [4, 26]. На самом деле, сжатие может повысить производительность обработки запросов, даже если не принимать во внимание экономию ввода-вывода.
Если компонент выполнения запросов в колоночном хранилище сможет выполнять операции прямо над сжатыми данными, то распаковка вообще не потребуется, а производительность еще более повысится. Например, для схем продольного кодирования (run-length encoding) – где последовательность повторяющихся значений заменяется счетчиком числа значений и самим значением (например, 1; 1; 1; 2; 2 → 1?3; 2?2) – выполнение операций прямо над сжатыми данными дает возможность компоненту обработки запросов выполнять операцию над несколькими одинаковыми значениями столбца только один раз, что позволяет сократить расходы центрального процессора.
В предыдущей работе [4] авторы пришли к выводу, что наибольшее различие между сжатием в строчных и колоночных хранилищах проявляется в тех случаях, когда столбец отсортирован (или вторично отсортирован), и в нем содержатся группы повторяющихся значений. В колоночном хранилище исключительно легко работать с этими группами как с единым целым. В строчном хранилище этот процесс существенно усложняется наличием данных других атрибутов. Таким образом, вообще говоря, сжатие оказывает тем большее воздействие на производительность, чем у большего числа столбцов, упоминаемых в запросе, имеется некоторый порядок сортировки. В базе данных SSBM, используемой в описываемом исследовании, авторы не сохраняли несколько копий таблицы фактов в разных порядках сортировки, и поэтому можно было отсортировать только один из семнадцати столбцов этой таблицы (и еще два – отсортировать вторично). Поэтому сжатие в этом случае в меньшей степени (и в большей зависимости от вида запроса) воздействовало на производительность, чем могло бы быть при более активном использовании избыточности.
Тестовый набор Star Schema Benchmark
В этой работе для сравнения производительности C-Store и коммерческого строчного хранилища используется тестовый набор Star Schema Benchmark (SSBM) [18, 19].SSBM – это тестовый набор хранилищ данных, происходящий от TPC-H. В отличие от TPC-H, в нем используется классическая звездообразная схема (являющаяся установившейся практикой организации данных в хранилищах данных). В SSBM также содержится меньшее число запросов, чем в TPC-H, и ослаблены требования к допустимым настройкам системы. Авторы выбрали этот тестовый набор, потому что его проще реализовать, чем TPC-H, и для его запуска не требовалось модифицировать C-Store (а для запуска полного тестового набора TPC-H это пришлось бы делать).
Традиционный подход.
При применении традиционного подхода этот запрос выполняется путем просмотра всей таблицы LINEORDER c использованием метода хэш-соединений для соединения этой таблицы с таблицами DATE, PART и SUPPLIER (в этом порядке). Затем производится вычисление агрегатной функции (на основе сортировки) для выдачи окончательного результата. Основные расходы по времени уходят на сканирование таблицы LINEORDER, что на системе авторов заняло около 40 секунд. Работа с материализованными представлениями заняла всего 15 секунд, поскольку при этом пришлось прочитать только около трети объема данных, требовавшегося при применении традиционного подхода.Вертикальное разделение.
Наиболее прямолинейный способ эмуляции колоночного хранения в строчном хранилище состоит в полном вертикальном разделении каждого отношения [16]. При использовании такого подхода требуется некоторый механизм соединения полей, образующих допустимую строку (в колоночных хранилищах записи обычно подбираются неявным образом за счет хранения значений столбцов в некотором порядке, но в строчном хранилище такие оптимизации невозможны). Простейший способ состоит в добавлении к каждой таблице целочисленного столбца «позиций» – часто этот способ бывает предпочтительнее использования первичного ключа, поскольку первичный ключ может быть большого размера, а иногда и составным (как в случае таблицы LINEORDER в базе данных SSBM). Для каждого столбца логической схемы создается одна физическая таблица с двумя столбцами – один столбец соответствует столбцу логической схемы, а второй – столбец позиций.Затем запросы переписываются таким образом, чтобы при выборке нескольких столбцов из одного отношения выполнялись соединения по столбцу позиций. В System X по умолчанию для этих целей используются хэш-соединения, которые оказались дорогостоящими. По этой причине авторы экспериментировали с добавлением к каждой таблице кластеризованного индекса на столбце позиций и принуждали System X выполнять соединения через индексы, но это не улучшило производительность – дополнительные обмены с диском из-за обращения к индексам приводили к тому, что соединения выполнялись еще медленнее.
При использовании подхода с вертикальным разделением столбец partkey соединяется (методом хэш-соединения) с отфильтрованной таблицей PART, столбец suppkey соединяется с отфильтрованной таблицей SUPPLIER, и затем оба результирующие множества хэш-соединяются. В результате получаются удовлетворяющие условию запроса кортежи с идентификаторами записей из таблицы фактов и атрибутом p.brand1 из таблицы PART. Затем System X соединяет их (методом хэш-соединения) с таблицей DATE для получения d.year и в завершение использует еще одно хэш-соединение для получения столбца lo.revenue из соответствующей колоночной таблицы. При применении этого подхода требуется полностью (последовательно) прочитать четыре столбца таблицы LINEORDER, для чего, как уже говорилось, приходится считать с диска почти столько же данных, что и при использовании традиционного подхода. И именно это сканирование доминирует при выполнении запроса, делая производительность сравнимой с производительностью традиционного подхода. Хэш-соединения в этом случае снижают производительность почти на 25%. Авторы пытались избавиться от хэш-соединений путем определения кластеризованных B-деревьев на ключевых столбцах каждого вертикального раздела, но System X все равно предпочла использовать хэш-сединения.
В последние годы появился ряд
В последние годы появился ряд систем баз данных с хранением данных по столбцам, включая MonetDB [9, 10] и C-Store [22]. Разработчики этих систем утверждают, что их подход обеспечивает выигрыш в производительности на порядки величин при некоторых рабочих нагрузках, в особенности, при аналитических рабочих нагрузках с большим числом запросов на чтение данных, подобных тем, которые встречаются в приложениях хранилищ данных.Действительно, в статьях, описывающих системы баз данных с хранением данных по столбцам, обычно приводятся результаты, демонстрирующие выигрыш в производительности этих систем над традиционными системами баз данных, которые ориентированы на хранение данных по строкам (как коммерческими, так и распространяемыми с открытыми исходными текстами). Однако сравнения обычно производятся с такими системами, хранящими данные по строкам, в которых используются традиционные схемы хранения данных: база данных состоит из набора хранимых по строкам таблиц, находящихся в более или менее взаимнооднозначном соответствии с таблицами логической схемы базы данных. Хотя эти результаты явно демонстрируют потенциал подхода с хранением данных по столбцам, они оставляют открытым важный вопрос: является ли получаемый выигрыш в производительности следствием фундаментальных архитектурных особенностей колоночных систем, или же подобный выигрыш можно получить и при использовании традиционной системы, если прибегнуть к физической схеме, в большей степени ориентированной на поддержку доступа к данным по столбцам?
Часто разработчики систем с хранением данных по столбцам говорят о наличии фундаментального различия между разработанным с нуля колоночным хранилищем и строчными хранилищами, в которых используется физическая схема, ориентированная на столбцы, в действительности, не анализируя альтернативные физические схемы в строчных хранилищах. Цель данной статьи &ndash на основе систематического подхода ответить на поставленный выше вопрос. Один из авторов статьи является профессиональным администратором баз данных, специализирующимся на одной из популярных коммерческих СУБД с хранением данных по строкам.
Он разработал ряд физических схем базы данных для недавно предложенного эталонного тестового набора хранилищ данных – Star Schema Benchmark (SSBM) [18, 19], изыскивая схемы, которые были бы как можно в большей степени считать «ориентированными на столбцы». К числу основных использованных приемов относятся следующие:
Авторы сравнивали производительность, обеспечиваемую применением этих различных методов, с базовым уровнем производительности СУБД с открытыми кодами C-Store [22] на тестовом наборе SSBM. Результаты сравнения показывают, что, несмотря на возможность применения перечисленных методов для эмуляции физической структуры колоночного хранилища внутри строчного хранилища, производительность обработки запросов в традиционных СУБД остается довольно низкой. Следовательно, основным вкладом этого исследования является демонстрация того, что архитектура систем с хранением данных по столбцам обладает фундаментальными особенностями, делающими такие системы более пригодными к обработке рабочей нагрузки хранилищ данных. Этот результат важен, поскольку позволяет отмести расхожее мнение, что поставщиками существующих СУБД с хранением данных по строкам было бы совсем нетрудно внедрить поколоночное хранение данных на физическом уровне.
Авторы подчеркивают, что их целью являлось не нахождение способа быстрейшего выполнения SSBM в системе, ориентированной на хранение по строкам, а оценка производительности конкретных «колоночных» физических реализаций, что приводит их ко второму вопросу. Какие из многочисленных предлагавшихся в литературе оптимизаций, которые предназначаются для систем с хранением данных по столбцам, играют основную роль в обеспечении преимуществ колоночных хранилищ над строчными хранилищами при выполнении рабочей нагрузки хранилищ данных?
Предыдущие исследования позволяют предположить, что к числу оптимизаций, наиболее важных для СУБД с хранением данных по столбцам, относится следующее:
Однако, поскольку каждый из этих методов описывался в отдельной исследовательской статье, ни в одной работе не проводился анализ того, какой из методов наиболее существенно влияет на производительность. Поэтому третьим вкладом данного исследования является тщательное измерение производительности различных вариантов СУБД C-Store, получаемых поочередным удалением этих оптимизаций (фактически, это вынуждает компонент выполнения запросов C-Store вести себя так, как если бы база данных хранилась по строкам).
Это позволяет проанализировать факторы, обеспечивающие хорошую производительность системы. Авторы установили, что сжатие, если оно возможно, может привести к повышению производительности на порядок, но при использовании других оптимизаций получаемый выигрыш в производительности не является таким значительным. Например, отложенная материализация позволяет повысить производительность всего в три раза, а другие оптимизации, включая итерацию по блокам и скрытые соединения, в среднем обеспечивают выигрыш в производительности в полтора раза.
Таким образом, тремя достижениями статьи являются следующие.
Полученные результаты подтверждают предыдущие утверждения о производительности колоночных хранилищ на новом тестовом наборе хранилищ данных (SSBM) и демонстрируют, что только лишь хранение данных по столбцам – без сжатия и отложенной материализации – не обеспечивает значительного выигрыша в производительности у хорошо оптимизированных систем с хранением данных по строкам.
Оставшаяся часть статьи организована следующим образом. Авторы начинают с описания предыдущих работ в области СУБД с хранением данных по столбцам, включая ранее производившиеся сравнения производительности и архитектурные инновации (разд. 2). В разд. 3 приводится обзор SSBM. После этого в разд. 4 описываются методы разработки физических схем базы данных, использовавшихся в системе с хранением данных по строкам, а в разд. 5 – физическая организация данных и методы выполнения запросов, применявшиеся в системе C-Store. В разд. 6 представлены результаты сравнения этих двух систем. Сначала сравнивается производительность оптимизированной СУБД с хранением данных по строкам с производительностью базового варианта C-Store, а затем изучается, какие методы эффективной обработки запросов, используемые в этой системе, оказались наиболее существенными при выполнении SSBM.
Выполнение запросов в СУБД с хранением данных по строкам
В этом разделе обсуждается несколько различных методов, которые можно использовать для реализации колоночной базы данных в коммерческой СУБД, ориентированной на хранение данных по строкам (здесь и далее она называется System X). Авторы рассматривают три класса физических схем: схема с полным вертикальным разделением, схема с доступом только к индексам и схема с материализованными представлениями. Также проводится сравнение со «стандартной» физической структурой строчного хранилища с одной физической таблицей на каждое отношение.В этом разделе приводится обзор трех общепринятых оптимизаций, используемых для повышения производительности систем баз данных с хранением данных по столбцам, и описывается метод скрытых соединений.
В этой статье сравнивается производительность
В этой статье сравнивается производительность C-Store и нескольких вариантов коммерческого строчного хранилища на тестовом наборе хранилищ данных SSBM. Авторы показали, что попытки эмулировать физическую схему колоночного хранилища в строчном хранилище на основе методов вертикального разделения и доступа только к индексам не приводят к хорошей производительности. Авторы объясняют это высокой стоимостью реконструкции кортежей, а также высокими покортежными накладными расходами в узких вертикально разделенных таблицах. Проанализированы причины, по которым колоночное хранилище может настолько эффективно обрабатывать данные, ориентированные на хранение в столбцах. Обнаружено, что отложенная материализация повышает производительность в три раза, сжатие – в среднем почти в два раза (и на десятичный порядок на запросах, обращающихся к отсортированным данным). Также предложен новый метод соединения, названный скрытым соединением, который позволяет повысить производительность еще на 50%.Авторы не утверждают, что моделировать колоночное хранилище в строчном хранилище невозможно. Они говорят лишь о том, что подобные варианты организации данных показывают плохую производительность при использовании сегодняшних строчных хранилищ (в экспериментах авторов использовался один из последних релизов System X). Для успешного моделирования колоночного хранилища потребуются существенные усовершенствования базовой системы, такие как введение виртуальные идентификаторы кортежей, сокращение покортежных накладных расходов, использование продольного кодирования для нескольких кортежей и применение некоторых ориентированных на столбцы методов выполнения запросов: выполнение операций прямо над сжатыми данными, блочная обработка, скрытые соединения и отложенная материализация. Некоторые из этих усовершенствований реализованы или намечены к реализации в различных строчных хранилищах [12, 13, 20, 24]. Однако построение полного строчного хранилища, которое может работать как колоночное хранилище на соответствующих рабочих нагрузках, представляется авторам интересной исследовательской проблемой.
Запросы.
В тестовый набор SSBM входит тринадцать запросов, разделенных на четыре категории, или «звена» (flight):select sum(lo_extendedprice*lo_discount) as revenue from lineorder, date where lo_orderdate = d_datekey and d_year = 1993 and lo_discount betweenl and 3 and lo_quantity < 25;
select sum(lo_extendedprice*lo_discount) as revenue from lineorder, date where lo_orderdate = d_datekey and d_yearmonth = 199401 and lo_discount between 4 and 6 and lo_quantity between 26 and 35;
select sum(lo_extendedprice*lo_discount) as revenue from lineorder, date where lo_orderdate = d_datekey and d_weeknuminyear = 6 and d_year = 1994 and lo_discount between 5 and 7 and lo_quantity between 26 and 35;
Базы данных: Разработка - Управление - Excel
- Базы данных
- Разработка баз данных
- СУБД и базы данных
- Управление базами данных
- Классика баз данных
- Софт для создания базы данных
- SQL
- Access
- FoxProо
- Расширенная оптимизация подзапросов в Oracle
- Informix
- Линтер
- Postgres
- СУБД DB2
- InterBase
- Excel
- Таблицы Excel
- Справка Excel
- Программирование в Excel
- Деньги в Excel
- Задачи Excel