Postgres 有时对 WHERE a IN (...) ORDER BY b LIMIT N 使用劣等索引

Question

我们有一个包含约 50 亿行的 PostgreSQL 表，它养成了一个讨厌的习惯，即缺少正确的索引并对某些LIMIT操作进行主键扫描。

问题通常出现在一个ORDER BY .. LIMIT ..子句（Django 分页中的常见模式）上，其中LIMIT是索引匹配的结果的一些相对较小的子集。一个极端的例子是这样的：

SELECT * FROM mcqueen_base_imagemeta2 
  WHERE image_id IN ( 123, ... )
  ORDER BY id DESC
  LIMIT 1;

其中该IN子句中的项目约为 20，索引匹配的总行数image_id为 16。

在EXPLAIN表明，它错过了image_id指数，而是确实5B行的PK扫描：

限制（成本=0.58..4632.03 行=1 宽度=28）
   -> 在 mcqueen_base_imagemeta2 上使用 mcqueen_base_imagemeta2_pkey 向后扫描索引（成本=0.58..364597074.75 行=78722 宽度=28）
         过滤器：(image_id = ANY ('{123, ...}'::bigint[]))

如果LIMIT增加到2，它会按预期工作：

限制（成本=7585.92..7585.93 行=2 宽度=28）
   -> 排序（成本=7585.92..7782.73 行=78722 宽度=28）
         排序键：id DESC
         -> 在 mcqueen_base_imagemeta2 上使用 mcqueen_base_imagemeta2_image_id_616fe89c 进行索引扫描（成本=0.58..6798.70 行=78722 宽度=28）
               索引条件：(image_id = ANY ('{123, ...}'::bigint[]))

这也发生在索引匹配约 3000 行且限制设置为 100 的查询中，因此在现实世界的 REST API 分页中很容易发生这种情况。

表定义为：

mcqueen=# \d mcqueen_base_imagemeta2
                                       Table "public.mcqueen_base_imagemeta2"
      Column       |           Type           |                              Modifiers                               
-------------------+--------------------------+----------------------------------------------------------------------
 id                | bigint                   | not null default nextval('mcqueen_base_imagemeta2_id_seq'::regclass)
 created_at        | timestamp with time zone | not null
 image_id          | bigint                   | not null
 key_id            | smallint                 | not null
 source_version_id | smallint                 | not null
Indexes:
    "mcqueen_base_imagemeta2_pkey" PRIMARY KEY, btree (id)
    "mcqueen_base_imagemeta2_image_id_616fe89c" btree (image_id)
    "mcqueen_base_imagemeta2_key_id_a4854581" btree (key_id)
    "mcqueen_base_imagemeta2_source_version_id_f9b0513e" btree (source_version_id)
Foreign-key constraints:
    "mcqueen_base_imageme_image_id_616fe89c_fk_mcqueen_b" FOREIGN KEY (image_id) REFERENCES mcqueen_base_image(id) DEFERRABLE INITIALLY DEFERRED
    "mcqueen_base_imageme_key_id_a4854581_fk_mcqueen_b" FOREIGN KEY (key_id) REFERENCES mcqueen_base_metakey(id) DEFERRABLE INITIALLY DEFERRED
    "mcqueen_base_imageme_source_version_id_f9b0513e_fk_mcqueen_b" FOREIGN KEY (source_version_id) REFERENCES mcqueen_base_metasourceversion(id) DEFERRABLE INITIALLY DEFERRED

在调优方面，我充其量只是一个新手，但我认为统计信息的默认值不符合该表的大小，因此它天真地认为 PK 扫描比索引扫描快。

Answer 1

为什么？

对于 a LIMIT 1，Postgres 可能估计它会更快地遍历支持 a 的索引ORDER BY并继续过滤直到找到第一行。只要超过几行符合条件并且其中之一根据ORDER BY. 但是，如果没有排位赛提前弹出，则（非常）慢，或者如果根本没有排位赛排位，甚至是最坏的情况。类似的任何小LIMIT.

Postgres 收集有关最常见值（MCV 列表）的统计信息，但不会收集最不常见的值 - 出于显而易见的原因，这太多而无用。默认情况下，它没有列之间相关性的统计信息。（虽然可以手动创建，但无论如何都不适合您的用例，因为 ID 号通常是不相关的。）

