単一インデックスの組合せ機能と、複数列インデックスの速度の違いを計測してみる

Postgreで単一インデックスでの組合せ機能というものがあることを知りました。

https://www.postgresql.jp/document/12/html/indexes-bitmap-scans.html

幸いにも、PostgreSQLは、単一のインデックススキャンでは実装できない場合を扱うために、複数のインデックス（同じインデックスの複数回使用を含む）を組み合わせる機能を持ちます。 システムは複数のインデックススキャンを跨がる、AND条件およびOR条件を形成できます。

疑問： 単一インデックスの組合せ機能と、複数列インデックスってどっちが早いの？

たとえば、以下のようなお店が扱う商品コードとその値段を管理するテーブルを作ります。

CREATE TABLE shop_item1
(
    shop_id TEXT    NOT NULL, -- お店コード
    item_id TEXT    NOT NULL, -- 商品コード
    price   INTEGER NOT NULL  -- 値段
);

このテーブルは、shop_idとitem_idで絞り込む（一意制約をいま付けてないけど）ことができて、
かつ、あるお店が持っている商品コードを一覧として出したい。
または、ある商品コードがどんなお店で、どんな値段で売っているかを一覧として出したい。

そういった3つの検索パターンがあると考えた時に、以下のような疑問が出てきました。

• shop_id、item_idでそれぞれ単一インデックスを貼るのと、(shop_id, item_id) で複数列インデックスを貼った場合、どちらが良いのか

上記であげたインデックスに関するマニュアルでは、以下のような記述が。

両方の列を含む問い合わせでは、通常このインデックスの方がインデックスの組み合わせよりも効率的です。 しかし、11.3で説明した通り、yのみを含む問い合わせではほとんど意味がありません。 従って、このインデックスのみとすることはできません。 複数列インデックスとyに対する別のインデックスの組み合わせがかなりよく役に立ちます。 xのみを含む問い合わせでは、複数列インデックスを使用することができます。 しかし、これはより大きくなりますので、x のみインデックスよりも低速になります。 最後の別方法は、3つのインデックスすべてを作成することです。 しかしこれはおそらく、テーブルの検索頻度が更新頻度よりもかなり高く、3種類の問い合わせすべてが良く使用される場合のみ合理的です。 問い合わせの中の1つの頻度が他よりも少なければ、おそらく良く使用される種類にもっとも合うように2つだけインデックスを作成した方がよいでしょう。

xとy、上記のテーブル例で言うと、shop_idとitem_idですね。
3つの検索パターンを考えたときに、shop_idとitem_idの単一インデックスと、(shop_id, item_id)の複数列インデックスを全部用意する方法もあるよ、とは言っていますが、

• (shop_id, item_id)と item_idの単一インデックスの組合せ
• shop_id、item_idの単一インデックスだけ用意して、AND検索は、postgreの単一インデックスを組み合わせる機能を利用する

これらも有用であるとのこと。
実際に、どれだけ違うのかを確かめてみたくなったので、実験をしてみます。

結論だけ見たい方は、結果へどうぞ。

実験

• 実験協力：mohiraさん

実行環境

• postgres (PostgreSQL) 11.9 (Debian 11.9-1.pgdg90+1)
• Docker version 19.03.13

やり方

インデックスの貼り方を変えた、合計8パターンのテーブルを準備。
そのあと、以下の3パターンのクエリを投げてみて、結果が返ってくる時間を計測する。

計測方法は、 \timing onメタコマンドを使用する。

-- その1
SELECT * FROM shop_item1 where shop_id='shop#1' and item_id='item#1';

-- その2
SELECT * FROM shop_item1 where shop_id='shop#1';
-- その3
SELECT * FROM shop_item1 where item_id='item#1';

実験テーブル一覧

テーブル名	shop_index	item_index	(shop_index, item_index)	where shop_id='shop#1'	where item_id='item#1'	where shop_id='#shop1' and item_id='#item1'
shop_item1	x	x	x
shop_item2	x	x	o
shop_item3	x	o	x
shop_item4	x	o	o
shop_item5	o	x	x
shop_item6	o	x	o
shop_item7	o	o	x
shop_item8	o	o	o

テーブル準備するSQL

1番目: shop_idなし-item_idなし-(shop_id, item_id)なし

CREATE TABLE shop_item1
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

2番目: shop_idなし-item_idなし-(shop_id, item_id)あり

CREATE TABLE shop_item2
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table2_shop_and_item_idx ON shop_item2 (shop_id, item_id);

3番目: shop_idなし-item_idあり-(shop_id, item_id)なし

CREATE TABLE shop_item3
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table3_item_idx ON shop_item3 (item_id);

4番目: shop_idなし-item_idあり-(shop_id, item_id)あり

CREATE TABLE shop_item4
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table4_item_idx ON shop_item4 (item_id);
CREATE INDEX table4_shop_and_item_idx ON shop_item4 (shop_id, item_id);

5番目： shop_idあり-item_idなし-(shop_id, item_id)なし

CREATE TABLE shop_item5
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table5_shop_idx ON shop_item5 (shop_id);

