Unit 2 Query Optimization and Execution Strategies Study Guide

Introduction




Goal of Query Optimization: The primary objective is to select the best possible strategy for query evaluation.
  • The Optimization Misnomer: The term "optimization" is technically a misnomer because the execution plan chosen by the system might not always be the absolute most optimal plan possible.

  • Objectives of the Optimizer: The goal is to arrive at the most efficient and cost-effective plan using available information about the schema and relation content, within a reasonable amount of time.

  • Role of the Query Optimizer: This is a dedicated activity conducted by the query optimizer within a Database Management System (DBMS) to select the best available strategy for executing queries.

Query Trees and Heuristics for Query Optimization

  • Heuristic Rules: These rules are utilized to modify the internal representation of a query, which is typically stored as a query tree or query graph data structure, to improve expected performance.

  • Optimized Representation: An optimized version of the query is generated to execute groups of operations based on the specific access paths available on the files involved.

  • Order of Operations: A key example of a heuristic is applying SELECT and PROJECT operations before JOIN or other binary operations. This reduces the size of the intermediate files before they undergo more computationally expensive processes.

  • Query Tree Notation:

    •  Structure: A tree data structure corresponding to an extended relational algebra expression.

    • Leaf Nodes: Represent input database relations.

    • Internal Nodes: Represent relational algebra operations.

    • Execution Flow: Internal nodes are executed whenever their operands (children) are available. The internal node is then replaced by the resulting relation. Execution starts at the leaves and concludes at the root.

    • Termination: The process ends when the root node is executed, producing the final result relation.

  • Example Case (Stafford Project):

    • SQL Query:         SELECT P.Pnumber, P.Dnum, E.Lname, E.Address, E.Bdate         FROM PROJECT P, DEPARTMENT D, EMPLOYEE E         WHERE P.Dnum=D.Dnumber AND D.Mgr_ssn=E.Ssn AND P.Plocation= 'Stafford';

    • Relational Algebra Representation: πPnumber,Dnum,Lname,Address,Bdate(((σPlocation=′Stafford′(PROJECT))⋈Dnum=Dnumber(DEPARTMENT))⋈Mgrssn=Ssn(EMPLOYEE))π_{Pnumber, Dnum, Lname, Address, Bdate} (((σ_{Plocation = 'Stafford'} (PROJECT)) ⋈_{Dnum = Dnumber} (DEPARTMENT)) ⋈_{Mgr_ssn=Ssn} (EMPLOYEE))

  • Query Graph Notation:

    • Relation Nodes: Represented by single circles.

    • Constant Nodes: Represented by double circles or ovals.

    • Edges: Represent selection and join conditions.

    • Attributes: Displayed in square brackets above the corresponding relation.

    • Comparison: Unlike query trees, query graphs do not indicate the specific order of operations. While some techniques use them, query trees are generally preferred in practice because optimizers must specify the order of execution.

  • Heuristic Optimization of Query Trees:

    • Initial (Canonical) Query Tree: Generated by the query parser without optimization. This tree is often very inefficient if executed directly.

    • Transformation Process: The heuristic optimizer transforms the initial tree into an equivalent final tree that is more efficient. This requires rules for equivalence among extended relational algebra expressions.

    • Step-by-Step Optimization Example (Aquarius Query):

      • Query Q: SELECT E.Lname FROM EMPLOYEE E, WORKS_ON W, PROJECT P WHERE P.Pname='Aquarius' AND P.Pnumber=W.Pno AND E.Essn=W.Ssn AND E.Bdate>'1957-12-31';

      • Transformation (b): Moving SELECT operations down the tree.

      • Transformation (c): Applying the more restrictive SELECT operation first.

      • Transformation (d): Replacing CARTESIAN PRODUCT and SELECT with JOIN operations.

      • Transformation (e): Moving PROJECT operations down the tree to minimize attributes passed up.

  • Summary of Algebraic Heuristics:

    • Apply operations first that reduce the size of intermediate results.

    • Perform SELECT and PROJECT as early as possible.

    • Execute the most restrictive SELECT and JOIN operations before others.

