Query Execution and the Optimizer

SQL states what result is wanted, not how to compute it. The optimizer picks how. This lesson covers the steps between sending a query and receiving rows, and the parts of the optimizer that interviews ask about. Reading plans is covered in Query Plans.

Example 1: the pipeline

flowchart LR
    A[SQL text] --> B["Parser<br/>syntax check, parse tree"]
    B --> C["Analyzer<br/>resolve names and types"]
    C --> D["Rewriter<br/>expand views, apply rules"]
    D --> E["Planner / optimizer<br/>generate paths, pick cheapest"]
    E --> F["Executor<br/>run the plan, return rows"]

The executor is a tree of nodes; each node asks its children for the next row (the iterator model).

Example 2: cost-based optimization

The planner generates candidate plans, estimates the cost of each in abstract units, and picks the cheapest. Costs are built from settings:

SELECT name, setting
FROM pg_settings
WHERE name IN ('seq_page_cost', 'random_page_cost', 'cpu_tuple_cost', 'cpu_index_tuple_cost', 'cpu_operator_cost')
ORDER BY name;

         name         | setting 
----------------------+---------
 cpu_index_tuple_cost | 0.005
 cpu_operator_cost    | 0.0025
 cpu_tuple_cost       | 0.01
 random_page_cost     | 4
 seq_page_cost        | 1
(5 rows)

Cost = pages read x page cost + rows processed x CPU cost. The estimate depends on how many rows each step returns (cardinality), which comes from statistics. Oracle, SQL Server, and MySQL also use cost-based optimizers.

Example 3: statistics in pg_stats

ANALYZE samples table rows and stores per-column statistics. A demo table of 20000 rows (small enough to be read completely, so the numbers are exact):

CREATE TABLE stats_demo AS
SELECT g AS id,
       CASE WHEN g % 10 < 5 THEN 'A' WHEN g % 10 < 8 THEN 'B' ELSE 'C' || (g % 100) END AS grade,
       g % 1000 AS bucket
FROM generate_series(1, 20000) g;
ANALYZE stats_demo;

SELECT attname, n_distinct, null_frac
FROM pg_stats
WHERE tablename = 'stats_demo'
ORDER BY attname;

 attname | n_distinct | null_frac 
---------+------------+-----------
 bucket  |       1000 |         0
 grade   |         22 |         0
 id      |         -1 |         0
(3 rows)

Example 4: most common values and histograms

SELECT (most_common_vals::text::text[])[1:3] AS top_values,
       (most_common_freqs::text::real[])[1:3] AS top_freqs
FROM pg_stats
WHERE tablename = 'stats_demo' AND attname = 'grade';

SELECT (histogram_bounds::text::text[])[1:5] AS first_bounds
FROM pg_stats
WHERE tablename = 'stats_demo' AND attname = 'id';

 top_values |   top_freqs    
------------+----------------
 {A,B,C18}  | {0.5,0.3,0.01}
(1 row)

    first_bounds     
---------------------
 {1,200,400,600,800}
(1 row)

Equality on a common value uses its recorded frequency. Equality on other values uses the remaining fraction divided by the remaining distinct values. Range conditions use the histogram: each bucket holds about the same number of rows, so the fraction of buckets covered estimates the fraction of rows. The number of buckets and common values is set by default_statistics_target (100, raised per column with ALTER TABLE ... ALTER COLUMN ... SET STATISTICS).

Example 5: cardinality estimates

The estimated row count of a plan node is compared with the actual count. A helper reads the estimate from EXPLAIN:

CREATE FUNCTION est_rows(q text) RETURNS bigint LANGUAGE plpgsql AS $$
DECLARE j json;
BEGIN
  EXECUTE 'EXPLAIN (FORMAT JSON) ' || q INTO j;
  RETURN (j->0->'Plan'->>'Plan Rows')::bigint;
END $$;

SELECT est_rows($$SELECT * FROM stats_demo WHERE grade = 'A'$$) AS est_common_value,
       (SELECT count(*) FROM stats_demo WHERE grade = 'A') AS actual_common_value,
       est_rows($$SELECT * FROM stats_demo WHERE id < 2000$$) AS est_range,
       (SELECT count(*) FROM stats_demo WHERE id < 2000) AS actual_range;

 est_common_value | actual_common_value | est_range | actual_range 
------------------+---------------------+-----------+--------------
            10000 |               10000 |      1999 |         1999
(1 row)

Both estimates are accurate because the columns have MCV and histogram statistics.

Example 6: correlated columns break the estimate

