2012年4月11日水曜日

GIN を利用したタグ検索の最適化

こんにちは、OSS テクノロジーセンターの渡辺です。

今回は PostgreSQL の配列型と GIN インデックスを使用したタグシステムについて解説します。

はじめに

データにタグを付けて分類するシステムは多くあります。タグはデータ分類を行う為によく利用される仕組みで、様々なアプリケーションに利用されています。

タグを使ったシステムの特徴

  1. タグの名前が自由に登録できる
  2. 一つのデータに対して、タグを任意の数、設定できる
  3. 任意のタグ名を任意の数、指定して検索できる

タグはデータを分類する仕組みとして柔軟で便利な仕組みですが、検索する場合のコストが大きくパフォーマンスがあまりよくありません。タグシステムは、MongoDB などのドキュメント指向のデータベース NoSQL と比べると、RDBMS と相性が良いと言えません。この事は、NoSQL が多くの Web サービスで利用される理由の一つになっています。

PostgreSQL 場合、PostgreSQL 独自の配列型と GIN (Generalized Inverted Index) インデックスを利用し、他の RDBMS とは比較にならないほど効率的なタグシステムを構築できます。GIN インデックスは全文検索「専用」のインデックスと理解されている方も多いと思います。しかし、GIN インデックスは名前の通り「汎用」の転置インデックスです。この記事では、配列型と GIN インデックスを利用したタグ検索の効率化を紹介します。タグを利用したシステムとしてブログ型のアプリケーションを想定してベンチマークを行います。ブログシステムとしては、比較的大きめの 1000 万件の記事と 4000 万件のタグ情報を利用し、実行時間の違いを検証します。

今回の記事執筆に利用した環境

  • Linux 2.6.35 x86_64
  • PostgreSQL 9.1.3
  • PHP 5.4.0 (テストデータ作成)

デフォルトの PostgreSQL 設定では遅すぎるので、バッファを 1GB に増やすなど、多少設定もチューニングしています。9.1.3 のデフォルトからの変更箇所と設定値は最後の「参照」をご覧下さい。

配列型

PostgreSQL は様々なデータ型を容易に追加できる仕組みになっています。この為、PostgreSQL には Point 型、Circle 型、Polygon 型などの幾何学的なデータ型や、ネットワークアドレス型などのデータ型をサポートしています。データ型を配列として扱える配列型も、他の RDBMS にはあまり見られない独特なデータ型と言えます。まず、配列型の利用方法を紹介します。

配列型はデータ型の後に[]を付ける事により作成できます。PostgreSQL のデータ型であれば、どのデータ型であっても配列にできます。

CREATE TABLE sal_emp (
    name            text,
    pay_by_quarter  integer[],
    schedule        text[][]
);

pay_by_quarter は整数型の 1 次元の配列、schedule はテキスト型の 2 次元配列として定義されます。配列型のコラムにデータは、'{“data1”, “data2”}' の形式で挿入します。

INSERT INTO sal_emp
    VALUES ('Bill',
    '{10000, 10000, 10000, 10000}',
    '{{"meeting", "lunch"}, {"training", "presentation"}}');

INSERT INTO sal_emp
    VALUES ('Carol',
    '{20000, 25000, 25000, 25000}',
    '{{"breakfast", "consulting"}, {"meeting", "lunch"}}');

このテーブルを SELECT すると以下のようになります。

username@127 ~=# SELECT * FROM sal_emp;
 name  |      pay_by_quarter       |                 schedule                  
-------+---------------------------+-------------------------------------------
 Bill  | {10000,10000,10000,10000} | {{meeting,lunch},{training,presentation}}
 Carol | {20000,25000,25000,25000} | {{breakfast,consulting},{meeting,lunch}}
(2 rows)

配列型は、任意の数のデータをフィールドに保存したい場合に便利な機能です。データに任意数のタグを付ける場合に、適当なデータ型と言えます。
PostgreSQL は配列用に演算子と関数を用意しています。これらの演算子と関数の詳しい説明は PostgreSQL9.1 マニュアルを参照してください。配列型は最初の PostgreSQL からサポートされている機能です。NULL 要素、包含演算子などのサポートは最近追加されていますが、ほとんどの機能は古い PostgreSQL でも利用できます。

