An order update changes paid_at from NULL to a timestamp. The SQL-level fact is tiny; the physical system must find a page, keep it resident while a worker changes it, preserve a stable reference from indexes, and survive a power loss between the write and the acknowledgement. A storage engine is the machinery that makes those obligations compatible.
Readiness refresh: cost tools for page I/OExpandCollapse
A page I/O is one page read or write; it is the model’s unit of work. A scan over pages is I/Os. A balanced tree with fan-out reaches a key in about page reads. A hash table is useful for equality lookup under its distribution assumptions, not for ordered range traversal. Treat these as named approximations: each comparison states its page, cache, and workload assumptions.
Pages preserve location while records move
A slotted page grows its slot directory from one end and tuple payloads from the other. A slot points to a tuple’s current offset. Moving a variable-length tuple within the page changes the slot, so an index entry that names the slot remains valid. Moving it to another page requires a forwarding record or index maintenance. The distinction explains why a physical identifier is unsuitable as a public business identifier.
The header records structural facts such as free-space boundaries and, in a WAL-based engine, the most recent log sequence number reflected by the page. PostgreSQL’s current format is a concrete example: it has a fixed page header, line pointers, free space, items, and special space. Other engines choose different fields; the indirection principle is the transferable idea.
Prediction — a tuple grows
Page 42 has 40 bytes of free space. Slot 1 points to a 24-byte tuple. Updating the tuple makes it 56 bytes. Which action preserves an index entry (42, 1): overwrite in place, change only the slot, or copy to page 43 without further work?
HintExpandCollapse
Ask whether the record identifier names bytes or an indirection entry.
Worked solutionExpandCollapse
Overwriting is impossible: the tuple needs 32 more bytes. If another 56-byte region exists within page 42 after compaction, the engine can copy the tuple there and change slot 1’s offset; (42, 1) still resolves. Copying it to page 43 without a forwarding record or index update leaves the old identifier dangling. The missing idea is stable indirection, not a larger page.
A buffer frame has three different protections
The buffer pool maps page identifiers to memory frames. Fetching a page pins a frame, possibly waits for I/O, and returns a frame that is initialized. A short latch protects the in-memory page structure while the worker examines or changes slots. A transaction lock or MVCC rule governs which logical rows a transaction may observe or modify across statements. These scopes differ deliberately.
| Mechanism | Protects | Typical lifetime | Failure if omitted |
|---|---|---|---|
| Pin | frame residency | until caller releases the page | eviction turns a live pointer into a stale reference |
| Latch | bytes and metadata in one frame | a short critical section | concurrent slot edits corrupt page structure |
| Transaction lock / version rule | logical row or predicate | until commit, abort, or validation | a correct page can still contain a lost update |
Worked trace — two fetches and one eviction
- Worker A fetches page 42; the page table installs frame 3 and A pins it.
- Worker B asks for page 42 while the read is in flight; B joins that in-flight fetch rather than issuing a second read.
- A latches frame 3, changes slot 1, marks it dirty, releases the latch, and later unpins it.
- Eviction may choose frame 3 only after all pins are gone. It first satisfies the log condition below, writes the dirty page if necessary, then removes the page-table mapping.
Why not hold one global latch during step 2?ExpandCollapse
I/O can take orders of magnitude longer than metadata updates. A global latch held during I/O serializes unrelated page lookups. A correct design protects the page table briefly, represents the in-flight state, and lets other fetches wait on that page rather than on the entire pool.
Application — scan pollution
A pool holds 100 pages. A hot OLTP working set uses pages 1–80 repeatedly. An analyst sequentially scans 10,000 distinct pages using naive LRU. Predict the result for the next OLTP burst.
HintExpandCollapse
A page referenced once by the scan looks recent to LRU.
Worked solutionExpandCollapse
The scan continually inserts one-time pages at the most-recent end and eventually evicts much of pages 1–80. The next OLTP burst faults those hot pages again. A scan-resistant policy can give sequential pages low retention priority or use a separate ring, but it cannot ignore the need to pin pages while a scan consumes them.
Layout is a workload hypothesis
| Layout | Favors | Pays for | Boundary case |
|---|---|---|---|
| Row store | point reads, full-row writes, transactional updates | unnecessary bytes during narrow analytics | wide rows can waste cache and I/O |
| Column store | scans of few attributes, aggregation, compression | rewriting or locating one full mutable row | late materialization must still reconstruct rows when needed |
| Log-structured / LSM | sustained append-heavy writes and immutable segments | compaction, read amplification, tombstone retention | a point read needs an index/filter across levels |
Compression changes the I/O/CPU balance. Dictionary, run-length, delta, and bit-packed encodings exploit repeated or ordered values; they are not free. A column segment that compresses well may be expensive to update one row at a time. An LSM engine writes new versions sequentially, then compacts segments; it must retain a delete tombstone until every relevant snapshot and replica can no longer interpret an older value.
Transfer — a changed workload
An event table receives 50,000 inserts/s, later serves a 90-day aggregate, and also supports one support-agent lookup by event ID. Choose a primary layout and name the auxiliary structure that prevents the lookup from becoming a full scan.
HintExpandCollapse
Separate the write path, analytical path, and point-lookup path instead of seeking one universally best layout.
Worked solutionExpandCollapse
An append-friendly log/LSM or time-partitioned row store fits the ingest path; columnar segments or a columnar replica can serve the aggregate after data becomes stable. A B-tree or hash-like key directory on event_id supplies the support lookup. The decision is conditional: if support lookups become dominant and updates are frequent, a row-oriented primary store may become the simpler choice.
Columnar execution changes the unit of work
A finance query that sums amount over 200 million orders touches one or two attributes. In a row store with a 200-byte row, a full scan still reads every attribute for every row: roughly 40 GB. In a column store the same query reads the amount column and perhaps region, and each column segment can be compressed independently: dictionary encoding for repeated region names, delta encoding for ordered timestamps, run-length encoding for low-cardinality status. The saving is not a better algorithm; it is a different unit of I/O.
A vectorized executor can process batches instead of invoking each operator once per row. Amortizing dispatch and processing contiguous values can improve CPU efficiency and sometimes expose SIMD operations; the gain depends on operator, data, and implementation. The MonetDB/X100 design uses this approach. Vectorized execution and columnar storage are complementary choices, not the same mechanism, and compression can add decoding work.
| Question | Row store answer | Column store answer |
|---|---|---|
| Read one full order | one page, all attributes together | reconstruct the row from several column segments |
| Sum one numeric column | read all attributes, discard most | read only that segment, often compressed |
| Update one field | in-place or new tuple version | append a delta or rewrite a segment |
| Compress repeated values | limited by row heterogeneity | strong per-column encodings |
| Late materialization | unnecessary | fetch remaining columns only for qualifying rows |
Columnar layouts pay for their scan advantage on updates and point reads. A single-row update may touch many segments, and a delete becomes a deletion vector or a rewritten segment. That is why analytical engines separate ingest, compaction, and query paths, and why a columnar layout is a workload hypothesis rather than a universal upgrade.
Application — change the workload
A fraud service changes from nightly two-column scans to frequent updates and lookups of individual orders with all 25 attributes. Does the original columnar advantage still determine the primary layout?
HintExpandCollapse
Compare the bytes and structures touched by a point operation, not only the scan's previous throughput.
Worked solutionExpandCollapse
Not by itself. A row-oriented primary with an order-ID index can fetch and update one record without reconstructing it from multiple column segments. Retain a columnar analytical replica only if measured scan demand justifies replication and freshness costs. Compare update rate, point latency, scan frequency, and lag rather than assuming either layout is always superior.
Columnar layout and late materialization
An analytical query evaluates SELECT AVG(revenue) FROM orders WHERE status = 'delivered' AND date >= '2026-01-01'. The table has 40 columns. Evaluate which statements regarding columnar storage and execution are correct:
Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.
A log makes a dirty page recoverable
Under write-ahead logging (WAL), the log record describing an update to a database page must be written to non-volatile storage before the modified data page itself may be flushed to disk. Furthermore, a transaction commit acknowledgement requires the corresponding commit log record to be durable.
Under write-ahead logging (WAL), the log record describing an update to a database page must be written to non-volatile storage before the modified data page itself may be flushed to disk. Furthermore, a transaction commit acknowledgement requires the corresponding commit log record to be durable.
For the paid_at update, write a log record with LSN 911, change the in-memory page, mark its page LSN 911, then flush the log through 911 before flushing page 42. After a crash, recovery compares the durable log with page LSNs: a page missing a logged update can be redone; an uncommitted update can be undone or made invisible according to the system’s recovery design. Writing the page first risks a durable change with no durable explanation.
Prediction — crash boundary
The log is durable through LSN 910. Page 42 has been changed in memory to page LSN 911, but neither the log record 911 nor the page is flushed. The machine loses power. What may recovery expose?
HintExpandCollapse
Check whether any durable record of LSN 911 reached non-volatile storage.
Worked solutionExpandCollapse
Nothing from LSN 911 may be exposed, because neither its log record nor its page image was durable. If the page had reached storage before the log record, recovery could find an unexplained update and could not rely on WAL redo/undo reasoning. The safe result follows from the ordering condition, not from hoping the device flushes in a convenient order.
Deep Practice
Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.
Exercise 3.1.1: Write-Ahead Logging Flushing Order Verification
A storage engine flushes dirty data page 42 (containing uncommitted update with page LSN 911) to persistent disk while the WAL buffer is durable only through LSN 910. Referring to Theorem 3.1.1
HintExpandCollapse
Examine whether recovery can reconstruct the transaction status of changes on page 42.
Worked solutionExpandCollapse
The flush violates Theorem 3.1.1
Exercise 3.1.2: Slotted-Page Architecture and Item Pointer Indirection
Describe how a slotted-page architecture uses an array of item pointers (line pointers) at the start of the page to decouple index pointers from physical byte offsets during record updates.
HintExpandCollapse
Indexes store (page_number, slot_index) pairs rather than raw byte offsets.
Worked solutionExpandCollapse
In a slotted page, indexes reference a tuple by its tuple ID (page_number, slot_index). The slot array grows forward from the page header while variable-length tuple records are packed from the end of the page upward. When a tuple is updated or defragmented within the page, only its offset in the slot array changes; index references to the stable slot index remain completely untouched.
Exercise 3.1.3: Row vs. Column I/O Calculation on Filtered Scans
Consider a table with 1,000,000 rows and 50 fixed-width 8-byte columns (400 bytes per row, 20 rows per 8 KB page, total 50,000 pages). An analytical query computes the average of one column for rows matching a predicate on another column, with 1% selectivity. Compare the raw I/O volume between a full row-store table scan and a column store using late materialization (assuming 8-byte uncompressed column segments).
HintExpandCollapse
Row store must read all 50,000 pages. Column store reads only the filter and target columns.
Worked solutionExpandCollapse
- Row store: Scans all 50,000 pages =
- Column store: The filter column requires (1,000 pages). The matching 1% (10,000 rows) requires reading target column segments for those positions spanning at most 1,000 pages if contiguous or fetched selectively). Total columnar I/O is at most a reduction in data transferred.
Exercise 3.1.4: Layout Selection under Shifting Analytical-OLTP Workloads
An engineering team migrates a financial fraud system from batch nightly reporting (2-column scans over 50 columns) to real-time transactional scoring (1,000 updates/sec touching all 50 attributes by customer ID). Contrast the physical trade-offs of retaining a pure columnar store versus switching to a row-oriented primary engine with an asynchronous columnar replica.
HintExpandCollapse
Analyze write amplification and lock granularity for point updates across 50 separate column files.
Worked solutionExpandCollapse
A pure columnar engine suffers extreme write amplification under 1,000 point updates/second: each single-row update must modify or append to 50 independent column segments, incurring heavy I/O, lock contention, and fragmentation. Switching to a row-oriented primary engine isolates each update to a single slotted page with minimal write amplification and microsecond index lookups. Analytical queries can be offloaded to an asynchronous columnar replica (e.g. via change data capture), decoupling write throughput from scan optimization.
References & Further Reading
- Stonebraker, M., et al. (2005). C-Store: A Column-oriented DBMS. VLDB, 553–564. (Column layout, compression, and read-optimized projections.)
- Abadi, D. J., Madden, S. R., & Hachem, N. (2008). Column-Stores vs. Row-Stores: How Different Are They Really? ACM SIGMOD, 967–980. (Late materialization, compression, and the limits of a row-store simulation.)
- Boncz, P. A., Zukowski, M., & Nes, N. J. (2005). MonetDB/X100: Hyper-Pipelining Query Execution. CIDR. (Vectorized, cache-conscious execution.)
- PostgreSQL: Database Page Layout
- PostgreSQL: Write-Ahead Logging
- CMU 15-445/645 Database Systems