列索引的有效性与列数据的熵有关。

Question

作为关系数据库(Postgres，MySQL)的使用者，我常常不得不在各种查询的上下文中考虑查询速度。然而，在生产之前，您通常不知道如何使用数据库，也不知道瓶颈可能在哪里。

这让我想知道，，我能不能用一条关于一列的预测熵的经验法则来猜测索引该列的速度增长？

一个快速的谷歌结果是由计算机科学毕业生为计算机科学毕业生撰写的论文。对于一个自学的程序员来说，你能用“外行”来概括它吗？

熵？：我将熵定义为按行数除以平均重复值的次数来计算的熵。如果对于那些拥有CS词汇的人来说，这是一个糟糕的词汇选择，请建议一个更好的词。

Answer 1

这个问题实在太宽泛，无法彻底回答，但我将尝试总结一下PostgreSQL的情况(我对其他关系数据库管理系统还不太了解，但我编写的一些内容将适用于其中的大多数)。

与前面提出的熵不同，PostgreSQL项是某个条件的选择性，它是一个介于0到1之间的数字，定义为满足条件的行数，除以表中的行总数。一个低选择性值的条件被称为高度选择性(在某种程度上与直觉相反)。

确定索引是否有用的唯一可靠方法是比较有索引和没有索引的执行时间。

当PostgreSQL确定对表上的条件使用索引是否有效时，它将整个表的顺序扫描的估计成本与使用适用的索引进行索引扫描的成本进行比较。

由于顺序读取和随机I/O (用于访问索引)的速度往往不同，因此有几个参数影响成本估计，从而影响决策：

• seq_page_cost：顺序获取磁盘页的成本
• random_page_cost：非顺序获取磁盘页的成本
• cpu_tuple_cost：处理一个表行的成本
• cpu_index_tuple_cost：索引扫描期间处理索引条目的成本

这些成本是以虚单位来衡量的，通常将seq_page_cost定义为1，而将其他的定义为关系。

数据库收集表统计信息，以便知道每个表的大小以及列值是如何分布的(最常见的值及其频率、直方图、与物理位置的相关性)。

要查看PostgreSQL如何使用所有这些数字的示例，请查看文档中的这个例子。

使用默认设置，经验法则可能是，除非选择性小于0.2，否则索引不会有多大帮助。

Answer 2

我认为您要问的是，索引的影响与列中数据的分布有关。这里有很多理论。通常，您会发现索引查找效率取决于索引中数据的分布。换句话说，如果你拉0.01%的表，一个索引比拉5%的表更有效率。这是因为随机磁盘I/O的效率总是低于顺序读取(即使是在SSD上，因为操作系统会提前进行缓存)。

这并不是唯一的考虑因素。总是存在关于使用索引检索集合的最佳方法的问题，特别是如果排序的话。您是扫描排序索引还是筛选索引，然后进行排序？通常，这里有一个假设，即数据在两者之间平均分布，但如果这是一个错误的假设，您可能会得到糟糕的查询计划。

因此，您在这里应该做的是查找索引cardinality并获得查询计划的经验，特别是当计划者出错时，这样您就可以理解为什么会出现错误。