Phase 1 · Chapter 3

Inside the Database

How Postgres actually stores, finds, and protects your data

What this chapter does to you: After this, you will never write a query without knowing what Postgres is doing physically to execute it. Slow queries, missing indexes, locking bugs, transaction isolation failures — all of these will have an obvious cause and an obvious fix. This is the chapter that separates engineers who "use a database" from engineers who "understand a database."

The Setup: What Postgres Actually Is

Postgres is a process running on your Hetzner server. It has:

• Its own RAM allocation (the shared_buffers — a cache of disk pages)
• Files on disk where your actual data lives
• A pool of worker processes, one per connection
• A Write-Ahead Log (WAL) — the most important file you've never looked at

When you write SELECT * FROM tests WHERE user_id = 'abc', a chain of events happens inside Postgres that most engineers have never traced. We're going to trace it.

But first — how is data stored physically?

Part 1: How Postgres Stores Data on Disk

Pages — The Unit of Everything

Postgres never reads or writes individual rows. It reads and writes pages.

A page is exactly 8 kilobytes. Everything in Postgres — tables, indexes, everything — is stored as a sequence of 8KB pages on disk.

When Postgres needs a row, it:

1. Figures out which page that row lives on
2. Reads the entire 8KB page from disk into RAM (into shared_buffers)
3. Finds the row within that page
4. Returns it

This is why reading one row from a cold database still incurs the cost of reading an 8KB page. You never get less than a page.

The physical layout of one page:

┌─────────────────────────────────────────────┐
│  Page Header (24 bytes)                      │
│  — LSN (Log Sequence Number, for WAL)        │
│  — page version, checksum                    │
├─────────────────────────────────────────────┤
│  Item Pointers (array of small offsets)      │
│  — pointer 1 → row 1's location in page     │
│  — pointer 2 → row 2's location in page     │
│  — pointer 3 → (empty, row was deleted)     │
│  — ...                                       │
├─────────────────────────────────────────────┤
│  Free Space (middle of the page)             │
├─────────────────────────────────────────────┤
│  Row 3 data (grows upward from bottom)       │
│  Row 2 data                                  │
│  Row 1 data                                  │
└─────────────────────────────────────────────┘

Item pointers grow downward from the top. Row data grows upward from the bottom. They meet in the middle when the page is full.

Why this layout matters: When you delete a row, Postgres doesn't immediately reclaim that space. It marks the item pointer as dead and marks the row as invisible to future transactions. The space is wasted — called bloat — until VACUUM runs. We'll get to VACUUM shortly.

The Heap File — Your Table on Disk

Your tests table is stored as a heap file — a sequence of 8KB pages in a file on disk. The file is literally named after the table's internal OID (object ID): something like /var/lib/postgresql/data/base/16384/24601.

The word "heap" here means unordered. Rows are not sorted by any column. They're just appended wherever there's space on the most recent page.

This is crucial to understand: a table has no natural order. When you write SELECT * FROM tests without ORDER BY, you might get rows in any order. Not insertion order. Not any predictable order. Whatever page Postgres reads first.

The implication: If you need rows in order, you must say so explicitly with ORDER BY. Postgres will never give you a sorted result unless you ask for one.

TOAST — What Happens to Big Data

8KB pages have a problem: what if a single row is larger than 8KB? A user bio with 50KB of text. A JSON blob. A test question with base64-encoded images.

Postgres solves this with TOAST (The Oversized-Attribute Storage Technique).

When a field value is too large to fit in a page, Postgres automatically:

1. Compresses it (if that makes it small enough)
2. If still too large, slices it into ~2KB chunks
3. Stores those chunks in a separate hidden TOAST table
4. Stores a pointer to those chunks in the main row

Your query still returns the full value — Postgres assembles it transparently. But the cost is real: fetching a TOASTed value requires reading from two tables instead of one.

The practical lesson: Don't store large blobs (PDFs, images) as Postgres columns. Store them in Cloudflare R2 (which you already do). Store the URL in Postgres. This isn't just about storage cost — it's about page efficiency and query speed.

Part 2: Indexes — The Data Structure You Need to Draw

