Chapter 2

Algorithms for Query Processing

and Optimization

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Chapter Outline (1)
0. Introduction to Query Processing
1. Translating SQL Queries into Relational Algebra
2. Algorithms for External Sorting
3. Algorithms for SELECT and JOIN Operations
4. Algorithms for PROJECT and SET Operations
5. Implementing Aggregate Operations and Outer Joins
6. Combining Operations using Pipelining
7. Using Heuristics in Query Optimization
8. Using Selectivity and Cost Estimates in Query
Optimization
9. Overview of Query Optimization in Oracle
10. Semantic Query Optimization

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 2

Introduction to Query Processing (2)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 3

1. Translating SQL Queries into Relational
Algebra (1)
■ 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- 4

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

πLNAME, FNAME (σSALARY>C(EMPLOYEE)) ℱMAX SALARY (σDNO=5 (EMPLOYEE))

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 5

2. Algorithms for External Sorting (1)
■ External sorting:
■ Refers to sorting algorithms that are suitable for large files
of records stored on disk that do not fit entirely in main
memory, such as most database files.
■ Sort-Merge strategy:
■ Starts by sorting small subfiles (runs) of the main file and
then merges the sorted runs, creating larger sorted subfiles
that are merged in turn.
■ Sorting phase: nR = ⎡(b/nB)⎤
■ Merging phase: dM = Min (nB-1, nR); nP = ⎡(logdM(nR))⎤
■ nR: number of initial runs; b: number of file blocks;
■ nB: available buffer space; dM: degree of merging;
■ nP: number of passes.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 6

3. Algorithms for SELECT and JOIN
Operations (1)
■ Implementing the SELECT Operation

■ Examples:
■ (OP1): σ SSN='123456789' (EMPLOYEE)
■ In (OP2): σ DNUMBER>5(DEPARTMENT)
■ (OP3): σ DNO=5(EMPLOYEE)
■ (OP4): σ DNO=5 AND SALARY>30000 AND SEX=F(EMPLOYEE)
■ (OP5): σ ESSN=123456789 AND PNO=10(WORKS_ON)
■ Where σ: The SELECT/RESTRICT operator
■ Combined conditions using AND, Or, Not
■ SQL SELECT * FROM EMPLOYEE WHERE
SSN='123456789';
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 7
Algorithms for SELECT and JOIN
Operations (2)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S1 Linear search (brute force):
■ Retrieve every record in the file, and test whether its attribute
values satisfy the selection condition.

■ S2 Binary search:
■ If the selection condition involves an equality comparison on a
key attribute on which the file is ordered, binary search (which
is more efficient than linear search) can be used. (See OP1).

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 8

Algorithms for SELECT and JOIN
Operations (2)
■ S3 Using a primary index or hash key to retrieve a
single record:
■ If the selection condition involves an equality comparison on a
key attribute with a primary index (or a hash key), use the
primary index (or the hash key) to retrieve the record.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 9

Algorithms for SELECT and JOIN
Operations (3)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S4 Using a primary index to retrieve multiple records:
■ If the comparison condition is >, ≥, <, or ≤ on a key field with a
primary index, use the index to find the record satisfying the
corresponding equality condition, then retrieve all subsequent records
in the (ordered) file. E.g book catalog

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 10

Algorithms for SELECT and JOIN
Operations (3)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S5 Using a clustering index to retrieve multiple records:
■ If the selection condition involves an equality comparison on a
non-key attribute with a clustering index, use the clustering index to
retrieve all the records satisfying the selection condition. Books by
authors

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 11

Algorithms for SELECT and JOIN
Operations (3)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S6 Using a secondary (B+-tree) index:
■ On an equality comparison, this search method can be used to
retrieve a single record if the indexing field has unique values (is a
key) or to retrieve multiple records if the indexing field is not a key.
■ In addition, it can be used to retrieve records on conditions involving
>,>=, <, or <=. (FOR RANGE QUERIES). Books about Database in
the library and bring them together

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 12

