Клёвые оптимизации 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. cлияние предикатов;
7. доказуемо пустые множества;
8. oграничения 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 тут – безусловные лидеры! Продолжение следует