Оптимізація запитів — це 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. Из-во: Вильямс.
- Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003)
- Дональд Кнут. 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. — .
Посилання
- Kristin Bennett, Michael C. Ferris, Yannis E. Ioannidis. A Genetic Algorithm for Database Query Optimization. 1991 Proceedings of the Fourth International Conference on Genetic Algorithms
- Michael Stillger, Myra Spiliopoulou. 1996 Genetic Programming in Database Query Optimization. Institut fur Informatik Humboldt-Universitat zu Berlin
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Optimizaciya zapitiv ce 1 funkciya SKBD yaka vikonuye poshuk optimalnogo plana vikonannya zapitu z usih mozhlivih dlya zadanogo zapitu 2 proces zmini zapitu ta abo strukturi BD v cilyah zmenshennya vikoristannya rozrahunkovih resursiv pri vikonanni zapitu Odin i toj zhe rezultat mozhe buti otrimanij SKBD riznomanitnimi sposobami planami vikonannya zapitu yaki mozhut suttyevo vidriznyatisya yak za zatratami resursiv tak i za chasom vikonannya Zadacha optimizaciyi polyagaye v znahodzhenni optimalnogo sposobu V relyacijnij SKBD optimalnij plan vikonannya zapitu ce taka poslidovnist zastosuvannya operatoriv relyacijnoyi algebri do vishidnih ta promizhnim vidnoshennyam yaka dlya konkretnogo potochnogo stanu BD yiyi strukturi i napovnennya mozhe buti vikonana z minimalnim vikoristannyam obchislyuvalnih resursiv V danij chas vidomi dvi strategiyi poshuku optimalnogo planu gruboyi sili shlyahom ocinki vsih perestanovok z yednuvanih tablic vikoristovuvanih sposobiv vhodu v tablici i tipiv z yednannya tobto povnij perebir variantiv na osnovi genetichnogo algoritmu shlyahom ocinki obmezhenogo chisla perestanovok Takozh deyaki SKBD dozvolyayut programistu vtruchatisya v poshuk optimalnogo planu riznoyi miri vid minimalnogo vplivu do povnogo i chitkogo zaznachennya yakij same plan zapitu vikoristovuvati Plani vikonannya zapitu porivnyuyutsya vihodyachi z bezlichi chinnikiv realizaciyi v riznih SKBD vidriznyayutsya v tomu chisli potencijne chislo ryadkiv sho vityagayut iz kozhnoyi tablici oderzhuvane z statistiki nayavnist indeksiv mozhlivist vikonannya merge join sposib chitannya zapisiv blokiv tablic indeksiv U zagalnomu vipadku z yednannya vikonuyetsya Odnak cej algoritm mozhe viyavitisya mensh efektivnim nizh specializovani algoritmi Napriklad yaksho u zlivanih tablic ye indeksi po z yednuvalnih polyah abo odna abo obidvi tablici dosit mali shob buti vidsortovanimi v pam yati to doslidzhuyetsya mozhlivist vikonannya Strategiyi optimizaciyiYak vzhe zaznachalosya sut optimizaciyi polyagaye v poshuku minimumu funkciyi vartosti vid perestanovki tablic Nezalezhno vid strategiyi optimizator povinen vmiti analizuvati vartist dlya dovilnoyi perestanovki v toj chas yak sami perestanovki dlya analizu nadayutsya inshim algoritmom Doslidzhuvana mnozhina perestanovok mozhe vidriznyatisya vid usogo prostoru perestanovok Vihodyachi z cogo uzagalnenij algoritm roboti optimizatora mozhna zapisati tak Perebir usih planiv v poshuku najkrashogo PotochnijPoryadokTablic ZnajtiPochatkovijPoryadokTablic KrashijPoryadokTablic PotochnijPoryadokTablic NajmenshaZatratnist MaksimalnoMozhlivaZatratnist Vikonuvati Zatratnist OcinitiZatratnist PotochnijPoryadokTablic Yaksho Zatratnist lt NajmenshaZatratnist Todi KrashijPoryadokTablic PotochnijPoryadokTablic NajmenshaZatratnist Zatratnist KinecYaksho PotochnijPoryadokTablic ZnajtiNastupnijPoryadokTablic Dopoki DostupnijNastupnijPoryadokTablic Strategiya gruboyi sili U teoriyi pri vikoristanni strategiyi gruboyi sili optimizator zapitiv doslidzhuye ves prostir perestanovok vsih vihidnih obiranih tablic i porivnyuye sumarni ocinki vartosti vikonannya z yednannya dlya kozhnoyi perestanovki Na praktici pri rozrobci System R bulo zaproponovano obmezhiti prostir doslidzhennya tilki livobichnimi spolukami shob pri vikonanni zapitu odna z tablic zavzhdi bula predstavlena chinom na disku Doslidzhennya nelivostoronnih z yednan maye sens yaksho tablici sho vhodyat v z yednannya roztashovani na bilsh nizh odnomu vuzli Dlya kozhnoyi tablici v kozhnij z perestanovok za statistikoyu ocinyuyetsya mozhlivist vikoristannya indeksiv Perestanovka z minimalnoyu ocinkoyu i ye pidsumkovij plan vikonannya zapitu Algoritmi generaciyi vsih perestanovok obgovoryuyutsya v chetvertomu tomi sekciyi 2 Mistectva programuvannya dlya EOM Donalda Knuta div spisok literaturi Dokladnishe Ocinka vartosti planu na osnovi potochnoyi perestanovki tablic Making estimation of query cost accordingly current order of tables in query Function returns value lt 0 if it decides not to make all steps of estimation because the cost of this order gt gt the best cost if the best cost gt 0 In another case it returns estimated cost gt 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 lt 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 lt 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 lt number of SPs prdc num if SPs prdc num flag this predicate wasn t used yet amp amp 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 gt Sel this predicate is SP for current table ColNum cur ind info gt ColNum if col stat ColNum Sel gt cur ind info gt Sel col stat ColNum Sel cur ind info gt Sel if cur ind info gt IndExists there is index for the column of this SP amp amp col stat ColNum Sel lt 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 lt 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 lt number of disjuncts prdc num if SPs prdc num flag this predicate wasn t used yet amp amp 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 lt number of disjuncts prdc num SPs prdc num flag 0 adding of the cost of all subqueries for prdc num 0 prdc num lt number of disjuncts prdc num for tbl num 0 tbl num lt number of tables tbl num if CAN BE USED SPs prdc num SQ deps TblAllBits tbl num break assert tbl num lt 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 lt 1 0 1 row num lt FLT MAX LNG i4 t row num MAX LNG return cost all est cost order Tut cur tbl order znajomij po poperednomu prikladu vektor sho mistit potochnij poryadok tablic Strategiya na osnovi genetichnogo algoritmu Z rostom chisla tablic v zapiti kilkist mozhlivih perestanovok roste yak n Otzhe i chas ocinki dlya kozhnoyi z nih Ce robit problematichnim optimizaciyu zapitiv na osnovi velikogo chisla tablic U poshukah virishennya ciyeyi problemi v 1991 roci Kristin Bennett Michael Ferris Yannis Ioannidis zaproponuvali vikoristovuvati genetichnij algoritm dlya optimizaciyi zapitiv yakij daye suboptimalnoe rishennya za linijnij chas Pri vikoristanni genetichnogo algoritmu doslidzhuyetsya tilki chastina prostoru perestanovok Tablici yaki berut uchast v zapiti koduyutsya v hromosomi Nad nimi vikonuyutsya mutaciyi i shreshuvannya Na kozhnij iteraciyi vikonuyetsya vidnovlennya hromosom dlya otrimannya osmislenoyi perestanovki tablic i vidbir hromosom yaki dayut minimalni ocinki vartosti V rezultati vidboru zalishayutsya tilki ti hromosomi yaki dayut menshe v porivnyanni z poperednoyu iteraciej znachennya funkciyi vartosti Takim chinom vidbuvayetsya doslidzhennya i znahodzhennya lokalnih minimumiv funkciyi vartosti Peredbachayetsya sho globalnij minimum ne daye istotnih perevag u porivnyanni z najkrashim lokalnim minimumom Algoritm povtoryuyetsya kilka iteracij pislya chogo vibirayetsya najbilsh efektivne rishennya Ocinka alternativnih sposobiv vikonannyaPri ocinci planiv vikonannya zapitiv doslidzhuyutsya alternativni sposobi vikonannya relyacijnih z yednan Sposobi vikonannya z yednan vidriznyayutsya po efektivnosti ale volodiyut obmezhennyami shodo zastosuvannya Vkladeni cikli Dokladnishe U razi vkladenih cikliv zovnishnij cikl vityaguye vsi ryadki z zovnishnoyi tablici i dlya kozhnoyi znajdenoyi ryadki viklikaye vnutrishnij cikl Vnutrishnij cikl za umovami ob yednannya i danimi zovnishnogo ciklu shukaye ryadki u vnutrishnij tablici Cikli mozhut vkladatisya dovilnu kilkist raziv U comu vipadku vnutrishnij cikl staye zovnishnim dlya nastupnogo ciklu i t d Pri ocinci riznih poryadkiv vikonannya vkladenih cikliv dlya minimizaciyi nakladnih vitrat na viklik vnutrishnogo ciklu krashe shob zovnishnij cikl skanuvav menshu kilkist ryadkiv nizh vnutrishnij Vibir indeksu Dlya viboru indeksu dlya kozhnoyi tablici nasampered znahodyatsya vsi potencijni indeksi yaki mozhut buti zastosovani v doslidzhuvanomu zapiti Oskilki klyuchi v indeksi vporyadkovani to efektivna vibirka z nogo mozhe vikonuvatisya tilki v leksikografichnomu poryadku U zv yazku z cim vibir indeksu gruntuyetsya na nayavnosti obmezhen dlya kolonok sho vhodyat v indeks pochinayuchi z pershoyi Dlya kozhnoyi kolonki sho vhodit do indeksu pochinayuchi z pershoyi shukayutsya obmezhennya z usogo naboru obmezhen dlya danoyi tablici vklyuchayuchi umovi z yednan Yaksho dlya pershoyi kolonki indeksu ne mozhe buti znajdeno zhodnogo obmezhennya to indeks ne vikoristovuyetsya v inshomu vipadku dovelosya b skanuvati indeks cilkom Yaksho dlya chergovoyi kolonki obmezhen ne mozhe buti znajdeno to poshuk zavershuyetsya i indeks prijmayetsya Pri ocinci planiv vikonannya doslidzhuyutsya alternativni nabori indeksiv yaki mozhut buti vikoristani dlya vibirki U razi vkladenih cikliv najbilsh zovnishnij cikl ne mozhe vikoristovuvati zhodnogo indeksu yakij obmezhuyetsya hocha b odniyeyu umovoyu spoluki oskilki pri vikonanni cogo ciklu zhodna z umov z yednannya povnistyu ne viznacheno Vnutrishnij cikl ne mozhe vikoristovuvati zhodnogo indeksu z obmezhennyami ne sumisnimi z umovami z yednannya Reshta indeksi ranzhuyutsya za kilkistyu vidobutih ryadkiv i dovzhini klyucha Ochevidno chislo vidobutih ryadkiv zalezhit vid obmezhen Chim menshe chislo vidobutih ryadkiv i korotshe dovzhina klyucha tim vishe rang Indeks z najvishim rangom vikoristovuyetsya dlya vibirki Skanuvannya indeksu cilkom Dlya vikonannya deyakih zapitiv z agregaciyeyu indeks mozhe skanuvatisya cilkom Zokrema Dlya poshuku globalnih maksimalnih i minimalnih znachen vikoristovuvatisya indeks po vidpovidnij kolonci kolonok bez obmezhen Dlya poshuku chisla ryadkiv v tablici vikoristovuyetsya indeks po pervinnomu klyuchu yaksho takij ye Ce pov yazano z tim sho SUBD ne zberigaye i ne mozhe zberigati chislo ryadkiv v tablici a skanuvannya indeksu po pervinnomu klyuchu najmensh resursoyemnih Yaksho zapitanij poryadok vibirki zbigayetsya z poryadkom odnogo abo bilshe indeksiv to vikonuyetsya ocinka mozhlivosti skanuvannya odnogo z takih indeksiv cilkom Yaksho indeks mistit vsi kolonki neobhidni dlya otrimannya rezultatu to skanuvannya tablici ne vidbuvayetsya Yaksho optimizator vikoristovuye cej faktor to mozhna priskoriti vibirku z tablici dlya specializovanih zapitiv shlyahom vklyuchennya v indeks nadlishkovih kolonok yaki budut vilucheni bezposeredno pri poshuku po klyuchu Podibnij metod priskorennya zapitiv slid vikoristovuvati oberezhno Div TakozhSemantichna optimizaciya zapitiv SUBD Plan zapituLiteraturaDejt K Dzh Vvedenie v sistemy baz dannyh 2001 Iz vo Vilyams ISBN 5 8459 0138 3 Konnoli T Begg K Bazy dannyh Proektirovanie realizaciya i soprovozhdenie Teoriya i praktika Iz vo Vilyams M 2003 ISBN 5 8459 0527 3 Donald Knut 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 S 240 ISBN 978 0321534965 PosilannyaKristin Bennett Michael C Ferris Yannis E Ioannidis A Genetic Algorithm for Database Query Optimization 1991 Proceedings of the Fourth International Conference on Genetic Algorithms Michael Stillger Myra Spiliopoulou 1996 Genetic Programming in Database Query Optimization Institut fur Informatik Humboldt Universitat zu Berlin