Database Management System (MDS 505)

Jagdish Bhatta

Jagdish Bhatta 1
 Unit – 4
SQL & Query Optimization

Jagdish Bhatta 2
 SQL Standards ,Data types

 We have already covered these in unit 2.

Jagdish Bhatta 3
 Database Objects- DDL-DML-DCL-TCL

 We have already covered these in unit 2

Jagdish Bhatta 4
 Embedded SQL
 Embedded SQL is a method of combining the computing power of
a programming language and the database manipulation capabilities
of SQL. Embedded SQL statements are SQL statements written inline
with the program source code, of the host language. The embedded
SQL statements are parsed by an embedded SQL preprocessor and
replaced by host-language calls to a code library. The output from the
preprocessor is then compiled by the host compiler. This allows
programmers to embed SQL statements in programs written in any
number of languages such as C/C++. E.g.: Proc*C is Oracle’s
embedded SQL environment.

Jagdish Bhatta 5
 Embedded SQL
 E.g: Embedding SQL into C.
{
int a;
/* ... */
EXEC SQL SELECT salary INTO :a
FROM Employee
WHERE SSN=876543210;
/* ... */
printf("The salary is %d\n", a);
/* ... */
}
All SQL statements need to start with EXEC SQL and end with a semicolon ";". You can place the SQL
statements anywhere within a C/C++ block, with the restriction that the declarative statements do not come
after the executable statements.
Jagdish Bhatta 6
 Static Vs Dynamic SQL

 In the previous examples, the embedded SQL queries were written as

part of the host program source code. Hence, anytime we want to
write a different query, we must modify the program code and go
through all the steps involved (compiling, debugging, testing, and so
on). In some cases, it is convenient to write a program that can
execute different SQL queries or updates (or other operations)
dynamically at runtime. For example, we may want to write a
program that accepts an SQLquery typed from the monitor, executes
it, and displays its result, such as the interactive interfaces available
for most relational DBMSs. Another example is when a user-friendly
interface generates SQL queries dynamically for the user based on
user input through a Web interface or mobile App. Dynamic SQL,
which is one technique for writing this type of database program.

Jagdish Bhatta 7
 Query Processing

 Query processing refers to the range of activities

involved in extracting data from a database. The
activities include translation of queries in high-level
database languages into expressions that can be used at the
physical level of the file system, a variety of query-
optimizing transformations, and actual evaluation of
queries.
 The basic steps are:
– Parsing and translation.
– Optimization.
– Evaluation.

Jagdish Bhatta 8
 Query Processing

 Before query processing can begin, the system must

translate the query into a usable form. A language such as
SQL is suitable for human use, but is ill suited to be the
system’s internal representation of a query. A more useful
internal representation is one based on the extended
relational algebra.

Jagdish Bhatta 9
 Query Processing

 Thus, the first action the system must take in query

processing is to translate a given query into its internal
form. This translation process is similar to the work
performed by the parser of a compiler. In generating the
internal form of the query, the parser checks the syntax of
the user’s query, verifies that the relation names appearing
in the query are names of the relations in the database, and
so on. The system constructs a parse-tree representation of
the query, which it then translates into a relational-algebra
expression. If the query was expressed in terms of a view,
the translation phase also replaces all uses of the view by
the relational-algebra expression that defines the view.
Jagdish Bhatta 10
 Query Processing

Jagdish Bhatta 11
 Query Processing

 Given a query, there are generally a variety of methods for

computing the answer. For example, we have seen that, in
SQL, a query could be expressed in several different ways.
Each SQL query can itself be translated into a relational
algebra expression in one of several ways. Furthermore, the
relational-algebra representation of a query specifies only
partially how to evaluate a query; there are usually several
ways to evaluate relational-algebra expressions.

Jagdish Bhatta 12
 Query Processing

 Consider the query;

select salary
from instructor
where salary < 75000;
 This query can be translated into either of the following
relational-algebra expressions:

Jagdish Bhatta 13
 Query Processing
 Further, we can execute each relational-algebra operation by one of
several different algorithms.
 To specify fully how to evaluate a query, we need not only to provide
the relational-algebra expression, but also to annotate it with
instructions specifying how to evaluate each operation. Annotations
may state the algorithm to be used for a specific operation, or the
particular index or indices to use.
 A relational algebra operation annotated with instructions on how to