The planner assumes that conditions on different columns are independent and multiplies their selectivities. When columns are correlated, the estimate is far too low, and a low estimate can select a nested loop join that is slow at the real row count.

CREATE TABLE places AS
SELECT g AS id, g % 100 AS zip, g % 100 AS area_code
FROM generate_series(1, 20000) g;
ANALYZE places;

SELECT est_rows($$SELECT * FROM places WHERE zip = 7 AND area_code = 7$$) AS estimated,
       (SELECT count(*) FROM places WHERE zip = 7 AND area_code = 7) AS actual;

 estimated | actual 
-----------+--------
         2 |    200
(1 row)

The estimate is 20000 x 1/100 x 1/100 = 2 rows, while 200 rows match. CREATE STATISTICS tells the planner about the dependency:

CREATE STATISTICS places_dep (dependencies) ON zip, area_code FROM places;
ANALYZE places;

SELECT est_rows($$SELECT * FROM places WHERE zip = 7 AND area_code = 7$$) AS estimated,
       (SELECT count(*) FROM places WHERE zip = 7 AND area_code = 7) AS actual;

 estimated | actual 
-----------+--------
       200 |    200
(1 row)

Other fixes for bad estimates: ANALYZE after bulk loads, a higher statistics target, expression indexes (which also collect statistics), and rewriting the query. Outdated statistics, correlated columns, and conditions on expressions or function results are the usual causes. See Fixing Slow Queries.

Example 7: join algorithms

The three plans for the same join, forced with the enable_* settings. The tables have 10000 orders and 500 customers.

CREATE TABLE cust AS SELECT g AS id, 'c' || g AS name FROM generate_series(1, 500) g;
CREATE TABLE ord AS SELECT g AS id, (g % 500) + 1 AS cust_id FROM generate_series(1, 10000) g;
ALTER TABLE cust ADD PRIMARY KEY (id);
ANALYZE cust;
ANALYZE ord;

EXPLAIN (COSTS OFF)
SELECT c.name, o.id FROM ord o JOIN cust c ON c.id = o.cust_id;

SET enable_hashjoin = off;
EXPLAIN (COSTS OFF)
SELECT c.name, o.id FROM ord o JOIN cust c ON c.id = o.cust_id;

SET enable_nestloop = off;
EXPLAIN (COSTS OFF)
SELECT c.name, o.id FROM ord o JOIN cust c ON c.id = o.cust_id;
RESET enable_hashjoin;
RESET enable_nestloop;

           QUERY PLAN            
---------------------------------
 Hash Join
   Hash Cond: (o.cust_id = c.id)
   ->  Seq Scan on ord o
   ->  Hash
         ->  Seq Scan on cust c
(5 rows)

                    QUERY PLAN                    
--------------------------------------------------
 Nested Loop
   ->  Seq Scan on ord o
   ->  Memoize
         Cache Key: o.cust_id
         Cache Mode: logical
         ->  Index Scan using cust_pkey on cust c
               Index Cond: (id = o.cust_id)
(7 rows)

                 QUERY PLAN                 
--------------------------------------------
 Merge Join
   Merge Cond: (c.id = o.cust_id)
   ->  Index Scan using cust_pkey on cust c
   ->  Sort
         Sort Key: o.cust_id
         ->  Seq Scan on ord o
(6 rows)

The default plan is a hash join: the 500-row table is hashed and the 10000 orders probe it. With hash join off, the planner picks a nested loop that looks up each order's customer in the primary key index (Memoize caches repeated lookups). With nested loop also off, it sorts both inputs and uses a merge join. The enable_* settings do not forbid a method; they add a large cost to it. Use them to test and compare, not in application code.

Example 8: join order

For n tables there are n! join orders. The planner searches them with dynamic programming, joining the smallest intermediate results first. Above geqo_threshold (12 tables) it switches to a genetic search that does not guarantee the best plan. join_collapse_limit (default 8) caps how many explicit JOINs are reordered.

SHOW geqo_threshold;
SHOW join_collapse_limit;

 geqo_threshold 
----------------
 12
(1 row)

 join_collapse_limit 
---------------------
 8
(1 row)

A good order filters early: joining a 10-row filtered table to a 10-million-row table first keeps intermediate results small. Estimate errors compound through each join, so a wrong estimate in the first join affects every later choice.

Example 9: index scan vs sequential scan break-even

An index scan reads random heap pages; a sequential scan reads all pages in order. Above a certain fraction of matching rows, the sequential scan is cheaper.

CREATE TABLE big AS SELECT g AS id, (g * 7919) % 100000 AS k FROM generate_series(1, 100000) g;
CREATE INDEX ON big (k);
ANALYZE big;

