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

Hello hackers,

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.

I ran into this while working on undirected edge patterns in SQL/PGQ
[1]. An undirected edge becomes an OR over the two directions of the
edge in the join condition, and on LSQB the nested loop
with the per-row BitmapOr ran the inner scan about 61 million times at SF
0.1. Writing the same query by hand as a UNION ALL took it from 91.7 s to
1.6 s, and at greater scale factors it was faster by 4610x . I first
did the rewrite in the GRAPH_TABLE rewriter, but Ashutosh pointed out that
it belongs in the planner: if at any time its added, the rewrite for
SQL/PGQ would be redundant.

Previous work

There was a previous discussion on this, Tom Lane posted a patch for
this in 2017 [2], in the thread . The idea is: plan the arms before
query_planner() runs and add
the result as an Append path afterwards. The differences are the way
duplicates are avoided and what is accepted. At that time it wasn't
clear how to prove correctness on deduplication (which was done with a
Unique on CTIDs of base relations), last message of the thread actually
puts the proof of doing the expansion with negating previous arms'
clauses. The latter way of doing it is far better than deduplication
with CTIDs because: we are not limited to plain tables, we don't need a
unique step.

What the patch does

For an OR with arms C1..Cn, branch k is planned as the original query with
the OR replaced by

    Ck AND (C1) IS NOT TRUE AND ... AND (C(k-1)) IS NOT TRUE

so a row that satisfies several arms is returned only by the first of
them. IS NOT TRUE (rather than NOT) keeps rows where an earlier arm
evaluates to NULL, so the result has the same rows and multiplicity as the
original query and no duplicate elimination step is needed. Each branch is
planned with query_planner() on a copy of the query, the cheapest path
of each branch is taken, and
they are combined into an Append that is added to the top scan/join
relation with add_path(). Here i followed exactly what Tom's patch did.

Outer joins are reduced again inside each branch, since the branch's
quals can make it null-rejecting.

Where it applies:

An OR in the WHERE clause with between 2 and or_expansion_limit arms that
refers to at least two relations: either the OR is the join condition, or
it is a filter spanning two tables.

    SELECT ... FROM a, b WHERE a.x = b.y OR a.x = b.z;
    SELECT ... FROM a JOIN b ON a.id = b.a_id WHERE a.f = 1 OR b.g = 2;

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.

or_expansion_limit (default 8, 0 disables) bounds the number of arms.
Every arm costs one extra planner run, and arm n carries n-1 negated copies
of the earlier arms, so planning cost can grow quickly with the number of
arms. It is also an off switch to makes before/after comparisons easy
for the moment. The
default of 8 is a nice guess because i found that starting from 7 arms,
planning time sometimes doubles (in complicated queries).

Some simlpe benchmark results

12 vCPUs, 15GB RAM, NVMe, shared_buffers = 2GB, work_mem = 128MB,
max_parallel_workers_per_gather = 2.

Star schema, 20M row fact table, OR between a condition on a customer
dimension and one on a product dimension:
    1893 ms -> 148 ms   (planning 0.26 ms -> 0.52 ms)

Two 2M row tables, selective OR with one arm on each table:
    415 ms -> 26 ms     (planning 0.94 ms -> 1.07 ms)

Three tables, three selective arms:
    891 ms -> 125 ms    (planning 1.6 ms -> 3.0 ms)

Join of two 2M row tables on (a = a OR b = b), join columns indexed,
outer side limited to id < 100k:
    1520 ms -> 435 ms   (buffer hits 57,204,110 -> 179,797)
Same with no indexes, id < 50k:
    1508 ms -> 484 ms
With id < 10k, indexed / not indexed:
    841 ms -> 417 ms  /  1538 ms -> 451 ms

Where the arms are not selective (about 20% of the rows each) the original
plans are kept.

Patch and simple benchmark files attached.

[1]
https://www.postgresql.org/message-id/4ab664c3585d3c2da2d4c1d1bbed430e%40data-bene.io
[2]
https://www.postgresql.org/message-id/flat/7f70bd5a-5d16-e05c-f0b4-2fdfc8873489%40BlueTreble.com

Regards,
Ayoub Kazar