PostgreSQL - Index Type

목차

1. Index Type
2. B-Tree
3. Hash
4. Gist
5. SP-GiST
6. GIN
7. BRIN

Index Type

PostgreSQL에는 B-Tree, HASH, GiST, SP-GiST, GIN, BGIN, 그리고 확장 기능으로 bloom으로 총 7개의 인덱스 유형을 가지고 있다.
CREATE INDEX는 기본적으로 가장 일반적인 상황에 적합한 B-Tree 인덱스를 생성한다.
다른 인덱스 유형을 사용하려면 USING 다음에 사용하려는 인덱스 유형을 추가해야한다.

CREATE INDEX index_name on table_name USING index_type(column_name);

B-Tree

B-tree는 어떤 순서로 정렬될 수 있는 데이터에 대한 동등 및 범위 쿼리를 처리할 수 있다.
PostgreSQL 쿼리 플래너는 index에 포함된 열이 < <= = >= > 중 하나의 연산자를 사용하여 비교할 때 항상 B-Tree 인덱스를 사용할 것을 고려한다.
이러한 연산자의 조합과 동등한 구성요소 ex) Between, In도 B-Tree 인덱스 검색으로 구옇할 수 있다.
또한 인덱스 열에 대한 IS NULL 또는 IS NOT NULL 조건은 B-Tree 인덱스와 함깨 사용될 수 있다.

옵티마이저는 패턴 일치 연산자 LIKE와 ~을 사용하는 쿼리에도 B-Tree 인덱스를 사용할 수 있다.
단, 패턴이 상수이고 문자열의 시작 부분에 고정된 경우에만 사용할 수 있다.
예를 들어 col LIKE ‘foo%’ 혹은 col ~ ‘‘^foo’는 사용이 가능하지만 col LIKE ‘%bar’는 사용할 수 없다.
데이터베이스가 C locale을 사용하지 않는 경우 패턴 일치 쿼리의 인덱싱을 지원하기 위해 특별한 연산자 클래스로 인덱스를 생성해야 할 수 있다.
locale은 initdb를 이용해 클러스터를 구성하면 자동으로 초기화된다.
특별히 옵션을 넣지 않으면 en_US.UTF8로 설정이 된다.

LC_COLLATE	String 정렬 순서
LC_CTYPE	문자 분류 (어떤글자인지, 대문자도 동일한지)
LC_MESSAGES	메세지 언어
LC_MONETARY	통화 형식
LC_NUMERIC	숫자 형식
LC_TIME	날짜 및 시간 형식

LC_COLLATE을 C로 설정하지 않으면 문자 처리가 느려지고, LIKE에서 사용되는 일반 인덱스를 사용하지 못한다.
locale 설정은 다음과 같은 SQL 기능에 영향을 준다.

1. order by를 사용한 쿼리에서 정렬 순서
   
2. 텍스트 데이터에서 표준 비교 연산자
   
3. upper, lower, initcap 함수
   
4. 패턴일치 연산자
   
5. TO_CHAR 계열 함수
   
6. LIKE를 사용한 인덱스 사용 능력
   이러한 이유로 필요한 경우에만 locale 설정을 변경해야한다.
   
   SHOW LC_COLLATE;을 실행하면 해당 옵션의 설정을 확인할 수 있다.
   

B-Tree 인덱스는 데이터를 정렬된 순서로 검색하는데도 사용할 수 있다.
이것이 항상 간단한 스캔 및 정렬보다 빠르지는 않지만, 간혹 도움이 된다.

Hash

Hash 인덱스는 index에 포함된 열의 값으로 생성된 32비트 해시 코드를 저장한다.
쿼리 플래너는 인덱스된 열이 = 연산자를 사용하여 비교할때 해시 인덱스를 사용할 것을 고려한다.

GiST

GiSt는 일반화된 검색 트리(Generalized Search Tree)다.
균형 잡힌 트리 구조의 접근 방법으로서, 임의의 인덱스 방식을 구현하기 위한 기본 템플릿 역활을 한다.
B트리, R트리 및 많은 다른 인덱스 방식을 GiST로 구현할 수 있다.
GiST의 장점은 데이터 유형에 적합한 엑세스 방법을 사용하여 사용자 정의 데이터 유형의 개발이 가능한 것이다.
여러 종류의 2차원 기하 데이터 유형을 위한 GiST 연산자 클래스가 포함되어 있고 다음과 같은 연산자를 사용하는 쿼리를 지원한다.

<<   &<   &>   >>   <<|   &<|   |&>   |>>   @>   <@   ~=   &&

GiST 인터페이스는 높은 수준의 추상화를 갖추고 있어서, 엑세스 방법 구현자가 엑세스하는 데이터 유형의 의미론만 구현하면 된다.
GiST 레이어 자체가 동시성, 로깅 및 트리 구조 검색을 처리한다.
GiST 기반 인덱스를 사용하면 도메인별 질문을 할 수 있는 쿼리를 만들 수 있다.