EXPLAIN (COSTS OFF) SELECT * FROM big WHERE k = 5;
EXPLAIN (COSTS OFF) SELECT * FROM big WHERE k < 5000;
EXPLAIN (COSTS OFF) SELECT * FROM big WHERE k < 50000;

            QUERY PLAN             
-----------------------------------
 Index Scan using big_k_idx on big
   Index Cond: (k = 5)
(2 rows)

              QUERY PLAN              
--------------------------------------
 Bitmap Heap Scan on big
   Recheck Cond: (k < 5000)
   ->  Bitmap Index Scan on big_k_idx
         Index Cond: (k < 5000)
(4 rows)

      QUERY PLAN       
-----------------------
 Seq Scan on big
   Filter: (k < 50000)
(2 rows)

k is a shuffled permutation of 0-99999, so index order does not match table order. The queries return 1 row (0.001%), 5% of the rows, and 50% of the rows. With the default random_page_cost = 4, the planner uses the index for 1 row, a bitmap scan for 5%, and a sequential scan for 50%. The break-even lies between these fractions and depends on how well the index order matches the table order. Lowering random_page_cost (1.1 is common for SSDs) moves it toward larger fractions.

Example 10: prepared statements and plan caching

PREPARE parses a statement once and reuses it. Each execution uses a custom plan (built for the parameter values) or a generic plan (parameter-independent, cached). By default PostgreSQL uses custom plans for the first 5 executions, then switches to the generic plan if its estimated cost is not much worse than the average custom cost.

PREPARE by_k (int) AS SELECT count(*) FROM big WHERE k = $1;
EXECUTE by_k(1);
EXECUTE by_k(2);
EXECUTE by_k(3);
EXECUTE by_k(4);
EXECUTE by_k(5);
EXECUTE by_k(6);
EXECUTE by_k(7);

SELECT name, generic_plans, custom_plans
FROM pg_prepared_statements;

SHOW plan_cache_mode;

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 count 
-------
     1
(1 row)

 name | generic_plans | custom_plans 
------+---------------+--------------
 by_k |             2 |            5
(1 row)

 plan_cache_mode 
-----------------
 auto
(1 row)

Benefits: less parse and plan time, and protection from SQL injection because parameters are never part of the SQL text. Risk: a generic plan can be poor for skewed values; plan_cache_mode = force_custom_plan avoids it. Drivers such as JDBC and psycopg use server-side prepared statements automatically after a few executions.

Example 11: query hints

PostgreSQL has no hint syntax in SQL comments. The core tools:

Oracle (/*+ INDEX(t idx) */), MySQL (USE INDEX, STRAIGHT_JOIN), and SQL Server (OPTION (HASH JOIN), WITH (INDEX(...))) support hints in the query text. Fixing statistics is preferred to hints, because a hint stays wrong when the data changes.

Example 12: connection handling and pooling

PostgreSQL starts one operating system process per connection. Each process uses memory (several MB plus work_mem per sort or hash), and many processes cause context switching, so max_connections is kept at a few hundred at most.

SELECT pg_backend_pid() > 0 AS has_own_backend_process;
SHOW max_connections;

 has_own_backend_process 
-------------------------
 t
(1 row)

 max_connections 
-----------------
 100
(1 row)

MySQL uses a thread per connection; Oracle and SQL Server use processes or threads with their own schedulers.

A connection pooler such as PgBouncer sits between the application and the database and shares a small number of server connections among many clients.

flowchart LR
    A1[App 1] --> P
    A2[App 2] --> P
    A3[App 1000] --> P
    P["PgBouncer<br/>1000 client connections"] --> D["PostgreSQL<br/>20 server connections"]

[pgbouncer]
pool_mode = transaction
max_client_conn = 1000
default_pool_size = 20

Pool size is set from CPU cores and disk parallelism, not from the number of clients. A pool that is too large makes queries compete for the same CPUs.

Summary

• Pipeline: parse, analyze, rewrite, plan, execute; the planner picks the cheapest of many candidate plans using cost formulas.
• Row estimates come from pg_stats (n_distinct, most common values, histograms); stale statistics and correlated columns produce wrong estimates and bad plans. Fix with ANALYZE and CREATE STATISTICS.
• Nested loop suits a small outer side with an inner index, hash join suits large unordered equality joins, merge join suits sorted inputs.
• Sequential scans beat index scans when a large fraction of rows match; prepared statements cache plans; hints are limited in PostgreSQL.
• PostgreSQL uses a process per connection, so a pooler such as PgBouncer is used for many clients.