Skip to content

Query Optimization

Rule-Based Optimizer (RBO): Uses a fixed set of heuristics to transform queries. Access paths Are chosen based on rules like “use an index if available” and “avoid full table scans.” RBO does Not consider data distribution, row counts, or I/O costs. Oracle deprecated RBO in Oracle 10g.

Cost-Based Optimizer (CBO): Estimates the cost of alternative execution plans using statistics About the data (row counts, column distributions, index sizes) and system parameters (CPU speed, Disk I/O cost). PostgreSQL, MySQL, and modern Oracle use CBO exclusively.

flowchart TD
    A[SQL Query] --> B[Parser]
    B --> C[Query Tree / AST]
    C --> D[Query Rewriter]
    D --> E[Optimizer]
    E --> F1[Plan 1: Seq Scan + Nested Loop]
    E --> F2[Plan 2: Index Scan + Hash Join]
    E --> F3[Plan 3: Bitmap Scan + Merge Join]
    F1 --> G[Cost Estimator]
    F2 --> G
    F3 --> G
    G --> H[Select Lowest-Cost Plan]
    H --> I[Executor]

The PostgreSQL optimizer uses a dynamic programming approach: it explores join orderings and Access paths, estimating costs based on:

  • seq_page_cost: cost of a sequential disk page fetch (default 1.0)
  • random_page_cost: cost of a random disk page fetch (default 4.0)
  • cpu_tuple_cost: cost of processing each tuple (default 0.01)
  • cpu_index_tuple_cost: cost of processing each index entry (default 0.005)
  • cpu_operator_cost: cost of processing each operator (default 0.0025)

PostgreSQL collects per-column statistics during ANALYZE:

SELECT attname, null_frac, n_distinct, avg_width, correlation,
most_common_vals, most_common_freqs,
histogram_bounds
FROM pg_stats
WHERE tablename = "orders'
ORDER BY attname;
StatisticMeaning
null_fracFraction of rows with NULL in this column
n_distinctPositive: approximate distinct values. Negative: fraction of rows that are distinct
avg_widthAverage byte width of column values
correlationPhysical vs logical order correlation (-1.0 to 1.0)
most_common_valsMost frequent values (MCV list)
most_common_freqsFrequencies of MCV values
histogram_boundsBoundaries for histogram of non-MCV values

PostgreSQL stores an equi-depth histogram with default_statistics_target buckets (default 100). Each bucket contains approximately the same number of rows. The histogram is used to estimate Selectivity for conditions on non-MCV values.

-- Increase statistics target for a column with skewed distribution
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
ANALYZE orders;
-- Global default
SET default_statistics_target = 200;

The correlation statistic measures how closely the physical row order on disk matches the logical Order of the column value. A correlation of 1.0 means the data is perfectly sorted by this column on Disk. This matters for index scans:

-- High correlation (e.g., 0.99): index scan is efficient
-- Low correlation (e.g., 0.01): index scan requires many random I/Os
SELECT attname, correlation FROM pg_stats WHERE tablename = 'orders';

When multiple columns are used in a WHERE clause, independent column statistics can lead to poor Estimates. Extended statistics capture cross-column correlations:

-- Create extended statistics for column pairs
CREATE STATISTICS s_orders_region_date (ndistinct, dependencies, mcv)
ON region, order_date FROM orders;
-- Dependencies: functional dependency (region determines country)
CREATE STATISTICS s_orders_region_country (dependencies)
ON region, country FROM orders;
-- After creating extended statistics, run ANALYZE
ANALYZE orders;
-- Verify extended statistics are used
SELECT * FROM pg_stats_ext WHERE tablename = 'orders';
Statistic TypeCapturesUse Case
ndistinctDistinct count of column combinationsGROUP BY multiple columns
dependenciesFunctional dependenciesWHERE a = 1 AND b = 2 (b depends on a)
mcvMost common value combinationsMulti-column filter selectivity

For each row in the outer (driving) table, scan the inner table for matching rows.

Cost: O(N * M) where N = outer rows, M = inner rows per outer row
Best when: outer is small, inner has a useful index, or one side is very small
-- EXPLAIN shows:
-- -> Nested Loop (cost=0.43..12.50 rows=10)
-- -> Seq Scan on small_table (cost=0.00..1.50 rows=10)
-- -> Index Scan using idx_large_id on large_table (cost=0.43..1.00 rows=1)

