IEEE

120

Volcano-An

TRANSACTIONSONKNOWLEDGE

AND

DATA

ENGINEERING,

VOL.

6, NO.

1, FEBRUARY

1994

Extensible and Parallel Query
Evaluation System
Goetz Graefe

Abstract-To
investigate the interactionsof extensibility
andparallelism in database query processing, we have developed a
new dataflow query execution system called Volcano. The Volcano effort provides a rich environment
for research and education in database systems design, heuristics for query optimization, parallel query execution, and resource allocation.
Volcano uses a standard interface between algebra operators, allowing easy addition of new operators and operator implementations.
Operations
on individual
items, e.g., predicates, are imported into the query processing operators using
support functions.
The semantics of support functions is notprescribed; any data type including complex objects and any
operation can be realized. Thus, Volcano is extensible with new
operators, algorithms,
data types, and type-specific methods.
Volcano includes two novel meta-operators.
The choose-planmeta-operator
supports dynamic query evaluation plans that allow delaying selected optimization
decisions until run-time,e.g., for embedded queries with free variables. The exchangemeta-operator
supports intra-operator
parallelism
on partitioned datasets and both vertical and horizontal inter-operator
parallelism, translating between demand-driven
dataflow withinprocesses and data-driven
dataflow between processes.
All operators, with the exception of the exchange operator,
have been designed and implemented
in a single-process environment, and parallelizedusing the exchange operator. Even
operators not yet designed can be parallelizedusing this new
operator if they use and provide the interator interface. Thus,
the issues of data manipulationand parallelism
have become
orthogonal, making Volcano the first implemented
query execution engine that effectively combines extensibility
and parallelism.
Index Terms-Dynamic
query evaluationplans, extensible
database systems, iterators, operator model of parallelization,
query execution.

I. INTRODUCTION
N ORDER to investigate the interactions of extensibility, efficiency, and parallelism in database query processing and to provide a testbed for databse systems research and education, we have designed and implemented
a new query evaluation system called Volcano. It is intended to provide an experimental vehicle for research intoquery execution techniques and query optimization
optimization heuristics rather than a database system readyto support applications. It is not a complete database sys-

I

Manuscript
received July 26, 1990; revised September
5, 1991. This
work was supported
in part by the National
Science Foundation
under
Grants IRI-8996270,
IRI-8912618,
and IRI-9006348,
and by the Oregon
Advanced
ComputingInstitute (OACIS).
The author is with the Computer
Science Department,
Portland
State
University,
Portland, OR 97207-075 1.
IEEE Log Number 92 11308.
1041-4347/94$04.00

tern as it lacks features such as a user-friendly query language, a type system for instances (record definitions), a
query optimizer, and catalogs. Because of this focus, Volcano is able to serve as an experimental vehicle for a multitude of purposes, all .of them open-ended, which results
in a combination of requirements that have not been integrated in a single system before. First, it is modular andextensible to enable future research, e.g., on algorithms,
data models, resource allocation, parallel execution, loadbalancing, and query optimization heuristics. Thus, Volcano provides an infrastructure for experimental researchrather than a final research prototype in itself. Second, it
is simple in its design to allow student use and research.
Modularity and simplicity are very important for this purpose because they allow students to begin working on
projects without an understanding of the entire design andall its details, and they permit several concurrent student
projects. Third, Volcano’s design does not presume any
particular data model; the only assumption is that query
processing is based on transforming sets of items usingparameterized operators. To achieve data model independence, the design very consistently separates set processing control (which is provided and inherent in the Volcano operators) from interpretationand manipulationofdata items (which is imported into the operators, as described later). Fourth, to free algorithm design, implementation, debugging, tuning, and initial experimentationfrom the intricacies of parallelism but to allow experimentation with parallel query processing. Volcano can beused as a single-process or as a parallel system. Singleprocess query evaluation plans can already be parallelizedeasily on shared-memory machines and soon also on distributed-memorymachines. Fifth, Volcano is realistic in
its query execution paradigm to ensure that students learn
how query processing is really done in commercial database products. For example, using temporary files totransfer data from one operation to the next as suggested
in most textbooks has a substantial performance penalty,
and is therefore used in neither real database systems nor
in Volcano. Finally, Volcano’s means for parallel query
processing could not be based on existing models since
all models explored to date have been designed with aparticular data model and operator set in mind. Instead,our design goal was to make parallelism and data manipulation orthogonal, which means that the mechanisms forparallel query processing are independent of the operator
set and semantics, and that all operators, including new@ 1994 IEEEGRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEM

ones, could be designed and implemented independentlyof future parallel execution.
Following a design principle well established in operating systems research but not exploited in most databasesystem designs, Volcano provides mechanisms to support
policies. Policies can be set by a human experimenter orby a query optimizer. The separation of mechanisms andpolicies has contributed to the extensibility and modularity of modern operating systems, and may make the same
contribution to extensible database systems. We will return to this separation repeatedly in this paper.
Since its very purpose is to allow future extensions andresearch, Volcano is continuously being modified and extended. Among the most important recent extensions were
the design and implementationof two meta-operators.
Both of them are not only new operators but also embody
and encapsulate new concepts for query processing. They
are meta-operators since they do not contribute to data
manipulation,
selection, derivation, etc., but instead provide additional control over query processing that cannot
be provided by conventional operators like file scan, sort,and merge join. The choose-plan operator implements dynamic query evaluation plans, a concept developed for
queries that must be optimized with incomplete information [ 171. For example, it is not possible to reliably optimize an embedded query if one of the constants in thequery predicate is actually a program variable and therefore unknown during compilation and optimization.
Dynamic plans allow preparation for multiple equivalentplans, each one optimal for a certain range of actual parameter values. The choose-plan operator selects among
these plans at runtime while all other operators in Volcano’s operator set (present or future) are entirely oblivious to the presence and function of the choose-plan operator.
The second meta-operator, the exchange operator, implements and controls parallel query evaluation in Volcano. While operators can exchange data without the exchange operator, in fact within processes as easily as asingle procedure call, this new operator exchanges data
across process and processor boundaries. All other operators are implemented and execute without regard to parallelism; all parallelism issues like partitioning and flow
control are encapsulated in and provided by the exchange
operator. Thus, data manipulation and parallelism are indeed orthogonal in Volcano [20]. Beyond the cleanlinessfrom a software engineering point of view, it is also very
encouraging to see that this method of parallelizingaquery processing engine does indeed allow linear or nearlinear speedup [ 181.
This paper is a general overview describing the overaii
goals and design principles. Other articles on Volcano
were written on special aspects of the system, e.g., [ 16][21], [25], [26]. These articles also include experimental
performance evaluations of Volcano’s techniques and algorithms, in particular [ 181, [2 11.
The present paper is organized as follows. In the following section, we briefly review previous work that in-121

fluenced Volcano’s design. A detailed description of Volcano follows in Section III. Section IV contains a
discussion of extensibility in the system. Dynamic query
evaluation plans and their implementation
are describedin Section V. Parallel processing encapsulated in the exchange module is described in Section VI. Section VII
contains a summary and our conclusions from this effort.
II. RELATED WORK
Since so many different systems have been developed
to process large datesets efficiently, we only survey thesystems that have significantly influenced the design ofVolcano. Our work has been influenced most strongly by
WiSS, GAMMA,
and EXODUS. The Wisconsin Storage
System (WiSS) [lo] is a record-oriented file system providing heap files, B-tree and hash indexes, buffering, andscans with predicates. GAMMA[ 1 l] is a software database machine running on a number of general-purpose
CPU’s as a backend to a UNIX host machine. It was developed on 17 VAX 11/750’s connected with each otherand the VAX 11/750 host via a 80 Mb /s token ring. Eight
GAMMA processors had a local disk device, accessed using WiSS. The disks were accessible only locally, andupdate and selection operators used only these eight processors. The other, diskless processors were used for join
processing. Recently, the GAMMA
software has been
ported to an Intel iPSC/2 hypercube with 32 nodes, eachwith a local disk drive. GAMMA uses hash-based algorithms extensively, implemented in such a way that each
operator is executed on several (usually all) processors
and the input stream for each operator is partitioned into
disjoint sets according to a hash function.
The limited data model and extensibility of GAMMA
led to the search for a more flexible but equally powerful
query processing model. The operator design used in the
GAMMA database machine software gives each operator
control within its own process, leaving it to the networking and operating system software to synchronize multiple operators in producer-consumer
relationships using
flow-control mechanisms. This design, while working extremely well in GAMMA,
does not lend itself to singleprocess query evaluation since multiple loci of control,i.e., multiple operators, cannot be realized inside a single
process without special pseudo-multiprocess
mechanisms
such as threads. Therefore, GAMMA’s
operator and datatransfer concepts are not suitable for an efficient query
processing engine intended for both sequential and parallel query execution.
EXODUS[7] is an extensible database system withsome components followiong the “tool-kit”
approach,e.g., the optimizer generator [ 131, [ 141 and the E database
implementation
language [27], [28], and other components built as powerful but fixed components, e.g., thestorage manager [5]. Originally,
EXODUS. was conceived to be data-model-independent,i.e., it was supposed to support a wide variety of data models, but latera novel, powerful, structurally object-oriented data model
called Extra was developed [6]. The concept of data model

122

IEEE

TRANSACTIONSON KNOWLEDGE

independence as first explored in EXODUS has been retained in the Volcano project and the design and implementation of its software. During the design of the EXODUS storage manager, many storage and access issues
explored in WiSS and GAMMA were revisited. Lessons
learned and trade-offs explored in these discussions certainly helped in forming the ideas behind Volcano. The
design and development of E influenced the strong emphasis on iterators for query processing.
A number of further conventional (relational) and extensible systems have influenced our design. Ingres [32]and System R [9] have probably influenced most databasesystems, in particular their extensible follow-on projects
Starburst [23] and Postgres [35]. It is interesting to notethat independently of our work the Starburst group has
also identified the demand-driven interator paradigm as asuitable basis for an extensible single-process query evaluation architecture after using it successfully in the System R relational system, but as yet has not been able tocombine extensibility
with parallelism.
GENESIS[ l]early on stressed the importance of uniform operator interfaces for extensibility and software reusability.
XPRS has been the first project aiming to combine extensibility with parallelism [34]. Its basic premise is toimplement Postgres on top of RAID disk arrays and the
Sprite operating system. XPRS and GAMMA
basically
differ in four ways. First, GAMMA supports. a purely relational data model while XPRS supports an extensible
relational model, Postgres. Second, GAMMA’s
mainform of parallelism is intra-operator parallelism based onpartitioned data sets. XPRS, on the other hand, will rely
on bushy parallelism, i.e. , concurrent execution of different subtrees in a complex query evaluation plan. Third,
GAMMA relies heavily on hashing for joins and aggregations whereas XPRS will have a mainly sort-based
query processing engine [33]. Fourth, GAMMA
is builton the premise that distributed memory is required toachieve scalable linear speed-up while XPRS is being implemented on a shared-memory machine.
Both XPRS and Volcano combine parallelism and extensibility, but XPRS is a far more comprehensive project
than Volcano. In particular, XPRS includes a data modeland a query optimizer. On the other hand, Volcano is more
extensible precisely because it does not presume a data
model. Therefore, Volcano could be used as the query
processing engine in a parallel extensible-relational
system such as XPRS. Moreover, it will eventually include
a data-model-independent
optimizer generator to form acomplete query processing research environment.
III. VOLCANO SYSTEM DESIGNIn this section, we provide an overview of the designof Volcano. At the current time, Volcano is a library of
about two dozen modules with a total of about 15 000lines of C code. These modules include a file system,
buffer management,sorting, Bf-trees, and two algorithms each (sort- and hash-based) for natural join, semi-

AND

DATA

ENGINEERING,

VOL.

6, NO.

1, FEBRUARY

1994

join, all three outer joins, anti-joint, aggregation, duplicate elimination,
union, intersection, difference, anti-difference, and relational division. Moreover, two modules
implement dynamic query evaluation plans and allow parallel processing of all algorithms listed above.
All operations on individual records are deliberately left
open for later definition. Instead of inventing a language
in which to specify selection predicates, hash functions,etc., functions are passed to the query processing operators to be called when necessary with the appropriate arguments. These support jkzctions are described later inmore detail. One common and repeating theme in the design of Volcano is that it provides mechanisms for query
evaluation to allow selection of and experimentation
withpolicies. The separation of mechanisms and policies is avery well-known and well-established principle in the design and implementationof operating systems, but it has
not been used as extensively and consistently in the design and implementationof database systems. It has contributed significantly to the extensibility
and modularityof modem operating systems, and may make the same
contribution to extensible database systems.
Currently, Volcano consists of two layers, the file system layer and the query processing layer. The former provides record, file, and index operations including scanswith optional predicates, and buffering; the latter is a setof query processing modules that can be nested to build
complex query evaluation trees. Fig. 1 identifies Volcano’s main modules. This separation can be found in
most query evaluation systems, e.g., RSS and RDS in
System R [9] and Core and Corona in Starburst [23]. System catalogs or a data dictionary are not included in Volcano since the system was designed to be extensible andindependent from any particular data model. We start ourdescription at the bottom, the file system, and then discuss the query processing modules.
A. The File System
Within our discussion of the Volcano file system, we
also proceed bottom-up, from buffer management to data
files and indices. The existing facilities are meant to provide a backbone of a query processing system, and aredesigned such that modifications and additions can easilybe accomplished as the need arises.
The buffer manager is the most interesting part of thefile system. Because buffer management is performancecritical in any database system, the Volcano buffer manager was designed to include mechanisms that can be usedmost effectively and efficiently in a large variety of contexts and with a wide array of policies. In consequence,
its features include multiple buffer pools, variable-length
units of buffering that are called clusters in Volcano, andreplacement hints from the next higher software level.
The buffer manager’s hint facility is an excellent example of Volcano’s design principle to implement mechanisms to support multiple policies. The buffer manager
only provides the mechanisms, i.e., pinning, page re-GRAEFE:

VOLCANO-QUERYExecute (driver)
Hash One-to-One Match
Hash One-to-Many
Match
scans
Files & Records
Physical I/O
Fig.

EVALUATIONSYSTEM

Exchange
Sort One-to-One Mate h
Sort One-to-Many Match
Functional Join
Devices
Buffer Manager
1. Volcano’s

Choose-Plan
sort
Index Maintenance
FilterIndices (B+-trees)
Memory Manager

main modules.

placement, and reading and writing disk pages, while thehigher level software determines the policies depending
on data semantics, importance, and access patterns. It issurprising that database buffer managers derive replacement decisions from observed reference behavior in spiteof the fact that this behavior is generated by higher level
database software and thus known and foreseeable in advance within the same system, albeit different subcomponents.
Files are composed of records, clusters, and extents.
Since file operations are invoked very frequently in any
database system, all design decisions in the file module
have been made to provide basic functionality
with thehighest attainable performance. A cluster, consisting of
one or more pages, is the unit of I/O and of buffering, as
discussed above. The cluster size is set for each file individually.
Thus, different files on the same device canhave different cluster sizes. Disk space for files is allocated in physically contiguous extents, because extents
allow very fast scanning without seeks and large-chunkread-ahead and write-behind.
Records are identified by a record identifier (RID), andcan be accessed directly using the RID. For fast access toa large set of records, Volcano supports not only individual file and record operations but also scans that support
read-next and append operations. There are two interfaces
to file scans; one is part of the file system and is described
momentarily;
the other is part of the query processing
level and is described later. The first one has the standard
procedures for file scans, namely open, next, close, andrewind. The next procedure returns the main memory address of the next record. This address is guaranteed(pinned) until the next operation is invoked on the scan.
Thus, getting the next record within the same cluster does
not require calling the buffer manager and can be performed very efficiently.
For fast creation of files, scans support an append operation. It allocates a new record slot, and returns the newslot’s main memory address. It is the caller’s responsibility to fill the provided record space with useful information, i.e., the append routine is entirely oblivious to thedata and their representation.
Scans also support optional predicates. The predicate
function is called by the next procedure with the argument
and a record address. Selective scans are the first example
of support functions mentioned briefly in the introduction.
Instead of determining
a qualification
itself, the scanmechanism relies on a predicate function imported froma higher level.
Support functions are passed to an operation as a function entry point and a typeless pointer that serves as a123

predicate argument. Arguments to support functions canbe used in two ways, namely in compiled and interpreted
query execution. In compiled scans, i.e., when the predicate evaluation function is available in macvhine code,
the argument can be used to pass a constant or a pointerto several constants to the predicate function. For example, if the predicate consists of comparing a record fieldwith a string, the comparison function is passed as predicate function while the search string is passed as predicate argument. In interpreted scans, i.e., when a generalinterpreter is used to evaluate all predicates in query, they
can be used to pass appropriate code to the interpreter.
The interpreter’s entry point is given as predicate function. Thus, both interpreted and compiled scans are supported with a single simple and efficient mechanism. Volcano’s use of support functions and their arguments is
another example for a mechanism that leaves a policy decision, in this case whether to use compiled or interpretedscans, open to be decided by higher level software.
Zndices are implemented currently only in the form of
B + -trees with an interface similar to files. A leaf entry
consists of a key and information.
The information parttypically is a RID, but it could include more or different
information. The key and the information can be of any
type; a comparison function must be provided to compare
keys. The comparison function uses an argument equivalent to the one described for scan predicates. Permitting
any information in the leaves gives more choices in physical database design. It is another example of Volcano
providing a mechanism to allow a multitude of designs
and usage policies. B + -trees support scans similar to files,
including predicates and append operations for fast loading. In addition, B f -tree scans allow seeking to a particular key, and setting lower and upper bounds.
For intermediate results in query processing (later calledstreams), Volcano uses special devices called virtual devices. The difference between virtual and disk devices isthat data pages of virtual devices only exist in the buffer.
As soon as such data pages are unpinned, they disappear
and their contents are lost. Thus, Volcano uses the samemechanisms and function calls for permanent and intermediate data sets, easing implementationof new operators significantly.
In summary, much of Volcano’s file system is conventional in its goals but implemented in a flexible, efficient,and compact way. The file system supports basic abstractions and operations, namely devices, files, records,
B+-trees, and scans. It provides mechanisms to accessthese objects, leaving many policy decisions to higher
level software. High performance was a very important
goal in the design and implementationof these mechanisms since performance studies and parallelization
only
make sense if the underlying mechanisms are efficient.
Furthermore, research into implementationand performance trade-offs for extensible database systems and new
data models is only relevant if an efficient evaluation platform is used.

124

IEEE

TRANSACTIONSON KNOWLEDGE

B. Query Processing
The file system routines described above are utilized by
the query processing routines to evaluate complex queries. Queries are expressed as query plans or algebra
expressions; the operators of this algebra are query processing algorithms and we call the algebra an executablealgebra as opposed to logical algebras, ‘e .g . , relational
algebra. We will describe the operations using relationalterminology hoping that this will assist the reader. We
must point out, however, that the operations can beviewed and are implemented as operations on sets of objects, and that Volcano does not depend on assumptions
about the internal structure of such objects. In fact, we
intend to use Volcano for query processing in an objectoriented database system [ 151. The key to this use of Volcano is that set processing and interpretation of data items
are separated.
In Volcano, all algebra operators are implemented as
iterators, i.e., they support a simple open-next-close protocol. Basically, iterators provide the iteration componentof a loop, i.e., initialization,
increment, loop termination
condition, and final housekeeping. These functions allow“iteration’ ’ over the results of any operation similar to
the iteration over the result of a conventional file scan.
Associated with each iterator is a state record type. A
state record contains arguments, e.g., the size of a hashtable to be allocated in the open procedure, and state, e.g.,
the location of a hash table. All state information of an
iterator is kept in its state record and there are no ‘ ‘static’ ’variables; thus, an algorithm may be used multiple times
in a query by including more than one state record in thequery.
All manipulationand interpretationof data objects,
e*g*, comparisons and hashing, is passed to the iterators
by means of pointers to the entry points of appropriate
support functions. Each of these support functions uses
an argument allowing interpreted or compiled query evaluation, as described earlier for file scan predicates. Without the support functions, Volcano’s iterators are empty
algorithm shells that cannot perform any useful work. In
effect, the split into algorithm shells and support functions
separates control and iteration over sets from interpretation of records or objects. This separation is one of thecornerstones’ of Volcano’s data model independent andextensibility, which will be discussed in Section IV.
Iterators can be nested and then operate similarly tocoroutines. State records are linked together by means of
input pointers. The input pointers are also kept in the state
records. Fig. 2 shows two operators in a query evaluation
plan. Purpose and capabilities of the Jilter operator will
be discussed shortly; one of its possible functions is toprint items of a stream using a function passed to the filter
operator as one of its arguments. The structure at the top
gives access to the functions as well as to the state record.
Using a pointer to this structure, the filter functions canbe called and their local state can be passed to them as aprocedure argument. The functions themselves, e. g . ,

AND

DATA

ENGINEERING,

VOL.

6, NO.

1, FEBRUARY

1994.
w open-filter
w next-filter* close-filter

()
()
()

..
Arguments

1
print 0

!
...
..

..
Input
\
\

i
...
..

State

&I-

open-file-scan()fpredicateFig. 2. Two operators

in a query()

evaluationplan.

open--Zter, can use the input pointer contained in the state
record to invoke the input operator’s functions. Thus, thefilter functions can invoke the file scan functions asneeded, and can pace the file scan according to the needsof the filter. In other words, Fig. 2 shows a complete query
evaluation plan that prints selected records from a file.
Using Volcano’s standard form of iterators, an operator
does not need to know what kind of operator produces its
input, or whether its input comes from a complex query
tree or from a simple file scan. We call this concept anonymous inputs or streams. Streams are a simple but powerful abstraction that allows combining any number andany kind of operators to evaluate a complex query, a second cornerstone to Volcano’s extensibility. Together with
the iterator control paradigm, streams represent the mostefficient execution model in terms of time (overhead forsynchronizing operators) and space (number of records
that must reside in memory concurrently) for single-process query evaluation.
Calling open for the top-most operator results in instantiations for the associated state record’s state, e.g., allocation of a hash table, and in open calls for all inputs. In
this way, all iterators in a query are initiated recursively.
In order to process the query, next for the top-most operator is called repeatedly until it fails with an end-ofstream indicator. The top-most operator calls the next
procedure of its input if it needs more input data to produce an output record. Finally, the close call recursively“shuts down” all iterators in the query. This model ofquery execution matches very closely the ones being ineluded in the E database implementation
language in EXODUS and the query executor of the Starburst relational
database system.

GRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEM

A number of query and environment parameters may
influence policy decisions during opening a query evaluation plan, e.g., query predicate constants and system load
information. Such parameters are passed between all open
procedures in Volcano with a parameter called bindings.
This is a typeless pointer that can be used to pass information for policy decisions. Such policy decisions are implemented using support functions again. For example,
the module implementing
hash join allows dynamic determination of the size of a hash table-anotherexampleof the separation of mechanism and policy. This bindings
parameter is particularly useful in dynamic query evaluation plans, which will be discussed later in Section V.
The tree-structured query evaluation plan is used to execute queries by demand-driven
dataflow. The return
value of a next operation is, besides a status indicator, astructure called Next-Record, which consists of an RID
and a record address in the buffer pool. This record ispinned in the buffer. The protocol about fixing and unfixing records is as follows. Each record pinned in the buffer
is owned by exactly one operator at any point in time.
After receiving a record, the operator can hold on to it fora while, e.g., in a hash table, unfix it, e.g., when a predicate fails, or pass it on to the next operator. Complex
operations that create new records, e.g., join, have to fix
their output records in the buffer before passing them on,
and have to unfix their input records. Since this could result in a large number of buffer calls (one per record ineach operator in the query), the interface to the buffer
manager was recently redesigned such that it will requirea total of two buffer calls per cluster on the procedure side(e. g ., a file scan) independently of how many records acluster contains, and only one buffer call per cluster on
the consumer side.
A Next-Record structure can point to one record only.
All currently implemented
query processing algorithms
pass complete records between operators, e.g., join creates new, complete records by copying fields from two
input records. It can be argued that creating complete newrecords and passing them between operators is prohibitively expensive. An alternative is to leave original records in the buffer as they were retrieved from the stored
data, and compose Next-Record pairs, triples, etc., as intermediate results. Although this alternative results in lessmemory-to-memory
copying, it is not implemented
explicitly because Volcano already provides the necessary
mechanisms, namely the Biter iterator (see next subsection) that can replace each record in a stream by an RIDpointer pair or vice versa.
In summary, demand-driven dataflow is implemented
by encoding operators as iterators, i.e., with open, next,
and close procedures, since this scheme promises generality , extensibility, efficiency, and low overhead. The next
few sections describe some of Volcano’s existing iterators
in more detail. In very few modules, the described operators provide much of the functionalityof other query
evaluation systems through generality and separation of125

mechanisms and policies. Furthermore, the separation ofset processing control (iteration) from item interpretationand manipulation
provides this functionality
independently from any data model.
1) Scans, Functional Join, and Filter: The first scaninterface was discussed with the file system. The second
interface to scans, both file scans and B+-tree scans, provides an iterator interface suitable for query processing.
The open procedures open the file or B+-tree and initiatea scan using the scan procedures of the file system level.
The file name or closed file descriptor are given in thestate record as are an optional predicate and bounds for
B+-tree scans. Thus, the two scan interfaces are functionally equivalent. Their difference is that the file system scaninterface is used by various internal modules, e.g., by thedevice module for the device table of contents, while theiterator interface is used to provide leaf operators for query
evaluation plans.
Typically, Bf-tree indices hold keys and RID’s in theirleaves. In order to use B+-tree indices, the records in thedata file must be retrieved. In Volcano, this look-up operation is split from the B+-tree scan iterator and is performed by the functional join operator. This operator requires a stream of records containing RID’s as input andeither outputs the records retrieved using the RID’s or itcomposes new records from the input records and the retrieved records, thus “joining”
the B+-tree entries andtheir corresponding data records.
B’-tree scan and functional join are separated for anumber of reasons. First, it is not clear that storing data
in B+-tree leaves never is a good idea. At times, it may
be desirable to experiment with having other types of information associated with look-up keys. Second, this separation allows experimentation
with manipulation of RIDlists for complex queries. Third, while functional join iscurrently implemented rather naively, this operation canbe made more intelligent to assemble complex objects recursively. In summary, separating index search and record retrieval is another example for providing mechanisms in Volcano to allow for experiments with policies,
a design principle employed to ensure that the Volcano
software would be flexible and extensible.
The filter operator used in the example above performs
three functions, depending on presence or absence of corresponding support functions in the state record. The
predicate function applies a selection predicate, e.g., toimplement bit vector filtering. The transform function
creates a new record, typically of a new type, from eachold record. An example would be a relational projection(without duplicate elimination).
More complex examples
include compression and decompression, other changes incodes and representations, and reducing a stream of records to RID-pointer pairs. Finally, the apply function is
invoked once on each record for the benefit of its side
effects. Typical examples are updates and printing. Notice that updates are done within streams and query evaluation plans. Thus, Volcano plans are not only retrieval

126

IEEE

TRANSACTIONS

ON

but also update plans. The filter operator is also called the‘ ‘side-effect operator. ’ ’ Another example is creating a filter for bit vector filtering. In other words, the filter operator is a very versatile single-input single-output operator that can be used for a variety of purposes. Bit vector
filtering is an example for a special version of separationof policy and mechanism, namely the rule not to provide
an operation that can be composed easily and efficiently
using existing operations.
2) One-to-One Match: Together with the filter operator, the one-to-one match operator will probably be among
the most frequently used query processing operators in
Volcano as it implements a variety of set-matching functions. In a single operator, it realizes join, semi-join, outer
joint, anti-joint, intersection, union, difference, anti-difference, aggregation, and duplicate elimination.
The oneto-one match operator is a physical operator like sort, i.e.,part of the executable algebra, not a logical operator likethe operators of relational algebra. It is the operator that
implements all operations in which an item is included in
the output depending on the result of a comparison between a pair of items.
Fig. 3 shows the basic principle underlying the one-toone match operator for binary operations, namely separation of the matching and non-matching components of
two sets, called R and S in the Fig. 3, and producing appropriate subsets, possibly after some transformation andcombination as in the case of a join. Since all these operations require basically the same steps, it was logical to
implement them in one general and efficient module. The
main difference between the unary and binary operations,e. g . , aggregate functions and equi-join, is that the former
require comparing items of the same input while the latter
require comparing items of two different inputs.
Since the implementationof Volcano’s one-to-one
match is data-model-independentand all operations ondata items are imported via support functions, the module
is not restricted to the relational model but can perform
set matching functions for arbitrary data types. Furthermore, the hash-based version provides recursive hash table overflow avoidance [ 121 and resolution similar to hybrid hash join [31] and can therefore handle very large
input sizes. The sort-based version of one-to-one matchis based on an external sort operator and can also operate
on arbitrarily large inputs.
While there seems to be an abundance of join algorithms, our design goals of extensibility and limited system size led to the choice of only two algorithms (at thecurrent time) to be implemented
in Volcano, namely
merge join and hybrid hash join. This choice will also
allow experimental research into the duality and trade-offs
between sort- and hash-based query processing algorithms.
The classic hash join algorithm (which is the in-memory component of hybrid hash join) proceeds in twophases. In the first phase, a hash table is built from one
input; it is therefore called the build phase. In the second
phase, the hash table is probed using tuples from the other

KNOWLEDGE

AND

DATA

ENGINEERING,

VOL.

R

0
B
C
A B
A, c
B, c
&B,C

B

Full Match
Difference
Intersection
Difference
Anti-difference
Union
Fig.

3. Binary

1, FEBRUARY

1994

S

A

outputA

6, NO.

one-to-one

C

Attribute match
Anti-semi-join
Join, semi-join
Anti-semi-join
Left outer join
Anti-join
Right outer join
Symmetric outer join
matching.

input to determine matches and to compose output tuples;
it is called the probe phase. After the probe phase, thehash table and its entries are discarded. Instead, our oneto-one match operator uses a third phase called the flush
phase, which is needed for aggregate functions and someother operations.
Since the one-to-one match operator is an interator likeall Volcano operators, the three phases are assigned to theopen, next, and close functions. Open includes the build
phase, while the other two phases are included in the next
function. Successive invocations of the next function automatically switch from the probe phase to the flush phasewhen the second input is exhausted.
The build phase can be used to eliminate duplicates orto perform an aggregate function in the build input. The
one-to-one match module does not require a probe input;
if only an aggregation is required without subsequent join,
the absence of the probe input in the state record signals
to the module that the probe phase should be skipped. For
aggregation, instead of inserting a new tuple into the hashtable as in the classic hash join, an input tuple is firstmatched with the tuples in its prospective hash bucket. If
a match is found, the new tuple is discarded or its values
are aggregated into the existing tuple.
While hash tables in main memory are usually quite
fast, a severe problem occurs if the build input does not
fit in main memory. This situation is called hash tableoveflow. There are two ways to deal with hash table overflow. First, if a query optimizer is used and can anticipate
overflow, it can be avoided by partitioning the input(s).
This overjlow avoidance technique is the basis for the hashjoin algorithm used in the Grace database machine [ 121.
Second, overflow files can be created using oveflow resolution after the problem occurs.
For Volcano’s one-to-one match, we have adopted hybrid hash join. Compared to the hybrid hash algorithm
used in GAMMA,
our overflow resolution scheme has
several improvements. Items can be inserted into the hash

GRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEM

table without copying, i.e., the hash table points directly
to records in the buffer as produced by one-to-one match’s
build input. If input items are not densely packed, however, the available buffer memory can fill up very quickly.
Therefore, the one-to-one match operator has an argument called the packing threshold. When the number of
items in the hash table reaches this threshold, items arepacked densely into overflow files. However, the clusters(pages) of these overflow files are not yet unfixed in thebuffer, i.e., no Z/O is performed as yet. Only when thenumber of items in the hash table reaches a second threshold called spilling threshold is the first of the partition
files unfixed. The clusters of this file are written to disk
and the count of items in the hash table, accordingly reduced. When this number reaches the spilling thresholdagain, the next partition is unfixed, etc. If necessary, partitioning is performed recursively, with automatically adjusted packing and spilling thresholds. The unused portions of the hash table, i.e., the portions corresponding tospilled buckets, are used for bit vector filtering to save
Z/O to overflow files.
The fan-out of the first partitioning step is determinedby the total available memory minus the memory required
to reach the packing threshold. By choosing the packing
and spilling thresholds, a query optimizer can avoid record copying entirely for small build inputs, specify
overflow avoidance (and the maximum fan-out) for verylarge build inputs, or determine packing and spilling
thresholds based on the expected build input size. In fact,
because the input sizes cannot be estimated precisely if
the inputs are produced by moderately complex expressions, the optimizer
can adjust packing and spilling
thresholds based on the esimated probability distributionsof input sizes. For example, if overflow is very unlikely,
it might be best to set the packing threshold quite highsuch that, with high probability,
the operation can proteed without copying. On the other hand , if overflow ismore likely, the packin g th reshold should be set lower toobtain a larger partitioning fan-out.
The initial packing and spilling thresholds can be set tozero; in that case, Volcano’s one-to-one match performs
overflow avoidance very similar to the join algorithm usedin the Grace database machine. Beyond this parameterization of overflow avoidance and resolution, Volcano’s
one-to-one match algorithm also permits optimizations ofcluster size and recursion depth similar to the ones used
for sorting [4], [21] and for nonuniform hash value distributions, and it can operate on inputs with variablelength records.
The extension of the module described so far to set operations started with the observation that the intersectionof two union-compatible
relations is the same as the natural join of these relations, and can be best implemented
as semi-join. The union is the (double-sided) outer joinof union-compatible
relations. Difference and anti-difference of two sets can be computed using special settingsof the algorithm’s bells and whistles. Finally, a Cartesian127

product can be implemented by matching successfully all
possible pairs of items from the two inputs.
A second version of one-to-one match is based on sorting. Its two modules are a disk-based merge-sort and theactual merge-join. Merge-join has been generalized similarly to hash-join to support semi-join, outer join, antijoin, and set operations. The sort operator has been implemented in such a way that it uses and provides the iterator interface. Opening the sort iterator prepares sorted
runs for merging. If the number of runs is larger than the
maximal fan-in, runs are merged into larger runs until theremaining runs can be merged in a single step. The final
merge is performed on demand by the next function. If
the entire input fits into the sort buffer, it is kept there
until demanded by the next function. The sort operator
also supports aggregation and duplicate elimi nation. It canperform these operations early, i.e., while writing temporary files [2]. The sort algorithm is described and evaluated in detail in [2 11.
In summary, Volcano’s one-to-one match operators arevery powerful parts of Volcano’s query execution algebra. By separating the control required to operate on setsof items and the interpretation and manipulationof individual items it can perform a variety of set matching tasks
frequently used in database query processing, and canperform these tasks for arbitrary data types and data
models. The separation of mechanisms and policies foroverflow management supports overflow avoidance aswell as hybrid hash overflow resolution, both recursively
if required. Implementing
sort- and hash-based algorithms in a comparable fashion will allow meaningful experimental research into the duality and trade-offs between sort- and hash-based query processing algorithms.
The iterator interface guarantees that the one-to-one match
operator can easily be combined with other operations,
including new iterators yet to be designed.
3) One-to-Many Match: While the one-to-one match
operator includes an item in its output depending on acomparison of two items with one another, the one-tomany m atch o perator compa res each item with a numberof other items to determine wh .ether a new item is to be
produced. A typical example is relational division, the relational algebra operator corresponding to universa 1 quantification in relational calculus. There are two versions ofrelational division in Volcano. The first version, called
native division, is based on sorting. The second version,
called hash-division, utilizes two hash tables, one on thedivisor and one on the quotient. An exact description of
the two algorithms and alternative algorithms based on
aweg ate functions can be found in [ 161 along with analytical and experimenta 1 performance comparisons anddetailed discussions of two partitioning strategies for hashtable overflow and multiprocessor implementations.
We
are currently studying how to generalize these algorithms in a way comparable with the generalizations of
aggregation and join, e.g., for a majority
function

PI .

IEEE

TRANSACTIONS

ON

IV. EXTENSIBILITY
A number of database research efforts strive for extensibility, e.g., EXODUS, GENESIS, Postgres, Starburst,
DASDBS [30], Cactis [24], and others. Volcano is a very
open query evaluation architecture that provides easy extensibility. Let us consider a number of frequently proposed database extensions and how they can be accommodated in Volcano.
First, when extending the object type system, e.g., witha new abstract data type (ADT) like date or box, the Volcano software is not affected at all because it does notprovide a type system for objects. All manipulation of andcalculation based on individual objects is performed by
support functions. To a certain extent, Volcano is incomplete (it is not a database system), but by separating set
processing and instance interpretationand providing awell-defined interface between them, Volcano is inherently extensible on the level of instance types and semantics.
As a rule, data items that are transferred between operators using some next iterator procedure are records. For
an extensible or object-oriented
database system, thiswould be an unacceptable problem and limitation.
The
solution to be used in Volcano is to pass only the root
component (record) between operators after loading andfixing necessary component records in the buffer and suitably swizzling inter-record pointers. Very simple objects
can be assembled in Volcano with the functional join operator. Generalizations of this operator are necessaryfor,object-oriented
or non-first-normal-form
database systems, but can be included in Volcano without difficulty.
In fact, a prototype for such an assembly operator has been
built [26] for use in the REVELATION object-oriented database systems project [ 151.
Second, in order to add new functions on individual
objects or aggregate functions, e.g., geometric mean, tothe database and query processing system, the appropriate
support function is required and passed to a query processing routine. In other words, the query processing routines are not affected by the semantics of the support functions as long as interface and return values are correct.
The reason Volcano software is not affected by extensionsof the functionality on individual objects is that Volcano’s
software only provides abstractions and implementations
for dealing with and sequencing sets of objects using
streams, whereas the capabilities for interpreting and manipulating individual objects are imported in the form of
support functions.
Third, in order to incorporate a new access method,e.g., multidimensional
indices in form of R-trees [22],appropriate iterators have to be defined. Notice that it
makes sense to perform not only retrieval but also maintenance of storage structures in the form of iterators. For
example, if a set of items defined via a predicate (selection) needs to be updated, the iterator or query tree implementing the selection can “feed” its data into a maintenance iterator. The items fed into the maintenance
operator should include a reference to the part of the stor-

KNOWLEDGE

AND

DATA

ENGINEERING,

VOL.

6, NO.

1, FEBRUARY

1994

age structure to be updated, e.g., a RID or a key, andappropriate new values if they have been computed in theselection, e.g., new salaries from old salaries. Updating
multiple structures (multiple indices) can be organized andexecuted very efficiently using nested iterators, i.e., aquery evaluation plan. Furthermore, if ordering makes
maintenance more efficient as for B-trees, an ordering or
sort iterator can easily be included in the plan. In otherwords, it makes sense to think of plans not only as queryplans used in retrieval but also as “update plans” or combinations of retrieval and update plans. The stream concept is very open; in particular, anonymous inputs shieldexisting query processing modules and the new iteratorsfrom one another.
Fourth, to include a new query processing algorithm inVolcano, e.g., an algorithm for transitive closure or nest
and unnest operations for nested relations, the algorithm
needs to be coded in the iterator paradigm. In other words,
the algorithm implementationmust provide open, next,
and close procedures, and must use these procedures for
its input stream or streams. After an algorithm has beenbrought into this form, its integration with Volcano istrivial. In fact, as the Volcano query processing software
became more complex and complete, this was done anumber of times. For example, the one-to-many match ordivision operators [ 161 were added without regard to theother operators, and when the early in-memory-onlyversion of hash-based one-to-one match was replaced by theversion with overflow management described above, noneof the other operators or meta-operators
had to bechanged. Finally, a complex object assembly operator wasadded recently to Volcano [26].
Extensibility can also be considered in a different context. In the long run, it clearly is desirable to provide aninteractive front-end to make using Volcano easier. We
are currently working on a two front-end, a nonoptimizedcommand interpreter based on Volcano’s executable algebra and an optimized one based on a logical algebra or
calculus language including query optimization
implemented with a new optimizer generator. The translation
between plans as produced by an optimizer and Volcano
will be. accomplished using a module that “walks” query
evaluation plans produced by the optimizer and Volcano
plans, i.e., state records, support functions, etc. We will
also use the optimizing front-end as a vehicle for experimentation with dynamic query evaluation plans that are
outlined in the next section.
In summary, since Volcano is very modular in its design, extensibility is provided naturally. It could be argued that this is the case only because Volcano does notaddress the hard problems in extensibility.
However, thisargument does not hold. Rather, Volcano is only one
component of a database system, namely the query execution engine. Therefore, it addresses only a subset of theextensibility problems and ignores a different subset. Asa query processing engine, it provides extensibility of its
set of query processing algorithms, and it does so in a waythat matches well with the extensibility
as provided by

GRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEM

query optimizer generators. It does not provide other database services and abstractions like a type system andtype checking for the support functions since it is not an
extensible database system. The Volcano routines assume
that query evaluation plans and their support functions arecorrect. Their correctness has to be ensured before Volcano is invoked, which is entirely consistent with the general database systems concept to ensure correctness at thehighest possible level, i.e. , as soon as possible after a user
query is parsed. The significance of Volcano as an extensible query evaluation system is that it provides a simple
but very useful and powerful set of mechanisms for efficient query processing and that it can and has been used
as a flexible research tool. Its power comes not only fromthe fact that it has been implemented following a few consistent design principles but also from its two meta-operators described in the next two sections.
V. DYNAMIC QUERY EVALUATION
PLANS
In most database systems, a query embedded in a program
written in a conventional programming language is optimized when the program is compiled. The query optimizer must make assumptions about the values of the program variables that appear as constants in the query andthe data in the database. These assumptions include thatthe query can be optimized realistically using guessed“typical’ ’ values for the program variables and that the
database will not change significantly between query optimization and query evaluation. The optimizer must also
anticipate the resources that can be committed to query
evaluation, e.g., the size of the buffer or the number ofprocessors. The optimality of the resulting query evaluation plan depends on the validity of these assumptions. If
a query evaluation plan is used repeatedly over an extended period of time, it is important to determine whenreoptimization is necessary. We are working on a scheme
in which reoptimization
can be avoided by using a newtechnique called dynamic query evaluation plans [17]. ’Volcano includes a choose-plan operator that allows realization of both multiplan access modules and dynamic
plans. In some sense, it is not an operator as it does not
perform any data manipulations.
Since it provides control
for query execution it is a meta-operator.
This operator
provides the same open-next-close protocol as the otheroperators and can therefore be inserted into a query planat any location. The open operation decides which of several equivalent query plans to use and invokes the open
operation for this input. Open calls upon a support function for this policy decision, passing it the bindings parameter described above. The next and close operations
simply call the appropriate operation for the input chosen
during open.
Fig. 4 shows a very simple dynamic plan. Imagine a
selection predicate controlled by a program variable. The‘This section

is a brief summaryof [ 171.

129

Print

Choose-Plan/
Functional Join\
File Scan

Index Scan
Fig. 4. A dynamic

query

evaluationplan.

index scan and functional join can be much faster than thefile scan, but not when the index is nonclustering and alarge number of items must be retrieved. Using the planof Fig. 4, however, the optimizer can prepare effectively
for both cases, and the application program using this dynamic plan will perform well for any predicate value.
The choose-plan operator allows considerable flexibility. If only one choose-plan operator is used as the top ofa query evaluation plan, it implements a multiplan accessmodule. If multiple choose-plan operators are included ina plan, they implement a dynamic query evaluation plan.
Thus, all forms of dynamic plans identified in [ 171 can berealized with one simple and effective mechanism. Notethat the choose-plan operator does not make the policy
decision concerning which of several plans to execute; it
only provides the mechanism. The policy is imported using a support function. Thus, the decision can be madedepending on bindings for query variables (e.g., program
variables used as constants in a query predicate), on the
resource and contention situation (e. g . , the availability ofprocessors and memory), other considerations such as userpriority, or all of the above.
The choose-plan operator provides significant new
freedom in query optimization and evaluation with an extremely small amount of code. Since it is compatible with
the query processing paradigm, its presence does not affect the other operators at all, and it can be used in a very
flexible way. The operator is another example for Volcano’s design principle to provide mechanisms to implement a multitude of policies. We used the same philosophy when designing and implementing
a scheme forparallel query evaluation.
VI. MULTIPROCESSOR QUERY EVALUATION
A large number of research and development projects
have shown over the last decade that query processing in
relational database systems can benefit significantly fromparallel algorithms. The main reasons parallelism is relatively easy to exploit in relational query processing systems are 1) query processing is performed using a tree of
operators that can be executed in separate processes andprocessors connected with pipelines (inter-operator parallelism) and 2) each operator consumes and produces setsthat can be partitioned or fragmented into disjoint subsets
to be processed in parallel (intra-operator parallelism).

IEEE

130

TRANSACTIONSON KNOWLEDGE

AND

DATA

ENGINEERING,

A. Vertical Parallelism
The first function of exchange is to provide verticalparallelism
or pipelining between processes. The open
procedure creates a new process after creating a data
structure in shared memory called a port for synchronization and data exchange. The child process is an exact
duplicate of the parent process. The exchange operator
then takes different paths in the parent and child processes.
The parent process serves as the consumer and the childprocess as the producer in Volcano. The exchange operator in the consumer process acts as a normal iterator, theonly difference from other iterators is that it receives its
input via inter-process communication
rather than iterator(procedure) calls. After creating the child process,open-exchange in the consumer is done. Next-exchange
2Parts of this section

have appearedin [20].

6, NO.

1, FEBRUARY

1994

Print

Fortunately, the reasons parallelism is easy to exploit inrelational systems does not require the relational data
model per se, only that queries be processed as sets ofdata items in a tree of operators. These are exactly theassumptions made in the design of Volcano, and it wastherefore logical to parallelize extensible query processing in Volcano.

When Volcano was ported to a multiprocessor
machine, it was desirable to use all single-process query processing code existing at that point without any change.
The result is very clean, self-scheduling parallel processing. We call this novel approach the operator model ofparallelizing
a query evaluation engine [20] .2 In thismodel, all parallelism issues are localized in one operator
that uses and provides the standard iterator interface to theoperators above and below in a query tree.
The module responsible for parallel execution and synchronization is called the exchange iterator in Volcano.
Notice that it is an iterator with open, next, and close procedures; therefore, it can be inserted at any one place orat multiple places in a complex query tree. Fig. 5 shows
a complex query execution plan that includes data processing operators, i.e. , file scans and joins, and exchange
operators. The next two figures will show the processes
created when this plan is executed.
This section describes how the exchange iterator implements vertical and horizontal parallelism followed bydiscussions of alternative modes of operation of Volcano’s exchange operator and modifications
to the filesystem required for multiprocess query evaluation. The
description goes into a fair amount of detail since the exchange operator adds significantly to the power of Volcano. In fact, it represents a new concept in parallel query
execution that is likely to prove useful in parallelizing both
existing commercial database products and extensible single-process systems. It is described here for shared-memory systems only; considerations for the distributed-memory version are outlined as future work in the last sectionof this paper.

VOL.

I

Exchange

Join
/

\

Exchange

Join
/

\

Exchange

Fig. 5. Operator

Exchange

model

Scan

of parallelization.

waits for data to arrive via the port and returns them arecord at a time. Close - exchange informs the producer
that it can close, waits for an acknowledgment,
and returns.
Fig. 6 shows the processes created for vertical parallelism or pipelining by the exchange operators in the queryplan of the previous figure. The exchange operators havecreated the processes, and are executing on both sides ofthe process boundaries, hiding the existence of process
boundaries from the “work” operators. The fact that thejoin operators are executing within the same process, i.e.,
the placement of the exchange operators in the query tree,
was arbitrary. The exchange operator provides only themechanisms for parallel query evaluation, and many otherchoices (policies) would have been possible. In fact, themechanisms provided in the operator model tend to be
more flexible and amenable to more different policies thanin the alternative bracket model [20].
In the producer process, the exchange operator becomes the driver for the query tree below the exchange
operator using open, next, and close on its input. The output of next is collected in packets, which are arrays of
Next-Record structures. The packet size is an argument in
the exchange iterator’s state record, and can be set between 1 and 32 000 records. When a packet is filled, it isinserted into a linked list originating in the port and asemaphore is used to inform the consumer about the newpacket. Records in packets are fixed in the shared buffer
and must be unfixed by a consuming operator.
When its input is exhausted, the exchange operator in
the producer process marks the last packet with an endof-stream tag, passes it to the consumer, and waits until
the consumer allows closing all open files. This delay isnecessary in Volcano because files on virtual devices mustnot be closed before all their records are unpinned in thebuffer. In other words, it is a peculiarity due to other design decisions in Volcano rather than inherent in the exchange iterator on the operator model of parallelization.
The alert reader has noticed that the exchange- module
uses a different dataflow paradigm than all other opera-

GRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEM

3
Print

Fig. 6. Verticalparallelism.

tors. While all other modules are based on demand-driven
dataflow (iterators, lazy evaluation), the producer-consumer relationship of exchange uses data-driven dataflow(eager evaluation). There are two reasons for this change
in paradigms. First, we intend to use the exchange operator also for horizontal parallelism,
to be described below, which is easier to implement w ith data-driven dataflow. Second, this scheme removes the need for request
messages. Even though a scheme with request messages,e.g., using a semaphore, would probably perform acceptably on a shared-memory machine, it would create unnecessary control overhead and delays. Since very-highdegrees of parallelism and very-high-performancequery
evaluation require a closely tied network, e.g., a hypercube, of shared-memory machines, we decided to use aparadigm for data exchange that has been proven to perform well in a “shared-nothing”
database machine [ 111.
A run-time switch of exchange enables Jlow control orback pressure using an additional semaphore. If the producer is significantly faster than the consumer, the producer may pin a significant portion of the buffer, thus
impeding overall system performance. If flow control isenabled, after a producer has inserted a new packet into
the port, it must request the flow control semaphore. Aftera consumer has removed a packet from the port, it releases the flow control semaphore. The initial value of theflow control semaphore determines how many packets the
producers may get ahead of the consumers.
Notice that flow control and demand-driven dataflow
are not the same. One significant difference is that flow
control allows some “ slack’ ’ in the synchronization of
producer and consumer and therefore truly overlapped execution, while demand-driven dataflow is a rather rigid
structure of request and delivery in which the consumer
waits while the producer works on its next output. The
second significant difference is that data-driven dataflow

131

is easier to combine efficiently
and partitioning.

with horizontal

parallelism

B. Horizontal Parallelism
There are two forms of horizontal parallelism, which
we call bushy parallelism and intra-operator parallelism.
In bushy parallelism,
different CPU’s execute different
subtrees of a complex query tree. Bushy parallelism andvertical parallelism are forms of inter-operator
parallelism. Intra-operator parallelism means that several CPU’s
perform the same operator on different subsets of a stored
dataset or an intermediate result.
Bushy parallelism can easily be implemented by inserting one or two exchange operators into a query tree. For
example, in order to sort two inputs into a merge-join inparallel, the first or both inputs are separated from themerge-join by an exchange operation. The parent process
turns to the second sort immediately after forking the childprocess that will produce the first input in sorted order.
Thus, the two sort operations are working in parallel.
Intra-operator
parallelism
requires data partitioning.
Partitioning of stored datasets is achieved by using multiple files, preferably on different devices. Partitioning ofintermediate results is implemented by including multiple
queues in a port. If there are multiple consumer processes, each uses its own input queue. The producers use
a support function to decide into which of the queues (oractually, into which of the packets being filled by the producer) an output record must go. Using a support function
allows implementing
round-robin-, key-range-, or hashpartitioning.
Fig. 7 shows the processes created for horizontal parallelism or partitioning by the exchange operators in thequery plan shown earlier. The join operators are executedby three processes while the file scan operators are executed by one or two processes each, typically scanning
file partitions on different devices. To obtain this grouping of processes, the only difference to the query plan used
for the previous figure is that the “degree of parallelism’ ’
arguments in the exchange state records have to be set to
2 or 3, respectively, and that partitioning
support functions must be provided for the exchange operators thattransfer file scan output to the joint processes. All file scan
processes can transfer data to all join processes; however,data transfer between the join operators occurs only withineach of the join processes. Unfortunately,
this restriction
renders this parallelization
infeasible if the two joins areon different attributes and partitioning-based
parallel join
methods are used. For this case, a variant of exchange is
supported in Volcano exchange operator called interchange, which is described in the next section.
If an operator or an operator subtree is executed in parallel by a group of processes, one of them is designatedthe master. When a query tree is opened, only one process
is running, which is naturally the master. When a master
forks a child process in a producer-consumer
relationship, the child process becomes the master within its
group. The first action of the master producer is to deter-

132

IEEE

TRANSACTIONSON KNOWLEDGE

AND

DATA

ENGINEERING,

VOL.

6, NO.

1, FEBRUARY

1994

the two partitioning
methods for hash-division[ 161 requires that the divisor be replicated and used with eachPrint
partition of the dividend. Another example are fragmentand-replicate parallel join algorithms in which one of thetwo input relations is not moved at all while the otherrelation is sent to all processors. To support these algorithms, the exchange operator can be directed to send allrecords to all consumers, after pinning them appropriately
multiple times in the buffer pool. Notice that it is not necessary to copy the records since they reside in a sharedbuffer pool; it is sufficient to pin them such that each consumer can unpin them as if it were the only process using
them.
During implementation
and benchmarkingof parallelsorting [ 181, [21], we added two more features to exchange. First, we wanted to implement a merge networkin which some processors produce sorted streams merge
concurrently by other processors. Volcano’s sort iterator
can be used to generate a sorted stream. A merge iterator
was easily derived from the sort module. It uses a single
Fig. 7. Horizontal
parallelism.
level merge, instead of the cascaded merge of runs usedin sort. The input of a merge iterator is an exchange. Difmine how many slaves are needed by calling an approferently from other operators, the merge iterator requires
priate support function. If the producer operation is to run to distinguish the input records by their producer. As an
in parallel, the master producer forks the other producer
example, for a join operation it does not matter where theprocesses.
input records were created, and all inputs can be accuAfter all producer processes are forked, they run withmulated in a single input stream. For a merge operation,out further synchronization among themselves, with two it is crucial to distinguish the input records by their proexceptions. First, when accessing a shared data structure,
ducer inorder to merge multiple sorted streams correctly.
e.g., the port to the consumers or a buffer table, shortWe modified the exchange module such that it can keep
term locks must be acquired for the duration of one linkedthe input records separated according to their producers.
list insertion. Second, when a producer group is also a A third argument to next - exchange is used to communiconsumer group, i.e., there are at least two exchange op- cate the required producer from the merge to the exchange
erators and three process groups involved in a verticaliterator. Further modifications
included increasing thepipeline, the processes that are both consumers and pronumber of input buffers used by exchange, the number ofducers synchronize twice. During the (very short) interval
semaphores (including for flow control) used between
between synchronizations, the master of this group cre- producer and consumer part of exchange, and the logic
ates a port that serves all processes in its group.
were implefor end-of-stream. All these modifications
When a close request is propagated down the tree and mented in such a way that they support multilevel merge
reaches the first exchange operator, the master consumtrees, e.g., a parallel binary merge tree as used in [3].
er’s close-exchange procedure informs all producer proThe merging paths are selected automaticallysuch thatcesses that they are allowed to close down using the the load is distributed as evenly as possible in each level.
semaphore mentioned above in the discussion on vertical
Second, we implemented a sort algorithm that sorts data
parallelism. If the producer processes are also consumers,
randomly partitioned (or “striped”[29]) over multiple
the master of the process group informs its producers, etc.
disks into a range-partitioned
file with sorted partitions,
In this way, all operators are shut down in an orderly fash- i.e., a sorted file distributed over multiple disks. Whenion, and the entire query evaluation is self-scheduling.
using the same number of processors and disks, two processes per CPU were required, one to perform the file
C. Variants of the Exchange Operator
scan and partition the records and another one to sort
There are a number of situations for which the ex- them. Creating and running more processes than processors can inflict a significant cost since these processeschange operator described so far required some modificompete for the CPU’s and therefore require operating
cations or extensions. In this section, we outline addisystem scheduling.
tional capabilities implemented
in Volcano’s exchange
In order to make better use of the available processing
operator. All of these variants have been implemented in
the exchange operator and are controlled by arguments in power, we decided to redue the number of processes byhalf, effectively moving to one process per CPU. This
the state record.
to the exchange operator. Until
For some operations, it is desirable to replicate or required modifications
broadcast a stream to all consumers. For example, one of then, the exchange operator could “live” only at the top($

GRAEFE:

VOLCANO-QUERYEVALUATIONSYSTEMor the bottom of the operator tree in a process. Since themodification,
the exchange operator can also be in the
middle of a process’ operator tree. When the exchange
operator is opened, it does not fork any processes but establishes a communication
port for data exchange. The
next operation requests records from its input tree, possibly sending them off to other processes in the group,
until a record for its own partition is found. This mode ofoperation was termed interchange, and was referred toearlier in the discussion of Fig. 7.
This mode of operation also makes flow control obsolete. A process runs a producer (and produces input forthe other processes) only if it does not have input for the
consumer. Therefore, if the producers are in danger ofoverrunning the consumers, none of the producer operators gets scheduled, and the consumers consume theavailable records.
D. File System ModiJications
The file system required some modifications
to serve
several processes concurrently. In order to restrict the extent of such modifications, Volcano currently does not include protection of files and records other than each disk’s
volume table of contents. Furthermore, typically nonrepetitive actions like mounting a device must be invokedby the query root process before or after a query is evaluated by multiple processes.
The most intricate changes were required for the bu$er
module. In fact, making sure the buffer manager would
not be a bottleneck in a shared-memory machine was aninteresting subproject independent of database query processing [ 181. Concurrency control in the buffer manager
was designed to provide a testbed for future research witheffective and efficient mechanisms, and not to destroy theseparation of policies and mechanisms.
Using one exclusive lock is the simplest way to protect
a buffer pool and its internal data structures. However,decreased concurrency would have removed most or all
advantages of parallel query processing. Therefore, thebuffer uses a two-level scheme. There is a lock for eachbuffer pool and one for each descriptor (page or cluster
resident in the buffer). The buffer pool lock must be held
while searching or updating the hash tables and bucket
chains. It is never held while doing Z/O; thus, it is neverheld for a long period of time. A descriptor or cluster lockmust be held while doing Z/O or while updating a descriptor in the buffer, e.g., to decrease its fix count.
If a process finds a requested cluster in the buffer, it
uses an atomic test-and-lock operation to lock the descriptor. If this operation fails, the pool lock is released, theoperation delayed and restarted. It is necessary to restart
the buffer operation including the hash table lookup because the process that holds the lock might be replacing
the requested cluster. Therefore, the requesting process
must wait to determine the outcome of the prior operation.
Using this restart-scheme for descriptor locks has the additional benefit of avoiding deadlocks. The four conditions for deadlock are mutual exclusion, hold-and-wait,133

no preemption,and circular wait; Volcano’s restartscheme does not satisfy the second condition. On the other
hand, starvation is theoretically possible but has become
extremely unlikely after buffer modifications
that basically eliminated buffer contention.
In summary, the exchange module encapsulates parallel query processing in Volcano. It provides a large set ofmechanisms useful in parallel query evaluation. Only very
few changes had to be made in the buffer manager and theother file system modules to accommodate parallel execution. The most important properties of the exchange
module are that it implements three forms of parallel processing within a single module, that it makes parallel
query processng entirely self-scheduling,supports a variety of policies, e.g., partitioning
schemes or packet
sizes, and that it did not require any changes in the existing query processing modules, thus leveraging significantly the time and effort spent on them and allowing easy
parallel implementationof new algorithms.
It entirely
separates data selection, manipulation,
derivation, etc.
from all parallelism issues, and may therefore prove useful in parallelizing
other systems, both relational commercial and extensible research systems.
VII. SUMMARY
AND CONCLUSIONS
We have described Volcano, a new query evaluation
system that combines compactness, efficiency, extensibility, and parallelism in a dataflow query evaluation system. Compactness is achieved by focusing on few generalalgorithms. For example, the one-to-one match operator
implements join, semi-join, our join, anti-join, duplication elimination,
aggregation, intersection, union, difference, and anti-difference. Extensibility is achieved by implementing only one essential abstraction, streams, andby relying on imported support functions for object interpretation and manipulation.
The details of streams, e.g.,
type and structure of their elements, are not part of thestream definition and its implementation,and can be determined at will, making Volcano a data-model-independent set processor. The separation of set processing
control in iterators and object interpretation and manipulation through support functions contributes significantly
to Volcano’s extensibility.
The Volcano design and implementation
was guided bya few simple but generally useful principles. First, Volcano implements mechanisms to support policies that canbe determined by a human experimenter or a query optimizer. Second, operators are implemented as iterators toallow efficient transfer of data and control within a single
process. Third, a uniform operator interface allows for
integration of new query processing operators and algorithms. Fourth, the interpretationand manipulationofstream elements is consistently left open to allow supporting any data model and processing items of any type,
shape, and representation. Finally, the encapsulated implementation of parallelism allows developing query processing algorithms in a single-process environment but
executing them in parallel. These principles have led to a

134

IEEE

TRANSACTIONS

ON

very flexible, extensible, and powerful query processing
engine.
Volcano introduces two novel meta-operators.
Dynamic query evaluation plans are a new concept introduced in [ 171 that allow efficient evaluation of queries withfree variables. The choose-plan meta-operator at the topof a plan or a subplan makes an efficient -decision whichalternative plan to use when the plan is invoked. Dynamic
plans have the potential of increasing the performance ofembedded and repetitive queries significantly.
Dataflow techniques are used within processes as well
as between processes. Within a process, demand-driven
dataflow is implemented by means of streams and iterators. Streams and iterators represent the most efficient execution model in terms of time and space for single-process query evaluation. Between processes, data-driven
dataflow is used to pass data between producers and consumers efficiently. If necessary, Volcano’s data-driven
dataflow can be augmented with flow control or backpressure. Horizontal partitioning
can be used both on
stored and intermediate datasets to allow intra-operator
parallelism. The design of the exchange meta-operator
encapsulates the parallel execution mechanism for vertical, bushy, and intra-operator parallelism, and it performs
the translations from demand-driven to data-driven dataflow and back [20].
Encapsulating all issues of parallelism control in one
operator and thus orthogonalizing
data manipulation
andparallelism offers important extensibility and portability
advantages. All data manipulation operators are shieldedfrom parallelism
issues, and have been designed, debugged, tuned, and preliminarily
evaluated in a singleprocess environment.
To parallelize a new operator, it
only has to be combined with the exchange operator in aquery evaluation plan. To port all Volcano operators to a
new parallel machine, only the exchange operator requires appropriate modifications. At the current time, theexchange operator supports parallelism only on sharedmemory machines. We are currently working on extending this operator to support query processing on distributed-memory machines while maintaining its encapsulation properties. However, we do not want to give up theadvantages of shared memory, namely fast communication and synchronization.
A recent investigation demonstrated that shared-memory architectures can deliver nearlinear speed-up for limited degrees of parallelism; we observed a speed-up of 14.9 with 16 CPU’s for parallel sorting in Volcano [ 181. To combine the bets of both worlds,
we are building our software such that it runs on a closelytied group, e.g., a hypercube or mesh architecture, of
shared-memory parallel machines. Once this version ofVolcano’s exchange operator and therefore all of Volcano
runs on such machines, we can investigate query processing on hierarchical architectures and heuristics of how
CPU and Z/O power as well as memory can best be placedand exploited in such machines.
Most of today’s parallel machines are built as one of
the two extreme cases of this hierarchical design: a distributed-memorymachine uses single-CPU nodes, while

KNOWLEDGE

AND

DATA

ENGINEERING,

VOL.

6, NO.

I,FEBRUARY

1994

a shared-memory machine consists of a single node. Software designed for this hierarchical architecture will run
on either conventional design as well as a genuinely hierarchical machine, and will allow exploring trade-offs in
the range of alternatives in between. Thus, the operator
model of parallelization
also offers the advantage of architecture- and topology-independent
parallel query evaluation [ 191.
A number of features make Volcano an interesting object for further performance studies. First, the LRU/MRU
buffer replacement strategy switched by a keep-or-tosshint needs to be evaluated. Second, using clusters of different sizes on a single device and avoiding buffer shuffling by allocating buffer space dynamicallyinstead of
statically require careful evaluation. Third, the duality andtrade-offs between sort- and hash-based query processing
algorithms and their implementations
will be exploredfurther. Fourth, Volcano allows measuring the performance of parallel algorithms and identifying bottlenecks
on a shared-memory architecture, as demonstrated for instance in [ 181. We intend to perform similar studies on
distributed-memory
and, as they become available, hierarchical architectures. Fifth, the advantages and disadvantages of a separate scheduler process in distributedmemory query processing (as used in GAMMA)
will beevaluated. Finally, after data-driven dataflow has beenshown to work well on a shared-nothing database machine[ 111, the combination of demand- and data-driven dataflow should be explored on a network on shared-memorycomputers.
While Volcano is a working system in its current form,
we are considering several extensions and improvements.
First, Volcano currently does very extensive error detection, but it does not encapsulate errors in fail-fast modules. It would be desirable to modify all modules such thatthey have all-or-nothing
semantics for all requests. Thismight prove particularly tricky for the exchange module,
even more so in a distributed-memory
environment. Second, for a more complete performance evaluation, Volcano should be enhanced to a multiuser system that allows
inter-query parallelism. Third, to make it a complete data
manager and query processor, transactions semantics including recovery should be added.
Volcano is the first operational query evaluation systemthat combines extensibility
and parallelism.
We believethat Volcano is a powerful tool for database systems research and education. We are making it available for student use, e.g., for implementationand performance studies, and have given copies to selected outsideorganizations. We intend to use it in a number of further
research projects, including research on the optimizationand evaluation of dynamic query evaluation plans [ 171 andthe REVELATION project on query optimizationand execution in object-oriented database systems with encapsulated behavior [ 151.
ACKNOWLEDGMENT

The one-to-one match operators were implemented by
Tom Keller starting with existing hash join, hash aggre-

GRAEFE:

VOLCANO--QUERYEVALUATION

gate, merge join, and sort code. Hash table overflow management was added by Mark Swain- Dynamic query evaluation plans and the choose-plarz operator were designed
and implemented by Karen Ward. We are also very muchindebted to all members of the GAMMA
and EXODUS
projects. Leonard Shapiro contributed to the quality andclarity of the exposition with many insightful comments.
David Dewitt,
Jim Gray, ‘David Maier, Bill McKenna,
Marguerite Murphy,
and Mike Stonebraker
gave very
helpful comments on earlier drafts of this paper. The
anonymous referees gave some further helpful suggestions.

REFERENCES[l]

D. S. Batory. J. R. Barnett, J. F. Garza, K. P. Smith, K. Tsukuda,
B. C. Twichell,
and T. E. Wise, “GENESIS:
An extensible databasemanagement
system, ” IEEE Trum. Softwure Erq., vol. 14, p. 171 1,
Nov. 1988.
“Duplicate
record eliminationin large[2] D. Bitton and D. J. Dewitt,
data files, ’ ’ ACM Trans. Dutuhusu Syst., vol. 8, p. 255, June 1983.
D. Bitton, H. Boral, D. J. Dewitt,
and W. K. Wilkinson,“Parallel
algorithms
for the execution of relational database operations,”
ACM
Truns. Dutubuse Syst. , vol. 8, p. 324, Sept. 1983.
K. Bratbergsengen,“Hashing
methods and relational algebra operations,” in Proc Confl Very Large Data Buses, Singapore,Aug. 1984,
p. 323.
M. J. Carey, D. J. Dewitt,
J. E. Richardson,
and E. J. Shekita, “Object and file managementin the EXODUS
Extensible
database sysin Proc. ConJ Very Large Data Buses, Kyoto, Japan, Aug.
tem,”
1986, p. 91.
M. J. Carey, D. J. Dewitt,
and S. L. Vandenberg,“A data modeland query language for EXODUS,”
in Proc. ACM SZGMOD
Conf.,
Chicago, IL, June 1988, p. 413.
M. J. Carey, D. J. Dewitt,
G. Graefe, D. M. Haight, J. E. Richardson, D. T. Schuh, E. J. Shekita, and S. Vandenberg,“The EXODUS
extensible DBMS Project: An overview ,” in Readings on Object-OriSan Mateo,
CA:
ented Database Systems, D. M. S. Zdonik,
Ed.
Morgan Kaufman,
1990.
J. V. Carlis, “HAS:
A relational
algebra operator,
or divide is notenough to conquer, ” in Proc. IEEE Conf. Data Eng., Los Angeles,
CA, Feb. 1986, p. 254.
D. D. Chamberlin,
M. M. Astrahan,
M. W. Blasgen, J. N. Gray,
W. F. King, B. G. Lindsay,
R. Lorie, J. W. Mehl, T. G. Price, F.
Putzolo,
P. G. Selinger,
M. Schkolnik,
D. R. Slutz, I. L. Traiger,of system
B. W. Wade, and R. A. Yost, “A history and evaluation
R,” Commun. Assoc. Comput. Much., vol. 24, p. 632, Oct. 1981.
[lo] H. T. Chou, D. J. Dewitt,
R. H. Katz, and A. C. Klug, “Design
and implementationof the Wisconsin
storage system,”
SoftwarePractice Experience,
vol. 15, no. 10, p. 943, Oct. 1985.
[ 111 D. J. Dewitt,
S. Ghandeharadizeh,
D. Schneider,
A. Bricker,
H. I.
Hsiao, and R. Rasmussen,‘ ‘The Gamma database machine project, ’ ’IEEE Trans. Knowledge
Dutu Eng., vol. 2, p. 44, Mar. 1990.
[12] S. Fushimi,
M. Kitsuregawa
and H. Tanaka, “An overview
of thesystem software of a parallel relational database machine GRACE,”
in Proc. Con& Very Large Data Bases, Kyoto, Japan, Aug. 1986, p.
209.

[13]

13s

SYSTEM

G. Graefe and D. J. Dewitt,“The EXODUS
optimizer
generator, ”
in Proc. ACM SZGMOD
Conf., San Francisco,
CA, May 1987, p.
160.
“Rule-based
query optimizationin extensible
database[14] G. Graefe,
systems, ” Ph. D. dissertation
Univ. Wisconsin-Madison,Aug. 1987.
[IS] G. Graefe and D. Maier, “Query
optimizationin object-oriented
dain Adrunces in Object-Oriented
Dutabase systems: A prospectus,”
tubuse Systems, Lecture Notes in Computer
Science, vol. 334, K. R.
Sept. 1988, p. 358.
Dittrich,
Ed. New York: Springer-Verlag,
division:
Four algorithms
and their perforU6 1 G. Graefe, “Relational
mance, ’ ’ in Proc. IEEE Conf. Data Eng., Los Angeles, CA, Feb.
1989, p. 94.
query evaluationplans,” in Proc.
[17 G. Graefe and K. Ward, “Dynamic
ACM SIGMOD
Conf., Portland, OR, May-June
1989, p. 358.
118 G. Graefe and S. S. Thakkar, “Tuning a parallel database algorithm

on a shared-memory
rrlultiprocessor-.”,Tc,~i,l’ur-c~-Prli(~tic.c’ mcl hprictlcnc, vol . 22, no. 7, July VW, p. 485.
1191 G. Graet‘e and D. I,. Davison.
“Encapsulationof Parallelism
and Architecture-Independence
in Extensible
Database Query Processing. ”
to appear in l&?E Trum. OII &!#iw. E,‘rz~. . vol. 19, no. 8, August
1993.
of parallelism
in the Volcano query pro1 G. Graefe, “Encapsulation
cessing system, ’ ’ in Proc. ACM SIGMOD
Corz$ , Atlantic
City, NJ,
May 1990, p. 102.
“Parallel
external
sorting in Volcano,”
CU Boulder Comput.
Sci.‘Tech.
Rep. 459, Feb. 1990.
A. Guttman,“R-trees:
A dynamic index structure for spatial searching,” in Proc. ACM SIGMOD
Conf., Boston, MA, June 1984, p. 47.
[23] L. Haas, W. Chang, G. Lohman,
J. McPherson,
P. F. Wilms,
G.
Lapis, B. Lindsay,
H. Pirahesh, and M. J. Carey, and E. Shekita,“Starburst
mid-flight:
As the dust clears,”IEEE Truns. Knowledge
Data Eng., vol. 2, p. 143, Mar. 1990.
1241 S. E. Hudson and R. King, ‘ ‘Cactis: A self-adaptive,
concurrent
implementationof an object-oriented
database management
system, ”
ACM Truns. Database Syst., vol. 14, p. 29 1, Sept. 1989.
[25] T. Keller and G. Graefe, “The one-to-one
match operator of the Volcano query processing system,”
Oregon Grad. Center, Comput.
Sci.
Tech. Rep., Beaverton,
OR, June 1989.
[26] T. Keller, G. Graefe, and D. Maier, “Ethcient
assembly of complex
objects,”
Proc. ACM SIGMOD
Conf., Denver,
CO, May 1991, p.
148.
1271 J. E. Richardson
and M. J. Carey, “Programming
constructs for database system implementationin EXODUS,” in Proc. ACM SIGMOD Conf., San Francisco,
CA, May 1987, p. 208.
[28] J. E. Richardson,“E: A persistentsystems implementation
language, ’ ’ Comput.
Sci. Tech. Rep. 868, Univ. Wisconson-Madison,Aug. 1989.
1291 K. Salem and H. Garcia-Molina,“Disk
Striping,”
in Proc. IEEE
Con& Data Eng., Los Angeles, CA, Feb. 1986, p. 336.
[30] H. J. Schek, H. B. Paul, M. H. Scholl, and G. Weikum,“The
DASDBS
project:
Objectives,
experiences,and future prospects,”
IEEE Truns. Knowledge
Data Eng., vol. 2, p. 25, Mar. 199.
[31] L. D. Shapiro, “Join processing in database systems with large main
memories, ’ ’ ACM Trans. Database Syst., vol. 11, p. 239, Sept. 1986.
[ 32 ] M. Stonebraker,“Retrospection
on a database system,”
ACM Trans.
Dutabuse Syst., vol. 5, p. 225, June 1980.
[33] M. Stonebraker,
P. Aoki, and M. Seltzer, “Parallelismin XPRS,”UCB/Electronics
Research Lab. Memo. M89/16,
Berkeley,
CA, Feb.
1989.
[34] M. Stonebraker,
R. Katz, D. Patterson, and J. Ousterhout,“The Design of XPRS,”
in Proc. Conf. Very Large Databases,
Long Beach,
CA, Aug. 1988, p. 318.
[35] M. Stonebraker,
L. A. Rowe, and M. Hirohama,“The Implementation of Postgres, ’ ’ IEEE Trans. Knowledge
Data Eng., vol. 2, p.
125, Mar. 1990.

coetz----~ Graefe-~
was an undergraduate
student inbusiness administrationand c%mputer science inGermany
before getting his M.S. and Ph.D. deowe

b”’

in

.a-

rnmnlltpr

‘““‘y

-.I-

cripncey---mm__

in

--_

1984

_

_

-

and
__--_

1987.

,

re-

of Wisconsinspectively , from the University
Madison.
His dissertation
work was on the EXODUS Optimizer
Generator
under David Dewitt
and Michael Carey.
In 1987, he joined the faculty of the Oregon
Graduate
Institute,
where he initiatedboth theVolcano project and with David Maier, the REVELATION OODBMS
project. From 1989 to 1992, he was with the Universityof Colorado
at Boulder.
Since 1992, he has been an Associate Professor
with Portland State University.
He is currently
working
on extensions
toVolcano,includinga new optimizer
generator,
on request processingin
OODBMS’s
and scientific databases, and on physical database design.