Government College of Engineering,
Amravati
Course Name: Database Management Systems (ITU
422)
Topic Name : Evaluation of Expressions
Course Co-Ordinator : S.R. Wankhade
21007008 21007009
21007064 21007016
Durgesh Firake Yash Gupta Pranay Chandrikapure Pratik Zade
𝜋
Query
Evaluation
Table of contents 𝜋
01 What is Query ⋈
Evaluation? σ
02 Query Evaluation Plans
03 Approaches of Query
Evaluation
04 Comparison
01
What is Query
Evaluation?
What is Query
Evaluation ?
It is nothing but a program for an
abstract machine inside the DBMS. It
is produced by the query optimizer. At
times this can also be termed as access
plan because DBMS decide how to
access the rows. Query evaluation
plans are very much similar to
relational algebra expressions in most
of the systems.
02
Query
Evaluation Plans
Creation of Query Evaluation Plan
Generation of query-evaluation plans for an expression involves
several steps:
1. Generating logically equivalent expressions using equivalence rules
2. Annotating resultant expressions to get alternative query plans
3. Choosing the cheapest plan based on estimated cost.
• The overall process is called cost based optimization.
03 (σ())
Approaches of Query J OI N
PROJEC
TION
Evaluation
Approaches of Query Evaluation
1 . Materialization
Demand-driven Pipeline
2 . Pipelining
Producer-driven Pipeline
1. MATERIALIZATION
Compute the result of an evaluation primitive and
materialize (store) the new relation on the disk
In other language, materialize intermediate results in
temporary relations and use those for evaluating
operations at the next level
STEPS IN
MATERIALIZATION
1 Construct an Operator Tree
Use appropriate algorithm for evaluation. Begin by evaluating lowest level operation.
2
Store the result of the operation in the temporary relations. (Result works as an input for
3 every next level up in the tree.)
Use these temporary relations for evaluating the next-level operation in the operator
4 tree.
5 Repeat these steps until all operators at the root of tree will be evaluated
MATERIALIZATION
Lets understand by example how will query evaluate by materialization.
Student Result
Roll no. Name Roll no. Marks
1 Akhil 1 45
2 Jon 2 85 Query is: ( (Student ⋈ σ Marks > 90 (Result))
3 Rohan 3 96 Output
4 Suresh 4 92
(σ Marks > 90 ( Result ⋈ Student )) σMarks > 90
Name Roll no. Name Marks Roll no. Marks
Rohan 3 Rohan 96 3 96
Suresh 4 Suresh 92 4 92
MATERIALIZATION
𝜋 Name
It is called Materialization evalution since,
the result to each intermediate operation are
⋈ created (materialized) and then are then are
used to evaluate of the rest level operation.
σ Mark > 90 Student
Result Cost = Cost of all operation + The cost of
writing the Intermediate result
Operator Tree
2. Pipelining
Concept :
• Involves processing the input relations incrementally
and passing the intermediate results from one
operation to the next without storing them as separate
relations.
• Reduces the need for temporary storage and improves
efficiency by avoiding unnecessary materialization of
intermediate results.
• Allows for faster processing of queries and can be
particularly beneficial when dealing with large datasets.
Start with input relations
1
STEPS IN
PIPELINING
Apply first operation, generate
intermediate result.
2
: Pass intermediate result to
next operation.
3
Apply next operation,
generate new intermediate
result.
4
Repeat steps 3 and 4 for
remaining operations. 5
Final operation produces
desired result.
6
Types of
PIPELINING :
1 . Demand Driven
(Pull Approach)
2 . Procedure Driven
(Push Approach)
Demand Procedure
Start with input
Start with input relations.
relations.
Driven
Producers push relevant
Apply each operation
data to subsequent
and produce data only
operations or
when demanded.
Driven
consumers.
Pass
Consumers
demanded receive
data
pushed
directly
datatoand
the perform
next
computations.
operation.
Repeat steps 2 and 3 for
all operations.
Final operation produces
the desired result based
on demanded
procedure data.
Example:
Example on pipelining
● Students (id, name, age)
● Grades (id, subject, grade)
● And we want to evaluate the following relational expression:
● πStudents.name, Grades.subject, Grades.grade(σStudents.id = Grades.id(Students ⨝ Grades))
ID Name Age ID Subject Grade
1 Akash 15 1 Maths A+
2 Nilesh 16 2 Science B2
3 Suresh 14 3 Eng A2
ID Name Age ID Subject Grade
1 Akash 15 1 Maths A+
1 Akash 15 2 Science B2
1 Akash 15 3 Eng A2
2 Nilesh 16 1 Maths A+
2 Nilesh 16 2 Science B2
2 Nilesh 16 3 Eng A2
3 Suresh 14 1 Maths A+
3 Suresh 14 2 Science B2
3 Suresh 14 3 Eng A2
ID Name Age ID Subject Grade
1 Akash 15 1 Maths A+
1 Akash 15 2 Science B2
1 Akash 15 3 Eng A2
2 Nilesh 16 1 Maths A+
2 Nilesh 16 2 Science B2
2 Nilesh 16 3 Eng A2
3 Suresh 14 1 Maths A+
3 Suresh 14 2 Science B2
3 Suresh 14 3 Eng A2
ID Name Age ID Subject Grade
1 Akash 15 1 Maths A+
2 Nilesh 16 2 Science B2
3 Suresh 14 3 Eng A2
Name Subject Grade
Akash Maths A+
Nilesh Science B2
Suresh Eng A2
04 Compare
MATERIALIZA
TION VS
PIPELINING
Traditional
Modern Approach
Approach
Uses temporary
Don't Materialization
relations
use temporary
results
the results
to store
relations the
to store Pipelining
Less Efficient
More Efficient
No highermemory
Requires requirement of secondary
buffers at a high rate for
memory
generating outputs
No Trashing
Poor performance in trashing
Costlier
Less CostOperation
Thanks!
Any questions?
