Chapter One
Query Processing and
Optimization
Query Processing
There are different techniques used internally by a
DBMS to process high-level queries.
A query expressed in a high-level query language
such as SQL must first be scanned, parsed, and
validated.
Scanner: identifies the query tokens such as SQL
Keywords, attribute names, and relation names in
the text of the query.
Parser: checks the query syntax to determine
whether it is formulated according to the syntax
rules of the query language.
Cont…
Validation: The query must be validated by
checking that all attributes and relation names
are valid and semantically meaningful names in
the schema of the particular database being
queried.
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, which
is generally a directed acyclic graph (DAG).
The DBMS must then devise an execution
strategy or query plan for retrieving the results of
the query from the database files.
Cont…
Query Optimization: The process of choosing a
suitable execution strategy for processing a query.
◦ This module has the task of producing a good
execution plan.
Query Code Generator: generates the code to
execute the plan.
Runtime Database Processor: has the task of
running 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
Steps of Processing a High-Level
Query
Translating SQL Queries into
Relational Algebra
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 clause if these are part of the block.
Nested queries within a query are identified as
separate query blocks.
Example
– Inner
block
– Outer
block
Algorithms in Query
Processing
1) Brute Force Algorithm
Retrieve every record in the file.
Since the records are grouped into disk blocks, each
disk block is read into a main memory buffer;
Then a search through the records within the disk
block is conducted in main memory.
Used for SELECT operation to test whether its attribute
values satisfy the selection condition.
Called also as, Linear search when used for SELECT
operations.
Used for JOIN operation to test whether the two
records satisfy the join condition.
For disk files, it is obvious that the loops will be over
disk blocks, so this technique has also been called
2) External Sorting
Sorting is an often-used algorithm in query
processing
For example, whenever an SQL query specifies an
ORDER BY-clause, the query result must be
sorted.
External sorting refers to sorting algorithms
suitable for large files that do not fit entirely in
main memory.
Internal sorting algorithms are suitable for sorting
data structures, such as tables and lists, that can
fit entirely in main memory and include
techniques such as quick sort, heap sort, bubble
sort, and many others.
Cont ..
Typical external sorting algorithm uses a sort-
merge strategy, which starts by sorting small
subfiles—called runs—of the main file and then
merges the sorted runs, creating larger sorted
subfiles that are merged in turn.
The sort-merge algorithm, like other database
algorithms, requires buffer space in main
memory, where the actual sorting and merging of
the runs is performed.
The buffer space in main memory is part of the
DBMS cache—an area in the computer’s main
memory that is controlled by the DBMS.
Cont ..
The buffer space is divided into individual buffers,
where each buffer is the same size in bytes as the
size of one disk block.
Thus, one buffer can hold the contents of exactly
one disk block.
In the sorting phase, runs (portions or pieces) of
the file that can fit in the available buffer space are
read into main memory, sorted using an internal
sorting algorithm, and written back to disk as
temporary sorted subfiles (or runs).
The size of each run and the number of initial runs
(nR) are dictated by the number of file blocks (b) and
the available buffer space (nB).
For example, if the number of available main
Cont ..
Hence, after the sorting phase, 205 sorted runs (or
205 sorted subfiles of the original file) are stored as
temporary subfiles on disk.
The following figure shows how runs are sorted
between the disk and memory:
Cont ..
In the merging phase, the sorted runs are
merged during one or more merge passes.
Each merge pass can have one or more merge
steps.
The degree of merging (dM) is the number of
sorted subfiles that can be merged in each merge
step.
During each merge step, one buffer block is
needed to hold one disk block from each of the
sorted subfiles being merged, and one additional
buffer is needed for containing one disk block of
the merge result, which will produce a larger
sorted file that is the result of merging several
smaller sorted subfiles.
Cont ..
Thefollowing figure shows 12 items, sorted and
merged by assuming the degree of merging as 2,
which takes two merge passes:
Cont ..
In our example, where nB = 5, dM = 4 (four-way
merging):
◦ The 205 initial sorted runs would be merged 4 at
a time in each step into 52 larger sorted subfiles
at the end of the first merge pass.
◦ These 52 sorted files are then merged 4 at a time
into 13 sorted files,which are then
◦ Merged into 4 sorted files, and then
◦ Finally into 1 fully sorted file
Which means that four passes are needed.
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
3) Hashing Techniques
Hashing, provides very fast access to records
under certain search conditions.
This organization is usually called a hash file (also
called direct file.
The search condition must be an equality
condition on a single field, called the hash field.
In most cases, the hash field is also a key field of
the file, in which case it is called the hash key.
The idea behind hashing is to provide a function
h, called a hash function or randomizing function,
which is applied to the hash field value of a record
and yields the address of the disk block in which
the record is stored.
Cont ..
For Example, suppose we squeeze numbers in the
range 0 to 199 into the range 0 to 9.
The remainders when any number is divided by 10
are always in the range 0 to 9; this is shown in the
next figure.
We’ve squeezed the range 0–199 into the range 0–9,
a 20-to-1 compression ratio.
This is an example of a hash function.
It hashes (converts) a number in a large range into a
number in a smaller range.
Cont ..
Cont ..
A search for the record within the block can be
carried out in a main memory buffer.
For most records, we need only a single-block access
to retrieve that record.
Hashing is also used as an internal search structure
within a program whenever a group of records is
accessed exclusively by using the value of one field.
For internal files, hashing is typically implemented as
a hash table through the use of an array of records.
Hashing for disk files is called external hashing.
To suit the characteristics of disk storage, the target
address space is made of buckets, each of which
holds multiple records.
A bucket is either one disk block or a cluster of
Cont ..
The hashing function maps a key into a relative
bucket number.
Hashing provides the fastest possible access for
retrieving an arbitrary record given the value of its
hash field.
Many hashing functions can be used.
One technique, called folding, involves applying an
arithmetic function such as addition or a logical
function such as exclusive or to different portions of
the hash field value to calculate the hash address.
For example, with an address space from 0 to 999 to
store 1,000 keys, a 6-digit key 235469 may be
folded and stored at the address: (235+964) mod
1000 = 199.
Cont ..
Another technique involves picking some digits of
the hash field value—for instance, the third, fifth,
and eighth digits—to form the hash address.
For example, storing 1,000 employees with Social
Security numbers of 10 digits into a hash file with
1,000 positions would give the Social Security
number 301-67-8923 a hash value of 172 by this
hash function).
Noninteger hash field values can be transformed
into integers before the hash function is applied.
For character strings, the numeric (ASCII) codes
associated with characters can be used in the
transformation.
Cont ..
Hashing is used for SELECT operations to retrieve a
record, if the selection condition involves an
equality comparison on a key attribute with a hash
key. (Eg. s SSN='123456789' (EMPLOYEE))
Hashing is used for PROJECT operations to eliminate
duplicates: as each record is hashed and inserted
into a bucket of the hash file in memory, it is
checked against those records already in the
bucket; if it is a duplicate, it is not inserted in the
bucket.
When hashing is used for JOIN operations, it is
called Partition-hash join (or just hash-join),
which partitions the records of the files to be joined
into smaller files.
Cont ..
First, a single pass through the file with fewer
records hashes its records to the various partitions.
This is called the partitioning phase, since the
records of R are partitioned into the hash buckets.
The collection of records with the same value of h
are placed in the same partition, which is a hash
bucket in a hash table.
In the second phase, called the probing phase, a
single pass through the other file then hashes each
of its records using the same hash function h to
probe the appropriate bucket, and that record is
combined with all matching records from previous
file in that bucket.
4) Indexing Structures
Indexes are used to speed up the retrieval of records
in response to certain search conditions.
The index structures are additional files on disk that
provide secondary access paths, which provide
alternative ways to access the records without
affecting the physical placement of records in the
primary data file on disk.
They enable efficient access to records based on the
indexing fields that are used to construct the index.
Basically, any field of the file can be used to create
an index, and multiple indexes on different fields—as
well as indexes on multiple fields—can be
constructed on the same file.
A variety of indexes are possible; each of them uses
Cont ..
To find a record or records in the data file based on a
search condition on an indexing field, the index is
searched, which leads to pointers to one or more
disk blocks in the data file where the required
records are located.
The most prevalent types of indexes are based on
ordered files (single-level indexes) and use tree data
structures (multilevel indexes, B+-trees) to organize
the index.
There are different types of single-level ordered
indexes—primary, secondary, and clustering
B+-trees have become a commonly accepted default
structure for generating indexes on demand in most
relational DBMSs.
Indexes can also be constructed based on hashing or
Cont ..
The idea behind an ordered index is similar to that
behind the index used in a textbook, which lists
important terms at the end of the book in
alphabetical order along with a list of page numbers
where the term appears in the book.
We can search the book index for a certain term in
the textbook to find a list of addresses—page
numbers in this case—and use these addresses to
locate the specified pages first and then search for
the term on each specified page.
The alternative, if no other guidance is given, would
be to sift slowly through the whole textbook word by
word to find the term we are interested in; this
corresponds to doing a linear search, which scans
the whole file.
Cont ..
However, the index is the only exact indication of
the pages where each term occurs in the book.
For a file with a given record structure consisting of
several fields (or attributes), an index access
structure is usually defined on a single field of a file,
called an indexing field (or indexing attribute).
The index typically stores each value of the index
field along with a list of pointers to all disk blocks
that contain records with that field value.
The values in the index are ordered so that we can
do a binary search on the index.
There are several types of ordered indexes, such as
primary index and clustering index.
A primary index is specified on the ordering key
field of an ordered file of records. (an ordering key
field is used to physically order the file records on
Cont ..
A primary index is an ordered file whose records are
of fixed length with two fields.
The first field is of the same data type as the
ordering key field—called the primary key—of the
data file.
The second field is a pointer to a disk block (a block
address).
There is one index entry (or index record) in the
index file for each block in the data file.
Each index entry has the value of the primary key
field for the first record in a block and a pointer to
that block as its two field values.
We will refer to the two field values of index entry i
as <K(i), P(i)>.
Cont ..
The total number of entries in the index is the same
as the number of disk blocks in the ordered data file.
The first record in each block of the data file is called
the anchor record of the block, or simply the block
anchor.
We can also use the last record in each block as the
block anchor, which slightly improves the efficiency
of the search algorithm.
Indexes can also be characterized as dense or
sparse.
A dense index has an index entry for every search
key value (and hence every record) in the data file.
A sparse (or nondense) index, on the other hand,
has index entries for only some of the search values.
Thus, a primary index is a nondense (sparse) index,
Cont ..
The index file for a primary index occupies a much
smaller space than does the data file, for two
reasons.
First, there are fewer index entries than there are
records in the data file.
Second, each index entry is typically smaller in size
than a data record because it has only two fields,
both of which tend to be short in size.
If the ordering field is not a key field—that is, if
numerous records in the file can have the same
value for the ordering field— another type of index,
called a clustering index, can be used.
So, if file records are physically ordered on a nonkey
field—which does not have a distinct value for each
record—that field is called the clustering field and
Cont ..
A clustering index is also an ordered file with two
fields;
The first field is of the same type as the clustering
field of the data file and
The second field is a disk block pointer.
There is one entry in the clustering index for each
distinct value of the clustering field and
It contains also the value and a pointer to the first
block in the data file that has a record with that
value for its clustering field.
A clustering index is another example of a nondense
index because it has an entry for every distinct value
of the indexing field, which is a nonkey by definition
and hence has duplicate values rather than a unique
Cont ..
Primary index is used for SELECT operations to
retrieve a record, if the selection condition involves
an equality comparison on a key attribute with a
primary index.
Primary index is used for SELECT operations to
retrieve multiple records, if the comparison condition
is >, >=, <, or <= on a key field with a primary
index.
For example, for Dnumber > 5 in s
DNUMBER>5(DEPARTMENT)
We can use the index to find the record satisfying the
corresponding equality condition (Dnumber = 5);
Then retrieve all subsequent records in the (ordered)
file.
For the condition Dnumber < 5, retrieve all the
Cont ..
When indexing is used for JOIN operations it is called
Index-based nested-loop join.
Indexing is used also for the aggregate operators
(MIN, MAX, COUNT, AVERAGE, SUM), applied to an
entire table.
Query Optimization
The goal of query optimization is to select the best
possible strategy for query evaluation.
The term optimization is a misnomer because the
chosen execution plan may not always be the most
optimal plan possible.
The primary goal is to arrive at the most efficient and
cost-effective plan using the available information
about the schema and the content of relations
involved, and to do so in a reasonable amount of
time.
Thus a proper way to describe query optimization
would be that it is an activity conducted by a query
optimizer in a DBMS to select the best available
strategy for executing the query.
Query Trees and Heuristics
Optimization techniques that apply heuristic rules to
modify the internal representation of a query are
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.
Cont ..
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.
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
Cont ..
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.
Let us see a query example ,which is specified on
the COMPANY relational schema.
Cont ..
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 can be specified in SQL as:
The corresponding relational algebra expression is:
Cont ..
Querytree corresponding to the relational algebra
expression is:
Cont ..
In the figure, the leaf nodes P, D, and E represent
the three relations PROJECT, DEPARTMENT, and
EMPLOYEE, respectively.
The internal tree nodes represent the relational
algebra operations of the expression.
When this query tree is executed, the node marked
(1) in the figure 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.
Cont ..
Consider another query example ,which is specified
on the COMPANY relational schema.
Find the last names of employees born after 1957
who work on a project named ‘Aquarius’.
This query can be specified in SQL as:
Thequery tree can be converted step by step during
heuristic optimization.
Cont ..
The following figure shows the query tree that first
applies the SELECT operations to reduce the number
of tuples that appear in the CARTESIAN PRODUCT.
Cont ..
The following figure shows an improved query tree by
switching the positions of the EMPLOYEE and PROJECT
relations in the tree, which applys the more restrictive
SELECT operation first.
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 only.
Cont ..
Wecan 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 the figure below.
Cont ..
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.
This reduces the attributes (columns) of the
intermediate relations, whereas the SELECT
operations reduce the number of tuples (records).
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.
It then chooses the strategy with the lowest cost
estimate.
This approach is generally referred to as cost-based
query optimization.
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.
Cont ..
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.
Cost Components for Query Execution
1. 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
Cont ..
Inaddition, factors such as whether the file blocks
are allocated contiguously on the same disk cylinder
or scattered on the disk affect the access cost.
2. Disk storage cost
This is the cost of storing on disk any intermediate
files that are generated by an execution strategy for
the query.
3. 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
Cont ..
4. Memory usage cost
This
is the cost pertaining to the number of main
memory buffers needed during query execution.
5. 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.
Cont ..
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.
Catalog Information Used in
Cost Functions
To estimate the costs of various execution strategies,
we must keep track of any information that is needed
for the cost functions.
This information may be stored in the DBMS catalog,
where it is accessed by the query optimizer.
A typical RDBMS catalog contains the following types
of information:
◦ Number of rows/records
◦ “Width” of the relation (the length of each tuple in
the relation)
◦ Number of blocks that relation occupies in storage
◦ Blocking factor, which is the number of tuples per
block
Catalog Information Used in
Cost Functions
◦ Primary file organization for each file.
The primary file organization records may be
unordered, ordered by an attribute with or without
a primary or clustering index, or hashed (static
hashing or one of the dynamic hashing methods)
on a key attribute.
◦ Selectivity, which is the fraction of records satisfying
an equality condition on an attribute
Information such as the number of index levels is easy
to maintain because it does not change very often.
However, number of records in a file changes every
time a record is inserted or deleted.
The query optimizer will need reasonably close but not
necessarily completely up-to-the-minute values of
Semantic Query Optimization
This technique, which may be used in combination with
the techniques discussed previously, uses constraints
specified on the database schema—such as unique
attributes and other more complex constraints—to
modify one query into another query that is more
efficient to execute.
Consider a query that retrieves the names of
employees who earn more than their supervisors.
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 does not need to
execute the query because it knows that the result of
Cont ..
There can also be query transformations, by removing
some relations from the query and thus avoiding inner
joins, based on the primary-key/foreign-key
relationship semantics, which are a constraint between
two relations.
This may save considerable time if the constraint
checking can be done efficiently.
However, searching through many constraints to find
those that are applicable to a given query and that
may semantically optimize it can also be time-
consuming.
With the inclusion of active rules and additional
metadata in database systems, semantic query
optimization techniques are being gradually