【PostgreSQL】実行計画について

## 初めに

## 実行計画とは
SQLクエリが実際にどのように実行されるかを決定するための戦略のことを指します。これは、テーブルの結合順序、インデックスの使用、ソート操作など、データベースがクエリを最も効率的に実行する方法を決定します。

## EXPLAINとは？
EXPLAINコマンドを利用して問い合わせに対してプランナがどのような問い合わせ計画を作ったのかがわかる。
デフォルトではtext出力ですが、機械が読み取りしやすいようにXML、JSON、YAMLでの出力が可能。

### EXPLAINの基本について
EXPLAINは推定値であるため、実際のSQLの実行と合わせて推定値を出せるEXPLAIN ANALYZEを利用する。

### 実行計画の読み方について
実行計画は、クエリを処理するための一連のステップを表すツリー構造として表現されている。
このツリー構造の各要素をノードと言う。
``` sql
EXPLAIN ANALYZE SELECT *
FROM tenk1 t1, tenk2 t2
WHERE t1.unique1 < 10 AND t1.unique2 = t2.unique2;

                                                           QUERY PLAN
-------------------------------------------------------------------​--------------------------------------------------------------
 Nested Loop  (cost=4.65..118.62 rows=10 width=488) (actual time=0.128..0.377 rows=10 loops=1)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.36..39.47 rows=10 width=244) (actual time=0.057..0.121 rows=10 loops=1)
         Recheck Cond: (unique1 < 10)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.36 rows=10 width=0) (actual time=0.024..0.024 rows=10 loops=1)
               Index Cond: (unique1 < 10)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.29..7.91 rows=1 width=244) (actual time=0.021..0.022 rows=1 loops=10)
         Index Cond: (unique2 = t1.unique2)
 Planning time: 0.181 ms
 Execution time: 0.501 ms
 ```

`Nested Loop  (cost=4.65..118.62 rows=10 width=488) (actual time=0.128..0.377 rows=10 loops=1)`
「Nested Loop」は、クエリが実行された方法を示しています。Nested Loopは、2つのテーブル（この場合はtenk1とtenk2）間の結合を行う方式の一つで、一つ目のテーブルの各行に対して二つ目のテーブルを全走査する方法です。

`Bitmap Heap Scan on tenk1 t1  (cost=4.36..39.47 rows=10 width=244) (actual time=0.057..0.121 rows=10 loops=1)`
「Bitmap Heap Scan on tenk1 t1」は、tenk1テーブルでBitmap Heap Scanが行われたことを示しています。Bitmap Heap Scanは、インデックスを使用してクエリ条件に一致する可能性のある行を特定し、その後でそれらの行を直接テーブルからフェッチする方法です。「cost=4.36..39.47 rows=10 width=244」は、この操作のコスト、返す行数の予測、そして返されるデータの幅を示しています。
「actual time=0.057..0.121 rows=10 loops=1」は、`actual time`で実際にその操作にかかった時間を示している。0.057秒から開始して0.121秒で終了と示している。`row`で実際に返す行数、`loop`でその操作が何回実行されたかを示す。

`Recheck Cond: (unique1 < 10)`
「Recheck Cond: (unique1 < 10)」は、Bitmap Heap Scanが行われた後で、再び条件を確認したことを示しています。これは、Bitmap Heap Scanがいくつかの余分な行をフェッチする可能性があるためです。

`Bitmap Index Scan on tenk1_unique1`
「Bitmap Index Scan on tenk1_unique1」は、インデックスtenk1_unique1がBitmap Index Scanでスキャンされたことを示しています。これは、クエリのWHERE句の条件に一致する行を特定するために行われます。

`Index Scan using tenk2_unique2 on tenk2 t2`
「Index Scan using tenk2_unique2 on tenk2 t2」は、tenk2テーブルのtenk2_unique2インデックスがスキャンされたことを示しています。これは、Nested Loopの内側のループで行われ、t1.unique2がt2.unique2と等しい行を見つけるためです。

