Індекси і швидкодія запитів

Що таке індекс і чому він пришвидшує читання?

Індекс (index) — допоміжна структура, що живе окремо від таблиці й постійно тримається відсортованою за значеннями обраних колонок. Головна ідея — впорядкованість: у відсортованих даних можна шукати діленням навпіл, як прізвище в телефонній книзі, а не читати все підряд. Без індексу базі лишається послідовне сканування (sequential scan) — перебір рядок за рядком, і на 50 мільйонах рядків це десятки секунд. З індексом вартість пошуку падає з n до приблизно log(n) кроків. Але це не безкоштовно: за швидше читання платиш повільнішим записом і місцем на диску — і без згадки про цей компроміс відповідь читається як зубріння.

Що таке B-дерево і чому пошук у ньому коштує log(n)?

B-дерево (B-tree) — збалансоване дерево пошуку, тип індексу за замовчуванням у PostgreSQL, MySQL і більшості СУБД. Ключове слово — «збалансоване»: кожен листок розташований на тій самій глибині, тому будь-яке значення шукається за однакову кількість кроків. Щоб знайти рядок, база спускається від кореня: на кожному вузлі порівнює шукане значення з межами й обирає одну гілку, відкидаючи решту. Саме тому кількість кроків росте як log(n), а не n — кожен рівень звужує простір пошуку в рази. Навіть таблиця на десятки мільйонів рядків дає дерево глибиною всього 3–5 рівнів — три-п'ять порівнянь замість мільйонів.

Які запити пришвидшує B-tree, окрім точного пошуку по рівності?

Впорядкованість B-дерева працює не лише на точний пошук (=): діапазони (<, >, BETWEEN), ORDER BY і префіксний LIKE 'abc%' теж лягають на нього, бо в кожному з цих випадків є звідки почати спуск — точка, межа діапазону або початок рядка. Дрібний шрифт для PostgreSQL: у базі з не-C локаллю під LIKE-префікси індекс створюють з операторним класом text_pattern_ops, інакше планувальник його не візьме. А LIKE '%abc' з провідним відсотком не прискорити жодним B-деревом — початок значення невідомий, спускатися нема від чого, і база вертається до послідовного сканування. Це практично важливо: пошук «містить підрядок» вимагає інших засобів (повнотекстовий чи триграмний індекс).

Чи треба створювати індекс під первинний ключ і UNIQUE вручну?

Ні — база будує його автоматично. Оголошення первинного ключа (primary key) чи обмеження UNIQUE тягне за собою унікальний індекс, і це не примха: перевірка «чи немає вже такого значення?» при кожній вставці сама вимагає швидкого пошуку — а швидкий пошук і є індекс. Практичний наслідок — фільтри по id чи унікальному email швидкі з коробки, навіть якщо ти жодного індексу руками не створював. Тому частину роботи з продуктивністю за тебе вже зробило оголошення схеми.

Чи створюється індекс під зовнішній ключ автоматично?

Тут поведінка СУБД розходиться, і це улюблене питання інтерв'юерів. У PostgreSQL FOREIGN KEY не породжує індексу на колонці-посиланні: автоматично індексований лише бік, на який FK вказує, — первинний ключ батьківської таблиці. Тому JOIN або WHERE user_id = 42 по FK-колонці ризикує з'їхати в послідовне сканування, доки індекс не додано вручну. У MySQL (InnoDB) індекс під зовнішній ключ з'являється сам — рушій без нього просто не приймає FK. Практичний висновок для QA: зв'язок між таблицями ще не гарантує швидких запитів по ньому — на PostgreSQL це перевіряють окремо через EXPLAIN.

Чим кластерний індекс відрізняється від некластерного?

Різниця про фізичне зберігання даних. Кластерний індекс (clustered index) задає, як рядки фізично розкладені на диску, і саме тому він єдиний на таблицю: одні й ті самі дані неможливо фізично впорядкувати двома способами. Пошук по ньому одразу дає рядок — покажчик і є самі дані. Некластерний (non-clustered), або вторинний, індекс живе окремо від таблиці й у листках тримає не дані, а покажчики; таких індексів скільки завгодно, але за кожен пошук платиш зайвим кроком: спершу покажчик, потім сам рядок. Сильна відповідь називає реалізацію: у MySQL InnoDB уся таблиця — це кластерний індекс за PK, а в PostgreSQL таблиця зберігається як «купа» (heap) і всі індекси вторинні.

Як зберігається таблиця в InnoDB і чим це загрожує при широкому первинному ключі?

