Rule Based Optimizer (RBO)
 
 

What is Rule-Based Optimizer (RBO)?

A Rule-Based Optimizer (RBO) is a type of query optimizer used in database management systems that determines query execution strategies by applying a fixed set of predefined rules. These rules are generally syntactic and structural in nature—focused on how a query is written and logically structured—rather than informed by any actual data statistics or runtime costs.

Think of an RBO like a checklist of "if-then" heuristics:

  • If a WHERE clause filters on a column with an index, then use the index.

  • If a query has multiple joins, then join tables in a predetermined order (e.g., smallest table first).

Unlike Cost-Based Optimizers (CBOs), which model the cost of alternative plans using statistics like cardinality, selectivity, or row size, RBOs treat every query the same way every time, provided the structure doesn’t change.


How Does a Rule-Based Optimizer Work?

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:

Rule Pattern Action
UseIndexOnFilter Filter(col = val) above Scan(table) Rewrite to IndexScan(table, col = val) if index exists
JoinOrderHeuristic Join(A, B) where A < B (by declared size) Preserve A JOIN B; don’t swap
SubqueryFlattening Select * from (Select ...) Merge subquery into parent plan
ProjectionPruning Project(col1, col2) on Scan(table) Eliminate unused columns from scan
SimplifyExpr a = a or x * 1 Replace with constant TRUE or x

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

Aspect RBO CBO
Decision Logic Applies a fixed set of heuristic rules to rewrite query plans Models execution cost of alternative plans using data statistics
Plan Selection One deterministic plan per query Considers many alternatives and selects the lowest-cost one
Transformation Driver Query structure (syntax, logical operators) Data volume, cardinality, selectivity, estimated I/O/CPU cost

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

Aspect RBO CBO
Uses Statistics? No Yes—cardinalities, histograms, null rates, etc.
Adapts to Data Changes? No—plan is static unless query structure changes Yes—plan may change as data volume or distribution changes
Sensitive to Skew? No Yes—CBO can favor skew-aware join strategies (e.g., broadcast vs. shuffle)
Supports Runtime Feedback? Not inherently Some advanced CBOs integrate runtime profiling or feedback loops

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

Aspect RBO CBO
Best Plan Guarantee No—rule-based plans may be suboptimal Yes—picks the lowest-cost plan based on current model
Query Performance Stability High (same plan every time) Variable—plan can change due to stats or engine version
Execution Plan Diversity Limited Broad—CBO considers many more physical plans
Handling Complex Queries Weak—struggles with multi-join reordering or nested logic Strong—can optimize across joins, aggregations, and subqueries holistically

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

Aspect RBO CBO
Plan Generation Time Very low Higher—evaluates multiple alternatives
Memory Footprint Minimal Higher, especially in memoization-based optimizers
Explainability Easy to trace—rules are transparent Harder to debug—plans depend on opaque cost functions
Compile-Time Tuning Mostly fixed—minimal knobs Tunable—cost weights, plan shapes, join thresholds, etc.

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

Aspect RBO CBO
Requires Stats Maintenance? No Yes—must collect and update stats
Prone to Regressions from Stale Stats? No Yes—bad plans may result from outdated or skewed stats
Tuning Complexity Low—no knobs, just rule order High—many knobs, cost model tuning, stats sampling frequency
Operational Overhead Minimal Non-trivial in large data platforms

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

Dimension RBO CBO
Plan generation Fast, single-pass Slower, multi-path
Adaptivity Static Dynamic
Cost-awareness None Full
Statistics dependency No Required
Explainability High Medium/Low
Maintenance burden Low High
Optimization quality Low in complex queries High
Use case fit Embedded, static, legacy systems OLAP, lakehouse, SaaS, AI apps

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

Context Use RBO Avoid RBO
Lightweight, embedded systems
Legacy or safety-critical systems
Fixed schemas with predictable access
OLAP workloads with joins/aggregations
Ad hoc or dynamic queries
Multi-tenant SaaS analytics
Streaming or real-time analytics
Distributed query engines

 

Conclusion

Rule-Based Optimizers represent one of the earliest and most deterministic forms of query optimization. Unlike their cost-based counterparts, RBOs do not attempt to “model the world”—they apply a fixed set of syntactic and structural rules, resulting in predictable, low-overhead execution plans.

This predictability can be an asset or a liability, depending on the context. RBOs shine in resource-constrained environments, embedded systems, legacy applications, or static workloads—where performance consistency and plan transparency matter more than absolute query efficiency. But as query complexity, data volume, and workload variability increase, the absence of cost-awareness makes RBOs increasingly brittle and suboptimal.

Today, most modern database systems, including StarRocks, Trino, and CockroachDB, combine rule-based preprocessing with cost-based decision-making. Understanding how RBOs work—and when not to rely on them—is essential for database engineers, architects, and query practitioners navigating modern query engines, especially those balancing performance, scale, and governance.


