Semantic information-based alternative plan generation for multiple query optimization

Polat F. , Cosar A., Alhajj R.

INFORMATION SCIENCES, vol.137, pp.103-133, 2001 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 137
  • Publication Date: 2001
  • Doi Number: 10.1016/s0020-0255(01)00114-1
  • Title of Journal : INFORMATION SCIENCES
  • Page Numbers: pp.103-133
  • Keywords: alternative plan generation, common tasks, multiple query optimization, performance analysis, relational databases, semantic information


This paper addresses the impact of semantic information about queries on alternative plan generation (APG) for multiple query optimization (MQO). MQO covers optimizing the execution of a set of queries together where each query in the set to be optimized has several alternative execution plans. A multiple query optimizer selects an alternative plan for each query to obtain an optimal global execution plan. Our approach uses information such as common relations, common possible joins and common conditions to investigate factors that provide a good estimation of shared tasks between queries. It generates alternative plans for queries having more common tasks. The amount of possible sharing between the queries is determined and used to obtain a fewer number of high quality alternative plans. While doing this, we try to preserve the optimum global execution cost obtained as the result of MQO. Finally, the proposed approach is compared with the other APG approaches described in the literature. The obtained results show that a near optimal solution can be obtained with our technique in less time. (C) 2001 Elsevier Science Inc. All rights reserved.