Планування індексів

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

Реферат

На тему “Планування індексів”

Львів 2012

Зміст

1 Фізичний проект бази даних

1.2. Проектування індексів

2. Індекси в Oracle

3. Висновки

Глосарій

Вправи

1 Фізичний проект бази даних

планування індекс оracle

Поліпшення схеми (schemas) таблиці і нормальні форми

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

Якщо всі таблиці знаходяться в нормальній формі ((Boyce-Codd) BCNF), то вони вільні від надлишковостей, пов'язаних з функціональними залежностями.

Якщо таблиця не знаходиться у нормальній формі (BCNF), то ми намагаємося провести декомпозицію(decompose), розбити її на множину таблиць в нормальній формі (BCNF):

Якщо під час декомпозиції ми не можемо утримувати функціональну залежність, то залишаємося в 3-ій нормальній формі;

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

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

Коли прикладна програма обробляє дві множини рядків окремо, може бути корисним розбити таблицю на дві, тобто таблицю Persons на Students та Employees. Тут декомпозиція - горизонтальна, протягом нормалізації - декомпозиція вертикальна.

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

Проектування індексів

Спершу ми конкретизуємо обсяг робіт в додатку бази даних.

Робоче навантаження бази даних складається з:

Найважливіші запити разом з інформацією про те, як часто вони використовуватимуться.

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

Необхідна швидкість виконання цих запитів і модифікацій.

Для кожного ідентифікованого запиту:

До яких таблиць потрібен доступ?

Які стовпці з'являються в результаті вибірки/об'єднання (selection/join) стовпців? Як вони вибрані?

Для кожної ідентифікованої модифікації:

Які стовпці з'являються в результаті вибірки (selection) стовпців? Як вони вибрані?

Вид модифікації ВСТАВКА/ЗНИЩЕННЯ/ОНОВЛЕННЯ (INSERT/DELETE/UPDATE) і яких стовпців вона торкнеться (стосуватиметься)?

Базуючись на зібраній інформації ми ухвалюємо рішення:

На основі яких таблиць та стовпців повинні створюватися індекси? Який тип: первинні/унікальні/звичайні (primary/unique/ordinary)? кластерні-зовнішні/хеш-зовнішні/звичайні (clustered-internal/hash-internal/ordinary)? хеш/деревовидні (hash/tree)? динамічні/статичн (dynamic/static)?

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

Варто представити горизонтальну декомпозицію (horizontal decomposition), тобто, чи повинні ми розбити таблицю Persons на дві таблиці: Students та Employees: що слід порекомендувати, якщо запити, які виконуються в базі даних, залучають окремо працівників або студентів і умова пошуку пропонує індекси з ріних розподілених стовпців, відповідно?

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

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

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

Нижче ми представляємо короткий підсумок проектування індексів:

Стовпці, що з'являються у клаузі (умові) WHERE, є кандидатами для компонентів ключа пошуку в індексах.

Індекс автоматично створюється системою для кожного первинного і унікального ключа.

Індекс іноді будується на стовпцях:

чиї значення обмежують рядки, що шукаються в таблиці, тобто Emp.Job='MANAGER', проте важливо, що пошук є вибірковим, тобто, відсоток рядків, що шукаються, не такий вже великий, наприклад максимум до 5 або 10%;

які є зовнішніми ключами, якщо це пришвидшує виконання об'єднання двох таблиць за наступною умовою foreign key=primary key - припускають, що виконання приєднання починається вибором рядка з головної таблиці (з первинним ключем). Пізніше шукаються ряди з таблиці деталей (із зовнішнім ключем);

які з'являється у важливих запитах інформаційної системи, за участю стратегії реалізації «тільки індекс» (only-index).

Для пошуку тотожностей пропонується хеш-індекс.

Для пошуку діапазону пропонується деревовидний індекс.

Кластерний індекс, особливо важливий для запитів діапазону, з кляузою GROUP BY та з дублюванням - це не важливо, коли використовується тільки-індексна (only-index) стратегія.

