60.3. Генетическая оптимизация запросов (GEQO) в PostgreSQL#
60.3. Генетическая оптимизация запросов (GEQO) в PostgreSQL
Модуль GEQO подходит к проблеме оптимизации запроса, как если бы это была известная проблема коммивояжера (TSP). Возможные планы запроса кодируются в виде целочисленных строк. Каждая строка представляет порядок соединения от одного отношения запроса к следующему. Например, дерево соединения.
/\ /\ 2 /\ 3 4 1
закодирована целочисленной строкой '4-1-3-2', что означает, сначала объединить отношения '4' и '1', затем '3', а затем '2', где 1, 2, 3, 4 - это идентификаторы отношений внутри оптимизатора Tantor SE.
Специфические характеристики реализации GEQO в Tantor SE следующие:
Использование устойчивого состояния GA (замена наименее подходящих особей в популяции, а не полная замена поколения) позволяет быстро сходиться к улучшенным планам запросов. Это существенно для обработки запросов в разумное время;
Использование кроссовера краевой рекомбинации, который особенно подходит для минимизации краевых потерь при решении TSP с помощью GA;
Мутация в качестве генетического оператора устарела, поэтому не требуется механизмов восстановления для генерации правильных туров TSP.
Части модуля GEQO адаптированы из алгоритма Genitor D. Whitley.
Модуль GEQO позволяет оптимизатору запросов Tantor SE эффективно поддерживать выполнение больших запросов с использованием неисчерпывающего поиска.
60.3.1. Генерация возможных планов с GEQO
Процесс планирования GEQO использует стандартный планировщик для генерации планов для сканирования отдельных отношений. Затем планы соединения разрабатываются с использованием генетического подхода. Как показано выше, каждый кандидат в план соединения представлен последовательностью, в которой происходит соединение базовых отношений. На начальном этапе код GEQO просто случайным образом генерирует некоторые возможные последовательности соединения. Для каждой рассматриваемой последовательности соединения вызывается стандартный планировщик для оценки стоимости выполнения запроса с использованием этой последовательности соединения. (Для каждого шага последовательности соединения рассматриваются все три возможные стратегии соединения, и все изначально определенные планы сканирования отношений доступны. Оценочная стоимость является наименьшей из этих возможностей). Последовательности соединения с более низкой оценочной стоимостью считаются "более подходящими" по сравнению с теми, у которых стоимость выше. Генетический алгоритм отбрасывает наименее подходящих кандидатов. Затем новые кандидаты создаются путем комбинирования генов более подходящих кандидатов - то есть, с использованием случайно выбранных частей известных последовательностей соединения с низкой стоимостью для создания новых последовательностей для рассмотрения. Этот процесс повторяется до тех пор, пока не будет рассмотрено заранее заданное количество последовательностей соединения; затем лучшая найденная в любое время во время поиска используется для создания окончательного плана.
Этот процесс по своей сути недетерминирован, из-за случайных выборов, сделанных как при начальном выборе популяции, так и при последующей “мутации” лучших кандидатов. Чтобы избежать неожиданных изменений выбранного плана, каждый запуск алгоритма GEQO перезапускает свой генератор случайных чисел с текущим значением параметра geqo_seed. При условии, что geqo_seed и другие параметры GEQO остаются неизменными, для данного запроса (и других входных данных планировщика, таких как статистика) будет сгенерирован тот же план. Чтобы экспериментировать с разными путями поиска, попробуйте изменить geqo_seed.
60.3.2. Задачи по реализации в будущем для Tantor SE GEQO
Работа по улучшению настроек параметров генетического алгоритма все еще требуется.
В файле src/backend/optimizer/geqo/geqo_main.c,
в процедурах
gimme_pool_size и gimme_number_generations,
нам нужно найти компромисс для настроек параметров,
чтобы удовлетворить два конкурирующих требования:
Оптимальность плана запроса
Время вычислений
В текущей реализации оценка пригодности каждой кандидатской последовательности соединения осуществляется путем запуска кода выбора соединения и оценки стоимости стандартного планировщика с нуля. В той мере, в которой различные кандидаты используют похожие подпоследовательности соединений, будет повторяться значительное количество работы. Это можно сделать значительно быстрее, сохраняя оценки стоимости для под-соединений. Проблема заключается в том, чтобы избежать необоснованного расхода памяти на сохранение этого состояния.
На более базовом уровне не ясно, что решение оптимизации запроса с помощью алгоритма ГА, разработанного для задачи коммивояжера, является уместным. В случае задачи коммивояжера стоимость, связанная с любой подстрокой (частичным маршрутом), не зависит от остальной части маршрута, но это определенно не верно для оптимизации запроса. Таким образом, можно сомневаться, что кроссовер с рекомбинацией ребер является наиболее эффективной процедурой мутации.