pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Robert Haas <robertmhaas@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Cédric Villemain <cedric.villemain.debian@gmail.com>
Cc: panam <panam@gmx.net>
Cc: PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: [PERFORM] Hash Anti Join performance degradation
Date: Wed, 1 Jun 2011 16:31:34 -0400
Message-ID: <BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com> (raw)
In-Reply-To: <24247.1306959956@sss.pgh.pa.us>
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>

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?

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company



view thread (35+ messages)  latest in thread

Message-ID: <BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com>
Permalink:  ../BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com/
Also on:    postgresql.org/message-id/BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com

 · 

reply
Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: robertmhaas@gmail.com, tgl@sss.pgh.pa.us, cedric.villemain.debian@gmail.com, panam@gmx.net, pgsql-hackers@postgresql.org
  Subject: Re: [PERFORM] Hash Anti Join performance degradation
  In-Reply-To: <BANLkTim=Tp55eM1Ch6VMtkHT5Tr=Xvnq5g@mail.gmail.com>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox