3.1. Overview

In PostgreSQL, a single backend process typically handles all queries issued by a connected client.

The backend consists of five primary subsystems:

  1. Parser: Creates a parse tree from a plain-text SQL statement.
  2. Analyzer/Analyser: Performs semantic analysis of the parse tree and creates a query tree.
  3. Rewriter: Transforms the query tree according to rules stored in the rule system, if any such rules exist.
  4. Planner: Creates the most efficient plan tree from the query tree.
  5. Executor: Executes the query by accessing tables and indexes in the order specified by the plan tree.
Figure 3.1. Query Processing.

This section provides an overview of these subsystems. Because the planner and the executor are highly complex, their functions are explained in detail in the subsequent sections.

Section Contents

3.1.1. Parser

The parser creates a parse tree from a plain-text SQL statement that can be processed by subsequent subsystems. Below is a specific example illustrating this process.

Consider the following query:

testdb=# SELECT id, data FROM tbl_a WHERE id < 300 ORDER BY data;

A parse tree is a data structure whose root is the SelectStmt structure, defined in parsenodes.h.

Figure 3.2(b) illustrates the parse tree of the query shown in Figure 3.2(a).

typedef struct SelectStmt
{
	NodeTag		type;

	/*
	 * These fields are used only in "leaf" SelectStmts.
	 */
	List	   *distinctClause; /* NULL, list of DISTINCT ON exprs, or
								 * lcons(NIL,NIL) for all (SELECT DISTINCT) */
	IntoClause *intoClause;		/* target for SELECT INTO */
	List	   *targetList;		/* the target list (of ResTarget) */
	List	   *fromClause;		/* the FROM clause */
	Node	   *whereClause;	/* WHERE qualification */
	List	   *groupClause;	/* GROUP BY clauses */
	bool		groupDistinct;	/* Is this GROUP BY DISTINCT? */
	Node	   *havingClause;	/* HAVING conditional-expression */
	List	   *windowClause;	/* WINDOW window_name AS (...), ... */

	/*
	 * In a "leaf" node representing a VALUES list, the above fields are all
	 * null, and instead this field is set.  Note that the elements of the
	 * sublists are just expressions, without ResTarget decoration. Also note
	 * that a list element can be DEFAULT (represented as a SetToDefault
	 * node), regardless of the context of the VALUES list. It's up to parse
	 * analysis to reject that where not valid.
	 */
	List	   *valuesLists;	/* untransformed list of expression lists */

	/*
	 * These fields are used in both "leaf" SelectStmts and upper-level
	 * SelectStmts.
	 */
	List	   *sortClause;		/* sort clause (a list of SortBy's) */
	Node	   *limitOffset;	/* # of result tuples to skip */
	Node	   *limitCount;		/* # of result tuples to return */
	LimitOption limitOption;	/* limit type */
	List	   *lockingClause;	/* FOR UPDATE (list of LockingClause's) */
	WithClause *withClause;		/* WITH clause */

	/*
	 * These fields are used only in upper-level SelectStmts.
	 */
	SetOperation op;			/* type of set op */
	bool		all;			/* ALL specified? */
	struct SelectStmt *larg;	/* left child */
	struct SelectStmt *rarg;	/* right child */
	/* Eventually add fields for CORRESPONDING spec here */
} SelectStmt;
Figure 3.2. An example of a parse tree.

The elements of the SELECT query are mapped to corresponding nodes in the parse tree, indicated by the matching numbers in Figure 3.2. For example:

  • (1) is an item in the target list, representing the ‘id’ column.
  • (4) represents the WHERE clause.

The parser validates only the syntax of the input query. Consequently, it returns an error only if the query contains a syntax violation.

The parser does not perform semantic checks; for example, it will not return an error even if the query references a non-existent table. All semantic validations are handled by the analyzer/analyser.

3.1.2. Analyzer/Analyser

The analyzer/analyser performs a semantic analysis of the parse tree created by the parser and produces a query tree.

The root of a query tree is the Query structure, defined in parsenodes.h. This structure contains metadata for the query — such as the command type (SELECT, INSERT, etc.) — and several leaves. Each leaf constitutes a list or a tree that holds data for a specific clause.

/*
 * Query -
 *	  Parse analysis turns all statements into a Query tree
 *	  for further processing by the rewriter and planner.
 *
 *	  Utility statements (i.e. non-optimizable statements) have the
 *	  utilityStmt field set, and the rest of the Query is mostly dummy.
 *
 *	  Planning converts a Query tree into a Plan tree headed by a PlannedStmt
 *	  node --- the Query structure is not used by the executor.
 *
 *	  All the fields ignored for the query jumbling are not semantically
 *	  significant (such as alias names), as is ignored anything that can
 *	  be deduced from child nodes (else we'd just be double-hashing that
 *	  piece of information).
 */
