Indexes

Backend Fundamentals · Databases · 8 min read

1. What problem does this solve?

• Problem
  Databases store data in tables that are essentially unordered collections of rows. When you run a query like SELECT * FROM users WHERE email = 'alice@example.com', the database has to look at every row until it finds a match. This is called a full table scan.

• Why it matters
  Full scans are linear in the number of rows. On a table with millions of rows, a scan can take hundreds of milliseconds or even seconds, which is unacceptable for interactive web services, real‑time APIs, or batch jobs that run frequently.

• What happens if you don’t use indexes

  • Slow query response times → poor user experience.
  • High CPU and I/O load → contention with other queries.
  • Inability to scale horizontally because each node must scan the entire dataset.

• Where it appears in real backend systems

  • User authentication (WHERE username = ?).
  • E‑commerce order lookups (WHERE order_id = ?).
  • Log aggregation (WHERE timestamp >= ?).
  • AI inference pipelines that filter data by tags or timestamps.

2. Mental model

Analogy

Think of a library. If every book is just stacked on a shelf, finding a specific title means walking through every book. A library index (the card catalog) lets you jump directly to the shelf and page where the book is.

Engineering model

A database index is a data structure that maps a key (e.g., email) to the physical location of rows that contain that key. The most common structure is a B‑tree, which keeps keys sorted and allows binary search in logarithmic time.

3. Deep explanation

Trade‑offs

Failure modes

• Stale statistics → planner chooses a full scan even though an index exists.
• Fragmented index → slower lookups, higher I/O.
• Missing index on a hot column → catastrophic performance degradation.
• Index corruption (rare) → queries fail or return wrong results.

Limitations

• Not all queries benefit (e.g., SELECT * FROM table without a WHERE).
• High write workloads can negate the benefits.
• Certain data types (e.g., arrays, JSONB) require specialized index types.
• Indexes do not help with clustering (physical ordering) unless you use a clustered index (PostgreSQL’s CLUSTER command).

Where it fits in a backend architecture

┌─────────────────────┐
│  Application Layer  │
│  (Node.js / FastAPI)│
└────────────┬────────┘
             │
             ▼
┌─────────────────────┐
│  Database Layer     │
│  (PostgreSQL, etc.) │
└────────────┬────────┘
             │
             ▼
┌─────────────────────┐
│  Storage Layer      │
│  (SSD, HDD)         │
└─────────────────────┘

The index lives in the Database Layer and is consulted by the query planner before the query is executed on the Storage Layer.

Interaction with related concepts

• Caching: Even with a cache, indexes reduce the load on the database.
• Sharding: Each shard must maintain its own indexes.
• Replication: Indexes are replicated automatically.
• ORMs: Many ORMs expose index creation via migrations (e.g., Prisma, TypeORM).

4. How it works

1. Query received by the database.
2. Planner reads the query, looks at statistics.
3. Planner decides whether an index can satisfy the WHERE clause.
4. If yes, index lookup:
   • Traverse the B‑tree from root to leaf.
   • Each node comparison reduces the search space by ~50%.
5. Retrieve row pointers from leaf nodes.
6. Fetch rows from the table (unless a covering index suffices).
7. Return result to the application.

sequenceDiagram
    participant App as Application
    participant DB as PostgreSQL
    participant Index as B‑Tree Index
    participant Table as Table Data

    App->>DB: SELECT * FROM users WHERE email = 'alice@example.com';
    DB->>DB: Planner reads statistics
    DB->>Index: Lookup key 'alice@example.com'
    Index->>Index: Traverse B‑Tree
    Index->>DB: Return row pointer(s)
    DB->>Table: Fetch row(s)
    DB->>App: Return result

5. Practical implementation

5.1 PostgreSQL index with Node.js (pg)

// db.ts
import { Pool } from 'pg';

export const pool = new Pool({
  connectionString: process.env.DATABASE_URL,
});

// migrations/create_user_index.ts
import { pool } from './db';

async function createIndex() {
  await pool.query(`
    CREATE INDEX IF NOT EXISTS idx_users_email
    ON users (email);
  `);
  console.log('Index created');
}

createIndex().catch(console.error);

// queries/findUserByEmail.ts
import { pool } from './db';

