WIXLIB

International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 3 Issue 7, July - 2014Query Optimization Based on HeuristicRulesVishal HatmodeDepartment of Information Technology, SiddhantCollege of Engineering, Pune, India.Professor Sonali RangdaleDepartment of Information Technology, SiddhantCollege of Engineering, Pune, India.result of examined queries good query plan is identified. Thismay or may not be the absolute best of all strategies because thereare many ways of creating plans. There is a trade-off between theamount of time spent figuring out the best plan and the amountrunning the plan. Different database management systems havedifferent quality and ways of balancing these two. The mainperformance advantage is achieved in modern database system isby means of query optimizers. [1] Given a request for dataretrieval; an Optimizer will select an optimal plan for evaluatingwith the given request from among the manifold differentstrategies. The largest and most complex module of databasesystems is query optimizers and it’s been proved its difficulty tomodify and extend to accommodate these areas. Queryoptimization is very large area within the database field. It’s beenstudied in a great variety of contexts and from many divergentangles, giving rise to several different solutions in each case.Over time, SQL has become as the standard for relational querylanguages. Query optimization and query execution are the twokey components for query evaluation of an SQL database system[1][6].Heuristic Optimization is less expensive than that of costbased optimization. It is based on some heuristic rules by whichoptimizer can decide optimized query execution plan [6].IJERTAbstract: In this paper, we will Rules based on Heuristicapproach for query optimization. It is often observed inmany database industries that a lot of time is spent inexecuting inefficient SQL queries. The problem here is thatalthough the DBA knows that the query red are inefficient,the large sections of people who are actually running thesequeries are unable to write efficient queries. As a result, theperformance of the entire system affects because of the majorfall in the system performance i.e. the number of transactionsperformed per unit time is reduced. Typically, to overcomethis problem, most of the people frequently consult the DBAfor writing efficient and optimized queries. This approachresults in a lot of time and money loss. A better solution isusing a Query Optimizer Tool. A Query Optimizer willaccept the user query and automatically generate anequivalent but highly optimized and effective query. This willsave a lot of time, cost and effort. This in turn improves thesystem performance and its overall throughput capability.The Query Optimizer in this paper is based on HeuristicOptimizer. It tries to minimize the number of accesses byreducing the number of tuples and number of columns to beselect operation.Backround NeedSpeed of execution is main factor in huge databases ofbiological, physical or chemical projects. Optimization needed forI. INTRODUCTIONsaving energy and resources [2]. The query optimizer is one ofThe main function of many relational database management the important components in today’s database managementsystems is query optimization in which multiple query plans are systems. This component is responsible for transform userto be prepared for satisfying a query are examined, and based on submitted queries usually written in non procedural language intoKeywords: Heuristic Approach, Query Optimization, tuplesIJERTV3IS070992www.ijert.org(This work is licensed under a Creative Commons Attribution 4.0 International License.)1001

International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 3 Issue 7, July - 2014Algebraic Expressions for following querySELECT p.pname, d.dname FROM Patients p, Doctors d Wherep.doctor d.dname AND d.gender 'M'Advantages:1. Rather than considering with the time constraints, it adapts toclient requirements.2. Speed of query retrieval increaseDisadvantages:1. Uses cost based optimization hence expensive.Figure 1: Relational Algebra Expression for QueryIJERTefficient query evaluation program that can be executed againstdatabase. In this paper, we will gain a feel for how queryprocessing works in a database management system, specificallyfocusing on a simple Select-Project-Join query engine. We willalso see how various query execution plans have differentperformance results, which will provide some motivation forquery optimization techniques [5].Today all corporations, companies and organizations likebanks maintain their own databases. These databases are used forholding many different kinds of information like customerdetails, employee details, and so on and so forth. The size of thesedatabases is too huge i.e. containing large amount of records.Retrieval of information is done by querying the database usingSQL. Now if the query used is an inefficient one then it consumesa lot of time before producing the result [6]. This is because aninefficient query requires a lot of memory operations i.e. thenumber of I/O operations is very high. Since in any computersystem the main factor that hampers high speed performance isthe I/O operation, an inefficient query is very slow inperformance which consumes lot of time. Thus an inefficientquery reduces the system performance by reducing thethroughput greatly. Hence being able to write an efficient query isa important. An efficient query reduces the number of diskoperations and hence reduces the number of I/O operations diskaccess rate. As a result an efficient query produces the resultsmuch more quickly than its inefficient counterpart. Nowobviously the question that arises is how to write such an efficientquery? This is where Query Optimizer steps in. This allows youto write your own queries and will in turn generate an equivalentbut highly and efficient optimized query. Thus the QueryOptimizer helps in enhancing the system performance byincreasing the throughput.II. LITERATURE SURVEYDifferent Query Optimization ApproachesCost Based OptimizationA cost-based query optimizer works as follows: First, itgenerates all possible query execution plans. Next, the cost ofeach plan is estimated. Finally, based on the estimation, the planwith the lowest estimated cost is chosen. Since the decision ismade using estimated cost values, the plan chosen may not beoptimal. [1] The quality of optimizer decisions depends on thecomplexity and accuracy of cost functions used. It includesdifferent techniques such as the use of dynamic programming fordeciding best plan. Their main disadvantage is that it is verycostly. As a result most of the optimizers do not employ thisstrategy [2] [3]1. Generates all possible query execution plans and then basedon it cost is calculated.2. Quality depends on complexity and accuracy of the costFunction.IJERTV3IS070992Figure 2: Execution PlanSemantic Query OptimizationTwo queries can be called as a semantically equivalent ifthey return the same answer for a database. For this purpose, ituses integrity constraints to match results. Semantic queryoptimization is known as process of determining the set ofsemantic conversion that result in a semantically equivalent querywith a low execution cost. ODB-Optimizer defines morespecialized classes to be accessed and reduces the number offactors by applying different integrity constraint rules. [2][4]www.ijert.org(This work is licensed under a Creative Commons Attribution 4.0 International License.)1002

