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 

Answer 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.