Заняття 11. Індекси як об’єкт в реляційних базах даних

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

що дані на фізичному диску зберігаються в сторінках.
Сторінка – це блок фіксованої довжини неперервних віртуальних адрес пам’яті, який бере участь в операціях читання і запису як єдине ціле.
Сучасний MySQL працює з таблицями типу InnoDB, розмір сторінки даних яких рівний 16 Кбайт (16 384 байт).

яку сервер виділяє як єдине ціле при розміщенні даних на

диску по мірі необхідності.
Типово екстент складається із 64 сторінок.

містить рядки даних або в кучі, або в структурі кластерного

індексу.
Сторінки кучі або кластерного індексу об’єднуються в одну або декілька одиниць розподілу в залежності від типів стовпців у рядках даних.

замовчуванням таблиця або індекс має єдину секцію, яка містить усі

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

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

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

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

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

в купі є одна секція.
Якщо купа має декілька секцій,

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

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

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

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

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

вузол дерева називається кореневим.
Вузли нижнього рівня індексу називаються кінцевими.

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

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

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

індексом.
В кластерному індексі кінцевий рівень не містить ключів індексу і

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

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

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

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

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

за замовчуванням стає кластерним індексом.
Якщо в таблиці є унікальний (унікальні)

індекс, кластерним стає перший із них.
Інакше InnoDB самостійно створює приховане поле з сурогатним ID, розміром в 6 байт.
InnoDB в унікальних ключах зберігає повний набір значень полів кластерного ключа в якості посилання на кінцевий рядок у таблиці. Тому, чим більший первинний ключ, тим більшими є унікальні ключі.

дерева, що й кластерні індекси, але з такою різницею:
рядки

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

є вказівником на рядок.
Якщо для таблиці створено індекс, то

вказівник – це ключ кластерного індексу для рядка.

займає декілька секцій, то кожна секція має структуру збалансованого дерева,

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

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

переважно неповторювані дані чи багато NULL-значень.
Завдяки індексам оптимізується виконання запитів, що видають невелику кількість результатних рядків (до 25%).
Слід пам’ятати, що індекси прискорюють пошук даних, однак сповільнюють процес їхнього оновлення, що стає особливо відчутним під час одночасного оновлення великої кількості рядків (у подібних випадках перед оновленням індекс потрібно видаляти, а після завершення даної операції – відновити).

керувати пам’яттю, слід відвести частину пам’яті під індекси.
Потрібно завжди індексувати

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

для одного індексу вказується більш ніж одне поле, то друге

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

створювати перед створенням будь-яких некластерних індексів.
Якщо таблиця має і кластерний

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

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

з:
оптимізацією умов;
оптимізацією сортування;
оптимізацією групування і агрегування;
оптимізацією з’єднання таблиць.

умови, можна досягнути значної продуктивності запитів.
Чим простіші (коротші) операнди

використовуються в операціях порівняння, тим вища швидкість виконання запиту.

то при відсутності відповідних індексів і статистики такі вирази будуть

виконуватись зліва направо, причому ніякі круглі дужки не зможуть змінити такий порядок.
Принцип перевірки послідовності кон’юнкцій такий, що якщо перший вираз є хибним, то решта перевірятись не будуть.
Тому доцільно першими розміщати вирази, імовірність істинності яких є малоімовірною.
Якщо для пари виразів імовірність приблизно однакова, то першим треба розмістити найпростіший.
Зауважимо, що такі рекомендації не відносяться до СУБД Oracle, де умови починають перевірятись з кінця. Відповідно, порядок виразів повинен бути протилежним.

умові повинні бути розміщеними у порядку спадання імовірностей – від

найбільшої.
Це не відноситься до СУБД Oracle, де умови з диз’юнкцією повинні розміщуватись за зростанням імовірності істиності.

використати розподілений закон:
A AND (B OR C) = (A

AND B) OR (A AND C)
Дослідним шляхом встановлено, що вираз зліва виконується швидше.
Деякі СУБД самі вміють оптимізувати запити такого типу. Але краще відразу записати оптимальний вираз.

WHERE NOT (column1 > 5)
відразу можна записати:
WHERE column1

умови можна записати, використовуючи правило де Моргана:
NOT(A AND B) = (NOT A) OR (NOT B);
NOT(A OR B) = (NOT A) AND (NOT B).
Наприклад, умову
WHERE NOT (column1 > 5 OR column2 = 7)
можна перетворити на простішу:
WHERE column1 <= 5 AND column2 <> 7.

На швидкість сортування впливає три фактора:
кількість вибраних рядів;
кількість стовпців, вказаних

у фразі ORDER BY;
довжина і тип стовпців, вказаних у фразі ORDER BY.

у фразі HAVING не використовується агрегатна функція, то вважається, що

вона є еквівалентною до фрази WHERE, яку і потрібно використовувати для оптимізації запиту.
Однак, необхідно враховувати специфіку СУБД, оскільки в багатьох СУБД фрази WHERE і HAVING не є рівноцінними і виконуються не однаково.
Якщо відбувається групування без агрегатних функцій, доцільно використовувати оператор DISTINCT.

необхідно враховувати, що виконуються вони швидше, якщо записані окремо.
Це

означає, що їх краще використовувати в різних запитах або в запитах з використання операції об’єднання UNION.
При використанні функції SUM:
оптимальнішим буде вираз SUM(x + y), а не SUM(x) + SUM(y).
для віднімання – навпаки: SUM(x) – SUM(y) опрацьовується швидше, ніж SUM(x – y).

WHERE, то оптимізатор при використанні з’єднання оцінює запит в цілому,

а у випадку підзапитів, вони будуть оптимізовані окремо (по частинах).
Деякі СУБД (наприклад, Oracle) ефективніше працюють з операціями з’єднання таблиць.
Після з’єднання в результатній таблиці виводиться вся вказана інформація, а в підзапитах частина даних використовується як параметр в умові пошуку.

більш вільних, різноманітних умов.
Підзапити можуть містити фрази GROUP BY, HAVING,

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

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

можна скористатися посиланням http://www.mysql.ru/docs/man/Query_Speed.html (також можна переглянути інші поради щодо оптимізації запитів);