配列演算子
演算子 説明 結果
= 等しい ARRAY[1.1,2.1,3.1]::int[] = ARRAY[1,2,3] t
<> 等しくない ARRAY[1,2,3] <> ARRAY[1,2,4] t
< 未満 ARRAY[1,2,3] < ARRAY[1,2,4] t
> より大きい ARRAY[1,4,3] > ARRAY[1,2,4] t
<= 以下 ARRAY[1,2,3] <= ARRAY[1,2,3] t
>= 以上 ARRAY[1,4,3] >= ARRAY[1,4,3] t
@> 包含する ARRAY[1,4,3] @> ARRAY[3,1] t
<@ …により包含される ARRAY[2,7] <@ ARRAY[1,7,4,2,6] t
&& 重複する(共通要素を持つ) ARRAY[1,4,3] && ARRAY[2,1] t
|| 配列と配列を連結 ARRAY[1,2,3] || ARRAY[4,5,6] {1,2,3,4,5,6}
|| 配列と配列を連結 ARRAY[1,2,3] || ARRAY[[4,5,6],[7,8,9]] {{1,2,3},{4,5,6},{7,8,9}}
|| 要素と配列を連結 3 || ARRAY[4,5,6] {3,4,5,6}
|| 配列と要素を連結 ARRAY[4,5,6] || 7 {4,5,6,7}

配列関数
関数 戻り値型 説明 結果
array_append(anyarray, anyelement) anyarray 配列の末尾に要素を追加 array_append(ARRAY[1,2], 3) {1,2,3}
array_cat(anyarray, anyarray) anyarray 2 つの配列を連結 array_cat(ARRAY[1,2,3], ARRAY[4,5]) {1,2,3,4,5}
array_ndims(anyarray) int その配列の次数を返す array_ndims(ARRAY[[1,2,3], [4,5,6]]) 2
array_dims(anyarray) text 配列の次数をテキスト表現で返す array_dims(ARRAY[[1,2,3], [4,5,6]]) [1:2][1:3]
array_fill(anyelement, int[], [, int[]]) anyarray 提供された値と次数で初期化された配列を返す。1 以外の下限を持たせることもできます array_fill(7, ARRAY[3], ARRAY[2]) [2:4]={7,7,7}
array_length(anyarray, int) int 入力された配列次元の長さを返す array_length(array[1,2,3], 1) 3
array_lower(anyarray, int) int 配列次元の下限を返す array_lower('[0:2]={1,2,3}'::int[], 1) 0
array_prepend(anyelement, anyarray) anyarray 配列の先頭に要素を追加 array_prepend(1, ARRAY[2,3]) {1,2,3}
array_to_string(anyarray, text [, text]) text 配列の要素を提供された区切り文字かオプショナルな NULL 文字を使用して連結 array_to_string(ARRAY[1, 2, 3, NULL, 5], ',', '*') 1,2,3,*,5
array_upper(anyarray, int) int 入力された配列の次元の上限を返す array_upper(ARRAY[1,8,3,7], 1) 4
string_to_array(text, text [, text]) text[] 提供された区切り文字、およびオプショナルな NULL 文字を使用して、文字列を配列の要素に分割 string_to_array('xx~^~yy~^~zz', '~^~', 'yy') {xx,NULL,zz}
unnest(anyarray) setof anyelement 配列を行集合に展開 unnest(ARRAY[1,2]) 1
2
(2 rows)

GIN インデックス

GIN はインデックスの一種で、主に全文検索を行う場合に利用するインデックスです。GIN とは汎用転置インデックス (Generalized Inverted Index) の事です。主にインデックス対象が複合型であり、インデックスにより取り扱われる問い合わせが、複合型の項目内に存在する要素値に対し、検索できるように設計されています。言葉で説明すると難しく感じますが、図にすると簡単です。

図 :  転置インデックス(Inverted Index)の構造

図「転置インデックス (Inverted Index) の構造」のように、単語と単語を含む文書 ID が対となって保存されるのが、転置インデックスです。インデックスされるデータとインデックスの構造が、通常のインデックスとは反転 (逆引き) しているので「転置インデックス」と呼ばれています。
この図からも分かるように、特定のタグを含むレコードを検索するために GIN を利用すると、テキストの全文検索と同様に高速化が期待できる事がわかります。実際、GIN インデックスの特徴を利用すると、PostgreSQL の配列型のデータ検索を大幅に高速化できます。
GIN インデックスは PostgeSQL 8.3 から利用できる機能です。今回、利用しているシステムは PostgreSQL 9.1 ですが、8.3 以降であれば同様の仕組みを構築できます。

一般的なタグシステムの実装

