Перезапись в предикат between
Алгоритм скрытых соединений в том виде, как он описан выше, во многом заимствует идеи полусоединения с учетом хранения данных по столбцам и хэш-соединения с отложенной материализацией. Хотя в методе скрытых соединений хэш-часть соединения выражается в виде предиката на столбце таблицы фактов, способы вычисления этого предиката и выполнения хэш-соединения (с отложенной материализацией) практически почти не различаются. Преимущество от представления соединения в виде предиката становится существенным в очень распространенном случае (для соединений в базе данных со звездообразной схемой), когда множество ключей в таблице измерений, остающееся после применения предиката, является непрерывным. В этом случае можно использовать метод, называемый авторами перезаписью в предикат between, когда предикат на таблице фактов, вычисляемый на основе хэш-поиска, переписывается в предикат between, ограничивающий внешний ключ диапазоном значений. Например, если непрерывным множеством значений ключа после применения предиката является отрезок [1000, 2000], то вместо вставки каждого из этих ключей в хэш-таблицу и проверки на основе этой хэш-таблицы каждого значения внешнего ключа таблицы фактов можно просто проверять вхождение очередного значения внешнего ключа в этот отрезок. Если эта проверка удается, соответствующий кортеж входит в результат соединения, иначе – нет. Очевидно, что предикаты between обрабатываются быстрее, поскольку для этого не требуется какой-либо поиск.
Возможность применения этой оптимизации зависит от того, непрерывны ли множества допустимых ключей таблиц измерений. Во многих случаях это свойство не выполняется. Например, при применении к неотсортированному полю предиката, задающего условие вхождения в диапазон значений, получается не непрерывное множество позиций. И даже для предикатов на отсортированных полях процесс сортировки таблицы измерений по такому атрибуту, вероятно, переупорядочит первичные ключи, так что они перестанут образовывать упорядоченное, непрерывное множество идентификаторов.
Однако последнюю проблему легко преодолеть за счет использования кодирования по словарю (dictionary encoding) с целью переназначения ключей (а не сжатия). Поскольку ключи уникальны, кодирование столбца по словарю приводит к тому, что словарные ключи образуют упорядоченный, непрерывный список, начинающийся с нуля. Если столбец внешнего ключа таблицы фактов кодируется с использованием той же словарной таблицы, то можно производить перепись предиката с поиском по хэш-таблице в предикат between.
Кроме того, утверждение, что эта оптимизация работает только для предикатов на отсортированном столбце таблицы измерений, является не совсем верным. На самом деле, таблицы измерений в хранилище данных часто содержат наборы атрибутов с повышающимися уровнями детализации. Например, в таблице DATE базы данных SSBM имеются столбцы year, yearmonth и столбец полной даты date. Если таблица отсортирована по столбцу year, вторично отсортирована по столбцу yearmonth и на третьем уровне отсортирована по полной дате, то применение предиката сравнения по равенству к любому из этих трех столбцов приведет к формированию непрерывного набора результатов (или предиката проверки вхождения в диапазон значений на отсортированном столбце). Другой пример: в таблице SUPPLIER имеются столбцы region, nation, и city (в регион входит много стран, а в стране имеется много городов). Снова при сортировке слева направо применение предиката к любому из этих трех столбцов приведет к формированию непрерывного диапазона. В запросах к хранилищу данных часто используются такие столбцы, поскольку распространенной практикой OLAP является детализация данных при последовательном применении запросов (получить величину прибыли по регионам, получить величину прибыли по странам, получить величину прибыли по городам). Таким образом, перезапись в предикат between может использоваться чаще, чем может показаться сначала, и часто приводит к существенному выигрышу в производительности (что демонстрируется в следующем разделе).
Заметим, что для применения этого вида оптимизации не требуется изменять оптимизатор запросов. При вычислении предикатов над таблицами измерений можно проверить, является ли результирующее множество непрерывным. Если это так, то предикат над таблицей фактов переписывается во время выполнения.
