Page Layout and Organization

Fixed-length records are elegant but limited. Real-world data is messy: user bios range from empty to thousands of characters, JSON documents vary from {} to megabytes, and images span bytes to gigabytes. Variable-length data is the norm, not the exception.

Handling variable-length data introduces fundamental challenges:

• How do you find where one field ends and the next begins?
• What happens when a value is too large for a single page?
• How do you update a value if the new version is larger than the old?
• Can you compress variable-length data to save space?

This page explores the techniques databases use to handle these challenges efficiently.

There are two primary strategies for encoding variable-length fields: length-prefixing and offset arrays.

The length field itself must balance overhead against maximum representable size.

PostgreSQL's varlena Format

PostgreSQL uses a clever variable-length header (varlena) that adapts to value size:

Varlena header interpretation (first byte):

┌─────────────────────────────────────────────────────────────┐
│ If first byte has high bit = 0:                             │
│   - 4-byte header: bits 0-29 = length including header      │
│   - bits 30-31 = compression/TOAST flags                    │
│   - Max untoasted size: ~1GB                                │
├─────────────────────────────────────────────────────────────┤
│ If first byte has high bit = 1:                             │
│   - 1-byte header (short varlena)                           │
│   - bits 1-7 = length including header                      │
│   - Max size: 127 bytes                                     │
│   - Saves 3 bytes per small string!                         │
├─────────────────────────────────────────────────────────────┤
│ Special encodings for TOAST pointers, compressed data, etc. │
└─────────────────────────────────────────────────────────────┘

Examples:
  'Hi' → 0x85 'H' 'i' (short varlena: 0x80 | 5 = header+data length)
  100-char string → 0x00000068 ... (4-byte header: 104 total bytes)

This optimization saves 3 bytes per small string—significant for tables with many short VARCHAR columns.

Variable-Length Integer Encoding (Varint)

SQLite and Protocol Buffers use varint encoding where smaller numbers use fewer bytes:

Varint encoding (SQLite style):
  Values 0-127:       1 byte  (high bit = 0)
  Values 128-16383:   2 bytes (first byte high bit = 1, continues)
  Values 16384+:      3+ bytes

Example: Length = 200
  Binary: 11001000 = 0xC8
  Varint: 0x81 0x48 (10000001 01001000)
    First byte: 0x81 -> high bit set, continue; value bits = 0000001
    Second byte: 0x48 -> high bit clear, done; value bits = 1001000
    Combined: 0000001_1001000 = 11001000 = 200

Varint is space-optimal when most lengths are small, but parsing is slightly more complex than fixed-size lengths.

What happens when a value is too large to fit on a single page? PostgreSQL's TOAST (The Oversized-Attribute Storage Technique) provides a comprehensive solution.

The Problem

PostgreSQL pages are 8KB. A single tuple must fit on one page (minus header overhead). But:

• TEXT columns can hold strings up to 1GB
• JSONB documents can be megabytes
• BYTEA can store arbitrary binary data

TOAST Solution

When a row is too large, TOAST kicks in:

1. Try compression — If column type supports it, compress the value
2. If still too big: out-of-line storage — Store in separate TOAST table, replace inline value with a TOAST pointer
3. Chunk large values — Split into ~2KB chunks stored across multiple TOAST pages

TOAST Strategies

TOAST Pointer Structure

typedef struct varatt_external {
    int32  va_rawsize;      // Original uncompressed size
    int32  va_extsize;      // External stored size (after compression)
    Oid    va_valueid;      // OID of TOAST value
    Oid    va_toastrelid;   // OID of TOAST table
} varatt_external;

// Size: 18 bytes on disk
// Replaces potentially multi-megabyte value

Every database system has its own mechanism for handling values that exceed page capacity:

Variable-length data often contains redundancy that compression can exploit. Databases offer multiple compression strategies:

Compression Tradeoffs

Compression Decision Matrix:

                 High Compression Ratio ──────────────►
          ┌────────────────────────────────────────────────┐
  Fast    │ LZ4, Snappy           │ zstd (balanced)       │
Decompress│ Good for OLTP,        │ Good general purpose, │
     │    │ hot data, real-time   │ configurable levels   │
     │    ├────────────────────────────────────────────────┤
     ▼    │ No compression        │ zlib, gzip            │
  Slow    │ Simple, CPU-free      │ Best ratio, slow      │
Decompress│ Max speed needed      │ Cold data, archival   │
          └────────────────────────────────────────────────┘

When to Use Compression:

• ✅ Large text values with redundancy (logs, HTML, XML)
• ✅ Cold/archival data rarely accessed
• ✅ I/O-bound systems (SSD/HDD often slower than decompression)
• ❌ Already-compressed data (images, videos, encrypted)
• ❌ CPU-bound systems with low I/O pressure
• ❌ Very small values (overhead > savings)

Index pages also must handle variable-length keys, but with different constraints than heap pages:

Why Index Keys Are Special

• Keys must fit on a single page — No TOAST/overflow for index entries
• Keys must be comparable — Compressed/encoded values must preserve order
• Fanout matters — Larger keys = fewer entries per page = taller tree

Key Truncation and Prefix Compression

B-tree indexes can use key abbreviation in internal pages:

Leaf level: Full keys for exact matching
  ['Alice', 'Bob', 'Charlie', 'David', 'Eve']

Internal level: Truncated separator keys
  ['C', 'E']  // Minimal keys that separate children

Prefix compression (InnoDB):
  Page stores common prefix once
  Individual entries store suffix only
  
  Original: ['product_12345', 'product_12346', 'product_12347']
  Prefix: 'product_1234'
  Entries: ['5', '6', '7']

Maximum Key Length

Strategies When Keys Are Too Long:

1. Use prefix index: INDEX(column(100))
2. Hash the value: INDEX(MD5(column)) with equality-only queries
3. Use full-text search instead of B-tree
4. Normalize: Extract long values to separate table
5. PostgreSQL: Use hash index (lower overhead than B-tree for long keys)

Updates to variable-length fields present unique challenges because the new value may differ in size from the old value.

Update Scenarios

Scenario 1: New value is SMALLER
  Old: 'The quick brown fox jumps over the lazy dog' (45 bytes)
  New: 'Hello' (5 bytes)
  
  Options:
  a) In-place update, leaving 40 bytes as internal fragmentation
  b) Delete old + insert new at different location
  c) Compact page after update
  
Scenario 2: New value is SAME SIZE
  Old: 'Hello' (5 bytes)
  New: 'World' (5 bytes)
  
  Simple in-place overwrite
  
Scenario 3: New value is LARGER
  Old: 'Hi' (2 bytes)
  New: 'Hello World' (11 bytes)
  
  Options:
  a) Extend in-place if contiguous free space available
  b) Relocate within same page if total space available
  c) Move to different page entirely
  d) Original slot becomes forward pointer (Oracle migration)
  e) MVCC: Keep old version, insert new version (PostgreSQL)

Scenario 4: Value exceeds TOAST threshold
  Old: 100-byte string (inline)
  New: 50KB document (must TOAST)
  
  Old inline space freed (or kept for MVCC)
  New value goes to TOAST table
  Pointer replaces inline value

Variable-length data is the norm in real-world databases, requiring sophisticated encoding and overflow mechanisms. Let's consolidate the key takeaways:

What's Next:

We've explored page structure, slot directories, record layouts, and variable-length handling. The final page brings everything together with page management—the policies and mechanisms that coordinate page allocation, free space tracking, and lifecycle management across the database.