N+1 Query Problem & DataLoader Batching

+-----------------------------------------------------------------------------------+
| The N+1 Query Cascade Disaster                                                    |
|                                                                                   |
|  Client Query:                                                                    |
|  query GetRecentArticles {                                                        |
|    articles(limit: 100) {      <-- 1 Initial Query                                |
|      id                                                                           |
|      title                                                                        |
|      author {                  <-- N Subordinate Queries (N = 100)                |
|        name                                                                       |
|      }                                                                            |
|    }                                                                              |
|  }                                                                                |
|                                                                                   |
|  Execution Timeline at the Database:                                              |
|                                                                                   |
|  1. Query.articles Resolver Dispatches:                                           |
|     SQL: SELECT * FROM articles ORDER BY published_at DESC LIMIT 100;             |
|     -> Database returns 100 article records. (1 Network Round-trip)               |
|                                                                                   |
|  2. Execution Engine Dispatches Article.author for EACH Article in Parallel:      |
|     SQL 1:   SELECT * FROM users WHERE id = 12;                                   |
|     SQL 2:   SELECT * FROM users WHERE id = 45;                                   |
|     SQL 3:   SELECT * FROM users WHERE id = 12;  <-- Duplicate!                   |
|     SQL 4:   SELECT * FROM users WHERE id = 89;                                   |
|     ...                                                                           |
|     SQL 100: SELECT * FROM users WHERE id = 45;  <-- Duplicate!                   |
|     -> 100 INDEPENDENT SQL QUERIES FLOOD THE DATABASE!                            |
|                                                                                   |
|  Total Database Round-trips: 1 + 100 = 101 queries!                               |
|  If each article also requested 'comments(limit: 10)', total queries:             |
|  1 + 100 (authors) + 100 (comments) + 1,000 (comment authors) = 1,201 queries!   |
+-----------------------------------------------------------------------------------+

// NAIVE RESOLVER (ANTI-PATTERN)
const resolvers = {
  Article: {
    author: async (parent: ArticleEntity, _args: unknown, context: GraphQLContext) => {
      // Dispatches a separate database query for every single article!
      return context.db.query('SELECT * FROM users WHERE id = 1', [parent.author_id]);
    }
  }
};

+-----------------------------------------------------------------------------------+
| DataLoader Batching & Microtask Coalescing Pipeline                               |
|                                                                                   |
|  Synchronous Execution Phase (Tick 0):                                            |
|  - Resolver 1 calls:  userLoader.load(12)  --> Appends 12 to queue; returns Prom1 |
|  - Resolver 2 calls:  userLoader.load(45)  --> Appends 45 to queue; returns Prom2 |
|  - Resolver 3 calls:  userLoader.load(12)  --> Cache Hit! Returns Prom1           |
|  - Resolver 4 calls:  userLoader.load(89)  --> Appends 89 to queue; returns Prom4 |
|  ...                                                                              |
|  - Resolver 100 calls: userLoader.load(7)  --> Appends 7 to queue; returns Prom100|
|                                                                                   |
|  ===============================================================================  |
|  Synchronous Execution Stack Drains -> Microtask Queue Fires (process.nextTick)   |
|  ===============================================================================  |
|                                                                                   |
|  DataLoader Batch Function Dispatches (Tick 1):                                   |
|  - Distinct Keys Collected: [12, 45, 89, ..., 7] (e.g., 18 unique user IDs)       |
|  - Dispatches SINGLE Batched SQL Query:                                           |
|    SELECT * FROM users WHERE id IN (12, 45, 89, ..., 7);                          |
|  - Receives database records.                                                     |
|  - Resolves Prom1, Prom2, ..., Prom100 simultaneously with matching user entities.|
|                                                                                   |
|  Total Database Queries Dispatched: Exactly 1 query!                              |
+-----------------------------------------------------------------------------------+

type BatchFunction<K, V> = (keys: readonly K[]) => Promise<(V | Error)[]>;

// BROKEN BATCH FUNCTION (VIOLATES INVARIANT 2)
async function batchUsers(keys: readonly string[]) {
  // SQL DOES NOT GUARANTEE RETURN ORDER MATCHES THE "IN" LIST!
  const rows = await db.query('SELECT * FROM users WHERE id IN (1)', [keys]);
  return rows; // CATASTROPHIC BUG: rows[0] does NOT match keys[0]!
}

// CORRECT BATCH FUNCTION
async function batchUsers(keys: readonly string[]) {
  const rows = await db.query('SELECT * FROM users WHERE id = ANY(1)', [keys]);
  
  // 1. Build lookup map: Key -> Row
  const userMap = new Map<string, UserEntity>();
  for (const row of rows) {
    userMap.set(row.id, row);
  }

  // 2. Map strictly across original input keys to preserve length and order
  return keys.map((key) => {
    return userMap.get(key) || null; // Return null (or Error) if key not found
  });
}

