Looking Back at Postgres — Papers Distilled

In one breath — the whole paper, compressed

This is Joseph Hellerstein's recollection of the UC Berkeley Postgres project that Michael Stonebraker led from the mid-1980s to the mid-1990s. Postgres set out to be a one-size-fits-all database that kept tables and declarative queries but made almost every layer extensible: user-defined abstract data types and functions, complex nested columns, pluggable access methods, an active rules system, a no-overwrite storage engine that treats the log as the data, and parallel query optimization. The article walks through each of those bets and says plainly which survived and which were later ripped out. Two students replaced the Postquel language with SQL to produce Postgres95, an outside volunteer community adopted the code as PostgreSQL, and that same architecture now underlies the fourth most popular database in the world plus over $2.6 billion of acquisitions. The central claim is that Postgres beat Fred Brooks's second-system effect precisely because extensibility, not feature discipline, was the architectural core.

Before this paper — the world it landed in

Stonebraker had already succeeded with the Ingres research project at Berkeley and with RTI, the startup he founded on it, so Postgres was explicitly Post-Ingres: take what Ingres could do and go beyond. In the early 1980s his group was being pulled toward Computer-Aided Design tools for the microelectronics industry, which needed polygons, rectangles, text strings, efficient spatial searching, complex integrity constraints, and design hierarchies with multiple representations of the same physical construction. That pressure produced Antonin Guttman's R-trees and ADT-Ingres, a prototype that bolted abstract data types onto Ingres and even allowed a Quel query to serve as a column type. Meanwhile commercial vendors were differentiating themselves by investing heavily in highly optimized write-ahead logging and transaction throughput, and the AI community's enthusiasm for rule-based expert systems was at its tail end. Postgres was designed against all of these currents at once, and did not follow any of them.

The problem — what was actually breaking

Microelectronics CAD tools needed new data types such as polygons, rectangles and text strings, efficient spatial searching, complex integrity constraints, and design hierarchies with multiple representations of the same physical construction, none of which fit the flat rows and columns of Codd's relational model.
Relational modeling doctrine required nested data, such as a purchase order with its products, quantities and prices, to be shredded into flat entity and relationship tables, which is unnatural for an application like a CAD circuit layout engine where updates are rare.
Code that interprets an application-specific type had to live above the DBMS, so the system was forced to pull data to code rather than push code to data, at significant performance cost.
B-trees and related structures support only equality lookups and one-dimensional range queries, and inventing a better index such as the R-tree does not by itself solve the end-to-end problem of teaching the optimizer, the storage layer, and the logging and recovery system about it.
Textbook optimizers pushed selections below joins and ordered them arbitrarily, an assumption that breaks once a selection contains an expensive user-defined function that may even belong above a join.
The write-ahead logging schemes pioneered at IBM and Tandem were, in Stonebraker's view, too complicated to rely on for functionality that would only be exercised in rare, critical scenarios after a crash.

Core ideas — the contributions, and why they work

Object-Relational, not object-oriented

Rather than making programming-language objects persistent, as the OODB vendors proposed for the impedance mismatch, Postgres retained tables as its outermost data type and declarative queries as the interface, then allowed columns to hold complex types: nested tuples or tables, and in one esoteric form a column defined declaratively as a query, Quel as a data type. This works because the relational model never actually demanded scalar columns; Codd's model admits any atomic type with predicates, so extending the type system cost modest changes to the metadata catalog rather than a new architecture. Stonebraker branded the result Object-Relational and sidestepped the OODB workload as a zero-billion-dollar market. Today essentially all commercial relational systems are object-relational, and PostgreSQL absorbed XML and JSON without any significant rearchitecting.

User-defined types and functions in the catalog

Postgres was the pioneering database system to support, in a comprehensive way, opaque abstract data types that are stored in the database but not interpreted by the core engine, together with user-defined functions and user-defined aggregates that queries can invoke over them. The payoff is the classic one of pushing code to data instead of pulling data to code, and the reason it is cheap is that query syntax, semantics and system architecture all stay the same: only the relational metadata catalog and a mechanism to invoke foreign code are added. Postgres was ahead of its time on the downside too, since the security implications of uploading unsafe code into a server were not an active concern in database research then, and Oracle's negative marketing about Informix running unprotected user-defined C code did real commercial damage. The paper argues MapReduce is a re-realization of this same idea, Postgres software engineering combined with Gamma and Teradata parallelism.

Extensible access methods

