PaperlayerView exact revision on arXiv

Source-linked AI summary

Updatable Learned Index with Precise Positions

Jiacheng Wu, Yong Zhang, Shimin Chen, Jin Wang, Yu Chen, Chunxiao Xing

arXiv:2104.05520v2cs.DB

TL;DR

Learned indexes support fast position prediction but have limited update support, and update-oriented alternatives incur lookup overhead from imprecise leaf predictions. LIPP preserves precise positions while supporting the full set of index operations and bounding tree height. Across mixed workloads, it outperforms state-of-the-art learned indexes, with reported gains up to 6.3× for lookup and 2.9× for write-heavy comparisons.

  • Problem

    Existing learned indexes cannot efficiently support updates, while update-capable approaches incur lookup overhead from imprecise leaf predictions.

  • Method

    LIPP preserves precise key-to-position mappings by extending the tree for conflicts and uses dynamic adjustment to bound tree height while supporting all index operations.

  • Results

    LIPP outperforms state-of-the-art indexes across read-only, write-only, and read-write workloads, achieving 2.8× and 6.3× better lookup performance than ALEX and PGM and up to 2.9× over ALEX for write-heavy workloads.

  • Takeaways & Limitations

    Precise positions eliminate leaf searches and support efficient index operations across varied workloads, with comparable index size under most read-write settings.

  • Takeaways & Limitations

    Future work includes automatically selecting monotonic functions, integrating LIPP into relational DBMSs with concurrency control, and adapting it to new hardware.

Abstract

from arXiv · show

Index plays an essential role in modern database engines to accelerate the query processing. The new paradigm of "learned index" has significantly changed the way of designing index structures in DBMS. The key insight is that indexes could be regarded as learned models that predict the position of a lookup key in the dataset. While such studies show promising results in both lookup time and index size, they cannot efficiently support update operations. Although recent studies have proposed some preliminary approaches to support update, they are at the cost of scarifying the lookup performance as they suffer from the overheads brought by imprecise predictions in the leaf nodes. In this paper, we propose LIPP, a brand new framework of learned index to address such issues. Similar with state-of-the-art learned index structures, LIPP is able to support all kinds of index operations, namely lookup query, range query, insert, delete, update and bulkload. Meanwhile, we overcome the limitations of previous studies by properly extending the tree structure when dealing with update operations so as to eliminate the deviation of location predicted by the models in the leaf nodes. Moreover, we further propose a dynamic adjustment strategy to ensure that the height of the tree index is tightly bounded and provide comprehensive theoretical analysis to illustrate it. We conduct an extensive set of experiments on several real-life and synthetic datasets. The results demonstrate that our method consistently outperforms state-of-the-art solutions, achieving by up to 4x for a broader class of workloads with different index operations.

1 INTRODUCTION

Learned indexes use models to predict key positions, but update support can introduce lookup overhead through imprecise leaf predictions. LIPP addresses this by preserving precise positions, supporting full index operations, and bounding tree height.

  • Learned indexes predict lookup-key positions from the dataset distribution, opening a new way to construct indexes for sorted data.
  • Updates remain challenging because prior approaches add lookup overhead: PGM searches multiple subtrees, while ALEX has unbounded leaf-node search cost.
  • LIPP supports lookup, range, insert, update, delete, and bulkload operations while eliminating last-mile leaf searches through precise key-to-position mappings.
  • LIPP bounds tree height at O(log N) using kernelized linear models and a lightweight adjustment strategy that distributes newly inserted elements across positions.
  • 2.8× and 6.3× better lookup performance than ALEX and PGM, respectively, is reported for read-only workloads; LIPP also outperforms ALEX by up to 2.9× on write-only and read-write workloads.

2 PRELIMINARIES

The preliminaries define index operations and explain how learned indexes and update-oriented designs organize models, segments, and nodes. They also introduce monotonic prediction models, which support range queries and compute positions within node arrays.

  • The index interface includes membership, lookup, range, insert, delete, update, and bulkload operations, assuming unique keys.
  • B+Tree lookup cost combines root-to-leaf traversal with in-node search, while limiting node size prevents large within-node search costs.
  • Learned Index builds a fixed-height hierarchy of models that predicts positions in sorted keys and corrects errors with bounded binary search, but it cannot support updates.
  • PGM corrects predicted positions at each level and uses an LSM-tree-style organization to support insertions.
  • ALEX uses exponential search in leaf nodes and shifts elements for insertion, with average shifting cost O(log m) and worst-case cost O(m).
  • Monotonically increasing models preserve key order, which is essential for range queries because the start-key prediction must not follow the end-key prediction.
  • LIPP's kernelized linear model maps a key to an entry position in an L-entry node using a monotonically increasing kernel, slope, and intercept.

