yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Різні конспекти лекцій->Содержание->2.9 Порядок виконання оператора SELECT

Організація баз даних і знань

2.9 Порядок виконання оператора SELECT

Для того щоб зрозуміти, як виходить результат виконання оператора SELECT, розглянемо концептуальну схему його виконання. Ця схема є саме концептуальною, тому що гарантується, що результат буде таким, якби він виконувався крок за кроком відповідно до цієї схеми.

Стадія 1. Виконання одиночного оператора SELECT

Якщо в операторі присутні ключові слова UNION, EXCEPT й INTERSECT, то запит розбивається на кілька незалежних запитів, кожний з яких виконується окремо:

Крок 1 (FROM). Обчислюється прямий декартовий добуток всіх таблиць, зазначених в обов'язковому розділі FROM. У результаті кроку 1 одержуємо таблицю A.

Крок 2 (WHERE). Якщо в операторі SELECT є присутнім розділ WHERE, то сканується таблиця A, отримана при виконанні кроку 1. При цьому для кожного рядка з таблиці A обчислюється умовний вираз, наведений у розділі WHERE. Тільки ті рядки, для яких умовний вираз повертає значення TRUE, включаються в результат. Якщо розділ WHERE опущений, то відразу переходимо до кроку 3. Якщо в умовному виразі беруть участь вкладені підзапити, то вони обчислюються відповідно до даної концептуальної схеми. У результаті кроку 2 одержуємо таблицю B.

Крок 3 (GROUP BY). Якщо в операторі SELECT є присутнім розділ GROUP BY, то рядки таблиці B, отриманої на другому кроці, групуються у відповідності зі списком групування, наведеним у розділі GROUP BY. Якщо розділ GROUP BY опущений, то відразу переходимо до кроку 4. У результаті кроку 3 одержуємо таблицю С.

Крок 4 (HAVING). Якщо в операторі SELECT є присутнім розділ HAVING, то групи, що не задовольняють умовному виразу, наведеному в розділі HAVING, виключаються. Якщо розділ HAVING опущений, то відразу переходимо до кроку 5. У результаті кроку 4 одержуємо таблицю D.

Крок 5 (SELECT). Кожна група, отримана на кроці 4, генерує один рядок результату в такий спосіб. Обчислюються всі скалярні вирази, зазначені у розділі SELECT. За правилами використання розділу GROUP BY, такі скалярні вирази повинні бути однаковими для всіх рядків усередині кожної групи. Для кожної групи обчислюються значення агрегатних функцій, наведених у розділі SELECT. Якщо розділ GROUP BY був відсутній, але в розділі SELECT є агрегатні функції, то вважається, що є всього одна група. Якщо немає ні GROUP BY, ні агрегатних функцій, то вважається, що є стільки груп, скільки рядків відібрано до даного моменту. У результаті кроку 5 одержуємо таблицю E, що містить стільки колонок, скільки елементів наведено в розділі SELECT і стільки рядків, скільки відібрано груп.

Стадія 2. Виконання операцій UNION, EXCEPT, INTERSECT

Якщо в операторі SELECT були присутні ключові слова UNION, EXCEPT й INTERSECT, то таблиці, отримані в результаті виконання 1-ої стадії, поєднуються, віднімаються або перетинаються.

Стадія 3. Впорядкування результату

Якщо в операторі SELECT є присутнім розділ ORDER BY, то рядки, отриманої на попередніх кроках таблиці, впорядковуються у відповідності зі списком упорядкування, наведеному у розділі ORDER BY.

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

Насправді в РСКБД є оптимізатор, функцією якого є знаходження такого оптимального алгоритму виконання запиту, що гарантує одержання правильного результату. Схематично роботу оптимізатора можна подати у вигляді послідовності декількох кроків:

Крок 1 (Синтаксичний аналіз). Запит, який надійшов, піддається синтаксичному аналізу. На цьому кроці визначається, чи правильно взагалі (з погляду синтаксису SQL) сформульований запит. У ході синтаксичного аналізу виробляється деяке внутрішньє подання запиту, використовуване на наступних кроках.

Крок 2 (Перетворення в канонічну форму). Запит у внутрішньому поданні піддається перетворенню у деяку канонічну форму. При перетворенні до канонічної форми використовуються як синтаксичні, так і семантичні перетворення. Синтаксичні перетворення (наприклад, приведення логічних виразів до кон'юнктивної або диз'юнктивної нормальної форми, заміна виразів "x AND NOT x" на "FALSE", і т.п.) дозволяють одержати нове внутрішнє подання запиту, синтаксично еквівалентне вихідному, але стандартне у деякому змісті. Семантичні перетворення використовують додаткові знання, якими володіє система, наприклад, обмеження цілісності. У результаті семантичних перетворень виходить запит, синтаксично не еквівалентний вихідному, але результат, що дає, той самий.

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

Крок 4. (Виконання плану запиту). На цьому кроці план, обраний на попередньому кроці, передається на реальне виконання.

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

 

26