[MySQL] R-Tree 인덱스와 Fractal-Tree 인덱스

R-Tree 인덱스

---

아마도 MySQL의 공간 인덱스(Spatial Index)라는 말을 한번쯤 들어본 적이 있을 것입니다. 공간 인덱스는 R-Tree 인덱스 알고리즘을 이용해 2차원의 데이터를 인덱싱하고 검색하는 목적의 인덱스입니다. 기본적인 내부 메커니즘은 B-Tree와 흡사합니다. B-Tree는 인덱스를 구성하는 컬럼의 값이 1차원의 스칼라값인 반면, R-Tree 인덱스는 2차원의 공간 개념 값이라는 것입니다.

최근 GPS나 지도 서비스를 내장하는 스마트 폰이 대중화되면서 SNS 서비스가 GIS와 GPS에 기반을 둔 서비스로 확장되고 있기도 합니다. 이러한 위치 기반의 서비스를 구현하는 방법은 여러 가지가 있겠지만 MySQL의 공간 확장(Spatial Extension)을 이용하면 간단하게 이러한 기능을 구현할 수 있습니다.

MySQL의 공간 확장에는 아래와 같이 크게 3가지 기능이 포함돼 있습니다. R-Tree 인덱스를 사용하여 MySQL은 공간 검색을 제공합니다.

- 공간 데이터를 저장할 수 있는 데이터 타입

- 공간 데이터의 검색을 위한 공간 인덱스(R-Tree 알고리즘)

- 공간 데이터의 연산 함수(거리 또는 포함 관계의 처리)

구조 및 특성

MySQL은 공간 정보의 저장 및 검색을 위해 여러 가지 기하학적 도형(Geometry) 정보를 관리할 수 있는 데이터 타입을 제공합니다. 대표적으로 MySQL에서 지원하는 데이터 타입은 아래와 같습니다.

GEOMETRY 타입은 POINT, LINE, POLYGON, GEOMETRY 타입의 수퍼타입입니다. POINT와 LINE, 그리고 POLYGON 객체 모두 저장할 수 있습니다.

공간 정보의 검색을 위한 R-Tree 알고리즘을 이해하려면 MBR이라는 개념을 알고 있어야 합니다. MBR이란 Minimum Bounding Rectangle의 약자로 해당 도형을 감싸는 최소 크기의 사각형을 의미하는데, 이 사각형들의 포함 관계를 B-Tree 형태로 구현한 인덱스가 R-Tree입니다.

간단히 R-Tree의 구조를 살펴보면, 단수히 X좌표와 Y좌표만 있는 포인트 데이터 또한 하나의 도형 객체가 될 수 있습니다. 이러한 도형이 저장됐을 때 만들어지는 인덱스의 구조를 이해하려면 우선 이도형들의 MBR이 어떻게 되는지 알아볼 필요가 있습니다. 

위 도형의 MBR은 3개의 레벨로 나뉘어져 있습니다.

최상위 레벨: R1

차상위 레벨: R2, R3

최하위 레벨: R4, R5, R6, R7

최하위 레벨의 MBR(각 도형을 제일 안쪽에서 둘러썬 상자)는 각 도형 데이터의 MBR을 의미합니다. 그리고 차상위 레벨의 MBR은 중간 크기의 MBR(도형 객체의 그룹)입니다. 최상위 MBR은 R-Tree의 루트 노드에 저장되는 정보가 되며, 차상위 그룹 MBR은 R-Tree의 브랜치 노드가 됩니다. 마지막으로 각 도형의 객체는 리프 노드에 저장되므로, R-Tree 인덱스의 내부를 표현할 수 있습니다.

R-Tree 인덱스의 용도

R-Tree는 위에서 언급한 MBR 정보를 이용해 B-Tree 형태로 인덱스를 구축하므로 Rectangle의 "R"과 B-Tree의 "Tree"를 섞어서 R-Tree라는 이름이 붙여졌으며, 공간(Spatial) 인덱스라고도 합니다. 일반적으로는 WGS84(GPS) 기준의 위도, 경도 좌표 저장에 주로 사용됩니다. 하지만 위도, 경도 좌표뿐 아니라 CAD/CAM 소프트웨어 또는 회로 디자인 등과 같이 좌표 시스템에 기반을 둔 정보에 대해서는 모두 적용할 수 있습니다.

R-Tree는 각도형의 포함관계를 이용해서 만들어진 인덱스입니다. 따라서 Contains() 또는 Intersect() 등과 같이 포함 관계를 비교하는 함수로 검색을 수행하는 경우에만 인덱스를 이용할 수 있습니다. 대표적으로는 "현재 사용자의 위치로부터 반경 5Km 이내의 음식점 검색" 등과 같은 검색에 사용할 수 있습니다. 현재 출시되는 버전의 MySQL에서는 거리를 비교하는 Distance() 함수를 지원하지 않으므로 Contains()나 Intersect()를 이용해 거리기반의 비교를 사용합니다.

위에서는 빨간점이 기준점이 된다. 기준점으로부터 특정거리 이내의 점들을 검색하려면 원의 MBR에 포함되는 점들을 검색하면 됩니다. 여기서 Contains()나 Intersect() 연산은 사각형 박스와 같은 다각형(Polygon)으로만 연산할 수 있으므로 특정거리 반경을 그리는 원을 포함하는 최소 사각형으로 포함 관계를 비교 수행하게 됩니다. 만약 두번째 첨부된 그림내 Extra area included in collision zone - creates errors, invalid collision 영역의 점들을 제외하고 결과를 조회하려면 조금 더 복잡한 비교가 필요하게 됩니다.

