1
00:00:01,000 --> 00:00:40,799
[Hal Turing] Alrighty! Thanks for tuning in! Hello AI world! I am your host, Hal Turing, and my co-host is Dr. Ada Shannon. Today we're digging into ALEX: An Updatable Adaptive Learned Index, by Jialin Ding et al. — that's twelve co-authors total — out of MIT, Microsoft Research, Arizona State, and Georgia Tech, posted to arXiv in May 2020. And Ada, here's the number that made me sit up: up to 4.1x the throughput of a B+Tree, with an index that's up to 2000 times smaller. Two thousand times. That's not a rounding error, that's a different universe of memory footprint.

2
00:00:40,799 --> 00:01:16,511
[Dr. Ada Shannon] Right, and what's fun is that number alone doesn't tell you why this paper matters — the real story is what it had to fix to even be allowed to make that claim. Because there was a very famous predecessor to this, Kraska et al.'s Learned Index from 2018, that got a ton of attention for basically the same pitch: replace a database index with machine learning models. And it had a fatal catch that a lot of people glossed over — it only worked if your data never changed. No inserts, no updates, no deletes. Which, if you think about it, describes almost no real database anyone actually runs.

3
00:01:16,511 --> 00:01:32,625
[Hal Turing] Okay, let's back up for listeners who aren't living and breathing database internals, because I want us to actually build this up properly. What even is a database index doing, mechanically? Walk me through a B+Tree like I'm someone who's only ever called .find() on a dictionary.

4
00:01:32,625 --> 00:02:25,195
[Dr. Ada Shannon] Sure. Picture a phone book, but instead of one flat alphabetical list, it's organized as a tree of decisions. You start at the root: is the name before or after 'M'? That sends you down a branch. Each internal node just narrows the range further — before 'F', after 'F' but before 'M', and so on — until you hit a leaf node that actually holds the record, or a pointer to it. That's a B+Tree: height-balanced, meaning every leaf is roughly the same distance from the root, so lookups are predictable, typically logarithmic in the number of keys. Leaf nodes also keep some free space at the end so a handful of new records can be inserted without immediately triggering a reorganization. It's been the default choice in databases since the 1970s because it's robust, well-understood, and has decent worst-case guarantees.

5
00:02:25,195 --> 00:02:30,397
[Hal Turing] So what's the catch? Why would anyone want to replace something that's been battle-tested for fifty years?

6
00:02:30,397 --> 00:03:29,515
[Dr. Ada Shannon] Because a B+Tree treats every key distribution identically. It doesn't care if your keys are timestamps that increase steadily, or sequential IDs, or completely random UUIDs — the tree shape and traversal logic are the same generic decision procedure regardless. And that's the insight Kraska, Beutel, Chi, Dean, and Polyzotis had at Google in 2018, in their paper 'The Case for Learned Index Structures.' Real-world keys are often smooth, learnable sequences — think of a CDF, a cumulative distribution function, mapping key value to rank. If you can learn that function with a small model, you can predict roughly where a key sits in a sorted array directly, skipping most of the tree traversal. They called it the Recursive Model Index, or RMI — a hierarchy of regression models, root model predicts which child model to use, and so on down to a model that predicts the position in a dense sorted array. They showed up to 3x faster lookups and an order of magnitude smaller footprint than a B+Tree.

7
00:03:29,515 --> 00:03:31,976
[Hal Turing] Okay, so that sounds great — where's the trap?

8
00:03:31,976 --> 00:04:01,744
[Dr. Ada Shannon] The trap is that array has to stay densely packed and sorted for the model's predictions to line up with actual positions. The instant you insert a new key in the middle, you'd have to shift everything after it, or the model's predictions go stale. So the Learned Index just... didn't support inserts. At all. If your data changed, you rebuilt the entire structure from scratch. That's fine for a read-only analytics snapshot. It's completely unusable for a live transactional system where rows are being written every millisecond.

9
00:04:01,744 --> 00:04:11,636
[Hal Turing] Oh wait wait wait — so this is literally why ALEX exists. The 'A' isn't just a name, it's 'Adaptive' specifically because the original thing was frozen solid.

10
00:04:11,636 --> 00:04:47,580
[Dr. Ada Shannon] Exactly, and that's the whole research question this paper poses directly in the introduction: can you design an in-memory index that keeps the core insight — models predicting position — but marries it to proven storage techniques so it survives point lookups, range scans, inserts, updates, and deletes simultaneously? That mix is what OLTP workloads look like — online transaction processing, think bank ledgers, order systems, anything with constant reads and writes happening together, as opposed to OLAP, big batch analytical scans over data that doesn't move.

