In 1979, P. Griffiths Selinger and her colleagues at the IBM San Jose Research Laboratory published a paper titled "Access Path Selection in a Relational Database Management System." This document established the fundamental architecture for modern query optimizers by introducing a cost-based framework for executing SQL statements. Before this publication, database systems relied heavily on heuristic rules or manual tuning by programmers to determine how data should be retrieved. The System R project, which served as the experimental vehicle for these ideas, demonstrated that a database engine could autonomously analyze the structure of a query and select the most efficient execution plan based on statistical models of the data.
The mechanics described in the 1979 paper provided the first detailed solution to the problem of join ordering and access path selection in a relational context. By treating the execution of a query as a search problem within a multi-dimensional space of possible plans, the researchers developed an algorithm that minimized the total resources required for data retrieval. This approach is now recognized as Relational Query Optimization Mechanics, a discipline that combines algebraic transformations with computational complexity theory to manage the execution of complex SQL commands across massive datasets.
What changed
The introduction of the Selinger optimizer marked a significant departure from the software engineering practices of the 1970s. The following shifts redefined the relationship between developers and database engines:
- Shift from Heuristics to Cost-Based Modeling:Early systems used fixed rules, such as "always use an index if available." The Selinger model introduced quantitative estimates of I/O and CPU costs, allowing the system to bypass an index if a sequential scan was determined to be faster.
- Automated Join Ordering:The paper introduced a dynamic programming approach to find the optimal order in which to join multiple tables, a task that previously required manual intervention to avoid performance bottlenecks.
- Introduction of Statistics:System R began tracking table cardinalities and index distributions, enabling the optimizer to predict the size of intermediate result sets.
- Concept of "Interesting Orders":The optimizer was designed to recognize when a specific access path (like an index scan) produced results in a sorted order that would benefit subsequent operations, such as a join or a GROUP BY clause, even if that path was more expensive initially.
Background
During the late 1960s and early 1970s, database management was dominated by hierarchical and network models, such as IBM's IMS. These systems required users to understand the physical storage of data and write complex procedural code to handle record pointers. When E.F. Codd proposed the relational model in 1970, it introduced a declarative approach where users specified *what* data they wanted rather than *how* to get it. However, the viability of the relational model depended entirely on the ability of the system to translate these declarative requests into efficient machine instructions.
The System R project was initiated at IBM to prove that the relational model was not only theoretically sound but also commercially viable. The query language developed for System R, known as SEQUEL (later SQL), allowed for nested queries and complex joins. Without an intelligent optimizer, a complex SQL statement could result in an execution plan that took hours or days to complete. The research team, led by Patricia Selinger, sought to automate the selection of the "access path"—the sequence of internal operations used to fetch and combine data from disk-based tables.
The Anatomy of the Search Space
Relational query optimization involves exploring a vast search space of potential execution plans. For a query involving multiple tables, the number of possible join permutations increases exponentially. ForNTables, there areN!Possible join orders, and for each pair of tables, several different join algorithms (such as nested loops or sort-merge joins) could be applied. The Selinger optimizer addressed this complexity by employing a dynamic programming algorithm that builds the optimal plan incrementally.
The algorithm starts by evaluating the cost of accessing each individual table using every available method, such as a full table scan or various index scans. It then proceeds to find the best way to join pairs of tables, then triples, and so on, until a complete plan is formed. A critical component of this process is pruning: at each step, the optimizer discards any plan that is more expensive than another plan producing the same set of rows in the same order. This significantly reduces the number of paths the system must evaluate while ensuring that the lowest-cost option is retained.
Cost Estimation and Cardinality
The efficacy of the Selinger model relies on the accuracy of its cost estimations. The optimizer calculates a cost value that represents a weighted sum of the expected number of disk I/O operations and the CPU cycles required to process the data. This calculation depends on "cardinality estimation"—the process of predicting how many rows will satisfy a specific filter or join condition.
| Cost Component | Description | Impact on Plan Selection |
|---|---|---|
| I/O Cost | Number of data pages fetched from disk | Primary driver for large-scale table scans and joins. |
| CPU Cost | Processing time for predicates and sorting | Critical for complex calculations and high-volume data filtering. |
| Selectivity | Fraction of rows satisfying a condition | Determines the size of intermediate results and join efficiency. |
To estimate selectivity, the system maintains metadata in a data dictionary. This includes the number of records in a table, the number of pages used for storage, and the number of unique values in specific columns. When a SQL query includes a predicate such asWHERE age > 25, the optimizer uses these statistics to guess what percentage of the data will pass the filter. If the statistics are outdated or inaccurate, the optimizer may choose a sub-optimal plan, a phenomenon often referred to as "plan regression."
Algebraic Transformations and Heuristic Pruning
While the Selinger model focuses on cost-based selection, modern database engines also apply algebraic transformations to simplify queries before the cost analysis begins. One of the most important transformations is "predicate pushdown." This involves moving filtering conditions as close to the data source as possible. By filtering rows early, the system reduces the size of the intermediate result sets that must be joined, thereby saving memory and CPU time.
Another common technique is "view merging," where the definition of a virtual table or view is expanded directly into the main query. This allows the optimizer to see all the underlying tables at once and potentially find a more efficient join order that spans across the view's boundaries. Similarly, subquery unrolling or flattening transforms nested queries into joins, which are typically easier for the cost-based optimizer to analyze using standard dynamic programming techniques.
The Role of Indexing Structures
The optimizer must choose between various indexing structures based on the nature of the query. B-tree indexes are the most common, as they provide efficient access for both equality and range searches. For columns with a low number of unique values, such as "Gender" or "Status," bitmap indexes may be used to allow for rapid bitwise operations. In environments with high-speed memory, hash indexes provide near-instant access for exact matches but do not support range-based filtering. The optimizer evaluates these structures by comparing the cost of traversing the index and then fetching the data pages versus the cost of a direct sequential scan of the entire table.
"The choice of an access path for a given query is based on the estimated number of I/O operations and the estimated CPU processing time. These estimates are derived from the statistics collected by the system about the data stored in the database."
The Persistent Legacy of System R
The principles established in the 1979 paper remain the cornerstone of relational database technology. Major commercial and open-source systems, including PostgreSQL, IBM Db2, and Microsoft SQL Server, continue to use a Selinger-style dynamic programming approach for their query optimizers. While modern systems have added sophisticated features such as histograms for better selectivity estimation, parallel execution capabilities, and machine learning models for cardinality prediction, the core logic of evaluating plans based on a cost metric derived from data statistics remains unchanged.
Subsequent advancements, such as the Cascades and Volcano optimization frameworks developed in the 1990s, expanded the Selinger model by providing a more modular architecture for defining optimization rules. However, these frameworks still operate on the fundamental premise of exploring a search space to find a minimum-cost execution path. The study of Relational Query Optimization Mechanics thus remains a vital field for database researchers seeking to keep pace with the increasing volume and complexity of global data.
