Руководство по созданию эффективных запросов

 

определение возможных порядков операций;
 

определение возможных алгоритмов выполнения для каждой опе-
рации;
 

сравнение стоимости разных планов;
 

выбор оптимального плана выполнения.
Многие разработчики SQL предполагают, что PostgreSQL выполняет за-
просы, обращаясь к таблицам в том порядке, в котором они указаны в пред-
ложении 
FROM
, и соединяя их в том же самом порядке.
Однако в большинстве случаев порядок соединений 
не
сохраняется. В сле-
дующих главах мы более подробно обсудим, что влияет на порядок операций, 
а пока посмотрим, как оценить план выполнения.
Почему планов выполнения так много?
Мы несколько раз отмечали, что одна инструкция SQL может выполняться 
разными способами, используя разные планы исполнения. На самом деле 
могут быть сотни, тысячи или даже миллионы возможных способов выпол-
нения одной команды! Эта глава дает представление о том, откуда берутся 
эти цифры. Планы могут отличаться:

---

Планы выполнения 

63
 

порядком операций;
 

алгоритмами, используемыми для соединений и других операций (та-
кими как вложенные циклы или соединение хешированием);
 

методами получения данных (такими как индексный доступ или пол-
ное сканирование).
Говоря формально, оптимизатор находит лучший план, вычисляя стоимо-
сти всех возможных планов, а затем сравнивая их. Но поскольку мы знаем, 
что для выполнения каждого соединения есть три основных алгоритма, даже 
простой запрос из трех таблиц порождает девять возможных планов вы-
полнения; учитывая 12 возможных порядков соединения, это дает 108 воз-
можных планов (3 × 3 × 12 = 108). А если мы учтем все возможные методы 
извлечения данных для каждой таблицы, то количество планов увеличится 
до нескольких тысяч.
К счастью, PostgreSQL не проверяет все возможные планы.
Алгоритм оптимизации основан на принципе оптимальности: поддерево 
оптимального плана оптимально для соответствующего подзапроса. План 
можно рассматривать как композицию из нескольких составных частей или 
поддеревьев. Поддерево плана – это план, который включает в себя некоторую 
операцию исходного плана в качестве корневого узла и все ее дочерние узлы, 
то есть все операции, которые являются аргументами операции, выбранной 
в качестве корня поддерева. Оптимизатор строит оптимальный план, на-
чиная с самых маленьких поддеревьев (то есть с доступа к отдельным табли-
цам), и постепенно создает более сложные поддеревья, включающие больше 
операций, выполняя на каждом шаге лишь несколько сравнений стоимости. 
Алгоритм является исчерпывающим: он строит оптимальный план, несмотря 
на то что значительная часть возможных планов не рассматривается.
Например, в предыдущем примере, как только оптимизатор выберет пра-
вильный алгоритм извлечения данных для одной из трех таблиц, он не будет 
рассматривать планы, которые не используют этот оптимальный алгоритм.
Тем не менее количество рассмотренных планов может быть огромным. 
Эвристики исключают те части пространства планов, которые вряд ли будут 
содержать оптимальные планы, уменьшая тем самым количество прове-
ряемых вариантов. Хотя это и помогает оптимизатору быстрее выбирать 
план выполнения, но может отрицательно сказаться на производительности: 
существует риск, что самый подходящий план выполнения будет случайно 
исключен перед сравнением стоимостей.
Хотя эвристики и могут исключить оптимальный план, алгоритм строит 
лучший план из оставшихся.
Теперь рассмотрим подробнее, как рассчитываются стоимости.