From: Ankur Jain (ankur@cs.washington.edu)
Date: Mon May 24 2004 - 10:49:16 PDT
Access Path Selection in a RDMS - Selinger et al.
System R was one of the first databases to have a rather sophisticated query
optimizer. Its importance can be
judged from the fact that most databases even today are designed on much the
same principles that System R used.
In this paper, the authors presented many of the cool ideas that made up the
System R optimizer. It maintains
a wide array of statistics on relations and indexes such as index
cardinality, pages per relation which helped
in determining the approximate size of the output using the notion of
selectivity factor. Using these along with
formulas to estimate the processing and I/O costs, the optimizer makes cost
estimates which although not accurate
are able to choose access paths rather well. I also liked their idea of
comparing two execution plans only if they
both represent the same expression as well as the same "interesting order".
Conspicuously missing in the paper was the evaluation of their techniques.
Also, I wasn't very clear why if they
disregarded some join sequences when they were doing the sort of dynamic
programming that we discussed in the class
for finding the most efficient join.
Overall though, I was very impressed by the building blocks to query
optimization that this paper gave; its place as
one of the seminal papers in this field is definitely well-earned! :)
This archive was generated by hypermail 2.1.6 : Mon May 24 2004 - 09:49:18 PDT