Виконання запитів

Размещено на http://www.allbest.ru/

Реферат

На тему “Виконання запитів”

Львів 2012

Зміст

запит алгебраїчний оператор алгоритм

1 Реляційні оператори

2. Оптимізація запиту

3. Висновки

4. Глосарій

5. Вправи

1 Реляційні оператори

Кожний SQL оператор може розбиватись на частини і кожна частина пов'язана з одним реляційним оператором, кожен з яких працює з однією або більше таблицями. Нижче наведені основні реляційні операції:

Вибірка (Selection) - вибирання підмножини рядків (конкретизують умовою у WHERE виразі).

Проектування (Projection) - видалення деяких стовпчиків з результату (SELECT і SELECT DISTINCT вирази).

Об'єднання (Join) - об'єднання таблиць (реляції).

Алгебраїчні оператори UNION, DISTINCT і EXCEPT на таблицях (реляції).

Агрегація (Aggregation) - використання об'єднувальних функцій SUM, MIN, і т.п. і GROUP BY виразів.

Реалізація вибірки

Давайте розглянемо приклад.

SELECT *

FROM Emp e

WHERE e.Ename < 'C' AND e.Sal > 1000;

Давайте припустимо, що умова у виразі WHERE є у формі з'єднання. (Між іншим, ми знаємо з лекцій Дискретної Математики, що кожна логічна формула може бути перетворена до рівноцінної форми роз'єднання з'єднань простих умов, - до так званої нормальної форми.) Є два методи для реалізації вибірки:

послідовне сканування цілого файлу даних (операція сканування)

