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 "
