Ю.А. Григорьев, Е.Ю. Ермаков
6
Эти ключи используются для построения хэш-таблицы, которую
можно использовать для проверки того, удовлетворяет ли предикату
некоторое значение ключа. Пример выполнения первого этапа пока-
зан на рис. 3.
На втором этапе хэш-таблицы используются для извлечения по-
зиций тех записей из таблицы фактов, которые удовлетворяют соот-
ветствующему предикату. Для каждого значения столбца внешнего
ключа таблицы фактов выполняется поиск в соответствующей хэш-
таблице. Далее создается список всех позиций в этом столбце, значе-
ния которых удовлетворяют предикату. Затем списки позиций всех
столбцов пересекаются и создается список позиций таблицы фактов,
которые соответствуют записям, удовлетворяющим исходному усло-
вию поиска. Пример выполнения второго этапа показан на рис. 4.
Рис. 4.
Второй этап скрытого соединения
На третьем этапе с помощью списка позиций таблицы фактов
осуществляется поиск в соответствующей таблице измерений. Если
ключи таблицы измерений образуют отсортированный непрерывный
список идентификаторов, начинающийся с единицы, значение внеш-
него ключа в действительности задает позицию нужного кортежа в
таблице измерений. Это означает, что требуемые столбцы таблицы
измерений могут быть извлечены напрямую с использованием этого
списка значений внешнего ключа.
Пример выполнения третьего этапа показан на рис. 5. Для табли-
цы Date столбец ключа не является отсортированным непрерывным
списком, начинающимся с единицы, поэтому для него требуется вы-
