Minguk Choi

By embedding the distribution of keys in indexing structure, learned indexes can minimize the index size and maximize the lookup performance. Yet, one of the problems in the present learned index is the long index-building time. The conventional learned index requires a complete traversal of the entire dataset, which makes it less practical than traditional index. This paper challenges the efficiency of build time to make the learned index practical. Our approach for a build time-efficient learned index is to employ sampled learning. In this paper, we present two error-bounded sampling schemes: Sample EB-PLA, and Sample EB-Histogram. Although sampling is a simple idea, there are several considerations to make it practical. For example, sampling interval, errorboundness, and index hyper-parameters are inter-related each other, presenting complicated trade-offs between build-time, index size, accuracy and lookup latency. Throughout the extensive experiments over six real-world datasets, we show that the index-building time can be efficiently reduced over an order of magnitude by our sampling schemes. The results reveal that the sampling expands the design space of learned indexes, including the build-time as well as lookup performance and index size. Our Pareto analysis shows that a learned index can be built more efficiently than a traditional index through sampling.

The purpose of this paper is proposing a novel search mechanism, called SLR (Segmented Linear Regression) search, based on the concept of learned index. It is motivated by our observation that a lot of big data, collected and used by previous studies, have a linearity property, meaning that keys and their stored locations show a strong linear correlation. This observation leads us to design SLR search where we apply segmentation into the well-known machine learning algorithm, linear regression, for identifying a location from a given key. We devise two segmentation techniques, equal-size and error-aware, with the consideration of both prediction accuracy and segmentation overhead. We implement our proposal in LevelDB, Google’s key-value store, and verify that it can improve search performance by up to 12.7%. In addition, we find that the equal-size technique provides efficiency in training while the error-aware one is tolerable to noisy data.

데이터의 양 증가에 따라 발생한 전통적인 인덱스의 크기 문제를 해결하기 위해 Learned Index 기법이 제 안회었다. 대표적인 읽기 전용 Learned Index인 RMI(Recursive Model Indexes)는 여러 계층에서 데이터 구 간을 세분화한 구조를 가진다. RMI에서 키 탐색은 여러 계층의 모델을 거쳐 위치를 결정하고 미리 측정한 오 차범위를 탐색하여 최종 위치에 접근하는 과정을 가진다. RMI의 오차범위 탐색은 모델 예측과 비슷한 오버헤 드를 가진다는 단점이 있다. 본 논문에서는 RMI의 오차범위 탐색 성능을 개선하기 위해 Branchless Binary Search와 SIMD(Single Instruction Multiple Data) Linear Search 기법을 적용하여 탐색 지연 시간을 최대 1.73, 2.97배 감소시켰다. (To address the size issues of traditional indexes caused by the increase in data volume, the Learned Index technique was proposed. A representative read-only Learned Index, RMI (Recursive Model Indexes), has a structure that segments data ranges across multiple layers. In RMI, key retrieval involves determining the position through several layers of models and accessing the final position by searching within a pre-measured error range. However, the error range search in RMI has a drawback of having an overhead similar to model prediction. In this paper, we apply Branchless Binary Search and SIMD (Single Instruction Multiple Data) Linear Search techniques to improve the error range search performance of RMI, reducing the search latency by up to 1.73 and 2.97 times, respectively)

본 논문에서는 updatable learned index의 공정한 비교를 위해 메모리 사용 정책이 다른 두 인덱스 ALEX와 LIPP를 분석하여 인덱스 크기를 비슷하게 사용할 때의 성능을 비교한다. 또한, 키 삽입 시에 발생하는 과정을 탐색과 삽입으로 구분하여 내부 작업을 분석함으로써 워크로드에 따른 성능 병목 원인을 분석한다. (In this paper, we conduct a fair comparison of updatable learned indexes by analyzing two indexes with different memory usage policies, ALEX and LIPP, and compare their performance when the index sizes are similar. Additionally, we differentiate the processes that occur during key insertion into search and insertion operations, and analyze the internal tasks to identify the performance bottlenecks according to the workload.)