Parallel Database Systems: The Future of High Performance Database Processing

In one breath — the whole paper, compressed

By 1992 the special-purpose database machine had failed, but parallel database systems built entirely from commodity processors, memories and disks were displacing mainframes on the largest workloads. DeWitt and Gray explain why: relational operators consume and produce uniform streams of tuples, so a SQL query compiles into a dataflow graph that can be run with pipelined parallelism and, far more profitably, with partitioned parallelism over declustered relations. The enabling trick is that no operator needs rewriting; ordinary sequential scan, sort and join code is wrapped by two plumbing operators, split (route each output tuple to one of several destination processes) and merge (funnel several streams into one sequential input port), with flow control built in. The recommended hardware is shared-nothing, where each disk and memory is owned by one processor and the network carries only questions and answers rather than pages, because shared-memory and shared-disk designs pay interference costs that cap them at tens of processors. Teradata, Tandem, Gamma, Bubba and Oracle-on-nCUBE are surveyed as evidence that this design delivers near-linear speedup and scaleup to hundreds of processors, and cheaply enough that Grosch's law no longer holds for database work.

Before this paper — the world it landed in

In 1983 Boral and DeWitt had written a well-known critique arguing that database machines were an idea whose time had passed, and the evidence was on their side: a decade of research had chased CCD memories, bubble memories, head-per-track disks and optical disks, and none of those technologies delivered. Forecasts said processor speed would grow much faster than disk throughput, so critics expected multiprocessors to become I/O bound. Meanwhile mainframe designers could not build single machines big enough to serve thousands of concurrent users or to scan terabyte relational databases. Cheap microprocessors were arriving from Encore, Intel, NCR, nCUBE, Sequent, Tandem, Teradata and Thinking Machines, and message-passing client-server operating systems over fast LANs had become mainstream architecture rather than an exotic research toy. Teradata had been quietly shipping highly parallel SQL machines since 1978, and Tandem and a wave of startups followed, so the question in 1992 was no longer whether parallel database systems worked but why they worked.

The problem — what was actually breaking

Mainframe designers could not build a single machine powerful enough to meet the CPU and I/O demands of relational databases serving large numbers of simultaneous users or searching terabyte databases.
In most computer designs, adding a processor slows every other processor down a little, and the paper shows that even 1% interference caps speedup at 37, so naive multiprocessing does not scale.
A decade of special-purpose database machine hardware, including CCD memories, bubble memories, head-per-track disks and optical disks, had failed to fulfil its promises, discrediting the whole database machine agenda.
Disk throughput was predicted to only double while processor speeds grew much faster, so multi-processor systems were expected to become I/O limited unless the I/O bottleneck was attacked directly.
Old software written for uni-processors gets no speedup or scaleup when moved onto any multiprocessor and must be rewritten, which for most application domains is prohibitively expensive.
Even a correctly parallelized system faces three generic barriers to linearity: startup cost when thousands of processes must be launched, interference on shared resources, and skew, where the variance of step sizes exceeds the mean so the slowest step determines the job time.

Core ideas — the contributions, and why they work

Speedup and scaleup as the yardstick

The paper insists that a parallel database be judged by two ratios rather than by peak hardware specifications. Linear speedup means an N-times larger system runs a fixed job N times faster, computed as small system elapsed time divided by big system elapsed time. Linear scaleup means an N-times larger system runs an N-times larger job in the same elapsed time, so the ratio evaluates to 1; it comes in two flavours, transaction scaleup (N times as many clients issuing N times as many small requests against an N times larger database, the form used by the TPC benchmarks) and batch scaleup (the same single query against an N times larger database). Making success falsifiable this way is what lets the authors name the three things that break it: startup, interference and skew.

Shared-nothing wins the architecture argument

