Бази даних і структури даних / крок 04
Як працюють індекси в базах на прикладі: MySQL vs Postgres, UUID vs Auto Increment
Про що це відео
«Хардкорна» кульмінація серії про індекси: наполовину теорія, наполовину живі експерименти на таблиці з 16 млн рядків — усе на підтримку тези автора, що треба розуміти нутрощі, аби передбачати властивості технології (глибоке вивчення основ). Ключові нутрощі: у MySQL сама таблиця — це B+ дерево, відсортоване за первинним ключем (кластерний індекс), тож кожен пошук через вторинний індекс — це подвійний пошук: спершу вторинний індекс (який зберігає первинний ключ як вказівник на рядок), потім кластерний; у Postgres кластерного індексу немає — вторинні індекси зберігають фізичне розташування рядка у файлі. Далі він пояснює MVCC: обидві бази копіюють рядки на кожну транзакцію, і оскільки копії рядків у Postgres лягають на нові фізичні адреси, оновлення однієї індексованої колонки змушує Postgres перебудувати всі індекси таблиці (оптимізація HOT — heap-only tuple — допомагає, лише якщо копія вмістилася в той самий блок і жодна індексована колонка не змінилася); MySQL оновлює лише зачеплений індекс. Він киває на знамениті міграції Uber Postgres→MySQL→Postgres як наслідок саме цих нюансів. Практичний центр — UUID проти auto increment: оскільки MySQL дублює первинний ключ у кожному вторинному індексі, UUID як первинний ключ там «катастрофічний» — його заміряні таблиці: auto-increment 4.3 ГБ, auto-increment + окрема колонка UUID 4.9 ГБ, UUID як PK 7.8 ГБ; вторинні індекси роздулися з 2 ГБ до 5.5 ГБ, тобто ~70% байтів індексів — це просто UUID-PK. Випадкові UUID-вставки також трощать кешування вузлів B+ дерева — вставки пішли з ~4 с до ~5.5 с на 1000 рядків навіть на його топовому SSD (на повільніших дисках він бачив 2.5–3×). Подальші експерименти: покривні індекси (додай до індексу колонку, за якою ніколи не фільтруєш, — наприклад (year, name) — і запит взагалі не торкається основної таблиці; EXPLAIN показує "covering index"), прихована ціна пагінації з OFFSET 1000000 навіть з індексом (~10 с, бо ланцюжок листків доводиться гортати на мільйон записів углиб) і видалення індексів, що зрізає час вставки з 5.5 с до ~1.2 с.
Головне
- Таблиця MySQL — сама по собі B+ дерево, впорядковане за первинним ключем (кластерний індекс); вторинні індекси зберігають PK, тож пошук не за PK шукає двічі. Таблиці Postgres — невпорядковані «купи» (heap); індекси вказують на фізичні розташування рядків (Індекси баз даних, B-tree / B+ tree).
- За MVCC оновлення в Postgres фізично переміщує рядок, тож доводиться оновити кожен індекс таблиці — навіть якщо ви змінили неіндексовану колонку (оптимізація HOT допомагає лише в межах одного блоку 8 КБ); MySQL, що посилається на рядки через PK, торкається лише зміненого індексу. Міграції Uber туди-сюди він наводить як наслідок цих нутрощів.
- UUID проти auto-increment у MySQL: UUID як первинний ключ роздув його таблицю з 4.3 ГБ до 7.8 ГБ, а вторинні індекси — з 2 ГБ до 5.5 ГБ (~70% простору індексів — сам PK, майже втричі більше RAM під індекси); контрінтуїтивне рішення — залишити auto-increment PK і зберігати UUID окремою колонкою — виходить меншим і швидшим попри «додану» колонку. Postgres до цього здебільшого нечутливий, бо ніколи не вбудовує PK в інші індекси.
- Випадкові (UUID) вставки ламають кешування вузлів B+ дерева: послідовні вставки торкаються лише крайніх правих закешованих вузлів, випадкові — трощать кеш: вставки по 1000 рядків пішли 4 с → 5.5 с на найшвидшому споживчому SSD, у 2.5–3 рази гірше на повільніших сховищах.
- У MySQL не буває таблиці без первинного ключа — якщо його не вказати, він мовчки додає прихований 6-байтовий auto-increment; оголошення власного 4-байтового заощаджує 2 байти × кожен рядок × кожен індекс (гігабайти RAM на 100 млн рядків, а індекси мають жити в RAM).
- Покривні індекси: додавання суто «відображуваної» колонки до індексу (наприклад
(year, name)) дозволяє відповісти на весь запит з самого індексу — він демонструє, як запит падає з ~10 с до миттєвого — ціною додаткових копій на диску. - Навіть з індексом
ORDER BY ... OFFSET 1000000 LIMIT 1повільний: відсортований ланцюжок листків усе одно доводиться пройти на мільйон записів углиб — тож пагінація «остання сторінка» болить на масштабі. - Індекси — податок на запис: видалення вторинних індексів зрізало час вставки ~вчетверо (5.5 с → 1.2 с на батч); не індексуйте все підряд за замовчуванням.
- Фінальна рамка: з трьох програмістів — того, хто не знає про існування індексів; того, хто знає, що «індекси прискорюють»; і того, хто розуміє їхні нутрощі, — лише третій може реально проектувати під поведінку бази й передбачати її (глибоке вивчення основ).