Advanced SQL: Internals and Optimization

Advanced SQL: Internals and Optimization

SQL optimization extends far beyond query rewriting. Understanding the architectural decisions within database engines—particularly PostgreSQL—reveals why certain queries perform well while others fail catastrophically. This deep dive explores the internals that separate competent SQL practitioners from true optimization experts.

Query Execution: From Parse Tree to Physical Plan

When you submit a SQL query, PostgreSQL transforms it through several stages. The parser creates an abstract syntax tree (AST), the planner generates candidate execution plans, and the optimizer selects the lowest-cost plan. This process is deterministic but not always optimal—the optimizer makes decisions based on statistics, not actual data distribution.

The planner uses table statistics (maintained by ANALYZE) to estimate row counts at each step. These estimates cascade through the plan tree, influencing join order, join method selection, and aggregation strategy. A single bad estimate early in the plan can corrupt all downstream decisions.

-- Examine the planner's reasoning
EXPLAIN (ANALYZE, BUFFERS, VERBOSE) 
SELECT o.order_id, c.customer_name, SUM(oi.quantity)
FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
JOIN order_items oi ON o.order_id = oi.order_id
WHERE o.order_date > '2024-01-01'
GROUP BY o.order_id, c.customer_name;

The ANALYZE keyword shows actual execution statistics. Compare "Rows" (estimated) with "Actual Rows" (observed). Significant divergence indicates stale statistics or data skew. The BUFFERS option reveals I/O patterns—whether the query hit the buffer pool or required disk access.

Join Strategies and Their Trade-offs

PostgreSQL supports three primary join algorithms, each optimal under different conditions:

Nested Loop Join: The simplest strategy—for each row in the outer table, scan the inner table. Cost is O(N*M). This dominates when the inner table is small or indexed, because it avoids materializing large intermediate results. However, it's catastrophic for large unsorted scans.

-- Nested loop is efficient here (small inner result)
EXPLAIN SELECT * FROM large_table lt
JOIN small_lookup sl ON lt.lookup_id = sl.id
WHERE sl.status = 'active';

Hash Join: Build a hash table from the inner relation, then probe with outer rows. Cost is O(N+M), making it superior for large relations. The hash table must fit in work_mem; if it doesn't, PostgreSQL spills to disk, degrading performance dramatically. This is where the architectural trade-off emerges: hash joins are fast but memory-hungry.

-- Hash join preferred for large equijoins
EXPLAIN SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.customer_id;

Sort-Merge Join: Sort both relations, then merge them. Cost is O(N log N + M log M). This excels when data is already sorted or when you need sorted output anyway (avoiding a final sort). It's also the only join type that can handle non-equijoins efficiently.

The optimizer chooses based on estimated costs, but these estimates assume uniform data distribution. In reality, data skew—where certain values appear far more frequently than statistics suggest—can make the chosen strategy suboptimal. Consider a customer_id that appears in 50% of orders; the optimizer might choose a hash join assuming even distribution, but that customer's rows will dominate the hash table, causing poor cache locality.

Index Selection and the Cost Model

Indexes are not universally beneficial. An index has overhead: storage, maintenance on writes, and CPU cost during planning. The optimizer must decide: is an index scan cheaper than a sequential scan?

-- Force sequential scan to compare costs
EXPLAIN SELECT * FROM orders 
WHERE customer_id = 42 AND order_date > '2024-01-01';

EXPLAIN (ANALYZE) SELECT * FROM orders 
WHERE customer_id = 42 AND order_date > '2024-01-01';

The planner estimates that a sequential scan reads every page, while an index scan reads index pages plus heap pages. If the query returns many rows, sequential scan wins despite the index existing. This is why high-selectivity predicates favor indexes while low-selectivity ones don't.

Composite indexes introduce subtle trade-offs. A B-tree index on (customer_id, order_date) can support both "customer_id = 42" and "customer_id = 42 AND order_date > date" efficiently. However, it cannot efficiently support "order_date > date" alone—the index must be scanned from the beginning. This is the "index leading column" constraint.

Partial indexes—indexes on a subset of rows—reduce maintenance cost while improving selectivity for filtered queries:

-- Only index active orders, reducing index size
CREATE INDEX idx_active_orders ON orders(customer_id) 
WHERE status = 'active';

Statistics, Cardinality Estimation, and Plan Instability

PostgreSQL maintains statistics in pg_stats. The default sample size (analyzed rows) is 300, which can be insufficient for large tables with skewed distributions. When you ANALYZE a table, PostgreSQL samples rows and builds histograms of value distributions.

-- Check statistics for a table
SELECT attname, n_distinct, correlation 
FROM pg_stats 
WHERE tablename = 'orders';

The n_distinct value is critical. If it's negative, it's a ratio (e.g., -0.5 means 50% of rows are distinct). If positive, it's an absolute count. A negative value suggests the planner will estimate more rows per value than actually exist, leading to overestimation of join output.

Correlation measures whether physical row order matches logical order. High correlation (near 1.0) means sequential scans are cache-efficient. Low correlation means random I/O dominates, favoring index scans despite higher logical cost.

Plan instability occurs when small changes in data cause the optimizer to choose different plans. A query that uses a hash join today might switch to a nested loop tomorrow after data changes. This is dangerous in production because the new plan might be orders of magnitude slower. The solution is explicit plan hints (via planner parameters) or materialized views that force specific execution strategies.

Buffer Pool and I/O Architecture

