Summary

  • The 1979 System R optimizer chose the lowest estimated-cost plan among the alternatives it considered. Its cost combined estimated page fetches and storage-interface calls; it did not measure elapsed time in advance or prove a global optimum over every imaginable plan.
  • Selectivity estimates feed cardinality estimates, which shape access-path, join-order and operator choices. “Interesting orders” explain why a locally more expensive path can be worth preserving when it avoids later sorting or helps another join.
  • Selinger organized a landmark team contribution with Morton Astrahan, Donald Chamberlin, Raymond Lorie and Thomas Price. Their most durable achievement was an explicit decision architecture whose assumptions could be tested, revised and monitored.

The plan does not exist yet when the promise is made

Consider a query that joins orders, customers and regions, filters for a recent period, groups by market and returns the ten largest totals. The relational result is defined by the query. A correct implementation must return the same qualifying rows and aggregates whether it scans a table, follows an index, joins customers first or postpones regions until the end.

The physical experience can be completely different. One route reads a narrow index, reaches a small set of rows and preserves an order useful for grouping. Another scans a large relation, generates an oversized intermediate result and sorts it after the join. Both routes may be semantically equivalent. Only one may be tolerable at production scale.

Before the first page is fetched, however, the database cannot observe the runtime of this particular execution. It must choose using descriptions: catalog statistics, predicate assumptions, operator formulas, hardware weights and a bounded search of alternatives. The optimizer's cheapest plan is therefore a forecast made under a model. Execution later supplies the verdict.

That distinction sounds obvious until operational language erases it. Teams say the optimizer “knows” a plan is cheapest. Dashboards label an estimated cost as if it were milliseconds. A regression is dismissed because the chosen plan has the lowest displayed number. Each formulation turns a comparative estimate into a fact about a future execution.

The original System R work is more careful than that folklore. It built a systematic way to choose while uncertainty remained, and its authors openly reported that absolute cost predictions could be inaccurate. The architecture is important precisely because it makes an uncertain choice explicit.

Declarative SQL created a new control problem

SQL's nonprocedural promise changes who selects the route. A user states what information is wanted without prescribing a sequence of storage operations. That separation improves portability and lets the database adapt as indexes, table sizes and distributions change. It also gives the optimizer authority over a decision with direct consequences for latency, capacity and reliability.

The 1979 paper, Access Path Selection in a Relational Database Management System, placed that authority inside a four-stage sequence. Parsing turned the statement into an internal representation. Optimization chose an access specification. Code generation translated that specification into executable machinery. Execution then ran it. The ordering is the central fact: optimization happens before the relevant run can reveal its actual resource use.

An access specification is not another statement of query meaning. It records physical choices. Which relation should be accessed first? Is a segment scan or an index appropriate? In what order should joins occur? Is an existing order valuable enough to preserve? Once code generation and execution proceed, those planning choices become real reads, calls, comparisons, buffers and intermediate rows.

Semantic correctness and physical economy consequently occupy different layers. A plan can be correct and slow. Two plans can be equally correct and have radically different costs. A fast result on one dataset does not establish that its plan is generally best. A mathematically lower estimate does not guarantee lower elapsed time under the next buffer state, parameter value or concurrent workload.

The catalog was a compressed view of reality

System R did not inspect every row while deciding how to inspect the rows. It used catalog statistics. The paper describes values such as NCARD, the number of tuples in a relation; TCARD, the number of pages occupied; P, a page-occupancy measure; ICARD, the number of distinct keys in an index; and NINDX, the number of index pages.

Those quantities supplied a compact description of the database. They also imposed a boundary. Statistics were initialized and periodically refreshed by an UPDATE STATISTICS operation. The authors explicitly rejected maintaining every statistic after every data modification because catalog updates and locking would add unacceptable cost.

The compromise is fundamental, not accidental. A planning summary must be cheap enough to maintain and rich enough to guide a choice. If it were a perfect, continuously synchronized copy of all relevant reality, acquiring it could cost more than the query decision it supports. If it is too coarse or stale, the plan can be misranked.

Modern terminology often treats “stale statistics” as a maintenance fault. Sometimes it is. But the deeper issue is economic: observation has a price. Systems decide what to sample, how often, at what granularity and with which assumptions. Every optimizer therefore sees a constructed picture of its data, not the data's complete future behavior.

Selectivity is a belief; cardinality is the consequence

For each predicate, System R assigned a selectivity factor: the expected fraction of tuples that would pass. An indexed equality could use the count of distinct index keys. Other predicates relied on simple defaults. The paper gives one tenth for an equality without an index, one third for an open-ended range and one quarter for a closed range, and says these numbers have no significance beyond rough ordering.

