Application — SWE/DE — Thomas To

Each topic follows the North Star order: what the decision is, why first principles favor one answer, and how to apply it.

The RUM conjecture: read, update, memory — pick two

No access method minimizes read, write, and space overhead at once; every storage engine is a chosen point on that triangle.

What are you trying to do?

Pick a storage engine by the workload's read/write mix, not by the product's popularity.

Why are you doing it?

Making reads cheap means maintaining structure at write time (sorted pages, indexes), which costs writes. Making writes cheap means deferring that structure (append now, organize later), which costs reads or space until compaction catches up. Making space cheap means giving up redundant structures that speed up one or the other. The RUM conjecture (Athanassoulis et al., 2016) names that triangle; storage engine families are its corners.

Swipe sideways if the diagram is cut off.

Read overhead: Corner = cheap reads: few I/Os per lookup or scan
Update overhead: Corner = cheap writes: little extra data written per logical write
Memory overhead: Corner = cheap space: few extra bytes stored per live byte, including indexes

Marker positions are qualitative, drawn from the amplification column of the storage-engine table, not measured. Moving toward one corner moves away from the others.

Database Internals Designing Data-Intensive Applications (2nd ed.)

How are you going to do it?

Measure the workload first: write rate, read pattern (point vs range vs full scan), and how much data is hot.
Express engine costs as amplification: read amplification (I/Os per logical read), write amplification (bytes written per logical byte), space amplification (bytes stored per live byte).
Choose the engine whose cheap corner matches the dominant operation, then tune the knobs that move along the triangle (fill factor, compaction strategy, bloom filter size).

Storage engines: B-tree vs LSM-tree, and the rest

B-trees update in place and favor reads; LSM-trees append and compact and favor writes. Other engines fill specific corners.

What are you trying to do?

Know how each engine family turns a logical read or write into physical I/O.

Why are you doing it?

A B+tree keeps keys sorted in fixed-size pages (often 4–16 KB) with a high fan-out, so a lookup touches about log_fanout(N) pages — three or four for billions of rows — and range scans walk linked leaves. The cost is on writes: each update rewrites a whole page in place (plus a write-ahead-log record), and random inserts split pages. An LSM-tree buffers writes in a sorted in-memory memtable (backed by a WAL), flushes it as an immutable sorted SSTable, and merges SSTables in the background. Writes become sequential and cheap; reads may check several levels, so engines add bloom filters and fence pointers to skip most of them, and compaction spends I/O later to reclaim space.

B+tree write path — update in place

Find leaf page
Descend about log_fanout(N) pages
Log to WAL
Record the change for crash recovery
Modify page in place
Rewrite the whole fixed-size page
Split if full
Random inserts split pages, leaving some half full

LSM-tree write path — append and compact

Append to WAL
Sequential log for crash recovery
Insert into memtable
Sorted in-memory buffer
Flush SSTable
Immutable sorted file, written sequentially
Compact in background
Merge SSTables; reclaim space, spend I/O later

LSM-tree read path — skip what you can

Check memtable
Newest data first
Bloom filter
Skip SSTables that cannot hold the key
Fence pointers
Jump to the one block that may hold it
Read newest-first
May still touch several levels

The B+tree pays at write time to keep data organized for reads; the LSM-tree defers that work to flush and compaction.

Database Internals Designing Data-Intensive Applications (2nd ed.)

How are you going to do it?

Read-heavy OLTP with range queries and strict latency: a B+tree engine (PostgreSQL, InnoDB).
Write-heavy ingestion, time series, or key-value at scale: an LSM engine (RocksDB, Cassandra, ScyllaDB), with compaction chosen per workload — leveled for read-heavy, size-tiered for write-heavy.
Analytics: columnar files with zone maps — a different corner entirely, optimized for scans rather than lookups.

