Mastering Database Internals: Index Architectures, Query Optimization, Concurrency, and Caching

At scale, relational database performance degradation rarely stems from raw storage volume. Rather, it occurs when storage engines are forced into pathological physical access paths: scanning unindexed heap pages, managing lock escalation under concurrent write pressure, or churning through garbage collection across bloated MVCC snapshots.

Scaling relational engines like PostgreSQL and MySQL InnoDB beyond tens of thousands of queries per second requires treating them as deterministic state machines governed by physical I/O constraints, memory-page lifecycles, and algorithmic concurrency controls.

1. Index Internals: B+Tree vs. GiST

Relational storage engines rely on balanced tree structures to bound block I/O. However, the physical layout of the underlying leaf pages dictates how secondary lookups and writes scale.

       [ Root Page ]
      /             \
 [ Internal ]     [ Internal ]
   /      \         /      \
[Leaf]  [Leaf]   [Leaf]  [Leaf]  <---> Bidirectional Linked List

B+Tree: PostgreSQL Heap vs. MySQL Clustered Index

PostgreSQL and MySQL InnoDB default to the B+Tree for scalar ordering, but their underlying storage topologies diverge fundamentally:

• MySQL InnoDB (Clustered Index): Tables are organized around the primary key. Leaf nodes store the actual row tuple. Secondary indexes do not point to physical block addresses; their leaf nodes store the corresponding primary key value. Consequently, a non-covering secondary index lookup requires a secondary traversal—an "index bookmark lookup"—through the primary clustered B+Tree.
• PostgreSQL (Heap Storage with Secondary Indexes): PostgreSQL decouples tables from indexes, storing rows in an unordered heap. Every index—including the primary key—is a secondary index mapping search keys to physical Tuple Identifiers (ctid: page number and slot offset). Updates write a new tuple version to the heap, which updates every secondary index unless PostgreSQL can leverage Heap-Only Tuples (HOT). HOT optimization requires that no indexed columns are modified and the new row version fits inside the original 8KB data page.

The traversal depth of a balanced B+Tree is defined as:

$$h \approx \left\lceil \log_B \left( \frac{N}{L} \right) \right\rceil$$

where $B$ represents the page fanout factor (typically between 100 and 1,000 depending on key size and fill factor), $N$ is total row count, and $L$ is leaf node capacity. A fanout of 200 with an 8KB page size indexes tens of millions of rows within a height of 3 to 4, keeping root and intermediate nodes permanently cached in the buffer pool.

GiST (Generalized Search Tree)

Standard B+Trees fail on non-scalar or multidimensional domains (e.g., geometric polygons, IP ranges, temporal intervals). PostgreSQL’s GiST architecture provides an extensible, balanced tree framework parameterized by user-defined methods: consistent(), union(), compress(), and penalty().

Intermediate nodes store bounding predicates encompassing their child subtrees. When querying overlapping coordinates or timestamp ranges, non-matching branches are pruned without linear page scans:

-- GiST exclusion constraint preventing overlapping reservations
CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE room_reservations (
    room_id INT NOT NULL,
    booked_during TSRANGE NOT NULL,
    EXCLUDE USING gist (room_id WITH =, booked_during WITH &&)
);

2. Query Planner Analysis with EXPLAIN

The cost-based optimizer (CBO) models disk and CPU costs across candidate physical operators. PostgreSQL calculates total plan costs using the following base cost model:

$$\text{Total Cost} = (P \times c_{\text{page}}) + (T \times c_{\text{tuple}}) + (I \times c_{\text{index\_page}}) + (O \times c_{\text{operator}})$$

The balance between seq_page_cost (default 1.0) and random_page_cost (default 4.0) determines whether the planner selects an index path or falls back to a sequential scan. On modern NVMe storage, leaving random_page_cost at 4.0 causes the planner to overestimate random seek costs; reducing it to 1.1–1.5 aligns plan selection with real flash hardware.

EXPLAIN (ANALYZE, BUFFERS, SETTINGS, COSTS)
SELECT u.id, o.total_amount
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE o.created_at >= NOW() - INTERVAL '3 days'
  AND u.status = 'active';

Hash Join  (cost=1240.50..5820.30 rows=1520 width=16) (actual time=1.201..8.412 rows=1450 loops=1)
  Hash Cond: (o.user_id = u.id)
  Buffers: shared hit=342 read=12
  ->  Index Scan using idx_orders_created_at on orders o  (cost=0.42..3120.10 rows=4800 width=16)
        Buffers: shared hit=180 read=10
  ->  Hash  (cost=850.00..850.00 rows=31200 width=8)
        Buckets: 32768  Batches: 1  Memory Usage: 1485kB
        ->  Seq Scan on users u  (cost=0.00..850.00 rows=31200 width=8)
              Filter: (status = 'active'::text)
              Buffers: shared hit=162 read=2

Critical Execution Metrics

• Buffer Misses (read vs. hit): hit indicates the page was resident in shared_buffers. High read counts reveal physical I/O requests handled by the OS page cache or storage hardware.
• Bitmap Index Scan vs. Index Scan: When matching rows are dispersed throughout the table, an Index Scan generates high random I/O. A Bitmap Index Scan instead loads matching block addresses into an in-memory bitmask, sorting heap page access sequentially before executing a Bitmap Heap Scan.

3. High-Volume Table Partitioning

When an index outgrows physical RAM, random B+Tree traversals miss the cache, incurring severe I/O penalties. Declarative table partitioning physically splits a logical relation into distinct physical tables, preserving working-set residency in memory.

CREATE TABLE telemetry_events (
    device_id BIGINT NOT NULL,
    recorded_at TIMESTAMPTZ NOT NULL,
    payload JSONB
) PARTITION BY RANGE (recorded_at);

CREATE TABLE telemetry_events_2026_q1 PARTITION OF telemetry_events
    FOR VALUES FROM ('2026-01-01 00:00:00+00') TO ('2026-04-01 00:00:00+00');

When queries filter on the partition key, the optimizer employs partition pruning during planning and execution, reading only the target partition's index pages.

Partitioning also circumvents maintenance debt. Executing large DELETE queries floods write-ahead logs (WAL) and leaves behind dead tuples that cause index bloat. With partitioning, data retirement is a metadata operation:

ALTER TABLE telemetry_events DETACH PARTITION telemetry_events_2026_q1 CONCURRENTLY;
DROP TABLE telemetry_events_2026_q1;

4. Isolation Levels, MVCC, and Row Locking

Concurrency engines resolve read-write conflicts using Multi-Version Concurrency Control (MVCC), but storage designs differ:

• PostgreSQL: Append-only MVCC. Updates append a new tuple with updated xmin (creation transaction) and xmax (expiry transaction) metadata. Dead tuples remain on the heap until pruned by the autovacuum daemon.
• MySQL InnoDB: In-place updates within the clustered index. Historical versions are written to the Undo Log segment. Prior states are reconstructed on demand by following the row's DB_ROLL_PTR back through the rollback segment.

*Both PostgreSQL (via Snapshot Isolation) and InnoDB (via Next-Key gap locking during locking reads, and MVCC snapshot during non-locking reads) prevent phantom reads in Repeatable Read mode. However, both engines remain vulnerable to write-skew anomalies unless true Serializable isolation (such as PostgreSQL's SSI) is enforced.

Low-Contention Queue Processing

Using unconstrained SELECT ... FOR UPDATE causes transactions to block on locked rows, serializing worker pools. The SKIP LOCKED clause circumvents lock queues entirely:

SELECT id, task_data
FROM task_queue
WHERE status = 'QUEUED'
ORDER BY priority DESC, id ASC
LIMIT 1
FOR UPDATE SKIP LOCKED;

Workers bypass currently locked records and acquire the next available task without latency spikes or deadlocks.

5. Distributed Caching Patterns with Redis

Cache-aside architectures frequently suffer from cache stampedes (thundering herds): when a hot key expires, concurrent application threads simultaneously miss the cache and overwhelm the primary database with identical queries.

Client 1 ──(Cache Miss)──> [DB Query] ──> [Set Redis]
Client 2 ──(Cache Miss)──> [DB Query] ──> [Set Redis]  <-- Database Thrashing
Client 3 ──(Cache Miss)──> [DB Query] ──> [Set Redis]

Probabilistic Early Expiration (XFetch)

Rather than using static TTL expirations, the XFetch algorithm proactively recalculates and refreshes keys based on read frequency and computational cost:

$$-\beta \times \delta \times \ln(r) > \text{TTL}_{\text{remaining}}$$

where $\delta$ is the delta computation time, $\beta > 0$ is an aggressiveness multiplier, and $r \sim U(0, 1)$.

import Redis from "ioredis";

interface CachePayload<T> {
  value: T;
  computeTimeMs: number;
  expiresAt: number;
}

export async function xfetch<T>(
  redis: Redis,
  key: string,
  ttlMs: number,
  computeFn: () => Promise<T>,
  beta: number = 1.0
): Promise<T> {
  const cached = await redis.get(key);
  const now = Date.now();

  if (cached) {
    const payload: CachePayload<T> = JSON.parse(cached);
    const remainingTtlMs = payload.expiresAt - now;

    // Evaluate probabilistic recomputation threshold
    const earlyCompute = -beta * payload.computeTimeMs * Math.log(Math.random());
    if (earlyCompute <= remainingTtlMs && remainingTtlMs > 0) {
      return payload.value;
    }
  }

  // Execute refresh when expired or threshold is reached
  const start = Date.now();
  const freshData = await computeFn();
  const computeDuration = Date.now() - start;

  const newPayload: CachePayload<T> = {
    value: freshData,
    computeTimeMs: computeDuration,
    expiresAt: now + ttlMs,
  };

  await redis.set(key, JSON.stringify(newPayload), "PX", ttlMs);
  return freshData;
}

Architectural Summary

Operating high-throughput transactional databases requires coordinating physical storage formats with runtime query mechanics:

1. Index Topologies: Treat indexes as physical layouts. InnoDB secondary indexes incur a bookmark lookup penalty; PostgreSQL updates cause secondary index churn unless HOT-optimized.
2. Cost Calibration: Audit execution plans with EXPLAIN (ANALYZE, BUFFERS). Align random_page_cost with the physical IOPS capabilities of your storage layer.
3. Partition Boundaries: Partition large tables by timestamp or key ranges to enforce active index working-set residency in memory, transforming high-overhead row purges into zero-cost DDL operations.
4. Lock Contention: Mitigate concurrency bottlenecks in consumer queues using FOR UPDATE SKIP LOCKED.
5. Cache Protection: Implement probabilistic cache refreshing (XFetch) to eliminate stampedes on high-cardinality and high-read keys.