コスト モデルに依存しない優れた SQL 最適化。パート1

メタデータ (制約など) とクエリ自体にのみ基づいて実装できる 5 つの簡単な最適化 データベースと SQL についての一般的な理解と DBMS の実践経験がある人向けに、Lukas Eder の記事を改変したものを提供します。 。 コストの最適化は、実際には、最新のデータベースで SQL クエリを最適化する標準的な方法です。これが、最新のオプティマイザによって生成される動的に計算された実行計画を超えるパフォーマンスをもたらす複雑なアルゴリズムを3GL (第 3 世代プログラミング言語)で手動で記述することが非常に難しい理由です。今日はコストの最適化、つまりデータベースのコストモデルに基づく最適化については説明しません。より単純な最適化を見ていきます。メタデータ (つまり、制限) とリクエスト自体にのみ基づいて実装できるもの。通常、データベースへの実装はニュートン二項式ではありません。この場合、インデックスの存在、データ量、データ分散の歪みに関係なく、あらゆる最適化がより良い実行計画につながるからです。「ニュートン二項式ではない」とは、最適化の実装がいかに簡単であるかという意味ではなく、最適化を実行すべきかどうかという意味です。これらの最適化により、[データベースに対する] 不必要な余分な作業が排除されます (すでに書いた不必要で必要な作業とは対照的です)。

これらの最適化は何に使用されますか?

それらのほとんどは次の目的で使用されます。

• クエリのバグ修正。
• データベースが実際にビュー ロジックを実行しなくても、ビューを再利用できるようになります。

最初のケースでは、「それでは、この愚かな SQL クエリを修正してください。」と言うことができます。しかし、一度も間違いを犯したことがない人に、まず私に石を投げてもらいましょう。2 番目のケースは特に興味深いものです。これにより、複数のレイヤー間で再利用できるビューとテーブル関数の複雑なライブラリを作成できるようになります。

使用されるデータベース

この記事では、最も広く使用されている 5 つの DBMS における 10 の SQL 最適化を比較します (データベース ランキングに従って)。

• オラクル 12.2;
• MySQL 8.0.2;
• SQL Server 2014。
• PostgreSQL 9.6;
• DB2 LUW 10.5。

別の評価もそれとほぼ同じです。いつものように、この記事では、Sakila データベースにクエリを実行します。 これら 10 種類の最適化のリストは次のとおりです。

1. 推移閉包;
2. 不可能な述語と不必要なテーブル呼び出し。
3. JOIN を削除します。
4. 「意味のない」述語の削除。
5. EXISTS サブクエリのプロジェクション。
6. 述語のマージ。
7. おそらく空集合。
8. 制約チェック;
9. 不必要な反射的な接続。
10. プッシュダウン述語

今日はpp.36について説明します。1〜3、2番目のパートでは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 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 が選択される可能性があります。したがって、可能な限り、推移閉包を利用するように結合と単純な述語を設計してください。この機能をサポートしているデータベースは他にありますか?

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 が 2 回指定されているという事実は、両方のテーブルが定数値を検索していることを示しています。同時に、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

最初のクエリは明らかに結果を返しませんが、2 番目のクエリにも同じことが当てはまります。結局のところ、NULL IS NULL は常に TRUE ですが、NULL = NULL の計算結果は NULL となり、3 値論理によれば、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 句について知らせてくれました。ありがとう！これにより、特に他のデータベースと比較して、分析がはるかに簡単になります。

オラクル

はい！

---------------------------------------------------------------
| 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 ブール データ型を嫌っているため、プランでは単に FALSE ではなく NULL IS NOT NULL と表示されます。まあ...しかし真剣に、その述語を見てください。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 が複数のテーブル アクセスのうちの 1 つを必要としない場合はどうなるでしょうか? JOIN の削除については、ブログの以前の投稿ですでに書きました。SQL エンジンは、クエリの種類と主キーと外部キーの存在に基づいて、特定の JOIN が特定のクエリで実際に必要かどうか、またはそれを削除してもクエリのセマンティクスに影響を与えないかどうかを判断できます。次の 3 つの例ではすべて、JOIN は必要ありません。内部 ...-to-one 結合は、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 は、Null 許容外部キーがある場合に置き換えることができます。上記のクエリは、外部キーに 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 は、ここでは議論の余地のないリーダーです。 つづく