Індекси (InterBase та Firebird)

Олексій Ковязін, останнє оновлення 07-Вер-2005

Концепція, покладена в основу індексів, проста та наочна і є однією з найважливіших основ проєктування баз даних. На основі індексів ґрунтуються багато базових об’єктів бази даних, і, крім того, правильне використання індексів є ключем до підвищення продуктивності застосунків баз даних. Однак що таке індекс? Індекс - це впорядкований покажчик записів у таблиці. Покажчик означає, що індекс містить значення одного або кількох полів у таблиці та адреси сторінок даних, де розташовані ці значення (детальніше про сторінки даних див. у розділі «Структура бази даних InterBase») (частина 4). Іншими словами, індекс складається з пар значень «значення поля» - «фізичне розташування цього поля».

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

Навіщо потрібні індекси?

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

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

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

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

Як вони організовані?

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

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

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

Відокремлення зберігання даних від їх представлення дає додаткові переваги порівняно з прямим сортуванням - можливо, вам знадобиться сортувати вихідну таблицю різними способами. Тоді вам допоможуть індекси - для кожної таблиці може бути до 64 індексів!

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

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

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

Прискорення виконання запитів. Індекси створюються для полів, які використовуються в умовах пошуку SQL-запитів.
Підтримка унікальності значень у полях; обмеження первинного ключа (про яке йшлося в розділі «Таблиці. Первинні ключі») вимагає, щоб у таблиці не було двох однакових значень полів, включених до первинного ключа. Щоб виконати цю умову, під час вставлення нового запису слід шукати те саме значення, яке буде вставлено. Для пошуку записів використовується особливий різновид індексу - унікальний індекс (див. нижче).
Підтримка посилальної цілісності. Обмеження зовнішніх ключів (які розглядаються в розділі «Обмеження бази даних») використовуються для перевірки того, що значення, вставлені в таблицю, обов’язково існують в іншій таблиці. Під час створення зовнішнього ключа індекс створюється автоматично. Цей індекс застосовується для прискорення запитів, що використовують з’єднання таблиць, а також для перевірки умов зовнішнього ключа. Ми коротко розглянули всі можливі застосування індексів. Тепер ми розглянемо особливості кожного випадку детальніше та відповімо на найчастіші запитання щодо застосування індексів.

Прискорення виконання запитів за допомогою індексів

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

Другий момент важливіший. Це витрати під час модифікації даних у таблиці. У реляційній СУБД, як відомо, записи в таблицях невпорядковані, і тому додавання/видалення записів відбувається без значних витрат ресурсів сервера. Навіть якщо запис видаляється із середини бази даних, немає переміщення обсягів даних, щоб заповнити цю порожнечу, - це не потрібно: сервер просто позначить порожнє місце та запише туди щось за потреби. Що стосується додавання, то в більшості випадків воно виконується в кінці таблиці. Однак, хоча сервер і не переміщує основні дані в таблиці під час модифікації, дані, що зберігаються в індексах, перевпорядковуються щоразу під час додавання/видалення записів! Іншими словами, серверу доводиться перебудовувати індекс під час додавання запису в середину таблиці. Звичайно, реалізація індексу певною мірою призначена для частих реорганізацій, але ці операції, тим не менш, займають час і ресурси процесора, і за наявності великої кількості індексів у таблиці модифікація даних у ній може бути набагато повільнішою, ніж у тій самій таблиці без індексів!

Це дві основні причини, які перешкоджають загальному індексуванню. Крім них, є ще кілька зауважень, що обмежують застосування індексів. Перше - це правило 20 %. Воно говорить, що якщо пошуковий запит повертає більше 20 % записів із таблиці, використання індексу може сповільнити пошук даних! Звичайно, ситуація залежить від конкретного запиту та умов, заданих для пошуку, але слід пам’ятати, що 20 % записів - це поріг, коли ефективність використання індексів стає сумнівною. Друге зауваження сформульоване не так чітко. Воно пов’язане з роботою оптимізатора InterBase.

Оптимізатор - це сукупність механізмів, які розробляють план виконання запиту. Коли користувач передає будь-який SQL-запит до InterBase, він вказує, що сервер має повернути після виконання запиту, але не визначає, ЯК сервер має виконати запит. Оптимізатор на основі заданого запиту створює план його виконання, тобто звідки і в якому порядку будуть братися дані для виконання запиту, які індекси будуть при цьому використовуватися. Коли сервер аналізує умови пошуку (це переважно частини виразу WHERE, ORDER BY тощо) для кожного поля, включеного в умову, сервер намагається використати індекс. На жаль, алгоритм створення плану є неповним, і оптимізатор часто використовує індекси, які не є достатньо ефективними для конкретного запиту, через що час виконання може суттєво сповільнитися. Тому створення зайвих індексів може призвести до створення неоптимальних планів.

