[PostgreSQL] 2. PostgreSQL Index 알아보기 (Index Type, Index Scan)

0. 들어가기 전

이전 챕터에서 PostgreSQL의 Internal, 내부 구조에 대해서 간략하게 살펴봤습니다.

 

이번에는 PostgreSQL에는 어떤 Index Type이 있는지, Index Scan은 어떤 것이 있는지 살펴보겠습니다.

Index는 깊게 들어가면 너무나 어려운 내용이라서 간략하게만 다뤄보도록 하겠습니다 :(

('PostgreSQL'의 Index에 대해서 알아보는 것이기 때문에, 기본 Index에 관한 개념은 알고 있다고 가정하고 다루지 않겠습니다!)

 

PostgreSQL의 Index를 공부하면서 목표로 한 점은 다음과 같습니다.

• 여러 PostgreSQL Index Type의 동작방식, 내부 원리를 설명할 수 있다.
• 여러 PostgreSQL 타입, 상황에 대해 어떤 Index를 적용할지 떠올릴 수 있다.
• 쿼리 실행 계획에서 마주하는 Scan 방식에 대해 왜 해당 Scan이 적용되었는지 떠올릴 수 있다.

 

이전까지는 PostgreSQL의 공식문서를 통해서 공부했지만, 다소 내용이 적고 어려운 느낌이 있었습니다.

그래서 PostgreSQL의 주요 Contributor로 이루어진 PostgresPro 팀에서 출판한 `PostgreSQL 14 Internals`를 읽고 공부한 부분을 작성해보도록 하겠습니다.

 

해당 문서는 아래 링크에서 무료 PDF로 받을 수 있고, 책을 구매할 수도 있습니다.

https://postgrespro.com/community/books/internals

PostgreSQL 14 Internals

 

---

1. PostgreSQL Index Types

먼저 PostgreSQL의 다양한 Index들에 대해서 알아보도록 하겠습니다.

 

PostgreSQL에서는 다양한 Index 타입이 존재하는데, 인덱스를 생성할 때 타입을 지정해서 생성할 수 있습니다.

일반적으로 다음과 같이 Index를 생성할 때, 타입을 지정하지 않으면 B-Tree 인덱스 타입이 지정되어 생성됩니다.

CREATE INDEX member_name_idx ON member (name);

 

타입을 지정하기 위해서는 'USING' 키워드를 사용하여 타입을 명시하면 됩니다.

CREATE INDEX member_name_idx ON member USING HASH(name);

 

 

각 Index Type은 모두 다른 알고리즘을 사용해서 인덱싱하므로 인덱스 타입에 따라 저장되는 형태가 달라질 수 있습니다.

또, Index Type에 따라 지원하는 연산자가 다르기 때문에 데이터, 상황에 맞는 인덱스 타입을 사용하는 것이 중요합니다.

 

따라서, 각 타입의 인덱싱 구조와 지원하는 연산자를 알아보면서 어떤 상황, 데이터에 적합한지 알아보도록 하겠습니다.

---

1-1. Hash Index

Hash Index는 Key-Value 기반의 Hash Table 형태로 디스크에 데이터를 인덱싱합니다.

결론적으로 Hash Index의 구조를 도식화하면 다음과 같습니다.

Hash Index 내부 구조

• 각 데이터 값들은 Hash Function에 의해 해싱되어 Disk 내의 Bucket(Hash Table) 형태로 저장됩니다.
• Key-Value 형태로, Key는 해싱된 데이터 값을 의미하고 Value로는 해당 Tuple이 있는 TID를 가집니다.
• 정렬된 순서를 보장하지 않기 때문에, 범위 연산(<, >, >=, <=)을 지원하지 않고 동등 연산(=)만 지원합니다.

 

Hash Index는 상대적으로 간단한 구조이고 인덱스 크기도 작다는 장점이 있지만, 일반적으로 자주 사용하지 않습니다.

왜냐하면, 대부분 인덱스를 사용할 때는 범위 검색을 하기 위함인데 동등 연산만 지원하기 때문에 잘 사용하지는 않습니다.

 

※ Hash Index 적절한 상황, 데이터

• 범위 연산 없이 동등 연산만을 사용하는 데이터

---

1-2. B-Tree Index

B-Tree Index는 PostgreSQL 뿐만 아니라 다른 DB 벤더도 기본 Index Type으로 할만큼 자주 사용되는 Index Type입니다.

결론적으로 B-Tree Index의 구조를 도식화하면 다음과 같습니다.

B-Tree 내부 구조

• 기본적으로 Balanced Tree의 구조로 이루어져 있습니다.
• B Tree는 하나의 노드에 여러 값을 가질 수 있고, 2개 이상의 자식 노드를 가질 수 있습니다. (그림은 이해를 돕기 위해 이진 트리처럼 1개의 값, 2개의 자식 노드로 가정했습니다.)
• 노드는 3종류로 나뉘며, 모두 다른 역할을 수행합니다.
  • Root Node : 처음의 검색 범위를 구분하기 위한 Index Key, 다음 자식 Node로 이동하기 위한 Pointer 저장
  • Branch Node : 다음 Node를 선택하기 위한 Index Key, 다음 자식 Node로 이동하기 위한 Pointer 저장
  • Leaf Node : 검색 Key에 해당하는지를 나타내는 Index Key, 실제 데이터가 위치한 TID 저장
• Root -> Branch -> Leaf Node를 거쳐 찾고자 하는 데이터의 TID를 찾는 구조입니다.

 

기본적인 특성은 위와 같고, Index에서 중요한 특성은 다음과 같습니다.

• Root -> Branch -> Leaf로의 빠른 탐색을 위해 모든 요소는 정렬되어 있습니다.
• 균형 트리이기 때문에 모든 Leaf Node는 같은 Depth를 가지고, 따라서 모든 값의 검색 시간은 같습니다.
• 각 노드에 저장할 수 있는 데이터 크기가 크고, 여러 개의 값을 저장할 수 있기 때문에 데이터가 많더라도 Depth는 항상 적습니다.
• Leaf Node는 정렬된 양방향 리스트로 설계되어 있기 때문에 리프 노드를 한 방향으로 탐색하면 정렬된 데이터 셋을 얻을 수 있습니다.
• 동등 연산자와 범위 비교 연산자를 지원합니다. 
  • =
  • >
  • >=
  • <
  • <=

 

일반적으로 데이터가 균형 분포 및 정렬되어 있어 성능이 준수하고 동등 연산, 범위 비교 연산을 지원한다는 점에서

Hash보다 B Tree를 기본 Index Type으로 지정한 것이 아닐까 싶습니다.

 

※ B Tree 적절한 상황, 데이터

• 일반적으로 B Tree는 다양한 상황, 데이터에 적절하기 때문에 다른 Type Index가 적절하지 않을 때 기본적으로 적용하면 좋을 것 같습니다.

---

1-3. GiST Index

GiST는 Generalized Search Tree로,

범위 쿼리나 공간 데이터, 사용자 정의 데이터 타입 등 다양한 데이터 구조를 인덱싱하기 위해 나온 타입입니다.

 

해당 Index는 앞서 소개된 PDF, PostgrePro의 GiST를 소개한 내용의 이미지를 인용하여 설명해보도록 하겠습니다.

https://postgrespro.com/blog/pgsql/4175817

Indexes in PostgreSQL — 5 (GiST)

 

일반적으로 GiST도 Tree 구조이기 때문에 각 Root, Branch, Leaf 노드를 동일하게 가집니다.

대신, 각 노드에서 가지는 정보가 다음과 같이 다릅니다.

• B Tree : Index Key & Next Node Pointer
• GiST : Predicate & Next Node Pointer

 

여기서 Predicate가 무엇일까요? 바로 Predicate는 조건을 나타내는 개념입니다.

PostgreSQL에서는 각 데이터에 따라서 정해진 Predicate 조건을 사용합니다. (Predicate 커스텀도 가능한 것으로 알고 있습니다.)

• Geometric Type (point, box, polygon, ...) : 각 공간 데이터가 나타내는 최소-최대 사각형 영역(MBR)을 Predicate 조건으로 사용
  • 해당 Predicate 조건을 통해 주어진 값들이 영역에 포함되는지, 교차하는지 등을 판단
  • EX) 특정 노드가 (1, 1), (5, 3), (2, 8) 등의 포인트를 포함한다면, Predicate : (1, 1)부터 (5, 8)까지의 범위
