Page header

Every page carries a header describing its contents (59:44, 1:01:09). Typical fields:

  • Page size and checksum (1:00:08)
  • DBMS version that created the page, so an upgrade can detect older page formats and convert them (1:00:08)
  • Transaction visibility information (covered with transactions) (1:00:26)
  • Compression / encoding metadata (1:00:26)
  • Schema information — only in self-contained designs such as Oracle's; most systems do not (59:44, 1:00:08)
  • Sketches / zone maps, e.g. min-max values, so a range query can skip the page body entirely after reading the header — heavily used by column stores (1:00:26, 1:00:46)

Storage models (today's assumptions)

  • Tuple-oriented storage is the focus today: attributes of one record stored contiguously as a row, then the next record (1:01:44).
  • Assume all attributes of a tuple fit in one page — relaxed next week (1:01:44).
  • Deferred alternatives (1:02:15, 1:02:27, 1:02:41):
    • Log-structured storage: store redundant tuple versions as a log.
    • Index-organized storage (MySQL, SQLite): the table is a tree, with data in the leaves and inner/leaf nodes mixed in the file.

Straw-man layout (bad idea)

  • Header counts the tuples; each insert computes the offset of the next free spot and appends until the page is full (1:03:01).
  • Problems (1:03:23, 1:03:37, 1:04:05):
    • Deletes are fine only for fixed-length tuples; variable-length tuples (email addresses, IDs) make finding a fitting free slot hard.
    • Moving a tuple within the page forces updating everything pointing at it, e.g. indexes.
  • Log-structured databases do use this append pattern, but with variable-size tuple support (1:03:37).

Slotted pages (what row stores actually do)

  • Essentially every row-oriented DBMS uses some variant of a slot array plus movable tuple data (1:04:05, 1:04:23, 1:08:40).
  • Layout (1:04:41, 1:05:03, 1:05:19):
    • Slot array of fixed-length offsets grows from the start of the page forward.
    • Fixed- and variable-length tuple data grows from the end of the page backward.
    • The page is full when the two meet in the middle.
flowchart LR
    subgraph Page
      H[Header] --> S["Slot array (offsets) -->"]
      S -.->|grow toward each other| T["<-- Tuple data"]
    end
  • Delete: mark the slot as empty in the slot array/header; the data can simply be left in place (1:05:38, 1:05:56).
  • Optional compaction: move a later tuple into the hole, then update only its slot-array offset — external pointers stay valid because they reference the slot, not the byte offset (1:06:11).

Is compaction worth it?

  • Student objections: a small tuple might fit the hole anyway; shuffling many small tuples is wasteful (1:06:31, 1:06:53, 1:07:08).
  • Instructor's answer — it depends, and the objections ignore disk (1:07:25):
    • In-memory shuffling is essentially free compared with fetching another page from disk (1:07:25, 1:07:52).
    • The real cost is concurrency: compaction holds the page latch (a lock) longer, blocking other readers/writers (1:07:52, 1:08:10).
  • Who does what: SQL Server and Oracle compact; Postgres does not (1:08:22).
  • Record IDs were pushed to the next lecture to make room for the flash talk (1:08:22).