Query Processing

Query Processing A database management system (DBMS) stores data and answers questions about it.

10 frameworks, from 1975 to today · Databases · Computer Science

still a working view ended · each leads to its entry below

Overview

Query Processing

A database management system (DBMS) stores data and answers questions about it1. Query processing is the part of the system that turns a user's question—typically written in SQL—into a concrete plan for finding the answer, and then executes that plan12. The user says what they want; query processing decides how to get it. That gap is where the field lives. A single SQL query can often be executed in thousands of different ways, and the difference between a good plan and a bad one can be seconds versus hours. The history of query processing is the history of closing that gap: first by giving the system rules to follow, then by teaching it to estimate costs, then by making it adapt when estimates are wrong, and most recently by letting it learn from data.

Early Relational Systems and the Case for Declarative Queries

When Edgar F. Codd proposed the relational model in 1970, he described data as tables and gave a relational algebra for querying them. The model's radical promise was data independence: users would describe results declaratively, and the system would handle storage and access13. But early relational prototypes in the 1970s—IBM's System R and the University of California's Ingres—faced a practical problem145. A declarative query says nothing about how to execute it. The system had to choose among access paths (which index to use, whether to scan a whole table), join orders, and join algorithms. Without a systematic method, performance was unpredictable.

The answer was the query optimizer: a component that rewrites a query into an efficient execution plan before running it16. System R, described in a landmark 1979 paper by Patricia Selinger and colleagues, introduced cost-based optimization. The optimizer enumerated alternative plans, estimated each plan's cost using statistics about the data (such as the number of distinct values in a column), and chose the cheapest. The key insight was that cost estimates could be derived from catalog statistics and simple models of I/O and CPU. System R also introduced the idea of interesting orders—plans that produce sorted output can make later operations cheaper—and used dynamic programming to search join orders efficiently.

Ingres took a different path. Its optimizer was rule-based: it applied heuristic rules, such as "perform selections as early as possible" and "avoid Cartesian products," to transform a query tree into a better one. These rules were grounded in relational algebra equivalences—for example, pushing a selection below a join is always semantically valid17. Rule-based optimization was simpler and required no statistics, but it could not distinguish between two valid plans of very different cost. The competition between rule-based and cost-based approaches shaped the next decade.

Cost Models, Join Algorithms, and Physical Design

Through the 1980s, cost-based optimization became the dominant paradigm, and researchers focused on the components it required. Join algorithms were a central concern. The nested-loop join (for each row of one table, scan the other) is simple but slow for large inputs8. The sort-merge join sorts both inputs and merges them, which is efficient when inputs are already sorted or when indexes exist9. The hash join, developed in the late 1970s and early 1980s, builds a hash table on one input and probes it with the other, giving near-linear performance for equi-joins. Each algorithm has different cost characteristics depending on data size, memory, and the presence of indexes, and the optimizer's job was to choose among them.

Physical operator and access-method design became a subfield in its own right. A physical operator is a concrete algorithm for a relational operation (a hash join, an index scan, a sort). An access method is a way of retrieving tuples from a table (a sequential scan, a B-tree index lookup, a bitmap index). The optimizer's search space is the cross-product of these choices, and the cost model must estimate each one accurately. The 1980s and 1990s saw steady refinement: better selectivity estimation (the fraction of rows a predicate passes), histograms to capture data distribution, and techniques for estimating the cost of complex predicates.

Extensible Optimizers and the Object-Relational Turn

By the late 1980s, relational systems were being asked to handle new data types—images, text, spatial data, user-defined functions—that the original cost model did not anticipate. A monolithic optimizer with hard-coded rules for built-in types could not keep up. The response was the extensible optimizer: an architecture in which new operators, access methods, and cost functions could be registered with the system. The Volcano project at the University of Colorado, led by Goetz Graefe in the early 1990s, introduced an extensible optimizer generator called the Volcano Optimizer Generator, and later the Cascades framework, which used a rule-based transformation engine to explore plan alternatives. Commercial systems followed: IBM's DB2 and Microsoft's SQL Server added extensibility interfaces. The idea was that the optimizer's search strategy and cost model could be separated from the specific operators and rules, allowing the system to grow without rewriting its core.

Parallel and Distributed Query Processing

As data volumes grew, a single machine could no longer hold or process large tables. Parallel query processing split a query's work across multiple processors or nodes. The key challenges were data partitioning (how to divide tables so that joins and aggregations can be done locally), plan fragmentation (splitting a query plan into pieces that run on different nodes), and exchange operators (mechanisms for moving data between nodes, such as repartitioning or broadcasting). The Gamma project at the University of Wisconsin in the 1980s demonstrated parallel database machines using hash-based partitioning and join algorithms. In the 1990s and 2000s, commercial parallel databases such as Teradata and IBM's DB2 Parallel Edition brought these ideas to data warehouses.

Distributed query processing extended this to geographically separated sites, where network latency and failure become first-order concerns. The optimizer must decide not only which algorithms to use but also where to execute each step and how much data to ship. Semijoin techniques—sending only the join keys rather than full tuples—were developed to reduce network traffic. The rise of large-scale data processing frameworks in the 2000s, such as MapReduce and later Apache Spark, brought a new style of distributed query processing: users wrote programs that the framework parallelized, and optimizers (such as Spark's Catalyst) applied rule-based and cost-based transformations to those programs. The boundary between database query processing and general-purpose data processing blurred.

Vectorized and Compiled Execution

Traditional query engines used a tuple-at-a-time (Volcano-style) iterator model: each operator pulls one tuple from its child, processes it, and passes it up. This model is flexible but incurs high per-tuple overhead from virtual function calls and interpretation. In the 2000s, two alternative execution strategies gained traction. Vectorized execution, pioneered by MonetDB and later adopted by systems such as Vectorwise and DuckDB, processes batches of tuples (vectors) at a time, amortizing overhead and improving CPU cache behavior. Compiled execution, explored in systems such as HyPer (later part of Tableau) and later in Apache Spark's Tungsten engine, generates machine code for a query plan, eliminating interpretation entirely. Both approaches exploit modern hardware—large caches, SIMD instructions, multiple cores—far better than tuple-at-a-time execution. The result was order-of-magnitude speedups for analytical workloads, and these techniques are now standard in both commercial and open-source systems.

Adaptive Query Processing

Cost-based optimization assumes that statistics are accurate and that cost models reflect reality. In practice, both assumptions often fail: statistics go stale, correlations between columns are missed, and cost models misestimate the cost of complex operators. Adaptive query processing (AQP) responds by changing the plan at runtime. Early work in the 1990s and 2000s explored mid-query re-optimization (re-planning after observing actual cardinalities), parametric query optimization (precomputing plans for a range of parameter values), and eddy operators (which route tuples dynamically through a set of operators, learning which order is best). More recent systems use adaptive operators that can switch algorithms mid-execution—for example, a join that starts as a nested-loop join and switches to a hash join if the input turns out to be large. AQP is particularly valuable in environments where data distribution is skewed or unpredictable, such as data lakes and federated systems.

Learned Query Optimization

The most recent turn applies machine learning to the optimizer itself. Traditional cost models are hand-crafted approximations; learned query optimization replaces or augments them with models trained on data. One line of work learns cardinality estimation—predicting how many rows a predicate will pass—using neural networks or other models trained on query execution feedback. Another line learns plan cost models directly from observed execution times, bypassing the need for explicit cost formulas. A third line uses reinforcement learning to choose join orders or physical operators. Systems such as Bao (learned query optimization for commercial databases) and Neo (a learned optimizer for PostgreSQL) demonstrated that learned components can outperform traditional heuristics on some workloads. The field is still young, and challenges remain: training data is scarce, models can be brittle, and integrating learned components into existing optimizers is non-trivial. But the direction is clear: the optimizer is becoming a learning system rather than a hand-tuned one.

The Present: Hybrid Systems and Open Questions

Today's query processors combine all of these strands. A modern analytical database might use a cost-based optimizer with extensible rules, vectorized or compiled execution, adaptive operators for skewed data, and learned cardinality estimates. Cloud data warehouses such as Snowflake and BigQuery separate storage from compute, which changes the cost model (network and storage costs matter as much as CPU). Streaming systems process queries continuously over unbounded data, requiring new models for time and state. The open questions are substantial: how to make learned optimizers robust and explainable; how to optimize queries across heterogeneous data sources (files, APIs, databases); how to handle the extreme skew and schema variability of data lakes; and how to design optimizers that work well without detailed statistics, as is often the case in federated or serverless environments. The history of query processing is a history of making declarative questions answerable efficiently, and that work continues.

References

  1. Database (introduction, Terminology, 1970s, relational DBMS, Late 1970s, SQL DBMS, Miscellaneous features), Wikipedia
  2. Query plan, Wikipedia
  3. Relational model, Wikipedia
  4. Relational database (History), Wikipedia
  5. IBM System R, Wikipedia
  6. Query optimization, Wikipedia
  7. Query rewriting, Wikipedia
  8. Nested loop join, Wikipedia
  9. Sort-merge join, Wikipedia

The frameworks of Query Processing

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1975-1990

    Rule-based query optimization

    Which heuristic rules rewrite a query into a better plan?

    Fly to its tower in Nousfarer

  2. 1979-Present

    Cost-based query optimization

    Which plan among alternatives has the lowest estimated cost?

    Fly to its tower in Nousfarer

  3. 1980-Present
  4. 1980-Present

    Physical operator and access-method design

    What algorithms and access paths should execute each operation?

    Fly to its tower in Nousfarer

  5. 1985-Present

    Parallel Query Processing

    How do we partition data and fragment plans for parallel execution?

    Fly to its tower in Nousfarer

  6. 1990-Present

    Extensible optimizer architectures

    How can new operators and rules be added without rewriting the optimizer?

    Fly to its tower in Nousfarer

  7. 2000-Present

    Adaptive query processing

    How should a plan change when runtime estimates prove wrong?

    Fly to its tower in Nousfarer

  8. 2005-Present

    Vectorized and compiled execution

    How do we process tuples in batches to use hardware well?

    Fly to its tower in Nousfarer

  9. 2011-Present

    Compiled Query Execution

    How do we generate machine code for a query plan?

    Fly to its tower in Nousfarer

  10. 2017-Present

    Learned query optimization

    Can a system learn from data to choose better plans?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Rule-based query optimizationCost-based query optimizationParallel and distributed query proces…Physical operator and access-method d…Parallel Query ProcessingExtensible optimizer architecturesAdaptive query processingVectorized and compiled executionCompiled Query ExecutionLearned query optimization

Beyond the field

Where Query Processing's ideas came from in other fields, and what they led to there: the strongest 12 of 36 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Query Processing is a planet in Nousfarer

Its city has a tower for each of these 10 frameworks. Land, walk in, and climb one concept at a time.

Land on Query Processing

Related fields

Fields its ideas are linked to

More in Databases

See where Query Processing sits on the Map of Human Knowledge