SP-GiST 인덱스
SP-GiST 인덱스 (SP-GiST Indexes)
검색 트리 노드를 디스크 페이지에 "어떻게" 매핑할지, 그래서 검색이 많은 노드를 거치면서도 디스크 페이지는 몇 개만 건드리게 할지 — 이 고민을 푸는 게 SP-GiST예요. 쿼드 트리(quad-tree), k-d 트리, radix 트리(trie) 같은 비균형 데이터 구조를 PostgreSQL에서 쓸 수 있게 해주는 인덱스 접근 방식이에요.
소개 (Introduction)
SP-GiST는 space-partitioned GiST의 약자예요. SP-GiST는 분할 검색 트리(partitioned search trees)를 지원해서, 쿼드 트리, k-d 트리, radix 트리(trie) 같은 다양한 비균형(non-balanced) 데이터 구조를 개발하기 쉽게 해줘요. 이 구조들의 공통점은 검색 공간을 같은 크기가 아닐 수 있는 구획(partition) 으로 반복해서 나눈다는 거예요. 분할 규칙에 잘 맞는 검색은 매우 빨라질 수 있죠.
이런 인기 있는 데이터 구조들은 원래 메모리 내 사용을 위해 개발됐어요. 주 메모리에서는 보통 포인터로 연결된 동적으로 할당된 노드 집합으로 설계되죠. 그런데 이건 디스크에 직접 저장하기엔 부적합해요. 포인터 체인이 꽤 길어질 수 있어서 디스크 접근이 너무 많이 필요해지거든요. 반대로 디스크 기반 데이터 구조는 I/O를 최소화하려면 높은 fanout(분기율) 을 가져야 해요. SP-GiST가 해결하려는 과제는, 검색이 많은 노드를 거치더라도 디스크 페이지를 몇 개만 접근하도록 검색 트리 노드를 디스크 페이지에 매핑하는 거예요.
GiST처럼 SP-GiST도 데이터 타입 분야의 전문가(데이터베이스 전문가가 아니라)가 적절한 접근 방식과 함께 커스텀 데이터 타입을 개발할 수 있게 해주는 걸 목표로 해요.
여기 있는 정보 중 일부는 Purdue University의 SP-GiST Indexing Project 웹사이트에서 파생됐어요. PostgreSQL의 SP-GiST 구현은 주로 Teodor Sigaev와 Oleg Bartunov가 유지보수하고 있고, 그들의 웹사이트에서 더 많은 정보를 볼 수 있어요.
내장 연산자 클래스 (Built-in Operator Classes)
PostgreSQL 핵심 배포판에는 Table 65.2에 보이는 SP-GiST 연산자 클래스(operator classes)가 포함돼 있어요.
Table 65.2. 내장 SP-GiST 연산자 클래스 (Built-in SP-GiST Operator Classes)
| Name | Indexable Operators | Ordering Operators |
|---|---|---|
box_ops |
<< (box,box), &< (box,box), &> (box,box), >> (box,box), <@ (box,box), @> (box,box), ~= (box,box), && (box,box), <<| (box,box), &<| (box,box), |&> (box,box), |>> (box,box) |
<-> (box,point) |
inet_ops |
<< (inet,inet), <<= (inet,inet), >> (inet,inet), >>= (inet,inet), = (inet,inet), <> (inet,inet), < (inet,inet), <= (inet,inet), > (inet,inet), >= (inet,inet), && (inet,inet) |
(없음) |
kd_point_ops |
|>> (point,point), << (point,point), >> (point,point), <<| (point,point), ~= (point,point), <@ (point,box) |
<-> (point,point) |
poly_ops |
<< (polygon,polygon), &< (polygon,polygon), &> (polygon,polygon), >> (polygon,polygon), <@ (polygon,polygon), @> (polygon,polygon), ~= (polygon,polygon), && (polygon,polygon), <<| (polygon,polygon), &<| (polygon,polygon), |>> (polygon,polygon), |&> (polygon,polygon) |
<-> (polygon,point) |
quad_point_ops |
|>> (point,point), << (point,point), >> (point,point), <<| (point,point), ~= (point,point), <@ (point,box) |
<-> (point,point) |
range_ops |
= (anyrange,anyrange), && (anyrange,anyrange), @> (anyrange,anyelement), @> (anyrange,anyrange), <@ (anyrange,anyrange), << (anyrange,anyrange), >> (anyrange,anyrange), &< (anyrange,anyrange), &> (anyrange,anyrange), -|- (anyrange,anyrange) |
(없음) |
text_ops |
= (text,text), < (text,text), <= (text,text), > (text,text), >= (text,text), ~<~ (text,text), ~<=~ (text,text), ~>=~ (text,text), ~>~ (text,text), ^@ (text,text) |
(없음) |
point 타입의 두 연산자 클래스 중 quad_point_ops가 기본값이에요. kd_point_ops는 같은 연산자를 지원하지만 다른 인덱스 데이터 구조를 사용해서, 일부 애플리케이션에서 더 나은 성능을 보여줄 수 있어요.
quad_point_ops, kd_point_ops, poly_ops 연산자 클래스는 <-> 정렬 연산자(orderring operator)를 지원해서, 인덱스된 point 또는 polygon 데이터 집합에 대한 k-최근접 이웃(k-NN) 검색을 가능하게 해줘요.
확장성 (Extensibility)
SP-GiST는 높은 수준의 추상화 인터페이스를 제공해서, 접근 방식 개발자는 특정 데이터 타입에 특화된 메서드만 구현하면 돼요. SP-GiST 핵심이 효율적인 디스크 매핑과 트리 구조 검색을 책임지고, 동시성(concurrency)과 로깅(logging) 처리도 담당해요.
SP-GiST 트리의 리프 튜플(leaf tuple) 은 보통 인덱스된 컬럼과 같은 데이터 타입의 값을 담지만, 인덱스된 컬럼의 손실 표현(lossy representation) 을 담는 것도 가능해요. 루트 수준에 저장된 리프 튜플은 원래 인덱스 데이터 값을 직접 나타내지만, 더 낮은 수준의 리프 튜플은 접미사(suffix) 같은 부분 값만 담을 수 있어요. 그 경우 연산자 클래스 지원 함수는 리프 수준에 도달하기 위해 거쳐온 내부 튜플에서 누적된 정보를 사용해 원래 값을 재구성할 수 있어야 해요.
SP-GiST 인덱스를 INCLUDE 컬럼으로 만들면 그 컬럼들의 값도 리프 튜플에 저장돼요. INCLUDE 컬럼은 SP-GiST 연산자 클래스와는 무관하므로 여기서 더 다루지 않을게요.
내부 튜플(inner tuple) 은 검색 트리의 분기점이라 더 복잡해요. 각 내부 튜플은 하나 이상의 노드(node) 집합을 담는데, 노드는 비슷한 리프 값들의 그룹을 나타내요. 노드는 더 낮은 수준의 내부 튜플이나, 같은 인덱스 페이지에 있는 짧은 리프 튜플 목록으로 이어지는 다운링크(downlink)를 담아요. 각 노드는 보통 그것을 설명하는 레이블(label) 을 가져요. 예를 들어 radix 트리에서 노드 레이블은 문자열 값의 다음 문자일 수 있어요. (대안으로 연산자 클래스는 모든 내부 튜플에 대해 고정된 노드 집합으로 작업한다면 노드 레이블을 생략할 수 있어요. 65.3.4.2절 참고.) 선택적으로 내부 튜플은 모든 멤버를 설명하는 접두사(prefix) 값을 가질 수 있어요. radix 트리에서 이건 표현된 문자열들의 공통 접두사일 수 있어요. 접두사 값은 반드시 진짜 접두사일 필요는 없고, 연산자 클래스가 필요로 하는 어떤 데이터든 될 수 있어요. 예를 들어 쿼드 트리에서는 네 사분면이 측정되는 기준이 되는 중심점을 저장할 수 있죠. 그러면 쿼드 트리 내부 튜플은 이 중심점 주변의 사분면에 해당하는 네 개의 노드도 담게 돼요.
일부 트리 알고리즘은 현재 튜플의 수준(level, 깊이)을 알아야 해서, SP-GiST 핵심은 트리를 내려가면서 연산자 클래스가 수준 계산을 관리할 수 있는 가능성을 제공해요. 필요할 때 표현된 값을 점진적으로 재구성하는 지원과, 트리 하강 중 추가 데이터(traverse values라고 함)를 아래로 전달하는 지원도 있어요.
참고: SP-GiST 핵심 코드가 null 항목을 처리해요. SP-GiST 인덱스는 인덱스된 컬럼의 null에 대한 항목을 저장하긴 하지만, 이는 인덱스 연산자 클래스 코드에는 숨겨져 있어요 — null 인덱스 항목이나 검색 조건이 연산자 클래스 메서드에 전달되지 않아요. (SP-GiST 연산자는 strict(엄격)하고 그래서 null 값으로는 성공할 수 없다고 가정해요.) 따라서 null 값은 여기서 더 다루지 않아요.
SP-GiST용 인덱스 연산자 클래스가 제공해야 하는 사용자 정의 메서드는 5개가 필수이고 2개는 선택이에요. 필수 5개 모두 두 개의 internal 인자를 받는 관례를 따르는데, 첫 번째는 지원 메서드의 입력 값을 담은 C 구조체를 가리키는 포인터이고, 두 번째는 출력 값을 놓아야 하는 C 구조체를 가리키는 포인터예요. 필수 메서드 중 4개는 결과가 모두 출력 구조체에 나타나므로 그냥 void를 반환하지만, leaf_consistent는 boolean 결과를 반환해요. 메서드는 입력 구조체의 어떤 필드도 수정해서는 안 돼요. 모든 경우 출력 구조체는 사용자 정의 메서드를 호출하기 전에 0으로 초기화돼요. 선택적인 여섯 번째 메서드 compress는 인덱스할 datum을 유일한 인자로 받아 리프 튜플에 물리적으로 저장하기 적합한 값을 반환해요. 선택적인 일곱 번째 메서드 options는 C 구조체에 대한 internal 포인터를 받는데, 여기에 opclass별 파라미터를 놓아야 하고, void를 반환해요.
필수 사용자 정의 메서드 5개는 다음과 같아요.
config
인덱스 구현에 대한 정적 정보를 반환하는데, 접두사와 노드 레이블 데이터 타입의 OID를 포함해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
첫 번째 인자는 함수의 입력 데이터를 담은 spgConfigIn C 구조체에 대한 포인터예요. 두 번째 인자는 결과 데이터로 채워야 하는 spgConfigOut C 구조체에 대한 포인터예요.
typedef struct spgConfigIn
{
Oid attType; /* Data type to be indexed */
} spgConfigIn;
typedef struct spgConfigOut
{
Oid prefixType; /* Data type of inner-tuple prefixes */
Oid labelType; /* Data type of inner-tuple node labels */
Oid leafType; /* Data type of leaf-tuple values */
bool canReturnData; /* Opclass can reconstruct original data */
bool longValuesOK; /* Opclass can cope with values > 1 page */
} spgConfigOut;
attType는 다형(polymorphic) 인덱스 연산자 클래스를 지원하기 위해 전달돼요. 일반 고정 데이터 타입 연산자 클래스에서는 항상 같은 값을 가지므로 무시해도 돼요.
접두사를 쓰지 않는 연산자 클래스는 prefixType을 VOIDOID로 설정할 수 있어요. 마찬가지로 노드 레이블을 쓰지 않는 연산자 클래스는 labelType을 VOIDOID로 설정할 수 있어요. canReturnData는 연산자 클래스가 원래 공급된 인덱스 값을 재구성할 수 있으면 true로 설정해야 해요. longValuesOK는 attType이 가변 길이이고 연산자 클래스가 반복 접미사화로 긴 값을 세그먼트화할 수 있을 때만 true로 설정해야 해요 (65.3.4.1절 참고).
leafType은 연산자 클래스의 opckeytype 카탈로그 항목이 정의한 인덱스 저장 타입과 일치해야 해요. (opckeytype가 0일 수 있는데, 이는 저장 타입이 연산자 클래스의 입력 타입과 같다는 뜻으로 가장 흔한 상황이에요.) 하위 호환성 때문에 config 메서드는 leafType을 다른 값으로 설정할 수 있고 그 값이 사용되지만, 인덱스 내용이 카탈로그에서 부정확하게 식별되므로 이는 deprecated(권장되지 않음) 돼요. 또 leafType을 초기화하지 않고(0으로) 남겨두는 것도 허용되는데, opckeytype에서 파생된 인덱스 저장 타입을 의미하는 것으로 해석돼요.
attType과 leafType이 다르면 선택 메서드 compress가 반드시 제공돼야 해요. compress 메서드는 인덱스할 datums를 attType에서 leafType으로 변환하는 것을 담당해요.
choose
내부 튜플에 새 값을 삽입하는 방법을 선택해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
첫 번째 인자는 함수의 입력 데이터를 담은 spgChooseIn C 구조체 포인터, 두 번째 인자는 결과 데이터로 채워야 하는 spgChooseOut C 구조체 포인터예요.
typedef struct spgChooseIn
{
Datum datum; /* original datum to be indexed */
Datum leafDatum; /* current datum to be stored at leaf */
int level; /* current level (counting from zero) */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgChooseIn;
typedef enum spgChooseResultType
{
spgMatchNode = 1, /* descend into existing node */
spgAddNode, /* add a node to the inner tuple */
spgSplitTuple /* split inner tuple (change its prefix) */
} spgChooseResultType;
typedef struct spgChooseOut
{
spgChooseResultType resultType; /* action code, see above */
union
{
struct /* results for spgMatchNode */
{
int nodeN; /* descend to this node (index from 0) */
int levelAdd; /* increment level by this much */
Datum restDatum; /* new leaf datum */
} matchNode;
struct /* results for spgAddNode */
{
Datum nodeLabel; /* new node's label */
int nodeN; /* where to insert it (index from 0) */
} addNode;
struct /* results for spgSplitTuple */
{
/* Info to form new upper-level inner tuple with one child tuple */
bool prefixHasPrefix; /* tuple should have a prefix? */
Datum prefixPrefixDatum; /* if so, its value */
int prefixNNodes; /* number of nodes */
Datum *prefixNodeLabels; /* their labels (or NULL for
* no labels) */
int childNodeN; /* which node gets child tuple */
/* Info to form new lower-level inner tuple with all old nodes */
bool postfixHasPrefix; /* tuple should have a prefix? */
Datum postfixPrefixDatum; /* if so, its value */
} splitTuple;
} result;
} spgChooseOut;
datum은 인덱스에 삽입하려고 했던 spgConfigIn의 attType 타입의 원래 datum이에요. leafDatum은 spgConfigOut의 leafType 타입 값으로, compress 메서드가 제공되면 그 메서드를 datum에 적용한 결과이거나, 그렇지 않으면 datum과 같은 값이에요. leafDatum은 choose나 picksplit 메서드가 바꾸면 트리의 더 낮은 수준에서 변할 수 있어요. 삽입 검색이 리프 페이지에 도달하면 leafDatum의 현재 값이 새로 만들어진 리프 튜플에 저장돼요. level은 현재 내부 튜플의 수준으로, 루트 수준이 0이에요. allTheSame은 현재 내부 튜플이 여러 동등 노드를 담도록 표시되어 있으면 true예요 (65.3.4.3절 참고). hasPrefix는 현재 내부 튜플이 접두사를 담고 있으면 true이고, 담고 있으면 prefixDatum이 그 값이에요. nNodes는 내부 튜플에 담긴 자식 노드 수이고, nodeLabels는 그 레이블 값들의 배열이며 레이블이 없으면 NULL이에요.
choose 함수는 새 값이 기존 자식 노드 중 하나와 일치한다고 판단하거나, 새 자식 노드를 추가해야 한다고 판단하거나, 새 값이 튜플 접두사와 일치하지 않아서 덜 제한적인 접두사를 만들기 위해 내부 튜플을 분할해야 한다고 판단할 수 있어요.
새 값이 기존 자식 노드 중 하나와 일치하면 resultType을 spgMatchNode로 설정해요. nodeN을 노드 배열에서 그 노드의 (0부터 세는) 인덱스로 설정해요. 그 노드를 내려가면서 생기는 level 증가분을 levelAdd로 설정하고, 연산자 클래스가 수준을 쓰지 않으면 0으로 남겨둬요. 연산자 클래스가 한 수준에서 다음 수준으로 datums를 수정하지 않으면 restDatum을 leafDatum과 같게 설정하고, 아니면 다음 수준에서 leafDatum으로 쓸 수정된 값으로 설정해요.
새 자식 노드를 추가해야 하면 resultType을 spgAddNode로 설정해요. 새 노드에 쓸 레이블을 nodeLabel로 설정하고, 노드 배열에 삽입할 (0부터 세는) 인덱스를 nodeN으로 설정해요. 노드가 추가된 후 choose 함수가 수정된 내부 튜플로 다시 호출되는데, 그 호출은 spgMatchNode 결과를 내야 해요.
새 값이 튜플 접두사와 일치하지 않으면 resultType을 spgSplitTuple로 설정해요. 이 동작은 모든 기존 노드를 새 하위 수준 내부 튜플로 옮기고, 기존 내부 튜플을 새 하위 수준 내부 튜플을 가리키는 단일 다운링크를 가진 튜플로 교체해요. 새 상위 튜플이 접두사를 가져야 하는지 prefixHasPrefix로 나타내고, 가져야 하면 prefixPrefixDatum으로 접두사 값을 설정해요. 이 새 접두사 값은 인덱스할 새 값을 받아들이도록 원래 것보다 충분히 덜 제한적이어야 해요. 새 튜플에 필요한 노드 수를 prefixNNodes로, 그 레이블을 담은 palloc'd 배열을 prefixNodeLabels로 설정하고, 노드 레이블이 필요 없으면 NULL로 설정해요. 새 상위 튜플의 전체 크기는 교체하는 튜플의 전체 크기보다 클 수 없습니다 — 이는 새 접두사와 새 레이블의 길이를 제약해요. childNodeN을 새 하위 수준 내부 튜플로 다운링크할 노드의 (0부터 세는) 인덱스로 설정해요. 새 하위 수준 내부 튜플이 접두사를 가져야 하는지 postfixHasPrefix로 나타내고, 가져야 하면 postfixPrefixDatum으로 접두사 값을 설정해요. 이 두 접두사와 다운링크 노드의 레이블(있으면)의 조합은 원래 접두사와 같은 의미를 가져야 해요. 새 하위 수준 튜플로 옮겨진 노드 레이블이나 어떤 자식 인덱스 항목도 바꿀 기회가 없기 때문이에요. 노드가 분할된 후 choose 함수가 교체 내부 튜플로 다시 호출돼요. 그 호출은 spgSplitTuple 동작으로 적절한 노드가 만들어지지 않았다면 spgAddNode 결과를 반환할 수 있어요. 결국 choose는 삽입이 다음 수준으로 내려가도록 spgMatchNode를 반환해야 해요.
picksplit
리프 튜플 집합 위에 새 내부 튜플을 어떻게 만들지 결정해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
첫 번째 인자는 입력 데이터를 담은 spgPickSplitIn C 구조체 포인터, 두 번째 인자는 결과 데이터를 채울 spgPickSplitOut C 구조체 포인터예요.
typedef struct spgPickSplitIn
{
int nTuples; /* number of leaf tuples */
Datum *datums; /* their datums (array of length nTuples) */
int level; /* current level (counting from zero) */
} spgPickSplitIn;
typedef struct spgPickSplitOut
{
bool hasPrefix; /* new inner tuple should have a prefix? */
Datum prefixDatum; /* if so, its value */
int nNodes; /* number of nodes for new inner tuple */
Datum *nodeLabels; /* their labels (or NULL for no labels) */
int *mapTuplesToNodes; /* node index for each leaf tuple */
Datum *leafTupleDatums; /* datum to store in each new leaf tuple */
} spgPickSplitOut;
nTuples는 제공된 리프 튜플 수예요. datums는 spgConfigOut의 leafType 타입인 그 datum 값들의 배열이에요. level은 모든 리프 튜플이 공유하는 현재 수준으로, 새 내부 튜플의 수준이 될 거예요.
새 내부 튜플이 접두사를 가져야 하는지 hasPrefix로 설정하고, 가져야 하면 prefixDatum으로 접두사 값을 설정해요. 새 내부 튜플이 담을 노드 수를 nNodes로, 그 레이블 값 배열을 nodeLabels로 설정하고, 레이블이 필요 없으면 NULL로 설정해요. mapTuplesToNodes를 각 리프 튜플이 할당될 노드의 (0부터 세는) 인덱스를 주는 배열로 설정해요. leafTupleDatums를 새 리프 튜플에 저장할 값들의 배열로 설정해요 (이 값들은 연산자 클래스가 한 수준에서 다음 수준으로 datums를 수정하지 않으면 입력 datums와 같을 거예요). picksplit 함수가 nodeLabels, mapTuplesToNodes, leafTupleDatums 배열을 palloc해야 한다는 점을 주의하세요.
리프 튜플이 둘 이상 제공되면 picksplit 함수가 그것들을 둘 이상의 노드로 분류할 것으로 기대돼요. 그렇지 않으면 리프 튜플을 여러 페이지로 나눌 수 없는데, 이게 이 연산의 궁극적인 목적이기 때문이에요. 그래서 picksplit 함수가 모든 리프 튜플을 같은 노드에 두게 되면, SP-GiST 핵심 코드가 그 결정을 덮어쓰고 리프 튜플을 동일한 레이블의 여러 노드에 무작위로 할당한 내부 튜플을 생성해요. 그런 튜플은 이런 일이 일어났음을 나타내기 위해 allTheSame으로 표시돼요. choose와 inner_consistent 함수는 그런 내부 튜플을 적절히 처리해야 해요. 더 자세한 내용은 65.3.4.3절을 참고하세요.
picksplit은 config 함수가 longValuesOK를 true로 설정하고 페이지보다 큰 입력 값이 제공된 경우에만 단일 리프 튜플에 적용될 수 있어요. 이 경우 연산의 요점은 접두사를 떼어내고 더 짧은 새 리프 datum 값을 만드는 거예요. 페이지에 맞을 만큼 충분히 짧은 리프 datum이 생길 때까지 호출이 반복돼요. 자세한 내용은 65.3.4.1절을 참고하세요.
inner_consistent
트리 검색 중 따라갈 노드(분기) 집합을 반환해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
첫 번째 인자는 입력 데이터를 담은 spgInnerConsistentIn C 구조체 포인터, 두 번째 인자는 결과 데이터를 채울 spgInnerConsistentOut C 구조체 포인터예요.
typedef struct spgInnerConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
ScanKey orderbys; /* array of ordering operators and comparison
* values */
int nkeys; /* length of scankeys array */
int norderbys; /* length of orderbys array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
MemoryContext traversalMemoryContext; /* put new traverse values here */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgInnerConsistentIn;
typedef struct spgInnerConsistentOut
{
int nNodes; /* number of child nodes to be visited */
int *nodeNumbers; /* their indexes in the node array */
int *levelAdds; /* increment level by this much for each */
Datum *reconstructedValues; /* associated reconstructed values */
void **traversalValues; /* opclass-specific traverse values */
double **distances; /* associated distances */
} spgInnerConsistentOut;
길이 nkeys의 배열 scankeys는 인덱스 검색 조건을 설명해요. 이 조건들은 AND로 결합되는데 — 모두를 만족하는 인덱스 항목만 관심 대상이에요. (nkeys = 0이면 모든 인덱스 항목이 쿼리를 만족한다는 뜻이에요.) 보통 consistent 함수는 각 배열 항목의 sk_strategy와 sk_argument 필드만 신경 쓰는데, 이는 각각 인덱스 가능 연산자와 비교 값을 줘요. 특히 비교 값이 NULL인지 sk_flags를 확인할 필요는 없어요. SP-GiST 핵심 코드가 그런 조건을 걸러내기 때문이에요. 길이 norderbys의 배열 orderbys는 같은 방식으로 정렬 연산자(있으면)를 설명해요. reconstructedValue는 부모 튜플에 대해 재구성된 값으로, 루트 수준이거나 부모 수준에서 inner_consistent 함수가 값을 제공하지 않았으면 (Datum) 0이에요. traversalValue는 부모 인덱스 튜플에서 inner_consistent를 이전 호출로부터 전달된 traverse 데이터에 대한 포인터이거나, 루트 수준에서는 NULL이에요. traversalMemoryContext는 출력 traverse 값을 저장할 메모리 컨텍스트예요 (아래 참고). level은 현재 내부 튜플의 수준으로 루트 수준이 0이에요. returnData는 이 쿼리에 재구성된 데이터가 필요한 경우 true인데, config 함수가 canReturnData를 단언한 경우에만 그렇게 돼요. allTheSame은 현재 내부 튜플이 "all-the-same"으로 표시되면 true인데, 이 경우 모든 노드가 같은 레이블(있으면)을 가지므로 모두 또는 전혀 쿼리와 일치해요 (65.3.4.3절 참고). hasPrefix는 현재 내부 튜플이 접두사를 담고 있으면 true이고, 담고 있으면 prefixDatum이 그 값이에요. nNodes는 내부 튜플에 담긴 자식 노드 수이고, nodeLabels는 그 레이블 값 배열이며 노드에 레이블이 없으면 NULL이에요.
검색이 방문해야 하는 자식 노드 수를 nNodes로, 그 인덱스 배열을 nodeNumbers로 설정해야 해요. 연산자 클래스가 수준을 추적하면 방문할 각 노드로 내려갈 때 필요한 수준 증가분 배열을 levelAdds로 설정해요. (종종 이 증가분들은 모든 노드에 대해 같지만 반드시 그런 건 아니므로 배열을 써요.) 값 재구성이 필요하면 방문할 각 자식 노드에 대해 재구성된 값 배열을 reconstructedValues로 설정하고, 아니면 NULL로 남겨둬요. 재구성된 값은 spgConfigOut의 leafType 타입으로 가정돼요. (그러나 핵심 시스템이 그것들을 복사하는 것 외에는 아무것도 하지 않으므로, leafType과 같은 typlen과 typbyval 속성을 갖기만 하면 충분해요.) 정렬된 검색을 수행하면 orderbys 배열에 따른 거리 값 배열을 distances로 설정해요 (거리가 가장 낮은 노드가 먼저 처리돼요). 아니면 NULL로 남겨둬요. 트리 검색의 더 낮은 수준에 추가 대역 외 정보("traverse values")를 전달하고 싶으면 방문할 각 자식 노드에 하나씩, 적절한 traverse 값 배열을 traversalValues로 설정하고, 아니면 NULL로 남겨둬요. inner_consistent 함수가 현재 메모리 컨텍스트에서 nodeNumbers, levelAdds, distances, reconstructedValues, traversalValues 배열을 palloc해야 한다는 점을 주의하세요. 단, traversalValues 배열이 가리키는 출력 traverse 값들은 traversalMemoryContext에 할당해야 해요. 각 traverse 값은 단일 palloc'd 청크여야 해요.
leaf_consistent
리프 튜플이 쿼리를 만족하면 true를 반환해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
첫 번째 인자는 입력 데이터를 담은 spgLeafConsistentIn C 구조체 포인터, 두 번째 인자는 결과 데이터를 채울 spgLeafConsistentOut C 구조체 포인터예요.
typedef struct spgLeafConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
ScanKey orderbys; /* array of ordering operators and comparison
* values */
int nkeys; /* length of scankeys array */
int norderbys; /* length of orderbys array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
Datum leafDatum; /* datum in leaf tuple */
} spgLeafConsistentIn;
typedef struct spgLeafConsistentOut
{
Datum leafValue; /* reconstructed original data, if any */
bool recheck; /* set true if operator must be rechecked */
bool recheckDistances; /* set true if distances must be rechecked */
double *distances; /* associated distances */
} spgLeafConsistentOut;
길이 nkeys의 배열 scankeys는 인덱스 검색 조건을 설명해요. 이 조건들은 AND로 결합되어 — 모두를 만족하는 인덱스 항목만 쿼리를 만족해요. (nkeys = 0이면 모든 인덱스 항목이 쿼리를 만족한다는 뜻이에요.) 보통 consistent 함수는 각 배열 항목의 sk_strategy와 sk_argument 필드만 신경 써요. (비교 값이 NULL인지 sk_flags를 확인할 필요는 없어요. SP-GiST 핵심 코드가 그런 조건을 걸러내기 때문이에요.) 길이 norderbys의 배열 orderbys는 같은 방식으로 정렬 연산자를 설명해요. reconstructedValue는 부모 튜플에 대해 재구성된 값으로, 루트 수준이거나 부모 수준에서 inner_consistent 함수가 값을 제공하지 않았으면 (Datum) 0이에요. traversalValue는 부모 인덱스 튜플에서 inner_consistent를 이전 호출로부터 전달된 traverse 데이터에 대한 포인터이거나 루트 수준에서는 NULL이에요. level은 현재 리프 튜플의 수준으로 루트 수준이 0이에요. returnData는 이 쿼리에 재구성된 데이터가 필요한 경우 true인데, config 함수가 canReturnData를 단언한 경우에만 그래요. leafDatum은 현재 리프 튜플에 저장된 spgConfigOut의 leafType 타입 키 값이에요.
함수는 리프 튜플이 쿼리와 일치하면 true를, 아니면 false를 반환해야 해요. true 경우에 returnData가 true면, leafValue를 이 리프 튜플에 대해 인덱스하려고 원래 공급된 (spgConfigIn의 attType 타입) 값으로 설정해야 해요. 또 일치가 불확실해서 실제 힙 튜플에 연산자를 다시 적용해 일치를 검증해야 한다면 recheck를 true로 설정할 수 있어요. 정렬된 검색을 수행하면 orderbys 배열에 따른 거리 값 배열을 distances로 설정해요. 아니면 NULL로 남겨둬요. 반환된 거리 중 하나라도 정확하지 않으면 recheckDistances를 true로 설정해요. 이 경우 실행기가 힙에서 튜플을 가져온 뒤 정확한 거리를 계산하고, 필요하면 튜플을 재정렬해요.
선택적 사용자 정의 메서드는 다음과 같아요.
Datum compress(Datum in)
데이터 항목을 인덱스의 리프 튜플에 물리적으로 저장하기에 적합한 형식으로 변환해요. spgConfigIn의 attType 타입 값을 받아 spgConfigOut의 leafType 타입 값을 반환해요. 출력 값은 out-of-line TOAST 포인터를 담으면 안 돼요.
참고:
compress메서드는 저장할 값에만 적용돼요. consistent 메서드는compress를 사용한 변환 없이 쿼리scankeys를 그대로 받아요.
options
연산자 클래스 동작을 제어하는 사용자에게 보이는 파라미터 집합을 정의해요.
함수의 SQL 선언은 이렇게 생겨야 해요.
CREATE OR REPLACE FUNCTION my_options(internal)
RETURNS void
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT;
함수는 local_relopts 구조체에 대한 포인터를 받는데, 연산자 클래스별 옵션 집합으로 채워야 해요. 옵션은 PG_HAS_OPCLASS_OPTIONS()와 PG_GET_OPCLASS_OPTIONS() 매크로를 사용해 다른 지원 함수에서 접근할 수 있어요.
SP-GiST에서 키의 표현이 유연하므로, 사용자 지정 파라미터에 따라 달라질 수 있어요.
모든 SP-GiST 지원 메서드는 보통 수명이 짧은 메모리 컨텍스트에서 호출돼요. 즉 CurrentMemoryContext는 각 튜플 처리가 끝나면 리셋돼요. 그래서 palloc한 것을 전부 pfree할 걱정은 크게 하지 않아도 돼요. (config 메서드는 예외로, 메모리 누수를 피하려고 해야 해요. 하지만 보통 config 메서드는 전달된 파라미터 구조체에 상수를 할당하는 것 외에는 아무것도 할 필요가 없어요.)
인덱스된 컬럼이 콜레이션 가능한 데이터 타입이면, 표준 PG_GET_COLLATION() 메커니즘을 사용해 인덱스 콜레이션이 모든 지원 메서드에 전달돼요.
구현 (Implementation)
이 절은 SP-GiST 연산자 클래스 구현자가 알아두면 유용한 구현 상세와 요령을 다뤄요.
SP-GiST 한계 (SP-GiST Limits)
개별 리프 튜플과 내부 튜플은 단일 인덱스 페이지(기본 8kB) 에 맞아야 해요. 그래서 가변 길이 데이터 타입의 값을 인덱싱할 때 긴 값은 radix 트리 같은 메서드로만 지원할 수 있어요. 여기서 트리의 각 수준은 페이지에 맞을 만큼 짧은 접두사를 포함하고, 최종 리프 수준은 역시 페이지에 맞을 만큼 짧은 접미사를 포함해요. 연산자 클래스는 이런 일이 일어나도록 준비돼 있을 때만 longValuesOK를 true로 설정해야 해요. 아니면 SP-GiST 핵심이 인덱스 페이지에 맞기엔 너무 큰 값을 인덱싱하려는 어떤 요청도 거부해요.
마찬가지로 내부 튜플이 인덱스 페이지에 맞기엔 너무 커지지 않도록 하는 것도 연산자 클래스의 책임이에요. 이는 한 내부 튜플에 쓸 수 있는 자식 노드 수와 접두사 값의 최대 크기를 제한해요.
또 다른 한계는 내부 튜플의 노드가 리프 튜플 집합을 가리킬 때, 그 튜플들이 모두 같은 인덱스 페이지에 있어야 한다는 거예요. (이건 seek를 줄이고 그런 튜플을 연결하는 링크의 공간을 아끼기 위한 설계 결정이에요.) 리프 튜플 집합이 페이지에 너무 커지면 분할이 수행되고 중간 내부 튜플이 삽입돼요. 이게 문제를 해결하려면 새 내부 튜플이 리프 값 집합을 둘 이상의 노드 그룹으로 나눠야 해요. 연산자 클래스의 picksplit 함수가 그러지 못하면 SP-GiST 핵심은 65.3.4.3절에서 설명하는 비상 수단에 의존해요.
longValuesOK가 true이면, SP-GiST 트리의 연속 수준이 내부 튜플의 접두사와 노드 레이블에 점점 더 많은 정보를 흡수해서 필요한 리프 datum을 점점 더 작게 만들어, 결국 페이지에 맞게 될 것으로 기대돼요. 연산자 클래스의 버그가 무한 삽입 루프를 일으키는 것을 막기 위해, SP-GiST 핵심은 리프 datum이 choose 메서드 호출 10회 주기 안에 더 작아지지 않으면 오류를 일으켜요.
노드 레이블이 없는 SP-GiST (SP-GiST Without Node Labels)
일부 트리 알고리즘은 각 내부 튜플에 고정된 노드 집합을 사용해요. 예를 들어 쿼드 트리에는 내부 튜플의 중심점 주변 사분면에 해당하는 항상 정확히 네 개의 노드가 있어요. 그런 경우 코드는 보통 노드를 번호로 다루고 명시적 노드 레이블이 필요 없어요. 노드 레이블을 억제하고(그래서 공간을 아끼고) 싶으면, picksplit 함수가 nodeLabels 배열에 대해 NULL을 반환할 수 있고, 마찬가지로 choose 함수가 spgSplitTuple 동작 중 prefixNodeLabels 배열에 대해 NULL을 반환할 수 있어요. 이는 결과적으로 이후 choose와 inner_consistent 호출에서 nodeLabels가 NULL이 되게 해요. 원칙적으로 같은 인덱스에서 일부 내부 튜플에 노드 레이블을 쓰고 다른 튜플에선 생략할 수 있어요.
레이블이 없는 노드를 가진 내부 튜플로 작업할 때, choose가 spgAddNode를 반환하는 것은 오류예요. 그런 경우 노드 집합이 고정되어 있기 때문이죠.
"All-the-Same" 내부 튜플 (All-the-Same Inner Tuples)
SP-GiST 핵심은 picksplit 함수가 제공된 리프 값을 적어도 두 개의 노드 범주로 나누지 못하면 연산자 클래스의 picksplit 결과를 덮어쓸 수 있어요. 이렇게 되면, picksplit이 사용한 그 노드 하나에 준 것과 같은 레이블(있으면)을 각각 가진 여러 노드로 새 내부 튜플이 만들어지고, 리프 값들이 이 동등한 노드들에 무작위로 나눠져요. allTheSame 플래그가 내부 튜플에 설정되어, choose와 inner_consistent 함수에게 그 튜플이 기대했을 것과 다른 노드 집합을 가질 수 있음을 경고해요.
allTheSame 튜플을 다룰 때 choose의 spgMatchNode 결과는 새 값이 동등한 노드 중 어느 것에나 할당될 수 있다는 뜻으로 해석돼요. 핵심 코드는 제공된 nodeN 값을 무시하고 (트리를 균형 있게 유지하려고) 노드 중 하나에 무작위로 내려가요. choose가 spgAddNode를 반환하는 것은 오류예요. 그러면 노드들이 모두 동등하지 않게 되기 때문이죠. 삽입할 값이 기존 노드들과 일치하지 않으면 spgSplitTuple 동작을 써야 해요.
allTheSame 튜플을 다룰 때 inner_consistent 함수는 노드들이 모두 동등하므로, 인덱스 검색을 계속하기 위한 대상으로 모든 노드 또는 아무 노드도 반환해야 해요. inner_consistent 함수가 보통 노드의 의미에 대해 얼마나 가정하는지에 따라 특수 사례 코드가 필요할 수도 있고 아닐 수도 있어요.
예제 (Examples)
PostgreSQL 소스 배포판에는 Table 65.2에서 설명한 대로 SP-GiST용 인덱스 연산자 클래스의 예제가 여러 개 포함돼 있어요. 코드를 보려면 src/backend/access/spgist/와 src/backend/utils/adt/를 살펴보세요.