Created by Turbolearn AI

Objectives of Query Processing

Static versus dynamic queries.
How a query is decomposed and semantically analyzed.
How to create a relational algebra tree to represent a query.
The rules of equivalence for the relational algebra operations.
How to apply heuristic transformation rules to improve the efficiency of a query.
The types of database statistics required to estimate the cost of operations.
The different strategies for implementing the relational algebra operations.
How to evaluate the cost and size of the relational algebra operations.
How pipelining can be used to improve the efficiency of queries.
The difference between materialization and pipelining.
The advantages of left-deep trees.
Approaches for finding the optimal execution strategy.
Extensions required to relational query processing and query optimization to advanced queries.
How Oracle handles query optimization.

When the relational model was first launched commercially, one of the main aims of query processing was to determine the
most cost-effective way to perform a complex query.

Query Optimization Techniques

In first-generation network and hierarchical database systems, programmers were responsible for selecting the most appropriate
execution strategy. In contrast, with declarative languages like SQL, users specify what data is required rather than how it should
be retrieved.

There are two main techniques for query optimization:

1. Heuristic rules to order the operations in a query.

2. Comparing different strategies based on their relative costs and selecting the one that minimizes resource usage.

Because disk access is slow compared with memory access, disk access tends to be the dominant cost in query processing for a
centralized DBMS.

Query processing transforms a high-level query into a relational algebra query and checks that it is syntactically and
semantically correct.

Query Processing Phases

Query processing can be divided into four main phases:

1. Decomposition: Parsing, code decomposition, and transformation.

2. Optimization: Orders the operations in a query transformation using rules known to generate good execution strategies;
compares different strategies based on their relative costs and selects the one that minimizes resource usage.
3. Pipelining: Allows several operations to be performed in a parallel way, rather than requiring one operation to be complete
before another can start.
4. Execution: A typical query processor chooses an optimal execution strategy.

What is Query Optimization?

Query optimization is the activity of choosing an efficient execution strategy for processing a query. It involves finding
equivalent transformations of the same high-level query to minimize resource usage.

The goal is to reduce the total execution time of the query. However, resource usage may also be viewed as the response time,
in which case, we concentrate on maximizing the number of parallel operations. Due to the computational complexity with a
large number of relations, the strategy is generally reduced to finding a near-optimum solution.

Both methods of query optimization depend on database statistics to properly assess the different options that are available.
The accuracy and currency of these statistics significantly affect the efficiency of the execution strategy. The statistics cover
information about relations, attributes, and indexes.

Page 1
 Created by Turbolearn AI

For example, the system catalog may store statistics giving the cardinality of relations, the number of distinct values for each
attribute, and the number of levels in a multilevel index. Keeping the statistics current can be problematic, so an alternative
approach is to update the statistics periodically or whenever the system is idle, or to make it the users’ responsibility to indicate
when the statistics should be updated.

Comparison of Different Processing Strategies: Example

Let's look at an example query in SQL:

SELECT *
FROM Staff s,
Branch b
WHERE [Link] = [Link]
AND [Link] = 'Manager'
AND [Link] = 'London';

This query can be expressed in relational algebra in different ways. Here are two of them:

1. Calculate the Cartesian product of Staff and Branch, then apply the selection:

σ(position=′M anager′)∧(city=′London′)(Staf f ⋈Staf f .branchN o=[Link] o Branch)

2. Join Staff and Branch on the branch number, then apply the selection:

⋈(Staf f .branchN o=[Link] o) (Staf f )

Assume there are 1000 tuples in Staff, 50 in Branch, 50 Managers onef oreachbranch, and 5 London branches. Also, assume
there are no indexes or sort keys, and intermediate operations are stored on disk.

The first query would perform significantly more disk accesses because of the Cartesian product. A better strategy is to perform
the unary operations Selection and Projection as early as possible, thereby reducing the operands of any subsequent binary
operations.

Optimization Timing

Dynamic Query Optimization

Advantages: Always selects an optimum strategy based on the most up-to-date information.
Disadvantages: Performance is affected as the query has to be parsed, validated, and optimized before it can be executed
every time.

Static Query Optimization

Advantages: Removes runtime overhead and allows more time to evaluate execution strategies.
Disadvantages: The chosen strategy may no longer be optimal when the query is run due to changes in the database.

A hybrid approach could be used to overcome the disadvantage of static query optimization, where the query is reoptimized if
the system detects that the database statistics have changed significantly across the entire DBMS session.

Query Decomposition
The aims of query decomposition are to transform a high-level query into one that is easier to process and to check whether the
query is syntactically and semantically correct. Typical stages of query decomposition are:

Page 2
 Created by Turbolearn AI

1. Analysis
2. Normalization
3. Semantic Analysis
4. Simplification
5. Query Restructuring

1. Analysis
In this stage, the query is lexically and syntactically analyzed using techniques based on the grammar of the query language
defined in the system catalog. It also verifies that any operations applied to database objects are appropriate for the object type.

