postgresql - 了解 PostgreSQL 中的相关性

Question

当数据库必须执行与另一个表的连接时，它可能会广泛地从以下三种策略中选择一种:

• 顺序扫描(当我们需要大部分记录时)
• 位图索引扫描(当我们想要一些记录时)
• 索引扫描(当我们需要相对较少的记录时，具有相关索引)

这里的推理是，如果需要保留大部分记录，完全忽略索引，避免I/O惩罚，只顺序读取整个表会更高效。在另一个极端，显然如果我们只需要从索引中读取几个叶节点，这将比读取整个表更快。

我不清楚的是相关性在这里扮演什么角色，以及我们应该如何考虑它。

专注于 Postgres，documentation在这里描述相关性:

Statistical correlation between physical row ordering and logical ordering of the column values. This ranges from -1 to +1. When the value is near -1 or +1, an index scan on the column will be estimated to be cheaper than when it is near zero, due to reduction of random access to the disk. (This column is null if the column data type does not have a < operator.)

下面是我们可以获取给定表中每一列的相关值的方法:

SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'your_table';

据我了解，使用二级索引总是需要对聚簇索引执行 I/O 搜索以查找数据。据我所知，唯一能使 I/O 变好或变坏的是二级索引是否非常接近磁盘上的聚簇索引。但我不清楚相关性对于确定 I/O 寻道的成本有多重要，因为寻道总是需要的。

有人可以解释相关性在这里的物理含义吗？也许我的困惑是由于不了解数据库如何执行索引扫描而引起的。

Answer 1

相关性仅对具有总排序的数据类型的列有意义，也就是说，它支持 operator family属于 btree访问方法(<、<=、=、>= 和 > 运算符)。

如果较大的值倾向于出现在表的物理末端附近而较小的值倾向于出现在开头附近，则相关性为正。值为 1 表示值按排序顺序存储在表中，-1 表示它们按降序存储。

PostgreSQL 中的索引扫描是这样工作的:

1. 第一个匹配条目位于索引中。

2. 如果visibility map指示相应的表 block 仅包含对所有人可见的元组并且我们不需要未存储在索引中的列，我们有一个结果并继续第 4 步(如果优化器认为这适用于大多数索引条目，它将规划一个 index only scan )。

3. 从表中提取相应的行并检查可见性。如果可见且满足过滤条件，我们就找到了结果。

4. 沿扫描方向遍历索引，找到下一个索引项，看是否满足扫描条件。如果是，则返回第二步，否则我们就完成了。

这会导致表 block 随机读取，除非它们已经在共享缓冲区中。

现在如果相关性很高，则更有可能发生两件事:

• 在索引扫描中找到的下一个元组与前一个元组在同一个表 block 中。然后它已经在共享缓冲区中并且不会导致读取。

  总而言之，您最终会碰到更少的不同表 block :彼此相邻的索引条目往往也彼此靠近，通常在同一个 block 中。

• 如果下一个索引条目与上一个索引条目不指向同一个表 block ，则很可能指向下一个表 block 。这导致表 block 的顺序读取，这在旋转磁盘上比随机读取更有效。

让我用一个例子来说明这一点，假设一个索引在一个完全相关的列上:

找到的第一个索引条目指向表 block 42，第二个也是，第三个到第 30 个指向 block 43，接下来的 20 个索引条目将指向 block 44。

因此索引扫描将访问 50 个元组，但它只会从磁盘读取 3 个 block ，并且按顺序读取这些 block (首先是 block 42，然后是 block 43，然后是 block 44)。

如果没有相关性，50 个元组可能位于不同的表 block 中(假设表很大)，这意味着 50 次随机磁盘读取。

因此，当相关性高时，索引扫描成本更低，而如果相关性低，则向后索引扫描成本更低。优化器使用相关性相应地调整估计成本。