为什么在 PostgreSQL 中获取相当大比例的 table 时位图扫描比索引扫描快？
Why is Bitmap Scan faster than Index Scan when fetching a moderately large percentage of the table in PostgreSQL?
位图扫描作者described the difference between Bitmap Heap Scan and Index Scan：
A plain indexscan fetches one tuple-pointer at a time from the index,
and immediately visits that tuple in the table. A bitmap scan fetches
all the tuple-pointers from the index in one go, sorts them using an
in-memory "bitmap" data structure, and then visits the table tuples in
physical tuple-location order. The bitmap scan improves locality of
reference to the table at the cost of more bookkeeping overhead to
manage the "bitmap" data structure --- and at the cost that the data
is no longer retrieved in index order, which doesn't matter for your
query but would matter if you said ORDER BY.
问题：
为什么在索引已经排序的情况下再次对获取的元组指针进行排序？
位图如何排序？我知道位图是什么，但我不明白它如何用于排序。
为什么在获取 table 的较大百分比时它比索引扫描更快？相反，它似乎在这个过程中增加了相当多的计算量。
Postgres 存储的 backbone 在典型安装中由 8 KB 的数据页组成。每个数据页通常包含许多元组。阅读 physical storage in the manual.
的详细信息
位图扫描中的"bitmap"是一种在数据页桶中收集元组指针的方法。在此过程中必然会丢失索引排序顺序，以支持物理排序顺序。在 "lossy mode" 中（仅当结果太大或 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
你的问题：
索引的排序丢失是因为收集命中，逐个数据页读出。
因此，结果必须在添加的排序步骤中再次排序 - 如果需要排序顺序（例如 ORDER BY）。
必须读取的数据页数是影响整体性能的最突出因素。位图索引扫描将这个数字降到最低。随着存储速度的加快，位图索引扫描的好处变得越来越小。这就是为什么准确的成本设置对于查询规划器做出正确决策至关重要。
位图扫描作者described the difference between Bitmap Heap Scan and Index Scan：
A plain indexscan fetches one tuple-pointer at a time from the index, and immediately visits that tuple in the table. A bitmap scan fetches all the tuple-pointers from the index in one go, sorts them using an in-memory "bitmap" data structure, and then visits the table tuples in physical tuple-location order. The bitmap scan improves locality of reference to the table at the cost of more bookkeeping overhead to manage the "bitmap" data structure --- and at the cost that the data is no longer retrieved in index order, which doesn't matter for your query but would matter if you said ORDER BY.
问题：
为什么在索引已经排序的情况下再次对获取的元组指针进行排序？
位图如何排序？我知道位图是什么，但我不明白它如何用于排序。
为什么在获取 table 的较大百分比时它比索引扫描更快？相反，它似乎在这个过程中增加了相当多的计算量。
Postgres 存储的 backbone 在典型安装中由 8 KB 的数据页组成。每个数据页通常包含许多元组。阅读 physical storage in the manual.
的详细信息位图扫描中的"bitmap"是一种在数据页桶中收集元组指针的方法。在此过程中必然会丢失索引排序顺序，以支持物理排序顺序。在 "lossy mode" 中（仅当结果太大或 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
你的问题：
索引的排序丢失是因为收集命中，逐个数据页读出。
因此，结果必须在添加的排序步骤中再次排序 - 如果需要排序顺序（例如
ORDER BY）。必须读取的数据页数是影响整体性能的最突出因素。位图索引扫描将这个数字降到最低。随着存储速度的加快，位图索引扫描的好处变得越来越小。这就是为什么准确的成本设置对于查询规划器做出正确决策至关重要。