Gist 엑세스 방법을 실행하고, 실행하기 위해 필요한 것은 트리에 있는 키의 동작을 정의하는 여러 사용자 정의 방법을 구현하는 것 이다.
물론 이러한 메소드는 고급 쿼리를 지원하기 위해 꽤 복잡해야 하지만, 표준 쿼리(B-Tree, R-Tree)에 대해서는 비교적 간단하다.

GiST를 위한 인덱스 연산자 클래스는 다섯 가지 메서드를 제공해야 하며, 선택적으로 여섯 가지 메서드를 제공할 수 있다.
인덱스의 정확성은 같은 메서드, 일관된 메서드 및 합집합 메서드의 적절한 구현에 의해 보장되며, 인덱스의 효율성(크기 및 속도)은 패널티 메서드 및 픽스플릿 메서드에 따라 달라진다.
선택적으로 사용할 수 있는 두 가지 메서드는 압축 및 압축 해제이며, 이를 통해 인덱스가 인덱싱하는 데이터와 다른 유형의 내부 트리 데이터를 가질 수 있다.
리프는 인덱싱된 데이터 유형이어야 하며, 다른 트리 노드는 모든 C 구조체일 수 있습니다.
트리의 내부 데이터 유형이 SQL 수준에서 존재하는 경우, CREATE OPERATOR CLASS 명령의 STORAGE 옵션을 사용할 수 있다.
선택적 메서드 중 8번째는 연산자 클래스가 순서화된 스캔(가장 가까운 이웃 검색)을 지원하려는 경우 필요하다.
선택적 메서드 중 9번째는 fetch로 압축 메서드가 생략된 경우에는 인덱스 전용 스캔을 지원하려는 경우 필요하다.
선택적 메서드 중 10번째는 optsions로 연산자 클래스에 사용자 지정 매개 변수가 있는 경우 필요하다.
선택적 메서드 중 11번째 sortsupport는 GiST 인덱스를 빌드하는 속도를 높이기 위해 사용된다.

Gist 인덱스를 구현하는 가장 간단한 방법은 모든 항목을 하나씩 삽입하는 것인데, 이 방법은 대규모 인덱스에 대해 속도가 느릴 수 있다.
냐하면 인덱스 튜플이 인덱스 전체에 흩어져 있고, 인덱스가 캐시에 들어갈만큼 충분히 크다면, 많은 랜덤 I/O가 필요하기 때문이다.
PostgreSQL은 GiST 인덱스의 초기 빌드를 위해 두 가지 대체 방법을 지원하는데, sorted와 buffered이다.

sorted 모드는 각 opclass가 인덱스에 제공하는 sortsupport 함수를 제공하는 경우에만 사용할 수 있다.
이 방법이 일반적으로 가장 좋기 때문에 기본적으로 사용된다.

buffered 모드는 튜플을 즉시 인덱스에 직접 삽입하지 않고 작동한다.
이 방법은 비순서화된 데이터 세트에 필요한 랜덤 I/O 양을 현저하게 줄일 수 있다.
잘 정렬된 데이터 세트의 경우 혜택이 작거나 없을 수 있다.
왜냐하면 한 번에 새로운 튜플을 받는 페이지 수가 매우 적기 때문에 해당 페이지들은 캐시에 들어가며 전체 인덱스가 캐시에 들어가지 않더라도 이득을 볼 수 있다.
buffered 모드는 단순한 방법보다 패널티 함수를 더 자주 호출해야 하므로 약간의 추가 CPU 자원을 소비한다.
또한 버퍼에는 결과 인덱스의 크기만큼의 임시 디스크 공간이 필요하다.
버퍼링은 결과 인덱스의 품질에도 긍정적이거나 부정적인 영향을 미칠 수 있다.
이 영향은 입력 데이터의 분포 및 연산자 클래스 구현과 같은 여러 요소에 따라 달라진다.

정렬이 불가능한 경우, GiST 인덱스 빌드는 기본적으로 인덱스 크기가 effective_cache_size에 도달할 때 버퍼링 방법으로 전환된다.
버퍼링은 CREATE INDEX의 buffering 매개변수를 사용하여 수동으로 강제하거나 방지할 수 있다.
기본 동작은 대부분의 경우에 적합하지만 입력 데이터가 정렬되어 있는 경우 버퍼링을 비활성화하면 빌드 속도가 약간 빨라질 수 있다.

SP-GiST

SP-GiST는 Space-Partitioned GiST의 약어다.
SP-GiST는 분할 검색 트리를 지원하여 쿼드 트리, k-d 트리, 라디스 트리(트라이)와 같은 다양한 비균형 데이터 구조를 개발하는 데 도움을 준다.
이러한 구조들의 공통 특징은 검색 공간을 반복적으로 동일한 크기일 필요는 없는 파티션으로 분할한다는 것이다.
분할 규칙과 잘 맞는 검색은 매우 빠를 수 있다.
다음과 같은 연산자를 사용하는 쿼리를 지원한다.

