Оптимизация генетических запросов (GEQO) в PostgreSQL

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

   /\
  /\ 2
 /\ 3
4  1

кодируется целочисленной строкой '4-1-3-2', что означает, что сначала присоединяются отношения '4' и '1', затем '3', а потом '2', где 1, 2, 3, 4 - идентификаторы отношений в оптимизаторе PostgreSQL.

Специфическими особенностями реализации GEQO в PostgreSQL являются:

• использование ГА с устойчивым состоянием (замена наименее подходящих особей в популяции, а не замена целых поколений) позволяет быстро сходиться к улучшенным планам запросов. Это очень важно для обработки запросов за разумное время;
• использование кроссинговера с рекомбинацией краев, который особенно хорошо подходит для поддержания низких потерь на краях, для решения TSP с помощью ГА;
• мутация как генетический оператор отменена, поэтому для создания легальных туров TSP не нужны механизмы восстановления.

Часть модуля GEQO адаптирована из алгоритма Genitor Д. Уитли.

Модуль GEQO позволяет оптимизатору запросов PostgreSQL эффективно поддерживать большие объединенные запросы за счет неполного поиска.

Генерация возможных планов с помощью GEQO

Процесс планирования GEQO использует стандартный код планировщика для генерации планов сканирования отдельных отношений. Затем с помощью генетического подхода разрабатываются планы соединения. Как показано выше, каждый план-кандидат на присоединение представлен последовательностью, в которой нужно присоединить базовые отношения. На начальном этапе код GEQO просто генерирует несколько возможных последовательностей соединений случайным образом. Для каждой рассматриваемой последовательности соединений вызывается стандартный код планировщика для оценки стоимости выполнения запроса с использованием этой последовательности соединений. (Для каждого шага последовательности соединения рассматриваются все три возможные стратегии соединения, и доступны все первоначально определенные планы сканирования отношений. Оценочная стоимость - это самая дешевая из этих возможностей.) Последовательности соединений с меньшей оценочной стоимостью считаются "более подходящими", чем те, что имеют большую стоимость. Генетический алгоритм отбрасывает наименее подходящие кандидатуры. Затем генерируются новые кандидаты путем объединения генов более подходящих кандидатов - то есть путем использования случайно выбранных частей известных дешевых последовательностей соединения для создания новых последовательностей для рассмотрения. Этот процесс повторяется до тех пор, пока не будет рассмотрено заданное количество последовательностей соединений; затем лучшая из них, найденная в любой момент времени в ходе поиска, используется для создания готового плана.

Этот процесс по своей сути является недетерминированным, поскольку случайные выборы делаются как во время первоначального отбора популяции, так и во время последующей "мутации" лучших кандидатов. Чтобы избежать неожиданных изменений выбранного плана, при каждом запуске алгоритма GEQO генератор случайных чисел перезапускается с текущим значением параметра geqo_seed. Пока geqo_seed и другие параметры GEQO остаются неизменными, для заданного запроса (и других входных данных планировщика, таких как статистика) будет сгенерирован один и тот же план. Чтобы поэкспериментировать с различными путями поиска, попробуйте изменить geqo_seed.

Будущее развитие модуля PostgreSQL GEQO

Необходимо еще поработать над улучшением настроек параметров генетического алгоритма. В файле src/backend/optimizer/geqo/geqo_main.c, подпрограммы gimme_pool_size и gimme_number_generations, мы должны найти компромиссные значения параметров, удовлетворяющие двум несовместимым требованиям:

• оптимальность плана запроса;
• время вычислений.

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

На более базовом уровне не ясно, подходит ли для оптимизации запросов алгоритм ГА, разработанный для TSP. В случае TSP стоимость, связанная с любой подстрокой (частичным туром), не зависит от остальной части тура, но это, конечно, не так для оптимизации запросов. Таким образом, возникает вопрос, является ли кроссовер с рекомбинацией краев наиболее эффективной процедурой мутации.