PostgreSQL のクエリ実行のテーブルスキャンにおいて Bitmap scan はどういう条件で選ばれるのか

この記事は毎週必ず記事がでるテックブログ Loglass Tech Blog Sprint の73週目の記事です！
2年間連続達成まで残り33週となりました！

こんにちは、株式会社ログラスでエンジニアをしている上田（@ueda1013）です。

遅いクエリの調査などで実行計画を確認していると、テーブルのスキャン方法について「どのスキャン方法が選ばれているのか？」という点が気になることがあります。

Seq scan はいわゆるフルスキャン、インデックスを適切に設定すると Index scan になる、あたりまでは比較的理解しやすいのですが、スキャン方法の1つである Bitmap scan は挙動が分かりづらく、どういった条件で選ばれるのか気になっていました。

そこで、どういった条件だと Bitmap scan になるのか複数の条件で実際にクエリを実行して試してみたので、今回の記事ではその検証結果をまとめたいと思います。

スキャン系ノードの概要

PostgreSQL でテーブルをスキャンする際に使われるスキャン系ノードには、主に以下の種類があります。

ノード名	説明
Seq scan	テーブル全体を一行ずつ順番にスキャンする方法。特にインデックスが使えない場合に選ばれることが多い
Index scan	インデックスを利用して条件に一致するデータを取得
Bitmap Heap scan	インデックスからビットマップを作成し、それをもとにスキャンする手法
Index Only scan	インデックスだけで必要なデータを取得。テーブルへのアクセスが不要になる

今回の記事では、上から3つ目の Bitmap scan を扱います。

Bitmap scan とは何かは上記の説明のみだと不十分かと思います。気になる方は、「ビットマップインデックスの仕組み」でとても分かりやすく解説されているので、こちらをご参考いただけると嬉しいです。

また、Bitmap scan 以外の挙動については、「postgresqlにおけるテーブルスキャンの実行例」がとても分かりやすくまとまっていたのでこちらも合わせて紹介させていただきます。

Bitmap scan が選ばれる条件を考える

Bitmap scan が選ばれる条件を検索して調べていると、主に以下の条件が関係していそうなことが分かりました。これらを検証するために実際にクエリを作成し実行計画を取得してみます。

1. カーディナリティ（値の種類）
2. 結果行数
3. 条件の種類（AND/OR検索）

事前準備

これらの条件を実際に試すため、簡単なテーブルを作ります。カーディナリティや結果行数の制御のため、必要なカラムとデータセットを用意しました。

create database lgtechblogsprint;

create table products (
    id serial primary key,
    name varchar(50) not null,  -- 高カーディナリティ用のカラム
    category varchar(20) not null, -- 低カーディナリティ用のカラム
    price int not null -- 結果行数を制御するためのカラム
);

insert into products (name, category, price)
select
    '商品' || i as name,
    case when i % 3 = 0 then '家具'
         when i % 3 = 1 then '家電'
         else 'キッチン用品' end as category,
    case when i = 500 then 999 -- 結果行数を制御するため特定の行に特定の値を割り当て
         when i % 100 < 50 then 100
         else 200 end as price
from generate_series(1, 10000) as s(i);

create index idx_name on products (name);
create index idx_category on products (category);
analyze products;

念のため統計情報を取得してカーディナリティが意図した結果になっているか確認しておきます。

select attname, n_distinct
from pg_stats
where tablename = 'products' and attname in ('name', 'category');

 attname  | n_distinct 
----------+------------
 name     |         -1  -- 高カーディナリティ
 category |          3  -- 低カーディナリティ
(2 rows)

実験

それでは、Bitmap scan の挙動を確認するためのクエリを試してみます。

1. カーディナリティ（値の種類）の影響

カーディナリティが高いカラム^[1]を検索（name）

explain select * from products where name = '商品500' and price = 100;

                                QUERY PLAN                                
--------------------------------------------------------------------------
 Index Scan using idx_name on products  (cost=0.29..8.30 rows=1 width=28)
   Index Cond: ((name)::text = '商品500'::text)
   Filter: (price = 100)
(3 rows)

Index scan になりました。

カーディナリティが低いカラム^[2]を検索（category）

explain select * from products where category = '家具' and price = 999;

                                  QUERY PLAN                                   
-------------------------------------------------------------------------------
 Bitmap Heap Scan on products  (cost=41.28..168.28 rows=1 width=28)
   Recheck Cond: ((category)::text = '家具'::text)
   Filter: (price = 999)
   ->  Bitmap Index Scan on idx_category  (cost=0.00..41.28 rows=3333 width=0)
         Index Cond: ((category)::text = '家具'::text)
(5 rows)

Bitmap scan になりました。

※クエリの where 句の price は結果行数を揃えるために指定しています

結果

結果行数は同じですが、カーディナリティが高いカラムを指定したクエリでは Index scan が選ばれ、カーディナリティが低いカラムを指定したクエリでは Bitmap scan が利用されることが確認できました。

これは、PostgreSQL でコスト計算する際、カーディナリティが低いカラムでは多くの行を効率的に取り出すためにビットマップが有効と判定されているためかと思われます。

2. 結果行数の影響

結果行数が少ない^[3]場合

explain select * from products where name = '商品1';

                                QUERY PLAN                                
