0% found this document useful (0 votes)

6 views29 pages

Module 4. Query Processing, Query Tree, Query Optimization

This document covers query processing and optimization in database systems, detailing the steps involved in optimizing SQL queries through internal representations like query trees and graphs. It discusses the importance of heuristics in improving query performance and provides examples of translating SQL queries into relational algebra. Additionally, it outlines the process of optimizing query trees to enhance execution efficiency.

Uploaded by

adiraj.kashyap.01

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

6 views29 pages

Module 4. Query Processing, Query Tree, Query Optimization

Uploaded by

adiraj.kashyap.01

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Database Systems

BCSE302L
Module 4 – Query Processing and Optimization

Dr. Abishi Chowdhury

Assistant Professor (Sr.)
SCOPE, VIT Chennai
Topics to be covered

 Introduction to Query Processing

 Combining Operations using Pipelining
 Using Heuristics in Query Optimization

20 March 2024 VITCC-BCSE302L 2

Introduction to Query Processing
• Query optimization:
– The process of choosing a suitable execution strategy for processing
a query.
• Two internal representations of a query:
– Query Tree
– Query Graph

20 March 2024 VITCC-BCSE302L 3

Basic Steps in Query Processing :
Optimization
• A query expressed in a high-level query language (SQL) must first be Scanned,
Parsed, and Validated.
• The Scanner identifies the query tokens (SQL keywords, attribute names, and relation
names).
• The Parser checks the query syntax to determine whether it is formulated according to
the syntax rules (rules of grammar) of the query language.
• The Validation involves ensuring and checking whether all attribute and relation names
are valid and semantically meaningful names in the schema.
• An internal representation of the query is then created Query (Tree/Graph).
• The DBMS must then devise an execution strategy/query plan for retrieving the results of
the query from the database.
• 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.
20 March 2024 VITCC-BCSE302L 4
Basic Steps in Query Processing :
Optimization

20 March 2024 VITCC-BCSE302L 5

Basic Steps in Query Processing :
Optimization

20 March 2024 VITCC-BCSE302L 6

Basic Steps in Query Processing :
Optimization (contd…)
• A relational algebra expression may have many equivalent expressions

– E.g., salary75000(salary(instructor)) is equivalent to

salary(salary75000(instructor))

• Each relational algebra operation can be evaluated using one of several different
algorithms
– Correspondingly, a relational-algebra expression can be evaluated in many
ways.
 Query Optimization: Amongst all equivalent evaluation plans choose the one
with lowest cost.
20 March 2024 VITCC-BCSE302L 7
Translating SQL Queries into
Relational Algebra
• An SQL query is first translated into an equivalent extended Relational algebra
expression, represented as a query Tree/Graph data structure and then optimized.

• SQL queries are decomposed into query blocks(Units/Chunks).

• Query Block: It is a single SELECT-FROM-WHERE expression, as well as GROUP BY

and HAVING clause if these are part of the block.

• Nested queries: are within a query are identified as separate query blocks.

• Aggregate operators: are in SQL must be included in the extended algebra.

20 March 2024 VITCC-BCSE302L 8

Translating SQL Queries into
Relational Algebra (contd…)

 Finally, The query optimizer will choose an execution plan for each query block.
20 March 2024 VITCC-BCSE302L 9
Translating SQL Queries into
Relational Algebra (contd…)
 For Converting/Translating a Query, written in HLL(SQL) into
Relational Algebra, need to have an appropriate strategies for the
following:
 Algorithm for Selection Operation Algorithm for Projection and Set Operation
Algorithm for External Sorting

 Implementation of JOIN, SET and Aggregate Operations Combining Operations

Using Pipelining

 Parallel Algorithms for Query Processing

20 March 2024 VITCC-BCSE302L 10

Query Trees and Heuristics for Query
Optimization
 Heuristic : Problem solving by Experimental (Trail-and-Error) Heuristic Rules :
Used to Modify the Internal Representation of Query, to improve the performance.
i.e Query Tree/ Query Graph (Data Structure)

 Process for heuristics optimization

1. The parser of a high-level query generates an initial internal representation;
2. Apply heuristics rules to optimize the internal representation.
3. A query execution plan is generated to execute groups of operations based on
the access paths available on the files involved in the query.

The main heuristic is to apply first, the operations that reduce the size of
intermediate results.
E.g., Apply SELECT and PROJECT operations before applying the JOIN or other binary
operations.
20 March 2024 VITCC-BCSE302L 11
Query Trees and Heuristics for Query
Optimization (contd…)
• 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.

20 March 2024 VITCC-BCSE302L 12

Example Database

20 March 2024 VITCC-BCSE302L 13

Using Heuristics in Query Optimization: Example1
• 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.

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

• Relational algebra:
PNUMBER, DNUM, LNAME, ADDRESS, BDATE (((PLOCATION=‘STAFFORD’(PROJECT)) DNUM=DNUMBER (DEPARTMENT))
MGR_SSN=SSN (EMPLOYEE))

20 March 2024 VITCC-BCSE302L 14

Example 1 (a)
Figure:
Query tree
corresponding to the
relational algebra

20 March 2024 VITCC-BCSE302L 15

Example 1 (b)
Figure:
Initial (canonical)
query tree for SQL
query

20 March 2024 VITCC-BCSE302L 16

Example 1 (c)

Figure:
Query graph for the SQL
query

20 March 2024 VITCC-BCSE302L 17

Heuristics Optimization of Query Trees
• Heuristic Query Optimization:
• Oracle calls this Rule Based optimization.
• A query can be represented as a tree data structure. Operations are at the interior
nodes and data items (tables, columns) are at the leaves.
• The query is evaluated in a depth-first pattern.
• 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:
SELECT [Link]
FROM EMPLOYEE E, WORKS_ON W, PROJECT P
WHERE [Link] = ‘Aquarius’ AND [Link]=[Link] AND [Link]=[Link] AND [Link] > ‘1957-12-31’;

20 March 2024 VITCC-BCSE302L 18

Steps to Optimize Query
• Query Optimization Steps in converting a Query Tree
 Initial (Canonical) Query Tree for SQL Query ’Q’. Moving SELECT

Operations down the Query Tree

 Applying the More Restrictive SELECT Operation First

 Replacing the CARTESIAN PRODUCT and SELECT Operations with JOIN
Operations
 Moving PROJECTION Operations down the Query Tree ’Q’