ブログアプリを例に、タグを使ったシステムを解説します。ブログシステムの記事には、記述されている内容が分かるようにタグが付けれるようになっている物が一般的です。例えば、この記事のようなブログ記事の場合、以下のようなタグを付けます。

  • PostgreSQL
  • GIN
  • 配列
  • パフォーマンスチューニング
  • 検索
  • ベンチマーク

記事とタグは MN 関係であるので、テーブル設計は次の様になります。

検証用のデータベースのテーブル定義には次の定義を利用しました。

CREATE TABLE article (
  id   SERIAL PRIMARY KEY,
  title  TEXT NOT NULL,
  article  TEXT NOT NULL
);

CREATE TABLE tag (
  id   SERIAL PRIMARY KEY,
  name   TEXT NOT NULL
);

CREATE TABLE article_tag (
  id   SERIAL PRIMARY KEY,
  aid   INT REFERENCES article(id),
  tid   INT REFERENCES tag(id)
);

今回は GIN インデックスを利用するので article_tag テーブルの aid, tid には INT 型を利用しました。INT8 型などを指定した場合、明示的な型変換が必要となります。今回は分り易くするために型変換の必要がない INT 型を利用します。

GIN と配列を使用した実装

GIN と配列を利用した場合、タグ情報は article テーブルのコラムに配列として保存します。その配列型コラムに対して GIN インデックスを適用します。テーブル設計は次のようになります。

GIN を利用する場合、article テーブルと tag テーブルの関係はインデックス自体に保存されるので関係を保存するテーブルは必要なくなります。テーブル定義は以下のようになります。
CREATE TABLE article2 (
  id   SERIAL PRIMARY KEY,
  title  TEXT NOT NULL,
  article  TEXT NOT NULL,
  tids   INT[]
);

CREATE TABLE tag (
  id   SERIAL PRIMARY KEY,
  name   TEXT NOT NULL
);

インデックスの定義は GIN を利用し、次のように定義します。article2 テーブル用に tag テーブルを別に作る意味が無いので、今回のテストでは作成していません。

CREATE INDEX tag_idx ON article2 USING GIN (tids);

テストデータの準備

テーブル定義は出来たので、テスト用のデータを用意します。筆者は PHP 5.4.0 を利用しましたが、データ準備用のスクリプトは PHP 5.3 でも動作するはずです。データ数は以下のように設定しました。

  • article : 1000 万件 (1000 万レコード)
  • tag : 300 件 (300 レコード)
  • タグ : 1 article に対して 4 つ (4000 万レコード)

データ準備に利用したスクリプト (SIOS-prepare-data.php)

<?php
$pgport = 5491;
$pghost = '127.0.0.1';
$pguser = username;

$num_tags = 300;
$num_articles = 10000000;

$db = pg_connect("host=$pghost port=$pgport user=$pguser");

// クリーンナップ
pg_query($db, "DROP TABLE article_tag;");
pg_query($db, "DROP TABLE article;");
pg_query($db, "DROP TABLE tag;");
pg_query($db, "DROP TABLE article2;");
//pg_query($db, "DROP SEQUENCE article_id_seq CASCADE;");
//pg_query($db, "DROP SEQUENCE article_tag_id_seq CASCADE;");
//pg_query($db, "DROP SEQUENCE article2_id_seq CASCADE;");

// テーブル作成
$sql = '
CREATE TABLE article (
 id SERIAL PRIMARY KEY,
 title TEXT NOT NULL,
 article TEXT NOT NULL
);

CREATE TABLE tag (
 id SERIAL PRIMARY KEY,
 name TEXT NOT NULL
);

CREATE TABLE article_tag (
 id SERIAL PRIMARY KEY,
 aid INT REFERENCES article(id),
 tid INT REFERENCES tag(id)
);

CREATE TABLE article2 (
 id SERIAL PRIMARY KEY,
 title TEXT NOT NULL,
 article TEXT NOT NULL,
 tids INT[]
);
';
pg_query($db, $sql);

// tagテーブルにダミータグを挿入
pg_prepare('tag', 'INSERT INTO tag (name) VALUES ($1)') or die('Failed to prepare. '. __LINE__. PHP_EOL);
echo 'Inserting tags', PHP_EOL;
for($i=0; $i < $num_tags; $i++) {
 pg_execute($db, 'tag', array(substr(md5(uniqid()), 0, 5)));
}

