Детали соединений
При использовании метода скрытых соединений соединения выполняются в три этапа. Сначала каждый предикат применяется к соответствующей таблице измерений для извлечения списка ключей таблицы измерений, удовлетворяющих данному предикату. Эти ключи используются для построения хэш-таблицы, которую можно использовать для проверки того, удовлетворяет ли предикату некоторое значение ключа (эта хэш-таблица должна легко поместиться в основной памяти, поскольку таблицы измерений обычно являются небольшими, и хэш-таблица содержит только ключи). Пример выполнения этого первого этапа для приведенного выше запроса на некоторых примерных данных показан на рис. 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 на некоторых примерных данных
