Evaluation Metrics of Indexing

Lecture 8 · eight measurable properties that tell you whether an index is worth having.

1 · Search time

Search time means how much time is needed to find a record.

SELECT * FROM Employee WHERE Emp_ID = 105;

Without index: may scan all rows.
With index: directly finds the record.
A good index should reduce search time.

2 · Disk I/O cost

Disk I/O means the number of disk pages read or written. A good index reduces disk I/O.

If an employee table has 10,000 rows, without an index the DBMS may read many pages. With an index, it may read only a few pages. Lower disk I/O means better performance.

3 · Query execution time

The actual time required to execute a query.

execution time

SELECT * FROM Employee WHERE Department = 'CSE';

	Time
Before index	2 seconds
After index	0.2 seconds

So the index improves execution time by a factor of ten in this example.

4 · Selectivity

Selectivity = Number of distinct values ÷ Total number of rows

Emp_ID has high selectivity because almost every value is unique.
Gender has low selectivity because many rows have the same value.

Indexes are more useful on high-selectivity columns.

Live calculator

Distinct values Total rows

Selectivity = 1000 / 1000 = 1.0000
HIGH selectivity — a very good index candidate

Good candidate

CREATE INDEX idx_emp_id ON Employee(Emp_ID);

Less useful candidate

CREATE INDEX idx_gender ON Employee(Gender);

5 · Index size

Index size means how much storage space the index uses. A smaller index is better, because it uses less memory and disk space. An index on Emp_ID may require far less space than an index on a long text column like Address.

6 · Maintenance cost

The extra cost needed to update the index during insert, update and delete operations.

maintenance

INSERT INTO Employee VALUES (107, 'Mina', 'EEE', 48000);

If the table has 5 indexes, all 5 indexes may need to be updated. So more indexes mean higher maintenance cost.

7 · Index hit ratio

How often the DBMS uses the index instead of a full table scan.

If 100 queries are executed and 80 use the index:
Index Hit Ratio = 80 / 100 = 0.80 = 80 %

A higher hit ratio indicates better index usefulness.

8 · Cardinality

Cardinality means the number of unique values in a column.

Column	Distinct values	Total rows	Selectivity	Cardinality
Emp_ID	1000	1000	1.00	High
Email	1000	1000	1.00	High
Department	5	1000	0.005	Low
Gender	2	1000	0.002	Low

High-cardinality columns are usually better for indexing.CREATE INDEX idx_email ON Employee(Email); is useful because email values are usually unique.

Next: The ten types of index →