4. Спецификации процедуры JoinPlan

Вход: список имен таблиц R=(P – Q_j) и имя таблицы S=Q_j (см. основной алгоритм в п. 1.7.1)

Выход: заполненный экземпляр структуры str[n].

Алгоритм.

Поиск в массиве структур str экземпляров с номерами m₁ и m₂,

для которых str[m₁].W=R и str[m₂].W=S .

// Оценка стоимости соединения для различных методов:

// i=1 – NLJ, i=2 – SMJ, i=3 – HJ ;

// выбрать оптимальный метод соединения k(1,2,3).

ДЛЯ i=1,3

C_i = C_CPUi + C_I/Oi

// C_CPUi и C_I/Oi вычисляются с помощью формул (5.8) (для i=1)

// или формул (5.9) (для i=2); метод i=3 не рассматривается.

// Необходимая информация для расчета по формулам

// хранится в полях str[m₁].V и str[m₂].V.

КОНЕЦ ДЛЯ

C = min(C₁, C₂) //здесь С=С_k; пока это стоимость соединения R и S

// текущая стоимость плана, включающая стоимости чтения

// из исходных таблиц и стоимости промежуточных соединений

С = str[m₁].Z + str[m₂].Z + C

С_I/O = str[m₁].ZIO + str[m₂].ZIO + C_{I/O k} // дисковая составляющая

Поиск в массиве структур str экземпляра "n", для которого str[n].W=P. Если экземпляр "n" не найден, то заполнить пустой экземпляр "n". Если экземпляр "n" найден и выполняется неравенство str[n].Z > C, то переписать экземпляр "n". Выражения для заполнения экземпляра "n":

str[n] = {P, R, S, C, C_I/O , // W, X, Y, Z, ZIO

{T(P), B(P), {I(P, A_i)}_i, k} } // V - см. формулы (5.10)

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

5. Спецификации процедуры 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)

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

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

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

Построим оптимальный физический план для примера, который был рассмотрен ранее в разделе 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).