Cardinality and Selectivity: Performance Tuning -> Databases

 Selectivity and Cardinality (detailed, with formulas & examples)

Cardinality = how many distinct values (or how many rows),

Selectivity = what fraction of the table matches a predicate. The optimizer uses these to estimate rows and pick plans.

1) Cardinality — definitions & formulae

A. Column cardinality (distinct values)

Definition:

Number of distinct values in a column.

Notation / formula:

CARDINALITY(column) = COUNT(DISTINCT column)

Example: if dept_id in emp has values {0,10,20,30,40} → CARDINALITY(dept_id) = 5.

B. Result-set cardinality (rows returned by a query/predicate)

Definition:

Actual number of rows that satisfy a predicate.

Notation / formula:

CARDINALITY(result) = COUNT(*) WHERE <predicate>

Example:

If emp has N = 10,000 rows and dept_id = 20 occurs in 2,000 rows, then:

CARDINALITY(result) = 2000

2) Selectivity - definition & basic formula

Definition:

Fraction (or probability) of rows that satisfy a predicate.

Formula:

Selectivity(s) = (number of rows satisfying predicate) / (total rows)

s = matched_rows / N

Estimated rows (used by optimizer):

Estimated_Rows = N * s

Worked example (digit-by-digit):

Table emp has N = 10,000 rows. dept_id = 20 occurs in matched_rows = 2,000

rows.

Compute selectivity:

1. matched_rows / N = 2000 / 10000

2. simplify: 2000/10000 = 2/10 (divide numerator & denominator by 1000)

3. 2/10 = 1/5

4. 1/5 = 0.2

So s = 0.2. Estimated rows = 10,000 * 0.2 = 2,000 (same as actual here).

3) Common useful formulas & rules-of-thumb

Equality predicate (assuming uniform distribution):

Selectivity(eq) ≈ 1 / NDV(column) where NDV = number of distinct values for that column.

Example: NDV(dept_id) = 5 → s ≈ 1/5 = 0.2.

Range predicate (simple uniform model):

Selectivity(range low..high) ≈ (high - low + 1) / (max_value - min_value + 1)

(For continuous numeric ranges you can drop the +1's, it’s an approximation.)

AND of independent predicates (multiplicative):

If predicates A and B are independent,

s(A AND B) = s(A) * s(B)

Example: s(dept_id = 20) = 0.2, s(gender = 'M') = 0.5 

 combined s = 0.2 0.5 = 0.1 → estimated rows = 10,000 0.1 = 1,000.

OR of independent predicates (inclusion–exclusion):

s(A OR B) = s(A) + s(B) - s(A)*s(B)

Example: s(dept=20)=0.2, s(dept=30)=0.2 (disjoint here so s=0.4 actually — inclusion-exclusion gives same result when disjoint).

Negation:

s(NOT A) = 1 - s(A)

Important caveat: independence assumption often fails (correlation/skew) — real estimates need histograms/statistics.

4) How optimizer uses selectivity & cardinality

1. Optimizer reads table size N and statistics (NDV, histograms, min/max, frequency) and computes s for predicates → then Estimated_Rows = N * s.

2. The chosen access path (index vs full scan), join order, join method depend on estimated rows.

3. If estimated rows are very small → index access is attractive. If large → full table scan may be cheaper.

Rule-of-thumb (not absolute): indexes are more likely to be used when predicate selectivity is low (small fraction), e.g. s < 0.05 (5%)

- but threshold depends on table size, index clustering factor, I/O costs, and DB engine.

5) Concrete SQL examples (with numbers)

Assume emp table: N = 10,000 rows, dept_id has NDV = 5 uniformly distribute

d → each dept has 2,000 rows.

1. SELECT * FROM emp WHERE dept_id = 20;

1. matched_rows = 2,000

2. selectivity s = 2000 / 10000 = 0.2 (20%)

3. estimated rows = 10,000 * 0.2 = 2,000

2. SELECT * FROM emp WHERE gender = 'M' (assume 50% male)

1. s = 0.5 → estimated rows = 5,000

3. SELECT * FROM emp WHERE dept_id = 20 AND gender = 'M'

1. If independent: s = 0.2 * 0.5 = 0.1 → estimated rows = 1,000

2. If highly correlated (say dept 20 mostly males), actual rows could be much

higher — optimizer needs histograms to be accurate.

4. SELECT * FROM emp WHERE salary BETWEEN 40000 AND 60000

Suppose salary min=30000, max=130000 and uniform distribution:

s ≈ (60000 - 40000) / (130000 - 30000) = 20000 / 100000 = 0.2

Estimated rows = 10,000 * 0.2 = 2,000.

6) Why real-world estimates can be wrong

1. Skew: some values much more frequent → uniform assumption fails.

2. Correlation: two columns not independent (e.g., dept and salary). Multiplicative rule gives wrong estimates.

3. Stale or missing statistics: optimizer guesses and may pick poor plan.

4. Complex predicates (LIKE '%abc', functions) require function-based stats or histograms.

Solution: gather accurate statistics (DBMS_STATS in Oracle), create histograms

for skewed columns, use extended statistics for correlated columns.

7) Quick cheat-sheet (formulas)

1. s = matched_rows / N

2. Estimated_Rows = N * s

3. s(eq) ≈ 1 / NDV (if uniform)

4. s(range) ≈ (high - low) / (max - min) (approx)

5. s(A AND B) = s(A) * s(B) (if independent)

6. s(A OR B) = s(A) + s(B) - s(A)*s(B) (if independent)

Vinayak Vishweshwara Dabgar

www.dabgarvinayakv.com

Technical Blogs@ https://crypticcircuit.blogspot.com/