Storage engine families and their trade-offs
Engine	Write path	Read path	Amplification profile	Choose when	Examples
B+tree	Find leaf page, modify in place, log to WAL; page splits on growth	O(log N) page reads; efficient range scans across linked leaves	Low read amp; higher write amp (whole-page writes); some space lost to partially full pages	Read-heavy, point and range queries, transactional updates	PostgreSQL, MySQL InnoDB, SQLite
LSM-tree	Append to WAL and memtable; flush sorted SSTables; compact in background	Check memtable then levels newest-first; bloom filters skip most SSTables	Low write amp at ingest but compaction rewrites data; higher read and space amp until compaction	Write-heavy ingestion, time series, large key-value stores	RocksDB, LevelDB, Cassandra, ScyllaDB, HBase
Log-structured hash index	Append to log; update in-memory hash map of key → offset	One hash lookup plus one seek	Minimal read and write amp; all keys must fit in memory; no range queries	High-rate point lookups on a bounded key set	Bitcask (Riak)
Columnar + zone maps	Batch-written immutable files or row groups; updates via rewrite or delete files	Scan only needed columns; skip chunks whose min/max excludes the predicate	Excellent compression; very high cost per single-row update	Analytical scans and aggregates	Parquet, ORC, Delta Lake, Iceberg, ClickHouse
Inverted index	Tokenize and append to posting lists in immutable segments; merge segments	Look up term → posting list; intersect lists	Large index relative to data; fast term and full-text lookups	Search, log exploration, full-text filtering	Lucene, Elasticsearch, OpenSearch
Bε-tree	Buffer writes in internal nodes; flush down in batches	Near B-tree point reads; must check buffers on the path	Write cost between B-tree and LSM; read cost close to B-tree	Mixed workloads that need both cheap writes and fast reads	TokuDB / PerconaFT, BetrFS
Skip list (in-memory)	Probabilistic multi-level linked list; lock-free inserts possible	Expected O(log N) search and ordered iteration	Pointer-heavy, so cache-unfriendly; memory only	Sorted in-memory buffers	LSM memtables (RocksDB, LevelDB), Redis sorted sets

Index lookups: seek vs scan

An index helps only when it avoids enough I/O to beat a sequential scan; selectivity decides.

What are you trying to do?

Make the optimizer's access-path choice predictable.

Why are you doing it?

An index seek is a handful of random page reads per matching row; a full scan is sequential I/O over every page. Random reads cost far more per byte than sequential ones, so past a selectivity threshold (often a few percent of rows) a scan wins. Clustered indexes store rows in key order so range reads stay sequential; secondary indexes add a lookup back to the row unless they cover every column the query needs.

Full scan

Every page, sequential I/O

P1 (read)
P2 (read)
P3 (read)
P4 (read)
P5 (read)
P6 (read)
P7 (read)
P8 (read)
P9 (read)
P10 (read)
P11 (read)
P12 (read)

Index seek, selective predicate

Root, leaf, then one table page: random reads, far fewer pages

Root (read)
Leaf (read)
P1
P2
P3
P4
P5 (read)
P6
P7
P8
P9
P10
P11
P12

Index seek, low selectivity

Matching rows spread over most pages: many random reads, scan wins

Root (read)
Leaf (read)
P1 (read)
P2 (read)
P3
P4 (read)
P5 (read)
P6 (read)
P7
P8 (read)
P9 (read)
P10 (read)
P11
P12 (read)

Highlighted cells are pages read to answer the query.

Page counts are illustrative. A seek wins when it skips most pages; as selectivity drops, random reads add up and the sequential scan wins.

PostgreSQL Query Optimization High Performance MySQL (4th ed.)

How are you going to do it?

Read the plan (EXPLAIN ANALYZE) before adding an index; confirm estimated vs actual row counts, since bad statistics cause most bad plans.
Order composite index columns by equality predicates first, then range predicates; add included columns to make hot queries covering.
In InnoDB the primary key is the clustered index, so a random UUID primary key scatters inserts across pages; prefer monotonic keys.

Index types and what a lookup costs
Index	Structure	Lookup cost	Use when
Clustered (primary)	Rows stored in key order inside the B+tree leaves	One traversal; ranges read sequentially	Primary access path, range queries on the key
Secondary	Separate B+tree of key → row pointer or primary key	Traversal plus one lookup per matching row	Selective predicates on non-key columns
Covering	Secondary index that includes every column the query reads	Traversal only; no row lookup (index-only scan)	Hot, read-heavy queries with a known column set
No index (full scan)	Read every page sequentially	Linear in table size but sequential	Low-selectivity predicates, small tables, analytics

Join algorithms, from one node to a cluster

Nested-loop, hash, and sort-merge joins trade memory for I/O; Spark adds broadcast vs shuffle on top of the same three.

What are you trying to do?

Predict which join an engine will pick, and why it might pick wrong.

Why are you doing it?

A nested-loop join is cheap when the outer side is small and the inner side has an index. A hash join builds a hash table on the smaller side and streams the larger one past it — linear time, but the build side must fit in memory or it spills. A sort-merge join sorts both sides on the key and merges them — it costs a sort but needs little memory and handles any size. Distribution adds one more choice: either copy the small side to every node (broadcast), or repartition both sides by key so matching rows meet (shuffle). The shuffle is a full network exchange and is usually the most expensive step in a Spark job.

Nested loop, no index — outer rows × inner scan

