
A Practical Guide to 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 aScan
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)
toa != 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.