Query optimisation and indexes

On a table with ten million orders, a query that finds one customer's orders takes 8 seconds; after the right index, the same query runs in milliseconds. SQL is declarative: we write what we want, and the DBMS optimiser chooses how to find it. It compares several possible plans and picks the cheapest one based on table statistics. In this lesson we learn how the optimiser thinks: the inner structure of an index, how to read a plan and how to write queries that make its job easier. The good news: no special tools are needed — everything starts with the EXPLAIN command and a few simple rules.

Inside a B-tree index

In most DBMSs the default index is a B-tree (strictly speaking, a B+ tree): keys are kept sorted in disk pages, every inner page holds hundreds of keys with pointers to the level below, and the leaves point to rows and are chained to each other. The tree is always balanced: the path from the root to any leaf has the same length. That is why a lookup takes only a few page reads, and the leaf chain makes range queries (BETWEEN, >, ORDER BY) cheap.

Sargable conditions

Sargable (search-argument-able) means a condition that can use an index for searching: the column stands “bare” on one side of the comparison. When you apply a function or arithmetic to the column (strftime('%m', order_date) = '03', price * 1.18 > 100), the sorted values in the index are of no use and the DBMS has to check every row. Rewriting the same condition as a range is enough.

CREATE INDEX idx_orders_date ON orders (order_date);

-- not sargable: a function on the column
EXPLAIN QUERY PLAN
SELECT id FROM orders
WHERE strftime('%m', order_date) = '03';

id | parent | notused | detail
2 | 0 | 214 | SCAN orders USING COVERING INDEX idx_orders_date

CREATE INDEX idx_orders_date ON orders (order_date);

-- sargable: a range on the bare column
EXPLAIN QUERY PLAN
SELECT id FROM orders
WHERE order_date >= '2025-03-01' AND order_date < '2025-04-01';

id | parent | notused | detail
2 | 0 | 154 | SEARCH orders USING COVERING INDEX idx_orders_date (order_date>? AND order_date<?)

Composite and covering indexes

A composite index is sorted by several columns: (customer_id, order_date) first by customer and, within the same customer, by date. It works like a phone book: you can search by surname, or by surname and first name, but not by first name alone — this is the leftmost prefix rule. If the index contains all the columns a query needs, the DBMS never touches the table — such an index is called covering. On top of that, when the index order matches ORDER BY, the separate sorting step disappears.

-- before: function on the column, no suitable index
EXPLAIN QUERY PLAN
SELECT id, order_date FROM orders
WHERE customer_id = 1 AND strftime('%Y', order_date) = '2025'
ORDER BY order_date;

id | parent | notused | detail
3 | 0 | 216 | SCAN orders
15 | 0 | 0 | USE TEMP B-TREE FOR ORDER BY

-- after: sargable range + composite index
CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date);

EXPLAIN QUERY PLAN
SELECT id, order_date FROM orders
WHERE customer_id = 1
  AND order_date >= '2025-01-01' AND order_date < '2026-01-01'
ORDER BY order_date;

id | parent | notused | detail
3 | 0 | 46 | SEARCH orders USING COVERING INDEX idx_orders_cust_date (customer_id=? AND order_date>? AND order_date<?)

In PostgreSQL, EXPLAIN shows the plan and the estimated cost, while EXPLAIN ANALYZE actually runs the query and shows real times. Below is a typical result on a table with 1,000,000 rows before and after the index (the numbers depend on the hardware). cost=startup..total is in arbitrary units, and rows is the optimiser's estimate; if the estimate differs greatly from the actual rows, the statistics are stale and ANALYZE is needed.

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

CREATE INDEX idx_orders_customer ON orders (customer_id);

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 42;

Seq Scan on orders  (cost=0.00..20834.00 rows=10 width=24) (actual time=0.018..61.922 rows=12 loops=1)
  Filter: (customer_id = 42)
  Rows Removed by Filter: 999988
Planning Time: 0.081 ms
Execution Time: 61.950 ms

Index Scan using idx_orders_customer on orders  (cost=0.42..44.58 rows=10 width=24) (actual time=0.024..0.039 rows=12 loops=1)
  Index Cond: (customer_id = 42)
Planning Time: 0.210 ms
Execution Time: 0.061 ms

When not to index

• Small tables — scanning a table of a few pages is cheaper than descending a tree.
• Low selectivity — on a two-valued column such as is_active, a condition returns half of the rows.
• Write-heavy tables — every index is updated on each INSERT, UPDATE and DELETE; on log and sensor tables that is expensive.
• Duplicate indexes — if (customer_id, order_date) exists, a separate (customer_id) index is redundant: the leftmost prefix replaces it.

CREATE INDEX idx_orders_date ON orders (order_date);

-- slow version: WHERE strftime('%m', order_date) IN ('01', '02', '03')
SELECT id, order_date
FROM orders
-- WHERE: a range on the bare column
ORDER BY order_date, id;

id | order_date
1 | 2025-01-15
2 | 2025-01-15
3 | 2025-02-02
4 | 2025-02-10
5 | 2025-03-05
6 | 2025-03-18

SELECT category,
       COUNT(*) AS rows_count
       -- selectivity_pct = 100 * n / N
FROM products
GROUP BY category
ORDER BY rows_count DESC, category;

category | rows_count | selectivity_pct
Electronics | 4 | 40
Accessories | 2 | 20
Stationery | 2 | 20
Games | 1 | 10
Home | 1 | 10