When does PostgreSQL collapse subqueries to join?

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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-when-not 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@xxxxxxxxxxxx
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@xxxxxxxxxxxxxx)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance





[Postgresql General]     [Postgresql PHP]     [PHP Users]     [PHP Home]     [PHP on Windows]     [Kernel Newbies]     [PHP Classes]     [PHP Books]     [PHP Databases]     [Yosemite]

  Powered by Linux