Beyond Traditional Search: SIMD-Optimized Correction for Learned Index

기계 학습 기반의 Learned Index는 전통적 인덱스 기법의 한계를 극복하기 위해 등장했다. 본 논문에서는 읽기 전용 RMI와 수정 가능한 ALEX의 탐색 성능을 분석하고, 오차 보정 과정에서 발생하는 오버헤드를 줄이기 위한 SIMD 기반 최적화 기법을 제안한다. Learned Index는 키의 분포를 학습해 예측과 오차 보정의 두 단계로 탐색을 수행하는데, 오차 보정이 전체 탐색 시간의 최대 80%를 차지할 수 있음이 확인되었다. RMI에서는 오차가 클 때 탐색 범위를 빠르게 줄이는 SIMD Branchless Binary Search, 작을 때 모델 예측 기반의 SIMD Linear Search가 효과적이었다. 반면, ALEX는 일정한 오차 범위를 유지하는 특성으로 인해 단순한 SIMD Linear Search가 가장 효율적이었다. 이를 통해 데이터셋의 오차 범위, 인덱스 크기 및 밀도에 따라 적절한 탐색 알고리즘을 선택하는 것이 성능 최적화에 중요함을 제시한다.