Keep PostgreSQL from sometimes choosing a bad query plan

Question

I have a strange problem with PostgreSQL performance for a query, using PostgreSQL 8.4.9. This query is selecting a set of points within a 3D volume, using a LEFT OUTER JOIN to add a related ID column where that related ID exists. Small changes in the x range can cause PostgreSQL to choose a different query plan, which takes the execution time from 0.01 seconds to 50 seconds. This is the query in question:

SELECT treenode.id AS id,
       treenode.parent_id AS parentid,
       (treenode.location).x AS x,
       (treenode.location).y AS y,
       (treenode.location).z AS z,
       treenode.confidence AS confidence,
       treenode.user_id AS user_id,
       treenode.radius AS radius,
       ((treenode.location).z - 50) AS z_diff,
       treenode_class_instance.class_instance_id AS skeleton_id
  FROM treenode LEFT OUTER JOIN
         (treenode_class_instance INNER JOIN
          class_instance ON treenode_class_instance.class_instance_id
                                                  = class_instance.id
                            AND class_instance.class_id = 7828307)
       ON (treenode_class_instance.treenode_id = treenode.id
           AND treenode_class_instance.relation_id = 7828321)
  WHERE treenode.project_id = 4
    AND (treenode.location).x >= 8000
    AND (treenode.location).x <= (8000 + 4736)
    AND (treenode.location).y >= 22244
    AND (treenode.location).y <= (22244 + 3248)
    AND (treenode.location).z >= 0
    AND (treenode.location).z <= 100
  ORDER BY parentid DESC, id, z_diff
  LIMIT 400;

That query takes nearly a minute, and, if I add EXPLAIN to the front of that query, seems to be using the following query plan:

 Limit  (cost=56185.16..56185.17 rows=1 width=89)
   ->  Sort  (cost=56185.16..56185.17 rows=1 width=89)
         Sort Key: treenode.parent_id, treenode.id, (((treenode.location).z - 50::double precision))
         ->  Nested Loop Left Join  (cost=6715.16..56185.15 rows=1 width=89)
               Join Filter: (treenode_class_instance.treenode_id = treenode.id)
               ->  Bitmap Heap Scan on treenode  (cost=148.55..184.16 rows=1 width=81)
                     Recheck Cond: (((location).x >= 8000::double precision) AND ((location).x <= 12736::double precision) AND ((location).z >= 0::double precision) AND ((location).z <= 100::double precision))
                     Filter: (((location).y >= 22244::double precision) AND ((location).y <= 25492::double precision) AND (project_id = 4))
                     ->  BitmapAnd  (cost=148.55..148.55 rows=9 width=0)
                           ->  Bitmap Index Scan on location_x_index  (cost=0.00..67.38 rows=2700 width=0)
                                 Index Cond: (((location).x >= 8000::double precision) AND ((location).x <= 12736::double precision))
                           ->  Bitmap Index Scan on location_z_index  (cost=0.00..80.91 rows=3253 width=0)
                                 Index Cond: (((location).z >= 0::double precision) AND ((location).z <= 100::double precision))
               ->  Hash Join  (cost=6566.61..53361.69 rows=211144 width=16)
                     Hash Cond: (treenode_class_instance.class_instance_id = class_instance.id)
                     ->  Seq Scan on treenode_class_instance  (cost=0.00..25323.79 rows=969285 width=16)
                           Filter: (relation_id = 7828321)
                     ->  Hash  (cost=5723.54..5723.54 rows=51366 width=8)
                           ->  Seq Scan on class_instance  (cost=0.00..5723.54 rows=51366 width=8)
                                 Filter: (class_id = 7828307)
(20 rows)

However, if I replace the 8000 in the x range condition with 10644, the query is performed in a fraction of a second and uses this query plan:

 Limit  (cost=58378.94..58378.95 rows=2 width=89)
   ->  Sort  (cost=58378.94..58378.95 rows=2 width=89)
         Sort Key: treenode.parent_id, treenode.id, (((treenode.location).z - 50::double precision))
         ->  Hash Left Join  (cost=57263.11..58378.93 rows=2 width=89)
               Hash Cond: (treenode.id = treenode_class_instance.treenode_id)
               ->  Bitmap Heap Scan on treenode  (cost=231.12..313.44 rows=2 width=81)
                     Recheck Cond: (((location).z >= 0::double precision) AND ((location).z <= 100::double precision) AND ((location).x >= 10644::double precision) AND ((location).x <= 15380::double precision))
                     Filter: (((location).y >= 22244::double precision) AND ((location).y <= 25492::double precision) AND (project_id = 4))
                     ->  BitmapAnd  (cost=231.12..231.12 rows=21 width=0)
                           ->  Bitmap Index Scan on location_z_index  (cost=0.00..80.91 rows=3253 width=0)
                                 Index Cond: (((location).z >= 0::double precision) AND ((location).z <= 100::double precision))
                           ->  Bitmap Index Scan on location_x_index  (cost=0.00..149.95 rows=6157 width=0)
                                 Index Cond: (((location).x >= 10644::double precision) AND ((location).x <= 15380::double precision))
               ->  Hash  (cost=53361.69..53361.69 rows=211144 width=16)
                     ->  Hash Join  (cost=6566.61..53361.69 rows=211144 width=16)
                           Hash Cond: (treenode_class_instance.class_instance_id = class_instance.id)
                           ->  Seq Scan on treenode_class_instance  (cost=0.00..25323.79 rows=969285 width=16)
                                 Filter: (relation_id = 7828321)
                           ->  Hash  (cost=5723.54..5723.54 rows=51366 width=8)
                                 ->  Seq Scan on class_instance  (cost=0.00..5723.54 rows=51366 width=8)
                                       Filter: (class_id = 7828307)
