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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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