In 1979, a group of researchers at the IBM San Jose Research Laboratory published a technical paper that redefined the engineering of relational database management systems (RDBMS). The document, titled "Access Path Selection in a Relational Database Management System," authored by Patricia Selinger and her colleagues, introduced the first detailed framework for cost-based optimization (CBO). This research was part of the System R project, IBM's experimental effort to implement the relational model first proposed by Edgar F. Codd in 1970. The Selinger paper established the methodological underpinnings for how a database engine evaluates a SQL query and selects the most efficient execution plan from a massive search space of potential alternatives.
Before the introduction of the System R optimizer, database systems relied heavily on manual tuning or simple rule-based heuristics that did not account for the actual distribution or volume of data. The Selinger framework shifted the model by introducing a mathematical cost model. This model estimated the resources—specifically CPU cycles and I/O operations—required for different execution strategies. Today, the core principles established in 1979, including the use of dynamic programming for join ordering and the concept of "interesting orders," remain central to the optimizers found in modern systems such as PostgreSQL, Microsoft SQL Server, and Oracle.
In brief
- The Foundation:Pat Selinger’s 1979 paper provided the blueprint for cost-based optimization, moving away from static rules to dynamic statistical estimations.
- Dynamic Programming:The framework introduced a systematic way to explore join orders by building up optimal solutions for sub-queries, a technique still used in most SQL engines today.
- Cost Function:The original model defined cost as a weighted sum of I/O (page fetches) and CPU usage (number of instructions), allowing the engine to predict performance before execution.
- Interesting Orders:The optimizer recognizes when a particular access path (like an index) produces results in a sorted order that could benefit subsequent operations, such as joins or grouping.
- Cardinality Estimation:Central to the process is the estimation of how many rows will be returned at each step of the query plan, based on data statistics and selectivity.
Background
The relational model proposed by E.F. Codd in the early 1970s offered a high degree of data independence, allowing users to defineWhatData they wanted without specifyingHowThe computer should retrieve it. However, early critics argued that this abstraction would lead to unacceptable performance compared to the then-dominant hierarchical and network database models, which required programmers to manually handle data pointers. The primary challenge was the non-procedural nature of SQL; since a single query could be executed in thousands of different ways, the database engine required an automated mechanism to find the optimal path.
Prior to System R, systems often used Rule-Based Optimization (RBO). RBO followed a fixed hierarchy of priorities. For example, a rule might state: "If an index exists on a column in the WHERE clause, always use it." While predictable, RBO was rigid and often made poor decisions when data distributions were skewed. If an index existed on a column where 99% of the values were identical, using the index would be far slower than a full table scan. The emergence of the Selinger framework addressed this by integrating statistical knowledge of the data into the decision-making process.
The Mechanics of Access Path Selection
Relational query optimization mechanics involve dissecting a query into its fundamental algebraic components. The optimizer first parses the SQL statement into a query tree or graph. Each node in this graph represents a relational operation, such as a selection, projection, or join. The "Access Path Selection" refers to the choice made for the leaf nodes: how to retrieve the base data from the physical storage media. The two primary paths are the sequential scan (reading every page of a table) and the index scan (using a B-tree or similar structure to jump to specific records).
The Selinger model introduced the concept of "selectivity," which is the fraction of rows in a table that satisfy a given predicate. By multiplying the total number of rows (cardinality) by the selectivity of the filters, the optimizer can estimate the intermediate result set size. These estimations are critical because they dictate the choice of join algorithms further up the query tree. Modern systems have refined this by using histograms and multi-column statistics to handle correlated data, yet the basic logic of calculating selectivity remains tied to the 1979 principles.
Join Ordering and Dynamic Programming
Perhaps the most enduring contribution of the Selinger framework is the approach to join ordering. In a query involving multiple tables, the order in which they are joined significantly impacts performance. ForNTables, the number of possible join orders grows exponentially. An exhaustive search of every possible combination is computationally prohibitive for large queries. To solve this, Selinger applied dynamic programming.
The algorithm works bottom-up. It first finds the best way to access each individual table. Then, it finds the best way to join pairs of tables, reusing the optimal results from the first step. This process continues until all tables are joined. To further prune the search space, the optimizer typically only considers "left-deep" trees, where the right-hand input of any join is always a base table. While this limits the exploration of "bushy" trees (where two intermediate results are joined together), it keeps the optimization time manageable. Modern optimizers, such as the one in PostgreSQL, still use this dynamic programming approach for small to medium-sized joins, though they may switch to genetic algorithms or other heuristics when the number of tables exceeds a certain threshold.
The Transition from Rule-Based to Cost-Based Models
The industry-wide shift from RBO to CBO was most visible during the 1990s. Oracle Corporation’s documentation from the early part of that decade illustrates this evolution. In Oracle 6, the optimizer was primarily rule-based. With the release of Oracle 7 and 8, the Cost-Based Optimizer was introduced as the preferred method, though the RBO remained available for backward compatibility. This transition was necessitated by the increasing complexity of data warehouse workloads and the variety of physical storage options, such as partitioned tables and bitmapped indexes.
The CBO allowed for more sophisticated optimizations, such as "predicate pushdown," where filters are moved as close to the data source as possible to reduce the volume of data flowing through the join pipeline. It also enabled "view merging," where the definition of a virtual view is integrated into the main query to allow the optimizer to reorder joins across the view boundary. These advancements were only possible because the engine could now compare the costs of a merged view versus a materialized one using the statistical models pioneered by the System R team.
Modern Implementation: SQL Server and the Cascades Model
While the Selinger framework provided the foundation, subsequent research led to new optimization architectures. Microsoft SQL Server utilizes a framework known as Cascades, which is based on the Volcano optimizer model developed by Goetz Graefe. Unlike the strictly bottom-up dynamic programming of Selinger, the Cascades model is a top-down approach that uses transformation rules to explore the search space. However, it still relies on the same fundamental pillars: a cost model, cardinality estimation based on statistics, and the pruning of suboptimal paths.
Modern engines also incorporate "adaptive" query optimization. This addresses a major weakness of the original Selinger model: the reliance on potentially inaccurate statistics. If the optimizer predicts 10 rows will return from a filter but 1,000,000 actually appear, the chosen join algorithm (such as a nested loop join) may become disastrously slow. Adaptive engines can now detect these discrepancies during execution and switch to a more appropriate algorithm, such as a hash join, on the fly. This represents a dynamic extension of the static plan selection described in 1979.
"The goal of an optimizer is not necessarily to find the absolute best plan, but to avoid choosing a significantly bad plan."
This sentiment, often echoed by database architects, highlights the practical reality of query optimization. The mechanics of relational query optimization are as much about risk management as they are about mathematical perfection. By meticulously analyzing query graphs, identifying dependencies, and evaluating indexing structures against estimated distributions, the legacy of Pat Selinger’s work continues to ensure that relational systems can handle the vast and complex data demands of the modern era.
