Indexes, selectivity and query plans

A missing index turns a lookup into a full scan, and a wrong index taxes writes without helping reads. Plans show what the database actually does, and selectivity decides which design wins on your data.

explain
measure

You can now

Explain B-tree versus sequential access, selectivity, and leftmost-prefix, partial and covering index choices.
Read EXPLAIN and EXPLAIN ANALYZE plans, compare estimated and actual rows, and name the scan and join strategy.
Measure two index designs on controlled data and explain the selectivity-dependent result with table size and ANALYZE state.

Covers

Indexes, selectivity, cardinality and query plans

Study, in this order

5 steps

How Indexes Work
AlgoMaster SQL - selected route

How Databases Find Rows Without an Index; B-Tree Indexes (equality, range, sorted output); Hash Indexes; Index Overhead: The Trade-offs; Selectivity: When Indexes Actually Help; Common Mistakes

Done
Composite, Partial and Covering Indexes
AlgoMaster SQL - selected route

Composite Indexes (The Leftmost Prefix Rule, Column Order Guidelines); Partial Indexes; Covering Indexes with INCLUDE; skim GIN and GiST Indexes

Done
`EXPLAIN` and Execution Plans
AlgoMaster SQL - selected route

EXPLAIN vs EXPLAIN ANALYZE; Reading a Plan: Cost Fields; Scan Types (sequential, index, index only, bitmap); Join Strategies; Identifying Bottlenecks

Done
Query Optimization and Anti-Patterns
AlgoMaster SQL - selected route

Anti-Patterns 1 to 4: Functions on Indexed Columns, Implicit Type Conversions, SELECT * in Production, OR Conditions That Prevent Index Usage; Anti-Pattern 6: The \(N+1\) Query Problem

Done
PostgreSQL 14.1 Using `EXPLAIN`
PostgreSQL transactions and EXPLAIN

14.1.1 EXPLAIN Basics: the sequential-scan cost as pages times seq_page_cost plus rows times cpu_tuple_cost, plus cpu_operator_cost per row for a WHERE check; 14.1.2 EXPLAIN ANALYZE; 14.1.3 Caveats

Done

Focus on

High-selectivity equality predicates gain most. Low-selectivity filters and tiny tables stay on sequential scans, and every index taxes writes.
Equality columns come before range columns in composite indexes, and only the leftmost prefix is usable. A range column first wastes the rest.
EXPLAIN shows estimates and planner costs. EXPLAIN ANALYZE executes and shows actual rows, loops, buffers and timing. Costs are planner units, not milliseconds.
Plans depend on statistics. State table size and ANALYZE state with every claim, and distrust toy-table plans.

Reproduce closed-book

Closed-book, on a 5000-row ANALYZEd table of 32 pages with default cost settings: derive the sequential-scan cost for one equality filter from pages and rows before running EXPLAIN, add an index on the filter column, and compare EXPLAIN (ANALYZE, BUFFERS) when the matching rows are scattered across the table and when they are clustered.

Traps

Cost numbers are milliseconds. They are abstract planner units; only the EXPLAIN ANALYZE Execution Time is measured, on your hardware and cache state.
Wrapping an indexed column in a function. The predicate becomes unsargable and the plan falls back to a scan; rewrite the predicate or index the expression.
One index per column. Leftmost-prefix rules, OR conditions and implicit type conversions defeat single-column indexes; check the plan, not the schema.

Practice

Measured plan improvement on a scratch database

14.1.2 EXPLAIN ANALYZE: before and after plans with BUFFERS for a selective filter plus a join from your service schema

Use a scratch PostgreSQL 18 database (a throwaway postgres:18 container works) and a table over 1000 rows, run ANALYZE, and record pages, row counts, both plans, Heap Blocks and both execution times. Fix one anti-pattern from the lesson (function-wrapped column or SELECT star) and show the plan change.

Self-test

