СУБД с хранением данных по столбцами и по строкам

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


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

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

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

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


Содержание раздела