Build an in-memory hash table from the inner (build) side, then probe with the outer side.

Cost: O(N + M) where N = outer rows, M = inner rows
Best when: both sides are large, no useful index, equijoin
Memory: requires work_mem for the hash table
-- EXPLAIN shows:
-- -> Hash Join (cost=450.00..850.00 rows=10000)
-- Hash Cond: (a.customer_id = b.customer_id)
-- -> Seq Scan on orders a (cost=0.00..300.00 rows=10000)
-- -> Hash (cost=200.00..200.00 rows=5000)
-- -> Seq Scan on customers b (cost=0.00..200.00 rows=5000)

If the hash table exceeds work_memPostgreSQL spills to disk, creating multiple batches. This Degrades performance significantly. Monitor with:

-- Check if hash joins spilled to disk
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id;
-- Look for "Batches" > 1 in Hash Join node output

Both inputs must be sorted on the join key. Walk through both sorted streams simultaneously.

Cost: O(N log N + M log M) for sorting, O(N + M) for merge
Best when: both sides already sorted (index order), or when a presorted merge is cheaper than hashing
-- EXPLAIN shows:
-- -> Merge Join (cost=1000.00..2000.00 rows=20000)
-- Merge Cond: (a.id = b.id)
-- -> Index Scan using idx_a_id on table_a (cost=0.42..800.00 rows=20000)
-- -> Sort (cost=500.00..510.00 rows=10000)
-- -> Seq Scan on table_b (cost=0.00..200.00 rows=10000)
ConditionPreferred Strategy
One table is very small (< 1000 rows)Nested Loop
Inner table has a selective index on join keyNested Loop
Both tables large, equijoin, sufficient work_memHash Join
Both sides sorted on join keyMerge Join
Non-equijoin (e.g., range condition)Nested Loop
Inner table large, no index, insufficient work_memMerge Join (after sort)
-- Correlated subquery: executed once per outer row (slow)
SELECT * FROM orders o
WHERE EXISTS (
SELECT 1 FROM customers c
WHERE c.customer_id = o.customer_id AND c.tier = 'premium'
);
-- Uncorrelated subquery: executed once (fast)
SELECT * FROM orders o
WHERE o.customer_id IN (
SELECT customer_id FROM customers WHERE tier = 'premium'
);

PostgreSQL may rewrite correlated subqueries as joins (subquery flattening or “pull-up”), but this Depends on the specific query shape. Use EXPLAIN to verify.

A semi-join returns rows from the outer table where a match exists in the inner table, but does not Duplicate outer rows. EXISTS and IN are converted to semi-joins:

-- Both are converted to Hash Semi Join by the optimizer
SELECT * FROM orders WHERE customer_id IN (SELECT id FROM premium_customers);
SELECT * FROM orders WHERE EXISTS (SELECT 1 FROM premium_customers WHERE id = customer_id);

CTEs in PostgreSQL 12+ may be inlined or materialized. When materialized, the subquery is executed Once and stored:

-- The CTE may be materialized if referenced multiple times
WITH active_users AS (
SELECT user_id, COUNT(*) AS login_count
FROM login_events
WHERE last_login >= CURRENT_DATE - INTERVAL '30 days'
GROUP BY user_id
)
SELECT
(SELECT COUNT(*) FROM active_users) AS total_active,
(SELECT COUNT(*) FROM active_users WHERE login_count > 10) AS power_users,
(SELECT AVG(login_count) FROM active_users) AS avg_logins;

PostgreSQL 9.6+ supports parallel execution for sequential scans, joins, and aggregates.

-- Maximum number of parallel workers per query
SET max_parallel_workers_per_gather = 4;
-- Maximum number of parallel workers across all queries
SET max_parallel_workers = 8;
-- Minimum table size (in 8KB pages) to consider parallel scan
SET min_parallel_table_scan_size = '8MB';
-- Minimum index size to consider parallel index scan
SET min_parallel_index_scan_size = '512kB';
EXPLAIN (ANALYZE)
SELECT COUNT(*) FROM large_table;
-- -> Gather (cost=0.00..12345.67 rows=1 width=8)
-- Workers Planned: 4
-- Workers Launched: 4
-- -> Parallel Seq Scan on large_table (cost=0.00..10000.00 rows=2500000)
-- Hash Join can be parallelized (each worker builds a partial hash table)
-- Nested Loop Join can be parallelized (each worker handles a subset of outer rows)
-- Merge Join can be parallelized in PostgreSQL 13+ (requires sorted inputs)
EXPLAIN (ANALYZE)
SELECT * FROM large_a JOIN large_b ON a.id = b.id;

When Parallel Query Helps (and When It Does Not)

Section titled “When Parallel Query Helps (and When It Does Not)”
ScenarioParallel Helps?Reason
Full table scan on large tableYesWork distributed across workers
Aggregates on large tablesYesPartial aggregates combined at coordinator
Index scan with few rowsNoCoordination overhead exceeds scan cost
Foreign data wrapper queriesNoFDW does not support parallel execution
Queries returning few rowsNoGather overhead exceeds benefit

Index-only scans still access the heap if any column in the index has NULL values, because PostgreSQL’s visibility information is stored in the heap. To maximize index-only scan efficiency, Keep indexed columns NOT NULL where possible, or run VACUUM regularly to keep visibility map Accurate.

A partial index only indexes rows that match a WHERE clause:

-- Index only unshipped orders (smaller, faster)
CREATE INDEX idx_orders_pending
ON orders (customer_id, created_at)
WHERE status = 'pending';
-- Index only active users
CREATE INDEX idx_users_active_email
ON users (email)
WHERE is_active = TRUE;
-- Index for common filter combination
CREATE INDEX idx_orders_high_value
ON orders (customer_id)
WHERE total > 10000;

Partial indexes are dramatically smaller than full indexes when the condition filters out most rows. The planner automatically considers partial indexes when the query contains a compatible WHERE Clause.

-- This query will use the partial index:
SELECT * FROM orders
WHERE status = 'pending' AND customer_id = 42
ORDER BY created_at;
-- This query will NOT use the partial index (status filter missing):
SELECT * FROM orders
WHERE customer_id = 42
ORDER BY created_at;

Index the result of an expression:

-- Case-insensitive email lookup
CREATE INDEX idx_users_lower_email ON users (LOWER(email));
SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';
-- JSONB field extraction
CREATE INDEX idx_events_type ON events ((payload ->> 'event_type'));
SELECT * FROM events WHERE payload ->> 'event_type' = 'purchase';
-- Common computation
CREATE INDEX idx_orders_monthly ON orders (DATE_TRUNC('month', order_date));
SELECT * FROM orders WHERE DATE_TRUNC('month', order_date) = '2024-01-01';

With PgBouncer in transaction mode, server-side prepared statements do not persist across Transactions. Use the prepared_statements option or driver-side prepared statement emulation.

-- View current autovacuum settings
SELECT name, setting, unit FROM pg_settings WHERE name LIKE 'autovacuum%';
-- Per-table autovacuum tuning
ALTER TABLE orders SET (
autovacuum_vacuum_scale_factor = 0.05, -- vacuum after 5% of rows change (default 20%)
autovacuum_analyze_scale_factor = 0.02, -- analyze after 2% of rows change (default 10%)
autovacuum_vacuum_cost_delay = 10, -- sleep 10ms between cost batches (default 2ms)
autovacuum_vacuum_cost_limit = 500 -- cost limit per vacuum run (default 200)
);
-- For append-only tables (no updates/deletes):
ALTER TABLE measurements SET (
autovacuum_vacuum_scale_factor = 0.0, -- disable vacuum-based trigger
autovacuum_analyze_scale_factor = 0.01 -- analyze after 1% of rows inserted
);
-- For high-write tables:
ALTER TABLE events SET (
autovacuum_vacuum_scale_factor = 0.01,
autovacuum_analyze_scale_factor = 0.005,
autovacuum_vacuum_cost_delay = 5,
autovacuum_max_workers = 3
);
-- Tables most needing vacuum (by dead tuple count)
SELECT relname, n_live_tup, n_dead_tup,
ROUND(n_dead_tup::NUMERIC / NULLIF(n_live_tup, 0) * 100, 2) AS dead_pct,
last_autovacuum, last_autoanalyze
FROM pg_stat_user_tables
ORDER BY n_dead_tup DESC
LIMIT 20;
-- Currently running autovacuum workers
SELECT pid, relname, phase,
EXTRACT(EPOCH FROM (now() - query_start)) AS elapsed_seconds
FROM pg_stat_progress_vacuum v
JOIN pg_stat_activity a ON a.pid = v.pid;
-- Enable (add to shared_preload_libraries and restart)
-- shared_preload_libraries = 'pg_stat_statements'
-- pg_stat_statements.track = all
-- Top 10 queries by total execution time
SELECT query, calls, total_exec_time / 1000 AS total_ms,
mean_exec_time / 1000 AS avg_ms,
rows, shared_blks_hit, shared_blks_read
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 10;
-- Top 10 queries by average execution time
SELECT query, calls, mean_exec_time / 1000 AS avg_ms
FROM pg_stat_statements
ORDER BY mean_exec_time DESC
LIMIT 10;
-- Top 10 queries by rows (potential N+1)
SELECT query, calls, rows,
rows::FLOAT / NULLIF(calls, 0) AS avg_rows
FROM pg_stat_statements
ORDER BY rows DESC
LIMIT 10;
-- Reset statistics
SELECT pg_stat_statements_reset();
-- Anti-pattern: N+1 queries (one query per order to get customer)
SELECT * FROM orders; -- 1 query
-- For each order: SELECT * FROM customers WHERE id = ? -- N queries
-- Fix: single JOIN query
SELECT o.*, c.name, c.email
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id;

Detect N+1 in pg_stat_statements:

-- Queries with high calls but low avg rows (likely N+1)
SELECT query, calls, rows, rows::FLOAT / calls AS avg_rows
FROM pg_stat_statements
WHERE calls > 100 AND rows::FLOAT / calls &lt; 5
ORDER BY calls DESC;

SELECT * retrieves all columns, which prevents index-only scans and wastes I/O bandwidth and Memory. Always specify the columns you need.

-- Anti-pattern: joining tables you don't need
SELECT o.order_id, o.total
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id -- not used
JOIN products p ON o.product_id = p.product_id -- not used
WHERE o.status = 'pending';
-- Fix: only join what you need
SELECT o.order_id, o.total
FROM orders o
WHERE o.status = 'pending';
-- Anti-pattern: OFFSET 1000000 is slow
SELECT * FROM orders ORDER BY created_at DESC LIMIT 20 OFFSET 1000000;
-- Fix: keyset (cursor) pagination
SELECT * FROM orders
WHERE created_at &lt; '2024-01-15T10:30:00Z' -- last value from previous page
ORDER BY created_at DESC
LIMIT 20;
-- Anti-pattern: function wrapping indexed column prevents index use
SELECT * FROM orders WHERE DATE(created_at) = '2024-01-15';
-- Fix: use range condition on the raw column
SELECT * FROM orders
WHERE created_at >= '2024-01-15' AND created_at &lt; '2024-01-16';
-- Or use an expression index
CREATE INDEX idx_orders_created_date ON orders ((DATE(created_at)));

After bulk loads, deletes, or updates, statistics may be severely out of date. The planner may Choose a seq scan when an index scan would be 100x faster. Always run ANALYZE after significant Data changes:

ANALYZE VERBOSE orders;
-- Or set autovacuum to trigger more aggressively
ALTER TABLE orders SET (autovacuum_analyze_scale_factor = 0.01);

The default work_mem is 4MB. A hash join on a table with 10 million rows likely requires much More. If the hash table spills to disk, performance degrades by 10-100x:

-- Per-session
SET work_mem = '256MB';
-- Per-role (for reporting users)
ALTER ROLE reporting_app SET work_mem = '256MB';
-- Check for spills in EXPLAIN ANALYZE output
EXPLAIN (ANALYZE, BUFFERS) SELECT ...;

CREATE INDEX acquires an ACCESS EXCLUSIVE lock, blocking all reads and writes. On a production Table, this means downtime:

-- WRONG: blocks all access
CREATE INDEX idx_orders_date ON orders(order_date);
-- RIGHT: allows reads and writes during creation
CREATE INDEX CONCURRENTLY idx_orders_date ON orders(order_date);

CREATE INDEX CONCURRENTLY takes longer but does not block concurrent operations. It is the only Safe way to create indexes on live production tables.

Without aggressive autovacuum, dead tuples accumulate, causing:

  • Table bloat (disk space waste)
  • Index bloat (slower index scans)
  • Longer query plans (planner estimates are based on live tuple count)
  • Potential transaction ID wraparound (data loss)

Every index slows down writes (INSERT, UPDATE, DELETE) by 10-30% per index. Indexes consume disk Space and memory. Create indexes based on actual query patterns, not hypothetical future needs. Remove unused indexes:

-- Find unused indexes
SELECT schemaname, relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE idx_scan = 0
AND indexrelname NOT LIKE '%_pkey'
ORDER BY pg_relation_size(indexrelid) DESC;

Histogram and Multivariate Statistics Deep-Dive

Section titled “Histogram and Multivariate Statistics Deep-Dive”

PostgreSQL stores a most_common_vals list (MCV) for the most frequent values, and histogram_bounds for the rest of the value distribution. The selectivity estimator uses these to Estimate how many rows a WHERE clause will match.

-- Examine MCV and histogram for a column
SELECT attname, n_distinct,
array_length(most_common_vals, 1) AS mcv_count,
array_length(histogram_bounds, 1) AS histogram_bucket_count
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'status';
-- Example output:
-- attname | n_distinct | mcv_count | histogram_bucket_count
-- status | 8 | 5 | 20
-- This means: 5 most common values captured, remaining distribution in 20 buckets

When a query filters on a value that is NOT in the MCV list, the planner uses the histogram to Estimate selectivity. If the histogram has too few buckets (low statistics_target), the estimate Can be wildly wrong.

-- Increase statistics for skewed distributions
ALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 500;
ANALYZE orders;
-- Check the impact on estimates
EXPLAIN (ANALYZE) SELECT * FROM orders WHERE customer_id = 12345;
-- Compare "rows" (estimated) vs actual rows returned

The correlation statistic measures how closely the physical order of rows on disk matches the Logical order of column values. A correlation of 1.0 means data is perfectly sorted.

-- Check correlation for frequently queried columns
SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'orders'
ORDER BY correlation;
-- Low correlation (e.g., &lt; 0.1): random I/O pattern for index scans
-- High correlation (e.g., > 0.9): sequential I/O pattern, much faster
-- Fix low correlation with CLUSTER (rewrites table in index order)
CLUSTER orders USING idx_orders_customer_date;
-- CLUSTER acquires ACCESS EXCLUSIVE lock. For production:
-- 1. CLUSTER on a replica
-- 2. Promote the replica
-- Or use pg_repack for online reorganization

CLUSTER rewrites the entire table in the order of the specified index. It improves index scan Performance for that index but degrades it for other indexes. Use CLUSTER on the index that Corresponds to the most common access pattern.

-- GIN trigram index: stores all trigrams, good for substring search
CREATE INDEX idx_docs_body_gin ON documents USING GIN (body gin_trgm_ops);
-- Fast for: LIKE '%pattern%', similarity search
-- Index size: large (stores every trigram)
-- Write cost: high (many index entries updated per row change)
-- GiST trigram index: stores trigram signatures, compact
CREATE INDEX idx_docs_body_gist ON documents USING GiST (body gist_trgm_ops);
-- Fast for: exact LIKE, equality, proximity
-- Index size: small (signature-based)
-- Write cost: low (compact index entries)
-- Less selective for short patterns
FeatureGIN trigramGiST trigram
Substring LIKEFastModerate
SimilarityFastFast
Index sizeLarge (3-5x data)Small (0.1x data)
Write speedSlowFast
Read speedFast (exact match)Moderate
Best forRead-heavyWrite-heavy

PostgreSQL prunes partitions at plan time using the query’s WHERE clause against the partition Bounds:

-- Partition pruning in action
EXPLAIN (ANALYZE)
SELECT * FROM orders
WHERE created_at >= '2024-01-01' AND created_at &lt; '2024-04-01';
-- Output should show:
-- -> Seq Scan on orders_2024_q1
-- Only orders_2024_q1 is scanned; other partitions are pruned
-- Pruning does NOT work with:
-- 1. Non-immutable functions: WHERE created_at >= NOW() (NOW() is stable, not immutable)
-- 2. Parameters from prepared statements (in some cases)
-- 3. Expressions the planner cannot evaluate at plan time

PostgreSQL 11+ supports partition-wise joins, where the optimizer joins matching partitions directly Instead of joining entire partitioned tables:

-- Enable partition-wise joins
SET enable_partitionwise_join = on;
SET enable_partitionwise_aggregate = on;
-- Verify partition-wise join in EXPLAIN output
EXPLAIN (ANALYZE)
SELECT o.*, c.name
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.created_at >= '2024-01-01';
-- Look for: "Append" node containing "Join" nodes per partition pair