--------------------------------------------------------------------------
 Index Scan using idx_name on products  (cost=0.29..8.30 rows=1 width=28)
   Index Cond: ((name)::text = '商品1'::text)
(2 rows)

Index scan になりました。

結果行数が中程度^[4]の場合

explain select * from products where name like '商品1%';

                                        QUERY PLAN                                        
------------------------------------------------------------------------------------------
 Bitmap Heap Scan on products  (cost=32.55..124.54 rows=1111 width=28)
   Filter: ((name)::text ~~ '商品1%'::text)
   ->  Bitmap Index Scan on idx_name  (cost=0.00..32.27 rows=1199 width=0)
         Index Cond: (((name)::text >= '商品1'::text) AND ((name)::text < '商品2'::text))
(4 rows)

結果行数が増えたからか、Bitmap scan になりました。

結果行数が多い^[5]場合

explain select * from products where name like '商品%';

                          QUERY PLAN                          
--------------------------------------------------------------
 Seq Scan on products  (cost=0.00..202.00 rows=9999 width=28)
   Filter: ((name)::text ~~ '商品%'::text)
(2 rows)

Seq scan になりました。ほとんどのレコードが対象となるため、フルスキャンの方が効率が良いと判断されたからでしょうか。

結果

結果行数が非常に少ない場合はインデックスをそのまま活用していましたが、結果行数を増やした結果ビットマップを作成するようになりました。インデックスのみを使用するのではなく、ビットマップを作成して絞り込んだ方が効率的だと判定されていそうです。

反対に対象行数が非常に多い場合は全行をスキャンしており、ビットマップの作成が余分なコストと判定されているように見えます。

3. 条件の種類（AND/OR検索）

AND条件

explain select * from products where name = '商品500' and category = '家具' and price = 999;

                                QUERY PLAN                                
--------------------------------------------------------------------------
 Index Scan using idx_name on products  (cost=0.29..8.31 rows=1 width=28)
   Index Cond: ((name)::text = '商品500'::text)
   Filter: (((category)::text = '家具'::text) AND (price = 999))
(3 rows)

Index scan になりました。

OR条件

explain select * from products where (name = '商品500' or category = '家具') and price = 999;

                                       QUERY PLAN                                        
-----------------------------------------------------------------------------------------
 Bitmap Heap Scan on products  (cost=45.58..180.92 rows=1 width=28)
   Recheck Cond: (((name)::text = '商品500'::text) OR ((category)::text = '家具'::text))
   Filter: (price = 999)
   ->  BitmapOr  (cost=45.58..45.58 rows=3334 width=0)
         ->  Bitmap Index Scan on idx_name  (cost=0.00..4.29 rows=1 width=0)
               Index Cond: ((name)::text = '商品500'::text)
         ->  Bitmap Index Scan on idx_category  (cost=0.00..41.28 rows=3333 width=0)
               Index Cond: ((category)::text = '家具'::text)
(8 rows)

Bitmap scan になりました。

※クエリの where 句の price は結果行数を揃えるために指定しています

結果

AND条件 で条件が限られる場合、インデックスを使用して効率的に必要な行を取得し、OR条件 で条件を複合する必要がある場合は、ビットマップが作成されています。

また、インデックスというと通常は B-treeインデックス というツリー型のインデックスが使用されていますが、OR検索 では使用することができないデメリットがあります。OR検索 では代わりにビットマップを使用することで、OR検索 時にもインデックスを活用できるようになっているようです。

さいごに

今回の実験を通じて、PostgreSQL のスキャン系ノード選択の仕組みを少し深掘りできました。

• 高カーディナリティの列では、インデックスを活用した Index scan が選ばれ、必要な行を効率的に直接的に取得していた
• 一方、低カーディナリティの列や結果行数が多い場合では、Bitmap scan が選ばれることで、広範囲な行を効率的にスキャンする方法が確認できた
• OR条件 では、ビットマップが利用され、B-treeインデックス のデメリットを補う形で最適化がされていた

PostgreSQL がエンジニアの代わりに状況に応じて適切なスキャン方法を選択していることが実際に確認でき、おおまかな挙動は掴めたので、実行計画がとても読みやすくなりそうです。

データベースの仕組みは奥が深く、まだまだ知らないことがたくさんあるので、気になるテーマを見つけてまた深掘りしてみたいと思います。

さいごに、ログラスのエンジニアリングや組織についてお話するカジュアル面談を公開しているので、ご興味あればお気軽にご連絡いただけると嬉しいです。

https://pitta.me/matches/WhsNecfrvgZo

お読みいただきありがとうございました！

参考文献

• postgresqlにおけるテーブルスキャンの実行例
• ビットマップインデックスの仕組み
• [改訂3版] 内部構造から学ぶPostgreSQL――設計・運用計画の鉄則 Software Design plus
  上原 一樹, 佐伯 昌樹, 原田 登志, 勝俣 智成
• SQL実践入門――高速でわかりやすいクエリの書き方 WEB+DB PRESS plus
  ミック

脚注

1. 今回は pg_stats からの n_distinct 値が -1 （すべての行がユニーク）のカラムを用意

2. 今回は pg_stats からの n_distinct 値が 3 のカラムを用意

3. 今回は explain の予測行数が 1 行のクエリを作成

4. 今回は explain の予測行数が約 1,000 行のクエリを作成

5. 今回は explain の予測行数が約 10,000 行のクエリを作成