AI-Driven Database Query Optimization

From Cost Models to Neural Optimizers — A Practical Engineering Guide

Introduction

1. What This Book Covers
2. Who This Book Is For
3. How to Use This Book
4. Why PostgreSQL?
5. Acknowledgments and Limitations

Chapter 1: The Problem of Query Optimization

1. The Cost of Bad Query Plans
2. Why Query Optimization Is NP-Hard
3. The Gap Between Theoretical Optimality and Practical Constraints
4. A Motivating Example: Cardinality Estimation Failure in Multi-Join Queries
5. Overview of the Optimizer Pipeline and Where AI Can Intervene
6. Scope and Roadmap of This Book
7. References

Chapter 2: Anatomy of a Traditional Query Optimizer

1. SQL Parsing and the Parse Tree
2. From Parse Tree to Logical Query Representation
3. The Query Optimization Pipeline in PostgreSQL
4. EXPLAIN and EXPLAIN ANALYZE — Reading Plan Output
5. Cost Model Components: CPU, I/O, Memory
6. Planner Configuration Parameters and Their Effects
7. Comparing PostgreSQL with Other Systems
8. References

Chapter 3: Relational Algebra and Query Plans

1. Basic Relational Operators
2. Logical vs Physical Plans
3. Algebraic Equivalences and Transformation Rules
4. Left-Deep vs Bushy Join Trees
5. PostgreSQL’s Join Tree Representation
6. Building Alternative Plans Through Transformations
7. Code Example: Parsing EXPLAIN JSON and Extracting Plan Structure
8. References

Chapter 4: Statistics and Cardinality Estimation

1. Table Statistics: Column Histograms, Most-Common-Values
2. Correlation Handling and Dependency Statistics
3. Join Selectivity Estimation
4. PostgreSQL Statistics Collection: ANALYZE, Histogram Buckets
5. Failure Modes: Skew, Outliers, Correlated Columns
6. Impact of Estimation Errors on Plan Choice
7. References

Chapter 5: Join Ordering and Search Strategies

1. The NP-Hard Join Ordering Problem
2. Dynamic Programming for Left-Deep Trees
3. Greedy Search and Branch-and-Bound
4. PostgreSQL’s GEQO Genetic Algorithm
5. Query Decomposition and Join Graph Analysis
6. Trade-offs: Optimality vs Planning Time
7. References

Chapter 6: Indexing and Physical Design

1. B-Tree Indexes: Structure, Cost, and Usage
2. Hash Indexes and Bitmap Indexes
3. Partial Indexes and Covering Indexes
4. PostgreSQL: GiST, GIN, BRIN, SP-GiST
5. Index Selection as Part of Query Optimization
6. Multi-Dimensional Indexes and Composite Keys
7. References

Chapter 7: Cost Models and Plan Selection

1. The Total Cost Formula: CPU, I/O, Memory
2. Cost Parameters in PostgreSQL
3. Selectivity-Based Cost Computation
4. Pipeline vs Materialization Costs
5. Memory Grant Estimation
6. Plan Selection: Choosing the Minimum-Cost Plan
7. References

Chapter 8: Query Execution Engines

1. Volcano Iterator Model
2. Vectorized Execution
3. Hash-Based Execution
4. Nested Loop, Sort-Merge, Index Scan Strategies
5. PostgreSQL’s Executor Internals
6. The Plan Execution Feedback Loop
7. References

Chapter 9: Caching, Reuse, and Parameterized Plans

1. Prepared Statements and Plan Caching
2. PostgreSQL: Prepared Statements and Plan Inference
3. Parameter Sniffing and Plan Stability Issues
4. Adaptive Plans and Parameter-Sensitive Plans
5. Plan Reuse Trade-offs: Overhead vs Consistency
6. Query Fingerprinting and Workload Analysis
7. References

Chapter 10: Machine Learning Foundations for Database Optimization

1. Supervised Learning: Regression and Classification for Cost Estimation
2. Feature Engineering for Database Queries
3. Model Families: Linear Models, Random Forests, Gradient Boosting
4. Deep Learning Fundamentals Relevant to Query Optimization
5. Graph Representations for Query Plans
6. Evaluation Metrics: Prediction Accuracy vs Optimization Quality
7. References

Chapter 11: Learned Cardinality Estimation

1. Failure Modes of Traditional Histogram-Based Estimation
2. Designing Features for Query Representation
3. Random Forest Cardinality Estimators
4. Deep Learning Approaches: RNNs, Transformers for Query Encoding
5. Learned Histograms and Sampling-Based Methods
6. Building a Learned Cardinality Estimator in Python
7. Integration with PostgreSQL Optimizer
8. References

