Search Knowledge

© 2026 LIBREUNI PROJECT

Database Systems/Storage, access, and execution
Page 9 of 20

Storage Engines

Trace how a durable record moves through pages, a buffer pool, and a recovery-safe write path.

Lesson briefStorage, access, and execution · 8 h · 4 outcomes

Required knowledge

  • Fixed-size arrays, trees, hashing, and asymptotic I/O reasoning
  • Relational rows, keys, and the distinction between a logical identifier and a physical address
  • Basic concurrency vocabulary: shared state, critical sections, and races

Learning outcomes

  • Trace an insert or update from a logical row through a slotted page, buffer frame, dirty state, and durable write boundary.
  • Distinguish a page pin, latch, and transaction lock and diagnose the failure caused by confusing them.
  • Choose row, column, or log-structured storage for a stated workload and defend the choice with I/O, update, and recovery costs.
  • State the write-ahead condition that makes a dirty-page flush recoverable.

Assessment target

Given an unseen page trace and workload, identify the first violated storage invariant, repair the buffer/log protocol, and justify a layout choice under a changed workload.

Scope boundary

  • Vendor file formats, operating-system page cache tuning, SSD firmware behavior, and implementation of lock-free buffer pools are outside scope.
  • Columnar execution and LSM compaction are compared as physical-design choices, not implemented in full.

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/OExpand

A page I/O is one page read or write; it is the model’s unit of work. A scan over NN pages is O(N)O(N) I/Os. A balanced tree with fan-out BB reaches a key in about O(log⁡BN)O(\log_B N) 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.

Code
rectangle "page 42 header\nLSN = 910" as H
rectangle "slot 0 → offset 8060\nslot 1 → offset 7994" as S
rectangle "free space" as F
rectangle "tuple: order 17\npaid_at = NULL" as T0
rectangle "tuple: order 18\npaid_at = 10:03" as T1
H -down-> S
S -down-> F
F -down-> T0
T0 -down-> T1
note right of S
An index can name
(42, 1), even if T1
moves inside page 42.
end note
page 42 headerLSN = 910slot 0 → offset 8060slot 1 → offset 7994free spacetuple: order 17paid_at = NULLtuple: order 18paid_at = 10:03An index can name(42, 1), even if T1moves inside page 42.

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?

HintExpand

Ask whether the record identifier names bytes or an indirection entry.

Worked solutionExpand

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.

MechanismProtectsTypical lifetimeFailure if omitted
Pinframe residencyuntil caller releases the pageeviction turns a live pointer into a stale reference
Latchbytes and metadata in one framea short critical sectionconcurrent slot edits corrupt page structure
Transaction lock / version rulelogical row or predicateuntil commit, abort, or validationa correct page can still contain a lost update

Worked trace — two fetches and one eviction

  1. Worker A fetches page 42; the page table installs frame 3 and A pins it.
  2. Worker B asks for page 42 while the read is in flight; B joins that in-flight fetch rather than issuing a second read.
  3. A latches frame 3, changes slot 1, marks it dirty, releases the latch, and later unpins it.
  4. 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?Expand

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.

HintExpand

A page referenced once by the scan looks recent to LRU.

Worked solutionExpand

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

LayoutFavorsPays forBoundary case
Row storepoint reads, full-row writes, transactional updatesunnecessary bytes during narrow analyticswide rows can waste cache and I/O
Column storescans of few attributes, aggregation, compressionrewriting or locating one full mutable rowlate materialization must still reconstruct rows when needed
Log-structured / LSMsustained append-heavy writes and immutable segmentscompaction, read amplification, tombstone retentiona 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.

HintExpand

Separate the write path, analytical path, and point-lookup path instead of seeking one universally best layout.

Worked solutionExpand

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.

QuestionRow store answerColumn store answer
Read one full orderone page, all attributes togetherreconstruct the row from several column segments
Sum one numeric columnread all attributes, discard mostread only that segment, often compressed
Update one fieldin-place or new tuple versionappend a delta or rewrite a segment
Compress repeated valueslimited by row heterogeneitystrong per-column encodings
Late materializationunnecessaryfetch 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?

HintExpand

Compare the bytes and structures touched by a point operation, not only the scan's previous throughput.

Worked solutionExpand

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

0 / 4 answered

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.

1
Scanning and filtering only compressed status and date column segments avoids reading the remaining 37 unreferenced attributes from disk.
2
Late materialization evaluates predicates to form qualifying row-id bitsets before fetching matching revenue segment values.
3
A columnar layout is universally superior to a row store for OLTP workloads consisting of high-frequency single-tuple point updates.
4
Late materialization requires the query engine to immediately reconstruct full 40-attribute tuples in memory before filtering.

A log makes a dirty page recoverable

Theorem 3.1.1Write-Ahead Logging Protocol Invariant

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?

HintExpand

Check whether any durable record of LSN 911 reached non-volatile storage.

Worked solutionExpand

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.

Section Exercises

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

Verificationapplication

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, identify why this flush violates the write-ahead logging invariant and what failure mode ensues if power is lost immediately afterward.

HintExpand

Examine whether recovery can reconstruct the transaction status of changes on page 42.

Worked solutionExpand

The flush violates Theorem 3.1.1 because the data page modification reached disk before its explanatory log record was durable. If power is lost immediately afterward, recovery encounters a page containing an uncommitted modification without a durable undo log record, leaving persistent storage in an unrecoverable, inconsistent state.

Exercise 3.1.2: Slotted-Page Architecture and Item Pointer Indirection

Descriptionrecall

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.

HintExpand

Indexes store (page_number, slot_index) pairs rather than raw byte offsets.

Worked solutionExpand

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

Constructionapplication

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).

HintExpand

Row store must read all 50,000 pages. Column store reads only the filter and target columns.

Worked solutionExpand
  1. Row store: Scans all 50,000 pages = 50,000×8 KB=400 MB50{,}000 \times 8\text{ KB} = 400\text{ MB}
  2. Column store: The filter column requires 1,000,000×8 B=8 MB1{,}000{,}000 \times 8\text{ B} = 8\text{ MB} (1,000 pages). The matching 1% (10,000 rows) requires reading target column segments for those positions 10,000×8 B=80 KB10{,}000 \times 8\text{ B} = 80\text{ KB} spanning at most 1,000 pages if contiguous or fetched selectively). Total columnar I/O is at most 8 MB+8 MB=16 MB8\text{ MB} + 8\text{ MB} = 16\text{ MB} a 25×25\times reduction in data transferred.

Exercise 3.1.4: Layout Selection under Shifting Analytical-OLTP Workloads

Generalisationtransfer

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.

HintExpand

Analyze write amplification and lock granularity for point updates across 50 separate column files.

Worked solutionExpand

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