Answer:
Generation of query-evaluation plans for an expression involves several steps:
- Generating logically equivalent expressions using equivalence rules
- Annotating resultant expressions to get alternative query plans
- Choosing the cheapest plan based on estimated cost. The overall process is called cost based optimisation.
The cost difference between a good and a bad method of evaluating a query would be enormous. We would therefore, need to estimate the cost of operations and statistical information about relations. For example a number of tuples, a number of distinct values for an attribute etc. Statistics helps in estimating intermediate results to compute the cost of complex expressions.
