1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

/* PostgreSQL Tuple Header Structure (simplified from htup_details.h) */
 
typedef struct HeapTupleHeaderData {
    union {
        HeapTupleFields t_heap;
        DatumTupleFields t_datum;
    } t_choice;
    
    ItemPointerData t_ctid;      /* Current tuple ID (6 bytes) */
    
    /* Fields below here must match MinimalTupleData */
    uint16      t_infomask2;     /* Number of attributes + flags */
    uint16      t_infomask;      /* Various flags (see below) */
    uint8       t_hoff;          /* Sizeof header incl. bitmap + padding */
    
    /* NULL bitmap and user data follow after header */
    bits8       t_bits[FLEXIBLE_ARRAY_MEMBER]; /* Null bitmap (variable length) */
    /* Actual row data follows the null bitmap */
} HeapTupleHeaderData;
 
typedef struct HeapTupleFields {
    TransactionId t_xmin;        /* Inserting xact ID */
    TransactionId t_xmax;        /* Deleting or locking xact ID */
    union {
        CommandId   t_cid;       /* Inserting or deleting command ID */
        TransactionId t_xvac;    /* VACUUM xact ID (for freezing) */
    } t_field3;
} HeapTupleFields;
 
/* t_infomask flag bits */
#define HEAP_HASNULL            0x0001  /* Has null attribute(s) */
#define HEAP_HASVARWIDTH        0x0002  /* Has variable-width attr(s) */
#define HEAP_HASEXTERNAL        0x0004  /* Has external stored attr(s) */
#define HEAP_HASOID             0x0008  /* Has an OID (deprecated) */
#define HEAP_XMAX_KEYSHR_LOCK   0x0010  /* xmax is a key-share locker */
#define HEAP_COMBOCID           0x0020  /* t_cid is a combo cid */
#define HEAP_XMAX_EXCL_LOCK     0x0040  /* xmax is exclusive locker */
#define HEAP_XMAX_LOCK_ONLY     0x0080  /* xmax is a locker only */
 
/* Hint bits - critical for MVCC performance */
#define HEAP_XMIN_COMMITTED     0x0100  /* t_xmin committed */
#define HEAP_XMIN_INVALID       0x0200  /* t_xmin invalid/aborted */
#define HEAP_XMAX_COMMITTED     0x0400  /* t_xmax committed */
#define HEAP_XMAX_INVALID       0x0800  /* t_xmax invalid/aborted */
 
/* Example tuple in memory:
 * +------------------+
 * | t_xmin = 12345   | <- Inserted by txn 12345
 * | t_xmax = 0       | <- Not deleted (still live)
 * | t_cid = 0        | <- First command in transaction
 * | t_ctid = (4,17)  | <- Page 4, item 17 (points to self)
 * | t_infomask2 = 5  | <- 5 columns
 * | t_infomask = 0x102| <- Has nulls, xmin committed
 * | t_hoff = 24      | <- Header is 24 bytes
 * +------------------+
 * | null bitmap      | <- 1 byte: which columns are null
 * | padding          | <- Alignment padding
 * +------------------+
 * | column data...   | <- Actual row data
 * +------------------+
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/* PostgreSQL Transaction ID Comparison
 * 
 * XIDs are compared using 32-bit modular arithmetic.
 * XID space is conceptually circular, like a clock.
 * 
 * For two XIDs A and B:
 * - A is "before" B if (int32)(A - B) < 0
 * - A is "after" B if (int32)(A - B) > 0
 * 
 * This means:
 * - We can compare XIDs up to ~2 billion apart
 * - XIDs more than ~2B apart give incorrect comparisons
 * - This is why XID wraparound is dangerous!
 */
 
#define TransactionIdPrecedes(id1, id2)     ((int32) ((id1) - (id2)) < 0)
 
#define TransactionIdFollows(id1, id2)     ((int32) ((id1) - (id2)) > 0)
 
/* Example:
 * Current XID: 4,000,000,000 (near max)
 * 
 * Comparing 4,000,000,000 with 100:
 * (int32)(4000000000 - 100) = 3999999900
 * 3999999900 > 0, so 4B is "after" 100... 
 * 
 * BUT if they were 2B+ apart due to wraparound,
 * comparison becomes unreliable!
 * 
 * This is why we must freeze old tuples before wraparound.
 */
 
