5. Оценка числа блоков в промежуточной таблице q

Число блоков в промежуточной таблице можно оценить при помощи следующей формулы:

,

где

Q=_F(R) – промежуточной таблица, соответствующая подзапросу Q,

T(Q) - оценка числа кортежей в промежуточной таблице (см. п. 1.4.4),

L_B – длина блока (т.е. число записей в блоке),

- операция округления с избытком.

5. Порядок соединения таблиц

Существуют три вида деревьев соединений:

1. Левостороннее дерево соединений.

2. Кустовое (ветвящееся) дерево соединений.

3. Правостороннее дерево соединений.

1. Левостороннее дерево соединений

Рис. 1.9. Левостороннее дерево соединений.

В данном варианте в каждом соединении правым аргументом является исходная таблица. Этот порядок соединения имеет следующие преимущества:

• число переборов вариантов соединений меньше, чем для кустового дерева (для левостороннего дерева оно равно n!, где n – число соединяемых таблиц);

• для этого типа дерева достаточно просто организовать каналы обработки.

Канал обработки – это возможность передачи результатов выполнения одной операции на вход другой операции через оперативную память (без промежуточного запоминания на диске).

Рассмотрим операции соединений 1 и 2 на Рис. 1 .9: (R S) T. Схема выполнения этих операций показана на Рис. 1 .10.

Рис. 1.10. Организация каналов обработки.

В канале только левый аргумент может быть опорным (т.е. храниться в оперативной памяти). Правый аргумент соединения называется тестируемым и может располагаться на диске. Если таблица подзапроса R и результат соединения (см. Рис. 1 .10) умещаются в оперативной памяти, то использование каналов позволяет организовать однопроходной алгоритм соединения таблиц (исходные таблицы R₁, S₁, T₁ читаются с диска один раз).

Можно отметить следующий недостаток рассмотренного порядка соединения таблиц: выбирается квазиоптимальный план, так как перебирается ограниченное число вариантов (n!), поскольку правый аргумент – это всегда исходная таблица.

2. Кустовое дерево соединений

Рис. 1.11. Кустовое дерево соединений.

Здесь таблицы могут соединяться в произвольном порядке.

Этот метод обеспечивает поиск оптимального плана, так как перебираются все возможные варианты соединения таблиц. Но часто полный перебор всех деревьев соединений занимает много времени. Также при выполнении соединений таблиц имеются сложности в организации каналов, так как возрастают требования к объёму оперативной памяти.

Например, для реализации однопроходного алгоритма соединения таблиц, представленных на Рис. 1 .11, необходимо, чтобы в оперативной памяти размещались таблицы R и , T и .

3. Правостороннее дерево соединений

Рис. 1.12. Правостороннее дерево соединений.

В данном варианте в каждом соединении левым аргументом является исходная таблица.

Этот способ практически не используется, так как для реализации однопроходного алгоритма соединений необходимо, чтобы в ОП размещались (не одновременно) таблицы T, S, R и результаты промежуточных соединений.

6. Методы соединения таблиц

Ниже рассматриваются три метода соединения таблиц:

• метод вложенных циклов (NLJ – Nested Loop Join),

• метод сортировки-слияния (SMJ – Sort Merge Join),

• хешированное соединение (HJ – Hash Join).