(21 rows)

I'm far from an expert in parsing these query plans, but the clear difference seems to be that with one x range it uses a Hash Left Join for the LEFT OUTER JOIN (which is very fast), while with the other range it uses a Nested Loop Left Join (which seems to be very slow). In both cases the queries return about 90 rows. If I do SET ENABLE_NESTLOOP TO FALSE before the slow version of the query, it goes very fast, but I understand that using that setting in general is a bad idea.

Can I, for example, create a particular index in order to make it more likely that the query planner will choose the clearly more efficient strategy? Could anyone suggest why PostgreSQL's query planner should be choosing such a poor strategy for one of these queries? Below I have included details of the schema that may be helpful.

---

The treenode table has 900,000 rows, and is defined as follows:

                                     Table "public.treenode"
    Column     |           Type           |                      Modifiers                       
---------------+--------------------------+------------------------------------------------------
 id            | bigint                   | not null default nextval('concept_id_seq'::regclass)
 user_id       | bigint                   | not null
 creation_time | timestamp with time zone | not null default now()
 edition_time  | timestamp with time zone | not null default now()
 project_id    | bigint                   | not null
 location      | double3d                 | not null
 parent_id     | bigint                   | 
 radius        | double precision         | not null default 0
 confidence    | integer                  | not null default 5
Indexes:
    "treenode_pkey" PRIMARY KEY, btree (id)
    "treenode_id_key" UNIQUE, btree (id)
    "location_x_index" btree (((location).x))
    "location_y_index" btree (((location).y))
    "location_z_index" btree (((location).z))
Foreign-key constraints:
    "treenode_parent_id_fkey" FOREIGN KEY (parent_id) REFERENCES treenode(id)
Referenced by:
    TABLE "treenode_class_instance" CONSTRAINT "treenode_class_instance_treenode_id_fkey" FOREIGN KEY (treenode_id) REFERENCES treenode(id) ON DELETE CASCADE
    TABLE "treenode" CONSTRAINT "treenode_parent_id_fkey" FOREIGN KEY (parent_id) REFERENCES treenode(id)
Triggers:
    on_edit_treenode BEFORE UPDATE ON treenode FOR EACH ROW EXECUTE PROCEDURE on_edit()
Inherits: location

The double3d composite type is defined as follows:

Composite type "public.double3d"
 Column |       Type       
--------+------------------
 x      | double precision
 y      | double precision
 z      | double precision

The other two tables involved in the join are treenode_class_instance:

                               Table "public.treenode_class_instance"
      Column       |           Type           |                      Modifiers                       
-------------------+--------------------------+------------------------------------------------------
 id                | bigint                   | not null default nextval('concept_id_seq'::regclass)
 user_id           | bigint                   | not null
 creation_time     | timestamp with time zone | not null default now()
 edition_time      | timestamp with time zone | not null default now()
 project_id        | bigint                   | not null
 relation_id       | bigint                   | not null
 treenode_id       | bigint                   | not null
 class_instance_id | bigint                   | not null
Indexes:
    "treenode_class_instance_pkey" PRIMARY KEY, btree (id)
    "treenode_class_instance_id_key" UNIQUE, btree (id)
    "idx_class_instance_id" btree (class_instance_id)
Foreign-key constraints:
    "treenode_class_instance_class_instance_id_fkey" FOREIGN KEY (class_instance_id) REFERENCES class_instance(id) ON DELETE CASCADE
    "treenode_class_instance_relation_id_fkey" FOREIGN KEY (relation_id) REFERENCES relation(id)
    "treenode_class_instance_treenode_id_fkey" FOREIGN KEY (treenode_id) REFERENCES treenode(id) ON DELETE CASCADE
    "treenode_class_instance_user_id_fkey" FOREIGN KEY (user_id) REFERENCES "user"(id)
Triggers:
    on_edit_treenode_class_instance BEFORE UPDATE ON treenode_class_instance FOR EACH ROW EXECUTE PROCEDURE on_edit()
Inherits: relation_instance

... and class_instance:

                                  Table "public.class_instance"
    Column     |           Type           |                      Modifiers                       
---------------+--------------------------+------------------------------------------------------
 id            | bigint                   | not null default nextval('concept_id_seq'::regclass)
 user_id       | bigint                   | not null
 creation_time | timestamp with time zone | not null default now()
 edition_time  | timestamp with time zone | not null default now()
 project_id    | bigint                   | not null
 class_id      | bigint                   | not null
 name          | character varying(255)   | not null
