[PostgreSQL] postgres SCAN 종류 (Bitmap SCAN)

개요

postgres에서는 데이터를 찾을 때 다양한 SCAN을 사용합니다.

 

그 중 Sequential SCAN, Index SCAN, Bitmap SCAN에 대해 알아보려고 합니다.

 

쿼리를 실행할 때 쿼리 계획을 살펴보면 해당 쿼리가 어떠한 SCAN을 사용하는지 확인할 수 있습니다.

 

테스트를 할 page 테이블을 생성합니다.

CREATE TABLE page(id serial PRIMARY KEY, content TEXT);

 

랜덤한 값 100만개를 넣어줍니다.

INSERT INTO page (content)
SELECT
    md5(random()::text || clock_timestamp()::text) -- 랜덤한 문자열 생성
FROM generate_series(1, 1000000);

 

Sequential SCAN

순차 탐색입니다.

 

인덱스가 존재하지 않은 컬럼을 대상으로 검색하면 순차 탐색을 진행합니다.

 

테스트를 위해 content 컬럼을 기준으로 검색을 할 건데 랜덤한 문자열로 생성했기 때문에 page에서 50만번 인덱스의 content 값을 가져옵니다.

SELECT content FROM page WHERE id=500000;

 

             content              
----------------------------------
 b4933e6eb7a0d120f9b5b16b1ae8e37f
(1 row)

 

이제 EXPLAIN으로 쿼리 플랜을 확인해봅시다.

EXPLAIN ANALYZE SELECT content FROM page WHERE content='b4933e6eb7a0d120f9b5b16b1ae8e37f';

                                                     QUERY PLAN                                                     
