pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedWhen does PostgreSQL collapse subqueries to join?
2+ messages / 2 participants
[nested] [flat]
* When does PostgreSQL collapse subqueries to join?
@ 2014-12-10 11:31 Sven R. Kunze <srkunze@tbz-pariv.de>
2014-12-10 15:34 ` Re: When does PostgreSQL collapse subqueries to join? Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 2+ messages in thread
From: Sven R. Kunze @ 2014-12-10 11:31 UTC (permalink / raw)
To: pgsql-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
^ permalink raw reply [nested|flat] 2+ messages in thread
* Re: When does PostgreSQL collapse subqueries to join?
2014-12-10 11:31 When does PostgreSQL collapse subqueries to join? Sven R. Kunze <srkunze@tbz-pariv.de>
@ 2014-12-10 15:34 ` Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 0 replies; 2+ messages in thread
From: Tom Lane @ 2014-12-10 15:34 UTC (permalink / raw)
To: Sven R. Kunze <srkunze@tbz-pariv.de>; +Cc: pgsql-performance
"Sven R. Kunze" <srkunze@tbz-pariv.de> writes:
> ################ 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);
> [ ... other variant cases ... ]
> ################### 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;
> What needs to be done in order to feed PostgreSQL with the last query
> and achieve the performance of the first one?
Postgres will *never* turn the last query into the first one, because
they are not in fact equivalent. Putting the ORDER BY/LIMIT inside the
subquery has entirely different effects than putting it outside. There's
no guarantee at all that the first query returns only 20 rows, nor that
the returned rows are in any particular order.
I'm a bit suspicious of the other aspect of your manual transformation
here too: in general semijoins (IN joins) don't commute with inner joins.
It's possible that it's okay here given the specific forms of the join
clauses, but the planner won't assume that.
regards, tom lane
--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance
^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2014-12-10 15:34 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2014-12-10 11:31 When does PostgreSQL collapse subqueries to join? Sven R. Kunze <srkunze@tbz-pariv.de>
2014-12-10 15:34 ` Tom Lane <tgl@sss.pgh.pa.us>
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