A JOIN (B JOIN C)

(A JOIN C) JOIN B

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

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

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

• число строк в таблице;
• интервал и распределение значений данной колонки;
• длину строки и, соответственно, число строк на физической странице диска;
• высоту индекса;
• число терминальных (leaf) страниц в индексе.

Эти характеристики данных могут сильно влиять на эффективность обработки запроса. Использование таких характеристик приводит к следующему типу оптимизации.