[PostgreSQL] PostgreSQL의 GiST, SP-GiST Index에 대해서 알아보자.

(1) GiST

 

복합적인 지리학적(geometric) 데이터를 조회하는데 매우 유용한 인덱스이다.
Full Text Search 에서도 사용한다.

 

인덱싱 과정은 아래 그림과 같은 방식이다.

분포 양을 내부적인 로직으로 점점 나눈다.

 

1

 

2

 

3

 

 

 

그래프로 한 번 알아보자.

CREATE TABLE points(p point);
INSERT INTO points(p) VALUES
(POINT '(1,1)'), (POINT '(3,2)'), (POINT '(6,3)'),
(POINT '(5,5)'), (POINT '(7,8)'), (POINT '(8,6)');

CREATE INDEX ON points USING GIST(p);

앞서 배운 Geometric Type을 사용해서 일부 점을 INSERT 했다.

그리고 점에 대해서 GiST 인덱스를 생성한다.

 

 

내부 로직으로 점들의 범위를 위와 같이 나눈다.

SET enable_seqscan = off;
EXPLAIN(costs off) SELECT * FROM points WHERE p <@ box '(2,1),(7,4)';

Result

QUERY PLAN                
----------------------------------------------
Index Only Scan using points_p_idx on points
  Index Cond: (p <@ '(7,4),(2,1)'::box)
(2 rows)

 

정상적으로 인덱스 스캔을 확인할 수 있다.

 

(2, 1) , (7, 4) 범위를 찾아보면 위 사진과 같이 값을 찾아 나간다.

SELECT * FROM points WHERE p <@ box '(2,1),(7,4)';

Result

p
-------
(3,2)
(6,3)
(2 rows)

 

 

 

(2) SP-GiST

 

GiST를 개선하고 분류할 공간을 또 공간 단위로 나누어 관리하는 개념

 

SP-GiST에는 여러가지 방식이 존재하지만, 많이 사용한다는 Quad-Tree(사진 트리) 방식에 대해서 설명하겠다.

아래 그림과 같이 내부 로직에 의해  한 점을 기준으로 계속해서 4분할 해나가는 방식이다.

 

1

2

3

 

그래프로 알아보자.

위 그림처럼 인덱싱을 진행하며

 

수학시간에 배운 그래프에서 사분면을 통해서 각 레벨에 최대 4개 노드를 가지며 인덱싱을 한다. 

 

 

 

 

REFERENCES

PostgreSQL : Documentation: 13: PostgreSQL 13.7 Documentation