Cover

CMU Database Group · 1:22:41 · Watch on YouTube

Summary

University lecture (CMU 15-445/645, Fall 2024) that finishes the tuple-oriented storage model and then presents its two main alternatives. The first half completes slotted pages and record IDs — with live demos of ctid, rowid and %%physloc%% in PostgreSQL, SQLite, SQL Server and Oracle — and enumerates the problems of tuple-oriented storage: fragmentation, useless disk I/O, random I/O, and the fact that append-only storage layers such as S3 and HDFS cannot do in-place updates at all. That motivates log-structured storage / LSM trees (MemTable → SSTable → levels → compaction, as implemented by LevelDB and RocksDB) and index-organized storage, positioned as opposite ends of the write-cost vs. read-cost trade-off. The second half zooms into the bytes of a single tuple: word alignment, padding vs. attribute reordering, integer and fixed-point numeric representation, three ways to encode NULLs, and overflow pages for values larger than a page.

flowchart TD
  A[Storing tuples on disk] --> B[Tuple-oriented<br/>heap files + slotted pages]
  A --> C[Log-structured storage<br/>LSM trees]
  A --> D[Index-organized storage<br/>tuples in leaf nodes]
  B --> B1[Record IDs · page directory<br/>fragmentation, random I/O,<br/>needs in-place updates]
  C --> C1[MemTable → SSTable → levels<br/>summary tables + Bloom filters<br/>compaction, write amplification]
  D --> D1[Pay at write time<br/>reads land directly on data]
  A --> E[Inside a single tuple]
  E --> E1[Word alignment: padding / reordering]
  E --> E2[Types: ints, IEEE 754 vs numerics]
  E --> E3[NULLs: bitmap / sentinel / per-attribute]
  E --> E4[Overflow pages for large values]

Topics

  1. Course logistics and announcements
  2. Tuple-oriented architecture and slotted pages
  3. Record IDs
  4. Inserting and updating tuples
  5. Problems with tuple-oriented storage
  6. Log-structured storage and LSM trees
  7. Levels, reads, and summary tables
  8. Compaction, RocksDB, and the trade-offs
  9. Index-organized storage
  10. What a tuple is: layout and word alignment
  11. Representing attribute data types
  12. Large values and overflow pages
  13. Conclusion and next class

Key takeaways

  • Real systems disagree on page compaction, and the demo proves it: after deleting a tuple and re-inserting, SQL Server compacted the page and reused slot 1, while PostgreSQL, SQLite and Oracle all left the gap and appended at the end. SQL Server compacts because it already holds the latch; Postgres optimizes for getting in and out of the page fast 13:23 20:17
  • The in-place update assumption is the real breaking point: SSDs rewrite whole blocks, and HDFS, Amazon S3 and Google Colossus are append-only access methods where a written page can be deleted but never overwritten — which is what makes log-structured storage necessary rather than merely fashionable 22:53 23:28
  • LSM trees trade write speed for read cost, and pay it back as write amplification: writes become blind inserts into the MemTable at near bare-metal SSD speed, but a single logical write can be physically rewritten dozens or hundreds of times as it is compacted down the levels — burning out SSDs or running up cloud bills. Index-organized storage is the exact mirror image: pay at insert, read cheaply 39:52 47:19 50:13
  • Bloom filters and min/max summaries are both required, for different query shapes: a filter says only whether a key exists, which lets a read skip an entire level holding thousands of SSTables; min/max ranges are what make range scans possible, since you cannot probe unknown keys individually 37:05 38:02
  • The first thing Facebook did when forking LevelDB into RocksDB was remove mmap and write a real buffer manager — letting the OS manage pages is called "a terrible idea", and rebuilding that manager is exactly Project 1 45:19
  • Column order physically changes tuple size: pg_column_size showed the same mixed char/integer columns taking 48 bytes in one declaration order and 44 bytes when reordered, because Postgres pads less. Casting three integers from 32-bit to 16-bit dropped a row from 36 to 30 bytes 1:01:28 1:01:45 1:01:10
  • Exactness costs speed, deliberately: IEEE 754 cannot represent 0.1 + 0.2 exactly, so every DBMS also ships fixed-point numerics — Postgres stores digits, weight, scale and sign, and its numeric addition is a branch-heavy routine that cannot match a single hardware float instruction 1:05:57 1:07:27 1:08:20
  • NULL encoding is settled by storage model: bitmap in the tuple header for row stores, sentinel values for column stores (they preserve fixed-length offsets), and never a per-attribute null bit — it turns an 8-bit boolean into 16 bits. Only MemSQL shipped that, and dropped it on rebranding to SingleStore 1:12:08 1:12:35
  • Overflow pages unlock optimizations regular data pages cannot have: skipping the read entirely when the query does not touch the column, compressing it with gzip/Snappy/Zstandard, or storing an inline prefix ("German strings") so prefix predicates are answered without ever following the pointer 1:18:38 1:19:25