Chapter 19: Query Optimization PDF

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe  CHAPTER 19 Query Optimization Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Introduction n Query optimization n Conducted by a query optimizer in a DBMS n...

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe  CHAPTER 19 Query Optimization Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Introduction n Query optimization n Conducted by a query optimizer in a DBMS n Goal: select best available strategy for executing query n Based on information available n Most RDBMSs use a tree as the internal representation of a query Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 3 19.1 Query Trees and Heuristics for Query Optimization n Step 1: scanner and parser generate initial query representation n Step 2: representation is optimized according to heuristic rules n Step 3: query execution plan is developed n Execute groups of operations based on access paths available and files involved Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 4 Query Trees and Heuristics for Query Optimization (cont’d.) n Example heuristic rule n Apply SELECT and PROJECT before JOIN n Reduces size of files to be joined n Query tree n Represents relational algebra expression n Query graph n Represents relational calculus expression n Example for Q2 on next slide Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 5 Query Trees and Query Graph Corresponding to Q2 Figure 19.1 Two query trees for the query Q2. (a) Query tree corresponding to the relational algebra expression for Q2. (b) Initial (canonical) query tree for SQL query Q2. (c) Query graph for Q2. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19-6 Query Trees and Heuristics for Query Optimization (cont’d.) n Query tree represents a specific order of operations for executing a query n Preferred to query graph for this reason n Query graph n Relation nodes displayed as single circles n Constants represented by constant nodes n Double circles or ovals n Selection or join conditions represented as edges n Attributes to be retrieved displayed in square brackets Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 7 Heuristic Optimization of Query Trees n Many different query trees can be used to represent the query and get the same results n Figure 19.1b shows initial tree for Q2 n Very inefficient - will never be executed n Optimizer will transform into equivalent final query tree Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 8 Query Transformation Example Figure 19.2 Steps in converting a query tree during heuristic optimization. (a) Initial (canonical) query tree for SQL query Q. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 9 Query Transformation Example (cont’d.) Figure 19.2 Steps in converting a query tree during heuristic optimization (b) Moving SELECT operations down the query tree. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 10 Query Transformation Example (cont’d.) Figure 19.2 Steps in converting a query tree during heuristic optimization (c) Applying the more restrictive SELECT operation first. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 11 Query Transformation Example (cont’d.) Figure 19.2 Steps in converting a query tree during heuristic optimization (d) Replacing CARTESIAN PRODUCT and SELECT with JOIN operations. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 12 Query Transformation Example (cont’d.) Figure 19.2 Steps in converting a query tree during heuristic optimization (e) Moving PROJECT operations down the query tree. Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 13 General Transformation Rules for Rational Algebra Equations n Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 14 Summary of Heuristics for Algebraic Optimization n Apply first the operations that reduce the size of intermediate results n Perform SELECT and PROJECT operations as early as possible to reduce the number of tuples and attributes n The SELECT and JOIN operations that are most restrictive should be executed before other similar operations Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 15 19.2 Choice of Query Execution Plans n Materialized evaluation n Result of an operation stored as temporary relation n Pipelined evaluation n Operation results forwarded directly to the next operation in the query sequence Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 16 Nested Subquery Optimization n Unnesting n Process of removing the nested query and converting the inner and outer query into one block n Queries involving a nested subquery connected by IN or ANY connector can always be converted into a single block query n Alternate technique n Creating temporary result tables from subqueries and using them in joins Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 17 Subquery (View) Merging Transformation n Inline view n FROM clause subquery n View merging operation n Merges the tables in the view with the tables from the outer query block n Views containing select-project-join operations are considered simple views n Can always be subjected to this type of view- merging Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 18 Subquery (View) Merging Transformation (cont’d.) n Group-By view-merging n Delaying the Group By operation after performing joins may reduce the data subjected to grouping in case the joins have low join selectivity n Alternately, performing Group By early may reduce the amount of data subjected to subsequent joins n Optimizer determines whether to merge GROUP- BY views based on estimated costs Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 19 Materialized Views n View defined in database as a query n Materialized view stores results of that query n May be stored temporarily or permanently n Optimization technique n Using materialized views to avoid some of the computation involved in the query n Easier to read it when needed than recompute from scratch Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 20 Incremental View Maintenance n Update view incrementally by accounting for changes that occurred since last update n Join n Selection n Projection n Intersection n Aggregation Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 21 19.3 Use of Selectives in Cost-Based Optimization n Query optimizer estimates and compares costs of query execution using different strategies n Chooses lowest cost estimate strategy n Process suited to compiled queries n Interpreted queries n Entire process occurs at runtime n Cost estimate may slow down response time Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 22 Use of Selectives in Cost-Based Optimization (cont’d.) n Cost-based query optimization approach n For a given query subexpression, multiple equivalence rules may apply n Quantitative measure for evaluating alternatives n Cost metric includes space and time requirements n Design appropriate search strategies by keeping cheapest alternatives and pruning costlier alternatives n Scope of query optimization is a query block n Global query optimization involves multiple query blocks Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 23 Use of Selectives in Cost-Based Optimization (cont’d.) n Cost components for query execution n Access cost to secondary storage n Disk storage cost n Computation cost n Memory usage cost n Communication cost Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 24 Catalog Information Used in Cost Functions n Information stored in DBMS catalog and used by optimizer n File size n Organization n Number of levels of each multilevel index n Number of distinct values of an attribute n Attribute selectivity n Allows calculation of selection cardinality n Average number of records that satisfy equality selection condition on that attribute Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 25 Histograms n Tables or data structures that record information about the distribution of data n RDBMS stores histograms for most important attributes Figure 19.4 Histogram of salary in the relation EMPLOYEE Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 26 19.4 Cost Functions for SELECT Operation n Notation used in cost formulas Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 27 Cost Function for SELECT Operation (cont’d.) n S1: Linear search (brute force approach) n Search all file blocks to retrieve all records CS1a=b n For equality condition on a key attribute, on average one-half the records are searched ! CS1b=" n S2: Binary search # CS2=log2b+[ ]-1 !$% n Reduces to log2b if equality condition is on a key attribute Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 28 Cost Function for SELECT Operation (cont’d.) n S3a: Using a primary index to retrieve a single record CS3a = x + 1 n S3b: Using a hash key to retrieve a single record CS3b = 1 n S4: Using an ordering index to retrieve multiple records ! CS4 = x + " Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 29 Cost Functions for SELECT Operation (cont’d.) n Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 30 Cost Functions for SELECT Operation (cont’d.) n Dynamic programming n Cost-based optimization approach n Subproblems are solved only once n Applies when a problem has subproblems that themselves have subproblems Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 31 19.5 Cost Functions for the JOIN Operation n Cost functions involve estimate of file size that results from the JOIN operation n Join selectivity n Ratio of the size of resulting file to size of the CARTESIAN PRODUCT file n Simple formula for join selectivity n Join cardinality Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 32 Cost Functions for the JOIN Operation (cont’d.) n J1: Nested-loop join n For three memory buffer blocks: n For nB memory buffer blocks: n J2: Index-based nested-loop join n For a secondary index with selection cardinality SB for join attribute B of S: Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 33 Cost Functions for the JOIN Operation (cont’d.) n J3: Sort-merge join n For files already sorted on the join attributes n Cost of sorting must be added if sorting needed n J4: Partition-hash join Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 34 Cost Functions for the JOIN Operation (cont’d.) n Join selectivity and cardinality for semi-join n Unnesting query above leads to semi-join n Join selectivity n Join cardinality Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 35 Cost Functions for the JOIN Operation (cont’d.) n Join selectivity and cardinality for anti-join n Unnesting query above leads to anti-join n Join selectivity n Join cardinality Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 36 Cost Functions for the JOIN Operation (cont’d.) n Multirelation queries and JOIN ordering choices n Left-deep join tree n Right-deep join tree n Bushy join tree Table 19.1 Number of permutations of left-deep and bushy join trees of n relations Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 37 Cost Functions for the JOIN Operation (cont’d.) n Physical optimization involves execution decision at the physical level n Cost-based physical optimization n Top-down approach n Bottom-up approach n Certain physical level heuristics make cost optimizations unnecessary n Example: for selections, use index scans whenever possible Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 38 Cost Functions for the JOIN Operation (cont’d.) n Left-deep trees generally preferred n Work well for common algorithms for join n Able to generate fully pipelined plans n Characteristics of dynamic programming algorithm n Optimal solution structure is developed n Value of the optimal solution is recursively defined n Optimal solution is computed and its value developed in a bottom-up fashion Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 39 19.6 Example to Illustrate Cost-Based Query Optimization n Example: Consider Q2 below and query tree from Figure 19.1(a) on slide 6 n Information about the relations shown in Figure 19.6 (next slide) Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 40 Figure 19.6 Sample statistical information for relations in Q2. (a) Column information (b) Table information (c) Index information Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19-41 Example to Illustrate Cost-Based Query Optimization (cont’d.) n Assume optimizer considers only left-deep trees n Evaluate potential join orders n PROJECT DEPARTMENT EMPLOYEE n DEPARTMENT PROJECT EMPLOYEE n DEPARTMENT EMPLOYEE PROJECT n EMPLOYEE DEPARTMENT PROJECT Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 16- 42 19.7 Additional Issues Related to Query Optimization n Displaying the system’s query execution plan n Oracle syntax n EXPLAIN PLAN FOR n IBM DB2 syntax n EXPLAIN PLAN SELECTION [additional options] FOR n SQL server syntax n SET SHOWPLAN_TEXT ON or SET SHOWPLAN_XML ON or SET SHOWPLAN_ALL ON Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 43 Additional Issues Related to Query Optimization (cont’d.) n Size estimation of other operations n Projection n Set operations n Aggregation n Outer join n Plan caching n Plan stored by query optimizer for later use by same queries with different parameters n Top k-results optimization n Limits strategy generation Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 44 19.8 An Example of Query Optimization in Data Warehouses n Star transformation optimization n Goal: access a reduced set of data from the fact table and avoid using a full table scan on it n Classic star transformation n Bitmap index star transformation n Joining back Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 45 19.9 Overview of Query Optimization in Oracle n Physical optimizer is cost-based n Scope is a single query block n Calculates cost based on object statistics, estimated resource use and memory needed n Global query optimizer n Integrates logical transformation and physical optimization phases to generate optimal plan for entire query tree n Adaptive optimization n Feedback loop used to improve on previous decisions Slide 19- 46 Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Overview of Query Optimization in Oracle (cont’d.) n Array processing n Hints n Specified by application developer n Embedded in text of SQL statement n Types: access path, join order, join method, enabling or disabling a transformation n Outlines used to preserve execution plans n SQL plan management Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 47 19.10 Semantic Query Optimization n Uses constraints specified on the database schema n Goal: modify one query into another that is more efficient to execute Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 48 19.11 Summary n Query trees n Heuristic approaches used to improve efficiency of query execution n Reorganization of query trees n Pipelining and materialized evaluation n Cost-based optimization approach n Oracle query optimizer n Semantic query optimization Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 19- 49