PostgreSQL의 Bitmap Index Scan

 

 

본 문서의 내용은 PostgreSQL 버젼에 따라 다를 수 있습니다. 본 문서에서 사용한 버젼은 아래와 같습니다.

• AWS RDS PostgreSQL 15.4 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12), 64-bit

 

PostgreSQL의 Bitmap Index Scan

 

PostgreSQL의 실행계획에는 Index (Range) Scan이 아닌 Bitmap Index Scan이 종종 나타납니다.

 

설명에 앞서, 오라클의 Bitmap Index와 PostgreSQL의 Bitmap Index Scan를 구분할 필요가 있습니다. 이 두개는 완전히 다른 것입니다.

오라클의 Bitmap Index는 인덱스 자체를 Bitmap 형태로 구성한 것입니다.

반면에 PostgreSQL의 Bitmap Index Scan은 일반적인 B Tree 인덱스를 사용하는 처리 방식 중에 하나입니다. 다시 말해, B Tree 인덱스를 사용해 일반적인 Index Scan을 할 수도 있으며 Bitmap Index Scan을 할 수도 있습니다. Bitmap Index Scan은 인덱스를 통한 테이블 블록의 접근 횟수를 줄이기 위해 Bitmap 처리를 추가 적용한 것을 뜻합니다.

 

아래 SQL을 실행해 봅니다. 실행계획을 보면 x02(rno) 인덱스에 대해 Bitmap Index Scan이 작동했습니다.

총 실행 시간은 3.482 ms가 걸렸고, 3053의 IO(Buffers: shared ht)가 발생하고 있습니다.

EXPLAIN (ANALYZE,BUFFERS)
SELECT  TO_CHAR(t1.ord_dt,'YYYYMM') ym,COUNT(*) cnt
FROM    t_ord_big t1
WHERE   t1.cus_id = 'CUS_0064' 
AND     t1.pay_tp = 'BANK' 
AND     t1.rno = 2 
GROUP BY TO_CHAR(t1.ord_dt,'YYYYMM');

GroupAggregate  (cost=10374.03..10374.25 rows=11 width=40) (actual time=3.446..3.448 rows=2 loops=1)
  Group Key: (to_char(ord_dt, 'YYYYMM'::text))
  Buffers: shared hit=3053
  ->  Sort  (cost=10374.03..10374.06 rows=11 width=32) (actual time=3.440..3.442 rows=2 loops=1)
        Sort Key: (to_char(ord_dt, 'YYYYMM'::text))
        Sort Method: quicksort  Memory: 25kB
        Buffers: shared hit=3053
        ->  Bitmap Heap Scan on t_ord_big t1  (cost=35.24..10373.84 rows=11 width=32) (actual time=0.712..3.432 rows=2 loops=1)
              Recheck Cond: (rno = 2)
              Filter: (((cus_id)::text = 'CUS_0064'::text) AND ((pay_tp)::text = 'BANK'::text))
              Rows Removed by Filter: 3045
              Heap Blocks: exact=3047
              Buffers: shared hit=3053
              ->  Bitmap Index Scan on t_ord_big_x02  (cost=0.00..35.23 rows=3040 width=0) (actual time=0.282..0.283 rows=3047 loops=1)
                    Index Cond: (rno = 2)
                    Buffers: shared hit=6
Planning Time: 0.092 ms
Execution Time: 3.482 ms

 

 

 

Bitmap Index Scan 역시 Index Scan과 마찬가지로 수직적탐색과 수평적탐색, 테이블접근으로 작업이 진행됩니다.

단, 테이블 블록 접근 단계에서,  접근 횟수를 줄일 수 있도록 아래와 같은 알고리즘이 추가되어 있습니다.

• 인덱스 수평탐색을 하면서 얻은 ctid(실제 레코드 포인터) 정보를 모아서 비트맵으로 변환
• ctid 별로 건건이 테이블 블록에 한 번씩 접근하는 것이 아니라,
• ctid 를 모아서 비트맵으로 변환한 후에 같은 블록의 데이터는 한 번에 가져오는 방법
• 이를 통해, 불필요한 중복 접근을 줄일 수 있습니다.
• 마치 오라클의 TABLE ACCESS BY INDEX ROWID BATCHED 와 유사하다 할 수 있습니다.

