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
For Database Scripts : https://l-earn.dabgarvinayakv.com/toolkit/