---

## Production Multi-Type DataLoader Implementation in TypeScript

Below is a complete, production-grade TypeScript implementation of a resilient DataLoader repository for PostgreSQL, handling both single-entity and collection lookups with strict invariant enforcement.

---

## Checkpoint Practice Problems

Test your mastery of batching mathematics, event loop scheduling, and cache invariant integrity through these detailed engineering problems.

### Problem 1: Database IOPS, Connection Saturation & Latency Derivation

An enterprise microservice cluster serves an e-commerce catalog via GraphQL. The platform experiences a sustained traffic load of Q = 800  GraphQL queries/sec.

Each GraphQL query fetches a collection of 50 products and resolves the corresponding supplier for each product:

The database cluster has a connection pool ceiling of C_{max} = 100  connections.
Each individual SQL query over the database socket requires an average network round-trip time of T_{sql} = 2.0  ms plus 0.5  ms of database execution time (T_{total} = 2.5  ms = 0.0025  s).

1. Under **Architecture A (Naive Resolvers without DataLoader)**:
   * Calculate the total SQL queries generated per second (IOPS demand).
   * Using Little's Law (L = λ × W), calculate the average number of active database connections required to sustain this traffic.
   * Determine whether the database connection pool (C_{max} = 100) will saturate, and compute the resulting queuing delay if overloaded.
2. Under **Architecture B (DataLoader Batching Enabled)**:
   * Assume that across the 50 products in each query, there are an average of 8 distinct suppliers.
   * Calculate the total SQL queries generated per second under DataLoader batching.
   * Calculate the required active database connections under Little's Law, and evaluate connection pool headroom.

**Solution**:

**Step 1: Evaluate Architecture A (Naive Resolvers)**:
* Each GraphQL query executes:
  * 1 query for products (`SELECT * FROM products LIMIT 50`)
  * 50 queries for suppliers (`SELECT * FROM suppliers WHERE id = ...`)
  * Total SQL queries per GraphQL query = 1 + 50 = 51  queries.
* Total database queries per second:
  Query Rate  λ_A = 800  GraphQL req/s × 51  SQL/req = 40,800  SQL queries/sec* Applying Little's Law to calculate concurrent active connections (L_A):
  L_A = λ_A × Wwhere W = T_{total} = 0.0025  seconds.
  L_A = 40,800  queries/sec × 0.0025  seconds = 102  concurrent connections* **Connection Pool Saturation Assessment**:
  The required average connection count is 102, which strictly exceeds the maximum pool capacity (C_{max} = 100).
  Under stochastic arrival bursts (Poisson distribution), incoming queries find all 100 connections permanently occupied. Requests accumulate in the connection pool waiting queue.
  If the queue fills, application threads throw `ConnectionPoolTimeoutException` (500 Internal Server Error). If queries queue up, connection wait time escalates from 0 ms to over 1,500 ms, causing cascading service failure.

**Step 2: Evaluate Architecture B (DataLoader Batching Enabled)**:
* With DataLoader:
  * 1 query for products (`SELECT * FROM products LIMIT 50`)
  * Exactly 1 batched query for all distinct suppliers (`SELECT * FROM suppliers WHERE id IN (...)`)
  * Total SQL queries per GraphQL query = 1 + 1 = 2  queries.
* Total database queries per second:
  Query Rate  λ_B = 800  GraphQL req/s × 2  SQL/req = 1,600  SQL queries/secThis represents a **96.08% reduction in database IOPS**!

* Applying Little's Law for Architecture B:
  L_B = λ_B × W = 1,600  queries/sec × 0.0025  seconds = 4.0  concurrent connections* **Headroom Assessment**:
  Architecture B requires only 4 concurrent database connections out of the 100 available (96\% headroom available). The database operates at nominal CPU and IOPS capacity, completely eliminating connection contention and queuing delay.

---

### Problem 2: Batch Array Ordering & Invariant Recovery Algorithm

A junior developer implements a batch loading function for fetching student grades by enrollment IDs:

The database contains grades for only 3 of the 5 requested enrollment IDs:
* Input `enrollmentIds`: `['e_101', 'e_102', 'e_103', 'e_104', 'e_105']`
* Records present in database:
  * `e_101` -> `{ enrollment_id: 'e_101', score: 88, grade: 'B+' }`
  * `e_103` -> `{ enrollment_id: 'e_103', score: 95, grade: 'A' }`
  * `e_105` -> `{ enrollment_id: 'e_105', score: 72, grade: 'C' }`
  (Enrollment IDs `e_102` and `e_104` do not exist).
Due to physical page indexing, PostgreSQL returns the 3 rows in order: `['e_105', 'e_101', 'e_103']`.