Algorithms for SELECT and JOIN
Operations (4)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S7 Conjunctive selection:
■ If an attribute involved in any single simple condition in the
conjunctive condition has an access path that permits the use
of one of the methods S2 to S6, use that condition to retrieve
the records and then check whether each retrieved record
satisfies the remaining simple conditions in the conjunctive
condition. When you have a query with
multiple AND conditions (e.g., department = 'Sales' AND
salary > 50000), use the single most efficient condition
first to narrow down the records.
■ S8 Conjunctive selection using a composite index
■ If two or more attributes are involved in equality conditions in
the conjunctive condition and a composite index (or hash
structure) exists on the combined field, we can use the index
directly.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 13
Algorithms for SELECT and JOIN
Operations (4)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection: composite index

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 14

Algorithms for SELECT and JOIN
Operations (4)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Simple Selection:
■ S8 Conjunctive selection using a composite index
■ If two or more attributes are involved in equality conditions in
the conjunctive condition and a composite index (or hash
structure) exists on the combined field, we can use the index
directly.
■ for example: When you have
multiple AND conditions with equals checks
(e.g., department = 'Sales' AND title = 'Manager')
and there's a combined index on both fields, use
that single index to find the records directly.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 15

Algorithms for SELECT and JOIN
Operations (5)
■ Implementing the SELECT Operation (contd.):
■ Search Methods for Complex Selection:
■ S9 Conjunctive selection by intersection of record pointers:
■ This method is possible if secondary indexes are available on all (or some of)
the fields involved in equality comparison conditions in the conjunctive
condition and if the indexes include record pointers (rather than block
pointers).
■ Each index can be used to retrieve the record pointers that satisfy the
individual condition.
■ The intersection of these sets of record pointers gives the record pointers that
satisfy the conjunctive condition, which are then used to retrieve those records
directly.
■ If only some of the conditions have secondary indexes, each retrieved record
is further tested to determine whether it satisfies the remaining conditions.
■ Example:
Query: department = 'Sales' AND title = 'Manager'
■ Index on department returns: [Record5, Record8, Record11]
■ Index on title returns: [Record8, Record11, Record15]
■ Intersection: [Record8, Record11]
■ Only records #8 and #11 are retrieved from disk
■

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 16

Algorithms for SELECT and JOIN
Operations (7)
■ Implementing the SELECT Operation (contd.):
■ Whenever a single condition specifies the selection, we
can only check whether an access path exists on the
attribute involved in that condition.
■ If an access path exists, the method corresponding to that
access path is used; otherwise, the “brute force” linear search
approach of method S1 is used. (See OP1, OP2 and OP3)
■ For conjunctive selection conditions, whenever more
than one of the attributes involved in the conditions have an
access path, query optimization should be done to choose
the access path that retrieves the fewest records in the most
efficient way.
■ Disjunctive Selection Conditions are database queries where
records must satisfy at least one of multiple conditions,
connected by the OR operator.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 17

Algorithms for SELECT and JOIN
Operations (8)

■ Implementing the JOIN Operation: A Join combines

rows from two or more tables based on a related column
between them
■ Join (EQUIJOIN, NATURAL JOIN)
■ two–way join: a join on two files
■ e.g. R A=B S Equijoin (the value column A=B)
■ Join table R and table S
■ multi-way joins: joins involving more than two files.
■ e.g. R A=B S C=D T
■ Examples
■ (OP6): EMPLOYEE DNO=DNUMBER DEPARTMENT
■ (OP7): DEPARTMENT MGRSSN=SSN EMPLOYEE
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 18
Algorithms for SELECT and JOIN
Operations (8)
■ Employees (Table R): (employee_id, name, department_id)
■ Departments (Table S): (department_id, department_name)
SELECT * FROM Employees JOIN Departments
ON Employees.department_id = Departments.department_id;
■ Projects (Table T): (project_id, project_name,
department_id)
SELECT * FROM Employees JOIN Departments ON
Employees.department_id = Departments.department_id
JOIN Projects ON Departments.department_id =
Projects.department_id;

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 19

Algorithms for SELECT and JOIN
Operations (9)
■ Implementing the JOIN Operation (contd.):
■ Methods for implementing joins:
■ J1 Nested-loop join (brute force):
■ For each record t in R (outer loop), retrieve every record s
from S (inner loop) and test whether the two records satisfy
the join condition t[A] = s[B]. Check the entire table, high cost.
■ J2 Single-loop join (Using an access structure to retrieve
the matching records):
■ If an index (or hash key) exists for one of the two join attributes
— say, B of S — retrieve each record t in R, one at a time, and
then use the access structure to retrieve directly all matching
records s from S that satisfy s[B] = t[A]. Lower cost. Take one
a time

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 20

Algorithms for SELECT and JOIN
Operations (10)
■ Implementing the JOIN Operation (contd.):
■ Methods for implementing joins:
■ J3 Sort-merge join:
■ If the records of R and S are physically sorted (ordered) by
value of the join attributes A and B, respectively, we can
implement the join in the most efficient way possible.
■ Both files are scanned in order of the join attributes, matching
the records that have the same values for A and B.
■ In this method, the records of each file are scanned only once
each for matching with the other file—unless both A and B are
non-key attributes, in which case the method needs to be
modified slightly.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 21

Algorithms for SELECT and JOIN
Operations (10)
■ How it works:
■ Sort Phase: Sort table R by column A and table S by column B
■ Merge Phase:
■ Scan both sorted tables simultaneously
■ Compare the current A value from R with the current B value from
S
■ When they match, output the joined pair and handle all matching
records
■ Example:
Join Employees and Departments on dept_id:
■ Sort Employees by dept_id: [10, 20, 20, 30]
■ Sort Departments by dept_id: [10, 20, 30, 40]
■ Merge scan matches: 10-10, 20-20, 20-20, 30-30

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 22

Algorithms for SELECT and JOIN
Operations (11)
■ Implementing the JOIN Operation (contd.):
■ Methods for implementing joins:
■ J4 Hash-join:

■ The records of files R and S are both hashed to the same

hash file, using the same hashing function on the join
attributes A of R and B of S as hash keys.
■ A single pass through the file with fewer records (say, R)
hashes its records to the hash file buckets.
■ A single pass through the other file (S) then hashes each of its
records to the appropriate bucket, where the record is
combined with all matching records from R. example
■ Hash Function: Count the number of letters in the book's title, then use the last digit.
■ "The Cat in the Hat" → 18 letters → Hash = 8 → Place on shelf #8.
■ "War and Peace" → 12 letters → Hash = 2 → Place on shelf #2.
■ "Dune" → 4 letters → Hash = 4 → Place on shelf #4

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 23

Algorithms for SELECT and JOIN
Operations (14)

■ Implementing the JOIN Operation (contd.):

■ Factors affecting JOIN performance
■ Available buffer space
■ Join selection factor
■ Choice of inner VS outer relation

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 24

Algorithms for SELECT and JOIN
Operations (15)
■ Implementing the JOIN Operation (contd.):
■ Other types of JOIN algorithms
■ Partition hash join
■ Partitioning phase:
■ Each file (R and S) is first partitioned into M partitions using a
partitioning hash function on the join attributes:
■ R1 , R2 , R3 , ...... Rm and S1 , S2 , S3 , ...... Sm
■ Minimum number of in-memory buffers needed for the
partitioning phase: M+1. Because we need one buffere to read
original relation.
■ A disk sub-file is created per partition to store the tuples for
that partition.
■ Joining or probing phase:
■ Involves M iterations, one per partitioned file.
■ Iteration i involves joining partitions Ri and Si.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 25

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

■ Partitioned Hash Join Procedure:
■ Assume Ri is smaller than Si.
1. Copy records from Ri into memory buffers.
2. Read all blocks from Si, one at a time and each
record from Si is used to probe for a matching
record(s) from partition Si.
3. Write matching record from Ri after joining to the
record from Si into the result file.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 26

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 27

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 28

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 29

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 30

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 31

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 32

Algorithms for SELECT and JOIN
Operations (16)

■ Implementing the JOIN Operation (contd.):

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 33

SELECT and PROJECT Operations to remove
duplication

