Бази даних і структури даних / крок 01
Навіщо потрібні індекси в базі даних — розберемо на прикладі
Про що це відео
Живе демо-знайомство з індексами баз даних: автор готує дві бази MySQL — одну з таблицею products на 1 тис. рядків, другу на 10 мільйонів — і вимірює той самий SELECT з увімкненим SQL-профілюванням. На маленькій таблиці запит займає ~0,3 мс; на таблиці з 10 млн рядків ідентичний запит — 3,3 секунди, що він називає катастрофою для вебзастосунку: запити, які надходять швидше, ніж завершуються, накопичуються і кладуть усю базу. Індекс на name змушує той самий запит виконуватися за ~0,05 мс — він ділить прямо на екрані: приблизно у 60 000 разів швидше. Причина — алгоритмічна складність: індекс — це окрема відсортована структура, що живе поруч із таблицею, тож пошук стає бінарним — O(log N) замість повних сканів O(N). Його фірмова ілюстрація: на 50 рядках лінійний перебір робить 50 кроків, а на 100 трильйонах рядків бінарному пошуку треба лише ~46 кроків — «log N — це практично безкоштовно». Далі він показує, де індекси ламаються: LIKE 'prefix%' — миттєвий (відсортовані дані підтримують пошук за префіксом), але LIKE '%substring%' займає ~7 секунд, бо жодний порядок сортування не допоможе знайти фразу всередині значення — для цього потрібен інвертований / повнотекстовий індекс («усі кажуть "візьми Elastic", а що той Elastic насправді робить?»), який він обіцяє побудувати руками в наступному відео, згадуючи, що колись реалізував кастомний індекс повнотекстового пошуку по 300 ТБ даних у продакшені. Наприкінці — EXPLAIN для перевірки використання індексу, погляд на те, як індекс зберігає проіндексовану колонку плюс вказівник на рядок, і застереження: кожен запис перебудовує індекси, тож у таблицях із інтенсивним записом не варто індексувати кожну колонку.
Головне
- Реальний вимір, той самий запит: 1 тис. рядків ≈ 0,3 мс, 10 млн рядків ≈ 3,3 с без індексу; з індексом на
name≈ 0,05 мс — приблизно у 60 000 разів швидше (індекси). - Запит на 3 секунди — це не просто повільно: під вебнавантаженням запити накопичуються швидше, ніж завершуються, і база валиться.
- Індекс — це відсортована структура даних, що зберігається поруч із таблицею (на практиці B+ дерево; існують і хеш-індекси); відсортовані дані уможливлюють бінарний пошук, а O(log N) — це ~46 кроків навіть для 100 трильйонів рядків (алгоритмічна складність).
- Індекси працюють для точних збігів і
LIKE 'prefix%', і навіть для пошуку за суфіксом, якщо побудувати індекс «у зворотний бік», — але ніколи дляLIKE '%word%': «сортуй чи не сортуй — нічого не допоможе знайти фразу всередині» — для цього потрібен інвертований індекс (повнотекстовий пошук). - Використовуйте
EXPLAIN(однаково в MySQL і Postgres), щоб перевірити, чи запит справді використовує індекс. - Індекс зберігає проіндексовану колонку плюс вказівник на рядок; щоб дістати інші колонки (наприклад,
description), потрібен другий похід у таблицю — а MySQL і Postgres організовують таблиці зовсім по-різному (кластерний індекс проти heap; MySQL фактично не може існувати без первинного ключа). - Індекси не безкоштовні: кожен INSERT/UPDATE перебудовує кожен індекс таблиці, тож при інтенсивному записі менше індексів може бути краще.
- Байка з практики: він колись побудував саморобний повнотекстовий (інвертований) індекс із пошуком по 300 ТБ даних, включно з кастомним механізмом пакування індексу.