象と戯れ

 | 

2010-06-23

ソート処理について調べた

23:32 | ソート処理について調べた - 象と戯れ を含むブックマーク はてなブックマーク - ソート処理について調べた - 象と戯れ

基本的にソート周りの速度に満足がいっていないわけです。ソートが速くなると単純なORDER BYだけじゃなくてGROUP BYやウィンドウ関数も速くなるので、どうにかできなかと常々考えておりました。そこで一念発起、tuplesortを調べたわけです。

いろいろ見所はあるのですが、気になっているのは全てのタプルをコピーするという事実。

void
tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
{
	MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
	SortTuple	stup;

	/*
	 * Copy the given tuple into memory we control, and decrease availMem.
	 * Then call the common code.
	 */
	COPYTUP(state, &stup, (void *) slot);

	puttuple_common(state, &stup);

	MemoryContextSwitchTo(oldcontext);
}

上記のCOPYTUPで入ってくるタプルをコピーするわけです。実体はHeap(ヒープソートと関係ない)のソートの場合はcopytup_heap()

static void
copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
{
	/*
	 * We expect the passed "tup" to be a TupleTableSlot, and form a
	 * MinimalTuple using the exported interface for that.
	 */
	TupleTableSlot *slot = (TupleTableSlot *) tup;
	MinimalTuple tuple;
	HeapTupleData htup;

	/* copy the tuple into sort storage */
	tuple = ExecCopySlotMinimalTuple(slot);
	stup->tuple = (void *) tuple;
	USEMEM(state, GetMemoryChunkSpace(tuple));
	/* set up first-column key value */
	htup.t_len = tuple->t_len + MINIMAL_TUPLE_OFFSET;
	htup.t_data = (HeapTupleHeader) ((char *) tuple - MINIMAL_TUPLE_OFFSET);
	stup->datum1 = heap_getattr(&htup,
								state->scanKeys[0].sk_attno,
								state->tupDesc,
								&stup->isnull1);
}

ExecCopySlotMinimalTuple(slot);でディスク上のタプルをメモリ上のMinimalTupleにコピーしています。でもディスク上のタプルもメモリアドレスで指しているのだから、わざわざコピーしないでそのまま(行ポインタのみを)ソートすればいいじゃん、って思った訳ですね。

結論としてはそれは無理。なぜならば行を含むバッファが共有メモリからリリースされてしまえば行データにアクセスできなくなってしまうから。だと思う。ソートするために100万行を持っておくためにはディスク上へのアドレスだけでは共有メモリが溢れてしまったときに対処できないので、結局メモリ上にコピーした上でメモリが溢れればディスクに一時データとして書き出さないといけない、という感じです。ある程度入力データ量が事前に見積もれれば最初からディスクソートで行くという戦略はありかもしれない。とにかくいちいちコピーして捨てるという考え方が気に入らないわけですが、このあたりがディスクを前提とするDBの設計上の十字架かもしれませんね。俗に「オンメモリDBはデータがメモリに載っているというだけではなく前提が変わるので処理の方法も違う」というのはこのあたりにも実感します。

そんな中でわかってきたのは、メモリの無駄遣い。tuplesortでは使っているメモリ量を正確に計算するためにGetMemoryChunkSpace()を使っているわけですが、ちょっとGDBしたところ、67バイトのMinimalTupleに対して確保されているChunkSizeがなんと128バイト。ま、63バイトまでのリクエストなら64バイトの確保で済むみたいなんですが、この無駄遣いっぷりはどうだろう。道理でwork_memをテーブルサイズよりちょい多めで設定してもquick sortにならないわけです。

メモリ管理は滅多に手が入ることもないし読んでも意味不明なところが多いので開発コミュニティでも放置プレイですが、実はまだ絞りがいがあるのかもしれません。インターフェイス風に関数ポインタで定義してあるけど、実際これが入れ替わったケースがないのでこんな抽象化は要らないのではとか怖くて誰にも言えない。興味がある方は是非src/backend/utils/mmgr/aset.cをご一読下さい。

 |