Планировщик/Оптимизатор

Задача планировщика/оптимизатора - создать оптимальный план выполнения. Заданный SQL-запрос (и, следовательно, дерево запросов) может быть фактически выполнен множеством различных способов, каждый из которых приведет к одному и тому же набору результатов. Если это осуществимо с вычислительной точки зрения, оптимизатор запросов рассмотрит каждый из этих возможных планов выполнения, в конечном итоге выбрав тот план выполнения, который, как ожидается, будет работать быстрее всего.

Примечание

В некоторых ситуациях изучение всех возможных способов выполнения запроса займет слишком много времени и памяти. В частности, это происходит при выполнении запросов с большим количеством операций соединения. Чтобы определить разумный (не обязательно оптимальный) план запроса в разумное время, PostgreSQL использует генетический оптимизатор запросов (см. раздел «Генетический оптимизатор запросов»), когда количество соединений превышает пороговое значение)

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

Генерация возможных планов

Планировщик/оптимизатор начинает с генерации планов сканирования каждого отдельного отношения (таблицы), используемого в запросе. Возможные планы определяются доступными индексами для каждого отношения. Всегда есть возможность выполнить последовательное сканирование отношения, поэтому всегда создается план последовательного сканирования. Предположим, что на отношении определен индекс (например, индекс B-дерева), а запрос содержит ограничение relation.attribute OPR constant. Если relation.attribute совпадает с ключом индекса B-дерева и OPR является одним из операторов, перечисленных в классе операторов индекса, создается другой план сканирования отношения с использованием индекса B-дерева. Если присутствуют другие индексы и ограничения в запросе совпадают с ключом индекса, будут рассмотрены дальнейшие планы. Планы сканирования индексов также создаются для индексов, имеющих порядок сортировки, который может соответствовать предложению ORDER BY запроса (если таковое имеется), или порядок сортировки, который может быть полезен для объединения (см. ниже).

Если запрос требует объединения двух или более отношений, планы объединения отношений рассматриваются после того, как найдены все выполнимые планы для сканирования отдельных отношений. Доступны три стратегии объединения:

• Вложенный цикл join – правое отношение сканируется один раз для каждой строки, найденной в левом отношении. Эта стратегия проста в реализации, но может отнимать много времени. (Однако если правое отношение можно просканировать с помощью индексного сканирования, это может быть хорошей стратегией. Можно использовать значения из текущей строки левого отношения в качестве ключей для индексного сканирования правого).
• Объединение слиянием – перед началом объединения каждое отношение сортируется по атрибутам объединения. Затем два отношения сканируются параллельно, и совпадающие строки объединяются в строки соединения. Этот вид объединения привлекателен тем, что каждое отношение нужно просканировать только один раз. Требуемая сортировка может быть достигнута либо с помощью явного шага сортировки, либо путем сканирования отношения в нужном порядке с использованием индекса по ключу соединения.
• Хэш-соединение – сначала сканируется правое отношение и загружается в хэш-таблицу, используя его атрибуты присоединения в качестве хэш-ключей. Затем сканируется левое отношение, и соответствующие значения каждой найденной строки используются как хэш-ключи для нахождения совпадающих строк в таблице.

Если запрос включает более двух отношений, конечный результат должен быть построен в виде дерева шагов объединения, каждый из которых имеет два входа. Планировщик рассматривает различные возможные последовательности соединений, чтобы найти самую дешевую.

Если в запросе используется меньше, чем geqo_threshold отношений, то для поиска наилучшей последовательности соединений выполняется почти исчерпывающий поиск. Планировщик предпочтительно рассматривает соединения между любыми двумя отношениями, для которых существует соответствующее условие соединения в квалификации WHERE (т.е. для которых существует ограничение типа where rel1.attr1=rel2.attr2). Пары соединений без оговорок рассматриваются только тогда, когда нет другого выбора, то есть у конкретного отношения нет доступных оговорок соединения с любым другим отношением. Для каждой пары соединений, рассматриваемой планировщиком, генерируются все возможные планы, и выбирается тот, который является (по оценкам) самым дешевым.

Если порог geqo_threshold превышен, рассматриваемые последовательности соединений определяются с помощью эвристики, как описано в разделе «Генетический оптимизатор запросов». В остальном процесс не меняется.

Готовое дерево плана состоит из последовательного или индексного сканирования базовых отношений, а также узлов вложенного цикла, слияния или хэш-соединения, если это необходимо, и всех необходимых вспомогательных шагов, таких как узлы сортировки или вычисления функции aggre- gate-function. Большинство из этих типов узлов плана имеют дополнительную возможность выполнять селекцию (отбрасывание строк, не удовлетворяющих заданному булеву условию) и проекцию (вычисление производного набора столбцов на основе заданных значений столбцов, то есть оценка скалярных выражений, где это необходимо). Одна из обязанностей планировщика - прикреплять условия отбора из предложения WHERE и вычисления необходимых выходных выражений к наиболее подходящим узлам дерева плана.