Оценка стоимости и мощности
Теперь мы выведем формулу для оценки стоимости применения метода Filterjoin. Заметим, что эта оценочная формула должна вычисляться за константное время. Предположим, что в оцениваемом Filterjoin имеются (R1 ?? R2 ?? … ?? R(k-1)) как внешнее отношение и Rk как внутреннее отношение. Стоимость вычисления соединения можно разбить на компоненты, показанные в таб. 1 и разъясняемые ниже. Общая стоимость Filterjoin является суммой этих компонентов.
JoinCostP + ProductionCostP + ProjCostF +
FilterCostRk + FinalJoinCost
JoinCostP: Это стоимость внешнего отношения, которая уже вычислялась как часть алгоритма оптимизации.
ProductionCostP: P требуется материализовать, поскольку это отношение используется как для генерации фильтрующего множества, так и в соединении верхнего уровня. Стоимость материализации PartialResult – это простая функция от мощности P. Поскольку эта мощность уже известна (т.е. уже оценена оптимизатором), можно вычислить стоимость материализации. Вместо того чтобы создавать временное отношение P, можно было бы вычислять повторно. Стоимость повторного вычисления P является такой же, как и JoinCostP. В качестве ProductionCostP выбирается минимум из стоимости материализации и стоимости повторного вычисления.
ProjCostF: Стоимость выполнения проецирования P (с устранением дубликатов) для генерации фильтрующего множества F зависит от мощности P. Эта стоимость также зависит от физических характеристик плана для P (например, отсортировано P или нет) и от того, можно ли совместить проецирования с генерацией P. У оптимизатора имеется вся необходимая информация для оценивания ProjCostF.
FilterCostRk: Это стоимость генерации отфильтрованной версии Rk с использованием фильтрующего множества F (пусть отфильтрованное отношение называется Rk’). Обсуждение метода вычисления стоимости и мощности Rk’ приводится после этих определений.
FinalJoinCost: Это считается просто. Мощность внешнего отношения известна. Мощность отфильтрованного внутреннего отношения только что подсчитана. Для определения наиболее дешевого способа выполнения завершающего соединения можно применить оценочные формулы других доступных методов соединения.
Заметим, что все (кроме одного) компоненты стоимости можно вычислить за константное время с использованием общеизвестных оценочных формул, уже используемых в существующих оценочных оптимизаторах. В следующем разделе показывается, как можно оценить за константное время стоимость и мощность отфильтрованного отношения Rk (FilterCostRk).
