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


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


Подход System R является тривиальным частным случаем метода параметрической оценки распределения - любое распределение оценивается как равномерное. Более развитый подход был предложен Христодолакисом в [81]. Он предложил использовать для оценки реального распределения значений поля отношения серию распределений Пирсона, в которую входят распределения от равномерного до нормального. Выбор распределения из серии производится путем вычисления нескольких параметров на основе выборок реально встречающихся значений.

К сожалению, нам неизвестна какая-либо реализованная система, в оптимизаторе которой использовался бы этот подход, и потому мы ничего не можем сказать по поводу его практической применимости на основе экспериментальных результатов. Заметим лишь, что его применение ограничено только числовыми значениями (т.е. на основе этого подхода нельзя, например, оценить распределение поля, значения которого - текстовые строки переменного размера).

Метод оценки распределения на основе сигнатур в общих словах можно описать следующим образом. Область значений поля разбивается на несколько интервалов. Для каждого интервала некоторым образом устанавливается число значений поля, попадающих в этот интервал. Внутри интервала значения считаются распределенными по некоторому фиксированному закону (как правило, принимается равномерное приближение). Рассмотрим теперь более точно два альтернативных подхода, связанных с сигнатурным описанием распределений.

Традиционный подход, описываемый, например, в [81], состоит в том, что область значений поля разбивается на N интервалов равного размера, и для каждого интервала подсчитывается число значений полей из кортежей данного отношения, попадающих в интервал. Например, предположим, что наше отношение регистрации сотрудников предприятия EMP расширено еще одним полем AGE - возраст сотрудника. Пусть всего в организации работает 60 сотрудников в возрасте от 10 до 60 лет. Тогда гистограмма, изображающая распределение значений поля AGE может иметь вид, показанный на Рис.2.


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



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