Take outer row
Ideally a tiny side
Scan inner side
Full pass per outer row
Emit matches
Low memory, quadratic work

Nested loop, indexed inner — outer rows × seek

Take outer row
Small outer side
Seek inner index
One lookup per outer row
Emit matches
Low memory

Hash join — build, then probe

Build hash table
On the smaller side; must fit in memory or spill
Probe
Stream the larger side past the table
Emit matches
Linear: build + probe

Sort-merge join — sort both, merge once

Sort side A
External sort if too big for memory
Sort side B
Skipped if already sorted on the key
Merge
One linear pass over both

Distributed: broadcast — copy the small side

Broadcast small side
Copy to every node
Join locally
Large side stays in place, no shuffle

Distributed: shuffle — meet by key

Repartition both sides
Hash by join key over the network
Join each partition
Sort-merge by default for large-large

Joins trade memory against passes over the data: hash needs memory, sort-merge pays for a sort, and distribution adds broadcast or shuffle.

PostgreSQL Query Optimization Spark: The Definitive Guide High Performance Spark (2nd ed.)

How are you going to do it?

Keep statistics fresh so the optimizer knows which side is small.
In Spark, small dimension tables should be broadcast (spark.sql.autoBroadcastJoinThreshold or a broadcast hint); large-to-large joins fall back to shuffle sort-merge.
Turn on adaptive query execution (AQE, the default since Spark 3.2). It re-plans at runtime from real shuffle sizes: it switches to broadcast, coalesces small partitions, and splits skewed ones.

Join algorithms and their distributed forms
Join	Cost shape	Memory need	Best when	Spark form
Nested loop	Outer rows × inner lookup	Low	Tiny outer side with an indexed inner side	Broadcast nested loop (non-equi joins)
Hash join	Linear: build + probe	Build side in memory	One side fits in memory	Broadcast hash join; shuffle hash join
Sort-merge join	Sort both sides, then linear merge	Low (external sort)	Both sides large, or already sorted	Shuffle sort-merge join (default for large-large)

Spark execution: the same principles, distributed

Spark SQL is a relational optimizer over partitions; most tuning means reading less data and shuffling less of it.

What are you trying to do?

Turn a slow Spark job into a plan you can explain stage by stage.

Why are you doing it?

Catalyst rewrites a logical plan (pushing predicates down, pruning columns), picks a physical plan (join strategies), and Tungsten compiles stages into generated code over off-heap binary rows. A job splits into stages at every shuffle boundary, and each stage runs one task per partition. Elapsed time is therefore usually set by bytes read, bytes shuffled, and the slowest (most skewed) task — not by CPU work inside a task.

Planning — on the driver

Logical plan
What to compute, built from the query
Optimize
Push down predicates, prune columns
Physical plan
Pick join strategies; compile stages to code

Execution — on the cluster

Split into stages
A new stage at every shuffle boundary
One task per partition
Run on executors; the slowest task sets stage time
Adaptive re-plan
AQE uses real shuffle sizes: broadcast, coalesce, split skew

Elapsed time is usually set by bytes read, bytes shuffled, and the slowest task, so tuning targets those rather than CPU inside a task.

Learning Spark (2nd ed.)Spark: The Definitive Guide High Performance Spark (2nd ed.)

How are you going to do it?

Read less: partition and cluster data on common filter columns so partition pruning and predicate pushdown skip files and row groups.
Shuffle less: broadcast small sides, aggregate before joining, and avoid wide transformations you do not need.
Fix skew: AQE skew-join splitting, or salting hot keys by hand; check the stage's task-time distribution in the Spark UI.
Right-size partitions (roughly 100–200 MB each) so tasks neither spill nor drown the scheduler in overhead.

Reading path

What to read for the application level

2
Storage engines
Application
Designing Data-Intensive Applications (2nd ed.)Database Internals
You can now explain: B-tree vs LSM-tree, and the read, write, and space amplification each one trades.
3
SQL, basics to high performance
Application
Learning SQL (3rd ed.)PostgreSQL Query Optimization High Performance MySQL (4th ed.)The Data Warehouse Toolkit (3rd ed.)SQL Antipatterns, Volume 1
You can now explain: Execution plans, index choice, join algorithms, and dimensional modeling.
4
Spark, basics to high performance
Application
Learning Spark (2nd ed.)Spark: The Definitive Guide High Performance Spark (2nd ed.)
You can now explain: Shuffles, join strategy selection, adaptive query execution, and Tungsten.

Every engine picks a corner of the same triangle

What to read for the application level

Storage engines

SQL, basics to high performance

Spark, basics to high performance