PostgreSQL 의 bitmap scan 분석

PostgreSQL 에서 단일 열 에 있 는 btree 색인 조회 에 대해 우리 가 본 것 은 모두 일반적인 색인 검색 Index Scan 입 니 다. 예 를 들 어 아래 와 같 습 니 다.

bill=# explain select * from t1 where c1=10;
                             QUERY PLAN                             
--------------------------------------------------------------------
 Index Scan using idx_t1 on t1  (cost=0.15..10.73 rows=10 width=12)
   Index Cond: (c1 = 10)
(2 rows)

여러 개의 단일 색인 이 조합 조회 SQL 에 사용 되 는 상황 에서 우 리 는 bitmap scan 을 사용 하 는 것 을 볼 수 있 습 니 다. 예 를 들 어:

bill=# create index idx_t11 on t1 using btree(c1);
CREATE INDEX
bill=# create index idx_t12 on t1 using btree(c2); 
CREATE INDEX
bill=# create index idx_t13 on t1 using btree(c3); 
CREATE INDEX
bill=# explain select * from t1 where c1 =10 and c2 =20 and c3 = 30;  
                                 QUERY PLAN                                  
-----------------------------------------------------------------------------
 Bitmap Heap Scan on t1  (cost=3.31..4.62 rows=1 width=12)
   Recheck Cond: ((c3 = 30) AND (c2 = 20))
   Filter: (c1 = 10)
   ->  BitmapAnd  (cost=3.31..3.31 rows=1 width=0)
         ->  Bitmap Index Scan on idx_t13  (cost=0.00..1.53 rows=10 width=0)
               Index Cond: (c3 = 30)
         ->  Bitmap Index Scan on idx_t12  (cost=0.00..1.53 rows=10 width=0)
               Index Cond: (c2 = 20)
(8 rows)

그렇다면 이 두 가 지 는 어떤 차이 가 있 을 까?PostgreSQL 은 여러 조합 조건 의 BITMAP SCAN 을 어떻게 처리 합 니까?먼저 Index Scan 을 살 펴 보 겠 습 니 다. 이것 은 가장 간단 한 btree 색인 스 캔 입 니 다. 그 원 리 는 색인 key 를 통 해 원 그룹의 ctid 를 찾 은 다음 에 표 로 돌아 가 해당 하 는 데 이 터 를 가 져 오 는 것 입 니 다 (index only scan 제외). BITMAP SCAN 은 모든 검색 조건 에 대해 해당 하 는 색인 에서 조건 에 맞 는 표 PAGE 를 찾 고 색인 마다 bitmap 문자열 을 구성 합 니 다.이 bitmap 문자열 에서 모든 BIT 비트 는 HEAP PAGE 에 대응 합 니 다. 이 HEAP PAGE 에는 이 조건 에 맞 는 줄 이 있 습 니 다 (임의의 줄 이 조건 에 부합 하면 이 PAGE 의 BIT 비트 가 표 시 됩 니 다 1).조건 에 따라 여러 비트 맵 을 구성 하 였 습 니 다.다음 그림 에서 보 듯 이:

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

예 를 들 어 우 리 는 c1 열 에 색인 을 만 들 었 습 니 다. 우 리 는 c1 = 10 의 조 회 를 사용 하면 bitmap 1 과 같은 bitmap 문자열 을 만 들 었 습 니 다. 그리고 c2 = 20 에 bitmap 2 와 같은 bitmap 문자열 을 만 든 다음 에 이 두 bitmap 문자열 을 and 로 조작 하여 combined bitmap 와 같은 bitmap 문자열 을 얻 었 습 니 다. 그러나 이때 우 리 는 앞의 실행 계획 에 마지막 으로 Recheck Cond 가 있다 는 것 을 알 게 되 었 습 니 다. 이것 은 무엇 입 니까?앞에서 말 했 듯 이 모든 BIT 비트 는 하나의 HEAP PAGE 에 대응 합 니 다. 우 리 는 모든 page 에 가서 recheck 이 필요 로 하 는 줄 을 얻어 야 합 니 다. 이것 이 바로 Recheck Cond 의 역할 입 니 다. 마지막 으로 어떤 장면 이 bitmap scan 을 사용 하 는 지 살 펴 보 겠 습 니 다.1. 상기 에서 예 를 들 어 btree 색인 의 여러 조합 은 서로 다른 열 및 / 또는 같은 열 을 조회 하 는 or 조 회 를 조회 합 니 다.
2. brin 색인 은 brin 색인 자체 에 저 장 된 것 이 연속 블록 의 메타 정보 이기 때문에 그 자체 가 정확 한 조 회 를 실현 할 수 없 기 때문에 brin 조 회 를 통 해 먼저 힙 페이지 의 bitmap 문자열 을 구축 합 니 다. (조건 에 부합 되 는 것 은 1 이 고 조건 에 부합 되 지 않 는 것 은 0) 그 다음 에 이 bitmap 문자열 에 따라 tuple 을 검색 하고 bitmap heap scan 단계 recheck 조건 을 참조 합 니 다.

bill=# create table t_brin (id int, info text, crt_time timestamp);
CREATE TABLE
bill=# insert into t_brin select generate_series(1,1000000), md5(random()::text), clock_timestamp();    
INSERT 0 1000000
bill=# create index idx_t_brin_1 on t_brin using brin (id) with (pages_per_range=1);    
CREATE INDEX
bill=# explain (analyze,verbose,timing,costs,buffers) select * from t_brin where id between 100 and 200;    
                                                       QUERY PLAN                                                        
-------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on public.t_brin  (cost=38.52..175.79 rows=88 width=45) (actual time=2.100..2.116 rows=101 loops=1)
   Output: id, info, crt_time
   Recheck Cond: ((t_brin.id >= 100) AND (t_brin.id <= 200))
   Rows Removed by Index Recheck: 113
   Heap Blocks: lossy=2
   Buffers: shared hit=45
   ->  Bitmap Index Scan on idx_t_brin_1  (cost=0.00..38.50 rows=107 width=0) (actual time=2.082..2.082 rows=20 loops=1)
         Index Cond: ((t_brin.id >= 100) AND (t_brin.id <= 200))
         Buffers: shared hit=43
 Planning Time: 0.224 ms
 Execution Time: 2.145 ms
(11 rows)

3. gin 색인 gin 색인 은 KEY 와 ctid (heap 줄 번호) 로 구 성 된 posting list 나 posting tree 를 저장 합 니 다. 이론 적 으로 index scan 을 지원 할 수 있 지만 PostgreSQL 은 현재 GIN 에 만 bitmap scan 을 실시 하고 있 습 니 다.따라서 gin 색인 을 사용 할 때 먼저 힙 페이지 를 구성 하 는 bitmap 문자열 (조건 에 부합 되 는 것 은 1, 조건 에 부합 되 지 않 는 것 은 0) 을 사용 한 다음 에 이 bitmap 문자열 에 따라 tuple 을 검색 하고 bitmap heap scan 단계 에서 recheck 조건 을 검색 합 니 다.이것 도 현재 gin 이 개선 할 만 한 부분 입 니 다.

bill=# create table t_gin2 (id int, c1 int);   
CREATE TABLE
bill=# insert into t_gin2 select generate_series(1,100000), random()*10 ;    
INSERT 0 100000
bill=# create index idx_t_gin2_1 on t_gin2 using gin (c1);  
CREATE INDEX
bill=# explain (analyze,verbose,timing,costs,buffers) select * from t_gin2 where c1=1; 
                                                        QUERY PLAN                                                         
---------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on public.t_gin2  (cost=9.07..349.73 rows=500 width=8) (actual time=1.084..3.279 rows=10038 loops=1)
   Output: id, c1
   Recheck Cond: (t_gin2.c1 = 1)
   Heap Blocks: exact=443
   Buffers: shared hit=448
   ->  Bitmap Index Scan on idx_t_gin2_1  (cost=0.00..8.95 rows=500 width=0) (actual time=1.032..1.032 rows=10038 loops=1)
         Index Cond: (t_gin2.c1 = 1)
         Buffers: shared hit=5
 Planning Time: 0.137 ms
 Execution Time: 3.775 ms
(10 rows)