Оптимизация запросов СУБД

Оптимизация запросов — это функция СУБД, осуществляющая поиск наиболее оптимального плана выполнения запросов из всех возможных для заданного запроса. Один и тот же результат может быть получен СУБД различными способами (планами выполнения запросов), которые могут существенно отличаться как по затратам ресурсов, так и по времени выполнения. Задача оптимизации заключается в нахождении оптимального способа.

В реляционной СУБД оптимальный план выполнения запроса - это такая перестановка всех исходных выбираемых таблиц, реляционное соединение которых в выбранной последовательности, представленное в процедурном виде, может быть выполнено за минимальное число операций.

В настоящее время известны две стратегии поиска оптимального плана:

грубой силы путём оценки всех перестановок соединяемых таблиц;
на основе генетического алгоритма путём оценки ограниченного числа перестановок.

Планы выполнения запроса сравниваются исходя из следующих факторов:

потенциальное число строк, извлекаемое из каждой таблицы, получаемое из статистики;
наличие индексов;
возможность выполнения слияний (merge-join).

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

Стратегии оптимизации

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

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

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

  Выполнять
    Стоимость := ОценитьСтоимость(ТекущийПорядокТаблиц);

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

    ТекущийПорядокТаблиц := НайтиСледующийПорядокТаблиц;
  Пока (ДоступенСледующийПорядокТаблиц);

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

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

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

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

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

/*
 * Making estimation of query cost accordingly
 * current order of tables in query
 * Functin returns value < 0  if it decides not to
 * make all steps of estimation because the cost of
 * this order >> the_best_cost (if the_best_cost > 0)
 * In another case it returns estimated cost (>=0)
 */
static float
est_cost_order (i4_t *res_row_num)
{
  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 (tbl_num = 0; tbl_num < number_of_tables; tbl_num++)
    {
      ind_best_sel = 1.0;
      real_num = cur_tbl_order [tbl_num];
      TblAllBits[tbl_num] = Depend = BitOR (Depend, TblBits [real_num]);

      /* init of array for information about culumns */
      for (i = 0; i < tab_col_num[real_num]; i++)
   col_stat[i].Sel = 1.0;

      /* checking information about SPs for current table */
      for (prdc_num = 0; prdc_num < number_of_SPs; prdc_num++)
   if (!(SPs[prdc_num].flag) /* this predicate wasn't used yet */ &&
       CAN_BE_USED (SPs[prdc_num].Depend, Depend)
       /* predicate can be used now */)
     {
       SPs[prdc_num].flag++;
       cur_ind_info = (SPs_indexes[real_num]) + prdc_num;
       if (cur_ind_info->Sel)
         { /* this predicate is SP for current table */
      ColNum = cur_ind_info->ColNum;
      if (col_stat[ColNum].Sel > cur_ind_info->Sel)
        {
          col_stat[ColNum].Sel = cur_ind_info->Sel;
          if (cur_ind_info->IndExists /* there is index for the column of this SP */
         && col_stat[ColNum].Sel < ind_best_sel)
            ind_best_sel = col_stat[ColNum].Sel;
        }
         }
     }

     /* finding of common selectivity of all simple predicates for current table */
      for (i = 0, sel = 1.0; i < tab_col_num[real_num]; i++)
   sel *=col_stat[i].Sel;

      /* adding of default selectivity for the rest of predicates */
      for (prdc_num = number_of_SPs; prdc_num < number_of_disjuncts; prdc_num++)
   if (!(SPs[prdc_num].flag) /* this predicate wasn't used yet */ &&
       CAN_BE_USED (SPs[prdc_num].Depend, Depend)/* predicate can be used now */
      )
     {
       SPs[prdc_num].flag++;
            sel *= DEFAULT_SEL;
          }

      number_of_scanned_rows [tbl_num] = number_of_rows[real_num] * ind_best_sel * row_num;
      /* number_of_scanned_rows [i] - estimated number of rows read from i-th table */
      cost_all += number_of_scanned_rows [tbl_num] + OPEN_SCAN_COST * row_num;
      row_num *= number_of_rows[real_num] * sel;

    } /* for tbl_num: tables handling */
  for (prdc_num = 0; prdc_num < number_of_disjuncts; prdc_num++)
    SPs[prdc_num].flag = 0;

  /* adding of the cost of all subqueries */
  for (prdc_num = 0; prdc_num < number_of_disjuncts; prdc_num++)
    {
      for (tbl_num = 0; tbl_num < number_of_tables; tbl_num++)
        if (CAN_BE_USED (SPs[prdc_num].SQ_deps, TblAllBits[tbl_num]))
          break;
      assert (tbl_num < number_of_tables);

      /* tbl_num - number of the last (in order) table *
       * that is referenced in the predicate           */
      cost_all += SPs[prdc_num].SQ_cost * number_of_scanned_rows [tbl_num];
    }

  *res_row_num = (row_num < 1.0) ? 1 :
    ((row_num < FLT_MAX_LNG) ? (i4_t)row_num : MAX_LNG);

  return cost_all;
} /* est_cost_order */

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

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

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

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

Оценка альтернативных способов выполнения

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

Вложенные циклы

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

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

Выбор индекса

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

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

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

Оставшиеся индексы ранжируются по числу извлекаемых строк и длине ключа. Очевидно, число извлекаемых строк зависит от ограничений. Чем меньше число извлекаемых строк и короче длина ключа, тем выше ранг.

Индекс с наивысшим рангом используется для выборки.

Сканирование индекса целиком

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

Для поиска глобальных максимальных и минимальных значений использоваться индекс по соответствующей колонке (колонкам) без ограничений;
Для поиска числа строк в таблице используется индекс по первичному ключу, если таковой имеется. Это связано с тем, что СУБД не хранит и не может хранить число строк в таблице, а сканирование индекса по первичному ключу наименее ресурсоемко.

