1
00:00:01,000 --> 00:00:51,155
[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 a systems paper called SALI: A Scalable Adaptive Learned Index Framework based on Probability Models. That's Jiake Ge et al. — eight authors total — out of Renmin University of China, Tsinghua University, the Shanghai Qi Zhi Institute, and Tencent Inc. It was submitted to arXiv in September 2023 and published at SIGMOD 2024. Here's the number that got me: the prior state-of-the-art learned indexes don't just plateau under heavy concurrency — in the paper's own experiments, throughput can actually go down as you throw more threads at them. That's the opposite of what you want from a database index.

2
00:00:51,155 --> 00:01:28,910
[Dr. Ada Shannon] Right, and that's the real hook here — this isn't a paper claiming a faster index in isolation, it's a paper diagnosing why two well-regarded learned indexes, ALEX and LIPP, basically fall over once you scale past a few dozen threads on modern multi-core hardware. Everyone building these structures assumed the hard part was making the model accurate. Turns out the hard part, once you add concurrent writers, is bookkeeping — the statistics you maintain to know when your structure needs to reorganize itself become the bottleneck, not the model math. So SALI's whole pitch is: keep the good parts of these designs, but rip out the part that doesn't scale.

3
00:01:28,910 --> 00:01:39,034
[Hal Turing] Okay, let's back up, because I think some listeners are picturing a neural net doing database lookups, and that's not it at all. What is a learned index, in plain terms?

4
00:01:39,034 --> 00:02:25,056
[Dr. Ada Shannon] So a normal database index — a B+Tree — finds your key by walking down a tree, comparing at each level, root to leaf, order log N. A learned index throws that out and says: if I sort all my keys, they trace out a cumulative distribution function. If I fit a simple model — often just linear regression — to that CDF, I can plug a key in and get a predicted position directly, then do a tiny local correction if I'm off. This traces back to Kraska, Beutel, Chi, Dean, and Polyzotis's 2018 SIGMOD paper out of Google, 'The Case for Learned Index Structures,' which introduced the Recursive Model Index, or RMI. It showed you could beat a B+Tree on speed and memory using something closer to arithmetic than a tree traversal.

5
00:02:25,056 --> 00:02:37,038
[Hal Turing] So it's less 'AI' and more 'a regression line pretending to be a search tree.' I can respect that. But RMI was from 2018 — why are we still writing papers about this six years later?

6
00:02:37,038 --> 00:03:21,016
[Dr. Ada Shannon] Because RMI had a glaring hole: it was built for static, read-only data. The moment you insert a key, you can shift where every subsequent key should map to, and the model doesn't know that happened. Fixing that spawned a whole sub-field. Two camps emerged. Buffer-based designs, like XIndex from Tang et al., 2020, out of Shanghai Jiao Tong, presented at PPoPP, stage new keys in a side buffer and merge periodically instead of touching the model. Model-based designs, like ALEX from Ding, Minhas, and colleagues at Microsoft Research in 2020, reserve empty gaps inside nodes so new keys can drop in directly, no buffer needed.

7
00:03:21,016 --> 00:03:31,837
[Hal Turing] Okay, wait, so — sorry, jumping in here — if ALEX reserves gaps, what happens when the gap's already full and two keys want the same slot? That seems like it'd get messy fast.

8
00:03:31,837 --> 00:04:26,543
[Dr. Ada Shannon] That's exactly the fork in the road. ALEX resolves it by shifting — it slides neighboring keys over to open space, which works, but it moves data around, introduces new prediction error, and forces you to take a coarse-grained lock over a wide chunk of the array while you do it. LIPP, from Wu, Zhang, Chen, and colleagues, VLDB 2021, resolves it differently: instead of shifting, it chains — when a slot's occupied, it just grows a new child node downward and pushes the conflicting key there. No data movement, lookups stay precise, and because you're only touching one small node, you can use fine-grained locking instead of locking a whole region. That model-based-plus-chain design is what the paper shorthands as Mod.+C, and it's the foundation SALI is built directly on top of.

9
00:04:26,543 --> 00:04:36,342
[Hal Turing] So chaining sounds strictly better on paper — precise, fine-grained locks, no shifting overhead. Then why is this whole paper necessary? What actually breaks?

10
00:04:36,342 --> 00:05:21,203
[Dr. Ada Shannon] Because fine-grained locks solve the data contention problem, not the statistics contention problem. In the paper's motivating experiments, they take ALEX-plus and LIPP-plus — concurrency-hardened versions of both — and hammer them with increasing thread counts. ALEX-plus chokes because its shift operations still need those coarse locks across wide regions, so threads pile up waiting on each other. LIPP-plus dodges that, but it still needs shared counters at each node to decide when a subtree has gotten skewed enough to reorganize — and under high concurrency, every thread hitting that same counter turns into cacheline ping-pong. Different failure mode, same result: the curve that should climb with more threads instead flattens or drops.

11
00:05:21,203 --> 00:05:29,794
[Hal Turing] So both roads — shift and chain — eventually hit a wall, just from different directions. That's a pretty clean setup for whatever SALI's actually proposing to fix it.

12
00:05:29,794 --> 00:05:49,717
[Dr. Ada Shannon] Exactly, and that's where we're headed next — SALI keeps LIPP's chained, fine-grained-lock foundation, since that's the one with the better scalability bones, and then goes after the statistics bottleneck directly, with a couple of ideas about letting nodes adapt themselves and estimating when they need to without a shared counter anyone has to fight over.

13
00:05:49,717 --> 00:06:29,237
[Dr. Ada Shannon] Right — need to evolve before things degrade, not after. So SALI's whole pitch rests on two legs. First, node-evolving strategies: instead of one blunt 'retrain when things get bad' response, a node can expand to grab more gaps, flatten to shrink lookup depth, or compress to shed unused space, depending on what it's actually experiencing. Second, and this is the clever part, they replace the shared counters LIPP+ was choking on with probability models — instead of every thread incrementing a real counter and fighting over a cacheline, each thread runs a lightweight coin-flip that's been tuned to fire at roughly the right rate. No shared state to contend over, but statistically it behaves as if you were counting precisely.

14
00:06:29,237 --> 00:06:43,448
[Hal Turing] Okay, that's a neat trick, but I want to poke at it — a coin flip instead of a counter sounds like you're trading accuracy for speed. How do they actually calibrate the coin so it fires at the right moment instead of just randomly triggering retraining whenever?

15
00:06:43,448 --> 00:07:22,318
[Dr. Ada Shannon] So for inserts, they track a ratio they call P_acc — current node size over the size at the last evolve, with a tolerance constant beta set to 2. Once that ratio hits 1, you evolve for sure; below that, they run what's literally a Bernoulli trial weighted by how close you are, so nodes with more accumulated inserts are proportionally more likely to trigger. And conflicts get a companion signal: since collisions arrive somewhat randomly, they model the count of inserts-until-next-conflict with a geometric distribution, so a single collision is enough to estimate whether the node's degrading, without ever needing a running conflict counter shared across threads.

16
00:07:22,318 --> 00:07:32,860
[Hal Turing] And that's just the write side. What about reads — because presumably a node getting hammered with lookups needs its own trigger, and you can't exactly count 'conflicts' on a read path.

17
00:07:32,860 --> 00:08:05,507
[Dr. Ada Shannon] Exactly, so for reads they introduce a separate hyperparameter, P_hl — literally just a fixed probability that gets checked periodically, every ten lookups per thread via a local skip-counter. If that check fires, and the node also shows healthy insert activity via P_acc, SALI flags it as a hot-read node and queues it for the flattening operation. It's deliberately simple — no adaptive tuning on the read side the way there is on the insert side — which is honestly one of the softer parts of the design, but it's cheap, and cheap is the entire point here.

18
00:08:05,507 --> 00:08:14,934
[Hal Turing] So walk me through what actually happens physically to a node once one of these gets triggered — like, expand versus flatten versus compress, concretely.

19
00:08:14,934 --> 00:09:04,393
[Dr. Ada Shannon] Expand is the simplest: an insert-heavy node gets rebuilt with more reserved gaps, sized proportionally to how fast it's been accumulating keys — faster insert rate, bigger expansion factor. Flatten targets hot-read subtrees: instead of one linear model per node stacked several levels deep, SALI merges the top-k largest gaps into fewer, wider segments and uses SIMD to scan across them in one shot, which collapses tree height directly into lookup latency savings. And compress is the inverse for cold nodes — nodes that land in a randomly sampled 'cooling pool' and never get touched again get their gaps stripped out entirely and re-fit with a PGM-style piecewise linear approximation, trading insert headroom for a smaller footprint since nobody's inserting there anyway.

20
00:09:04,393 --> 00:09:16,003
[Hal Turing] Oh wait, wait — hold on, that cooling pool detail is interesting, because if a node's sitting there getting reused for lookups while it's being compressed, doesn't that risk a reader grabbing a half-rebuilt structure?

21
00:09:16,003 --> 00:10:04,440
[Dr. Ada Shannon] That's exactly the concurrency problem they had to solve, and it's not glamorous — it's textbook systems engineering. Writes take an optimistic lock on just the target slot, so conflicts are rare and cheap. Evolving itself uses read-copy-update: the new structure gets built off to the side, and only after it's fully ready does SALI swap the pointer, so any reader mid-traversal just keeps seeing the old, consistent version until the swap lands. And to make sure nobody frees a node a reader is still walking through, they layer in epoch-based reclamation on top — nothing gets physically freed until every thread has passed through a safe checkpoint. None of it is novel in isolation; McKenney's RCU work goes back to 2001. It's the fact that they needed it at all here that tells you how seriously they took the lock-free requirement.

22
00:10:04,440 --> 00:10:11,081
[Hal Turing] Alright, so does all this machinery actually pay off, or is this an elegant solution to a problem that only saves you a few percent?

23
00:10:11,081 --> 00:10:58,356
[Dr. Ada Shannon] It pays off, and not marginally. At 64 threads, SALI beats the second-best learned index, ALEX+, by 2.04x average insertion throughput, while matching LIPP+ on lookups — so you're not trading read speed for the write win. On the genuinely hard datasets, OSM and GENOME, where the CDF is nasty to fit, the gap widens to 2.5x to 10x over the other learned indexes, because SALI's evolving structure adapts to that difficulty instead of choking on it. Tail latency is maybe the most telling number: while LIPP+ and ALEX+ spike hard as thread count climbs, SALI just stays flat. And cold-node compression isn't just theoretical — it cuts space by 31 to 37 percent on those same hard datasets under skewed workloads.

24
00:10:58,356 --> 00:11:06,437
[Hal Turing] And presumably they didn't just take the probability model on faith — did they actually test it against the alternative, high-contention counters?

25
00:11:06,437 --> 00:11:59,007
[Dr. Ada Shannon] They did an ablation specifically for that. Three variants: raw high-contention counters, a sampling-based approach borrowed from Anneser et al.'s adaptive hybrid indexes out of TUM, 2022, and their own probability model. The probability version beats the sampling approach by up to 35% at 60 threads, and obliterates the high-contention baseline. Worth noting, too, this whole framing — that ALEX+ and LIPP+ collapse under concurrency in the first place — isn't SALI's discovery. That's Wongkham et al.'s GRE benchmark paper from VLDB 2022, which built ALEX+ and LIPP+ and diagnosed exactly where they break. SALI is very explicitly the fix built on top of somebody else's diagnosis, which is a perfectly respectable way to write a systems paper, just worth being clear-eyed about.

26
00:11:59,007 --> 00:12:07,831
[Hal Turing] That's a good place to pause, because 'clear-eyed' is exactly the mode I want to switch into next — how far does this actually generalize, and what didn't they test.

27
00:12:07,831 --> 00:12:53,574
[Dr. Ada Shannon] Clear-eyed it is. Here's the big one: every number we just gave you — the 2.04x, the tail latency, the 31-37% compression — is measured on SALI bolted onto LIPP, the Mod.+C structure. Section 5 of the paper says the probability models and evolving strategies 'can potentially be applied to' ALEX-style shift structures and buffer-based ones like XIndex and FINEdex. That's the actual language — potentially. There's zero experiments on a second base structure. And that collapse diagnosis this whole paper opens with, from Wongkham et al. out of Monash and PolyU — 'Are Updatable Learned Indexes Ready?' — I'd want to see SALI's fix actually demonstrated on the structure it claims generalizes to, not asserted in a paragraph.

28
00:12:53,574 --> 00:13:46,701
[Hal Turing] Right, so SALI is explicitly standing on Wu et al.'s LIPP, 2021 VLDB, and layering probability-triggered evolving on top of an already-known collapse pattern. Fine, that's honest framing if they'd stopped there. But here's what bugs me on the mechanism side: the whole probability model runs on hand-picked constants. Beta is 2, alpha is 0.1, theta is 1, there's this P_hl hyperparameter for read triggers, and that epsilon correction is literally path_size divided by 1000. Every one of those is labeled 'rule of thumb' in the paper. No sensitivity sweep, no ablation across datasets or skew levels. So if I deploy this on a workload that doesn't look like their five SOSD datasets, am I re-tuning five magic numbers blind?

29
00:13:46,701 --> 00:14:36,020
[Dr. Ada Shannon] That's the practitioner's nightmare scenario, yeah. And it compounds with something deeper — the Bernoulli and geometric distribution triggers aren't measuring reality, they're simulating it. The whole pitch is 'as if the timing were determined by accurate statistics,' their words. That's an explicit accuracy-for-low-contention trade. Which means evolving can fire early, late, or not at all relative to actual degradation, and the paper never quantifies that error margin. Under steady synthetic insert rates across a two-socket, 384 gigs of DRAM machine, sure, the coin flips average out fine. Under a bursty, non-stationary production stream — flash sale traffic, log-structured appends — nobody tested whether that stochastic approximation drifts into pathological over- or under-evolving.

30
00:14:36,020 --> 00:15:14,937
[Hal Turing] Oh, hold on, wait — that actually connects to something that bugged me reading the limitations section. The read-evolving strategy needs to be manually toggled on or off depending on whether your dataset is 'easy' or 'hard' to fit. The paper straight up says determining that benefit automatically 'can be challenging' and punts it to future work. So the headline adaptive numbers assume an operator already knows the answer to the question the system is supposedly adapting to. For a paper whose name is literally Scalable Adaptive Learned Index, that's a pretty significant asterisk on the word adaptive.

31
00:15:14,937 --> 00:16:01,423
[Dr. Ada Shannon] It is, and it's not the only asterisk. SALI still doesn't support duplicate keys, inherited straight from LIPP's limitation — Wu et al. sketched an overflow-list pointer as an easy fix, but SALI's authors just defer it too. Real relational workloads have foreign keys and duplicate-heavy columns constantly, so that's a real gap in the 'general-purpose index' framing. And range queries — Figure 24b — SALI trails ALEX+ because its gap-and-pointer layout forces branchy scans. Their fix, SALI+Comp, assumes you already know which nodes are hot-scan nodes, a mechanism that doesn't exist yet. That's a live regression against a widely deployed baseline, tucked into the appendix rather than the headline results.

32
00:16:01,423 --> 00:16:48,049
[Hal Turing] So stepping back to who should actually care about this: it's squarely for in-memory, multi-core OLTP or key-value engines with high concurrent insert rates and integer or otherwise simple keys — the LIPP-shaped world. If you're disk-resident, or you're on a buffer-based design, or your workload leans on range scans and duplicates, the paper simply hasn't earned your trust yet, and that includes the disk-resident angle they gesture at in the motivation but never test — Lan et al.'s 'Updatable Learned Indexes Meet Disk-Resident DBMS,' RMIT and Melbourne, 2023, is the paper that actually found statistics maintenance behaves very differently once I/O, not memory bandwidth, is your bottleneck.

33
00:16:48,049 --> 00:17:30,449
[Dr. Ada Shannon] Which is exactly where I'd point future work, and to be fair, the authors do flag some of this themselves — automatic tuning of the flattening depth instead of a manual toggle, duplicate-key support via the overflow-list approach, better hot-scan detection for range queries, and eventually testing on a second base structure to actually back up the generality claim. DILI, the distribution-driven learned index from Li et al. out of Aalborg and Alibaba, 2023, gets named as another candidate that 'can also' benefit — again, asserted, not tested. Until someone runs that experiment, I'd treat SALI as a strong, well-engineered optimization layer for one specific structure, not the general framework its title promises.

34
00:17:30,449 --> 00:17:58,638
[Hal Turing] So the honest takeaway: the core research question — can you scale a learned index past dozens of threads without per-node statistics choking it — gets a genuinely good answer here, and the probability-model idea for triggering evolving is a clever, well-validated piece of engineering on top of LIPP. What it isn't, yet, is proof that the same trick works everywhere the abstract implies it does. That's it for SALI — thanks for sticking with us through all three parts, and we'll catch you next time.