Statistics include a correlation value per column: how well the order of the values matches the order rows are physically stored in. When correlation is near 1, reading a range through the index visits pages almost in order and costs little; when it is near 0, the same index scan jumps randomly across the table and can cost more than reading everything. This is why an index on a timestamp column that rows were inserted by is fast, while an index on a scattered column is not, even with identical row counts. It explains plans that pick a sequential scan despite a perfectly good index.
Every column has a logical order (the sorted order of its values) and the table has a physical order (the order rows sit in the file). PostgreSQL records how well those two match as a correlation bet…