<<   >>   ~=   <@   <<|   |>>

메인 메모리에서는 일반적으로 포인터로 연결된 동적으로 할당된 노드 세트로 설계된다.
이는 이러한 포인터 체인이 상당히 길어져 많은 디스크 액세스를 필요로 할 수 있기 때문에 직접 디스크에 저장하는 데 적합하지 않다.
반면에 디스크 기반 데이터 구조는 I/O를 최소화하기 위해 높은 팬아웃을 가져야 한다.

팬 아웃은 논리 회로에서 하나의 논리 게이트의 출력이 얼마나 많은 논리 게이트의 입력으로 사용되는가를 의미한다.
팬 아웃이 크다는 말은 하나의 출력이 많은 논리게이트의 입력으로 사용된다는 뜻이다.

SP-GiST는 검색 트리 노드를 디스크 페이지에 매핑하여 검색이 많은 노드를 횡단하더라도 소수의 디스크 페이지에만 액세스할 수 있도록 하는 것이다.

두 개의 포인트 유형에 대한 연산자 클래스 중 quad_point_ops가 기본값이다.
kd_point_ops는 동일한 연산자를 지원하지만 다른 인덱스 데이터 구조를 사용하여 일부 응용 프로그램에서 더 나은 성능을 제공할 수 있다.

quad_point_ops, kd_point_ops 및 poly_ops 연산자 클래스는 인덱싱된 포인트 또는 폴리곤 데이터 집합에 대한 k-최근접 이웃 (k-NN) 검색을 가능하게 하는 <-> 순서 지정 연산자를 지원한다.

SP-GiST는 높은 수준의 추상화를 제공하여 액세스 방법 개발자가 주어진 데이터 유형에 특화된 메서드만 구현하면 된다.
SP-GiST 코어는 효율적인 디스크 매핑 및 트리 구조 검색을 담당한다.
또한 동시성 및 로깅 고려 사항도 처리한다.

SP-GiST 트리의 리프 튜플은 일반적으로 인덱스된 열과 동일한 데이터 유형의 값을 포함하고 있지만, 손실 있는 표현을 포함할 수도 있다.
루트 수준에 저장된 리프 튜플은 원래의 인덱스된 데이터 값을 직접 나타내지만, 하위 수준의 리프 튜플은 접미사와 같은 부분 값만 포함할 수 있다.
이 경우, 연산자 클래스 지원 함수는 리프 수준에 도달하기 위해 전달된 내부 튜플로부터 축적된 정보를 사용하여 원래 값을 재구성할 수 있어야 한다.

SP-GiST 인덱스가 INCLUDE 열을 사용하여 생성되면 해당 열의 값도 리프 튜플에 저장된다.

내부 튜플은 검색 트리의 분기점이기 때문에 더 복잡하다.
각 내부 튜플에는 유사한 리프 값 그룹을 나타내는 하나 이상의 노드 집합이 포함된다.
노드에는 다른 하위 수준의 내부 튜플로 이어지는 다운링크 또는 동일한 인덱스 페이지에 위치한 일련의 리프 튜플로 이어지는 다운링크가 포함된다.
일반적으로 각 노드에는 설명하는 레이블이 있다.
예를 들어, 라디스 트리에서 노드 레이블은 문자열 값의 다음 문자일 수 있다.
또는 연산자 클래스가 모든 내부 튜플에 대해 고정된 노드 집합을 사용하는 경우 노드 레이블을 생략할 수도 있다.
선택적으로 내부 튜플에는 그 멤버를 설명하는 접두사 값이 포함될 수 있다.
라디스 트리에서 이것은 표현된 문자열의 공통 접두사가 될 수 있다.
접두사 값은 실제로 접두사일 필요가 없으며, 연산자 클래스에서 필요한 모든 데이터가 될 수 있다.
예를 들어, 쿼드 트리의 경우 네 개의 사분면이 중심점을 중심으로 측정되는 중심점을 저장할 수 있다.
그러면 쿼드 트리 내부 튜플은 이 중심점 주위의 네 개의 사분면에 해당하는 네 개의 노드를 포함한다.

일부 트리 알고리즘은 현재 튜플의 레벨(또는 깊이)에 대한 지식을 필요로 하기 때문에, SP-GiST 코어는 트리를 내려가는 동안 연산자 클래스가 레벨 카운팅을 관리할 수 있는 기능을 제공한다.
또한, 필요할 때 표현된 값을 점진적으로 재구성하는 기능과 트리 하강 중에 추가 데이터(트래버스 값이라고 함)를 전달하는 기능도 지원한다.

