« アドセンスの国産版（？）のマッチスマートあっさりサービス終了 | Main | ドコモもauもいいかげんにメールアドレス設定の仕様を直せ。 »

PostgreSQLの配列データ型とGINインデックスを使って高速検索する

例えばレストランの検索サイトを思い浮かべてみよう。 「ぐるなび」とかそういうやつ。

  • 場所は必ず日比谷
  • 料理は必ずイタリアン
というふうにガッチリと検索キーを決めているユーザーは すごく少ないはずだ。 かといって単に最寄り駅名だけで検索すると 「1500件ヒットしました」とか言われてしまうのでそれでは選びようも無い。 そこで、検索条件をある程度緩めたり絞りこんだりを繰り返すことになる。
  • 場所は四谷、市ヶ谷、飯田橋、御茶ノ水、秋葉原、浅草橋 （つまりこの人は総武線沿線が便利）
  • 料理はイタリアン、フレンチ、中華（なんでもいいからおいしいもの）
みたいな感じの広めの検索条件を考えているのが 実際のユーザー像ひとつだろう。（あくまでパターンのひとつ）

一方で、レストラン情報を格納しているテーブル群は どんな構造になっているだろう？

  • 最寄り駅：都心は路線が入り乱れている。 地下鉄丸の内線の小川町とJR山手線の神田なんて目と鼻の先だ。 市ヶ谷と飯田橋の中間あたりに位置するレストランだってあるだろう。 したがってひとつのレストランに対して最寄り駅が複数設定されている。 （1対Nの関係）
  • 料理ジャンル：イタリアンと中華が同居しているレストランなんてありえないので 1レコードにひとつ（1対1）としてしまいがちだが、 「和食」と「和風居酒屋」の両方のジャンルでヒットするようにしておきたいという 気持ちもあるだろう。そこでこれも1対Nだとする。

1対Nの関係にある情報はそれぞれ別のテーブルに格納（正規化）するのが リレーショナルデータベースの基本である。 上の話を統合すると、レストラン情報を格納するテーブルは下記の3つの テーブルで構成される。

  • レストランテーブル（コレが親テーブル。1対Nの1の側）
  • 最寄り駅テーブル（子テーブル。1対NのNの側）
  • 料理ジャンルテーブル（同上）
本当は駅マスタテーブル、ジャンルマスタテーブルetcだって もちろん必要となるだろうがここでは省略。

ではこのテーブル群を、上のほうで書いたような広めの検索条件で検索してみる。 

SELECT
    レストランテーブル.レストラン名
FROM
    レストランテーブル, 最寄り駅テーブル, 料理ジャンルテーブル
WHERE
    レストランテーブル.レストランID = 最寄り駅テーブル.レストランID
    AND
    レストランテーブル.レストランID = 料理ジャンルテーブル.レストランID
    AND
    最寄り駅テーブル.駅コード IN ( 
        20,21,22,23,24 /* 20が四谷、21が市ヶ谷と思ってね */
    ) 
    AND
    料理ジャンルテーブル.ジャンルコード IN ( 
        5,6,7 /* それぞれの番号がイタリアン、フレンチ...*/
    )
IN句じゃなくてEXIST句のほうがとか、 USING句のほうがすっきりだとか、 条件によってはOR句じゃないと難しくね？とか、 イコールの右辺と左辺入れ替えたほうがどうだろう？ とかいった細かい点は目をつむっていただきたい（苦笑）。 あくまで話をわかりやすくするための例なので。

とにかく、ここで配列データ型の登場である。

  1. 教科書どおりに正規化されたこれら3つのテーブルは、 実はPostgreSQLの配列データ型を使うとひとつのテーブルに集約できる。
  2. それらのカラムには一般に使われるB-Tree形式のインデックスではなく GIN形式のインデックスを張ることができ、
  3. さらに配列関数、配列演算子を使って上記のSQL文を 記述しなおしたものを走らせると、
  4. かなり高速に検索できるようだ。

実際に試してみる。 テーブル構造はこんな感じ。 

