2013年7月1日月曜日

文字列のソート順とパフォーマンス

こんにちは。サイオステクノロジーの稲垣です。

今回は、文字列のソート順とパフォーマンスの関係性についてご紹介します。

PostgreSQL のデフォルトのソート順を、言語に合わせて変える事ができます。

ソート順を変えるとパフォーマンスに大きく影響しますが、意外にどの程度の影響が出るのか知られていません。ソート順のパフォーマンスへの影響は状況によって異なります。

今回は簡単なデータベースを使ってその影響を検証してみます。

この文書の執筆とベンチマークには以下の環境を使いました。

  • CPU: Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz
  • HDD: SATA II
  • OS: Fedora 18 x86_64
  • PostgreSQL: 9.2 (git branch 2013/4/20)
  • PHP: php-5.4.13-1.fc18.x86_64

■ ソートの順序

PostgreSQL のデフォルトのソート順は C となっています。C のソート順とはバイナリの値で文字列を比較することを意味します。これは、バイナリ値をそのままソート時の比較に使うので、最も高速に動作することが予測できます。

しかし、バイナリ値でソートしてもあまり困らないようになっていますが、ソートが早いだけでは困る場合もあります。ソートが一定のルールに従って動作して欲しい場合も少なくありません。

例えば、ロケールを指定しない場合(C の場合)、仮名をソートすると以下の様にソートされます。

 \343\201\257 | は(清音)
 \343\201\260 | ば(濁音)
 \343\201\261 | ぱ(半濁音)
 \343\203\217 | ハ(清音)
 \343\203\220 | バ(濁音)
 \343\203\221 | パ(半濁音)

平仮名と片仮名の「は」と「ハ」は同じ順位としてソートされるべきですが、実際にはそのようになりません。ロケールを日本語に設定すると、正しくソート出来るようになります。

 \343\203\217 | ハ(清音)
 \343\201\257 | は(清音)
 \343\203\220 | バ(濁音)
 \343\201\260 | ば(濁音)
 \343\203\221 | パ(半濁音)
 \343\201\261 | ぱ(半濁音)

■ ソート順序(ロケール)の指定

ソート順序はロケールによって変わります。ソート順序を変える方法には、以下の 3 つがあります。

  1. データベース初期化時に指定する
  2. データベース作成時に指定する
  3. テーブル定義時に指定する

それぞれの方法について、以下に解説します。

  1. データベース初期化時に指定する
  2. initdb を実行して PostgreSQL のデータベースを初期化する際に、--locale オプションを利用して設定できます。
    以下の例のように、文字エンコーディングとロケールは一致しなければなりません。

    【例】

    $ initdb --encoding=UTF-8 --locale=ja_JP.UTF-8
    

    initdb ではロケールをより細かく指定する事も可能です。

    • --locale=LOCALE
    • 新しいデータベースのデフォルトロケールをセット

    • --lc-collate, --lc-ctype, --lc-messages=ロケール名
    • --lc-monetary, --lc-numeric, --lc-time=ロケール名
    • 新しいデータベースに対応するカテゴリに対するデフォルトロケールをセット (デフォルト値は環境変数から選ばれます)

  3. データベース作成時に指定する
  4. createdb を実行する場合にも、文字エンコーディングとロケールを指定できます。initdb より設定可能な項目は少ないですが、COLLATE と CTYPE の設定を個別に指定できるようになっています。

    【例】

    $ createdb -h localhost -T template0 --lc-collate=ja_JP.eucjp -E EUC-JP testdb
    
    • -l, --locale=ロケール名
    • データベースのロケール設定

    • --lc-collate=ロケール名
    • データベースの LC_COLLATE 設定

    • --lc-ctype==ロケール名
    • データベースの LC_CTYPE 設定

  5. テーブル定義時に指定する
  6. テーブル定義時に COLLATE を用いてソート順を指定できます。"ja_JP" を指定すると日本語順でソートされます。

    【例】

    CREATE TABLE mytable (
      txt text COLLATE "ja_JP"
    );
    

