白状すると、ハッシュ結合を全く理解していませんでした。
最近少し時間ができたのでAmazon.co.jp: Database Management Systems: Raghu Ramakrishnan, Johannes Gehrke: 洋書を読んだりしていて、ハッシュ結合を勉強したので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とかだと結構起きているのかもしれない。
ハッシュ結合の詳細については上記ざっくりとしすぎなので本を読むか、no titleとか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には実装されてるっぽいですが、論文とかは最近のものが多いのでアカデミックには割と新しいのかもしれない。OSSなRDBMSの中にはハッシュ結合をサポートしないものもあるので、そういう意味では前衛的なエグゼキュータなんですね。9.1ではRIGHT JOINとFULL JOINでもハッシュ結合をサポートしたらしい。もう複雑すぎるからFSMにしたよと。
話があっちこっちしましたが、まとめると、
・ハッシュ結合にはいろいろなサブカテゴリがあるよ
・かならずしもオンメモリオンリーというわけではないよ
・ただハイブリッドではオンメモリーオンリーもありうるよ
・Skewなハッシュテーブルを使うことがあるよ
・Skewを狙うならANALYZEしておこうね
あまり理論側は得意ではないのでツッコミいただけると幸いです。
Jaylan2011/08/21 01:58Always the best cntonet from these prodigious writers.
ssecvwazdm2011/08/23 00:23eM9CgZ <a href="http://wrbdtejgocqu.com/">wrbdtejgocqu</a>
yjezfaa2011/08/24 02:52Pd5csq , [url=http://zofyevoadmyk.com/]zofyevoadmyk[/url], [link=http://mztviualethb.com/]mztviualethb[/link], http://ixlrjkuaaxbt.com/
mlcihm2011/08/26 02:26ChwsB6 <a href="http://jcvorzbynnky.com/">jcvorzbynnky</a>
yypqgsf2011/08/31 19:12z5kWY4 , [url=http://cgmgxvxapxwp.com/]cgmgxvxapxwp[/url], [link=http://nailrhttcisp.com/]nailrhttcisp[/link], http://dudmycbcqmix.com/