To: PostgreSQL-development <pgsql-hackers@postgresql.org>
From: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
Subject: ERROR: left and right pathkeys do not match in mergejoin
Message-ID: <5dad9160-4632-0e47-e120-8e2082000c01@postgrespro.ru>
Date: Thu, 22 Feb 2018 00:04:45 +0300
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.6.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: en-US
Precedence: bulk

Hi hackers,

I found a bug related to the planning of merge joins. The steps to 
reproduce are as follows:
```
CREATE TABLE J1_TBL (
     i integer,
     j integer,
     t text
);
CREATE TABLE J2_TBL (
     i integer,
     k integer
);
set enable_hashjoin to off;
explain select * from j1_tbl full join (select * from j2_tbl order by 
j2_tbl.i desc, j2_tbl.k) j2_tbl on j1_tbl.i = j2_tbl.i and j1_tbl.i = 
j2_tbl.k;

ERROR:  left and right pathkeys do not match in mergejoin
```

It can be reproduced on the latest 9.6, 10 and devel versions. 
Basically, j2_tbl is used as the outer relation in merge join. We try to 
use the existing order of j2_tbl, that is, 'i2 desc' and 'k asc'. As a 
result, there is no order for i1 that would allow it to be merge-joined 
to both i2 and k. The corresponding code path begins in 
`generate_mergejoin_pathkeys()`, when it is first called by 
`match_unsorted_outer()`. `find_mergeclauses_for_pathkeys()` selects 
both mergeclauses for the given outer pathkeys, and then 
`make_inner_pathkeys_for_merge()` generates inner pathkey for the first 
mergeclause. Inner pathkey for the second mergeclause is skipped as 
redundant. It looks suspicious already, because this new pathkey has 
different direction and is more like conflicting than redundant. 
Finally, `create_mergejoin_plan()` detects that the inner pathkey 
doesn't match the second mergeclause and throws the error.

I found this while working on the inequality merge join patch. I don't 
know yet how to fix this, so any help is welcome.

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