3 THE LIPP INDEX

LIPP preserves exact model-predicted positions by replacing conflicting entries with child nodes, then controls tree growth through subtree adjustment and conflict-aware model construction. It defines conflict degree to select models and provides an efficient algorithm with a theoretical logarithmic height bound.

  • Design challenges: LIPP preserves precise predictions by replacing conflicting entries with child nodes instead of shifting elements.This eliminates inaccurate leaf predictions and the associated in-node search and insertion shifting overheads.
  • Design challenges: A subtree adjustment strategy redistributes keys to control height after new nodes are created for conflicts.The strategy selects the subtree and determines when and how adjustment occurs.
  • Guarantees: LIPP provides a theoretical guarantee that its tree height is bounded by O(log N).The bound accompanies theoretical analysis of lookup and insertion complexity.
  • Structure: LIPP models every node uniformly with a model, entry array, and entry-type bit vector rather than separate leaf and internal node classes.Entries are NULL, DATA, or NODE; NODE entries point to child nodes holding conflicting elements.
  • Structure: Monotonically increasing models keep DATA entries and NODE subtrees sorted by key across each node’s array.This ordering property supports sorted index operations throughout the structure.
  • Model metric: Conflict degree T_M is the maximum number of keys mapped to any one position, with lower values indicating better models.The ideal model has conflict degree 1, while mapping all keys to one position yields |K|.
  • Model construction: The model-construction conditions constrain A and b so mapped keys remain within the entry range and consecutive keys avoid conflicts.The algorithm checks Condition (9), increments T after failures, and derives model parameters from the resulting conflict degree.
  • Model metric: FMCD computes the minimum conflict degree and corresponding model in linear complexity, whereas naive enumeration has O(N^2) time complexity.Theorem 3.3 states that FMCD returns precisely the minimum T satisfying Condition (9).

4 OPERATIONS OF LIPP

LIPP supports lookup, range, insert, delete, update, and bulkload operations while preserving precise model-based positions. Its node-adjustment strategy controls conflicts and tree growth, keeping lookup dependent on tree height.

  • Lookup Queries: LIPP lookup follows model-computed positions through child nodes and verifies DATA entries because multiple keys may map to one position.NULL entries indicate absent keys; NODE entries lead to the next traversal level.
  • Lookup Queries: Lookup costs O(h), where h is the tree height, because precise positions eliminate extra searches within nodes.The procedure traverses only the root-to-entry path.
  • Range Queries: Range queries locate the start key, then scan forward through ordered entries and child nodes until the end key is reached.LIPP can compute end-key positions across levels to avoid unnecessary key comparisons.
  • Index Inserts: Insertions fill NULL gaps directly, while conflicts create a child node containing the new and original elements.After insertion, LIPP may adjust nodes along the reverse traversal path.
  • Node Adjustment: Node adjustment is triggered by subtree expansion or excessive conflicts, then rebuilds a partial tree from the subtree’s ordered keys.The expansion criterion uses β, defaulting to 2, while conflicts can increase tree height and hurt lookup and insert performance.
  • Node Adjustment: The rebuilt partial tree assigns L=δ times the number of keys, with δ=2 as an example, while capping L at 1M entries.The design preserves gaps for future insertions and reduces elements assigned to the next level to limit tree height.

5 ANALYSIS

