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


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


Как и в чистом методе гистограмм, количество интервалов выбирается исходя из ограничений по памяти, и чем оно больше, тем точнее получаемые оценки. При выборе разбиения области значений на десять интервалов получаемая псевдогистограммная картина распределений значений поля AGE показана на Рис.3.

На Рис.3 область значений поля AGE отношения EMP разбита на 10 интервалов таким образом, что в каждый интервал попадает ровно по 10 значений поля AGE. При этом, естественно, интервалы имеют разные размеры. Граничные значения интервалов показаны над вертикальными линиями. Особенностью псевдогистограммы является то, что в ней возможны, в частности, интервалы, правая и левая граница которых совпадают. На нашем рисунке таким интервалом является интервал (28,28). Он образовался по причине наличия в отношении EMP большого (большего десяти) числа кортежей со значением AGE = 28.

Очевидно, что с использованием такой "псевдогистограммы" ошибки при оценках степеней селективности предикатов с операцией, отличной от равенства, уменьшаются. В [84] приводятся два метода оценок селективности простых предикатов на основе такого способа описания распределения с минимизацией возможной ошибки в худшем случае и в среднем. При этом размер ошибки уже не зависит от значения константы предиката и уменьшается при увеличении числа интервалов.

Существенным недостатком метода псевдогистограмм по сравнению с методом гистограмм является необходимость сортировки отношения в соответствии со значениями поля для построения псевдогистограммы распределений значений этого поля. С другой стороны, ситуация ничем не отличается от получения статистик в System R: чтобы получить число различных значений поля, на котором не определен индекс, нужно отсортировать отношение в соответствии со значениями этого поля. Тем не менее, в [84] предлагается некоторый подход, который позволяет получить достоверную псевдогистограмму без необходимости сортировки всего отношения.

Подход основывается на статистике Колмогорова, из которой применительно к случаю реляционных баз данных следует, что если из отношения выбирается образец из 1064 кортежей, и b - доля кортежей в образце со значениями поля C < V, то с достоверностью 99% доля кортежей во всем отношении со значениями поля C < V находится в интервале [b-0.05, b+0.05].


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



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