Module 8.

Query Processing and Optimization

Syllabus:
●​ Overview
●​ Issues in Query Optimization
●​ Steps in Query Processing
●​ System Catalog or Metadata
●​ Query Parsing
●​ Query Optimization
●​ Access Paths
●​ Query Code Generation
●​ Query Execution
●​ Algorithms for Computing Selection and Projection
●​ Algorithms for Computing a Join
●​ Computing Aggregation Functions
●​ Cost Based Query Optimization

Overview
Although a database system provides a high-level view of data, ultimately data have to be
stored as bits on one or more storage devices. A vast majority of databases today store
data on magnetic disk (and, increasingly, on flash storage) and fetch data into main
memory for processing, or copy data onto tapes and other backup devices for archival
storage. The physical characteristics of storage devices play a major role in the way data
are stored, in particular because access to a random piece of data on disk is much slower
than memory access: Disk access takes tens of milliseconds, whereas memory access takes
a tenth of a microsecond.

Disk Access (Slow) Memory Access (Fast)

tens of milliseconds tenth of a microsecond

This module gives overview of physical storage media, including mechanisms to minimize
the chance of data loss due to device failures. Also describes how records are mapped to
files, which in turn are mapped to bits on the disk.

Many queries reference only a small proportion of the records in a file. An index is a
structure that helps locate desired records of a relation quickly, without examining all
records. The index in textbook is an example, although, unlike database indices, it is meant
for human use. This module describes several types of indices used in database systems.

User queries have to be executed on the database contents, which reside on storage
devices. It is usually convenient to break up queries into smaller operations, roughly
corresponding to the relational-algebra operations. This module also describes how queries
are processed, presenting algorithms for implementing individual operations, and then
outlining how the operations are executed in synchrony, to process a query.

There are many alternative ways of processing a query, often called plans, which can have
widely varying costs. Query optimization refers to the process of finding the lowest-cost

1
method of evaluating a given query. This module also describes the process of query
optimization.

Figure: Query Optimizer

In this module we discuss the techniques used internally by a DBMS to process, optimize,
and execute high-level queries.

Steps in 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 steps involved in processing a query appear in Figure. The basic steps are:
1.​ Parsing and translation.
2.​ Optimization.
3.​ Evaluation.

Parsing
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 not suited to be the system’s
internal representation of a query. A more useful internal representation is one based on the
extended relational algebra. 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.

A query expressed in a high-level query language such as SQL must first be scanned,
parsed, and validated.

Scanner Parser Validator

The scanner identifies the Whereas the parser checks The query must also be
query tokens—such as SQL the query syntax to validated by checking that
keywords, attribute names, determine whether it is all attribute and relation
and relation names—that formulated according to the names are valid and
appear in the text of the syntax rules (rules of semantically meaningful
query. grammar) of the query names in the schema of the
language. particular database being
queried.

2
Translation
An internal representation of the query is then created, usually as a tree data structure
called a query tree. It is also possible to represent the query using a graph data structure
called a query graph. The DBMS must then devise an execution strategy or query plan
for retrieving the results of the query from the database files. 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. (Dictionary: Optimization-as effective or functional
as possible). Figure shows the different steps of processing a high-level query.

Evaluation
The query optimizer module has the task of producing a good execution plan, and the
code generator generates the code to execute that plan. The runtime database
processor has the task of running (executing) the query code, whether in compiled or
interpreted mode, to produce the query result. If a runtime error results, an error message
is generated by the runtime database processor.

Figure: Typical steps when processing a high-level query

3
Query-execution plan or query-evaluation plan
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. As an illustration, consider the query:
SELECT salary
FROM instructor
WHERE salary < 75000;
This query can be translated into either of the following relational-algebra expressions:

Further, we can execute each relational-algebra operation by one of several different

algorithms. For example, to implement the preceding selection, we can search every tuple in
instructor to find tuples with salary less than 75000. If a B+-tree index is available on the
attribute salary, we can use the index instead to locate the tuples.

