Date: Sun, 28 Sep 2003 12:03:43 -0700 (PDT)
From: Stephan Szabo <sszabo@megazone.bigpanda.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Christopher Kings-Lynne <chriskl@familyhealth.com.au>,
	Bruce Momjian <pgman@candle.pha.pa.us>,
	Peter Childs <Blue.Dragon@blueyonder.co.uk>,
	PostgreSQL-development <pgsql-hackers@postgresql.org>
Subject: Re: ADD FOREIGN KEY (was Re: [GENERAL] 7.4Beta) 
In-Reply-To: <10377.1064775363@sss.pgh.pa.us>
Message-ID: <20030928115726.K74070@megazone.bigpanda.com>
References: <20030815073837.R19338-100000@megazone.bigpanda.com>
	<1718.1064705858@sss.pgh.pa.us>
	<20030928111850.B73144@megazone.bigpanda.com>
	<10377.1064775363@sss.pgh.pa.us>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII

On Sun, 28 Sep 2003, Tom Lane wrote:

> Stephan Szabo <sszabo@megazone.bigpanda.com> writes:
> > On Sat, 27 Sep 2003, Tom Lane wrote:
> >> I thought of what seems to be a better design for the check query: use
> >> a LEFT JOIN and check for NULL in the righthand joined column.
>
> > Hmm, my initial testing showed that it really was a little slower
> > than a more complicated one with NOT EXISTS so I'd abandoned it. How does
> > it fare for you compared to:
> > select f1, f2 from fk where not exists (select 1 from pk where pk.f1=fk.f1
> > and pk.f2=pk.f2) where fk.f1 is not null and fk.f2 is not null;
>
> Were you testing against 7.3 or 7.4?  On what kinds of tables?

7.4 with tables of 1-2 integer key columns with 10k-1m pk rows of
sequential data (in the 2 key case it was value and #rows-value iirc) and
1m-20m fk rows of randomly generated valid data.  But it wasn't any sort
of amazingly detailed test and those aren't huge tables, but I don't
exactly have a huge machine.  I can go back through, do more tests and
report back.

> In 7.4 I think that the JOIN would yield as good or better a plan.  The
> best possible plan for the NOT EXISTS query is effectively a nestloop
> with inner indexscan, which is great if the FK table is small and the
> PK table is large, but it sucks otherwise.  The planner should choose a
> plan of this form for the LEFT JOIN given that combination of table
> sizes, and so there shouldn't be any great difference in runtime in that
> case.  But in other combinations, such as large FK and small PK, other
> plan types will beat the pants off nestloop.

That's what I was expecting too.  I expected it to basically go, NOT IN,
LEFT JOIN, NOT EXISTS in speed (at least when the hashing stuff
happened for in given the not in enhancements), but didn't actually see
that.

> > I've actually got code (that no longer cleanly applies, but...) that uses
> > the single query version with NOT EXISTS (which could be easily changed to
> > either of the other forms) and was planning to put it together for a patch
> > when 7.5 devel started because I figured it wasn't precisely a bug and
> > wouldn't get accepted for 7.4.
>
> Well, Bruce has this on his open-items list, so I figure we have a green
> light to do something for 7.4 if we can work out what to do.

I must have missed that.  I'd have mentioned it earlier then.