Copyright © 2007 Ramez Elmasri and Shamkant B.
Navathe
Chapter 15
Algorithms for Query Processing
and Optimization
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
Query Optimization
An internal representation of the query is created, usually as a
tree data structure called a query tree.
The DBMS must devise an execution strategy or query plan
for retrieving the results of the query from the database files.
A query typically has many possible execution strategies, and the
process of choosing a suitable one for processing a query is known
as query optimization.
Query optimization:
The process of choosing a suitable execution strategy for
processing a query.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 22
Query optimizer
The optimizer must limit the number of execution
strategies to be considered; otherwise, too much
time will be spent making cost estimates for the
many possible execution strategies.
24
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
Translating SQL Queries into Relational
Algebra
Query block:
The basic unit that can be translated into the
algebraic operators and optimized.
A query block contains a single SELECT-FROM-
WHERE expression, as well as GROUP BY and
HAVING clause if these are part of the block.
Nested queries within a query are identified as
separate query blocks.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 25
Translating SQL Queries into Relational
Algebra 2))
SELECT LNAME, FNAME
FROM EMPLOYEE
WHERE SALARY > ( SELECT MAX (SALARY)
FROM EMPLOYEE
WHERE DNO = 5);
SELECT LNAME, FNAME
SELECT MAX (SALARY)
FROM EMPLOYEE FROM EMPLOYEE
WHERE SALARY > C WHERE DNO=5
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 26
In general, a query tree gives a good visual
representation and understanding of the
query in terms of the relational operations
30
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
Example
Find the last names of employees born after 1957
who work on a project named ‘Aquarius’.
SELECT Lname
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE Pname=‘Aquarius’ AND Pnumber=Pno
AND Essn=Ssn AND Bdate > ‘31-12-1957’
32
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
1- Initial Query Tree
Read from bottom to up
Start with leafs
33
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
2- Improved Query Tree
An improved query tree that first applies the SELECT operations to
reduce the number of tuples that appear in the CARTESIAN
PRODUCT
34
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
3- Improved Query Tree
A further improvement is achieved by switching the positions of
the EMPLOYEE and PROJECT relations in the tree:
35
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
4- Improved Query Tree
We can further improve the query tree by replacing any CARTESIAN
PRODUCT operation that is followed by a join condition with a JOIN
operation:
36
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
5- Improved Query Tree
Another improvement is to keep only the attributes needed by
subsequent operations in the intermediate relations, by including
PROJECT (π) operations as early as possible in the query tree:
Copyright © 2007 Ramez Elmasri an d Shamkant B. Navathe
Rules
1. Break up any SELECT operations with conjunctive conditions into
a cascade of SELECT operations. This permits a greater degree of
freedom in moving SELECT operations down different branches of
the tree.
2. Move each SELECT operation as far down the query tree as is
permitted by the attributes involved in the select condition.
If the condition involves attributes from only one table, which
means that it represents a selection condition, the operation is
moved all the way to the leaf node that represents this table.
3. Rearrange the leaf nodes of the tree, position the leaf node
relations with the most restrictive SELECT operations so they are
executed first in the query tree representation. The definition of most
restrictive SELECT can mean either the ones that produce a
relation with the fewest tuples or with the smallest absolute size.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
4. Combine a CARTESIAN PRODUCT operation
with a subsequent SELECT operation in the tree
into a JOIN operation, if the condition
represents a join condition.
5. Break down and move lists of projection
attributes down the tree as far as possible by
creating new PROJECT operations as needed.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