Postgres let a new index structure be registered through an abstract description, so an R-tree could be added without patching the engine, and taught the optimizer to recognize an abstract selection predicate, a range selection for example, and match it to that abstractly described access method. This is why extensibility here is architectural rather than local: the change reaches from the optimizer down through the storage layer to logging and recovery. The design survived intact. PostgreSQL still ships B-tree, GiST, SP-GiST and Gin indexes through this framework, with GiST powering the PostGIS geographic information system and Gin powering PostgreSQL's internal text indexing.

Optimizing expensive predicates

Once selections can contain arbitrarily expensive user-defined functions, the classic rule of pushing every selection below every join becomes wrong: the order in which UDFs execute can be critical, and a sufficiently time-consuming predicate may belong after a join, which is selection pullup. Postgres was the first DBMS to capture the costs and selectivities of UDFs in the database catalog, which is what makes the decision computable at all. The optimizer computed an optimal ordering of selections and then an optimal interleaving of those selections along the branches of each join tree considered during plan search, preserving the textbook System R dynamic-programming architecture at the price of a small additional sorting cost.

Rules as a database feature

Instead of following the theoretical branch of rule programming into Datalog, which Stonebraker openly disliked, Postgres pursued the pragmatic branch that became Active Databases and database triggers. Eric Hanson's and Spyros Potamianos's work produced PRS2, which deliberately kept two implementations: rules as query rewrites, in the spirit of the view rewriting Stonebraker had pioneered in Ingres, and rules as row-level conditions checked using locks inside the database. Neither scheme was declared the winner and the released system kept both. The per-statement and per-row trigger distinction still present in PostgreSQL descends directly from that unresolved choice.

No-overwrite storage: the log is the data

Stonebraker refused to implement another write-ahead log and instead unified primary storage and historical logging into a single, simple disk-based representation: each record is a linked list of versions stamped with transaction IDs, and the only additional metadata required is a list of committed transaction IDs and wall-clock times. Recovery becomes enormously simpler because there is no translating from a log representation back into a primary representation; the committed versions already sit where the data lives. The same structure yields time travel for free, since a query can run as of some wall-clock time and see exactly the versions committed then. The 1991 design added the use of non-volatile memory to hold commit status.

The Wei Hong Optimizer

Parallelism in principle blows up the plan space by multiplying every traditional choice, data access, join algorithm and join order, against every possible way of parallelizing that choice. XPRS cut the problem in two: run a traditional single-node optimizer in the style of System R, then parallelize the resulting plan by scheduling the degree of parallelism and the placement of each operator based on data layouts and system configuration. The approach is heuristic and can miss plans an integrated search would find, but it makes parallelism an additive cost to traditional query optimization rather than a multiplicative one, and it became the standard approach for many parallel query optimizers in industry.

How it works — the mechanism, concretely

Registering a type in the catalog

A programmer defines an abstract data type by supplying the functions that convert it in and out plus the user-defined functions and operators that act on it, and these registrations live in the relational metadata catalog next to the built-in types. The executor reaches this foreign code through a general invocation mechanism, so an ADT column stays opaque to the engine, which stores bytes it never interprets. Postgres additionally records each user-defined function's cost and selectivity in the catalog, data the optimizer reads later. Because everything hangs off the catalog, adding a type requires no change to the parser, the plan representation or the storage format.

Plugging in an access method

An access method such as an R-tree is registered abstractly, described by the predicates it can answer rather than by its internals. During optimization the planner examines a selection predicate abstractly, recognizing for instance a range selection, and matches it against the registered access methods that claim to serve that kind of predicate, so a new index becomes usable by the optimizer without optimizer surgery. The gap in the original effort was concurrency control: without a unidimensional ordering on keys, B-tree-style locking is inapplicable, and the project largely set the question aside. Marcel Kornacker's later thesis work supplied templated concurrency and recovery for exactly this interface in GiST.

Placing expensive selections in the plan

The optimizer first derives an optimal ordering of the query's selection predicates from their catalogued costs and selectivities, producing one ranked sequence. It then interleaves that sequence along the branches of each join tree that the System R dynamic-programming search enumerates, which is what allows a predicate to be evaluated after a join when its cost warrants it. Because the ordering is computed once and reused across the enumerated trees, the extra work is a small sorting cost rather than an explosion of the search space. The feature reached Illustra, but was disabled in the PostgreSQL source trees early on, largely because there were no compelling expensive-UDF use cases at the time.

PRS2: two rule engines side by side

In the rewrite path, a rule of the form on condition then action is recast as on query then rewrite to a modified query and execute it instead, reusing the machinery Stonebraker had built for view rewriting in Ingres, so that appending a row to one table can become an entirely different update such as raising a salary by ten percent. In the physical path, conditions are checked at row level using locks placed inside the database; when such a lock is encountered the system does not wait as in traditional concurrency control, but executes the associated action. Both shipped in the released system. A surviving source comment from Postgres 3.1, circa 1991, warning hackers away from the tuple level rule system records just how treacherous the row-level path was to maintain.

Versioned, no-overwrite tuples

An update never overwrites a record; it appends a new version into that record's linked list of versions, stamped with the writing transaction's ID. Visibility is resolved against the list of committed transaction IDs, and the accompanying wall-clock times let a query ask for the state as of a given moment, which is exactly how time travel is implemented. Because committed data already sits in its final place, crash recovery has no pass that translates log records back into primary storage. The costs are that superseded versions accumulate and demand expensive background reorganization, and that transactional replication by log shipping, which the vendors built once their write-ahead logs worked well, would be difficult in this scheme.

Parallelizing a finished plan

XPRS runs the ordinary sequential optimizer to completion, yielding a single best single-node plan, and only then performs a parallelization pass over that plan tree. The pass assigns each operator a degree of parallelism and a placement, decided from the physical layout of the data and the configuration of the shared-memory machine. Nothing in the search phase itself changes, so the total plan space remains the sequential one plus a post-pass, which is precisely what keeps the cost additive rather than multiplicative.

Reaching down to tertiary storage

Project Sequoia required up to 100 terabytes of digital satellite imagery, far more than could reasonably be stored on magnetic disks at the time, so Sunita Sarawagi's thesis work extended the stack down to robotic jukeboxes of optical disks and tapes. Large multidimensional arrays are broken into chunks, chunks that are fetched together are stored together, and chunks are replicated so that a given chunk has multiple physical neighbors. Disk is then treated as a cache for tertiary storage, and both query optimization and query scheduling must account for the long load times of tertiary storage and the value of hits in the disk cache, changing both the plan chosen and the time at which it is scheduled to execute. A companion effort, Mike Olson's Inversion file system, put a UNIX filesystem abstraction above the RDBMS; Stonebraker called it a straightforward exercise, and it proved neither straightforward nor durable.

What the paper showed — measurements and proofs

This is a recollection rather than an experimental paper, so its headline measure is adoption: PostgreSQL is reported as the most popular independent open-source database system in the world and the fourth most popular database system overall, behind Oracle, MySQL and MS SQL Server, and was the fastest-growing database system in the world in both 2017 and 2018.
The disclosed or estimated acquisitions of Postgres-derived companies total over $2.6 billion: Illustra to Informix in 1997 at an estimated $400M, Netezza to IBM valued at $1.7B, Greenplum to EMC at an estimated $300M, and Aster Data to Teradata at $263M. ParAccel also went to Actian, but its price was not disclosed and is therefore excluded from that total.
Architectural durability is the paper's other measurement: after 25 years, PostgreSQL's source directory structure, process structure and data structures remain close enough to the Postgres 3.1 release of about 1991 that a developer familiar with the current source would have little trouble wandering through the old code.
The extensible access method layer is still load-bearing in production, since PostgreSQL ships B-tree, GiST, SP-GiST and Gin indexes through it, with GiST supporting the PostGIS geographic information system and Gin supporting PostgreSQL's internal text indexing.
Postgres was the first DBMS to capture the costs and selectivities of user-defined functions in the database catalog, and the resulting expensive-predicate optimizer preserved the textbook System R dynamic-programming architecture at the cost of only a small additional sort to order the selections properly.
The two-phase parallel optimization of XPRS became the standard approach for many of the parallel query optimizers in industry, and the Postgres-based startups Greenplum and Aster showed around 2007 that parallelizing Postgres produced something much higher-function and more practical than MapReduce for most customers.

Limits and trade-offs — conceded and discovered

Conceded: the Postgres storage system never excelled on performance, and versioning and time travel were removed from PostgreSQL over time and replaced by write-ahead logging, while transactional replication based on log shipping, an obvious follow-on once vendors had write-ahead logs working, would have been difficult in the Postgres scheme.
Conceded in a footnote and sharpened by hindsight: PostgreSQL is still not particularly fast for transaction processing, because it kept much of the Postgres tuple storage overhead in order to provide multiversion concurrency control, something that was never a goal of the Berkeley project, so it emulates Oracle's snapshot isolation with a fair bit of extra I/O while supporting neither time travel nor simple recovery.
Conceded: concurrency control was much less of a focus in the original extensible access method work, because the lack of a unidimensional ordering on keys makes B-tree-style locking inapplicable; the difficult concurrency and recovery problems were only solved later by Kornacker's templated approach for GiST.
Conceded: neither the query-rewrite nor the row-level locking scheme could be declared a winner for rules, all the rules code was eventually scrapped and rewritten in PostgreSQL, and triggers are used sparingly in practice because interactions within a pile of rules become untenably confusing as the rule set grows and triggers remain relatively time-consuming.
Exposed by later work: PostgreSQL's key limitation is that it does not scale out to a parallel, shared-nothing architecture, which every major commercial fork had to add for itself, and the author regrets that this was not done in true open source in the early 2000s; likewise the Fast Path API made Postgres moderately performant on academic OODB benchmarks without ever addressing the impedance mismatch, and the Inversion file system did not survive in practice.

What it became — the systems that inherited it

PostgreSQL is the direct descendant: Andrew Yu and Jolly Chen swapped Postquel for an extensible variant of SQL to produce Postgres95, a pick-up team of outside volunteers adopted the code as PostgreSQL and has shepherded it since 1995, and Heroku's 2010 choice of it as a platform default pulled Ruby on Rails and Django along with it. The commercial line runs through Illustra, whose DataBlades became Informix Universal Server, then Netezza's FPGA-based parallel warehouse, Greenplum's shared-nothing fork with its Orca optimizer and MADlib machine-learning library, EnterpriseDB's Oracle-compatibility edition, Aster Data's SQL and MapReduce analytics, ParAccel, whose technology became AWS Redshift, and CitusDB, which since 2016 ships purely as PostgreSQL extensions. The extensibility architecture itself became the industry norm: all the major vendors now execute user-defined functions in the server, essentially all commercial relational systems are object-relational, and triggers are part of the SQL standard. Ideas the paper argues arrived too early keep returning under new names, since MapReduce and the Big Data stacks are user-defined code hosted in a query framework, XQuery and today's JSON query languages recapitulate Postquel's complex objects, and materialized view maintenance, complex event processing and stream queries all extend the rules work. Even the side bets left descendants: GiST grew out of the extensible access method interface and now powers PostGIS, while Margo Seltzer's BerkeleyDB, written at Berkeley alongside Postgres, presaged the distributed key-value stores Dynamo, MongoDB and Cassandra.

In the paper’s words — verbatim

“Postgres was Michael Stonebraker's most ambitious project — his grand effort to build a one-size-fits-all database system.”

§1 Opening

“At base, the idea was to keep each record in the database in a linked list of versions stamped with transaction IDs—in some sense, this is "the log as data" or "the data as a log," depending on your point of view.”

§2.3

“Postgres was designed for extensibility, and that design was sound. With extensibility as an architectural core, it is possible to be creative and stop worrying so much about discipline: you can try many extensions and let the strong succeed.”

§4 Lessons

Vocabulary — as this paper uses it

Object-Relational: Stonebraker's branding for extending the relational data model and declarative query language with object-oriented features such as user-defined types, functions and nested columns, rather than making programming-language objects persistent as the OODB camp proposed.
Abstract Data Type (ADT): A user-supplied type that is stored in the database but not interpreted by the core database system; the engine knows only how to move it in and out and which registered functions operate on it.
User-Defined Function (UDF): Application code registered with the system so that queries can invoke it over ADT columns. Postgres also supported user-defined aggregates and was the first DBMS to record each function's cost and selectivity in the catalog.
Complex object: A column whose value is itself nested, a tuple or a table, and in the ADT-Ingres lineage even a stored Quel query used as a data type, so that non-first-normal-form data can live inside an ordinary relational table.
Extensible access method: An index structure registered with the system through an abstract description of the predicates it answers, so the optimizer can match abstract selection predicates to it. R-trees were the driving example and GiST the later generalization.
No-overwrite storage: The Postgres storage discipline in which an update appends a new tuple version onto a per-record version chain stamped with a transaction ID rather than modifying data in place, making the primary data and the historical log one and the same structure.
Time travel: Running a query as of some past wall-clock time, answered by consulting the list of committed transaction IDs and their timestamps to select the tuple versions that were committed at that moment.
Fast Path: A C or C++ API exposing the storage internals of the database directly, added so that Postgres could bypass query parsing and optimization and compete with OODB products on their own benchmarks.
The Wei Hong Optimizer: Stonebraker's name for the XPRS scheme of optimizing a query as though for a single node, then parallelizing that finished plan by scheduling each operator's degree of parallelism and placement.

On the timeline — where this sits in the story

Year1986 onward

MilestonePOSTGRES

Problem solvedFirst-generation relational systems had rigid scalar types and limited support for complex application-specific objects and operators.

How it solved itPOSTGRES introduced object-relational extensibility, user-defined types/operators, and rules.

Why it matteredBecame the intellectual ancestor of PostgreSQL and influenced extensible database architecture.

DDIACh. 3: Data Models Ch. 4: Storage & Retrieval

View on the timeline