■ ロケール利用のメリットとデメリット

ロケールは便利な機能ですが、日本語ロケール ("ja_JP") を利用するとメリットとデメリットがあります。大きなデメリットの 1 つはパフォーマンスへの影響ですが、それだけではありません。

以下に、日本語ロケールを利用するメリットとデメリットを記載します。

メリット

  • 辞書順で文字列をソートできる
  • 全角の文字種の判別が適切になる

デメリット

  • 結果がプラットホーム依存
  • 文字列の比較処理に時間がかかる
  • 普通にインデックスを作ると LIKE 前方一致検索でインデックスが使われない

PostgreSQL のロケールサポートは、システムのライブラリに依存しています。つまり、同じ PostgreSQL であってもシステムが異なると結果が異なる可能性があります。

また、ロケールを有効にすると、文字列比較に時間がかかるようになります。これはソート順がバイナリとは異なる為、テーブルルックアップが発生する事が原因で、排除することは不可能なオーバーヘッドです。

さらに、ロケールを有効にした場合、前方一致検索でインデックス検索が行われなくなります。

以下の例は、今回のベンチマークにテーブルをクエリした場合の実行プランです。インデックスが利用されず、Seq Scan が行われる事が分かります。

test_utf8=# explain select * from foo where txt1 like 'ア%';
                        QUERY PLAN                         
-----------------------------------------------------------
 Seq Scan on foo  (cost=0.00..5552.00 rows=12457 width=49)
   Filter: (txt1 ~~ 'ア%'::text)

これを回避するには、インデックス作成時のインデックスカラムの演算子クラスを text_pattern_ops に指定します。

test_utf8=# CREATE INDEX txt2_idx ON foo (txt1 text_pattern_ops);
CREATE INDEX
時間: 1144.060 ms
test_utf8=# explain select * from foo where txt1 like 'ア%';
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Bitmap Heap Scan on foo  (cost=578.96..3200.35 rows=12457 width=49)
   Filter: (txt1 ~~ 'ア%'::text)
   ->  Bitmap Index Scan on txt2_idx  (cost=0.00..575.85 rows=12351 width=0)
         Index Cond: ((txt1 ~>=~ 'ア'::text) AND (txt1 ~<~ 'イ'::text))

今度は、txt2_idx を利用したスキャンが行われる事が分かります。

■ ベンチマーク

ロケールを利用すると、実際にどの程度の違い発生するのかベンチマークしてみます。まず、次の 3 つデータベースを作成します。

createdb -h localhost -T template0 --lc-collate=ja_JP.eucjp -E EUC-JP test_eucjp
createdb -h localhost -T template0 --lc-collate=C -E UTF-8 test_utf8c
createdb -h localhost -T template0 --lc-collate=ja_JP.UTF-8 -E UTF-8 test_utf8

test_eucjp は EUC-JP エンコーディングでソート順を日本語 ("ja_JP.eucjp") に設定しています。test_utf8c のデータベースは UTF-8 エンコーディングを利用してソート順を C に設定しています。test_utf8 は UTF-8 エンコーディングを用い、日本語 ("ja_JP.UTF-8") に設定しています。

テスト用にデータが必要なので郵便番号データを利用します。
郵便番号データは、以下の URL からダウンロードすることができます。

http://www.post.japanpost.jp/zipcode/download.html

利用したデータは「読み仮名データの促音・拗音を小書きで表記するもの」の全県データを使いました。レコード数は 12 万 3 千件です。

このデータ用に簡単な PHP スクリプトを作成し、前に作成したデータベースに対して実行してみます。下記に記載するとおり、PHP スクリプトは単純な操作内容とします。

bench.php

<?php
// 動作オプションの設定
if (empty($argv[1]) || $argv[1] == 'eucjp') {
    $dbname = 'test_eucjp';
    $enc = 'EUC-JP';
} else if ($argv[1] == 'utf8c') {
    $dbname = 'test_utf8c'; 
    $enc = 'UTF-8';
}  else if ($argv[1] == 'utf8') {
    $dbname = 'test_utf8'; 
    $enc = 'UTF-8';
} else {
    die('Specify options: eucjp, utf8c or utf8');
}    