■ 1. Sorting
■ How it works:
■ Perform the initial projection to get the data with
potential duplicates.
■ Sort the entire result set based on all the projected
attributes.
■ Scan the sorted list. Identical tuples will be
adjacent to each other.
■ As you scan, you only keep the first occurrence of
each unique tuple and discard the subsequent
duplicates.
Copyright .
1. © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 34
SELECT and PROJECT Operations to remove
duplication

1. .

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 35

SELECT and PROJECT Operations to
remove duplication
■ 2. Hashing
■ How it works:
■ Use a hash function on all the projected attributes of a tuple to
calculate a "hash value" (a kind of numerical signature).
■ Tuples with the same values will produce the same hash value
and are placed into the same "bucket."
■ Within each bucket, a second, finer check is done to identify and
eliminate exact duplicates.
■ The final result is the set of unique tuples collected from all
buckets.
■ Analogy: Like putting people into rooms based on their birth month.
You then only need to check for duplicates within each room, which is
a smaller, more manageable task.
■ .

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 36

SELECT and PROJECT Operations to
remove duplication

Hashing based organization

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 37

SELECT and PROJECT Operations to
remove duplication

■ Projection
■ 1. Extract tuples with the specified attributes.
2. Remove duplicates using Sorting or Hashing.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 38

Algorithms for SELECT and JOIN
Operations (17)
■ Implementing the JOIN Operation (contd.):
■ Cost analysis of partition hash join:
1. Reading and writing each record from R and S during the
partitioning phase: b use the block
(bR + bS), (bR + bS)
2. Reading each record during the joining phase:
(bR + bS)
3. Writing the result of join:
bRESULT
■ Total Cost:
■ 3* (bR + bS) + bRESULT

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 39

 SELECT and PROJECT
Operations

(a) σ(DNO=4 AND SALARY>25000) OR (DNO=5 AND

SALARY>30000)
(EMPLOYEE)
(b) πLNAME, FNAME, SALARY(EMPLOYEE)
(c) πSEX, SALARY(EMPLOYEE)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Relational Algebra Operations from
Set Theory
■ The UNION, INTERSECTION, and MINUS
Operations
■ The CARTESIAN PRODUCT (or CROSS
PRODUCT) Operation

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Set Operators
■ A relation is a set of tuples, so set
operations apply:
∩, ∪, − (set difference)
■ Result of combining two relations with a set
operator is a relation => all elements are
tuples with the same structure

42

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 UNION Operation

Denoted by R ∪ S
Result is a relation that includes all tuples that are
either in R or in S or in both. Duplicate tuples are
eliminated.
Example: Retrieve the SSNs of all employees who
either work in department 5 or directly supervise an
employee who works in department 5:
DEP5_EMPS ← σDNO=5 (EMPLOYEE)
RESULT1 ← π SSN(DEP5_EMPS)
RESULT2(SSN) ← π SUPERSSN(DEP5_EMPS)
RESULT ← RESULT1 ∪ RESULT2
The union operation produces the tuples that are in
either RESULT1 or RESULT2 or both. The two
operands must be “type compatible”. 43

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Example

Tables:
Person (SSN, Name, Address, Hobby)
Professor (Id, Name, Office, Phone)

π Name (Person) and π Name (Professor)

are union compatible so
π Name (Person) - π Name (Professor)
makes sense.
44

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 UNION Example

STUDENT ∪ INSTRUCTOR:

What would STUDENT ∩ INSTRUCTOR be?

45

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Set Difference Operation

Set Difference (or MINUS) Operation

The result of this operation, denoted by R - S,
is a relation that includes all tuples that are in
R but not in S. The two operands must be
"type compatible”.

46

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Set Difference Example
S1 S2
SID SName Age SID SName Age
473 Popeye 22 202 Rusty 21
192 Jose 22 403 Marcia 20
715 Alicia 28 914 Hal 24
914 Hal 24 192 Jose 22
881 Stimpy 19
47

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Set Difference Operation

▪ What is set difference of S1 and S2

(S1-S2)
▪

48

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Relational Algebra Operations
From Set Theory (cont.)
■ Union and intersection are commutative operations:
R ∪ S = S ∪ R, and R ∩ S = S ∩ R

■ Both union and intersection can be treated as n-ary

operations applicable to any number of relations as
both are associative operations; that is
R ∪ (S ∪ T) = (R ∪ S) ∪ T, and
(R ∩ S) ∩ T = R ∩ (S ∩ T)

■ The minus operation is not commutative; that is, in

general
R-S≠S–R 49

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Cartesian (Cross) Product
■ If R and S are two relations, R × S is the set of all
concatenated tuples <x,y>, where x is a tuple in R
and y is a tuple in S
■ R and S need not be union compatible
■ R × S is expensive to compute:
■ Factor of two in the size of each row; Quadratic in the
number of rows

50

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Cartesian Product Example
■ How the cartesian product works?
■ Take the first row from the first table.
■ Pair it with every single row from the second table.
■ Repeat this for every row in the first table.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Cartesian (Cross) Product
■ Examples of Cartesian product of the following table

A B C D A B C
D
x1 x2 y1 y2 x1 x2 y1
y2
x3 x4 y3 y4 x1 x2 y3
y4
x3 x4 y1
y2
R S x3 x4
52
y3 y4
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe
 Cartesian Product Example
■ Cartesian product examples

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Cartesian Product Example
■ The SQL CROSS JOIN produces a result set
which is the number of rows in the first table
multiplied by the number of rows in the second
table if no WHERE clause is used along with
CROSS JOIN. This kind of result is called as
Cartesian Product.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Implementing Aggregate Operations and
Outer Joins
■ Implementing Aggregate Operations (contd.):
■ SUM, COUNT and AVG
■ For a dense index (each record has one index entry):
■ Apply the associated computation to the values in the index.
■ Content: "Apply the associated computation to the values in the index."
■ Explanation: If we have a dense index on Amount, the database can
compute aggregates by scanning just the index without touching the
actual table data.
■ Example:
■ Index on Amount: [100→101, 150→103, 200→102, 250→105,
300→104]
■ SUM(Amount): Scan index: 100 + 150 + 200 + 250 + 300 = 1000
■ COUNT(*): Count index entries = 5
■ AVG(Amount): 1000 ÷ 5 = 200
■ Benefit: Much faster than scanning the entire table!

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 55

Implementing Aggregate Operations and
Outer Joins
■ Implementing Aggregate Operations (contd.):
| OrderID | Product | Amount |
|--------- |--------- |--------|
| 101 |A | 100 |
| 103 |A | 150 |
| 102 |B | 200 |
| 105 |B | 250 |
| 104 |C | 300 |

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 56

Implementing Aggregate Operations and
Outer Joins
■ For a non-dense index:
■ number of records associated with each index entry
must be accounted for
■ Explanation: With sparse indexes, each index entry represents multiple
records, so we need to track counts.
■ Example:
■ Non-dense index on Amount (one entry per block):
■ Block 1: 100→[101,103] (2 records)
■ Block 2: 200→[102,105] (2 records)
■ Block 3: 300→[104] (1 record)
■ SUM(Amount): (100 × 2) + (200 × 2) + (300 × 1) = 900 ❌ WRONG!
■ Problem: We can't multiply like this because amounts vary within blocks
■ Solution: Must check actual records or use different approach

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 57

Implementing Aggregate Operations and
Outer Joins
■ With GROUP BY: the aggregate operator must be applied
separately to each group of tuples.
■ Use sorting or hashing on the group attributes to
partition the file into the appropriate groups;
■ Computes the aggregate function for the tuples in each
group.
■ Example: SELECT Product, SUM(Amount) FROM Sales GROUP BY
Product
Method 1: Sorting
■ Sort by Product: [A, A, B, B, C]
■ Group and compute:
■ Group A: 100 + 150 = 250
■ Group B: 200 + 250 = 450
■ Group C: 300

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 58

Implementing Aggregate Operations and
Outer Joins