typedef struct Query
{
	NodeTag		type;

	CmdType		commandType;	/* select|insert|update|delete|merge|utility */

	/* where did I come from? */
	QuerySource querySource pg_node_attr(query_jumble_ignore);

	/*
	 * query identifier (can be set by plugins); ignored for equal, as it
	 * might not be set; also not stored.  This is the result of the query
	 * jumble, hence ignored.
	 *
	 * We store this as a signed value as this is the form it's displayed to
	 * users in places such as EXPLAIN and pg_stat_statements.  Primarily this
	 * is done due to lack of an SQL type to represent the full range of
	 * uint64.
	 */
	int64		queryId pg_node_attr(equal_ignore, query_jumble_ignore, read_write_ignore, read_as(0));

	/* do I set the command result tag? */
	bool		canSetTag pg_node_attr(query_jumble_ignore);

	Node	   *utilityStmt;	/* non-null if commandType == CMD_UTILITY */

	/*
	 * rtable index of target relation for INSERT/UPDATE/DELETE/MERGE; 0 for
	 * SELECT.  This is ignored in the query jumble as unrelated to the
	 * compilation of the query ID.
	 */
	int			resultRelation pg_node_attr(query_jumble_ignore);

	/* has aggregates in tlist or havingQual */
	bool		hasAggs pg_node_attr(query_jumble_ignore);
	/* has window functions in tlist */
	bool		hasWindowFuncs pg_node_attr(query_jumble_ignore);
	/* has set-returning functions in tlist */
	bool		hasTargetSRFs pg_node_attr(query_jumble_ignore);
	/* has subquery SubLink */
	bool		hasSubLinks pg_node_attr(query_jumble_ignore);
	/* distinctClause is from DISTINCT ON */
	bool		hasDistinctOn pg_node_attr(query_jumble_ignore);
	/* WITH RECURSIVE was specified */
	bool		hasRecursive pg_node_attr(query_jumble_ignore);
	/* has INSERT/UPDATE/DELETE/MERGE in WITH */
	bool		hasModifyingCTE pg_node_attr(query_jumble_ignore);
	/* FOR [KEY] UPDATE/SHARE was specified */
	bool		hasForUpdate pg_node_attr(query_jumble_ignore);
	/* rewriter has applied some RLS policy */
	bool		hasRowSecurity pg_node_attr(query_jumble_ignore);
	/* parser has added an RTE_GROUP RTE */
	bool		hasGroupRTE pg_node_attr(query_jumble_ignore);
	/* is a RETURN statement */
	bool		isReturn pg_node_attr(query_jumble_ignore);

	List	   *cteList;		/* WITH list (of CommonTableExpr's) */

	List	   *rtable;			/* list of range table entries */

	/*
	 * list of RTEPermissionInfo nodes for the rtable entries having
	 * perminfoindex > 0
	 */
	List	   *rteperminfos pg_node_attr(query_jumble_ignore);
	FromExpr   *jointree;		/* table join tree (FROM and WHERE clauses);
								 * also USING clause for MERGE */

	List	   *mergeActionList;	/* list of actions for MERGE (only) */

	/*
	 * rtable index of target relation for MERGE to pull data. Initially, this
	 * is the same as resultRelation, but after query rewriting, if the target
	 * relation is a trigger-updatable view, this is the index of the expanded
	 * view subquery, whereas resultRelation is the index of the target view.
	 */
	int			mergeTargetRelation pg_node_attr(query_jumble_ignore);

	/* join condition between source and target for MERGE */
	Node	   *mergeJoinCondition;

	List	   *targetList;		/* target list (of TargetEntry) */

	/* OVERRIDING clause */
	OverridingKind override pg_node_attr(query_jumble_ignore);

	OnConflictExpr *onConflict; /* ON CONFLICT DO [NOTHING | UPDATE] */

	/*
	 * The following three fields describe the contents of the RETURNING list
	 * for INSERT/UPDATE/DELETE/MERGE. returningOldAlias and returningNewAlias
	 * are the alias names for OLD and NEW, which may be user-supplied values,
	 * the defaults "old" and "new", or NULL (if the default "old"/"new" is
	 * already in use as the alias for some other relation).
	 */
	char	   *returningOldAlias pg_node_attr(query_jumble_ignore);
	char	   *returningNewAlias pg_node_attr(query_jumble_ignore);
	List	   *returningList;	/* return-values list (of TargetEntry) */

	List	   *groupClause;	/* a list of SortGroupClause's */
	bool		groupDistinct;	/* is the group by clause distinct? */

	List	   *groupingSets;	/* a list of GroupingSet's if present */

	Node	   *havingQual;		/* qualifications applied to groups */

	List	   *windowClause;	/* a list of WindowClause's */

	List	   *distinctClause; /* a list of SortGroupClause's */

	List	   *sortClause;		/* a list of SortGroupClause's */

	Node	   *limitOffset;	/* # of result tuples to skip (int8 expr) */
	Node	   *limitCount;		/* # of result tuples to return (int8 expr) */
	LimitOption limitOption;	/* limit type */

	List	   *rowMarks;		/* a list of RowMarkClause's */

	Node	   *setOperations;	/* set-operation tree if this is top level of
								 * a UNION/INTERSECT/EXCEPT query */

	/*
	 * A list of pg_constraint OIDs that the query depends on to be
	 * semantically valid
	 */
	List	   *constraintDeps pg_node_attr(query_jumble_ignore);

	/* a list of WithCheckOption's (added during rewrite) */
	List	   *withCheckOptions pg_node_attr(query_jumble_ignore);

	/*
	 * The following two fields identify the portion of the source text string
	 * containing this query.  They are typically only populated in top-level
	 * Queries, not in sub-queries.  When not set, they might both be zero, or
	 * both be -1 meaning "unknown".
	 */
	/* start location, or -1 if unknown */
	ParseLoc	stmt_location;
	/* length in bytes; 0 means "rest of string" */
	ParseLoc	stmt_len pg_node_attr(query_jumble_ignore);
} Query;

