Клёвые оптимизации SQL, не зависящие от стоимостной модели. Часть 1
Клёвые оптимизации SQL, не зависящие от стоимостной модели. Часть 2
![Клёвые оптимизации SQL, не зависящие от стоимостной модели. Часть 3 - 1]()
Заметим, что это можно выполнить и множеством других способов. Не стесняйтесь комментировать и предлагать свои собственные варианты создания "доказуемо пустых множеств", чтобы проверить оптимизацию их этими базами данных.

6. Слияние предикатов
Это — интересная возможность, на которой я когда-то споткнулся, ошибочно предположив, что моя СУБД на такое способна. Рассмотрим следующий запрос:
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 Да
Explain Plan
--------------------------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 11
2 | FETCH ACTOR | 2 of 2 (100.00%) | 11
3 | IXSCAN PK_ACTOR | 2 of 200 ( 1.00%) | 0
Predicate Information
3 - SARG Q3.ACTOR_ID IN (2, 3)
Слияние диапазонных предикатов
Да (но пусть план не вводит вас в заблуждение!)
Explain Plan
--------------------------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 13
2 | FETCH FILM | 2 of 2 (100.00%) | 13
3 | IXSCAN PK_FILM | 2 of 1000 ( .20%) | 6
Predicate Information
3 - 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 199 AND 200;
и вы получите правильный план:
Explain Plan
-----------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 0
2 | TBSCAN GENROW | 0 of 0 | 0
Predicate Information
2 - RESID (1 = 0)
MySQL
Слияние предикатов IN Опять же, к сожалению, MySQL плохо отображает информацию о предикате. Планы для обоих запросов совпадают:
ID TABLE TYPE KEY ROWS FILTERED EXTRA
------------------------------------------------------
1 actor range PRIMARY 2 100.00 Using 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 1 100.00
Обратите внимание на то, что TYPE=range поменялся на TYPE=const.
Итак, можем сделать вывод, что да, MySQL выполняет данную оптимизацию.
Слияние диапазонных предикатов
Опять же, план запроса ничего не дает:
ID TABLE TYPE KEY ROWS FILTERED EXTRA
------------------------------------------------------
1 film range PRIMARY 2 100.00 Using 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 |
----------------------------------------------------------
Predicate Information (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 |
----------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
2 - access("FILM_ID">=99 AND "FILM_ID"<=100)
PostgreSQL
Слияние предикатов IN Увы, нет, оптимизации не происходит!
QUERY PLAN
-----------------------------------------------------------------------------------------------
Seq Scan 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
-----------------------------------------------------
Seq Scan 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
-----------------------------------------------------------------------------------------------
Seq Scan 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
--------------------------------------------------------------------------------------------
Index Scan using film_pkey on film (cost=0.28..8.30 rows=1 width=386)
Index Cond: ((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 199 AND 200;
План стал хуже:
QUERY PLAN
-------------------------------------------------------------------------------------------
Index Scan using film_pkey on film (cost=0.28..8.42 rows=5 width=386)
Index Cond: ((film_id >= 1) AND (film_id >= 2) AND (film_id >= 199) AND (film_id >= 200))
Кардинальность повысилась, вместо того, чтобы понизиться. И, в конце концов, такой запрос вообще не должен выполняться. Жирный минус PostgreSQL.
SQL Server
Слияние предикатов IN Да, всё работает:
|--Nested Loops(Inner Join)
|--Index Seek(SEEK:([actor_id]=(2) OR [actor_id]=(3)))
|--RID Lookup(OBJECT:([actor]))
Слияние диапазонных предикатов
Опять же похоже на случай DB2:
|--Nested Loops(Inner Join)
|--Index Seek(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).
Облом!
Мне кажется, что это программная ошибка, ведь невозможный предикат приводит к гораздо более обоснованному:
|--Constant Scan
Резюме
Не забывайте, что есть множество предикатов, которые сливаются правильно в одних базах данных, а в других – нет. Если сомневаетесь – обязательно проверьте план выполнения!База данных | Слияние 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
WHERE 1 = 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):
Explain Plan
-----------------------------------
*ID | Operation | Rows | Cost
1 | RETURN | | 0
2 | TBSCAN GENROW | 0 of 0 | 0
Predicate Information
2 - RESID (1 = 0)
Соединение доказуемо пустого множества (INTERSECT):
Explain Plan
-----------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 0
2 | TBSCAN GENROW | 0 of 0 | 0
Predicate Information
2 - RESID (1 = 0)
Полусоединение доказуемо пустого множества (предикат IS NULL):
Explain Plan
-----------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 0
2 | TBSCAN GENROW | 0 of 0 | 0
Predicate Information
2 - RESID (1 = 0)
Полусоединение доказуемо пустого множества (INTERSECT):
Explain Plan
-----------------------------------
ID | Operation | Rows | Cost
1 | RETURN | | 0
2 | TBSCAN GENROW | 0 of 0 | 0
Predicate Information
2 - RESID (1 = 0)
Вау, круто! Похоже, победитель забега!
MySQL
Соединение доказуемо пустого множества (предикат IS NULL):
ID TABLE EXTRA
----------------------------
1 Impossible WHERE
Круто, я не ожидал!
Соединение доказуемо пустого множества (INTERSECT):
Увы, MySQL не поддерживает INTERSECT.
Полусоединение доказуемо пустого множества (предикат IS NULL):
ID TABLE EXTRA
----------------------------
1 Impossible 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 |
---------------------------------------------------------------------------
Predicate Information (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 |
---------------------------------------------------------------------------------
Predicate Information (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 |
-------------------------------------------------------------------------------------
Predicate Information (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 |
-------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
8 - access("A"."ACTOR_ID"="ACTOR_ID")
Не слишком хорошие результаты!
PostgreSQL
К вящему разочарованию, PostgreSQL в этом эксперименте показывает себя не с лучшей стороны! Соединение доказуемо пустого множества (предикат IS NULL): Не-а:
QUERY PLAN
--------------------------------------------------------------------------------------------
Hash Join (cost=8.31..13.07 rows=1 width=13)
Hash Cond: (a.actor_id = film_actor.actor_id)
-> Seq Scan on actor a (cost=0.00..4.00 rows=200 width=17)
-> Hash (cost=8.30..8.30 rows=1 width=2)
-> Index Scan using idx_fk_film_id on film_actor (cost=0.28..8.30 rows=1 width=2)
Index Cond: (film_id IS NULL)
Соединение доказуемо пустого множества (INTERSECT):
Еще хуже:
QUERY PLAN
---------------------------------------------------------------------------------------------------
Hash Join (cost=166.60..171.36 rows=1 width=29)
Hash Cond: (a.actor_id = fa.actor_id)
-> Seq Scan on actor a (cost=0.00..4.00 rows=200 width=25)
-> Hash (cost=166.59..166.59 rows=1 width=4)
-> Subquery Scan on fa (cost=0.00..166.59 rows=1 width=4)
-> HashSetOp Intersect (cost=0.00..166.58 rows=1 width=8)
-> Append (cost=0.00..139.26 rows=5463 width=8)
-> Subquery Scan on "*SELECT* 2" (cost=0.00..0.02 rows=1 width=8)
-> Result (cost=0.00..0.01 rows=1 width=4)
-> Subquery Scan on "*SELECT* 1" (cost=0.00..139.24 rows=5462 width=8)
-> Seq Scan on film_actor (cost=0.00..84.62 rows=5462 width=4)
Полусоединение доказуемо пустого множества (предикат IS NULL):
Так же, как и в случае со внутренним соединением:
QUERY PLAN
-------------------------------------------------------------------------------------------------
Hash Semi Join (cost=6.06..10.60 rows=1 width=25)
Hash Cond: (a.actor_id = film_actor.actor_id)
-> Seq Scan on actor a (cost=0.00..4.00 rows=200 width=25)
-> Hash (cost=6.05..6.05 rows=1 width=2)
-> Index Only Scan using film_actor_pkey on film_actor (cost=0.28..6.05 rows=1 width=2)
Index Cond: (actor_id IS NULL)
Полусоединение доказуемо пустого множества (INTERSECT):
Как и ожидалось:
QUERY PLAN
--------------------------------------------------------------------------------------------------
Hash Semi Join (cost=152.94..157.48 rows=1 width=25)
Hash Cond: (a.actor_id = "ANY_subquery".actor_id)
-> Seq Scan on actor a (cost=0.00..4.00 rows=200 width=25)
-> Hash (cost=152.93..152.93 rows=1 width=2)
-> Subquery Scan on "ANY_subquery" (cost=0.00..152.93 rows=1 width=2)
-> HashSetOp Intersect (cost=0.00..152.92 rows=1 width=6)
-> Append (cost=0.00..139.26 rows=5463 width=6)
-> Subquery Scan on "*SELECT* 2" (cost=0.00..0.02 rows=1 width=6)
-> Result (cost=0.00..0.01 rows=1 width=2)
-> Subquery Scan on "*SELECT* 1" (cost=0.00..139.24 rows=5462 width=6)
-> Seq Scan on film_actor (cost=0.00..84.62 rows=5462 width=2)
SQL Server
SQL Server тут во всей красе, как и DB2! Соединение доказуемо пустого множества (предикат IS NULL):
|--Constant Scan
Соединение доказуемо пустого множества (INTERSECT):
|--Constant Scan
Полусоединение доказуемо пустого множества (предикат IS NULL):
|--Constant Scan
Полусоединение доказуемо пустого множества (INTERSECT):
|--Constant Scan
Резюме
База данных | 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 | Да | Да | Да | Да |
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