Page Management

A database may contain millions of pages across thousands of tables and indexes. How does the system know which pages have free space for new inserts? How are new pages allocated as data grows? What happens to pages when records are deleted—do they return to a free pool, or does the space linger as fragmentation?

Page management encompasses all the mechanisms that coordinate page allocation, track free space, and maintain efficient storage utilization. These mechanisms operate largely invisibly, but their effectiveness directly impacts database performance, storage efficiency, and operational complexity.

When a table or index needs a new page, the database must decide:

1. Where in the file should this page be physically located?
2. How is the page initialized?
3. How is it linked to other pages in the same object?

Allocation Approaches

PostgreSQL Allocation Model

PostgreSQL uses a relatively simple model:

Table → Relation file(s) on disk
  main fork: user data (heap pages)
  fsm fork: Free Space Map
  vm fork: Visibility Map
  init fork: for unlogged tables

Page allocation:
  1. Extend file by one page (8KB)
  2. Initialize page header
  3. Zero remaining bytes
  4. Update FSM to show available space
  
No explicit extent grouping; pages added sequentially.
OS and filesystem handle physical contiguity.

InnoDB Extent Model

Tablespace → Multiple files
  Segment: collection of extents for one B-tree level
  Extent: 64 contiguous pages (1MB for 16KB pages)
  Page: 16KB

Allocation levels:
  - First 32 pages: single-page allocation
  - After: extent allocation for locality
  
Fragmented pages for small tables (< 32 pages)
Full extents for larger tables (better scan performance)

When inserting a row, the database must find a page with sufficient free space. Scanning every page would be O(n)—impractical for large tables. Free Space Maps (FSM) provide efficient space lookup.

PostgreSQL FSM Details

FSM fork: tablename_fsm

Structure: Binary tree stored across FSM pages
  - Leaf nodes: 1 byte per heap page
  - Internal nodes: max of children
  - Root: max free space in entire table

Free space encoding (1 byte = 256 categories):
  Category × 32 = approximate free bytes
  Category 0: < 32 bytes free
  Category 255: > 8160 bytes free (nearly empty)

Search algorithm:
  1. Start at root
  2. Request: need 500 bytes → category 16 (500/32)
  3. Navigate tree to find leaf with category ≥ 16
  4. Return page number
  5. Insert may fail if estimate inaccurate → try next

Update policy:
  - VACUUM updates FSM from actual page contents
  - INSERT/UPDATE may update FSM opportunistically
  - Stale FSM can cause unnecessary page extensions

InnoDB Free Space Management

Page types for space management:
  - FSP_HDR page: tablespace header + extent descriptors
  - XDES pages: additional extent descriptors
  - INODE pages: segment descriptors
  
Extent states:
  - FREE: available for allocation
  - FREE_FRAG: partially used, pages can be allocated
  - FULL_FRAG: all pages in use
  - Segment-owned: belongs to specific segment

Per-page free space tracked in page headers.
Segment manages list of pages with free space.

PostgreSQL maintains a Visibility Map (VM) alongside the FSM. While FSM tracks free space, the VM tracks which pages are 'all-visible'—containing only tuples visible to all transactions.

Visibility Map Structure

VM fork: tablename_vm

Format: 2 bits per heap page
  Bit 0: All-visible flag
    1 = All tuples on page visible to all transactions
    0 = Some tuples may be invisible to some transactions
  Bit 1: All-frozen flag (PostgreSQL 9.6+)
    1 = All tuples are frozen (ancient, never need visibility check)
    0 = Some tuples may need freezing

Compactness: 1 VM page tracks 8192 × 8 / 2 = 32,768 heap pages
  For 8KB pages: ~256MB of heap per VM page

Use Cases

Index-Only Scan Example

SELECT customer_id FROM orders WHERE status = 'shipped';

-- If there's an index on (status, customer_id):

-- Without VM / not all-visible:
  1. Search index → find matching entries with (status, customer_id, TID)
  2. For each TID, fetch heap page to check visibility (MVCC)
  3. Return customer_id if visible
  
-- With VM showing pages all-visible:
  1. Search index → find matching entries
  2. Check VM: is page at TID all-visible?
     If yes: trust index data, skip heap fetch
     If no: fetch heap page for visibility check
  3. Return customer_id

-- Result: Dramatically fewer heap I/Os for recent tables

VM Maintenance

• Set all-visible: VACUUM, when page confirmed all-visible
• Clear all-visible: Any INSERT/UPDATE/DELETE on page
• Set all-frozen: VACUUM FREEZE (or regular vacuum for old tuples)
• Clear all-frozen: Logically, never happens (frozen is permanent)

Index pages, unlike heap pages, maintain sorted order. When a page fills and a new entry must be inserted, the page must split. Conversely, when deletions leave pages too empty, they may merge with siblings.

B-Tree Page Split

