summaryrefslogtreecommitdiffstats
path: root/sql/opt_subselect.cc
diff options
context:
space:
mode:
Diffstat (limited to 'sql/opt_subselect.cc')
-rw-r--r--sql/opt_subselect.cc7147
1 files changed, 7147 insertions, 0 deletions
diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc
new file mode 100644
index 00000000..dd981a8f
--- /dev/null
+++ b/sql/opt_subselect.cc
@@ -0,0 +1,7147 @@
+/*
+ Copyright (c) 2010, 2020, 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 */
+
+/**
+ @file
+
+ @brief
+ Semi-join subquery optimizations code
+
+*/
+
+#ifdef USE_PRAGMA_IMPLEMENTATION
+#pragma implementation // gcc: Class implementation
+#endif
+
+#include "mariadb.h"
+#include "sql_base.h"
+#include "sql_const.h"
+#include "sql_select.h"
+#include "filesort.h"
+#include "opt_subselect.h"
+#include "sql_test.h"
+#include <my_bit.h>
+#include "opt_trace.h"
+
+/*
+ This file contains optimizations for semi-join subqueries.
+
+ Contents
+ --------
+ 1. What is a semi-join subquery
+ 2. General idea about semi-join execution
+ 2.1 Correlated vs uncorrelated semi-joins
+ 2.2 Mergeable vs non-mergeable semi-joins
+ 3. Code-level view of semi-join processing
+ 3.1 Conversion
+ 3.1.1 Merged semi-join TABLE_LIST object
+ 3.1.2 Non-merged semi-join data structure
+ 3.2 Semi-joins and query optimization
+ 3.2.1 Non-merged semi-joins and join optimization
+ 3.2.2 Merged semi-joins and join optimization
+ 3.3 Semi-joins and query execution
+
+ 1. What is a semi-join subquery
+ -------------------------------
+ We use this definition of semi-join:
+
+ outer_tbl SEMI JOIN inner_tbl ON cond = {set of outer_tbl.row such that
+ exist inner_tbl.row, for which
+ cond(outer_tbl.row,inner_tbl.row)
+ is satisfied}
+
+ That is, semi-join operation is similar to inner join operation, with
+ exception that we don't care how many matches a row from outer_tbl has in
+ inner_tbl.
+
+ In SQL terms: a semi-join subquery is an IN subquery that is an AND-part of
+ the WHERE/ON clause.
+
+ 2. General idea about semi-join execution
+ -----------------------------------------
+ We can execute semi-join in a way similar to inner join, with exception that
+ we need to somehow ensure that we do not generate record combinations that
+ differ only in rows of inner tables.
+ There is a number of different ways to achieve this property, implemented by
+ a number of semi-join execution strategies.
+ Some strategies can handle any semi-joins, other can be applied only to
+ semi-joins that have certain properties that are described below:
+
+ 2.1 Correlated vs uncorrelated semi-joins
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ Uncorrelated semi-joins are special in the respect that they allow to
+ - execute the subquery (possible as it's uncorrelated)
+ - somehow make sure that generated set does not have duplicates
+ - perform an inner join with outer tables.
+
+ or, rephrasing in SQL form:
+
+ SELECT ... FROM ot WHERE ot.col IN (SELECT it.col FROM it WHERE uncorr_cond)
+ ->
+ SELECT ... FROM ot JOIN (SELECT DISTINCT it.col FROM it WHERE uncorr_cond)
+
+ 2.2 Mergeable vs non-mergeable semi-joins
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ Semi-join operation has some degree of commutability with inner join
+ operation: we can join subquery's tables with ouside table(s) and eliminate
+ duplicate record combination after that:
+
+ ot1 JOIN ot2 SEMI_JOIN{it1,it2} (it1 JOIN it2) ON sjcond(ot2,it*) ->
+ |
+ +-------------------------------+
+ v
+ ot1 SEMI_JOIN{it1,it2} (it1 JOIN it2 JOIN ot2) ON sjcond(ot2,it*)
+
+ In order for this to work, subquery's top-level operation must be join, and
+ grouping or ordering with limit (grouping or ordering with limit are not
+ commutative with duplicate removal). In other words, the conversion is
+ possible when the subquery doesn't have GROUP BY clause, any aggregate
+ functions*, or ORDER BY ... LIMIT clause.
+
+ Definitions:
+ - Subquery whose top-level operation is a join is called *mergeable semi-join*
+ - All other kinds of semi-join subqueries are considered non-mergeable.
+
+ *- this requirement is actually too strong, but its exceptions are too
+ complicated to be considered here.
+
+ 3. Code-level view of semi-join processing
+ ------------------------------------------
+
+ 3.1 Conversion and pre-optimization data structures
+ ---------------------------------------------------
+ * When doing JOIN::prepare for the subquery, we detect that it can be
+ converted into a semi-join and register it in parent_join->sj_subselects
+
+ * At the start of parent_join->optimize(), the predicate is converted into
+ a semi-join node. A semi-join node is a TABLE_LIST object that is linked
+ somewhere in parent_join->join_list (either it is just present there, or
+ it is a descendant of some of its members).
+
+ There are two kinds of semi-joins:
+ - Merged semi-joins
+ - Non-merged semi-joins
+
+ 3.1.1 Merged semi-join TABLE_LIST object
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ Merged semi-join object is a TABLE_LIST that contains a sub-join of
+ subquery tables and the semi-join ON expression (in this respect it is
+ very similar to nested outer join representation)
+ Merged semi-join represents this SQL:
+
+ ... SEMI JOIN (inner_tbl1 JOIN ... JOIN inner_tbl_n) ON sj_on_expr
+
+ Semi-join objects of this kind have TABLE_LIST::sj_subq_pred set.
+
+ 3.1.2 Non-merged semi-join data structure
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ Non-merged semi-join object is a leaf TABLE_LIST object that has a subquery
+ that produces rows. It is similar to a base table and represents this SQL:
+
+ ... SEMI_JOIN (SELECT non_mergeable_select) ON sj_on_expr
+
+ Subquery items that were converted into semi-joins are removed from the WHERE
+ clause. (They do remain in PS-saved WHERE clause, and they replace themselves
+ with Item_int(1) on subsequent re-executions).
+
+ 3.2 Semi-joins and join optimization
+ ------------------------------------
+
+ 3.2.1 Non-merged semi-joins and join optimization
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ For join optimization purposes, non-merged semi-join nests are similar to
+ base tables. Each such nest is represented by one one JOIN_TAB, which has
+ two possible access strategies:
+ - full table scan (representing SJ-Materialization-Scan strategy)
+ - eq_ref-like table lookup (representing SJ-Materialization-Lookup)
+
+ Unlike regular base tables, non-merged semi-joins have:
+ - non-zero JOIN_TAB::startup_cost, and
+ - join_tab->table->is_filled_at_execution()==TRUE, which means one
+ cannot do const table detection, range analysis or other dataset-dependent
+ optimizations.
+ Instead, get_delayed_table_estimates() will run optimization for the
+ subquery and produce an E(materialized table size).
+
+ 3.2.2 Merged semi-joins and join optimization
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ - optimize_semijoin_nests() does pre-optimization
+ - during join optimization, the join has one JOIN_TAB (or is it POSITION?)
+ array, and suffix-based detection is used, see advance_sj_state()
+ - after join optimization is done, get_best_combination() switches
+ the data-structure to prefix-based, multiple JOIN_TAB ranges format.
+
+ 3.3 Semi-joins and query execution
+ ----------------------------------
+ * Join executor has hooks for all semi-join strategies.
+ TODO elaborate.
+
+*/
+
+/*
+EqualityPropagationAndSjmNests
+******************************
+
+Equalities are used for:
+P1. Equality propagation
+P2. Equality substitution [for a certain join order]
+
+The equality propagation is not affected by SJM nests. In fact, it is done
+before we determine the execution plan, i.e. before we even know we will use
+SJM-nests for execution.
+
+The equality substitution is affected.
+
+Substitution without SJMs
+=========================
+When one doesn't have SJM nests, tables have a strict join order:
+
+ --------------------------------->
+ t1 -- t2 -- t3 -- t4 --- t5
+
+
+ ? ^
+ \
+ --(part-of-WHERE)
+
+
+parts WHERE/ON and ref. expressions are attached at some point along the axis.
+Expression is allowed to refer to a table column if the table is to the left of
+the attachment point. For any given expression, we have a goal:
+
+ "Move leftmost allowed attachment point as much as possible to the left"
+
+Substitution with SJMs - task setting
+=====================================
+
+When SJM nests are present, there is no global strict table ordering anymore:
+
+
+ --------------------------------->
+
+ ot1 -- ot2 --- sjm -- ot4 --- ot5
+ |
+ | Main execution
+ - - - - - - - - - - - - - - - - - - - - - - - -
+ | Materialization
+ it1 -- it2 --/
+
+
+Besides that, we must take into account that
+ - values for outer table columns, otN.col, are inaccessible at
+ materialization step (SJM-RULE)
+ - values for inner table columns, itN.col, are inaccessible at Main execution
+ step, except for SJ-Materialization-Scan and columns that are in the
+ subquery's select list. (SJM-RULE)
+
+Substitution with SJMs - solution
+=================================
+
+First, we introduce global strict table ordering like this:
+
+ ot1 - ot2 --\ /--- ot3 -- ot5
+ \--- it1 --- it2 --/
+
+Now, let's see how to meet (SJM-RULE).
+
+SJ-Materialization is only applicable for uncorrelated subqueries. From this, it
+follows that any multiple equality will either
+1. include only columns of outer tables, or
+2. include only columns of inner tables, or
+3. include columns of inner and outer tables, joined together through one
+ of IN-equalities.
+
+Cases #1 and #2 can be handled in the same way as with regular inner joins.
+
+Case #3 requires special handling, so that we don't construct violations of
+(SJM-RULE). Let's consider possible ways to build violations.
+
+Equality propagation starts with the clause in this form
+
+ top_query_where AND subquery_where AND in_equalities
+
+First, it builds multi-equalities. It can also build a mixed multi-equality
+
+ multiple-equal(ot1.col, ot2.col, ... it1.col, itN.col)
+
+Multi-equalities are pushed down the OR-clauses in top_query_where and in
+subquery_where, so it's possible that clauses like this one are built:
+
+ subquery_cond OR (multiple-equal(it1.col, ot1.col,...) AND ...)
+ ^^^^^^^^^^^^^ \
+ | this must be evaluated
+ \- can only be evaluated at the main phase.
+ at the materialization phase
+
+Finally, equality substitution is started. It does two operations:
+
+
+1. Field reference substitution
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+(In the code, this is Item_field::replace_equal_field)
+
+This is a process of replacing each reference to "tblX.col"
+with the first element of the multi-equality. (REF-SUBST-ORIG)
+
+This behaviour can cause problems with Semi-join nests. Suppose, we have a
+condition:
+
+ func(it1.col, it2.col)
+
+and a multi-equality(ot1.col, it1.col). Then, reference to "it1.col" will be
+replaced with "ot1.col", constructing a condition
+
+ func(ot1.col, it2.col)
+
+which will be a violation of (SJM-RULE).
+
+In order to avoid this, (REF-SUBST-ORIG) is amended as follows:
+
+- references to tables "itX.col" that are inner wrt some SJM nest, are
+ replaced with references to the first inner table from the same SJM nest.
+
+- references to top-level tables "otX.col" are replaced with references to
+ the first element of the multi-equality, no matter if that first element is
+ a column of a top-level table or of table from some SJM nest.
+ (REF-SUBST-SJM)
+
+ The case where the first element is a table from an SJM nest $SJM is ok,
+ because it can be proven that $SJM uses SJ-Materialization-Scan, and
+ "unpacks" correct column values to the first element during the main
+ execution phase.
+
+2. Item_equal elimination
+~~~~~~~~~~~~~~~~~~~~~~~~~
+(In the code: eliminate_item_equal) This is a process of taking
+
+ multiple-equal(a,b,c,d,e)
+
+and replacing it with an equivalent expression which is an AND of pair-wise
+equalities:
+
+ a=b AND a=c AND ...
+
+The equalities are picked such that for any given join prefix (t1,t2...) the
+subset of equalities that can be evaluated gives the most restrictive
+filtering.
+
+Without SJM nests, it is sufficient to compare every multi-equality member
+with the first one:
+
+ elem1=elem2 AND elem1=elem3 AND elem1=elem4 ...
+
+When SJM nests are present, we should take care not to construct equalities
+that violate the (SJM-RULE). This is achieved by generating separate sets of
+equalites for top-level tables and for inner tables. That is, for the join
+order
+
+ ot1 - ot2 --\ /--- ot3 -- ot5
+ \--- it1 --- it2 --/
+
+we will generate
+ ot1.col=ot2.col
+ ot1.col=ot3.col
+ ot1.col=ot5.col
+ it2.col=it1.col
+
+
+2.1 The problem with Item_equals and ORs
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+As has been mentioned above, multiple equalities are pushed down into OR
+clauses, possibly building clauses like this:
+
+ func(it.col2) OR multiple-equal(it1.col1, it1.col2, ot1.col) (1)
+
+where the first part of the clause has references to inner tables, while the
+second has references to the top-level tables, which is a violation of
+(SJM-RULE).
+
+AND-clauses of this kind do not create problems, because make_cond_for_table()
+will take them apart. OR-clauses will not be split. It is possible to
+split-out the part that's dependent on the inner table:
+
+ func(it.col2) OR it1.col1=it1.col2
+
+but this is a less-restrictive condition than condition (1). Current execution
+scheme will still try to generate the "remainder" condition:
+
+ func(it.col2) OR it1.col1=ot1.col
+
+which is a violation of (SJM-RULE).
+
+QQ: "ot1.col=it1.col" is checked at the upper level. Why was it not removed
+here?
+AA: because has a proper subset of conditions that are found on this level.
+ consider a join order of ot, sjm(it)
+ and a condition
+ ot.col=it.col AND ( ot.col=it.col='foo' OR it.col2='bar')
+
+ we will produce:
+ table ot: nothing
+ table it: ot.col=it.col AND (ot.col='foo' OR it.col2='bar')
+ ^^^^ ^^^^^^^^^^^^^^^^
+ | \ the problem is that
+ | this part condition didnt
+ | receive a substitution
+ |
+ +--- it was correct to subst, 'ot' is
+ the left-most.
+
+
+Does it make sense to push "inner=outer" down into ORs?
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Yes. Consider the query:
+
+ select * from ot
+ where ot.col in (select it.col from it where (it.col='foo' OR it.col='bar'))
+
+here, it may be useful to infer that
+
+ (ot.col='foo' OR ot.col='bar') (CASE-FOR-SUBST)
+
+and attach that condition to the table 'ot'.
+
+Possible solutions for Item_equals and ORs
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Solution #1
+~~~~~~~~~~~
+Let make_cond_for_table() chop analyze the OR clauses it has produced and
+discard them if they violate (SJM-RULE). This solution would allow to handle
+cases like (CASE-FOR-SUBST) at the expense of making semantics of
+make_cond_for_table() complicated.
+
+Solution #2
+~~~~~~~~~~~
+Before the equality propagation phase, none of the OR clauses violate the
+(SJM-RULE). This way, if we remember which tables the original equality
+referred to, we can only generate equalities that refer to the outer (or inner)
+tables. Note that this will disallow handling of cases like (CASE-FOR-SUBST).
+
+Currently, solution #2 is implemented.
+*/
+
+LEX_CSTRING weedout_key= {STRING_WITH_LEN("weedout_key")};
+
+static
+bool subquery_types_allow_materialization(THD *thd, Item_in_subselect *in_subs);
+static bool replace_where_subcondition(JOIN *, Item **, Item *, Item *, bool);
+static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
+ void *arg);
+static void reset_equality_number_for_subq_conds(Item * cond);
+static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred);
+static bool convert_subq_to_jtbm(JOIN *parent_join,
+ Item_in_subselect *subq_pred, bool *remove);
+static TABLE_LIST *alloc_join_nest(THD *thd);
+static uint get_tmp_table_rec_length(Ref_ptr_array p_list, uint elements);
+bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables);
+static SJ_MATERIALIZATION_INFO *
+at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
+ uint idx, bool *loose_scan);
+static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
+ Item_in_subselect *subq_pred);
+static bool remove_sj_conds(THD *thd, Item **tree);
+static bool is_cond_sj_in_equality(Item *item);
+static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab);
+static Item *remove_additional_cond(Item* conds);
+static void remove_subq_pushed_predicates(JOIN *join, Item **where);
+
+enum_nested_loop_state
+end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
+
+
+/*
+ Check if Materialization strategy is allowed for given subquery predicate.
+
+ @param thd Thread handle
+ @param in_subs The subquery predicate
+ @param child_select The select inside predicate (the function will
+ check it is the only one)
+
+ @return TRUE - Materialization is applicable
+ FALSE - Otherwise
+*/
+
+bool is_materialization_applicable(THD *thd, Item_in_subselect *in_subs,
+ st_select_lex *child_select)
+{
+ st_select_lex_unit* parent_unit= child_select->master_unit();
+ /*
+ Check if the subquery predicate can be executed via materialization.
+ The required conditions are:
+ 0. The materialization optimizer switch was set.
+ 1. Subquery is a single SELECT (not a UNION).
+ TODO: this is a limitation that can be fixed
+ 2. Subquery is not a table-less query. In this case there is no
+ point in materializing.
+ 2A The upper query is not a table-less SELECT ... FROM DUAL. We
+ can't do materialization for SELECT .. FROM DUAL because it
+ does not call setup_subquery_materialization(). We could make
+ SELECT ... FROM DUAL call that function but that doesn't seem
+ to be the case that is worth handling.
+ 3. Either the subquery predicate is a top-level predicate, or at
+ least one partial match strategy is enabled. If no partial match
+ strategy is enabled, then materialization cannot be used for
+ non-top-level queries because it cannot handle NULLs correctly.
+ 4. Subquery is non-correlated
+ TODO:
+ This condition is too restrictive (limitation). It can be extended to:
+ (Subquery is non-correlated ||
+ Subquery is correlated to any query outer to IN predicate ||
+ (Subquery is correlated to the immediate outer query &&
+ Subquery !contains {GROUP BY, ORDER BY [LIMIT],
+ aggregate functions}) && subquery predicate is not under "NOT IN"))
+ 5. Subquery does not contain recursive references
+
+ A note about prepared statements: we want the if-branch to be taken on
+ PREPARE and each EXECUTE. The rewrites are only done once, but we need
+ select_lex->sj_subselects list to be populated for every EXECUTE.
+
+ */
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION) && // 0
+ !child_select->is_part_of_union() && // 1
+ parent_unit->first_select()->leaf_tables.elements && // 2
+ child_select->outer_select() &&
+ child_select->outer_select()->table_list.first && // 2A
+ subquery_types_allow_materialization(thd, in_subs) &&
+ (in_subs->is_top_level_item() || //3
+ optimizer_flag(thd,
+ OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) || //3
+ optimizer_flag(thd,
+ OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)) && //3
+ !in_subs->is_correlated && //4
+ !in_subs->with_recursive_reference) //5
+ {
+ return TRUE;
+ }
+ return FALSE;
+}
+
+
+/*
+ Check if we need JOIN::prepare()-phase subquery rewrites and if yes, do them
+
+ SYNOPSIS
+ check_and_do_in_subquery_rewrites()
+ join Subquery's join
+
+ DESCRIPTION
+ Check if we need to do
+ - subquery -> mergeable semi-join rewrite
+ - if the subquery can be handled with materialization
+ - 'substitution' rewrite for table-less subqueries like "(select 1)"
+ - IN->EXISTS rewrite
+ and, depending on the rewrite, either do it, or record it to be done at a
+ later phase.
+
+ RETURN
+ 0 - OK
+ Other - Some sort of query error
+*/
+
+int check_and_do_in_subquery_rewrites(JOIN *join)
+{
+ THD *thd=join->thd;
+ st_select_lex *select_lex= join->select_lex;
+ st_select_lex_unit* parent_unit= select_lex->master_unit();
+ DBUG_ENTER("check_and_do_in_subquery_rewrites");
+
+ /*
+ IN/ALL/ANY rewrites are not applicable for so called fake select
+ (this select exists only to filter results of union if it is needed).
+ */
+ if (select_lex == select_lex->master_unit()->fake_select_lex)
+ DBUG_RETURN(0);
+
+ /*
+ If
+ 1) this join is inside a subquery (of any type except FROM-clause
+ subquery) and
+ 2) we aren't just normalizing a VIEW
+
+ Then perform early unconditional subquery transformations:
+ - Convert subquery predicate into semi-join, or
+ - Mark the subquery for execution using materialization, or
+ - Perform IN->EXISTS transformation, or
+ - Perform more/less ALL/ANY -> MIN/MAX rewrite
+ - Substitute trivial scalar-context subquery with its value
+
+ TODO: for PS, make the whole block execute only on the first execution
+ */
+ Item_subselect *subselect;
+ if (!thd->lex->is_view_context_analysis() && // (1)
+ (subselect= parent_unit->item)) // (2)
+ {
+ Item_in_subselect *in_subs= NULL;
+ Item_allany_subselect *allany_subs= NULL;
+ Item_subselect::subs_type substype= subselect->substype();
+ switch (substype) {
+ case Item_subselect::IN_SUBS:
+ in_subs= subselect->get_IN_subquery();
+ break;
+ case Item_subselect::ALL_SUBS:
+ case Item_subselect::ANY_SUBS:
+ DBUG_ASSERT(subselect->get_IN_subquery());
+ allany_subs= (Item_allany_subselect *)subselect;
+ break;
+ default:
+ break;
+ }
+
+ /*
+ Try removing "ORDER BY" or even "ORDER BY ... LIMIT" from certain kinds
+ of subqueries. The removal might enable further transformations.
+ */
+ if (substype == Item_subselect::IN_SUBS ||
+ substype == Item_subselect::EXISTS_SUBS ||
+ substype == Item_subselect::ANY_SUBS ||
+ substype == Item_subselect::ALL_SUBS)
+ {
+ // (1) - ORDER BY without LIMIT can be removed from IN/EXISTS subqueries
+ // (2) - for EXISTS, can also remove "ORDER BY ... LIMIT n",
+ // but cannot remove "ORDER BY ... LIMIT n OFFSET m"
+ if (!select_lex->select_limit || // (1)
+ (substype == Item_subselect::EXISTS_SUBS && // (2)
+ !select_lex->offset_limit)) // (2)
+ {
+ select_lex->join->order= 0;
+ select_lex->join->skip_sort_order= 1;
+ }
+ }
+
+ /* Resolve expressions and perform semantic analysis for IN query */
+ if (in_subs != NULL)
+ /*
+ TODO: Add the condition below to this if statement when we have proper
+ support for is_correlated handling for materialized semijoins.
+ If we were to add this condition now, the fix_fields() call in
+ convert_subq_to_sj() would force the flag is_correlated to be set
+ erroneously for prepared queries.
+
+ thd->stmt_arena->state != Query_arena::PREPARED)
+ */
+ {
+ SELECT_LEX *current= thd->lex->current_select;
+ thd->lex->current_select= current->return_after_parsing();
+ char const *save_where= thd->where;
+ thd->where= "IN/ALL/ANY subquery";
+
+ Item **left= in_subs->left_exp_ptr();
+ bool failure= (*left)->fix_fields_if_needed(thd, left);
+ thd->lex->current_select= current;
+ thd->where= save_where;
+ if (failure)
+ DBUG_RETURN(-1); /* purecov: deadcode */
+
+ // fix_field above can rewrite left expression
+ uint ncols= (*left)->cols();
+ /*
+ Check if the left and right expressions have the same # of
+ columns, i.e. we don't have a case like
+ (oe1, oe2) IN (SELECT ie1, ie2, ie3 ...)
+
+ TODO why do we have this duplicated in IN->EXISTS transformers?
+ psergey-todo: fix these: grep for duplicated_subselect_card_check
+ */
+ if (select_lex->item_list.elements != ncols)
+ {
+ my_error(ER_OPERAND_COLUMNS, MYF(0), ncols);
+ DBUG_RETURN(-1);
+ }
+ }
+
+ DBUG_PRINT("info", ("Checking if subq can be converted to semi-join"));
+ /*
+ Check if we're in subquery that is a candidate for flattening into a
+ semi-join (which is done in flatten_subqueries()). The
+ requirements are:
+ 1. Subquery predicate is an IN/=ANY subq predicate
+ 2. Subquery is a single SELECT (not a UNION)
+ 3. Subquery does not have GROUP BY or ORDER BY
+ 4. Subquery does not use aggregate functions or HAVING
+ 5. Subquery predicate is at the AND-top-level of ON/WHERE clause
+ 6. We are not in a subquery of a single table UPDATE/DELETE that
+ doesn't have a JOIN (TODO: We should handle this at some
+ point by switching to multi-table UPDATE/DELETE)
+ 7. We're not in a table-less subquery like "SELECT 1"
+ 8. No execution method was already chosen (by a prepared statement)
+ 9. Parent select is not a table-less select
+ 10. Neither parent nor child select have STRAIGHT_JOIN option.
+ 11. It is first optimisation (the subquery could be moved from ON
+ clause during first optimisation and then be considered for SJ
+ on the second when it is too late)
+ */
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
+ in_subs && // 1
+ !select_lex->is_part_of_union() && // 2
+ !select_lex->group_list.elements && !join->order && // 3
+ !join->having && !select_lex->with_sum_func && // 4
+ in_subs->emb_on_expr_nest && // 5
+ select_lex->outer_select()->join && // 6
+ parent_unit->first_select()->leaf_tables.elements && // 7
+ !in_subs->has_strategy() && // 8
+ select_lex->outer_select()->table_list.first && // 9
+ !((join->select_options | // 10
+ select_lex->outer_select()->join->select_options) // 10
+ & SELECT_STRAIGHT_JOIN) && // 10
+ select_lex->first_cond_optimization) // 11
+ {
+ DBUG_PRINT("info", ("Subquery is semi-join conversion candidate"));
+
+ (void)subquery_types_allow_materialization(thd, in_subs);
+
+ in_subs->is_flattenable_semijoin= TRUE;
+
+ /* Register the subquery for further processing in flatten_subqueries() */
+ if (!in_subs->is_registered_semijoin)
+ {
+ Query_arena *arena, backup;
+ arena= thd->activate_stmt_arena_if_needed(&backup);
+ select_lex->outer_select()->sj_subselects.push_back(in_subs,
+ thd->mem_root);
+ if (arena)
+ thd->restore_active_arena(arena, &backup);
+ in_subs->is_registered_semijoin= TRUE;
+ OPT_TRACE_TRANSFORM(thd, trace_wrapper, trace_transform,
+ select_lex->select_number,
+ "IN (SELECT)", "semijoin");
+ trace_transform.add("chosen", true);
+ }
+ }
+ else
+ {
+ DBUG_PRINT("info", ("Subquery can't be converted to merged semi-join"));
+ /* Test if the user has set a legal combination of optimizer switches. */
+ DBUG_ASSERT(optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS |
+ OPTIMIZER_SWITCH_MATERIALIZATION));
+ /*
+ Transform each subquery predicate according to its overloaded
+ transformer.
+ */
+ if (subselect->select_transformer(join))
+ DBUG_RETURN(-1);
+
+ /*
+ If the subquery predicate is IN/=ANY, analyse and set all possible
+ subquery execution strategies based on optimizer switches and syntactic
+ properties.
+ */
+ if (in_subs && !in_subs->has_strategy())
+ {
+ if (is_materialization_applicable(thd, in_subs, select_lex))
+ {
+ in_subs->add_strategy(SUBS_MATERIALIZATION);
+
+ /*
+ If the subquery is an AND-part of WHERE register for being processed
+ with jtbm strategy
+ */
+ if (in_subs->emb_on_expr_nest == NO_JOIN_NEST &&
+ optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN))
+ {
+ in_subs->is_flattenable_semijoin= FALSE;
+ if (!in_subs->is_registered_semijoin)
+ {
+ Query_arena *arena, backup;
+ arena= thd->activate_stmt_arena_if_needed(&backup);
+ select_lex->outer_select()->sj_subselects.push_back(in_subs,
+ thd->mem_root);
+ if (arena)
+ thd->restore_active_arena(arena, &backup);
+ in_subs->is_registered_semijoin= TRUE;
+ }
+ }
+ }
+
+ /*
+ IN-TO-EXISTS is the only universal strategy. Choose it if the user
+ allowed it via an optimizer switch, or if materialization is not
+ possible.
+ */
+ if (optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS) ||
+ !in_subs->has_strategy())
+ in_subs->add_strategy(SUBS_IN_TO_EXISTS);
+ }
+
+ /* Check if max/min optimization applicable */
+ if (allany_subs && !allany_subs->is_set_strategy())
+ {
+ uchar strategy= (allany_subs->is_maxmin_applicable(join) ?
+ (SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE) :
+ SUBS_IN_TO_EXISTS);
+ allany_subs->add_strategy(strategy);
+ }
+
+ }
+ }
+ DBUG_RETURN(0);
+}
+
+
+/**
+ @brief Check if subquery's compared types allow materialization.
+
+ @param in_subs Subquery predicate, updated as follows:
+ types_allow_materialization TRUE if subquery materialization is allowed.
+ sjm_scan_allowed If types_allow_materialization is TRUE,
+ indicates whether it is possible to use subquery
+ materialization and scan the materialized table.
+
+ @retval TRUE If subquery types allow materialization.
+ @retval FALSE Otherwise.
+
+ @details
+ This is a temporary fix for BUG#36752.
+
+ There are two subquery materialization strategies:
+
+ 1. Materialize and do index lookups in the materialized table. See
+ BUG#36752 for description of restrictions we need to put on the
+ compared expressions.
+
+ 2. Materialize and then do a full scan of the materialized table. At the
+ moment, this strategy's applicability criteria are even stricter than
+ in #1.
+
+ This is so because of the following: consider an uncorrelated subquery
+
+ ...WHERE (ot1.col1, ot2.col2 ...) IN (SELECT ie1,ie2,... FROM it1 ...)
+
+ and a join order that could be used to do sjm-materialization:
+
+ SJM-Scan(it1, it1), ot1, ot2
+
+ IN-equalities will be parts of conditions attached to the outer tables:
+
+ ot1: ot1.col1 = ie1 AND ... (C1)
+ ot2: ot1.col2 = ie2 AND ... (C2)
+
+ besides those there may be additional references to ie1 and ie2
+ generated by equality propagation. The problem with evaluating C1 and
+ C2 is that ie{1,2} refer to subquery tables' columns, while we only have
+ current value of materialization temptable. Our solution is to
+ * require that all ie{N} are table column references. This allows
+ to copy the values of materialization temptable columns to the
+ original table's columns (see setup_sj_materialization for more
+ details)
+ * require that compared columns have exactly the same type. This is
+ a temporary measure to avoid BUG#36752-type problems.
+
+ JOIN_TAB::keyuse_is_valid_for_access_in_chosen_plan expects that for Semi Join Materialization
+ Scan all the items in the select list of the IN Subquery are of the type Item::FIELD_ITEM.
+*/
+
+static
+bool subquery_types_allow_materialization(THD* thd, Item_in_subselect *in_subs)
+{
+ Item *left_exp= in_subs->left_exp();
+ DBUG_ENTER("subquery_types_allow_materialization");
+
+ DBUG_ASSERT(left_exp->is_fixed());
+
+ List_iterator<Item> it(in_subs->unit->first_select()->item_list);
+ uint elements= in_subs->unit->first_select()->item_list.elements;
+ const char* cause= NULL;
+
+ in_subs->types_allow_materialization= FALSE; // Assign default values
+ in_subs->sjm_scan_allowed= FALSE;
+
+ OPT_TRACE_TRANSFORM(thd, trace_wrapper, trace_transform,
+ in_subs->get_select_lex()->select_number,
+ "IN (SELECT)", "materialization");
+
+ /*
+ The checks here must be kept in sync with the one in
+ Item_func_in::in_predicate_to_in_subs_transformer().
+ */
+
+ bool all_are_fields= TRUE;
+ uint32 total_key_length = 0;
+ bool converted_from_in_predicate= in_subs->converted_from_in_predicate;
+ for (uint i= 0; i < elements; i++)
+ {
+ Item *outer= left_exp->element_index(i);
+ Item *inner= it++;
+ all_are_fields &= (outer->real_item()->type() == Item::FIELD_ITEM &&
+ inner->real_item()->type() == Item::FIELD_ITEM);
+ total_key_length += inner->max_length;
+ if (!inner->
+ type_handler()->
+ subquery_type_allows_materialization(inner,
+ outer,
+ converted_from_in_predicate))
+ {
+ trace_transform.add("possible", false);
+ trace_transform.add("cause", "types mismatch");
+ DBUG_RETURN(FALSE);
+ }
+ }
+
+ /*
+ Make sure that create_tmp_table will not fail due to too long keys.
+ See MDEV-7122. This check is performed inside create_tmp_table also and
+ we must do it so that we know the table has keys created.
+ Make sure that the length of the key for the temp_table is atleast
+ greater than 0.
+ */
+ if (!total_key_length)
+ cause= "zero length key for materialized table";
+ else if (total_key_length > tmp_table_max_key_length())
+ cause= "length of key greater than allowed key length for materialized tables";
+ else if (elements > tmp_table_max_key_parts())
+ cause= "#keyparts greater than allowed key parts for materialized tables";
+ else
+ {
+ in_subs->types_allow_materialization= TRUE;
+ in_subs->sjm_scan_allowed= all_are_fields;
+ trace_transform.add("sjm_scan_allowed", all_are_fields)
+ .add("possible", true);
+ DBUG_PRINT("info",("subquery_types_allow_materialization: ok, allowed"));
+ DBUG_RETURN(TRUE);
+ }
+ trace_transform.add("possible", false).add("cause", cause);
+ DBUG_RETURN(FALSE);
+}
+
+
+/**
+ Apply max min optimization of all/any subselect
+*/
+
+bool JOIN::transform_max_min_subquery()
+{
+ DBUG_ENTER("JOIN::transform_max_min_subquery");
+ Item_subselect *subselect= unit->item;
+ if (!subselect || (subselect->substype() != Item_subselect::ALL_SUBS &&
+ subselect->substype() != Item_subselect::ANY_SUBS))
+ DBUG_RETURN(0);
+ DBUG_RETURN(((Item_allany_subselect *) subselect)->
+ transform_into_max_min(this));
+}
+
+
+/*
+ Finalize IN->EXISTS conversion in case we couldn't use materialization.
+
+ DESCRIPTION Invoke the IN->EXISTS converter
+ Replace the Item_in_subselect with its wrapper Item_in_optimizer in WHERE.
+
+ RETURN
+ FALSE - Ok
+ TRUE - Fatal error
+*/
+
+bool make_in_exists_conversion(THD *thd, JOIN *join, Item_in_subselect *item)
+{
+ DBUG_ENTER("make_in_exists_conversion");
+ JOIN *child_join= item->unit->first_select()->join;
+ bool res;
+
+ /*
+ We're going to finalize IN->EXISTS conversion.
+ Normally, IN->EXISTS conversion takes place inside the
+ Item_subselect::fix_fields() call, where item_subselect->is_fixed()==FALSE (as
+ fix_fields() haven't finished yet) and item_subselect->changed==FALSE (as
+ the conversion haven't been finalized)
+
+ At the end of Item_subselect::fix_fields() we had to set fixed=TRUE,
+ changed=TRUE (the only other option would have been to return error).
+
+ So, now we have to set these back for the duration of select_transformer()
+ call.
+ */
+ item->changed= 0;
+ item->fixed= 0;
+
+ SELECT_LEX *save_select_lex= thd->lex->current_select;
+ thd->lex->current_select= item->unit->first_select();
+
+ res= item->select_transformer(child_join);
+
+ thd->lex->current_select= save_select_lex;
+
+ if (res)
+ DBUG_RETURN(TRUE);
+
+ item->changed= 1;
+ item->fixed= 1;
+
+ Item *substitute= item->substitution;
+ bool do_fix_fields= !item->substitution->is_fixed();
+ /*
+ The Item_subselect has already been wrapped with Item_in_optimizer, so we
+ should search for item->optimizer, not 'item'.
+ */
+ Item *replace_me= item->optimizer;
+ DBUG_ASSERT(replace_me==substitute);
+
+ Item **tree= (item->emb_on_expr_nest == NO_JOIN_NEST)?
+ &join->conds : &(item->emb_on_expr_nest->on_expr);
+ if (replace_where_subcondition(join, tree, replace_me, substitute,
+ do_fix_fields))
+ DBUG_RETURN(TRUE);
+ item->substitution= NULL;
+
+ /*
+ If this is a prepared statement, repeat the above operation for
+ prep_where (or prep_on_expr).
+ */
+ if (!thd->stmt_arena->is_conventional())
+ {
+ tree= (item->emb_on_expr_nest == (TABLE_LIST*)NO_JOIN_NEST)?
+ &join->select_lex->prep_where :
+ &(item->emb_on_expr_nest->prep_on_expr);
+
+ if (replace_where_subcondition(join, tree, replace_me, substitute,
+ FALSE))
+ DBUG_RETURN(TRUE);
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+bool check_for_outer_joins(List<TABLE_LIST> *join_list)
+{
+ TABLE_LIST *table;
+ NESTED_JOIN *nested_join;
+ List_iterator<TABLE_LIST> li(*join_list);
+ while ((table= li++))
+ {
+ if ((nested_join= table->nested_join))
+ {
+ if (check_for_outer_joins(&nested_join->join_list))
+ return TRUE;
+ }
+
+ if (table->outer_join)
+ return TRUE;
+ }
+ return FALSE;
+}
+
+
+void find_and_block_conversion_to_sj(Item *to_find,
+ List_iterator_fast<Item_in_subselect> &li)
+{
+ if (to_find->type() == Item::FUNC_ITEM &&
+ ((Item_func*)to_find)->functype() == Item_func::IN_OPTIMIZER_FUNC)
+ to_find= ((Item_in_optimizer*)to_find)->get_wrapped_in_subselect_item();
+
+ if (to_find->type() != Item::SUBSELECT_ITEM ||
+ ((Item_subselect *) to_find)->substype() != Item_subselect::IN_SUBS)
+ return;
+ Item_in_subselect *in_subq;
+ li.rewind();
+ while ((in_subq= li++))
+ {
+ if (in_subq == to_find)
+ {
+ in_subq->block_conversion_to_sj();
+ return;
+ }
+ }
+}
+
+
+/*
+ Convert semi-join subquery predicates into semi-join join nests
+
+ SYNOPSIS
+ convert_join_subqueries_to_semijoins()
+
+ DESCRIPTION
+
+ Convert candidate subquery predicates into semi-join join nests. This
+ transformation is performed once in query lifetime and is irreversible.
+
+ Conversion of one subquery predicate
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ We start with a join that has a semi-join subquery:
+
+ SELECT ...
+ FROM ot, ...
+ WHERE oe IN (SELECT ie FROM it1 ... itN WHERE subq_where) AND outer_where
+
+ and convert it into a semi-join nest:
+
+ SELECT ...
+ FROM ot SEMI JOIN (it1 ... itN), ...
+ WHERE outer_where AND subq_where AND oe=ie
+
+ that is, in order to do the conversion, we need to
+
+ * Create the "SEMI JOIN (it1 .. itN)" part and add it into the parent
+ query's FROM structure.
+ * Add "AND subq_where AND oe=ie" into parent query's WHERE (or ON if
+ the subquery predicate was in an ON expression)
+ * Remove the subquery predicate from the parent query's WHERE
+
+ Considerations when converting many predicates
+ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ A join may have at most MAX_TABLES tables. This may prevent us from
+ flattening all subqueries when the total number of tables in parent and
+ child selects exceeds MAX_TABLES.
+ We deal with this problem by flattening children's subqueries first and
+ then using a heuristic rule to determine each subquery predicate's
+ "priority".
+
+ RETURN
+ FALSE OK
+ TRUE Error
+*/
+
+bool convert_join_subqueries_to_semijoins(JOIN *join)
+{
+ Query_arena *arena, backup;
+ Item_in_subselect *in_subq;
+ THD *thd= join->thd;
+ DBUG_ENTER("convert_join_subqueries_to_semijoins");
+
+ if (join->select_lex->sj_subselects.is_empty())
+ DBUG_RETURN(FALSE);
+
+ List_iterator_fast<Item_in_subselect> li(join->select_lex->sj_subselects);
+
+ while ((in_subq= li++))
+ {
+ SELECT_LEX *subq_sel= in_subq->get_select_lex();
+ if (subq_sel->handle_derived(thd->lex, DT_MERGE))
+ DBUG_RETURN(TRUE);
+ if (subq_sel->join->transform_in_predicates_into_in_subq(thd))
+ DBUG_RETURN(TRUE);
+ subq_sel->update_used_tables();
+ }
+
+ /*
+ Check all candidates to semi-join conversion that occur
+ in ON expressions of outer join. Set the flag blocking
+ this conversion for them.
+ */
+ TABLE_LIST *tbl;
+ List_iterator<TABLE_LIST> ti(join->select_lex->leaf_tables);
+ while ((tbl= ti++))
+ {
+ TABLE_LIST *embedded;
+ TABLE_LIST *embedding= tbl;
+ do
+ {
+ embedded= embedding;
+ bool block_conversion_to_sj= false;
+ if (embedded->on_expr)
+ {
+ /*
+ Conversion of an IN subquery predicate into semi-join
+ is blocked now if the predicate occurs:
+ - in the ON expression of an outer join
+ - in the ON expression of an inner join embedded directly
+ or indirectly in the inner nest of an outer join
+ */
+ for (TABLE_LIST *tl= embedded; tl; tl= tl->embedding)
+ {
+ if (tl->outer_join)
+ {
+ block_conversion_to_sj= true;
+ break;
+ }
+ }
+ }
+ if (block_conversion_to_sj)
+ {
+ Item *cond= embedded->on_expr;
+ if (!cond)
+ ;
+ else if (cond->type() != Item::COND_ITEM)
+ find_and_block_conversion_to_sj(cond, li);
+ else if (((Item_cond*) cond)->functype() ==
+ Item_func::COND_AND_FUNC)
+ {
+ Item *item;
+ List_iterator<Item> it(*(((Item_cond*) cond)->argument_list()));
+ while ((item= it++))
+ {
+ find_and_block_conversion_to_sj(item, li);
+ }
+ }
+ }
+ embedding= embedded->embedding;
+ }
+ while (embedding &&
+ embedding->nested_join->join_list.head() == embedded);
+ }
+
+ /*
+ Block conversion to semi-joins for those candidates that
+ are encountered in the WHERE condition of the multi-table view
+ with CHECK OPTION if this view is used in UPDATE/DELETE.
+ (This limitation can be, probably, easily lifted.)
+ */
+ li.rewind();
+ while ((in_subq= li++))
+ {
+ if (in_subq->emb_on_expr_nest != NO_JOIN_NEST &&
+ in_subq->emb_on_expr_nest->effective_with_check)
+ {
+ in_subq->block_conversion_to_sj();
+ }
+ }
+
+ if (join->select_options & SELECT_STRAIGHT_JOIN)
+ {
+ /* Block conversion to semijoins for all candidates */
+ li.rewind();
+ while ((in_subq= li++))
+ {
+ in_subq->block_conversion_to_sj();
+ }
+ }
+
+ li.rewind();
+ /* First, convert child join's subqueries. We proceed bottom-up here */
+ while ((in_subq= li++))
+ {
+ st_select_lex *child_select= in_subq->get_select_lex();
+ JOIN *child_join= child_select->join;
+ child_join->outer_tables = child_join->table_count;
+
+ /*
+ child_select->where contains only the WHERE predicate of the
+ subquery itself here. We may be selecting from a VIEW, which has its
+ own predicate. The combined predicates are available in child_join->conds,
+ which was built by setup_conds() doing prepare_where() for all views.
+ */
+ child_select->where= child_join->conds;
+
+ if (convert_join_subqueries_to_semijoins(child_join))
+ DBUG_RETURN(TRUE);
+
+
+ in_subq->sj_convert_priority=
+ MY_TEST(in_subq->do_not_convert_to_sj) * MAX_TABLES * 2 +
+ in_subq->is_correlated * MAX_TABLES + child_join->outer_tables;
+ }
+
+ // Temporary measure: disable semi-joins when they are together with outer
+ // joins.
+#if 0
+ if (check_for_outer_joins(join->join_list))
+ {
+ in_subq= join->select_lex->sj_subselects.head();
+ arena= thd->activate_stmt_arena_if_needed(&backup);
+ goto skip_conversion;
+ }
+#endif
+ //dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables);
+ /*
+ 2. Pick which subqueries to convert:
+ sort the subquery array
+ - prefer correlated subqueries over uncorrelated;
+ - prefer subqueries that have greater number of outer tables;
+ */
+ bubble_sort<Item_in_subselect>(&join->select_lex->sj_subselects,
+ subq_sj_candidate_cmp, NULL);
+ // #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
+ /* Replace all subqueries to be flattened with Item_int(1) */
+ arena= thd->activate_stmt_arena_if_needed(&backup);
+
+ li.rewind();
+ while ((in_subq= li++))
+ {
+ bool remove_item= TRUE;
+
+ /* Stop processing if we've reached a subquery that's attached to the ON clause */
+ if (in_subq->do_not_convert_to_sj)
+ {
+ OPT_TRACE_TRANSFORM(thd, trace_wrapper, trace_transform,
+ in_subq->get_select_lex()->select_number,
+ "IN (SELECT)", "semijoin");
+ trace_transform.add("converted_to_semi_join", false)
+ .add("cause", "subquery attached to the ON clause");
+ break;
+ }
+
+ if (in_subq->is_flattenable_semijoin)
+ {
+ OPT_TRACE_TRANSFORM(thd, trace_wrapper, trace_transform,
+ in_subq->get_select_lex()->select_number,
+ "IN (SELECT)", "semijoin");
+ if (join->table_count +
+ in_subq->unit->first_select()->join->table_count >= MAX_TABLES)
+ {
+ trace_transform.add("converted_to_semi_join", false);
+ trace_transform.add("cause",
+ "table in parent join now exceeds MAX_TABLES");
+ break;
+ }
+ if (convert_subq_to_sj(join, in_subq))
+ goto restore_arena_and_fail;
+ trace_transform.add("converted_to_semi_join", true);
+ }
+ else
+ {
+ if (join->table_count + 1 >= MAX_TABLES)
+ break;
+ if (convert_subq_to_jtbm(join, in_subq, &remove_item))
+ goto restore_arena_and_fail;
+ }
+ if (remove_item)
+ {
+ Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
+ &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
+ Item *replace_me= in_subq->original_item();
+ if (replace_where_subcondition(join, tree, replace_me,
+ new (thd->mem_root) Item_int(thd, 1),
+ FALSE))
+ goto restore_arena_and_fail;
+ }
+ }
+//skip_conversion:
+ /*
+ 3. Finalize (perform IN->EXISTS rewrite) the subqueries that we didn't
+ convert:
+ */
+ while (in_subq)
+ {
+ JOIN *child_join= in_subq->unit->first_select()->join;
+ in_subq->changed= 0;
+ in_subq->fixed= 0;
+
+ SELECT_LEX *save_select_lex= thd->lex->current_select;
+ thd->lex->current_select= in_subq->unit->first_select();
+
+ bool res= in_subq->select_transformer(child_join);
+
+ thd->lex->current_select= save_select_lex;
+
+ if (res)
+ DBUG_RETURN(TRUE);
+
+ in_subq->changed= 1;
+ in_subq->fixed= 1;
+
+ Item *substitute= in_subq->substitution;
+ bool do_fix_fields= !in_subq->substitution->is_fixed();
+ Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
+ &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
+ Item *replace_me= in_subq->original_item();
+ if (replace_where_subcondition(join, tree, replace_me, substitute,
+ do_fix_fields))
+ DBUG_RETURN(TRUE);
+ in_subq->substitution= NULL;
+ /*
+ If this is a prepared statement, repeat the above operation for
+ prep_where (or prep_on_expr). Subquery-to-semijoin conversion is
+ done once for prepared statement.
+ */
+ if (!thd->stmt_arena->is_conventional())
+ {
+ tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
+ &join->select_lex->prep_where :
+ &(in_subq->emb_on_expr_nest->prep_on_expr);
+ /*
+ prep_on_expr/ prep_where may be NULL in some cases.
+ If that is the case, do nothing - simplify_joins() will copy
+ ON/WHERE expression into prep_on_expr/prep_where.
+ */
+ if (*tree && replace_where_subcondition(join, tree, replace_me, substitute,
+ FALSE))
+ DBUG_RETURN(TRUE);
+ }
+ /*
+ Revert to the IN->EXISTS strategy in the rare case when the subquery could
+ not be flattened.
+ */
+ in_subq->reset_strategy(SUBS_IN_TO_EXISTS);
+ if (is_materialization_applicable(thd, in_subq,
+ in_subq->unit->first_select()))
+ {
+ in_subq->add_strategy(SUBS_MATERIALIZATION);
+ }
+
+ in_subq= li++;
+ }
+
+ if (arena)
+ thd->restore_active_arena(arena, &backup);
+ join->select_lex->sj_subselects.empty();
+ DBUG_RETURN(FALSE);
+
+restore_arena_and_fail:
+ if (arena)
+ thd->restore_active_arena(arena, &backup);
+ DBUG_RETURN(TRUE);
+}
+
+
+/*
+ Get #output_rows and scan_time estimates for a "delayed" table.
+
+ SYNOPSIS
+ get_delayed_table_estimates()
+ table IN Table to get estimates for
+ out_rows OUT E(#rows in the table)
+ scan_time OUT E(scan_time).
+ startup_cost OUT cost to populate the table.
+
+ DESCRIPTION
+ Get #output_rows and scan_time estimates for a "delayed" table. By
+ "delayed" here we mean that the table is filled at the start of query
+ execution. This means that the optimizer can't use table statistics to
+ get #rows estimate for it, it has to call this function instead.
+
+ This function is expected to make different actions depending on the nature
+ of the table. At the moment there is only one kind of delayed tables,
+ non-flattenable semi-joins.
+*/
+
+void get_delayed_table_estimates(TABLE *table,
+ ha_rows *out_rows,
+ double *scan_time,
+ double *startup_cost)
+{
+ Item_in_subselect *item= table->pos_in_table_list->jtbm_subselect;
+
+ DBUG_ASSERT(item->engine->engine_type() ==
+ subselect_engine::HASH_SJ_ENGINE);
+
+ subselect_hash_sj_engine *hash_sj_engine=
+ ((subselect_hash_sj_engine*)item->engine);
+
+ *out_rows= (ha_rows)item->jtbm_record_count;
+ *startup_cost= item->jtbm_read_time;
+
+ /* Calculate cost of scanning the temptable */
+ double data_size= COST_MULT(item->jtbm_record_count,
+ hash_sj_engine->tmp_table->s->reclength);
+ /* Do like in handler::scan_time() */
+ *scan_time= ((data_size/table->file->stats.block_size+2) *
+ table->file->avg_io_cost());
+}
+
+
+/**
+ @brief Replaces an expression destructively inside the expression tree of
+ the WHERE clase.
+
+ @note We substitute AND/OR structure because it was copied by
+ copy_andor_structure and some changes could be done in the copy but
+ should be left permanent, also there could be several layers of AND over
+ AND and OR over OR because ::fix_field() possibly is not called.
+
+ @param join The top-level query.
+ @param old_cond The expression to be replaced.
+ @param new_cond The expression to be substituted.
+ @param do_fix_fields If true, Item::fix_fields(THD*, Item**) is called for
+ the new expression.
+ @return <code>true</code> if there was an error, <code>false</code> if
+ successful.
+*/
+
+static bool replace_where_subcondition(JOIN *join, Item **expr,
+ Item *old_cond, Item *new_cond,
+ bool do_fix_fields)
+{
+ if (*expr == old_cond)
+ {
+ *expr= new_cond;
+ if (do_fix_fields)
+ new_cond->fix_fields(join->thd, expr);
+ return FALSE;
+ }
+
+ if ((*expr)->type() == Item::COND_ITEM)
+ {
+ List_iterator<Item> li(*((Item_cond*)(*expr))->argument_list());
+ Item *item;
+ while ((item= li++))
+ {
+ if (item == old_cond)
+ {
+ li.replace(new_cond);
+ if (do_fix_fields)
+ new_cond->fix_fields(join->thd, li.ref());
+ return FALSE;
+ }
+ else if (item->type() == Item::COND_ITEM)
+ {
+ replace_where_subcondition(join, li.ref(),
+ old_cond, new_cond,
+ do_fix_fields);
+ }
+ }
+ }
+ /*
+ We can come to here when
+ - we're doing replace operations on both on_expr and prep_on_expr
+ - on_expr is the same as prep_on_expr, or they share a sub-tree
+ (so, when we do replace in on_expr, we replace in prep_on_expr, too,
+ and when we try doing a replace in prep_on_expr, the item we wanted
+ to replace there has already been replaced)
+ */
+ return FALSE;
+}
+
+static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
+ void *arg)
+{
+ return (el1->sj_convert_priority > el2->sj_convert_priority) ? -1 :
+ ( (el1->sj_convert_priority == el2->sj_convert_priority)? 0 : 1);
+}
+
+
+/**
+ @brief
+ reset the value of the field in_eqaulity_no for all Item_func_eq
+ items in the where clause of the subquery.
+
+ Look for in_equality_no description in Item_func_eq class
+
+ DESCRIPTION
+ Lets have an example:
+ SELECT t1.a FROM t1 WHERE t1.a IN
+ (SELECT t2.a FROM t2 where t2.b IN
+ (select t3.b from t3 where t3.c=27 ))
+
+ So for such a query we have the parent, child and
+ grandchild select.
+
+ So for the equality t2.b = t3.b we set the value for in_equality_no to
+ 0 according to its description. Wewe do the same for t1.a = t2.a.
+ But when we look at the child select (with the grandchild select merged),
+ the query would be
+
+ SELECT t1.a FROM t1 WHERE t1.a IN
+ (SELECT t2.a FROM t2 where t2.b = t3.b and t3.c=27)
+
+ and then when the child select is merged into the parent select the query
+ would look like
+
+ SELECT t1.a FROM t1, semi-join-nest(t2,t3)
+ WHERE t1.a =t2.a and t2.b = t3.b and t3.c=27
+
+ Still we would have in_equality_no set for t2.b = t3.b
+ though it does not take part in the semi-join equality for the parent select,
+ so we should reset its value to UINT_MAX.
+
+ @param cond WHERE clause of the subquery
+*/
+
+static void reset_equality_number_for_subq_conds(Item * cond)
+{
+ if (!cond)
+ return;
+ if (cond->type() == Item::COND_ITEM)
+ {
+ List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
+ Item *item;
+ while ((item=li++))
+ {
+ if (item->type() == Item::FUNC_ITEM &&
+ ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
+ ((Item_func_eq*)item)->in_equality_no= UINT_MAX;
+ }
+ }
+ else
+ {
+ if (cond->type() == Item::FUNC_ITEM &&
+ ((Item_func*)cond)->functype()== Item_func::EQ_FUNC)
+ ((Item_func_eq*)cond)->in_equality_no= UINT_MAX;
+ }
+ return;
+}
+
+/*
+ Convert a subquery predicate into a TABLE_LIST semi-join nest
+
+ SYNOPSIS
+ convert_subq_to_sj()
+ parent_join Parent join, the one that has subq_pred in its WHERE/ON
+ clause
+ subq_pred Subquery predicate to be converted
+
+ DESCRIPTION
+ Convert a subquery predicate into a TABLE_LIST semi-join nest. All the
+ prerequisites are already checked, so the conversion is always successfull.
+
+ Prepared Statements: the transformation is permanent:
+ - Changes in TABLE_LIST structures are naturally permanent
+ - Item tree changes are performed on statement MEM_ROOT:
+ = we activate statement MEM_ROOT
+ = this function is called before the first fix_prepare_information
+ call.
+
+ This is intended because the criteria for subquery-to-sj conversion remain
+ constant for the lifetime of the Prepared Statement.
+
+ RETURN
+ FALSE OK
+ TRUE Out of memory error
+*/
+
+static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
+{
+ SELECT_LEX *parent_lex= parent_join->select_lex;
+ TABLE_LIST *emb_tbl_nest= NULL;
+ List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
+ THD *thd= parent_join->thd;
+ DBUG_ENTER("convert_subq_to_sj");
+
+ /*
+ 1. Find out where to put the predicate into.
+ Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
+ */
+ if ((void*)subq_pred->emb_on_expr_nest != (void*)NO_JOIN_NEST)
+ {
+ if (subq_pred->emb_on_expr_nest->nested_join)
+ {
+ /*
+ We're dealing with
+
+ ... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
+
+ The sj-nest will be inserted into the brackets nest.
+ */
+ emb_tbl_nest= subq_pred->emb_on_expr_nest;
+ emb_join_list= &emb_tbl_nest->nested_join->join_list;
+ }
+ else if (!subq_pred->emb_on_expr_nest->outer_join)
+ {
+ /*
+ We're dealing with
+
+ ... INNER JOIN tblX ON (subquery AND whatever) ...
+
+ The sj-nest will be tblX's "sibling", i.e. another child of its
+ parent. This is ok because tblX is joined as an inner join.
+ */
+ emb_tbl_nest= subq_pred->emb_on_expr_nest->embedding;
+ if (emb_tbl_nest)
+ emb_join_list= &emb_tbl_nest->nested_join->join_list;
+ }
+ else if (!subq_pred->emb_on_expr_nest->nested_join)
+ {
+ TABLE_LIST *outer_tbl= subq_pred->emb_on_expr_nest;
+ TABLE_LIST *wrap_nest;
+ LEX_CSTRING sj_wrap_name= { STRING_WITH_LEN("(sj-wrap)") };
+ /*
+ We're dealing with
+
+ ... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
+
+ we'll need to convert it into:
+
+ ... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
+ | |
+ |<----- wrap_nest ---->|
+
+ Q: other subqueries may be pointing to this element. What to do?
+ A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
+ But we'll need to fix other pointers.
+ A2: Another way: have TABLE_LIST::next_ptr so the following
+ subqueries know the table has been nested.
+ A3: changes in the TABLE_LIST::outer_join will make everything work
+ automatically.
+ */
+ if (!(wrap_nest= alloc_join_nest(thd)))
+ {
+ DBUG_RETURN(TRUE);
+ }
+ wrap_nest->embedding= outer_tbl->embedding;
+ wrap_nest->join_list= outer_tbl->join_list;
+ wrap_nest->alias= sj_wrap_name;
+
+ wrap_nest->nested_join->join_list.empty();
+ wrap_nest->nested_join->join_list.push_back(outer_tbl, thd->mem_root);
+
+ outer_tbl->embedding= wrap_nest;
+ outer_tbl->join_list= &wrap_nest->nested_join->join_list;
+
+ /*
+ wrap_nest will take place of outer_tbl, so move the outer join flag
+ and on_expr
+ */
+ wrap_nest->outer_join= outer_tbl->outer_join;
+ outer_tbl->outer_join= 0;
+
+ wrap_nest->on_expr= outer_tbl->on_expr;
+ outer_tbl->on_expr= NULL;
+
+ List_iterator<TABLE_LIST> li(*wrap_nest->join_list);
+ TABLE_LIST *tbl;
+ while ((tbl= li++))
+ {
+ if (tbl == outer_tbl)
+ {
+ li.replace(wrap_nest);
+ break;
+ }
+ }
+ /*
+ Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
+ semi-join nest into it
+ */
+ emb_join_list= &wrap_nest->nested_join->join_list;
+ emb_tbl_nest= wrap_nest;
+ }
+ }
+
+ TABLE_LIST *sj_nest;
+ NESTED_JOIN *nested_join;
+ LEX_CSTRING sj_nest_name= { STRING_WITH_LEN("(sj-nest)") };
+ if (!(sj_nest= alloc_join_nest(thd)))
+ {
+ DBUG_RETURN(TRUE);
+ }
+ nested_join= sj_nest->nested_join;
+
+ sj_nest->join_list= emb_join_list;
+ sj_nest->embedding= emb_tbl_nest;
+ sj_nest->alias= sj_nest_name;
+ sj_nest->sj_subq_pred= subq_pred;
+ sj_nest->original_subq_pred_used_tables= subq_pred->used_tables() |
+ subq_pred->left_exp()->used_tables();
+ /* Nests do not participate in those 'chains', so: */
+ /* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
+ emb_join_list->push_back(sj_nest, thd->mem_root);
+
+ /*
+ nested_join->used_tables and nested_join->not_null_tables are
+ initialized in simplify_joins().
+ */
+
+ /*
+ 2. Walk through subquery's top list and set 'embedding' to point to the
+ sj-nest.
+ */
+ st_select_lex *subq_lex= subq_pred->unit->first_select();
+ DBUG_ASSERT(subq_lex->next_select() == NULL);
+ nested_join->join_list.empty();
+ List_iterator_fast<TABLE_LIST> li(subq_lex->top_join_list);
+ TABLE_LIST *tl;
+ while ((tl= li++))
+ {
+ tl->embedding= sj_nest;
+ tl->join_list= &nested_join->join_list;
+ nested_join->join_list.push_back(tl, thd->mem_root);
+ }
+
+ /*
+ Reconnect the next_leaf chain.
+ TODO: Do we have to put subquery's tables at the end of the chain?
+ Inserting them at the beginning would be a bit faster.
+ NOTE: We actually insert them at the front! That's because the order is
+ reversed in this list.
+ */
+ parent_lex->leaf_tables.append(&subq_lex->leaf_tables);
+
+ if (subq_lex->options & OPTION_SCHEMA_TABLE)
+ parent_lex->options |= OPTION_SCHEMA_TABLE;
+
+ /*
+ Same as above for next_local chain
+ (a theory: a next_local chain always starts with ::leaf_tables
+ because view's tables are inserted after the view)
+ */
+
+ for (tl= (TABLE_LIST*)(parent_lex->table_list.first); tl->next_local; tl= tl->next_local)
+ {}
+
+ tl->next_local= subq_lex->join->tables_list;
+
+ /* A theory: no need to re-connect the next_global chain */
+
+ /* 3. Remove the original subquery predicate from the WHERE/ON */
+
+ // The subqueries were replaced for Item_int(1) earlier
+ subq_pred->reset_strategy(SUBS_SEMI_JOIN); // for subsequent executions
+ /*TODO: also reset the 'm_with_subquery' there. */
+
+ /* n. Adjust the parent_join->table_count counter */
+ uint table_no= parent_join->table_count;
+ /* n. Walk through child's tables and adjust table->map */
+ List_iterator_fast<TABLE_LIST> si(subq_lex->leaf_tables);
+ while ((tl= si++))
+ {
+ tl->set_tablenr(table_no);
+ if (tl->is_jtbm())
+ {
+ tl->jtbm_table_no= table_no;
+ Item *dummy= tl->jtbm_subselect;
+ tl->jtbm_subselect->fix_after_pullout(parent_lex, &dummy, true);
+ DBUG_ASSERT(dummy == tl->jtbm_subselect);
+ }
+ SELECT_LEX *old_sl= tl->select_lex;
+ tl->select_lex= parent_join->select_lex;
+ for (TABLE_LIST *emb= tl->embedding;
+ emb && emb->select_lex == old_sl;
+ emb= emb->embedding)
+ emb->select_lex= parent_join->select_lex;
+ table_no++;
+ }
+ parent_join->table_count += subq_lex->join->table_count;
+ //parent_join->table_count += subq_lex->leaf_tables.elements;
+
+ /*
+ Put the subquery's WHERE into semi-join's sj_on_expr
+ Add the subquery-induced equalities too.
+ */
+ SELECT_LEX *save_lex= thd->lex->current_select;
+ thd->lex->current_select=subq_lex;
+ Item **left= subq_pred->left_exp_ptr();
+ if ((*left)->fix_fields_if_needed(thd, left))
+ DBUG_RETURN(TRUE);
+ Item *left_exp= *left;
+ Item *left_exp_orig= subq_pred->left_exp_orig();
+ thd->lex->current_select=save_lex;
+
+ table_map subq_pred_used_tables= subq_pred->used_tables();
+ sj_nest->nested_join->sj_corr_tables= subq_pred_used_tables;
+ sj_nest->nested_join->sj_depends_on= subq_pred_used_tables |
+ left_exp->used_tables();
+ sj_nest->sj_on_expr= subq_lex->join->conds;
+
+ /*
+ Create the IN-equalities and inject them into semi-join's ON expression.
+ Additionally, for LooseScan strategy
+ - Record the number of IN-equalities.
+ - Create list of pointers to (oe1, ..., ieN). We'll need the list to
+ see which of the expressions are bound and which are not (for those
+ we'll produce a distinct stream of (ie_i1,...ie_ik).
+
+ (TODO: can we just create a list of pointers and hope the expressions
+ will not substitute themselves on fix_fields()? or we need to wrap
+ them into Item_direct_view_refs and store pointers to those. The
+ pointers to Item_direct_view_refs are guaranteed to be stable as
+ Item_direct_view_refs doesn't substitute itself with anything in
+ Item_direct_view_ref::fix_fields.
+ */
+ uint ncols= sj_nest->sj_in_exprs= left_exp->cols();
+ sj_nest->nested_join->sj_outer_expr_list.empty();
+ reset_equality_number_for_subq_conds(sj_nest->sj_on_expr);
+
+ if (ncols == 1)
+ {
+ /* add left = select_list_element */
+ nested_join->sj_outer_expr_list.push_back(left,
+ thd->mem_root);
+ /*
+ Create Item_func_eq. Note that
+ 1. this is done on the statement, not execution, arena
+ 2. if it's a PS then this happens only once - on the first execution.
+ On following re-executions, the item will be fix_field-ed normally.
+ 3. Thus it should be created as if it was fix_field'ed, in particular
+ all pointers to items in the execution arena should be protected
+ with thd->change_item_tree
+ */
+ Item_func_eq *item_eq=
+ new (thd->mem_root) Item_func_eq(thd, left_exp_orig,
+ subq_lex->ref_pointer_array[0]);
+ if (!item_eq)
+ DBUG_RETURN(TRUE);
+ if (left_exp_orig != left_exp)
+ thd->change_item_tree(item_eq->arguments(), left_exp);
+ item_eq->in_equality_no= 0;
+ sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
+ }
+ else if (left_exp->type() == Item::ROW_ITEM)
+ {
+ /*
+ disassemple left expression and add
+ left1 = select_list_element1 and left2 = select_list_element2 ...
+ */
+ for (uint i= 0; i < ncols; i++)
+ {
+ nested_join->sj_outer_expr_list.push_back(left_exp->addr(i),
+ thd->mem_root);
+ Item_func_eq *item_eq=
+ new (thd->mem_root)
+ Item_func_eq(thd, left_exp_orig->element_index(i),
+ subq_lex->ref_pointer_array[i]);
+ if (!item_eq)
+ DBUG_RETURN(TRUE);
+ DBUG_ASSERT(left_exp->element_index(i)->is_fixed());
+ if (left_exp_orig->element_index(i) !=
+ left_exp->element_index(i))
+ thd->change_item_tree(item_eq->arguments(),
+ left_exp->element_index(i));
+ item_eq->in_equality_no= i;
+ sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
+ }
+ }
+ else
+ {
+ /*
+ add row operation
+ left = (select_list_element1, select_list_element2, ...)
+ */
+ Item_row *row= new (thd->mem_root) Item_row(thd, subq_lex->pre_fix);
+ /* fix fields on subquery was call so they should be the same */
+ if (!row)
+ DBUG_RETURN(TRUE);
+ DBUG_ASSERT(ncols == row->cols());
+ nested_join->sj_outer_expr_list.push_back(left);
+ Item_func_eq *item_eq=
+ new (thd->mem_root) Item_func_eq(thd, left_exp_orig, row);
+ if (!item_eq)
+ DBUG_RETURN(TRUE);
+ for (uint i= 0; i < row->cols(); i++)
+ {
+ if (row->element_index(i) != subq_lex->ref_pointer_array[i])
+ thd->change_item_tree(row->addr(i), subq_lex->ref_pointer_array[i]);
+ }
+ item_eq->in_equality_no= 0;
+ sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
+ }
+ /*
+ Fix the created equality and AND
+
+ Note that fix_fields() can actually fail in a meaningful way here. One
+ example is when the IN-equality is not valid, because it compares columns
+ with incompatible collations. (One can argue it would be more appropriate
+ to check for this at name resolution stage, but as a legacy of IN->EXISTS
+ we have in here).
+ */
+ if (sj_nest->sj_on_expr->fix_fields_if_needed(thd, &sj_nest->sj_on_expr))
+ {
+ DBUG_RETURN(TRUE);
+ }
+
+ /*
+ Walk through sj nest's WHERE and ON expressions and call
+ item->fix_table_changes() for all items.
+ */
+ sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr,
+ TRUE);
+ fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
+
+
+ /* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
+ subq_lex->master_unit()->exclude_level();
+
+ DBUG_EXECUTE("where",
+ print_where(sj_nest->sj_on_expr,"SJ-EXPR", QT_ORDINARY););
+
+ /* Inject sj_on_expr into the parent's WHERE or ON */
+ if (emb_tbl_nest)
+ {
+ emb_tbl_nest->on_expr= and_items(thd, emb_tbl_nest->on_expr,
+ sj_nest->sj_on_expr);
+ emb_tbl_nest->on_expr->top_level_item();
+ if (emb_tbl_nest->on_expr->fix_fields_if_needed(thd,
+ &emb_tbl_nest->on_expr))
+ {
+ DBUG_RETURN(TRUE);
+ }
+ }
+ else
+ {
+ /* Inject into the WHERE */
+ parent_join->conds= and_items(thd, parent_join->conds, sj_nest->sj_on_expr);
+ parent_join->conds->top_level_item();
+ /*
+ fix_fields must update the properties (e.g. st_select_lex::cond_count of
+ the correct select_lex.
+ */
+ save_lex= thd->lex->current_select;
+ thd->lex->current_select=parent_join->select_lex;
+ if (parent_join->conds->fix_fields_if_needed(thd, &parent_join->conds))
+ {
+ DBUG_RETURN(1);
+ }
+ thd->lex->current_select=save_lex;
+ parent_join->select_lex->where= parent_join->conds;
+ }
+
+ if (subq_lex->ftfunc_list->elements)
+ {
+ Item_func_match *ifm;
+ List_iterator_fast<Item_func_match> li(*(subq_lex->ftfunc_list));
+ while ((ifm= li++))
+ parent_lex->ftfunc_list->push_front(ifm, thd->mem_root);
+ }
+
+ parent_lex->have_merged_subqueries= TRUE;
+ /* Fatal error may have been set to by fix_after_pullout() */
+ DBUG_RETURN(thd->is_fatal_error);
+}
+
+
+const int SUBQERY_TEMPTABLE_NAME_MAX_LEN= 20;
+
+static void create_subquery_temptable_name(LEX_STRING *str, uint number)
+{
+ char *to= str->str;
+ DBUG_ASSERT(number < 10000);
+ to= strmov(to, "<subquery");
+ to= int10_to_str((int) number, to, 10);
+ to[0]= '>';
+ to[1]= 0;
+ str->length= (size_t) (to - str->str)+1;
+}
+
+
+/*
+ Convert subquery predicate into non-mergeable semi-join nest.
+
+ TODO:
+ why does this do IN-EXISTS conversion? Can't we unify it with mergeable
+ semi-joins? currently, convert_subq_to_sj() cannot fail to convert (unless
+ fatal errors)
+
+
+ RETURN
+ FALSE - Ok
+ TRUE - Fatal error
+*/
+
+static bool convert_subq_to_jtbm(JOIN *parent_join,
+ Item_in_subselect *subq_pred,
+ bool *remove_item)
+{
+ SELECT_LEX *parent_lex= parent_join->select_lex;
+ List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
+ TABLE_LIST *emb_tbl_nest= NULL; // will change when we learn to handle outer joins
+ TABLE_LIST *tl;
+ bool optimization_delayed= TRUE;
+ TABLE_LIST *jtbm;
+ LEX_STRING tbl_alias;
+ THD *thd= parent_join->thd;
+ DBUG_ENTER("convert_subq_to_jtbm");
+
+ subq_pred->set_strategy(SUBS_MATERIALIZATION);
+ subq_pred->is_jtbm_merged= TRUE;
+
+ *remove_item= TRUE;
+
+ if (!(tbl_alias.str= (char*)thd->calloc(SUBQERY_TEMPTABLE_NAME_MAX_LEN)) ||
+ !(jtbm= alloc_join_nest(thd))) //todo: this is not a join nest!
+ {
+ DBUG_RETURN(TRUE);
+ }
+
+ jtbm->join_list= emb_join_list;
+ jtbm->embedding= emb_tbl_nest;
+ jtbm->jtbm_subselect= subq_pred;
+ jtbm->nested_join= NULL;
+
+ /* Nests do not participate in those 'chains', so: */
+ /* jtbm->next_leaf= jtbm->next_local= jtbm->next_global == NULL*/
+ emb_join_list->push_back(jtbm, thd->mem_root);
+
+ /*
+ Inject the jtbm table into TABLE_LIST::next_leaf list, so that
+ make_join_statistics() and co. can find it.
+ */
+ parent_lex->leaf_tables.push_back(jtbm, thd->mem_root);
+
+ if (subq_pred->unit->first_select()->options & OPTION_SCHEMA_TABLE)
+ parent_lex->options |= OPTION_SCHEMA_TABLE;
+
+ /*
+ Same as above for TABLE_LIST::next_local chain
+ (a theory: a next_local chain always starts with ::leaf_tables
+ because view's tables are inserted after the view)
+ */
+ for (tl= (TABLE_LIST*)(parent_lex->table_list.first); tl->next_local; tl= tl->next_local)
+ {}
+ tl->next_local= jtbm;
+
+ /* A theory: no need to re-connect the next_global chain */
+ if (optimization_delayed)
+ {
+ DBUG_ASSERT(parent_join->table_count < MAX_TABLES);
+
+ jtbm->jtbm_table_no= parent_join->table_count;
+
+ create_subquery_temptable_name(&tbl_alias,
+ subq_pred->unit->first_select()->select_number);
+ jtbm->alias.str= tbl_alias.str;
+ jtbm->alias.length= tbl_alias.length;
+ parent_join->table_count++;
+ DBUG_RETURN(thd->is_fatal_error);
+ }
+ subselect_hash_sj_engine *hash_sj_engine=
+ ((subselect_hash_sj_engine*)subq_pred->engine);
+ jtbm->table= hash_sj_engine->tmp_table;
+
+ jtbm->table->tablenr= parent_join->table_count;
+ jtbm->table->map= table_map(1) << (parent_join->table_count);
+ jtbm->jtbm_table_no= jtbm->table->tablenr;
+
+ parent_join->table_count++;
+ DBUG_ASSERT(parent_join->table_count < MAX_TABLES);
+
+ Item *conds= hash_sj_engine->semi_join_conds;
+ conds->fix_after_pullout(parent_lex, &conds, TRUE);
+
+ DBUG_EXECUTE("where", print_where(conds,"SJ-EXPR", QT_ORDINARY););
+
+ create_subquery_temptable_name(&tbl_alias, hash_sj_engine->materialize_join->
+ select_lex->select_number);
+ jtbm->alias.str= tbl_alias.str;
+ jtbm->alias.length= tbl_alias.length;
+
+ parent_lex->have_merged_subqueries= TRUE;
+
+ /* Don't unlink the child subselect, as the subquery will be used. */
+
+ DBUG_RETURN(thd->is_fatal_error);
+}
+
+
+static TABLE_LIST *alloc_join_nest(THD *thd)
+{
+ TABLE_LIST *tbl;
+ if (!(tbl= (TABLE_LIST*) thd->calloc(ALIGN_SIZE(sizeof(TABLE_LIST))+
+ sizeof(NESTED_JOIN))))
+ return NULL;
+ tbl->nested_join= (NESTED_JOIN*) ((uchar*)tbl +
+ ALIGN_SIZE(sizeof(TABLE_LIST)));
+ return tbl;
+}
+
+/*
+ @Note thd->is_fatal_error can be set in case of OOM
+*/
+
+void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist)
+{
+ List_iterator<TABLE_LIST> it(*tlist);
+ TABLE_LIST *table;
+ while ((table= it++))
+ {
+ if (table->on_expr)
+ table->on_expr->fix_after_pullout(new_parent, &table->on_expr, TRUE);
+ if (table->nested_join)
+ fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
+ }
+}
+
+
+static void set_emb_join_nest(List<TABLE_LIST> *tables, TABLE_LIST *emb_sj_nest)
+{
+ List_iterator<TABLE_LIST> it(*tables);
+ TABLE_LIST *tbl;
+ while ((tbl= it++))
+ {
+ /*
+ Note: check for nested_join first.
+ derived-merged tables have tbl->table!=NULL &&
+ tbl->table->reginfo==NULL.
+ */
+ if (tbl->nested_join)
+ set_emb_join_nest(&tbl->nested_join->join_list, emb_sj_nest);
+ else if (tbl->table)
+ tbl->table->reginfo.join_tab->emb_sj_nest= emb_sj_nest;
+
+ }
+}
+
+/*
+ Pull tables out of semi-join nests, if possible
+
+ SYNOPSIS
+ pull_out_semijoin_tables()
+ join The join where to do the semi-join flattening
+
+ DESCRIPTION
+ Try to pull tables out of semi-join nests.
+
+ PRECONDITIONS
+ When this function is called, the join may have several semi-join nests
+ but it is guaranteed that one semi-join nest does not contain another.
+
+ ACTION
+ A table can be pulled out of the semi-join nest if
+ - It is a constant table, or
+ - It is accessed via eq_ref(outer_tables)
+
+ POSTCONDITIONS
+ * Tables that were pulled out have JOIN_TAB::emb_sj_nest == NULL
+ * Tables that were not pulled out have JOIN_TAB::emb_sj_nest pointing
+ to semi-join nest they are in.
+ * Semi-join nests' TABLE_LIST::sj_inner_tables is updated accordingly
+
+ This operation is (and should be) performed at each PS execution since
+ tables may become/cease to be constant across PS reexecutions.
+
+ NOTE
+ Table pullout may make uncorrelated subquery correlated. Consider this
+ example:
+
+ ... WHERE oe IN (SELECT it1.primary_key WHERE p(it1, it2) ... )
+
+ here table it1 can be pulled out (we have it1.primary_key=oe which gives
+ us functional dependency). Once it1 is pulled out, all references to it1
+ from p(it1, it2) become references to outside of the subquery and thus
+ make the subquery (i.e. its semi-join nest) correlated.
+ Making the subquery (i.e. its semi-join nest) correlated prevents us from
+ using Materialization or LooseScan to execute it.
+
+ RETURN
+ 0 - OK
+ 1 - Out of memory error
+*/
+
+int pull_out_semijoin_tables(JOIN *join)
+{
+ TABLE_LIST *sj_nest;
+ DBUG_ENTER("pull_out_semijoin_tables");
+ List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
+
+ /* Try pulling out of the each of the semi-joins */
+ while ((sj_nest= sj_list_it++))
+ {
+ List_iterator<TABLE_LIST> child_li(sj_nest->nested_join->join_list);
+ TABLE_LIST *tbl;
+ Json_writer_object trace_wrapper(join->thd);
+ Json_writer_object trace(join->thd, "semijoin_table_pullout");
+ Json_writer_array trace_arr(join->thd, "pulled_out_tables");
+
+ /*
+ Don't do table pull-out for nested joins (if we get nested joins here, it
+ means these are outer joins. It is theoretically possible to do pull-out
+ for some of the outer tables but we don't support this currently.
+ */
+ bool have_join_nest_children= FALSE;
+
+ set_emb_join_nest(&sj_nest->nested_join->join_list, sj_nest);
+
+ while ((tbl= child_li++))
+ {
+ if (tbl->nested_join)
+ {
+ have_join_nest_children= TRUE;
+ break;
+ }
+ }
+
+ table_map pulled_tables= 0;
+ table_map dep_tables= 0;
+ if (have_join_nest_children)
+ goto skip;
+
+ /*
+ Calculate set of tables within this semi-join nest that have
+ other dependent tables
+ */
+ child_li.rewind();
+ while ((tbl= child_li++))
+ {
+ TABLE *const table= tbl->table;
+ if (table &&
+ (table->reginfo.join_tab->dependent &
+ sj_nest->nested_join->used_tables))
+ dep_tables|= table->reginfo.join_tab->dependent;
+ }
+
+ /* Action #1: Mark the constant tables to be pulled out */
+ child_li.rewind();
+ while ((tbl= child_li++))
+ {
+ if (tbl->table)
+ {
+ tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
+#if 0
+ /*
+ Do not pull out tables because they are constant. This operation has
+ a problem:
+ - Some constant tables may become/cease to be constant across PS
+ re-executions
+ - Contrary to our initial assumption, it turned out that table pullout
+ operation is not easily undoable.
+
+ The solution is to leave constant tables where they are. This will
+ affect only constant tables that are 1-row or empty, tables that are
+ constant because they are accessed via eq_ref(const) access will
+ still be pulled out as functionally-dependent.
+
+ This will cause us to miss the chance to flatten some of the
+ subqueries, but since const tables do not generate many duplicates,
+ it really doesn't matter that much whether they were pulled out or
+ not.
+
+ All of this was done as fix for BUG#43768.
+ */
+ if (tbl->table->map & join->const_table_map)
+ {
+ pulled_tables |= tbl->table->map;
+ DBUG_PRINT("info", ("Table %s pulled out (reason: constant)",
+ tbl->table->alias));
+ }
+#endif
+ }
+ }
+
+ /*
+ Action #2: Find which tables we can pull out based on
+ update_ref_and_keys() data. Note that pulling one table out can allow
+ us to pull out some other tables too.
+ */
+ bool pulled_a_table;
+ do
+ {
+ pulled_a_table= FALSE;
+ child_li.rewind();
+ while ((tbl= child_li++))
+ {
+ if (tbl->table && !(pulled_tables & tbl->table->map) &&
+ !(dep_tables & tbl->table->map))
+ {
+ if (find_eq_ref_candidate(tbl->table,
+ sj_nest->nested_join->used_tables &
+ ~pulled_tables))
+ {
+ pulled_a_table= TRUE;
+ pulled_tables |= tbl->table->map;
+ DBUG_PRINT("info", ("Table %s pulled out (reason: func dep)",
+ tbl->table->alias.c_ptr_safe()));
+ trace_arr.add(tbl->table->alias.c_ptr_safe());
+ /*
+ Pulling a table out of uncorrelated subquery in general makes
+ makes it correlated. See the NOTE to this funtion.
+ */
+ sj_nest->sj_subq_pred->is_correlated= TRUE;
+ sj_nest->nested_join->sj_corr_tables|= tbl->table->map;
+ sj_nest->nested_join->sj_depends_on|= tbl->table->map;
+ }
+ }
+ }
+ } while (pulled_a_table);
+
+ child_li.rewind();
+ skip:
+ /*
+ Action #3: Move the pulled out TABLE_LIST elements to the parents.
+ */
+ table_map inner_tables= sj_nest->nested_join->used_tables &
+ ~pulled_tables;
+ /* Record the bitmap of inner tables */
+ sj_nest->sj_inner_tables= inner_tables;
+ if (pulled_tables)
+ {
+ List<TABLE_LIST> *upper_join_list= (sj_nest->embedding != NULL)?
+ (&sj_nest->embedding->nested_join->join_list):
+ (&join->select_lex->top_join_list);
+ Query_arena *arena, backup;
+ arena= join->thd->activate_stmt_arena_if_needed(&backup);
+ while ((tbl= child_li++))
+ {
+ if (tbl->table)
+ {
+ if (inner_tables & tbl->table->map)
+ {
+ /* This table is not pulled out */
+ tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
+ }
+ else
+ {
+ /* This table has been pulled out of the semi-join nest */
+ tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
+ /*
+ Pull the table up in the same way as simplify_joins() does:
+ update join_list and embedding pointers but keep next[_local]
+ pointers.
+ */
+ child_li.remove();
+ sj_nest->nested_join->used_tables &= ~tbl->table->map;
+ upper_join_list->push_back(tbl, join->thd->mem_root);
+ tbl->join_list= upper_join_list;
+ tbl->embedding= sj_nest->embedding;
+ }
+ }
+ }
+
+ /* Remove the sj-nest itself if we've removed everything from it */
+ if (!inner_tables)
+ {
+ List_iterator<TABLE_LIST> li(*upper_join_list);
+ /* Find the sj_nest in the list. */
+ while (sj_nest != li++) ;
+ li.remove();
+ /* Also remove it from the list of SJ-nests: */
+ sj_list_it.remove();
+ }
+
+ if (arena)
+ join->thd->restore_active_arena(arena, &backup);
+ }
+ }
+ DBUG_RETURN(0);
+}
+
+
+/*
+ Optimize semi-join nests that could be run with sj-materialization
+
+ SYNOPSIS
+ optimize_semijoin_nests()
+ join The join to optimize semi-join nests for
+ all_table_map Bitmap of all tables in the join
+
+ DESCRIPTION
+ Optimize each of the semi-join nests that can be run with
+ materialization. For each of the nests, we
+ - Generate the best join order for this "sub-join" and remember it;
+ - Remember the sub-join execution cost (it's part of materialization
+ cost);
+ - Calculate other costs that will be incurred if we decide
+ to use materialization strategy for this semi-join nest.
+
+ All obtained information is saved and will be used by the main join
+ optimization pass.
+
+ NOTES
+ Because of Join::reoptimize(), this function may be called multiple times.
+
+ RETURN
+ FALSE Ok
+ TRUE Out of memory error
+*/
+
+bool optimize_semijoin_nests(JOIN *join, table_map all_table_map)
+{
+ DBUG_ENTER("optimize_semijoin_nests");
+ THD *thd= join->thd;
+ List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
+ TABLE_LIST *sj_nest;
+ if (!join->select_lex->sj_nests.elements)
+ DBUG_RETURN(FALSE);
+ Json_writer_object wrapper(thd);
+ Json_writer_object trace_semijoin_nest(thd,
+ "execution_plan_for_potential_materialization");
+ Json_writer_array trace_steps_array(thd, "steps");
+ while ((sj_nest= sj_list_it++))
+ {
+ /* semi-join nests with only constant tables are not valid */
+ /// DBUG_ASSERT(sj_nest->sj_inner_tables & ~join->const_table_map);
+
+ sj_nest->sj_mat_info= NULL;
+ /*
+ The statement may have been executed with 'semijoin=on' earlier.
+ We need to verify that 'semijoin=on' still holds.
+ */
+ if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
+ optimizer_flag(join->thd, OPTIMIZER_SWITCH_MATERIALIZATION))
+ {
+ if ((sj_nest->sj_inner_tables & ~join->const_table_map) && /* not everything was pulled out */
+ !sj_nest->sj_subq_pred->is_correlated &&
+ sj_nest->sj_subq_pred->types_allow_materialization)
+ {
+ join->emb_sjm_nest= sj_nest;
+ if (choose_plan(join, all_table_map &~join->const_table_map))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ /*
+ The best plan to run the subquery is now in join->best_positions,
+ save it.
+ */
+ uint n_tables= my_count_bits(sj_nest->sj_inner_tables & ~join->const_table_map);
+ SJ_MATERIALIZATION_INFO* sjm;
+ if (!(sjm= new SJ_MATERIALIZATION_INFO) ||
+ !(sjm->positions= (POSITION*)join->thd->alloc(sizeof(POSITION)*
+ n_tables)))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ sjm->tables= n_tables;
+ sjm->is_used= FALSE;
+ double subjoin_out_rows, subjoin_read_time;
+
+ /*
+ join->get_partial_cost_and_fanout(n_tables + join->const_tables,
+ table_map(-1),
+ &subjoin_read_time,
+ &subjoin_out_rows);
+ */
+ join->get_prefix_cost_and_fanout(n_tables,
+ &subjoin_read_time,
+ &subjoin_out_rows);
+
+ sjm->materialization_cost.convert_from_cost(subjoin_read_time);
+ sjm->rows_with_duplicates= sjm->rows= subjoin_out_rows;
+
+ // Don't use the following list because it has "stale" items. use
+ // ref_pointer_array instead:
+ //
+ //List<Item> &right_expr_list=
+ // sj_nest->sj_subq_pred->unit->first_select()->item_list;
+ /*
+ Adjust output cardinality estimates. If the subquery has form
+
+ ... oe IN (SELECT t1.colX, t2.colY, func(X,Y,Z) )
+
+ then the number of distinct output record combinations has an
+ upper bound of product of number of records matching the tables
+ that are used by the SELECT clause.
+ TODO:
+ We can get a more precise estimate if we
+ - use rec_per_key cardinality estimates. For simple cases like
+ "oe IN (SELECT t.key ...)" it is trivial.
+ - Functional dependencies between the tables in the semi-join
+ nest (the payoff is probably less here?)
+
+ See also get_post_group_estimate().
+ */
+ SELECT_LEX *subq_select= sj_nest->sj_subq_pred->unit->first_select();
+ {
+ for (uint i=0 ; i < join->const_tables + sjm->tables ; i++)
+ {
+ JOIN_TAB *tab= join->best_positions[i].table;
+ join->map2table[tab->table->tablenr]= tab;
+ }
+ table_map map= 0;
+ for (uint i=0; i < subq_select->item_list.elements; i++)
+ map|= subq_select->ref_pointer_array[i]->used_tables();
+ map= map & ~PSEUDO_TABLE_BITS;
+ Table_map_iterator tm_it(map);
+ int tableno;
+ double rows= 1.0;
+ while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
+ rows= COST_MULT(rows,
+ join->map2table[tableno]->table->opt_range_condition_rows);
+ sjm->rows= MY_MIN(sjm->rows, rows);
+ }
+ memcpy((uchar*) sjm->positions,
+ (uchar*) (join->best_positions + join->const_tables),
+ sizeof(POSITION) * n_tables);
+
+ /*
+ Calculate temporary table parameters and usage costs
+ */
+ uint rowlen= get_tmp_table_rec_length(subq_select->ref_pointer_array,
+ subq_select->item_list.elements);
+ double lookup_cost= get_tmp_table_lookup_cost(join->thd,
+ subjoin_out_rows, rowlen);
+ double write_cost= get_tmp_table_write_cost(join->thd,
+ subjoin_out_rows, rowlen);
+
+ /*
+ Let materialization cost include the cost to write the data into the
+ temporary table:
+ */
+ sjm->materialization_cost.add_io(subjoin_out_rows, write_cost);
+
+ /*
+ Set the cost to do a full scan of the temptable (will need this to
+ consider doing sjm-scan):
+ */
+ sjm->scan_cost.reset();
+ sjm->scan_cost.add_io(sjm->rows, lookup_cost);
+
+ sjm->lookup_cost.convert_from_cost(lookup_cost);
+ sj_nest->sj_mat_info= sjm;
+ DBUG_EXECUTE("opt", print_sjm(sjm););
+ }
+ }
+ }
+ join->emb_sjm_nest= NULL;
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ Get estimated record length for semi-join materialization temptable
+
+ SYNOPSIS
+ get_tmp_table_rec_length()
+ items IN subquery's select list.
+
+ DESCRIPTION
+ Calculate estimated record length for semi-join materialization
+ temptable. It's an estimate because we don't follow every bit of
+ create_tmp_table()'s logic. This isn't necessary as the return value of
+ this function is used only for cost calculations.
+
+ RETURN
+ Length of the temptable record, in bytes
+*/
+
+static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements)
+{
+ uint len= 0;
+ Item *item;
+ //List_iterator<Item> it(items);
+ for (uint i= 0; i < elements ; i++)
+ {
+ item = p_items[i];
+ switch (item->result_type()) {
+ case REAL_RESULT:
+ len += sizeof(double);
+ break;
+ case INT_RESULT:
+ if (item->max_length >= (MY_INT32_NUM_DECIMAL_DIGITS - 1))
+ len += 8;
+ else
+ len += 4;
+ break;
+ case STRING_RESULT:
+ enum enum_field_types type;
+ /* DATE/TIME and GEOMETRY fields have STRING_RESULT result type. */
+ if ((type= item->field_type()) == MYSQL_TYPE_DATETIME ||
+ type == MYSQL_TYPE_TIME || type == MYSQL_TYPE_DATE ||
+ type == MYSQL_TYPE_TIMESTAMP || type == MYSQL_TYPE_GEOMETRY)
+ len += 8;
+ else
+ len += item->max_length;
+ break;
+ case DECIMAL_RESULT:
+ len += 10;
+ break;
+ case ROW_RESULT:
+ default:
+ DBUG_ASSERT(0); /* purecov: deadcode */
+ break;
+ }
+ }
+ return len;
+}
+
+
+/**
+ The cost of a lookup into a unique hash/btree index on a temporary table
+ with 'row_count' rows each of size 'row_size'.
+
+ @param thd current query context
+ @param row_count number of rows in the temp table
+ @param row_size average size in bytes of the rows
+
+ @return the cost of one lookup
+*/
+
+double
+get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size)
+{
+ if (row_count > thd->variables.max_heap_table_size / (double) row_size)
+ return (double) DISK_TEMPTABLE_LOOKUP_COST;
+ else
+ return (double) HEAP_TEMPTABLE_LOOKUP_COST;
+}
+
+/**
+ The cost of writing a row into a temporary table with 'row_count' unique
+ rows each of size 'row_size'.
+
+ @param thd current query context
+ @param row_count number of rows in the temp table
+ @param row_size average size in bytes of the rows
+
+ @return the cost of writing one row
+*/
+
+double
+get_tmp_table_write_cost(THD *thd, double row_count, uint row_size)
+{
+ double lookup_cost= get_tmp_table_lookup_cost(thd, row_count, row_size);
+ /*
+ TODO:
+ This is an optimistic estimate. Add additional costs resulting from
+ actually writing the row to memory/disk and possible index reorganization.
+ */
+ return lookup_cost;
+}
+
+
+/*
+ Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
+
+ SYNOPSIS
+ find_eq_ref_candidate()
+ table Table to be checked
+ sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
+ count.
+
+ DESCRIPTION
+ Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
+
+ TODO
+ Check again if it is feasible to factor common parts with constant table
+ search
+
+ Also check if it's feasible to factor common parts with table elimination
+
+ RETURN
+ TRUE - There exists an eq_ref(outer-tables) candidate
+ FALSE - Otherwise
+*/
+
+bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables)
+{
+ KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
+
+ if (keyuse)
+ {
+ do
+ {
+ uint key= keyuse->key;
+ key_part_map bound_parts= 0;
+ if (!keyuse->is_for_hash_join() &&
+ (table->key_info[key].flags & HA_NOSAME))
+ {
+ KEY *keyinfo= table->key_info + key;
+ do /* For all equalities on all key parts */
+ {
+ /*
+ Check if this is "t.keypart = expr(outer_tables)
+
+ Don't allow variants that can produce duplicates:
+ - Dont allow "ref or null"
+ - the keyuse (that is, the operation) must be null-rejecting,
+ unless the other expression is non-NULLable.
+ */
+ if (!(keyuse->used_tables & sj_inner_tables) &&
+ !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) &&
+ (keyuse->null_rejecting || !keyuse->val->maybe_null))
+ {
+ bound_parts |= 1 << keyuse->keypart;
+ }
+ keyuse++;
+ } while (keyuse->key == key && keyuse->table == table);
+
+ if (bound_parts == PREV_BITS(uint, keyinfo->user_defined_key_parts))
+ return TRUE;
+ }
+ else
+ {
+ do
+ {
+ keyuse++;
+ } while (keyuse->key == key && keyuse->table == table);
+ }
+ } while (keyuse->table == table);
+ }
+ return FALSE;
+}
+
+
+/*
+ Do semi-join optimization step after we've added a new tab to join prefix
+
+ SYNOPSIS
+ advance_sj_state()
+ join The join we're optimizing
+ remaining_tables Tables not in the join prefix
+ new_join_tab Join tab we've just added to the join prefix
+ idx Index of this join tab (i.e. number of tables
+ in the prefix minus one)
+ current_record_count INOUT Estimate of #records in join prefix's output
+ current_read_time INOUT Cost to execute the join prefix
+ loose_scan_pos IN A POSITION with LooseScan plan to access
+ table new_join_tab
+ (produced by the last best_access_path call)
+
+ DESCRIPTION
+ Update semi-join optimization state after we've added another tab (table
+ and access method) to the join prefix.
+
+ The state is maintained in join->positions[#prefix_size]. Each of the
+ available strategies has its own state variables.
+
+ for each semi-join strategy
+ {
+ update strategy's state variables;
+
+ if (join prefix has all the tables that are needed to consider
+ using this strategy for the semi-join(s))
+ {
+ calculate cost of using the strategy
+ if ((this is the first strategy to handle the semi-join nest(s) ||
+ the cost is less than other strategies))
+ {
+ // Pick this strategy
+ pos->sj_strategy= ..
+ ..
+ }
+ }
+
+ Most of the new state is saved join->positions[idx] (and hence no undo
+ is necessary). Several members of class JOIN are updated also, these
+ changes can be rolled back with restore_prev_sj_state().
+
+ See setup_semijoin_dups_elimination() for a description of what kinds of
+ join prefixes each strategy can handle.
+*/
+
+bool is_multiple_semi_joins(JOIN *join, POSITION *prefix, uint idx, table_map inner_tables)
+{
+ for (int i= (int)idx; i >= 0; i--)
+ {
+ TABLE_LIST *emb_sj_nest;
+ if ((emb_sj_nest= prefix[i].table->emb_sj_nest))
+ {
+ if (inner_tables & emb_sj_nest->sj_inner_tables)
+ return !MY_TEST(inner_tables == (emb_sj_nest->sj_inner_tables &
+ ~join->const_table_map));
+ }
+ }
+ return FALSE;
+}
+
+
+void advance_sj_state(JOIN *join, table_map remaining_tables, uint idx,
+ double *current_record_count, double *current_read_time,
+ POSITION *loose_scan_pos)
+{
+ POSITION *pos= join->positions + idx;
+ const JOIN_TAB *new_join_tab= pos->table;
+
+#ifdef HAVE_valgrind
+ new (&pos->firstmatch_picker) Firstmatch_picker;
+ new (&pos->loosescan_picker) LooseScan_picker;
+ new (&pos->sjmat_picker) Sj_materialization_picker;
+ new (&pos->dups_weedout_picker) Duplicate_weedout_picker;
+#endif
+
+ if (join->emb_sjm_nest || //(1)
+ !join->select_lex->have_merged_subqueries) //(2)
+ {
+ /*
+ (1): We're performing optimization inside SJ-Materialization nest:
+ - there are no other semi-joins inside semi-join nests
+ - attempts to build semi-join strategies here will confuse
+ the optimizer, so bail out.
+ (2): Don't waste time on semi-join optimizations if we don't have any
+ semi-joins
+ */
+ pos->sj_strategy= SJ_OPT_NONE;
+ return;
+ }
+
+ Semi_join_strategy_picker *pickers[]=
+ {
+ &pos->firstmatch_picker,
+ &pos->loosescan_picker,
+ &pos->sjmat_picker,
+ &pos->dups_weedout_picker,
+ NULL,
+ };
+ Json_writer_array trace_steps(join->thd, "semijoin_strategy_choice");
+ /*
+ Update join->cur_sj_inner_tables (Used by FirstMatch in this function and
+ LooseScan detector in best_access_path)
+ */
+ remaining_tables &= ~new_join_tab->table->map;
+ table_map dups_producing_tables, UNINIT_VAR(prev_dups_producing_tables),
+ UNINIT_VAR(prev_sjm_lookup_tables);
+
+ if (idx == join->const_tables)
+ dups_producing_tables= 0;
+ else
+ dups_producing_tables= pos[-1].dups_producing_tables;
+
+ TABLE_LIST *emb_sj_nest;
+ if ((emb_sj_nest= new_join_tab->emb_sj_nest))
+ dups_producing_tables |= emb_sj_nest->sj_inner_tables;
+
+ Semi_join_strategy_picker **strategy, **prev_strategy= 0;
+ if (idx == join->const_tables)
+ {
+ /* First table, initialize pickers */
+ for (strategy= pickers; *strategy != NULL; strategy++)
+ (*strategy)->set_empty();
+ pos->inner_tables_handled_with_other_sjs= 0;
+ }
+ else
+ {
+ for (strategy= pickers; *strategy != NULL; strategy++)
+ {
+ (*strategy)->set_from_prev(pos - 1);
+ }
+ pos->inner_tables_handled_with_other_sjs=
+ pos[-1].inner_tables_handled_with_other_sjs;
+ }
+
+ pos->prefix_cost.convert_from_cost(*current_read_time);
+ pos->prefix_record_count= *current_record_count;
+
+ {
+ pos->sj_strategy= SJ_OPT_NONE;
+
+ for (strategy= pickers; *strategy != NULL; strategy++)
+ {
+ table_map handled_fanout;
+ sj_strategy_enum sj_strategy;
+ double rec_count= *current_record_count;
+ double read_time= *current_read_time;
+ if ((*strategy)->check_qep(join, idx, remaining_tables,
+ new_join_tab,
+ &rec_count,
+ &read_time,
+ &handled_fanout,
+ &sj_strategy,
+ loose_scan_pos))
+ {
+ /*
+ It's possible to use the strategy. Use it, if
+ - it removes semi-join fanout that was not removed before
+ - using it is cheaper than using something else,
+ and {if some other strategy has removed fanout
+ that this strategy is trying to remove, then it
+ did remove the fanout only for one semi-join}
+ This is to avoid a situation when
+ 1. strategy X removes fanout for semijoin X,Y
+ 2. using strategy Z is cheaper, but it only removes
+ fanout from semijoin X.
+ 3. We have no clue what to do about fanount of semi-join Y.
+ */
+ if ((dups_producing_tables & handled_fanout) ||
+ (read_time < *current_read_time &&
+ !(handled_fanout & pos->inner_tables_handled_with_other_sjs)))
+ {
+ DBUG_ASSERT(pos->sj_strategy != sj_strategy);
+ /*
+ If the strategy chosen first time or
+ the strategy replace strategy which was used to exectly the same
+ tables
+ */
+ if (pos->sj_strategy == SJ_OPT_NONE ||
+ handled_fanout ==
+ (prev_dups_producing_tables ^ dups_producing_tables))
+ {
+ prev_strategy= strategy;
+ if (pos->sj_strategy == SJ_OPT_NONE)
+ {
+ prev_dups_producing_tables= dups_producing_tables;
+ prev_sjm_lookup_tables= join->sjm_lookup_tables;
+ }
+ /* Mark strategy as used */
+ (*strategy)->mark_used();
+ pos->sj_strategy= sj_strategy;
+ if (sj_strategy == SJ_OPT_MATERIALIZE)
+ join->sjm_lookup_tables |= handled_fanout;
+ else
+ join->sjm_lookup_tables &= ~handled_fanout;
+ *current_read_time= read_time;
+ *current_record_count= rec_count;
+ dups_producing_tables &= ~handled_fanout;
+
+ //TODO: update bitmap of semi-joins that were handled together with
+ // others.
+ if (is_multiple_semi_joins(join, join->positions, idx,
+ handled_fanout))
+ pos->inner_tables_handled_with_other_sjs |= handled_fanout;
+ }
+ else
+ {
+ /* Conflict fall to most general variant */
+ (*prev_strategy)->set_empty();
+ dups_producing_tables= prev_dups_producing_tables;
+ join->sjm_lookup_tables= prev_sjm_lookup_tables;
+ // mark it 'none' to avpoid loops
+ pos->sj_strategy= SJ_OPT_NONE;
+ // next skip to last;
+ strategy= pickers +
+ (sizeof(pickers)/sizeof(Semi_join_strategy_picker*) - 3);
+ continue;
+ }
+ }
+ else
+ {
+ /* We decided not to apply the strategy. */
+ (*strategy)->set_empty();
+ }
+ }
+ }
+
+ if (unlikely(join->thd->trace_started() && pos->sj_strategy != SJ_OPT_NONE))
+ {
+ Json_writer_object tr(join->thd);
+ const char *sname;
+ switch (pos->sj_strategy) {
+ case SJ_OPT_MATERIALIZE:
+ sname= "SJ-Materialization";
+ break;
+ case SJ_OPT_MATERIALIZE_SCAN:
+ sname= "SJ-Materialization-Scan";
+ break;
+ case SJ_OPT_FIRST_MATCH:
+ sname= "FirstMatch";
+ break;
+ case SJ_OPT_DUPS_WEEDOUT:
+ sname= "DuplicateWeedout";
+ break;
+ case SJ_OPT_LOOSE_SCAN:
+ sname= "LooseScan";
+ break;
+ default:
+ DBUG_ASSERT(0);
+ sname="Invalid";
+ }
+ tr.add("chosen_strategy", sname);
+ }
+ }
+
+ if ((emb_sj_nest= new_join_tab->emb_sj_nest))
+ {
+ join->cur_sj_inner_tables |= emb_sj_nest->sj_inner_tables;
+
+ /* Remove the sj_nest if all of its SJ-inner tables are in cur_table_map */
+ if (!(remaining_tables &
+ emb_sj_nest->sj_inner_tables & ~new_join_tab->table->map))
+ join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
+ }
+
+ pos->prefix_cost.convert_from_cost(*current_read_time);
+ pos->prefix_record_count= *current_record_count;
+ pos->dups_producing_tables= dups_producing_tables;
+}
+
+
+void Sj_materialization_picker::set_from_prev(POSITION *prev)
+{
+ if (prev->sjmat_picker.is_used)
+ set_empty();
+ else
+ {
+ sjm_scan_need_tables= prev->sjmat_picker.sjm_scan_need_tables;
+ sjm_scan_last_inner= prev->sjmat_picker.sjm_scan_last_inner;
+ }
+ is_used= FALSE;
+}
+
+
+bool Sj_materialization_picker::check_qep(JOIN *join,
+ uint idx,
+ table_map remaining_tables,
+ const JOIN_TAB *new_join_tab,
+ double *record_count,
+ double *read_time,
+ table_map *handled_fanout,
+ sj_strategy_enum *strategy,
+ POSITION *loose_scan_pos)
+{
+ bool sjm_scan;
+ SJ_MATERIALIZATION_INFO *mat_info;
+ THD *thd= join->thd;
+ if ((mat_info= at_sjmat_pos(join, remaining_tables,
+ new_join_tab, idx, &sjm_scan)))
+ {
+ if (sjm_scan)
+ {
+ /*
+ We can't yet evaluate this option yet. This is because we can't
+ accout for fanout of sj-inner tables yet:
+
+ ntX SJM-SCAN(it1 ... itN) | ot1 ... otN |
+ ^(1) ^(2)
+
+ we're now at position (1). SJM temptable in general has multiple
+ records, so at point (1) we'll get the fanout from sj-inner tables (ie
+ there will be multiple record combinations).
+
+ The final join result will not contain any semi-join produced
+ fanout, i.e. tables within SJM-SCAN(...) will not contribute to
+ the cardinality of the join output. Extra fanout produced by
+ SJM-SCAN(...) will be 'absorbed' into fanout produced by ot1 ... otN.
+
+ The simple way to model this is to remove SJM-SCAN(...) fanout once
+ we reach the point #2.
+ */
+ sjm_scan_need_tables=
+ new_join_tab->emb_sj_nest->sj_inner_tables |
+ new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
+ new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
+ sjm_scan_last_inner= idx;
+ }
+ else
+ {
+ /* This is SJ-Materialization with lookups */
+ Cost_estimate prefix_cost;
+ signed int first_tab= (int)idx - mat_info->tables;
+ double prefix_rec_count;
+ Json_writer_object trace(join->thd);
+ trace.add("strategy", "SJ-Materialization");
+
+ if (first_tab < (int)join->const_tables)
+ {
+ prefix_cost.reset();
+ prefix_rec_count= 1.0;
+ }
+ else
+ {
+ prefix_cost= join->positions[first_tab].prefix_cost;
+ prefix_rec_count= join->positions[first_tab].prefix_record_count;
+ }
+
+ double mat_read_time= prefix_cost.total_cost();
+ mat_read_time=
+ COST_ADD(mat_read_time,
+ COST_ADD(mat_info->materialization_cost.total_cost(),
+ COST_MULT(prefix_rec_count,
+ mat_info->lookup_cost.total_cost())));
+
+ /*
+ NOTE: When we pick to use SJM[-Scan] we don't memcpy its POSITION
+ elements to join->positions as that makes it hard to return things
+ back when making one step back in join optimization. That's done
+ after the QEP has been chosen.
+ */
+ *read_time= mat_read_time;
+ *record_count= prefix_rec_count;
+ *handled_fanout= new_join_tab->emb_sj_nest->sj_inner_tables;
+ *strategy= SJ_OPT_MATERIALIZE;
+ if (unlikely(trace.trace_started()))
+ {
+ trace.add("records", *record_count);
+ trace.add("read_time", *read_time);
+ }
+ return TRUE;
+ }
+ }
+
+ /* 4.A SJM-Scan second phase check */
+ if (sjm_scan_need_tables && /* Have SJM-Scan prefix */
+ !(sjm_scan_need_tables & remaining_tables))
+ {
+ Json_writer_object trace(join->thd);
+ trace.add("strategy", "SJ-Materialization-Scan");
+ TABLE_LIST *mat_nest=
+ join->positions[sjm_scan_last_inner].table->emb_sj_nest;
+ SJ_MATERIALIZATION_INFO *mat_info= mat_nest->sj_mat_info;
+
+ double prefix_cost;
+ double prefix_rec_count;
+ int first_tab= sjm_scan_last_inner + 1 - mat_info->tables;
+ /* Get the prefix cost */
+ if (first_tab == (int)join->const_tables)
+ {
+ prefix_rec_count= 1.0;
+ prefix_cost= 0.0;
+ }
+ else
+ {
+ prefix_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
+ prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
+ }
+
+ /* Add materialization cost */
+ prefix_cost=
+ COST_ADD(prefix_cost,
+ COST_ADD(mat_info->materialization_cost.total_cost(),
+ COST_MULT(prefix_rec_count,
+ mat_info->scan_cost.total_cost())));
+ prefix_rec_count= COST_MULT(prefix_rec_count, mat_info->rows);
+
+ uint i;
+ table_map rem_tables= remaining_tables;
+ for (i= idx; i != (first_tab + mat_info->tables - 1); i--)
+ rem_tables |= join->positions[i].table->table->map;
+
+ POSITION curpos, dummy;
+ /* Need to re-run best-access-path as we prefix_rec_count has changed */
+ bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
+ Json_writer_temp_disable trace_semijoin_mat_scan(thd);
+ for (i= first_tab + mat_info->tables; i <= idx; i++)
+ {
+ best_access_path(join, join->positions[i].table, rem_tables,
+ join->positions, i,
+ disable_jbuf, prefix_rec_count, &curpos, &dummy);
+ prefix_rec_count= COST_MULT(prefix_rec_count, curpos.records_read);
+ prefix_cost= COST_ADD(prefix_cost, curpos.read_time);
+ prefix_cost= COST_ADD(prefix_cost,
+ prefix_rec_count / TIME_FOR_COMPARE);
+ //TODO: take into account join condition selectivity here
+ }
+
+ *strategy= SJ_OPT_MATERIALIZE_SCAN;
+ *read_time= prefix_cost;
+ /*
+ Note: the next line means we did not remove the subquery's fanout from
+ *record_count. It needs to be removed, as the join prefix is
+
+ ntX SJM-SCAN(it1 ... itN) | (ot1 ... otN) ...
+
+ here, the SJM-SCAN may have introduced subquery's fanout (duplicate rows,
+ rows that don't have matches in ot1_i). All this fanout is gone after
+ table otN (or earlier) but taking it into account is hard.
+
+ Some consolation here is that SJM-Scan strategy is applicable when the
+ subquery is smaller than tables otX. If the subquery has large cardinality,
+ we can greatly overestimate *record_count here, but it doesn't matter as
+ SJ-Materialization-Lookup is a better strategy anyway.
+ */
+ *record_count= prefix_rec_count;
+ *handled_fanout= mat_nest->sj_inner_tables;
+ if (unlikely(trace.trace_started()))
+ {
+ trace.add("records", *record_count);
+ trace.add("read_time", *read_time);
+ }
+ return TRUE;
+ }
+ return FALSE;
+}
+
+
+void LooseScan_picker::set_from_prev(POSITION *prev)
+{
+ if (prev->loosescan_picker.is_used)
+ set_empty();
+ else
+ {
+ first_loosescan_table= prev->loosescan_picker.first_loosescan_table;
+ loosescan_need_tables= prev->loosescan_picker.loosescan_need_tables;
+ }
+ is_used= FALSE;
+}
+
+
+bool LooseScan_picker::check_qep(JOIN *join,
+ uint idx,
+ table_map remaining_tables,
+ const JOIN_TAB *new_join_tab,
+ double *record_count,
+ double *read_time,
+ table_map *handled_fanout,
+ sj_strategy_enum *strategy,
+ POSITION *loose_scan_pos)
+{
+ POSITION *first= join->positions + first_loosescan_table;
+ /*
+ LooseScan strategy can't handle interleaving between tables from the
+ semi-join that LooseScan is handling and any other tables.
+
+ If we were considering LooseScan for the join prefix (1)
+ and the table we're adding creates an interleaving (2)
+ then
+ stop considering loose scan
+ */
+ if ((first_loosescan_table != MAX_TABLES) && // (1)
+ (first->table->emb_sj_nest->sj_inner_tables & remaining_tables) && //(2)
+ new_join_tab->emb_sj_nest != first->table->emb_sj_nest) //(2)
+ {
+ first_loosescan_table= MAX_TABLES;
+ }
+
+ /*
+ If we got an option to use LooseScan for the current table, start
+ considering using LooseScan strategy
+ */
+ if (loose_scan_pos->read_time != DBL_MAX && !join->outer_join)
+ {
+ first_loosescan_table= idx;
+ loosescan_need_tables=
+ new_join_tab->emb_sj_nest->sj_inner_tables |
+ new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
+ new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
+ }
+
+ if ((first_loosescan_table != MAX_TABLES) &&
+ !(remaining_tables & loosescan_need_tables) &&
+ (new_join_tab->table->map & loosescan_need_tables))
+ {
+ Json_writer_object trace(join->thd);
+ trace.add("strategy", "LooseScan");
+ /*
+ Ok we have LooseScan plan and also have all LooseScan sj-nest's
+ inner tables and outer correlated tables into the prefix.
+ */
+
+ first= join->positions + first_loosescan_table;
+ uint n_tables= my_count_bits(first->table->emb_sj_nest->sj_inner_tables);
+ /* Got a complete LooseScan range. Calculate its cost */
+ /*
+ The same problem as with FirstMatch - we need to save POSITIONs
+ somewhere but reserving space for all cases would require too
+ much space. We will re-calculate POSITION structures later on.
+ */
+ bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
+ optimize_wo_join_buffering(join, first_loosescan_table, idx,
+ remaining_tables,
+ TRUE, //first_alt
+ disable_jbuf ? join->table_count :
+ first_loosescan_table + n_tables,
+ record_count,
+ read_time);
+ /*
+ We don't yet have any other strategies that could handle this
+ semi-join nest (the other options are Duplicate Elimination or
+ Materialization, which need at least the same set of tables in
+ the join prefix to be considered) so unconditionally pick the
+ LooseScan.
+ */
+ *strategy= SJ_OPT_LOOSE_SCAN;
+ *handled_fanout= first->table->emb_sj_nest->sj_inner_tables;
+ if (unlikely(trace.trace_started()))
+ {
+ trace.add("records", *record_count);
+ trace.add("read_time", *read_time);
+ }
+ return TRUE;
+ }
+ return FALSE;
+}
+
+void Firstmatch_picker::set_from_prev(POSITION *prev)
+{
+ if (prev->firstmatch_picker.is_used)
+ invalidate_firstmatch_prefix();
+ else
+ {
+ first_firstmatch_table= prev->firstmatch_picker.first_firstmatch_table;
+ first_firstmatch_rtbl= prev->firstmatch_picker.first_firstmatch_rtbl;
+ firstmatch_need_tables= prev->firstmatch_picker.firstmatch_need_tables;
+ }
+ is_used= FALSE;
+}
+
+bool Firstmatch_picker::check_qep(JOIN *join,
+ uint idx,
+ table_map remaining_tables,
+ const JOIN_TAB *new_join_tab,
+ double *record_count,
+ double *read_time,
+ table_map *handled_fanout,
+ sj_strategy_enum *strategy,
+ POSITION *loose_scan_pos)
+{
+ if (new_join_tab->emb_sj_nest &&
+ optimizer_flag(join->thd, OPTIMIZER_SWITCH_FIRSTMATCH) &&
+ !join->outer_join)
+ {
+ const table_map outer_corr_tables=
+ new_join_tab->emb_sj_nest->nested_join->sj_corr_tables |
+ new_join_tab->emb_sj_nest->nested_join->sj_depends_on;
+ const table_map sj_inner_tables=
+ new_join_tab->emb_sj_nest->sj_inner_tables & ~join->const_table_map;
+
+ /*
+ Enter condition:
+ 1. The next join tab belongs to semi-join nest
+ (verified for the encompassing code block above).
+ 2. We're not in a duplicate producer range yet
+ 3. All outer tables that
+ - the subquery is correlated with, or
+ - referred to from the outer_expr
+ are in the join prefix
+ 4. All inner tables are still part of remaining_tables.
+ */
+ if (!join->cur_sj_inner_tables && // (2)
+ !(remaining_tables & outer_corr_tables) && // (3)
+ (sj_inner_tables == // (4)
+ ((remaining_tables | new_join_tab->table->map) & sj_inner_tables)))
+ {
+ /* Start tracking potential FirstMatch range */
+ first_firstmatch_table= idx;
+ firstmatch_need_tables= sj_inner_tables;
+ first_firstmatch_rtbl= remaining_tables;
+ }
+
+ if (in_firstmatch_prefix())
+ {
+ if (outer_corr_tables & first_firstmatch_rtbl)
+ {
+ /*
+ Trying to add an sj-inner table whose sj-nest has an outer correlated
+ table that was not in the prefix. This means FirstMatch can't be used.
+ */
+ invalidate_firstmatch_prefix();
+ }
+ else
+ {
+ /* Record that we need all of this semi-join's inner tables, too */
+ firstmatch_need_tables|= sj_inner_tables;
+ }
+
+ if (in_firstmatch_prefix() &&
+ !(firstmatch_need_tables & remaining_tables))
+ {
+ Json_writer_object trace(join->thd);
+ trace.add("strategy", "FirstMatch");
+ /*
+ Got a complete FirstMatch range. Calculate correct costs and fanout
+ */
+
+ if (idx == first_firstmatch_table &&
+ optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN_WITH_CACHE))
+ {
+ /*
+ An important special case: only one inner table, and @@optimizer_switch
+ allows join buffering.
+ - read_time is the same (i.e. FirstMatch doesn't add any cost
+ - remove fanout added by the last table
+ */
+ if (*record_count)
+ *record_count /= join->positions[idx].records_read;
+ }
+ else
+ {
+ optimize_wo_join_buffering(join, first_firstmatch_table, idx,
+ remaining_tables, FALSE, idx,
+ record_count,
+ read_time);
+ }
+ /*
+ We ought to save the alternate POSITIONs produced by
+ optimize_wo_join_buffering but the problem is that providing save
+ space uses too much space. Instead, we will re-calculate the
+ alternate POSITIONs after we've picked the best QEP.
+ */
+ *handled_fanout= firstmatch_need_tables;
+ /* *record_count and *read_time were set by the above call */
+ *strategy= SJ_OPT_FIRST_MATCH;
+ if (unlikely(trace.trace_started()))
+ {
+ trace.add("records", *record_count);
+ trace.add("read_time", *read_time);
+ }
+ return TRUE;
+ }
+ }
+ }
+ else
+ invalidate_firstmatch_prefix();
+ return FALSE;
+}
+
+
+void Duplicate_weedout_picker::set_from_prev(POSITION *prev)
+{
+ if (prev->dups_weedout_picker.is_used)
+ set_empty();
+ else
+ {
+ dupsweedout_tables= prev->dups_weedout_picker.dupsweedout_tables;
+ first_dupsweedout_table= prev->dups_weedout_picker.first_dupsweedout_table;
+ }
+ is_used= FALSE;
+}
+
+
+bool Duplicate_weedout_picker::check_qep(JOIN *join,
+ uint idx,
+ table_map remaining_tables,
+ const JOIN_TAB *new_join_tab,
+ double *record_count,
+ double *read_time,
+ table_map *handled_fanout,
+ sj_strategy_enum *strategy,
+ POSITION *loose_scan_pos
+ )
+{
+ TABLE_LIST *nest;
+ if ((nest= new_join_tab->emb_sj_nest))
+ {
+ if (!dupsweedout_tables)
+ first_dupsweedout_table= idx;
+
+ dupsweedout_tables |= nest->sj_inner_tables |
+ nest->nested_join->sj_depends_on |
+ nest->nested_join->sj_corr_tables;
+ }
+
+ if (dupsweedout_tables)
+ {
+ /* we're in the process of constructing a DuplicateWeedout range */
+ TABLE_LIST *emb= new_join_tab->table->pos_in_table_list->embedding;
+ /* and we've entered an inner side of an outer join*/
+ if (emb && emb->on_expr)
+ dupsweedout_tables |= emb->nested_join->used_tables;
+ }
+
+ /* If this is the last table that we need for DuplicateWeedout range */
+ if (dupsweedout_tables && !(remaining_tables & ~new_join_tab->table->map &
+ dupsweedout_tables))
+ {
+ /*
+ Ok, reached a state where we could put a dups weedout point.
+ Walk back and calculate
+ - the join cost (this is needed as the accumulated cost may assume
+ some other duplicate elimination method)
+ - extra fanout that will be removed by duplicate elimination
+ - duplicate elimination cost
+ There are two cases:
+ 1. We have other strategy/ies to remove all of the duplicates.
+ 2. We don't.
+
+ We need to calculate the cost in case #2 also because we need to make
+ choice between this join order and others.
+ */
+ uint first_tab= first_dupsweedout_table;
+ double dups_cost;
+ double prefix_rec_count;
+ double sj_inner_fanout= 1.0;
+ double sj_outer_fanout= 1.0;
+ uint temptable_rec_size;
+ Json_writer_object trace(join->thd);
+ trace.add("strategy", "DuplicateWeedout");
+
+ if (first_tab == join->const_tables)
+ {
+ prefix_rec_count= 1.0;
+ temptable_rec_size= 0;
+ dups_cost= 0.0;
+ }
+ else
+ {
+ dups_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
+ prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
+ temptable_rec_size= 8; /* This is not true but we'll make it so */
+ }
+
+ table_map dups_removed_fanout= 0;
+ double current_fanout= prefix_rec_count;
+ for (uint j= first_dupsweedout_table; j <= idx; j++)
+ {
+ POSITION *p= join->positions + j;
+ current_fanout= COST_MULT(current_fanout, p->records_read);
+ dups_cost= COST_ADD(dups_cost,
+ COST_ADD(p->read_time,
+ current_fanout / TIME_FOR_COMPARE));
+ if (p->table->emb_sj_nest)
+ {
+ sj_inner_fanout= COST_MULT(sj_inner_fanout, p->records_read);
+ dups_removed_fanout |= p->table->table->map;
+ }
+ else
+ {
+ sj_outer_fanout= COST_MULT(sj_outer_fanout, p->records_read);
+ temptable_rec_size += p->table->table->file->ref_length;
+ }
+ }
+
+ /*
+ Add the cost of temptable use. The table will have sj_outer_fanout
+ records, and we will make
+ - sj_outer_fanout table writes
+ - sj_inner_fanout*sj_outer_fanout lookups.
+
+ */
+ double one_lookup_cost= get_tmp_table_lookup_cost(join->thd,
+ sj_outer_fanout,
+ temptable_rec_size);
+ double one_write_cost= get_tmp_table_write_cost(join->thd,
+ sj_outer_fanout,
+ temptable_rec_size);
+
+ double write_cost= COST_MULT(join->positions[first_tab].prefix_record_count,
+ sj_outer_fanout * one_write_cost);
+ double full_lookup_cost=
+ COST_MULT(join->positions[first_tab].prefix_record_count,
+ COST_MULT(sj_outer_fanout,
+ sj_inner_fanout * one_lookup_cost));
+ dups_cost= COST_ADD(dups_cost, COST_ADD(write_cost, full_lookup_cost));
+
+ *read_time= dups_cost;
+ *record_count= prefix_rec_count * sj_outer_fanout;
+ *handled_fanout= dups_removed_fanout;
+ *strategy= SJ_OPT_DUPS_WEEDOUT;
+ if (unlikely(trace.trace_started()))
+ {
+ trace.add("records", *record_count);
+ trace.add("read_time", *read_time);
+ }
+ return TRUE;
+ }
+ return FALSE;
+}
+
+
+/*
+ Remove the last join tab from from join->cur_sj_inner_tables bitmap
+ we assume remaining_tables doesnt contain @tab.
+*/
+
+void restore_prev_sj_state(const table_map remaining_tables,
+ const JOIN_TAB *tab, uint idx)
+{
+ TABLE_LIST *emb_sj_nest;
+
+ if (tab->emb_sj_nest)
+ {
+ table_map subq_tables= tab->emb_sj_nest->sj_inner_tables;
+ tab->join->sjm_lookup_tables &= ~subq_tables;
+ }
+
+ if ((emb_sj_nest= tab->emb_sj_nest))
+ {
+ /* If we're removing the last SJ-inner table, remove the sj-nest */
+ if ((remaining_tables & emb_sj_nest->sj_inner_tables) ==
+ (emb_sj_nest->sj_inner_tables & ~tab->table->map))
+ {
+ tab->join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
+ }
+ }
+}
+
+
+/*
+ Given a semi-join nest, find out which of the IN-equalities are bound
+
+ SYNOPSIS
+ get_bound_sj_equalities()
+ sj_nest Semi-join nest
+ remaining_tables Tables that are not yet bound
+
+ DESCRIPTION
+ Given a semi-join nest, find out which of the IN-equalities have their
+ left part expression bound (i.e. the said expression doesn't refer to
+ any of remaining_tables and can be evaluated).
+
+ RETURN
+ Bitmap of bound IN-equalities.
+*/
+
+ulonglong get_bound_sj_equalities(TABLE_LIST *sj_nest,
+ table_map remaining_tables)
+{
+ List_iterator<Item_ptr> li(sj_nest->nested_join->sj_outer_expr_list);
+ Item **item;
+ uint i= 0;
+ ulonglong res= 0;
+ while ((item= li++))
+ {
+ /*
+ Q: should this take into account equality propagation and how?
+ A: If e->outer_side is an Item_field, walk over the equality
+ class and see if there is an element that is bound?
+ (this is an optional feature)
+ */
+ if (!(item[0]->used_tables() & remaining_tables))
+ {
+ res |= 1ULL << i;
+ }
+ i++;
+ }
+ return res;
+}
+
+
+/*
+ Check if the last tables of the partial join order allow to use
+ sj-materialization strategy for them
+
+ SYNOPSIS
+ at_sjmat_pos()
+ join
+ remaining_tables
+ tab the last table's join tab
+ idx last table's index
+ loose_scan OUT TRUE <=> use LooseScan
+
+ RETURN
+ TRUE Yes, can apply sj-materialization
+ FALSE No, some of the requirements are not met
+*/
+
+static SJ_MATERIALIZATION_INFO *
+at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
+ uint idx, bool *loose_scan)
+{
+ /*
+ Check if
+ 1. We're in a semi-join nest that can be run with SJ-materialization
+ 2. All the tables correlated through the IN subquery are in the prefix
+ */
+ TABLE_LIST *emb_sj_nest= tab->emb_sj_nest;
+ table_map suffix= remaining_tables & ~tab->table->map;
+ if (emb_sj_nest && emb_sj_nest->sj_mat_info &&
+ !(suffix & emb_sj_nest->sj_inner_tables))
+ {
+ /*
+ Walk back and check if all immediately preceding tables are from
+ this semi-join.
+ */
+ uint n_tables= my_count_bits(tab->emb_sj_nest->sj_inner_tables);
+ for (uint i= 1; i < n_tables ; i++)
+ {
+ if (join->positions[idx - i].table->emb_sj_nest != tab->emb_sj_nest)
+ return NULL;
+ }
+ *loose_scan= MY_TEST(remaining_tables & ~tab->table->map &
+ (emb_sj_nest->sj_inner_tables |
+ emb_sj_nest->nested_join->sj_depends_on));
+ if (*loose_scan && !emb_sj_nest->sj_subq_pred->sjm_scan_allowed)
+ return NULL;
+ else
+ return emb_sj_nest->sj_mat_info;
+ }
+ return NULL;
+}
+
+
+/*
+ Re-calculate values of join->best_positions[start..end].prefix_record_count
+*/
+
+static void recalculate_prefix_record_count(JOIN *join, uint start, uint end)
+{
+ for (uint j= start; j < end ;j++)
+ {
+ double prefix_count;
+ if (j == join->const_tables)
+ prefix_count= 1.0;
+ else
+ prefix_count= COST_MULT(join->best_positions[j-1].prefix_record_count,
+ join->best_positions[j-1].records_read);
+
+ join->best_positions[j].prefix_record_count= prefix_count;
+ }
+}
+
+
+/*
+ Fix semi-join strategies for the picked join order
+
+ SYNOPSIS
+ fix_semijoin_strategies_for_picked_join_order()
+ join The join with the picked join order
+
+ DESCRIPTION
+ Fix semi-join strategies for the picked join order. This is a step that
+ needs to be done right after we have fixed the join order. What we do
+ here is switch join's semi-join strategy description from backward-based
+ to forwards based.
+
+ When join optimization is in progress, we re-consider semi-join
+ strategies after we've added another table. Here's an illustration.
+ Suppose the join optimization is underway:
+
+ 1) ot1 it1 it2
+ sjX -- looking at (ot1, it1, it2) join prefix, we decide
+ to use semi-join strategy sjX.
+
+ 2) ot1 it1 it2 ot2
+ sjX sjY -- Having added table ot2, we now may consider
+ another semi-join strategy and decide to use a
+ different strategy sjY. Note that the record
+ of sjX has remained under it2. That is
+ necessary because we need to be able to get
+ back to (ot1, it1, it2) join prefix.
+ what makes things even worse is that there are cases where the choice
+ of sjY changes the way we should access it2.
+
+ 3) [ot1 it1 it2 ot2 ot3]
+ sjX sjY -- This means that after join optimization is
+ finished, semi-join info should be read
+ right-to-left (while nearly all plan refinement
+ functions, EXPLAIN, etc proceed from left to
+ right)
+
+ This function does the needed reversal, making it possible to read the
+ join and semi-join order from left to right.
+*/
+
+void fix_semijoin_strategies_for_picked_join_order(JOIN *join)
+{
+ join->sjm_lookup_tables= 0;
+ join->sjm_scan_tables= 0;
+ if (!join->select_lex->sj_nests.elements)
+ return;
+
+ THD *thd= join->thd;
+ uint table_count=join->table_count;
+ uint tablenr;
+ table_map remaining_tables= 0;
+ table_map handled_tabs= 0;
+ Json_writer_object trace_wrapper(thd);
+ Json_writer_array trace_semijoin_strategies(thd,
+ "fix_semijoin_strategies_for_picked_join_order");
+
+ for (tablenr= table_count - 1 ; tablenr != join->const_tables - 1; tablenr--)
+ {
+ POSITION *pos= join->best_positions + tablenr;
+ JOIN_TAB *s= pos->table;
+ uint UNINIT_VAR(first); // Set by every branch except SJ_OPT_NONE which doesn't use it
+
+ if ((handled_tabs & s->table->map) || pos->sj_strategy == SJ_OPT_NONE)
+ {
+ remaining_tables |= s->table->map;
+ continue;
+ }
+
+ if (pos->sj_strategy == SJ_OPT_MATERIALIZE)
+ {
+ SJ_MATERIALIZATION_INFO *sjm= s->emb_sj_nest->sj_mat_info;
+ sjm->is_used= TRUE;
+ sjm->is_sj_scan= FALSE;
+ memcpy((uchar*) (pos - sjm->tables + 1), (uchar*) sjm->positions,
+ sizeof(POSITION) * sjm->tables);
+ recalculate_prefix_record_count(join, tablenr - sjm->tables + 1,
+ tablenr);
+ first= tablenr - sjm->tables + 1;
+ join->best_positions[first].n_sj_tables= sjm->tables;
+ join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE;
+ Json_writer_object semijoin_strategy(thd);
+ semijoin_strategy.add("semi_join_strategy","SJ-Materialization");
+ Json_writer_array semijoin_plan(thd, "join_order");
+ for (uint i= first; i < first+ sjm->tables; i++)
+ {
+ if (unlikely(thd->trace_started()))
+ {
+ Json_writer_object trace_one_table(thd);
+ trace_one_table.add_table_name(join->best_positions[i].table);
+ }
+ join->sjm_lookup_tables |= join->best_positions[i].table->table->map;
+ }
+ }
+ else if (pos->sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
+ {
+ POSITION *first_inner= join->best_positions + pos->sjmat_picker.sjm_scan_last_inner;
+ SJ_MATERIALIZATION_INFO *sjm= first_inner->table->emb_sj_nest->sj_mat_info;
+ sjm->is_used= TRUE;
+ sjm->is_sj_scan= TRUE;
+ first= pos->sjmat_picker.sjm_scan_last_inner - sjm->tables + 1;
+ memcpy((uchar*) (join->best_positions + first),
+ (uchar*) sjm->positions, sizeof(POSITION) * sjm->tables);
+ recalculate_prefix_record_count(join, first, first + sjm->tables);
+ join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE_SCAN;
+ join->best_positions[first].n_sj_tables= sjm->tables;
+ /*
+ Do what advance_sj_state did: re-run best_access_path for every table
+ in the [last_inner_table + 1; pos..) range
+ */
+ double prefix_rec_count;
+ /* Get the prefix record count */
+ if (first == join->const_tables)
+ prefix_rec_count= 1.0;
+ else
+ prefix_rec_count= join->best_positions[first-1].prefix_record_count;
+
+ /* Add materialization record count*/
+ prefix_rec_count *= sjm->rows;
+
+ uint i;
+ table_map rem_tables= remaining_tables;
+ for (i= tablenr; i != (first + sjm->tables - 1); i--)
+ rem_tables |= join->best_positions[i].table->table->map;
+
+ for (i= first; i < first+ sjm->tables; i++)
+ join->sjm_scan_tables |= join->best_positions[i].table->table->map;
+
+ POSITION dummy;
+ join->cur_sj_inner_tables= 0;
+ Json_writer_object semijoin_strategy(thd);
+ semijoin_strategy.add("semi_join_strategy","SJ-Materialization-Scan");
+ Json_writer_array semijoin_plan(thd, "join_order");
+ for (i= first + sjm->tables; i <= tablenr; i++)
+ {
+ if (unlikely(thd->trace_started()))
+ {
+ Json_writer_object trace_one_table(thd);
+ trace_one_table.add_table_name(join->best_positions[i].table);
+ }
+ best_access_path(join, join->best_positions[i].table, rem_tables,
+ join->best_positions, i,
+ FALSE, prefix_rec_count,
+ join->best_positions + i, &dummy);
+ prefix_rec_count *= join->best_positions[i].records_read;
+ rem_tables &= ~join->best_positions[i].table->table->map;
+ }
+ }
+
+ if (pos->sj_strategy == SJ_OPT_FIRST_MATCH)
+ {
+ first= pos->firstmatch_picker.first_firstmatch_table;
+ join->best_positions[first].sj_strategy= SJ_OPT_FIRST_MATCH;
+ join->best_positions[first].n_sj_tables= tablenr - first + 1;
+ POSITION dummy; // For loose scan paths
+ double record_count= (first== join->const_tables)? 1.0:
+ join->best_positions[tablenr - 1].prefix_record_count;
+
+ table_map rem_tables= remaining_tables;
+ uint idx;
+ for (idx= first; idx <= tablenr; idx++)
+ {
+ rem_tables |= join->best_positions[idx].table->table->map;
+ }
+ /*
+ Re-run best_access_path to produce best access methods that do not use
+ join buffering
+ */
+ join->cur_sj_inner_tables= 0;
+ Json_writer_object semijoin_strategy(thd);
+ semijoin_strategy.add("semi_join_strategy","FirstMatch");
+ Json_writer_array semijoin_plan(thd, "join_order");
+ for (idx= first; idx <= tablenr; idx++)
+ {
+ if (unlikely(thd->trace_started()))
+ {
+ Json_writer_object trace_one_table(thd);
+ trace_one_table.add_table_name(join->best_positions[idx].table);
+ }
+ if (join->best_positions[idx].use_join_buffer)
+ {
+ best_access_path(join, join->best_positions[idx].table,
+ rem_tables, join->best_positions, idx,
+ TRUE /* no jbuf */,
+ record_count, join->best_positions + idx, &dummy);
+ }
+ record_count *= join->best_positions[idx].records_read;
+ rem_tables &= ~join->best_positions[idx].table->table->map;
+ }
+ }
+
+ if (pos->sj_strategy == SJ_OPT_LOOSE_SCAN)
+ {
+ first= pos->loosescan_picker.first_loosescan_table;
+ POSITION *first_pos= join->best_positions + first;
+ POSITION loose_scan_pos; // For loose scan paths
+ double record_count= (first== join->const_tables)? 1.0:
+ join->best_positions[tablenr - 1].prefix_record_count;
+
+ table_map rem_tables= remaining_tables;
+ uint idx;
+ for (idx= first; idx <= tablenr; idx++)
+ rem_tables |= join->best_positions[idx].table->table->map;
+ /*
+ Re-run best_access_path to produce best access methods that do not use
+ join buffering
+ */
+ join->cur_sj_inner_tables= 0;
+ Json_writer_object semijoin_strategy(thd);
+ semijoin_strategy.add("semi_join_strategy","LooseScan");
+ Json_writer_array semijoin_plan(thd, "join_order");
+ for (idx= first; idx <= tablenr; idx++)
+ {
+ if (unlikely(thd->trace_started()))
+ {
+ Json_writer_object trace_one_table(thd);
+ trace_one_table.add_table_name(join->best_positions[idx].table);
+ }
+ if (join->best_positions[idx].use_join_buffer || (idx == first))
+ {
+ best_access_path(join, join->best_positions[idx].table,
+ rem_tables, join->best_positions, idx,
+ TRUE /* no jbuf */,
+ record_count, join->best_positions + idx,
+ &loose_scan_pos);
+ if (idx==first)
+ {
+ join->best_positions[idx]= loose_scan_pos;
+ /*
+ If LooseScan is based on ref access (including the "degenerate"
+ one with 0 key parts), we should use full index scan.
+
+ Unfortunately, lots of code assumes that if tab->type==JT_ALL &&
+ tab->quick!=NULL, then quick select should be used. The only
+ simple way to fix this is to remove the quick select:
+ */
+ if (join->best_positions[idx].key)
+ {
+ delete join->best_positions[idx].table->quick;
+ join->best_positions[idx].table->quick= NULL;
+ }
+ }
+ }
+ rem_tables &= ~join->best_positions[idx].table->table->map;
+ record_count *= join->best_positions[idx].records_read;
+ }
+ first_pos->sj_strategy= SJ_OPT_LOOSE_SCAN;
+ first_pos->n_sj_tables= my_count_bits(first_pos->table->emb_sj_nest->sj_inner_tables);
+ }
+
+ if (pos->sj_strategy == SJ_OPT_DUPS_WEEDOUT)
+ {
+ Json_writer_object semijoin_strategy(thd);
+ semijoin_strategy.add("semi_join_strategy","DuplicateWeedout");
+ /*
+ Duplicate Weedout starting at pos->first_dupsweedout_table, ending at
+ this table.
+ */
+ first= pos->dups_weedout_picker.first_dupsweedout_table;
+ join->best_positions[first].sj_strategy= SJ_OPT_DUPS_WEEDOUT;
+ join->best_positions[first].n_sj_tables= tablenr - first + 1;
+ }
+
+ uint i_end= first + join->best_positions[first].n_sj_tables;
+ for (uint i= first; i < i_end; i++)
+ {
+ if (i != first)
+ join->best_positions[i].sj_strategy= SJ_OPT_NONE;
+ handled_tabs |= join->best_positions[i].table->table->map;
+ }
+
+ if (tablenr != first)
+ pos->sj_strategy= SJ_OPT_NONE;
+ remaining_tables |= s->table->map;
+ join->join_tab[first].sj_strategy= join->best_positions[first].sj_strategy;
+ join->join_tab[first].n_sj_tables= join->best_positions[first].n_sj_tables;
+ }
+}
+
+
+/*
+ Return the number of tables at the top-level of the JOIN
+
+ SYNOPSIS
+ get_number_of_tables_at_top_level()
+ join The join with the picked join order
+
+ DESCRIPTION
+ The number of tables in the JOIN currently include all the inner tables of the
+ mergeable semi-joins. The function would make sure that we only count the semi-join
+ nest and not the inner tables of teh semi-join nest.
+*/
+
+uint get_number_of_tables_at_top_level(JOIN *join)
+{
+ uint j= 0, tables= 0;
+ while(j < join->table_count)
+ {
+ POSITION *cur_pos= &join->best_positions[j];
+ tables++;
+ if (cur_pos->sj_strategy == SJ_OPT_MATERIALIZE ||
+ cur_pos->sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
+ {
+ SJ_MATERIALIZATION_INFO *sjm= cur_pos->table->emb_sj_nest->sj_mat_info;
+ j= j + sjm->tables;
+ }
+ else
+ j++;
+ }
+ return tables;
+}
+
+
+/*
+ Setup semi-join materialization strategy for one semi-join nest
+
+ SYNOPSIS
+
+ setup_sj_materialization()
+ tab The first tab in the semi-join
+
+ DESCRIPTION
+ Setup execution structures for one semi-join materialization nest:
+ - Create the materialization temporary table
+ - If we're going to do index lookups
+ create TABLE_REF structure to make the lookus
+ - else (if we're going to do a full scan of the temptable)
+ create Copy_field structures to do copying.
+
+ RETURN
+ FALSE Ok
+ TRUE Error
+*/
+
+bool setup_sj_materialization_part1(JOIN_TAB *sjm_tab)
+{
+ JOIN_TAB *tab= sjm_tab->bush_children->start;
+ TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
+ SJ_MATERIALIZATION_INFO *sjm;
+ THD *thd;
+
+ DBUG_ENTER("setup_sj_materialization");
+
+ /* Walk out of outer join nests until we reach the semi-join nest we're in */
+ while (!emb_sj_nest->sj_mat_info)
+ emb_sj_nest= emb_sj_nest->embedding;
+
+ sjm= emb_sj_nest->sj_mat_info;
+ thd= tab->join->thd;
+ /* First the calls come to the materialization function */
+
+ DBUG_ASSERT(sjm->is_used);
+ /*
+ Set up the table to write to, do as select_union::create_result_table does
+ */
+ sjm->sjm_table_param.init();
+ sjm->sjm_table_param.bit_fields_as_long= TRUE;
+ SELECT_LEX *subq_select= emb_sj_nest->sj_subq_pred->unit->first_select();
+ const LEX_CSTRING sj_materialize_name= { STRING_WITH_LEN("sj-materialize") };
+ List_iterator<Item> it(subq_select->item_list);
+ Item *item;
+ while((item= it++))
+ {
+ /*
+ This semi-join replaced the subquery (subq_select) and so on
+ re-executing it will not be prepared. To use the Items from its
+ select list we have to prepare (fix_fields) them
+ */
+ if (item->fix_fields_if_needed(thd, it.ref()))
+ DBUG_RETURN(TRUE);
+ item= *(it.ref()); // it can be changed by fix_fields
+ DBUG_ASSERT(!item->name.length || item->name.length == strlen(item->name.str));
+ sjm->sjm_table_cols.push_back(item, thd->mem_root);
+ }
+
+ sjm->sjm_table_param.field_count= subq_select->item_list.elements;
+ sjm->sjm_table_param.force_not_null_cols= TRUE;
+
+ if (!(sjm->table= create_tmp_table(thd, &sjm->sjm_table_param,
+ sjm->sjm_table_cols, (ORDER*) 0,
+ TRUE /* distinct */,
+ 1, /*save_sum_fields*/
+ thd->variables.option_bits | TMP_TABLE_ALL_COLUMNS,
+ HA_POS_ERROR /*rows_limit */,
+ &sj_materialize_name)))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ sjm->table->map= emb_sj_nest->nested_join->used_tables;
+ sjm->table->file->extra(HA_EXTRA_WRITE_CACHE);
+ sjm->table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
+
+ tab->join->sj_tmp_tables.push_back(sjm->table, thd->mem_root);
+ tab->join->sjm_info_list.push_back(sjm, thd->mem_root);
+
+ sjm->materialized= FALSE;
+ sjm_tab->table= sjm->table;
+ sjm->table->pos_in_table_list= emb_sj_nest;
+
+ DBUG_RETURN(FALSE);
+}
+
+/**
+ @retval
+ FALSE ok
+ TRUE error
+*/
+
+bool setup_sj_materialization_part2(JOIN_TAB *sjm_tab)
+{
+ DBUG_ENTER("setup_sj_materialization_part2");
+ JOIN_TAB *tab= sjm_tab->bush_children->start;
+ TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
+ /* Walk out of outer join nests until we reach the semi-join nest we're in */
+ while (!emb_sj_nest->sj_mat_info)
+ emb_sj_nest= emb_sj_nest->embedding;
+ SJ_MATERIALIZATION_INFO *sjm= emb_sj_nest->sj_mat_info;
+ THD *thd= tab->join->thd;
+ uint i;
+
+ if (!sjm->is_sj_scan)
+ {
+ KEY *tmp_key; /* The only index on the temporary table. */
+ uint tmp_key_parts; /* Number of keyparts in tmp_key. */
+ tmp_key= sjm->table->key_info;
+ tmp_key_parts= tmp_key->user_defined_key_parts;
+
+ /*
+ Create/initialize everything we will need to index lookups into the
+ temptable.
+ */
+ TABLE_REF *tab_ref;
+ tab_ref= &sjm_tab->ref;
+ tab_ref->key= 0; /* The only temp table index. */
+ tab_ref->key_length= tmp_key->key_length;
+ if (!(tab_ref->key_buff=
+ (uchar*) thd->calloc(ALIGN_SIZE(tmp_key->key_length) * 2)) ||
+ !(tab_ref->key_copy=
+ (store_key**) thd->alloc((sizeof(store_key*) *
+ (tmp_key_parts + 1)))) ||
+ !(tab_ref->items=
+ (Item**) thd->alloc(sizeof(Item*) * tmp_key_parts)))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+
+ tab_ref->key_buff2=tab_ref->key_buff+ALIGN_SIZE(tmp_key->key_length);
+ tab_ref->key_err=1;
+ tab_ref->null_rejecting= 1;
+ tab_ref->disable_cache= FALSE;
+
+ KEY_PART_INFO *cur_key_part= tmp_key->key_part;
+ store_key **ref_key= tab_ref->key_copy;
+ uchar *cur_ref_buff= tab_ref->key_buff;
+
+ for (i= 0; i < tmp_key_parts; i++, cur_key_part++, ref_key++)
+ {
+ tab_ref->items[i]=
+ emb_sj_nest->sj_subq_pred->left_exp()->element_index(i);
+ int null_count= MY_TEST(cur_key_part->field->real_maybe_null());
+ *ref_key= new store_key_item(thd, cur_key_part->field,
+ /* TODO:
+ the NULL byte is taken into account in
+ cur_key_part->store_length, so instead of
+ cur_ref_buff + MY_TEST(maybe_null), we could
+ use that information instead.
+ */
+ cur_ref_buff + null_count,
+ null_count ? cur_ref_buff : 0,
+ cur_key_part->length, tab_ref->items[i],
+ FALSE);
+ if (!*ref_key)
+ DBUG_RETURN(TRUE);
+ cur_ref_buff+= cur_key_part->store_length;
+ }
+ *ref_key= NULL; /* End marker. */
+
+ /*
+ We don't ever have guarded conditions for SJM tables, but code at SQL
+ layer depends on cond_guards array being alloced.
+ */
+ if (!(tab_ref->cond_guards= (bool**) thd->calloc(sizeof(uint*)*tmp_key_parts)))
+ {
+ DBUG_RETURN(TRUE);
+ }
+
+ tab_ref->key_err= 1;
+ tab_ref->key_parts= tmp_key_parts;
+ sjm->tab_ref= tab_ref;
+
+ /*
+ Remove the injected semi-join IN-equalities from join_tab conds. This
+ needs to be done because the IN-equalities refer to columns of
+ sj-inner tables which are not available after the materialization
+ has been finished.
+ */
+ for (i= 0; i < sjm->tables; i++)
+ {
+ if (remove_sj_conds(thd, &tab[i].select_cond) ||
+ (tab[i].select && remove_sj_conds(thd, &tab[i].select->cond)))
+ DBUG_RETURN(TRUE);
+ }
+ if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm,
+ emb_sj_nest->sj_subq_pred)))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ sjm_tab->type= JT_EQ_REF;
+ sjm_tab->select_cond= sjm->in_equality;
+ }
+ else
+ {
+ /*
+ We'll be doing full scan of the temptable.
+ Setup copying of temptable columns back to the record buffers
+ for their source tables. We need this because IN-equalities
+ refer to the original tables.
+
+ EXAMPLE
+
+ Consider the query:
+ SELECT * FROM ot WHERE ot.col1 IN (SELECT it.col2 FROM it)
+
+ Suppose it's executed with SJ-Materialization-scan. We choose to do scan
+ if we can't do the lookup, i.e. the join order is (it, ot). The plan
+ would look as follows:
+
+ table access method condition
+ it materialize+scan -
+ ot (whatever) ot1.col1=it.col2 (C2)
+
+ The condition C2 refers to current row of table it. The problem is
+ that by the time we evaluate C2, we would have finished with scanning
+ it itself and will be scanning the temptable.
+
+ At the moment, our solution is to copy back: when we get the next
+ temptable record, we copy its columns to their corresponding columns
+ in the record buffers for the source tables.
+ */
+ if (!(sjm->copy_field= new Copy_field[sjm->sjm_table_cols.elements]))
+ DBUG_RETURN(TRUE);
+
+ //it.rewind();
+ Ref_ptr_array p_items= emb_sj_nest->sj_subq_pred->unit->first_select()->ref_pointer_array;
+ for (uint i=0; i < sjm->sjm_table_cols.elements; i++)
+ {
+ bool dummy;
+ Item_equal *item_eq;
+ //Item *item= (it++)->real_item();
+ Item *item= p_items[i]->real_item();
+ DBUG_ASSERT(item->type() == Item::FIELD_ITEM);
+ Field *copy_to= ((Item_field*)item)->field;
+ /*
+ Tricks with Item_equal are due to the following: suppose we have a
+ query:
+
+ ... WHERE cond(ot.col) AND ot.col IN (SELECT it2.col FROM it1,it2
+ WHERE it1.col= it2.col)
+ then equality propagation will create an
+
+ Item_equal(it1.col, it2.col, ot.col)
+
+ then substitute_for_best_equal_field() will change the conditions
+ according to the join order:
+
+ table | attached condition
+ ------+--------------------
+ it1 |
+ it2 | it1.col=it2.col
+ ot | cond(it1.col)
+
+ although we've originally had "SELECT it2.col", conditions attached
+ to subsequent outer tables will refer to it1.col, so SJM-Scan will
+ need to unpack data to there.
+ That is, if an element from subquery's select list participates in
+ equality propagation, then we need to unpack it to the first
+ element equality propagation member that refers to table that is
+ within the subquery.
+ */
+ item_eq= find_item_equal(tab->join->cond_equal, copy_to, &dummy);
+
+ if (item_eq)
+ {
+ List_iterator<Item> it(item_eq->equal_items);
+ /* We're interested in field items only */
+ if (item_eq->get_const())
+ it++;
+ Item *item;
+ while ((item= it++))
+ {
+ if (!(item->used_tables() & ~emb_sj_nest->sj_inner_tables))
+ {
+ DBUG_ASSERT(item->real_item()->type() == Item::FIELD_ITEM);
+ copy_to= ((Item_field *) (item->real_item()))->field;
+ break;
+ }
+ }
+ }
+ sjm->copy_field[i].set(copy_to, sjm->table->field[i], FALSE);
+ /* The write_set for source tables must be set up to allow the copying */
+ bitmap_set_bit(copy_to->table->write_set, copy_to->field_index);
+ }
+ sjm_tab->type= JT_ALL;
+
+ /* Initialize full scan */
+ sjm_tab->read_first_record= join_read_record_no_init;
+ sjm_tab->read_record.copy_field= sjm->copy_field;
+ sjm_tab->read_record.copy_field_end= sjm->copy_field +
+ sjm->sjm_table_cols.elements;
+ sjm_tab->read_record.read_record_func= rr_sequential_and_unpack;
+ }
+
+ sjm_tab->bush_children->end[-1].next_select= end_sj_materialize;
+
+ DBUG_RETURN(FALSE);
+}
+
+
+
+/*
+ Create subquery IN-equalities assuming use of materialization strategy
+
+ SYNOPSIS
+ create_subq_in_equalities()
+ thd Thread handle
+ sjm Semi-join materialization structure
+ subq_pred The subquery predicate
+
+ DESCRIPTION
+ Create subquery IN-equality predicates. That is, for a subquery
+
+ (oe1, oe2, ...) IN (SELECT ie1, ie2, ... FROM ...)
+
+ create "oe1=ie1 AND ie1=ie2 AND ..." expression, such that ie1, ie2, ..
+ refer to the columns of the table that's used to materialize the
+ subquery.
+
+ RETURN
+ Created condition
+*/
+
+static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
+ Item_in_subselect *subq_pred)
+{
+ Item *res= NULL;
+ Item *left_exp= subq_pred->left_exp();
+ uint ncols= left_exp->cols();
+ if (ncols == 1)
+ {
+ if (!(res= new (thd->mem_root) Item_func_eq(thd, left_exp,
+ new (thd->mem_root) Item_field(thd, sjm->table->field[0]))))
+ return NULL; /* purecov: inspected */
+ }
+ else
+ {
+ Item *conj;
+ for (uint i= 0; i < ncols; i++)
+ {
+ if (!(conj= new (thd->mem_root) Item_func_eq(thd, left_exp->element_index(i),
+ new (thd->mem_root) Item_field(thd, sjm->table->field[i]))) ||
+ !(res= and_items(thd, res, conj)))
+ return NULL; /* purecov: inspected */
+ }
+ }
+ if (res->fix_fields(thd, &res))
+ return NULL; /* purecov: inspected */
+ return res;
+}
+
+
+/**
+ @retval
+ 0 ok
+ 1 error
+*/
+
+static bool remove_sj_conds(THD *thd, Item **tree)
+{
+ if (*tree)
+ {
+ if (is_cond_sj_in_equality(*tree))
+ {
+ *tree= NULL;
+ return 0;
+ }
+ else if ((*tree)->type() == Item::COND_ITEM)
+ {
+ Item *item;
+ List_iterator<Item> li(*(((Item_cond*)*tree)->argument_list()));
+ while ((item= li++))
+ {
+ if (is_cond_sj_in_equality(item))
+ {
+ Item_int *tmp= new (thd->mem_root) Item_int(thd, 1);
+ if (!tmp)
+ return 1;
+ li.replace(tmp);
+ }
+ }
+ }
+ }
+ return 0;
+}
+
+
+/* Check if given Item was injected by semi-join equality */
+static bool is_cond_sj_in_equality(Item *item)
+{
+ if (item->type() == Item::FUNC_ITEM &&
+ ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
+ {
+ Item_func_eq *item_eq= (Item_func_eq*)item;
+ return MY_TEST(item_eq->in_equality_no != UINT_MAX);
+ }
+ return FALSE;
+}
+
+
+/*
+ Create a temporary table to weed out duplicate rowid combinations
+
+ SYNOPSIS
+
+ create_sj_weedout_tmp_table()
+ thd Thread handle
+
+ DESCRIPTION
+ Create a temporary table to weed out duplicate rowid combinations. The
+ table has a single column that is a concatenation of all rowids in the
+ combination.
+
+ Depending on the needed length, there are two cases:
+
+ 1. When the length of the column < max_key_length:
+
+ CREATE TABLE tmp (col VARBINARY(n) NOT NULL, UNIQUE KEY(col));
+
+ 2. Otherwise (not a valid SQL syntax but internally supported):
+
+ CREATE TABLE tmp (col VARBINARY NOT NULL, UNIQUE CONSTRAINT(col));
+
+ The code in this function was produced by extraction of relevant parts
+ from create_tmp_table().
+
+ RETURN
+ created table
+ NULL on error
+*/
+
+bool
+SJ_TMP_TABLE::create_sj_weedout_tmp_table(THD *thd)
+{
+ MEM_ROOT *mem_root_save, own_root;
+ TABLE *table;
+ TABLE_SHARE *share;
+ uint temp_pool_slot=MY_BIT_NONE;
+ char *tmpname,path[FN_REFLEN];
+ Field **reg_field;
+ KEY_PART_INFO *key_part_info;
+ KEY *keyinfo;
+ uchar *group_buff;
+ uchar *bitmaps;
+ uint *blob_field;
+ bool using_unique_constraint=FALSE;
+ bool use_packed_rows= FALSE;
+ Field *field, *key_field;
+ uint null_pack_length, null_count;
+ uchar *null_flags;
+ uchar *pos;
+ DBUG_ENTER("create_sj_weedout_tmp_table");
+ DBUG_ASSERT(!is_degenerate);
+
+ tmp_table= NULL;
+ uint uniq_tuple_length_arg= rowid_len + null_bytes;
+ /*
+ STEP 1: Get temporary table name
+ */
+ if (use_temp_pool && !(test_flags & TEST_KEEP_TMP_TABLES))
+ temp_pool_slot = bitmap_lock_set_next(&temp_pool);
+
+ if (temp_pool_slot != MY_BIT_NONE) // we got a slot
+ sprintf(path, "%s-subquery-%lx-%i", tmp_file_prefix,
+ current_pid, temp_pool_slot);
+ else
+ {
+ /* if we run out of slots or we are not using tempool */
+ sprintf(path,"%s-subquery-%lx-%lx-%x", tmp_file_prefix,current_pid,
+ (ulong) thd->thread_id, thd->tmp_table++);
+ }
+ fn_format(path, path, mysql_tmpdir, "", MY_REPLACE_EXT|MY_UNPACK_FILENAME);
+
+ /* STEP 2: Figure if we'll be using a key or blob+constraint */
+ /* it always has my_charset_bin, so mbmaxlen==1 */
+ if (uniq_tuple_length_arg >= CONVERT_IF_BIGGER_TO_BLOB)
+ using_unique_constraint= TRUE;
+
+ /* STEP 3: Allocate memory for temptable description */
+ init_sql_alloc(PSI_INSTRUMENT_ME, &own_root, TABLE_ALLOC_BLOCK_SIZE, 0,
+ MYF(MY_THREAD_SPECIFIC));
+ if (!multi_alloc_root(&own_root,
+ &table, sizeof(*table),
+ &share, sizeof(*share),
+ &reg_field, sizeof(Field*) * (1+1),
+ &blob_field, sizeof(uint)*2,
+ &keyinfo, sizeof(*keyinfo),
+ &key_part_info, sizeof(*key_part_info) * 2,
+ &start_recinfo,
+ sizeof(*recinfo)*(1*2+4),
+ &tmpname, (uint) strlen(path)+1,
+ &group_buff, (!using_unique_constraint ?
+ uniq_tuple_length_arg : 0),
+ &bitmaps, bitmap_buffer_size(1)*6,
+ NullS))
+ {
+ if (temp_pool_slot != MY_BIT_NONE)
+ bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
+ DBUG_RETURN(TRUE);
+ }
+ strmov(tmpname,path);
+
+
+ /* STEP 4: Create TABLE description */
+ bzero((char*) table,sizeof(*table));
+ bzero((char*) reg_field,sizeof(Field*)*2);
+
+ table->mem_root= own_root;
+ mem_root_save= thd->mem_root;
+ thd->mem_root= &table->mem_root;
+
+ table->field=reg_field;
+ table->alias.set("weedout-tmp", sizeof("weedout-tmp")-1,
+ table_alias_charset);
+ table->reginfo.lock_type=TL_WRITE; /* Will be updated */
+ table->db_stat=HA_OPEN_KEYFILE;
+ table->map=1;
+ table->temp_pool_slot = temp_pool_slot;
+ table->copy_blobs= 1;
+ table->in_use= thd;
+
+ table->s= share;
+ init_tmp_table_share(thd, share, "", 0, tmpname, tmpname);
+ share->blob_field= blob_field;
+ share->table_charset= NULL;
+ share->primary_key= MAX_KEY; // Indicate no primary key
+
+ /* Create the field */
+ {
+ LEX_CSTRING field_name= {STRING_WITH_LEN("rowids") };
+ /*
+ For the sake of uniformity, always use Field_varstring (altough we could
+ use Field_string for shorter keys)
+ */
+ field= new Field_varstring(uniq_tuple_length_arg, FALSE, &field_name,
+ share, &my_charset_bin);
+ if (!field)
+ DBUG_RETURN(0);
+ field->table= table;
+ field->key_start.clear_all();
+ field->part_of_key.clear_all();
+ field->part_of_sortkey.clear_all();
+ field->unireg_check= Field::NONE;
+ field->flags= (NOT_NULL_FLAG | BINARY_FLAG | NO_DEFAULT_VALUE_FLAG);
+ field->reset_fields();
+ field->init(table);
+ field->orig_table= NULL;
+
+ field->field_index= 0;
+
+ *(reg_field++)= field;
+ *blob_field= 0;
+ *reg_field= 0;
+
+ share->fields= 1;
+ share->blob_fields= 0;
+ }
+
+ uint reclength= field->pack_length();
+ if (using_unique_constraint || thd->variables.tmp_memory_table_size == 0)
+ {
+ share->db_plugin= ha_lock_engine(0, TMP_ENGINE_HTON);
+ table->file= get_new_handler(share, &table->mem_root,
+ share->db_type());
+ }
+ else
+ {
+ share->db_plugin= ha_lock_engine(0, heap_hton);
+ table->file= get_new_handler(share, &table->mem_root,
+ share->db_type());
+ DBUG_ASSERT(!table->file || uniq_tuple_length_arg <= table->file->max_key_length());
+ }
+ if (!table->file)
+ goto err;
+
+ if (table->file->set_ha_share_ref(&share->ha_share))
+ {
+ delete table->file;
+ goto err;
+ }
+
+ null_count=1;
+
+ null_pack_length= 1;
+ reclength += null_pack_length;
+
+ share->reclength= reclength;
+ {
+ uint alloc_length=ALIGN_SIZE(share->reclength + MI_UNIQUE_HASH_LENGTH+1);
+ share->rec_buff_length= alloc_length;
+ if (!(table->record[0]= (uchar*)
+ alloc_root(&table->mem_root, alloc_length*3)))
+ goto err;
+ table->record[1]= table->record[0]+alloc_length;
+ share->default_values= table->record[1]+alloc_length;
+ }
+ setup_tmp_table_column_bitmaps(table, bitmaps);
+
+ recinfo= start_recinfo;
+ null_flags=(uchar*) table->record[0];
+ pos=table->record[0]+ null_pack_length;
+ if (null_pack_length)
+ {
+ bzero((uchar*) recinfo,sizeof(*recinfo));
+ recinfo->type=FIELD_NORMAL;
+ recinfo->length=null_pack_length;
+ recinfo++;
+ bfill(null_flags,null_pack_length,255); // Set null fields
+
+ table->null_flags= (uchar*) table->record[0];
+ share->null_fields= null_count;
+ share->null_bytes= null_pack_length;
+ }
+ null_count=1;
+
+ {
+ //Field *field= *reg_field;
+ uint length;
+ bzero((uchar*) recinfo,sizeof(*recinfo));
+ field->move_field(pos,(uchar*) 0,0);
+
+ field->reset();
+ /*
+ Test if there is a default field value. The test for ->ptr is to skip
+ 'offset' fields generated by initialize_tables
+ */
+ // Initialize the table field:
+ bzero(field->ptr, field->pack_length());
+
+ length=field->pack_length();
+ pos+= length;
+
+ /* Make entry for create table */
+ recinfo->length=length;
+ recinfo->type= field->tmp_engine_column_type(use_packed_rows);
+ field->set_table_name(&table->alias);
+ }
+
+ if (thd->variables.tmp_memory_table_size == ~ (ulonglong) 0) // No limit
+ share->max_rows= ~(ha_rows) 0;
+ else
+ share->max_rows= (ha_rows) (((share->db_type() == heap_hton) ?
+ MY_MIN(thd->variables.tmp_memory_table_size,
+ thd->variables.max_heap_table_size) :
+ thd->variables.tmp_disk_table_size) /
+ share->reclength);
+ set_if_bigger(share->max_rows,1); // For dummy start options
+
+
+ //// keyinfo= param->keyinfo;
+ if (TRUE)
+ {
+ DBUG_PRINT("info",("Creating group key in temporary table"));
+ share->keys=1;
+ share->uniques= MY_TEST(using_unique_constraint);
+ table->key_info=keyinfo;
+ keyinfo->key_part=key_part_info;
+ keyinfo->flags=HA_NOSAME;
+ keyinfo->usable_key_parts= keyinfo->user_defined_key_parts= 1;
+ keyinfo->key_length=0;
+ keyinfo->rec_per_key=0;
+ keyinfo->algorithm= HA_KEY_ALG_UNDEF;
+ keyinfo->name= weedout_key;
+ {
+ key_part_info->null_bit=0;
+ key_part_info->field= field;
+ key_part_info->offset= field->offset(table->record[0]);
+ key_part_info->length= (uint16) field->key_length();
+ key_part_info->type= (uint8) field->key_type();
+ key_part_info->key_type = FIELDFLAG_BINARY;
+ if (!using_unique_constraint)
+ {
+ if (!(key_field= field->new_key_field(thd->mem_root, table,
+ group_buff,
+ key_part_info->length,
+ field->null_ptr,
+ field->null_bit)))
+ goto err;
+ }
+ keyinfo->key_length+= key_part_info->length;
+ }
+ }
+
+ if (unlikely(thd->is_fatal_error)) // If end of memory
+ goto err;
+ share->db_record_offset= 1;
+ table->no_rows= 1; // We don't need the data
+
+ // recinfo must point after last field
+ recinfo++;
+ if (share->db_type() == TMP_ENGINE_HTON)
+ {
+ if (unlikely(create_internal_tmp_table(table, keyinfo, start_recinfo,
+ &recinfo, 0)))
+ goto err;
+ }
+ if (unlikely(open_tmp_table(table)))
+ goto err;
+
+ thd->mem_root= mem_root_save;
+ tmp_table= table;
+ DBUG_RETURN(FALSE);
+
+err:
+ thd->mem_root= mem_root_save;
+ free_tmp_table(thd,table); /* purecov: inspected */
+ if (temp_pool_slot != MY_BIT_NONE)
+ bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+}
+
+
+/*
+ SemiJoinDuplicateElimination: Reset the temporary table
+*/
+
+int SJ_TMP_TABLE::sj_weedout_delete_rows()
+{
+ DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_delete_rows");
+ if (tmp_table)
+ {
+ int rc= tmp_table->file->ha_delete_all_rows();
+ DBUG_RETURN(rc);
+ }
+ have_degenerate_row= FALSE;
+ DBUG_RETURN(0);
+}
+
+
+/*
+ SemiJoinDuplicateElimination: Weed out duplicate row combinations
+
+ SYNPOSIS
+ sj_weedout_check_row()
+ thd Thread handle
+
+ DESCRIPTION
+ Try storing current record combination of outer tables (i.e. their
+ rowids) in the temporary table. This records the fact that we've seen
+ this record combination and also tells us if we've seen it before.
+
+ RETURN
+ -1 Error
+ 1 The row combination is a duplicate (discard it)
+ 0 The row combination is not a duplicate (continue)
+*/
+
+int SJ_TMP_TABLE::sj_weedout_check_row(THD *thd)
+{
+ int error;
+ SJ_TMP_TABLE::TAB *tab= tabs;
+ SJ_TMP_TABLE::TAB *tab_end= tabs_end;
+ uchar *ptr;
+ uchar *nulls_ptr;
+
+ DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_check_row");
+
+ if (is_degenerate)
+ {
+ if (have_degenerate_row)
+ DBUG_RETURN(1);
+
+ have_degenerate_row= TRUE;
+ DBUG_RETURN(0);
+ }
+
+ ptr= tmp_table->record[0] + 1;
+
+ /* Put the the rowids tuple into table->record[0]: */
+
+ // 1. Store the length
+ if (((Field_varstring*)(tmp_table->field[0]))->length_bytes == 1)
+ {
+ *ptr= (uchar)(rowid_len + null_bytes);
+ ptr++;
+ }
+ else
+ {
+ int2store(ptr, rowid_len + null_bytes);
+ ptr += 2;
+ }
+
+ nulls_ptr= ptr;
+ // 2. Zero the null bytes
+ if (null_bytes)
+ {
+ bzero(ptr, null_bytes);
+ ptr += null_bytes;
+ }
+
+ // 3. Put the rowids
+ for (uint i=0; tab != tab_end; tab++, i++)
+ {
+ handler *h= tab->join_tab->table->file;
+ if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
+ {
+ /* It's a NULL-complemented row */
+ *(nulls_ptr + tab->null_byte) |= tab->null_bit;
+ bzero(ptr + tab->rowid_offset, h->ref_length);
+ }
+ else
+ {
+ /* Copy the rowid value */
+ memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
+ }
+ }
+
+ error= tmp_table->file->ha_write_tmp_row(tmp_table->record[0]);
+ if (unlikely(error))
+ {
+ /* create_internal_tmp_table_from_heap will generate error if needed */
+ if (!tmp_table->file->is_fatal_error(error, HA_CHECK_DUP))
+ DBUG_RETURN(1); /* Duplicate */
+
+ bool is_duplicate;
+ if (create_internal_tmp_table_from_heap(thd, tmp_table, start_recinfo,
+ &recinfo, error, 1, &is_duplicate))
+ DBUG_RETURN(-1);
+ if (is_duplicate)
+ DBUG_RETURN(1);
+ }
+ DBUG_RETURN(0);
+}
+
+
+int init_dups_weedout(JOIN *join, uint first_table, int first_fanout_table, uint n_tables)
+{
+ THD *thd= join->thd;
+ DBUG_ENTER("init_dups_weedout");
+ SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
+ SJ_TMP_TABLE::TAB *last_tab= sjtabs;
+ uint jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
+ uint jt_null_bits= 0; // # null bits in tuple bytes
+ /*
+ Walk through the range and remember
+ - tables that need their rowids to be put into temptable
+ - the last outer table
+ */
+ for (JOIN_TAB *j=join->join_tab + first_table;
+ j < join->join_tab + first_table + n_tables; j++)
+ {
+ if (sj_table_is_included(join, j))
+ {
+ last_tab->join_tab= j;
+ last_tab->rowid_offset= jt_rowid_offset;
+ jt_rowid_offset += j->table->file->ref_length;
+ if (j->table->maybe_null)
+ {
+ last_tab->null_byte= jt_null_bits / 8;
+ last_tab->null_bit= jt_null_bits++;
+ }
+ last_tab++;
+ j->table->prepare_for_position();
+ j->keep_current_rowid= TRUE;
+ }
+ }
+
+ SJ_TMP_TABLE *sjtbl;
+ if (jt_rowid_offset) /* Temptable has at least one rowid */
+ {
+ size_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
+ if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
+ !(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ memcpy(sjtbl->tabs, sjtabs, tabs_size);
+ sjtbl->is_degenerate= FALSE;
+ sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
+ sjtbl->rowid_len= jt_rowid_offset;
+ sjtbl->null_bits= jt_null_bits;
+ sjtbl->null_bytes= (jt_null_bits + 7)/8;
+ if (sjtbl->create_sj_weedout_tmp_table(thd))
+ DBUG_RETURN(TRUE);
+ join->sj_tmp_tables.push_back(sjtbl->tmp_table, thd->mem_root);
+ }
+ else
+ {
+ /*
+ This is a special case where the entire subquery predicate does
+ not depend on anything at all, ie this is
+ WHERE const IN (uncorrelated select)
+ */
+ if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))))
+ DBUG_RETURN(TRUE); /* purecov: inspected */
+ sjtbl->tmp_table= NULL;
+ sjtbl->is_degenerate= TRUE;
+ sjtbl->have_degenerate_row= FALSE;
+ }
+
+ sjtbl->next_flush_table= join->join_tab[first_table].flush_weedout_table;
+ join->join_tab[first_table].flush_weedout_table= sjtbl;
+ join->join_tab[first_fanout_table].first_weedout_table= sjtbl;
+ join->join_tab[first_table + n_tables - 1].check_weed_out_table= sjtbl;
+ DBUG_RETURN(0);
+}
+
+
+/*
+ @brief
+ Set up semi-join Loose Scan strategy for execution
+
+ @detail
+ Other strategies are done in setup_semijoin_dups_elimination(),
+ however, we need to set up Loose Scan earlier, before make_join_select is
+ called. This is to prevent make_join_select() from switching full index
+ scans into quick selects (which will break Loose Scan access).
+
+ @return
+ 0 OK
+ 1 Error
+*/
+
+int setup_semijoin_loosescan(JOIN *join)
+{
+ uint i;
+ DBUG_ENTER("setup_semijoin_loosescan");
+
+ POSITION *pos= join->best_positions + join->const_tables;
+ for (i= join->const_tables ; i < join->top_join_tab_count; )
+ {
+ JOIN_TAB *tab=join->join_tab + i;
+ switch (pos->sj_strategy) {
+ case SJ_OPT_MATERIALIZE:
+ case SJ_OPT_MATERIALIZE_SCAN:
+ i+= 1; /* join tabs are embedded in the nest */
+ pos += pos->n_sj_tables;
+ break;
+ case SJ_OPT_LOOSE_SCAN:
+ {
+ /* We jump from the last table to the first one */
+ tab->loosescan_match_tab= tab + pos->n_sj_tables - 1;
+
+ /* LooseScan requires records to be produced in order */
+ if (tab->select && tab->select->quick)
+ tab->select->quick->need_sorted_output();
+
+ for (uint j= i; j < i + pos->n_sj_tables; j++)
+ join->join_tab[j].inside_loosescan_range= TRUE;
+
+ /* Calculate key length */
+ uint keylen= 0;
+ uint keyno= pos->loosescan_picker.loosescan_key;
+ for (uint kp=0; kp < pos->loosescan_picker.loosescan_parts; kp++)
+ keylen += tab->table->key_info[keyno].key_part[kp].store_length;
+
+ tab->loosescan_key= keyno;
+ tab->loosescan_key_len= keylen;
+ if (pos->n_sj_tables > 1)
+ tab[pos->n_sj_tables - 1].do_firstmatch= tab;
+ i+= pos->n_sj_tables;
+ pos+= pos->n_sj_tables;
+ break;
+ }
+ default:
+ {
+ i++;
+ pos++;
+ break;
+ }
+ }
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ Setup the strategies to eliminate semi-join duplicates.
+
+ SYNOPSIS
+ setup_semijoin_dups_elimination()
+ join Join to process
+ options Join options (needed to see if join buffering will be
+ used or not)
+ no_jbuf_after Another bit of information re where join buffering will
+ be used.
+
+ DESCRIPTION
+ Setup the strategies to eliminate semi-join duplicates. ATM there are 4
+ strategies:
+
+ 1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
+ of row combinations)
+ 2. FirstMatch (pick only the 1st matching row combination of inner tables)
+ 3. LooseScan (scanning the sj-inner table in a way that groups duplicates
+ together and picking the 1st one)
+ 4. SJ-Materialization.
+
+ The join order has "duplicate-generating ranges", and every range is
+ served by one strategy or a combination of FirstMatch with with some
+ other strategy.
+
+ "Duplicate-generating range" is defined as a range within the join order
+ that contains all of the inner tables of a semi-join. All ranges must be
+ disjoint, if tables of several semi-joins are interleaved, then the ranges
+ are joined together, which is equivalent to converting
+ SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
+ to
+ SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
+ .
+
+ Applicability conditions are as follows:
+
+ DuplicateWeedout strategy
+ ~~~~~~~~~~~~~~~~~~~~~~~~~
+
+ (ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
+ +------+ +=========================+ +---+
+ (1) (2) (3)
+
+ (1) - Prefix of OuterTables (those that participate in
+ IN-equality and/or are correlated with subquery) and outer
+ Non-correlated tables.
+ (2) - The handled range. The range starts with the first sj-inner
+ table, and covers all sj-inner and outer tables
+ Within the range, Inner, Outer, outer non-correlated tables
+ may follow in any order.
+ (3) - The suffix of outer non-correlated tables.
+
+ FirstMatch strategy
+ ~~~~~~~~~~~~~~~~~~~
+
+ (ot|nt)* [ it ((it|nt)* it) ] (nt)*
+ +------+ +==================+ +---+
+ (1) (2) (3)
+
+ (1) - Prefix of outer and non-correlated tables
+ (2) - The handled range, which may contain only inner and
+ non-correlated tables.
+ (3) - The suffix of outer non-correlated tables.
+
+ LooseScan strategy
+ ~~~~~~~~~~~~~~~~~~
+
+ (ot|ct|nt) [ loosescan_tbl (ot|nt|it)* it ] (ot|nt)*
+ +--------+ +===========+ +=============+ +------+
+ (1) (2) (3) (4)
+
+ (1) - Prefix that may contain any outer tables. The prefix must contain
+ all the non-trivially correlated outer tables. (non-trivially means
+ that the correlation is not just through the IN-equality).
+
+ (2) - Inner table for which the LooseScan scan is performed.
+
+ (3) - The remainder of the duplicate-generating range. It is served by
+ application of FirstMatch strategy, with the exception that
+ outer IN-correlated tables are considered to be non-correlated.
+
+ (4) - THe suffix of outer and outer non-correlated tables.
+
+
+ The choice between the strategies is made by the join optimizer (see
+ advance_sj_state() and fix_semijoin_strategies_for_picked_join_order()).
+ This function sets up all fields/structures/etc needed for execution except
+ for setup/initialization of semi-join materialization which is done in
+ setup_sj_materialization() (todo: can't we move that to here also?)
+
+ RETURN
+ FALSE OK
+ TRUE Out of memory error
+*/
+
+int setup_semijoin_dups_elimination(JOIN *join, ulonglong options,
+ uint no_jbuf_after)
+{
+ uint i;
+ DBUG_ENTER("setup_semijoin_dups_elimination");
+
+ join->complex_firstmatch_tables= table_map(0);
+
+ POSITION *pos= join->best_positions + join->const_tables;
+ for (i= join->const_tables ; i < join->top_join_tab_count; )
+ {
+ JOIN_TAB *tab=join->join_tab + i;
+ switch (pos->sj_strategy) {
+ case SJ_OPT_MATERIALIZE:
+ case SJ_OPT_MATERIALIZE_SCAN:
+ /* Do nothing */
+ i+= 1;// It used to be pos->n_sj_tables, but now they are embedded in a nest
+ pos += pos->n_sj_tables;
+ break;
+ case SJ_OPT_LOOSE_SCAN:
+ {
+ /* Setup already handled by setup_semijoin_loosescan */
+ i+= pos->n_sj_tables;
+ pos+= pos->n_sj_tables;
+ break;
+ }
+ case SJ_OPT_DUPS_WEEDOUT:
+ {
+ /*
+ Check for join buffering. If there is one, move the first table
+ forwards, but do not destroy other duplicate elimination methods.
+ */
+ uint first_table= i;
+
+ uint join_cache_level= join->thd->variables.join_cache_level;
+ for (uint j= i; j < i + pos->n_sj_tables; j++)
+ {
+ /*
+ When we'll properly take join buffering into account during
+ join optimization, the below check should be changed to
+ "if (join->best_positions[j].use_join_buffer &&
+ j <= no_jbuf_after)".
+ For now, use a rough criteria:
+ */
+ JOIN_TAB *js_tab=join->join_tab + j;
+ if (j != join->const_tables && js_tab->use_quick != 2 &&
+ j <= no_jbuf_after &&
+ ((js_tab->type == JT_ALL && join_cache_level != 0) ||
+ (join_cache_level > 2 && (js_tab->type == JT_REF ||
+ js_tab->type == JT_EQ_REF))))
+ {
+ /* Looks like we'll be using join buffer */
+ first_table= join->const_tables;
+ /*
+ Make sure that possible sorting of rows from the head table
+ is not to be employed.
+ */
+ if (join->get_sort_by_join_tab())
+ {
+ join->simple_order= 0;
+ join->simple_group= 0;
+ join->need_tmp= join->test_if_need_tmp_table();
+ }
+ break;
+ }
+ }
+
+ init_dups_weedout(join, first_table, i, i + pos->n_sj_tables - first_table);
+ i+= pos->n_sj_tables;
+ pos+= pos->n_sj_tables;
+ break;
+ }
+ case SJ_OPT_FIRST_MATCH:
+ {
+ JOIN_TAB *j;
+ JOIN_TAB *jump_to= tab-1;
+
+ bool complex_range= FALSE;
+ table_map tables_in_range= table_map(0);
+
+ for (j= tab; j != tab + pos->n_sj_tables; j++)
+ {
+ tables_in_range |= j->table->map;
+ if (!j->emb_sj_nest)
+ {
+ /*
+ Got a table that's not within any semi-join nest. This is a case
+ like this:
+
+ SELECT * FROM ot1, nt1 WHERE ot1.col IN (SELECT expr FROM it1, it2)
+
+ with a join order of
+
+ +----- FirstMatch range ----+
+ | |
+ ot1 it1 nt1 nt2 it2 it3 ...
+ | ^
+ | +-------- 'j' points here
+ +------------- SJ_OPT_FIRST_MATCH was set for this table as
+ it's the first one that produces duplicates
+
+ */
+ DBUG_ASSERT(j != tab); /* table ntX must have an itX before it */
+
+ /*
+ If the table right before us is an inner table (like it1 in the
+ picture), it should be set to jump back to previous outer-table
+ */
+ if (j[-1].emb_sj_nest)
+ j[-1].do_firstmatch= jump_to;
+
+ jump_to= j; /* Jump back to us */
+ complex_range= TRUE;
+ }
+ else
+ {
+ j->first_sj_inner_tab= tab;
+ j->last_sj_inner_tab= tab + pos->n_sj_tables - 1;
+ }
+ }
+ j[-1].do_firstmatch= jump_to;
+ i+= pos->n_sj_tables;
+ pos+= pos->n_sj_tables;
+
+ if (complex_range)
+ join->complex_firstmatch_tables|= tables_in_range;
+ break;
+ }
+ case SJ_OPT_NONE:
+ i++;
+ pos++;
+ break;
+ }
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ Destroy all temporary tables created by NL-semijoin runtime
+*/
+
+void destroy_sj_tmp_tables(JOIN *join)
+{
+ List_iterator<TABLE> it(join->sj_tmp_tables);
+ TABLE *table;
+ while ((table= it++))
+ {
+ /*
+ SJ-Materialization tables are initialized for either sequential reading
+ or index lookup, DuplicateWeedout tables are not initialized for read
+ (we only write to them), so need to call ha_index_or_rnd_end.
+ */
+ table->file->ha_index_or_rnd_end();
+ free_tmp_table(join->thd, table);
+ }
+ join->sj_tmp_tables.empty();
+ join->sjm_info_list.empty();
+}
+
+
+/*
+ Remove all records from all temp tables used by NL-semijoin runtime
+
+ SYNOPSIS
+ clear_sj_tmp_tables()
+ join The join to remove tables for
+
+ DESCRIPTION
+ Remove all records from all temp tables used by NL-semijoin runtime. This
+ must be done before every join re-execution.
+*/
+
+int clear_sj_tmp_tables(JOIN *join)
+{
+ int res;
+ List_iterator<TABLE> it(join->sj_tmp_tables);
+ TABLE *table;
+ while ((table= it++))
+ {
+ if ((res= table->file->ha_delete_all_rows()))
+ return res; /* purecov: inspected */
+ }
+
+ SJ_MATERIALIZATION_INFO *sjm;
+ List_iterator<SJ_MATERIALIZATION_INFO> it2(join->sjm_info_list);
+ while ((sjm= it2++))
+ {
+ sjm->materialized= FALSE;
+ }
+ return 0;
+}
+
+
+/*
+ Check if the table's rowid is included in the temptable
+
+ SYNOPSIS
+ sj_table_is_included()
+ join The join
+ join_tab The table to be checked
+
+ DESCRIPTION
+ SemiJoinDuplicateElimination: check the table's rowid should be included
+ in the temptable. This is so if
+
+ 1. The table is not embedded within some semi-join nest
+ 2. The has been pulled out of a semi-join nest, or
+
+ 3. The table is functionally dependent on some previous table
+
+ [4. This is also true for constant tables that can't be
+ NULL-complemented but this function is not called for such tables]
+
+ RETURN
+ TRUE - Include table's rowid
+ FALSE - Don't
+*/
+
+static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
+{
+ if (join_tab->emb_sj_nest)
+ return FALSE;
+
+ /* Check if this table is functionally dependent on the tables that
+ are within the same outer join nest
+ */
+ TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;
+ if (join_tab->type == JT_EQ_REF)
+ {
+ table_map depends_on= 0;
+ uint idx;
+
+ for (uint kp= 0; kp < join_tab->ref.key_parts; kp++)
+ depends_on |= join_tab->ref.items[kp]->used_tables();
+
+ Table_map_iterator it(depends_on & ~PSEUDO_TABLE_BITS);
+ while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
+ {
+ JOIN_TAB *ref_tab= join->map2table[idx];
+ if (embedding != ref_tab->table->pos_in_table_list->embedding)
+ return TRUE;
+ }
+ /* Ok, functionally dependent */
+ return FALSE;
+ }
+ /* Not functionally dependent => need to include*/
+ return TRUE;
+}
+
+
+/*
+ Index lookup-based subquery: save some flags for EXPLAIN output
+
+ SYNOPSIS
+ save_index_subquery_explain_info()
+ join_tab Subquery's join tab (there is only one as index lookup is
+ only used for subqueries that are single-table SELECTs)
+ where Subquery's WHERE clause
+
+ DESCRIPTION
+ For index lookup-based subquery (i.e. one executed with
+ subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
+ check its EXPLAIN output row should contain
+ "Using index" (TAB_INFO_FULL_SCAN_ON_NULL)
+ "Using Where" (TAB_INFO_USING_WHERE)
+ "Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
+ and set appropriate flags in join_tab->packed_info.
+*/
+
+static void save_index_subquery_explain_info(JOIN_TAB *join_tab, Item* where)
+{
+ join_tab->packed_info= TAB_INFO_HAVE_VALUE;
+ if (join_tab->table->covering_keys.is_set(join_tab->ref.key))
+ join_tab->packed_info |= TAB_INFO_USING_INDEX;
+ if (where)
+ join_tab->packed_info |= TAB_INFO_USING_WHERE;
+ for (uint i = 0; i < join_tab->ref.key_parts; i++)
+ {
+ if (join_tab->ref.cond_guards[i])
+ {
+ join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
+ break;
+ }
+ }
+}
+
+
+/*
+ Check if the join can be rewritten to [unique_]indexsubquery_engine
+
+ DESCRIPTION
+ Check if the join can be changed into [unique_]indexsubquery_engine.
+
+ The check is done after join optimization, the idea is that if the join
+ has only one table and uses a [eq_]ref access generated from subselect's
+ IN-equality then we replace it with a subselect_indexsubquery_engine or a
+ subselect_uniquesubquery_engine.
+
+ RETURN
+ 0 - Ok, rewrite done (stop join optimization and return)
+ 1 - Fatal error (stop join optimization and return)
+ -1 - No rewrite performed, continue with join optimization
+*/
+
+int rewrite_to_index_subquery_engine(JOIN *join)
+{
+ THD *thd= join->thd;
+ JOIN_TAB* join_tab=join->join_tab;
+ SELECT_LEX_UNIT *unit= join->unit;
+ DBUG_ENTER("rewrite_to_index_subquery_engine");
+
+ /*
+ is this simple IN subquery?
+ */
+ /* TODO: In order to use these more efficient subquery engines in more cases,
+ the following problems need to be solved:
+ - the code that removes GROUP BY (group_list), also adds an ORDER BY
+ (order), thus GROUP BY queries (almost?) never pass through this branch.
+ Solution: remove the test below '!join->order', because we remove the
+ ORDER clase for subqueries anyway.
+ - in order to set a more efficient engine, the optimizer needs to both
+ decide to remove GROUP BY, *and* select one of the JT_[EQ_]REF[_OR_NULL]
+ access methods, *and* loose scan should be more expensive or
+ inapliccable. When is that possible?
+ - Consider expanding the applicability of this rewrite for loose scan
+ for group by queries.
+ */
+ if (!join->group_list && !join->order &&
+ join->unit->item &&
+ join->unit->item->substype() == Item_subselect::IN_SUBS &&
+ join->table_count == 1 && join->conds &&
+ !join->unit->is_unit_op())
+ {
+ if (!join->having)
+ {
+ Item *where= join->conds;
+ if (join_tab[0].type == JT_EQ_REF &&
+ join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
+ {
+ remove_subq_pushed_predicates(join, &where);
+ save_index_subquery_explain_info(join_tab, where);
+ join_tab[0].type= JT_UNIQUE_SUBQUERY;
+ join->error= 0;
+ DBUG_RETURN(unit->item->
+ change_engine(new
+ subselect_uniquesubquery_engine(thd,
+ join_tab,
+ unit->item->get_IN_subquery(),
+ where)));
+ }
+ else if (join_tab[0].type == JT_REF &&
+ join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
+ {
+ remove_subq_pushed_predicates(join, &where);
+ save_index_subquery_explain_info(join_tab, where);
+ join_tab[0].type= JT_INDEX_SUBQUERY;
+ join->error= 0;
+ DBUG_RETURN(unit->item->
+ change_engine(new
+ subselect_indexsubquery_engine(thd,
+ join_tab,
+ unit->item->get_IN_subquery(),
+ where,
+ NULL,
+ 0)));
+ }
+ } else if (join_tab[0].type == JT_REF_OR_NULL &&
+ join_tab[0].ref.items[0]->name.str == in_left_expr_name.str &&
+ join->having->name.str == in_having_cond.str)
+ {
+ join_tab[0].type= JT_INDEX_SUBQUERY;
+ join->error= 0;
+ join->conds= remove_additional_cond(join->conds);
+ save_index_subquery_explain_info(join_tab, join->conds);
+ DBUG_RETURN(unit->item->
+ change_engine(new subselect_indexsubquery_engine(thd,
+ join_tab,
+ unit->item->get_IN_subquery(),
+ join->conds,
+ join->having,
+ 1)));
+ }
+ }
+
+ DBUG_RETURN(-1); /* Haven't done the rewrite */
+}
+
+
+/**
+ Remove additional condition inserted by IN/ALL/ANY transformation.
+
+ @param conds condition for processing
+
+ @return
+ new conditions
+*/
+
+static Item *remove_additional_cond(Item* conds)
+{
+ if (conds->name.str == in_additional_cond.str)
+ return 0;
+ if (conds->type() == Item::COND_ITEM)
+ {
+ Item_cond *cnd= (Item_cond*) conds;
+ List_iterator<Item> li(*(cnd->argument_list()));
+ Item *item;
+ while ((item= li++))
+ {
+ if (item->name.str == in_additional_cond.str)
+ {
+ li.remove();
+ if (cnd->argument_list()->elements == 1)
+ return cnd->argument_list()->head();
+ return conds;
+ }
+ }
+ }
+ return conds;
+}
+
+
+/*
+ Remove the predicates pushed down into the subquery
+
+ SYNOPSIS
+ remove_subq_pushed_predicates()
+ where IN Must be NULL
+ OUT The remaining WHERE condition, or NULL
+
+ DESCRIPTION
+ Given that this join will be executed using (unique|index)_subquery,
+ without "checking NULL", remove the predicates that were pushed down
+ into the subquery.
+
+ If the subquery compares scalar values, we can remove the condition that
+ was wrapped into trig_cond (it will be checked when needed by the subquery
+ engine)
+
+ If the subquery compares row values, we need to keep the wrapped
+ equalities in the WHERE clause: when the left (outer) tuple has both NULL
+ and non-NULL values, we'll do a full table scan and will rely on the
+ equalities corresponding to non-NULL parts of left tuple to filter out
+ non-matching records.
+
+ TODO: We can remove the equalities that will be guaranteed to be true by the
+ fact that subquery engine will be using index lookup. This must be done only
+ for cases where there are no conversion errors of significance, e.g. 257
+ that is searched in a byte. But this requires homogenization of the return
+ codes of all Field*::store() methods.
+*/
+
+static void remove_subq_pushed_predicates(JOIN *join, Item **where)
+{
+ if (join->conds->type() == Item::FUNC_ITEM &&
+ ((Item_func *)join->conds)->functype() == Item_func::EQ_FUNC &&
+ ((Item_func *)join->conds)->arguments()[0]->type() == Item::REF_ITEM &&
+ ((Item_func *)join->conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
+ test_if_ref (join->conds,
+ (Item_field *)((Item_func *)join->conds)->arguments()[1],
+ ((Item_func *)join->conds)->arguments()[0]))
+ {
+ *where= 0;
+ return;
+ }
+}
+
+
+
+
+/**
+ Optimize all subqueries of a query that were not flattened into a semijoin.
+
+ @details
+ Optimize all immediate children subqueries of a query.
+
+ This phase must be called after substitute_for_best_equal_field() because
+ that function may replace items with other items from a multiple equality,
+ and we need to reference the correct items in the index access method of the
+ IN predicate.
+
+ @return Operation status
+ @retval FALSE success.
+ @retval TRUE error occurred.
+*/
+
+bool JOIN::optimize_unflattened_subqueries()
+{
+ return select_lex->optimize_unflattened_subqueries(false);
+}
+
+/**
+ Optimize all constant subqueries of a query that were not flattened into
+ a semijoin.
+
+ @details
+ Similar to other constant conditions, constant subqueries can be used in
+ various constant optimizations. Having optimized constant subqueries before
+ these constant optimizations, makes it possible to estimate if a subquery
+ is "cheap" enough to be executed during the optimization phase.
+
+ Constant subqueries can be optimized and evaluated independent of the outer
+ query, therefore if const_only = true, this method can be called early in
+ the optimization phase of the outer query.
+
+ @return Operation status
+ @retval FALSE success.
+ @retval TRUE error occurred.
+*/
+
+bool JOIN::optimize_constant_subqueries()
+{
+ ulonglong save_options= select_lex->options;
+ bool res;
+ /*
+ Constant subqueries may be executed during the optimization phase.
+ In EXPLAIN mode the optimizer doesn't initialize many of the data structures
+ needed for execution. In order to make it possible to execute subqueries
+ during optimization, constant subqueries must be optimized for execution,
+ not for EXPLAIN.
+ */
+ select_lex->options&= ~SELECT_DESCRIBE;
+ res= select_lex->optimize_unflattened_subqueries(true);
+ select_lex->options= save_options;
+ return res;
+}
+
+
+/*
+ Join tab execution startup function.
+
+ SYNOPSIS
+ join_tab_execution_startup()
+ tab Join tab to perform startup actions for
+
+ DESCRIPTION
+ Join tab execution startup function. This is different from
+ tab->read_first_record in the regard that this has actions that are to be
+ done once per join execution.
+
+ Currently there are only two possible startup functions, so we have them
+ both here inside if (...) branches. In future we could switch to function
+ pointers.
+
+ TODO: consider moving this together with JOIN_TAB::preread_init
+
+ RETURN
+ NESTED_LOOP_OK - OK
+ NESTED_LOOP_ERROR| NESTED_LOOP_KILLED - Error, abort the join execution
+*/
+
+enum_nested_loop_state join_tab_execution_startup(JOIN_TAB *tab)
+{
+ Item_in_subselect *in_subs;
+ DBUG_ENTER("join_tab_execution_startup");
+
+ if (tab->table->pos_in_table_list &&
+ (in_subs= tab->table->pos_in_table_list->jtbm_subselect))
+ {
+ /* It's a non-merged SJM nest */
+ DBUG_ASSERT(in_subs->engine->engine_type() ==
+ subselect_engine::HASH_SJ_ENGINE);
+ subselect_hash_sj_engine *hash_sj_engine=
+ ((subselect_hash_sj_engine*)in_subs->engine);
+ if (!hash_sj_engine->is_materialized)
+ {
+ hash_sj_engine->materialize_join->exec();
+ hash_sj_engine->is_materialized= TRUE;
+
+ if (unlikely(hash_sj_engine->materialize_join->error) ||
+ unlikely(tab->join->thd->is_fatal_error))
+ DBUG_RETURN(NESTED_LOOP_ERROR);
+ }
+ }
+ else if (tab->bush_children)
+ {
+ /* It's a merged SJM nest */
+ enum_nested_loop_state rc;
+ SJ_MATERIALIZATION_INFO *sjm= tab->bush_children->start->emb_sj_nest->sj_mat_info;
+
+ if (!sjm->materialized)
+ {
+ JOIN *join= tab->join;
+ JOIN_TAB *join_tab= tab->bush_children->start;
+ JOIN_TAB *save_return_tab= join->return_tab;
+ /*
+ Now run the join for the inner tables. The first call is to run the
+ join, the second one is to signal EOF (this is essential for some
+ join strategies, e.g. it will make join buffering flush the records)
+ */
+ if ((rc= sub_select(join, join_tab, FALSE/* no EOF */)) < 0 ||
+ (rc= sub_select(join, join_tab, TRUE/* now EOF */)) < 0)
+ {
+ join->return_tab= save_return_tab;
+ DBUG_RETURN(rc); /* it's NESTED_LOOP_(ERROR|KILLED)*/
+ }
+ join->return_tab= save_return_tab;
+ sjm->materialized= TRUE;
+ }
+ }
+
+ DBUG_RETURN(NESTED_LOOP_OK);
+}
+
+
+/*
+ Create a dummy temporary table, useful only for the sake of having a
+ TABLE* object with map,tablenr and maybe_null properties.
+
+ This is used by non-mergeable semi-join materilization code to handle
+ degenerate cases where materialized subquery produced "Impossible WHERE"
+ and thus wasn't materialized.
+*/
+
+TABLE *create_dummy_tmp_table(THD *thd)
+{
+ DBUG_ENTER("create_dummy_tmp_table");
+ TABLE *table;
+ TMP_TABLE_PARAM sjm_table_param;
+ sjm_table_param.init();
+ sjm_table_param.field_count= 1;
+ List<Item> sjm_table_cols;
+ const LEX_CSTRING dummy_name= { STRING_WITH_LEN("dummy") };
+ Item *column_item= new (thd->mem_root) Item_int(thd, 1);
+ if (!column_item)
+ DBUG_RETURN(NULL);
+
+ sjm_table_cols.push_back(column_item, thd->mem_root);
+ if (!(table= create_tmp_table(thd, &sjm_table_param,
+ sjm_table_cols, (ORDER*) 0,
+ TRUE /* distinct */,
+ 1, /*save_sum_fields*/
+ thd->variables.option_bits |
+ TMP_TABLE_ALL_COLUMNS,
+ HA_POS_ERROR /*rows_limit */,
+ &dummy_name, TRUE /* Do not open */)))
+ {
+ DBUG_RETURN(NULL);
+ }
+ DBUG_RETURN(table);
+}
+
+
+/*
+ A class that is used to catch one single tuple that is sent to the join
+ output, and save it in Item_cache element(s).
+
+ It is very similar to select_singlerow_subselect but doesn't require a
+ Item_singlerow_subselect item.
+*/
+
+class select_value_catcher :public select_subselect
+{
+public:
+ select_value_catcher(THD *thd_arg, Item_subselect *item_arg):
+ select_subselect(thd_arg, item_arg)
+ {}
+ int send_data(List<Item> &items);
+ int setup(List<Item> *items);
+ bool assigned; /* TRUE <=> we've caught a value */
+ uint n_elements; /* How many elements we get */
+ Item_cache **row; /* Array of cache elements */
+};
+
+
+int select_value_catcher::setup(List<Item> *items)
+{
+ assigned= FALSE;
+ n_elements= items->elements;
+
+ if (!(row= (Item_cache**) thd->alloc(sizeof(Item_cache*) * n_elements)))
+ return TRUE;
+
+ Item *sel_item;
+ List_iterator<Item> li(*items);
+ for (uint i= 0; (sel_item= li++); i++)
+ {
+ if (!(row[i]= sel_item->get_cache(thd)))
+ return TRUE;
+ row[i]->setup(thd, sel_item);
+ }
+ return FALSE;
+}
+
+
+int select_value_catcher::send_data(List<Item> &items)
+{
+ DBUG_ENTER("select_value_catcher::send_data");
+ DBUG_ASSERT(!assigned);
+ DBUG_ASSERT(items.elements == n_elements);
+
+ Item *val_item;
+ List_iterator_fast<Item> li(items);
+ for (uint i= 0; (val_item= li++); i++)
+ {
+ row[i]->store(val_item);
+ row[i]->cache_value();
+ }
+ assigned= TRUE;
+ DBUG_RETURN(0);
+}
+
+
+/**
+ @brief
+ Attach conditions to already optimized condition
+
+ @param thd the thread handle
+ @param cond the condition to which add new conditions
+ @param cond_eq IN/OUT the multiple equalities of cond
+ @param new_conds the list of conditions to be added
+ @param cond_value the returned value of the condition
+ if it can be evaluated
+
+ @details
+ The method creates new condition through union of cond and
+ the conditions from new_conds list.
+ The method is called after optimize_cond() for cond. The result
+ of the union should be the same as if it was done before the
+ the optimize_cond() call.
+
+ @retval otherwise the created condition
+ @retval NULL if an error occurs
+*/
+
+Item *and_new_conditions_to_optimized_cond(THD *thd, Item *cond,
+ COND_EQUAL **cond_eq,
+ List<Item> &new_conds,
+ Item::cond_result *cond_value)
+{
+ COND_EQUAL new_cond_equal;
+ Item *item;
+ Item_equal *mult_eq;
+ bool is_simplified_cond= false;
+ /* The list where parts of the new condition are stored. */
+ List_iterator<Item> li(new_conds);
+ List_iterator_fast<Item_equal> it(new_cond_equal.current_level);
+
+ /*
+ Create multiple equalities from the equalities of the list new_conds.
+ Save the created multiple equalities in new_cond_equal.
+ If multiple equality can't be created or the condition
+ from new_conds list isn't an equality leave it in new_conds
+ list.
+
+ The equality can't be converted into the multiple equality if it
+ is a knowingly false or true equality.
+ For example, (3 = 1) equality.
+ */
+ while ((item=li++))
+ {
+ if (item->type() == Item::FUNC_ITEM &&
+ ((Item_func *) item)->functype() == Item_func::EQ_FUNC &&
+ check_simple_equality(thd,
+ Item::Context(Item::ANY_SUBST,
+ ((Item_func_eq *)item)->compare_type_handler(),
+ ((Item_func_eq *)item)->compare_collation()),
+ ((Item_func *)item)->arguments()[0],
+ ((Item_func *)item)->arguments()[1],
+ &new_cond_equal))
+ li.remove();
+ }
+
+ it.rewind();
+ if (cond && cond->type() == Item::COND_ITEM &&
+ ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
+ {
+ /*
+ Case when cond is an AND-condition.
+ Union AND-condition cond, created multiple equalities from
+ new_cond_equal and remaining conditions from new_conds.
+ */
+ COND_EQUAL *cond_equal= &((Item_cond_and *) cond)->m_cond_equal;
+ List<Item_equal> *cond_equalities= &cond_equal->current_level;
+ List<Item> *and_args= ((Item_cond_and *)cond)->argument_list();
+
+ /*
+ Disjoin multiple equalities of cond.
+ Merge these multiple equalities with the multiple equalities of
+ new_cond_equal. Save the result in new_cond_equal.
+ Check if after the merge some multiple equalities are knowingly
+ true or false.
+ */
+ and_args->disjoin((List<Item> *) cond_equalities);
+ while ((mult_eq= it++))
+ {
+ mult_eq->upper_levels= 0;
+ mult_eq->merge_into_list(thd, cond_equalities, false, false);
+ }
+ List_iterator_fast<Item_equal> ei(*cond_equalities);
+ while ((mult_eq= ei++))
+ {
+ if (mult_eq->const_item() && !mult_eq->val_int())
+ is_simplified_cond= true;
+ else
+ {
+ mult_eq->unfix_fields();
+ if (mult_eq->fix_fields(thd, NULL))
+ return NULL;
+ }
+ }
+
+ li.rewind();
+ while ((item=li++))
+ {
+ /*
+ There still can be some equalities at not top level of new_conds
+ conditions that are not transformed into multiple equalities.
+ To transform them build_item_equal() is called.
+
+ Examples of not top level equalities:
+
+ 1. (t1.a = 3) OR (t1.b > 5)
+ (t1.a = 3) - not top level equality.
+ It is inside OR condition
+
+ 2. ((t3.d = t3.c) AND (t3.c < 15)) OR (t3.d > 1)
+ (t1.d = t3.c) - not top level equality.
+ It is inside AND condition which is a part of OR condition
+ */
+ if (item->type() == Item::COND_ITEM &&
+ ((Item_cond *)item)->functype() == Item_func::COND_OR_FUNC)
+ {
+ item= item->build_equal_items(thd,
+ &((Item_cond_and *) cond)->m_cond_equal,
+ false, NULL);
+ }
+ and_args->push_back(item, thd->mem_root);
+ }
+ and_args->append((List<Item> *) cond_equalities);
+ *cond_eq= &((Item_cond_and *) cond)->m_cond_equal;
+ }
+ else
+ {
+ /*
+ Case when cond isn't an AND-condition or is NULL.
+ There can be several cases:
+
+ 1. cond is a multiple equality.
+ In this case merge cond with the multiple equalities of
+ new_cond_equal.
+ Create new condition from the created multiple equalities
+ and new_conds list conditions.
+ 2. cond is NULL
+ Create new condition from new_conds list conditions
+ and multiple equalities from new_cond_equal.
+ 3. Otherwise
+ Create new condition through union of cond, conditions from new_conds
+ list and created multiple equalities from new_cond_equal.
+ */
+ List<Item> new_conds_list;
+ /* Flag is set to true if cond is a multiple equality */
+ bool is_mult_eq= (cond && cond->type() == Item::FUNC_ITEM &&
+ ((Item_func*) cond)->functype() == Item_func::MULT_EQUAL_FUNC);
+
+ /*
+ If cond is non-empty and is not multiple equality save it as
+ a part of a new condition.
+ */
+ if (cond && !is_mult_eq &&
+ new_conds_list.push_back(cond, thd->mem_root))
+ return NULL;
+
+ /*
+ If cond is a multiple equality merge it with new_cond_equal
+ multiple equalities.
+ */
+ if (is_mult_eq)
+ {
+ Item_equal *eq_cond= (Item_equal *)cond;
+ eq_cond->upper_levels= 0;
+ eq_cond->merge_into_list(thd, &new_cond_equal.current_level,
+ false, false);
+ }
+
+ /**
+ Fix created multiple equalities and check if they are knowingly
+ true or false.
+ */
+ List_iterator_fast<Item_equal> ei(new_cond_equal.current_level);
+ while ((mult_eq=ei++))
+ {
+ if (mult_eq->const_item() && !mult_eq->val_int())
+ is_simplified_cond= true;
+ else
+ {
+ mult_eq->unfix_fields();
+ if (mult_eq->fix_fields(thd, NULL))
+ return NULL;
+ }
+ }
+
+ /*
+ Create AND condition if new condition will have two or
+ more elements.
+ */
+ Item_cond_and *and_cond= 0;
+ COND_EQUAL *inherited= 0;
+ if (new_conds_list.elements +
+ new_conds.elements +
+ new_cond_equal.current_level.elements > 1)
+ {
+ and_cond= new (thd->mem_root) Item_cond_and(thd);
+ and_cond->m_cond_equal.copy(new_cond_equal);
+ inherited= &and_cond->m_cond_equal;
+ }
+
+ li.rewind();
+ while ((item=li++))
+ {
+ /*
+ Look for the comment in the case when cond is an
+ AND condition above the build_equal_items() call.
+ */
+ if (item->type() == Item::COND_ITEM &&
+ ((Item_cond *)item)->functype() == Item_func::COND_OR_FUNC)
+ {
+ item= item->build_equal_items(thd, inherited, false, NULL);
+ }
+ new_conds_list.push_back(item, thd->mem_root);
+ }
+ new_conds_list.append((List<Item> *)&new_cond_equal.current_level);
+
+ if (and_cond)
+ {
+ and_cond->argument_list()->append(&new_conds_list);
+ cond= (Item *)and_cond;
+ *cond_eq= &((Item_cond_and *) cond)->m_cond_equal;
+ }
+ else
+ {
+ List_iterator_fast<Item> iter(new_conds_list);
+ cond= iter++;
+ if (cond->type() == Item::FUNC_ITEM &&
+ ((Item_func *)cond)->functype() == Item_func::MULT_EQUAL_FUNC)
+ {
+ if (!(*cond_eq))
+ *cond_eq= new COND_EQUAL();
+ (*cond_eq)->copy(new_cond_equal);
+ }
+ else
+ *cond_eq= 0;
+ }
+ }
+
+ if (!cond)
+ return NULL;
+
+ if (*cond_eq)
+ {
+ /*
+ The multiple equalities are attached only to the upper level
+ of AND-condition cond.
+ Push them down to the bottom levels of cond AND-condition if needed.
+ */
+ propagate_new_equalities(thd, cond,
+ &(*cond_eq)->current_level,
+ 0,
+ &is_simplified_cond);
+ cond= cond->propagate_equal_fields(thd,
+ Item::Context_boolean(),
+ *cond_eq);
+ cond->update_used_tables();
+ }
+ /* Check if conds has knowingly true or false parts. */
+ if (cond &&
+ !is_simplified_cond &&
+ cond->walk(&Item::is_simplified_cond_processor, 0, 0))
+ is_simplified_cond= true;
+
+
+ /*
+ If it was found that there are some knowingly true or false equalities
+ remove them from cond and set cond_value to the appropriate value.
+ */
+ if (cond && is_simplified_cond)
+ cond= cond->remove_eq_conds(thd, cond_value, true);
+
+ if (cond && cond->fix_fields_if_needed(thd, NULL))
+ return NULL;
+
+ return cond;
+}
+
+
+/**
+ @brief Materialize a degenerate jtbm semi join
+
+ @param thd thread handler
+ @param tbl table list for the target jtbm semi join table
+ @param subq_pred IN subquery predicate with the degenerate jtbm semi join
+ @param eq_list IN/OUT the list where to add produced equalities
+
+ @details
+ The method materializes the degenerate jtbm semi join for the
+ subquery from the IN subquery predicate subq_pred taking table
+ as the target for materialization.
+ Any degenerate table is guaranteed to produce 0 or 1 record.
+ Examples of both cases:
+
+ select * from ot where col in (select ... from it where 2>3)
+ select * from ot where col in (select MY_MIN(it.key) from it)
+
+ in this case, there is no necessity to create a temp.table for
+ materialization.
+ We now just need to
+ 1. Check whether 1 or 0 records are produced, setup this as a
+ constant join tab.
+ 2. Create a dummy temporary table, because all of the join
+ optimization code relies on TABLE object being present.
+
+ In the case when materialization produces one row the function
+ additionally creates equalities between the expressions from the
+ left part of the IN subquery predicate and the corresponding
+ columns of the produced row. These equalities are added to the
+ list eq_list. They are supposed to be conjuncted with the condition
+ of the WHERE clause.
+
+ @retval TRUE if an error occurs
+ @retval FALSE otherwise
+*/
+
+bool execute_degenerate_jtbm_semi_join(THD *thd,
+ TABLE_LIST *tbl,
+ Item_in_subselect *subq_pred,
+ List<Item> &eq_list)
+{
+ DBUG_ENTER("execute_degenerate_jtbm_semi_join");
+ select_value_catcher *new_sink;
+
+ DBUG_ASSERT(subq_pred->engine->engine_type() ==
+ subselect_engine::SINGLE_SELECT_ENGINE);
+ subselect_single_select_engine *engine=
+ (subselect_single_select_engine*)subq_pred->engine;
+ if (!(new_sink= new (thd->mem_root) select_value_catcher(thd, subq_pred)))
+ DBUG_RETURN(TRUE);
+ if (new_sink->setup(&engine->select_lex->join->fields_list) ||
+ engine->select_lex->join->change_result(new_sink, NULL) ||
+ engine->exec())
+ {
+ DBUG_RETURN(TRUE);
+ }
+ subq_pred->is_jtbm_const_tab= TRUE;
+
+ if (new_sink->assigned)
+ {
+ /*
+ Subselect produced one row, which is saved in new_sink->row.
+ Save "left_expr[i] == row[i]" equalities into the eq_list.
+ */
+ subq_pred->jtbm_const_row_found= TRUE;
+
+ Item *eq_cond;
+ Item *left_exp= subq_pred->left_exp();
+ uint ncols= left_exp->cols();
+ for (uint i= 0; i < ncols; i++)
+ {
+ eq_cond=
+ new (thd->mem_root) Item_func_eq(thd,
+ left_exp->element_index(i),
+ new_sink->row[i]);
+ if (!eq_cond || eq_cond->fix_fields(thd, NULL) ||
+ eq_list.push_back(eq_cond, thd->mem_root))
+ DBUG_RETURN(TRUE);
+ }
+ }
+ else
+ {
+ /* Subselect produced no rows. Just set the flag */
+ subq_pred->jtbm_const_row_found= FALSE;
+ }
+
+ TABLE *dummy_table;
+ if (!(dummy_table= create_dummy_tmp_table(thd)))
+ DBUG_RETURN(TRUE);
+ tbl->table= dummy_table;
+ tbl->table->pos_in_table_list= tbl;
+ /*
+ Note: the table created above may be freed by:
+ 1. JOIN_TAB::cleanup(), when the parent join is a regular join.
+ 2. cleanup_empty_jtbm_semi_joins(), when the parent join is a
+ degenerate join (e.g. one with "Impossible where").
+ */
+ setup_table_map(tbl->table, tbl, tbl->jtbm_table_no);
+ DBUG_RETURN(FALSE);
+}
+
+
+/**
+ @brief
+ Execute degenerate jtbm semi joins before optimize_cond() for parent
+
+ @param join the parent join for jtbm semi joins
+ @param join_list the list of tables where jtbm semi joins are processed
+ @param eq_list IN/OUT the list where to add equalities produced after
+ materialization of single-row degenerate jtbm semi joins
+
+ @details
+ The method traverses join_list trying to find any degenerate jtbm semi
+ joins for subqueries of IN predicates. For each degenerate jtbm
+ semi join execute_degenerate_jtbm_semi_join() is called. As a result
+ of this call new equalities that substitute for single-row materialized
+ jtbm semi join are added to eq_list.
+
+ In the case when a table is nested in another table 'nested_join' the
+ method is recursively called for the join_list of the 'nested_join' trying
+ to find in the list any degenerate jtbm semi joins. Currently a jtbm semi
+ join may occur in a mergeable semi join nest.
+
+ @retval TRUE if an error occurs
+ @retval FALSE otherwise
+*/
+
+bool setup_degenerate_jtbm_semi_joins(JOIN *join,
+ List<TABLE_LIST> *join_list,
+ List<Item> &eq_list)
+{
+ TABLE_LIST *table;
+ NESTED_JOIN *nested_join;
+ List_iterator<TABLE_LIST> li(*join_list);
+ THD *thd= join->thd;
+ DBUG_ENTER("setup_degenerate_jtbm_semi_joins");
+
+ while ((table= li++))
+ {
+ Item_in_subselect *subq_pred;
+
+ if ((subq_pred= table->jtbm_subselect))
+ {
+ JOIN *subq_join= subq_pred->unit->first_select()->join;
+
+ if (!subq_join->tables_list || !subq_join->table_count)
+ {
+ if (execute_degenerate_jtbm_semi_join(thd,
+ table,
+ subq_pred,
+ eq_list))
+ DBUG_RETURN(TRUE);
+ join->is_orig_degenerated= true;
+ }
+ }
+ if ((nested_join= table->nested_join))
+ {
+ if (setup_degenerate_jtbm_semi_joins(join,
+ &nested_join->join_list,
+ eq_list))
+ DBUG_RETURN(TRUE);
+ }
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+/**
+ @brief
+ Optimize jtbm semi joins for materialization
+
+ @param join the parent join for jtbm semi joins
+ @param join_list the list of TABLE_LIST objects where jtbm semi join
+ can occur
+ @param eq_list IN/OUT the list where to add produced equalities
+
+ @details
+ This method is called by the optimizer after the call of
+ optimize_cond() for parent select.
+ The method traverses join_list trying to find any jtbm semi joins for
+ subqueries from IN predicates and optimizes them.
+ After the optimization some of jtbm semi joins may become degenerate.
+ For example the subquery 'SELECT MAX(b) FROM t2' from the query
+
+ SELECT * FROM t1 WHERE 4 IN (SELECT MAX(b) FROM t2);
+
+ will become degenerate if there is an index on t2.b.
+ If a subquery becomes degenerate it is handled by the function
+ execute_degenerate_jtbm_semi_join().
+
+ Otherwise the method creates a temporary table in which the subquery
+ of the jtbm semi join will be materialied.
+
+ The function saves the equalities between all pairs of the expressions
+ from the left part of the IN subquery predicate and the corresponding
+ columns of the subquery from the predicate in eq_list appending them
+ to the list. The equalities of eq_list will be later conjucted with the
+ condition of the WHERE clause.
+
+ In the case when a table is nested in another table 'nested_join' the
+ method is recursively called for the join_list of the 'nested_join' trying
+ to find in the list any degenerate jtbm semi joins. Currently a jtbm semi
+ join may occur in a mergeable semi join nest.
+
+ @retval TRUE if an error occurs
+ @retval FALSE otherwise
+*/
+
+bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list,
+ List<Item> &eq_list)
+{
+ TABLE_LIST *table;
+ NESTED_JOIN *nested_join;
+ List_iterator<TABLE_LIST> li(*join_list);
+ THD *thd= join->thd;
+ DBUG_ENTER("setup_jtbm_semi_joins");
+
+ while ((table= li++))
+ {
+ Item_in_subselect *subq_pred;
+
+ if ((subq_pred= table->jtbm_subselect))
+ {
+ double rows;
+ double read_time;
+
+ /*
+ Perform optimization of the subquery, so that we know estimated
+ - cost of materialization process
+ - how many records will be in the materialized temp.table
+ */
+ if (subq_pred->optimize(&rows, &read_time))
+ DBUG_RETURN(TRUE);
+
+ subq_pred->jtbm_read_time= read_time;
+ subq_pred->jtbm_record_count=rows;
+ JOIN *subq_join= subq_pred->unit->first_select()->join;
+
+ if (!subq_join->tables_list || !subq_join->table_count)
+ {
+ if (!join->is_orig_degenerated &&
+ execute_degenerate_jtbm_semi_join(thd, table, subq_pred,
+ eq_list))
+ DBUG_RETURN(TRUE);
+ }
+ else
+ {
+ DBUG_ASSERT(subq_pred->test_set_strategy(SUBS_MATERIALIZATION));
+ subq_pred->is_jtbm_const_tab= FALSE;
+ subselect_hash_sj_engine *hash_sj_engine=
+ ((subselect_hash_sj_engine*)subq_pred->engine);
+
+ table->table= hash_sj_engine->tmp_table;
+ table->table->pos_in_table_list= table;
+
+ setup_table_map(table->table, table, table->jtbm_table_no);
+
+ List_iterator<Item> li(*hash_sj_engine->semi_join_conds->argument_list());
+ Item *item;
+ while ((item=li++))
+ {
+ item->update_used_tables();
+ if (eq_list.push_back(item, thd->mem_root))
+ DBUG_RETURN(TRUE);
+ }
+ }
+ table->table->maybe_null= MY_TEST(join->mixed_implicit_grouping);
+ }
+ if ((nested_join= table->nested_join))
+ {
+ if (setup_jtbm_semi_joins(join, &nested_join->join_list, eq_list))
+ DBUG_RETURN(TRUE);
+ }
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+/*
+ Cleanup non-merged semi-joins (JBMs) that have empty.
+
+ This function is to cleanups for a special case:
+ Consider a query like
+
+ select * from t1 where 1=2 AND t1.col IN (select max(..) ... having 1=2)
+
+ For this query, optimization of subquery will short-circuit, and
+ setup_jtbm_semi_joins() will call create_dummy_tmp_table() so that we have
+ empty, constant temp.table to stand in as materialized temp. table.
+
+ Now, suppose that the upper join is also found to be degenerate. In that
+ case, no JOIN_TAB array will be produced, and hence, JOIN::cleanup() will
+ have a problem with cleaning up empty JTBMs (non-empty ones are cleaned up
+ through Item::cleanup() calls).
+*/
+
+void cleanup_empty_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list)
+{
+ List_iterator<TABLE_LIST> li(*join_list);
+ TABLE_LIST *table;
+ while ((table= li++))
+ {
+ if ((table->jtbm_subselect && table->jtbm_subselect->is_jtbm_const_tab))
+ {
+ if (table->table)
+ {
+ free_tmp_table(join->thd, table->table);
+ table->table= NULL;
+ }
+ }
+ else if (table->nested_join && table->sj_subq_pred)
+ {
+ cleanup_empty_jtbm_semi_joins(join, &table->nested_join->join_list);
+ }
+ }
+}
+
+
+/**
+ Choose an optimal strategy to execute an IN/ALL/ANY subquery predicate
+ based on cost.
+
+ @param join_tables the set of tables joined in the subquery
+
+ @notes
+ The method chooses between the materialization and IN=>EXISTS rewrite
+ strategies for the execution of a non-flattened subquery IN predicate.
+ The cost-based decision is made as follows:
+
+ 1. compute materialize_strategy_cost based on the unmodified subquery
+ 2. reoptimize the subquery taking into account the IN-EXISTS predicates
+ 3. compute in_exists_strategy_cost based on the reoptimized plan
+ 4. compare and set the cheaper strategy
+ if (materialize_strategy_cost >= in_exists_strategy_cost)
+ in_strategy = MATERIALIZATION
+ else
+ in_strategy = IN_TO_EXISTS
+ 5. if in_strategy = MATERIALIZATION and it is not possible to initialize it
+ revert to IN_TO_EXISTS
+ 6. if (in_strategy == MATERIALIZATION)
+ revert the subquery plan to the original one before reoptimizing
+ else
+ inject the IN=>EXISTS predicates into the new EXISTS subquery plan
+
+ The implementation itself is a bit more complicated because it takes into
+ account two more factors:
+ - whether the user allowed both strategies through an optimizer_switch, and
+ - if materialization was the cheaper strategy, whether it can be executed
+ or not.
+
+ @retval FALSE success.
+ @retval TRUE error occurred.
+*/
+
+bool JOIN::choose_subquery_plan(table_map join_tables)
+{
+ enum_reopt_result reopt_result= REOPT_NONE;
+ Item_in_subselect *in_subs;
+
+ /*
+ IN/ALL/ANY optimizations are not applicable for so called fake select
+ (this select exists only to filter results of union if it is needed).
+ */
+ if (select_lex == select_lex->master_unit()->fake_select_lex)
+ return 0;
+
+ if (is_in_subquery())
+ {
+ in_subs= unit->item->get_IN_subquery();
+ if (in_subs->create_in_to_exists_cond(this))
+ return true;
+ }
+ else
+ return false;
+
+ /* A strategy must be chosen earlier. */
+ DBUG_ASSERT(in_subs->has_strategy());
+ DBUG_ASSERT(in_to_exists_where || in_to_exists_having);
+ DBUG_ASSERT(!in_to_exists_where || in_to_exists_where->is_fixed());
+ DBUG_ASSERT(!in_to_exists_having || in_to_exists_having->is_fixed());
+
+ /* The original QEP of the subquery. */
+ Join_plan_state save_qep(table_count);
+
+ /*
+ Compute and compare the costs of materialization and in-exists if both
+ strategies are possible and allowed by the user (checked during the prepare
+ phase.
+ */
+ if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
+ in_subs->test_strategy(SUBS_IN_TO_EXISTS))
+ {
+ JOIN *outer_join;
+ JOIN *inner_join= this;
+ /* Number of unique value combinations filtered by the IN predicate. */
+ double outer_lookup_keys;
+ /* Cost and row count of the unmodified subquery. */
+ double inner_read_time_1, inner_record_count_1;
+ /* Cost of the subquery with injected IN-EXISTS predicates. */
+ double inner_read_time_2;
+ /* The cost to compute IN via materialization. */
+ double materialize_strategy_cost;
+ /* The cost of the IN->EXISTS strategy. */
+ double in_exists_strategy_cost;
+ double dummy;
+
+ /*
+ A. Estimate the number of rows of the outer table that will be filtered
+ by the IN predicate.
+ */
+ outer_join= unit->outer_select() ? unit->outer_select()->join : NULL;
+ /*
+ Get the cost of the outer join if:
+ (1) It has at least one table, and
+ (2) It has been already optimized (if there is no join_tab, then the
+ outer join has not been optimized yet).
+ */
+ if (outer_join && outer_join->table_count > 0 && // (1)
+ outer_join->join_tab && // (2)
+ !in_subs->const_item())
+ {
+ /*
+ TODO:
+ Currently outer_lookup_keys is computed as the number of rows in
+ the partial join including the JOIN_TAB where the IN predicate is
+ pushed to. In the general case this is a gross overestimate because
+ due to caching we are interested only in the number of unique keys.
+ The search key may be formed by columns from much fewer than all
+ tables in the partial join. Example:
+ select * from t1, t2 where t1.c1 = t2.key AND t2.c2 IN (select ...);
+ If the join order: t1, t2, the number of unique lookup keys is ~ to
+ the number of unique values t2.c2 in the partial join t1 join t2.
+ */
+ outer_join->get_partial_cost_and_fanout(in_subs->get_join_tab_idx(),
+ table_map(-1),
+ &dummy,
+ &outer_lookup_keys);
+ }
+ else
+ {
+ /*
+ TODO: outer_join can be NULL for DELETE statements.
+ How to compute its cost?
+ */
+ outer_lookup_keys= 1;
+ }
+
+ /*
+ B. Estimate the cost and number of records of the subquery both
+ unmodified, and with injected IN->EXISTS predicates.
+ */
+ inner_read_time_1= inner_join->best_read;
+ inner_record_count_1= inner_join->join_record_count;
+
+ if (in_to_exists_where && const_tables != table_count)
+ {
+ /*
+ Re-optimize and cost the subquery taking into account the IN-EXISTS
+ conditions.
+ */
+ reopt_result= reoptimize(in_to_exists_where, join_tables, &save_qep);
+ if (reopt_result == REOPT_ERROR)
+ return TRUE;
+
+ /* Get the cost of the modified IN-EXISTS plan. */
+ inner_read_time_2= inner_join->best_read;
+
+ }
+ else
+ {
+ /* Reoptimization would not produce any better plan. */
+ inner_read_time_2= inner_read_time_1;
+ }
+
+ /*
+ C. Compute execution costs.
+ */
+ /* C.1 Compute the cost of the materialization strategy. */
+ //uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list);
+ uint rowlen= get_tmp_table_rec_length(ref_ptrs,
+ select_lex->item_list.elements);
+ /* The cost of writing one row into the temporary table. */
+ double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1,
+ rowlen);
+ /* The cost of a lookup into the unique index of the materialized table. */
+ double lookup_cost= get_tmp_table_lookup_cost(thd, inner_record_count_1,
+ rowlen);
+ /*
+ The cost of executing the subquery and storing its result in an indexed
+ temporary table.
+ */
+ double materialization_cost= COST_ADD(inner_read_time_1,
+ COST_MULT(write_cost,
+ inner_record_count_1));
+
+ materialize_strategy_cost= COST_ADD(materialization_cost,
+ COST_MULT(outer_lookup_keys,
+ lookup_cost));
+
+ /* C.2 Compute the cost of the IN=>EXISTS strategy. */
+ in_exists_strategy_cost= COST_MULT(outer_lookup_keys, inner_read_time_2);
+
+ /* C.3 Compare the costs and choose the cheaper strategy. */
+ if (materialize_strategy_cost >= in_exists_strategy_cost)
+ in_subs->set_strategy(SUBS_IN_TO_EXISTS);
+ else
+ in_subs->set_strategy(SUBS_MATERIALIZATION);
+
+ DBUG_PRINT("info",
+ ("mat_strategy_cost: %.2f, mat_cost: %.2f, write_cost: %.2f, lookup_cost: %.2f",
+ materialize_strategy_cost, materialization_cost, write_cost, lookup_cost));
+ DBUG_PRINT("info",
+ ("inx_strategy_cost: %.2f, inner_read_time_2: %.2f",
+ in_exists_strategy_cost, inner_read_time_2));
+ DBUG_PRINT("info",("outer_lookup_keys: %.2f", outer_lookup_keys));
+ }
+
+ /*
+ If (1) materialization is a possible strategy based on semantic analysis
+ during the prepare phase, then if
+ (2) it is more expensive than the IN->EXISTS transformation, and
+ (3) it is not possible to create usable indexes for the materialization
+ strategy,
+ fall back to IN->EXISTS.
+ otherwise
+ use materialization.
+ */
+ if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
+ in_subs->setup_mat_engine())
+ {
+ /*
+ If materialization was the cheaper or the only user-selected strategy,
+ but it is not possible to execute it due to limitations in the
+ implementation, fall back to IN-TO-EXISTS.
+ */
+ in_subs->set_strategy(SUBS_IN_TO_EXISTS);
+ }
+
+ if (in_subs->test_strategy(SUBS_MATERIALIZATION))
+ {
+ /* Restore the original query plan used for materialization. */
+ if (reopt_result == REOPT_NEW_PLAN)
+ restore_query_plan(&save_qep);
+
+ in_subs->unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
+ select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
+
+ /*
+ Reset the "LIMIT 1" set in Item_exists_subselect::fix_length_and_dec.
+ TODO:
+ Currently we set the subquery LIMIT to infinity, and this is correct
+ because we forbid at parse time LIMIT inside IN subqueries (see
+ Item_in_subselect::test_limit). However, once we allow this, here
+ we should set the correct limit if given in the query.
+ */
+ in_subs->unit->global_parameters()->select_limit= NULL;
+ in_subs->unit->set_limit(unit->global_parameters());
+ /*
+ Set the limit of this JOIN object as well, because normally its being
+ set in the beginning of JOIN::optimize, which was already done.
+ */
+ select_limit= in_subs->unit->lim.get_select_limit();
+ }
+ else if (in_subs->test_strategy(SUBS_IN_TO_EXISTS))
+ {
+ if (reopt_result == REOPT_NONE && in_to_exists_where &&
+ const_tables != table_count)
+ {
+ /*
+ The subquery was not reoptimized with the newly injected IN-EXISTS
+ conditions either because the user allowed only the IN-EXISTS strategy,
+ or because materialization was not possible based on semantic analysis.
+ */
+ reopt_result= reoptimize(in_to_exists_where, join_tables, NULL);
+ if (reopt_result == REOPT_ERROR)
+ return TRUE;
+ }
+
+ if (in_subs->inject_in_to_exists_cond(this))
+ return TRUE;
+ /*
+ If the injected predicate is correlated the IN->EXISTS transformation
+ make the subquery dependent.
+ */
+ if ((in_to_exists_where &&
+ in_to_exists_where->used_tables() & OUTER_REF_TABLE_BIT) ||
+ (in_to_exists_having &&
+ in_to_exists_having->used_tables() & OUTER_REF_TABLE_BIT))
+ {
+ in_subs->unit->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
+ select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
+ }
+ select_limit= 1;
+ }
+ else
+ DBUG_ASSERT(FALSE);
+
+ return FALSE;
+}
+
+
+/**
+ Choose a query plan for a table-less subquery.
+
+ @notes
+
+ @retval FALSE success.
+ @retval TRUE error occurred.
+*/
+
+bool JOIN::choose_tableless_subquery_plan()
+{
+ DBUG_ASSERT(!tables_list || !table_count);
+ if (unit->item)
+ {
+ DBUG_ASSERT(unit->item->type() == Item::SUBSELECT_ITEM);
+ Item_subselect *subs_predicate= unit->item;
+
+ /*
+ If the optimizer determined that his query has an empty result,
+ in most cases the subquery predicate is a known constant value -
+ either of TRUE, FALSE or NULL. The implementation of
+ Item_subselect::no_rows_in_result() determines which one.
+ */
+ if (zero_result_cause)
+ {
+ if (!implicit_grouping)
+ {
+ /*
+ Both group by queries and non-group by queries without aggregate
+ functions produce empty subquery result. There is no need to further
+ rewrite the subquery because it will not be executed at all.
+ */
+ exec_const_cond= 0;
+ return FALSE;
+ }
+
+ /* @todo
+ A further optimization is possible when a non-group query with
+ MIN/MAX/COUNT is optimized by opt_sum_query. Then, if there are
+ only MIN/MAX functions over an empty result set, the subquery
+ result is a NULL value/row, thus the value of subs_predicate is
+ NULL.
+ */
+ }
+
+ /*
+ For IN subqueries, use IN->EXISTS transfomation, unless the subquery
+ has been converted to a JTBM semi-join. In that case, just leave
+ everything as-is, setup_jtbm_semi_joins() has special handling for cases
+ like this.
+ */
+ Item_in_subselect *in_subs;
+ in_subs= subs_predicate->get_IN_subquery();
+ if (in_subs &&
+ !(subs_predicate->substype() == Item_subselect::IN_SUBS &&
+ in_subs->is_jtbm_merged))
+ {
+ in_subs->set_strategy(SUBS_IN_TO_EXISTS);
+ if (in_subs->create_in_to_exists_cond(this) ||
+ in_subs->inject_in_to_exists_cond(this))
+ return TRUE;
+ tmp_having= having;
+ }
+ }
+ exec_const_cond= zero_result_cause ? 0 : conds;
+ return FALSE;
+}
+
+
+bool Item::pushable_equality_checker_for_subquery(uchar *arg)
+{
+ return
+ get_corresponding_field_pair(this,
+ ((Item *)arg)->get_IN_subquery()->
+ corresponding_fields);
+}
+
+
+/*
+ Checks if 'item' or some item equal to it is equal to the field from
+ some Field_pair of 'pair_list' and returns matching Field_pair or
+ NULL if the matching Field_pair wasn't found.
+*/
+
+Field_pair *find_matching_field_pair(Item *item, List<Field_pair> pair_list)
+{
+ Field_pair *field_pair= get_corresponding_field_pair(item, pair_list);
+ if (field_pair)
+ return field_pair;
+
+ Item_equal *item_equal= item->get_item_equal();
+ if (item_equal)
+ {
+ Item_equal_fields_iterator it(*item_equal);
+ Item *equal_item;
+ while ((equal_item= it++))
+ {
+ if (equal_item->const_item())
+ continue;
+ field_pair= get_corresponding_field_pair(equal_item, pair_list);
+ if (field_pair)
+ return field_pair;
+ }
+ }
+ return NULL;
+}
+
+
+bool Item_field::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
+{
+ if (find_matching_field_pair(((Item *) this), subq_pred->corresponding_fields))
+ return true;
+ return false;
+}
+
+
+bool Item_direct_view_ref::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
+{
+ if (item_equal)
+ {
+ DBUG_ASSERT(real_item()->type() == Item::FIELD_ITEM);
+ if (get_corresponding_field_pair(((Item *)this), subq_pred->corresponding_fields))
+ return true;
+ }
+ return (*ref)->excl_dep_on_in_subq_left_part(subq_pred);
+}
+
+
+bool Item_equal::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
+{
+ Item *left_item = get_const();
+ Item_equal_fields_iterator it(*this);
+ Item *item;
+ if (!left_item)
+ {
+ while ((item=it++))
+ {
+ if (item->excl_dep_on_in_subq_left_part(subq_pred))
+ {
+ left_item= item;
+ break;
+ }
+ }
+ }
+ if (!left_item)
+ return false;
+ while ((item=it++))
+ {
+ if (item->excl_dep_on_in_subq_left_part(subq_pred))
+ return true;
+ }
+ return false;
+}
+
+
+/**
+ @brief
+ Get corresponding item from the select of the right part of IN subquery
+
+ @param thd the thread handle
+ @param item the item from the left part of subq_pred for which
+ corresponding item should be found
+ @param subq_pred the IN subquery predicate
+
+ @details
+ This method looks through the fields of the select of the right part of
+ the IN subquery predicate subq_pred trying to find the corresponding
+ item 'new_item' for item. If item has equal items it looks through
+ the fields of the select of the right part of subq_pred for each equal
+ item trying to find the corresponding item.
+ The method assumes that the given item is either a field item or
+ a reference to a field item.
+
+ @retval <item*> reference to the corresponding item
+ @retval NULL if item was not found
+*/
+
+static
+Item *get_corresponding_item(THD *thd, Item *item,
+ Item_in_subselect *subq_pred)
+{
+ DBUG_ASSERT(item->type() == Item::FIELD_ITEM ||
+ (item->type() == Item::REF_ITEM &&
+ ((Item_ref *) item)->ref_type() == Item_ref::VIEW_REF));
+
+ Field_pair *field_pair;
+ Item_equal *item_equal= item->get_item_equal();
+
+ if (item_equal)
+ {
+ Item_equal_fields_iterator it(*item_equal);
+ Item *equal_item;
+ while ((equal_item= it++))
+ {
+ field_pair=
+ get_corresponding_field_pair(equal_item, subq_pred->corresponding_fields);
+ if (field_pair)
+ return field_pair->corresponding_item;
+ }
+ }
+ else
+ {
+ field_pair=
+ get_corresponding_field_pair(item, subq_pred->corresponding_fields);
+ if (field_pair)
+ return field_pair->corresponding_item;
+ }
+ return NULL;
+}
+
+
+Item *Item_field::in_subq_field_transformer_for_where(THD *thd, uchar *arg)
+{
+ Item_in_subselect *subq_pred= ((Item *)arg)->get_IN_subquery();
+ Item *producing_item= get_corresponding_item(thd, this, subq_pred);
+ if (producing_item)
+ return producing_item->build_clone(thd);
+ return this;
+}
+
+
+Item *Item_direct_view_ref::in_subq_field_transformer_for_where(THD *thd,
+ uchar *arg)
+{
+ if (item_equal)
+ {
+ Item_in_subselect *subq_pred= ((Item *)arg)->get_IN_subquery();
+ Item *producing_item= get_corresponding_item(thd, this, subq_pred);
+ DBUG_ASSERT (producing_item != NULL);
+ return producing_item->build_clone(thd);
+ }
+ return this;
+}
+
+
+/**
+ @brief
+ Transforms item so it can be pushed into the IN subquery HAVING clause
+
+ @param thd the thread handle
+ @param in_item the item for which pushable item should be created
+ @param subq_pred the IN subquery predicate
+
+ @details
+ This method finds for in_item that is a field from the left part of the
+ IN subquery predicate subq_pred its corresponding item from the right part
+ of subq_pred.
+ If corresponding item is found, a shell for this item is created.
+ This shell can be pushed into the HAVING part of subq_pred select.
+
+ @retval <item*> reference to the created corresponding item shell for in_item
+ @retval NULL if mistake occurs
+*/
+
+static Item*
+get_corresponding_item_for_in_subq_having(THD *thd, Item *in_item,
+ Item_in_subselect *subq_pred)
+{
+ Item *new_item= get_corresponding_item(thd, in_item, subq_pred);
+
+ if (new_item)
+ {
+ Item_ref *ref=
+ new (thd->mem_root) Item_ref(thd,
+ &subq_pred->unit->first_select()->context,
+ new_item->name);
+ if (!ref)
+ DBUG_ASSERT(0);
+ return ref;
+ }
+ return new_item;
+}
+
+
+Item *Item_field::in_subq_field_transformer_for_having(THD *thd, uchar *arg)
+{
+ DBUG_ASSERT(((Item *)arg)->get_IN_subquery());
+ return get_corresponding_item_for_in_subq_having(thd, this,
+ (Item_in_subselect *)arg);
+}
+
+
+Item *Item_direct_view_ref::in_subq_field_transformer_for_having(THD *thd,
+ uchar *arg)
+{
+ if (!item_equal)
+ return this;
+ else
+ {
+ DBUG_ASSERT(((Item *)arg)->get_IN_subquery());
+ Item *new_item= get_corresponding_item_for_in_subq_having(thd, this,
+ (Item_in_subselect *)arg);
+ if (!new_item)
+ return this;
+ return new_item;
+ }
+}
+
+
+/**
+ @brief
+ Find fields that are used in the GROUP BY of the select
+
+ @param thd the thread handle
+ @param sel the select of the IN subquery predicate
+ @param fields fields of the left part of the IN subquery predicate
+ @param grouping_list GROUP BY clause
+
+ @details
+ This method traverses fields which are used in the GROUP BY of
+ sel and saves them with their corresponding items from fields.
+*/
+
+bool grouping_fields_in_the_in_subq_left_part(THD *thd,
+ st_select_lex *sel,
+ List<Field_pair> *fields,
+ ORDER *grouping_list)
+{
+ DBUG_ENTER("grouping_fields_in_the_in_subq_left_part");
+ sel->grouping_tmp_fields.empty();
+ List_iterator<Field_pair> it(*fields);
+ Field_pair *item;
+ while ((item= it++))
+ {
+ for (ORDER *ord= grouping_list; ord; ord= ord->next)
+ {
+ if ((*ord->item)->eq(item->corresponding_item, 0))
+ {
+ if (sel->grouping_tmp_fields.push_back(item, thd->mem_root))
+ DBUG_RETURN(TRUE);
+ }
+ }
+ }
+ DBUG_RETURN(FALSE);
+}
+
+
+/**
+ @brief
+ Extract condition that can be pushed into select of this IN subquery
+
+ @param thd the thread handle
+ @param cond current condition
+
+ @details
+ This function builds the most restrictive condition depending only on
+ the list of fields of the left part of this IN subquery predicate
+ (directly or indirectly through equality) that can be extracted from the
+ given condition cond and pushes it into this IN subquery.
+
+ Example of the transformation:
+
+ SELECT * FROM t1
+ WHERE a>3 AND b>10 AND
+ (a,b) IN (SELECT x,MAX(y) FROM t2 GROUP BY x);
+
+ =>
+
+ SELECT * FROM t1
+ WHERE a>3 AND b>10 AND
+ (a,b) IN (SELECT x,max(y)
+ FROM t2
+ WHERE x>3
+ GROUP BY x
+ HAVING MAX(y)>10);
+
+
+ In details:
+ 1. Check what pushable formula can be extracted from cond
+ 2. Build a clone PC of the formula that can be extracted
+ (the clone is built only if the extracted formula is a AND subformula
+ of cond or conjunction of such subformulas)
+ 3. If there is no HAVING clause prepare PC to be conjuncted with
+ WHERE clause of this subquery. Otherwise do 4-7.
+ 4. Check what formula PC_where can be extracted from PC to be pushed
+ into the WHERE clause of the subquery
+ 5. Build PC_where and if PC_where is a conjunct(s) of PC remove it from PC
+ getting PC_having
+ 6. Prepare PC_where to be conjuncted with the WHERE clause of
+ the IN subquery
+ 7. Prepare PC_having to be conjuncted with the HAVING clause of
+ the IN subquery
+
+ @note
+ This method is similar to pushdown_cond_for_derived()
+
+ @retval TRUE if an error occurs
+ @retval FALSE otherwise
+*/
+
+bool Item_in_subselect::pushdown_cond_for_in_subquery(THD *thd, Item *cond)
+{
+ DBUG_ENTER("Item_in_subselect::pushdown_cond_for_in_subquery");
+ Item *remaining_cond= NULL;
+
+ if (!cond)
+ DBUG_RETURN(FALSE);
+
+ st_select_lex *sel = unit->first_select();
+
+ if (is_jtbm_const_tab)
+ DBUG_RETURN(FALSE);
+
+ if (!sel->cond_pushdown_is_allowed())
+ DBUG_RETURN(FALSE);
+
+ /*
+ Create a list of Field_pair items for this IN subquery.
+ It consists of the pairs of fields from the left part of this IN subquery
+ predicate 'left_part' and the respective fields from the select of the
+ right part of the IN subquery 'sel' (the field from left_part with the
+ corresponding field from the sel projection list).
+ Attach this list to the IN subquery.
+ */
+ corresponding_fields.empty();
+ List_iterator_fast<Item> it(sel->join->fields_list);
+ Item *item;
+ for (uint i= 0; i < left_expr->cols(); i++)
+ {
+ item= it++;
+ Item *elem= left_expr->element_index(i);
+
+ if (elem->real_item()->type() != Item::FIELD_ITEM)
+ continue;
+
+ if (corresponding_fields.push_back(
+ new Field_pair(((Item_field *)(elem->real_item()))->field,
+ item)))
+ DBUG_RETURN(TRUE);
+ }
+
+ /* 1. Check what pushable formula can be extracted from cond */
+ Item *extracted_cond;
+ cond->check_pushable_cond(&Item::pushable_cond_checker_for_subquery,
+ (uchar *)this);
+ /* 2. Build a clone PC of the formula that can be extracted */
+ extracted_cond=
+ cond->build_pushable_cond(thd,
+ &Item::pushable_equality_checker_for_subquery,
+ (uchar *)this);
+ /* Nothing to push */
+ if (!extracted_cond)
+ {
+ DBUG_RETURN(FALSE);
+ }
+
+ /* Collect fields that are used in the GROUP BY of sel */
+ st_select_lex *save_curr_select= thd->lex->current_select;
+ if (sel->have_window_funcs())
+ {
+ if (sel->group_list.first || sel->join->implicit_grouping)
+ goto exit;
+ ORDER *common_partition_fields=
+ sel->find_common_window_func_partition_fields(thd);
+ if (!common_partition_fields)
+ goto exit;
+
+ if (grouping_fields_in_the_in_subq_left_part(thd, sel, &corresponding_fields,
+ common_partition_fields))
+ DBUG_RETURN(TRUE);
+ }
+ else if (grouping_fields_in_the_in_subq_left_part(thd, sel,
+ &corresponding_fields,
+ sel->group_list.first))
+ DBUG_RETURN(TRUE);
+
+ /* Do 4-6 */
+ sel->pushdown_cond_into_where_clause(thd, extracted_cond,
+ &remaining_cond,
+ &Item::in_subq_field_transformer_for_where,
+ (uchar *) this);
+ if (!remaining_cond)
+ goto exit;
+ /*
+ 7. Prepare PC_having to be conjuncted with the HAVING clause of
+ the IN subquery
+ */
+ remaining_cond=
+ remaining_cond->transform(thd,
+ &Item::in_subq_field_transformer_for_having,
+ (uchar *)this);
+ if (!remaining_cond ||
+ remaining_cond->walk(&Item::cleanup_excluding_const_fields_processor,
+ 0, 0))
+ goto exit;
+
+ mark_or_conds_to_avoid_pushdown(remaining_cond);
+
+ sel->cond_pushed_into_having= remaining_cond;
+
+exit:
+ thd->lex->current_select= save_curr_select;
+ DBUG_RETURN(FALSE);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-30 16:02:28 +0000