ぱぱネット（仮）

2010-06-10 基本に立ち戻ろうか

_ [Linux][開発] TokyoCabinet/Tyrantの複合検索について

もちろん、ディスクに永久保持されるKVSとしての側面も十分魅力的ですが。 RDBMSばりのテーブルインデックスを備え複合検索ができるTC/TTは、「どうしてもMySQLとかの代わりに使ってみたくなる」のが人情といふもの。

実際にはたくさんのカラムを登録してある(横に長い表)だけど、一応以下のようなテーブルだとだと思ってください。

＜＜投稿時刻ptime('3')＞＞	＜＜トークンptoken('14')＞＞
1275332400	演奏してみた,アイマス
1275246000	大臣,ナチス,誰得
1275459590	才能の無駄遣い,コマ撮り

時刻はUNIX起源時間(epoch_time)。トークンは実際は文章タグ検索用のテキスト。 TCでは、カラム名を各セルに付与するのでデータサイズを考慮して番号に置換してある。

また、それぞれのカラムには以下のインデックスが張ってある。 ptime(3)では数値型の比較速度アップ(ITDECIMAL)が、 ptoken(14)ではトークン単位(上の例だとカンマ(,)で区切られた箇所ごと)の比較速度アップ(ITTOKEN)が期待できる。

$db->setindex('3', $db->ITDECIMAL);
$db->setindex('14', $db->ITTOKEN);

これはレコード数が数千規模では十分うまく動いていた.....のですが。

_ [Linux][開発] しかしこれが遅い

まあ基本的には 110万件も登録するなよという話なんですが。以下サンプルプログラム。単純に時刻範囲を指定して検索トークンを指定しているだけです。

#!usr/bin/perl
use strict;
use Time::HiRes qw( gettimeofday tv_interval );
use TokyoTyrant;
my $db = TokyoTyrant::RDBTBL->new;
$db->open("localhost", 1991);
my $qry = TokyoTyrant::RDBQRY->new($db);
$qry->addcond('3', $qry->QCNUMGE, 1275591600);
$qry->addcond('3', $qry->QCNUMLE, 1276196400);
$qry->addcond('14', $qry->QCSTRAND, 'はやぶさ');
$qry->setlimit(1000);
my $t1 = [gettimeofday];
my $rv = $qry->search();
printf "TIME: %.2f s\n", tv_interval($t1);
printf "RESULT: %d records\n", scalar @$rv;
printf "%s\n" . $qry->hint;
$db->close();

検索結果。

TIME: 19.83
RESULT: 53 records

using an auxiliary index: "3" desc (NUMLT/NUMLE)
auxiliary result set size: 1191219
using an index: "3" asc (NUMGT/NUMGE)
limited matching: 1000
result set size: 53
leaving the natural order

119万件から53件見つけるのに20秒弱(！)かかる。これはいったい............ そもそも多くのRDBMSではlike演算子以外にテキスト検索の手法を持たないから、検索時間を責めるのは不当に感じる人もいるかもしれないけど。

何かおかしいので以下の2行を抜いてみる。時刻レンジはなくなってしまうけれど.....

# $qry->addcond('3', $qry->QCNUMGE, 1275591600);
# $qry->addcond('3', $qry->QCNUMLE, 1276196400);

TIME: 0.10 (速い)
RESULT: 100 records(増えてる)

なんと0.1秒でオワタ(;∀`)

これはひどい......条件を減らして件数が多くなるほうが速いとか何なの。複合検索の意味あるのかよ、と。

_ [Linux][開発] ソースコードを追いました

本質的な問題はTokyo Cabinetのtctdb.cにあります。全体はこういうループなのね。で、mcondという変数にメインの検索条件を、ncondという変数にサブの検索条件を登録する。

static TCLIST *tctdbqrysearchimpl(TDBQRY *qry){
(省略)
 for(int i = 0; i < cnum; i++){
   TDBCOND *cond = conds + i;
   for(int j = 0; j < inum; j++){
     TDBIDX *idx = idxs + j;
     if(!strcmp(cond->name, idx->name)){
     (省略)
   }
 }
}

まずこれがいけない。iがカラム方向で、jが使われているインデックスの種別だから。本当に順番に検索条件を指定してしまっている。古くから売っているRDBMSでここまでずさんなのは存在しないだろう。検索条件の適用順ソート、つまりコスト推定は必須のアルゴリズムだと思います。メインの検索条件には、なるべく件数を絞り込める条件を持ってこなければならないわけ。

例えば新聞データベースで「東京」って入力したら数万件ひっかかってくるだろうけど、「パラダイス」だったら数百件かもしれない。だったら「東京」＋「パラダイス」という複合検索だったら、「パラダイス」を先に検索して、その結果から東京を含むものを抜く...って当然するよね。

数値型でも同様。データの特性にもよるけど、全体が均一に入っていることを期待しなくても、数値の分布を集計しておいて、投機コストを算定するくらいは商用RDBMSはやっているはず。極端な話、最小値が10000で最大値が20000である数列に対して「検索条件は数値100未満」と指定したら、それは結果ゼロ件に決まっているわけです。そんなに難しい話じゃないです。

このように、投機コストによる複合検索条件のソート、というものは検索時間に大きな影響を与えるわけです。むしろこれがインデックスと並んでRDBMSの各社がアルゴリズムにしのぎを削っているところ、と言っても良いんじゃないでしょうか。

真に重要なのは検索結果レコードを取得する（投機）前に、コストの見積もりを行うということなのです。

_ [Linux][開発] さらに良くないことに....

こちらは本質的な話じゃないけれど。富豪プログラミングというんですかね。 tctdb.cではサブの検索条件の結果をnmapというテーブルに格納してしまうらしい。

 if(ncond){
   ncond->alive = false;
   acnum--;
   nmap = tctdbqryidxfetch(qry, ncond, nidx);
   max = tclmin(max, TCMAPRNUM(nmap));
 }

いやこれはダメでしょう。なぜかって？検索結果が110万件でも全部メモリに読み込むのかい？ということですわ。実際、TC/TTは読み込んでいても110万件をたった19秒！で済ませている(AthlonII X4 605e時) ので、とても優秀だと褒めるべきなのだろうか....

検索システムを作るときは、何の入力に検索時間や品質が比例してほしいか、最悪値はどこか、トンでもない条件でトンでもないことにならないか、これらを良く考える必要があります。

まあ所詮、俺のRDBの知識は2000年前半、メモリ32MB,HDD320MBのPC、読んでいた本はリコーの研究所の中の人が書いた絶版RDBMSアルゴリズム本（笑）なので、最近のオンメモリDBとかの常識は知らんのですが、俺の常識ではこんなことはしない.... するとしても投機コスト（つまり件数が少なくてメモリに読み込めば高速化が見込めるということ）がわかってからだね。