Внутрішній хеш-індекс особливо важливий з дублюванням - це не важливо, коли використовується тільки-індексна (only-index) стратегія.

При використовуванні методу Вкладених Циклів Індексу Об'єднання (Index Nested Loops Join method), індекс для об'єднання з внутрішньою таблицею повинен бути: первинним, унікальним, кластерним, внутрішнім хеш, або селективним (primary or unique or clustered or internal hash or selective ) доти, поки нам потрібне збільшення значень в деяких інших внутрішніх стовпцях таблиці, окрім пошукових ключових значень безпосередньо. Якщо це не можливо, то краще не встановлювати індекс, а використовувати об'єднання Сорта (Sort-Merge Join) або метод хеш-об'єднання (Hash Join method ) для того, щоб приєднатися до цих таблиць.

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

Приклад 1

SELECT E.Ename, D.Loc

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

D.Dname='SALES';

Індекс D.Dname підтримує вибірку D.Dname='SALES' коли D є зовнішньою таблицею. Потрібно індекси типу: унікальний, селективний, кластерний або хеш.

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

Навіть краще (оптимальне) рішення повинне бути кластером цих двох таблиць. Потім приєднання було б зведено до вибору на кластері, що побудований на основі індексів стовпця D.Dname. Якщо записи кластеру запам'ятали належним чином (подібну реалізацію в Oracle, буде описано пізніше), для даного запису про відділ, записи про всіх працівників, що працюють в цьому відділі, повинні запам'ятовуватися на тій же сторінці або по одному на окремих сторінках. Використовування кластера особливо важливе, коли виділення торкається таблиці з одного боку взаємозв'язку між таблицями (з боку первинного ключа).

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

Ми могли б також подумати про відображення даних, що обчислює ціле об'єднання таблиць Dept і Emp:

SELECT D.Dname, E.Ename, D.Loc

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno;

і встановлення відповідного індексу в стовпці D.Dname (хеш, кластерного або внутрішнього) щоб зробити швидшим пошук в стовпці D.Dname.

Приклад 2

SELECT E.Ename, D.Loc

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

E.Sal BETWEEN 10000 AND 20000 AND E.Job='SALESMAN';

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

Стовпець D.Deptno є первинним ключем, що завжди має індекс, який ми можемо використовувати, поки об'єднуємо.

Який індекс потрібен на таблиці Emp E? Індекс на E.Sal або на E.Job - вибір залежить від виборності пошукових умов - якщо маємо погану вибірковість, то нам повинен бути потрібен кластер ний індекс, але, можливо використовувати внутрішній хеш-індекс на E.Job.

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

Кластер також міг би використовуватися. Це часове виділення (вибірка) стосується таблиці зі сторони «багато» (?) (це збоку зовнішнього ключа): так для запису працівника на тій же сторінці потім ми могли б прочитати запис департаменту.

Приклад 3

SELECT E.Deptno, COUNT(*)

FROM Emp E

WHERE E.Sal>2000

GROUP BY E.Deptno;

На стовпці E.Deptno потрібен кластерний або внутрішній хеш-індекс. Якщо неможливе встановлення такого індекса, то система відсортує файл записів таблиці Emp E у E.Deptno - розглядаються і обираються тільки записи, де E.Sal>2000. Потім ми обчислюємо COUNT(*).

Це повинне бути навіть краще, якщо ми могли б використовувати деревовидний індекс на стовпцях <E.Deptno, E.Sal>. Потім ми могли б виконувати запит, що заперечує індекс без потреби перетину файлом записів, - за допомогою використовування тільки-індексної (only-index) стратегії.

Приклад 4

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

(a)

SELECT D.Dname

FROM Dept D, Emp E

WHERE D.Deptno=E.Deptno;

В даному випадку будь-який індекс на E.Deptno достатній, тому що немає необхідності звертатися до файлу записів таблиці E! Запит виконується скануванням цілого файлу записів таблиці D і досягаючи індексу на E.Deptno тільки, для того, щоб перевірити, чи існує ведення даних зі значенням ключа пошуку, що дорівнює D.Deptno.

