PostgreSQL プラン・ツリーの概要

この記事はPostgreSQL Advent Calendar 2014の1日目の記事である。

この記事は PostgreSQL 9.4 と 9.5 に基づいて記述している。

このページでは PostgreSQL のプラン情報を保持するノード・ツリーの概略を解説する。また PostgreSQL の生成するプランのノード・ツリー情報を可視化するために、Graphviz の dot ファイルとして書き出すエクステンション pg_plan_tree_dot を紹介する。 PostgreSQL 本体の改造やエクステンションを作成するために、プランを変更しようとする人向けの記事である。

現在は pg_plan_tree_dot は Linux の PostgreSQL 9.x 上でだけ動作する。

PostgreSQL の他の記事へのインデックスはここ。

更新履歴
(2014.11.30) 作成。
(2015.12.13) エクスプレッション・ノードとプラン・ノードを追加
(2016.09.24) Join と TargetEntry の説明を追加
(2017.01.07) 各種例外事項について記述を追加

1. PostgreSQL の実行の流れ
2. pg_plan_tree_dot エクステンション
- 2.1 インストール
- 2.2 使い方
3. プランツリー(Plan Tree)を構成するノード
4. 各プラン・ノードのはたらき
- 4.1 Scan
  - 4.1.1 SeqScan
  - 4.1.2 IndexScan
  - 4.1.3 BitmapHeapScan
  - 4.1.4 TidScan
  - 4.1.5 SubqueryScan
  - 4.1.6 FunctionScan
  - 4.1.7 ValuesScan
  - 4.1.8 CteScan
  - 4.1.9 WorkTableScan
  - 4.1.10 ForeignScan
- 4.2 Sort
- 4.3 Agg
- 4.4 WindowAgg
- 4.5 Join
- 4.6 サブクエリーの結合に関係するプラン・ノード
- 4.7 補助的なプラン・ノード
- 4.8 更新に関係するプラン・ノード
  - 4.8.1 ModifyTable
  - 4.8.2 LockRows
コメント

1. PostgreSQL の実行の流れ

PostgreSQL は与えられた SQL ステートをパースし、まずクエリー・ツリー(Query Tree)を作成する。これをプランナー(planner)に渡して最適化を行い、プラン・ツリー(Plan Tree)に変換する。プラン・ツリーは PostgreSQL がどのように処理を行うかの設計図である。プラン・ツリーをエグゼキューター(executor)に渡すことで実行が開始される。

エグゼキューターは ExecutorStart、ExecutorRun、ExecutorFinish、ExecutorEnd の 4 つフェーズに分かれている。最初の ExecutorStart でプラン・ツリーはプラン・ステート・ツリー(Plan State Tree)へ変換される。プラン・ステート・ツリーは、プラン・ツリーに実行に必要なメモリの割り当てなどを行った情報である。プラン・ステート・ツリーが最終的な表現になり、これを使って ExecutorRun を行う。 ExecutorRun が実行の中心になる。 ExecutorFinish、ExecutorEnd は後始末の処理になる。

Flow of PostgreSQL — fig-1: PostgreSQL の実行の流れ

PostgreSQL が SQL をどのように処理するかはプラン・ツリーで決定されている。よって PostgreSQL を改造したい場合、プラン・ツリーの理解が必要になる。しかしプラン・ツリー情報を直接的に吐き出す機能は PostgreSQL には存在しない。 EXPLAIN コマンドはプラン・ツリーの情報の一部を表示するが欠落している情報が多い。

そこで pg_plan_tree_dot エクステンションを作成した。 pg_plan_tree_dot エクステンションを使うとプラン・ツリーの情報を Graphviz を使ってグラフ化することができる。

2. pg_plan_tree_dot エクステンション

現在の pg_plan_tree_dot は更新系のクエリーではエラーで落ちるかもしれない。

2.1 インストール

pg_plan_tree_dot エクステンションを使うにはソースコードをダウンロードしてコンパイルを行う必要がある。

まず適当な Linux のディストリビューションに PostgreSQL 9.x、graphviz、C と C++ の開発環境がインストールされているものとして扱う。

PostgreSQL の bin/ ディレクトリには事前に実行パスを通しておくこと。例えば .bash_profile に以下のようにパスを通す。

POSTGRESQL=$HOME/postgresql-install-dir
PATH=$PATH:$POSTGRESQL/bin

pg_plan_tree_dot エクステンションのコンパイルに必要になる pg_config コマンドにパスが通っているか確認する。

$ which pg_config
~/postgresql-install-dir/bin/pg_config

ソースコードを github からダウンロードし、コンパイルを行う。

$ git clone https://github.com/nminoru/pg_plan_tree_dot
$ cd pg_plan_tree_dot
$ make

最後に make install でインストールを行う。インストール先のパーミッションによっては root の実行権限で行う必要がある。

$ make install

2.2 pg_plan_tree_dot の使い方

pg_plan_tree_dot エクステンションを使うためにはまず CREATE EXTENSION コマンドで登録する。

CREATE EXTENSION pg_plan_tree_dot;

いったん登録した pg_plan_tree_dot エクステンションを削除したい場合は DROP EXTENSION コマンドを使用する。

DROP EXTENSION pg_plan_tree_dot;

プランツリーを出力したい場合は generate_plan_tree_dot 関数を呼び出す。第一引数は SQL クエリーを文字列として渡し、第二引数は出力する dot ファイルを指定する。 SQL クエリーの文字列中に ' が使われている場合は、'' のようにエスケープして渡す必要がある。

SELECT generate_plan_tree_dot('SQL query', 'output.dot');

実行すると output.dot が作成される。これを Graphviz の dot コマンドを使って画像ファイルを作成する。

dot -Tpng output.dot -o output.png

以下のような SQL を実行した場合、

CREATE TABLE employee (
       ID         int PRIMARY KEY,
       name       varchar(10),
       salary     real,
       start_date date,
       city       varchar(10),
       region     char(1));

INSERT INTO employee VALUES (1,  'Jason', 40420,  '94/02/01', 'New York', 'W');
INSERT INTO employee VALUES (2,  'Robert',14420,  '95/01/02', 'Vancouver','N');
INSERT INTO employee VALUES (3,  'Celia', 24020,  '96/12/03', 'Toronto',  'W');
INSERT INTO employee VALUES (4,  'Linda', 40620,  '87/11/04', 'New York', 'N');
INSERT INTO employee VALUES (5,  'David', 80026,  '98/10/05', 'Vancouver','W');
INSERT INTO employee VALUES (6,  'James', 70060,  '99/09/06', 'Toronto',  'N');
INSERT INTO employee VALUES (7,  'Alison',90620,  '00/08/07', 'New York', 'W');
INSERT INTO employee VALUES (8,  'Chris', 26020,  '01/07/08', 'Vancouver','N');
INSERT INTO employee VALUES (9,  'Mary',  60020,  '02/06/09', 'Toronto',  'W');

-- test-01-1
SELECT generate_plan_tree_dot('SELECT region FROM employee GROUP BY region;', 'test-01-1.dot');

-- test-01-2
SELECT generate_plan_tree_dot('SELECT region FROM employee ORDER BY ID;',     'test-01-2.dot');

DROP TABLE employee;

以下のような test-01-1.dot、test-01-2.dot のような dot ファイルが生成される。これを dot コマンドで PNG 画像を生成すると test-01-1.png、test-01-2.png のようになる。

3. プラン・ツリー(Plan Tree)を構成するノード

プラン・ツリーは複数の種類のノードによって構成されている。これを順に説明する。

3.1 Nodes

プラン・ツリーを説明する前に PostgreSQL に使われているノード(Node) の構造を確認する。 PostgreSQL のノードは全て構造体の第一フィールドに NodeTag 列挙子で定義されたノード種類の情報を持っている。 PostgreSQL はこれを使って疑似オブジェクト指向を行っている。

typedef struct Node
{
    NodeTag type;
} Node;

NodeTag 列挙子は include/nodes/nodes.h で定義されており、大雑把に以下の表のように分類されている。

