A Practical Guide to Rule Based Optimizer (RBO)

What is Rule-Based Optimizer (RBO)?

At its core, a Rule-Based Optimizer applies a fixed set of heuristics to transform a logical query plan into a physical execution plan. This process is deterministic and purely structure-driven—meaning the same query will always produce the same plan, regardless of data volume or distribution.

Let’s unpack this process in more depth.

1. Logical Plan Analysis and Pattern Recognition

Once a SQL query is parsed, it’s translated into a logical plan—a tree-like representation of relational algebra operations: scans, joins, filters, aggregations, projections, etc.

The optimizer traverses this plan looking for substructures that match known rule patterns. This is where the “rule-based” approach begins: each rule includes a pattern-matching clause that defines what kind of plan fragment it can act upon.

Example: A rule might apply to any subtree with a Filter node above a Scan node, enabling predicate pushdown.

Pattern matching in this context isn’t just syntactic—it operates over the abstract relational structure of the query. Optimizers may use tree traversal algorithms (preorder, postorder, etc.) to efficiently match candidate rules to query subtrees.

2. Rule Matching and Activation

Not all rules fire for every query. Only those whose preconditions are satisfied by the logical plan get activated. Once matched, a rule will transform the applicable subtree into a new one.

For example:

• If a Filter applies to a column with an index, the rule may rewrite the logical plan to replace a full scan with an index scan.

• If a query includes nested subqueries that can be flattened, a rule may rewrite those into joins or CTEs.

This step is often repeated recursively, as applying one rule may create new patterns that match subsequent rules.

3. Rule Application Ordering: Sequential vs. Phased

Rule execution order is critical in RBOs because rule output is not cost-evaluated. Unlike CBOs, where multiple transformed plans compete based on estimated cost, an RBO simply executes rules in a fixed order.

There are two common models:

• Linear (Sequential): Rules are arranged in a prioritized list. The optimizer scans the list top to bottom and applies the first applicable rule.

• Phased (Hierarchical): Rules are grouped into stages. Lower-level rules (e.g., predicate pushdown) must run to completion before higher-level rules (e.g., join reordering) can begin.

This ensures that certain “safe” rewrites—like expression simplifications or constant folding—happen early and don’t interfere with more complex structural changes.

In practice, this model enforces determinism. Two identical queries always yield the same plan.

4. Transformation Mechanics: Structural Rewrites

RBOs primarily rely on rewriting the logical tree using transformation rules. These rules may target:

• Access paths: e.g., replace a full scan with an index scan

• Join order and strategy: e.g., reorder joins left-to-right, convert nested joins to hash joins

• Predicate pushdown: e.g., move filters closer to scans to reduce intermediate result size

• Projection pruning: e.g., eliminate unnecessary columns early to reduce memory pressure

• Expression normalization: e.g., convert NOT (a = b) to a != b

Unlike a CBO, which tries multiple candidate trees and scores them, an RBO commits to each transformation as it applies it. This makes the transformation path easier to debug but also more brittle in changing workloads.

5. Rule Examples in Real Systems

Here are representative examples of rules and their rewrite behavior:

Some systems, like CockroachDB, define these in a DSL (domain-specific language) to enable modularity and reuse. Others, like older versions of Oracle or PostgreSQL, hard-code them in the planner.

6. Limitations of Rule Interactions

Rule application isn’t always independent. Some rewrites can block others if applied in the wrong order. For instance:

• Reordering joins too early might prevent filter pushdown.

• Pushing down projections might interfere with aggregations.

That’s why ordering is critical. Well-designed RBOs define precedence graphs or dependency chains to avoid these conflicts, but poorly ordered rules can lead to bloated or redundant plans.

7. Output: One Deterministic Plan

At the end of the process, the RBO produces a single physical execution plan. No alternatives are considered. There’s no notion of “best plan” in terms of cost—only “valid transformations” according to predefined rules.

This gives you:

• Repeatability: Plans never change unless rules do.

• Traceability: Easy to follow why a particular path was chosen.

• Stability: Ideal for regulated environments where consistency trumps performance variance.

Thought on Execution Path Stability

The deterministic path of RBOs is both a strength and a liability. While you get guaranteed predictability—especially important in embedded, low-footprint systems or legacy business workflows—you lose the opportunity to adapt. A highly selective filter might be applied late simply because the rules don’t prioritize it early enough. There’s no feedback loop.

In modern hybrid engines like StarRocks, RBO-like rule rewrites still exist—but typically serve as the pre-processing layer before cost-based optimization begins. In such designs, RBO transformations act as a scaffolding layer, ensuring the query is clean and logically simplified before cost modeling is applied.

Let me know if you want to extend this section with rule DSL examples (e.g., from CockroachDB), or draw parallels with Cascades frameworks.

 

Advantages of Rule-Based Optimizers (RBO)

