Relational Engine Internals: Indexing, Concurrency, Partitioning, and Cache Topologies

High-throughput systems operating at $\ge 15{,}000$ QPS expose the limits of speculative index design and default database configurations. At scale, p99 latency regressions rarely stem from application-layer business logic. Instead, they emerge from the physical mechanics of the relational storage engine: B+Tree page splits, lock escalation, buffer cache misses, and serialization conflicts.

Achieving predictable sub-millisecond execution requires mechanical sympathy with the underlying storage and concurrency subsystems. This analysis examines the execution mechanics of PostgreSQL and MySQL (InnoDB), detailing how storage topologies, execution paths, transaction schedulers, and cache invalidation strategies behave under load.

1. Index Internals: B+Tree vs. GiST

Relational storage engines utilize tree structures to bound disk seek operations. The architectural divergence between PostgreSQL's heap-organized tables and MySQL's clustered index implementation dictates physical I/O profiles.

B+Tree: InnoDB vs. PostgreSQL

A standard B+Tree organizes keys and child pointers into balanced nodes. For a node branching capacity $B$, where the minimum branching factor is $b = \lceil B/2 \rceil$, and an index cardinality $N$, worst-case tree height is bounded by:

$$h \le \left\lceil \log_{b} \left( \frac{N+1}{2} \right) \right\rceil + 1 \implies \mathcal{O}(\log_b N)$$

                     +-------------------+
                     |   Root Node [R]   |
                     +---------+---------+
                               |
              +----------------+----------------+
              v                                 v
     +-----------------+               +-----------------+
     | Internal Node A |               | Internal Node B |
     +--------+--------+               +--------+--------+
              |                                 |
      +-------+-------+                 +-------+-------+
      v               v                 v               v
+-----------+   +-----------+     +-----------+   +-----------+
| Leaf: L1  |<->| Leaf: L2  |<--->| Leaf: L3  |<->| Leaf: L4  |
+-----------+   +-----------+     +-----------+   +-----------+
 [Row/Tuple]     [Row/Tuple]       [Row/Tuple]     [Row/Tuple]

• MySQL InnoDB: Implements an Index-Organized Table (IOT) architecture using 16 KB pages. The primary key forms the clustered B+Tree, where leaf nodes store the physical row payload. Secondary indexes store the corresponding primary key value at their leaf nodes rather than a raw physical pointer. Consequently, a non-covering secondary index search requires a two-pass traversal: traversing the secondary index, followed by a primary key bookmark lookup in the clustered index.
• PostgreSQL: Uses a decoupled heap storage model with 8 KB default pages. Both primary and secondary B+Trees store a physical tuple identifier (ctid: a 4-byte block number and 2-byte tuple offset index). To avoid updating secondary indexes on every record modification, PostgreSQL uses Heap-Only Tuple (HOT) optimization. When an UPDATE does not alter indexed columns and sufficient space exists in the original data block, the new tuple is appended to the same page, linked via an intra-page pointer chain.

GiST (Generalized Search Tree)

PostgreSQL's GiST provides an extensible, balanced tree framework for non-scalar data types, such as spatial coordinates (PostGIS), range intervals, and full-text search vectors. While B+Trees enforce strict total scalar ordering ($<$or$>$), GiST evaluates non-scalar predicates using extensible method interfaces:

• consistent(): Determines if a query predicate is satisfied by a given index entry.
• penalty(): Quantifies the volume expansion cost of inserting a new entry into a specific subtree.
• picksplit(): Partitions entries across two new leaf pages when a node splits.

Because bounding predicates (such as overlap && or contains @>) can intersect multiple bounding boxes simultaneously, GiST lookups can traverse multiple search paths, trading strict logarithmic depth guarantees for multi-dimensional indexing.

2. Execution Plan Diagnostics via EXPLAIN ANALYZE

Evaluating query execution plans requires inspecting internal memory usage, disk spills, and buffer engine metrics:

EXPLAIN (ANALYZE, BUFFERS, SETTINGS, TIMING OFF)
SELECT o.id, o.total_amount, c.email
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.created_at >= '2024-01-01' AND o.status = 'COMPLETED';

A representative execution plan illustrates diagnostic vectors:

