50.5. Планировщик/Оптимизатор#
50.5. Планировщик/Оптимизатор
Задача планировщика/оптимизатора состоит в создании оптимального плана выполнения. Заданный SQL-запрос (и, следовательно, дерево запроса) может быть выполнен на самом деле во множестве различных способов, каждый из которых будет производить одинаковый набор результатов. Если это вычислительно возможно, оптимизатор запросов будет рассматривать каждый из этих возможных планов выполнения, в конечном итоге выбирая план выполнения, который ожидается будет выполняться быстрее.
Примечание
В некоторых ситуациях анализ каждого возможного способа выполнения запроса может занять слишком много времени и памяти. Это особенно проявляется при выполнении запросов, включающих большое количество операций соединения. Чтобы определить разумный (не обязательно оптимальный) план запроса за разумное время, Tantor SE использует Генетический оптимизатор запросов (см. Глава 60) при превышении порога количества соединений (см. geqo_threshold).
Процедура поиска планировщика фактически работает с структурами данных, называемыми путями, которые являются упрощенными представлениями планов, содержащими только ту информацию, которая необходима планировщику для принятия решений. После определения самого дешевого пути строится полноценное дерево планов, которое передается исполнителю. Оно представляет собой желаемый план выполнения с достаточной детализацией для исполнителя, чтобы он мог его выполнить. В остальной части этого раздела мы будем игнорировать различие между путями и планами.
50.5.1. Генерация возможных планов
Планировщик/оптимизатор начинает с генерации планов для сканирования каждого отдельного отношения (таблицы), используемого в запросе. Возможные планы определяются доступными индексами на каждом отношении. Всегда есть возможность выполнить последовательное сканирование отношения, поэтому всегда создается план последовательного сканирования. Предположим, что на отношении (например, на B-дереве) определен индекс, и запрос содержит ограничение relation.attribute OPR constant. Если relation.attribute случайно совпадает с ключом B-дерева индекса, а OPR является одним из операторов, перечисленных в классе операторов индекса, создается еще один план, использующий индекс B-дерева для сканирования отношения. Если имеются дополнительные индексы и ограничения в запросе случайно совпадают с ключом индекса, рассматриваются дополнительные планы. Планы сканирования индекса также генерируются для индексов, у которых есть порядок сортировки, который может соответствовать ORDER BY запроса (если есть), или порядок сортировки, который может быть полезен для соединения слиянием (см. ниже).
Если запрос требует соединения двух или более отношений, планы для соединения отношений рассматриваются после того, как найдены все возможные планы для сканирования отдельных отношений. Три доступные стратегии соединения:
Вложенное соединение циклом: Правая таблица сканируется один раз для каждой найденной строки в левой таблице. Эта стратегия легко реализуется, но может занимать много времени. (Однако, если правую таблицу можно просканировать с помощью индексного сканирования, это может быть хорошей стратегией. Возможно использование значений из текущей строки левой таблицы в качестве ключей для индексного сканирования правой).
соединение слиянием: Каждое отношение сортируется по атрибутам соединения перед началом соединения. Затем два отношения сканируются параллельно, и совпадающие строки объединяются для формирования строк соединения. Такое соединение привлекательно, потому что каждое отношение должно быть просканировано только один раз. Необходимая сортировка может быть достигнута либо с помощью явного шага сортировки, либо путем сканирования отношения в правильном порядке с использованием индекса на ключе соединения.
Hash join: правое отношение сначала сканируется и загружается в хеш-таблицу, используя свои атрибуты соединения в качестве ключей хеша. Затем левое отношение сканируется и подходящие значения каждой найденной строки используются в качестве ключей хеша для поиска соответствующих строк в таблице.
Когда запрос включает более двух отношений, конечный результат должен быть построен в виде дерева шагов соединения, каждый из которых имеет два входа. Планировщик рассматривает различные возможные последовательности соединения, чтобы найти самую дешевую.
Если запрос использует меньше, чем geqo_threshold отношений, выполняется почти исчерпывающий поиск для нахождения наилучшей последовательности соединений. Планировщик предпочтительно рассматривает соединения между любыми двумя отношениями, для которых существует соответствующая условная конструкция соединения в квалификации WHERE (т.е. для которых существует ограничение вида where rel1.attr1=rel2.attr2). Пары соединений без условной конструкции рассматриваются только в случае отсутствия других вариантов, то есть когда определенное отношение не имеет доступных условных конструкций соединения с другими отношениями. Для каждой пары соединений, рассматриваемой планировщиком, генерируются все возможные планы, и выбирается (предполагаемо) самый дешевый.
Когда превышается значение geqo_threshold, рассматриваемые последовательности соединений определяются эвристиескими алгоритмами как описанные в разделе Глава 60. В остальных случаях процесс остается тем же.
Дерево готового плана состоит из последовательных или индексных сканирований базовых отношений, а также узлов вложенных циклов, соединений слиянием или по хешу при необходимости, а также любых вспомогательных шагов, таких как узлы сортировки или вычисления агрегатных функций. Большинство этих типов узлов плана имеют дополнительную возможность выполнения отбора (отбрасывание строк, не удовлетворяющих заданному логическому условию) и проекции (вычисление набора производных столбцов на основе заданных значений столбцов, то есть вычисление скалярных выражений при необходимости). Одной из обязанностей планировщика является присоединение условий отбора из предложения WHERE и вычисление требуемых выходных выражений к наиболее подходящим узлам дерева плана.