Если запрошенный порядок выборки совпадает с порядком одного или более индексов, то выполняется оценка возможности сканирования одного из таких индексов целиком.

Если индекс содержит все колонки, необходимые для получения результата, то сканирование таблицы не происходит. Если оптимизатор использует этот фактор, то можно ускорить выборку из таблицы для специализированных запросов путем включения в индекс избыточных колонок, которые будут извлечены непосредственно при поиске по ключу. Подобный метод ускорения запросов следует использовать осторожно.

Слияние

Если объединяемые таблицы имеют индексы по сравниваемым полям, или одна или обе таблицы достаточно малы, чтобы быть отсортированными в памяти, то объединение может быть выполнено с помощью слияния. Оба отсортированных набора данных сканируются и в них ищутся одинаковые значения. За счет сортировки слияние эффективнее вложенных циклов на больших объемах данных, но план выполнения не может не начинаться со слияния.

Оценка числа извлекаемых строк

Оценка числа извлекаемых из таблицы строк используется для принятия решения о полном сканировании таблицы вместо доступа по индексу. Решение принимается на том основании, что каждое чтение листовой страницы индекса с диска влечет за собой 1 или более позиционирований и 1 или более чтений страниц таблицы. Поскольку индекс содержит ещё и нелистовые страницы, то извлечение более 0.1-1%[2] строк из таблицы, как правило, эффективней выполнять полным сканированием таблицы.

Более точная оценка получится на основе следующих показателей:

Число извлекаемых строк
Средняя длина ключа в индексе
Среднее число строк в странице индекса
Длина страницы индекса
Высота B*-дерева в индексе
Средняя длина строки в таблице
Среднее число строк в странице таблицы
Длина страницы таблицы

СУБД старается организовать хранение блоков данных одной таблицы последовательно с целью исключить накладные расходы на позиционирование при полном сканировании (СУБД Oracle использует предварительное выделение дискового пространства для файлов данных). Эффективность полного сканирования так же увеличивается за счет упреждающего чтения. При упреждающем чтении СУБД одновременно выдает внешней памяти команды чтения нескольких блоков. Сканирование начинается по завершению чтения любого из блоков. Одновременно продолжается чтение остальных блоков. Эффективность достигается за счет параллелизма чтения и сканирования.

Оптимизация параллельных сортировок

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

Если СУБД запущена на нескольких узлах, то сортировка параллельно выполняется каждым из узлов, вовлеченных в выполнение запроса. Затем каждый из узлов оправляет свой фрагмент узлу, отвечающему за выдачу данных клиенту, где выполняется слияние полученных фрагментов.

Статистика

Гистограмма для колонки таблицы. Все возможные значения разбиты на 4 интервала в зависимости от первой буквы. Высота столбца указывает число строк в процентах, для которых значение колонки попадает в соответствующий интервал.

Для оценки потенциального числа строк, извлекаемого из таблицы, РСУБД использует статистику. Статистика имеет вид гистограмм для каждой колонки таблицы, где по горизонтали располагается шкала значений, а высотой столбца отмечается оценка числа строк в процентах от общего числа строк.

Таким образом, если из таблицы извлекаются строки со значением колонки C с ограничением [V1, V2], то можно оценить число строк, попадающих в этот интервал. Алгоритм оценки числа извлекаемых строк следующий:

Определить, в какие интервалы гистограммы попадает ограничение [V1, V2];
Найти оценки числа строк Ri для каждого интервала i в процентах.
Если [V1, V2] попадает в некоторый интервал [S1, S2] частично или полностью лежит в интервале, то:
1. Найти пересечение [V1, V2] и [S1, S2]
2. Откорректировать число значений в частичном интервале (это либо Ri * (V1 - S2 + 1) / (S1 - S2 + 1), либо Ri * (S1 - V2 + 1) / (S1 - S2 + 1), либо Ri * (V1 - V2 + 1) / (S1 - S2 + 1));
Иначе оценка для интервала равна Ri;
Просуммировать оценки в процентах для всех интервалов;
Перевести оценку в процентах в число строк (см. ниже).

Как правило, СУБД не знает и не может знать точное число строк в таблице (даже для выполнения запроса SELECT COUNT(*) FROM TABLE выполняется сканирование первичного индекса), поскольку в базе могут храниться одновременно несколько образов одной и той же таблицы с различным числом строк. Для оценки числа строк используются следующие данные:

Число страниц в таблице
Длина страницы
Средняя длина строки в таблице

Статистика для колонки таблицы нарастающим итогом.

Статистика так же может храниться нарастающим итогом. В этом случае каждый интервал содержит суммарную оценку всех предыдущих интервалов плюс собственную оценку. Для получения оценки числа строк для ограничения [V1, V2] достаточно из оценки интервала, в который попадает V2, вычесть оценку интервала, в который попадает V1.

Сбор статистики для построения гистограмм осуществляется либо специальными командами СУБД, либо фоновыми процессами СУБД. При этом, ввиду того, что база может содержать существенный объем данных, делается выборка меньшего объема из всей генеральной совокупности строк. Оценка репрезентативности (достоверности) выборки может осуществляться, например, по критерию согласия Колмогорова.

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

См. также

Семантическая оптимизация запросов

План выполнения запроса

Кэш запросов

Литература

Дейт К. Дж. Введение в системы баз данных. 2001. Из-во: Вильямс. ISBN 5-8459-0138-3
Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003) ISBN 5-8459-0527-3
Donald E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 2: Generating All Tuples and Permutations (Art of Computer Programming) ISBN 0-201-85393-0

Ссылки

Оптимизация запросов СУБД

Содержание