Databases — What They Are and How They Work Internally

B-tree page structure (PostgreSQL uses 8 KB pages):

  Root page (level 3)
    ├── Internal page A (level 2) — covers order_id 1–5,000,000
    │     ├── Internal page A1 (level 1) — covers 1–500,000
    │     │     ├── Leaf page 1 — rows: order_id 1–100
    │     │     ├── Leaf page 2 — rows: order_id 101–200
    │     │     └── ...
    │     └── Internal page A2 — covers 500,001–1,000,000
    └── Internal page B (level 2) — covers 5,000,001–10,000,000

Leaf pages contain the actual row data (or pointers to it).
Internal pages contain only keys and child page pointers.

What this means for operations:
  READ by primary key (order_id = 9284751):
    Root → Internal page → Leaf page → row found
    = 3–4 page reads regardless of table size (O log n)
    At 100M rows, still only 4 page reads. Fast.

  FULL TABLE SCAN (no WHERE clause or non-indexed column):
    Must read ALL leaf pages sequentially
    100M rows × 100 rows/page = 1M page reads. Slow.

  UPDATE existing row:
    Find the page (3–4 reads), modify the value in-place,
    write the page back. Fast for individual updates.

  INSERT new row:
    Find the correct leaf page, insert in sorted order.
    If page is full → page split (expensive operation).

LSM-tree write path (Cassandra, RocksDB, HBase):

  WRITE (INSERT or UPDATE order 9284751):
    1. Write to in-memory buffer (MemTable)          ← very fast
    2. Append to Write-Ahead Log (for crash safety)   ← sequential write
    3. Return success to client                       ← done, no disk random write

  BACKGROUND (when MemTable fills up):
    4. Flush MemTable to disk as new SSTable file     ← immutable sorted file
    5. Periodically COMPACT multiple SSTables         ← merge + remove old versions
       into fewer, larger sorted files

RESULT of multiple updates to same key:
  SSTable 1 (oldest): {order_id: 9284751, status: "placed"}
  SSTable 2:          {order_id: 9284751, status: "confirmed"}
  SSTable 3 (newest): {order_id: 9284751, status: "delivered"}

  READ order 9284751: check MemTable first,
  then SSTables newest-to-oldest, return first match found.
  Bloom filters on each SSTable tell you if key exists
  without reading the whole file.

TRADE-OFFS vs B-tree:
  ✓ Writes are much faster (sequential append, no page splits)
  ✓ Better write throughput at high velocity
  ✗ Reads are slower (check multiple SSTables)
  ✗ Compaction consumes background CPU and I/O
  ✗ Space amplification (same data in multiple SSTables until compaction)

Best for: write-heavy workloads, time-series data, IoT streams, Kafka consumer state

Table: orders (100 million rows)
Index: idx_orders_city ON orders(city)

INDEX STRUCTURE (simplified):
  Root page:  [Chennai | Hyderabad | Mumbai]
                  ↓           ↓          ↓
  Level 1: [Ahm..Che] [Hy..Mum] [Mum..Pun] [Pun..Vis]
                                     ↓
  Leaf pages: [Mumbai row_ptr_1, Mumbai row_ptr_2, ...]
              [Mumbai row_ptr_3, Mumbai row_ptr_4, ...]

QUERY: SELECT * FROM orders WHERE city = 'Mumbai'

EXECUTION WITH INDEX:
  1. Read root page → navigate right subtree (Mumbai > Hyderabad)
  2. Read level-1 internal page → find leaf page range for Mumbai
  3. Read first leaf page → find first Mumbai entry + row pointer
  4. Follow row pointer → read actual table page for this row
  5. Continue through leaf pages until city > 'Mumbai'

  Total: ~4 index pages + N data pages (one per matching row)
  For 50,000 Mumbai orders in 100M rows: ~50,004 page reads

QUERY WITHOUT INDEX:
  Full table scan: 100,000,000 rows / 100 rows per page = 1,000,000 page reads
  With index: ~50,004 page reads
  Speedup: ~20× for this query

RANGE QUERY benefit:
  SELECT * FROM orders WHERE city = 'Mumbai' AND amount > 500
  Index on city narrows to Mumbai rows, then filters amount.
  Index on (city, amount) composite — narrows to both criteria in one pass.