11
00:04:47,580 --> 00:04:54,825
[Hal Turing] So how does ALEX actually solve the 'my sorted array can't move' problem? Because that seems like the crux of it.

12
00:04:54,825 --> 00:05:45,259
[Dr. Ada Shannon] Two big ideas, and we'll go deeper on the mechanics next, but here's the shape of it. First: the Gapped Array. Instead of packing the array with zero slack, ALEX deliberately leaves empty gaps scattered through it — like a binder with blank pages between chapters so you can pencil in new content without recopying the whole book. The model predicts roughly where a key belongs, and if there's a nearby gap, the insert lands there almost for free, no mass shifting required. Second: the tree itself isn't fixed. Where the original RMI had one static depth chosen at training time, ALEX's internal nodes and data nodes can independently grow, shrink, split, or retrain their local linear model as the workload evolves. It's an adaptive RMI — the structure reshapes itself instead of freezing on day one.

13
00:05:45,259 --> 00:05:56,590
[Hal Turing] And I have to ask, because I know some listeners are already there mentally — when you say 'model' here, are we talking neural networks? Is there a tiny transformer living inside my database index?

14
00:05:56,590 --> 00:06:45,445
[Dr. Ada Shannon] No, and that's actually the elegant part. These are dead-simple linear models — y equals a times x plus b, mapping a key straight to a predicted array position, fit with closed-form least squares, no gradient descent, no backprop. That's deliberate: a node's model might get retrained thousands of times a second, and it has to evaluate in nanoseconds during a lookup on the hot path. A transformer or even a small MLP would be laughably too slow for this job. The 'learning' here is classical statistics, and the 'adaptivity' is an algorithmic policy — explicit cost models triggering grow, shrink, split, or retrain — not anything like online weight updates. It's a much closer cousin to how an LSM-tree's compaction policy reshapes itself than to anything in deep learning.

15
00:06:45,445 --> 00:07:01,141
[Hal Turing] That's a good gut-check for anyone assuming 'learned' automatically means 'deep learning.' So given that background, Ada, what's your honest first take on where this sits — is this the moment learned indexes became practical, or is it still a research curiosity?

16
00:07:01,141 --> 00:07:32,303
[Dr. Ada Shannon] My honest take, before we get into the mechanics of the Gapped Array and the actual benchmark numbers, is that this paper earns its headline claims on paper — 4.1x over B+Tree, 2.2x over the original Learned Index with 15x smaller footprint on read-only — but 'earns it on paper' and 'is production-ready' are two very different bars. We'll get into exactly how the gaps and splits work, and then later we need to talk about what a single-threaded benchmark on one CPU core actually tells you versus what a real multi-core OLTP system demands.

17
00:07:32,303 --> 00:08:16,374
[Dr. Ada Shannon] —ready are two very different claims, and that's exactly the distinction I want to hold onto as we open the hood. So let's actually look at how inserts get absorbed, because this is where the whole design either holds together or falls apart. Remember the dense array problem from before — ALEX's fix is the Gapped Array, and the trick is it doesn't just leave slack at the end like a B+Tree page does. It defines two density thresholds, a lower bound around 0.6 and an upper bound around 0.8. As long as the array's fill ratio sits inside that band, gaps are scattered throughout the array, not bunched at the tail, so an insert usually lands near its predicted position without shifting half the node.

18
00:08:16,374 --> 00:08:30,863
[Hal Turing] Okay, so the array is basically breathing, expanding and contracting between those two limits. But eventually you hit the ceiling. What actually happens the moment a node crosses that 0.8 density mark and there's nowhere left to put a gap?

19
00:08:30,863 --> 00:09:17,535
[Dr. Ada Shannon] That's where it gets genuinely clever. ALEX keeps running statistics per node — average search iterations, average shift distance — and compares the empirical cost against the cost it predicted when the node was created. If they're within 50% of each other, it just expands the node and rescales the existing model, cheap. If the empirical cost has drifted past that threshold, meaning the model's predictions have gotten stale, it picks between three options using a simple linear cost model: expand-and-retrain, split sideways the way a B+Tree splits, pushing a new pointer up to the parent, or split downward, which converts the data node itself into a fresh internal node with two children. Sideways preserves tree depth; downward adds a level only where the data actually needs finer resolution.

20
00:09:17,535 --> 00:09:33,511
[Hal Turing] Wait, wait, hold on, that's actually a bigger deal than it sounds. So the tree isn't uniformly deep the way a B+Tree is, some branches stay shallow because the data's easy to model, and other branches grow deeper only exactly where the distribution gets gnarly?