FAQ: Rule-Based Optimizers


Q1. How is a Rule-Based Optimizer different from a Cost-Based Optimizer?

A Rule-Based Optimizer applies a fixed set of transformation rules to a query plan based on its syntactic and logical structure. It does not evaluate data statistics or execution cost. In contrast, a Cost-Based Optimizer uses statistics (e.g., row counts, cardinality, filter selectivity) to compare multiple physical plans and select the one with the lowest estimated cost.

Think of RBOs like a set of hard-coded traffic rules: always take the left fork if it’s available. CBOs are like GPS systems: they dynamically choose the route based on current traffic.

Q2. Does an RBO ever consider runtime statistics?

No. By definition, RBOs are completely statistics-blind. They don’t use:

  • Table sizes

  • Index selectivity

  • Join cardinalities

  • Runtime performance metrics

They are purely logical: they look at how a query is structured, not how much data it processes.

Q3. Are RBOs faster than CBOs?

Yes—in terms of plan generation time. Since RBOs do not model or compare multiple plans, they compile queries much faster. This makes them ideal for:

  • Environments with strict latency budgets (e.g., serverless query routing)

  • Use cases with high-frequency ad hoc query generation

  • Embedded engines with limited CPU/memory resources

However, the tradeoff is that execution time may suffer if the generated plan is suboptimal.

Q4. Why would anyone still use an RBO today?

Because determinism, simplicity, and zero-maintenance still matter:

  • In embedded databases (e.g., SQLite) where planning overhead must be negligible

  • In compliance-heavy environments where query plans must remain stable for auditing

  • In static workloads where queries and schemas rarely change

  • In educational tools or internal DSLs where plan visibility is more important than runtime efficiency

Q5. Can RBOs support complex SQL features like window functions, CTEs, and subqueries?

Support varies by implementation. Many older RBOs struggle with:

  • Inlining or flattening subqueries

  • Rewriting correlated subqueries into joins

  • Optimizing window function partitioning or sorting

Without a cost model to reason about intermediate result sizes or operator cost, RBOs may:

  • Apply rules in a non-optimal order

  • Fail to identify more efficient plan shapes

  • Leave query constructs unoptimized unless rewritten manually

Q6. How does rule ordering affect RBO output?

Significantly. Since RBOs don’t cost-evaluate multiple plans, the order in which rules are applied dictates the final plan. If a rule applies early (e.g., join reordering), it can prevent a later, better rule (e.g., predicate pushdown) from firing.

Well-designed RBOs use:

  • Phased rule groups (e.g., all pushdowns first, then joins)

  • Rule dependency graphs to prevent destructive rewrites

  • Manual hints or override mechanisms in edge cases

Poorly ordered rules can produce bloated, inefficient plans with unnecessary operations.

Q7. Can I use RBO and CBO together?

Yes—this is the default in many modern query engines.

Typical architecture:

  • RBO phase: apply low-risk, high-reward rewrites (e.g., pushdowns, constant folding, projection pruning)

  • CBO phase: evaluate full join graphs, parallel scan choices, data movement, sort strategies

For example, StarRocks performs:

  • Predicate pushdown and projection pruning (rule-based)

  • Join reordering and index selection (cost-based)

This hybrid approach combines the fast compile time and deterministic benefits of RBO with the adaptability and performance of CBO.

Q8. What are examples of real-world systems using RBOs?

  • SQLite: Uses a basic rule-based approach with limited join reordering and no statistics.

  • ClickHouse (early versions): Relied heavily on rule-based heuristics before introducing hybrid strategies.

  • CockroachDB: Uses a Cascades-style optimizer that expresses rewrites as rules, but applies them based on cost.

  • Presto/Trino: Uses transformation rules extensively for logical plan rewrites (e.g., pushdown, inlining) before costing.

  • StarRocks: Uses RBO for early-phase optimizations (e.g., materialized view rewrites) before invoking the CBO.

Q9. What are common pitfalls of relying on RBO?

  • Brittle performance: Plans don’t adapt to data growth or skew.

  • Manual query rewriting: Engineers often need to optimize SQL structure manually.

  • Poor join strategies: Without cost awareness, join order may increase intermediate result size drastically.

  • Incompatibility with federated or distributed systems: RBOs don’t model network cost or partition locality.

These pitfalls make RBO a poor fit for:

  • OLAP systems

  • Multi-tenant analytics

  • Streaming pipelines

  • AI model feature stores or lakehouse architectures

Q10. When should I avoid using RBO altogether?

Avoid RBOs if your system has:

  • High query complexity (e.g., star schemas, exploratory SQL)

  • Rapidly changing schemas or table sizes

  • Multi-join or subquery-heavy workloads

  • Unpredictable ad hoc query patterns

  • SLAs requiring cost-efficient execution across large volumes

In such environments, a cost-based optimizer is essential to maintain predictable performance and avoid regressions.