--------------------------------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..14542.43 rows=1 width=33) (actual time=20.419..39.975 rows=1 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on page  (cost=0.00..13542.33 rows=1 width=33) (actual time=28.522..33.981 rows=0 loops=3)
         Filter: (content = 'b4933e6eb7a0d120f9b5b16b1ae8e37f'::text)
         Rows Removed by Filter: 333333
 Planning Time: 0.069 ms
 Execution Time: 39.998 ms
(8 rows)

 

2개의 worker가 병렬로 순차 탐색을 수행했다는 것을 알 수 있습니다.

 

이러한 순차 탐색은 당연하게도 데이터가 많을 경우 오랜 시간이 걸립니다.

 

Index SCAN

이번에는 index scan을 해봅시다.

 

content에 인덱스를 생성합니다.

CREATE INDEX content_index ON page(content);

 

똑같이 content로 검색을 합니다.

EXPLAIN ANALYZE SELECT * FROM page WHERE content='b4933e6eb7a0d120f9b5b16b1ae8e37f';

                                                     QUERY PLAN                                                      
---------------------------------------------------------------------------------------------------------------------
 Index Scan using content_index on page  (cost=0.42..8.44 rows=1 width=37) (actual time=0.032..0.034 rows=1 loops=1)
   Index Cond: (content = 'b4933e6eb7a0d120f9b5b16b1ae8e37f'::text)
 Planning Time: 0.081 ms
 Execution Time: 0.053 ms
(4 rows)

 

index를 생성했기 때문에 sequential SCAN이 아닌 Index Scan을 사용한 모습을 확인할 수 있습니다.

 

쿼리 실행 시간이 39.998ms에서 0.053ms로 대폭 감소했습니다.

 

Index Only SCAN

Index에서 바로 값을 가져올 수 있을 때 사용합니다.

 

위에서 조건에 해당하는 page의 모든 컬럼을 가져왔는데 이번에는 인덱스가 걸린 content만 가져오는 쿼리를 작성해봅시다.

 

EXPLAIN ANALYZE SELECT content FROM page WHERE content='b4933e6eb7a0d120f9b5b16b1ae8e37f';

                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using content_index on page  (cost=0.42..4.44 rows=1 width=33) (actual time=0.041..0.042 rows=1 loops=1)
   Index Cond: (content = 'b4933e6eb7a0d120f9b5b16b1ae8e37f'::text)
   Heap Fetches: 0
 Planning Time: 0.112 ms
 Execution Time: 0.066 ms
(5 rows)

 

인덱스에서 바로 값을 가져올 수 있기 때문에 Index Scan이 아닌 Index Only Scan이 사용되었습니다.

 

 

Bitmap SCAN

다음은 Bitmap SCAN에 대해 알아볼건데 보통 Bitmap Index SCAN이 이루어진 다음 Bitmap Heap SCAN이 이루어집니다.

 

Bitmap Index SCAN은 Sequential SCAN과 Index SCAN의 사이라고 볼 수 있습니다.

 

보통 인덱스가 걸린 컬럼에서 여러 개의 행을 반환할 때 사용합니다.

 

현재 page 테이블의 content 컬럼은 인덱스가 걸려있으나 랜덤 문자열이라서 거의 행이 하나만 나오게 됩니다.

 

즉, Index SCAN을 사용할 확률이 높기 때문에 Bitmap SCAN을 위해 여러 값이 중복되는 컬럼을 하나 생성합니다.

 

user_id 컬럼을 생성하고 랜덤으로 1에서 10 사이의 값으로 갱신해줍니다.

ALTER TABLE page ADD COLUMN user_id INT;
UPDATE page
SET user_id = floor(random() * 10 + 1);

 

이제 user_id는 중복되는 행이 많을 수밖에 없고 user_id로 인덱스를 생성하고 검색을 하면 여러 개의 행이 나올 확률이 높습니다.

CREATE INDEX user_id_index ON page(user_id);

EXPLAIN ANALYZE SELECT * FROM page WHERE user_id=3;

 

                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on page  (cost=1149.12..20114.12 rows=102800 width=41) (actual time=5.586..79.321 rows=99901 loops=1)
   Recheck Cond: (user_id = 3)
   Heap Blocks: exact=9347
   ->  Bitmap Index Scan on user_id_index  (cost=0.00..1123.42 rows=102800 width=0) (actual time=3.755..3.756 rows=99901 loops=1)
         Index Cond: (user_id = 3)
 Planning Time: 0.241 ms
 Execution Time: 83.307 ms
(7 rows)

 

Bitmap SCAN이 사용된 모습을 확인할 수 있습니다.

 

이제 Bitmap SCAN에서 Bitmap Index SCAN과 Bitmap Heap SCAN에 대해 알아봐야 하는데 그 전에 Bitmap에 대해 알아봅시다.

 

Bitmap이란?

Bitmap은 비트의 배열 형태로 된 자료구조입니다.

 

다양한 곳에서 사용하지만 Bitmap으로 ON/OFF를 표현할 수 있습니다.

 

리눅스 파일 시스템의 권한에 대해 생각해봅시다.

 

r(read), w(write), x(execute) 순서대로 권한을 부여했다면 1, 그렇지 않다면 0으로 표현합니다.

 

예를 들어 읽기와 실행 권한만 부여했다면 101이 되는 것입니다.

 

이렇게 Bitmap으로 쉽게 ON/OFF를 표현할 수 있습니다.

Bitmap Index SCAN

Bitmap Index SCAN은 Index SCAN을 통해 Bitmap을 만드는 과정입니다.

 

Bitmap을 만드는 이유는 I/O 접근을 줄이기 위함입니다.

 

제대로 이해를 하기 위해서는 데이터베이스의 블록과 레코드의 관계에 대해 알아야 합니다.

https://growth-coder.tistory.com/13

[Database] 디스크 안에 파일 레코드를 저장하는 방법

 

간단하게 설명하자면 하나의 블록 안에는 여러 개의 레코드(행)가 들어가게 됩니다.

 

그리고 하나의 블록 안에 존재하는 3개의 레코드를 찾아야 한다고 가정합시다.

 

일반적인 Index SCAN을 사용하면 3개의 레코드를 찾기 위해 동일한 블록에 3번 접근을 해야 합니다.

 

 

하지만 5개의 레코드가 동일한 블록에 존재한다는 사실을 미리 알고 있다면 어떨까요?

 

동일한 블록에 5번 접근할 필요 없이 한 번만 접근해서 필요한 레코드들을 가져오면 됩니다.

 

그렇다면 각 블록에 대한 접근 여부를 Bitmap으로 만들면 어떠한 블록에 접근이 발생하는지 미리 알 수 있게 됩니다.

 

이렇게 Bitmap Index SCAN을 통해 각 블록에 대한 접근 여부를 Bitmap으로 만들고 다음 단계인 Bitmap Heap SCAN에서 이 Bitmap을 활용하여 I/O 접근을 줄일 수 있게 되는 것입니다.

Bitmap Heap SCAN

이제 Bitmap Heap SCAN에서 Bitmap을 스캔하면서 조건에 맞는 레코드를 가져오게 됩니다.

 

그러면 이제 위에서 실행한 쿼리 플랜을 다시 보면서 분석해봅시다.

                                                            QUERY PLAN                                                            
----------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on page  (cost=1149.12..20114.12 rows=102800 width=41) (actual time=5.586..79.321 rows=99901 loops=1)
   Recheck Cond: (user_id = 3)
   Heap Blocks: exact=9347
   ->  Bitmap Index Scan on user_id_index  (cost=0.00..1123.42 rows=102800 width=0) (actual time=3.755..3.756 rows=99901 loops=1)
         Index Cond: (user_id = 3)
 Planning Time: 0.241 ms
 Execution Time: 83.307 ms
(7 rows)

 

Bitmap Index SCAN으로 bitmap을 만들고 이 bitmap을 탐색하면서 Bitmap Heap SCAN이 발생했습니다.

 

TID SCAN

TID SCAN는 레코드의 위치로 SCAN 합니다.

 

tid는 (블록 인덱스, 오프셋)를 의미하고 (30, 8)이라고 한다면 31번째 블록의 8번째 레코드를 의미합니다.

 

SELECT 구문에서 ctid를 확인할 수 있습니다.

SELECT ctid, * FROM page WHERE id<10;

   ctid    | id |             content              | user_id 
-----------+----+----------------------------------+---------
 (8333,41) |  1 | 0f84d95c75fb5c04b8c088fa08db0ca2 |      10
 (8333,42) |  2 | 84aff29e3d9360c47e01dc5242dec82b |       8
 (8333,43) |  3 | fa4f5a485ef9b1fd23c0a64fd012a491 |       2
 (8333,44) |  4 | 61c19de640040d9de94250cfebec9860 |       1
 (8333,45) |  5 | c6123d4da80dfe1c852b11bff671efe1 |       4
 (8333,46) |  6 | 50a61e13a8bf99c07034eaa4f5dad8fa |       6
 (8333,47) |  7 | f6659bf0b5c59c5f78436fe62a246594 |       9
 (8333,48) |  8 | 753e6e0dee8e10c87626a06e73825f5e |       9
 (8333,49) |  9 | a43d21fccbee4bea9b953f500685cb19 |       6
(9 rows)

 

실제 쿼리에서 ctid를 사용하게 될 일은 거의 없을 것입니다.