Subject: Non-trivial condition is only propagated to one side of JOIN

From: Tobias Hoffmann <[email-masked]>
Date: Sun, 25 Aug 2024 17:10:26 +0200

Hi,

using `PostgreSQL 16.2 (Debian 16.2-1.pgdg120+2) on x86_64-pc-linux-gnu, 
compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit`, I've observed the 
following behavior:

– keep in mind that this example is as simplified as possible, the 
original query involves foreign tables, and the failure to propagate / 
push down the condition results in a query plan that basically tries to 
download the complete foreign table, which is not a feasible execution 
strategy:

Setup:

CREATE TABLE tbl1 (id INTEGER GENERATED ALWAYS AS IDENTITY, site_id 
INTEGER NOT NULL, data TEXT);
CREATE TABLE tbl2 (id INTEGER GENERATED ALWAYS AS IDENTITY, site_id 
INTEGER NOT NULL, data TEXT);
CREATE INDEX ON tbl1 (site_id);
CREATE INDEX ON tbl2 (site_id);

Working queries:

SELECT * FROM tbl1 WHERE tbl1.site_id = 1;  -- "trivial condition"
SELECT * FROM tbl2 WHERE tbl2.site_id = 1;
SELECT * FROM tbl1 WHERE tbl1.site_id = 1 OR tbl1.site_id IS NULL;  -- 
"non-trivial condition"
SELECT * FROM tbl2 WHERE tbl2.site_id = 1 OR tbl2.site_id IS NULL;

1) Exemplary Query Plan:

# EXPLAIN SELECT * FROM tbl2 WHERE tbl2.site_id = 1 OR tbl2.site_id IS NULL;

                                      QUERY PLAN
-------------------------------------------------------------------------------------
  Bitmap Heap Scan on tbl2  (cost=8.40..19.08 rows=12 width=40)
    Recheck Cond: ((site_id = 1) OR (site_id IS NULL))
    ->  BitmapOr  (cost=8.40..8.40 rows=12 width=0)
          ->  Bitmap Index Scan on tbl2_site_id_idx (cost=0.00..4.20 
rows=6 width=0)
                Index Cond: (site_id = 1)
          ->  Bitmap Index Scan on tbl2_site_id_idx (cost=0.00..4.20 
rows=6 width=0)
                Index Cond: (site_id IS NULL)
(7 rows)

The key takeaway is, that the index can be used, because the condition 
is propagated deep enough.

2) Still working example:

# EXPLAIN SELECT * FROM tbl1 LEFT JOIN tbl2 ON tbl2.site_id = 
tbl1.site_id WHERE tbl1.site_id = 1;

                                         QUERY PLAN
-------------------------------------------------------------------------------------------
  Nested Loop Left Join  (cost=8.40..27.80 rows=36 width=80)
    ->  Bitmap Heap Scan on tbl1  (cost=4.20..13.67 rows=6 width=40)
          Recheck Cond: (site_id = 1)
          ->  Bitmap Index Scan on tbl1_site_id_idx (cost=0.00..4.20 
rows=6 width=0)
                Index Cond: (site_id = 1)
    ->  Materialize  (cost=4.20..13.70 rows=6 width=40)
          ->  Bitmap Heap Scan on tbl2  (cost=4.20..13.67 rows=6 width=40)
                Recheck Cond: (site_id = 1)
                ->  Bitmap Index Scan on tbl2_site_id_idx 
(cost=0.00..4.20 rows=6 width=0)
                      Index Cond: (site_id = 1)
(10 rows)

The condition is propagated into BOTH branches of the join. The join 
could also be an INNER join and might also be realized as a Merge Join 
or Hash Join: they all behave the same.

3) Problematic example:

# EXPLAIN SELECT * FROM tbl1 JOIN tbl2 ON tbl2.site_id = tbl1.site_id 
WHERE tbl1.site_id = 1 OR tbl1.site_id IS NULL;

                                            QUERY PLAN
-------------------------------------------------------------------------------------------------
  Hash Join  (cost=19.23..46.45 rows=72 width=80)
    Hash Cond: (tbl2.site_id = tbl1.site_id)
    ->  Seq Scan on tbl2  (cost=0.00..22.00 rows=1200 width=40)
    ->  Hash  (cost=19.08..19.08 rows=12 width=40)
          ->  Bitmap Heap Scan on tbl1  (cost=8.40..19.08 rows=12 width=40)
                Recheck Cond: ((site_id = 1) OR (site_id IS NULL))
                ->  BitmapOr  (cost=8.40..8.40 rows=12 width=0)
                      ->  Bitmap Index Scan on tbl1_site_id_idx 
(cost=0.00..4.20 rows=6 width=0)
                            Index Cond: (site_id = 1)
                      ->  Bitmap Index Scan on tbl1_site_id_idx 
