> Yeah. But the whole discussion here was about the dilemma the optimizer faces if it only has the two indexes on (created_at) and (organization_id), and why the assumption of independence/uniformity does not work for the skewed case.

Was it? The whole discussion started when zac23or said at the top of the thread that their biggest problem with PostgreSQL is its optimizer, that this is their worst example, that it needs an index on (organization_id, created_id) for it to be solved, and that SQLite and MS SQL Server do not need that index on (organization_id, created_at). They didn't initially say how their data are distributed other than that there are millions of rows with organization_id=10 and they didn't initially say that their data are skewed. Later, they said that the data are "distributed equally" and added that organization_id is random, which would be consistent, though they did say that their data are clustered not by created_at but by organization_id. Consequently, the skewed distribution seems to be a special case that you added in this sub-thread. That's fine, but that's a different albeit related problem from the one zac23or posed. If the original problem is, "Arrange for PostgreSQL to perform well on this query on this data model for equally-distributed data without adding an index on (organization_id, created_id)." that problem is solved. It can be done. If your additional problem is "Arrange for PostgreSQL to perform well on this query on this data model for unequally-distributed data without adding an index on (organization_id, created_at)." that problem is also solved with a partial index on just (created_at).

> Of course, adding a composite or partial index may help, but people are confused why the optimizer is not smart enough to just switch to the other index, which on my machine does this:

I'm curious how you forced the optimizer to switch to that query plan if it's not smart enough to do it on its own. I don't know, but I suspect you ordered by an expression, with something like

explain analyze select * from foo where organization_id = 10 order by created_at + interval '0 day' limit 10;

That produces nearly identical results on my machine, which increases my suspicion.

QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
Limit (cost=183393.70..183393.73 rows=10 width=24) (actual time=310.827..310.828 rows=10 loops=1)
-> Sort (cost=183393.70..183657.98 rows=105713 width=24) (actual time=307.195..307.196 rows=10 loops=1)
Sort Key: ((created_at + '00:00:00'::interval))
Sort Method: top-N heapsort Memory: 26kB
-> Seq Scan on foo (cost=0.00..181109.28 rows=105713 width=24) (actual time=294.054..300.537 rows=100000 loops=1)
Filter: (organization_id = 10)
Rows Removed by Filter: 10000000
Planning Time: 0.116 ms
JIT:
Functions: 5
Options: Inlining false, Optimization false, Expressions true, Deforming true
Timing: Generation 0.594 ms, Inlining 0.000 ms, Optimization 0.347 ms, Emission 3.296 ms, Total 4.237 ms
Execution Time: 311.490 ms

This plan is better for organization_id=10 than the one the optimizer chose, without resorting to a partial index, but it comes at a cost: this plan is worse for any of the other values of organization_id, whose data are not skewed.

I think a third question, which is implicit in your comments is, "Well then why doesn't the optimizer use one plan for organization_id=10 and the other plan for the other values of organization_id?" That's a good question. Is this possible? Does any other database do this? I don't know. I'll try to find out but if somebody already has the answer, I'd love to hear it.

A fourth question is, "How do other databases perform on this and similar queries?" In my experiments, the picture is still cloudy. With my original data, SQLite chose the same plan and performed just as badly in the skewed case, until I also gave it a partial index. With your data, SQLite actually outperforms PostgreSQL in the skewed case even without the partial index. Why is that? I don't know. These are just experiments for different cases that are highly context-dependent. So far, I don't see enough evidence to support the original claim, that PostgreSQL's optimizer has a problem and that this is an example.