evaluate it is called an evaluation primitive. A sequence of
primitive operations that can be used to evaluate a query is a
query-execution plan or query-evaluation plan.
 The query-execution engine takes a query-evaluation plan,
executes that plan, and returns the answers to the query.

Jagdish Bhatta 14
 Query Processing

Jagdish Bhatta 15
 Query Processing
 The different evaluation plans for a given query can have different
costs. We do not expect users to write their queries in a way that
suggests the most efficient evaluation plan. Rather, it is the
responsibility of the system to construct a query evaluation plan that
minimizes the cost of query evaluation; this task is called query
optimization.
 Once the query plan is chosen, the query is evaluated with that plan,
and the result of the query is output.
 The sequence of steps already described for processing a query is
representative; not all databases exactly follow those steps. For
instance, instead of using the relational-algebra representation,
several databases use an annotated parse tree representation based on
the structure of the given SQL query

Jagdish Bhatta 16
 Query Processing

 In order to optimize a query, a query optimizer must know

the cost of each operation. Although the exact cost is hard
to compute, since it depends on many parameters such as
actual memory available to the operation, it is possible to
get a rough estimate of execution cost for each operation.

Jagdish Bhatta 17
 Query Tree

 A query tree is a tree data structure that corresponds to an extended

relational algebra expression. It represents the input relations of the
query as leaf nodes of the tree, and it 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. The order of execution of
operations starts at the leaf nodes, which represents the input
database relations for the query, and ends at the root node, which
represents the final operation of the query. The execution terminates
when the root node operation is executed and produces the result
relation for the query

Jagdish Bhatta 18
 Query Tree

Jagdish Bhatta 19
 Query Tree

Jagdish Bhatta 20
 Measures of Query Cost

 There are multiple possible evaluation plans for a query, and it is

important to be able to compare the alternatives in terms of their
(estimated) cost, and choose the best plan. To do so, we must
estimate the cost of individual operations, and combine them to get
the cost of a query evaluation plan.
 The cost of query evaluation can be measured in terms of a number of
different resources, including disk accesses, CPU time to execute a
query, and, in a distributed or parallel database system, the cost of
communication.
 In large database systems, the cost to access data from disk is usually
the most important cost, since disk accesses are slow compared to in-
memory operations.

Jagdish Bhatta 21
 Measures of Query Cost
 The number of block transfers from disk and the number of disk seeks
can be used to estimate the cost of a query-evaluation plan. If the disk
subsystem takes an average of tT seconds to transfer a block of data,
and has an average block-access time (disk seek time plus rotational
latency) of tS seconds, then an operation that transfers b blocks and
performs S seeks would take b ∗ tT + S ∗ tS seconds.
 The values of tT and tS must be calibrated for the disk system used,
but typical values for high-end disks today would be tS = 4
milliseconds and tT = 0.1 milliseconds, assuming a 4-kilobyte block
size and a transfer rate of 40 megabytes per second.
 One can refine the cost estimates further by distinguishing block
reads from block writes, since block writes are typically about twice
as expensive as reads (this is because disk systems read sectors back
after they are written to verify that the write was successful).
Jagdish Bhatta 22
 Measures of Query Cost
 The response time for a query-evaluation plan (that is, the wall-
clock time required to execute the plan), assuming no other activity is
going on in the computer, would account for all these costs, and could
be used as a measure of the cost of the plan.
 Unfortunately, the response time of a plan is very hard to estimate
without actually executing the plan, for the following reasons:
– The response time depends on the contents of the buffer when
the query begins execution; this information is not available
when the query is optimized, and is hard to account for even if it
were available.
– In a system with multiple disks, the response time depends on
how accesses are distributed among disks, which is hard to
estimate without detailed knowledge of data layout on disk.

Jagdish Bhatta 23
 Measures of Query Cost

 Optimizers often try to minimize the total resource consumption of a

query plan. Where resource consumption may be extra disk reads,
parallel reads across multiple disks etc.

Jagdish Bhatta 24
 Evaluation of Expressions

 The obvious way to evaluate an expression is simply to evaluate one

operation at a time, in an appropriate order. The result of each
evaluation is materialized in a temporary relation for subsequent use.
A disadvantage to this approach is the need to construct the
temporary relations, which (unless they are small) must be written to
disk. An alternative approach is to evaluate several operations
simultaneously in a pipeline, with the results of one operation
passed on to the next, without the need to store a temporary relation.

