Keep PostgreSQL from sometimes choosing a bad query plan
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:
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 4:
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.