Database Indexing, What, When and How

A query is slow:

SELECT * FROM orders WHERE customer_id = 123;

The usual fix is to add an index on customer_id, and it works. But the moment your query grows a second condition -

SELECT * FROM orders WHERE customer_id = 123 AND total < 10;

• the "just add an index" advice runs out, and most people guess. This post is about not guessing: how an index actually works, how to build the right one for queries like that, what and when to index, the real costs of indexing, when indexing simply cannot fix a scale problem, and why the indexing story in NoSQL comes with serious catches. It builds on the database fundamentals.

Why the query is slow, and what an index does

Without an index, WHERE customer_id = 123 forces a sequential scan: the database reads every row in the table and checks each one. On a million-row table that is a million reads to find maybe five rows. You can see it:

EXPLAIN SELECT * FROM orders WHERE customer_id = 123;

Seq Scan on orders  (cost=0.00..18334.00 rows=5 width=...)
  Filter: (customer_id = 123)

An index is a separate, sorted copy of the indexed column(s) with a pointer back to each row - almost always a B-tree: a balanced tree kept in sorted order, so the database walks from the root to the right leaf in O(log n) instead of scanning O(n). Because the leaves are sorted and linked, a B-tree is fast at four things: equality lookups (= 123), range scans (BETWEEN, <, >), sorted retrieval (ORDER BY), and min/max. Create it and the same query becomes an index scan:

CREATE INDEX idx_orders_customer ON orders (customer_id);

Index Scan using idx_orders_customer on orders  (rows=5 ...)
  Index Cond: (customer_id = 123)

A million-row scan became a handful of tree hops. That is the whole promise of an index - and also the whole reason its column order matters once you have more than one condition.

The real question: customer_id = 123 AND total < 10

You have two honest options.

Option 1 - index customer_id only, filter the rest. If customer_id = 123 already narrows the table to five rows, the database uses idx_orders_customer to find those five and then checks total < 10 on each. Perfectly fine when the first column is selective (few matching rows). Nothing more is needed.

Option 2 - a composite index on (customer_id, total). When customer_id matches many rows and total < 10 cuts it down a lot, you want both conditions satisfied by the index itself. A composite index is a copy sorted by the first column, then by the second within each first-column group. So (customer_id, total) is sorted by customer_id, and within each customer, by total:

CREATE INDEX idx_orders_cust_total ON orders (customer_id, total);

Now WHERE customer_id = 123 AND total < 10 is a single, tight operation: seek straight to the customer_id = 123 block, and because that block is itself sorted by total, total < 10 is a contiguous range at the start of it. One seek, one short range scan.

Column order is the whole game: equality first, range last

Here is the rule that answers the question and a hundred like it:

Put the columns with equality conditions first, then one column with a range condition last.

Why? Reverse the index to (total, customer_id) and watch it fall apart. Now the copy is sorted by total first. total < 10 is a range, so it is scattered across the whole low end of the index - and customer_id = 123 rows sit anywhere within that range, not together. The database can use the index to satisfy total < 10, but then has to check customer_id on every one of those rows. You got one condition from the index instead of two.

The general form, for an index on (a, b, c):

• Fully served: a = 1 AND b = 2 AND c = 3, and a = 1 AND b = 2 AND c > 10, and a = 1 AND b > 5, and a = 1.
• Not served well: b = 2 alone, or c = 3 alone - because of the leftmost-prefix rule: the index is only usable from the left, up to and including the first range, with no gaps. A column with no condition is a gap that ends the usable prefix.

Two consequences worth burning in:

• Only one range column earns its place. After the first <, >, or BETWEEN, later columns can only filter, not seek - so a = 1 AND b > 5 AND c > 3 uses the index for a and b, and c is just a filter.
• The index also gives you the sort for free. WHERE customer_id = 123 ORDER BY total needs no separate sort step, because idx_orders_cust_total already stores that customer's rows in total order.

For the deep, worked treatment of exactly this, Use The Index, Luke and the MySQL index cookbook are the canonical references, and the PostgreSQL indexes docs cover the specifics for Postgres.

Covering indexes: never touch the table

If an index contains every column a query needs, the database answers straight from the index and never reads the table at all - an index-only scan. Add the returned columns to the index (or, in Postgres, INCLUDE them):

CREATE INDEX idx_cover ON orders (customer_id, total) INCLUDE (status);
-- SELECT status FROM orders WHERE customer_id = 123 AND total < 10;  -> index-only

This is the single biggest win for a hot read query, because it removes the trip back to the table entirely.

What to index

Index the columns your queries actually filter, join, and sort on:

• Columns in WHERE, JOIN ... ON, ORDER BY, and GROUP BY.
• Foreign keys - joins hammer them.
• High-selectivity columns - ones with many distinct values, so a lookup narrows to few rows.

And do not bother indexing low-selectivity columns. If WHERE status = 'active' matches more than roughly 20% of the table, the optimizer will ignore the index and scan anyway - bouncing between index and table for a fifth of the rows is slower than reading the table straight through. An index on a boolean or a two-value flag is usually dead weight.