NodeTag の種類
ノード種類	NodeTag 番号	説明	例
Executor Nodes	10 ～ 99	実行時に補助的に利用するノード	ExprContext、ProjectionInfo、EState、TupleTableSlot
Plan Nodes	100 ～ 199	プラン・ノード	Scan、Agg、Sort、Union
Plan State Nodes	200 ～ 299	プラン・ステート・ノード。プラン・ノードに実行のために必要な情報(メモリ、システムカタログから検索した情報)を足したノード。プラン・ノードと一対一のプラン・ステート・ノードが存在する。	ScanState、AggState、SortState
Expression Nodes (Primitive Nodes)	300 ～ 399	プランに付随する式を表現するためのノード。	OpExpr、FuncExpr、Aggref、Var、Const、Param
Expression State Nodes	400 ～ 499	プラン・ノード→プラン・ステート・ノードのように、エクスプレッション・ノードに実行のために必要な情報を足したノード。エクスプレッション・ノードとだいたい一対一のエクスプレッション・ステート・ノードが存在する。	FuncExprState、GenericState、AggrefState
Planner Nodes	500 ～ 599	Planner/optimizer 内で使うノード。アクセスパスもここに含まれる。プランが生成される段階では存在しない。
Memory Context	600、601	メモリ管理情報を持つノード。プラン以外でも PostgreSQL 全体で使われる。	MemoryContext、AllocSetContext
Value Nodes	650 ～	数値データやリストのプリミティブ。PostgreSQL 全体で利用される。	Integer、Float、String、List
Statement Nodes	800 ～	SQL クエリーの種類を記録し、他のノードツリー全体のプレイスフォルダーになるノード。	Query、PlannedStmt、InsertStmt、DeleteStmt、UpdateStmt
Parse Tree Nodes	900 ～	クエリーのパース時に使われるノード。プランが生成される段階では存在しない。

プラン・ツリーは 100～199 のプラン・ノード(Plan Node)、300 ～ 3999 のエクスプレッション・ノード(Expression Node)、650 台の Value Node から構成される。プラン・ツリー全体は statement node の一種である PlannedStmt ノードに連結して管理される。

3.2 PlannedStmt

まずプランツリーはそれを格納するプレイスフォルダーになっている PlannedStmt ノードがある。これが起点となる。 PlannedStmt ノードの構造体は以下のようになる。

typedef struct PlannedStmt
{
    NodeTag     type;
    CmdType     commandType;    /* select|insert|update|delete */
    uint32      queryId;        /* query identifier (copied from Query) */
    bool        hasReturning;   /* is it insert|update|delete RETURNING? */
    bool        hasModifyingCTE;    /* has insert|update|delete in WITH? */
    bool        canSetTag;      /* do I set the command result tag? */
    bool        transientPlan;  /* redo plan when TransactionXmin changes? */
    struct Plan *planTree;      /* tree of Plan nodes */
    List       *rtable;         /* list of RangeTblEntry nodes */
    /* rtable indexes of target relations for INSERT/UPDATE/DELETE */
    List       *resultRelations;    /* integer list of RT indexes, or NIL */
    Node       *utilityStmt;    /* non-null if this is DECLARE CURSOR */
    List       *subplans;       /* Plan trees for SubPlan expressions */
    Bitmapset  *rewindPlanIDs;  /* indices of subplans that require REWIND */
    List       *rowMarks;       /* a list of PlanRowMark's */
    List       *relationOids;   /* OIDs of relations the plan depends on */
    List       *invalItems;     /* other dependencies, as PlanInvalItems */
    int         nParamExec;     /* number of PARAM_EXEC Params used */
    bool        hasRowSecurity; /* row security applied? */
} PlannedStmt;

PlannedStmt 構造体の中で、プランツリーを理解するためには planTree、subplans、rtable が特に重要である。

プランツリーはプランノードの木構造だが、planTree からつながっているメインとなるプランツリーと subplans にリストとしてつながっている複数のサブプランのプランツリーから構成される。
- planTree が最初に実行されるプランツリーであり、必要に応じて subplans の下にあるサブプランを呼び出す。
- subplans は主にサブクエリー(副問い合わせ, subquery)から作成されるサブプランツリーである。
rtable は subplans も含めたプランツリー内でアクセスされるテーブルの情報を RangeTableEntry のリストの形で保持している。同様に relationOids はアクセスされるテーブルの Oid のリストを持っている。

これ以外にも PlannedStmt 構造体は、プランを実行するための諸情報を記録している。

3.3 リスト(List)

リストは他のノードを繋げる糊としてはたらくノードである。エクスプレッション・ノードとプラン・ノードの一部で利用される。 pg_plan_tree_dot では下の図のような形で表現する。

3.4 プラン・ノード(Plan Nodes)

プラン・ノードの基本になっているのは Plan 構造体だ。

typedef struct Plan
{
    NodeTag         type;
    Cost            startup_cost
    Cost            total_cost;
    double          plan_rows;
    int             plan_width;

    List           *targetlist;
    List           *qual;
    struct Plan    *lefttree;
    struct Plan    *righttree;
    List           *initPlan;

    Bitmapset      *extParam;
    Bitmapset      *allParam;
} Plan;

Plan は lefttree と righttree によって別の 2 つのプラン・ノードに繋がることができる。 lefttree に繋がって入るのが outer (plan) node、righttree に繋がって入るのが inner (plan) node と呼ぶ。プラン・ノードが実際に outer plan node と inner plan node を持つかどうかは種類による。

スキャン系ノードは別に入力を持たないので入力プラン・ノードを持たない。
ジョイン系ノードは outer plan node とinner plan node の両方を持つ。
それ以外のノードは 1 つだけ入力プラン・ノードを持つ。入力が 1 つだけの場合は lefttree が使われ outer plan node 扱いとなる。

ちなみに根(ルート)に近いほうが上位ノードであり、葉(リーフ)に近い方が下位ノードである。 PostgreSQL のソースコード内では最上位のプランノードを topmost plan node と呼んでいる。

targetlist はターゲット・リストと呼ばれ、このプランの出力タプルのフォーマットと、場合によっては出力のために必要な演算を指示する。 SELECT コマンドの選択句がこのターゲット・リストに変換される。ターゲット・リストの詳細は3.6で説明する。

qual はプランがフィルターをかける際に利用するエクスプレッション・ツリーである。 WHERE 句は qual となる。プランによっては qual が使われずに、独自のフィールドが使われることがある。

RDBMS の用語としてはプラン(Plan) と PostgreSQL ソースコード中の Plan 構造体は概念が一致しないので注意が必要となる。

RDBMS 用語としてのプランは、与えられたクエリーを実行するためのプランノード・ツリー全体を指している。一方、Plan 構造体は、プランの一部分であるプランノードをあらわすデータ構造である。 outerPlan() など

同様にサブプランはプランノード・ツリーの一部、部分木にあたる。 SQL 中のサブクエリー(副問い合わせ)からサブプランができることが多い(サブクエリーがサブプランを生成しないこともある)。

Plan 構造体内の情報はそれが指すプランノードの情報を指しているが、initPlan は例外である。これはプランノードの情報ではなく、サブプランの情報を保持している。

initPlan はプランノードツリーの中で各サブプランの topmost plan node が代表して保持している。 Topmost plan node 以外は initPlan は NIL になる。もしプランの書き換えを行い、topmost plan node の前に新しい別のプランノードを挿入した場合、initPlan を移動させる必要がある。

Plan 構造体によるプランノードは C++ 言語で言うところの純粋仮想関数を持つ抽象クラスであり、Plan がそのまま利用されることはなく「継承」した構造体を用いる。例えば Sort の場合は以下のような構造体となる。

typedef struct Sort
{
    Plan        plan;
    int         numCols;
    AttrNumber *sortColIdx;
    Oid        *sortOperators;
    Oid        *collations;
    bool       *nullsFirst;
} Sort;

Plan が「抽象クラス」だが、他にスキャン系ノードの基底となっている Scan と、ジョイン系ノードの基底となっている Join も「抽象クラス」である。これらも派生した型が利用され、Scan/Join 自身は直接は生成されない。