// articleテーブルにダミーデータを挿入
pg_prepare('article', 'INSERT INTO article (title, article) VALUES ($1, $2)') or die('Failed to prepare. '.  __LINE__. PHP_EOL);
echo "Inserting article", PHP_EOL;
for ($i=0; $i < $num_articles; $i++) {
 pg_execute($db, 'article', array(md5(uniqid()), md5(uniqid())));
 if (!($i % 10000)) echo '.';
}
echo PHP_EOL;

// article_tagテーブルに4つづつのタグを設定
pg_prepare('article_tag', 'INSERT INTO article_tag (aid, tid) VALUES ($1, $2)') or die('Failed to prepare. '. __LINE__. PHP_EOL);
echo "Inserting article_tag", PHP_EOL;
for ($i=1; $i <= $num_articles; $i++) {
 for($j=0; $j < 4; $j++) {
  pg_execute($db, 'article_tag', array($i, mt_rand(1, $num_tags)));
 }
 if (!($i % 10000)) echo '.';
}
echo PHP_EOL;

// article2テーブルにダミーデータを挿入
pg_prepare('article2', 'INSERT INTO article2 (title, article, tids) VALUES ($1, $2, $3)') or die('Failed to prepare. '. __LINE__. PHP_EOL);
echo "Inserting article2", PHP_EOL;
for ($i=0; $i < $num_articles; $i++) {
 $tids = '{'.mt_rand(1, $num_tags).','.mt_rand(1, $num_tags).','.mt_rand(1, $num_tags).','.mt_rand(1, $num_tags).'}';
    pg_execute($db, 'article2', array(md5(uniqid()), md5(uniqid()), $tids));
 if (!($i % 10000)) echo '.';
}
echo PHP_EOL;

スクリプト実行後のテーブルは以下のようになります。

username@[local] ~=# select * from article limit 1;
 id |              title               |             article              
----+----------------------------------+----------------------------------
  1 | 91f7bb5c1891a8a6850c67268c317430 | 6876259598b1314ff43d66f192446e6f
(1 行)

時間: 58.639 ms
username@[local] ~=# select * from tag limit 1;
 id | name  
----+-------
  1 | 52bdc
(1 行)

時間: 0.869 ms
username@[local] ~=# select * from article2 limit 1;
 id |              title               |             article              |      tids      
----+----------------------------------+----------------------------------+----------------
  1 | b063ac07bce25d0e645fa79558aee285 | 69f4c548b5de4bb5eabe0c65a75b54d0 | {59,29,56,183}
(1 行)

時間: 0.872 ms

データベースは pgdata-9.1 ディレクトリに保存しています。この状態でテストデータベースの大きさは 5.8GB でした。

[username@dev ~]$ du -h pgdata-9.1/
12K pgdata-9.1/pg_notify
4.0K pgdata-9.1/pg_tblspc
4.0K pgdata-9.1/pg_serial
4.0K pgdata-9.1/pg_twophase
32K pgdata-9.1/pg_stat_tmp
15M pgdata-9.1/pg_clog
4.0K pgdata-9.1/base/pgsql_tmp
5.7G pgdata-9.1/base/16384
6.1M pgdata-9.1/base/12780
6.0M pgdata-9.1/base/1
6.0M pgdata-9.1/base/12772
5.7G pgdata-9.1/base
76K pgdata-9.1/pg_subtrans
288K pgdata-9.1/global
12K pgdata-9.1/pg_multixact/offsets
12K pgdata-9.1/pg_multixact/members
28K pgdata-9.1/pg_multixact
4.0K pgdata-9.1/pg_xlog/archive_status
129M pgdata-9.1/pg_xlog
5.8G pgdata-9.1/

ベンチマーク

データを準備した段階ではインデックスがありません。まず、この状態で EXPLAIN ANALYZE を使用して実行時間を計測します。

今回は、テーブル構成の違いによる速度の違いを確認する事が目的なので、tag テーブルとのジョインは行わないで検索します。タグ付けしたデータを検索する場合、指定した全てのタグが含まれるレコードを抽出する事が多いです。通常のテーブルの場合、INTERSECT を使いタグを含む記事の ID を取り出します。

SELECT a.id FROM article AS a, article_tag AS t WHERE t.tids = XX
INTERSECT
SELECT a.id FROM article AS a, article_tag AS t WHERE t.tids = YY;

