不依賴成本模型的酷 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 是無可爭議的領導者！ 待續