Figure 3.3 illustrates the query tree for the query shown in Figure 3.2(a) from the previous subsection.

Figure 3.3. The Query Tree of the SELECT query in Figure 3.2.

The query tree shown above is summarized as follows:

  • targetlist: A list of columns that form the result of the query. In this example, the list contains two columns: ‘id’ and ‘data’. If the input query uses an asterisk (’*’), the analyzer/analyser explicitly expands it into all available columns.
  • range table: A list of relations (tables) used in the query. In this example, the range table holds metadata for ’tbl_a’, such as its OID and name.
  • jointree: A structure that stores the FROM and WHERE clauses.
  • sortClause: A list of SortGroupClause structures.

The official documentation briefly describes the details of query trees.

3.1.3. Rewriter

The rewriter is the subsystem based on the rule system. It transforms a query tree according to the rules stored in the pg_rules system catalog, when applicable.

Although the rewriter and the rule system are powerful features, this section focuses on how they implement Views, using a specific example.

3.1.3.1. Views

When a view is defined with the CREATE VIEW command, a corresponding rule is automatically created and stored in the system catalog.

Assume that the following view has been defined and its corresponding rule is stored in the pg_rules system catalog:

sampledb=# CREATE VIEW employees_list
sampledb-#      AS SELECT e.id, e.name, d.name AS department
sampledb-#            FROM employees AS e, departments AS d WHERE e.department_id = d.id;

When the query shown below is issued, the parser creates a parse tree as illustrated in Figure 3.4(a).

sampledb=# SELECT * FROM employees_list;

At this stage, the rewriter transforms the range table node into a subquery parse tree based on the view definition stored in pg_rules system catalog.

Figure 3.4. An example of the rewriter stage.
Info

Because PostgreSQL implements views using this mechanism, they were not updatable prior to version 9.2. Although updatable views were introduced in version 9.3, several limitations remain. For further details, refer to the official documentation.

3.1.4. Planner and Executor

The planner receives a query tree from the rewriter and creates a (query) plan tree optimized for efficient execution by the executor.

PostgreSQL’s planner is based on pure cost-based optimization; it does not support rule-based optimization or hints. As the most complex subsystem in PostgreSQL, a detailed overview of the planner is provided in the subsequent sections of this chapter.

pg_hint_plan

PostgreSQL does not support planner hints in SQL, and there are no plans to support them in the future.

To use hints in queries, consider installing the pg_hint_plan extension.

Similar to other RDBMSs, the EXPLAIN command in PostgreSQL displays the plan tree. A specific example is shown below:

1
2
3
4
5
6
7
8

testdb=# EXPLAIN SELECT * FROM tbl_a WHERE id < 300 ORDER BY data;
                          QUERY PLAN
---------------------------------------------------------------
 Sort  (cost=182.34..183.09 rows=300 width=8)
   Sort Key: data
   ->  Seq Scan on tbl_a  (cost=0.00..170.00 rows=300 width=8)
         Filter: (id < 300)
(4 rows)

This output represents the plan tree illustrated in Figure 3.5.

Figure 3.5. A simple plan tree and the relationship between the plan tree and the result of the EXPLAIN command.

A plan tree is composed of elements called plan nodes, which are linked to the plantree list of the PlannedStmt structure. These elements are defined in plannodes.h. For more details, refer to Section 3.3.3 and Section 3.5.4.2.

Each plan node contains the metadata required by the executor. In a single-table query, data flows through the plan tree from the leaves (bottom) up to the root. This execution follows the Volcano Model (also known as the Iterator Model), where tuples are processed and passed upward one at a time.

For example, the plan tree in Figure 3.5. consists of a Sort node and a Sequential Scan node. Consequently, the executor performs a sequential scan of the table tbl_a and then sorts the retrieved result1.

The executor interacts with tables and indexes via the buffer manager, as described in Chapter 8. During processing, the executor utilizes allocated memory areas such as temp_buffers and work_mem, and creates temporary files if the data exceeds the available memory. See Figure 3.6.

Furthermore, when accessing tuples, PostgreSQL employs a concurrency control mechanism to maintain the atomicity and isolation of active transactions. This mechanism is detailed in Chapter 5.

Figure 3.6. The relationship among the executor, buffer manager and temporary files.

  1. From the perspective of control flow rather than data flow, the executor processes the plan tree from the top down. For instance, in this example, the executor invokes the Sort node, which in turn triggers the Sequential Scan node. ↩︎