add support for oracle outer join syntax - the ( + )

Add support for oracle's left join syntax - the ( + )

example syntax:

SELECT * FROM table1, table2 WHERE table1.rec_num = table2.fk_table1( + );

Update:
See https://www.techonthenet.com/oracle/joins.php for syntax examples

Spec

The task is to convert Oracle outer join operator to regular LEFT JOINs while
keeping the original table order where possible.

Limitations on where the operator can be used

The FROM clause of such queries can contain only comma-separated list of
tables (no JOIN operators of any kind or parentheses)

Oracle's outer join operator (+) can only occur in the WHERE clause.
If the WHERE condition has AND at the top, then each argument of the AND is
considered for finding the EXPRESSION operator independently. Otherwise,
the whole WHERE condition is considered for finding the EXPRESSION.

OR are not allowed in the expressions with the operator (TODO: check if AND
is allowed deep inside the EXPRESSION), also the operator is not
allowed in the right side of IN.

The EXPRESSION with the operator can refer only many or 1 table. All fields
of one table should be mentioned with the operator (the OUTER side) the
other tables is the INNER side. If the INNER part is absent (the EXPRESSION
has only constants and the OUTER table) the operator is just ignored.

Need name resolution to interpret the operator

Note that one needs Name Resolution to have been done in order to interpret the query. Example:

select * from t1,t2 where a(+)=b

Here, we need to know which table column a belongs to.

Solution overview

• In Oracle mode, the parser shall accept the (+) operator, where allowed.
• The parser shall generate special kind of items for (+) (TODO: or is it just Item objects with special flag?)
• Sometime after the Name Resolution, we will find all items marked with (+) and based on them, convert the inner joins into into outer join data structures.
  • It should be possible to print back the parse-able LEFT JOIN syntax. This is needed for VIEWs (sql_mode is not saved in the VIEW. it's only saved to PS. So, we can't write (+) when saving VIEW definition.

Generating LEFT JOIN structures from operators

For each table in the FROM clause list we allocate descriptors where we
collect its relations with other tables (list of tables that are
OUTER w.r.t. this one and list of tables which are INNER as well as list
of EXPRESSIONs where the relation was found attached to corespondent OUTER
table and removed from WHERE clause.

Example:

SELECT *

FROM

  t1,t2,t3,t4,t5

WHERE

  t1.a=t2.b(+) AND t2.b=t3.c(+) AND

  t4.d=t3.c(+) AND

  t1.a=t5.e

Collected info:

 Table: t1  order: 0

   Outer side: t2

 Table: t2  order: 1

   On: "test"."t1"."a" = "test"."t2"."b"

   Inner side: t1

   Outer side: t3

 Table: t3  order: 2

   On: "test"."t2"."b" = "test"."t3"."c"

   On: "test"."t4"."d" = "test"."t3"."c"

   Inner side: t2

   Inner side: t4

 Table: t4  order: 3

   Outer side: t3

 Table: t5  order: 4

The relation makes connected graph (cycles found and error issued during the
graphs analyzes).

Above there is only one real connected graph and one degraded:

t1

 \

  \

   t2  t4

    \  /

     \/

     t3    t5

Top of each branch are "independent" tables (i.e. they are not OUTER table
for others and so do not have INNER side tables connected to them)

in the examples t1, t4 and t5 are independent in the example.

So the idea is to scan the list of the tables in the order of FROM list and
as we find "independent" table we include it in the new list and than
process its connected graph recursively putting directly OUTER tables just
after this (sorted by position in the original list ("order")). If included
table has INNER side tables from that relation put between the
"independent" table and the OUTER according to its "order" and procedure
processing its relation processed recursively.

We mark processed tables (included in the new list) which allow to detect
possible cyclic relation and issue an error.

If after the scan left unprocessed tables it is ring relations and so an
error.

So after processing we will have new table order, for example it is:

t1, t2, t4, t3, t5

so if table has INNER side we "replace" "," before the table with LEFT JOIN
.. ON (...) and if no with just JOIN.

so the above example becomes:

FROM t1

  LEFT JOIN t2 ON ("test"."t1"."a" = "test"."t2"."b")

  JOIN t4

  LEFT JOIN t3 ON ("test"."t2"."b" = "test"."t3"."c" AND

                   "test"."t4"."d" = "test"."t3"."c")

  JOIN t5

WHERE

  t1.a=t5.e