BUG #16889: Suboptimal behavior related to join condition

The following bug has been logged on the website:

Bug reference: 16889
Logged by: XINYU LIU
Email address: liuxy(at)gatech(dot)edu
PostgreSQL version: 12.3
Operating system: Ubuntu 20.04
Description:

Hello,

We have 2 TPC-H queries which fetch the same tuples but have significant
query execution time differences (3.1 times).

We are sharing a pair of TPC-H queries that exhibit this performance
difference:

First query:
SELECT *
FROM (
SELECT *
FROM "partsupp"
WHERE "ps_suppkey" = 752) AS "t37"
INNER JOIN
(
SELECT *
FROM "part"
WHERE "p_partkey" + 77 <= 1
AND "p_brand" LIKE '%% ') AS "t38"
ON "t38"."p_partkey" - 177 < "t37"."ps_suppkey" FETCH next 1 rows
only

Second query:
SELECT *
FROM (
SELECT *
FROM "partsupp"
WHERE "ps_suppkey" = 752) AS "t37"
INNER JOIN
(
SELECT *
FROM "part"
WHERE "p_partkey" + 77 <= 1
AND "p_brand" LIKE '%% ') AS "t38"
ON "t38"."p_partkey" - 177 < 752 FETCH next 1 rows only

Actual Behavior
We executed both queries on the TPC-H benchmark of scale factor 5: the first
query takes 1149 milliseconds, while the second query only takes 373
milliseconds. We think the time difference results from different plans
selected.

Query Execution Plan
First query:
QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.00..0.13 rows=1 width=274) (actual time=1148.944..1148.944
rows=0 loops=1)
-> Nested Loop (cost=0.00..1163556.03 rows=8888880 width=274) (actual
time=1148.943..1148.943 rows=0 loops=1)
Join Filter: ((part.p_partkey - 177) < partsupp.ps_suppkey)
-> Seq Scan on partsupp (cost=0.00..137194.50 rows=80 width=144)
(actual time=0.039..776.700 rows=80 loops=1)
Filter: (ps_suppkey = 752)
Rows Removed by Filter: 3999920
-> Materialize (cost=0.00..46159.67 rows=333333 width=130)
(actual time=4.652..4.652 rows=0 loops=80)
-> Seq Scan on part (cost=0.00..37982.00 rows=333333
width=130) (actual time=372.113..372.113 rows=0 loops=1)
Filter: ((p_brand ~~ '%% '::text) AND ((p_partkey +
77) <= 1))
Rows Removed by Filter: 1000000
Planning Time: 0.291 ms
Execution Time: 1148.998 ms
(12 rows)

Second query:
QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------
Limit (cost=0.43..0.46 rows=1 width=274) (actual time=369.333..369.333
rows=0 loops=1)
-> Nested Loop (cost=0.43..228113.34 rows=8888880 width=274) (actual
time=369.331..369.331 rows=0 loops=1)
-> Seq Scan on part (cost=0.00..42982.00 rows=111111 width=130)
(actual time=369.327..369.327 rows=0 loops=1)
Filter: ((p_brand ~~ '%% '::text) AND ((p_partkey + 77) <=
1) AND ((p_partkey - 177) < 752))
Rows Removed by Filter: 1000000
-> Materialize (cost=0.43..74020.54 rows=80 width=144) (never
executed)
-> Index Scan using partsupp_pkey on partsupp
(cost=0.43..74020.14 rows=80 width=144) (never executed)
Index Cond: (ps_suppkey = 752)
Planning Time: 0.293 ms
Execution Time: 369.406 ms
(10 rows)

Expected Behavior
Since these two queries are semantically equivalent, we were hoping that
PostgreSQL will evaluate them in roughly the same amount of time. It looks
to me that when evaluating the first (slower) query, the query optimizer
does not propagate the information about "ps_suppkey" = 752 to the INNER
JOIN condition.

Test Environment
Ubuntu 20.04 machine "Linux panda 5.4.0-40-generic #44-Ubuntu SMP Tue Jun 23
00:01:04 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux"
PostgreSQL v12.3
Database: TPC-H benchmark (with scale factor 5)
Description about the partsupp table:
tpch5=# \d+ partsupp
Table "public.partsupp"
Column | Type | Collation | Nullable | Default |
Storage | Stats target | Description
---------------+------------------------+-----------+----------+---------+----------+--------------+-------------
ps_partkey | integer | | not null | |
plain | |
ps_suppkey | integer | | not null | |
plain | |
ps_availqty | integer | | not null | |
plain | |
ps_supplycost | numeric(15,2) | | not null | |
main | |
ps_comment | character varying(199) | | not null | |
extended | |
Indexes:
"partsupp_pkey" PRIMARY KEY, btree (ps_partkey, ps_suppkey)
Foreign-key constraints:
"partsupp_fk1" FOREIGN KEY (ps_suppkey) REFERENCES supplier(s_suppkey)
"partsupp_fk2" FOREIGN KEY (ps_partkey) REFERENCES part(p_partkey)
Referenced by:
TABLE "lineitem" CONSTRAINT "lineitem_fk2" FOREIGN KEY (l_partkey,
l_suppkey) REFERENCES partsupp(ps_partkey, ps_suppkey)

Description about the part table:
tpch5=# \d+ part;
Table "public.part"
Column | Type | Collation | Nullable | Default |
Storage | Stats target | Description
---------------+-----------------------+-----------+----------+---------+----------+--------------+-------------
p_partkey | integer | | not null | |
plain | |
p_name | character varying(55) | | not null | |
extended | |
p_mfgr | character(25) | | not null | |
extended | |
p_brand | character(10) | | not null | |
extended | |
p_type | character varying(25) | | not null | |
extended | |
p_size | integer | | not null | |
plain | |
p_container | character(10) | | not null | |
extended | |
p_retailprice | numeric(15,2) | | not null | |
main | |
p_comment | character varying(23) | | not null | |
extended | |
Indexes:
"part_pkey" PRIMARY KEY, btree (p_partkey)
Referenced by:
TABLE "partsupp" CONSTRAINT "partsupp_fk2" FOREIGN KEY (ps_partkey)
REFERENCES part(p_partkey)

Here are the steps for reproducing our observations:

1. Download the dataset from the link:
https://drive.google.com/file/d/13rFa1BNDi4e2RmXBn-yEQkcqt6lsBu1c/view?usp=sharing
2. Set up TPC-H benchmark
tar xzvf tpch5_postgresql.tar.gz
cd tpch5_postgresql
db=tpch5
createdb $db
psql -d $db < dss.ddl
for i in `ls *.tbl`
do
echo $i
name=`echo $i|cut -d'.' -f1`
psql -d $db -c "COPY $name FROM '`pwd`/$i' DELIMITER '|' ENCODING
'LATIN1';"
done
psql -d $db < dss_postgres.ri
3. Execute the queries