SELECT * FROM tb_location
WHERE CONTAINS(Px, 사각상자);    -- // 공간 좌표 Px가 사각 상자에 포함되는지 비교.

Collision zone 안의 점을 제외하고 싶다면 다음과 같이 Contains() 비교의 결과를 다시 한번 필터링해야 합니다. 물론 MySQL에서는 아직 Distance() 함수를 제공하지 않으므로 거기를 계산하는 함수를 직접 구현해야 합니다.

SELECT * FROM tb_location
WHERE CONTAINS(px, 사각상자) -- // 공간 좌표 Px가 사각 상자에 포함되는지 비교
    AND DISTNACE(p, px) <= 5km;

Fractal-Tree 인덱스

---

인터넷이 발전하면서 데이터의 양이 급증하고 있는데, 하드웨어의 성능은 그만큼 따라가지 못하는 것이 현실입니다. 기계식 장치에 데이터를 저장하고 있는 이상 그 처리 성능은 제한적일 수밖에 없습니다. 더구나 최근에는 SNS 서비스까지 가세하면서, 기존의 데이터 증가량은 사용자 수에 비례했다면 최근의 데이터 증가량은 사용자 수의 곱으로 증가하는 추세입니다. 하드웨어뿐 아니라 DBMS의 B-Tree 인덱스 알고리즘 또한 한계에 도달한 것으로 보입니다. 특히 B-Tree 인덱스 알고리즘은 대략 40여년 전에 고안된 알고리즘이라는 것을 고려하면 Fractal-Tree가 지금의 데이터에 맞는 인덱스 알고리즘일 가능성이 더 높습니다.

Fractal-Tree는 아주 최근에 개발된 기술인데, 독점적인 특허로 등록된 알고리즘이어서 아직 많은 DBMS에 구현되지 못하고 있습니다.

Fractal-Tree의 특성

B-Tree 인덱스에서 인덱스 키를 검색하거나 변경하는 과정 중에 발생하는 가장 큰 문제는 디스크의 랜덤 I/O가 상대적으로 많이 필요하다는 것입니다. Fractal-Tree는 이러한 B-Tree의 단점을 최소화하고, 이를 순차 I/O로 변환해서 처리할 수 있다는 것이 가장 큰 장점입니다. 그래서 Fractal-Tree를 스트리밍(Streaming) B-Tree라고도 합니다. Fractal-Tree는 인덱스 키가 추가되거나 삭제될 때 B-Tree인덱스보다 더 많은 정렬 작업이 필요하며, 이 때문에 더 많은 CPU 처리가 필요할지도 모릅니다. 하지만 인덱스의 단편화가 발생하지 않도록 구성할 수 있고, 인덱스 키값을 클러스터링하기 때문에 B-Tree보다는 대용량 테이블에서 높은 성능을 보장합니다. 또한 B-Tree 인덱스는 일정 수준을 넘어서면 급격한 성능 저하가 발생하는데, Fractal-Tree는 이런 급격한 성능 저하 현상이 없습니다.

오랜 시간 동안 데이터가 변경되면서 단편화가 발생하고, 그 때문에 인덱스의 효율이 떨어지는 현상을 에이징(Aging)이라고 합니다. 이러한 현상 때문에 테이블이나 인덱스 최적화(옵티마이즈)하는데 Fractal-Tree에서는 이러한 현상이 발생하지 않기 때문에 별도의 최적화 작업이 필요하지 않습니다.

위 그림에서도 알 수 있듯이, Fractal Tree를 사용하는 TokuDB의 경우에는 InnoDB와 같은 급격한 성능 저하 현상이 나타나지 않습니다. InnoDB의 성능이 급격하게 떨어지는 시기는 아마도 InnoDB 버퍼풀 보다 데이터와 인덱스의 크기가 커지면서 본격적으로 CPU 바운 작업에서 IO 바운드 작업으로 넘어가는 시점일 것입니다.

레코드 건수가 많아질수록 InnoDB의 B-Tree보다는 TokuDB의 Fractal-Tree가 빠르게 반응합니다. 한편, TokuDB는 InnoDB보다 동시 처리 능력이 훨씬 떨어지는 상태입니다. 만약 많은 스레드로 복합적인 성능을 테스트했다면 Fractal-Tree를 사용하는 TokuDB의 성능은 훨씬 낮게 나오게 됩니다. 하지만 이는 TokuDB 스토리지 엔진의 문제이지 Fractal-Tree 자체의 문제는 아닙니다. Fractal-Tree의 편귱적인 처리 능력은 이론적으로 B-Tree보다 400배 가량 빠르며, 실제로도 TokuDB의 키 추가 및 삭제 작업은 InnoDB보다 100배 가량 빠른 처리속도를 보여줍니다.

Fractal-Tree의 가용성과 효율성

Fractal-Tree의 또 다른 장점은 B-Tree의 장점을 그대로 Fractal-Tree도 가지고 있다는 것입니다. 그래서 현재 B-Tree로 생성된 인덱스를 Fractal-Tree로 변경해도 충분히 동일한 효과를 얻을 수 있습니다. 또한 B-Tree에서 인덱스를 효율적으로 사용하지 못하는 쿼리는 Fractal-Tree에서 적용되더라도 같은 결과를 보인다고 할 수 있습니다. B-Tree를 Fractal-Tree로 변환하더라도 별도의 추가 학습이 필요하지 않습니다.

지금의 TokuDB는 동시성이 떨어지기 때문에 웹서비스와 같은 OLTP 환경에는 아직 적용하기에 무리가 있습니다. 하지만 OLAP이나 DW와 같은 대용량 분석 시스템에는 상당히 적합할 것으로 보입니다.

출처: https://12bme.tistory.com/143?category=682920 [길은 가면, 뒤에 있다.]