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.
39 posts · ~288 min of reading
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.