echo 'Creating data...'.PHP_EOL;
// 総務省が公開している郵便番号の CSV データ
$lines = file('ken_all.csv') or die('Cannot open ken_all.csv');
$cnt = 0;
foreach($lines as $l) {
    $tmp = mb_convert_encoding($l, $enc, 'Shift-JIS');
    $tmp = strtr($tmp, '"', ''); // " で囲まれているデータとそれ以外があるので整形
    $data[] = str_getcsv($tmp, ',', '');
}
shuffle($data);

// データベースを準備
$db = pg_connect('host=localhost dbname='.$dbname) or die('Cannot connect to postgresql');
@pg_query($db, 'DROP TABLE foo');
pg_query($db, '
CREATE TABLE foo (
 txt1 text
);
CREATE INDEX txt1_idx ON foo (txt1);
DELETE FROM foo;
');

echo 'Inserting data..'.PHP_EOL;
$start = microtime(true);
$cnt = 0;
foreach($data as $e) {
    // 郵便番号データの 4,5,6 番目に半角カタカナの住所が保存されている
    // $s = mb_convert_kana($e[3].$e[4].$e[5], 'KV', $enc); // 全角カナを使う場合
    $s = $e[3].$e[4].$e[5];
    pg_query($db, 'INSERT INTO foo (txt1) VALUES ('.pg_escape_literal($s).');') or die('Failed to insert');
    // 漢字の住所データも挿入
    pg_query($db, 'INSERT INTO foo (txt1) VALUES ('.pg_escape_literal($e[6].$e[7].$e[8]).');') or die('Failed to insert');
     if (!(++$cnt % 10000)) {
        echo $cnt . PHP_EOL;
    }
}
echo 'Elapsed: ', microtime(true) - $start, PHP_EOL;


echo 'Benchmarking...'.PHP_EOL;
pg_query($db, 'VACUUM FULL');
for ($i=0; $i<3; $i++) {
    $start = microtime(true);
    $sql = 'SELECT * FROM foo;';
    pg_query($db, $sql);
    echo $sql, microtime(true)-$start, PHP_EOL;
}
for ($i=0; $i<3; $i++) {
    $start = microtime(true);
    $sql = 'SELECT * FROM foo ORDER BY foo;';
    pg_query($db, $sql);
    echo $sql, microtime(true)-$start, PHP_EOL;
}

echo 'Done'.PHP_EOL.PHP_EOL;

実行結果

$ php -d memory_limit=1G -d display_errors=on bench.php eucjp
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 30.143050909042
Benchmarking...
SELECT * FROM foo;0.13502097129822
SELECT * FROM foo;0.12818002700806
SELECT * FROM foo;0.12841701507568
SELECT * FROM foo ORDER BY foo;7.0083200931549
SELECT * FROM foo ORDER BY foo;7.0247440338135
SELECT * FROM foo ORDER BY foo;7.0759279727936
Done
$ php -d memory_limit=1G -d display_errors=on bench.php utf8c
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 28.212981939316
Benchmarking...
SELECT * FROM foo;0.19160103797913
SELECT * FROM foo;0.14273405075073
SELECT * FROM foo;0.14291596412659
SELECT * FROM foo ORDER BY foo;4.4753310680389
SELECT * FROM foo ORDER BY foo;4.3906571865082
SELECT * FROM foo ORDER BY foo;4.4129600524902
Done
$ php -d memory_limit=1G -d display_errors=on .php utf8
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 112.52828502655
Benchmarking...
SELECT * FROM foo;0.15445709228516
SELECT * FROM foo;0.15400290489197
SELECT * FROM foo;0.15289807319641
SELECT * FROM foo ORDER BY foo;114.70737695694
SELECT * FROM foo ORDER BY foo;114.97317409515
SELECT * FROM foo ORDER BY foo;114.78408503532
Done

EUC-JP と UTF-8 で多少実行時間が異なる事が分かりますが、それ以上に UTF-8 のロケールの有無で大きな差が出ている事が分かります。

約 24 万件のデータ挿入にロケール無しの場合は 28 秒のところ、ロケール有りでは 112 秒と 4 倍近くも時間がかかっています。SELECT でソートした場合は更に違いは顕著で、ロケールの無しの場合は 4 秒ほどでソートしていますが、ロケール有りの場合は 114 秒と 28 倍近い時間が必要でした。

また、今回の記事では詳しく紹介していませんが、半角カナだけのソートの場合はこれほど大きな違いになりませんでした。このブログの最後にベンチマーク結果を掲載しています。

PHP スクリプトを少し変えるだけで色々なテストケースが試せます。PostgreSQL/PHP が利用できる Linux 環境であれば、郵便番号データだけで簡単にテストを行うことができるので、ダウンロードして試してみて下さい。

■ まとめ

このようにロケールの利用は数倍から数十倍、場合によってはもっと大きなパフォーマンスの違いが発生します。データベースを設計する際には、ロケールサポートがシステムに大きなインパクトを与える事を理解した上で利用しなければ、思わぬパフォーマンス問題の原因になります。

また、データベース全体でロケールを利用するメリットがないアプリケーションも多いと思います。ロケールを有効にした文字列比較のオーバーヘッドは無視できないので、特定のテーブルでのみロケールを有効にしたソートを行いたい場合は、カラムに COLLATE を指定する方が良いでしょう。

そして、ロケールを有効化するとパフォーマンスに悪い影響を与えますが、ロケールありの半角カナの比較では 2 倍程度だけ遅くなる結果となりました。

解析はしていませんが、ルックアップテーブルが CPU のキャッシュ等に収まるので、大きな違いにならずに済んでいるのかもしれません。仮名のみの文字列データであれば、あまりパフォーマンスへの影響を気にする必要は無い可能性もあります。

ロケールサポートはシステムにも依存するので、利用するシステムではより大きなオーバーヘッドとなる可能性もあります。実際にどのような動作になるかは、ベンチマークして確かめると良いでしょう。

■ 参考

22.2. Collation Support
http://www.postgresql.org/docs/9.1/static/collation.html

ロケール(国際化と地域化)
http://lets.postgresql.jp/documents/technical/text-processing/2/

郵便番号データダウンロード(全国一括を利用しています)
http://www.post.japanpost.jp/zipcode/dl/kogaki.html

■ おまけ

全角カナのみソート結果(漢字住所を除いている為、レコード件数は半分)

$ php -d memory_limit=1G -d display_errors=on bench.php eucjp
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 16.111113071442
Benchmarking...
SELECT * FROM foo;0.069916009902954
SELECT * FROM foo;0.068452835083008
SELECT * FROM foo;0.068163156509399
SELECT * FROM foo ORDER BY foo;3.4341111183167
SELECT * FROM foo ORDER BY foo;3.4579529762268
SELECT * FROM foo ORDER BY foo;3.4676611423492
Done
$ php -d memory_limit=1G -d display_errors=on bench.php utf8c
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 15.606687068939
Benchmarking...
SELECT * FROM foo;0.084367990493774
SELECT * FROM foo;0.079833030700684
SELECT * FROM foo;0.078112840652466
SELECT * FROM foo ORDER BY foo;2.0987250804901
SELECT * FROM foo ORDER BY foo;2.0986139774323
SELECT * FROM foo ORDER BY foo;2.1002449989319
Done
$ php -d memory_limit=1G -d display_errors=on bench.php utf8
Creating data...
Inserting data..
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
110000
120000
Elapsed: 17.320512056351
Benchmarking...
SELECT * FROM foo;0.07519793510437
SELECT * FROM foo;0.074814081192017
SELECT * FROM foo;0.074079990386963
SELECT * FROM foo ORDER BY foo;4.5430409908295
SELECT * FROM foo ORDER BY foo;4.5495541095734
SELECT * FROM foo ORDER BY foo;4.535505771637
Done

0 件のコメント:

コメントを投稿