LIPP’s lookup complexity depends on tree height, which is theoretically bounded logarithmically in the number of elements. Insertions incur amortized adjustment overhead, while typical insertions remain cheaper than the worst-case bound.

  • Tree Height and Lookup Analysis: LIPP lookup traverses from root to the final entry without extra search steps, so its cost depends only on tree height.The stated lookup complexity is O(log N) even in the worst case.
  • Tree Height and Lookup Analysis: Theorem 5.1 states that a LIPP index with N elements built from adjustment has height at most O(log N).The proof uses at least m branches per level, yielding an O(log_m N) bound.
  • Tree Height and Lookup Analysis: Theorem 5.2 states that a LIPP index with N elements built from scratch also has height at most O(log N).The analysis derives a recursive relation between parent and child element counts.
  • Tree Height and Lookup Analysis: With minimum fanout m, LIPP has average lookup complexity O(log_m N), compared with O(log_2m N) for PGM and O(log_m N+log_2 m) for ALEX.The paper identifies LIPP as having the best lookup complexity among these expressions.
  • Insert Analysis: Adjustment on a node with N elements costs at most O(N·log N), while amortized insertion cost is at most O(log^2 N).The adjustment bound accounts for model training across tree levels; insertion analysis uses amortized accounting.
  • Insert Analysis: Although the worst-case amortized insertion bound is worse than B+Tree, ordinary insertions usually traverse to a NULL entry and cost O(log_m N).The paper reports that experiments show insertions behave well in practice.

6 EVALUATION

LIPP is evaluated against learned and traditional indexes across varied datasets and mixed operation workloads. It consistently improves throughput while maintaining acceptable index size and reducing lookup and adjustment overheads.

  • Experiment setup: Experiments use real-world and synthetic datasets, with read-only, read-heavy, write-heavy, and write-only workloads measured by average throughput.The workloads run for 100M operations, with five repetitions, on a single-threaded Ubuntu system.
  • Throughput comparison: LIPP consistently outperforms state-of-the-art methods across different workload types.The paper reports particularly strong gains against ALEX, PGM, B+Tree, and ART.
  • Throughput comparison: For read-only workloads, LIPP achieves up to 2.8x, 6.3x, 15.3x, and 9.8x throughput than ALEX, PGM, Learned Index, and B+Tree, respectively.The precise-position design eliminates in-node search while keeping tree height bounded.
  • Throughput comparison: On the highly non-uniform LLT dataset, LIPP reaches only 1.47x the throughput of ALEX because increased tree traversal dominates learned-index performance.The irregular distribution makes the learned models harder to fit and increases tree height.
  • Throughput comparison: For read-write workloads, LIPP achieves 2.9x, 13.5x, 5.4x, and 3.7x higher throughput than ALEX, PGM, B+Tree, and ART, respectively.LIPP has comparable index size under most settings, while all methods slow as insertions increase.
  • Index size: LIPP's index size is generally comparable to or smaller than ALEX and Learned Index, while raw data typically dominates memory usage.For YCSB, the raw dataset is 17.6 GB while the index remains below 500 MB even for the worst method.
  • Bulkload: LIPP bulkloads 100M elements in less than half the time required by ALEX and PGM, while remaining only slightly slower than B+Tree.Its insert performance can offset the small bulkload disadvantage because B+Tree degrades sharply after additional inserts.
  • Detailed performance study: LIPP reduces lookup memory accesses by eliminating last-mile search, redundant PGM component lookups, and longer traditional-tree traversals.Its lower access count reflects fewer search and traversal steps.

7 DISCUSSION

The discussion connects LIPP's tree structure to established concurrency techniques and considers its use with hardware accelerators. Precise positions reduce unnecessary contention, while GPU deployment introduces utilization and synchronization challenges.

  • Concurrency: LIPP can use traditional tree concurrency mechanisms because its adjustments resemble B+Tree structure modifications such as splits and merges.The paper specifically identifies latch coupling with read/write locks as applicable.
  • Concurrency: Precise positions reduce unnecessary contention because inserts without adjustment do not shift leaf elements.This separates lookup and insert activity more effectively than in B+Tree or ALEX leaf nodes.
  • New hardware accelerators: GPU and TPU deployment may benefit LIPP, but high invocation latency and different computing models require careful system integration.The paper argues batching can amortize invocation cost, while data layout and synchronization remain concerns.
  • New hardware accelerators: GPU execution faces under-utilization from communication and branch divergence, potentially requiring new data layouts and concurrency protocols.GPU synchronization and communication are described as heavier and more complicated than on CPUs.

8 RELATED WORK