International Journal of Engineering Research & Technology (IJERT)ISSN: 2278-0181Vol. 3 Issue 7, July - 2014Advantages1. Supports recursive queries and queries havingdisjunction.Disadvantages:1. Suitable for only simple prototypes.2. No commercial implementations exist.Optimized Query: Select * from (select branch.id from branch)negation, t, (select customer.cid from customer) where t.name 'Brooklyn';Performance Enhancement:1) Projection operations reduce size of relations.2) Reduces the number of columns in relation and hence relationsize reduces.3) Better technique is to use selection rule.III.PROPOSED ARCHITECTUREProposed SystemThe Query Optimizer in this project is a HeuristicOptimiser. It tries to minimize the number of accesses byreducing the number of tuples and number of columns to besearched. Heuristic Optimization is less expensive than that ofcost based optimization. It is based on some heuristic rules bywhich optimiser can decide optimized query execution plan.[1][3][6] Important Heuristic Rules used are:1. Performing selection as early as possible.2. Perform projections as early as possible.Constraints1. The optimizer is a Heuristic optimizer only. It does not containanything related to cost based optimization.2. Parser has certain constraints like it takes only DML queries(select queries) and not any DDL queries.3. Also some of the clauses of SQL such as EXISTS, NOTEXIST and ORDER BY is not taken into consideration.4. Before changing the backend database the correspondingdatabase schema has to be specified before operating on it.5. Transparency for user application is not possibleIJERTIt’s been found that Cost-based optimization is moreexpensive, even with dynamic programming. Systems can useheuristics to decrease the number of choices that have to be madein a cost-based fashion. Heuristic optimization transforms thequery into query-tree by using a set of rules that (but not in allcases) improves execution performance [2][6].1. Perform selection early (reduces the number of tuples)2. Perform projection early (reduces the number of attributes)3. Performing most restrictive selection and join operations (i.e.with smaller result size) before other equivalent operations. [4][6]Few systems use only heuristics; while others combineboth heuristics with partial cost-based optimization.Example of two rulesPerform selection as early as possible.Original Query: Select * from branch, customer wherebranch.name 'Brooklyn' and customer. City 'Brooklyn';Transformed Query: Select * from (select * from branchwhere branch.name 'Brooklyn'), (select * from customer wherecustomer. City 'Brooklyn');Performance enhancement: Suppose there are branchand customer tables each has 100 and 100 tuples respectively.Figure 3: Query Optimization Process FlowIV. DESIGN OF THE PROPOSED SYSTEMDesign SpecificationsOriginal query: 100 * 100 tuples fetchedQuery processing refers to the range of activities involvedOptimized Query: Selection performed early hence say only 10in extracting data from a database. The cost of any processing aand 20 tuples selected so 10*20 tuples fetched.query is usually dominated by disk access, which is slowcompared to memory accessPerform projection as early as possible:Main tasks involved are:Original Query: Select branch.id, customer.cid from branch,1. Parsing the given SQL querycustomer where branch.name 'Brooklyn';2. Transforming it in the form of GLLIJERTV3IS070992www.ijert.org(This work is licensed under a Creative Commons Attribution 4.0 International License.)1003