(cost=0.00..4.20 rows=6 width=0)
                            Index Cond: (site_id IS NULL)
(11 rows)

Now, a full seq scan used for tbl2, the condition is only pushed down on 
ONE side of the JOIN!
(with `WHERE tbl2.site_id = 1 OR tbl2.site_id IS NULL`, the Seq Scan 
would have been on tbl1... [not so easily demostrated w/ LEFT JOINs]).
Also, `ON tbl1.site_id IS NOT DISTINCT FROM tbl2.site_id` does not help,

The weird thing is: The subqueries on both sides of the join are 
perfectly capable of accepting/using the "non-trivial" condition, as 
demonstrated in 1), and JOINs are generally able to propagate conditions 
to both sides, as demonstrated in 2).

Is there a magic knob to force postgres to do the right thing, or is 
this basically a bug in the query planner?

   Tobias

---

From: "David G. Johnston" <[email-masked]>
Date: Sun, 25 Aug 2024 08:35:24 -0700

> WHERE tbl1.site_id = 1 OR tbl1.site_id IS NULL;

The “is null” predicate in this query is doing nothing as your next comment
alludes to; you will produce no rows out of the join with a null site_id
due to the use of the equals operator in the join.

> Also, `ON tbl1.site_id IS NOT DISTINCT FROM tbl2.site_id` does not help,

Others may correct me but I’m guessing that indeed the optimizer has a gap
here that could be filled in, it’s just it feels like adding code to deal
with broken queries so isn’t overly motivated to work on. Joining using
distinct instead of equality is uncommon, since nearly all models join
primary keys to foreign keys and both of those are almost always non-null.

David J.

---

From: Tobias Hoffmann <[email-masked]>
Date: Sun, 25 Aug 2024 19:04:32 +0200

On 25/08/2024 17:35, David G. Johnston wrote:
> On Sunday, August 25, 2024, Tobias Hoffmann 
> <[email-masked]> wrote:
>
>
>     3) Problematic example:
>
>     # EXPLAIN SELECT * FROM tbl1 JOIN tbl2 ON tbl2.site_id =
>     tbl1.site_id WHERE tbl1.site_id = 1 OR tbl1.site_id IS NULL; 
>
>
> The “is null” predicate in this query is doing nothing as your next 
> comment alludes to; you will produce no rows out of the join with a 
> null site_id due to the use of the equals operator in the join.

Well, that's why I said: "keep in mind that this example is as 
simplified as possible"...
Even though `tbl1.site_id = 1` is – in this case – completely equivalent 
to `tbl1.site_id = 1 OR tbl1.site_id IS NULL` – the first one is 
completely pushed down, but the second is not.

A more complete example might look more like this:

CREATE VIEW "subview1" AS
   SELECT tbl1.site_id, ... JOIN ... ON tbl1.site_id = tbl2.site_id 
WHERE ...;

CREATE VIEW "view1" AS
   SELECT site_id, ... FROM subview1  -- maybe even: WHERE site_id IS 
NOT NULL
   UNION ALL
   SELECT null, ...;

SELECT * FROM view1 WHERE (site_id = 1 OR site_id IS NULL);

The reason, why the outer query would have a more complicated condition 
might have nothing to do with the subquery containing the JOIN.
(This is also not a `UNION ALL` special case: `site_id IS NULL` could 
also be generated by a LEFT JOIN, e.g.)

But not pushing down the condition has the grave impact, that those - 
otherwise working VIEWs (i.e. subview1) become "unfixably" broken, for 
certain WHERE-conditions on the outside.

Another reason why I said `site_id INTEGER NOT NULL` and `IS NOT 
DISTINCT FROM`, is that there might be some mathematical reason I'm not 
yet aware of where the propagation would not be sound, but which would 
not apply for arbitrary site_id [nullable, ...].
My primary goal is to find at least *some* way to get the condition 
pushed further in to avoid the full table scan, and to not have to 
completely rewrite all the VIEWs into a single big query, where I could 
inject the site_id parameter (e.g. "$1") in multiple places as needed...

   Tobias

---

From: Tom Lane <[email-masked]>
Date: Sun, 25 Aug 2024 13:28:13 -0400

> SELECT * FROM view1 WHERE (site_id = 1 OR site_id IS NULL);

For this particular case, you could probably get somewhere by
writing

SELECT * FROM view1 WHERE site_id = 1
UNION ALL
SELECT * FROM view1 WHERE site_id IS NULL;

since the sets of rows satisfying those two WHERE conditions
must be disjoint.  (I recall working on a patch that essentially
tried to do that transformation automatically, but it eventually
failed because things get too messy if the row sets might not
be disjoint.)

			regards, tom lane