High Cardinality vs. Low Cardinality: Which Column Should Come First in a Range Index?

High Cardinality Column Ordering in a Range Index

In database design, when creating an index on multiple columns, the order of those columns can significantly impact performance for range queries. In particular, for queries involving both a high cardinality column and a low cardinality column, the optimal column ordering in the index can be counterintuitive.

Scenario:

Consider a table with the following schema:

CREATE TABLE `files` (
  `did` int(10) unsigned NOT NULL DEFAULT '0',
  `filename` varbinary(200) NOT NULL,
  `ext` varbinary(5) DEFAULT NULL,
  `fsize` double DEFAULT NULL,
  `filetime` datetime DEFAULT NULL,
  PRIMARY KEY (`did`,`filename`),
  KEY `fe` (`filetime`,`ext`),          -- This?
  KEY `ef` (`ext`,`filetime`)           -- or This?
) ENGINE=InnoDB DEFAULT CHARSET=utf8 ;

This table stores file metadata, with approximately 1 million rows. The filetime column has mostly distinct values, indicating high cardinality, while the ext column has a finite number of values, indicating low cardinality.

Query:

The following query is used to retrieve file information based on both ext and filetime:

WHERE ext = '...'
  AND filetime BETWEEN ... AND ...

Best Index Choice:

The question arises as to which index, fe or ef, would be better for this query. Intuitively, one might assume that the index with the high cardinality column (filetime) first would be more efficient. However, analysis shows that the opposite is true.

Explanation:

Using the EXPLAIN command, we can examine the query plan for different index choices:

-- Force index on fe (filetime first)
EXPLAIN SELECT COUNT(*), AVG(fsize)
FROM files FORCE INDEX(fe)
WHERE ext = 'gif' AND filetime >= '2015-01-01' AND filetime < '2015-01-01' + INTERVAL 1 MONTH;

-- Force index on ef (ext first)
EXPLAIN SELECT COUNT(*), AVG(fsize)
FROM files FORCE INDEX(ef)
WHERE ext = 'gif' AND filetime >= '2015-01-01' AND filetime < '2015-01-01' + INTERVAL 1 MONTH;

The results show that the index ef, with the low cardinality ext column first, performs significantly better than fe.

Further analysis using the Optimizer trace reveals that with the fe index, the optimizer estimated scanning a large number of rows (16684) to filter on the ext value. With the ef index, it could use both index columns efficiently and retrieve only the relevant rows (538).

Conclusion:

When creating a composite index to support range queries, it is advisable to place the column involved in the equality test (in this case, ext) first, regardless of its cardinality. This allows the index to be used more effectively in the query execution plan, resulting in improved performance.

The above is the detailed content of High Cardinality vs. Low Cardinality: Which Column Should Come First in a Range Index?. For more information, please follow other related articles on the PHP Chinese website!