Using Stonebraker's taxonomy, the paper contrasts shared-memory (all processors share one global memory and all disks), shared-disk (private memory per processor, but every processor can address every disk) and shared-nothing (each memory and disk is owned by one processor that acts as its server, and processors communicate only by messages). Shared-nothing minimizes interference by minimizing sharing: raw memory and disk accesses happen locally and only filtered, reduced results cross the network, so the interconnect carries questions and answers rather than pages. Shared-memory machines must build an interconnect with the summed bandwidth of all processors and disks, and measurements of database workloads show that loading and flushing the large private caches they need degrades processors considerably. Shared-disk fails differently: any update requires declaring an intent, waiting for acknowledgement from every other processor, then reading and writing whole physical pages, which is far more expensive than exchanging small high-level questions and answers.

Relational queries are dataflow graphs

Every relational operator takes relations as input and produces a relation as output, so operators compose arbitrarily; a SQL statement is therefore syntactic sugar over a graph of scan, sort, aggregate, join, insert, update and delete nodes. Because SQL is non-procedural, the system rather than the programmer decides how a query executes, which means an unmodified SQL application written for a uni-processor can be run in parallel on a shared-nothing machine with no source changes. This is why database applications are the exception to the old-software barrier that blocks parallelism everywhere else. The authors point out the historical irony: Codd proposed the relational model for programmer productivity and data independence, and parallelism turned out to be an unanticipated benefit.

Partitioned parallelism, not pipelined

The paper is blunt that of the two kinds of parallelism a dataflow graph offers, pipelining is the weak one. Relational pipelines are short, since a chain of length ten is unusual; sort and aggregate are blocking operators that emit no output until they have consumed all their input, so they cannot be pipelined at all; and usually one operator costs far more than the others, which is itself a form of skew that bounds the pipeline's gain. Partitioned execution instead applies divide and conquer, turning one big job into many independent little ones by partitioning an operator's inputs and outputs across processors and disks. Speedup then scales with the number of partitions rather than with the depth of the plan, which is why partitioned data is called the key to partitioned execution.

Declustering as physical design

Spreading a relation's tuples across many disks is the precondition for partitioned execution and yields I/O bandwidth superior to RAID-style striping without any specialized hardware. The three basic schemes trade off differently: round-robin is ideal when every query scans the whole relation but forces associative lookups onto every disk; hash partitioning directs an equality lookup on the partitioning attribute to a single disk but randomizes rather than clusters data; range partitioning preserves clustering and serves range predicates well but risks data skew and hence execution skew, which hashing and round-robin resist better. Bubba refines range partitioning by considering each tuple's access frequency, or heat, so that partitions are balanced by how often they are accessed (temperature) rather than by how many tuples they hold (volume). Partitioning is not free at any degree: past some point the per-node cost of starting a query becomes a significant fraction of execution time and further partitioning increases response time.

Encapsulating parallelism in split and merge

Rather than writing parallel versions of scan, sort and join, the system keeps the existing sequential operator implementations and changes only the plumbing between them. Each operator is given a set of input ports and one output port; a merge operator combines several parallel streams into one sequential stream feeding a port, and a split operator maps each output tuple to one of several destination processes based on its attribute values. The mapping can be a range predicate, a hash, round-robin, a duplication of the stream, or an arbitrary program, and because parallelism lives entirely in these two operators, any new relational operator added to the system becomes parallel automatically. Split and merge also carry flow control and buffering, so when a split operator's output buffers fill it stalls its producer until the consumer asks for more, making the whole graph self-pacing.

Hash join as the parallel join

The conventional sort-merge join sorts both inputs on the join attribute and merges them, so it inherits sort's n log n cost, and under data skew some sort partitions become far larger than others, converting data skew into execution skew that limits speedup and scaleup. Hash join instead hash-partitions both relations on the join attribute, loads one partition of A into an in-memory hash table, and scans the corresponding partition of B against it, emitting a concatenated tuple on every match. Its cost is linear rather than n log n, it breaks one big join into many small independent joins, and it is more resistant to skew, so it beats sort-merge unless the inputs already arrive sorted. Provided the hash function is good and skew is moderate, bucket sizes vary little and the join achieves linear speedup and scaleup, which is why the authors present it as proof that better parallel algorithms, not better hardware, are the fruitful research direction.

How it works — the mechanism, concretely

Decluster every relation across disks

