The Evolution of the SQL Query Optimizer

• Introduction
• Chapter 1 The Declarative Promise: Pre-Relational Data Access and the Need for Optimization
• Chapter 2 System R and the Genesis of Cost-Based Optimization
• Chapter 3 The Architecture of the Selinger Optimizer
• Chapter 4 Relational Algebra as the Foundation of Query Transformation
• Chapter 5 Heuristics vs. Costs: Rule-Based Approaches and Early Commercial Engines
• Chapter 6 The Search Space Explosion: Join Enumeration and Dynamic Programming
• Chapter 7 Statistics and Selectivity Estimation: The Early Statistical Models
• Chapter 8 Beyond Uniformity: Equi-Depth, Equi-Width, and Multi-Dimensional Histograms
• Chapter 9 The Volcano Model: Extensibility and Dynamic Equivalence
• Chapter 10 The Cascades Framework: Object-Oriented, Rule-Driven Optimization
• Chapter 11 Subquery Flattening, Unnesting, and View Inlining
• Chapter 12 Outer Join Simplification and Reordering Strategies
• Chapter 13 Physical Plan Selection: Index Scans, Hash Joins, and Merge Joins
• Chapter 14 Parallel Query Optimization for Shared-Memory and Shared-Nothing Systems
• Chapter 15 Distributed Query Optimization and Data Shipping Paradigms
• Chapter 16 Modern Cardinality Estimation: Sketches, Wavelets, and HyperLogLog
• Chapter 17 Adaptive and Dynamic Query Optimization: Re-planning at Runtime
• Chapter 18 Parametric and Robust Query Optimization: Defending Against Estimation Errors
• Chapter 19 Vectorized and Code-Generating Engines: How Modern Hardware Impacts Cost Models
• Chapter 20 Optimizing Analytical Workloads: Star Schema, Columnar Storage, and OLAP
• Chapter 21 The SQL-on-Hadoop Era: Optimizing Queries in Massively Distributed Big Data Engines
• Chapter 22 Bridging Relational and NoSQL: Schemaless, Semi-Structured, and Document Optimization
• Chapter 23 Machine Learning for Query Optimization: Learned Cardinalities and Plan Selection
• Chapter 24 Autonomous and Self-Tuning Optimizers in the Cloud
• Chapter 25 The Future of Cost-Based Optimization: Open Challenges and Next Frontiers

Every time an engineer, data analyst, or distributed application issues a SQL query, a quiet miracle takes place beneath the surface of the database engine. In a fraction of a millisecond, the system translates a high-level, declarative statement of intent—a description of what data is desired rather than how to retrieve it—into an intricate, imperative program composed of physical algorithms, access paths, and data-shuffling directives. The difference between the best possible execution plan and a mediocre one is rarely a matter of a few percentage points; it is frequently a difference of several orders of magnitude, separating a query that returns in fifty milliseconds from one that grinds the cluster to a halt for twelve hours. Standing as the sole arbiter between declarative simplicity and physical performance is the query optimizer.

To appreciate the gravity of the query optimizer's role, one must recall the state of data processing before the advent of the relational model. In the era of hierarchical and network databases, programmers were manual navigators, forced to hand-craft procedural code that traversed pointer chains and physical disk records. When the underlying storage layout shifted, applications broke, demanding expensive and brittle rewrites. Edgar F. Codd’s radical 1970 proposal of the relational model promised data independence, unburdening software developers from the physical arrangement of bits on magnetic platters. Yet this declarative promise brought with it a profound computational challenge: if the programmer no longer specifies how to execute a query, the software engine itself must deduce the most efficient strategy. Early skeptics dismissed the relational vision as an academic fantasy, arguing that no automated compiler could ever match the hand-tuned efficiency of an experienced systems programmer.

The breakthrough that silenced those skeptics arrived in the late 1970s within the laboratories of IBM Research, encapsulated in the seminal work on System R and the foundational paper by Patricia Selinger and her colleagues. Selinger did not simply devise a set of clever heuristics; she introduced a coherent architectural blueprint: cost-based optimization. By synthesizing an algebraic search space, statistical profiles of stored data, and mathematical cost formulas accounting for CPU cycles and disk I/O, the optimizer transformed execution planning into a formal search problem. This marked the birth of a discipline that would spend the next half-century evolving through revolutions in theoretical computer science, computer architecture, and distributed systems.

