前缀索引和索引的选择性

有时候为了提升索引的性能，同时也节省索引空间，可以只对字段的前一部分字符进行索引，这样做的缺点是，会降低索引的选择性。

索引的选择性是指，不重复的索引值（也称为基数，cardinality）和数据表的记录总数（#T）的比值，范围从 1/#T 到 1 之间。

• 索引的选择性越高则查询效率越高，因为选择性高的索引可以让 MySQL 在查找时过滤掉更多的行。

• 唯一索引的选择性是 1，这是最好的索引选择性，性能也是最好的。

前缀索引是一种能使索引更小、更快的有效办法，但它也有缺点：MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY 操作，也无法使用前缀索引做覆盖扫描。对于 BLOB、TEXT 或者很长的 VARCHAR 类型的列，必须使用前缀索引，因为 MySQL 并不支持对这些列的完整内容进行索引。

建立前缀索引的关键点在于，既要选择足够长的前缀以保证较高的选择性，同时又不能太长（以便节约空间）。前缀应该足够长，以使得前缀索引的选择性接近于索引整列。换句话说，前缀的“基数”应该接近于完整列的“基数”。

实验

数据准备

CREATE TABLE city_demo
(
    city VARCHAR(50) NOT NULL
);

INSERT INTO city_demo SELECT city FROM city;

--- 重复5次
INSERT INTO city_demo SELECT * FROM city_demo;
--- 

UPDATE city_demo
SET city = (SELECT city FROM city ORDER BY RAND() LIMIT 1);

分析表中数据，找到常见的城市列表

SELECT city, COUNT(*) cnt
FROM city_demo
GROUP BY city
ORDER BY cnt DESC
LIMIT 10;

+----------------+---+
|city            |cnt|
+----------------+---+
|London          |63 |
|Jastrzebie-Zdrój|55 |
|Valencia        |50 |
|Brindisi        |48 |
|Talavera        |47 |
|Daxian          |47 |
|Shaoguan        |47 |
|Lapu-Lapu       |47 |
|Omiya           |46 |
|Kaliningrad     |46 |
+----------------+---+

找出分布近似的前缀

查找到最频繁出现的城市前缀，先从 3 个前缀字母开始：

SELECT LEFT(city, 3) prefix, COUNT(*) cnt
FROM city_demo
GROUP BY prefix
ORDER BY cnt DESC
LIMIT 10;

+------+---+
|prefix|cnt|
+------+---+
|San   |459|
|Cha   |195|
|al-   |163|
|Sal   |163|
|Val   |149|
|Tan   |148|
|Sou   |148|
|Sha   |143|
|Man   |132|
|Hal   |129|
+------+---+

增加前缀长度，直到这个前缀的选择性接近完整列的选择性。经过实验后发现，前缀长度为 7 时比较合适（长度为 8 的前缀与长度为 7 的前缀没有任何变化）：

SELECT LEFT(city, 7) prefix, COUNT(*) cnt
FROM city_demo
GROUP BY prefix
ORDER BY cnt DESC
LIMIT 10;

+--------+---+
|prefix  |cnt|
+--------+---+
|Santiago|71 |
|Valle de|70 |
|London  |63 |
|San Feli|61 |
|Jastrzeb|55 |
|Valencia|50 |
|Brindisi|48 |
|Talavera|47 |
|Shaoguan|47 |
|Daxian  |47 |
+--------+---+

计算列的选择性

计算合适的前缀长度的另外一个办法就是计算完整列的选择性，并使前缀的选择性接近完整列的选择性。

SELECT COUNT(DISTINCT city) / COUNT(*)          orginal,
       COUNT(DISTINCT LEFT(city, 3)) / COUNT(*) sel3,
       COUNT(DISTINCT LEFT(city, 4)) / COUNT(*) sel4,
       COUNT(DISTINCT LEFT(city, 5)) / COUNT(*) sel5,
       COUNT(DISTINCT LEFT(city, 6)) / COUNT(*) sel6,
       COUNT(DISTINCT LEFT(city, 7)) / COUNT(*) sel7,
       COUNT(DISTINCT LEFT(city, 8)) / COUNT(*) sel8
FROM city_demo;

+-------+------+------+------+------+------+------+
|orginal|sel3  |sel4  |sel5  |sel6  |sel7  |sel8  |
+-------+------+------+------+------+------+------+
|0.0312 |0.0237|0.0293|0.0305|0.0309|0.0310|0.0310|
+-------+------+------+------+------+------+------+

只看平均选择性是不够的，还有例外的情况，需要考虑最坏情况下的选择性。平均选择性会让你认为前缀长度为 4 或者 5 的索引已经足够了，但如果数据分布很不均匀，可能就会有陷阱。

观察前缀为 4 的最常出现城市的次数：

SELECT LEFT(city, 4) prefix, COUNT(*) cnt
FROM city_demo
GROUP BY prefix
ORDER BY cnt DESC
LIMIT 10;

+------+---+
|prefix|cnt|
+------+---+
|Sant  |207|
|San   |188|
|Sout  |118|
|Toul  |100|
|Chan  |92 |
|Kali  |78 |
|al-Q  |73 |
|Xi´a  |73 |
|Cuau  |72 |
|Ranc  |71 |
+------+---+

如果前缀是 4 字节，则最常出现的前缀出现的次数比最常出现的城市出现的次数要多很多，即这些值的选择性比平均选择性要低。

创建索引

ALTER TABLE city_demo
    ADD KEY (city(7));