GIN 인덱스

GIN 인덱스 (GIN Indexes)

문서 중에 특정 단어가 들어있는지를 빠르게 찾아야 한다면? 배열 안에 특정 원소가 있는지, JSONB 안에 특정 키가 있는지 검색해야 한다면? 그런 "안에 포함되어 있는지" 검색에 최적화된 게 바로 GIN 인덱스예요. Generalized Inverted Index라고 불리는 이 인덱스가 어떻게 동작하고 어떻게 확장하는지 같이 살펴볼게요.

출처: PostgreSQL 공식 문서 — gin

소개 (Introduction)

GIN은 Generalized Inverted Index(일반화된 역인덱스)의 약자예요. GIN은 "인덱싱할 대상(item)이 복합값(composite value)이고, 그 안에 포함된 원소(element) 값을 검색해야 하는 경우"를 처리하도록 설계됐어요.

예를 들어 이렇게 생각해 볼까요.

item(항목) — 인덱싱할 복합값을 말해요. 예를 들면 문서(document) 자체가 되죠.
key(키) — 원소. 예를 들어 검색 대상이 되는 특정 단어를 말해요.

즉, "특정 단어를 포함하는 문서를 찾아라" 같은 검색이 바로 GIN이 잘하는 일이에요. GIN은 항상 item 값 자체가 아니라 key를 저장하고 검색해요.

GIN의 저장 방식 (How GIN stores data)

GIN 인덱스는 (key, posting list) 쌍들의 집합을 저장해요.

posting list — 해당 key가 등장하는 행 ID(row ID)들의 집합이에요.
같은 행 ID가 여러 posting list에 나타날 수 있어요. item 하나가 여러 key를 포함할 수 있으니까요.
각 key 값은 한 번만 저장돼요. 그래서 같은 key가 여러 번 나타나는 경우 GIN 인덱스는 아주 컴팩트(compact)해요.

GIN이 "일반화"되었다는 의미 (What "Generalized" means)

GIN은 접근 메서드(access method) 코드가 자신이 가속화하는 구체적인 연산을 알 필요가 없어요. 대신 특정 데이터 타입을 위해 정의된 커스텀 전략(custom strategies) 을 사용해요.

전략은 인덱싱할 item과 쿼리 조건에서 key를 어떻게 추출할지,
그리고 쿼리 key 값 중 일부를 포함하는 행이 실제로 쿼리를 만족하는지 어떻게 판단할지

를 정의해요.

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

PostgreSQL에서 GIN 구현은 주로 Teodor Sigaev와 Oleg Bartunov가 관리하고 있어요. GIN에 대한 더 자세한 정보는 그들의 웹사이트에서 확인할 수 있어요.

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

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

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

