When to Use Nested Loop Joins

1
2
3
4
5
6
7
8
9
10
11
12

-- Example: Customer lookup with order details
-- Outer: 1 customer (after WHERE)
-- Inner: millions of orders with index on customer_id
 
SELECT c.name, o.order_date, o.total
FROM Customers c
JOIN Orders o ON c.id = o.customer_id
WHERE c.email = 'john@example.com';
 
-- INLJ: Read 1 customer, probe index ~4 times = ~5 I/Os
-- Hash Join: Build hash on Customers (1 row), scan Orders = millions of I/Os
-- Winner: INLJ by orders of magnitude

1
2
3
4
5
6
7
8
9
10
11

-- Example: Find overlapping time intervals
SELECT e1.event_name, e2.event_name
FROM Events e1
JOIN Events e2 
  ON e1.start_time < e2.end_time 
  AND e1.end_time > e2.start_time
  AND e1.id < e2.id;  -- Avoid duplicate pairs
 
-- Only nested loop can handle this predicate
-- No hash key exists (inequality conditions)
-- BNLJ with in-memory filtering is the only option

1
2
3
4
5
6
7
8
9
10
11
12

-- Example: Get 10 most recent orders with customer info
SELECT o.order_date, c.name, o.total
FROM Orders o
JOIN Customers c ON o.customer_id = c.id
ORDER BY o.order_date DESC
LIMIT 10;
 
-- With index on Orders(order_date DESC):
-- INLJ: Scan 10 orders (using index), probe Customers 10 times = ~50 I/Os
-- Hash Join: Build hash on Customers, scan ALL orders, sort, take 10 = massive
 
-- INLJ terminates after first 10 matches

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

-- Semi-join: Customers with at least one order
SELECT c.*
FROM Customers c
WHERE EXISTS (
    SELECT 1 FROM Orders o WHERE o.customer_id = c.id
);
 
-- INLJ advantage: Stop after FIRST match (not all matches)
-- For each customer, probe index—if match found, emit and move on
-- If typical customer has 100 orders, we examine 1 instead of 100
 
-- Anti-join: Customers with NO orders
SELECT c.*
FROM Customers c
WHERE NOT EXISTS (
    SELECT 1 FROM Orders o WHERE o.customer_id = c.id
);
 
-- INLJ: Probe index—if NO match, emit customer
-- Early termination on first match (to reject)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

-- Correlated subquery: Orders above customer's average
SELECT o.*
FROM Orders o
WHERE o.total > (
    SELECT AVG(o2.total) 
    FROM Orders o2 
    WHERE o2.customer_id = o.customer_id
);
 
-- Execution model is inherently nested loop:
-- For each order o:
--   Execute subquery with o.customer_id as parameter
--   Compare o.total against result
 
-- Index on Orders(customer_id) makes subquery efficient

1
2
3
4
5
6
7
8
9
10
11
12
13

-- Window function over ordered join result
SELECT 
    o.order_date,
    c.name,
    o.total,
    SUM(o.total) OVER (PARTITION BY c.id ORDER BY o.order_date) as running_total
FROM Orders o
JOIN Customers c ON o.customer_id = c.id
ORDER BY c.id, o.order_date;
 
-- If Orders is clustered by (customer_id, order_date):
-- INLJ preserves this order naturally
-- Hash join destroys order, requiring expensive re-sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14

-- Anti-pattern: Full join of two large tables
SELECT *
FROM Transactions t        -- 100 million rows
JOIN Accounts a            -- 10 million rows  
  ON t.account_id = a.id;  -- No WHERE clause
 
-- Hash join: Build hash on Accounts (10M rows), probe with Transactions
-- Cost: ~3 passes over each table = O(n + m)
 
-- BNLJ: Even with generous memory, scans Accounts hundreds of times
-- Cost: O(b_T + (b_T/M) × b_A) >> O(n + m)
 
-- INLJ: 100 million random index probes
-- Utterly catastrophic

1
2
3
4
5
6
7
8

-- Optimizer chose INLJ but no suitable index exists
EXPLAIN ANALYZE
SELECT * FROM Orders o
JOIN Customers c ON o.customer_email = c.email;  -- No index on Customers.email
 
-- Without index, INLJ degrades to repeated full scans of Customers
-- Effectively becomes O(n_orders × b_customers)
-- Solution: CREATE INDEX idx_customers_email ON Customers(email);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

-- Design indexes to support INLJ
 
-- Basic: Index on join key
CREATE INDEX idx_orders_customer ON Orders(customer_id);
 
-- Better: Covering index avoids data page access
CREATE INDEX idx_orders_customer_covering 
ON Orders(customer_id) 
INCLUDE (order_date, total, status);
 
-- Best: Clustered index if join key aligns with access pattern
-- (Note: Only one clustered index per table)
CREATE CLUSTERED INDEX idx_orders_clustered 
ON Orders(customer_id, order_date);
 
-- Composite index for multi-column joins
CREATE INDEX idx_order_items_composite 
ON OrderItems(order_id, product_id) 
INCLUDE (quantity, unit_price);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

-- Suboptimal: Filter after join
SELECT c.name, o.total
FROM Customers c
JOIN Orders o ON c.id = o.customer_id
WHERE o.order_date > '2024-01-01';  -- Filter after joining all orders
 
-- Optimal: Filter before join (optimizer should do this automatically)
-- But verify with EXPLAIN that the filter is applied early
 
-- Explicit approach using CTE or subquery (forces early filter):
WITH RecentOrders AS (
    SELECT * FROM Orders WHERE order_date > '2024-01-01'
)
SELECT c.name, o.total
FROM RecentOrders o
JOIN Customers c ON o.customer_id = c.id;

