A learned index is a regression line pretending to be a search tree
Sorted keys trace a CDF. Fit a model, plug in a key, get a position. Toggle an easy vs hard CDF and drag the query key.
Mock CDFs. One root model shown; real learned indexes stack many models per segment, which is why hard CDFs cost tree depth.
Lineage: from static RMI to SALI
Hover a node. Static RMI could not take inserts, so the field split into buffer-based and model-based camps.
Hover a node to see what it contributed.
Shift vs chain: what happens when the predicted slot is taken
Insert key 34 into a gapped node. Step through both designs, and watch what each one locks, moves, and updates.
Throughput vs threads
ALEX+ and LIPP+ stop scaling for different reasons. Toggle workload and series, then hover the chart.
Curve shapes are illustrative. The 2.04× SALI vs ALEX+ ratio at 64 threads (write-heavy) is the figure quoted in the episode.
Statistics contention: one cacheline, many writers
Fine-grained locks protect slots, not the shared counter that decides when to reorganize.
Hover a cell: core × time bucket, coherence-miss intensity.
Insert trigger: a weighted coin
Each node flips a Bernoulli coin biased by how much it has grown. Certain at ratio 1.
Mapping from growth to P_acc is schematic. The paper sets β = 2 as a rule of thumb.
Conflict signal: geometric
Inserts until the next collision is geometric, so one collision already estimates the rate.
Three ways a node evolves
Expand insert-hot nodes, flatten read-hot subtrees, compress cold ones.
Lock-free evolving: RCU swap + epoch reclamation
Readers never see a half-built node. Scrub time or press play.
2.04×avg insert throughput vs ALEX+, 64 threads
2.5–10×vs other learned indexes on OSM, GENOME
31–37%space cut by cold-node compression
+35%probability model vs sampling, 60 threads
Results explorer
Switch metric. Bar heights are relative and illustrative, anchored to the ratios above.
Evidence ledger: measured, asserted, or missing
Everything measured is on one base structure (LIPP). Hover a row.
Hover a row for the note.
Hand-picked constants
Each is labeled a rule of thumb. No sensitivity sweep across datasets or skew.
References
- SALI: A Scalable Adaptive Learned Index Framework based on Probability ModelsGe, Zhang, Shi, Luo, Guo, Chai, Chen, Pan · 2023 · arXiv 2308.15012
- The Case for Learned Index StructuresKraska, Beutel, Chi, Dean, Polyzotis · 2018
- ALEX: An Updatable Adaptive Learned IndexDing, Minhas, Yu, Wang, Do, Li, Zhang, Chandramouli, Gehrke, Kossmann, Lomet, Kraska · 2020
- Updatable Learned Index with Precise Positions (LIPP)Wu, Zhang, Chen, Wang, Chen, Xing · 2021
- XIndex: A Scalable Learned Index for Multicore Data StorageTang, Wang, Dong, Hu, Wang, Wang, Chen · 2020
- Are Updatable Learned Indexes Ready?Wongkham, Lu, Liu, Zhong, Lo, Wang · 2022
- Adaptive Hybrid IndexesAnneser, Kipf, Zhang, Neumann, Kemper · 2022
- DILI: A Distribution-Driven Learned IndexLi, Lu, Zhu, Ding, Yang, Pan · 2023
- Updatable Learned Indexes Meet Disk-Resident DBMSLan, Bao, Culpepper, Borovica-Gajic · 2023