В InnoDB уся таблиця фізично є кластерним індексом за первинним ключем — рядки лежать упорядковані за PK. Наслідок: вторинний індекс у листках тримає не прямий покажчик на рядок, а значення PK, тож пошук по ньому — це два спуски: спершу знайшли PK, потім по ньому — рядок у кластерному індексі. Звідси практичне правило: довгий або невпорядкований первинний ключ (рядковий ключ, випадковий UUID) збільшує кожен вторинний індекс, адже копія PK лежить у кожному з них. Це реальний аргумент за компактні цілочислові сурогатні ключі — вони економлять місце в усіх індексах одразу.

Що таке складений індекс і правило лівого префікса?

Складений (composite) індекс будується на кількох колонках одразу, і сортування в ньому словникове: головний ключ порівняння — перша колонка, при рівності — друга, далі третя. Звідси правило лівого префікса (leftmost prefix): запит має накривати колонки індексу зліва направо без дірок. Для індексу на (a, b, c) придатні умови по a, по парі a+b і по всіх трьох — а от фільтр лише по b чи лише по c індекс не задіє. Причина проста: без значення a немає точки входу для спуску деревом — усе одно що гортати словник у пошуках слова, від якого знаєш лише третю літеру.

У якому порядку ставити колонки у складеному індексі?

Порядок — не косметика, а рішення, від якого залежить, які запити індекс пришвидшить. Загальне правило: колонки з умовою на рівність (=) ставлять ліворуч, а колонку з діапазоном (<, >, BETWEEN) чи сортуванням — праворуч. Тоді база спершу точно позиціонується по рівності, а решту читає як готовий упорядкований відрізок — діапазон чи ORDER BY дістаються безкоштовно. Класика — індекс на (user_id, created_at) під «останні замовлення користувача»: спуск у гілку user_id = 42, а всередині неї рядки вже стоять по даті, тож окремого сортування не буде. Переставиш колонки — і той самий запит ляже на індекс значно гірше.

Ти додав індекс, а запит не пришвидшився. Які причини перевіряєш?

Найчастіше індекс є, але ним неможливо скористатися, і це видно в EXPLAIN як Seq Scan. Перша причина — функція чи вираз над колонкою: WHERE lower(email) = 'a@b.com' не задіє звичайний індекс на email, бо в індексі лежать вихідні значення, а не результати lower(). Друга — неявне приведення типів: якщо phone рядковий, а в запиті число, база перетворює типи й індекс «відклеюється». Третя — провідний символ підстановки в LIKE '%abc'. Четверта — низька селективність: коли умова пропускає більшість рядків, планувальник свідомо йде в seq scan — суцільне читання обходиться дешевше за мільйони точкових звернень через індекс. Тому перший крок діагностики завжди один — подивитися в EXPLAIN, чи індекс узагалі задіяний.

Що таке селективність і як вона впливає на вибір плану?

Селективність (selectivity) — це наскільки умова звужує вибірку: висока селективність відбирає малу частку рядків, низька — велику. Планувальник ураховує її, щоб вирішити, чи вигідно взагалі йти в індекс. Якщо WHERE status = 'active' пропускає 90% таблиці, база свідомо піде в послідовне сканування: один суцільний прохід диском коштує менше, ніж мільйони випадкових стрибків між індексом і рядками. Індекс окупається лише тоді, коли умова відсіює більшість рядків. Тому індекс на колонку з двома-трьома значеннями (status, is_deleted) часто марний — а той самий стовпець усередині складеного індексу разом із селективною колонкою може бути цілком доречним.

Якщо індекси такі корисні, чому не навісити їх на кожну колонку?

Бо кожен індекс — це борг, який обслуговується на запис. Кожен INSERT, UPDATE чи DELETE зачіпає не лише рядок: усі індекси, куди цей рядок входить, теж доводиться оновлювати — п'ять індексів означають п'ять додаткових структур на кожну вставку. Ціна складається з трьох частин: повільніший запис (відчутно для таблиць з інтенсивним записом), дисковий простір (на великій таблиці індекс сам розростається до гігабайтів) і робота планувальнику, який зайві чи дубльовані індекси все одно розглядає й підтримує актуальними. Тому індекс — завжди компроміс «швидше читання ↔ повільніший запис», а правильний набір визначають за реальними запитами, а не «про запас».

Що показує EXPLAIN і чим він відрізняється від EXPLAIN ANALYZE?

