[go: up one dir, main page]
Scribd
Upload
11 views21 pages

Chapter One1

Uploaded by

tafeseobsi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
11 views21 pages

Chapter One1

Uploaded by

tafeseobsi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 21

CHAPTER one

QUERY PROCESSING &


OPTIMIZATION
Overview of Query Processing

Query processing: The activities involved in

parsing, optimizing, and executing a query.


It is the process of breaking the high level

language into low level language which


machine can understand and perform the
requested action for user.
Basic task of query processing is extracting

data from a database.


2
Three Steps of Query Processing
1. Parsing and translation Query

2. Optimization Parser &


Translator

3. Evaluation Relational Algebra


Expression Statistics
About Data

Optimizer

Query
Evaluation Engine Execution Plan
Output

Data
3
Three Steps of Query Processing
1) Parsing and translation: translate the query into relational
algebra
2) Optimization is to find the most efficient evaluation plan
for a query because there can be more than one way.
 Optimization: Find the “cheapest" execution

plan for a query


3) Evaluation :The query execution engine takes a physical
query plan, executes the plan, and returns the result 4
Cont
As query processing includes certain activities
for data retrieval.
 Initially, the given user queries translated in
high-level database languages such as SQL.
Before processing a query, a computer system
needs to translate the query into a human-
readable and understandable language.
Consequently, SQL or Structured Query
Language is the best suitable for humans.
 But, it is not perfectly suitable for the internal
representation of the query to the system.
Cont
Relational algebra is well suited for the

internal representation of a query.


When a user executes any query, for

generating the internal form of the query, the

parser in the system checks the syntax of the


query, verifies the name of the relation in the
database, the tuple, and finally the required
attribute value.
optimization
Query optimization: The activity of choosing

an efficient execution strategy for processing


a query.
 Aim

To choose the one that minimizes resource

usage.
Reduce the total execution time of the query,

which is the sum of the execution times of all


7
cont
The steps of the process performed at the time of query
execution by the engine database are described by a set
of instructions called a query plan.
The query optimizer generates the SQL Server execution
plan or query plan.
The generation of an optimum and economic query plan
is the main objective of the query optimizer.
 Multiple execution plans are generated by the query
processing engine after query execution, and from those
generated execution plans, a plan with the best
performance is selected.
Query Evaluation
With addition to the relational algebra translation,

It is required to annotate the translated relational

algebra expression with the instructions used for


specifying and evaluating each operation.
After translating the user query, the system

executes a query evaluation plan.


Query Evaluation Plan
In order to fully evaluate a query, the system
needs to construct a query evaluation plan.
Example 1.1 - Different Strategies
Find all Managers who work at a London
branch.
SELECT * FROM Staff s, Branch b
WHERE
s.branchNo = b.branchNo AND (s.position
= ‘Manager’ AND b.city = ‘London’);
Three equivalent relational algebra queries
corresponding to this SQL statement are:

10
Translating SQL Queries into Relational Algebra
Query block

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.


Translating SQL Queries into Relational Algebra
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))


Using Heuristic in Query Optimization
Heuristic algorithm for Algebraic Optimization:

1. The goal of heuristic is to apply first the operations that


reduce the size of intermediate results.
2. Perform select operations as early as possible to reduce
the number of tuples and perform project operations as
early as possible to reduce the number of attributes.
3.Most restrictive select and join operations are should
be executed before other similar operations.
13
Heuristics Algorithm
 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:
Q2: SELECT P.NUMBER,P.DNUM, E.LNAME, E.ADDRESS, E.BDATE

FROM PROJECT AS P, DEPARTMENT AS D, EMPLOYEE


AS E

WHERE P.DNUM=D.DNUMBER AND D.MGRSSN=E.SSN


AND

P.PLOCATION=‘STAFFORD’;

14
Two query trees for Q2

15
Cost Estimates in Query Optimization

 Cost-based query optimization: Estimate

and compare the costs of executing a query


using different execution strategies
 Finally choose the strategy with the

lowest cost estimate.

16
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.

17
Query Optimization in ORACLE
ORACLE DBMS provides two different approaches

to query optimization: rule-based and cost-based.


In rule-based approach, the optimizer chooses

execution plans based on heuristically ranked


operations.
ORACLE maintains 15 ranked access paths to get

more efficient approach.


However, cost-based approach better than
rule-based approach.
The optimizer examines alternative access paths
and operator algorithms and chooses the
execution plan with lowest estimated cost.
Catalog tables containing statistical information
of the table.
ORACLE optimizer calculates cost based on
the estimated usage of resources.
The goal of cost-based optimization in
ORACLE is to minimize elapsed time to
process the entire query
Semantic Query Optimization
Semantic Query Optimization: Uses constraints specified on the
database schema in order to modify one query into another query that
is more efficient to execute. Consider the following SQL query,
SELECT E.LNAME, M.LNAME
FROM EMPLOYEE E M
WHERE E.SUPERSSN=M.SSN AND
E.SALARY>M.SALARY
Explanation: Suppose that we had a constraint on the
database schema that stated that no employee can earn
more than his or her direct supervisor. If the semantic
query optimizer checks for the existence of this
constraint, it need not execute the query at all because it
knows that the result of the query will be empty.
This is the end of the
lecture!
I hope you enjoyed it.

21

You might also like