postgresql - PostgreSQL 如何在字段上执行带有 b 树索引的 ORDER BY？

Question

我有一个表bsort:

CREATE TABLE bsort(a int, data text);

此处数据可能不完整。换句话说，一些元组可能没有 data 值。

然后我在表上建立一个 b-tree 索引:

CREATE INDEX ON bsort USING BTREE(a);

现在如果我执行这个查询:

SELECT * FROM bsort ORDER BY a;

PostgreSQL 是对具有 nlogn 复杂度的元组进行排序，还是直接从 b-tree 索引中获取顺序？

Answer 1

对于像这样的简单查询，Postgres 将使用 index scan并按顺序从索引中检索易于排序的元组。由于其 MVCC model Postgres 必须始终另外访问“堆”(数据页)以验证条目对当前事务是否确实可见。引用 Postgres Wiki on index-only scans :

PostgreSQL indexes do not contain visibility information. That is, it is not directly possible to ascertain if any given tuple is visible to the current transaction, which is why it has taken so long for index-only scans to be implemented.

这最终发生在 9.2 版本中: index-only scans 。 The manual:

If the index stores the original indexed data values (and not some lossy representation of them), it is useful to support index-only scans, in which the index returns the actual data not just the TID of the heap tuple. This will only avoid I/O if the visibility map shows that the TID is on an all-visible page; else the heap tuple must be visited anyway to check MVCC visibility. But that is no concern of the access method's.

visibility map 决定是否可以进行仅索引扫描。如果所有涉及的列值都包含在索引中，则只有一个选项。否则，无论如何都必须(另外)访问堆。 仍然不需要排序步骤。

这就是为什么我们现在有时会将无用的列附加到索引中。喜欢 data您示例中的列:

CREATE INDEX ON bsort (a, data);  -- btree is the default index type

它使索引更大(取决于)并且维护和用于其他目的的成本更高。所以只附加 data如果您从中获得仅索引扫描，则列。索引中列的顺序很重要:

• Working of indexes in PostgreSQL
• Is a composite index also good for queries on the first field?

从 Postgres 11 开始，也有 INCLUDE 的“覆盖索引”关键词。喜欢:

CREATE INDEX ON bsort (a) INCLUDE (data);

参见:

• Does a query with a primary key and foreign keys run faster than a query with just primary keys?

仅索引扫描的好处，per documentation:

If it's known that all tuples on the page are visible, the heap fetch can be skipped. This is most noticeable on large data sets where the visibility map can prevent disk accesses. The visibility map is vastly smaller than the heap, so it can easily be cached even when the heap is very large.

可见性 map 由 VACUUM 维护如果你有autovacuum，这会自动发生正在运行(现代 Postgres 中的默认设置)。详情:

• Are regular VACUUM ANALYZE still recommended under 9.1?

但是在对表的写操作和下一个 VACUUM 之间有一些延迟运行。它的要点:

• 只读表在清理后随时准备进行仅索引扫描。
• 被修改的数据页在可见性映射中失去它们的“全部可见”标志，直到下一个VACUUM。 (并且所有旧的交易都已完成)，因此这取决于写操作与 VACUUM 之间的比率频率。

如果涉及的页面一些被标记为全部可见，则部分仅索引扫描仍然是可能的。但是如果无论如何都要访问堆，访问方法“索引扫描”会更便宜一些。所以如果当前有太多页面是脏的，Postgres 将完全切换到更便宜的索引扫描。 The Postgres Wiki again :

As the number of heap fetches (or "visits") that are projected to be needed by the planner goes up, the planner will eventually conclude that an index-only scan isn't desirable, as it isn't the cheapest possible plan according to its cost model. The value of index-only scans lies wholly in their potential to allow us to elide heap access (if only partially) and minimise I/O.