Execution Plans Generated by the Planner

The EXPLAIN command only shows you the execution plan that PostgreSQL considered to be the least expensive. Unfortunately, you can't convince PostgreSQL to show the other execution plans that it considered. The most common performance question that we hear is "why didn't the database use my index?" If you could see all the alternatives, you could usually (but not always) answer that question.

When the optimizer generates a set of execution plans for a query, it starts by generating a set of plans that traverse each base table involved in the query. For a single-table query, there is only one base table and the planner generates a single set of execution plans. For a multitable query (a join), the planner starts by generating a set of traversal plans for each table.

There are only three ways that PostgreSQL can scan an individual table: a table scan (Seq Scan), an Index Scan, or a tuple-ID scan (TID Scan). For each table involved in the query, the planner generates one plan that makes a pass over the table using a Seq Scan operator. If the WHERE clause of the query selects one or more rows by ctid value, the planner generates a TID Scan. Next, the planner examines each index defined for the table. In theory, any single-table query can be satisfied by making a complete scan of a B-Tree index (assuming that the index is not a partial index), but the planner knows that a complete Index Scan is always more expensive than a complete Seq Scan and won't consider an Index Scan unless it offers some advantage.

An index is useful if it can reduce the number of tuples read from the table. If the WHERE clause for a query contains an expression of the form indexCol operator constant-expression or constant-expression operator indexCol, PostgreSQL may be able to use the index to read a subset of the table. For example, the recalls table has a B-Tree index that covers the record_id column. If you execute the query

perf=# SELECT * FROM recalls WHERE record_id > 8000;

the planner examines the expression record_id > 8000 and finds that it is written in the form indexCol operator constant-expressionthe record_id column is an indexCol. Notice that PostgreSQL looks for a constant-expression, not just a constant. That means that an expression such as record_id > (800 * 10) is acceptable as well. You can also include function calls in the constant-expression as long as the functions are not volatile. A volatile function (such as random()) can change value from row to row as PostgreSQL scans through the table. A constant-expression can include any operator that is not implemented by a volatile function.

Prior to version 8.0, PostgreSQL would only use an index if the data type of the indexed value exactly matched the data type of the constant-expression. Starting with 8.0, PostgreSQL will use an index if constant-expression can be coerced (that is, converted) to the same type as the indexed value.

An index is also useful if it can produce rows in a desired order. If an index produces rows in the sequence required by the ORDER BY clause, the planner will generate an Index Scan plan for the table. Some of the query operators (MergeJoin, Unique, Group, and Setop) require an ordered input set. For example, the Unique operator requires its input set to be ordered by the set of columns required to be unique. If an index can produce rows in the order required by one of these operators, the planner will generate an Index Scan plan for the table. A Hash index cannot produce rows in any particular order and therefore can't contribute to the ordering of a table.

What happens if you have two (or more) indexes that are useful to a given query? The planner generates a plan for each index and the optimizer chooses the least expensive plan among all of the alternatives.

Once the planner has generated a set of plans for each base table, it generates a set of plans to join the tables together according to the WHERE clause. PostgreSQL can join two tables together using any of three query operators: Merge Join, Hash Join, or Nested Loop. Consider a simple two-table query such as

movies=# SELECT * FROM rentals, customers
 WHERE rentals.customer_id = customers.customer_id;

Assuming that you have a B-Tree indexes that cover rentals.customer_id and customers.customer_id, the planner would generate the following plans to traverse each table individually:

SeqScan( rentals )
IndexScan( rentals.customer_id )
SeqScan( customers )
IndexScan( customers.customer_id )

To join these two tables together, the planner produces a set of execution plans.

First, the planner joins rentals and customers using the MergeJoin operator. Given that there are two paths through each table, the planner produces four MergeJoin plans for the combination of rentals and customers:

MergeJoin( IndexScan( rentals.customer_id ), IndexScan( customers.customer_id ))
MergeJoin(Sort( SeqScan( rentals )), Sort( SeqScan( customers )))
MergeJoin( IndexScan( rentals.customer_id ) , Sort( SeqScan( customers )))
MergeJoin( Sort( SeqScan( rentals )), IndexScan( customers.customer_id ))

Notice that the MergeJoin operator requires both input set to be ordered by the join columnbecause a SeqScan operator does not produce rows in any particular order, the planner inserts a Sort operator where needed.

Next, the planner produces a set of four NestedLoop plans:

NestedLoop( IndexScan( rentals.customer_id ), IndexScan( customers.customer_id ))
NestedLoop( SeqScan( rentals ), SeqScan( customers ))
NestedLoop( IndexScan( rentals.customer_id ) , SeqScan( customers ))
NestedLoop( SeqScan( rentals ), IndexScan( customers.customer_id ))

Then, the planner considers a set of four HashJoin plans:

HashJoin
(
 IndexScan( rentals.customer_id ),
 Hash( IndexScan( customers.customer_id ))
)

HashJoin
(
 SeqScan( rentals ),
 Hash( SeqScan( customers ))
)

