Learned Adaptive Indexing with Updatable Learned Index

arXiv:2508.03471 · cs.DB · Submitted 2025-08-05 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Learned Adaptive Indexing with Updatable Learned Index".

Jane: Here's the gist of the paper. Indexes can significantly improve search performance in relational databases <ref:2508.03471#pg2> 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 <ref:2508.03471#pg3> To address the limitations of existing approaches, we propose a novel Learned Adaptive Index (LAI) <ref:2508.03471#pg4>.

Tom: Proposed Approach Overview The paper introduces Learned Adaptive Indexing (LAI), which integrates learned indexes with adaptive indexing to efficiently process Range Queries <ref:2508.03471#pg7>.

Jane: LAI is incrementally built as a byproduct of query execution, utilizing learned models for indexing data on the fly <ref:2508.03471#pg7>.

Tom: A key feature is that LAI creates a learned index on a partition of the input dataset depending on the query ranges, allowing it to maintain different types of learned indexes in different partitions, such as a FITing tree or a PGM Index <ref:2508.03471#pg7>.

Title and authors: Tom: So, to recap, this paper is about Learned Adaptive Indexing, or LAI. Basically, they're building an index that learns on the fly as you run queries against a database instead of having to build one huge index all up front and training it beforehand.

Jane: Right. The big idea here is that traditional learned indexes are hard to train when your data keeps changing constantly, so LAI makes the index adaptive—it adjusts based on what the query needs right then and there.

Lu: What's really interesting about this design is how they partition the input data and create different kinds of learned indexes inside those partitions depending on which query range you are using. So you might have a specific type of index, like a fitting tree, for one part of your data, and another kind, like a PGM Index, for another part.

Meng: That sounds complex to manage at scale. How does it handle the actual query execution speed while it’s building that index incrementally? We need to know if this adds huge latency spikes when a user hits the search bar.

Tom: They tackle that with two main things they added on top of the adaptive learning itself. First, there’s Learned Sort. It switches between traditional sorting and this learned method based on how big the partition is, which helps speed up the initial sort time itself.

Jane: And then they have query workload prediction coming in. They use past query data to guess what queries are coming next, so they can update the index for that predicted batch before it even happens. That’s a really proactive way to handle dynamic workloads.

Lalam: The results show that when you put Learned Sort and query workload prediction together with LAI, the performance jump is pretty big—we're talking improvements of five point two times up to nineteen point three times better in some cases compared to other adaptive indexes.

Tom: That jump is significant, and it’s tied directly into how they manage those sorts. They show that query workload prediction actually helps a lot with specific workloads, like ZoomOut or Periodic queries.

Jane: It suggests that for systems where queries follow a pattern, this predictive maintenance of the index might make the whole system much more responsive than just letting it react to every single query one by one.

Lu: The implication is that we can move away from building static indexes and instead create systems that are actively learning and optimizing their own structure in real time based on usage patterns.

Meng: But I gotta ask, what’s the cost of running this? If the prediction model needs to be constantly retrained with new traffic, does that mean the overhead just shifts from indexing to prediction?

Tom: It definitely adds a modeling layer, but they claim it allows for much faster index updates during query execution compared to rebuilding everything from scratch when things change.

Jane: So what we’re seeing here is a system that learns its own structure while trying to anticipate the future demands placed on it. But they did mention that extending this idea to multi-dimensional indexing is the next big goal for them.

Lalam: That sounds like where the real complexity lies, because moving from one dimension of data to many dimensions means you’re dealing with a whole new set of representation learning challenges.

Tom: Yeah, so it’s a powerful piece of work showing how ML models can be embedded directly into the indexing logic to handle uncertainty better.

The paper's summary: Tom: So, we've talked about how LAI is built incrementally and uses prediction to update indexes ahead of time; now let's talk about what they suggest as improvements for this system.

Jane: The paper points out a few ways to make this whole adaptive indexing setup even better. They focus on how the system handles those query scenarios where you have boundaries in different partitions, which is a real practical problem.

Lu: They show that by having different learned indexes like a fitting tree for one partition and a PGM Index for another, the system can maintain different data structures depending on what the query needs to do. That’s how it handles the complexity of those range queries efficiently.

Meng: So, if I'm deploying this, I need to know what this means for maintenance. They suggest that by using Learned Sort based on partition size, we can improve the initial sorting time even further when a partition needs to be processed.

Tom: Exactly. That learned sort toggling between traditional and learned methods is a clean way to get better performance without adding a huge fixed cost to the hardware just for indexing.

Jane: And they also suggest that this whole approach can be extended beyond just handling range queries, into multi-dimensional indexing for more complex data relationships.

Lalam: That’s where I see the next big thing; if you can make this adaptive structure work across multiple dimensions at once, it opens up a whole new way to structure learned representations over spatial or correlated data.