/*
 レストラン情報テーブル(普通のリレーショナルなやつ。
 3テーブルで構成。
*/
CREATE TABLE RESTAURANT (
    REST_ID     INT4            NOT NULL, -- レストランのID（通し番号）
    NAME        VARCHAR(64)     NOT NULL  -- レストランの名前
);
-- 最寄り駅テーブル
CREATE TABLE RESTAURANT_MOYORIEKI (
    REST_ID     INT4        NOT NULL,
    EKI_ID      INT4        NOT NULL
);
-- 料理ジャンルテーブル
CREATE TABLE RESTAURANT_JANRU (
    REST_ID     INT4        NOT NULL,
    JANRU_ID    INT4        NOT NULL
);

/*
 レストラン情報テーブル（配列データ型を活用したバージョン）
 1テーブルのみで構成される。
*/
CREATE TABLE RESTAURANT2 (
    REST_ID         INT4        NOT NULL, -- レストランのID（通し番号）
    NAME            VARCHAR(64) NOT NULL, -- レストランの名前
    MOYORIEKI_ARRAY INT4[]              , -- 最寄り駅コード数値の配列データ型
    JANRU_ARRAY     INT4[]                -- ジャンルコード数値の配列データ型
);
上記のテーブルに対して次のような想定でデータをつっこんでおく。
  • レストランは10万件
  • 駅は200個
  • 料理ジャンルは10種類
  • レストラン1件あたり、最寄り駅は200個からランダムに3個。
  • レストラン1件あたり、ジャンルは10種類のうちランダムに2個。

まず普通のテーブルのほうを普通に検索してみる。 まだインデックスはなにも張ってない状態。 

testdb=> explain analyze
testdb-> select
testdb->     r.rest_id
testdb-> from
testdb->     restaurant r
testdb->     inner join restaurant_moyorieki m using(rest_id)
testdb->     inner join restaurant_janru j using(rest_id)
testdb-> where
testdb->     m.eki_id in (48,174)
testdb->     and
testdb->     j.janru_id in (4,5)
testdb-> ;
                                                                 QUERY PLAN               
--------------------------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=9096.03..12723.21 rows=1045 width=4) (actual time=296.193..406.993 rows=1257 loops=1)
   Hash Cond: (j.rest_id = r.rest_id)
   ->  Seq Scan on restaurant_janru j  (cost=0.00..3481.00 rows=36195 width=4) (actual time=0.043..84.441 rows=40084 loops=1)
         Filter: (janru_id = ANY ('{4,5}'::integer[]))
   ->  Hash  (cost=9059.93..9059.93 rows=2888 width=8) (actual time=296.103..296.103 rows=3092 loops=1)
         ->  Hash Join  (cost=3377.00..9059.93 rows=2888 width=8) (actual time=174.980..293.434 rows=3092 loops=1)
               Hash Cond: (m.rest_id = r.rest_id)
               ->  Seq Scan on restaurant_moyorieki m  (cost=0.00..5221.00 rows=2888 width=4) (actual time=0.037..94.158 rows=3092 loops=1)
                     Filter: (eki_id = ANY ('{48,174}'::integer[]))
               ->  Hash  (cost=1736.00..1736.00 rows=100000 width=4) (actual time=169.302..169.302 rows=100000 loops=1)
                     ->  Seq Scan on restaurant r  (cost=0.00..1736.00 rows=100000 width=4) (actual time=0.024..81.049 rows=100000 loops=1)
 Total runtime: 407.983 ms
(12 rows)
400ミリ秒ほどかかる。

次に配列データ型をつかって作ったテーブルのほうを数字だけ変えた条件で。 

testdb=> explain analyze
testdb-> select
testdb->     r2.rest_id
testdb-> from
testdb->     restaurant2 r2
testdb-> where
testdb->     r2.moyorieki_array && array[43,125]
testdb->     and
testdb->     r2.janru_array && array[3,4]
testdb-> ;
                                                  QUERY PLAN                              
---------------------------------------------------------------------------------------------------------------
 Seq Scan on restaurant2 r2  (cost=0.00..3088.00 rows=2 width=4) (actual time=0.256..69.804 rows=1156 loops=1)
   Filter: ((moyorieki_array && '{43,125}'::integer[]) AND (janru_array && '{3,4}'::integer[]))
 Total runtime: 70.400 ms
(3 rows)
70ミリ秒。インデックス張ってなくてもこの性能。 テーブル間のJOIN（結合）が無いから効率がよいのは当然だが。

次に、それぞれインデックスを張ってみる。こんな感じ。 

