РЕАЛІЗАЦІЯ Реляційних ОПЕРАТОРІВ

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

Примітка Ьолее складні прийоми реалізації описані в анотаціях до певних робіт, посилання на які наведені в кінці розділу Див також додаток А

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

1 Операнд PER взагалі не визначає атрибутів (PER TABLE_DEE)

2 Операнд PER, щонайменше, визначає один атрибут

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

SUMMARIZE SP ADD AVG ( QTY ) AS AQ

Для обчислення його результатів досить переглянути індекс по атрибуту QTY (за умови, що такий індекс існує), не зачіпаючи самої змінної відносини поставок SP Аналогічне зауваження стосується того випадку, коли функція SUM замінюється функцією COUNT або AVG (причому для функції COUNT підійде будь індекс) Що стосується функцій МАХ і MIN, то результат їх виконання можна отримати, застосувавши єдину операцію читання останньої (для функції МАХ) або першої (для функції MIN) записи індексу (знову-таки, за умови, що індекс для відповідного атрибута вже існує)

В останній частині даного розділу передбачається, що в якості операції агрегування розглядається саме операція, описана в разі 2 Нижче показаний приклад операції агрегування другого типу

SUMMARIZE SP PER P {Р #} ADD SUM (QTY) AS TOTQTY

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

702 Частина V Додаткові теми

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

кілька методів подібної угруповання ксртежей

1 Послідовний перегляд (або метод грубої сили)

2 Пошук за індексом

3 Пошук за допомогою хеш-функції

4 Злиття

5 Хешування

6 Поєднання методів 1-5

На рис 184-188 наведені псевдокоду процедур реалізації перерахованих методів для операції зєднання (операції проекції і агрегування залишені читачеві як вправа) На цих малюнках використовуються наступні позначення Насамперед, R і S – це відносини, які повинні бути зєднані, а с – їх загальний атрибут (можливо, складений) Передбачається, що можливий послідовний доступ до кортежів обох відносин R і s по одному за одну операцію Ці кортежі в послідовності доступу буд ут позначатися як R [1], R [2], .., R [m] і S [l], S [2], .., s [n], відповідно Для зєднаного кортежу, складеного з атрибутів кортежів R [i] і S [j], використовуватиметься позначення R [i] * S [j] Нарешті, змінну відносини R будемо вважати зовнішньої, а змінну відносини S –внутрішньої (Оскільки вони управляють зовнішнім і внутрішнім циклами перегляду, відповідно)

Послідовний перегляд

Метод послідовного перегляду (або грубої сили) іноді також називають простим методом У цьому випадку розглядаються всі можливі комбінації кортежів (тобто кожен кортеж відносини R перевіряється в поєднанні з кожним кортежем відносини S, як показано на рис 184)

Примітка Метод послідовного перегляду часто називають методом вкладених циклів, але ця назва не можна вважати прийнятним, оскільки вкладені цикли використовуються в реалізаціях всіх названих вище методів

Рис 184 Метод послідовного перегляду

Проаналізуємо витрати, повязані з використанням методу послідовного перегляду

Примітка Тут ми обмежимося тільки аналізом витрат на виконання операцій

введення-виведення, хоча на практиці може знадобитися також врахувати інші параметри

(Наприклад, витрати процесорного часу)

Глава 18 Оптимізація703

Насамперед, ясно, що для реалізації цього методу буде потрібно всього m + (n * m)

операцій читання кортежів А як щодо операцій запису кортежів Інакше кажучи, яка кардинальність результату операції зєднання (Кількість операцій запису кортежу дорівнюватиме кардинальності результуючого відносини, якщо останнє вимагається записувати на диск)

■ У приватному, але досить важливому випадку зєднання типу багато до одного (Наприклад, зєднання типу зовнішній ключ до відповідного потенційно му ключу) кардинальність результуючого відносини майже завжди точно сов падає з величиною т або п залежно від того, яке з відносин, R або S, розташоване на стороні зовнішнього ключа розглянутого зєднання

■ Тепер розглянемо більш загальний випадок зєднання типу багато до багатьох.

Нехай dCR – кількість розрізняються значень атрибута з відносини R, за яким виконується зєднання, a dCS має той же зміст, але для відносини

S Якщо припустити, що значення атрибутів розподілені рівномірно (Тобто будь-яке значення атрибута с може зустрітися з тією ж імовірністю, що й інші значен ня), то для даного кортежу відносини R існує n / dCS відповідних кортежів у відношенні S зі значенням атрибута с, рівним значенню цього атрибути та в розглянутому кортежі з відносини R Таким чином, загальна кількість кортежів у зєднанні (тобто кардинальність результуючого відносини) дорівнюватиме (т * N) / dCS Або, якщо повторити викладені міркування, почавши з кор тежа відносно S, то кардинальність результуючого відносини складе

(П * m) / dCR Ці дві оцінки будуть різними, якщо dCS * dCR, тобто якщо стосовно R існують значення атрибута с, які не зустрічаються відносно s, і навпаки У цьому випадку слід використовувати меншу з оцінок

Безумовно, як було зазначено в розділі 182, на практиці застосовуються операції введення-виведення сторінок, а не кортежів Тому припустимо, що у відносинах R і S на сторінці поміщається, відповідно, pR і pS кортежів (тобто відносини займають m / pR і n / ps сторінок, відповідно) Тепер легко побачити, що процедура, псевдокод якої показаний на рис 184, виконає (m / pR) + (m * n) / pS операцій читання сторінок Аналогічним чином, якщо поміняти ролями відносини R і S (відношення S вважати зовнішнім, a R-внутрішнім), кількість операцій читання сторінок становитиме (n / pS) + (n * m) / pR

Для прикладу припустимо, що m = 100, п = 10 000, pR = 1 і pS = 10 Тоді результатами обчислення останніх двох формул будуть значення 100 1 00і1 001000 операцій читання сторінок, відповідно

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

Завершуючи коротке обговорення методу послідовного перегляду, зауважимо, що цей прийом є найгіршим з усіх У ньому передбачається, що для відносини S не передбачений індекс, і не застосовується хеш-функція для доступу до атрибуту зєднання с Експерименти, проведені Биттон (Bitton) та ін [186], показали, що якщо це

припущення (відсутність індексів і хеш-функції) дійсно має місце, то

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

Пошук за індексом

Тепер розглянемо ситуацію, в якій для атрибута З внутрішнього ставлення S існує індекс X (рис 185) Перевага пошуку по індексу в порівнянні з методом послідовного перегляду полягає в тому, що завдяки наявності індексу X для даного кортежу зовнішнього відносини R можливий перехід безпосередньо до відповідного кортежу внутрішнього ставлення S Загальна кількість операцій читання кортежів з відносин R і s дорівнюватиме кардинальності результуючого відносини операції зєднання Загальна кількість операцій читання сторінок для відносин R і S при найгіршому припущенні, що кожна операція читання кортежу з відносини S вимагає звернення до окремої сторінки, складе (m / pR) + (mn / dCS)

Але якщо кортежі відносини S зберігаються в порядку значень атрибута зєднання С, то кількість операцій читання сторінки скорочується до значення (m / pR) + (mn / dCS) / pS Скориставшись тими ж прикладами і значеннями, що і вище (т = 100, п = 10 000, pR = 1, pS = 10), і припустивши, що dCS = 100, отримаємо в результаті обчислення двох останніх формул значення 10100 і 1100, відповідно Різниця між отриманими значеннями показує, що кортежі збережених відносин доцільно розміщувати в підходящої фізичної послідовності [187]

Рис 185 Пошук за індексом

Однак при оцінці витрат слід враховувати і витрати, повязані з виконанням операцій читання в самому індексі X Найгіршим є припущення, що при пошуку відповідних кортежів у відношенні S для кожного кортежу у відношенні R буде потрібно виконати непередбачений пошук по індексу, що вимагає читання сторінки для кожного рівня індексу Для індексу, що володіє х рівнями, операція пошуку додасть до загальної кількості операцій читання сторінки ще m * х операцій На практиці х зазвичай має значення 3 або менше (Більше того, досить імовірно, що верхній рівень індексу протягом всієї обробки даних буде знаходитися в оперативній памяті, що значно скоротить кількість операцій читання сторінок)

Глава 18 Оптимізація705

Пошук за допомогою хеш-функції

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

Метод злиття

У методі злиття передбачається, що кортежі відносин R і S фізично зберігаються в зовнішній памяті в послідовності значень атрибута с, за яким виконується зєднання Якщо дане припущення відповідає дійсності, то два відносини можна буде переглядати в їх фізичної послідовності, причому обидві операції перегляду можна синхронізувати, в результаті чого зєднання може бути виконано за один прохід за даними (це твердження істинне, принаймні, для зєднань типу один до багатьох, але не завжди істинно для зєднань типу багато до багатьох) Безсумнівно, подібний метод буде оптимальним при дотриманні зазначених припущень, оскільки кожна сторінка даних зчитується всього один раз (рис 187) Іншими словами, кількість операцій читання сторінок складе (m/pR)   +   (n/pS)

Рис 186 Пошук c допомогою хеш-функції

На підставі цього можна зробити наведені нижче висновки

■ Фізична кластеризація логічно повязаних даних є одним з важ нейших факторів, що впливають на продуктивність системи, тобто вельми бажаною тельно проводити кластеризацію даних так, щоб вони відповідали соеди неніям, найбільш важливим для підприємства [187]

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

Рис 187 Метод злиття (для зєднань типу багато до багатьох)

Хешування

Як і метод злиття, метод хешування дозволяє обійтися одним проходом по кожному з двох зєднуються відносин (рис 188) В результаті першого проходу будується хеш-таблиця для відносини S за значеннями атрибута зєднання SC Записи в цій таблиці містять значення атрибута зєднання (а також, можливо, значення інших атрибутів) і покажчик на відповідний кортеж, що зберігається на диску Під час другий проходу скануються кортежі відношення R і застосовується та ж хешфункція для значень атрибута зєднання R С Коли по обчисленому для кортежу відносини R значенням хеш-функції в хеш-таблиці виявляється один або кілька відповідних йому кортежів відносини S, алгоритм перевіряє, чи дійсно рівні значення RC і SC, і, якщо це так, виробляє відповідний кортеж (або кортежі) результуючого зєднання Основною перевагою даного методу в порівнянні з методом злиття є те, що кортежі відносин R і S можна зберігати в довільній послідовності, а значить, не потрібно їх попередньо сортувати

Рис 188 Метод хешування

Як і у випадку методу пошуку за допомогою хеш-функції, визначення оцінок витрат,

повязаних з використанням хешування, залишаємо в якості вправи для читача

181 РЕЗЮМЕ

Ця глава починається з твердження, що для реляційних систем оптимізація є як проблемою, Так і сприятливою можливістюФактично оптимізація є сильною стороною таких систем, причому з цілого ряду причин Реляційна система з хорошим оптимізатором функціонуватиме набагато краще, ніж нереляційних Наведений вступний приклад дає чітке уявлення про тих разючих результатах, яких можна досягти завдяки оптимізації (іноді ефективність виконання запиту підвищується в співвідношенні 10000:1)

Процес оптимізації в загальному випадку включає чотири описані нижче послідовні стадії

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

■ Перетворення в канонічну форму за допомогою різних законів преобразо вання

■ Вибір відповідних низькорівневих процедур реалізації різних операторів в

канонічному поданні запиту

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

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

В якості ілюстрації був зроблений короткий огляд статистичних показників бази даних, що використовуються в СУБД DB2 і Ingres Далі обговорювалася одна з стратегій, побудованих за принципом розділяй і володарюй, — декомпозиція запитів, вперше реалізована в прототипі системи Ingres Було також відзначено, що стратегії, побудовані за принципом розділяй і володарюй, вельми привабливі для систем з підтримкою паралельних обчислень і розподілених систем

Нарешті, розглядалися деякіметоди реалізаціїокремих реляційних операторів, зокрема оператора зєднання Був представлений псевдокод алгоритмів

для пяти методів виконання операції зєднання: метод послідовного перегляду, пошук за індексом, пошук за допомогою хеш-функції, метод злиття (Включаючи метод сортування-злиття) і метод хешування Також коротко розглядалися вартісні

характеристики описаних методів

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

такі функції розглянутих СУБД, які не дозволяють оптимізаторові виконувати свою роботу так, як вона могла бути виконана в іншому випадку (тобто за відсутності цих перешкод) До числа таких особливостей, перешкоджають оптимізації, можна, наприклад, віднести дублікати рядків (Див [66]), тризначну логіку (Див главу 19) і реалізацію тризначною логіки в мові SQL (див [196] і [1910])

У даній главі задачі оптимізації розглядалися так, як вони зазвичай трактуються і реалізуються в СУБД іншими словами, тут показано, якіемпіричні підходи в

основному застосовуються в даній області Але останнім часом зявилися реалізації принципово нового підходу до організації роботи СУБД, а цей підхід, по суті, ставить під сумнів багато припущення, лежать в основі зазначених емпіричних

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

■ Застосування методу вибору шляху доступу з урахуванням вартості (стадії 3 і 4 вказано ного процесу)

■ Застосування індексів і інших звичайних шляхів доступу

■ Здійснення вибору між компіляцією і інтерпретацією запитів до бази даних

■ Застосування алгоритмів для реалізації реляційних операторів

Додаткова інформація на цю тему наведена в додатку А

Джерело: Дейт К Дж, Введення в системи баз даних, 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>

*

*