Alright... let's have some test data.
CREATE UNLOGGED TABLE foo( id INTEGER PRIMARY KEY,
doneCleanup BOOL NOT NULL, alertedUser BOOL NOT NULL,
doneCleanupTimestamp TIMESTAMP NOT NULL, initialTimestamp TIMESTAMP NOT NULL);
INSERT INTO foo SELECT n, random()<0.9, random()<0.9,
'2020-01-01'::TIMESTAMP+'1 SECOND'::INTERVAL*(n + random()*1000),
FROM generate_series(1,1000000) n;
VACUUM ANALYZE foo;
CREATE INDEX foo_dad ON foo(doneCleanup, alertedUser, doneCleanupTimestamp DESC) WHERE doneCleanup = true AND alertedUser = true;
EXPLAIN ANALYZE select distinct * FROM foo
doneCleanup = true AND
alertedUser = true AND
order by id asc, initialTimestamp asc limit 100 offset 50000;
Limit (cost=10060.58..10078.70 rows=100 width=22) (actual time=27.482..28.697 rows=100 loops=1)
-> Unique (cost=1000.54..145648.64 rows=798275 width=22) (actual time=7.410..27.133 rows=50100 loops=1)
-> Gather Merge (cost=1000.54..135670.20 rows=798275 width=22) (actual time=7.409..18.259 rows=50100 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Incremental Sort (cost=0.52..42529.43 rows=332615 width=22) (actual time=0.122..6.867 rows=17316 loops=3)
Sort Key: id, initialtimestamp, donecleanup, alerteduser, donecleanuptimestamp
Presorted Key: id
Full-sort Groups: 177 Sort Method: quicksort Average Memory: 27kB Peak Memory: 27kB
Worker 0: Full-sort Groups: 710 Sort Method: quicksort Average Memory: 27kB Peak Memory: 27kB
Worker 1: Full-sort Groups: 739 Sort Method: quicksort Average Memory: 27kB Peak Memory: 27kB
-> Parallel Index Scan using foo_pkey on foo (cost=0.42..27561.76 rows=332615 width=22) (actual time=0.015..4.461 rows=17345 loops=3)
Filter: (donecleanup AND alerteduser AND (donecleanuptimestamp <= '2020-01-12 10:01:57'::timestamp without time zone))
Rows Removed by Filter: 4038
Planning Time: 0.375 ms
Execution Time: 28.778 ms
With these parameters, this plan is fine. For test data generation, I had a hunch that it would be good that something called doneCleanup should be true for the majority of the rows, so I set it at 90% true with "random()<0.9". Also the condition on initialTimeStamp includes most of the table, which means the index is useless, and it is using the index on id to optimize the ORDER BY.
So, I restricted the condition on initialTimeStamp to
...and I reproduced your problem. This index is used:
CREATE INDEX foo_d ON foo(doneCleanupTimestamp DESC) WHERE doneCleanup = true AND alertedUser = true;
....but the other index including columns doneCleanup, alertedUser is not used. Let's try changing the proportion of bools set to true from 90% to 10%.
UPDATE foo SET doneCleanup=NOT doneCleanup, alertedUser=NOT alertedUser;
VACUUM ANALYZE foo;
And now the other index including columns doneCleanup, alertedUser is used if the other is not available. If the smaller index including only doneCleanupTimestamp is there, then it is used instead, and it is faster, as expected.
Doing the update again to restore the previous distribution of bool value, then testing again while messing with random_page_cost, it appears it is possible to make it use the index if random_page_cost is low enough. But the index with the two extra columns is much, much slower.
The bool values in the index are all the same due to the WHERE clause restricting them both to true. So they are useless anyway, and the simpler index on the timestamp column should be used. But what would happen if I removed the WHERE instead? The answer is quite surprising: the index is used, and it is very fast.
So, there seems to be something in the postgres code that makes it not work very well when the bool first column(s) of an index are constant, AND this is specific to indices having WHERE clauses, since if I update all the bool columns to true, it still uses the index and it is fast...