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

Примечание
Данный оптимизатор разработал Мартин Утеш (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

Наше внимание по-прежнему сосредоточено на поисках пути оптимизации значений параметров генетического алгоритма.

При поиске решения проблемы оптимизации запросов средствами ГА (подпрограммы gimme_pool_size и gimme_number_generations) мы должны найти компромиссные значения параметров, удовлетворяющие двум разнонаправленным требованиям:

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

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

Например:

/*
* Параметры конфигурации
*/
int         Geqo_effort;
int         Geqo_pool_size;
int         Geqo_generations;
double      Geqo_selection_bias;
double      Geqo_seed;


static int  gimme_pool_size(int nr_rel);
static int  gimme_number_generations(int pool_size);

/* пожаловаться, если ни один механизм рекомбинации не определен (#define) */
#if !defined(ERX) && \
   !defined(PMX) && \
   !defined(CX)  && \
   !defined(PX)  && \
   !defined(OX1) && \
   !defined(OX2)
#error "must choose one GEQO recombination mechanism in geqo.h"
#endif


/*
 * geqo
 *    решение проблемы оптимизации запросов,
 *    схожей с ограниченной задачей коммивояжера (TSP)
 */

RelOptInfo *
geqo(PlannerInfo *root, int number_of_rels, List *initial_rels)
{
   GeqoPrivateData private;
   int         generation;
   Chromosome *momma;
   Chromosome *daddy;
   Chromosome *kid;
   Pool       *pool;
   int         pool_size,
               number_generations;

#ifdef GEQO_DEBUG
   int         status_interval;
#endif
   Gene       *best_tour;
   RelOptInfo *best_rel;

#if defined(ERX)
   Edge       *edge_table;     /* список границ */
   int         edge_failures = 0;
#endif
#if defined(CX) || defined(PX) || defined(OX1) || defined(OX2)
   City       *city_table;     /* список городов */
#endif
#if defined(CX)
   int         cycle_diffs = 0;
   int         mutations = 0;
#endif

/* настройка внутренней информации */
   root->join_search_private = (void *) &private;
   private.initial_rels = initial_rels;

/* инициализация внутреннего генератора случайных чисел */
   geqo_set_seed(root, Geqo_seed);

/* установка параметров ГА */
   pool_size = gimme_pool_size(number_of_rels);
   number_generations = gimme_number_generations(pool_size);
#ifdef GEQO_DEBUG
   status_interval = 10;
#endif

/* выделение памяти для генетического пула */
   pool = alloc_pool(root, pool_size, number_of_rels);

/* случайная инициализация пула */
   random_init_pool(root, pool);

/* сортировка пула, исходя из того, что приспособленность — это самый дешевый путь */
   sort_pool(root, pool);      /* we have to do it only one time, since all
                                * kids replace the worst individuals in
                                * future (-> geqo_pool.c:spread_chromo ) */

#ifdef GEQO_DEBUG
   elog(DEBUG1, "GEQO selected %d pool entries, best %.2f, worst %.2f",
        pool_size,
        pool->data[0].worth,
        pool->data[pool_size - 1].worth);
#endif

/* выделение памяти для хромосом мама и папа */
   momma = alloc_chromo(root, pool->string_length);
   daddy = alloc_chromo(root, pool->string_length);

#if defined (ERX)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using edge recombination crossover [ERX]");
#endif
/* выделение памяти для таблицы границ */
   edge_table = alloc_edge_table(root, pool->string_length);
#elif defined(PMX)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using partially matched crossover [PMX]");
#endif
/* выделение памяти для хромосомы ребенок */
   kid = alloc_chromo(root, pool->string_length);
#elif defined(CX)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using cycle crossover [CX]");
#endif
/* выделение памяти для таблицы городов */
   kid = alloc_chromo(root, pool->string_length);
   city_table = alloc_city_table(root, pool->string_length);
#elif defined(PX)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using position crossover [PX]");
#endif
/* выделение памяти для таблицы городов */
   kid = alloc_chromo(root, pool->string_length);
   city_table = alloc_city_table(root, pool->string_length);
#elif defined(OX1)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using order crossover [OX1]");
#endif
/* выделение памяти для таблицы городов */
   kid = alloc_chromo(root, pool->string_length);
   city_table = alloc_city_table(root, pool->string_length);
#elif defined(OX2)
#ifdef GEQO_DEBUG
   elog(DEBUG2, "using order crossover [OX2]");
#endif
/* выделение памяти для таблицы городов */
   kid = alloc_chromo(root, pool->string_length);
   city_table = alloc_city_table(root, pool->string_length);
#endif


/* основная часть: */
/* итеративная оптимизация */

   for (generation = 0; generation < number_generations; generation++)
   {
       /* ВЫБОР: с помощью функции линейного отклонения */
       geqo_selection(root, momma, daddy, pool, Geqo_selection_bias);

#if defined (ERX)
       /* СКРЕЩИВАНИЕ С КРАЕВОЙ РЕКОМБИНАЦИЕЙ */
       gimme_edge_table(root, momma->string, daddy->string, pool->string_length, edge_table);

       kid = momma;

       /* есть ли какие-либо ошибки границ? */
       edge_failures += gimme_tour(root, edge_table, kid->string, pool->string_length);
#elif defined(PMX)
       /* СКРЕЩИВАНИЕ С ЧАСТИЧНЫМ СООТВЕТСТВИЕМ */
       pmx(root, momma->string, daddy->string, kid->string, pool->string_length);
#elif defined(CX)
       /* СКРЕЩИВАНИЕ С ЦИКЛОМ */
       cycle_diffs = cx(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
       /* mutate the child */
       if (cycle_diffs == 0)
       {
           mutations++;
           geqo_mutation(root, kid->string, pool->string_length);
       }
#elif defined(PX)
       /* СКРЕЩИВАНИЕ ПОЗИЦИИ */
       px(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX1)
       /* СКРЕЩИВАНИЕ ПОРЯДКА */
       ox1(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#elif defined(OX2)
       /* СКРЕЩИВАНИЕ ПОРЯДКА */
       ox2(root, momma->string, daddy->string, kid->string, pool->string_length, city_table);
#endif


       /* ВЫЧИСЛЕНИЕ ПРИСПОСОБЛЕННОСТИ */
       kid->worth = geqo_eval(root, kid->string, pool->string_length);

       /* вытолкнуть ребенка в дебри жизни в соответствии с его ценностью */
       spread_chromo(root, kid, pool);


#ifdef GEQO_DEBUG
       if (status_interval && !(generation % status_interval))
           print_gen(stdout, pool, generation);
#endif

   }


#if defined(ERX)
#if defined(GEQO_DEBUG)
   if (edge_failures != 0)
       elog(LOG, "[GEQO] failures: %d, average: %d",
            edge_failures, (int) number_generations / edge_failures);
   else
       elog(LOG, "[GEQO] no edge failures detected");
#else
   /* подавить предупреждения «переменная установлена но не использована» от некоторых компиляторов */
   (void) edge_failures;
#endif
#endif

#if defined(CX) && defined(GEQO_DEBUG)
   if (mutations != 0)
       elog(LOG, "[GEQO] mutations: %d, generations: %d",
            mutations, number_generations);
   else
       elog(LOG, "[GEQO] no mutations processed");
#endif

#ifdef GEQO_DEBUG
   print_pool(stdout, pool, 0, pool_size - 1);
#endif

#ifdef GEQO_DEBUG
   elog(DEBUG1, "GEQO best is %.2f after %d generations",
        pool->data[0].worth, number_generations);
#endif


   /*
    * получить самое дешевое дерево запросов, обработанное geqo; первый элемент
    * популяции указывает на самое лучшее дерево запросов
    */
   best_tour = (Gene *) pool->data[0].string;

   best_rel = gimme_tree(root, best_tour, pool->string_length);

   if (best_rel == NULL)
       elog(ERROR, "geqo failed to make a valid plan");

   /* DBG: показать план запроса */
#ifdef NOT_USED
   print_plan(best_plan, root);
#endif

   /* ... освобождение памяти */
   free_chromo(root, momma);
   free_chromo(root, daddy);

#if defined (ERX)
   free_edge_table(root, edge_table);
#elif defined(PMX)
   free_chromo(root, kid);
#elif defined(CX)
   free_chromo(root, kid);
   free_city_table(root, city_table);
#elif defined(PX)
   free_chromo(root, kid);
   free_city_table(root, city_table);
#elif defined(OX1)
   free_chromo(root, kid);
   free_city_table(root, city_table);
#elif defined(OX2)
   free_chromo(root, kid);
   free_city_table(root, city_table);
#endif

   free_pool(root, pool);

   /* ... очистка указателя root на наше внутреннее хранилище */
   root->join_search_private = NULL;

   return best_rel;
}


/*
 * Вернуть сконфигурированный размер пула или хорошее значение по умолчанию
 *
 * Значение по умолчанию основано на размере запроса (числа отношений) = 2^(QS+1),
 * но ограничено диапазоном, основанным на значении усилия.
 */
static int
gimme_pool_size(int nr_rel)
{
   double      size;
   int         minsize;
   int         maxsize;

   /* Допустимый размер пула *должен* быть не меньше 2, так что игнорируем попытку выбрать 1 */
   if (Geqo_pool_size >= 2)
       return Geqo_pool_size;

   size = pow(2.0, nr_rel + 1.0);

   maxsize = 50 * Geqo_effort; /* от 50 до 500 особей */
   if (size > maxsize)
       return maxsize;

   minsize = 10 * Geqo_effort; /* от 10 до 100 особей */
   if (size < minsize)
       return minsize;

   return (int) ceil(size);
}


/*
 * Вернуть сконфигурированное число поколений или хорошее значение по умолчанию
 *
 * Значение по умолчанию такое же, как и для размера пула, что придает нам
 * уверенности, что наименее приспособленные особы будут удалены из племенного ядра
 * популяции до окончания прогона.
 */
static int
gimme_number_generations(int pool_size)
{
   if (Geqo_generations > 0)
       return Geqo_generations;

   return pool_size;
}

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

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

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

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

Copyright © KVANTOM LLC, 2019-2025