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


Выбор и оценка альтернативных планов выполнения запросов - часть 14


Обозначим через CiMax и CiMin, соответственно, максимальное и минимальное значения поля Ci.Пусть кортежи из j-ой группы кортежей отношения R1 имеют значение поля C1, равное cj. Тогда число кортежей отношения R2, удовлетворяющих предикату соединения относительно j-ой группы отношения R1 можно оценить как ((C2Max - cj) / (C2Max - C2Min)) * T2. Число кортежей в результирующем отношении, возникающих при соединении j-ой группы кортежей отношения R1 с кортежами отношения R2 оценивается как (T1/CD1) * ((C2Max - cj) / (C2Max - C2Min)) * T2. Для получения оценки общего числа кортежей в результирующем отношении необходимо просуммировать полученную формулу по j для всех групп отношения R1. При этом можно воспользоваться тем, что в силу предположения о равномерности распределения значений поля C1 сумму cj можно оценить как CD1 * AVG (cj) = CD1 * (C1Max C1Min) / CD1 = C1Max - C1Min. Результирующая формула для оценки мощности результирующего отношения имеет вид: T1 * T2 * (C2Max - C1Max + C2Min) / (C2Max - C2Min). Соответственно, селективность предиката оценивается по формуле (C2Max C1Max + C2Min) / (C2Max - C2Min).

Аналогично строятся формулы для оценок мощностей результатов других двухместных операций.

Оценки селективности предикатов используются в оценочных формулах оптимизатора и для оценки затрат ресурсов процессора. Эти оценки базируются на предположении (подтверждаемом на практике) о том, что основная часть процессорной обработки производится в RSS. Поэтому процессорные затраты измеряются просто числом обращений к RSS, которое в свою очередь определяется числом кортежей, получаемых при сканировании хранимого или временного отношения, т.е. селективностью логического выражения, состоящего из простых предикатов. (Напомним, что при сканировании отношения при каждой операции взятия следующего кортежа RSS получает параметр - логическое выражение, состоящее из простых предикатов и представляющее условие, которому должен удовлетворять следующий кортеж. На самом деле при использовании RSS в System R это логическое условие всегда одно и то же в пределах каждого сканирования и представляет собой предикат ограничения соответствующего отношения [129].) При предположениях о равномерности и независимости значений разных полей отношения селективность логического выражения, составленного из простых предикатов, легко оценить при известных степенях селективности простых предикатов.




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