Re: [HACKERS] PoC: full merge join on comparison clause

pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  
help / color / mirror / Atom feed

From: Tom Lane <tgl@sss.pgh.pa.us>
To: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
Cc: Ashutosh Bapat <ashutosh.bapat@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Cc: Jeff Davis <pgsql@j-davis.com>
Subject: Re: [HACKERS] PoC: full merge join on comparison clause
Date: Sun, 18 Nov 2018 20:46:40 -0500
Message-ID: <22877.1542592000@sss.pgh.pa.us> (raw)
In-Reply-To: <9de15ac8-10b2-8569-4683-002db9131771@postgrespro.ru>
References: <b31e1a2d-5ed2-cbca-649e-136f1a7c4c31@postgrespro.ru>
	<0e0a0cb9-f51e-f8a6-3829-50c3e38e33f9@postgrespro.ru>
	<CAFjFpRfP0Q_+j_9oZ5Jsi7SwQyrx+BgVfvE=zUeZHuinPPsVdw@mail.gmail.com>
	<715cb811-4538-9967-a2e3-ca85f2711d80@postgrespro.ru>
	<CAB7nPqRddVnHB6uz8oA-VhvfS6c+kq+NdO+ae7E4i1BShQpT5w@mail.gmail.com>
	<636d3f40-be16-78cc-717f-b85e9f1b9362@postgrespro.ru>
	<20180123163126.GK2416@tamriel.snowman.net>
	<CAFjFpRe275NScegUNDZ8D8qBK62vcePMxzVBMH7nhvBbyjx5aw@mail.gmail.com>
	<53625d9e-b608-bd9d-86a2-f560c02aff7f@postgrespro.ru>
	<513df2b9-b068-6cf4-895e-adb3968547e0@postgrespro.ru>
	<8c762bb0-1507-5ac1-b408-b942416416bf@postgrespro.ru>
	<CAFjFpRcgAAy=Tmn=cpf0PaScqaE+c8cYqvqOVYRELxDspA5UKQ@mail.gmail.com>
	<36d18491-579e-e54b-96bb-4cba38c5a544@postgrespro.ru>
	<CAFjFpRdPUCXOe9bcAQWnRBTU1jAtPPa8fMJrn6oAtttBj=HniA@mail.gmail.com>
	<1a4bac9a-640d-31b8-fb6f-cc4bf36abbf9@postgrespro.ru>
	<CAFjFpRfAxa6CEKVA4E0mYXY+R+=2+o7H+Yk5h3PMfdRx5cTYvQ@mail.gmail.com>
	<9de15ac8-10b2-8569-4683-002db913! 1771@postgrespro.ru>

Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> writes:
> [ Inequality-merge-join-v10.patch ]

Just thinking about this patch a bit ... I wonder why you were so quick to
reject the UNION approach at the outset.  This patch is pretty messy, and
it complicates a lot of stuff that is quite fundamental to the planner,
and you still end up that the only functionality gain is now we can handle
full joins whose conditions include a single btree inequality clause.
Nor are we doing that remarkably efficiently ... it's pretty much
impossible to do it efficiently, in fact, since if the inputs have M and N
rows respectively then the output will have something like (M*N)/2 rows.

So it seems to me that if we're going to put sweat into this area at all,
our ambition ought to be "we'll successfully perform a FULL JOIN with any
join clause whatsoever, though it might take O(M*N) time".

Now as far as I can tell, the UNION substitution you proposed is
completely valid, although it'd be better to phrase the second step
as an antijoin.  That is, I believe

select * from t1 full join t2 on (anything)

is exactly equal to

select t1.*, t2.* from t1 left join t2 on (anything)
union all
select t1.*, t2.* from t2 anti join t1 on (anything)

There is one fly in the ointment, which is that we will have to run the
join clause twice, so it can't contain volatile functions --- but the
merge join approach wouldn't handle that case either.

Having to read the inputs twice is not good, but we could put them
into CTEs, which fixes any problems with volatility below the join
and at least alleviates the performance problem.  Since we can't
currently do any meaningful qual pushdown through full joins, the
optimization-fence aspect of a CTE doesn't seem like an issue either.

In short, proceeding like the above when we can't find another plan
type for a full join seems like it fixes a far wider variety of cases.
The possibility that maybe we could do some of those cases a bit faster
isn't sufficiently attractive to me to justify also putting in a
mechanism like this patch proposes.  We only rarely see complaints at
all about can't-do-a-full-join problems, and I do not think this patch
would fix enough of those complaints to be worthwhile.

			regards, tom lane

view thread (29+ messages)  latest in thread

Message-ID: <22877.1542592000@sss.pgh.pa.us>
Permalink:  ../22877.1542592000@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/22877.1542592000@sss.pgh.pa.us

 ·

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-hackers@postgresql.org
  Cc: tgl@sss.pgh.pa.us, a.kuzmenkov@postgrespro.ru, ashutosh.bapat@enterprisedb.com, pgsql@j-davis.com
  Subject: Re: [HACKERS] PoC: full merge join on comparison clause
  In-Reply-To: <22877.1542592000@sss.pgh.pa.us>

* 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