6番目: shop_idあり-item_idなし-(shop_id, item_id)あり

CREATE TABLE shop_item6
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table6_shop_idx ON shop_item6 (shop_id);
CREATE INDEX table6_shop_and_item_idx ON shop_item6 (shop_id, item_id);

7番目: shop_idあり-item_idあり-(shop_id, item_id)なし

CREATE TABLE shop_item7
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table7_shop_idx ON shop_item7 (shop_id);
CREATE INDEX table7_item_idx ON shop_item7 (item_id);

8番目: shop_idあり-item_idあり-(shop_id, item_id)あり

CREATE TABLE shop_item8
(
    shop_id TEXT    NOT NULL,
    item_id TEXT    NOT NULL,
    price   INTEGER NOT NULL
);

CREATE INDEX table8_shop_idx ON shop_item8 (shop_id);
CREATE INDEX table8_item_idx ON shop_item8 (item_id);
CREATE INDEX table8_shop_and_item_idx ON shop_item8 (shop_id, item_id);

データ投入

• ひとまず100万件用意する

INSERT INTO shop_item1 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item2 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item3 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item4 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item5 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item6 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item7 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

INSERT INTO shop_item8 (shop_id, item_id, price)
SELECT 'shop#' || x.n
     , 'item#' || x.n
     , 50000 + floor(random() * 20)::integer
FROM generate_series(1, 1000000) x(n);

検証用スクリプト

calculate.sql

\o /dev/null

SELECT 'shop_item1 shop_idなし-item_idなし-(shop_id, item_id)なし'; \p \timing on
SELECT * FROM shop_item1 where shop_id='shop#1';
SELECT * FROM shop_item1 where item_id='item#1';
SELECT * FROM shop_item1 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item2 shop_idなし-item_idなし-(shop_id, item_id)あり'; \p \timing on
SELECT * FROM shop_item2 where shop_id='shop#1';
SELECT * FROM shop_item2 where item_id='item#1';
SELECT * FROM shop_item2 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item3 shop_idなし-item_idあり-(shop_id, item_id)なし'; \p \timing on
SELECT * FROM shop_item3 where shop_id='shop#1';
SELECT * FROM shop_item3 where item_id='item#1';
SELECT * FROM shop_item3 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item4 shop_idなし-item_idあり-(shop_id, item_id)あり'; \p \timing on
SELECT * FROM shop_item4 where shop_id='shop#1';
SELECT * FROM shop_item4 where item_id='item#1';
SELECT * FROM shop_item4 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item5 shop_idあり-item_idなし-(shop_id, item_id)なし'; \p \timing on
SELECT * FROM shop_item5 where shop_id='shop#1';
SELECT * FROM shop_item5 where item_id='item#1';
SELECT * FROM shop_item5 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item6 shop_idあり-item_idなし-(shop_id, item_id)あり'; \p \timing on
SELECT * FROM shop_item6 where shop_id='shop#1';
SELECT * FROM shop_item6 where item_id='item#1';
SELECT * FROM shop_item6 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item7 shop_idあり-item_idあり-(shop_id, item_id)なし'; \p \timing on
SELECT * FROM shop_item7 where shop_id='shop#1';
SELECT * FROM shop_item7 where item_id='item#1';
SELECT * FROM shop_item7 where shop_id='shop#1' and item_id='item#1';
\timing off


SELECT 'shop_item8 shop_idあり-item_idあり-(shop_id, item_id)あり'; \p \timing on
SELECT * FROM shop_item8 where shop_id='shop#1';
SELECT * FROM shop_item8 where item_id='item#1';
SELECT * FROM shop_item8 where shop_id='shop#1' and item_id='item#1';
\timing off

実行

psql -U <User名> <DataBase名> < calculate.sql | grep -v Timing > result

結果

• 単位は、マイクロ秒で合わせています

テーブル名	shop_index	item_index	(shop_index, item_index)	where shop_id='shop#1'	where item_id='item#1'	where shop_id='#shop1' and item_id='#item1'
shop_item1	x	x	x	66000	64000	72000
shop_item2	x	x	o	500	64000	500
shop_item3	x	o	x	64000	400	400
shop_item4	x	o	o	700	400	400
shop_item5	o	x	x	700	73000	600
shop_item6	o	x	o	500	63000	500
shop_item7	o	o	x	300	200	200
shop_item8	o	o	o	400	200	400

結論

見た感じ、各単一インデックスと、複合列インデックスを用意したパターンでそこまで大きな違いは無いように見えます（むしろ複合列でのAND検索が、shop_item7の方が早いけど、これは誤差だと思われます）。

結局の所、どういうクエリパターンを使うかによるとは思われますが、単一インデックスでも十分賄えそうな感じがしています。

今回は試してないですが、

• INSERTの時間
  • インデックス貼っているとインサートは遅くなるが、どんな組合せのインデックスの場合で顕著に遅くなるのだろうか
• index を (item_id, shop_id) にしたときにどうなるか
• index を (shop_id, item_id)と(item_id, shop_id) どちらも貼ったときにどうなるか

などなどが気になってきました。また時間がある時に試してみようかと思います。