• Range Type (int4range, daterange, tsrange, ...) : 저장되는 최소-최대 범위를 Predicate 조건으로 사용
  • 해당 Predicate 조건을 통해 주어진 값들이 범위에 포함되는지를 판단
  • EX) 노드에 [1, 5), [3, 7), [2, 10)와 같은 범위가 포함되어 있다면, 노드의 Predicate 범위는 [1, 10)으로 설정
• Text Search Type (tsvector, tsquery) : 해당 데이터의 토큰 집합을 Predicate 조건으로 사용
  • 해당 Predicate 조건을 통해 Text 일치, 포함, 유사도 검색 사용
  • EX) 특정 노드에 "cat", "dog", "animal" 등의 토큰이 포함된 여러 tsvector가 존재한다면, 노드의 Predicate는 {cat, dog, animal}과 같은 토큰 집합으로 표현

 

이 중에서 Geometric Type을 예시로 들면, 다음과 같이 인덱싱된다고 표현할 수 있습니다.

origin : https://postgrespro.com/blog/pgsql/4175817

 

origin : https://postgrespro.com/blog/pgsql/4175817

 

해당 데이터는 PostgreSQL의 point 타입으로 나타낼 수 있고, 내부 GiST 구조는 B Tree와 같이 균형 트리로 다음과 같이 표현됩니다.

