The first relational query optimizers
were described in [Selinger 79] and [Wong 76],
in System R and Ingres,
respectively.
These optimizers
were developed
for a particular variant
of the relational model
and specifically
for their physical implementation
of the model.
The System R optimizer worked rather well,
and is the basis for many current
commercial database optimizers.
But the database world
has not stood still.
First,
many extensions have been added
to the relational model.
One early extension
to the relational model
was the query language SQL.
SQL has
the concept of tuple ordering,
duplicates tuples
and aggregation operations.
Later versions of SQL
(SQL2
[Melton 93],
[Date 93]
and the extensions contemplated in SQL3
[Melton 96]),
and vendor specific features
represent further
extensions to the relational model.
The types of attributes
(which started as numbers and strings)
have been enriched to include
many new types and
user defined types
and to allow unions of types
(or no fixed types) for an attribute.
Important offshoots
of the relational data model
dealing with issues of
rules,
transitive closure
and recursion
have appeared.
On the physical side,
many
new algorithms
and variants of algorithms,
as well as new
storage structures
and physical architectures
have been developed.
At about the same time,
the object oriented database model [Atkinson 89]
was developed.
It has a much more
complicated logical paradigm
with many new logical
and physical operators.
Since the first query optimizers
had been developed
for a single data model,
a new extensible optimizer had to be developed.
The EXODUS Optimizer Generator [Graefe 87]
was specifically designed to
fit into the EXODUS framework
of an extensible database system.
Later Volcano and then the Cascades Optimizer Framework
were developed by Graefe and others.
Page 1
