Індекси
Навіщо це
Section titled “Навіщо це”Сторінка «Мої замовлення» у «Крамниці» показує покупцеві двадцять останніх замовлень. Запит простий, а індексів у датасеті, крім первинних ключів, немає:
EXPLAIN (ANALYZE, BUFFERS)SELECT order_id, placed_at, status, total_amountFROM ordersWHERE customer_id = 16877ORDER BY placed_at DESC, order_id DESCLIMIT 20;На розмірі medium (220 тисяч замовлень, див. Датасет) база читає всю таблицю, щоб знайти 171 замовлення цього покупця, і залишає двадцять найновіших:
Limit (actual time=7.126..9.089 rows=20.00 loops=1) Buffers: shared hit=2687 -> ... Parallel Seq Scan on orders (rows=85.50 loops=2) Execution Time: 9.157 ms2687 буферів, 9 мс. Буфер — сторінка, прочитана з пам’яті чи з диска. Їх число не залежить від швидкості машини, тому далі міркою служить воно, а не час. Послідовне сканування читає всю таблицю, тож і буфери, і час ростуть разом із нею.
Після CREATE INDEX orders_customer_placed_idx ON orders (customer_id, placed_at DESC) той самий запит читає 27 буферів і йде 0.1 мс.
Зворотний бік видно на запису. Вставка 100 тисяч замовлень у таблицю з трьома додатковими індексами триває втричі-вчетверо довше, ніж без них. Оновлення, що було дешевим, починає писати в усі індекси одразу. Саме так у 2016 році Uber пояснив перехід з PostgreSQL на MySQL (розбір нижче).
Передумови. Сторінка, heap і ctid: модуль 7. Вибір планувальником між скануванням і індексом та повне читання EXPLAIN: модуль 9; тут EXPLAIN лише показує, чи використано індекс і скільки сторінок прочитано. CREATE INDEX CONCURRENTLY і недійсні індекси: модуль 4.
Виводи нижче виміряно на PostgreSQL 18.6 у Docker, розмір medium, якщо не сказано інше.
Індекс як відсортований список
Section titled “Індекс як відсортований список”Індекс — окрема структура, де ключі лежать упорядковано, а поруч із кожним адреса рядка в таблиці. За відсортованим списком шукають діленням навпіл. Бінарне дерево пошуку на 220 тисяч ключів має близько 18 рівнів, і кожен рівень у базі означав би окреме читання сторінки.
Тому вузлом дерева роблять саму сторінку, а не один ключ. Сторінка в 8 КіБ вміщує сотні ключів, і кожен рівень звужує пошук у сотні разів, а не вдвічі. Це B+-дерево. Три-чотири читання сторінок знаходять один рядок і в таблиці з мільйонами рядків.
Висота залежить від ширини ключа. На окремій таблиці із 6 мільйонами рядків:
| Ключ | Розмір індексу | Рівнів | Буферів на пошук |
|---|---|---|---|
bigint |
129 МіБ | 3 | 4 (3 у дереві й 1 у таблиці) |
| текст із 64 символів | 547 МіБ | 4 | 5 |
Вузький ключ дає три рівні й на десятках мільйонів рядків, широкий доходить до чотирьох раніше.
Ключі лежать упорядковано, тому індекс допомагає не лише знайти рівність. Діапазон (BETWEEN, >=) знаходить нижню межу й далі йде по сусідніх записах. ORDER BY за ключем індексу обходиться без кроку сортування, бо записи вже впорядковані.
Складений індекс і порядок колонок
Section titled “Складений індекс і порядок колонок”Складений індекс упорядковує записи за першою колонкою, у межах рівних значень за другою і так далі, як телефонна книга: прізвище, потім ім’я.
Запит customer_id = 27672 AND placed_at >= '2025-01-01' (у покупця 256 замовлень, вибирається 120) виконано з двома індексами одного складу й різного порядку:
| Індекс | Буферів |
|---|---|
(customer_id, placed_at) |
125 |
(placed_at, customer_id) |
588 |
Другий індекс теж використано, але він читає всі записи від 2025 року й відкидає чужих покупців усередині індексу. Звідси правило: спершу колонки з рівністю, потім одна колонка з діапазоном або сортуванням. Правило лівого префікса є його наслідком: індекс (customer_id, placed_at) допомагає запитам, що задають customer_id, і майже не допомагає запиту лише за placed_at.
CREATE INDEX orders_customer_placed_idx ON orders (customer_id, placed_at DESC);CREATE INDEX orders_status_placed_idx ON orders (status, placed_at);
EXPLAIN (ANALYZE, BUFFERS)SELECT count(*) FROM orders WHERE placed_at >= '2025-12-30'; Aggregate (actual time=0.123..0.123 rows=1.00 loops=1) -> Index Only Scan using orders_status_placed_idx on orders Index Cond: (placed_at >= '2025-12-30 00:00:00+00'::timestamp with time zone) Heap Fetches: 0 Index Searches: 5 Buffers: shared hit=20З (customer_id, placed_at) цей запит читав би всю таблицю (2640 буферів). Але в PostgreSQL 18 з’явився skip scan: якщо в першій колонці мало різних значень, як у status, база робить по пошуку на кожне значення, і складений індекс працює без умови на початок. У плані це Index Searches: 5. Для customer_id з десятками тисяч значень прийом не окупається, тож правило лишається основним.
Порядок колонок диктує й сортування. Індекс (customer_id, placed_at DESC) віддає замовлення покупця від новіших до старіших, і LIMIT 20 зупиняє читання після двадцяти записів. Для покупця 16877 це 27 буферів проти 172 в індексу лише за customer_id (база знаходить усі 171 замовлення й сортує їх) і 2687 без індексу. Додатковий order_id DESC у ORDER BY лишає над індексом крок Incremental Sort, який читає один зайвий запис, щоб упевнитися, що група рівних placed_at закінчилась.
Покриваючий індекс
Section titled “Покриваючий індекс”Якщо всі колонки запиту лежать в індексі, таблиця не потрібна. Колонки, за якими не шукають, а лише виводять, додають через INCLUDE:
CREATE INDEX orders_customer_cover_idx ON orders (customer_id, placed_at DESC) INCLUDE (status, total_amount);
EXPLAIN (ANALYZE, BUFFERS)SELECT placed_at, status, total_amountFROM ordersWHERE customer_id = 27672ORDER BY placed_at DESCLIMIT 20; Limit (actual time=0.030..0.032 rows=20.00 loops=1) -> Index Only Scan using orders_customer_cover_idx on orders Index Cond: (customer_id = 27672) Heap Fetches: 0 Index Searches: 1 Buffers: shared hit=4 read=3Сім буферів і жодної сторінки таблиці. Платити доводиться місцем: 11 МіБ проти 6.8 МіБ без INCLUDE. Heap Fetches: 0 тримається на карті видимості (visibility map): біт «усі рядки сторінки видимі всім транзакціям» дозволяє не перевіряти рядок у таблиці (модуль 7; чому рядок може бути невидимий, див. модуль 10). Після UPDATE 256 рядків цього покупця біти зникли, і запит показав Heap Fetches: 39 та 43 буфери. VACUUM orders повернув біти й чотири буфери. Колонка поза INCLUDE, додана в SELECT, одразу повертає читання таблиці.
Частковий індекс і індекс за виразом
Section titled “Частковий індекс і індекс за виразом”Частковий індекс будують лише для рядків, що відповідають умові. У orders на medium 308 замовлень зі статусом new або confirmed: це черга, яку оператор дивиться постійно. Індекс на всю колонку status займає 1544 КіБ, а (placed_at) WHERE status IN ('new', 'confirmed') — 16 КіБ. Планувальник його бере, лише якщо умова запиту випливає з умови індексу (status = 'new' випливає, status = 'shipped' ні).
Індекс за виразом будується за результатом виразу. Підтримка шукає покупця за email без урахування регістру. Унікальний індекс за lower(email) не створюється, бо в датасеті є дублікати зі старого імпорту:
CREATE UNIQUE INDEX customers_lower_email_uq ON customers (lower(email));ERROR: could not create unique index "customers_lower_email_uq"DETAIL: Key (lower(email))=(olha_ivanytska784@mail.example) is duplicated.На medium 152 групи покупців мають email, що різниться лише регістром (A.Hordiy@… і a.hordiy@…). Унікальний індекс можливий лише після злиття дублікатів (завдання 22 в L1). Звичайний індекс за виразом працює й із дублікатами:
На medium запит без індексу читав 912 буферів, з індексом за email теж 912 (вираз lower(email) його не використовує), а з індексом за lower(email) лише 5.
Hash, GIN, GiST і BRIN
Section titled “Hash, GIN, GiST і BRIN”B-дерево вміє рівність, діапазон і порядок. Решта типів беруть на себе те, чого воно не вміє: hash (лише =), GIN («які рядки містять це значення»), GiST (перетини й відстані) і BRIN (величезна таблиця зі значеннями в порядку зберігання).
Hash. Хеш-індекс рахує хеш ключа й переходить до кошика. На 610 тисячах подій (view_events, medium) за session_id він зайняв 16 МіБ проти 10 МіБ у B-дерева, а пошук читав 2 сторінки замість 3. Сторінка виграшу не виправдовує більшого індексу без діапазонів.
GIN (інвертований індекс) зберігає відображення «значення → список рядків». Запит про рожеві товари бренду «Kozak Sport» за attributes ->> 'brand' читає всі 2760 сторінок таблиці, а оператор @> («містить») підхоплює GIN:
На medium це 11 буферів замість 2760. Індекс займає 640 КіБ із класом jsonb_path_ops (928 КіБ із типовим jsonb_ops, який підтримує ще й ?). Запит із ->> цей індекс не використає: оператор інший. Для умови з ->> годиться B-дерево за виразами ((attributes ->> 'brand'), (attributes ->> 'colour')). Масиви індексують так само (GIN над string_to_array(attributes ->> 'sizes', ', ') відповідає на @> ARRAY['42']), а повнотекстовий пошук будується тим самим типом над tsvector: модуль 20.
GiST обходить простір за перетинами й відстанями. Найближчі до Києва населені пункти він віддає без сортування всієї таблиці:
CREATE INDEX settlements_geo_gist ON settlements USING gist (point(longitude::float8, latitude::float8));
SELECT nameFROM settlementsORDER BY point(longitude::float8, latitude::float8) <-> point(30.5234, 50.4501)LIMIT 4;Результат: Київ, Вишгород, Вишневе, Софіївська Борщагівка. У плані Index Scan using settlements_geo_gist стоїть рядок Order By: GiST віддає записи за зростанням відстані.
BRIN не зберігає ключі: для кожних 128 сторінок таблиці він пам’ятає найменше й найбільше значення колонки. Це працює, коли значення йдуть у порядку зберігання. view_events заповнюється за часом, кореляція occurred_at із фізичним порядком у pg_stats дорівнює 1:
На medium BRIN займає 24 КіБ, а B-дерево 13 МіБ. Звіт за тиждень читав 6784 буфери без індексу, 79 із B-деревом і 133 з BRIN: BRIN знаходить діапазони, де можуть бути потрібні рядки, читає їх з таблиці й перевіряє (у плані Rows Removed by Index Recheck: 6195). Програш у 54 буфери купує економію 13 МіБ на диску й на записі. Коли порядок у таблиці зіпсується (вставка заднім числом), діапазони розширяться, і BRIN стане повільним скануванням.
Ціна індексу на запис
Section titled “Ціна індексу на запис”Кожен індекс оновлюється разом із таблицею. Вставка рядка додає запис у кожен індекс: спуск деревом до листка, вставка, іноді розбиття сторінки. Усе це потрапляє ще й у WAL (журнал, у який база спершу пише кожну зміну, модуль 11). Вставка 100 тисяч рядків у копію orders (medium) одним INSERT … SELECT, первинний ключ плюс додаткові індекси:
| Додаткових індексів | Час | WAL | Розмір індексів |
|---|---|---|---|
| 0 | 0.16 с | 18.6 МіБ | 2.2 МіБ |
| 3 | 0.55–0.64 с | 47.8 МіБ | 17.9 МіБ |
| 6 | 0.84–0.93 с | 68.5 МіБ | 24.0 МіБ |
WAL у повторах збігався до десятої частки мегабайта. Індекси: (customer_id, placed_at DESC), (pickup_point_id, status, placed_at DESC), (status, placed_at), далі (total_amount), (promo_code), (updated_at). Кожен коштує від 7 до 10 МіБ WAL на 100 тисяч рядків, тоді як BRIN на view_events майже не змінив WAL вставки подій (18 проти 17 МіБ).
Непотрібні індекси знаходять за лічильниками використання:
SELECT indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid)) AS sizeFROM pg_stat_user_indexesWHERE relname = 'orders'ORDER BY idx_scan, pg_relation_size(indexrelid) DESC; indexrelname | idx_scan | size--------------+----------+--------- o_upd | 0 | 4864 kB o_promo | 0 | 1512 kB orders_pkey | 3 | 4856 kB o_cp | 5 | 6808 kBНа експериментальних індексах: o_upd і o_promo ніхто не читав, а оновлює їх кожен запис. Лічильники дивляться за довгий період (день може не містити місячного звіту), а видаляють через DROP INDEX CONCURRENTLY.
HOT-оновлення
Section titled “HOT-оновлення”UPDATE створює нову версію рядка з новою адресою, тож кожен індекс таблиці мусить отримати запис про неї. Виняток називають HOT (heap-only tuple). За документацією, оновлення стає HOT, якщо воно не змінює жодної колонки, що входить до індексу таблиці, і на сторінці старого рядка вистачає місця для нової версії. Тоді запис в індекси не потрібен: індекс веде до старої версії, а та — до нової.
Експеримент: 19 122 оновлення status і updated_at у копії orders (medium) із первинним ключем та двома індексами ((customer_id, placed_at) і (pickup_point_id, placed_at)), без індексу на status і з ним:
fillfactor |
Індекс на status |
HOT із 19 122 | WAL |
|---|---|---|---|
| 100 | ні | 57 | 44.2 МіБ |
| 100 | так | 0 | 45.6 МіБ |
| 90 | ні | 19 096 | 23.1 МіБ |
| 90 | так | 0 | 44.2 МіБ |
Без вільного місця на сторінках (типове fillfactor = 100 щойно завантаженої таблиці) HOT майже не буває. З fillfactor = 90 майже всі оновлення HOT, а WAL удвічі менший. Індекс на змінюваній колонці вимикає HOT цілком: кожне оновлення пише в усі індекси таблиці.
LSM-дерево
Section titled “LSM-дерево”Інша відповідь на ціну запису — не оновлювати дерево на місці, а накопичувати зміни в пам’яті, скидати їх на диск відсортованими файлами й зливати у фоні. Це LSM-дерево (log-structured merge-tree): читання платить за швидкий запис. Докладно в модулі 17.
Усередині B+-дерева
Section titled “Усередині B+-дерева”У B+-дереві пари «ключ → ctid» лежать лише в листових сторінках (leaf), а внутрішні сторінки тримають роздільні ключі й вказівники на дочірні. Листові сторінки зв’язані в ланцюжок за порядком ключів. Пошук за рівністю спускається від кореня до одного листка. Діапазон спускається до нижньої межі й далі йде ланцюжком, не повертаючись до кореня.
Первинний ключ orders на medium — дерево з трьох рівнів, що показує pageinspect (у контейнері потрібен користувач postgres):
SELECT root, level FROM bt_metap('orders_pkey');SELECT blkno, type, live_items, btpo_level FROM bt_page_stats('orders_pkey', 412); root | level------+------- 412 | 2
blkno | type | live_items | btpo_level-------+------+------------+------------ 412 | r | 2 | 2Рівні рахуються від листків, тож level = 2 означає три сторінки на шляху: корінь із двома записами, дві проміжні сторінки (286 і 318 записів) і 603 листки. Листок тримає до 366 ключів із адресами рядків (ctid, модуль 7). Пошук одного замовлення читає три сторінки дерева й одну сторінку таблиці.
Коли листок повний, база виділяє нову сторінку, переносить туди частину ключів, додає в батьківську сторінку роздільний ключ і вмикає листок у ланцюжок. Це розбиття сторінки (page split). Якщо повна батьківська сторінка, розбиття йде вгору, а висота дерева зростає лише тоді, коли ділиться корінь.
Куди вставляється ключ, визначає, наскільки щільно заповнені сторінки. Три таблиці з мільйоном рядків і первинним ключем кожна:
| Ключ | Розмір індексу | Заповнення листків |
|---|---|---|
bigint за зростанням |
21 МіБ | 90 % |
uuid версії 4 (випадковий) |
39 МіБ | 70 % |
uuid версії 7 (за часом) |
30 МіБ | 90 % |
Послідовні ключі завжди б’ють у правий край, і старі листки лишаються заповненими на 90 % (типовий fillfactor B-дерева). Випадковий ключ потрапляє в довільний листок, і кожне розбиття лишає там по половині вільного місця. Індекс uuid v4 на третину більший за v7 із тими самими даними, а кожна вставка торкається випадкової сторінки (вибір ідентифікатора: модуль 5).
Кластерний індекс: InnoDB і PostgreSQL
Section titled “Кластерний індекс: InnoDB і PostgreSQL”Про те, як InnoDB і PostgreSQL зберігають таблицю, докладно в модулі 7; тут лише те, що це змінює для індексів.
Таблиця лежить у heap без впорядкування, а всі індекси, первинний ключ теж, є окремими B+-деревами й указують на рядок через ctid. UPDATE без HOT додає запис у кожен індекс.
InnoDB зберігає таблицю як B+-дерево за первинним ключем (кластерний індекс): листки й є рядками. Вторинний індекс тримає значення первинного ключа замість адреси, тож пошук за ним — два спуски: вторинним індексом, потім кластерним. InnoDB сам створює індекси для зовнішніх ключів (SHOW INDEX FROM orders показує customer_id і pickup_point_id). На medium PRIMARY (дані таблиці) займає 16.9 МіБ, а вторинний індекс за customer_id 7.7 МіБ проти 2.2 МіБ у PostgreSQL.
EXPLAIN FORMAT=TREE SELECT order_id FROM orders WHERE customer_id = 27672;-- -> Covering index lookup on orders using customer_id (customer_id=27672)Запит лише про order_id покривається індексом: первинний ключ лежить у кожному вторинному.
У InnoDB зміна колонки, якої немає в індексі, цього індексу не чіпає, а первинний ключ за зростанням дає послідовну вставку в саму таблицю (з випадковим ключем розкидається вже таблиця). У PostgreSQL адреса рядка змінюється за кожного оновлення без HOT. Який підхід кращий, залежить від навантаження, про що й розбір нижче.
Як це насправді
Section titled “Як це насправді”Запит, що здається повільним, перевіряють за EXPLAIN (ANALYZE, BUFFERS): рядок Buffers на вершині плану, а у вузлі індексу Index Searches і Heap Fetches. Розмір індексів показує \di+ у psql, використання показує pg_stat_user_indexes (вище), а ціну на запис видно, якщо вимірити той самий INSERT чи UPDATE до і після та порівняти WAL через pg_current_wal_lsn().
На small планувальник багато індексів не вибирає, як сказано на сторінці пісочниці: таблиця, що вміщується в кількадесят сторінок, читається скануванням швидше, і різницю в буферах годі побачити. Справжню різницю дає medium.
Розбір: Uber, 2016
Section titled “Розбір: Uber, 2016”26 липня 2016 року інженерний блог Uber опублікував допис Евана Клітцке про перехід з PostgreSQL на MySQL (InnoDB). Головний аргумент: write amplification, тобто те, що невелика зміна даних тягне за собою багато записів. За описом допису, оновлення одного поля в PostgreSQL пише нову версію рядка в таблицю, а потім запис у кожен індекс, навіть у ті, що цього поля не стосуються. InnoDB лишає вторинним індексам значення первинного ключа, і зміна поля чіпає лише індекси, які його містять. Серед інших причин допис називає фізичну реплікацію, конфлікти читань на репліці із застосуванням журналу й складність оновлення між мажорними версіями.
Спільнота PostgreSQL відповіла по суті. Брюс Момджян написав у розсилку pgsql-hackers 28 липня, що допис вказує на справжні слабкі місця, що відповідати треба спокійно й без оборони, а PostgreSQL проєктували під інші навантаження. 2 серпня Роберт Гаас, розробник PostgreSQL, назвав у блозі write amplification найскладнішою з порушених проблем. Оновлення з HOT в індекси не пишуть, але будь-яке оновлення індексованої колонки HOT бути не може, і на таблицях із багатьма індексами та частими оновленнями це справді боляче. Кластерні індекси MySQL він визнав перевагою для такого навантаження, хоч і за рахунок місця, справжньою потребою Uber назвав логічну реплікацію, а розвитком запропонував зробити шар зберігання PostgreSQL замінним.
Наші виміри підтверджують обидві сторони. У 19 096 із 19 122 оновлень таблиця з двома індексами й fillfactor = 90 не писала в індекси взагалі, а щойно на status з’явився індекс, HOT зник цілком, і WAL подвоївся (усе на medium). Тож критика слушна там, де оновлювана колонка проіндексована або на сторінках немає місця, а де цього нема, HOT її знімає. Для «Крамниці» висновок такий: індекс на orders.status чи orders.updated_at коштує не лише місця й вставки, а й HOT-оновлень усієї таблиці.
Типові помилки розуміння
Section titled “Типові помилки розуміння”«Індекс на кожну колонку з WHERE, і буде швидко». База вибирає один індекс, решту перевіряє в таблиці: окремий індекс за customer_id дав 172 буфери проти 27 у складеного.
«Порядок колонок у складеному індексі не важливий». На тих самих 120 рядках 588 буферів проти 125.
«Якщо індекс є, база ним скористається». Вираз у запиті має збігатися з виразом в індексі: lower(email) не використає індекс за email, а ->> не використає GIN. Умову, що відбирає 86 % рядків (status = 'delivered'), планувальник виконає скануванням.
«Hash швидший за B-дерево на рівності». На 610 тисячах подій він заощадив одну сторінку на пошуку й забрав у півтора раза більше місця.
Перевір себе
Лабораторна
Section titled “Лабораторна”L4. Прискорити повільні запити: шість повільних запитів «Крамниці» на розмірі medium. П’ять із них прискорюють індексами (складеним, за виразом, GIN, BRIN), один переписують, а перевіряється падіння кількості прочитаних буферів, розмір доданих індексів і ціна на запис.
Джерела
Section titled “Джерела”- PostgreSQL 18, документація: розділ 11 «Indexes», B-tree, BRIN, Heap-Only Tuples, pageinspect.
- PostgreSQL 18 Release Notes: skip scan,
Index SearchesуEXPLAIN. - MySQL 8.4 Reference Manual, Clustered and Secondary Indexes.
- Evan Klitzke, Why Uber Engineering Switched from Postgres to MySQL, Uber Engineering, 26 липня 2016.
- Bruce Momjian, лист у
pgsql-hackers, 28 липня 2016, Re: Uber moving towards MySQL. - Robert Haas, Uber’s move away from PostgreSQL, 2 серпня 2016.
- M. Kleppmann, Designing Data-Intensive Applications, розділ 3 «Storage and Retrieval» (B-дерева й LSM-дерева).
- M. Winand, SQL Performance Explained: порядок колонок у складених індексах.