KAHIBARO
Discord Login Register ☰
☰

26.6 Indexing

Table of Contents

Why Indexes Matter for Performance

Indexes are one of the most powerful tools for speeding up database queries. Used correctly, they can make a slow query thousands of times faster. Used wrongly, they can slow down writes and waste memory.

This chapter focuses on indexing from a performance and scalability perspective. It assumes you already know basic database concepts and what an index is at a high level.

Key idea: An index lets the database find rows without scanning the whole table. You trade extra storage and slower writes for much faster reads.

How Indexes Affect Query Performance

Full table scan vs indexed lookup

Imagine a users table with 10 million rows.

sql 
SELECT * FROM users WHERE email = 'alice@example.com';

Without an index on email, the database must:

  1. Start at the first row.
  2. Check email value.
  3. Move to the next row.
  4. Repeat until it finds matching rows or reaches the end.

This is a full table scan. Time grows roughly with the number of rows, $O(n)$.

With an index on email:

sql 
CREATE INDEX idx_users_email ON users (email);

The database can:

  1. Search the index structure (for example a B-tree) to find the right position.
  2. Jump directly to the matching row(s).

This lookup is typically $O(\log n)$ and involves far fewer disk pages.

Very roughly:

RowsFull Scan (no index)Indexed Lookup (B-tree)
1,000~1,000 checks~10 checks
1,000,000~1,000,000 checks~20 checks
100M~100,000,000 checks~27 checks

The exact numbers vary, but the pattern is stable: indexes scale much better as data grows.

Selectivity and cardinality

Indexes are fastest when they are selective, meaning they greatly reduce the number of rows the database must inspect.

Example:

sql 
SELECT * FROM orders WHERE status = 'PAID';

If 90% of orders are PAID, the index on status will not filter much. The database might choose a table scan instead, because jumping around through the index and table can be slower than a simple sequential scan.

Rule: Index columns that significantly reduce the number of rows to scan. High selectivity makes indexes effective.

Reading Queries Through the Lens of Indexes

Identifying the “filter columns”

Look at a query and mark the parts that filter rows:

sql 
SELECT id, email
FROM users
WHERE country = 'US'
  AND is_active = true
  AND created_at >= '2024-01-01'
ORDER BY created_at DESC
LIMIT 20;

Indexing goals:

  1. Help the database filter quickly by the WHERE clause.
  2. Help it avoid a sort for ORDER BY if possible.
  3. Combine both so it can find the top 20 rows quickly.

A possible composite index:

sql 
CREATE INDEX idx_users_country_active_created
ON users (country, is_active, created_at DESC);

This index can:

Range queries and indexes

Range conditions like >=, >, <, BETWEEN use indexes efficiently when they appear at the end of an index.

Example:

sql 
SELECT *
FROM orders
WHERE customer_id = 123
  AND created_at >= '2024-01-01';

Index:

sql 
CREATE INDEX idx_orders_customer_created
ON orders (customer_id, created_at);

This index structure is grouped by customer_id. Inside each group, rows are ordered by created_at. To handle the query:

  1. Find the first index entry with customer_id = 123 and created_at >= '2024-01-01'.
  2. Scan forward until customer_id changes.

Very few rows are touched if the user has few orders.

If you reversed the index:

sql 
CREATE INDEX idx_orders_created_customer
ON orders (created_at, customer_id);

This is worse for the same query, because:

Rule: For composite indexes, put equality filters first, then range filters.

How Indexes Affect Writes and Storage

Indexes improve read performance, but they are not free.

Inserts, updates, and deletes

When you:

sql 
INSERT INTO users (id, email) VALUES (...);

the database must:

  1. Insert the row into the table.
  2. Update every index that touches id or email.

Similarly, when you UPDATE or DELETE rows, indexes must be maintained.

Effects:

A table with 10 indexes will have much slower inserts than a table with 2 well chosen indexes.

Rule: Indexes speed up reads, but slow down writes. Do not index every column by default.

Storage and memory

Indexes take disk space and memory.

On a busy system, extra indexes can:

Index maintenance over time

Indexes also influence:

From a scalability point of view, too many or poorly designed indexes can become a serious operational cost.

Types of Indexes and When to Use Them

Different database engines have different index types. Here we stay at a conceptual level.

B-tree indexes

Most common default index type.

Good for:

Most of your indexes in OLTP (online transaction processing) systems will be B-tree like structures.

Hash indexes

Optimized for equality checks, for example WHERE session_token = 'xyz'.

Limitations often include:

For many workloads B-tree is still the best default.

Covering indexes

A covering index is an index that contains all the columns needed for a query, so the database does not have to read the base table at all.

Example query:

sql 
SELECT id, email
FROM users
WHERE email LIKE 'alice%@example.com';

If the index is:

sql 
CREATE INDEX idx_users_email
ON users (email);

The database:

If you create a covering index:

sql 
-- Syntax varies by database, concept is what matters
CREATE INDEX idx_users_email_id
ON users (email, id);

Now, the index has both email and id. The database might satisfy the entire query from the index, which saves I/O.

Covering indexes are especially useful for frequent, performance critical queries that read few columns.

Rule: Use covering indexes for hot, simple queries where avoiding table lookups is worth extra index storage.

Designing Composite Indexes for Performance

Index column order

For an index on (a, b, c):

This is sometimes called the left prefix rule.

Example:

sql 
CREATE INDEX idx_orders_customer_status_created
ON orders (customer_id, status, created_at);

Useful for queries like:

sql 
-- 1. Uses (customer_id)
SELECT * FROM orders WHERE customer_id = 123;
-- 2. Uses (customer_id, status)
SELECT * FROM orders WHERE customer_id = 123 AND status = 'PAID';
-- 3. Uses (customer_id, status, created_at)
SELECT * FROM orders
WHERE customer_id = 123 AND status = 'PAID'
ORDER BY created_at DESC;