Lu: The implication is that we move from just indexing individual pieces of information to creating a more holistic, intelligent index that understands the relationships between all the data points simultaneously.

Tom: It moves the AI from being a passive search tool to an active indexing agent that anticipates the data access patterns it's going to need.

Jane: It’s really about making sure that when we have massive amounts of dynamic information, our search system doesn't get stuck because it can't keep up with how fast things are changing.

The paper's improvements: Tom: So we've walked through how Learned Adaptive Indexing, or LAI, uses incremental learning and prediction to handle dynamic workloads for range queries across various data partitions; now let’s wrap up with the final thoughts on this paper by Suvam Kumar Das and Suprio Ray.

Jane: The main implication is that we can build search systems that are inherently smarter about the data they're querying, rather than relying on rigid structures that break when things change.

Lu: It shows how machine learning models can be embedded directly into the indexing logic to handle uncertainty better while still maintaining a structure that’s efficient for query ranges.

Meng: From a production standpoint, I see this as moving toward systems that are more resilient to unexpected traffic spikes because they adapt their index on the fly instead of crashing when they hit something new.

Lalam: I'm quite sure of it; LAI directly addresses the challenge where learned indexes usually get stuck because they need a lot of upfront training time, and this method solves that by making it adaptive during runtime.

Tom: It’s definitely a solid piece of research that proves you can integrate learned indexes with adaptive indexing to process range queries efficiently using on-the-fly learning and workload prediction.

Jane: It’s a step toward making database search much more resilient to changing data patterns by moving away from static pre-indexing toward something that learns as you go.

Lu: I think the next big challenge is taking this idea of adaptive indexing and extending it to multi-dimensional indexing for more complex data relationships.

Meng: If we can make the workload prediction model lightweight enough, this could be really valuable for our production systems where query patterns are somewhat predictable over time.

Conclusion: Tom: So we've gone through how Learned Adaptive Indexing, or LAI, uses incremental learning and prediction to handle range queries across various data partitions; now we’re wrapping up this piece by Suvam Kumar Das and Suprio Ray.

Jane: The main point is that you can build search systems that are inherently smarter about the data they're querying, instead of relying on rigid structures that just break when things change.

Lu: It shows how machine learning models can be embedded directly into the indexing logic to handle uncertainty better while still maintaining a structure that’s efficient for query ranges.

Meng: From a production standpoint, I see this as moving toward systems that are more resilient to unexpected traffic spikes because they adapt their index on the fly instead of crashing when they hit something new.

Lalam: I’m quite sure of it; LAI directly addresses the challenge where learned indexes usually get stuck because they need a lot of upfront training time, and this method solves that by making it adaptive during runtime.

Tom: It’s definitely a solid piece of research that proves you can integrate learned indexes with adaptive indexing to process range queries efficiently using on-the-fly learning and workload prediction.

Jane: It’s a step toward making database search much more resilient to changing data patterns by moving away from static pre-indexing toward something that learns as you go.

Lu: I think the next big challenge is taking this idea of adaptive indexing and extending it to multi-dimensional indexing for more complex data relationships.

Meng: If we can make the workload prediction model lightweight enough, this could be really valuable for our production systems where query patterns are somewhat predictable over time.

Tom: So, to wrap up on Learned Adaptive Indexing with Updatable Learned Index by Suvam Kumar Das and Suprio Ray, they’ve successfully integrated learned indexes with adaptive indexing to handle range queries efficiently by using on-the-fly learning and workload prediction. It’s a solid step toward making database search much more resilient to changing data patterns.

Jane: That’s the gist of it—moving away from static pre-indexing to something that learns as you go, with help from predictive modeling. It gives people a way to get those massive performance boosts without the upfront training headache.

Lalam: I think this paper represents a really interesting evolution in how we think about indexing for modern, dynamic data environments. It’s practical research that shows ML models can be used for the actual mechanics of data retrieval, not just as something sitting on top of it.

Lu: Exactly, extending it to multi-dimensional indexing is the next logical step because that’s where many of these complex data science problems live. It opens up new avenues for how we structure learned representations over spatial or correlated data.

Meng: If we can get that workload prediction model to be lightweight enough, this could be really valuable for our production systems where query patterns are somewhat predictable over time.

Tom: Right, so next time you hear about adaptive indexing, remember to look at how it uses on-the-fly learning and prediction to keep up with the changing demands of the data.

University of New Brunswick

cs.DB

Submitted: 2025-08-05

Updated: 2026-11-18

Code: https://github.com/felix-halim/scrack

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 82/100

The gist: Indexes can significantly improve search performance in relational databases <ref:2508.03471#pg2> However…

Key concepts

