Кльові оптимізації SQL, що не залежать від вартісної моделі. Частина 1

Пропонуємо вам адаптацію статті Лукаса Едера, розраховану на тих, хто має загальне уявлення про бази даних і SQL, а також невеликий практичний досвід роботи з СУБД. Вартісна оптимізація – практично стандартний метод оптимізації SQL-запитів у сучасних базах даних. Саме тому настільки складно написати вручну складний алгоритм на 3GL (мовах програмування третього покоління), продуктивність якого перевищувала б план виконання, що динамічно розраховується, згенерований сучасним оптимізатором. Сьогодні ми не обговорюватимемо вартісну оптимізацію, тобто оптимізацію на основі вартісної моделі бази даних. Ми розглянемо набагато простіші оптимізації. Ті, які можна реалізувати на основі самих лише метаданих (тобто обмежень) і самого запиту. Зазвичай їх реалізація для бази даних – не біном Ньютона, оскільки, у разі, будь-яка оптимізація призведе до кращого плану виконання, незалежно від наявності індексів, обсягів даних, і асиметрії розподілу даних. "Не біном Ньютона" не в сенсі легкості реалізації оптимізації, а в тому, чи це слід робити. Ці оптимізації усувають [для бази даних] непотрібну, додаткову роботу (на відміну від непотрібної, обов'язкової роботи, про яку я вже писав ).

Навіщо ці оптимізації застосовуються?

Більшість із них застосовується для:

• виправлення помилок у запитах;
• забезпечення повторного використання уявлень без фактичного виконання логіки подання базою даних

У першому випадку, можна було б заявити: "Ну і що, просто візьми, і виправи цей безглуздий SQL-запит". Але нехай першим кине в мене камінь той, кому не доводилося помилятися. Другий випадок особливо цікавий: це дає нам можливість створення складних бібліотек уявлень та табличних функцій, що допускають багаторазове використання у кількох шарах.

Використовувані бази даних

У цій статті ми будемо порівнювати 10 SQL-оптимізацій у п'яти найбільш широко використовуваних СУБД ( згідно з рейтингом баз даних ):

• Oracle 12.2;
• MySQL 8.0.2;
• SQL Server 2014;
• PostgreSQL 9.6;
• DB2 LUW 10.5.

Інший рейтинг майже вторить йому. Як завжди, у цій статті я виконуватиму запити до бази даних Sakila. Ось список цих десяти різновидів оптимізації:

1. транзитивне замикання;
2. неможливі предикати та непотрібні звернення до таблиць;
3. усунення JOIN;
4. усунення "безглуздих" предикатів;
5. проекції у підзапитах EXISTS;
6. злиття предикатів;
7. доведено порожні множини;
8. обмеження CHECK;
9. непотрібні рефлексивні сполуки;
10. Pushdown предикатів

Сьогодні ми обговоримо пп. 1-3, у другій частині - 4 і 5, а в частині 3 - 6-10.

1. Транзитивне замикання

Почнемо з чогось простіше: транзитивного замикання . Це очевидне поняття, застосовне до багатьох математичних операцій, наприклад, оператору рівності. Його можна сформулювати у разі таким чином: якщо A = B і B = C, то A = C.

Нескладно, правда? Але це тягне за собою деякі цікаві наслідки для оптимізаторів SQL. Розглянемо приклад. Витягнемо всі фільми з ACTOR_ID = 1:

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE a.actor_id = 1;

Результат наступний:

FIRST_NAME      LAST_NAME  FILM_ID
PENELOPE        GUINESS    1
PENELOPE        GUINESS    23
PENELOPE        GUINESS    25
PENELOPE        GUINESS    106
PENELOPE        GUINESS    140
PENELOPE        GUINESS    166
...

Погляньмо тепер на план виконання цього запиту у разі СУБД Oracle:

--------------------------------------------------------------
| Id  | Operation                    | Name          | Rows  |
--------------------------------------------------------------
|   0 | SELECT STATEMENT             |               |       |
|   1 |  NESTED LOOPS                |               |    19 |
|   2 |   TABLE ACCESS BY INDEX ROWID| ACTOR         |     1 |
|*  3 |    INDEX UNIQUE SCAN         | PK_ACTOR      |     1 |
|*  4 |   INDEX RANGE SCAN           | PK_FILM_ACTOR |    19 |
--------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   3 - access("A"."ACTOR_ID"=1)
   4 - access("FA"."ACTOR_ID"=1)

Особливо тут цікавим є розділ предикатів. Предикат ACTOR_ID = 1, внаслідок транзитивного замикання застосовується як до таблиці ACTOR, і до таблиці FILM_ACTOR. Якщо:

• A.ACTOR_ID = 1 (из предиката WHERE) и…
• A.ACTOR_ID = FA.ACTOR_ID (из предиката ON)
  То:
• FA.ACTOR_ID = 1

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

SELECT first_name, last_name, film_id
FROM actor a
JOIN film_actor fa ON a.actor_id = fa.actor_id
WHERE first_name = 'PENELOPE'
AND last_name = 'GUINESS'

Його план:

----------------------------------------------------------------------------
| Id  | Operation                            | Name                | Rows  |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT                     |                     |       |
|   1 |  NESTED LOOPS                        |                     |     2 |
|*  2 |   TABLE ACCESS BY INDEX ROWID BATCHED| ACTOR               |     1 |
|*  3 |    INDEX RANGE SCAN                  | IDX_ACTOR_LAST_NAME |     3 |
|*  4 |   INDEX RANGE SCAN                   | PK_FILM_ACTOR       |    27 |
----------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   2 - filter("A"."FIRST_NAME"='PENELOPE')
   3 - access("A"."LAST_NAME"='GUINESS')
   4 - access("A"."ACTOR_ID"="FA"."ACTOR_ID")

Як можна бачити, оцінка числа рядків таблиці FILM_ACTOR завищена, а оцінка для вкладених циклів (NESTED LOOP) занижена. Ось кілька цікавих значень:

SELECT count(*) FROM film_actor WHERE actor_id = 1;
SELECT avg(c) FROM (
  SELECT count(*) c FROM film_actor GROUP BY actor_id
);

Результат:

19
27.315

Звідси й виходять оцінки. Якщо база даних знає, що йдеться про ACTOR_ID = 1, може зібрати статистику за кількістю фільмів для цього конкретного актора . Якщо не знає (оскільки стандартний механізм збору статистики не співвідносить FIRST_NAME/LAST_NAME з ACTOR_ID), ми отримаємо середнє число фільмів всім акторів . Проста, несуттєва помилка в даному конкретному випадку, але у складному запиті вона може поширюватися далі, накопичуватися та приводити далі у запиті (вище у плані) до неправильного вибору JOIN. Тому завжди, коли тільки можете, проектуйте свої з'єднання і прості предикати так, що скористатися перевагами транзитивного замикання. Які ще бази даних підтримують цю можливість?

DB2

Так!

Explain Plan
-----------------------------------------------------------
ID | Operation              |                 Rows | Cost
 1 | RETURN                 |                      |   13
 2 |  NLJOIN                |              27 of 1 |   13
 3 |   FETCH ACTOR          |     1 of 1 (100.00%) |    6
 4 |    IXSCAN PK_ACTOR     |   1 of 200 (   .50%) |    0
 5 |   IXSCAN PK_FILM_ACTOR | 27 of 5462 (   .49%) |    6
Predicate Information
 4 - START (Q2.ACTOR_ID = 1)
      STOP (Q2.ACTOR_ID = 1)
 5 - START (1 = Q1.ACTOR_ID)
      STOP (1 = Q1.ACTOR_ID)

До речі, якщо вам подобаються круті плани виконання на зразок цього, скористайтеся сценарієм Маркуса Вінанда (Markus Winand) .

MySQL

На жаль, плани виконання MySQL погано підходять для такого аналізу. У інформації, що виводиться, відсутній сам предикат:

ID  SELECT TYPE  TABLE  TYPE   REF    ROWS
------------------------------------------
1   SIMPLE       a      const  const  1
1   SIMPLE       fa     ref    const  19

Але те що, що у стовпці REF двічі зазначено const показує, що у обох таблицях йде пошук за константним значенням. У той же час план запиту з FIRST_NAME / LAST_NAME виглядає таким чином:

ID  SELECT TYPE  TABLE  TYPE   REF         ROWS
-----------------------------------------------
1   SIMPLE       a      ref    const       3
1   SIMPLE       fa     ref    a.actor_id  27

І, як ви можете бачити, в REF тепер вказано посилання на стовпець із предикату JOIN. Оцінка кардинальності практично така сама, як у Oracle. Так що так, MySQL також підтримує транзитивне замикання.

PostgreSQL

Так!

QUERY PLAN
------------------------------------------------------------------------------------
Nested Loop  (cost=4.49..40.24 rows=27 width=15)
  ->  Seq Scan on actor a  (cost=0.00..4.50 rows=1 width=17)
        Filter: (actor_id = 1)
  ->  Bitmap Heap Scan on film_actor fa  (cost=4.49..35.47 rows=27 width=4)
        Recheck Cond: (actor_id = 1)
        ->  Bitmap Index Scan on film_actor_pkey  (cost=0.00..4.48 rows=27 width=0)
              Index Cond: (actor_id = 1)

SQL Server

Так!

|--Nested Loops(Inner Join)
     |--Nested Loops(Inner Join)
     |    |--Index Seek (SEEK:([a].[actor_id]=(1)))
     |    |--RID Lookup
     |--Index Seek (SEEK:([fa].[actor_id]=(1)))

Резюме

Усі наші бази даних підтримують транзитивне замикання. Проте зачекайте №6 у наступній частині статті. Існують складні випадки транзитивного замикання, із якими справляються в повному обсязі бази даних.

2. Неможливі предикати та непотрібні звернення до таблиць

Ця зовсім безглузда оптимізація, але чому б і ні? Якщо користувачі пишуть неможливі предикати, то навіщо їх виконувати? Ось кілька прикладів:

-- "Очевидный"
SELECT * FROM actor WHERE 1 = 0
-- "Хитрый"
SELECT * FROM actor WHERE NULL = NULL

Перший запит, очевидно, ніколи не поверне жодних результатів, але те саме твердження справедливе і щодо другого. Адже хоча NULL IS NULL завжди TRUE, результат обчислення NULL = NULL дорівнює NULL, що, згідно з тризначною логікою , еквівалентно FALSE. Це не вимагає особливих пояснень, тому перейдемо відразу до з'ясування, які з баз даних виконують таку оптимізацію.

DB2

Так!

Explain Plan
-----------------------------------
ID | Operation      |   Rows | Cost
 1 | RETURN         |        |    0
 2 |  TBSCAN GENROW | 0 of 0 |    0

Як можна побачити, звернення до таблиці ACTOR повністю виключено з плану. У ньому є тільки операція GENROW, що генерує нуль рядків. Ідеально.

MySQL

Так!

ID  SELECT TYPE  TABLE   EXTRAS
-----------------------------------------
1   SIMPLE         Impossible WHERE

На цей раз, MySQL був настільки люб'язний, що повідомив нам про неможливу пропозицію WHERE. Дякую! Це полегшує аналіз, особливо проти іншими базами даних.

Oracle

Так!

---------------------------------------------------------------
| Id  | Operation          | Name  | Starts | E-Rows | A-Rows |
---------------------------------------------------------------
|   0 | SELECT STATEMENT   |       |      1 |        |      0 |
|*  1 |  FILTER            |       |      1 |        |      0 |
|   2 |   TABLE ACCESS FULL| ACTOR |      0 |    200 |      0 |
---------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
   1 - filter(NULL IS NOT NULL)

Бачимо, що в плані, як і раніше, згадується звернення до таблиці ACTOR, причому очікуване число рядків, як і раніше, 200, але є і операція фільтрації (FILTER) при Id=1, де ніколи не буде TRUE. В силу нелюбові Oracle до стандартного булевого типу даних SQL Oracle відображає в плані NULL IS NOT NULL, замість простого FALSE. Але якщо серйозно, стежте за цим предикатом. Мені траплялося налагоджувати плани виконання з піддеревами в 1000 рядків і вкрай високими значеннями вартості і лише постфактум виявляти, що все це дерево "відсікалося" фільтром NULL IS NOT NULL. Трохи бентежить, скажу я вам.

PostgreSQL

Так!

QUERY PLAN
-------------------------------------------
Result  (cost=0.00..0.00 rows=0 width=228)
  One-Time Filter: false

Вже краще. Жодного докучливого звернення до таблиці ACTOR і маленький акуратний предикат FALSE.

SQL Server?

Так!

|--Constant Scan

SQL Server називає це " константним переглядом", тобто переглядом, при якому нічого не відбувається - аналогічно DB2. Всі наші бази даних можуть виключати неможливі предикати:

3. Усунення JOIN

У попередньому розділі спостерігали непотрібні звернення до таблиць в однотабличних запитах. Але що станеться, якщо JOIN не потребує одного з декількох звернень до таблиць? Я вже писав про усунення JOIN у попередньому пості з мого блогу . SQL-движок здатний визначити, на основі виду запиту, а також наявності первинних та зовнішніх ключів, чи дійсно конкретний JOIN необхідний у даному запиті, чи його усунення не вплине на семантику запиту. У всіх наступних трьох прикладах JOIN не потрібен. Внутрішнє з'єднання типу "...-к-одному" можна усунути за наявності неприпустимого невизначеного значення (NOT NULL) зовнішнього ключа Замість цього:

SELECT first_name, last_name
FROM customer c
JOIN address a ON c.address_id = a.address_id

База даних може виконати таке:

SELECT first_name, last_name
FROM customer c

Внутрішнє з'єднання (INNER JOIN) типу "...-до-одного" можна замінити за наявності невизначеного значення зовнішнього ключа, що допускає. Наведений вище запит працює, якщо на зовнішній ключ накладено обмеження NOT NULL. Якщо ж ні, наприклад, як у цьому запиті:

SELECT title
FROM film f
JOIN language l ON f.original_language_id = l.language_id

то JOIN все одно можна усунути, але доведеться додати предикат NOT NULL, ось так:

SELECT title
FROM film
WHERE original_language_id IS NOT NULL

Зовнішнє з'єднання (OUTER JOIN) типу "...-до одного" можна прибрати за наявності унікального ключа. Замість цього:

SELECT first_name, last_name
FROM customer c
LEFT JOIN address a ON c.address_id = a.address_id

База даних, знову ж таки, може виконати таке:

SELECT first_name, last_name
FROM customer c

... навіть якщо зовнішнього ключа CUSTOMER.ADDRESS_ID немає. Унікальне зовнішнє з'єднання (DISTINCT OUTER JOIN) типу "...-ко-многим" можна прибрати. Замість цього:

SELECT DISTINCT first_name, last_name
FROM actor a
LEFT JOIN film_actor fa ON a.actor_id = fa.actor_id

База даних може виконати таке:

SELECT DISTINCT first_name, last_name
FROM actor a

Всі ці приклади були детально вивчені в попередній статті, так що я не повторюватимуся, а лише підсумую все, що можуть усувати різні бази даних: На жаль, не всі бази даних можуть усувати всі види з'єднань. DB2 та SQL Server тут – безумовні лідери! Далі буде