EXPLAIN показує план виконання (query plan) — як саме база збирається виконати запит: які сканування, які з'єднання, у якому порядку. Важливий нюанс: звичайний EXPLAIN — це лише прогноз планувальника, запит при цьому не виконується. EXPLAIN ANALYZE натомість проганяє запит по-справжньому й до кожного вузла плану дописує фактичний час та кількість рядків — коли треба справжня швидкодія, а не гіпотетична, беруть саме його. Практична пастка: EXPLAIN ANALYZE виконує запит по-справжньому, тож на UPDATE/DELETE він змінить дані — на проді його загортають у транзакцію з відкатом. Для читання плану без ризику досить звичайного EXPLAIN.

Що означає Seq Scan проти Index Scan у плані, і на що дивитися QA?

Seq Scan — база перебирає таблицю цілком, відкидаючи рядки, що не пройшли Filter; на 50 мільйонах рядків це дорого. Index Scan — спуск деревом за умовою Index Cond і точкове діставання лише потрібного. Головний сигнал проблеми для QA — Seq Scan на великій таблиці там, де ти очікував index scan: або індексу немає, або запит написаний так, що ним не скористатися. Друге — наскільки оцінка rows збігається з фактом у EXPLAIN ANALYZE: коли планувальник розраховував на 10 рядків, а отримав 2 мільйони, статистика протухла й план обрано на хибних даних. Для повільних запитів із багатьма таблицями вузьким місцем часто є порядок і тип JOIN (Nested Loop, Hash Join).

Числа cost у виводі EXPLAIN — це мілісекунди?

Ні, і це поширена пастка. cost — умовні одиниці вартості, у яких планувальник порівнює плани між собою, щоб обрати найдешевший; до реального часу вони не прив'язані. Наприклад, cost=0.00..1043210.00 для seq scan проти cost=0.56..8.58 для index scan — різниця на п'ять порядків, і за нею видно, що план з індексом кращий, але сказати «запит виконається за 8 мілісекунд» на цій підставі не можна. Реальний час у мілісекундах дає лише EXPLAIN ANALYZE, який запускає запит і міряє actual time. Тому в баг-репорті про швидкодію посилаються саме на ANALYZE, а не на оцінкові cost.

Чому проблему повільного запиту часто не видно на локальній базі?

Бо на малих даних планувальник поводиться інакше. На кількох сотнях чи тисячах рядків послідовне сканування миттєве, і база й так не пішла б в індекс — дрібну таблицю дешевше прочитати цілком, ніж лізти в дерево. Відсутній індекс дає про себе знати лише на прод-масштабі, де тих самих рядків десятки мільйонів. Тому обсяг даних — це частина умов відтворення бага: швидкодію перевіряють на реалістичних обсягах, а не на десятку рядків із фікстури. Це найпідступніший клас дефектів: усі перевірки зелені й на локальній базі, й на стейджі, а на проді користувач дивиться на спінер — і формально «все працює».

Чому повільний запит — це баг, і як його правильно завести?

Швидкодія — не приємний бонус, а нефункціональна вимога: у моделі якості ISO/IEC 25010 продуктивність (performance efficiency, зокрема time behaviour) — окрема характеристика того ж рангу, що й функціональність. Тож коректний результат, який їде до користувача 30 секунд, — усе одно дефект, і його заводять як повноцінний баг. Силу репорту дає план виконання: не «сторінка замовлень довго вантажиться», а конкретика — текст запиту, вивід EXPLAIN ANALYZE, зафіксований Seq Scan на мільйонах рядків, гіпотеза про відсутній індекс. Із таким тікетом розробнику лишається тільки виправити — діагностика вже зроблена. Плюс дисципліна: обсяг даних вказують в умовах відтворення, бо на малій базі проблема невидима.

Три кейси на демо-таблиці orders (id, user_id, email, status, amount, created_at, 50 млн рядків): читаємо EXPLAIN ANALYZE й бачимо, як seq scan перетворюється на index scan; розбираємо таблицею, які запити ляжуть на складений індекс, а які ні; ставимо в автотесті гард на регресію плану й складаємо баг-репорт про повільний запит. Скрізь — що дивитися і чому.

Кейс 1. EXPLAIN ANALYZE: seq scan проти index scan

Сторінка «мої замовлення» вантажиться 20+ секунд на проді, а локально — миттєво. Замість гадати, дивимося план того самого запиту. Без індексу на email:

EXPLAIN ANALYZE
SELECT * FROM orders WHERE email = 'a@b.com';

Seq Scan on orders  (cost=0.00..1043210.00 rows=1 width=64)
                    (actual time=812.4..19533.7 rows=1 loops=1)
  Filter: (email = 'a@b.com')
  Rows Removed by Filter: 49999999
