Datalog 엔진을 구현하다 보면 성능 병목을 해결하기 위해 다양한 최적화 기법을 도입하게 됩니다. 특히 다량의 데이터를 처리해야 하는 데이터베이스나 논리 프로그래밍 엔진에서는 어떤 정렬 알고리즘을 선택하느냐에 따라 전체적인 성능 차이가 극명하게 나타날 수 있습니다.

이번 글에서는 기수 정렬(Radix Sort)의 기본 개념에 대해 알아보고, 왜 Datalog 엔진에서 정렬 알고리즘이 필수적인지, 그리고 기존의 qsort에서 Radix Sort로 전환하여 어떤 성능적 이점을 기대하고 있는지 정리해 보았습니다.

기수 정렬 (Radix Sort)이란?

기수 정렬(Radix Sort)은 요소를 비교하지 않고 분산(Distribution)하여 정렬하는 알고리즘입니다. 일반적인 비교 기반 정렬 알고리즘(예: Quick Sort, Merge Sort)이 최소 $O(N \log N)$의 시간 복잡도를 가지는 반면, 기수 정렬은 정렬할 키의 크기가 제한적일 때 $O(dN)$ (이때 $d$는 데이터의 최대 자릿수)의 선형 시간에 가까운 속도로 정렬을 완료할 수 있습니다.

작동 방식

기수 정렬은 데이터의 가장 낮은 자릿수(LSD, Least Significant Digit)부터 가장 높은 자릿수(MSD, Most Significant Digit)까지, 혹은 그 반대로 각 자릿수를 기준으로 정렬을 반복합니다.

1. 초기화: 0부터 9까지(혹은 진법에 따른 기수만큼)의 버킷(Queue 등)을 준비합니다.
2. 분배: 정렬할 데이터의 일의 자리를 기준으로 각 버킷에 데이터를 넣습니다.
3. 병합: 0번 버킷부터 순서대로 데이터를 다시 가져옵니다.
4. 반복: 십의 자리, 백의 자리 등 가장 큰 자릿수까지 위 과정을 반복합니다.

이렇게 요소 간의 직접적인 크기 비교 없이 자릿수 기반의 버킷 배치를 통해 정렬을 수행하기 때문에, 정수나 문자열 같은 일정한 형식의 키를 가진 데이터를 정렬할 때 매우 강력한 성능을 발휘합니다.

Datalog 엔진 구현에서 정렬이 필요한 이유

Datalog는 선언형 논리 프로그래밍 언어로, 사실(Fact)과 규칙(Rule)을 기반으로 새로운 사실을 추론해 냅니다. 엔진 내부에서는 이러한 추론 과정이 주로 관계형 대수(Relational Algebra) 연산으로 변환되어 실행됩니다.

Datalog 엔진에서 데이터를 정렬해야 하는 주된 이유는 다음과 같습니다.

1. 중복 제거 (Deduplication) Datalog의 평가 과정(특히 Bottom-up 방식의 Semi-naïve Evaluation)에서는 매 반복마다 새롭게 생성된 데이터(Fact) 중에서 기존의 데이터와 겹치는 중복을 제거해야 합니다. 데이터가 정렬되어 있다면 선형 탐색 한 번만으로 중복된 튜플을 쉽게 걸러낼 수 있습니다.

2. 조인 연산 (Join) 보통 하나의 Rule은 여러 개의 Predicate(조건)가 엮여 있으며, 이를 모두 만족하는 해를 찾기 위해 조인 연산이 연속해서 일어납니다. 해시 조인(Hash Join)을 사용할 수도 있지만, 메모리 사용량을 예측 가능하게 유지하면서 높은 성능을 내기 위해 정렬 병합 조인(Sort-Merge Join)이 자주 활용됩니다. 데이터를 조인 키 기준으로 미리 정렬해두면 조인 처리가 매우 효율적입니다.

결과적으로 Datalog 엔진에서 데이터를 릴레이션 형태로 보관하고 연산할 때, 빠른 정렬은 엔진의 핵심 성능을 좌우하는 중요한 요소입니다.

QSort에서 Radix Sort로의 전환: 캐시 히트율 향상을 향한 기대

초기 Datalog 엔진(wirelog) 구현에서는 라이브러리에서 기본 제공하는 퀵 정렬(qsort 또는 std::sort)을 사용해왔습니다. Quick Sort는 평균적으로 $O(N \log N)$의 우수한 시간 복잡도를 가지며 범용적으로 가장 널리 쓰이는 정렬 방식입니다.

하지만 처리해야 할 일의 양과 사실(Fact) 데이터의 개수가 기하급수적으로 늘어나면서 Quick Sort의 한계가 나타나기 시작했습니다. 가장 큰 문제는 바로 캐시 히트율(Cache Hit Rate) 이었습니다.

Quick Sort는 피벗(Pivot)을 기준으로 배열의 양 끝에서부터 스왑(Swap) 연산을 수행하면서 재귀적으로 범위를 좁혀 들어갑니다. 데이터가 커져서 한 번에 CPU 캐시에 담을 수 있는 크기를 넘어서게 되면 메모리 접근 패턴은 무작위(Random)에 가까워집니다. 이로 인해 심각한 Cache Miss가 발생하기 시작하고, 결국 CPU 연산 시간보다 메모리에서 데이터를 퍼오는 데 걸리는 대기 시간이 정렬 연산의 병목이 됩니다.

반면, Radix Sort는 데이터를 버킷에 순차적으로 분배하고 다시 순차적으로 거두어들이는 패턴을 가집니다. 특히 데이터 엔진에서 주로 다루는 고정 크기의 정수형 키를 정렬할 때, 메모리에 대해서 연속적이고 예측 가능한 접근(Sequential Memory Access) 을 가능하게 합니다.

이러한 특성 덕분에 하드웨어 프리패처(Hardware Prefetcher) 동작에 매우 유리하며 다음 메모리 블록을 미리 캐시에 올려둘 수 있어, 결과적으로 캐시 히트율이 획기적으로 상승합니다.

마무리

현재 Datalog 엔진의 핵심 병목 중 하나였던 대용량 튜플의 정렬 단계를 기존의 qsort에서 Radix Sort 기반으로 교체하는 작업을 진행하고 있습니다(관련 이슈: justinjoy/wirelog#308). 연산 복잡도 자체의 감소($O(N \log N) \rightarrow O(dN)$)도 의미가 있지만, 무엇보다 메모리 계층 구조에 친화적인(Cache-friendly) 특성 덕분에 실제 하드웨어 최우선 과제인 캐시 히트율을 대폭 향상시켜 훨씬 더 빠른 쿼리 응답 속도를 얻을 수 있을 것으로 기대하고 있습니다. 향후 최적화가 완료되면 벤치마킹을 통해 얼마나 속도가 개선되었는지 다시 정리해 보도록 하겠습니다.