QUERY OPTIMIZATION

QUERY TREE
QUERY TREE
What is a query Tree?
• A query tree is a tree data structure representing a relational algebra expression.
• The tables/relations of the query are represented as leaf nodes.
• The relational algebra operations are represented as the internal nodes.
• The root represents the query as a whole.
• Root node is executed last, and is replaced by the result of the entire tree
• During execution, an internal node is executed whenever its operand tables are
available.
• The node is then replaced by the result table. This process continues for all
internal nodes until the root node is executed and replaced by the result table.
• canonical query tree 
Query Tree Example
SELECT Name FROM Student WHERE Major='CS'

Name

Major='CS'

Student

Page 4
Query Tree Example 2
SELECT DeptName FROM Department, Student
WHERE Code = Major AND Year = 4

 DeptName

Code=Major AND Year = 4


Student Department

Page 18
 Query Tree Example 3 sname

SELECT S.sname bid=100 rating > 5

FROM Reserves R, Sailors S
WHERE R.sid=S.sid AND RA Tree:
R.bid=100 AND S.rating>5
sid=sid

Reserves Sailors

Sailors))
sname (σbid=100rating>5 (Reserves sid=sid

8
Optimization of query tree
SELECT DISTINCT Dname
FROM Em , Dept
WHERE Em. dept_n = Dept . dept_n AND Salary > 1000 ;
• The first transformation is done separating the two conditions of
selection:
• The second transformation change the cartesian product in a join
operation:
P=Em. dept_n = Dept . dept_n
• The third transformation is anticipate selection:
 Query Tree Example 3 sname

SELECT S.sname bid=100 rating > 5

FROM Reserves R, Sailors S
WHERE R.sid=S.sid AND RA Tree:
R.bid=100 AND S.rating>5
sid=sid

Reserves Sailors

Sailors))
sname (σbid=100rating>5 (Reserves sid=sid

8
Alternative Plan 1 (Selection Pushed
Down)
• Push selections below the join.
sname

sid=sid

bid=100 rating > 5

Reserves Sailors
 Alternative Plan 2
• Selection sname

rating > 5

sid=sid

Sailors
bid=100

Reserves

 Push rating>5 before the join? Need to use search arguments More on this
later…
 COSC 404 - Dr. Ramon Lawrence

Rules of Optimization using query tree

1.Deconstruct conjunctive selections into a sequence of single
selection operations.
2.Move selection operations down the query tree for the
earliest possible execution.
3.Replace Cartesian product operations that are followed by a
selection condition by join operations.
4.Execute first selection and join operations that will produce
the smallest relations.
5.Deconstruct and move as far down the tree as possible lists
of projection attributes, creating new projections where needed.

Page 15
Example
• An SQL query:
SELECT ENAME
FROM EMPLOYEE, WORKSON, PROJECT
WHERE PNAME = ‘database’ AND
PNUM = PNO AND ENO = ENUM AND BDATE > ‘1965’
 ENAME

PNUM = PNO
• Apply SELECT
first
• Optimized 1
ENUM = ENO PNAME = ‘d a ta ba se ’

PROJECT

BDATE > ‘1965’ WORKSON

EMPLOYEE
Example: Replace “σ − ×” by “join”

ENAME
PNUM = PNO

ENUM = ENO PNAME = ‘da ta b a se ’

BDATE > ‘1965’ WORKSON

PROJECT

EMPLOYEE
 ENAME

PNUM = PNO
• Move Projection
Down

ENAME, PNO PNUM

ENUM = ENO PNAME = ‘d a ta ba se ’

ENO, PRO JEC T

ENAME, ENUM PNO

WO RKSO N
BDATE > ‘1965’

EMPLO YEE
Construct equivalent query tree and optimize

• SELECT * • SELECT Country

FROM Product FROM Product, Company
WHERE category=‘Gadgets WHERE Manufacturer=CName
• SELECT PName, Price, AND Category=‘Gadgets’
Manufacturer • SELECT PName, Price
FROM Product FROM Product, Company
WHERE Price > 100 WHERE Manufacturer=CName
•  AND Country=‘Japan’
AND Price <= 200