Skip to content

Latest commit

 

History

History
57 lines (44 loc) · 2.26 KB

cost_estimation.md

File metadata and controls

57 lines (44 loc) · 2.26 KB
Raw

Query Cost Estimation

Overview

Query optimisers estimate costs via:

  • Cost of performing operation.
  • Size of result (which affects cost of performing next operation).

Result size estimated by statistical measures on relations. For example:

  • r_S: cardinality of relation S.
  • R_S: average size of tuple in relation S.
  • V(A, S): number of distinct values of attribute A in S.
  • min(A, S): min value of attribute A in S.
  • max(A, S): max value of attribute A in S.

Estimating Projection Result Size

Easy, since we know:

  • Number of tuples in output:
    • r_out = |π_{a,b,..}(T)| = |T| = r_T (in SQL, because of bag semantics).
  • Size of tuples in output:
    • R_out = sizeof(a) + sizeof(b) + ... + (tuple overhead).

Assume page size B:

  • b_out = ceil(r_T / c_out) where c_out = floor(B / R_out).

If using select distinct:

  • |π_{a,b,..}(T)| depends on proportion of duplicates produced.

Estimating Selection Result Size

Selectivity: fraction of tuples expected to satisfy a condition.

Common assumption: attribute values uniformly distributed. Using this, can incorporate:

  • Total number of tuples.
  • Total number of distinct values.
  • Minimum, maximum values.

Non-Uniform Attribute Value Distributions

Effective ways to handle non-uniform attribute value distributions:

  • Collect statistics about the values stored in the attribute/relation.
  • Store these as meta-data for the relation.

Disadvantage: cost of storing/maintaining statistics.

Estimating Join Result Size

Analysis relies on semantic knowledge about data/relations.

Consider equijoin on common attribute: R ⨝_a S:

  • Case 1: values(R.a) ∩ values(S.a) = {} ==> size(R ⨝_a S) = 0.
  • Case 2: ``uniq(R.a) and uniq(S.a) ==> size(R ⨝_a S) ≤ min(|R|, |S|)`.
  • Case 3: pkey(R.a) and fkey(S.a) ==> size(R ⨝_a S) ≤ |S|.

Postscript

Above methods can (sometimes) give inaccurate estimates that lead to poor evaluation plans. To get more accurate cost estimates:

  • More time for complex computation of selectivity.
  • More space for storage of statistics for data values.

EIther way, optimisation process costs more.

Tradeoff between optimiser performance and query performance.