← Back to summary
Replace or Augment: Rethinking the Role of Learned Indexes in Relational Databases
Converted from PDF with markitdown. Layout may be rough.
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 executiontimeandexhibitpoorscalabilityunderhighconcurrency.
accelerationmethodsinInnoDB.Inparticular,MirrorBtrachieves Weillustratethisbottleneckwithtworepresentativequeries:
upto7.45×higherquerythroughputthantheB-Tree.
•Q1(PriceRangeFilter):SELECT id, price, title FROM goods
WHERE price BETWEEN 20 AND 120;
•Q2(JoinwithDateFilter):SELECT users.id, users.name FROM
PVLDBReferenceFormat:
users JOIN shipmentsON users.id = shipments.user_id AND
ZhipengChen,MengLi,HanchengWang,JunhanLv,HaipengDai,
shipments.date = ‘2026-01-01’;
andSiqiangLuo.ReplaceorAugment:RethinkingtheRoleofLearned
Q1performsrangescansandrepetitiveprimaryindexlookupson
IndexesinRelationalDatabases.PVLDB,20(1):1-15,2026.
thegoodstabletofetchmatchingproducts.Q2conductsajoin
doi:10.14778/3845598.3845599
withdatefilteringandprobestheprimaryindexofusersforeach
PVLDBArtifactAvailability: matchingrecord.Bothqueriesrelyonfrequentroot-to-leafB-Tree
Thesourcecode,data,and/orotherartifactshavebeenmadeavailableat nodeaccessesandintra-nodebinarysearches,incurringsubstantial
https://github.com/unconsolable/MirrorBtr. cumulativeoverhead.Inaddition,node-levellatchesensurethread
safety,buttheiratomicoperationsfrequentlyinvalidateCPUcache
lines,leadingtocostlysynchronizationoverhead.Asaresult,such
∗WorkdoneduringinternshipatAlibabaGroup. frequentlookupsencounteraperformancewall:(1)B-Treetraversal
†Correspondingauthor. overheadincreasesfrom20%toover80%oftotalqueryexecution
ThisworkislicensedundertheCreativeCommonsBY-NC-ND4.0International timeastheresultsetsizeincreases(detailedinSection3.1)and(2)
License.Visithttps://creativecommons.org/licenses/by-nc-nd/4.0/toviewacopyof
thislicense.Foranyusebeyondthosecoveredbythislicense,obtainpermissionby repeatedlatchcontentiondegradesconcurrentscalability.
emailinginfo@vldb.org.Copyrightisheldbytheowner/author(s).Publicationrights
Toaddresstheabovebottlenecks,learnedindexesaccelerate
licensedtotheVLDBEndowment.
ProceedingsoftheVLDBEndowment,Vol.20,No.1ISSN2150-8097. indexlookups,whileoptimisticlatchingB-Treesmitigate
doi:10.14778/3845598.3845599 readlatchcontention.Despitetheirpotential,bothsuffer
1
fromhighintegrationcomplexityinreal-worldrelational Whilelearnedindexesarecontinuouslyevolvingtowardhardware
databases.Learnedindexes[11,18,32,72]andoptimisticlatching limits,demonstratingtheirpracticalvalueviareal-worldsystem
B-Trees[37]arepromisingsolutionstothetraversalbottleneck.The integrationremainsrelativelyunderexplored.Ratherthanpropos-
pioneeringworkonlearnedindexes[32]exploitsdatadistribution ingnewlearnedindexes,ourworkfocusesondeployingexisting
toachievelowerquerylatencythantraditionalB-Trees.Thisinitial onestorelationaldatabasesthroughaunifiedframework.
proposal catalyzes a surge of research that extends the learned Contributions.Ourmaincontributionsaresummarizedasfollows:
paradigmtobroaderscenarios,includingdynamicupdates[11,18,
• B-Treeaugmentationwithlearnedindexes.WeproposeMir-
50,72,83]anddisk-basedstorage[34,44,81].Meanwhile,optimistic
rorBtr, a lightweight framework that augments B-Trees with
latchingB-Treesemployversion-basedvalidationtoeliminateread-
learnedindexestospeedupB-Treelookups.Thisapproachre-
sidecontention[3,37].Giventhesebenefits,bothtechniquesare
ducesspaceandsynchronizationoverheadwhilepreservingthe
viableandeffectivealternativestoaddressthetraversalbottleneck.
originalphysicallayoutofB-Trees.
Despitethesecompellingadvantages,thedeploymentoflearned • Privacy-preservingofflinepipelineforlearnedindexse-
indexesandoptimisticlatchingB-Treesinrelationaldatabasesre-
lection.Wedevelopanofflinepipelinetoselectalearnedindex
mainslimited,primarilyduetoexcessiveintegrationcomplexity.
candidateacrosssynthesizeddatasetswithvaryingdistributional
First,B-Treeindexesaredeeplycoupledwithcoredatabasecom-
complexity.Decoupledfromthedatabaseinstance,thisdesign
ponents such as crash recovery [27, 51, 52, 85] and transaction
avoidsaccessinguserdataandcomplieswithprivacypolicies.
management[4,14,58,74].MigratingfromB-Treestolearnedin- • Lightweightsynchronizationforcoexistingindexes.Wede-
dexesthusrequirescomprehensivesystemredesignandrigorous
signasynchronizationprotocolbasedonlearnedindexupdates
validation,goingfarbeyondsimpleAPIreplacements.Notably,the
andrightwardB-Treeleaf-siblingsearches,ensuringcorrectness
PostgreSQLcommunityhasfacedsimilarchallengesduringtrialsof
withoutgloballatchesonthelearnedindex.
learnedindexintegration[12].Inaddition,incorporatingoptimistic • Integrationandevaluationinareal-worlddatabase.We
latchingB-Treescomplicatesthecontrolflow.Anydetectedcon-
implementMirrorBtrintheMySQLInnoDBstorageengineand
currentwritetriggersanoperationrestart[37,38],demandingsafe
evaluateitwithmultiplereal-worlddatasets[46,71].Experi-
resourcereclamationtoavoidleaksfromincompletecleanupduring mentalresultsshowupto7.45×throughputimprovementover
repeatedretries.Thismechanismentailsextensivecodemodifica-
vanillaB-Treeontraversal-intensivequeries,whileconsuming
tionstocoreexecutionpaths[3].Asaresult,mainstreamrelational
only0.51%oftheB-Treeindexsize.
databases, including MySQL and PostgreSQL [12, 26], have not
adoptedthesetechniquesintotheircorearchitectures,whilemost 2 BACKGROUND
deploymentsareconfinedtokey-valuestores[2,9,28,36,43,68,70].
Thissectionreviewstheon-diskB-TreeasthefoundationofMir-
Proposeddesign.Totackletheaforementionedintegrationchal-
rorBtrdesign,takingInnoDBasarepresentativeexample.Note
lenge,weadvocateapragmaticalternativeparadigm:augmenting
thatalthoughInnoDB’sindexstructureistechnicallyaB+-Tree,
conventionalB-Treeswithlearnedmodelsratherthanreplacing
weuse“B-Tree”toalsorefertotheB+-Treethroughoutthiswork,
them.Specifically,areplacementdesignfullysubstitutesthenative
followingtheconventionin[16,54].
B-Treewithanewstructurethatindependentlycontrolssearch
Searchmodesandseparatorkeys.Pointandrangequeriesadopt
logicanddatalayout.Incontrast,anaugmentationapproachpre-
dedicated search modes to retrieve matched records via B-Tree
servestheexistingB-Treesforcompatibilityandleveragesauxiliary
traversal.Duringthisprocess,separatorkeysininnernodesgov-
structurestoassistwithspecificsubtasks,suchasguidingsearch
ernthetraversalpath.SpecifictoInnoDB,fourdirectionalsearch
pathsandalleviatingconcurrencycontention.Wechooseconcur-
modes[65]areprovided:
rentlearnedindexesforaugmentation,motivatedbytheirhighread
performance,compactmemoryfootprint[46,62,71],andsupport • LTandLE.Searchforrecordslessthan(LT)orlessthanor
foroptimisticlatching[18,71,83].However,learnedindexesevolve equalto(LE)thequerykey,withbackwardscanning.
continuouslytowardmoreadvanceddesigns[11,18,50,83],and • GTandGE.Searchforrecordsgreaterthan(GT)orgreater
differentindexdesignsexhibitdistinctperformancecharacteris- thanorequalto(GE)thequerykey,withforwardscanning.
tics[62,71],resultinginvaryingbenefitsandoverheadswithin Intermsofseparatorkeyimplementation,InnoDBstoresthemini-
MirrorBtr.Wethusconstructaflexibleframeworkcompatiblewith mumkeyofeachchildsubtreeinsideinnernodes[8].Asillustrated
diverseindeximplementations,alongwithadedicatedmechanism inFigure1,10and8613serveasseparatorkeys,whicharemini-
tochoosethemostsuitableone. mumkeysoftheirrespectivechildsubtrees.Givenaquerykey𝑘,
WeinstantiatethisparadigminMySQLInnoDBandpresentMir- innernodesroutethetraversaltotheleafnodewiththelargest
rorBtr,alightweightlearnedmirrorthataugmentsB-Trees.Mir- separatorkeythatsatisfies<𝑘forLTandGEmodes,and≤𝑘for
rorBtroffersthefollowingkeyfeatures:(1)Anon-intrusiveframe- LEandGTmodes.Afterlocatingthetargetleafnode,thesearch
workthatenablesseamlessintegrationofvariouslearnedindexes continuestofindtheexactrecordwithinthenode.
intoB-Trees;(2)Anofflineselectionpipelinethatidentifiessuitable Sortedoffsetarraysinnodes.On-diskB-Treesmaintainanar-
learnedindexcandidates;(3)Alightweightsynchronizationscheme rayofrecordoffsetssortedbykey,enablingbinarysearchduring
betweenthelearnedindexandtheunderlyingB-Treewithlowrun- lookups[54].Suchoffsetarrayscanbedensewithoneslotper
timeoverhead;(4)EffectiveaccelerationofB-Treetraversals. record,asinPostgreSQL’slinepointerarray[25],orsparsewith
oneslotpergroupofrecords,asinInnoDB’spagedirectory[64].
2
| | | | B-Tree | | | Table1:Traversaltimeofsecondaryindexrangequeries. | | | |
| ----- | --- | ---- | ------ | ---- | ----------- | ------------------------------------------------- | --- | -------- | ------- |
| | | 10 … | ... | 8613 | Inner nodes | | | | |
| | | | | | | Rangesize | 1 | 10 25 50 | 100 200 |
| 10 60 | ... | 359 | 8613 | … | ... 9947 | | | | |
…
| | | | | | | Percentage(%) | 21.80 | 45.82 61.72 71.91 | 79.08 83.02 |
| ----------- | ----------- | --------- | ----------- | --- | ----------- | ------------- | ------------- | ----------------- | ------------- |
| … | … | Leaf Node | | … | … | | | | |
| | | Records | | | | 80 | | 80 | |
| | | | | | | W/ RL | | W/ CB | |
| Key: −∞ | Key: 359 | | Key: 362 | | Key: 365 | 60 W/O RL | | 60 W/O CB | |
| Offset: 100 | Offset: 135 | | Offset: 150 | | Offset: 200 | SPQK | | SPQK | |
| | | | | | | 40 | | 40 | |
| | | | | | | 20 | | 20 | |
| Key: 386 | Key: 377 | | Key: 371 | | Key: 367 | | | | |
| Offset: 366 | Offset: 340 | | Offset: 313 | | Offset: 238 | | | | |
| | | | | | | 0 | | 0 | |
| | | | | | | 1 2 4 | 8 16 32 64128 | 1 2 4 | 8 16 32 64128 |
| | | | | | | | Threads | | Threads |
| Key: 393 | Key: 399 | | Key: 407 | | Key: +∞ | | | | |
Offset: 399 Offset: 266 Offset: 287 Offset: 110 (a) Effect of Read Latch (RL) (b) Effect of Core Binding (CB)
Page Directory
100 238 399 110 Figure2:Secondaryindexrangequeryscalabilityunderdif-
ferentsettingswith100rangesize.W/RL:withreadlatch,
W/ORL:withoutreadlatch,W/CB:withcorebinding,W/O
Figure1:InnoDBB-Treeanditsleafnodelayout.
CB:withoutcorebinding.
200keys,thetimeshareofB-Treetraversalsurgesfrom21.80%to
Accordingly,intra-nodesearchesinInnoDBfirstperformabinary
83.02%,confirmingtraversaloverheadastheprimarybottleneck.
searchonthepagedirectoryandthenproceedwithalinearscan
ontherecordgroup.Figure1illustratesthelayoutofanInnoDB Case#2:ScalabilityBarriersinConcurrentWorkloads.Be-
leafnode,includingitsrecordsandtheassociatedpagedirectory. yond accumulated traversal overhead, B-Trees suffer from scal-
Adjacentuserrecordsformanorderedlinkedlistanchoredbytwo ability limitations under concurrent access, as validated by the
markers:theinfimumandsupremumrecords.Thesemarkerrecords throughputresultsinFigure2.InFigure2(a),thestandardB-Tree
withreadlatches(W/RL)plateausat24KQPS,whiletheversion
areallocatedduringnodeinitializationwithloweroffsetsthanuser
records.Thepagedirectorystoresoffsetstotheinfimumrecord withoutreadlatches(W/ORL)scalestoover50KQPSat128threads.
(100),twouserrecords(238and399),andthesupremumrecord Thisgapstemsfromcachelineping-ponginducedbylatchcon-
(110)assparselandmarks.Thisarrangementboundsthesizeofeach tention[38]:evenforread-onlyworkloads,acquiringareadlatch
recordgrouptoafixedthreshold(1to3inthisexample),thereby entailsatomicupdatestolatchstates(e.g.,readercounts),which
inturntriggerexpensivecross-corecachecoherencetraffic.Inad-
limitingthescandistance.
dition,Figure2(b)showsthatbindingthreadstoasinglesocket
3 MOTIVATION (W/CB)improvesthroughputbyupto13%.Thisgainstemsfrom
theeliminationofcross-socketnodefetching,whichreducesthe
Inthissection,weanalyzetherootcausesofB-Treeinefficiencies
CPUcycleshareofnodefetchingfrom13.04%to4.51%.Thesere-
andexaminewhyintegratingexistingindexoptimizationsremains
sultsconfirmthatlatchcontentionistheprimaryscalabilitybarrier,
nontrivialforrelationaldatabases.
whilecross-socketnodefetchingfurtherreducesthroughput.
3.1 WhenB-TreesBecomeaBottleneck?
3.2 AdoptionBarriersofExistingTechniques
B-Treesdeliverhighefficiencyforquerieswithfewindexsearches:
Despitesubstantialprogressinlearnedindexes,whichspandy-
thenumberoftraversalsissmall,andtheshallowtreeheight(typi-
namicupdates[11,13,15,18,50,72,80,83],on-diskstorage[33,
cally3to4levels)resultingfromkilobyte-sizednodes(e.g.,16KB
34,44,81],andscalabilityoptimizations[18,50,83],mainstream
inInnoDB,8KBinPostgreSQL)keepstraversaloverheadmodest databaseshesitatetoadoptthemasreplacementsforB-Trees.Sim-
intotalqueryexecutiontime. ilarly,optimisticlatchingB-Treevariantsmitigatethescalability
However,B-Treesbecomebottlenecksintraversal-heavyqueries bottleneck [3, 37, 38], yet see limited deployment in relational
thatrepeatedlyperformroot-to-leaflookups,includingsecondary- databases.Theseadoptiongapsstemprimarilyfromprohibitive
indexrangescans(Q1)andindexnested-loopjoins(Q2)inSection1. engineeringcomplexity.Weelaborateonthekeyreasonsbelow.
Weillustratethiswithtwocasesreturningatmosthundredsof
Reason#1:IndexesaredeeplycoupledwithkeyDBMScom-
rowsonatablewith100millionrecords.Althoughindexlookups
ponentssuchasrecoveryandconcurrencycontrol,making
accessfarfewerpagesthanafulltablescan,thecumulativetra- fullreplacementhighlynontrivial.Forcrashrecovery,ARIES-
versaloverheaddominatesexecutiontimeandlimitsconcurrent stylewrite-aheadloggingisthedefactostandardinmainstream
scalability.
databases[27,51,52,85].Underthisscheme,indexupdatesgen-
Case#1:B-TreeTraversalDominance.Astheresultsetsize eratephysiologicalredologs(e.g.,"insertrecordatpositionXin
grows,B-Treetraversalincreasinglydominatesqueryexecution nodeY")andlogicalundologs.Furthermore,moderndatabases
time. As shown in Table 1, when the range expands from 1 to extensivelyemploymulti-versionconcurrencycontrol(MVCC)for
3
transactionmanagement[4,14,58,74],whichmaintainsaversion Storage Engine MirrorBtr
chainofoldervaluesforeachindexentry.Giventhefundamentally Transaction Logging Structure (§4.2)
differentnodelayoutoflearnedindexes,adaptingthemrequiresa Selection Learned Index
Pipeline (§4.3)
fullredesignofbothlogreplayandversionstoragemechanisms. B-Tree Locate
Leaf
AttemptstointegrateALEXintoPostgreSQL[12]furtherconfirm
thisengineeringburden:beyondloggingandMVCC,suchefforts Synchronization A B X Y
alsofacechallengesindiskpersistenceandoptimizercostestima- A B X Y (§4.4) Intra-leaf Models
tion.Hence,indexreplacementisnotadrop-inswapbutentails
Locate Search
holisticre-engineering. Traversal (§4.5) Leaf in Leaf
Buffer pool
Reason#2:IntegratingoptimisticlatchingB-Treealsode- Leaf A Leaf X Leaf Y Intra-leaf Models
mandsextensivecodechanges.Optimisticlatchingeffectively Record Model Model Model
Leaf A Leaf X Leaf Y
relieveslatchcontention,butrequiresoperationretriesuponread-
writeconflict[3,37,38].Toenableefficientretriesacrossmulti-
plecallstacks,LeanStoreproposesmanualstackunwindingusing Figure3:MirrorBtrdesignoverview.
“longjmp”inC[3].Since“longjmp”bypassesC++destructors,man-
ualstackunwindingexplicitlycleansupresourcesbywrapping
resourceallocation,destruction,andcontrol-flowtransitionwith
migrationandengineeringeffortsonothermodules(e.g.,recovery,
concurrencycontrol).Bynon-intrusiveintegration,wepreserve
hooks.Suchpervasive,fine-grainedmodificationstotheexisting
theon-disklayoutwhileconfiningchangeswithintheB-Tree.
codebaseincuraprohibitiveimplementationeffort.
4 DESIGN
3.3 APracticalAlternativetoFullReplacement
ThissectionpresentsMirrorBtr,anon-intrusiveframeworkthat
Giventhehighengineeringcomplexity,replacingexistingB-Tree
constructsauxiliarystructurestoaccelerateB-Treetraversals.
indexesentirelyremainsprohibitive.Amorepracticalalternativeis
augmentation:preservingexistinginfrastructurewhileemploying ArchitectureOverview.AsillustratedinFigure3,MirrorBtrem-
learnedmodelsasauxiliarystructures. ploysalearnedindextolocatethetargetleafforagivenkey,skip-
pinginnernodeaccessesduringB-Treetraversals.Toeffectively
Augmentation overcomes replacement barriers and gains
meettherequirementsforindexaugmentation(R1-R3),itscore
benefitsatalowercost.First,augmentationensurescompatibil-
designprinciplesaresummarizedasfollows:
itywithothermodules:thelearnedmodelonlyassiststraversals,
whiletheB-Treestillhandlescriticalresponsibilitiessuchascrash •Leaf-node-levelmapping. Toreducethememoryfootprint
recoveryandtransactioncontrol.Inaddition,weencapsulateop- andsimplifysynchronization,MirrorBtrmirrorskey-to-leaf-node
timisticretrieswithintheauxiliarystructures,therebyavoiding mappingsratherthanexactrecordpositions(satisfyingR1andR2).
themassiveintrusivecodechangesrequiredbyoptimisticlatching •Non-intrusiveauxiliarystructure.Buildingonleaf-node-level
B-Trees.Traversalsaccesstheauxiliarystructureoncetoobtain mappings,MirrorBtremploysanin-memorylearnedindexwithout
ahintcursorandvalidatethecursorposition,therebyconfining modifyingtheB-Treenodelayout(satisfyingR3).
changestoafewhookpoints.Hence,augmentationentailsfarless •Offlinelearnedindexselection.Anofflinepipelinehelpsto
integrationeffortthanreplacingwithlearnedindexesandadopting
identifyalearnedindexcandidatethatoffersgainswithlowover-
optimisticvariants.Finally,augmentingtheB-Treewithauxiliary
head(satisfyingR1andR2).
structures reduces the number of nodes accessed per traversal,
•Correctandefficientsynchronization.MirrorBtrallowsB-
therebymitigatingindextraversaloverheadandlatchcontention.
Treetraversalstoproceedconcurrentlywithlearnedindexupdates.
Requirements for index augmentation. However, applying
Byenforcingrightwardnodesplitsandmerges,staleresultscanbe
learned models as auxiliary structures to B-Trees is nontrivial.
repairedbymovingrightalongtheleafnodes.Thus,correctness
Therefore,tobebothpracticallyviableandeffective,auxiliarystruc-
andefficiencyareensuredwithoutgloballatches(satisfyingR2).
turesmustsatisfythefollowingstringentrequirements:
Collectively, these design decisions enable MirrorBtr to deliver
•R1:Lightweightmemoryfootprint.Giventhatindexesalready
lowoverhead,seamlessB-Treeintegration,andtraversalspeedups
dominatememoryconsumption[79],theauxiliarystructuremust
acrossdiverseworkloads.Weelaborateoneachcomponentbelow.
bespace-efficient.Otherwise,excessivememoryusagereducesthe
numberofcachedindexnodes,increasingI/Ooverhead. 4.1 Leaf-node-levelMapping
•R2:Correctnesswithlowsynchronizationoverhead.When
AstraightforwardB-Treeaugmentationschememaintainsrecord-
auxiliarystructureupdatesarenotsynchronizedwithB-Treeup- levelmappings,incurringsubstantialspaceandsynchronization
dates,traversalsmayencounterstalemappings.Enforcingstrong costs.Specifically,thisschemestorescorrespondencesbetween
consistencyeliminatesthisstalenessbutincurssubstantialsynchro- keysandtheirexactrecordpositions.Despitelocatingrecordswith
nizationoverhead.Thus,theauxiliarystructuremustminimize asinglelookup,itincursexcessivespaceoverhead:foranindex
synchronizationwhileensuringcorrectness. with 𝑁 records,itrequires𝑂(𝑁) extrastorage,whichbecomes
•R3:Non-intrusiveintegration.AsstatedinSection3.2,index prohibitiveatscale.Moreover,eachrecordmodificationtriggersan
replacementscanalterthephysicalB-Treeformat,incurringdata updatetotheauxiliarystructure,raisingmaintenanceoverhead.
4
Table2:Notationusedinselectionpipeline.
Selection Pipeline (§ 4.3) Database Instance
Dataset Synthesis (§ 4.3.1) Storage Engine
Synthesize subset Expand full dataset Notation Definition
MirrorBtr 𝜖 Absolutemodelpredictionerror
Accelera C t o io s n t E e s ff t e im ct a 𝜶 tion (§ 4.3.2) Lea S r t n ru e c d t u In r d e ex 𝑀 𝑀 𝑠 𝑙 N N u u m m b b e e r r o o f f P P L L A A m m o o d d e e l l s s t t o o k k e e e e p p a a s la m rg a e ll 𝜖 𝜖
Space overhead 𝝃 Total cost 𝒄 Intra-leaf Models 𝑛 Datasetsize
𝑑 Syntheticdatasetstoredintheindex
Sync performance 𝜼 … 𝑖 B-Treeindex
𝑙 Learnedindex
𝑇ℎ𝑑𝑠 Threadcountset
Figure4:Selectionpipelineoverview. 𝑡 Threadcountinset𝑇ℎ𝑑𝑠
𝑤 Operationexecutedontheindex
𝑟
𝑤
Theratioof𝑤
𝑇𝑝 𝑤(𝑖,∅,𝑑,𝑡) Throughputof𝑤 withindex𝑖under𝑑,𝑡
𝑇𝑝 𝑤(𝑖,𝑙,𝑑,𝑡) Throughputof𝑤 when𝑙 augments𝑖under𝑑,𝑡
Toalleviatetheseproblems,MirrorBtradoptsleaf-node-level 𝑆(𝑖,𝑑) Spacecostof𝑖under𝑑
mappingsinstead.Theauxiliarystructuretrackskey-to-leaf-node 𝑆(𝑖,𝑙,𝑑) Spacecostof𝑖and𝑙 when𝑙 augments𝑖under𝑑
mappingsratherthanindividualrecordlocations.SinceaB-Tree 𝛼(𝑖,𝑙,𝑑) Accelerationeffectwhen𝑙 augments𝑖under𝑑
with𝑁 recordsandaleaffanoutof𝑚contains(𝑁/𝑚)leafnodes, 𝜉(𝑖,𝑙,𝑑) Spaceoverheadwhen𝑙 augments𝑖under𝑑
thespacecomplexityreducesto𝑂(𝑁/𝑚).Synchronizationisalso 𝜂(𝑖,𝑙,𝑑) Syncperformancewhen𝑙 augments𝑖under𝑑
simplifiedbecauseupdatesareonlytriggeredbyB-Treestructural
𝑐(𝑖,𝑙,𝑑) Totalcostwhen𝑙 augments𝑖under𝑑
modifications(e.g.,nodesplitsandmerges).Nevertheless,leaf-node-
levelmappingentailsanadditionalintra-leafsearchtolocatethe
record.Tocompensate,MirrorBtremploysleaf-node-levelmapping 4.3 LearnedIndexSelectionPipeline
withlightweightintra-leafmodels.
Existingbenchmarks[62,71]showthattheperformancediversity
oflearnedindexesdemandsdedicatedselection. However,they
4.2 Non-intrusiveAuxiliaryStructure evaluatestandalonelearnedindexes,ignoringtheinteractionswith
Buildinguponleaf-node-levelmappings,MirrorBtremploysanon- B-Treeduringaugmentation.Wethusdesignanofflineselection
intrusiveauxiliarystructure.AsshowninFigure3,thisauxiliary pipelinethatidentifiesthemostsuitableindexunderaugmentation-
structureisalearnedindexconstructedontheoriginalB-Tree.Itis specificmetrics,asillustratedinFigure4.Thisselectionisdecoupled
maintainedentirelyinmemoryandleavestheon-disknodelayout fromtheonlineinstance,offloadingheavyevaluationstoadevel-
unmodified. The learned index stores mappings from separator opmentenvironmentandavoidinginterferencewithforeground
keystoleafnodeIDs,thussupportingthesamesearchmodesas workloads.However,thisdesignrestrictsdirectaccesstorawuser
thevanillaB-Tree.InourInnoDBinstantiation,theseparatorkey dataforprivacycompliance:exportinguserdataoutsidethedata-
istheminimumkeyofeachleafnode.Toreducethelatencyof baseinstanceintroducesleakagerisks.Itmayviolateregulations
intra-leafsearches,aper-leafmodellearnsthekeysintheoffset suchasHIPAAandGDPR[1,82].Toaddressthis,MirrorBtrem-
array.Thismodelresidesinnodemetadataforcachedleafnodes, ploystwokeysteps:(1)Datasetsynthesisthatgeneratesdiversekey
therebypreservingon-disknodelayoutsandavoidingconstruction distributionswithoutviolatingprivacyrules,(2)Costestimation
overheadforinfrequentlyaccessednodes. thatcombinesaugmentation-specificmetricsintoaunifiedcost.
MirrorBtrprovidesaunifiedframeworkforintegratingdiverse ThenotationsinthissectionaresummarizedinTable2.
learnedindexes.Givenemergingadvancesinlearnedindexes[11,
4.3.1 Dataset Synthesis. Sincethe selectionpipelineis isolated
18,50],theframeworkenablesMirrorBtrtoadoptsuitablefuture
fromthedatabasewithuserdataaccessrestrictedunderprivacy
oneswithoutextensivemodifications.Asthelearnedindexresides
policies,wesynthesizeevaluationdatasetsthatmirrorempirical
inmemory,suchadoptionincursnodisk-formatcompatibilityis-
behavior.Priorworkhasestablishedthatlearnedindexperformance
sues.Specifically,theframeworkrequirestheintegratedlearned
dependsprimarilyondistributionalhardnessratherthanspecific
indexestosupportthefollowingconcurrentoperations:
values[46,62,71].Basedonthisinsight,weadoptacontrollable
• last_lt(k):Findthelastkey-valuepairwhosekeyislessthank. synthesizer[71],quantifyingthehardnessusingthenumberof
• last_lt_eq(k):Findthelastkey-valuepairwhosekeyislessthan
piecewiselinearapproximation(PLA)models[75].Specifically,𝑀
𝑙
orequaltok. and𝑀 𝑠 denotethenumberofPLAmodelsforlarge(𝜖 =4096)and
• insert(k,v):Insertthekey-valuepair(k,v)tothelearnedindex. small(𝜖 =32)errorthresholds,capturingglobalnonlinearityand
• update(k,v):Updatethecorrespondingvalueofktov. localfine-grainedfluctuation,respectively.
• delete(k):Removethekey-valuepaircorrespondingtokeyk. Conventional synthesizers directly generate full datasets for
end-to-endindexevaluation[13,71].However,thisapproachis
Accordingly,read-only[32]andsingle-threadedupdatablelearned infeasibleforMirrorBtr,whichisbuiltatoptheoriginalB-Treeand
indexes[11,13,15,72,80]donotmeettherequirements. trainsitslearnedindexonasubsetofB-Treeleafminimumkeys
5
ratherthanthefulldataset.Thisraisesacriticalobservation:the B-Tree Learned Index
distributionalhardnessofthissubsetisnotuniquelydetermined
2
bythatofthefulldataset.Forexample,underfixedglobalhardness
𝑀 𝑙,increasinglocalhardness𝑀 𝑠 tendstoreducethehardnessof … …
| thesubset.Ahigher𝑀 | 𝑠 shrinksthespanoflocalPLAmodelsand | | | | | | |
| ------------------ | ----------------------------------- | --- | --- | --- | --- | --- | --- |
1
decreasesthenumberofkeyspermodel.Whenthesamplingstride … 1 … 1 2
| | | | | 1 splits to 2 | | Insert 2 | |
| --- | --- | --- | --- | ------------- | --- | -------- | --- |
exceedsthiskeycount,onlyafewminimumkeysliewithineach
(a) Leaf node split: Insert new mapping
model.Hence,intra-modelslopedifferencesandlocalperturbations
areheavilyundersampled,filteringoutmostlocalvariations.In
| | | | | B-Tree | | Learned Index | |
| --------------------------- | ----- | -------------------------- | --- | ------ | --- | ------------- | --- |
| addition,evenwithidentical𝑀 | 𝑠and𝑀 | 𝑙,differentplacementsofPLA | | | | | |
breakpointsalterthealignmentbetweensamplingpositionsand
| breakpoints,yieldingminimumkeysubsetswithdistincthardness. | | | | | | | 4 |
| ---------------------------------------------------------- | --- | --- | --- | --- | --- | --- | --- |
…
…
| Therefore,wefirstsynthesizethesubsetforthelearnedindex, | | | | | | | 3->4 |
| ------------------------------------------------------- | --- | --- | --- | --- | --- | --- | ---- |
thenexpanditintoafulldatasetfortheB-Tree,asformalizedin 3 4 … 4 … 3 4
Algorithm1.First,wefixthenumberofkeysperleafnode𝑘,which
| | | | | 3 merges to 4 | Delete 4, update 3 to 4 | | |
| ------------------------------------------------ | --- | --- | ------ | ------------- | ----------------------- | --- | --- |
| isusedonlywithinAlgorithm1,todeterminethesizeof𝑑 | | | 𝑚𝑖𝑛and | | | | |
(b) Leaf node merge: Delete right slibing
| ensure every𝑘-th | key in𝑑 corresponds | to a leaf minimum | key | | | | |
| ---------------- | ------------------- | ----------------- | --- | --- | --- | --- | --- |
mapping, update leaf mapping
(lines1-2).Wethengeneratethetargetleafminimum-keysubset
| 𝑑 𝑚𝑖𝑛withhardness𝑀 | and𝑀 | | | | | | |
| ------------------ | ---- | --- | --- | --- | --- | --- | --- |
𝑠 𝑙 usingacontrollablesynthesizer[71] Figure5:LeafnodesplitandmergewithMirrorBtr.
(line3).Toreservespaceforintra-leafkeysintheB-Tree,wescale
eachminimumkeyfordisjointgaps.Thesegapsarethenfilled
withconsecutivekeystoconstructthefulldataset𝑑(lines4-8).The Thenwecombinethesemetricsintoaunifiedcostmodel:
𝜉(𝑖,𝑙,𝑑)
resultpreservestheintendedhardnessforsubsequentevaluation. 𝑐(𝑖,𝑙,𝑑)=
| | | | | | 𝛼′(𝑖,𝑙,𝑑)·𝜂′(𝑖,𝑙,𝑑) | | (4) |
| --------------------- | ------------------------------------- | --- | -------------- | ----- | ------------------- | ---------------- | ---- |
| 4.3.2 CostEstimation. | Withthesyntheticdatasetgeneratedinthe | | | | | | |
| | | | where𝛼′(𝑖,𝑙,𝑑) | = 1+𝑟 | · (𝛼(𝑖,𝑙,𝑑) | −1) and𝜂′(𝑖,𝑙,𝑑) | = 1+ |
previousstep,weevaluatecandidatelearnedindexesalongthree 𝑟𝑒𝑎𝑑
| | | | 𝑟 (𝜂(𝑖,𝑙,𝑑) | | | effect𝛼 | |
| --- | --- | --- | ----------- | --- | --- | ------- | --- |
augmentation-specificmetricsthatalignwiththedesigngoals: 𝑤𝑟𝑖𝑡𝑒 · −1) are the adjusted acceleration and
| | | | syncperformance𝜂,weightedbyworkloadratios𝑟 | | | 𝑟𝑒𝑎𝑑 | and𝑟 𝑤𝑟𝑖𝑡𝑒. |
| --- | --- | --- | ------------------------------------------ | --- | --- | ---- | ----------- |
• Accelerationeffect𝜶.Asreadsdonottriggersynchronizations,
| | | | Specifically,underread-intensiveworkloads(𝑟 | | | 𝑤𝑟𝑖𝑡𝑒 →0),𝜂′ | →1, |
| --- | --- | --- | ------------------------------------------- | --- | --- | ------------ | --- |
𝛼 quantifiestheaveragereadthroughputgainrelativetotheB-
andthecostisdominatedbytheaccelerationeffect𝛼′.Conversely,
Treeacrossthreadcountsinset𝑇ℎ𝑑𝑠:
𝑇𝑝 𝑟𝑒𝑎𝑑(𝑖,𝑙,𝑑,𝑡) underwrite-intensiveworkloads,thecostisdominatedbysync
| | 1 ∑︁ | | performance𝜂′.Alowercost𝑐indicatesthatthelearnedindex𝑙 | | | | |
| --------- | ---- | --- | ------------------------------------------------------ | --- | --- | --- | --- |
| 𝛼(𝑖,𝑙,𝑑)= | | | (1) | | | | |
|𝑇ℎ𝑑𝑠| 𝑇𝑝 𝑟𝑒𝑎𝑑(𝑖,∅,𝑑,𝑡) isbettersuitedforMirrorBtrondataset𝑑.Section5.2appliesthis
𝑡∈𝑇ℎ𝑑𝑠
| • | | | pipelinetoevaluatecandidatelearnedindexes. | | | | |
| --- | --- | --- | ------------------------------------------ | --- | --- | --- | --- |
Spaceoverhead𝝃.Thismetricmeasuresthesizeratioofthe
combinedB-TreeandMirrorBtrtothevanillaB-Tree:
| | | | 4.4 CorrectandEfficientSynchronization | | | | |
| --- | --- | --- | -------------------------------------- | --- | --- | --- | --- |
𝑆(𝑖,𝑙,𝑑)
| | 𝜉(𝑖,𝑙,𝑑)= | | (2) | | | | |
| --- | --------- | --- | --- | --- | --- | --- | --- |
𝑆(𝑖,𝑑) InMirrorBtr,thelearnedindexmaintainsanindependentkey-to-
| | | | leaf mapping | that is updated | separately | from B-Tree | structural |
| --- | --- | --- | ------------ | --------------- | ---------- | ----------- | ---------- |
• Syncperformance𝜼.Sincesynchronizationwiththelearned
modifications.ThiscreatesatimewindowinwhichtheB-Tree
indexisonlytriggeredbywrites,𝜂capturestheaveragewrite
throughputgainacrossthreadcountsinset𝑇ℎ𝑑𝑠: andthelearnedindexaretemporarilyinconsistent,introducing
twosynchronizationchallenges:(1)correctness:aconcurrenttra-
𝑇𝑝 𝑤𝑟𝑖𝑡𝑒(𝑖,𝑙,𝑑,𝑡)
𝜂(𝑖,𝑙,𝑑)= 1 ∑︁ versalmayuseastaleresultfromthelearnedindextolocatea
(3)
|𝑇ℎ𝑑𝑠| 𝑇𝑝 𝑤𝑟𝑖𝑡𝑒(𝑖,∅,𝑑,𝑡) now-splitormergednode,and(2)efficiency:themappingupdate
𝑡∈𝑇ℎ𝑑𝑠
| | | | may become | a centralized | bottleneck | that serializes | concurrent |
| --- | --- | --- | ---------- | ------------- | ---------- | --------------- | ---------- |
traversals.Toaddress(1),weadapttherightward-onlyinvariants
Algorithm1:Datasetsynthesisforselectionpipeline
fromB-linktrees[21,35]totheinter-indexsetting:B-Treenodes
| Input:datasetsize:𝑛,hardnessparameters:𝑀 | | ,𝑀 | | | | | |
| ---------------------------------------- | --- | --- | --------------------------------------------------------- | --- | --- | --- | --- |
| | | 𝑠 𝑙 | splitandmergeonlytotheright,andtraversalsresolvestaleness | | | | |
Output:fullsyntheticdataset:𝑑
viarightwardsiblingsearch.Toaddress(2),weupdatemappings
𝑘
1 ←fixednumberofkeysperleafnode inthelearnedindexwithoutserializingconcurrenttraversals.The
| 𝑛 ← ⌈𝑛/𝑘⌉ | | | | | | | |
| --------- | --- | --- | --- | --- | --- | --- | --- |
2 𝑙𝑒𝑎𝑓 remainderofthissubsectiondetailssynchronizationmechanisms
| 𝑑 ←hardness_synthesis(𝑛 | ,𝑀 | ,𝑀 𝑙) | | | | | |
| ----------------------- | --- | ----- | --- | --- | --- | --- | --- |
3 𝑚𝑖𝑛 𝑙𝑒𝑎𝑓 𝑠 forinitializationandB-Treestructuralmodifications.
4 𝑑 ←∅
| | | | 4.4.1 Initialization. | ThelearnedindexinMirrorBtrisinitialized | | | |
| -------------- | -------- | --- | ------------------------------------------------------ | --------------------------------------- | --- | --- | --- |
| foreach𝑚𝑖𝑛_𝑘𝑒𝑦 | ∈𝑑 𝑚𝑖𝑛do | | | | | | |
| 5 | | | withallminimumkeysandtheircorrespondingleafnodeIDsfrom | | | | |
𝑠𝑐𝑎𝑙𝑒𝑑_𝑘𝑒𝑦←𝑚𝑖𝑛_𝑘𝑒𝑦×𝑘
6
theB-Tree.Specifically,thisprocesstraversesthelowest-levelinner
| 7 for𝑗 =0to𝑘−1do | | | | | | | |
| ---------------- | --- | --- | --- | --- | --- | --- | --- |
nodes,collectstheminimumkeysandtheirassociatednodeIDs,and
| 𝑑 ←𝑑∪{𝑠𝑐𝑎𝑙𝑒𝑑_𝑘𝑒𝑦+𝑗} | | | | | | | |
| ------------------- | --- | --- | --------------------------------------------------------- | --- | --- | --- | --- |
| 8 | | | loadsthesemappingsintothelearnedindex.Asingletonpatternis | | | | |
employedtopreventredundantindexpopulation.
6
4.4.2 Handlingleafnodesplits. Aleafnodesplitsuponoverflow:a Algorithm2:Locatetheleafnodewithlearnedindex
newleafnodeiscreated,recordsareredistributed,andinnernodes Input:searchkey:𝑘,searchmode:𝑚
areupdatedtoreferencethenewnode.Sincethelearnedindex Output:leafnodecontainingthetargetrecord:𝑙𝑒𝑎𝑓
maintainsitsownmappingfromkeystoleafnodes,aconcurrent
1
𝑙𝑖denotesthelearnedindex
traversalmayquerythelearnedindexbeforethemappingupdate.
2
𝑏𝑝denotesthebufferpool
ThetraversalthenretrievesastaleleafnodeID,onlytofindthetar-
3
𝑙𝑒𝑎𝑓_𝑖𝑑 ←𝑚∈{𝐿𝑇,𝐺𝐸}?𝑙𝑖.𝑙𝑎𝑠𝑡_𝑙𝑡(𝑘):𝑙𝑖.𝑙𝑎𝑠𝑡_𝑙𝑡_𝑒𝑞(𝑘)
getrecordrelocatedtothenewlycreatednode.MirrorBtraddresses
thisbyapplyingrightward-onlysplits;thusthetargetrecordcan 4
𝑙𝑒𝑎𝑓 ←𝑏𝑝.𝑔𝑒𝑡(𝑙𝑒𝑎𝑓_𝑖𝑑)
onlyresideintheoriginallyretrievednodeoritsrightsiblings.We 5
𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑 ←𝑙𝑒𝑎𝑓.𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑
theninsertthemappingforthenewlycreatednodeintothelearned 6
𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 ←true
indexsothatfuturetraversalscandirectlylocateit.Asdetailedin 7
𝑜𝑝 ←𝑚∈{𝐿𝑇,𝐺𝐸}?">":"≥"
Figure5(a),whenleafnode1issplitintonode2,amappingforthe 8 while𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 and𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑isnotnulldo
newleafnode2isinsertedintothelearnedindex.Themapping 9 𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 ←𝑘𝑜𝑝𝑙𝑎𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑙𝑒𝑎𝑓)
updateonthelearnedindexdoesnotneedtoserializeconcurrent 10 if𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 then
traversals,sinceatraversalthatobservesastaleresultcanlocate 11 𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓 ←𝑏𝑝.𝑔𝑒𝑡(𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑)
thecorrectleafviarightwardsiblingsearch.
12
if𝑚∈{𝐺𝐸,𝐺𝑇}then
13
𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 ←true
14 else
15
𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 ←
4.4.3 Handlingleafnodemerges. Aleafnodemergesuponunder- 𝑘𝑜𝑝 𝑓𝑖𝑟𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓)
flowbyconsolidatingwithasibling,triggeringupdatestochild
referencesininnernodes.Aswithnodesplits,whenaconcurrent 16 if𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 then
mergeremovesaleafnodefromtheB-Tree,traversalsmayretrieve 17
𝑙𝑒𝑎𝑓 ←𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓
thisreclaimednode.Similarly,MirrorBtrappliesrightward-only 18
𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑 ←𝑙𝑒𝑎𝑓.𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑
merges and rightward sibling search from B-link trees [21, 35].
Sincemergealwaysconsolidateswiththerightsibling,atraversal 19
return𝑙𝑒𝑎𝑓
thatarrivesatthereclaimednodecanlocatethetargetrecordby
scanningright.ToreflecttheB-Treeleafnodemerge,thelearned
indexisupdatedaccordingly.AsillustratedinFigure5(b),merging 4.5 AcceleratedB-TreeTraversal
node3withitsrightsiblingnode4firstremovesthemappingof MirrorBtraugmentsB-Treewithatwo-stepaccelerationscheme:
node4fromthelearnedindexandthenupdatesthemappingof (1)Leafnodelookup.Thelearnedindexmapssearchkeystoleaf
node3toreferencenode4.Togetherwiththerightwardsibling nodeIDs,skippinginnernodeprobes.(2)Intra-leafmodel-guided
search,adeferredreclamationmechanismisemployedtoensure search.Theintra-leafmodelpredictsaslotintheoffsetarrayto
memorysafetyforconcurrenttraversals.Thismechanismmarks narrowthesearchrange.Thissubsectiondetailsthisscheme.
themergedleafnodeaspendingreclamation,unlinksitfromthe
B-Tree,butdoesnotrecycleitsstorage.Reclamationisdeferredun- 4.5.1 Locateleafnodewithlearnedindex. Readandoptimisticwrite
tilallpre-mergetransactionsarecomplete,sincetraversalscannot operationsdonotincurstructuralmodificationsandcandirectly
accessthereclaimednodeviathelearnedindex.Whenatraversal locate leaf nodes via the learned index. In contrast, pessimistic
encountersanodemarkedaspendingreclamation,itsearchesthe writesrequirelatchcoupling[21]fromtherootnodetomodifythe
rightsiblingsdirectlysincetherecordshavebeenmergedthere. B-Tree,thusunabletoskipinnernodeswiththelearnedindex.
Deferredreclamationensuressafeconcurrencywithnegligible AsdetailedinAlgorithm2,thisprocessfirstqueriesthelearned
overhead.Along-livedtransactiondelaysmergednodereclamation indextoobtainaleafnodeID(line3),thenperformsarightwardsib-
butdoesnotamplifytraversalcost.Onlytraversalsthatqueriedthe lingsearchtolocatethecorrectleaf(lines8–19).Specifically,itcom-
learnedindexbeforetheupdatemaylocatethepending-reclamation
pares𝑘against𝑙𝑎𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑙𝑒𝑎𝑓)todecidewhethertoaccess
node,independentoftransactionduration.OtherB-Treeoperations
therightsibling(line9),using>forLT/GEand≥forLE/GT.Ifmove-
(e.g.,leafnodescans)remainunaffected,astheyneveraccessun- mentisneeded,thealgorithmfetchestherightsiblingandvalidates
linkednodes.SinceOLTPtransactionsaretypicallyshort-lived[4],
themovebycomparing𝑘against𝑓𝑖𝑟𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓);GE
mergednodesarereclaimedpromptly. andGTmodesalwaysmovebecausethecurrentleafdoesnotcon-
Inaddition,MirrorBtrcorrectlyresolvesanintermediatestate tain the first record satisfying these modes (lines 12–15). If the
duringlearnedindexupdates.Considerthetransientintervalafter move is confirmed, the algorithm advances to the right sibling
deletingthemappingfornode4butbeforeupdatingthemapping anditerates;otherwise,itterminatesandreturnsthecurrentleaf
fornode3.Duringthisinterval,traversalsforkeysinnode4tem- (lines16–18).Nodesmarkedaspendingreclamationredirecttra-
porarilyresolvetonode3.Uponreachingnode3,thetraversalac- versalsimmediatelytotheirrightsiblings.
quiresareadlatchandfindsitmarkedaspendingreclamation.The Correctnessanalysis.Weprovecorrectnessviaaloopinvariant:
traversalthenaccessesitsrightsiblingnode4,wherethemerged atthestartofeachwhile-loopiteration(line8),thetargetrecord
recordresides.Itthusautomaticallyrecoversfromthisintermediate residesin𝑙𝑒𝑎𝑓 oroneofitsrightsiblings.(1)Initialization.With-
stateandensurescorrectness. outconcurrentmodifications,thelearnedindexreturnstheexact
7
𝑙𝑒𝑎𝑓_𝑖𝑑viaerrorcorrectioninlearnedindexes[11,32].Withcon-
currentsplitsormerges,therightward-onlyinvariantsfromB-link 20
trees[21,35]ensurethetargetcanonlyresideintheretrievednode 15
oritsrightsiblings.(2)Maintenance.Eachiterationcompares𝑘 10
5
against𝑙𝑎𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑙𝑒𝑎𝑓)and𝑓𝑖𝑟𝑠𝑡_𝑖𝑛𝑑𝑒𝑥_𝑘𝑒𝑦(𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓).If
0
thetargetliesbeyond𝑙𝑒𝑎𝑓,thealgorithmadvancestotheright 0
#
2
o
0
f o
4
p
0
e
6
r
0
at
8
io
0
n
1
s
00
sibling,preservingtheinvariant.(3)Termination.Theloopex-
itswhen(a)𝑚𝑜𝑣𝑒_𝑟𝑖𝑔ℎ𝑡 isfalse,confirmingthetargetfallswithin
𝑙𝑒𝑎𝑓’skeyrange,or(b)𝑛𝑒𝑥𝑡_𝑙𝑒𝑎𝑓_𝑖𝑑isnull,meaningnorightsib-
lingexists.Inbothcases,theinvarianteliminatesthe“rightsiblings”
possibility,sothetargetmustresideinthereturned𝑙𝑒𝑎𝑓.
Efficiencytrade-off.Therightwardsiblingsearchtradesraresu-
perfluoussiblingfetchesforanon-intrusiveaugmentationrequire-
ment. For example, consider an LT query with key𝑘 that falls
betweenaleaf’slastkeyanditsrightsibling’sfirstkey.Thesib-
lingisfetchedforvalidation,butnomovementisperformedsince
itsfirstkeyexceeds𝑘.Storingtherightsibling’sfirstkeyinthe
currentnodeeliminatestheseredundantfetches.Nevertheless,it
necessitatesmodifyingtheB-Tree’sphysicallayout,violatingthe
non-intrusiveintegrationrequirement(R3inSection3.3).
4.5.2 Searchleafnodewithintra-leafmodel. Uponreceivinganew
query,theintra-leafmodelpredictsapositionwithintheoffset
array,andanexponentialsearchaccuratelylocatesthetargetslot.
Inasparselayout(e.g.,InnoDB[64]),eachslotcoversagroupof
records,requiringalinearscantofindtherecord.Inadenselayout
(e.g.,PostgreSQL[25]),theslotdirectlyyieldsthetargetrecord.
Intra-leafmodelselection.Webeginwithlinearmodelsdueto
theircomputationalefficiency[11,17]andwideadoption[9,13,40].
Whilecomplexmodelssuchasneuralnetworksarealsoexplored
inlearnedindexes[32,73],theiraddedcomplexityisrarelyjus-
tifiedbymarginalperformancegains[11,40].Weevaluatethree
representativecandidatestoidentifyaneffectiveone:linearregres-
sion(LR)andtwopiecewiselinearregression(PLR)variants[75],
namelyOptimalPLRandGreedyPLR.Theevaluationusesthree
real-worlddatasets:genome[71],osm[46],andlibio[71](seeSec-
tion5.1fordetails).Wefirstbuildeachmodelandmeasureitsspace
andconstructioncost.Wethenperform50deletesfollowedby50
inserts,recordingtheaveragepredictionerroraftereachroundand
theaveragesearchlatencyacrossallrounds.AsillustratedinFig-
ure6(a)–(c),allthreemodelsexhibitasawtootherrorpatternrather
thanmonotonicdegradation.AlthoughLRexhibitsthehighester-
ror,Figure6(d)showsthatitachievesthelowestaveragesearch
latency,whichisconsistentlylowerthanthatofbinarysearch.This
isbecausePLR’serror-boundedsegmentationyieldsmultipleseg-
mentsperleafnode,forcingeachsearchtolocateanapplicable
segment.Moreover,Figure6(e)–(f)showsthatPLRincurshigher
spaceandconstructioncosts.Overall,LRispreferredduetoits
fastersearch,fixedspace,andsimpleconstruction.
Intra-leafmodelconstruction.Intra-leafmodelsarebuiltlazily
uponfirstaccesstothatleaf,usingasingletonguardtoavoidcon-
currentredundanttraining.Thisprocessscansrecordsintheoffset
arrayandtrainsamodelthatmapsrecordkeystoslotpositions.
Intra-leafmodelupdates.Theintra-leafmodelisrebuiltupon
changestotheoffsetarraystructure.Forsparseoffsetarrays(e.g.,
pagedirectoryinInnoDB),anewslotiscreatedwhenthesizeofa
rorrE
20
15
10
5
0
0 20406080100
# of operations
(a) Error on genome
rorrE
20
15
10
5
0
0 20406080100
# of operations
(b) Error on osm
rorrE
(c) Error on libio
300
200
100
0
genomeosm libio
Datasets
sn
200
150
100
50
0
genomeosm libio
Datasets
(d) Search latency
etyB
8000
6000
4000
2000
0
genomeosm libio
Datasets
(e) Model size
sn
LR GreedyPLR OptimalPLR
LR GreedyPLR OptimalPLR
(f) Model build latency
Figure6:Intra-leafmodelevaluationresults.Thedashedline
insubfigure(d)representsbinarysearchlatency.
recordgroupexceedsthemaximumthreshold,andadjacentslots
mergeifthesizefallsbelowtheminimum.Whentriggered,the
intra-leafmodelisretrainedbyscanningrecordsintheoffsetarray.
Fordenseoffsetarrays,entrycounttrackstherecordcountdirectly,
thusrequiringmorefrequentretraining.
5 EVALUATION
5.1 ExperimentalSetup
Platform. All experiments are run on an Ubuntu 22.04 server
equippedwithtwo24-coreIntelXeonGold5318Yprocessors(hyper-
threadingenabled)and512GBofRAM.WeimplementMirrorBtron
theInnoDBstorageengineinMySQL8.0.41andmakethesource
codepubliclyavailable1.
Baseline.WecompareagainsttwoInnoDBbuilt-inbaselines.
• B-TreeisthedefaultindexinInnoDB,whichisabalancedtree
forefficientpointandrangequeries.
• AdaptiveHashIndex(AHI)[63]isanin-memory,hash-based
auxiliarystructurethataccelerateslookupsbymappingkeysto
recordpointers,thusavoidingmulti-levelB-Treetraversal.
Datasets.Theevaluationsusethefollowingdatasets,mostofwhich
arereal-worlddatasetsfromSOSD[46]andGRE[71]benchmarks.
Amongthem,osmandgenomeexhibithighernonlinearity,posing
greaterchallengesforlearnedmodels[71].
• autoinc[66]referstotheauto-incrementedsequencenumbers,
whichserveasthedefaultindexkeyinSysbench[30].
• libio[71]containstheRepositoryIDsfromlibraries.io.
• osm[46]isderivedfromuniformlysampledOpenStreetMap
locationcoordinates.
• genome[71]iscreatedfromlocipairsinhumanchromosomes.
Workloads.WeextendtheSysbench[30]workloadsasfollows.In
eachexperiment,wepopulatethedatabasewith100millionrecords
andrunbenchmarkoperationsfor30seconds.
• Secondary index range query issues range queries on the
secondaryindexwitharangesizeof100.
1https://github.com/unconsolable/MirrorBtr
8
| | | | | | | ALEX+ | SALI | LOFT | |
| --- | --- | --- | --- | ------------ | --- | ------------ | ---- | ------------ | --- |
| | | | | 2.0 | | 2.0 | | 2.0 | |
| | | | | )c( tsoC 1.5 | | )c( tsoC 1.5 | | )c( tsoC 1.5 | |
Small Ms, Small MlLarge Ms, Small MlSmall Ms, Large MlLarge Ms, Large Ml 1.0 1.0 1.0
| | | | | 0.5 | | 0.5 | | 0.5 | |
| ----------------------------- | --- | ---- | --- | --- | --- | --- | --- | --- | --- |
| | | | | 0.0 | | 0.0 | | 0.0 | |
| Figure7:SyntheticsubsetCDFs.𝑀 | | and𝑀 | | | | | | | |
𝑠 𝑙 controllocaland 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0
globalhardness,respectively. Write ratio (rwrite) Write ratio (rwrite) Write ratio (rwrite)
| | | | | Small Ms Small Ml | | Large Ms Small Ml | | | libio |
| --- | --- | --- | --- | ----------------- | --- | ----------------- | --- | --- | ----- |
| | | | | 2.0 | | 2.0 | | 2.0 | |
Table3:Averagespeedupratioandlearnedindexsize.The )c( tsoC 1.5 )c( tsoC 1.5 )c( tsoC 1.5
| | | | | 1.0 | | 1.0 | | 1.0 | |
| -------------------------- | --------------------------------------- | -------------- | -------------- | -------------------- | ----------- | -------------------- | --------------- | ------- | -------------------- |
| bestvaluesaremarkedinbold. | | | | 0.5 | | 0.5 | | 0.5 | |
| | | | | 0.0 | | 0.0 | | 0.0 | |
| | | | | 0.0 0.2 | 0.4 0.6 0.8 | 1.0 0.0 | 0.2 0.4 0.6 0.8 | 1.0 0.0 | 0.2 0.4 0.6 0.8 1.0 |
| Dataset | libio | osm | genome | | | | | | |
| | | | | Write ratio (rwrite) | | Write ratio (rwrite) | | | Write ratio (rwrite) |
| | | | | Small Ms Large Ml | | Large Ms Large Ml | | | osm |
| Algorithm | ALEX+SALILOFTALEX+SALILOFTALEX+SALILOFT | | | | | | | | |
| SpeedupRatio | 1.62 1.59 1.08 | 1.28 1.02 0.84 | 1.42 1.38 0.97 | | | | | | |
Figure8:Costmodelevaluationresults.
| Size(MB) | 71.4 52.7 81.4 | 87.9 226.8 76.2 | 72.2 84.2 79.9 | | | | | | |
| -------- | -------------- | --------------- | -------------- | --- | --- | --- | ------ | --------- | --- |
| | | | | | | AHI | B-Tree | MirrorBtr | |
• Primaryindexnested-loopjoinperformsindexjoinsonthe
| | | | | 160 | | | 160 | | |
| --------------------------------------------- | --- | --- | --- | ------- | --- | --- | ---- | --- | --- |
| | | | | 30 | | | | 30 | |
| primaryindexusing100randomlyselectedjoinkeys. | | | | 120 20 | | | 120 | 20 | |
| | | | | SPQK 10 | | | SPQK | 10 | |
• Read-writeonindexesrunsatransactionofpointqueries,sec- 80 0 80 0
| | | | | | 1 2 4 | 8 | | 1 2 4 | 8 |
| --- | --- | --- | --- | --- | ----- | --- | --- | ----- | --- |
ondaryindexrangequeries,updates,andpaireddelete-inserts. 40 40
| | | | | 0 | | | 0 | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
• Write-onlyonindexesinsertstoboththeprimaryandsec-
| | | | | 1 | 2 4 8 | 163264128 | | 1 2 4 | 8 163264128 |
| --- | --- | --- | --- | --- | ----- | --------- | --- | ----- | ----------- |
ondaryindexes.
| | | | | | Threads | | | Threads | |
| ---------------------------------------------------- | --- | --- | --- | --- | ------- | --- | --- | ------- | --- |
| • | | | | | autoinc | | | | osm |
| Skewedinsertspreloadstwonon-contiguouskeysegmentsand | | | | 160 | | | 160 | | |
| | | | | 30 | | | | 30 | |
concentratesconcurrentinsertsinthegapbetweenthem[18]. 120 20 120 20
| | | | | SPQK 10 | | | SPQK | 10 | |
| --- | --- | --- | --- | ------- | --- | --- | ---- | --- | --- |
• Intrinsic-orderinsertsissueinsertsunderpartialdatasorted- 80 0 80 0
| | | | | | 1 2 4 | 8 | | 1 2 4 | 8 |
| --------------------------------------- | --- | --- | --- | --- | ----- | --------- | --- | ----- | ----------- |
| nessusingthe(𝐾,𝐿)-sortednessmetric[59]. | | | | 40 | | | 40 | | |
| | | | | 0 | | | 0 | | |
| | | | | 1 | 2 4 8 | 163264128 | | 1 2 4 | 8 163264128 |
5.2 LearnedIndexSelection
| | | | | | Threads | | | Threads | |
| --- | --- | --- | --- | --- | ------- | --- | --- | ------- | ----- |
| | | | | | genome | | | | libio |
Thisexperimentidentifiesthelearnedindexusedinsubsequent
evaluations.WeconsiderALEX+[71],SALI[18]andLOFT[50]as
Figure9:Throughputofsecondaryindexrangequery.
candidates,whileHyper[83]isexcludedduetounavailablesource
code.Weintegratetheselectionpipelineintoanin-memoryB-link
tree[7]andevaluatecostoverfoursyntheticdatasetswhosesub-
setCDFsareshowninFigure7.AsreportedinFigure8,ALEX+ expansion.Weduplicatetherootandboundaryleafnodes,modify
achievesthelowestcostacrossmostsettingsbecauseitstoresmap- thecopies,thenatomicallywritebackpointers,withallmodifica-
tionsserializedviaper-nodelatches.
pingssolelyindatanodes,enablingsiblingscanswithoutparent
backtracking.SALIincursparentbacktrackingforsiblingscansdue
5.3 In-memoryWorkloads
toco-locatedmappingsandsubtreepointers,alongwithmemory
overprovisioning[40],whileLOFTmustscanextramappingsdue 5.3.1 Traversal-intensivequeries. Thisexperimentmeasuresthe
totheirunsortedorder,sobothincurhighercost.Consistentper- throughputunderworkloadsdominatedbyrepeatedprimaryindex
formancetrendsonsyntheticandreal-worlddatasets(libioand traversals,usingsecondaryindexrangequeriesandprimaryindex
osm)validatetheuseofsyntheticdataforcostestimation. nested-loopjoinsasrepresentativecases.Figure9andFigure10
Tovalidatethecostestimation,wemeasuretheaveragespeedup reportthatMirrorBtrconsistentlyoutperformsallbaselinesunder
ratioandlearnedindexsizewithwriteratiosfrom0to1(step0.2). thesequeries.Forrangequeries,MirrorBtroutperformsAHIand
AsshowninTable3,ALEX+achievesthehighestspeedupratio B-Treebyupto5.60×and7.45×,respectively.Fornested-loopjoins,
theperformancegainsreach5.81×and7.26×,respectively.This
acrossallthreedatasetswithcompetitivespaceoverhead.Thus,the
costmodelcorrectlyidentifiestheoptimalcandidate,andweselect stemsfromMirrorBtr’straversalwithALEX+,whichemployslatch-
ALEX+ for subsequent evaluations. Notably, while we evaluate freereadsandoptimisticlatchingondatanodes,sothetraversal
state-of-the-artindexes,MirrorBtrcaneasilyincorporatefuture onlyacquiresareadlatchoneachB-Treeleafnode.Nevertheless,B-
advanceddesignsandidentifythesuitableone. Treeremainscompetitiveatlowconcurrency(i.e.,<8threads)since
ALEX+lackssupportforstructuralmodificationsontheroot latchcontentionisminor.Evenso,MirrorBtrstilldeliversconsistent
node, making insertions beyond key boundaries prone to dead- gainsbyreducingtraversallatency,asshowninthezoomedinsetof
locks[50].Toresolvethisissuewhilepreservinglatch-freeinner- Figure9and10.Specifically,MirrorBtrimprovesthroughputover
nodereadsofALEX+,weadoptacopy-on-writeschemeforroot B-Treebyanaverageof1.47×forsecondaryindexrangequeries
9
| | | | AHI | B-Tree | MirrorBtr | | | | AHI | B-Tree | MirrorBtr | |
| ---- | ------ | ----- | --- | -------- | --------- | --- | ------- | --- | --- | ------- | --------- | --- |
| | 160 | | | 160 | | | 120 | | | 120 | | |
| | 30 | | | | 30 | | | | | | | |
| SPQK | 120 20 | | | SPQK 120 | 20 | | | | | | | |
| | 10 | | | | 10 | | SPTK 80 | | | SPTK 80 | | |
| | 80 0 | | | 80 | 0 | | | | | | | |
| | 40 | 1 2 4 | 8 | 40 | 1 2 | 4 8 | 40 | | | 40 | | |
| | 0 | | | 0 | | | | | | | | |
| | | | | | | | | 0 | | 0 | | |
1 2 4 8 163264128 1 2 4 8 163264128 osm libio genome osm libio genome
| | | Threads | | | | Threads | | | | | | |
| ---- | ------ | ------- | --- | ---- | --- | ------- | --- | ------------------ | ------- | --- | --------------------------- | ------- |
| | | | | | | | | | Dataset | | | Dataset |
| | | autoinc | | | | osm | | (a) Skewed Inserts | | | (b) Intrinsic-order inserts | |
| | 160 | | | 160 | | | | | | | | |
| | 30 | | | | 30 | | | | | | | |
| | 120 20 | | | 120 | 20 | | | | | | | |
| SPQK | 10 | | | SPQK | 10 | | | | | | | |
80 0 80 0 Figure12:Throughputofskewedandintrinsic-orderinserts.
| | | 1 2 4 | 8 | | 1 2 | 4 8 | | | | | | |
| --- | --- | ------- | --------- | --- | ----- | ----------- | ---- | --- | --- | --- | --- | --- |
| | 40 | | | 40 | | | | | | | | |
| | 0 | | | 0 | | | | | | | | |
| | 1 | 2 4 8 | 163264128 | | 1 2 4 | 8 163264128 | | | | | | |
| | | Threads | | | | Threads | 3000 | | | | | |
AHI (autoinc)
| | | genome | | | | libio | )BM( eziS 2500 | 2304.6 | | | | |
| --- | --- | ------ | --- | --- | --- | ----- | -------------- | ------ | --- | --- | --- | ------------------- |
| | | | | | | | 2000 | | | | | MirrorBtr (autoinc) |
| | | | | | | | 1500 | | | | | MirrorBtr (osm) |
| | | | | | | | 1000 | | | | | MirrorBtr (genome) |
Figure10:Throughputofprimaryindexnested-loopjoins. 500 MirrorBtr (libio)
| | | | | | | | | | 106.3 123.0 | 111.6 | 110.4 | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | ----------- | ----- | ----- | --- |
0
AHI B-Tree MirrorBtr Figure13:SpaceoverheadofAHIandMirrorBtr.
| | 160 | | | 160 | | | | | | | | |
| ---- | --- | ----- | --------- | -------- | ----- | ----------- | ----------------------------------------------------- | --- | -------------------------------- | --- | --- | --- |
| SPTK | 120 | | | SPTK 120 | | | | | | | | |
| | 80 | | | 80 | | | | | | | | |
| | 40 | | | 40 | | | thefractionofout-of-orderentriesand𝐿denotesthemaximum | | | | | |
| | 0 | | | 0 | | | displacement.Weset | | (𝐾=25%,𝐿=25%),underwhichthewrite | | | |
| | 1 | 2 4 8 | 163264128 | | 1 2 4 | 8 163264128 | | | | | | |
Threads Threads throughputofALEXdropsby36%[59].AsshowninFigure12,
autoinc osm MirrorBtroutperformsthebest-performingbaseline,B-Tree,by
| | 200 | | | 200 | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
11.5%underskewedinsertsand18.9%underintrinsic-orderinserts.
| | 150 | | | 150 | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
SPTK SPTK TheadvantageofMirrorBtrisnotdiminishedbecauseupdatesto
| | 100 | | | 100 | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
50 50 thelearnedindexareonlytriggeredbyB-Treeleafnodesplitsand
| | 0 | | | 0 | | | | | | | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
merges.Hence,theoverheadoflearnedindexupdatesiseffectively
| | 1 | 2 4 8 | 163264128 | | 1 2 4 | 8 163264128 | | | | | | |
| --- | --- | ------- | --------- | --- | ----- | ----------- | ----------------------------- | -------------- | --------------------------------- | --- | --- | --- |
| | | Threads | | | | Threads | amortizedbyindividualinserts. | | | | | |
| | | genome | | | | libio | | | | | | |
| | | | | | | | 5.3.4 | Spaceoverhead. | Figure13comparesthememoryoverhead | | | |
betweenAHIandMirrorBtr.AHI’sspaceisconstantacrossdistri-
Figure11:Throughputofwrite-onlyonindexes.
butions,sotheresultontheautoincdatasetsufficesforothers.In
contrast,thememoryfootprintofMirrorBtrvariesslightlywith
| | | | | | | | dataset | hardness. | At minimum, | MirrorBtr | incurs | only 4.61% of |
| --- | --- | --- | --- | --- | --- | --- | ------- | --------- | ----------- | --------- | ------ | ------------- |
with2threads.Amongthebaselines,AHIoutperformsB-Treeby
AHI’ssize,equivalentto0.51%ofthe20.44GBB+-Treeindexsize.
bypassingtreetraversal,butitssingleread-writelatchperhash
tablelimitsscalability.B-Treesuffersfromlatchcontentionatevery Thissubstantialsavingoriginatesfromtheirdivergentmapping
leveloftheroot-to-leafpath. granularities.AHIcachesrecord-levelmappingsproportionaltothe
numberofrecords,whereasMirrorBtrmaintainsleaf-node-level
5.3.2 Write-onlyonindexes. Thisexperimentevaluatesinsertper- mappings,resultinginfarfewerentries.
| formance | under | distinct | patterns: | autoinc | and | osm produce se- | | | | | | |
| -------- | ----- | -------- | --------- | ------- | --- | --------------- | --- | --- | --- | --- | --- | --- |
quentialinserts,whilegenomeandlibioproducerandominserts.
5.4 Larger-than-memoryWorkloads
Figure11showsthatMirrorBtroutperformsbaselines,thoughthe
Thissectionevaluatesperformancewhenthedatasetexceedsbuffer
improvementismodest(reasonsdetailedinSection5.6.2).MirrorBtr
poolcapacity.Weevaluatesecondaryindexrangequeriesandread-
benefitssequentialinsertsmorethanrandominserts,becausese-
writequeriesusing16threadswhilevaryingthebufferpoolsize.
quentialinsertsconfinesplitstotherightmostleaf,causingmost
AsshowninFigure14,MirrorBtroutperformsallbaselines,achiev-
threadstoacquirelatchesonthesameinnernodes.MirrorBtr’s
ingupto2.29×higherthroughputoverB-Treeforrangequeries
learnedindexbypassesinnernodesandlocatesthetargetleafdi-
and1.53×forread-writequeries.AHIconsistentlyunderperforms
rectly,relievingsuchlatchcontention.
B-Treesinceitsrecord-levelmappingsconsumeexcessivememory,
5.3.3 Learnedindexstresstest. Sincelearnedindexesmaydegrade thuscompetingwiththeB-Treeforlimitedbufferpoolspaceand
underskewed[18,62]andintrinsic-orderinserts[59],weevaluate incurringadditionalI/O.Incontrast,MirrorBtradoptsleaf-node-
MirrorBtrunderthesetwochallengingpatternswith64threads. levelmappings,significantlyreducingspaceoverheadandleaving
Skewedinsertsfirstsorttheentiredatasetandpreloadtwonon- morememoryforB-Tree.Moreover,itsacceleratedtraversalfur-
contiguoussegments(0–50millionand75–125million),theninsert therimprovesthroughput.Asthebufferpoolsizegrows,reduced
a segment (50–75 million) as a concentrated hotspot. Intrinsic- I/OshiftsthebottlenecktoCPU,furtheramplifyingMirrorBtr’s
orderinsertsusethe (𝐾,𝐿)-sortednessmetric,where𝐾 denotes traversalacceleration.
10
AHI B-Tree MirrorBtr buffer-pool (w/ latch) auxiliary-index page-search
| 30 | | | 30 | | | | 5 | | | 5 | | | |
| ---- | --------------------- | ----------- | ---- | ----------------------- | ----------- | ------------ | ------ | ------- | -------------- | ------------ | ---- | ---- | ----------- |
| 25 | | | 25 | | | )su( ycnetaL | | | | )su( ycnetaL | | | |
| SPQK | | | SPQK | | | | 4 | | | 4 | 3.22 | 3.09 | |
| 20 | | | 20 | | | | 3 2.93 | | 2.63 | 3 | | | |
| 15 | | | 15 | | | | | 2.01 | 2.15 1.91 | | 2.02 | | 2.47 2.29 |
| 10 | | | 10 | | | | 2 | | | 2 | | | |
| | 5 | | | 5 | | | | | | | | | |
| | 0 | | | 0 | | | 1 | | | 1 | | | |
| | | | | | | | 0 | | | 0 | | | |
| | 10 12 | 14 16 18 20 | | 10 12 | 14 16 18 20 | | | | | | | | |
| | | | | | | | B-Tree | AHI | IM LIMirrorBtr | B-Tree | AHI | IM | LIMirrorBtr |
| | Buffer Pool Size (GB) | | | Buffer Pool Size (GB) | | | | autoinc | | | | osm | |
| | Secondary Range (osm) | | | Secondary Range (libio) | | | | | | | | | |
| | 5 | | | 5 | | | | | | | | | |
(a)Single-threadedexecution.
| | 4 | | | 4 | | | | | | | | | |
| ------------------------------------------------ | --------------------- | ----------- | ---- | --------------------- | ----------- | ------------ | ------ | ---------------------- | -------------- | --------------- | ---------- | ----------- | ----------- |
| SPTK | 3 | | SPTK | 3 | | | | | | | | | |
| | 2 | | | 2 | | | | buffer-pool (w/ latch) | | auxiliary-index | | page-search | |
| | 1 | | | 1 | | | | | | | | | |
| | | | | | | )su( ycnetaL | 50 | | | )su( ycnetaL 50 | | | |
| | 0 | | | 0 | | | 40 | | | 40 | | | |
| | 10 12 | 14 16 18 20 | | 10 12 | 14 16 18 20 | | 29.16 | | | | 33.37 | 32.20 | |
| | | | | | | | 30 | | 26.86 | 30 | | | |
| | Buffer Pool Size (GB) | | | Buffer Pool Size (GB) | | | 20 | | | 20 | | | |
| | Read Write (osm) | | | Read Write (libio) | | | | | | | | | |
| | | | | | | | 10 | 7.66 | | 10 | 7.53 | | |
| | | | | | | | | | 3.17 2.88 | | | | 3.68 3.49 |
| | | | | | | | 0 | | | 0 | | | |
| | | | | | | | B-Tree | AHI | IM LIMirrorBtr | | B-Tree AHI | IM | LIMirrorBtr |
| Figure14:Throughputwithdifferentbufferpoolsizes. | | | | | | | | autoinc | | | | osm | |
(b)64-threadedexecution.
| | | AHI | B-Tree | MirrorBtr | | | | | | | | | |
| ---- | --- | --- | ------ | --------- | --- | --------------------------------------------------- | --- | --- | --- | --- | --- | --- | --- |
| 50 | | | 50 | | | | | | | | | | |
| 40 | | | 40 | | | Figure16:Breakdownofprimaryindextraversal.MirrorBtr | | | | | | | |
| SPQK | | | SPQK | | | | | | | | | | |
| 30 | | | 30 | | | | | | | | | | |
20 20 ablations:LI(learnedindexonly),IM(intra-leafmodelonly).
| 10 | | | 10 | | | | | | | | | | |
| --- | -------- | ------- | --- | -------- | ------- | ------------ | --- | --- | --------- | --------------- | ------ | --- | --- |
| | 0 | | | 0 | | | | | | | | | |
| | 0 60 | 120 180 | | 0 60 | 120 180 | | | | | | | | |
| | Time (s) | | | Time (s) | | | | | traversal | | modify | | |
| | autoinc | | | genome | | )su( ycnetaL | 40 | | | )su( ycnetaL 40 | | | |
32.38
| | | | | | | | 30 | 23.60 | | 30 | 27.23 | 25.40 | 24.66 |
| -------------------------------------------- | --- | --- | --- | --- | --- | --- | ----------------------- | ----- | ------------ | --- | ---------------------- | ------ | --------- |
| | | | | | | | 22.99 | | 21.97 20.44 | | | | |
| Figure15:Throughputonafreshinstanceovertime. | | | | | | | 20 | | | 20 | | | |
| | | | | | | | 10 | | | 10 | | | |
| | | | | | | | 0 | | | 0 | | | |
| | | | | | | | B-Tree | AHI | LI MirrorBtr | | B-Tree | AHI LI | MirrorBtr |
| | | | | | | | Sequential Insert (osm) | | | | Random Insert (genome) | | |
5.5 ConstructionTime
Thisexperimentevaluatesthewarm-uptimetoreachsteady-state (a)Single-threadedexecution.
throughputfromacoldstart.Weexecutesecondaryindexrange
| | | | | | | | | | traversal | | modify | | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --------- | --- | ------ | --- | --- |
queriesonfreshlyinitializedinstanceswith16threadsandtrack
| | | | | | | )sm( ycnetaL | 0.8 | | | )sm( ycnetaL 0.8 | | | |
| ----------------------------------------------------- | --- | --- | --- | --- | --- | ------------ | -------- | ---- | --- | ---------------- | --- | ---- | --- |
| throughputovertime.AsshowninFigure15,MirrorBtrreaches | | | | | | | | 0.62 | | | | | |
| | | | | | | | 0.6 0.59 | | | 0.6 | | 0.54 | |
stableperformancewithin20seconds,comparabletothebaseline
| | | | | | | | 0.4 | | 0.39 | 0.36 0.4 | 0.40 | 0.32 | |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | ---- | -------- | ---- | ---- | --- |
0.29
B-Tree.Thisefficiencyisattributedtoitslightweightconstruction, 0.2 0.2
whichonlyscansthelowest-levelinnernodestobuildthelearned 0.0 0.0
| | | | | | | | B-Tree | AHI | LI MirrorBtr | | B-Tree | AHI LI | MirrorBtr |
| --- | --- | --- | --- | --- | --- | --- | ------ | --- | ------------ | --- | ------ | ------ | --------- |
indexinlessthan2seconds.Inaddition,intra-leafmodelsarelazily
| | | | | | | | Sequential Insert (osm) | | | | Random Insert (genome) | | |
| --- | --- | --- | --- | --- | --- | --- | ----------------------- | --- | --- | --- | ---------------------- | --- | --- |
trainedupontheirfirstaccess,avoidingcentralizedbottlenecks.
Incontrast,AHItakesmorethan1minutetowarmupbecause (b)64-threadedexecution.
itpopulatesahashtablewithmassiverecord-levelmappings.Its
throughputrisesgraduallyasentriesareimported. Figure17:Breakdownofinsertion.MirrorBtrablations:LI
(learnedindexonly).
5.6 PerformanceBreakdown
| 5.6.1 | Primaryindextraversallatencybreakdown. | | | | Wemeasurepri- | | | | | | | | |
| ----- | -------------------------------------- | --- | --- | --- | ------------- | --- | --- | --- | --- | --- | --- | --- | --- |
under1threadand7.8%under64threads.Combiningbothcom-
maryindextraversallatencyonsecondaryindexrangequeries,
ponents,MirrorBtrreducessingle-threadedtraversallatencyby
sinceeachquerytraversestheprimaryindextofetchafullrecord
34.8%and64-threadedlatencyby90.1%onautoinc.Thelatency
foreachmatchingkey,makingitthedominantcost.Toisolatecom-
reductionissmalleronosm(28.8%under1threadand89.5%under
ponentcontributions,wefurtherevaluatetwoablationvariants,LI
64threads),asitslesslinearCDFincreasesboththetreeheight
(learnedindexonly)andIM(intra-leafmodelonly).Asillustrated
ofALEX+andthepredictionerrorofintra-leafmodels.Giventhe
inFigure16,learnedindexistheprimarycontributortolatency
modestcontributionofIM,subsequentanalysesomitthisvariant.
reduction.Onautoinc,LIreducessingle-threadedtraversallatency
by26.6%overB-Treebyskippingbufferpoolaccessesandsearches 5.6.2 Insertionlatencybreakdown. Toanalyzethereasonsbehind
oninnernodes.Under64threads,LIachieves89.1%reductionby themodestimprovementofMirrorBtrunderinsertionworkloads,
eliminatinglatchcontentiononinnernodes.IMpredictspositions wedecomposeitslatencyinFigure17.Underasinglethread,mod-
withintheoffsetarrayofleafnodes,reducinglatencyby10.2% ificationdominatesthelatency,leavinglittleroomfortraversal
11
acceleration.Under64threads,nodesplitsblockconcurrenttraver- integration,shownbyrecenteffortsinrelationalDBMSs[56,86].Pi-
salsduetoInnoDB’sB-Treeconcurrencycontrol.MirrorBtrreduces lotScope[86]providesageneralframeworkonPostgreSQLforknob
insertionlatencybyacceleratingtraversalsofoptimisticinsertions. tuning,indextuning,cardinalityestimation,andqueryoptimiza-
However,itcannotmitigatethewrite-sideblockingduringnode tion.NeurDB[84]incorporateslearnedconcurrencycontroland
splits,offeringlimitedimprovementtoconcurrentscalability. queryoptimizationintoPostgreSQL.RedshiftMDDL[10]learnsfre-
quentscanpredicatestoreorganizedatalayoutforblockskipping.
6 DISCUSSIONANDFUTUREDIRECTIONS Incontrast,theintegrationoflearnedindexesremainsunderex-
plored.MirrorBtrsupportsdiverseupdatablelearnedindexesto
Extendtootherdatabases.AlthoughMirrorBtrisimplementedin
accelerateB-Treetraversalandalleviatelatchcontention.
InnoDB,itsdesignisdatabase-agnostic.PortingMirrorBtrrequires:
(1)inner-nodeseparatorkeystoinitializethelearnedindex,(2)right- ModernB-Treevariants.SeveralworksreplaceB-Treewithre-
siblinglinksinleafnodesforrightwardsiblingsearches,(3)per-leaf designed mechanisms to address bottlenecks such as latch con-
sortedoffsetarraysforintra-leafmodeltrainingandprediction. tention[39],point-rangetradeoffs[76],andinsertionefficiency[60],
These properties are readily available in mainstream databases, assurveyedin[22,23].MirrorBtrinsteadadoptsanaugmentation
suchasPostgreSQL[25],MariaDB[47],andSQLServer[31]. strategythatpreservestheexistingB-Treeandlayerslearnedmod-
elsasauxiliarystructures.SinceMirrorBtracceleratestraversalvia
Monetaryefficiency. MirrorBtrreducestheoverallmonetary
locatingtheleafnodedirectly,itappliestovariantsthatkeepa
cost.Withamemoryfootprintofonly0.51%oftheB-Treeindex
standardroot-to-leafB-Treetraversal.Forexample,BP-Tree[76]
size,MirrorBtrachieveshigherthroughputwithfewerthreadsthan
andQuIT[60]retainstandardtraversalinreads,makingaugmen-
theB-Tree.Giventhat1vCPUcoreis8×moreexpensivethan1GB
tationwithMirrorBtrfeasible.Incontrast,Bw-Tree[39]introduces
memoryinpublicclouds[45],thisCPUefficiencyleadstoanet
latch-freetraversalthatMirrorBtrdoesnotguarantee,makingit
reductionintotalcostofownership.
unsuitableforaugmentationwithMirrorBtr.
Lightweightconstruction. Asanin-memoryauxiliarystructure,
Databasecracking.Databasecracking[29]sharesanon-intrusive
MirrorBtrisreconstructedduringdatabaseinitialization.However,
augmentationphilosophywithMirrorBtr.However,databasecrack-
theoverheadisreducedbytwokeystrategies:(1)Scanningfewer
ing follows a query-driven update scheme, whereas MirrorBtr
nodes.Thelearnedindexisconstructedbyscanningthelowest-
adoptsawrite-drivenone.Fordatabasecracking,eachquerytrig-
levelinnernodes,whicharefewerthantheleafnodes.(2)Building
gersaphysicaldatareorganization.Incontrast,MirrorBtrisup-
intra-leafmodelsforcachednodes.Theintra-leafmodelsare
datedunderB-Treestructuralmodificationsorchangesontheleaf
builtlazilyfornodesinthebufferpool,bypassingcoldnodes.As
nodeoffsetarray.
showninSection5.5,MirrorBtrachievesstablethroughputafter
awarm-upperiodsimilartothebaselineB-Tree.Moreover,this
8 CONCLUSION
one-timecostisfurtheramortizedbytheentireinstancelifetime
(oftenmonthsinproduction),makingtheoverheadnegligible. WeproposeMirrorBtr,aframeworkthatspeedsupB-Treetraversal
withoutintrusiveintegration.Ituseslearnedmodelsforinnerand
Supportforvariable-lengthkeys.MirrorBtrcurrentlysupports
leafnodestosavespaceandsimplifysynchronization.Aselection
fixed-lengthkeys.Tohandlevariable-lengthstringkeys,learned
pipelinehelpschoosethemostsuitablelearnedindex;ALEX+is
indexesforstrings[69,78]canbeincorporatedthroughtheunified
used for InnoDB integration. Experiments show that MirrorBtr
interfaceofMirrorBtr.Fortheselectionpipeline,existinghardness
improvestraversalperformancewithlowoverhead.
metricsfailtocapturethehighlyskewedprefixcommonlyfoundin
strings[78].Instead,theGroupPartialKeyLength(GPKL)metric
ACKNOWLEDGMENTS
andthecorrespondingsynthesizercanbeadopted[78].Intra-leaf
modelsaretrainedonpoorman’snormalizedkeys[24,54]:extract ThisworkwassupportedinpartbytheNationalKeyR&DProgram
8bytesafterthenode’scommonprefixasanunsignedinteger. ofChinaunderGrantNo.2023YFB4502400,inpartbytheFunda-
mentalandInterdisciplinaryDisciplinesBreakthroughPlanofthe
MinistryofEducationofChinaunderGrantNo.JYB2025XDXM901,
7 RELATEDWORK
inpartbytheNationalNaturalScienceFoundationofChinaunder
Learnedindexdeployment:KVstoresvs.relationaldatabases. GrantNo.62272223,U22A2031,U24B20153,62402212,inpartbythe
Recentworks[2,9,28,43,68,70]andabenchmark[41]uselearned NewGenerationInformationTechnologyInnovationProject2023
indexesaslightweighthelpersinLSM-basedkey-valuestoressuch (2023IT196),inpartbytheFundamentalResearchFundsforthe
asRocksDBorLevelDB.However,augmentingB-Trees,theprimary CentralUniversitiesunderGrantNo.2024300349and2025300309,
indexinrelationalOLTPdatabases,isharderbecausetheyrequire in part by the Natural Science Foundation for Young Scientists
carefulupdatehandling,whileimmutableSSTablesareidealfor ofJiangsuProvinceunderGrantNo.BK20241245,inpartbythe
learning[9].Inaddition,theeffectivenessofthelearnedindexin “111 Center” (No. B26023), in part by the Collaborative Innova-
relationaldatabasesremainsuncertain.MirrorBtrfillsthisgapby tionCenterofNovelSoftwareTechnologyandIndustrialization,
exploringanon-intrusivemethodthatlayerslearnedindexeson NanjingUniversity,inpartbySingaporeMOEAcRFTier-2Grant
existingB-Treesinrelationaldatabases. (MOE-T2EP20224-0005),inpartbyAlibabaGroupthroughtheAl-
IntegratingAI4DBtechniquesinrelationaldatabases.AI4DB ibabaResearchInternProgram.WealsothankZheyuMiao,Yuming
techniqueshaveshownpromiseinautonomousdatabaseoptimiza- Yang,andMingweiXufromAlibabaGroupforthevaluablehelp
tion[6,19,50,77].Yetitspracticalimpacthingesonsystem-level throughouttheproject.
12
REFERENCES
FrameworkbasedonProbabilityModels. Proc.ACMManag.Data1,4(2023),
[1] SepidehAbedini,ShubhankarMohapatra,DBEmerson,MasoumehShafieinejad, 258:1–258:25. https://doi.org/10.1145/3626752
JesseCCresswell,andXiHe.2025.MaskSQL:SafeguardingPrivacyforLLM- [19] VictorGiannakourisandImmanuelTrummer.2025.𝜆-Tune:HarnessingLarge
BasedText-to-SQLviaAbstraction.InNeurIPS2025WorkshoponRegulatable LanguageModelsforAutomatedDatabaseSystemTuning.Proc.ACMManag.
ML. Data3,1(2025),2:1–2:26. https://doi.org/10.1145/3709652
[2] HussamAbu-Libdeh,DenizAltinbüken,AlexBeutel,EdH.Chi,LyricDoshi, [20] Google.2025. CloudSQLPricing. RetrievedAugust22,2026fromhttps:
TimKraska,XiaozhouLi,AndyLy,andChristopherOlston.2020. Learned //cloud.google.com/sql/pricing
IndexesforaGoogle-scaleDisk-basedDatabase.CoRRabs/2012.12501(2020). [21] GoetzGraefe.2010.ASurveyofB-treeLockingTechniques.ACMTrans.Database
arXiv:2012.12501 https://arxiv.org/abs/2012.12501 Syst.35,3(2010),16:1–16:26. https://doi.org/10.1145/1806907.1806908
[3] AdnanAlhomssi,MichaelHaubenschild,andViktorLeis.2023.TheEvolutionof [22] GoetzGraefe.2011.ModernB-TreeTechniques.Found.TrendsDatabases3,4
LeanStore.InDatenbanksystemefürBusiness,TechnologieundWeb(BTW2023),20. (2011),203–402. https://doi.org/10.1561/1900000028
FachtagungdesGI-Fachbereichs„DatenbankenundInformationssysteme"(DBIS), [23] GoetzGraefe.2024.MoreModernB-TreeTechniques.Found.TrendsDatabases
06.-10,März2023,Dresden,Germany,Proceedings(LNI),BirgittaKönig-Ries, 13,3(2024),169–249. https://doi.org/10.1561/1900000070
StefanieScherzinger,WolfgangLehner,andGottfriedVossen(Eds.),Vol.P-331. [24] GoetzGraefeandPer-ÅkeLarson.2001. B-TreeIndexesandCPUCaches.In
GesellschaftfürInformatike.V.,259–281. https://doi.org/10.18420/BTW2023-13 Proceedingsofthe17thInternationalConferenceonDataEngineering,April2-6,
[4] AdnanAlhomssiandViktorLeis.2023.ScalableandRobustSnapshotIsolationfor 2001,Heidelberg,Germany,DimitriosGeorgakopoulosandAlexanderBuchmann
High-PerformanceStorageEngines.Proc.VLDBEndow.16,6(2023),1426–1438. (Eds.).IEEEComputerSociety,349–358. https://doi.org/10.1109/ICDE.2001.
https://doi.org/10.14778/3583140.3583157 914847
[5] AWS.2025.AmazonAuroraInstanceTypes. RetrievedAugust22,2026from [25] ThePostgreSQLGlobalDevelopmentGroup.2025.PostgreSQL:Documentation:
https://aws.amazon.com/rds/aurora/instance-types/ 17.64.1B-TreeIndexes. RetrievedAugust22,2026fromhttps://www.postgresql.
[6] MatteoBrucato,TariqueSiddiqui,WentaoWu,VivekR.Narasayya,andSurajit org/docs/17/btree.html
Chaudhuri.2024.Wred:WorkloadReductionforScalableIndexTuning.Proc. [26] JonahH.Harris.2021. Re:ML-basedindexing("TheCaseforLearnedIndex
ACMManag.Data2,1(2024),50:1–50:26. https://doi.org/10.1145/3639305 Structures,apaperfromGoogle")-Mailinglistpgsql-hackers. Retrieved
[7] HokeunCha,XiangpengHao,TianzhengWang,HuanchenZhang,AdityaAkella, August22,2026fromhttps://postgrespro.com/list/id/CAH2-Wzkwopr028p+3d=
andXiangyaoYu.2023.Blink-hash:AnAdaptiveHybridIndexforIn-Memory kNjd6hoA3V+Zy6hbou-LcHaV8FymH9Q@mail.gmail.com
Time-SeriesDatabases. Proc.VLDBEndow.16,6(2023),1235–1248. https: [27] MichaelHaubenschild,CaetanoSauer,ThomasNeumann,andViktorLeis.2020.
//doi.org/10.14778/3583140.3583143 RethinkingLogging,Checkpoints,andRecoveryforHigh-PerformanceStorage
[8] JeremyCole.2013.B+TreeIndexStructuresinInnoDB. RetrievedAugust22, Engines.InProceedingsofthe2020InternationalConferenceonManagementof
2026fromhttps://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/ Data,SIGMODConference2020,onlineconference[Portland,OR,USA],June14-19,
[9] YifanDai,YienXu,AishwaryaGanesan,RamnatthanAlagappan,BrianKroth, 2020,DavidMaier,RachelPottinger,AnHaiDoan,Wang-ChiewTan,Abdussalam
AndreaC.Arpaci-Dusseau,andRemziH.Arpaci-Dusseau.2020.FromWiscKey Alawini,andHungQ.Ngo(Eds.).ACM,877–892.https://doi.org/10.1145/3318464.
toBourbon:ALearnedIndexforLog-StructuredMergeTrees.In14thUSENIX 3389716
SymposiumonOperatingSystemsDesignandImplementation,OSDI2020,Virtual [28] AlirezaHeidari,AmirhosseinAhmadi,andWeiZhang.2025.DobLIX:ADual-
Event,November4-6,2020.USENIXAssociation,155–171. https://www.usenix. ObjectiveLearnedIndexforLog-StructuredMergeTrees.Proc.VLDBEndow.18,
org/conference/osdi20/presentation/dai 11(2025),3965–3978. https://www.vldb.org/pvldb/vol18/p3965-heidari.pdf
[10] JialinDing,MattAbrams,SanghitaBandyopadhyay,LucianoDiPalma,Yanzhu [29] StratosIdreos,MartinL.Kersten,andStefanManegold.2007.DatabaseCracking.
Ji,DavidePagano,GopalPaliwal,PanosParchas,PascalPfeil,OrestisPolychro- InThirdBiennialConferenceonInnovativeDataSystemsResearch,CIDR2007,
niou,GauravSaxena,AamerShah,AminaVoloder,SherryXiao,DavisZhang, Asilomar,CA,USA,January7-10,2007,OnlineProceedings.www.cidrdb.org,
andTimKraska.2024.AutomatedMultidimensionalDataLayoutsinAmazon 68–78. http://cidrdb.org/cidr2007/papers/cidr07p07.pdf
Redshift.InCompanionofthe2024InternationalConferenceonManagement [30] AlexeyKopytov.2004.Sysbench:ASystemPerformanceBenchmark. Retrieved
ofData,SIGMOD/PODS2024,Santiago,Chile,June9-15,2024,PabloBarceló, August22,2026fromhttps://github.com/akopytov/sysbench
NayatSánchez-Pi,AlexandraMeliou,andS.Sudarshan(Eds.).ACM,55–67. [31] DmitriKorotkevitch.2016.ProSQLServerInternals.Apress.
https://doi.org/10.1145/3626246.3653379 [32] TimKraska,AlexBeutel,EdH.Chi,JeffreyDean,andNeoklisPolyzotis.2018.
[11] JialinDing,UmarFarooqMinhas,JiaYu,ChiWang,JaeyoungDo,YinanLi, TheCaseforLearnedIndexStructures.InProceedingsofthe2018International
HantianZhang,BadrishChandramouli,JohannesGehrke,DonaldKossmann, ConferenceonManagementofData,SIGMODConference2018,Houston,TX,USA,
DavidB.Lomet,andTimKraska.2020.ALEX:AnUpdatableAdaptiveLearned June10-15,2018,GautamDas,ChristopherM.Jermaine,andPhilipA.Bernstein
Index.InProceedingsofthe2020InternationalConferenceonManagementof (Eds.).ACM,489–504. https://doi.org/10.1145/3183713.3196909
Data,SIGMODConference2020,onlineconference[Portland,OR,USA],June14-19, [33] HaiLan,ZhifengBao,J.ShaneCulpepper,andRenataBorovica-Gajic.2023.
2020,DavidMaier,RachelPottinger,AnHaiDoan,Wang-ChiewTan,Abdussalam UpdatableLearnedIndexesMeetDisk-ResidentDBMS-FromEvaluationsto
Alawini,andHungQ.Ngo(Eds.).ACM,969–984.https://doi.org/10.1145/3318464. DesignChoices. Proc.ACMManag.Data1,2(2023),139:1–139:22. https:
3389711 //doi.org/10.1145/3589284
[12] GaryEvansandNischayKothari.2025.ExploringlearnedindexesinPostgreSQL: [34] HaiLan,ZhifengBao,J.ShaneCulpepper,RenataBorovica-Gajic,andYuDong.
TheoryandImplementation. RetrievedAugust22,2026fromhttps://www. 2024. AFullyOn-DiskUpdatableLearnedIndex.In40thIEEEInternational
postgresql.fastware.com/blog/exploring-learned-indexes-in-postgresql ConferenceonDataEngineering,ICDE2024,Utrecht,TheNetherlands,May13-16,
[13] PaoloFerraginaandGiorgioVinciguerra.2020.ThePGM-index:afully-dynamic 2024.IEEE,4856–4869. https://doi.org/10.1109/ICDE60146.2024.00369
compressedlearnedindexwithprovableworst-casebounds.Proc.VLDBEndow. [35] PhilipL.LehmanandS.BingYao.1981.EfficientLockingforConcurrentOp-
13,8(2020),1162–1175. https://doi.org/10.14778/3389133.3389135 erationsonB-Trees. ACMTrans.DatabaseSyst.6,4(1981),650–670. https:
[14] MichaelJ.Freitag,AlfonsKemper,andThomasNeumann.2022. Memory- //doi.org/10.1145/319628.319663
OptimizedMulti-VersionConcurrencyControlforDisk-BasedDatabaseSystems. [36] ViktorLeis.2024.LeanStore:AHigh-PerformanceStorageEngineforNVMe
Proc.VLDBEndow.15,11(2022),2797–2810. https://doi.org/10.14778/3551793. SSDs. Proc.VLDBEndow.17,12(2024),4536–4545. https://doi.org/10.14778/
3551832 3685800.3685915
[15] AlexGalakatos,MichaelMarkovitch,CarstenBinnig,RodrigoFonseca,andTim [37] ViktorLeis,MichaelHaubenschild,andThomasNeumann.2019.OptimisticLock
Kraska.2019. FITing-Tree:AData-awareIndexStructure.InProceedingsof Coupling:AScalableandEfficientGeneral-PurposeSynchronizationMethod.
the2019InternationalConferenceonManagementofData,SIGMODConference IEEEDataEng.Bull.42(2019),73–84. https://api.semanticscholar.org/CorpusID:
2019,Amsterdam,TheNetherlands,June30-July5,2019,PeterA.Boncz,Stefan 83459602
Manegold,AnastasiaAilamaki,AmolDeshpande,andTimKraska(Eds.).ACM, [38] ViktorLeis,FlorianScheibner,AlfonsKemper,andThomasNeumann.2016.
1189–1206. https://doi.org/10.1145/3299869.3319860 TheARTofpracticalsynchronization.InProceedingsofthe12thInternational
[16] ChuqingGao,ShreyaBallijepalli,andJianguoWang.2024. RevisitingB-tree WorkshoponDataManagementonNewHardware,DaMoN2016,SanFrancisco,
Compression:AnExperimentalStudy.Proc.ACMManag.Data2,3(2024),169. CA,USA,June27,2016.ACM,3:1–3:8. https://doi.org/10.1145/2933349.2933352
https://doi.org/10.1145/3654972 [39] JustinJ.Levandoski,DavidB.Lomet,andSudiptaSengupta.2013.TheBw-Tree:
[17] JiakeGe,BoyuShi,YanfengChai,YuanhuiLuo,YundaGuo,YinxuanHe,and AB-treeforNewHardwarePlatforms.In29thIEEEInternationalConferenceon
YunpengChai.2023.CuttingLearnedIndexintoPieces:AnIn-depthInquiry DataEngineering,ICDE2013,Brisbane,Australia,April8-12,2013,ChristianS.
intoUpdatableLearnedIndexes.In39thIEEEInternationalConferenceonData Jensen,ChristopherM.Jermaine,andXiaofangZhou(Eds.).IEEEComputer
Engineering,ICDE2023,Anaheim,CA,USA,April3-7,2023.IEEE,315–327. https: Society,USA,302–313. https://doi.org/10.1109/ICDE.2013.6544834
//doi.org/10.1109/ICDE55515.2023.00031 [40] MengLi,HuayiChai,SiqiangLuo,HaipengDai,RongGu,JiaqiZheng,and
[18] JiakeGe,HuanchenZhang,BoyuShi,YuanhuiLuo,YundaGuo,YunpengChai, GuihaiChen.2025.VEGA:AnActive-tuningLearnedIndexwithGroup-Wise
YuxingChen,andAnqunPan.2023.SALI:AScalableAdaptiveLearnedIndex LearningGranularity. Proc.ACMManag.Data3,1(2025),86:1–86:26. https:
13
//doi.org/10.1145/3709736 DatabaseTechnology,EDBT2025,Barcelona,Spain,March25-28,2025,AlkisSim-
[41] JunfengLiu,JiaruiYe,MengshiChen,MengLi,andSiqiangLuo.2026.Evaluating itsis,BettinaKemme,AnnaQueralt,OscarRomero,andPetarJovanovic(Eds.).
LearnedIndexesinLSM-treeSystems:Benchmarks,InsightsandDesignChoices. OpenProceedings.org,451–463. https://doi.org/10.48786/EDBT.2025.36
InProceedings29thInternationalConferenceonExtendingDatabaseTechnology, [61] JiachenShi,JingyiYang,GaoCong,andXiaoliLi.2025.NEXT:ANewSecondary
EDBT2026,Tampere,Finland,March24-27,2026,WolfgangLehner,Vanessa IndexFrameworkforLSM-basedDataStorage. Proc.ACMManag.Data3,3
Braganholo,KostasStefanidis,ZheyingZhang,AlexanderKrause,andJoão (2025),193:1–193:25. https://doi.org/10.1145/3725330
FelipeNicolaciPimentel(Eds.).OpenProceedings.org,183–195. https://doi.org/ [62] ZhaoyanSun,XuanheZhou,andGuoliangLi.2023.LearnedIndex:ACompre-
10.48786/EDBT.2026.16 hensiveExperimentalEvaluation. Proc.VLDBEndow.16,8(2023),1992–2004.
[42] MingyuLiu,JunbinKang,KaiWang,LuZhang,HaiboChen,XiuchangLi,and https://doi.org/10.14778/3594512.3594528
TianhongDing.2025.ScaleCache:ScalableandProduction-gradeBufferMan- [63] MySQLTeam.2025. AdaptiveHashIndex. RetrievedAugust22,2026from
agementforDisk-basedDatabaseSystems. Proc.VLDBEndow.18,12(2025), https://dev.mysql.com/doc/refman/8.0/en/innodb-adaptive-hash.html
5073–5085. https://doi.org/10.14778/3750601.3750628 [64] MySQLTeam.2025.IntroductiontoInnoDB. RetrievedAugust22,2026from
[43] KaiLu,NannanZhao,JiguangWan,ChanghongFei,WeiZhao,andTongliang https://dev.mysql.com/doc/refman/8.0/en/innodb-introduction.html
Deng.2022.TridentKV:ARead-OptimizedLSM-TreeBasedKVStoreviaAdap- [65] MySQL Team. 2025. page0types.h File Reference. Retrieved
tiveIndexingandSpace-EfficientPartitioning.IEEETrans.ParallelDistributed August 22, 2026 from https://github.com/mysql/mysql-server/blob/
Syst.33,8(2022),1953–1966. https://doi.org/10.1109/TPDS.2021.3118599 9fc8d60003b4eee32767c1e30942f222c3508c31/storage/innobase/include/
[44] ChaohongMa,XiaohuiYu,YifanLi,XiaofengMeng,andAishanMaoliniyazi. page0types.h
2022. FILM:aFullyLearnedIndexforLarger-than-MemoryDatabases. Proc. [66] MySQLTeam.2025.UsingAUTO_INCREMENT. RetrievedAugust22,2026
VLDBEndow.16,3(2022),561–573. https://doi.org/10.14778/3570690.3570704 fromhttps://dev.mysql.com/doc/refman/8.0/en/example-auto-increment.html
[45] ZimingMao,JonathanD.Ellithorpe,AtulAdya,RishabhIyer,MateiZaharia, [67] KefeiWangandFengChen.2023.Catalyst:OptimizingCacheManagementfor
ScottShenker,andIonStoica.2025.RethinkingtheCostofDistributedCaches LargeIn-memoryKey-valueSystems.Proc.VLDBEndow.16,13(2023),4339–4352.
forDatacenterServices.InProceedingsofthe24thACMWorkshoponHotTopics https://doi.org/10.14778/3625054.3625068
inNetworks,HotNets2025,UMDCampus,CollegePark,MD,USA,November17-18, [68] WenlongWangandDavidHung-ChangDu.2024.LearnedKV:IntegratingLSM
2025,AlanZaoxingLiu,PhilipBrightenGodfrey,andBarathRaghavan(Eds.). andLearnedIndexforSuperiorPerformanceonSSD.CoRRabs/2406.18892(2024).
ACM,317–325. https://doi.org/10.1145/3772356.3772388 https://doi.org/10.48550/ARXIV.2406.18892arXiv:2406.18892
[46] RyanMarcus,AndreasKipf,AlexandervanRenen,MihailStoian,SanchitMisra, [69] YouyunWang,ChuzheTang,ZhaoguoWang,andHaiboChen.2020.SIndex:a
AlfonsKemper,ThomasNeumann,andTimKraska.2020.BenchmarkingLearned scalablelearnedindexforstringkeys.InAPSys’20:11thACMSIGOPSAsia-Pacific
Indexes.Proc.VLDBEndow.14,1(2020),1–13. https://doi.org/10.14778/3421424. WorkshoponSystems,Tsukuba,Japan,August24-25,2020,TaesooKimandPatrick
3421425 P.C.Lee(Eds.).ACM,17–24. https://doi.org/10.1145/3409963.3410496
[47] MariaDB.2025.MariaDBEnterpriseOpenSourceDatabase. RetrievedAugust [70] YiWang,JiananYuan,ShangyuWu,HuanLiu,JiaxianChen,ChenlinMa,and
22,2026fromhttps://mariadb.com/ JianbinQin.2024. LeaderKV:ImprovingReadPerformanceofKVStoresvia
[48] JohnC.McCallum.2024. MemoryPrices1957-2024. RetrievedAugust LearnedIndexandDecoupledKVTable.In40thIEEEInternationalConference
22,2026fromhttps://web.archive.org/web/20250423035422/https://jcmit.net/ onDataEngineering,ICDE2024,Utrecht,TheNetherlands,May13-16,2024.IEEE,
memoryprice.htm 29–41. https://doi.org/10.1109/ICDE60146.2024.00010
[49] Microsoft.2025. OverviewofAzureSQLManagedInstanceResourceLimits. [71] ChaichonWongkham,BaotongLu,ChrisLiu,ZhicongZhong,EricLo,and
RetrievedAugust22,2026fromhttps://learn.microsoft.com/en-us/azure/azure- TianzhengWang.2022. AreUpdatableLearnedIndexesReady? Proc.VLDB
sql/managed-instance/resource-limits/ Endow.15,11(2022),3004–3017.
[50] YuxuanMoandYuHua.2025. LOFT:ALock-freeandAdaptiveLearned [72] JiachengWu,YongZhang,ShiminChen,YuChen,JinWang,andChunxiaoXing.
IndexwithHighScalabilityforDynamicWorkloads.InProceedingsofthe 2021.UpdatableLearnedIndexwithPrecisePositions.Proc.VLDBEndow.14,8
Twentieth European Conference on Computer Systems, EuroSys 2025, Rotter- (2021),1276–1288. https://doi.org/10.14778/3457390.3457393
dam,TheNetherlands,30March2025-3April2025.ACM,475–491. https: [73] ShangyuWu,YufeiCui,JinghuanYu,XuanSun,Tei-WeiKuo,andChunJason
//doi.org/10.1145/3689031.3717458 Xue.2022.NFL:RobustLearnedIndexviaDistributionTransformation.Proc.
[51] C.Mohan.1999.RepeatingHistoryBeyondARIES.InVLDB’99,Proceedingsof VLDBEndow.15,10(2022),2188–2200. https://doi.org/10.14778/3547305.3547322
25thInternationalConferenceonVeryLargeDataBases,September7-10,1999, [74] YingjunWu,JoyArulraj,JiexiLin,RanXian,andAndrewPavlo.2017. An
Edinburgh,Scotland,UK,MalcolmP.Atkinson,MariaE.Orlowska,PatrickVal- EmpiricalEvaluationofIn-MemoryMulti-VersionConcurrencyControl.Proc.
duriez,StanleyB.Zdonik,andMichaelL.Brodie(Eds.).MorganKaufmann,1–17. VLDBEndow.10,7(2017),781–792. https://doi.org/10.14778/3067421.3067427
http://www.vldb.org/conf/1999/P1.pdf [75] QingXie,ChaoyiPang,XiaofangZhou,XiangliangZhang,andKeDeng.2014.
[52] C.Mohan,DonHaderle,BruceG.Lindsay,HamidPirahesh,andPeterM.Schwarz. Maximumerror-boundedPiecewiseLinearRepresentationforonlinestream
1992. ARIES:ATransactionRecoveryMethodSupportingFine-Granularity approximation.VLDBJ.23,6(2014),915–937. https://doi.org/10.1007/S00778-
LockingandPartialRollbacksUsingWrite-AheadLogging.ACMTrans.Database 014-0355-0
Syst.17,1(1992),94–162. https://doi.org/10.1145/128765.128770 [76] HelenXu,AmandaLi,BrianWheatman,ManojMarneni,andPrashantPandey.
[53] MongoDB.2025.WiredTigerStorageEngine. RetrievedAugust22,2026from 2023.BP-tree:OvercomingthePoint-RangeOperationTradeoffforIn-Memory
https://www.mongodb.com/docs/manual/core/wiredtiger/ B-trees.Proc.VLDBEndow.16,11(2023),2976–2989. https://doi.org/10.14778/
[54] MarcusMüller,LawrenceBenson,andViktorLeis.2025. B-TreesAreBack: 3611479.3611502
EngineeringFastandPageableNodeLayouts.Proc.ACMManag.Data3,1(2025), [77] XianghongXu,TieyingZhang,XiaoHe,HaoyangLi,RongKang,ShuaiWang,
14:1–14:26. https://doi.org/10.1145/3709664 LinhuiXu,ZhiminLiang,ShangyuLuo,LeiZhang,andJianjunChen.2025.
[55] ThomasNeumann.2017. TheCaseforB-TreeIndexStructures. Retrieved AdaNDV:AdaptiveNumberofDistinctValueEstimationviaLearningtoSelect
August22,2026fromhttps://databasearchitects.blogspot.com/2017/12/the-case- andFuseEstimators. CoRRabs/2502.16190(2025). https://doi.org/10.48550/
for-b-tree-index-structures.html ARXIV.2502.16190arXiv:2502.16190
[56] BengChinOoi,ShaofengCai,GangChen,YanyanShen,Kian-LeeTan,Yuncheng [78] YifanYangandShiminChen.2024. LITS:AnOptimizedLearnedIndexfor
Wu,XiaokuiXiao,NailiXing,CongYue,LingzeZeng,MeihuiZhang,andZhan- Strings.Proc.VLDBEndow.17,11(2024),3415–3427. https://doi.org/10.14778/
haoZhao.2024.NeurDB:anAI-poweredautonomousdatasystem.Sci.China 3681954.3682010
Inf.Sci.67,10(2024). https://doi.org/10.1007/S11432-024-4125-9 [79] HuanchenZhang,DavidG.Andersen,AndrewPavlo,MichaelKaminsky,Lin
[57] Oracle.2025. IndexesandIndex-OrganizedTables. RetrievedAugust22, Ma,andRuiShen.2016. ReducingtheStorageOverheadofMain-Memory
2026fromhttps://docs.oracle.com/en/database/oracle/oracle-database/23/cncpt/ OLTPDatabaseswithHybridIndexes.InProceedingsofthe2016International
indexes-and-index-organized-tables.html ConferenceonManagementofData,SIGMODConference2016,SanFrancisco,CA,
[58] Shujian Qian and Ashvin Goel. 2024. Massively Parallel Multi-Versioned USA,June26-July01,2016,FatmaÖzcan,GeorgiaKoutrika,andSamMadden
TransactionProcessing.In18thUSENIXSymposiumonOperatingSystemsDe- (Eds.).ACM,1567–1581. https://doi.org/10.1145/2882903.2915222
signandImplementation,OSDI2024,SantaClara,CA,USA,July10-12,2024, [80] JiaoyiZhangandYihanGao.2022.CARMI:ACache-AwareLearnedIndexwitha
AdaGavrilovskaandDouglasB.Terry(Eds.).USENIXAssociation,765–781. Cost-basedConstructionAlgorithm.Proc.VLDBEndow.15,11(2022),2679–2691.
https://www.usenix.org/conference/osdi24/presentation/qian https://doi.org/10.14778/3551793.3551823
[59] AneeshRaman,AndyHuynh,JinqiLu,andManosAthanassoulis.2024.Bench- [81] JiaoyiZhang,KaiSu,andHuanchenZhang.2024.MakingIn-MemoryLearned
markingLearnedandLSMIndexesforDataSortedness.InProceedingsofthe IndexesEfficientonDisk. Proc.ACMManag.Data2,3(2024),151. https:
TenthInternationalWorkshoponTestingDatabaseSystems,DBTest2024,Santiago, //doi.org/10.1145/3654954
Chile,9June2024.ACM,16–22. https://doi.org/10.1145/3662165.3662764 [82] RuiZhangandShenghuiZhao.2025.SafeSQL-LLM:ASyntheticDataApproach
[60] AneeshRaman,KonstantinosKaratsenidis,ShaolinXie,MatthaiosOlma,Sub- toPrivacy-PreservingText-to-SQL.In31thIEEEInternationalConferenceon
hadeepSarkar,andManosAthanassoulis.2025. QuITyourB+-treeforthe ParallelandDistributedSystems,ICPADS2025,Hefei,China,December14-18,2025.
QuickInsertionTree.InProceedings28thInternationalConferenceonExtending IEEE,1–8. https://doi.org/10.1109/ICPADS67057.2025.11323205
14
[83] ShunkangZhang,JiQi,XinYao,andAndréBrinkmann.2024.Hyper:AHigh- [85] BolongZheng,YongyongGao,JingyiWan,LingsenYan,LongHu,BoLiu,Yunjun
PerformanceandMemory-EfficientLearnedIndexviaHybridConstruction.Proc. Gao,XiaofangZhou,andChristianS.Jensen.2023. DecLog:Decentralized
ACMManag.Data2,3(2024),145. https://doi.org/10.1145/3654948 LogginginNon-VolatileMemoryforTimeSeriesDatabaseSystems.Proc.VLDB
[84] ZhanhaoZhao,ShaofengCai,HaotianGao,HexiangPan,SiqiXiang,Naili Endow.17,1(2023),1–14. https://doi.org/10.14778/3617838.3617839
Xing,GangChen,BengChinOoi,YanyanShen,YunchengWu,andMeihui [86] RongZhu,LiangguiWeng,WenqingWei,DiWu,JiazhenPeng,YifanWang,
Zhang.2025. NeurDB:OntheDesignandImplementationofanAI-powered BolinDing,DefuLian,BolongZheng,andJingrenZhou.2024. PilotScope:
AutonomousDatabase.In15thConferenceonInnovativeDataSystemsResearch, SteeringDatabaseswithMachineLearningDrivers. Proc.VLDBEndow.17,5
CIDR2025,Amsterdam,TheNetherlands,January19-22,2025.www.cidrdb.org. (2024),980–993. https://doi.org/10.14778/3641204.3641209
https://vldb.org/cidrdb/papers/2025/p29-zhao.pdf
15