不依赖于成本模型的酷 SQL 优化。第1部分

仅基于元数据（即约束）和查询本身即可实现的五种简单优化 我们为您提供 Lukas Eder 文章的改编版，专为那些对数据库和 SQL 有一般了解以及 DBMS 的一些实践经验的人而设计。 成本优化实际上是现代数据库中优化 SQL 查询的标准方法。这就是为什么用3GL（第三代编程语言）手动编写复杂算法如此困难，其性能将超过现代优化器生成的动态计算执行计划。今天我们不讨论成本优化，即基于数据库成本模型的优化。我们将研究更简单的优化。那些可以仅基于元数据（即限制）和请求本身来实现的。通常，它们对数据库的实现不是牛顿二项式，因为在这种情况下，任何优化都将导致更好的执行计划，无论是否存在索引、数据量和数据分布的偏度。“不是牛顿二项式”并不是指实现优化有多容易，而是指是否应该这样做。这些优化消除了[数据库]不必要的额外工作（而不是我已经写过的不必要的必需工作）。

这些优化有什么用？

其中大部分用于：

• 查询中的错误修复；
• 允许在数据库不实际执行视图逻辑的情况下重用视图。

在第一种情况下，人们可能会说：“那又怎么样，继续修复这个愚蠢的 SQL 查询吧。” 但让从来没有犯过错误的人先向我扔石头吧。第二种情况特别有趣：它使我们能够创建可以跨多个层重用的复杂的视图和表函数库。

使用的数据库

在本文中，我们将比较 5 个最广泛使用的 DBMS 中的 10 个 SQL 优化（根据数据库排名）：

• 甲骨文 12.2；
• MySQL 8.0.2；
• SQL Server 2014；
• PostgreSQL 9.6；
• DB2 LUW 10.5。

另一个评级几乎与之呼应。像往常一样，在本文中我将查询 Sakila 数据库。 以下是这十种优化的列表：

1. 传递闭包；
2. 不可能的谓词和不必要的表调用；
3. 消除连接；
4. 消除“无意义”谓词；
5. EXISTS 子查询中的投影；
6. 谓词的合并；
7. 可证明空集；
8. 约束条件检查；
9. 不必要的反射性连接；
10. 下推谓词

今天我们将讨论 pp. 1-3，第二部分 - 4 和 5，第三部分 - 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 DBMS 的情况下执行此查询的计划：

--------------------------------------------------------------
| 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 选择。因此，只要有可能，请设计连接和简单谓词以利用传递闭包。还有哪些数据库支持此功能？

数据库2

是的！

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服务器

是的！

|--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。这是不言自明的，所以让我们直接跳到找出哪些数据库执行此优化。

数据库2

是的！

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 子句。谢谢你！这使得分析变得更加容易，特别是与其他数据库相比。

甲骨文

是的！

---------------------------------------------------------------
| 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，但是还有一个Id=1的过滤操作（FILTER），这里永远不会有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 服务器？

是的！

|--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

如果存在可为空的外键，则可以替换“...-to-one”类型的 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

如果存在唯一键，则可以删除“...-to-one”类型的 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 没有外键。可以去掉“...-to-many”类型的唯一外连接（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 是无可争议的领导者！ 待续