Jagdish Bhatta 25
 Evaluation of Expressions
 Materialization:
 Consider the expression;

Jagdish Bhatta 26
 Evaluation of Expressions
 Materialization:

 If we apply the materialization approach, we start from the

lowest-level operations in the expression (at the bottom of the
tree). In our example, there is only one such operation: the selection
operation on department. The inputs to the lowest-level operations
are relations in the database. We execute these operations by the
algorithms that we studied earlier, like selection, join etc, and we
store the results in temporary relations. We can use these temporary
relations to execute the operations at the next level up in the tree,
where the inputs now are either temporary relations or relations
stored in the database. In our example, the inputs to the join are the
instructor relation and the temporary relation created by the selection
on department. The join can now be evaluated, creating another
temporary relation.
Jagdish Bhatta 27
 Evaluation of Expressions
 Materialization:
 By repeating the process, we will eventually evaluate the operation at
the root of the tree, giving the final result of the expression. In the
earlier example, we get the final result by executing the projection
operation at the root of the tree, using as input the temporary relation
created by the join.

 This is known as materialized evaluation, since the results of each

intermediate operation are created (materialized) and then are used
for evaluation of the next-level operations.

 To compute the cost of evaluating an expression as done here, we

have to add the costs of all the operations, as well as the cost of
writing the intermediate results to disk.
Jagdish Bhatta 28
 Evaluation of Expressions
 Pipelining:
 We can improve query-evaluation efficiency by reducing the number
of temporary files that are produced. We achieve this reduction by
combining several relational operations into a pipeline of operations,
in which the results of one operation are passed along to the next
operation in the pipeline. This is called pipelined evaluation.
 For example, consider the expression If materialization
were applied, evaluation would involve creating a temporary relation
to hold the result of the join, and then reading back in the result to
perform the projection. These operations can be combined: When the
join operation generates a tuple of its result, it passes that tuple
immediately to the project operation for processing. By combining
the join and the projection, we avoid creating the intermediate result,
and instead create the final result directly.

Jagdish Bhatta 29
 Evaluation of Expressions
 Pipelining:
 Creating a pipeline of operations can provide two benefits:
– It eliminates the cost of reading and writing temporary
relations, reducing the cost of query evaluation.
– It can start generating query results quickly, if the root
operator of a query evaluation plan is combined in a pipeline
with its inputs. This can be quite useful if the results are displayed
to a user as they are generated, since otherwise there may be a
long delay before the user sees any query results.

Jagdish Bhatta 30
 Query Optimization

 Query optimization is the process of selecting the most efficient

query-evaluation plan from among the many strategies usually
possible for processing a given query, especially if the query is
complex. We do not expect users to write their queries so that they
can be processed efficiently. Rather, we expect the system to
construct a query-evaluation plan that minimizes the cost of query
evaluation. This is where query optimization comes into play.
 Query optimization is the process of executing a SQL query in
relational databases to determine the most efficient way to execute a
given query by considering the possible query plans. The goal of
query optimization is to optimize the given query for the sake of
efficiency.

Jagdish Bhatta 31
 Query Optimization

 Query optimization in database has gained significant importance as

it helps to reduce the size, memory usage and time required for any
query to be processed.
 The main objective of any query optimization is to determine the best
strategy for executing each query.

Jagdish Bhatta 32
 Query Optimization

 Consider the following relational-algebra expression, for the query

“Find the names of all instructors in the Music department together
with the course title of all the courses that the instructors teach.”

 Since we are concerned with only those tuples in the instructor

relation that pertain to the Music department, we do not need to
consider those tuples that do not have dept name = “Music”. By
reducing the number of tuples of the instructor relation that we need
to access, we reduce the size of the intermediate result. Our query is
now represented by the relational-algebra expression:

Jagdish Bhatta 33
 Query Optimization

Jagdish Bhatta 34
 Query Optimization

Jagdish Bhatta 35
 Query Optimization

 An evaluation plan defines exactly what algorithm should be used

for each operation and how the execution of the operations should be
coordinated. Figure 16.2 illustrates one possible evaluation plan for
the expression from Figure 16.1(b).
 As we have seen, several different algorithms can be used for each
relational operation, giving rise to alternative evaluation plans. In the
figure, hash join has been chosen for one of the join operations, while
the other uses merge join, after sorting the relations on the join
attribute, which is ID. All edges are assumed to be pipelined, unless
marked as materialized. With pipelined edges the output of the
producer is sent directly to the consumer, without being written out to
disk.