Name	Indexable Operators
`array_ops`	`&& (anyarray,anyarray)`, `@> (anyarray,anyarray)`, `<@ (anyarray,anyarray)`, `= (anyarray,anyarray)`
`jsonb_ops`	`@> (jsonb,jsonb)`, `@? (jsonb,jsonpath)`, `@@ (jsonb,jsonpath)`, `? (jsonb,text)`, `?
`jsonb_path_ops`	`@> (jsonb,jsonb)`, `@? (jsonb,jsonpath)`, `@@ (jsonb,jsonpath)`
`tsvector_ops`	`@@ (tsvector,tsquery)`

jsonb 타입의 두 연산자 클래스 중 jsonb_ops가 기본(default) 이에요. jsonb_path_ops는 지원하는 연산자가 더 적지만, 그 연산자들에 대해서는 더 나은 성능을 제공해요. 자세한 내용은 Section 8.14.4를 확인하세요.

확장성 (Extensibility)

GIN 인터페이스는 추상화 수준이 아주 높아요. 접근 메서드 구현자는 접근 대상 데이터 타입의 의미(semantics)만 구현하면 되고, 동시성(concurrency)·로깅(logging)·트리 구조 검색은 GIN 레이어가 알아서 처리해요.

GIN 접근 메서드를 동작하게 하려면 몇 개의 사용자 정의 메서드(user-defined method)만 구현하면 돼요. 이 메서드들은 트리 안에서 key의 동작과 key·indexed item·indexable query 사이의 관계를 정의해요. 요약하면 GIN은 확장성 + 일반성 + 코드 재사용 + 깔끔한 인터페이스를 결합한 구조예요.

GIN 연산자 클래스가 반드시 제공해야 하는 메서드 (Required methods)

GIN 연산자 클래스가 반드시 제공해야 하는 메서드는 두 가지예요.

Datum *extractValue(Datum itemValue, int32 *nkeys, bool **nullFlags) 인덱싱할 item이 주어지면 key 배열을 반환해요. 반환된 key의 개수는 *nkeys에 저장해야 해요. key 중 null이 될 수 있다면 *nkeys 크기의 bool 배열을 palloc해서 주소를 *nullFlags에 저장하고 필요에 따라 null 플래그를 설정해요. 모든 key가 non-null이면 *nullFlags는 초기값 NULL로 남겨두면 돼요. item에 key가 없으면 반환값은 NULL일 수 있어요.
Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data, bool **nullFlags, int32 *searchMode) 쿼리할 값이 주어지면 key 배열을 반환해요. 여기서 query는 인덱스된 컬럼을 왼쪽 변으로 하는 indexable 연산자의 오른쪽 변 값이에요. n은 연산자 클래스 내 연산자의 전략 번호(strategy number)예요. 종종 extractQuery는 n을 참고해서 query의 데이터 타입과 key 값을 추출할 메서드를 결정해요.

searchMode는 검색이 어떻게 수행될지 지정하는 출력 인자예요.

GIN_SEARCH_MODE_DEFAULT (호출 전 초기값) — 반환된 key 중 최소 하나와 일치하는 item만 후보로 간주해요.
GIN_SEARCH_MODE_INCLUDE_EMPTY — key를 하나도 포함하지 않는 item도 후보에 포함해요. (예: is-subset-of 연산자 구현에 유용해요.)
GIN_SEARCH_MODE_ALL — 반환된 key와 일치 여부와 무관하게 인덱스의 모든 non-null item을 후보로 간주해요. (인덱스 전체를 스캔해야 하므로 훨씬 느려요.)

pmatch는 부분 일치(partial match) 지원 시 사용하는 출력 인자예요. extractQuery가 *nkeys 크기의 bool 배열을 할당해 *pmatch에 주소를 저장해요. 부분 일치가 필요하면 true, 아니면 false로 설정해요. *pmatch가 NULL이면 GIN은 부분 일치가 필요 없다고 가정해요.

extra_data는 extractQuery가 consistent와 comparePartial 메서드에 추가 데이터를 전달할 수 있게 해주는 출력 인자예요. *nkeys 크기의 포인터 배열을 할당해 *extra_data에 저장하면 돼요. *extra_data가 설정되면 전체 배열이 consistent 메서드에 전달되고, 적절한 원소가 comparePartial 메서드에 전달돼요.

연산자 클래스는 인덱스된 item이 쿼리를 만족하는지 확인하는 함수도 제공해야 해요. 두 가지 형태가 있는데, Boolean consistent 함수와 삼항(ternary) triConsistent 함수예요. triConsistent가 둘 다의 기능을 포함하므로 triConsistent만 제공해도 충분해요. 다만 Boolean 변형이 훨씬 저렴하다면 둘 다 제공하는 게 유리할 수 있어요.

bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], bool *recheck, Datum queryKeys[], bool nullFlags[]) 전략 번호 n을 가진 쿼리 연산자를 인덱스된 item이 만족하는지 true를 반환해요. 이 함수는 인덱스된 item의 값에 직접 접근하지 못해요. GIN은 item을 명시적으로 저장하지 않으니까요. 대신 쿼리에서 추출된 key 값 중 어느 것이 주어진 인덱스된 item에 나타나는지에 대한 정보만 있어요. check 배열의 각 원소는 인덱스된 item이 해당 쿼리 key를 포함하면 true예요.

성공 시 *recheck는 힙 튜플(heap tuple)을 쿼리 연산자로 재검사해야 하면 true, 인덱스 테스트가 정확하면 false로 설정해야 해요.
GinTernaryValue triConsistent(GinTernaryValue check[], StrategyNumber n, Datum query, int32 nkeys, Pointer extra_data[], Datum queryKeys[], bool nullFlags[]) consistent와 비슷하지만 check 벡터에 Boolean 대신 GIN_TRUE, GIN_FALSE, GIN_MAYBE 세 가지 값이 있어요. GIN_MAYBE는 해당 key의 존재 여부가 알려지지 않았다는 뜻이에요. GIN_MAYBE가 있을 때는 item이 확실히 매치하면 GIN_TRUE를, 확실히 매치하지 않으면 GIN_FALSE를 반환해야 해요. 결과가 GIN_MAYBE 항목에 의존한다면 GIN_MAYBE를 반환해야 해요.

또한 GIN은 인덱스에 저장된 key 값을 정렬하는 방법이 필요해요. 연산자 클래스는 비교 메서드를 지정해 정렬 순서를 정의할 수 있어요.

int compare(Datum a, Datum b) 두 key(인덱스된 item이 아니라!)를 비교해 첫 번째가 두 번째보다 작으면 0보다 작은 정수, 같으면 0, 크면 0보다 큰 정수를 반환해요. null key는 이 함수에 절대 전달되지 않아요.

만약 연산자 클래스가 compare 메서드를 제공하지 않으면, GIN은 인덱스 key 데이터 타입의 기본 btree 연산자 클래스를 찾아 그 비교 함수를 사용해요.

GIN 연산자 클래스는 다음 메서드를 선택적으로 제공할 수 있어요.

int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer extra_data) 부분 일치 쿼리 key를 인덱스 key와 비교해요. 0보다 작으면 매치되지 않지만 인덱스 스캔을 계속해야 함, 0이면 매치, 0보다 크면 더 이상 매치가 없으니 스캔을 멈춰야 함을 나타내요.
void options(local_relopts *relopts) 연산자 클래스 동작을 제어하는 사용자-가시 매개변수 집합을 정의해요. local_relopts 구조체 포인터를 받아 연산자 클래스별 옵션을 채워 넣어요. 옵션은 PG_HAS_OPCLASS_OPTIONS()와 PG_GET_OPCLASS_OPTIONS() 매크로로 다른 지원 함수에서 접근할 수 있어요.

"부분 일치(partial match)" 쿼리를 지원하려면 연산자 클래스가 comparePartial 메서드를 제공해야 하고, extractQuery 메서드가 부분 일치 쿼리를 만났을 때 pmatch 매개변수를 설정해야 해요.

구현 (Implementation)

내부적으로 GIN 인덱스는 key 위에 구축된 B-트리 인덱스예요. 각 key는 하나 이상의 인덱스된 item의 원소(예: 배열의 멤버)예요. 리프 페이지의 각 튜플은 힙 포인터의 B-트리(posting tree)에 대한 포인터를 포함하거나, 리스트가 key 값과 함께 단일 인덱스 튜플에 들어갈 만큼 작으면 간단한 힙 포인터 리스트(posting list)를 포함해요.

PostgreSQL 9.1부터 null key 값을 인덱스에 포함할 수 있어요.
또한 extractValue에 따라 null이거나 key가 없는 인덱스된 item을 위해 플레이스홀더 null이 인덱스에 포함돼요. 그래서 빈 item을 찾는 검색이 가능해져요.
멀티컬럼 GIN 인덱스는 복합값(컬럼 번호, key 값) 위에 단일 B-트리를 구축해 구현돼요. 서로 다른 컬럼의 key 값은 서로 다른 타입일 수 있어요.

GIN 신속 업데이트 기법 (GIN Fast Update Technique)

GIN 인덱스 업데이트는 역인덱스의 본질 때문에 느려지기 쉬워요. 힙 행 하나를 삽입·업데이트하면 인덱스에 많은 삽입이 일어날 수 있거든요(key 하나마다 하나씩). GIN은 이 작업의 상당 부분을 연기할 수 있어요. 새 튜플을 임시의 정렬되지 않은 pending entries 리스트에 넣는 방식이에요.

테이블이 vacuum이나 autoanalyze될 때,
gin_clean_pending_list 함수가 호출될 때,
또는 pending 리스트가 gin_pending_list_limit보다 커질 때,

항목들은 초기 인덱스 생성 때 쓰는 것과 동일한 대량 삽입 기법을 사용해 메인 GIN 데이터 구조로 옮겨져요. 이 방식은 GIN 인덱스 업데이트 속도를 크게 개선해요.

이 방식의 단점은 검색이 일반 인덱스에 더해 pending entries 리스트도 스캔해야 한다는 거예요. 그래서 pending 리스트가 크면 검색이 크게 느려질 수 있어요. 또 대부분의 업데이트는 빠르지만, pending 리스트가 "너무 커지게" 만드는 업데이트는 즉시 정리 사이클이 발생해서 훨씬 느려질 수 있어요. autovacuum을 적절히 쓰면 두 문제를 모두 완화할 수 있어요.

일관된 응답 시간이 업데이트 속도보다 더 중요하다면, GIN 인덱스의 fastupdate 저장 매개변수를 끄면 pending entries 사용을 비활성화할 수 있어요. 자세한 내용은 CREATE INDEX 문서를 확인하세요.

부분 일치 알고리즘 (Partial Match Algorithm)

GIN은 "부분 일치(partial match)" 쿼리를 지원해요. 이 경우 쿼리는 하나 이상의 key에 대해 정확한 매치를 결정하지 못하지만, 가능한 매치는 key 값의 비교적 좁은 범위 안에 들어와요(compare 지원 메서드가 결정한 key 정렬 순서 기준). extractQuery 메서드는 정확히 매치할 key 값을 반환하는 대신, 검색할 범위의 하한(lower bound)이 되는 key 값을 반환하고 pmatch 플래그를 true로 설정해요. 그러면 key 범위가 comparePartial 메서드로 스캔돼요.

GIN 팁과 트릭 (GIN Tips and Tricks)

Create vs. insert (생성 vs. 삽입) — GIN 인덱스에 삽입하는 것은 item마다 key가 많이 삽입될 가능성이 있어 느릴 수 있어요. 그래서 테이블에 대량 삽입을 할 때는 GIN 인덱스를 드롭하고 대량 삽입이 끝난 뒤 다시 만드는 게 좋아요. fastupdate가 켜져 있으면 불이익이 덜하지만, 아주 큰 업데이트에는 여전히 드롭 후 재생성이 나을 수 있어요.
maintenance_work_mem — GIN 인덱스 구축 시간은 maintenance_work_mem 설정에 아주 민감해요. 인덱스 생성 중에 작업 메모리를 아끼는 건 이득이 없어요.
gin_pending_list_limit — fastupdate가 켜진 기존 GIN 인덱스에 연속 삽입하는 동안, pending 리스트가 gin_pending_list_limit보다 커지면 시스템이 pending-entry 리스트를 정리해요. 응답 시간 변동을 피하려면 pending-list 정리가 백그라운드(즉, autovacuum)에서 일어나는 게 좋아요. gin_pending_list_limit을 늘리거나 autovacuum을 더 공격적으로 만들면 포그라운드 정리를 피할 수 있어요. gin_pending_list_limit은 개별 GIN 인덱스의 저장 매개변수로 오버라이드할 수 있어요.
gin_fuzzy_search_limit — GIN 인덱스를 개발한 주된 목적은 확장성 높은 전문(full-text) 검색 지원이었어요. 그런데 전문 검색이 아주 큰 결과 집합을 반환하는 상황이 자주 있어요. 특히 쿼리에 아주 흔한 단어가 포함되면 큰 결과 집합이 쓸모없어지기도 하죠. 디스크에서 많은 튜플을 읽어 정렬하는 건 시간이 오래 걸려서 프로덕션에는 받아들이기 어려워요. (인덱스 검색 자체는 아주 빠르다는 점을 참고하세요.)

이를 위해 GIN에는 반환되는 행 수에 대한 설정 가능한 소프트 상한(soft upper limit) 이 있어요. 바로 gin_fuzzy_search_limit 구성 매개변수예요. 기본값은 0(제한 없음)이에요. 0이 아닌 값을 설정하면 반환 집합은 전체 결과 집합의 부분 집합이며, 무작위로 선택돼요.

"soft(소프트)"라는 건 실제 반환 결과 수가 지정된 한도와 다소 다를 수 있다는 뜻이에요. 쿼리와 시스템의 난수 생성기 품질에 따라서요. 경험상 수천 단위(예: 5000~20000)가 잘 동작해요.

제한 사항 (Limitations)

GIN은 인덱싱 가능한 연산자가 strict하다고 가정해요. 즉:

null item 값에 대해서는 extractValue가 아예 호출되지 않아요. (대신 플레이스홀더 인덱스 항목이 자동 생성돼요.)
null query 값에 대해서는 extractQuery가 호출되지 않아요. (대신 쿼리가 만족 불가능하다고 간주돼요.)

다만 non-null 복합 item/query 값 안에 포함된 null key 값은 지원돼요.

예제 (Examples)

PostgreSQL 코어 배포판에는 앞서 Table 65.3에서 본 GIN 연산자 클래스가 포함돼 있어요. 다음 contrib 모듈들도 GIN 연산자 클래스를 포함해요.

모듈	설명
`btree_gin`	여러 데이터 타입에 대한 B-트리 동등 기능
`hstore`	(key, value) 쌍 저장 모듈
`intarray`	`int[]`에 대한 향상된 지원
`pg_trgm`	trigram 매칭을 사용한 텍스트 유사도