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

Скрытое соединение


Запросы к хранилищам данным, в частности, к хранилищам данных со звездообразной схемой часто имеют следующую структуру: ограничить множество кортежей в таблице фактов, используя предикаты ограничения над одной или несколькими таблицах измерений; затем выполнить некоторое агрегирование ограниченной таблицы фактов, часто с группировкой по атрибутам другой таблицы измерений. Таким образом, требуется выполнять соединения таблицы фактов и таблиц измерений для каждого предиката и каждой агрегатной группировки. Хорошим примером является Запрос 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 &gt= 1992 and d.year &lt= 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]) за счет использования преимуществ колоночной организации базы данных и методов переписи предикатов, позволяющих избежать хэш-поиска.


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