Planning Time: 0.09 ms
Execution Time: 19533.9 ms

Додаємо індекс і повторюємо:

CREATE INDEX orders_email_idx ON orders (email);

Index Scan using orders_email_idx on orders  (cost=0.56..8.58 rows=1 width=64)
                                             (actual time=0.041..0.043 rows=1 loops=1)
  Index Cond: (email = 'a@b.com')
Planning Time: 0.12 ms
Execution Time: 0.071 ms

Що дивитися і чому:

• Seq Scan + Rows Removed by Filter: 49999999 — база прочитала всі 50 млн рядків, щоб віддати один. Це і є діагноз: запит перебирає таблицю поспіль, індексу немає або ним не скористатися.
• actual time проти cost. cost=1043210 — абстрактні одиниці для порівняння планів, а actual time ... 19533.7 — реальні мілісекунди. У баг-репорт іде саме Execution Time з ANALYZE, а не оцінковий cost.
• rows=1 в оцінці збігся з rows=1 у факті — статистика жива. Якби планувальник чекав 1 рядок, а прийшло 2 млн, це сигнал застарілої статистики: план обрано хибно, треба ANALYZE/VACUUM ANALYZE.
• Після індексу — Index Scan і Execution Time: 0.071 ms. Падіння з ~19.5 с до часток мілісекунди на тих самих даних. Локально різниці не було б узагалі: на тисячі рядків seq scan і так миттєвий, тож проблему видно тільки на прод-обсязі.

Кейс 2. Лівий префікс: який запит ляже на складений індекс

Під типові запити «останні замовлення користувача» створюємо складений індекс. Порядок колонок — рівність ліворуч, сортування праворуч:

CREATE INDEX orders_user_created_idx ON orders (user_id, created_at);

SELECT * FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 20;

Індекс (user_id, created_at) упорядкований як словник: спершу за user_id, усередині кожного user_id — за created_at. Тому база спускається до гілки user_id = 42 й читає рядки вже відсортованими — окреме сортування не потрібне. А тепер таблиця, які запити цей індекс пришвидшить, а які ні:

Що дивитися і чому:

• Фільтр тільки по created_at індекс не задіє. Це прямий наслідок лівого префікса: без значення першої колонки спуск неможливий. Якщо такий запит потрібен часто — це аргумент за окремий індекс на created_at, а не за переоблаштування наявного.
• Порядок колонок — рішення, не косметика. Індекс на (created_at, user_id) під той самий «останні замовлення користувача» ляже гірше: спершу довелося б відбирати за датою, а не точно позиціонуватися по user_id.
• Селективність вирішує, чи взагалі варто. Якщо user_id майже унікальний — індекс золото. Якби ми першою колонкою поставили status із трьома значеннями, префікс по ньому лишав би в кандидатах близько третини таблиці, і планувальник міг би знехтувати індексом.

Кейс 3. Гард на регресію плану + баг-репорт

План критичного запиту не має тихо скочуватися в Seq Scan після рефакторингу. Маючи підключення до бази поряд із Playwright, ставимо гард, який ловить регресію продуктивності до того, як вона доїде на прод:

import { test, expect } from '@playwright/test';
import { Client } from 'pg';

test('план критичного запиту лишається Index Scan', async () => {
  const client = new Client({ connectionString: process.env.DATABASE_URL });
  await client.connect();
  try {
    const { rows } = await client.query(
      'EXPLAIN (FORMAT JSON) SELECT * FROM orders WHERE user_id = $1 ' +
        'ORDER BY created_at DESC LIMIT 20',
      [42],
    );
    // ORDER BY/LIMIT кладе зверху вузол Limit, тож шукаємо Seq Scan по всьому дереву плану
    const hasSeqScan = (node: any): boolean =>
      node['Node Type'] === 'Seq Scan' ||
      (node.Plans ?? []).some(hasSeqScan);
    expect(hasSeqScan(rows[0]['QUERY PLAN'][0].Plan),
      'критичний запит скотився в Seq Scan').toBe(false);
  } finally {
    await client.end();
  }
});

Коли гард червоніє (або запит просто повзе), заводимо дефект — не «сторінка гальмує», а з планом на столі:

Заголовок: [perf] Сторінка замовлень (фільтр по email) — 19.5 с на проді, Seq Scan на 50M рядків

