Query plans and execution

When you write SELECT … JOIN … WHERE …, the database does not run your text directly. It turns the text into a plan: a tree of steps that fetch, join, sort and count rows. Many plans can give the same answer, and they can differ in speed by a factor of thousands. Knowing how the plan is built is the first step to fixing a slow query.

The big idea: four stages

A query passes through four stages, in order.

• Parse. The SQL string becomes a parse tree. Syntax errors stop here.
• Rewrite. Views are expanded into their underlying queries, and * is expanded into column names. Types and functions are resolved. The output is a query tree.
• Plan. The planner lists ways to find each table's rows and orders for the joins. It gives each option an estimated cost, in disk pages and CPU, and keeps the cheapest.
• Execute. The plan runs. Most engines use the iterator (Volcano) model. Each operator has a next() call that returns one row, and a parent pulls rows from its children one at a time.

Pulling one row at a time keeps memory low. A few operators, such as a sort or the build side of a hash join, must collect all their input before they can return anything.

Walking through a small plan

Here is a simple query on two tables, and the plan that a database might choose.

SELECT c.name, o.total_cents
FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.status = 'paid';

Hash Join                       ← build a hash table on customers, probe with orders
  ->  Seq Scan on orders        ← read every order row, keep status = 'paid'
  ->  Seq Scan on customers     ← read every customer row into the hash table

Read it bottom up for data flow: the scans produce rows, and the join consumes them. Read it top down for control: the top node asks for rows, and the requests flow down.

Two ways to see a plan

• EXPLAIN shows the plan the planner would run. It does not run the query, so it is safe and fast.
• EXPLAIN ANALYZE runs the query and adds real time and real row counts to each node.

Common mistakes

• Reading the plan from the top only. Data flows from the leaves up, so the slow step is often a leaf.
• Assuming EXPLAIN shows real timings. It shows estimates. Use ANALYZE to see what happened.
• Running EXPLAIN ANALYZE on production writes. It executes the statement.

Check yourself

1. Why does the executor pull rows one at a time instead of building every intermediate result? Pulling keeps memory low, because each operator passes rows along as soon as they are ready.
2. What is the difference between EXPLAIN and EXPLAIN ANALYZE? EXPLAIN shows the planned tree with estimates. EXPLAIN ANALYZE runs the query and adds real time and row counts.

Key takeaways

• SQL runs through parse, rewrite, plan and execute. Performance is decided mainly in the plan and in I/O.
• A plan is a tree of operators. Data flows from the leaves to the root.
• The planner chooses by estimated cost, so the quality of its estimates matters.
• EXPLAIN shows the plan. EXPLAIN ANALYZE shows what actually happened.

Further learning

Next, read access paths and selectivity to see how each table's rows are found, and why an index is not always the winner.

PostgreSQL docs: Using EXPLAIN14.1. Using EXPLAIN # 14.1.1. EXPLAIN Basics 14.1.2. EXPLAIN ANALYZE 14.1.3. Caveats PostgreSQL devises a query plan for each query it …PostgreSQL Documentation