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


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


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

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

Если при организации списка tid'ов в записи индекса поддерживать в каждом списке упорядоченность tid'ов в соответствии с номерами блоков, содержащих соответствующие кортежи, то при последовательном просмотре кортежей с фиксированным значением ключа появляется некоторый элемент порядка. В уточненном варианте оптимизатора System R для оценки числа блоков, обращения к которым должны произойти при таком просмотре используется формула N * (1 - (1 - 1/N) ** CD). Эта формула была впервые выведена и обоснована Яо [74]. Понятно, что на основе этой формулы можно оценить и число блоков, обращения к которым потребуются при сканировании отношения через индекс для ограничения отношения в соответствии с предикатом с известной (оцененной ранее) селективностью.

Заметим, что и в этом подходе к оценке числа блоков с жестким разделением случаев кластеризованности отношения R по полю C и отсутствия такой кластеризованности проявляется некоторая ограниченность System R.


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



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