Query optimization refers to the process of producing a query execution plan (QEP)

which represents an execution strategy for the query. This QEP minimizes an objective
cost function. A query optimizer, the software module that performs query optimization,
is usually seen as consisting of three components: a search space, a cost model, and a
search strategy.
which can be dynamic, static or hybrid, is a good basis for classifying query optimization techniques.

Dynamic Query Optimization

Dynamic query optimization combines the two phases of query decomposition and optimization with
execution. The QEP is dynamically constructed by the query optimizer which makes calls to the DBMS
execution engine for executing the query’s operations. The most popular dynamic query optimization
algorithm is that of INGRES, one of the first relational DBMS. The algorithm recursively breaks up a
query expressed in relational calculus (i.e., SQL) into smaller pieces which are executed along the way.
The query is first decomposed into a sequence of queries having a unique relation in common. Then

each monorelation query is processed by selecting, based on the predicate, the best access method to
that relation (e.g., index, sequential scan). For example, if the predicate is of the form A = value, an index
available on attribute A would be used if it exists. However, if the predicate is of the form A 6 = value, an
index on A would not help, and sequential scan should be used.

The eager update propagation approaches apply the changes to all the replicas within the context of the
update transaction. Consequently, when the update transaction commits, all the copies have the same
value. Typically, eager propagation techniques use 2PC at commit point, but, as we will see later,
alternatives are possible to achieve agreement. Furthermore, eager propagation may use synchronous
propagation of each update by applying it on all the replicas at the same time (when the Write is issued),
or deferred propagation whereby the updates are applied to one replica when they are issued, but their
application on the other replicas is batched and deferred to the end of the transaction. Deferred
propagation can be implemented by including the updates in the “Prepare-to-Commit” message at the
start of 2PC execution.

Eager techniques typically enforce strong mutual consistency criteria. Since all the replicas are mutually
consistent at the end of an update transaction, a subsequent read can read from any copy (i.e., one can
map a Read(x) to Read(xi ) for any xi). However,a Write(x) has to be applied to all xi(i.e., Write(xi ); 8xi ).
Thus, protocols that follow eager update propagation are known as read-one/write-all (ROWA)
protocols.

The advantages of eager update propagation are threefold. First, they typically ensure that mutual
consistency is enforced using 1SR; therefore, there are no transactional inconsistencies. Second, a
transaction can read a local copy of the data item (if a local copy is available) and be certain that an up-
to-date value is read. Thus, there is no need to do a remote read. Finally, the changes to replicas are
done atomically; thus recovery from failures can be governed by the protocols we have already studied

in the previous chapter. The main disadvantage of eager update propagation is that a transaction has to
update all the copies before it can terminate. This has two consequences. First, the response time
performance of the update transaction suffers, since it typically has to participate in a 2PC execution,
and because the update speed is restricted by the slowest machine. Second, if one of the copies is
unavailable, then the transaction cannot terminate since all the copies need to be updated.

if it is possible to differentiate between site failures and network failures, then one can terminate the
transaction as long as only one replica is unavailable (recall that more than one site unavailability causes
2PC to be blocking), but it is generally not possible to differentiate between these two types of failures.

Lazy Update Propagation

In lazy update propagation the replica updates are not all performed within the context of the update
transaction. In other words, the transaction does not wait until its updates are applied to all the copies
before it commits – it commits as soon as one replica is updated. The propagation to other copies is
done asynchronously from the original transaction, by means of refresh transactions that are sent to the
replica sites some time after the update transaction commits. A refresh transaction carries the sequence
of updates of the corresponding update transaction.

Lazy propagation is used in those applications for which strong mutual consistency may be unnecessary
and too restrictive. These applications may be able to tolerate some inconsistency among the replicas in
return for better performance. Examples of such applications are Domain Name Service (DNS),
databases over geographically widely distributed sites, mobile databases, and personal digital assistant
databases. In these cases, usually weak mutual consistency is enforced.

The primary advantage of lazy update propagation techniques is that they generally have lower
response times for update transactions, since an update transaction can commit as soon as it has
updated one copy. The disadvantages are that the replicas are not mutually consistent and some
replicas may be out-of-date, and, consequently, a local read may read stale data and does not guarantee
to return the up-to-date value.