Subject: Re: Removing unneeded self joins
To: David Rowley <david.rowley@2ndquadrant.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
References: <64486b0b-0404-e39e-322d-0801154901f3@postgrespro.ru>
 <8a17cc3d-f933-ba32-6110-f2d8481070e7@postgrespro.ru>
 <CAEepm=19wLyUc4o43j5WnSbYsQPoaErdoOfeXiPP0iB_zRUm_w@mail.gmail.com>
 <2285d5d0-f330-e8b6-9ee5-b2b90e44409b@postgrespro.ru>
 <35fd3789-bde8-f290-9b55-da3d54cd6af5@postgrespro.ru>
 <e34fc4cc-68d0-8ebf-9376-a8089a92ec2d@postgrespro.ru>
 <CAKJS1f8-TuxfYMewFoBicGDtac1dK8RhbYzXgyzgW6Ej5U70sg@mail.gmail.com>
 <23f6cf6d-32ca-faa2-f4ec-da690ba42482@postgrespro.ru>
 <c3ce94ab-1c1d-98ee-c067-f3e3a5444e98@postgrespro.ru>
 <22996.1550795112@sss.pgh.pa.us>
 <2b74af78-3417-167d-ad72-d54ec558d8be@postgrespro.ru>
 <CAKJS1f8VV4YvsC_YSNHVtKfmqTAnrfcDoH21gVgAJNAFmwK6zA@mail.gmail.com>
 <552e481b-2feb-75fd-4e9f-4199bfd1c1f3@postgrespro.ru>
 <CAKJS1f8p-KiEujr12k-oa52JNWWaQUjEjNg+o1MGZk4mHBn_Rg@mail.gmail.com>
 <31c2ee33-5db1-a43c-b964-8e2624020ae9@postgrespro.ru>
 <CAKJS1f_cPDTRBTW4KpuD5fktVjPs2ugg704CJn=OxWXoUv-rDw@mail.gmail.com>
 <CAKJS1f8cJOCGyoxi7a_LG7eu+WKF9+HTff3wp1KKS5gcUg2Qfg@mail.gmail.com>
From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
Message-ID: <89c8a17d-01f8-a03d-7fb8-0a8a070be47c@postgrespro.ru>
Date: Mon, 25 Mar 2019 16:45:02 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.2.1
MIME-Version: 1.0
In-Reply-To: 
 <CAKJS1f8cJOCGyoxi7a_LG7eu+WKF9+HTff3wp1KKS5gcUg2Qfg@mail.gmail.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: en-US
Precedence: bulk

On 3/25/19 07:07, David Rowley wrote:
> You had commented the test with:
>
> -- If index conditions are different for each side, we won't select the same
> -- row on both sides, so the join can't be removed.
>
> but I don't quite understand why we can't remove the join in this
> situation.


My rationale was that we're not exactly removing the join, but replacing 
it with a scan. So it is not enough to just have a single row on each 
side, it must be the same physical row. In this example, before the 
transformation, t1.b is not equal to t2.b, but they become equal 
afterwards. This looks somewhat wrong. On the other hand, if the 
conditions are different, the resulting condition is going to evaluate 
to constant false and we won't get any rows, so maybe it's OK.

This brings me again to the question of what are the conditions for join 
removal. If the formulation with indexes is not general enough, what do 
we use instead? I guess it could be something like this:

1. Given the (btree equality) join and restriction clauses, both sides 
are unique on the same set of columns. That is, if we fix the values of 
these columns, both sides have at most one matching row.

     a. For each of these columns, we have either

         i) a join clause that equates some expression referencing the 
outer column to the same expression referencing the same inner column.

         ii) a clause for each relation that equates the same expression 
referencing the outer and inner column to some other arbitrary 
expression, possibly a different one for each side. This expression may 
be a Const or some expression that references a Var of some third relation.

2. All the resulting columns can be calculated using either side of the 
join. For now, just require that both sides are base relations that 
refer to the same physical relation.

Two points are not clear to me here:

1. We don't handle join clauses to third relations, but can they be 
treated the same way we treat Consts?

2. Can we simplify the join when we don't have any join clauses and only 
have Consts? Or should we have at least one join clause that equates the 
same inner and outer column? Why is one join clause enough?

-- 
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company