Buffer pool: 4 GB RAM allocated to PostgreSQL shared_buffers

State before a query runs:
  Buffer pool (4 GB): [page_1847, page_9234, page_2341 ... 500,000 pages cached]

QUERY: SELECT * FROM orders WHERE order_id = 9284751

Step 1: Query executor needs leaf page of orders index (page_8823)
  → Check buffer pool: page_8823 is in cache? YES → cache hit
  → Read from RAM: ~100 nanoseconds

Step 2: Follow row pointer to data page (page_44219)
  → Check buffer pool: page_44219 in cache? NO → cache miss
  → Read from disk: ~1 millisecond (10,000× slower than RAM)
  → Load page_44219 into buffer pool (evict least-recently-used page)

Step 3: Return row data to client

BUFFER POOL EVICTION (when cache is full):
  PostgreSQL uses Clock Sweep (approximate LRU):
    Each page has a usage counter
    Pages used recently have higher counters
    When eviction needed, scan and evict first page with counter = 0
    Dirty pages (modified but not yet written to disk) must be flushed
    before eviction — adds latency

WHY THIS MATTERS FOR DATA ENGINEERS:
  When you run a large analytical query on a production OLTP database,
  it reads millions of pages from disk into the buffer pool.
  This EVICTS the hot pages that application queries use frequently.
  After your analytical query, every application query hits cache misses
  until the buffer pool refills with hot pages.
  
  Result: you ran a "read-only" analytical query and slowed down
  the production application for the next 10–30 minutes.
  This is why analytical queries must NOT run on production databases.

Buffer pool hit ratio = (cache hits) / (cache hits + cache misses) × 100%

-- PostgreSQL: check buffer pool hit ratio
SELECT
    sum(heap_blks_hit) AS cache_hits,
    sum(heap_blks_read) AS disk_reads,
    ROUND(
        sum(heap_blks_hit)::numeric /
        NULLIF(sum(heap_blks_hit) + sum(heap_blks_read), 0) * 100, 2
    ) AS hit_ratio_pct
FROM pg_statio_user_tables;

Interpreting the result:
  > 99%  → Excellent. Frequently-accessed data is in memory.
  95–99% → Good. Some disk reads, acceptable for mixed workloads.
  90–95% → Warning. Significant disk I/O. Consider increasing shared_buffers.
  < 90%  → Problem. Most queries hit disk. Database is I/O bound.
            Either increase RAM, reduce working set size, or both.

Real impact of hit ratio on query latency:
  99% hit ratio:  average page read = 100ns×0.99 + 1ms×0.01 = ~10 μs
  95% hit ratio:  average page read = 100ns×0.95 + 1ms×0.05 = ~50 μs
  80% hit ratio:  average page read = 100ns×0.80 + 1ms×0.20 = ~200 μs
  50% hit ratio:  average page read = 100ns×0.50 + 1ms×0.50 = ~500 μs

WITHOUT WAL (naive approach):
  UPDATE orders SET status = 'delivered' WHERE order_id = 9284751

  1. Find the data page containing order 9284751 (random read)
  2. Modify the status value in the page in buffer pool
  3. Write the modified page to its original disk location (random write)
  4. Return success to application

  Problem: step 3 is a random write — slow.
  If crash between step 2 and step 3: data change is LOST.

WITH WAL (actual approach — PostgreSQL, MySQL, SQL Server):
  1. Find the data page (random read → probably buffer pool hit)
  2. Write WAL record to WAL file (sequential append — very fast):
     {txn_id: 847291, operation: UPDATE, table: orders,
      old: {status: "confirmed"}, new: {status: "delivered"},
      row_pointer: page_44219/slot_7}
  3. Flush WAL file to disk (fsync — ensures durability)
  4. Modify the page in buffer pool (in memory only, not yet on disk)
  5. Return success to application ← WAL guarantees durability

  Data page will be written to disk LATER during checkpoint.
  If crash before checkpoint: replay WAL at startup → data recovered.
  WAL write is sequential → fast even under high write load.

WAL record contains everything needed to reproduce or reverse a change:
  - Transaction ID
  - Table and page location
  - Before image (old values) — used for rollback and MVCC
  - After image (new values) — used for redo on crash recovery

