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:
For tuples:
Relationship:
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:
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:
Clustering index on S:
Primary index on S:
Hash key for join attributes - S.B:
Sort-Merge Join (J3)
The cost associated:
Cost for sorting files:
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:
Data for OP6 and OP7
Details provided in the following table:
Table_name|Num_rows|BlocksEmployee | 10,000 | 2,000
Department | 125 | 13
Table_name|Index_column|Unique|Index_typeEmployee | 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
Cost-Based Query Optimization (Example for OP6)
Method J1 with EMPLOYEE as the outer loop:
End cost is calculated as .
Method J2 with EMPLOYEE as the outer loop:
Since Dnumber in DEPARTMENT is the primary key:
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.