That sentence prevents a common historical mistake. The defaults were not discovered constants of databases. They were pragmatic beliefs used to rank alternatives when better evidence was unavailable.

Predicates combined with AND could multiply their selectivity factors. Multiplication is convenient, but it treats conditions as though their effects were independent. Real data often refuse that assumption. Postal code correlates with city; product line correlates with price; account type correlates with balance; date correlates with status. When correlated predicates are multiplied as independent filters, a modest selectivity error can become a large cardinality error.

Cardinality asks how many rows emerge from a relation, join or intermediate operator. The paper's simplified QCARD reasoning combines base-relation cardinalities and applicable selectivity factors. That row-count forecast then becomes an input to downstream cost formulas. Underestimate an early join and a nested-loop route can look inexpensive because the model imagines only a few outer rows. At runtime, thousands or millions may drive repeated work. Overestimate a filter and the optimizer can reject an index route that would in fact touch very little data.

Selectivity and cardinality are related but not interchangeable. Selectivity is a fraction or probability-like estimate. Cardinality is a count derived from it and from the size of the input. A one-percent error on a small table is minor; the same relative mistake propagated through several joins can reshape the entire physical plan.

Later evaluations have repeatedly returned to this point. Leis and coauthors found in 2015 that cardinality-estimation errors generally damaged plan quality more than small inaccuracies in cost formulas. Their 2025 retrospective describes cardinality estimation as a continuing source of instability and highlights robustness and adaptivity as unfinished work. That does not make the 1979 design obsolete. It shows where its decision chain remains most exposed.

Cost was a ranking currency, not a stopwatch

System R's published formula was concise:

COST = PAGE FETCHES + W × (RSI CALLS)

Page fetches represented I/O. Calls to the Research Storage Interface approximated processor work. The weight W expressed their relative price. This was a deliberate step beyond an I/O-only view: CPU work mattered too. Yet the result was still a model score.

The score combined unlike quantities through an assumed exchange rate. It could rank two candidates without predicting their elapsed time in seconds. It omitted or simplified effects that are difficult to know before execution: whether a needed page is already in memory, how sequential the reads will be, how much contention exists, whether an intermediate result spills, how the processor behaves, what another workload does to the cache, and how much data is eventually consumed by the client.

Calling the lower score “cheaper” is valid within the model. Calling it “faster” is a hypothesis. Calling it “optimal” requires two further qualifications: optimal according to which objective, and within which searched alternatives?

PostgreSQL's documentation preserves the same distinction in contemporary form. The planner's cost units are conventional and platform dependent; they are not milliseconds. Plain EXPLAIN shows estimates without running the statement. EXPLAIN ANALYZE executes it and adds actual row counts and timing. The pair is almost a laboratory demonstration of the boundary Selinger's architecture created: estimate first, observe later.

Access path, operator and join order are separate choices

The phrase “choose a plan” can hide several decisions.

An access path determines how a base relation is reached: for example, by scanning its pages or using an applicable index. A physical operator determines how work is performed: a particular join or sorting mechanism has its own input requirements and resource profile. Join order determines which relations are combined first and therefore the sizes and properties of intermediate results.

These decisions interact. An index can both filter rows and deliver a useful order. An early selective join may shrink the input to everything downstream. A join method that is excellent for a small outer input can be disastrous when the estimated cardinality is wrong. A sort inserted to satisfy one requirement can make a later step cheaper, while an order destroyed by an operator can force another sort.

Result correctness does not distinguish the alternatives. Relational equivalences let the optimizer transform a logical expression without changing its meaning, subject to the semantics of nulls, duplicates, aggregation and other language rules. Physical planning asks which equivalent realization should be used. Mixing the two questions produces bad diagnosis: a wrong answer is a correctness bug; a correct answer that arrives too late is a planning, estimation or execution problem.

Interesting orders preserved disciplined optionality

One of the paper's most durable ideas is the “interesting order.” Suppose an index path costs more than a scan for the immediate relation. If it returns tuples ordered on a join key, a grouping key or the query's final ORDER BY, it can avoid future sorting or enable a better downstream join. Discarding it because it is not locally cheapest would make the global plan worse.

System R therefore retained more than one winner for a partial result. It kept the cheapest unordered plan and the cheapest plan for each relevant interesting order. Plans that delivered the same subset of relations with the same useful ordering property formed a practical equivalence class for comparison.

This is not an exception to cost-based optimization. It is what makes the costing coherent across stages. The property carried by an intermediate result has option value. Paying more now can reduce later work. A plan score without physical properties would confuse immediate price with total consequence.

Interesting orders also sharpen the meaning of equivalence. Two partial plans can produce the same rows but not be substitutable at the same downstream cost. Their logical outputs match; their physical promises differ. The optimizer needs both views at once.

