ReviseAlgo Logo

Query Optimization

Scans (Seq, Index, Bitmap) and Joins (Nested Loop, Hash, Merge)

How database algorithms execute lookup queries.

Last Updated: June 15, 2026•18 min read

1. Introduction

PostgreSQL uses different scan types to read table data and different join algorithms to combine tables. The query planner chooses the optimal combination based on table sizes, indexes, and statistics.

2. Why It Matters

  • Scan choice: Seq Scan reads all pages; Index Scan reads only matching pages. Wrong choice = 1000x slower.
  • Join choice: Hash Join builds a hash table; Nested Loop iterates. For large tables, wrong choice means hours vs seconds.

3. Real-World Analogy

Scans: Seq Scan = reading every page of a book to find "cat". Index Scan = using the index to jump to pages 23, 145. Bitmap Scan = noting all relevant pages first, then reading them in disk order. Joins: Nested Loop = for each person in room A, check every person in room B. Hash Join = give everyone name tags, then match instantly.

4. How It Works

5. Internal Architecture

6. Visual Explanation

7. Practical Example

8. Common Mistakes

Assuming index scan is always faster

For queries returning >15% of the table, Seq Scan is faster because sequential I/O beats random index lookups.

9. Quick Quiz

Q1: When is Bitmap Scan better than Index Scan?

Answer: When multiple indexes could contribute (BitmapAnd/BitmapOr) or when reading 5-15% of the table. Bitmap Scan reads pages in disk order, reducing random I/O.

10. Scenario-Based Challenge

Challenge: Join Optimization

A report joins 5 tables (100K, 1M, 10M, 50M, 100M rows). Analyze the EXPLAIN output and suggest which join types and indexes would optimize this query.

11. Debugging Exercise

Nested Loop Join taking 30 seconds. Why?

Issue: Outer table has 100K rows, inner scan takes 0.3ms each. 100K × 0.3ms = 30s. Fix: Add index on inner table's join column to reduce inner scan to 0.01ms, or force Hash Join.

12. Interview Questions

Q1: When does PostgreSQL choose Hash Join over Nested Loop?

A: Hash Join when both tables are large and the join column isn't indexed. Nested Loop when the outer table is small or the inner table has an index on the join column.

13. Production Considerations

  • work_mem for Hash Join: Increase work_mem if EXPLAIN shows "Batches: 4" in Hash Join (spilling to disk).
  • Index FK columns: Missing FK indexes force Nested Loop with Seq Scan on the inner table — extremely slow for large tables.