Indexes and query performance

What an index is

An index is a separate structure sorted by one or more columns, where each entry holds the value and a pointer to its row. It is the phone book sorted by last name instead of by signup order. InnoDB and PostgreSQL both build ordinary indexes as a B-tree that stays three or four levels deep over millions of rows, so a lookup reads a few pages and also serves ranges, prefix LIKE, ORDER BY and joins.

-- The most common index a DBA adds: the column a WHERE or JOIN filters on
CREATE INDEX idx_orders_customer ON orders (customer_id);

-- InnoDB already created one for the foreign key (fk_orders_customer).
-- PostgreSQL does not index foreign key columns for you.

Where the rows actually live

MySQL In InnoDB the primary key index is the table: its leaf pages hold the whole rows in primary key order, the clustered index. Every other index is a secondary index whose pointer is the primary key value, so a lookup costs two descents and that key sits in every entry. A 36-character UUID therefore bloats every index; prefer a short, increasing BIGINT.

PostgreSQL PostgreSQL stores the table as a heap, with rows wherever there is free space. Every index, including the primary key's, is a separate B-tree pointing at a physical location. No index is special, so a UUID key hurts far less.

The kinds of index you will meet

Most tables need only B-tree indexes on the columns queries filter, join and sort by.

Composite indexes and the leftmost-prefix rule

An index on (customer_id, order_date) is sorted by customer, and within each customer by date.

CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date);

-- uses the index:   WHERE customer_id = 1
-- uses the index:   WHERE customer_id = 1 AND order_date >= '2026-02-01'
-- uses the index:   WHERE customer_id = 1 ORDER BY order_date
-- cannot use it:    WHERE order_date >= '2026-02-01'   (leading column missing)

The rule: a query must constrain the leftmost column, then the next, without skipping. An index on (a, b) therefore serves queries on a alone, and equality columns go first with the range column last. PostgreSQL 18 added skip scan for a skipped low-cardinality leading column, but do not design for it.

Selectivity, cardinality and statistics

Cardinality is the number of distinct values in a column; selectivity is the share of rows a condition matches. The optimizer decides per query, and it ignores an index on status when 90 percent of orders are 'paid', because a scan beats millions of random row fetches. It judges from stored statistics, so plans that broke overnight usually want ANALYZE first.

Reading a plan

EXPLAIN asks the optimizer what it would do without doing it. EXPLAIN ANALYZE runs the statement and prints real row counts and timings next to the estimates. An estimate of 300,000 rows that turns out to be 2 is a statistics problem; a scan of three million rows to return 2 is an index problem. The plans below assume three million orders.

MySQL EXPLAIN

MySQL Three fields carry the meaning: type is how the table is read (ALL is a full table scan, ref an index lookup), key is the index chosen (NULL means none), and Extra holds the warnings such as Using filesort. 8.4 prints the TRADITIONAL grid; 9.5 and later default to TREE.

EXPLAIN SELECT id, order_date, total
FROM orders
WHERE customer_id = 1
ORDER BY order_date;

The filesort is gone too: the index returns each customer's orders in date order.

PostgreSQL EXPLAIN

PostgreSQL PostgreSQL prints one tree. Recognize Seq Scan, Index Scan and Index Only Scan, and read Rows Removed by Filter as wasted work. EXPLAIN (ANALYZE, BUFFERS) adds actual time, rows and pages from cache (shared hit) or disk (read); 18 includes BUFFERS with ANALYZE.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, order_date, total FROM orders WHERE customer_id = 1 ORDER BY order_date;

-- before the index
Sort  (cost=63012.10..63757.20 rows=298041 width=17) (actual time=1650.32..1650.33 rows=2 loops=1)
  ->  Seq Scan on orders  (cost=0.00..58233.00 rows=298041 width=17) (actual time=0.04..1642.11 rows=2 loops=1)
        Filter: (customer_id = 1)
        Rows Removed by Filter: 2999998
        Buffers: shared hit=2112 read=20734

-- after CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date)
Index Scan using idx_orders_cust_date on orders  (cost=0.43..12.47 rows=2 width=17) (actual time=0.03..0.04 rows=2 loops=1)
  Index Cond: (customer_id = 1)
  Buffers: shared hit=5

Same fix: 22,846 pages and a sort before, five cached pages after.

The usual suspects

Nine out of ten slow queries are one of these patterns, and the pattern is most of the fix.

The wildcard one is worth seeing on real rows. Both queries below find Gary Moore's Still Got the Blues in the sample tracks table, and only the first one can use an index on title. A B-tree is sorted by first character, so an anchored pattern is a seek and a leading % is a scan of every row.

-- Seek: the engine jumps to the S entries and stops
SELECT title FROM tracks WHERE title LIKE 'Still%';

-- Scan: the sort order is no help, so every row is examined
SELECT title FROM tracks WHERE title LIKE '%Blues%';

On fourteen rows nobody notices. On fourteen million, the second query is the ticket you get paged about.

Finding the slow queries, and giving the engine memory

When the complaint is "the app is slow", first find which statements deserve attention. Chapter 16 makes this a weekly routine.

MySQL Slow query log

Off by default. SET PERSIST slow_query_log = ON and long_query_time = 1 logs every statement over one second.

MySQL sys schema

Installed by default over the Performance Schema. sys.statement_analysis ranks statements by total latency, and sys.schema_unused_indexes lists indexes nobody used.

PostgreSQL pg_stat_statements

Add it to shared_preload_libraries, restart the service, then CREATE EXTENSION. It lists calls, mean time and rows per statement.

An index only pays off when its pages are in memory. MySQL InnoDB caches table and index pages in the buffer pool, raised online with SET PERSIST. PostgreSQL shared_buffers plays the same role, needs a restart, and rarely helps far above its starting point because the operating system caches files too.

[mysqld]
# 16 GB machine dedicated to MySQL: give InnoDB 12 GB
innodb_buffer_pool_size=12G
slow_query_log=ON
long_query_time=1

Go deeper

• MySQL: EXPLAIN output format
• PostgreSQL: Using EXPLAIN
• PostgreSQL: index types
• MySQL: the slow query log
• PostgreSQL: pg_stat_statements