如果在该字段上构建b-tree索引,PostgreSQL如何执行ORDER BY？

Question

我有一张桌子bsort:

CREATE TABLE bsort(a int, data text);

这里data可能不完整.换句话说,一些元组可能没有data价值.

然后我在表上构建一个b树索引:

CREATE INDEX ON bsort USING BTREE(a);

现在,如果我执行此查询:

SELECT * FROM bsort ORDER BY a;

PostgreSQL是否使用nlogn复杂性对元组进行排序,还是直接从b-tree索引获取顺序？

Answer 1

对于像这样的简单查询,Postgres将使用索引扫描并按顺序从索引中检索容易排序的元组.由于其MVCC模型, Postgres必须始终访问"堆"(数据页),以验证条目实际上对当前事务可见.在仅索引扫描上引用Postgres Wiki:

PostgreSQL索引不包含可见性信息.也就是说,不能直接确定当前事务是否可以看到任何给定元组,这就是为什么实现仅索引扫描需要这么长时间的原因.

最终在9.2版中发生了:仅索引扫描.手册:

如果索引存储原始索引数据值(而不是它们的某些有损表示),则支持仅索引扫描很有用,其中索引返回实际数据而不仅仅是TID堆元组的数据.如果可见性图表显示TID在全部可见页面上,则这将仅避免I/O. 否则必须访问堆元组以检查MVCC可见性.但这并不是访问方法的关注点.

所以现在它取决于表的可见性映射,是否可以进行仅索引扫描.如果索引中包含所有涉及的列,则只有一个选项.否则,在任何情况下都必须访问堆(另外).仍然不需要排序步骤.

这就是为什么我们现在有时会将无用的列附加到索引中.与data示例中的列一样:

CREATE INDEX ON bsort USING BTREE(a, data);

它使索引更大(取决于)并且维护和使用更加昂贵,以用于不允许仅索引扫描的其他目的.因此,data如果您从中获取仅索引扫描,则只附加该列.索引中列的顺序很重要:

每个文档的仅索引扫描的好处:

如果已知页面上的所有元组都可见,则可以跳过堆提取.这在可见性映射可以阻止磁盘访问的大型数据集中最为明显.可见性映射远小于堆,因此即使堆非常大,也可以轻松地进行缓存.

VACUUM如果您运行autovacuum(现代Postgres中的默认设置),将自动维护可见性图.细节:

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

一旦抽真空,只读表就可以进行仅索引扫描.
已修改的数据页在可见性映射中丢失其"全可见"标志,直到下一个VACUUM(以及所有较旧的tansactions完成),因此它取决于写入操作和VACUUM频率.

如果某些涉及的页面被标记为全部可见,则仍然可以进行仅部分索引扫描.但是如果必须访问堆,访问方法"索引扫描"会稍微便宜一些.因此,如果目前有太多页面是脏的,Postgres将完全切换到更便宜的索引扫描.Postgres Wiki再次发布:

随着规划人员预计需要的堆取(或"访问次数")的数量增加,规划人员最终将得出结论,仅索引扫描是不可取的,因为它不是最便宜的可能计划.其成本模型.仅索引扫描的价值完全在于它们允许我们忽略堆访问(如果只是部分)并最小化I/O的潜力.