プラン・ノードの全種類を以下にしめす。スキャン系とジョイン系には二番目の階層がある。 NestLoopParam、PlanRowMark、PlanInvalItem は Plan からの派生ではない。これらは他のプランのパラメータを保持するために利用される。

Node
- Plan (抽象クラス)
  - Scan (抽象クラス)
    - SeqScan
    - IndexScan
    - IndexOnlyScan
    - BitmapIndexScan
    - BitmapHeapScan
    - TidScan
    - SubqueryScan
    - FunctionScan
    - ValuesScan
    - CteScan
    - ForeignScan
  - Join (抽象クラス)
    - NestLoop
    - MergeJoin
    - HasJoin
  - Material
  - Sort
  - Group
  - Agg
  - WindowAgg
  - Unique
  - Hash
  - SetOp
  - LockRows
  - Limit
  - Result
  - ModifyTable
  - Append
  - MergeAppend
  - RecursiveUnion
  - BitmapAnd
  - BitmapOr
- NestLoopParam
- PlanRowMark
- PlanInvalItem

個々のプラン・ノードの説明は先にエクステンション・ノードを説明してから行う。

3.5 エクスプレッション・ノード(Expression Nodes)

エクスプレッション・ノードは式の表現などに使われるノードである。基底となるのは Expr だが、これも C++ の抽象クラスな構造体である。

typedef struct Expr
{
    NodeTag         type;
} Expr;

プラン・ノードとして使われるエクスプレッション・ノードは以下のようなものがある(クエリー・ツリーや planner の内部だけで使われるエクスプレッション・ノードは他に存在する)。

エクスプレッション・ノードの種類
Expression	説明	参照
Aggref	集約の集約句を保持する。	3.5.7.。機能の説明は4.3で行う
AlternativeSubPlan	サブプラン呼び出しを行う SubPlan の補助。2 つのサブプランを提示しておき、実行開始時にコストが小さい方を実行する。
ArrayCoerceExpr	配列(array)を別の要素型の配列に変換する。
ArrayExpr	ARRAY[] に対応。
ArrayRef	配列(array)から要素を取り出す。
BooleanTest	IS (NOT) TRUE、IS (NOT) FALSE、IS (NOT) UNKNOWN に対応。
BoolExpr	AND、OR、NOT に対応。	3.5.4
CaseExpr、CaseTestExpr、CaseWhen	CASE 句に対応。この 3 つのエクスプレッション・ノードは組み合わせて利用する。	3.5.5
CoalesceExpr	COALESCE 句に対応。
CoerceToDomain、CoerceoDomainValue	CREATE DOMAIN で生成するドメインの制約チェックを行うエクスプレッション・ノード。
CoerceViaIO	データをテキストへ変換あるいはテキストからデータへ変換する箇所で利用。JSON 型と JSONB 型との相互変換や、CREATE CAST WITH INOUT で定義されたキャスト式で利用。
Const	定数値を保持するエクスプレッション・ノード。	3.5.2
ConvertRowtypeExpr	複合型(composite type)を別の型に変換する。
CurrentOfExpr	CURRENT OF 句に対応に対応。
DistinctExpr	x IS DISTINCT FROM y 構文に対応。互換性のために残されたエクスプレッション・ノードのようだ。
FieldSelect	行(ROW)からカラムを取り出す処理に対応。複合型(composite type)からメンバーを取り出すの場合にも出現する。
FieldStore	タプル中の特定カラムを書き換える。UPDATE 操作で出現。
FuncExpr	関数呼び出しに対応。	3.5.3
GroupingFunc	PostgreSQL 9.5 から登場。GROUPING 句に対応。
MinMaxExpr	GREATEST、LEAST に対応。
NullIfExpr	NULLIF に対応。
NullTest	IS (NOT) NULL に対応。
OpExpr	演算の処理に対応。関数呼び出しは FuncExpr、演算は OpExpr と生成されるエクスプレッション・ノードの違いがあるが、実行時には両者はほぼ同等に処理される。	3.5.3
Param	「パラメータ」を参照するエクスプレッション・ノード。パラメータの解説は 3.5.6 を参照。	3.5.6
RelabelType	簡単な型変換を行うノード。例えば OID 型から int4 型のような実質何もしない型変換なので出現する。
RowCompareExpr	(a,b) >= (1, 2) のような行(ROW)同士の比較演算に対応。
RowExpr	ROW() に対応。
ScalarArrayOpExpr	scalar op ANY/ALL (array) のような構文に対応。
TargetEntry	ターゲットリスト(target list)の構成要素を示すために利用。	3.6
Var	下位ノードから受け取ったデータを参照するのに利用。	3.5.1
WindowFunc	Window 関数処理に利用すると思われる。
XmlExpr	XML 処理に利用すると思われる。

3.5.1 Var

Var ノードは、そのプラン内のデータ(タプル)を参照して読み込み、上位ノードに返す。

typedef struct Var
{
    Expr            xpr;
    Index           varno;          /* index of this var's relation in the range table,
                                       or INNER_VAR/OUTER_VAR/INDEX_VAR */
    AttrNumber      varattno;       /* attribute number of this var, or zero for all */
    Oid             vartype;        /* pg_type OID for the type of this var */
    int32           vartypmod;      /* pg_attribute typmod value */
    Oid             varcollid;      /* OID of collation, or InvalidOid if none */
    Index           varlevelsup;    /* for subquery variables referencing outer relations;
                                       0 in a normal var, <0 means N levels up */
    Index           varnoold;       /* original value of varno, for debugging */
    AttrNumber      varoattno;      /* original value of varattno */
    int             location;       /* token location, or -1 if unknown */
} Var;

varno は Var で読み込むデータ(タプル)の位置を示すデータである。

varno が OUTER_VAR(65001) であれば outer node からタプルを読み込むことを意味する。
varno が INNER_VAR(65000) であれば inner node からタプルを読み込むことを意味する。
スキャン系プラン・ノードでは varno が 1 以上の正の整数の場合があるが、これはテーブルスキャン時に読み込むテーブルの指定する。これは relid を指すのだが、その意味はScan を説明する際に述べる。
スキャン系プラン・ノードの中でも IndexScan プランなどインデックスを用いるスキャン系プラン・ノードが、インデックスのデータを読み取る場合は varno が INDEX_VAR(65002) に設定される。

OUTER_VAR は Plan 構造体の lefttree につながった outer node からタプルを読むが、プランノードが Append や MergeAppend の場合には例外がある。

Append は SQL で UNION 句を利用した時に出現するプランノードだが、A UNION B UNION C UNION D; のように複数のサブプランを同時に扱える。このため一つのプランノードへのポインタである lefttree ではなく、プランノードへのリストである appendplans を使う。 Append のターゲットリストに varno が OUTER_VAR に設定された Var が出現した場合、appendplans の先にあるプランノードのうち現在処理中のノードの出力タプルを指すことになる。

MergeAppend の場合も同様である。ただし mergeplans になる。

varattno が 1 以上の場合、varno が指定したタプル読込先のどのカラムからデータを読み取るかを指定する。 varno にテーブルが指定された場合、varattno が 0 以下の場合がありえる。 0 の場合は whole-row を、負の数の場合はシステム列を指定したことになる。

Whole-row Var は、sample-whole-row.sql の SELECT concat_selected_fields(employee.*) FROM employee; のようなパターンで出現する(結果:sample-whole-row.dot、sample-whole-row.png)。

システム列は以下の表のような意味がある。

マクロ名	varattno	システム列
SelfItemPointerAttributeNumber	-1	ctid
ObjectIdAttributeNumber	-2	oid
MinTransactionIdAttributeNumber	-3	xmin
MinCommandIdAttributeNumber	-4	cmin
MaxTransactionIdAttributeNumber	-5	xmax
MaxCommandIdAttributeNumber	-6	cmax
TableOidAttributeNumber	-7	tableoid

vartype は Var の結果の型を返す pg_type システムカタログ中の OID、vartypemod は一部の型の可変長情報などの補助情報を持っている。

