Postgresql bad planning with multicolumn gist and search with empty results

Question

I'm having an issue with a multicolumn index (integer, geom), where geom are PostGIS points, and the integer is a point aggregator with business meaning. I do searches by boxes in the geom column, joining the integer with other tables. When the box covers an empty region, the planner does an index scan looking only the secondary column, very inefficiently. I've spent some time trying to create a scenario with a reproduction of the problem (with less data), and I was able to do something that sounds the same issue, only with integers. This setup will need about 2GB of disk.

/*   0<=n1<=10000 */
/*   0<=n2<=1000 || 3000<=n2<=4000 */
/* s1, r1, r2 to increase I/O needs and avoid index only scans */
create table test as select n as n1, (1000*random())::int as n2, generate_series(1,1000) s1 , random() as r1, random() as r2 from generate_series(1,10000) as n;
insert into test select n as n1, ((1000*random())::int) + 3000 as n2, generate_series(1,1000) s1 , random() as r1, random() as r2 from generate_series(1,10000) as n;
create index ind_test on test using gist (n1,n2);
create table ids as select generate_series(1,5) as n1; -- same problem with just one row on this table
analyze ids;
alter table test alter column n1 set statistics 10000;  --excluding poor stats
alter table test alter column n2 set statistics 10000;  --excluding poor stats
analyze test;
explain analyze select * from test join ids using (n1) where n2 = 1001 and n1 = 1; --Q1 Outside n2 range, Index cond n1 AND n2 < 1ms
explain analyze select * from test join ids using (n1) where n2 = 999;  --Q2 Inside n2 range, Index cond n1 AND n2 < 1ms
explain analyze select * from test join ids using (n1) where n2 = 1000;  --Q3 Inside n2 range, Index cond n1 AND n2 < 1 ms
explain analyze select * from test join ids using (n1) where n2 = 1001;  --Q4 Outside n2 range, Index cond n2 > 100 ms
explain analyze select * from test join ids using (n1) where n2 = 1002;  --Q5 Outside n2 range, Index cond n2 > 100 ms

Below the result of the explains above:

 ➤ psql://postgres@[local]:5432/postgres 

#     explain analyze select * from test join ids using (n1) where n2 = 1001 and n1 = 1; --Q1 Outside n2 range, Index cond n1 AND n2 < 1ms
                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..9.51 rows=1 width=28) (actual time=0.067..0.067 rows=0 loops=1)
   ->  Index Scan using ind_test on test  (cost=0.42..8.44 rows=1 width=28) (actual time=0.067..0.067 rows=0 loops=1)
         Index Cond: ((n1 = 1) AND (n2 = 1001))
   ->  Seq Scan on ids  (cost=0.00..1.06 rows=1 width=4) (never executed)
         Filter: (n1 = 1)
 Planning time: 0.404 ms
 Execution time: 0.096 ms
(7 rows)

Time: 0.826 ms

 ➤ psql://postgres@[local]:5432/postgres 

#     explain analyze select * from test join ids using (n1) where n2 = 999;  --Q2 Inside n2 range, Index cond n1 AND n2 < 1ms
                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..43.29 rows=5 width=28) (actual time=0.098..0.367 rows=7 loops=1)
   ->  Seq Scan on ids  (cost=0.00..1.05 rows=5 width=4) (actual time=0.012..0.014 rows=5 loops=1)
   ->  Index Scan using ind_test on test  (cost=0.42..8.44 rows=1 width=28) (actual time=0.064..0.068 rows=1 loops=5)
         Index Cond: ((n1 = ids.n1) AND (n2 = 999))
 Planning time: 0.994 ms
 Execution time: 0.407 ms
(6 rows)

Time: 1.713 ms

 ➤ psql://postgres@[local]:5432/postgres 

#     explain analyze select * from test join ids using (n1) where n2 = 1000;  --Q3 Inside n2 range, Index cond n1 AND n2 < 1 ms
                                                      QUERY PLAN                                                      
----------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..43.29 rows=3 width=28) (actual time=0.157..0.248 rows=3 loops=1)
   ->  Seq Scan on ids  (cost=0.00..1.05 rows=5 width=4) (actual time=0.010..0.011 rows=5 loops=1)
   ->  Index Scan using ind_test on test  (cost=0.42..8.44 rows=1 width=28) (actual time=0.044..0.046 rows=1 loops=5)
         Index Cond: ((n1 = ids.n1) AND (n2 = 1000))
 Planning time: 0.877 ms
 Execution time: 0.277 ms
(6 rows)

Time: 1.440 ms

 ➤ psql://postgres@[local]:5432/postgres 

#     explain analyze select * from test join ids using (n1) where n2 = 1001;  --Q4 Outside n2 range, Index cond n2 > 100 ms
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..9.55 rows=1 width=28) (actual time=93.247..93.247 rows=0 loops=1)
   Join Filter: (test.n1 = ids.n1)
   ->  Index Scan using ind_test on test  (cost=0.42..8.44 rows=1 width=28) (actual time=93.246..93.246 rows=0 loops=1)
         Index Cond: (n2 = 1001)
   ->  Seq Scan on ids  (cost=0.00..1.05 rows=5 width=4) (never executed)
 Planning time: 0.716 ms
 Execution time: 93.280 ms
(7 rows)

Time: 94.242 ms

 ➤ psql://postgres@[local]:5432/postgres 

#     explain analyze select * from test join ids using (n1) where n2 = 1002;  --Q5 Outside n2 range, Index cond n2 > 100 ms
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.42..9.55 rows=1 width=28) (actual time=86.857..86.857 rows=0 loops=1)
   Join Filter: (test.n1 = ids.n1)
   ->  Index Scan using ind_test on test  (cost=0.42..8.44 rows=1 width=28) (actual time=86.856..86.856 rows=0 loops=1)
         Index Cond: (n2 = 1002)
   ->  Seq Scan on ids  (cost=0.00..1.05 rows=5 width=4) (never executed)
 Planning time: 0.750 ms
 Execution time: 86.885 ms
(7 rows)

Time: 87.955 ms

# select version();
                                                                   version                                                                   
---------------------------------------------------------------------------------------------------------------------------------------------
 PostgreSQL 10.5 (Ubuntu 10.5-1.pgdg16.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609, 64-bit
(1 row)

Time: 2.372 ms

As seen in the explain results, when I search for non-existent values of n2, the plan changes on Index condition used, giving poor plans. None of this plan differences appear if the index is btree. It seems something gist related, and I need to use gist due to PostGIS functions.

A workaround I'm using is creating an additional index for the problematic queries, but they are causing I/O and storage overhead, due to the huge amount of data. I've tried two single column indexes, but the performance penalty was too high compared to the multi-column.

Any toughts?

Answer 1

Sounds like a problem in cost estimator for gist, assuming that a constraint on a lower-order column is worth the same as one on the first column.

https://www.postgresql-archive.org/BUG-15408-Postgresql-bad-planning-with-multicolumn-gist-and-search-with-empty-results-td6047700.html