Jagdish Bhatta 36
 Query Optimization

 Given a relational-algebra expression, it is the job of the query

optimizer to come up with a query-evaluation plan that computes the
same result as the given expression, and is the least costly way of
generating the result (or, at least, is not much costlier than the least
costly way).

Jagdish Bhatta 37
 Query Optimization

 To find the least-costly query-evaluation plan, the optimizer needs to

generate alternative plans that produce the same result as the given
expression, and to choose the least-costly one. Generation of query-
evaluation plans involves three steps:
– generating expressions that are logically equivalent to the given
expression,
– annotating the resultant expressions in alternative ways to
generate alternative query-evaluation plans, and
– estimating the cost of each evaluation plan, and choosing the one
whose estimated cost is the least

Jagdish Bhatta 38
 Heuristic Optimization of Query Trees

 Many different query trees—can be semantically equivalent; that is,

they can represent the same query and produce the same results.

 The query parser will typically generate a standard initial query tree
to correspond to an SQL query, without doing any optimization. For
example, for a SELECTPROJECT-JOIN query, in next slide, the
initial tree is shown in Figure (b). The CARTESIAN PRODUCT of
the relations specified in the FROM clause is first applied; then the
selection and join conditions of the WHERE clause are applied,
followed by the projection on the SELECT clause attributes. Such a
canonical query tree represents a relational algebra expression that is
very inefficient if executed directly, because of the CARTESIAN
PRODUCT (×) operations.

Jagdish Bhatta 39
 Heuristic Optimization of Query Trees

Jagdish Bhatta 40
 Heuristic Optimization of Query Trees

 For example, if the PROJECT, DEPARTMENT, and EMPLOYEE

relations had record sizes of 100, 50, and 150 bytes and contained
100, 20, and 5,000 tuples, respectively, the result of the CARTESIAN
PRODUCT would contain 10 million tuples of record size 300 bytes
each.
 However, this canonical query tree in Figure b is in a simple standard
form that can be easily created from the SQL query. It will never be
executed. The heuristic query optimizer will transform this initial
query tree into an equivalent final query tree that is efficient to
execute.

Jagdish Bhatta 41
 Heuristic Optimization of Query Trees

 The optimizer must include rules for equivalence among extended

relational algebra expressions that can be applied to transform the
initial tree into the final, optimized query tree.
 Consider the following query Q on the database: Find the last names
of employees born after 1957 who work on a project named
‘Aquarius’. This query can be specified in SQL as follows:

Q: SELECT [Link]
FROM EMPLOYEE AS E, WORKS_ON AS W, PROJECT AS P
WHERE [Link]=‘Aquarius’ AND [Link] = [Link]
AND [Link]=[Link] AND [Link] > ‘1957-12-31’;

Jagdish Bhatta 42
 Heuristic Optimization of Query Trees

 The initial query tree for Q is shown in Figure 19.2(a). Executing this
tree directly first creates a very large file containing the CARTESIAN
PRODUCT of the entire EMPLOYEE, WORKS_ON, and PROJECT
files. That is why the initial query tree is never executed, but is
transformed into another equivalent tree that is efficient to execute.
This particular query needs only one record from the PROJECT
relation— for the ‘Aquarius’ project—and only the EMPLOYEE
records for those whose date of birth is after ‘1957-12-31’.
 Figure 19.2(b) shows an improved query tree that first applies the
SELECT operations to reduce the number of tuples that appear in the
CARTESIAN PRODUCT.

Jagdish Bhatta 43
 Heuristic Optimization of Query Trees

 A further improvement is achieved by switching the positions of the

EMPLOYEE and PROJECT relations in the tree, as shown in Figure
19.2(c). This uses the information that Pnumber is a key attribute and
Pname is uniqueof the PROJECT relation, and hence the SELECT
operation on the PROJECT relation will retrieve a single record only.
We can further improve the query tree by replacing any
CARTESIAN PRODUCT operation that is followed by a join
condition as a selection with a JOIN operation, as shown in Figure
19.2(d). Another improvement is to keep only the attributes needed
by subsequent operations in the intermediate relations, by including
PROJECT (π) operations as early as possible in the query tree, as
shown in Figure 19.2(e). This reduces the attributes (columns) of the
intermediate relations, whereas the SELECT operations reduce the
number of tuples (records).
Jagdish Bhatta 44
 Heuristic Optimization of Query Trees

