理解“位图堆扫描”和“位图索引扫描”

Question

我将尝试通过以下示例来解释我的误解。

我不明白基本面的Bitmap Heap Scan Node。考虑SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';计划如下的查询：

Bitmap Heap Scan on customers  (cost=25.76..61.62 rows=10 width=13) (actual time=0.077..0.077 rows=2 loops=1)
  Recheck Cond: (((username)::text < 'user100'::text) AND (customerid < 1000))
  ->  BitmapAnd  (cost=25.76..25.76 rows=10 width=0) (actual time=0.073..0.073 rows=0 loops=1)
        ->  Bitmap Index Scan on ix_cust_username  (cost=0.00..5.75 rows=200 width=0) (actual time=0.006..0.006 rows=2 loops=1)
              Index Cond: ((username)::text < 'user100'::text)
        ->  Bitmap Index Scan on customers_pkey  (cost=0.00..19.75 rows=1000 width=0) (actual time=0.065..0.065 rows=999 loops=1)
              Index Cond: (customerid < 1000)

我对这个节点的理解：

正如那里所解释的，bitmap heap scan读取表按顺序阻塞，因此它不会产生随机表访问开销，而这只是Index Scan.

完成后Index Scan，PostgreSQL 不知道如何以最佳方式获取行，以避免不必要的heap blocks reads（或hits是否有热缓存）。因此，要弄清楚它会生成Bitmap Index Scan称为结构 ( )的结构bitmap，在我的情况下，它是通过生成索引的两个位图并执行BITWISE AND. 由于位图已经生成，它现在可以按顺序以最佳方式读取表，避免不必要的heap I/O-operations.

这就是很多问题出现的地方。

问题：我们只有一个位图。PostgreSQL 如何仅通过位图了解行的物理顺序？或者生成位图以便它的任何元素都可以轻松映射到指向页面的指针？如果是这样，那就解释了一切，但这只是我的猜测。

那么，我们能不能简单地说这bitmap heap scan -> bitmap index scan就像一个顺序扫描，但只对表的适当部分进行扫描？

Answer 1

PostgreSQL 如何仅通过位图了解行的物理顺序？

位图是每个堆页一位。位图索引扫描根据索引条目指向的堆页面地址设置位。

因此，当它进行位图堆扫描时，它只是进行线性表扫描，读取位图以查看它是否应该打扰特定页面或搜索它。

或者生成位图以便它的任何元素都可以轻松映射到指向页面的指针？

不，位图对应于 1:1 堆页面。

我在这里写了更多。

好的，看起来您可能误解了“位图”在这种情况下的含义。

它不是为每个堆页面或每个索引读取或其他任何内容创建的像“101011”这样的位字符串。

整个位图是一个位数组，其位数与正在扫描的关系中的堆页数一样多。

第一次索引扫描创建一个位图，从所有条目 0 (false) 开始。每当找到与搜索条件匹配的索引条目时，该索引条目指向的堆地址将作为位图中的偏移量进行查找，并将该位设置为 1（真）。因此位图索引扫描不是直接查找堆页面，而是查找位图中对应的位位置。

第二次和进一步的位图索引扫描对其他索引和对它们的搜索条件执行相同的操作。

然后将每个位图进行 AND 运算。生成的位图对于每个堆页面都有一个位，其中这些位只有在所有单独位图索引扫描中都为真时才为真，即每个索引扫描都匹配搜索条件。这些是我们唯一需要加载和检查的堆页面。由于每个堆页面可能包含多行，因此我们必须检查每一行以查看它是否符合所有条件 - 这就是“重新检查条件”部分的内容。

理解这一切的一个关键点是索引条目中的元组地址指向行的ctid，它是堆页号和堆页内偏移量的组合。位图索引扫描会忽略偏移量，因为它无论如何都会检查整个页面，并在该页面上的任何行与条件匹配时设置该位。

图例

Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.


Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not

Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+

一旦位图被按位创建并对其执行：

+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
            |       |              |
            v       v              v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+

然后位图堆扫描会寻找每个页面的开头并读取页面：

+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
            |       |              |
            ------------------------
            only these pages read

然后根据条件重新检查每个读取页面，因为每页可能有 >1 行，并且不一定都与条件匹配。

Answer 2

请参阅我的博客文章 https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 有关 PostgreSQL 中位图扫描的详细说明。

位图扫描的总体快速功能概述：

1. 位图堆扫描向位图索引扫描请求元组。

2. 位图索引扫描按照条件扫描索引，几乎与普通索引扫描的方式相同。但它不是返回与堆数据对应的 TID（由页号和其中的偏移量组成），而是将这些 TID 添加到位图中。为了简单理解，您可以认为该位图包含所有页面的散列（基于页面编号进行散列），并且每个页面条目包含该页面内所有偏移量的数组。

3. 然后 Bitmap Heap Scan 读取位图以获取与存储的页号和偏移量对应的堆数据。然后它检查可见性、资格等，并根据所有这些检查的结果返回元组。