Why SQL JOINs Become Prohibitively Expensive at Very Large Scale

• Scatter-gather – When joined tables are sharded across nodes, a JOIN that does not include the shard key must query every shard and merge results.
• Deep B-tree walks – A B-tree index on billions of rows is many levels deep, with a potential disk I/O per level for each lookup.
• Network-heavy intermediates – Unfiltered intermediate result sets can be millions of rows that must travel across the network.
• Uncacheable per-user results – A personalized dashboard JOIN is unique to one user, so the cache hit rate is near zero.
• Normalization trade-off – Third normal form stores each fact once for write correctness (no update anomalies), but reads must JOIN to reconstruct denormalized views.
• Scale solution – Keep OLTP JOINs shard-local by including the shard key, and pre-compute cross-shard views for analytics.

Why are JOINs cheap at small scale?

At small scale, a JOIN uses a nested-loop, hash, or merge strategy over indexed keys. The optimizer picks the cheapest plan, and the data pages are usually in the buffer cache, so the cost is dominated by in-memory comparisons.

-- On a single-node database with indexed keys: fast
SELECT c.full_name, a.account_type, t.amount, t.txn_date
FROM customers c
JOIN accounts a ON a.customer_id = c.customer_id
JOIN transactions t ON t.account_id = a.account_id
WHERE c.customer_id = 42;
-- All tables on one node. Indexed lookups. Buffer cache warm. ~2ms.

What happens when data is sharded?

A sharded database partitions rows by a shard key – say, customer_id. If all three tables are sharded by customer_id, a single customer's JOIN stays on one shard and is fine. But a JOIN that spans shard keys must scatter to every shard and merge.

-- Shard-local JOIN: fast (stays on one shard)
SELECT * FROM customers c
JOIN accounts a ON a.customer_id = c.customer_id
JOIN transactions t ON t.account_id = a.account_id
WHERE c.customer_id = 42;
-- customer_id is the shard key. Query goes to one shard only.

-- Cross-shard JOIN: slow (scatter-gather)
SELECT c.full_name, SUM(t.amount) AS total
FROM customers c
JOIN accounts a ON a.customer_id = c.customer_id
JOIN transactions t ON t.account_id = a.account_id
WHERE t.amount > 100000
GROUP BY c.full_name;
-- Filtered on amount, not customer_id. Must query EVERY shard.

Why do deep B-tree indexes hurt at scale?

A B-tree with a billion rows is several levels deep, and in the worst case each level is a page not in cache, meaning a disk read per level. One lookup is a few disk reads; a JOIN producing millions of matches is millions of disk reads.

B-tree depth for different table sizes:
  1,000 rows      → ~2 levels (all in cache)
  1,000,000 rows  → ~3 levels (mostly in cache)
  1,000,000,000   → ~5 levels (cold pages = disk I/O per level)

One row lookup: 5 disk reads
JOIN producing 1,000,000 matches: 5,000,000 disk reads

What about intermediate result sets?

If the left side of a JOIN produces ten million rows before the filter narrows them, those rows may have to travel across the network to the node doing the join. Network bandwidth becomes the bottleneck.

-- Large intermediate: all transactions above 1 lakh, then join to customers
SELECT c.full_name, t.amount
FROM transactions t
JOIN customers c ON c.customer_id = t.customer_id
WHERE t.amount > 100000;
-- If 10 million transactions match, those 10M rows ship across the network
-- before the join filters them further

Why can't you cache per-user results?

A page like "top products" is identical for everyone and caches beautifully. But "Rajesh's personalized dashboard joined across three tables" is unique to Rajesh. The cache hit rate is near zero.

package com.bank.service;

public class CacheAnalysis {
    // Shared page: cached once, served to all
    // Hit rate: ~99% (everyone sees the same page)
    static final String TOP_PRODUCTS_KEY = "page:top-products";

    // Per-user dashboard: unique to each customer
    // Hit rate: ~0% (each customer has a unique JOIN result)
    static String dashboardKey(long customerId) {
        return "dashboard:" + customerId;
    }
    // 1 million customers = 1 million cache entries, each accessed once
}

Why does normalization optimize for writes, not reads?

Normalization (third normal form) stores each fact once so there is a single source of truth and no update anomalies. An address change touches one row. The cost is that reads must JOIN to reconstruct the full picture.

-- Normalized: each fact stored once
UPDATE customers SET address = 'New Mumbai Branch' WHERE customer_id = 42;
-- One row updated. No duplicated addresses.

-- But reading requires a JOIN
SELECT c.full_name, c.address, a.account_type, t.amount
FROM customers c
JOIN accounts a ON a.customer_id = c.customer_id
JOIN transactions t ON t.account_id = a.account_id
WHERE c.customer_id = 42;
-- Read reassembles the denormalized view by joining three tables

What is the solution at scale?

Keep OLTP JOINs shard-local by carrying the shard key. For cross-shard analytics, pre-compute the view.

-- Shard-local OLTP: always include the shard key
SELECT * FROM transactions
WHERE customer_id = 42 AND txn_date >= '2024-01-01';
-- Goes to one shard. Fast.

-- Pre-computed materialized view for analytics
CREATE MATERIALIZED VIEW daily_summary AS
SELECT c.full_name, a.account_type, SUM(t.amount) AS daily_total, t.txn_date
FROM customers c
JOIN accounts a ON a.customer_id = c.customer_id
JOIN transactions t ON t.account_id = a.account_id
GROUP BY c.full_name, a.account_type, t.txn_date;
-- Pre-computed once, queried many times without re-joining

What should a senior engineer know?

A senior engineer knows that normalization is a write optimization and JOINs are its read cost, that the four scale pain points are scatter-gather, deep indexes, network-heavy intermediates, and uncacheable per-user results, and that the remedy is shard-local queries plus pre-computed views.