Learned Adaptive Indexing CCS: Information systems Data access methods CCS: Information systems Database query processing Suvam Kumar Das and Suprio Ray Abstract . Indexes can significantly improve search performance in relational databases. However, if the query workload changes frequently or new data updates occur continuously, it may not be worthwhile to build a conventional index upfront for query processing. Adaptive indexing is a technique in which an index gets built on the fly as a byproduct of query processing. In recent years, research in database indexing has taken a new direction where machine learning models are employed for the purpose of indexing. These indexes, known as learned indexes , can be more efficient compared to traditional indexes such as B+-tree in terms of memory footprints and query performance. However, a learned index has to be constructed upfront and requires training the model in advance, which becomes a challenge in dynamic situations when workload changes frequently. To the best of our knowledge, no learned indexes exist yet for adaptive indexing. We propose a novel learned approach for adaptive indexing. It is built on the fly as queries are submitted and utilizes learned models for indexing data. To enhance query performance, we employ a query workload prediction technique that makes future workload projection based on past workload data. We have evaluated our learned adaptive indexing approach against existing adaptive indexes for various query workloads. Our results show that our approach performs better than others in most cases, offering 1.2 × \times – 5.6 × \times improvement in query performance. 1. Introduction Indexes in a data system enhance data retrieval speed, improve performance, and ensure data consistency. Although an index incurs additional storage overhead, with its help the data system can quickly narrow down the data it needs to process a query , thus reducing the number of disk accesses and improving query performance. In relational databases, for decades, B+-tree ( B+-tree ) has been a dominant approach for indexing and answering range searches. This structure is able to retrieve the position of a sorted key in logarithmic time with respect to the total number of keys , but requires the storage of all keys as part of the index organization. Hash-based indexes ( Extendible_hashing ) are very effective in answering equality searches in almost constant time. Indexes such as Bloom Filters ( Bloom_filter ) can efficiently check the existence of a record. Traditional indexes, such as the B+-tree are constructed prior to query execution and they require scanning the entire dataset once during the index construction. But in some scenarios, the queries may be localized to a specific portion of a dataset, or the workload is dynamic and the dataset keeps on changing due to continuous data updates. In these situations, it may not be worthwhile to create an index on the entire dataset in a database table . Rather, indexes are built on the fly as a by product of query execution. Once a sufficient number of queries are executed, an index on the complete dataset is built as part of the query execution. This is known as adaptive indexing . Some of the indexes built on this concept are database cracking ( Stochastic_database_cracking ; Database_Cracking ) and adaptive merging ( Adaptive_Index_Relational_Keys_Adaptive_Merging ; Adaptive_Merging ) . In recent years, researchers have developed indexes that utilize learned models to predict the location of a key value by learning the distribution within the lookup keys. Learning based models leverage techniques such as Linear Regression ( FitingTree ) , Radix Spline Interpolation ( RadixSpline ) . They are trained on a subset of the lookup keys to “learn” the Cumulative Distribution Function . Then the model is used to predict the location given any key. This technique has been termed as a learned index ( LearnedIndex ) , and this can enhance or even replace traditional index structures due to its smaller memory footprint and better search performance. Learned index approaches, such as the FITing tree ( FitingTree ) and the PGM index ( PGM-Index ) have been developed based on this idea and have been shown to be superior to B+-trees in terms of storage space requirement and search time. Learned indexes have also been incorporated in other domains ( FLIRT ; LISA ; LIMS ) . However, a learned index needs to be built upfront and it incurs additional cost associated with training the learned model. This becomes a challenge for dynamic situations where, the dataset is frequently updated or becomes stale and needs discarded whenever new batch of data arrives. Hence, it may not be worthwhile to create a learned index upfront under these scenarios, as the time spent on creating the index on dynamic data could rather be used to answer thousands of user queries. On the other hand, to the best of our knowledge, no work has been done to incorporate the advantages of learned approaches for incremental construction of adaptive indexes yet, which could result in enhanced query performance compared to the present adaptive indexes. To address the limitations of existing approaches, we propose a novel Learned Adaptive Index (LAI) . LAI is general purpose and uses any learned index for its construction. Following the concepts of adaptive indexing, LAI is incrementally built as a by product of query execution. Each query tries to find all x in the dataset, such that x\in[l,h] , where l,h are the query boundaries. Unlike traditional learned indexes which creates an index on the entire dataset, in LAI a learned index gets created on a partition of the input dataset depending on the query ranges. As an advantage, LAI can maintain different types of learned indexes in different partitions, e.g. a FITing tree ( FitingTree ) on one partition and a PGM Index ( PGM-Index ) on another, creating an ensemble of learned indexes. This can prove to be beneficial, for instance, in situations where a specific portion of the dataset is updatable, leaving the rest of the data untouched. In such a situation LAI can maintain an updatable learned index such as ALEX ( ALEX ) for the updatable partition and static learned indexes such as RadixSpline ( RadixSpline ) for the other partitions. Learned indexes require the data to be sorted, but LAI also works for queries on unsorted data. We partition and reorganize the input data based on the query boundaries such that all the keys answering the query fall within a single partition. Depending on the partition size to sort, we toggle between traditional sorting and a Learned Sort technique similar to ( LearnedSort ) , which has been shown to enhance sorting time on large datasets. In enterprise data-driven applications, not all queries are submitted at the same time for execution. Rather, a set of queries are usually submitted within a particular time interval, which can be considered as a ‘batch’ of query workload. We employ a statistical forecasting technique for query workload prediction, to predict the future queries using the past queries. Since modern hardware supports many CPU cores, while a current batch of queries is still in execution, once a fixed number of queries are received, the forecasting process can be launched simultaneously, without affecting the overall system performance. Once the next batch of query is forecasted, our index is updated based on them. This enables automated and predictive index maintenance, where the next batch of query workload is predicted and the index is updated upfront for them only. This approach can be beneficial for workloads whose queries follow a pattern and are predictable based on the current queries. Therefore, LAI may be considered as an hybrid between traditional index such as B+-tree and adaptive index, where we predict and build the index upfront only for the next batch of queries. We have conducted extensive experimental evaluation to compare the performance of LAI against other adaptive indexes for various query workloads on a synthetic dataset of 100M keys. Our experiments show that LAI outperforms the other approaches for most of the workloads. We also demonstrate that with query workload prediction LAI achieves performance improvement of 5.2 \times –19.3 \times for some of the workloads, compared to the approach that do not use workload prediction. To summarize, the key contributions of the paper are: • We propose LAI that can integrate learned index with adaptive indexing. • We present a number of different query scenarios and show how LAI handles each of them. • We present a Learned Sort technique for LAI and based on the partition size to sort, we toggle between learned and traditional sorting to enhance overall sorting time. • We present a query workload prediction approach that can predict the next batch of queries from the past batch, update the index a priori for the predicted workload batch. • We conduct extensive experimental evaluation with a synthetic dataset of size 100M, by executing 10 (ten) different query workloads. The rest of the paper is organized as follow. In Section 2 we mention about the related work. Then in Section 3 we introduce LAI and give a brief description of all the query scenarios that can appear. Section 4 explains our approach and the algorithms in details. In Section 5 we explain how we incorporate Learned Sort in LAI . Section 6 mentions about query forecasting and updating our index on the fly . We discuss about our experimental evaluation in Section 7 and finally conclude in Section 8 . 2. Related Work In this section, the related work is presented in detail. Here, we divide the discussion into two parts, Learned Access Methods and Adaptive Indexes. 2.1. Learned Access Methods Here we look into the existing works done focusing on the usage of ML and interpolation techniques to create Learned Indexes and how these techniques are employed on the other paradigms of data analytics. 2.1.1. Learned Index Incorporating ML techniques to create database indexes has created a new avenue of research in query processing, known as Learned Indexes. Here ML models are trained to model the CDF of the dataset, which are then used for predicting the position of search keys in a sorted list. RMI ( LearnedIndex ) was the first learned index to be proposed, which is a hierarchical structure of neural networks. But this introduced space-time tradeoffs due to the complexity of the ML models adopted. To address this, FITing-Tree ( FitingTree ) was introduced that uses a simple linear model at the leaf level of a B+-tree index. Experimentally it was found that the FITing-tree improved the execution time performance of the B+-tree with a space saving of orders of magnitude. However, these indexes are built in static datasets and work for read-only workloads. Updates are not handled by these indexes. This limitation renders the Learned Index unusable for dynamic, read-write workloads, common in many use cases. To address this issue, researchers later proposed updatable learned indexes, such as ALEX ( ALEX ) and PGM-Index ( PGM-Index ) . Apart from point lookups, both these indexes support additional operations such as range queries, inserts, updates and deletes. Another limitation of RMI is that it cannot be constructed over a single pass of the input data, whereas ALEX and PGM can be. However, the complexity to insert an element in both of these indexes is logarithmic in the number of levels (similar to inserts in a B+-tree). But there are applications (e.g. LSM trees) where it is much more important to efficiently build the index. To address this researchers proposed RadixSpline (RS) ( RadixSpline ) , the first single-pass learned index with a constant complexity to insert each element. RS utilizes the spline-based interpolation method and it is not only efficient to build, but also competitive with state-of-the-art RMI models in size and lookup performance. The positions of the key values predicted by these models are not always precise and often requires a local search around the predicted position to find the key. This degrades the overall performance of the index. Recently, LIPP ( LIPP ) was developed, which trains the learned models for the entire data set and places the data at the predicted positions. When multiple data records are assigned to the same position, a new node is created at the position to hold them. This however, does not consider the data distribution of the keys and often results in long traversal paths. Later DIstribution-driven Learned Index tree (DILI) ( DILI ) , was proposed where a concise and computation-efficient linear regression model is used for each node. The indexes proposed so far only considered a single dimension, whereas queries often involve predicates spanning over multiple dimensions. To address this scenario, Flood ( Flood ) , the first learned multi-dimensional in-memory index, was introduced. But Flood was not very efficient in handling skewed query workloads and correlated data. To address this, the idea of Flood was extended to propose Tsunami ( Tsunami ) , an in-memory read-optimized learned multi-dimensional index for correlated data and skewed workloads. The indexes discussed so far were for single standalone systems. We developed a distributed learned index and a distributed partition-wise index join algorithm based on this index to answer join queries for DaskDB ( DaskDB ) , our novel scalable data science system, which supports unified data analytics and in situ SQL query processing on heterogeneous data sources. Inspired by the idea of learned indexes over columnar data, learned indexes were developed for other scenarios as well. FLIRT ( FLIRT ) and SWIX ( SWIX ) were proposed for sliding windows over data streams. A few learned indexes such as RSMI ( RSMI ) , LISA ( LISA ) , SPRIG ( SPRIG ) and IH-tree/IH-tree+/C-IH-tree+ ( IH-tree ) were proposed for spatial data. To incorporate learned methods in metric space indexing, LIMS ( LIMS ) and LMI ( LMI ) were proposed. 2.1.2. Learned Approaches In Other Paradigms Apart from creating indexes, ML techniques have been found to be useful in other aspects of data analytics as well. Using learned models in several well-known operations such as hashing, sorting and joins have been shown to be more effective than the traditional approaches. Under certain conditions (e.g. when keys are generated from a uniform random distribution), replacing hash functions with learned models achieve improvement in terms of hash collisions, hash table size, and probe latency while maintaining the compute efficiency almost the same ( Learned_Hashing ) . By approximating the emperical CDF of the keys, learned models can be utilized for sorting datasets, as shown in Learned Sort ( LearnedSort ) and PCF Learned Sort ( PCF_Learned_Sort ) . It has been shown that learned variants of Index Nested Loop Join and Sort-based Joins can outperform the state-of-the-art techniques by using CDF-based partitioning and learned indexes ( Learned_In_Memory_Joins ) . 2.2. Adaptive Indexes Adaptive indexing such as database cracking ( Stochastic_database_cracking ; Database_Cracking ) and adaptive merging ( Adaptive_Index_Relational_Keys_Adaptive_Merging ; Adaptive_Merging ) allow for building an index incrementally in response to queries, rather than building it upfront. Database cracking progressively partitions and sorts a column by quicksort while answering range queries. When a column is queried by a predicate for the first time, a new cracker index is created. As predicates of subsequent queries are applied on the column, the cracker index is refined by range partitioning until a minimum size is reached. The keys in a cracker index are partitioned into disjoint key ranges, but left unsorted within each key range. Each range query analyzes the cracker index, scans key ranges that fall entirely within the query range, and uses the two end points of the query range to further partition the appropriate two key ranges. While database cracking works as an incremental quick sort, adaptive merging functions as an incremental external merge sort on block-access devices such as disks, in addition to main memory. Under adaptive merging, the first query to use a given column in a predicate produces sorted runs, ideally stored in a partitioned B-tree, and subsequent queries upon that same column perform merge steps. Each merge step affects key ranges that are relevant to actual queries, avoiding any effort on all other key ranges. This merge logic executes as a side effect of query execution. Database cracking has a low initialization cost, but converges to a full index slowly, whereas adaptive merging has a relatively high initialization cost but converges rapidly. A hybrid combination of the two ( Adaptive_Indexing ) applying cracking on the initial partitions and sorting on the final one was proposed to achieve both lightweight initialization and quick convergence. These approaches blindly cracked the data space based on each query ranges thus failing in terms of workload robustness . Hence these approaches worked well with random queries, but faltered in scenarios when successive queries ask for consecutive items in the data space. To address this, researchers later proposed Stochastic Database Cracking ( Stochastic_database_cracking ) , where apart from the query region, the data space is also cracked at arbitrary positions. Instead of reorganizing the data space based on the queries only, this approach makes it partially query-driven and partially random. The authors proposed multiple techniques that are based on this approach, such as DDC , in which the array is recursively halved until the resulting piece is sufficiently small. Then it cracks this piece based on the query region only. However, this technique requires finding the median of a partition for optimal partitioning. As calculating median is expensive, in DDR , the array is cracked based on random pivots. These auxiliary operations incurs a considerable high overload for the first few queries. This is addressed by DD1C and DD1R , which are variants of DDC and DDR . They perform the auxiliary operations at most once. MDD1R works like DD1R , with the difference that it does not perform the final cracking step based on the query bounds. Instead, the qualified tuples are detected while cracking a data piece based on a random pivot and then they are materialized in a new array. AICC1R and AICS1R are variants of Crack-Crack (AICC) and Crack-Sort (AICS) methods ( Adaptive_Indexing ) . In addition to the cracking and partition/merge logic, they also incorporate DD1R-like stochastic cracking in one pass during query processing. 3. Our approach: Learned Adaptive Index Figure 1 . An illustration of LAI Inspired by the idea of learned indexes and the advantages in terms of storage consumption and query execution over the traditional indexes, we propose to integrate learned indexes with adaptive indexing. We call this approach Learned Adaptive Index (LAI) , which can efficiently process Range Queries . A Range Query is defined as follows. Definition 3.1 (Range Query). Given an array A (sorted or unsorted) and an interval [l,h] , find all x\in A , such that l\leq x\leq h . The basic concepts behind LAI are illustrated in Fig. 1 . Let A is an unsorted array, and a Range Query Q1 is submitted, where Q1:9\leq A\leq 13 . The idea is to crack A based on the query endpoints i.e. 9 and 13, such that three disjoint partitions P_{1},P_{2} and P_{3} are created where P_{1} contains all values <9 , P_{2} contains all values within the range [9,13] (marked in red), and finally P_{3} contains the rest of the values greater than 13 . As can be seen in the figure, P_{2} answers Q_{1} and thus the entire partition is returned to the user. This partition is then sorted using a standard sorting algorithm, and a learned index M_{1} is created on this partition. Finally, a tuple of the form (9,13,pos_{9},pos_{13},M_{1}) is stored in a 1-D Partition Table T , where pos_{9} and pos_{13} are the positions of 9 and 13 respectively in T . When another query Q_{2}:6\leq A\leq 19 is submitted, we scan T to identify that 6 lies in P_{1} whereas 19 belongs to P_{3} . It is easy to identify the start and end indexes of the partitions P_{1},P_{3} from T, since an entry in T stores both the key as well as its position in A . Next, we crack P_{1} based on 6 to find all elements \geq 6 and sort them (shown in green) to create a learned model M_{2} . Similarly we crack P_{3} based on 19 and find all keys \leq 19 and then sort them (shown in green) to create another learned model M_{3} . We find that the maximum element in P_{1} is 8 and the minimum in P_{3} is 14. We create two tuples of the form (6,8,pos_{6},pos_{8},M_{2}) and (14,19,pos_{14},pos_{19},M_{3}) . Finally to answer Q_{2} all elements in A[pos_{6}:pos_{19}] are returned. In order to improve search time, the entries in T are inserted in such a way that they remain sorted by the boundary interval [l,h] . Thus the tuple (6,8,pos_{6},pos_{8},M_{2}) appears before (9,13,pos_{9},pos_{13},M_{1}) , whereas (14,19,pos_{14},pos_{19},M_{3}) appears after it. As and when more queries arrive, A gets further refined and new entries are inserted in T , until enough queries are submitted so that an index gets created on the entire array A . Subsequently submitted queries can be directly answered by using T only. When one or both of the end points of a query already fall(s) within a sorted partition, its corresponding learned model is consulted to obtain the position(s) of the key(s). Next, we discuss our approach in detail. 3.1. Query scenarios (a) Case 1(i): l and h overlap existing partition(s) (b) Case 1(ii): l and h fall within a single unsorted partition (c) Case 2: l and h fall within a single sorted partition (d) Case 3: l and h fall in two different sorted partitions (e) Case 4: Only l falls within a sorted partition (f) Case 5: Only h falls within a sorted partition Figure 2 . Different query scenarios For a query Q to find all x\in A , such that l\leq x\leq h is invoked, one of the following cases holds, which are also shown in Fig. 2 . In the figure, the black outer rectangle represents the entire data range, whereas the red solid rectangles represent those partitions that have been sorted by previous queries, and learned indexes is/are constructed for those partitions. The white spaces represent unsorted partitions, which have not been touched by any query yet. Note that, initially before any query arrives, the entire unsorted array A is considered to be a single partition: Case 1 : Both l and h reside within an unsorted partition. This can be divided into two sub-scenarios: i. Sorted partition(s) already exists between l and h . This happens when both the end points of Q covers or overlaps existing sorted partition(s), as shown in Fig. 2(a) . ii. No sorted partition exists between l and h , i.e. both endpoints belong to a single unsorted partition, as shown in Fig. 2(b) . This situation always arises when a query is issued for the first time on A . Or there might be existing sorted partitions before and/or after this query range. Case 2 : Both l and h belong to the same sorted partition, as shown in Fig. 2(c) . Case 3 : Both l and h belong to different sorted partitions, as shown in Fig. 2(d) . Case 4 : Only l belongs to an already sorted partition, but h does not, as shown in Fig. 2(e) . Case 5 : l does not belong to an already sorted partition, but only h does, as shown in Fig. 2(f) . Next, we discuss each scenario in detail. For the purpose of this discussion, we assume that each scenario begins with the the following conditions: Figure 3 . Example Situation • The array A has been divided into disjoint sorted and unsorted partitions as a result of queries submitted prior to Q as shown in Fig. 3 . There are 6 unsorted partitions U_{1}-U_{6} (shown in white) and 5 sorted partitions S_{1}-S_{5} (shown in red). Although in our example situation, we always have an unsorted partition between two sorted partitions, in a real-life scenario it is possible to have two contiguous sorted partitions without an unsorted partition in between, as we discuss later in this section. • For each sorted partition S_{i} , a tuple of the form T_{i}\equiv ( l_{i} , h_{i} , pos_{l_{i}} , pos_{h_{i}} , M_{i} ) is stored in the 1-D partition table T , where l_{i},h_{i} are the corresponding low and high values of S_{i} , pos_{l_{i}},pos_{h_{i}} are the locations of l_{i},h_{i} in A , and M_{i} is the corresponding learned index (any existing one-dimensional learned index model could be used here). The entries of T are sorted by the the interval [l,h] i.e. [l_{i},h_{i}]<[l_{j},h_{j}] implies T_{i} appears before T_{j} . It is evident, that for all x_{i},x_{j}\in S_{i},S_{j} , if S_{i} appears before S_{j} in A , then x_{i}h_{i} . Conversely, if S_{i} appears after U_{j} it implies that for all x_{j}\in U_{j},x_{j} 6K, otherwise , we use traditional sorting. 6. Query Workload Prediction And Index Update In a real-world scenario, not all queries are submitted at the same time, instead several queries are submitted simultaneously or during a certain time interval. These queries can be processed together as a workload ‘batch’. In customer-centric use cases, there could be peak times and off-peak times, with potentially short time intervals when no query is running i.e. ‘short down times’. Additionally, in many scenarios, the queries often follow a fixed pattern. In this case, future queries are predictable from the previous queries, as shown in Fig. 11 . (a) Actual Queries (b) Predicted Queries Figure 11 . Sequential ZoomIn Queries The figure shows the query workload pattern in a Sequential ZoomIn workload. In this workload, the queries zoom into a specific region of the data space and then shift to a different region. The zoom-in follows a linear trend both in terms of low and high boundaries, followed by a steady jump to another region. Fig. 11(a) shows the actual query ranges. If there are sufficient number of queries in the past, which maintains the linearity (i.e. constant difference between consecutive l or h values, e.g. between 1 st to 5 th and again between 6 th to 10 th queries in Fig. 11 ) and the jumps (i.e. sudden but constant change in l or h after fixed set of queries, e.g. a constant jump between queries 5 th and 6 th and again between 10 th and 11 th query in Fig. 11 ) , then a future query workload can be predicted, as shown in Fig. 11(b) . Thus, when enough queries are executed, these can be utilized to ‘learn’ the query patterns and forecast the next batch of queries by invoking a workload prediction algorithm in a separate thread. Since, modern CPUs support hundreds of cores, this would not affect the overall query performance. The query ranges can be considered as a ‘time-series’ data and so statistical methods for time series analysis and forecasting, such as ARIMA, can be employed for query workload forecasting. For each workload, the query patterns are different. Hence, it may be challenging for a single prediction model to forecast queries from different workloads. Input: \Delta – Past query batch S – Set of forecasting methods T -- Existing Partition Table constructed so far Output: Forecasted query batch \Delta_{f} 1 scores=\{\} ; 2 for M\in S do 3 MASE=M.apply(\Delta) //Get MASE for M ; 4 scores.append((M,MASE)) ; 5 M_{l} = forecasting method having least MASE in scores ; 6 \Delta_{f}=M_{l}.forecast(\Delta) ; 7 T.update(\Delta_{f}) ; 8 return ; 9 Algorithm 10 PredictWorkload (\Delta,S,T) Our approach for query workload prediction is shown in Algorithm 10 . In this , we maintain a fixed set of methods S (such as ARIMA, AdaBoost, and Random Forest). To simplify matters, we assume that each workload batch contains \Delta number of queries. After the execution of a workload batch, our LAI structure is incrementally updated. While the execution is in progress, the system launches the workload prediction task in a separate thread . In this task, every forecasting method M\in S is applied over \Delta (Lines 1–4) , after which the method ( M_{l} ) having the least MASE (Mean Absolute Scaled Error) is chosen (Line 5) . Then, M_{l} is utilized to forecast the next batch of queries \Delta_{f} (Line 6) . Once \Delta_{f} is generated, it is used to further update LAI based on the forecasted queries (Line 7) . In workloads, such as Sequential ZoomIn of Fig. 11 , the forecasts can be quite accurate due to the nature of the queries. Hence, when the next batch of queries is submitted, the query executor takes advantage of LAI to answer the queries. It takes negligible amount of time to answer them, since the index is already built by \Delta_{f} ( Case 2 ). For workloads where the \Delta_{f} is not very similar to the next batch of \Delta queries, it can still be advantageous as it mostly falls in one of the cases except Case 1(i) . This process of query workload prediction and index updating continues as new batches of queries appear. Our experimental results, as we discussed in the next section, reveal that this approach leads to a significant performance improvement in terms of cumulative query execution time. 7. Experimental Evaluation In this section, we present our experimental evaluation of LAI in various settings. (a) Random (b) Sequential Random (c) Sequential Alternate (d) Sequential Inverse (e) Sequential Overlap (f) ZoomIn (g) Sequential ZoomIn (h) ZoomOut (i) Sequential ZoomOut (j) Periodic Figure 12 . Synthetic Query Workloads 7.1. Experimental Setup LAI was implemented in C++ and its performance was compared against other adaptive indexing technique such as database cracking ( CRACK ) and stochastic cracking algorithms ( Stochastic_database_cracking ) , such as DDC, DDR, DD1C, DD1R, MDD1R, AICC1R and AICS1R . The C++ implementations of CRACK and the other stochastic cracking algorithms were obtained from ( url:stochastic-cracking-impl ) . All the implementations were compiled with -O3 flag enabled. Queries were executed on a randomly shuffled dataset A having all keys between [0, 100M). The queries were of the form: Find all x\in A such that l\leq x\leq h . The queries were executed from ten different synthetic workloads – Random, Sequential Random, Sequential Alternate, Sequential Inverse, Sequential Overlap, ZoomIn, Sequential ZoomIn, ZoomOut, Sequential ZoomOut and Periodic . The type of queries across each workload is shown in Fig. 12 . The experiments were conducted on a system with Intel(R) Core(TM) i5-1035G1, having Ubuntu 24.04 LTS. 7.1.1. Workload Details. From the figure, it is observed that for Random , both l and h were generated randomly. In Sequential Random , for the odd numbered queries l was random, whereas for the even ones l was sequentially increased. However, h was still random. In Sequential Alternate , for the odd numbered queries l was randomly generated but h was gradually decreased and vice-versa (i.e. l increased but h was random) for the even numbered queries. For Sequential Inverse , h sequentially decreased, but l was random. Sequential Overlap is the reverse of Sequential Inverse , where l sequentially increased but h was random. In case of ZoomIn , l gradually increased whereas h gradually decreased. Sequential ZoomIn contains zoom-in queries distributed across the data space. ZoomOut is the opposite of ZoomIn where l gradually decreased, whereas h gradually increased. In Sequential ZoomOut , zoom-out queries are distributed across the data space, similar to Sequential ZoomIn . In Periodic , the difference between l and h remains constant, but the query boundary changes such that the boundaries of the initial few queries are disjoint from each other and span the entire data space. Then the remaining queries have l that falls within the previous query range, but not h . 7.1.2. Learned Index Implementation. Although any learned index model can be used for LAI , we chose Radix-Spline (RS) ( RadixSpline ; url:radix-spline-impl ) because, its build time is quite fast , since it is built over a single-pass of the data and has efficient execution time compared to other learned indices. 7.1.3. Performance Metric. For each query workload, we measured the cumulative query execution time for 20K queries of LAI and LAI_{wofc} ( LAI w ith o ut query f ore c asting) and compared their performance with the other adaptive indexes. For LAI, we had set our forecasting window to 1000 queries, i.e. after every 1000 actual queries ( \Delta ), we are forecasting the next 1000 queries ( \Delta_{f} ) and use it to update LAI upfront for the next batch of user queries. Unlike LAI , in LAI_{wofc} query forecasting is disabled and thus LAI_{wofc} is updated only when the user queries are submitted. (a) Random (b) Sequential Random (c) Sequential Alternate (d) Sequential Inverse (e) Sequential Overlap (f) ZoomIn (g) Sequential ZoomIn (h) ZoomOut (i) Sequential ZoomOut (j) Periodic Figure 13 . Evaluation on different Query Workloads (a) Sequential ZoomIn - Freq (b) ZoomOut - Freq (c) Sequential ZoomOut - Freq (d) Periodic - Freq (e) Sequential ZoomIn - Time (f) ZoomOut - Time (g) Sequential ZoomOut - Time (h) Periodic - Time Figure 14 . Casewise evaluation of frequency and execution time on Sequential ZoomIn, ZoomOut, Sequential ZoomOut and Periodic Workloads 7.2. Experimental Results We present our evaluation of LAI against other adaptive indexing approaches, and then demonstrate the performance improvement of LAI due to query workload prediction. 7.2.1. Evaluating LAI with other approaches on different query workloads. The results of the experiments are shown in Fig. 13 . From the figure we see that the performance of both LAI and LAI_{wofc} , in-terms of cumulative query execution time, is almost the same for Random, Sequential Random, Sequential Alternate, Sequential Inverse, Sequential Overlap, and ZoomIn queries (Figs. 13(a) – 13(f) ). But there is a significant improvement in the cumulative query execution time of LAI compared to LAI_{wofc} for the remaining four workloads (Figs. 13(g) – 13(j) ). To show the benefits of query workload prediction, we also measure the frequency and the total execution time of these four workloads that each of the query spends in different cases (shown in Fig. 14 ) as explained in Section 3 . From Figs. 12(g) – 12(j) , we see that both the endpoints of the queries from these four workloads follow a pattern and are thus quite predictable. Thus, query workload forecasting offers an advantage in these situations. Although the execution times for the first query in both LAI and LAI_{wofc} are high, but as more queries are submitted, their performance starts to improve. For LAI the cumulative query execution time almost remains constant after 1K queries across all workloads, but for LAI_{wofc} , it keeps linearly increasing for Sequential ZoomIn, ZoomOut, Sequential ZoomOut and Periodic workloads (Figs. 13(g) – 13(j) ) after 1K queries. This suggests that the cumulative query execution time is dominated by the first 1K queries in case of LAI , after which the execution time remains constant due to query forecasting, especially for the last four workloads (Figs. 13(g) – 13(j) ). Both LAI and LAI_{wofc} perform better than the other adaptive indexes for Random, Sequential Random, Sequential Alternate, Sequential Inverse and Sequential Overlap queries (Figs. 13(a) – 13(e) ). So, in these workloads, our Learned Adaptive Index provides the best performance even when queries are not forecasted using our workload prediction approach. The query forecasting does not help much in these scenarios, since at least one of the endpoints is randomly generated, so it is hard to forecast the actual query patterns. So, we may be able to forecast one query endpoint (which follows a pattern, such as the high value in Fig. 12(d) ), but not the other endpoint. Therefore, our approach works well when at least one of the endpoints follows random pattern. For ZoomIn (Fig. 13(f) ), the cumulative execution time for CRACK was large (around 350 seconds) compared to the other approaches (around 5.5 seconds). Due to this reason, when we plotted them, it was hard to distinguish the performance of the other approaches. Hence, we removed CRACK from this figure. Similar to the previous experiments, here also both LAI and LAI_{wofc} have a high initialization time, and as more queries are submitted its performance nearly converges to that of the other adaptive indexes. From Fig. 12(f) , we see that after the first query, all the subsequent queries entirely falls within the first query, leading us to Case 2 . In this case all the subsequent queries are completely answered from the index built from the first query. Due to this reason the cumulative execution time of both LAI and LAI_{wofc} remains almost the same as the first query. Hence, there is no advantage of query workload prediction in this scenario as well. In case of Sequential ZoomIn (Fig. 13(g) ) LAI performs the best, whereas the performance of LAI_{wofc} is not good enough compared to the other indexes (in spite of having similar execution times until 1K queries), showcasing the advantage that we get from query workload prediction. For these workloads, multiple small ZoomIn queries are spread across the data space. As shown in Figs. 14(a) and 14(e) , in the absence of query forecasting, when the ranges of the queries move to a different data region, they cannot take advantage of the index built so far. Because, the indexes exist for the previous data region only. Thus quite a few queries fall under Case 1(ii) (around 40). This is responsible for taking most of the time and the rest of the queries belong to Case 2 . In LAI , as we were able to forecast the queries in the workload with reasonably high accuracy, this resulted in only 2 queries falling under Case 1(ii) and the remaining under Case 2 . Using query workload prediction, the reduction in the number of queries falling under Case 1(ii) in LAI has resulted in significantly reduced query execution times. Although around 19.9K queries fall under Case 2 for both LAI and LAI_{wofc} , answering them using our learned index is quite fast and it takes negligible amount of time compared to the cumulative execution time. Hence, the time values appear as 0 in Fig. 14(e) . 7.2.2. Evaluating query workload prediction. For Zoomout, Sequential ZoomOut and Periodic workloads (Figs. 13(h) – 13(j) ) we once again can observe significant improvement in query execution time with LAI compared to LAI_{wofc} . Similar to the previous case, the performance of LAI_{wofc} is not good enough in comparison to the other approaches. The performance of LAI is always better than CRACK in all the three workloads and is also better than AICS1R in case of Periodic workload . As we previously mentioned, in case of LAI , the cumulative query execution time is dominated by the first 1K queries, after which the query workload forecasting comes into effect. We can see from Figs. 12(h) – 12(j) that the ranges of the current queries are not completely covered by previous queries. This leads us to always creating an index for the uncovered portion of the current query. For ZoomOut (Fig. 12(h) ), we always need to build an index on a portion of the dataset having both the endpoints, as the entire range of the previous query is completely within the current query (Case 1(i)) . We see from Figs. 14(b) and 14(f) that LAI_{wofc} spent all the time to handle Case 1(i) , except for the first query that belonged to Case 1(ii) . In LAI , the first query also belonged to Case 1(ii) , the next 999 queries belonged to Case 1(i) . The rest 19K queries fell under Case 3 due to query forecasting, which were answered instantly. For Sequential ZoomOut (Fig. 12(i) ), we execute ZoomIn , whose range is distributed across the entire data space (shown in Figs. 14(c) and 14(g) ). This leads to a combination of fewer scenarios of Case 1(ii) and the rest being Case 1(i) for LAI_{wofc} , both of which are expensive. In LAI , for the first 1K queries, 998 and 2 queries belonged to Case 1(i) and Case 1(ii) respectively, which contributed to the entire execution time. From the remaining 19K queries, 38 queries fell under Case 2 , and the remaining under Case 3 , which were answered almost instantly. For Periodic (Fig. 12(j) ), as shown in Figs. 14(d) and 14(h) , in case of LAI_{wofc} , 100 queries belonged to Case 1(ii) since the query ranges were disjoint. The rest 19.9K queries belonged to Case 4 , where h had to be cracked always and consumed most of the execution time . With query workload prediction in LAI , out of the first 1K queries 100 belonged to Case 1(ii) and the rest of 900 queries fell under Case 4 . It took most of the time for the first 1K queries as LAI had to be updated for each of them. Due to query workload forecasting, indexes existed for the rest 19K queries, which were answered quickly, since they belonged to Case 3 . 8. Conclusion Both learned indexes and adaptive indexes have their own advantages. We propose Learned Adaptive Index (LAI) , where we incorporate learned indexes for the purpose of adaptive indexing and hence bring the advantages of both worlds. To enhance query performance, we use Learned Sort instead of traditional sorting techniques. For faster query execution, we perform workload prediction and update LAI on-the-fly . We evaluate our approach against other adaptive indexes against various query workloads and show that it outperforms for most of them. As a future work, we plan to investigate towards improving the performance of LAI on workloads, such as ZoomOut and Periodic . We also aim to extend LAI to handle multi-dimensional indexing.