[PROPOSAL] Expand OR clauses in joins to UNION ALL paths

On 07.10.26 13:02, Ayoub Kazar wrote:

Attached is a patch that lets the planner rewrite an OR clause that spans
several relations into a UNION ALL with one branch per arm, and use that
plan when it is estimated to be cheaper.

Background

OR clauses that mention more than one relation are awkward for the planner
today. If the OR is the join condition itself (a.x = b.y OR a.x = b.z), it
cannot be a hash or merge join clause, so the only choice left is a nested
loop, usually with a BitmapOr of index scans on the inner side that is run
again for every outer row. If it is a filter on two different tables
(a.f = 1 OR b.g = 2), BitmapOr cannot help either, since it only combines
indexes of one relation, and the OR ends up as a join filter. The
textbook case is a star schema with an OR over conditions on two
dimension tables.

This transformation is extremely useful and in my experience, queries
that can profit from it occur frequently. So +1 for the effort.

Where it is not considered:

- ORs that only reference one relation, the argument is that in this
case, surely a BitmapOr or anything else do the job.
- volatile functions in the jointree, security quals or function/subquery
  RTEs, since the arms are evaluated more than once
- FULL joins, TABLESAMPLE, FOR UPDATE/SHARE, CTEs, set operations,
  recursive queries, well anything other than SELECT ?
- partitioned tables, also inside subqueries. Child RTEs are created inside
  query_planner(), so after arms prune differently their range table
  indexes no longer match the original one, i didn't try to make it work
yet the solution here is maybe to refix pointers back to match root
PlannerInfo for each arm, but this felt too much, i wonder if its worth
it for the benefit it can get for partitioned tables.
- ORs in JOIN ... ON clauses. Only the top level WHERE quals are looked at
  for now.

The transformation is not always beneficial. Here's an example:

SELECT o.*
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'returned' -- very selective: 1k rows
OR c.tier = 'standard'; -- very unselective: 900k of 1M customers

When one condition is very selective a NLJ on the table with the more
selective condition is actually pretty efficient.

Do you unconditionally apply the transformation, or do you have
heuristics to only do it if it likely pays off?

--
David Geier

On 07.10.26 13:02, Ayoub Kazar wrote:

Attached is a patch that lets the planner rewrite an OR clause that spans
several relations into a UNION ALL with one branch per arm, and use that
plan when it is estimated to be cheaper.

Background

OR clauses that mention more than one relation are awkward for the planner
today. If the OR is the join condition itself (a.x = b.y OR a.x = b.z), it
cannot be a hash or merge join clause, so the only choice left is a nested
loop, usually with a BitmapOr of index scans on the inner side that is run
again for every outer row. If it is a filter on two different tables
(a.f = 1 OR b.g = 2), BitmapOr cannot help either, since it only combines
indexes of one relation, and the OR ends up as a join filter. The
textbook case is a star schema with an OR over conditions on two
dimension tables.

This transformation is extremely useful and in my experience, queries
that can profit from it occur frequently. So +1 for the effort.

Where it is not considered:

- ORs that only reference one relation, the argument is that in this
case, surely a BitmapOr or anything else do the job.
- volatile functions in the jointree, security quals or function/subquery
  RTEs, since the arms are evaluated more than once
- FULL joins, TABLESAMPLE, FOR UPDATE/SHARE, CTEs, set operations,
  recursive queries, well anything other than SELECT ?
- partitioned tables, also inside subqueries. Child RTEs are created inside
  query_planner(), so after arms prune differently their range table
  indexes no longer match the original one, i didn't try to make it work
yet the solution here is maybe to refix pointers back to match root
PlannerInfo for each arm, but this felt too much, i wonder if its worth
it for the benefit it can get for partitioned tables.
- ORs in JOIN ... ON clauses. Only the top level WHERE quals are looked at
  for now.

The transformation is not always beneficial. Here's an example:

SELECT o.*
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'returned' -- very selective: 1k rows
OR c.tier = 'standard'; -- very unselective: 900k of 1M customers

When one condition is very selective a NLJ on the table with the more
selective condition is actually pretty efficient.

Do you unconditionally apply the transformation, or do you have
heuristics to only do it if it likely pays off?

--
David Geier

On 07/10/2026 17:42, David Geier wrote:

On 07.10.26 13:02, Ayoub Kazar wrote:

Attached is a patch that lets the planner rewrite an OR clause that spans
several relations into a UNION ALL with one branch per arm, and use that
plan when it is estimated to be cheaper.

Background

OR clauses that mention more than one relation are awkward for the planner
today. If the OR is the join condition itself (a.x = b.y OR a.x = b.z), it
cannot be a hash or merge join clause, so the only choice left is a nested
loop, usually with a BitmapOr of index scans on the inner side that is run
again for every outer row. If it is a filter on two different tables
(a.f = 1 OR b.g = 2), BitmapOr cannot help either, since it only combines
indexes of one relation, and the OR ends up as a join filter. The
textbook case is a star schema with an OR over conditions on two
dimension tables.