SP-GiST 코어 코드는 null 항목을 처리한다.
SP-GiST 인덱스는 인덱스된 열의 null에 대한 항목을 저장하지만, 이는 인덱스 연산자 클래스 코드에서 숨겨진다.
null 인덱스 항목이나 검색 조건은 영원히 연산자 클래스 메서드에 전달되지 않는다.
SP-GiST 연산자가 엄격하며 null 값을 처리할 수 없다고 가정된다.

SP-GiST를 위한 인덱스 연산자 클래스는 다섯 가지 사용자 정의 메서드를 제공해야 하며, 두 가지는 선택적이다.
다섯 가지 필수 메서드는 모두 두 개의 내부 인수를 받는 관례를 따른다.
첫 번째 인수는 지원 메서드에 대한 입력 값이 포함된 C 구조체에 대한 포인터이며, 두 번째 인수는 결과 값을 배치해야 하는 C 구조체에 대한 포인터다.
네 가지 필수 메서드는 모두 결과 값이 출력 구조체에 나타나므로 void를 반환한다.
그러나 leaf_consistent는 불리언 결과를 반환한다.
메서드는 입력 구조체의 필드를 수정해서는 안 된다.
모든 경우에, 사용자 정의 메서드를 호출하기 전에 출력 구조체는 모두 0으로 초기화된다.
선택적인 여섯 번째 메서드인 compress는 인덱싱할 데이터를 나타내는 단일 인수를 받아 리프 튜플에 물리적으로 저장할 수 있는 값을 반환한다.
선택적인 일곱 번째 메서드인 options는 C 구조체에 대한 내부 포인터를 받아 연산자 클래스별 매개변수를 배치하고 void를 반환한다.

모든 SP-GiST 지원 메서드는 일반적으로 단기간의 메모리 컨텍스트에서 호출된다.
즉, 각 튜플 처리 후에 CurrentMemoryContext가 재설정된다.
따라서 palloc으로 할당한 모든 것을 pfree하는 것에 대해 걱정할 필요는 없다.
config 메서드는 예외입니다.
하지만 메모리 누수를 피하려고 노력해야 한다.
일반적으로 config 메서드는 전달된 매개변수 구조체에 상수를 할당하는 것 외에는 아무것도 수행하지 않아도 된다.

인덱스된 열이 정렬 가능한 데이터 유형인 경우, 표준 PG_GET_COLLATION() 메커니즘을 사용하여 인덱스 정렬이 모든 지원 메서드에 전달된다.

개별 리프 튜플과 내부 튜플은 하나의 인덱스 페이지(기본값은 8kB)에 들어가야 한다.
따라서 가변 길이 데이터 유형의 값을 인덱싱할 때는 각 트리 레벨이 페이지에 맞는 길이의 접두사를 포함하고 최종 리프 레벨이 페이지에 맞는 길이의 접미사를 포함하는 라디스 트리와 같은 방법을 사용하여 긴 값만 처리할 수 있다.
연산자 클래스는 longValuesOK를 true로 설정해야 할 경우에만 이를 수행할 준비가 되어 있다.
그렇지 않으면 SP-GiST 코어는 인덱스 페이지에 맞지 않는 값을 인덱싱하는 모든 요청을 거부한다.

마찬가지로, 내부 튜플이 인덱스 페이지에 맞게 너무 커지지 않도록 하는 것은 연산자 클래스의 책임이다.
이는 하나의 내부 튜플에 사용할 수 있는 자식 노드의 수와 접두사 값의 최대 크기를 제한한다.

또 다른 제한 사항은 내부 튜플의 노드가 일련의 리프 튜플을 가리킬 때, 해당 튜플들이 모두 동일한 인덱스 페이지에 있어야 한다는 것이다.
이는 이러한 튜플들을 연결하는 링크에서 싱크를 줄이고 공간을 절약하기 위한 설계 결정이다.
리프 튜플 집합이 페이지에 대해 너무 커지면 분할이 수행되고 중간 내부 튜플이 삽입된다.
이 문제를 해결하기 위해서는 새로운 내부 튜플이 리프 값의 집합을 여러 노드 그룹으로 나눠야 한다.
연산자 클래스의 picksplit 함수가 이를 수행하지 못하면, SP-GiST 코어는 아래에 설명할 특별한 조치에 의존한다.

longValuesOK가 true로 설정된 경우, SP-GiST 트리의 연속된 레벨이 내부 튜플의 접두사와 노드 레이블로 더 많은 정보를 흡수하여 필요한 리프 데이터를 점차 줄이고, 결국 페이지에 맞게 만들 것으로 기대된다.
연산자 클래스의 버그로 인해 무한 삽입 루프가 발생하는 것을 방지하기 위해, SP-GiST 코어는 선택 메서드 호출의 열 번의 주기 내에도 리프 데이터가 더 작아지지 않으면 오류를 발생시킨다.

