PostgreSQL 13の実行計画

スポンサーリンク

PostgreSQLに限らず多くのRDBMSはどのようにデータベースを探索するのかが高速なのかの「実行計画」を立てます。実行計画には、レコードを全て探索するようなシーケンススキャン(seq scan)やインデックスに沿った探索を行うインデックススキャン(index scan)があります。このページでは「実行計画」についてまとめます。

事前準備

PostgreSQLチュートリアルのサンプル教材であるdvdrentalをインポートします。

wget https://sp.postgresqltutorial.com/wp-content/uploads/2019/05/dvdrental.zip
unzip dvdrental.zip
pg_restore -d dvdrental dvdrental.tar
rm dvdrental.tar dvdrental.zip 

単一テーブルのスキャン

単一のテーブルを探索する時は、全レコードを調べる「シーケンススキャン(seq scan, 全走探索)」やインデックスに沿って探索する「インデックススキャン(index scan)」などがあります。

シーケンススキャン

インデックスではなく、全てのレコードを順次探索した方が早い場合はシーケンススキャンが実行されます。

dvdrental=# EXPLAIN SELECT * FROM rental ;
                         QUERY PLAN                          
-------------------------------------------------------------
 Seq Scan on rental  (cost=0.00..310.44 rows=16044 width=36)
(1 row)

インデックススキャン

インデックスに沿って探索した方が早い場合はインデックススキャン(index scan)が実行されます。

レコードが少ないテーブルの場合はインデックスが付与されていたとしてもシーケンススキャンが実行されますが、レコードが一定数を越えたタイミングでインデックススキャンに変わります。

dvdrental=# EXPLAIN SELECT * FROM rental WHERE rental_id < 10 ;
                                QUERY PLAN                                 
---------------------------------------------------------------------------
 Index Scan using rental_pkey on rental  (cost=0.29..8.47 rows=9 width=36)
   Index Cond: (rental_id < 10)
(2 rows)

ビットマップスキャン

PostgreSQLは一意性が高い(カーディナリティが高い)レコードに対してインデックスを作成する場合はB-tree(二分木)のインデックスを作成しますが、一意性が低い(カーディナリティが低い)レコードに対してインデックスを作成する場合はビットマップインデックスを作成します。

例えば、性別や言語のように取りうる値が少ない場合は、B-treeではなくビットマップのインデックスを作成します。

以下SQL文のようにinventory_idで絞り込む場合は、inventory_idは一意性が低い(カーディナリティが低い)のでビットマップに従った探索が行われます。

dvdrental=# EXPLAIN SELECT * FROM rental WHERE inventory_id = 1525;
                                    QUERY PLAN                                  
  
--------------------------------------------------------------------------------
--
 Bitmap Heap Scan on rental  (cost=4.31..15.07 rows=3 width=36)
   Recheck Cond: (inventory_id = 1525)
   ->  Bitmap Index Scan on idx_fk_inventory_id  (cost=0.00..4.31 rows=3 width=0
)
         Index Cond: (inventory_id = 1525)
(4 rows)

複数テーブルの結合

複数テーブルを結合する時は、総当たりで結合する「Nested Loop」やインデックスに沿って結合する「ハッシュ結合」などの実行計画が立てられます。

Nested Loop

インデックスが付与されてないテーブルを結合したりレコード数が少ないテーブルを結合したりする時は、総当たりで結合する「Nested Loop」が採用されます。

以下はNested Loopが実行される例です。サンプル教材のdvdrentalではstaffが2人しか居ないため、インデックスが付与されていてもNested Loopが採用されます。このように結合先のテーブルのレコードが少ないならば、後述の「Hash Join」よりも「Nested Loop」の方が優位です。

dvdrental=# explain select * from rental join staff using (staff_id);
                            QUERY PLAN                             
-------------------------------------------------------------------
 Nested Loop  (cost=0.00..712.57 rows=16044 width=565)
   Join Filter: (rental.staff_id = staff.staff_id)
   ->  Seq Scan on rental  (cost=0.00..310.44 rows=16044 width=36)
   ->  Materialize  (cost=0.00..1.03 rows=2 width=531)
         ->  Seq Scan on staff  (cost=0.00..1.02 rows=2 width=531)
(5 rows)

Hash Join(ハッシュ結合)

インデックスが付与されている場合にそのハッシュ値に沿って結合する実行計画を「Hash Join(ハッシュ結合)」と呼びます。

dvdrental=# explain select * from rental join inventory using ( inventory_id );
                                QUERY PLAN                                
--------------------------------------------------------------------------
 Hash Join  (cost=128.07..480.67 rows=16044 width=48)
   Hash Cond: (rental.inventory_id = inventory.inventory_id)
   ->  Seq Scan on rental  (cost=0.00..310.44 rows=16044 width=36)
   ->  Hash  (cost=70.81..70.81 rows=4581 width=16)
         ->  Seq Scan on inventory  (cost=0.00..70.81 rows=4581 width=16)
(5 rows)

Marge Join(マージ結合)

インデックスが付与されている場合に予めソートされたキーを互いに突き合わせる実行計画を「Marge Join(マージ結合)」と呼びます。

MySQLにはMarge Joinの概念はありません。

dvdrental=# EXPLAIN SELECT * FROM payment JOIN customer USING ( customer_id ) JOIN rental USING ( rental_id ) ;
                                                QUERY PLAN                                                 
-----------------------------------------------------------------------------------------------------------
 Merge Join  (cost=1981.22..2773.77 rows=14596 width=126)
   Merge Cond: (rental.rental_id = payment.rental_id)
   ->  Index Scan using rental_pkey on rental  (cost=0.29..578.29 rows=16044 width=36)
   ->  Sort  (cost=1936.43..1972.92 rows=14596 width=94)
         Sort Key: payment.rental_id
         ->  Merge Join  (cost=0.56..926.88 rows=14596 width=94)
               Merge Cond: (payment.customer_id = customer.customer_id)
               ->  Index Scan using idx_fk_customer_id on payment  (cost=0.29..705.31 rows=14596 width=26)
               ->  Index Scan using customer_pkey on customer  (cost=0.28..37.63 rows=599 width=70)
タイトルとURLをコピーしました