A 5000-row ANALYZEd table of 32 pages filters user_id = 7 with 100 matches. Where does the sequential scan's cost of 94.50 come from, and what does an index on user_id change?
A filter has equality on status and a range on created_at. How do you order the composite index?
EXPLAIN estimates 10 rows but ANALYZE shows 4500 actual. What do you do first?
Why can an index slow a workload down?

Completion criterion

Stop when

You show before and after EXPLAIN ANALYZE with table size and ANALYZE state, explain why the selective case improved, and name one case on the same tables where the index does not help.

Mark passed, then open 4.7 Only mark this when you can do it without notes.

Leads to

4.8 HTTP APIs, pagination, streaming and idempotency Index the idempotency-key and pagination lookups behind the endpoints.
stage 06 · Systems Foundations Carry plan reading into storage and I/O behavior.

Comes after

4.4 Relational modeling, joins, aggregation and window functionsDiagnose the slow joins with plans and selectivity.
4.5 Transactions, isolation anomalies and ORM boundariesMeasure the plans behind the invariant checks.

Resources for this unit

AlgoMaster SQL - selected route
AlgoMasterrequiredcourse
Study SQL Foundations, Querying Data, Joins, Subqueries and CTEs, Window Functions, DDL, DML and Views, Performance Optimization, Transactions and Concurrency, and Data Modeling. Stop when the service queries and transaction tests pass.
PostgreSQL transactions and EXPLAIN
PostgreSQLrequiredreference
Use the transaction tutorial and EXPLAIN guide to demonstrate commit, rollback, one isolation anomaly or prevented anomaly, and a measured plan improvement on the database actually used.

Also in this section

Official docs typed-service build path
Python typing, Pydantic, FastAPI and PostgreSQLprimarycourse
Build one record service in this order: structural protocols and generics; Pydantic models, validators, strict mode, serialization and settings; FastAPI request bodies, dependencies, errors and tests; then PostgreSQL transactions and EXPLAIN. Replay valid, malformed, duplicate and previous-schema requests through CLI and HTTP.
FastAPI tutorial
FastAPIsupportimplementation
Use Request Body, Dependencies, Handling Errors and Testing to expose the same service layer through HTTP. Keep framework models outside the domain core and preserve the same error semantics as the CLI.
AlgoMaster Low-Level Design - one rehearsal
AlgoMastersupportpractice
Use one fitting design prompt to rehearse interface contracts, dependency direction and failure ownership. Treat the review as feedback, then verify behavior with your own tests.
Stas' Python Cookbook - data and interfaces
Stas Bekmansupportreference
Use Serialization and Deserialization plus Environment and Arguments for focused implementation help. Compare JSON, JSONL, CSV and compressed data, and never use pickle for untrusted interchange.
AlgoMaster Python - interfaces, generics and data files
AlgoMastersupportcourse
Use Interfaces and Protocols plus Generic Types for structural typing, and Working with JSON plus Working with CSV for JSONL, error handling, newline and DictReader behavior. Lesson quizzes check recall; implementation is verified with your own scripts.
SQLAlchemy 2.1 documentation - select, Session and eager loading
SQLAlchemyreferencereference
Use the select() tutorial for 2.x query style, Session basics for the transaction boundary and identity map, and relationship loading for lazy versus selectinload versus joinedload plus raiseload. Use select() style and Session.execute or Session.scalars only, never the legacy Query API.
Alembic tutorial - migration scripts and downgrading
SQLAlchemysupportreference
Use Create a Migration Script, Running our First and Second Migration, Getting Information and Downgrading to run a paired upgrade and downgrade round trip on a scratch database.
PyArrow Parquet read and write docs
Apache Arrowsupportreference
Use Reading and Writing Single Files plus Table from_pydict and from_pylist to convert normalized records to Parquet and test types, nulls, column projection and schema.
Stripe idempotent requests
Stripesupportreference
Use the Idempotency-Key header contract, stored-response replay, parameter-mismatch errors and POST-only scope to implement keyed replay for one endpoint.