PostgreSQL bitmapAnd, bitmapOr, bitmap index scan, bitmap heap scan

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云原生数据库 PolarDB 分布式版,标准版 2核8GB
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
简介:

标签

PostgreSQL , bitmap index scan , bitmap heap scan


背景

在PostgreSQL中,多个单列索引是可以用在组合查询SQL中的,也就是说实现了bitmap scan。

比如

select * from tbl where c1=1 and c2=1 or c3=1;

用到了3列,如果这3列分别有一个索引,那么PostgreSQL会使用这三个索引的bitmap scan。

PostgreSQL是如何处理多个组合条件的BITMAP SCAN的呢?

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 scan原理

对于每个查询条件,在对应索引中找到符合条件的堆表PAGE,每个索引构造一个bitmap串。

在这个bitmap串中,每一个BIT位对应一个HEAP PAGE,代表这个HEAP PAGE中有符合该条件的行。

根据条件的多少,组成了多个bitmap。

例如 a=1 or a=2 是两个bitmap。

postgres=# explain select * from tbl where id in (1,2,3);  -- in 可以直接使用index扫描  
                                QUERY PLAN                                  
--------------------------------------------------------------------------  
 Index Scan using idx_tbl on tbl  (cost=0.29..257.15 rows=10000 width=12)  
   Index Cond: (id = ANY ('{1,2,3}'::integer[]))  
(2 rows)  

postgres=# explain select * from tbl where id =1 or id=2 or id=3;  
                                    QUERY PLAN                                      
----------------------------------------------------------------------------------  
 Bitmap Heap Scan on tbl  (cost=124.97..354.97 rows=10000 width=12)  
   Recheck Cond: ((id = 1) OR (id = 2) OR (id = 3))  
   ->  BitmapOr  (cost=124.97..124.97 rows=10000 width=0)  
         ->  Bitmap Index Scan on idx_tbl  (cost=0.00..114.28 rows=10000 width=0)  
               Index Cond: (id = 1)  
         ->  Bitmap Index Scan on idx_tbl  (cost=0.00..1.59 rows=1 width=0)  
               Index Cond: (id = 2)  
         ->  Bitmap Index Scan on idx_tbl  (cost=0.00..1.59 rows=1 width=0)  
               Index Cond: (id = 3)  
(9 rows)  

postgres=# explain select * from tbl where id=1 and id=2 or id=3;  
                                 QUERY PLAN                                   
----------------------------------------------------------------------------  
 Bitmap Heap Scan on tbl  (cost=3.19..4.51 rows=1 width=12)  
   Recheck Cond: (((id = 1) AND (id = 2)) OR (id = 3))  
   ->  BitmapOr  (cost=3.19..3.19 rows=1 width=0)  
         ->  Bitmap Index Scan on idx_tbl  (cost=0.00..1.59 rows=1 width=0)  
               Index Cond: ((id = 1) AND (id = 2))  -- and 可以合并  
         ->  Bitmap Index Scan on idx_tbl  (cost=0.00..1.59 rows=1 width=0)  
               Index Cond: (id = 3)  
(7 rows)  

不同字段也一样。

postgres=# create table t12 (c1 int, c2 int, c3 int);  
CREATE TABLE  
postgres=# create index t12_c1 on t12 (c1);  
CREATE INDEX  
postgres=# create index t12_c2 on t12 (c2);  
CREATE INDEX  
postgres=# create index t12_c3 on t12 (c3);  
CREATE INDEX  

postgres=# explain select * from t12 where c1=1 and c2=1 or c3=1;  
                                    QUERY PLAN                                      
----------------------------------------------------------------------------------  
 Bitmap Heap Scan on t12  (cost=4.84..12.36 rows=10 width=12)  
   Recheck Cond: (((c2 = 1) AND (c1 = 1)) OR (c3 = 1))  
   ->  BitmapOr  (cost=4.84..4.84 rows=10 width=0)  
         ->  BitmapAnd  (cost=3.31..3.31 rows=1 width=0)  
               ->  Bitmap Index Scan on t12_c2  (cost=0.00..1.53 rows=10 width=0)  
                     Index Cond: (c2 = 1)  
               ->  Bitmap Index Scan on t12_c1  (cost=0.00..1.53 rows=10 width=0)  
                     Index Cond: (c1 = 1)  
         ->  Bitmap Index Scan on t12_c3  (cost=0.00..1.53 rows=10 width=0)  
               Index Cond: (c3 = 1)  
