SQL Basics — Joins, Indexes, Transactions

A JOIN operation combines columns from two or more tables based on a related attribute:

• INNER JOIN: Returns records that have matching values in both tables.
• LEFT OUTER JOIN: Returns all records from the left table, along with matching records from the right table. If no match exists, right-side columns contain NULL.
• RIGHT OUTER JOIN: Returns all records from the right table, along with matching records from the left table.
• FULL OUTER JOIN: Returns all records when there is a match in either the left or right table.
• CROSS JOIN: Computes the Cartesian Product (M × N rows), pairing every row in Table A with every row in Table B.

While developers write declarative SQL (SELECT * FROM a JOIN b ON a.id = b.a_id), the database query optimizer chooses one of three physical algorithms to execute the join:

1. Nested Loop Join (Index-Driven)

The engine iterates through the outer table row by row, and for each row, looks up matching rows in the inner table using a B-Tree index.

• Time Complexity: O(M × log N) where M is the outer table size and N is the inner table size.
• Best For: Small driving table joining an inner table with an indexed foreign key.

2. Hash Join (Memory-Intensive)

The engine scans the smaller table and constructs an in-memory Hash Table keyed on the join attribute. It then scans the larger table, hashing each row's join key to probe the hash table in O(1) time.

• Time Complexity: O(M + N) linear execution time.
• Best For: Large datasets where neither table is indexed on the join key, and the join operator is an equality comparison (=).

3. Sort-Merge Join (Pre-Sorted Streaming)

The engine sorts both tables on the join key (or uses existing B-Tree index orders) and steps through both sorted streams simultaneously in linear time.

• Best For: Joining pre-sorted indexed columns or handling non-equality range joins (a.val >= b.val).

The N+1 Query Problem is the most common cause of catastrophic database latency in microservices using Object-Relational Mappers (Hibernate, Prisma, TypeORM, ActiveRecord):

typescript
Copy
// THE DISASTER: Generates 101 separate SQL queries!
const orders = await db.orders.findMany({ limit: 100 }); // Query 1: Fetches 100 orders

for (const order of orders) {
  // Queries 2..101: Executes 100 individual SQL queries for each customer!
  const user = await db.users.findById(order.userId);
}

The Solution: Eager Loading / SQL IN Join:

sql
Copy
-- Single query joins both tables in O(1) network roundtrip:
SELECT orders.*, users.name, users.email 
FROM orders 
INNER JOIN users ON orders.user_id = users.id 
LIMIT 100;