Learned Adaptive Indexing (LAI)
LAI combines traditional adaptive indexing with learned index techniques. It incrementally builds specialized learned indexes on parts of the data based on query ranges as queries run. This allows it to use different types of learned structures, like a FITing tree or PGM Index, in different data partitions.
Query Workload Prediction
This technique uses statistical forecasting to predict future queries based on historical workload data. The index is then updated proactively for the predicted batch of queries before they arrive. This upfront indexing can improve performance by preparing the necessary structures ahead of time.
Learned Sort
Learned Sort improves sorting efficiency by dynamically switching between traditional sorting methods and a learned sorting technique. The choice depends on the size of the specific data partition being sorted, optimizing the overall time taken for that operation.
Range Query Handling Scenarios
The system manages Range Queries based on where the query endpoints fall relative to existing data partitions. It defines five distinct cases—from both boundaries in unsorted partitions to both within a sorted partition—to ensure efficient indexing regardless of the query structure.

Terminology

Summary

Indexes can significantly improve search performance in relational databases <ref:2508. p. 0

Where the paper says it

das,sray}@unb. ca ABSTRACT Indexes can significantly improve search performance in relational databases.

03471#pg2> 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 <ref:2508. p. 0
Where the paper says it

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.

03471#pg3> To address the limitations of existing approaches, we propose a novel Learned Adaptive Index (LAI) <ref:2508. p. 0
Where the paper says it

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).

03471#pg4>.

Proposed Approach Overview

The paper introduces Learned Adaptive Indexing (LAI), which integrates learned indexes with adaptive indexing to efficiently process Range Queries <ref:2508.03471#pg7>. LAI is incrementally built as a byproduct of query execution, utilizing learned models for indexing data on the fly <ref:2508. p. 0

Where the paper says it

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.

03471#pg7>. A key feature is that LAI creates a learned index on a partition of the input dataset depending on the query ranges, allowing it to maintain different types of learned indexes in different partitions, such as a FITing tree or a PGM Index <ref:2508. p. 0
Where the paper says it

Unlike traditional learned indexes which creates an index on the entire dataset, in 𝐿𝐴𝐼 a learned index gets created on a partition of the input dataset depending on the query ranges. As an advantage, 𝐿𝐴𝐼 can maintain different types of learned indexes in different partitions, e.

03471#pg7>.

Query Handling Scenarios

The LAI structure handles various query scenarios based on where the query endpoints reside relative to existing sorted and unsorted partitions <ref:2508.03471#pg7>. The paper details five main cases for handling a Range Query, including Case 1 where both boundaries are in an unsorted partition, Case 2 when both fall within the same sorted partition, Case 3 when they fall in different sorted partitions, and Cases 4 and 5 where only one endpoint is in a sorted partition <ref:2508. p. 3

Where the paper says it

Or there might be existing sorted partitions before and/or after this query range. l h (a) Case 1(i): 𝑙 and ℎ overlap existing partition(s) l h (b) Case 1(ii):𝑙 andℎ fall within a single unsorted partition l h (c) Case 2: 𝑙 and ℎ fall within a single sorted partition l h (d) Case 3: 𝑙 and ℎ fall in two different sorted partitions l h (e) Case 4: Only 𝑙 falls within a sorted partition l h (f) Case 5: Only ℎ falls within a sorted partition Figure 2: Different query scenarios Case 2: Both 𝑙 and ℎ belong to the same sorted partition, as shown in Fig.

03471#pg7>.

Performance Enhancement Mechanisms

The performance of LAI is further enhanced by two main techniques: Learned Sort and query workload prediction <ref:2508.03471#pg7>. Learned Sort uses a technique similar to [16] that toggles between traditional sorting and a Learned Sort technique based on partition size to enhance overall sorting time <ref:2508. p. 1

Where the paper says it

• We present a number of different query scenarios and show how 𝐿𝐴𝐼 handles each of them. • We present a Learned Sort technique for 𝐿𝐴𝐼 and based on the partition size to sort, we toggle between learned and traditional sorting to enhance overall sorting time.

03471#pg7>. Query workload prediction employs statistical forecasting techniques to predict the future queries using past workload data, allowing the index to be updated upfront for the predicted batch, which can result in performance improvements of 5. p. 1
Where the paper says it

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.

2× – 19.3× compared to approaches without workload prediction <ref:2508. p. 9
Where the paper says it

3 Performance Metric. For each query workload, we measured the cumulative query execution time for 20K queries of 𝐿𝐴𝐼 and 𝐿𝐴𝐼𝑤𝑜 𝑓 𝑐 (𝐿𝐴𝐼 without query forecasting) and compared their performance with the other adaptive indexes.

03471#pg7>.

Experimental Validation

Extensive experimental evaluation was conducted using a synthetic dataset of 100M keys across ten different query workloads <ref:2508.03471#pg7>. The results show that LAI outperforms other adaptive indexes for most workloads, and with query workload prediction, LAI achieves performance improvement of 5. p. 1

Where the paper says it

Our experiments show that 𝐿𝐴𝐼 outperforms the other approaches for most of the workloads. We also demonstrate that with query workload prediction 𝐿𝐴𝐼 achieves performance improvement of 5.

2×–19.3× for some of the workloads <ref:2508. p. 0
Where the paper says it

In such a situation 𝐿𝐴𝐼 can maintain an updatable learned index such as ALEX [15] for the updatable partition and static learned indexes such as RadixSpline [9] for the other partitions. 1 arXiv:2508.

03471#pg7>. Specifically, query workload prediction leads to significant improvements in cumulative query execution time for ZoomIn, ZoomOut, Sequential ZoomOut, and Periodic workloads <ref:2508. p. 8
Where the paper says it

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.

03471#pg7>.

Conclusion

The paper concludes that Learned Adaptive Indexing (LAI) successfully integrates learned indexes with adaptive indexing to efficiently process Range Queries <ref:2508.03471#pg7>. The combination of Learned Sort and query workload prediction leads to better performance than existing adaptive indexes across various query workloads <ref:2508. p. 0

Where the paper says it

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.

03471#pg7>. Future work plans include investigating the performance of LAI on workloads such as ZoomOut and Periodic, as well as extending LAI to handle multi-dimensional indexing <ref:2508. p. 9
Where the paper says it

Suvam Kumar Das and Suprio Ray Low High Query Sequence V alu e D o m ain (a) Random Low High Query Sequence V alu e D o m ain (b) Sequential Random Low High Query Sequence V alu e D o m ain (c) Sequential Alternate Low High Query Sequence V alu e D o m ain (d) Sequential Inverse Low High Query Sequence V alu e D o m ain (e) Sequential Overlap Low High Query Sequence V alu e D o m ain (f) ZoomIn Low High Query Sequence V alu e D o m ain (g) Sequential ZoomIn Low High Query Sequence V alu e D o m ain (h) ZoomOut Low High Query Sequence V alu e D o m ain (i) Sequential ZoomOut Low High Query Sequence V alu e D o m ain (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 [4], such as DDC, DDR, DD1C, DD1R, MDD1R, AICC1R and AICS1R.

03471#pg7>.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Adaptive Indexing Integration: The Learned Adaptive Index (LAI) can efficiently process Range Queries by incrementally building learned indexes on partitions of the input dataset depending on query ranges, allowing it to maintain different types of learned indexes in different partitions, such as a FITing tree for one partition and a PGM Index for another.

  2. Query Workload Prediction: The system can utilize a statistical forecasting technique to predict future queries based on past workload data, enabling automated and predictive index maintenance where the index is updated upfront for the next predicted batch of queries only.

  3. Learned Sort Enhancement: A Learned Sort technique, which toggles between traditional sorting and a learned sorting method based on partition size, can be employed to enhance overall sorting time when a partition needs to be sorted.

  4. Query Performance Improvement: The combination of LAI with query workload prediction can achieve performance improvement of 1.2x – 5.6x in query performance compared to existing adaptive indexes for various query workloads, and up to 5.2x–19.3x improvement when workload prediction is used on some workloads.

  5. Handling Dynamic Workloads: LAI is proposed as a hybrid between traditional index structures like B+-tree and adaptive indexes, where the system predicts and builds the index upfront only for the next batch of queries, which can be beneficial for workloads whose queries follow a pattern and are predictable based on current queries.

Abstract

Indexes can significantly improve search performance in 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. Building a conventional fine-grained index, like B+-tree on the entire dataset can be very expensive since it may involve processing terabytes to petabytes of data. Moreover, with a traditional indexing, data ingestion tends to slow down in case of heavy updates as the index also needs to be updated. In these cases, adaptive indexing is a viable solution instead of traditional indexing. Adaptive indexing is a technique in which an index gets built on the fly as a byproduct of query processing. In recent years, research has taken on a new direction where machine learning models are employed for the purpose of indexing. These indexes, known as learned indexes, are more efficient compared to traditional indexes in terms of memory footprints and query performance. To the best of our knowledge, no learned indexes exist yet for adaptive indexing. We propose a novel learned approach, called FLAIRS, for adaptive indexing. It is built on the fly as queries are submitted. We also introduce an updatable learned index TULSI that is utilized by FLAIRS for indexing data. FLAIRS can employ a query workload prediction technique that makes future workload projection based on past workload data. We have evaluated FLAIRS against existing adaptive indexes for various query workloads. Our results show that our approach performs better than others in most cases, offering significant improvement in query performance.

Related papers