From: Charles Giefer (cgiefer@cs.washington.edu)
Date: Mon May 24 2004 - 01:57:59 PDT
Access Path Selection in a Relational Database Management System
Selinger et al.
This paper was written in 1979 about IBM's research on relational database
query optimization. System R is the name they gave to their database. It
seems that System R was experimental and the first time that many of these
important topics had been addressed.
The language used by System R was SQL. There are many translations from SQL
(the logical query) to the physical query that is executed in the system.
For example, choosing the order to execute the physical query and choosing
the algorithms to use for each physical component are the two biggest
decisions.
The bulk of this paper was concerned with assigning a cost model to the
query optimizer so that an efficient physical translation could be found.
An optimizer must be performed on each query, so it must be fast. Also, a
good optimizer can greatly increase the execution time of a query, so it
must be accurate. These are the conflicting goals of the optimizer (speed
and accuracy). In order to satisfy both of these adequately, this paper
proposes a cost model that estimates costs and enumerates them to find the
path of least cost.
The cost model addresses several aspects such as clustering, sorting,
indexing, stored cardinality information, page information, and even a rough
estimate of CPU usage. It creates a search tree and locates the cheapest
estimated path to the answer. I found it interesting that the System kept
data about the data so that the cost functions could be computed more
easily.
As with most papers that are fairly old, the terminology and familiarity
with the system are different for the contemporary audience than for the
intended audience. Therefore, it was difficult to translate the
significance of some of the ideas proposed here. This paper contained
several subtle details in the explanation of their processes.
This archive was generated by hypermail 2.1.6 : Mon May 24 2004 - 01:58:13 PDT