エグゼキュータ。LimitとSort
8.3からORDER BYとLIMITの組み合わせが改良されたということで、どう処理されるのか見てみた。参考にしたのは以下のページ。
マイコミジャーナルの記事ではoffsetをつけた場合には最適化が適用されないとあったが、PostgreSQL 8.3.5で試す限り、offsetをつけても最適化されているように見える（実行計画と実際の処理をdebugで確かめた）。
クエリ（explain analyze verboseつき）
1000000万件あるデータから10件を取り出す。
explain analyze verbose select * from accounts order by abalance limit 10
プランツリーと実行計画
{LIMIT
:startup_cost 47485.60
:total_cost 47485.63
:plan_rows 10
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree
{SORT
:startup_cost 47485.60
:total_cost 49985.76
:plan_rows 1000062
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 65001
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree
{SEQSCAN
:startup_cost 0.00
:total_cost 25874.62
:plan_rows 1000062
:plan_width 97
:targetlist (
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 1
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 1
}
:resno 1
:resname aid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 1
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 2
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 2
}
:resno 2
:resname bid
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 2
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 3
:vartype 23
:vartypmod -1
:varlevelsup 0
:varnoold 1
:varoattno 3
}
:resno 3
:resname abalance
:ressortgroupref 1
:resorigtbl 16453
:resorigcol 3
:resjunk false
}
{TARGETENTRY
:expr
{VAR
:varno 1
:varattno 4
:vartype 1042
:vartypmod 88
:varlevelsup 0
:varnoold 1
:varoattno 4
}
:resno 4
:resname filler
:ressortgroupref 0
:resorigtbl 16453
:resorigcol 4
:resjunk false
}
)
:qual <>
:lefttree <>
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:scanrelid 1
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:numCols 1
:sortColIdx 3
:sortOperators 97
:nullsFirst false
}
:righttree <>
:initPlan <>
:extParam (b)
:allParam (b)
:limitOffset <>
:limitCount
{CONST
:consttype 20
:consttypmod -1
:constlen 8
:constbyval false
:constisnull false
:constvalue 8 [ 10 0 0 0 0 0 0 0 ]
}
}
Limit (cost=47485.60..47485.63 rows=10 width=97) (actual time=3300.073..3300.073 rows=10 loops=1)
-> Sort (cost=47485.60..49985.76 rows=1000062 width=97) (actual time=3300.073..3300.073 rows=10 loops=1)
Sort Key: abalance
Sort Method: top-N heapsort Memory: 18kB
-> Seq Scan on accounts (cost=0.00..25874.62 rows=1000062 width=97) (actual time=0.000..1360.033 rows=1000000 loops=1)
Total runtime: 3300.073 msLimitの処理はExecLimit()、Sortの処理はExecSort()で行われる。
- ExecLimit()
- offset指定なしは 0 を指定したのと同じ。
- 結果のタプルを下位ノードから受け取るが、offsetを満たすまではループして捨てる。
- 一度offsetを超えたら、limitになるまでは1件ごとに上位へタプルを返す。
- 結果がなくなるかlimitになったらNULLを返して処理終わり。
- ExecSort()
- 最初のアクセスでは、下位のノードから受け取ったタプルをひたすらtuplesort_puttupleslot()をつかってputする。今回の例だと1000000回。そしてtuplesort_performsort()でソートする。
- ソートされた結果をTupleTableSlotに詰めて返す。
- 2度目以降のアクセスではソート済みのデータを単に返すだけ。
- puttuple_common()
- tuplesort_puttupleslot()から呼び出される。
- 最初は（TSS_INITIALの状態）タプルをメモリにためていく。
- limitの2倍に達するか、メモリが足りなくなったらmake_bounded_heap()を呼び出し、limit分だけしか保持しないようにする。TSS_BOUNDEDの状態に移行する。
- TSS_BOUNDEDの状態になったら、limit分の件数だけを保持する。この例の場合、より小さい値がきたら、今までのなかでもっとも大きいデータを破棄（しているっぽい）。
まとめ
limit分の件数だけを保持し、それだけをソートするというのが8.3から最適化の内容らしい。8.2以前では、limitに関係なく全データをソートしていたのだろう。今回の例だとソート対象が10件か1000000件かだから違いは大きい。
tuplesort.cは今のところ軽くみただけ。いずれちゃんと読む。
