Introduction to Query Optimization

 Query optimization is a difficult part of the query processing.

 It determines the efficient way to execute a query with different possible query plans.
 It cannot be accessed directly by users once the queries are submitted to the database
server or parsed by the parser.
 A query is passed to the query optimizer where optimization occurs.
 Main aim of Query Optimization is to minimize the cost function,
I/O Cost + CPU Cost + Communication Cost
 It defines how an RDBMS can improve the performance of the query by re-ordering the
operations.
 It is the process of selecting the most efficient query evaluation plan from among various
strategies if the query is complex.
 It computes the same result as per the given expression, but it is a least costly way of
generating result.

Importance of Query Optimization

 Query optimization provides faster query processing.
 It requires less cost per query.

 It gives less stress to the database.

 It provides high performance of the system.
 It consumes less memory.

Query Processing
 Query Processing includes translations on high level Queries into low level expressions
that can be used at physical level of file system, query optimization and actual execution
of query to get the actual result.
 Block Diagram of Query Processing is as:
 

Detailed Diagram is drawn as:

t is done in the following steps:

 Step-1:
Parser: During parse call, the database performs the following checks- Syntax check,
Semantic check and Shared pool check, after converting the query into relational algebra.

Parser performs the following checks as (refer detailed diagram):

1. Syntax check – concludes SQL syntactic validity. Example:

SELECT * FORM employee

 Here error of wrong spelling of FROM is given by this check.

2. Semantic check – determines whether the statement is meaningful or not.

Example: query contains a tablename which does not exist is checked by this
check.
3. Shared Pool check – Every query possess a hash code during its execution. So,
this check determines existence of written hash code in shared pool if code exists
in shared pool then database will not take additional steps for optimization and
execution. SELECT * FROM v$sgastat WHERE name = 'free memory';
 Step-2:
Optimizer: During optimization stage, database must perform a hard parse atleast for
one unique DML statement and perform optimization during this parse. This database
never optimizes DDL unless it includes a DML component such as subquery that require
optimization.

It is a process in which multiple query execution plan for satisfying a query are examined
and most efficient query plan is satisfied for execution.
Database catalog stores the execution plans and then optimizer passes the lowest cost
plan for execution.

Row Source Generation –

The Row Source Generation is a software that receives a optimal execution plan from the
optimizer and produces an iterative execution plan that is usable by the rest of the
database. the iterative plan is the binary program that when executes by the sql engine
produces the result set.

 Step-3:
Execution Engine: Finally runs the query and display the required result


QUERY EVALUATION PLAN

A query evaluation plan (Oracle calls it an “execution plan”) is a program for an abstract
machine (interpreter) inside the DBMS. It is produced by the query [Link] name
is “access plan” (the DBMS has to decide how to access the rows, e.g. whether to use an
index).

In most systems, query evaluation plans (QEPs) are similarto relational algebra expressions
(very system dependent).
•
E.g. consider the following SQL query:
SELECT ENAME, DNAME
FROM EMP, DEPT
WHERE [Link] = [Link] AND JOB = ’MANAGER’
In relational algebra, the example query would be written as:
Complex relational algebra expressions are best displayed as
“operator trees” (showing the flow of data):
SQL Anywhere supports a variety of different join implementations that the query optimizer
chooses from. Each of the join algorithms has specific characteristics that make it more or less
suitable for a given query and a given execution environment.

The order of the joins in an access plan may or may not correspond to the ordering of the joins in
the original SQL statement; the query optimizer is responsible for choosing the best join strategy
for each query based on the lowest execution cost. In some situations, query rewrite
optimizations may be utilized for complex statements that either increase, or decrease, the
number of joins computed for any particular statement.

There are three classes of join algorithms supported by SQL Anywhere, though each of them has
additional variants:

 Nested Loops Join The most straightforward algorithm is Nested Loops Join. For each
row on the left-hand side, the right-hand side is scanned for a match based on the join
condition. Ordinarily, rows on the right-hand side are accessed through an index to reduce
the overall execution cost. This scenario is frequently referred to as an Index Nested Loops
Join.

Nested Loops Join has variants that support LEFT OUTER and FULL OUTER joins. A
nested loops implementation can also be used for semijoins (most often used for processing
EXISTS subqueries).

A Nested Loops Join can be utilized no matter what the characteristics of the join condition,
although a join over inequality conditions can be very inefficient to compute.

A Nested Loops FULL OUTER join is very expensive to execute over inputs of any size, and
is only chosen by the query optimizer as a last resort when no other join algorithm is
possible.
 Merge Join A Merge Join relies on its two inputs being sorted on the join attributes.
The join condition must contain at least one equality predicate in order for this method to be
chosen by the query optimizer. The basic algorithm is a straightforward merge of the two
inputs: when the values of the two join attributes differ, the algorithm scrolls to the next row
of the left or right-hand side, depending on which side has the lower of the two values.
Backtracking may be necessary when there is more than one match.

There are Merge Join variants to support LEFT OUTER and FULL OUTER joins. Merge

Join for FULL OUTER Joins is considerably more efficient than its nested loops counterpart.

The basic Merge Join algorithm is also used to support the SQL set operators EXCEPT and
INTERSECT, although these variants are explicitly named as EXCEPT or INTERSECT
algorithms within an access plan.
 Hash Join A Hash Join is the most versatile join method supported by the SQL
Anywhere database server. The Hash Join algorithm builds an in-memory hash table of the
smaller of its two inputs, and then reads the larger input and probes the in-memory hash table
to find matches.

Hash Join variants exist to support LEFT OUTER join, FULL OUTER join, semijoin, and
anti-semijoin. In addition, SQL Anywhere supports hash join variants for recursive INNER
and LEFT OUTER joins when a recursive UNION query expression is being used.

The Hash Inner Join, Left Outer Join, Semijoin, and Antisemijoin algorithms can be executed
in parallel.

If the in-memory hash table constructed by the algorithm does not fit into available memory,
the Hash Join algorithm splits the input into partitions (possibly recursively for very large
inputs) and performs the join on each partition independently. If there is not enough cache
memory to hold all the rows that have a particular value of the join attributes, then, if
possible, each Hash Join dynamically switches to an index-based nested loops strategy after
first discarding the interim results to avoid exhausting the statement's memory consumption
quota.

Variants of Hash Join are also utilized to support the SQL query expressions EXCEPT and
INTERSECT, although these variants are explicitly named as EXCEPT or INTERSECT
algorithms within an access plan.

For example, suppose there are two tuples a and b where both of them satisfy the join condition.
It means they have the same value for the join attributes. Suppose that both a and b tuples consist
of a hash value as i. It implies that tuple a should be in a i, and tuple b should be in b i. Thus, we
only compare a tuples in ai with b tuples of bi. We do not need to compare the b tuples in any
other partition. Therefore, in this way, the hash join operation works.

Cost-Based Optimization
A query optimizer is a part of the relational database software which is meant to analyze a SQL
query and then figure out what the best to run that query. That is why it is called a query
optimizer, because it’s goal is to optimize the query for the sake of efficiency.

A cost based optimizer will look at all of the possible ways or scenarios in which a query can be
executed – and each scenario will be assigned a ‘cost’, which indicates how efficiently that query
can be run. Then, the cost based optimizer will pick the scenario that has the least cost and
execute the query using that scenario, because that is the most efficient way to run the query.

The cost is an internal numeric measure that represents the estimated resource usage for a plan.
The cost is specific to a query in an optimizer environment. To estimate cost, the optimizer
considers factors such as the following:

 System resources, which includes estimated I/O, CPU, and memory

 Estimated number of rows returned (cardinality)
  Size of the initial data sets
 Distribution of the data
 Access structures

The execution time is a function of the cost, but cost does not equate directly to time. For
example, if the plan for query A has a lower cost than the plan for query B, then the following
outcomes are possible:

 A executes faster than B.

 A executes slower than B.
 A executes in the same amount of time as B.

Therefore, you cannot compare the costs of different queries with one another. Also, you cannot
compare the costs of semantically equivalent queries that use different optimizer modes.

Example 4-2 Cost in a Sample Execution Plan

The execution plan displays the cost of the entire plan, which is indicated on line 0, and each
individual operation. For example, the following plan shows an overall cost of 14.

EXPLAINED SQL STATEMENT:

------------------------
SELECT prod_category, AVG(amount_sold) FROM sales s, products p WHERE
p.prod_id = s.prod_id GROUP BY prod_category

Plan hash value: 4073170114

----------------------------------------------------------------------
| Id | Operation | Name | Cost (%CPU)|
----------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 14 (100)|
| 1 | HASH GROUP BY | | 14 (22)|
| 2 | HASH JOIN | | 13 (16)|
| 3 | VIEW | index$_join$_002 | 7 (15)|
| 4 | HASH JOIN | | |
| 5 | INDEX FAST FULL SCAN| PRODUCTS_PK | 4 (0)|
| 6 | INDEX FAST FULL SCAN| PRODUCTS_PROD_CAT_IX | 4 (0)|
| 7 | PARTITION RANGE ALL | | 5 (0)|
| 8 | TABLE ACCESS FULL | SALES | 5 (0)|
----------------------------------------------------------------------

The access path determines the number of units of work required to get data from a base table.
To determine the overall plan cost, the optimizer assigns a cost to each access path:

 Table scan or fast full index scan

During a table scan or fast full index scan, the database reads multiple blocks from disk
in a single I/O. The cost of the scan depends on the number of blocks to be scanned and
the multiblock read count value.

 Index scan
 The cost of an index scan depends on the levels in the B-tree, the number of index leaf
blocks to be scanned, and the number of rows to be fetched using the rowid in the index
keys. The cost of fetching rows using rowids depends on the index clustering factor.

The join cost represents the combination of the individual access costs of the two row sets being
joined, plus the cost of the join operation.
There are two methods of query optimization.
1. Cost based Optimization (Physical)

This is based on the cost of the query. The query can use different paths based on indexes,
constraints, sorting methods etc. This method mainly uses the statistics like record size, number
of records, number of records per block, number of blocks, table size, whether whole table fits in
a block, organization of tables, uniqueness of column values, size of columns etc.

Suppose, we have series of table joined in a query.

T1 ∞ T2 ∞ T3 ∞ T4∞ T5 ∞ T6

For above query we can have any order of evaluation. We can start taking any two tables in any
order and start evaluating the query. Ideally, we can have join combinations in (2(n-1))! / (n-1)!
ways. For example, suppose we have 5 tables involved in join, then we can have 8! / 4! = 1680
combinations. But when query optimizer runs, it does not evaluate in all these ways always. It
uses Dynamic Programming where it generates the costs for join orders of any combination of
tables. It is calculated and generated only once. This least cost for all the table combination is
then stored in the database and is used for future use. i.e.; say we have a set of tables, T = { T1 ,
T2 , T3 .. Tn}, then it generates least cost combination for all the tables and stores it.

 Dynamic Programming

As we learnt above, the least cost for the joins of any combination of table is generated here.
These values are stored in the database and when those tables are used in the query, this
combination is selected for evaluating the query.

While generating the cost, it follows below steps :

Suppose we have set of tables, T = {T1 , T2 , T3 .. Tn}, in a DB. It picks the first table, and
computes cost for joining with rest of the tables in set T. It calculates cost for each of the tables
and then chooses the best cost. It continues doing the same with rest of the tables in set T. It will
generate 2n – 1 cases and it selects the lowest cost and stores it. When a query uses those tables,
it checks for the costs here and that combination is used to evaluate the query. This is called
dynamic programming.

