A storage layout specifies how a table's bytes are stored on disk.
The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file
Figure: The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file
The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file. Both layouts live on disk, shown by green frames. The rating column is the highlight, shown in violet: a query for AVG(rating) reads only that one file in columnar, but every row page in row-oriented. Color key: green is the on-disk file layouts, violet is the focal rating column.
Listens, the logical table your query sees: 5 rows.
user_id
song_id
rating
listen_time
42
100
5
10:32
7
200
4
10:35
13
100
3
10:40
42
300
5
10:42
7
100
5
10:45
Row-oriented file on disk, page 1 of 2: each page packs whole rows together, so a query that wants one column still drags every other column along. Each row is written as user_id, song_id, rating, listen_time.
Page 1
[ 42 · 100 · 5 · 10:32 ]
[ 7 · 200 · 4 · 10:35 ]
[ 13 · 100 · 3 · 10:40 ]
Row-oriented file on disk, page 2 of 2: the remaining 2 rows.
Page 2
[ 42 · 300 · 5 · 10:42 ]
[ 7 · 100 · 5 · 10:45 ]
Columnar files on disk: each column gets its own file, so an AVG over rating reads only the rating file. The same 5 rows, read down each column.
user_id
song_id
rating
listen_time
42
100
5
10:32
7
200
4
10:35
13
100
3
10:40
42
300
5
10:42
7
100
5
10:45
The physical layout decides which bytes a query reads. The same logical Listens table appears in both layouts. Row-oriented storage packs whole rows into a page, so reading row 5 returns all four columns in one read and a write is one append. Columnar storage gives each column its own file, so AVG(rating) touches only the rating file and skips the other three. Which layout wins depends on the query: SELECT AVG(rating) favors columnar (row layout wastes about 75% of the I/O on this 4-column toy, far more on wide tables), while SELECT * WHERE listen_id = 42 and inserts or updates favor row, since one record is one packed page rather than a seek-and-reassemble across four files.
Case Study 3.1: BigQuery, From Web Crawl to Petabyte Analytics
BigQuery scales to trillions of rows by storing data in a columnar format and decoupling storage from compute.
Read 4-byte ratings, skip 5 MB songs
Figure: BigQuery: columnar storage scanned by thousands of on-demand workers on a tree
Illustrative rows contain rating (4 bytes), genre (a 4-byte dictionary code), artwork (1 MB), and song audio (5 MB). The query reads rating and genre and skips both media payloads. Thin green bars mark on-disk columns. Workers scan the selected columns and aggregate results up a tree.
Each row in this illustrative table has a 4-byte rating, a 4-byte genre dictionary code, 1 MB of artwork, and 5 MB of song audio. The query reads the two small columns and skips the media. Workers scan those columns in parallel and combine partial results. Thin green bars identify on-disk columns.
The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file
Figure: The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file
The same logical Listens table stored two ways on disk: row-oriented packs whole rows together into pages; columnar puts each column in its own file. Both layouts live on disk, shown by green frames. The rating column is the highlight, shown in violet: a query for AVG(rating) reads only that one file in columnar, but every row page in row-oriented. Color key: green is the on-disk file layouts, violet is the focal rating column.
Listens, the logical table your query sees: 5 rows.
user_id
song_id
rating
listen_time
42
100
5
10:32
7
200
4
10:35
13
100
3
10:40
42
300
5
10:42
7
100
5
10:45
Row-oriented file on disk, page 1 of 2: each page packs whole rows together, so a query that wants one column still drags every other column along. Each row is written as user_id, song_id, rating, listen_time.
Page 1
[ 42 · 100 · 5 · 10:32 ]
[ 7 · 200 · 4 · 10:35 ]
[ 13 · 100 · 3 · 10:40 ]
Row-oriented file on disk, page 2 of 2: the remaining 2 rows.
Page 2
[ 42 · 300 · 5 · 10:42 ]
[ 7 · 100 · 5 · 10:45 ]
Columnar files on disk: each column gets its own file, so an AVG over rating reads only the rating file. The same 5 rows, read down each column.
user_id
song_id
rating
listen_time
42
100
5
10:32
7
200
4
10:35
13
100
3
10:40
42
300
5
10:42
7
100
5
10:45
The physical layout decides which bytes a query reads. The same logical Listens table appears in both layouts. Row-oriented storage packs whole rows into a page, so reading row 5 returns all four columns in one read and a write is one append. Columnar storage gives each column its own file, so AVG(rating) touches only the rating file and skips the other three. Which layout wins depends on the query: SELECT AVG(rating) favors columnar (row layout wastes about 75% of the I/O on this 4-column toy, far more on wide tables), while SELECT * WHERE listen_id = 42 and inserts or updates favor row, since one record is one packed page rather than a seek-and-reassemble across four files.
Slotted page layout: a single 64MB row-oriented page
Figure: Slotted page layout: a single 64MB row-oriented page
Slotted page layout: a single 64MB row-oriented page on disk. Data records grow from the top down (Row A, B, C). The slot array grows from the bottom up; three slot cells (S0, S1, S2) point to their rows by label. Free space sits in the middle and shrinks as both grow toward each other. Color key: green is the page on disk (persistent); the rows and slots inside are neutral.
A 64 MB slotted page stores variable-length records from the top downward and a fixed-size slot array from the bottom upward. Free space remains between them. Each slot stores an (offset, length) pointer, so S0 points to Row A and S1 to Row B. An in-place update writes the row without moving it when the row keeps the same size. When a row grows, the DB moves the row to a new location inside the page and updates the slot, so references like page_id, slot_id remain stable.
Parquet nests rows into row-groups, columns into column chunks, and bytes into ~1 MB pages, all in one file, for a sliver of compression in exchange for big gains in row access, file count, and write simplicity
Figure: Parquet nests rows into row-groups, columns into column chunks, and bytes into ~1 MB pages, all in one file, for a sliver of compression in exchange for big gains in row access, file count, and write simplicity
Two layouts compared, revealed in steps. On the left, pure columnar (grey, out of focus) puts each column in its own file, so one row needs a seek per column and 1,000 columns require 1,000 files. On the right, one Parquet file (emerald, in focus) builds up in three beats: first the file as a sequence of row-groups of about 128 MB and a million rows, then the column chunks inside one row-group with the rating chunk highlighted, then a zoom showing a column chunk is a stack of roughly 1 MB pages. A note flags that Parquet's page is finer than the 64 MB DbFile page from earlier. A footer of per-row-group min/max statistics lets a query skip whole row-groups. The trade panel states the cost in amber and the gains in emerald. Color key: emerald is the Parquet file in focus, grey is pure columnar out of focus, amber is the cost.
Parquet stores columnar data inside row-groups in one file. A pure columnar layout stores one file per column, so reading one row performs a seek per column and 1,000 columns produce 1,000 files. Parquet keeps per-column compression and scan behavior. A row stays within one row-group, and row-groups support writes and parallel scans. The footer stores per-row-group min/max statistics, and predicates can skip groups without reading their column chunks. Encodings stop at row-group boundaries, which reduces compression slightly.
Hybrid storage keeps row-oriented and column-oriented layouts in the same table.
Hybrid storage: row on write, columnar on read, split by data age
Figure: Hybrid storage: row on write, columnar on read, split by data age
A time axis runs from newest, hot data on the left to oldest,
cold data on the right. On the left, fresh listens land as small grey
row-shaped parts that take inserts at about a million per second. A grey
background-merge arrow in the middle converts aged parts into the large green
columnar segments on the right, which answer analytics scans in about 100 ms
with roughly ten to one compression. A neutral unified-query panel spans
the bottom: one SQL surface reads both layouts and merges the results. Color
key: green is the columnar storage; grey is
the row parts and the scaffolding.
listen_time provides a partitioning dimension. The system writes fresh listens into small row-shaped parts (grey) to accept inserts at about 1M/sec by writing each row contiguously. A background merge rewrites older parts into columnar segments (green) after activity slows. Analytics scan one column and skip others at roughly 10:1 compression. One query engine reads both layouts through the same SQL surface.
Hash partitioning splits a too-big-for-RAM table into N partitions by hashing a key.
Hash partitioning through a fixed RAM buffer
Figure: Hash partitioning through a fixed RAM buffer
Hash partitioning shown as DISK input on the left, a small fixed RAM buffer in the middle, and DISK partitions on the right. The disk columns are visibly large; RAM is intentionally small to convey that the input file does not fit in RAM. The source file is read one page at a time into a flat one-page input buffer on the left of RAM. A hash function routes each row to output buffers B0, B1, and B2 on the right. Buffers show all six complete rows after processing input pages P1 through P3, before any flush. Each output buffer points horizontally to its final disk partition, shown after the full scan. When a buffer fills, it flushes to its partition file on disk. Color key: red is RAM (volatile and limited), green is disk (persistent), grey is out of focus.
Hash partitioning makes one pass over a too-big-for-RAM file using a small, fixed RAM buffer: one input slot plus one output buffer per partition. A page streams into the input slot, each row hashes by h(user_id) % B and routes to one of ~B output buffers. The instant any buffer fills, it flushes to its partition file on disk and is cleared, so RAM never holds more than that fixed set of buffers no matter how large the input. Partitions are stored on disk, not in memory: the full partitions live on disk, while only the small fixed RAM buffer is resident at any point in time. Rows with the same key always land in the same partition, so later stages can sort, join, or group one partition at a time. See the IO Cost Summary for the cost breakdown.
BigSort (or external merge-sort) sorts a table larger than RAM by reading RAM-sized chunks, sorting each chunk in memory, writing each sorted chunk to disk, then merging the sorted chunks.
External merge sort as a memory model
Figure: External merge sort as a memory model
Pages stream from disk through a small four-page RAM box and back. Phase one reads four pages into RAM, quicksorts them, and writes a sorted run; repeat to get several runs. Phase two reads the head page of each run into RAM and emits the smallest value over and over, merging the runs into one sorted file. Each tile is a page shaded by its sort key, light for small and dark for large, so a sorted run reads as a smooth light-to-dark gradient. Color key: the green box is disk (persistent), the red box is RAM (volatile), the neutral tiles are pages shaded by sort key.
Phase 1 reads four pages into memory, quicksorts them in place, and writes the pages back as one sorted run, repeating until the file becomes a set of sorted runs. Phase 2 keeps the head page of each run in memory, repeatedly selects the smallest remaining value, and writes it to the output to merge the runs into one sorted file. Each tile is a page shaded by its sort key, light for small and dark for large.
Block nested loop join loads a block of the outer table into RAM, scans the inner table once per block, and applies the join predicate to candidate row pairs.
Block Nested Loop Join: disk inputs, RAM buffers, comparison, and joined output
Figure: Block Nested Loop Join: disk inputs, RAM buffers, comparison, and joined output
In this example R fits in RAM. Load R once into a retained block. Stream S one page at a time into a one-page input buffer. Compare every row in that page with the R block, then emit matching joined rows. Repeat for all four S pages to produce eight rows. Green marks persistent disk; red marks RAM.
Block Nested Loop Join, R ⋈ S. Read the smaller table R from disk and hold it in RAM for the whole join. The larger table S streams past in 4 pages, each loaded into a one-page slot, probed against R, then discarded, producing 8 joined rows (2 per S page here). Best case, when R fits in B pages, is P(R) + P(S) + OUT; if R is bigger than B it becomes P(R) + ⌈P(R)/B⌉ × P(S) + OUT, because S is re-scanned once per R-block. Always make the smaller table the outer one.
Hash partition join joins two tables that do not fit in RAM.
Hash Partition Join: in Phase 1 both R and S are hashed on the join key into matching partitions on disk; in Phase 2 each partition pair is joined in RAM
Figure: Hash Partition Join: in Phase 1 both R and S are hashed on the join key into matching partitions on disk; in Phase 2 each partition pair is joined in RAM
Hash Partition Join. Phase 1: both R and S are read from disk and hashed on the join key into matching partitions written back to disk, so the same key always lands in the same partition number. Phase 2: each partition pair is loaded into RAM and joined there. Color key: green is the tables and partitions on disk (persistent), red is the per-partition join in RAM (volatile); partitions are identified by their h to 0, 1, 2 labels.
R (Users) on disk, 4 rows, one input to phase 1.
user_id
name
7
Mickey
13
Minnie
42
Pluto
99
Daffy
S (Listens) on disk, 8 rows, the other input to phase 1.
user_id
song_id
42
100
7
200
13
100
42
300
7
100
13
200
42
400
99
500
Phase 1 writes R's rows to disk in three partitions by h(user_id), so a user_id always lands in the same partition number. R partition 0 holds 2 rows, each written user_id then name.
R₀ · disk (h → 0)
42 · Pluto
99 · Daffy
R partition 1, 1 row.
R₁ · disk (h → 1)
7 · Mickey
R partition 2, 1 row.
R₂ · disk (h → 2)
13 · Minnie
Phase 1 hashes S with the same h, so matching keys meet in the same partition pair. S partition 0, 4 rows, each written user_id then song_id.
S₀ · disk (h → 0)
42 · 100
42 · 300
42 · 400
99 · 500
S partition 1, 2 rows.
S₁ · disk (h → 1)
7 · 200
7 · 100
S partition 2, 2 rows.
S₂ · disk (h → 2)
13 · 100
13 · 200
Phase 2 loads each partition pair into RAM and joins it there, so no row is ever compared against a partition it cannot match. Read each column down: the pair, how it is joined, how many rows it outputs, and which keys matched. The three partitions together output 8 rows, one per S row.
R₀ ⋈ S₀ · in RAM
R₁ ⋈ S₁ · in RAM
R₂ ⋈ S₂ · in RAM
build hash on R₀, probe with S₀
build hash on R₁, probe with S₁
build hash on R₂, probe with S₂
→ 4 output rows
→ 2 output rows
→ 2 output rows
user_id 42 → 3 matches · user_id 99 → 1 match
user_id 7 → 2 matches
user_id 13 → 2 matches
Hash Partition Join, R ⋈ S on user_id. Phase 1 hashes both tables with the same function so matching user_ids always land in the same partition number. Phase 2 joins each (Rᵢ, Sᵢ) pair independently in RAM, building a hash table on R and probing with S, three parallelizable joins that yield 4 + 2 + 2 = 8 rows. Best-case cost is 3(N+M) + OUT (read each table, write partitions, read them back, write the output). The worst case is hash skew, where a hot key overflows a partition past RAM and recursive re-partitioning or a sort-merge fallback adds another pass.
Sort-merge join sorts both tables on the join key, then scans them in lockstep and emits matching rows for equal keys.
Sort-Merge Join: after Phase 1 BigSort, both R and S are sorted on disk on the join key
Figure: Sort-Merge Join: after Phase 1 BigSort, both R and S are sorted on disk on the join key
Sort-Merge Join: after Phase 1 BigSort, both R and S are sorted on the join key and live on disk. Phase 2 walks both tables in one pass with two pointers in RAM, emitting matched groups as it goes. The dashed match lines connect each key's R row to its matching S rows: key 7 yields 2 outputs, key 13 yields 2, key 42 yields 3, key 99 yields 1. Total 8 output rows. Color key: green is the sorted tables on disk (persistent), red is the two-pointer merge in RAM (volatile).
Sort-Merge Join, R ⋈ S on user_id (Phase 2 shown). Phase 1 (not shown) BigSorts both R and S on the join key (see the big sort page). Phase 2 scans the two sorted runs with two pointers. Equal keys form a matching key group, and the operator emits every pair in the group. Unequal keys advance the smaller side. The example advances through user_id 7 → 2, 13 → 2, 42 → 3, 99 → 1, total 8 rows. A key that appears on only one side emits nothing under inner join semantics. A key with m matches on one side and n on the other emits the m × n cross-product for that key. The output stream stays sorted on the join key, so a downstream operator that requires that order does not add a sort. Best case is P(R) + P(S) + OUT for one linear scan per run, plus the two Phase-1 BigSort costs. Worst case is O(P(R) × P(S)) + OUT when one key dominates and the merge performs a per-key cross-product. OUT can dominate when match rates are high.
The IO cost of every algorithm in this module (BigSort, HashPartition, BNLJ, SMJ, HPJ) is a function of table size, buffer size, and the read/write cost ratio.
Figure: Join IO cost versus buffer size, log scale
A log-scale line chart of IO cost against buffer size B for
the same join, Songs3 100 GB by Listens3 1 TB, at C_r = C_w = 1. Buffer grows
left to right: 10, 100, 1000, 10000 pages. BNLJ, the solid ink line, starts
highest at 2.6M IOs and drops steeply to 18K as the buffer grows. SMJ-best,
the dashed line, falls gently from 159K to 54K. HPJ-best, the dotted line, is
flat at about 54K. A green crossover divider marks where the cheapest
algorithm switches: HPJ is cheapest at small buffers, BNLJ at large buffers.
Numbers are verified from the Module 3 NanoDB colab. Color key: green is the
crossover and the winning regions; ink and grey are the cost lines
and axes.
HPJ-best stays near 54K because partitioning does one read and one write independent of B. BNLJ drops from 2.6M to 18K because larger B reduces rescans of the inner table. SMJ-best drops as larger initial runs reduce merge passes. The crossover marks the point where BNLJ becomes cheaper than HPJ at this scale. SMJ with many duplicates can rescan during merge. HPJ with heavy skew can create oversized partitions, each up to 2 to 10x worse.
An index maps a search key, such as artist, to the data pages containing matching rows.
Index finds topics quickly
Figure: Index finds topics quickly
A Python programming book has a Quicksort section on page 201 in its sorting chapter. The separate alphabetical index lists Binary search, Functions, Loops, Quicksort, and Variables. Quicksort points to pages 201 and 208; the arrow leads to page 201. The chapters remain in teaching order.
A Python programming book organizes its chapters for teaching, not alphabetically by topic. Its back-of-book index sorts topics: “Quicksort” points to pages 201 and 208.
A dictionary page 128 contains dragon, draw, and dream. A small range index maps door–dozen to page 127, dragon–dream to page 128, and dress–dry to page 129. Since the words are sorted, the index need not list every word. This is an Oxford English Dictionary analogy, not a reproduction of its index.
Think of the Oxford English Dictionary: its words are already alphabetical. An index can store each page’s word range rather than every word. To find “draw,” choose the dragon to dream range, then search page 128.
Table size vs index size: on the left the Songs table is a 10 TB file of 160,000 pages storing whole rows. On the right the artist index is a 20 MB file of one page storing only (artist, page#) pointers. Size bars beneath show 10 TB vs 20 MB at the same horizontal scale. Both the table and the index live on disk and are shown green; the size difference is carried by the bar widths, not by colour. Color key: green is on-disk storage; the 10 TB table bar versus the 20 MB index sliver shows the roughly 500,000x size difference.
The Songs table stores 10 MB rows (10 TB, 160,000 pages). The artist index stores 20-byte pointers (20 MB, one page), 500,000 times smaller. WHERE artist = 'Beatles' without an index scans 160,000 pages. With an index, the database reads one index page, learns Beatles is on page 47, then reads page 47. The query uses two IOs instead of 160,000, 80,000 times fewer for the same answer.
A hash index computes hash(key) and uses it to choose the page that stores the key's index entry.
hash(key) → index page → entry → data pages
Figure: hash(key) → index page → entry → data pages
A lookup for Dan computes hash(Dan) = 1 in this example, selecting index page 1. The Dan entry points to data pages 0, 1, and 4, which hold the matching rows. The violet path follows this lookup; green marks index and data pages on disk.
A hash index on People.name stores (search_key, page#) entries in buckets chosen by hash(value). Here, hash(Dan) = 1 selects index page 1. Its Dan entry points to data pages 0, 1, and 4. The lookup requires 4 IOs: one index-page read and three data-page reads.
A B+Tree index stores keys in sorted order in a balanced tree.
Build a hierarchy over sorted leaves
Figure: Build a hierarchy over sorted leaves
B+Tree layout on Songs.catalog_no. Data pages on the left hold the rows. The tree on the right has a root node, three internal nodes, and a row of leaf nodes. Leaves store (key, data-page pointer) pairs in sorted order; neighbouring leaves are linked left-to-right so a range scan can walk across them without returning to the root. Color key: green is the index and data pages on disk (persistent), violet is the lookup trace for key 12890.
Data pages on disk store the Songs rows. The B+Tree on disk stores a root and internal nodes that route lookups to sorted leaves. Leaves store (key, data-page pointer) pairs and link left-to-right. For catalog_no = 12890 ("As It Was"), the root selects 5000..14999, the internal node selects 11234..13788, the leaf resolves 12890 → Page 3, and Page 3 contains the row. With no pages cached, the lookup reads three index pages and one data page: four IOs.
Walking a range query SELECT * WHERE catalog_no BETWEEN 12000 AND 14000 in a B+Tree. Step 1 visits the root. Step 2 descends to the middle internal node (the other two internals are skipped). Step 3 walks from leaf 3 to leaf 4 sequentially, loading data pages 3 and 4. Stop at 14001 in leaf 4. Total 6 IOs versus 160,000 for a full scan. Color key: green is the index and data pages on disk (persistent), violet arrows show the lookup path, grey dashed is skipped or not visited.
For 12000 ≤ catalog_no ≤ 14000, matching rows occupy data pages 3 and 4. The descent runs root → middle internal → Leaf 3, then follows leaf links. Leaf 3 yields 12890 and 13456. Leaf 4 yields 13789 and 13980. The next key in Leaf 4 is 14001, which exceeds 14000, so the scan stops without reading another leaf. The query reads 4 index pages and 2 data pages, 6 IOs total, versus roughly 160,000 for a full scan, about 27,000× fewer IOs.
An SSTable is an immutable file of key-value pairs sorted by key.
An SSTable is a sorted, immutable file
Figure: An SSTable is a sorted, immutable file
One immutable SSTable contains a Bloom filter, a sparse index, and sorted data blocks. In the dictionary analogy, a Bloom filter first checks whether a word may exist; an absent result skips the file. The sparse index maps the first word of each sorted page to that page: door to page 201, dragon to page 202, and dress to page 203. To find draw, choose the dragon entry and read page 202. Page numbers illustrate block offsets; the dictionary example is schematic. Multiple SSTable files can coexist on disk.
An SSTable is one immutable on-disk file with three sections: a Bloom filter cached in RAM for fast not-exists checks, a sparse index block that binary-searches to the target data block, and sorted, compressed data blocks. Think of an Oxford English Dictionary: the sparse index records the first word on each page, while the pages contain sorted words and their definitions. To find draw, follow the dragon → Page 202 entry. These illustrative page numbers stand for data-block offsets in an SSTable. Multiple SSTables can coexist, each with its own index and sorted data.
An LSM tree buffers inserts in a RAM MemTable, flushes them to immutable SSTables, and merges SSTables in the background.
Buffer writes, flush files, then compact
Figure: Buffer writes, flush files, then compact
LSM write path at 1:44 PM. Top lane: incoming plays land in the live MemTable in RAM. Middle lane: every 15 minutes the MemTable is flushed as a Level-0 SSTable on disk; the 1:01, 1:15, and 1:30 files are already there. Bottom lane: every hour compaction merges Level-0 files into one larger Level-1+ SSTable. Song S75 has +2 plays in the MemTable, +18 across the Level-0 flushes, and 5420 in the compacted history. Color key: red strip is the MemTable in RAM (volatile), green strip is SSTables on disk (persistent).
LSM write path at 1:44 PM, RAM on top and disk below, time flowing downward. Incoming plays land in the in-RAM MemTable (fast, no seek, lost on crash unless replayed from the WAL). Every 15 minutes the engine flushes it to an immutable Level-0 SSTable on disk (1:01pm.sst, 1:15pm.sst, 1:30pm.sst). Hourly compaction merges those into one larger sorted, de-duplicated Level-1+ file. Total plays for S75 spread across tiers (+2 in the MemTable, +10, no matching entry, and +8 in Level-0, 5,420 in compacted history) and the read path sums them to 5,440 (merge-on-read). The merge operator is configurable: "add" for counters, "newest wins" for last-write-wins keys, "set union" for tags, "max" for high-water-marks. The merge section walks through more examples.
Read S75 from the MemTable and SSTables. MemTable contributes 2; 1:30pm.sst contributes 10; 1:15pm.sst has no matching entry; 1:01pm.sst contributes 8; before1:00pm.sst contributes 5420. Sum: 5440. Red and green top rules indicate RAM and disk.
Merge-on-read computes S75's play count at read time instead of storing it, by summing every tier that holds a fragment. The live in-RAM MemTable (red) adds +2, the three flushed Level-0 SSTables on disk (green) add 10 + 0 + 8 = 18, and the compacted Level-1+ SSTable on disk (green) adds +5,420, for a total of 2 + 18 + 5,420 = 5,440 (the merge function is "add" because plays are a counter). Each SSTable carries a bloom filter, so the reader skips any tier that cannot hold the key with no disk read, making most reads far cheaper than this worst case.
Case Study 3.3: How LSM trees handle Spotify-scale activity
This example uses an LSM tree to batch writes for play counters, playback positions, and friend activity.
Three workloads share the same write path
Figure: Three workloads share the same write path
Illustrative Spotify-style architecture. Play increments, timestamped playback positions, and listening events enter a compact RAM MemTable. Flushes produce sorted SSTables, and compaction merges them using the workload's rule. Thin red bars mark RAM and green bars mark disk. The next slide contrasts sum, newest timestamp, and merging events in time order.
In this example, a play writes a counter increment, a pause writes a timestamped position, and a listen appends an activity event. The shared write path buffers records in RAM, flushes sorted SSTables, and compacts them using the appropriate merge rule. The key prefixes distinguish the three example workloads.
Case Study 3.2: How an inverted index supports Spotify search
This example architecture supports text search across 100 million tracks with an inverted index, which maps each search term to the song_ids that contain it.
Map each word to its matching songs
Figure: Map each word to its matching songs
Search for songs containing both Crazy and Heart. Two sorted term-index leaf pages contain multiple term rows. Crazy and Heart point to sorted postings lists. Intersect the song IDs in RAM to obtain 12 and 108, then fetch their song records from data pages. Routing nodes above the term pages are omitted. Data pages are schematic.
Each term-index page holds several sorted terms; each term points to a postings list of song IDs. For Crazy AND Heart, intersect the two lists in RAM to get {12, 108}, then fetch those songs from the data pages. The postings store IDs; the data pages store rows. The B+Tree routing nodes above the term pages are omitted.
A Python programming book has a Quicksort section on page 201 in its sorting chapter. The separate alphabetical index lists Binary search, Functions, Loops, Quicksort, and Variables. Quicksort points to pages 201 and 208; the arrow leads to page 201. The chapters remain in teaching order.
A Python programming book organizes its chapters for teaching, not alphabetically by topic. Its back-of-book index sorts topics: “Quicksort” points to pages 201 and 208.
A dictionary page 128 contains dragon, draw, and dream. A small range index maps door–dozen to page 127, dragon–dream to page 128, and dress–dry to page 129. Since the words are sorted, the index need not list every word. This is an Oxford English Dictionary analogy, not a reproduction of its index.
Think of the Oxford English Dictionary: its words are already alphabetical. An index can store each page’s word range rather than every word. To find “draw,” choose the dragon to dream range, then search page 128.
Figure: Clustering puts one user’s listens together
Find all listens for user 7. The same eight rows occupy four pages in either layout, with two rows per page. Arrival order scatters user 7 across four pages. Clustering by user_id and listen_time groups the four matching rows into two pages. Counts exclude index lookup cost. Thin green markers identify matching rows.
Find all listens for user_id = 7. Both layouts contain the same eight rows, two per page; the figure shows user_id and song_id. In arrival order, user 7’s four listens occupy four pages. Clustering by (user_id, listen_time) groups them onto two neighboring pages, in time order. That is four versus two data-page reads, excluding index lookup cost. The index finds the rows; clustering puts them on fewer pages.
Case Study 3.4: How Spotify Wrapped serves a launch-day spike
Spotify Wrapped computes each user's yearly summary before launch and stores the result by user, so the launch-day spike serves precomputed records.
Precompute summaries, then look them up
Figure: Precompute summaries, then look them up
Chronological storage scatters one user's listens across the disk and requires one thousand random reads in this example. Clustering the Listens table by user_id and listen_time groups that user's plays on neighboring pages. Before launch, the batch job reads them sequentially and writes one Wrapped summary row per user. On December 1, this example fetches the card with one hash-index lookup on user_id.
The design clusters Listens by (user_id, listen_time), so a batch job reads each user's year sequentially and writes one summary row per user. On December 1, the card fetch uses one hash-index lookup on user_id.
How Three Changes Cut One Query from $550,000 to $400
A company runs one weekly aggregation 100 times a day against a 1 TB table.
Weekly trending genres: October 21-27
SELECT s.genre,
COUNT(*) ASlistens,
COUNT(DISTINCT l.user_id) AS listeners,
AVG(l.rating) AS avg_rating
FROMListensAS l
JOINSongsAS s ON s.song_id = l.song_id
WHERE l.listen_time >='2026-10-21'AND l.listen_time < '2026-10-28'GROUP BY s.genre
ORDER BYlistens DESC;
The same weekly aggregation in four stages, left to right. A Hash Partition Join scans the full 1 TB at 49,200 IOs and about $550,000 a year. A B+Tree index cuts the query to about 554 IOs, columnar storage cuts it to about 60 IOs, and compression cuts it to about 35 IOs. The endpoint ratio gives roughly 1,400 times fewer IOs and about $400 a year. Color key: red marks the costly baseline, green marks the optimized result, and grey marks intermediate steps and structure.
Four stages of the same weekly aggregation. The Hash Partition Join costs 49,200 IOs. A B+Tree index cuts the query to about 554 IOs, columnar storage cuts it to about 60, and compression cuts it to about 35. The endpoint ratio gives roughly 1,400× fewer IOs and lowers annual cost from about $550,000 to about $400.
The optimizer estimates the cost of alternative plans and chooses the cheapest.
Choose a cheaper plan for the same answer
Figure: Choose a cheaper plan for the same answer
One left-to-right pipeline of five stages. Stage 1: SQL is
declarative, it states the result, not the procedure. Stage 2: parse and
bind turn the text into a validated tree, resolving names and types against
the catalog. Stage 3: the logical plan applies equivalence-preserving
relational-algebra rewrites (predicate pushdown, projection pruning,
subquery flattening); this defines the result, every rewrite returns the
same rows. Stage 4, the focal stage: the physical-plan search picks a join
order, join algorithm, and access path, using dynamic programming that
computes the best sub-plan for each subset of tables once and reuses it, so
it never enumerates all n factorial orders, and costs each from table
statistics; this is where speed is decided. Stage 5: the chosen operator
tree executes, routinely about 100 times faster than the naive ordering.
Because the logical plan and every plan the search considers are
result-equivalent, only speed varies, never the answer. Color key: mint is
the physical-plan cost search where speed is decided; grey is the
parse, rewrite, and execute scaffolding.
Preserve the query’s result; choose how to compute it using estimated costs.
-- Count recommendation-listen matches for each song.SELECT r.song_id, COUNT(r.recommendation_id) AS recommendation_count
FROM Recommendations AS r
-- Goal 1: match the same user and song.JOINListensAS l ON r.user_id = l.user_id AND r.song_id = l.song_id
-- Goal 2: count matching pairs per song.GROUP BY r.song_id
-- Goal 3: show the largest counts first.ORDER BYCOUNT(r.recommendation_id) DESC;
Read, join, group, and sort the recommendation query. Choose alternatives for each operation; partitioning and sorting support operators when needed.
For the recommendation query, choose access methods, a join, an aggregation method, and a final sort by count. Partition or sort only where an operator needs it. Compare the complete plans using estimated rows, pages, memory, and existing order.
EXPLAIN shows PostgreSQL’s chosen plan and estimated costs.
What PostgreSQL actually chose
Figure: What PostgreSQL actually chose
Actual PostgreSQL 17.9 EXPLAIN for the recommendation query. Scans, Hash Join, HashAggregate, Sort. Local Colab schema and data with four added recommendation rows; ANALYZE before planning.
Actual PostgreSQL 17.9 output, using the Query Plans Colab’s schema and nine listens plus four added sample recommendations. The original Colab leaves Recommendations empty. After ANALYZE, PostgreSQL chose Hash Join, HashAggregate, and Sort. The groups fit in RAM, so this plan avoids the extra repartition in the hand-worked Plan 2. These tiny-data costs are not predictions for large tables.
Sample: inspect a sample of the table (example: 1% of its rows).
Summarize: keep row and page counts, distinct-value counts, common-value frequencies, and histograms of value ranges.
Store and use: save these compact summaries in the database’s system catalog, organized by table and column. The optimizer uses them to estimate output rows and compare plan costs.
Example: for WHERE user_id BETWEEN 1 AND 100, suppose the statistics estimate that 1% of rows match. That is the selectivity. With 1 million input rows, the estimated output cardinality is 1,000,000 × 1% = 10,000 rows.
Partition the data, run local operators, and shuffle rows when matching keys must meet.
Send matching keys to the same machine
Figure: Send matching keys to the same machine
Distributed shuffle: rows starting on multiple nodes are hashed on the join key and sent over the network so all rows with the same key land on the same target node, ready for local join. This is data movement across machines, not a disk or RAM story. Color key: mint follows one key (user_id 42) from every source node, over the network, onto its single colocated node; grey is the other keys and the node structure.
Rows begin scattered across multiple nodes. Hashing each row on the join key picks its target machine, so every row sharing a key travels over the network to the same node. Once the keys sit together, each node runs an ordinary local join on the rows it now owns. This is exactly hash partitioning with the network as the destination, so the cost is the same 2N IO plus the network transfer.
Follow a play event through writes, batch processing, and analytics.
One click connects OLTP, ETL, and OLAP
Figure: One click connects OLTP, ETL, and OLAP
Spotify end-to-end architecture: one click triggers three systems. Act 1 OLTP (LSM tree write), Act 2 ETL (Spark hash partition, BigSort, broadcast join, columnar write), Act 3 OLAP (star schema query with broadcast and columnar scan). All three are persistent storage systems on disk. Color key: mint marks the durable on-disk storage system at each act; red marks the volatile RAM MemTable on the OLTP hot path before it persists to disk.
LSM writes feed a batch pipeline that produces columnar data for analytics.
Words and IDs can be indexed directly. Embeddings can be full keys for exact matches or mapped to LSH codes for similarity candidates. Locations can be mapped to spatial codes. Hash indexes support equality; B+ trees also support ordered key ranges.
How do you find 20 album covers similar to this one?
Given a cover or cover ID, find 20 similar images among 10 million covers. Their embeddings are indexed using LSH. Approximate results are acceptable.
Consider:
A Hash index
B B+ tree
C LSH
D LSM tree
E Bloom filter
Hint
Use LSH for candidates, then score them. What belongs in each bucket?
One possible design
Key/value:LSH_code → cover IDs, within each LSH table.
How it works:get the cover’s embedding, compute its LSH codes, and probe matching buckets. Deduplicate candidates, score by cosine similarity, and return the closest 20 candidates.
Tradeoff:the true closest matches may be missed. Probing more buckets improves coverage but adds work.
