1
00:00:01,000 --> 00:00:54,080
[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's paper is APEX: A High-Performance Learned Index on Persistent Memory. That's Baotong Lu et al., five authors total — Lu and Eric Lo out of The Chinese University of Hong Kong, Jialin Ding from MIT, Umar Farooq Minhas from Microsoft Research, and Tianzheng Wang from Simon Fraser University. It's headed to VLDB 2022; the extended version we're reading carries an arXiv date of December 6th, 2021. Ada, here's the number that grabbed me: up to fifteen times faster inserts than existing persistent-memory indexes, and full crash recovery in about forty-two milliseconds.

2
00:00:54,080 --> 00:01:16,650
[Dr. Ada Shannon] Those numbers deserve scrutiny later, and we'll give it. But the setup's interesting: persistent memory promised to blur RAM and disk, and separately, a different research thread was trying to replace tree-based indexes with machine learning models. Nobody had married the two before this — and it wasn't obvious a learned index's speed could survive contact with real, crash-prone hardware.

3
00:01:16,650 --> 00:01:36,108
[Hal Turing] So for anyone who hasn't thought about database internals since a systems class — why do we even need this? DRAM's the default, it's fast, everyone understands it. I didn't realize until reading this paper that indexes alone can eat over half a database server's memory. Is that really the pressure here?

4
00:01:36,108 --> 00:02:04,019
[Dr. Ada Shannon] That's exactly it — over fifty-five percent of total memory in some OLTP deployments, and DRAM's price and density can't keep pace. Persistent memory sits on the same DDR bus as DRAM at a fraction of the cost per gigabyte and survives a power cycle. Intel's Optane DCPMM was the first commercial version, shipping in DIMMs from 128 to 512 gigabytes — but it behaves differently enough that existing software can't just point at it.

5
00:02:04,019 --> 00:02:15,489
[Hal Turing] Wait, wait — hold on. When you say 'behaves differently,' do you mean it's actually addressed like RAM, with load and store instructions, not read and write calls like a disk?

6
00:02:15,489 --> 00:02:49,530
[Dr. Ada Shannon] Exactly, and that's the strange part. You touch it with ordinary loads and stores, not a block driver or a syscall. But writes still pass through the volatile CPU cache, which can reorder them, so software must explicitly flush a cache line — CLWB or CLFLUSH — then fence with SFENCE, forcing data into the ADR domain, a hardware buffer guaranteed to survive power loss before it's even on the media. One more wrinkle: Optane's internal access granularity is 256 bytes, an XPLine — ask for 64 and it still moves the full 256.

7
00:02:49,530 --> 00:03:06,109
[Hal Turing] Okay — memory you touch directly, but you have to manually tell the hardware when something's actually safe, and you pay a tax for small writes. Now, the other half of this paper is 'learned indexes.' What actually is that, and why trust a model over a plain B-tree?

8
00:03:06,109 --> 00:03:50,645
[Dr. Ada Shannon] This traces to a 2018 paper out of Google, 'The Case for Learned Index Structures,' by Tim Kraska and colleagues. Their insight: if keys are sorted in an array, finding a position is a regression problem, not a traversal problem. Train a tiny linear model — position equals a times key plus b — and it beats a cache-optimized B-tree using a fraction of the memory. They stacked these into a hierarchy called a recursive model index, or RMI, though it was read-only. That gap closed in 2020 with ALEX, a Microsoft Research paper led by Jialin Ding — also a co-author on this APEX paper — using gapped arrays: sorted arrays with deliberate empty slots so inserts don't shift everything.

9
00:03:50,645 --> 00:04:05,273
[Hal Turing] Honestly, that's elegant — trading a memory-chasing tree walk for one cheap multiply-and-add. Feels like it should've taken over everywhere by now. If a model beats a B-tree on speed and memory, why hasn't every serious database switched?

10
00:04:05,273 --> 00:04:26,682
[Dr. Ada Shannon] I'd push back on 'should have,' Hal. Six years after that paper, learned indexes still aren't the index engine inside any major production database. Every one of these — RMI, ALEX, PGM-index, now APEX — is a bespoke, hand-built C++ artifact. There's no pip-install version; you handle out-of-distribution keys and retraining by hand, every time.

11
00:04:26,682 --> 00:04:41,589
[Hal Turing] No, no — I think you're underselling it, though. The speed numbers keep showing up, reproducibly, across a decade of independent papers. That has to count for something, even if shipping it is painful. Slow adoption doesn't mean the idea's wrong.

12
00:04:41,589 --> 00:04:58,865
[Dr. Ada Shannon] That's fair — and it's exactly the gap this paper closes: engineering the idea into something durable enough to trust with real data. Which is why persistent memory matters here — it's the step that makes a learned index an actual systems component, not just a DRAM-only demo.

13
00:04:58,865 --> 00:05:07,782
[Hal Turing] So what actually happens if you just take ALEX, unmodified, and point it at Optane? I'm guessing 'it just works' isn't the answer, or this paper wouldn't need to exist.

14
00:05:07,782 --> 00:06:04,717
[Dr. Ada Shannon] Two failure modes, both in the paper. Run ALEX unmodified — they call it 'Unsafe.' It's fast, but zero crash consistency: ALEX shifts records across a gapped array on every insert, and a crash mid-shift corrupts the index. The obvious fix is PMDK, Intel's standard PM library, wrapping operations in logged transactions. That variant, 'Naive,' restores consistency, but logs every shift before applying it, saturating the exact write bandwidth persistent memory is already short on — it barely scales past a few threads. So the real target is crash consistency: after any crash, the index recovers to a valid state, ideally with instant recovery — back online in milliseconds, not minutes of rebuilding. And that's exactly why APEX's answer isn't 'log smarter' — it's 'stop shifting records at all.' That's the real trick in this paper: probe-and-stash.

15
00:06:04,717 --> 00:06:17,906
[Hal Turing] Okay, 'probe-and-stash' — walk me through it. You said earlier a data node is basically a hash table with the model as the hash function. So what happens when two keys hash to the same slot, which I assume happens constantly?

16
00:06:17,906 --> 00:06:56,683
[Dr. Ada Shannon] Right, that's a collision, and APEX handles it with bounded linear probing capped at sixteen slots — which not coincidentally is exactly two of those 256-byte XPLines we talked about, so a worst-case probe still only touches memory the hardware was going to move anyway. If all sixteen slots are full, the record doesn't shift anything else — it spills into a separate overflow area called the stash. No record ever moves once it's placed. That single design choice is what kills the write amplification: an insert becomes one small write into a free slot, not a cascade of shifts down the array like ALEX's gapped structure forces.

17
00:06:56,683 --> 00:07:10,429
[Hal Turing] And because probing only ever goes one direction — forward from the predicted slot — that's also why two threads probing the same node can't deadlock on each other, right? That felt like a small detail in the paper but it's doing a lot of work.

18
00:07:10,429 --> 00:07:47,906
[Dr. Ada Shannon] Exactly, and it pays off again in the numbers: in most cases APEX issues exactly one PM write per insert, update, or delete — versus, they measure, more than ten for BzTree per insert. Same idea drives the node sizing. Data nodes are capped at 256 kilobytes specifically so a structural modification — a split or expansion — stays cheap to retrain and copy. Inner nodes get to be huge, up to sixteen megabytes, because SMOs up there are rare, and a big fan-out keeps the tree shallow — average depth barely over one on the easy datasets.

19
00:07:47,906 --> 00:08:06,204
[Hal Turing] So small nodes where change is frequent, big nodes where it's rare — that's just matching node size to how often you pay the reorganization cost. What about the DRAM side? You mentioned accelerators earlier — fingerprints, bitmaps — sitting outside PM entirely.

20
00:08:06,204 --> 00:08:54,269
[Dr. Ada Shannon] That's the part I think is most underrated in this paper. Plenty of prior PM indexes also keep hot metadata in DRAM — inner nodes, mostly — but the catch is that DRAM content vanishes on a crash, so on restart you have to rebuild it from PM before serving a single query, and that rebuild scales with data size. APEX's fingerprints and free-slot bitmaps are deliberately designed to be cheap to reconstruct from what's already sitting in PM, on demand, per node, not all at once. Structural changes themselves are made crash-safe with a hybrid logging scheme — undo logging while a split or expansion is mid-flight doing the expensive retraining and copying, then it flips to redo logging for the last, cheap step of swapping pointers. So a crash mid-SMO either rolls back cleanly or just replays a few pointer writes.

21
00:08:54,269 --> 00:09:05,833
[Hal Turing] And concurrency has to interact with all of that without threads stepping on each other during a split. How does APEX avoid the classic optimistic-locking problem where every writer forces every reader to retry?

22
00:09:05,833 --> 00:09:43,124
[Dr. Ada Shannon] It uses version numbers per lock region — readers never take a lock, they just check the version before and after and retry only if it changed underneath them. The clever part is SMOs happen out-of-place: expanding a node means allocating a new one and atomically swapping the parent's pointer, so a reader either sees the old node fully intact or the new one fully intact, never a half-built structure. That's what lets them claim retry-free traversal even under concurrent structural changes, which is genuinely harder to pull off in a learned index than a B-tree, because you're retraining a model, not just re-linking pointers.

23
00:09:43,124 --> 00:09:52,690
[Hal Turing] Okay, so tally it up for me — what does all of this actually buy in the benchmarks? Because 'up to fifteen times faster' is the number in the abstract.

24
00:09:52,690 --> 00:10:27,242
[Dr. Ada Shannon] On the friendlier datasets, yes — up to about fifteen times BzTree on inserts, with solid multi-x wins over LB+Tree, FAST+FAIR, DPTree, uTree and FPTree too, and APEX leads outright on search, update, delete and scan across nearly every dataset they test. Recovery is the other headline: roughly forty-two milliseconds, because undoing an in-flight SMO is bounded by thread count, not data size — versus multi-second to tens-of-seconds rebuilds for indexes that keep inner nodes in DRAM without APEX's reconstructable design.

25
00:10:27,242 --> 00:10:29,796
[Hal Turing] So it just wins, full stop — across the board.

26
00:10:29,796 --> 00:10:45,075
[Dr. Ada Shannon] No, I actually disagree with that framing, Hal. There's one dataset — FB, Facebook user IDs, deliberately the hardest one to fit with a linear model — where APEX loses on inserts. 5.77% slower than LB+Tree, 42% slower than DPTree.

27
00:10:45,075 --> 00:10:52,923
[Hal Turing] But that's one dataset out of six, and a single-digit-to-low-double-digit gap. That barely dents 'up to fifteen times faster,' does it?

28
00:10:52,923 --> 00:11:15,679
[Dr. Ada Shannon] It dents the framing, not the paper. When the data doesn't fit the model, collisions spike, more inserts route to the stash, and that's exactly the overflow ratio in their own table — nearly half the keys on FB. APEX still wins on search even there, which tells you the degradation is contained to inserts. I just don't want us saying 'wins everywhere' when their own hardest test case says otherwise.

29
00:11:15,679 --> 00:11:28,310
[Hal Turing] Fair — leads on five of six for inserts, wins search everywhere including FB, and recovers in milliseconds regardless of which dataset broke it. That's a more honest sentence than the abstract's headline number.

30
00:11:28,310 --> 00:11:53,759
[Hal Turing] So Ada, before we tally the scorecard, I want to push on something. Optane DCPMM got discontinued in 2022 — the same year this paper landed at VLDB. This whole design leans hard on very specific Optane quirks: the ADR domain, the 256-byte XPLine, eight-byte atomic writes. If the hardware's gone, how much of APEX actually survives?

31
00:11:53,759 --> 00:12:33,419
[Dr. Ada Shannon] Some of it clearly transfers, some doesn't. The big idea — treat a data node as a hash table with the model as the hash function, and be judicious about what lives in DRAM — that's hardware-agnostic, and I'd bet it shows up again on CXL-attached memory. But the tuning is Optane-specific. Capping probing at sixteen slots so you never cross more than two XPLines, the exact flush-and-fence ordering into the ADR domain, node sizes calibrated to Optane's three-to-four-times write-versus-read bandwidth gap — none of that just recompiles onto a successor with different latency and granularity. That part gets re-derived, not ported.

32
00:12:33,419 --> 00:12:44,472
[Hal Turing] That's a fair split. Here's the one that bugs me more, though — every experiment uses fixed eight-byte numeric or double keys. Variable-length keys are pushed to a footnote as future work.

33
00:12:44,472 --> 00:13:25,664
[Dr. Ada Shannon] Right, footnote two. And that matters because real OLTP tables use string and composite keys constantly. B+-tree baselines like FAST+FAIR handle that more naturally since they're not relying on a regression model over a numeric key space. There's a real chance some of that reported margin evaporates once you're modeling strings instead of doubles. And it compounds with another gap: PM's whole pitch in the introduction is capacity — cheap 128 to 512 gigabyte DIMMs replacing DRAM at scale. Every dataset here tops out under four gigabytes, 150 to 260 million keys. That's nowhere near the regime that actually justifies choosing PM over DRAM in the first place.

34
00:13:25,664 --> 00:13:45,633
[Hal Turing] Wait, wait, wait — hold on, before you move off recovery, I want to flag something from that table. The forty-two millisecond number is time-to-accept-requests. But Figure 17 shows APEX still needs almost two full seconds on one thread, or a hundred fifty milliseconds on twenty-four, before throughput actually peaks.

35
00:13:45,633 --> 00:14:11,779
[Dr. Ada Shannon] That's the honest caveat, yes. Forty-two milliseconds is technically true — it's the time to start serving — but it's not the time to serve well. And that warm-up scales with data size, so at billions of keys instead of a hundred fifty million, that curve stretches out further. It's still faster than uTree or LB+Tree's multi-second rebuilds, so the headline comparison holds up. But quoting forty-two milliseconds alone as an SLA number would be misleading.

36
00:14:11,779 --> 00:14:51,392
[Hal Turing] Which gets me wondering how much of APEX's edge is genuinely new algorithm versus clever reuse. Probe-and-stash is explicitly adapted from Dash — Baotong Lu's own prior paper with Xiangpeng Hao, Tianzheng Wang, and Eric Lo, PVLDB 2020, out of Chinese University of Hong Kong and Simon Fraser. The fingerprint trick comes from FPTree, Oukid and colleagues out of SAP and TU Dresden, 2016. And several baselines here — LB+Tree, FAST+FAIR, uTree, DPTree — were patched by APEX's own authors, in their words, in best effort.

37
00:14:51,392 --> 00:15:14,287
[Dr. Ada Shannon] And that last part is exactly what makes me skeptical. When you're the one fixing the competitor's missing PMDK integration and its isolation-level bug, you control how strong that competitor shows up in your own table. Combine that with borrowing Dash's stash bucket and FPTree's fingerprint, and I'd call this recombination engineering dressed up as a new index, not a genuinely novel algorithm.

38
00:15:14,287 --> 00:15:41,965
[Hal Turing] I actually disagree with you there, Ada. Recombination under real constraints is still hard. Nobody had made a learned index crash-consistent before this. The hybrid undo-then-redo logical logging around SMOs is built specifically around the fact that model retraining is the one slow step — that's a new mechanism, not a relabeled old one, even if the collision handling has ancestry in Dash.

39
00:15:41,965 --> 00:16:10,015
[Dr. Ada Shannon] Fine, I'll meet you halfway — solving crash consistency for a learned index is a real first, and that's worth crediting. But I still want one asterisk on the table: the crash-safe insert banks on modern x86 not reordering writes within a cacheline, while the paper itself says only eight-byte PM writes are formally atomic. That's a reasonable engineering bet, not a proven guarantee, and it's the one place I'd want more scrutiny before calling this bulletproof.

40
00:16:10,015 --> 00:16:39,086
[Hal Turing] That's a good note to close on. So — can a learned index run natively on persistent memory without giving up the speed that made it attractive? Yes, convincingly, for fixed numeric keys at the scale they tested. Whether it holds at string keys and multi-hundred-gigabyte capacity, and whether the crash-consistency machinery survives past Optane, are the open questions the paper leaves for whoever picks this up next. That's APEX. Thanks for listening, and we'll catch you next time.