2. Normalization
The normalization stage of query processing converts the query into a normalized form to facilitate further processing. Common
normal forms include Conjunctive Normal Form and Disjunctive Normal Form.

Conjunctive normal form: a sequence of conjuncts connectedbyAN Doperator, where each conjunct contains one or more
terms connected by OR operator.

(position = 'Manager' OR salary > 20000) AND branchNo = 'B003'

Disjunctive normal form: a sequence of disjuncts connectedbyORoperator, where each disjunct contains one or more terms
connected by AND operator.

(position = 'Manager' AND branchNo = 'B003') OR (salary > 20000 AND branchNo = 'B003')

3. Semantic Analysis
The objective of semantic analysis is to reject normalized queries that are incorrectly formulated or contradictory. A query is
contradictory if its predicate cannot be satisfied by any tuple.

4. Simplification
In this stage, the query is simplified by applying idempotency rules of boolean algebra, such as:

p AND (p) ≡ p
p OR (p) ≡ p
p AND false ≡ false
p OR false ≡ p
p AND true ≡ p
p OR true ≡ true
p AND (~p) ≡ false
p OR (~p) ≡ true
p AND (p OR q) ≡ p
p OR (p AND q) ≡ p

5. Query Restructuring
In the final stage of query decomposition, the query is restructured to provide a more efficient execution strategy.

Heuristic Approach to Query Optimization

The heuristic approach uses transformation rules to convert one relational algebra expression into an equivalent form known to
be more efficient.

Transformation Rules for Relational Algebra Operations

Page 3
 Created by Turbolearn AI

By applying transformation rules, the optimizer can transform a relational algebra expression into an equivalent expression that
is known to use less resources.

1. Conjunctive Selection Operations can cascade into individual Selection operations andviceversa:

σp∧q∧r(R) ≡ σp(σq(σr(R)))

2. Commutativity of Selection operations:

σp(σq(R)) ≡ σq(σp(R))

3. In a sequence of Projection operations, only the last one is required:

πLπM . . . πN (R) ≡ πL(R)

4. Commutativity of Selection and Projection operations:

πA1,...,Am(σp(R)) ≡ σp(πA1,...,Am(R)) where p ∈ A 1, A2, . . . , An

5. Commutativity of Theta Join orCartesianproduct:

R ⋈p S ≡ S ⋈p R

R × S ≡ S × R

6. Commutativity of Selection and Theta Join orCartesianproduct:

σp(R ⋈ S) ≡ (σp(R)) ⋈ S where p ∈ A 1, A2, . . . , An

σp(R × S) ≡ (σp(R)) × S where p ∈ A 1, A2, . . . , An

7. Commutativity of Projection and Theta Join:

πL1∪L2(R ⋈ S) ≡ (πL1(R)) ⋈ (πL2(S))

8. Commutativity of Union and Intersection:

R ∪ S ≡ S ∪ R

R ∩ S ≡ S ∩ R

9. Commutativity of Selection with Union, Intersection and Set Difference:

σp(R ∪ S) ≡ σp(S) ∪ σp(R)

σp(R ∩ S) ≡ σp(S) ∩ σp(R)

σp(R − S) ≡ σp(S) − σp(R)

10. Commutativity of Projection with Union:

πL(R ∪ S) ≡ πL(S) ∪ πL(R)

11. Associativity of Theta Join andCartesianproduct:

(R ⋈ S) ⋈ T ≡ R ⋈ (S ⋈ T )

(R × S) × T ≡ R × (S × T )

12. Associativity of Union and Intersection:

(R ∪ S) ∪ T ≡ S ∪ (R ∪ T )

(R ∩ S) ∩ T ≡ S ∩ (R ∩ T )

Good Heuristics for Query Optimization

Page 4
 Created by Turbolearn AI

1. Perform Selection operations as early as possible.

2. Combine the Cartesian product with a subsequent Selection operation whose predicate represents a join condition into a
Join operation.
3. Use associativity of binary operations to rearrange leaf nodes so that the most restrictive relations are used first.
4. Perform Projection operations as early as possible.
5. Compute common expressions once.

Cost Estimation for Relational Algebra Operations

A DBMS may have many different ways of implementing the relational algebra operations. The aim of query optimization is to
choose the cheapest one. To do this, it uses formulae that estimate the costs, and selects the one with the lowest cost. In this
section we examine the different strategies available for implementing the main relational algebra operations. For each one we
provide an overview of the implementation and give an estimated cost. The dominant cost in query processing is usually that of
disk accesses.

Database Statistics
The success of estimating the size and cost of intermediate relations depends on the amount of information the DBMS holds.

Typically, we require the following information in its system catalog:

For each base relation R:

nTuplesR: the number of tuples records in relation R thatis, itscardinality.

TupleSizeR: the size of each tuple in R inbytes.
nBlocksR: the number of blocks required to store R.
bFactorR: the blocking factor of R thatis, thenumberof tuplesof Rthatf itintooneblock.
Index information - type of index clusteredorunclustered, search keys, levels.

