Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1XyfUT-00067T-Qi for pgsql-performance@arkaria.postgresql.org; Wed, 10 Dec 2014 11:31:34 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1XyfUS-0006Vn-Q4 for pgsql-performance@arkaria.postgresql.org; Wed, 10 Dec 2014 11:31:32 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1XyfUR-0006Vg-Io for pgsql-performance@postgresql.org; Wed, 10 Dec 2014 11:31:31 +0000 Received: from mout.kundenserver.de ([212.227.17.13]) by magus.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1XyfUI-0008WF-5H for pgsql-performance@postgresql.org; Wed, 10 Dec 2014 11:31:26 +0000 Received: from comserver.tbz-pariv.de ([194.113.71.71]) by mrelayeu.kundenserver.de (mreue104) with ESMTPSA (Nemesis) id 0MNLx3-1Y19Op3jhJ-006vW4 for ; Wed, 10 Dec 2014 12:31:19 +0100 Received: from localhost (localhost [127.0.0.1]) by comserver.tbz-pariv.de (Postfix) with ESMTP id 55F79207AF for ; Wed, 10 Dec 2014 12:31:18 +0100 (CET) X-Virus-Scanned: amavisd-new at tbz-pariv.de Received: from comserver.tbz-pariv.de ([127.0.0.1]) by localhost (comserver.tbz-pariv.de [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ajsBwYmzQFPL for ; Wed, 10 Dec 2014 12:31:14 +0100 (CET) Received: from [172.17.6.169] (apsrkunze.tbz-pariv.lan [172.17.6.169]) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by comserver.tbz-pariv.de (Postfix) with ESMTPSA id F401F20545 for ; Wed, 10 Dec 2014 12:31:13 +0100 (CET) Message-ID: <54882F02.3010107@tbz-pariv.de> Date: Wed, 10 Dec 2014 12:31:14 +0100 From: "Sven R. Kunze" Organization: TBZ-PARIV GmbH User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0 MIME-Version: 1.0 To: pgsql-performance@postgresql.org Subject: When does PostgreSQL collapse subqueries to join? Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: quoted-printable X-Provags-ID: V03:K0:LuayzCRmaPG3JF6ez8O4pZdF807+HRJuqv1OCSJWawv+xtJEt1l Yk4EufT8r3+CS6c415vlSjWiZVCurTAWRPFbVrg/mzA6GIaurnyrUr6+HOpoZ4qMF5t0l1+ ccRZUWSd3ykQeFwNv8OaTJrTIsc2GgKqJZPomRbtYnqVI0YvHv4U/WaJrrU2+RR0CW5UI66 SZjU2CcguV48E7ItqCdMw== X-UI-Out-Filterresults: notjunk:1; X-Pg-Spam-Score: -1.9 (-) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-performance Precedence: bulk Sender: pgsql-performance-owner@postgresql.org Hi everybody, Denis from SO (see his latest comment) advised me to post my question=20 here:=20 http://stackoverflow.com/questions/27363263/when-does-postgresql-collapse-s= ubqueries-to-joins-and-when-not=20 Please also read all the comments as they contain valuable data as well. What we actually have now is that PostgreSQL collapses subqueries to=20 joins but a way differently than using "normal joins" by using "Merge=20 Semi Joins" or "Nested Loop Semi Joins" (btw an explanation of these=20 would be great here :) ). The queries given in the post are reduced to=20 the problem at hand and the by-PostgreSQL-optimized version performed=20 very well (bit slower than "normal joins"). Regarding our actual query=20 however, the still-different query plan leads to a big performance=20 issue. We actually need the complete rows of a instead of a.id. I=20 prepared the query plans for you (please note, that querie are executed=20 empty file and mem chaches): ################ Perfect Plan ############### We assume all our queries to be equivalent and therefore want PostgreSQL=20 to re-plan the others to this one. explain analyze verbose select * from a where a.id in (select a.id from=20 a inner join text_b b1 on (a.id=3Db1.a_id) inner join text_b b2 on=20 (a.id=3Db2.a_id) where b1.x=3D'x1' and b1.y=3D'y1' and b2.x=3D'x2' and b2.y= =3D'y2'=20 order by a.date desc limit 20); QUERY PLAN ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---- Nested Loop (cost=3D183.30..191.34 rows=3D1 width=3D135) (actual=20 time=3D812.486..918.561 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9 -> HashAggregate (cost=3D182.87..182.88 rows=3D1 width=3D4) (actual=20 time=3D804.866..804.884 rows=3D20 loops=3D1) Output: a_1.id Group Key: a_1.id -> Limit (cost=3D182.85..182.86 rows=3D1 width=3D8) (actual=20 time=3D804.825..804.839 rows=3D20 loops=3D1) Output: a_1.id, a_1.date -> Sort (cost=3D182.85..182.86 rows=3D1 width=3D8) (actua= l=20 time=3D804.823..804.829 rows=3D20 loops=3D1) Output: a_1.id, a_1.date Sort Key: a_1.date Sort Method: top-N heapsort Memory: 25kB -> Nested Loop (cost=3D1.57..182.84 rows=3D1=20 width=3D8) (actual time=3D96.737..803.871 rows=3D739 loops=3D1) Output: a_1.id, a_1.date -> Merge Join (cost=3D1.14..178.74 rows=3D1=20 width=3D8) (actual time=3D64.829..83.489 rows=3D739 loops=3D1) Output: b1.a_id, b2.a_id Merge Cond: (b1.a_id =3D b2.a_id) -> Index Only Scan using text_b_y_x_y=20 on public.text_b b1 (cost=3D0.57..163.29 rows=3D3936 width=3D4) (actual=20 time=3D34.811..47.328 rows=3D15195 loops=3D1) Output: b1.x, b1.y, b1.a_id Index Cond: ((b1.x =3D 'x1'::text)= =20 AND (b1.y =3D 'y1'::text)) Heap Fetches: 0 -> Index Only Scan using text_b_y_x_y=20 on public.text_b b2 (cost=3D0.57..5.49 rows=3D46 width=3D4) (actual=20 time=3D22.123..30.940 rows=3D1009 loops=3D1) Output: b2.x, b2.y, b2.a_id Index Cond: ((b2.x =3D 'x2'::text)= =20 AND (b2.y =3D 'y2'::text)) Heap Fetches: 0 -> Index Only Scan using a_id_date on=20 public.a a_1 (cost=3D0.43..4.09 rows=3D1 width=3D8) (actual time=3D0.970..= 0.973=20 rows=3D1 loops=3D739) Output: a_1.id, a_1.date Index Cond: (a_1.id =3D b1.a_id) Heap Fetches: 0 -> Index Scan using a_id_date on public.a (cost=3D0.43..8.45 rows=3D1= =20 width=3D135) (actual time=3D5.677..5.679 rows=3D1 loops=3D20) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9 Index Cond: (a.id =3D 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=20 perfect query, we also see here a performance degradation. explain analyze verbose select * from a where a.id in (select a.id from=20 a where a.id in (select text_b.a_id from text_b where text_b.x=3D'x1' and=20 text_b.y=3D'y1') and a.id in (select text_b.a_id from text_b where=20 text_b.x=3D'x2' and text_b.y=3D'y2') order by a.date desc limit 20); QUERY PLAN ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---- Nested Loop (cost=3D384.48..392.51 rows=3D1 width=3D135) (actual=20 time=3D1311.680..1426.135 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9 -> HashAggregate (cost=3D384.04..384.05 rows=3D1 width=3D4) (actual=20 time=3D1298.447..1298.470 rows=3D20 loops=3D1) Output: a_1.id Group Key: a_1.id -> Limit (cost=3D384.03..384.03 rows=3D1 width=3D8) (actual=20 time=3D1298.411..1298.426 rows=3D20 loops=3D1) Output: a_1.id, a_1.date -> Sort (cost=3D384.03..384.03 rows=3D1 width=3D8) (actua= l=20 time=3D1298.409..1298.416 rows=3D20 loops=3D1) Output: a_1.id, a_1.date Sort Key: a_1.date Sort Method: top-N heapsort Memory: 25kB -> Merge Semi Join (cost=3D1.57..384.02 rows=3D1=20 width=3D8) (actual time=3D160.186..1297.628 rows=3D739 loops=3D1) Output: a_1.id, a_1.date Merge Cond: (a_1.id =3D text_b.a_id) -> Nested Loop (cost=3D1.00..210.76 rows=3D46= =20 width=3D12) (actual time=3D80.587..1236.967 rows=3D1009 loops=3D1) Output: a_1.id, a_1.date, text_b_1.a_id -> Index Only Scan using text_b_y_x_y=20 on public.text_b text_b_1 (cost=3D0.57..5.49 rows=3D46 width=3D4) (actual= =20 time=3D51.190..63.400 rows=3D1009 loops=3D1) Output: text_b_1.x, text_b_1.y,=20 text_b_1.a_id Index Cond: ((text_b_1.x =3D=20 'x2'::text) AND (text_b_1.y =3D 'y2'::text)) Heap Fetches: 0 -> Index Only Scan using a_id_date on=20 public.a a_1 (cost=3D0.43..4.45 rows=3D1 width=3D8) (actual time=3D1.158..= 1.160=20 rows=3D1 loops=3D1009) Output: a_1.id, a_1.date Index Cond: (a_1.id =3D text_b_1.a_= id) Heap Fetches: 0 -> Index Only Scan using text_b_y_x_y on=20 public.text_b (cost=3D0.57..163.29 rows=3D3936 width=3D4) (actual=20 time=3D36.963..54.396 rows=3D15194 loops=3D1) Output: text_b.x, text_b.y, text_b.a_id Index Cond: ((text_b.x =3D 'x1'::text)=20 AND (text_b.y =3D 'y1'::text)) Heap Fetches: 0 -> Index Scan using a_id_date on public.a (cost=3D0.43..8.45 rows=3D1= =20 width=3D135) (actual time=3D6.376..6.378 rows=3D1 loops=3D20) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9 Index Cond: (a.id =3D 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=20 (a.id=3Db1.a_id) inner join text_b b2 on (a.id=3Db2.a_id) where b1.x=3D'x1'= =20 and b1.y=3D'y1' and b2.x=3D'x2' and b2.y=3D'y2' order by a.date desc limit = 20; QUERY PLAN ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= -------------------------------- Limit (cost=3D186.83..186.83 rows=3D1 width=3D177) (actual=20 time=3D4133.420..4133.434 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,=20 b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date -> Sort (cost=3D186.83..186.83 rows=3D1 width=3D177) (actual=20 time=3D4133.417..4133.423 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9,=20 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=3D1.57..186.82 rows=3D1 width=3D177) (actu= al=20 time=3D109.094..4130.290 rows=3D739 loops=3D1) Output: a.id, a.date, a.content1, a.content2,=20 a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,=20 a.content9, b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y, a.date -> Merge Join (cost=3D1.14..178.74 rows=3D1 width=3D42)=20 (actual time=3D72.023..94.234 rows=3D739 loops=3D1) Output: b1.a_id, b1.x, b1.y, b2.a_id, b2.x, b2.y Merge Cond: (b1.a_id =3D b2.a_id) -> Index Only Scan using text_b_y_x_y on=20 public.text_b b1 (cost=3D0.57..163.29 rows=3D3936 width=3D21) (actual=20 time=3D36.084..50.308 rows=3D15195 loops=3D1) Output: b1.x, b1.y, b1.a_id Index Cond: ((b1.x =3D 'x1'::text) AND (b1.y = =3D=20 'y1'::text)) Heap Fetches: 0 -> Index Only Scan using text_b_y_x_y on=20 public.text_b b2 (cost=3D0.57..5.49 rows=3D46 width=3D21) (actual=20 time=3D20.227..37.654 rows=3D1009 loops=3D1) Output: b2.x, b2.y, b2.a_id Index Cond: ((b2.x =3D 'x2'::text) AND (b2.y = =3D=20 'y2'::text)) Heap Fetches: 0 -> Index Scan using a_id_date on public.a=20 (cost=3D0.43..8.07 rows=3D1 width=3D135) (actual time=3D5.454..5.457 rows= =3D1=20 loops=3D739) Output: a.id, a.date, a.content1, a.content2,=20 a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,=20 a.content9 Index Cond: (a.id =3D 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=20 text_b.a_id from text_b where text_b.x=3D'x1' and text_b.y=3D'y1') and a.id= =20 in (select text_b.a_id from text_b where text_b.x=3D'x2' and=20 text_b.y=3D'y2') order by a.date desc limit 20; QUERY PLAN ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= ---------------------------------------------------------------------------= --------------------------------------------- Limit (cost=3D568.02..568.03 rows=3D1 width=3D135) (actual=20 time=3D9765.174..9765.190 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 a.content4, a.content5, a.content6n, a.content7, a.content8, a.content9 -> Sort (cost=3D568.02..568.03 rows=3D1 width=3D135) (actual=20 time=3D9765.173..9765.180 rows=3D20 loops=3D1) Output: a.id, a.date, a.content1, a.content2, a.content3,=20 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=3D1.57..568.01 rows=3D1 width=3D135)=20 (actual time=3D294.909..9762.978 rows=3D739 loops=3D1) Output: a.id, a.date, a.content1, a.content2,=20 a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,=20 a.content9 Merge Cond: (a.id =3D text_b.a_id) -> Nested Loop (cost=3D1.00..394.76 rows=3D46 width=3D139= )=20 (actual time=3D94.441..9668.179 rows=3D1009 loops=3D1) Output: a.id, a.date, a.content1, a.content2,=20 a.content3, a.content4, a.content5, a.content6n, a.content7, a.content8,=20 a.content9, text_b_1.a_id -> Index Only Scan using text_b_y_x_y on=20 public.text_b text_b_1 (cost=3D0.57..5.49 rows=3D46 width=3D4) (actual=20 time=3D52.588..67.307 rows=3D1009 loops=3D1) Output: text_b_1.x, text_b_1.y, text_b_1.a_id Index Cond: ((text_b_1.x =3D 'x2'::text) AND=20 (text_b_1.y =3D 'y2'::text)) Heap Fetches: 0 -> Index Scan using a_id_date on public.a=20 (cost=3D0.43..8.45 rows=3D1 width=3D135) (actual time=3D9.485..9.511 rows= =3D1=20 loops=3D1009) Output: a.id, a.date, a.content1,=20 a.content2, a.content3, a.content4, a.content5, a.content6n, a.content7,=20 a.content8, a.content9 Index Cond: (a.id =3D text_b_1.a_id) -> Index Only Scan using text_b_y_x_y on public.text_b=20= =20 (cost=3D0.57..163.29 rows=3D3936 width=3D4) (actual time=3D22.705..86.822=20 rows=3D15194 loops=3D1) Output: text_b.x, text_b.y, text_b.a_id Index Cond: ((text_b.x =3D 'x1'::text) AND (text_b.y= =20 =3D '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=20 and achieve the performance of the first one? Best regards, --=20 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=C3=A4ftsf=C3=BChrer: Dr. Reiner Wohlgemuth Sitz der Gesellschaft: Chemnitz Registergericht: Chemnitz HRB 8543 --=20 Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-performance