HashJoin
(
 IndexScan( rentals.customer_id ) ,
 Hash( SeqScan( customers ))
)

HashJoin
(
 SeqScan( rentals ),
 Hash( IndexScan( customers.customer_id ))
)

The HashJoin operator requires the inner input set to be a hash table so the planner inserts a Hash operator in front of each of the inner tables.

For a simple join, the planner has considered 12 plans. But it's not finished yet. The planner generates a second set of plans using customers as the outer table and rentals as the inner table (in the first set of join plans, rentals served as the outer table and customers served as the inner table):

MergeJoin( IndexScan( customers.customer_id ), IndexScan( rentals.customer_id ))
MergeJoin(Sort( SeqScan( customers )), Sort( SeqScan( rentals )))
MergeJoin( IndexScan( customers.customer_id ) , Sort( SeqScan( rentals )))
MergeJoin( Sort( SeqScan(customers )), IndexScan( rentals.customer_id ))
NestedLoop( IndexScan( customers.customer_id ), IndexScan( rentals.customer_id ))
NestedLoop( SeqScan(customers ), SeqScan( rentals ))
NestedLoop( IndexScan(customers.customer_id ) , SeqScan( rentals ))
NestedLoop( SeqScan(customers ), IndexScan( rentals.customer_id ))
HashJoin(IndexScan(customers.customer_id), Hash(IndexScan(rentals.customer_id)))
HashJoin( SeqScan(customers ), Hash( SeqScan( rentals )))
HashJoin( IndexScan(customers.customer_id ) , Hash( SeqScan( rentals )))
HashJoin( SeqScan( customers ), Hash( IndexScan( rentals.customer_id )))

Once it's finished, the planner has considered 24 plans to join these two tables. In general, the planner will consider

joinOperatorCount x (( pathCount( table1 ) x pathCount( table2 )) x 2 )

plans to join any two tables, where pathCount(table ) is the number of possible paths (SeqScans, Index Scans, and TID Scans) through a given table and joinOperatorCount is always 3 in PostgreSQL (MergeJoin, NestedLoop, and HashJoin).

As you've seen, a two-table join will result in 24 possible plans (assuming that there are two paths through each table). Add a third table and the number of possible plans skyrockets. So how does the planner generate plans for a three-table join? It first generates a set of plans to join two of the three tables into a single result set then generates a set of plans to join the intermediate result set to the remaining table. With three tables (a, b, and c), you find the following combinations (note I've abbreviated MergeJoin and HashJoin here to better fit the printed page):

Merge( a, Join( b, c )) NestedLoop( a, Join( b, c )) Hash( a, Join( b, c ))
Merge( a, Join( c, b )) NestedLoop( a, Join( c, b )) Hash( a, Join( c, b ))
Merge( b, Join( a, c )) NestedLoop( b, Join( a, c )) Hash( b, Join( a, c ))
Merge( b, Join( c, a )) NestedLoop( b, Join( c, a )) Hash( b, Join( c, a ))
Merge( c, Join( a, b )) NestedLoop( c, Join( a, b )) Hash( c, Join( a, b ))
Merge( c, Join( c, b )) NestedLoop( c, Join( c, b )) Hash( c, Join( c, b ))
Merge( Join( a, b ), c ) NestedLoop( Join( a, b ), c ) Hash( Join( a, b ), c )
Merge( Join( a, c ), b ) NestedLoop( Join( a, c ), b ) Hash( Join( a, c ), b )
Merge( Join( b, a ), c ) NestedLoop( Join( b, a ), c ) Hash( Join( b, a ), c )
Merge( Join( b, c ), a ) NestedLoop( Join( b, c ), a ) Hash( Join( b, c ), a )
Merge( Join( c, a ), b ) NestedLoop( Join( c, a ), b ) Hash( Join( c, a ), b )
Merge( Join( c, b ), a ) NestedLoop( Join( c, b ), a ) Hash( Join( c, b ), a )

And considering that any of these two-table join results in 24 possible plans, you're suddenly looking at 864 possible plans! If you add a fourth table, the planner considers the plans needed to join three of the four tables into an intermediate result, then joins the fourth table to that.

In practice, the planner won't take the time to generate every possible planthe planner contains a number of heuristics that avoid generating plans that are known to be more expensive than plans already seen. For example, the planner knows that a complete Index Scan is more expensive than a complete Seq Scan and it won't generate a plan that includes a complete Index Scan unless the ordering of the result set is important.

In fact, when you reach a certain point, the plan generator switches from a near-exhaustive search to an algorithm known as the genetic query optimizer. The genetic optimizer evolves a plan by mutating and recombining possible join plans and then evaluating each generation for its "fitness." As each generation emerges, the genetic optimizer selects those mutations and recombinations that result in lower execution plans. The plan that eventually evolves is not guaranteed to be the best possible plan, but it is typically a "good" plan. By default, PostgreSQL uses the genetic query optimizer when the FROM clause of a query refers to 12 or more tables.