SQL Processing - Relational Database Index Design and the Optimizers - page 37

FILTER FACTORS

The filter factor specifies the selectivity of a predicate—what proportion of the
source table rows satisfy the condition expressed by the predicate. It is dependent
on the distribution of the column values. Thus, the filter factor of predicate
SEX = 'F' increases whenever a female customer is added to the customer table.
ThepredicateCITY = :CITY has an average filter factor (1/the number
of distinct values of CITY) as well as a value specific filter factor (CITY =
'HELSINKI'). The difference between these two is critical, both for index design
and for access path selection. Figure 3.4 shows an example where a filter factor
of 0.2% for the CITY column in a 1-million-row customer table predicts the size
of the result set will be 2000 rows.
When evaluating the adequacy of an index, worst-case filter factors are more
important than average filter factors; worst case relates to the worst input ,that
is, the input that results in the longest elapsed time with a given index.

Filter Factors for Compound Predicates

The filter factor for a compound predicate can be derived from the filter factors of
the simple predicates, only if the values of the predicate columns are not statisti-
cally correlated. Consider, for example, the filter factor for CITY

= :CITY AND

LNAME :LNAME. If there is no statistical correlation between the columns

CITY and LNAME, the filter factor of the compound predicate will be equal to
the product of the filter factors for CITY

=

:LNAME.
If column CITY has 500 distinct values and column LNAME 10,000 distinct
values, the filter factor for the compound predicate will be 1

= :CITY and LNAME =

000
or 1/5,000,000. This implies that the column combination CITY, LNAME has
5,000,000 distinct values. In most CUSTOMER tables, however, the two columns
are correlated. The proportion of Andersens is much higher in Copenhagen than
in London, and there could even be cities in England that don't have a single
customer with a common Danish last name. Therefore, the filter factor of this

/ 500 × 1 / 10 ,

Filter factor (FF)

Number of result rows
=
Number of source rows

WHERE
CITY = :CITY

CUST

Result

Figure 3.4 Filter factor is a
property of a predicate.

1,000,000 rows FF = 0.2 % 2000 rows