Alternative Plan Generation methods for Multiple Query Optimization

Date

1998-10-28

Author

Menekse, G
Polat, Faruk
Cosar, A

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

153
views

0
downloads

Alternative Plan Generation (APG) is an important phase of Multiple Query Optimization (MQO) in relational databases. It is necessary to generate a number of alternative plans in such a way that the sharing between queries is maximized and an optimal execution plan with minimal cost is obtained. For relational databases several methods have previously been proposed for generating alternative plans using commutativity and associativity properties of select, project and join operations. When all possible alternative plans are generated using these properties, the number of alternative plans to be used in MQO will be quite large leading to an unacceptable increase in the cost of APG which eliminates the benefits of MQO for query execution. The quality of the alternative plans determines the cost of the global execution plan for the queries. In this paper, we propose a new method for APG that uses information about the queries to best utilize the sharing between the queries. This method generates the alternative plans for queries having more common tasks by introducing the factors that provides a good estimation of shared tasks of queries using information such as common relations, common possible joins and common conditions. We also compare benefits obtained from MQO with the previously proposed APG methods and with our method, and show that it is possible to find a near optimal solution with this technique. For 14 queries and a database of 15 relations on the average, MQO performs 30 times faster by using the alternative plans generated by this new method while we are within 7% of the optimal solution.

URI

https://hdl.handle.net/11511/52895

Conference Name

13th International Symposium on Computer and Information Sciences (ISCIS 98)

Collections

Department of Computer Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

Semantic information-based alternative plan generation for multiple query optimization Polat, Faruk; Alhajj, R (Elsevier BV, 2001-09-01) 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...
Exploiting query views for static index pruning in web search engines Altıngövde, İsmail Sengör; Ulusoy, Özgür (2009-12-01) We propose incorporating query views in a number of static pruning strategies, namely term-centric, document-centric and access-based approaches. These query-view based strategies considerably outperform their counterparts for both disjunctive and conjunctive query processing in Web search engines.
Integer Linear Programming Solution for the Multiple Query Optimization Problem Dokeroglu, Tansel; Bayir, Murat Ali; Coşar, Ahmet (2014-10-28) Multiple Query Optimization (MQO) is a technique for processing a batch of queries in such a way that shared tasks in these queries are executed only once, resulting in significant savings in the total evaluation. The first phase of MQO requires producing alternative query execution plans so that the shared tasks between queries are identified and maximized. The second phase of MQO is an optimization problem where the goal is selecting exactly one of the alternative plans for each query to minimize the tota...
Improving the performance of Hadoop/Hive by sharing scan and computation tasks Özal, Serkan; Toroslu, İsmail Hakkı; Doğaç, Asuman; Department of Computer Engineering (2013) MapReduce is a popular model of executing time-consuming analytical queries as a batch of tasks on large scale data. During simultaneous execution of multiple queries, many oppor- tunities can arise for sharing scan and/or computation tasks. Executing common tasks only once can reduce the total execution time of all queries remarkably. Therefore, we propose to use Multiple Query Optimization (MQO) techniques to improve the overall performance of Hadoop Hive, an open source SQL-based distributed warehouse sy...
Multiple query optimization with depth first branch and bound and dynamic query ordering Coşar, Ahmet; Lım, Ee Peng; Srıvastava, Jaıdeep (null; 1993-09-01) In certain database applications such as deductive databases, batch query processing, and recursive query processing etc., a single query can be transformed into a set of closely related database queries. Great benefits can be obtained by executing a group of related queries all together in a single unified multi-plan instead of executing each query separately. In order to achieve this, Multiple Query Optimization (MQO) identifies common task(s) (e.g. common subexpressions, joins, etc.) among a set of query...

Citation Formats

G. Menekse, F. Polat, and A. Cosar, “Alternative Plan Generation methods for Multiple Query Optimization,” Antalya, Turkey, 1998, vol. 53, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/52895.