일부 트리 알고리즘은 각 내부 튜플에 대해 고정된 노드 세트를 사용한다.
예를 들어, 쿼드 트리의 경우 항상 내부 튜플의 중심점 주변의 네 개의 사분면에 해당하는 정확히 네 개의 노드가 있다.
이러한 경우 코드는 일반적으로 노드를 번호별로 처리하며 명시적인 노드 레이블이 필요하지 않는다.
노드 레이블을 억제하고 (그로 인해 일부 공간을 절약할 수 있도록) picksplit 함수는 노드 레이블 배열에 대해 NULL을 반환할 수 있으며, 마찬가지로 spgSplitTuple 작업 중 choose 함수는 prefixNodeLabels 배열에 대해 NULL을 반환할 수 있다.
이로써 choose 및 inner_consistent에 대한 후속 호출 중에는 노드 레이블이 NULL로 설정된다.
원칙적으로 같은 인덱스에서 일부 내부 튜플에는 노드 레이블을 사용하고 다른 내부 튜플에는 노드 레이블을 생략할 수 있다.

노드가 레이블이 없는 내부 튜플과 작업할 때, choose가 spgAddNode를 반환하는 것은 오류다. 이런 경우에는 노드 세트가 고정되어 있어야 하기 때문이다.

operator class의 picksplit 함수가 제공된 리프 값을 적어도 두 개 이상의 노드 범주로 분할하지 못할 때, SP-GiST 코어는 picksplit의 결과를 무시하고 재정의할 수 있다.
이런 경우, 새로운 내부 튜플은 각각이 picksplit이 사용한 하나의 노드에 대해 동일한 레이블 (있는 경우)을 가진 여러 노드로 생성되며, 리프 값은 이러한 동등한 노드들 사이에서 무작위로 분할된다.
allTheSame 플래그가 내부 튜플에 설정되어 있어 choose 및 inner_consistent 함수에게 해당 튜플이 기대할 수 있는 노드 집합을 가지고 있지 않음을 알린다.

allTheSame 튜플을 처리할 때, choose 결과가 spgMatchNode로 해석되어 새로운 값이 동등한 노드 중 하나에 할당될 수 있다는 것을 의미한다.
코어 코드는 제공된 nodeN 값은 무시하고 무작위로 하나의 노드로 이동하여 트리를 균형있게 유지합니다.
choose가 spgAddNode를 반환하는 것은 오류다.
그것은 노드들이 모두 동등하지 않기 때문이다.
따라서 삽입해야 하는 값이 기존의 노드와 일치하지 않는 경우 spgSplitTuple 작업을 사용해야 한다.

allTheSame 튜플을 처리할 때, 모든 노드가 동등하기 때문에 inner_consistent 함수는 모든 노드를 지속적으로 인덱스 검색의 대상으로 반환하거나 반환하지 않아야 한다.
노드의 의미에 대해 inner_consistent 함수가 일반적으로 가정하는 정도에 따라 특수한 경우 코드가 필요할 수도 있고 그렇지 않을 수도 있다.

PostgreSQL 소스 배포에는 SP-GiST를 위한 여러 인덱스 연산자 클래스 예제가 포함되어 있다.
코드를 보려면 src/backend/access/spgist/ 및 src/backend/utils/adt/에서 확인할 수 있다.

GIN

GIN은 Generalized Inverted Index의 줄임말이다.
GiST 및 SP-GiST와 마찬가지로 GIN은 많은 다양한 사용자 정의 인덱싱 전략을 지원할 수 있으며, GIN 인덱스를 사용할 수 있는 특정 연산자는 인덱싱 전략에 따라 다르다.
예를 들어, PostgreSQL의 표준 배포판에는 배열에 대한 GIN 연산자 클래스가 포함되어 있으며, 이 클래스는 아래의 연산자를 사용하는 쿼리를 지원한다.

<@   @>   =   &&

배열과 같은 여러 구성 요소 값을 포함하는 데이터 값에 적합한 “역 인덱스”이다.
역 인덱스에는 각 구성 요소 값에 대한 별도의 항목이 포함되어 있으며, 특정 구성 요소 값의 존재를 효율적으로 처리할 수 있다.
GIN은 색인화할 항목이 복합 값인 경우와 색인에 의해 처리되어야 하는 쿼리가 복합 항목 내에서 나타나는 요소 값을 검색해야 하는 경우에 사용된다.
예를 들어, 항목은 문서일 수 있고, 쿼리는 특정 단어를 포함하는 문서를 검색하는 것일 수 있다. 여기서 항목이란 색인화될 복합 값을 가리키는 용어이고, 키는 요소 값을 가리킨다.
GIN은 항목 값 자체가 아니라 키를 저장하고 검색한다.

GIN 인덱스는 (키, 포스팅 리스트) 쌍의 집합을 저장하는데, 포스팅 리스트는 키가 발생하는 행 ID의 집합이다.
항목이 하나 이상의 키를 포함할 수 있기 때문에 동일한 행 ID가 여러 포스팅 리스트에 나타날 수 있다.
각 키 값은 한 번만 저장되므로 GIN 인덱스는 동일한 키가 여러 번 나타나는 경우에 매우 콤팩트하다.