This transformation is extremely useful and in my experience, queries
that can profit from it occur frequently. So +1 for the effort.

Glad to hear.

Where it is not considered:

- ORs that only reference one relation, the argument is that in this
case, surely a BitmapOr or anything else do the job.
- volatile functions in the jointree, security quals or function/subquery
  RTEs, since the arms are evaluated more than once
- FULL joins, TABLESAMPLE, FOR UPDATE/SHARE, CTEs, set operations,
  recursive queries, well anything other than SELECT ?
- partitioned tables, also inside subqueries. Child RTEs are created inside
  query_planner(), so after arms prune differently their range table
  indexes no longer match the original one, i didn't try to make it work
yet the solution here is maybe to refix pointers back to match root
PlannerInfo for each arm, but this felt too much, i wonder if its worth
it for the benefit it can get for partitioned tables.
- ORs in JOIN ... ON clauses. Only the top level WHERE quals are looked at
  for now.

The transformation is not always beneficial. Here's an example:

SELECT o.*
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.status = 'returned' -- very selective: 1k rows
OR c.tier = 'standard'; -- very unselective: 900k of 1M customers

When one condition is very selective a NLJ on the table with the more
selective condition is actually pretty efficient.

Do you unconditionally apply the transformation, or do you have
heuristics to only do it if it likely pays off?

No everything is planned like any other path, each arm in the OR gets
fully planned alone, then UNIONed ALL together, cost is recalculated on
this new Append path, so its cost based, not a rule.

Regards,
Ayoub Kazar

Hello!

I see the motivation / idea behind it, but I think this needs some more thought.

The patch seems to cause some test failures in the test suite (test_misc/003_check_guc, test_plan_advice/001_replan_regress.

And some quick testing revealed two more specific issues:

1. Shouldn't the patch either handle subplans, or skip queries containing them?

CREATE TABLE t1 (id int PRIMARY KEY, a int, c int);
CREATE TABLE t2 (id int PRIMARY KEY, b int);
INSERT INTO t1 SELECT g, g % 10, g % 7 FROM generate_series(1, 2000) g;
INSERT INTO t2 SELECT g, g % 10 FROM generate_series(1, 2000) g;
CREATE INDEX ON t2 (b);
ANALYZE t1, t2;
CREATE SEQUENCE flip_seq;
CREATE FUNCTION flip() RETURNS bool VOLATILE LANGUAGE sql
AS $$ SELECT nextval('flip_seq') % 3 = 0 $$;
SELECT count(*) FROM t1, t2
WHERE (SELECT flip() WHERE t1.id > 0) OR t1.a = t2.b;

2.

The default of 8 is a nice guess because i found that starting from 7 arms,
planning time sometimes doubles (in complicated queries).

The planning time and memory use seems to be exponential with nesting, this explain takes 153 seconds for me in a debug build:

create table t1 (id int primary key, a int, c int);
create table t2 (id int primary key, b int);
insert into t1 select g, g % 10, g % 7 from generate_series(1, 2000) g;
insert into t2 select g, g % 10 from generate_series(1, 2000) g;
analyze t1, t2;
explain (summary, memory, costs off, timing off) select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select id, b from t2) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id;

Hello,

On 07/10/2026 23:44, Zsolt Parragi wrote:

Hello!

I see the motivation / idea behind it, but I think this needs some more thought.

Thanks for the review!

