paperPVLDB·25 Oct 2026·Zhipeng Chen, Meng Li, Hancheng Wang, Junhan Lv, Haipeng Dai, Siqiang Luo

Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases

MirrorBtr speeds up B-Tree traversals in MySQL InnoDB by adding a learned index alongside the tree instead of replacing it, so transactions and recovery stay untouched while lookups skip most inner nodes.

Read original on vldb.org Read PDF

database-internals query-performance learned-indexes b-tree mysql

Depth 5/5Score 5.27

Paper (from PDF)

Read full text

Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases ZhipengChen∗ MengLi† HanchengWang StateKeyLaboratoryforNovel StateKeyLaboratoryforNovel StateKeyLaboratoryforNovel SoftwareTechnology,Nanjing SoftwareTechnology,Nanjing SoftwareTechnology,Nanjing University University University Nanjing,China Nanjing,China Nanjing,China zhipengchen@smail.nju.edu.cn meng@nju.edu.cn hanchengwang@smail.nju.edu.cn JunhanLv HaipengDai SiqiangLuo StateKeyLaboratoryforNovel StateKeyLaboratoryforNovel NanyangTechnologicalUniversity SoftwareTechnology,Nanjing SoftwareTechnology,Nanjing Singapore,Singapore University University siqiang.luo@ntu.edu.sg Nanjing,China Nanjing,China 231220021@smail.nju.edu.cn haipengdai@nju.edu.cn ABSTRACT 1 INTRODUCTION B-Treesarethepredominantindexstructuresinrelationaldatabases. B-Treesareubiquitousindatabases,buttheybecomeaperfor- However,theybecomeaperformancebottleneckintraversal-heavy mancebottleneckfortraversal-intensiveworkloads.B-Tree workloads.Althoughlearnedindexeshaveemergedasapromis- indexesandtheirvariants(e.g.,B+-Trees)remainthedefactostan- ing solution to mitigate this bottleneck, their high engineering dardinmainstreamdatabasesystems[25,53,57,64],duetotheir complexityhinderstheirpracticaladoptionasreplacementsfor predictableperformance,robustnessacrossworkloads,andmature B-Trees.Instead,weproposeamoreviablealternative:augmenting supportfortransactionalandrecoveryfeatures[23,54,55]. B-Treeswithlearnedindexingtechniquestoreduceintegration TherapiddevelopmentofDRAMtechnology[48,67]hasmade costsandspeeduptraversals.Tothisend,wepresentMirrorBtr, large-memorydatabaseinstances(e.g.,uptoseveralhundredgiga- aunifiedframeworkthatbuildsuponexistinglearnedindexesto bytes)widelyavailableinmajorcloudproviders[5,20,49].These accelerateB-TreetraversalswithoutalteringtheB-Treestructure. instancescancachemostoreventheentireworkingset,eliminat- MirrorBtrreducesspaceandsynchronizationoverheadanddynam- ingdiskI/Oastheprimaryperformancebottleneck.Nevertheless, icallyadaptstoB-Treeupdates.WeimplementMirrorBtrinMySQL querythroughputisboundedinworkloadswithintensiveB-Tree InnoDBandconductextensiveevaluations,showingthatitcon- traversals,suchasthoseine-commerce,logistics,finance,andso- sistentlydeliverstraversalspeedupswithnegligiblemaintenance cialnetworks[42,61].Specifically,thesetraversalsdominateCPU overheadandoutperformsboththeconventionalB-Treeandprior …

Explained

What happened

MirrorBtr (Nanjing University, Alibaba, NTU; PVLDB 2026) makes B-tree lookups in MySQL InnoDB faster by adding a learned index beside the B-tree instead of replacing it. Results: up to 7.45x higher query throughput on traversal-heavy queries, with the learned index using only 0.51% of the B-tree's size. Code: github.com/unconsolable/MirrorBtr.

Why it works

With big-memory cloud instances, the working set is often fully cached, so disk I/O is no longer the bottleneck. CPU is: queries like price-range scans or joins that probe the primary key per row do root-to-leaf traversals and in-node binary searches over and over. The paper measures traversal at 20% to over 80% of query time as result sets grow. Node latches add cache-line invalidation under concurrency.

Learned indexes (a small model that predicts where a key lives from the data distribution) are faster than walking a tree, but replacing the B-tree in a real database is a huge job: crash recovery, transactions, and locking are all tied to it. Even the PostgreSQL community hit this wall.

MirrorBtr's trick is augment, don't replace:

Keep the InnoDB B-tree exactly as it is (layout, recovery, transactions unchanged).
Maintain a compact learned index that maps a key straight to the right leaf page, skipping inner-node traversal and latches.
Keep them in sync cheaply: if the leaf moved (after a page split), follow the B-tree's right-sibling links to find the right page, so the learned index never needs a global latch to be correct.
Choose the learned-index type offline on synthetic data with similar distribution, so user data is never touched (a privacy requirement).

The bigger pattern

Accelerate behind a correctness anchor. The proven structure stays the source of truth; the fast structure is a hint that can be wrong but is always checked and repaired. Same idea as caches in front of databases, or "hint" pointers in file systems. It is the practical path for research ideas to reach production engines.

What it means in practice

When your Postgres/MySQL workload is fully in memory and still CPU-bound, the cost is index traversal and latching, not I/O. Batching lookups (fewer, larger IN queries) and covering indexes help today.
Learned indexes are still not in mainstream Postgres. Watch this space rather than adopt it.
The design lesson is reusable: add speedups as verifiable hints next to the system of record, not as replacements.