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

我不了解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就像是顺序扫描,但仅扫描表的适当部分吗?

评论

我在这里写了一些解释:stackoverflow.com/q/33100637/398670

@CraigRinger似乎我没有正确解释我不了解的内容。当然,正如您所解释的,PostgreSQL有一个位图,PostgreSQL通过该位图顺序读取表。我不明白它如何找出特定位图指定的实际块,例如001001010101011010101.或实际上并不重要,我们所要知道的只是可以通过位图以非常快速的方式找到一个块...?

嗯,您可能会误解“位图”在这里的含义。让我继续进行编辑。

@CraigRinger也许我是从他们的定义中提取的。

#1 楼


PostgreSQL如何仅通过位图了解有关行的物理顺序的任何信息?


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

因此,当进行位图堆扫描时,它仅进行线性表扫描,读取位图


还是生成位图以便可以轻松地将其任何元素映射到指向页面的指针? />

不,位图与堆页面1:1对应。

我在这里写了更多内容。


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

并不是为每个堆页面,每个读取的索引或诸如此类创建的像“ 101011”这样的字符串。

整个位图是一个单个位数组,具有与要扫描的关系中的堆页面一样多的位。

第一次索引扫描会创建一个位图,从所有条目0(false)开始。只要找到与搜索条件匹配的索引条目,该索引条目所指向的堆地址就会作为位图中的偏移量查找,并将该位设置为1(true)。因此,位图索引扫描不是直接查找堆页面,而是查找位图中的相应位位置。

第二次及以后的位图索引扫描对其他索引和搜索执行相同的操作条件。

然后将每个位图与在一起。所产生的位图在每个堆页面中都有一个位,其中只有在所有单个位图索引扫描中这些位都为真时,这些位才为真,即,与每个索引扫描匹配的搜索条件。这些是我们唯一需要加载和检查的堆页面。由于每个堆页面可能包含多行,因此我们必须检查每一行,看它是否符合所有条件-这就是“重新检查条件”部分所要解决的问题。所有这些都是索引条目中的元组地址指向行的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行以上,并且不一定都符合条件。

评论


嗯,这就是填充位图的含义。

–圣安东尼奥
15-10-28在7:50



@ St.Antario我添加了图形来解释

–克雷格·林格(Craig Ringer)
15年10月28日在7:58

让我澄清一下有关位图扫描的另一件事。您说过,我们有一个1:1的位图来堆页面,并且可以通过位图中的位索引确定堆页面。由于该关系可能以不连续的顺序(非群集的)包含磁盘上的页面,因此还不清楚如何仅通过位图中的偏移量来确定页面的地址。我想,规划者知道如何为给定关系按偏移量计算页面地址。真的吗?

–圣安东尼奥
16-3-30在6:18



因此,我们必须将所有页面都放在驱动器上。而且,关系的数据可能散布在两个或多个驱动器上(因此很难想象关系页面的线性顺序),因此很难确定下一页的实际偏移量。因为我相信“偏移”是指与驱动器上的物理位置相对应的实际物理偏移。

–圣安东尼奥
16-3-30在6:29



PostgreSQL一点也不关心驱动器。它只关心文件系统上的文件。关系的逻辑文件是线性且连续的,这就是位图结束的地方。 (文件可能有多个扩展区,但是它们被视为连续附加,并且位图覆盖了所有扩展区)。您正在查看错误的抽象级别。 (顺便提一下,位图索引扫描中的位图也不是由计划程序计算的,它是btree索引访问方法的一部分,与计划程序相比,与执行器的关系更大。)

–克雷格·林格(Craig Ringer)
16-3-30在6:36



#2 楼

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

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



位图堆扫描从位图索引扫描中请求元组。
位图索引扫描将扫描根据条件索引的方式几乎与正常索引扫描中的方式相同。但是,与其返回与堆数据相对应的TID(由页号和其中的偏移量组成),而是将这些TID添加到位图中。为了简单理解,您可以考虑将该位图包含所有页面的哈希值(基于页面编号进行哈希处理),并且每个页面条目均包含该页面内所有偏移量的数组。
然后,位图堆扫描读取该位图以获取堆数据。对应于存储的页码和偏移量。然后检查可见性,资格等,并根据所有这些检查的结果返回元组。