Related work spans learned indexes, compressed or accelerated tree structures, and concurrency-oriented B+Tree variants. These systems motivate LIPP's focus on learned distributions, efficient node search, and updates.

  • Learned index: Learned-index research includes A-Trees, Learned Index, FITing, PGM, and pB+-tree, which use learned distributions or models to organize and compress indexes.Related systems differ in prediction guarantees, model placement, and index-node design.
  • Tree and hardware optimizations: FAST uses SIMD instructions for cache-efficient node searches, while Blink-Tree supports concurrent restructuring for underflow and overflow nodes.The broader index literature also includes specialized structures such as T-trees and radix-style designs.

9 CONCLUSION AND FUTURE WORK

The conclusion presents LIPP as a learned index supporting the full operation set through precise positions and dynamic tree-height control. Future work targets broader distribution robustness, DBMS integration, and new hardware.

  • Conclusion: LIPP supports a full set of index operations by precisely predicting search-key positions and eliminating last-mile leaf searches.Its dynamic adjustment strategy tightly bounds tree height across workloads.
  • Conclusion: The paper reports superior performance across popular datasets and varied workloads.This conclusion summarizes the experimental evaluation without identifying a single dataset or workload as representative.
  • Future work: Future work includes automatically selecting monotonic functions for different distributions and implementing LIPP in relational DBMSs with concurrency control.The authors also plan to adapt LIPP for new hardware.
  • Theoretical analysis: The analysis proves that the selected T0 satisfies the required spacing constraint for all relevant key pairs.The proof uses monotonicity and the algorithm's checks over candidate values of T.
  • Theoretical analysis: The analysis establishes that no smaller T1 can satisfy the same condition, so the returned T0 is minimal.The contradiction follows because any smaller candidate would have failed the algorithm's check.

A.2 Proof of Theorem 5.2

The proof bounds the maximum subtree size after adjustment and derives an O(log N) upper bound on LIPP's index height.

  • After adjustment, the maximum number of entries in a subtree is bounded by μ, while subsequent insertions can add at most N−μ elements to one child.
  • When a node contains N elements, its subtree contains at most (m·β−(m−1))·N elements.
  • The index height is at most O(log_{m·β/(m·β−(m−1))} N), which is O(log N) when m≥3 and β>1.

A.3 Proof of Theorem 5.4

The amortized analysis charges insertions for adjustment overhead using credits saved along traversal paths, yielding an O(log^2 N) amortized insertion cost.

  • The accounting method saves O(log N) credits for each node along an insertion traversal path and uses those credits to pay for adjustment.
  • Without adjustment, each insertion costs O(log N), and storing credits across at most O(log N) traversed nodes requires O(log^2 N) credits per insertion.
  • After adjustment clears a node's credits, (β−1)·μ later insertions accumulate enough credits to pay for the next adjustment without extra cost.
  • The total cost of N insertions is O(N·log^2 N), so the amortized cost per insertion is at most O(log^2 N).

B.1 Comparisons on Synthetic Datasets

On synthetic datasets, kernel functions matched to the data distribution improve LIPP's throughput and reduce conflicts, adjustments, and tree levels, while default LIPP remains competitive overall.

  • LIPP with a distribution-specific kernel consistently outperforms its default kernel across workloads, exceeding it by more than five times in some extreme cases.
  • Matching the kernel to the distribution reduces element conflicts, structure modifications, and tree levels, improving lookup and insertion performance.
  • Even with the default kernel, LIPP outperforms state-of-the-art methods on extremely nonlinear and non-uniform synthetic distributions.
  • Adjustments have lower complexity and usually operate on relatively small data collections, limiting their overhead.
  • With the default kernel, LIPP performs worse than ART only on exponential datasets, where dense early regions cause repeated collisions and adjustments.
  • LIPP is not very sensitive to α and β; using α=0.2 causes at most 20% degradation versus α=0.1, with a similar trend for β.

B.3 The Analysis for ALEX

The ALEX analysis attributes LIPP's performance advantage to avoiding ALEX's extra memory accesses for leaf searches and element shifting, while maintaining comparable or lower tree height.

  • ALEX spends about 30% of memory accesses on leaf exponential search for lookups and more than 50% on shifting and gap management for most insert workloads.
  • LIPP avoids these ALEX memory accesses because its precise positions eliminate the corresponding search and shifting costs.
  • LIPP's adjustment time is comparable to ALEX's structure-modification time on write-only workloads.
  • LIPP and ALEX have comparable tree heights, while LIPP's tree is much shorter than B+Tree and ART.
Loading 2104.05520v2…