вибір "найвибірковішого" поля, яке з'являється в простій умові з'єднання і яке має індекс, а потім виконується пошук використовуючи цей індекс (це означає, ми перетворюємо, WHERE умову у форму об'єднань: p AND Rest (Залишок), де p є простим предикатом, що стосується єдиного поля в таблиці). Найкраще, коли індекс базується на хеші (hash) для вибірки тотожностей і коли індекс - це B+ дерево (B+ tree) для вибірки діапазону.

Рекомендується вибрати другий метод в наступних трьох ситуаціях:

коли індекс є первинним, унікальним або внутрішнім хешом (hash) і пошук базується на тотожності;

коли індекс є кластерним і пошук базується на вибірці діапазону;

коли передбачається не великий за розміром результат (не велика кількість рядків) (тобто, коли пошук за індексом є вибірковим) - наприклад вибір максимум до 5-10% рядків з цілої таблиці.

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

В спеціальному випадку, коли всі елементи SELECT і WHERE виразів належать пошуковому ключу одного індексу - то достатньо пройти через цей індекс. Цей метод названий тільки-індексною стратегією (only-index strategy). Інколи варто додати до пошукового ключа одне або більше полів, щоб використати цей метод, тобто ми можемо подумати про додавання платні (salary) та/або номера департаменту (department's number) до індексу, базованого на імені працівника (employee's name). Таке використовування індексу нагадує використання реального перегляду (view).

Реалізація проектування

Розглянемо приклад:

SELECT DISTINCT e.Job

FROM Emp e;

Коли немає оператора DISTINCT - достатньо, просканувати цілий файл і порахувати вирази у SELECT списку.

Тільки є проблема з SELECT DISTINCT виразом, який вимагає виключення повторень рядків - вона може вирішитися за допомогою сортовування рядків у результуючій множині.

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

Коли всі елементи SELECT і WHERE виразів належать пошуковому ключу одного індексу, то достатньо пройти тільки через цей індекс без того, щоб діставати файл з записами даних взагалі (тільки-індексна стратегія, only-index strategy).

Реалізація набору алгебраїчних операторів

UNION, DISTINCT і EXCEPT оператори виконуються подібно до SELECT DISTINCT - вони вимагають видалення повторюваних рядків, за допомогою внутрішнього сортування або хешування.

INTERSECT є специфічною випадком об'єднання (join). Наприклад, вираз:

SELECT Deptno FROM Dept

INTERSECT

SELECT Deptno FROM Emp;

рівноцінний:

SELECT d.Deptno

FROM Dept d, Emp e

WHERE d.Deptno=e.Deptno;

Методи для реалізації об'єднань обговорюються пізніше в цій лекції.

Реалізація агрегування

Без GROUP BY

Розглянемо приклад:

SELECT AVG(e.Sal)

FROM Emp e;

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

З GROUP BY

Розглянемо приклад:

SELECT e.Job, AVG(e.Sal)

FROM Emp e

GROUP BY e.Job;

Є можливим просканувати цілий файл записів, поділяючи записи по групах, що відповідають значенням у GROUP BY умові. Замість сканування цілого файлу записів іноді достатньо, щоб сканувати тільки індексний файл, а саме у разі, коли всі елементи, що є у SELECT, WHERE, GROUP BY і HAVING виразах, є підмножиною індексного пошукового ключа (тільки-індексна стратегія, only-index strategy). Інший метод для реалізації групування застосовує хешування.

Реалізація об'єднань

Для того, щоб представити методи об'єднань таблиць, розглянемо об'єднання по одній колонці для простоти. Давайте припустимо, що ми зацікавлені в тому, щоб об'єднати дві таблиці E і D по колонці i в E і колонці j в D. Це означає, що ми припускаємо, що приєднуюча умова є Ei=Dj.

Для того, щоб порівняти ціну специфічних методів ми використаємо наступні скорочення:

M - кількість сторінок у таблиці E ;

pE - кількість записів на сторінці для E;

N - кількість сторінок у таблиці D ;

pD - кількість записів на сторінці для D ;

pas - середнє число записів у D, що відповідають запису в E.

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

SELECT E.Ename, D.Loc

FROM Emp E, Dept D

WHERE E.Deptno = D.Deptno;

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

Алгоритм простих вкладених циклів

foreach row e in E do

foreach row d in D do

if ei == dj then add <e, d> to computed result;

Для кожного рядку з таблиці E ми скануємо всі рядки в таблиці D. Ціна - це M + (pE * M) * N.

Таблицю E називають зовнішньою таблицею (об'єднання), таблиця D називають внутрішньою таблицею (об'єднання). Як ми можемо бачити, шаблон не симетричний між M і N так, що це є критичним, яку таблицю ми вибираємо зовнішньою, а яку внутрішньою для об'єднання.

Очевидне поліпшення можна досягатися наступним шляхом: для кожної сторінки в E вибрати кожну сторінку в D. Ціна - M + M*N. Ми і далі будемо використовувати метод Простих Вкладених Циклів разом з цим вдосконаленням.

Алгоритм індексованих вкладених циклів

{E -зовнішня таблиця об'єднання, D внутрішня таблиця об'єднання, на приєднуючій колонці Dj в D встановлений індекс}

foreach row e in E do

{ взяти ei значення приєднуючої колонки Ei і, використовуючи індекс на Dj, знайти всі рядки d, які мають те ж значення в приєднуючій колонці Dj (ei == dj) - об'єднати ці два рядки <e,d> і додати до результату }

Ціна:

M + ( ( M * pE) * середня вартість визначення відповідних рядків у D )

Для кожного ряду в E ми зпочатку знаходимо входження даних у індекс для колонки Dj. Ціна цього кроку залежить від індексу. Це:

~ 1.2 - для хеш-індексу;

~ 3 - для B+ дерева.

Знайшовши входження даних у індекс для колонки Dj ми рухаємося до відповідних рядків у файлі записів для D. Вартість цього кроку знову залежить від індексного типу.

Для внутрішнього хешованого індексу ціна складає 0, що дає повну ціну приблизно M + 1.2 M * pE.

Для зовнішнього первинного або унікальної хешу ціна індексу складає 1, що дає повну ціну приблизно M + 2.2 M * pE.

Для внутрішнього кластерного індексу (на дереві B+) ціна складає 0, що дає повну вартість приблизно M + 3 M * pE.

Для зовнішнього (на дереві B+) первинного або унікального індексу ціна складає 1, що дає повну ціну приблизно M + 4 M * pE.

Для зовнішнього хешованого індексу ціна є pas (ми нагадуємо, що pas - це середнє число рядків в D, що відповідають рядку в E), що дає повну ціну приблизно M + ( 1.2 + pas ) ( M * pE).

Для зовнішнього індексу (на дереві B+) ціна - це також M + ( 3 + pas ) ( M * pE).

У випадках 1-4 ціна відносно мала - лінійна до числа рядків у зовнішній таблиці і не залежить від числа рядків у внутрішній таблиці.

У випадках 5 і 6 ціна дуже залежить від вибірковості пошуку за індексом - виражається у вище згаданій формулі pas параметром і може бути дуже великою (навіть квадратично до числа рядків в зовнішній і внутрішній таблицях).

Використання кластера таблиці

Ми можемо підготуватися краще для частих об'єднань двох або більше таблиць за допомогою розміщення їх в кластері з ключем, що є об'єднуючою колонкою обох таблиць. Об'єднання таблиць у кластері робить операцію об'єднання як єдину дію, нібито проглядаючи одну таблицю. Реалізація нашого зразкового запиту була б швидше, якщо таблиці Emp та Dept були б розміщені в одному кластері, як це було у Лекції 3.

Більше інформації про реалізацію і використовування кластера буде подано в наступній лекції, коли ми будемо обговорювати індексні структури в системі Oracle DBMS.

Алгоритм об'єднання сортованого злиття

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

Вартість алгоритму об'єднання сортованого злиття є близько 8M + 8N + (M+N) = 9M+9N операцій вводу/виводу.

Алгоритм хешованого об'єднання

Розмістити рядки з таблиць E і D у сегментах за допомогою використовування хеш-функції h1, визначеної для значень з об'єднуючих колонок. Сегменти запам'ятовують на диску.

Розглянемо відповідні сегменти з таблиць E і D шукаючи пари рядків e і d, для яких ei=dj. Немає необхідності домовлятися про рядки з різних сегментів - тому, що на таких рядах, значення хеш-функції інше, так що значення в об'єднувальних колонках також різні. Для кожної відповідної пари рядків, додаємо <e, d> до обчисленого результату.

Якщо розміри однієї з пар відповідних сегментів такі великі, що для кожного з них не достатньо оперативної пам'яті, то ми повинні використати до них іншу хеш-функцію h2 (відмінну від h1) і повторити кроки, описані вище.

Ціна алгоритму хешованого об'єднання, виміряного числом операцій вводу/виводу приблизно рівна ( 2 M + 2 N ) + ( 2 M + 2 N ) + ( M + N ) = 5 M + 5 N (Припускаючи, що ми виконуємо розміщення у сегментах двічі; якщо це були один раз, ціна може бути 3 M + 3 N.)

Об'єднання об'єктних таблиць

Об'єднуючи об'єктні таблиці, ми можемо використовувати посилання (references) і колекції посилань(reference collections). Обидві ці дії, проглядання посилань та проглядання колекцій посилань, швидше, ніж відповідні дії проглядання зовнішніх індексів для реляційних таблиць. Недоліком посилань і колекцій посилань (окрім втрати незалежності від значень фізичної моделі) - це додаткова ціна часу і ціна дискового простору, необхідна, щоб представити і обробити колекції (запис, що включає велику колекцію посилань, може вимагати більш ніж одна сторінку для запису; переміщення до записів, вказаних у посиланнях, вимагає вичитування стількох сторінок, скільки є посилань у колекції.)

Порівняння методів

Коли DBMS хоче об'єднати таблиці, він вираховує можливі методи в наступному порядку:

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

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

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

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

Метод Хешованого Об'єднання кращий щодо середнього числа операцій вводу/виводу, порівняно з методом Сортованого Злиття, але в песимістичному випадку він може бути непридатним.

Метод Хешованого Об'єднання кращий, ніж метод Сортованого Злиття, коли розміри відсортованих файлів відрізняються істотно. Легше перетворити його у паралельну версію, ніж Сортованого Злиття.

Метод Сортованого Злиття кращий, коли розміри відсортованих файлів подібні. Це менш чутливо до відсутності довільності даних і результат об'єднання є відсортованим.

2. Оптимізація запиту

SQL запит декларативний: він конкретизує, що має бути знайдено в базі даних і не як це повинне бути знайдено. Для кожного запиту є декілька шляхів реалізації. Який з них кращий залежить від додаткових обставин. DBMS рахує різні альтернативи, оцінює їх вартість і вибирає можливий кращий, "оптимальний" план. Цей процес називають оптимізація запиту (query optimization) і модуль, який виконує це називається оптимізатором запиту (query optimizer).

В DBMS, запит відразу обробляється аналізатором (parser), який виконує аналіз синтаксису запиту.

Після аналізу синтаксису викликається оптимізатор запиту (query optimizer), який базується на двох головних модулях:

генератор плану (plan generator) - модуль, що генерує можливі плани виконання запиту, і

оцінювач вартості (cost estimator) - модуль, що обчислює ціну виконання запиту згідно даному плану.

При оцінюванні вартості плану, оцінювач вартості використовує статичну інформацію, що записана у словнику даних (каталог системи), як наприклад: число записів у файлі, число сторінок, що містять записи, число різних значень в колонці, розміщення значення в колонці (так звана гістограма даних - data histogram).

Оптимізатор вибирає план з найнижчою ціною і передає дані оцінювачу плану (plan's evaluator) - модуль, що виконує запит.

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

План виконання запиту (query execution plan) включає:

Дерево оператора SQL-оператора цього запиту

метод доступу для кожної таблиці в цьому запиті

метод реалізації для кожної операції відношення в цьому запиті.

Деякі з планів виконання запиту не використовують тимчасові таблиці - ми говоримо, вони виконуються на місці (run in place). Їхня операція схожа на: з певним методом доступу до записів кожної таблиці ми тримуємо тільки курсори, що пробігають по записах у файлах (або можливо по даних у індексному файлі) без запам'ятовування тимчасових таблиць. Таким чином, ми уникаємо записування тимчасових результатів на диск для отримання їх назад пізніше.

Плани, які є у формі ліво-орієнтованого дерева (описані пізніше) у поєднанні з Простими Вкладеними Циклами і Індексними Вкладеними Циклами дозволяють запуск на місці. З другого боку, методи Сортованого Злиття і Хешованого Об'єднання вимагають використовування допоміжних файлів на диску, тому вони не виконуються на місці. Використовування кластера або колекцій посилань також дозволяє виконувати на місці.

Щоб об'єднати разом оператори у плані виконання запиту, використовується правило конвеєрного опрацювання (pipelining). Результат одного оператора передається на вхід іншому оператору. Це означає, що тимчасова таблиця не потрібна, і знову, ми працюємо із "запуском на місці".

Запит відображений у формі дерева операторів SQL-виразу. Наприклад, запит:

SELECT E.Ename

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

E.Mgr=100 AND D.Loc='Oz';

План 1

Найпростіший план для виконання цього запиту:

об'єднати таблиці Emp E і Dept D, використовуючи Прості Вкладені Цикли і для кожного об'єднаного рядка перевірити умову E.Mgr=100 AND D.Loc='Oz';

якщо умова відповідає дійсності, прочитати значення колонки E.Ename і передати його у результуючу множину.

Цей план запускається „на місці” (без тимчасових таблиць) і не використовує індекси. Це не дуже добре.

План 2

Розглянемо наступний альтернативний план:

ми окремо проходимо через Emp E і Dept D разом з вибіркою E.Mgr=100 and D.Loc='Oz', відповідно; результати вибірки записані у дві тимчасові таблиці;

ми використовуємо Об'єднання Сортованого Злиття, щоб виконати об'єднання (як альтернатива, замість Сортованого Злиття ми можемо використати Хешоване Об'єднання);

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

Головна відмінність від попереднього плану полягає в тому, що перед об'єднанням виконуються перші вибірки. Є надія, що вони істотно обмежать число об'єднаних записів у порівнянні з попереднім планом. Перед об'єднанням, окрім вибірки ми могли б також виключити невикористані стовпчики. Іншими словами, ми могли б виконувати проектування Ename,Deptno для Emp і Deptno для Dept. В цьому випадку, ми могли б зменшити розмір тимчасових таблиць T1 і T2 і відповідно число операцій вводу/виводу.

Невеликі зміни у згаданому вище плані можуть включати заміну операції сканування на пошук за індексами на колонах E.Mgr і D.Loc, відповідно. У випадку індексів: внутрішнє хешування, кластерування на B+ дереві або з гарною вибірковістю, зміна повинна істотно пришвидшити весь процес обчислення результату запиту.

План 3

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

Викорстовуючи хешований індекс на E.Mgr ми вибираємо ряди, що задовольняють умову E.Mgr=100.

Для кожного отриманого рядку з E, використовуючи індекс на D.Deptno, ми знаходимо відповідні рядки (D.Deptno=E.Deptno) з таблиці D.

Ми об'єднуємо разом обидва рядки і перевіряємо, чи справджується умова D.Loc='Oz', і в кінці ми виконуємо проектування для колонки E.Ename.

ідмітьте що:

Emp E є зовнішньою таблицею об'єднання. Dept D є внутрішньою таблицею об'єднання.

Ми використовуємо метод Об'єднання Індексними Вкладеними Циклами разом з конвеєрною обробкою. Немає необхідності запам'ятати результат вибірки як тимчасове відношення - використовується конвеєрна обробка і обробляється все на місці.

Гарна вибірковість пошукової умови E.Mgr=100 є дуже важливою тому, що число працівників з номером менеджера 100 не велике.

У разі поганої вибірковості могло б допомогти, якщо мати внутрішній хешований індекс для E.Mgr.

Інакше сканування цілої таблиці E може бути кращим.

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

Генерування планів виконання запиту оптимізатором запиту

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

Через велике число можливостей, оптимізатор запиту обмежується до певного класу дерев - ліво-орієнтованими деревами (left-oriented trees). Ліво-орієнтоване дерево має "ядро" у формі гілки вузлів, де кожний наступний вузол - це лівий наступник попереднього, тільки вузли цієї гілки можуть мати ступінь два і вони містять оператор об'єднання (решта вузлів мають ступінь 0 або 1).

З трьох дерев тільки середнє є ліво-орієнтованим. Результуючі плани ліво-орієнтованих дерев дозволяють конвеєрне виконання запитів "на місці", тобто без тимчасових файлів.

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

реба вімітити, що запит, який містить n-1 оператор об'єднанання і n таблиць, має як мінімум n! ліво-орієнтованих дерев відповідно до n! перестановок таблиць.

Приклад

Фаза 1: Ми генеруємо дерево плану виконання наступного запиту: Emp - зовнішня таблиця, Dept - внутрішня таблиця. (Інше можливе дерево - це варіант першого дерева, де таблиця Dept з лівого і Emp з правого боку.)

Фаза 2: План доступу до рядків з таблиць Emp і Dept

Emp:

Хеш-індекс для Emp.Mgr

Хеш-індекс для Emp.Deptno

Сканування

Dept:

B+ дерево дляDept.Loc

Первинний хеш-індекс дляDept.Deptno

Сканування

Фаза 3: Ми рахуємо кожний план доступу, ми розглядаємо можливі методи об'єднання (SNLJ, INLJ, SMJ, HJ) для плану доступу і вираховуємо наближені витрати за допомогою використовування статистики, зібраної системою, як наприклад число рядків у таблиці, число сторінок у файлі даних і в індексному файлі.

Підзапити

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

Загальні стратегії оптимізації

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

Щоб виконувати вибірку використовується індекс - кращими є первинним індекс, унікальний, кластерний, внутрішній хеш або індекс, заснований на вибірковій умові, - наприклад вибір менш ніж 5-10% всіх записів у файлі. Якщо такий індекс не можливо використати, то замість проглядання індексу краще шукати у цілому файлі послідовно (сканування), поки не виберуться записи, що відповідають заданій умові.

Пробувати об'єднати вибірки з Декартовим добутком для того, щоб ідентифікувати вид об'єднання таблиць.

Щоб виконати об'єднання, треба використати індекс внутрішньої таблиці (найкращі: первинний індекс, унікальний, кластерний, внутрішній хеш або індекс, заснований на вибірковій умові).

Вибрати план, який запускається на місці без тимчасових таблиць, тобто у формі ліво-орієнтованого дерева. Використати конвеєрну обробку для виконання послідовності операторів з одним аргументом, таких як вибірка чи проектування.

Замість об'єднання використати кластер, який також дозволяє виконання на місці.

Якщо можливо, пробувати проглянути індекси, а не таблиці (тільки-індексна стратегія).

Використати обчислені результати матеріалізованих представлень (materialized views).

Шукати загальні підвирази і обчислювати їх тільки один раз.

Обробити файл на початку по-справжньому (індекси, сортування, хешування, матеріалізоване представлення).

Зібрати кількістну статистику, що стосується таблиць, колонок та індексів, - включаючи гістограми даних (розповсюдження значень у стовпцях таблиці). Використати статистику зібрану в каталозі системи.

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

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

3. Висновки

В Лекції 10 ми обговорювали методи реалізації для операцій відношення, які будують блоки цілого SQL запиту. Реалізація цих операторів може точніше настроюватися. В другій частині ми обговорювали правила виконання запитів. Перед тим, як DBMS виконує запит, викликається оптимізатор запиту і ціль його - проаналізувати і знайти кращий можливий план виконання запиту.

4. Глосарій

relational operator - один з операторів: вибірка, проектування, об'єднання, злиття і агрегування. Виконання SQL запиту може грунтуватися на реалізації цих основних операторів.

selection - операція відношення, яка обмежує файл записів до підмножини.

projection - операція відношення, яка обмежує файл записів до вибраних полів.

union - операція відношення, що виконує злиття двох файлів з записами.

aggregation - операція відношення, яка обчислює статистику на даному файлі записів згідно розділенню в групах записів.

join - операція відношення, яка об'єднує два файли записів згідно значенням загального поля.

Simple Nested Loops Join - метод, який обробляє кожний запис із самого початку файлу записів, сканує всі записи з другого файлу, шукає всі пари записів, які можуть об'єднатися.

Index Nested Loops Join - метод, який обробляє кожний запис із самого початку файлу записів, використовує індексний пошук, щоб знайти всі відповідні записи з другого файлу.

Sort Merge Join - метод, який об'єднує дві таблиці за допомогою відсортовування файлів записів по значенням об'єднувальних полів а потім виконання їх злиття.

Hash Join - метод, який об'єднує дві таблиці за допомогою розбиття записів на сегменти по значеннях хеш-функції, порахованої для об'єднувальних колонок, а потім виконання їх злиття.

query optimization - операція, яку виконує DBMS, для аналізу різних планів виконання SQL запиту і вибору самого "оптимального" з них.

query optimizer - модуль DBMS чиє завдання - знайти кращий можливий ("оптимальний") план виконання SQL запиту.

5. Вправи

1. Подумайте про реалізацію комплексної вибірки F1 AND F2, де F1 і F2 є предикатами тотожності. Які можливості ви бачите?

2. Подумайте про реалізацію комплексної вибірки F1 OR F2, де F1 і F2 є предикатами тотожності. Які можливості ви бачите?

3. Поясніть, чому INTERSECT оператор є окремим випадком оператора об'єднання. Який алгоритм об'єднання кращий для INTERSECT?

4. Чи можливо реалізувати проектування швидшим, використовуючи індекс?

5. Чи можливо реалізувати HAVING вираз швидшим, використовуючи індекс?

Размещено на Allbest.ru