export async function findUserByEmail(email: string) {
  const res = await pool.query(
    'SELECT id, username, email FROM users WHERE email = $1',
    [email]
  );
  return res.rows[0];
}

Important lines

• CREATE INDEX IF NOT EXISTS ensures idempotent migrations.
• ON users (email) creates a B‑tree index on the email column.
• Parameterized query ($1) protects against SQL injection.

5.2 Redis sorted set as an index

// redisIndex.ts
import { createClient } from 'redis';

const client = createClient();
await client.connect();

// Add a user ID to the index keyed by email
async function indexUser(email: string, userId: string) {
  await client.zAdd(`idx:users:email`, { score: 0, value: userId });
  // Store mapping from email to userId
  await client.hSet(`user:${userId}`, 'email', email);
}

// Query by email
async function getUserIdByEmail(email: string) {
  const userId = await client.zScore(`idx:users:email`, email);
  return userId;
}

Redis sorted sets are a simple key‑value index that can be used for small‑scale lookups or as a cache layer.

6. Production considerations

7. Common mistakes

8. Senior engineer perspective

Design decisions at scale

• Index strategy:

  • Use composite indexes that match the most common query patterns.
  • Prefer partial indexes for hot subsets (e.g., WHERE status = 'active').
  • Consider covering indexes for read‑heavy workloads.

• Trade‑offs:

  • Write‑heavy systems may need to limit indexes or use write‑optimized storage (e.g., UNLOGGED tables).
  • Storage cost vs. query latency: evaluate with real metrics.

• Bottlenecks:

  • Index rebuilds can lock tables; use REINDEX CONCURRENTLY.
  • High contention on hot index pages; consider sharding or read replicas.

• Failure scenarios:

  • Index corruption: run REINDEX or restore from backup.
  • Missing index: monitor query plans for full scans.

• Monitoring:

  • pg_stat_user_indexes for hit ratios.
  • pg_stat_user_tables for index scans vs. sequential scans.
  • Alert on high seq_scan ratio.

• Cost/performance:

  • Estimate disk usage: pg_indexes_size('table_name').
  • Benchmark query latency before/after index changes.

• When NOT to use:

  • Small tables (< 1 k rows).
  • Extremely high write throughput where index maintenance dominates.
  • Queries that touch almost all rows (e.g., WHERE age > 0 on a table of 10 M rows).

9. Interview questions

10. Hands‑on task

Goal: Add a composite index to the orders table in the repository’s PostgreSQL database and measure the performance impact.

1. Create the index

   await pool.query(`
     CREATE INDEX IF NOT EXISTS idx_orders_user_date
     ON orders (user_id, created_at DESC);
   `);
   

2. Run a benchmark

   • Use pgbench or a simple Node.js script that executes a query like:

     SELECT * FROM orders WHERE user_id = $1 ORDER BY created_at DESC LIMIT 10;
     

   • Measure execution time before and after adding the index.

3. Analyze the plan

   const res = await pool.query(`EXPLAIN (ANALYZE, BUFFERS) SELECT ...`);
   console.log(res.rows.map(r => r['QUERY PLAN']).join('\n'));
   

4. Document findings

   • Record the query times, plan differences, and any changes in I/O or CPU usage.

11. Quick revision

• Indexes are data structures that map key values to row locations.
• B‑tree is the default index type; GiST, SP‑GiST, GIN for specialized data.
• Indexes speed up WHERE, ORDER BY, GROUP BY, and join predicates.
• Write operations incur extra I/O to maintain indexes.
• Use EXPLAIN to verify index usage.
• Partial indexes target hot subsets; covering indexes avoid table lookups.
• Monitor pg_stat_user_indexes and pg_stat_user_tables.
• Rebuild indexes with REINDEX CONCURRENTLY to avoid locking.
• Drop unused indexes to reduce write overhead.
• Keep statistics up‑to‑date with ANALYZE.
• Indexes are stored in plain text; encrypt sensitive columns if needed.
• In high‑write workloads, consider sharding or read replicas to distribute index maintenance.

12. References

• PostgreSQL Documentation – Indexes
• PostgreSQL Documentation – Index Types
• PostgreSQL Documentation – Query Planner and Optimizer
• Node.js pg Library – Official Docs
• Prisma Migrations – Creating Indexes
• Redis – Sorted Sets