21
00:09:33,511 --> 00:10:06,762
[Dr. Ada Shannon] Exactly right, and that's the adaptive RMI paying off, depth follows the data, not a fixed schema. It carries through to bulk loading too. Instead of a human picking how many models per level, like you had to do with the original Learned Index, ALEX builds what they call a Fanout Tree. It greedily tries different fanouts at each node, scores them with that same cost model, merges regions that are cheap and splits regions that need more resolution, and settles on a structure automatically. No grid search, no hand-tuned parameter file per dataset.

22
00:10:06,762 --> 00:10:13,356
[Hal Turing] Alright, that's the mechanics. Now give me the scoreboard, what did all that actually buy them against the competition?

23
00:10:13,356 --> 00:10:59,007
[Dr. Ada Shannon] On read-only workloads, ALEX beats the original Learned Index by up to 2.2x on throughput while using 15x less space for the index itself. Against B+Tree it's up to 4.1x faster with an 800x smaller index. Flip to the read-write spectrum, where the Learned Index can't even compete because its insert cost is unusably high, and ALEX still beats B+Tree by 4.0 to 4.1x with up to 2000x smaller index size. They also throw in a Model B+Tree, same skeleton but with linear models and exponential search bolted onto each node, basically an ablation, and ALEX still wins there, plus it beats Adaptive Radix Tree from Leis, Kemper, and Neumann out of TUM, 2013, on every read-heavy workload.

24
00:10:59,007 --> 00:11:17,768
[Hal Turing] I'll push back on the '2000x smaller index' framing, though. That's index metadata, models and pointers, not the actual data storage, which dominates memory anyway. Trumpeting a 2000x number on the part that was never the bottleneck feels like it's doing more marketing work than engineering work.

25
00:11:17,768 --> 00:11:38,620
[Dr. Ada Shannon] I actually disagree with you there, Hal. It's not free-floating marketing, the paper says smaller index footprint means more indexes fit in the same memory budget, which matters enormously if you're running a multi-tenant OLTP system with hundreds of tables each needing their own index. It's a real constraint, just not the one that shows up in a single-index microbenchmark.

26
00:11:38,620 --> 00:11:49,812
[Hal Turing] Sure, in a multi-index deployment I'll grant that's real. I still think leading the abstract with the biggest multiplier rather than the throughput number is a framing choice designed to grab headlines.

27
00:11:49,812 --> 00:12:24,317
[Dr. Ada Shannon] We can agree to disagree on the marketing instinct, but the underlying number is legitimate. What actually explains the throughput gap is the exponential search result, Figure 16 in the paper. They benchmark exponential search against binary search and Kraska's biased quaternary search under synthetic prediction error. Exponential search's cost scales with the log of the error, so when ALEX's model-based inserts keep prediction error tiny, exponential search wins outright; binary search pays a constant cost no matter how good your guess was, because it always has to search the full error bound.

28
00:12:24,317 --> 00:12:46,561
[Hal Turing] So accuracy from model-based inserts is what unlocks the search speedup, it's not exponential search that's inherently better, it's that ALEX earns the conditions where exponential search dominates. Last thing before the sharper critique — how does this hold up outside the tidy 60-second benchmark window? Scaling, distribution shift, that kind of thing?

29
00:12:46,561 --> 00:13:28,636
[Dr. Ada Shannon] Robust, from what they show. Throughput degrades slowly as dataset size grows because the adaptive RMI keeps restructuring itself rather than sitting on a stale model. Under distribution shift, they initialize on the 50 million smallest keys, then insert a completely disjoint range, ALEX still holds up to 3.2x over B+Tree. And for the nasty case, pure ascending sequential inserts, append-only, worst case, ALEX detects that pattern by tracking how often inserts exceed the current max key, expands the root rightward without doing a full model-based reinsertion, and still comes out 3.6x ahead of B+Tree.

30
00:13:28,636 --> 00:14:10,943
[Hal Turing] Good place to land, and it sets up the harder question I want to put to this paper directly. Every single number we just cited — the 4.1x, the 2.2x, the 2000x — comes from single-threaded runs on one Intel i9-9900K core. OLTP, by definition, is a concurrent workload with dozens of threads hammering the same structure. The paper's own conclusion admits this, listing 'new concurrency control techniques tailored to the ALEX design' as future work. So does any of this survive contact with a real multi-core database engine, or are we looking at a single-core artifact wearing an OLTP costume?

31
00:14:10,943 --> 00:14:59,333
[Dr. Ada Shannon] It's a real gap, and it's structurally harder than it sounds. With a B+Tree, concurrent inserts are a solved problem — latch-coupling, optimistic locking, decades of engineering. But ALEX's whole advantage comes from mutating state that concurrency control usually treats as sacred: it retrains a linear model in place, it shifts the Gapped Array under an insert, it splits nodes and reassigns parent pointers dynamically. None of that is a simple 'lock the leaf' operation anymore, because the leaf's own predictive function is changing underneath you. Compare that to Masstree, from Mao, Kohler, and Morris out of MIT and Harvard, EuroSys 2012 — that's an actual concurrent, cache-conscious trie-B+Tree hybrid built from day one for multicore key-value storage. ALEX doesn't even attempt that problem here.

32
00:14:59,333 --> 00:15:30,680
[Hal Turing] And it's not just concurrency — there's zero discussion of durability anywhere in this paper. No write-ahead log, no crash recovery story. If the process dies, the entire index vanishes, models and all. That's fine for a research prototype, but an index that can't survive a crash isn't OLTP-usable as shipped. A real WAL forces extra writes on every mutation and can't just shift bytes around in place the way the Gapped Array assumes it can.

33
00:15:30,680 --> 00:16:02,166
[Dr. Ada Shannon] Oh, hold on — that actually connects to something worse buried in section 4.4. They explicitly say merging of underfull nodes after deletes is 'not implemented, for simplicity.' Their benchmark window is sixty seconds. Any production system running delete-heavy or high-churn workloads for days or weeks would watch data nodes drift toward the lower density limit and just sit there, fragmented, because there's no merge-back path. You'd need to periodically rebuild the whole index to reclaim that density. None of that shows up in a one-minute throughput chart.

34
00:16:02,166 --> 00:16:13,962
[Hal Turing] I want to push back a little there, Ada. They're upfront about it — it's in the paper, in plain language, flagged as future work. That's honest science, not a hidden flaw you had to go dig for.

35
00:16:13,962 --> 00:16:40,851
[Dr. Ada Shannon] I actually disagree with you there, Hal. Being upfront in section 8 doesn't erase what the abstract and introduction are selling — language like 'practical for a broader class of database workloads with dynamic updates.' That's positioning this as a general OLTP index. When three load-bearing requirements of real OLTP — concurrency, durability, larger-than-memory data — are all future work, the honest framing should be narrower than the marketing.

36
00:16:40,851 --> 00:16:55,108
[Hal Turing] Okay, that's fair — there's daylight between what's rigorously demonstrated and what the title implies, even if nobody's hiding anything. So where does that leave prior art? Because ALEX isn't the first attempt at an updatable learned index.

37
00:16:55,108 --> 00:17:55,155
[Dr. Ada Shannon] Not even close. FITing-Tree, from Galakatos, Markovitch, Binnig, Fonseca, and Kraska, SIGMOD 2019, already put linear models inside B+Tree leaves specifically to compress the index while keeping update support. ALEX's real contribution on top of that is the Gapped Array and the adaptive RMI. And on the storage side, they explicitly tested the Adaptive Packed-Memory Array from Bender and Hu, TODS 2007, in Appendix E, and rejected it — PMA rebalances toward uniform density with strong worst-case guarantees, but that spreads keys away from their model-predicted slot, which kills exponential search. ALEX trades PMA's worst-case safety for average-case speed. All of it still traces back to Kraska, Beutel, Chi, Dean, and Polyzotis, SIGMOD 2018 — ALEX is that paper's read-only limitation, finally addressed for writes.

38
00:17:55,155 --> 00:18:09,830
[Hal Turing] So practically, if I'm an engineer today, where does ALEX actually fit? Sounds like single-threaded, embedded, or analytical workloads where you control the process and durability is someone else's problem — not a drop-in B+Tree replacement in Postgres tomorrow.

39
00:18:09,830 --> 00:18:26,409
[Dr. Ada Shannon] Exactly right. Treat it as a proof of concept that updatable learned indexes are viable at all, which two years earlier wasn't obvious. Concurrency control and durable secondary storage are the two gates between this and production OLTP, and the authors name both themselves.

40
00:18:26,409 --> 00:18:53,576
[Hal Turing] So to wrap: ALEX takes Kraska's static, read-only learned index and makes it genuinely writable through the Gapped Array and an adaptive model tree, and it wins convincingly on the workloads it tests. Just don't confuse a great single-threaded, in-memory benchmark with a finished OLTP index — concurrency and durability are still wide open. Thanks for listening, everyone — we'll catch you next time.