Query Optimization

Cost-Based Optimization

Modern relational DBs use cost-based optimizers (CBO): generate plan candidates -> estimate cost via statistics (row counts, distributions, selectivity) -> select lowest I/O/CPU/memory plan. Stale statistics lead to suboptimal plans.

Execution Plan Analysis

Validate optimization with EXPLAIN before and after changes.

sql
-- PostgreSQL (add ANALYZE for actual runtime stats)
EXPLAIN ANALYZE SELECT order_id, total FROM orders WHERE customer_id = 12345;
-- MySQL: EXPLAIN FORMAT=JSON ... | SQL Server: SET STATISTICS IO ON

Key indicators: Seq Scan/Table Scan = missing index | Index Scan/Seek = efficient | Hash Join = large equality joins | Nested Loop = small/indexed inner | Merge Join = pre-sorted inputs | Sort = watch disk spills

Indexing Strategies

B-Tree (Default)

Supports: equality, range, sorting, prefix matching | O(log n) lookup | General-purpose, all major DBs default

Hash

Equality only | O(1) lookup | High-cardinality exact-match | No range/sorting/pattern support

Covering Indexes

Include all query columns in index -> eliminates table access (index-only scan) | Trade-off: larger index, slower writes

sql
-- Covering index for: SELECT name, email FROM users WHERE status = 'active'
CREATE INDEX idx_users_status_covering ON users(status) INCLUDE (name, email);

PostgreSQL Specialized

• GiST: Geometric data, full-text search, nearest-neighbor
• GIN: Arrays, full-text search, JSONB queries
• BRIN: Large tables with physically correlated data (timestamps), minimal storage
• SP-GiST: Non-balanced structures, point-based geometric queries

Compound Index Design

Order by: 1. Equality conditions first (highest selectivity) | 2. Sort columns second | 3. Range conditions last

MongoDB ESR Rule

Equality-Sort-Range ordering for compound indexes:

javascript
// Query: status = "A", qty > 20, sorted by item
// Optimal index:
db.collection.createIndex({ status: 1, item: 1, qty: 1 })
//                          E(quality)  S(ort)   R(ange)

SQL Optimization Patterns

Select Only Needed Columns

sql
-- Bad: SELECT * retrieves unnecessary data, prevents covering indexes
SELECT * FROM orders WHERE customer_id = 12345;

-- Good: Specify columns, enables covering index
SELECT order_id, order_date, total FROM orders WHERE customer_id = 12345;

Other Key Patterns

• CTEs: Improve readability but not always performance -- PostgreSQL may materialize CTEs (pre-v12), MySQL inlines them
• Window functions: Use SUM() OVER, RANK() OVER (PARTITION BY ...) for analytics without self-joins
• Pagination: Prefer keyset (WHERE id > last_seen ORDER BY id LIMIT N) over OFFSET for deep pages
• Parameterized queries: Prevent SQL injection AND enable plan caching (cursor.execute("... WHERE id = %s", (id,)))

JOIN Algorithm Selection

| Algorithm | Best When | Cost | |-----------|-----------|------| | Nested Loop | Small outer table, indexed inner table | O(n m) worst, O(n log m) with index | | Hash Join | Large tables, equality joins, no useful indexes | O(n + m) build + probe | | Merge Join | Both inputs already sorted (index order) | O(n + m) after sort |

Cardinality Estimation

Optimizer predicts row counts using: Histograms (value distribution) | Density vectors (non-histogram columns) | Statistics objects via ANALYZE (PostgreSQL) / UPDATE STATISTICS (SQL Server)

When estimation is wrong (correlated columns, skewed data, multi-table joins): 1. Run ANALYZE/UPDATE STATISTICS | 2. Create multi-column statistics | 3. Query hints as last resort

NoSQL Query Optimization

MongoDB

Place $match/$project early in pipelines | Use $lookup sparingly (left outer joins) | Compound indexes following ESR | Validate with explain("executionStats")

Cassandra

Always include partition key | Design tables around query patterns (query-first) | Use SAI over SASI (43% throughput gain) | Avoid ALLOW FILTERING (full cluster scan) | Materialized views add write overhead

DynamoDB

Use Query not Scan | Design partition keys for even distribution | GSIs for alternative access patterns | Single-table design with composite sort keys

Redis

FT.SEARCH for complex queries (RediSearch module) | Design key naming for efficient SCAN | Use pipelining for batch ops

Anti-Patterns to Detect

• SELECT : Wastes I/O, prevents covering indexes
• Missing indexes on WHERE/JOIN/ORDER BY columns: full table scans
• N+1 queries: Fetch in loops instead of JOINs/batch
• Implicit type conversions: Prevents index use (WHERE varchar_col = 123)
• Functions on indexed columns: WHERE UPPER(name) = 'JOHN' blocks index; use function-based indexes
• Missing pagination: Unbounded result sets
• Hot partitions (NoSQL): Low-cardinality partition keys concentrate load
• ALLOW FILTERING (Cassandra): Expensive full-cluster scans
• Large partitions (Cassandra): >100MB degrades performance