[PostgreSQL] 인덱스: Gist

Gist는 PostgreSQL의 주요 인덱스 타입 중 하나다.

이건 기본 primitive 타입시스템의 인덱스로는 잘 쓰이지 않고, 추가 확장 플러그인에서 일부 특수한 형태의 쿼리에 대해서 지원이 되는 편이다. 특히 공간 좌표에서의 거리나 인접성 검사 등에 응용된다.

Gist가 사용되는 대표적인 확장으로는 PostGIS가 있다.
그리고 기본 타입 중에서 Gist가 지원되는 것으로는 Range, Point 정도가 있다.

기본 원리

Gist는 Generalized Search Tree의 축약이다.
내부 구현상으로는 일반화된 B-Tree지만 R-Tree의 개념에 가깝다.

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

조금 헷갈릴 수 있는데, Gist는 BTree와 다르게 기본 타입들에 대한 operator 구현체가 없다. PostgreSQL은 인터페이스만을 제공하고 실제 타입별 동작이나 의미론은 각 서드파티 플러그인의 operator class가 구현한다.

아무튼 기본 원리는 이것도 Tree이긴 하고, 물리 구현상으로 B-Tree와 크게 다르진 않다.
다만 값들끼리의 유사도를 직접 커스텀할 수 있다는 것이 다를 뿐이다. 다시 말해서, "서울"이라는 값과 "인천"이라는 값이 "도쿄"보다 가까운지를 플러그인 구현자 입장에서 직접 정의할 수 있다는 것이다.

그리고 B-Tree와의 가장 큰 차이점은 값끼리 "겹칠 수 있다."는 것이다.
그래서 트리 탐색에 들어갈 때도 결정적으로 동작하지 않는다. BTree는 서브트리를 탈때 딱 하나씩 선택해서 들어가지만, Gist는 여러개의 서브트리를 타고 들어갈 수 있다.

Gist의 이점과 한계

Gist는 특유의 구조 탓에 잠재적인 성능 병목 지점이 존재한다. 탐색 과정에서 subtree를 너무 많이 타고 들어가면 fanout이 폭증할 수 있기 때문이다.
그래서 탐색 중에 관계없는 subtree를 많이 버릴 수 있는지(pruning)가 실제 속도를 좌우하는데, 일반적인 공간 좌표 데이터들은 이러한 데이터 패턴에 잘 맞는다. "서울"과 "부산"처럼 공간이 꽤 명확하게 분리되고, 막 엄청나게 겹칠 일도 적기 때문이다.

근데 이게 차원 수가 낮은 데이터에는 효율적으로 잘 동작하지만, 차원 수가 높아지는 경우에는 적합하지 않다.
특히 "벡터" 처럼 차원수가 수천 단위로 깊어지고 개별 값과의 겹침 정도가 사방팔방으로 퍼지는 경우에는 subtree pruning이 매우 드물게 일어나므로 문제가 많다.
그래서 pgvector 같은 경우에는 Gist를 쓰지 않고 HNSW 같은 커스텀 구현체를 사용한다.

Gist의 사용법

인덱스를 만드는 것 자체는 그다지 복잡하거나 어려울 것은 없다. gist가 지원되는 타입의 컬럼에 gist 옵션만 넘겨서 만들면 된다.

CREATE INDEX 인덱스명 ON 테이블명 USING gist (컬럼);

Gist가 지원되는 타입 중에 가장 테스트가 간단한 것은 Range 타입이다. 별도 포스트를 참조한다.
https://blog.naver.com/sssang97/224134278317

아무튼 Gist 인덱싱을 태우기 위해서는 적절한 연산자를 사용해야만 한다.
주로 사용되는 연산 패턴은 다음과 같다.

1. 겹침(overlap)
2. 포함(contain)
3. 거리(distance)

overlap 연산자로는 &&가 가장 대표적인데, 이건 2개의 값이 겹친다는 것을 의미한다.
Range에서는 2개의 범위가 겹치는 부분이 있는지를 체크하고, PostGIS에서는 공간끼리 겹치는지를 검사한다.

@> 연산자는 포함관계를 정의한다. A @> B면 A가 B를 포함한다는 것이다.

<-> 연산자는 거리를 정의한다. 이건 양변 값의 거리를 반환한다. 특히 정렬조건으로 사용하기 용이하다.

참조
https://www.postgresql.org/docs/current/gist.html
https://postgrespro.com/blog/pgsql/4175817