Query Optimization
Query Optimizer Architecture
Section titled “Query Optimizer Architecture”Rule-Based vs Cost-Based Optimization
Section titled “Rule-Based vs Cost-Based 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)
Statistics
Section titled “Statistics”Column Statistics
Section titled “Column Statistics”PostgreSQL collects per-column statistics during ANALYZE:
SELECT attname, null_frac, n_distinct, avg_width, correlation, most_common_vals, most_common_freqs, histogram_boundsFROM pg_statsWHERE tablename = "orders'ORDER BY attname;| Statistic | Meaning |
|---|---|
null_frac | Fraction of rows with NULL in this column |
n_distinct | Positive: approximate distinct values. Negative: fraction of rows that are distinct |
avg_width | Average byte width of column values |
correlation | Physical vs logical order correlation (-1.0 to 1.0) |
most_common_vals | Most frequent values (MCV list) |
most_common_freqs | Frequencies of MCV values |
histogram_bounds | Boundaries for histogram of non-MCV values |
Histograms
Section titled “Histograms”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 distributionALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;ANALYZE orders;
-- Global defaultSET default_statistics_target = 200;Correlation
Section titled “Correlation”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/OsSELECT attname, correlation FROM pg_stats WHERE tablename = 'orders';Extended Statistics (PostgreSQL 10+)
Section titled “Extended Statistics (PostgreSQL 10+)”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 pairsCREATE 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 ANALYZEANALYZE orders;
-- Verify extended statistics are usedSELECT * FROM pg_stats_ext WHERE tablename = 'orders';| Statistic Type | Captures | Use Case |
|---|---|---|
ndistinct | Distinct count of column combinations | GROUP BY multiple columns |
dependencies | Functional dependencies | WHERE a = 1 AND b = 2 (b depends on a) |
mcv | Most common value combinations | Multi-column filter selectivity |
Join Strategies
Section titled “Join Strategies”Nested Loop Join
Section titled “Nested Loop Join”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 rowBest 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)Hash Join
Section titled “Hash Join”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 rowsBest when: both sides are large, no useful index, equijoinMemory: 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 diskEXPLAIN (ANALYZE, BUFFERS)SELECT * FROM orders o JOIN customers c ON o.customer_id = c.customer_id;-- Look for "Batches" > 1 in Hash Join node outputMerge Join
Section titled “Merge Join”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 mergeBest 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)Join Strategy Selection Guide
Section titled “Join Strategy Selection Guide”| Condition | Preferred Strategy |
|---|---|
| One table is very small (< 1000 rows) | Nested Loop |
| Inner table has a selective index on join key | Nested Loop |
| Both tables large, equijoin, sufficient work_mem | Hash Join |
| Both sides sorted on join key | Merge Join |
| Non-equijoin (e.g., range condition) | Nested Loop |
| Inner table large, no index, insufficient work_mem | Merge Join (after sort) |
Subquery Optimization
Section titled “Subquery Optimization”Correlated vs Uncorrelated Subqueries
Section titled “Correlated vs Uncorrelated Subqueries”-- Correlated subquery: executed once per outer row (slow)SELECT * FROM orders oWHERE 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 oWHERE 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.
Semi-Join
Section titled “Semi-Join”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 optimizerSELECT * 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);Materialized Subqueries
Section titled “Materialized Subqueries”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 timesWITH 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;Parallel Query
Section titled “Parallel Query”PostgreSQL 9.6+ supports parallel execution for sequential scans, joins, and aggregates.
Configuration Parameters
Section titled “Configuration Parameters”-- Maximum number of parallel workers per querySET max_parallel_workers_per_gather = 4;
-- Maximum number of parallel workers across all queriesSET max_parallel_workers = 8;
-- Minimum table size (in 8KB pages) to consider parallel scanSET min_parallel_table_scan_size = '8MB';
-- Minimum index size to consider parallel index scanSET min_parallel_index_scan_size = '512kB';Parallel Seq Scan
Section titled “Parallel Seq Scan”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)Parallel Join
Section titled “Parallel Join”-- 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)”| Scenario | Parallel Helps? | Reason |
|---|---|---|
| Full table scan on large table | Yes | Work distributed across workers |
| Aggregates on large tables | Yes | Partial aggregates combined at coordinator |
| Index scan with few rows | No | Coordination overhead exceeds scan cost |
| Foreign data wrapper queries | No | FDW does not support parallel execution |
| Queries returning few rows | No | Gather 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.
Partial Indexes and Conditional Indexes
Section titled “Partial Indexes and Conditional Indexes”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 usersCREATE INDEX idx_users_active_email ON users (email) WHERE is_active = TRUE;
-- Index for common filter combinationCREATE 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 ordersWHERE status = 'pending' AND customer_id = 42ORDER BY created_at;
-- This query will NOT use the partial index (status filter missing):SELECT * FROM ordersWHERE customer_id = 42ORDER BY created_at;Expression Indexes
Section titled “Expression Indexes”Index the result of an expression:
-- Case-insensitive email lookupCREATE INDEX idx_users_lower_email ON users (LOWER(email));SELECT * FROM users WHERE LOWER(email) = 'alice@example.com';
-- JSONB field extractionCREATE INDEX idx_events_type ON events ((payload ->> 'event_type'));SELECT * FROM events WHERE payload ->> 'event_type' = 'purchase';
-- Common computationCREATE 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.
Auto-Vacuum Tuning
Section titled “Auto-Vacuum Tuning”-- View current autovacuum settingsSELECT name, setting, unit FROM pg_settings WHERE name LIKE 'autovacuum%';
-- Per-table autovacuum tuningALTER 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);Monitoring Autovacuum
Section titled “Monitoring Autovacuum”-- 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_autoanalyzeFROM pg_stat_user_tablesORDER BY n_dead_tup DESCLIMIT 20;
-- Currently running autovacuum workersSELECT pid, relname, phase, EXTRACT(EPOCH FROM (now() - query_start)) AS elapsed_secondsFROM pg_stat_progress_vacuum vJOIN pg_stat_activity a ON a.pid = v.pid;pg_stat_statements
Section titled “pg_stat_statements”-- 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 timeSELECT query, calls, total_exec_time / 1000 AS total_ms, mean_exec_time / 1000 AS avg_ms, rows, shared_blks_hit, shared_blks_readFROM pg_stat_statementsORDER BY total_exec_time DESCLIMIT 10;
-- Top 10 queries by average execution timeSELECT query, calls, mean_exec_time / 1000 AS avg_msFROM pg_stat_statementsORDER BY mean_exec_time DESCLIMIT 10;
-- Top 10 queries by rows (potential N+1)SELECT query, calls, rows, rows::FLOAT / NULLIF(calls, 0) AS avg_rowsFROM pg_stat_statementsORDER BY rows DESCLIMIT 10;
-- Reset statisticsSELECT pg_stat_statements_reset();Common Anti-Patterns
Section titled “Common Anti-Patterns”N+1 Queries
Section titled “N+1 Queries”-- 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 querySELECT o.*, c.name, c.emailFROM orders oJOIN 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_rowsFROM pg_stat_statementsWHERE calls > 100 AND rows::FLOAT / calls < 5ORDER BY calls DESC;SELECT *
Section titled “SELECT *”SELECT * retrieves all columns, which prevents index-only scans and wastes I/O bandwidth and Memory. Always specify the columns you need.
Unnecessary JOINs
Section titled “Unnecessary JOINs”-- Anti-pattern: joining tables you don't needSELECT o.order_id, o.totalFROM orders oJOIN customers c ON o.customer_id = c.customer_id -- not usedJOIN products p ON o.product_id = p.product_id -- not usedWHERE o.status = 'pending';
-- Fix: only join what you needSELECT o.order_id, o.totalFROM orders oWHERE o.status = 'pending';OFFSET Pagination on Large Datasets
Section titled “OFFSET Pagination on Large Datasets”-- Anti-pattern: OFFSET 1000000 is slowSELECT * FROM orders ORDER BY created_at DESC LIMIT 20 OFFSET 1000000;
-- Fix: keyset (cursor) paginationSELECT * FROM ordersWHERE created_at < '2024-01-15T10:30:00Z' -- last value from previous pageORDER BY created_at DESCLIMIT 20;Functions on Indexed Columns
Section titled “Functions on Indexed Columns”-- Anti-pattern: function wrapping indexed column prevents index useSELECT * FROM orders WHERE DATE(created_at) = '2024-01-15';
-- Fix: use range condition on the raw columnSELECT * FROM ordersWHERE created_at >= '2024-01-15' AND created_at < '2024-01-16';
-- Or use an expression indexCREATE INDEX idx_orders_created_date ON orders ((DATE(created_at)));Common Pitfalls
Section titled “Common Pitfalls”Stale Statistics
Section titled “Stale Statistics”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 aggressivelyALTER TABLE orders SET (autovacuum_analyze_scale_factor = 0.01);work_mem Too Low for Hash Joins
Section titled “work_mem Too Low for Hash Joins”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-sessionSET work_mem = '256MB';
-- Per-role (for reporting users)ALTER ROLE reporting_app SET work_mem = '256MB';
-- Check for spills in EXPLAIN ANALYZE outputEXPLAIN (ANALYZE, BUFFERS) SELECT ...;Not Using CONCURRENTLY for Index Creation
Section titled “Not Using CONCURRENTLY for Index Creation”CREATE INDEX acquires an ACCESS EXCLUSIVE lock, blocking all reads and writes. On a production Table, this means downtime:
-- WRONG: blocks all accessCREATE INDEX idx_orders_date ON orders(order_date);
-- RIGHT: allows reads and writes during creationCREATE 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.
Ignoring VACUUM on High-Write Tables
Section titled “Ignoring VACUUM on High-Write 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)
Over-Indexing
Section titled “Over-Indexing”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 indexesSELECT schemaname, relname, indexrelname, idx_scanFROM pg_stat_user_indexesWHERE 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”Understanding Histogram Boundaries
Section titled “Understanding Histogram Boundaries”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 columnSELECT attname, n_distinct, array_length(most_common_vals, 1) AS mcv_count, array_length(histogram_bounds, 1) AS histogram_bucket_countFROM pg_statsWHERE 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 bucketsWhen 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 distributionsALTER TABLE orders ALTER COLUMN customer_id SET STATISTICS 500;ANALYZE orders;
-- Check the impact on estimatesEXPLAIN (ANALYZE) SELECT * FROM orders WHERE customer_id = 12345;-- Compare "rows" (estimated) vs actual rows returnedCorrelation and Index Scan Efficiency
Section titled “Correlation and Index Scan Efficiency”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 columnsSELECT attname, correlationFROM pg_statsWHERE tablename = 'orders'ORDER BY correlation;
-- Low correlation (e.g., < 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 reorganizationCLUSTER 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.
GiST vs GIN for Full-Text Search
Section titled “GiST vs GIN for Full-Text Search”pg_trgm with GIN
Section titled “pg_trgm with GIN”-- GIN trigram index: stores all trigrams, good for substring searchCREATE 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)pg_trgm with GiST
Section titled “pg_trgm with GiST”-- GiST trigram index: stores trigram signatures, compactCREATE 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| Feature | GIN trigram | GiST trigram |
|---|---|---|
| Substring LIKE | Fast | Moderate |
| Similarity | Fast | Fast |
| Index size | Large (3-5x data) | Small (0.1x data) |
| Write speed | Slow | Fast |
| Read speed | Fast (exact match) | Moderate |
| Best for | Read-heavy | Write-heavy |
Partition Pruning Details
Section titled “Partition Pruning Details”Constraint-Based Pruning
Section titled “Constraint-Based Pruning”PostgreSQL prunes partitions at plan time using the query’s WHERE clause against the partition Bounds:
-- Partition pruning in actionEXPLAIN (ANALYZE)SELECT * FROM ordersWHERE created_at >= '2024-01-01' AND created_at < '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 timePartition-Wise Joins
Section titled “Partition-Wise Joins”PostgreSQL 11+ supports partition-wise joins, where the optimizer joins matching partitions directly Instead of joining entire partitioned tables:
-- Enable partition-wise joinsSET enable_partitionwise_join = on;SET enable_partitionwise_aggregate = on;
-- Verify partition-wise join in EXPLAIN outputEXPLAIN (ANALYZE)SELECT o.*, c.nameFROM orders oJOIN customers c ON o.customer_id = c.idWHERE o.created_at >= '2024-01-01';
-- Look for: "Append" node containing "Join" nodes per partition pair