|
Query optimizers are among the most complex components of database systems.
They provide the physical independence and performance which make relational
systems ubiquitous today.
Dynamic programming and memoization are two fundamental approaches to
optimization, and each is used by different commercial optimizers. The
SQLServer optimizer from Microsoft uses memoization, while the optimizers of
all other major database vendors use dynamic programming. We will describe
the advantages of each approach. In particular, memoization provides early
upper and lower bounds which allow extensive pruning of candidate solutions.
Dynamic programming uses significantly less memory. However, we will
describe some techniques which can minimize memoization's use of memory, at
the cost of compromizing extensibility. Because optimizers are so complex,
it is particularly difficult to compare the two approaches, and many
questions still remain open in this field.
|