To: Robert Haas <robertmhaas@gmail.com>
cc: =?ISO-8859-1?Q?C=E9dric_Villemain?= <cedric.villemain.debian@gmail.com>,
	panam <panam@gmx.net>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: [PERFORM] Hash Anti Join performance degradation 
In-reply-to: <BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com> 
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>
	<BANLkTinwJ69W4i6JXVGqodbzZdTZ+SSzyA@mail.gmail.com>
	<BANLkTi==zbH2kepG3OmR=Nt0ArxMvWgwdA@mail.gmail.com>
	<BANLkTimRjbzjqA13MLtjLf1XCini_UAAQw@mail.gmail.com>
	<BANLkTikDKUF53_MhP-T9y9NM7a8z40djXA@mail.gmail.com>
	<BANLkTinbb35QT_57EozGOnszBWuarBgW1g@mail.gmail.com>
	<7913.1306900062@sss.pgh.pa.us>
	<BANLkTim-DqDC2AbVJ_1t-XAS4NYq2tQYZg@mail.gmail.com>
	<24247.1306959956@sss.pgh.pa.us>
	<BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com>
Comments: In-reply-to Robert Haas <robertmhaas@gmail.com>
	message dated "Wed, 01 Jun 2011 16:31:34 -0400"
Date: Wed, 01 Jun 2011 16:35:16 -0400
Message-ID: <24461.1306960516@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Robert Haas <robertmhaas@gmail.com> writes:
> On Wed, Jun 1, 2011 at 4:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> Because of the way that a bitmap heap scan works, the rows are
>> guaranteed to be loaded into the hash table in physical order, which
>> means (in the fast case) that the row with the largest "id" value gets
>> loaded last.  And because ExecHashTableInsert pushes each row onto the
>> front of its hash chain, that row ends up at the front of the hash
>> chain.  Net result: for all the outer rows that aren't the one with
>> maximum id, we get a joinqual match at the very first entry in the hash
>> chain.  Since it's an antijoin, we then reject that outer row and go
>> on to the next.  The join thus ends up costing us only O(N) time.

> Ah!  Make sense.  If I'm reading your explanation right, this means
> that we could have hit a similar pathological case on a nestloop as
> well, just with a data ordering that is the reverse of what we have
> here?

Yeah.  It's just chance that this particular data set, with this
particular ordering, happens to work well with a nestloop version
of the query.  On average I'd expect nestloop to suck even more,
because of more per-inner-tuple overhead.

			regards, tom lane