- Atlas
- Computer Science
- Query Processing
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
- Rule-based query optimization 1975-1990
- Cost-based query optimization 1979-Present
- Parallel and distributed query processing 1980-Present
- Physical operator and access-method design 1980-Present
- Parallel Query Processing 1985-Present
- Extensible optimizer architectures 1990-Present
- Adaptive query processing 2000-Present
- Vectorized and compiled execution 2005-Present
- Compiled Query Execution 2011-Present
- Learned query optimization 2017-Present
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
- Database (introduction, Terminology, 1970s, relational DBMS, Late 1970s, SQL DBMS, Miscellaneous features), Wikipedia
- Query plan, Wikipedia
- Relational model, Wikipedia
- Relational database (History), Wikipedia
- IBM System R, Wikipedia
- Query optimization, Wikipedia
- Query rewriting, Wikipedia
- Nested loop join, Wikipedia
- 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.
- 1975-1990
Rule-based query optimization
Which heuristic rules rewrite a query into a better plan?
- 1979-Present
Cost-based query optimization
Which plan among alternatives has the lowest estimated cost?
- 1980-Present
Parallel and distributed query processing
How do we split a query across many machines?
- 1980-Present
Physical operator and access-method design
What algorithms and access paths should execute each operation?
- 1985-Present
Parallel Query Processing
How do we partition data and fragment plans for parallel execution?
- 1990-Present
Extensible optimizer architectures
How can new operators and rules be added without rewriting the optimizer?
- 2000-Present
Adaptive query processing
How should a plan change when runtime estimates prove wrong?
- 2005-Present
Vectorized and compiled execution
How do we process tuples in batches to use hardware well?
- 2011-Present
Compiled Query Execution
How do we generate machine code for a query plan?
- 2017-Present
Learned query optimization
Can a system learn from data to choose better plans?
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.
Cost-based query optimization replaced Rule-based query optimization
System R's cost-based optimizer, described by Patricia Selinger and colleagues in 1979, replaced the heuristic rule-based approach of Ingres as the dominant paradigm. Cost-based optimization kept relational-algebra rewrite rules but added statistics-driven plan enumeration and cost comparison.
Carried by Patricia Selinger; Access Path Selection in a Relational Database Management System (1979).
Extensible optimizer architectures grew out of Cost-based query optimization
The Volcano Optimizer Generator and Cascades framework by Goetz Graefe generalized cost-based optimization into an extensible architecture where operators, rules and cost functions could be registered. It separated the search strategy and cost model from hard-coded built-in types.
Carried by Goetz Graefe; The Volcano Optimizer Generator (1993).
Adaptive query processing reacted against Cost-based query optimization
Adaptive query processing arose because cost-based optimization's static estimates often failed on skewed or unpredictable data. Mid-query re-optimization and eddy operators changed plans at runtime rather than trusting the optimizer's upfront cost model.
Carried by Ron Avnur; Joseph M. Hellerstein; Eddies: Continuously Adaptive Query Processing (2000).
Learned query optimization reacted against Cost-based query optimization
Learned query optimization replaced or augmented hand-crafted cost models and cardinality estimators with machine-learning models trained on query execution data. The approach defined itself against the inaccuracy of traditional cost-based estimation.
Vectorized and compiled execution grew out of Physical operator and access-method design
Vectorized execution redesigned physical operators to process batches of tuples rather than one at a time, amortizing per-tuple overhead and improving cache behavior. MonetDB and later Vectorwise built on decades of physical operator and access-method design.
Carried by Peter Boncz; Marcin Zukowski; MonetDB/X100 (2005).
Compiled Query Execution grew out of Physical operator and access-method design
Compiled query execution generated machine code for physical operators, eliminating interpretation overhead in the Volcano iterator model. HyPer's compilation approach built directly on the operator design tradition.
Carried by Thomas Neumann; Efficiently Compiling Efficient Query Plans for Modern Hardware (2011).
Compiled Query Execution rival of Vectorized and compiled execution
Vectorized execution and compiled execution were contemporary alternatives for overcoming tuple-at-a-time overhead, competing to answer how to exploit modern hardware. Systems adopted one or the other, and later engines sometimes combined both.
Carried by Marcin Zukowski; Thomas Neumann.
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.
Cost-based query optimization influenced by Dynamic Programming in Operations Research
Cost-based query optimizers used dynamic programming to enumerate join orders, directly adapting the technique from operations research. The System R optimizer's bottom-up dynamic programming over join subplans is the canonical case.
Carried by Patricia G. Selinger; System R (1979).
Cost-based query optimization grew out of Query optimization in Database Theory
Cost-based query optimization is a refinement of query optimization, using statistics and cost models to choose among plans. It grew directly out of the earlier plan-selection problem, notably in System R.
Carried by Patricia Selinger; Access Path Selection in a Relational Database Management System (1979).
Cost-based query optimization led to Distributed Query Processing in Distributed Databases
Distributed query processing adopted cost-based optimization and extended the cost model to include network transmission and site-local processing. The optimizer chose among distributed plans using the same cost-driven search.
Physical operator and access-method design influenced by Relational model in Database Theory
Physical operator and access-method design implemented the relational model's operators, taking Codd's relational algebra as the specification of what operators such as join, select, and project must compute. Access methods were designed to realize these relational operations efficiently.
Carried by Edgar F. Codd.
Parallel Query Processing grew out of Distributed Query Processing in Distributed Databases
Parallel query processing grew directly out of distributed query processing, generalizing its techniques for fragmenting, shipping, and scheduling query execution across nodes to tightly coupled parallel machines. The same operator and scheduling ideas were carried over.
Adaptive query processing grew out of Query optimization in Database Theory
Adaptive query processing grew out of classical query optimization, keeping its cost-model and plan-space framing while adding runtime re-optimization and adaptive operators. The eddies and adaptive-query-processing work of the early 2000s was defined against the static plans produced by optimizers like System R's.
Carried by Ron Avnur; Joseph M. Hellerstein.
Adaptive query processing grew out of Query optimization in Databases
Adaptive query processing took the cost-based optimization problem from database query optimization and made plan choice a runtime rather than compile-time activity. The static optimizer's limitations under uncertain cardinalities were the explicit motivation for adaptive techniques.
Carried by Joseph M. Hellerstein; Ron Avnur.
Vectorized and compiled execution influenced by Vector processor in Parallel Computing
Vectorized query execution borrowed the core idea of the vector processor: operating on batches of values with a single instruction to amortize per-element overhead. MonetDB/X100 explicitly drew on vector processing principles when it introduced vectorized execution for databases.
Carried by Marcin Zukowski; Peter Boncz.
Vectorized and compiled execution influenced by Vector processor in Instruction Set Architecture
Vectorized execution in databases is directly modeled on SIMD vector instruction sets, processing tuples in batches to exploit wide registers and reduce interpretation overhead. The X100 work framed its execution model in terms of vector instructions.
Carried by Marcin Zukowski; Peter Boncz.
Compiled Query Execution influenced by Compilation and implementation in Programming Languages
Compiled query execution applies compiler construction techniques, generating native code for query pipelines instead of interpreting plans. The work on compilation and implementation, including code generation and data representation, is the direct source of these methods.
Carried by Thomas Neumann.
Learned query optimization grew out of Query optimization in Database Theory
Learned query optimization replaces or augments the cost models and plan search of classical query optimization with learned models, taking the optimization problem as its target. The learned-optimizer work is explicitly framed as improving on cost-based optimization.
Learned query optimization grew out of Query optimization in Databases
Learned query optimization grew out of database query optimization, using its plan spaces, cardinality estimation problems and cost models as the object of learning. The work is a direct extension of the optimizer's components with machine learning.

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 ProcessingRelated fields
Fields its ideas are linked to
- Database Theory 7 links
- Parallel Algorithms 5 links
- Compiler Design 5 links
- Big Data Processing 4 links
- Databases 3 links
- Computer Systems 3 links
- Distributed Databases 2 links
- Operations Research 2 links
- Algorithms 1 link
- Randomized Algorithms 1 link
- Instruction Set Architecture 1 link
- Parallel Computing 1 link
More in Databases
See where Query Processing sits on the Map of Human Knowledge