Before split: Page P is full, need to insert key 'M'

  Page P: [A, B, C, D, E, F, G, H, I, J, K, L, N, O, P, Q, R, S, T]
                                           ↑ Insert 'M' here
                                           No room!

Split process:
  1. Allocate new page P'
  2. Choose split point (typically middle: 'J')
  3. Move keys > J to new page P'
  4. Insert 'M' into appropriate page (P' since M > J)
  5. Add separator key 'J' to parent (with pointer to P')
  6. Parent may cascade split if full

After split:
  Page P: [A, B, C, D, E, F, G, H, I, J]
  Page P': [K, L, M, N, O, P, Q, R, S, T]
  Parent: [..., (ptr to P), 'J', (ptr to P'), ...]

Cost of split:
  - Write 3 pages (P, P', parent) — potentially more if cascades
  - Brief lock escalation
  - WAL logging for each page

Merge (Coalesce) Operations

Trigger: Page utilization drops below threshold (often 50%)

Merge process:
  1. Identify under-full sibling pages
  2. If combined content fits in one page:
     a. Copy all entries from one page to another
     b. Remove separator from parent
     c. Mark emptied page as free
  3. Parent may cascade merge if under-full

Alternatives to merge:
  - Redistribution: Move some entries from fuller sibling
  - Deferred merge: Mark for later batch processing
  - No merge: Accept space wastage (common choice!)

Why many databases don't merge aggressively:
  - Merge is expensive (page locks, WAL, parent update)
  - Workload may re-fill pages (wasted merge effort)
  - Dead pages are reclaimed during rebuild operations

In MVCC databases, deleted rows aren't immediately removed—they may be visible to in-progress transactions. VACUUM is the garbage collection process that reclaims space from dead tuples.

Standard VACUUM Process

Phase 1: Heap Scan
  For each page not all-visible in VM:
    1. Acquire page lock (share)
    2. Identify dead tuples (xmax < oldest active transaction)
    3. Mark dead tuples for removal
    4. Update page's free space
    5. If page now all-visible, update VM
    
Phase 2: Index Cleanup
  For each index on table:
    1. Scan index for TIDs of dead tuples
    2. Remove index entries pointing to dead tuples
    3. Recycle empty index pages to free list
    
Phase 3: Heap Cleanup
  For each page with dead tuples:
    1. Acquire page lock (exclusive, brief)
    2. Remove dead tuples, update slot directory
    3. Optionally compact page
    4. Update FSM
    
Phase 4: Truncation (optional)
  If trailing pages are all-empty:
    1. Acquire AccessExclusiveLock briefly
    2. Truncate file, returning space to OS
    3. Update relation size

Autovacuum Tuning

Key parameters:

  autovacuum_vacuum_threshold = 50
  autovacuum_vacuum_scale_factor = 0.2
  
  Trigger: vacuum when dead_tuples > threshold + scale_factor × n_live_tup
  
  For 1M row table: vacuum when dead > 50 + 0.2 × 1M = 200,050 dead tuples
  For 100 row table: vacuum when dead > 50 + 0.2 × 100 = 70 dead tuples

Aggressive tables (high churn):
  ALTER TABLE orders SET (autovacuum_vacuum_scale_factor = 0.05);
  -- Vacuum at 5% instead of 20%

Large tables:
  ALTER TABLE huge_archive SET (autovacuum_vacuum_threshold = 10000);
  -- Don't vacuum for few scattered deletes

Monitoring:
  SELECT relname, n_dead_tup, last_vacuum, last_autovacuum
  FROM pg_stat_user_tables ORDER BY n_dead_tup DESC;

Bloat occurs when dead space accumulates faster than it's reclaimed. A 10GB logical table might occupy 50GB on disk. This wastes storage, slows scans, and increases backup sizes.

Detecting Bloat

-- Quick estimate using pg_stat_user_tables
SELECT 
    relname,
    n_live_tup,
    n_dead_tup,
    round(100.0 * n_dead_tup / nullif(n_live_tup + n_dead_tup, 0), 1) as dead_pct,
    pg_size_pretty(pg_relation_size(relid)) as table_size
FROM pg_stat_user_tables
ORDER BY n_dead_tup DESC
LIMIT 20;

-- More accurate: pgstattuple extension
CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT * FROM pgstattuple('orders');
-- Returns: dead_tuple_percent, free_percent, etc.

-- Table size vs estimated live data size
SELECT
    relname,
    pg_size_pretty(pg_relation_size(oid)) as actual_size,
    pg_size_pretty((n_live_tup * avg_row_width)::bigint) as estimated_live_size
FROM pg_class
JOIN pg_stat_user_tables ON pg_class.oid = pg_stat_user_tables.relid
WHERE avg_row_width > 0;

Bloat Prevention Strategies

Different databases approach page management with varying philosophies: