taediumの日記

2009-04-12

[][] エグゼキュータ。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 ms

Limitの処理は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は今のところ軽くみただけ。いずれちゃんと読む。


[][] エグゼキュータ。ビットマップヒープスキャン(Bitmap Heap Scan)

たまに実行計画で見かけるBitmap Heap Scan や Bitmap Index Scan が気になり調べてみた。ここの解説がわかりやすい。

【PostgreSQLウォッチ】第17回 新しい実行プラン・タイプによるPostgreSQL 8.1の性能向上

Indexの種類としてビットマップインデックスというものがB-Treeインデックスに並ぶものとしてあるというわけではなく、実行時にビットマップを使うよということ。ビットマップヒープスキャンが行われそうなクエリを投げて実行される処理を確認する。

ドキュメントで触れているのはここかな。

11.5. 複数のインデックスの組み合わせ

他のRDBMSでインデックスマージと呼んでいるものと同じなのかもしれない。

クエリ(explain analyze verboseつき)

aidにはインデックスが張られている。aidに対してはorで検索。bidにはインデックスは張られていないが、bid = 1 としたのはインデックス以外の条件が含められた場合を確認するため。

explain analyze verbose
select 
  aid
from 
  accounts
where 
  bid = 1
and
(
  aid = 100
  or 
  aid = 500
  or 
  aid = 1000
)
結果

