Subject: Re: Removing unneeded self joins
To: Heikki Linnakangas <hlinnaka@iki.fi>, David Rowley <dgrowleyml@gmail.com>
Cc: David Steele <david@pgmasters.net>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
References: <64486b0b-0404-e39e-322d-0801154901f3@postgrespro.ru>
 <89c8a17d-01f8-a03d-7fb8-0a8a070be47c@postgrespro.ru>
 <fa5ce779-2200-702f-85ec-780f1769cd66@postgrespro.ru>
 <9b226ea2-bce0-90b2-9909-7964b7f353f7@postgrespro.ru>
 <8556348d-b5fa-728a-e4db-8dcad9d11e4b@postgrespro.ru>
 <CA+hUKGK_gpPm4AN7rV0RUvdFus=V_P_7DEVErRfMdeQt4Zr3vA@mail.gmail.com>
 <9aa6421b-fa8c-b578-6f18-0174c51f0884@postgrespro.ru>
 <bfcdcf79-d726-3986-597e-bbd9b68a67cc@postgrespro.ru>
 <2c08741c-3d58-f517-23de-549d6c15e14e@postgrespro.ru>
 <cd839807-fc9e-9028-a132-a70631a1edbf@postgrespro.ru>
 <f84b7d25-d99c-5dd8-c9cb-64a3731a3e2a@postgrespro.ru>
 <9315b1bc-f134-93aa-ed38-0d6a08719058@postgrespro.ru>
 <031ab7da-c943-cd65-590e-671add024e3f@pgmasters.net>
 <8a427a9a-50cd-51e9-3c1c-2176eceb39b0@postgrespro.ru>
 <CAApHDvpggnFMC4yP-jUO7PKN=fXeErW5bOxisvJ0HvkHQEY=Ww@mail.gmail.com>
 <30b38869-9430-31fb-39e1-c735074b9259@postgrespro.ru>
 <16aa5d06-d8c6-416a-cb71-21663019944e@iki.fi>
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
Organization: Postgres Professional
Message-ID: <b32dda0d-41dc-381f-73f0-4702265c97aa@postgrespro.ru>
Date: Sat, 28 Nov 2020 22:21:17 +0500
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
 Gecko/20100101 Thunderbird/78.5.0
MIME-Version: 1.0
In-Reply-To: <16aa5d06-d8c6-416a-cb71-21663019944e@iki.fi>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

Thank you for the review,

On 27.11.2020 21:49, Heikki Linnakangas wrote:
> On 31/10/2020 11:26, Andrey V. Lepikhov wrote:
>> +            /*
>> +             * Process restrictlist to seperate out the self join 
>> quals from
>> +             * the other quals. e.g x = x goes to selfjoinquals and a 
>> = b to
>> +             * otherjoinquals.
>> +             */
>> +            split_selfjoin_quals(root, restrictlist, &selfjoinquals,
>> +                                 &otherjoinquals);
>> +
>> +            if (list_length(selfjoinquals) == 0)
>> +            {
>> +                /*
>> +                 * Have a chance to remove join if target list 
>> contains vars from
>> +                 * the only one relation.
>> +                 */
> 
> I don't understand the logic here. If 'selfjoinquals' is empty, it means 
> that there is no join qual between the two relations, right? How can we 
> ever remove the join in that case? And how does the target list affect 
> that? Can you give an example query of that?

Maybe it is a problem of variable naming. Following the idea of David 
Rowley, we split quals into two subsets: {x==x} and another, for example 
{x=y}.
First set is an trivial case of self-join: if we have unique index on 
the attribute 'x', then this join is self-join.
Second set is give us a chance: if right side is unique for right side 
of the qual and no vars from right side end up in the target list of the 
join, then this is a self-join case. Example:

CREATE TABLE a(x int, y int);
CREATE UNIQUE INDEX ON a(x);
SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.x;  -- self-join
CREATE UNIQUE INDEX ON a(y);
SELECT a1.* FROM a a1, a a2 WHERE a1.x = a2.y;  -- self-join too

> 
>> --- a/src/test/regress/expected/join.out
>> +++ b/src/test/regress/expected/join.out
>> @@ -4553,11 +4553,13 @@ explain (costs off)
>>  select p.* from
>>    (parent p left join child c on (p.k = c.k)) join parent x on p.k = x.k
>>    where p.k = 1 and p.k = 2;
>> -        QUERY PLAN ---------------------------
>> +                   QUERY PLAN 
>> +------------------------------------------------
>>   Result
>>     One-Time Filter: false
>> -(2 rows)
>> +   ->  Index Scan using parent_pkey on parent x
>> +         Index Cond: (k = 1)
>> +(4 rows)
>>
>>  -- bug 5255: this is not optimizable by join removal
>>  begin;
> 
> That doesn't seem like an improvement...

I investigated this case. It is a planner feature: it simplifies dummy 
joins and dummy scans to different plans. Maybe it can cause some 
discussion, but this example so rare and doesn't make a problem.

> My general impression of this patch is that it's a lot of code to deal 
> with a rare special case. At the beginning of this thread there was 
> discussion on the overhead that this might add to planning queries that 
> don't benefit, but adding a lot of code isn't nice either, even if the 
> performance is acceptable. That's not necessarily a show-stopper, but it 
> does make me much less excited about this. I'm not sure what to suggest 
> to do about that, except a really vague "Can you make is simpler?"

Currently planner reduces useless outer joins and unique semijoins. 
Reduce self join feature continues the development of the planner in the 
same direction. For example, it is needed for ORM software.
Most of the code dedicated to removing unnecessary relation and 
replacing of one oid with another. We are trying to use 
remove_rel_from_query() machinery. Perhaps this will allow us to make 
the code shorter.

-- 
regards,
Andrey Lepikhov
Postgres Professional