The Transition from Rule-Based to Cost-Based Optimization: Oracle Case Study

Relational database management systems (RDBMS) rely on a component known as the optimizer to determine the most efficient path for executing SQL statements. For several decades, Oracle Corporation utilized two distinct methodologies for this task: the Rule-Based Optimizer (RBO) and the Cost-Based Optimizer (CBO). The transition between these two frameworks represents a significant shift in database engineering, moving from a rigid, heuristic-driven model to a dynamic, statistics-oriented system.

The Oracle Rule-Based Optimizer was the primary mechanism for query path selection until the mid-1990s. It utilized a predefined set of 15 ranks to evaluate potential execution plans. This approach did not consider the actual volume or distribution of data within the tables; instead, it followed a fixed hierarchy where certain access methods were always preferred over others. With the release of Oracle Database 10g, the RBO was officially deprecated, requiring administrators and developers to migrate legacy systems to the CBO to maintain support and performance.

What changed

• Decision Basis:The RBO used a fixed hierarchy of 15 rules (ranks) to select execution plans. The CBO uses data statistics (cardinality, selectivity, and cost) gathered by the database engine.
• Flexibility:RBO plans were predictable but static, often ignoring the most efficient path if it violated the rule hierarchy. CBO plans are dynamic, adjusting as the data within the tables grows or changes.
• Join Methods:While RBO primarily relied on nested loop joins, the CBO introduced and optimized hash joins and sort-merge joins based on the estimated size of the result sets.
• Statistics Requirement:The RBO required no metadata about table sizes. The CBO necessitates regular execution of statistics collection (e.g., via DBMS_STATS) to function accurately.
• Index Utilization:In RBO, the presence of an index almost always forced its use. In CBO, the optimizer may choose a full table scan if it determines that reading the index and the table would be more expensive than a sequential scan of the data blocks.

Background

The foundations of relational query optimization were established in the late 1970s, most notably by Patricia Selinger and her team at IBM during the development of System R. Selinger’s research introduced the concept of cost-based optimization, which attempted to model the physical resources—specifically CPU and I/O—required to execute a query. This research identified that the order in which tables are joined and the methods used to access them significantly impact system latency.

Oracle Corporation initially adopted a rule-based approach because the computational overhead of calculating costs was high, and early database environments often lacked the complex data distributions that necessitate a cost-based model. In the RBO era, a developer could manually tune a query by rearranging the order of tables in theFROMClause or by adding specific indexes, knowing exactly how the optimizer would respond. However, as databases grew to multi-terabyte scales and query complexity increased, the limitations of heuristic ranking became a bottleneck for enterprise performance.

The Hierarchy of the Rule-Based Optimizer

The RBO operated on a strict ranking system. If multiple access paths were available for a query, the optimizer selected the one with the lowest rank. The following table illustrates the primary ranks utilized by the RBO before its deprecation:

Under this system, the physical reality of the data was ignored. For example, if a table had 1,000,000 rows and an index existed on a column where 999,000 rows shared the same value, the RBO would still use the index (Rank 9) rather than a full table scan (Rank 15), despite the index being vastly less efficient in that specific scenario.

The Mechanics of Cost-Based Optimization

The CBO abandoned the rank system in favor of an arithmetic approach. It evaluates multiple execution plan candidates and assigns each a "cost" value. The objective is to select the plan with the lowest total cost. The CBO calculates this by analyzing three primary metrics:

1. Cardinality:The estimated number of rows that will be returned by a specific operation (e.g., a filter or a join).
2. Selectivity:The fraction of rows from a row set that satisfy a predicate (e.g., aWHEREClause).
3. Cost:A unit of measure representing the expected resource usage. In modern Oracle versions, this is primarily expressed in terms of the time required to complete the I/O operations and CPU cycles.

"The shift to CBO allowed the database to transform the query structure itself through techniques like predicate pushdown, where filters are applied as early as possible in the execution chain to reduce the size of intermediate result sets."

Migration Challenges and Legacy SQL

When Oracle transitioned from version 9i to 10g, the removal of RBO support created significant challenges for organizations with legacy codebases. Many applications had been "hand-tuned" for the RBO. Because the CBO relies on statistics, queries that performed well for years suddenly suffered from "plan instability" or "plan flipping."

A common migration challenge involved the absence of table statistics. If a table migrated to a 10g environment lacked statistics, the CBO would often default to guestimates or perform dynamic sampling, which could lead to suboptimal join orders. To mitigate this, Oracle introduced theOPTIMIZER_MODEInitialization parameter, allowing users to set it toRULE(in older versions) orCHOOSE. However, by version 10g, theRULEMode was no longer functionally supported for new features, forcing a widespread adoption of theDBMS_STATSPackage to generate histograms and density maps of data distribution.

Join Algorithm Selection

One of the most complex aspects of the CBO is the selection of join algorithms. Unlike the RBO, which favored nested loops, the CBO evaluates three primary methods:

• Nested Loop Join:Best for joining a small outer table to a large inner table with an index. The optimizer "loops" through the outer rows and looks up matches in the inner table.
• Hash Join:Preferred for large data sets. The optimizer builds a hash table in memory for the smaller of the two data sets and then probes it with the larger set.
• Sort Merge Join:Used when the data is already sorted or when a join condition uses an inequality (e.g.,>Or<).

The CBO’s ability to choose between these based on the actual number of rows involved—rather than a fixed rule—marked the maturity of Oracle’s relational query optimization mechanics. This evolution allowed databases to scale to the demands of modern data warehousing and complex analytical processing (OLAP), where fixed rules are insufficient for the sheer variety of data patterns encountered.

Statistical Estimator Accuracy

The effectiveness of the CBO is entirely dependent on the accuracy of the statistics it consumes. Modern Oracle engines use histograms to deal with data skew. For instance, if a column representing "Country" has 90% of its values as "USA" and 1% as "Canada," a height-balanced or frequency histogram allows the CBO to realize that a query for "Canada" should use an index, while a query for "USA" should likely use a full table scan. This level of nuance was impossible under the RBO framework, illustrating the fundamental necessity of the transition for high-performance relational database systems.