Postgresでも複数のインデックスが使用可能な状況ならカーディナリティが高いカラムのが優先的に使われるんだよね

はじめに

タイトル通りです。

挙動ベースのお話でソースを追ったわけではないのです。

環境

select version();

PostgreSQL 14.5, compiled by Visual C++ build 1914, 64-bit

環境構築

こんな感じにクラスタを作成して

initdb --encoding=UTF8 --no-locale --username=postgres --pgdata=C:\pgdata\14

こんな感じにテーブルを作ります。

create table table1
(
    id bigint primary key,
    c1 varchar(10) not null,
    c2 varchar(10) not null,
    c3 bigint      not null,
    c4 bigint      not null
);

create index idx_table1_c1 on table1 (c1);
create index idx_table1_c2 on table1 (c2);
create index idx_table1_c3 on table1 (c3);
create index idx_table1_c4 on table1 (c4);

そうしたらこんな感じにダミーデータをぶち込みます。

using Dapper;
using Npgsql;

namespace ConsoleApp1
{
    internal class Program
    {
        static void Main(string[] args)
        {
            using var db = new NpgsqlConnection("Host=localhost;Username=testdb;Database=testdb");
            db.Open();

            var tx = db.BeginTransaction();
            var rand = new Random();

            for (var i = 0; i < 10_000_000; i++)
            {
                if (i != 0 && i % 10000 == 0)
                {
                    Console.WriteLine("{0}", i);
                    tx.Commit();
                    tx = db.BeginTransaction();
                }

                var n = rand.Next();

                var p = new
                {
                    Id = i,
                    C1 = n,
                    C2 = n % 1_000,
                    C3 = n % 100_000,
                    C4 = n % 1_000_000,
                };

                db.Execute("insert into table1 (id, c1, c2, c3, c4) values (@Id, @C1, @C2, @C3, @C4)", p, transaction: tx);
            }

            tx.Commit();
        }
    }
}

あとは念のため

analyse table1;

しておきましょうか。

検証

統計情報のうち、個別値の推定値を見てみましょう。

select tablename,
       attname,
       n_distinct
from pg_stats
where tablename = 'table1'
  and attname <> 'id'
order by attname;
tablename attname n_distinct
table1 c1 -1
table1 c2 1000
table1 c3 97508
table1 c4 919503

n_distinctの説明は以下の感じです。

www.postgresql.jp

c1は統計情報的には完全に固有の値とみなされています。あとはc4 → c3 → c2の順で個別値の数が多いと推定されています。

つまり、統計情報的にはc1 → c4 → c3 → c2の順でインデックスを使ったほうが有利になるはずです。

explain analyse
select *
from table1
where c4 = 1 and c3 = 1 and c2 = 1 and c1 = 1;

Index Scan using idx_table1_c1 on table1  (cost=0.43..2.66 rows=1 width=40) (actual time=0.017..0.017 rows=0 loops=1)
  Index Cond: (c1 = 1)
  Filter: ((c4 = 1) AND (c3 = 1) AND (c2 = 1))
Planning Time: 0.151 ms
Execution Time: 0.035 ms
explain analyse
select *
from table1
where c4 = 1 and c3 = 1 and c2 = 1;

Bitmap Heap Scan on table1  (cost=4.18..5.29 rows=1 width=40) (actual time=0.106..0.193 rows=16 loops=1)
  Recheck Cond: ((c4 = 1) AND (c3 = 1))
  Filter: (c2 = 1)
  Heap Blocks: exact=16
  ->  BitmapAnd  (cost=4.18..4.18 rows=1 width=0) (actual time=0.094..0.095 rows=0 loops=1)
        ->  Bitmap Index Scan on idx_table1_c4  (cost=0.00..1.62 rows=11 width=0) (actual time=0.068..0.068 rows=16 loops=1)
              Index Cond: (c4 = 1)
        ->  Bitmap Index Scan on idx_table1_c3  (cost=0.00..2.31 rows=103 width=0) (actual time=0.023..0.023 rows=93 loops=1)
              Index Cond: (c3 = 1)
explain analyse
select *
from table1
where c3 = 1 and c2 = 1;

Bitmap Heap Scan on table1  (cost=86.17..87.29 rows=1 width=40) (actual time=1.511..1.682 rows=93 loops=1)
  Recheck Cond: ((c3 = 1) AND (c2 = 1))
  Heap Blocks: exact=93
  ->  BitmapAnd  (cost=86.17..86.17 rows=1 width=0) (actual time=1.498..1.499 rows=0 loops=1)
        ->  Bitmap Index Scan on idx_table1_c3  (cost=0.00..2.31 rows=103 width=0) (actual time=0.019..0.019 rows=93 loops=1)
              Index Cond: (c3 = 1)
        ->  Bitmap Index Scan on idx_table1_c2  (cost=0.00..83.61 rows=9917 width=0) (actual time=1.353..1.353 rows=10098 loops=1)
              Index Cond: (c2 = 1)
Planning Time: 0.112 ms
explain analyse
select *
from table1
where c2 = 1;

Bitmap Heap Scan on table1  (cost=86.09..10193.41 rows=9917 width=40) (actual time=2.318..30.969 rows=10098 loops=1)
  Recheck Cond: (c2 = 1)
  Heap Blocks: exact=9530
  ->  Bitmap Index Scan on idx_table1_c2  (cost=0.00..83.61 rows=9917 width=0) (actual time=1.287..1.287 rows=10098 loops=1)
        Index Cond: (c2 = 1)
Planning Time: 0.095 ms
Execution Time: 31.413 ms

c1が条件に入っている場合はc1のインデックが使われています。

c1を条件から外すとc4とc3が個別にBitmap Index ScanされてからBitmapAndでなんかいい感じに処理されているっぽいです。

おわり