`Planning time: 0.181 ms`
`Execution time: 0.501 ms`
「Planning time」は解析された問い合わせから問い合わせ計画を生成し最適化するのにかかった時間
「Execution time」は、エクゼキュータの起動、停止時間、発行される何らかのトリガの実行時間も含まれますが、解析や書き換え、計画作成の時間は含まれません。

## ノードについて
### スキャンノード
#### シーケンシャルスキャン
`Sec Scan`
テーブルを1行ずつ取り出してスキャンする手法。

#### インデックススキャン
`Index Scan`
先にインデックスファイルにアクセスして条件に該当する行の位置を取得してからテーブルファイルにアクセスし、該当行をスキャンする。
シーケンシャルスキャンよりも基本的には高速だが、大量の行を取得すると効率が悪化する場合がある。
インデックスファイルのみを参照する`Index Only Scan`というより高速なスキャン形式がある。
ただし以下の条件がある
- インデックスが`B-Tree`インデックス、GiST、SP-GiSTインデックスの一部の演算子であること
- 問い合わせでインデックスに指定されていない列は使えない
- 可視性マップ[^1]を見てそれが可視であった場合
[^1]:各データブロックが全てのアクティブなトランザクションに対して可視であるかどうかを追跡するためのデータ構造

#### ビットマップスキャン
ビットマップとは列の値の種類（カーディナリティー[^2]）レコードで定義される2次元のインデックスのこと。
OR検索するときに効果を発揮する。
[^2]:カーディナリティーが低いとは、例えば性別のカラムであれば2択であるようなデータのこと

### 結合系ノード
`Nested Loop`
外部表から1行ずつ取り出し、その結合キーを内部表の全ての行の結合キーに対して突き合わせ、条件に合う行を結合する。
内部表の結合キーにインデックスが設定されている場合には内部表での検索が高速になる。
外部表の行数が内部表より少ないとループの数が減るため高速に処理できる。

`Hash Join`
内部表のハッシュ表を事前に作成、外部表と突き合わせる。
ハッシュ表の作成にコストが発生するが、ハッシュがメモリに収まるなら有効な方法。
外部表が大きく内部表が小さいときに効果的。

`Merge Join`
外部表と内部表を結合キーでソートして突き合わせる。
ソート処理にオーバーヘッドが発生するが、検索は高速である。
B-Treeインデックスが作成されている場合はこちらを利用する。
大規模なテーブル同士を結合するのに効果的。

### 条件に対応する実行計画
SQL構文に対応するノードがある。
- `JOIN`
最適な結合系ノードが選択される。

- `GROUP BY`
GroupAggregateノードは事前にソートを行ってから集約する。
HashAggregateノードは事前にハッシュ表を作ってから集約する。
HashAggregateノードはwork_memが不足していると選択されないという欠点がある。
Aggregateノードは比較的単純な集約関数(sum・count)に用いられる。

- `ORDER BY`
Sortノードが対応する。

- `LIMIT`
Limitノードは指定された行数が取り出せた時点で内部的な処理を中断する。

### その他
- パーティション
`Append`ノードが対応する。

- パラレルクエリ
`Gather`、`Gather Merge`が対応する。
`Gather`はパラレルクエリの結果の行の順番を問わない場合に利用する。
`Gather Merge`はパラレルクエリの結果をソートしたい場合に利用する。

``` sql
EXPLAIN SELECT * FROM pgbench_accounts WHERE filler LIKE '%x%';
                                     QUERY PLAN                                      
-------------------------------------------------------------------​------------------
 Gather  (cost=1000.00..217018.43 rows=1 width=97)
   Workers Planned: 2
   ->  Parallel Seq Scan on pgbench_accounts  (cost=0.00..216018.33 rows=1 width=97)
         Filter: (filler ~~ '%x%'::text)
(4 rows)
```

`Workers Planned: 2`
クエリの実行に2つのワーカープロセスが予定されている。

`Parallel Seq Scan`
パラレルでシーケンシャルスキャンを実施する
他のノードの場合は`Parallel ~`と対応する。

### ウィンドウ関数
`WindowAgg`ノードが対応する。

## まとめ