Relational Bottlenecks: Query Complexity and Index Failures

Scaling a system to handle massive traffic requires a deep understanding of how databases process queries under load. While application servers can scale horizontally with ease, the database often becomes the ultimate bottleneck. This chapter explores the limits of relational database write throughput, the hidden costs of provisioning hardware to solve performance issues, and how seemingly simple SQL queries can completely crash a database when scaled to millions of records.

1. The Database Connection Pool Problem

When scaling an application across multiple instances, managing the database connection pool is critical. If every application instance opens too many connections, the database will quickly exhaust its resources and crash.

Connection Math and Defaults

In our architecture, we deployed 128 application machines.

• Each machine runs a Node.js process connecting to PostgreSQL via the pg library.
• By default, the PostgreSQL client driver (pg) allocates a maximum pool size of 10 connections per instance if not explicitly configured.

The Database Limit

A standard, low-tier database instance would immediately crash or reject connections under this load. However, our high-performance database instance is configured with a high connection ceiling:

-- Checking the maximum connection limit in PostgreSQL
SHOW max_connections;
-- Output: 5000

Because the database is configured to support up to 5,000 concurrent connections, it easily tolerates the 1,280 active connections. However, having the capacity to connect does not equate to having the capacity to perform high-speed writes.

2. The Cost of Brute-Forcing Write Throughput (IOPS)

Our initial write performance was highly bottlenecked, hovering around a pathetic 32,000 writes per second—far below our target of 1 million requests per second.

The Hardware Bottleneck: Provisioned IOPS

The primary bottleneck for relational database writes is disk I/O. Relational databases must write transactions to a write-ahead log (WAL) and commit them to non-volatile storage to maintain ACID compliance.

• Initial Configuration: The database was provisioned with 3,000 IOPS (Input/Output Operations Per Second).
• Upgraded Configuration: The storage was increased to 500 GB and the throughput was scaled to 12,000 IOPS (a $4\times$ increase in disk speed).

The Diminishing Returns of Vertical Scaling

After upgrading the disk performance by $4\times$, we reran the write benchmark:

While performance increased, it did not scale linearly with the IOPS increase. To reach 1 million writes per second purely by scaling cloud hardware, the database costs would skyrocket to at least $15,000 per month, and even then, physical hardware limits would likely prevent us from achieving the target.

💡 Real-Life Analogy

Trying to write 1 million individual records per second directly to a relational database is like a mail carrier trying to drive back and forth to the post office for every single letter they deliver. Instead of driving back and forth 1,000 times, the carrier collects letters in a bag and delivers them all in a single trip (Batch Processing). We will explore batch processing strategies in later chapters.

3. The Danger of Naive Queries: ORDER BY random() (V1)

To test read performance at scale, we seeded the database with 10 million records (a realistic dataset size for an application handling high traffic).

Our first read implementation (Version 1) attempted to fetch a random record from the database using a common SQL pattern:

// Version 1: Naive Random Read
app.get('/v1/code', async (req, res) => {
  const result = await db.query('SELECT id, code FROM codes ORDER BY random() LIMIT 1');
  res.send(result.rows[0]);
});

Why This Crashed the Database (Big O Complexity)

This query has a time complexity of $\mathcal{O}(N \log N)$ because of how sorting works:

1. The database generates a random float value between 0.0 and 1.0 for every single one of the 10 million rows.
2. It copies these rows into temporary memory or disk storage.
3. It sorts the entire 10-million-row dataset based on these newly generated random values.
4. It finally returns the top record (LIMIT 1).

When we ran this query against our 10-million-row database, a single request took 43 seconds to complete. Under load, this query immediately exhausted database CPU and memory, causing the entire database to crash.

4. The Pitfalls of Table Scans: COUNT(*) (V2)

To avoid sorting the entire table, Version 2 attempted to count the records, generate a random index in application memory, and query that specific offset.

// Version 2: Count and Offset
app.get('/v2/code', async (req, res) => {
  const countResult = await db.query('SELECT count(*) FROM codes');
  const totalRows = parseInt(countResult.rows[0].count);
  const randomOffset = Math.floor(Math.random() * totalRows);
  
  const result = await db.query('SELECT id, code FROM codes LIMIT 1 OFFSET $1', [randomOffset]);
  res.send(result.rows[0]);
});

Why This Also Failed

While it looks better on paper, Version 2 failed under load for two reasons:

1. COUNT(*) is $\mathcal{O}(N)$ in PostgreSQL: PostgreSQL does not keep a live, cached counter of the exact row count in a table because of Multi-Version Concurrency Control (MVCC). To get an exact count, it must perform a sequential scan of the table or its index.
2. OFFSET is $\mathcal{O}(K)$: To skip to a random offset of 5 million, the database engine must still scan through the first 5 million rows sequentially before returning the next row.

At 10 million rows, this approach timed out and crashed the database under load.

5. The Optimized Approach: Index-Backed Random Selection (V3)

To achieve high-speed reads, we must query the database using an index-backed operation that runs in $\mathcal{O}(\log N)$ or $\mathcal{O}(1)$ time.

In Version 3, we query the maximum ID in the table (which is an instantaneous $\mathcal{O}(1)$ index lookup), generate a random ID between 1 and max_id in the application code, and fetch that specific row directly by its primary key.

// Version 3: Index-Backed Random Selection
app.get('/v3/code', async (req, res) => {
  // 1. Get the maximum ID (O(1) operation using the primary key index)
  const maxIdResult = await db.query('SELECT id FROM codes ORDER BY id DESC LIMIT 1');
  const maxId = maxIdResult.rows[0].id;
  
  // 2. Generate a random ID in application memory
  const randomId = Math.floor(Math.random() * maxId) + 1;
  
  // 3. Fetch the record directly by its indexed ID (O(log N) B-Tree lookup)
  const result = await db.query('SELECT id, code FROM codes WHERE id = $1', [randomId]);
  res.send(result.rows[0]);
});

Execution Flow Comparison

Performance Results

Using the Version 3 strategy, the average query response time dropped from 43 seconds to 40 milliseconds. When benchmarked under load, this optimized route achieved 200,000 reads per second.

While 200,000 reads per second is an incredible milestone for a relational database, it is still only $20\%$ of our target of 1 million requests per second. To bridge this final gap, we must look beyond raw relational database queries.

Summary and Key Takeaways

• Connection Pool Exhaustion: When scaling out application servers, always calculate the total connection footprint (instances * max_pool_size) to ensure it does not exceed the database's max_connections limit.
• Vertical Scaling Limits: Upgrading database storage IOPS is highly expensive and yields diminishing returns. Upgrading disk performance by $4\times$ ($1,000/month extra) only yielded a$2.2\times$ write throughput improvement.
• Avoid ORDER BY random(): This query is an $\mathcal{O}(N \log N)$ operation that forces the database to copy and sort the entire table in memory. It will crash production databases at scale.
• Avoid COUNT(*) and OFFSET: In MVCC databases like PostgreSQL, COUNT(*) requires a full table scan, and large OFFSET values require scanning and discarding thousands of rows.
• Leverage Indexes for Randomness: To fetch a random row efficiently, query the maximum ID using an index, generate the random target in the application layer, and fetch the row directly by its indexed primary key.