Семантична оптимізація запитів СУБД - процес валідації та перетворення синтаксичного дерева запиту в форму, яка придатна для подальших кроків оптимізації.
На цій стадії виконується:
- Перетворення запитів у канонічну форму;
- Розкриття уявлень;
- Перетворення підзапитів у сполуки;
- Спуск предикатів;
- Спрощення умов і розподіл предикатів;
- Перетворення дерева умов до шляхів вибірки.
Перетворення запитів до канонічної форми
Запити зводяться до канонічної форми, тобто переписуються так, щоб вони містили мінімальну кількість операторів SELECT (з'єднання-фільтрація-проєкція). Скрізь, де можливо, запит повинен бути зведений до форми єдиного оператора SELECT. Це може дозволити наступним фазам оптимізації згенерувати значно ефективніший (на 2-3 порядки) план виконання для складних запитів.
Розкриття уявлень
Розкриття уявлень застосовується для того, щоб підсумковий запит містив посилання тільки на матеріалізовані відносини (таблиці) і можливості використовувати конвеєрну обробку даних.
Початковий запит | Результат |
---|---|
( T where cond1 ) where cond2 | T where ( cond1 and cond2) |
Перетворення підзапитів у сполуки
Перетворення підзапитів у сполуки є необхідним для застосування конвеєрної обробки даних та мінімізації обсягу результатів підзапитів, акумульованих у тимчасовій дисковій чи оперативній пам'яті.
Початковий запит | Результат |
---|---|
select distinct T.a from T where T.b in ( select T1.b from T1 where T1.c < T.c) | select distinct T.a from T,T1 where T.b = T1.b and T1.c < T.c |
Спуск предикатів
Початковий запит | Результат |
---|---|
( A join B) where condA and condB | (A where condA) join (B where condB) |
Спрощення умов та розподіл предикатів
Спрощення умов
Виконується шляхом перетворення дерева логічних операцій у КНФ та спрощення отриманої логічної функції.
Перетворення дерева логічних операцій у КНФ виконується наступним чином:
- 1. Для всіх диз'юнкцій, які входять у прямому вигляді, застосовується розподільний закон:
P OR (Q AND R) = (P OR Q) AND (P OR R) (P AND Q) OR R = (P OR R) AND (Q OR R)
- Для всіх диз'юнкцій, що входять у інверсному вигляді, застосовується правило де Моргана
NOT (P OR Q) = NOT P AND NOT Q
Перетворення триває рекурсивно до тих пір, поки дерево не буде складатися із кон'юнкцій .
Отримана логічна функція знаходиться у кон’юнктивній нормальній формі, проте вона надлишкова. Для спрощення застосовують методи оптимізації логічних функцій, такі як або Куайна-Мак-Класкі.
Розподіл предикатів
Розподіл предикатів виконується
- Для всіх предикатів виду:
A.B pred C
Для яких існує предикат
A.B = D.E
Як результат - отримаємо предикат
D.B pred C
де C - константа; A, D - відношення; B, E - порівнювані атрибути. Це спрощення виконується на основі припущення, що початковий предикат A.B pred C може бути ефективнішим для відношення D.
- Для кожної умови об'єднання виду:
A.B pred D.E
генерується обернена умова
D.E inversed pred A.B
для можливості виконати з'єднання в оберненому порядку.
Перетворення дерева умов у шляху вибірки
Після спрощення дерева умов кожна кон'юнкція у дереві - це шлях вибірки. Предикати всередині кон'юнкцій групуються за належністю відносин. Для отримання підсумкового результату необхідно об'єднати результати кожного зі шляхів вибірки.
Література
- Дейт К. Дж. Введение в системы баз данных. 2001. Из-во: Вильямс.
- Конноли Т., Бегг К. Базы данных. Проектирование, реализация и сопровождение. Теория и практика. Из-во: Вильямс (М., 2003)
- Кимельман Михаил Леонидович. Исследование и разработка языковой подсистемы SQL сервера. Диссертация на соискание ученой степени кандидата физико-математических наук. Москва 1996
Див. також
Це незавершена стаття про бази даних. Ви можете проєкту, виправивши або дописавши її. |
Ця стаття потребує додаткових для поліпшення її . (червень 2017) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Semantichna optimizaciya zapitiv SUBD proces validaciyi ta peretvorennya sintaksichnogo dereva zapitu v formu yaka pridatna dlya podalshih krokiv optimizaciyi Na cij stadiyi vikonuyetsya Peretvorennya zapitiv u kanonichnu formu Rozkrittya uyavlen Peretvorennya pidzapitiv u spoluki Spusk predikativ Sproshennya umov i rozpodil predikativ Peretvorennya dereva umov do shlyahiv vibirki Peretvorennya zapitiv do kanonichnoyi formiZapiti zvodyatsya do kanonichnoyi formi tobto perepisuyutsya tak shob voni mistili minimalnu kilkist operatoriv SELECT z yednannya filtraciya proyekciya Skriz de mozhlivo zapit povinen buti zvedenij do formi yedinogo operatora SELECT Ce mozhe dozvoliti nastupnim fazam optimizaciyi zgeneruvati znachno efektivnishij na 2 3 poryadki plan vikonannya dlya skladnih zapitiv Rozkrittya uyavlen Rozkrittya uyavlen zastosovuyetsya dlya togo shob pidsumkovij zapit mistiv posilannya tilki na materializovani vidnosini tablici i mozhlivosti vikoristovuvati konveyernu obrobku danih Pochatkovij zapit Rezultat T where cond1 where cond2 T where cond1 and cond2 Peretvorennya pidzapitiv u spoluki Peretvorennya pidzapitiv u spoluki ye neobhidnim dlya zastosuvannya konveyernoyi obrobki danih ta minimizaciyi obsyagu rezultativ pidzapitiv akumulovanih u timchasovij diskovij chi operativnij pam yati Pochatkovij zapit Rezultatselect distinct T a from T where T b in select T1 b from T1 where T1 c lt T c select distinct T a from T T1 where T b T1 b and T1 c lt T cSpusk predikativ Pochatkovij zapit Rezultat A join B where condA and condB A where condA join B where condB Sproshennya umov ta rozpodil predikativSproshennya umov Vikonuyetsya shlyahom peretvorennya dereva logichnih operacij u KNF ta sproshennya otrimanoyi logichnoyi funkciyi Peretvorennya dereva logichnih operacij u KNF vikonuyetsya nastupnim chinom 1 Dlya vsih diz yunkcij yaki vhodyat u pryamomu viglyadi zastosovuyetsya rozpodilnij zakon P OR Q AND R P OR Q AND P OR R P AND Q OR R P OR R AND Q OR R Dlya vsih diz yunkcij sho vhodyat u inversnomu viglyadi zastosovuyetsya pravilo de MorganaNOT P OR Q NOT P AND NOT Q Peretvorennya trivaye rekursivno do tih pir poki derevo ne bude skladatisya iz kon yunkcij Otrimana logichna funkciya znahoditsya u kon yunktivnij normalnij formi prote vona nadlishkova Dlya sproshennya zastosovuyut metodi optimizaciyi logichnih funkcij taki yak abo Kuajna Mak Klaski Rozpodil predikativ Rozpodil predikativ vikonuyetsya Dlya vsih predikativ vidu A B pred C Dlya yakih isnuye predikat A B D E Yak rezultat otrimayemo predikat D B pred C de C konstanta A D vidnoshennya B E porivnyuvani atributi Ce sproshennya vikonuyetsya na osnovi pripushennya sho pochatkovij predikat A B pred C mozhe buti efektivnishim dlya vidnoshennya D Dlya kozhnoyi umovi ob yednannya vidu A B pred D E generuyetsya obernena umova D E inversed pred A B dlya mozhlivosti vikonati z yednannya v obernenomu poryadku Peretvorennya dereva umov u shlyahu vibirki Pislya sproshennya dereva umov kozhna kon yunkciya u derevi ce shlyah vibirki Predikati vseredini kon yunkcij grupuyutsya za nalezhnistyu vidnosin Dlya otrimannya pidsumkovogo rezultatu neobhidno ob yednati rezultati kozhnogo zi shlyahiv vibirki LiteraturaDejt 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 Kimelman Mihail Leonidovich Issledovanie i razrabotka yazykovoj podsistemy SQL servera Dissertaciya na soiskanie uchenoj stepeni kandidata fiziko matematicheskih nauk Moskva 1996Div takozhPlan zapitu Ce nezavershena stattya pro bazi danih Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Cya stattya potrebuye dodatkovih posilan na dzherela dlya polipshennya yiyi perevirnosti Bud laska dopomozhit udoskonaliti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Zvernitsya na storinku obgovorennya za poyasnennyami ta dopomozhit vipraviti nedoliki Material bez dzherel mozhe buti piddano sumnivu ta vilucheno cherven 2017