INTERSECT の代わりに UNION と使うと、いずれかのタグを含むレコードを検索できます。明示的な JOIN を利用するなど、チューニングが考えられますが、今回は解りやすさを優先して特にチューニングは考えません。
配列を使ったテーブルの場合、配列型として保存されている tids コラムを検索、タグを含む記事の ID を抽出します。ANY() は配列中の任意の要素に値が含まれる場合に真と評価されます。ANY() を利用すると通常のテーブルと似たような形式で、必要なレコードを抽出できます。

SELECT a.id FROM article2 AS a WHERE
  XX = ANY(tids)
  AND
  YY = ANY(tids);

AND の代わりに OR を使うと、いずれかのタグを含むレコードを検索できます。

ベンチマークを行う場合、データば既にキャッシュ済みの場合とキャッシュ済みでない場合の違いは非常に大きいです。今回は一回以上クエリを実行し、キャッシュ済みの実行結果を掲載します。

インデックスが無い場合のパフォーマンス

  • 通常のテーブル
  •  username@[local] ~=# EXPLAIN ANALYZE SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 3 INTERSECT SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 6 INTERSECT SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 22;
                                                       QUERY PLAN                                     
    ------------------------------------------------------------------------------------------------------------------------------------
    HashSetOp Intersect  (cost=710729.27..3314246.56 rows=128604 width=4) (actual time=132662.079..132662.390 rows=8 loops=1)
       ->  Append  (cost=710729.27..3313603.54 rows=257208 width=4) (actual time=88008.356..132614.957 rows=134025 loops=1)
             ->  Result  (cost=710729.27..2209283.37 rows=128604 width=4) (actual time=88008.354..88019.451 rows=1407 loops=1)
                   ->  HashSetOp Intersect  (cost=710729.27..2209283.37 rows=128604 width=4) (actual time=88008.353..88019.092 rows=1407 loops=1)
                         ->  Append  (cost=710729.27..2208640.35 rows=257208 width=4) (actual time=22631.841..87840.528 rows=266083 loops=1)
                               ->  Subquery Scan on "*SELECT* 1"  (cost=710729.27..1104320.17 rows=128604 width=4) (actual time=22631.840..43825.904 rows=133724 loops=1)
                                     ->  Merge Join  (cost=710729.27..1103034.13 rows=128604 width=4) (actual time=22631.840..43783.381 rows=133724 loops=1)
                                           Merge Cond: (public.article.id = t.aid)
                                           ->  Index Scan using article_pkey on article  (cost=0.00..380571.18 rows=9828389 width=4) (actual time=0.016..19654.198 rows=9999817 loops=1)
                                           ->  Sort  (cost=710729.21..711050.72 rows=128604 width=4) (actual time=22631.789..22652.894 rows=133724 loops=1)
                                                 Sort Key: t.aid
                                                 Sort Method: quicksort  Memory: 12413kB
                                                 ->  Seq Scan on article_tag t  (cost=0.00..699815.50 rows=128604 width=4) (actual time=378.633..22571.174 rows=133724 loops=1)
                                                       Filter: (tid = 3)
                               ->  Subquery Scan on "*SELECT* 2"  (cost=710729.27..1104320.17 rows=128604 width=4) (actual time=22299.632..43951.581 rows=132359 loops=1)
                                     ->  Merge Join  (cost=710729.27..1103034.13 rows=128604 width=4) (actual time=22299.631..43906.152 rows=132359 loops=1)
                                           Merge Cond: (public.article.id = t.aid)
                                           ->  Index Scan using article_pkey on article  (cost=0.00..380571.18 rows=9828389 width=4) (actual time=0.014..20120.274 rows=9999766 loops=1)
                                           ->  Sort  (cost=710729.21..711050.72 rows=128604 width=4) (actual time=22299.577..22320.041 rows=132359 loops=1)
                                                 Sort Key: t.aid
                                                 Sort Method: quicksort  Memory: 12349kB
                                                 ->  Seq Scan on article_tag t  (cost=0.00..699815.50 rows=128604 width=4) (actual time=2.016..22240.702 rows=132359 loops=1)
                                                       Filter: (tid = 6)
             ->  Subquery Scan on "*SELECT* 3"  (cost=710729.27..1104320.17 rows=128604 width=4) (actual time=22343.607..44569.712 rows=132618 loops=1)
                   ->  Merge Join  (cost=710729.27..1103034.13 rows=128604 width=4) (actual time=22343.607..44532.361 rows=132618 loops=1)
                         Merge Cond: (public.article.id = t.aid)
                         ->  Index Scan using article_pkey on article  (cost=0.00..380571.18 rows=9828389 width=4) (actual time=0.021..20668.980 rows=9999945 loops=1)
                         ->  Sort  (cost=710729.21..711050.72 rows=128604 width=4) (actual time=22343.551..22364.494 rows=132618 loops=1)
                               Sort Key: t.aid
                               Sort Method: quicksort  Memory: 12361kB
                               ->  Seq Scan on article_tag t  (cost=0.00..699815.50 rows=128604 width=4) (actual time=12.574..22285.686 rows=132618 loops=1)
                                     Filter: (tid = 22)
     Total runtime: 132672.852 ms
    (33 行)
    
  • 配列を使ったテーブル
  • username@[local] ~=# EXPLAIN ANALYZE SELECT id FROM article2 WHERE 3 = ANY(tids) AND 6 = ANY(tids) AND 22 = ANY(tids);
                                                       QUERY PLAN                                                   
    ----------------------------------------------------------------------------------------------------------------
     Seq Scan on article2  (cost=0.00..647414.00 rows=1169 width=4) (actual time=1974.210..3075.540 rows=8 loops=1)
       Filter: ((3 = ANY (tids)) AND (6 = ANY (tids)) AND (22 = ANY (tids)))
     Total runtime: 3075.571 ms
    (3 行)
    
    時間: 3076.039 ms
    

    配列を利用したテーブル構成の場合、ジョインや集合操作を行わないので当然ですが、クエリプランが非常にシンプルで、132 秒対 3 秒と40 倍以上速い事が分かります。通常のテーブル構成の場合は、検索に非常に長い時間が必要でした。しかし、個人ブログ程度のデータ量であれば、十分実用的な速度で動作します。

    今回のテストケースように、ブログ記事数が 1000 万、タグの数が 4000 万と比較的データ量が多い場合は、どちらの場合も実用的な速度では動作しません。特に、通常のテーブル定義の場合は問題外に遅い速度と言えます。