Join order made search itself expensive

With several relations, join order grows combinatorially. A naïve enumeration of every permutation approaches factorial growth. Optimization can then consume so much time and memory that saving execution time no longer justifies the search.

System R used dynamic programming. It built plans for subsets of relations, saved the best representatives for each subset and interesting order, and reused them when extending the join. A heuristic postponed Cartesian products unless required, because combining unrelated relations early normally creates large intermediate results.

The paper describes a search bounded in terms of relation subsets and interesting orders rather than every raw permutation and reports that eight-table joins could be optimized in seconds on an IBM 370/158. This was a remarkable engineering result. It was also a constraint. The optimizer deliberately defined which plan shapes and properties were candidates, which partial plans could be discarded and which were worth retaining.

Search-space pruning does not mean arbitrary guessing. It means solving a defined optimization problem within a tractable representation. Nor does dynamic programming prove a globally best plan across every operator, join tree, physical property and transformation a database designer could imagine. It identifies the best candidate under the enumerator, cost model and pruning rules actually implemented.

Optimization time and execution time therefore belong on the same ledger but remain different quantities. A larger search can find a better plan while delaying every query. A smaller search can produce an adequate plan quickly but miss a valuable alternative. Prepared statements add another layer: a generic plan can save repeated planning work yet perform poorly when the best route depends strongly on parameter values.

The authors did not hide the model's limits

The 1979 paper concludes that predicted costs were often inaccurate as absolute values. It also reports that the model selected the genuinely best tested access path in the majority of cases and calls for further validation. Those statements are compatible. Ranking can be useful even when calibration is imperfect, just as a weather forecast can order risks without specifying the exact minute rain will begin.

Mackert and Lohman's 1986 evaluation of the R* optimizer supplied the later empirical pressure. Estimated resources were compared with actual use. Much of the I/O modeling worked, but processor-cost detail needed improvement. Buffer assumptions mattered. Nested-loop costs were especially difficult because join cardinality, outer cardinality and available pages interacted.

The validation matters institutionally. A cost model is not protected by its mathematical appearance. It makes claims that can be compared with execution. Where discrepancies cluster, designers can improve statistics, formulas, operator assumptions or feedback. The estimate becomes governable because it is falsifiable.

IBM's later work on just-in-time statistics followed the same logic. When independently collected statistics are missing or stale, the optimizer can discover that it lacks a crucial observation and request targeted data at planning time. The response is not to pretend uncertainty has vanished. It is to buy better information where the expected planning benefit justifies the cost.

Patricia Selinger led a team architecture

Patricia G. Selinger joined IBM Research in 1975. IBM's history credits her with leading the System R optimizer work and later the R* distributed database effort; she became an IBM Fellow in 1994, was elected to the US National Academy of Engineering in 1999 and retired from IBM in 2018. Those honors reflect a substantial career beyond one paper.

The optimizer itself must be credited collectively. The 1979 paper was written by P. Griffiths Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie and Thomas G. Price. In his Computer History Museum oral history, Chamberlin recalls Selinger organizing the optimization work and the landmark paper while explicitly naming Lorie, Price and Astrahan as important contributors. IBM's broader history situates the work alongside Edgar Codd's relational model, the SQL work of Chamberlin and Raymond Boyce, Lorie's compiler work and a much larger System R program.

Leadership here did not mean solitary invention. Selinger's distinctive role was to organize an optimization problem into an implementable contract: inputs from statistics, candidate access paths, selectivity and cardinality estimates, a weighted cost, useful physical properties and a bounded enumeration procedure. The team turned declarative language from an elegant interface into something a general-purpose system could execute economically.

Calling that work “AI” would flatten its specificity. The paper describes explicit statistics, rules, formulas and dynamic programming. Its importance does not need a fashionable label. It created a durable control layer between what a query asks and how a machine attempts it.

The boundary survived because it was honest

Cost-based optimization is sometimes described as if its achievement were finding the one true route. The more consequential achievement is narrower and stronger: it separated meaning from method, made physical choices comparable, and preserved a place where new evidence could change the decision without changing the query.

The design survives because it expects revision. Statistics can become richer. Cardinality estimators can model correlations. Cost weights can adapt to hardware. Enumerators can admit new join shapes. Runtime feedback can trigger re-planning. None of those changes requires users to rewrite every declarative query into a physical program.

That adaptability depends on keeping the boundary clear. The chosen plan is an authorized forecast. It deserves execution because it won the implemented comparison, not because it has already been vindicated by reality. Once execution begins, actual rows, I/O, processor work, memory pressure and elapsed time become evidence. A mature system keeps both records and learns from the gap.

Sources