При выполнении запросов современные СУБД используют стоимостную модель оптимизации — на основе сохраненных в конфигурационных файлах коэффициентов и собранной статистики высчитывают “цену” получения и объем результирующих наборов строк. При повторном выполнении запросов стоимость и селективность высчитываются заново. Можно выполнить запрос и посмотреть реальные значения этих параметров, однако, в процессе (стандартного) повторного планирования оптимизатор СУБД эту информацию никак не использует.

А что, если бы оптимизатор сохранял реальные значения стоимости, селективности и другие необходимые параметры выполнения запроса и, при повторном его выполнении ориентировался не только на стандартную собранную статистику, но и на сохраненную после предыдущего выполнения?

Это называется адаптивная оптимизация запросов, и данный способ оптимизации является перспективным. В некоторых СУБД такие технологии уже используются.

Компания Postgres Professional уже несколько лет работает над расширением AQO для PostgreSQL, которое реализует (в некотором виде) адаптивную оптимизацию. Работы еще ведутся, но уже есть что потестировать.

Сначала — подробнее рассмотрим предметную область оптимизации запросов.

Почему планировщик может выбирать неоптимальный план

SQL-запрос можно выполнить по-разному. Например, когда происходит соединение двух таблиц, это можно сделать несколькими разными способами — с помощью вложенных циклов, слиянием, хешированием. Чем больше таблиц участвует в запросе — тем больше вариаций их соединений. Задача планировщика — выбрать план выполнения запроса с минимальной стоимостью из множества вариаций.

Как уже было сказано, при своей работе планировщики многих СУБД используют статистическую информацию, собираемую либо автоматически, либо вручную. Планировщик высчитывает ориентировочную стоимость на основе этой статистики.

В целом, планировщики современных СУБД в большинстве ситуаций работают хорошо. Однако, в некоторых случаях выбранный план может быть очень далёк от оптимальных.

Например, отсутствие актуальной статистической информации приводит к тому, что планировщик ориентируется при своей работе на (скорее всего) неверные данные о количестве строк в соединяемых таблицах. Излишнее занижение (или завышение) кардинальности приводит к выбору неоптимальных методов доступа к данным в таблицах.

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

Использование зависимых (коррелированных) условий тоже может негативно повлиять на работу СУБД. Планировщик (по умолчанию) считает, что все условия в запросе независимы друг от друга, то есть значение одного условия никак не влияет на другое. Это выполняется не всегда. Если используются зависимые условия (например, почтовый индекс и город), планировщик тоже будет высчитывать неправильную стоимость и кардинальность соединений.

На планировщик может влиять и использование функций в условиях. Функция для планировщика — это “черный ящик”, он не знает, сколько строк вернет функция, что также может приводить к ошибочной стоимости плана.

Способы влияния на работу планировщика

Актуальная статистика — непременное условие адекватной работы планировщика. Прежде всего убедитесь, что в системе настроен регулярный сбор статистической информации.

Есть несколько способов исправить вышеописанные ситуации и помочь планировщику выбирать более оптимальные планы выполнения запросов.

Без индексов у планировщика только один путь получить данные — последовательное сканирование таблицы (и это не всегда плохо и затратно). В некоторых случаях создание необходимых индексов помогает ускорить доступ к данным — не нужно сканировать всю таблицу. Но использование индексов (поиск необходимых, создание, поддержание в работе) — удовольствие не бесплатное. В идеале, их нужно использовать именно там, где нужно. А где не нужно — не использовать.

При использовании коррелированных условий соединений в запросах, можно сформировать расширенную статистику — явно “подсказать” оптимизатору, что условия связаны друг с другом. Для этого администратору базы данных (или разработчику) нужно хорошо знать свои данные и отслеживать зависимые условия в запросах, так как количество комбинаций зависимых столбцов заранее предугадать сложно. Расширенную статистику придется создавать вручную под каждый такой вариант.

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

Если ничего не помогает, можно вручную переписать запрос, например, используя материализованные представления, общие табличные выражения (Common Table Expressions, CTE). Либо уточнить требования предметной области и, возможно, кардинальным образом переписать логику запроса.

