/**
Retrieve records ends with a given beginning from the result of a join.
SYNPOSIS
sub_select()
join pointer to the structure providing all context info for the query
join_tab the first next table of the execution plan to be retrieved
end_records true when we need to perform final steps of retrival
DESCRIPTION
For a given partial join record consisting of records from the tables
preceding the table join_tab in the execution plan, the function
retrieves all matching full records from the result set and
send them to the result set stream.
@note
The function effectively implements the final (n-k) nested loops
of nested loops join algorithm, where k is the ordinal number of
the join_tab table and n is the total number of tables in the join query.
It performs nested loops joins with all conjunctive predicates from
the where condition pushed as low to the tables as possible.
E.g. for the query
@code
SELECT * FROM t1,t2,t3
WHERE t1.a=t2.a AND t2.b=t3.b AND t1.a BETWEEN 5 AND 9
@endcode
the predicate (t1.a BETWEEN 5 AND 9) will be pushed to table t1,
given the selected plan prescribes to nest retrievals of the
joined tables in the following order: t1,t2,t3.
A pushed down predicate are attached to the table which it pushed to,
at the field join_tab->cond.
When executing a nested loop of level k the function runs through
the rows of 'join_tab' and for each row checks the pushed condition
attached to the table.
If it is false the function moves to the next row of the
table. If the condition is true the function recursively executes (n-k-1)
remaining embedded nested loops.
The situation becomes more complicated if outer joins are involved in
the execution plan. In this case the pushed down predicates can be
checked only at certain conditions.
Suppose for the query
@code
SELECT * FROM t1 LEFT JOIN (t2,t3) ON t3.a=t1.a
WHERE t1>2 AND (t2.b>5 OR t2.b IS NULL)
@endcode
the optimizer has chosen a plan with the table order t1,t2,t3.
The predicate P1=t1>2 will be pushed down to the table t1, while the
predicate P2=(t2.b>5 OR t2.b IS NULL) will be attached to the table
t2. But the second predicate can not be unconditionally tested right
after a row from t2 has been read. This can be done only after the
first row with t3.a=t1.a has been encountered.
Thus, the second predicate P2 is supplied with a guarded value that are
stored in the field 'found' of the first inner table for the outer join
(table t2). When the first row with t3.a=t1.a for the current row
of table t1 appears, the value becomes true. For now on the predicate
is evaluated immediately after the row of table t2 has been read.
When the first row with t3.a=t1.a has been encountered all
conditions attached to the inner tables t2,t3 must be evaluated.
Only when all of them are true the row is sent to the output stream.
If not, the function returns to the lowest nest level that has a false
attached condition.
The predicates from on expressions are also pushed down. If in the
the above example the on expression were (t3.a=t1.a AND t2.a=t1.a),
then t1.a=t2.a would be pushed down to table t2, and without any
guard.
If after the run through all rows of table t2, the first inner table
for the outer join operation, it turns out that no matches are
found for the current row of t1, then current row from table t1
is complemented by nulls for t2 and t3. Then the pushed down predicates
are checked for the composed row almost in the same way as it had
been done for the first row with a match. The only difference is
the predicates from on expressions are not checked.
@par
@b IMPLEMENTATION
@par
The function forms output rows for a current partial join of k
tables tables recursively.
For each partial join record ending with a certain row from
join_tab it calls sub_select that builds all possible matching
tails from the result set.
To be able check predicates conditionally items of the class
Item_func_trig_cond are employed.
An object of this class is constructed from an item of class COND
and a pointer to a guarding boolean variable.
When the value of the guard variable is true the value of the object
is the same as the value of the predicate, otherwise it's just returns
true.
To carry out a return to a nested loop level of join table t the pointer
to t is remembered in the field 'return_tab' of the join structure.
Consider the following query:
@code
SELECT * FROM t1,
LEFT JOIN
(t2, t3 LEFT JOIN (t4,t5) ON t5.a=t3.a)
ON t4.a=t2.a
WHERE (t2.b=5 OR t2.b IS NULL) AND (t4.b=2 OR t4.b IS NULL)
@endcode
Suppose the chosen execution plan dictates the order t1,t2,t3,t4,t5
and suppose for a given joined rows from tables t1,t2,t3 there are
no rows in the result set yet.
When first row from t5 that satisfies the on condition
t5.a=t3.a is found, the pushed down predicate t4.b=2 OR t4.b IS NULL
becomes 'activated', as well the predicate t4.a=t2.a. But
the predicate (t2.b=5 OR t2.b IS NULL) can not be checked until
t4.a=t2.a becomes true.
In order not to re-evaluate the predicates that were already evaluated
as attached pushed down predicates, a pointer to the the first
most inner unmatched table is maintained in join_tab->first_unmatched.
Thus, when the first row from t5 with t5.a=t3.a is found
this pointer for t5 is changed from t4 to t2.
@par
@b STRUCTURE @b NOTES
@par
join_tab->first_unmatched points always backwards to the first inner
table of the embedding nested join, if any.
@param join pointer to the structure providing all context info for
the query
@param join_tab the first next table of the execution plan to be retrieved
@param end_records true when we need to perform final steps of retrival
@return
return one of enum_nested_loop_state, except NESTED_LOOP_NO_MORE_ROWS.
*/
enum_nested_loop_state
sub_select(JOIN *join, QEP_TAB *const qep_tab,bool end_of_records)