/*
 普通のリレーショナルなやつ用。
*/
DROP INDEX IF EXISTS I_RESTAURANT_ID;
DROP INDEX IF EXISTS I_REST_ID_MOYORIEKI;
DROP INDEX IF EXISTS I_EKI_ID_MOYORIEKI;
DROP INDEX IF EXISTS I_REST_ID_JANRU;
DROP INDEX IF EXISTS I_JANRU_ID_JANRU;

CREATE INDEX I_RESTAURANT_ID        ON RESTAURANT (REST_ID);
CREATE INDEX I_REST_ID_MOYORIEKI    ON RESTAURANT_MOYORIEKI (REST_ID);
CREATE INDEX I_EKI_ID_MOYORIEKI     ON RESTAURANT_MOYORIEKI (EKI_ID);
CREATE INDEX I_REST_ID_JANRU        ON RESTAURANT_JANRU (REST_ID);
CREATE INDEX I_JANRU_ID_JANRU       ON RESTAURANT_JANRU (JANRU_ID);

/*
 配列型のテーブル用。まずはこっちも普通に(Btreeで）はる。
*/
DROP INDEX IF EXISTS I_RESTAURANT_ID_2;
DROP INDEX IF EXISTS I_MOYORIEKI_ARRAY;
DROP INDEX IF EXISTS I_JANRU_ARRAY;

CREATE INDEX I_RESTAURANT_ID_2  ON RESTAURANT2 (REST_ID);
CREATE INDEX I_MOYORIEKI_ARRAY  ON RESTAURANT2 (MOYORIEKI_ARRAY);
CREATE INDEX I_JANRU_ARRAY      ON RESTAURANT2 (JANRU_ARRAY);
これでさっきと同じ検索をする。

まずは普通のテーブルのほう。 

testdb=> explain analyze
testdb-> select
testdb->     r.rest_id
testdb-> from
testdb->     restaurant r
testdb->     inner join restaurant_moyorieki m using(rest_id)
testdb->     inner join restaurant_janru j using(rest_id)
testdb-> where
testdb->     m.eki_id in (48,174)
testdb->     and
testdb->     j.janru_id in (4,5)
testdb-> ;
                                                                          QUERY PLAN      
--------------------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=5764.08..7343.70 rows=1045 width=4) (actual time=187.404..244.678 rows=1257 loops=1)
   Hash Cond: (j.rest_id = r.rest_id)
   ->  Bitmap Heap Scan on restaurant_janru j  (cost=577.02..2010.46 rows=36195 width=4) (actual time=9.544..38.947 rows=40084 loops=1)
         Recheck Cond: (janru_id = ANY ('{4,5}'::integer[]))
         ->  Bitmap Index Scan on i_janru_id_janru  (cost=0.00..567.97 rows=36195 width=0) (actual time=9.238..9.238 rows=40084 loops=1)
               Index Cond: (janru_id = ANY ('{4,5}'::integer[]))
   ->  Hash  (cost=5150.96..5150.96 rows=2888 width=8) (actual time=177.794..177.794 rows=3092 loops=1)
         ->  Merge Join  (cost=1734.38..5150.96 rows=2888 width=8) (actual time=23.220..174.715 rows=3092 loops=1)
               Merge Cond: (r.rest_id = m.rest_id)
               ->  Index Scan using i_restaurant_id on restaurant r  (cost=0.00..3123.26 rows=100000 width=4) (actual time=13.071..99.232 rows=99997 loops=1)
               ->  Sort  (cost=1734.38..1741.60 rows=2888 width=4) (actual time=10.124..11.872 rows=3092 loops=1)
                     Sort Key: m.rest_id
                     ->  Bitmap Heap Scan on restaurant_moyorieki m  (cost=54.91..1568.38 rows=2888 width=4) (actual time=1.477..7.925 rows=3092 loops=1)
                           Recheck Cond: (eki_id = ANY ('{48,174}'::integer[]))
                           ->  Bitmap Index Scan on i_eki_id_moyorieki  (cost=0.00..54.19 rows=2888 width=0) (actual time=1.095..1.095 rows=3092 loops=1)
                                 Index Cond: (eki_id = ANY ('{48,174}'::integer[]))
 Total runtime: 245.447 ms
(17 rows)
インデックススキャンが走るようになり、速度も幾分速くなった。

次に配列データ型を使ったテーブルのほう。 

testdb=> explain analyze
testdb-> select
testdb->     r2.rest_id
testdb-> from
testdb->     restaurant2 r2
testdb-> where
testdb->     r2.moyorieki_array && array[31,159]
testdb->     and
testdb->     r2.janru_array && array[2,4]
testdb-> ;
                                                  QUERY PLAN                              
