[PostgreSQL] Table Scan 종류

 

해당 포스팅은 PostgreSQL의 실행 계획 분석에 사용되는 EXPLAIN과 ANALYZE에 대한 개념을 기본으로 전제하고 있다.

이에 대해 알지 못한다면 아래의 포스팅을 먼저 읽기를 추천한다.

[PostgreSQL] 쿼리 실행 계획 분석(explain, analyze)

 

---

 

PostgreSQL에서 실행 계획 분석을 실행할 때 실행되는 Table Scan 방식에는 5가지 종류가 있다.

• Sequential Scan
• Index Scan
• Index Only Scan
• Bitmap Scan
• TID Scan

Test Data

CREATE TABLE post (
    id serial PRIMARY KEY,
    title varchar(255),
    author varchar(255),
    created_at timestamp
);

테스트할 테이블로 게시판의 게시물에 해당하는 테이블을 생성하였다.

 

DO $$
DECLARE
    i INTEGER := 1;
BEGIN
    WHILE i < 1000000 LOOP
        INSERT INTO post(title, author, created_at)
            VALUES(CONCAT('title', i), CONCAT('author', i % 100), now() + i * INTERVAL '1 second');
        i := i + 1;
    END LOOP;
END $$;

테이블 내의 데이터는 'title{i}'라는 서로 다른 제목을 갖는 100만 개의 게시물이 생성된다.

사용자는 총 100명으로, 'author{0-100}'의 이름을 갖는다.

즉, 100의 사용자가 10,000개씩 게시물을 작성한 상황을 가정하며, 생성 날짜는 모두 다르게 설정하였다. 

 

Sequential Scan

Sequential Scan(순차 스캔)은 테이블의 모든 데이터를 하나씩 확인하는 방법이다.

주로 인덱스가 없는 column을 조건으로 검색할 경우에 사용된다.

가장 단순하고, 기본적이지만 데이터의 양에 따라 좋은 성능을 낼 수 없다.

EXPLAIN ANALYZE
SELECT * FROM post WHERE title = 'title5432';

결과

Gather (cost=1000.00..14369.43 rows=1 width=31) (actual time=33.082..36.603 rows=1 loops=1)

   Workers Planned: 2

   Workers Launched: 2

   -> Parallel Seq Scan on post (cost=0.00..13369.33 rows=1 width=31) (actual time=25.364..30.031 rows=0 loops=3)

       Filter: ((title)::text='title5432'::text)

       Rows Removed by Filter: 333333

Planning Time: 0.085 ms

Execution Time: 36.621 ms

 

위 쿼리는 4번째 줄의 Seq Scan과 1번째 줄의 Gather, 2단계의 실행 계획으로 이루어져 있다.

화살표로 인덴트된 실행 계획은 child plan으로, 해당 단계에서 실행된 결과를 상위 단계에서 처리한다는 뜻이다.

즉, 안쪽 인덴트에서 바깥으로 실행 계획의 흐름을 따라가야 한다.

 

title은 인덱스가 없는 column이기 때문에 테이블의 모든 데이터를 조회하는 방법 밖에 없다.

결과적으로 PostgreSQL은 2개의 워커 프로세스를 생성해 병렬적으로 테이블을 순차 스캔하였으며, 각 워커 프로세스가 찾아낸 Row를 종합해서 쿼리를 수행했음을 알 수 있다.(Parallel Seq Scan)

(워커 프로세스는 쿼리의 병렬 처리를 구현한다.)

 

실행 계획에서 또 다른 중요 키워드는 Rows Removed by Filter이다.

이 결과는 테이블의 Row를 조회했으나, 사용자가 찾는 Row 데이터(title = 'title 5432')가 아니기 때문에 버려진 Row 수를 나타낸다. 이 수가 적을수록 최적화된 쿼리라고 할 수 있다.

 

3번의 루프(loops=3)를 돌면서 333,333개의 Row를 버렸다는 말은 1개의 Row를 찾기 위해 100만 개의 Row를 모두 조회했다는 의미이다.

 

Execution Time은 실제 실행에 소요된 시간을 의미한다.

 

Index Scan

Index Scan은 인덱스를 탐색하는 방식을 말한다.

인덱스가 만들어진 column을 조건문으로 조회할 때 데이터베이스가 선택하는 방식이다.

EXPLAIN ANALYZE
SELECT * FROM post WHERE id = 5432;

결과

Index Scan using post_pkey on post (cost=0.42..8.44 rows=1 width=31) (actual time=0.019..0.021 rows=1 loops=1)

   Index Cond: (id=5432)

Planning Time: 0.062 ms

Execution Time: 0.040 ms

 

id column은 PK 지정했기 때문에 테이블을 생성할 때 인덱스가 자동으로 생성되고 정렬된다.

때문에 id로 데이터를 조회할 때 Index Scan을 사용하여 필요한 Row만 빠르게 가져올 수 있다.

Index Scan을 사용할 때 가장 실행시간이 가장 짧다.

 

EXPLAIN ANALYZE
SELECT * FROM post WHERE id < 5432;

결과

Index Scan using post_pkey on post (cost=0.42..198.37 rows=5254 width=31) (actual time=0.010..0.853 rows=5431 loops=1)

   Index Cond: (id < 5432)

Planning Time: 0.127 ms

Execution Time: 1.098 ms

 

EXPLAIN ANALYZE
SELECT * FROM post WHERE id < 5432 ORDER BY id DESC;

결과

Index Scan Backward using post_pkey on post (cost=0.42..198.37 rows=5254 width=31) (actual time=0.013..0.837 rows=5431 loops=1)

   Index Cond: (id < 5432)

Planning Time: 0.088 ms

Execution Time: 1.076 ms

 

Index Scan은 범위 조회와 역순 조회가 가능하다. 특히 역순 조회의 경우 항상 정렬되어 있는 인덱스의 특징 때문에 Index Scan Backward 방식을 이용해서 id를 역순으로 조회하여 쿼리를 효율적으로 처리할 수 있다.

 

하지만 index가 존재해도 Sequential Scan 방식이 사용될 때가 있다.

EXPLAIN ANALYZE
SELECT id FROM post WHERE id > 5432;

결과

Seq Scan on post (cost=0.00..20661.00 rowse=994075 width=4) (actual time=0.304..100.115 rows=994568 loops=1)

   Filter: (id > 5432)

   Rows Removed by Filter: 5432

Planning Time: 0.239 ms

Execution Time: 138.829 ms

 

100만 개의 Row 중, 5432개의 Row를 제외한 Row를 select하게 되면 데이터베이스 엔진이 이 수를 계산해서 인덱스를 조회하고 데이터에 접근하는 것보다 바로 데이터를 조회하는 것이 더 낫다고 판단하고, Index Scan대신 Sequential Scan을 사용한다.

 

이처럼 데이터베이스 엔진은 인덱스가 있다고 Index Scan을 사용하는 것이 아닌, 해당 쿼리에 적합하다고 판단되는 방식을 이용한다.

 

Index Only Scan

Index Only Scan은 인덱스에 필요한 데이터가 있는 경우 사용되는 방식이다.

인덱스에 필요한 값이 있기 때문에, 실제 데이터를 fetch하지 않아도 된다.

EXPLAIN ANALYZE
SELECT id FROM post;

결과

Index Only Scan using post_pkey on post (cost=0.42..6.16 rows=99 width=4) (actual time=0.006..0.014 rows=99 loops=1)

   Index Cond: (id < 100)

   Heap Fetches: 0

Planning Time: 0.139 ms

Execution Time: 0.029 ms

 

위 쿼리처럼 필요한 column 값이 인덱스에 이미 존재할 때 사용된다.

 

Index Scan 사용 시 고민해봐야 할 점
빠르게 데이터를 찾을 수 있게 만드는 index지만, 항상 모든 데이터를 빠르게 select 할 수 있는 것은 아니다.

 

index를 생성하면 데이터마다 대응되는 인덱스 트리값이 생겨나기 때문에 기본적으로 메모리를 적지않게 차지하게된다. 또한 데이터를 삽입, 수정, 삭제할 때마다 index값도 그에 맞춰주는 작업을 수행하기 때문에 추가적인 부하가 발생할 수 있다.

 

이와 유사하게 위의 예시와 같이 Index Scan이 Sequential Scan보다 항상 빠른 것은 아니다.

Index Scan은 내부적으로 랜덤 I/O를 사용하는데, 이 작업은 순차 I/O에 비해 4배 정도 느리다. 때문에 많은 양의 데이터를 scan할 경우 순차적으로 읽는 것보다 더 오래 걸릴 수 있다.

 

Bitmap Scan