origin : https://postgrespro.com/blog/pgsql/4175817

 

 

• 다양한 비정형 데이터를 지원하는 만큼, 데이터 타입에 따라 다양한 연산자들을 지원합니다.
  • <<
  • &<
  • &>
  • >>
  • <<|
  • &<|
  • |&>
  • |>>
  • @>
  • <@
  • ~=
  • &&

데이터 타입에 따라 사용 예시도 다르고 많기 때문에 아래 문서를 참고하고 연산별 설명은 생략하도록 하겠습니다.

(간략하게 요약하면, 데이터가 범위, 영역에 포함되는지 어느 방향에 위치하는지(위, 아래, 오른쪽, 왼쪽)에 대해 판단하는 연산자들 입니다.)

https://www.postgresql.org/docs/6.3/c09.htm

Operators

 

 

※ GiST 적절한 상황, 데이터

• 비정형 데이터 (공간 데이터, 범위 데이터, 텍스트 데이터 등)
• 포함 요소 검색, 근접 요소 검색과 같은 상황

---

1-4. SP-GiST 

SP-GiST는 기본적으로 GiST를 기반으로 'SP'라는 이름이 추가된 Index입니다.

 

SP는 Space Patitioning으로 공간 파티셔닝에 특화된 Index임을 알 수 있습니다.

따라서 GiST와 달리 공간을 겹치지 않게 나누면서 non-balanced Tree를 형성합니다.

 

SP-GiST에서는 다음과 같은 개념이 GiST의 개념에 대응됩니다.

• 하위 노드의 정보 Pointer : lables
• 하위 노드가 만족해야하는 조건 Predicate : prefix

 

일반적인 개념은 GiST와 동일하고 '공간 파티셔닝', 'non-balanced Tree'가 다르기 때문에

어떤 점이 다른지 GiST와 동일한 예시로 살펴보도록 하겠습니다.

origin : https://postgrespro.com/blog/pgsql/4220639

 

origin : https://postgrespro.com/blog/pgsql/4220639

 

겹치는 영역으로 분리되었던 GiST와 달리 SP-GiST는 겹치는 영역없이 파티션 단위로 위의 그림처럼 공간을 분리합니다.

내부 구조를 살펴보면 다음과 같습니다.

origin : https://postgrespro.com/blog/pgsql/4220639

 

(4,4)가 파티셔닝의 중심인 Root Node가 되고 4번 영역에는 데이터가 없을 수 있기 때문에 non-balanced Tree가 형성됩니다.

계속해서 파티션 단위로 분할하여 파티셔닝을 하기 때문에 SP-GiST는 하위 노드 수(가지 수)가 적고 깊은 Depth를 가지게 됩니다.

 

 

※ SP-GiST 적절한 상황, 데이터