/* XID "distance" check - used for freeze threshold */
#define TransactionIdIsOlder(id, epoch, current, current_epoch)     ( ((current_epoch) > (epoch)) ||       ((current_epoch) == (epoch) &&        TransactionIdPrecedes((id), (current))) )
 
/* The visibility logic fundamentally relies on correct XID ordering.
 * If XID comparison breaks, MVCC visibility breaks!
 * 
 * PostgreSQL prevents this with:
 * 1. VACUUM freezing old XIDs to FrozenTransactionId
 * 2. Blocking new transactions if too old unfrozen XIDs exist
 * 3. Autovacuum to_prevent_wraparound monitoring
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

// Hint Bits Optimization Logic
 
function check_xmin_committed(tuple: HeapTuple) -> Boolean:
    // Fast path: hint bit already set
    if tuple.t_infomask & HEAP_XMIN_COMMITTED:
        return true
    
    if tuple.t_infomask & HEAP_XMIN_INVALID:
        return false
    
    // Slow path: must check pg_xact
    xmin = tuple.t_xmin
    status = pg_xact_lookup(xmin)
    
    // Set hint bit to avoid future lookups
    if status == COMMITTED:
        tuple.t_infomask |= HEAP_XMIN_COMMITTED  // Dirty the page!
        return true
    else if status == ABORTED:
        tuple.t_infomask |= HEAP_XMIN_INVALID    // Dirty the page!
        return false
    else:
        // Still in progress - can't set hint bit yet
        return false
 
/*
 * Performance Impact Example:
 * 
 * Scenario: SELECT * FROM large_table; (1 million rows)
 * 
 * WITHOUT hint bits:
 * - 1M pg_xact lookups per query execution
 * - Even with caching, significant overhead
 * 
 * WITH hint bits (after first scan):
 * - First scan: 1M pg_xact lookups, sets 1M hint bits
 * - Subsequent scans: 0 pg_xact lookups!
 * - Just check the bits in the already-fetched tuple header
 * 
 * Trade-off:
 * - Setting hint bits dirties pages (even for reads!)
 * - This can increase WAL traffic and checkpoint pressure
 * - But saves far more I/O on repeated accesses
 */

VACUUM Process Flow (Simplified)
 
Phase 1: Heap Scan
─────────────────────────────────────────────────────────────
For each page in the table:
  1. Acquire cleanup lock on page (allows concurrent reads)
  2. Scan all tuples on page
  3. For each tuple:
     - Check visibility to OldestXmin (oldest active snapshot)
     - If dead (not visible to any snapshot):
       * Add to dead tuple list
     - If old (xmin < freeze threshold):
       * Consider freezing (replacing xmin with FrozenTransactionId)
  4. If any dead tuples found on page:
     - Add page to list for Phase 2
 
Phase 2: Index Vacuuming (if indexes exist)
─────────────────────────────────────────────────────────────
For each index on the table:
  1. Scan entire index
  2. Find entries pointing to dead tuple locations
  3. Remove those index entries
  
Note: This is expensive! B-tree scan of entire index.
      Reason vacuum with many dead tuples is costly.
 
Phase 3: Heap Vacuuming  
─────────────────────────────────────────────────────────────
For each page with dead tuples:
  1. Acquire exclusive lock on page
  2. Remove dead tuples from page
  3. Defragment page (optional, for contiguous free space)
  4. Update Free Space Map
 
Phase 4: Truncation (if enabled)
─────────────────────────────────────────────────────────────
If last N pages are completely empty:
  1. Acquire exclusive lock on those pages
  2. Truncate file to remove empty trailing pages
  3. Return space to filesystem
 
Phase 5: Cleanup
─────────────────────────────────────────────────────────────
1. Update visibility map for all-visible pages
2. Update table's relfrozenxid in pg_class
3. Write statistics to pg_stat tables

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

-- Autovacuum Trigger Formula
 
-- VACUUM triggered when:
-- dead_tuples > autovacuum_vacuum_threshold + 
--               (autovacuum_vacuum_scale_factor * n_live_tup)
 
-- Default values:
-- autovacuum_vacuum_threshold = 50
-- autovacuum_vacuum_scale_factor = 0.2 (20%)
 
-- Example: Table with 100,000 live tuples
-- Threshold = 50 + (0.2 * 100,000) = 20,050 dead tuples
 
-- ANALYZE triggered when:
-- changes > autovacuum_analyze_threshold + 
--           (autovacuum_analyze_scale_factor * n_live_tup)
 