This book charts the remarkable evolution of cost-based query optimization from those early research prototypes into the central computational engine driving the modern digital economy. It is a story of continuous tension between mathematical perfection and engineering pragmatism. Because join enumeration is NP-hard, query optimizers can never be pure brute-force evaluators; they are sophisticated engines of trade-offs. Over the decades, researchers and database architects have dismantled and rebuilt the optimizer's internals: evolving from bottom-up dynamic programming to extensible, rule-driven frameworks like Volcano and Cascades; transitioning from simplistic uniform histograms to advanced probabilistic sketching and hyper-dimensional synopsis structures; and shifting from static compile-time planning to runtime adaptivity and machine-learned cost estimation.

Today, the footprint of the query optimizer extends far beyond classical relational database management systems. The principles established in the relational dawn now orchestrate petabyte-scale analytical queries across thousands of nodes in cloud data warehouses, mediate graph and document traversals in schemaless NoSQL stores, and govern vectorized query pipelines running on modern multicore and hardware-accelerated processors. Whether inside an embedded engine like SQLite, an enterprise relational titan, or a globally distributed lakehouse, the optimizer remains the core brain of the data management stack.

Written for systems software engineers, database architects, graduate students, and curious practitioners who refuse to treat their database as an inscrutable black box, this book aims to illuminate the deep algorithmic machinery beneath declarative interfaces. As you turn these pages, you will follow the conceptual threads that connect early disk-bound relational prototypes to the autonomous, self-tuning cloud engines of today. In doing so, you will gain not only a profound technical understanding of query transformation, cardinality estimation, and physical plan synthesis, but also an enduring appreciation for one of the most sophisticated, consequential, and elegant software systems ever conceived.

In the late 1960s, long before developers could casually type a query into a terminal and expect an intelligent engine to work out the mechanics, retrieving data from a computer was an exercise in explicit physical navigation. Software systems did not possess an abstraction layer between the logic of an application and the physical arrangement of bits on magnetic tape, iron-core memory, or early disk drives. To extract an answer from a database, a programmer had to write an imperative program that issued explicit instructions on how to locate records, follow hard-coded memory pointers, and traverse physical storage structures step by step. If the underlying hardware shifted, or if an administrator reorganized the disk layout to free up space, the application logic broke immediately. Modern developers often take for granted that writing code to manipulate data is fundamentally distinct from managing the physical bytes on disk, but in the early decades of computing, these two concerns were hopelessly entangled.

To understand why the query optimizer became a necessity, one must first look at the database architectures that defined this procedural era: the hierarchical model and the network model. The primary commercial titan of the hierarchical world was IBM’s Information Management System, better known as IMS, which was developed in 1966 to track the millions of parts required for the Apollo space program. IMS structured data as strict parent-child trees. A top-level root record, such as a supplier, could own multiple child records, such as parts, which in turn could own grandchild records, such as line items. This model worked reasonably well when access patterns perfectly mirrored the fixed tree hierarchy. If your application needed to find a supplier and list all the parts supplied by that vendor, the pointer structures embedded in the records made navigation straightforward and predictable.

Problems arose as soon as an application required an alternative view of the same data. If a technician wanted to find all suppliers that produced a specific part, the hierarchical structure worked against them. Because the primary access path was rooted at the supplier level, the program could not simply jump to the desired part records. Instead, it had to scan the root nodes sequentially, descend into every child branch, evaluate the part details, and collect the matches manually. Data access was record-at-a-time, and procedural code was explicitly coupled to the physical layout on disk.

To address the rigid rigidity of hierarchical trees, the Conference on Data Systems Languages—a industry task group better known as CODASYL—formulated the network database model in the late 1960s. Systems like Cullinane’s IDMS implemented this vision, introducing the concept of set types that permitted a record to participate in multiple parent-child relationships simultaneously. Instead of a simple strict hierarchy, a network database formed a graph of records connected by pointer chains. An application navigated this graph by maintaining physical currency indicators: software cursors that kept track of the current record, current owner, and current position within a specific set.

While the network model added structural flexibility, it exponentially increased procedural complexity. Navigating a CODASYL database was analogous to playing a blindfolded game of micro-management inside a complex maze. Programmers had to issue low-level commands like FIND FIRST, FIND NEXT, and GET, explicitly instructing the database engine to follow pointer links through physical memory blocks. The programmer was required to act as their own execution engine, mentally tracing execution paths, selecting indices, and manually deciding whether to traverse set link chains or scan record sets sequentially.

Consider a typical data access task in a CODASYL environment: finding all projects assigned to a specific department along with the employee details for everyone working on those projects. Writing this required dozens of lines of tightly coupled application code. The developer had to navigate to the department record, loop over the set of attached project pointers, and for each project record, navigate across a separate pointer chain to fetch the employee records. The developer, not the system, was responsible for optimizing the traversal loop, ordering the pointer jumps, and deciding how to handle missing keys or corrupt link pointers.

This procedural paradigm suffered from a fatal architectural flaw: a total lack of physical data independence. Physical data independence is the principle that the logical schema seen by application developers should remain completely decoupled from the physical layout, storage structures, and access mechanisms used by the underlying software engine. In hierarchical and network databases, physical data independence did not exist. Pointer chains were physically stored inside record headers or index nodes. If a database administrator decided to add an index, split a file across multiple disks, or reorder a set of pointers to optimize performance for a new reporting tool, every application program that relied on the old physical memory paths had to be laboriously rewritten, recompiled, and retested.

By the end of the 1960s, enterprise software development was facing a crisis of maintainability. As businesses expanded and their data management requirements grew more intricate, corporations found that up to eighty percent of their software engineering bandwidth was spent modifying existing code to adapt to physical database migrations and schema evolution. Applications were fragile, brittle structures held together by procedural navigation code. The computing industry desperately needed a model that separated the mathematical specification of what data was required from the physical implementation details of how that data was stored and retrieved.

The catalyst for change came in June 1970, when Edgar F. Codd, a mathematician working at the IBM San Jose Research Laboratory, published a landmark paper titled A Relational Model of Data for Large Shared Data Banks. Codd recognized that the root cause of the maintenance crisis was the physical coupling inherent in procedural database navigation. His proposal was radical: replace physical pointer networks with mathematical relations, represented as flat tables consisting of rows and columns.

In Codd’s relational world, data elements were no longer linked by physical memory addresses or embedded system pointers. Instead, relationships between tables were expressed purely through data values contained within the columns themselves. To connect an employee record to a department record, one did not traverse a physical link chain; one matched the value of a department identifier column in the employee table with the corresponding primary key column in the department table.

Crucially, Codd introduced set-at-a-time relational operators—such as selection, projection, and join—grounded in predicate calculus and relational algebra. Instead of processing data record-at-a-time via imperative navigation code, a user expressed queries declaratively, defining logical conditions that specified the desired result set. The user stated what data they wanted, leaving the underlying computing environment completely free from any prescribed path or sequence of instructions.

This mathematical abstraction achieved true physical data independence. Because tables were abstract mathematical sets, the database management system could change physical disk layouts, introduce B-trees, partition files, or build secondary indices without altering the mathematical meaning of a relational query. An application query written against relational tables would remain syntactically and semantically valid regardless of how the physical storage beneath it evolved over time.

However, Codd’s declarative vision met immediate and fierce resistance from systems engineers and database practitioners of the day. Skeptics argued that while relational math was elegant in an academic paper, it was fundamentally impractical for production workloads. The critique was based on a simple reality: hardware in the 1970s was constrained by limited memory and slow disk I/O. Procedural network database programs were blindingly fast precisely because human programmers hand-crafted and hand-tuned every single pointer traversal to minimize disk arm movement and CPU cycles. An experienced programmer knew which physical index to use, which loop order was optimal, and when to bypass standard record sets to reach a target block directly.

The declarative model eliminated the human navigator. By forbidding the programmer from writing pointer-level execution logic, Codd shifted the burden of physical plan generation entirely to the software system itself. If a declarative query simply requested the set of all employees in the engineering department working on active projects, the database management system had to figure out how to retrieve that data.

Without an automated component capable of making intelligent physical execution choices, a relational database engine would have to default to naive evaluation strategies: reading whole tables sequentially, cross-joining every row with every other row, and evaluating criteria line by line. For tables containing millions of rows, such unoptimized set operations would require hours or days to execute, while a hand-tuned CODASYL program could return the same result in seconds.

The declarative promise had created an existential engineering bottleneck. The industry could not enjoy the software design benefits of logical and physical data independence unless the database management system possessed a software component that could automatically analyze a declarative query and transform it into a physical execution plan capable of matching—or exceeding—the performance of a hand-tuned imperative program written by a expert developer.

This necessity gave birth to the query optimizer. The job of the query optimizer is to act as an automated compiler for declarative data requests. It accepts a high-level query specification expressed in a language like SQL, translates that request into a relational algebra tree, explores alternative physical implementation strategies, and emits an imperative physical plan composed of lower-level storage engine calls.

To grasp why this translation task is demanding, consider the sheer combinatorial variety that exists when translating a non-procedural query into a physical execution plan. Even for a simple declarative query involving three tables, a set of filter conditions, and an ordering requirement, the search space of execution possibilities is large. The engine must answer numerous concrete operational questions:

In what sequence should the tables be joined? Joining table A to table B and then joining the result to table C might process ten thousand intermediate rows, whereas joining table B to table C first might produce an intermediate set of only five rows.

Which physical algorithm should be used for each join operation? Should the engine construct a hash table in memory, execute a nested loop over secondary indices, or perform a sort-merge operation on disk-sorted files?

How should individual table records be filtered? Should the system execute an index scan using an existing secondary B-tree, scan the main clustered index, or perform a full sequential scan of the table space while applying bitmask filters?

Should temporary intermediate results be written to disk, kept in memory buffers, or streamed directly through a execution pipeline?

The table below illustrates the contrast between the procedural approach of pre-relational systems and the declarative paradigm that necessitated query optimization:

In the early years following Codd's paper, early relational prototypes relied on naive, rule-based heuristics to process declarative queries. These early engines applied fixed structural transformations: evaluating simple local selection filters as early as possible, utilizing a secondary index whenever one happened to match a column referenced in a predicate, and executing joins in the exact lexical order in which tables were listed in the query string.

While these heuristic rules were an improvement over unoptimized full-table cross products, they lacked any true understanding of the data's underlying statistical properties. A heuristic rule that forces the usage of an index might perform exceptionally well when a filter predicate matches two rows out of a million. However, if that same filter predicate matches nine hundred thousand rows out of a million, using that secondary index causes hundreds of thousands of random disk reads, performing orders of magnitude worse than a sequential table scan. Heuristics were blind to data scale, data skew, value distribution, and physical storage costs.

It quickly became obvious to researchers that simple fixed rules were insufficient to make relational databases commercially viable against hand-tuned navigational engines. To fulfill Codd’s vision, database engines required a principled, quantitative mechanism to evaluate alternative physical plans. The system needed a way to model physical storage dynamics, compute mathematical estimates of intermediate data sizes, quantify the resource costs of CPU operations and disk accesses, and dynamically select the cheapest overall physical execution plan from among millions of theoretical possibilities.

The declarative promise had set the stage for one of the most important chapters in software systems history. The shift from low-level physical pointer navigation to high-level declarative set logic was not merely a syntax change; it fundamentally altered where computing intelligence resided. By relieving human developers from the burden of manual navigation, the relational model placed the burden of performance squarely on the software engine itself. The survival of the relational model depended entirely on whether computer scientists could design an automated engine capable of reasoning about data access costs as effectively as a human systems programmer. That challenge led directly to the creation of cost-based query optimization.