Слід зазначити, що в клоні Yaffil ця проблема вирішується завдяки використанню сучасних алгоритмів створення планів. Третій випадок, коли індекс не потрібен, - це поля з обмеженим набором значень. Наприклад, поле, що зберігає інформацію про стать людини і містить лише два можливі значення - “F” та “M”; немає сенсу індексувати це поле. Отже, ми розглянули основні обмеження щодо створення індексів. Тепер слід розглянути проблему, коли необхідно використовувати індекси для досягнення покращення продуктивності. Існує 3 основні випадки, коли поле має бути індексоване:

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

Розглянемо синтаксис створення індексів. Ось повний формат команди DDL, яка дозволяє створювати індекси:

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

Мінімальний вираз для створення індексу виглядає наступним чином:

CREATE INDEX my_index ON Table_example(ID)

У цьому прикладі індекс з ім’ям my_index створюється для таблиці Table_example, а поле ID є індексованим полем. Індекс є висхідним, тобто значення в ньому впорядковані за зростанням, а також неунікальним, що означає, що поле ID може містити кілька однакових значень. Це, звичайно, найпростіший приклад індексу - найпоширеніший. Як видно з опису синтаксису, індекс може містити не одне, а кілька полів. Такий індекс використовується, коли запити часто виконуються і містять комбінацію індексованих полів в умовах пошуку або сортування. Наприклад, якщо ми маємо таблицю з полями Прізвище, Ім’я, По батькові, такий індекс буде застосований при виконанні запиту, який використовує сортування за Прізвищем, Ім’ям та По батькові. Загалом, не обов’язково вказувати умови для всіх 3 полів, застосованих в індексі, щоб скористатися його перевагами. Якщо ми хочемо відсортувати результат запиту, індекс буде використаний у випадку, коли перше поле в умові сортування збігається з першим полем в індексі. Наприклад, наш індекс буде застосований у випадку сортування за Прізвищем та Ім’ям.

Згідно з документацією, для оптимізації виконання запиту, що містить в операторі WHERE з’єднання полів з умовою OR, слід використовувати не агрегований індекс, а кілька окремих для всіх полів, включених в умову OR.

Щодо питання порядку сортування індексу, він може бути як висхідним, так і низхідним. Навіщо нам потрібні різні порядки сортування? Очевидно, для різних сортувань! Якщо ми хочемо відсортувати людей за прізвищем у висхідному порядку, ми створюємо висхідний індекс (ASC), а якщо в низхідному (від Z до A) - то низхідний! Якщо ми хочемо обидва, нам доведеться створити обидва індекси.

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

Існує ще одна опція у визначенні індексу - UNIQUE. Якщо ми її вкажемо, індекс дозволить вставляти в таблицю лише унікальні значення. Власне, це є основою для реалізації унікальних ключів. Унікальні ключі широко використовуються в базах даних. Тобто РК - це унікальний ключ-індекс, але не кожен УК є РК. Вище ми говорили лише про РК. Первинний ключ - це найпоширеніший тип унікального ключа. При створенні первинного ключа для таблиці автоматично створюється унікальний індекс. Йому присвоюється ім’я, що складається з RDB$PRIMARYNNN, де NNN - це послідовний унікальний номер у межах бази даних. Таким чином, два основні обмеження посилальної цілісності - унікальний ключ і первинний ключ - реалізуються завдяки використанню унікального індексу. Очевидно, що поняття унікальності несумісне з поняттям невизначеного значення. Іншими словами, у полях, що входять до унікальних індексів, не повинно бути жодних значень типу NULL. Перед створенням унікального індексу для поля необхідно встановити обмеження NOT NULL. Якщо індекс створюється для даних, які вже існують, то при створенні індексоване поле буде перевірено на наявність повторюваних значень. Якщо вони є, вам буде заборонено створювати індекс.

Окрім обмежень унікального та первинного ключа, механізм індексів лежить в основі реалізації ще одного обмеження посилальної цілісності - зовнішнього ключа. Обмеження зовнішнього ключа встановлюється для одного або кількох полів будь-якої таблиці та запобігає вставленню в ці поля значень, які не входять до первинного ключа іншої, батьківської таблиці. Для реалізації зовнішнього ключа, тобто для виконання перевірки наявності значення в батьківській таблиці, автоматично створюється спеціальний індекс. Його ім’я - RDB$FOREIGNNN, де NNN - це послідовний унікальний номер у межах бази даних.

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

