Deep Database Internals: Indexing, Execution Plans, Partitioning, Concurrency, and Caching

Scaling relational workloads beyond $100\text{k}$ queries per second requires mastery of physical storage layouts, memory-to-disk access paths, transaction isolation guarantees, and cache coordination. Inefficient access paths degrade throughput non-linearly under concurrent load. This technical analysis explores storage engine internals across PostgreSQL and MySQL InnoDB, query plan execution mechanics, table partitioning strategies, concurrency control, and distributed caching patterns.

1. Index Internals: B+Tree and GiST

Relational database performance depends on index architecture. PostgreSQL and MySQL InnoDB utilize B+Tree variants as default storage structures, but memory layout and heap interaction differ fundamentally.

       +------------------------------------+
       |          Root Page (Node)          |
       |  [Key: 100 | Ptr] [Key: 500 | Ptr] |
       +-----------------+------------------+
                         |
       +-----------------+------------------+
       |       Internal Branch Node         |
       |  [Key: 50 | Ptr] [Key: 80 | Ptr]   |
       +-----------------+------------------+
                         |
       +-----------------+------------------+
       |             Leaf Page              |
       |  [Key: 10 -> Row/Tuple Pointer]    | <---> Doubly-Linked
       |  [Key: 20 -> Row/Tuple Pointer]    |       Leaf Chain
       +------------------------------------+

B+Tree Structure and Engine Differences

B+Trees maintain sorted keys with high fan-out $B$, bounding random disk I/O. Maximum tree height $h$ for $N$ records satisfies:

$$h \le \left\lceil \log_{\lceil B/2 \rceil} \left( \frac{N+1}{2} \right) \right\rceil + 1$$

• MySQL InnoDB (Clustered Index): Organizes primary table data directly inside primary key B+Tree leaf pages. Secondary indexes store indexed column values alongside the corresponding primary key. Secondary index lookups require a secondary traversal through the clustered index unless satisfied entirely by a covering index.
• PostgreSQL (Heap + Secondary Indexes): Stores table records in unordered 8KB heap pages. All indexes—including primary keys—are secondary indexes pointing to physical Tuple Identifiers:

$$\text{TID} = (\text{Block Number}, \text{Offset Number})$$

PostgreSQL writes a new tuple version on every update, inducing write amplification and index bloat unless Heap-Only Tuple (HOT) conditions are met: the update does not modify indexed attributes, and the new tuple version fits inside the existing heap page.

GiST (Generalized Search Tree)

PostgreSQL GiST provides an extensible, balanced tree structure for non-scalar data types (geometric, text, ranges). GiST organizes keys into hierarchical bounding predicates:

$$\text{Consistent}(E, q) \implies \text{true if predicate } E \text{ matches query } q$$

For 2D bounding boxes (R-Tree implementation on GiST), intermediate nodes store minimal bounding rectangles (MBR) enclosing child nodes:

$$R_{\text{parent}} = \left[ \min(x_{\min}), \min(y_{\min}), \max(x_{\max}), \max(y_{\max}) \right]$$

GiST allows lossy index entries by filtering candidates before final heap re-checks, enabling nearest-neighbor searches ($k$-NN) via priority queue traversal over bounding distance functions.

2. EXPLAIN Plan Dissection and Cost Modeling

Query optimizers evaluate candidate physical execution paths using cost-based models.

                +---------------------------------+
                |        HashAggregate            |
                |  Cost: 1450.20..1520.40         |
                +----------------+----------------+
                                 |
                +----------------+----------------+
                |           Hash Join             |
                |  Hash Cond: (o.user_id = u.id)  |
                +-------+-----------------+-------+
                        |                 |
        +---------------+---+     +-------+---------------+
        |    Seq Scan (u)   |     |    Bitmap Heap Scan   |
        |  Filter: status   |     |  Bitmap Index: orders |
        +-------------------+     +-----------------------+

PostgreSQL Cost Model Formulation

Total execution plan cost combines random I/O, sequential I/O, and CPU evaluation cycles:

$$\text{Total Cost} = (N_{\text{seq\_pages}} \cdot C_{\text{seq\_page\_cost}}) + (N_{\text{rand\_pages}} \cdot C_{\text{rand\_page\_cost}}) + (N_{\text{tuples}} \cdot C_{\text{cpu\_tuple}}) + (N_{\text{ops}} \cdot C_{\text{cpu\_operator}})$$

