Selectivity factors

[vweevers]

On selectivity factors for single relation access paths, adapted from Access Path Selection
in a Relational Database Management System (p26):

property = value (eq)
F = 1 / cardinality(property index) if there is an index
F = 1/10 otherwise

property1 = property2 (eq)
F = 1/MAX(cardinality(property1 index), cardinality(property2 index))
if there are indexes on both property1 and property2
This assumes that each key value in the index with the smaller cardinality has a
matching value in the other index.

F = 1/cardinality(property-i index) if there is only an index on property-i
F = 1/10 otherwise

property > value (or any other open-ended comparison) (lt/gt)
F = (high key value - value) / (high key value - low key value)
Linear interpolation of the value within the range of key values yields F if the property
is an arithmetic type and value is known at access path selection time.
F = 1/3 otherwise (i.e. property not arithmetic)

property BETWEEN value1 AND value2 (lt + gt)
F = (value2 - value1) / (high key value - low key value)
A ratio of the BETWEEN value range to the entire key value range is used as the
selectivity factor if property is arithmetic and both value1 and value2 are known at
access path selection.
F = 1/4 otherwise

property IN (list of values)
F = (number of items in list) * (selectivity factor for property = value)
This is allowed to be no more than 1/2.

propertyA IN subquery
F = (expected cardinality of the subquery result) / (product of the cardinalities of
all the relations in the subquery’s FROM-list).

(pred expression1) OR (pred expression2)
F = F(pred1) + F(pred2) - F(pred1) * F(pred2)

(pred1) AND (pred2)
F = F(pred1) * F(pred2)

NOT pred
F = 1 - F(pred)