Chapter 12: Learned Cost Models

1. The Structure of Cost Models and Their Assumptions
2. Learning Cost from Execution Traces
3. Feature Engineering for Plan Cost Prediction
4. Regression Models for Operator Cost Prediction
5. Handling Distributional Shifts Across Hardware
6. End-to-End Cost Model Training Pipeline
7. Accuracy Requirements: What Margin of Error Matters
8. References

Chapter 13: Learned Indexes

1. The Learned Index Paper and Core Ideas
2. Piecewise Linear Regression Models for Index Functions
3. Adaptive Radix Trees and Learned Variants
4. Learned Index Performance: Query Latency, Memory, Insertions
5. Practical Implementations: Lucene, SQLite Extensions
6. When Learned Indexes Help and When They Do Not
7. References

Chapter 14: Neural Query Optimizers and Plan Selection

1. Representing Queries and Plans as Graphs
2. Graph Neural Networks for Plan Scoring
3. Reinforcement Learning for Plan Search
4. End-to-End Optimizers That Bypass Traditional Search
5. Hybrid Approaches: ML-Guided Search Within Traditional Optimizers
6. Training Data Generation and Reward Design
7. References

Chapter 15: Workload-Aware Optimization

1. Workload Classification and Clustering
2. Temporal Patterns and Query Mixing
3. Learning Workload-Specific Cost Parameters
4. Adaptive Tuning Based on Workload Shifts
5. PostgreSQL: Autovacuum and Workload Statistics
6. Multi-Tenant and OLTP vs OLAP Workload Challenges
7. References

Chapter 16: Automatic Index and Materialized View Selection

1. The Index Recommendation Problem
2. Greedy and Genetic Algorithm Approaches
3. ML-Based Index Selection
4. Materialized View Recommendation
5. PostgreSQL: pg_hint_plan and Index Usage Feedback
6. Cost-Benefit Trade-offs: Space vs Query Speed
7. References

Chapter 17: Adaptive Query Optimization

1. Progressive Feedback During Execution
2. PostgreSQL: Adaptive Hash Joins
3. Re-optimization and Query Reshaping
4. Online Learning for Cardinality Estimation
5. Plan Guidance and Forced Plans
6. Safety: Preventing Adaptive Failures from Cascading
7. References

Chapter 18: LLM-Based Query Reasoning and Optimization

1. What LLMs Can and Cannot Do for Database Optimization
2. Representing SQL and Query Plans for LLMs
3. Prompting Strategies for Query Optimization Assistance
4. Fine-Tuning LLMs on Plan Data
5. Retrieval-Augmented Generation for Plan Recommendations
6. Tool-Using Agents and Optimizer as LLM Tool
7. Hallucination, Correctness, and Evaluation Risks
8. Practical Architectures Combining LLMs with Traditional Optimizers
9. References

Chapter 19: Building an AI-Assisted Optimizer: End-to-End System

1. System Architecture: Data Collection, Model Serving, Optimizer Integration
2. Designing the Training Data Pipeline from PostgreSQL
3. Model Selection for Each Optimization Stage
4. A/B Testing New Plans Against Baseline
5. Gradual Rollout and Safety Mechanisms
6. Complete Code Implementation Walkthrough
7. References

Chapter 20: Evaluation, Benchmarking, and Correctness

1. Benchmarks: TPC-H, TPC-DS, JOB, Custom Workloads
2. Metrics: Execution Time, Latency Percentiles, Throughput
3. Planning Overhead and Inference Latency
4. Model Accuracy vs Optimization Quality: The Critical Distinction
5. Regression Detection and Robustness Testing
6. Generalization Across Schemas and Workloads
7. References

Chapter 21: Production Deployment and Operations

1. Model Serving Architecture: Latency, Throughput, Reliability
2. Continuous Training and Drift Detection
3. Observability: Logging, Metrics, Tracing
4. Rollback Strategies and Plan Safety
5. Handling Cold Starts and Data Scarcity
6. Privacy, Security, and Access Control
7. Team Skills and Organizational Considerations
8. References

Chapter 22: Frontiers and Open Problems

1. Open Research Problems in AI-Driven Optimization
2. Scaling to Large Schemas and Complex Queries
3. Cross-Database and Cloud-Native Optimization
4. Federated and Distributed Query Optimization with ML
5. The Path from Research to Production: Lessons Learned
6. Future Directions and a Realistic Assessment
7. References

Conclusion

References