Database Management System (DBMS)

Web Embedded Interactive

Applications Forms SQL SQL

SQL Commands
DBMS
Query
Evaluation Engine

Files and Access Methods

Concurrency Recovery
Control Buffer Manager Manager
Disk Space Manager

Database Data Indexes Catalog

1
Steps in Processing a Query
SQL statement

Scan, Parse, Validate

Intermediate form of query

Query
Query Optimizer
Optimizer
Execution plan

Query Code Generator

Code to execute query

Runtime DB Processor

Results of running query

2
Conceptual Evaluation Strategy

 Semantics of an SQL query defined in terms of

the following conceptual evaluation strategy:

1. Compute the cross-product of from-list

2. Discard resulting tuples that fail qualifications
3. Delete attributes that are not in select-list
4. If DISTINCT is specified, eliminate duplicate
rows

3
Example of Conceptual Evaluation
SELECT [Link]
FROM Sailors S, Reserves R
WHERE [Link]=[Link] AND [Link]=103

[Link] SName Rating Age [Link] BID Day

22 Dustin 7 45 22 101 10/10/96
22 Dustin 7 45 58 103 11/12/96
31 Lubber 8 55 22 101 10/10/96
31 Lubber 8 55 58 103 11/12/96
58 Rusty 10 35 22 101 10/10/96
58 Rusty 10 35 58 103 11/12/96

4
Conceptual Evaluation Strategy
 This strategy is probably the least efficient
way to compute a query!

 An “optimizer” will find more efficient

strategies to compute the same answers

5
Query Optimization Overview
Query Optimization Overview Cont.

 Optimizing a query involves two basic steps:

1. Generating alternative plans: only a subset of

all possible plans is considered (Why?)
2. Estimating the cost of each generated plan and
choosing the plan with the lowest estimated
cost
Intermediate Query Form
 An SQL query is translated into equivalent:

Relational Algebra Expression

 Represented as a:

Query Tree

8
Relational Algebra

 Relational algebra

 Basic set of operations for the relational model

 Relational algebra expression

 Sequence of relational algebra operations

 SQL is based on concepts from relational algebra

9
 Relational Algebra - Example
SELECT name, rating name,rating( Rating > 8(S))
FROM Sailors S
WHERE rating > 8

Commercial DBMSs do not provide user interface for

relational algebra queries!

But the core operations and functions in the DBMS

internal modules are all based on relational algebra
10
Query Tree: A Query Evaluation Plan

 Query tree: a data structure that corresponds to a

relational algebra expression

 Input relations of the query as leaf nodes

 Relational algebra operations as internal nodes

 An execution of the query tree consists of executing

internal node operations

11
 Query Tree
 [Link]

SELECT [Link]
[Link] = [Link] FROM Student S, Enrolled E
WHERE [Link] = [Link]
AND [Link] > 4
 [Link] > 4  [Link] = CSE454
AND [Link] = CS545

S E

sname(gpa > 4(S) id=sid cid=CS545(E))

12
Optimization of Query Trees
 Get initial Query Tree
 Apply Cartesian Product of relations in FROM
 Selection and Join conditions of WHERE is applied
 Project on attributes in SELECT

 Transform it into an Equivalent Query Tree

 Represents a different relational expression
 Gives the same result
 More efficient to execute

 How?
 Next slides..

13
Several alternatives!

14
Equivalent Query Trees

 Alternative query evaluation plans are

considered as follows:

1. Selections and cross products can be combined

into joins
2. Joins can be reordered
3. Selections and projections can be pushed
ahead of joins
Equivalent Query Trees Cont.

 The output of one operator is sometimes

pipelined into the next operator without storing
it in a temporary relation
 When pipelining to a unary operator, we say
that the operator is applied on-the-fly and the
operator does not incur additional I/Os

Result tuples
of first join
pipelined into
join with C C

A B
 Left Deep Plans
 Plan Space: Too large, must be pruned
 In left-deep trees, the right child of each join node is a base table
 Only the space of left-deep plans is considered as they allow
output of each operator to be pipelined into the next operator 
fully pipelined plans

D D

C C A B C D

A B A B
Cost Estimation of a Plan

 For each plan considered:

 Must estimate cost of each operation in plan
tree
 Depends on input (relation) size
 Need to estimate the cost using different access
paths (sequential scan, index, etc.)
 Must also estimate size of result for each
operation in tree!
 Use information about the input relations
 For selections and joins, use estimates, e.g.,
“selectivity”
Operations of Relational Algebra

In this
Lecture

19
Operations of Relational Algebra

20
 Projection () - Example
SID Name Rating Age
28 Yuppy 9 35
Name,Rating(S)
31 Lubber 8 55
44 Guppy 5 35
58 Rusty 10 35

S
Name Rating
The result of an operation is a: Yuppy 9
new relation
Lubber 8
Guppy 5
Rusty 10

21
Projection () - Example
SID Name Rating Age
28 Yuppy 9 35
Age(S)
31 Lubber 8 55
44 Guppy 5 35
58 Rusty 10 35

Age
35
55

22
 Projection ()

<Attribute List> (R)

When applied on a a relation, say R

 Deletes attributes that are not in <Attribute List>
 Schema of result identical to the fields in the Attribute List

 Projection has to eliminate duplicates: why?

 In the formal relational model: a relation is a set of records
 Elements cannot be repeated in a set
 SQL typically does not eliminate duplicates unless the user
explicitly asks for it (i.e., DISTINCT)!

23
Selection () - Example
SID Name Rating Age
28 Yuppy 9 35 σRating > 8(S)
31 Lubber 8 55
44 Guppy 5 35
58 Rusty 10 35

SID Name Rating Age

28 Yuppy 9 35
58 Rusty 10 35

24
Selection ()

σ<Selection Condition> (R)

When applied on a relation, say R

 Selects rows that satisfy <Selection Condition>
 Schema of result identical to schema of input relation
 <Selection Condition> applied independently to each
individual tuple t in R
 If condition evaluates to TRUE, tuple selected
 Boolean conditions: AND, OR, NOT

25
 Relational Algebra Expression - Example
SID Name Rating Age
28 Yuppy 9 35 name,rating( Rating > 8(S))
31 Lubber 8 55
44 Guppy 5 35
58 Rusty 10 35

A sequence of relational algebra Name Rating

operations forms a: Yuppy 9
relational algebra expression Rusty 10

26
SELECT vs. WHERE
 In SQL:
 Selection (σ) is expressed by the WHERE clause
 SELECT clause actually does Projection (π)

 It is a historical accident 

27
SELECT Queries - Examples
 Point Query (equality search):
  SSN='123456789' (Employee)
 Range Query
  DNUMBER>5 (Department)
 Conjunction Query
  DNO=5 AND SALARY>30000 AND GENDER=F (Employee)

 Disjunction Query
  DNO=5 OR SALARY>30000 OR GENDER=F (Employee)

 How does the DBMS answer each of those queries?

28