8.2. Оценка размеров промежуточных отношений

Физический план выбирается таким образом, чтобы свести к минимуму пример­ную стоимость выполнения запроса. Независимо от метода выполнения плана и спо­собов подсчета его стоимости, на значение стоимости большое влияние оказывают размеры промежуточных отношений, получаемых в процессе обработки операторов плана. В идеале было бы неплохо иметь правила предсказания количества кортежей в промежуточных отношениях,

1) дающие точные оценки;

2) простые в использовании;

3) логически непротиворечивые (в частности, оценка размера промежуточ­ного отношения не должна зависеть от способа его получения: например, прогнозируемое значение объема отношения, получаемого в результате со­единения нескольких операндов, не должно определяться порядком обра­ботки этих операндов).

Универсального способа, который позволил бы удовлетворить все три условия, не су­ществует. Мы, тем не менее, предложим вашему вниманию несколько простых пра­вил, приемлемых в большинстве ситуаций. К счастью, целью прогнозирования разме­ров отношений не является получение сколько-нибудь точных абсолютных оценок — задача сводится к тому, чтобы просто облегчить выбор физического плана запроса. Неточный метод предсказания может восприниматься как вполне терпимый, если он ставит в соответствие наименьшее значение стоимости наилучшему физическому пла­ну, - даже в том случае, когда само это значение расходится с реальным, получаемым в результате выполнения плана.

8.2.1. Оценка размера результата операции объединения

Рассмотрим первый вариант операции объединения

.

Рис. 8.1 - Операция объединения

.

В общем случае

.

Второй вариант операции объединения

.

Рис. 8.2 - Операция объединения

.

8.2.2. Оценка размера результата операции пересечения

.

8.2.3. Оценка размера результата оператора проекции

Оператор проекции (projection) π в контексте обсуждаемой темы отличается от других операторов тем, что объем результата его выполнения может быть вычислен точно. Поскольку в итоговое отношение проекции включается каждый кортеж отноше­ния-аргумента, изменение объема данных обусловлено только трансформацией структу­ры кортежа. Напомним, что оператор проекции относится, вообще говоря, к категории "мультимножественных" операторов и сам по себе не обеспечивает удаление повто­ряющихся кортежей; если после проецирования необходимо избавиться от дубликатов, следует прибегнуть к услугам оператора δ, предназначенного именно для такой цели.

Обычно оператор проекции предполагает сокращение длины кортежей за счет изъя­тия компонентов отдельных атрибутов. Однако оператор расширенной проекции (extended projection), напротив, позволяет формировать новые компо­ненты на основе существующих, так что в определенных ситуациях размер итогового отношения не только не уменьшается в сравнении с исходным, но даже возрастает.

Пример. Обратимся к отношению R(a, b, с), атрибуты а и b которого относятся к целочисленному четырехбайтовому типу, а компоненты атрибута с являются стро­ками длиной в 100 байт. Допустим, что под заголовок кортежа R отводится 12 байт. Тогда для хранения каждого кортежа потребуются 120 байт. Предположим также, что объем блока составляет 1024 байт, причем длина заголовка блока равна 24 байт. Таким образом, в один блок способны уместиться 8 кортежей. Будем считать, что T(R)= 10000, т.е. R содержит 10000 кортежей. Тогда B(R) = 1250.

Рассмотрим оператор S = π_a+b,c(R), предусматривающий замену компонентов а и b каждого кортежа R их суммой. Длина кортежа S составляет 116 байт: 12 для заголовка, 4 для суммы и 100 для строки. Хотя кортежи S несколько короче кортежей R, в один блок можно уместить по-прежнему только 8 кортежей, так что T(S)= 10000 и B(S)=1250.

Теперь воспользуемся оператором U = π_а,b (R), который предполагает изъятие строкового компонента с. Длина кортежа U равна всего 20 байт, a T(U) = 10000. Сейчас в один блок удается упаковать уже 50 кортежей, поэтому B(U) = 200, и в результате секции объем исходного отношения уменьшится в шесть с небольшим раз.