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


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


Можно привести сколь угодно много примеров баз данных, для которых эти предположения не оправданы. В этих случаях, естественно, оптимизатор System R будет заведомо неверно оценивать планы выполнения запросов.

В каталогах базы данных для каждого отношения R поддерживается следующая информация: число кортежей в данном отношении (T); число блоков внешней памяти, в которых располагаются кортежи отношения (N); для каждого поля C отношения хранится число различных значений этого поля (CD), минимальное хранимое значение этого поля (CMin) и максимальное значение (CMax). Для более точной оценки доступа к отношению через индексы для каждого индекса хранится число уровней этого индекса и число листовых страниц. (Напомним, что для организации индексов в System R используется техника B-деревьев. Поскольку в B-деревьях допускается наличие недозаполненных страниц, информация о числе уровней индекса и числе листовых страниц не выводится из информации об общем числе кортежей в отношении и числе различных значений поля, на котором определен индекс.) На нашем уровне изложения статистическая информация об индексах несущественна.

Заметим, что в ранних версиях System R (например, [2]) статистики о значениях полей поддерживались только для тех полей, на которых определены индексы, но затем были внедрены и для неиндексных полей, чтобы была возможность оценивать мощность временных отношений, полученных ограничением базового отношения в соответствии с простым предикатом на неиндексном поле [6].

При наличии такой информации в условиях базового предположения о равномерности распределения значений любого поля отношения степень селективности простых предикатов вычисляется очень просто (и очень точно, если распределение на самом деле равномерно). Будем обозначать степень селективности предиката P как SEL (P). Тогда SEL (R.C = const) = CD / (CMax - CMin) (естественно, что при равномерном распределении степень селективности такого предиката не зависит от значения константы). SEL (R.C > const) = (CMax - const) / (CMax - CMin).


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



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