Indexes and Query Performance

What an index is

Think of the index at the back of a book. To find every page about "deadlock", you do not read the book from cover to cover: you look up the word in the alphabetical index and jump to the listed pages. A database index works the same way: it is a separate, sorted structure holding the values of one or more columns, each with a pointer to the row it came from. The database keeps it up to date automatically on every INSERT, UPDATE and DELETE.

Without a suitable index, the only way to answer WHERE customer_id = 2 is a full table scan: read every row of the table and test the condition on each. On the shop's ten orders that takes no time at all. On fifty million orders it means reading gigabytes for every page view — the most common reason a query that was fast in testing becomes slow in production.

An index changes how fast a query runs, never what it returns. You can add or drop indexes without changing a single query; the database decides on its own whether to use them.

How it works: the B-tree

Almost every relational database stores its ordinary indexes as a B-tree (strictly, usually a B+ tree variant): a balanced tree of pages in which each node holds many sorted keys. The top (root) and middle nodes only guide the search; the bottom (leaf) nodes hold every key with a pointer to its row (in a clustered index, as in InnoDB and SQL Server, the leaves hold the rows themselves). Because each node holds hundreds of keys, the tree stays very shallow: three or four levels cover millions of rows, so a lookup reads only a handful of pages.

Because the leaves are sorted, a B-tree also helps with ranges (order_date BETWEEN …), with ORDER BY on the indexed column, and with MIN/MAX. Other index types exist for special cases — hash indexes for pure equality, full-text indexes for words in long text, GIN and GiST in PostgreSQL, columnstore indexes in SQL Server for analytics — but the B-tree is the default and the one to understand first.

Creating indexes

The shop's queries often ask "which orders belong to this customer?" and "which products are in this category?". Both columns are good index candidates:

CREATE INDEX idx_orders_customer_id ON orders (customer_id);
CREATE INDEX idx_products_category ON products (category);

The syntax is the same in SQLite, PostgreSQL, MySQL and SQL Server: a name (by convention idx_<table>_<columns>), the table, and the column list. DROP INDEX removes one again (SQL Server and MySQL also want the table name). Building an index on a large table takes time and, in some systems, blocks writes while it runs; PostgreSQL offers CREATE INDEX CONCURRENTLY and SQL Server WITH (ONLINE = ON) (in editions that support it) to avoid that.