PostgreSQL's buffer pool (shared_buffers) is the first line of defense against disk I/O. Queries that fit entirely in the buffer pool run at memory speed; those that don't incur disk latency (milliseconds vs. nanoseconds).

The buffer replacement policy is LRU (Least Recently Used), but with a twist: PostgreSQL uses a "clock sweep" algorithm to avoid the overhead of maintaining a true LRU list. This means recently accessed pages are kept, but the policy is approximate. For sequential scans of large tables, PostgreSQL uses a "ring buffer" to avoid evicting useful pages—the scan allocates a small buffer and reuses it, preventing the entire table from polluting the cache.

Understanding I/O patterns is crucial. A query that reads 1GB sequentially might complete faster than one reading 100MB randomly, because sequential I/O allows the disk to prefetch and amortize seek time.

-- Check buffer hit ratio
SELECT 
  sum(heap_blks_read) as heap_read,
  sum(heap_blks_hit) as heap_hit,
  sum(heap_blks_hit) / (sum(heap_blks_hit) + sum(heap_blks_read)) as ratio
FROM pg_statio_user_tables;

A ratio below 99% suggests memory pressure. Increasing shared_buffers helps, but there's a trade-off: larger buffers mean more CPU time managing them, and the OS page cache becomes less effective.

Aggregation and Grouping Internals

GROUP BY operations use one of two strategies: hash aggregation or sort aggregation. Hash aggregation builds a hash table of groups, streaming results as groups complete. Sort aggregation sorts the input by group keys, then processes groups sequentially.

Hash aggregation is faster when groups are numerous and fit in work_mem. Sort aggregation is better when the input is already sorted (or can be sorted cheaply via an index) or when work_mem is constrained. If the hash table exceeds work_mem, PostgreSQL spills to disk, degrading performance catastrophically.

-- Force sort aggregation
SET enable_hashagg = off;
EXPLAIN SELECT customer_id, COUNT(*) 
FROM orders 
GROUP BY customer_id;

The number of groups matters enormously. If you GROUP BY a high-cardinality column (e.g., order_id), the hash table becomes huge. If you GROUP BY a low-cardinality column (e.g., status), the hash table is tiny and aggregation is fast.

Window Functions and Frame Buffers

Window functions (ROW_NUMBER, LAG, LEAD, etc.) require buffering rows to compute frames. A frame like "ROWS BETWEEN 100 PRECEDING AND 100 FOLLOWING" requires 200 rows in memory simultaneously. For large frames or large result sets, this becomes a memory bottleneck.

-- This buffers 1000 rows per partition
SELECT order_id, customer_id,
  AVG(amount) OVER (
    PARTITION BY customer_id 
    ROWS BETWEEN 500 PRECEDING AND 500 FOLLOWING
  ) as moving_avg
FROM orders;

Window functions cannot use hash aggregation; they require sort aggregation with frame buffering. This is why window functions on unsorted data are expensive—PostgreSQL must sort first, then buffer frames.

Transaction Isolation and MVCC Overhead

PostgreSQL uses MVCC (Multi-Version Concurrency Control) to provide isolation without locking. Every row has xmin (transaction that inserted it) and xmax (transaction that deleted it). Visibility checks determine whether a row is visible to the current transaction.

This has performance implications. Visibility checks add CPU overhead to every row access. Dead rows (deleted but not yet vacuumed) must still be checked and filtered. A table with high churn (many deletes) accumulates dead rows, bloating the table and slowing scans.

VACUUM reclaims dead row space and updates visibility information. Aggressive vacuuming prevents bloat but consumes I/O. This is an architectural trade-off: MVCC provides concurrency but requires maintenance overhead.

Partitioning and Constraint Exclusion

Table partitioning divides large tables into smaller pieces, enabling partition pruning—the optimizer eliminates partitions that cannot contain matching rows. This is powerful for time-series data:

-- Partition by month
CREATE TABLE orders (
  order_id BIGINT,
  customer_id INT,
  order_date DATE,
  amount DECIMAL
) PARTITION BY RANGE (order_date);

CREATE TABLE orders_2024_01 PARTITION OF orders
  FOR VALUES FROM ('2024-01-01') TO ('2024-02-01');

-- Query only touches 2024_01 partition
SELECT * FROM orders WHERE order_date = '2024-01-15';

Constraint exclusion works similarly for inherited tables. The optimizer checks CHECK constraints and eliminates tables that cannot match the WHERE clause. This is less efficient than native partitioning but works with older PostgreSQL versions.

Partitioning introduces trade-offs: smaller tables scan faster, but queries spanning multiple partitions must union results. Partition elimination is only effective with simple predicates; complex expressions may prevent pruning.

Practical Optimization Workflow

Effective optimization follows a systematic approach:

1. Establish baselines: Measure query time, I/O, and memory before optimization. Use EXPLAIN ANALYZE to understand the current plan.

2. Identify bottlenecks: Is the query CPU-bound (high execution time) or I/O-bound (high buffer misses)? Is it a single slow operation or many slow operations?

3. Test hypotheses: Adjust statistics (ANALYZE with higher sample size), add indexes, rewrite queries, or adjust planner parameters. Always measure the impact.

4. Monitor for regressions: Plans change as data evolves. A query optimized today might degrade tomorrow. Use auto_explain to log slow queries and detect plan changes.

-- Log queries slower than 1 second
SET log_min_duration_statement = 1000;
SET log_statement = 'all';
SET log_duration = on;

5. Consider trade-offs: Faster queries might require more memory, larger indexes, or more frequent maintenance. Optimize for your actual constraints, not theoretical ideals.