Indexing

Table: users (100,000,000 rows)
Query: SELECT * FROM users WHERE email = 'alice@mail.com'

Without index (full table scan):
  → Read all 100M rows from disk
  → Check each row's email column
  → Time: O(n) = ~100,000,000 comparisons
  → Duration: 5-30 seconds (depending on disk speed)

With B-tree index on email:
  → Navigate the tree: ~27 levels (log₂ 100M)
  → Each level = 1 disk read
  → Find the row pointer → read 1 row
  → Time: O(log n) = ~27 comparisons
  → Duration: 0.1-1ms

Speedup: ~100,000x

B-tree index on users.email (branching factor ~100)

Query: WHERE email = 'martinez@mail.com'

Level 0 (root):     [... garcia ... lee ... patel ... zhang ...]
                     → 'martinez' is between 'lee' and 'patel'
                     → Follow pointer to child node

Level 1 (internal): [... kim ... lin ... martinez ... miller ...]
                     → Found 'martinez'!
                     → Follow pointer to leaf node

Level 2 (leaf):     [martinez@mail.com → row_id: 4,827,391]
                     → Read row 4,827,391 from the table

Total: 3 disk reads to find 1 row out of millions.

For 100M rows with branching factor 100:
  Levels needed = log₁₀₀(100M) ≈ 4 levels
  4 disk reads to find any row. Always.

WRITE: SET user:42 = "Alice"
  1. Append to WAL (durability)           → ~0.01ms
  2. Insert into memtable (in-memory)     → ~0.001ms
  Done. Total: ~0.01ms

  Later (async): memtable full → flush to SSTable on disk

READ: GET user:42
  1. Check memtable                       → found? return.
  2. Check SSTable L0 (newest)            → bloom filter says NO → skip
  3. Check SSTable L1                     → bloom filter says MAYBE → read → found!
  Done. Total: 1-5 disk reads

COMPACTION (background):
  L0: [SST1] [SST2] [SST3]  → merge → L1: [SST_merged]
  Removes duplicates, deleted keys, reduces file count

CREATE INDEX idx_user_status_date ON orders(user_id, status, created_at);

-- ✅ Uses the index (leftmost prefix: user_id)
SELECT * FROM orders WHERE user_id = 42;

-- ✅ Uses the index (prefix: user_id + status)
SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

-- ✅ Uses the full index (all 3 columns)
SELECT * FROM orders
WHERE user_id = 42 AND status = 'shipped' AND created_at > '2024-01-01';

-- ❌ CANNOT use this index (skips user_id)
SELECT * FROM orders WHERE status = 'shipped';

-- ❌ CANNOT use this index (skips user_id and status)
SELECT * FROM orders WHERE created_at > '2024-01-01';

-- ⚠️ Uses only user_id part (skips status, jumps to created_at)
SELECT * FROM orders WHERE user_id = 42 AND created_at > '2024-01-01';

Index: (A, B, C)

Query filters on:    Uses index?    How much?
A                    ✅ Yes         Full prefix (A)
A, B                 ✅ Yes         Full prefix (A, B)
A, B, C              ✅ Yes         Full index (A, B, C)
B                    ❌ No          Skips A (leftmost column)
C                    ❌ No          Skips A and B
B, C                 ❌ No          Skips A
A, C                 ⚠️ Partial    Uses A only, skips B to reach C

Rule: the index is used left-to-right. You can stop early,
but you cannot skip columns in the middle.

-- Full index: indexes ALL 100M users (including inactive)
CREATE INDEX idx_email ON users(email);
-- Size: ~2 GB, updated on every user insert/update

-- Partial index: indexes only active users (5% of total)
CREATE INDEX idx_active_email ON users(email) WHERE is_active = true;
-- Size: ~100 MB, updated only when active users change

-- Partial index: only unprocessed orders
CREATE INDEX idx_pending ON orders(created_at) WHERE status = 'pending';
-- Size: tiny (only pending orders, not the 99% that are completed)

-- Query that uses the partial index:
SELECT * FROM users WHERE email = 'alice@mail.com' AND is_active = true;
-- → Uses idx_active_email (small, fast)

-- Query that CANNOT use the partial index:
SELECT * FROM users WHERE email = 'alice@mail.com' AND is_active = false;
-- → Cannot use idx_active_email (condition doesn't match)

-- Query: get name and email for active users
SELECT name, email FROM users WHERE is_active = true;

-- Regular index (NOT covering):
CREATE INDEX idx_active ON users(is_active);
-- Step 1: Use index to find row IDs where is_active = true
-- Step 2: For EACH row ID, read the full row from the table (random I/O!)
-- Step 3: Extract name and email from the full row
-- → Slow: millions of random disk reads

-- Covering index (includes all needed columns):
CREATE INDEX idx_active_covering ON users(is_active) INCLUDE (name, email);
-- Step 1: Use index to find entries where is_active = true
-- Step 2: name and email are IN the index → return directly
-- → Fast: no table access needed, sequential index scan only

-- PostgreSQL EXPLAIN output:
-- "Index Only Scan using idx_active_covering"  ← covering index used!
-- vs
-- "Index Scan using idx_active"                ← table lookup needed

-- Query 1: Product search by category + price sort
SELECT id, name, price, image_url
FROM products
WHERE category_id = 5 AND in_stock = true
ORDER BY price ASC
LIMIT 20;

→ Composite index: (category_id, in_stock, price)
  Equality columns first, range/sort column last.
→ Covering index: INCLUDE (name, image_url)
  Avoids table lookup for listing page.

CREATE INDEX idx_product_search
  ON products(category_id, in_stock, price)
  INCLUDE (name, image_url);


-- Query 2: User's order history
SELECT id, total, status, created_at
FROM orders
WHERE user_id = 42
ORDER BY created_at DESC
LIMIT 10;

→ Composite index: (user_id, created_at DESC)
  user_id for filtering, created_at for sorting.
→ Covering index: INCLUDE (total, status)

CREATE INDEX idx_user_orders
  ON orders(user_id, created_at DESC)
  INCLUDE (total, status);


-- Query 3: Admin dashboard — pending orders count
SELECT COUNT(*) FROM orders WHERE status = 'pending';

→ Partial index: only pending orders (0.5% of total)

CREATE INDEX idx_pending_orders
  ON orders(status)
  WHERE status = 'pending';
  -- Indexes 1M rows instead of 200M. 200x smaller.


-- Query 4: Login by email
SELECT id, name, password_hash FROM users WHERE email = 'alice@mail.com';

→ Unique index on email (also enforces uniqueness)
→ Covering: INCLUDE (name, password_hash)

CREATE UNIQUE INDEX idx_user_email
  ON users(email)
  INCLUDE (name, password_hash);