mysql - MySQL 的查询规划器中的 "no statistics"案例的记录/扇出逻辑是如何导出的？

Question

在MySQL Server 5.7源码中，公式records = (x * (b-a) + a*c-b)/(c-1)在query planner中用于计算记录的数量当 key 分布统计不可用时记录。

这个公式是从哪里来的，它是如何推导出来的，或者为什么这个特定的公式是正在使用的公式？它是否有既定的理论基础，如果有，它的基础是什么？

https://github.com/mysql/mysql-server/blob/5.7/sql/sql_planner.cc#L529

          Assume that the first key part matches 1% of the file
          and that the whole key matches 10 (duplicates) or 1
          (unique) records.
          Assume also that more key matches proportionally more
          records
          This gives the formula:
          records = (x * (b-a) + a*c-b)/(c-1)
          b = records matched by whole key
          a = records matched by first key part (1% of all records?)
          c = number of key parts in key
          x = used key parts (1 <= x <= c)

Answer 1

如果您完全没有关于您的问题的数据，您将被迫进行估算。

该公式的一般形式在评论中进行了解释:

• 如果我们仅使用多列索引(具有 c 列)的一个键列 (x)，我们将得到 a 行(1%总行数)。所以对于 x=1，根据定义，结果是 a。
• 如果我们知道多列索引的每个键列的值，我们就可以得到每个整个键的行数 (b)；所以对于 x=c，我们根据定义得到 b 行(即 1 或 10)。<
• 在两者之间(如果我们对超过 1 个键列使用键值，但不是全部)，对于每个额外的已知键值，我们可以排除一些额外的行:我们有 a-b 行不属于对于我们知道我们的 完整 键(将有 b 行)的情况，根据定义，它们应按可用键列(( x-1)/(c-1)).
• (x-1)/(c-1) 中的 -1 只是一个移位(你可以使用不同的变量名)，因为我们只需要计算 additional 列，但 c 和 x 是包含第一列的计数。 (在时间序列中，您将为第一列调用参数t=0，-1 就是这样做的)。

所以总而言之，我们得到 a - (a-b) * (x-1)/(c-1) (第一个键列的 a 减去我们按比例排除)。这就是(如果你稍微改变一下那个表达式)给出的公式。快速完整性检查:对于 x=1 (x-1=0)，第二项是 0 我们得到 a ，由第一个条件定义；对于 x=c，我们得到第二个条件定义的 a-(a-b)=b。

使用这些假设来做出这个假设并非不合理，但您可能会找到一个不同的公式，同样有意义。不过，要争论它更好将是一项更艰巨的任务。

然后是选择值的问题(在本例中为 b=10 和 1%)。您显然可以选择任何值。为了在没有任何可靠数据的情况下做到这一点，除了直觉，有一个叫做 Fermi estimate 的概念。 :

The estimation technique is named after physicist Enrico Fermi as he was known for his ability to make good approximate calculations with little or no actual data.

您基本上只需为您的输入参数选择 magnite (1, 1000000, 1/100) 的数量级，您就会得到一个合理的数量级的结果。

那么您希望非唯一键覆盖多少行？它大于 1，否则您会将其设为唯一键，但它更像是 2、10 还是 100？ 10 可能是一个很好的猜测(它涵盖了该估计中大约 3 到 30 的值)。因此，尽管这个数字可能来自一项为期 2 年的全局 key 分配调查，但通常以 10 的幂的估计值以这样的方式得出。如果您想绝对确定，请询问开发人员。

还有 obligatory xkcd对于此类主题:What-if? Paint the Earth