The patch seems to cause some test failures in the test suite
(test_misc/003_check_guc, test_plan_advice/001_replan_regress.

I was aware of GUC test, i forgot about that, so its fixed now.

For the plan_advice test, there's a join test where previously planner
was doing ScalarArrayOpExpr transformation, when i added or expansion it
became cheaper for that test case. IIUC pg_plan_advice doesn't support
having different join strategies across Append arms for the same
relation pair, i'm not sure how should i avoid this test fail without
doing something wrong like disabling or expansion before the join test ?

I suppose this might be a pg_plan_advice issue ?

And some quick testing revealed two more specific issues:

1. Shouldn't the patch either handle subplans, or skip queries containing them?

CREATE TABLE t1 (id int PRIMARY KEY, a int, c int);
CREATE TABLE t2 (id int PRIMARY KEY, b int);
INSERT INTO t1 SELECT g, g % 10, g % 7 FROM generate_series(1, 2000) g;
INSERT INTO t2 SELECT g, g % 10 FROM generate_series(1, 2000) g;
CREATE INDEX ON t2 (b);
ANALYZE t1, t2;
CREATE SEQUENCE flip_seq;
CREATE FUNCTION flip() RETURNS bool VOLATILE LANGUAGE sql
AS $$ SELECT nextval('flip_seq') % 3 = 0 $$;
SELECT count(*) FROM t1, t2
WHERE (SELECT flip() WHERE t1.id > 0) OR t1.a = t2.b;

Correct:
+ if (contain_subplans((Node *) parse->jointree->quals))
this should be enough i think.

2.

The default of 8 is a nice guess because i found that starting from 7 arms,
planning time sometimes doubles (in complicated queries).

The planning time and memory use seems to be exponential with nesting,
this explain takes 153 seconds for me in a debug build:

create table t1 (id int primary key, a int, c int);
create table t2 (id int primary key, b int);
insert into t1 select g, g % 10, g % 7 from generate_series(1, 2000) g;
insert into t2 select g, g % 10 from generate_series(1, 2000) g;
analyze t1, t2;
explain (summary, memory, costs off, timing off) select x.id, max(s.b)
as b from t1 x, (select x.id, max(s.b) as b from t1 x, (select x.id,
max(s.b) as b from t1 x, (select x.id, max(s.b) as b from t1 x,
(select x.id, max(s.b) as b from t1 x, (select x.id, max(s.b) as b
from t1 x, (select x.id, max(s.b) as b from t1 x, (select id, b from
t2) s where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s
where x.a = s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a
= s.b or x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or
x.c = s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c =
s.id or x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or
x.id = s.b group by x.id) s where x.a = s.b or x.c = s.id or x.id =
s.b group by x.id;

True, this shouldn't be allowed for subqueries IMO.

+ /* + * Only top-level queries may be expanded. Expanding within
subqueries + * leads to extreme planning overhead with nested
subqueries. + */ + if (root->parent_root != NULL) + return false;

I also found two other issues:

- Previously i had a comment on whether LateralRTEs should be allowed, i
found that they are not safe for this transformation, therefore there's
a new guard for it too.

- Derived tables with un-grouped aggregates can be optimized into
MinMaxAggPath nodes whose InitPlan replacement parameters are populated
in that arm's private subroot->minmax_aggs during plan creation. Because
set_subqueryscan_references() resolves the subquery's planner state
through the top-level root->simple_rel_array, this mapping is missing
during reference fixing, causing an Aggref found in non-Agg plan node
executor error.

Example:
SELECT * FROM agg_t1 t1, agg_t2 t2, (SELECT min(x) as mx FROM agg_t2) s
WHERE (t1.a = t2.x OR t1.b = t2.y) AND s.mx = 1;

so i added a guard for this too. (attached as v2 of the patch)

I'm not sure whether it is worth making some of the guarded cases work
with or-expansion, if the list doesn't grow bigger than this, i think
that not considering them would be cheaper.

Or we can do the inverse: the query is safe for expansion only if all
RTEs are base relations, not even inherited and partitioned relations.
The latter might be too restrictive but far simpler, maybe (attached as
v3 of the patch).

Thoughts ?

Regards,
Ayoub Kazar

The transformation is not always beneficial. Here's an example:

SELECT o.*
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE    o.status = 'returned' -- very selective: 1k rows
       OR c.tier = 'standard';  -- very unselective: 900k of 1M customers

When one condition is very selective a NLJ on the table with the more
selective condition is actually pretty efficient.

Do you unconditionally apply the transformation, or do you have
heuristics to only do it if it likely pays off?

No everything is planned like any other path, each arm in the OR gets
fully planned alone, then UNIONed ALL together, cost is recalculated on
this new Append path, so its cost based, not a rule.

Ah, that's cool!

I was thinking about it like a rewrite happening post-parsing /
pre-planning.

--
David Geier

Rebased v2 and v3.

Regards,
Ayoub Kazar

+		/* Only plain base relations are permitted */
+		if (rte->rtekind != RTE_RELATION)
+			return false;

This will even reject simple GROUP BY (RTE_GROUP)

SELECT a.x FROM a JOIN b ... WHERE a.f=1 OR b.g=2 GROUP BY a.x

And there are probably many other interesting query features the patch could support without problems.

I also want to point out that this can result in queries that otherwise work on master erroring out with the patch:

CREATE TABLE item (id int PRIMARY KEY, kind text);
CREATE TABLE attr (item_id int, val text, tag int);
INSERT INTO item
SELECT g, CASE WHEN g % 100 = 0 THEN 'txt' ELSE 'num' END
FROM generate_series(1, 100000) g;
INSERT INTO attr
SELECT g, CASE WHEN g % 100 = 0 THEN 'abc' ELSE (g % 500)::text END,
CASE WHEN g % 100 = 0 THEN 7 ELSE g % 1000 END
FROM generate_series(1, 100000) g;
CREATE INDEX ON item (kind);
CREATE INDEX ON attr (tag);
ANALYZE item, attr;

SELECT count(*) FROM item i JOIN attr a ON a.item_id = i.id
WHERE i.kind = 'txt' OR (a.val::int = 7 AND a.tag = 7);

Every 'txt' item in this database fails the right side of the OR, but because the left side is true, the right side is never evaluated.
The evaluation order isn't guaranteed in this case, the documentation explicitly tells people not to do this. So in that sense, breaking it isn't wrong, but it is still a noticeable behavior change.