Although often overshadowed by modern cost-based optimizers, Rule-Based Optimizers still offer important advantages in specific architectural scenarios. These strengths stem from their deterministic logic, simplicity, and low overhead.

1. Deterministic Behavior

RBOs follow a fixed sequence of rules that operate solely on query structure. This means:

• The same query will always generate the same execution plan.

• Plan changes occur only when the query text or rule definitions change.

This determinism is valuable in environments where plan stability is a requirement:

• Debugging: Easy to reproduce and trace execution plans.

• Auditing: Plan changes can be tracked and reviewed explicitly.

• Regulated systems: Execution behavior must remain consistent across environments.

In contrast, cost-based optimizers (CBOs) can change plans unpredictably due to statistics drift or optimizer version differences.

2. No Dependency on Statistics

RBOs operate independently of:

• Cardinality estimates

• Histograms or distribution metrics

• Runtime profiling

This makes them resilient in environments where:

• Statistics are costly or impossible to gather (e.g., edge computing, embedded systems).

• Data is highly dynamic or unstructured, making stats obsolete quickly.

• Governance or encryption restricts introspection, preventing the optimizer from “seeing” into the data.

Without a stats collection pipeline to maintain, operational overhead is significantly reduced.

3. Fast Plan Generation and Low Footprint

Because RBOs don’t evaluate multiple alternative plans or compute cost models, they:

• Generate plans quickly (often near-instantaneous).

• Consume less memory and CPU during optimization.

• Avoid complex planning logic or memoization overhead.

This makes them well-suited for:

• Runtime plan generation in serverless or interactive apps.

• Resource-constrained environments like IoT, mobile, and embedded databases.

• Pre-compilation contexts where queries are generated dynamically but must compile instantly.

4. Predictable Performance in Stable Workloads

When the schema is fixed, access patterns are consistent, and query templates are reused, RBOs provide a stable performance baseline with minimal tuning:

• No need to recalibrate join thresholds or query hints.

• No need to reanalyze table statistics after data updates.

• Minimal risk of performance regression due to optimizer behavior.

This is especially useful in:

• Templated BI dashboards

• Static ETL pipelines

• Reports scheduled over consistent datasets

Limitations of Rule-Based Optimizers

The same design principles that make RBOs simple and predictable also limit their effectiveness in more complex or dynamic systems. Their inability to reason about data leads to several architectural constraints.

1. Lack of Cost Awareness or Adaptability

RBOs don’t consider:

• Actual row counts or table sizes

• Filter selectivity

• Join cardinalities or sort cost

They apply rules statically, regardless of underlying data. This results in:

• Inefficient scan choices (e.g., using an index when a full scan is cheaper).

• Rigid join orderings based on syntax or hardcoded size hints.

• Inability to exploit cheaper join types (e.g., hash vs. merge vs. nested loop).

2. Poor Join Optimization in Complex Queries

Join planning is one of the hardest problems in query optimization. RBOs:

• Typically join in left-to-right or written order.

• May join large tables before smaller filters are applied.

• Struggle with star schemas or snowflake joins common in analytics.

In multi-join queries, this can result in:

• Intermediate result sets that explode in size.

• Excessive memory usage and I/O.

• Plans that scale poorly with data growth.

3. No Feedback or Runtime Learning

RBOs do not:

• Track runtime execution profiles.

• Adjust future plans based on observed performance.

• Respond to query failures, timeouts, or hotspots.

This limits their effectiveness in:

• Adaptive query environments.

• Federated queries where data characteristics change across sources.

• Real-time or streaming analytics pipelines with unpredictable inputs.

4. Limited Handling of Complex SQL Constructs

RBOs often fall short when faced with advanced SQL features:

• Common Table Expressions (CTEs) may not be inlined or rewritten efficiently.

• Window functions may not be optimized or parallelized.

• Subqueries, especially correlated ones, may not be flattened into joins.

Without a global cost model, RBOs can't holistically rewrite or collapse query plans—often requiring engineers to manually refactor SQL.

RBO vs CBO: A Deep Comparison 

1. Optimization Strategy

Example: An RBO might always choose an index scan for a WHERE clause if the index exists—even if the filter is unselective. A CBO might prefer a full table scan if it estimates fewer random I/Os overall.

2. Data Dependency and Adaptability

In high-cardinality joins with data skew, RBOs might always pick a nested loop, while a CBO can choose a broadcast join or partition-aware hash join.

3. Performance and Plan Quality

RBO works fine for simple queries or small lookups. But as soon as 4+ joins or subqueries are involved, its rigid strategy tends to collapse into inefficient plans.

4. Planning Overhead and Compilation Time

In low-latency systems or embedded DBs, RBO may be preferred because it compiles instantly. CBOs often take milliseconds to seconds to find the best plan.

5. Maintainability and Operational Cost

Example: In a distributed CBO like in StarRocks or Snowflake, operators often need to run scheduled ANALYZE jobs to update stats and avoid performance regressions.