Figure: A query-evaluation plan.

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. Figure illustrates an evaluation plan for our example query, in which a particular index
(denoted in the figure as “index 1”) is specified for the selection operation. The
query-execution engine takes a query-evaluation plan, executes that plan, and returns the
answers to the query.

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.
4
Once the query plan is chosen, the query is evaluated with that plan, and the result of the
query is output.

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.

The term optimization is actually a misleading because in some cases the chosen execution
plan is not the optimal (or absolute best) strategy—it is just a reasonably efficient strategy
for executing the query. Finding the optimal strategy is usually too time-consuming—except
for the simplest of queries. In addition, trying to find the optimal query execution strategy
may require detailed information on how the files are implemented and even on the
contents of the files—information that may not be fully available in the DBMS catalog.
Hence, planning of a good execution strategy may be a more accurate description than
query optimization.

Query Parsing (Translating SQL Queries into Relational Algebra)

The first step in query processing is query parsing. The main role of parser is to check the
query for correct syntax, resolve names and references and translate the query into a
conventional parse tree (query tree) or some other internal representation.

In practice, SQL is the query language that is used in most commercial RDBMSs. An SQL
query is first translated into an equivalent extended relational algebra expression—
represented as a query tree data structure—that is then optimized. Typically, SQL queries
are decomposed into query blocks, which form the basic units that can be translated into
the algebraic operators and optimized.

A query block contains a single SELECT-FROM-WHERE expression, as well as GROUP BY

and HAVING clauses if these are part of the block. Hence, nested queries within a query are
identified as separate query blocks. Because SQL includes aggregate operators—such as
MAX, MIN, SUM, and COUNT—these operators must also be included in the extended
algebra. In addition parser also check if the user is authorised to execute the query or not.

Consider the following SQL query on the EMPLOYEE relation:

SELECT Lname, Fname
FROM EMPLOYEE
WHERE Salary > ( SELECT MAX (Salary)
FROM EMPLOYEE
WHERE Dno=5 );

This query retrieves the names of employees (from any department in the company) who
earn a salary that is greater than the highest salary in department 5. The query includes a
nested subquery and hence would be decomposed into two blocks. The inner block is:
( SELECT MAX (Salary)
FROM EMPLOYEE
WHERE Dno=5 )
5
This retrieves the highest salary in department 5. The outer query block is:
SELECT Lname, Fname
FROM EMPLOYEE
WHERE Salary > c
where c represents the result returned from the inner block. The inner block could be
translated into the following extended relational algebra expression:

GMAX Salary(σDno=5(EMPLOYEE))
and the outer block into the expression:

πLname,Fname(σSalary>c (EMPLOYEE))
The query optimizer would then choose an execution plan for each query block. Notice that
in the above example, the inner block needs to be evaluated only once to produce the
maximum salary of employees in department 5, which is then used—as the constant c—by
the outer [Link] called this a nested query (without correlation with the outer query). It
is much harder to optimize the more complex correlated nested queries, where a tuple
variable from the outer query block appears in the WHERE-clause of the inner query block.

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.

One aspect of optimization occurs at the relational-algebra level, where the system attempts
to find an expression that is equivalent to the given expression, but more efficient to
execute. Another aspect is selecting a detailed strategy for processing the query, such as
choosing the algorithm to use for executing an operation, choosing the specific indices to
use, and so on.

The difference in cost (in terms of evaluation time) between a good strategy and a bad
strategy is often substantial, and may be several orders of magnitude. Hence, it is
worthwhile for the system to spend a substantial amount of time on the selection of a good
strategy for processing a query, even if the query is executed only once.

Once the query parser validates the query, the query in its internal format, possibly
represented as a query-tree, is passed to the query optimizer. The query optimization
module may carry out some transformation of the internal representation received from the
parser.