• non-balanced Tree인 만큼, 비대칭인 데이터 (큰 범위의 좌표 중 특정 지역에 밀집된 좌표 데이터 등)
• 공간 분할이 필요한 데이터

 

 

※ GiST / SP-GiST 둘 중 어떤 것을 사용?

GiST, SP-GiST 두 개의 인덱스를 살펴보다보면 비슷하다보니 사용 기준을 구분하는게 어려울 수 있습니다.

SP-GiST의 '공간 파티셔닝' 특성과 'non-balanced Tree' 특성에 초점을 맞춰 살펴보면 다음과 같이 구분할 수 있습니다.

• 포괄적이고 균형적인 데이터 검색 : GiST 
  • 기준 텍스트와 유사한 모든 텍스트 검색
• 계층이 존재하고 (분할이 되는) 비대칭적인 데이터 검색 : SP-GiST
  • 텍스트의 '접두어'만 일치하는 텍스트 검색

---

1-5. GIN

GIN은 Generalized Inverted Index의 약자로, 하나의 데이터가 여러 개별 요소로 구성된 데이터 타입을 인덱싱하기 위한 인덱스입니다.

• 여러 요소를 포함하는 Array Type
• Json의 여러 Key/Value를 포함하는 Json Type(json, jsonb)

 

GIN의 내부 구조를 이해하기 위해서는 GIN의 약자 중에서 'Inverted'에 주목해야 합니다.

일반적으로 하나의 요소를 가지는 데이터를 인덱싱할 때는 다음과 같은 구조로 인덱싱을 합니다.

• 해당 데이터로 Index Key를 생성하고, 해당 데이터가 존재하는 Tuple의 ID (TID)를 저장

 

해당 구조를 여러 요소가 존재하는 데이터 타입에 사용하면 어떻게 될지 예를 들어서 설명해보겠습니다.

• 여러 언어 데이터를 Array 타입으로 가지는 상황

ID | Array
----------------
1  | ['KOREAN', 'ENGLISH', 'JAPANESE']
2  | ['KOREAN']
3  | ['ENGLISH', 'JAPANESE']
4  | ['KOREAN', 'JAPANESE']

 

이때, 각 데이터로 Index Key를 생성하고 TID를 저장하는 기본 구조(B-Tree)를 따른다면 배열 요소 데이터들로 Key가 생성될 수 있을 것입니다.

(실제로는 PostgreSQL에서는 Array 타입에서 B Tree 인덱스를 지원하지 않습니다.)

 

이때, 여러 요소를 포함한 데이터에서의 쿼리는 대부분 '특정 요소가 포함되어 있는지'에 관한 쿼리일 것입니다.

해당 쿼리에서 위처럼 인덱싱한 인덱스가 효율적일까요? 특정 요소 하나로 키를 형성한게 아니기 때문에 인덱스를 사용하지 못할 것입니다.

 

 

이렇게 '특정 요소가 포함되어 있는지'에 관한 연산에 사용하기 위해 GIN은 다음과 같이 인덱싱을 합니다.

• 해당 컬럼에 존재하는 모든 요소를 Index Key로 사용하고, 해당 요소가 포함된 TID를 저장

 

이렇게 GIN을 사용했을 때 '특정 요소가 포함되어 있는지'에 관한 연산은 어떻게 처리될까요?

인덱싱된 해당 요소에 포함된 TID들을 한번에 가져와서 Scan하면 빠르게 데이터 셋을 가져올 수 있게 됩니다.

 

 

※ GIN 적절한 상황, 데이터

• 여러 요소가 포함된 데이터 타입 (Array, Json)
• tsvector에서도 포함된 키워드 확인 같은 상황에서 유리 (고객 리뷰에 특정 키워드가 포함된 리뷰를 빠르게 찾고자 할 때)
  • GIN 사용 시 키워드별로 인덱싱 가능

---

 

1-6. BRIN

BRIN은 필요한 행들을 빠르게 가져오는 것에 초점을 맞춘 다른 Index들과 달리 다른 목적에 초점을 맞춘 인덱스입니다.

BRIN은 불필요한 행들을 제거하는 것에 초점을 맞추고 있습니다.

 

