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


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


В реальных условиях кластеризованность отношения по одному полю не обязательно означает полное отсутствие кластеризованности того же отношения по другим полям (предположение System R о независимости распределений значений разных полей отношения). Ниже мы рассмотрим один из предложенных в последнее время подходов к более адекватному учету реально существующих кореляций атрибутов отношений.

Предположения о равномерности распределений значений атрибутов отношений позволяют достаточно просто оценивать и мощности отношений, являющихся результатами двухместных реляционных и теоретико-множественных операций над отношениями. Рассмотрим, например, как можно оценить степени селективности двух предикатов соединения - R1.C1 = R2.C2 и R1.C1 > R2.C2.

Начнем с предиката эквисоединения R1.C1 = R2.C2. Пусть Ti и CDi - число кортежей в отношении Ri и число различных значений поля Ci, соответственно. Тогда в отношении Ri существует Ti/CDi групп кортежей с одинаковыми значениями поля Ci. Очевидно, что при выполнении операции соединения кортежи каждой группы кортежей отношения R1 могут быть соединены с кортежами не более, чем одной группы отношения R2 (и наоборот). Если кортежи двух групп соединяются, то в результирующем отношении образуется (T1/CD1) * (T2/CD2) кортежей. (Оценка числа кортежей в каждой группе в виде Ti/CDi правомерна в соответствии с предположением о равномерности распределения). Очевидно, что соединиться могут не более, чем Min (CD1, CD2) групп. Поэтому верхней оценкой мощности результирующего отношения может быть Min (CD1, CD2) * (T1/CD1) * (T2/CD2). Соответственно, степень селективности предиката эквисоединения можно оценить, как Min (CD1, CD2) / (CD1 * CD2).Заметим, что эта оценка достаточно точна (при соблюдении предположении о равномерности распределения), если отношения "хорошо" соединяются, как, например, отношения EMP и DEPT из нашего примера по полю DEPT#.

Формула для оценки степени селективности предиката соединения R1.C1 > R2.C2 выводится немного более сложно.


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



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