Add support for FULL OUTER JOIN

https://www.w3schools.com/sql/sql_join_full.asp

One of the way how to implement is to re-write the query

select t1.*, t2.* from t1 full outer join t2 on P(t1,t2)

into the following union all:

select t1.*, t2.* from t1 left outer join t2 on P(t1,t2)

union all

select t1.*,t2.* from t2 left outer join t1 on P(t1,t2) where t1.a is null

Here t1.a is some non-nullable column of t1 (e.g. the column of single column primary key).

Solution considerations

contents

1. Conversion to simpler join types

2. FULL OUTER JOIN Execution

2.1 Approach #1: implement full outer join as an operation in executor

2.2 Approach #2: rewrite into two OUTER joins

Conversion to simpler join types

We will need code that analyzes/rewrites FULL OUTER JOIN into LEFT/RIGHT/INNER join based on NULL-rejecting predicates in the WHERE (or ON expressions that are outside the outer join in question).

2. FULL OUTER JOIN Execution

One can think of:
Approach #1: implement full outer join as an operation in executor.
Approach #2: rewrite it into two inner joins

2.1 Approach #1: implement full outer join as an operation in executor

This is what e.g. Cockroach and PostgreSQL seem to do.

FULL OUTER JOIN can be handled by Merge Join (or similar) operation which is symmetric wrt its inputs and can emit rows that didn't have matches for both inputs.

(note: for PostgreSQL, I saw FULL OUTER JOIN to be handled by a variant of Hash join and Merge Join. PostgreSQL seems to require that FULL OUTER JOIN conditions have equalities. This error is produced

ERROR: FULL JOIN is only supported with merge-joinable or hash-joinable join condition

when one doesn't have a join equality in the ON expression.)

Extend MariaDB's OUTER JOIN code to compute FULL OUTER JOIN?

Can't think of anything really efficient here.
We basically need to pick one side of the join to be "inner" and then compute an outer join but also keep track of which record combinations of the "inner" side were hit and which weren't?
All approaches seem to be quite expensive.

2.2 Approach #2: rewrite into two OUTER joins.

In the query

  SELECT

    ...

    t1 FULL OUTER JOIN t2 ON fjcond

    ...

where t1 and t2 may be base tables or more complex expressions,

Rewrite the

   t1 FULL OUTER JOIN t2 ON fjcond

part into

  (

    select ... from t1 left join t2 on fjcond

    union all

    select ... from t2 left join t1 on fjcond where t1.pk IS NULL

  ) as full_oj_tbl

Here we assume that t1 has a not-null column "pk", so we can construct a condition meaning "outer join had no matches".
The "..." denotes all the needed columns.

How to check for non-matches if all columns are NULL-able

If we cannot find a column t1.pk such that we could add a t1.pk IS NULL, we can rewrite into

    select ... from t2 left join ( select *, '1' as NULL_MARKER from t1) on fjcond where NULL_MARKER IS NULL

(In the code, see Item_direct_view_ref::null_ref_table).

Non-symmetry

Note that the rewrite is not symmetric wrt t1 and t2. Does it matter? Well, one side will be able to benefit from outer join's Not-Exists optimization while the other won't?