From: CR (chrisre@cs.washington.edu)
Date: Mon May 24 2004 - 09:53:01 PDT
This paper outlines System R’s heuristics for optimization and access
path selection. I remember hearing a review of this once that access
path selection was an extremely appropriate view of what they were doing
– as opposed to optimization. Their heuristics considerably prune the
join-ordering space but do little cross block optimization. This is said
not to diminish this paper’s importance since so many of the ideas
(selectivity, orderings) are used today in the SFW type query
implementation.
One thing they were concerned about in their cost model was CPU time. On
its surface this cost model seems outmoded since CPU speeds have
increased so dramatically. I would argue that there is some kind of ebb
and flow in this cost models. While it is true that disk cost dominated,
they reappeared with main memory databases and then began to fall off as
memory lagged behind CPU. I would suspect they will re-emerge when
network speed eclipses CPU growth, which is quickly coming. So this
paper may again find renewed relevance in unexpected ways.
The second paper makes this point, but the key weakness of this approach
is the lack of flexibility. These are needed to adopt to the changing
cost models. A tiny bit more abstraction could do a lot of good.
I also tried to think about why they missed the importance of rewrites.
I think CPU cost and the fact that they were trying to get a proof of
concept done were the two dominant factors. It is slightly odd though.
Since they were trying to show that declarative queries could be
implemented efficiently, you would think they would want to show the
benefits of making something more declarative – i.e. flatten queries.
This archive was generated by hypermail 2.1.6 : Mon May 24 2004 - 09:53:08 PDT