И есть еще один способ “подсказок” планировщику — адаптивная оптимизация запросов (adaptive query optimization). Идея этого метода в том, что после выполнения запроса реальная статистическая информация сохраняется и, при повторном выполнении данного (или подобного) запроса, оптимизатор может на нее опираться.

В СУБД Postgres Pro Enterprise есть расширение для адаптивной оптимизации запросов под названием AQO. Это расширение выложено на гитхабе: github.com/postgrespro/aqo, его можно попробовать и с ванильным PostgreSQL, об этом ниже.

Принцип работы модуля

Модуль AQO использует в работе машинное обучение. Более подробно про принцип работы можно прочитать в статье Олега Иванова Применение машинного обучения для увеличения производительности PostgreSQL и еще более подробно в презентации Адаптивная оптимизация запросов (доклад на YouTube).

Ниже кратко описана суть данного метода:

Для оценки стоимости планировщику нужна оценка кардинальности, а для нее, в свою очередь, нужна оценка селективности условий.

Для простых условий (таких, как «атрибут = константа» или «атрибут > константа») у планировщика есть модель, по которой он оценивает селективность. Для этого он пользуется статистической информацией: количеством уникальных значений атрибута, гистограммами и т.п.
Для условий, которые составлены из простых элементов с помощью логических связок, планировщик применяет легко вычисляемые формулы:

sel(not A) = 1 − sel(A)
sel(A and B) = sel(A) * sel(B)
sel(A or B) = sel( not(not A and not B) ) = 1 − (1 − sel(A)) * (1 − sel(B))

Эти формулы предполагают независимость (некоррелированность) условий A и B, из-за чего получаем неверные оценки в случае, когда это предположение нарушается.
AQO усложняет формулу: вводит для каждого простого условия свой собственный коэффициент. С помощью машинного обучения (используется регрессия методом ближайших соседей) AQO подбирает эти коэффициенты так, чтобы селективность, вычисленная по формуле, наилучшим образом соответствовала реальной селективности, которую AQO наблюдал ранее.

Для этого модулем сохраняется:

селективность простых условий, вычисленная штатным планировщиком;
реальная селективность условия по результатам выполнения запроса.

При своей работе AQO различает условия с точностью до констант. Это позволяет уменьшить сложность решаемой задачи, а кроме того — в большинстве случаев — информация все равно не теряется: AQO не «видит» значение константы, но зато «видит» селективность условия.
Ситуация, при которой потеря все-таки происходит, это условия, которые оцениваются константой вне зависимости от конкретных значений. Например, для некоторых условий планировщик не может сделать никаких разумных оценок и выбирает константу по умолчанию (например, селективность условия «выражение1 = выражение2» всегда оценивается как 0.005, а «выражение1 > выражение2» — как 1/3).

Таким образом AQO позволяет улучшить оценку селективности сложных условий (и, как следствие, оценку стоимости, что может приводить к выбору более адекватного плана выполнения).

Установка модуля

Чтобы попробовать функциональность модуля на ванильном PostgreSQL, необходимо использовать специальный патч, а затем собрать систему из исходного кода. Подробнее описано в файле README на github.

Если же используется Postgres Pro Enterprise, установка модуля AQO будет проходить в стандартном режиме:

shared_preload_libraries = 'aqo'

После этого можно создавать расширение в необходимой базе данных.

Подготовка базы данных

Рассмотрим конкретный пример работы модуля AQO в демонстрационной базе данных. Будем использовать базу большого размера, содержащую информацию о перелетах за год, с сентября 2016 по сентябрь 2017 года.

Сначала создадим расширение:

CREATE EXTENSION aqo;

Далее отключим параллельную обработку запросов — чтобы отображение параллельных планов не отвлекало от основной задачи:

max_parallel_workers_per_gather = 0;

Для того чтобы у планировщика PostgreSQL было больше вариантов соединения таблиц, создадим два индекса:

CREATE INDEX ON flights (scheduled_departure );
CREATE INDEX ON ticket_flights (fare_conditions );

При анализе результатов упор будем делать на значение BUFFERS как числа страниц, которое требуется прочитать для выполнения работы. На время выполнения тоже посмотрим (но время на нагруженной системе и на домашнем ноутбуке может сильно отличаться).

Увеличим буферный кеш и work_mem — чтобы вся работа осуществлялась в оперативной памяти:

shared_buffers = '256MB';

work_mem = '256MB';

Использование модуля AQO

Сформируем запрос: требуется получить пассажиров, которые летали бизнес-классом начиная с некоторой даты, причем прибыли с опозданием не более часа.
Выполним запрос без использования AQO (здесь и далее часть информации, не влияющая на понимание работы модуля, из планов удалена):

EXPLAIN (ANALYZE, BUFFERS, TIMING OFF) SELECT t.ticket_no
  FROM flights f
   	JOIN ticket_flights tf ON f.flight_id = tf.flight_id
   	JOIN tickets t ON tf.ticket_no = t.ticket_no
 WHERE f.scheduled_departure > '2017-08-01'::timestamptz
   AND f.actual_arrival < f.scheduled_arrival + interval '1 hour'
   AND tf.fare_conditions = 'Business';

И посмотрим получившийся план:

Nested Loop (rows=33210) (actual rows=31677)

  Buffers: shared hit=116830 read=1

  ->  Hash Join (rows=33210) (actual rows=31677)

        Hash Cond: (tf.flight_id = f.flight_id)

        ->  Index Scan ... on ticket_flights tf  

              Index Cond: fare_conditions = 'Business'

        ->  Hash

              ->  Bitmap Heap Scan on flights f (rows=8331) (actual rows=7673)

                    Recheck Cond: scheduled_departure > '2017-08-01'

                    Filter: actual_arrival < scheduled_arrival + '01:00:00'::interval

                    ->  Bitmap Index Scan on ... [flights]

                          Index Cond: scheduled_departure > '2017-08-01'

                          Buffers: shared hit=44 read=1

  ->   Index Only Scan  ... on tickets t (rows=1 width=14) (actual rows=1 loops=31677)

        Index Cond: (ticket_no = tf.ticket_no)

        Buffers: shared hit=106205

 Planning Time: 9.326 ms

 Execution Time: 675.836 ms

В данном случае планировщик посчитал оптимальным план, в котором сначала, с помощью сканирования по битовой карте (Bitmap Heap Scan on flights) получаем набор строк из таблицы flights, который соединяем путем хеширования (узел Hash Join) с набором строк из таблицы ticket_flights, полученных с помощью индексного сканирования (Index Scan ... on ticket_flights). Полученный результат будет использоваться как внешний набор набор строк для итогового соединения вложенным циклом (узел Nested Loop). Внутренний набор для этого соединения получается с помощью исключительного индексного сканирования таблицы tickets (Index Only Scan ... on tickets).
Самая “объемная” операция — получение внутреннего набора строк для Nested Loop — на неё читается 106 205 буферов.

Данный план можно назвать относительно хорошим, так как соединением вложенным циклом обрабатывается относительно небольшое число строк во внешнем наборе.

А теперь проведем эксперимент и посмотрим, как будет (или не будет) меняться предлагаемый план в зависимости от изменения дат в запросе. Даты подобраны таким образом, чтобы последовательно увеличить диапазон строк таблицы Flights удовлетворяющих условию, что приводит к ошибке планировщика в оценке кардинальности доступа к этой таблице. В плане выше видно, что с первой датой оптимизатор почти не ошибается в кардинальности (Bitmap Heap Scan on flights f (rows=8331) (actual rows=7673)).

Поочередно подставим в запрос следующие даты:

2017-04-01
2017-01-01
2016-08-01

И посмотрим результат:

Планы запросов без AQO

Дата 2017-04-01

Nested Loop (rows=31677) (actual rows=292392)
  Buffers: shared hit=991756
  ->  Hash Join (rows=31677) (actual rows=292392)
        Hash Cond: (tf.flight_id = f.flight_id)
        ->  Index Scan … on ticket_flights tf
              Index Cond: fare_conditions = 'Business')
        ->  Hash
              ->  Bitmap Heap Scan on flights f (rows=7673) (actual rows=70553)
                    Recheck Cond: scheduled_departure > '2017-04-01'
                    Filter: actual_arrival < (scheduled_arrival + '01:00:00'::interval)
                    ->  Bitmap Index Scan on ... [flights]
                          Index Cond: scheduled_departure > '2017-04-01'
                          Buffers: shared hit=160
  ->  Index Only Scan ... on tickets t ( rows=1 width=14) (actual rows=1 loops=292392)
        Index Cond: (ticket_no = tf.ticket_no)
        Buffers: shared hit=980995
Planning Time: 5.980 ms
Execution Time: 2771.563 ms

За счет уменьшения даты, увеличивается объем выборок из базы данных. Но структура плана осталась той же самой. Планировщик, за счет ошибки в кардинальности (Bitmap Heap Scan on flights f (rows=7673) (actual rows=70553)), считает, что наиболее оптимальным соединением получившихся наборов строк будет Nested Loop, хотя реальное количество строк в наборах в несколько раз больше, чем было в первый раз.

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

Дата 2017-01-01

Nested Loop (rows=187710) (actual rows=484569)
  Buffers: shared hit=1640723 read=49
  ->  Hash Join (rows=187738) (actual rows=484569)
        Hash Cond: (tf.flight_id = f.flight_id)
        ->  Index Scan ... on ticket_flights tf
              Index Cond: fare_conditions = 'Business'
        ->  Hash
              ->  Seq Scan on flights f (rows=45352) (actual rows=116985)
                    Filter: scheduled_departure > '2017-01-01'::date
                              AND actual_arrival < scheduled_arrival + '01:00:00'::interval
  ->  Index Only Scan ... on tickets t (rows=1) (actual rows=1 loops=484569)
        Index Cond: (ticket_no = tf.ticket_no)
        Buffers: shared hit=1630118 read=49
Planning Time: 6.225 ms
Execution Time: 4498.741 ms

У оптимизатора всё еще есть расхождения между плановой и реальной кардинальностью, но план продолжает быть почти идентичным предыдущему. В нём поменялся только метод доступа к таблице flights, теперь (даже при наличии ошибки) используется последовательное сканирование всей таблицы.
Работа по обработке таблицы tickets еще больше увеличилась — до более чем полутора миллионов буферов (1 630 118).

Дата 2016-08-01

Hash Join (rows=302200) (actual rows=771441)
   Hash Cond: (t.ticket_no = tf.ticket_no)
   Buffers: shared hit=25499 read=34643
   ->  Seq Scan on tickets t (rows=2949857) (actual rows=2949857)
   ->  Hash
         ->  Hash Join (rows=302236) (actual rows=771441)
               Hash Cond: (tf.flight_id = f.flight_id)
               ->  Index Scan on ticket_flights tf
                     Index Cond: fare_conditions = 'Business'
               ->  Hash
                     ->  Seq Scan on flights f (rows=73005) (actual rows=188563)
                           Filter: scheduled_departure > '2016-08-01'::date)
                                     AND actual_arrival < scheduled_arrival + '01:00:00'::interval
Planning Time: 9.990 ms
Execution Time: 3014.577 ms

И снова есть разница между плановой и реальной кардинальностью наборов строк ((rows=302236) (actual rows=771441)). Но, даже с этой разницей, оптимизатор выбрал более эффективный план: Hash Join вместо Nested Loop.

Если собрать краткий итог, без использования модуля AQO планировщик отрабатывает следующим образом:

Дата	Буферы	Время, мс	Комментарий
2017-08-01	116 831	675.836	Используется соединения nested loop и hash join, таблицы Flights и Tickets сканируются по индексу
2017-04-01	991 756	2771.563	Тот же план, но неоптимальный. При выборе доступа по индексу для таблиц Flights и Tickets видно, что планировщик сильно ошибается при расчете кардинальности
2017-01-01	1 640 772	4498.741	Всё тот же неоптимальный план. Но планировщик решает перейти на последовательное сканирование таблицы Flights
2016-08-01	60 142	3014.577	План наконец-то поменялся — оптимизатор понимает, что придется выбрать много строк из таблиц, поэтому переходит на последовательное сканирование таблиц Flights и Tickets. Неэффективный (в данном случае) nested loop заменяет на hash join.

Планы запросов с AQO

Теперь подключим AQO. Запускаем режим обучения:

SET aqo.mode = 'learn';

И снова последовательно выполняем те же четыре запроса, которые были выше:

Дата 2017-08-01

План запроса будет абсолютно таким же, как и запрос с той же датой, но без использования модуля. AQO пока еще обучается.

Дата 2017-04-01

Hash Join (rows=293891) (actual rows=292392)
  Hash Cond: (t.ticket_no = tf.ticket_no)
  Buffers: shared hit=25658 read=34640
  ->  Seq Scan on tickets t  (rows=2949857) (actual rows=2949857)
  ->  Hash
        ->  Hash Join  (rows=293734) (actual rows=292392)
              Hash Cond: (tf.flight_id = f.flight_id)
              ->  Index Scan ... on ticket_flights tf
                    Index Cond: (fare_conditions)::text = 'Business'::text
              ->  Hash
                    ->  Bitmap Heap Scan on flights f
                          Recheck Cond: scheduled_departure > '2017-04-01'::date
                          Filter: actual_arrival < scheduled_arrival + '01:00:00'::interval
                          ->  Bitmap Index Scan on ... [flights]
                                Index Cond: scheduled_departure > '2017-04-01'::date
                                Buffers: shared hit=160
Planning Time: 9.652 ms
Execution Time: 2218.074 ms

Уже на второй “проход”, подсказки модуля AQO кардинально повлияли на выполнение запроса — вместо соединения вложенным циклом используется соединение хешированием. В качестве метода доступа к таблице Tickets используется последовательный доступ. Кардинальность соединений рассчитаны близко к реальным. Количество прочитанных буферов примерно равно тому количеству, которое было прочитано при использовании удовлетворительного плана в последней итерации эксперимента без использования модуля AQO.

Дата 2017-01-01

Hash Join  (rows=484452) (actual rows=484569)
  Hash Cond: (t.ticket_no = tf.ticket_no)
  Buffers: shared hit=25534 read=34608
  ->  Seq Scan on tickets t (rows=2949857) (actual rows=2949857)
  ->  Hash (rows=484464) (actual rows=484569)
        ->  Hash Join (rows=484464) (actual rows=484569)
              Hash Cond: (tf.flight_id = f.flight_id)
              ->  Index Scan ... on ticket_flights tf
                    Index Cond: fare_conditions::text = 'Business'::text
              ->  Hash
                    ->  Seq Scan on flights f (rows=116971) (actual rows=116985)
                          Filter: scheduled_departure > '2017-01-01'::date
                                    AND actual_arrival < scheduled_arrival + '01:00:00'::interval
Planning Time: 6.264 ms
Execution Time: 2746.485 ms

В данном случае план почти не изменился — вместо сканирования таблицы Flights по битовой карте используется последовательный доступ.

Дата 2016-08-01

А тут план совсем не изменился.

Снова посмотрим на результат:

Дата	Буферы	Время, мс	Комментарий
2017-08-01	116 831	662.966	План такой же, как и без использования модуля
2017-04-01	60 298	2218.074	С помощью подсказок модуля, оптимизатор понимает, что планируется соединение большого количества строк, и уже на этом шаге улучшает план путём замены nested loop на hash join
2017-01-01	60 142	2746.485	План ещё немного улучшился — вместо доступа по битовой карте к таблице flights используется её последовательное сканирование
2016-08-01	60 142	3253.861	План остался без изменений — лучший план в данном случае

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

Подведем итог

У использования модуля AQO для адаптивной оптимизации запросов есть как достоинства, так и недостатки.

Одним из достоинств использования модуля является то, что не обязательно отслеживать зависимые условия в запросах. В некоторых случаях скорость выполнения запросов может вырасти. И есть различные режимы использования модуля. Например, можно использовать AQO для оптимизации только определенных типов запросов.

Из недостатков модуля можно выделить дополнительные накладные расходы на обучение и сохранение статистики в структурах модуля. И собранная модулем статистическая информация не передается на реплики.

Модуль AQO не является “серебряной пулей” от всех возможных проблем планировщика. Например, в некоторых ситуациях модуль может заменить расширенную статистику (если её не создавать руками), или не будет обращать внимания на неактуальную статистику. А вот необходимые индексы модуль не создаст и, тем более, не перепишет текст запроса.

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

AQO — адаптивная оптимизация запросов в PostgreSQL