3.5.2 Const

Const ノードは定数値を保持している。

3.5.3 OpExpr、FuncExpr、DistinctExpr、NullIfExpr

OpExpr ノードは SQL 中の演算子、FuncExpr ノードは関数呼び出し、DistinctExpr ノードは DISTINCT から、NullIfExpr ノードは NULLIF から生成されるノードである。種類の差はあるがいずれも pg_func システムカタログに登録された関数を呼び出すためのノードである。

OpExpr と FuncExpr は以下のような構造体を持っている。 DistinctExpr と NullIfExpr は OpExpr の typedef である。

typedef struct OpExpr
{
    Expr        xpr;
    Oid         opno;           /* PG_OPERATOR OID of the operator */
    Oid         opfuncid;       /* PG_PROC OID of underlying function */
    Oid         opresulttype;   /* PG_TYPE OID of result value */
    bool        opretset;       /* true if operator returns set */
    Oid         opcollid;       /* OID of collation of result */
    Oid         inputcollid;    /* OID of collation that operator should use */
    List       *args;           /* arguments to the operator (1 or 2) */
    int         location;       /* token location, or -1 if unknown */
} OpExpr;

typedef struct FuncExpr
{
    Expr        xpr;
    Oid         funcid;         /* PG_PROC OID of the function */
    Oid         funcresulttype; /* PG_TYPE OID of result value */
    bool        funcretset;     /* true if function returns set */
    bool        funcvariadic;   /* true if variadic arguments have been
                                 * combined into an array last argument */
    CoercionForm funcformat;    /* how to display this function call */
    Oid         funccollid;     /* OID of collation of result */
    Oid         inputcollid;    /* OID of collation that function should use */
    List       *args;           /* arguments to the function */
    int         location;       /* token location, or -1 if unknown */
} FuncExpr;

OpExpr や FuncExpr は、args の子エクスプレッション・ノードのリストがつながっている。 OpExpr や FuncExpr を評価する場合、先に args の先にある子エクスプレッション・ノードを評価して、それを関数の引数として扱う。

opfuncid、funcid は pg_proc システムカタログに登録された OID で、呼び出し関数を示す。

opresulttype、funcresulttype は pg_type システムカタログ中の値で、OpExpr や FuncExpr の返却する値の型を指示する。

関数には引数の一つでも NULL なら OpExpr/FuncExpr 全体が NULL になる restrict 指定がある。この指定の有無は OpExr/FuncExpr には含まれない。 restrict の有無が決まるのは OpExpr/FuncExpr が ExecutorStart フェーズで FuncExprState に変換され、ExecutorRun フェーズで最初に評価される時に pg_proc システムカタログの値をシステムキャッシュから取り出した時に決定する。

3.5.4 BoolExpr

BoolExpr ノードは、AND や OR や NOT によって生成される。

3.5.5 CaseExpr、CaseWhen、CaseTestExpr

CaseExpr ノードや CaseWhen ノードは CASE 式を使った場合に生成される。

まず CaseExpr ノードが存在し、args の先に WHEN 句を意味する CaseWhen ノードが並ぶことになる。 CaseWhen ノードの expr は評価すべき条件式を意味するエクスプレッション・ツリーが繋がっており、条件式が成立する時は result の先のエクスプレッション・ツリーが評価されて結果となる。 CaseExpr ノードは args の先にある CaseWhen ノードを全て評価しても成立するものを発見できなかった場合は、defresult の先にあるエクスプレッション・ツリーを評価して返す。 defresult が ELSE 節に相当する。

CASE 式を使った場合の例をあげる。

3.5.6 Param、SubPlan

プラン・ツリーは下位ノードから上位ノードへデータを受け渡すことで処理するのが原則だが、ツリーの親子関係のないノード間でデータを渡したい場合がある。これを行うためにクエリー全体で共通にアクセスできるパラメータ領域があり、Param ノードはこれからデータを取得するためのデータ構造である。一般のプログラム言語で言えば、Var ノードはローカル変数の参照で、Param ノードはグローバル変数の参照に相当する。

Param ノードのアクセス可能なパラメータは ParamKind として PARAM_EXTERN と PARAM_EXEC の 2 種類が存在する。 PARAM_EXTERN は CREATE FUNCTION で定義されたユーザー定義関数の引数を受け取るために利用するパラメータである。これはエグゼキュータ内で値が変わらないので、単なる参照ポイントである。もう一つは PARAM_EXEC でクエリー内で実行時に値を生成するパラメータである。クエリーの実行を考える上ではこちらの方が重要である。

PARAM_EXEC のパラメータの利用方法は以下の 3 種類がある。

NestLoop のおいて外周(outer plan node)のデータを内周(inner plan node)側に渡すために利用する。4.5.2 節を参照のこと。
非相関サブクエリーの実行においてサブクエリーの実行結果を受け取るために利用する。
相関サブクエリーの実行においてサブクエリーへ渡す入力データを設定するために利用する。サブクエリー側ではこのパラメータを参照する。

ParamKind は PARAM_SUBLINK が存在するが、プラン・ツリーが完成した時点では PARAM_EXEC に書き改められ消滅している。

typedef struct Param
{
    Expr        xpr;
    ParamKind   paramkind;      /* kind of parameter. See above */
    int         paramid;        /* numeric ID for parameter */
    Oid         paramtype;      /* pg_type OID of parameter's datatype */
    int32       paramtypmod;    /* typmod value, if known */
    Oid         paramcollid;    /* OID of collation, or InvalidOid if none */
    int         location;       /* token location, or -1 if unknown */
} Param;

パラメータは PARAM_EXEC と PARAM_EXTERN で別々に番号付けされている。 Param ノードの paramid が番号になる。ただし PARAM_EXEC は 0-origin で、PARAM_EXTERN は 1-origin になっている。

SubPlan ノードはサブプランの実行させるためのノードである。 SubPlan という名前がついているが、プラン・ノードではなくエクスプレッション・ノードである。

Param と SubPlan は組み合わせてサブクエリー実行の制御を行う。

非相関サブクエリーの実行

非相関サブクエリーを含む SQL ステートを実行すると Param ノードがエクスプレッション・ツリー内に生成される。 Param ノードは初回の評価時に対応するサブクエリーを実行する契機になる。いったんサブクエリーを評価した後は、その結果を保存し以降はキャッシュしたデータを返却することになる。

非相関サブクエリーの例をあげる。

サンプルを説明する。

非相関サブクエリーの結果を格納するスロット数を PlannedStmt ノードに nParamExec に設定する。この例では 1 となる。
実行すべきサブプランは PlannedStmt ノードの subplans の中に並んでいる。
非相関サブクエリーを実行する SeqScan(2) は initPlan が必要となり、この中に SubPlan ノードが入っている。 SubPlan(16) ノードの plan_id は呼び出すサブクエリーの番号で、PlannedStmt ノードの subplans の並びに一致している。ただし span_id から 1 を引く必要がある。サブクエリーの実行結果の保存先のスロットは setParam で指定する。サンプルでは IntList(17) ノードの中に 0 を指定している。
ExecutorStart フェーズで SeqScan(2) は initPlan の先にある SubPlan(16) を評価し、サブクエリー実行の準備を行う。

ExecutorRun フェーズで Param(14) ノードが評価されると、サブクエリーの実行結果の保存スロットの paramid 番目を参照する。このスロットは ExecutorStart フェーズで SubPlan(16) が評価された時に、最初の評価時にサブクエリーが実行されるように設定されている。

static Datum
ExecEvalParamExec(ExprState *exprstate, ExprContext *econtext,
                  bool *isNull, ExprDoneCond *isDone)
{
    Param      *expression = (Param *) exprstate->expr;
    int         thisParamId = expression->paramid;
    ParamExecData *prm;

    prm = &econtext->ecxt_param_exec_vals[thisParamId]);
    if (prm->execPlan != NULL) /* 初回はここが NULL になっている。 */
    {
        ExecSetParamPlan(prm->execPlan, econtext); /* サブクエリー実行 */
    }
    *isNull = prm->isnull;
    return prm->value;
}

