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


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


Аналогично, SEL (R.C < const) = (const - CMin) / (CMax - CMin) (опять же естественно, что при равномерном распределении значений поля доля кортежей, удовлетворяющих условию попадания значения заданного поля в указанный интервал значений, линейно возрастает при увеличении размера интервала). SEL (R.C <= const) полагается равной SEL (R.C < const), а SEL (R.C >= const) равной SEL (R.C > const).

При оценках числа блоков, в которых могут располагаться кортежи, удовлетворяющие предикату R.C op const, различаются два случая: отношение кластеризовано по полю C или не кластерозовано по этому полю. Заметим, что оценивать это число блоков имеет смысл только в том случае, когда сканирование отношения для его ограничения в соответствии с предикатом производится с использованием индекса на поле C. Для варианта сканирования без использования индекса понадобится всегда обратиться ровно к N блокам внешней памяти.

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

В этом случае селективность предиката по отношению к кортежам распространяется и на блоки, занимаемые этими кортежами. Например, если в блоке внешней памяти базы данных размещается K кортежей отношения R (параметр K в System R определяется при создании отношения и не изменяется во все время его существования), то число блоков кластеризованного отношения, содержащих кортежи, удовлетворяющие предикату R.C op const, определяется по формуле T * SEL (R.C op const) / K. (Первый член формулы задает количество кортежей, удовлетворяющих предикату.)




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



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