Querying and performance: SQL, query plans and physical design

This third unit asks what it costs to read a schema back. A query language makes a promise: state the question, not the route to the answer. The user names columns and joins tables, and never says which index to use or in what order to combine them. That separation is the declarative contract.

The promise, this lecture argues, is real but partial. The language fixes what can be asked, the plan the engine builds fixes what asking costs, and the plan rests on estimates that are routinely wrong.

The contract fixes what can be asked, not what it costs

Chamberlin and Boyce (1974) set out the contract. SEQUEL identifies simple operations on tabular structures without bound variables or quantifiers. It is shown equivalent in power to the first-order predicate calculus, and it gives the user keyword English templates that reflect how people read tables and assume a reader at home in English. The language fixes what can be asked and leaves how it is answered to the system.

Syntax was a choice, not a consequence of the model. Zloof (1977) presents Query-by-Example, whose distinguishing feature is that very few concepts must be learned before the system can be used. The query is written by filling in example tables rather than composing clauses. Two systems can share a data model and still disagree about how a question should be posed.

The contract has since been stretched across data models. Meijer, Beckman and Bierman (2006) describe LINQ, which defines standard query operators for traversal, filter and projection. It lets a language query objects, relational data and XML in one syntax.

Expressiveness carries a price, and Perez, Arenas and Gutierrez (2009) make it explicit for a graph model. They give a compositional semantics for the core of SPARQL. Their complexity study shows general SPARQL pattern evaluation is PSPACE-complete, while a natural syntactic restriction yields well-designed patterns, whose evaluation is coNP-complete. Querying a graph moves the cost from the join to the pattern match, so a language that can pose questions the relational model cannot must have its evaluation optimised rather than assumed cheap.

The plan is where the cost is decided

The hinge of the unit is the query plan. Selinger and colleagues (1979) describe how System R chooses access paths for simple and complex queries. The user supplies a non-procedural specification of the wanted data as a boolean expression of predicates, and no reference to any access path. That is the origin of cost-based planning. The user supplies predicates, the system supplies a plan, and the plan decides whether the question is answered in milliseconds or in minutes.

Ask for the orders of a single customer from a table of a million rows. Without an index the engine reads every page of the table and discards almost all of it. With an index on the customer column it reads a few pages of the index and then the matching rows. The same question, at two orders of cost, decided by the structures the designer built. The example is a textbook shape rather than a measurement. It is the shape Selinger and colleagues (1979) formalise, in which the plan and not the question fixes the cost.

Chaudhuri (1998) supplies the vocabulary, separating the search space, the cost model and the cardinality estimate in a deliberately incomplete overview of query optimisation. Graefe (1993) shows what a plan chooses among, arguing that object-oriented and extensible systems make the problem harder rather than easier. A plan is a choice among procedures whose cost depends on how many rows each stage will see.

The estimates the plan rests on are routinely wrong

Whether the choice is good depends on the numbers behind it, and the evidence is hostile. Leis and colleagues (2015) build the Join Order Benchmark on a complex real-world dataset and a set of realistic multi-join queries, and find that industrial-strength cardinality estimators routinely produce large errors. The cost model has far less influence on performance than the cardinality estimates have, and exhaustive enumeration of join orders still beat the heuristics despite those bad estimates. What the study does not show is what a designer working with a fixed access path would achieve. It measures the optimiser's internals rather than the designer's alternative.

Read against Selinger and colleagues (1979), that is uncomfortable rather than fatal. What fails is the assumption that the choice is competent because it is systematic. The decisive input is the least reliable one, and the engine does not advertise its error.

Physical design fixes what is cheap

If the route is the optimiser's business, physical design still falls on the designer. Comer (1979) reviews B-trees, explains why they became the de facto standard for file organisation, and contrasts the major variations, especially the B+-tree. The structure decides which access patterns are cheap. An equality lookup and a range scan are cheap, while needing the rows in another order pays for a sort.