相関サブクエリーの実行

相関サブクエリーを含む SQL ステートを実行すると SubPlan ノードがエクスプレッション・ツリー内に生成される。 SubPlan ノードは評価される度に、サブプランを実行する。この際にメインクエリーからサブクエリーに対して Param ノードの仕組みを使ってデータの受け渡しを行う。

相関サブクエリーの例をあげる。

サンプルを説明する。

メインクエリーから相関サブクエリーへ渡すデータを格納するスロット数を PlannedStmt ノードに nParamExec に設定する。この例では 1 となる。
実行すべきサブプランは PlannedStmt ノードの subplans の中に並んでいる。
相関サブクエリーを実行する SeqScan(2) の qual につながったエクスプレッション・ツリーの中に SubPlan(14) が存在し、SubPlan(14) が評価された時にサブクエリーが実行される。initPlan は不要。 SubPlan(14) ノードの plan_id は呼び出すサブクエリーの番号で、PlannedStmt ノードの subplans の並びの一致している。ただし span_id から 1 を引く必要がある。
SubPlan(14) は parParam と args が設定されており、サブクエリーに渡すデータを指定する。parParm はデータを格納するスロットの番号を、args は格納するデータを生成するエクスプレッション・ツリーがつながる。複数のデータを格納できるように、parParm と args は配列になっている。
呼び出し先のサブクエリーは、Param(42) を介して SubPlan(14) にわたる。

3.5.7 Aggref

Aggref ノードは Agg プラン・ノードと WindowAgg プラン・ノードのターゲットリストにのみ出現する。これは Agg プラン・ノードの説明の中で解説する。

3.6 Target List

ターゲット・リスト(Target List) は TargetEntry ノードのリストである。ターゲット・リストはプランが出力するタプルをカラム数と各カラム名とデータ型をあらわしている。 TargetEntry ノードの resno は出力タプルのカラム番号 +1 を記録している。リストの並びと resno の並びは常に一致している。

TargetEntry の実際の構造は以下のようにになる。

typedef struct TargetEntry
{
    Expr        xpr;
    Expr       *expr;           /* expression to evaluate */
    AttrNumber  resno;          /* attribute number (see notes above) */
    char       *resname;        /* name of the column (could be NULL) */
    Index       ressortgroupref;/* nonzero if referenced by a sort/group
                                 * clause */
    Oid         resorigtbl;     /* OID of column's source table */
    AttrNumber  resorigcol;     /* column's number in source table */
    bool        resjunk;        /* set to true to eliminate the attribute from
                                 * final target list */
} TargetEntry;

TargetEntry はエクスプレッション・ノードの一種として存在するので Expr 型 xpr が基底クラスとなっている。ただし TargetEntry はプレイスフォルダーなので評価関数は持たない。
expr にはこの TargetEntry を評価した時の「値」となるエクスプレッション・ツリーが入っている。
resno はターゲットリストの中でのこの TargetEntry が何番目のカラムかを示している。1番からはじまる。
resname はカラム名を示している。SELECT コマンドがタプルを表示する時のカラム名はこの値となる。resname は resjunk が false の場合にのみ有効。
ressortgroupref はこのカラムが ORDER BY、GROUP BY、DISTINCT によってソートやグループ化の対象となるかどうかの情報を持つ。ressortgroupref が 1 以上の場合は、ORDER BY、GROUP BY、DISTINCT の対象となることを示す。0 なら対象ではない。ORDER BY A, B の一つの操作が 2 つのカラムを対象とする場合、対応する TargetEntry の ressortgroupref は同じ値になる。
resorigtbl は、このカラムの元となったテーブルが存在する場合に、そのテーブルの Oid を示す。0 ならテーブルとは関係のないカラムである。
resorigcol は、このカラムの元となったテーブルが存在する場合にテーブルのカラム番号を示す。
resjunk は、このカラムが「隠し」カラムであり最終的な表示からは除外することを示す。

resjunk が true となる隠しカラムには以下のようなパターンがある。

UPDATE、DELETE、SELECT FOR UPDATE コマンドなどを使った場合。操作の対象となるテーブルの ctid を隠しカラムとして読み、それを上位にある ModifyTable ノードや LockRows ノードに渡す。4.8.1 節、4.8.2 節にあるサンプルを参照のこと。
RETURING 句で ModifyTable の対象でないテーブルを参照する場合。
ORDER BY で指定されたカラムが選択リストに登場しない場合。例えば SELECT C1, C2 FROM T1 ORDER BY C1, C3; のプランは SELECT C1, C2, C3 FROM T1 ORDER BY C1, C3; とほぼ等しく resjunk が true に指定された C3 が隠されている。
Foreign Data Wrapper の AddForeignUpdateTargets コールバックで rowid を追加する場合。
UNION ALL 以外の問い合わせ結合をした場合。SetOp ノードがクエリー番号を隠しカラムとして挿入する。4.6.2 節を参照のこと。

ターゲット・リストは原則として 1 個以上の TargetEntry ノードを持つが例外がある。 EXISTS を使うと TargetEntry ノードが 0 個のターゲット・リストができる。

例えば SELECT * FROM T1 WHERE EXISTS (SELECT 1 FROM T2 WHERE T1.COL = T2.COL); の場合、サブクエリーがサブプランとなるが、このサブプランの topmost plan node のターゲット・リストは常に TargetEntry ノードが 0 個となる。そのため例の中のサブクエリーの 1 は実際には評価されない。 1 を、* と書いても、具体的なカラムを並べても全て無視される。

4. 各プラン・ノードのはたらき

4.1 Scan

Scan はスキャン系ノードのための抽象クラスである。 Scan には Plan に scanrelid が追加されている。

typedef struct Scan
{
    Plan      plan;
    Index     scanrelid; /* relid is index into the range table */
} Scan;

クエリー内で使われるテーブルは、実行時に管理し易いように 1 番から連番が振られている。これが relid。アクセスするテーブルの詳細情報は、PlannedStmt ノードの rtable から繋がっている range table で管理されており、relid はそのインデックス番号になる(ただし実際にアクセスする際に relid から 1 を引く)。 relid は Var ノードの varno にも利用される。

4.1.1 SeqScan

SeqScan はテーブルのスキャンを行う。 Plan ノードの qual が条件式となり、これに合致するタプルが targetlist で指定されたターゲットリストに従い評価されて出力タプルとして生成される。テーブルをスキャンする順序はない。

4.1.2 IndexScan

IndexScan はインデックスを使ったスキャンを行うプラン・ノードである。テーブルスキャン時に WHERE 句による絞込み(selectivity)が見込める場合には IndexScan に、インデックスがなかったり、あっても絞込みが十分でないと判断された場合には SeqScan が選択される。

IndexScan は SeqScan と違って追加のフィールドを持っている。 IndexScan がアクセスする元テーブルは Scan の relid で決まるが、アクセスするインデックス(リレーション)は indexid で指定される。

typedef struct IndexScan
{
    Scan    scan;
    Oid     indexid;            /* OID of index to scan */
    List   *indexqual;          /* list of index quals (usually OpExprs) */
    List   *indexqualorig;      /* the same in original form */
    List   *indexorderby;       /* list of index ORDER BY exprs */
    List   *indexorderbyorig;   /* the same in original form */
    ScanDirection indexorderdir; /* forward or backward or don't care */
} IndexScan;

IndexScan の条件式は Plan の qual を使わずに、indexqual 、indexqualorig が使われる。 indexqual はインデックス情報を検索する条件式になる。 indexqual からつながるエクスプレッション・ツリーに出現する Var は varno は INDEX_VAR が設定され、インデックスからデータを読み取ることを指示している。 varattno はインデックス内のデータの並び順を指定している。これは CREATE INDEX コマンドで指定した並びと一致する。

CREATE INDEX indexname ON tablename (ColA, ColB, ColC, ColD)

IndexScan はソートにおいても使用されることがある。 ORDER BY 句とインデックスの整順条件が一致した場合、インデックスになる並び替えた情報を使えるからである。この用途に IndexScan が使われる場合は、indexorderdir に ForwardScanDirection(1) または BackwardScanDirection(-1) が指定される。逆にインデックスをただの絞込みのみに利用する場合には、indexorderdir には NoMovementScanDirection(0) が指定されている。

4.1.3 BitmapHeapScan

BitmapHeapScan プランもインデックススキャンの一種だが、IndexScan よりもさらに絞り込める場合に利用される。

BitmapHeapScan は BitmapIndexScan と一緒に使用され、場合によって BitmapOr と BitmapAnd も使われる。 BitmapIndexScan がまず indexid が指定するインデックス(リレーション)を indexqual の条件に沿って検索し、ヒットしたタプルの Tuple-Id(TID、ctid) のビットマップを作成する。これが BitmapHeapScan の入力になり、BitmapHeapScan はビットマップで 1 が立っている箇所のタプルを読み込み自身の qual の条件で最後の絞込みを行う。 BitmapHeapIndexScan を複数使い、複数のビットマップを OR(BitmapOr)、AND(BitmapAnd) して条件を合成することもできる。

一群の BitmapHeapScan と BitmapIndexScan の bitmapqualorig には「オリジナル」の条件、つまり SeqScan が選択された場合 qual に入っていたであろう条件が設定される。これは BitmapHeapScan と全 BitmapIndexScan で同じエクスプレッション・ツリーが入っている。

BitmapIndexScan が選択する条件は indexqual である。このエクスプレッション・ツリー内の Var の varno は IndexScan と同様 INDEX_VAR になる。

BitmapHeapScan の qual のエクスプレッション・ツリーの Var の varno は scanrelid、上の図の場合は 1 を指している。これは BitmapHeapScan がインデックスではなくテーブルからタプルを読み込んで、そのデータを判定しているからである。

BitmapHeapScan の例をあげる。

4.2 Sort

Sort は ORDER BY によるソートによって生成される。

numCols がソートのキー数を意味し、後のフィールドは numCols 個の要素を持つ配列になる。 sortColIdx は outer node のどの列をソートするかを、sortOperatos はソートに使うオペレータの OID を、collations は文字列をソートする時の collation 指定を、nullsFirst は NULL を最小の値として扱うかどうかを指定する(デフォルトでは最大の値として扱われる)。

typedef struct Sort
{
    Plan        plan;
    int         numCols;        /* number of sort-key columns */
    AttrNumber *sortColIdx;     /* their indexes in the target list */
    Oid        *sortOperators;  /* OIDs of operators to sort them by */
    Oid        *collations;     /* OIDs of collations */
    bool       *nullsFirst;     /* NULLS FIRST/LAST directions */
} Sort;

Sort には条件を絞り込む機能はないので、qual は持たない。 targetlist は存在するが、入力と同形式のフォーマットで出力する。プランを書き換える場合は、outer node のターゲット・リストと Sort のターゲット・リストのカラム数・各カラムの型が一致するようにしなくてはならない。

Sort はまたソートアグリゲーション(sort aggregation、PostgreSQL の EXPALIN 中の表記では GroupAggregate)やマージジョイン(Merge Join)が選択された時に、Agg プランや MergeJoin プランへ渡すデータをソートするのにも利用される。

Sort の例をあげる。

この例では SELECT C2 FROM testtable1 ORDER BY C1; というクエリーを実行したパターンである。テーブルに C1 と C2 というカラムがあり、C1 を使ってソートするが表示するのは C2 のみである。しかし一見このプランツリーは SELECT C2, C1 FROM testtable1 ORDER BY C1; のクエリーのものと同形である。

違いは C2 のカラムは TargetEntry の resjunk が true になっている点である。 3.6 節で述べたように resjunk が true だとクエリーの出力からは隠される。

EXPLAIN (VERBOSE ON, COSTS OFF) SELECT … を使っても確認した場合、Sort の出力には本来表示されない c1 が表示される。

Sort
  Output: c2, c1
  Sort Key: testtable1.c1
  ->  Seq Scan on public.testtable1
        Output: c2, c1

4.3 Agg

Agg は集約を行うためのプラン・ノードである。 Agg の構造体は以下のようにシンプルだが、Agg と一緒に使われる Aggref エクスプレッション・ノードと組み合わせて他のプランよりも複雑な処理をする。

まず aggstrategy は AGG_PLAIN(GROUP BY のないただの集約)、AGG_HASHED(ハッシュ・アグリゲーション)、AGG_SORTED(ソート・アグリゲーション、EXPLAIN 中の表記では GroupAggregation)を選択する。 AGG_PLAIN と AGG_HASHED は単体で動作するが、AGG_SORTED の場合は入力データが GROUP BY 指定と同じ条件でソートされている必要がある。ソートは Agg の outer plan に Sort や IndexScan を配置して実現する。

typedef struct Agg
{
    Plan        plan;
    AggStrategy aggstrategy;    /* AGG_PLAIN, AGG_SORTED, AGG_HASHED */
    int         numCols;        /* number of grouping columns */
    AttrNumber *grpColIdx;      /* their indexes in the target list */
    Oid        *grpOperators;   /* equality operators to compare with */
    long        numGroups;      /* estimated number of groups in input */
} Agg;

GROUP BY 句は numCols、grpColIdx、grpOperators で指定される。

qual は HAVING 句の制限のために使用される。 WHERE 句の制限は Agg ではなく、Agg の入力になる outer node によって処理される。

Agg の最も特徴的なのは targetlist に出現する Aggref エクスプレッション・ノードである。 Aggref は集約の処理方法を記載したノードであると共に、集約結果を参照する Var や Param のようなノードでもある。 Agg のターゲット・リストは TargetEntry の下に Aggref が出現すると、Aggref の args の下にさらに二段目のターゲット・リストが出現する。二段目のターゲット・リストを持たない Aggref もある(count(*) などターゲットを必要としない場合)。

Agg's target list — fig-8: Agg's Target List

この二段のターゲットリストは、PostgreSQL が ordered-set aggregation などの複雑な集約に対応するための設計だと思われる。 Agg プランは ExecutorStart フェーズにおいて、Aggref の下にある二段目のターゲットリストは切り外される。その上で Agg プランの内で各 Aggref がそれぞれ別個のミニ実行エンジンがあるように処理される。

Agg は qual や targetlist に出現する OUTER_VAR 指定の Var は、GROUP BY 句で指定した列(varattno)を指定することはできない。これは SQL で以下のような構文エラーを犯しているのに等しい。

SELECT city, name, sum(ID), avg(salary), count(*) FROM employee GROUP BY city;

Agg の例をあげる。

この例ではテーブル employee の中の ID、salary、city しか参照していない。プランノード中の SeqScan(36) は name、start_date、region も読み込んでいる。これはSort と異なり Agg ノードは入力されたタプルを変形して出力する機能を持っている。このため SeqScan ノード側でカラムを絞るとの、Agg ノード側で絞るのの 2 つの選択肢がある。しかし SeqScan ノードからはテーブルと同形式で読み込み無加工で Agg ノードに送った方がコストが低くなるのでこのような形になる。テーブルにインデックスが張ってある場合などは別のプランになる可能性がある。

4.4 WindowAgg

To be described...

4.5 Join

Join はジョイン系ノードのための抽象クラスである。 2 つのテーブルの結合する機能を提供する。

typedef struct Join
{
    Plan            plan;
    JoinType        jointype;
    List            joinqual;
} Join;

Join ノードは plan.lefttree つまり outer plan が左テーブル、plan.righttree つまり inner plan が右テーブルとなる。これは SQL クエリー中の並びとは必ずしも一致せず、Join ノードでは反対に配置されている可能性がある。

jointype は結合のタイプを示す列挙子である。プランツリーの段階では以下の 6 種類のいずれかが設定されている。

マクロ名	説明
JOIN_INNER	INNER JOIN であることを示す。
JOIN_LEFT	`lefttree` LEFT OUTER JOIN `righttree` 相当の OUTER JOIN であることを示す。`lefttree` 側のタプルはマッチするものがなくても必ず表示される。
JOIN_RIGHT	`lefttree` RIGHT OUTER JOIN `righttree` 相当の OUTER JOIN であることを示す。`lefttree` 側のタプルはマッチするものがなくても必ず表示される。
JOIN_FULL	FULL OUTER JOIN であることを示す。
JOIN_SEMI	Semi-join。SQL JOIN のシンタックスではなく EXISTS 句を使った時に出現する。左テーブルの行が右テーブルの行のいずれかに合致した時に出力される。逆に言えば右テーブルの中に合致する最初の行を見つければ、それ以上右テーブルをスキャンしない。
JOIN_ANTI	Anti-join。JOIN_SEMI の逆で NOT EXISTS 句を使った時に出現する。左テーブルの行が右テーブルの行のいずれにも合致しない時に出力される。逆に言えば右テーブルの中に合致する最初の行を見つければ、それ以上右テーブルをスキャンしない。

joinqual は左右のテーブルの結合条件である。 Join が Plan を含んでいるため plan.qual も条件式として使えるが、以下のような違いがある。

joinqual を評価する。条件に成立しない場合はパスする。
Sem-join(JOIN_SEMI) の場合、右テーブルの次の行はもう読まない。 Anti-join(JOIN_SEMI)の場合、 plan.qual を評価せずにパスする。
plan.qualを評価する。条件に成立しない場合はパスする。

4.5.1 ジョインの種類と選択

PostgreSQL は Join ノードの具象クラスとして NestLoop、HashJoin、MergeJoin の 3 種類を持っている。 SQL クエリーの内容に応じて以下のように選択される。

equi-join (結合条件が A = B のような等号の JOIN) は NestLoop しか使えない。
CROSS JOIN は NestLoop になる。
NestLoop は JOIN_OUTER に対応しない。そのため FULL OUTER JOIN は MergeJoin か HashJoin になる。
非 equi-join の FULL OUTER JOIN をサポートしない。

複数の候補がありえる場合にはコストによって最適なものが選択される。

4.5.2 NestLoop

NestLoop はいわゆる Nested Loop を行うためのプランノードである。

Nested Loop は一番簡単な INNER JOIN(JOIN_INNER) の場合は以下のようなロジックで動作する。単純な二重ループとなる。

foreach outer tuple IN outer plan
    foreach inner tuple IN inner plan
        if (inner tuple と outer tuple が結合条件に合致)
            inner tuple と outer tuple から出力タプルを合成して出力

NestLoop ノードの NestLoop 構造体は以下の形式になっている。

typedef struct NestLoop
{
    Join        join;
    List       *nestParams;     /* list of NestLoopParam nodes */
} NestLoop;

NestLoop 構造体の nestParams の説明は後に回す。インデックスのない 2 つのテーブルを nested loop したパターンでは nestParams は NIL となる。左右のテーブルを読み込んだ結果を joinqual の結合条件でマッチングする。

SELECT T1.C1, T1.C2 FROM T1 JOIN T2 ON (T1.C1 = T2.C1);

Nested Loop
  Output: t1.c1, t1.c2
  Join Filter: (t1.c1 = t2.c1)
  ->  Seq Scan on public.t1
        Output: t1.c1, t1.c2
  ->  Materialize
        Output: t2.c1
        ->  Seq Scan on public.t2
              Output: t2.c1

Parameterized Nested Loop

テーブルのどちらか一方にインデックスを張った場合には NestLoop は、より高速な動作を行う。インデックスを張っているテーブルを内周(inner plan node)に配置した上で、外周(outer plan node)からタプルを1つ読み込むと、内周側にデータを転送し、内周側ではそのデータを使って IndexScan をかける。 NestLoop の二重ループが実質一重ループとなる。

しかし外周(outer plan node) → NestLoop、内周(inner plan node) → NestLoop というタプルの流れはあっても、外周(outer plan node)→内周(inner plan node)や NestLoop → 内周(inner plan node)は通常のタプルの流れではありえない。 3.5.6 節で述べたようにデータを記録するために PARAM_EXEC 型のパラメータを用いる。 NestLoop は外周(outer plan node)からタプルを取り出す度に outer tupleの一部を Param に記録し、内周(inner plan node)側で Param を参照する。 Parameterized された nested loop である。 NestLoop 構造体の nestParams はこのために利用され、outer tuple のどの位置をどのパラメータに記録するかを NestLoopParam ノードのリストで保持している。

NestLoopParam 構造体は以下の構造を持つ。

typedef struct NestLoopParam
{
    NodeTag     type;
    int         paramno;        /* number of the PARAM_EXEC Param to set */
    Var        *paramval;       /* outer-relation Var to assign to Param */
} NestLoopParam;

paramval は outer tuple のうちどのカラムをパラメータに記録するかを指示する。
paramno はどのパラメータに記録するかを指示する。

Parameterized NestLoop は EXPLAIN に対して以下のような表示を返す。またプランツリーを可視化した例を上げる。

Nested Loop
  Output: t1.c1, t1.c2
  ->  Seq Scan on public.t2
        Output: t2.c1, t2.c2
  ->  Index Scan using t1_c1_idx on public.t1
        Output: t1.c1, t1.c2
        Index Cond: (t1.c1 = t2.c1)

4.5.3 HashJoin

HashJoin はいわゆる Hash Join を行うためのプランノードである。実行の最初に inner plan node 側のタプルを全て読み込みハッシュテーブルに格納する。その後で outer plan node 側からタプルを 1 つづつ読み込み、ハッシュテーブルから該当するハッシュを読み出して

typedef struct HashJoin
{
    Join        join;
    List       *hashclauses;
} HashJoin;

hashclauses はジョインの結合条件を記述する。ハッシュテーブルの検索条件にもなる。 HashJoin においても join.joinqual や join.plan.qual も結合条件として働くが、hashclauses だけで条件を絞り込めるのであれば join.joinqual や join.plan.qual はなくてもよい。

HashJoin は outer plan node 側に必ず Hash を配置する。 Hash はプランノードのだが、HashJoin と連動して動作する専用ノードである。ハッシュテーブルの作成は Hash が担当する。

typedef struct Hash
{
    Plan        plan;
    Oid         skewTable;      /* outer join key's table OID, or InvalidOid */
    AttrNumber  skewColumn;     /* outer join key's column #, or zero */
    bool        skewInherit;    /* is outer join rel an inheritance tree? */
    Oid         skewColType;    /* datatype of the outer key column */
    int32       skewColTypmod;  /* typmod of the outer key column */
} Hash;

skewXXX はこの HashJoin を特徴付けている outer plan node 側のテーブルの情報を設定する。 Hash は内部でこのテーブルの統計情報を参照し最頻出値(Most Common Value; MVC)を取得する。そして通常のハッシュテーブルの前に、この MVC のエントリを設けることで、ハッシュテーブル検索を高速化する。

4.5.4 MergeJoin

MergeJoin はいわゆる Merge Join を行うためのプランノードである。

typedef struct MergeJoin
{
    Join        join;
    List       *mergeclauses;       /* mergeclauses as expression trees */
    Oid        *mergeFamilies;      /* per-clause OIDs of btree opfamilies */
    Oid        *mergeCollations;    /* per-clause OIDs of collations */
    int        *mergeStrategies;    /* per-clause ordering (ASC or DESC) */
    bool       *mergeNullsFirst;    /* per-clause nulls ordering */
} MergeJoin;

To be described.

4.6 サブクエリーの結合に関係するプラン・ノード

複数のサブクエリーの内容を様々に結合するプラン・ノードが存在する。

4.6.1 Append

Append は任意の個数の下位ノードを持ち、下位ノードの内容をマージして上位ノードに返す。通常のプラン・ノードと異なり inner/outer 以外の下位ノードを持っている。最初の下位ノードをスキャンして結果を返し、スキャンが完了すると次の下位ノードに処理が移る。

Append は UNION や UNION ALL で利用される。

SELECT c1 FROM t1 UNION ALL SELECT c1 FROM t2;