The optimizer is then invoked with the internal representation of the query as input so that
a query plan or execution plan may be devised for retrieving the information that is
required. The optimizer carries out a number of operations. It relates the symbolic names in
the query to database objects and checks their existence. Since current DBMS software is
designed to run on many different platforms, it is necessary that the query plan be
represented in a form that can easily be translated to each computer's internal instructions.

6
As noted earlier, the query optimizer is a very important component of a DBMS because the
efficiency of the system depends lot on the performance of the optimizer. Before query
optimization is carried out one needs to decide what is to be optimized. The goal of
achieving efficiency itself may be different in different situations. For example, one may
wish to minimize the processing time but in many situations one would wish to minimize the
response time. In other situations, one may wish to minimize the I/O. network time,
memory used or some combination of these, for example total resources used.

Generally, a query processing algorithm A will be considered more efficient than an

algorithm B if the measure of cost being minimized for processing the same query, given the
same resources using A, is generally less than that for B.

There are two main techniques that are employed during query optimization.
1.​ The first technique is based on heuristic rules for ordering the operations in a query
execution strategy. A heuristic is a rule that works well in most cases but is not
guaranteed to work well in every case. The rules typically reorder the operations in a
query tree.
2.​ The second technique involves systematically estimating the cost of different
execution strategies and choosing the execution plan with the lowest cost estimate.
These techniques are usually combined in a query optimizer.

Using Heuristics in Query Optimization

In this section we discuss optimization techniques that apply heuristic rules to modify the
internal representation of a query—which is usually in the form of a query tree or a query
graph data structure—to improve its expected performance. The scanner and parser of an
SQL query first generate a data structure that corresponds to an initial query
representation, which is then optimized according to heuristic rules. This leads to an
optimized query representation, which corresponds to the query execution strategy.
Following that, a query execution plan is generated to execute groups of operations based
on the access paths available on the files involved in the query.

One of the main heuristic rules is to apply SELECT and PROJECT operations before
applying the JOIN or other binary operations, because the size of the file resulting from a
binary operation—such as JOIN—is usually a multiplicative function of the sizes of the input
files. The SELECT and PROJECT operations reduce the size of a file and hence should be
applied before a join or other binary operation.

Notation for Query Trees and Query Graphs

A query tree is 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.

leaf node relation

internal node relational algebra operation

An execution of the query tree consists of executing an internal node operation whenever its

7
operands (child nodes) 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.

figure: query tree

Figure shows a query tree for query Q2:
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’;

For every project located in ‘Stafford’, retrieve the project number, the controlling
department number, and the department manager’s last name, address, and birthdate. This
query is specified on the COMPANY relational schema and corresponds to the following
relational algebra expression:

In Figure, the leaf nodes P, D, and E represent the three relations PROJECT, DEPARTMENT,
and EMPLOYEE, respectively, and the internal tree nodes represent the relational algebra
operations of the expression. When this query tree is executed, the node marked (1) in
must begin execution before node (2) because some resulting tuples of operation (1) must
be available before we can begin executing operation (2). Similarly, node (2) must begin
executing and producing results before node (3) can start execution, and so on.

As we can see, the query tree represents a specific order of operations for executing a

8
query. A more neutral data structure for representation of a query is the query graph
notation. Figure below shows the query graph for above query.

Figure: query graph

Relations in the query are represented by relation nodes, which are displayed as single
circles. Constant values, typically from the query selection conditions, are represented by
constant nodes, which are displayed as double circles or ovals. Selection and join
conditions are represented by the graph edges. Finally, the attributes to be retrieved from
each relation are displayed in square brackets above each relation.

The query graph representation does not indicate an order on which operations to perform
first. There is only a single graph corresponding to each query. Although some optimization
techniques were based on query graphs, it is now generally accepted that query trees are
preferable because, in practice, the query optimizer needs to show the order of operations
for query execution, which is not possible in query graphs.

Heuristic Optimization of Query Trees

In general, many different relational algebra expressions—and hence many different query
trees—can be equivalent; that is, they can represent the same query.

