SQL Indexing & Optimization

A B-tree keeps keys sorted in a shallow, wide tree, so an equality or range lookup costs O(log n) page reads (usually 3-4 levels even for hundreds of millions of rows) instead of scanning the whole table. It also returns rows in key order, which can eliminate a sort.

• It helps for =, <, >, BETWEEN, IN, prefix LIKE 'abc%', ORDER BY and MIN/MAX.
• It does not help when the predicate matches a large fraction of rows (the planner prefers a sequential scan), on tiny tables, or when the predicate is not sargable.
• Every index costs write amplification (each INSERT/UPDATE/DELETE maintains it), disk and buffer-pool space.

Composite indexes are sorted by a, then b within a, then c. The leftmost-prefix rule says the index is usable efficiently only for a prefix of the columns.

• a=1: yes, full use.
• b=2: not as an efficient seek (MySQL cannot; PostgreSQL may do a full index scan, MySQL 8.0 has skip scan in limited cases).
• a=1 AND c=3: seeks on a, then c is only filtered inside the range of a (an index condition, not a seek).
• a=1 AND b>5 AND c=3: seeks on a and range on b; c cannot narrow the range because after a range predicate the following columns are not sorted contiguously.

Rule of thumb: equality columns first, then the range or sort column, in order of selectivity and query frequency.

CREATE INDEX idx_orders_cust_status_created ON orders (customer_id, status, created_at);

A covering index contains every column a query needs, so the engine answers from the index alone without visiting the table (heap or clustered index). That is an index-only scan in PostgreSQL and Using index in MySQL EXPLAIN.

-- PostgreSQL 11+: non-key payload columns
CREATE INDEX idx_orders_cust ON orders (customer_id, created_at) INCLUDE (total);
SELECT created_at, total FROM orders WHERE customer_id = 42 ORDER BY created_at;

• INCLUDE columns are stored in leaf pages only, are not sortable/searchable, and keep the key small.
• MySQL has no INCLUDE; add the extra columns as trailing key columns. Secondary indexes implicitly contain the PK, so SELECT id is already covered.
• PostgreSQL index-only scans still check the visibility map; on a table with many dead or recently modified pages it falls back to heap fetches (Heap Fetches: n in EXPLAIN ANALYZE), so VACUUM matters.

A partial index indexes only rows matching a predicate, which makes it small and cheap to maintain; an expression index indexes a computed value so that queries on that expression are sargable.

-- Only 0.5% of orders are pending; index just them
CREATE INDEX idx_orders_pending ON orders (created_at) WHERE status = 'PENDING';

-- Case-insensitive lookup
CREATE INDEX idx_users_email_lower ON users (lower(email));
SELECT * FROM users WHERE lower(email) = 'a@b.com';

-- Enforce uniqueness only for active rows
CREATE UNIQUE INDEX uq_active_email ON users (email) WHERE deleted_at IS NULL;

• The query predicate must imply the index predicate for the planner to use it.
• MySQL has no partial indexes; 8.0.13+ supports functional key parts (CREATE INDEX i ON users ((lower(email)))) and generated columns can be indexed.
• SQL Server calls partial indexes filtered indexes.

EXPLAIN shows the estimated plan; EXPLAIN ANALYZE actually executes the query and adds real row counts, loops and timings. Read the tree from the innermost node outward and compare estimated rows vs actual rows: large mismatches point at stale statistics or correlated columns.

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE customer_id = 42 AND status = 'PAID';
-- Index Scan using idx_orders_cust on orders  (cost=0.43..8.45 rows=1 width=64)
--   (actual time=0.02..95.1 rows=48000 loops=1)
--   Filter: (status = 'PAID')   Rows Removed by Filter: 120
--   Buffers: shared hit=1200 read=900

What to look at:

• Estimated rows=1 vs actual rows=48000: the planner chose a plan for the wrong cardinality.
• Seq Scan on a big table with a selective filter, Rows Removed by Filter large, Sort Method: external merge Disk, Nested Loop with a large loops count.
• Buffers: read = disk reads, hit = shared buffer cache.
• MySQL 8: EXPLAIN ANALYZE (8.0.18+) prints a tree with actual time; classic EXPLAIN shows type (ALL = full scan, ref, range), key, rows, Extra (Using filesort, Using temporary, Using index).

• Nested loop: for each row of the outer input, probe the inner side. Best when the outer side is small and the inner has an index on the join key; cost roughly outer_rows x index probe.
• Hash join: build an in-memory hash table on the smaller input, stream the larger one and probe. Best for large unsorted equi-joins without useful indexes; spills to disk in batches when it exceeds work_mem.
• Merge join: both inputs sorted on the join key, then merged in one pass. Best when both are already ordered (index scans) or the join is non-selective on big inputs; supports range-ish conditions on sorted data.