At load time each relation is assigned a partitioning strategy and a set of disk fragments, one per participating processor. Round-robin sends the i-th tuple to disk i mod n; hash partitioning applies a hash function to a chosen attribute to pick the disk; range partitioning maps contiguous attribute ranges, such as names a-to-c on one disk and d-to-g on the next, to different disks; Gamma adds hybrid-range partitioning that mixes the properties of hash and range. Increasing the degree of partitioning shortens sequential scans because more disks are read in parallel, and shortens associative scans because each node's index covers fewer tuples. Physical design therefore becomes a per-relation choice of strategy, attribute and degree, and the paper flags that no automated tool existed to make it.

Compile SQL into a graph of sequential operators

The optimizer produces a logical query graph: for the query that inserts into C the join of A and B on A.x = B.y, the tree has one scan node per input relation, one join node and one insert node. Each node is an ordinary sequential relational operator with a set of numbered input ports and a single output port. Parallelization is then a separate step, performed by inserting split and merge operators between nodes of that tree rather than by rewriting any operator. Tandem, Gamma and Volcano all take exactly this approach, which is why the same query plan shape works at any degree of parallelism.

Merge: many parallel streams into one port

Consider relation A declustered into fragments A0, A1 and A2. The parallel query executor creates three scan processes, directs each at one fragment, and directs all three to send their output to a common merge node. The merge operator produces a single output data stream that can go to the application, to a terminal, or to the next relational operator, which is unaware that its input arrived from three machines. Merge is thus the operator that lets a sequential consumer sit on top of partitioned producers without modification.

Split: one stream into many destinations

A split operator holds a table mapping predicates on output-tuple attributes to destination triples of the form (cpu number, process number, port number). In the paper's example the split on each relation A scan sends tuples in the range A-H to cpu 5 / process 3 / port 0, tuples in I-Q to cpu 7 / process 8 / port 0, and tuples in R-Z to cpu 2 / process 2 / port 0, while the split on each relation B scan uses the same ranges but targets port 1 of the same three processes. Other split operators may duplicate the stream, partition it round-robin, or partition it by hash; the partitioning function can be an arbitrary program. Buffering and flow control live inside split, so a full output buffer stalls the upstream relational operator until the downstream target requests more data, which prevents one part of the graph from running far ahead of another.

Worked example: a partitioned join

Take the insert-into-C-select-from-A-and-B query with three processes running the join, three scanning fragments of A and two scanning fragments of B. Every A scan applies the same split, so join process 0 receives, merged on port 0, all the A-H tuples of A produced by all three A scans; every B scan applies the corresponding split, so the same join process receives all the A-H tuples of B merged on port 1. Each join process therefore sees two ordinary sequential input streams and can run hash join, sort-merge join, or even nested-loop join if tuples arrive in a suitable order, entirely unaware of the parallelism around it. The outputs of the three joins are in turn split according to relation C's own partitioning criterion and merged at the three insert nodes, so the result lands correctly declustered without a separate redistribution pass.

Executing the parallel hash join

Both A and B are hash partitioned on the join attribute, which guarantees that matching tuples land in the same bucket pair and eliminates any need for cross-node comparison. One hash partition of A is built into a main-memory hash table; the corresponding partition of B is scanned and each of its tuples probed against that table, with matching pairs concatenated into the output stream; the process repeats for every pair of partitions. Correctness depends only on the partitioning invariant, and performance depends on the bucket-size variance, so a good hash function plus moderate skew yields near-uniform buckets and linear behaviour. The failure mode is explicit: if many or all tuples share a single join attribute value, one bucket receives them all, and the paper states that in such pathological cases no algorithm is known that speeds up or scales up.

How the shipped systems instantiate this

Teradata splits processors into Interface Processors, which parse, optimize and coordinate, and Access Module Processors, which store and execute, joined by the dual-redundant tree-structured Y-net; a first hash on the primary key selects the AMP and a second hash places the tuple within that AMP's fragment in hash-key order, so a key lookup reaches one AMP and, on a cache miss, one disk read, and joins run as a parallel sort-merge with each operator run to completion everywhere before the next begins rather than pipelined. Tandem NonStop SQL runs applications on the same processors as the database servers over 4-plexed fibre optic rings, configures roughly one disk per MIPS with duplexed disks, range partitions relations, supports B-tree secondary indices and nested, sort-merge and hash joins, and parallelizes by inserting split and merge into the query tree. Tandem's key OLTP trick is parallel index maintenance: relations typically carry five and sometimes ten indices, and spreading them over many processors and disks holds total maintenance time almost constant as indices are added. Gamma runs on a 32-node Intel iPSC/2 Hypercube with a disk per node, offers round-robin, range, hash and hybrid-range partitioning with clustered and non-clustered B-tree or hash indices, and uses split and merge to get both partitioned and pipelined execution.

What the paper showed — measurements and proofs

The interference arithmetic that motivates shared-nothing: if adding a processor slows every other processor by 1%, the maximum achievable speedup is 37, and a thousand-processor system delivers only 4% of the effective power of a single-processor system.
Scale actually reached: the largest shared-memory multiprocessors then available were limited to about 32 processors, while Teradata, Tandem and Intel had each shipped systems with more than 200 processors, Intel was implementing a 2000-node Hypercube, and Teradata configurations could have over a thousand processors and many thousands of disks.
Oracle running on a 64-node nCUBE shared-nothing system was the first to demonstrate more than 1000 transactions per second on the industry-standard TPC-B benchmark, far in excess of Oracle's own performance on conventional mainframes in both peak performance and price/performance.
Tandem NonStop SQL scaled linearly well beyond the largest reported mainframes on the TPC-A benchmark at price/performance three times cheaper than the comparable mainframe numbers, and Gamma, Tandem and Teradata all reported near-linear speedup and scaleup on complex relational query benchmarks.
The price evidence against Grosch's law: mainframes were priced at $25,000 per MIPS and $1,000 per megabyte of RAM, while microprocessors sold at $250 per MIPS and $100 per megabyte, so combining hundreds or thousands of small systems buys more database power than a modest mainframe.
Why the authors say near-linear rather than linear: because sort costs n log n, scaling a problem up by a factor of a thousand increases n log n by a factor of 3000, a 30% deviation from linearity across three orders of magnitude of scaleup.

Limits and trade-offs — conceded and discovered

Conceded by the paper: pipelined parallelism contributes very little, because relational pipelines rarely exceed a chain of ten, sort and aggregate block until all input is consumed, and one dominant operator caps the gain, so essentially the entire win comes from partitioning.
Conceded by the paper: pathological data skew defeats the whole approach, since when many or all tuples share one join attribute value a single hash bucket receives them all and no algorithm is known to speed up or scale up; range partitioning is separately exposed to data skew and the resulting execution skew.
Conceded by the paper as open problems: mixing ad-hoc queries with OLTP (large queries hold many locks for a long time, forcing either dirty reads or versioning, and priority inversion arises when a low-priority client calls a high-priority server), optimizers that consider no parallel algorithms or plan shapes at all, missing physical-design tools, partitioning limited to a single attribute, and utilities that would take over twelve days to reorganize a terabyte at a megabyte per second unless made online, incremental, parallel and recoverable.
Conceded, and partly self-contradicting: the conclusion admits some application domains are poorly served by the relational model and calls for object-oriented database systems, and the Tokyo Super Database Computer's special-purpose hardware sorter and omega network are acknowledged to contradict the paper's own thesis that special-purpose hardware is a bad investment.
Exposed by later work: the paper treats the architecture question as settled, but cheap high-bandwidth networks and cloud object storage revived shared-disk in Oracle RAC, Amazon Aurora and Snowflake; shared-nothing's binding of data to a specific node makes elasticity, rebalancing and straggler tolerance painful, and the paper has essentially nothing to say about node failure during a long query, which MapReduce and Spark later treated as a first-order concern.

What it became — the systems that inherited it

