You created an index and can check it using \d tablename. The field is indexed, yet PostgreSQL still performs a full table scan. This is one of the most frequent discoveries made by developers, and the reason behind this fact is very important for understanding the nature of the query planner.
The Planner Is Not a Rule Follower
The query planner of PostgreSQL is a cost-based optimizer, which means that the planner doesn't operate according to the rule "use indexes when there are any available". Rather, it evaluates the cost of all possible plans — sequential scan, index scan, bitmap index scan, various combinations of these plans — and chooses the least expensive. The word "cost" here doesn't mean milliseconds of operation. It means some unitless measure of the combination of I/O and CPU costs that is calculated according to your configuration settings.
The Two Costs That Drive Everything
Two configuration values are important here. seq_page_cost is the cost of reading one page when performing a sequential scan, and it has the default value of 1.0. random_page_cost is the cost of reading one page via random access, and it has the default value of 4.0.
This is a very specific value, 4.0, and it's not accidental either. It describes the fact that the cost of performing random seeks is high on spinning hard drives. Modern SSDs have a much smaller ratio, somewhere between 1.1 and 1.5. If you are using SSDs and haven't changed the value of random_page_cost to reflect this change, you are definitely underestimating how cheap the access to the indexes is.
Sequential scan works in the way that pages are read sequentially from the disk and prefetched by the operating system in order. The index scan works in a completely different way. First, it performs some reads in the index and then finds a row pointer there. After that, it reads the heap page where that row resides, then returns to the index and continues doing that until it finishes reading the required data.
Selectivity: How Many Rows Are You Really Asking For?
This is estimated in terms of what percentage of the rows in the table will satisfy the conditions set out in the query. This is referred to as selectivity and is the most critical input to the scan decision.
In a case where you are retrieving ten rows from a million-row table, then the use of indexes is certainly the best approach. The planner will come up with a very small figure for selectivity and will multiply it by the total number of pages in the table. Therefore, it will be found that an index scan will visit just a few pages, whereas a sequential scan visits all of them.
However, when fetching 40% of the rows, the math changes. An index scan that retrieves 400,000 rows has to do 400,000 random accesses to pages, many of which are the same heap page being accessed more than once. A sequential scan, on the other hand, accesses per page in order.
It is not a fixed figure. The ratio depends on the random access to sequential access cost, the size of the table, and the physical orderliness of the data compared to the index. But the rule stands firm that indexes are only useful for selective queries.
Correlation: Physical Order Counts
The more subtle one is correlation. If a column’s values are sorted according to their physical order on disk, then an index scan on that column can be almost as efficient as a sequential scan: Each index entry will point to the subsequent page, and not all over the place. PostgreSQL keeps track of this per-column correlation value and uses it when computing the cost of the index scan. Perfectly correlated columns (such as monotonically incrementing IDs) greatly benefit from an index; lowly correlated columns (such as a status flag that was updated randomly over time) do not.
Outdated Statistics – the Invisible Offender
All of the above is based on the assumption that the planner receives accurate estimates, which, in turn, come from the statistics generated by the ANALYZE tool. If your table has changed substantially since the statistics were generated, the planner may mistakenly believe that the table is smaller than it actually is, underestimate the cost of a sequential scan, or consider a condition highly selective when it is not.
The autovacuum process automatically runs ANALYZE on frequently changing tables, yet it can fall behind when the database changes rapidly. To ensure that the planner takes the current state of the data into account, you should run ANALYZE manually after adding a substantial number of rows to a table.
In order to understand the cost model, you do not need to tune all the knobs. You only need to understand that PostgreSQL estimates something, and the estimation is based on statistics and configuration. The aim here is to provide the planner with the correct information and not force his decisions.