Chapter 19: Query Optimization Study Guide

Chapter 19: Query Optimization

Section 19.1: Overview

  • Topics not covered in the current discussion:

    • Query Trees and Heuristics for Query Optimization

    • Choice of Query Execution Plans

    • Use of Selectivities in Cost-Based Optimization

Section 19.4: Cost Functions for SELECT Operation

  • Cost functions are provided for selection algorithms S1 to S8 based on the number of block transfers between memory and disk.

  • Important Note:

    • Algorithm S9: Involves intersection of record pointers after retrieval by another means, typically associated with Algorithm S6.

    • Cost function formulated based on the cost for S6.

  • These cost functions primarily estimate costs and do not factor computation time, storage cost, or other elements.

Variables Used in Cost Estimates

Catalog Information for Cost Functions
  • Detailed while considering:

    • File Size Information:

    • B – Block size (in kilobytes, kb)

    • R – Record size (in kilobytes, kb)

    • r – Number of records (tuples)

    • b – Number of blocks

    • bfr – Blocking factor defined as follows:

      • Blocking Factor Formula:

      • For records: (bfr=extfloor(B/R))(bfr = ext{floor}(B/R))

      • For tuples: (bfr=extceil(r/b))(bfr = ext{ceil}(r/b))

      • Relationship: r=b∗bfrr = b * bfr

Section 19.5: Cost Functions for the JOIN Operation

Examples of Cost Functions for JOIN
  • J1. Nested-Loop Join:

    • Utilizing table R for the outer loop:

    • Cost Function:

    • CJ1=b<em>R+(b</em>R∗b<em>S)+rac(j</em>s∗∣R∣∗∣S∣)bfrRSCJ1 = b<em>R + (b</em>R * b<em>S) + rac{(j</em>s * |R| * |S|)}{bfr_{RS}}

J2: Single-Loop Join
  • Aids in retrieving matching records:

    • If an index exists for the join attribute B in S with x_B (index levels), one can retrieve each record s in R and use the index to get matching records t from S while satisfying the condition t[B] = s[A].

    • The cost varies based on the type of index:

    • Secondary index on S:

      • CJ2a=b<em>R+(∣R∣∗(x</em>B+1+s<em>B))+rac(j</em>s∗∣R∣∗∣S∣)bfrRSCJ2a = b<em>R + (|R| * (x</em>B + 1 + s<em>B)) + rac{(j</em>s * |R| * |S|)}{bfr_{RS}}

    • Clustering index on S:

      • CJ2b=b<em>R+(∣R∣∗(x</em>B+(s<em>B/bfr</em>B)))+rac(j<em>s∗∣R∣∗∣S∣)bfr</em>RSCJ2b = b<em>R + (|R| * (x</em>B + (s<em>B / bfr</em>B))) + rac{(j<em>s * |R| * |S|)}{bfr</em>{RS}}

    • Primary index on S:

      • CJ2c=b<em>R+(∣R∣∗(x</em>B+1))+rac(j<em>s∗∣R∣∗∣S∣)bfr</em>RSCJ2c = b<em>R + (|R| * (x</em>B + 1)) + rac{(j<em>s * |R| * |S|)}{bfr</em>{RS}}

    • Hash key for join attributes - S.B:

      • CJ2d=b<em>R+(∣R∣∗h)+rac(j</em>s∗∣R∣∗∣S∣)bfrRSCJ2d = b<em>R + (|R| * h) + rac{(j</em>s * |R| * |S|)}{bfr_{RS}}

Sort-Merge Join (J3)
  • The cost associated:

    • Cost for sorting files:

    • CJ3a=C<em>S+b</em>R+b<em>S+rac(j</em>s∗∣R∣∗∣S∣)bfrRSCJ3a = C<em>S + b</em>R + b<em>S + rac{(j</em>s * |R| * |S|)}{bfr_{RS}}

Example: Estimated Join Cost

  • Consider EMPLOYEE and DEPARTMENT files:

    • DEPARTMENT file consists of:

    • rD = 125 records stored in bD = 13 disk blocks

    • Join Operations OP6:

    • EMPLOYEE⋈Dno=DnumberDEPARTMENTEMPLOYEE \bowtie_{Dno=Dnumber} DEPARTMENT

Data for OP6 and OP7
  • Details provided in the following table:

    • Table_name | Num_rows | Blocks

    • Employee | 10,000 | 2,000

    • Department | 125 | 13

    • Table_name | Index_column | Unique | Index_type

    • Employee | Ssn | 1 | Yes (Primary)

    • Employee | Dno | 1 | No (Secondary)

    • Department | Dnumber | 1 | Yes (Primary)

    • Department | Mgr_ssn | 1 | Yes (Secondary)

Determine Lowest Estimated Cost for OP6

  • Join operations are considered:

    • Assuming blocking factor for the join bfrEMP−DEPT=4bfr_{EMP-DEPT} = 4

Cost-Based Query Optimization (Example for OP6)
  • Method J1 with EMPLOYEE as the outer loop:

    • CJ1=b<em>D+(b</em>D∗b<em>E)+rac(j</em>sOP6∗r<em>D∗r</em>E)bfrEDCJ1 = b<em>D + (b</em>D * b<em>E) + rac{(j</em>{sOP6} * r<em>D * r</em>E)}{bfr_{ED}}

    • CJ1=13+(13∗2000)+rac(1/125∗10,000∗125)4CJ1 = 13 + (13 * 2000) + rac{(1/125 * 10,000 * 125)}{4}

    • End cost is calculated as 30,50030,500.

  • Method J2 with EMPLOYEE as the outer loop:

    • Since Dnumber in DEPARTMENT is the primary key:

    • CJ2c=b<em>E+(r</em>E∗(x<em>Dnumber+1))+rac(j</em>sOP6∗r<em>E∗r</em>D)bfrEDCJ2c = b<em>E + (r</em>E * (x<em>{Dnumber} + 1)) + rac{(j</em>{sOP6} * r<em>E * r</em>D)}{bfr_{ED}}

    • This results in a cost of 24,500.

Overview of Query Optimization in Oracle

  • Oracle DBMS V8:

    • Rule-Based Query Optimization:

    • Heuristic-based execution plans without statistical examination (currently phasing out).

    • Cost-Based Query Optimization:

    • Includes evaluation of alternative accesses and operator algorithms to find a cost-effective execution plan based on resource usage (I/O, CPU, memory).

    • Application developers can suggest hints to the Oracle query optimizer, allowing for potentially better-informed decisions based on insights of specific datasets.