Back to index

Access Path Selection in a Relational DBMS

P.G. Selinger, M.M. Astrahan, D.D> Chamberlin, R.A. Lorie, T.G. Price

Summary by: Steve Gribble and Armando Fox

One-line summary: Optimize queries by selecting from a tree of possible query step orderings, by using statistics of existing relations, selectivity factors that estimate how many tuples will be returned by a predicate, and appropriately weighted CPU and disk costs of accessing tuples.

Overview/Main Points

Relevance

The seminal work on query optimization relying on table statistics and a model of CPU and disk utilization.

Flaws

Cost models used were adequate for the hardware of the day, but probably simplistic given today's multiheaded CPU's and synchronous nonblocking I/O subsystems. (Compilers have the same problem in trying to optimize code for hairy new architectures; seems like there would be many parallels between query optimization and the back end of a compiler.)
Back to index