GIN은 특정 연산을 가속화하는 데 필요한 구체적인 작업을 알 필요가 없는 일반화된 접근 방식이다.
대신 특정 데이터 유형에 대해 정의된 사용자 정의 전략을 사용한다.
전략은 색인화된 항목 및 쿼리 조건에서 키를 추출하는 방법과 쿼리를 실제로 만족하는지 여부를 결정하는 방법을 정의한다.

jsonb 유형에 대한 두 가지 연산자 클래스 중 jsonb_ops가 기본값이다.
jsonb_path_ops는 더 적은 연산자를 지원하지만 해당 연산자에 대해 더 나은 성능을 제공한다.

GIN 인터페이스는 데이터 유형의 의미를 구현하는 것만을 요구하는 높은 수준의 추상화를 가지고 있다.
GIN 레이어 자체가 동시성, 로깅 및 트리 구조 검색을 처리한다.

GIN 액세스 방법을 작동시키기 위해 필요한 것은 몇 가지 사용자 정의 메서드를 구현하는 것뿐이다.
이 메서드들은 트리 내에서 키의 동작과 키 간의 관계, 색인화된 항목 및 색인 가능한 쿼리를 정의한다.
“부분 일치” 쿼리를 지원하려면 연산자 클래스가 comparePartial 메서드를 제공해야 하며, extractQuery 메서드가 부분 일치 쿼리를 만났을 때 pmatch 매개변수를 설정해야 한다.

다양한 Datum 값의 실제 데이터 유형은 연산자 클래스에 따라 다르다.
extractValue에 전달되는 항목 값은 항상 연산자 클래스의 입력 유형이며, 모든 키 값은 클래스의 저장 유형이어야 한다.
extractQuery, consistent 및 triConsistent에 전달되는 쿼리 인수의 유형은 전략 번호로 식별된 클래스 멤버 연산자의 오른쪽 입력 유형이다.
색인화된 유형과 동일할 필요는 없으며, 올바른 유형의 키 값을 추출할 수 있다면 된다.
그러나 연산자에 따라 실제 유형이 달라질 수 있으므로 이 세 가지 지원 함수의 SQL 선언에서는 쿼리 인수로 opclass의 색인화된 데이터 유형을 사용하는 것이 권장된다.

내부적으로 GIN 인덱스는 키 위에 구성된 B-트리 인덱스를 포함하며, 각 키는 하나 이상의 색인화된 항목의 요소(ex : 배열의 멤버)다.
리프 페이지의 각 튜플에는 B-트리 포인터(“포스팅 트리”라고 함)를 포함하거나 인덱스 튜플 하나에 키 값과 함께 맞출만큼 충분히 작은 경우 힙 포인터의 간단한 목록(“포스팅 목록”이라고 함)이 포함된다.

PostgreSQL 9.1부터는 null 키 값이 인덱스에 포함될 수 있다.
또한, extractValue에 따라 null이거나 키가 없는 색인화된 항목에 대한 플레이스홀더 null이 인덱스에 포함된다.
이를 통해 비어 있는 항목을 찾아야 하는 검색을 수행할 수 있다.

다중 열 GIN 인덱스는 복합 값(열 번호, 키 값) 위에 단일 B-트리를 구축함으로써 구현된다.
다른 열의 키 값은 서로 다른 유형일 수 있다.

GIN 인덱스를 업데이트하는 것은 역 인덱스의 본질적인 특성 때문에 일반적으로 느리다.
색인화된 항목에서 추출된 각 키에 대해 하나씩 힙 행 하나를 삽입하거나 업데이트하는 것은 인덱스에 많은 삽입을 유발할 수 있다.
GIN은 새 튜플을 대기 중인 항목의 임시, 정렬되지 않은 목록에 삽입함으로써 이 작업을 많이 연기할 수 있다.
테이블이 vacuum되거나 autoanalyze되거나 gin_clean_pending_list 함수가 호출되거나 대기 중인 목록이 gin_pending_list_limit보다 크게되면 항목은 초기 인덱스 생성 중에 사용되는 동일한 대량 삽입 기술을 사용하여 주 GIN 데이터 구조로 이동된다.
이는 추가적인 vacuum 오버헤드를 포함하여 GIN 인덱스 업데이트 속도를 크게 향상시킨다.
또한 오버헤드 작업은 전경 쿼리 처리 대신 백그라운드 프로세스에서 수행될 수 있다.

이 접근 방식의 주요 단점은 일반적인 인덱스 검색뿐만 아니라 대기 중인 항목 목록을 스캔해야 하므로 대기 중인 항목 목록이 크면 검색이 크게 느려질 수 있다는 것이다.
또 다른 단점은 대부분의 업데이트가 빠르지만 대기 중인 목록이 “너무 크게”되는 업데이트는 즉시 정리 주기가 발생하고 따라서 다른 업데이트보다 훨씬 느릴 수 있다는 것이다.
올바른 autovacuum의 사용으로 이러한 두 가지 문제를 최소화할 수 있습니다.