Кроки відтворення:
  1. Прод-обсяг orders (~50 млн рядків) — обов'язкова умова, на малій базі невідтворно.
  2. EXPLAIN ANALYZE SELECT * FROM orders WHERE email = 'a@b.com';

Факт:
  Seq Scan on orders (actual time=812..19533 ms), Rows Removed by Filter: 49999999
  Execution Time: 19533.9 ms

Очікування:
  Index Scan, Execution Time у межах десятків мс.

Гіпотеза: відсутній індекс на orders.email (фільтр по email не покритий).

Що дивитися і чому:

• EXPLAIN (FORMAT JSON) дає машиночитний план. Обхід дерева планів за Node Type — надійний якір для асерту (з ORDER BY/LIMIT корінь плану — це Limit, тож перевіряти лише верхній вузол мало); парсити текстовий вивід крихкіше. EXPLAIN без ANALYZE нічого не виконує, тож гард безпечний і швидкий.
• Обсяг даних — у кроках відтворення першим рядком. Без цього розробник відкриє тікет на локальній базі, побачить 0.07 ms і закриє як «не відтворюється». Найпідступніший клас perf-багів невидимий на фікстурі.
• План замість прикметників. «Довго вантажиться» → Seq Scan на мільйонах рядків + Execution Time + гіпотеза про індекс. Причина вже на столі — такий репорт закривають швидко.
• Не заявляй причину без доказу. «Схоже, немає індексу на email, бо в плані Seq Scan із Rows Removed by Filter: 49999999» коштує рівно стільки, скільки під ним видно в EXPLAIN.

Що таке індекс і B-дерево

• Можу пояснити, що індекс — це впорядкована допоміжна структура, і що вся швидкість тримається на впорядкованості, а не на «магії».
• Знаю, що тип індексу за замовчуванням — B-дерево, воно збалансоване (усі листки на однаковій глибині), і пошук коштує log(n), а не n.
• Розумію, що B-дерево пришвидшує =, діапазони (<, >, BETWEEN), ORDER BY і LIKE 'abc%', але безсиле проти LIKE '%abc'.

Індекси «безкоштовно»: PK, UNIQUE, FK

• Знаю, що під первинний ключ і UNIQUE індекс створюється автоматично, тож пошук по id чи унікальному email швидкий за замовчуванням.
• Знаю різницю по FK між СУБД: PostgreSQL під зовнішній ключ індекс не створює, MySQL InnoDB — створює.

Clustered vs non-clustered

• Можу пояснити різницю: кластерний індекс задає фізичний порядок рядків (лише один на таблицю), некластерний — окрема структура з покажчиками (їх багато).
• Знаю, як це реалізовано: InnoDB — уся таблиця кластерна за PK; PostgreSQL — таблиця це heap, усі індекси вторинні.

Складений індекс і лівий префікс

• Знаю правило лівого префікса: індекс на (a, b, c) працює для a, для a, b, для a, b, c, але не для самого b чи самого c.
• Можу пояснити правило порядку колонок: рівність (=) ліворуч, діапазон/сортування — праворуч.

Коли індекс не рятує

• Знаю, чому функція над колонкою (lower(email)) вбиває звичайний індекс і що рятує функціональний індекс.
• Пам'ятаю про неявне приведення типів (phone = 380... число проти рядка) як причину «відклеєного» індексу.
• Розумію селективність: на неселективній умові (status = 'active', 90% рядків) планувальник свідомо обирає seq scan — і це правильно.

Ціна індексу

• Можу пояснити три складові ціни: повільніший запис (INSERT/UPDATE/DELETE оновлює кожен індекс), місце на диску, робота планувальнику.
• Знаю, що правильний набір індексів визначають за реальними запитами, а не «про запас».

EXPLAIN і план виконання

• Знаю різницю EXPLAIN vs EXPLAIN ANALYZE: перший лише оцінює план, другий реально виконує запит і дає фактичний час.
• Розумію, що cost у виводі — абстрактні одиниці для порівняння планів, а не мілісекунди.
• Умію читати сигнал: Seq Scan на великій таблиці там, де очікувався index scan, — перший підозрюваний.

Повільний запит як дефект

• Розумію, що швидкодія — нефункціональна вимога (ISO/IEC 25010, time behaviour), а не бонус: правильний результат за 30 с це баг.
• Пам'ятаю, що обсяг даних — частина умов відтворення: перевіряю швидкодію на реалістичних обсягах, а не на фікстурі з десяти рядків.
• Можу скласти сильний баг-репорт: запит + EXPLAIN ANALYZE + видимий Seq Scan + гіпотеза про відсутній індекс.