mirror of
https://github.com/MariaDB/server.git
synced 2025-10-31 02:46:29 +01:00
dae5a99c73
Parser changes made by Alexander Barkov <bar@mariadb.com>. Part of the tests made by Iqbal Hassan <iqbal@hasprime.com>. Initially marking with ORA_JOIN flag made also by Iqbal Hassan <iqbal@hasprime.com>. Main idea is that parser mark fields with (+) with a flag (ORA_JOIN). During Prepare the flag bring to the new created items if needed. Later after preparing (fix_firlds()) WHERE confition the relations betweel the tables analyzed and tables reordered so to make JOIN/LEFT JOIN operators in chain equivalent to the query with oracle outer join operator (+). Then the flags of (+) removed.
1147 lines
32 KiB
C++
1147 lines
32 KiB
C++
/* Copyright (c) 2000, 2016, Oracle and/or its affiliates.
|
|
Copyright (c) 2010, 2024, MariaDB
|
|
|
|
This program is free software; you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation; version 2 of the License.
|
|
|
|
This program is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with this program; if not, write to the Free Software
|
|
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
|
|
|
|
#include "lex_ident_sys.h"
|
|
#include "mariadb.h"
|
|
#include "sql_base.h"
|
|
#include "sql_parse.h" // check_stack_overrun
|
|
|
|
/*
|
|
Support for Oracle's outer join syntax.
|
|
|
|
== Contents ==
|
|
1. Basic syntax
|
|
1.1. Outer join operator
|
|
1.2. Outer-joining tables
|
|
1.3 Example 1: peer outer joins
|
|
1.4 Example 2: chained outer joins
|
|
1.5 Outer join graph
|
|
2. Implementation
|
|
2.1 Parser
|
|
2.2 Conversion to LEFT JOIN tree
|
|
2.2.1 Building the graph
|
|
2.2.2 Ordering the graph
|
|
2.2.3 Building the TABLE_LIST structure
|
|
3. Debugging
|
|
|
|
|
|
== 1. Basic syntax ==
|
|
|
|
Oracle's outer join syntax is like this:
|
|
|
|
set sql_mode='oracle';
|
|
select * from t1, t2 where t1.col=t2.col(+)
|
|
|
|
The (+) is the "outer join operator". It specifies that table t2 is outer-
|
|
joined (i.e. is INNER) and the predicate containing the (+) is the outer
|
|
join's ON expression. This makes the above query to be equivalent to:
|
|
|
|
select * from t1.col left join t2 on t1.col=t2.col
|
|
|
|
== 1.1. Outer join operator ==
|
|
Outer join operators may occur only in the WHERE clause. The WHERE clause
|
|
may be one predicate or multiple predicates connected with AND. Each of the
|
|
predicates
|
|
- may reference only one outer-joined (aka the "INNER") table (all
|
|
references to its columns have "outer join operator")
|
|
- may reference zero, one or more "OUTER" tables (without outer join
|
|
operator).
|
|
|
|
A predicate that refers to an INNER table and OUTER table(s) prescribes that
|
|
the INNER table is joined with outer join operation.
|
|
|
|
A predicate that only refers to an INNER table (like "t1.col(+)=124") will be
|
|
added to the table's ON expression, provided there is another predicate that
|
|
prescribes that the inner table is joined with outer join operation
|
|
(otherwise, the predicate remains in the WHERE and a warning is issued).
|
|
|
|
== 1.2. Outer-joining tables ==
|
|
|
|
If a query uses outer join operators, the FROM clause must be a simple
|
|
comma-separated list of tables (denoting inner join operations):
|
|
|
|
FROM t1, t2, ..., tN
|
|
|
|
If outer join operators prescribe that some table t_j is joined with outer
|
|
join, the FROM clause becomes:
|
|
|
|
FROM (t1, ..., tbl) LEFT JOIN t_j ON outer_join_predicates, ... tN
|
|
|
|
Here, all tables used by outer_join_predicates are moved to the left (ok to
|
|
do as inner join is commutative).
|
|
|
|
== 1.3 Example 1: peer outer joins ==
|
|
Consider a query:
|
|
|
|
select *
|
|
from t1,t2,t3
|
|
where t1.col=t2.col(+) and t1.col=t3.col(+)
|
|
|
|
This has two outer join predicates
|
|
OUTER=t1, INNER=t2
|
|
OUTER=t1, INNER=t3
|
|
|
|
The query can be transformed to
|
|
|
|
select *
|
|
from (t1 left join t2 on t2.col=t1.col) left join t3 on t1.col=t3.col
|
|
|
|
or an equvalent query:
|
|
|
|
select *
|
|
from (t1 left join t3 on t3.col=t1.col) left join t2 on t1.col=t2.col
|
|
|
|
MariaDB optimizer will try to preserve the original order the tables were
|
|
listed in the WHERE clause.
|
|
|
|
== 1.4 Example 2: chained outer joins ==
|
|
The query
|
|
|
|
select ...
|
|
from t1,t2,t3
|
|
where cond1(t1.col, t2.col(+)) and cond2(t2.col, t3.col(+))
|
|
|
|
has two outer join predicates
|
|
OUTER=t1, INNER=t2
|
|
OUTER=t2, INNER=t3
|
|
|
|
The query is transformed into
|
|
|
|
select ...
|
|
from
|
|
t1
|
|
left join t2 on cond1(t1.col, t2.col)
|
|
left join t3 on cond2(t2.col, t3.col)
|
|
|
|
Note that the result of transformation is
|
|
(t1 left join t2) left join t3
|
|
and not
|
|
t1 left join (t2 left join t3)
|
|
|
|
(these two expressions are in general not equivalent) There's always just one
|
|
table on the inner side of the outer join.
|
|
|
|
== 1.5 Outer join graph ==
|
|
If we take tables as vertexes and OUTER->INNER relationships as edges, then
|
|
we get a directed graph.
|
|
|
|
The graph must not have cycles. A query that produces a graph with cycles
|
|
is aborted with error.
|
|
The graph may have alternative paths, like t1->t2->t3 and t1->t4->t3.
|
|
|
|
In order to produce the query expression with LEFT JOIN syntax, one needs to
|
|
perform topological sorting of the graph.
|
|
Then, write out the graph vertices (tables) in an order such that all edges
|
|
would come from left to the right.
|
|
|
|
== 2. Implementation ==
|
|
|
|
== 2.1 Parser ==
|
|
The parser recognizes the "(+)" operator. After parsing, Item objects that
|
|
have a (+) operator somewhere inside have (item->with_flags() & ORA_JOIN)
|
|
flag set.
|
|
|
|
== 2.2 Conversion to LEFT JOIN tree ==
|
|
|
|
At Name Resolution phase, we convert (+) operators into LEFT JOIN data
|
|
structures (that is, a tree of TABLE_LIST objects with ON expressions).
|
|
This is done in setup_oracle_join().
|
|
|
|
=== 2.2.1 Building the graph ===
|
|
First, we create an array of table_pos structures. These are the vertices
|
|
of the graph.
|
|
Then, we analyze the WHERE clause and construct graph's edges.
|
|
|
|
== 2.2.2 Ordering the graph ==
|
|
|
|
Then, we walk the graph and construct a linked list of table_pos structures
|
|
(connected via table_pos::{next,prev}) so that they come in what we call
|
|
"LEFT JOIN syntax order". In decreasing order of importance, the criteria
|
|
are:
|
|
1. Outer tables must come before their inner tables.
|
|
2. Tables that are connected to the tables already in the order must come
|
|
before those who are not
|
|
3. Tables that were listed earlier in the original FROM clause come before.
|
|
|
|
== 2.2.3 Building the TABLE_LIST structure ==
|
|
Then, we walk through the table_pos objects via {table_pos::next} edges and
|
|
create a parsed LEFT JOIN data sructure.
|
|
|
|
For a chain of t1-t2-t3-t4-t5 we would create:
|
|
|
|
(
|
|
(
|
|
(
|
|
t1
|
|
[left] join t2 on cond2
|
|
)
|
|
[left] join t3 on cond3
|
|
)
|
|
[left] join t4 on cond4
|
|
)
|
|
[left] join t5 on cond5
|
|
|
|
Each pair of () brackets is a TABLE_LIST object representing a join nest. It
|
|
has a NESTED_JOIN object which includes its two children.
|
|
|
|
Some of the brackets are redundant, this is not a problem because
|
|
simplify_joins() will remove them.
|
|
|
|
== 3. Debugging ==
|
|
One can examine the conversion result by doing this:
|
|
|
|
create view v1 as select ...
|
|
show create view v1;
|
|
|
|
Unlike regular EXPLAIN, this bypasses simplify_joins() call.
|
|
*/
|
|
|
|
|
|
/**
|
|
An outer join graph vertex.
|
|
*/
|
|
|
|
struct table_pos: public Sql_alloc
|
|
{
|
|
/*
|
|
Links the tables in the "LEFT JOIN syntax order"
|
|
*/
|
|
table_pos *next;
|
|
table_pos *prev;
|
|
|
|
/* Tables we have outgoing edges to. Duplicates are possible. */
|
|
List<table_pos> inner_side;
|
|
|
|
/* Incoming edges */
|
|
List<table_pos> outer_side;
|
|
|
|
/* ON condition expressions (to be AND-ed together) */
|
|
List<Item> on_conds;
|
|
TABLE_LIST *table;
|
|
|
|
/* Ordinal number of the table in the original FROM clause */
|
|
int order;
|
|
|
|
/* TRUE <=> this table is already linked (in the prev<=>next chain) */
|
|
bool processed;
|
|
|
|
/* TRUE <=> All tables in outer_side are already linked in prev/next */
|
|
bool outer_processed;
|
|
|
|
bool is_outer_of(table_pos *tab)
|
|
{
|
|
List_iterator_fast<table_pos> it(outer_side);
|
|
table_pos *t;
|
|
while((t= it++))
|
|
{
|
|
if (t == tab)
|
|
return TRUE;
|
|
}
|
|
return FALSE;
|
|
}
|
|
};
|
|
|
|
static bool add_conditions_to_where(THD *thd, Item **conds,
|
|
List<Item> &&return_to_where);
|
|
|
|
/*
|
|
Order the tables (which are inner_side peers of some table)
|
|
- INNER table comes before its OUTER
|
|
- then, tables that were later in the FROM clause come first
|
|
*/
|
|
|
|
static int table_pos_sort(table_pos *a, table_pos *b, void *arg)
|
|
{
|
|
if (a->is_outer_of(b))
|
|
return -1;
|
|
if (b->is_outer_of(a))
|
|
return 1;
|
|
return b->order - a->order;
|
|
}
|
|
|
|
|
|
/**
|
|
@brief
|
|
Collect info about table relationships from a part of WHERE condition
|
|
|
|
@detail
|
|
This processes an individual AND-part of the WHERE clause.
|
|
We catch these patterns:
|
|
|
|
1. Condition refers to one or more OUTER tables and one INNER table:
|
|
cond(outer_table1.col, outer_table2.col, ..., inner_table.col(+))
|
|
|
|
2. Condition refers to just one inner table:
|
|
cond(inner_table.col(+), constants)
|
|
|
|
We note one single inner table and zero or more outer tables and record
|
|
these dependencies in the table graph.
|
|
|
|
Also, the predicates that will form the ON expression are collected in
|
|
table_list::on_conds.
|
|
*/
|
|
|
|
static bool
|
|
ora_join_process_expression(THD *thd, Item *cond,
|
|
table_pos *tab, uint n_tables)
|
|
{
|
|
DBUG_ENTER("ora_join_process_expression");
|
|
|
|
struct ora_join_processor_param param;
|
|
param.inner= NULL;
|
|
param.outer.empty();
|
|
param.or_present= FALSE;
|
|
|
|
if (cond->walk(&Item::ora_join_processor, (void *)(¶m), WALK_NO_REF))
|
|
DBUG_RETURN(TRUE);
|
|
|
|
/*
|
|
There should be at least one table for inner part (outer can be absent in
|
|
case of constants)
|
|
*/
|
|
DBUG_ASSERT(param.inner != NULL);
|
|
table_pos *inner_tab= tab + param.inner->ora_join_table_no;
|
|
|
|
if (param.outer.elements > 0)
|
|
{
|
|
if (param.or_present)
|
|
{
|
|
my_error(ER_INVALID_USE_OF_ORA_JOIN_WRONG_FUNC, MYF(0));
|
|
DBUG_RETURN(TRUE);
|
|
}
|
|
{
|
|
// Permanent list can be used in AND
|
|
Query_arena_stmt on_stmt_arena(thd);
|
|
inner_tab->on_conds.push_back(cond);
|
|
}
|
|
List_iterator_fast<TABLE_LIST> it(param.outer);
|
|
TABLE_LIST *t;
|
|
while ((t= it++))
|
|
{
|
|
table_pos *outer_tab= tab + t->ora_join_table_no;
|
|
outer_tab->inner_side.push_back(inner_tab);
|
|
inner_tab->outer_side.push_back(outer_tab);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
// Permanent list can be used in AND
|
|
Query_arena_stmt on_stmt_arena(thd);
|
|
inner_tab->on_conds.push_back(cond);
|
|
}
|
|
|
|
DBUG_RETURN(FALSE);
|
|
}
|
|
|
|
|
|
/**
|
|
@brief
|
|
Put the table @t into "LEFT JOIN syntax order" list after table @end.
|
|
|
|
@detail
|
|
@t must not be already in that list.
|
|
*/
|
|
|
|
static void insert_element_after(table_pos *end, table_pos *t,
|
|
uint * const processed)
|
|
{
|
|
DBUG_ASSERT(t->next == NULL);
|
|
DBUG_ASSERT(t->prev == NULL);
|
|
if (end)
|
|
{
|
|
if ((t->next= end->next))
|
|
end->next->prev= t;
|
|
end->next= t;
|
|
t->prev= end;
|
|
}
|
|
t->processed= TRUE;
|
|
(*processed)++;
|
|
}
|
|
|
|
|
|
static bool process_outer_relations(THD* thd,
|
|
table_pos *tab,
|
|
table_pos *first,
|
|
uint * const processed,
|
|
uint n_tables);
|
|
|
|
|
|
/**
|
|
@brief
|
|
Check presence of directional cycles (starting from "tab" with beginning
|
|
of check in "beginning") in case we have non-directional cycle
|
|
|
|
@bdetail
|
|
Recusively check if table "beginning" is reachable from table "tab" through
|
|
the table_pos::inner_side pointers.
|
|
*/
|
|
|
|
static bool check_directed_cycle(THD* thd, table_pos *tab,
|
|
table_pos* beginning, uint lvl, uint max)
|
|
{
|
|
List_iterator_fast<table_pos> it(tab->inner_side);
|
|
table_pos *t;
|
|
uchar buff[STACK_BUFF_ALLOC]; // Max argument in function
|
|
if (check_stack_overrun(thd, STACK_MIN_SIZE, buff))
|
|
return(TRUE);// Fatal error flag is set!
|
|
|
|
if ((++lvl) >= max)
|
|
{
|
|
/*
|
|
We checked tables more times than tables we have => we have other cycle
|
|
reachable from "beginning"
|
|
|
|
TODO: try to make such test
|
|
The loop of interest would like this:
|
|
|
|
t1->t2->t3->t4->-+
|
|
^ |
|
|
| |
|
|
+--------+
|
|
However for such graph we would first call
|
|
check_directed_cycle(tab=t3,beginning=t3) and detect the loop.
|
|
We won't get to the point where we we would call
|
|
check_directed_cycle(tab=t3,beginning=t1)
|
|
*/
|
|
return FALSE;
|
|
}
|
|
while ((t= it++))
|
|
{
|
|
if (t == beginning)
|
|
return true;
|
|
if (check_directed_cycle(thd, t, beginning, lvl, max))
|
|
return TRUE;
|
|
}
|
|
return FALSE;
|
|
}
|
|
|
|
|
|
/**
|
|
@brief
|
|
Table @tab has been added to the "LEFT JOIN syntax ordering". Add its
|
|
inner-side neighbors first, then add all their connections.
|
|
|
|
@param tab Table for which to process
|
|
param processed Counter of processed tables.
|
|
@param n_tables Total number of tables in the join
|
|
|
|
@return
|
|
FALSE OK
|
|
TRUE Error, found a circular loop in outer join relationships.
|
|
*/
|
|
|
|
static bool process_inner_relations(THD* thd,
|
|
table_pos *tab,
|
|
uint *const processed,
|
|
uint n_tables)
|
|
{
|
|
if (tab->inner_side.elements > 0)
|
|
{
|
|
List_iterator_fast<table_pos> it(tab->inner_side);
|
|
table_pos *t;
|
|
|
|
/* First, add all inner_side neighbors */
|
|
while ((t= it++))
|
|
{
|
|
if (t->processed)
|
|
{
|
|
/*
|
|
it is case of "non-cyclic" loop (or just processed already
|
|
branch)
|
|
|
|
tab->t
|
|
^
|
|
|
|
|
t1--+
|
|
(it would be t1 then t then tab and again probe t (from tab))
|
|
|
|
Check if it is also directional loop:
|
|
*/
|
|
if (check_directed_cycle(thd, t, t, 0, n_tables))
|
|
{
|
|
/*
|
|
Found a circular dependency:
|
|
|
|
t1->tab -> t -+
|
|
^ |
|
|
| |
|
|
+--....--+
|
|
*/
|
|
my_error(ER_INVALID_USE_OF_ORA_JOIN_CYCLE, MYF(0));
|
|
return TRUE;
|
|
}
|
|
}
|
|
else
|
|
insert_element_after(tab, t, processed);
|
|
}
|
|
|
|
/* Second, process the connections of each neighbor */
|
|
it.rewind();
|
|
while ((t= it++))
|
|
{
|
|
if (!t->outer_processed)
|
|
{
|
|
if (process_outer_relations(thd, t, tab, processed, n_tables))
|
|
return TRUE;
|
|
}
|
|
}
|
|
}
|
|
return FALSE;
|
|
}
|
|
|
|
|
|
/*
|
|
@brief
|
|
Insert @tab into the "LEFT JOIN syntax ordering" list between @first and
|
|
@last.
|
|
*/
|
|
|
|
static
|
|
void insert_element_between(THD *thd, table_pos *tab,
|
|
table_pos *first, table_pos *last,
|
|
uint *const processed)
|
|
{
|
|
table_pos *curr= last;
|
|
|
|
DBUG_ASSERT(first != last);
|
|
// find place to insert
|
|
while (curr->prev != first && tab->order > curr->prev->order &&
|
|
!curr->is_outer_of(curr->prev))
|
|
curr= curr->prev;
|
|
|
|
insert_element_after(curr->prev, tab, processed);
|
|
}
|
|
|
|
|
|
/*
|
|
@brief
|
|
Table @tab has been added to the "LEFT JOIN syntax ordering". Add its
|
|
outer-side neighbors and all their connections.
|
|
|
|
@param tab Examine tab->outer_side and their connection.
|
|
@param first All outer-side connections must be added after "first" and
|
|
before the "tab".
|
|
|
|
@detail
|
|
Outer-side neighbors need to be added *before* the table tab.
|
|
*/
|
|
|
|
static bool process_outer_relations(THD* thd,
|
|
table_pos *tab,
|
|
table_pos *first,
|
|
uint * const processed,
|
|
uint n_tables)
|
|
{
|
|
uchar buff[STACK_BUFF_ALLOC]; // Max argument in function
|
|
if (check_stack_overrun(thd, STACK_MIN_SIZE, buff))
|
|
return(TRUE);// Fatal error flag is set!
|
|
|
|
tab->outer_processed= TRUE;
|
|
if (tab->outer_side.elements)
|
|
{
|
|
List_iterator_fast<table_pos> it(tab->outer_side);
|
|
table_pos *t;
|
|
while((t= it++))
|
|
{
|
|
if (!t->processed)
|
|
{
|
|
/*
|
|
This (t3 in the example) table serves as inner table for several
|
|
others.
|
|
|
|
For example we have such dependencies (outer to the right and inner
|
|
to the left):
|
|
SELECT *
|
|
FROM t1,t2,t3,t4
|
|
WHERE t1.a=t2.a(+) AND t2.a=t3.a(+) AND
|
|
t4.a=t3.a(+);
|
|
|
|
t1->t2-+
|
|
|
|
|
+==>t3
|
|
|
|
|
t4-----+
|
|
|
|
So we have built following list of left joins already (we
|
|
started from the first independent table we have found - t1
|
|
and went by inner_side relation till table t3):
|
|
|
|
first
|
|
|
|
|
*->t1 => t2 => t3
|
|
^
|
|
|
|
|
t->t4 tab
|
|
|
|
Now we go by list of unprocessed outer relation of t3 and put
|
|
them before t3.
|
|
So we have to put t4 between t1 and t2 or between t2 and t3
|
|
(depends on its original position because we
|
|
are trying to keep original order where it is possible).
|
|
|
|
t1 => t2 => t4 => t3
|
|
|
|
SELECT *
|
|
FROM t1 left join t2 on (t1.a=t2.a),
|
|
t4
|
|
left join t3 on (t2.a=t3.a and t4.a=t3.a)
|
|
|
|
We can also put it before t1, but as far as we have found t1 first
|
|
it have definitely early position in the original list of tables
|
|
than t4.
|
|
*/
|
|
insert_element_between(thd, t, first, tab, processed);
|
|
if (process_inner_relations(thd, t, processed, n_tables))
|
|
return TRUE;
|
|
}
|
|
}
|
|
}
|
|
return process_inner_relations(thd, tab, processed, n_tables);
|
|
}
|
|
|
|
|
|
#ifndef DBUG_OFF
|
|
static void dbug_trace_table_pos(table_pos *t)
|
|
{
|
|
DBUG_ENTER("dbug_trace_table_pos");
|
|
DBUG_PRINT("table_pos", ("Table: %s", t->table->alias.str));
|
|
List_iterator_fast iti(t->on_conds);
|
|
Item *item;
|
|
while ((item= iti++))
|
|
{
|
|
StringBuffer<STRING_BUFFER_USUAL_SIZE> expr;
|
|
item->print(&expr, QT_ORDINARY);
|
|
DBUG_PRINT("INFO", (" On_conds: %s", expr.c_ptr()));
|
|
}
|
|
List_iterator_fast itot(t->outer_side);
|
|
table_pos *tbl;
|
|
while ((tbl= itot++))
|
|
DBUG_PRINT("INFO", (" Outer side: %s", tbl->table->alias.str));
|
|
|
|
List_iterator_fast itit(t->inner_side);
|
|
while ((tbl= itit++))
|
|
DBUG_PRINT("INFO", (" Inner side: %s", tbl->table->alias.str));
|
|
|
|
DBUG_VOID_RETURN;
|
|
}
|
|
|
|
|
|
static void dbug_trace_table_entry(const char *prefix,
|
|
const char *legend, TABLE_LIST *t)
|
|
{
|
|
if (t)
|
|
{
|
|
StringBuffer<STRING_BUFFER_USUAL_SIZE> expr;
|
|
if (t->on_expr)
|
|
t->on_expr->print(&expr, QT_ORDINARY);
|
|
|
|
DBUG_PRINT(prefix, ("%s Table: '%s' %p outer: %s on_expr: %s", legend,
|
|
(t->alias.str ? t->alias.str : ""), t,
|
|
(t->outer_join ? "YES" : "no"),
|
|
(t->on_expr ? expr.c_ptr() : "NULL")));
|
|
}
|
|
else
|
|
DBUG_PRINT(prefix, ("%s Table: NULL", legend));
|
|
}
|
|
|
|
|
|
static void dbug_trace_table_list(TABLE_LIST *t)
|
|
{
|
|
DBUG_ENTER("dbug_trace_table_list");
|
|
dbug_trace_table_entry("TABLE_LIST", "---", t);
|
|
dbug_trace_table_entry("INFO", "Embedding", t->embedding);
|
|
if (t->join_list)
|
|
{
|
|
DBUG_PRINT("INFO", ("Join list: %p elements %d",
|
|
t->join_list, t->join_list->elements));
|
|
List_iterator_fast<TABLE_LIST> it(*t->join_list);
|
|
TABLE_LIST *tbl;
|
|
while ((tbl= it++))
|
|
{
|
|
dbug_trace_table_entry("INFO", "join_list", tbl);
|
|
}
|
|
}
|
|
else
|
|
DBUG_PRINT("INFO", ("Join list: NULL"));
|
|
|
|
DBUG_VOID_RETURN;
|
|
}
|
|
#endif
|
|
|
|
|
|
/**
|
|
@brief
|
|
Init array of graph vertexes
|
|
|
|
@return
|
|
TRUE Error
|
|
FALSE Ok, conversion is either done or not needed.
|
|
*/
|
|
|
|
static bool init_tables_array(TABLE_LIST *tables,
|
|
uint n_tables,
|
|
table_pos *tab)
|
|
{
|
|
table_pos *t= tab;
|
|
TABLE_LIST *table= tables;
|
|
uint i= 0;
|
|
DBUG_ENTER("init_tables_array");
|
|
|
|
/*
|
|
Create a graph vertex for each table.
|
|
Also note the original order of tables in the FROM clause.
|
|
*/
|
|
for (;table; i++, t++, table= table->next_local)
|
|
{
|
|
DBUG_ASSERT(i < n_tables);
|
|
if (table->outer_join || table->nested_join || table->natural_join ||
|
|
table->embedding || table->straight)
|
|
{
|
|
// mixed with other JOIN operations
|
|
my_error(ER_INVALID_USE_OF_ORA_JOIN_MIX, MYF(0));
|
|
DBUG_RETURN(TRUE);
|
|
}
|
|
t->next= t->prev= NULL;
|
|
t->inner_side.empty();
|
|
t->outer_side.empty();
|
|
t->on_conds.empty();
|
|
t->table= table;
|
|
// psergey-todo: can't we keep ora_join_table_no in table_pos?
|
|
table->ora_join_table_no= t->order= i;
|
|
t->processed= t->outer_processed= FALSE;
|
|
}
|
|
DBUG_ASSERT(i == n_tables);
|
|
DBUG_RETURN(FALSE);
|
|
}
|
|
|
|
|
|
/**
|
|
@brief
|
|
Convert Oracle's outer join (+) operators into regular outer join
|
|
structures
|
|
|
|
@param conds INOUT The WHERE condition
|
|
@param select_join_list INOUT Top-level join list
|
|
|
|
@return
|
|
TRUE Error
|
|
FALSE Ok, conversion is either done or not needed.
|
|
*/
|
|
|
|
bool setup_oracle_join(THD *thd, Item **conds,
|
|
TABLE_LIST *tables,
|
|
SQL_I_List<TABLE_LIST> &select_table_list,
|
|
List<TABLE_LIST> *select_join_list,
|
|
List<Item> *all_fields)
|
|
{
|
|
DBUG_ENTER("setup_oracle_join");
|
|
uint n_tables= select_table_list.elements;
|
|
uint i= 0;
|
|
|
|
if (!(*conds)->with_ora_join() || n_tables == 0)
|
|
DBUG_RETURN(FALSE); // no oracle joins
|
|
|
|
table_pos *tab= (table_pos *) new(thd->mem_root) table_pos[n_tables];
|
|
if (init_tables_array(tables, n_tables, tab))
|
|
DBUG_RETURN(TRUE); // mixed with other joins
|
|
|
|
|
|
/*
|
|
Process the WHERE clause:
|
|
- Find Outer Join conditions
|
|
- Create graph edges from them
|
|
- Remove them from the WHERE clause
|
|
*/
|
|
if (is_cond_and(*conds))
|
|
{
|
|
Item_cond_and *and_item= (Item_cond_and *)(*conds);
|
|
Item *item;
|
|
List_iterator<Item> it(*and_item->argument_list());
|
|
while ((item= it++))
|
|
{
|
|
if (item->with_ora_join())
|
|
{
|
|
if (ora_join_process_expression(thd, item, tab, n_tables))
|
|
DBUG_RETURN(TRUE);
|
|
item->walk(&Item::remove_ora_join_processor, 0, 0);
|
|
it.remove(); // will be moved to ON
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if ((*conds)->with_ora_join())
|
|
{
|
|
if (ora_join_process_expression(thd, (*conds), tab, n_tables))
|
|
DBUG_RETURN(TRUE);
|
|
(*conds)->walk(&Item::remove_ora_join_processor, 0, 0);
|
|
*conds= NULL; // will be moved to ON
|
|
}
|
|
}
|
|
|
|
/*
|
|
Check for inner tables that don't have outer tables;
|
|
Prepare for producing the ordering.
|
|
*/
|
|
List<Item> return_to_where;
|
|
return_to_where.empty();
|
|
for (i= 0; i < n_tables; i++)
|
|
{
|
|
if (tab[i].on_conds.elements > 0 &&
|
|
tab[i].outer_side.elements == 0)
|
|
{
|
|
/*
|
|
This table is marked as INNER but it has no matching OUTER tables. This
|
|
can happen for queries like:
|
|
|
|
select * from t1,t2 where t2.a(+)=123;
|
|
|
|
Issue a warning and move ON condition predicates back to the WHERE.
|
|
*/
|
|
List_iterator_fast it(tab[i].on_conds);
|
|
StringBuffer<STRING_BUFFER_USUAL_SIZE> expr;
|
|
Item *item;
|
|
while ((item= it++))
|
|
{
|
|
expr.set("", 0, system_charset_info);
|
|
item->print(&expr, QT_ORDINARY);
|
|
push_warning_printf(thd, Sql_condition::WARN_LEVEL_WARN,
|
|
WARN_ORA_JOIN_IGNORED,
|
|
ER_THD(thd, WARN_ORA_JOIN_IGNORED),
|
|
expr.c_ptr());
|
|
|
|
// The item will be moved into the WHERE clause
|
|
item->walk(&Item::remove_ora_join_processor, 0, 0);
|
|
}
|
|
return_to_where.append(&tab[i].on_conds);
|
|
tab[i].on_conds.empty();
|
|
}
|
|
/*
|
|
Sort the outgoing edges in reverse order (those that should come
|
|
first are the last). This is because we will do this:
|
|
|
|
for each T in tab[i].inner_side
|
|
insert_element_after(tab[i], T);
|
|
|
|
after which the elements will be in the right order.
|
|
*/
|
|
if (tab[i].inner_side.elements > 1)
|
|
bubble_sort<table_pos>(&tab[i].inner_side, table_pos_sort, NULL);
|
|
|
|
#ifndef DBUG_OFF
|
|
dbug_trace_table_pos(tab + i);
|
|
dbug_trace_table_list(tab[i].table);
|
|
#endif
|
|
}
|
|
|
|
/*
|
|
Order the tables according to the "LEFT JOIN syntax order".
|
|
*/
|
|
table_pos *list= NULL;
|
|
table_pos *end= NULL;
|
|
uint processed= 0;
|
|
i= 0;
|
|
do
|
|
{
|
|
// Find the first independent table
|
|
for(;
|
|
i < n_tables && (tab[i].processed || tab[i].outer_side.elements != 0);
|
|
i++);
|
|
if (i >= n_tables)
|
|
break;
|
|
|
|
// Set (list, end) to point to the list we've collected so far
|
|
if (list == NULL)
|
|
list= tab + i;
|
|
else
|
|
{
|
|
if (end == NULL)
|
|
end= list;
|
|
while(end->next) end= end->next; // go to the new end
|
|
}
|
|
|
|
// Process "sub-graph" with this independent is top of one of branches
|
|
insert_element_after(end, tab + i, &processed);
|
|
process_inner_relations(thd, tab + i, &processed, n_tables);
|
|
} while (i < n_tables);
|
|
|
|
if (processed < n_tables)
|
|
{
|
|
/*
|
|
Some tables are not processed but they all have incoming edges.
|
|
This can only happen if there are circular dependencies:
|
|
|
|
t1 -> t2 -> t3 -+
|
|
^ |
|
|
| |
|
|
+--------------+
|
|
*/
|
|
my_error(ER_INVALID_USE_OF_ORA_JOIN_CYCLE, MYF(0));
|
|
DBUG_RETURN(TRUE);
|
|
}
|
|
|
|
#ifndef DBUG_OFF
|
|
for (table_pos *t= list; t != NULL; t= t->next)
|
|
dbug_trace_table_pos(t);
|
|
#endif
|
|
|
|
|
|
/*
|
|
Now we build new permanent list of table according to our new order
|
|
|
|
table1 [left inner] join table2 ... [left inner] join tableN
|
|
|
|
which parses in:
|
|
|
|
top_join_list of SELECT_LEX
|
|
|
|
|
nest_tableN-1 --nested_join-> NESTED_JOIN_N-1
|
|
join_list of NESTED_JOIN_N-1
|
|
/\
|
|
tableN nest_tableN-2
|
|
...
|
|
join_list of of NESTED_JOIN_2
|
|
/\
|
|
table3 nest_table1 --nested_join-> NESTED_JOIN_1
|
|
join_list of NESTED_JOIN1
|
|
/\
|
|
table2 table1
|
|
|
|
*/
|
|
TABLE_LIST *new_from= list->table;
|
|
if (n_tables > 1) // nothing to do with only one table
|
|
{
|
|
// changes are permanent
|
|
Query_arena_stmt on_stmt_arena(thd);
|
|
TABLE_LIST *prev_table= list->table;
|
|
TABLE_LIST *nest_table_lists;
|
|
NESTED_JOIN *nested_joins;
|
|
if (!(nest_table_lists=
|
|
(TABLE_LIST*)thd->calloc(ALIGN_SIZE(sizeof(TABLE_LIST)) *
|
|
(n_tables - 1) +
|
|
ALIGN_SIZE(sizeof(NESTED_JOIN)) *
|
|
(n_tables - 1))))
|
|
{
|
|
DBUG_RETURN(TRUE); // EOM
|
|
}
|
|
nested_joins= (NESTED_JOIN *)(((char*)nest_table_lists) +
|
|
ALIGN_SIZE(sizeof(TABLE_LIST)) *
|
|
(n_tables - 1));
|
|
for (uint i= 0; i < n_tables - 1; i++)
|
|
{
|
|
nest_table_lists[i].nested_join= nested_joins + i;
|
|
}
|
|
nested_joins[0].join_list.empty();
|
|
nested_joins[0].join_list.push_front(list->table);
|
|
DBUG_ASSERT(list->table->embedding == NULL);
|
|
list->table->embedding= nest_table_lists;
|
|
list->table->join_list= &nested_joins->join_list;
|
|
DBUG_ASSERT(list->table->outer_join == 0);
|
|
uint i;
|
|
table_pos *curr;
|
|
for (i=0, curr= list->next; curr; i++, curr= curr->next)
|
|
{
|
|
DBUG_ASSERT(i <= n_tables - 2);
|
|
TABLE_LIST *next_embedding= ((i < n_tables - 2) ?
|
|
nest_table_lists + (i+1) :
|
|
NULL);
|
|
// join type
|
|
DBUG_ASSERT(curr->table->outer_join == 0);
|
|
DBUG_ASSERT(curr->table->on_expr == 0);
|
|
if (curr->outer_side.elements)
|
|
{
|
|
DBUG_ASSERT(curr->on_conds.elements > 0);
|
|
curr->table->outer_join|=JOIN_TYPE_LEFT;
|
|
// update maybe_null which was previously set in setup_table_map()
|
|
if (curr->table->table)
|
|
curr->table->table->maybe_null= JOIN_TYPE_LEFT;
|
|
if (curr->on_conds.elements == 1)
|
|
{
|
|
curr->table->on_expr= curr->on_conds.head();
|
|
}
|
|
else
|
|
{
|
|
Item *item= new(thd->mem_root) Item_cond_and(thd, curr->on_conds);
|
|
if (!item)
|
|
DBUG_RETURN(TRUE);
|
|
item->top_level_item();
|
|
curr->table->on_expr= item;
|
|
/* setup_on_expr() will call fix_fields() for on_expr */
|
|
}
|
|
}
|
|
else
|
|
{
|
|
DBUG_ASSERT(curr->on_conds.elements == 0);
|
|
}
|
|
|
|
// add real table
|
|
prev_table->next_local= curr->table;
|
|
nested_joins[i].join_list.push_front(curr->table);
|
|
DBUG_ASSERT(curr->table->embedding == NULL);
|
|
curr->table->embedding= nest_table_lists + i;
|
|
curr->table->join_list= &nested_joins[i].join_list;
|
|
// prepare fake table
|
|
nest_table_lists[i].alias= {STRING_WITH_LEN("(nest_last_join)")};
|
|
nest_table_lists[i].embedding= next_embedding;
|
|
|
|
if (next_embedding)
|
|
{
|
|
nested_joins[i+1].join_list.empty();
|
|
nested_joins[i+1].join_list.push_front(nest_table_lists + i);
|
|
nest_table_lists[i].join_list= &nested_joins[i + 1].join_list;
|
|
}
|
|
else
|
|
{
|
|
DBUG_ASSERT(i == n_tables - 2);
|
|
// all tables should be there because query was without JOIN
|
|
// operators except oracle ones
|
|
DBUG_ASSERT(select_join_list->elements == n_tables);
|
|
select_join_list->empty();
|
|
select_join_list->push_front(nest_table_lists + i);
|
|
nest_table_lists[i].join_list= select_join_list;
|
|
}
|
|
|
|
prev_table= curr->table;
|
|
}
|
|
prev_table->next_local= NULL;
|
|
select_table_list.first= new_from;
|
|
select_table_list.next= &prev_table->next_local;
|
|
}
|
|
|
|
DBUG_PRINT("INFO", ("new FROM clause: %p", new_from));
|
|
#ifndef DBUG_OFF
|
|
for (TABLE_LIST *t= new_from; t; t= t->next_local)
|
|
{
|
|
dbug_trace_table_list(t);
|
|
}
|
|
#endif
|
|
|
|
if (add_conditions_to_where(thd, conds, std::move(return_to_where)))
|
|
DBUG_RETURN(TRUE);
|
|
|
|
// Refresh nullability of already fixed parts:
|
|
|
|
// WHERE
|
|
if (conds[0])
|
|
{
|
|
conds[0]->update_used_tables();
|
|
conds[0]->walk(&Item::add_maybe_null_after_ora_join_processor, 0, 0);
|
|
}
|
|
// SELECT list and hidden fields
|
|
if (all_fields)
|
|
{
|
|
List_iterator<Item> it(*all_fields);
|
|
Item *item;
|
|
while((item= it++))
|
|
{
|
|
item->update_used_tables();
|
|
item->walk(&Item::add_maybe_null_after_ora_join_processor, 0, 0);
|
|
}
|
|
}
|
|
// parts of WHERE moved to ON (original ONs will be fixed later)
|
|
for (i= 0; i < n_tables; i++)
|
|
{
|
|
// we have to count becaust this lists are included in other lists
|
|
List_iterator<Item> it(*all_fields);
|
|
Item *item;
|
|
for (uint j= 0; j < tab[i].on_conds.elements && (item= it++); j++)
|
|
{
|
|
item->update_used_tables();
|
|
item->walk(&Item::add_maybe_null_after_ora_join_processor, 0, 0);
|
|
}
|
|
}
|
|
|
|
DBUG_RETURN(FALSE);
|
|
}
|
|
|
|
|
|
/*
|
|
@brief
|
|
Add conditions from return_to_where into *conds.
|
|
Then, normalize *conds: it can be an Item_cond_and with one or zero
|
|
children.
|
|
|
|
@return
|
|
false OK
|
|
true Fatal error
|
|
*/
|
|
|
|
static bool add_conditions_to_where(THD *thd, Item **conds,
|
|
List<Item> &&return_to_where)
|
|
{
|
|
// Make changes on statement's mem_root
|
|
Query_arena_stmt on_stmt_arena(thd);
|
|
uint number_of_cond_parts= return_to_where.elements;
|
|
if ((*conds) != NULL)
|
|
{
|
|
if (is_cond_and(*conds))
|
|
{
|
|
uint elements= ((Item_cond_and *)(*conds))->argument_list()->elements;
|
|
switch (elements)
|
|
{
|
|
case 0:
|
|
(*conds)= NULL;
|
|
break;
|
|
case 1:
|
|
(*conds)= ((Item_cond_and *)(*conds))->argument_list()->head();
|
|
number_of_cond_parts++;
|
|
break;
|
|
default:
|
|
number_of_cond_parts+= elements;
|
|
}
|
|
}
|
|
else
|
|
number_of_cond_parts++;
|
|
}
|
|
|
|
if (number_of_cond_parts == 0)
|
|
{
|
|
/* Nothing is left in the WHERE */
|
|
DBUG_ASSERT((*conds) == NULL);
|
|
}
|
|
else if (number_of_cond_parts == 1)
|
|
{
|
|
if ((*conds) == NULL)
|
|
{
|
|
DBUG_ASSERT(return_to_where.elements == 1);
|
|
(*conds)= return_to_where.head();
|
|
}
|
|
else
|
|
{
|
|
// There is one remaining condition, it's in *conds.
|
|
DBUG_ASSERT(return_to_where.elements == 0);
|
|
DBUG_ASSERT((*conds) != NULL);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if ((*conds) == NULL || !is_cond_and(*conds))
|
|
{
|
|
if (*conds)
|
|
return_to_where.push_back(*conds);
|
|
}
|
|
else
|
|
return_to_where.append(((Item_cond_and *)(*conds))->argument_list());
|
|
|
|
if (!((*conds)= new(thd->mem_root) Item_cond_and(thd, return_to_where)))
|
|
return true;
|
|
(*conds)->top_level_item();
|
|
if ((*conds)->fix_fields(thd, conds))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|