所以 Postgres 必须基于通用估计做出决定。很难确定从一个索引切换到另一个索引的最佳位置。然而，对于像image_id IN (123, ... )许多项目这样的谓词，这变得更加困难，而且大多数通常是罕见的或非常罕见的，甚至不存在。但是如果你在列表中放入足够多的数字，Postgres 最终会期望遍历另一个索引会更快地找到第一个命中。

解决方案？

您可以通过更大的统计目标来稍微改善这种情况：

ALTER TABLE mcqueen_base_imagemeta2 ALTER image_id SET STATISTICS 2000;

这（除其他外）增加了列的 MCV 列表的大小，并有助于识别更多（更少）常见的值。但这不是问题的通用解决方案，并且会使ANALYZE和查询计划的成本更高一些。有关的：

• 检查 PostgreSQL 中的统计目标

升级到最新版本（即将成为 Postgres 12）也有帮助，因为总体性能变得更好，规划器更智能。

解决方法有多种技术，具体取决于基数、值频率、访问模式，...ORDER BY像Laurenz 演示的那样完全禁用索引是一种激进的解决方法 - 这可能会适得其反，或者非常常见image_id，ORDER BY实际上索引会，要快得多。

有关的：

• 空间索引可以帮助“范围 - 按 - 限制”查询

您的情况的解决方法

应该适用于给定的数字：50 亿行，image_id过滤器列表中大约 20 行， small LIMIT。最有效LIMIT 1的短列表，但适用于任何小型LIMIT且易于管理的列表大小：

SELECT m.*
FROM   unnest( '{123, ...}'::bigint[]) i(image_id)
CROSS  JOIN LATERAL (
   SELECT m.id
   FROM   mcqueen_base_imagemeta2 m
   WHERE  m.image_id = i.image_id
   ORDER  BY m.id DESC
   LIMIT  1  -- or N
   ) m
ORDER  BY id DESC
LIMIT  1;  -- or N

提供您的列表作为数组和unnest()。或者使用VALUES表达式。有关的：

• 使用大 IN 优化 Postgres 查询

使用多列索引来支持这一点至关重要(image_id, id DESC)！

然后，您可以mcqueen_base_imagemeta2_image_id_616fe89c仅删除 上的现有索引(image_id)。看：

• 复合索引是否也适用于第一个字段的查询？

这应该会导致每个image_id. 最后，（非常）便宜的排序步骤。

为每个获取 N 行image_id保证我们拥有外部查询中所需的所有行。如果您有元知识，即image_id结果中每个单行的行数较少，则可以相应地减少嵌套LIMIT。

在旁边

（Django分页中的常见模式）

用LIMIT和分页OFFSET？第一页还可以，但在那之后它只是一个坏主意。

• 大表的高效分页
• 加入联结表以实现高效排序/分页的推荐方法是什么？

Answer 2

它认为它会找到 78722，但它真的找到了 16，所以这会导致一些糟糕的计划。

当 stats 表的 MCV 列表中不存在 in-list 中的值时，它会使用 n_distinct 值来猜测它们的频率，这可能很遥远（您没有回答我的问题）。这样做的方法是取未包含在 MCV 频率列表中的元组数量，并将其除以未在 MCV 列表中列出的不同值的数量。所以基本上ntuples * (1-sum of MCF) / (n_distinct - length of MCF)。这个简化的公式忽略了 NULL。

正如@ErwinBrandstetter 所建议的那样，您可以通过增加统计样本大小来增加 MCV 列表的大小来改善这种情况。这也可能会提高 n_distinct 估计的准确性。但是对于 60 亿行，可能无法将样本量增加足够多。此外，如果 image_id 与可能出现在同一页面中的重复值聚集在一起，那么 PostgreSQL 使用的采样方法在计算 n_distinct 时非常有偏差，并且仅通过增加样本大小就无法修复。

解决此问题的更简单方法可能是手动修复 n_distinct：

alter table mcqueen_base_imagemeta2 alter column image_id set (n_distinct=1000000000);
analyze mcqueen_base_imagemeta2;

这种方法不会像增加样本大小那样增加 ANALYZE 所需的时间或存储空间，而且也更有可能成功。