5 ms·

Now try adding a new organization with ID 11 and timestamps on the tail end (>2020-01-01). And query for that ID.

dventimi 3y ago
Sure. -- 1e7 entries for organization_id = 10 distributed evenly over the 10 -- years after '2020-01-01 00:00:00' as requested insert into foo ( organization_id, created_at, updated_at) select 10, --9 was the previous max organization_id so presumably 10 is OK rather than 11 generate_series('2020-01-01 00:00:00'::timestamp, '2020-01-01 00:00:00'::timestamp + interval '10 years', (interval '10 years')/1e7), generate_series('2020-01-01 00:00:00'::timestamp, '2020-01-01 00:00:00'::timestamp + interval '10 years', (interval '10 years')/1e7); cluster foo using foo_created_at_idx; --should be a no-op but why not vacuum analyze; --same thing create index on foo (updated_at) where organization_id = 10; --stats will be highly-skewed so we had better fix that explain analyze select * from foo where organization_id = 10 order by updated_at limit 10; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.43..23.35 rows=10 width=57) (actual time=0.073..0.079 rows=10 loops=1) -> Index Scan using foo_updated_at_idx1 on foo (cost=0.43..23495662.12 rows=10254706 width=57) (actual time=0.071..0.075 rows=10 loops=1) Planning Time: 0.185 ms Execution Time: 0.101 ms BTW, SQLite was no better at solving this riddle. It also failed miserably in its query plan until I created the same partial index.
- pgaddict 3y ago
  Not sure, but I see this ... I simplified the SQL a little bit - I don't think it's necessary to have two timestamps and cluster on one of them. The other timestamp is not correlated, so the access through that index will be random anyway. And I used 10M rows only. create unlogged table foo ( id int primary key generated by default as identity, organization_id int, created_at timestamptz ); insert into foo (id, organization_id, created_at) select i, floor(random()*10), timestamp '2010-01-01' + random()*(timestamp '2020-01-01' - timestamp '2010-01-01') from generate_series(1, 1e7) s(i); insert into foo (id, organization_id, created_at) select 1e7 + i, 10, timestamp '2020-01-01' + random()*(timestamp '2021-01-01' - timestamp '2020-01-01') from generate_series(1, 100000) s(i); -- see the timestamp range for each org select organization_id, min(created_at), max(created_at) from foo group by 1 order by 1; create index on foo (created_at); vacuum analyze; checkpoint; set max_parallel_workers_per_gather = 0; explain analyze select * from foo where organization_id = 1 order by created_at limit 10; explain analyze select * from foo where organization_id = 10 order by created_at limit 10; For me, this produces: QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ Limit (cost=0.43..5.62 rows=10 width=16) (actual time=0.072..0.378 rows=10 loops=1) -> Index Scan using foo_created_at_idx on foo (cost=0.43..505826.61 rows=975331 width=16) (actual time=0.071..0.375 rows=10 loops=1) Filter: (organization_id = 1) Rows Removed by Filter: 76 Planning Time: 0.040 ms Execution Time: 0.390 ms (6 rows) QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.43..43.61 rows=10 width=16) (actual time=30316.079..30316.117 rows=10 loops=1) -> Index Scan using foo_created_at_idx on foo (cost=0.43..505826.61 rows=117161 width=16) (actual time=30316.078..30316.114 rows=10 loops=1) Filter: (organization_id = 10) Rows Removed by Filter: 10000000 Planning Time: 0.041 ms Execution Time: 30316.136 ms (6 rows) So perhaps there's something "wrong" with your data, because there's no "Filter" or "Rows Removed by Filter" in your query plans.
  - dventimi 3y ago
    Now add a partial index and re-run your queries. create index on foo (created_at) where organization_id = 10;
    - pgaddict 3y ago
      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. 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: QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------- Limit (cost=182766.62..182766.65 rows=10 width=16) (actual time=441.647..441.650 rows=10 loops=1) -> Sort (cost=182766.62..182988.83 rows=88881 width=16) (actual time=441.642..441.644 rows=10 loops=1) Sort Key: created_at Sort Method: top-N heapsort Memory: 25kB -> Seq Scan on foo (cost=0.00..180845.94 rows=88881 width=16) (actual time=210.901..437.292 rows=100000 loops=1) Filter: (organization_id = 10) Rows Removed by Filter: 10000000 Planning Time: 0.327 ms Execution Time: 441.696 ms (9 rows) That's ~2 orders of magnitude faster, but the optimizer has no way to predict this. Sure, the composite/partial indexes will do much better, but my intent was to explain why LIMIT queries have this problem.
      - dventimi 3y ago
        > 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.

