GiST 인덱스

GiST 인덱스 (GiST Indexes)

"이미지 중에서 말 사진만 찾아줘" 같은 도메인 특화 검색을 인덱스로 구현하고 싶다면? 일반 B-트리는 =, <, > 같은 범위 검색만 되잖아요. 그럴 때 B-트리, R-트리는 물론 훨씬 복잡한 인덱스 스킴까지 만들어낼 수 있는 템플릿이 바로 GiST예요. Generalized Search Tree, 함께 살펴볼게요.

출처: PostgreSQL 공식 문서 — gist

소개 (Introduction)

GiST는 Generalized Search Tree(일반화된 검색 트리)의 약자예요. 균형 잡힌(balanced) 트리 구조의 접근 메서드로, 임의의 인덱싱 스킴을 구현할 수 있는 기본 템플릿(base template) 역할을 해요. B-트리, R-트리와 그 밖의 많은 인덱싱 스킴을 GiST로 구현할 수 있어요.

GiST의 큰 장점 중 하나는, 데이터베이스 전문가가 아니라 해당 데이터 타입의 도메인 전문가가 적절한 접근 메서드를 가진 커스텀 데이터 타입을 개발할 수 있게 해준다는 점이에요.

여기 있는 정보 중 일부는 UC Berkeley의 GiST Indexing Project 웹사이트와 Marcel Kornacker의 논문 《Access Methods for Next-Generation Database Systems》에서 파생됐어요. PostgreSQL의 GiST 구현은 주로 Teodor Sigaev와 Oleg Bartunov가 관리하고 있어요.

내장 연산자 클래스 (Built-in Operator Classes)

PostgreSQL 코어 배포판에는 아래 표의 GiST 연산자 클래스가 포함돼 있어요. (Appendix F에 설명된 일부 선택 모듈이 추가 GiST 연산자 클래스를 제공하기도 해요.)

Table 65.1. 내장 GiST 연산자 클래스 (Built-in GiST Operator Classes)