For each attribute A of relation R:

ValueSizeA: the size of each value of A inbytes.

minAR, maxAR: the minimum and maximum values of A in relation R.
SCAR: the selection cardinality of attribute A in relation R. This is the number of tuples that satisfy an equality
condition on attribute A.

Selection Cardinality Estimation

When estimating the selection cardinality SCA of a relation R, given that the values of attribute A are uniformly distributed in R,
and there is at least one value that satisfies the condition:
nT uples(R)
SCA(R) = 1 if A is a key attribute of R; [ ] otherwise
nDistinctA(R)

We can also estimate the selection cardinality for other conditions:

(maxA(R)−c)
SCA(R) = [nT uples(R) ∗ ]
(maxA(R)−minA(R))

For combined conditions:

SCA(R) ∗ SCB(R) f or (A ∧ B)
SCA(R)∗SCB(R)
f or (A ∨ B)
1

For multilevel index I on attribute set A:

nLevelsA(I ) —the number of levels in I.

nLf BlocksA(I ) —the number of leaf blocks.

Keeping these statistics current can be problematic because updating statistics every time a tuple is inserted or updated can
significantly impact performance. A common approach is for the DBMS to update the statistics periodically or whenever the
system is idle. Another approach is to make it the users’ responsibility to indicate that the statistics should be updated.

Page 5
 Created by Turbolearn AI

Selection Operation Strategies

The Selection operation in the relational model works on a single relation, say R, and defines tuples of R that satisfy the
specified predicate. This predicate often involves comparing an attribute of R with a constant value or another attribute value.
The predicate may also be composite, involving more than one condition, with conditions combined using logical connectives like
AND, OR, and NOT.

Here are the main strategies for implementing the Selection operation:

Linear search unorderedf ile, noindex

Binary search orderedf ile, noindex
Equality on hash key

Linear Search
With this approach, it may be necessary to scan each tuple in each block to determine whether it satisfies the
selection predicate.

As shown in the pseudocode above, a linear search involves checking each entry until you find the one you're looking for.

Cost Estimate:
[nBlocks(R)/2] for equality condition on a key attribute, assuming tuples are uniformly distributed.
nBlocks(R) otherwise.

Binary Search
If the file is ordered on the attribute involved in the equality comparison, a binary search can be used.

Cost Estimate:
[log2(nBlocks(R))] for equality condition on ordered attribute.
[log2(nBlocks(R))] + [SCA(R)/bF actor(R)] otherwise.

Other Strategies
Here are some additional strategies, with a brief overview of when each should be applied:

Equality on hash key: Cost is 1, assuming no overflow.

Equality condition on primary key: Cost is nLevelsA(I ) + 1.
Inequality condition on primary key: Cost is nLevelsA(I ) + [nBlocks(R)/2].
Equality condition on clustering secondary index: Cost is nLevelsA(I ) + [SCA(R)/bF actor(R)].
Equality condition on a nonclustering secondary index: Cost is nLevelsA(I ) + [SCA(R)].
Inequality condition on a secondary B+-tree index: Cost is nLevelsA(I ) + [nLf BlocksA(I )/2 + nT uples(R)/2].

Cardinality Estimation
Estimating the cardinality of the result relation S obtained from the Selection operation can be quite difficult. However, if we
assume that attribute values are uniformly distributed within the domain and that attributes are independent, we can use the
following estimates:

Page 6
 Created by Turbolearn AI

nT uples(S) = SCA(R)

For any attribute B of S:

nDistinctB(R) (nT uples(S)+nDistinctB(R)) nDistinctB(R)
nDistinctB(S) = nT uples(S) if nT uples(S) < ; if ≤ nT uples(S) ≤ 2 ∗ nDistinctB
2 3 2

It is possible to derive more accurate estimates when we relax the assumption of uniform distribution, but this requires the use of
more detailed statistical information, such as histograms and distribution.

Composite Predicates
We can express a composite predicate in two forms: conjunctive normal form and disjunctive normal form.

Conjunctive selection: Contains only those tuples that satisfy all conjuncts.
Disjunctive selection: Contains tuples formed by the union of all tuples that satisfy the disjuncts.

Conjunctive Selection Without Disjunction

1. If one of the attributes in a conjunct has an index or is ordered, we can use one of the selection strategies 2–8 discussed
previously to retrieve tuples satisfying that condition. We can then check whether each retrieved tuple satisfies the
remaining conditions in the predicate.
2. If the Selection involves an equality condition on two or more attributes and a composite index orhashkey exists on the
combined attributes, we can use the index directly, as previously discussed. The type of index will determine which of the
aforementioned algorithms will be used.
3. If we have secondary indexes defined on one or more attributes and these attributes are involved only in equality conditions
in the predicate, if the indexes use record pointers arecordpointeruniquelyidentif iesatuple, we can take the intersection of
the sets of pointers that satisfy these conditions. If indexes are not available on all the attributes, we can test the retrieved
tuples against the remaining conditions.

