PostgreSQL index Correlation with UPDATE
Tags: postgres, sql, database, index
Published: 2024-03-25 17:01:39


Here is a small example inspired by by [this](https://news.ycombinator.com/item?id=39726793) on HackerNews:

> `SELECT * FROM TABLE FOO WHERE ORGANIZATION_ID = 10 ORDER BY CREATED_AT LIMIT 10 OFFSET 0;`
> Postgres sorts by `created_at` using an index, but uses the filter on `organization_id`. This organization has a million rows... without the order, the query runs in ms. In order, in seconds/minutes.
> I did the same test on SQLServer and SQLite, they executed the query correctly, using the correct index. I've never created an index to fix a bad plan in SQLServer, and I've used SqlServer a lot more than Postgres.

I created a temporary demo table to disable auto vacuum and analyze and observe the behavior of optimizer statistics.

```sql
create extension if not exists pgcrypto;
drop table if exists demo;
create temporary table demo ( id uuid default gen_random_uuid() primary key,  a int, b int, c int default 0 );
create index demoa on demo(a asc);
create index demob on demo(b asc);
insert into demo (a,b) select a, b from generate_series(1,10) a, lateral ( select generate_series(1,100*a) b ) b ;
vacuum analyze demo;
```

I run a query that filters on column `a` and sorts on column `b` to get the Top-10. Because I've two indexes, the query planner has the choice between
 - read all rows for the `a` value with an index range scan, sort them, and return the first 10 rows
 - read all rows in `b` order with a full index scan, filter for the `a` value and stop when 10 rows have been returned.

This choice is not easy as it involves estimating the cost of sorting in the first case and the selectivity of the filter in the second case. 

Here, with the table freshly vacuumed and analyzed, the query planner decides on the first solution: range scan and sort:
```sql
postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=12.19..12.22 rows=10 width=28) (actual time=0.048..0.050 rows=10 loops=1)
   Buffers: local hit=3
   ->  Sort  (cost=12.19..12.44 rows=100 width=28) (actual time=0.047..0.048 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=3
         ->  Index Scan using demoa on demo  (cost=0.28..10.03 rows=100 width=28) (actual time=0.015..0.032 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=3
 Planning Time: 0.088 ms
 Execution Time: 0.066 ms
```
The estimated cost is estimated to `10.03`

## Update

I'm running an update for all rows I'm interested in. I vacuum the changes, but do not analyze yet:
```sql
postgres=# update demo set c=c+1 where a =1;
UPDATE 100
postgres=# vacuum demo;
VACUUM
```
Because the statistics are the same, the plan for my query is the same, with a similar cost:

```sql
postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                         QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=12.15..12.18 rows=10 width=28) (actual time=0.052..0.054 rows=10 loops=1)
   Buffers: local hit=4
   ->  Sort  (cost=12.15..12.40 rows=99 width=28) (actual time=0.051..0.052 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=4
         ->  Index Scan using demoa on demo  (cost=0.28..10.02 rows=99 width=28) (actual time=0.016..0.035 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=4
 Planning Time: 0.095 ms
 Execution Time: 0.069 ms
(11 rows)
```
The estimated cost is `10.02`. If you have an idea why it is not exactly the same (10.02 instead of 10.03) when planning with exactly the same statistics, please share your idea in comments.

## Look and Save the statistics

Here are the statistics from before the UPDATE:

```sql
postgres=# select schemaname,tablename,attname,correlation,* from pg_stats where tablename='demo';
 schemaname | tablename | attname | correlation  | schemaname | tablename | attname | inherited | null_frac | avg_width | n_distinct  |                                                                                                                                           most_common_vals                                                                                                                                            |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   most_common_freqs                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      histogram_bounds                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      | correlation  | most_common_elems | most_common_elem_freqs | elem_count_histogram
------------+-----------+---------+--------------+------------+-----------+---------+-----------+-----------+-----------+-------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------+-------------------+------------------------+----------------------
 pg_temp_3  | demo      | id      | -0.017304245 | pg_temp_3  | demo      | id      | f         |         0 |        16 |          -1 |                                                                                                                                                                                                                                                                                                       |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       | {00177a50-262f-44cb-8d1e-3d9559d08fd3,02a53508-2345-4d4f-8f4c-7548af2d0c28,050e297f-1d09-4d99-9700-4766e6f368a5,08076212-f6f0-4109-a9d4-05b28eec858a,0a1c98d4-c8b5-47c1-97e7-67fa9a8b4236,0bd09320-af97-474c-8b6f-5befee23787b,0e88109a-f281-4657-a7b5-a9bfc36d8fb2,111b3f37-7a43-4292-ae6a-fa19c8eb96bd,13d0df94-04f4-44d0-a931-bf084785aeca,16c67cc1-8893-4086-97f8-6331748e8e76,18fcf9a4-683a-41d6-964f-5c8290137f1e,1b4c73c7-2bc5-41cc-827c-c46897e212c9,1e47c3bc-d8d0-42cd-8cf5-cc7870221c59,2090ca69-4094-45f9-985f-a137bbb449b2,2347fa3d-c4af-4ec9-93ca-4ffbc7ce7a3e,259e5b31-dd0a-4c30-b1f7-7cb9294a047e,285b7cd9-8834-4ba4-99b1-02e665d53b8b,2ad15788-b68c-4f13-b96d-f8dc72ec8d3c,2d442a98-b977-47c5-b321-a28bec5bbee7,300b5f1c-24b9-42eb-8d70-c6e6b1f010b5,327121cf-8813-4eef-b769-273512ade3ec,353cd2b6-0bcd-4392-800b-398f1f95a26d,3771edc7-277f-451e-99ed-7dd2cc0358c8,3abae78e-9739-45bc-9d2a-b6a891cc8c5f,3d73e280-91c3-4bcd-ab1f-ad0e3c798a7c,40155190-712e-4a03-a717-537c10d0cbee,430755f5-efde-4adc-8166-bca0f6bd185a,457decf4-aff4-44ac-a527-9896339e9d78,4822960c-86d8-405f-92bb-704f12100797,4aa22a76-8796-46ef-9e50-8735913f246e,4cf59db9-d6a2-477e-a7fb-e7f1ff392345,50229955-60ee-461d-b810-6299e8ede8b4,530e85d3-fde4-4413-bc36-7b44925d6e9c,5657c3bc-9f9c-402b-b3b0-b46b57f91ee5,58f797ef-6bd0-4ea9-bad5-bdee1e1ea8b9,5b3f6fbe-b55f-4faa-82d8-c092d50db5d4,5df5155f-2015-42f2-a4f4-3faf086058b9,60728578-f62f-4aa8-9a8b-3ea897fa7681,637eb296-1dc8-41d7-949f-64e9d2309d82,65efdb61-0c0a-4e04-a0aa-e6cc2e68f95b,6882bef1-27a1-429c-b80e-e155836b7e25,6b150811-621f-4331-98e4-726c7487efca,6db90715-69ed-461d-b55f-7b0c163dae13,70ddbe21-332b-49c0-aad0-645577c7ed4a,730b1f18-6245-47f6-9c1e-c74ae23741d8,75450bab-d60b-43c3-a7eb-eb7aad0790df,77cf7a70-e1c7-46f2-846b-fc186e5800d1,7a60c937-700c-4872-bff3-b9ee7deeb4bb,7d413b35-b2b6-40e8-8b98-a69b4adf4873,7fb76dbe-8d52-414b-9baf-f8768f403c91,824c969f-9af6-4151-8462-a01856cd35c9,84bc8a53-2ee3-4d54-be7a-5849837f5c23,878ed8b4-f802-464d-865f-c394f611c254,898c5890-8e9e-402c-9500-93ddb716e54a,8bc7aa7d-9e25-444b-abdd-9f970c76d226,8e16229c-d6a3-4d6b-9d54-9063e44fee0d,9050e18c-55f6-4066-8a37-78f48ef990e0,9269e5a7-edd8-44cf-a850-9c5f6f0cf2ec,94d8c19c-afd2-4765-9aea-92aa2a7c50cf,978df8ba-90c8-4178-b46f-59a8414436a7,99d89759-5cdf-4fce-ad43-6f34bcae4291,9c284ad7-c3a2-47ef-a5d2-7a1fb840863b,9ed32aa3-eef8-4e2c-b279-b2a79f062802,a163bb22-b901-4303-85a9-62ab7b5a99a9,a3e03662-827a-40f1-a1c6-690716d45419,a6a625b7-5522-44d0-95f0-bf2bdbef932c,a95e51dc-0956-4475-83ae-a41d391f7169,ac906b78-acef-4c17-ba61-02e1514811ff,af2e92a8-61a0-4893-bed6-1fd319c01c09,b20dbd0d-4a9f-401c-88a4-25b84d215f1c,b4ceda62-7683-4b53-bb9e-46209dce724d,b759fd6f-c8ff-4411-9ccd-4ffd3dc26038,b9db83b4-52d9-4372-a30e-0e7fb305af8a,bc1f7aef-3a4e-4fa2-80c7-c70039d354fb,bddfd17f-6734-43a2-9e78-55f1eca74fb4,c03054ba-7873-4b96-af6c-be18e6c3f2f3,c29d0d3e-f52d-4613-97c6-f6f27c6f0776,c48eed2f-7d92-4934-8953-a40cd5ed4e83,c6df1a12-9da9-48b8-b03b-87bf855bda8d,c979d826-7143-41c0-9336-076d6ef693ec,cc3804b0-88d6-4c31-83e2-5f59a6dcc462,ced519b1-b856-4f00-b8f8-a0be4199affd,d1ab2aed-e2c8-42ad-a7bd-a687c0b5d5b2,d3f3bcb9-26c5-4681-9b85-96bb1267f69b,d65c5c7e-11c7-4cc6-98d2-90fc107035ca,d8ca7739-f8cf-4fd1-bc29-a9d6fdd44030,db4e11cf-e6e0-40ed-ba4c-a7551b9a7ab1,de7fa6de-90dc-49b8-b86a-afc2cbe11523,e0d8186a-11a8-4000-a630-caa86b5d5a16,e33eb335-ba8b-4aa1-aac1-538e1be9e006,e5c43d4f-f2bf-4027-bcaa-ba185f1f55fe,e81b88d8-4abb-4a03-9492-fd716fcb9def,eb774db0-7e61-4821-8543-b57138692fa8,ee2e8e26-20bc-4784-8177-14aaf60081c8,f0b78a9f-ae6e-4e1d-89f8-ec253c9c572d,f359d614-ffb4-4c5d-9e66-518d70ffe26a,f5b9d45c-1388-4a26-8e16-5dd331b69715,f8340cbf-010b-4f58-bd3e-9864fbab28be,fad8492e-f12f-472e-9eb6-b70e4714d81e,fd5b3384-193c-4be3-a122-71fd6f4cedff,ffebdedd-d88e-4037-8942-dcc611d6c4c7} | -0.017304245 |                   |                        |
 pg_temp_3  | demo      | a       |            1 | pg_temp_3  | demo      | a       | f         |         0 |         4 |          10 | {10,9,8,7,6,5,4,3,2,1}                                                                                                                                                                                                                                                                                | {0.18181819,0.16363636,0.14545454,0.12727273,0.10909091,0.09090909,0.07272727,0.054545455,0.036363635,0.018181818}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |            1 |                   |                        |
 pg_temp_3  | demo      | b       |   0.57577896 | pg_temp_3  | demo      | b       | f         |         0 |         4 | -0.18181819 | {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100} | {0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818,0.0018181818} | {101,105,110,115,120,125,130,135,140,145,150,155,160,165,170,175,180,185,190,195,200,206,212,217,223,229,234,240,245,251,257,262,268,274,279,285,290,296,302,308,315,321,328,334,340,347,353,360,366,373,379,385,392,398,405,413,420,428,435,443,450,458,465,473,480,488,495,503,512,521,530,539,548,557,566,575,584,593,603,614,625,637,648,659,670,682,693,705,720,735,750,765,780,795,815,838,860,883,910,955,1000}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     |   0.57577896 |                   |                        |
 pg_temp_3  | demo      | c       |            1 | pg_temp_3  | demo      | c       | f         |         0 |         4 |           1 | {0}                                                                                                                                                                                                                                                                                                   | {1}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                            |            1 |                   |                        |
(4 rows)

postgres=# select * from pg_class where relname='demo';
  oid  | relname | relnamespace | reltype | reloftype | relowner | relam | relfilenode | reltablespace | relpages | reltuples | relallvisible | reltoastrelid | relhasindex | relisshared | relpersistence | relkind | relnatts | relchecks | relhasrules | relhastriggers | relhassubclass | relrowsecurity | relforcerowsecurity | relispopulated | relreplident | relispartition | relrewrite | relfrozenxid | relminmxid | relacl | reloptions | relpartbound
-------+---------+--------------+---------+-----------+----------+-------+-------------+---------------+----------+-----------+---------------+---------------+-------------+-------------+----------------+---------+----------+-----------+-------------+----------------+----------------+----------------+---------------------+----------------+--------------+----------------+------------+--------------+------------+--------+------------+--------------
 18338 | demo    |        18145 |   18340 |         0 |       10 |     2 |       18338 |             0 |       42 |      5428 |            42 |             0 | t           | f           | t              | r       |        4 |         0 | f           | f              | f              | f              | f                   | t              | d            | f              |          0 |         2026 |          1 |        |            |
(1 row)

```

Because I already know which one will make the difference, I save the statistics about index correlation by generating the statements to set them back:

```sql
postgres=# select string_agg(
format('update pg_statistic set stanumbers%s=%L where starelid=%s and staattnum=%s and stakind%s=3;'
,n,array[correlation],starelid,staattnum,n
),e'\n' order by staattnum) as restore_correlation
 from pg_stats
 natural join (select oid as starelid, relname as tablename, relnamespace from pg_class) c
 natural join (select oid as relnamespace, nspname as schemaname from pg_namespace) n
 natural join (select attrelid as starelid, attname, attnum as staattnum from pg_attribute) a
 cross join (select generate_series(1,5) n) g
where tablename='demo' and attname='a';
                                      restore_correlation
------------------------------------------------------------------------------------------------
 update pg_statistic set stanumbers1='{1}' where starelid=18338 and staattnum=2 and stakind1=3;+
 update pg_statistic set stanumbers2='{1}' where starelid=18338 and staattnum=2 and stakind2=3;+
 update pg_statistic set stanumbers3='{1}' where starelid=18338 and staattnum=2 and stakind3=3;+
 update pg_statistic set stanumbers4='{1}' where starelid=18338 and staattnum=2 and stakind4=3;+
 update pg_statistic set stanumbers5='{1}' where starelid=18338 and staattnum=2 and stakind5=3;
(1 row)

postgres=# \gset
```

You may be surprised by my query but `pg_statistic` is not very relational, the value can to to different places, and that's why I have multiple updates for one value.

The point of this article is that I do not expect a change when analyzing the table because my updated rows are still well clustered. My query can get all from the same heap page:
```sql
postgres=# select ctid,* from demo  where a=1  order by b limit 10;
  ctid   |                  id                  | a | b  | c
---------+--------------------------------------+---+----+---
 (40,61) | 163d93e7-ed84-4be8-9f87-f8771895490e | 1 |  1 | 1
 (40,62) | a6fd2b75-7d96-4af5-a0fd-6deb8f03e2ed | 1 |  2 | 1
 (40,63) | 8d730e02-a4c0-45bf-afc9-5a44f9241a64 | 1 |  3 | 1
 (40,64) | 1c0d6e1c-e88e-47f0-bc8d-71daa85170dd | 1 |  4 | 1
 (40,65) | 130ffe14-705a-476c-94b6-fa0354efe994 | 1 |  5 | 1
 (40,66) | 3dbff06e-5126-4abb-87c7-a24e07a3e37a | 1 |  6 | 1
 (40,67) | 92248fb9-10ba-47a7-b13f-c521e1e11a4b | 1 |  7 | 1
 (40,68) | 291239e1-23a7-4398-b6af-a17352fab837 | 1 |  8 | 1
 (40,69) | c9c997d1-0df4-4a81-bee3-989fe3d42cb9 | 1 |  9 | 1
 (40,70) | d54c50c4-fb1a-4126-b15c-11de36a7316b | 1 | 10 | 1
(10 rows)
```
Looking at the CTID, the rows I'm interested in seems to be well clustered.

## Analyze

I analyze the table, like what would happen with auto-analyze on a non-temporary table, and run my query again:
```sql
postgres=# analyze demo;
ANALYZE

postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..28.20 rows=10 width=28) (actual time=0.020..0.048 rows=10 loops=1)
   Buffers: local hit=102
   ->  Index Scan using demob on demo  (cost=0.28..279.41 rows=100 width=28) (actual time=0.019..0.046 rows=10 loops=1)
         Filter: (a = 1)
         Rows Removed by Filter: 90
         Buffers: local hit=102
 Planning:
   Buffers: shared hit=16
 Planning Time: 0.147 ms
 Execution Time: 0.060 ms
(10 rows)
```
The query planner has chosen the other index, to avoid a sort, but having to read more rows to discard to apply the filter. Obviously, this was a bad choice, reading 102 buffers instead of 4.

I can prove that it was a bad choice by removing the index (or using `/*+ IndexScan( demo demoa ) */` if `pg_hint_plan` is installed):
```sql
postgres=# drop index demob;
DROP INDEX
postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=45.44..45.47 rows=10 width=28) (actual time=0.043..0.045 rows=10 loops=1)
   Buffers: local hit=4
   ->  Sort  (cost=45.44..45.69 rows=100 width=28) (actual time=0.042..0.043 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=4
         ->  Index Scan using demoa on demo  (cost=0.28..43.28 rows=100 width=28) (actual time=0.009..0.027 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=4
 Planning:
   Buffers: shared hit=5 dirtied=1
 Planning Time: 0.120 ms
 Execution Time: 0.058 ms
(13 rows)
```
This plan is much better but the PostgreSQL query planner didn't choose it because it estimated the cost to 45.47 which is higher than the estimation from the other index that was 28.20

The reason for this higher estimation is in the Index Scan which was estimated to 10.02 before the analyze and to 43.28 after it. It is not a high factor, but it is a huge change in the access path.

## Correlation

I suspect the correlation factor, which is there to estimate the random reads to the table when coming from an index entry:
```sql
postgres=# select schemaname,tablename,attname,correlation from pg_stats where tablename='demo'
;
 schemaname | tablename | attname | correlation
------------+-----------+---------+--------------
 pg_temp_3  | demo      | id      | -0.023444278
 pg_temp_3  | demo      | a       |   0.89289254
 pg_temp_3  | demo      | b       |   0.48658225
 pg_temp_3  | demo      | c       |            1
(4 rows)
```
It was 1 for the column `a` before the analyze, but 0.89289254 after the analyze. It doesn't look much different but seems to be enough to have the query planner choosing another index.

This is why I saved the previous one, and I run the statements to set to the previous value:

```sql
postgres=# select :'restore_correlation';
                                            ?column?
------------------------------------------------------------------------------------------------
 update pg_statistic set stanumbers1='{1}' where starelid=18338 and staattnum=2 and stakind1=3;+
 update pg_statistic set stanumbers2='{1}' where starelid=18338 and staattnum=2 and stakind2=3;+
 update pg_statistic set stanumbers3='{1}' where starelid=18338 and staattnum=2 and stakind3=3;+
 update pg_statistic set stanumbers4='{1}' where starelid=18338 and staattnum=2 and stakind4=3;+
 update pg_statistic set stanumbers5='{1}' where starelid=18338 and staattnum=2 and stakind5=3;
(1 row)

postgres=# :restore_correlation
UPDATE 0
UPDATE 1
UPDATE 0
UPDATE 0
UPDATE 0

postgres=# select schemaname,tablename,attname,correlation from 
           pg_stats where tablename='demo'
;
 schemaname | tablename | attname | correlation
------------+-----------+---------+--------------
 pg_temp_3  | demo      | id      | -0.023444278
 pg_temp_3  | demo      | a       |            1
 pg_temp_3  | demo      | b       |   0.48658225
 pg_temp_3  | demo      | c       |            1
(4 rows)
```
The `pg_statistic` table is a bit weird, the values can be at different places, and that's why I had several updates but updated on the Statistic Kind number 3 which is the correlation.

## Using the previous correlation factor

With the previous correlation, the cost is back to 10.3 which means that the right index would have been picked up even if I didn't drop the other one:
```sql
postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=12.19..12.22 rows=10 width=28) (actual time=0.043..0.045 rows=10 loops=1)
   Buffers: local hit=4
   ->  Sort  (cost=12.19..12.44 rows=100 width=28) (actual time=0.042..0.043 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=4
         ->  Index Scan using demoa on demo  (cost=0.28..10.03 rows=100 width=28) (actual time=0.008..0.026 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=4
 Planning:
   Buffers: shared hit=3
 Planning Time: 0.144 ms
 Execution Time: 0.058 ms
(13 rows)
```

However, this is not a sustainable solution because in a regular table, it will be analyzed again, the query would get a higher cost, and a bad index may be chosen.

```sql
postgres=# vacuum full demo;
VACUUM

postgres=# analyze demo;
ANALYZE

postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=44.63..44.66 rows=10 width=28) (actual time=0.039..0.041 rows=10 loops=1)
   Buffers: local hit=4
   ->  Sort  (cost=44.63..44.88 rows=100 width=28) (actual time=0.038..0.039 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=4
         ->  Index Scan using demoa on demo  (cost=0.28..42.47 rows=100 width=28) (actual time=0.007..0.023 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=4
 Planning:
   Buffers: shared hit=12
 Planning Time: 0.138 ms
 Execution Time: 0.054 ms
(13 rows)

postgres=# select ctid,* from demo  where a=1  order by b limit 10
;
   ctid   |                  id                  | a | b  | c
----------+--------------------------------------+---+----+---
 (39,97)  | 163d93e7-ed84-4be8-9f87-f8771895490e | 1 |  1 | 1
 (39,98)  | a6fd2b75-7d96-4af5-a0fd-6deb8f03e2ed | 1 |  2 | 1
 (39,99)  | 8d730e02-a4c0-45bf-afc9-5a44f9241a64 | 1 |  3 | 1
 (39,100) | 1c0d6e1c-e88e-47f0-bc8d-71daa85170dd | 1 |  4 | 1
 (39,101) | 130ffe14-705a-476c-94b6-fa0354efe994 | 1 |  5 | 1
 (39,102) | 3dbff06e-5126-4abb-87c7-a24e07a3e37a | 1 |  6 | 1
 (39,103) | 92248fb9-10ba-47a7-b13f-c521e1e11a4b | 1 |  7 | 1
 (39,104) | 291239e1-23a7-4398-b6af-a17352fab837 | 1 |  8 | 1
 (39,105) | c9c997d1-0df4-4a81-bee3-989fe3d42cb9 | 1 |  9 | 1
 (39,106) | d54c50c4-fb1a-4126-b15c-11de36a7316b | 1 | 10 | 1
(10 rows)
```
I listed the CTID to show you that the query planner was wrong. My rows are well correlated: all in the same block, in the same order as the index value.

## PageInspect

I can check with PageInspect that the index entries in the index leaf block are in the same order as the rows in the heap table:
```sql
postgres=# create extension if not exists pageinspect;
CREATE EXTENSION

postgres=# select * from bt_metap('demoa');
 magic  | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
 340322 |       4 |    3 |     1 |        3 |         1 |                         0 |                      -1 | t
(1 row)

postgres=# select substr(data,1,30), itemoffset, ctid, itemlen, nulls, vars, dead , *
           from bt_page_items(get_raw_page('demoa', 1))
           where data < '02' order by data
;
         substr          | itemoffset |   ctid    | itemlen | nulls | vars | dead | itemoffset |   ctid    | itemlen | nulls | vars |          data           | dead |  htid   |                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 tids
-------------------------+------------+-----------+---------+-------+------+------+------------+-----------+---------+-------+------+-------------------------+------+---------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 01 00 00 00 00 00 00 00 |          2 | (16,8292) |     616 | f     | f    | f    |          2 | (16,8292) |     616 | f     | f    | 01 00 00 00 00 00 00 00 | f    | (39,97) | {"(39,97)","(39,98)","(39,99)","(39,100)","(39,101)","(39,102)","(39,103)","(39,104)","(39,105)","(39,106)","(39,107)","(39,108)","(39,109)","(39,110)","(39,111)","(39,112)","(39,113)","(39,114)","(39,115)","(39,116)","(39,117)","(39,118)","(39,119)","(39,120)","(39,121)","(39,122)","(39,123)","(39,124)","(39,125)","(39,126)","(39,127)","(39,128)","(39,129)","(39,130)","(39,131)","(39,132)","(39,133)","(39,134)","(39,135)","(39,136)","(40,1)","(40,2)","(40,3)","(40,4)","(40,5)","(40,6)","(40,7)","(40,8)","(40,9)","(40,10)","(40,11)","(40,12)","(40,13)","(40,14)","(40,15)","(40,16)","(40,17)","(40,18)","(40,19)","(40,20)","(40,21)","(40,22)","(40,23)","(40,24)","(40,25)","(40,26)","(40,27)","(40,28)","(40,29)","(40,30)","(40,31)","(40,32)","(40,33)","(40,34)","(40,35)","(40,36)","(40,37)","(40,38)","(40,39)","(40,40)","(40,41)","(40,42)","(40,43)","(40,44)","(40,45)","(40,46)","(40,47)","(40,48)","(40,49)","(40,50)","(40,51)","(40,52)","(40,53)","(40,54)","(40,55)","(40,56)","(40,57)","(40,58)","(40,59)","(40,60)"}
(1 row)
```
This looks well correlated to me, but probably not enough according to the statistics.

## Reorganize the table (CLUSTER)

Another solution is to reorganize the table to get the best correlation with the index, using CLUSTER:
```sql
postgres=# cluster demo using demoa;
CLUSTER
postgres=# analyze demo;
ANALYZE
postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=12.19..12.22 rows=10 width=28) (actual time=0.042..0.044 rows=10 loops=1)
   Buffers: local hit=1 read=2
   ->  Sort  (cost=12.19..12.44 rows=100 width=28) (actual time=0.042..0.042 rows=10 loops=1)
         Sort Key: b
         Sort Method: top-N heapsort  Memory: 25kB
         Buffers: local hit=1 read=2
         ->  Index Scan using demoa on demo  (cost=0.28..10.03 rows=100 width=28) (actual time=0.010..0.024 rows=100 loops=1)
               Index Cond: (a = 1)
               Buffers: local hit=1 read=2
 Planning:
   Buffers: shared hit=16, local read=2
 Planning Time: 0.197 ms
 Execution Time: 0.057 ms
(13 rows)

postgres=# select ctid,* from demo  where a=1  order by b limit 10
;
  ctid  |                  id                  | a | b  | c
--------+--------------------------------------+---+----+---
 (0,1)  | 163d93e7-ed84-4be8-9f87-f8771895490e | 1 |  1 | 1
 (0,2)  | a6fd2b75-7d96-4af5-a0fd-6deb8f03e2ed | 1 |  2 | 1
 (0,3)  | 8d730e02-a4c0-45bf-afc9-5a44f9241a64 | 1 |  3 | 1
 (0,4)  | 1c0d6e1c-e88e-47f0-bc8d-71daa85170dd | 1 |  4 | 1
 (0,5)  | 130ffe14-705a-476c-94b6-fa0354efe994 | 1 |  5 | 1
 (0,6)  | 3dbff06e-5126-4abb-87c7-a24e07a3e37a | 1 |  6 | 1
 (0,7)  | 92248fb9-10ba-47a7-b13f-c521e1e11a4b | 1 |  7 | 1
 (0,8)  | 291239e1-23a7-4398-b6af-a17352fab837 | 1 |  8 | 1
 (0,9)  | c9c997d1-0df4-4a81-bee3-989fe3d42cb9 | 1 |  9 | 1
 (0,10) | d54c50c4-fb1a-4126-b15c-11de36a7316b | 1 | 10 | 1
(10 rows)
```
This is usually not an acceptable solution because it requires downtime (except if you do it with `pg_repack` instead), may have side effects with other indexes (you can cluster on one index only), and is not sustainable (new updates will shuffle the rows again).

## Provide the best index to avoid bad plans

My go-to solution for addressing plan instability is to use a more robust index that isn't sensitive to small fluctuations in query planner estimates. When you filter and sort, a single index should provide both:

```sql
postgres=# create index demoab on demo(a asc, b asc);
CREATE INDEX

postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                       QUERY PLAN
------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..8.26 rows=10 width=28) (actual time=0.012..0.015 rows=10 loops=1)
   Buffers: local hit=1 read=2
   ->  Index Scan using demoab on demo  (cost=0.28..80.03 rows=100 width=28) (actual time=0.011..0.013 rows=10 loops=1)
         Index Cond: (a = 1)
         Buffers: local hit=1 read=2
 Planning:
   Buffers: shared hit=18, local read=1
 Planning Time: 0.166 ms
 Execution Time: 0.027 ms
(9 rows)
```
The cost is smaller than the index on `b` that I have deleted. To be sure, let's re-create it and test again:
```sql
postgres=# create index demob on demo(b asc);
CREATE INDEX

postgres=# update demo set c=c+1 where a =1;
UPDATE 100

postgres=# vacuum analyze demo;
VACUUM

postgres=# select schemaname,tablename,attname,correlation from pg_stats where tablename='demo';
 schemaname | tablename | attname | correlation
------------+-----------+---------+--------------
 pg_temp_3  | demo      | id      | -0.023419052
 pg_temp_3  | demo      | a       |   0.89289254
 pg_temp_3  | demo      | b       |    0.4865387
 pg_temp_3  | demo      | c       |            1
(4 rows)

postgres=# explain (analyze, buffers)
           select * from demo where a=1
           order by b limit 10
;
                                                       QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..10.30 rows=10 width=28) (actual time=0.010..0.014 rows=10 loops=1)
   Buffers: local hit=3
   ->  Index Scan using demoab on demo  (cost=0.28..100.49 rows=100 width=28) (actual time=0.010..0.012 rows=10 loops=1)
         Index Cond: (a = 1)
         Buffers: local hit=3
 Planning:
   Buffers: shared hit=14, local hit=1
 Planning Time: 0.273 ms
 Execution Time: 0.026 ms
(9 rows)
```
The right index is still used but in my opinion the cost difference is still very low (10.30 vs 28.20) to clear all risks. To be safe, we can:
 - change to a covering index `on demo ( a, b ) include (c, id)` that will makes the query cheaper when using this index.
 - use `pg_hint_plan` to force the index we have designed for this query: `/*+ IndexScan(demo demoab) */`
 - use `pg_hint_plan` to increase the cost of reading too many tuples: `/*+ Set(cpu_tuple_cost 1) */`

 
You may be surprised by the recommandation of using hints, but this is a limitation of the Cost Based Optimizer, and we need to workaround. For such query, you are more concerned about the scalability, and how the response time is proportional to the number of rows in the result. A plan that has to read more rows, sort them, and discard them should be avoided even if the estimated cost is lower.

Note that, as far as I know, extended statistics are not useful here because PostgreSQL doesn't gather their correlation. This means that there's only a single-column correlation that doesn't show the true correlation with a multi-column index. To compare, Oracle stores correlation (called clustering factor) per index and not per column.