Retrospection on a Database System

In one breath — the whole paper, compressed

INGRES was one of the first relational database systems that really ran, and this paper is Stonebraker's account of what it actually took to build it at Berkeley between 1973 and 1979. It traces three phases -- design seminars, a first implementation demonstrated to Ted Codd in barely working shape, and a multi-year rewrite to make the system efficient, reliable, and maintainable -- and then lists the decisions the author calls flat out mistakes. The technical core is a set of choices made for simplicity: system catalogs stored as ordinary relations, query modification for views, protection, and integrity, decomposition by tuple substitution down to one-variable queries, one QUEL statement as the transaction unit with coarse physical locks, and deferred update for crash recovery. Its most quoted claim is that the running war over data-model efficiency was largely beside the point: with a 400-millisecond fixed overhead per interaction imposed by five UNIX processes and run-time interpretation, INGRES managed about 2.5 interactions per second, and a network-model system in the same environment would have managed the same.

Before this paper — the world it landed in

By 1973 Codd's relational model was several years old on paper and the standing objection was that it could not be made efficient. Stonebraker and Wong started reading the relational literature together, agreed they wanted an implementation, and admit they had no experience leading one -- neither had ever written a sizable computer program. They raised about $90,000 for hardware, incurring an obligation to deliver a geodata system for Berkeley's Urban Economics Group, and picked UNIX because the software environment mattered more than the machine. That choice meant a PDP-11 with a 64K address space, a file system with a 16-megabyte file limit and 512-byte pages, and no concurrency control or crash recovery underneath them. IBM's System R was being built in parallel and made the opposite call on several of these points, including writing its own file system under VM/370.

The problem — what was actually breaking

The PDP-11's 16-bit address space could not hold the system in one image, so INGRES had to be split into five cooperating UNIX processes (six in the Berkeley experimental version), and even a do-nothing interaction had to pass through eight of them.
Every interaction was parsed, validated against the system catalogs, and given an execution strategy at run time, including statements embedded in C programs through EQUEL, where the same simple update is typically executed over and over inside a loop.
Project goals expanded repeatedly -- concurrency control, crash recovery, and distributed databases were nowhere in the original design -- and each expansion forced large parts of the system to be rewritten.
The code had been built haphazardly by several people, each with a personal coding style, naming scheme, and library, so modules were unmaintainable by anyone but their original author and documentation was skipped because nothing was expected to survive.
UNIX supplied no concurrency control and no crash recovery for its file system, capped files at 16 megabytes, used a 512-byte page, and mapped logical to physical pages inefficiently.
Database administrators could not be relied on to make physical design decisions correctly: some never hashed the heavily and predictably accessed system catalogs, so their installations simply ran slower and slower without failing.

Core ideas — the contributions, and why they work

System catalogs as ordinary relations

The group first considered a specialized, non-relational structure for the data dictionary because it would be faster. They rejected it once they saw that a private access path for catalogs meant duplicated code and, worse, made it impossible to query the catalogs in QUEL. Storing metadata as ordinary relations gave them a data dictionary system for free and kept a single access-method layer for all data. The price shows up later in the paper: catalog interrogation at run time is roughly 100 milliseconds of the fixed per-interaction overhead, and users who never hash the catalogs pay for it forever.

Query modification

Protection, integrity control, and views are all implemented by rewriting the user's query before it is executed rather than by filtering results afterwards. A view definition, an authorization rule, and an integrity constraint are all just qualifications to be folded into the incoming QUEL query, so one mechanism in the parser covers three features and the query processor sees a single combined query it can optimize normally. The paper concedes the mechanism was pointed at the wrong object: protecting views, as in the System R authorization work, is cleaner than protecting base relations, and the author blames sheer dogma on his own part for not switching.

Decomposition by tuple substitution

A multi-variable QUEL query is processed by rewriting it into simpler commands in QUEL itself, principally by substituting actual tuples for one variable so that the residual query has one fewer variable. The recursion bottoms out at a one-variable query, which is why the system has a distinct one-variable query processor as a level at all -- the layering follows the algorithm, not the other way round. Because everything stays inside the same language, the strategy was easy to implement and easy to optimize. Its blind spot is stated plainly: it cannot express the sort-both-relations-and-merge tactic that is sometimes best for a two-variable equijoin.

Interchangeable access methods

From the start the design assumed several implementations of one access-method interface, all with the same calling conventions and interchangeable at will; five existed by the 1975 demo (heap, hash, compressed hash, index, compressed index). Users see nothing of the storage structure and, unlike some contemporary systems, are given no way to reach a lower level of the system, which is what makes physical data independence real rather than nominal. The cost is that the interface had to be frozen before anyone understood how restriction optimization would work, and it turned out not to be what was needed, and that utilities such as the ISAM loader had to break through the abstraction for performance.

One QUEL statement as the transaction

The team deliberated between a System R style locking subsystem, coarse physical locks on files or collections of files, and predicate locks, and settled the question on simplicity rather than power. Making a single QUEL statement the atomic unit means all needed resources can be demanded in advance, which sidesteps deadlock entirely; anything larger would have made that strategy impossible. Given that unit, the hunch that coarse physical locking would win was later confirmed by simulation studies of locking granularity. User experience supported the choice: locking the whole database would have been acceptable to most of their users.

Protection delegated to the operating system

The database administrator owns every physical UNIX file holding a database, and the INGRES binary runs with the UNIX set-user-id facility so that it executes on behalf of any user with the DBA's effective user id. This was, in the authors' view, the only way to guarantee that nobody but the DBA could touch a database except by running INGRES; any weaker scheme would let other programs tamper with the files directly. The guarantee therefore rests on the operating system rather than on the correctness of database code. It also forced structure elsewhere: because the terminal monitor lets users edit files directly, it had to be pushed out into a separate process to protect the rest of INGRES from it.

Performance is the operating system, not the data model

The paper separates two measures of database performance: the overhead of small transactions, and the cost of one big query. The first, it argues, has nothing to do with the data model in a PDP-11 environment -- it is entirely system call cost, environment switches, and validity checking, so a network-oriented system running as five processes would also do 2.5 transactions per second. The second is somewhat model dependent but is still dominated by system call cost, operating system buffering and scheduling, output formatting, and how much tuning was done. The conclusion is that benchmarking two systems with different data models mostly measures their operating systems and their implementers.

How it works — the mechanism, concretely

Five processes and the eight-process path

The shipped system runs as five UNIX processes and the Berkeley experimental system as six, with decomposition intended to run in parallel with the one-variable query processor and the utilities living in overlays. Processing even a do-nothing interaction moves control through eight processes, which means formatting eight messages, eight calls to the UNIX scheduler, and eight invocations of the pipe mechanism, contributing 150-175 of the 400 milliseconds of fixed overhead. Because code cannot be shared between processes, the access methods are physically duplicated in every process that needs them. Some of the messages carry the internal parse tree of a QUEL command, so the system needs a routine to linearize a tree-structured object into a pipe and its inverse to rebuild the tree on the other side -- where a procedure call would have passed a pointer.

Access methods over the UNIX file system

Rather than write their own file system as System R did under VM/370, the team built access methods directly on UNIX files, to avoid duplicating operating system function and to keep the code easy to export. A hash bucket is exactly one 512-byte UNIX page, so a lookup always searches an entire page even when a single tuple is wanted. The original sizing assumption was that INGRES would never need more than 30 milliseconds to process a 512-byte page, roughly the time UNIX needs to fetch one from disk, so on the usual single-controller PDP-11 the system would always be I/O bound; measurement found significant CPU-bound cases instead, at which point per-page and per-tuple waste became visible. Two related inefficiencies were fixed -- an extra copy of a tuple in main memory, and manipulating whole tuples rather than the wanted fields -- but the page-sized hash bucket is called fundamental to the design and a mistake.

Decomposition and the one-variable query processor

DECOMP takes the parsed QUEL query and reduces it to a sequence of one-variable queries, using tuple substitution to eliminate variables one at a time, and OVQP executes each single-relation query against whichever access method the relation currently uses. The two live in different UNIX processes, which is exactly why adding a new join tactic is expensive: recognizing that a two-variable equijoin should be done by sorting both relations on the join field and merging is described as not very hard, but implementing it would require restructuring the interface between the two query-processing processes. The first implementation did decomposition by brute force; it was improved substantially during the rewrite phase, and the parser, having become top-heavy from patches, was rewritten from scratch.