In this method, time required to find optimized query is in the order of 3n, where n is the number
of tables. Suppose we have 5 tables, then time required in 35 = 243, which is lesser than finding
all the combination of tables and then deciding the best combination (1680). Also, the space
required for computing and storing the cost is also less and is in the order of 2n. In above
example, it is 25 = 32.

 Left Deep Trees

This is another method of determining the cost of the joins. Here, the tables and joins are
represented in the form of trees. The joins always form the root of the tree and table is kept at the
right side of the root. LHS of the root always point to the next join. Hence it gets deeper and
deeper on LHS. Hence it is called as left deep tree.

Here instead of calculating the best join cost for set of tables, best join cost for joining with each
table is calculated. In this method, time required to find optimized query is in the order of n2n,
where n is the number of tables. Suppose we have 5 tables, then time required in 5*25 =160,
which is lesser than dynamic programming. Also, the space required for computing storing the
cost is also less and is in the order of 2n. In above example, it is 25 = 32, same as dynamic
programming.

 Interesting Sort Orders

This method is an enhancement to dynamic programming. Here, while calculating the best join
order costs, it also considers the sorted tables. It assumes, calculating the join orders on sorted
tables would be efficient. i.e.; suppose we have unsorted tables T1 , T2 , T3 .. Tn and we have
join on these tables.

(T1 ∞T2)∞ T3 ∞… ∞ Tn

This method uses hash join or merge join method to calculate the cost. Hash Join will simply join
the tables. We get sorted output in merge join method, but it is costlier than hash join. Even
though merge join is costlier at this stage, when it moves to join with third table, the join will
have less effort to sort the tables. This is because first table is the sorted result of first two tables.
Hence it will reduce the total cost of the query.

But the number of tables involved in the join would be relatively less and this cost/space
difference will be hardly noticeable.

All these cost based optimizations are expensive and are suitable for large number of data. There
is another method of optimization called heuristic optimization, which is better compared to cost
based optimization.

2. Heuristic Optimization (Logical)

This method is also known as rule based optimization. This is based on the equivalence rule on
relational expressions; hence the number of combination of queries get reduces here. Hence the
cost of the query too reduces.
This method creates relational tree for the given query based on the equivalence rules. These
equivalence rules by providing an alternative way of writing and evaluating the query, gives the
better path to evaluate the query. This rule need not be true in all cases. It needs to be examined
after applying those rules. The most important set of rules followed in this method is listed
below:

 Perform all the selection operation as early as possible in the query. This should be first
and foremost set of actions on the tables in the query. By performing the selection
operation, we can reduce the number of records involved in the query, rather than using
the whole tables throughout the query.

Suppose we have a query to retrieve the students with age 18 and studying in class DESIGN_01.
We can get all the student details from STUDENT table, and class details from CLASS table.
We can write this query in two different ways.

Here both the queries will return same result. But when we observe them closely we can see that
first query will join the two tables first and then applies the filters. That means, it traverses whole
table to join, hence the number of records involved is more. But he second query, applies the
filters on each table first. This reduces the number of records on each table (in class table, the
number of record reduces to one in this case!). Then it joins these intermediary tables. Hence the
cost in this case is comparatively less.

Instead of writing query the optimizer creates relational algebra and tree for above case.

 Perform all the projection as early as possible in the query. This is similar to selection but
will reduce the number of columns in the query.
 Suppose for example, we have to select only student name, address and class name of students
with age 18 from STUDENT and CLASS tables.

Here again, both the queries look alike, results alike. But when we compare the number of
records and attributes involved at each stage, second query uses less records and hence more
efficient.

 Next step is to perform most restrictive joins and selection operations. When we say most
restrictive joins and selection means, select those set of tables and views which will result
in comparatively less number of records. Any query will have better performance when
tables with few records are joined. Hence throughout heuristic method of optimization,
the rules are formed to get less number of records at each stage, so that query
performance is better. So is the case here to

Physical & Logical Data Structures in DBMS:

