为什么索引列上的 SELECT DISTINCT 不是瞬时的？

Question

我有一个像这样的 table 存储各种程序的配置运行。它看起来像这样：

+--------------+---------------+------+-----+---------+-------+
| Field        | Type          | Null | Key | Default | Extra |
+--------------+---------------+------+-----+---------+-------+
| Date         | date          | YES  | MUL | NULL    |       |
| Program      | varchar(20)   | YES  | MUL | NULL    |       |
| ConfigFile   | int(11)       | YES  |     | NULL    |       |
| Parameter    | varchar(20)   | YES  |     | NULL    |       |
| Value        | varchar(20)   | YES  |     | NULL    |       |
+--------------+---------------+------+-----+---------+-------+

ConfigFile 字段包含配置文件的编号 -- 对于某些程序，可以选择多个配置文件。

它有几个索引，如下所示：

+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name | Seq_in_index | Column_name  | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| lists |          1 | Date     |            1 | Date         | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Date     |            2 | Program      | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Date     |            3 | Parameter    | A         |     1108060 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Program  |            1 | Program      | A         |        4676 |     NULL | NULL   | YES  | BTREE      |         |               |
| lists |          1 | Program  |            2 | Parameter    | A         |      183706 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+----------+--------------+--------------+-----------+-------------+----------+--------+------+------------+---------+---------------+

现在假设我想知道给定程序的参数是什么。看来我应该可以做这样的事情：

SELECT DISTINCT Parameter FROM params WHERE Program = 'MyProgram';

这里有如下的解释方案：

+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+
| id | select_type | table  | partitions | type | possible_keys  | key     | key_len | ref   | rows      | filtered | Extra                    |
+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+
|  1 | SIMPLE      | params | NULL       | ref  | Date,Program   | Program | 23      | const | 137203382 |   100.00 | Using where; Using index |
+----+-------------+--------+------------+------+----------------+---------+---------+-------+-----------+----------+--------------------------+

Program 大约有 15 种不同的选择，每个程序可能有 10 到 100 个 Parameter 的值。

根据我对数据库索引工作原理的理解，我希望这会立即完成。特别是，我希望底层数据结构是一个有 15 个节点的二叉搜索树，我搜索它以找到与我的程序对应的那个；找到我的程序后，它会将我带到可能有 100 个或更少节点的第二个二叉搜索树，然后我将简单地遍历它。

当我实际运行查询时，它最终会花费几分钟。

对我来说，这表明在二叉搜索树中可能存在相同值的多个副本，table 的每个节点一个。这是正在发生的事情吗？如果是，我可以做些什么来缓解这种情况？

我考虑过 table 具有唯一的三元组（日期、程序、参数）并具有关系，但我不确定在这种情况下如何执行数据的批量插入。如果我错了为什么它这么慢那么当然这甚至没有帮助。

Answer 1

InnoDB 的 B+Tree 二级索引不是这样形成的。这样想：

对于每一行，构造一个由Program、Parameter、PK.
对这些字符串进行排序。
将它们放在 BTree 中。

注：Program没有分手的迹象。如果 99.9% 的程序都在程序 #5 中怎么办？那将是一个相当不平衡的 BTree。对于您的一个罕见查询很方便，但对于大多数其他查询来说速度较慢。

使用平衡良好的 B+Tree，您的查询必须：

向下钻取 BTree 找到 Program = 'MyProgram'
向前遍历 B+Tree 的叶节点，使用“+”从一个叶块步进到下一个。
走路时，跟踪每个新的Parameter。
Program = 'MyProgram' 失败时退出。

备注：

DISTINCT 通过了解项目的排序方式在我的第 3 步中轻松实施。
"Using index" 说索引是 "covering"——因为你只需要 Program 和 Parameter（那些是 INDEX 中的列). PK 也可隐式用于 "covering".
您提供的 15 与“4676”的基数不一致。但这只是指出统计数据有时相差甚远。（统计信息对此查询的优化没有影响。）

I considered having one table with unique triples (Date, Program, Parameter)

是的，拥有这样的 table 将使您的查询运行更快。但是这样的保养值得吗？

table 可以让您做的另一件事是将这 3 列规范化为单个 MEDIUMINT UNSIGNED（仅 3 个字节），而不是现在在平均行上使用的可能是 30 个字节。同样，JOINs 等的复杂性会超过好处吗？它可能会将磁盘占用空间缩小 50%。

为什么索引列上的 SELECT DISTINCT 不是瞬时的？

Why isn't SELECT DISTINCT on an indexed column instantaneous?

mysql

b-tree

mariadb

database-indexes