Selections With Disjunction

If one of the terms in the selection condition contains an OR, and the term requires a linear search because no suitable index or
sort order exists on every term in the Selection, can we optimize the query by retrieving the tuples that satisfy each condition and
applying the Union operation, which will also eliminate duplicates. Record pointers can be used if they exist. If no attribute can be
used for efficient retrieval, we use the linear search and check all the conditions simultaneously for each tuple.

Join Operation Strategies

The Join operation is one of the most time-consuming operations to process, so it must be performed as efficiently as possible.

Recall that the Theta join operation defines a relation containing tuples that satisfy a specified predicate F from the
Cartesian product of two relations.

Here are the main strategies for implementing the Join operation:

Block nested loop join

Indexed nested loop join
Sort–merge join
Hash join

Block Nested Loop Join

Page 7
 Created by Turbolearn AI

The simplest join algorithm is a nested loop that joins the two relations together. Because the basic unit of reading/writing is a
disk block, we can improve on the algorithm by having two additional loops that process blocks.

Cost Estimate:

nBlocks(R) + (nBlocks(R) ∗ nBlocks(S))

An improvement to this strategy is to read as many blocks as possible from the smaller relation, say R, into the database buffer,
saving one block for the inner relation and one for the result relation. If the buffer can hold nBuffer blocks, then we read
(nBuf f er − 2) blocks from R into the buffer at a time, and one block from S at a time.

New Cost Estimate:

nBlocks(S)∗nBlocks(R)
nBlocks(R) + [ ]
(nBuf f er−2)

Indexed Nested Loop Join

If there is an index orhashf unction on the join attributes of the inner relation, say S, the indexed nested loop join can be used.
For each tuple in R, we use the index to retrieve the matching tuples in S.

Cost Estimate:

nBlocks(R) + nT uples(R) ∗ (nLevelsA(I ) + 1) if the join attribute A in S is the primary key

nBlocks(R) + nT uples(R) ∗ (nLevelsA(I ) + [SCA(R)/bF actor(R)]) for clustering index I on attribute A

Sort-Merge Join

Page 8
 Created by Turbolearn AI

With the sort-merge join, the relations are first sorted on the join attributes and then merged. Because the relations are in sorted
order, tuples with the same join attribute value are guaranteed to be in consecutive order.

Cost Estimate:

nBlocks(R) + nBlocks(S)

If a relation, R, has to be sorted, we would have to add the cost of the sort. We can approximate this as
nBlocks(R) ∗ [log2(nBlocks(R))]

Hash Join

With a hash join, the relations are partitioned using a hash function. The hash function should provide uniformity and
randomness. The algorithm has to check equivalent partitions for the value.

Cost Estimate:

3 ∗ (nBlocks(R) + nBlocks(S))

Projection Operation Strategies

The Projection operation creates a new relation containing a vertical subset of a relation R, extracting the values of specified
attributes and eliminating duplicates.

To implement Projection, the following steps are performed:

Page 9
 Created by Turbolearn AI

1. Removal of attributes that are not required.

2. Elimination of any duplicate tuples that are produced from the previous step.

There are two main approaches to eliminating duplicates: sorting and hashing.

Cardinality Estimation
When the Projection contains a key attribute, then because no elimination of duplicates is required:

nT uples(S) = nT uples(R)

If the Projection consists of a single non-key attribute:

nT uples(S) = SCA(R)

Duplicate Elimination Using Sorting

To remove the unwanted attributes, we need to read all tuples of R and copy the required attributes to a temporary relation. The
estimated cost of sorting is nBlocks(R) ∗ [log (nBlocks(R))], and so the combined cost is:
2

nBlocks(R) + nBlocks(R) ∗ [log2(nBlocks(R))]

Duplicate Elimination Using Hashing

In the partitioning phase, we read relation R and use (nBuf f er − 1) buffer blocks for output. For each tuple, we remove the
unwanted attributes and then apply a hash function h to the combination of the remaining attributes, and write the reduced tuple
to the corresponding partition based on the hashed value.

Relational Algebra Set Operations

The binary set operations of Union, Intersection, and Set difference apply only to relations that are union-compatible.

Union: We place in the result any tuple that appears in either of the original relations, eliminating duplicates where
necessary.

Intersection: We place in the result only tuples that appear in both relations.

Set difference: We examine each tuple of R and place it in the result if it has no match in S.

For all these operations, we could develop an algorithm using the sort–merge join algorithm as a basis.

Page 10
 Created by Turbolearn AI

Cardinality Estimation
Union:

max(nT uples(R), nT uples(S)) ≤ nT uples(T ) ≤ nT uples(R) + nT uples(S)

Set difference:

0 ≤ nT uples(T ) ≤ nT uples(R)

Enumeration of Alternative Execution Strategies