Hybrid Models in the Real World

Most modern query engines blend RBO and CBO strategies:

• Preprocessing with Rules: Simple rewrites like constant folding, projection pruning, and subquery flattening are rule-based and run before cost modeling.

• Cascades-Based CBO: Systems like StarRocks and CockroachDB use memoization + transformation rules + cost models to find optimal plans.

• Fallback RBO Paths: In some cases, if statistics are missing or corrupted, systems can fall back to rule-based plans to guarantee execution.

StarRocks, for example, uses rule-based predicate pushdown and materialized view rewrite before its cost-based join reordering and scan selection kicks in.

Summary Table

When to Use an RBO (and Why It Still Matters)

Despite the dominance of Cost-Based Optimization in modern systems, Rule-Based Optimizers remain valuable in environments where simplicity, predictability, and low overhead are paramount. Their utility emerges not from sophistication, but from constraint-aware design.

1. Embedded, Edge, and Lightweight Systems

In systems where resources are limited—both compute and memory—RBOs shine due to their minimal overhead and deterministic behavior. There's no need for:

• Cardinality estimation

• Statistics gathering

• Runtime plan search or costing

Use Cases:

• Embedded SQLite databases in mobile apps

• Local browser-based SQL engines (e.g., DuckDB running client-side)

• Lightweight analytics in IoT gateways or edge devices

Example: A thermostat that logs sensor data locally and runs basic queries using SQLite benefits from fast RBO planning with negligible memory footprint.

2. Legacy, Regulated, or Safety-Critical Environments

RBOs are often deployed in environments where:

• Plan determinism is required for regulatory or audit purposes

• Infrastructure or query engines are decades old and too costly to modernize

• Code and schema changes are infrequent and highly controlled

Use Cases:

• Healthcare systems generating repeatable patient reports

• Banking or compliance audit trails

• Industrial SCADA databases where consistency outweighs optimization

In such contexts, even a 5× slower query may be acceptable—if it runs the same way every time.

3. Stable, Small-Scale, or Templated Workloads

In reporting dashboards, periodic batch ETLs, or lookup-heavy microservices with:

• Few or no joins

• Small tables

• Repetitive query templates

…RBOs deliver stable performance with zero maintenance overhead. You don’t need to monitor statistics, recalibrate the optimizer, or explain performance shifts.

Use Cases:

• Static reference lookups (e.g., country codes, currency conversions)

• Fixed ETL workflows running over well-understood schemas

• Scheduled reports where queries don’t change month-to-month

RBOs are often embedded in homegrown tools and ETL schedulers for this reason.

When Not to Use an RBO

RBOs begin to fall apart in environments that demand adaptability, performance tuning, or dynamic optimization. Here’s where they simply don’t scale.

1. Analytic Workloads with Joins, Aggregations, or Subqueries

Complex OLAP queries—especially those involving:

• Multiple joins across large tables

• Grouping, sorting, and aggregation

• Nested subqueries, especially correlated ones

…require plan choices that depend on data volume and shape. RBOs don’t evaluate cost and often:

• Join in suboptimal order

• Choose inefficient scan paths

• Miss opportunities to eliminate intermediate shuffles or sorts

StarRocks’ CBO, by contrast, estimates costs across join graphs and rewrites accordingly—even using bushy joins where appropriate.

2. Rapidly Changing or Heterogeneous Data Distributions

When table sizes, distributions, or filter selectivity change frequently:

• A rule that once selected an index scan may now cause thrashing

• Join order based on schema assumptions can produce Cartesian explosions

• The optimizer cannot react unless the developer rewrites the query

Typical environments include:

• Streaming ingestion tables

• Shared analytics tables with mixed usage patterns

• SaaS apps supporting ad hoc querying across customer datasets

A modern lakehouse query engine like StarRocks or Snowflake will dynamically adjust plans based on current partition sizes, row counts, and user concurrency—RBOs cannot.

3. Customer-Facing or Multi-Tenant Analytics

When query workloads are:

• Dynamic (users build queries on the fly)

• Diverse (tenants have different access patterns)

• High-throughput (must meet SLA at scale)

…you need a cost model that reflects real system conditions.

Example: In a SaaS platform like Demandbase or Pinterest Ads, queries must run with:

• Sub-second latency

• Unpredictable filter predicates

• Variable group-by dimensions

Here, CBOs outperform RBOs by orders of magnitude—especially with features like:

• Materialized view rewrite

• Adaptive join strategies

• Partition pruning

4. Systems with Massive Data Volumes or Distributed Execution

RBOs make naive assumptions about I/O and CPU cost. In distributed systems:

• They don’t model network transfer cost (e.g., shuffle joins)

• They can’t account for skew or replication overhead

• They can't exploit adaptive execution strategies (e.g., dynamic re-partitioning)

Example: Trino, StarRocks, and ClickHouse all need to model where data lives and how much of it must move. An RBO simply can't do this.

Summary