PostgreSQL WAL record (internal binary format):
  {lsn: 0/1A3F2B8, txn: 847291, op: UPDATE, rel: orders,
   old: {order_id:9284751, status:"confirmed"},
   new: {order_id:9284751, status:"delivered"}}

Debezium decodes WAL → structured Kafka event:
{
  "before": {
    "order_id": 9284751,
    "status": "confirmed"
  },
  "after": {
    "order_id": 9284751,
    "status": "delivered"
  },
  "op": "u",                    ← u=update, c=create, d=delete
  "ts_ms": 1710698072847,       ← timestamp of the change
  "source": {
    "db": "production",
    "table": "orders",
    "lsn": 28437128,            ← log sequence number (position in WAL)
    "txId": 847291
  }
}

This Kafka event is published to topic "production.public.orders"
Any consumer (data pipeline, search indexer, cache invalidator)
can subscribe and react to every database change in near-real-time.

Latency: change committed in PostgreSQL → Kafka event available
         typically 50–500 milliseconds
         
Key benefit for data engineers: your data lake sees every change
within seconds, not the next morning's batch.

PostgreSQL MVCC mechanism:

Every row has two hidden fields:
  xmin: transaction ID that created this row version
  xmax: transaction ID that deleted this row version (0 if not deleted)

Timeline:
  T=100 (txn 100): INSERT order {id:9284751, status:'placed'}
    Row: {id:9284751, status:'placed',  xmin:100, xmax:0}

  T=200 (txn 200): UPDATE status = 'confirmed'
    OLD row: {id:9284751, status:'placed',    xmin:100, xmax:200}  ← marked deleted
    NEW row: {id:9284751, status:'confirmed', xmin:200, xmax:0}    ← new version

  T=300 (txn 300): UPDATE status = 'delivered'
    OLD row: {id:9284751, status:'confirmed', xmin:200, xmax:300}  ← marked deleted
    NEW row: {id:9284751, status:'delivered', xmin:300, xmax:0}    ← current version

  All three versions exist on disk simultaneously!

NOW: two concurrent queries run at T=250:

  QUERY A (analyst, started before txn 300):
    Snapshot: sees all transactions committed before T=250
    Sees: status='confirmed' (txn 200 committed, txn 300 not yet)
    Returns: 'confirmed'

  QUERY B (application write, started at T=300):
    Sees: status='delivered' (txn 300 committed)
    Returns: 'delivered'

NEITHER QUERY BLOCKED THE OTHER.
Readers see a consistent point-in-time snapshot.
Writers create new row versions, not locking old ones.

This is why SELECT queries in PostgreSQL never block UPDATE queries
and UPDATE queries never block SELECT queries.

VACUUM: old row versions are eventually cleaned up by the
        background VACUUM process once no transaction can see them.
        Without VACUUM, the table grows forever (table bloat).

SQL string: SELECT c.name, SUM(o.amount) as total
            FROM orders o
            JOIN customers c ON o.customer_id = c.id
            WHERE o.created_at >= '2026-01-01'
            GROUP BY c.name
            ORDER BY total DESC
            LIMIT 10

STEP 1: PARSING
  Lexer tokenises: [SELECT, c.name, SUM, (, o.amount, ), ...]
  Parser builds Abstract Syntax Tree (AST)
  Validates syntax — catches typos, missing clauses

STEP 2: SEMANTIC ANALYSIS
  Resolves table and column names against catalog
  Validates types: created_at >= '2026-01-01' — date comparison valid?
  Expands SELECT * to explicit column names if needed

STEP 3: LOGICAL PLAN
  Relational algebra tree — what to compute, not how:
    Limit(10)
      Sort(total DESC)
        Aggregate(GROUP BY c.name, SUM(o.amount))
          Join(o.customer_id = c.id)
            Filter(o.created_at >= '2026-01-01')
              Scan(orders)
            Scan(customers)

STEP 4: OPTIMISATION (the most important step)
  Query optimizer rewrites the logical plan for efficiency:
    - Push filters DOWN before joins (filter orders before joining customers)
    - Choose join algorithm: hash join? merge join? nested loop?
    - Choose index scans vs sequential scans based on statistics
    - Decide join order (smaller table first)
  
  Statistics used: row counts, column cardinality, value distributions
  Optimizer estimates cost of each plan in abstract "cost units"
  Chooses plan with lowest estimated cost

