  We identify two unreasonable, though standard, assumptions made by database
query optimizers that can adversely affect the quality of the chosen evaluation
plans. One assumption is that it is enough to optimize for the expected
case---that is, the case where various parameters (like available memory) take
on their expected value. The other assumption is that the parameters are
constant throughout the execution of the query. We present an algorithm based
on the ``System R''-style query optimization algorithm that does not rely on
these assumptions. The algorithm we present chooses the plan of the least
expected cost instead of the plan of least cost given some fixed value of the
parameters. In execution environments that exhibit a high degree of
variability, our techniques should result in better performance.
