From: Sven R. Kunze <srkunze@tbz-pariv.de>
To: pgsql-performance@postgresql.org
Subject: When does PostgreSQL collapse subqueries to join?
Date: Wed, 10 Dec 2014 12:31:14 +0100
Message-ID: <54882F02.3010107@tbz-pariv.de> (raw)
List-Unsubscribe: <mailto:majordomo@postgresql.org?body=unsub%20pgsql-performance>
Hi everybody,
Denis from SO (see his latest comment) advised me to post my question
here:
http://stackoverflow.com/questions/27363263/when-does-postgresql-collapse-subqueries-to-joins-and-wh...
Please also read all the comments as they contain valuable data as well.
What we actually have now is that PostgreSQL collapses subqueries to
joins but a way differently than using "normal joins" by using "Merge
Semi Joins" or "Nested Loop Semi Joins" (btw an explanation of these
would be great here :) ). The queries given in the post are reduced to
the problem at hand and the by-PostgreSQL-optimized version performed
very well (bit slower than "normal joins"). Regarding our actual query
however, the still-different query plan leads to a big performance
issue. We actually need the complete rows of a instead of a.id. I
prepared the query plans for you (please note, that querie are executed
empty file and mem chaches):
################ Perfect Plan ###############
We assume all our queries to be equivalent and therefore want PostgreSQL
to re-plan the others to this one.
explain analyze verbose select * from a where a.id in (select a.id from
a inner join text_b b1 on (a.id=b1.a_id) inner join text_b b2 on
(a.id=b2.a_id) where b1.x='x1' and b1.y='y1' and b2.x='x2' and b2.y='y2'
order by a.date desc limit 20);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=183.30..191.34 rows=1 width=135) (actual
time=812.486..918.561 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
-> HashAggregate (cost=182.87..182.88 rows=1 width=4) (actual
time=804.866..804.884 rows=20 loops=1)
Output: a_1.id
Group Key: a_1.id
-> Limit (cost=182.85..182.86 rows=1 width=8) (actual
time=804.825..804.839 rows=20 loops=1)
Output: a_1.id, a_1.date
-> Sort (cost=182.85..182.86 rows=1 width=8) (actual
time=804.823..804.829 rows=20 loops=1)
Output: a_1.id, a_1.date
Sort Key: a_1.date
Sort Method: top-N heapsort Memory: 25kB
-> Nested Loop (cost=1.57..182.84 rows=1
width=8) (actual time=96.737..803.871 rows=739 loops=1)
Output: a_1.id, a_1.date
-> Merge Join (cost=1.14..178.74 rows=1
width=8) (actual time=64.829..83.489 rows=739 loops=1)
Output: b1.a_id, b2.a_id
Merge Cond: (b1.a_id = b2.a_id)
-> Index Only Scan using text_b_y_x_y
on public.text_b b1 (cost=0.57..163.29 rows=3936 width=4) (actual
time=34.811..47.328 rows=15195 loops=1)
Output: b1.x, b1.y, b1.a_id
Index Cond: ((b1.x = 'x1'::text)
AND (b1.y = 'y1'::text))
Heap Fetches: 0
-> Index Only Scan using text_b_y_x_y
on public.text_b b2 (cost=0.57..5.49 rows=46 width=4) (actual
time=22.123..30.940 rows=1009 loops=1)
Output: b2.x, b2.y, b2.a_id
Index Cond: ((b2.x = 'x2'::text)
AND (b2.y = 'y2'::text))
Heap Fetches: 0
-> Index Only Scan using a_id_date on
public.a a_1 (cost=0.43..4.09 rows=1 width=8) (actual time=0.970..0.973
rows=1 loops=739)
Output: a_1.id, a_1.date
Index Cond: (a_1.id = b1.a_id)
Heap Fetches: 0
-> Index Scan using a_id_date on public.a (cost=0.43..8.45 rows=1
width=135) (actual time=5.677..5.679 rows=1 loops=20)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
Index Cond: (a.id = a_1.id)
Planning time: 331.190 ms
Execution time: 918.694 ms
###################### Not so perfect Plan ##################
Because PostgreSQL does not re-plan the id-only query from SO to the
perfect query, we also see here a performance degradation.
explain analyze verbose select * from a where a.id in (select a.id from
a where a.id in (select text_b.a_id from text_b where text_b.x='x1' and
text_b.y='y1') and a.id in (select text_b.a_id from text_b where
text_b.x='x2' and text_b.y='y2') order by a.date desc limit 20);
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=384.48..392.51 rows=1 width=135) (actual
time=1311.680..1426.135 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
-> HashAggregate (cost=384.04..384.05 rows=1 width=4) (actual
time=1298.447..1298.470 rows=20 loops=1)
Output: a_1.id
Group Key: a_1.id
-> Limit (cost=384.03..384.03 rows=1 width=8) (actual
time=1298.411..1298.426 rows=20 loops=1)
Output: a_1.id, a_1.date
-> Sort (cost=384.03..384.03 rows=1 width=8) (actual
time=1298.409..1298.416 rows=20 loops=1)
Output: a_1.id, a_1.date
Sort Key: a_1.date
Sort Method: top-N heapsort Memory: 25kB
-> Merge Semi Join (cost=1.57..384.02 rows=1
width=8) (actual time=160.186..1297.628 rows=739 loops=1)
Output: a_1.id, a_1.date
Merge Cond: (a_1.id = text_b.a_id)
-> Nested Loop (cost=1.00..210.76 rows=46
width=12) (actual time=80.587..1236.967 rows=1009 loops=1)
Output: a_1.id, a_1.date, text_b_1.a_id
-> Index Only Scan using text_b_y_x_y
on public.text_b text_b_1 (cost=0.57..5.49 rows=46 width=4) (actual
time=51.190..63.400 rows=1009 loops=1)
Output: text_b_1.x, text_b_1.y,
text_b_1.a_id
Index Cond: ((text_b_1.x =
'x2'::text) AND (text_b_1.y = 'y2'::text))
Heap Fetches: 0
-> Index Only Scan using a_id_date on
public.a a_1 (cost=0.43..4.45 rows=1 width=8) (actual time=1.158..1.160
rows=1 loops=1009)
Output: a_1.id, a_1.date
Index Cond: (a_1.id = text_b_1.a_id)
Heap Fetches: 0
-> Index Only Scan using text_b_y_x_y on
public.text_b (cost=0.57..163.29 rows=3936 width=4) (actual
time=36.963..54.396 rows=15194 loops=1)
Output: text_b.x, text_b.y, text_b.a_id
Index Cond: ((text_b.x = 'x1'::text)
AND (text_b.y = 'y1'::text))
Heap Fetches: 0
-> Index Scan using a_id_date on public.a (cost=0.43..8.45 rows=1
width=135) (actual time=6.376..6.378 rows=1 loops=20)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
Index Cond: (a.id = a_1.id)
Planning time: 248.279 ms
Execution time: 1426.337 ms
################### Slow Joins ##########################
Directly querying from the join performs worse.
explain analyze verbose select * from a inner join text_b b1 on
(a.id=b1.a_id) inner join text_b b2 on (a.id=b2.a_id) where b1.x='x1'
and b1.y='y1' and b2.x='x2' and b2.y='y2' order by a.date desc limit 20;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=186.83..186.83 rows=1 width=177) (actual
time=4133.420..4133.434 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,
b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
-> Sort (cost=186.83..186.83 rows=1 width=177) (actual
time=4133.417..4133.423 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,
b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
Sort Key: a.date
Sort Method: top-N heapsort Memory: 34kB
-> Nested Loop (cost=1.57..186.82 rows=1 width=177) (actual
time=109.094..4130.290 rows=739 loops=1)
Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9, b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date
-> Merge Join (cost=1.14..178.74 rows=1 width=42)
(actual time=72.023..94.234 rows=739 loops=1)
Output: b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y
Merge Cond: (b1.a_id = b2.a_id)
-> Index Only Scan using text_b_y_x_y on
public.text_b b1 (cost=0.57..163.29 rows=3936 width=21) (actual
time=36.084..50.308 rows=15195 loops=1)
Output: b1.x, b1.y, b1.a_id
Index Cond: ((b1.x = 'x1'::text) AND (b1.y =
'y1'::text))
Heap Fetches: 0
-> Index Only Scan using text_b_y_x_y on
public.text_b b2 (cost=0.57..5.49 rows=46 width=21) (actual
time=20.227..37.654 rows=1009 loops=1)
Output: b2.x, b2.y, b2.a_id
Index Cond: ((b2.x = 'x2'::text) AND (b2.y =
'y2'::text))
Heap Fetches: 0
-> Index Scan using a_id_date on public.a
(cost=0.43..8.07 rows=1 width=135) (actual time=5.454..5.457 rows=1
loops=739)
Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9
Index Cond: (a.id = b1.a_id)
Planning time: 332.545 ms
Execution time: 4133.574 ms
################### Slow Subqueries ##########################
Directly querying from the subqueries performs even worse.
explain analyze verbose select * from a where a.id in (select
text_b.a_id from text_b where text_b.x='x1' and text_b.y='y1') and a.id
in (select text_b.a_id from text_b where text_b.x='x2' and
text_b.y='y2') order by a.date desc limit 20;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=568.02..568.03 rows=1 width=135) (actual
time=9765.174..9765.190 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
-> Sort (cost=568.02..568.03 rows=1 width=135) (actual
time=9765.173..9765.180 rows=20 loops=1)
Output: a.id, a.date, a.content1, a.content2, a.content3,
a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9
Sort Key: a.date
Sort Method: top-N heapsort Memory: 30kB
-> Merge Semi Join (cost=1.57..568.01 rows=1 width=135)
(actual time=294.909..9762.978 rows=739 loops=1)
Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9
Merge Cond: (a.id = text_b.a_id)
-> Nested Loop (cost=1.00..394.76 rows=46 width=139)
(actual time=94.441..9668.179 rows=1009 loops=1)
Output: a.id, a.date, a.content1, a.content2,
a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,
a.content9, text_b_1.a_id
-> Index Only Scan using text_b_y_x_y on
public.text_b text_b_1 (cost=0.57..5.49 rows=46 width=4) (actual
time=52.588..67.307 rows=1009 loops=1)
Output: text_b_1.x, text_b_1.y, text_b_1.a_id
Index Cond: ((text_b_1.x = 'x2'::text) AND
(text_b_1.y = 'y2'::text))
Heap Fetches: 0
-> Index Scan using a_id_date on public.a
(cost=0.43..8.45 rows=1 width=135) (actual time=9.485..9.511 rows=1
loops=1009)
Output: a.id, a.date, a.content1,
a.content2, a.content3, a.content4, a.content5, a.content6n, a.content7,
a.content8, a.content9
Index Cond: (a.id = text_b_1.a_id)
-> Index Only Scan using text_b_y_x_y on public.text_b
(cost=0.57..163.29 rows=3936 width=4) (actual time=22.705..86.822
rows=15194 loops=1)
Output: text_b.x, text_b.y, text_b.a_id
Index Cond: ((text_b.x = 'x1'::text) AND (text_b.y
= 'y1'::text))
Heap Fetches: 0
Planning time: 267.442 ms
Execution time: 9765.339 m
What needs to be done in order to feed PostgreSQL with the last query
and achieve the performance of the first one?
Best regards,
--
Sven R. Kunze
TBZ-PARIV GmbH, Bernsdorfer Str. 210-212, 09130 Chemnitz
Tel: +49 (0)371 5347916, Fax: +49 (0)371 5347920
e-mail: srkunze@tbz-pariv.de
web: www.tbz-pariv.de
Geschäftsführer: Dr. Reiner Wohlgemuth
Sitz der Gesellschaft: Chemnitz
Registergericht: Chemnitz HRB 8543
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: srkunze@tbz-pariv.de
Subject: Re: When does PostgreSQL collapse subqueries to join?
In-Reply-To: <54882F02.3010107@tbz-pariv.de>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox