Компания Postgres Professional занимается разработкой и поддержкой СУБД с 2015 года. Это серьёзный срок для компании в ИТ-сфере, и за это время мы видели много случаев, когда клиенты сталкивались с неоптимальным выполнением запросов. Обычно оптимизатор PostgreSQL неплохо справляется и строит хорошие планы, если количества джойнов в запросе не больше 10 и данные в таблицах распределены равномерно. Однако в даже на изначально тщательно продуманной базе данных, оптимизатор может сгенерировать настолько неоптимальный план, что его время выполнения увеличится в разы. В некоторых особо экстремальных случаях будет практически невозможно дождаться окончания выполнения запроса и понять при помощи EXPLAIN ANALYZE, что пошло не так. Усугубляющим фактором является то, что оптимизатор PostgreSQL никак не запоминает допущенные ошибки выполнения. Построив неоптимальный план один раз, он с большой долей вероятности будет делать это снова и снова до тех пор, пока что-то не изменится: статистика, настройки оптимизатора или какое-то внутреннее состояние СУБД.

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

На протяжении своего существования наша компания пытается отвечать на эти вызовы, для чего, например, были разработаны расширения AQO и sr_plan. Сообщество PostgreSQL также не стоит на месте: в ванильной версии появилась расширенная статистика и был введён ряд оптимизаций вроде инкрементальной сортировки и материализации промежуточных результатов выполнения запроса.

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

Зачем

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

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

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

Предположим, что раз в секунду создается новый конвейер (pipeline) с 5 задачами и после выполнения задачи (40 мс) она меняет свой статус с “NEW” на “COMPLETE”. Раз в 200 мс происходит проверка сколько заданий и конвейеров осталось.

SELECT t.id, p.id
  FROM tasks t,
             pipeline p 
  WHERE t.status = 'NEW'
    AND t.pipeline_id = p.id
    AND p.status = 'STARTED'
  ORDER BY p.creation_time, t.id
  LIMIT 1 FOR UPDATE OF t SKIP LOCKED;

Так как данных немного, в текущей ситуации достаточно плана запроса содержащего Nested Loop:

---------------------------------------------------
Limit  (cost=4.08..4.09 rows=1 width=36)                                                                                   
  ->  LockRows  (cost=4.08..4.09 rows=1 width=36)                                                                          
        ->  Sort  (cost=4.08..4.08 rows=1 width=36)                                                                        
              Sort Key: p.creation_time, t.id                                                                              
              ->  Nested Loop  (cost=0.86..4.07 rows=1 width=36)                                                           
                    Join Filter: (t.pipeline_id = p.id)                                                                    
                    ->  Index Scan using pipeline_status_creation_time_idx on pipeline p  (cost=0.42..2.02 rows=1 width=22)
                          Index Cond: (status = 'STARTED'::text)                                                           
                    ->  Index Scan using tasks_status_creation_time_idx on tasks t  (cost=0.43..2.03 rows=1 width=22)      
                          Index Cond: (status = 'NEW'::text)   

Но учитывая, что количество заданий может появляться неравномерно, представим такую ситуацию, когда конвейеров приходит слишком много (5000), в каждом из которых 5 задач. То есть в совокупности у нас 25000 задач. С такой нагрузкой автовакуум не успевает закончить работу и обновить статистику, которая показала бы планировщику, что данных в таблице теперь уже очень много по сравнению с предыдущим разами, поэтому ранее выбранный план запроса уже не подходит для выполнения и нужно применить другой алгоритм -  Hash Join:

---------------------------------------------------
Sort Method: external merge  Disk: 784kB
   ->  Hash Join  (cost=57.42..104.91 rows=21978 width=24) (actual time=4.528..27.889 rows=23276 loops=1)
         Hash Cond: (t.pipeline_id = p.id)
         ->  Index Scan using tasks_status_creation_time_idx on tasks t  (cost=0.43..2.03 rows=17483 width=16) (actual time=0.045..9.327 rows=23276 loops=1)
               Index Cond: (status = 'NEW'::text)
          ->  Hash  (cost=2.02..2.02 rows=4397 width=16) (actual time=4.465..4.466 rows=4656 loops=1)
               ->  Index Scan using pipeline_status_creation_time_idx on pipeline p  (cost=0.42..2.02 rows=4397 width=16) (actual time=0.035..2.816 rows=4656 loops=1)
                     Index Cond: (status = 'STARTED'::text)

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

Как устроен оптимизатор

Довольно много статей было написано о том, как работает оптимизатор и какой механизм лежит в основе подбора оптимального плана запроса. Если обобщенно, то стоимость плана можно рассматривать как совокупную стоимость его частей. А точнее, сумму отдельных инструкций, которые должны быть исполнены при выполнении запроса. Инструкцию можно рассматривать как операцию, которая содержит определенный алгоритм. Например, в основе чтения таблицы лежит алгоритм последовательного чтения файлов (страниц таблицы), которые содержат данные. Или операция индексного чтения может содержать группу алгоритмов, таких как index-only-scan. Поэтому выбор оптимального алгоритма для выполнения инструкции состоит в  выборе алгоритма с минимальной стоимостью.

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

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

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

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

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

Сначала происходит разбор синтаксический и семантический, который выполняет Parser. Текст запроса разбивается на лексемы, затем Analyzer проверяет, что эти лексемы входят в состав языка, и получаем сформированное дерево разбора. Это дерево передается на Rewriter и запрос может быть переписан. Например, может быть добавлен текст представления или другое дополнение в дерево разбора. Оптимизатор получает итоговое дерево разбора, и наконец наступает процесс создания плана выполнения запроса.

Больше всего нас будет интересовать данная часть схемы:

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

Чем больше таблиц в запросе — тем более глубокое дерево будет получаться. Однако рассматриваться будут комбинации соединений между таблицами и соединениями, находящиеся на одном уровне в дереве разбора. Сколько элементов будет рассматриваться для формирования комбинаций соединений регулируется параметром join_collapse_limit (для соединений) и from_collapse_limit (для таблиц). То есть изначально структура дерева будет состоять из join_collapse_limit таблиц на нижнем уровне и из join collapse limit-1 соединений на уровнях выше.

Оптимизатор выравнивает в одну плоскость дерево разбора снизу-вверх. Но  выравнивание происходит только в том случае, если в списке будет не больше join_collapse_limit элементов. Об этом можно почитать подробнее в ранее упоминавшейся статье.

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

Стоимость узла зависит от его типа и объема обрабатываемых им данных. Тип нам известен, а для оценки объема данных необходимо оценить кардинальность (количество строк) входных наборов данных и селективность (долю строк, которая останется на выходе) данного узла. То есть кардинальностью в результате работы узла является произведение селективности на максимально возможное количество строк. Максимально возможное количество строк — это декартово произведение для соединений между таблицами. Или количество строк всей таблицы, если рассматриваем ноду сканирования. Для подсчета кардинальности оптимизатору надо иметь статистическую информацию о данных: размер таблиц, распределение данных по столбцам. Эту информацию оптимизатор может получить из статистики, которая может быть представлена как Most Common Values (MCV), так и гистограммой. Подробнее про статистику можно почитать в этой статье.

Используя полученное значение кардинальности, оптимизатор предсказывает стоимость выполнения ноды. Под стоимостью можно понимать затраты CPU на выполнение алгоритма. Причём для каждого алгоритма существует свой метод оценки его стоимости — для Nested Loop нас интересует, сколько ресурсов компьютера будет потрачено на выполнение вложенного цикла, а, например, для Hash Join нам нужно учитывать, сколько потребуется памяти на построение хеш-таблицы.

Если в каждом узле плана кардинальность оценена верно, то и общая стоимость обычно адекватно отражает реальные затраты. Основные ошибки планировщика связаны именно с неправильной оценкой кардинальностей и селективностей. Если кардинальность, используемая планировщиком, была ниже, чем на самом деле, то оптимизатор предпочтет более щадящий алгоритм, по его мнению, который  будет к тому же дешевле по сравнению с Hash Join или Merge Join. Потому в данном примере, оптимизатор предпочтет выбрать Nested Loop. В обратной ситуации, когда данных намного меньше ожидаемого, оптимизатор использует более затратный алгоритм. Может еще и воркеров дополнительных подключить для ускорения, что в результате приведет к тому, что ресурсы были потрачены впустую. А то и еще хуже, если в это время кто-то запускает свои запросы и они исполняются значительно медленнее.

Итак, вроде бы понятно, что мы имеем проблемы из-за неправильно рассчитанной кардинальности, но почему это происходит? Строго говоря, для этого довольно много причин. Особенно подробно они расписаны в этой и этой статьях. Но одна из самых популярных — это использование устаревшей статистики, когда автовакуум не успевает пройти вовремя для очистки страниц таблиц и обновить статистики по ним. Второй причиной обычно становится наличие неравномерного распределения в данных. К сожалению, оптимизатор верит, что все данные в таблице распределены равномерно и они независимы между собой, что зачастую далеко от реальности. 

С этим можно бороться, например, уточняя статистику по таблице с помощью расширенной статистики или используя сторонние расширения. Более глубоко можно копнуть в этой статье. Есть довольно много инструментов разработанных в нашей компании, которые неплохо справляются с этой проблемой. Один из них, Adaptive Query Optimization (AQO), запоминает кардинальности для каждой ноды и передает их оптимизатору для генерации плана запроса при следующем исполнении. 

В основе AQO лежит алгоритм k-ближайших соседей, который позволяет учиться оптимизатору на своих ошибках, если кардинальность при вычислении плана была выбрана или предсказана оптимизатором некорректно. Для каждой вершины плана доля всех отобранных кортежей по отношению ко всем обработанным кортежам называется выборочностью (selectivity) — это определение нам пригодится в дальнейшем, поскольку оно очень сильно связано с тем, как рассчитывается кардинальность и лежит в основе многих функциональностей улучшающих кардинальность. На текущем этапе пока отметим, что для получения количества кортежей, отбираемых вершиной, достаточно умножить выборочность вершины на количество обрабатываемых кортежей (например, для SeqScan'а это будет количество записей в таблице).

Наблюдаемыми признаками нод плана являются маргинальные выборочности (логарифм selectivity) всех условий для ноды — они записываются в виде вектора в таблице знаний AQO. Заметим: для маргинальности важно, что условия, отличающиеся только в константах, считаются эквивалентными между собой. Решается задача регрессии: требуется предсказать кардинальность для ноды, причем из таблицы AQO выбирается информация о всех похожих нодах. А решение о похожести принимается через расстояние между вектором селективности ноды, для которой делается предсказание, и всеми имеющимися в таблице знаний. 30 нод с минимальным расстоянием используются для дальнейших вычислений кардинальности. Но в данной статье мы рассматриваем другой подход — перепланирование. И хотя у перепланирования есть что-то общее с AQO, работает он иначе.

Как работает перепланирование запросов

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

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

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

Когда выполняется условие перепланирования, то выполнение запроса прерывается, имеющееся информация по нодам (хеш и кардинальность) собирается и сохраняется, как и контекст выполнения (query statement), затем запрос снова начнет перепланирование. Стоит уточнить, что мы таким образом пытаемся оптимизировать случаи, в которых кардинальность, используемая оптимизатором, была строго меньше той, что была получена при выполнении запроса — то есть случаи underestimation. Это важно, потому что иначе алгоритм перерос бы в бесконечный цикл перепланирования. Также есть второй момент, который надо пояснить. Если нет новой информации, которая может быть использована на следующей итерации перепланирования (назовем это “обучением”), а на последней итерации перепланирования больше не оказалось нод с underestimation, то наша таблица знаний будет пуста. Отсюда следует, что больше модель обучать  нечему. 

Говоря об условие перепланирования, проще всего понять условие по времени выполнения. В нём мы задаем условие срабатывания перепланировщика так: будем перепланировать запрос, который выполняется большее количество времени, чем мы ожидали. Значение в данном условии устанавливается как определенное количество миллисекунд, за которые запрос должен выполниться. Второе условие перепланирования — по кардинальности. Он запускает процесс перепланирования запросов, если количество строк в ноде превышает допустимый лимит. Он отлично срабатывает, когда нужно предусмотреть план с кешированием результатов через материализацию — механизм кеширования результатов — для этого могут использоваться оптимизатором такие ноды, как Materialize или Memoize. Последний — по памяти. Если использование памяти при планировании превышает ее объем во время выполнения запроса, то уходим перепланировать. Отличный пример для для этого случай: планы с сортировкой, где объема настолько много, что они не помещаются в оперативную память для проведения сортировки.

Теперь дополним уже известную нам схему планировщика новыми компонентами — условие перепланирования (trigger на схеме) и Replan-хранилище.

Начнем с того момента, когда выполняется условие перепланирования: когда в процессе выполнения плана запроса срабатывает условие, например, по времени, выполнение запроса прерывается и данные о нём сохраняются в Replan Data:

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

Теперь открываем новую сабтранзакцию и начинаем процесс перепланирования снова, передавая информацию о запросе как query statement, для которого нужно получить план запроса.

Теперь, когда планировщику при генерации плана нужно использовать кардинальности для ноды, он возьмет эту информацию из Replan Data.

Где перепланирование точно не поможет

Очень важно для пользователя правильно установить условия перепланирования. Если их значения будут малы, то перепланирование начнёт запускаться даже для простых случаев. Например:

EXPLAIN ANALYZE SELECT count(1) FROM pipeline p,tasks t
WHERE p.status = 'STARTED' AND p.id = t.pipeline_id and t.status IN ('NEW', 'COMPLETED') AND t.creation_time > now() - interval '1 hour';                                 
----------------------------------------------------------
 Aggregate  (rows=1) (rows=1)
	 ->  Nested Loop  (rows=9) (rows=25000)
         ->  Index Scan using pipeline_status_idx on pipeline p  (rows=1) (rows=5000)
               Index Cond: (status = 'STARTED'::text)
         ->  Index Scan using tasks_pipeline_id_idx on tasks t  (rows=5) (rows=5)
               Index Cond: (pipeline_id = p.id)
               Filter: ((status = ANY ('{NEW,COMPLETED}'::text[])) AND (creation_time > (now() - '01:00:00'::interval)))
--------------------------------------------
Planning Time: 3.043 ms
 Execution Time: 43.531 ms
(9 rows)

Как видно, хотя запрос имеет проблему underestimation в одном из индексов (строк в ноде гораздо меньше, чем есть на самом деле), машина достаточно быстрая, чтобы данную проблему пережить — на выполнение запроса отводится 43 мс.

Установив значение в 30 мс, перепланирование запустится, а план сменится с Nested Loop на Hash Join, но на это будет потрачена целая секунда, поскольку потребуется одна дополнительная попытка для перепланирования.

EXPLAIN ANALYZE SELECT count(1) FROM pipeline p,tasks t
	WHERE p.status = 'STARTED' AND p.id = t.pipeline_id and t.status IN ('NEW', 'COMPLETED') AND t.creation_time > now() - interval '1 hour';                             
-------------------------------------------------------
Aggregate  (rows=1) (rows=1)
	->  Hash Join  (rows=491) (rows=25000)
   Hash Cond: (t.pipeline_id = p.id)
  ->  Index Scan using tasks_status_creation_time_idx on tasks t  (rows=24752) (rows=25000)
          Index Cond: ((status = ANY ('{NEW,COMPLETED}'::text[])) AND (creation_time > (now() - '01:00:00'::interval)))
      ->  Hash  (rows=99) (rows=5000)
      ->  Index Scan using pipeline_status_idx on pipeline p  (rows=99) (rows=5000)
           Index Cond: (status = 'STARTED'::text)
 Planning Time: 0.414 ms
 Execution Time: 22.380 ms
 Replanning Attempts: 1
 Total Execution Time: 1025.460 ms

Другой пример связан с ограниченной областью действия перепланирования: он отлично помогает, когда количество строк гораздо меньше, чем в реальности у оптимизатора, но он абсолютно бесполезен в обратной ситуации. Чаще всего вы будете сталкиваться с ситуацией, что план, выбранный оптимизатором, потребляет гораздо больше памяти, чем следовало бы. Применяя, например, кеширование через ноды (Materialize, Memoize) или подтягивая параллельных воркеров для выполнения запроса, хотя они в итоге и задействованы толком не были. Возможно есть какое-то решение как Replan, которое может справляться с подобным случаем, но мы пока оставили такой подход, чтобы не уходить в бесконечное перепланирование.

Бенчмарки

Join Order Benchmark

Тестировали перепланирование мы на REL_16_STABLE PostgreSQL. Для нагрузки был выбран Join Order Benchmark или ImDB. Этот бенчмарк состоит из 113 запросов, которые отвечают на вопросы любителей кино. Причем один из таких запросов может иметь от 8 до 13 соединений между таблицами. Помимо этого данные в базе неравномерно распределены и имеют корреляции, что усложняет оптимизатору возможность сгенерировать оптимальный план запроса.

Так выглядит схема базы данных JOB:

А теперь о результатах тестирования.

На графике ниже показано как мы запускали JOB и фиксировали, что от запроса к запросу время выполнения меняется. Например, для запроса 25 время выполнения на 4 попытки возросло по сравнению с первой попыткой, при этом на третьей попытке оно было значительно ниже. Для некоторых запросов от попытки к попытке время выполнения не меняется вовсе.

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

Перебрав три варианта условия перепланирования по времени между 200, 1000 и 10000 мс, мы обнаружили, что последний лучше всего работает для оптимизатора, ускоряя некоторые запросы в 2 или более чем в 10 раз.

Заключение

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

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

Соавтор: Лепихов Андрей