Спецификации процедуры OptPlanReturn

Вход: список таблиц Q={Q_i}.

Выход: вывод оптимального плана.

Алгоритм.

Поиск в массиве структур str экземпляра i, где str[i].W=Q

// Вывод шага оптимизации

Печать (Q, "=", str[i].X, " ", str[i].Y, "метод", str[i].V.k)

Если str[i].X пусто, то выйти из алгоритма

// Вывод оптимального плана для левого аргумента соединения

OptPlanReturn(str[i].X)

// Вывод метода выбора записей для правого аргумента

// соединения, которым является исходная таблица.

OptPlanReturn(str[i].Y)

Конец алгоритма.

Пример построения оптимального физического плана

Логический план

Построим оптимальный физический план для примера, который был рассмотрен ранее в разделе 1.3. В этом примере был построен логический план, представленный на рис. 1.24.

Рис. 1.24. Логический план выполнения запроса.

Ниже приведены исходные данные для построения физического плана:

1. Количество записей в исходных таблицах:

T(R₁)=10000, T(R₂)=100000

2. Количество записей в одном блоке таблицы:

L_R1= L_R2= 100, L_JOIN=1000

3. Индексы по атрибутам и число записей в блоке индекса (L):

таблица R₁: индекс по атрибуту "код_пользователя" (L=200),

таблица R₂: индекс по атрибуту "номер_счета" (L = 200).

Примечание.Записи исходных таблиц могут читаться в отсортированном виде по своим индексированным атрибутам. Записи в таблице R₁ сгруппированы по атрибуту "код_пользователя" (кластеризованный индекс), записи в таблице R₂ не сгруппированы по атрибуту "остаток".

4. Мощности атрибутов в исходных таблицах:

I(R₁, код_пользователя) = 5000, I(R₁, номер_счета) = 10000,

I(R₂, номер_счета) = 100000, I(R₂, остаток) – неизвестно.

5. Предполагается, что используются левосторонние деревья для поиска оптимального плана и применяются каналы.

6. Некоторые параметры:

b = 10 – число блоков в буфере;

C_comp = C_move = C_filter = 0,01 мс;

C_B = 10 мс – время чтения/записи блока на диск.

Для построения оптимального плана воспользуемся алгоритмом динамического программирования (см. п. 1.7.1).

Алгоритм поиска оптимального физического плана

Ниже приведена последовательность расчётов.

Определение :

1.Определение метода выбора записей из исходной таблицы R₁

(Пользователь):

AccessPlan(R₁) (см. п. 1.7.3).

2. Определение метода выбора записей из исходной таблицы R₂

(Счёт):

AccessPlan(R₂) (см. п. 1.7.3).

Определение метода и порядка соединения :

3. Оценка соединения Q₁ и Q₂ методом NLJ:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

4. Оценка соединения Q₁ и Q₂ методом SMJ:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

5. Выбор метода соединения Q₁ и Q₂ и заполнение структуры:

в JoinPlan(Q₁, Q₂) (см. п. 1.7.4).

6. Оценка и выбор метода соединения Q₂ и Q₁ (по аналогии с

пунктами 3 - 4), сравнение вариантов:

JoinPlan(Q₂, Q₁) (см. п. 1.7.4).

Вывод оптимального физического плана:

7. Вывод физического плана:

OptPlanReturn({Q₁, Q₂}) (см. п. 1.7.5).

8. Представление физического плана в графическом виде.