Choice of Query Execution Plans

  • Execution Plan Components: Includes the access methods for each relation and the specific algorithms used to compute relational operators in the tree.

  • Evaluation Types:

    • Materialized Evaluation: The result of an operation is stored as a temporary relation in storage.

    • Pipelined Evaluation: Resulting tuples are forwarded directly to the next operation as they are produced. This is generally preferred whenever feasible.

  • Nested Subquery Optimization:

    • Unnesting: The process of removing a nested query and converting the inner and outer queries into a single block.

    • Queries with IN or ANY connectors can typically be converted into a single block query.

    • Other techniques include creating temporary result tables from subqueries to be used in joins.

  • Subquery and View Merging:

    • Inline View: A subquery appearing in the FROM clause.

    • View-Merging: Merging the tables within a view with the tables in the outer query block to provide the optimizer more options. Simple views (select-project-join) are always eligible.

    • Complexity Limitations: View merging may be invalid if the view contains DISTINCT, OUTER JOIN, AGGREGATION, GROUP BY, or set operations.

  • Materialized Views:

    • Stores the results of a query (temporarily or permanently) to avoid recomputation.

    • Refresh/Update Strategies:

      • Immediate Update: Updates the view immediately when a base relation is modified.

      • Lazy Update: Recomputes the view only when it is demanded by a query.

      • Periodic (Deferred) Update: Updates the view at regular intervals.

    • Incremental View Maintenance: Instead of recomputing from scratch, the system calculates the net change based on inserted or deleted tuples in the base relations.

Use of Selectivities in Cost-Based Optimization

  • Definition: Cost-based optimization estimates and compares the costs of different execution strategies to choose the one with the lowest estimate.

  • Trade-offs: The optimizer must limit the number of strategies considered to avoid excessive overhead. This is better suited for compiled queries rather than interpreted ones.

  • Scope: Optimization usually occurs at the level of a single query block, though global optimization can span multiple blocks.

  • Cost Components:

    • Access Cost: Disk I/O cost of transferring blocks between secondary storage and main memory.

    • Disk Storage Cost: Cost of storing intermediate files generated during execution.

    • Computation (CPU) Cost: Cost of in-memory operations on records in buffers.

    • Memory Usage Cost: Cost related to the number of main memory buffers required.

    • Communication Cost: Cost of shipping queries and results in distributed systems.

    • Simplified Cost Function: Often, cost functions focus solely on the number of block transfers (disk access).

  • DBMS Catalog Information:

    • rr: Number of records (tuples) in a file.

    • RR: Average record size.

    • bb: Number of file blocks.

    • bfrbfr: Blocking factor (number of tuples per block).

    • xx: Number of levels in a multilevel index.

    • bI1b_{I1}: Number of first-level index blocks.

    • **NDV(A,R)NDV(A, R): Number of distinct values of an attribute AA in relation RR.

    • slsl: Attribute selectivity (fraction of records satisfying an equality condition).

    • ss: Selection cardinality (s=sl×rs = sl \times r), representing the average number of records satisfying an equality selection.

  • Histograms:

    • Used to record the distribution of data across "buckets" (ranges).

    • Equi-width Histograms: Divide the value range into equal subranges.

    • Equi-height Histograms: Form buckets so each contains approximately the same number of records.

Cost Functions for SELECT Operation

  • S1: Linear Search: Costs bb blocks. For equality on a key, average cost is b2\frac{b}{2}.

  • S2: Binary Search: Estimated cost is log⁡2(b)+⌈sbfr⌉−1\log_2(b) + \lceil \frac{s}{bfr} \rceil - 1. For unique keys, this simplifies to log⁡2(b)\log_2(b).

  • S3a: Primary Index (Single Record retrieval): Cost is x+1x + 1 (index levels plus one data block).

  • S3b: Hash Key: Cost is approximately 11 for static/linear hashing and 22 for extendible hashing.

  • S4: Ordering Index (Multiple Records): For conditions like >>, ≥≥, ≤≤, cost is roughly x+(b2)x + (\frac{b}{2}).

  • S5: Clustering Index: Cost is x+⌈sbfr⌉x + \lceil \frac{s}{bfr} \rceil.

  • S6: Secondary (B+-tree) Index:

    • Equality on Key: x+1x + 1 block accesses.

    • Equality on Non-key: Costs x+1+sx + 1 + s (assuming each record is on a different block).

    • Range Queries: Estimated cost is x+(bI12)+(r2)x + (\frac{b_{I1}}{2}) + (\frac{r}{2}).

  • S7: Conjunctive Selection: Uses S1 or a combination of S2 through S6.

  • S8: Composite Index: Uses same logic as S3a, S5, or S6a based on index type.

  • S9: Bitmap Index: If ss records qualify, cost is ss data block accesses.

  • S10: Functional Index: Operates like S6 but utilizes indices based on functions of multiple attributes.

/