1
2
3
4
5
6
7
8
9
10
11
12

-- PostgreSQL: Increase work_mem for larger outer buffers
SET work_mem = '256MB';  -- Per-operation memory
SET effective_cache_size = '8GB';  -- Optimizer's cache size assumption
 
-- MySQL: Increase join buffer
SET SESSION join_buffer_size = 4 * 1024 * 1024;  -- 4MB
 
-- For BNLJ: Larger buffer = fewer inner scans
-- Formula: Scans = ⌈outer_blocks / (work_mem_blocks - 1)⌉
 
-- Monitor actual memory usage:
EXPLAIN (ANALYZE, BUFFERS, FORMAT YAML) SELECT ...;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

-- Accurate statistics enable correct algorithm selection
 
-- PostgreSQL: Update statistics
ANALYZE Customers;
ANALYZE Orders;
 
-- Increase statistics target for skewed columns
ALTER TABLE Orders ALTER COLUMN status SET STATISTICS 1000;
ANALYZE Orders;
 
-- MySQL: Update statistics
ANALYZE TABLE Customers, Orders;
 
-- SQL Server: Update with full scan for accuracy
UPDATE STATISTICS Customers WITH FULLSCAN;
UPDATE STATISTICS Orders WITH FULLSCAN;
 
-- Verify cardinality estimates match actuals:
EXPLAIN ANALYZE SELECT ... 
-- Compare "rows" (estimated) vs "actual rows" in output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- Disable competing join methods (session level)
SET enable_hashjoin = off;
SET enable_mergejoin = off;
-- Now only nested loop is available
 
-- For testing, examine all options:
SET enable_hashjoin = on;
SET enable_mergejoin = on;
SET enable_nestloop = on;
 
-- Compare plans with different settings:
EXPLAIN (ANALYZE) SELECT ... -- Note chosen method
SET enable_hashjoin = off;
EXPLAIN (ANALYZE) SELECT ... -- Force away from hash
 
-- Reset to default:
RESET enable_hashjoin;
RESET enable_mergejoin;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- Use optimizer hints (MySQL 8.0+)
SELECT /*+ NO_HASH_JOIN(o, c) */ 
    c.name, o.total
FROM Customers c
JOIN Orders o ON c.id = o.customer_id;
 
-- Force specific join order:
SELECT /*+ JOIN_ORDER(c, o) */
    c.name, o.total  
FROM Orders o
JOIN Customers c ON c.id = o.customer_id;
 
-- Force index usage (enables INLJ):
SELECT c.name, o.total
FROM Customers c
JOIN Orders o FORCE INDEX (idx_orders_customer)
  ON c.id = o.customer_id;
 
-- Block nested loop specific:
SET optimizer_switch = 'block_nested_loop=on';
SET optimizer_switch = 'batched_key_access=on,mrr=on';

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

-- Join hints in SQL Server
SELECT c.name, o.total
FROM Customers c
INNER LOOP JOIN Orders o ON c.id = o.customer_id;
-- Forces nested loop join
 
-- Compare with:
FROM Customers c
INNER HASH JOIN Orders o ON c.id = o.customer_id;
 
FROM Customers c
INNER MERGE JOIN Orders o ON c.id = o.customer_id;
 
-- Force join order with OPTION clause:
SELECT ...
FROM Customers c
JOIN Orders o ON ...
OPTION (FORCE ORDER);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

-- Original query: 15 seconds execution time
SELECT o.*, oi.product_name, oi.quantity
FROM Orders o
JOIN OrderItems oi ON o.id = oi.order_id
WHERE o.customer_id = 12345
  AND o.order_date BETWEEN '2024-01-01' AND '2024-03-31';
 
-- Problem: Optimizer chose hash join based on total table sizes
-- But WHERE clause reduces Orders to ~50 rows
 
-- Solution: Created composite index
CREATE INDEX idx_orders_cust_date ON Orders(customer_id, order_date);
 
-- Result: Optimizer now chooses INLJ
-- 50 probes into OrderItems via existing index
-- Execution time: 5ms (3000x improvement)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

-- Slowly Changing Dimension lookup
-- Find product price at time of each order
 
SELECT o.order_id, o.product_id, 
       p.price as price_at_order_time
FROM Orders o
JOIN ProductPriceHistory p 
  ON o.product_id = p.product_id
  AND o.order_date >= p.effective_from
  AND o.order_date < COALESCE(p.effective_to, '9999-12-31');
 
-- This theta-join cannot use hash join
-- BNLJ chosen, but slow for 10M orders × 1M price records
 
-- Optimization: Created range index and used partial scan
CREATE INDEX idx_price_history 
ON ProductPriceHistory(product_id, effective_from);
 
-- For each order, index finds relevant price range efficiently
-- Reduced from 45 minutes to 3 minutes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

-- API endpoint: Get page of user's recent activity
-- User sees first page in 100ms, scrolls for more
 
SELECT a.event_type, a.event_time, p.product_name
FROM UserActivity a
JOIN Products p ON a.product_id = p.id
WHERE a.user_id = 56789
ORDER BY a.event_time DESC
LIMIT 20 OFFSET 0;
 
-- Hash join: Must process ALL activity for user, sort, then limit
-- With 100K activity records: 8 seconds
 
-- INLJ with user_id index: 
-- Scan 20 activities (using index on user_id, event_time DESC)
-- Probe Products 20 times
-- Total: 20ms
 
-- Key: Index on (user_id, event_time DESC) enables index-order scan
CREATE INDEX idx_activity_user_time 
ON UserActivity(user_id, event_time DESC);