ОПТИМІЗАЦІЯ ЗАПИТІВ

Розглянемо чотири стадії процесу оптимізації запитів, який схематично представлений на рис 181

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

1 Перетворення запиту у внутрішню форму

2 Перетворення запиту в канонічну форму

3 Вибір потенційних низькорівневих процедур

4 Генерація різних варіантів планів обчислення запиту і вибір плану з мі мінімальними витратами

Перейдемо до докладного розгляду кожної стадії процесу оптимізації

Стадія 1 Перетворення запиту у внутрішню форму

На цій стадії виконується перетворення початкового запиту в деякий внутрішнє подання, більш зручне для машинної обробки В результаті з розгляду повністю виключаються конструкції суто зовнішнього рівня (наприклад, різноманітні варіанти конкретного синтаксису використовуваної мови запитів) і готується грунт для подальших стадій оптимізації

Примітка Обробка уявлень (тобто процес заміни посилань на подання виразами, визначальними відповідні подання) також виконується на цьому етапі

Виникає очевидне питання: Яке формальне подання має використовуватися для внутрішнього подання запиту”. Незалежно від того, який саме варіант формального представлення буде обраний, він повинен бути достатньо повним, щоб допускати подання будь-яких запитів, які можуть бути визначені на зовнішньому мовою запитів Крім того, обраний спосіб формального представлення повинен бути нейтральним, наскільки це можливо, в тому сенсі, що він не повинен заздалегідь зумовлювати наступні оптимізаційні рішення Найчастіше для внутрішнього подання запитів використовується та чи інша модифікаціяабстрактного синтаксичного дерева, яке в цьому випадку називають деревом запиту Наприклад, на рис 182 показано дерево для запиту, рассматривавшегося вище в цьому ж розділі в розділі

182 (Визначити імена постачальників деталі з номером Р2)

Рис 182 Дерево реалізації запиту Визначити імена постачальників деталі з номером Р2

Однак для наших цілей найзручніше припустити, що для внутрішнього подання запитів використовується один з тих формальних методів, з якими ми вже знайомі: реляційна алгебра або реляційне числення У цьому випадку дерево запиту, подібне представленому на рис 182, можна розглядати просто як альтернативний схематичний варіант подання деякого виразу, записаного в системі

позначень одного з двох запропонованих вище формальних методів (реляційна алгебра або реляційне числення) Припустимо, що обраний формальний метод – реляційна алгебра З цього моменту будемо вважати, що внутрішнім поданням дерева запиту, показаного на рис 182, є наступне алгебраїчне вираження1:

({SP JOIN S) WHERE P # = Р # (Р2)) {SNAME}

Стадія 2 Перетворення запиту в канонічну форму

На цій стадії оптимізатор виконує кілька операцій оптимізації, які гарантовано є прийнятними незалежно від реальних значень даних та існуючих шляхів доступу до них Суть в тому, що зазвичай реляційні мови дозволяють сформулювати будь-які запити (за винятком хіба що найпростіших) декількома різними (принаймні, зовні) способами Наприклад, навіть простий запит Визначити імена постачальників деталі з номером Р2 мовою SQL може бути записаний буквально десятками способов2, не рахуючи таких тривіальних варіантів, як заміна А = в на в = А чи р AND q на q AND p Продуктивність обчислення запиту не повинна залежати від форми запису запиту, яку вибрав користувач Тому наступний етап в обробці запиту – перетворення його внутрішнього представлення в деяку еквівалентну канонічну форму (Див наступний абзац) Призначенням даного перетворення є виключення зовнішніх відмінностей в еквівалентних представлених запиту і, що більш важливо, пошук подання запиту, в деякому розумінні більш ефективного порівняно з вихідним поданням

Зауваження про канонічну формі Поняття канонічної форми є центральним у багатьох розділах математики та повязаних з нею дисциплінах Канонічна форма може бути визначена таким чином Нехай Q – безліч обєктів (запитів) і нехай існує поняття про їх еквівалентності (а саме, запити ql і q2 еквівалентні тоді і тільки тоді, коли дають ідентичні результати) Тоді підмножина З безлічі Q є безліччю канонічних форм для запитів з безлічі Q в сенсі певної вище еквівалентності тоді і тільки тоді, коли кожному обєкту q з безлічі Q відповідає тільки один обєкт із з безлічі с У цьому випадку говорять, що обєкт з є канонічною формою обєкта q Всі цікавлять нас властивості, якими володіє обєкт q, притаманні також обєкту с Тому, щоб довести різні цікавлять нас результати, достатньо вивчити менш потужне безліч обєктів С, а не більш потужне безліч Q

Повернемося до основної теми обговорення Щоб перетворити результати виконання стадії 1 в деяку еквівалентну, але більш ефективну форму, оптимізатор використовує певні і добре відомі правила, або закони перетворення Нижче наведено приклад такого правила Тут вираз

1 Фактично деякі комерційні оптимізатори SQL призначені саме для преобразо вання подібного первісного запиту в еквівалентне вираження реляційної алгебри

2 Але слід зауважити, що особливо сприйнятливим до цієї проблеми є мова SQL (див упр 812 в главі 8, а також [418]) Інші мови (наприклад, мови реляційної алгебри або числення) зазвичай не пропонують таку ж кількість способів створення еквівалентних виразів Така зайва гнучкість мови SQL насправді значно ускладнює життя розробникам СУБД (Не кажучи вже про користувачів), оскільки здійснення функцій оптимізатора стає набагато складніше

(A JOIN В) WHEREобмеження, що поширюється наА може бути перетворено в еквівалентну, але більш ефективне вираз

(  A WHERE   обмеження, що поширюється наА) JOIN В

Подібне перетворення коротко розглядалася в розділі 76 глави 7 Крім того, воно було описано вище, при обговоренні прикладу в розділі 182, який ясно продемонстрував, навіщо потрібні подібні перетворення Багато інших правила перетворення описуються нижче, в розділі 184

Стадія 3 Вибір потенційних низькорівневих процедур

Після перетворення внутрішньої форми запиту в більш відповідну (канонічну) форму, оптимізатор повинен визначити, як слід виконувати запит, представлений у цій канонічній формі На даній стадії беруться до уваги такі фактори, як наявність індексів та інших фізичних шляхів доступу, статистичний розподіл існуючих значень даних, фізична кластеризація збережених даних і тп Зверніть увагу на те, що на стадіях 1 і 2 цих аспектів зовсім не приділялося уваги

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

Для кожної низькорівневої операції (а також, можливо, для декількох часто зустрічаються комбінацій подібних операцій) оптимізатор має набір низькорівневих процедур реалізації Наприклад, існує набір процедур для реалізації операції скорочення: за умовою рівності певному значенню потенційного ключа на основі індексованого атрибута, за яким виконується скорочення на основі хешірованного атрибута і тд Приклади таких процедур наведені нижче, в розділі 187 (див також [187], [1812])

З кожною процедурою повязана параметрезованих формула вартості, що дозволяє оцінити вартість виконання процедури (тобто рівень витрат, необхідних для її виконання) Найчастіше вартість визначається шляхом підрахунку кількості необхідних

дискових операцій введення-виведення, але деякі системи враховують також час використання процесора і інші фактори Ці формули вартості застосовуються на стадії 4 (див наступний підрозділ) В [187] – [1812] обговорюються і аналізуються формули вартості для різних процедур реалізації при різних вихідних припущеннях (див також розділ 187)

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

3 Безумовно, що в даному контексті поняття рівня є відносним По суті, згадані тут оператори низького рівня є операторами реляційної алгебри (зєднання, обмеження і тд), а вони зазвичай розглядаються як оператори високого рівня

про взаємні залежностях, згадуваних вище, оптимізатор вибирає одну або кілька процедур-кандидатів для кожної низькорівневої операції в запиті Цей процес зазвичай називають вибором шляху доступу (Див також [1833])

Примітка Слід зазначити, що в [1833] термін вибір шляху доступу використовується для посилання на визначені в даній главі стадії 3 і 4, а не тільки на стадію 3 Дійсно, на практиці дуже важко розмежувати, де закінчується одна стадія і починається інша просто стадія 3 більш-менш плавно переходить в стадію4

Стадія 4 Генерація різних варіантів планів обчислення запиту і вибір плану з мінімальними витратами

На останній стадії процесу оптимізації створюється набір потенційних планів запиту, після чого здійснюється вибір кращого (тобто найменш дорогого) плану виконання запиту Кожен план виконання формується як комбінація деякого набору потенційних процедур реалізації, причому кожної низькорівневої операції в запиті відповідає одна процедура Відзначимо, що зазвичай для запиту, що поступив може існувати багато планів виконання запиту (можливо, навіть занадто багато) На практиці, ймовірно, не варто генерувати всі можливі плани запиту, так як одні з них можуть бути комбінаторними версіями інших планів виконання цього ж запиту, і сам процес вибору найбільш ефективного плану може стати надмірно дорогим При виборі плану з найменшою вартістю рекомендується (можливо, навіть потрібно) керуватися деякими евристичними правилами, що дозволяють обмежити кількість аналізованих планів запитів розумними межами, але см [1853] Практику обмеження кількості запитів розумними межами інакше називають скороченням простору пошуку, оскільки її можна розглядати і як зменшення діапазону аналізованих оптимізатором варіантів {Простору пошуку) до контрольованих меж

Безсумнівно, для вибору плану з найменшою вартістю необхідний метод визначення вартості будь-якого можливого плану По суті, вартість плану – це просто сума вартостей окремих процедур, що входять в його складу Тому завдання оптимізатора зводиться до обчислення формул вартості для кожної окремої процедури Основна проблема полягає в тому, що формули вартості виконання процедури залежать від розміру відносини (або відносин), яке обробляє ця процедура Оскільки всі запити, за винятком найпростіших, вимагають створення деяких проміжних результатів виконання (щонайменше, концептуально), оптимізатор повинен бути здатний оцінити розмір цих проміжних результатів і використовувати отримані значення при обчисленні формул вартості На жаль, розміри проміжних наборів даних сильно залежать від конкретних значень збережених даних, тому точна оцінка вартості може виявитися досить складним завданням В [182], [183] обговорюються деякі підходи до вирішення цієї проблеми і наводяться посилання на інші публікації

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*