[prev] 65 [next]

Estimating Selection Result Size

Selectivity = fraction of tuples expected to satisfy a condition.

Common assumption: attribute values uniformly distributed.

Example: Consider the query

select * from Parts where colour='Red'

If   V(colour,Parts)=4,   r=1000  ⇒  |σcolour=red(Parts)|=250

In general, | σA=c(R) |  ≅  rR / V(A,R)

Heuristic used by PostgreSQL: | σA=c(R) |  ≅  r/10