Indexes:
    "class_instance_pkey" PRIMARY KEY, btree (id)
    "class_instance_id_key" UNIQUE, btree (id)
Foreign-key constraints:
    "class_instance_class_id_fkey" FOREIGN KEY (class_id) REFERENCES class(id)
    "class_instance_user_id_fkey" FOREIGN KEY (user_id) REFERENCES "user"(id)
Referenced by:
    TABLE "class_instance_class_instance" CONSTRAINT "class_instance_class_instance_class_instance_a_fkey" FOREIGN KEY (class_instance_a) REFERENCES class_instance(id) ON DELETE CASCADE
    TABLE "class_instance_class_instance" CONSTRAINT "class_instance_class_instance_class_instance_b_fkey" FOREIGN KEY (class_instance_b) REFERENCES class_instance(id) ON DELETE CASCADE
    TABLE "connector_class_instance" CONSTRAINT "connector_class_instance_class_instance_id_fkey" FOREIGN KEY (class_instance_id) REFERENCES class_instance(id)
    TABLE "treenode_class_instance" CONSTRAINT "treenode_class_instance_class_instance_id_fkey" FOREIGN KEY (class_instance_id) REFERENCES class_instance(id) ON DELETE CASCADE
Triggers:
    on_edit_class_instance BEFORE UPDATE ON class_instance FOR EACH ROW EXECUTE PROCEDURE on_edit()
Inherits: concept

Solution 1

If the query planner makes bad decisions it's mostly one of two things:

1. The statistics are inaccurate.

Do you run ANALYZE enough? Also popular in it's combined form VACUUM ANALYZE. If autovacuum is on (which is the default in modern-day Postgres), ANALYZE is run automatically. But consider:

• Are regular VACUUM ANALYZE still recommended under 9.1?

^{(Top two answers still apply for Postgres 12.)}

If your table is big and data distribution is irregular, raising the default_statistics_target may help. Or rather, just set the statistics target for relevant columns (those in WHERE or JOIN clauses of your queries, basically):

ALTER TABLE ... ALTER COLUMN ... SET STATISTICS 400;  -- calibrate number

The target can be set in the range 0 to 10000;

Run ANALYZE again after that (on relevant tables).

2. The cost settings for planner estimates are off.

Read the chapter Planner Cost Constants in the manual.

Look at the chapters default_statistics_target and random_page_cost on this generally helpful PostgreSQL Wiki page.

There are many other possible reasons, but these are the most common ones by far.

Solution 2

I'm skeptical that this has anything to do with bad statistics unless you consider the combination of database statistics and your custom data type.

My guess is that PostgreSQL is picking a nested loop join because it looks at the predicates (treenode.location).x >= 8000 AND (treenode.location).x <= (8000 + 4736) and does something funky in the arithmetic of your comparison. A nested loop is typically going to be used when you have a small amount of data in the inner side of the join.

But, once you switch the constant to 10736 you get a different plan. It's always possible that the plan is of sufficiently complexity that the Genetic Query Optimization (GEQO) is kicking in and you're seeing the side effects of non-deterministic plan building. There are enough discrepancies in the order of evaluation in the queries to make me think that's what's going on.

One option would be to examine using a parameterized/prepared statement for this instead of using ad hoc code. Since you're working in a 3-dimensional space, you might also want to considering using PostGIS. While it might be overkill, it may also be able to provide you with the performance that you need to get these queries running properly.

While forcing planner behavior isn't the best choice, sometimes we do end up making better decisions than the software.

Solution 3

I am not positive it is the source of your problem but it looks like there were some changes made in the postgres query planner between versions 8.4.8 and 8.4.9. You could try using an older version and see if it makes a difference.

http://postgresql.1045698.n5.nabble.com/BUG-6275-Horrible-performance-regression-td4944891.html

Don't forget to reanalyze your tables if you change the version.

Solution 4

What Erwin said about the statistics. Also:

ORDER BY parentid DESC, id, z_diff

Sorting on

parentid DESC, id, z

might give the optimiser a bit more room to shuffle. (I don't think it will matter much since it is the last term, and the sort is not that expensive, but you could give it a try)

Solution 5

+1 for tuning statistics target & doing ANALYZE. And for PostGIS (for OP).

But also, not quite related to the original question, but still, if anyone gets here looking for how to deal, in general, with inaccurate planner's row count estimates in complex queries, leading to undesired plans. An option might be to wrap a part of the initial query into a function and to set its ROWS option to something more or less expected. I've never done that but should work apparently.

Also there are row estimation directives in pg_hint_plan. I would not advice planner hinting in general, but adjusting rows estimate is a softer option.

And finally, to enforce a nested loop scan, sometimes one might do a LATERAL JOIN with LIMIT N or just OFFSET 0 inside the subquery. That will give you what you want. But note it's a very rough trick. At some point it WILL lead to bad performance IF the conditions change - because of table growth or just a different data distribution. Still this might be a good option just to urgently get some relief for a legacy system.

View more solutions