In 1972, Edgar Frank “Ted” Codd published a paper called “Relational Completeness of Data Base Sublanguages” (External link), which established an equivalence in expressive power between relational calculus (External link) and relational algebra (External link). The theorem that he developed implied that there was a connection between the declarative representation of queries and their operational description, which opened the door to SQL as we know it.
The declarative nature of SQL, allowing a user to state what information they want to retrieve and not how to get it, enables a system to optimize how to retrieve and process the information the user is requesting.
Program synthesis
In computer science, there is a field called program synthesis (External link), which studies how to automatically generate a program given a formal specification; in other words, this field allows a user to create a program without actually coding it. This idea might remind us of the concepts of vibe coding (External link) or agentic engineering (External link), where the user might specify a program’s goal (or even structure) in natural language, although these might not exactly count as program synthesis since English is not a formal language. Nonetheless, as a formal language, SQL might be an example of how databases have been implementing program synthesis for a few decades.
The query optimizer
During the ’70s and ’80s, commercial databases that adopted SQL (or an SQL-like API) had to implement a query optimizer (External link) for the system to plan how to effectively (and efficiently) retrieve the data that the user asked for.
The first approach was to use rule-based optimization (External link), allowing the system to design a query execution plan based on a set of rules, such as whether the data to be retrieved had an index, but not accounting for any current state of the database or the data layout. A few years after Ted Codd published his papers justifying his theorem and the proposal for the relational data model, the research division at IBM started developing System R as a relational database. One of the innovations of System R was the implementation of a cost-based optimizer (External link), developed by Patricia Selinger et al. (External link).
System R’s cost-based optimizer has come to be considered a framework known as the bible of query optimization. This framework uses catalog stats to find the least-cost plan per query block. The idea is that since each block of a query can be converted to relational algebra, and each operator has different implementation options, operators can be applied in different orders.
There are three main components of a cost-based query optimizer:
- The plan space, which analyzes the possible ways to implement a query.
- The cost estimation, which analyzes the cost of a particular plan.
- The search strategy, which aims to answer the question: given that we have a plan space, how do we efficiently find a plan with the cheapest cost estimate?
Search problems
While there are many foundations of AI, search algorithms (External link) allow systems to find solutions by exploring paths and traversing states in a problem space. Databases that implement a cost-based optimizer implement these search algorithms as part of their search strategy, exploring the different plans of the plan space while trying to find the cheapest path to run a query. And because the plan space might grow exponentially depending on the complexity of a query, modern databases and optimizers also implement the use of heuristic pruning (External link) to avoid an exhaustive search of the plan space.
Query optimizers are the magic that allows for databases to translate a formal language such as SQL into a complete data description and manipulation program. The long-standing objective of databases has been to retrieve data and apply operators on said data efficiently, and this objective has driven innovations that incorporate research from other areas of computre science, serving as an example of collaboration across fields.