NEW THEORY (AT LEAST FOR ME!) OF TODAY !!

Database Systems & Architecture

Relational Query Optimization Theory

Query Equivalence & Cost-Based Search Space Exploration (Pioneered by System R)

Formalized in classic Database Systems Theory and implemented in Selinger's landmark System R optimizer architecture, relational query optimization solves a fundamental problem: translating declarative SQL queries into the most efficient physical access path without altering semantics.

PILLAR 1

Algebraic Query Equivalence & Search Space Construction

Core Focus: Similarity in Ways & Deterministic Output Equivalence

• Relational Algebra Equivalence Rules: Exploits commutative, associative, and distributive properties (e.g., pushing projections and selections down join trees) to generate structurally diverse yet semantically identical logical query plans.
• Physical Plan Enumeration: Mapping abstract operator nodes into concrete execution primitives (e.g., transform $R \bowtie S$ into physical options like Nested Loop Join, Hash Join, or Sort-Merge Join).
• System R Design Legacy: Restricting the search space to left-deep trees to minimize intermediate result pipelining costs while maintaining mathematical guarantee of semantic equivalence across execution options.

PILLAR 2

Cost-Based Search Space Exploration & Plan Variance

Core Focus: Performance Delta & Execution Skew Across Heterogeneous Access Paths

• Statistical Cost Metrics: Evaluating plan variants against catalog statistics (table cardinalities, column histograms, page counts) to predict physical execution latency and I/O overhead.
• Dynamic Programming (DP) Search Strategy: Bottom-up estimation of join orders to quickly prune sub-optimal plan trees based on intermediate result cost thresholds.
• System R Cost Equation Formula: Evaluates disk I/O and CPU computational overhead across competing physical operator paths:

$$\text{Cost} = \text{Page\_Fetch\_I/O} + (W \times \text{Tuple\_Instruction\_CPU})$$

Summary Protocol Query Optimization Theory bridges abstract mathematical query specs and physical database engine realities. By balancing algebraic equivalence generation (building the search space) with cost-based dynamic programming (pruning the search space), engines ensure maximum query execution performance with zero transactional output regression.

Deep Dive: System R & Modern Database Engine Theory

Granular Technical Components of Relational Query Optimization

Beyond High-Level Pillars: The Operational Mechanics of Cost-Based Optimizers

While query optimization is conceptually split into Search Space Generation and Cost-Based Evaluation, executing this process inside a production engine relies on six distinct, granular sub-systems and theoretical primitives.

1. Parser & Canonical Logical Operator Tree Construction

Before optimization begins, raw SQL statements undergo lexical analysis, parsing, and semantic validation.

• Abstract Syntax Tree (AST): Converts text into a tree structure representing SQL clauses.
• Catalog Metadata Binding: Resolves column/table identifiers, verifying types and schema permissions.
• Canonical Translation: Maps query syntax into standard Relational Algebra operators ($\sigma$ Select, $\pi$ Project, $\bowtie$ Join).

2. Heuristic Query Rewriting & Semantic Transformations

Applies rule-based equivalence transformations to simplify expressions prior to costly search space exploration.

• Predicate Pushdown: Moves selection operators ($\sigma$) below joins to filter rows as early as possible.
• Projection Pruning: Drops unreferenced columns ($\pi$) early to reduce buffer frame payload size.
• Subquery Unnesting & View Flattening: Converts correlated subqueries into equivalent join operators to unlock batch processing algorithms.

3. Physical Access Path & Operator Mapping

Translates logical algebra expressions into execution routines backed by actual storage structures.

• Table Traversal Algorithms: Chooses between Full Table Scans (Sequential I/O) and B+ Tree Index Range Scans (Random I/O).
• Physical Join Implementations: Selects algorithm based on data properties (e.g., Hash Join for unsorted inputs, Sort-Merge Join for pre-sorted indexed columns, Nested Loop Join for small datasets).
• Index-Only Scans: Utilizes covering indexes to satisfy queries entirely out of the RAM index buffer without touching heap pages.

4. Catalog Statistics & Selectivity Estimation Mechanics

Quantifies data volume and distribution to provide input variables for the optimizer's cost functions.

• Cardinality Estimation ($|R|$): Estimates the expected output row count of intermediate plan nodes.
• Selectivity Factors ($SF$): Calculates match probability for predicates using mathematical formulas:
  SF(col = val) = 1 / Distinct_Values(col)
• Data Density Modeling: Uses Equi-Depth Histograms, Equi-Width Histograms, and HyperLogLog counters to handle skewed data distributions.

5. Search Space Exploration Strategies

Algorithms used to navigate the combinatorial explosion of valid execution plans.

• System R Dynamic Programming (Bottom-Up): Builds $N$-way join plans incrementally from 1-table access paths, retaining only the cheapest sub-plans per subset.
• Volcano / Cascades Framework (Top-Down): Goal-driven, rule-based transformation search space navigation with memoization (used in modern optimizers like SQL Server).
• Genetic / Heuristic Algorithms: Applied when join counts exceed dynamic programming thresholds ($N > 10\text{--}12$ tables) to avoid $O(N!)$ or $O(3^N)$ plan space explosion.

6. Interesting Orders & Physical Property Propagation

A key innovation from Selinger's System R paper regarding physical layout properties.

• Definition: A plan property (e.g., output tuples sorted by a specific column due to an index scan or explicit sort).
• Optimization Impact: A plan node that appears more expensive in isolation may be retained if its "interesting order" eliminates a downstream ORDER BY, GROUP BY, or Sort-Merge Join sorting step.