L15:Query Optimization(2019)

Question 1

Evaluation Plan

Answer 1

An Evaluation Plan

defines what algorithm is used for each operation,

and how execution of these operations is coordinated.

• There can be equivalent plans for a single query
• Represented as a Tree of Operations on relations
  
  • Tree uses relational algebra symbols as nodes

Question 2

Cost-Based

Query Optimization

Steps (3)

Answer 2

1. Generate logically equivalent expressions using equivalence rules
2. Annotate resultant expressions to get alternative query plans
3. Choose the cheapest plan based on estimated cost

Question 3

Query Costs:

Factors

Answer 3

There are multiple statistics on a DBMS:

• Statistical information about relations
• Statistical Estimation for Intermediate Results
• Cost of Algorithms, using the above statistics

Question 4

Equivalence of

Relational Algebra Statements

Answer 4

Two RA statements are said to be Equivalent IF:

They produce the same tuples on every database instance.

• If the statements are equivalent, we can use them interchangably
• Equivalence can be quickly determined through the equivalence rules

Question 5

Relational Algebra Equivalence Rules:

Set of Rules

Answer 5

• Conjunctive Selections
• Commutative Selection Operations
• Series of Projections
• Selections combined with Theta Join or Cartesian Product
• Join Commutative Property
• Natural Join Associativity
• Theta Join Conditioin Associativity
• Set Union
• Set Intersection

Question 6

Relational Algebra Equivalence Rules:

3 Most Useful Join Rules

Answer 6

• Join Commutativity
• Natural Join Associativity
• Theta Join Associativity

Question 7

Cost Estimation:

Basics

Answer 7

Goal:

Compare an execution plan’s cost,

not exactly measure computation time.

*More of an art, not exact.

Variables and Symbols:

• S - a relation
• B(S) - Blocks of S
• T(S) - Tuples in S
• V(S, a) - number of distinct values of a in relation S

Question 8

General

Query Optimization

Rules

Answer 8

• Push Selection** and **Projection operations as far as possible down the tree
• Put Joins on the left
  
  • Allows pipelining without using intermediate files
• Avoid Cartesian Products
  
  • If they cannot be avoided, delay as long as possible
    
    • Push UP the tree
    • Performed on smaller relations

Question 9

Cost Estimation:

Selection:

Cost of Scanning Disk with Index,

• Clustered
• Unclustered

Answer 9

If indexed over an attribute, use a function F(R,a) to determine how many Input/Output operations required.

The Value of F(R,a) depends on the condition in the selection

Costs:

If Data is clustered:

Cost = F(R,a) * B(R)

(Reading Blocks at a time)

Unclustered:

Cost = F(R,a) * T(R)

(Reading Tuples at a time)

B(R) = Blocks in the relation

T(R) = Tuples in the relation

Question 10

Cost Estimation:

Selection:

Cost of Scanning Disk without Index

Answer 10

Cost = B(R) + Seek Time

B(R) = Blocks in the relation

Question 11

Cost Estimation:

Selection Cost Function, F(R,a):

Functions for common predicates

Answer 11

The Cost Function used depends on the Condition(Predicate) in the Selection Operation

Equals : σ_a=v(R)

F(R,a) = 1 / V(R,a)

V(R, a) = number of distinct values in R

Less than : σ_a<v>(R)</v>

F(R,a) = (v - min(a) ) /

( max(a)-min(a) )

Range : σ_{x<a><span>(R)</span></a>}

F(R,a) = (v - x ) /

( max(a)-min(a) )

Question 12

Cost Estimation:

Selection Cost Function, F(R,a):

Equals Predicate :

σ_a=v(R)

Answer 12

F(R,a) = 1 / V(R,a)

V(R, a) = number of distinct values in R

Question 13

Cost Estimation:

Selection Cost Function, F(R,a):

Less than predicate:

σ_a<v>(R)</v>

Answer 13

σ_a<v>(R)</v>

F(R,a) = (v - min(a) ) /

( max(a)-min(a) )

Question 14

Cost Estimation:

Selection Cost Function, F(R,a):

Range Predicate:

σ_{x<a><span>(R)</span></a>}

Answer 14

σ_{x<a><span>(R)</span></a>}

F(R,a) =

(v - x ) / ( max(a)-min(a) )

Question 15

Cost Estimation:

Joins

Answer 15

• Assumption: Containment of Values
  
  • If V(S,a) <= V(R,a) , then A values in S is a subset of A values in R
  • Less Tuples in S, R contains all those tuples
• With this assumption, say that each tuple “t” joins with “x” tuples in R
  
  • x = T(R) / V(R,a)
• Therefore:
  
  • T(S join_a R) = T(S) * T(R) / V(R,a)
• Consider the cost of joins as simply the NUMBER of TUPLES OUTPUT, for simplicity

Question 16

Optimizers:

Enumerating Equivalences

Answer 16

Optimizers use Equivalence Rules to systematically generate Equivalent Expressions

Process

• Repeat until no new expressions are found
• Apply all applicable equivalence rules to every subexpression of every equivalent expression found so far
• Add newly generated expressions to set of Equivalent Expressions

This process is extremely expensive, optimized with:

• Optimized generation based on some rules
• Special Cases for queries with only Selection, Projection and/or Joins

Question 17

Equivalence Rules:

Conjunctive Selections

Answer 17

Conjunctive Selections are

Selection Operations with Multiple Conditions:

σ_{θ1 ^ θ2} (R)

Is equivalent to a

Sequence of Individual Selections

σ_θ1 ( σ_θ2 (R) )

Question 18

Equivalence Rules:

Commutative Selection Operations

Answer 18

Selection Operations are Commutative:

The Selections can be performed in any order to get the same result:

σθ₁ ( σθ₂ (R) )

=

σθ₂ ( σθ₁ (R) )

Question 19

Equivalence Rules:

Series of Projections

Answer 19

Within a series of Projections,

only the LAST Projection is needed.

All earlier Projections can be omitted:

πθ_n ( πθn-1 (…( πθ₁ (R)…))

=

πθ₁ (R)

Question 20

Equivalence Rules:

Combining Selection with

Cartesian Product

Answer 20

Performing a Selection after a Cartesian Product is equivalent to a Theta Join with the same condition:

σθ (R1 X R2)

=

R1 ⋈θ R2

Question 21

Equivalence Rules:

Join Commutative Property

Answer 21

Both Theta Joins and Natural Joins are Commutative:

The joins can be performed in any order

R1 ⋈θ R2

=

R2 ⋈θ R1

Question 22

Equivalence Rules:

Natural Join Associativity

Answer 22

Natural Joins are Associative:

Can be optimized by performing the SMALLER join first

R1 ⋈ (R2 ⋈ R3)

=

(R1 ⋈ R2 ) ⋈ R3

Question 23

Equivalence Rules:

Theta Join Associativity

-Special Case

Answer 23

Theta Joins are associative in the following case:

(R1 ⋈θ₁ R2 ) ⋈θ₂^θ₃ R3

Where the second condition, θ₂ , ONLY involves attributes from R₂ and R₃

=

R1⋈θ₁^θ₃ (R2 ⋈θ₂ R3 )

Question 24

Equivalence Rules:

Set Union

Set Intersection

Answer 24

Both operations are Commutative:

E₁ ∪ E₂ = E₂ ∪ E₁

E₁ ∩ E₂ = E₂ ∩ E₁

Both operations are Associative:

(E₁∪E₂)∪E₃ = E₂∪(E₁ ∪ E₃)

(E₁∩E₂)∩E₃ = E₂∩(E₁ ∩ E₃)

Question 25

Equivalence Rules:

Selection and Set Union/Intersection/Difference

Answer 25

In Set Union, Intersection and Difference operations,

A Selection Operation is Distributive:

σθ (E1 - E2)

=

σθ(E1 - σθ(E2)

Question 26

Query Optimization:

Basic RA Commutators

(Operations on Tree)

Answer 26

• Can “push” Projections through:
  
  • Selection
  • Join
• Push Selection through:
  
  • Selection
  • Projection
  • Join
• Joins can be re-ordered