Accession Number:

ADA461520

Title:

Optimization of Dynamic Query Evaluation Plans

Descriptive Note:

Corporate Author:

COLORADO UNIV AT BOULDER DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1993-12-01

Pagination or Media Count:

28.0

Abstract:

Traditional query optimizers assume accurate knowledge of run-time parameters such as selectivities and resource availability during plan optimization, i.e., at compile-time. In reality, however, this assumption is often not justified. Therefore, the static plans produced by traditional optimizers may not be optimal for many of their actual run-time invocations. Instead, we propose a novel optimization model that assigns the bulk of the optimization effort to compile-time and delays carefully selected optimization decisions until run-time. Our previous work defined the run-time primitives, dynamic plans using choose-plan operators, for executing such delayed decisions, but did not solve the problem of constructing dynamic plans at compile-time. The present paper introduces techniques that solve this problem. Experience with a working prototype optimizer demonstrates i that the additional optimization and start-up overhead of dynamic plans compared to static plans is dominated by their advantage at run-time, ii that dynamic plans are as robust as the brute-force remedy of run-time optimization, i.e., dynamic plans maintain their optimality even if parameters change between compile-time and run-time, and iii that the start-up overhead of dynamic plans is significantly less than the time required for complete optimization at run-time. In other words, our proposed techniques are superior to both techniques considered to-date, namely compile-time optimization into a single static plan as well as run-time optimization. Finally, we believe that the concepts and technology described can be transferred to most commercial query optimizers in order to improve the performance of embedded quenes with host variables in the query predicate.

Subject Categories:

  • Information Science
  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE