象と戯れ

 | 

2011-04-25

モダンハッシュ結合

02:31 | モダンハッシュ結合 - 象と戯れ を含むブックマーク はてなブックマーク - モダンハッシュ結合 - 象と戯れ

白状すると、ハッシュ結合を全く理解していませんでした。

最近少し時間ができたのでAmazon CAPTCHAを読んだりしていて、ハッシュ結合を勉強したのでPostgreSQLの実装を再訪しました。

プランナも見るべきですがまずはエグゼキュータ。ファイルとしてはnodeHash.cとnodeHashjoin.cです。あとはhashjoin.h。これだけハッシュ結合してきたくせに今までオンメモリでしか処理しないと思ってました。擬似コードにするとこんなかんじ(JS御免)。

var htable = {};
for(var i=0, l=inner.length; i<l; i++){
  var hkey = h(inner.key);
  htable[hkey] = inner.tuple;
}
for(var i=0, l=outer.length; i<l; i++){
  var hkey = h(outer.key);
  if(hkey in htable){
    emit(outer.tuple, htable[hkey]);
  }
}

が、RDBMSの教科書的には最初に出てくるのが単純ハッシュ結合というやつで、メモリに乗り切る分だけでハッシュテーブルを作り結合を繰り返すというもの。それじゃあんまりだからGRACE結合というのがあってinnerとouterをまずハッシュ関数でk分割したあと、それぞれの分割結果同士でハッシュテーブルを作り結合する方法が出てきます。一回目のハッシュ分割で同一ハッシュ値のタプルがまとめられるから単純よりは効率がいい。それでもこの分割結果は一度ディスクに書き出されるわけです。そりゃそうだ。メモリが無限ではない(むしろわずかしかない)ことを前提とするのがRDBMSの基本的なコンセプトだから。そのあと出てくるのがハイブリッドハッシュ結合という奴で、GRACEの改善として1回目の分割に限りディスクに書き出さずにメモリに乗ったまま処理しましょうと。ディスクに書き出す分割が1減るのと、分割後の再読み出しが1なくなるのでI/Oが減っていいかんじ。このハイブリッドの特殊ケースとして、分割数=1のとき、ディスク書き出しなしでオンメモリ結合ができる、それが冒頭に示したような処理に落ち着くというところのようです。

