Это — интересная возможность, на которой я когда-то споткнулся, ошибочно предположив, что моя СУБД на такое способна.
Рассмотрим следующий запрос:
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):
Соединение доказуемо пустого множества (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):
Забавно. Как видим, при этом плане выполнения происходит просмотр всего первичного ключа таблицы 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):
Опять же, никакой оптимизации:
К вящему разочарованию, 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
Да
Да
Да
Да
Заметим, что это можно выполнить и множеством других способов. Не стесняйтесь комментировать и предлагать свои собственные варианты создания "доказуемо пустых множеств", чтобы проверить оптимизацию их этими базами данных.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