일관된 응답 시간이 업데이트 속도보다 중요한 경우 GIN 인덱스의 fastupdate 저장 매개변수를 끄는 것으로 대기 중인 항목의 사용을 비활성화할 수 있다.

GIN은 “부분 일치” 쿼리를 지원할 수 있다.
이는 쿼리가 하나 이상의 키에 대해 정확한 일치를 결정하지 않지만 가능한 일치 항목이 비교 지원 메서드에 의해 결정된 키 정렬 순서 내에서 키 값의 상당히 좁은 범위 내에 있을 때 발생한다.
extractQuery 메서드는 정확히 일치해야 하는 키 값을 반환하는 대신에 검색할 범위의 하한이 되는 키 값을 반환하고 pmatch 플래그를 true로 설정한다.
그런 다음 키 범위를 comparePartial 메서드를 사용하여 스캔한다.
comparePartial은 일치하는 인덱스 키에 대해 0을 반환해야 하며, 검색할 범위 내에 있는 비일치에 대해 0보다 작은 값을 반환하거나 일치할 수 있는 범위를 지나간 경우 0보다 큰 값을 반환해야 한다.

GIN 인덱스에 삽입하는 것은 각 항목마다 많은 키가 삽입될 가능성이 있기 때문에 느릴 수 있다.
따라서 대량 삽입을 수행할 때는 GIN 인덱스를 삭제하고 대량 삽입을 완료한 후에 다시 만드는 것이 좋다.

GIN은 색인 가능한 연산자가 strict하다고 가정한다.
이는 extractValue가 null 항목 값에 대해 전혀 호출되지 않을 것을 의미한다.
그리고 extractQuery도 null 쿼리 값에 대해 호출되지 않을 것입니다.
그러나 null 키 값이 null이 아닌 복합 항목 또는 쿼리 값 내에 포함된 경우에는 지원된다.

BRIN

BRIN은 블록 범위 인덱스(Block Range Index)의 줄임말이다.
BRIN은 특정 열이 테이블 내에서 물리적 위치와 어떤 자연스러운 상관 관계를 가지는 매우 큰 테이블을 처리하기 위해 설계되어서 테이블의 연속적인 물리적 블록 범위에 저장된 값에 대한 요약 정보를 저장한다. 따라서 테이블 행의 물리적 순서와 잘 상관된 열에 대해 가장 효과적이다.

GiST, SP-GiST 및 GIN과 마찬가지로 BRIN은 여러 다양한 인덱싱 전략을 지원할 수 있으며, BRIN 인덱스에 사용할 수 있는 특정 연산자는 인덱싱 전략에 따라 다르다.
선형 정렬 순서를 가진 데이터 유형의 경우 인덱싱된 데이터는 각 블록 범위의 열의 값 중 최솟값과 최댓값에 해당한다.
아래의 연산자를 사용하는 쿼리를 지원한다.

<   <=   =   >=   >

BRIN은 블록 범위(또는 “페이지 범위”)의 개념으로 작동한다.
블록 범위는 테이블에서 물리적으로 인접한 페이지 그룹이다.
각 블록 범위에 대해 인덱스에 의해 일부 요약 정보가 저장된다.
예를 들어, 매장의 주문을 저장하는 테이블은 각 주문이 배치된 날짜 열을 가질 수 있으며, 대부분의 경우 더 이른 주문 항목은 테이블에서 더 이른 위치에 나타날 것이다.
ZIP 코드 열을 저장하는 테이블은 동일한 도시의 모든 코드가 자연스럽게 함께 그룹화될 수 있다.

BRIN 인덱스는 일반적인 비트맵 인덱스 스캔을 통해 쿼리를 충족시킬 수 있으며, 인덱스에 의해 저장된 요약 정보가 쿼리 조건과 일치하는 경우 각 범위 내의 모든 페이지에 있는 모든 튜플을 반환한다.
쿼리 실행자는 이러한 튜플을 다시 확인하고 쿼리 조건과 일치하지 않는 항목을 삭제한다.
다시 말해, 이러한 인덱스는 손실이 발생한다.
BRIN 인덱스는 매우 작기 때문에 인덱스를 스캔하는 것은 순차 스캔과 비교하여 거의 추가 오버헤드가 발생하지 않지만, 일치하는 튜플을 포함하지 않는 것으로 알려진 테이블의 큰 부분을 스캔하는 것을 피할 수 있다.

BRIN 인덱스가 저장할 특정 데이터 및 인덱스가 충족시킬 수 있는 특정 쿼리는 인덱스의 각 열에 대해 선택된 연산자 클래스에 따라 다르다.
선형 정렬 순서를 가진 데이터 유형은 각 블록 범위 내의 최솟값과 최댓값을 저장하는 연산자 클래스를 가질 수 있다.
예를 들어, 지형 유형은 블록 범위 내의 모든 객체의 바운딩 박스를 저장할 수 있다.

