Query Optimizer in PostgreSQL

Query optimization is one of the most important processes in the relational database system and the query optimizer is referred to the module in a database engine conducting this query optimization process. Sometimes the module is also called as query compiler or query planner. The role of this module is to understand user-issued queries and try to find the most efficient way to evaluate them. Most RDBMSs have their own query optimizer and PostgreSQL has also a great query optimizer. In this post, we present some details about PostgreSQL’s query optimizer.

First, why does a database system need a query optimizer? SQL is declarative, that is, users specify what they need to find not how to find it. When database systems are requested to process users’ SQL, the first thing to do is to understand the SQL (what the user requests) and then the system find how the request can be evaluated. Usually, there are many ways to process a SQL and the efficiency of database might be decided by whether it can find the most efficient way to process users’ SQL queries.

There are many articles and presentations about query optimizer. Here are some helpful materials to understand the basics of PostgreSQL query optimizer.

• Great blog post about basic concepts of query optimization http://jinchengli.me/post/postgres-query-opt/?utm_source=postgresweekly&utm_medium=email

• PGCon presentation about query optimization 2016 Beyond Explain: Query Optimization From Theory to Code 2011 Hacking the Query Planner

PostgreSQL optimizer uses the “System-R style” optimization, which was introduced in the seminal paper published by IBM research center in 1979, “Access Path Selection in a Relational Database Management System”. This method is also called as Selinger optimization after the name of the main author. This is also base method for many database systems, such as MySQL, DB2, and Oracle.

Selinger optimization uses cost estimation regarding I/O and CPU operations for each relational operator. The main goal of this method is to find a plan with minimum cost. To save processing and space cost of enumerating possible plans, this method exploits a dynamic programming approach.

Although lots of query optimization techniques have been developed since the paper was published, this technique still forms the base of many query optimizers. There are also other methods including Volcano/Cascades. You can find more historical and basic details about general query optimizer technologies in following research papers:

1. Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System, ACM SIGMOD, 1979
2. Goetz Graefe and William J. McKenna: The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE, 1993
3. Surajit Chaudhuri: An Overview of Query Optimization in Relational Systems, PODS 1998

From now on, we’ll present how the query optimizer of PostgreSQL is implemented. The source code of the query optimizer is very huge because the optimizer should handle various complex structures of SQL queries and a lot of information mainly related to Meta data within a query and database. So we cannot go into details and rather explain the source code structure briefly to give some starting points for understanding the behavior of the PostgreSQL’s query optimization.

Source codes of PostgreSQL’s query optimizer are structured as follows:

▲ from PGCon 2011, Hacking the Query Planner

When a query is parsed and analyzed, Query structure is made for the query. Query can be regarded as annotated parse tree. It is used for metadata check and query rewrite. Then pg_plan_query function transform Query structure to PlannedStmt, which is a wrapper structure for Plan structure. Plan structure represents the evaluation process of a query and this is the output of planning is represented as a plan. A Plan is a tree of plan nodes, which represents a relational operation (i.e., table scan, join, sort, etc.) During main planning process, Path tree is used rather than Plan structure.

One of the most important processes of planning is to decide join ordering, which uses Selinger method mentioned above. This method uses a dynamic programming and the intermediate solutions are represented as RelOptInfo structure, which has Path structure. RelOptInfo represents of which subproblem the structure deal with (that is, a set of relations in the query) and Path represents the cheapest solution for the subproblem.

query_planner function in planmain.c produces RelOptInfo structure.

In this post, we briefly describe what query optimization is and how it is implemented in PostgreSQL.