为什么在PostgreSQL中获取相当大比例的表时，位图扫描比索引扫描更快？

Question

Bitmap Scan described the difference between Bitmap Heap Scan and Index Scan的作者：

普通的索引可以从索引中一次获取一个元组指针，并立即访问表中的元组。位图扫描一次性从索引中获取所有元组指针，使用内存中的“位图”数据结构对它们进行排序，然后以物理元组位置顺序访问表元组。位图扫描改进了对表的引用的局部性，代价是管理“位图”数据结构的更多簿记开销 - 并且代价是不再按索引顺序检索数据，这对您来说无关紧要查询，但如果你说ORDER BY会很重要。

问题：

1. 当索引已经排序时，为什么它会再次对获取的元组指针进行排序？
2. 它如何与位图排序？我知道位图是什么，但我不明白它是如何用于排序的。
3. 为什么在获取相当大比例的表时，它比索引扫描更快？相反，它似乎为这个过程添加了相当多的计算。

Answer 1

Postgres存储的主干由典型安装中的8千字节的数据页组成。每个数据页通常包含许多元组。阅读physical storage in the manual的详细信息。

位图扫描中的“位图”是一种在数据页的桶中收集元组指针的方法。索引排序顺序在此过程中必然会丢失，以支持物理排序顺序。在“有损模式”（仅当结果如此巨大或workmem如此小以至于微小的位图不适合时才会出现）仅保留块编号并丢弃相应的元组索引。

之后，每个数据页面仅从存储器访问一次以提取（可能）多个元组并按物理顺序，这对于某些类型的存储也很重要。在有损模式中，必须通过重新检查索引条件来过滤每个已识别页面的元组;可以使用收集的元组索引直接检索其他元组。

在索引扫描中，如果多个元组最终存储在同一数据页中，则可能必须多次访问每个页面。实际过程更加复杂。有关：

• Postgres not using index when index scan is much better option
• Index usage on a temporary table
• “Recheck Cond:” line in query plans with a bitmap index scan
• How do I decompose ctid into page and row numbers?
• Keep PostgreSQL from sometimes choosing a bad query plan

对你的问题：

1. 由于收集命中并通过数据页读出数据页，索引的排序将丢失。
2. 因此，必须在添加的排序步骤中再次对结果进行排序 - 如果需要排序顺序（例如，通过ORDER BY）。
3. 必须读取的数据页数是整体性能的最重要因素。位图索引扫描将该数量减少到最小。通过更快的存储，位图索引扫描的优势变得更小。这就是为什么准确的成本设置对于查询计划员做出正确决策至关重要的原因。