Bitmap Index Scan에는 Bitmap Heap Scan 단계가 따라옵니다. 이는 ctid 비트맵을 사용해 Heap 테이블에 접근하는 단계입니다.

 

이와 같은 Bitmap Index Scan은 인덱스를 사용해 많은 데이터 블록에 접근할 가능성이 높거나, 실제 테이블의 데이터 정렬 순서와 인덱스 리프의 정렬 순서 차이가 클때 유용한 것으로 알려져 있습니다. 

PostgreSQL의 pg_stats를 통해 컬럼과 테이블간의 정렬 순서의 상관 관계 통계값을 알 수 있습니다. rno의 상관 계수는 0.012로 낮은 편입니다. 결과적으로 x02 인덱스(rno)의 정렬 순서와 실제 데이터의 정렬 순서 차이가 커서 Bitmap Index Scan을 사용한 것으로 추정할 수 있습니다.

SELECT attname, correlation
FROM   pg_stats
WHERE  tablename = 't_ord_big';

attname|correlation |
-------+------------+
ord_seq|         1.0|
rno    | 0.012465741|
ord_ymd|         1.0|
cus_id | 0.018490704|
ord_dt |         1.0|
ord_st |    0.815537|
pay_dt |         1.0|
pay_tp |   0.5573953|
ord_amt|-0.035096794|
pay_amt|-0.012219012|

 

 

그러나! 100% 완벽한 통계는 없습니다. 아니요. 통계는 100% 완벽할 수 있을거 같습니다. 하지만, 그에 따라 선택한 옵티마이져의 결정이 항상 최선은 아닐 수 있다고 말하는게 맞을거 같습니다.

 

아래와 같이 힌트를 사용해 일반적인 IndexScan으로 SQL을 실행해봅니다. IO가 3,053으로 기존의 Bitmap Index Scan을 했을때와 동일합니다. 이처럼 IO가 같다면 Bitmap 연산을 추가로 수행하는 Bitmap Inedx Scan이 좀 더 느릴 수 있습니다. 현재 결과에서도 IndexScan의 실행시간이 2.416ms로 Bitmap Index Scan보다 아주 조금 더 빠릅니다.

EXPLAIN (ANALYZE,BUFFERS)
/*+ IndexScan(t1) */
SELECT  TO_CHAR(t1.ord_dt,'YYYYMM') ym,COUNT(*) cnt
FROM    t_ord_big t1
WHERE   t1.cus_id = 'CUS_0064' 
AND     t1.pay_tp = 'BANK' 
AND     t1.rno = 2 
GROUP BY TO_CHAR(t1.ord_dt,'YYYYMM');


GroupAggregate  (cost=12031.20..12031.42 rows=11 width=40) (actual time=2.387..2.389 rows=2 loops=1)
  Group Key: (to_char(ord_dt, 'YYYYMM'::text))
  Buffers: shared hit=3053
  ->  Sort  (cost=12031.20..12031.23 rows=11 width=32) (actual time=2.381..2.382 rows=2 loops=1)
        Sort Key: (to_char(ord_dt, 'YYYYMM'::text))
        Sort Method: quicksort  Memory: 25kB
        Buffers: shared hit=3053
        ->  Index Scan using t_ord_big_x02 on t_ord_big t1  (cost=0.43..12031.01 rows=11 width=32) (actual time=0.043..2.371 rows=2 loops=1)
              Index Cond: (rno = 2)
              Filter: (((cus_id)::text = 'CUS_0064'::text) AND ((pay_tp)::text = 'BANK'::text))
              Rows Removed by Filter: 3045
              Buffers: shared hit=3053
Planning Time: 0.123 ms
Execution Time: 2.416 ms

 

3.482 ms나 2.416 ms나 인간이 거의 느낄 수 없는 시간 차이이기 때문에 의미가 있다고 할 수는 없습니다.

어쨋든, 옵티마이져가 선택한 방법이 최선이 아닐 수도 있다라고 한 번쯤 의심해볼 필요는 있습니다.