Оптимізація продуктивності індексів

У назві цієї частини можна виявити певний парадокс - індекси, як було сказано вище, призначені для прискорення виконання запитів, і виявляється, що їх теж потрібно оптимізувати! Але що поробиш (таке життя) - хтось має піклуватися про індекси. Що відбувається з індексами? Чому вони “втрачають форму”? Доведеться ще раз сказати, що індекси реалізовані як бінарне дерево. І коли до таблиці додається новий запис (оновлюється, видаляється - як завгодно), до дерева додається нова гілка. Ці гілки додаються не в середину дерева, а до вершин інших гілок. Поступово дерево стає все більш розгалуженим (або незбалансованим), а пошук - менш ефективним. Перебудова дерева або (у деяких випадках) перерахунок статистики можуть покращити ситуацію.

Періодично потрібно перестворювати індекс, щоб відновити його продуктивність. Перестворення індексу відбувається в таких випадках:

При перебудові індексу за допомогою команди ALTER INDEX.
При видаленні та повторному створенні індексу за допомогою команд DROP INDEX та CREATE INDEX.
При резервному копіюванні та відновленні з резервної копії за допомогою інструмента gbak.

Також можна використовувати перерахунок статистики. Але слід розуміти, що ця операція не змінює стан індексу, вона лише надає оптимізатору точну інформацію про його стан, дозволяючи правильно використовувати цей індекс. Іншими словами, перерахунок статистики - це не “лікування” індексу, а лише точна діагностика його стану. Розглянемо всі ці способи оптимізації індексів детальніше. Використання команди ALTER INDEX має наступний формат:

ALTER INDEX name {ACTIVE | INACTIVE};

Тут name - це ім’я індексу, а ACTIVE та INACTIVE - два стани індексу, в які його можна перевести за допомогою команди ALTER INDEX. Параметр ACTIVE означає, що індекс активний і може застосовуватися в усіх запитах і процедурах. Якщо ви встановите індекс у стан INACTIVE, це призведе до відключення його використання. Для перебудови дерева слід послідовно виконати дві команди:

ALTER INDEX name INACTIVE; ALTER INDEX name ACTIVE;

Таким чином, індекс буде перебудовано. Використання ALTER INDEX має низку обмежень: не можна перебудовувати індекси, що використовуються в первинних, унікальних та зовнішніх ключах; не можна перебудовувати індекс, якщо він використовується будь-яким запитом у поточний момент; а також для зміни індексу необхідно мати права адміністратора (SYSDBA) або бути творцем цього індексу.

Перестворення індексу за допомогою команд DROP INDEX та CREATE INDEX призводить до повного видалення індексу з бази даних, а потім до його створення з нуля. Синтаксис команди DROP INDEX очевидний:

DROP INDEX ім’я_індексу;

Після видалення необхідно створити індекс з тим самим ім’ям та параметрами за допомогою команди CREATE INDEX, синтаксис якої ми вже розглянули. Спосіб перебудови індексу шляхом його повного перестворення має обмеження, подібні до обмежень для використання ALTER INDEX.

Третій спосіб перебудови індексу ґрунтується на властивості резервних копій баз даних InterBase, створених утилітою gbak. Справа в тому, що під час резервного копіювання дані, включені в індекс, не зберігаються в резервній копії, зберігається лише визначення індексу. Під час відновлення з резервної копії індекс створюється заново. Якщо ви хочете дізнатися про резервне копіювання докладніше, дивіться розділ “Резервне копіювання та відновлення з резервної копії” (частина 4).

Четвертий спосіб підвищення продуктивності індексів - збір статистики щодо індексів за допомогою команди SET STATISTICS. Статистика таблиці - це значення в діапазоні від 0 до 1, яке залежить від кількості різних записів у таблиці. Оптимізатор InterBase використовує статистику для визначення ефективності застосування того чи іншого індексу в запиті. Коли кількість записів у таблиці може суттєво змінюватися (наприклад, через велику кількість вставок або видалень), перерахунок статистики може значно покращити продуктивність. Команда перерахунку статистики виглядає наступним чином:

SET STATISTICS INDEX name;

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

Ми розглянули кілька способів підвищення продуктивності індексів. Використовуючи команди ALTER INDEX та DROP/CREATE INDEX, ми можемо перебудовувати будь-які індекси, крім системних індексів, створених автоматично, призначених для забезпечення посилальної цілісності. Якщо ви хочете перебудувати ці індекси, слід використовувати команди зміни та створення таблиць - ALTER TABLE та CREATE TABLE, оскільки ці індекси є невід’ємною частиною табличних ключів.