Introduction

In network and hierarchical DBMSs, low-level

procedural query language is generally
embedded in high-level programming
language.
Programmer’s responsibility to select most
appropriate execution strategy.
With declarative languages such as SQL, user
Query Processing & Optimization specifies what data is required rather than
how it is to be retrieved.
Relieves user of knowing what constitutes
good execution strategy.
Pearson Education © 2014 Pearson Education © 2014 2

Introduction Query Processing

Also gives DBMS more control over system Activities involved in retrieving data from the
performance. database.
Two main techniques for query optimization: Aims of QP:
heuristic rules that order operations in a query; transform query written in high-level language
comparing different strategies based on relative (e.g. SQL), into correct and efficient execution
costs, and selecting one that minimizes resource strategy expressed in low-level language
usage. (implementing RA);
execute strategy to retrieve required data.
Disk access tends to be dominant cost in
query processing for centralized DBMS.

Pearson Education © 2014 3 Pearson Education © 2014 4

Query Optimization Example 23.1 - Different Strategies

Activity of choosing an efficient execution strategy
for processing query. Find all Managers who work at a London
branch.
• As there are many equivalent transformations of
same high-level query, aim of QO is to choose one
that minimizes resource usage. SELECT *
• Generally, reduce total execution time of query. FROM Staff s, Branch b
• May also reduce response time of query. WHERE s.branchNo = b.branchNo AND
• Problem computationally intractable with large (s.position = ‘Manager’ AND b.city = ‘London’);
number of relations, so strategy adopted is reduced
to finding near optimum solution.

Pearson Education © 2014 5 Pearson Education © 2014 6

Phases of Query Processing Phases of Query Processing
QP has four main phases:
decomposition (consisting of parsing and
validation);
optimization;
code generation;
execution.

Pearson Education © 2014 7 8

Pearson Education © 2014