Understanding SQL Indexes and Query Performance

How the Query Optimizer Chooses: Seek vs. Scan

Every major relational database has a cost-based optimizer that estimates the cost of several possible ways to execute a query and picks the cheapest one it can find — it does not blindly use every index that exists just because one is available. The two operations worth knowing by name:

• An index seek (or index scan, terminology varies by engine) navigates the B-tree directly to the matching value(s) — proportional to the size of the result, not the size of the table.
• A full table scan (or sequential scan, in Postgres's terminology) reads every row in the table in physical storage order — proportional to the size of the table, regardless of how few rows match.

The optimizer bases this choice on statistics it maintains about the data — approximate row counts, the distribution of distinct values per column, sometimes a histogram of value frequencies. Those statistics can go stale after large data changes (a bulk load, a mass delete), which is why every engine has some form of a ANALYZE (or UPDATE STATISTICS) command to refresh them — a query that "used to be fast" and mysteriously isn't anymore is worth checking against stale statistics before assuming the schema itself is the problem.