This paper is the canonical statement of the shared-nothing, partitioned-parallel design that every massively parallel database has used since. Its split and merge operators are the direct ancestor of Volcano's exchange operator, which Goetz Graefe carried into Microsoft SQL Server and which remains how parallelism is expressed in modern optimizers; the same encapsulation idea reappears as the shuffle stage in MapReduce, Hadoop, Spark, Presto and Flink. The declustering taxonomy of round-robin, hash and range partitioning became standard physical design vocabulary and survives unchanged as sharding in Bigtable, Dynamo, Cassandra, MongoDB, Spanner and CockroachDB. Its commercial lineage runs from Teradata and Tandem NonStop SQL through IBM DB2 Parallel Edition and Informix XPS to the MPP warehouses of the 2000s, Netezza, Greenplum, Vertica and ParAccel, the last of which became Amazon Redshift. DeWitt and Gray's argument that commodity parallelism repeals Grosch's law is the economic premise of every cloud analytics service, and DeWitt himself invoked this paper's benchmarking discipline in the 2008-2009 parallel-DBMS-versus-MapReduce comparisons with Stonebraker. The one place history reversed the paper is storage: separating compute from a shared storage layer, as Snowflake, BigQuery and Aurora do, restores a shared-disk topology while keeping the partitioned dataflow execution model this paper defined.

In the paper’s words — verbatim

“Parallel database machine architectures have evolved from the use of exotic hardware to a software parallel dataflow architecture based on conventional shared-nothing hardware.”

Abstract

“The shared-nothing design moves only questions and answers through the network.”

§2.2

“Parallelism is an unanticipated benefit of the relational model.”

§2.3

Vocabulary — as this paper uses it

Linear speedup: The property that an N-times larger or more expensive system runs a fixed job N times faster, measured as small system elapsed time divided by big system elapsed time. Speedup holds the problem size constant and grows only the hardware.
Linear scaleup: The property that an N-times larger system performs an N-times larger job in the same elapsed time, so the ratio of small-system-on-small-problem time to big-system-on-big-problem time equals 1. Transaction scaleup grows the number of clients and small requests together with the database; batch scaleup runs the same single query over an N-times larger database.
Interference: The slowdown each newly added process imposes on all the others when they contend for shared resources such as a global memory, a cache or an interconnect. It is the barrier that shared-nothing architectures exist to minimize, since even 1% interference caps speedup at 37.
Skew: The condition where the variance in the size or cost of parallel steps exceeds the mean, so that the job's service time is set by its slowest step and added parallelism buys almost nothing. The paper distinguishes data skew, where one partition holds most of the tuples, from execution skew, where most of the work lands on one node.
Shared-nothing: A hardware architecture in which each memory and disk is owned by a single processor that acts as the server for that data, and processors communicate only by sending messages over an interconnection network. Because raw memory and disk accesses stay local, only filtered results cross the network.
Declustering (data partitioning): Distributing the tuples of one relation over several disks, each attached to its own processor, so that the relation can be scanned in parallel. It is the storage-level precondition for partitioned execution and provides multi-disk bandwidth without specialized RAID hardware.
Split operator: A dataflow node that partitions or replicates one operator's output stream into several independent streams, mapping attribute values of each tuple to a destination process and port. It also implements buffering and flow control, stalling its producer when output buffers fill.
Merge operator: A dataflow node that combines several parallel data streams into a single sequential stream delivered to one input port of a downstream operator. Together with split it lets unmodified sequential relational operators run in parallel.
Hash join: A join algorithm that hash partitions both relations on the join attribute, builds a main-memory hash table from one partition of the first relation, and probes it with the matching partition of the second. It has linear rather than n log n cost and tolerates skew better than sort-merge join, unless the inputs already arrive sorted.

On the timeline — where this sits in the story

Year1986–1990s

MilestoneGamma and shared-nothing parallel DB research

Problem solvedRelational query execution needed to scale beyond a single server without centralized bottlenecks.

How it solved itGamma showed how data partitioning and parallel relational operators could run on shared-nothing architectures.

Why it matteredInfluenced parallel databases, MPP warehouses, and later distributed analytical engines.

DDIACh. 7: Sharding

View on the timeline