Chapter 19 Algorithms for Query Processing and Optimization Copyright 2011 Pearson Education Inc Publishing as Pearson Addison Wesley Introduction to Query Processing 1 Copyright 2011 Ramez Elmasri and Shamkant Navathe Introduction to Query Processing 2 Query optimization The process of choosing an efficient execution strategy for processing a query Two internal representations of a query Query Tree Query Graph Copyright 2011 Ramez Elmasri and Shamkant Navathe 1 Translating SQL Queries into Relational Algebra 1 Query block The basic unit that can be translated into the algebraic operators and optimized A query block contains a single SELECT FROMWHERE expression as well as GROUP BY and HAVING clause if these are part of the block Nested queries within a query are identified as separate query blocks Aggregate operators in SQL must be included in the extended algebra Copyright 2011 Ramez Elmasri and Shamkant Navathe Translating SQL Queries into Relational Algebra 2 SELECT FROM WHERE SELECT FROM WHERE LNAME FNAME EMPLOYEE SALARY SELECT FROM WHERE LNAME FNAME EMPLOYEE SALARY C LNAME FNAME SALARY C EMPLOYEE Copyright 2011 Ramez Elmasri and Shamkant Navathe SELECT FROM WHERE MAX SALARY EMPLOYEE DNO 5 MAX SALARY EMPLOYEE DNO 5 MAX SALARY DNO 5 EMPLOYEE 2 Algorithms for SELECT and JOIN Operations 1 Implementing the SELECT Operation Examples OP1 SSN 123456789 EMPLOYEE OP2 DNUMBER 5 DEPARTMENT OP3 DNO 5 EMPLOYEE OP4 DNO 5 AND SALARY 30000 AND SEX F EMPLOYEE OP5 ESSN 123456789 AND PNO 10 WORKS ON Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 2 Implementing the SELECT Operation contd Search Methods for Simple Selection S1 Linear search brute force S2 Binary search Retrieve every record in the file and test whether its attribute values satisfy the selection condition If the selection condition involves an equality comparison on a key attribute on which the file is ordered binary search which is more efficient than linear search can be used See OP1 S3 Using a primary index or hash key to retrieve a single record If the selection condition involves an equality comparison on a key attribute with a primary index or a hash key use the primary index or the hash key to retrieve the record Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 3 Implementing the SELECT Operation contd Search Methods for Simple Selection S4 Using a primary index to retrieve multiple records S5 Using a clustering index to retrieve multiple records If the comparison condition is or on a key field with a primary index use the index to find the record satisfying the corresponding equality condition then retrieve all subsequent records in the ordered file If the selection condition involves an equality comparison on a nonkey attribute with a clustering index use the clustering index to retrieve all the records satisfying the selection condition S6 Using a secondary B tree index On an equality comparison this search method can be used to retrieve a single record if the indexing field has unique values is a key or to retrieve multiple records if the indexing field is not a key In addition it can be used to retrieve records on conditions involving or FOR RANGE QUERIES Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 4 Implementing the SELECT Operation contd Search Methods for Simple Selection S7 Conjunctive selection If an attribute involved in any single simple condition in the conjunctive condition has an access path that permits the use of one of the methods S2 to S6 use that condition to retrieve the records and then check whether each retrieved record satisfies the remaining simple conditions in the conjunctive condition S8 Conjunctive selection using a composite index If two or more attributes are involved in equality conditions in the conjunctive condition and a composite index or hash structure exists on the combined field we can use the index directly Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 5 Implementing the SELECT Operation contd Search Methods for Complex Selection S9 Conjunctive selection by intersection of record pointers This method is possible if secondary indexes are available on all or some of the fields involved in equality comparison conditions in the conjunctive condition and if the indexes include record pointers rather than block pointers Each index can be used to retrieve the record pointers that satisfy the individual condition The intersection of these sets of record pointers gives the record pointers that satisfy the conjunctive condition which are then used to retrieve those records directly If only some of the conditions have secondary indexes each retrieved record is further tested to determine whether it satisfies the remaining conditions Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 7 Implementing the SELECT Operation contd Whenever a single condition specifies the selection we can only check whether an access path exists on the attribute involved in that condition If an access path exists the method corresponding to that access path is used otherwise the brute force linear search approach of method S1 is used See OP1 OP2 and OP3 For conjunctive selection conditions whenever more than one of the attributes involved in the conditions have an access path query optimization should be done to choose the access path that retrieves the fewest records in the most efficient way Disjunctive selection conditions Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 8 Implementing the JOIN Operation Join EQUIJOIN NATURAL JOIN two way join a join on two files e g R A B S multi way joins joins involving more than two files e g R A B S C D T Examples OP6 EMPLOYEE DNO DNUMBER DEPARTMENT OP7 DEPARTMENT MGRSSN SSN EMPLOYEE Copyright 2011 Ramez Elmasri and Shamkant Navathe Algorithms for SELECT and JOIN Operations 9 Implementing the JOIN Operation contd Methods for implementing joins J1 Nested loop join brute force For each record t in R outer loop retrieve every record s from S inner loop and test whether the two records satisfy the join condition t A s B J2 Single loop join Using an access structure to retrieve the matching records If an index or hash key exists for one of the two join attributes say B of S retrieve each record t in R one at a time and
View Full Document
Unlocking...