Jagdish Bhatta 45
 Heuristic Optimization of Query Trees

Jagdish Bhatta 46
 Heuristic Optimization of Query Trees

Jagdish Bhatta 47
 Heuristic Optimization of Query Trees

Jagdish Bhatta 48
 Heuristic Optimization of Query Trees

Jagdish Bhatta 49
 Heuristic Optimization of Query Trees

 As the preceding example demonstrates, a query tree can be

transformed step by step into an equivalent query tree that is more
efficient to execute. However, we must make sure that the
transformation steps always lead to an equivalent query tree. To do
this, the query optimizer must know which transformation rules
preserve this equivalence.

Jagdish Bhatta 50
 General Transformation Rules for Relational Algebra
Operations

 There are many rules for transforming relational algebra operations

into equivalent ones. For query optimization purposes, we are
interested in the meaning of the operations and the resulting relations.
Hence, if two relations have the same set of attributes in a different
order but the two relations represent the same information, we
consider the relations to be equivalent.

Jagdish Bhatta 51
 General Transformation Rules for Relational Algebra
Operations

Jagdish Bhatta 52
 General Transformation Rules for Relational Algebra
Operations

Jagdish Bhatta 53
 General Transformation Rules for Relational Algebra
Operations

Jagdish Bhatta 54
 General Transformation Rules for Relational Algebra
Operations

Jagdish Bhatta 55
 General Transformation Rules for Relational Algebra
Operations

Jagdish Bhatta 56
 Outline of a Heuristic Algebraic Optimization Algorithm

 We can now outline the steps of an algorithm that utilizes some of the
above rules to transform an initial query tree into a final tree that is
more efficient to execute (in most cases).
– Step 1: Using Rule 1, break up any SELECT operations with conjunctive
conditions into a cascade of SELECT operations. This permits a greater degree
of freedom in moving SELECT operations down different branches of the tree.
– Step 2: Using Rules 2, 4, 6, and 10, 13, 14 concerning the commutativity of
SELECT with other operations, move each SELECT operation as far down the
query tree as is permitted by the attributes involved in the select condition. If
the condition involves attributes from only one table, which means that it
represents a selection condition, the operation is moved all the way to the leaf
node that represents this table. If the condition involves attributes from two
tables, which means that it represents a join condition, the condition is moved
to a location down the tree after the two tables are combined

Jagdish Bhatta 57
 Outline of a Heuristic Algebraic Optimization Algorithm

 We can now outline the steps of an algorithm that utilizes some of the
above rules to transform an initial query tree into a final tree that is
more efficient to execute (in most cases).
– Step 3: Using Rules 5 and 9 concerning commutativity and associativity of
binary operations, rearrange the leaf nodes of the tree using the following
criteria. First, position the leaf node relations with the most restrictive SELECT
operations so they are executed first in the query tree representation. The
definition of most restrictive SELECT can mean either the ones that produce a
relation with the fewest tuples or with the smallest absolute size.
– Step 4: Another possibility is to define the most restrictive SELECT as the one
with the smallest selectivity; this is more practical because estimates of
selectivities are often available in the DBMS catalog. Second, make sure that
the ordering of leaf nodes does not cause CARTESIAN PRODUCT operations;
for example, if the two relations with the most restrictive SELECT do not have
a direct join condition between them, it may be desirable to change the order of
leaf nodes to avoid Cartesian products.
Jagdish Bhatta 58
 Outline of a Heuristic Algebraic Optimization Algorithm

 We can now outline the steps of an algorithm that utilizes some of the
above rules to transform an initial query tree into a final tree that is
more efficient to execute (in most cases).
– Step 5: Using Rule 12, combine a CARTESIAN PRODUCT operation with a
subsequent SELECT operation in the tree into a JOIN operation, if the
condition represents a join condition.
– Step 6: Using Rules 3, 4, 7, and 11 concerning the cascading of PROJECT and
the commuting of PROJECT with other operations, break down and move lists
of projection attributes down the tree as far as possible by creating new
PROJECT operations as needed. Only those attributes needed in the query
result and in subsequent operations in the query tree should be kept after each
PROJECT operation.

Jagdish Bhatta 59
 Outline of a Heuristic Algebraic Optimization Algorithm

 We can now outline the steps of an algorithm that utilizes some of the
