Генетический оптимизатор запросов

Примечание
Данный оптимизатор разработал Мартин Утеш (Martin Utesch, utesch@aut.tu-freiberg.de) для Института автоматического управления в Техническом университете Фрайбергская горная академия, Германия.

Обработка запроса как сложная задача оптимизации

Среди всех операторов отношений самым сложным для обработки и оптимизации является соединение. Количество возможных планов запроса растет экспоненциально по мере увеличения количества соединений в запросе. Дополнительные затраты на оптимизацию возникают как следствие поддержки различных методов соединения (например, в QHB это вложенный цикл, соединение по хешу и соединение слиянием) для обработки отдельных соединений и разнообразия индексов (например, в QHB это B-дерево, хеш, GiST и GIN), выступающих в роли путей доступа к отношениям.

Обычный оптимизатор запросов QHB выполняет почти исчерпывающий поиск по всему пространству стратегических альтернатив. Этот алгоритм, впервые появившийся в СУБД IBM System R, выдает близкий к оптимальному порядок соединений, но может потребовать огромного объема времени и памяти, когда количество соединений в запросе оказывается большим. В итоге обычный оптимизатор QHB оказывается неподходящим для запросов, соединяющих большое количество таблиц.

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

Генетические алгоритмы

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

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

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

Рисунок 1. Структура генетического алгоритма

Структура генетического алгоритма

Согласно FAQ в группе comp.ai.genetic, нельзя в полной мере утверждать, что ГА реализует чисто случайный поиск решения проблемы. ГА использует стохастические процессы, но результат получается определенно не случайным (лучше случайного).

Генетическая оптимизация запросов (GEQO) в QHB

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

   /\
  /\ 2
 /\ 3
4  1

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

Реализация GEQO в QHB имеет следующие особые характеристики:

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

  • Использование скрещивания с краевой рекомбинацией, которое особенно подходит для минимизации краевых потерь при решении TSP посредством ГА;

  • Мутация как генетический оператор считается устаревшей, поэтому для генерирования допустимых маршрутов TSP не требуются механизмы исправления.

Части модуля GEQO взяты из алгоритма Genitor, разработанного Д. Уитли (D. Whitley).

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

Генерирование возможных планов с GEQO

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

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

Задачи будущих реализаций GEQO в QHB

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

  • Оптимальность плана запроса

  • Время вычисления

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

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

Дополнительные материалы

Дополнительную информацию о генетических алгоритмах можно найти в следующих источниках:

Copyright © KVANTOM LLC, 2019-2024