Branch: CS Foundations (quant-cs) · Node CS2.04 · ~16 focused hours · Gate: Quiz ≥ 85% + structured code-pack ≥ 85%

You already know how to write a SELECT that joins three tables and aggregates a million rows (CS2.03). You have almost certainly also had the experience of that exact same kind of query running fine in January and crawling in July (same syntax, same shape, ten times slower) and reaching for the only lever you knew how to pull: a bigger machine, more RAM, "let it run overnight." That instinct is not stupid, but it is aimed at the wrong target, because it treats the slowdown as a mystery instead of a mechanism. It is not a mystery. Every database, every file format, every cache, and every operating system is making a small number of very ordinary trade-offs about where bytes physically live and how far they have to travel to reach the CPU, and once you can see those trade-offs explicitly, "why did this suddenly get slow" stops being a shrug and becomes a diagnosis.

Here is the whole module compressed into one sentence you will spend sixteen hours earning the right to believe: a computer system's speed is overwhelmingly a story about distance, not cleverness. A CPU register is nanoseconds away from the core doing the work; main memory (RAM) is roughly a hundred times farther; a solid-state disk is roughly a thousand times farther again; a spinning disk or a network hop is farther still. Every technique this module teaches (caching, paging, indexing, columnar storage, compression, the shape of a small analyst data warehouse) is a different answer to the same one question: given that some data lives close and most data lives far, how do we arrange things so the CPU touches the close stuff as often as possible and the far stuff as rarely as possible? CS2.03 taught you to ask a database for the right rows. This module teaches you to understand what happens physically once you ask.

One promise for the hours ahead: by the end, you will be able to look at a query that used to run in two seconds and now takes two minutes, and (before you touch a single knob) name the two or three most likely mechanical causes (a cache that stopped fitting, a full scan where an index used to apply, a column store doing a job a row store now has to do ten times slower), and know which cheap experiment would confirm which one. That diagnostic reflex, more than any single fact in this module, is what "systems and data-intensive thinking" means for a working analyst.

Every exercise in this module lives in its code pack, code-packs/CS2.04.json (module id CS2.04, eight exercises CS2.04-e01 through CS2.04-e08), reachable from this node's Code tab. Every one of the eight ships a structured fill-in-the-blank fallback as its definition of record, so the pack is 100% completable even with zero runtime, live execution in the browser is a bonus, never a requirement to pass the gate.

Learning objectives

By the end you can:

