The first relational query optimizers
were described in [Selinger 79] and [Wong 76],
in System R and Ingres,
for a particular variant
of the relational model
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.
many extensions have been added
to the relational model.
One early extension
to the relational model
was the query language SQL.
the concept of tuple ordering,
and aggregation operations.
Later versions of SQL
and the extensions contemplated in SQL3
and vendor specific features
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.
of the relational data model
dealing with issues of
On the physical side,
and variants of algorithms,
as well as new
and physical architectures
have been developed.
At about the same time,
the object oriented database model [Atkinson 89]
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.