The choice is a trade rather than a ranking. O'Neil and colleagues (1996) introduce the log-structured merge-tree, which defers and batches index changes and cascades them from a memory component through disk components. It greatly reduces disk arm movements relative to a B-tree, but it costs finds that need an immediate response, so it suits workloads where inserts outnumber finds. A structure that makes writes cheap makes some reads expensive, so the index follows the access pattern.

Even the headline comparison hides the mechanism. Abadi, Madden and Hachem (2008) examine how different column-stores really are from row-stores. They argue that reading fewer attributes is not the whole story, and that compression and late materialisation account for much of the speed-up.

Contested question: can the engine be trusted with the choice?

The literature disagrees about what the separation is worth.

One position treats the separation as the achievement. Chamberlin and Boyce (1974) design a language in which the user never names a route. Selinger and colleagues (1979) build the machinery that lets the system choose one, and Meijer, Beckman and Bierman (2006) carry the separation across data models. On this view, asking the user to manage access paths is the error the relational systems were built to fix.

The opposing position holds that the abstraction leaks, and that the leak is where the time is spent. Leis and colleagues (2015) show the estimate the plan depends on is routinely wrong. Graefe (1993) shows the procedures a plan chooses among are complex enough that the choice matters as the data grows. Abadi, Madden and Hachem (2008) show the storage model's slogan does not explain the performance the model is credited with. On this view, the user who ignores the plan relies on a promise the system cannot keep.

A second axis is what the contract should be. Zloof (1977) offers a two-dimensional interface, and Perez, Arenas and Gutierrez (2009) show that another contract buys expressiveness at a cost in evaluation complexity.

What would settle it is a measurement that separates the sources of cost. The decisive study would run the same queries over the same data twice. The first run leaves the optimiser free to choose from whatever structures exist. The second fixes access paths by a designer who has read the workload. If the fixed design is not reliably better, the separation is a virtue the engine honours. If it is better, the separation is a promise the estimates break.

Rate each side by its evidence. Chamberlin and Boyce (1974) and Selinger and colleagues (1979) describe systems, so the separation side rests on a design rather than a measurement. Leis and colleagues (2015) measure the optimiser's own error, the sharpest evidence here, and Abadi, Madden and Hachem (2008) measure where a headline comparison hides its mechanism. The strongest objection is that the separation is what makes a query portable, so a designer who fixes access paths takes on maintenance the language was built to remove. While the dispute is open, a designer reads the plan for the queries that matter and records the estimate it rested on.

Where the argument is heading

The named work points to the boundary between logical and physical design being redrawn rather than removed. Kraska and colleagues (2018) argue that indexes are models, a B-tree mapping a key to a position and a hash index modelling membership. They posit that learned models, including deep networks, can replace index structures, analysing the conditions and reporting initial results in their favour. If an index is a fitted model, physical design becomes a question about how well the model was trained.

That prospect inherits the unit's problem. Leis and colleagues (2025) revisit that benchmark a decade on and report that the cardinality errors still dominate poor plans, naming robustness and adaptive execution as the open problems. A learned model making the choices is therefore answerable to the same question: who is accountable when the model is wrong? Abadi, Madden and Hachem (2008) supply the warning, because a headline comparison, learned against classic, usually hides the mechanism that produces the difference. The question to hold is whether the designs that make a system fast can be made legible to whoever maintains them.

The sources this unit rests on

