Uploaded image for project: 'MariaDB Server'
  1. MariaDB Server
  2. MDEV-13648

Add FULL OUTER JOIN to MariaDB

    XMLWordPrintable

Details

    Description

      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?

      Attachments

        Issue Links

          Activity

            People

              igor Igor Babaev
              Juan Juan Telleria
              Votes:
              14 Vote for this issue
              Watchers:
              29 Start watching this issue

              Dates

                Created:
                Updated:

                Git Integration

                  Error rendering 'com.xiplink.jira.git.jira_git_plugin:git-issue-webpanel'. Please contact your Jira administrators.