(b)

SELECT E.Deptno, COUNT(*)

FROM Emp E

GROUP BY E.Deptno;

Будь-який індекс на E.Deptno достатній, тому що немає потреби звертатися до файлу записів таблиці E.

(c)

SELECT E.Deptno, MIN(E.sal)

FROM Emp E

GROUP BY E.Deptno;

Тут добрим для використання є деревовидний індекс на <E.Deptno, E.sal> Потім нам не доведеться звертатися до файлу записів таблиці E.

(d)

SELECT AVG(E.Sal)

FROM Emp E

WHERE E.Deptno=25 AND E.Sal BETWEEN 3000 AND 5000;

Деревовидний індекс на <E.Deptno, E.sal> або на <E.Sal, E.Deptno> тут повинен бути добрим для використання. Потім нам не доведеться звертатися до файлу записів таблиці E.

Евристичні методи оптимізації, що стосуються запитів та індексів

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

Створіть індекси, що дозволені для тільки-індексні (only-index) стратегії.

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

Уникайте, якщо можливо, вкладені запити (підзапити), комплексні умови, DISTINCT, GROUP BY, OR, вирази типу арифметичний/рядок.

Час від часу відновлюйте всі індекси, особливо статичні.

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

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

2 Індекси в Oracle

Зараз ми покажемо, як представлені поняття створення і використовування індексів застовуються у разі специфічної СУБД (DBMS), якою є Oracle.

Результат пошуку за індексом в Oracle є ідентифікаторами рядка, що є спеціальними значеннями типу даних ROWID. Існують наступні види індексів.

1. Індекс, заснований на дереві B+

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

При виконанні запиту, система використовує індекс, заснований на дереві B+ тільки тоді, коли гарантована достатня пошукова вибірка , наприклад 5 -10% всіх записів у файлі.

Звичайний індекс, заснований на дереві B+, автоматично створений для кожного первинного і унікального ключа.

2. Організовані таблиці індексу, засновані на дереві B+

(створюється за допомогою використовування кляузи ORGANIZATION INDEX в CREATE TABLE )

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

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

Cities(City_id, City_name)

Customers(City_id,Cust_id_in_city, Name, Hobby, Age)

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

SELECT Customers.Name, Customers.Hobby

FROM Customers, Cities

WHERE Customers.City_id = Cities.City_id

AND Cities.City_name = 'WARSZAWA'

AND Customers.Age BETWEEN 18 and 25;

тому що після пошуку Warszawa's City_id всі замовники від Warszawa запам'ятаються разом тільки на декількох сторінках і не розмістяться скрізь на диску, як це могло б трапитися без об'єднання таблиці з індексом.

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

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

CREATE TABLE Customers(

City_id INTEGER,

Cust_id_in_city INTEGER,

Name VARCHAR2(80),

Hobby VARCHAR(20),

Age INTEGER,

CONSTRAINT Clients_pk PRIMARY KEY(City_id,Cust_id_in_city),

CONSTRAINT Clients_fk FOREIGN KEY(City_id) REFERENCES City

)

ORGANIZATION INDEX;

3. Індекс, заснований на дереві B+ із зміненими ключовими значеннями

(REVERSE в операторі CREATE TABLE) Це використовується тільки з предикатом тотожності - зокрема ви не можете переглядати результуючі рядки відповідно до значення ключа пошуку Цей тип, як індекс іноді використовується при розподілі таблиці і індексу, де більш важливим є рівне розповсюдження ключових значень в піддеревах дерева B+.

4. Індекс, заснований на одному або більше таблицях кластеру, хеш-індекс

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

Там на кожному кластері створено зовнішній індекс - один з двох типів:

звичайний індекс, заснований на дереві B+

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

Давайте вважатимемо зразковим запит, що обчислює значення порядку, зроблений замовником Kowalski.

SELECT z.Id_zam, SUM(p.Value*p.Quantity)