-- For large tables, 20% is too high!
-- Table with 100 million rows: needs 20 million dead tuples
-- This could mean GBs of bloat before vacuum triggers
 
-- Recommended: Lower scale_factor for large tables
ALTER TABLE huge_table SET (
    autovacuum_vacuum_scale_factor = 0.01,  -- 1% instead of 20%
    autovacuum_analyze_scale_factor = 0.005  -- 0.5%
);
 
-- Or use flat thresholds for very large tables
ALTER TABLE huge_table SET (
    autovacuum_vacuum_threshold = 10000,
    autovacuum_vacuum_scale_factor = 0.0
);
-- Triggers after 10,000 dead tuples regardless of table size
 
-- Check current settings for a table
SELECT 
    n.nspname,
    c.relname,
    pg_table_size(c.oid) as table_size,
    c.reloptions  -- Shows table-specific autovacuum settings
FROM pg_class c
JOIN pg_namespace n ON n.oid = c.relnamespace
WHERE c.relname = 'my_table';

Visibility Map Structure
 
Heap File: my_table (8KB pages)
┌────────────────────────────────────────────────────────────┐
│ Page 0  │ Page 1  │ Page 2  │ Page 3  │ Page 4  │ ...      │
│ Mixed   │ All-Vis │ All-Frz │ Mixed   │ All-Vis │          │
└────────────────────────────────────────────────────────────┘
     ↑         ↑         ↑         ↑         ↑
     │         │         │         │         │
Visibility Map File: my_table_vm
┌─────────────────────────────────────────┐
│ Bits: 00 │ 01 │ 11 │ 00 │ 01 │ ...      │
│     page0  page1  page2  page3  page4   │
└─────────────────────────────────────────┘
 
Bit meanings:
00 = Mixed: Page has dead tuples or recent changes, needs full check
01 = All-Visible: All tuples visible, but some not frozen
11 = All-Frozen: All tuples visible AND frozen
 
Benefits:
 
1. Index-Only Scans:
   - If VM bit is set, no need to visit heap to check visibility
   - Just return data from index directly
   - Massive speedup for covered indexes!
 
2. VACUUM Optimization:
   - Can skip all-frozen pages entirely
   - Can skip all-visible pages (unless freezing needed)
   - Dramatically faster VACUUM for stable tables
 
3. VACUUM FREEZE Optimization:
   - Only processes pages without all-frozen bit
   - Stable data only frozen once, then skipped forever
 
Example Query Optimization:
─────────────────────────────────────────
Query: SELECT indexed_col FROM table WHERE indexed_col = 'foo'
 
Without VM (or VM bit not set):
1. Search index → find heap page 5, item 3
2. Fetch heap page 5
3. Check visibility of item 3
4. Return if visible
 
With VM (bit set for page 5):
1. Search index → find heap page 5, item 3
2. Check VM for page 5 → all-visible!
3. Skip heap fetch, return directly from index
   ← Heap I/O eliminated!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

-- Index-Only Scan Example
 
-- Create a covering index
CREATE INDEX idx_orders_covering ON orders (customer_id) 
INCLUDE (order_date, total_amount);
 
-- This query can be satisfied entirely from the index
-- if visibility map bits are set
EXPLAIN ANALYZE
SELECT customer_id, order_date, total_amount 
FROM orders 
WHERE customer_id = 12345;
 
/*
Plan with good VM coverage:
 Index Only Scan using idx_orders_covering on orders
   Index Cond: (customer_id = 12345)
   Heap Fetches: 0  ← All pages were all-visible!
   
Plan with poor VM coverage (after many updates):
 Index Only Scan using idx_orders_covering on orders
   Index Cond: (customer_id = 12345)  
   Heap Fetches: 847  ← Had to check heap visibility
*/
 
-- Check VM coverage for a table
SELECT 
    relname,
    pg_size_pretty(pg_relation_size(oid)) as table_size,
    pg_size_pretty(pg_relation_size(reltoastrelid)) as toast_size,
    pg_stat_get_live_tuples(oid) as live_tuples,
    pg_stat_get_dead_tuples(oid) as dead_tuples,
    pg_stat_get_mod_since_analyze(oid) as mods_since_analyze
FROM pg_class 
WHERE relname = 'orders';
 
-- After VACUUM, VM bits will be set for all-visible pages
VACUUM orders;
 
-- Re-run query, observe "Heap Fetches: 0"