Bitmap Scan은 Index Scan과 Sequential Scan이 조합된 방식이다.

Bitmap Scan은 Index Scan에서 발생할 수 있는 과도한 랜덤 I/O를 방지하면서, Index의 성능도 어느정도 가져올 수 있다.

 

데이터베이스가 Bitmap Scan을 이용하도록 author 컬럼을 인덱스로 생성한 후 autor로 검색을 해보았다.

CREATE INDEX idx_author ON post(author);

EXPLAIN ANALYZE
SELECT id FROM post WHERE id < 600000 AND author = 'author54';

결과

Bitmap Heap Scan on post (cost=115.21..8864.55 rows=6146 width=4) (actual time=1.873..60.768 rows=6000 loops=1)

   Recheck Cond: ((author)::text = 'author54'::text)

   Filter: (id < 600000)

   Rows Removed by Filter: 4000

   Heap Blocks: exact=8160

   -> Bitmap Index Scan on idx_author (cost=0.00..113.67 rows=10300 width=0) (actual time=0.692..0.700 rows=10000 loops=1)

       Index Cond: ((author)::text = 'author54'::text)

Planning Time: 0.105 ms

Execution Time: 105.692 ms

 

데이터베이스에서 첫 번째로 Bitmap Index Scan을 수행하고, 두 번째로 Bitmap Heap Scan을 수행한 것을 확인할 수 있다.

Bitmap Index Scan 단계에서는 index 자료구조를 스캔하며 조건에 해당하는 index의 데이터를 이용해서 bitmap을 생성한다. 이 bitmap에는 index에 해당하는 테이블의 Row에 접근할 수 있는 정보가 담겨있다.

Bitmap Heap Scan 단계에서는 앞서 생성된 bitmap을 스캔하면서 조건에 맞는 실제 데이터를 select 한다.

 

위 예시에서는 author 인덱스를 사용하여 author가 'author504'인 10,000개의 Row에 접근할 수 있는 bitmap을 생성한 후, id가 600,000이하인 6,000개의 Row를 결과로 반환했다.

 

이때 select할 데이터의 양이 줄면(현재 상황에서는 id의 범위 조건이 줄어들 경우) 데이터베이스가 Index Scan을 사용한다.

EXPLAIN ANALYZE
SELECT id FROM post WHERE id < 200000 AND author = 'author54';

결과

Gather (cost=1000.42..7512.26 rows=2038 width=4) (actual time=1.024..23.998 rows=2000 loops=1)

   Workers Planned: 2

   Workers Launched: 2

   -> Parallel Index Scan using post_pkey on post (cost=0.42..6308.46 rows=849 width=4) (actual time=0.020..17.282 rows=667 loops=1)

       Index Cond: (id < 200000)

       Filter: ((author)::text = 'author54'::text)

       Rows Removed by Filter: 66000

Planning Time: 0.080 ms

Execution Time: 39.262 ms

 

id 조건 범위를 200,000으로 줄일 경우, 데이터베이스가 Parallel Index Scan을 사용한다.

데이터베이스가 조건문에 사용할 column의 인덱스 유무 뿐만 아니라 실제로 가져와야 할 데이터의 크기도 고려하여 Table Scan 방법을 정한다는 것을 확인할 수 있다.

 

TID Scan

TID Scan은 데이터베이스가 실제 테이블의 데이터를 식별하기 위해 사용하는 TID라는 것을 이용한 쿼리를 사용할 때 사용된다.

TID는 Tuple Indecator의 줄임말로, PostgreSQL의 데이터에 존재하는 고유한 식별 값이다.

평소에는 숨겨져 있지만, 일반 column처럼 접근이 가능하다.

EXPLAIN ANALYZE
SELECT id FROM post WHERE ctid = '(1, 1)';

결과

Tid Scan on post (cost=0.00..4.01 rows=1 width=4) (actual time=0.016..0.031 rows=1 loops=1)

   TID Cond: (ctid = '(1,1)'::tid)

Planning Time: 0.060 ms

Execution Time: 0.080 ms

 

특정 Row의 실제 위치를 나타내는 6byte 값으로, 4byte는 페이지 번호, 2byte는 페이지 내의 tuple index를 나타낸다.

 

---

참고

https://seungtaek-overflow.tistory.com/5

https://blog.naver.com/PostView.naver?blogId=sssang97&logNo=222066082736

https://blog.naver.com/sssang97/222066082736