Интернет магазин китайских планшетных компьютеров

Компьютеры - Оптимизация запросов СУБД - Стратегии оптимизации

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

Перебор всех планов в поисках наилучшего

  ТекущийПорядокТаблиц := НайтиИсходныйПорядокТаблиц;
  ЛучшийПорядокТаблиц := ТекущийПорядокТаблиц;
  НаименьшаяСтоимость := МаксимальноВозможнаяСтоимость;

  Выполнять
    Стоимость := ОценитьСтоимость;

    Если Стоимость < НаименьшаяСтоимость То
      ЛучшийПорядокТаблиц := ТекущийПорядокТаблиц;
      НаименьшаяСтоимость := Стоимость;
    КонецЕсли;

    ТекущийПорядокТаблиц := НайтиСледующийПорядокТаблиц;
  Пока;

Стратегия грубой силы

В теории, при использовании стратегии грубой силы оптимизатор запросов исследует все пространство перестановок всех исходных выбираемых таблиц и сравнивает суммарные оценки стоимости выполнения соединения для каждой перестановки. На практике, при разработке System R было предложено ограничить пространство исследования только левосторонними соединениями, чтобы при выполнении запроса одна из таблиц всегда была представлена образом на диске. Исследование нелевосторонних соединений имеет смысл если таблицы, входящие в соединения, расположены на более чем одном узле.

Для каждой таблицы в каждой из перестановок по статистике оценивается возможность использования индексов. Перестановка с минимальной оценкой и есть итоговый план выполнения запроса.

Алгоритмы генерации всех перестановок обсуждаются в четвёртом томе секции 2 «Искусства программирования для ЭВМ» Дональда Кнута.

Оценка стоимости плана на основе текущей перестановки таблиц

/*
 * Making estimation of query cost accordingly
 * current order of tables in query
 * Function returns value < 0  if it decides not to
 * make all steps of estimation because the cost of
 * this order >> the_best_cost
 * In another case it returns estimated cost
 */
static float
est_cost_order 
{
  MASK Depend = _AllTblMsk;
  i4_t tbl_num, prdc_num, i, real_num, ColNum;
  float cost_all = 0.0, row_num = 1.0;
  float ind_best_sel, sel;
  SP_Ind_Info *cur_ind_info;
 
  /* estimation of the cost of tables scanning */
  for 
    {
      ind_best_sel = 1.0;
      real_num = cur_tbl_order ;
      TblAllBits = Depend = BitOR ;
 
      /* init of array for information about culumns */
      for 
   col_stat.Sel = 1.0;
 
      /* checking information about SPs for current table */
      for 
   if  /* this predicate wasn't used yet */ &&
       CAN_BE_USED 
       /* predicate can be used now */)
     {
       SPs.flag++;
       cur_ind_info =  + prdc_num;
       if 
         { /* this predicate is SP for current table */
      ColNum = cur_ind_info->ColNum;
      if 
        {
          col_stat.Sel = cur_ind_info->Sel;
          if (cur_ind_info->IndExists /* there is index for the column of this SP */
         && col_stat.Sel < ind_best_sel)
            ind_best_sel = col_stat.Sel;
        }
         }
     }
 
     /* finding of common selectivity of all simple predicates for current table */
      for 
   sel *=col_stat.Sel;
 
      /* adding of default selectivity for the rest of predicates */
      for 
   if  /* this predicate wasn't used yet */ &&
       CAN_BE_USED /* predicate can be used now */
      )
     {
       SPs.flag++;
            sel *= DEFAULT_SEL;
          }
 
      number_of_scanned_rows  = number_of_rows * ind_best_sel * row_num;
      /* number_of_scanned_rows - estimated number of rows read from i-th table */
      cost_all += number_of_scanned_rows  + OPEN_SCAN_COST * row_num;
      row_num *= number_of_rows * sel;
 
    } /* for tbl_num: tables handling */
  for 
    SPs.flag = 0;
 
  /* adding of the cost of all subqueries */
  for 
    {
      for 
        if )
          break;
      assert ;
 
      /* tbl_num - number of the last table *
       * that is referenced in the predicate           */
      cost_all += SPs.SQ_cost * number_of_scanned_rows ;
    }
 
  *res_row_num =  ? 1 :
     ? row_num : MAX_LNG);
 
  return cost_all;
} /* est_cost_order */

Здесь cur_tbl_order — знакомый по предыдущему примеру вектор, содержащий текущий порядок таблиц.

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

С ростом числа таблиц в запросе количество возможных перестановок растет как n!, следовательно, пропорционально растет и время оценки для каждой из них. Это делает проблематичным оптимизацию запросов на основе большого числа таблиц. В поисках решения этой проблемы в 1991 году Kristin Bennett, Michael Ferris, Yannis Ioannidis предложили использовать генетический алгоритм для оптимизации запросов, который дает субоптимальное решение за линейное время.

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