(절대, Bitmap Index Scan보다 Index Scan이 좋다는 일반론적 이야기가 아닙니다. 상황에 따라서는 Bitmap Index Scan이 더 유리할 수 있습니다. 또한 옵티마이져가 제대로 제 할일을 못한다라는 뜻의 이야기도 아닙니다.! 기본적으로 통계가 잘 구성되어 있다면 옵티마이져를 믿는 것이 우선입니다.)

 

이번에는 SQL을 살짝 바뿨봅니다. rno를 범위 조건으로 조금 더 많은 데이터를 조회해봅니다. 아래 결과를 살펴보면 Bitma Index Scan이 Index Scan보다 훨씬 적은 IO(Bitmap:3,192, IndexScan: 12,202)가 발생하고 실행시간도 근소하지만 더 빠릅니다.

EXPLAIN (ANALYZE,BUFFERS)
SELECT  TO_CHAR(t1.ord_dt,'YYYYMM') ym,COUNT(*) cnt
FROM    t_ord_big t1
WHERE   t1.rno BETWEEN 2 AND 5 
GROUP BY TO_CHAR(t1.ord_dt,'YYYYMM');


HashAggregate  (cost=33470.11..33474.47 rows=349 width=40) (actual time=9.486..9.489 rows=12 loops=1)
  Group Key: to_char(ord_dt, 'YYYYMM'::text)
  Batches: 1  Memory Usage: 37kB
  Buffers: shared hit=3192
  ->  Bitmap Heap Scan on t_ord_big t1  (cost=168.78..33409.45 rows=12131 width=32) (actual time=1.140..7.639 rows=12188 loops=1)
        Recheck Cond: ((rno >= 2) AND (rno <= 5))
        Heap Blocks: exact=3178
        Buffers: shared hit=3192
        ->  Bitmap Index Scan on t_ord_big_x02  (cost=0.00..165.74 rows=12131 width=0) (actual time=0.741..0.741 rows=12188 loops=1)
              Index Cond: ((rno >= 2) AND (rno <= 5))
              Buffers: shared hit=14
Planning:
  Buffers: shared hit=8
Planning Time: 0.104 ms
Execution Time: 9.546 ms


EXPLAIN (ANALYZE,BUFFERS)
/*+ IndexScan(t1) */
SELECT  TO_CHAR(t1.ord_dt,'YYYYMM') ym,COUNT(*) cnt
FROM    t_ord_big t1
WHERE   t1.rno BETWEEN 2 AND 5 
GROUP BY TO_CHAR(t1.ord_dt,'YYYYMM');

HashAggregate  (cost=45715.02..45719.38 rows=349 width=40) (actual time=10.388..10.392 rows=12 loops=1)
  Group Key: to_char(ord_dt, 'YYYYMM'::text)
  Batches: 1  Memory Usage: 37kB
  Buffers: shared hit=12202
  ->  Index Scan using t_ord_big_x02 on t_ord_big t1  (cost=0.43..45654.36 rows=12131 width=32) (actual time=0.015..8.493 rows=12188 loops=1)
        Index Cond: ((rno >= 2) AND (rno <= 5))
        Buffers: shared hit=12202
Planning:
  Buffers: shared hit=8
Planning Time: 0.142 ms
Execution Time: 10.420 ms

 

이처럼 대량의 데이터에 접근해야 한다면, 바꿔말해 인덱스를 사용해 테이블의 데이터 블록에 많은 접근이 발생할 수 있다면, Bitmap 처리를 통해 불필요한 IO를 줄일 수 있습니다. 이것이 바로 Bitmap Index Scan입니다.

 

살펴볼 내용은 여기까지입니다. 이상입니다.

 

P.S. 아래 강의들을 진행하고 있으니, 많은 관심 부탁드립니다.
  - StartUP Tuning For PostgreSQL: PostgreSQL을 활용한 SQL 튜닝 입문 교육
    https://cafe.naver.com/dbian/7181
  - StartUP Tuning For MySQL: MySQL을 활용한 SQL 튜닝 입문 교육
    https://cafe.naver.com/dbian/6958
  - 평생필요한 데이터 분석: 저자 직강!, 주식 데이터를 활용한 SQL 입문자 교육
    https://cafe.naver.com/dbian/7131