プランツリーと実行計画。

   {BITMAPHEAPSCAN 
   :startup_cost 13.04 
   :total_cost 24.97 
   :plan_rows 1 
   :plan_width 4 
   :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
      }
   )
   :qual (
      {OPEXPR 
      :opno 96 
      :opfuncid 65 
      :opresulttype 16 
      :opretset false 
      :args (
         {VAR 
         :varno 1 
         :varattno 2 
         :vartype 23 
         :vartypmod -1 
         :varlevelsup 0 
         :varnoold 1 
         :varoattno 2
         }
         {CONST 
         :consttype 23 
         :consttypmod -1 
         :constlen 4 
         :constbyval true 
         :constisnull false 
         :constvalue 4 [ 1 0 0 0 ]
         }
      )
      }
   )
   :lefttree 
      {BITMAPOR 
      :startup_cost 13.04 
      :total_cost 13.04 
      :plan_rows 3 
      :plan_width 0 
      :targetlist <> 
      :qual <> 
      :lefttree <> 
      :righttree <> 
      :initPlan <> 
      :extParam (b)
      :allParam (b)
      :bitmapplans (
         {BITMAPINDEXSCAN 
         :startup_cost 0.00 
         :total_cost 4.35 
         :plan_rows 1 
         :plan_width 0 
         :targetlist <> 
         :qual <> 
         :lefttree <> 
         :righttree <> 
         :initPlan <> 
         :extParam (b)
         :allParam (b)
         :scanrelid 1 
         :indexid 16464 
         :indexqual (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ 100 0 0 0 ]
               }
            )
            }
         )
         :indexqualorig (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ 100 0 0 0 ]
               }
            )
            }
         )
         :indexstrategy (i 3)
         :indexsubtype (o 23)
         }
         {BITMAPINDEXSCAN 
         :startup_cost 0.00 
         :total_cost 4.35 
         :plan_rows 1 
         :plan_width 0 
         :targetlist <> 
         :qual <> 
         :lefttree <> 
         :righttree <> 
         :initPlan <> 
         :extParam (b)
         :allParam (b)
         :scanrelid 1 
         :indexid 16464 
         :indexqual (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ -12 1 0 0 ]
               }
            )
            }
         )
         :indexqualorig (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ -12 1 0 0 ]
               }
            )
            }
         )
         :indexstrategy (i 3)
         :indexsubtype (o 23)
         }
         {BITMAPINDEXSCAN 
         :startup_cost 0.00 
         :total_cost 4.35 
         :plan_rows 1 
         :plan_width 0 
         :targetlist <> 
         :qual <> 
         :lefttree <> 
         :righttree <> 
         :initPlan <> 
         :extParam (b)
         :allParam (b)
         :scanrelid 1 
         :indexid 16464 
         :indexqual (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ -24 3 0 0 ]
               }
            )
            }
         )
         :indexqualorig (
            {OPEXPR 
            :opno 96 
            :opfuncid 65 
            :opresulttype 16 
            :opretset false 
            :args (
               {VAR 
               :varno 1 
               :varattno 1 
               :vartype 23 
               :vartypmod -1 
               :varlevelsup 0 
               :varnoold 1 
               :varoattno 1
               }
               {CONST 
               :consttype 23 
               :consttypmod -1 
               :constlen 4 
               :constbyval true 
               :constisnull false 
               :constvalue 4 [ -24 3 0 0 ]
               }
            )
            }
         )
         :indexstrategy (i 3)
         :indexsubtype (o 23)
         }
      )
      }
   :righttree <> 
   :initPlan <> 
   :extParam (b)
   :allParam (b)
   :scanrelid 1 
   :bitmapqualorig (
      {BOOLEXPR 
      :boolop or 
      :args (
         {OPEXPR 
         :opno 96 
         :opfuncid 65 
         :opresulttype 16 
         :opretset false 
         :args (
            {VAR 
            :varno 1 
            :varattno 1 
            :vartype 23 
            :vartypmod -1 
            :varlevelsup 0 
            :varnoold 1 
            :varoattno 1
            }
            {CONST 
            :consttype 23 
            :consttypmod -1 
            :constlen 4 
            :constbyval true 
            :constisnull false 
            :constvalue 4 [ 100 0 0 0 ]
            }
         )
         }
         {OPEXPR 
         :opno 96 
         :opfuncid 65 
         :opresulttype 16 
         :opretset false 
         :args (
            {VAR 
            :varno 1 
            :varattno 1 
            :vartype 23 
            :vartypmod -1 
            :varlevelsup 0 
            :varnoold 1 
            :varoattno 1
            }
            {CONST 
            :consttype 23 
            :consttypmod -1 
            :constlen 4 
            :constbyval true 
            :constisnull false 
            :constvalue 4 [ -12 1 0 0 ]
            }
         )
         }
         {OPEXPR 
         :opno 96 
         :opfuncid 65 
         :opresulttype 16 
         :opretset false 
         :args (
            {VAR 
            :varno 1 
            :varattno 1 
            :vartype 23 
            :vartypmod -1 
            :varlevelsup 0 
            :varnoold 1 
            :varoattno 1
            }
            {CONST 
            :consttype 23 
            :consttypmod -1 
            :constlen 4 
            :constbyval true 
            :constisnull false 
            :constvalue 4 [ -24 3 0 0 ]
            }
         )
         }
      )
      }
   )
   }

Bitmap Heap Scan on accounts  (cost=13.04..24.97 rows=1 width=4) (actual time=0.000..0.000 rows=3 loops=1)
  Recheck Cond: ((aid = 100) OR (aid = 500) OR (aid = 1000))
  Filter: (bid = 1)
  ->  BitmapOr  (cost=13.04..13.04 rows=3 width=0) (actual time=0.000..0.000 rows=0 loops=1)
        ->  Bitmap Index Scan on accounts_pkey1  (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
              Index Cond: (aid = 100)
        ->  Bitmap Index Scan on accounts_pkey1  (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
              Index Cond: (aid = 500)
        ->  Bitmap Index Scan on accounts_pkey1  (cost=0.00..4.35 rows=1 width=0) (actual time=0.000..0.000 rows=1 loops=1)
              Index Cond: (aid = 1000)"
Total runtime: 0.000 ms

実行計画とプランツリーについて気づいたこと

  • 実行計画がどのように出力されるかはExplainOnePlan()あたりを見るとわかる
    • Recheck Cond は bitmapqualorig に対応
    • Filter は qual に対応
    • Index Cond は indexqualorig に対応
  • explain verboseだとPlannedStmtのノードが出力されない(デバッグ出力と異なりPlannedStmtのメンバのplanTreeが出力対象になっている)。だからどのリレーションにアクセスしようとしているのかわからない。
  • righttreeは空。

実行時の処理

とりあえずbtで呼び出しシーケンス(抜粋)。

(gdb) bt
#0  _bt_next (scan=0x84d5f48, dir=ForwardScanDirection) at nbtsearch.c:923
#1  0x080aee63 in btgetmulti (fcinfo=0xbfe18c20) at nbtree.c:326
#2  0x0831e0c5 in FunctionCall4 (flinfo=0x84f5a70, arg1=139288392, arg2=3219230352, arg3=1024, arg4=3219230348) at fmgr.c:1331
#3  0x080a8d85 in index_getmulti (scan=0x84d5f48, tids=0xbfe18e90, max_tids=1024, returned_tids=0xbfe18e8c) at indexam.c:708
#4  0x0819ed5e in MultiExecBitmapIndexScan (node=0x84d5e40) at nodeBitmapIndexscan.c:94
#5  0x0818f67e in MultiExecProcNode (node=0x84d5e40) at execProcnode.c:460
#6  0x0819e180 in MultiExecBitmapOr (node=0x84d5da0) at nodeBitmapOr.c:151
#7  0x0818f69e in MultiExecProcNode (node=0x84d5da0) at execProcnode.c:468
#8  0x0819e49e in BitmapHeapNext (node=0x84d4420) at nodeBitmapHeapscan.c:114
#9  0x08197b6b in ExecScan (node=0x84d4420, accessMtd=0x819e35c <BitmapHeapNext>) at execScan.c:103
#10 0x0819e97f in ExecBitmapHeapScan (node=0x84d4420) at nodeBitmapHeapscan.c:335
#11 0x0818f45d in ExecProcNode (node=0x84d4420) at execProcnode.c:344
#12 0x0818d14a in ExecutePlan (estate=0x84d4290, planstate=0x84d4420, operation=CMD_SELECT, numberTuples=0, direction=ForwardScanDirection, dest=0x8503a08) at execMain.c:1335

上位の関数から見ていく。

  • ExecBitmapHeapScan()
    • 実行計画のBitmap Heap Scanに対応。
  • ExecScan()
    • 関数ポインタを受け取って、個別処理はそっちに委譲する汎用処理。
    • 実行計画のFilterに相当するところを実行。
  • BitmapHeapNext()
    • ExecScan()に渡される関数ポインタの実体。
    • TIDBitmap型のデータから示されるブロックのタプルにアクセスし、TupleTableSlotに詰めて返す。
    • 実行計画のRecheck Condに対応する処理はlossyのときにのみ行われる。
  • MultiExecBitmapOr()
    • 実行計画のBitmapOrに対応。
    • 下位の結果をビットマップに束ねて(unionして)返す。要するに複数タプルの情報を返す。
    • 今回のように下位のノードがBitmapIndexScanStateときはunionの処理は省かれている。重複が発生しないことがわかっているからだと思う。
  • btgetmulti()
    • 最初の実行かどうかで_bt_first()と_bt_next()を呼び出し分けている。
    • 複数のTID(structとしてはItemPointer)を返す。このTIDはこの例だとaccountsテーブルのある特定のブロックとそのオフセット番号のこと。

まとめ

実行計画が実行される順番で見ていくとこうなる。

  • 3つのBitmap Index Scanがあるが、この処理ごとにインデックスアクセスし複数のTIDを取得する(今回のようにインデックスがユニークの場合は1度のBitmap Index Scanで1件しかヒットしないが)。
  • BitmapOrでTIDをまとめる。この時点でアクセスしているのTIDだけ。まだタプルの実体にアクセスしていない。
  • Bitmap Heap Scanで実際にリレーション(テーブル)のブロックにアクセスしタプルを取り出す。
    • lossyならRecheck Condのチェック。
    • Filterの処理。

lossyはよくわかっていない。今は大きなデータのときに採用される方法というくらいの認識で。

2009-04-11

[][] EXPLAINでプランツリーの出力

explain verbose 
select * from hoge;

みたいにexplain verboseとすると実行計画と一緒にプランツリーも出力してくれる。そうか、postgresql.confでdebug_print_planを設定しなくてもプランツリーが確認できるのか。

ところで、実行計画の見方は公式のドキュメント以外に次のサイトがとても参考になる。

関連して、次のページも興味深い。PostgreSQL 8.4 からauto_explainというのが可能みたい。

2009-04-10

[][] エクゼキュータ。集約(Aggregate)

適当なクエリを流して、GROUP BYによる集約がどう実行されるのか見てみた。

DDLとデータ
create table person (
  name text primary key,
  country text not null,
  age integer not null
);

insert into person values
('aaa', 'jp', 20),
('bbb', 'us', 30),
('ccc', 'jp', 30),
('ddd', 'us', 20),
('eee', 'us', 20);
クエリ

国別の集計で人の年齢の合計が50より大きくなる国。

select 
  country, 
  sum(age) as age 
from 
  person 
group by 
  country 
having 
  sum(age) > 50;
実行計画
 HashAggregate  (cost=24.52..28.02 rows=200 width=36)
   Filter: (sum(age) > 50)
   ->  Seq Scan on person  (cost=0.00..18.30 rows=830 width=36)
プランツリー

昨日の設定で出力。

DEBUG:  plan:
DETAIL:     {PLANNEDSTMT
           :commandType 1
           :canSetTag true
           :planTree
              {AGG
              :startup_cost 24.52
              :total_cost 28.02
              :plan_rows 200
              :plan_width 36
              :targetlist (
                 {TARGETENTRY
                 :expr
                    {VAR
                    :varno 65001
                    :varattno 2
                    :vartype 25
                    :vartypmod -1
                    :varlevelsup 0
                    :varnoold 1
                    :varoattno 2
                    }
                 :resno 1
                 :resname country
                 :ressortgroupref 1
                 :resorigtbl 32944
                 :resorigcol 2
                 :resjunk false
                 }
                 {TARGETENTRY
                 :expr
                    {AGGREF
                    :aggfnoid 2108
                    :aggtype 20
                    :args (
                       {VAR
                       :varno 65001
                       :varattno 3
                       :vartype 23
                       :vartypmod -1
                       :varlevelsup 0
                       :varnoold 1
                       :varoattno 3
                       }
                    )
                    :agglevelsup 0
                    :aggstar false
                    :aggdistinct false
                    }
                 :resno 2
                 :resname age
                 :ressortgroupref 0
                 :resorigtbl 0
                 :resorigcol 0
                 :resjunk false
                 }
              )
              :qual (
                 {OPEXPR
                 :opno 419
                 :opfuncid 477
                 :opresulttype 16
                 :opretset false
                 :args (
                    {AGGREF
                    :aggfnoid 2108
                    :aggtype 20
                    :args (
                       {VAR
                       :varno 65001
                       :varattno 3
                       :vartype 23
                       :vartypmod -1
                       :varlevelsup 0
                       :varnoold 1
                       :varoattno 3
                       }
                    )
                    :agglevelsup 0
                    :aggstar false
                    :aggdistinct false
                    }
                    {CONST
                    :consttype 23
                    :consttypmod -1
                    :constlen 4
                    :constbyval true
                    :constisnull false
                    :constvalue 4 [ 50 0 0 0 ]
                    }
                 )
                 }
              )
              :lefttree
                 {SEQSCAN
                 :startup_cost 0.00
                 :total_cost 18.30
                 :plan_rows 830
                 :plan_width 36
                 :targetlist (
                    {TARGETENTRY
                    :expr
                       {VAR
                       :varno 1
                       :varattno 1
                       :vartype 25
                       :vartypmod -1
                       :varlevelsup 0
                       :varnoold 1
                       :varoattno 1
                       }
                    :resno 1
                    :resname <>
                    :ressortgroupref 0
                    :resorigtbl 0
                    :resorigcol 0
                    :resjunk false
                    }
                    {TARGETENTRY
                    :expr
                       {VAR
                       :varno 1
                       :varattno 2
                       :vartype 25
                       :vartypmod -1
                       :varlevelsup 0
                       :varnoold 1
                       :varoattno 2
                       }
                    :resno 2
                    :resname <>
                    :ressortgroupref 0
                    :resorigtbl 0
                    :resorigcol 0
                    :resjunk false
                    }
                    {TARGETENTRY
                    :expr
                       {VAR
                       :varno 1
                       :varattno 3
                       :vartype 23
                       :vartypmod -1
                       :varlevelsup 0
                       :varnoold 1
                       :varoattno 3
                       }
                    :resno 3
                    :resname <>
                    :ressortgroupref 0
                    :resorigtbl 0
                    :resorigcol 0
                    :resjunk false
                    }
                 )
                 :qual <>
                 :lefttree <>
                 :righttree <>
                 :initPlan <>
                 :extParam (b)
                 :allParam (b)
                 :scanrelid 1
                 }
              :righttree <>
              :initPlan <>
              :extParam (b)
              :allParam (b)
              :aggstrategy 2
              :numCols 1
              :grpColIdx 2
              :grpOperators 98
              :numGroups 200
              }
           :rtable (
              {RTE
              :alias <>
              :eref
                 {ALIAS
                 :aliasname person
                 :colnames ("name" "country" "age")
                 }
              :rtekind 0
              :relid 32944
              :inh false
              :inFromCl true
              :requiredPerms 2
              :checkAsUser 0
              }
           )
           :resultRelations <>
           :utilityStmt <>
           :intoClause <>
           :subplans <>
           :rewindPlanIDs (b)
           :returningLists <>
           :rowMarks <>
           :relationOids (o 32944)
           :nParamExec 0
           }
  • GROUP BYはAGGで、集約関数はAGGREFで表されている。
  • HAVINGはAGGのqualにあるOPEXPRで表されている。
  • personテーブルへの順スキャンのノードはAGGのlefttreeで。
  • AGGのrighttreeは空。
  • AGGのaggstrategy=2は集約にハッシュテーブルを使うことを表す。ほかにはソートを使う手法があるよう。

集約はExecAgg()で行われる。

TupleTableSlot *
ExecAgg(AggState *node)

だいたいこんな感じの処理が行われる。

  • lefttreeのノードを実行し、返されるタプルをグループごとにハッシュテーブルに格納する。
  • 集約関数の計算をする。
  • 全件をハッシュテーブルに入れ終えたら、ハッシュテーブルのエントリを順に見て(HAVINGの)条件に満たすものを探す。
    • あれば呼び出し元に返す、なければ次のエントリを探す。
  • 次に実行されたら、ハッシュテーブルのまだチェックしていないエントリを順に見ていく。
  • すべてのエントリをチェックしたら終了。
  • 条件を満たすかどうかのチェックは、ExecQual()で行われる。ExprStateの関数ポインタで式が評価されるためロジックが一様ではない。

2009-04-09

[][] プランツリーのデバッグ出力

http://www.postgresql.jp/document/pg835doc/html/runtime-config-logging.html#RUNTIME-CONFIG-LOGGING-WHAT

postgresql.confのパラメタを変更すればパースツリー、クエリツリー、プランツリーを自動でログ出力できるみたい。そうかわざわざgdbからcall pprint()する必要なかったのか。

とりあえずプランツリーについてだけログ出力されるように設定した。

  • log_min_messages = debug1
  • debug_print_plan = true
  • debug_pretty_print = true

きれいに出力できた。

[][] エクゼキュータ。ネストループ結合(Nested Loop Join)

ネストループ結合はExecNestLoop()で実行される。

  TupleTableSlot *
  ExecNestLoop(NestLoopState *node)

気づいたこと書いてみる(順番は関係ない)。

  • outerとinnerをスキャンして比較項目が合致したらそれをTupleTableSlotとして返す。
  • 返すのは1件だけ。(呼び出し元で1件ずつ処理するので。outerがNULLを返すまでこの関数は何度でも呼ばれる。)
  • ExecNestLoop()では内側のループしかない。外側のループは呼び出し元になるのだと思う。例えばExecNestLoop()のループとか。innerがNULLを返したらExecNestLoop()のループを抜けずに次のouterを読んでた。
  • 1つのouterのタプルにつきinnerをNULLが返されるまで何度もスキャンする。
    • 内部結合のときはinnerがNULLを返したら次のouterを読もうとするが、外部結合のときは処理をつづける。
  • outerをスキャンした後、innerを先頭からスキャンする前にExecReScan()を呼ぶ。ReはResetのReらしい。innerのスキャン結果を保持するところなどを初期化しているよう。
  • 射影をしてから返す。
  • 結合の比較は演算子に対応する関数(int4eq()など)で行われる。
  • outerやinnerのタプルはExprContextというstructに保持される。ExprContextはExecReScan()やExecQual()の関数に渡される。

2009-04-08

[][] エクゼキュータ。PlanStateとExprState

クエリの実行では、プランツリーがそのまま使われるわけではなく、プランツリー(Plan)から変換されたプランステート(PlanState)が使われる。変換を行うのはExecInitNode()。ExecInitNodeのシグネチャは次のとおり。

PlanState *
ExecInitNode(Plan *node, EState *estate, int eflags)

PlanStateの継承関係はPlanの継承関係にほととんどそのまま対応する。すべてexecnodes.hに定義されている。継承関係は次のとおり。

PlanState
 +--ResultState
 +--AppendState
 +--BitmapAndState
 +--BitmapOrState
 +--ScanState
     +--SeqScanState
     +--IndexScanState
     +--BitmapIndexScanState
     +--BitmapHeapScanState
     +--TidScanStateState
     +--SubqueryScanState
     +--FunctionScanState
     +--ValuesScanState
     +--MaterialState                ※ Planの継承関係と一致していない
     +--SortState                    ※ Planの継承関係と一致していない
     +--GroupState                   ※ Planの継承関係と一致していない
     +--AggState                     ※ Planの継承関係と一致していない
 +--JoinState
     +--NestLoopState
     +--MergeJoinState
     +--HashJoinState
 +--UniqueState
 +--HashState
 +--SetOpState
 +--LimitState

なぜか、MaterialState、SortState、GroupState、AggStateがPlanのときと継承関係が一致していない。


ExecInitNode()すると、プランツリーにぶらさがるExprはExprStateに変換されPlanStateにぶらさがる。これらもexecnodes.hで定義されている。ExprStateを親とした継承関係がある。

ExprState
 +--GenericExprState
 +--AppendState
 +--AggrefExprState
 +--ArrayRefExprState
 +--FuncExprState
     +--ScalarArrayOpExprState
 +--BoolExprState
 +--SubPlanState
 +--FieldSelectState
 +--FieldStoreState
 +--CoerceViaIOState
 +--ArrayCoerceExprState
 +--ConvertRowtypeExprState
 +--CaseExprState
 +--CaseWhenState
 +--ArrayExprState
 +--RowExprState
 +--RowCompareExprState
 +--CoalesceExprState
 +--MinMaxExprState
 +--XmlExprState
 +--NullTestState
 +--CoerceToDomainState

ExprStateは元の式に応じて関数ポインタがセットされるようになっている。評価されるときに呼び出されるのだと思う。名前だけ何をやるのか想像がつくものもあればよくわからないのもある。


クエリの実行でPlanStateのノードを処理しているのはExecProcNode()。ExecProcNodeのシグネチャは次のとおり。

TupleTableSlot *
ExecProcNode(PlanState *node)

ここから下の処理を読むと実行計画がどのように処理されていくかわかるはず。


追記

PlanStateのノードをpprintでデバッグ出力したかったのだけどできなかった。対応していないみたい。