R-Tree 인덱스
R-Tree 인덱스 (R-Tree Indexes)
[spatial 확장]({% link docs/current/core_extensions/spatial/overview.md %})은 R-tree 확장 인덱스 타입을 통해 공간 인덱싱을 지원해요.
출처: 문서
본문
왜 R-Tree 인덱스를 사용해야 할까?
지리공간 데이터셋을 다룰 때, 특정 관심 영역과의 공간 관계를 기반으로 행을 필터링하고 싶은 경우가 아주 흔해요. 안타깝게도 DuckDB의 벡터화 실행 엔진이 꽤 빠르더라도, 이런 종류의 연산은 항상 테이블의 모든 행을 검사하는 전체 테이블 스캔이 필요하므로 큰 데이터셋에는 잘 확장되지 않아요. 하지만 테이블을 R-tree로 인덱싱하면 이런 유형의 쿼리를 크게 가속화할 수 있어요.
R-Tree 인덱스는 어떻게 동작하나?
R-tree는 균형 트리 데이터 구조로, 각 geometry의 근사 최소 경계 사각형 (과 해당 행의 내부 ID)을 리프 노드에, 모든 자식 노드의 경계 사각형을 감싸는 경계 사각형을 각 내부 노드에 저장해요.
geometry의 최소 경계 사각형 (MBR)은 geometry를 완전히 감싸는 가장 작은 사각형이에요. 보통 geometry의 경계 사각형(2D geometry 맥락의 경계 "box")이라고 할 때 최소 경계 사각형을 의미해요. 또한 경계 box/사각형은 축-정렬된 것으로 가정하는 경향이 있어요. 즉 사각형이 회전하지 않으며 측면이 항상 좌표 축에 평행하다는 뜻이에요. 점의 MBR은 점 자체예요.
R-tree를 위에서 아래로 탐색하면 부모 노드의 경계 사각형이 쿼리 영역과 전혀 교차하지 않으면 하위 트리 전체를 건너뛸 수 있으므로, 인덱싱된 geometry 컬럼이 특정 관심 영역과 교차하는 행만 매우 빠르게 검색할 수 있어요. 리프 노드에 도달하면 그 geometry가 쿼리 영역과 교차하는 특정 행만 디스크에서 가져오고, 자주 훨씬 더 비싼 정확한 공간 술어 검사(및 기타 필터)는 이 행들에 대해서만 실행하면 돼요.
DuckDB에서 R-Tree 인덱스의 제한 사항은?
R-tree 인덱스 사용을 시작하기 전에 알아야 할 몇 가지 제한 사항이 있어요:
- R-tree 인덱스는
GEOMETRY데이터 타입에만 지원돼요. - R-tree 인덱스는 테이블이 다음 공간 술어 함수 중 하나로 (
WHERE절을 사용해) 필터링될 때만 "인덱스 스캔"을 수행하는 데 사용돼요 (모두 교차를 의미하므로):ST_Equals,ST_Intersects,ST_Touches,ST_Crosses,ST_Within,ST_Contains,ST_Overlaps,ST_Covers,ST_CoveredBy,ST_ContainsProperly. - 공간 술어 함수의 인자 하나는 "상수"(즉, 쿼리 플랜 수립 시점에 결과가 알려진 표현식)여야 해요. 이는 쿼리 플래너가 R-tree 인덱스 스캔을 사용하기 위해 쿼리 실행 전에 쿼리 영역의 경계 box를 알아야 하기 때문이에요.
앞으로 추가 술어 함수와 공간 조인 같은 더 복잡한 쿼리를 가속화하는 데 R-tree 인덱스를 사용할 수 있게 하고 싶어요.
DuckDB에서 R-Tree 인덱스 사용법
R-tree 인덱스를 만들려면 USING RTREE 절과 함께 CREATE INDEX 구문을 사용하고, 괄호 안에 인덱싱할 geometry 컬럼을 전달해요. 예를 들어:
-- geometry 컬럼이 있는 테이블 생성
CREATE TABLE my_table (geom GEOMETRY);
-- geometry 컬럼에 R-tree 인덱스 생성
CREATE INDEX my_idx ON my_table USING RTREE (geom);
R-tree 인덱스를 만들 때 WITH 절로 추가 옵션을 전달해 R-tree의 동작을 제어할 수도 있어요. 예를 들어 R-tree의 노드당 최대 항목 수를 지정하려면 max_node_capacity 옵션을 사용해요:
CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (max_node_capacity = 16);
이 옵션을 조정하는 것이 성능에 미치는 영향은 DuckDB가 실행되는 시스템 설정, 데이터셋의 공간 분포, 특정 워크로드의 쿼리 패턴에 크게 의존해요. 기본값이 충분히 좋아야 하지만 다른 파라미터로 실험하고 싶다면 여기서 전체 옵션 목록을 보세요.
예시
다음은 geometry 컬럼에 R-tree 인덱스를 만들고, 공간 술어로 테이블이 필터링될 때 RTREE_INDEX_SCAN 연산자가 사용되는 것을 보여주는 예시예요:
INSTALL spatial;
LOAD spatial;
-- 10_000개의 무작위 점이 있는 테이블 생성
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 10_000, 1337);
-- 테이블에 인덱스 생성.
CREATE INDEX my_idx ON t1 USING RTREE (geom);
-- 인덱싱된 geometry 컬럼에 "공간 술어"로 쿼리 수행
-- 이 경우 두 번째 인자인 ST_MakeEnvelope 호출이 "상수"임에 주목
SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
390
R-tree 인덱스 스캔이 사용되는지 EXPLAIN 구문으로 직접 확인할 수 있어요:
EXPLAIN SELECT count(*) FROM t1 WHERE ST_Within(geom, ST_MakeEnvelope(45, 45, 65, 65));
┌───────────────────────────┐
│ UNGROUPED_AGGREGATE │
│ ──────────────────── │
│ Aggregates: │
│ count_star() │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ FILTER │
│ ──────────────────── │
│ ST_Within(geom, '...') │
│ │
│ ~2000 Rows │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│ RTREE_INDEX_SCAN │
│ ──────────────────── │
│ t1 (RTREE INDEX SCAN : │
│ my_idx) │
│ │
│ Projections: geom │
│ │
│ ~10000 Rows │
└───────────────────────────┘
성능 고려 사항 (Performance Considerations)
벌크 로딩 및 유지보수
이미 채워진 테이블 위에 R-tree를 만드는 것이 먼저 인덱스를 만든 다음 데이터를 삽입하는 것보다 훨씬 빠르게. 그 이유는 R-tree가 주기적으로 스스로 재균형을 해야 하고, 삽입 후 노드가 최대 용량에 도달하면 다소 비용이 드는 분할 연산을 수행해야 하며, 추가 분할이 트리 위로 연쇄할 수 있기 때문이에요. 하지만 이미 채워진 테이블에 R-tree 인덱스를 만들면 특별한 하향식 "벌크 로딩 알고리즘"(Sort-Tile-Recursive)이 사용되는데, 필요한 노드의 총 수를 처음부터 계산할 수 있으므로 모든 항목을 이미 균형 잡힌 트리로 나눠요.
또한 벌크 로딩 알고리즘을 사용하는 것은 더 나은 구조(경계 box 간 겹침이 적음)의 R-tree를 만드는 경향이 있어, 보통 더 나은 쿼리 성능으로 이어져요. 많은 업데이트나 삭제 후 R-tree 쿼리 성능이 저하되기 시작하면 인덱스를 버리고 다시 만드는 것이 더 고품질의 R-tree를 만들 수 있어요.
메모리 사용
DuckDB의 내장 ART-index처럼, R-tree를 포함하는 모든 연관 버퍼는 (DuckDB가 디스크-백업 모드로 실행될 때) 디스크에서 지연 로드되지만, 인덱스가 버려지지 않는 한 현재 절대 언로드되지 않아요. 즉 전체 인덱스를 스캔하게 되면 인덱스 전체가 메모리에 로드되어 데이터베이스 연결이 지속되는 동안 거기에 머물러요. 하지만 R-tree 인덱스가 사용하는 모든 메모리(벌크-로딩 중에도)는 DuckDB가 추적하며, memory_limit 구성 파라미터가 설정한 메모리 제한에 포함돼요.
튜닝
특정 워크로드에 따라 max_node_capacity와 min_node_capacity 옵션을 실험해 R-tree의 구조와 삽입·삭제에 대한 반응을 바꿀 수 있어요. 여기서 전체 옵션 목록을 보세요. 일반적으로 총 노드 수가 더 많은 트리(즉, 더 낮은 max_node_capacity)는 쿼리 실행 중 더 공격적인 하위 트리 가지치기를 가능하게 하는 더 세분화된 구조를 만들 수 있지만, 트리 자체를 저장하는 데 더 많은 메모리가 필요하고 더 많은 내부 노드를 탐색해야 하므로 더 큰 영역을 쿼리할 때 더 가혹할 수 있어요.
옵션 (Options)
R-tree 인덱스를 만들 때 WITH 절에 다음 옵션을 전달할 수 있어요: (예: CREATE INDEX my_idx ON my_table USING RTREE (geom) WITH (⟨option⟩ = ⟨value⟩);)
| 옵션 | 설명 | 기본값 |
|---|---|---|
max_node_capacity |
R-tree의 노드당 최대 항목 수 | 128 |
min_node_capacity |
R-tree의 노드당 최소 항목 수 | 0.4 * max_node_capacity |
*삭제 후 노드가 최소 항목 수 아래로 내려가면 노드가 해체되고 모든 항목이 트리 상단에서 다시 삽입돼요. 이것은 트리가 너무 불균형해지는 것을 방지하기 위한 R-tree 구현의 일반적인 연산이에요.
R-Tree 테이블 함수
rtree_index_dump(VARCHAR) 테이블 함수는 R-tree 인덱스 안의 모든 노드를 반환하는 데 사용할 수 있는데, 디버깅, 프로파일링, 또는 인덱스의 구조를 그냥 검사할 때 유용해요. 이 함수는 R-tree 인덱스의 이름을 인자로 받고 다음 컬럼을 가진 테이블을 반환해요:
| 컬럼 이름 | 타입 | 설명 |
|---|---|---|
level |
INTEGER |
R-tree의 노드 레벨. 루트 노드는 레벨 0 |
bounds |
BOX_2DF |
노드의 경계 box |
row_id |
ROW_TYPE |
리프 노드이면 테이블에서 행의 rowid, 그렇지 않으면 NULL |
예시:
-- 64개의 무작위 점이 있는 테이블 생성
CREATE TABLE t1 AS SELECT point::GEOMETRY AS geom
FROM st_generatepoints({min_x: 0, min_y: 0, max_x: 100, max_y: 100}::BOX_2D, 64, 1337);
-- geometry 컬럼에 R-tree 인덱스 생성 (시연을 위해 낮은 max_node_capacity 사용)
CREATE INDEX my_idx ON t1 USING RTREE (geom) WITH (max_node_capacity = 4);
-- R-tree 인덱스 검사. 트리 깊이로 들어갈수록 지점 노드의 경계 box 면적이
-- 감소하는 것에 주목.
SELECT
level,
bounds::GEOMETRY AS geom,
CASE WHEN row_id IS NULL THEN st_area(geom) ELSE NULL END AS area,
row_id,
CASE WHEN row_id IS NULL THEN 'branch' ELSE 'leaf' END AS kind
FROM rtree_index_dump('my_idx')
ORDER BY area DESC;
┌───────┬──────────────────────────────┬────────────────────┬────────┬─────────┐
│ level │ geom │ area │ row_id │ kind │
│ int32 │ geometry │ double │ int64 │ varchar │
├───────┼──────────────────────────────┼────────────────────┼────────┼─────────┤
│ 0 │ POLYGON ((2.17285037040710… │ 3286.396482226409 │ │ branch │
│ 0 │ POLYGON ((6.00962591171264… │ 3193.725100864862 │ │ branch │
│ 0 │ POLYGON ((0.74995160102844… │ 3099.921458393704 │ │ branch │
│ 0 │ POLYGON ((14.6168870925903… │ 2322.2760491675654 │ │ branch │
│ 1 │ POLYGON ((2.17285037040710… │ 604.1520104388514 │ │ branch │
│ 1 │ POLYGON ((26.6022186279296… │ 569.1665467030252 │ │ branch │
│ 1 │ POLYGON ((35.7942314147949… │ 435.24662436250037 │ │ branch │
│ 1 │ POLYGON ((62.2643051147460… │ 396.39027683023596 │ │ branch │
│ 1 │ POLYGON ((59.5225715637207… │ 386.09153403820187 │ │ branch │
│ 1 │ POLYGON ((82.3060836791992… │ 369.15115640929434 │ │ branch │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ · │ · │ · │ · │ · │
│ 2 │ POLYGON ((20.5411434173584… │ │ 35 │ leaf │
│ 2 │ POLYGON ((14.6168870925903… │ │ 36 │ leaf │
│ 2 │ POLYGON ((43.7271652221679… │ │ 39 │ leaf │
│ 2 │ POLYGON ((53.4629211425781… │ │ 44 │ leaf │
│ 2 │ POLYGON ((26.6022186279296… │ │ 62 │ leaf │
│ 2 │ POLYGON ((53.1732063293457… │ │ 63 │ leaf │
│ 2 │ POLYGON ((78.1427154541015… │ │ 10 │ leaf │
│ 2 │ POLYGON ((75.1728591918945… │ │ 15 │ leaf │
더 알아보기 (Learn more)
spatial 확장의 전체 개요는 [spatial extension]({% link docs/current/core_extensions/spatial/overview.md %}) 문서를 참고해요.