Дружимо ORDER BY з індексами

Alex Alex 07 лютого 2020
Дружимо ORDER BY з індексами


Привіт, Хабр!


Я потихеньку перекладаю статті Маркуса Винанда з блогу use the index luke.


Першої статті у циклі був маніфест Маркуса про важливість використання безофсетной пагинации на ключах. Ми розглянули лише один приклад, як цей підхід працює на практиці. У цій та наступних статтях я буду обґрунтовувати такий підхід — з графіками і прикладами, як всі люблять.


Почнемо з самого початку. У цій статті буде розбір pipelined order by. Ми розглянемо, що це таке, як досягти і в чому переваги такого підходу. У наступній статті поговоримо про top-N синтаксис і його зв'язок з pipelined order by. І вже потім перейдемо до пагинации, що буде всередині себе використовувати всі раніше описані підходи, і тоді стане зрозуміло, як це все працює всередині і чому це дійсно круто.


Варто зауважити, що оригінальні матеріали досить старі за мірками нашої індустрії: стаття про інструментальну підтримку оновлювалася останній раз в кінці 2017. Тому, якщо у вас є інформація про те, що змінилося за цей час, — пишіть у коментарях. Я обов'язково перевірю і виправлю, в тому числі повідомлю автору блогу.


Усі свої коментарі та примітки я залишаю з позначкою «заст.», щоб розділити слова автора і свої власні. Крім того, я дозволив собі вільність накидати запити і скрипти для PostgreSQL — мені здається, це досить актуальна база даних, щоб включити її в приклади. Скрипт повністю на Гітхабі.


Введення


SQL-запити, що використовують order by, можуть уникати явною сортування результату, якщо вираз потрапляє в існуючий індекс. Це відбувається за умови, що останній надає запитуваний порядок записів. Однак це так само означає, що індекс, який покриває вираз where в запиті, повинен покривати порядок сортування order by.


Прим.: Для прикладу нехай задана таблиця продажів. У ній створено два атрибути: sale_date, тобто дата продажу (тільки дата, без часу), і product_id — айді виду товару, який був проданий; sale_date при цьому покритий індексом.


Розглянемо наступний запит, що вибирає вчорашні замовлення, сортуючи їх спочатку по даті, а потім по айді продукту:


SELECT sale_date, product_id, quantity
FROM sales
WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
ORDER BY sale_date, product_id

Як вже було сказано, sale_date покритий індексом і цей індекс може бути використаний в умові where. Але база все одно повинна явно відсортувати записи, щоб задовольнити order by в запиті.


Плани виконання:


DB2
Explain Plan
------------------------------------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 682
2 | TBSCAN | 394 of 394 (100.00%) | 682
3 | SORT | 394 of 394 (100.00%) | 682
4 | FETCH SALES | 394 of 394 (100.00%) | 682
5 | IXSCAN SALES_DATE | 394 of 1009326 ( .04%) | 19

Predicate Information
5 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))

З-за специфіки DB2 вираз where трохи змінюється: WHERE sale_date = CURRENT_DATE — 1 DAY. Але суть залишається така ж.


Oracle
---------------------------------------------------------------
|Id | Operation | Name | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT| | 320 | 18 |
| 1 | SORT ORDER BY| | 320 | 18 |
| 2 | TABLE ACCESS BY INDEX ROWID| SALES| 320 | 17 |
|*3 | INDEX RANGE SCAN | SALES_DATE| 320 | 3 |
---------------------------------------------------------------

PostgreSQL
Sort (cost=27862.15..28359.74 rows=199034 width=16) (actual time=259.075..370.953 rows=200000 loops=1)
Sort Key: product_id
Sort Method: external merge Disk: 5872kB
-> Index Scan using sales_date on sales (cost=0.42..6942.52 rows=199034 width=16) (actual time=0.030..121.512 rows=200000 loops=1)
Index Cond: (sale_date = '2020-01-05 00:00:00'::timestamp without time zone)
Planning Time: 0.226 ms
Execution Time: 458.083 ms

Оракловый index range scan завжди надає записи в тому порядку, в якому вони вказані в індексі. Щоб використати це на свою користь, нам доведеться трохи змінити індекс:


DROP INDEX sales_date

CREATE INDEX sales_dt_pr ON sales (sale_date, product_id)

SELECT sale_date, product_id, quantity
FROM sales
WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
ORDER BY sale_date, product_id

Плани виконання з новим індексом:


DB2
Explain Plan
-----------------------------------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 688
2 | FETCH SALES | 394 of 394 (100.00%) | 688
3 | IXSCAN SALES_DT_PR | 394 of 1009326 ( .04%) | 24

Predicate Information
3 - START (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))
STOP (Q1.SALE_DATE = (CURRENT DATE - 1 DAYS))

Oracle
---------------------------------------------------------------
|Id | Operation | Name | Rows | Cost |
---------------------------------------------------------------
| 0 | SELECT STATEMENT| | 320 | 300 |
| 1 | TABLE ACCESS BY INDEX ROWID| SALES| 320 | 300 |
|*2 | INDEX RANGE SCAN | SALES_DT_PR| 320 | 4 |
---------------------------------------------------------------

PostgreSQL
Index Scan using sales_dt_pr on sales (cost=0.42..18413.96 rows=199034 width=16) (actual time=0.043..206.096 rows=200000 loops=1)
Index Cond: (sale_date = '2020-01-05 00:00:00'::timestamp without time zone)
Planning Time: 0.259 ms
Execution Time: 295.872 ms

Як можна помітити, операція sort order by зникла з плану, хоча запит ми не змінювали і в ньому досі міститься order by. База вирішила використовувати прохід по індексу і пропустити етап явною сортування.


Неочевидні індекси


Хоча новий план виконання має менше операцій, його вартість значно вище (прим.: в Oracle), тому що фактор кластеризації нового індексу гірше. Тут також треба зауважити, що вартість (cost value) не завжди хороший показник ефективності виконання запиту (прим.: під катом коротко розповідається, чому так).


Автоматична оптимізація фактора кластеризації

Прим.: Фактор кластеризації показує, наскільки точно порядок записів в індексі збігається з їх порядком в таблиці.


База даних Oracle намагається тримати фактор кластеризації на мінімумі з допомогою псевдостолбца ROWID, який визначає порядок записів в індексі. В той момент, коли дві індексовані записи мають однаковий ключ, ROWID вирішує, яким буде кінцевий порядок. Виходить, що індекс, у свою чергу, також впорядковується за порядком записів у таблиці. Отже, він має мінімально можливий фактор кластеризації.


При додаванні додаткового стовпця індекс ми додаємо новий критерій сортування перед ROWID. База даних при цьому вільна вирівнювання елементів індексу згідно з порядком у таблиці, тому фактор кластеризації індексу стає тільки гірше.


Незважаючи на це, все ще можливо, що індекс слабо, але все-таки відповідає порядку в таблиці. Продажу, відносяться до одного дня, ймовірно, все ще кластеризованы разом, як у таблиці, так і в індексі — навіть якщо їх послідовність вже не збігається. БД змушена читати одні і ті ж блоки таблиці кілька разів у різному порядку при використанні індексу sale_dt_pr. Тим не менше на продуктивність це може впливати набагато менше, ніж обчислена вартість в плані виконання, так як часті запити до одним і тим же даними потраплять в кеш і будуть оброблятися набагато швидше.


У нашому випадку достатньо, щоб сканований індекс був відсортований згідно order by. Отже, такий підхід буде працювати в запиті, де ми хочемо сортувати тільки за стовпець product_id:


SELECT sale_date, product_id, quantity
FROM sales
WHERE sale_date = TRUNC(sysdate) - INTERVAL '1' DAY
ORDER BY product_id

На малюнку нижче можемо помітити, що product_id — єдиний доречний критерій сортування сканируемом індексі при такому запиті (прим.: так як дата за один день завжди однакова для всіх записів в цей день). Отже, порядок індексу збігається з порядком у order by в даному діапазоні індексу, тому база може опустити явну сортування.



Порядок сортування у відповідних діапазонах індексу


Прим.: Тут треба трохи пояснити малюнок. На ньому зображено покриття таблиці індексом і те, як цей індекс розбивається на області. Можна помітити, що дата за один день (стовпець з датою, без часу) залишається без змін. Але, так як товари можуть повторюватися (product_id вказує на айді типу товару в таблиці товарів) як всередині однієї дати, так і між різними датами (наприклад, умовний товар-1 був проданий вчора 5 разів і сьогодні 2 рази). З-за такої особливості можемо отримати різні неприємні наслідки при спробі потрапити в індекс.


Наше загравання з індексами іноді може призводити до непередбачених наслідків. Наприклад, коли зміною умови where ми розширюємо область сканування індексу:


SELECT sale_date, product_id, quantity
FROM sales
WHERE sale_date >= TRUNC(sysdate) - INTERVAL '1' DAY
ORDER BY product_id

Даний запит отримує вже не тільки вчорашні запису про продажі, але всі записи, починаючи з вчорашнього дня. Це означає, що запит вже покриває більше однієї дати. При цьому виходить, що записи сортуються не тільки за product_id (прим.: так як в запит потрапляють два дні, а нам цікаво побачити сортування тільки за айді товару, то всі id записів за ці дні об'єднуються і з-за того, що вони відсортовані тільки в одному діапазоні індексу — за конкретний день, то доводиться ще раз явно сортувати). Якщо знову повернемося до картинці вище і розширимо скановану область індексу до самого низу, то побачимо, що у нас повторно з'являються менші значення з product_id. База даних, як наслідок, повинна застосувати явну сортування, щоб задовольнити order by.


Плани виконання:


DB2
Explain Plan
-------------------------------------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 688
2 | TBSCAN | 394 of 394 (100.00%) | 688
3 | SORT | 394 of 394 (100.00%) | 688
4 | FETCH SALES | 394 of 394 (100.00%) | 688
5 | IXSCAN SALES_DT_PR | 394 of 1009326 ( .04%) | 24

Predicate Information
5 - START ((CURRENT DATE - 1 DAYS) <= Q1.SALE_DATE)

Oracle
---------------------------------------------------------------
|Id |Operation | Name | Rows | Cost |
---------------------------------------------------------------
| 0 |SELECT STATEMENT| | 320 | 301 |
| 1 | SORT ORDER BY| | 320 | 301 |
| 2 | TABLE ACCESS BY INDEX ROWID| SALES| 320 | 300 |
|*3 | INDEX RANGE SCAN | SALES_DT_PR| 320 | 4 |
---------------------------------------------------------------

PostgreSQL
Sort (cost=34388.50..34886.08 rows=199034 width=16) (actual time=258.029..367.186 rows=200001 loops=1)
Sort Key: product_id
Sort Method: external merge Disk: 5872kB
-> Bitmap Heap Scan on sales (cost=4610.94..13468.86 rows=199034 width=16) (actual time=19.947..122.290 rows=200001 loops=1)
Recheck Cond: (sale_date >= '2020-01-05 00:00:00'::timestamp without time zone)
Heap Blocks: exact=1275
-> Bitmap Index Scan on sales_dt_pr (cost=0.00..4561.18 rows=199034 width=0) (actual time=19.742..19.742 rows=200001 loops=1)
Index Cond: (sale_date >= '2020-01-05 00:00:00'::timestamp without time zone)
Planning Time: 0.141 ms
Execution Time: 452.337 ms

Що ж тоді робити з усім цим неподобством?


Якщо БД використовує сортування, хоча ви очікуєте конвеєрне виконання (pipeline execution), то це може означати дві речі:


  1. План виконання з явною сортуванням має меншу вартість, тому оптимізатор волів вибрати його.
  2. Порядок записів в сканируемом діапазоні індексу не задовольняє висловом order by.

найпростіший спосіб визначити, що щось пішло не так, — підставити у order by повне покриття індексу. Таким чином ми вирівнюємо весь запит за індексом, щоб виключити другий варіант. В результаті, якщо база продовжує використовувати явну сортування, значить, оптимізатор воліє такий план з-за його меншої вартості. Якщо ж сортування пропала, то це свідчить про неможливість використовувати індекс order by.


У будь-якому випадку хочеться розуміти, можна отримати конвеєр в конкретному випадку і як це зробити. Для цього також підійде виконання запиту з повним попаданням в індекс order by і інспекція плану виконання. Найчастіше вдається виявити помилкове сприйняття індексу і те, що він не відповідає вимозі order by. Тому БД не може використовувати його в конкретному запиті.


Висновок


Якщо оптимізатор віддає явну сортування через її більш низької вартості, то це зазвичай відбувається тому, що оптимізатор оцінює план виконання цілком. Іншими словами, оптимізатор вибирає той план, який віддає останню запис результату швидше. Якщо БД виявляє, що запитуються не всі дані, а, наприклад, тільки перші N записів, то найімовірніше, що конвеєр буде обраний в якості оптимального підходу, якщо він, звичайно ж, можливий. Цей випадок ми розглянемо в наступній статті про top-N записів.


Джерело


Автор: Markus Winand

Source: habr.com

Коментарі (0)

    Ще немає коментарів

Щоб залишити коментар необхідно авторизуватися.