Індекси баз даних

Найщільніша тема каналу. Базове формулювання Віктора: індекс — це концептуально просто «скопіюй колонку і відсортуй» — відсортована структура, що зберігається поруч із таблицею і містить індексовану колонку плюс вказівник на рядок (навіщо потрібні індекси, Q&A і плани на 2024). Оскільки одну таблицю неможливо тримати відсортованою за двома колонками водночас, кожен індекс — це окрема структура (дерева, алгоритми пошуку і бази даних). Його фірмове демо: ідентичний запит на 1 тис. рядків виконується 0.3 мс, а на 10 млн рядків — 3.3 с; додай індекс — і час падає до ~0.05 мс, приблизно у 60 000 разів швидше, бо сортування перетворює скан за O(N) на бінарний пошук за O(log N) (навіщо потрібні індекси, навіщо потрібні алгоритми). У бенчмарках фільтра Блума той самий ефект видно знову: неіндексований скан у MySQL займає ~18 с на 10 запитів за відсутніми ключами, тоді як індексована таблиця виконує 100 000 запитів за ~17 с — «індекси неймовірно швидкі» (фільтр Блума і Firefox).

Але індекси не безкоштовні, і чимала частина матеріалу — про те, де вони шкодять або відмовляють. Кожен запис мусить оновити всі індекси таблиці: його експеримент на 16 млн рядків показує, що видалення індексів скорочує час вставки з 5.5 с до 1.2 с на батч, тож таблицям з інтенсивним записом варто індексувати менше (індекси: MySQL проти Postgres, навіщо потрібні індекси). Повільні запити не просто повільні: 3-секундний запит під вебнавантаженням накопичується і кладе всю базу (навіщо потрібні індекси). А B-tree-індекс допомагає лише там, де існує порядок сортування: LIKE 'prefix%' виконується миттєво, а LIKE '%word%' — 40 с, бо колонку неможливо відсортувати за словом усередині значення — саме ця відмова мотивує інвертований індекс (повнотекстовий пошук).

Глибший шар — нутрощі рушіїв. У MySQL сама таблиця є кластерним індексом (B+ деревом, відсортованим за первинним ключем), тож лукап за вторинним індексом — це подвійний пошук: вторинний індекс → первинний ключ → кластерний індекс. Postgres натомість зберігає фізичні адреси рядків у невпорядкованій купі (heap) (індекси: MySQL проти Postgres). Звідси і практичні трюки, які він демонструє: покривні індекси (додай до індексу колонки, потрібні лише для відображення, — і запит з ~10 с стає миттєвим; композитний двоколонковий індекс — це дворівневе сортування, що обслуговує (A) і (A,B), але ніколи (B) окремо), прихована ціна пагінації через OFFSET 1000000 навіть з індексом, селективність, яка визначає, чи допоможе індекс узагалі, і навіть Handler Socket — прямий доступ до індексу в обхід планувальника запитів MySQL, що перетворює його на key-value-сховище, — який виявився лише трохи швидшим за індексовані prepared statements (індекси: MySQL проти Postgres, Q&A і плани на 2024, фільтр Блума і Firefox). Розмір ключа теж важить: оскільки UUID — це hex, зберігання їх у сирому бінарному вигляді зменшує їх удвічі, але первинний ключ BINARY(16) все одно зʼїдає понад половину байтів індексу — він лишив би автоінкрементний PK, а UUID виніс би в окрему колонку (як працює Base64, перше Q&A, UUID проти автоінкремента).