SET enable_nestloop = off;  -- PostgreSQL diagnostic only, never in production code
EXPLAIN ANALYZE SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id;

MySQL used only nested-loop variants (index NLJ, block nested loop) until 8.0.18 added hash join (replacing block nested loop for non-indexed equi-joins); it has no merge join.

OFFSET n must produce and discard the first n rows, so cost grows linearly with page depth. It is also unstable under concurrent inserts (rows shift between pages, causing duplicates or skips). Keyset (seek) pagination remembers the last seen sort key and seeks directly to it with an index.

-- Offset: reads and discards 100000 rows
SELECT id, created_at FROM orders ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 100000;

-- Keyset: constant cost with INDEX (created_at DESC, id DESC)
SELECT id, created_at FROM orders
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;

• The sort key must be unique (add id as a tiebreaker) and deterministic.
• Row-value comparison (a, b) < (x, y) works in PostgreSQL and MySQL 8, but MySQL's optimizer used to handle it poorly; the expanded form a < x OR (a = x AND b < y) is safer there.
• Trade-offs: no random page jump or "page 57 of 400", and a total count still requires a separate COUNT(*) (approximate it for large tables).

Wrapping the indexed column in a function makes the predicate non-sargable: the index stores created_at, not DATE(created_at), so the engine must compute the function for every row. Rewrite the predicate so the column stands alone and the range is computed on the constant side.

-- Bad
SELECT * FROM orders WHERE DATE(created_at) = '2025-01-15';
-- Good: half-open range uses the index
SELECT * FROM orders
WHERE created_at >= '2025-01-15' AND created_at < '2025-01-16';

Other non-sargable patterns:

• WHERE col + 1 = 10, WHERE LOWER(col) = ... (unless an expression index exists), WHERE col LIKE '%abc' (leading wildcard; use trigram/full-text instead).
• Implicit casts: WHERE varchar_col = 123 can force a cast on the column; in MySQL comparing a string column with a number disables the index.
• Mismatched collation or charset in joins (MySQL utf8 vs utf8mb4) causes a conversion on the column side.
• OR across different columns may block index use; rewrite as UNION ALL or rely on PostgreSQL BitmapOr.

The planner estimates row counts from column statistics (histogram, most common values, n_distinct, null fraction) gathered by ANALYZE. After a bulk load or large delete the stats are stale, estimates are wrong, and it may pick a seq scan or a nested loop that explodes.

-- PostgreSQL
ANALYZE orders;
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 1000; -- finer histogram
CREATE STATISTICS st_city_zip (dependencies) ON city, zip FROM addresses; -- correlated columns
ANALYZE addresses;

-- MySQL 8
ANALYZE TABLE orders UPDATE HISTOGRAM ON status WITH 100 BUCKETS;

• Autovacuum triggers autoanalyze after ~10% of rows change by default (autovacuum_analyze_scale_factor = 0.1); lower it for huge tables.
• Planner assumes independence between columns; extended statistics fix correlated predicates like city = 'X' AND zip = 'Y'.
• InnoDB persistent statistics sample a few pages (innodb_stats_persistent_sample_pages) and can be skewed.
• Parameter-sniffing equivalent: a generic prepared plan chosen for a skewed value (PostgreSQL after 5 executions, plan_cache_mode).

Partitioning splits a table into physical pieces by a key (range, list, hash). Its main wins are partition pruning (queries touching one month read only that partition), cheap bulk deletion (drop a partition instead of DELETE + vacuum) and smaller per-partition indexes. It is not a general speed-up for point lookups.

CREATE TABLE events (
  id bigint, created_at timestamptz NOT NULL, payload jsonb,
  PRIMARY KEY (id, created_at)
) PARTITION BY RANGE (created_at);
CREATE TABLE events_2025_01 PARTITION OF events
  FOR VALUES FROM ('2025-01-01') TO ('2025-02-01');

Pitfalls:

• A unique or primary key must include the partition key in both PostgreSQL and MySQL, so a global unique id is impossible.
• Queries without the partition key in the WHERE scan every partition and can be slower (planning overhead grows with partition count).
• Pruning fails if the predicate wraps the key in a function or uses a mismatched type.
• Partitions must be created ahead of time (pg_partman or a scheduler); inserts with no matching partition fail unless a DEFAULT partition exists.
• MySQL does not support foreign keys on partitioned InnoDB tables.

Each index must be updated on every INSERT and DELETE, and on UPDATEs touching indexed columns; in PostgreSQL an UPDATE that changes any indexed column also defeats HOT updates and bloats all indexes. Indexes also compete for cache and slow VACUUM and replication.

