了解 PostgreSQL 中的相关性
Understanding correlation in PostgreSQL
当一个数据库必须执行与另一个数据库的连接时 table，它可能会从以下三种策略中选择一种：
- 顺序扫描（当我们想要大部分记录时）
- 位图索引扫描（当我们想要一些记录时）
- 索引扫描（当我们想要相对较少的记录时，具有相关索引）
这里的道理是，如果需要保留大部分记录，完全忽略索引更高效，避免I/O惩罚，只顺序读取整个table。在另一个极端，显然如果我们只需要从索引中读取几个叶节点，这将比读取整个 table.
更快
我不清楚的是相关性在这里扮演什么角色，以及我们应该如何考虑它。
关注 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.)
这里是我们可以获取给定 table 中每一列的相关值的方法：
SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'your_table';
据我了解，使用二级索引 总是 需要对聚簇索引执行 I/O 搜索以查找数据。据我所知，唯一能让 I/O 变好或变差的是二级索引是否非常接近磁盘上的聚簇索引。但我不清楚相关性对于确定 I/O 查找的成本有多重要，因为始终需要查找。
有人可以解释一下相关性在这里的物理含义吗？也许我的困惑是由于不了解数据库如何执行索引扫描而引起的。
首先，我们有几件事很难完全解释清楚，但我会尝试，如果其中一些对您来说已经很明显了，请原谅。
因此，随机 IOs 很昂贵，因为我们要读取整个磁盘上的随机数据块。
连续批量读取多个块要快得多（尤其是在磁驱动器上，非 ssd）
现在更进一步，您引用的文档专门讨论索引扫描，这通常是一个范围，而不是精确值。
因此，当索引相关时（可以通过相关索引对 table 进行聚类来强制执行），并且它正在寻找一个值范围 IE（其中 Id 在 1000000 和 1001000 之间），位置"scanning" 返回的（块位置）索引很可能位于磁盘上几乎相同的位置。
因此它可以转到索引 ABC，找到 1000 行并找出它需要读取的块，并可能在很少的查找次数中得到它们。 1（或更多）额外寻求获得索引是值得的。
现在，如果没有相关性并且它通过索引进行查找并发现这 1000 行都在不同的块中，在驱动器上的不同位置，它将不得不进行多达 1000 次查找找到所说的数据。从头到尾批量阅读整个 table 可能会更好。对索引的额外查找只会让情况变得更糟，并且批量读取现在不会对提高速度起到多大作用。
如果这有助于解释，请告诉我。
我认为真正的定义可以通过阅读源代码找到；-)
- 统计收集器可能使用{ctid,attribvalue}对来估计物理<-->逻辑相关性
- 计划者可以使用这些系数来估计要获取的页数
例如，这是我的 twitter-sucker-DB 运行 在 Raspberry Pi 上的统计数据：
（目前大约有 350 万行）
\connect twitters
SELECT version();
SELECT count(*) from tweets;
\d tweets
SELECT attname, correlation, n_distinct -- , null_frac
FROM pg_stats
WHERE tablename = 'tweets'
AND schemaname = 'public';
You are now connected to database "twitters" as user "postgres".
version
----------------------------------------------------------------------------------------------------------------------------
PostgreSQL 9.6.9 on armv6l-unknown-linux-gnueabihf, compiled by gcc (Raspbian 6.3.0-18+rpi1+deb9u1) 6.3.0 20170516, 32-bit
(1 row)
count
---------
3525068
(1 row)
Table "public.tweets"
Column | Type | Modifiers
----------------+--------------------------+------------------------------------------------------
seq | bigint | not null default nextval('tweets_seq_seq'::regclass)
id | bigint | not null
user_id | bigint | not null
sucker_id | integer | not null default 0
created_at | timestamp with time zone |
is_dm | boolean | not null default false
body | text |
in_reply_to_id | bigint | not null default 0
parent_seq | bigint | not null default 0
is_reply_to_me | boolean | not null default false
is_retweet | boolean | not null default false
did_resolve | boolean | not null default false
is_stuck | boolean | not null default false
need_refetch | boolean | not null default false
is_troll | boolean | not null default false
fetch_stamp | timestamp with time zone | not null default now()
Indexes:
"tweets_pkey" PRIMARY KEY, btree (seq)
"tweets_id_key" UNIQUE CONSTRAINT, btree (id)
"tweets_userid_id" UNIQUE, btree (user_id, id)
"tweets_created_at_idx" btree (created_at)
"tweets_du_idx" btree (created_at, user_id)
"tweets_id_idx" btree (id) WHERE need_refetch = true
"tweets_in_reply_to_id_created_at_idx" btree (in_reply_to_id, created_at) WHERE is_retweet = false AND did_resolve = false AND in_reply_to_id > 0
"tweets_in_reply_to_id_fp" btree (in_reply_to_id)
"tweets_parent_seq_fk" btree (parent_seq)
"tweets_ud_idx" btree (user_id, created_at)
Foreign-key constraints:
"tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)
"tweets_user_id_fkey" FOREIGN KEY (user_id) REFERENCES tweeps(id)
Referenced by:
TABLE "tweets" CONSTRAINT "tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)
attname | correlation | n_distinct
----------------+-------------+------------
seq | -0.519016 | -1 #<<-- PK
id | -0.519177 | -1 #<<-- NaturalKey
user_id | -0.0994714 | 1024 # FK to tweeps, cadinality ~= 5000)
sucker_id | 0.846975 | 5 # Low Card
created_at | -0.519177 | -0.762477 # High Card
is_dm | 1 | 1
body | 0.0276537 | -0.859618
in_reply_to_id | 0.104481 | 25956 # FK to self
parent_seq | 0.954938 | 1986 # FK To self
is_reply_to_me | 1 | 2
is_retweet | 0.595322 | 2
did_resolve | 0.909326 | 2
is_stuck | 1 | 1
need_refetch | 1 | 1
is_troll | 1 | 1
fetch_stamp | -0.519572 | 95960 # High Card
(16 rows)
这里奇怪的是（大部分）升序列 {seq,id,created_at,fetch_stamp} 具有负相关性，自参考 FKs {in_reply_to_id ,parent_seq} 积极的。我的猜测是对于 n_distinct = -1 (:=unique) 列，根本不使用相关性，可能只使用符号。
相关性仅对具有总排序的数据类型的列有意义，即它支持属于 btree 访问方法的 operator family（<、<=、=、>= 和 > 运算符）。
如果较大的值倾向于出现在 table 的物理末端附近而较小的值倾向于出现在开头附近，则相关性为正。值为 1 表示值按排序顺序存储在 table 中，-1 表示它们按降序存储。
PostgreSQL 中的索引扫描是这样工作的：
第一个匹配条目位于索引中。
如visibility map indicates that the corresponding table block contains only tuples that are visible to everybody and we need no column that is not stored in the index, we have a result and continue with step 4 (if the optimizer thinks that this works for most index entries, it will plan an index only scan).
从 table 中提取相应的行并检查可见性。如果是可见的，满足过滤条件，我们就找到了结果
沿扫描方向遍历索引，找到下一个索引项，看是否满足扫描条件。如果是，则返回第二步，否则我们就完成了。
这会导致随机读取 table 个块，除非它们已经在共享缓冲区中。
现在如果相关性高，则更有可能发生两件事：
在索引扫描中找到的下一个元组与前一个元组位于同一 table 块中。然后它已经在共享缓冲区中并且不会导致读取。
总而言之，您最终会碰到更少的不同 table 块：彼此相邻的索引条目往往也彼此靠近，通常在同一个块中。
如果下一个索引条目与前一个不指向同一个table块，则很可能指向下一个table块。这导致 table 块的顺序读取，这在旋转磁盘上比随机读取更有效。
让我用一个例子来说明这一点，假设一个索引在一个完全相关的列上：
找到的第一个索引条目指向 table 块 42，第二个也是，第三个到第 30 个指向块 43，接下来的 20 个索引条目将指向块 44。
因此索引扫描将访问 50 个元组，但它只会从磁盘读取 3 个块，并且按顺序读取这些块（首先是块 42，然后是块 43，然后是块 44）。
如果没有相关性，50 个元组可能位于不同的 table 块中（假设 table 很大），这意味着 50 次随机磁盘读取。
所以当相关性高时索引扫描成本更低，如果相关性低则向后索引扫描成本更低。优化器使用相关性相应地调整估计成本。
当一个数据库必须执行与另一个数据库的连接时 table，它可能会从以下三种策略中选择一种：
- 顺序扫描（当我们想要大部分记录时）
- 位图索引扫描（当我们想要一些记录时）
- 索引扫描（当我们想要相对较少的记录时，具有相关索引）
这里的道理是，如果需要保留大部分记录，完全忽略索引更高效，避免I/O惩罚，只顺序读取整个table。在另一个极端，显然如果我们只需要从索引中读取几个叶节点，这将比读取整个 table.
更快我不清楚的是相关性在这里扮演什么角色，以及我们应该如何考虑它。
关注 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.)
这里是我们可以获取给定 table 中每一列的相关值的方法：
SELECT attname, correlation
FROM pg_stats
WHERE tablename = 'your_table';
据我了解，使用二级索引 总是 需要对聚簇索引执行 I/O 搜索以查找数据。据我所知，唯一能让 I/O 变好或变差的是二级索引是否非常接近磁盘上的聚簇索引。但我不清楚相关性对于确定 I/O 查找的成本有多重要，因为始终需要查找。
有人可以解释一下相关性在这里的物理含义吗？也许我的困惑是由于不了解数据库如何执行索引扫描而引起的。
首先，我们有几件事很难完全解释清楚，但我会尝试，如果其中一些对您来说已经很明显了，请原谅。
因此，随机 IOs 很昂贵，因为我们要读取整个磁盘上的随机数据块。 连续批量读取多个块要快得多（尤其是在磁驱动器上，非 ssd）
现在更进一步，您引用的文档专门讨论索引扫描，这通常是一个范围，而不是精确值。
因此，当索引相关时（可以通过相关索引对 table 进行聚类来强制执行），并且它正在寻找一个值范围 IE（其中 Id 在 1000000 和 1001000 之间），位置"scanning" 返回的（块位置）索引很可能位于磁盘上几乎相同的位置。
因此它可以转到索引 ABC，找到 1000 行并找出它需要读取的块，并可能在很少的查找次数中得到它们。 1（或更多）额外寻求获得索引是值得的。
现在，如果没有相关性并且它通过索引进行查找并发现这 1000 行都在不同的块中，在驱动器上的不同位置，它将不得不进行多达 1000 次查找找到所说的数据。从头到尾批量阅读整个 table 可能会更好。对索引的额外查找只会让情况变得更糟，并且批量读取现在不会对提高速度起到多大作用。
如果这有助于解释，请告诉我。
我认为真正的定义可以通过阅读源代码找到；-)
- 统计收集器可能使用{ctid,attribvalue}对来估计物理<-->逻辑相关性
- 计划者可以使用这些系数来估计要获取的页数
例如，这是我的 twitter-sucker-DB 运行 在 Raspberry Pi 上的统计数据： （目前大约有 350 万行）
\connect twitters
SELECT version();
SELECT count(*) from tweets;
\d tweets
SELECT attname, correlation, n_distinct -- , null_frac
FROM pg_stats
WHERE tablename = 'tweets'
AND schemaname = 'public';
You are now connected to database "twitters" as user "postgres".
version
----------------------------------------------------------------------------------------------------------------------------
PostgreSQL 9.6.9 on armv6l-unknown-linux-gnueabihf, compiled by gcc (Raspbian 6.3.0-18+rpi1+deb9u1) 6.3.0 20170516, 32-bit
(1 row)
count
---------
3525068
(1 row)
Table "public.tweets"
Column | Type | Modifiers
----------------+--------------------------+------------------------------------------------------
seq | bigint | not null default nextval('tweets_seq_seq'::regclass)
id | bigint | not null
user_id | bigint | not null
sucker_id | integer | not null default 0
created_at | timestamp with time zone |
is_dm | boolean | not null default false
body | text |
in_reply_to_id | bigint | not null default 0
parent_seq | bigint | not null default 0
is_reply_to_me | boolean | not null default false
is_retweet | boolean | not null default false
did_resolve | boolean | not null default false
is_stuck | boolean | not null default false
need_refetch | boolean | not null default false
is_troll | boolean | not null default false
fetch_stamp | timestamp with time zone | not null default now()
Indexes:
"tweets_pkey" PRIMARY KEY, btree (seq)
"tweets_id_key" UNIQUE CONSTRAINT, btree (id)
"tweets_userid_id" UNIQUE, btree (user_id, id)
"tweets_created_at_idx" btree (created_at)
"tweets_du_idx" btree (created_at, user_id)
"tweets_id_idx" btree (id) WHERE need_refetch = true
"tweets_in_reply_to_id_created_at_idx" btree (in_reply_to_id, created_at) WHERE is_retweet = false AND did_resolve = false AND in_reply_to_id > 0
"tweets_in_reply_to_id_fp" btree (in_reply_to_id)
"tweets_parent_seq_fk" btree (parent_seq)
"tweets_ud_idx" btree (user_id, created_at)
Foreign-key constraints:
"tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)
"tweets_user_id_fkey" FOREIGN KEY (user_id) REFERENCES tweeps(id)
Referenced by:
TABLE "tweets" CONSTRAINT "tweets_parent_seq_fkey" FOREIGN KEY (parent_seq) REFERENCES tweets(seq)
attname | correlation | n_distinct
----------------+-------------+------------
seq | -0.519016 | -1 #<<-- PK
id | -0.519177 | -1 #<<-- NaturalKey
user_id | -0.0994714 | 1024 # FK to tweeps, cadinality ~= 5000)
sucker_id | 0.846975 | 5 # Low Card
created_at | -0.519177 | -0.762477 # High Card
is_dm | 1 | 1
body | 0.0276537 | -0.859618
in_reply_to_id | 0.104481 | 25956 # FK to self
parent_seq | 0.954938 | 1986 # FK To self
is_reply_to_me | 1 | 2
is_retweet | 0.595322 | 2
did_resolve | 0.909326 | 2
is_stuck | 1 | 1
need_refetch | 1 | 1
is_troll | 1 | 1
fetch_stamp | -0.519572 | 95960 # High Card
(16 rows)
这里奇怪的是（大部分）升序列 {seq,id,created_at,fetch_stamp} 具有负相关性，自参考 FKs {in_reply_to_id ,parent_seq} 积极的。我的猜测是对于 n_distinct = -1 (:=unique) 列，根本不使用相关性，可能只使用符号。
相关性仅对具有总排序的数据类型的列有意义，即它支持属于 btree 访问方法的 operator family（<、<=、=、>= 和 > 运算符）。
如果较大的值倾向于出现在 table 的物理末端附近而较小的值倾向于出现在开头附近，则相关性为正。值为 1 表示值按排序顺序存储在 table 中，-1 表示它们按降序存储。
PostgreSQL 中的索引扫描是这样工作的：
第一个匹配条目位于索引中。
如visibility map indicates that the corresponding table block contains only tuples that are visible to everybody and we need no column that is not stored in the index, we have a result and continue with step 4 (if the optimizer thinks that this works for most index entries, it will plan an index only scan).
从 table 中提取相应的行并检查可见性。如果是可见的，满足过滤条件，我们就找到了结果
沿扫描方向遍历索引，找到下一个索引项，看是否满足扫描条件。如果是，则返回第二步，否则我们就完成了。
这会导致随机读取 table 个块，除非它们已经在共享缓冲区中。
现在如果相关性高，则更有可能发生两件事：
在索引扫描中找到的下一个元组与前一个元组位于同一 table 块中。然后它已经在共享缓冲区中并且不会导致读取。
总而言之，您最终会碰到更少的不同 table 块：彼此相邻的索引条目往往也彼此靠近，通常在同一个块中。
如果下一个索引条目与前一个不指向同一个table块，则很可能指向下一个table块。这导致 table 块的顺序读取，这在旋转磁盘上比随机读取更有效。
让我用一个例子来说明这一点，假设一个索引在一个完全相关的列上：
找到的第一个索引条目指向 table 块 42，第二个也是，第三个到第 30 个指向块 43，接下来的 20 个索引条目将指向块 44。
因此索引扫描将访问 50 个元组，但它只会从磁盘读取 3 个块，并且按顺序读取这些块（首先是块 42，然后是块 43，然后是块 44）。
如果没有相关性，50 个元组可能位于不同的 table 块中（假设 table 很大），这意味着 50 次随机磁盘读取。
所以当相关性高时索引扫描成本更低，如果相关性低则向后索引扫描成本更低。优化器使用相关性相应地调整估计成本。