Default planner constants assume rotational media ($C_{\text{seq\_page\_cost}} = 1.0$, $C_{\text{rand\_page\_cost}} = 4.0$). High-throughput NVMe drives require setting random_page_cost = 1.1 to prevent planners from penalizing index scans over full table scans.

Execution Plan Analysis

Execute query profiling via PostgreSQL and MySQL interfaces:

-- PostgreSQL: Inspect buffer hits, disk reads, and execution timings
EXPLAIN (ANALYZE, BUFFERS, VERBOSE, SETTINGS)
SELECT u.id, count(o.id)
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE o.created_at >= '2024-01-01'
GROUP BY u.id;

-- MySQL 8.0: Analyze execution costs and iterator pipelines
EXPLAIN FORMAT=JSON
SELECT u.id, count(o.id)
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE o.created_at >= '2024-01-01'
GROUP BY u.id;

Critical node types:

1. Seq Scan / Table Scan: Scans physical table sequentially. High I/O overhead on large tables.
2. Index Scan: Traverses B+Tree and retrieves matching heap tuples. Optimal for selective filters ($\le 2\%$).
3. Bitmap Index Scan (PostgreSQL): Builds a dynamic memory bitmap of matching page locations, then reads heap blocks sequentially via Bitmap Heap Scan, mitigating random I/O.
4. Index Only Scan: Retrieves data directly from index leaf pages without accessing heap blocks when visibility map bits confirm pages contain no uncommitted tuples.

3. Declarative Table Partitioning

Partitioning divides large logical relations into distinct physical storage objects, optimizing working set cache residency and pruning index size.

-- Declarative Range Partitioning with Sub-Hash in PostgreSQL
CREATE TABLE telemetry_events (
    event_id   UUID NOT NULL,
    device_id  BIGINT NOT NULL,
    recorded_at TIMESTAMPTZ NOT NULL,
    payload    JSONB,
    PRIMARY KEY (recorded_at, device_id, event_id)
) PARTITION BY RANGE (recorded_at);

CREATE TABLE telemetry_events_2024_q1 PARTITION OF telemetry_events
    FOR VALUES FROM ('2024-01-01 00:00:00Z') TO ('2024-04-01 00:00:00Z')
    PARTITION BY HASH (device_id);

CREATE TABLE telemetry_events_2024_q1_p1 PARTITION OF telemetry_events_2024_q1
    FOR VALUES WITH (MODULUS 2, REMAINDER 0);
CREATE TABLE telemetry_events_2024_q1_p2 PARTITION OF telemetry_events_2024_q1
    FOR VALUES WITH (MODULUS 2, REMAINDER 1);

Partition Pruning

Partition pruning eliminates irrelevant physical partitions during planning and execution:

• Static Pruning: Planner strips non-matching partitions during compilation via constant WHERE expressions.
• Dynamic Pruning: Executor discards partitions at runtime during parameterized joins or subquery execution.

Verify partition pruning via EXPLAIN: Subplans Removed confirms unreferenced physical partitions are bypassed.

4. MVCC, Transaction Isolation, and Row Locking

Multi-Version Concurrency Control (MVCC) guarantees non-blocking concurrent reads and writes.

PostgreSQL Tuple Header:
+--------+--------+------------------+
| t_xmin | t_xmax | Data Payload     |
| 1001   | 1005   | { user_id: 42 }  |
+--------+--------+------------------+

InnoDB Clustered Index Record:
+-----------------+-------------+---------------+--------------+
| Primary Key Col | DB_TRX_ID   | DB_ROLL_PTR   | User Columns |
| ID = 42         | 1005        | 0x00A1BC8F    | Data...      |
+-----------------+-------------+---------------+--------------+
                                       |
                                       v
                                [ Undo Log Segment ]

• PostgreSQL: Tuple headers store t_xmin (creation transaction ID) and t_xmax (deletion/update transaction ID). Active transactions match visible tuples against snapshot metadata: $$\text{Snapshot} = (\text{xmin}, \text{xmax}, [\text{active\_txids}])$$
• InnoDB: Performs in-place record updates and streams prior tuple states into Undo Log segments. DB_TRX_ID tracks the modifying transaction, while DB_ROLL_PTR points to historical undo records to reconstruct snapshot states.