First: What Happens Without an Index

Your submissions table has 5 million rows. You run: SELECT * FROM submissions WHERE user_id = 'abc123'.

Without an index, Postgres must do a sequential scan (seq scan):

Read page 1   → check every row → any match? keep it
Read page 2   → check every row → any match? keep it
Read page 3   → check every row → any match? keep it
...
Read page 625,000 → check every row → done

5 million rows ÷ ~100 rows per page = ~50,000 pages read. At ~0.1ms per page disk read = 5 seconds for a single query. At 100 concurrent users = your database is on fire.

This is what "missing index" actually means physically: Postgres has to read every single page of your table to answer a simple lookup.

The B-Tree Index — Draw This in Your Head

The default Postgres index type is a B-tree (Balanced Tree).

Let's build one from scratch for user_id.

Imagine you have 8 user IDs and you want to find any one of them fast:

Without index (list of values, unsorted):
  abc, xyz, def, mno, pqr, ghi, uvw, jkl
  To find "ghi": check abc, xyz, def, mno, pqr — found it at position 6. Linear search.

With B-tree index (sorted, hierarchical):

                    [mno]
                   /     \
            [def,ghi]   [pqr,uvw]
           /   |   \   /   |    \
         abc  def  ghi  mno  pqr  uvw
              ↑         ↑
          (leaf nodes — each points to the actual row's location on disk)

To find "ghi":

1. Start at root: is "ghi" < "mno"? Yes → go left
2. Internal node [def, ghi]: is "ghi" ≥ "def" and ≤ "ghi"? Yes → go to ghi leaf
3. Leaf node: here's the pointer — "ghi" lives on page 4821, slot 3

3 steps to find 1 record in 8. With 5 million records, a B-tree is about 20 levels deep — still only ~20 page reads to find any single row. Compare to 50,000 page reads for a seq scan.

This is the whole magic. The B-tree is always balanced — every leaf is the same distance from the root. Finding any value takes the same number of steps: log₂(N) where N is the number of rows. For 5 million rows: log₂(5,000,000) ≈ 22 steps.

What a B-Tree Index Actually Stores

An index is a separate file on disk. It's not part of your table's heap file.

Each index entry stores:

• The indexed column value (e.g., 'abc123')
• A TID (Tuple ID) — a physical pointer to the row: page number + slot number

When Postgres uses your index:

1. Binary search through the B-tree index pages: ~3-20 page reads
2. Find the TID for your value
3. Jump directly to that page + slot in the heap file: 1 page read

Total: 4-21 page reads instead of 50,000. This is why indexes matter.

Composite Indexes — When One Column Isn't Enough

Your query: SELECT * FROM submissions WHERE user_id = 'abc' AND test_id = 'xyz'

An index on just user_id will:

1. Find all rows where user_id = 'abc' (maybe 500 rows)
2. Postgres then filters those 500 rows for test_id = 'xyz' — without an index on test_id, it reads all 500 rows' heap pages

A composite index on (user_id, test_id):

1. Finds the exact leaf node for ('abc', 'xyz') in one B-tree traversal
2. Returns the one (or few) matching TIDs directly

The critical rule about composite indexes: The order of columns in the index matters. An index on (user_id, test_id):

• ✅ Can be used for: WHERE user_id = ?
• ✅ Can be used for: WHERE user_id = ? AND test_id = ?
• ❌ Cannot be used for: WHERE test_id = ? (alone)

Why? Because the B-tree is sorted first by user_id, then by test_id within the same user_id. If you search by test_id alone, you'd have to scan every node — defeating the purpose.

The left-prefix rule: You can use any left-prefix of a composite index. Index on (a, b, c) can serve queries on a, a+b, or a+b+c. Not b, not c, not b+c.

When Postgres Ignores Your Index

Here is the thing that surprises most engineers:

Postgres sometimes ignores a valid index and does a sequential scan instead.

This is not a bug. It's the query planner being smarter than you.

Postgres keeps statistics about your data (run ANALYZE to refresh them). It knows:

• How many rows are in the table
• How many distinct values each column has
• How data is distributed

If your query would return 40% of the table's rows, using the index is actually slower than a sequential scan. Here's why:

• Index scan: for each of 2 million matching rows, read its specific heap page. If rows are spread across 40,000 pages, that's 40,000 random disk reads.
• Sequential scan: read all 50,000 pages in order — sequential reads are dramatically faster than random reads because the OS can prefetch them.

Postgres calculates the cost of each approach and picks the cheaper one. This is the query planner — the component that turns your SQL into an execution plan.

The practical lesson: If your query is slow and EXPLAIN shows a seq scan on a column that has an index, first check: how many rows does the query return? If it's a large fraction of the table, Postgres is probably right. If it's a small fraction, your statistics might be stale (run ANALYZE) or the index might not be matching your query's shape.

The Index Types You Should Know

B-tree (default): For equality and range queries. =, <, >, BETWEEN, LIKE 'prefix%'. Use for everything unless you have a specific reason not to.

Hash index: For equality only (=). Slightly faster than B-tree for pure equality. Can't do range queries. Rarely used in practice because B-tree is fast enough.

GIN (Generalized Inverted Index): For full-text search, arrays, JSONB. When you do WHERE tags @> ARRAY['math', 'physics'], a GIN index makes this fast. If you have JSONB columns you search inside, you need GIN.

GiST: For geometric data, full-text search (tsvector). Less common unless you're doing geographic queries.

Partial index: An index on a subset of rows. CREATE INDEX idx_active_users ON users(email) WHERE deleted_at IS NULL — only indexes rows where deleted_at IS NULL. Smaller, faster, perfect for "find active users by email" queries.

Expression index: An index on a computed expression. CREATE INDEX idx_lower_email ON users(LOWER(email)) — makes WHERE LOWER(email) = LOWER($1) use an index instead of a seq scan.

Part 3: Transactions and ACID

The Problem Without Transactions

You're processing a test submission on AttemptIQ. Your code does:

await db.query(`UPDATE submissions SET status='graded' WHERE id=$1`, [id])
await db.query(`INSERT INTO scores (user_id, test_id, score) VALUES ($1,$2,$3)`, [...])
await db.query(`UPDATE user_stats SET tests_completed = tests_completed + 1 WHERE user_id=$1`, [uid])

Your server crashes after the first query.

Now: submission is marked graded, but no score was inserted, and user_stats wasn't updated. Your database is in a partially updated, inconsistent state.

Transactions exist to prevent this.

What BEGIN Actually Does

BEGIN;
  UPDATE submissions SET status='graded' WHERE id=$1;
  INSERT INTO scores (user_id, test_id, score) VALUES ($1,$2,$3);
  UPDATE user_stats SET tests_completed = tests_completed + 1 WHERE user_id=$1;
COMMIT;

When you BEGIN, Postgres gives your connection a transaction ID (XID) and starts tracking every change you make. Those changes are written to the WAL (Write-Ahead Log) on disk before they're applied to the actual data pages.

When you COMMIT, all changes become permanent and visible to other connections.

When you ROLLBACK (or crash), all changes are discarded. The WAL records what to undo.

The physical mechanism of crash safety:

Postgres uses a Write-Ahead Log (WAL). Before any data page is modified, the change is written to the WAL — a sequential log file. Sequential writes are fast.

If Postgres crashes mid-transaction, on restart it reads the WAL and:

• For committed transactions: re-applies any changes not yet written to data pages
• For uncommitted transactions: rolls them back

This is how Postgres guarantees your data survives a crash. Your data pages might be in an inconsistent state after a crash. The WAL is the source of truth for what's real.

ACID — What Each Letter Actually Means Physically

Atomicity: All statements in a transaction succeed, or none do. There is no partial success. Physical mechanism: WAL + rollback log.

Consistency: A transaction takes the database from one valid state to another. Constraints (foreign keys, NOT NULL, UNIQUE) are enforced at commit time. Physical mechanism: constraint checking before COMMIT is allowed.

Isolation: Concurrent transactions don't see each other's uncommitted changes. Physical mechanism: MVCC (see below). This is the most complex one.

Durability: A committed transaction survives crashes. Physical mechanism: WAL is fsynced to disk before COMMIT returns success. When COMMIT returns to your Node.js code, it's physically on disk.

MVCC — The Mechanism Behind Isolation

This is the part most engineers never learn. It explains seemingly mysterious behavior like: "why can two writers not block readers?" and "why does my count() return stale data?"

MVCC = Multi-Version Concurrency Control.

The idea: instead of locking rows so only one person can read/write at a time, Postgres keeps multiple versions of every row.

Each row has hidden system columns:

• xmin — the transaction ID that created this row version
• xmax — the transaction ID that deleted this row version (0 if still alive)

When you update a row, Postgres doesn't modify it in-place. It:

1. Marks the old version as deleted (sets xmax to your transaction ID)
2. Inserts a brand new version of the row (with xmin = your transaction ID)

Both versions exist on disk simultaneously.

How isolation works with MVCC:

When your transaction reads a row, it asks: "which row versions are visible to me?" The answer depends on your isolation level and transaction ID:

A row version is visible to your transaction if:

• xmin committed before your transaction started (so the row existed when you started)
• xmax is 0 or belongs to a transaction that started after you (so the row wasn't deleted yet, from your perspective)

This means:

• You see a consistent snapshot of the database as it was when your transaction started
• Writers inserting/updating rows don't block your reads — they create new row versions
• Your reads don't block writers — you're reading old versions while they write new ones

Readers never block writers. Writers never block readers. This is why Postgres can handle high concurrency without everything grinding to a halt.

The cost: bloat. Old row versions accumulate on pages. They're dead (nobody can see them anymore) but they take space. This is why VACUUM exists.

Isolation Levels — The Tradeoffs

Postgres supports four isolation levels. Most applications use the default (READ COMMITTED) without understanding what they're giving up.

READ COMMITTED (default): Each statement sees data committed before that statement began. A long transaction can see different data in each statement — because other transactions committed between your statements.

BEGIN;
  SELECT COUNT(*) FROM submissions; -- returns 1000
  -- Another transaction inserts 50 rows and commits
  SELECT COUNT(*) FROM submissions; -- returns 1050 !!
COMMIT;

This is called a non-repeatable read. Surprising in analytics queries.

REPEATABLE READ: The entire transaction sees the same snapshot from when it started. No non-repeatable reads. You'll always see 1000 in both counts above. Use this for analytics, reports, any multi-statement read that needs consistency. (It still allows an anomaly called write skew — covered in the Transactions chapter, Phase 2.)

SERIALIZABLE: Transactions behave as if they ran one at a time, in serial order. Prevents all anomalies. Postgres may abort and retry transactions that conflict. Use for financial operations where order matters absolutely.

The rule of thumb for interviews:

• Default CRUD operations: READ COMMITTED is fine
• Analytics/reports: REPEATABLE READ
• Financial transactions: SERIALIZABLE

Part 4: VACUUM — Why Dead Rows Must Be Cleaned

The Problem: Table Bloat

Every UPDATE creates a new row version and marks the old one dead. Every DELETE marks a row dead without removing it.

Over time, your table fills with dead row versions that no transaction can see. They occupy space on pages. They slow down seq scans (more pages to read). Indexes still point to them (must be skipped during scans).

This is bloat. A heavily-updated table can be 3-5x larger than its live data.

What VACUUM Does

VACUUM scans the table, finds dead row versions, marks their space as reusable, and updates the free space map (a tracking structure Postgres uses when inserting new rows).

It does NOT return space to the OS (the file doesn't shrink). It just makes the space available for new rows.

VACUUM FULL reclaims space to the OS, rewrites the entire table, removes bloat completely. But it takes an exclusive lock — nobody can read or write the table while it runs. Use it carefully in production, during maintenance windows.

autovacuum is a Postgres background process that runs VACUUM automatically. It triggers when a table has accumulated enough dead rows (based on thresholds you can configure per-table). For most applications, autovacuum is sufficient.

But autovacuum can fall behind if your write rate is too high. Signs of this:

• Tables growing unexpectedly in disk size
• Query performance degrading over weeks (more pages = slower seq scans)
• pg_stat_user_tables.n_dead_tup climbing endlessly

VACUUM also has a second critical job: updating the transaction ID (XID) visibility horizon. Postgres uses 32-bit XIDs that wrap around at ~2 billion. VACUUM updates relfrozenxid — without it, your database eventually hits transaction ID wraparound and goes into emergency read-only mode. Autovacuum prevents this. Don't disable it.

Part 5: The Query Planner — Reading EXPLAIN

This is the tool that unlocks every performance problem.

When you run a query, Postgres doesn't execute it immediately. First, the query planner:

1. Parses your SQL into an internal tree
2. Considers multiple execution strategies (which index? which join algorithm?)
3. Estimates the cost of each strategy using table statistics
4. Picks the cheapest plan
5. Executes it

EXPLAIN ANALYZE shows you both the plan and the actual execution:

EXPLAIN ANALYZE
SELECT u.name, COUNT(s.id) as test_count
FROM users u
JOIN submissions s ON u.id = s.user_id
WHERE u.created_at > '2024-01-01'
GROUP BY u.id, u.name
ORDER BY test_count DESC
LIMIT 10;

Example output:

Limit  (cost=1240.50..1240.53 rows=10 width=40) (actual time=45.2..45.3 rows=10)
  ->  Sort  (cost=1240.50..1265.50 rows=10000 width=40) (actual time=45.1..45.2 rows=10)
        Sort Key: (count(s.id)) DESC
        ->  HashAggregate  (cost=800.00..900.00 rows=10000 width=40) (actual time=40.1..42.0)
              ->  Hash Join  (cost=150.00..700.00 rows=20000 width=16) (actual time=5.2..30.1)
                    Hash Cond: (s.user_id = u.id)
                    ->  Seq Scan on submissions  (cost=0.00..400.00 rows=20000) (actual time=0.1..15.0)
                    ->  Hash  (cost=100.00..100.00 rows=4000) (actual time=4.9..4.9)
                          ->  Index Scan on users  (cost=0.00..100.00 rows=4000) (actual time=0.1..3.5)
                                Index Cond: (created_at > '2024-01-01')

How to read this:

Read from the innermost (most indented) node outward — that's execution order.

Index Scan on users — Postgres used the index on created_at. Good. Seq Scan on submissions — Postgres read every row of submissions. Is this a problem? Only if submissions is huge and most rows don't match. Check rows — 20,000 returned out of how many total? Run \dt+ in psql to see table sizes.

Hash Join — Postgres built a hash table from users, then scanned submissions and probed the hash. This is the right algorithm for this query shape.

cost=X..Y — estimated cost in abstract units. First number = startup cost (before first row), second = total cost. Higher = more expensive.

actual time=X..Y — actual milliseconds. Compare cost to actual time. If they're wildly different, your statistics are stale — run ANALYZE.

The four execution nodes you'll see most:

Seq Scan — reads every page of the table. Expected for large result sets or small tables. Alarming for small result sets on large tables (missing index).

Index Scan — uses B-tree index, then fetches heap pages for matching rows. Good for low-selectivity queries (few rows match).

Index Only Scan — uses index without fetching heap pages at all. Happens when all needed columns are in the index. Very fast.

Bitmap Heap Scan — a hybrid: builds a bitmap of matching pages from the index, then reads those pages in order (better I/O pattern than random index scan for medium-selectivity queries).

Part 6: Connection Pooling — Why pgBouncer Exists

In Chapter 2 you learned why connection pooling exists — to avoid TCP handshakes. But there's a deeper problem with Postgres specifically.

Each Postgres connection is a separate OS process.

When your Node.js app does new Pool({ max: 20 }), Postgres forks 20 processes. Each process uses ~5-10MB of RAM just for overhead.

At 10 app servers × 20 connections each = 200 Postgres processes = 1-2GB RAM wasted just on connection overhead. Plus, context-switching between 200 processes is expensive.

pgBouncer is a lightweight connection pooler that sits between your app and Postgres:

Your app thinks it has 60 connections. pgBouncer actually maintains only 20-50 connections to Postgres. When your app's connection isn't executing a query, pgBouncer can give that Postgres connection to another app connection.

pgBouncer modes:

Session pooling — one Postgres connection per app session. Not much savings.

Transaction pooling — one Postgres connection per transaction. Connection returned to pool between transactions. This is the mode you want. One Postgres connection can serve dozens of app connections as long as they're not simultaneously in transactions.

Statement pooling — one connection per statement. Can't use multi-statement transactions. Too restrictive for most apps.

The gotcha with transaction pooling: Prepared statements, advisory locks, and SET commands are session-level in Postgres. With transaction pooling, your next transaction might run on a different Postgres connection. So SET search_path = myschema doesn't stick between transactions through pgBouncer. This affects some ORM features. Know your ORM's prepared statement behavior.

Part 7: The Vocabulary Map

Part 8: Practice Problems

Problem 1 (Physical Reasoning): Your submissions table has 10 million rows. You run:

SELECT * FROM submissions WHERE status = 'pending';

This query takes 8 seconds. You add an index on status. It still takes 6 seconds.

Explain why the index barely helped. What is happening physically? What would you do instead? (Hint: how many rows have status = 'pending'?)

Problem 2 (Schema Design): You're designing the AttemptIQ leaderboard query:

SELECT user_id, SUM(score) as total
FROM submissions
WHERE test_id = $1 AND submitted_at > NOW() - INTERVAL '30 days'
GROUP BY user_id
ORDER BY total DESC
LIMIT 10;

What indexes would you create for this query? Write the exact CREATE INDEX statements and explain why each column is in the position it's in.

Problem 3 (MVCC reasoning): Two transactions run simultaneously on AttemptIQ:

Transaction A (analytics job, READ COMMITTED, running for 2 minutes):

BEGIN;
  SELECT COUNT(*) FROM submissions; -- Step 1: returns 100,000
  -- ... does 2 minutes of processing ...
  SELECT COUNT(*) FROM submissions; -- Step 2: what does this return?
COMMIT;

Transaction B (user submitting test, commits after Transaction A's Step 1):

BEGIN;
  INSERT INTO submissions (...) VALUES (...); -- 500 new rows
COMMIT;

What does Transaction A's Step 2 return: 100,000 or 100,500? Why? What if Transaction A used REPEATABLE READ instead?

Problem 4 (Production Debug): Your AttemptIQ app runs fine during the day. Every Sunday at 3am, your DB CPU spikes to 100% for 30 minutes and queries slow to a crawl.

You check pg_stat_activity and see no unusual queries. You check pg_stat_user_tables and notice n_dead_tup is very high on the submissions table Saturday night.

What is happening? Why Sunday 3am? What is the exact Postgres mechanism involved, and what would you change to fix it?

Problem 5 (Index Design — Go Deep): You're told: "never use SELECT *, always specify columns." This is common advice. Explain the specific index mechanism that makes this advice true at the database level — not "it transfers less data over the network" (that's true but trivial). There is a deeper reason involving index scans.

(Hint: what is an Index Only Scan and when can Postgres use it?)

What's Coming in Phase 2

You now know how data gets to your server (Chapter 2) and how it's stored and retrieved (Chapter 3). This chapter gave you a first look at transactions, MVCC, and EXPLAIN. Phase 2 goes deep on exactly those, one chapter each:

• Chapter 1 — Transactions, ACID & isolation levels (including the anomalies the standard table leaves out)
• Chapter 2 — Replication: WAL, lag, and read-your-writes consistency
• Chapter 3 — Sharding: when, how, and what you give up
• Chapter 4 — Query optimisation: reading EXPLAIN ANALYZE like a doctor reads an X-ray

Some of Phase 2 will feel like review. That's on purpose: the second pass is where the details you skimmed here become things you can defend under questioning.

End of Phase 1, Chapter 3. Estimated reading time: 70-90 minutes. Practice problems: 60-90 minutes. Do not proceed to Phase 2 until you can explain MVCC — why readers don't block writers — in plain English without looking at your notes. That concept will appear in every senior backend interview you take.