For a number of reasons, even the best query optimizers can very often
produce sub-optimal query execution plans, leading to a significant
degradation of performance. This is especially true in databases used
for complex decision support queries and/or object-relational
databases. In this paper, we describe an algorithm that detects
sub-optimality of a query execution plan during query execution and
attempts to correct the problem. The basic idea is to collect statistics
at key points during the execution of a complex query. These
statistics are then used to optimize the execution of the query,
either by improving the resource allocation for that query, or by
changing the execution plan for the remainder of the query. To ensure
that this does not significantly slow down the normal execution of a
query, the Query Optimizer carefully chooses what statistics to
collect, when to collect them, and the circumstances under which to
re-optimize the query. We describe an implementation of this algorithm
in the Paradise Database System, and we report on performance studies,
which indicate that this can result in significant improvements in
the performance of complex queries.