インデックスがある場合のパフォーマンス

データにインデックスを付けた場合の比較を行います。article テーブルの id コラムはプライマリーキーであるため、自動的にユニークインデックスが作成されます。別途追加する必要はありません。article_tag テーブルの aid, tid に B-Tree インデックス、article2 テーブルの配列型コラムの tids には GIN インデックスを追加します。

CREATE INDEX tag_aid_idx ON article_tag(aid);
CREATE INDEX tag_tid_idx ON article_tag(tid);
CREATE INDEX artice2_tids_idx ON article2 USING GIN (tids);

PostgreSQL は、使用するインデックスを省略すると B-Tree インデックスが使用されます。2つの B-Tree インデックス作成後のデータベース容量の増加は、およそ 1.5GB でした。

配列型の tids に GIN インデックスを作成する事により、id と tids をペアとする転置インデックスが作成されます。GIN インデックス作成後のデータベース容量増加は、およそ 0.2GB でした。B-Tree に比べ、非常にコンパクトなインデックスであることが分かります。

  • 通常のテーブル
  • username@[local] ~=# EXPLAIN ANALYZE SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 3 INTERSECT SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 6 INTERSECT SELECT article.id FROM article, article_tag AS t WHERE article.id = t.aid AND t.tid = 22;                                                                                       
                                                       QUERY PLAN                                                                                       
    ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
     HashSetOp Intersect  (cost=233589.82..1936502.53 rows=132766 width=4) (actual time=77296.069..77296.627 rows=13 loops=1)
       ->  Append  (cost=233589.82..1935838.70 rows=265532 width=4) (actual time=54668.224..77252.612 rows=134236 loops=1)
             ->  Result  (cost=233589.82..1290780.41 rows=132766 width=4) (actual time=54668.222..54680.796 rows=1348 loops=1)
                   ->  HashSetOp Intersect  (cost=233589.82..1290780.41 rows=132766 width=4) (actual time=54668.220..54680.474 rows=1348 loops=1)
                         ->  Append  (cost=233589.82..1290116.58 rows=265532 width=4) (actual time=8827.234..54522.190 rows=267037 loops=1)
                               ->  Subquery Scan on "*SELECT* 1"  (cost=233589.82..645058.29 rows=132766 width=4) (actual time=8827.233..30325.553 rows=133622 loops=1)
                                     ->  Merge Join  (cost=233589.82..643730.63 rows=132766 width=4) (actual time=8827.231..30285.320 rows=133622 loops=1)
                                           Merge Cond: (public.article.id = t.aid)
                                           ->  Index Scan using article_pkey on article  (cost=0.00..383149.41 rows=10000004 width=4) (actual time=0.043..20008.606 rows=9999987 loops=1)
                                           ->  Sort  (cost=233589.78..233921.70 rows=132766 width=8) (actual time=8814.333..8834.066 rows=133622 loops=1)
                                                 Sort Key: t.aid
                                                 Sort Method: quicksort  Memory: 12408kB
                                                 ->  Bitmap Heap Scan on article_tag t  (cost=2493.57..222292.37 rows=132766 width=8) (actual time=91.303..8764.339 rows=133622 loops=1)
                                                       Recheck Cond: (tid = 3)
                                                       ->  Bitmap Index Scan on tag_tid_idx  (cost=0.00..2460.38 rows=132766 width=0) (actual time=39.765..39.765 rows=133622 loops=1)
                                                             Index Cond: (tid = 3)
                               ->  Subquery Scan on "*SELECT* 2"  (cost=233589.82..645058.29 rows=132766 width=4) (actual time=17786.354..24134.441 rows=133415 loops=1)
                                     ->  Merge Join  (cost=233589.82..643730.63 rows=132766 width=4) (actual time=17786.353..24093.252 rows=133415 loops=1)
                                           Merge Cond: (public.article.id = t.aid)
                                           ->  Index Scan using article_pkey on article  (cost=0.00..383149.41 rows=10000004 width=4) (actual time=0.013..4850.763 rows=9999924 loops=1)
                                           ->  Sort  (cost=233589.78..233921.70 rows=132766 width=8) (actual time=17786.323..17805.605 rows=133415 loops=1)
                                                 Sort Key: t.aid
                                                 Sort Method: quicksort  Memory: 12398kB
                                                 ->  Bitmap Heap Scan on article_tag t  (cost=2493.57..222292.37 rows=132766 width=8) (actual time=100.372..17725.633 rows=133415 loops=1)
                                                       Recheck Cond: (tid = 6)
                                                       ->  Bitmap Index Scan on tag_tid_idx  (cost=0.00..2460.38 rows=132766 width=0) (actual time=58.730..58.730 rows=133415 loops=1)
                                                             Index Cond: (tid = 6)
             ->  Subquery Scan on "*SELECT* 3"  (cost=233589.82..645058.29 rows=132766 width=4) (actual time=17246.527..22547.367 rows=132888 loops=1)
                   ->  Merge Join  (cost=233589.82..643730.63 rows=132766 width=4) (actual time=17246.526..22511.651 rows=132888 loops=1)
                         Merge Cond: (public.article.id = t.aid)
                         ->  Index Scan using article_pkey on article  (cost=0.00..383149.41 rows=10000004 width=4) (actual time=6.521..3722.227 rows=9999929 loops=1)
                         ->  Sort  (cost=233589.78..233921.70 rows=132766 width=8) (actual time=17239.968..17258.883 rows=132888 loops=1)
                               Sort Key: t.aid
                               Sort Method: quicksort  Memory: 12374kB
                               ->  Bitmap Heap Scan on article_tag t  (cost=2493.57..222292.37 rows=132766 width=8) (actual time=100.648..17185.592 rows=132888 loops=1)
                                     Recheck Cond: (tid = 22)
                                     ->  Bitmap Index Scan on tag_tid_idx  (cost=0.00..2460.38 rows=132766 width=0) (actual time=60.321..60.321 rows=132888 loops=1)
                                           Index Cond: (tid = 22)
     Total runtime: 19713.619 ms
    (39 行)
    時間: 19713.619 ms
    

    クエリプランが変更され、インデックスを利用するようになった事が分かります。実行時間もおよそ 132 秒から 20 秒へと 6 倍ほど高速化しました。6 倍以上高速化したといっても、まだまだ実用には程遠いパフォーマンスです。

  • 配列を使ったテーブル
  • username@[local] ~=# EXPLAIN ANALYZE SELECT id FROM article2 WHERE 3 = ANY(tids) AND 6 = ANY(tids) AND 22 = ANY(tids);
                                                       QUERY PLAN                                                   
    ----------------------------------------------------------------------------------------------------------------
     Seq Scan on article2  (cost=0.00..647414.00 rows=1169 width=4) (actual time=2163.149..3230.211 rows=8 loops=1)
       Filter: ((3 = ANY (tids)) AND (6 = ANY (tids)) AND (22 = ANY (tids)))
     Total runtime: 3230.240 ms
    (3 行)
    
    時間: 3230.781 ms
    

    配列を使ったテーブルに GIN インデックスを作成しても利用されません。これは配列演算子を利用しない事が原因です。細かい AND、OR 条件を一度に指定できませんが、配列演算子を利用すると GIN インデックスが利用されます。上記クエリの WHERE 条件と同等の演算子は "@>" (左辺が右辺を包含) であるので、これを利用します。

    username@[local] ~=# EXPLAIN ANALYZE SELECT id FROM article2 WHERE tids @> array[3,6,22];
                                                               QUERY PLAN                                                            
    ---------------------------------------------------------------------------------------------------------------------------------
     Bitmap Heap Scan on article2  (cost=685.50..32763.93 rows=10000 width=4) (actual time=94.217..94.229 rows=8 loops=1)
       Recheck Cond: (tids @> '{3,6,22}'::integer[])
       ->  Bitmap Index Scan on artice2_tids_idx  (cost=0.00..683.00 rows=10000 width=0) (actual time=94.205..94.205 rows=8 loops=1)
             Index Cond: (tids @> '{3,6,22}'::integer[])
     Total runtime: 94.256 ms
    (5 行)
    
    時間: 94.754 ms
    

    GIN インデックスが利用され、元々速かった配列型を利用したテーブルのおよそ 30 倍、インデックスを利用した通常テーブルのおよそ 200 倍の速度です。100ms 以内にクエリが完了しました。これなら実用的なパフォーマンスと言えます。

