공간 데이터 성능 최적화: Z-order Indexing (feat. 캐시, 압축, I/O)
들어가기에 앞서
좌측 그림은 데이터를 메모리에 선형적(Row-Major)으로 저장, 탐색하는 방식,
우측 그림은 Z-order 기반으로 정사각형 블록 단위로 저장, 탐색하는 방식입니다.
이 두 가지 방식의 차이가 공간 데이터 처리 성능에 어떤 영향을 미치는지 살펴보겠습니다.
현대의 지도 서비스, 자율주행 시뮬레이션, 지리 정보 시스템(GIS) 등은 방대한 공간 데이터를 실시간으로 탐색하고 처리해야 합니다.
하지만 이러한 데이터를 단순히 행렬 순서(예: Row-Major)로 저장하면, 지리적으로 가까운 두 점이 메모리 상에서는 멀리 떨어져 저장될 수 있습니다. 이는 CPU 캐시 효율을 낮추고 데이터 접근 성능을 저하시키는 주된 원인이 됩니다.
이러한 문제를 해결하는 대표적인 방식이 Z-order Indexing입니다.
목차
- 공간 데이터의 일반적 특성 – Z-order가 필요한 이유
- Z-order 개요 및 정의
- Z-order의 이점: 캐시 효율, 압축률, 탐색 성능 향상
- Z-order Index 계산 방식 – 비트 교차(Bit Interleaving)
- 요약
- 참고 자료
1. 공간 데이터의 일반적 특성 – Z-order가 필요한 이유
공간 정보(Spatial Data)는 위치나 영역과 관련된 데이터를 의미하며, 일반적으로 다음과 같은 특징을 가집니다.
- 공간적 지역성(Spatial Locality): 인접한 위치의 데이터는 유사한 특성을 가질 확률이 높습니다. 예를 들어, 서울 내의 데이터는 고층 빌딩, 도로 등 도시적 특성을 공유할 가능성이 크며, 논밭과 같은 농업 지형은 나타나지 않습니다.
- 대용량성(Large Volume): 광범위한 지역, 고해상도 데이터일수록 데이터 양이 기하급수적으로 증가합니다.
- 다차원성(Multi-dimensionality): 공간 데이터는 주로 2차원(위도, 경도) 또는 3차원(위도, 경도, 고도) 좌표계를 사용합니다. 일반적인 데이터베이스의 1차원 정렬(예: 숫자, 문자열)에 비해, 다차원 데이터를 효율적으로 저장·검색하기 어렵습니다. 예를 들어 복합 인덱스 (경도, 위도)를 사용하더라도 경도 검색은 빠르지만 위도 범위가 넓어지면 성능이 급격히 저하됩니다. 이는 다차원 공간을 1차원으로 효율적으로 매핑하기 어려운 구조적 한계 때문입니다.
이러한 특성 때문에 공간 데이터를 단순히 배열이나 일반적인 인덱스 구조로 처리하면 비효율적입니다. 특히, 메모리에 데이터를 저장하는 가장 기본적인 방식인 Row-Major(행 우선) 방식은 공간 데이터의 특성과 충돌하여 다음과 같은 문제들을 발생시킬 수 있습니다.
- 캐시 비효율 (Cache Miss 증가): 기본적인 메모리 저장 방식인 Row-Major (행 우선) 방식은 데이터가 저장된 순서가 지리적 순서와 무관합니다. 이로 인해 지리적으로 인접한 데이터가 메모리에서는 멀리 떨어져 저장되고, 이로 인해 캐시 미스가 증가하여 처리 속도가 느려집니다.
- 데이터 압축률 저하: 지리적으로 가까운 데이터는 유사한 패턴을 가질 가능성이 높지만, Row-Major 방식에서는 이 데이터들이 메모리 상에 흩어져 저장됩니다. 이로 인해 압축 알고리즘이 패턴을 제대로 찾지 못해 압축 효율이 떨어지고, 저장 공간이 낭비되며 전송 속도도 느려질 수 있습니다.
- 범위 검색 시 느린 탐색: 일반적인 데이터베이스 시스템은 1차원적인 SELECT * FROM table WHERE id BETWEEN 100 AND 200과 같은 쿼리(일반적인 트랜잭션 요청)에 최적화되어 있습니다. 하지만 공간 데이터는 위도, 경도, 또는 {X, Y, Z}와 같은 3차원 좌표로 표현되는 다차원적인 속성을 가집니다. SELECT * FROM map_data WHERE latitude BETWEEN 30 AND 35 AND longitude BETWEEN 120 AND 125와 같이 특정 영역(사각형 블록 등)에 해당하는 데이터를 찾는 다차원 범위 검색을 수행할 때, 데이터가 공간적 위치와 무관하게 저장되어 있다면 데이터베이스는 전체 데이터를 스캔(Full Table Scan)하거나 비효율적인 인덱스 탐색을 수행해야 할 수도 있습니다. 이는 시간과 자원 낭비로 이어집니다.
따라서 이러한 문제들을 해결하고 공간적 근접성을 유지하면서도 1차원으로 효율적인 정렬이 가능한 인덱싱 방식이 필요하며, 그 대표적인 방식이 바로 Z-order (Morton Order) 입니다.
2. Z-order 개요 및 정의
Z-order (Z-curve)는 2차원 또는 3차원 좌표를 1차원 공간으로 변환하면서도 공간적 인접성을 최대한 보존하는 정렬 방식입니다.
각 좌표는 Z자 형태로 인덱스가 부여되며, 이를 Z-order Index 또는 Morton Order라고 부릅니다. 이 방식은 계층적인 구조를 가지는데, 큰 Z-블록 안에는 더 작은 Z-블록들이 포함됩니다.
예를 들어, 4x4 그리드에서 (0,1)부터 시작하면 Z-자 경로를 따라 인덱스가 부여됩니다.
참고: 현재는 (0,0) 부터 시작하여 z가 축회전 된 모습 (단순 시작점의 차이)
3. Z-order의 이점
Z-order는 단순히 다차원 데이터를 1차원으로 정렬하는 것을 넘어, 시스템 성능에 직접적인 영향을 주는 다양한 최적화 효과를 제공합니다.
- 캐시 효율 향상
- 압축률 향상
- 디스크 I/O 감소 및 탐색 성능 향상
1. 캐시 효율 향상
- 선형 접근 방식(Row-Major): 데이터를 행 순서대로 순차적으로 접근합니다. 이 방식은 지리적으로 가까운 두 점이 메모리 상에서 멀리 떨어져 있을 수 있어, 특정 셀을 찾기 위해 불필요한 데이터까지 메모리에 로드하게 됩니다. 이는 캐시 미스를 유발하고 성능 저하로 이어집니다.
- 정사각형 블록 접근 방식(Z-order 기반): Z-order는 공간적으로 인접한 데이터를 메모리 상에서도 인접하게 저장합니다. 이는 마치 지도에서 우리 동네 블록만 확대해서 보는 방식과 유사합니다. 필요한 메모리 영역만 최소한으로 접근하므로 캐시 라인(Cache Line)에 필요한 데이터가 효율적으로 적재되어 CPU 캐시 미스를 줄이고 처리 속도를 높일 수 있습니다.
📌 예시: 지도 데이터를 Z-order로 정렬할 경우, 화면에 보이는 인접한 지형 정보를 캐시 단위로 효율적으로 로드할 수 있습니다. 사용자가 지도를 확대하거나 이동할 때, 필요한 데이터가 이미 캐시에 있거나, 캐시에서 빠르게 가져올 수 있어 부드러운 화면 전환이 가능합니다.
2. 압축률 향상
Z-order는 비슷한 위치에 있는 데이터(예: 같은 건물 영역의 정보, 비슷한 색상의 픽셀 데이터 등)를 메모리에 연속적으로 저장합니다.
- 연속적인 유사 데이터: 공간적 지역성 덕분에 인접한 데이터는 유사한 값을 가질 확률이 높습니다. 예를 들어, 한 건물의 모든 층에 대한 데이터는 비슷한 속성을 가질 것입니다.
- 압축 알고리즘의 효과: RLE(Run-Length Encoding)나 ZSTD와 같은 압축 알고리즘은 반복되거나 유사한 데이터 블록에서 높은 압축률을 보입니다. Z-order로 정렬된 데이터는 이러한 특성을 잘 만족시키므로 자연스럽게 압축률이 향상됩니다.
📌 예시: 빨간색 데이터 주변에는 보라색보다는 주황색처럼 RGB 값이 가까운 색상이 등장할 확률이 높기 때문에, 이러한 공간적 인접성과 색상의 유사성을 이용해 더 효율적인 압축이 가능합니다. 이는 저장 공간을 절약할 뿐만 아니라, 데이터를 전송하는 시간도 단축시킵니다.
3. 디스크 I/O 감소 및 탐색 성능 향상
디스크 I/O(Input/Output)는 데이터를 디스크에서 읽거나 쓰는 작업을 의미하며, 이는 시스템 성능에 큰 병목 현상을 일으킬 수 있습니다. 특히 무작위 접근(Random Seek)은 디스크 헤드가 여러 위치로 이동해야 하므로 매우 느립니다. 반면, 순차 접근(Sequential Read)은 헤드가 한 방향으로 계속 이동하므로 빠르고 효율적입니다.
- 연속된 블록 저장: Z-order는 공간적으로 가까운 데이터를 디스크의 연속된 블록에 저장합니다.
- 순차 접근 극대화: 특정 지역만 탐색할 때도 디스크에서 연속된 범위만 읽으면 되므로, 무작위 접근을 줄이고 순차 접근을 극대화할 수 있습니다. 이는 HDD나 SSD에서 데이터 읽기 성능을 크게 향상시킵니다.
📌 예시: 지도 애플리케이션에서 사용자가 '제주도' 지역만 렌더링하고 싶다고 가정해 봅시다. Z-order로 인덱싱된 데이터베이스에서는 제주도 지역에 해당하는 Z-order 인덱스 범위가 메모리상에 일련으로 저장되어 있습니다. 따라서 시스템은 제주도와 관련된 데이터 블록만 순차적으로 읽고, 나머지 불필요한 데이터는 건너뛸 수 있습니다. 이는 디스크 I/O를 줄여 시스템의 전반적인 반응 속도를 향상시킵니다.
4. Z-order Index 계산 방식 – 비트 교차(Bit Interleaving)
Z-order를 사용하려면 2차원 또는 3차원 좌표를 1차원 좌표인 Z-order Index로 변환하는 과정이 필요합니다.
이 변환하는 방식은 비트 교차(Bit Interleaving)라고 불립니다.
Bit Interleaving이란?
좌표 (x, y)의 이진 표현에서, 각 비트를 한 비트씩 교차(interleave)하여 새로운 정수를 만드는 방식입니다.
예를 들어 (x=5, y=7)은 다음과 같이 계산됩니다.
x = 101(2)
y = 111(2)
⚠️ 주의 사항: 비트 추출은 반드시 최하위 비트(LSB: Least Significant Bit)부터 시작해야 올바른 Z-order Index가 생성됩니다. Z-order Index는 비트가 교차되는 순서에 따라 값이 결정되므로, LSB부터 처리하여 낮은 차원의 비트가 낮은 자리수를 차지하도록 해야 합니다.
실제로 8x8 그리드에서 좌표(5, 7)의 Morton Order값이 59입니다.
실제로 8x8 그리드에서 좌표(5, 7)의 Morton Order값이 59입니다.
Bit Interleaving 코드 예시
uint result = 0;
for (int i = 0; i < 32; i++) { // 32비트 정수를 가정 (좌표값이 0부터 2^32-1까지 가능)
uint xBit = (x >> i) & 1; // x의 i번째 비트 추출
uint yBit = (y >> i) & 1; // y의 i번째 비트 추출
result |= (xBit << (2 * i)); // x의 비트를 짝수 자리에 삽입 (0, 2, 4...)
result |= (yBit << (2 * i + 1)); // y의 비트를 홀수 자리에 삽입 (1, 3, 5...)
}
5. 요약
Z-order (Morton Order)는 2차원 또는 3차원 공간 데이터를 1차원으로 정렬하면서도, 공간적으로 가까운 데이터끼리 인접하게 유지해주는 강력한 인덱싱 방식입니다. 이는 단순한 정렬 기법처럼 보일 수 있지만, 대규모 공간 데이터를 다룰 때 시스템 성능에 핵심적인 영향을 미칩니다.
공간 데이터는 일반적으로 다음과 같은 특징을 가집니다.
- 공간적 지역성: 인접한 위치일수록 유사한 값을 가집니다.
- 다차원성: 2D 또는 3D 좌표계를 기반으로 표현됩니다.
- 대용량성: 광범위한 영역을 다루므로 데이터 양이 방대합니다.
이러한 특성으로 인해 일반적인 행렬 순서(Row-Major)나 단순 인덱스 방식으로는 캐시 효율이 떨어지고, 압축률이 낮아지며, 범위 검색 속도 또한 느려질 수 있습니다.
이 문제를 해결하기 위한 방식이 바로 Z-order입니다. Z-order는 공간 데이터를 Z자 형태로 순회하며 1차원으로 정렬하되, 인접한 공간 데이터를 메모리 상에서도 가깝게 배치합니다. 이 덕분에 다음과 같은 장점을 가집니다.
- 첫째, 캐시 효율이 크게 향상됩니다. 선형 정렬에서는 특정 위치를 조회할 때 필요 없는 데이터까지 불필요하게 메모리에 로딩되지만, Z-order 방식에서는 필요한 지역만 좁고 깊게 접근할 수 있어 CPU 캐시 미스를 줄이고 전체 속도를 높일 수 있습니다.
- 둘째, 압축률이 높아집니다. 비슷한 위치에 있는 데이터는 대개 유사한 값을 가지기 때문에, 연속적으로 저장될 경우 RLE나 ZSTD와 같은 압축 알고리즘이 효율적으로 작동합니다. 이는 저장 공간을 절약하고 데이터 전송 속도도 높여줍니다.
- 셋째, 탐색 성능이 향상됩니다. Z-order는 인접한 데이터를 연속된 블록에 저장하기 때문에, 특정 지역만 탐색할 때 디스크나 SSD에서 순차 접근이 가능해지고, 무작위 접근을 줄일 수 있습니다. 실제로 지도에서 '서울' 지역을 조회할 때, 서울에 해당하는 Z-order 인덱스 범위만 빠르게 읽어오는 식으로 탐색이 최적화됩니다.
Z-order 인덱스는 좌표의 비트를 교차해서 만드는 비트 교차(Bit Interleaving) 방식을 통해 계산됩니다. 예를 들어, X와 Y 좌표의 이진수 비트를 한 자리씩 교차하여 새로운 정수로 만드는 방식입니다. 이 계산은 최하위 비트(LSB)부터 시작해야 정확한 순서를 보장할 수 있습니다.
결과적으로 Z-order는 단순한 정렬 이상으로, 대규모 공간 데이터 처리 시스템에서 캐시 성능, 압축률, 디스크 I/O 효율까지 향상시켜주는 핵심적인 기술이라고 할 수 있습니다.