Figure: initial query tree

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 SELECT-PROJECT- JOIN
query, such as Q2, the initial tree is shown Figure. 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.

9
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, the initial query tree in Figure 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.

The optimizer must include rules for equivalence among relational algebra expressions that
can be applied to transform the initial tree into the final, optimized query tree. First we
discuss informally how a query tree is transformed by using heuristics, and then we discuss
general transformation rules and show how they can be used in an algebraic heuristic
optimizer.

Example of Transforming a Query. Consider the following query Q: 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:
SELECT Lname
FROM EMPLOYEE, WORKS_ON, PROJECT
WHERE Pname=‘Aquarius’ AND Pnumber=Pno AND Essn=Ssn
AND Bdate > ‘1957-12-31’;
The initial query tree for Q is shown below.

Figure A: initial query tree

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 B below shows an improved query tree that first applies the SELECT
operations to reduce the number of tuples that appear in the CARTESIAN PRODUCT.

A further improvement is achieved by switching the positions of the EMPLOYEE and

PROJECT relations in the tree, as shown in Figure C. This uses the information that Pnumber
is a key attribute of the PROJECT relation, and hence the SELECT operation on the PROJECT
relation will retrieve a single record [Link] can further improve the query tree by replacing

10
any CARTESIAN PRODUCT operation that is followed by a join condition with a JOIN
operation, as shown in Figure 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 E. This reduces the attributes
(columns) of the intermediate relations, whereas the SELECT operations reduce the number
of tuples (records).

Figure B: Moving SELECT operations down Figure C: Applying the more restrictive
the query tree. SELECT operation first.

Figure D: Replacing CARTESIAN PRODUCT Figure E: Moving PROJECT operations down

and SELECT with JOIN operations. the query tree.

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. We discuss
some of these transformation rules next.

General Transformation Rules for Relational Algebra Operations

There are many rules for transforming relational algebra operations into equivalent ones.

11
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. In Section 3.1.2 we gave an alternative definition of relation that makes the
order of attributes unimportant; we will use this definition [Link] will state some
transformation rules that are useful in query optimization, without proving them:

1 Cascade of σ A conjunctive selection condition can be broken up into a cascade

(that is, a sequence) of individual σ operations:

2 Commutativity The σ operation is commutative:

of σ.

3 Cascade of π. In a cascade (sequence) of π operations, all but the last one can
be ignored:

4 Commuting σ If the selection condition c involves only those attributes

with π. A1, . . . , An in the projection list, the two operations can be
commuted:

5 Commutativity The join operation is commutative, as is the × operation:

of (⋈ and ×).

Notice that although the order of attributes may not be the same in
the relations resulting from the two joins (or two Cartesian
products), the meaning is the same because the order of attributes
is not important in the alternative definition of relation.

Algorithms for External Sorting

Sorting is one of the primary algorithms used in query processing. For example, whenever

12
an SQL query specifies an ORDER BY-clause, the query result must be sorted. Sorting is also
a key component in sort-merge algorithms used for JOIN and other operations (such as
UNION and INTERSECTION), and in duplicate elimination algorithms for the PROJECT
operation (when an SQL query specifies the DISTINCT option in the SELECT clause). We will
discuss one of these algorithms in this section. Note that sorting of a particular file may be
avoided if an appropriate index— such as a primary or clustering index —exists on the
desired file attribute to allow ordered access to the records of the file.

13
14
Issues in query optimization
A SQL query can be processed in a number of different ways, often called plans, where each
plan might have different sequence of operations. If query is complex a very large number
of alternative plans are possible. Often then it is necessary to consider a small number of
possible plans and select the best option from those. Even the difference between cost of
implementing these plans is quite large. It is the responsibility of the DBMS to find an
efficient execution plan. A user may express a query in any of the different possible forms
but one expects that the DBMS will execute the query efficiently.

System Catalog or Metadata