1. Explain the two specific runtime errors or data corruption events that occur if this flawed batch function is passed to DataLoader.
2. Write a mathematically correct, generic TypeScript function `normalizeBatchResults<K, V>` that accepts the input keys, raw database rows, a key-extractor function, and an error fallback, producing an array strictly compliant with DataLoader Invariants 1 and 2.

**Solution**:

**Step 1: Failure Analysis**:
1. **Length Invariant Violation**:
   DataLoader provided 5 keys (`length = 5`), but `result.rows` contains only 3 elements (`length = 3`).
   DataLoader runtime detects length(results) ≠ length(keys) and immediately throws:
   `Error: DataLoader must be constructed with a function which accepts Array<key> and returns Promise<Array<value>>, but the function did not return an array of the same length...`
   The entire GraphQL query fails with a top-level error.
2. **Index Alignment Violation**:
   Even if the database had returned 5 rows, because PostgreSQL returned `e_105` first, `result.rows[0]` (`e_105`'s grade) would be delivered to the resolver that requested `enrollmentIds[0]` (`e_101`). Student 101 receives Student 105's grade (silent data corruption and privacy breach).

**Step 2: Generic Invariant Normalization Utility**:

Usage in the corrected batch function:

Output:
`[ Grade#101, null, Grade#103, null, Grade#105 ]` (Length = 5, Order = Exact match). Both invariants are perfectly preserved.

---

### Problem 3: Production One-to-Many DataLoader with Limit Constraints

A common challenge in GraphQL is batching one-to-many relationships that include pagination or limit arguments:

If a developer queries `SELECT * FROM orders WHERE user_id IN (...) ORDER BY created_at DESC`, they cannot simply append `LIMIT 3` to the SQL query because the limit applies globally to the entire query result, not per user!

Write an optimized PostgreSQL query using SQL Window Functions (`ROW_NUMBER() OVER (PARTITION BY ...)`), and construct a TypeScript DataLoader batch function that retrieves the top N orders per user in a single SQL round-trip.

**Solution**:

Through the `ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY created_at DESC)` window function, the database server partitions and filters orders per customer directly in memory, returning at most 3 rows per user in a single query with zero client-side over-fetching.

---

### Problem 4: Microtask Scheduling Simulation & Execution Tick Timing

Examine the following code snippet simulating the Node.js event loop execution of a GraphQL query:

1. Trace the exact sequential order of log outputs from 1 through 8.
2. Explain precisely why DataLoader executes its batch function before the macrotask `setTimeout` timer fires.
3. What would happen if a resolver executed an asynchronous `await delay(10)` before invoking `userLoader.load('C')`?

**Solution**:

**Step 1: Sequential Execution Trace**:
1. `1: Synchronous Query Execution Starts` (Synchronous main thread execution)
2. `userLoader.load('A')` enqueues 'A' and registers internal batch dispatcher via `process.nextTick`.
3. `userLoader.load('B')` enqueues 'B' to the existing batch.
4. `setTimeout(..., 0)` registers a timer in the Macrotask (Timers) queue.
5. `process.nextTick(...)` appends callback '3' to the Microtask Tick queue.
6. `Promise.resolve().then(...)` appends callback '4' to the Microtask Promise queue.
7. `2: Synchronous Query Execution Ends` (Synchronous main thread finishes).
8. **Microtask Queue Drains**:
   * Node.js executes `process.nextTick` queue before Promise queue.
   * `3: Manual process.nextTick Callback Fires`
   * DataLoader's scheduled batch dispatcher executes:
     `5: DataLoader Batch Function Fires with keys: [ 'A', 'B' ]`
   * `4: Manual Promise.then Callback Fires`
   * Resolvers' `.then()` handlers resolve:
     `6: Resolver 1 receives: User_A`
     `7: Resolver 2 receives: User_B`
9. **Event Loop advances to Timers phase (Macrotask)**:
   * `8: Macrotask Timer Callback Fires`

**Step 2: Why DataLoader Preempts setTimeout**:
Under the Node.js event loop specification, the Microtask Queue (`process.nextTick` and `Promise` reaction queues) has strict priority over the Macrotask Queue (timers, I/O callbacks, `setImmediate`). Microtasks drain immediately whenever the current synchronous execution context empties, before the event loop advances to the next phase. DataLoader utilizes microtasks specifically to execute batching in 0 milliseconds without yielding to the OS timer subsystem.

**Step 3: Impact of `await delay(10)`**:
If Resolver 3 executes `await delay(10)` before calling `userLoader.load('C')`, the call stack yields, and the initial microtask queue drains completely, executing the batch for `['A', 'B']`. 10 milliseconds later, when Resolver 3 wakes up and calls `userLoader.load('C')`, that call enters a **new, separate batch**. Key 'C' is not coalesced with 'A' and 'B', resulting in an extra database query. In GraphQL architecture, all asynchronous preprocessing must occur before invoking DataLoaders to prevent premature batch dispatching.