Concurrency control by coarse physical locks

With one QUEL statement as the atomic operation, a command can claim all the resources it needs before it starts, so deadlock never arises and no waits-for graph is needed. Locks are coarse and physical -- on files or collections of files -- rather than fine-grained record locks or predicate locks, both of which were seriously considered and rejected as too much machinery for the setting. The choice was a hunch at the time and was afterwards validated by simulation experiments on locking granularity. In practice users never pushed back: the paper reports that whole-database locking would be an acceptable alternative for most of them.

Deferred update and crash recovery of the utilities

All QUEL statements are routed through a deferred update facility, so a soft crash (one where the disk survives) during statement execution can be undone or completed cleanly. The hard case is a crash while a utility is running, because each utility does its own manipulation of the system catalogs in addition to its real work, and a half-finished utility can leave the catalogs inconsistent. The recovery design is a program that passes over the system catalogs once, or at most twice, finds every inconsistency regardless of which command was in flight, and then either backs that command out or runs it forward. Making such a scan possible required ironclad protocols governing exactly how each utility may touch the catalogs, and installing those protocols was a large amount of unglamorous work in the utility code.

The EQUEL path and where the 400 milliseconds go

EQUEL is a preprocessor that embeds QUEL in C; C was the only candidate host language because it alone supported the interprocess communication INGRES depends on. The interpreter was designed for ad hoc terminal interactions, so an EQUEL program's statements are treated exactly like typed-in ones: parsed at run time, then checked against the catalogs to confirm the relation exists, the domains exist, and constants are of the right type or converted correctly. That validity checking costs roughly 100 milliseconds per interaction and the process traversal another 150-175, giving the 400-millisecond floor and a ceiling near 2.5 simple interactions per second. The interpreter also costs space: an EQUEL program's working set is about 150 kbytes plus the program, which is punishing on small machines, and the stated fix is to convert INGRES to be alternatively compiled and interpreted.

What the paper showed — measurements and proofs

The prototype has a fixed overhead of about 400 milliseconds (400,000 instructions) per interaction, which limits throughput on simple statements to roughly 2.5 interactions per second regardless of how trivial the statement is.
That overhead breaks down into roughly 100 milliseconds of run-time validity checking against the system catalogs and 150-175 milliseconds of interprocess traffic across the eight-process control path.
The working set of an EQUEL program is about 150 kbytes plus the program itself, and because code cannot be shared across processes the access methods are duplicated in every process that needs them.
The design assumed INGRES would never need more than 30 milliseconds to process a 512-byte page -- about what UNIX takes to fetch one -- so it should always have been I/O bound on a single-controller PDP-11; in fact significant cases turned out to be CPU bound.
The system is about 500,000 bytes of source code, mostly undocumented apart from comments, supporting roughly 100 users at the time of writing (5-10 serious users plus about 90 casual ones, mostly universities), with 106 users cited elsewhere in the paper, many of them on PDP-11/34s and 11/40s.
In four years every piece of the system went through between two and five incarnations, roughly a major rewrite per year; the equivalent of one entire rewrite is attributed to the initial absence of coding conventions, while users reported building applications as much as ten times faster than originally anticipated.

Limits and trade-offs — conceded and discovered

Conceded: making a hash bucket exactly one UNIX page means an entire 512-byte page is searched even to find one tuple, and unlike the extra in-memory tuple copy and whole-tuple manipulation (both fixed), the author calls this one fundamental to the design and a mistake.
Conceded: static, load-time index directories instead of B-tree style dynamic ones leave the DBA to rebuild directories periodically and to guess initial page fill factors, and overflow pages make buffer requirements unpredictable in an address space too small to hold them.
Conceded: decomposition cannot express sort-merge for a two-variable equijoin, and adding it would require redrawing the interface between the two UNIX processes that do query processing; likewise, protection is attached to base relations rather than views, which the author blames on his own dogma, and updates are silent, reporting only done without saying which or how many tuples changed.
Conceded: the whole system is interpreted, so repetitive parameterized statements issued from host-language programs pay full parse, validation, and optimization cost every time; the paper says the project was only then starting to convert INGRES to be alternatively compiled and interpreted.
Exposed by later work: the claim that data model choice matters far less than the operating system and implementation effort holds for 2.5-transaction-per-second PDP-11 systems but did not generalize -- System R's compiled access plans and cost-based optimization became the industry norm precisely because they attack the overhead this paper treats as environmental; and the evidence base is one project with limited user experience, which the author flags himself by noting that the ultimate jury, real users, had not yet reported.