But less useful for:

sql 
-- Cannot fully use the index, no customer_id
SELECT * FROM orders WHERE status = 'PAID';

So choose the column order based on actual query patterns, not just "what seems important."

Combining WHERE and ORDER BY

Try to support both filtering and sorting with one index.

Example query:

sql 
SELECT *
FROM products
WHERE category_id = 5
ORDER BY price ASC
LIMIT 50;

Index:

sql 
CREATE INDEX idx_products_category_price
ON products (category_id, price);

Benefits:

If you instead only had:

sql 
CREATE INDEX idx_products_category ON products (category_id);

The database:

  1. Uses the index to find all products with category_id = 5.
  2. Collects them, then sorts them by price.
  3. Returns the top 50.

This is slower, especially for large categories.

Multiple indexes vs one composite index

Sometimes you might think:

sql 
CREATE INDEX idx_users_country ON users (country);
CREATE INDEX idx_users_is_active ON users (is_active);

for:

sql 
SELECT * FROM users
WHERE country = 'US' AND is_active = true;

Whether this is good or not depends on the database. Some can combine indexes, using both. But usually a single composite index is more effective:

sql 
CREATE INDEX idx_users_country_is_active
ON users (country, is_active);

The composite index keeps the combination of values together, often reducing work.

Indexing Patterns for Common Workloads

Point lookups

Use case: Find a single row by unique key.

Example:

sql 
SELECT * FROM users WHERE id = 42;

Backend pattern: Getting a user by ID for authentication, showing a profile, etc.

Index design:

Another example:

sql 
SELECT * FROM users WHERE email = 'alice@example.com';

If email must be unique:

sql 
CREATE UNIQUE INDEX idx_users_email ON users (email);

Use unique indexes to:

Recent data queries

Use case: "Latest N" items, like last 100 orders, last 50 log entries.

Example:

sql 
SELECT *
FROM logs
ORDER BY created_at DESC
LIMIT 100;

Index:

sql 
CREATE INDEX idx_logs_created_at_desc
ON logs (created_at DESC);

The database can:

Very common in dashboards and activity feeds.

Time range queries

Use case: Data for a given time window.

sql 
SELECT *
FROM orders
WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31';

Index:

sql 
CREATE INDEX idx_orders_created_at
ON orders (created_at);

With additional filters:

sql 
SELECT *
FROM orders
WHERE customer_id = 123
  AND created_at >= '2024-01-01'
  AND created_at < '2024-02-01';

Index:

sql 
CREATE INDEX idx_orders_customer_created
ON orders (customer_id, created_at);

Pagination

Pattern:

sql 
SELECT *
FROM products
WHERE category_id = 7
ORDER BY id
LIMIT 20 OFFSET 1000;

Offset-based pagination can be slow because the database must skip and count many rows.

Better pattern for performance: keyset pagination (also called cursor-based):

sql 
-- First page
SELECT *
FROM products
WHERE category_id = 7
ORDER BY id
LIMIT 20;
-- Next page, use last id from previous page
SELECT *
FROM products
WHERE category_id = 7
  AND id > :last_id
ORDER BY id
LIMIT 20;

Index:

sql 
CREATE INDEX idx_products_category_id
ON products (category_id, id);

This index lets the database jump directly to category_id = 7 and id > last_id and then scan forward.

From a backend perspective, designing pagination that works well with indexes is crucial for scalability.

Avoiding Common Indexing Pitfalls

Indexing every column

It is easy to think: "Indexes make queries faster, so let us add one on every column."

Problems:

Instead:

Ignoring the query planner

Relational databases have tools to show query plans, such as EXPLAIN in PostgreSQL and MySQL.

Example:

sql 
EXPLAIN ANALYZE
SELECT * FROM users WHERE email = 'alice@example.com';

This shows:

Use these tools to:

Functions on indexed columns

This overlaps with more detailed SQL topics, but the performance idea is:

sql 
SELECT *
FROM users
WHERE LOWER(email) = 'alice@example.com';

If you have an index on email, the database might not use it, because LOWER(email) prevents direct index lookup.

Possible fix:

Overlapping indexes

Example:

sql 
CREATE INDEX idx_orders_customer ON orders (customer_id);
CREATE INDEX idx_orders_customer_status ON orders (customer_id, status);

The first index is mostly covered by the second. You might not need both.

Too many overlapping indexes:

Regularly review your index list and remove unused or redundant ones.

Monitoring and Evolving Index Strategy

Measuring index usage

Production databases expose statistics:

By monitoring:

Adapting to changing query patterns

As your backend grows:

Your index strategy should evolve:

  1. When adding new features, think about their queries and necessary indexes.
  2. Periodically review index usage in production.
  3. Clean up obsolete indexes.

Treat indexes as part of your performance-focused API design, not as a one-time database detail.

Practical workflow

A simple workflow when debugging a slow query:

  1. Get the exact SQL query the application sends.
  2. Run EXPLAIN or equivalent to see the plan.
  3. Check if a full table scan is happening.
  4. Identify filter, join, and sort columns.
  5. Design a candidate index that helps with the biggest cost.
  6. Create index in a test or staging environment.
  7. Re-run EXPLAIN and measure execution time.
  8. If improved, roll out carefully to production.

Over time, this workflow becomes a normal part of backend performance tuning.

Summary

Indexes are a central tool in backend performance and scalability:

By understanding indexing at this practical level, you can design schemas and queries that scale far better as your application and data grow.

Views: 6

Comments

Please login to add a comment.

Don't have an account? Register now!

© 2025 Kahibaro
Visitors: 3159 / 24h
Impressum / Imprint
Datenschutz / Data Policy