The physical data structure refers to the physical arrangement of the data on the
secondary storage device, usually disk. Typically, this physical structure is the concern
of specialists who design DBMSs. Analysts, programmers, and users are generally less
concerned with the physical structure than with the logical structure.

1. Physical Structure: it is simply the physical data files that you can see in a file
manager. You can find most of them in the directory where your database is resided.
Few types of file:
 Data File: extension is DBF, where the data is stored. It is a physical file on disk
that is created by the Database and contains data structures such as tables and
indexes. Data is written to these files in a proprietary format that cannot be read by
other programs.

Several mechanisms are available for allocating and managing the storage of these
files. The most common mechanisms include:

Automatic Storage Management (ASM).

Operating system file system:Most of the databases store files in a file system, which
is a data structure built inside a contiguous disk address space. All operating systems
have file managers that allocate and de-allocate disk space into files within a file
system.

A file system is commonly built on top of a logical volume constructed by a software

package called a logical volume manager (LVM). The LVM enables the pieces of
multiple physical disks to be combined into a single contiguous address space that
appears as one disk to higher layers of software.

Raw device:Raw devices are disk partitions or logical volumes not formatted with a file
system. The primary benefit of raw devices is the ability to perform direct I/O and to
write larger buffers. In direct I/O, applications write to and read from the storage device
directly, bypassing the operating system buffer cache.

Cluster File System: is a software that enables multiple computers to share file storage
while maintaining consistent space allocation and the file content. With a cluster file
system, the failure of a computer in the cluster does not make the file system
unavailable. In an operating system file system, however, if a computer sharing files
through NFS or other means fails, then the file system is unavailable.

 Control File: extension is CTL, where the database current state is stored. It is a
small binary file that records the physical structure of the database. The control file
includes:
 The database name
 Names and locations of associated datafiles and redo log files
 The timestamp of the database creation
 The current log sequence number
 Checkpoint information

The control file must be available for writing by the Database server whenever the
database is open. Without the control file, the database cannot be mounted and
recovery is difficult.

 Parameter File:A parameter file is a file that contains a list of initialization

parameters and a value for each parameter. You specify initialization parameters in a
parameter file that reflect your particular installation.
1. A server parameter file is a binary file that acts as a repository for initialization
parameters. The server parameter file can reside on the machine where the database
server executes.
2. An initialization parameter file is a text file that contains a list of initialization
parameters. The file should be written in the client's default character set. Sample
entries in an initialization parameter file are:
PROCESSES = 100
OPEN_LINKS = 12
GLOBAL_NAMES = true

 Redo Log: extension is RDO, It consists of two or more pre-allocated files that
store all changes made to the database as they occur. Every instance of anDatabase
has an associated redo log to protect the database in case of an instance failure.

 Redo log files are filled with redo records. A redo record, also called a redo entry,
is made up of a group of change vectors
 Redo entries record data that you can use to reconstruct all changes made to the
database, including the undo segments.
 Redo records are buffered in a circular fashion in the redo log buffer of the
SGAand are written to one of the redo log files by the Log Writer (LGWR) database
background process.
 Redo records can also be written to a redo log file before the corresponding
transaction is committed.

The redo log of a database consists of two or more redo log files. The database
requires a minimum of two files to guarantee that one is always available for writing
while the other is being archived (if the database is in ARCHIVELOG mode).

LGWR writes to redo log files in a circular fashion. When the current redo log file fills,
LGWR begins writing to the next available redo log file. When the last available redo log
file is filled, LGWR returns to the first redo log file and writes to it, starting the cycle
again.
 Fig. Use of Redo Log Files by LGWR

Logical Structure: it only stay in memory, where physically store in physical file. It only
appear when the database service is started, and only can be view by using certain
database tools. Few types of logical structure:
Tablespace: where the tables or data are stored. 1 tablespace can map to 1 or more
data files.
0..Segment: Smaller unit in tablespace, which can further categorized into data
segment, index segment, temporary segment and rollback segment.
 Extend: Smaller unit in Segment.
 Block: Smaller unit in Extend.