What it became — the systems that inherited it

INGRES became the second founding lineage of relational systems alongside System R, and this paper is the honest ledger of what that cost. The Berkeley code was commercialized as Ingres by Relational Technology Inc., later sold through Ingres Corporation and Computer Associates and eventually released as open source, while project alumni spread the design: Robert Epstein, one of its chief programmers, co-founded Britton Lee and then Sybase, whose engine Microsoft licensed as the basis of SQL Server, and Eric Allman, another chief programmer, wrote sendmail in the same environment. The Section 6 plans became Distributed INGRES and the MUFFIN database machine, early shared-nothing designs whose ideas carried into Gamma and today's MPP engines. Stonebraker's next Berkeley system, POSTGRES, was a direct answer to limits catalogued here and became PostgreSQL, which still implements views and row-level security through query rewriting descended from INGRES query modification. QUEL lost to SQL, but the paper's other verdicts aged well: prepared and compiled statements are now standard, static ISAM directories lost to B-trees everywhere, and automatic physical design -- which the author says the project converted him to -- is now a product feature. The candid, number-backed system postmortem also became a genre, with Stonebraker's later retrospectives, including What Goes Around Comes Around, as direct descendants.

In the paper’s words — verbatim

“This paper describes the implementation history of the INGRES database system. It focuses on mistakes that were made in progress rather than on eventual corrections.”

Abstract

“In four years there were between two and five incarnations of all pieces of the system.”

§3.2

“In summary, I would allege that a comparison of two systems using different data models would result primarily in a test of the underlying operating system and the implementation skill (or man-years allowed) of the designers and only secondarily in a test of the data models.”

§5.3

Vocabulary — as this paper uses it

QUEL: INGRES's data sublanguage, whose retrieval portion was loosely based on Codd's DSL/Alpha but had no quantifiers. Its original punctuation-oriented syntax was scrapped in 1975 for a keyword-oriented one, the last significant change to the user language.
EQUEL: The preprocessor that embeds QUEL statements in C programs. C was the only viable host language because it alone allowed the interprocess communication INGRES needed to run.
Decomposition: The query processing strategy of rewriting a multi-variable QUEL command into simpler commands expressed in QUEL itself. It is elegant and easy to optimize, but cannot express a sort-merge equijoin.
Tuple substitution: The core step of decomposition: substitute actual tuples for one query variable so the remaining query has one fewer variable. Repeated substitution reduces any query to one-variable queries.
OVQP (one-variable query processor): The module that executes a query over a single relation through whatever access method that relation uses. It exists as a distinct level of the system only because decomposition required such a level.
Query modification: Rewriting a user's query at parse time to incorporate view definitions, protection qualifications, and integrity constraints. One mechanism thereby implements three features, and the optimizer sees a single ordinary query.
System catalogs: INGRES's data dictionary, stored as ordinary relations so it can be queried in QUEL and managed by the same access methods. Catalogs begin as heaps and should be hashed once their size stabilizes.
Deferred update: The facility through which all QUEL statements pass so that a soft crash, one that leaves the disk intact, can be recovered from cleanly while a statement is executing.
Static directory: An index directory built at load time and never modified afterwards, as in ISAM. The paper contrasts it with a dynamic directory such as a B-tree and concludes the dynamic choice would have been correct.

On the timeline — where this sits in the story

Year1972–1976

MilestoneINGRES research system

Problem solvedThe relational model was elegant, but skeptics questioned whether relational databases could be practical and performant.

How it solved itINGRES implemented a working relational DBMS and query language for real users and research workloads.

Why it matteredInfluenced commercial relational systems and the lineage that eventually produced PostgreSQL.

DDIACh. 3: Data Models

View on the timeline