Вступ
Що таке індекс?
Індекс — це тип структури даних у базах даних, який призначений для підвищення швидкості та продуктивності запитів. Індекси присутні як у реляційних, так і в нереляційних базах даних. Ця стаття головним чином зосереджується на індексах у реляційних базах даних.
Навіщо потрібні індекси?
Під час написання запитів за допомогою SQL використовуються багато операцій об’єднання (join) та фільтрації. Кілька таблиць об’єднуються за допомогою зовнішніх ключів, а дані фільтруються, групуються або сортуються. Через ці складні операції отримання найшвидших результатів у таких запитах може бути складним завданням.
Під час виконання запитів до бази даних виконується багато операцій з диском. Дискові операції можуть потребувати багато часу процесора, а пошук потрібних даних на диску вимагає великої кількості сканувань. Якщо кількість цих сканувань зменшити, можна побачити значне покращення.
Розглянемо приклад. Припустимо, університету потрібно розробити базу даних для зберігання інформації про лекції, викладачів і студентів у коледжі. Може виникати багато потреб у об’єднанні та фільтрації цих даних. Викладач хоче отримати список усіх лекцій, де він є інструктором, або список студентів певного класу. З урахуванням різних сценаріїв отримання таких даних із бази може ставати повільнішим у міру її зростання. Однак із правильними індексами запити виконуються більш оптимізовано. Правильний індекс за ідентифікатором викладача або іменем студента в правильному контексті вирішує проблеми повільності.
Проблема і рішення
Дані на диску займають багато місця. Коли виконується запит, СУБД повинна звернутися до диска і просканувати всі блоки, щоб знайти потрібні дані. Комп’ютери повільні при роботі з диском, оскільки диск є пристроєм введення/виведення, і всі дані потрібно перемістити в оперативну пам’ять. Навіть нові високопродуктивні SSD повільніші порівняно з оперативною пам’яттю, і читання даних у таких обсягах є проблемою.
Як рішення, перше, що спадає на думку — зменшити кількість блоків, які читаються з диска. Але як цього досягти? Відповідь — індекси.
Класичний приклад для розуміння індексів — це книги. Коли потрібно знайти тему в книзі, замість пошуку на кожній сторінці дивляться зміст і знаходять потрібну сторінку, не переглядаючи всю книгу. Індекси працюють так само. Вони зберігають дані (назву теми в цьому прикладі) і вказівник на місце на диску, де знаходяться реальні дані (це номер сторінки в попередньому прикладі). СУБД звертається до індексу і швидко знаходить адресу даних на диску замість сканування всього диска. Це зменшує кількість дискових операцій і підвищує продуктивність.
Як вони працюють?
Індекси (некластеризовані) не змінюють порядок таблиці. Лише кластеризовані індекси змінюють порядок таблиці, і одна таблиця може мати один кластеризований індекс, зазвичай це первинний індекс. Натомість індекси зберігаються як окрема структура даних. Найпоширенішою структурою даних для реалізації індексів є B-дерева. Вони можуть використовуватись для сортування даних, і вартість пошуку буде дуже низькою.
Це збалансоване дерево містить лише наш стовпець індексу (або стовпці для складених індексів), а не інші. Дерево зберігає тільки індекс і відповідну адресу на диску. Адреса на диску подібна до номера сторінки в книзі. База даних може легко знайти розташування на диску, і це значно зменшує кількість дискових операцій. Оскільки розташування на диску відоме, немає потреби зберігати інші стовпці в структурі даних, і потрібні стовпці можна легко знайти.
Однак не всі реалізації індексів використовують B або B+ дерева. Також можуть використовуватись хеші та деякі інші структури даних для швидкого доступу.
Індекси баз даних та дискові операції
Основний принцип
Найбільш базова мета індексів — зменшити кількість звернень до диска під час виконання запиту. Читання кожного блоку з диска є дуже витратним для комп’ютера. Мінімізація цього дає приріст продуктивності на низькому рівні.
Про форматування диска
Диски складаються з блоків. Ці блоки мають адреси з номером доріжки (track) і сектора. Типовий розмір — 512 байт для кожного блоку. Читання і запис виконуються в одиницях блоків. Кожен байт має свою адресу, яка називається зсувом (offset).
Приклад для демонстрації роботи індексу
Припустимо, є таблиця з назвою employees для зберігання даних, і в ній 1000 співробітників. Дані кожного співробітника мають розмір 128 байт. Отже, кожен блок може зберігати 4 рядки, і загалом для зберігання даних використовується 250 блоків. Коли виконується запит для пошуку певних даних, потрібно просканувати всі 250 блоків, щоб визначити рядки, які задовольняють умову.
Тепер припустимо, що створено індекс за id співробітника і вказівник на диск, де зберігається рядок. Припустимо, що запис індексу з id і вказівником має розмір 16 байт. Цей індекс також зберігається на диску. Один блок може містити 512/16 = 32 індекси. Максимум потрібно 32 блоки для доступу до індексу. Коли індекс знайдено, дані на диску можна легко знайти за допомогою вказівника всередині індексу. Отже, максимум потрібно 33 блоки, щоб знайти дані. Простий індекс може зменшити кількість звернень до диска з 250 до 33.
Важливі моменти щодо індексів
Як база даних визначає, коли використовувати індекс?
База даних вирішує використовувати індекс внутрішньо. Коли виконується запит, СУБД перевіряє стовпці, які запитуються, чи є для них доступні індекси, і якщо вони є, використовує відповідний індекс для досягнення найкращої продуктивності. Це можна побачити в запитах EXPLAIN.
EXPLAIN можна додати на початок будь-якого запиту, і СУБД покаже план виконання запиту. Він показує, які індекси та сортування виконуються під час виконання запиту СУБД. Це допомагає визначити та зрозуміти проблеми в запитах. EXPLAIN можна використовувати разом із “ANALYZE”. ANALYZE також виконує запит. Не рекомендується широко використовувати його, оскільки це може створювати операцію запису.
У яких сценаріях індекси не слід використовувати
- Для малих таблиць індексація лише займає більше місця на диску, оскільки кількість блоків для сканування і так невелика.
- Для стовпців, що містять занадто багато значень null (можна використовувати розріджені індекси (sparse indexes)).
- Стовпці, які часто оновлюються, оскільки кожне оновлення цього стовпця також означає оновлення структури даних індексу.
- Таблиці, які мають більше операцій запису, ніж читання, оскільки індекси оптимізовані для читання, і кожна операція запису також записується в індекс, що уповільнює операції запису.
Щільні та розріджені індекси
У щільних індексах кожен запис індексується і має запис у структурі індексу. Однак можуть бути стовпці, які потребують індексації для підвищення продуктивності, але містять багато значень null або потрібно індексувати лише деякі значення. У таких випадках використовуються розріджені індекси. Ці індекси створюються не для всієї таблиці, а лише для деяких записів.
Вибір типу первинного індексу
Використання uint є кращим, оскільки немає проблеми з вичерпанням ключів, і оскільки ключі в більшості випадків автоінкрементні, немає потреби знову перебудовувати B-дерево індексу. При використанні рядків або UUID як первинного ключа таблиці індексів можуть ставати більшими, ніж при використанні uint, через розмір UUID. Також вставка в середину таблиці може спричинити перебудову дерева індексу. Тому, якщо це можливо, слід обирати uint.
Складені індекси
Ці індекси містять більше ніж один стовпець. Порядок стовпців має значення, оскільки доступ забезпечується відповідно до цього порядку. Доступ починається з лівого стовпця і рухається вправо, при цьому стовпці не можна пропускати. Сканування зупиняється, коли зустрічається перша умова діапазону. Під час створення складеного індексу порядок слід обирати обдумано. Перший стовпець зазвичай використовується з умовами рівності. Другий і наступні стовпці можуть використовуватись також з умовами діапазону.
CREATE INDEX a_b_idx ON sample_table(a,b);Стовпці для створення індексів
Хоча індекси можуть значно впливати на продуктивність, не всі стовпці слід індексувати, і їх потрібно обирати обдумано.
- Якщо стовпець часто використовується в WHERE, JOIN, GROUP BY, ORDER BY, тоді можна розглянути використання цього стовпця як індексу.
- Створення зайвих індексів може спричинити уповільнення операцій запису та займати занадто багато місця на диску.
Кардинальність і селективність
Кардинальність визначає кількість унікальних значень у стовпці. Селективність — це відношення кардинальності до загальної кількості рядків. Якщо селективність дорівнює 1, це означає, що стовпець є унікальним. Стовпець із високою селективністю працює краще як індекс, ніж стовпець із низькою селективністю. Якщо селективність індексу низька, СУБД може вирішити не використовувати індекс і звертатися безпосередньо до таблиці, що погіршує продуктивність. Тому при створенні індексів слід враховувати селективність.
Дубльовані індекси
Деякі індекси можуть бути створені дубльовано. Це найчастіше трапляється зі складеними індексами. Якщо складений індекс має порядок стовпців (x, y, z), тоді створення другого індексу для x буде дублюванням, оскільки складені індекси будуються зліва направо. Отже, другий індекс, створений для x, можна видалити.
CREATE INDEX a_b_idx ON sample_table(a,b);
CREATE INDEX a_idx ON sample_table(a); -- this index is duplicatesПокривні індекси (Covering Indexes)Покривні індекси (Covering Indexes)
У SQL-запиті може використовуватись кілька стовпців для вибірки, фільтрації або об’єднання. Якщо індекс охоплює всі ці стовпці, тоді такий індекс називається покривним індексом. При використанні покривних індексів немає потреби звертатися до основної таблиці бази даних, оскільки всі стовпці вже містяться в індексі. У наведеному нижче прикладі employee_name_departmants є покривним індексом.
CREATE TABLE employees(
id int PRIMARY KEY,
name text,
salary int,
departmant text,
);
CREATE INDEX employee_name_departmants ON employees(name,departmant);
SELECT name, departmant
FROM employees
WHERE name = 'John';Інвертовані індекси
Інвертовані індекси зазвичай використовуються в системах повнотекстового пошуку. Ідея полягає в тому, щоб розбити текст на слова або терміни та створити індекс на їх основі.
id | name
---------------------
1 | 'John Smith'
2 | 'Kevin Collins'
3 | 'Fred King'
4 | 'John Powell'
5 | 'David King'
token | id
-----------------------
john | 1, 4
smith | 1
kevin | 2
fred | 3
king | 3, 5
SELECT * FROM employees WHERE name ILIKE '%john%'У цій таблиці припустимо, що на стовпці name створено інвертований індекс. Цей індекс буде схожий на наведений вище. За допомогою такого інвертованого індексу пошук виконується значно швидше. У PostgreSQL такі індекси називаються GIN (Generalized Inverted Indexes). Вони також дозволяють індексувати стовпці типу jsonb.
Багаторівневі індекси
Багаторівневі індекси використовуються, коли перший індекс не вміщується в пам’яті. Індекси зазвичай зберігаються в пам’яті для підвищення швидкості. Але коли індекс занадто великий, щоб поміститися в пам’ять, потрібні додаткові звернення до диска. Щоб зменшити це, створюється другий індекс, який вказує на перший індекс.
Сховані (обфусковані) індекси
Сховані індекси означають зміну формату даних у стовпці, по якому створено індекс. Якщо формат стовпця змінено, СУБД не може правильно використовувати індекс для фільтрації даних і змушена звертатися до таблиці на диску. Замість обфускації стовпця слід змінювати умову. Найчастіше це трапляється зі стовпцями типу date. У такого типу запитах використовується функція, але СУБД не може обчислити результат функції і не може застосувати індекс. У таких випадках можна використовувати функціональні індекси або замість зміни формату даних змінювати формат фільтра до потрібного. Наприклад, якщо існує індекс на стовпці last_name, а фільтр створено як UPPER(last_name), оскільки функція UPPER змінює дані, індекс не використовується, і виконується повне сканування таблиці. Аналогічно, запит нижче виконується без використання індексів навіть якщо індекси є для стовпців a і b через виконання обчислень.
SELECT a, b
FROM table_name
WHERE 3*a - b = -5Замість виконання таких обчислень можна використати функціональний індекс:
CREATE INDEX math ON table_name (3*a - b)Ресурси
https://use-the-index-luke.com/?source=post_page—–cef384042e86—————————————
https://www.cockroachlabs.com/blog/inverted-indexes/?source=post_page—–cef384042e86—————————————
https://prepinsta.com/dbms/indexing-and-its-types
https://www.datacamp.com/tutorial/introduction-indexing-sql
https://www.programmerinterview.com/database-sql/what-is-an-index
ОРИГІНАЛ СТАТТІ:Deep Dive Into SQL Indexes
АВТОР СТАТІ:Ekrem Sönmezer
🚀Долучайтесь до нашої спільноти Telegram:
🚀Долучайтесь до нашої спільноти FaceBook:
🚀Долучайтесь до нашої спільноти Twiter X:
