Query Optimization: An Intelligent Hybrid Approach using Cuckoo and Tabu Search

Query Optimization: An Intelligent Hybrid Approach using Cuckoo and Tabu Search

Mukul Joshi (Department of Computer Science and Information System, Birla Institute of Technology & Science, Pilani Rajasthan, India) and Praveen Ranjan Srivastava (Department of Computer Science and Information System, Birla Institute of Technology & Science, Pilani Rajasthan, India)
Copyright: © 2013 |Pages: 16
DOI: 10.4018/jiit.2013010103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Query optimization is an important aspect in designing database management systems, aimed to find an optimal query execution plan so that overall time of query execution is minimized. Multi join query ordering (MJQO) is an integral part of query optimizer. This paper aims to propose a solution for MJQO problem, which is an NP complete problem. This paper proposes a heuristic based algorithm as a solution of MJQO problem. The proposed algorithm is a combination of two basic search algorithms, cuckoo and tabu search. Simulation shows some exciting results in favour of the proposed algorithm and concludes that proposed algorithm can solve MJQO problem in less amount of time than the existing methods.
Article Preview

1. Introduction

The amount of data is increasing rapidly in today’s world. A database management system (DBMS) plays a big role in storage management and maintenance of data in an efficient manner. Query language is an effective tool, which provides an interface to the user to store and access that data. In past few decades, SQL has emerged as a standard query language (VidyaBanu & Nagaveni, 2012; Rahman, 2010; Chaudhuri, 1998). Two components; query optimizer and query execution engine (Chaudhuri, 1998) do query evaluation. Query optimizer decides in which order to carry out operations in a query, using the fact that traditional relational algebra operators can be executed in a variety of Order (Badia, 2005). Many different combinations of sub queries can be used to evaluate a query. Though the combinations and cost of evaluation are different but every combination is evaluated to the same result. These combinations are called access plans or query execution plans (QEP) (Matysiak, 1995). The job of the query optimizer is to select the optimal (i.e. minimum cost) query execution plan amongst them; this problem is called query optimization problem (Matysiak, 1995). Query optimizer generates many alternative query execution plans for selecting the optimal query plan and estimates the execution cost of each of them to choose the QEP having lowest cost. Optimal query plan selected by query optimizer is forwarded to query execution engine which is responsible for execution of query. Query execution engine uses the QEP which is forwarded by query optimizer. Query optimizer is the most critical step in query evaluation; it decides the execution time and the space complexity of query. Query optimization is itself very complex and expensive; its computational complexity is determined by the number of alternatives for QEPs that must be evaluated before deciding the best query execution plan (Matysiak, 1995), The alternative planes grow exponentially with the increase in number of relations involved in a query. In past three decades this problem is addressed in many ways (Jarke & Koch, 1984; Swami & Gupta, 1988; Horng, Kao, & Liu, 1994; Matysiak, 1995; Steinbrunn, Moerkotte, & Kemper, 1997).

The join operator (Ribeiro, Ribeiro, & Lanzelotte, 1997) relates two tables through their common attributes. Evaluation of a join operation requires the matching of all tuples of relations according to their join attributes (Ribeiro, Ribeiro, & Lanzelotte, 1997). Cosar, Lim, & Srivastava (1995) shows reordering helps to improve the performance of multi query optimization algorithms. So, by reordering the join, query optimizer can lower the cost of execution of the query has join operator in between several tables. First task for a query optimizer is to decide the order of joins, which is called a multi join query optimization, or ordering problem. The multi join ordering is a combinatorial optimization problem (Dong & Liang, 2007) and if the number of input relations and joins are not fixed it is an NP hard problem (Zhou, 2007).

In traditional databases, the total number of relations in multi join queries is usually less than 10 which can be handled by dynamic programming approaches effectively (Li, Liu, Dong, & Gu, 2008). Nowadays the complexity of this problem increases due to the generation of complex multi join queries in some modern applications, such as knowledge base systems, decision support systems, expert systems, On-Line Analytical Processing (OLAP) and data mining etc. Sometimes, the generated query has more than 100 tables in a join (Li, Liu, Dong, & Gu, 2008).

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 14: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing