Це цікава можливість, на яку я колись спіткнувся, помилково припустивши, що моя СУБД на таке здатна. Розглянемо наступний запит:
SELECT *
FROM actor
WHERE actor_id IN (2,3,4)
AND actor_id IN (1,2,3);
Очевидно, що два предикати перетинаються і їх можна злити докупи. Очікується, що база даних перетворює наведений вище запит на наступне:
SELECT *
FROM actor
WHERE actor_id IN (2,3);
Виглядає цілком очевидним, правда? Це складніший випадок транзитивного замикання. Ще один випадок — злиття двох діапазонів. Під час виконання запиту:
SELECT *
FROM film
WHERE film_id BETWEEN 1 AND 100
AND film_id BETWEEN 99 AND 200
ми сподіваємося, що база даних перепише запит таким чином:
SELECT *
FROM film
WHERE film_id BETWEEN 99 AND 100
Кардинальність другого варіанту дорівнюватиме 2 рядкам, але в першому база даних може не зрозуміти, що діапазони можна об'єднати, і вибере повний перегляд таблиці, хоча мала б скористатися індексом. Які ж бази даних здатні ці оптимізації?
DB2
Злиття предикатів IN Так
ExplainPlan--------------------------------------------------
ID |Operation|Rows|Cost1| RETURN ||112| FETCH ACTOR |2 of 2(100.00%)|113| IXSCAN PK_ACTOR |2 of 200(1.00%)|0PredicateInformation3- SARG Q3.ACTOR_ID IN (2,3)
Злиття діапазонних предикатів Так (але нехай план не вводить вас в оману!)
ExplainPlan--------------------------------------------------
ID |Operation|Rows|Cost1| RETURN ||132| FETCH FILM |2 of 2(100.00%)|133| IXSCAN PK_FILM |2 of 1000(.20%)|6PredicateInformation3- START (99<= Q1.FILM_ID)
STOP (Q1.FILM_ID <=100)
SARG (Q1.FILM_ID <=200)
SARG (1<= Q1.FILM_ID)
Як ви можете бачити, предикат оптимізували не повністю. Фільтр (SARG), що перевіряє на потрапляння між нижньою та верхньою межами об'єднаного діапазону, на місці, але важливіші операції START та STOP, що вказують на швидкий доступ за індексом. Крім того, кардинальність теж така, якою і має бути. Якщо хочете переконатися, виконайте запит з наступним неможливим предикатом
SELECT *
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199AND200;
і ви отримаєте правильний план:
ExplainPlan-----------------------------------
ID |Operation|Rows|Cost1| RETURN ||02| TBSCAN GENROW |0 of 0|0PredicateInformation2- RESID (1=0)
MySQL
Злиття предикатів IN Знову ж таки, на жаль, MySQL погано відображає інформацію про предикат. Плани для обох запитів збігаються:
ID TABLE TYPE KEY ROWS FILTERED EXTRA
------------------------------------------------------1 actor range PRIMARY 2100.00Using where
Двічі одна кардинальність, двічі "Using where" без будь-якого натяку на те, що насправді відбувається всередині "where" . Але з кардинальності, ми можемо дійти невтішного висновку, що перетворення було виконано правильно. Можна поглянути на це з іншого боку, навіщо виконаємо запит:
SELECT * FROM actor
WHERE actor_id IN (3,4,5)
AND actor_id IN (1,2,3);
Який має бути перетворений на таке:
SELECT * FROM actor
WHERE actor_id =3;
І справді, це і відбувається:
ID TABLE TYPE KEY ROWS FILTERED EXTRA
------------------------------------------------------1 actor const PRIMARY 1100.00
TYPE=range змінився на TYPE=const. Отже, можемо зробити висновок, що так, MySQL виконує цю оптимізацію. Злиття діапазонних предикатів Знову ж таки, план запиту нічого не дає:
ID TABLE TYPE KEY ROWS FILTERED EXTRA
------------------------------------------------------1 film range PRIMARY 2100.00Using where
Але можна підтвердити виконання оптимізації за допомогою наступного "неможливого" предикату:
SELECT *
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199 AND 200
у разі якого план змінюється на такий:
ID TABLE EXTRA
-----------------------------------------1 no matching row in const table
Отже, знову добрі новини щодо MySQL.
Oracle
Злиття предикатів IN Так
----------------------------------------------------------|Id|Operation|Name|E-Rows|----------------------------------------------------------|0| SELECT STATEMENT ||||1| INLIST ITERATOR ||||2| TABLE ACCESS BY INDEX ROWID| ACTOR |2||*3| INDEX UNIQUE SCAN | PK_ACTOR |2|----------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------3-access(("ACTOR_ID"=2 OR "ACTOR_ID"=3))
Застосований предикат включає тільки значення 2 і 3 так що перетворення спрацювало правильно. Злиття діапазонних предикатів Знову ж таки — так:
----------------------------------------------------------------|Id|Operation|Name|E-Rows|----------------------------------------------------------------|0| SELECT STATEMENT ||||1| TABLE ACCESS BY INDEX ROWID BATCHED| FILM |2||*2| INDEX RANGE SCAN | PK_FILM |2|----------------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------2-access("FILM_ID">=99 AND "FILM_ID"<=100)
PostgreSQL
Злиття предикатів IN На жаль, ні, оптимізації не відбувається!
QUERY PLAN
-----------------------------------------------------------------------------------------------SeqScan on actor (cost=0.00..5.50 rows=1 width=25)Filter:((actor_id = ANY ('{2,3,4}'::integer[])) AND (actor_id = ANY ('{1,2,3}'::integer[])))
Обидва предикати, як і раніше, присутні в плані виконання, та й оцінка кардинальності помилкова, має бути 2 , а не 1 . Якщо перетворити запит вручну, ми отримали наступний план запиту:
QUERY PLAN
-----------------------------------------------------SeqScan on actor (cost=0.00..4.50 rows=2 width=25)Filter:(actor_id = ANY ('{2,3}'::integer[]))
Зокрема, ми бачимо неправильний план у разі, коли два предикати не перетинаються та формується "неможливий" предикат:
SELECT *
FROM actor
WHERE actor_id IN (2,3,4)
AND actor_id IN (7,8,9)
Опять неправильный план:
QUERY PLAN
-----------------------------------------------------------------------------------------------SeqScan on actor (cost=0.00..5.50 rows=1 width=25)Filter:((actor_id = ANY ('{2,3,4}'::integer[])) AND (actor_id = ANY ('{7,8,9}'::integer[])))
Облом! Злиття діапазонних предикатів Виглядає не краще:
QUERY PLAN
--------------------------------------------------------------------------------------------IndexScan using film_pkey on film (cost=0.28..8.30 rows=1 width=386)IndexCond:((film_id >=1) AND (film_id <=100) AND (film_id >=99) AND (film_id <=200))
Важко сказати, вийшло чи ні. Зрештою, ми отримали правильний план з розумною кардинальністю, тому все може працювати, як і на DB2. Але що станеться, знову ж таки, якщо створити "неможливий" предикат?
SELECT *
FROM film
WHERE film_id BETWEEN 1 AND 2
AND film_id BETWEEN 199AND200;
План став гіршим:
QUERY PLAN
-------------------------------------------------------------------------------------------IndexScan using film_pkey on film (cost=0.28..8.42 rows=5 width=386)IndexCond:((film_id >=1) AND (film_id >=2) AND (film_id >=199) AND (film_id >=200))
Кардинальність підвищилася замість того, щоб знизитися. І, зрештою, такий запит взагалі не повинен виконуватись. Жирний мінус PostgreSQL
SQL Server
Злиття предикатів IN Так, все працює:
|--NestedLoops(InnerJoin)|--IndexSeek(SEEK:([actor_id]=(2) OR [actor_id]=(3)))|--RID Lookup(OBJECT:([actor]))
Злиття діапазонних предикатів Знову ж таки схоже на випадок DB2:
|--NestedLoops(InnerJoin)|--IndexSeek(SEEK:([film_id]>=(1) AND [film_id]<=(100)), WHERE:([film_id]>=(99) AND [film_id]<=(200)))|--RID Lookup(OBJECT:([film]))
На жаль, зверніть увагу на різницю між SEEK і WHERE . Хотілося б бачити діапазон [99, 100] у SEEK , як у DB2, оскільки SEEK виконується швидко завдяки доступу за індексом за час O(log N) , у той час як час доступу WHERE зростає лінійно, порядку O(N) . Облом! Мені здається, що це програмна помилка, адже неможливий предикат призводить до більш обґрунтованого:
|--ConstantScan
Резюме
Не забувайте, що є безліч предикатів, які правильно зливаються в одних базах даних, а в інших – ні. Якщо сумніваєтеся – обов'язково перевірте план виконання!
База даних
Злиття IN
Злиття діапазонів
DB2 LUW 10.5
Так
Так
MySQL 8.0.2
Так
Так
Oracle 12.2.0.1
Так
Так
PostgreSQL 9.6
Ні
Ні
SQL Server 2014
Так
Ні
7. Доводимо порожні множини
Це особливо крута нагода. Ми вже бачабо вище неможливі предикати та непотрібні звернення до таблиць . Що якщо виконати це знову, але тепер за допомогою JOIN ? Чи спрацює тут усунення JOIN ? Спробуємо виконати наступні запити: Предикат IS NULL на стовпці з обмеженням NOT NULL Предикат у пропозиції WHERE не може дорівнювати TRUE , оскільки на стовпці FILM_ID встановлено обмеження NOT NULL .
SELECT first_name, last_name
FROM actor a
JOIN (
SELECT *
FROM film_actor
WHERE film_id IS NULL
) fa ON a.actor_id = fa.actor_id;
Похідна таблиця FA не поверне жодного стовпця, адже через обмеження NOT NULL на стовпці FA.FILM_ID вона порожня. А оскільки INNER JOIN з порожньою таблицею теж жодних рядків не повертає, звертатися до таблиці ACTOR необхідності немає, так що вищенаведений запит має бути переписаний приблизно так:
SELECT NULL AS first_name, NULL AS last_name
WHERE1=0;
Перетин стовпців, що допускають невизначене значення, зі стовпцями з обмеженням NOT NULL У принципі, це еквівалентно попередньому прикладу, тільки з трохи заплутаним синтаксисом:
SELECT *
FROM actor a
JOIN (SELECT actor_id, film_id
FROM film_actor
INTERSECT
SELECT NULL, NULL
FROM dual
) fa ON a.actor_id = fa.actor_id;
В силу обмежень NOT NULL на обох стовпцях FA.ACTOR_ID і FA.FILM_ID їх перетин з кортежем (NULL, NULL) жодних результатів не поверне, так що похідна таблиця доказово порожня, і, отже, внутрішнє з'єднання можна усунути. І ще раз, з підзапитом EXISTS Нарешті, повторимо наведений вище запит, але цього разу з напівз'єднанням замість внутрішнього з'єднання . Спочатку з неможливим предикатом:
SELECT *
FROM actor a
WHERE a.actor_id IN (
SELECT actor_id
FROM film_actor
WHERE actor_id IS NULL
);
... а потім знову з перетином.
SELECT *
FROM actor a
WHERE a.actor_id IN (
SELECT actor_id
FROM film_actor
INTERSECT
SELECT NULL
FROM sysibm.dual
)
Уперед. Подивимося, які бази даних можуть виконувати ці оптимізації.
DB2
З'єднання доведено порожньої множини (предикат IS NULL ):
З'єднання доведено порожньої множини (INTERSECT) :
ExplainPlan-----------------------------------
ID |Operation|Rows|Cost1| RETURN ||02| TBSCAN GENROW |0 of 0|0PredicateInformation2- RESID (1=0)
Напівз'єднання доказно порожньої множини (предикат IS NULL ):
ExplainPlan-----------------------------------
ID |Operation|Rows|Cost1| RETURN ||02| TBSCAN GENROW |0 of 0|0PredicateInformation2- RESID (1=0)
Напівз'єднання доведено порожньої множини (INTERSECT) :
ExplainPlan-----------------------------------
ID |Operation|Rows|Cost1| RETURN ||02| TBSCAN GENROW |0 of 0|0PredicateInformation2- RESID (1=0)
Вау круто! Схоже, переможець забігу!
MySQL
З'єднання доведено порожньої множини (предикат IS NULL ):
ID TABLE EXTRA
----------------------------1Impossible WHERE
Круто, я не очікував! З'єднання доказно порожньої множини (INTERSECT) : На жаль, MySQL не підтримує INTERSECT . Напівз'єднання доказно порожньої множини (предикат IS NULL ):
ID TABLE EXTRA
----------------------------1Impossible WHERE
Напівз'єднання доказно порожньої множини (INTERSECT) : На жаль, MySQL не підтримує INTERSECT . Але все одно MySQL демонструє відмінний результат!
Oracle
З'єднання доведено порожньої множини (предикат IS NULL ):
---------------------------------------------------------------------------|Id|Operation|Name|Starts|E-Rows|A-Rows|---------------------------------------------------------------------------|0| SELECT STATEMENT ||1||0||*1| FILTER ||1||0||*2| HASH JOIN ||0|5462|0||3| TABLE ACCESS FULL | ACTOR |0|200|0||4| INDEX FAST FULL SCAN| PK_FILM_ACTOR |0|5462|0|---------------------------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------1-filter(NULL IS NOT NULL)2-access("A"."ACTOR_ID"="FILM_ACTOR"."ACTOR_ID")
Знову ж таки, дуже дивний план виконання в Oracle, але фільтр NULL IS NOT NULL на місці, і він знаходиться перед іншими операціями, які, таким чином, не виконуються. З'єднання доведено порожньої множини (INTERSECT) :
---------------------------------------------------------------------------------|Id|Operation|Name|Starts|E-Rows|A-Rows|---------------------------------------------------------------------------------|0| SELECT STATEMENT ||1||0||1| NESTED LOOPS ||1|1|0||2| NESTED LOOPS ||1|1|0||3| VIEW ||1|1|0||4| INTERSECTION ||1||0||5| SORT UNIQUE ||1|5462|5463||6| INDEX FAST FULL SCAN | PK_FILM_ACTOR |1|5462|5463||7| FAST DUAL ||1|1|1||*8| INDEX UNIQUE SCAN | PK_ACTOR |0|1|0||9| TABLE ACCESS BY INDEX ROWID| ACTOR |0|1|0|---------------------------------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------8-access("A"."ACTOR_ID"="FA"."ACTOR_ID")
Кумедно. Як бачимо, у цьому плані виконання відбувається перегляд всього первинного ключа таблиці FILM_ACTOR . Це може позбавити від звернення до таблиці ACTOR і індексу первинного ключа, оскільки спочатку обробляється похідна таблиця (у якій немає жодного рядка), але операцій з Id = 5 і 6 все ж таки тут бути не повинно. Облом! Напівз'єднання доказно порожньої множини (предикат IS NULL ): А це знову виконується правильно:
-------------------------------------------------------------------------------------|Id|Operation|Name|Starts|E-Rows|A-Rows|-------------------------------------------------------------------------------------|0| SELECT STATEMENT ||1||0||*1| FILTER ||1||0||*2| HASH JOIN SEMI ||0|200|0||3| TABLE ACCESS FULL | ACTOR |0|200|0||4| INDEX FAST FULL SCAN| IDX_FK_FILM_ACTOR_ACTOR |0|5462|0|-------------------------------------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------1-filter(NULL IS NOT NULL)2-access("A"."ACTOR_ID"="ACTOR_ID")
... з тим же дивним планом виконання, що містить піддерево, що не виконується. Напівз'єднання доведено порожньої множини (INTERSECT) : Знову ж таки, ніякої оптимізації:
-------------------------------------------------------------------------------------------|Id|Operation|Name|Starts|E-Rows|A-Rows|-------------------------------------------------------------------------------------------|0| SELECT STATEMENT ||1||0||1| NESTED LOOPS ||1|1|0||2| NESTED LOOPS ||1|1|0||3| VIEW | VW_NSO_1 |1|1|0||4| INTERSECTION ||1||0||5| SORT UNIQUE ||1|5462|200||6| INDEX FAST FULL SCAN | IDX_FK_FILM_ACTOR_ACTOR |1|5462|5463||7| FAST DUAL ||1|1|1||*8| INDEX UNIQUE SCAN | PK_ACTOR |0|1|0||9| TABLE ACCESS BY INDEX ROWID| ACTOR |0|1|0|-------------------------------------------------------------------------------------------PredicateInformation(identified by operation id):---------------------------------------------------8-access("A"."ACTOR_ID"="ACTOR_ID")
Не надто добрі результати!
PostgreSQL
На превелике розчарування, PostgreSQL у цьому експерименті показує себе не з кращого боку! З'єднання доказно порожньої множини (предикат IS NULL ): Не-а:
QUERY PLAN
--------------------------------------------------------------------------------------------HashJoin(cost=8.31..13.07 rows=1 width=13)HashCond:(a.actor_id = film_actor.actor_id)->SeqScan on actor a (cost=0.00..4.00 rows=200 width=17)->Hash(cost=8.30..8.30 rows=1 width=2)->IndexScan using idx_fk_film_id on film_actor (cost=0.28..8.30 rows=1 width=2)IndexCond:(film_id IS NULL)
З'єднання доведено порожньої множини (INTERSECT) : Ще гірше:
QUERY PLAN
---------------------------------------------------------------------------------------------------HashJoin(cost=166.60..171.36 rows=1 width=29)HashCond:(a.actor_id = fa.actor_id)->SeqScan on actor a (cost=0.00..4.00 rows=200 width=25)->Hash(cost=166.59..166.59 rows=1 width=4)->SubqueryScan on fa (cost=0.00..166.59 rows=1 width=4)->HashSetOpIntersect(cost=0.00..166.58 rows=1 width=8)->Append(cost=0.00..139.26 rows=5463 width=8)->SubqueryScan on "*SELECT* 2"(cost=0.00..0.02 rows=1 width=8)->Result(cost=0.00..0.01 rows=1 width=4)->SubqueryScan on "*SELECT* 1"(cost=0.00..139.24 rows=5462 width=8)->SeqScan on film_actor (cost=0.00..84.62 rows=5462 width=4)
Напівз'єднання доказно порожньої множини (предикат IS NULL ) : Так само, як і у випадку з внутрішнім з'єднанням:
QUERY PLAN
-------------------------------------------------------------------------------------------------HashSemiJoin(cost=6.06..10.60 rows=1 width=25)HashCond:(a.actor_id = film_actor.actor_id)->SeqScan on actor a (cost=0.00..4.00 rows=200 width=25)->Hash(cost=6.05..6.05 rows=1 width=2)->IndexOnlyScan using film_actor_pkey on film_actor (cost=0.28..6.05 rows=1 width=2)IndexCond:(actor_id IS NULL)
Напівз'єднання доказно порожньої множини (INTERSECT) : Як і очікувалося:
QUERY PLAN
--------------------------------------------------------------------------------------------------HashSemiJoin(cost=152.94..157.48 rows=1 width=25)HashCond:(a.actor_id ="ANY_subquery".actor_id)->SeqScan on actor a (cost=0.00..4.00 rows=200 width=25)->Hash(cost=152.93..152.93 rows=1 width=2)->SubqueryScan on "ANY_subquery"(cost=0.00..152.93 rows=1 width=2)->HashSetOpIntersect(cost=0.00..152.92 rows=1 width=6)->Append(cost=0.00..139.26 rows=5463 width=6)->SubqueryScan on "*SELECT* 2"(cost=0.00..0.02 rows=1 width=6)->Result(cost=0.00..0.01 rows=1 width=2)->SubqueryScan on "*SELECT* 1"(cost=0.00..139.24 rows=5462 width=6)->SeqScan on film_actor (cost=0.00..84.62 rows=5462 width=2)
SQL Server
SQL Server тут у всій красі, як і DB2! З'єднання доведено порожньої множини (предикат IS NULL ) :
|--ConstantScan
З'єднання доведено порожньої множини (INTERSECT) :
|--ConstantScan
Напівз'єднання доказно порожньої множини (предикат IS NULL ) :
|--ConstantScan
Напівз'єднання доведено порожньої множини (INTERSECT) :
|--ConstantScan
Резюме
База даних
JOIN/NULL
JOIN/INTERSECT
SEMI JOIN/NULL
SEMI JOIN/INTERSECT
DB2 LUW 10.5
Так
Так
Так
Так
MySQL 8.0.2
Так
Не підтримується
Так
Не підтримується
Oracle 12.2.0.1
Так
Ні
Так
Ні
PostgreSQL 9.6
Ні
Ні
Ні
Ні
SQL Server 2014
Так
Так
Так
Так
Зауважимо, що це можна виконати і багатьма іншими способами. Не соромтеся коментувати і пропонувати власні варіанти створення "доказово порожніх множин", щоб перевірити оптимізацію їх цими базами даних.
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