For a given query, the space of possible execution strategies can be extensive. For example, a query involving three joins over
relations R, S, and T has 12 different join orderings:

R⋈S ⋈ T

R⋈T ⋈ S

S ⋈ T ⋈R
T ⋈ S ⋈ R

S⋈R⋈T
S⋈T ⋈R
R ⋈ T ⋈ S

T ⋈ R ⋈ S

T⋈R⋈S
T⋈S⋈R
R ⋈ S ⋈ T

S ⋈ R ⋈ T

In general, with n relations, there are (2(n − 1))!/(n − 1)! different join orderings. While manageable for small n, the number
grows rapidly. For n=4, there are 120; for n=5, the number exceeds 17 million; and for n=10, it surpasses 176 billion.

Pipelining
Pipelining enhances performance by processing data on-the-fly, avoiding the need to write intermediate relational algebra
operation results to disk temporarily.

Pipelining is an optimization technique where the results of one operation are immediately passed to another
operation without materialization.

Materialization involves storing the output of one operation in a temporary relation for subsequent processing.

For example, consider the selection operation with a composite predicate:

σposition=‵M anager′∧salary<20000(Staf f )

If there's an index on the salary attribute, we could execute:

σposition=‵M anager′(σsalary<20000(Staf f ))

Instead of creating a temporary relation, pipelining applies the second selection to each tuple resulting from the first selection.

Pipelining is typically implemented as a separate process or thread within a DBMS. It utilizes buffers for each pair of adjacent
operations to hold tuples being passed. However, pipelining may restrict algorithm choices, as inputs to operations might not be
immediately available. For instance, the standard sort-merge join algorithm cannot be used if pipelined input tuples are not
sorted on the join attributes.

Linear Trees
Linear trees are a specific tree structure used in query optimization.

Page 11
 Created by Turbolearn AI

This image illustrates various tree structures: a and b show left-deep and right-deep trees respectively; c shows another linear
tree; d presents a bushy nonlinear tree.

Left-deep trees are appealing because inner relations are always base relations and thus materialized. With linear trees, one
side of each operator is always a base relation.

Bushy trees alsocallednonlineartrees offer more flexibility but increase complexity.

Left-deep trees reduce the search space for the optimum strategy and allow the query optimizer to be based on dynamic
processing techniques. A disadvantage of left-deep trees is that many alternative execution strategies are not considered,
which may be of lower cost than the one found using the linear tree.

Left-deep trees allow the generation of all fully pipelined strategies, where joins are all evaluated using pipelining.

Physical Operators and Execution Strategies

A physical operator represents a specific algorithm that implements a logical database operation.

The image illustrates two alternative execution strategies. Strategy a involves a hash join between 'Staff' and 'Branch' followed
by another hash join with 'PropertyForRent', utilizing a B+-tree index on 'city'. Strategy b uses an indexed nested loop join with
pipelining from 'Staff' to 'Branch', then a merge join with 'PropertyForRent', also with a B+-tree index on 'city'.

Some abstract operators used to implement functions at the leaves of relational algebra trees include:

1. TableScan(R): Reads all blocks of R in an arbitrary order.

2. SortScan(R, L): Reads tuples of R in order, sorted by attributes in list L.

3. IndexScan(R, p): Accesses tuples of R through an index on attribute A, where p is a predicate of the form A θ c
θisacomparisonoperator, cisaconstantvalue .

4. IndexScan(R, A): Retrieves the entire relation R using the index on attribute A.

DBMSs typically support a uniform iterator interface, hiding internal implementation details of each operator. The iterator
interface consists of three functions:

Page 12
 Created by Turbolearn AI

1. Open: Initializes the state of the iterator to retrieve the first tuple and allocates buffers for inputs and the output.

2. GetNext: Returns the next tuple in the result and puts it in the output buffer. It calls GetNext on each child node and
performs operator-specific code to generate the output.

3. Close: Terminates the operator and deallocates buffers.

Reducing the Search Space

To reduce the search space, query optimizers generally restrict unary operations:

Restriction 1: Unary operations are processed on-the-fly: selections are processed as relations are accessed for the first
time; projections are processed as the results of other operations are generated.

This implies that all operations are dealt with as part of join execution.

Restriction 2: Cartesian products are never formed unless the query specifies one.

Restriction 3: The inner operand of each join is a base relation, never an intermediate result.

This third restriction is more heuristic and excludes many alternative strategies, but it significantly reduces the number of
alternative join strategies to be considered to O2n for queries with n relations and has a corresponding complexity of O3n.

Dynamic Programming Algorithm

The dynamic programming algorithm is based on the assumption that the model satisfies the principle of optimality.

To obtain the optimal strategy for a query consisting of n joins, consider only the optimal strategies for subexpressions that
consist of n − 1 joins and extend those strategies with an additional join. Suboptimal strategies can be discarded.