(10 rows)  

postgres=# explain select * from t12 where c1=1 and c2=1 or c3=1 or c3=2;  
                                    QUERY PLAN                                      
----------------------------------------------------------------------------------  
 Bitmap Heap Scan on t12  (cost=6.38..16.78 rows=20 width=12)  
   Recheck Cond: (((c2 = 1) AND (c1 = 1)) OR (c3 = 1) OR (c3 = 2))  
   ->  BitmapOr  (cost=6.38..6.38 rows=20 width=0)  
         ->  BitmapAnd  (cost=3.31..3.31 rows=1 width=0)  
               ->  Bitmap Index Scan on t12_c2  (cost=0.00..1.53 rows=10 width=0)  
                     Index Cond: (c2 = 1)  
               ->  Bitmap Index Scan on t12_c1  (cost=0.00..1.53 rows=10 width=0)  
                     Index Cond: (c1 = 1)  
         ->  Bitmap Index Scan on t12_c3  (cost=0.00..1.53 rows=10 width=0)  
               Index Cond: (c3 = 1)  
         ->  Bitmap Index Scan on t12_c3  (cost=0.00..1.53 rows=10 width=0)  
               Index Cond: (c3 = 2)  
(12 rows)  

在生成多个bitmap串后,对这些bitmap串执行BIT & | 操作,得到一个新的BIT串,然后根据这个BIT串,顺序搜索bit=1 (bit=0的heap page不会被扫描) 的对应的数据块(也就是bitmap heap scan)。

因为bitmap index scan返回的是块级别的bit串,所以在bitmap heap scan时还需要recheck。即搜索对应的heap page里的所有tuple(行),同时对bitmap index scan的条件进行再次过滤。

stackoverflow相关问题

问题

How does PostgreSQL knows by just a bitmap anything about rows' physical order?  

回答

The bitmap is one bit per heap page. The bitmap index scan sets the bits based on the heap page address that the index entry points to.  

So when it goes to do the bitmap heap scan, it just does a linear table scan, reading the bitmap to see whether it should bother with a particular page or seek over it.  

问题

Or generates the bitmap so that any element of it can be mapped to the pointer to a page easily?  

回答

No, the bitmap corresponds 1:1 to heap pages.  

I wrote some more on this here.  

OK, it looks like you might be misunderstanding what "bitmap" means in this context.  

It's not a bit string like "101011" that's created for each heap page, or each index read, or whatever.  

The whole bitmap is a single bit array, with as many bits as there are heap pages in the relation being scanned.  

One bitmap is created by the first index scan, starting off with all entries 0 (false). Whenever an index entry that matches the search condition is found, the heap address pointed to by that index entry is looked up as an offset into the bitmap, and that bit is set to 1 (true). So rather than looking up the heap page directly, the bitmap index scan looks up the corresponding bit position in the bitmap.  

The second and further bitmap index scans do the same thing with the other indexes and the search conditions on them.  

Then each bitmap is ANDed together. The resulting bitmap has one bit for each heap page, where the bits are true only if they were true in all the individual bitmap index scans, i.e. the search condition matched for every index scan. These are the only heap pages we need to bother to load and examine. Since each heap page might contain multiple rows, we then have to examine each row to see if it matches all the conditions - that's what the "recheck cond" part is about.  

One crucial thing to understand with all this is that the tuple address in an index entry points to the row's ctid, which is a combination of the heap page number and the offset within the heap page. A bitmap index scan ignores the offsets, since it'll check the whole page anyway, and sets the bit if any row on that page matches the condition.  

Graphical example  

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  
+---------------------------------------------+  
Once the bitmaps are created a bitwise AND is performed on them:  

+---------------------------------------------+  
|100000000001000000010000000000000111100000000| bitmap 1  
|000001000001000100010000000001000010000000010| bitmap 2  
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&  
|000000000001000000010000000000000010000000000| Combined bitmap  
+-----------+-------+--------------+----------+  
            |       |              |  
            v       v              v  
Used to scan the heap only for matching pages:  
+---------------------------------------------+  
|___________X_______X______________X__________|  
+---------------------------------------------+  
The bitmap heap scan then seeks to the start of each page and reads the page:  

+---------------------------------------------+  
|___________X_______X______________X__________|  
+---------------------------------------------+  
seek------->^seek-->^seek--------->^  
            |       |              |  
            ------------------------  
            only these pages read  
and each read page is then re-checked against the condition since there can be >1 row per page and not all necessarily match the condition.  

哪些查询可能会使用bitmap index scan

1. btree 索引的多个组合查询

不同列的 and\or 查询

相同列的 or 查询

2. brin 索引

由于brin索引本身存储的就是一些连续块的元信息,所以本身就无法实现精确查询,所以通过brin查询时,首先也是构建heap page的bitmap串,(符合条件的为1,不符合条件的为0),然后根据这个bitmap串搜索tuple.

并在bitmap heap scan阶段 recheck 条件。

postgres-# \d cluster_test_brin   
     Unlogged table "public.cluster_test_brin"  
  Column  |            Type             | Modifiers   
----------+-----------------------------+-----------  
 id       | integer                     |   
 info     | text                        |   
 crt_time | timestamp without time zone |   
Indexes:  
    "idx_cluster_test_brin_id" brin (id) WITH (pages_per_range='128')  

postgres=# explain select * from cluster_test_brin where id=1;  
                                         QUERY PLAN                                            
---------------------------------------------------------------------------------------------  
 Bitmap Heap Scan on cluster_test_brin  (cost=115.60..13767.33 rows=10722 width=45)  
   Recheck Cond: (id = 1)  
   ->  Bitmap Index Scan on idx_cluster_test_brin_id  (cost=0.00..112.92 rows=10722 width=0)  
         Index Cond: (id = 1)  
(4 rows)  

3. gin 索引

gin 索引存储的是KEY,以及ctid (heap行号)组成的posting list或posting tree,它理论上是可以支持index scan的,但是PostgreSQL目前仅对GIN实施了bitmap scan。

所以在使用gin索引时,首先也是构造heap page的bitmap串,(符合条件的为1,不符合条件的为0),然后根据这个bitmap串搜索tuple.

并在bitmap heap scan阶段 recheck 条件。

这也是目前gin值得改进的地方。

postgres=# \d cluster_test_btree   
     Unlogged table "public.cluster_test_btree"  
  Column  |            Type             | Modifiers   
----------+-----------------------------+-----------  
 id       | integer                     |   
 info     | text                        |   
 crt_time | timestamp without time zone |   
Indexes:  
    "idx_cluster_test_gin" gin (id)  

postgres=# explain select * from cluster_test_btree where id=1;  
                                       QUERY PLAN                                         
----------------------------------------------------------------------------------------  
 Bitmap Heap Scan on cluster_test_btree  (cost=90.83..13732.45 rows=10714 width=45)  
   Recheck Cond: (id = 1)  
   ->  Bitmap Index Scan on idx_cluster_test_gin  (cost=0.00..88.16 rows=10714 width=0)  
         Index Cond: (id = 1)  
(4 rows)  

参考

http://dba.stackexchange.com/questions/119386/understanding-bitmap-heap-scan-and-bitmap-index-scan/119391

http://stackoverflow.com/questions/33100637/undestanding-bitmap-indexes-in-postgresql

https://wiki.postgresql.org/wiki/What's_new_in_PostgreSQL_9.5#BRIN_Indexes

《宝剑赠英雄 - 任意组合字段等效查询, 探探PostgreSQL多列展开式B树》

《PostgreSQL GIN索引实现原理》

《PostgreSQL GIN multi-key search 优化》

《PostgreSQL 聚集存储 与 BRIN索引 - 高并发行为、轨迹类大吞吐数据查询场景解说》

相关实践学习
使用PolarDB和ECS搭建门户网站
本场景主要介绍基于PolarDB和ECS实现搭建门户网站。
阿里云数据库产品家族及特性
阿里云智能数据库产品团队一直致力于不断健全产品体系,提升产品性能,打磨产品功能,从而帮助客户实现更加极致的弹性能力、具备更强的扩展能力、并利用云设施进一步降低企业成本。以云原生+分布式为核心技术抓手,打造以自研的在线事务型(OLTP)数据库Polar DB和在线分析型(OLAP)数据库Analytic DB为代表的新一代企业级云原生数据库产品体系, 结合NoSQL数据库、数据库生态工具、云原生智能化数据库管控平台,为阿里巴巴经济体以及各个行业的企业客户和开发者提供从公共云到混合云再到私有云的完整解决方案,提供基于云基础设施进行数据从处理、到存储、再到计算与分析的一体化解决方案。本节课带你了解阿里云数据库产品家族及特性。
目录
相关文章
|
关系型数据库 PostgreSQL 索引
PostgreSQL通过索引获取heap tuple解析
PostgreSQL通过索引获取heap tuple解析
181 0
|
SQL 存储 Oracle
PostgreSQL 分页, offset, 返回顺序, 扫描方法原理(seqscan, index scan, index only scan, bitmap scan, parallel xx scan),游标
PostgreSQL 分页, offset, 返回顺序, 扫描方法原理(seqscan, index scan, index only scan, bitmap scan, parallel xx scan),游标
3857 0
|
SQL 存储 弹性计算
PostgreSQL 分页, offset, 返回顺序, 扫描方法原理(seqscan, index scan, index only scan, bitmap scan, parallel xx scan),游标
标签 PostgreSQL , 数据离散性 , 扫描性能 , 重复扫 , bitmap index scan , 排序扫描 , 扫描方法 , 顺序 背景 一个这样的问题: 为什么select x from tbl offset x limit x; 两次查询连续的OFFSET,会有重复数据呢? select ctid,* from tbl where ... offset 0 li
2126 0
|
存储 传感器 关系型数据库
【重新发现PostgreSQL之美】- 8 轨迹业务IO杀手克星index include(覆盖索引)
大家好 ,这里是重新发现PostgreSQL之美 - 8 轨迹业务IO杀手克星index include(覆盖索引)
|
传感器 SQL 并行计算
【重新发现PostgreSQL之美】 - 6 index链表跳跳糖 (CTE recursive 递归的详细用例)
大家好,这里是重新发现PostgreSQL之美 - 6 index链表跳跳糖 (CTE recursive 递归的详细用例)
|
SQL 分布式计算 并行计算
PostgreSQL 并行计算解说 之14 - parallel index scan
标签 PostgreSQL , cpu 并行 , smp 并行 , 并行计算 , gpu 并行 , 并行过程支持 背景 PostgreSQL 11 优化器已经支持了非常多场合的并行。简单估计,已支持27余种场景的并行计算。 parallel seq scan paral
1203 0
|
SQL 分布式计算 并行计算
PostgreSQL 并行计算解说 之15 - parallel bitmap scan
标签 PostgreSQL , cpu 并行 , smp 并行 , 并行计算 , gpu 并行 , 并行过程支持 背景 PostgreSQL 11 优化器已经支持了非常多场合的并行。简单估计,已支持27余种场景的并行计算。 parallel seq scan
1280 0
|
SQL 分布式计算 并行计算
PostgreSQL 并行计算解说 之16 - parallel index only scan
标签 PostgreSQL , cpu 并行 , smp 并行 , 并行计算 , gpu 并行 , 并行过程支持 背景 PostgreSQL 11 优化器已经支持了非常多场合的并行。简单估计,已支持27余种场景的并行计算。 parallel seq scan
783 0
|
存储 关系型数据库 Go
PostgreSQL 11 内核优化 - 降低vacuum cleanup阶段index scan概率 ( vacuum_cleanup_index_scale_factor , skip index vacuum cleanup stage)
PostgreSQL 11 内核优化 - 降低vacuum cleanup阶段index scan概率 ( vacuum_cleanup_index_scale_factor , skip index vacuum cleanup stage)
1272 0
|
关系型数据库 分布式数据库 PolarDB
《阿里云产品手册2022-2023 版》——PolarDB for PostgreSQL
《阿里云产品手册2022-2023 版》——PolarDB for PostgreSQL
373 0

相关产品

  • 云原生数据库 PolarDB