Skip to content

Query Optimization

Let the author state only what result a declarative query should return, then have a separate optimiser search the space of algebraically equivalent execution plans and emit the cheapest one under a cost model.

Core Idea

Query optimization is the database process that transforms a declarative query — what result is wanted, not how to compute it — into an execution plan chosen from a large space of algebraically equivalent candidates by a cost model. Its defining commitment separates specification from execution strategy: the author states logical intent in SQL, and a separate optimiser picks the physical procedure. Algebraic equivalence guarantees every candidate returns the identical relation, so the optimiser searches only for the cheapest.

Scope of Application

Lives wherever a declarative specification is rewritten over an algebraically-equivalent operator space against a cost model.

  • Relational SQL optimizers — the home: System R, Volcano/Cascades, PostgreSQL, Oracle, SQL Server, MySQL.
  • Stream-processing and big-data planners — Spark Catalyst, Flink, Trino/Presto over a different operator algebra.
  • GraphQL and federated-API engines — a request graph rewritten into upstream calls and joins, costed by call cost and cardinality.

Clarity

Naming query optimization makes a division of labor legible: the author owns logical intent, the optimiser owns the physical procedure, and the DBA tunes the statistics and indexes the optimiser reads. A slow query then localizes cleanly — is the query wrong, the plan poor, or the statistics stale? — and foregrounding algebraic equivalence draws a firm line between reorderings that preserve the result and changes that alter it.

Manages Complexity

A join over a handful of tables admits 10^k candidate plans once join orders, operator implementations, and access paths are crossed. The optimizer collapses that space to one emitted plan by treating the candidates as a single equivalence class searched against one scalar, estimated cost. Algebraic equivalence factors correctness out entirely, so "find a fast, correct procedure" reduces to "find the cheapest member of an already-correct set."

Abstract Reasoning

The construct licenses a three-input diagnostic that localizes a fault to the query, the plan, or the statistics, and a change-the-optimizer's-mind interventionist move that adjusts cost-model inputs rather than the SQL. A correctness-preservation boundary rests on algebraic equivalence, and a feasibility move reasons about the super-exponential plan space as one equivalence class searched against a single cost scalar, predicting that plan quality is bounded by estimate accuracy.

Knowledge Transfer

Within data systems it transfers as mechanism, unchanged across relational optimizers, stream planners, and federated-API engines, because each is the same substrate — a declarative spec rewritten over an equivalent operator algebra against a cost model. Beyond that cluster the content decomposes into parents that genuinely recur: optimization, planning, and especially the emergent equivalence_preserving_rewriting (shared with compilers and proof rewriting). What stays home is the relational furniture — algebraic rules, catalog statistics, plan cache — so reaching "query optimization" toward route-finding is a stretched analogy carrying only optimization plus planning.

Relationships to Other Abstractions

Local relationship map for Query OptimizationParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Query OptimizationDOMAINPrime abstraction: Optimization — is a kind ofOptimizationPRIME

Current abstraction Query Optimization Domain-specific

Parents (1) — more general patterns this builds on

  • Query Optimization is a kind of Optimization Prime

    Query Optimization is optimization specialized to selecting the least-cost execution plan from behaviorally equivalent relational-algebra rewrites under a database cost model.

Hierarchy path (1) — routes to 1 parentless root

Neighborhood in Abstraction Space

Query Optimization sits in a sparse region of the domain-specific corpus (75th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (309 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-07-12