5. Выполнение запросов в СУБД с хранением данных по столбцам

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

5.1. Сжатие

Для сжатия данных используются алгоритмы сжатия, ориентированные на хранение данных по столбцам. Показано [4], что выполнение операций над данными в сжатом формате позволяет на порядок повысить производительность обработки запросов. Интуитивно понятно, что данные, хранимые в столбцах, сжимаются лучше, чем данные, хранимые в строках. Алгоритмы сжатия лучше работают над данными с низкой энтропией информации (высоким уровнем локальности значений данных). Возьмем для примера таблицу базы данных, содержащую информацию о заказчиках (имя, номер телефона, адрес электронной почты, почтовый адрес и т.д.). При хранении данных по столбцам вместе хранятся все имена, все номера телефонов и т.д. Конечно, номера телефонов больше похожи один на другой, чем адреса электронной почты или имена. Кроме того, если данные отсортированы по значениям одного из столбцов, то этот столбец будет суперсжимаемым (например, последовательность одинаковых значений может кодироваться длиной этой серии).

Но, конечно, приведенное наблюдение непосредственно влияет только на степень сжатия. Дисковая память является дешевой и быстро еще более дешевеет (хотя сокращение числа требуемых дисков снижает уровень энергопотребления, фактор стоимости, становящийся все более важным). Однако сжатие способствует повышению производительности (в дополнение к снижению уровня требований к дисковой памяти), поскольку при наличии сжатых данных меньше времени занимают операции ввода-вывода при чтении данных с диска в основную память (или записи из основной памяти на диск). Следовательно, «тяжеловесные» схемы сжатия, оптимизирующие степень сжатия, такие как алгоритмы Лемпеля-Зива (Lempel-Ziv), Хаффмана (Huffman) или арифметического кодирования, могут оказаться менее пригодными, чем «легковесные» схемы, жертвующие степенью сжатия в пользу эффективности распаковки [4, 26]. На самом деле, сжатие может повысить производительность обработки запросов, даже если не принимать во внимание экономию ввода-вывода. Если компонент выполнения запросов в колоночном хранилище сможет выполнять операции прямо над сжатыми данными, то распаковка вообще не потребуется, а производительность еще более повысится. Например, для схем продольного кодирования (run-length encoding) – где последовательность повторяющихся значений заменяется счетчиком числа значений и самим значением (например, 1; 1; 1; 2; 2 → 1×3; 2×2) – выполнение операций прямо над сжатыми данными дает возможность компоненту обработки запросов выполнять операцию над несколькими одинаковыми значениями столбца только один раз, что позволяет сократить расходы центрального процессора.

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

5.2. Отложенная материализация

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

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

В более современных колоночных хранилищах, таких как MonetDB/X100, C-Store и, в меньшей степени, Sybase IQ, данные сохраняются в формате столбцов гораздо дольше, и операции выполняются прямо над этими столбцами. Для этого часто требуется построение промежуточных списков «позиций», чтобы можно было находить соответствие между результатами операций, выполненных над разными столбцами. Например, рассмотрим запрос, в котором к двум столбцам применяются предикаты, и из всех кортежей, удовлетворяющих этому условию, выбирается некоторый третий атрибут. В колоночных хранилищах с отложенной материализацией предикаты применяются к столбцам по отдельности, и формируется список позиций (порядковых смещений в столбце) значений, удовлетворивших данному условию. В зависимости от селективности предиката этот список позиций может представляться в виде простого массива, битовой строки (в которой наличие единицы в i-том бите означает, что i-тое значение удовлетворяет предикату) или множества диапазонов позиций. Затем над этими представлениями позиций выполняется операция пересечения (при использовании битовых строк можно использовать поразрядную операцию AND) для создания единого списка позиций. И, наконец, этот список применяется к третьему столбцу для выборки значений из нужных позиций.

У поздней материализации есть четыре основных преимущества. Во-первых, для выполнения операций выборки и агрегации конструирование некоторых кортежей может вообще не понадобиться (если компонент выполнения запросов откладывает конструирование кортежа достаточно надолго, то он может вообще избежать его конструирования). Во-вторых, если данные сжаты с использованием некоторого метода, ориентированного на хранение данных по столбцам, то их придется распаковывать до комбинирования этих значений со значениями других столбцов. Это устраняет описанные выше преимущества выполнения операций прямо над сжатыми данными. В третьих, при выполнении операций прямо над данными столбцов повышается эффективность использования кэша, поскольку блоки кэша не засоряются данными атрибутов, не существенными для данной операции (как показано в PAX [6]). В четвертых, на эффективность обработки атрибутов со значениями постоянного размера сильное воздействие оказывает оптимизация итерации по блокам, описываемая в следующем подразделе. В строчном хранилище, если у какого-нибудь атрибута допускаются значения разного размера, то и все кортежи имеют переменный размер. В колоночном хранилище с отложенной материализацией столбцы со значениями постоянного размера могут обрабатываться отдельно.

5.3. Итерация по блокам

Для обработки последовательностей кортежей в строчных хранилищах просматриваются все кортежи, и из них выбираются требуемые атрибуты через интерфейс представления кортежей [11]. Во многих случаях, например, в MySQL, это приводит к покортежной обработке запросов, где для каждой операции требуется 1-2 вызова функций для извлечения из кортежа требуемых данных (и если эта операция связана с вычислением простого выражения или условия, то стоимость ее выполнения мала по сравнению с расходами на вызов функции) [25].

В недавних исследованиях показано, что некоторые накладные расходы обработки кортежей в строчных хранилищах можно сократить, если одновременно доступны блоки кортежей, которые можно обрабатывать путем вызова одной операции [24, 15]. Подобный подход реализован в IBM DB2 [20]. В отличие от выборочной реализации блочного подхода в строчных хранилищах, во всех колоночных хранилищах (насколько это известно авторам) операции над блоками значений одного и того же столбца выполняются на счет одного вызова функции. Кроме того, не требуется извлечение атрибутов, и, если данный столбец содержит значения фиксированного размера, то данные можно представлять в виде массива. Обработка данных, представленных в виде массива, не только минимизирует покортежные накладные расходы, но также дает возможность использовать средства распараллеливания современных процессоров, позволяя применять методы конвейеризации циклов [9].