Классика баз данных - статьи

       

R для запросов над одиночными


Описан выбор путей доступа в System R для запросов над одиночными таблицами, соединений и вложенных запросов. Ведется работа по сравнению выбираемых вариантов с "правильными", результаты будут описаны в будущей статье. Предварительные результаты показывают, что хотя стоимости, предсказываемые оптимизатором, часто бывают неточны в абсолютном измерении, в подавляющем большинстве случаев выбирается действительно оптимальный план. Во многих случаях соотношения между оцененными стоимостями для всех рассмотренных планов являются в точности теми же, что и соотношения между реально измеренными стоимостями.
Кроме того, стоимость выбора пути не является непомерной. Для соединения двух отношений стоимость оптимизации приблизительно эквивалентна стоимости 5-20 выборок из базы данных. Это число становится еще более незначительным, когда выбор пути доступа производится в среде, подобной System R, где единожды скомпилированные прикладные программы выполняются многократно. Стоимость оптимизации окупается многократным выполнением.
Основной новый вклад данной работы над компонентом выбора путей доступа состоит в расширенном использовании статистики (например, мощности индексов), включении загрузки ЦП в оценочные формулы и разработке метода определения порядка соединений. Многие запросы ограничиваются возможностями ЦП, в частности, соединения слиянием, для которых создаются временные отношения и производится сортировка. Понятие "коэффициента селективности" позволяет оптимизатору использовать как можно большее число предикатов в аргументах поиска RSS и путях доступа. При запоминании классов эквивалентности "интересного упорядочивания" для соединений и спецификаций ORDER или GROUP оптимизатор учитывает больше информации, чем другие аналогичные программы, но во многих случаях эта дополнительная работа позволяет избежать сохранения и сортировки промежуточных результатов запроса. Методы обрезания дерева и поиска в дереве позволяют эффективно выполнять этот дополнительный учет. Требуется дополнительная работа по валидации оценочных формул оптимизатора, но из нашей предварительной работы мы можем заключить, что в системах управления базами данных могут поддерживаться непроцедурные языки запросов с эффективностью, сравнимой с той, которая поддерживается для современных более процедурных языков.

Содержание  Назад  Вперед