Topic
Data Engineering
Data engineering patterns: lakehouse architectures (Apache Iceberg), cache eviction (SIEVE, LRU), object storage (S3 conditional writes), database internals, file formats, and query engines.
59 posts · ~436 min of reading
Oct 16, 2026
AE Chunking, Solved Exactly: A 256-State Recursion, e^γ Instead of e−1, and Why Real Text Overshoots by 16%
A new ICDE 2027 benchmark of content-defined chunking finds that the standard horizon formula for Asymmetric Extremum (AE), h = µ/(e−1), produces chunks 13–39% smaller than intended. The authors call exact analysis impractical and calibrate by simulation. I show a 256-state backward recursion that gives the exact mean in microseconds and reproduces their simulated horizons (348 and 793). Its continuum limit says the formula is wrong even on continuous values: the constant is e^γ ≈ 1.781, not e−1. On this blog's own markdown, AE overshoots by 16% for a reason the byte histogram cannot explain.
Oct 16, 2026
Quake's Recall Estimator Works Because Its Geometry Is Off: Caps in d/2, a 1/e Ceiling, and a Split Example That Needs α < 0.51
Quake (OSDI '25) chooses nprobe per query by estimating recall from hyperspherical cap volumes, with no offline tuning. On SIFT1M I reproduce its Table 5 to within a point of recall. The released code computes cap volumes with sqrt(1−t²) where the textbook formula has 1−t², which is exactly the volume in 64 dimensions instead of 128. That error is what makes the estimator calibrated: the textbook formula delivers 78% recall at a 90% target. The same audit finds a 1/e ceiling on the first-partition estimate and a split example that only commits when α < 0.509. Measured α is 0.67–0.83.
Oct 15, 2026
PostgreSQL 18 Skip Scan, Measured: Skip Arrays, a Missing Increment That Doubles Descents, and Two Cliffs at One Value per Leaf Page
PostgreSQL 18 lets a B-tree on (a, b) answer WHERE b = 7700 by skipping through every distinct a. I read the nbtree source and measured PG 18.6 on 4M-row tables across 10 to 1M distinct leading values. Descents come out at exactly ndistinct + 2. Types without skip support pay 2·ndistinct + 1. The planner and the executor both give up at about one distinct value per leaf page. At that point a skip scan that kept descending would still have been 1.7× faster.
Oct 11, 2026
Aleph Filter: Growing a Quotient Filter Forever in O(1), and the Generation-Zero Term Its FPR Bounds Miss
Aleph Filter (VLDB 2024) lets a quotient filter double indefinitely without the original keys and keeps every query to one hash table by duplicating fingerprints that have run out of bits. I rebuilt its expansion logic as an exact bucket simulator. The fixed-width FPR matches Eq. 2 to two decimals. The widening and predictive bounds come in 1.3× and 1.4–1.7× too optimistic because the initial generation is twice as large as the model assumes and three generations around the target size get the same fingerprint length. One extra bit fixes the first. The longest-match delete rule holds: 0 false negatives against 536 for the shortest-match rule.
Oct 11, 2026
Breaking the Sorting Barrier for SSSP: A Working BMSSP, Pivots That Almost Never Fire, and the Tie-Break That Prevents a Livelock
Duan, Mao, Mao, Shu and Yin's O(m log^(2/3) n) directed SSSP algorithm (STOC 2025 best paper) is the first to beat Dijkstra in the comparison-addition model. I implemented it in Python and checked it against Dijkstra. It gets every distance right on graphs up to 384k vertices, using 6.6× Dijkstra's edge relaxations. FindPivots took its early exit in 849 of 850 calls on random graphs and in all 1,263 on grids. Removing FindPivots entirely cuts relaxations by 21% without any wrong answers. Dropping the paper's tie-breaking order livelocks the algorithm on the zero-weight cycles that its own constant-degree transform creates.
Oct 10, 2026
Driftsort: Rust's Stable Sort Ignores Runs Shorter Than √n, and Gets 45% Slower Just Above It
Since Rust 1.81, slice::sort is driftsort: powersort's merge policy, glidesort's lazy runs, and a branchless stable quicksort, with a √n entry threshold for pre-sorted runs. I ported its top-level loop to Python and measured the real std sort on an M3 Pro. Comparison counts match the port exactly (10.00, 9.00, 7.00 per element). But at n = 2^18, input made of sorted runs of 512 elements takes 31.0 ns/element, while runs of 511 take 21.3. Detecting the runs halves the comparisons and adds 45% to the time. I also found a counterexample to the source comment claiming its integer merge-depth trick reproduces the exact powersort tree for n < 2^30.
Oct 10, 2026
Unchained Hash Tables for Joins: The 1/169 Bloom Tag Checks Out, Except on Dense Keys, Where CRC Linearity Doubles It
Umbra's unchained join hash table (DaMoN 2024) stores tuples in a prefix-summed adjacency array and puts a 16-bit, 4-bits-per-tuple Bloom tag in the unused upper bits of every directory pointer. I reproduced the paper's false-positive model exactly (1/168.8 against the stated 1/169), though only at fill 2/3, not the stated ≈65%. I then ran the paper's CRC32C hash, checked against the M3's hardware crc32cw instruction. With dense primary keys 0..n−1 probed by the keys just past them, the filter's false-positive rate is 1/88. Each probe is 18× more likely than chance to have a build-side twin with the same slot and the same tag.
Oct 5, 2026
JumpBackHash: Constant-Time Consistent Hashing by Walking Active Indices Backwards
JumpBackHash (Ertl, arXiv:2403.18682) replaces JumpHash's O(log n) floating-point loop with an integer-only walk over power-of-two intervals, consuming under 5/3 PRG outputs on average. I ported it and every formula reproduced. On an M3 Pro (n ≥ 100) it runs at 7.5–20 ns versus JumpHash's 59–221 ns. But its bit-sharing optimizations break something the paper never tests: on multi-node resizes, each departing shard's keys spread to survivors with χ²/dof up to 1035, versus 1.0 for JumpHash.
Oct 1, 2026
Bf-Tree: Decoupling Cache Pages from Disk Pages with Variable-Length Mini-Pages
Bf-Tree (Hao & Chandramouli, VLDB 2024) keeps B-Tree pages at 4 KB on disk but drops the rule that a cached page must mirror one. Its buffer pool holds mini-pages: sorted, variable-length slices of a leaf that cache hot records, buffer writes, record negative lookups as phantoms, and grow into full-page mirrors when a range gets scanned. They live in a circular buffer with a 10% second-chance region. I simulated the caching claim: at the paper's memory ratio, record-granular caching hits 76% where page LRU hits 41%. I also found that the 1% admission default is a trade-off with warm-up time, not a free lunch.
Sep 29, 2026
Eg-walker: Replaying Event Graphs Instead of Choosing Between OT and CRDTs
Eg-walker (Gentle & Kleppmann, EuroSys 2025 best paper, arXiv 2409.14252) stores collaborative text edits as an immutable event graph and builds CRDT state only transiently, during merges — then throws it away. The result: OT-style steady-state memory (just the text), CRDT-style merge complexity O((k+m) log(k+m)), and a trace where OT needs an hour and eg-walker needs 24 ms. I built a miniature walker with prepare/effect versions and retreat/advance, and verified convergence over every valid replay order — after my first, naive concurrency tie-break diverged, which is itself the lesson: the walker's inner ordering logic must be a real CRDT.
Sep 27, 2026
OrioleDB: Undo-Log MVCC, Dual Pointers, and the End of VACUUM
OrioleDB is a PostgreSQL storage engine (now in public beta) that replaces the heap with index-organized B+-trees and rebuilds the three mechanisms everyone complains about: MVCC keeps old versions in an undo log instead of bloating the table, in-memory pages point directly at children so there's no buffer mapping table to serialize on, and WAL is logical row-level records that can be applied in parallel. On a bloat-inducing upsert benchmark the result is 5x the TPS at 22x fewer IOPS per transaction — but the trade-offs (no persistent rightlinks, fuzzy copy-on-write checkpoints, a patched Postgres) are just as instructive as the wins.
Sep 24, 2026
PostgreSQL 18's Async I/O: Completion Callbacks That Live in Shared Memory
PostgreSQL 18 shipped the largest storage-layer change in decades: reads now go through a real asynchronous I/O subsystem instead of posix_fadvise hints and kernel readahead. The interesting part isn't the io_uring integration — it's the design constraints. Any backend must be able to complete any other backend's I/O (to avoid a distributed deadlock through shared buffers), so completion callbacks live in shared memory, are addressed by one-byte IDs instead of function pointers, and are forbidden from raising errors. Cold-cache sequential scans get 2–3x faster, and EXPLAIN ANALYZE starts lying to you in a new way.
Sep 23, 2026
MUVERA: Collapsing Multi-Vector Retrieval into One MIPS Query
ColBERT-style late interaction scores a query against a document with Chamfer similarity over token embeddings — a sum of maxes that no off-the-shelf vector index can serve. MUVERA (Google, NeurIPS 2024) compresses each token set into one Fixed Dimensional Encoding whose plain inner product ε-approximates Chamfer, turning the whole problem into standard single-vector MIPS: 10% higher recall than PLAID at 90% lower latency, with a provable guarantee. A from-scratch reimplementation shows why it works — the estimator is heavily biased (−0.21) but almost uniformly so (σ=0.02), and the asymmetric sum/average construction plus fill_empty_clusters carry the ranking.
Sep 21, 2026
DuckLake: What Happens When Lakehouse Metadata Stops Pretending It Isn't a Database
Iceberg and Delta were designed so table metadata could live as files on object storage — then both quietly bolted a database-backed catalog on top to get atomic commits. DuckLake (DuckDB Labs, 2025) follows that concession to its logical end: put ALL metadata — snapshots, schemas, file lists, statistics — in ordinary SQL tables, keep only Parquet data and delete files on the object store. Query planning collapses from a chain of sequential S3 GETs over JSON and Avro manifests into one SQL query; commits become row inserts in an ACID transaction, which makes multi-table transactions and million-snapshot histories free.
Sep 21, 2026
Untorn Writes: How RWF_ATOMIC Lets Databases Finally Delete the Doublewrite Buffer
Every serious database pays a tax for one hardware lie: a 16 KB page write can tear in the middle of a power failure, so InnoDB writes every page twice and PostgreSQL stuffs full page images into its WAL. Between Linux 6.11 and 6.16, the kernel grew a real answer — RWF_ATOMIC, a per-write torn-write guarantee negotiated through statx, backed by NVMe/SCSI atomicity limits, XFS forced extent alignment, ext4 bigalloc, and a copy-on-write software fallback when the hardware can't promise enough. This is how the whole stack fits together, and why the constraints (power-of-two, naturally aligned, direct I/O) are exactly what they are.
Sep 17, 2026
Grafite: Range Filters That Survive Adversarial Queries
Range filters answer 'does any key fall in [a,b]?' with one-sided error — and almost every practical design (SuRF, SNARF, Proteus) collapses to a 100% false-positive rate when queries land near keys. Grafite (SIGMOD '24) fixes this with a locality-preserving hash into a reduced universe plus an Elias-Fano predecessor structure: log(L/ε)+2 bits per key, O(1) queries, and an FPR bound of ℓ/2^(B−2) that holds for any workload. A from-scratch reimplementation reproduces the paper's worked example, confirms the bound within sampling noise, and shows the true FPR is 1−e^(−ℓ/2^(B−2)) — the union bound's saturation at 1.0 hides a measurable 0.632.
Sep 10, 2026
Marconi: Prefix Caching When Your Model Can't Roll Back Its Own State
Hybrid SSM/attention models break the core assumption of prefix caching: recurrent states update in place, so a cached state for tokens 1..q is useless for a request that shares only 1..p. Marconi (MLSys 2025 Best Paper) fixes this with speculative radix-tree admission and FLOP-aware eviction, lifting token hit rates up to 34.4x over per-block checkpointing. My own eviction sim reproduces the win on an agentic trace (+10 hit-rate points) — and shows the same policy halving the hit rate on a chat trace, which is exactly why Marconi auto-tunes its eviction knob.
Sep 9, 2026
Lance: Random Access in Columnar Storage Without Giving Up Scans
Columnar formats are supposedly bad at point lookups. Lance (arXiv 2504.15247) shows the real culprit is how formats encode structure — validity and repetition — not columnar layout itself. Two adaptive encodings, mini-block and full-zip, cap any random access at 2 IOPS regardless of nesting depth. The numbers check out: default Parquet manages ~5.5K rows/sec where tuned layouts hit 350K, a 63.6x gap my own arithmetic reproduces.
Sep 7, 2026
The 04261537 Order: FastLanes and the Layout That Makes Decoding Data-Parallel
Bit-packing decoders are slow not because the arithmetic is hard but because the layout serializes it. FastLanes reorders values against a virtual 1024-bit register so that plain scalar C auto-vectorizes into something fast. I brute-forced its uniqueness proof (the paper has a typo), then measured it on an M3 Pro: 22-26x over a conventional bit-unpacker, and the compiler beating my hand-written quasi-SIMD by 2.2x.
Sep 7, 2026
Diskless Kafka: What Happens When the Log's Replication Protocol Becomes a PUT
KIP-1150 and KIP-1163 propose a leaderless Kafka topic type where any broker accepts produces, batches from many partitions share one WAL object, and a batch coordinator assigns offsets after upload. I worked through the design and ran the cost model: the cross-AZ advantage converges to ~41x on AWS, and the KIP's own P50 latency target carries ~2x headroom over the sum of its stated components.
Aug 30, 2026
OpenZL: Shipping the Compressor Inside the Compressed File
Format-aware compressors win big and then rot, because every reader needs the matching decoder. OpenZL embeds the resolved transform graph in each frame so one universal decoder handles all of them. I rebuilt its core thesis on a 10MB record table: structure-aware transforms at zstd -3 hit 2.84x, beating xz -9 on the raw bytes (2.35x) at roughly 60x the throughput — and once the structure is exposed, the entropy backend stops mattering.
Aug 27, 2026
The Move Structure: What Actually Makes a BWT-Runs Index Fast
Nishimoto and Tabei's move structure turns LF mapping on a run-length BWT from a predecessor search into a pointer dereference plus a short local scan, and the theory is about bounding that scan. I built the whole thing and measured it: the balancing that bounds the scan cost 4.5% more intervals and improved throughput by nothing. The pointer is the entire win — 1.05 cache lines per LF step versus 4.01 and climbing.
Aug 26, 2026
What Comes After HyperLogLog: Registers That Stop Throwing Information Away
HyperLogLog's 6-bit register keeps one number and discards everything else the hash told you. UltraLogLog spends two more bits per register to remember what it used to forget, and ExaLogLog generalizes the base to fractional leading-zero resolution. I re-derived both papers' space-efficiency numbers from the closed form to check the 43% claim.
Aug 22, 2026
The Smallest Seed That Works Is the Wrong Seed to Store
Every randomised data structure that retries until it succeeds stores the index of the first attempt that worked. A 2025 result shows that convention is provably wasteful. I computed the exact waste — log2(e) = 1.4427 bits per seed, 44% more than the paper's own bound — and derived why that single constant is what kept minimal perfect hash functions stuck above 1.5 bits per key.
Aug 22, 2026
Rateless IBLTs: Set Reconciliation Without Knowing the Difference Size
Every set reconciliation scheme in production makes you guess the answer before you compute it. Invertible Bloom Lookup Tables need the difference size up front; guess low and decoding fails outright, guess high and you burn bandwidth. Rateless IBLTs (SIGCOMM 2024) remove the guess entirely by turning the sketch into an infinite stream of coded symbols with a 1/(1+αi) mapping density. I re-derived the closed-form index generator and simulated the peeling decoder to check the 1.35x overhead claim.
Aug 22, 2026
Your p99.9 Has an Error Bar the Width of the Entire Tail
Every metrics pipeline stores a quantile sketch with an additive rank guarantee of ±εn, then asks it for p99.9 — where only εn·(1/ε(1-q)) items even exist. I measured the resulting value error at 52%, derived why the fix needs a different guarantee shape, and traced the space bound from ReqSketch's log^1.5 down to the SODA 2025 elastic-compactor result.
Aug 20, 2026
Two Slots and a Square Root: Optimal Weak Isolation Testing
Checking whether a database actually delivered Read Committed is polynomial time, which sounds like the end of the story until you notice the state of the art was degree six. AWDIT (PLDI 2025) gets Read Committed and Read Atomic to n^1.5 and Causal Consistency to n*k, and proves you cannot do better without fast matrix multiplication. I reimplemented the core pass and fuzzed 20,000 histories to find out where the cleverness actually lives.
Aug 19, 2026
Shredding the Variant: Columnar Statistics for Schemaless JSON
Storing JSON in a data lake has always meant choosing between a rigid schema and an opaque blob. Parquet's Variant type plus its shredding spec promise both: self-describing values that still get typed columns, page statistics, and partial projection. I reimplemented the encoding and shredding rules from scratch, and found that the size win is modest, the projection win is enormous, and the data-skipping win has a cliff so sharp that one bad producer in 3,000 rows destroys it entirely.
Aug 18, 2026
Worst-Case Optimal Joins on a GPU: Flattening Skew Into a Prefix Sum
Worst-case optimal joins fix the asymptotic blowup that kills binary join plans on cyclic queries, but their attribute-at-a-time intersections are a disaster on SIMT hardware: one high-degree hub key and a single warp holds up the whole device. SRDatalog's answer is to stop scheduling keys and start scheduling work units, flattening a skewed multi-level search space into a prefix-summed 1-D array that thread blocks slice at kernel launch. I re-derived the AGM bounds behind their rule rewriting and simulated their scheduler, and the numbers say the residual bottleneck is not where the paper says it is.
Aug 17, 2026
Breaking Yao's Conjecture: Elastic and Funnel Hashing at 99.98% Load
Uniform probing was proven optimal for open addressing in 1985, and conjectured optimal in the worst case too. A 2025 paper broke the conjecture with two constructions that never move an element after inserting it. I implemented both against uniform probing and found where the crossover actually is: 99.9% load, not sooner.
Aug 17, 2026
One Multiplication Per Cycle: How Twist and Shout Rebuilt zkVM Memory Checking
Every zkVM has to prove that its reads return the last thing written. For a decade that meant permutation checks and grand products. Twist and Shout replace both with one-hot addresses and increments. I implemented the core sum-checks, counted the prover's multiplications, and found the locality optimization pays off in RAM, not registers.
Aug 14, 2026
Running TPC-H on NCCL: The Broadcast That Refuses to Scale
A distributed SQL engine built on the collective communication library used for ML training runs all 22 TPC-H queries at 1TB in 0.53 seconds on 40 H100s. The abstract leads with that. Their own breakdown figure leads somewhere else: 8 GPUs in one machine do it in 1.13 seconds, so 5x the hardware bought 2.13x. This post derives why, verifies the paper's shuffle-vs-broadcast crossover condition, finds a non-monotonicity in it the paper doesn't mention, and computes the cost-per-query that makes scaling out the worse deal.
Aug 13, 2026
Semantic Operators: Putting a Statistical Contract on 6 Million LLM Calls
A semantic join over 250 documents and 24,370 labels costs 6,092,500 LLM calls and 25 days. Getting that to 5,290 calls is the easy part. The interesting part is what the accuracy guarantee actually covers, and what it quietly does not.
Aug 4, 2026
German Strings: Why Arrow's StringView Never Saves Memory, and Wins Anyway
Arrow's Utf8View layout, lifted from TU Munich's Umbra, replaces offsets with a 16-byte struct that inlines short strings and a 4-byte prefix. The pitch is usually framed as saving memory. Do the algebra and the memory delta is 12n minus the inlined bytes, which is non-negative for every possible dataset. The real wins are elsewhere: one memory access instead of two, prefix-decisive comparisons at 99.97 percent on a real corpus, and a filter that copies pointers instead of bytes. The cost is a garbage collector you now own.
Jul 27, 2026
ACORN: Why Filtered Vector Search Breaks HNSW, and the Two-Hop Fix
Every production vector search is really a filtered vector search: find similar documents, but only for this tenant, only from last quarter, only in these languages. HNSW handles this badly, and not for the reason most people assume. The problem is that HNSW's edge pruning rule is provably wrong once you restrict the graph to a subset of nodes. ACORN fixes it by making pruning predicate-agnostic and recovering the deleted edges at query time through two-hop expansion, reaching 2x to 1,000x higher throughput at fixed recall.
Jul 27, 2026
Predicate Transfer: Yannakakis's 1981 Algorithm, Rebuilt Out of Bloom Filters
There is a 1981 algorithm that provably evaluates any acyclic join in time proportional to input plus output, and essentially no production database uses it, because its constant factor makes queries 2.4x slower on average. Predicate transfer resurrects it by replacing exact semi-joins with Bloom filters, and the 2025 follow-up work shows that the interesting part was never the filters, it was the schedule.
Jul 26, 2026
Compute on Compressed Data: What Vortex Gets Right, and What Its Benchmarks Don't
Parquet's fatal architectural choice is the opaque second compression layer. Once ZSTD touches a page, you cannot read one value without decompressing all of them, and you certainly cannot evaluate a predicate against the bytes as they sit. Vortex removes that layer and pushes comparisons into the encoded domain instead: compare an ALP-encoded float column as bit-packed integers, run a LIKE against FSST codes via a DFA over compressed symbols. The mechanism is genuinely elegant. The '100x faster random access' claim built on top of it does not survive reading the benchmark harness.
Jul 15, 2026
Accord: Leaderless Strict-Serializable Transactions in One Round Trip
Every distributed transaction protocol you have used pays a latency tax: either a leader that funnels all writes through one node, or two round trips to order operations. Accord, the protocol behind Apache Cassandra's general-purpose transactions, delivers strict serializability with no leader and one wide-area round trip on the happy path. The trick is a reorder buffer that turns bounded clock skew into a consensus guarantee.
Jul 14, 2026
ALP: How to Compress Floating-Point Data Twice as Well and Decode It 2-4x Faster
Floating-point columns are the last frontier of columnar compression: general-purpose byte compressors barely dent them, and bit-level predictors like Gorilla trade speed for ratio. ALP wins on both axes by recognizing that most 'doubles' in the wild are actually decimals in disguise, and encoding them as small integers a vectorized bit-packer can crush.
Jul 12, 2026
DBSP: Turning Any SQL Query Into an Incremental Stream Processor
DBSP is a small, complete algebra that mechanically converts any relational query into an incremental one that updates materialized views in time proportional to the change, not the data. Here is how the circuit model, Z-sets, and the differentiation identity make it work.
Jul 11, 2026
WebAssembly UDFs: Sandboxed Extensibility in Modern Database Engines
How database engines use WebAssembly to run user-defined functions with near-native speed while maintaining memory safety, deterministic execution, and zero-trust isolation within the query pipeline.
Jul 9, 2026
Coroutine Interleaving: How Database Engines Use Stackless Coroutines to Hide Storage Latency
Modern analytical databases lose 40-60% of query time waiting on storage I/O. Coroutine interleaving transforms synchronous buffer pool accesses into cooperative multitasking, letting the CPU process other tuples while pages load from SSD. We explore the LeanStore and Umbra approaches, C++20 coroutine mechanics, and why this outperforms both blocking I/O and pure async callback models.
Jul 9, 2026
Hybrid Logical Clocks: Bridging Physical Time and Causality in Distributed Databases
How Hybrid Logical Clocks combine NTP-synchronized physical time with Lamport causality to provide globally meaningful timestamps without coordination, enabling snapshot isolation and serializable transactions across geo-distributed databases.
Jul 9, 2026
Learned Cardinality Estimation: When Neural Networks Replace Histograms in Query Optimizers
How modern database systems replace decades-old histogram-based cardinality estimators with neural models — covering CardBench, MSCN, and NeuroCard architectures that reduce join order estimation errors from 1000x to under 3x.
Jul 9, 2026
Memory-Mapped I/O Considered Harmful: Why Modern Databases Avoid mmap for Buffer Management
mmap() seems like the perfect database buffer pool: let the OS handle page caching, avoid copies, and get a simple pointer interface. In practice, it introduces catastrophic stalls, uncontrollable eviction, and subtle corruption. Here is why every serious DBMS builds its own buffer manager, and the systems-level reasons mmap fails at scale.
Jul 9, 2026
Shared Log Architecture: How Cloud-Native Databases Disaggregate Storage from Compute
The shared log pattern decouples compute from storage by treating a replicated, append-only log as the single source of truth. This deep dive explores how systems like Aurora DSQL, Neon, and FoundationDB leverage this architecture to achieve independent scaling, instant recovery, and strong consistency without distributed two-phase commit.
Jul 8, 2026
Adaptive Radix Trees: How Modern Databases Achieve Sub-Microsecond Lookups
Dissecting ART (Adaptive Radix Tree), the cache-conscious indexing structure that outperforms B-trees for in-memory workloads by collapsing node sizes, eliminating key comparisons, and exploiting CPU cache hierarchies.
Jul 8, 2026
Bw-Tree: Lock-Free B+ Trees for Multi-Core Database Scalability
How the Bw-Tree achieves latch-free concurrent access to B+ tree indexes through delta chains, an indirection mapping table, and epoch-based garbage collection, enabling linear scalability on modern many-core hardware.
Jul 8, 2026
MVCC Garbage Collection: Why Long Transactions Kill Throughput and How Modern Engines Fight Back
Multi-version concurrency control trades write amplification for read isolation, but version chain bloat from deferred garbage collection silently degrades scan performance by 10-100x. This post dissects the GC problem, examines PostgreSQL's vacuum pathology, and explores the epoch-based truncation and steam-cleaning techniques from LeanStore and Umbra that achieve O(1) amortized cleanup.
Jul 8, 2026
PGM-Index: How Piecewise Linear Models Replace B-Trees with O(log log n) Lookups
The Piecewise Geometric Model index uses linear regression segments to predict key positions, achieving O(log log n) point queries with orders-of-magnitude less space than B-trees. Here's the theory, the recursive structure, and why production systems are starting to care.
Jul 8, 2026
Prolly Trees: Content-Addressed Structural Sharing for Version-Controlled Databases
How probabilistic B-trees use rolling hash chunk boundaries to enable O(log n) structural diffs between database snapshots, bringing Git-like branching and merging semantics to multi-gigabyte relational datasets with minimal storage overhead.
Jul 8, 2026
Ribbon Filters: How RocksDB Achieved Near-Optimal Space with Gaussian Elimination
Inside Ribbon Filters, the Gaussian elimination based probabilistic data structure that replaced Bloom filters in RocksDB, achieving information-theoretic space optimality at the cost of a linear algebra construction step.
Jul 8, 2026
Roaring Bitmaps: Compressed Set Operations in Constant Time Per Container
How Roaring Bitmaps achieve intersection, union, and cardinality on billion-element sets in microseconds by partitioning integers into typed containers, each optimized for its density regime, and accelerated with SIMD vectorization.
Jul 8, 2026
Swiss Tables: How SIMD Rewrote the Rules of Hash Map Design
Flat hash maps based on Swiss Table design now dominate C++, Rust, Go, and Zig standard libraries. The key insight is not a better hash function or collision strategy, it is using SIMD to probe 16 slots in a single instruction, turning the control byte array into a hardware-accelerated Bloom filter.
Jul 8, 2026
Vectorized Execution: How DuckDB Processes a Billion Rows Per Second on a Laptop
Push-based pipelines, morsel-driven parallelism, and selection vectors: the three architectural bets that let an in-process database saturate modern hardware without a cluster.
Jul 7, 2026
Iceberg v3 Deletion Vectors: Fixing Merge-on-Read With One Bitmap Per File
Apache Iceberg v2 made row-level deletes possible with position delete files, and large deployments have regretted the details ever since. Format version 3 deprecates them in favor of deletion vectors, Roaring bitmaps stored in Puffin files with a hard invariant of at most one vector per data file. Here is what was broken, how the new binary format works down to the byte level, and why the length field is big-endian on purpose.
Jul 7, 2026
S3 Conditional Writes: The CAS Primitive That Killed the Coordination Sidecar
For years, every database built on object storage needed a DynamoDB table or a ZooKeeper cluster on the side just to answer "who is the writer?" In late 2024, S3 quietly shipped If-Match and If-None-Match support on PutObject, turning the object store itself into a compare-and-swap register. Here is why that one HTTP header changes how you architect storage systems, and how projects like SlateDB use it for formally verified writer fencing.
Jul 6, 2026
RaBitQ: 32x Vector Compression With an Error Bound You Can Actually Prove
Product Quantization has powered billion-scale vector search for 15 years, but it can fail badly on real datasets and offers no theoretical guarantees. RaBitQ (SIGMOD 2024) compresses vectors to one bit per dimension, estimates distances with a popcount, and comes with a provable O(1/sqrt(D)) error bound. Here is how a random rotation makes that possible.
Jul 5, 2026
SIEVE: The Cache Eviction Algorithm That Beats LRU by Doing Less
A 2024 NSDI paper showed that a FIFO queue, one bit per object, and a lazy hand pointer can out-perform LRU, ARC, and friends on web workloads, while removing the lock that makes LRU a scalability bottleneck. Here is how SIEVE works and why its simplicity is the whole point.