The algorithm recognizes that some potentially useful strategies could be discarded. To ensure that such possibilities are not
discarded, the algorithm introduces the concept of interesting orders: an intermediate result has an interesting order if it is
sorted by a final ORDER BY attribute, GROUP BY attribute, or any attributes that participate in subsequent joins.

The dynamic programming algorithm proceeds from the bottom up and constructs all alternative join trees that satisfy the
restrictions defined in the section:

Pass 1: Enumerate strategies for each base relation using a linear scan and all available indexes on the relation. Partition
these partial single − relation strategies into equivalence classes based on any interesting orders.

Pass k: Generate all k-relation strategies by considering each strategy retained after Pass k − 1 as the outer relation, again
discarding any Cartesian products generated and processing any selection and projections on-the-fly.

Pass n: Generate all n-relation strategies by considering each strategy retained after Pass n − 1 as the outer relation,
discarding any Cartesian products generated.

Semantic Query Optimization

Semantic query optimization uses database schema to reduce the search space.

For example, consider the constraint that prevents a member of staff from managing more than 100 properties at the same time:

CREATE ASSERTION StaffNotHandlingTooMuch

CHECK (NOT EXISTS (
SELECT staffNo
FROM PropertyForRent
GROUP BY staffNo
HAVING COUNT(*) > 100
));

Consider the query:

Page 13
 Created by Turbolearn AI

SELECT [Link], COUNT(*)

FROM Staff s, PropertyForRent p
WHERE [Link] = [Link]
GROUP BY [Link]
HAVING COUNT(*) > 100;

If the optimizer is aware of the query as there will be.

Consider the following:

CREATE ASSERTION ManagerSalary

CHECK (salary > 20000 AND position = ‘Manager’)

and the following query:

Using the previous constraint, we can rewrite this query

SELECT [Link], fName, IName, propertyNo

FROM Staff s, PropertyForRent p
WHERE [Link] = [Link]
AND salary > 20000

Alternative Approaches to Query Optimization

Alternative approaches to the System R dynamic programming algorithm have been proposed.

Simulated Annealing: Searches a graph of alternative execution strategies, modeling the annealing process used in crystal
growth.

Iterative Improvement: Performs a number of local optimizations, each starting at a random node and repeatedly accepting
random downhill moves until a local minimum is reached.

Two-Phase Optimization: A hybrid of Simulated Annealing and Iterative Improvement.

Genetic Algorithms: Simulate a biological phenomenon. The algorithms start with an initial population, consisting of a
random set of strategies, each with its own cost.

A Heuristic Algorithm*: Expands one execution strategy at a time, based on its proximity to the optimal strategy.

Distributed Query Optimization

Distributed query optimization is more complex due to the distribution of data across sites in a network. The speed of the
underlying network has to be taken into consideration when comparing different strategies.

Query Processing and Optimization in ORDBMS

These features address many of relational model. The SQL:2011 standard does not address some areas of extensibility.

One capability required is that the ORDBMS query processor flattens queries whenever possible.

When an external user-defined function is defined:

A. The per-call CPU cost of the function.

B. The expected percentage of bytes in the argument that the function will read.
C. The CPU cost per byte read.

The CPU cost of a function invocation is then given by the algorithm A + C ∗ expectedsizeof argument, and the I/O cost is
B ∗ expectedsizeof argument.

Page 14
 Created by Turbolearn AI

The problem with this approach is that it can be for a user to provide these figures.

Example: Find all detached properties in Glasgow that are within two miles of a primary school and are managed

SELECT *
FROM PropertyForRent p, Staff s

The image includes four flowcharts that demonstrate different scenarios related to primary school networks and their internet
connectivity.

CREATE INDEX nearPrimarySchoolIndex ON PropertyForRent USING B-tree nearP rimarySchool(postcode);

In this case, if the UDF causes a fatal runtime error, the only process affected of the UDF.

New Index Types

A mechanism to plug in any user-defined index structure provides the highest of flexibility. An ORDBMS could provide a generic
template index structure that is sufficiently general to encompass most index structures that users might design and interface to
the normal DBMS mechanisms. For example, the Generalized Search Tree GiST is a template index structure based on B-trees
that accommodates tree-based index structures with minimal coding.

Query Optimization in Oracle

Oracle supports rule-based and cost-based query optimization.

Rule-Based and Cost-Based Optimization

The Oracle rule-based optimizer has fifteen rules, ranked in order of efficiency, and chooses a table only if the statement access
path available.

The rule-based optimizer assigns a score to each execution strategy using these rankings and then selects the execution strategy
with lowest score.

Page 15
 Created by Turbolearn AI

1. Single row by ROWID

2. Single row by cluster join
3. Single row by hash cluster key with unique or primary key
4. Single row by unique or primary key
5. Cluster join
6. Hash cluster key
7. Indexed cluster key
8. Composite key
9. Single-column indexes
10. Bounded range search on indexed columns
11. Unbounded range search on indexed columns
12. Sort–merge join
13. MAX or MIN of indexed column
14. Order by
15. Full table scan