---------------------------------------------------------------------------------------------------------------
 Seq Scan on restaurant2 r2  (cost=0.00..3088.00 rows=2 width=4) (actual time=0.108..67.081 rows=1166 loops=1)
   Filter: ((moyorieki_array && '{31,159}'::integer[]) AND (janru_array && '{2,4}'::integer[]))
 Total runtime: 67.732 ms
(3 rows)
インデックスは確かに張ってあるのだが、使われない。したがって速度もさっきと変わらない。 この原因については詳しくは調べていないが、 配列データ型とB-Treeインデックスとの組み合わせの向き不向きかなあ。 検索条件の与え方でももちろん変わってくるかもしれないが。

そこで、さっきのB-Treeインデックスを削除して、GINインデックスで新たに張りなおしてみる。 

DROP INDEX IF EXISTS I_MOYORIEKI_ARRAY;
DROP INDEX IF EXISTS I_JANRU_ARRAY;
CREATE INDEX I_MOYORIEKI_ARRAY  ON RESTAURANT2 USING GIN (MOYORIEKI_ARRAY);
CREATE INDEX I_JANRU_ARRAY      ON RESTAURANT2 USING GIN (JANRU_ARRAY);
これで、さきほどのSELECT文を値だけ変えて流してみる。 
testdb=> explain analyze
testdb-> select
testdb->     r2.rest_id
testdb-> from
testdb->     restaurant2 r2
testdb-> where
testdb->     r2.moyorieki_array && array[67,101]
testdb->     and
testdb->     r2.janru_array && array[5,6]
testdb-> ;
                                                              QUERY PLAN                  
--------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on restaurant2 r2  (cost=28.28..36.10 rows=2 width=4) (actual time=15.790..18.862 rows=1059 loops=1)
   Recheck Cond: ((janru_array && '{5,6}'::integer[]) AND (moyorieki_array && '{67,101}'::integer[]))
   ->  BitmapAnd  (cost=28.28..28.28 rows=2 width=0) (actual time=15.555..15.555 rows=0 loops=1)
         ->  Bitmap Index Scan on i_janru_array  (cost=0.00..8.01 rows=500 width=0) (actual time=13.643..13.643 rows=37819 loops=1)
               Index Cond: (janru_array && '{5,6}'::integer[])
         ->  Bitmap Index Scan on i_moyorieki_array  (cost=0.00..20.02 rows=500 width=0) (actual time=1.440..1.440 rows=2933 loops=1)
               Index Cond: (moyorieki_array && '{67,101}'::integer[])
 Total runtime: 19.479 ms
(8 rows)
かなりのスピードＵＰ。

以下は、ランダムな検索条件を与えながら100回ほどSELECTし、 その処理速度の90%tileで平均値を取った結果である。

  普通のリレーショナルなテーブル構造 ＋ B-Treeインデックス 配列データ型を使ったテーブル ＋ GINインデックス
処理スピード平均(ms) 279 38
ざっと7倍速いという結果になった。 なお、普通のテーブルへの検索結果と配列データ型を使ったテーブルへの検索結果に 違いが発生してないかを調べるため、レストランID(REST_ID)だけをDISTINCTで 重複の無いように出力させ、とりあえずその数を照らし合わせた。 100回のテストで食い違いは発生していなかった。

see also:

そういえばここ一週間くらい*.postgresql.jpのサーバが全て死んでて困る。

2007年11月17日 Comments [1] | Trackbacks [0]

トラックバックURL

このエントリーのトラックバックURL:
http://www.ywcafe.net/mt/mt-tb.cgi/791

コメント

とても参考になりました
普通のリレーションで検索した場合と、同一テーブル内の配列カラムにして検索した場合との処理時間差を、エントリ数毎に比べてみたいです
例えば、
・レストランが1万件あるときと5000万件のときと比べてどうか
・ジャンル、最寄駅が1万件あるときと5000万件のときと比べてどうか
・その組合せ
等々
です

Posted by おざき at 2007年11月20日

コメントする

(初めてのコメントの時は、コメントが表示されるためにこのブログのオーナーの承認が必要になることがあります。承認されるまでコメントは表示されませんのでしばらくお待ちください)


画像の中に見える文字を入力してください。