2.3. The Parser Stage

2.3.1. 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.

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.

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.

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.

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.

For a better understanding of the data structures used in PostgreSQL for the processing of a query we use an example to illustrate the changes made to these data structures in every stage. 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 have already been defined.

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 Example 2-1 (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).

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.

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.

Figure \ref{where_clause} shows the operator tree built for the where clause of the SQL query given in Example 2-1 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.

2.3.2. Transformation Process

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 that 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).

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 that 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.

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 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.