Query Optimization Techniques

Indexed Columns and ORDER BY

When using ORDER BY on indexed columns, the rule-based optimizer considers various access paths.

For example, consider the query:

SELECT propertyNo
FROM PropertyForRent
WHERE rooms > 7 AND city = ‘London’;

assuming indexes on propertyNo primarykey, rooms, and city.

The rule-based optimizer considers:

A single-column access path using the condition (city = ‘London’). This has a rank of 9.
An unbounded range scan using the index on the rooms column from the condition (rooms > 7). This has a rank of 11.
A full table scan, which has a rank of 15.

Even with an index on the propertyNo column, it's not considered because it isn't used in the WHERE clause. The optimizer would
choose the index on the city column based on these paths.

Cost-Based Optimization
Cost-based optimization has deprecated rule-based optimization. It minimizes resource usage based on either:

Throughput: Minimizing resources to process rows accessed by the query.

Response Time: Minimizing resources to process the first row accessed by the query.

The OPTIMIZER_MODE initialization parameter determines which approach is used. The cost-based optimizer also considers user-
provided hints.

Statistics
The cost-based optimizer depends on statistics for tables, clusters, and indexes. Oracle can automatically gather statistics using
the automated maintenance tasks infrastructure (AutoTask). The DBMS_STATS PL/SQL package can generate statistics on various
objects. For instance, to gather schema statistics for a 'Manager' schema:

Page 16
 Created by Turbolearn AI

EXECUTE DBMS_STATS.GATHER_SCHEMA_STATS(‘Manager’, DBMS_STATS.AUTO_SAMPLE_SIZE);

Oracle uses parallel methods to gather statistics where possible, except for index statistics which are collected serially.

Sampling Methods
When gathering statistics, you can specify whether to calculate them on the entire data structure or just a sample. Options
include:

Row Sampling: Reads rows ignoring physical placement on disk, which may require a full table or index scan in the worst
case.
Block Sampling: Reads a random sample of blocks and gathers statistics using rows in these blocks.

Sampling uses fewer resources than computing exact figures for the entire structure.

Statistics can also be gathered while creating or rebuilding indexes using the COMPUTE STATISTICS option with CREATE INDEX or
ALTER INDEX commands. Statistics are stored in the Oracle data dictionary and can be inspected through various views.

Oracle Dictionary Views

Statistics are stored within the Oracle dictionary and can be inspected through views. Here’s a summary of some key views and
their contents:

View Name Description

ALL_TABLES All objects in the database that the user has access to.
USER_TABLES Objects in the user’s schema.
TAB_HISTOGRAMS Statistics about the use of histograms on tables.
TAB_COLUMNS Information about the columns in tables, views, and clusters.
TAB_COL_STATISTICS Column statistics and histogram information from TAB_COLUMNS.
TAB_PARTITIONS Information about the partitions in a partitioned table.
CLUSTERS Information about clusters.
INDEXES Information about indexes.
IND_STATISTICS Statistics about all indexes.
IND_COLUMNS Information about the columns in each index on tables/clusters.
TAB_SUBPARTITIONS Information on each table subpartition.
IND_PARTITIONS Information for each index partition.
IND_SUBPARTITIONS Information on each index subpartition.
PART_COL_STATISTICS Column statistics and histogram information for table partitions.
PART_HISTOGRAMS Histogram data for the histograms on the table partitions.
SUBPART_COL_STATISTICS Column statistics and histogram information for subpartitions of partitioned objects.
SUBPART_HISTOGRAMS Histogram data for histograms on table subpartitions.

These views can be prefixed with ALL_, USER_, or emptypref ix depending on the scope.

Hints
The cost-based optimizer considers hints to influence decisions, such as:

Forcing the use of a particular access path.

Specifying a particular join order.
Selecting a specific join type.
Enabling parallel execution.

For example:

Page 17
 Created by Turbolearn AI

SELECT /*+ INDEX(sexlndex) */ fName, IName

FROM Staff
WHERE sex = ‘M’;

If there are as many male as female staff members, a full table scan might be more efficient. If there are far fewer male staff
members, an index scan would be better. This hint forces the optimizer to use the index on the sex column.

Stored Execution Plans

Optimal plans can be stored using the CREATE OUTLINE statement. This stores the attributes used by the optimizer to create the
execution plan, ensuring that the optimizer uses these attributes rather than generating a new plan.

Histograms
Histograms improve estimates when data values within a column are not uniformly distributed.

Figure a shows a uniform distribution while Figure b illustrates a non-uniform distribution. Storing a uniform distribution is
straightforward with a low value, a high value, and a total count.

A histogram is a data structure that improves estimation accuracy. There are two types:

Width-Balanced Histogram: Divides data into fixed equal-width ranges buckets, each containing a count of the number of
values.
Height-Balanced Histogram: Places approximately the same number of values in each bucket.

Histograms can be used to improve estimates with non uniform distributions. Here is an example of two types of histograms that

can be used:

Here's a table that illustrates the difference in histograms:

Histogram
Description Characteristics
Type

Width- Divides data into fixed, equal-width ranges

Equal width buckets, distribution within bucket assumed uniform.
Balanced buckets.

Height- Places approximately the same number of End-points determined by data distribution, height of each
Balanced values per bucket. column approximately even.

For the predicate rooms > 9, a width-balanced histogram provides a better estimate than assuming uniform distribution. Oracle
uses height-balanced histograms.

Histograms are persistent objects, so creating and maintaining them involves overhead.

Page 18
 Created by Turbolearn AI

Viewing the Execution Plan

Oracle allows viewing the execution plan chosen by the optimizer using the EXPLAIN PLAN command. This helps verify if the query
is executed as expected. The output is stored in a database table (default is PLAN_TABLE).

Key columns in the execution plan:

STATEMENT_ID: Optional parameter specified in the EXPLAIN PLAN statement.

OPERATION: Name of the internal operation performed.
OPTIONS: Another internal operation performed.
OBJECT_NAME: Name of the table or index.
ID: Number assigned to each step in the execution plan.
PARENT_ID: ID of the next step that operates on the output of the current step.
POSITION: Order of processing for steps with the same PARENT_ID.
COST: Estimated cost of the operation nullf orrule − basedoptimizer.
CARDINALITY: Estimated number of rows accessed by the operation.

Here is an example of an execution plan:

Each line represents a step in the execution plan, with indentation showing the hierarchy of operations.

Query Processing Phases

Query processing includes:

Decomposition: Parsing and validating the query.

Optimization: Choosing the strategy that minimizes resource usage.
Code Generation: Creating executable code based on the optimized plan.
Execution: Running the code to retrieve the data.

The first three phases occur at compile time or runtime.

Query optimization aims to choose the most efficient strategy to minimize resource usage.

Query Decomposition
Query decomposition transforms a high-level query into a relational algebra query and checks its syntax and semantics. The
stages are:

1. Analysis
2. Normalization
3. Semantic Analysis
4. Simplification
5. Query Restructuring

A relational algebra tree represents the transformed query internally.

Page 19
 Created by Turbolearn AI

Query Optimization Rules

Query optimization applies transformation rules to convert relational algebra expressions into equivalent, more efficient
expressions. These rules include:

Cascade of selection.
Commutativity of unary operations.
Commutativity of Theta join andCartesianproduct.
Associativity of Theta join andCartesianproduct.

Heuristics for Query Optimization

Heuristic rules include:

Performing Selection and Projection operations as early as possible.

Combining Cartesian product with a subsequent Selection representingajoincondition into a Join operation.
Using associativity of binary operations to rearrange leaf nodes so that nodes with the most restrictive Selections are
executed first.

Cost Estimation
Cost estimation relies on statistical information from the system catalog, such as:

Cardinality of each base relation.

Number of blocks required to store a relation.
Number of distinct values for each attribute.
Selection cardinality of each attribute.
Number of levels in each multilevel index.

Selection Operation Strategies

Strategies for implementing the Selection operation:

Linear search unorderedf ile, noindex.

Binary search orderedf ile, noindex.
Equality on hash key.
Equality condition on primary key.
Inequality condition on primary key.
Equality condition on clustering secondary index.
Equality condition on a nonclustering secondary index.
Inequality condition on a secondary B+-tree index.

Join Operation Strategies

Strategies for implementing the Join operation:

Block nested loop join.

Indexed nested loop join.
Sort-merge join.
Hash join.

Materialization vs. Pipelining

With materialization, the output of one operation is stored in a temporary relation. Pipelining, on the other hand, streams the
results of one operation to another without creating a temporary relation.

Pipelining saves the cost of creating temporary relations and reading results back.

Page 20
 Created by Turbolearn AI

Left-Deep Trees
A relational algebra tree where the right-hand relation is always a base relation is known as a left-deep tree.

Left-deep trees:

Reduce the search space for the optimum strategy.

Allow query optimizers to be based on dynamic processing techniques.
May not consider all alternative execution strategies.

Dynamic Programming Algorithm

The dynamic programming algorithm assumes the cost model satisfies the principle of optimality. To find the optimal strategy for
a query with n joins:

1. Consider strategies with (n - 1) joins.

2. Extend those strategies with an additional join.
3. Create equivalence classes based on interesting orders.
4. Retain the lowest cost strategy in each class.

Extensibility of Query Optimizer

The query optimizer must:

Execute user-defined functions efficiently.

Take advantage of new index structures.
Transform queries in new ways.
Navigate among data using references.

Index Structures in ORDBMS

Traditional RDBMSs use B-tree indexes for scalar data. ORDBMSs require specialized index structures for complex types, such
as:

Generic B-trees.
R-trees regiontrees for two- and three-dimensional data.
Indexes on the output of a function.

Page 21