블록 범위의 크기는 pages_per_range 저장 매개변수에 의해 인덱스 생성 시에 결정됩니다. 인덱스 항목의 수는 페이지당 선택된 값을 나눈 관계의 크기와 동일하다.
따라서 더 많은 인덱스 항목을 저장해야하기 때문에 페이지 숫자가 작을수록 인덱스가 더 커지는 동시에 저장된 요약 데이터가 더 정확하고 인덱스 스캔 중에 더 많은 데이터 블록을 건너뛸 수 있습니다.

생성 시, 모든 기존 힙 페이지가 스캔되고 각 범위에 대한 요약 인덱스 튜플이 생성된다.
이 때 마지막에 있는 범위를 포함하여 모든 범위에 대해 요약 정보가 생성된다.
새로운 페이지에 데이터가 채워지면 이미 요약된 페이지 범위는 새로운 튜플의 데이터로 요약 정보가 업데이트된다.
새로운 페이지가 생성되면서 마지막으로 요약된 범위에 속하지 않는 경우, 새 페이지가 속한 범위는 자동으로 요약 튜플을 획득하지 않는다.
해당 튜플은 나중에 호출되는 요약 실행을 통해 요약될 때까지 요약되지 않은 상태로 유지된다.

페이지 범위의 초기 요약화를 트리거하는 여러 가지 방법이 있다.
테이블이 수동으로 또는 autovacuum에 의해 vacuum되면 모든 기존에 요약되지 않은 페이지 범위가 요약된다.
또한, 인덱스의 autosummarize 매개변수가 활성화된 경우(기본적으로 비활성화됨), 해당 데이터베이스에서 autovacuum이 실행될 때마다 요약되지 않은 페이지 범위가 모두 요약된다.
이때 테이블 자체가 autovacuum에 의해 처리되는지 여부에 관계없이 이미 채워진 페이지 범위에 대해 요약이 수행된다.

brin_summarize_new_values(regclass): 모든 요약되지 않은 범위를 요약한다.
brin_summarize_range(regclass, bigint): 요약되지 않은 경우 주어진 페이지를 포함하는 범위만 요약한다.

이러한 함수를 사용할 수도 있다.

자동 요약이 활성화된 경우, 다음 블록 범위의 첫 번째 페이지의 첫 번째 항목에 대한 삽입이 감지되면 해당 블록 범위에 대한 대상 요약을 실행하기 위해 autovacuum에 요청이 전송된다.
이 요청은 동일한 데이터베이스에서 autovacuum 작업자가 다음 실행을 완료할 때 다음번에 수행된다.
요청 큐가 가득 찬 경우 요청이 기록되지 않고 서버 로그에 LOG: request for BRIN range summarization for index "brin_wi_idx" page 128 was not recorded 메시지가 전송된다.

이 경우, 해당 범위는 테이블의 다음 정기 vacuum 실행 또는 위에서 언급한 함수 중 하나가 호출될 때까지 요약되지 않은 상태로 유지된다.

반대로, 색인 튜플이 더 이상 매우 좋은 표현이 아닌 경우에 유용한 brin_desummarize_range(regclass, bigint) 함수를 사용하여 범위를 요약 해제할 수 있다.

minmax 연산자 클래스는 범위 내에서 인덱싱된 열에 나타나는 최솟값과 최댓값을 저장한다.
inclusion 연산자 클래스는 범위 내의 인덱싱된 열의 값을 포함하는 값을 저장한다.
bloom 연산자 클래스는 범위 내의 모든 값에 대한 블룸 필터를 생성한다.
minmax-multi 연산자 클래스는 범위 내에서 나타나는 값을 나타내는 다중 최솟값과 최댓값을 저장한다.

일부 내장 연산자 클래스에서는 연산자 클래스의 동작에 영향을 미치는 매개변수를 지정할 수 있다.
각 연산자 클래스에는 허용되는 매개변수 집합이 있다.
블룸 및 minmax-multi 연산자 클래스만 매개변수를 지정할 수 있다.

BRIN 인터페이스는 데이터 유형의 의미를 구현하는 것만을 요구하는 고수준의 추상화를 갖고 있다.
BRIN 레이어 자체가 동시성, 로깅 및 인덱스 구조의 검색을 처리한다.

BRIN 액세스 방법을 작동시키려면 몇 가지 사용자 정의 메서드를 구현하면 되는데, 이 메서드는 인덱스에 저장된 요약 값의 동작과 스캔 키와의 상호 작용 방법을 정의한다.

---

현재 업무에서 사용할 수 있는 인덱스 타입은 B-Tree 혹은 BRIN이다.
두 개의 인덱스 타입에서 어떤 것이 더 유용한지 테스트하여 비교해보려고 한다.