QueryOptimization

Question 1

What is query optimization?

Answer 1

The process of selecting the most efficient query-evaluation plan from possible strategies for processing a query

Question 2

What are the two main aspects of optimization?

Answer 2

1) Finding equivalent but more efficient relational-algebra expressions 2) Selecting detailed processing strategies (algorithms, indices)

Question 3

What are the three steps to generate query-evaluation plans?

Answer 3

1) Generate logically equivalent expressions 2) Annotate expressions to create alternative plans 3) Estimate costs and choose least costly plan

Question 4

What three factors is plan cost estimation based on?

Answer 4

1) Statistics about relations 2) Statistics estimation for intermediate results 3) Cost formulas for algorithms

Question 5

What makes two relational-algebra expressions equivalent?

Answer 5

They generate the same set of tuples on every legal database instance

Question 6

How can join operations be optimized?

Answer 6

By carefully choosing the join order to reduce size of temporary results

Question 7

What is a cost-based optimizer?

Answer 7

A system that explores all equivalent query-evaluation plans and chooses the one with least estimated cost

Question 8

What are two common types of histograms used in databases?

Answer 8

Equi-width histograms and equi-depth histograms

Question 9

When are database statistics typically updated?

Answer 9

During periods of light system load

Question 10

What is a key heuristic rule for query optimization?

Answer 10

Perform selections as early as possible to reduce number of tuples