Append
 ->  Seq Scan on t1;
 ->  Seq Scan on t2;

また Append はテーブル継承がある時に、親テーブルの内容を読む時に利用される。

CREATE TABLE t1 (c1 int);
CREATE TABLE t2 () INHERITS (t1);
SELECT c1 FROM t1;

Append
 ->  Seq Scan on t1;
 ->  Seq Scan on t2;

4.6.2 SetOp

SetOp は2 つの問い合わせ結合(set operation)のためにあるプラン・ノードである。ただし UNION (ALL) 句は Append が担当しており、残りの INTERSECT と EXCEPT を担当する。

INTERSECT は query1 INTERSECT [ALL] query2 という構文で query1 と query2 の両方に含まれている行を返す。一方、EXCEPT は query1 EXCEPT [ALL] query2 という構文で query1 に含まれる行のうち query2 に含まれている行を返す。この処理を簡略化するために query1 と query2 の選択リストの最後にクエリー番号を追加している。この余分なカラムはクエリーの外側には公開しない(TargetEntry ノードの resjunk が true)。 INTERSECT はクエリー番号の両方が揃った行を出力し、EXCEPT はクエリー番号 0 が存在するが、クエリー番号 1 が出現しない行を出力する。

SetOp は Agg と同様に hash set-operation と sorted set-operation の 2 種類がある。入力数が予測できメモリに載るようであれば hash set-operation を、そうでなければ入力をソートした後に sorted set-operation が採用される。

SELECT c1 FROM t1 INTERSECT SELECT c1 FROM t2;

HashSetOp Intersect
  Output: "*SELECT* 1".c1, (0)
  ->  Append
        ->  Subquery Scan on "*SELECT* 1"
              Output: "*SELECT* 1".c1, 0
              ->  Seq Scan on public.t1
                    Output: t1.c1
        ->  Subquery Scan on "*SELECT* 2"
              Output: "*SELECT* 2".c1, 1
              ->  Seq Scan on public.t2
                    Output: t2.c1

4.6.3 MergeAppend

MergeAppend は Append 同様に任意の個数の下位ノードを持ち、下位ノードの内容をマージして上位ノードに返す。ただし Append が複数の下位ノードを順番にスキャンするだけだったのに対して、MergeAppend は各下位ノードがソート済みのデータを返すことを前提とした上で、それらをソートマージして順序を維持したまま上位ノードに返す。複数下位ノードの結果を受け取る Sort とも言える。

MergeAppend が出現するのは継承テーブルに関する親子のテーブルの両方にインデックスがあり、親テーブルに対するソートが両テーブルの IndexOnlyScan になる場合にその結果のマージを行うために出現する。

CREATE TABLE testtable1 (C1 int, C2 int);
CREATE TABLE testtable2 () INHERITS (testtable1);

CREATE INDEX testindex1 ON testtable1 (C1);
CREATE INDEX testindex2 ON testtable2 (C1);

SELECT C1 FROM testtable1 ORDER BY C1

Merge Append
  Sort Key: testtable1.c1
  ->  Index Only Scan using testindex1 on public.testtable1
        Output: testtable1.c1
  ->  Index Only Scan using testindex2 on public.testtable2
        Output: testtable2.c1

4.6.4 RecursiveUnion

RecursiveUnion は WITH RECURSIVE 句で出現する。

WITH RECURSIVE
    t(n) AS
        (VALUES(1)
         UNION ALL
         SELECT n + 1 FROM t WHERE n > 100)
SELECT
    sum(n) FROM t;

Aggregate
  Output: sum(t.n)
  CTE t
    ->  Recursive Union
          ->  Values Scan on "*VALUES*"
                Output: "*VALUES*".column1
          ->  WorkTable Scan on t t_1
                Output: (t_1.n + 1)
                Filter: (t_1.n > 100)
  ->  CTE Scan on t
        Output: t.n

4.7 補助的なプラン・ノード

補助的な機能を切り出したプラン・ノードが存在する。

4.7.1 Limit

Limit は LIMIT 句や OFFSET 句を実現するプラン・ノードである。下位ノードから受け取った行を LIMIT 句の数だけ上位ノードに渡した時点で下位ノードのスキャンを停止する。

この時、Limit が最初の行を取得する前に LIMIT 句の評価を行い、自分が読み取る行数 N を下位の Sort へ伝達する。 Sort は Limit からの N 行というデータを受け取り、Top-N ソートを実施することでソート処理を高速化する。

Limit の例をあげる。

4.7.2 Result

Result はクエリー実行中にテーブルのスキャンデータに依存しない一種の定数値を効率的に扱うためのプラン・ノードである。

例えばテーブルスキャンなしで計算式を SELECT に書いた場合に出現する。

SELECT 1 * 2;

 Result
   Output: 2

あるいは WHERE 句がクエリー実行時に一回評価すれば決まってしまう場合、Result がフィルターとして出現する。

SELECT sum(c1) FROM t1 WHERE current_date = date'2015-12-13';

Aggregate
  Output: sum(c1)
  ->  Result
        Output: c1, c2
        One-Time Filter: (('now'::cstring)::date = '2015-12-13'::date)
        ->  Seq Scan on public.t1
              Output: c1, c2

一般的なスキャンを含んだプランが Result を使ったプランに最適化されることもある。

SELECT min(c1), max(c1) FROM t1;

Result
  Output: $0, $1
  InitPlan 1
    ->>  Limit
          Output: t1.c1
          ->>  Index Only Scan using i on public.t1
                Output: t1.c1
                Index Cond: (t1.c1 IS NOT NULL)
  InitPlan 2 (returns $1)
    ->  Limit
          Output: t1_1.c1
          ->  Index Only Scan Backward using i on public.t1 t1_1
                Output: t1_1.c1
                Index Cond: (t1_1.c1 IS NOT NULL)

4.7.3 Unique

Unique は下位ノードから渡されるデータ(行)がソート済みであることを前提として、連続して同一内容の行が続く場合、それをまとめて1行だけ出力する。

Unique は DISTINCT 指定など重複行を除去する処理で利用される。

SELECT DISTINCT c1 FROM t1;

Unique
  ->  Sort
        Sort Key: c1
        ->  Seq Scan on t1

4.7.4 Group

Group は下位ノードから渡されるデータ(行)がソート済みであることを前提として、指定した列が同一内容の行が続く場合、それをまとめて1行にして出力する。 Unique が行全体が一致しているかを比較するのに対して、Group は一部の列しか比較しない。

Group は集約関数のない GROUP BY の処理に使われる。ただし Agg が Group の機能を包括しているので、単に集約関数のない GROUP BY を書いても hash aggergation の Agg が出ることが多い。

SET enable_hashagg = off;
SELECT c1 FROM t1 GROUP BY c1;

Group
  Group Key: c2
  ->  Sort
        Sort Key: c2
        ->  Seq Scan on t1

4.7.5 Material

Material は下位ノードから渡された入力データをいったんファイルへ記録してから上位ノードへ返す。

結合(join)処理は内周ノードに繰り返し読み直しがかかったり、内周ノードの現在のスキャン行位置にマークして後でマーク位置まで戻したりする処理が存在する。スキャン系プランノードや Sort (内容をファイルに書き出すことができる)などと違い、一般のプラン・ノードはいったん結果行を返すと、その内容は破棄されるので読み直しができない。そのような揮発性のプラン・ノードの上位に Material を挟むことで不揮発化を行うことができる。

Material は内容をファイルに書き出すので、このプラン・ノードが登場すると性能が劣化するようだ。

4.8 更新に関係するプラン・ノード

To be described...

4.8.1 ModifyTable

ModifyTable は INSERT、DELETE、UPDATE 処理を実行するプラン・ノード。

DELETE と UPDATE を実行した時の ModifyTable の例をあげる。

DELTE
UPDATE

4.8.2 LockRows

LockRows は SELECT FOR UPDATE、SELECT FOR SHARE などの行をロックする処理を実施するためのプラン・ノード。

SELECT FOR UPDATE を実行した時の LockRows の例をあげる。

コメントを書き込む