Learned Adaptive Indexing with Updatable Learned Index
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 das,sray}@unb. ca
ABSTRACT
Indexes can significantly improve search performance in relational
databases. 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. 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).Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 • 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
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.
-
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
- Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
- EMA: Approximate Nearest Neighbor Search with General Attribute Filtering and Dynamic Updates
- Open Biomedical Knowledge Graphs at Scale: Construction, Federation, and AI Agent Access with Samyama Graph Database
- Samyama: A Unified Graph-Vector Database with In-Database Optimization, Agentic Enrichment, and Hardware Acceleration
- GenTUS: Table Union Search via Constrained Generation of Semantic Table Identifiers
- Common-Neighbor-Count-Based Representative Possible World Finding on Uncertain Graphs