Hash Join  (cost=142.30..1845.60 rows=42 width=45) (actual rows=4890 loops=1)
  Hash Cond: (o.customer_id = c.id)
  Buffers: shared hit=1240 read=180 dirtied=12
  ->  Bitmap Heap Scan on orders o  (cost=20.10..1520.40 rows=42 width=20) (actual rows=4890 loops=1)
        Recheck Cond: (status = 'COMPLETED' AND created_at >= '2024-01-01')
        Buffers: shared hit=420 read=180
        ->  Bitmap Index Scan on idx_orders_status_date  (cost=0.00..20.09 rows=42 width=0) (actual rows=4890 loops=1)
              Buffers: shared hit=12
  ->  Hash  (cost=118.50..118.50 rows=8936 width=29) (actual rows=8936 loops=1)
        Buckets: 16384  Batches: 1  Memory Usage: 580kB
        Buffers: shared hit=820

Critical Vector Analysis

1. Buffer Cache Interaction: shared hit=1240 read=180 indicates cache performance. The read metric denotes physical page faults from the filesystem or NVMe subsystem into shared_buffers. High dirtied counts highlight concurrent write loads flushing through background writer processes.
2. Cardinality Estimation Errors: The optimizer predicted 42 rows (rows=42) but processed 4,890 rows (actual rows=4890). This two-order-of-magnitude skew indicates statistical correlation errors between status and created_at. Under-estimations cause the engine to allocate insufficient work_mem or select suboptimal join paths. Remediate this by collecting multivariate statistics or increasing the statistics target:
   sql

   Copy

   CREATE STATISTICS stats_orders_status_date ON status, created_at FROM orders;
   ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
   ANALYZE orders;
   

3. Join Strategy and Memory Limits: Hash joins construct an in-memory hash table on the inner relation. If the memory footprint breaches work_mem, the executor switches to a multi-batch hash join (Batches: > 1), spilling partitions to temporary disk files. For pre-sorted inputs, an explicit Merge Join eliminates the hash build phase and associated allocation overhead.

3. Declarative Table Partitioning & Pruning

Declarative partitioning bounds index working sets to fit within available RAM, isolating active write sets from archival data.

CREATE TABLE audit_logs (
    id BIGINT GENERATED ALWAYS AS IDENTITY,
    event_time TIMESTAMPTZ NOT NULL,
    payload JSONB
) PARTITION BY RANGE (event_time);

CREATE TABLE audit_logs_2024_q1 PARTITION OF audit_logs
    FOR VALUES FROM ('2024-01-01 00:00:00+00') TO ('2024-04-01 00:00:00+00');

                     +---------------------------------+
                     |   Client / Application Query    |
                     +----------------+----------------+
                                      |
                     WHERE event_time >= '2024-02-01'
                                      |
                     +----------------v----------------+
                     |        Query Optimizer          |
                     |     (Partition Pruning)         |
                     +----------------+----------------+
                                      |
                   Prune (Exclude)    | Route (Include)
             +------------------------+------------------------+
             v                                                 v
+---------------------------+                     +---------------------------+
|   audit_logs_2023_q4      |                     |   audit_logs_2024_q1      |
|   (Skipped / Untouched)   |                     |   (Targeted Scan)         |
+---------------------------+                     +---------------------------+

Pruning Mechanics and DDL Trade-offs

The planner utilizes both compile-time and run-time partition pruning (enable_partition_pruning = on) to eliminate non-matching partitions during plan generation or parameterized execution.

• Data Lifecycle Management: Purging archival data via DELETE statements induces vacuum bloat and extensive Write-Ahead Log (WAL) traffic. Partitioning transforms eviction into an instantaneous metadata modification:
  sql

  Copy

  ALTER TABLE audit_logs DETACH PARTITION audit_logs_2023_q4 CONCURRENTLY;
  DROP TABLE audit_logs_2023_q4;
  

• Lock Contention: A standard DETACH or ATTACH operation acquires an ACCESS EXCLUSIVE lock on the root table, blocking concurrent DML. Invoking DETACH CONCURRENTLY downgrades this requirement to a SHARE UPDATE EXCLUSIVE lock, maintaining online read and write paths. Always enforce strict lock timeouts to avoid blocking queued workloads:
  sql

  Copy

  SET lock_timeout = '2s';
  

4. Isolation Levels and Lock Scheduling

Concurrency anomalies scale with transaction arrival rates. Engines resolve isolation levels through distinct locking and snapshot mechanics.

Engine Implementations: Gap Locks vs. SSI

• MySQL InnoDB (Repeatable Read): Mitigates phantom reads using Next-Key Locking—combining an index-record lock with a gap lock over the preceding address space. When running range scans:

  sql

  Copy

  SELECT * FROM inventory WHERE stock_count BETWEEN 10 AND 50 FOR UPDATE;
  

  InnoDB locks existing keys and blocks concurrent INSERT operations into the gap $(\min, \max)$, preventing phantoms at the expense of lower write concurrency and elevated deadlock frequencies.

• PostgreSQL (Serializable): Uses Serializable Snapshot Isolation (SSI). It sets non-blocking SIREAD lock flags in shared memory without locking rows directly. The engine tracks read-write conflicts dynamically within a Serialization Dependency Graph. If an anti-dependency cycle forms ($T_1 \xrightarrow{rw} T_2 \xrightarrow{rw} T_1$), the scheduler aborts a participating transaction with SQLSTATE 40001 (serialization_failure), requiring client-side transaction retries.

Row-Lock Hazards

Acquiring row locks out of order across concurrent workers causes cyclic wait graphs. Enforce deterministic primary-key ordering on all batch updates to prevent deadlocks:

// Enforce deterministic row locking order
async function reserveInventoryBatch(trx: Transaction, itemIds: number[]) {
  const sortedIds = [...new Set(itemIds)].sort((a, b) => a - b);
  return await trx.raw(
    `SELECT id, stock FROM inventory 
     WHERE id = ANY(?::int[]) 
     ORDER BY id FOR UPDATE`,
    [sortedIds]
  );
}

5. Cache Coherency and High-Concurrency Redis Patterns

Coupling a distributed cache with a relational store introduces cache stampedes and invalidation races under peak read loads.

Application Read
       |
       v
+--------------+     HIT      +---------------+
| Redis Cache  |------------->| Return Data   |
+-------+------+              +---------------+
        |
   MISS | (Probabilistic Early Expiration or Lock)
        v
+--------------+              +---------------+
| PostgreSQL / |------------->| Rehydrate     |
| MySQL DB     |              | Redis Cache   |
+--------------+              +---------------+

Mitigating Stampedes: The XFetch Algorithm

Standard cache-aside patterns fail when a heavily accessed key expires, causing thousands of concurrent workers to query the database simultaneously. The XFetch algorithm provides probabilistic early recomputation, computing and refreshing the cache prior to hard expiration:

$$-\Delta \cdot \beta \cdot \ln(\text{rand}()) > \text{TTL}_{\text{remaining}}$$

Where $\Delta$ is the computation delta, $\beta > 0$ controls recomputation aggressiveness, $\text{rand}() \sim U(0,1)$, and $\text{TTL}_{\text{remaining}} = \text{expiry} - \text{now}$.

import Redis from "ioredis";

interface CachePayload<T> {
  data: T;
  delta: number; // Execution time in ms
  expiry: number; // Absolute epoch timestamp in ms
}

export async function xfetch<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 parsed: CachePayload<T> = JSON.parse(cached);
    const ttlRemaining = parsed.expiry - now;

    // Evaluate probabilistic early expiration condition
    if (-parsed.delta * beta * Math.log(Math.random()) <= ttlRemaining) {
      return parsed.data;
    }
  }

  // Ensure a single worker recomputes the expired cache entry
  const lockKey = `lock:${key}`;
  const acquired = await redis.set(lockKey, "1", "PX", 5000, "NX");

  if (!acquired && cached) {
    return JSON.parse(cached).data;
  }

  const startTime = Date.now();
  const freshData = await computeFn();
  const delta = Date.now() - startTime;
  const expiry = now + ttlSeconds * 1000;

  const payload: CachePayload<T> = { data: freshData, delta, expiry };

  await redis.set(key, JSON.stringify(payload), "EX", ttlSeconds);
  await redis.del(lockKey);

  return freshData;
}

Engineering Takeaways

• Storage-Conscious Indexing: Maximize PostgreSQL HOT updates by isolating frequently updated attributes from index definitions. For InnoDB, minimize secondary indexes to avoid redundant clustered index traversals.
• Execution Plan Tuning: Monitor shared read vs shared hit ratios in EXPLAIN (BUFFERS) to detect memory constraints. Expand statistics targets when cardinality estimates diverge by an order of magnitude.
• Deterministic Locking: Prevent deadlocks by sorting unique identifiers prior to issuing batch SELECT ... FOR UPDATE operations.
• Probabilistic Caching: Use the XFetch algorithm to eliminate cache stampedes, decoupling database load from traffic spikes on hot keys.