Name	Indexable Operators	Ordering Operators
`box_ops`	`<<`, `&<`, `&&`, `&>`, `>>`, `~=`, `@>`, `<@`, `&<	`,` <<
`circle_ops`	`<<`, `&<`, `&>`, `>>`, `<@`, `@>`, `~=`, `&&`, `\|>>`, `<<	`,` &<
`inet_ops`	`<<`, `<<=`, `>>`, `>>=`, `=`, `<>`, `<`, `<=`, `>`, `>=`, `&&` (모두 `(inet,inet)`)
`multirange_ops`	`=`, `&&`, `@>`, `<@`, `<<`, `>>`, `&<`, `&>`, `-\|-` (anymultirange/anyrange 조합)
`point_ops`	`\|>>`, `<<`, `>>`, `<<	`,` ~=`,` <@` (point/polygon/circle 등)
`poly_ops`	`<<`, `&<`, `&>`, `>>`, `<@`, `@>`, `~=`, `&&`, `<<	`,` &<
`range_ops`	`=`, `&&`, `@>`, `<@`, `<<`, `>>`, `&<`, `&>`, `-\|-` (anyrange/anymultirange 조합)
`tsquery_ops`	`<@ (tsquery, tsquery)`, `@> (tsquery, tsquery)`
`tsvector_ops`	`@@ (tsvector, tsquery)`

역사적인 이유로 inet_ops 연산자 클래스는 inet와 cidr 타입의 기본 클래스가 아니에요. 사용하려면 CREATE INDEX에서 클래스 이름을 명시해야 해요. 예:

CREATE INDEX ON my_table USING GIST (my_inet_column inet_ops);

확장성 (Extensibility)

전통적으로 새로운 인덱스 접근 메서드를 구현하는 건 아주 어려운 작업이었어요. 락 매니저(lock manager)와 Write-Ahead Log 같은 데이터베이스 내부 동작을 이해해야 했거든요. 하지만 GiST 인터페이스는 추상화 수준이 아주 높아요. 접근 메서드 구현자는 접근 대상 데이터 타입의 의미(semantics)만 구현하면 되고, 동시성(concurrency)·로깅(logging)·트리 구조 검색은 GiST 레이어가 알아서 처리해요.

확장성의 의미 (What this extensibility means)

이 확장성을 다른 표준 검색 트리의 "다룰 수 있는 데이터" 측면 확장성과 혼동하면 안 돼요.

PostgreSQL은 확장 가능한 B-트리와 해시 인덱스를 지원해요. 즉 어떤 데이터 타입이든 B-트리나 해시를 만들 수 있죠.
하지만 B-트리는 범위 조건(<, =, >)만, 해시 인덱스는 동등(equality) 쿼리만 지원해요.

예를 들어 이미지 컬렉션을 PostgreSQL B-트리로 인덱스했다면 "이미지x가 이미지y와 같은가", "작은가", "큰가" 같은 질문밖에 못 해요. 하지만 GiST 기반 인덱스를 쓰면 도메인 특화 질문을 만들 수 있어요. "말 사진을 모두 찾아줘", "과다 노출된 이미지를 모두 찾아줘" 같은 것들요.

필요한 메서드 (Required and optional methods)

GiST 접근 메서드를 동작시키려면 사용자 정의 메서드를 여러 개 구현해야 해요. 이 메서드들은 트리에서 key의 동작을 정의해요.

반드시 제공해야 하는 메서드 5개: same, consistent, union (정확성), penalty, picksplit (효율성: 크기와 속도)
선택 메서드 7개: compress, decompress, distance, fetch, options, sortsupport, translate_cmptype(일명 stratnum)
- compress/decompress — 인덱스 내부 트리 데이터가 인덱스하는 데이터와 다른 타입이 되도록 허용해요. 리프는 인덱스된 데이터 타입이어야 하고, 다른 트리 노드는 아무 C struct여도 돼요.
- distance — 순서 스캔(nearest-neighbor 검색)을 지원하려면 필요해요.
- fetch — 인덱스 전용 스캔(index-only scan)을 지원하려면 필요해요. compress 메서드를 생략한 경우 제외.
- options — 연산자 클래스가 사용자 지정 매개변수를 가질 때 필요해요.
- sortsupport — GiST 인덱스 구축 속도를 높이는 데 쓰여요.
- translate_cmptype(stratnum) — compare types(src/include/access/cmptype.h)를 연산자 클래스가 쓰는 전략 번호로 변환해요. 시간 제약(temporal constraint) 인덱스의 연산자를 코어 코드가 찾을 수 있게 해줘요.

consistent

인덱스 항목 p와 쿼리 값 q가 주어졌을 때, 이 함수는 인덱스 항목이 쿼리와 "일관(consistent)"되는지, 즉 indexed_column indexable_operator q 술어가 인덱스 항목이 나타내는 어떤 행에 대해서도 참일 수 있는지를 판단해요.

리프 인덱스 항목에서는 인덱스 가능 조건을 테스트하는 것과 동등해요.
내부 트리 노드에서는 그 트리 노드가 나타내는 인덱스의 서브트리를 스캔해야 하는지를 결정해요.

결과가 true일 때는 recheck 플래그를 함께 반환해야 해요. recheck = false면 인덱스가 조건을 정확히 테스트한 것, recheck = true면 행은 후보 매치일 뿐이고 시스템이 실제 행 값에 대해 연산자를 자동 평가해 진짜 매치인지 확인해요. 이 규약 덕분에 GiST는 lossless와 lossy 인덱스 구조를 모두 지원할 수 있어요.

SQL 선언은 다음과 같아야 해요:

CREATE OR REPLACE FUNCTION my_consistent(internal, data_type, smallint, oid, internal)
RETURNS bool
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

C 모듈의 해당 코드는 다음과 같은 골격을 따르면 돼요:

PG_FUNCTION_INFO_V1(my_consistent);

Datum
my_consistent(PG_FUNCTION_ARGS)
{
    GISTENTRY  *entry = (GISTENTRY *) PG_GETARG_POINTER(0);
    data_type  *query = PG_GETARG_DATA_TYPE_P(1);
    StrategyNumber strategy = (StrategyNumber) PG_GETARG_UINT16(2);
    /* Oid subtype = PG_GETARG_OID(3); */
    bool       *recheck = (bool *) PG_GETARG_POINTER(4);
    data_type  *key = DatumGetDataType(entry->key);
    bool        retval;

    /* ... strategy, key, query에 기반해 반환값 결정 ... */

    *recheck = true;        /* 검사가 정확하면 false */

    PG_RETURN_BOOL(retval);
}

여기서 key는 인덱스의 원소, query는 인덱스에서 찾는 값이에요. StrategyNumber 매개변수는 연산자 클래스의 어떤 연산자가 적용되는지 나타내며, CREATE OPERATOR CLASS 명령의 연산자 번호 중 하나와 매치돼요.

union

트리의 정보를 결합하는 메서드예요. 주어진 항목 집합에 대해 그 모든 항목을 대표하는 새 인덱스 항목을 생성해요.

SQL 선언:

CREATE OR REPLACE FUNCTION my_union(internal, internal)
RETURNS storage_type
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

union 함수의 결과는 인덱스의 저장 타입(storage type) 값이어야 해요. 새로 palloc()된 메모리 포인터를 반환해야 하며, 타입 변경이 없어도 입력 값을 그대로 반환하면 안 돼요. 첫 번째 internal 인자는 실제로 GistEntryVector 포인터예요.

compress

데이터 항목을 인덱스 페이지에 물리적으로 저장하기 적합한 형식으로 변환해요. compress 메서드를 생략하면 데이터 항목이 수정 없이 인덱스에 저장돼요.

CREATE OR REPLACE FUNCTION my_compress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

decompress

저장된 표현을 연산자 클래스의 다른 GiST 메서드가 조작할 수 있는 형식으로 변환해요. 생략하면 다른 메서드가 저장 형식에 직접 작업할 수 있다고 가정해요. decompress는 반드시 compress의 역이 되는 건 아니에요. 특히 compress가 lossy면 원본을 정확히 재구성할 수 없죠.

CREATE OR REPLACE FUNCTION my_decompress(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

penalty

새 항목을 트리의 특정 브랜치에 삽입하는 "비용(cost)"을 나타내는 값을 반환해요. 항목은 트리에서 penalty가 가장 작은 경로를 따라 삽입돼요. 반환 값은 non-negative여야 해요. 음수면 0으로 취급돼요. 인덱스 성능에 아주 중요한 함수예요.

CREATE OR REPLACE FUNCTION my_penalty(internal, internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;  -- 어떤 경우 penalty 함수는 strict일 필요가 없음

역사적인 이유로 penalty 함수는 float 결과를 그냥 반환하지 않고, 세 번째 인자가 가리키는 위치에 값을 저장해야 해요. 반환값 자체는 무시되지만, 보통 그 인자의 주소를 돌려주는 게 관례예요.

picksplit

인덱스 페이지 분할이 필요할 때, 페이지의 어떤 항목이 기존 페이지에 남고 어떤 항목이 새 페이지로 이동할지 결정해요. penalty와 마찬가지로 성능에 아주 중요해요. picksplit 함수의 결과는 전달된 v 구조체를 수정해서 전달돼요.

CREATE OR REPLACE FUNCTION my_picksplit(internal, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

same

두 인덱스 항목이 동일하면 true, 아니면 false를 반환해요. 인덱스 성능이 좋으려면 penalty와 picksplit 구현을 잘 설계하는 게 핵심이에요.

CREATE OR REPLACE FUNCTION my_same(storage_type, storage_type, internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

역사적인 이유로 same 함수는 Boolean 결과를 반환하지 않고 세 번째 인자가 가리키는 위치에 플래그를 저장해요.

distance

인덱스 항목 p와 쿼리 값 q가 주어졌을 때 인덱스 항목의 쿼리 값으로부터의 "거리(distance)"를 결정해요. 연산자 클래스에 순서 연산자(ordering operator)가 있으면 반드시 제공해야 해요.

거리를 결정할 때 약간의 근사는 허용돼요. 단 결과가 항목의 실제 거리보다 크면 안 돼요.
내부 트리 노드에서는 어떤 자식 노드까지의 거리보다도 크지 않은 거리를 반환해야 해요.
반환된 거리가 정확하지 않으면 함수는 *recheck를 true로 설정해야 해요.

CREATE OR REPLACE FUNCTION my_distance(internal, data_type, smallint, oid, internal)
RETURNS float8
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

distance 함수의 인자는 consistent 함수의 인자와 동일해요. 거리 함수가 어떤 리프 노드에 대해 *recheck = true를 반환하면, 원래 순서 연산자의 반환 타입은 float8 또는 float4여야 하며, executor가 두 결과를 모두 사용해 정렬하므로 거리 함수 결과 값이 원래 순서 연산자의 결과와 비교 가능해야 해요.

fetch

압축된 인덱스 표현을 원래 데이터 타입으로 변환해 인덱스 전용 스캔(index-only scan)을 지원해요. 반환된 데이터는 원래 인덱스된 값의 정확하고 lossy하지 않은 복사본이어야 해요. compress 메서드가 리프 항목에 대해 lossy라면 연산자 클래스는 인덱스 전용 스캔을 지원할 수 없고, fetch 함수를 정의하면 안 돼요.

CREATE OR REPLACE FUNCTION my_fetch(internal)
RETURNS internal
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

options

연산자 클래스 동작을 제어하는 사용자-가시 매개변수 정의를 허용해요. local_relopts 구조체 포인터를 받아 연산자 클래스별 옵션을 채워 넣어요.

CREATE OR REPLACE FUNCTION my_options(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

GiST에서 key의 표현이 유연하므로 사용자 지정 매개변수에 의존할 수 있어요. 예를 들어 key 서명(signature)의 길이를 지정할 수 있어요. gtsvector_options()를 예로 들 수 있어요.

sortsupport

지역성(locality)을 보존하는 방식으로 데이터를 정렬하는 비교자(comparator) 함수를 반환해요. CREATE INDEX와 REINDEX 명령에서 사용돼요. 이 메서드는 선택적이에요. 제공하지 않으면 CREATE INDEX가 penalty와 picksplit 함수를 사용해 각 튜플을 트리에 삽입하는 방식으로 인덱스를 구축하는데, 훨씬 느려요.

CREATE OR REPLACE FUNCTION my_sortsupport(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;

인자는 SortSupport 구조체 포인터예요. 최소한 비교자(comparator) 필드를 채워야 해요.

translate_cmptype (stratnum)

src/include/access/cmptype.h의 CompareType 값이 주어지면 이 연산자 클래스가 기능 매칭에 사용하는 전략 번호를 반환해요. 연산자 클래스에 매칭 전략이 없으면 InvalidStrategy를 반환해야 해요. 시간 제약 인덱스 제약(PRIMARY KEY, UNIQUE)에 사용돼요. 이 지원 함수는 인덱스 접근 메서드 콜백 함수 amtranslatecmptype에 대응해요.

PostgreSQL이 제공하는 번역 함수가 두 개 있어요.

gist_translate_cmptype_common — RT*StrategyNumber 상수를 쓰는 연산자 클래스용.
gist_translate_cmptype_btree — btree_gist 확장이 정의하며, BT*StrategyNumber 상수를 쓰는 연산자 클래스용.

메모리 컨텍스트 참고 (Memory context note)

모든 GiST 지원 메서드는 보통 단기(short-lived) 메모리 컨텍스트에서 호출돼요. 즉 CurrentMemoryContext는 각 튜플을 처리한 뒤 리셋돼요. 그래서 palloc한 모든 것을 pfree하는 데 크게 신경 쓸 필요는 없어요. 다만 반복 호출 간에 데이터를 캐시하고 싶다면 수명이 긴 데이터를 fcinfo->flinfo->fn_mcxt에 할당하고 fcinfo->flinfo->fn_extra에 포인터를 보관하면 돼요. 이 데이터는 인덱스 연산(단일 GiST 인덱스 스캔, 인덱스 구축, 인덱스 튜플 삽입 등) 동안 살아있어요. fn_extra 값을 교체할 때는 이전 값을 pfree해서 누수를 막아야 해요.

구현 (Implementation)

GiST 인덱스 구축 메서드 (GiST Index Build Methods)

GiST 인덱스를 구축하는 가장 간단한 방법은 모든 항목을 하나씩 삽입하는 거예요. 하지만 큰 인덱스에서는 느려질 수 있어요. 인덱스 튜플이 인덱스에 흩어져 있고 인덱스가 캐시에 안 들어갈 만큼 크다면 많은 랜덤 I/O가 필요하거든요. PostgreSQL은 초기 GiST 인덱스 구축을 위한 두 가지 대체 메서드를 지원해요: sorted(정렬) 와 buffered(버퍼링) 모드예요.

sorted 메서드 — 인덱스가 사용하는 각 opclass가 sortsupport 함수를 제공할 때만 사용할 수 있어요. 제공하면 보통 이 메서드가 가장 좋아서 기본값으로 사용돼요.
buffered 메서드 — 튜플을 곧바로 인덱스에 삽입하지 않는 방식이에요. 정렬되지 않은 데이터 집합에 필요한 랜덤 I/O를 크게 줄일 수 있어요. 다만 penalty 함수를 더 자주 호출해 CPU 자원을 더 소모하고, 결과 인덱스 크기만큼의 임시 디스크 공간이 필요해요. 버퍼링은 결과 인덱스 품질에도 양/음 방향으로 영향을 줄 수 있어요.

정렬이 불가능하면 기본적으로 GiST 인덱스 구축은 인덱스 크기가 effective_cache_size에 도달할 때 버퍼링 메서드로 전환해요. 버퍼링은 CREATE INDEX 명령의 buffering 매개변수로 강제하거나 막을 수 있어요. 기본 동작이 대부분의 경우 좋지만, 입력 데이터가 정렬돼 있다면 버퍼링을 끄면 구축이 다소 빨라질 수 있어요.

예제 (Examples)

PostgreSQL 소스 배포판에는 GiST를 사용해 구현된 몇 가지 인덱스 메서드 예제가 포함돼 있어요.

코어 시스템은 현재 텍스트 검색 지원(tsvector, tsquery 인덱싱)과 일부 내장 기하 데이터 타입을 위한 R-Tree 동등 기능을 제공해요. (src/backend/access/gist/gistproc.c 참고)

다음 contrib 모듈들도 GiST 연산자 클래스를 포함해요.

모듈	설명
`btree_gist`	여러 데이터 타입에 대한 B-트리 동등 기능
`cube`	다차원 큐브(cubes) 인덱싱
`hstore`	(key, value) 쌍 저장 모듈
`intarray`	int4 값 1차원 배열에 대한 RD-Tree
`ltree`	트리형 구조 인덱싱
`pg_trgm`	trigram 매칭을 사용한 텍스트 유사도
`seg`	"float ranges" 인덱싱