lOMoARcPSD|6916255
Query Optimization
Database Systems (University of Melbourne)
Scan to open on Studocu
Studocu is not sponsored or endorsed by any college or university
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
Query Plan 1
HOW DOES QUERY OPTIMIZATION WORK? 2
Query is first broken down into <blocks= 2
Each block is converted into relational algebra 2
Relational Algebra Equivalences 3
EQUIVALENCES INVOLVING JOINS 3
MIXING JOINS WITH SELECTIONS & PROJECTIONS 3
Plan with the lowest estimated cost is selected 4
COST ESTIMATION 5
Statistics and Catalogs 5
Result Size Estimation 5
Result Size Estimation Calculations 5
SINGLE TABLE SELECTION 6
CALCULATING REDUCTION FACTORS 6
There are many ways of executing a given query which gives the same result
However, cost of alternative methods often varies enormously
Query optimization aims to find the execution strategy with the lowest cost
Query Plan
● Basically a tree with relational algebra operators as the nodes and access path as the leaf nodes
● Each operator are labeled with a choice of algorithm
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
HOW DOES QUERY OPTIMIZATION WORK?
1. Query is first broken down into <blocks=
● Query block is any statement starting with SELECT
●
2. Each block is converted into relational algebra
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
3. Relational Algebra Equivalences
CASCADE specifies that when a referenced row is deleted, row(s) referencing it should be automatically
deleted as well.
EQUIVALENCES INVOLVING JOINS
These equivalences allows us to choose different join orders
MIXING JOINS WITH SELECTIONS & PROJECTIONS
Converting selection + cross-product => Join
SELECT + CROSS PRODUCT = JOIN
Selection on just attributes of S commutes with R join S (PUSH DOWN SELECTION)
SELECT a.age<18 FROM JOIN ON id
Second line is known as <push down= selection,
more efficient -> shrink down table and join -> less cost
PUSH DOWN PROJECTION (CAREFUL)
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
4. Plan with the lowest estimated cost is selected
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
COST ESTIMATION
FOR EACH PLAN in TREE
1. EstimateSizeOfResult(PlanTree)
a. Tree is a sequence of operations
i. Output of the previous operation is the input to subsequent operation
ii. Need to know size of output for the size of input of subsequent operation
2. EstimateCost(PlanTree)
a. Depends on input cardinalities
b. SequentialScan, IndexScan, Joins
c. Cost of entire plan
Statistics and Catalogs
● FindCost()
○ Optimizer needs information about relations and indexes related
○ FindInfo(SystemCatalogs) - information is stored in the system catalogs
● Catalogs - holds the information about the database and the data that it stores called as metadata
○ TUPLES: # tuples (NTUPLES) and # pages (NPAGES) per relation
○ # distinct key values (NKEYS) for each index (or relation attribute)
○ low/high key values (Low/High) for each index (or relation attribute)
○ Index height (Height(I)) for each tree index
○ # index pages (NPAGES(I)) for each index
● Statistics in catalogs are updated periodically
Result Size Estimation
Consider
SELECT AttributeList
FROM RelationList
WHERE predicate1 AND … predicate_k
● Maximum number of tuples in the result is the product of the cardinalities of relations in the FROM
clause
● REDUCTION FACTOR (RF) associated with each predicakes reflects the impact of the predicate in
reducing the result size. RF is also known as SELECTIVITY
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
lOMoARcPSD|6916255
INFO20003 Database Systems Relational Algebra
Result Size Estimation Calculations
SINGLE TABLE SELECTION
# Tuples * Product of all conditions
JOINS (OVER K TABLES)
If there are no selections (no predicates), reduction factors are ignored (==1).
CALCULATING REDUCTION FACTORS
EXAMPLE
Downloaded by Ramesh Prasad Bhatta (rpb.mcs@gmail.com)