When to index - and when not to

Index when: you have confirmed a slow query with EXPLAIN, the table is large, the workload is read-heavy, and the predicate is selective. Index for real queries you run, not hypothetical ones.

Do not index when: the table is tiny (a scan is already instant), the column is low-selectivity, the query runs rarely, or - critically - the table is write-heavy on a hot path, because every index you add taxes every write. Which brings us to the costs.

The disadvantages of indexing

Indexes are not free, and over-indexing is a real, common mistake:

• Write amplification. Every INSERT, UPDATE, and DELETE must update every index on the table, in sorted position. Five indexes means a write does its own work plus five index maintenances. On a write-heavy table this is the dominant cost, and it is why you do not "just index everything."
• Storage. An index is a copy of its columns; a few well-chosen indexes can rival the size of the table itself.
• Memory pressure. Indexes compete with table data for the buffer cache; bloated or unused indexes evict pages you actually needed.
• Maintenance and drift. Indexes fragment and bloat over time (needing VACUUM/REINDEX), and the more indexes you have, the more ways the query planner can pick the wrong one and make a query slower, not faster.
• Updating an indexed column is extra costly - the row has to move to its new sorted position in the index, not just change in place.

The discipline: add an index to fix a measured slow query, then check that it did not wreck your write throughput. Indexes you cannot tie to a real query should be dropped.

When indexing cannot save you - the scale ceiling

This is the part people miss. An index makes one machine's queries faster; it does not add capacity. So indexing hits a wall in exactly the cases where you most want a magic fix:

• Write-heavy workloads. Indexes slow writes down. You cannot index your way to higher write throughput - past a point that is a job for partitioning and sharding, not indexes (the scaling a database ladder - cache, replicas, shards - takes over here).
• Data or traffic beyond one node. If the working set or write volume exceeds what a single machine can hold or handle, no index changes that. You need read replicas for read capacity and sharding for write/storage capacity.
• Queries that inherently touch huge row counts. Analytics that scan and aggregate millions of rows (SUM, GROUP BY over a year of data) get little from a B-tree, because there is no small set of rows to seek to. The answers there are precomputation: denormalization, materialized views, or a purpose-built store - a columnar/OLAP engine like ClickHouse for analytics.
• Access patterns a B-tree cannot express. A B-tree cannot do LIKE '%foo%' (leading wildcard), relevance-ranked full-text search, or fuzzy matching. Those need an inverted index and usually a dedicated engine like Elasticsearch; geospatial needs GiST/R-tree indexes. The right kind of index, or the right system, not a bigger B-tree.

Indexing is the first and cheapest database-scaling lever - and it is a single-node, query-speed tool. When you have indexed correctly and it is still slow at scale, the fix is upstream: caching, replication, sharding, or a different data store. On the write side specifically, separating reads from writes with CQRS lets a read-optimized, heavily-indexed store exist without taxing the write path.

NoSQL: the indexing catches are serious

NoSQL stores are often sold as "scales effortlessly," but the fine print is about indexing, and it is steep. The whole model is that you get one blazing-fast access path - the partition/primary key - and everything else is a problem.

• Off-key queries are second-class. In a key-value or wide-column store, a query that is not on the partition key either is not allowed or degenerates into a scan. You do not get ad-hoc WHERE anything = ? the way SQL gives you.
• Secondary indexes are limited and costly. In DynamoDB, a Global Secondary Index is a separate copy of your data under a different key, updated asynchronously - so it is eventually consistent (reads can be stale), it consumes its own extra write capacity on every write to the base table, and there is a hard limit on how many you can have. Local Secondary Indexes can be strongly consistent but must be defined at table creation and can never be added later. In Cassandra, a native secondary index queries every node in the cluster (a scatter), and performs badly on both high- and low-cardinality columns - which is why the community advice is to avoid it and instead denormalize into a second table keyed for that query.
• You model for queries, not for data. Because you cannot cheaply "just add an index and query however," NoSQL forces query-first design: you enumerate your access patterns up front and build a table (or index) per pattern. A new query pattern discovered later often means a new table plus a backfill of all existing data - the flexibility SQL gives you for free is gone.
• No ad-hoc joins, and index updates are eventually consistent, so a write is not immediately visible through its secondary index.

None of this makes NoSQL wrong - it buys genuine horizontal write scale and predictable latency. But the price is exactly the thing indexing gives you in a relational database: flexible, consistent, add-it-later querying. Choose NoSQL when your access patterns are few, known, and key-shaped; reach for a relational database and its indexes when you need to slice the data many ways.

The short version

Start from a slow query and EXPLAIN it. Index the columns it filters, join, and sort on; for multi-condition queries, order composite indexes equality-first, one range last, and use covering indexes for hot reads. Index for real queries, not everything, because every index taxes writes. And know the ceiling: indexing speeds up one node's reads - it does not add capacity, cannot rescue write-heavy or huge-scan workloads, and in NoSQL it is a deliberately limited, eventually-consistent, design-it-upfront affair. Past that ceiling, the tools are caching, replicas, sharding, and the right store for the job.