この辺見るとファイルに書き出してるのがよくわかります。hashtable->nbatchというのが分割数=kですね。

 673     else if (curbatch < hashtable->nbatch)
 674     {
 675         BufFile    *file = hashtable->outerBatchFile[curbatch];
 676 
 677         /*
 678          * In outer-join cases, we could get here even though the batch file
 679          * is empty.
 680          */
 681         if (file == NULL)
 682             return NULL;
 683 
 684         slot = ExecHashJoinGetSavedTuple(hjstate,
 685                                          file,
 686                                          hashvalue,
 687                                          hjstate->hj_OuterTupleSlot);

PostgreSQLの場合メモリが許さない場合はNestedLoopかMergeJoinになるようにプランナが実装されているから、あまりこのディスク書き出しのケースは発生しないんじゃないかと思うのですが、enable_nestloop=offかつenable_mergejoin=offとかだと結構起きているのかもしれない。

ハッシュ結合の詳細については上記ざっくりとしすぎなので本を読むか、HTTP 404 ファイル未検出 - TOKYO TECH OCWとかWikipediaあたりが参考になります。

トラディショナルな理論としてはハイブリッドが出てきておしまい、なのですが、PostgreSQLは8.4からさらにSkewなハッシュ結合を実装しています。Skewって何やねんて思いますが、非対称な、とかそんな意味と思われます。正体を見破るにはhashjoin.hのこのコメントがとてもわかりやすい。

git.postgresql.org Git - postgresql.git/commit

  75 /*
  76  * If the outer relation's distribution is sufficiently nonuniform, we attempt
  77  * to optimize the join by treating the hash values corresponding to the outer
  78  * relation's MCVs specially.  Inner relation tuples matching these hash
  79  * values go into the "skew" hashtable instead of the main hashtable, and
  80  * outer relation tuples with these hash values are matched against that
  81  * table instead of the main one.  Thus, tuples with these hash values are
  82  * effectively handled as part of the first batch and will never go to disk.
  83  * The skew hashtable is limited to SKEW_WORK_MEM_PERCENT of the total memory
  84  * allowed for the join; while building the hashtables, we decrease the number
  85  * of MCVs being specially treated if needed to stay under this limit.
  86  *
  87  * Note: you might wonder why we look at the outer relation stats for this,
  88  * rather than the inner.  One reason is that the outer relation is typically
  89  * bigger, so we get more I/O savings by optimizing for its most common values.
  90  * Also, for similarly-sized relations, the planner prefers to put the more
  91  * uniformly distributed relation on the inside, so we're more likely to find
  92  * interesting skew in the outer relation.
  93  */
  94 typedef struct HashSkewBucket
  95 {
  96     uint32      hashvalue;      /* common hash value */
  97     HashJoinTuple tuples;       /* linked list of inner-relation tuples */
  98 } HashSkewBucket;

要するにハイブリッドハッシュ結合における1分割目は効率がいいので、MCV:頻出値については特別扱いして1分割目で処理しましょう、そのためのハッシュテーブルを別に用意しますということらしいです。ハッシュ関数によるランダムな分割だと結果的にデータの偏りがどこに現れるのかコントロールしにくいわけですが、プランナ用の統計情報を利用することで値の偏りを逆に利用した最適化を行っているわけです。分割数=1のときはどのみち全データをメモリで処理するので関係なくなります(実際のコードもnbatch > 1の条件が入っています)。そしてまさにnodeHash.cでは統計情報のテーブルからMCVを取得して事前にハッシュテーブルに登録している処理がありますので、もうこれは巨大テーブルの結合前にはANALYZE必須というわけです。

1139     /*
1140      * Try to find the MCV statistics for the outer relation's join key.
1141      */
1142     statsTuple = SearchSysCache3(STATRELATTINH,
1143                                  ObjectIdGetDatum(node->skewTable),
1144                                  Int16GetDatum(node->skewColumn),
1145                                  BoolGetDatum(node->skewInherit));
1146     if (!HeapTupleIsValid(statsTuple))
1147         return;
1148 
1149     if (get_attstatsslot(statsTuple, node->skewColType, node->skewColTypmod,
1150                          STATISTIC_KIND_MCV, InvalidOid,
1151                          NULL,
1152                          &values, &nvalues,
1153                          &numbers, &nnumbers))

商用RDBMSには実装されてるっぽいですが、論文とかは最近のものが多いのでアカデミックには割と新しいのかもしれない。OSSRDBMSの中にはハッシュ結合をサポートしないものもあるので、そういう意味では前衛的なエグゼキュータなんですね。9.1ではRIGHT JOINとFULL JOINでもハッシュ結合をサポートしたらしい。もう複雑すぎるからFSMにしたよと

話があっちこっちしましたが、まとめると、

・ハッシュ結合にはいろいろなサブカテゴリがあるよ

・かならずしもオンメモリオンリーというわけではないよ

・ただハイブリッドではオンメモリーオンリーもありうるよ

・Skewなハッシュテーブルを使うことがあるよ

・Skewを狙うならANALYZEしておこうね

あまり理論側は得意ではないのでツッコミいただけると幸いです。

JaylanJaylan2011/08/21 01:58Always the best cntonet from these prodigious writers.

ssecvwazdmssecvwazdm2011/08/23 00:23eM9CgZ <a href="http://wrbdtejgocqu.com/">wrbdtejgocqu</a>

yjezfaayjezfaa2011/08/24 02:52Pd5csq , [url=http://zofyevoadmyk.com/]zofyevoadmyk[/url], [link=http://mztviualethb.com/]mztviualethb[/link], http://ixlrjkuaaxbt.com/

mlcihmmlcihm2011/08/26 02:26ChwsB6 <a href="http://jcvorzbynnky.com/">jcvorzbynnky</a>

yypqgsfyypqgsf2011/08/31 19:12z5kWY4 , [url=http://cgmgxvxapxwp.com/]cgmgxvxapxwp[/url], [link=http://nailrhttcisp.com/]nailrhttcisp[/link], http://dudmycbcqmix.com/

 |