Query Optimization

Question 1

is the process of selecting the most efficient query-evaluation plan from among the many strategies usually possible for processing a given query, especially if the query is complex.

Answer 1

Query Optimization

Question 2

to find an expression that is equivalent to the given expression, but more efficient to execute.

Answer 2

relational-algebra level

Question 3

defines exactly what algorithm should be used for each operation and how the execution of the operations should be coordinated.

Answer 3

Evaluation plan

Question 4

provide a way to view the evaluation plan chosen to execute
a given query.

Answer 4

databases

Question 5

displays the execution plan chosen for the specified query <query>.</query>

Answer 5

explain <query></query>

Question 6

the command stores the resultant plan in a table called plan table, instead of displaying it.

Answer 6

explain plan for

Question 7

displays the stored plan

Answer 7

select * from table

Question 8

DB2 follows a simil arapproach to Oracle, but requires this program to be executed to display the stored plan.

Answer 8

db2exfmt

Question 9

to be executed before
submitting the query; then, when a query is submitted, instead of executing the query, the evaluation plan is displayed.

Answer 9

set showplan_text

Question 10

are said to be equivalent if on every legal database the
two expressions generate the same multiset of tuples.

Answer 10

multiset relational algebra

Question 11

states that two relational-algebra expressions are equivalent and can replace each other since they always produce the same result on any valid database.

Answer 11

equivalence rule

Question 12

Query optimizers use these rules to transform expressions into more efficient but logically equivalent forms.

Answer 12

equivalence rule

Question 13

operations are associative

Answer 13

Natural-join

Question 14

A set of equivalence rules is this if no rule can be derived from the others.

Answer 14

minimal

Question 15

can be deconstructed into a sequence of individual selections.

Answer 15

Conjunctive selection

Question 16

is important for reducing the size of temporary results

Answer 16

Join Ordering

Question 17

the number of tuples in the relation r

Answer 17

nr

Question 18

the number of blocks containing tuples of relation r.

Answer 18

br

Question 19

the size of a tuple of relation r in bytes.

Answer 19

lr

Question 20

the blocking factor of relation r—that is, the number of tuples of relation r that
f t into one block.

Answer 20

fr

Question 21

the number of distinct values that appear in the relation r for attribute A.

Answer 21

V(A,r)

Question 22

the values for the attribute are divided into a number of ranges, and with each range the histogram associates the number of tuples whose attribute value lies in that range.

Answer 22

histogram

Question 23

divides the range of values into equal-sized ranges

Answer 23

equi-width histogram

Question 24

adjusts the boundaries of the ranges such that each range has the same number of values.

Answer 24

equi-depth histogram

Question 25

generates statistics on specified relations, or on all relations.

Answer 25

analyze

Question 26

defines exactly what algorithm should be used for each operation, and how the execution of the operations should be coordinated.

Answer 26

evaluation plan

Question 27

explores the space of all query-evaluation plans that are equivalent to the given query, and chooses the one with the least estimated cost.

Answer 27

cost-based optimizer

Question 28

The most common type of query in SQL consists of a join of a few relations, with join predicates and selections specified in the where clause.

Answer 28

Cost-Based Join-Order Selection

Question 29

the number of different query plans that are equivalent to the query can be large.

Answer 29

complex join query

Question 30

store results of computations and reuse them, a procedure that can reduce execution time greatly.

Answer 30

Dynamic-programming algorithms

Question 31

if it could be useful for a later operation.

Answer 31

interesting sort order

Question 32

allows a logical operation, such as a join, to be transformed to a physical operation, such as a hash join, or a nested-loops join.

Answer 32

physical equivalence rules

Question 33

stores the optimal query evaluation plan for a subexpression when it is optimized for the first time

Answer 33

memoization

Question 34

reduce the cost of optimization

Answer 34

heuristics

Question 35

are particularly convenient for pipelined evaluation, since the right operand is a stored relation, and thus only one input to each join is pipelined.

Answer 35

left-deep join orders

Question 36

is a hierarchical procedure based on the nested-block concept of SQL.

Answer 36

Starburst project

Question 37

Caching and reuse of query plans

Answer 37

Plan caching

Question 38

as functions that take parameters and return either a single value or a set of values (possibly an empty set).

Answer 38

Optimizing Nested Subqueries

Question 39

The parameters are the variables from an outer-level query that are used in the nested subquery

Answer 39

correlation variables

Question 40

The technique of evaluating a nested subquery by invoking it as a function

Answer 40

correlated evaluation

Question 41

The process of replacing a nested query by a query with a join, semijoin, or anti-semijoin

Answer 41

decorrelation

Question 42

is a view whose contents are computed and stored.

Answer 42

materialized view

Question 43

constitute redundant data, in that their contents can be inferred from the view definition and the rest of the database contents.

Answer 43

Materialized views

Question 44

The task of keeping a materialized view up-to-date with the underlying data

Answer 44

view maintenance.

Question 45

A better option is to modify only the affected parts of the materialized view

Answer 45

incremental view maintenance

Question 46

Most database systems perform

Answer 46

immediate view maintenance

Question 47

The changes (inserts and deletes) to a relation or expression

Answer 47

differential

Question 48

which is a sequence of queries and updates that reflects the typical load on the system.

Answer 48

workload

Question 49

The problem of an update affecting the execution of a query associated with the update

Answer 49

Halloween problem

Question 50

Complex queries may in fact have subexpressions repeated in different parts of the query, which can be similarly exploited to reduce query evaluation cost.

Answer 50

multiquery optimization.

Question 51

optimizes subexpressions shared by different expressions in a program by computing and storing the result and reusing it wherever the subexpression occurs.

Answer 51

Common subexpression elimination