まとめ

PostgreSQL の配列型と GIN インデックスは、転置インデックスが効果的なデータ構造で利用すると圧倒的なパフォーマンスを提供します。今回のテストケースでは、必要なインデックスを作成した場合と比較しても、一般的なテーブル構成の 200 倍の高速化が可能でした。配列+GIN のテーブル構成は、構成がシンプルになるのみでなく、インデックス領域も 1/7 以下、MN 関係の為のテーブルも不要となりデータ容量の面でも有利でした。転置インデックスが有効に利用できるようなデータの場合、配列と転置インデックスを利用する事により、PostgreSQL 以外の RDBMS では不可能であるアプリケーションの構築も可能となります。

配列+GIN によるタグシステムのパフォーマンスチューニングは、これだけで十分速いと思えます。しかし、PostgreSQL はテーブル継承を利用したクラスタリング、データベースリンク (dblink) によるクラスタリングが行えます。これらを利用し、更に大きなデータの検索を高速に行う事も可能です。

GIN と類似のインデックスに GiST(Generalized Search Tree) インデックスがあります。GIN は GiST のおよそ 3 倍高速に検索できますが、インデックス作成は GiST に比べ3倍低速です。また、GIN インデックスは GiST インデックスの 2 から 3 倍のインデックスサイズとなります。GIN は可逆インデックスですが、GiST は不可逆 (つまり検索結果が正しいとは限らない) です。今回想定したブログのタグシステムの場合、GIN の方が適しています。しかし、用途によっては GiST の方が向いている場合もあります。必要に応じて適切なインデックスを選んで下さい。

参考

PostgreSQL 9.1.2文書
http://www.postgresql.jp/document/pg912doc/html/index.html
8.14. 配列
http://www.postgresql.jp/document/pg912doc/html/arrays.html
9.17. 配列関数と演算子
http://www.postgresql.jp/document/pg912doc/html/functions-array.html
11.2. インデックスの種類
http://www.postgresql.jp/document/pg912doc/html/indexes-types.html
12.9. GiSTおよびGINインデックス種類
http://www.postgresql.jp/document/pg912doc/html/textsearch-indexes.html
第 54章GINインデックス
http://www.postgresql.jp/document/pg912doc/html/gin.html
B. MOMJIAN (Jan. 2012) PostgreSQL Performance Tuning
http://momjian.us/main/writings/pgsql/performance.pdf

postgresql.conf 設定の変更箇所

  port = 5491
  shared_buffers = 1024MB
  work_mem = 100MB
  maintenance_work_mem = 160MB
  bgwriter_delay = 2000ms 
  fsync = off
  commit_delay = 10000
  commit_siblings = 50

テストに利用したシステム

  CPU: Core2Quad Q9400 2.66GHz
  MEM: 8GB DDR3
  HDD: SATA2 2TB 7200rpm

今回の記事作成にあたり、エレクトロニック・サービス・イニシアチブ社 大垣 靖男様に執筆協力をいただきました。

0 件のコメント:

コメントを投稿