Received: from maia.hub.org (maia-3.hub.org [200.46.204.243]) by mail.postgresql.org (Postfix) with ESMTP id E5D89B6075B for ; Wed, 1 Jun 2011 00:47:53 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.243]) (amavisd-maia, port 10024) with ESMTP id 77137-04 for ; Wed, 1 Jun 2011 03:47:47 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by mail.postgresql.org (Postfix) with ESMTP id E92D7B606AC for ; Wed, 1 Jun 2011 00:47:46 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.2/8.14.2) with ESMTP id p513lh64007915; Tue, 31 May 2011 23:47:43 -0400 (EDT) To: Robert Haas cc: =?ISO-8859-1?Q?C=E9dric_Villemain?= , panam , PostgreSQL-development Subject: Re: [PERFORM] Hash Anti Join performance degradation In-reply-to: References: <1306210464806-4420974.post@n5.nabble.com> <4DDB47BC.8030504@postnewspapers.com.au> <1306247697267-4422247.post@n5.nabble.com> <4DDC6109.7060708@postnewspapers.com.au> <1306341749094-4425890.post@n5.nabble.com> <4DDDBD96.4010809@postnewspapers.com.au> <1306413217406-4428435.post@n5.nabble.com> Comments: In-reply-to Robert Haas message dated "Tue, 31 May 2011 22:58:16 -0400" Date: Tue, 31 May 2011 23:47:42 -0400 Message-ID: <7913.1306900062@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.91 tagged_above=-5 required=5 tests=BAYES_00=-1.9, T_RP_MATCHES_RCVD=-0.01 X-Spam-Level: X-Archive-Number: 201106/4 X-Sequence-Number: 188717 Robert Haas writes: > With respect to the root of the issue (why does the anti-join take so > long?), my first thought was that perhaps the OP was very unlucky and > had a lot of values that hashed to the same bucket. But that doesn't > appear to be the case. Well, yes it is. Notice what the subquery is doing: for each row in "box", it's pulling all matching "box_id"s from message and running a self-join across those rows. The hash join condition is a complete no-op. And some of the box_ids have hundreds of thousands of rows. I'd just write it off as being a particularly stupid way to find the max(), except I'm not sure why deleting just a few thousand rows improves things so much. It looks like it ought to be an O(N^2) situation, so the improvement should be noticeable but not amazing. And if you force it to not use a hashjoin, suddenly things are better. Nestloop should also be O(N^2) in this situation, but seemingly it avoids whatever weird corner case we are hitting here. As Cedric says, the lack of any CHECK_FOR_INTERRUPTS in this loop is also problematic. I'm not sure that right there is an ideal place to put it, but we need one somewhere in the loop. regards, tom lane