Оптимизация, основанная на правилах

Операции соединения подчиняются как коммутативному, так и ассоциативному закону. Следовательно, теоретически возможно выполнять соединение в любом порядке.

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

Одним из первых подходов на пути борьбы с комбинаторной сложностью выполнения соединений состоит в установлении эвристических правил для выбора между путями доступа и методами соединений, которая называется оптимизацией, основанной на правилах (rule-based optimization). В этом подходе веса и предпочтения назначаются альтернативам на основе принципов, которые являются общепризнанными. Используя эти веса и предпочтения, оптимизатор запросов производит возможные планы выполнения до тех пор, пока не будет достигнут лучший план выполнения, удовлетворяющий этим правилам.

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

• число строк в таблице;

• интервал и распределение значений данной колонки;

• длину строки и, соответственно, число строк на физической странице диска;

• высоту индекса;

• число терминальных (leaf) страниц в индексе.

Оптимизация, основанная на вычислении стоимости

Оптимизация, основанная на вычислении стоимости запроса (cost-based optimization), аналогична оптимизации, основанной на правилах, за исключением того, что оптимизатор на основе вычисления стоимости использует статистическую информацию для выбора наиболее эффективного плана выполнения запроса. Стоимость каждого альтернативного плана выполнения запроса оценивается с помощью статистики, такой как число строк в таблице и числа и распределения значений колонки таблицы. Формулы стоимости обычно учитывают количество ввода/вывода и время CPU, необходимое для выполнения плана запроса. Такая статистика хранится в системном каталоге и поддерживается СУБД.