Received: from maia.hub.org (maia-2.hub.org [200.46.204.251]) by mail.postgresql.org (Postfix) with ESMTP id E6F5B632DFC for ; Tue, 25 May 2010 17:07:00 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.204.251]) (amavisd-maia, port 10024) with ESMTP id 02693-03 for ; Tue, 25 May 2010 20:06:53 +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 9D2D1632C42 for ; Tue, 25 May 2010 17:06:53 -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 o4PK6nb7028814; Tue, 25 May 2010 16:06:49 -0400 (EDT) To: Scott Marlowe cc: Matthew Wakeling , pgsql-hackers@postgreSQL.org Subject: mergejoin null handling (was Re: [PERFORM] merge join killing performance) In-reply-to: References: <21497.1274287983@sss.pgh.pa.us> Comments: In-reply-to Scott Marlowe message dated "Wed, 19 May 2010 20:07:39 -0600" Date: Tue, 25 May 2010 16:06:49 -0400 Message-ID: <28813.1274818009@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: 201005/1377 X-Sequence-Number: 163040 Scott Marlowe writes: > So, Tom, so you think it's possible that the planner isn't noticing > all those nulls and thinks it'll just take a row or two to get to the > value it needs to join on? I dug through this and have concluded that it's really an oversight in the patch I wrote some years ago in response to this: http://archives.postgresql.org/pgsql-performance/2005-05/msg00219.php That patch taught nodeMergejoin that a row containing a NULL key can't possibly match anything on the other side. However, its response to observing a NULL is just to advance to the next row of that input. What we should do, if the NULL is in the first merge column and the sort order is nulls-high, is realize that every following row in that input must also contain a NULL and so we can just terminate the mergejoin immediately. The original patch works well for cases where there are just a few nulls in one input and the important factor is to not read all the rest of the other input --- but it fails to cover the case where there are many nulls and the important factor is to not read all the rest of the nulls. The problem can be demonstrated if you modify the example given in the above-referenced message so that table t1 contains lots of nulls rather than just a few: explain analyze will show that all of t1 gets read by the mergejoin, and that's not necessary. I'm inclined to think this is a performance bug and should be back-patched, assuming the fix is simple (which I think it is, but haven't coded/tested yet). It'd probably be reasonable to go back to 8.3; before that, sorting nulls high versus nulls low was pretty poorly defined and so there'd be risk of breaking cases that gave the right answers before. Comments? regards, tom lane