Some indexes already exist without you asking. A primary key and every UNIQUE constraint are enforced through an index. In SQLite you can list them; the shop has two, for customers.email and for the composite key of order_items (an INTEGER PRIMARY KEY is the table's own row number and needs no separate index):

SELECT name, tbl_name FROM sqlite_master
WHERE type = 'index'
ORDER BY name;

name                            tbl_name
------------------------------  -----------
sqlite_autoindex_customers_1    customers
sqlite_autoindex_order_items_1  order_items

Reading a query plan

SQL says what you want, not how to get it. The database's query optimizer chooses the how: which index to use, in which order to join tables. The result is a query plan (also called an execution plan), and every serious database can show it. In SQLite, put EXPLAIN QUERY PLAN in front of the query. Here is the plan before and after creating the index on orders.customer_id:

EXPLAIN QUERY PLAN
SELECT order_id, order_date FROM orders WHERE customer_id = 2;

CREATE INDEX idx_orders_customer_id ON orders (customer_id);

EXPLAIN QUERY PLAN
SELECT order_id, order_date FROM orders WHERE customer_id = 2;

id  parent  notused  detail
--  ------  -------  -----------
2   0       0        SCAN orders

id  parent  notused  detail
--  ------  -------  ----------------------------------------------------------------
3   0       0        SEARCH orders USING INDEX idx_orders_customer_id (customer_id=?)

The detail column is the part to read (the other columns are internal numbering that links the steps of larger plans). The words mean:

• SCAN orders — a full table scan: every row is read.
• SEARCH orders USING INDEX … (customer_id=?) — the index is used to jump straight to the matching rows.
• USING INTEGER PRIMARY KEY (rowid=?) — a lookup by the primary key, the fastest kind.
• USING COVERING INDEX — the index alone answers the query (see covering indexes).
• USE TEMP B-TREE FOR ORDER BY — the result has to be sorted separately because no index delivers it in order.

Lookups by primary key and by a UNIQUE column use their automatic indexes:

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE order_id = 105;
EXPLAIN QUERY PLAN SELECT * FROM customers WHERE email = 'mei.chen@example.com';

id  parent  notused  detail
--  ------  -------  -------------------------------------------------
2   0       0        SEARCH orders USING INTEGER PRIMARY KEY (rowid=?)

id  parent  notused  detail
--  ------  -------  -------------------------------------------------------------------
3   0       0        SEARCH customers USING INDEX sqlite_autoindex_customers_1 (email=?)

EXPLAIN in other systems

The idea is universal; the command and output differ. In PostgreSQL and MySQL (8.0.18 and later), EXPLAIN shows the estimated plan and EXPLAIN ANALYZE actually runs the query and reports real row counts and timings:

EXPLAIN ANALYZE
SELECT order_id, order_date FROM orders WHERE customer_id = 2;

In PostgreSQL's output, look for Seq Scan (a full table scan) versus Index Scan, Index Only Scan or Bitmap Index Scan, and compare the estimated rows with the actual rows: a large difference points to outdated statistics. MySQL's classic EXPLAIN table shows the access type (ALL means a full scan; ref, range and const use an index) and the key it chose. In SQL Server, SQL Server Management Studio displays the estimated or actual execution plan graphically, and SET STATISTICS IO ON reports how many pages a query read.

Composite indexes and column order

A composite index (or multi-column index) covers several columns, sorted first by the first column, then by the second within each value of the first — like a phone book sorted by last name, then first name. That order decides which queries it can serve. An index on (customer_id, order_date) helps queries that filter on customer_id, or on customer_id and order_date together — but not queries on order_date alone, just as a phone book does not help you find everyone called "Mei":

CREATE INDEX idx_orders_customer_date ON orders (customer_id, order_date);

EXPLAIN QUERY PLAN
SELECT order_id FROM orders
WHERE customer_id = 1 AND order_date >= '2026-06-10';

EXPLAIN QUERY PLAN
SELECT order_id FROM orders WHERE customer_id = 1;

EXPLAIN QUERY PLAN
SELECT order_id, status FROM orders WHERE order_date >= '2026-09-01';

id  parent  notused  detail
--  ------  -------  --------------------------------------------------------------------------------------------
2   0       0        SEARCH orders USING COVERING INDEX idx_orders_customer_date (customer_id=? AND order_date>?)

id  parent  notused  detail
--  ------  -------  ---------------------------------------------------------------------------
2   0       0        SEARCH orders USING COVERING INDEX idx_orders_customer_date (customer_id=?)

id  parent  notused  detail
--  ------  -------  -----------
2   0       0        SCAN orders

The rule of thumb: put columns tested with = first and a range column (>=, BETWEEN) last, and choose the leading column so that the index serves as many queries as possible. An index on (a, b) makes a separate index on (a) redundant, but not one on (b).

Unique and covering indexes

Unique indexes

CREATE UNIQUE INDEX builds an index that also refuses duplicate values — the same effect as a UNIQUE constraint (see Designing Tables). If the shop decides that no two products may share a name:

CREATE UNIQUE INDEX idx_products_name ON products (name);

INSERT INTO products (name, category, price)
VALUES ('Wireless mouse', 'Peripherals', 19);

Error: UNIQUE constraint failed: products.name

Creating a unique index fails if the existing data already contains duplicates — a quick way to discover them. Prefer a UNIQUE constraint in the table definition when uniqueness is a business rule; it documents intent better.

Covering indexes

Normally an index lookup takes two steps: find the key in the index, then fetch the row from the table for the other columns. A covering index contains every column the query needs, so the second step disappears. In the composite example above, SQLite reported COVERING INDEX because order_id is the table's row number, which every SQLite index entry already carries. Here the index on (category, price) answers the query and delivers the rows already sorted by price, so no separate sort step appears:

CREATE INDEX idx_products_category_price ON products (category, price);

EXPLAIN QUERY PLAN
SELECT category, price FROM products
WHERE category = 'Cables'
ORDER BY price;

id  parent  notused  detail
--  ------  -------  -----------------------------------------------------------------------------
3   0       0        SEARCH products USING COVERING INDEX idx_products_category_price (category=?)

PostgreSQL and SQL Server let you add non-key columns to an index purely to make it covering: CREATE INDEX … ON products (category) INCLUDE (price);. Covering indexes are a precise tool for a few very frequent queries, not a default.

When an index does not help

Selectivity

Selectivity is the share of rows a condition keeps. An index shines when it narrows the search to a few rows: email = … matches one customer out of all of them. An index on orders.status, with only four possible values, helps much less: if three quarters of all orders are "delivered", using the index to find them means jumping back and forth between index and table for most of the rows, which is slower than one sequential scan. Optimizers know this and use statistics about the data (gathered by ANALYZE in SQLite and PostgreSQL) to skip such an index. It can still pay off for the rare values: finding the few "pending" orders among millions.

Functions on indexed columns

The index stores the column's values, not the result of a function applied to them. Wrap the column in a function and the index no longer matches:

CREATE INDEX idx_products_category ON products (category);

EXPLAIN QUERY PLAN
SELECT name, price FROM products WHERE category = 'Cables';

EXPLAIN QUERY PLAN
SELECT name, price FROM products WHERE lower(category) = 'cables';

id  parent  notused  detail
--  ------  -------  --------------------------------------------------------------
3   0       0        SEARCH products USING INDEX idx_products_category (category=?)

id  parent  notused  detail
--  ------  -------  -------------
2   0       0        SCAN products

The same happens with dates: substr(order_date, 1, 7) = '2026-07' scans, while the equivalent range order_date >= '2026-07-01' AND order_date < '2026-08-01' can use an index on order_date. Two fixes: rewrite the condition so the bare column stands alone on one side, or create an index on the expression itself (SQLite, PostgreSQL, and MySQL 8.0 support this; SQL Server uses an indexed computed column):

CREATE INDEX idx_products_category_lower ON products (lower(category));

EXPLAIN QUERY PLAN
SELECT name, price FROM products WHERE lower(category) = 'cables';

id  parent  notused  detail
--  ------  -------  ------------------------------------------------------------------
3   0       0        SEARCH products USING INDEX idx_products_category_lower (<expr>=?)

Other cases

• Leading wildcards: name LIKE '%cable' cannot use a B-tree, because the beginning of the value is unknown — like looking up words that end in "-tion" in a dictionary. A full-text index is the tool for searching words inside text.
• Mismatched types: comparing a text column with a number can force a conversion on every row.
• Small tables: when a table fits in a few pages, a scan is as fast as an index, and the optimizer may rightly ignore the index.

What an index costs

Indexes are not free, which is why you cannot simply index every column:

• Slower writes: every INSERT and DELETE must update every index on the table, and an UPDATE every index that contains a changed column. A table with ten indexes does roughly ten extra pieces of work per new row.
• Storage and memory: an index is a copy of its columns. Indexes compete with table data for the database's memory cache, and a large table's indexes together can be bigger than the table itself.
• Maintenance: indexes can become fragmented or bloated and must be rebuilt or vacuumed from time to time, and statistics must stay current (see Database Administration in Practice).

A sensible approach: index primary keys (automatic), foreign keys you join on, and the columns of your most frequent or most expensive WHERE and ORDER BY clauses. Then measure. Most database systems can report indexes that are never used — those are pure cost.

Finding slow queries

Guessing which query is slow wastes time. A practical routine:

1. Find the queries that cost the most in total — a 50-millisecond query run ten thousand times an hour matters more than one 5-second report a day. PostgreSQL's pg_stat_statements extension, MySQL's slow query log and performance schema, and SQL Server's Query Store all collect this.
2. Read the plan of the worst query. Look for full scans of large tables, sorts on large results, and estimated row counts that are far from the actual ones.
3. Change one thing — add or adjust an index, rewrite a condition so it can use one, select fewer columns, update statistics.
4. Measure again with the plan and timing, and keep an eye on write performance.

Not every slow query is an index problem: waiting for a lock held by another transaction (see Transactions and ACID), the "N+1" pattern of running one query per row in application code (see Working with Databases from Code), or simply fetching far more rows than the screen shows are just as common. Monitoring and the slow query log are covered on Database Administration in Practice.