尽管在列上排序了索引，但为什么查询计划仍然对表进行排序？

Question

我正在使用 Postgres 9.1 我要加入两个表：

wikidb=> \d page
                         Table "public.page"
        Column         |     Type      |          Modifiers           
-----------------------+---------------+------------------------------
 page_id               | bigint        | not null
 page_namespace        | integer       | not null default 0
 page_title            | text          | not null default ''::text
 [...]
Indexes:
    [...]
    "page_page_namespace_page_title_idx" UNIQUE, btree (page_namespace, page_title)

wikidb=> \d pagelinks
                 Table "public.pagelinks"
      Column       |  Type   |         Modifiers          
-------------------+---------+----------------------------
 pl_from           | bigint  | not null default 0::bigint
 pl_namespace      | integer | not null default 0
 pl_title          | text    | not null default ''::text
 [...]
Indexes:
    [...]
    "pagelinks_pl_namespace_pl_title_pl_from_idx" btree (pl_namespace, pl_title, pl_from)

请注意两者如何在 (namespace, title) 列上都有索引。我有兴趣找出 pagelinks 表中有多少 (pl_namespace, pl_title) 对没有在页表中显示为 (page_namespace, page_title)。

如果我使用连接，那么我会得到以下计划：

wikidb=> explain SELECT COUNT(*)
FROM pagelinks
LEFT OUTER JOIN page
  ON page.page_namespace = pagelinks.pl_namespace AND
     page.page_title = pagelinks.pl_title
WHERE page.page_namespace IS NULL AND page.page_title IS NULL;
                                                   QUERY PLAN                                                    
-----------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=1310748.56..1310748.57 rows=1 width=0)
   ->  Merge Anti Join  (cost=1189384.02..1310748.56 rows=1 width=0)
         Merge Cond: ((pagelinks.pl_title = page.page_title) AND (pagelinks.pl_namespace = page.page_namespace))
         ->  Sort  (cost=1144343.89..1164498.31 rows=8061768 width=19)
               Sort Key: pagelinks.pl_title, pagelinks.pl_namespace
               ->  Seq Scan on pagelinks  (cost=0.00..219551.68 rows=8061768 width=19)
         ->  Sort  (cost=45038.32..45975.52 rows=374880 width=20)
               Sort Key: page.page_title, page.page_namespace
               ->  Seq Scan on page  (cost=0.00..10331.80 rows=374880 width=20)
(9 rows)

如您所见，它对两个表中的每一个进行排序并合并它们。如果索引已经按排序顺序包含两列，我不明白为什么要这样做。

有什么解释吗？

Answer 1

PostgreSQL认为排序合并更快。在我的 9.1 上，它实际上比走两个索引都要快。您可以亲自尝试一下set enable_sort to off;，看看它给出了什么计划，以及该计划需要多长时间才能运行。

排序非常有效。遍历索引在 9.1 中效率低下，因为它仍然需要访问表以确保该行实际上是可见的。索引不存储可见性信息。9.2 引入了仅索引扫描，解决了部分问题。

此外，索引叶页不一定是逻辑顺序，因此按逻辑顺序遍历索引会导致大量随机 IO。（当然，检查表的可见性也可以通过索引扫描。）

自 9.1 以来已经进行了很多改进。