above rules to transform an initial query tree into a final tree that is
more efficient to execute (in most cases).
– Identify subtrees that represent groups of operations that can be executed by a
single algorithm.

Jagdish Bhatta 60
 Outline of a Heuristic Algebraic Optimization Algorithm

 In the example, Figure 19.2(b) shows the tree in Figure 19.2(a) after
applying steps 1 and 2 of the algorithm;
 Figure 19.2(c) shows the tree after step 3; Figure 19.2(d) after step 4;
and
 Figure 19.2(e) after step 5.
 In step 6, we may group together the operations in the subtree whose
root is the operation πEssn into a single algorithm. We may also group
the remaining operations into another subtree, where the tuples
resulting from the first algorithm replace the subtree whose root is the
operation πEssn , because the first grouping means that this subtree is
executed first.

Jagdish Bhatta 61
 Outline of a Heuristic Algebraic Optimization Algorithm

SELECT [Link]
FROM EMPLOYEE AS E, WORKS_ON AS W, PROJECT AS P
WHERE [Link]=‘Aquarius’ AND [Link] = [Link] AND
[Link]=[Link] AND [Link] > ‘1957-12-31’;

Jagdish Bhatta 62
 Outline of a Heuristic Algebraic Optimization Algorithm

 In the example, Figure 19.2(b) shows the tree in Figure 19.2(a) after
applying steps 1 and 2 of the algorithm;

Jagdish Bhatta 63
 Outline of a Heuristic Algebraic Optimization Algorithm

 Figure 19.2(c) shows the tree after step 3;

Jagdish Bhatta 64
 Outline of a Heuristic Algebraic Optimization Algorithm

 Figure 19.2(d) after step 4;

Jagdish Bhatta 65
 Outline of a Heuristic Algebraic Optimization Algorithm

 Figure 19.2(e) after step 5.

Jagdish Bhatta 66
 Outline of a Heuristic Algebraic Optimization Algorithm

 In step 6, we may group together the operations in the subtree whose

root is the operation πEssn into a single algorithm. We may also group
the remaining operations into another subtree, where the tuples
resulting from the first algorithm replace the subtree whose root is the
operation πEssn , because the first grouping means that this subtree is
executed first.

Jagdish Bhatta 67
 Outline of a Heuristic Algebraic Optimization Algorithm

 The main heuristic is to apply first the operations that reduce the size
of intermediate results.
 This includes performing as early as possible SELECT operations to
reduce the number of tuples and PROJECT operations to reduce the
number of attributes—by moving SELECT and PROJECT operations
as far down the tree as possible.
 Additionally, the SELECT and JOIN operations that are most
restrictive—that is, result in relations with the fewest tuples or with
the smallest absolute size—should be executed before other similar
operations. The latter rule is accomplished through reordering the leaf
nodes of the tree among themselves while avoiding Cartesian
products, and adjusting the rest of the tree appropriately

Jagdish Bhatta 68
 Cost-Based Optimization

 A query optimizer does not depend solely on heuristic rules or query

transformations; it also estimates and compares the costs of executing
a query using different execution strategies and algorithms, and it
then chooses the strategy with the lowest cost estimate. . For this
approach to work, accurate cost estimates are required so that
different strategies can be compared fairly and realistically.
 It uses traditional optimization techniques that search the solution
space to a problem for a solution that minimizes an objective (cost)
function. The cost functions used in query optimization are estimates
and not exact cost functions, so the optimization may select a query
execution strategy that is not the optimal (absolute best) one.

Jagdish Bhatta 69
 Cost-Based Optimization

 Cost-based query optimization is an overall process of choosing the

most efficient means of executing a SQL statement based on overall
cost of the query. The efficient execution is the execution with
minimum cost. To find the cost of query execution plan, the
optimization technique uses database statistics.

Jagdish Bhatta 70
 Cost Components for Query Execution

 Access cost to secondary storage. This is the cost of transferring

(reading and writing) data blocks between secondary disk storage and
main memory buffers. This is also known as disk I/O (input/output)
cost. The cost of searching for records in a disk file depends on the
type of access structures on that file, such as ordering, hashing, and
primary or secondary indexes. In addition, factors such as whether
the file blocks are allocated contiguously on the same disk cylinder or
scattered on the disk affect the access cost.

Jagdish Bhatta 71
 Cost Components for Query Execution

 Disk storage cost. This is the cost of storing on disk any intermediate