FROM Orders z, Order_items p, Customers k

WHERE p.Order_id = z.Order_id

AND z.Customers_id = k.Customers_id

AND k.Surname = 'Kowalski'

GROUP BY z.Order_id;

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

CREATE CLUSTER Order_cluster(Order_id INTEGER)

SIZE 2000;

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

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

Після створення таблиць і перед вставкою даних в них, ми повинні створити кластерний індекс.

CREATE INDEX Order_idx ON CLUSTER Order_cluster;

Повний приклад створення кластера був показаний в Лекції 3. В прикладі з побажаннями клієнта ми повинні також встановити звичайні індекси на стовпцях Customers.Surname та Orders.Customer_id. Ми розглядатимемо інший приклад, в якому використовується хеш-індекс для первинного ключа таблиці Account_id:

Accounts(Account_id, Balance, Name, Surname, Address)

Ми припускаємо, що таблиця Accounts включає багато рядків,, оскільки в банку часто багато касирів

SELECT *

FROM Accounts k

WHERE k.Account_id = :number;

Спершу ми визначаємо кластер, використовуючи опцію SINGLE TABLE:

CREATE CLUSTER Account_cluster(Account_id INTEGER)

SIZE 512

SINGLE TABLE

HASHKEYS 100000 HASH IS mod(Account_id, 100003);

де:

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

Клауза HASHKEYS конкретизує число значень хеш-функції - Oracle закругляє це до найближчого, більшого від цього простого числа - в даному випадку 100003.

HASH IS - ця клауза конкретизує хеш-функцію, що звертається до кластерного ключа.

Число значень хеш-функції може бути прочитане з перегляду словника наступних баз даних:

SELECT u.Hashkeys

FROM User_clusters u

WHERE u.Cluster_name = 'ACCOUNT_CLUSTER';

Потім ми визначаємо таблицю Accounts :

CREATE TABLE Accounts(Account_id INTEGER PRIMARY KEY,

Balance NUMBER,

Name VARCHAR2(20),

Name VARCHAR2(50),

Address VARCHAR2(70))

CLUSTER Account_Cluster(Account_id);

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

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

Ми можемо вважати кластерний індекс як проміжну структуру між внутрішнім і зовнішнім індексом.

5. Індекс з входами, конкретизованими через вирази

Індексні стовпці можуть бути виразами, включаючи функції (виключення складної (агрегованої) функції). Наприклад, створюючи індекс

CREATE INDEX Uppercase_idx ON Emp(UPPER(Ename));

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

SELECT * FROM Emp e

WHERE UPPER(e.Ename)='KOWALSKI';

6. Бітовий індекс

обговорюватиметься в лекції 15 (в сховищах даних)

3 Висновки

В Лекції 11 ми обговорювали правила фізичного проектування схеми бази даних і її налаштування: які індекси створювати, як групувати таблиці в кластерах, як поліпшити логічну схему бази даних з точки зору швидкості виконання запиту.

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

Глосарій

work load (перелік робіт, обсяг робіт) - містить зведення про додаток бази даних:

які запити найбільш важливі і як часто вони використовуються

які модифікації найбільш важливі і як часто вони використовуються

яка необхідна швидкість виконання запитів і модифікацій.

Вправи

Вивчіть проблему вибору індексів в таблицях Emp і Dept з точки зору підтримки ефективної оцінки запиту. Опишіть можливий план виконання запиту:

SELECT E.Mgr, COUNT(*)

FROM Emp E

GROUP BY E.Mgr;

SELECT E.Ename

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

D.Dname='SALES'

ORDER BY e.Empno;

SELECT e.Dname, COUNT(*)

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

E.Job = 'SALESMAN'

GROUP BY e.Deptno, e.Dname;

SELECT E.Ename, D.Dname

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno AND

E.Job = 'SALESMAN'

ORDER BY e.Empno;

SELECT E.Ename, E.job, D.Dname

FROM Emp E, Dept D

WHERE E.Deptno=D.Deptno

ORDER BY e.Ename;

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