An important part of the optimizer is the component that consults the metadata stored in
the database to obtain statistics about the referenced tables and the access paths available
on them. These are used to determine the most efficient order of the relational operations
and the most efficient access paths. The order of operations and the access paths are
selected from a number of alternative possibilities that normally exist so that the cost of
query processing is minimized.

Metadata or system catalog includes information about how data is stored in the computer
storage. The following information is often available in the catalog:
●​ For each table: The name of each table, the name of the file it is stored in, the data
structure used for storing it, all its attributes and their domains. Information about
the primary key and foreign keys, if any. The number of pages or blocks a table
occupies on the disk is also included in catalog.
●​ For each view: The names of the view and its definition.
●​ For each index: The name of the index, description of its storage structure, the size
of the index in terms of the number of blocks on the disk.
●​ Security: Information about ownership of the database and various tables, views,
indexes etc.
●​ Histograms: Some DBMS als stores histograms of ranges of attribute valus of varouis
tables in the database. This information can help in making better estimates of the
sizes of relational operations and thus the cost of query processing
Often the statistics are updated only periodically and not at every update/insert/delete. Also
the system catalog is often stored as a relational database itself, making it easy to query it
if a user is authorised to do so.

Information in the catalog is very important since query processing makes use of this
information extensively.

Cost Based Query Optimization

A query optimizer does not depend solely on heuristic rules; 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. In addition, the optimizer must limit the number of execution strategies to be
considered; otherwise, too much time will be spent making cost estimates for the many
possible execution strategies. Hence, this approach is more suitable for compiled queries
15
where the optimization is done at compile time and the resulting execution strategy code is
stored and executed directly at runtime. For interpreted queries, where the entire process
occurs at runtime, a full-scale optimization may slow down the response time. A more
elaborate optimization is indicated for compiled queries, whereas a partial, less
time-consuming optimization works best for interpreted queries.

This approach is generally referred to as cost-based query optimization. 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.

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. Moreover, CPU
speeds have been improving much faster than have disk speeds. Thus, it is likely that the
time spent in disk activity will continue to dominate the total time to execute a query. The
CPU time taken for a task is harder to estimate since it depends on low-level details of the
execution code. Although real-life query optimizers do take CPU costs into account, for
simplicity in this book we ignore CPU costs and use only disk-access costs to measure the
cost of a query-evaluation plan.

We use the number of block transfers from disk and the number of disk seeks 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.

We can refine our 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). For
simplicity, we ignore this detail, and leave it to you to work out more precise cost estimates
for various operations.

The cost estimates we give do not include the cost of writing the final result of an operation
back to disk. These are taken into account separately where required. The costs of all the
16
algorithms that we consider depend on the size of the buffer in main memory. In the best
case, all data can be read into the buffers, and the disk does not need to be accessed again.
In the worst case, we assume that the buffer can hold only a few blocks of
data—approximately one block per relation.
When presenting cost estimates, we generally assume the worst case.

In addition, although we assume that data must be read from disk initially, it is possible that
a block that is accessed is already present in the in-memory buffer. Again, for simplicity, we
ignore this effect; as a result, the actual disk-access cost during the execution of a plan may
be less than the estimated 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:
1.​ 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.
2.​ 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.

Interestingly, a plan may get a better response time at the cost of extra resource
consumption. For example, if a system has multiple disks, a plan A that requires extra disk
reads, but performs the reads in parallel across multiple disks may finish faster than
another plan B that has fewer disk reads, but from only one disk. However, if many
instances of a query using plan A run concurrently, the overall response time may actually
be more than if the same instances are executed using plan B, since plan A generates more
load on the disks.

As a result, instead of trying to minimize the response time, optimizers generally try to
minimize the total resource consumption of a query plan. Our model of estimating the
total disk access time (including seek and data transfer) is an example of such a resource
consumption–based model of query cost.

17
Query tree Examples:

SELECT Fname, Lname, Address

FROM EMPLOYEE, DEPARTMENT
WHERE Dname=‘Research’ AND Dnumber=Dno;

initial query tree optimized query tree

18