Методы оптимизации выполнения запросов в реляционных СУБД


Оптимизаторы с гибкой структурой - часть 5


Пусть, как и раньше, определение TableAccess имеет вид

TableAccess (T, C, P) = ¦TableScan (T, C, P) ¦ +FOR ALL i IN I(T): GET (TableScan (i, {TID}, P}, T, C, P) ¦ ¦ IF CONDITION1 L

Имеются два альтернативных определения: первая альтернатива вызывает STAR с именем TableScan, вторая - LOLEPOP с именем GET. Пусть условие CONDITION1 - истинно, и I (EMP) = {INDEX1, INDEX3}. Вторая альтернатива повторяется для каждого i, принадлежащего I (T).

При подстановке параметров для каждого нового узла каждый параметр в определении заменяется на соответствующий аргумент в вызове. Например, параметр T заменяется на EMP. Во втором альтернативном определении первый параметр является вызовом STAR с именем TableScan, на который указывает ссылка из первого аргумента узла GET. Указатель на TableScan получает приоритет и заносится в список необработанных вызовов.

Дерево вызовов после выполнения одной итерации первой фазы алгоритма показано на Рис.5. Для выработки плана, т.е. полной редукции всех STAR к LOLEPOP, потребуются еще по крайней мере три итерации, поскольку в дереве имеется STAR TableScan, не сведенное к LOLEPOP.

На второй фазе обработка начинается с наиболее вложенного LOLEPOP (обычно это LOLEPOP ACCESS, относящийся к хранимой таблице). Обработка производится "снизу вверх" с вызовом функции свойств каждого LOLEPOP. Каждая функция использует параметры вызова LOLEPOP, включая планы и их свойства. Стоимость рассматривается как часть вектора свойств и считается для каждого LOLEPOP как сумма его собственной стоимости и стоимостей всех его входных параметров-планов.

Предположим, что в нашем примере в полностью расширенной форме получаются два альтернативных плана:

ACCESS (HEAP, EMP, {NAME, ADDRESS}, {EMP.SAL < 30.000, EMP.AGE > 45}) и GET (ACCESS (BTree, INDEX1, {TID}, EMP.AGE > 45), EMP, {NAME, ADDRESS}, EMP.SAL < 30.000).

В первой альтернативе нет вложенности, поэтому нужно вызвать только функцию свойств для LOLEPOP ACCESS. Эта функция выработает вектор свойств, характеризующих стоимость и эффект этого плана: из отношения EMP будут выбираться значения полей NAME, ADDRESS и TID (TID выбирается всегда) с применением предикатов на SAL и AGE; при выборе не будет поддерживаться какой-либо порядок кортежей.




Начало  Назад  Вперед



Книжный магазин