Sure. -- 1e7 entries for organization_id = 10 distributed evenly over the 10 -- years after '2020-01-01 00:00:00' as requested insert into foo ( organization_id, created_at, updated_at) select 10, --9 was the previous max organization_id so presumably 10 is OK rather than 11 generate_series('2020-01-01 00:00:00'::timestamp, '2020-01-01 00:00:00'::timestamp + interval '10 years', (interval '10 years')/1e7), generate_series('2020-01-01 00:00:00'::timestamp, '2020-01-01 00:00:00'::timestamp + interval '10 years', (interval '10 years')/1e7); cluster foo using foo_created_at_idx; --should be a no-op but why not vacuum analyze; --same thing create index on foo (updated_at) where organization_id = 10; --stats will be highly-skewed so we had better fix that explain analyze select * from foo where organization_id = 10 order by updated_at limit 10; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.43..23.35 rows=10 width=57) (actual time=0.073..0.079 rows=10 loops=1) -> Index Scan using foo_updated_at_idx1 on foo (cost=0.43..23495662.12 rows=10254706 width=57) (actual time=0.071..0.075 rows=10 loops=1) Planning Time: 0.185 ms Execution Time: 0.101 ms BTW, SQLite was no better at solving this riddle. It also failed miserably in its query plan until I created the same partial index.

pgaddict 3y ago
Not sure, but I see this ... I simplified the SQL a little bit - I don't think it's necessary to have two timestamps and cluster on one of them. The other timestamp is not correlated, so the access through that index will be random anyway. And I used 10M rows only. create unlogged table foo ( id int primary key generated by default as identity, organization_id int, created_at timestamptz ); insert into foo (id, organization_id, created_at) select i, floor(random()*10), timestamp '2010-01-01' + random()*(timestamp '2020-01-01' - timestamp '2010-01-01') from generate_series(1, 1e7) s(i); insert into foo (id, organization_id, created_at) select 1e7 + i, 10, timestamp '2020-01-01' + random()*(timestamp '2021-01-01' - timestamp '2020-01-01') from generate_series(1, 100000) s(i); -- see the timestamp range for each org select organization_id, min(created_at), max(created_at) from foo group by 1 order by 1; create index on foo (created_at); vacuum analyze; checkpoint; set max_parallel_workers_per_gather = 0; explain analyze select * from foo where organization_id = 1 order by created_at limit 10; explain analyze select * from foo where organization_id = 10 order by created_at limit 10; For me, this produces: QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------ Limit (cost=0.43..5.62 rows=10 width=16) (actual time=0.072..0.378 rows=10 loops=1) -> Index Scan using foo_created_at_idx on foo (cost=0.43..505826.61 rows=975331 width=16) (actual time=0.071..0.375 rows=10 loops=1) Filter: (organization_id = 1) Rows Removed by Filter: 76 Planning Time: 0.040 ms Execution Time: 0.390 ms (6 rows) QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.43..43.61 rows=10 width=16) (actual time=30316.079..30316.117 rows=10 loops=1) -> Index Scan using foo_created_at_idx on foo (cost=0.43..505826.61 rows=117161 width=16) (actual time=30316.078..30316.114 rows=10 loops=1) Filter: (organization_id = 10) Rows Removed by Filter: 10000000 Planning Time: 0.041 ms Execution Time: 30316.136 ms (6 rows) So perhaps there's something "wrong" with your data, because there's no "Filter" or "Rows Removed by Filter" in your query plans.
- dventimi 3y ago
  Now add a partial index and re-run your queries. create index on foo (created_at) where organization_id = 10;
  - pgaddict 3y ago
    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. 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: QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------- Limit (cost=182766.62..182766.65 rows=10 width=16) (actual time=441.647..441.650 rows=10 loops=1) -> Sort (cost=182766.62..182988.83 rows=88881 width=16) (actual time=441.642..441.644 rows=10 loops=1) Sort Key: created_at Sort Method: top-N heapsort Memory: 25kB -> Seq Scan on foo (cost=0.00..180845.94 rows=88881 width=16) (actual time=210.901..437.292 rows=100000 loops=1) Filter: (organization_id = 10) Rows Removed by Filter: 10000000 Planning Time: 0.327 ms Execution Time: 441.696 ms (9 rows) That's ~2 orders of magnitude faster, but the optimizer has no way to predict this. Sure, the composite/partial indexes will do much better, but my intent was to explain why LIMIT queries have this problem.
    - dventimi 3y ago
      > 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.