The parser stage consists of two parts:
パーサは二段階で構成されています。
The parser defined in gram.y and scan.l is built using the UNIX tools yacc and lex.
gram.y と scan.l ファイルで定義されたパーサは UNIX の yacc と lex ツールを使って構築されます。
The transformation process does modifications and augmentations to the data structures returned by the parser.
変換プロセスはパーサから戻されたデータ構成に 変更と引数づけを行います。
The parser has to check the query string (which arrives as plain ASCII text) for valid syntax. If the syntax is correct a parse tree is built up and handed back otherwise an error is returned. For the implementation the well known UNIX tools lex and yacc are used.
パーサは(シンプルな ASCII テキストで届けられた)問合せ文字列が 正しい構文であるかどうかを調べます。構文が正しければパースツリーが 生成されて戻されますが、正しくない場合エラーが返されます。 実装するには UNIX では良く知られているツール、 lex と yacc が使用されます。
The lexer is defined in the file scan.l and is responsible for recognizing identifiers, the SQL keywords etc. For every keyword or identifier that is found, a token is generated and handed to the parser.
lexer は scan.l ファイルで 定義され、識別子、 SQL キーワードその他を認識する役割を持っています。 見つかった全てのキーワード又は識別子に対し token が発行されパーザに渡されます。
The parser is defined in the file gram.y and consists of a set of grammar rules and actions that are executed whenever a rule is fired. The code of the actions (which is actually C-code) is used to build up the parse tree.
パーサは gram.y ファイルで定義され、 文法 rule とその rule が放った アクション(action)の組みで構成されます。 アクションのコードは(実際にはCプログラムです)パースツリーを生成する のに使用されます。
The file scan.l is transformed to the C-source file scan.c using the program lex and gram.y is transformed to gram.c using yacc. After these transformations have taken place a normal C-compiler can be used to create the parser. Never make any changes to the generated C-files as they will be overwritten the next time lex or yacc is called.
scan.l ファイルは、プログラム lex により C のソースファイル scan.c に、gram.y ファイルは yacc により gram.c に変換されます。これらの変換後、 通常の C コンパイラでパーサが生成可能となります。生成された C の ファイルは、次回 lex 又は yacc が呼ばれたときに上書きされるため、 変更をしてはいけません。
Note: The mentioned transformations and compilations are normally done automatically using the makefiles shipped with the Postgres source distribution.
ここで記述した変換とコンパイルは通常 Postgres ソース配付物に同梱される makefiles で自動的に行われます。
A detailed description of yacc or the grammar rules given in gram.y would be beyond the scope of this paper. There are many books and documents dealing with lex and yacc. You should be familiar with yacc before you start to study the grammar given in gram.y otherwise you won't understand what happens there.
yacc 又は gram.y で規定されている文法 rule の詳細は本論文の範疇を越えるものです。 lex 及び yacc に関しては多数の書籍やドキュメントが存在します。gram.y で規定されている文法 rule を学ぶ前に yacc を熟知しておかないと、そこに何が書いてあるのか多分理解できないでしょう。
For a better understanding of the data structures used in Postgres for the processing of a query we use an example to illustrate the changes made to these data structures in every stage.
問合せ処理のために Postgres が使用する データ構造をより良く理解するため、それぞれのステージでデータ構造 に対して行われる変更について例示することにします。
Example 22-1. 単純な Select
This example contains the following simple query that will be used in various descriptions and figures throughout the following sections. The query assumes that the tables given in The Supplier Database <!-- XXX The above citetitle should really be an xref, but that part has not yet been converted from Stefan's original document. - thomas 1999-02-11 --> have already been defined.
select s.sname, se.pno
from supplier s, sells se
where s.sno > 2 and s.sno = se.sno;
この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 XXX 上記の citetitle は当然 xref タグ付きですが、Stefan の元のドキュメント ではこの部分は未だ変換されていません。 - thomas 1999-02-11
select s.sname, se.pno
from supplier s, sells se
where s.sno > 2 and s.sno = se.sno;
Figure \ref{parsetree} shows the parse tree built by the grammar rules and actions given in gram.y for the query given in 単純な SelectThis example contains the following simple query that will be used in various descriptions and figures throughout the following sections. The query assumes that the tables given in The Supplier Database <!-- XXX The above citetitle should really be an xref, but that part has not yet been converted from Stefan's original document. - thomas 1999-02-11 --> have already been defined. select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno;この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 XXX 上記の citetitle は当然 xref タグ付きですが、Stefan の元のドキュメント ではこの部分は未だ変換されていません。 - thomas 1999-02-11 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; (without the operator tree for the where clause which is shown in figure \ref{where_clause} because there was not enough space to show both data structures in one figure).
図 \ref{parsetree} は 単純な SelectThis example contains the following simple query that will be used in various descriptions and figures throughout the following sections. The query assumes that the tables given in The Supplier Database <!-- XXX The above citetitle should really be an xref, but that part has not yet been converted from Stefan's original document. - thomas 1999-02-11 --> have already been defined. select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno;この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 XXX 上記の citetitle は当然 xref タグ付きですが、Stefan の元のドキュメント ではこの部分は未だ変換されていません。 - thomas 1999-02-11 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; で与えられた問合せに対しての gram.y で与えられた 文法 rule とアクションによって生成されたパースツリーを示しています。 図 \ref{where_clause} で示した where 句による 演算子ツリーは、二つのデータ構造 を一つの図にまとめることが紙面の大きさの制約上出来ないため、 省略してあります。
The top node of the tree is a SelectStmt node. For every entry appearing in the from clause of the SQL query a RangeVar node is created holding the name of the alias and a pointer to a RelExpr node holding the name of the relation. All RangeVar nodes are collected in a list which is attached to the field fromClause of the SelectStmt node.
ツリーの最上ノードは SelectStmt ノードです。 SQL の問合せでの from 句の全ての項目 に対してエイリアス名を持った RangeVar ノードと、リレーション 名を持った RelExpr ノードへのポインタが生成されます。 全ての RangeVar ノードは SelectStmt ノードの fromClause に付けられるリスト にまとめられます。
For every entry appearing in the select list of the SQL query a ResTarget node is created holding a pointer to an Attr node. The Attr node holds the relation name of the entry and a pointer to a Value node holding the name of the attribute. All ResTarget nodes are collected to a list which is connected to the field targetList of the SelectStmt node.
SQL の問合せでの select list の全ての項目 に対して Attr ノードへのポインタを持った ResTarget ノードが生成されます。 Attr ノードはその項目の リレーション名と、属性 名を持った Value ノードへのポインタを所持します。 全ての ResTarget ノードは SelectStmt ノードの targetList フィールドに接続されるリストに納められます。
Figure \ref{where_clause} shows the operator tree built for the where clause of the SQL query given in example 単純な SelectThis example contains the following simple query that will be used in various descriptions and figures throughout the following sections. The query assumes that the tables given in The Supplier Database <!-- XXX The above citetitle should really be an xref, but that part has not yet been converted from Stefan's original document. - thomas 1999-02-11 --> have already been defined. select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno;この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 XXX 上記の citetitle は当然 xref タグ付きですが、Stefan の元のドキュメント ではこの部分は未だ変換されていません。 - thomas 1999-02-11 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; which is attached to the field qual of the SelectStmt node. The top node of the operator tree is an A_Expr node representing an AND operation. This node has two successors called lexpr and rexpr pointing to two subtrees. The subtree attached to lexpr represents the qualification s.sno > 2 and the one attached to rexpr represents s.sno = se.sno. For every attribute an Attr node is created holding the name of the relation and a pointer to a Value node holding the name of the attribute. For the constant term appearing in the query a Const node is created holding the value.
図 \ref{where_clause} は SelectStmt ノードの qual フィールドに添付される、例 単純な SelectThis example contains the following simple query that will be used in various descriptions and figures throughout the following sections. The query assumes that the tables given in The Supplier Database <!-- XXX The above citetitle should really be an xref, but that part has not yet been converted from Stefan's original document. - thomas 1999-02-11 --> have already been defined. select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno;この例は簡単な問合せで、以降の節を通して色々な場面での 記述と図とで参照されます。 問合せは The Supplier Database で与えられる テーブルが既に定義されているものと仮定しています。 XXX 上記の citetitle は当然 xref タグ付きですが、Stefan の元のドキュメント ではこの部分は未だ変換されていません。 - thomas 1999-02-11 select s.sname, se.pno from supplier s, sells se where s.sno > 2 and s.sno = se.sno; で示した SQL 問合せの where 句に対して生成された演算子ツリーを示して います。 演算子ツリーの最上ノードは AND 演算を示す A_Expr ノードです。このノードは二つの サブツリーのアドレスを格納する lexpr と rexpr と呼ばれる 二つの継承を持ちます。 lexpr に所属するサブツリーは s.sno > 2 の制限を示し、rexpr に所属するサブツリーは s.sno = se.sno の制限を 示します。全ての属性に対して、リレーション名と、属性名を を持った Value ノードへのポインタを示す Attr ノードが生成されます。問合せで常に出て来る 文言に対しては、その値を持った Const ノードが 生成されます。
The transformation process takes the tree handed back by the parser as input and steps recursively through it. If a SelectStmt node is found, it is transformed to a Query node which will be the top most node of the new data structure. Figure \ref{transformed} shows the transformed data structure (the part for the transformed where clause is given in figure \ref{transformed_where} because there was not enough space to show all parts in one figure).
変換プロセスは入力としてパーサから戻されたツリー を取得する繰り返しのプロセスです。 SelectStmt ノードが見つかった時、このノードは新しい データ構造の最上層のノードである Query ノードに変換 されます。図 \ref{transformed} は変換されたデータ構造を示しています。 変換された where 句 の一部は全ての構造を一つの 図に示すことが困難なため、図 \ref{transformed_where} に示してあります。
Now a check is made, if the relation names in the FROM clause are known to the system. For every relation name that is present in the system catalogs a RTE node is created containing the relation name, the alias name and the relation id. From now on the relation ids are used to refer to the relations given in the query. All RTE nodes are collected in the range table entry list which is connected to the field rtable of the Query node. If a name of a relation that is not known to the system is detected in the query an error will be returned and the query processing will be aborted.
もし FROM 句における リレーション名がシステムに存在していれば検証に 取り掛かります。 システムカタログに存在する全てのリレーション名に 対して、リレーション名、エイリアス名および リレーション ID を持つ RTE ノードが生成されます。 これ以降、リレーション ID は与えられた問合せの リレーションを参照するために使用されます。 全ての RTE ノードは、 問合せノード の rtable フィールドに接続する range table entry list にまとめられます。 システムに登録されていないリレーションが検出された場合はエラーが返され 問合せ処理は終了します。
Next it is checked if the attribute names used are contained in the relations given in the query. For every attribute} that is found a TLE node is created ^ TEX からの変換ミスか、下にもあり。 holding a pointer to a Resdom node (which holds the name of the column) and a pointer to a VAR node. There are two important numbers in the VAR node. The field varno gives the position of the relation containing the current attribute} in the range table entry list ^ created above. The field varattno gives the position of the attribute within the relation. If the name of an attribute cannot be found an error will be returned and the query processing will be aborted.
次に問合せで与えられたリレーションの中に 属性名が 用いられているかどうか検証されます。 検出された全ての属性に対し（カラム名を持った）Resdom ノードと VAR ノードへのポインタを持った TLE ノードが生成されます。 VAR ノードには重要な二つの数値が あります。varattno フィールドは、上で作られた range table entry list にある現在の属性を持ったりレーションの場所を 知らせます。 varattno フィールドはりレーション内での属性の位置 知らせます。 属性名が検出されなかった場合はエラーが返され問合せ処理は終了します。