Indexes and Query Plans

• Sorted, balanced tree of key values pointing to rows
• Point lookup: O(log n)
• Range scan or ORDER BY on the key: O(log n + k) for the k rows read

• Range scan finds the start once, then walks the linked leaves

• WHERE customer_id = 42 seeks the tree once the column is indexed

CREATE INDEX idx_orders_cust ON orders(customer_id);
SELECT * FROM orders WHERE customer_id = 42;

seeks the tree instead of scanning the table

• Indexing every column: each index costs disk space
• Every index slows INSERT, UPDATE and DELETE
• Low-selectivity columns (gender, boolean) rarely help

• Index on (a, b, c) is sorted by a, then b within a, then c within b
• Usable from the left only: the leftmost prefix

• Equality columns first, range column last
• Break ties by higher selectivity
• Columns after a range condition cannot narrow the seek

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

two equalities, then the range column

• Covering: every column the query needs is in the index
• Plan shows Index Only Scan or Using index: no table lookup
• Extra columns: INCLUDE (Postgres, SQL Server) or trailing key columns (MySQL)

• Function on the column hides the sorted key
• Leading %: LIKE 'abc%' is a prefix range; '%abc' is not
• Type mismatch: VARCHAR vs number casts every row

WHERE created_at >= '2025-01-01'
  AND created_at <  '2026-01-01'
CREATE INDEX idx_email_lower
  ON users (LOWER(email));

rewrite the predicate, or index the expression

• Query returns ~10-20%+ of rows: full scan wins
• Random lookups cost more than one sequential read
• Tiny table: a scan is already cheap
• Stale stats: run ANALYZE / UPDATE STATISTICS

• OR across different columns
• <> and NOT IN
• Leftmost prefix violated: (a,b) filtered on b alone

• EXPLAIN: plan only, query not run
• EXPLAIN ANALYZE (Postgres, MySQL 8): runs it, adds actual time and rows

• Seq Scan on a large table
• Estimated rows far from actual: stale stats
• Sort / Using filesort a better index could remove

• Sargable = can seek an index: keep the bare column on one side

• INSERT INTO t(cols) VALUES (...)
• UPDATE t SET c = v WHERE ...
• DELETE FROM t WHERE ...
• Run UPDATE and DELETE in a transaction with a WHERE
• INSERT and DELETE touch all indexes; UPDATE touches those with a changed column
• Write-heavy table → keep few indexes

• Index FK columns yourself: faster joins and parent deletes

• Leftmost prefix: (a,b,c) serves a, a+b, a+b+c, not b alone
• ORDER BY after a range column cannot remove the sort

• Function on column: YEAR(d) = 2025
• Leading %: LIKE '%x'
• Type mismatch: VARCHAR vs number
• Low selectivity
• OR across columns
• Stale stats: run ANALYZE

• Covering check: Index Only Scan or 'Using index' = no table lookup