오여진  김나경  최종무  유시환

10.5626/JOK.2025.52.5.363

학습된 인덱스 회기적 모델 인덱스 적응적 학습된 인덱스 탐색 알고리즘 SIMD 선형 탐색 이진 탐색 모델 예측 기반 탐색

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