BRIN의 내부 구조에서는 '범위'가 핵심 키워드입니다.

BRIN은 인덱싱 될 컬럼의 데이터를 여러 개의 '범위' 블록으로 나누어서 인덱싱하는 방식입니다.

origin : https://postgrespro.com/blog/pgsql/5967830

 

 

이때 중요한 점은 해당 블록에 데이터들의 TID를 저장하지 않고 블록 범위에 대한 MIN, MAX 요약 정보만 저장합니다.

• 나이를 나타내는 age 컬럼에 BRIN을 적용하면 나이대별로 블록이 생성됩니다.
• 해당 블록은 범위에 속하는 실제 행의 TID가 아닌, 범위의 Min / Max 값만 저장합니다.
• EX) age 20~30 블록 : MIN 20 / MAX 30 정보만 저장

 

이러한 방식을 통해 가지는 이점은 다음과 같습니다.

• 다른 인덱스 타입에 비해 요약 정보만 저장하기 때문에 인덱스 크기가 매우 작다.
  • 약 3천만 건의 데이터가 있는 테이블에서 B-Tree Index는 210MB, BRIN은 180KB의 크기를 가진다.

 

 

이때, 실제로 TID를 가지고 있지 않다면 어떻게 찾고자 하는 데이터를 가져오는지 궁금할 수 있습니다.

BRIN을 사용했을 때는 다음과 같이 생각하면 이해에 도움이 될 수 있습니다.

• BRIN은 찾고자 하는 데이터 셋을 가져오는 데 사용되지 않고, 찾고자 하는 데이터 셋의 범위를 가져오는데 사용된다.

 

실제로, BRIN을 사용한 컬럼에서 조건 검색이 들어오면 해당 조건에 해당하는 블록을 도출한 후 해당 범위를 Scan합니다.

이때 해당 범위에 검색 조건과 맞지 않는 데이터들이 존재할 수 있습니다.

• EX) 검색조건이 age ≤ 25일 때, BRIN의 범위 정보가 20~30일 수 있다.
• 이때는 age가 25보다 큰 데이터를 제외하는 Sequential Scan을 통해 필터링하여 20~25의 데이터들만 추출한다.

 

※ BRIN 적절한 상황, 데이터

• 연속적이고 규칙적인 데이터
  • BRIN의 범위 블록은 데이터가 저장된 순서에 따라 그대로 파티셔닝하는 느낌으로 나뉩니다.
  • 따라서, 정렬되지 않은 불연속적인 데이터가 하나의 범위 블록으로 묶인다면 데이터 오차가 커질 것입니다.
  • 그에 따라 Sequential Scan이 많이 발생하여 성능이 더 느릴 수 있습니다.

---

2. PostgreSQL Index Scan

앞에서는 PostgreSQL의 다양한 Index Type에 대해서 살펴봤습니다.

해당 Index Type에서는 데이터가 어떻게 인덱싱이 되는지 타입별로 살펴봤습니다.

 

인덱싱된 데이터는 실제로 어떻게 Scan이 되는 걸까요?

이전에는 Index를 사용하면 무조건 Index Scan이 발생하는 줄 알고 있었습니다.

그래서 다음과 같은 테이블에 인덱스를 생성하고 실행 계획을 분석한 순간 다음과 같이 예상치 못한 Scan이 나와 당황한 기억이 있습니다.

(테스트 용이라 테이블도 가장 간단하게 생성했었습니다.)

-- 테스트용 member 테이블 생성
CREATE TABLE member (
    id    BIGINT PRIMARY KEY,
    name  VARCHAR
);

-- member name 인덱스 생성
CREATE INDEX member_name_idx ON member (name);

-- seongha1, seognha2, seongha3 순으로 name을 가지는 member 100000만건 생성
... 생략

-- 'seongha1'인 이름 찾기
SELECT * FROM member WHERE name = 'seongha1'

 

Index 키워드가 Bitmap Index Scan으로 있긴 한데, 다른 형태의 Index Scan이 존재한다는 것을 알게 되었습니다.

 

따라서, 이번에는 PostgreSQL에서 데이터가 Scan되는 다양한 방식에 대해서 알아보도록 하겠습니다.

---

2-1. Index Scan

먼저, 가장 기본적인 Index Scan을 알아봅시다.

일반적으로 기본적인 Index Scan은 다음과 같이 동작합니다.

• Index가 설정된 데이터를 조회할 때 조건과 일치하는 데이터의 TID를 반환
• TID를 기반으로 실제 데이터를 찾아서 반환

 

일반적으로는 Index가 설정된 데이터를 조회할 때 Index Scan을 통해 데이터를 읽어옵니다.

모든 데이터를 Full Scan하는 대신 인덱싱된대로 데이터를 가져올 수 있기 때문에 Disk I/O를 줄이고 조회 성능을 높일 수 있습니다.

 

Index Scan은 가장 기본적인 인덱스를 사용했을 때의 Scan이므로 별다른 설명없이 넘어가도록 하겠습니다.

---

2-2. Bitmap Scan

그렇다면, 일반적이지 않은 앞서 든 예시에서 나왔던 Bitmap Scan은 어떤 Scan일까요?

 

Bitmap Scan을 이해하기 위해서는 먼저 Index Scan이 비효율적인 상황을 이해해야합니다.

해당 상황은 '인덱스 저장 순서와 실제 데이터의 저장 순서 유사도'인 Correlation과 관련이 있습니다.

• 일반적으로 B Tree Index를 사용한다고 했을 때 Index는 정렬된 상태를 유지하지만, 실제 데이터는 아닐 수 있습니다.
  • 인덱싱된 데이터가 정렬된 상태를 유지하더라도, 빠르게 인덱스를 찾을 수 있어서 인덱스를 찾는 Disk I/O를 줄일 뿐입니다.
  • 실제 데이터가 흩어져 있다면 실제 데이터를 가져오기 위한 페이지 이동이 잦아져 Disk I/O가 많아질 수 있습니다.
  • 이때, 이미 접근한 페이지도 다시 재조회하는 비용이 발생하여 Disk I/O가 많아질 수 있습니다.
• 위의 이유로 Correlation이 작다면, 실제 데이터 저장 순서가 정렬되어 있지 않다면 Index Scan은 비효율적일 것입니다.

 

이렇게 실제 데이터가 흩어져 있는, Correlation이 작은 상황일 때 잦은 페이지 이동으로 인한 Disk I/O를 줄이는 것이 Bitmap Scan입니다.

어떻게 실제 데이터가 흩어져 있을 때 Disk I/O를 줄일 수 있는지 살펴봅시다.

 

Bitmap Scan은 다음과 같은 2단계로 나뉩니다.

• Bitmap Index Scan
• Bitmap Heap Scan

 

Bitmap Index Scan

Bitmap Index Scan에서는 일반적인 Index Scan처럼 다음과 같은 동작을 수행합니다.

• Index를 통해 조건과 일치하는 데이터의 TID 반환

일반적인 Index Scan과 다른 점은 다음과 같습니다.

• 바로 실제 데이터를 조회하지 않고, TID를 Bitmap에 기록합니다.

이때, Bitmap은 데이터를 효율적으로 관리하기 위해 생성되는 PostgreSQL의 메모리 내 자료 구조로, 해당 Bitmap에 인덱스에 해당하는 TID들을 저장하게 됩니다.

 

 

Bitmap Heap Scan

가져올 실제 데이터 TID들이 있는 Bitmap이 Bitmap Index Scan을 통해 생성되면,

Bitmap Heap Scan 단계에서 Bitmap 기반으로 가져올 데이터의 페이지들을 읽고

해당 페이지에서 가져올 데이터들을 모두 읽어서 가져옵니다.

 

이러한 동작방식은 다음과 같은 이점이 있습니다.

• 한번 페이지를 접근했을 때, 해당 페이지에 존재하는 조건에 맞는 데이터를 모두 가져오기 때문에 페이지 재조회가 일어나지 않습니다.

 

따라서, Index Scan의 페이지 재조회 Disk I/O를 줄여서 더 최적의 성능을 제공하는 것입니다.

이러한 이유로 위의 예시에서 Optimizer는 Index Scan 대신 Bitmap Scan을 선택했던 것입니다.

 

 

※ Index Scan VS Bitmap Scan

그렇다면, 일반적으로 Bitmap Scan이 항상 더 Index Scan보다 성능이 좋을까요?

Bitmap Scan도 결국 Bitmap을 생성하는 비용을 생각해야 합니다.

 

Bitmap Scan은 Bitmap을 통해 Index Scan의 페이지 재조회 Disk I/O를 줄여서 특정 상황에 유리할 수 있습니다.

반대로, Index Scan에서 페이지 재조회가 일어나지 않는다면 Bitmap 생성 비용이 더 커져 Bitmap Scan이 비효율적일 것입니다.

 

따라서, 간단하게 각 Scan이 유리한 상황을 정리하면 다음과 같습니다.

• Index Scan
  • 실제 데이터가 정렬되어 있어서 이미 조회한 페이지를 재조회하지 않는 경우 (Correlation이 큰 경우)
• Bitmap Scan
  • 실제 데이터가 정렬되어 있지 않고 Index Scan 시 여러 번 페이지를 재조회해야 하는 경우 (Correlation이 작은 경우)

---

2-3. Sequential Scan

Sequential Scan은 PostgreSQL에서 수행하는 Table Full Scan이라고 할 수 있습니다.

말 그대로, 테이블의 모든 Tuple을 순차적으로 Scan하는 과정입니다.

 

일반적으로 Index가 존재하지 않을 때 사용되는 Scan입니다.

하지만, Index가 존재하더라도 인덱스 페이지에 접근하는 비용이 테이블을 Full Scan하는 Sequntial Scan 비용보다 클 수 있습니다.

이때는 Sequential Scan이 적용되게 됩니다.

---

2-4. Index-Only Scan

Index-Only Scan은 조금 특별한 Scan입니다.

바로, Covering Index가 적용될 때 사용되는 Scan 방식입니다.

 

Covering Index란, 쿼리에 사용되는 정보를 모두 가지고 있는 Index를 말합니다.

-- 테스트용 member 테이블 생성
CREATE TABLE member (
    id    BIGINT PRIMARY KEY,
    name  VARCHAR
);

-- member name 인덱스 생성
CREATE INDEX member_name_idx ON member (name);

-- seongha1, seognha2, seongha3 순으로 name을 가지는 member 100000만건 생성
... 생략

-- 'seongha1'인 이름 찾기
SELECT * FROM member WHERE name = 'seongha1'

 

위의 예시에서 'name' 컬럼에 Index를 생성했었습니다.

인덱스가 생성될 때 name 컬럼의 값이 Index Key가 되어 인덱스에 저장될 것입니다.

 

이때, 쿼리에 집중해보면 'SELECT *'로 name 이외의 해당 테이블의 모든 컬럼을 select 해야하는 것을 알 수 있습니다.

따라서 인덱스 Key로 name의 값이 있다고 하더라도 TID로 해당하는 Tuple을 찾아서 다른 컬럼의 데이터도 가져와야 합니다.

 

만약, 'SELECT name'으로 name만 가져와도 된다면 어떨까요?

TID로 Tuple을 찾을 필요 없이 인덱스의 Key로만 결과를 반환하면 됩니다.

이렇게 테이블에 접근하는 Disk I/O를 줄일 수 있는 것이 Covering Index, Index-Only Scan입니다.

 

---

이렇게 PostgreSQL의 다양한 Index Type과 Index Scan에 대해서 알아보았습니다.

글을 시작할 때 가졌던 목표는 다음과 같습니다.

• 여러 PostgreSQL Index Type의 동작방식, 내부 원리를 설명할 수 있다.
• 여러 PostgreSQL 타입, 상황에 대해 어떤 Index를 적용할지 떠올릴 수 있다.
• 쿼리 실행 계획에서 마주하는 Scan 방식에 대해 왜 해당 Scan이 적용되었는지 떠올릴 수 있다.

 

이러한 목표를 달성하기 위해서 Index Type에 대해서 간략하게 내부 동작과 적절한 상황들을 알아봤었습니다.

또, Scan 관련해서도 내부 원리를 살펴보며 쿼리 실행 계획에서 Scan 방식을 마주쳤을 때 추론할 수 있게 될 것 같습니다!

---

Reference

https://postgrespro.com/community/books/internals