Isolation Levels and Anomalies

Row Locking Strategies

Avoid lock contention and queue saturation using non-blocking locking primitives:

-- Acquire exclusive row locks, skipping locked records for worker queues
SELECT task_id, payload
FROM background_tasks
WHERE status = 'QUEUED'
ORDER BY priority DESC
LIMIT 10
FOR UPDATE SKIP LOCKED;

InnoDB implements Next-Key Locks (record locks coupled with gap locks on the preceding index interval) under REPEATABLE READ to eliminate phantom rows in range predicates:

$$\text{Lock Range} = (K_{i-1}, K_i]$$

5. Redis Caching Patterns: Cache-Aside and Probabilistic Expiry

Caching layers protect primary database instances from read saturation under concurrent spikes.

Application                  Redis Cache                  PostgreSQL DB
    |                             |                             |
    |---- 1. Read (Key) --------->|                             |
    |     (Cache Miss)            |                             |
    |<--- 2. Return nil ----------|                             |
    |                                                           |
    |---- 3. Execute Optimized SQL Query ---------------------->|
    |<--- 4. Return Tuple Result Set ---------------------------|
    |                                                           |
    |---- 5. Asynchronously Write Cache (Key, TTL) ------------>|
    |                                                           |

Cache Stampede Mitigation (XFetch Algorithm)

Standard cache-aside patterns fail when high-traffic keys expire, causing simultaneous cache misses that saturate the database. The XFetch algorithm applies probabilistic early recomputation to refresh values before expiration:

$$-\Delta t \cdot \beta \cdot \ln(\text{rand}()) > (\text{TTL}_{\text{expiration}} - \text{Time}_{\text{current}})$$

Where $\Delta t$ is computation duration, $\beta > 0$ is recomputation aggressiveness, and $\text{rand}() \sim U(0,1)$.

import Redis from "ioredis";

interface CacheEntry<T> {
  value: T;
  delta: number;      // Compute duration (ms)
  expiry: number;     // Absolute timestamp (ms)
}

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

  if (cached) {
    const entry: CacheEntry<T> = JSON.parse(cached);
    const timeRemaining = entry.expiry - now;
    const shouldRecomputeEarly = -(entry.delta * beta * Math.log(Math.random())) > timeRemaining;

    if (!shouldRecomputeEarly) {
      return entry.value;
    }
  }

  // Compute refreshed value
  const start = Date.now();
  const freshValue = await computeFn();
  const delta = Date.now() - start;
  const expiry = Date.now() + ttlSeconds * 1000;

  const payload: CacheEntry<T> = { value: freshValue, delta, expiry };
  await redis.set(key, JSON.stringify(payload), "EX", ttlSeconds);

  return freshValue;
}

Invalidation Mechanics

Use Change Data Capture (CDC) via Debezium to stream write-ahead logs (PostgreSQL WAL / MySQL binlog) asynchronously to Redis, avoiding dual-write consistency hazards:

[Postgres WAL] ---> [Debezium CDC] ---> [Kafka/Queue] ---> [Redis Invalidation Worker]

6. Architectural Decision Framework

Apply these engineering rules when designing high-throughput relational systems:

1. Index Selectivity Rule: Deploy B+Trees for predicates matching $< 5\%$ of table rows. Use covering indexes (INCLUDE clauses in PostgreSQL) to allow Index Only Scans.
2. Spatial and Range Lookups: Use GiST indexes for geometric predicates and interval ranges; avoid standard multi-column B+Trees for overlapping range types.
3. Queue Processing: Pair SELECT ... FOR UPDATE with SKIP LOCKED to eliminate lock queue serialization in worker pipelines.
4. Data Lifecycle Sharding: Use declarative range partitioning on append-heavy time-series tables to allow $O(1)$ partition detachment via ALTER TABLE ... DETACH PARTITION, preventing MVCC garbage collection overhead from massive DELETE operations.
5. Cache Layering: Apply probabilistic early expiration to hot cache entries to eliminate stampede lock contention under sustained concurrent traffic.