files that are generated by an execution strategy for the query.
 Computation cost. This is the cost of performing in-memory
operations on the records within the data buffers during query
execution. Such operations include searching for and sorting records,
merging records for a join or a sort operation, and performing
computations on field values. This is also known as CPU (central
processing unit) cost.

Jagdish Bhatta 72
 Cost Components for Query Execution

 Memory usage cost. This is the cost pertaining to the number of

main memory buffers needed during query execution.
 Communication cost. This is the cost of shipping the query and its
results from the database site to the site or terminal where the query
originated. In distributed databases, it would also include the cost of
transferring tables and results among various computers during query
evaluation.

Jagdish Bhatta 73
 Cost Components for Query Execution

 For large databases, the main emphasis is often on minimizing the

access cost to secondary storage. Simple cost functions ignore other
factors and compare different query execution strategies in terms of
the number of block transfers between disk and main memory
buffers.
 For smaller databases, where most of the data in the files involved in
the query can be completely stored in memory, the emphasis is on
minimizing computation cost.
 In distributed databases, where many sites are involved,
communication cost must be minimized. It is difficult to include all
the cost components in a (weighted) cost function because of the
difficulty of assigning suitable weights to the cost components.
 This is why some cost functions consider a single factor only—disk
access.
Jagdish Bhatta 74
 Cost Based Optimization

 Consider two relations

 employee (emp_no, emp_name, emp_address, position, salary,
branch_no)
 (branch_no, branch_city, branch_address, city) with a member of
employee can only work at one branch.
 Consider an SQL query as given below.
SELECT * FROM Employee, Branch
WHERE Employee.branch_no = Branch.branch_no AND
[Link] = ‘Manager’ AND [Link] = ‘Kathmandu’;

Jagdish Bhatta 75
 Cost Based Optimization

 SELECT * FROM Employee, Branch

WHERE Employee.branch_no = Branch.branch_no AND
[Link] = ‘Manager’ AND [Link] = ‘Kathmandu’;

Jagdish Bhatta 76
 Cost Based Optimization

Jagdish Bhatta 77
 Cost Based Optimization

Jagdish Bhatta 78
 Cost Based Optimization

Jagdish Bhatta 79
 Cost Based Optimization

 Suppose there are 2000 tuples in Employee, 20 tuples in Branch, 20

Managers (one for each branch), and 10 Kathmandu branches.
 To compare these three queries, we assume number of disk accesses.
We also assume that there are no indexes or sort keys on either
relation.
 The results of any intermediate operations are stored on disk.
 The cost of the final write is ignored because it is the same in each
query.
 We further assume that tuples are accessed one at a time (although in
practice disk accesses would be based on blocks, which would
typically contain several tuples), and main memory is large enough to
process entire relations for each relational algebra operation.

Jagdish Bhatta 80
 Cost Based Optimization

 The query1 calculates the Cartesian product of Employee and Branch,

which requires (2000 + 20) disk accesses to read these two relations,
and creates a relation with (2000 × 20) tuples. We then have to read
each of these tuples again to test them against the selection predicate
at a cost of another (2000 × 20) disk accesses, giving a total cost of
(2000 + 20) + 2 × (2000 × 20) = 82020 disk accesses.

Jagdish Bhatta 81
 Cost Based Optimization

 The query 2 joins Employee and Branch which again requires (2000
+ 20) disk accesses to read each of the relations. The Join of these
two relations has 2000 tuples, one for each member of Employee.
Consequently, the Selection operation requires 2000 disk accesses to
read the result of the join, giving a total cost of (2000 + 20) + 2 ×
(2000) = 6020 disk accesses.

Jagdish Bhatta 82
 Cost Based Optimization

 The query 3 first reads each Employee tuple to determine the

Manager tuples, which requires 2000 disk accesses and produces a
relation with 20 tuples. Similarly, the second Selection operation
reads each Branch tuple to determine the Kathmandu branches, which
requires 20 disk accesses and produces a relation with 10 tuples. The
final operation is the join of the reduced Employee and Branch
relations, which requires (20 + 10) disk accesses, giving a total cost
of (2000 + 20) + (20 + 10) + (20 + 10) = 2080 disk accesses.

Jagdish Bhatta 83
 Cost Based Optimization

 From the calculations above, it is clear that query 3 is the most

efficient query and is 2.89 times faster than query 2 and 39.43 times
faster than the query1.

Jagdish Bhatta 84