■ Method 2: Hashing
■ Hash Product to different buckets:
■ Bucket 1 (A): [100, 150]
■ Bucket 2 (B): [200, 250]
■ Bucket 3 (C): [300]
■ Compute aggregates per bucket
■ What if we have Clustering index on the grouping attributes?

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 59

Implementing Aggregate Operations and
Outer Joins
■ What if we have Clustering index on the grouping attributes?
■ Explanation: This is the optimal scenario for GROUP
BY operations!
■ Clustering Index means the physical data is sorted by
the indexed column.
■ Example: If we have a clustering index on Product, the
data is physically stored as: a table we use before

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 60

Implementing Aggregate Operations and
Outer Joins
■ What if we have Clustering index on the grouping attributes?
■ Benefits of Clustering index
■ No sorting needed - data is already grouped by Product
■ No hashing needed - groups are physically contiguous
■ Direct computation - simply scan through the pre-grouped
data
■ Process:
■ Start with Product A records: SUM = 100 + 150 = 250
■ Move to Product B records: SUM = 200 + 250 = 450
■ Move to Product C records: SUM = 300

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 61

Implementing Aggregate Operations and
Outer Joins

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 62

7. Using Heuristics in Query
Optimization(1)
■ Heuristics in query optimization are rules of
thumb or guidelines that help the database optimizer choose a good
execution plan without exhaustively checking all possibilities.
■ Heuristic optimization transforms the query-tree by using
a set of rules that typically improve execution
performance. These rules are
1. Perform selection early (reduces the number of tuples)
2. Perform projection early (reduces the number of attributes)
3. Perform most restrictive selection and join operations before
other similar operations (such as cartesian product).

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 63

7. Using Heuristics in Query
Optimization(1)

■ Process for heuristics optimization

Steps in Heuristic Estimation
Step 1: Scanner and parser generate initial query representation
Step 2: Representation is optimized according to heuristic rules
Step 3: Query execution plan is developed
■ For example: Suppose there are two relational algebra -
(1) σcity= "Pune" (Tcname Branch) Account Customer)
(2) Πcname(σcity="Pune (Branch Account Customer))
The query evaluation plan can be drawn using the query trees as follows
■ Some systems use only heuristics, others combine heuristics with
partial cost-based optimization.
E.g., Apply SELECT and PROJECT operations before applying the JOIN or
■
other binary operations.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 64

7. Using Heuristics in Query
Optimization(1)

■ Heuristic Optimization Rules Order

■ Early Operations (Highest Priority)
■ Push Selections Down - σ early
■ Push Projections Down - π early
■ Apply Most Restrictive Operations First

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 65

Using Heuristics in Query Optimization (2)
■ Query tree:
■ A tree data structure that corresponds to a relational algebra
expression. It represents the input relations of the query as
leaf nodes of the tree, and represents the relational algebra
operations as internal nodes.
■ An execution of the query tree consists of executing an
internal node operation whenever its operands are
available and then replacing that internal node by the
relation that results from executing the operation.
■ Query graph:
■ A graph data structure that corresponds to a relational
calculus expression. It does not indicate an order on which
operations to perform first. There is only a single graph
corresponding to each query.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 66

 7. Using Heuristics in Query
Optimization(1)
■ Out of the above given query evaluation plans, the Fig. (b) is much
faster than Fig. (a) because - in Fig. (a) the join operation is among
Branch, Account and Customer, whereas in Fig. (b) the join of
(Account and Customer) is made with the selected tuple for
City="Pune".
■ Thus the output of entire table for join operation is much more than the
join for some selected tuples.
■ Thus we get choose the optimized query.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 67

Using Heuristics in Query Optimization (3)
■ Example:
■ For every project located in ‘Stafford’, retrieve the project number,
the controlling department number and the department manager’s
last name, address and birthdate.
■ Relation algebra:
πPNUMBER, DNUM, LNAME, ADDRESS, BDATE
(((σPLOCATION=‘STAFFORD’(PROJECT))
DNUM=DNUMBER
(DEPARTMENT)) MGRSSN=SSN
(EMPLOYEE))

■ SQL query:
Q2: SELECT [Link],[Link],[Link],
[Link], [Link]
FROM PROJECT AS P,DEPARTMENT AS D,
EMPLOYEE AS E
WHERE [Link]=[Link] AND
[Link]=[Link] AND
[Link]=‘STAFFORD’;

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 68

Using Heuristics in Query Optimization (4)

Figure (a) represents the

optimized query tree — the
relational algebra expression
is decomposed and
reordered to improve query
performance.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 69

Using Heuristics in Query Optimization (2)
■ Reading the Tree (Bottom-Up):
■ Leaf Nodes (Bottom):
■ PROJECT, DEPARTMENT, EMPLOYEE - The three base tables
■ Internal Nodes (Operations):
(1) σ [Link]='Stafford' - Select only Stafford projects
(2) ⨝ [Link] = [Link] - Join Stafford projects with their
departments
(3) ⨝ [Link] = [Link] - Join the result with employees who are
managers
■ Root Node (Top):
■ π (Projection) - Keep only the specified columns in the final output

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 70

Using Heuristics in Query Optimization (5)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 71

Using Heuristics in Query Optimization (2)
Components of the Graph:
1. Relation Nodes (Circles):
▪ P: PROJECT relation
▪ D: DEPARTMENT relation
▪ E: EMPLOYEE relation
2. Constant Node (Double Circle):
'Stafford': The constant value we're searching for
3. Edges (Connection Lines):
▪ [Link] = [Link]: Join condition between PROJECT and DEPARTMENT
▪ D.Mgr_ssn = [Link]: Join condition between DEPARTMENT and EMPLOYEE
▪ [Link] = 'Stafford': Selection condition linking PROJECT to the constant
4. Result Attributes (Displayed Above):
From P: [[Link], [Link]] - Project number and department number
From E: [[Link], [Link], [Link]] - Manager's last name, address, and
birthdate

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 72

Using Heuristics in Query Optimization (6)
■ Heuristic Optimization of Query Trees:
■ The same query could correspond to many different
relational algebra expressions — and hence many different
query trees.
■ The task of heuristic optimization of query trees is to find a
final query tree that is efficient to execute.
■ Example:
Q: SELECT LNAME
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE PNAME = ‘AQUARIUS’ AND
PNMUBER=PNO AND ESSN=SSN AND
BDATE > ‘1957-12-31’;

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 73

Using Heuristics in Query Optimization (7)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 74

Using Heuristics in Query Optimization (6)

(a) Initial (Canonical) Query Tree

■Problem: This is the naive, inefficient starting point
■Cartesian Product of all 3 tables first (creates huge
intermediate result)
■Single SELECT with all conditions applied together

■No optimization - follows SQL syntax literally

■Execution:

■ EMPLOYEE * WORKS_ON * PROJECT (Massive Cartesian

product!)
■ σ Apply ALL conditions at once
■ π Project only Lname

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 75

Using Heuristics in Query Optimization (6)
(b) Moving SELECT Operations Down
■Improvement: Push filters closer to the data sources

■ σ Pname='Aquarius' pushed down to PROJECT table

■ σ Bdate>'1957-12-31' pushed down to EMPLOYEE table
■Reduces the size of intermediate results before joining
■Execution:

■ Filter PROJECTs → only 'Aquarius' projects

■ Filter EMPLOYEEs → only those born after 1957
■ Join the pre-filtered results

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 76

Using Heuristics in Query Optimization (6)

(c) Applying More Restrictive SELECT First

■Further Improvement: Reorder operations for
maximum efficiency
■Most restrictive filter first:

■ Pname='Aquarius' (likely few 'Aquarius' projects)

■ Then join with WORKS_ON to find who works on
these projects
■ Finally join with filtered EMPLOYEEs
Key Insight: Start with the smallest possible
■
dataset and build up.
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 77
Using Selectivity and Cost Estimates in
Query Optimization (2)

■ Cost Components for Query Execution

1. Access cost to secondary storage
2. Storage cost
3. Computation cost
4. Memory usage cost
5. Communication cost

■ Note: Different database systems may focus on

different cost components.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 15- 78