• Abadi, D. J., Madden, S. R. and Hachem, N. (2008). The authors examine how different column-stores really are from row-stores, arguing that reading fewer attributes is not the whole story and that compression and late materialisation account for much of the analytical speed-up. It carries the claim that physical layout is a first-class decision whose consequences the storage-model slogan hides.
• Chamberlin, D. D. and Boyce, R. F. (1974). The authors present SEQUEL, identifying simple operations on tables equivalent in power to the first-order predicate calculus, with keyword templates that reflect how people read tables. It carries the origin of the declarative contract: the language fixes what can be asked, not how the answer is found. It proposes a language rather than reporting a measured outcome. ACM records this DOI against SIGFIDET 1974, pages 249 to 264, where the DOI registrar's deposit still names the 1976 workshop.
• Chaudhuri, S. (1998). Chaudhuri gives a deliberately incomplete overview of query optimisation in relational systems, concentrating on SQL and explaining the foundations with samples of significant work. It supplies the vocabulary of search space, cost model and cardinality estimate that the unit's evidence later attacks. It frames the components rather than testing them.
• Comer, D. (1979). Comer reviews B-trees, explains why they became the de facto standard for file organisation, and discusses the major variations, especially the B+-tree, contrasting their merits and costs. It carries the physical-design half of the unit: the index structure decides which access patterns are cheap. It surveys structures rather than benchmarking them.
• Graefe, G. (1993). Graefe surveys the algorithms and architectural issues of query evaluation over large data volumes, arguing that object-oriented and extensible systems make the problem harder rather than easier. It shows the operations a plan chooses among, and why the choice matters as the data grows. It organises the field rather than reporting one result.
• Kraska, T., Beutel, A., Chi, E. H. et al. (2018). The authors argue that indexes are models, a B-tree mapping a key to a position and a hash index modelling membership, and posit that learned models including deep networks can replace index structures, analysing the conditions and reporting initial results. It reopens index design and shows where the physical-design argument has moved. It is exploratory, opening a line of work.
• Leis, V., Gubichev, A., Mirchev, A. et al. (2015). The authors introduce the Join Order Benchmark and revisit the classic optimiser on a complex real-world dataset and realistic multi-join queries, finding that industrial-strength cardinality estimators routinely produce large errors. It carries the unit's central evidence: the decisive input to the plan is the least reliable one. It measures optimiser internals rather than the designer's alternative.
• Leis, V., Gubichev, A., Mirchev, A. et al. (2025). Revisiting their 2015 benchmark, the authors report that cardinality-estimation errors remain the dominant cause of poor plans, and set the field's open problems as robustness and adaptive execution. It is a retrospective on their own experiment rather than a new measurement.
• Meijer, E., Beckman, B. and Bierman, G. (2006). The authors describe LINQ, which defines standard query operators for traversal, filter and projection so that a language can query objects, relational data and XML in one syntax. It shows the query contract being extended across data models, the pressure that later pushes SQL to absorb object and document features. It describes a framework rather than measuring it.
• O'Neil, P., Cheng, E., Gawlick, D. et al. (1996). The authors introduce the log-structured merge-tree, which defers and batches index changes and cascades them from a memory component through disk components, greatly reducing disk arm movements compared with a B-tree. Index choice trades read cost against write cost, so physical design follows the access pattern. Its stated limit: finds needing an immediate response lose I/O efficiency, so the structure suits workloads where inserts outnumber finds. The publisher abstract was read; no index carried it.
• Perez, J., Arenas, M. and Gutierrez, C. (2009). The authors give a compositional semantics for the core of SPARQL and study the complexity of evaluating several fragments, showing general SPARQL pattern evaluation is PSPACE-complete and identifying well-designed patterns, whose evaluation is coNP-complete. It puts a cost on graph query, so graph query is not a free replacement for SQL. It is a complexity result rather than an execution measurement.
• Selinger, P. G., Astrahan, M. M., Chamberlin, D. D. et al. (1979). The authors describe how System R chooses access paths for simple and complex queries, given a user's non-procedural specification of the wanted data as a boolean expression of predicates. It is the origin of cost-based planning and carries the unit's hinge: the user declares a question and the system picks the plan. It is a system description, establishing the mechanism rather than evaluating it.
• Zloof, M. M. (1977). Zloof presents Query-by-Example, a language for retrieval, manipulation and definition whose distinguishing feature is that very few concepts need be learned before the system can be used. It shows the query contract can be expressed visually, so syntax is a design choice rather than a consequence of the model. It argues for the interface rather than comparing it experimentally.