Query Processing

Query Processing
Query processing refers to the procedure of
converting a high-level query, typically written
in a language like SQL (Structured Query
Language), into a low-level or machine-
understandable form that the database
management system (DBMS) can execute.

2
Why we need query processing

3
 High-Level Query (SQL)
Imagine you have a table of students in a
database, and you want to find all the students
who are in grade 10.

In SQL, you might write the query like this:

SELECT * FROM students WHERE grade = 10;

4
 Low-Level Form (Machine-Understandable)

• The computer can't directly understand SQL. It

needs to convert this query into a set of
specific instructions (low-level operations) that
it can execute.
• Let's see how this works step by step:

5
 Low-Level Form (Machine-Understandable)

 Scan the Table:

The computer will start by looking at the
"students" table. This step is called a table scan.
 Filtering the Rows:
Then, the computer will filter out only the rows
(students) where the grade equals 10. This
filtering process is called a selection operation.
 Returning the Results:
Finally, the computer will gather the filtered rows
(students in grade 10) and return the result to you.
6
 Symbolic representation
The DBMS might internally represent this with
symbols like:
σ (grade = 10) (students)
This means "apply the selection (σ) where the
grade is 10 on the 'students' table."

7
 High-Level Query (SQL)
Imagine you have a table called "books" that
stores information about different books in a
library. Now, you want to find the titles of all
books written by "J.K. Rowling."
In SQL, you might write the query like this:
SELECT title FROM books WHERE author =
'J.K. Rowling';

8
 Low-Level Form (Machine-Understandable)

Now, the computer needs to convert this high-level SQL query into
steps it can execute. Here's how that happens:
 Scan the Table:
First, the computer will look at all the rows in the "books" table to
find the books written by "J.K. Rowling." This is called a table
scan.
 Filter the Rows:
Next, for each row, it checks the "author" column. If the author is
"J.K. Rowling," the computer keeps that row. This is the selection
operation.
 Project the Results:
After finding the matching rows, the computer only needs to return
the "title" column. This is called a projection operation, where it
selects only the needed column (title) and ignores the rest (like year,
genre, etc.).

9
 Symbolic representation
• In a symbolic form, it might look like this:
• π (title) (σ (author = 'J.K. Rowling') (books))
– π means select the column( the title).
– σ means "select" rows where the author is 'J.K.
Rowling.'
– books is the table being scanned.

10
Basic steps involved in query processing

Parsing & translation

Optimization
evaluation

11
Explanation of query processing

(High Level Query)

Query input

(Low Level Query) Query output

12
Steps involved in query processing

Query Tree

13
 Explanation to the diagram
The diagram you’ve provided shows the basic
process of how a high-level SQL query is
transformed into a machine-understandable
form and executed by the database

14
 Steps involved in query processing

Query Let's say you want to find all

Parser & Translator students in grade 5. Your
Relational Algebra
SQL query looks like this:
Optimizer
Execution Plan
Evaluation Engine SELECT * FROM students
Query Output WHERE grade = 5;

15
 Steps involved in query processing

Query The parser checks whether

Parser & Translator your query is written
Relational Algebra
correctly. It looks for any
Optimizer
Execution Plan
errors, like wrong words or
Evaluation Engine symbols. If everything is
Query Output correct, the translator
changes your SQL query into
something the computer can
work with, called a relational
algebra expression.
16
 Steps involved in query processing
In this step, the SQL query
Query
Parser & Translator
SELECT * FROM students WHERE grade = 5;
Relational Algebra
Optimizer is converted into a relational algebra expression.
Execution Plan
Evaluation Engine This expression is something like:
Query Output
σ (grade = 5) (students)

This means

"select all rows where grade equals 5 from the students table."
17
 Steps involved in query processing
 The relational algebra expression is the
Query mathematical version of your query. It
Parser & Translator describes what needs to be done, like:
Relational Algebra σ (Selection) means we need to select
Optimizer specific rows where a condition is true
Execution Plan (grade = 5).
Evaluation Engine
Query Output  students is the table we are working with.
 This expression tells the computer, in a
more detailed way, what to do with the
data.

18
 Steps involved in query processing
 The optimizer will help us in choosing the best
Query one out of the available list.
Parser & Translator  To find the solution for the given problem, we
have two options here.
Relational Algebra
 Solution 1:
Optimizer  You could either look at every single book until
Execution Plan you find the ones about grade 5.
Evaluation Engine
 Solution 2:
Query Output
 You could look in the section labeled “Grade 5” to
find them faster.

The optimizer chooses the best way to:

 Look through the "students" table.
 Find the rows where grade = 5 as quickly as
possible.
19
 Steps involved in query processing
 Once the optimizer decides the best way to do the
Query task, the computer creates an execution plan.
Parser & Translator  This is a detailed list of steps the database will
follow to get the result you want.
Relational Algebra
Optimizer In this case, the steps might be:
Execution Plan
Evaluation Engine  Check the "students" table.
Query Output
 Look for rows where the "grade" is 5.

 Return those rows.

20
 Steps involved in query processing
The evaluation engine actually runs the execution
Query plan. It goes through the database, follows the
Parser & Translator steps, and fetches the data.

Relational Algebra
For example:
Optimizer
Execution Plan  The engine will scan the "students" table.
Evaluation Engine
Query Output  It checks each student's grade.

 When it finds students in grade 5, it picks them

out.

21
 Steps involved in query processing

Query Finally, the result of your

Parser & Translator query is shown. In this
Relational Algebra
example, you’ll see a list of
Optimizer
Execution Plan
all the students in grade 5.
Evaluation Engine
Query Output

22
Summary :
• Query: You ask the computer, "Find students in grade
5.
• "Parser & Translator: The computer checks your
question and translates it into instructions it can
understand.
• Relational Algebra: The computer turns the question
into a step-by-step instruction plan.
• Optimizer: The computer finds the fastest way to
answer your question.
• Execution Plan: The computer writes a list of steps to
follow.
• Evaluation Engine: The computer actually follows the
steps and finds the students.
• Query Output: You get the list of students in grade 5.
23
 Given query
Select book, title, price from Book where price > 30

Solution 1:
σprice>30(π book,title,price(Book))
Solution 2:
πbook,title,price (σprice>30(Book))

24
 Query tree
• It is used to represent the relational algebraic
expressions
• The relational algebraic expression should be
in tree data structure.
• Relations should be represented as leaf nodes
• Operators as internal nodes.

25
 Solution 1:
σprice>30(π book,title,price(Book))
σprice>30

π book,title,price

Book

26
 Solution 2:
πbook,title,price (σprice>30(Book))
πbook,title,price

σprice>30

Book

27
 Note
Different evaluation plans can have different
cost. It is the responsibility of query optimizer
to select the best query to generate least costly
plan.

28