Explain the memory hierarchy (registers → L1/L2/L3 cache → RAM → SSD → spinning disk → network) as a ladder of distance, and use rough latency ratios to predict, before measuring, which of two designs will be faster.
Explain virtual memory and paging well enough to simulate page replacement by hand, implement the FIFO policy in code, and correctly predict and explain Belady's anomaly (more memory making performance worse, not better).
Implement an LRU (least-recently-used) cache, contrast its eviction logic with FIFO's, and reason about when a cache's assumption about access patterns matches, or mismatches: reality (cache pollution, thrashing).
Contrast row-oriented and column-oriented physical storage layouts, compute the bytes an analytic query must scan under each, and explain why Parquet and similar formats exist and what they cost you in return (write cost, mutation cost).
Explain and implement run-length encoding as a concrete instance of "compression only pays off on the right kind of data," and predict when compression helps versus when it actively hurts.
Explain why databases use B-trees, not binary trees or linear scans, for on-disk indexes; compute an index's height from its key count and fan-out; and reason about when an index helps a query and when it does not (selectivity).
Implement a small deterministic hash index and explain, from first principles, why Python's built-in hash() is the wrong tool for a persisted, cross-run index.
Sketch the shape of a small analyst data warehouse: the OLTP-vs-OLAP distinction, a star schema of fact and dimension tables, and where a batch/ETL pipeline sits between the two, and write the aggregation query that sits at the center of it.
(Productivity objective: R10 duality.) Use an AI coding assistant to accelerate writing systems-adjacent code (a cache, a query, a storage-layout experiment) after you can already explain the mechanism yourself by hand, and catch the specific ways AI-generated systems code goes subtly wrong (off-by-one eviction order, a plausible-looking index that doesn't match the query, a schema that silently drops a constraint).

The duality, stated once (R10). As in every module in this program, this node carries two objectives at once. The understanding objective (items 1–8) is what the mastery gate rewards; you earn the pass by explaining the mechanism and by clearing the code pack's hidden tests, not by having an assistant write code you cannot defend. The productivity objective (item 9) is the payoff you keep afterward: knowing how to point a copilot at systems work without being quietly misled by it. A tool can never buy you a pass on the gate.

Prerequisites & connections

Builds on. CS2.03 (Databases & SQL for Analysts) is the direct foundation, you already know how to ask a database for rows via SELECT/joins/aggregation, and you already have the vocabulary for indexing and ACID as user-facing guarantees. This module goes one level down: not "what do I type" but "what actually happens to bytes on a disk and in RAM when I hit enter." CS1.04 (Algorithmic Thinking, Recursion & Big-O) supplies the complexity vocabulary this module leans on constantly (a B-tree's height is a log; a full scan is linear; a hash lookup is amortized constant), if O(log n) versus O(n) doesn't yet feel visceral, revisit CS1.04 before this node's Practice set. CS1.02's discipline around mutability and clean function design shows up directly in the code pack (every exercise is a small, pure, testable function). You do not need calculus, statistics, or prior machine-learning exposure for this node, it is a pure systems module.

Feeds forward. CS2.05 (APIs, HTTP, JSON & Web Scraping) inherits this module's caching vocabulary directly, a rate-limited API and a buffer pool are solving structurally the same "expensive round-trip, cache what you can" problem. CS2.06 (Software Engineering) will ask you to write tests and reason about performance regressions for code whose mechanism you now understand rather than merely observe. In the DA branch, pandas's entire performance story, why vectorized column operations crush row-wise Python loops, why a wide DataFrame with one huge text column behaves differently from a narrow numeric one, is a direct, unannounced consequence of the row-vs-column reasoning built here; DA1.02/DA1.03 will assume it. In the QD branch, QD1.01's point-in-time, survivorship-controlled research panels are exactly the kind of data-intensive storage-and-retrieval problem this module is training you to reason about before you build one at scale. None of this module touches statistics, probability, or machine-learning theory, that remains QM's (G1) and DA's (this branch's DA1.05/DA2.x) territory; this node's business is purely mechanical: memory, storage, and the shape of a warehouse.

Core teaching content

The one sentence that explains almost everything

Strip away the acronyms (cache, buffer pool, index, columnar, Parquet, OLAP) and every one of them is a different tactical answer to a single strategic fact: some storage is close to the CPU and fast, most storage is far from the CPU and slow, and the amount of "close" storage is always, permanently, embarrassingly small compared to the amount of "far" storage. A modern machine might have a few hundred kilobytes of L1/L2 cache, a few tens of megabytes of L3 cache, tens of gigabytes of RAM, and terabytes of disk. Every layer down that list is bigger and slower than the layer above it, usually by one to three orders of magnitude at a time. Nothing in this module is really "about" databases or file formats; it is about that one ladder, and about the fact that a system's entire performance personality is determined by how well its access pattern matches the shape of that ladder.

The memory hierarchy: what "fast" actually means

Hold four numbers, not because they are exact (they are not, see the perishable note below) but because their ratios are the entire point. A reference to an L1 CPU cache costs on the order of 1 nanosecond. A reference to main memory (RAM) costs on the order of 100 nanoseconds, roughly a hundred times slower than L1. A random read from a solid-state drive (SSD) costs on the order of 100 microseconds (100,000 nanoseconds), again roughly a thousand times slower than RAM. A seek on a spinning hard disk (HDD) costs on the order of 10 milliseconds (10,000,000 nanoseconds), a hundred times slower again than the SSD, and ten million times slower than the L1 cache reference you started with. A round trip across a network to another datacenter can cost tens to hundreds of milliseconds, slower still, and now bounded by the speed of light, not by any hardware you can upgrade your way out of.

Perishable specifics, as of 2026-07; verify current. The ratios above are durable; the exact nanosecond figures drift with every hardware generation and are commonly circulated as illustrative "latency numbers every engineer should know" compilations (a lineage popularized inside systems engineering since roughly the early 2010s). Treat every number in this section as an order of magnitude, not a benchmark result for any specific machine, and if you ever need a precise figure for real capacity planning, measure your own hardware; do not cite this table as ground truth.

The consequence is not subtle: an algorithm that is asymptotically worse but touches memory in the order it is laid out can beat an asymptotically better algorithm that jumps around randomly, because the "worse" algorithm pays the RAM/cache price and the "better" one keeps paying the SSD or disk price. This single idea, that access pattern can matter as much as algorithm, is the thread every remaining section in this module pulls on. It is also why "just buy more RAM" is not systems thinking; more RAM changes how much fits close to the CPU, but it does nothing about an access pattern that insists on jumping randomly through the far tier anyway.

Virtual memory, paging, and why "out of memory" is a spectrum, not a wall

Every running program believes it has a huge, private, contiguous block of memory addresses. It does not, that belief, virtual memory, is a fiction the operating system maintains on the program's behalf, translating each virtual address the program uses into a real physical location, which might be in RAM or might currently be swapped out. Memory is managed in fixed-size chunks called pages (commonly 4 KB). When a program touches a virtual page that is not currently resident in physical RAM, the CPU raises a page fault, and the OS must bring that page in, from disk, if it was swapped out, or by mapping a fresh page for the first time. This is why "out of memory" is not one cliff edge: performance degrades gradually as page faults become more frequent, long before a program literally cannot allocate another byte. A workload whose working set (the pages it actively touches) fits in physical RAM runs at RAM speed; the moment that working set exceeds available RAM, the OS starts paging to disk, and the effective speed of "memory access" quietly collapses toward disk speed, a hundred-thousand-fold slowdown hiding behind an identical line of code.

Page replacement: FIFO, LRU, and Belady's anomaly

When physical RAM is full and a new page must be brought in, something resident has to be evicted, and which page you evict is a policy decision with real consequences. The simplest policy, FIFO (first-in, first-out), evicts whichever resident page has been loaded the longest, regardless of whether it was just used a moment ago. Code pack exercise CS2.04-e01 asks you to implement fifo_page_faults(refs, capacity) exactly this way: track load order, and whenever a referenced page is not resident and the frame set is full, evict the oldest-loaded page.

FIFO has a famous, genuinely counterintuitive failure mode called Belady's anomaly: giving a FIFO cache more memory can produce more page faults, not fewer. Trace the reference string 1,2,3,4,1,2,5,1,2,3,4,5 with 3 frames: faults occur at 1, 2, 3 (filling the frames), then 4 evicts 1, then 1 evicts 2, then 2 evicts 3, then 5 evicts 4, at this point 1 and 2 are both hits (they're resident), then 3 evicts 1, then 4 evicts 2, and 5 is a hit. Total: 9 faults. Now run the identical reference string with 4 frames, more memory, which should only help. It does not: the extra frame changes the eviction order just enough that later references that used to be hits become faults instead, and the total comes to 10 faults, one more fault with one more frame. This is not a contrived edge case; it is a mechanical consequence of FIFO tracking load order rather than usage, and it is exactly the kind of counterintuitive result that rewards hand-tracing over guessing. (Check both totals yourself against CS2.04-e01's harness before you trust this paragraph, that is the entire discipline this program is built on.)

LRU (least-recently-used) fixes the specific defect that causes Belady's anomaly by evicting based on access order, not load order: every hit moves a key to the "most recently used" end, so a frequently reused key is never penalized just because it happened to load early. Exercise CS2.04-e02 asks for lru_hit_rate(accesses, capacity). Compare the two policies on the short access sequence 1,2,1,3,1,4 with capacity 2: FIFO produces exactly one hit (the second 1, which arrives before its slot is stolen) out of five faults, because by the time 1 reappears later in the string it has already been evicted in load order; LRU produces two hits on the same sequence, because each time 1 is touched, LRU explicitly protects it from being the next eviction. LRU is not a universal law, though, it encodes a specific bet, that recently used implies likely to be used again (temporal locality). That bet holds for most real analyst workloads (the desk's active watch-list, this quarter's filings), which is why LRU is the default in almost every real system you will meet. But the deeper lesson is not "LRU always wins"; it is that every eviction policy encodes an assumption about your access pattern, and the moment your actual access pattern stops matching that assumption, the cache quietly stops helping, which is precisely the cache-pollution scenario in this module's Common Mistakes section.

Caching above the hierarchy: buffer pools, hit rate, and cache pollution

A database's buffer pool is nothing more than an LRU-flavored cache of disk pages held in RAM, sitting directly on top of everything in the previous two sections, the exact same eviction-policy reasoning applies, just one layer up the stack, caching whole disk pages instead of individual memory pages. Hit rate, the fraction of accesses satisfied from the cache without touching the slower tier beneath it, is the single number that determines whether a workload feels "instant" or "sluggish," because every miss pays the full latency-hierarchy tax from the previous sections. A buffer pool sized and tuned for the desk's normal day-to-day pattern (a "hot set" of a few hundred actively-traded tickers, touched over and over) can deliver hit rates well above 90%, until something changes the access pattern. Cache pollution is exactly that failure: a single enormous, unusual scan (a ten-year backtest touching every historical row once) floods the cache with pages that will never be touched again, evicting the genuinely hot pages that every other concurrent user depended on, so one analyst's one-off report can quietly tank every other analyst's afternoon, with no error message anywhere to explain why. Real systems defend against this with separate cache pools for scan-heavy versus point-lookup-heavy workloads, or by deliberately marking a bulk scan as "don't cache this", but recognizing the failure mode by name is the systems-thinking half of the fix; the code is the easy part.

Storage devices: disks, SSDs, pages, and why "random" is the enemy

A spinning hard disk drive (HDD) is, physically, a set of magnetic platters and a mechanical arm that must move to the correct location before it can read, the seek time cost from the latency table above. That mechanical fact has an enormous consequence: sequential reads (one location right after the previous one) require almost no additional seeking and can approach the disk's raw throughput, while random reads pay a full seek for every single access, making random I/O on an HDD one to three orders of magnitude slower than sequential I/O on the same device. A solid-state drive (SSD) has no moving parts and so has no seek time in the mechanical sense, but it still strongly favors sequential access over random access, because it reads and writes in fixed-size pages (commonly 4 KB or larger) and must sometimes erase and rewrite an entire larger block to update even a single page, a real, if smaller, "prefer contiguous, prefer bulk" asymmetry survives the transition from spinning disks to flash. The upshot for anything you design: whenever you have a choice, arrange data so that the values a typical query needs together are stored physically near each other, so that one sequential read serves many logical requests. That single design principle is the entire justification for the next two sections.

Row-store vs column-store: the physical layout decision that changes everything

A table has rows and columns, but a physical storage layer has to pick one linear order to actually write bytes in, and that choice is the single biggest performance lever in analytics. A row-oriented store lays every column of row 1 contiguously, then every column of row 2, and so on: excellent when your typical operation touches most or all columns of a few specific rows (fetch this one trade's full record), which is exactly the OLTP pattern from the section below. A column-oriented store instead lays every row's value for column A contiguously, then every row's value for column B, and so on: excellent when your typical operation touches one or a few columns across many or all rows (the average closing price across ten years of history), which is exactly the analytic (OLAP) pattern this entire program's worked examples live in.

Exercise CS2.04-e03, bytes_scanned(n_rows, col_widths, cols_needed, columnar), makes the trade-off arithmetic explicit rather than hand-wavy. A columnar layout need only read the bytes belonging to cols_needed, times n_rows; a row layout must read every column's bytes for every touched row, because a row store cannot skip columns within a row it has already committed to reading. On a realistic seven-column NSE-style OHLCV schema (date, symbol, open, high, low, close, volume, summing to 58 bytes per row) with 1,000 rows, a query that only needs close scans 8,000 bytes columnar versus 58,000 bytes row-oriented, a more than 7× difference for a single narrow column, and the gap only widens as tables grow wider. The general rule falls straight out of the arithmetic: column-oriented storage wins by a margin proportional to how few of the table's columns a typical query actually touches, and an analyst's typical query (aggregate one or two measures, filter on a couple of dimensions, ignore the other forty columns) is close to the worst case for a row store and close to the best case for a column store. This is precisely why every serious analytics warehouse and file format built for analysts (Parquet included) is columnar, while the transactional system feeding it trades and orders underneath is almost always row-oriented.

Parquet, encoding, and compression: what a columnar file format actually does

Apache Parquet (and formats like it) are, underneath the marketing, doing two very learnable things, both of which you can build a toy version of yourself. First, the core physical transform: turning a row-major table into a column-major one, and back, losslessly. Exercise CS2.04-e05, rows_to_columnar(rows) / columnar_to_rows(cols), is exactly that transform in miniature, get this round trip exactly right and you have, in essence, built the layer every columnar format sits on. Second, compression that only works because values are adjacent within a column, which a row store cannot exploit nearly as well, because adjacent bytes in a row store belong to different columns with different types and different value distributions. The simplest such scheme, and the one exercise CS2.04-e04 asks you to implement, is run-length encoding (RLE): instead of storing a repeated value once per row, store the value once alongside how many times it repeats: ("IT", 5), ("Banking", 2), ("Pharma", 3) instead of ten separate strings for a ten-row sector column. RLE is the simplest member of a much larger family real formats also use (dictionary encoding, which maps each distinct value to a small integer once and stores integers thereafter; bit-packing; delta encoding for sorted or near-sorted numeric columns), but RLE alone already teaches the load-bearing lesson: compression is not free, and it is not universal. It costs CPU time to decode on every read, and it only saves space when the data has the right shape, low cardinality, and ideally sorted or naturally clustered so that identical values sit next to each other. Run RLE against a column of ten million distinct trade IDs and every "run" has length one; encoding then costs more space than the raw values (you now store both a value and a redundant count for data that never repeated), not less. Compression is a bet on the shape of your data, not a free lunch, which is exactly why real formats let you choose an encoding per column rather than applying one scheme uniformly.

{
  "skill": "Using an AI coding assistant to scaffold a cache or storage-layout simulator without silently shipping a broken eviction policy",
  "use": "After you can already trace FIFO and LRU eviction by hand (this section, exercises CS2.04-e01/e02), ask a coding assistant to draft the first pass of a cache class or a bytes-scanned estimator so you spend your time on the interesting edge cases, not boilerplate — then read every line before you trust it.",
  "tools": ["AI coding assistants — Claude, GitHub Copilot, Cursor, ChatGPT"],
  "prompt": "Write a Python class ManagedCache with get(key) and put(key, value) implementing <FIFO|LRU> eviction with a fixed capacity. Include a short docstring stating the eviction rule in one sentence, and do not use any import beyond collections.",
  "verify": "Read every line — do not just run it and check the visible test. Specifically check: (1) does a HIT correctly refresh recency for LRU (a common off-by-one: only PUT refreshes order, not GET)? (2) does eviction happen exactly when the cache is already full, not one step early or late? (3) run it against this module's own hand-traced numbers (FIFO on the Belady string = 9 faults at capacity 3, 10 at capacity 4; LRU on 1,2,1,3,1,4 at capacity 2 = 2 hits) before trusting it on anything else — a subtly wrong eviction order will often still 'run' without error while quietly returning the wrong count.",
  "diy": "You must already be able to hand-trace both FIFO and LRU on a short reference string (this section) before asking an assistant to write the general-purpose version — otherwise you cannot tell a plausible-looking but subtly wrong eviction order from a correct one, and the hidden tests in CS2.04-e01/e02 exist precisely to catch that gap.",
  "market": "IN"
}

Indexes: B-trees, hash indexes, and the cost of "fast lookup"

CS2.03 taught you to write CREATE INDEX. This section teaches you why it works and, just as importantly, when it does not. A B-tree index is a balanced, wide-fanout tree structure, and its defining feature (the one that makes it the default on-disk index structure for essentially every relational database) is that its height (the number of pages, and therefore roughly the number of disk I/Os, a lookup costs in the worst case) grows only as log base fanout of the key count, and a B-tree's fanout is deliberately matched to the storage page size so that each node can hold hundreds of keys. Exercise CS2.04-e06, btree_height(n_keys, fanout), makes this concrete: with a fanout of 1,000 (realistic for small keys on a modern page size), one billion keys need a tree only 3 levels deep (since 1000³ = 1,000,000,000 exactly), three page reads, worst case, to find any one of a billion rows. Contrast that with the same formula run at fanout 2 (approximating a plain binary search tree, one comparison per level): the same billion keys need 30 levels, ten times as many I/Os, each potentially a full disk seek. That ten-to-one gap, multiplied by every query your warehouse ever runs, is the entire reason nobody builds an on-disk index as a binary tree.

A hash index trades the B-tree's ordering guarantee (it cannot answer range queries ("give me everything between these two dates") because a hash function deliberately scatters nearby keys apart) for average-case constant-time exact-match lookups: hash the key, land directly on its bucket, done. Exercise CS2.04-e08 has you build one from scratch, simple_hash(key) and hash_bucket_loads(keys, n_buckets), and it deliberately forbids Python's own built-in hash(). This is not a stylistic preference. CPython randomizes its string hash per process, specifically as a security defense (PYTHONHASHSEED), which means the exact same key can land in a different bucket on every single run. That is a fine property for an in-memory dictionary within one running program; it is a correctness bug waiting to happen for anything you persist to disk or compare across runs or machines, because a "reproducible, deterministic" bucket assignment is precisely what an on-disk hash index requires. Building your own small, fixed, deterministic hash function (h = (h * 31 + ord(char)) % 1_000_003, character by character) is the honest fix, and it is exactly what real embedded and on-disk hash structures do under the hood.

Neither index is free, and neither is automatically the right answer. An index costs storage (it is, physically, another data structure that must be kept in sync with every write) and it costs write time (every INSERT/UPDATE must also update every index on that table), the classic write amplification trade-off. And an index only helps a read when it is selective: an index on a column with only two distinct values (say, market IN/US across ten million rows) still has to walk roughly half the table to answer WHERE market = 'IN', so the query planner will often correctly choose a full table scan instead, a plain sequential read, which the previous section already established is fast compared to random access via a low-value index. "Add an index" is not a universal performance incantation; it is a bet that a specific column is selective enough, and queried often enough, to be worth its write-side cost.

ACID and durability, briefly: what the database promises you

CS2.03 introduced ACID (Atomicity, Consistency, Isolation, Durability) as the guarantee a database makes to its users. This module adds one mechanical fact about how durability is actually kept: a database does not simply hope its in-memory buffer pool survives a crash; before it acknowledges a write as committed, it first appends a compact record of that write to a sequential, append-only write-ahead log (WAL) on durable storage. Because the log is purely sequential, appending to it is cheap (recall the sequential-versus-random asymmetry from two sections ago) even though the corresponding buffer-pool pages might not be flushed to their final on-disk location until later, in a background checkpoint. If the system crashes between the WAL append and the checkpoint, recovery simply replays the log forward from the last checkpoint, durability recovered from a sequential file, not from hoping RAM never loses power. You will not implement a WAL in this module's code pack (that is squarely CS2.06/production-engineering territory), but recognizing that "durable" is not magic, it is "written to a sequential log before anything is acknowledged": completes the mental model CS2.03 left as a black box.

A small analyst data warehouse: OLTP vs OLAP, star schemas, and batch pipelines

Put the last several sections together and a genuine design pattern falls out, one that Martin Kleppmann's Designing Data-Intensive Applications documents at industrial scale and this module gives you in miniature. OLTP (online transactional processing) systems handle the day-to-day operational load (record this trade, update that client's holdings) one row at a time, read-and-write, and are naturally row-oriented for exactly the reasons two sections back. OLAP (online analytical processing) systems answer an analyst's questions (total notional traded by market last quarter, average spread by sector) touching few columns across enormous numbers of rows, and are naturally column-oriented for the same reasons. Running heavy analytical queries directly against the operational (OLTP) system is a classic mistake: a ten-year aggregate scan will pollute the operational cache exactly as described above, degrading the live trading desk's day for the sake of a report. The standard fix is architectural, not clever: periodically extract data from the operational system, transform it into an analysis-friendly shape, and load it into a separate analytical store optimized for scanning, the ETL pattern, running as a scheduled batch pipeline, is the seam between the two worlds.

The shape that analytical store almost always takes, even in miniature, is a star schema: one or more central fact tables (one row per event (a trade, a filing) surrounded by smaller dimension tables (descriptive attributes about the entities in the facts) a company's market, sector, listing exchange) that the facts reference by key. Exercise CS2.04-e07 builds exactly this in two tables (a companies dimension (company_id, symbol, market, sector) and a trades fact table (trade_id, company_id, trade_date, qty, price)) and asks for the query that sits at the center of almost every warehouse report ever written: join fact to dimension, group by a dimension attribute, aggregate a fact measure. SELECT c.market, SUM(t.qty * t.price) ... GROUP BY c.market is a two-line query, but it is the query that an entire star-schema architecture, an ETL pipeline, and a columnar storage layer all exist to make fast at scale, everything else in this module is infrastructure built to keep that one pattern cheap as the table grows from thousands of rows to billions.

{
  "skill": "Using an AI assistant to explain unfamiliar systems output (an EXPLAIN plan, a slow-query log, an unfamiliar storage format's documentation) without treating the explanation as ground truth",
  "use": "Paste a query plan, a schema, or a storage-format question to a chat assistant to get a fast first-pass explanation of what a database is doing and why a query might be slow — then verify the diagnosis against the actual mechanism (this module) and the database's own documentation before you act on it.",
  "tools": ["Chat assistants — Claude, ChatGPT, Gemini", "Your database's own EXPLAIN/EXPLAIN ANALYZE output — the actual primary source for what a query did"],
  "prompt": "Here is a query and its EXPLAIN ANALYZE output: <PASTE>. In plain language, explain what the query planner chose to do (scan type, join order, any index used) and name the single most likely reason this query is slower than expected, grounded in what the plan actually shows — not a generic list of possible causes.",
  "verify": "An assistant explaining a query plan can still produce a fluent, plausible-sounding diagnosis that doesn't match what the plan actually says (a hallucinated index that isn't in your schema, a claimed full scan where the plan shows an index scan). Re-read the EXPLAIN output yourself line by line and confirm the assistant's claim against it directly; check any general claim about index selectivity or storage layout against this module's own reasoning (or Kleppmann's book) rather than accepting it as authoritative on its own.",
  "diy": "You must already be able to explain, unaided, why a low-selectivity index doesn't help and why a columnar layout beats a row layout for a narrow analytic query (this module's Core content) before an AI's query-plan explanation is something you can actually evaluate rather than just believe.",
  "market": "US"
}

Where this leaves you (and where the productivity payoff sits)

Hold the ladder and the whole module becomes one coherent story instead of a list of trivia: registers, cache, RAM, SSD, disk, network, each roughly one to three orders of magnitude farther and slower than the one before. Virtual memory and paging manage the RAM/disk boundary; FIFO, LRU, and buffer pools decide what stays close when everything cannot; row-versus-column layout and compression decide how expensively an analytic query touches what it needs; B-trees and hash indexes decide how cheaply a lookup finds one needle in a very large haystack; and a star-schema warehouse with a batch ETL pipeline is simply all of the above, assembled once, on purpose, so that the two-line aggregation query an analyst actually cares about stays fast as the table grows. The productivity payoff (objective 9, R10) is that this same mental model is exactly what lets you use an AI assistant well on systems-adjacent code: you can ask it to draft a cache, a schema, or a query, and because you already know what a correct eviction order, a selective index, and a sane fact/dimension split look like, you can tell a plausible-looking answer from a right one instead of just hoping.

Common mistakes & how experts think differently

"The query is slow: get a bigger machine." More RAM changes how much fits in the fast tier; it does nothing about an access pattern that insists on jumping randomly through the slow tier regardless of how big the fast tier is. The expert's first move is never "add hardware", it is "name the access pattern," because a random-access workload on more RAM is still a random-access workload, and the real fix (an index, a columnar layout, a different join order) is usually free.
"SQL is inherently slow; Python/pandas is inherently fast" (or vice versa). Neither language determines performance here, the physical layout and access pattern do. A badly-indexed, row-scanning SQL query and an equivalent row-by-row Python loop over the same badly-laid-out data are both slow for the same underlying reason (random, wide, unnecessary bytes touched), and a well-indexed SQL aggregate can trivially beat naive Python doing the identical logical work. The expert asks "how many bytes does this actually have to touch, and how are they laid out," never "which language is faster" in the abstract.
"Caching always helps, so cache everything." A cache is a bet that the same data will be re-requested soon; a one-off bulk scan run through a cache sized for a small, stable "hot set" doesn't just fail to benefit, it actively evicts the genuinely hot data and degrades every other concurrent user's hit rate (cache pollution, this module's Core content). The expert asks whose access pattern a given cache is tuned for before assuming a new workload will benefit from it, and deliberately routes one-off scans around shared caches when the system allows it.
"An index always speeds up a query." An index only helps when it is selective enough to let the engine skip most of the table; an index on a near-binary column (market IN/US across ten million rows) still requires touching roughly half the table for a filter on one value, and a full sequential scan can genuinely beat a low-selectivity index lookup because sequential access is so much cheaper than the hierarchy's random-access tax. The expert checks selectivity before assuming an index helps, and remembers that every index also has a permanent write-side cost.
"Compression is free storage savings: apply it everywhere." Run-length encoding (and every richer scheme built on the same idea) trades CPU decode time for disk space, and it only wins when values repeat; RLE-encoding a column of ten million distinct IDs, where every "run" has length one, produces an encoding larger than the raw data (a value plus a redundant count, for data that never repeated). The expert checks a column's cardinality and ordering before reaching for a compression scheme, because the wrong scheme on the wrong column is a net loss, not a free win.
"Row stores and column stores are basically interchangeable; pick whichever." The two physical layouts are optimized for opposite access patterns (few columns across many rows (columnar) versus many columns of a few rows (row-oriented)) and using the wrong one for your actual workload is not a minor inefficiency, it is routinely a 5–50× difference on real analytic queries, as this module's own bytes_scanned arithmetic shows. The expert asks "does my typical query touch most columns of few rows, or few columns of many rows" before picking a storage layout, not after.
"Parquet, columnar formats, and warehouses are 'big data' concerns that don't matter at my scale." The bytes-scanned arithmetic in this module applies identically whether the table has a thousand rows or a billion; a single analyst's laptop loading a wide CSV with pandas.read_csv versus a narrow Parquet file for the same three columns will feel the difference at completely ordinary, single-machine scale. The expert treats "row versus column" as a default design question for any tabular file they'll read more than once, not a specialized concern reserved for distributed systems.
"hash(key) in Python is a fine, general-purpose way to bucket keys, including for anything I'll persist or compare across runs." CPython deliberately randomizes its built-in string hash per process (PYTHONHASHSEED) as a security defense, so the very same key can land in a different bucket every time the program restarts, invisible within a single run, and a genuine, hard-to-diagnose correctness bug the moment you persist a hash-derived bucket or index to disk, or compare it across machines or processes. The expert reaches for their own small, fixed, documented hash function (exactly as CS2.04-e08 requires) the moment a hash-based structure needs to survive past one running process.

The thread through all eight: the expert never treats "slow" or "fast" as a property of a language, a tool, or a raw amount of hardware. They treat it as the predictable consequence of how far the bytes a workload actually needs are from the CPU, and how well the system's layout, cache, and index choices match the workload's real access pattern, and they can always name which of those levers is the one actually in play before they touch anything.

Worked examples

Worked example 1: The memory-hierarchy ladder: estimating a backtest's time budget

An analyst is about to run a backtest that will touch 50 million individual price records once each, in order. Before running it, estimate: how long would this take if every record required a random SSD read (~100 microseconds each), versus if the whole history could be scanned sequentially from RAM (~100 nanoseconds each, since sequential access barely pays the per-access latency at all)?

Solution. Step 1: set up the arithmetic. 50,000,000 records × 100 microseconds (0.0001 seconds) each, if every single record requires its own random SSD read = 50,000,000 × 0.0001 s = 5,000 seconds, or roughly 83 minutes. Step 2, the RAM/sequential case. The same 50,000,000 records, read sequentially from RAM at roughly 100 nanoseconds (0.0000001 s) of effective per-record cost (sequential access amortizes almost all of the per-access latency away) = 50,000,000 × 0.0000001 s = 5 seconds. Step 3, read the ratio, not the absolute numbers. Roughly 1,000×, going from random-SSD-per-record to sequential-in-RAM turns an 83-minute job into a 5-second one, without changing a single line of the actual backtesting logic. Read it. This is the entire justification for everything the rest of this module teaches: loading the relevant slice of history once, sequentially, into memory-resident structures (exactly what a columnar in-memory DataFrame does) is not a minor optimization, it is routinely the difference between "runs during a coffee break" and "runs overnight." (Per the perishable note in Core content, treat the specific microsecond/nanosecond figures as order-of-magnitude illustrations, not a benchmark of any particular machine.)

Worked example 2: Row-store vs column-store on an NSE analytics query (India)

An analyst's NSE end-of-day table has seven columns (date, symbol, open, high, low, close, volume) with illustrative byte widths {date:8, symbol:10, open:8, high:8, low:8, close:8, volume:8} (58 bytes/row total) and 1,000 rows. A dashboard needs only the close column to plot a price history. Compute the bytes scanned under a columnar layout versus a row-oriented layout.

Solution. Step 1: columnar. Only close's bytes are read: 8 bytes × 1,000 rows = 8,000 bytes. Step 2: row-oriented. Every column of every touched row must be read regardless of which column the query actually wants: 58 bytes × 1,000 rows = 58,000 bytes. Step 3, the ratio. 58,000 / 8,000 = 7.25×, for a single narrow column out of seven, the row store reads more than seven times as much as it needs to. Read it. This is exactly code pack exercise CS2.04-e03's bytes_scanned function, and the ratio only grows as the schema grows wider (a table with forty columns and the same one-column query would show roughly a 40× gap, not 7×), which is precisely why real analyst warehouses, holding hundreds of fundamental and market-data fields per company, lean so heavily on columnar storage.

Worked example 3: Run-length encoding a US sector column (US)

A US equities table's sector column, sorted by sector, reads: Tech, Tech, Tech, Financials, Financials, Financials, Financials, Energy, Energy, Energy (10 rows). Compute its run-length encoding and its compression ratio.

Solution. Step 1: encode. Scanning left to right and collapsing each run: [("Tech", 3), ("Financials", 4), ("Energy", 3)]: three runs. Step 2: compression ratio. Using compression_ratio(values) = len(values) / (len(encoded) * 2) (raw element count over encoded storage units, two units, value and count, per run): 10 raw values / (3 runs × 2 units) = 10 / 6 ≈ 1.67× smaller. Step 3, the condition for this to work. Notice the entire saving depended on the column being sorted or naturally clustered so identical values sit adjacent, this is exactly code pack exercise CS2.04-e04. Read it. Try the same three sector labels in a shuffled, non-adjacent order (Tech, Financials, Tech, Energy, Financials, ...) and every run collapses to length one or two; the ratio falls toward, or below: 1.0. Run-length encoding is not compressing "the sector column" in the abstract; it is compressing this specific arrangement of it, which is exactly why real columnar formats often sort or dictionary-encode a column before run-length-encoding it.

Worked example 4: Belady's anomaly: more memory, more page faults

A process references pages in the order 1,2,3,4,1,2,5,1,2,3,4,5 under FIFO replacement. Compute the total page faults with 3 frames, then with 4 frames, and explain the result.

Solution. Step 1: trace 3 frames. Faults on 1, 2, 3 (filling the frames); 4 evicts the oldest (1); 1 evicts 2; 2 evicts 3; 5 evicts 4; then 1 and 2 are hits (both currently resident); 3 evicts 1; 4 evicts 2; 5 is a hit. Total: 9 faults. Step 2: trace 4 frames. Faults on 1, 2, 3, 4 (filling the larger frame set); 1 and 2 are now hits; 5 evicts the oldest (1); 1 evicts 2; 2 evicts 3; 3 evicts 4; 4 evicts 5; 5 evicts 1. Total: 10 faults, one more than with 3 frames, despite having more memory available. Step 3: name the mechanism. FIFO evicts by load order, not by usage, giving it a fourth frame changes exactly which page is "oldest" at each subsequent step, and in this reference string that change happens to make several later hits become faults instead. Read it. This is Belady's anomaly, and it is the single cleanest argument in this entire module for why usage-aware policies like LRU exist: a policy that is blind to actual access patterns can behave in ways that violate the most basic intuition anyone has about caching ("more memory can only help"). Verify both totals yourself against CS2.04-e01 before trusting this paragraph.

Worked example 5: Why databases don't use binary trees for on-disk indexes

A warehouse table has one billion rows, indexed by a B-tree with a fan-out of 1,000 (realistic for small keys on a modern storage page). Compute the index's height, and contrast it with the height of a plain binary search tree (fan-out 2) over the same billion keys.

Solution. Step 1. B-tree height. btree_height(1,000,000,000, 1000) = ceil(log₁₀₀₀(1,000,000,000)). Since 1000³ = 1,000,000,000 exactly, this is 3, three levels, three page reads (worst case) to find any one of a billion rows. Step 2: binary-tree height, same key count. Using the identical formula with fan-out 2 (log base 2): log₂(1,000,000,000) ≈ 29.9, so ceil(...) = 30: thirty levels. Step 3, the real-world cost. If each level potentially costs one disk I/O in the worst case, the B-tree needs 3 I/Os and the binary tree needs 30, a 10× difference, on every single lookup, forever, as long as the table exists. Read it. A B-tree's wide fan-out is not an arbitrary implementation detail; it is chosen specifically so that each tree level corresponds to one storage page, collapsing the "distance" a lookup has to travel down the memory hierarchy's ladder as much as possible. This is code pack exercise CS2.04-e06, and it is the entire reason a "smarter" binary search tree is, for on-disk indexes, the wrong answer.

Worked example 6: A two-market analyst warehouse query (India + US)

A small warehouse has a companies dimension table and a trades fact table (schema: CS2.04-e07). companies holds (1, 'INFY', 'IN', 'IT') and (2, 'AAPL', 'US', 'Tech'); trades holds four rows: 100 units of INFY at 1,500.0 and 50 units at 1,520.0; 10 units of AAPL at 190.0 and 5 units at 192.0 (all figures illustrative). Write and hand-verify the query that returns total notional traded per market.

Solution. Step 1, the query. SELECT c.market, SUM(t.qty * t.price) AS total_notional FROM trades t JOIN companies c ON c.company_id = t.company_id GROUP BY c.market ORDER BY c.market;, join fact to dimension, group by the dimension attribute, aggregate the fact measure. Step 2, compute India's total by hand. (100 × 1,500.0) + (50 × 1,520.0) = 150,000 + 76,000 = 226,000. Step 3, compute the US total. (10 × 190.0) + (5 × 192.0) = 1,900 + 960 = 2,860. Step 4, read the result set. [('IN', 226000.0), ('US', 2860.0)], ordered by market. Read it. This two-line query is the star-schema pattern in miniature, one join, one group-by, one aggregate, and it is exactly what CS2.04-e07's hidden tests reseed with entirely different India- and US-heavy company/trade mixes to confirm your query generalizes rather than hardcodes this one pair of numbers.

Practice set

Work each problem fully before reading its solution. Numeric answers are exact unless stated otherwise.

P1 (guided). FIFO by hand. Trace FIFO page replacement over the reference string 1,2,1,3,1,4 with capacity 2. How many page faults occur?

Solution. 1 → fault, frame [1]. 2 → fault, frame [1,2]. 1 → hit (already resident). 3 → fault, evict oldest (1), frame [2,3]. 1 → fault, evict oldest (2), frame [3,1]. 4 → fault, evict oldest (3), frame [1,4]. Total: 5 faults (only one hit, the second 1, which arrives before its slot is stolen).

P2 (guided). Same string, LRU. Trace LRU over the identical reference string 1,2,1,3,1,4 with capacity 2. How many hits, and how does this compare to P1's FIFO result?

Solution. 1 → miss, cache {1}. 2 → miss, cache {1,2}. 1 → hit, moved to most-recently-used. 3 → miss, evict the least-recently-used (2), cache {1,3}. 1 → hit again, moved to most-recently-used. 4 → miss, evict the least-recently-used (3), cache {1,4}. Total: 2 hits, double FIFO's 1 hit on the identical sequence, because LRU explicitly protects a just-reused key from eviction while FIFO evicts strictly by load order regardless of reuse.

P3. Latency ratio, RAM vs SSD. If a RAM access costs roughly 100 nanoseconds and a random SSD read costs roughly 100,000 nanoseconds (100 microseconds), how many RAM accesses fit in the time of one SSD read?

Solution. 100,000 / 100 = 1,000×: roughly a thousand RAM accesses in the time of a single random SSD read. This is the ratio that makes "keep the working set in RAM" worth real engineering effort.

P4. Latency ratio, RAM vs disk seek. A disk seek costs roughly 10,000,000 nanoseconds (10 ms); a RAM access costs roughly 100 nanoseconds. What is the ratio?

Solution. 10,000,000 / 100 = 100,000×. A single disk seek costs the same time as one hundred thousand RAM accesses, which is why even a handful of unavoidable random disk seeks can dominate an entire workload's runtime.

P5. Bytes scanned, a wide "notes" column. A table has five columns with byte widths {a:4, b:4, c:8, d:8, e:100} (e is a free-text notes field) and 10,000 rows. A query needs only column c. Compute bytes scanned columnar versus row-oriented, and the ratio.

Solution. Columnar: 8 × 10,000 = 80,000 bytes. Row-oriented: every column's width must be read regardless: (4+4+8+8+100) × 10,000 = 124 × 10,000 = 1,240,000 bytes. Ratio: 1,240,000 / 80,000 = 15.5×. A single wide, mostly-irrelevant text column can singlehandedly make the row-store penalty far worse than a "typical" schema suggests, exactly the situation bytes_scanned (CS2.04-e03) is built to make visible before you pay for it in production.

P6. RLE compression ratio. A column reads A,A,A,A,A,A,A,A,B,B (eight A's, two B's). Give its run-length encoding and compression ratio.

Solution. Encoding: [("A", 8), ("B", 2)]: two runs. Compression ratio: 10 raw values / (2 runs × 2 units) = 10 / 4 = 2.5× smaller. A column with very few, very long runs compresses dramatically better than one with many short runs (compare Worked Example 3's 1.67×, from three shorter runs).

P7. Why does columnar_to_rows need the row count n up front? columnar_to_rows(cols) in exercise CS2.04-e05 computes n = len(cols[keys[0]]) before reconstructing any row. Why is this necessary, rather than just iterating "however many values happen to be there"?

Solution. A column-major table is stored as several independent same-length arrays, one per field, with no row boundary markers anywhere in the data itself, nothing in a bare column-major representation says "here is where row 3 ends and row 4 begins" except the shared index position across every column's array. n (the length of any one column, since all columns must be equal length in a well-formed table) is what tells the reconstruction how many rows to walk, pick i from 0 to n-1 and read cols[key][i] from every column to rebuild one row. Without n, the function has no way to know when to stop.

P8. B-tree height, one billion keys. Compute btree_height(1_000_000_000, 1000).

Solution. 1000 to the third power is exactly 1,000,000,000, so log₁₀₀₀(1,000,000,000) = 3 exactly, and ceil(3.0) = **3**. A billion-row table, three page reads to find any row.

P9. The binary-tree contrast. Compute the same function with fanout = 2 over the same one billion keys, and state what this approximates.

Solution. log₂(1,000,000,000) ≈ 29.897, so ceil(...) = **30**. Using fanout = 2 in the same height formula approximates a plain binary search tree (each node has two children). Thirty levels versus the B-tree's three is a 10× difference in worst-case disk I/Os per lookup, on every single query, forever, the concrete reason on-disk indexes are wide B-trees, never binary trees.

P10. Hashing by hand: order matters. Using simple_hash(key): h = 0; for each character, h = (h * 31 + ord(char)) % 1_000_003. Compute simple_hash("AB") and simple_hash("BA"), and state what the comparison shows.

Solution. For "AB": start h=0; char 'A' (ord 65): h = (0*31+65) % 1_000_003 = 65; char 'B' (ord 66): h = (65*31+66) % 1_000_003 = 2015+66 = **2081**. For "BA": char 'B' (ord 66) first: h = 66; char 'A' (ord 65): h = (66*31+65) % 1_000_003 = 2046+65 = **2111**. The two hashes differ (2081 vs 2111) even though the characters are identical, this hash is position-sensitive, not a bag-of-characters hash, exactly like a real string hash needs to be (otherwise every anagram would collide).

P11. Fact or dimension? In the companies / trades schema (CS2.04-e07), is trades the fact table or the dimension table? Justify from the definitions in this module.

Solution. trades is the fact table: it holds one row per event (one trade), and it carries the numeric measures (qty, price) that get aggregated. companies is the dimension table, it holds descriptive attributes (market, sector) about the entities the facts reference, and it is what a report typically groups or filters by, not what it sums.

P12. OLTP or OLAP? Classify each as primarily an OLTP or an OLAP workload, and justify in one clause each: (a) recording a single client's trade confirmation the instant it executes; (b) computing total notional traded across every client for the whole of last quarter; (c) updating one company's sector classification after a reclassification.

Solution. (a) OLTP: one row, written and read individually, low-latency operational work. (b) OLAP, a wide aggregate scanning many rows across a long time window, the analytic pattern this module's columnar reasoning targets. (c) OLTP, a single, small, operational update to one dimension row, not an analytic query.

P13. Cache pollution scenario. A desk's buffer pool is sized and tuned for its normal day-to-day hot set of roughly 200 actively-traded tickers. One analyst kicks off a one-off report that scans the full ten-year price history for every ticker the exchange has ever listed. What happens to every other analyst's cache hit rate immediately afterward, and why?

Solution. Every other analyst's hit rate drops, often sharply, right after the scan. The ten-year historical scan touches an enormous number of pages that will likely never be touched again soon, and because the buffer pool has a fixed, limited capacity, bringing all of those pages in necessarily evicts the genuinely hot 200-ticker working set that everyone else depended on. The scan itself may run fine; the damage shows up as a mysterious, unexplained slowdown for everyone else, with no obvious link back to the one-off report that caused it: cache pollution.

P14. Index selectivity. A ten-million-row table has a market column with only two distinct values (IN/US). Would adding an index on market alone meaningfully speed up WHERE market = 'IN'? Why or why not?

Solution. Generally no. With only two distinct values roughly evenly split, an index on market still points to something on the order of five million matching rows out of ten million, the query still has to fetch roughly half the table either way, and the extra index-lookup step (following pointers to scattered row locations) can cost more than simply scanning the table sequentially, which the memory-hierarchy section already established is comparatively cheap. An index earns its keep on selective columns (say, a unique trade ID, or a narrow date range), not on a near-binary flag.

P15. Compression can hurt. A column holds ten million values, every one of them distinct (e.g., a unique trade_id). Using compression_ratio(values) = len(values) / (len(rle_encode(values)) * 2), what happens to the ratio, and what does that mean practically?

Solution. If every value is distinct, every "run" in the run-length encoding has length exactly 1, so the number of encoded runs equals the number of raw values: len(encoded) == len(values). The ratio becomes len(values) / (len(values) * 2) = **0.5**, the "compressed" representation is twice as large as the raw data, because you are now storing a redundant count of 1 alongside every value that never repeated. Practically: never apply run-length encoding to a high-cardinality column (unique IDs, timestamps to the microsecond), check cardinality and ordering first, or use a different encoding entirely (dictionary encoding, delta encoding) suited to that column's actual shape.

P16. The hash()-as-index bug. A learner builds index = {hash(symbol): row for symbol, row in table} in Python, writes index to disk, and reloads it in a fresh run the next day. Why is this a genuine bug, even though it worked perfectly within the session that created it?

Solution. CPython randomizes its built-in string hash() per process, seeded differently on every run (PYTHONHASHSEED), specifically as a security defense against hash-flooding attacks. hash("INFY") in today's process is very likely not the same integer as hash("INFY") in tomorrow's process, so an index keyed on today's hash values will silently fail to find "INFY" when looked up tomorrow using tomorrow's (different) hash of the same string, no error, just a lookup that returns "not found" for data that is actually present. The fix, exactly as in CS2.04-e08, is to use your own small, fixed, explicitly-documented hash function whenever a hash-derived structure needs to survive past a single running process.

Applied mini-project

Build a tiny analyst warehouse and benchmark it: rows vs columns, then cache it.

This project turns the module's four load-bearing ideas (layout, compression, indexing, caching) into one hands-on artifact, using functions from code-packs/CS2.04.json (module id CS2.04) as your toolkit. It is a self-scored worksheet: the code pack's own exercises are what the mastery gate grades; this project is where you assemble them into a single, realistic mini-decision.

Do this, in order:

Build a table. In your own Python environment (or this node's Code tab), construct a synthetic table of at least 500 rows and at least 6 columns, resembling either an NSE-style or a US-style OHLCV schema plus one categorical column (sector or exchange), seeded/synthetic data is fine and expected (R3); just note your seed.
Measure the layout trade-off. Using bytes_scanned (or your own equivalent), compute bytes scanned under columnar and row-oriented layouts for three different queries against your table: one needing exactly 1 column, one needing 3, and one needing all of them. Tabulate all six numbers (3 queries × 2 layouts) and the resulting ratios.
Measure the compression trade-off. Run rle_encode/compression_ratio (or your own equivalent) against your categorical column, both in its natural (possibly sorted) order and in a randomly shuffled order. Report both ratios and explain the gap in one sentence.
Measure the cache trade-off. Construct an access pattern of at least 50 lookups where a small "hot set" of 5–10 keys is accessed roughly 80% of the time and everything else 20% of the time (a Zipfian-style skew). Run this pattern through both a FIFO cache and an LRU cache, each of capacity 5, and report both hit rates.
Write the memo. In 150–300 words, state and justify a recommendation: given your measurements, would you store this specific table row-wise or column-wise for your simulated workload, would you add an index (and to which column, with a selectivity justification), and which cache eviction policy you'd pick, grounded in your own numbers from steps 2–4, not in generic advice.

Deliverable and self-check. One worksheet: your table's schema and seed, the six bytes-scanned numbers plus ratios, both compression ratios plus the one-sentence explanation, both cache hit rates, and the 150–300 word memo. Score yourself 2 points each for: (a) the layout measurement genuinely spans 1/3/all-columns queries with correct arithmetic; (b) both compression ratios are reported and the sorted-vs-shuffled gap is correctly explained; (c) both cache hit rates are reported and are internally consistent with your stated access pattern; (d) the memo's recommendation is directly justified by your own numbers, not generic claims; (e) all data is clearly marked seeded/synthetic with its seed recorded (R3). Pass at 8/10 with no zero on any item.

Lab: open the CS2.04 code pack in this node's Code tab (code-packs/CS2.04.json) and clear all eight exercises (CS2.04-e01 through CS2.04-e08), each ships a structured fallback, so the lab stays completable even fully offline, with zero runtime.

Reading & resources

Everything below is an anchor to build genuine understanding from and verify claims against, never a substitute for hand-tracing the module's own worked examples and code pack. Free unless marked; level tags reflect the ramp from intuition to mechanism.

The core spine (start here):

Martin Kleppmann, Designing Data-Intensive Applications: the field's standard reference; this module is deliberately "DDIA-lite." Chapters on storage engines, encoding, and replication map directly onto this node's Core content. [Paid $] [Intermediate–Advanced ▼]
Remzi H. and Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces (OSTEP), free online; the virtualization (memory, paging) chapters are the deepest, most rigorous free treatment of this module's OS material. [Free ✓] [Beginner–Advanced ▲▼]
CMU 15-445/645 Database Systems (Andy Pavlo), free lecture recordings covering storage, buffer pools, indexes (B-trees and hash), and query execution at a level well beyond this module, for anyone who wants to go deeper. [Free ✓] [Advanced ▼]

Foundational and historical:

The Elements of Computing Systems (Nisan & Schocken) / the Nand2Tetris project, build a computer from NAND gates up; the most literal possible answer to "how does a computer really work." [Paid $, free course materials ✓] [Beginner–Intermediate ▲]
Ulrich Drepper, What Every Programmer Should Know About Memory, a rigorous, freely available deep dive into the cache-hierarchy material in this module's Core content, for the reader who wants the hardware-level detail. [Free ✓] [Advanced ▼]
Apache Parquet's own format documentation, the primary source for how a real columnar file format extends this module's toy rows_to_columnar/RLE into production encodings (dictionary, bit-packing, delta). [Free ✓] [Intermediate ▲]

Practical and perishable (treat as dated):

SQLite's own documentation on its B-tree page format, a genuinely readable, primary-source description of exactly the index structure this module teaches, for the database this program's own SQL exercises run on (sql.js). [Free ✓] [Intermediate ▲] (implementation detail: check against current SQLite docs)
Your own machine's actual latency numbers, if you want to replace this module's illustrative ratios with real measurements, any simple benchmark script timing sequential vs. random reads on your own disk will do. [Free ✓] [Beginner ▲] (perishable by nature: hardware-specific)
Python's sys.getsizeof, array, and struct modules' own documentation, the practical, stdlib-only tools for inspecting and building compact layouts yourself, directly usable inside this module's code pack. [Free ✓] [Beginner ▲]

Do this, not just read: on your own machine, write a ten-line script that times reading the same 50 MB of data twice, once as a wide CSV with pandas.read_csv, once as the same data saved and reloaded as a narrow Parquet file selecting only two columns, and watch Worked Example 2's arithmetic show up as an actual wall-clock difference on your own hardware, not just a word-problem.

Teach it back & journal

Feynman prompt. Explain to a colleague who has only ever used spreadsheets why a report that "just sums one column" can run in under a second against a Parquet file but takes much longer against the exact same data saved as a wide CSV with fifty other columns, using the idea that a row-oriented layout must read every column of every touched row, while a column-oriented layout reads only the column the query actually needs. Then explain, in the same breath, why adding "more RAM" would not fix a query that is slow because of random disk access on a badly-chosen physical layout, using the idea that more fast storage changes how much fits close to the CPU, not whether the access pattern insists on jumping through the slow tier anyway. If your colleague can, unprompted, predict that a query touching one column of a hundred-column table is a case where columnar storage will win by a huge margin, and say roughly why, you have installed the mechanism this module exists to teach.

Journal prompt. For one working week, notice every time something you or a colleague built "just feels slow," and for each one, write down: which layer of the memory hierarchy is most likely the bottleneck (RAM-resident cache miss, random disk/SSD access, or a network round trip)? Is the culprit more likely a layout mismatch (row vs column for this specific access pattern), a missing or low-selectivity index, or a cache being polluted by someone else's one-off scan? Did you reach for "add more hardware" before you'd actually named the mechanism, and if so, what would naming it first have told you to do instead? Close with a paragraph on this: the analyst who understands the memory hierarchy does not necessarily write faster code on the first try, but they can always explain why something is slow in one sentence grounded in mechanism, and that one sentence is usually worth more than an afternoon of guessing which knob to turn.

This module's flashcards and mastery quiz are wired into the app: see the node's Quiz and Reviews.

Systems & Data-Intensive Thinking