Оптимізація запитів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Оптимізація запитів — це 1) функція СКБД, яка виконує пошук оптимального плана виконання запиту з усіх можливих для заданого запиту, 2) процес зміни запиту та/або структури БД в цілях зменшення використання розрахункових ресурсів при виконанні запиту. Один і той же результат може бути отриманий СКБД різноманітними способами (планами виконання запиту), які можуть суттєво відрізнятися як за затратами ресурсів, так і за часом виконання. Задача оптимізації полягає в знаходженні оптимального способу.

В реляційній СКБД оптимальний план виконання запиту — це така послідовність застосування операторів реляційної алгебри до висхідних та проміжним відношенням, яка для конкретного поточного стану БД (її структури і наповнення) може бути виконана з мінімальним використанням обчислювальних ресурсів.

В даний час відомі дві стратегії пошуку оптимального плану:

  • грубої сили шляхом оцінки всіх перестановок з'єднуваних таблиць, використовуваних способів входу в таблиці і типів з'єднання (тобто повний перебір варіантів);
  • на основі генетичного алгоритму шляхом оцінки обмеженого числа перестановок.

Також деякі СКБД дозволяють програмісту втручатися в пошук оптимального плану різної міри, від мінімального впливу до повного і чіткого зазначення який саме план запиту використовувати.

Плани виконання запиту порівнюються виходячи з безлічі чинників (реалізації в різних СКБД відрізняються), в тому числі:

  • потенційне число рядків, що витягають із кожної таблиці, одержуване з статистики;
  • наявність індексів;
  • можливість виконання злиття (merge-join);
  • спосіб читання записів / блоків таблиць / індексів.

У загальному випадку з'єднання виконується вкладеними циклами. Однак цей алгоритм може виявитися менш ефективним, ніж спеціалізовані алгоритми. Наприклад, якщо у зливаних таблиць є індекси по з'єднувальних полях, або одна або обидві таблиці досить малі, щоб бути відсортованими в пам'яті, то досліджується можливість виконання злиття.

Стратегії оптимізації[ред. | ред. код]

Як вже зазначалося, суть оптимізації полягає в пошуку мінімуму функції вартості від перестановки таблиць. Незалежно від стратегії, оптимізатор повинен вміти аналізувати вартість для довільної перестановки, в той час як самі перестановки для аналізу надаються іншим алгоритмом. Досліджувана множина перестановок може відрізнятися від усього простору перестановок. Виходячи з цього, узагальнений алгоритм роботи оптимізатора можна записати так:

Перебір усіх планів в пошуку найкращого[ред. | ред. код]

  ПоточнийПорядокТаблиць := ЗнайтиПочатковийПорядокТаблиць;
  КращийПорядокТаблиць := ПоточнийПорядокТаблиць;
  НайменшаЗатратність := МаксимальноМожливаЗатратність;

  Виконувати
    Затратність := ОцінитиЗатратність(ПоточнийПорядокТаблиць);

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

     ПоточнийПорядокТаблиць := ЗнайтиНаступнийПорядокТаблиць;
  Допоки (ДоступнийНаступнийПорядокТаблиць);

Стратегія грубої сили[ред. | ред. код]

У теорії, при використанні стратегії грубої сили оптимізатор запитів досліджує весь простір перестановок всіх вихідних обираних таблиць і порівнює сумарні оцінки вартості виконання з'єднання для кожної перестановки. На практиці, при розробці 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 (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 запропонували використовувати генетичний алгоритм для оптимізації запитів, який дає субоптимальное рішення за лінійний час. При використанні генетичного алгоритму досліджується тільки частина простору перестановок. Таблиці, які беруть участь в запиті, кодуються в хромосоми. Над ними виконуються мутації і схрещування. На кожній ітерації виконується відновлення хромосом для отримання осмисленої перестановки таблиць і відбір хромосом, які дають мінімальні оцінки вартості. В результаті відбору залишаються тільки ті хромосоми, які дають менше, в порівнянні з попередньою итерацией, значення функції вартості. Таким чином відбувається дослідження і знаходження локальних мінімумів функції вартості. Передбачається, що глобальний мінімум не дає істотних переваг, у порівнянні з найкращим локальним мінімумом. Алгоритм повторюється кілька ітерацій, після чого вибирається найбільш ефективне рішення.

Оцінка альтернативних способів виконання[ред. | ред. код]

При оцінці планів виконання запитів досліджуються альтернативні способи виконання реляційних з'єднань. Способи виконання з'єднань відрізняються по ефективності, але володіють обмеженнями щодо застосування.

Вкладені цикли[ред. | ред. код]

У разі вкладених циклів зовнішній цикл витягує всі рядки з зовнішньої таблиці і для кожної знайденої рядки викликає внутрішній цикл. Внутрішній цикл за умовами об'єднання і даними зовнішнього циклу шукає рядки у внутрішній таблиці. Цикли можуть вкладатися довільну кількість разів. У цьому випадку внутрішній цикл стає зовнішнім для наступного циклу і т.д.

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

Вибір індексу[ред. | ред. код]

Для вибору індексу для кожної таблиці насамперед знаходяться всі потенційні індекси, які можуть бути застосовані в досліджуваному запиті. Оскільки ключі в індексі впорядковані, то ефективна вибірка з нього може виконуватися тільки в лексикографічному порядку. У зв'язку з цим, вибір індексу ґрунтується на наявності обмежень для колонок, що входять в індекс, починаючи з першої. Для кожної колонки, що входить до індексу, починаючи з першої, шукаються обмеження з усього набору обмежень для даної таблиці, включаючи умови з'єднань. Якщо для першої колонки індексу не може бути знайдено жодного обмеження, то індекс не використовується (в іншому випадку довелося б сканувати індекс цілком). Якщо для чергової колонки обмежень не може бути знайдено, то пошук завершується і індекс приймається.

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

Решта індекси ранжуються за кількістю видобутих рядків і довжині ключа. Очевидно, число видобутих рядків залежить від обмежень. Чим менше число видобутих рядків і коротше довжина ключа, тим вище ранг.

Індекс з найвищим рангом використовується для вибірки.

Сканування індексу цілком[ред. | ред. код]

'Для виконання деяких запитів з агрегацією' індекс може скануватися цілком. Зокрема:

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

'Якщо запитаний порядок вибірки збігається з порядком одного або більше індексів' , то виконується оцінка можливості сканування одного з таких індексів цілком.

'Якщо індекс містить всі колонки, необхідні для отримання результату' , то сканування таблиці не відбувається. Якщо оптимізатор використовує цей фактор, то можна прискорити вибірку з таблиці для спеціалізованих запитів шляхом включення в індекс надлишкових колонок, які будуть вилучені безпосередньо при пошуку по ключу. Подібний метод прискорення запитів слід використовувати обережно.

Див. Також[ред. | ред. код]

Література[ред. | ред. код]

  • Дейт К. Дж. Введение в системы баз данных. 2001. Из-во: Вильямс. ISBN 5-8459-0138-3
  • Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003) ISBN 5-8459-0527-3
  • Дональд Кнут. The Art of Computer Programming, Volume 4, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions. — 1 edition (April 27, 2008). — Addison-Wesley Professional, 2008. — С. 240. — ISBN 978-0321534965.

Посилання[ред. | ред. код]