-- PostgreSQL: indexes never used since stats reset
SELECT relname, indexrelname, idx_scan, pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes WHERE idx_scan = 0 ORDER BY pg_relation_size(indexrelid) DESC;

-- MySQL 8 (sys schema)
SELECT * FROM sys.schema_unused_indexes;

• Redundant: (a) is redundant when (a, b) exists (unless it is unique or (a, b) is much wider and hot for a-only lookups).
• Check replicas too: an index unused on the primary may be used on a read replica; stats are per instance.
• Drop safely: MySQL 8 invisible indexes (ALTER INDEX i INVISIBLE), then drop after a soak period; PostgreSQL DROP INDEX CONCURRENTLY.

Identify the actual offender first, then explain it, then change one thing and measure.

1. Find top queries by total time: pg_stat_statements (ORDER BY total_exec_time DESC) or MySQL slow log / performance_schema.events_statements_summary_by_digest. High call count with moderate latency often matters more than one slow report.
2. Capture the real query with real bind values and run EXPLAIN (ANALYZE, BUFFERS) on production-sized data (or a restored copy).
3. Check estimates vs actuals, scan types, sorts spilling to disk, Rows Removed by Filter, buffer reads.
4. Fix in this order: rewrite non-sargable predicates, add or reshape an index (composite order, covering, partial), fix statistics, then reduce data (pagination, narrower select list, archive/partition).
5. Verify with the plan and with load, watch write overhead and lock impact of the DDL.

SELECT query, calls, total_exec_time, mean_exec_time, rows
FROM pg_stat_statements ORDER BY total_exec_time DESC LIMIT 10;

Also rule out non-query causes: lock waits (pg_locks, pg_stat_activity.wait_event), connection saturation, I/O saturation, and an ORM issuing N+1 queries.

N+1 shows up in pg_stat_statements as one cheap query with an enormous calls count (e.g. SELECT ... FROM item WHERE order_id = $1 called 100,000 times), each taking 0.3 ms but totalling minutes. Latency is dominated by round trips, not query cost.

Fixes:

-- Instead of N queries per parent id
SELECT * FROM item WHERE order_id = ANY(:ids);        -- PostgreSQL
SELECT * FROM item WHERE order_id IN (:id1, :id2, ...); -- portable

-- Or a single join with the parent
SELECT o.id, i.sku, i.qty FROM orders o JOIN item i ON i.order_id = o.id WHERE o.status = 'NEW';

• Batch with IN lists (chunk to a few hundred to stay within parameter limits: PostgreSQL JDBC allows 32767 bind parameters, SQL Server 2100).
• Ensure the child FK column has an index, otherwise each batched query is a scan.
• For aggregation, push work into SQL (GROUP BY) instead of looping.

COUNT(*) counts rows; COUNT(col) counts non-null values; COUNT(DISTINCT col) counts distinct non-null values and needs a sort or hash (most expensive). COUNT(1) equals COUNT(*).

In PostgreSQL, MVCC means each transaction can see a different set of row versions, so there is no stored exact row count; the engine must scan an index or heap and check tuple visibility. InnoDB has the same constraint (it scans the smallest secondary index), while MyISAM stored an exact count.

-- Exact but linear: use index-only scan if the visibility map is fresh
SELECT count(*) FROM orders WHERE status = 'PAID';
-- Approximate, instant
SELECT reltuples::bigint FROM pg_class WHERE relname = 'orders';

Options: approximate counts for UI ("about 2.3M"), maintained counter tables or triggers (contention!), materialized views refreshed periodically, or keyset pagination that avoids total counts.

Put equality predicates first, then the sort column: (customer_id, status, created_at DESC). The engine seeks to the (customer_id, status) prefix and reads entries already sorted by created_at, stopping after 20 rows, with no sort step.

CREATE INDEX idx_orders_lookup ON orders (customer_id, status, created_at DESC);
EXPLAIN SELECT * FROM orders
WHERE customer_id = 42 AND status = 'PAID' ORDER BY created_at DESC LIMIT 20;
-- Index Scan using idx_orders_lookup ... (no Sort node)

• If status were a range or IN (...) list, the sort order is broken across values: PostgreSQL needs a merge of several ranges or a Sort node; MySQL shows Using filesort. Then consider (customer_id, created_at) and filter status on the fly.
• Mixed directions (a ASC, b DESC) need an index defined with the same directions in PostgreSQL; MySQL supports descending index parts only from 8.0 (earlier versions parsed and ignored DESC).
• Add the PK/tiebreaker if you paginate with keyset.
• LIMIT makes the ordered index scan very cheap, but if the filters are very selective and the sort column is not in the index, the planner may prefer filter-then-sort.