STEP 5: PHYSICAL PLAN
  Concrete execution plan with specific algorithms:
    Limit
      Sort (external sort — result too large for memory)
        HashAggregate (hash table for GROUP BY)
          Hash Join (hash customers table, probe with filtered orders)
            Index Scan on idx_orders_created_at (filter pushdown)
            Sequential Scan on customers

STEP 6: EXECUTION
  Each node in the plan pulls rows from its children (volcano model)
  Rows flow up the plan from leaf nodes to the root
  Result returned to client

To see the plan PostgreSQL chose:
  EXPLAIN ANALYZE SELECT ... (same query)
  Shows: plan nodes, estimated vs actual rows, actual timing per node

EXPLAIN ANALYZE
  SELECT * FROM orders WHERE city = 'Bangalore' AND amount > 1000;

Output:
  Bitmap Heap Scan on orders  (cost=892.14..4821.33 rows=12847 width=89)
                               (actual time=12.847..89.234 rows=13102 loops=1)
    Recheck Cond: (city = 'Bangalore')
    Filter: (amount > 1000::numeric)
    Rows Removed by Filter: 28432
    ->  Bitmap Index Scan on idx_orders_city
                             (cost=0.00..888.93 rows=41279 width=0)
                             (actual time=11.234..11.234 rows=41534 loops=1)
          Index Cond: (city = 'Bangalore')
  Planning Time: 0.847 ms
  Execution Time: 94.127 ms

HOW TO READ THIS:
  "cost=892.14..4821.33" → estimated cost (startup..total) in arbitrary units
  "rows=12847"           → estimated number of rows (optimizer's guess)
  "actual time=12.847..89.234" → actual timing in milliseconds
  "rows=13102"           → actual rows returned (compare to estimate!)
  "Rows Removed by Filter: 28432" → 28k rows passed index but failed amount filter

KEY INSIGHT from this output:
  The index returned 41,534 rows for city='Bangalore'
  But only 13,102 had amount > 1000 (filter removed 28,432)
  
  This means a composite index on (city, amount) would be better:
  CREATE INDEX idx_orders_city_amount ON orders(city, amount);
  New plan would return only ~13,102 rows from the index directly,
  skipping the 28,432 wasted reads.

Warning sign: estimated rows vs actual rows differ by 10×+
  Means statistics are stale → run ANALYZE to update them

Your daily ingestion pipeline pulls the last 24 hours of transactions from PostgreSQL. It runs every morning at 5 AM and normally finishes in 18 minutes. This morning it ran for 3 hours and is still going when you arrive at 9 AM. Nothing in the pipeline code changed. What happened?

Step 1 — Check if the query is running: You connect to PostgreSQL and run SELECT pid, query, state, wait_event_type, wait_event, query_start FROM pg_stat_activity. You find your ingestion query in the "active" state with wait_event_type = "Lock". It is waiting for a lock.

Step 2 — Find the blocking query: You run SELECT * FROM pg_blocking_pids(pid) on your ingestion process. It returns a PID. You check that PID — it is a transaction started at 11 PM last night (10 hours ago) by a developer running an ad-hoc UPDATE statement that never committed. It has been sitting with an open transaction, holding row locks, for 10 hours.

Step 3 — Understand why this blocked you: Your ingestion query uses REPEATABLE READ isolation and was waiting for consistent snapshot data. The open transaction was holding locks on rows your query needed to read, causing a lock wait. This is the isolation mechanism working as designed — protecting you from reading uncommitted data — but the developer's abandoned transaction is blocking the entire pipeline.

Step 4 — Resolution: You confirm with the developer that the transaction can be safely terminated (it was a test query that was never meant to stay open). You run SELECT pg_terminate_backend(pid). The blocking transaction is terminated, the row locks are released, and your ingestion pipeline completes in 19 minutes.

The fix going forward: You set idle_in_transaction_session_timeout = '30min' on the PostgreSQL server — any transaction that sits idle for more than 30 minutes without executing a query is automatically terminated. This prevents a single forgotten developer query from blocking production pipelines overnight.

This scenario plays out at real companies regularly. The data engineer who understands database internals — transactions, locks, MVCC, pg_stat_activity — diagnoses and resolves it in 20 minutes. The one who does not spends hours restarting the pipeline, escalating to DBAs, and not understanding why.