1 /*
2 Copyright (c) 2010, 2020, MariaDB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335 USA */
16
17 /**
18 @file
19
20 @brief
21 Semi-join subquery optimizations code
22
23 */
24
25 #ifdef USE_PRAGMA_IMPLEMENTATION
26 #pragma implementation // gcc: Class implementation
27 #endif
28
29 #include "mariadb.h"
30 #include "sql_base.h"
31 #include "sql_const.h"
32 #include "sql_select.h"
33 #include "filesort.h"
34 #include "opt_subselect.h"
35 #include "sql_test.h"
36 #include <my_bit.h>
37
38 /*
39 This file contains optimizations for semi-join subqueries.
40
41 Contents
42 --------
43 1. What is a semi-join subquery
44 2. General idea about semi-join execution
45 2.1 Correlated vs uncorrelated semi-joins
46 2.2 Mergeable vs non-mergeable semi-joins
47 3. Code-level view of semi-join processing
48 3.1 Conversion
49 3.1.1 Merged semi-join TABLE_LIST object
50 3.1.2 Non-merged semi-join data structure
51 3.2 Semi-joins and query optimization
52 3.2.1 Non-merged semi-joins and join optimization
53 3.2.2 Merged semi-joins and join optimization
54 3.3 Semi-joins and query execution
55
56 1. What is a semi-join subquery
57 -------------------------------
58 We use this definition of semi-join:
59
60 outer_tbl SEMI JOIN inner_tbl ON cond = {set of outer_tbl.row such that
61 exist inner_tbl.row, for which
62 cond(outer_tbl.row,inner_tbl.row)
63 is satisfied}
64
65 That is, semi-join operation is similar to inner join operation, with
66 exception that we don't care how many matches a row from outer_tbl has in
67 inner_tbl.
68
69 In SQL terms: a semi-join subquery is an IN subquery that is an AND-part of
70 the WHERE/ON clause.
71
72 2. General idea about semi-join execution
73 -----------------------------------------
74 We can execute semi-join in a way similar to inner join, with exception that
75 we need to somehow ensure that we do not generate record combinations that
76 differ only in rows of inner tables.
77 There is a number of different ways to achieve this property, implemented by
78 a number of semi-join execution strategies.
79 Some strategies can handle any semi-joins, other can be applied only to
80 semi-joins that have certain properties that are described below:
81
82 2.1 Correlated vs uncorrelated semi-joins
83 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
84 Uncorrelated semi-joins are special in the respect that they allow to
85 - execute the subquery (possible as it's uncorrelated)
86 - somehow make sure that generated set does not have duplicates
87 - perform an inner join with outer tables.
88
89 or, rephrasing in SQL form:
90
91 SELECT ... FROM ot WHERE ot.col IN (SELECT it.col FROM it WHERE uncorr_cond)
92 ->
93 SELECT ... FROM ot JOIN (SELECT DISTINCT it.col FROM it WHERE uncorr_cond)
94
95 2.2 Mergeable vs non-mergeable semi-joins
96 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
97 Semi-join operation has some degree of commutability with inner join
98 operation: we can join subquery's tables with ouside table(s) and eliminate
99 duplicate record combination after that:
100
101 ot1 JOIN ot2 SEMI_JOIN{it1,it2} (it1 JOIN it2) ON sjcond(ot2,it*) ->
102 |
103 +-------------------------------+
104 v
105 ot1 SEMI_JOIN{it1,it2} (it1 JOIN it2 JOIN ot2) ON sjcond(ot2,it*)
106
107 In order for this to work, subquery's top-level operation must be join, and
108 grouping or ordering with limit (grouping or ordering with limit are not
109 commutative with duplicate removal). In other words, the conversion is
110 possible when the subquery doesn't have GROUP BY clause, any aggregate
111 functions*, or ORDER BY ... LIMIT clause.
112
113 Definitions:
114 - Subquery whose top-level operation is a join is called *mergeable semi-join*
115 - All other kinds of semi-join subqueries are considered non-mergeable.
116
117 *- this requirement is actually too strong, but its exceptions are too
118 complicated to be considered here.
119
120 3. Code-level view of semi-join processing
121 ------------------------------------------
122
123 3.1 Conversion and pre-optimization data structures
124 ---------------------------------------------------
125 * When doing JOIN::prepare for the subquery, we detect that it can be
126 converted into a semi-join and register it in parent_join->sj_subselects
127
128 * At the start of parent_join->optimize(), the predicate is converted into
129 a semi-join node. A semi-join node is a TABLE_LIST object that is linked
130 somewhere in parent_join->join_list (either it is just present there, or
131 it is a descendant of some of its members).
132
133 There are two kinds of semi-joins:
134 - Merged semi-joins
135 - Non-merged semi-joins
136
137 3.1.1 Merged semi-join TABLE_LIST object
138 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
139 Merged semi-join object is a TABLE_LIST that contains a sub-join of
140 subquery tables and the semi-join ON expression (in this respect it is
141 very similar to nested outer join representation)
142 Merged semi-join represents this SQL:
143
144 ... SEMI JOIN (inner_tbl1 JOIN ... JOIN inner_tbl_n) ON sj_on_expr
145
146 Semi-join objects of this kind have TABLE_LIST::sj_subq_pred set.
147
148 3.1.2 Non-merged semi-join data structure
149 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
150 Non-merged semi-join object is a leaf TABLE_LIST object that has a subquery
151 that produces rows. It is similar to a base table and represents this SQL:
152
153 ... SEMI_JOIN (SELECT non_mergeable_select) ON sj_on_expr
154
155 Subquery items that were converted into semi-joins are removed from the WHERE
156 clause. (They do remain in PS-saved WHERE clause, and they replace themselves
157 with Item_int(1) on subsequent re-executions).
158
159 3.2 Semi-joins and join optimization
160 ------------------------------------
161
162 3.2.1 Non-merged semi-joins and join optimization
163 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
164 For join optimization purposes, non-merged semi-join nests are similar to
165 base tables. Each such nest is represented by one one JOIN_TAB, which has
166 two possible access strategies:
167 - full table scan (representing SJ-Materialization-Scan strategy)
168 - eq_ref-like table lookup (representing SJ-Materialization-Lookup)
169
170 Unlike regular base tables, non-merged semi-joins have:
171 - non-zero JOIN_TAB::startup_cost, and
172 - join_tab->table->is_filled_at_execution()==TRUE, which means one
173 cannot do const table detection, range analysis or other dataset-dependent
174 optimizations.
175 Instead, get_delayed_table_estimates() will run optimization for the
176 subquery and produce an E(materialized table size).
177
178 3.2.2 Merged semi-joins and join optimization
179 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
180 - optimize_semijoin_nests() does pre-optimization
181 - during join optimization, the join has one JOIN_TAB (or is it POSITION?)
182 array, and suffix-based detection is used, see advance_sj_state()
183 - after join optimization is done, get_best_combination() switches
184 the data-structure to prefix-based, multiple JOIN_TAB ranges format.
185
186 3.3 Semi-joins and query execution
187 ----------------------------------
188 * Join executor has hooks for all semi-join strategies.
189 TODO elaborate.
190
191 */
192
193 /*
194 EqualityPropagationAndSjmNests
195 ******************************
196
197 Equalities are used for:
198 P1. Equality propagation
199 P2. Equality substitution [for a certain join order]
200
201 The equality propagation is not affected by SJM nests. In fact, it is done
202 before we determine the execution plan, i.e. before we even know we will use
203 SJM-nests for execution.
204
205 The equality substitution is affected.
206
207 Substitution without SJMs
208 =========================
209 When one doesn't have SJM nests, tables have a strict join order:
210
211 --------------------------------->
212 t1 -- t2 -- t3 -- t4 --- t5
213
214
215 ? ^
216 \
217 --(part-of-WHERE)
218
219
220 parts WHERE/ON and ref. expressions are attached at some point along the axis.
221 Expression is allowed to refer to a table column if the table is to the left of
222 the attachment point. For any given expression, we have a goal:
223
224 "Move leftmost allowed attachment point as much as possible to the left"
225
226 Substitution with SJMs - task setting
227 =====================================
228
229 When SJM nests are present, there is no global strict table ordering anymore:
230
231
232 --------------------------------->
233
234 ot1 -- ot2 --- sjm -- ot4 --- ot5
235 |
236 | Main execution
237 - - - - - - - - - - - - - - - - - - - - - - - -
238 | Materialization
239 it1 -- it2 --/
240
241
242 Besides that, we must take into account that
243 - values for outer table columns, otN.col, are inaccessible at
244 materialization step (SJM-RULE)
245 - values for inner table columns, itN.col, are inaccessible at Main execution
246 step, except for SJ-Materialization-Scan and columns that are in the
247 subquery's select list. (SJM-RULE)
248
249 Substitution with SJMs - solution
250 =================================
251
252 First, we introduce global strict table ordering like this:
253
254 ot1 - ot2 --\ /--- ot3 -- ot5
255 \--- it1 --- it2 --/
256
257 Now, let's see how to meet (SJM-RULE).
258
259 SJ-Materialization is only applicable for uncorrelated subqueries. From this, it
260 follows that any multiple equality will either
261 1. include only columns of outer tables, or
262 2. include only columns of inner tables, or
263 3. include columns of inner and outer tables, joined together through one
264 of IN-equalities.
265
266 Cases #1 and #2 can be handled in the same way as with regular inner joins.
267
268 Case #3 requires special handling, so that we don't construct violations of
269 (SJM-RULE). Let's consider possible ways to build violations.
270
271 Equality propagation starts with the clause in this form
272
273 top_query_where AND subquery_where AND in_equalities
274
275 First, it builds multi-equalities. It can also build a mixed multi-equality
276
277 multiple-equal(ot1.col, ot2.col, ... it1.col, itN.col)
278
279 Multi-equalities are pushed down the OR-clauses in top_query_where and in
280 subquery_where, so it's possible that clauses like this one are built:
281
282 subquery_cond OR (multiple-equal(it1.col, ot1.col,...) AND ...)
283 ^^^^^^^^^^^^^ \
284 | this must be evaluated
285 \- can only be evaluated at the main phase.
286 at the materialization phase
287
288 Finally, equality substitution is started. It does two operations:
289
290
291 1. Field reference substitution
292 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
293
294 (In the code, this is Item_field::replace_equal_field)
295
296 This is a process of replacing each reference to "tblX.col"
297 with the first element of the multi-equality. (REF-SUBST-ORIG)
298
299 This behaviour can cause problems with Semi-join nests. Suppose, we have a
300 condition:
301
302 func(it1.col, it2.col)
303
304 and a multi-equality(ot1.col, it1.col). Then, reference to "it1.col" will be
305 replaced with "ot1.col", constructing a condition
306
307 func(ot1.col, it2.col)
308
309 which will be a violation of (SJM-RULE).
310
311 In order to avoid this, (REF-SUBST-ORIG) is amended as follows:
312
313 - references to tables "itX.col" that are inner wrt some SJM nest, are
314 replaced with references to the first inner table from the same SJM nest.
315
316 - references to top-level tables "otX.col" are replaced with references to
317 the first element of the multi-equality, no matter if that first element is
318 a column of a top-level table or of table from some SJM nest.
319 (REF-SUBST-SJM)
320
321 The case where the first element is a table from an SJM nest $SJM is ok,
322 because it can be proven that $SJM uses SJ-Materialization-Scan, and
323 "unpacks" correct column values to the first element during the main
324 execution phase.
325
326 2. Item_equal elimination
327 ~~~~~~~~~~~~~~~~~~~~~~~~~
328 (In the code: eliminate_item_equal) This is a process of taking
329
330 multiple-equal(a,b,c,d,e)
331
332 and replacing it with an equivalent expression which is an AND of pair-wise
333 equalities:
334
335 a=b AND a=c AND ...
336
337 The equalities are picked such that for any given join prefix (t1,t2...) the
338 subset of equalities that can be evaluated gives the most restrictive
339 filtering.
340
341 Without SJM nests, it is sufficient to compare every multi-equality member
342 with the first one:
343
344 elem1=elem2 AND elem1=elem3 AND elem1=elem4 ...
345
346 When SJM nests are present, we should take care not to construct equalities
347 that violate the (SJM-RULE). This is achieved by generating separate sets of
348 equalites for top-level tables and for inner tables. That is, for the join
349 order
350
351 ot1 - ot2 --\ /--- ot3 -- ot5
352 \--- it1 --- it2 --/
353
354 we will generate
355 ot1.col=ot2.col
356 ot1.col=ot3.col
357 ot1.col=ot5.col
358 it2.col=it1.col
359
360
361 2.1 The problem with Item_equals and ORs
362 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
363 As has been mentioned above, multiple equalities are pushed down into OR
364 clauses, possibly building clauses like this:
365
366 func(it.col2) OR multiple-equal(it1.col1, it1.col2, ot1.col) (1)
367
368 where the first part of the clause has references to inner tables, while the
369 second has references to the top-level tables, which is a violation of
370 (SJM-RULE).
371
372 AND-clauses of this kind do not create problems, because make_cond_for_table()
373 will take them apart. OR-clauses will not be split. It is possible to
374 split-out the part that's dependent on the inner table:
375
376 func(it.col2) OR it1.col1=it1.col2
377
378 but this is a less-restrictive condition than condition (1). Current execution
379 scheme will still try to generate the "remainder" condition:
380
381 func(it.col2) OR it1.col1=ot1.col
382
383 which is a violation of (SJM-RULE).
384
385 QQ: "ot1.col=it1.col" is checked at the upper level. Why was it not removed
386 here?
387 AA: because has a proper subset of conditions that are found on this level.
388 consider a join order of ot, sjm(it)
389 and a condition
390 ot.col=it.col AND ( ot.col=it.col='foo' OR it.col2='bar')
391
392 we will produce:
393 table ot: nothing
394 table it: ot.col=it.col AND (ot.col='foo' OR it.col2='bar')
395 ^^^^ ^^^^^^^^^^^^^^^^
396 | \ the problem is that
397 | this part condition didnt
398 | receive a substitution
399 |
400 +--- it was correct to subst, 'ot' is
401 the left-most.
402
403
404 Does it make sense to push "inner=outer" down into ORs?
405 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
406
407 Yes. Consider the query:
408
409 select * from ot
410 where ot.col in (select it.col from it where (it.col='foo' OR it.col='bar'))
411
412 here, it may be useful to infer that
413
414 (ot.col='foo' OR ot.col='bar') (CASE-FOR-SUBST)
415
416 and attach that condition to the table 'ot'.
417
418 Possible solutions for Item_equals and ORs
419 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
420
421 Solution #1
422 ~~~~~~~~~~~
423 Let make_cond_for_table() chop analyze the OR clauses it has produced and
424 discard them if they violate (SJM-RULE). This solution would allow to handle
425 cases like (CASE-FOR-SUBST) at the expense of making semantics of
426 make_cond_for_table() complicated.
427
428 Solution #2
429 ~~~~~~~~~~~
430 Before the equality propagation phase, none of the OR clauses violate the
431 (SJM-RULE). This way, if we remember which tables the original equality
432 referred to, we can only generate equalities that refer to the outer (or inner)
433 tables. Note that this will disallow handling of cases like (CASE-FOR-SUBST).
434
435 Currently, solution #2 is implemented.
436 */
437
438 LEX_CSTRING weedout_key= {STRING_WITH_LEN("weedout_key")};
439
440 static
441 bool subquery_types_allow_materialization(Item_in_subselect *in_subs);
442 static bool replace_where_subcondition(JOIN *, Item **, Item *, Item *, bool);
443 static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
444 void *arg);
445 static void reset_equality_number_for_subq_conds(Item * cond);
446 static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred);
447 static bool convert_subq_to_jtbm(JOIN *parent_join,
448 Item_in_subselect *subq_pred, bool *remove);
449 static TABLE_LIST *alloc_join_nest(THD *thd);
450 static uint get_tmp_table_rec_length(Ref_ptr_array p_list, uint elements);
451 bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables);
452 static SJ_MATERIALIZATION_INFO *
453 at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
454 uint idx, bool *loose_scan);
455 static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
456 Item_in_subselect *subq_pred);
457 static bool remove_sj_conds(THD *thd, Item **tree);
458 static bool is_cond_sj_in_equality(Item *item);
459 static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab);
460 static Item *remove_additional_cond(Item* conds);
461 static void remove_subq_pushed_predicates(JOIN *join, Item **where);
462
463 enum_nested_loop_state
464 end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
465
466
467 /*
468 Check if Materialization strategy is allowed for given subquery predicate.
469
470 @param thd Thread handle
471 @param in_subs The subquery predicate
472 @param child_select The select inside predicate (the function will
473 check it is the only one)
474
475 @return TRUE - Materialization is applicable
476 FALSE - Otherwise
477 */
478
is_materialization_applicable(THD * thd,Item_in_subselect * in_subs,st_select_lex * child_select)479 bool is_materialization_applicable(THD *thd, Item_in_subselect *in_subs,
480 st_select_lex *child_select)
481 {
482 st_select_lex_unit* parent_unit= child_select->master_unit();
483 /*
484 Check if the subquery predicate can be executed via materialization.
485 The required conditions are:
486 0. The materialization optimizer switch was set.
487 1. Subquery is a single SELECT (not a UNION).
488 TODO: this is a limitation that can be fixed
489 2. Subquery is not a table-less query. In this case there is no
490 point in materializing.
491 2A The upper query is not a table-less SELECT ... FROM DUAL. We
492 can't do materialization for SELECT .. FROM DUAL because it
493 does not call setup_subquery_materialization(). We could make
494 SELECT ... FROM DUAL call that function but that doesn't seem
495 to be the case that is worth handling.
496 3. Either the subquery predicate is a top-level predicate, or at
497 least one partial match strategy is enabled. If no partial match
498 strategy is enabled, then materialization cannot be used for
499 non-top-level queries because it cannot handle NULLs correctly.
500 4. Subquery is non-correlated
501 TODO:
502 This condition is too restrictive (limitation). It can be extended to:
503 (Subquery is non-correlated ||
504 Subquery is correlated to any query outer to IN predicate ||
505 (Subquery is correlated to the immediate outer query &&
506 Subquery !contains {GROUP BY, ORDER BY [LIMIT],
507 aggregate functions}) && subquery predicate is not under "NOT IN"))
508 5. Subquery does not contain recursive references
509
510 A note about prepared statements: we want the if-branch to be taken on
511 PREPARE and each EXECUTE. The rewrites are only done once, but we need
512 select_lex->sj_subselects list to be populated for every EXECUTE.
513
514 */
515 if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION) && // 0
516 !child_select->is_part_of_union() && // 1
517 parent_unit->first_select()->leaf_tables.elements && // 2
518 child_select->outer_select()->table_list.first && // 2A
519 subquery_types_allow_materialization(in_subs) &&
520 (in_subs->is_top_level_item() || //3
521 optimizer_flag(thd,
522 OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) || //3
523 optimizer_flag(thd,
524 OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)) && //3
525 !in_subs->is_correlated && //4
526 !in_subs->with_recursive_reference) //5
527 {
528 return TRUE;
529 }
530 return FALSE;
531 }
532
533
534 /*
535 Check if we need JOIN::prepare()-phase subquery rewrites and if yes, do them
536
537 SYNOPSIS
538 check_and_do_in_subquery_rewrites()
539 join Subquery's join
540
541 DESCRIPTION
542 Check if we need to do
543 - subquery -> mergeable semi-join rewrite
544 - if the subquery can be handled with materialization
545 - 'substitution' rewrite for table-less subqueries like "(select 1)"
546 - IN->EXISTS rewrite
547 and, depending on the rewrite, either do it, or record it to be done at a
548 later phase.
549
550 RETURN
551 0 - OK
552 Other - Some sort of query error
553 */
554
check_and_do_in_subquery_rewrites(JOIN * join)555 int check_and_do_in_subquery_rewrites(JOIN *join)
556 {
557 THD *thd=join->thd;
558 st_select_lex *select_lex= join->select_lex;
559 st_select_lex_unit* parent_unit= select_lex->master_unit();
560 DBUG_ENTER("check_and_do_in_subquery_rewrites");
561
562 /*
563 IN/ALL/ANY rewrites are not applicable for so called fake select
564 (this select exists only to filter results of union if it is needed).
565 */
566 if (select_lex == select_lex->master_unit()->fake_select_lex)
567 DBUG_RETURN(0);
568
569 /*
570 If
571 1) this join is inside a subquery (of any type except FROM-clause
572 subquery) and
573 2) we aren't just normalizing a VIEW
574
575 Then perform early unconditional subquery transformations:
576 - Convert subquery predicate into semi-join, or
577 - Mark the subquery for execution using materialization, or
578 - Perform IN->EXISTS transformation, or
579 - Perform more/less ALL/ANY -> MIN/MAX rewrite
580 - Substitute trivial scalar-context subquery with its value
581
582 TODO: for PS, make the whole block execute only on the first execution
583 */
584 Item_subselect *subselect;
585 if (!thd->lex->is_view_context_analysis() && // (1)
586 (subselect= parent_unit->item)) // (2)
587 {
588 Item_in_subselect *in_subs= NULL;
589 Item_allany_subselect *allany_subs= NULL;
590 switch (subselect->substype()) {
591 case Item_subselect::IN_SUBS:
592 in_subs= (Item_in_subselect *)subselect;
593 break;
594 case Item_subselect::ALL_SUBS:
595 case Item_subselect::ANY_SUBS:
596 allany_subs= (Item_allany_subselect *)subselect;
597 break;
598 default:
599 break;
600 }
601
602
603 /* Resolve expressions and perform semantic analysis for IN query */
604 if (in_subs != NULL)
605 /*
606 TODO: Add the condition below to this if statement when we have proper
607 support for is_correlated handling for materialized semijoins.
608 If we were to add this condition now, the fix_fields() call in
609 convert_subq_to_sj() would force the flag is_correlated to be set
610 erroneously for prepared queries.
611
612 thd->stmt_arena->state != Query_arena::PREPARED)
613 */
614 {
615 SELECT_LEX *current= thd->lex->current_select;
616 thd->lex->current_select= current->return_after_parsing();
617 char const *save_where= thd->where;
618 thd->where= "IN/ALL/ANY subquery";
619
620 bool failure= in_subs->left_expr->fix_fields_if_needed(thd,
621 &in_subs->left_expr);
622 thd->lex->current_select= current;
623 thd->where= save_where;
624 if (failure)
625 DBUG_RETURN(-1); /* purecov: deadcode */
626
627 /*
628 Check if the left and right expressions have the same # of
629 columns, i.e. we don't have a case like
630 (oe1, oe2) IN (SELECT ie1, ie2, ie3 ...)
631
632 TODO why do we have this duplicated in IN->EXISTS transformers?
633 psergey-todo: fix these: grep for duplicated_subselect_card_check
634 */
635 if (select_lex->item_list.elements != in_subs->left_expr->cols())
636 {
637 my_error(ER_OPERAND_COLUMNS, MYF(0), in_subs->left_expr->cols());
638 DBUG_RETURN(-1);
639 }
640 }
641
642 DBUG_PRINT("info", ("Checking if subq can be converted to semi-join"));
643 /*
644 Check if we're in subquery that is a candidate for flattening into a
645 semi-join (which is done in flatten_subqueries()). The
646 requirements are:
647 1. Subquery predicate is an IN/=ANY subq predicate
648 2. Subquery is a single SELECT (not a UNION)
649 3. Subquery does not have GROUP BY or ORDER BY
650 4. Subquery does not use aggregate functions or HAVING
651 5. Subquery predicate is at the AND-top-level of ON/WHERE clause
652 6. We are not in a subquery of a single table UPDATE/DELETE that
653 doesn't have a JOIN (TODO: We should handle this at some
654 point by switching to multi-table UPDATE/DELETE)
655 7. We're not in a table-less subquery like "SELECT 1"
656 8. No execution method was already chosen (by a prepared statement)
657 9. Parent select is not a table-less select
658 10. Neither parent nor child select have STRAIGHT_JOIN option.
659 11. It is first optimisation (the subquery could be moved from ON
660 clause during first optimisation and then be considered for SJ
661 on the second when it is too late)
662 */
663 if (optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
664 in_subs && // 1
665 !select_lex->is_part_of_union() && // 2
666 !select_lex->group_list.elements && !join->order && // 3
667 !join->having && !select_lex->with_sum_func && // 4
668 in_subs->emb_on_expr_nest && // 5
669 select_lex->outer_select()->join && // 6
670 parent_unit->first_select()->leaf_tables.elements && // 7
671 !in_subs->has_strategy() && // 8
672 select_lex->outer_select()->table_list.first && // 9
673 !((join->select_options | // 10
674 select_lex->outer_select()->join->select_options) // 10
675 & SELECT_STRAIGHT_JOIN) && // 10
676 select_lex->first_cond_optimization) // 11
677 {
678 DBUG_PRINT("info", ("Subquery is semi-join conversion candidate"));
679
680 (void)subquery_types_allow_materialization(in_subs);
681
682 in_subs->is_flattenable_semijoin= TRUE;
683
684 /* Register the subquery for further processing in flatten_subqueries() */
685 if (!in_subs->is_registered_semijoin)
686 {
687 Query_arena *arena, backup;
688 arena= thd->activate_stmt_arena_if_needed(&backup);
689 select_lex->outer_select()->sj_subselects.push_back(in_subs,
690 thd->mem_root);
691 if (arena)
692 thd->restore_active_arena(arena, &backup);
693 in_subs->is_registered_semijoin= TRUE;
694 }
695 }
696 else
697 {
698 DBUG_PRINT("info", ("Subquery can't be converted to merged semi-join"));
699 /* Test if the user has set a legal combination of optimizer switches. */
700 DBUG_ASSERT(optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS |
701 OPTIMIZER_SWITCH_MATERIALIZATION));
702 /*
703 Transform each subquery predicate according to its overloaded
704 transformer.
705 */
706 if (subselect->select_transformer(join))
707 DBUG_RETURN(-1);
708
709 /*
710 If the subquery predicate is IN/=ANY, analyse and set all possible
711 subquery execution strategies based on optimizer switches and syntactic
712 properties.
713 */
714 if (in_subs && !in_subs->has_strategy())
715 {
716 if (is_materialization_applicable(thd, in_subs, select_lex))
717 {
718 in_subs->add_strategy(SUBS_MATERIALIZATION);
719
720 /*
721 If the subquery is an AND-part of WHERE register for being processed
722 with jtbm strategy
723 */
724 if (in_subs->emb_on_expr_nest == NO_JOIN_NEST &&
725 optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN))
726 {
727 in_subs->is_flattenable_semijoin= FALSE;
728 if (!in_subs->is_registered_semijoin)
729 {
730 Query_arena *arena, backup;
731 arena= thd->activate_stmt_arena_if_needed(&backup);
732 select_lex->outer_select()->sj_subselects.push_back(in_subs,
733 thd->mem_root);
734 if (arena)
735 thd->restore_active_arena(arena, &backup);
736 in_subs->is_registered_semijoin= TRUE;
737 }
738 }
739 }
740
741 /*
742 IN-TO-EXISTS is the only universal strategy. Choose it if the user
743 allowed it via an optimizer switch, or if materialization is not
744 possible.
745 */
746 if (optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS) ||
747 !in_subs->has_strategy())
748 in_subs->add_strategy(SUBS_IN_TO_EXISTS);
749 }
750
751 /* Check if max/min optimization applicable */
752 if (allany_subs && !allany_subs->is_set_strategy())
753 {
754 uchar strategy= (allany_subs->is_maxmin_applicable(join) ?
755 (SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE) :
756 SUBS_IN_TO_EXISTS);
757 allany_subs->add_strategy(strategy);
758 }
759
760 }
761 }
762 DBUG_RETURN(0);
763 }
764
765
766 /**
767 @brief Check if subquery's compared types allow materialization.
768
769 @param in_subs Subquery predicate, updated as follows:
770 types_allow_materialization TRUE if subquery materialization is allowed.
771 sjm_scan_allowed If types_allow_materialization is TRUE,
772 indicates whether it is possible to use subquery
773 materialization and scan the materialized table.
774
775 @retval TRUE If subquery types allow materialization.
776 @retval FALSE Otherwise.
777
778 @details
779 This is a temporary fix for BUG#36752.
780
781 There are two subquery materialization strategies:
782
783 1. Materialize and do index lookups in the materialized table. See
784 BUG#36752 for description of restrictions we need to put on the
785 compared expressions.
786
787 2. Materialize and then do a full scan of the materialized table. At the
788 moment, this strategy's applicability criteria are even stricter than
789 in #1.
790
791 This is so because of the following: consider an uncorrelated subquery
792
793 ...WHERE (ot1.col1, ot2.col2 ...) IN (SELECT ie1,ie2,... FROM it1 ...)
794
795 and a join order that could be used to do sjm-materialization:
796
797 SJM-Scan(it1, it1), ot1, ot2
798
799 IN-equalities will be parts of conditions attached to the outer tables:
800
801 ot1: ot1.col1 = ie1 AND ... (C1)
802 ot2: ot1.col2 = ie2 AND ... (C2)
803
804 besides those there may be additional references to ie1 and ie2
805 generated by equality propagation. The problem with evaluating C1 and
806 C2 is that ie{1,2} refer to subquery tables' columns, while we only have
807 current value of materialization temptable. Our solution is to
808 * require that all ie{N} are table column references. This allows
809 to copy the values of materialization temptable columns to the
810 original table's columns (see setup_sj_materialization for more
811 details)
812 * require that compared columns have exactly the same type. This is
813 a temporary measure to avoid BUG#36752-type problems.
814
815 JOIN_TAB::keyuse_is_valid_for_access_in_chosen_plan expects that for Semi Join Materialization
816 Scan all the items in the select list of the IN Subquery are of the type Item::FIELD_ITEM.
817 */
818
819 static
subquery_types_allow_materialization(Item_in_subselect * in_subs)820 bool subquery_types_allow_materialization(Item_in_subselect *in_subs)
821 {
822 DBUG_ENTER("subquery_types_allow_materialization");
823
824 DBUG_ASSERT(in_subs->left_expr->fixed);
825
826 List_iterator<Item> it(in_subs->unit->first_select()->item_list);
827 uint elements= in_subs->unit->first_select()->item_list.elements;
828
829 in_subs->types_allow_materialization= FALSE; // Assign default values
830 in_subs->sjm_scan_allowed= FALSE;
831
832 /*
833 The checks here must be kept in sync with the one in
834 Item_func_in::in_predicate_to_in_subs_transformer().
835 */
836
837 bool all_are_fields= TRUE;
838 uint32 total_key_length = 0;
839 bool converted_from_in_predicate= in_subs->converted_from_in_predicate;
840 for (uint i= 0; i < elements; i++)
841 {
842 Item *outer= in_subs->left_expr->element_index(i);
843 Item *inner= it++;
844 all_are_fields &= (outer->real_item()->type() == Item::FIELD_ITEM &&
845 inner->real_item()->type() == Item::FIELD_ITEM);
846 total_key_length += inner->max_length;
847
848 if (!inner->
849 type_handler()->
850 subquery_type_allows_materialization(inner,
851 outer,
852 converted_from_in_predicate))
853 DBUG_RETURN(FALSE);
854 }
855
856 /*
857 Make sure that create_tmp_table will not fail due to too long keys.
858 See MDEV-7122. This check is performed inside create_tmp_table also and
859 we must do it so that we know the table has keys created.
860 Make sure that the length of the key for the temp_table is atleast
861 greater than 0.
862 */
863 if (!total_key_length || total_key_length > tmp_table_max_key_length() ||
864 elements > tmp_table_max_key_parts())
865 DBUG_RETURN(FALSE);
866
867 in_subs->types_allow_materialization= TRUE;
868 in_subs->sjm_scan_allowed= all_are_fields;
869 DBUG_PRINT("info",("subquery_types_allow_materialization: ok, allowed"));
870 DBUG_RETURN(TRUE);
871 }
872
873
874 /**
875 Apply max min optimization of all/any subselect
876 */
877
transform_max_min_subquery()878 bool JOIN::transform_max_min_subquery()
879 {
880 DBUG_ENTER("JOIN::transform_max_min_subquery");
881 Item_subselect *subselect= unit->item;
882 if (!subselect || (subselect->substype() != Item_subselect::ALL_SUBS &&
883 subselect->substype() != Item_subselect::ANY_SUBS))
884 DBUG_RETURN(0);
885 DBUG_RETURN(((Item_allany_subselect *) subselect)->
886 transform_into_max_min(this));
887 }
888
889
890 /*
891 Finalize IN->EXISTS conversion in case we couldn't use materialization.
892
893 DESCRIPTION Invoke the IN->EXISTS converter
894 Replace the Item_in_subselect with its wrapper Item_in_optimizer in WHERE.
895
896 RETURN
897 FALSE - Ok
898 TRUE - Fatal error
899 */
900
make_in_exists_conversion(THD * thd,JOIN * join,Item_in_subselect * item)901 bool make_in_exists_conversion(THD *thd, JOIN *join, Item_in_subselect *item)
902 {
903 DBUG_ENTER("make_in_exists_conversion");
904 JOIN *child_join= item->unit->first_select()->join;
905 bool res;
906
907 /*
908 We're going to finalize IN->EXISTS conversion.
909 Normally, IN->EXISTS conversion takes place inside the
910 Item_subselect::fix_fields() call, where item_subselect->fixed==FALSE (as
911 fix_fields() haven't finished yet) and item_subselect->changed==FALSE (as
912 the conversion haven't been finalized)
913
914 At the end of Item_subselect::fix_fields() we had to set fixed=TRUE,
915 changed=TRUE (the only other option would have been to return error).
916
917 So, now we have to set these back for the duration of select_transformer()
918 call.
919 */
920 item->changed= 0;
921 item->fixed= 0;
922
923 SELECT_LEX *save_select_lex= thd->lex->current_select;
924 thd->lex->current_select= item->unit->first_select();
925
926 res= item->select_transformer(child_join);
927
928 thd->lex->current_select= save_select_lex;
929
930 if (res)
931 DBUG_RETURN(TRUE);
932
933 item->changed= 1;
934 item->fixed= 1;
935
936 Item *substitute= item->substitution;
937 bool do_fix_fields= !item->substitution->fixed;
938 /*
939 The Item_subselect has already been wrapped with Item_in_optimizer, so we
940 should search for item->optimizer, not 'item'.
941 */
942 Item *replace_me= item->optimizer;
943 DBUG_ASSERT(replace_me==substitute);
944
945 Item **tree= (item->emb_on_expr_nest == NO_JOIN_NEST)?
946 &join->conds : &(item->emb_on_expr_nest->on_expr);
947 if (replace_where_subcondition(join, tree, replace_me, substitute,
948 do_fix_fields))
949 DBUG_RETURN(TRUE);
950 item->substitution= NULL;
951
952 /*
953 If this is a prepared statement, repeat the above operation for
954 prep_where (or prep_on_expr).
955 */
956 if (!thd->stmt_arena->is_conventional())
957 {
958 tree= (item->emb_on_expr_nest == (TABLE_LIST*)NO_JOIN_NEST)?
959 &join->select_lex->prep_where :
960 &(item->emb_on_expr_nest->prep_on_expr);
961
962 if (replace_where_subcondition(join, tree, replace_me, substitute,
963 FALSE))
964 DBUG_RETURN(TRUE);
965 }
966 DBUG_RETURN(FALSE);
967 }
968
969
check_for_outer_joins(List<TABLE_LIST> * join_list)970 bool check_for_outer_joins(List<TABLE_LIST> *join_list)
971 {
972 TABLE_LIST *table;
973 NESTED_JOIN *nested_join;
974 List_iterator<TABLE_LIST> li(*join_list);
975 while ((table= li++))
976 {
977 if ((nested_join= table->nested_join))
978 {
979 if (check_for_outer_joins(&nested_join->join_list))
980 return TRUE;
981 }
982
983 if (table->outer_join)
984 return TRUE;
985 }
986 return FALSE;
987 }
988
989
find_and_block_conversion_to_sj(Item * to_find,List_iterator_fast<Item_in_subselect> & li)990 void find_and_block_conversion_to_sj(Item *to_find,
991 List_iterator_fast<Item_in_subselect> &li)
992 {
993 if (to_find->type() == Item::FUNC_ITEM &&
994 ((Item_func*)to_find)->functype() == Item_func::IN_OPTIMIZER_FUNC)
995 to_find= ((Item_in_optimizer*)to_find)->get_wrapped_in_subselect_item();
996
997 if (to_find->type() != Item::SUBSELECT_ITEM ||
998 ((Item_subselect *) to_find)->substype() != Item_subselect::IN_SUBS)
999 return;
1000 Item_in_subselect *in_subq;
1001 li.rewind();
1002 while ((in_subq= li++))
1003 {
1004 if (in_subq == to_find)
1005 {
1006 in_subq->block_conversion_to_sj();
1007 return;
1008 }
1009 }
1010 }
1011
1012
1013 /*
1014 Convert semi-join subquery predicates into semi-join join nests
1015
1016 SYNOPSIS
1017 convert_join_subqueries_to_semijoins()
1018
1019 DESCRIPTION
1020
1021 Convert candidate subquery predicates into semi-join join nests. This
1022 transformation is performed once in query lifetime and is irreversible.
1023
1024 Conversion of one subquery predicate
1025 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1026 We start with a join that has a semi-join subquery:
1027
1028 SELECT ...
1029 FROM ot, ...
1030 WHERE oe IN (SELECT ie FROM it1 ... itN WHERE subq_where) AND outer_where
1031
1032 and convert it into a semi-join nest:
1033
1034 SELECT ...
1035 FROM ot SEMI JOIN (it1 ... itN), ...
1036 WHERE outer_where AND subq_where AND oe=ie
1037
1038 that is, in order to do the conversion, we need to
1039
1040 * Create the "SEMI JOIN (it1 .. itN)" part and add it into the parent
1041 query's FROM structure.
1042 * Add "AND subq_where AND oe=ie" into parent query's WHERE (or ON if
1043 the subquery predicate was in an ON expression)
1044 * Remove the subquery predicate from the parent query's WHERE
1045
1046 Considerations when converting many predicates
1047 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1048 A join may have at most MAX_TABLES tables. This may prevent us from
1049 flattening all subqueries when the total number of tables in parent and
1050 child selects exceeds MAX_TABLES.
1051 We deal with this problem by flattening children's subqueries first and
1052 then using a heuristic rule to determine each subquery predicate's
1053 "priority".
1054
1055 RETURN
1056 FALSE OK
1057 TRUE Error
1058 */
1059
convert_join_subqueries_to_semijoins(JOIN * join)1060 bool convert_join_subqueries_to_semijoins(JOIN *join)
1061 {
1062 Query_arena *arena, backup;
1063 Item_in_subselect *in_subq;
1064 THD *thd= join->thd;
1065 DBUG_ENTER("convert_join_subqueries_to_semijoins");
1066
1067 if (join->select_lex->sj_subselects.is_empty())
1068 DBUG_RETURN(FALSE);
1069
1070 List_iterator_fast<Item_in_subselect> li(join->select_lex->sj_subselects);
1071
1072 while ((in_subq= li++))
1073 {
1074 SELECT_LEX *subq_sel= in_subq->get_select_lex();
1075 if (subq_sel->handle_derived(thd->lex, DT_MERGE))
1076 DBUG_RETURN(TRUE);
1077 if (subq_sel->join->transform_in_predicates_into_in_subq(thd))
1078 DBUG_RETURN(TRUE);
1079 subq_sel->update_used_tables();
1080 }
1081
1082 /*
1083 Check all candidates to semi-join conversion that occur
1084 in ON expressions of outer join. Set the flag blocking
1085 this conversion for them.
1086 */
1087 TABLE_LIST *tbl;
1088 List_iterator<TABLE_LIST> ti(join->select_lex->leaf_tables);
1089 while ((tbl= ti++))
1090 {
1091 TABLE_LIST *embedded;
1092 TABLE_LIST *embedding= tbl;
1093 do
1094 {
1095 embedded= embedding;
1096 bool block_conversion_to_sj= false;
1097 if (embedded->on_expr)
1098 {
1099 /*
1100 Conversion of an IN subquery predicate into semi-join
1101 is blocked now if the predicate occurs:
1102 - in the ON expression of an outer join
1103 - in the ON expression of an inner join embedded directly
1104 or indirectly in the inner nest of an outer join
1105 */
1106 for (TABLE_LIST *tl= embedded; tl; tl= tl->embedding)
1107 {
1108 if (tl->outer_join)
1109 {
1110 block_conversion_to_sj= true;
1111 break;
1112 }
1113 }
1114 }
1115 if (block_conversion_to_sj)
1116 {
1117 Item *cond= embedded->on_expr;
1118 if (!cond)
1119 ;
1120 else if (cond->type() != Item::COND_ITEM)
1121 find_and_block_conversion_to_sj(cond, li);
1122 else if (((Item_cond*) cond)->functype() ==
1123 Item_func::COND_AND_FUNC)
1124 {
1125 Item *item;
1126 List_iterator<Item> it(*(((Item_cond*) cond)->argument_list()));
1127 while ((item= it++))
1128 {
1129 find_and_block_conversion_to_sj(item, li);
1130 }
1131 }
1132 }
1133 embedding= embedded->embedding;
1134 }
1135 while (embedding &&
1136 embedding->nested_join->join_list.head() == embedded);
1137 }
1138
1139 /*
1140 Block conversion to semi-joins for those candidates that
1141 are encountered in the WHERE condition of the multi-table view
1142 with CHECK OPTION if this view is used in UPDATE/DELETE.
1143 (This limitation can be, probably, easily lifted.)
1144 */
1145 li.rewind();
1146 while ((in_subq= li++))
1147 {
1148 if (in_subq->emb_on_expr_nest != NO_JOIN_NEST &&
1149 in_subq->emb_on_expr_nest->effective_with_check)
1150 {
1151 in_subq->block_conversion_to_sj();
1152 }
1153 }
1154
1155 if (join->select_options & SELECT_STRAIGHT_JOIN)
1156 {
1157 /* Block conversion to semijoins for all candidates */
1158 li.rewind();
1159 while ((in_subq= li++))
1160 {
1161 in_subq->block_conversion_to_sj();
1162 }
1163 }
1164
1165 li.rewind();
1166 /* First, convert child join's subqueries. We proceed bottom-up here */
1167 while ((in_subq= li++))
1168 {
1169 st_select_lex *child_select= in_subq->get_select_lex();
1170 JOIN *child_join= child_select->join;
1171 child_join->outer_tables = child_join->table_count;
1172
1173 /*
1174 child_select->where contains only the WHERE predicate of the
1175 subquery itself here. We may be selecting from a VIEW, which has its
1176 own predicate. The combined predicates are available in child_join->conds,
1177 which was built by setup_conds() doing prepare_where() for all views.
1178 */
1179 child_select->where= child_join->conds;
1180
1181 if (convert_join_subqueries_to_semijoins(child_join))
1182 DBUG_RETURN(TRUE);
1183
1184
1185 in_subq->sj_convert_priority=
1186 MY_TEST(in_subq->do_not_convert_to_sj) * MAX_TABLES * 2 +
1187 in_subq->is_correlated * MAX_TABLES + child_join->outer_tables;
1188 }
1189
1190 // Temporary measure: disable semi-joins when they are together with outer
1191 // joins.
1192 #if 0
1193 if (check_for_outer_joins(join->join_list))
1194 {
1195 in_subq= join->select_lex->sj_subselects.head();
1196 arena= thd->activate_stmt_arena_if_needed(&backup);
1197 goto skip_conversion;
1198 }
1199 #endif
1200 //dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables);
1201 /*
1202 2. Pick which subqueries to convert:
1203 sort the subquery array
1204 - prefer correlated subqueries over uncorrelated;
1205 - prefer subqueries that have greater number of outer tables;
1206 */
1207 bubble_sort<Item_in_subselect>(&join->select_lex->sj_subselects,
1208 subq_sj_candidate_cmp, NULL);
1209 // #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
1210 /* Replace all subqueries to be flattened with Item_int(1) */
1211 arena= thd->activate_stmt_arena_if_needed(&backup);
1212
1213 li.rewind();
1214 while ((in_subq= li++))
1215 {
1216 bool remove_item= TRUE;
1217
1218 /* Stop processing if we've reached a subquery that's attached to the ON clause */
1219 if (in_subq->do_not_convert_to_sj)
1220 break;
1221
1222 if (in_subq->is_flattenable_semijoin)
1223 {
1224 if (join->table_count +
1225 in_subq->unit->first_select()->join->table_count >= MAX_TABLES)
1226 break;
1227 if (convert_subq_to_sj(join, in_subq))
1228 goto restore_arena_and_fail;
1229 }
1230 else
1231 {
1232 if (join->table_count + 1 >= MAX_TABLES)
1233 break;
1234 if (convert_subq_to_jtbm(join, in_subq, &remove_item))
1235 goto restore_arena_and_fail;
1236 }
1237 if (remove_item)
1238 {
1239 Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
1240 &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
1241 Item *replace_me= in_subq->original_item();
1242 if (replace_where_subcondition(join, tree, replace_me,
1243 new (thd->mem_root) Item_int(thd, 1),
1244 FALSE))
1245 goto restore_arena_and_fail;
1246 }
1247 }
1248 //skip_conversion:
1249 /*
1250 3. Finalize (perform IN->EXISTS rewrite) the subqueries that we didn't
1251 convert:
1252 */
1253 while (in_subq)
1254 {
1255 JOIN *child_join= in_subq->unit->first_select()->join;
1256 in_subq->changed= 0;
1257 in_subq->fixed= 0;
1258
1259 SELECT_LEX *save_select_lex= thd->lex->current_select;
1260 thd->lex->current_select= in_subq->unit->first_select();
1261
1262 bool res= in_subq->select_transformer(child_join);
1263
1264 thd->lex->current_select= save_select_lex;
1265
1266 if (res)
1267 DBUG_RETURN(TRUE);
1268
1269 in_subq->changed= 1;
1270 in_subq->fixed= 1;
1271
1272 Item *substitute= in_subq->substitution;
1273 bool do_fix_fields= !in_subq->substitution->fixed;
1274 Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
1275 &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
1276 Item *replace_me= in_subq->original_item();
1277 if (replace_where_subcondition(join, tree, replace_me, substitute,
1278 do_fix_fields))
1279 DBUG_RETURN(TRUE);
1280 in_subq->substitution= NULL;
1281 /*
1282 If this is a prepared statement, repeat the above operation for
1283 prep_where (or prep_on_expr). Subquery-to-semijoin conversion is
1284 done once for prepared statement.
1285 */
1286 if (!thd->stmt_arena->is_conventional())
1287 {
1288 tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
1289 &join->select_lex->prep_where :
1290 &(in_subq->emb_on_expr_nest->prep_on_expr);
1291 /*
1292 prep_on_expr/ prep_where may be NULL in some cases.
1293 If that is the case, do nothing - simplify_joins() will copy
1294 ON/WHERE expression into prep_on_expr/prep_where.
1295 */
1296 if (*tree && replace_where_subcondition(join, tree, replace_me, substitute,
1297 FALSE))
1298 DBUG_RETURN(TRUE);
1299 }
1300 /*
1301 Revert to the IN->EXISTS strategy in the rare case when the subquery could
1302 not be flattened.
1303 */
1304 in_subq->reset_strategy(SUBS_IN_TO_EXISTS);
1305 if (is_materialization_applicable(thd, in_subq,
1306 in_subq->unit->first_select()))
1307 {
1308 in_subq->add_strategy(SUBS_MATERIALIZATION);
1309 }
1310
1311 in_subq= li++;
1312 }
1313
1314 if (arena)
1315 thd->restore_active_arena(arena, &backup);
1316 join->select_lex->sj_subselects.empty();
1317 DBUG_RETURN(FALSE);
1318
1319 restore_arena_and_fail:
1320 if (arena)
1321 thd->restore_active_arena(arena, &backup);
1322 DBUG_RETURN(TRUE);
1323 }
1324
1325
1326 /*
1327 Get #output_rows and scan_time estimates for a "delayed" table.
1328
1329 SYNOPSIS
1330 get_delayed_table_estimates()
1331 table IN Table to get estimates for
1332 out_rows OUT E(#rows in the table)
1333 scan_time OUT E(scan_time).
1334 startup_cost OUT cost to populate the table.
1335
1336 DESCRIPTION
1337 Get #output_rows and scan_time estimates for a "delayed" table. By
1338 "delayed" here we mean that the table is filled at the start of query
1339 execution. This means that the optimizer can't use table statistics to
1340 get #rows estimate for it, it has to call this function instead.
1341
1342 This function is expected to make different actions depending on the nature
1343 of the table. At the moment there is only one kind of delayed tables,
1344 non-flattenable semi-joins.
1345 */
1346
get_delayed_table_estimates(TABLE * table,ha_rows * out_rows,double * scan_time,double * startup_cost)1347 void get_delayed_table_estimates(TABLE *table,
1348 ha_rows *out_rows,
1349 double *scan_time,
1350 double *startup_cost)
1351 {
1352 Item_in_subselect *item= table->pos_in_table_list->jtbm_subselect;
1353
1354 DBUG_ASSERT(item->engine->engine_type() ==
1355 subselect_engine::HASH_SJ_ENGINE);
1356
1357 subselect_hash_sj_engine *hash_sj_engine=
1358 ((subselect_hash_sj_engine*)item->engine);
1359
1360 *out_rows= (ha_rows)item->jtbm_record_count;
1361 *startup_cost= item->jtbm_read_time;
1362
1363 /* Calculate cost of scanning the temptable */
1364 double data_size= COST_MULT(item->jtbm_record_count,
1365 hash_sj_engine->tmp_table->s->reclength);
1366 /* Do like in handler::read_time */
1367 *scan_time= data_size/IO_SIZE + 2;
1368 }
1369
1370
1371 /**
1372 @brief Replaces an expression destructively inside the expression tree of
1373 the WHERE clase.
1374
1375 @note We substitute AND/OR structure because it was copied by
1376 copy_andor_structure and some changes could be done in the copy but
1377 should be left permanent, also there could be several layers of AND over
1378 AND and OR over OR because ::fix_field() possibly is not called.
1379
1380 @param join The top-level query.
1381 @param old_cond The expression to be replaced.
1382 @param new_cond The expression to be substituted.
1383 @param do_fix_fields If true, Item::fix_fields(THD*, Item**) is called for
1384 the new expression.
1385 @return <code>true</code> if there was an error, <code>false</code> if
1386 successful.
1387 */
1388
replace_where_subcondition(JOIN * join,Item ** expr,Item * old_cond,Item * new_cond,bool do_fix_fields)1389 static bool replace_where_subcondition(JOIN *join, Item **expr,
1390 Item *old_cond, Item *new_cond,
1391 bool do_fix_fields)
1392 {
1393 if (*expr == old_cond)
1394 {
1395 *expr= new_cond;
1396 if (do_fix_fields)
1397 new_cond->fix_fields(join->thd, expr);
1398 return FALSE;
1399 }
1400
1401 if ((*expr)->type() == Item::COND_ITEM)
1402 {
1403 List_iterator<Item> li(*((Item_cond*)(*expr))->argument_list());
1404 Item *item;
1405 while ((item= li++))
1406 {
1407 if (item == old_cond)
1408 {
1409 li.replace(new_cond);
1410 if (do_fix_fields)
1411 new_cond->fix_fields(join->thd, li.ref());
1412 return FALSE;
1413 }
1414 else if (item->type() == Item::COND_ITEM)
1415 {
1416 replace_where_subcondition(join, li.ref(),
1417 old_cond, new_cond,
1418 do_fix_fields);
1419 }
1420 }
1421 }
1422 /*
1423 We can come to here when
1424 - we're doing replace operations on both on_expr and prep_on_expr
1425 - on_expr is the same as prep_on_expr, or they share a sub-tree
1426 (so, when we do replace in on_expr, we replace in prep_on_expr, too,
1427 and when we try doing a replace in prep_on_expr, the item we wanted
1428 to replace there has already been replaced)
1429 */
1430 return FALSE;
1431 }
1432
subq_sj_candidate_cmp(Item_in_subselect * el1,Item_in_subselect * el2,void * arg)1433 static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
1434 void *arg)
1435 {
1436 return (el1->sj_convert_priority > el2->sj_convert_priority) ? -1 :
1437 ( (el1->sj_convert_priority == el2->sj_convert_priority)? 0 : 1);
1438 }
1439
1440
1441 /**
1442 @brief
1443 reset the value of the field in_eqaulity_no for all Item_func_eq
1444 items in the where clause of the subquery.
1445
1446 Look for in_equality_no description in Item_func_eq class
1447
1448 DESCRIPTION
1449 Lets have an example:
1450 SELECT t1.a FROM t1 WHERE t1.a IN
1451 (SELECT t2.a FROM t2 where t2.b IN
1452 (select t3.b from t3 where t3.c=27 ))
1453
1454 So for such a query we have the parent, child and
1455 grandchild select.
1456
1457 So for the equality t2.b = t3.b we set the value for in_equality_no to
1458 0 according to its description. Wewe do the same for t1.a = t2.a.
1459 But when we look at the child select (with the grandchild select merged),
1460 the query would be
1461
1462 SELECT t1.a FROM t1 WHERE t1.a IN
1463 (SELECT t2.a FROM t2 where t2.b = t3.b and t3.c=27)
1464
1465 and then when the child select is merged into the parent select the query
1466 would look like
1467
1468 SELECT t1.a FROM t1, semi-join-nest(t2,t3)
1469 WHERE t1.a =t2.a and t2.b = t3.b and t3.c=27
1470
1471 Still we would have in_equality_no set for t2.b = t3.b
1472 though it does not take part in the semi-join equality for the parent select,
1473 so we should reset its value to UINT_MAX.
1474
1475 @param cond WHERE clause of the subquery
1476 */
1477
reset_equality_number_for_subq_conds(Item * cond)1478 static void reset_equality_number_for_subq_conds(Item * cond)
1479 {
1480 if (!cond)
1481 return;
1482 if (cond->type() == Item::COND_ITEM)
1483 {
1484 List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
1485 Item *item;
1486 while ((item=li++))
1487 {
1488 if (item->type() == Item::FUNC_ITEM &&
1489 ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
1490 ((Item_func_eq*)item)->in_equality_no= UINT_MAX;
1491 }
1492 }
1493 else
1494 {
1495 if (cond->type() == Item::FUNC_ITEM &&
1496 ((Item_func*)cond)->functype()== Item_func::EQ_FUNC)
1497 ((Item_func_eq*)cond)->in_equality_no= UINT_MAX;
1498 }
1499 return;
1500 }
1501
1502 /*
1503 Convert a subquery predicate into a TABLE_LIST semi-join nest
1504
1505 SYNOPSIS
1506 convert_subq_to_sj()
1507 parent_join Parent join, the one that has subq_pred in its WHERE/ON
1508 clause
1509 subq_pred Subquery predicate to be converted
1510
1511 DESCRIPTION
1512 Convert a subquery predicate into a TABLE_LIST semi-join nest. All the
1513 prerequisites are already checked, so the conversion is always successfull.
1514
1515 Prepared Statements: the transformation is permanent:
1516 - Changes in TABLE_LIST structures are naturally permanent
1517 - Item tree changes are performed on statement MEM_ROOT:
1518 = we activate statement MEM_ROOT
1519 = this function is called before the first fix_prepare_information
1520 call.
1521
1522 This is intended because the criteria for subquery-to-sj conversion remain
1523 constant for the lifetime of the Prepared Statement.
1524
1525 RETURN
1526 FALSE OK
1527 TRUE Out of memory error
1528 */
1529
convert_subq_to_sj(JOIN * parent_join,Item_in_subselect * subq_pred)1530 static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
1531 {
1532 SELECT_LEX *parent_lex= parent_join->select_lex;
1533 TABLE_LIST *emb_tbl_nest= NULL;
1534 TABLE_LIST *orig_tl;
1535 List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
1536 THD *thd= parent_join->thd;
1537 DBUG_ENTER("convert_subq_to_sj");
1538
1539 /*
1540 1. Find out where to put the predicate into.
1541 Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
1542 */
1543 if ((void*)subq_pred->emb_on_expr_nest != (void*)NO_JOIN_NEST)
1544 {
1545 if (subq_pred->emb_on_expr_nest->nested_join)
1546 {
1547 /*
1548 We're dealing with
1549
1550 ... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
1551
1552 The sj-nest will be inserted into the brackets nest.
1553 */
1554 emb_tbl_nest= subq_pred->emb_on_expr_nest;
1555 emb_join_list= &emb_tbl_nest->nested_join->join_list;
1556 }
1557 else if (!subq_pred->emb_on_expr_nest->outer_join)
1558 {
1559 /*
1560 We're dealing with
1561
1562 ... INNER JOIN tblX ON (subquery AND whatever) ...
1563
1564 The sj-nest will be tblX's "sibling", i.e. another child of its
1565 parent. This is ok because tblX is joined as an inner join.
1566 */
1567 emb_tbl_nest= subq_pred->emb_on_expr_nest->embedding;
1568 if (emb_tbl_nest)
1569 emb_join_list= &emb_tbl_nest->nested_join->join_list;
1570 }
1571 else if (!subq_pred->emb_on_expr_nest->nested_join)
1572 {
1573 TABLE_LIST *outer_tbl= subq_pred->emb_on_expr_nest;
1574 TABLE_LIST *wrap_nest;
1575 LEX_CSTRING sj_wrap_name= { STRING_WITH_LEN("(sj-wrap)") };
1576 /*
1577 We're dealing with
1578
1579 ... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
1580
1581 we'll need to convert it into:
1582
1583 ... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
1584 | |
1585 |<----- wrap_nest ---->|
1586
1587 Q: other subqueries may be pointing to this element. What to do?
1588 A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
1589 But we'll need to fix other pointers.
1590 A2: Another way: have TABLE_LIST::next_ptr so the following
1591 subqueries know the table has been nested.
1592 A3: changes in the TABLE_LIST::outer_join will make everything work
1593 automatically.
1594 */
1595 if (!(wrap_nest= alloc_join_nest(thd)))
1596 {
1597 DBUG_RETURN(TRUE);
1598 }
1599 wrap_nest->embedding= outer_tbl->embedding;
1600 wrap_nest->join_list= outer_tbl->join_list;
1601 wrap_nest->alias= sj_wrap_name;
1602
1603 wrap_nest->nested_join->join_list.empty();
1604 wrap_nest->nested_join->join_list.push_back(outer_tbl, thd->mem_root);
1605
1606 outer_tbl->embedding= wrap_nest;
1607 outer_tbl->join_list= &wrap_nest->nested_join->join_list;
1608
1609 /*
1610 wrap_nest will take place of outer_tbl, so move the outer join flag
1611 and on_expr
1612 */
1613 wrap_nest->outer_join= outer_tbl->outer_join;
1614 outer_tbl->outer_join= 0;
1615
1616 wrap_nest->on_expr= outer_tbl->on_expr;
1617 outer_tbl->on_expr= NULL;
1618
1619 List_iterator<TABLE_LIST> li(*wrap_nest->join_list);
1620 TABLE_LIST *tbl;
1621 while ((tbl= li++))
1622 {
1623 if (tbl == outer_tbl)
1624 {
1625 li.replace(wrap_nest);
1626 break;
1627 }
1628 }
1629 /*
1630 Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
1631 semi-join nest into it
1632 */
1633 emb_join_list= &wrap_nest->nested_join->join_list;
1634 emb_tbl_nest= wrap_nest;
1635 }
1636 }
1637
1638 TABLE_LIST *sj_nest;
1639 NESTED_JOIN *nested_join;
1640 LEX_CSTRING sj_nest_name= { STRING_WITH_LEN("(sj-nest)") };
1641 if (!(sj_nest= alloc_join_nest(thd)))
1642 {
1643 DBUG_RETURN(TRUE);
1644 }
1645 nested_join= sj_nest->nested_join;
1646
1647 sj_nest->join_list= emb_join_list;
1648 sj_nest->embedding= emb_tbl_nest;
1649 sj_nest->alias= sj_nest_name;
1650 sj_nest->sj_subq_pred= subq_pred;
1651 sj_nest->original_subq_pred_used_tables= subq_pred->used_tables() |
1652 subq_pred->left_expr->used_tables();
1653 /* Nests do not participate in those 'chains', so: */
1654 /* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
1655 emb_join_list->push_back(sj_nest, thd->mem_root);
1656
1657 /*
1658 nested_join->used_tables and nested_join->not_null_tables are
1659 initialized in simplify_joins().
1660 */
1661
1662 /*
1663 2. Walk through subquery's top list and set 'embedding' to point to the
1664 sj-nest.
1665 */
1666 st_select_lex *subq_lex= subq_pred->unit->first_select();
1667 DBUG_ASSERT(subq_lex->next_select() == NULL);
1668 nested_join->join_list.empty();
1669 List_iterator_fast<TABLE_LIST> li(subq_lex->top_join_list);
1670 TABLE_LIST *tl;
1671 while ((tl= li++))
1672 {
1673 tl->embedding= sj_nest;
1674 tl->join_list= &nested_join->join_list;
1675 nested_join->join_list.push_back(tl, thd->mem_root);
1676 }
1677
1678 /*
1679 Reconnect the next_leaf chain.
1680 TODO: Do we have to put subquery's tables at the end of the chain?
1681 Inserting them at the beginning would be a bit faster.
1682 NOTE: We actually insert them at the front! That's because the order is
1683 reversed in this list.
1684 */
1685 parent_lex->leaf_tables.append(&subq_lex->leaf_tables);
1686
1687 if (subq_lex->options & OPTION_SCHEMA_TABLE)
1688 parent_lex->options |= OPTION_SCHEMA_TABLE;
1689
1690 /*
1691 Same as above for next_local chain
1692 (a theory: a next_local chain always starts with ::leaf_tables
1693 because view's tables are inserted after the view)
1694 */
1695
1696 for (orig_tl= (TABLE_LIST*)(parent_lex->table_list.first);
1697 orig_tl->next_local;
1698 orig_tl= orig_tl->next_local)
1699 {}
1700
1701 orig_tl->next_local= subq_lex->join->tables_list;
1702
1703 /* A theory: no need to re-connect the next_global chain */
1704
1705 /* 3. Remove the original subquery predicate from the WHERE/ON */
1706
1707 /*TODO: also reset the 'm_with_subquery' there. */
1708
1709 /* n. Adjust the parent_join->table_count counter */
1710 uint table_no= parent_join->table_count;
1711 /* n. Walk through child's tables and adjust table->map */
1712 List_iterator_fast<TABLE_LIST> si(subq_lex->leaf_tables);
1713 while ((tl= si++))
1714 {
1715 tl->set_tablenr(table_no);
1716 if (tl->is_jtbm())
1717 {
1718 tl->jtbm_table_no= table_no;
1719 Item *dummy= tl->jtbm_subselect;
1720 tl->jtbm_subselect->fix_after_pullout(parent_lex, &dummy, true);
1721 DBUG_ASSERT(dummy == tl->jtbm_subselect);
1722 }
1723 SELECT_LEX *old_sl= tl->select_lex;
1724 tl->select_lex= parent_join->select_lex;
1725 for (TABLE_LIST *emb= tl->embedding;
1726 emb && emb->select_lex == old_sl;
1727 emb= emb->embedding)
1728 emb->select_lex= parent_join->select_lex;
1729 table_no++;
1730 }
1731 parent_join->table_count += subq_lex->join->table_count;
1732 //parent_join->table_count += subq_lex->leaf_tables.elements;
1733
1734 /*
1735 Put the subquery's WHERE into semi-join's sj_on_expr
1736 Add the subquery-induced equalities too.
1737 */
1738 SELECT_LEX *save_lex= thd->lex->current_select;
1739 table_map subq_pred_used_tables;
1740
1741 thd->lex->current_select=subq_lex;
1742 if (subq_pred->left_expr->fix_fields_if_needed(thd, &subq_pred->left_expr))
1743 goto restore_tl_and_exit;
1744 thd->lex->current_select=save_lex;
1745
1746 subq_pred_used_tables= subq_pred->used_tables();
1747 sj_nest->nested_join->sj_corr_tables= subq_pred_used_tables;
1748 sj_nest->nested_join->sj_depends_on= subq_pred_used_tables |
1749 subq_pred->left_expr->used_tables();
1750 sj_nest->sj_on_expr= subq_lex->join->conds;
1751
1752 /*
1753 Create the IN-equalities and inject them into semi-join's ON expression.
1754 Additionally, for LooseScan strategy
1755 - Record the number of IN-equalities.
1756 - Create list of pointers to (oe1, ..., ieN). We'll need the list to
1757 see which of the expressions are bound and which are not (for those
1758 we'll produce a distinct stream of (ie_i1,...ie_ik).
1759
1760 (TODO: can we just create a list of pointers and hope the expressions
1761 will not substitute themselves on fix_fields()? or we need to wrap
1762 them into Item_direct_view_refs and store pointers to those. The
1763 pointers to Item_direct_view_refs are guaranteed to be stable as
1764 Item_direct_view_refs doesn't substitute itself with anything in
1765 Item_direct_view_ref::fix_fields.
1766 */
1767 sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
1768 sj_nest->nested_join->sj_outer_expr_list.empty();
1769 reset_equality_number_for_subq_conds(sj_nest->sj_on_expr);
1770
1771 if (subq_pred->left_expr->cols() == 1)
1772 {
1773 /* add left = select_list_element */
1774 nested_join->sj_outer_expr_list.push_back(&subq_pred->left_expr,
1775 thd->mem_root);
1776 /*
1777 Create Item_func_eq. Note that
1778 1. this is done on the statement, not execution, arena
1779 2. if it's a PS then this happens only once - on the first execution.
1780 On following re-executions, the item will be fix_field-ed normally.
1781 3. Thus it should be created as if it was fix_field'ed, in particular
1782 all pointers to items in the execution arena should be protected
1783 with thd->change_item_tree
1784 */
1785 Item_func_eq *item_eq=
1786 new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr_orig,
1787 subq_lex->ref_pointer_array[0]);
1788 if (!item_eq)
1789 goto restore_tl_and_exit;
1790 if (subq_pred->left_expr_orig != subq_pred->left_expr)
1791 thd->change_item_tree(item_eq->arguments(), subq_pred->left_expr);
1792 item_eq->in_equality_no= 0;
1793 sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1794 }
1795 else if (subq_pred->left_expr->type() == Item::ROW_ITEM)
1796 {
1797 /*
1798 disassemple left expression and add
1799 left1 = select_list_element1 and left2 = select_list_element2 ...
1800 */
1801 for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
1802 {
1803 nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->addr(i),
1804 thd->mem_root);
1805 Item_func_eq *item_eq=
1806 new (thd->mem_root)
1807 Item_func_eq(thd, subq_pred->left_expr_orig->element_index(i),
1808 subq_lex->ref_pointer_array[i]);
1809 if (!item_eq)
1810 goto restore_tl_and_exit;
1811 DBUG_ASSERT(subq_pred->left_expr->element_index(i)->fixed);
1812 if (subq_pred->left_expr_orig->element_index(i) !=
1813 subq_pred->left_expr->element_index(i))
1814 thd->change_item_tree(item_eq->arguments(),
1815 subq_pred->left_expr->element_index(i));
1816 item_eq->in_equality_no= i;
1817 sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1818 }
1819 }
1820 else
1821 {
1822 /*
1823 add row operation
1824 left = (select_list_element1, select_list_element2, ...)
1825 */
1826 Item_row *row= new (thd->mem_root) Item_row(thd, subq_lex->pre_fix);
1827 /* fix fields on subquery was call so they should be the same */
1828 if (!row)
1829 goto restore_tl_and_exit;
1830 DBUG_ASSERT(subq_pred->left_expr->cols() == row->cols());
1831 nested_join->sj_outer_expr_list.push_back(&subq_pred->left_expr);
1832 Item_func_eq *item_eq=
1833 new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr_orig, row);
1834 if (!item_eq)
1835 goto restore_tl_and_exit;
1836 for (uint i= 0; i < row->cols(); i++)
1837 {
1838 if (row->element_index(i) != subq_lex->ref_pointer_array[i])
1839 thd->change_item_tree(row->addr(i), subq_lex->ref_pointer_array[i]);
1840 }
1841 item_eq->in_equality_no= 0;
1842 sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1843 }
1844 /*
1845 Fix the created equality and AND
1846
1847 Note that fix_fields() can actually fail in a meaningful way here. One
1848 example is when the IN-equality is not valid, because it compares columns
1849 with incompatible collations. (One can argue it would be more appropriate
1850 to check for this at name resolution stage, but as a legacy of IN->EXISTS
1851 we have in here).
1852 */
1853 if (sj_nest->sj_on_expr->fix_fields_if_needed(thd, &sj_nest->sj_on_expr))
1854 goto restore_tl_and_exit;
1855
1856 /*
1857 Walk through sj nest's WHERE and ON expressions and call
1858 item->fix_table_changes() for all items.
1859 */
1860 sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr,
1861 TRUE);
1862 fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
1863
1864
1865 /* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
1866 subq_lex->master_unit()->exclude_level();
1867
1868 DBUG_EXECUTE("where",
1869 print_where(sj_nest->sj_on_expr,"SJ-EXPR", QT_ORDINARY););
1870
1871 /* Inject sj_on_expr into the parent's WHERE or ON */
1872 if (emb_tbl_nest)
1873 {
1874 emb_tbl_nest->on_expr= and_items(thd, emb_tbl_nest->on_expr,
1875 sj_nest->sj_on_expr);
1876 emb_tbl_nest->on_expr->top_level_item();
1877 if (emb_tbl_nest->on_expr->fix_fields_if_needed(thd,
1878 &emb_tbl_nest->on_expr))
1879 goto restore_tl_and_exit;
1880 }
1881 else
1882 {
1883 /* Inject into the WHERE */
1884 parent_join->conds= and_items(thd, parent_join->conds, sj_nest->sj_on_expr);
1885 parent_join->conds->top_level_item();
1886 /*
1887 fix_fields must update the properties (e.g. st_select_lex::cond_count of
1888 the correct select_lex.
1889 */
1890 save_lex= thd->lex->current_select;
1891 thd->lex->current_select=parent_join->select_lex;
1892 if (parent_join->conds->fix_fields_if_needed(thd, &parent_join->conds))
1893 goto restore_tl_and_exit;
1894
1895 thd->lex->current_select=save_lex;
1896 parent_join->select_lex->where= parent_join->conds;
1897 }
1898
1899 if (subq_lex->ftfunc_list->elements)
1900 {
1901 Item_func_match *ifm;
1902 List_iterator_fast<Item_func_match> li(*(subq_lex->ftfunc_list));
1903 while ((ifm= li++))
1904 parent_lex->ftfunc_list->push_front(ifm, thd->mem_root);
1905 }
1906
1907 // The subqueries were replaced for Item_int(1) earlier
1908 subq_pred->reset_strategy(SUBS_SEMI_JOIN); // for subsequent executions
1909
1910 parent_lex->have_merged_subqueries= TRUE;
1911 /* Fatal error may have been set to by fix_after_pullout() */
1912 DBUG_RETURN(thd->is_fatal_error);
1913
1914 restore_tl_and_exit:
1915 orig_tl->next_local= NULL;
1916 DBUG_RETURN(TRUE);
1917 }
1918
1919
1920 const int SUBQERY_TEMPTABLE_NAME_MAX_LEN= 20;
1921
create_subquery_temptable_name(LEX_STRING * str,uint number)1922 static void create_subquery_temptable_name(LEX_STRING *str, uint number)
1923 {
1924 char *to= str->str;
1925 DBUG_ASSERT(number < 10000);
1926 to= strmov(to, "<subquery");
1927 to= int10_to_str((int) number, to, 10);
1928 to[0]= '>';
1929 to[1]= 0;
1930 str->length= (size_t) (to - str->str)+1;
1931 }
1932
1933
1934 /*
1935 Convert subquery predicate into non-mergeable semi-join nest.
1936
1937 TODO:
1938 why does this do IN-EXISTS conversion? Can't we unify it with mergeable
1939 semi-joins? currently, convert_subq_to_sj() cannot fail to convert (unless
1940 fatal errors)
1941
1942
1943 RETURN
1944 FALSE - Ok
1945 TRUE - Fatal error
1946 */
1947
convert_subq_to_jtbm(JOIN * parent_join,Item_in_subselect * subq_pred,bool * remove_item)1948 static bool convert_subq_to_jtbm(JOIN *parent_join,
1949 Item_in_subselect *subq_pred,
1950 bool *remove_item)
1951 {
1952 SELECT_LEX *parent_lex= parent_join->select_lex;
1953 List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
1954 TABLE_LIST *emb_tbl_nest= NULL; // will change when we learn to handle outer joins
1955 TABLE_LIST *tl;
1956 bool optimization_delayed= TRUE;
1957 TABLE_LIST *jtbm;
1958 LEX_STRING tbl_alias;
1959 THD *thd= parent_join->thd;
1960 DBUG_ENTER("convert_subq_to_jtbm");
1961
1962 subq_pred->set_strategy(SUBS_MATERIALIZATION);
1963 subq_pred->is_jtbm_merged= TRUE;
1964
1965 *remove_item= TRUE;
1966
1967 if (!(tbl_alias.str= (char*)thd->calloc(SUBQERY_TEMPTABLE_NAME_MAX_LEN)) ||
1968 !(jtbm= alloc_join_nest(thd))) //todo: this is not a join nest!
1969 {
1970 DBUG_RETURN(TRUE);
1971 }
1972
1973 jtbm->join_list= emb_join_list;
1974 jtbm->embedding= emb_tbl_nest;
1975 jtbm->jtbm_subselect= subq_pred;
1976 jtbm->nested_join= NULL;
1977
1978 /* Nests do not participate in those 'chains', so: */
1979 /* jtbm->next_leaf= jtbm->next_local= jtbm->next_global == NULL*/
1980 emb_join_list->push_back(jtbm, thd->mem_root);
1981
1982 /*
1983 Inject the jtbm table into TABLE_LIST::next_leaf list, so that
1984 make_join_statistics() and co. can find it.
1985 */
1986 parent_lex->leaf_tables.push_back(jtbm, thd->mem_root);
1987
1988 if (subq_pred->unit->first_select()->options & OPTION_SCHEMA_TABLE)
1989 parent_lex->options |= OPTION_SCHEMA_TABLE;
1990
1991 /*
1992 Same as above for TABLE_LIST::next_local chain
1993 (a theory: a next_local chain always starts with ::leaf_tables
1994 because view's tables are inserted after the view)
1995 */
1996 for (tl= (TABLE_LIST*)(parent_lex->table_list.first); tl->next_local; tl= tl->next_local)
1997 {}
1998 tl->next_local= jtbm;
1999
2000 /* A theory: no need to re-connect the next_global chain */
2001 if (optimization_delayed)
2002 {
2003 DBUG_ASSERT(parent_join->table_count < MAX_TABLES);
2004
2005 jtbm->jtbm_table_no= parent_join->table_count;
2006
2007 create_subquery_temptable_name(&tbl_alias,
2008 subq_pred->unit->first_select()->select_number);
2009 jtbm->alias.str= tbl_alias.str;
2010 jtbm->alias.length= tbl_alias.length;
2011 parent_join->table_count++;
2012 DBUG_RETURN(thd->is_fatal_error);
2013 }
2014 subselect_hash_sj_engine *hash_sj_engine=
2015 ((subselect_hash_sj_engine*)subq_pred->engine);
2016 jtbm->table= hash_sj_engine->tmp_table;
2017
2018 jtbm->table->tablenr= parent_join->table_count;
2019 jtbm->table->map= table_map(1) << (parent_join->table_count);
2020 jtbm->jtbm_table_no= jtbm->table->tablenr;
2021
2022 parent_join->table_count++;
2023 DBUG_ASSERT(parent_join->table_count < MAX_TABLES);
2024
2025 Item *conds= hash_sj_engine->semi_join_conds;
2026 conds->fix_after_pullout(parent_lex, &conds, TRUE);
2027
2028 DBUG_EXECUTE("where", print_where(conds,"SJ-EXPR", QT_ORDINARY););
2029
2030 create_subquery_temptable_name(&tbl_alias, hash_sj_engine->materialize_join->
2031 select_lex->select_number);
2032 jtbm->alias.str= tbl_alias.str;
2033 jtbm->alias.length= tbl_alias.length;
2034
2035 parent_lex->have_merged_subqueries= TRUE;
2036
2037 /* Don't unlink the child subselect, as the subquery will be used. */
2038
2039 DBUG_RETURN(thd->is_fatal_error);
2040 }
2041
2042
alloc_join_nest(THD * thd)2043 static TABLE_LIST *alloc_join_nest(THD *thd)
2044 {
2045 TABLE_LIST *tbl;
2046 if (!(tbl= (TABLE_LIST*) thd->calloc(ALIGN_SIZE(sizeof(TABLE_LIST))+
2047 sizeof(NESTED_JOIN))))
2048 return NULL;
2049 tbl->nested_join= (NESTED_JOIN*) ((uchar*)tbl +
2050 ALIGN_SIZE(sizeof(TABLE_LIST)));
2051 return tbl;
2052 }
2053
2054 /*
2055 @Note thd->is_fatal_error can be set in case of OOM
2056 */
2057
fix_list_after_tbl_changes(SELECT_LEX * new_parent,List<TABLE_LIST> * tlist)2058 void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist)
2059 {
2060 List_iterator<TABLE_LIST> it(*tlist);
2061 TABLE_LIST *table;
2062 while ((table= it++))
2063 {
2064 if (table->on_expr)
2065 table->on_expr->fix_after_pullout(new_parent, &table->on_expr, TRUE);
2066 if (table->nested_join)
2067 fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
2068 }
2069 }
2070
2071
set_emb_join_nest(List<TABLE_LIST> * tables,TABLE_LIST * emb_sj_nest)2072 static void set_emb_join_nest(List<TABLE_LIST> *tables, TABLE_LIST *emb_sj_nest)
2073 {
2074 List_iterator<TABLE_LIST> it(*tables);
2075 TABLE_LIST *tbl;
2076 while ((tbl= it++))
2077 {
2078 /*
2079 Note: check for nested_join first.
2080 derived-merged tables have tbl->table!=NULL &&
2081 tbl->table->reginfo==NULL.
2082 */
2083 if (tbl->nested_join)
2084 set_emb_join_nest(&tbl->nested_join->join_list, emb_sj_nest);
2085 else if (tbl->table)
2086 tbl->table->reginfo.join_tab->emb_sj_nest= emb_sj_nest;
2087
2088 }
2089 }
2090
2091 /*
2092 Pull tables out of semi-join nests, if possible
2093
2094 SYNOPSIS
2095 pull_out_semijoin_tables()
2096 join The join where to do the semi-join flattening
2097
2098 DESCRIPTION
2099 Try to pull tables out of semi-join nests.
2100
2101 PRECONDITIONS
2102 When this function is called, the join may have several semi-join nests
2103 but it is guaranteed that one semi-join nest does not contain another.
2104
2105 ACTION
2106 A table can be pulled out of the semi-join nest if
2107 - It is a constant table, or
2108 - It is accessed via eq_ref(outer_tables)
2109
2110 POSTCONDITIONS
2111 * Tables that were pulled out have JOIN_TAB::emb_sj_nest == NULL
2112 * Tables that were not pulled out have JOIN_TAB::emb_sj_nest pointing
2113 to semi-join nest they are in.
2114 * Semi-join nests' TABLE_LIST::sj_inner_tables is updated accordingly
2115
2116 This operation is (and should be) performed at each PS execution since
2117 tables may become/cease to be constant across PS reexecutions.
2118
2119 NOTE
2120 Table pullout may make uncorrelated subquery correlated. Consider this
2121 example:
2122
2123 ... WHERE oe IN (SELECT it1.primary_key WHERE p(it1, it2) ... )
2124
2125 here table it1 can be pulled out (we have it1.primary_key=oe which gives
2126 us functional dependency). Once it1 is pulled out, all references to it1
2127 from p(it1, it2) become references to outside of the subquery and thus
2128 make the subquery (i.e. its semi-join nest) correlated.
2129 Making the subquery (i.e. its semi-join nest) correlated prevents us from
2130 using Materialization or LooseScan to execute it.
2131
2132 RETURN
2133 0 - OK
2134 1 - Out of memory error
2135 */
2136
pull_out_semijoin_tables(JOIN * join)2137 int pull_out_semijoin_tables(JOIN *join)
2138 {
2139 TABLE_LIST *sj_nest;
2140 DBUG_ENTER("pull_out_semijoin_tables");
2141 List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
2142
2143 /* Try pulling out of the each of the semi-joins */
2144 while ((sj_nest= sj_list_it++))
2145 {
2146 List_iterator<TABLE_LIST> child_li(sj_nest->nested_join->join_list);
2147 TABLE_LIST *tbl;
2148
2149 /*
2150 Don't do table pull-out for nested joins (if we get nested joins here, it
2151 means these are outer joins. It is theoretically possible to do pull-out
2152 for some of the outer tables but we dont support this currently.
2153 */
2154 bool have_join_nest_children= FALSE;
2155
2156 set_emb_join_nest(&sj_nest->nested_join->join_list, sj_nest);
2157
2158 while ((tbl= child_li++))
2159 {
2160 if (tbl->nested_join)
2161 {
2162 have_join_nest_children= TRUE;
2163 break;
2164 }
2165 }
2166
2167 table_map pulled_tables= 0;
2168 table_map dep_tables= 0;
2169 if (have_join_nest_children)
2170 goto skip;
2171
2172 /*
2173 Calculate set of tables within this semi-join nest that have
2174 other dependent tables
2175 */
2176 child_li.rewind();
2177 while ((tbl= child_li++))
2178 {
2179 TABLE *const table= tbl->table;
2180 if (table &&
2181 (table->reginfo.join_tab->dependent &
2182 sj_nest->nested_join->used_tables))
2183 dep_tables|= table->reginfo.join_tab->dependent;
2184 }
2185
2186 /* Action #1: Mark the constant tables to be pulled out */
2187 child_li.rewind();
2188 while ((tbl= child_li++))
2189 {
2190 if (tbl->table)
2191 {
2192 tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
2193 #if 0
2194 /*
2195 Do not pull out tables because they are constant. This operation has
2196 a problem:
2197 - Some constant tables may become/cease to be constant across PS
2198 re-executions
2199 - Contrary to our initial assumption, it turned out that table pullout
2200 operation is not easily undoable.
2201
2202 The solution is to leave constant tables where they are. This will
2203 affect only constant tables that are 1-row or empty, tables that are
2204 constant because they are accessed via eq_ref(const) access will
2205 still be pulled out as functionally-dependent.
2206
2207 This will cause us to miss the chance to flatten some of the
2208 subqueries, but since const tables do not generate many duplicates,
2209 it really doesn't matter that much whether they were pulled out or
2210 not.
2211
2212 All of this was done as fix for BUG#43768.
2213 */
2214 if (tbl->table->map & join->const_table_map)
2215 {
2216 pulled_tables |= tbl->table->map;
2217 DBUG_PRINT("info", ("Table %s pulled out (reason: constant)",
2218 tbl->table->alias));
2219 }
2220 #endif
2221 }
2222 }
2223
2224 /*
2225 Action #2: Find which tables we can pull out based on
2226 update_ref_and_keys() data. Note that pulling one table out can allow
2227 us to pull out some other tables too.
2228 */
2229 bool pulled_a_table;
2230 do
2231 {
2232 pulled_a_table= FALSE;
2233 child_li.rewind();
2234 while ((tbl= child_li++))
2235 {
2236 if (tbl->table && !(pulled_tables & tbl->table->map) &&
2237 !(dep_tables & tbl->table->map))
2238 {
2239 if (find_eq_ref_candidate(tbl->table,
2240 sj_nest->nested_join->used_tables &
2241 ~pulled_tables))
2242 {
2243 pulled_a_table= TRUE;
2244 pulled_tables |= tbl->table->map;
2245 DBUG_PRINT("info", ("Table %s pulled out (reason: func dep)",
2246 tbl->table->alias.c_ptr()));
2247 /*
2248 Pulling a table out of uncorrelated subquery in general makes
2249 makes it correlated. See the NOTE to this funtion.
2250 */
2251 sj_nest->sj_subq_pred->is_correlated= TRUE;
2252 sj_nest->nested_join->sj_corr_tables|= tbl->table->map;
2253 sj_nest->nested_join->sj_depends_on|= tbl->table->map;
2254 }
2255 }
2256 }
2257 } while (pulled_a_table);
2258
2259 child_li.rewind();
2260 skip:
2261 /*
2262 Action #3: Move the pulled out TABLE_LIST elements to the parents.
2263 */
2264 table_map inner_tables= sj_nest->nested_join->used_tables &
2265 ~pulled_tables;
2266 /* Record the bitmap of inner tables */
2267 sj_nest->sj_inner_tables= inner_tables;
2268 if (pulled_tables)
2269 {
2270 List<TABLE_LIST> *upper_join_list= (sj_nest->embedding != NULL)?
2271 (&sj_nest->embedding->nested_join->join_list):
2272 (&join->select_lex->top_join_list);
2273 Query_arena *arena, backup;
2274 arena= join->thd->activate_stmt_arena_if_needed(&backup);
2275 while ((tbl= child_li++))
2276 {
2277 if (tbl->table)
2278 {
2279 if (inner_tables & tbl->table->map)
2280 {
2281 /* This table is not pulled out */
2282 tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
2283 }
2284 else
2285 {
2286 /* This table has been pulled out of the semi-join nest */
2287 tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
2288 /*
2289 Pull the table up in the same way as simplify_joins() does:
2290 update join_list and embedding pointers but keep next[_local]
2291 pointers.
2292 */
2293 child_li.remove();
2294 sj_nest->nested_join->used_tables &= ~tbl->table->map;
2295 upper_join_list->push_back(tbl, join->thd->mem_root);
2296 tbl->join_list= upper_join_list;
2297 tbl->embedding= sj_nest->embedding;
2298 }
2299 }
2300 }
2301
2302 /* Remove the sj-nest itself if we've removed everything from it */
2303 if (!inner_tables)
2304 {
2305 List_iterator<TABLE_LIST> li(*upper_join_list);
2306 /* Find the sj_nest in the list. */
2307 while (sj_nest != li++) ;
2308 li.remove();
2309 /* Also remove it from the list of SJ-nests: */
2310 sj_list_it.remove();
2311 }
2312
2313 if (arena)
2314 join->thd->restore_active_arena(arena, &backup);
2315 }
2316 }
2317 DBUG_RETURN(0);
2318 }
2319
2320
2321 /*
2322 Optimize semi-join nests that could be run with sj-materialization
2323
2324 SYNOPSIS
2325 optimize_semijoin_nests()
2326 join The join to optimize semi-join nests for
2327 all_table_map Bitmap of all tables in the join
2328
2329 DESCRIPTION
2330 Optimize each of the semi-join nests that can be run with
2331 materialization. For each of the nests, we
2332 - Generate the best join order for this "sub-join" and remember it;
2333 - Remember the sub-join execution cost (it's part of materialization
2334 cost);
2335 - Calculate other costs that will be incurred if we decide
2336 to use materialization strategy for this semi-join nest.
2337
2338 All obtained information is saved and will be used by the main join
2339 optimization pass.
2340
2341 NOTES
2342 Because of Join::reoptimize(), this function may be called multiple times.
2343
2344 RETURN
2345 FALSE Ok
2346 TRUE Out of memory error
2347 */
2348
optimize_semijoin_nests(JOIN * join,table_map all_table_map)2349 bool optimize_semijoin_nests(JOIN *join, table_map all_table_map)
2350 {
2351 DBUG_ENTER("optimize_semijoin_nests");
2352 List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
2353 TABLE_LIST *sj_nest;
2354 while ((sj_nest= sj_list_it++))
2355 {
2356 /* semi-join nests with only constant tables are not valid */
2357 /// DBUG_ASSERT(sj_nest->sj_inner_tables & ~join->const_table_map);
2358
2359 sj_nest->sj_mat_info= NULL;
2360 /*
2361 The statement may have been executed with 'semijoin=on' earlier.
2362 We need to verify that 'semijoin=on' still holds.
2363 */
2364 if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
2365 optimizer_flag(join->thd, OPTIMIZER_SWITCH_MATERIALIZATION))
2366 {
2367 if ((sj_nest->sj_inner_tables & ~join->const_table_map) && /* not everything was pulled out */
2368 !sj_nest->sj_subq_pred->is_correlated &&
2369 sj_nest->sj_subq_pred->types_allow_materialization)
2370 {
2371 join->emb_sjm_nest= sj_nest;
2372 if (choose_plan(join, all_table_map &~join->const_table_map))
2373 DBUG_RETURN(TRUE); /* purecov: inspected */
2374 /*
2375 The best plan to run the subquery is now in join->best_positions,
2376 save it.
2377 */
2378 uint n_tables= my_count_bits(sj_nest->sj_inner_tables & ~join->const_table_map);
2379 SJ_MATERIALIZATION_INFO* sjm;
2380 if (!(sjm= new SJ_MATERIALIZATION_INFO) ||
2381 !(sjm->positions= (POSITION*)join->thd->alloc(sizeof(POSITION)*
2382 n_tables)))
2383 DBUG_RETURN(TRUE); /* purecov: inspected */
2384 sjm->tables= n_tables;
2385 sjm->is_used= FALSE;
2386 double subjoin_out_rows, subjoin_read_time;
2387
2388 /*
2389 join->get_partial_cost_and_fanout(n_tables + join->const_tables,
2390 table_map(-1),
2391 &subjoin_read_time,
2392 &subjoin_out_rows);
2393 */
2394 join->get_prefix_cost_and_fanout(n_tables,
2395 &subjoin_read_time,
2396 &subjoin_out_rows);
2397
2398 sjm->materialization_cost.convert_from_cost(subjoin_read_time);
2399 sjm->rows_with_duplicates= sjm->rows= subjoin_out_rows;
2400
2401 // Don't use the following list because it has "stale" items. use
2402 // ref_pointer_array instead:
2403 //
2404 //List<Item> &right_expr_list=
2405 // sj_nest->sj_subq_pred->unit->first_select()->item_list;
2406 /*
2407 Adjust output cardinality estimates. If the subquery has form
2408
2409 ... oe IN (SELECT t1.colX, t2.colY, func(X,Y,Z) )
2410
2411 then the number of distinct output record combinations has an
2412 upper bound of product of number of records matching the tables
2413 that are used by the SELECT clause.
2414 TODO:
2415 We can get a more precise estimate if we
2416 - use rec_per_key cardinality estimates. For simple cases like
2417 "oe IN (SELECT t.key ...)" it is trivial.
2418 - Functional dependencies between the tables in the semi-join
2419 nest (the payoff is probably less here?)
2420
2421 See also get_post_group_estimate().
2422 */
2423 SELECT_LEX *subq_select= sj_nest->sj_subq_pred->unit->first_select();
2424 {
2425 for (uint i=0 ; i < join->const_tables + sjm->tables ; i++)
2426 {
2427 JOIN_TAB *tab= join->best_positions[i].table;
2428 join->map2table[tab->table->tablenr]= tab;
2429 }
2430 table_map map= 0;
2431 for (uint i=0; i < subq_select->item_list.elements; i++)
2432 map|= subq_select->ref_pointer_array[i]->used_tables();
2433 map= map & ~PSEUDO_TABLE_BITS;
2434 Table_map_iterator tm_it(map);
2435 int tableno;
2436 double rows= 1.0;
2437 while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
2438 rows= COST_MULT(rows,
2439 join->map2table[tableno]->table->quick_condition_rows);
2440 sjm->rows= MY_MIN(sjm->rows, rows);
2441 }
2442 memcpy((uchar*) sjm->positions,
2443 (uchar*) (join->best_positions + join->const_tables),
2444 sizeof(POSITION) * n_tables);
2445
2446 /*
2447 Calculate temporary table parameters and usage costs
2448 */
2449 uint rowlen= get_tmp_table_rec_length(subq_select->ref_pointer_array,
2450 subq_select->item_list.elements);
2451 double lookup_cost= get_tmp_table_lookup_cost(join->thd,
2452 subjoin_out_rows, rowlen);
2453 double write_cost= get_tmp_table_write_cost(join->thd,
2454 subjoin_out_rows, rowlen);
2455
2456 /*
2457 Let materialization cost include the cost to write the data into the
2458 temporary table:
2459 */
2460 sjm->materialization_cost.add_io(subjoin_out_rows, write_cost);
2461
2462 /*
2463 Set the cost to do a full scan of the temptable (will need this to
2464 consider doing sjm-scan):
2465 */
2466 sjm->scan_cost.reset();
2467 sjm->scan_cost.add_io(sjm->rows, lookup_cost);
2468
2469 sjm->lookup_cost.convert_from_cost(lookup_cost);
2470 sj_nest->sj_mat_info= sjm;
2471 DBUG_EXECUTE("opt", print_sjm(sjm););
2472 }
2473 }
2474 }
2475 join->emb_sjm_nest= NULL;
2476 DBUG_RETURN(FALSE);
2477 }
2478
2479
2480 /*
2481 Get estimated record length for semi-join materialization temptable
2482
2483 SYNOPSIS
2484 get_tmp_table_rec_length()
2485 items IN subquery's select list.
2486
2487 DESCRIPTION
2488 Calculate estimated record length for semi-join materialization
2489 temptable. It's an estimate because we don't follow every bit of
2490 create_tmp_table()'s logic. This isn't necessary as the return value of
2491 this function is used only for cost calculations.
2492
2493 RETURN
2494 Length of the temptable record, in bytes
2495 */
2496
get_tmp_table_rec_length(Ref_ptr_array p_items,uint elements)2497 static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements)
2498 {
2499 uint len= 0;
2500 Item *item;
2501 //List_iterator<Item> it(items);
2502 for (uint i= 0; i < elements ; i++)
2503 {
2504 item = p_items[i];
2505 switch (item->result_type()) {
2506 case REAL_RESULT:
2507 len += sizeof(double);
2508 break;
2509 case INT_RESULT:
2510 if (item->max_length >= (MY_INT32_NUM_DECIMAL_DIGITS - 1))
2511 len += 8;
2512 else
2513 len += 4;
2514 break;
2515 case STRING_RESULT:
2516 enum enum_field_types type;
2517 /* DATE/TIME and GEOMETRY fields have STRING_RESULT result type. */
2518 if ((type= item->field_type()) == MYSQL_TYPE_DATETIME ||
2519 type == MYSQL_TYPE_TIME || type == MYSQL_TYPE_DATE ||
2520 type == MYSQL_TYPE_TIMESTAMP || type == MYSQL_TYPE_GEOMETRY)
2521 len += 8;
2522 else
2523 len += item->max_length;
2524 break;
2525 case DECIMAL_RESULT:
2526 len += 10;
2527 break;
2528 case ROW_RESULT:
2529 default:
2530 DBUG_ASSERT(0); /* purecov: deadcode */
2531 break;
2532 }
2533 }
2534 return len;
2535 }
2536
2537
2538 /**
2539 The cost of a lookup into a unique hash/btree index on a temporary table
2540 with 'row_count' rows each of size 'row_size'.
2541
2542 @param thd current query context
2543 @param row_count number of rows in the temp table
2544 @param row_size average size in bytes of the rows
2545
2546 @return the cost of one lookup
2547 */
2548
2549 double
get_tmp_table_lookup_cost(THD * thd,double row_count,uint row_size)2550 get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size)
2551 {
2552 if (row_count > thd->variables.max_heap_table_size / (double) row_size)
2553 return (double) DISK_TEMPTABLE_LOOKUP_COST;
2554 else
2555 return (double) HEAP_TEMPTABLE_LOOKUP_COST;
2556 }
2557
2558 /**
2559 The cost of writing a row into a temporary table with 'row_count' unique
2560 rows each of size 'row_size'.
2561
2562 @param thd current query context
2563 @param row_count number of rows in the temp table
2564 @param row_size average size in bytes of the rows
2565
2566 @return the cost of writing one row
2567 */
2568
2569 double
get_tmp_table_write_cost(THD * thd,double row_count,uint row_size)2570 get_tmp_table_write_cost(THD *thd, double row_count, uint row_size)
2571 {
2572 double lookup_cost= get_tmp_table_lookup_cost(thd, row_count, row_size);
2573 /*
2574 TODO:
2575 This is an optimistic estimate. Add additional costs resulting from
2576 actually writing the row to memory/disk and possible index reorganization.
2577 */
2578 return lookup_cost;
2579 }
2580
2581
2582 /*
2583 Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
2584
2585 SYNOPSIS
2586 find_eq_ref_candidate()
2587 table Table to be checked
2588 sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
2589 count.
2590
2591 DESCRIPTION
2592 Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
2593
2594 TODO
2595 Check again if it is feasible to factor common parts with constant table
2596 search
2597
2598 Also check if it's feasible to factor common parts with table elimination
2599
2600 RETURN
2601 TRUE - There exists an eq_ref(outer-tables) candidate
2602 FALSE - Otherwise
2603 */
2604
find_eq_ref_candidate(TABLE * table,table_map sj_inner_tables)2605 bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables)
2606 {
2607 KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
2608
2609 if (keyuse)
2610 {
2611 do
2612 {
2613 uint key= keyuse->key;
2614 key_part_map bound_parts= 0;
2615 if (!keyuse->is_for_hash_join() &&
2616 (table->key_info[key].flags & HA_NOSAME))
2617 {
2618 KEY *keyinfo= table->key_info + key;
2619 do /* For all equalities on all key parts */
2620 {
2621 /*
2622 Check if this is "t.keypart = expr(outer_tables)
2623
2624 Don't allow variants that can produce duplicates:
2625 - Dont allow "ref or null"
2626 - the keyuse (that is, the operation) must be null-rejecting,
2627 unless the other expression is non-NULLable.
2628 */
2629 if (!(keyuse->used_tables & sj_inner_tables) &&
2630 !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) &&
2631 (keyuse->null_rejecting || !keyuse->val->maybe_null))
2632 {
2633 bound_parts |= 1 << keyuse->keypart;
2634 }
2635 keyuse++;
2636 } while (keyuse->key == key && keyuse->table == table);
2637
2638 if (bound_parts == PREV_BITS(uint, keyinfo->user_defined_key_parts))
2639 return TRUE;
2640 }
2641 else
2642 {
2643 do
2644 {
2645 keyuse++;
2646 } while (keyuse->key == key && keyuse->table == table);
2647 }
2648 } while (keyuse->table == table);
2649 }
2650 return FALSE;
2651 }
2652
2653
2654 /*
2655 Do semi-join optimization step after we've added a new tab to join prefix
2656
2657 SYNOPSIS
2658 advance_sj_state()
2659 join The join we're optimizing
2660 remaining_tables Tables not in the join prefix
2661 new_join_tab Join tab we've just added to the join prefix
2662 idx Index of this join tab (i.e. number of tables
2663 in the prefix minus one)
2664 current_record_count INOUT Estimate of #records in join prefix's output
2665 current_read_time INOUT Cost to execute the join prefix
2666 loose_scan_pos IN A POSITION with LooseScan plan to access
2667 table new_join_tab
2668 (produced by the last best_access_path call)
2669
2670 DESCRIPTION
2671 Update semi-join optimization state after we've added another tab (table
2672 and access method) to the join prefix.
2673
2674 The state is maintained in join->positions[#prefix_size]. Each of the
2675 available strategies has its own state variables.
2676
2677 for each semi-join strategy
2678 {
2679 update strategy's state variables;
2680
2681 if (join prefix has all the tables that are needed to consider
2682 using this strategy for the semi-join(s))
2683 {
2684 calculate cost of using the strategy
2685 if ((this is the first strategy to handle the semi-join nest(s) ||
2686 the cost is less than other strategies))
2687 {
2688 // Pick this strategy
2689 pos->sj_strategy= ..
2690 ..
2691 }
2692 }
2693
2694 Most of the new state is saved join->positions[idx] (and hence no undo
2695 is necessary). Several members of class JOIN are updated also, these
2696 changes can be rolled back with restore_prev_sj_state().
2697
2698 See setup_semijoin_dups_elimination() for a description of what kinds of
2699 join prefixes each strategy can handle.
2700 */
2701
is_multiple_semi_joins(JOIN * join,POSITION * prefix,uint idx,table_map inner_tables)2702 bool is_multiple_semi_joins(JOIN *join, POSITION *prefix, uint idx, table_map inner_tables)
2703 {
2704 for (int i= (int)idx; i >= 0; i--)
2705 {
2706 TABLE_LIST *emb_sj_nest;
2707 if ((emb_sj_nest= prefix[i].table->emb_sj_nest))
2708 {
2709 if (inner_tables & emb_sj_nest->sj_inner_tables)
2710 return !MY_TEST(inner_tables == (emb_sj_nest->sj_inner_tables &
2711 ~join->const_table_map));
2712 }
2713 }
2714 return FALSE;
2715 }
2716
2717
advance_sj_state(JOIN * join,table_map remaining_tables,uint idx,double * current_record_count,double * current_read_time,POSITION * loose_scan_pos)2718 void advance_sj_state(JOIN *join, table_map remaining_tables, uint idx,
2719 double *current_record_count, double *current_read_time,
2720 POSITION *loose_scan_pos)
2721 {
2722 POSITION *pos= join->positions + idx;
2723 const JOIN_TAB *new_join_tab= pos->table;
2724 Semi_join_strategy_picker *pickers[]=
2725 {
2726 &pos->firstmatch_picker,
2727 &pos->loosescan_picker,
2728 &pos->sjmat_picker,
2729 &pos->dups_weedout_picker,
2730 NULL,
2731 };
2732
2733 #ifdef HAVE_valgrind
2734 new (&pos->firstmatch_picker) Firstmatch_picker;
2735 new (&pos->loosescan_picker) LooseScan_picker;
2736 new (&pos->sjmat_picker) Sj_materialization_picker;
2737 new (&pos->dups_weedout_picker) Duplicate_weedout_picker;
2738 #endif
2739
2740 if (join->emb_sjm_nest)
2741 {
2742 /*
2743 We're performing optimization inside SJ-Materialization nest:
2744 - there are no other semi-joins inside semi-join nests
2745 - attempts to build semi-join strategies here will confuse
2746 the optimizer, so bail out.
2747 */
2748 pos->sj_strategy= SJ_OPT_NONE;
2749 return;
2750 }
2751
2752 /*
2753 Update join->cur_sj_inner_tables (Used by FirstMatch in this function and
2754 LooseScan detector in best_access_path)
2755 */
2756 remaining_tables &= ~new_join_tab->table->map;
2757 table_map dups_producing_tables, UNINIT_VAR(prev_dups_producing_tables),
2758 UNINIT_VAR(prev_sjm_lookup_tables);
2759
2760 if (idx == join->const_tables)
2761 dups_producing_tables= 0;
2762 else
2763 dups_producing_tables= pos[-1].dups_producing_tables;
2764
2765 TABLE_LIST *emb_sj_nest;
2766 if ((emb_sj_nest= new_join_tab->emb_sj_nest))
2767 dups_producing_tables |= emb_sj_nest->sj_inner_tables;
2768
2769 Semi_join_strategy_picker **strategy, **prev_strategy= 0;
2770 if (idx == join->const_tables)
2771 {
2772 /* First table, initialize pickers */
2773 for (strategy= pickers; *strategy != NULL; strategy++)
2774 (*strategy)->set_empty();
2775 pos->inner_tables_handled_with_other_sjs= 0;
2776 }
2777 else
2778 {
2779 for (strategy= pickers; *strategy != NULL; strategy++)
2780 {
2781 (*strategy)->set_from_prev(pos - 1);
2782 }
2783 pos->inner_tables_handled_with_other_sjs=
2784 pos[-1].inner_tables_handled_with_other_sjs;
2785 }
2786
2787 pos->prefix_cost.convert_from_cost(*current_read_time);
2788 pos->prefix_record_count= *current_record_count;
2789
2790 {
2791 pos->sj_strategy= SJ_OPT_NONE;
2792
2793 for (strategy= pickers; *strategy != NULL; strategy++)
2794 {
2795 table_map handled_fanout;
2796 sj_strategy_enum sj_strategy;
2797 double rec_count= *current_record_count;
2798 double read_time= *current_read_time;
2799 if ((*strategy)->check_qep(join, idx, remaining_tables,
2800 new_join_tab,
2801 &rec_count,
2802 &read_time,
2803 &handled_fanout,
2804 &sj_strategy,
2805 loose_scan_pos))
2806 {
2807 /*
2808 It's possible to use the strategy. Use it, if
2809 - it removes semi-join fanout that was not removed before
2810 - using it is cheaper than using something else,
2811 and {if some other strategy has removed fanout
2812 that this strategy is trying to remove, then it
2813 did remove the fanout only for one semi-join}
2814 This is to avoid a situation when
2815 1. strategy X removes fanout for semijoin X,Y
2816 2. using strategy Z is cheaper, but it only removes
2817 fanout from semijoin X.
2818 3. We have no clue what to do about fanount of semi-join Y.
2819 */
2820 if ((dups_producing_tables & handled_fanout) ||
2821 (read_time < *current_read_time &&
2822 !(handled_fanout & pos->inner_tables_handled_with_other_sjs)))
2823 {
2824 DBUG_ASSERT(pos->sj_strategy != sj_strategy);
2825 /*
2826 If the strategy choosen first time or
2827 the strategy replace strategy which was used to exectly the same
2828 tables
2829 */
2830 if (pos->sj_strategy == SJ_OPT_NONE ||
2831 handled_fanout ==
2832 (prev_dups_producing_tables ^ dups_producing_tables))
2833 {
2834 prev_strategy= strategy;
2835 if (pos->sj_strategy == SJ_OPT_NONE)
2836 {
2837 prev_dups_producing_tables= dups_producing_tables;
2838 prev_sjm_lookup_tables= join->sjm_lookup_tables;
2839 }
2840 /* Mark strategy as used */
2841 (*strategy)->mark_used();
2842 pos->sj_strategy= sj_strategy;
2843 if (sj_strategy == SJ_OPT_MATERIALIZE)
2844 join->sjm_lookup_tables |= handled_fanout;
2845 else
2846 join->sjm_lookup_tables &= ~handled_fanout;
2847 *current_read_time= read_time;
2848 *current_record_count= rec_count;
2849 dups_producing_tables &= ~handled_fanout;
2850 //TODO: update bitmap of semi-joins that were handled together with
2851 // others.
2852 if (is_multiple_semi_joins(join, join->positions, idx,
2853 handled_fanout))
2854 pos->inner_tables_handled_with_other_sjs |= handled_fanout;
2855 }
2856 else
2857 {
2858 /* Conflict fall to most general variant */
2859 (*prev_strategy)->set_empty();
2860 dups_producing_tables= prev_dups_producing_tables;
2861 join->sjm_lookup_tables= prev_sjm_lookup_tables;
2862 // mark it 'none' to avpoid loops
2863 pos->sj_strategy= SJ_OPT_NONE;
2864 // next skip to last;
2865 strategy= pickers +
2866 (sizeof(pickers)/sizeof(Semi_join_strategy_picker*) - 3);
2867 continue;
2868 }
2869 }
2870 else
2871 {
2872 /* We decided not to apply the strategy. */
2873 (*strategy)->set_empty();
2874 }
2875 }
2876 }
2877 }
2878
2879 if ((emb_sj_nest= new_join_tab->emb_sj_nest))
2880 {
2881 join->cur_sj_inner_tables |= emb_sj_nest->sj_inner_tables;
2882
2883 /* Remove the sj_nest if all of its SJ-inner tables are in cur_table_map */
2884 if (!(remaining_tables &
2885 emb_sj_nest->sj_inner_tables & ~new_join_tab->table->map))
2886 join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
2887 }
2888
2889 pos->prefix_cost.convert_from_cost(*current_read_time);
2890 pos->prefix_record_count= *current_record_count;
2891 pos->dups_producing_tables= dups_producing_tables;
2892 }
2893
2894
set_from_prev(struct st_position * prev)2895 void Sj_materialization_picker::set_from_prev(struct st_position *prev)
2896 {
2897 if (prev->sjmat_picker.is_used)
2898 set_empty();
2899 else
2900 {
2901 sjm_scan_need_tables= prev->sjmat_picker.sjm_scan_need_tables;
2902 sjm_scan_last_inner= prev->sjmat_picker.sjm_scan_last_inner;
2903 }
2904 is_used= FALSE;
2905 }
2906
2907
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)2908 bool Sj_materialization_picker::check_qep(JOIN *join,
2909 uint idx,
2910 table_map remaining_tables,
2911 const JOIN_TAB *new_join_tab,
2912 double *record_count,
2913 double *read_time,
2914 table_map *handled_fanout,
2915 sj_strategy_enum *strategy,
2916 POSITION *loose_scan_pos)
2917 {
2918 bool sjm_scan;
2919 SJ_MATERIALIZATION_INFO *mat_info;
2920 if ((mat_info= at_sjmat_pos(join, remaining_tables,
2921 new_join_tab, idx, &sjm_scan)))
2922 {
2923 if (sjm_scan)
2924 {
2925 /*
2926 We can't yet evaluate this option yet. This is because we can't
2927 accout for fanout of sj-inner tables yet:
2928
2929 ntX SJM-SCAN(it1 ... itN) | ot1 ... otN |
2930 ^(1) ^(2)
2931
2932 we're now at position (1). SJM temptable in general has multiple
2933 records, so at point (1) we'll get the fanout from sj-inner tables (ie
2934 there will be multiple record combinations).
2935
2936 The final join result will not contain any semi-join produced
2937 fanout, i.e. tables within SJM-SCAN(...) will not contribute to
2938 the cardinality of the join output. Extra fanout produced by
2939 SJM-SCAN(...) will be 'absorbed' into fanout produced by ot1 ... otN.
2940
2941 The simple way to model this is to remove SJM-SCAN(...) fanout once
2942 we reach the point #2.
2943 */
2944 sjm_scan_need_tables=
2945 new_join_tab->emb_sj_nest->sj_inner_tables |
2946 new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
2947 new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
2948 sjm_scan_last_inner= idx;
2949 }
2950 else
2951 {
2952 /* This is SJ-Materialization with lookups */
2953 Cost_estimate prefix_cost;
2954 signed int first_tab= (int)idx - mat_info->tables;
2955 double prefix_rec_count;
2956 if (first_tab < (int)join->const_tables)
2957 {
2958 prefix_cost.reset();
2959 prefix_rec_count= 1.0;
2960 }
2961 else
2962 {
2963 prefix_cost= join->positions[first_tab].prefix_cost;
2964 prefix_rec_count= join->positions[first_tab].prefix_record_count;
2965 }
2966
2967 double mat_read_time= prefix_cost.total_cost();
2968 mat_read_time=
2969 COST_ADD(mat_read_time,
2970 COST_ADD(mat_info->materialization_cost.total_cost(),
2971 COST_MULT(prefix_rec_count,
2972 mat_info->lookup_cost.total_cost())));
2973
2974 /*
2975 NOTE: When we pick to use SJM[-Scan] we don't memcpy its POSITION
2976 elements to join->positions as that makes it hard to return things
2977 back when making one step back in join optimization. That's done
2978 after the QEP has been chosen.
2979 */
2980 *read_time= mat_read_time;
2981 *record_count= prefix_rec_count;
2982 *handled_fanout= new_join_tab->emb_sj_nest->sj_inner_tables;
2983 *strategy= SJ_OPT_MATERIALIZE;
2984 return TRUE;
2985 }
2986 }
2987
2988 /* 4.A SJM-Scan second phase check */
2989 if (sjm_scan_need_tables && /* Have SJM-Scan prefix */
2990 !(sjm_scan_need_tables & remaining_tables))
2991 {
2992 TABLE_LIST *mat_nest=
2993 join->positions[sjm_scan_last_inner].table->emb_sj_nest;
2994 SJ_MATERIALIZATION_INFO *mat_info= mat_nest->sj_mat_info;
2995
2996 double prefix_cost;
2997 double prefix_rec_count;
2998 int first_tab= sjm_scan_last_inner + 1 - mat_info->tables;
2999 /* Get the prefix cost */
3000 if (first_tab == (int)join->const_tables)
3001 {
3002 prefix_rec_count= 1.0;
3003 prefix_cost= 0.0;
3004 }
3005 else
3006 {
3007 prefix_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
3008 prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
3009 }
3010
3011 /* Add materialization cost */
3012 prefix_cost=
3013 COST_ADD(prefix_cost,
3014 COST_ADD(mat_info->materialization_cost.total_cost(),
3015 COST_MULT(prefix_rec_count,
3016 mat_info->scan_cost.total_cost())));
3017 prefix_rec_count= COST_MULT(prefix_rec_count, mat_info->rows);
3018
3019 uint i;
3020 table_map rem_tables= remaining_tables;
3021 for (i= idx; i != (first_tab + mat_info->tables - 1); i--)
3022 rem_tables |= join->positions[i].table->table->map;
3023
3024 POSITION curpos, dummy;
3025 /* Need to re-run best-access-path as we prefix_rec_count has changed */
3026 bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
3027 for (i= first_tab + mat_info->tables; i <= idx; i++)
3028 {
3029 best_access_path(join, join->positions[i].table, rem_tables,
3030 join->positions, i,
3031 disable_jbuf, prefix_rec_count, &curpos, &dummy);
3032 prefix_rec_count= COST_MULT(prefix_rec_count, curpos.records_read);
3033 prefix_cost= COST_ADD(prefix_cost, curpos.read_time);
3034 prefix_cost= COST_ADD(prefix_cost,
3035 prefix_rec_count / (double) TIME_FOR_COMPARE);
3036 //TODO: take into account join condition selectivity here
3037 }
3038
3039 *strategy= SJ_OPT_MATERIALIZE_SCAN;
3040 *read_time= prefix_cost;
3041 /*
3042 Note: the next line means we did not remove the subquery's fanout from
3043 *record_count. It needs to be removed, as the join prefix is
3044
3045 ntX SJM-SCAN(it1 ... itN) | (ot1 ... otN) ...
3046
3047 here, the SJM-SCAN may have introduced subquery's fanout (duplicate rows,
3048 rows that don't have matches in ot1_i). All this fanout is gone after
3049 table otN (or earlier) but taking it into account is hard.
3050
3051 Some consolation here is that SJM-Scan strategy is applicable when the
3052 subquery is smaller than tables otX. If the subquery has large cardinality,
3053 we can greatly overestimate *record_count here, but it doesn't matter as
3054 SJ-Materialization-Lookup is a better strategy anyway.
3055 */
3056 *record_count= prefix_rec_count;
3057 *handled_fanout= mat_nest->sj_inner_tables;
3058 return TRUE;
3059 }
3060 return FALSE;
3061 }
3062
3063
set_from_prev(struct st_position * prev)3064 void LooseScan_picker::set_from_prev(struct st_position *prev)
3065 {
3066 if (prev->loosescan_picker.is_used)
3067 set_empty();
3068 else
3069 {
3070 first_loosescan_table= prev->loosescan_picker.first_loosescan_table;
3071 loosescan_need_tables= prev->loosescan_picker.loosescan_need_tables;
3072 }
3073 is_used= FALSE;
3074 }
3075
3076
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,struct st_position * loose_scan_pos)3077 bool LooseScan_picker::check_qep(JOIN *join,
3078 uint idx,
3079 table_map remaining_tables,
3080 const JOIN_TAB *new_join_tab,
3081 double *record_count,
3082 double *read_time,
3083 table_map *handled_fanout,
3084 sj_strategy_enum *strategy,
3085 struct st_position *loose_scan_pos)
3086 {
3087 POSITION *first= join->positions + first_loosescan_table;
3088 /*
3089 LooseScan strategy can't handle interleaving between tables from the
3090 semi-join that LooseScan is handling and any other tables.
3091
3092 If we were considering LooseScan for the join prefix (1)
3093 and the table we're adding creates an interleaving (2)
3094 then
3095 stop considering loose scan
3096 */
3097 if ((first_loosescan_table != MAX_TABLES) && // (1)
3098 (first->table->emb_sj_nest->sj_inner_tables & remaining_tables) && //(2)
3099 new_join_tab->emb_sj_nest != first->table->emb_sj_nest) //(2)
3100 {
3101 first_loosescan_table= MAX_TABLES;
3102 }
3103
3104 /*
3105 If we got an option to use LooseScan for the current table, start
3106 considering using LooseScan strategy
3107 */
3108 if (loose_scan_pos->read_time != DBL_MAX && !join->outer_join)
3109 {
3110 first_loosescan_table= idx;
3111 loosescan_need_tables=
3112 new_join_tab->emb_sj_nest->sj_inner_tables |
3113 new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
3114 new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
3115 }
3116
3117 if ((first_loosescan_table != MAX_TABLES) &&
3118 !(remaining_tables & loosescan_need_tables) &&
3119 (new_join_tab->table->map & loosescan_need_tables))
3120 {
3121 /*
3122 Ok we have LooseScan plan and also have all LooseScan sj-nest's
3123 inner tables and outer correlated tables into the prefix.
3124 */
3125
3126 first= join->positions + first_loosescan_table;
3127 uint n_tables= my_count_bits(first->table->emb_sj_nest->sj_inner_tables);
3128 /* Got a complete LooseScan range. Calculate its cost */
3129 /*
3130 The same problem as with FirstMatch - we need to save POSITIONs
3131 somewhere but reserving space for all cases would require too
3132 much space. We will re-calculate POSITION structures later on.
3133 */
3134 bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
3135 optimize_wo_join_buffering(join, first_loosescan_table, idx,
3136 remaining_tables,
3137 TRUE, //first_alt
3138 disable_jbuf ? join->table_count :
3139 first_loosescan_table + n_tables,
3140 record_count,
3141 read_time);
3142 /*
3143 We don't yet have any other strategies that could handle this
3144 semi-join nest (the other options are Duplicate Elimination or
3145 Materialization, which need at least the same set of tables in
3146 the join prefix to be considered) so unconditionally pick the
3147 LooseScan.
3148 */
3149 *strategy= SJ_OPT_LOOSE_SCAN;
3150 *handled_fanout= first->table->emb_sj_nest->sj_inner_tables;
3151 return TRUE;
3152 }
3153 return FALSE;
3154 }
3155
set_from_prev(struct st_position * prev)3156 void Firstmatch_picker::set_from_prev(struct st_position *prev)
3157 {
3158 if (prev->firstmatch_picker.is_used)
3159 invalidate_firstmatch_prefix();
3160 else
3161 {
3162 first_firstmatch_table= prev->firstmatch_picker.first_firstmatch_table;
3163 first_firstmatch_rtbl= prev->firstmatch_picker.first_firstmatch_rtbl;
3164 firstmatch_need_tables= prev->firstmatch_picker.firstmatch_need_tables;
3165 }
3166 is_used= FALSE;
3167 }
3168
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)3169 bool Firstmatch_picker::check_qep(JOIN *join,
3170 uint idx,
3171 table_map remaining_tables,
3172 const JOIN_TAB *new_join_tab,
3173 double *record_count,
3174 double *read_time,
3175 table_map *handled_fanout,
3176 sj_strategy_enum *strategy,
3177 POSITION *loose_scan_pos)
3178 {
3179 if (new_join_tab->emb_sj_nest &&
3180 optimizer_flag(join->thd, OPTIMIZER_SWITCH_FIRSTMATCH) &&
3181 !join->outer_join)
3182 {
3183 const table_map outer_corr_tables=
3184 new_join_tab->emb_sj_nest->nested_join->sj_corr_tables |
3185 new_join_tab->emb_sj_nest->nested_join->sj_depends_on;
3186 const table_map sj_inner_tables=
3187 new_join_tab->emb_sj_nest->sj_inner_tables & ~join->const_table_map;
3188
3189 /*
3190 Enter condition:
3191 1. The next join tab belongs to semi-join nest
3192 (verified for the encompassing code block above).
3193 2. We're not in a duplicate producer range yet
3194 3. All outer tables that
3195 - the subquery is correlated with, or
3196 - referred to from the outer_expr
3197 are in the join prefix
3198 4. All inner tables are still part of remaining_tables.
3199 */
3200 if (!join->cur_sj_inner_tables && // (2)
3201 !(remaining_tables & outer_corr_tables) && // (3)
3202 (sj_inner_tables == // (4)
3203 ((remaining_tables | new_join_tab->table->map) & sj_inner_tables)))
3204 {
3205 /* Start tracking potential FirstMatch range */
3206 first_firstmatch_table= idx;
3207 firstmatch_need_tables= sj_inner_tables;
3208 first_firstmatch_rtbl= remaining_tables;
3209 }
3210
3211 if (in_firstmatch_prefix())
3212 {
3213 if (outer_corr_tables & first_firstmatch_rtbl)
3214 {
3215 /*
3216 Trying to add an sj-inner table whose sj-nest has an outer correlated
3217 table that was not in the prefix. This means FirstMatch can't be used.
3218 */
3219 invalidate_firstmatch_prefix();
3220 }
3221 else
3222 {
3223 /* Record that we need all of this semi-join's inner tables, too */
3224 firstmatch_need_tables|= sj_inner_tables;
3225 }
3226
3227 if (in_firstmatch_prefix() &&
3228 !(firstmatch_need_tables & remaining_tables))
3229 {
3230 /*
3231 Got a complete FirstMatch range. Calculate correct costs and fanout
3232 */
3233
3234 if (idx == first_firstmatch_table &&
3235 optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN_WITH_CACHE))
3236 {
3237 /*
3238 An important special case: only one inner table, and @@optimizer_switch
3239 allows join buffering.
3240 - read_time is the same (i.e. FirstMatch doesn't add any cost
3241 - remove fanout added by the last table
3242 */
3243 if (*record_count)
3244 *record_count /= join->positions[idx].records_read;
3245 }
3246 else
3247 {
3248 optimize_wo_join_buffering(join, first_firstmatch_table, idx,
3249 remaining_tables, FALSE, idx,
3250 record_count,
3251 read_time);
3252 }
3253 /*
3254 We ought to save the alternate POSITIONs produced by
3255 optimize_wo_join_buffering but the problem is that providing save
3256 space uses too much space. Instead, we will re-calculate the
3257 alternate POSITIONs after we've picked the best QEP.
3258 */
3259 *handled_fanout= firstmatch_need_tables;
3260 /* *record_count and *read_time were set by the above call */
3261 *strategy= SJ_OPT_FIRST_MATCH;
3262 return TRUE;
3263 }
3264 }
3265 }
3266 else
3267 invalidate_firstmatch_prefix();
3268 return FALSE;
3269 }
3270
3271
set_from_prev(POSITION * prev)3272 void Duplicate_weedout_picker::set_from_prev(POSITION *prev)
3273 {
3274 if (prev->dups_weedout_picker.is_used)
3275 set_empty();
3276 else
3277 {
3278 dupsweedout_tables= prev->dups_weedout_picker.dupsweedout_tables;
3279 first_dupsweedout_table= prev->dups_weedout_picker.first_dupsweedout_table;
3280 }
3281 is_used= FALSE;
3282 }
3283
3284
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)3285 bool Duplicate_weedout_picker::check_qep(JOIN *join,
3286 uint idx,
3287 table_map remaining_tables,
3288 const JOIN_TAB *new_join_tab,
3289 double *record_count,
3290 double *read_time,
3291 table_map *handled_fanout,
3292 sj_strategy_enum *strategy,
3293 POSITION *loose_scan_pos
3294 )
3295 {
3296 TABLE_LIST *nest;
3297 if ((nest= new_join_tab->emb_sj_nest))
3298 {
3299 if (!dupsweedout_tables)
3300 first_dupsweedout_table= idx;
3301
3302 dupsweedout_tables |= nest->sj_inner_tables |
3303 nest->nested_join->sj_depends_on |
3304 nest->nested_join->sj_corr_tables;
3305 }
3306
3307 if (dupsweedout_tables)
3308 {
3309 /* we're in the process of constructing a DuplicateWeedout range */
3310 TABLE_LIST *emb= new_join_tab->table->pos_in_table_list->embedding;
3311 /* and we've entered an inner side of an outer join*/
3312 if (emb && emb->on_expr)
3313 dupsweedout_tables |= emb->nested_join->used_tables;
3314 }
3315
3316 /* If this is the last table that we need for DuplicateWeedout range */
3317 if (dupsweedout_tables && !(remaining_tables & ~new_join_tab->table->map &
3318 dupsweedout_tables))
3319 {
3320 /*
3321 Ok, reached a state where we could put a dups weedout point.
3322 Walk back and calculate
3323 - the join cost (this is needed as the accumulated cost may assume
3324 some other duplicate elimination method)
3325 - extra fanout that will be removed by duplicate elimination
3326 - duplicate elimination cost
3327 There are two cases:
3328 1. We have other strategy/ies to remove all of the duplicates.
3329 2. We don't.
3330
3331 We need to calculate the cost in case #2 also because we need to make
3332 choice between this join order and others.
3333 */
3334 uint first_tab= first_dupsweedout_table;
3335 double dups_cost;
3336 double prefix_rec_count;
3337 double sj_inner_fanout= 1.0;
3338 double sj_outer_fanout= 1.0;
3339 uint temptable_rec_size;
3340 if (first_tab == join->const_tables)
3341 {
3342 prefix_rec_count= 1.0;
3343 temptable_rec_size= 0;
3344 dups_cost= 0.0;
3345 }
3346 else
3347 {
3348 dups_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
3349 prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
3350 temptable_rec_size= 8; /* This is not true but we'll make it so */
3351 }
3352
3353 table_map dups_removed_fanout= 0;
3354 double current_fanout= prefix_rec_count;
3355 for (uint j= first_dupsweedout_table; j <= idx; j++)
3356 {
3357 POSITION *p= join->positions + j;
3358 current_fanout= COST_MULT(current_fanout, p->records_read);
3359 dups_cost= COST_ADD(dups_cost,
3360 COST_ADD(p->read_time,
3361 current_fanout / TIME_FOR_COMPARE));
3362 if (p->table->emb_sj_nest)
3363 {
3364 sj_inner_fanout= COST_MULT(sj_inner_fanout, p->records_read);
3365 dups_removed_fanout |= p->table->table->map;
3366 }
3367 else
3368 {
3369 sj_outer_fanout= COST_MULT(sj_outer_fanout, p->records_read);
3370 temptable_rec_size += p->table->table->file->ref_length;
3371 }
3372 }
3373
3374 /*
3375 Add the cost of temptable use. The table will have sj_outer_fanout
3376 records, and we will make
3377 - sj_outer_fanout table writes
3378 - sj_inner_fanout*sj_outer_fanout lookups.
3379
3380 */
3381 double one_lookup_cost= get_tmp_table_lookup_cost(join->thd,
3382 sj_outer_fanout,
3383 temptable_rec_size);
3384 double one_write_cost= get_tmp_table_write_cost(join->thd,
3385 sj_outer_fanout,
3386 temptable_rec_size);
3387
3388 double write_cost= COST_MULT(join->positions[first_tab].prefix_record_count,
3389 sj_outer_fanout * one_write_cost);
3390 double full_lookup_cost=
3391 COST_MULT(join->positions[first_tab].prefix_record_count,
3392 COST_MULT(sj_outer_fanout,
3393 sj_inner_fanout * one_lookup_cost));
3394 dups_cost= COST_ADD(dups_cost, COST_ADD(write_cost, full_lookup_cost));
3395
3396 *read_time= dups_cost;
3397 *record_count= prefix_rec_count * sj_outer_fanout;
3398 *handled_fanout= dups_removed_fanout;
3399 *strategy= SJ_OPT_DUPS_WEEDOUT;
3400 return TRUE;
3401 }
3402 return FALSE;
3403 }
3404
3405
3406 /*
3407 Remove the last join tab from from join->cur_sj_inner_tables bitmap
3408 we assume remaining_tables doesnt contain @tab.
3409 */
3410
restore_prev_sj_state(const table_map remaining_tables,const JOIN_TAB * tab,uint idx)3411 void restore_prev_sj_state(const table_map remaining_tables,
3412 const JOIN_TAB *tab, uint idx)
3413 {
3414 TABLE_LIST *emb_sj_nest;
3415
3416 if (tab->emb_sj_nest)
3417 {
3418 table_map subq_tables= tab->emb_sj_nest->sj_inner_tables;
3419 tab->join->sjm_lookup_tables &= ~subq_tables;
3420 }
3421
3422 if ((emb_sj_nest= tab->emb_sj_nest))
3423 {
3424 /* If we're removing the last SJ-inner table, remove the sj-nest */
3425 if ((remaining_tables & emb_sj_nest->sj_inner_tables) ==
3426 (emb_sj_nest->sj_inner_tables & ~tab->table->map))
3427 {
3428 tab->join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
3429 }
3430 }
3431 }
3432
3433
3434 /*
3435 Given a semi-join nest, find out which of the IN-equalities are bound
3436
3437 SYNOPSIS
3438 get_bound_sj_equalities()
3439 sj_nest Semi-join nest
3440 remaining_tables Tables that are not yet bound
3441
3442 DESCRIPTION
3443 Given a semi-join nest, find out which of the IN-equalities have their
3444 left part expression bound (i.e. the said expression doesn't refer to
3445 any of remaining_tables and can be evaluated).
3446
3447 RETURN
3448 Bitmap of bound IN-equalities.
3449 */
3450
get_bound_sj_equalities(TABLE_LIST * sj_nest,table_map remaining_tables)3451 ulonglong get_bound_sj_equalities(TABLE_LIST *sj_nest,
3452 table_map remaining_tables)
3453 {
3454 List_iterator<Item_ptr> li(sj_nest->nested_join->sj_outer_expr_list);
3455 Item **item;
3456 uint i= 0;
3457 ulonglong res= 0;
3458 while ((item= li++))
3459 {
3460 /*
3461 Q: should this take into account equality propagation and how?
3462 A: If e->outer_side is an Item_field, walk over the equality
3463 class and see if there is an element that is bound?
3464 (this is an optional feature)
3465 */
3466 if (!(item[0]->used_tables() & remaining_tables))
3467 {
3468 res |= 1ULL << i;
3469 }
3470 i++;
3471 }
3472 return res;
3473 }
3474
3475
3476 /*
3477 Check if the last tables of the partial join order allow to use
3478 sj-materialization strategy for them
3479
3480 SYNOPSIS
3481 at_sjmat_pos()
3482 join
3483 remaining_tables
3484 tab the last table's join tab
3485 idx last table's index
3486 loose_scan OUT TRUE <=> use LooseScan
3487
3488 RETURN
3489 TRUE Yes, can apply sj-materialization
3490 FALSE No, some of the requirements are not met
3491 */
3492
3493 static SJ_MATERIALIZATION_INFO *
at_sjmat_pos(const JOIN * join,table_map remaining_tables,const JOIN_TAB * tab,uint idx,bool * loose_scan)3494 at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
3495 uint idx, bool *loose_scan)
3496 {
3497 /*
3498 Check if
3499 1. We're in a semi-join nest that can be run with SJ-materialization
3500 2. All the tables correlated through the IN subquery are in the prefix
3501 */
3502 TABLE_LIST *emb_sj_nest= tab->emb_sj_nest;
3503 table_map suffix= remaining_tables & ~tab->table->map;
3504 if (emb_sj_nest && emb_sj_nest->sj_mat_info &&
3505 !(suffix & emb_sj_nest->sj_inner_tables))
3506 {
3507 /*
3508 Walk back and check if all immediately preceding tables are from
3509 this semi-join.
3510 */
3511 uint n_tables= my_count_bits(tab->emb_sj_nest->sj_inner_tables);
3512 for (uint i= 1; i < n_tables ; i++)
3513 {
3514 if (join->positions[idx - i].table->emb_sj_nest != tab->emb_sj_nest)
3515 return NULL;
3516 }
3517 *loose_scan= MY_TEST(remaining_tables & ~tab->table->map &
3518 (emb_sj_nest->sj_inner_tables |
3519 emb_sj_nest->nested_join->sj_depends_on));
3520 if (*loose_scan && !emb_sj_nest->sj_subq_pred->sjm_scan_allowed)
3521 return NULL;
3522 else
3523 return emb_sj_nest->sj_mat_info;
3524 }
3525 return NULL;
3526 }
3527
3528
3529 /*
3530 Re-calculate values of join->best_positions[start..end].prefix_record_count
3531 */
3532
recalculate_prefix_record_count(JOIN * join,uint start,uint end)3533 static void recalculate_prefix_record_count(JOIN *join, uint start, uint end)
3534 {
3535 for (uint j= start; j < end ;j++)
3536 {
3537 double prefix_count;
3538 if (j == join->const_tables)
3539 prefix_count= 1.0;
3540 else
3541 prefix_count= COST_MULT(join->best_positions[j-1].prefix_record_count,
3542 join->best_positions[j-1].records_read);
3543
3544 join->best_positions[j].prefix_record_count= prefix_count;
3545 }
3546 }
3547
3548
3549 /*
3550 Fix semi-join strategies for the picked join order
3551
3552 SYNOPSIS
3553 fix_semijoin_strategies_for_picked_join_order()
3554 join The join with the picked join order
3555
3556 DESCRIPTION
3557 Fix semi-join strategies for the picked join order. This is a step that
3558 needs to be done right after we have fixed the join order. What we do
3559 here is switch join's semi-join strategy description from backward-based
3560 to forwards based.
3561
3562 When join optimization is in progress, we re-consider semi-join
3563 strategies after we've added another table. Here's an illustration.
3564 Suppose the join optimization is underway:
3565
3566 1) ot1 it1 it2
3567 sjX -- looking at (ot1, it1, it2) join prefix, we decide
3568 to use semi-join strategy sjX.
3569
3570 2) ot1 it1 it2 ot2
3571 sjX sjY -- Having added table ot2, we now may consider
3572 another semi-join strategy and decide to use a
3573 different strategy sjY. Note that the record
3574 of sjX has remained under it2. That is
3575 necessary because we need to be able to get
3576 back to (ot1, it1, it2) join prefix.
3577 what makes things even worse is that there are cases where the choice
3578 of sjY changes the way we should access it2.
3579
3580 3) [ot1 it1 it2 ot2 ot3]
3581 sjX sjY -- This means that after join optimization is
3582 finished, semi-join info should be read
3583 right-to-left (while nearly all plan refinement
3584 functions, EXPLAIN, etc proceed from left to
3585 right)
3586
3587 This function does the needed reversal, making it possible to read the
3588 join and semi-join order from left to right.
3589 */
3590
fix_semijoin_strategies_for_picked_join_order(JOIN * join)3591 void fix_semijoin_strategies_for_picked_join_order(JOIN *join)
3592 {
3593 uint table_count=join->table_count;
3594 uint tablenr;
3595 table_map remaining_tables= 0;
3596 table_map handled_tabs= 0;
3597 join->sjm_lookup_tables= 0;
3598 join->sjm_scan_tables= 0;
3599 for (tablenr= table_count - 1 ; tablenr != join->const_tables - 1; tablenr--)
3600 {
3601 POSITION *pos= join->best_positions + tablenr;
3602 JOIN_TAB *s= pos->table;
3603 uint UNINIT_VAR(first); // Set by every branch except SJ_OPT_NONE which doesn't use it
3604
3605 if ((handled_tabs & s->table->map) || pos->sj_strategy == SJ_OPT_NONE)
3606 {
3607 remaining_tables |= s->table->map;
3608 continue;
3609 }
3610
3611 if (pos->sj_strategy == SJ_OPT_MATERIALIZE)
3612 {
3613 SJ_MATERIALIZATION_INFO *sjm= s->emb_sj_nest->sj_mat_info;
3614 sjm->is_used= TRUE;
3615 sjm->is_sj_scan= FALSE;
3616 memcpy((uchar*) (pos - sjm->tables + 1), (uchar*) sjm->positions,
3617 sizeof(POSITION) * sjm->tables);
3618 recalculate_prefix_record_count(join, tablenr - sjm->tables + 1,
3619 tablenr);
3620 first= tablenr - sjm->tables + 1;
3621 join->best_positions[first].n_sj_tables= sjm->tables;
3622 join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE;
3623 for (uint i= first; i < first+ sjm->tables; i++)
3624 join->sjm_lookup_tables |= join->best_positions[i].table->table->map;
3625 }
3626 else if (pos->sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
3627 {
3628 POSITION *first_inner= join->best_positions + pos->sjmat_picker.sjm_scan_last_inner;
3629 SJ_MATERIALIZATION_INFO *sjm= first_inner->table->emb_sj_nest->sj_mat_info;
3630 sjm->is_used= TRUE;
3631 sjm->is_sj_scan= TRUE;
3632 first= pos->sjmat_picker.sjm_scan_last_inner - sjm->tables + 1;
3633 memcpy((uchar*) (join->best_positions + first),
3634 (uchar*) sjm->positions, sizeof(POSITION) * sjm->tables);
3635 recalculate_prefix_record_count(join, first, first + sjm->tables);
3636 join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE_SCAN;
3637 join->best_positions[first].n_sj_tables= sjm->tables;
3638 /*
3639 Do what advance_sj_state did: re-run best_access_path for every table
3640 in the [last_inner_table + 1; pos..) range
3641 */
3642 double prefix_rec_count;
3643 /* Get the prefix record count */
3644 if (first == join->const_tables)
3645 prefix_rec_count= 1.0;
3646 else
3647 prefix_rec_count= join->best_positions[first-1].prefix_record_count;
3648
3649 /* Add materialization record count*/
3650 prefix_rec_count *= sjm->rows;
3651
3652 uint i;
3653 table_map rem_tables= remaining_tables;
3654 for (i= tablenr; i != (first + sjm->tables - 1); i--)
3655 rem_tables |= join->best_positions[i].table->table->map;
3656
3657 for (i= first; i < first+ sjm->tables; i++)
3658 join->sjm_scan_tables |= join->best_positions[i].table->table->map;
3659
3660 POSITION dummy;
3661 join->cur_sj_inner_tables= 0;
3662 for (i= first + sjm->tables; i <= tablenr; i++)
3663 {
3664 best_access_path(join, join->best_positions[i].table, rem_tables,
3665 join->best_positions, i,
3666 FALSE, prefix_rec_count,
3667 join->best_positions + i, &dummy);
3668 prefix_rec_count *= join->best_positions[i].records_read;
3669 rem_tables &= ~join->best_positions[i].table->table->map;
3670 }
3671 }
3672
3673 if (pos->sj_strategy == SJ_OPT_FIRST_MATCH)
3674 {
3675 first= pos->firstmatch_picker.first_firstmatch_table;
3676 join->best_positions[first].sj_strategy= SJ_OPT_FIRST_MATCH;
3677 join->best_positions[first].n_sj_tables= tablenr - first + 1;
3678 POSITION dummy; // For loose scan paths
3679 double record_count= (first== join->const_tables)? 1.0:
3680 join->best_positions[tablenr - 1].prefix_record_count;
3681
3682 table_map rem_tables= remaining_tables;
3683 uint idx;
3684 for (idx= first; idx <= tablenr; idx++)
3685 {
3686 rem_tables |= join->best_positions[idx].table->table->map;
3687 }
3688 /*
3689 Re-run best_access_path to produce best access methods that do not use
3690 join buffering
3691 */
3692 join->cur_sj_inner_tables= 0;
3693 for (idx= first; idx <= tablenr; idx++)
3694 {
3695 if (join->best_positions[idx].use_join_buffer)
3696 {
3697 best_access_path(join, join->best_positions[idx].table,
3698 rem_tables, join->best_positions, idx,
3699 TRUE /* no jbuf */,
3700 record_count, join->best_positions + idx, &dummy);
3701 }
3702 record_count *= join->best_positions[idx].records_read;
3703 rem_tables &= ~join->best_positions[idx].table->table->map;
3704 }
3705 }
3706
3707 if (pos->sj_strategy == SJ_OPT_LOOSE_SCAN)
3708 {
3709 first= pos->loosescan_picker.first_loosescan_table;
3710 POSITION *first_pos= join->best_positions + first;
3711 POSITION loose_scan_pos; // For loose scan paths
3712 double record_count= (first== join->const_tables)? 1.0:
3713 join->best_positions[tablenr - 1].prefix_record_count;
3714
3715 table_map rem_tables= remaining_tables;
3716 uint idx;
3717 for (idx= first; idx <= tablenr; idx++)
3718 rem_tables |= join->best_positions[idx].table->table->map;
3719 /*
3720 Re-run best_access_path to produce best access methods that do not use
3721 join buffering
3722 */
3723 join->cur_sj_inner_tables= 0;
3724 for (idx= first; idx <= tablenr; idx++)
3725 {
3726 if (join->best_positions[idx].use_join_buffer || (idx == first))
3727 {
3728 best_access_path(join, join->best_positions[idx].table,
3729 rem_tables, join->best_positions, idx,
3730 TRUE /* no jbuf */,
3731 record_count, join->best_positions + idx,
3732 &loose_scan_pos);
3733 if (idx==first)
3734 {
3735 join->best_positions[idx]= loose_scan_pos;
3736 /*
3737 If LooseScan is based on ref access (including the "degenerate"
3738 one with 0 key parts), we should use full index scan.
3739
3740 Unfortunately, lots of code assumes that if tab->type==JT_ALL &&
3741 tab->quick!=NULL, then quick select should be used. The only
3742 simple way to fix this is to remove the quick select:
3743 */
3744 if (join->best_positions[idx].key)
3745 {
3746 delete join->best_positions[idx].table->quick;
3747 join->best_positions[idx].table->quick= NULL;
3748 }
3749 }
3750 }
3751 rem_tables &= ~join->best_positions[idx].table->table->map;
3752 record_count *= join->best_positions[idx].records_read;
3753 }
3754 first_pos->sj_strategy= SJ_OPT_LOOSE_SCAN;
3755 first_pos->n_sj_tables= my_count_bits(first_pos->table->emb_sj_nest->sj_inner_tables);
3756 }
3757
3758 if (pos->sj_strategy == SJ_OPT_DUPS_WEEDOUT)
3759 {
3760 /*
3761 Duplicate Weedout starting at pos->first_dupsweedout_table, ending at
3762 this table.
3763 */
3764 first= pos->dups_weedout_picker.first_dupsweedout_table;
3765 join->best_positions[first].sj_strategy= SJ_OPT_DUPS_WEEDOUT;
3766 join->best_positions[first].n_sj_tables= tablenr - first + 1;
3767 }
3768
3769 uint i_end= first + join->best_positions[first].n_sj_tables;
3770 for (uint i= first; i < i_end; i++)
3771 {
3772 if (i != first)
3773 join->best_positions[i].sj_strategy= SJ_OPT_NONE;
3774 handled_tabs |= join->best_positions[i].table->table->map;
3775 }
3776
3777 if (tablenr != first)
3778 pos->sj_strategy= SJ_OPT_NONE;
3779 remaining_tables |= s->table->map;
3780 join->join_tab[first].sj_strategy= join->best_positions[first].sj_strategy;
3781 join->join_tab[first].n_sj_tables= join->best_positions[first].n_sj_tables;
3782 }
3783 }
3784
3785
3786 /*
3787 Setup semi-join materialization strategy for one semi-join nest
3788
3789 SYNOPSIS
3790
3791 setup_sj_materialization()
3792 tab The first tab in the semi-join
3793
3794 DESCRIPTION
3795 Setup execution structures for one semi-join materialization nest:
3796 - Create the materialization temporary table
3797 - If we're going to do index lookups
3798 create TABLE_REF structure to make the lookus
3799 - else (if we're going to do a full scan of the temptable)
3800 create Copy_field structures to do copying.
3801
3802 RETURN
3803 FALSE Ok
3804 TRUE Error
3805 */
3806
setup_sj_materialization_part1(JOIN_TAB * sjm_tab)3807 bool setup_sj_materialization_part1(JOIN_TAB *sjm_tab)
3808 {
3809 JOIN_TAB *tab= sjm_tab->bush_children->start;
3810 TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
3811 SJ_MATERIALIZATION_INFO *sjm;
3812 THD *thd;
3813
3814 DBUG_ENTER("setup_sj_materialization");
3815
3816 /* Walk out of outer join nests until we reach the semi-join nest we're in */
3817 while (!emb_sj_nest->sj_mat_info)
3818 emb_sj_nest= emb_sj_nest->embedding;
3819
3820 sjm= emb_sj_nest->sj_mat_info;
3821 thd= tab->join->thd;
3822 /* First the calls come to the materialization function */
3823
3824 DBUG_ASSERT(sjm->is_used);
3825 /*
3826 Set up the table to write to, do as select_union::create_result_table does
3827 */
3828 sjm->sjm_table_param.init();
3829 sjm->sjm_table_param.bit_fields_as_long= TRUE;
3830 SELECT_LEX *subq_select= emb_sj_nest->sj_subq_pred->unit->first_select();
3831 const LEX_CSTRING sj_materialize_name= { STRING_WITH_LEN("sj-materialize") };
3832 List_iterator<Item> it(subq_select->item_list);
3833 Item *item;
3834 while((item= it++))
3835 {
3836 /*
3837 This semi-join replaced the subquery (subq_select) and so on
3838 re-executing it will not be prepared. To use the Items from its
3839 select list we have to prepare (fix_fields) them
3840 */
3841 if (item->fix_fields_if_needed(thd, it.ref()))
3842 DBUG_RETURN(TRUE);
3843 item= *(it.ref()); // it can be changed by fix_fields
3844 DBUG_ASSERT(!item->name.length || item->name.length == strlen(item->name.str));
3845 sjm->sjm_table_cols.push_back(item, thd->mem_root);
3846 }
3847
3848 sjm->sjm_table_param.field_count= subq_select->item_list.elements;
3849 sjm->sjm_table_param.force_not_null_cols= TRUE;
3850
3851 if (!(sjm->table= create_tmp_table(thd, &sjm->sjm_table_param,
3852 sjm->sjm_table_cols, (ORDER*) 0,
3853 TRUE /* distinct */,
3854 1, /*save_sum_fields*/
3855 thd->variables.option_bits | TMP_TABLE_ALL_COLUMNS,
3856 HA_POS_ERROR /*rows_limit */,
3857 &sj_materialize_name)))
3858 DBUG_RETURN(TRUE); /* purecov: inspected */
3859 sjm->table->map= emb_sj_nest->nested_join->used_tables;
3860 sjm->table->file->extra(HA_EXTRA_WRITE_CACHE);
3861 sjm->table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
3862
3863 tab->join->sj_tmp_tables.push_back(sjm->table, thd->mem_root);
3864 tab->join->sjm_info_list.push_back(sjm, thd->mem_root);
3865
3866 sjm->materialized= FALSE;
3867 sjm_tab->table= sjm->table;
3868 sjm->table->pos_in_table_list= emb_sj_nest;
3869
3870 DBUG_RETURN(FALSE);
3871 }
3872
3873 /**
3874 @retval
3875 FALSE ok
3876 TRUE error
3877 */
3878
setup_sj_materialization_part2(JOIN_TAB * sjm_tab)3879 bool setup_sj_materialization_part2(JOIN_TAB *sjm_tab)
3880 {
3881 DBUG_ENTER("setup_sj_materialization_part2");
3882 JOIN_TAB *tab= sjm_tab->bush_children->start;
3883 TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
3884 /* Walk out of outer join nests until we reach the semi-join nest we're in */
3885 while (!emb_sj_nest->sj_mat_info)
3886 emb_sj_nest= emb_sj_nest->embedding;
3887 SJ_MATERIALIZATION_INFO *sjm= emb_sj_nest->sj_mat_info;
3888 THD *thd= tab->join->thd;
3889 uint i;
3890
3891 if (!sjm->is_sj_scan)
3892 {
3893 KEY *tmp_key; /* The only index on the temporary table. */
3894 uint tmp_key_parts; /* Number of keyparts in tmp_key. */
3895 tmp_key= sjm->table->key_info;
3896 tmp_key_parts= tmp_key->user_defined_key_parts;
3897
3898 /*
3899 Create/initialize everything we will need to index lookups into the
3900 temptable.
3901 */
3902 TABLE_REF *tab_ref;
3903 tab_ref= &sjm_tab->ref;
3904 tab_ref->key= 0; /* The only temp table index. */
3905 tab_ref->key_length= tmp_key->key_length;
3906 if (!(tab_ref->key_buff=
3907 (uchar*) thd->calloc(ALIGN_SIZE(tmp_key->key_length) * 2)) ||
3908 !(tab_ref->key_copy=
3909 (store_key**) thd->alloc((sizeof(store_key*) *
3910 (tmp_key_parts + 1)))) ||
3911 !(tab_ref->items=
3912 (Item**) thd->alloc(sizeof(Item*) * tmp_key_parts)))
3913 DBUG_RETURN(TRUE); /* purecov: inspected */
3914
3915 tab_ref->key_buff2=tab_ref->key_buff+ALIGN_SIZE(tmp_key->key_length);
3916 tab_ref->key_err=1;
3917 tab_ref->null_rejecting= 1;
3918 tab_ref->disable_cache= FALSE;
3919
3920 KEY_PART_INFO *cur_key_part= tmp_key->key_part;
3921 store_key **ref_key= tab_ref->key_copy;
3922 uchar *cur_ref_buff= tab_ref->key_buff;
3923
3924 for (i= 0; i < tmp_key_parts; i++, cur_key_part++, ref_key++)
3925 {
3926 tab_ref->items[i]= emb_sj_nest->sj_subq_pred->left_expr->element_index(i);
3927 int null_count= MY_TEST(cur_key_part->field->real_maybe_null());
3928 *ref_key= new store_key_item(thd, cur_key_part->field,
3929 /* TODO:
3930 the NULL byte is taken into account in
3931 cur_key_part->store_length, so instead of
3932 cur_ref_buff + MY_TEST(maybe_null), we could
3933 use that information instead.
3934 */
3935 cur_ref_buff + null_count,
3936 null_count ? cur_ref_buff : 0,
3937 cur_key_part->length, tab_ref->items[i],
3938 FALSE);
3939 if (!*ref_key)
3940 DBUG_RETURN(TRUE);
3941 cur_ref_buff+= cur_key_part->store_length;
3942 }
3943 *ref_key= NULL; /* End marker. */
3944
3945 /*
3946 We don't ever have guarded conditions for SJM tables, but code at SQL
3947 layer depends on cond_guards array being alloced.
3948 */
3949 if (!(tab_ref->cond_guards= (bool**) thd->calloc(sizeof(uint*)*tmp_key_parts)))
3950 {
3951 DBUG_RETURN(TRUE);
3952 }
3953
3954 tab_ref->key_err= 1;
3955 tab_ref->key_parts= tmp_key_parts;
3956 sjm->tab_ref= tab_ref;
3957
3958 /*
3959 Remove the injected semi-join IN-equalities from join_tab conds. This
3960 needs to be done because the IN-equalities refer to columns of
3961 sj-inner tables which are not available after the materialization
3962 has been finished.
3963 */
3964 for (i= 0; i < sjm->tables; i++)
3965 {
3966 if (remove_sj_conds(thd, &tab[i].select_cond) ||
3967 (tab[i].select && remove_sj_conds(thd, &tab[i].select->cond)))
3968 DBUG_RETURN(TRUE);
3969 }
3970 if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm,
3971 emb_sj_nest->sj_subq_pred)))
3972 DBUG_RETURN(TRUE); /* purecov: inspected */
3973 sjm_tab->type= JT_EQ_REF;
3974 sjm_tab->select_cond= sjm->in_equality;
3975 }
3976 else
3977 {
3978 /*
3979 We'll be doing full scan of the temptable.
3980 Setup copying of temptable columns back to the record buffers
3981 for their source tables. We need this because IN-equalities
3982 refer to the original tables.
3983
3984 EXAMPLE
3985
3986 Consider the query:
3987 SELECT * FROM ot WHERE ot.col1 IN (SELECT it.col2 FROM it)
3988
3989 Suppose it's executed with SJ-Materialization-scan. We choose to do scan
3990 if we can't do the lookup, i.e. the join order is (it, ot). The plan
3991 would look as follows:
3992
3993 table access method condition
3994 it materialize+scan -
3995 ot (whatever) ot1.col1=it.col2 (C2)
3996
3997 The condition C2 refers to current row of table it. The problem is
3998 that by the time we evaluate C2, we would have finished with scanning
3999 it itself and will be scanning the temptable.
4000
4001 At the moment, our solution is to copy back: when we get the next
4002 temptable record, we copy its columns to their corresponding columns
4003 in the record buffers for the source tables.
4004 */
4005 if (!(sjm->copy_field= new Copy_field[sjm->sjm_table_cols.elements]))
4006 DBUG_RETURN(TRUE);
4007
4008 //it.rewind();
4009 Ref_ptr_array p_items= emb_sj_nest->sj_subq_pred->unit->first_select()->ref_pointer_array;
4010 for (uint i=0; i < sjm->sjm_table_cols.elements; i++)
4011 {
4012 bool dummy;
4013 Item_equal *item_eq;
4014 //Item *item= (it++)->real_item();
4015 Item *item= p_items[i]->real_item();
4016 DBUG_ASSERT(item->type() == Item::FIELD_ITEM);
4017 Field *copy_to= ((Item_field*)item)->field;
4018 /*
4019 Tricks with Item_equal are due to the following: suppose we have a
4020 query:
4021
4022 ... WHERE cond(ot.col) AND ot.col IN (SELECT it2.col FROM it1,it2
4023 WHERE it1.col= it2.col)
4024 then equality propagation will create an
4025
4026 Item_equal(it1.col, it2.col, ot.col)
4027
4028 then substitute_for_best_equal_field() will change the conditions
4029 according to the join order:
4030
4031 table | attached condition
4032 ------+--------------------
4033 it1 |
4034 it2 | it1.col=it2.col
4035 ot | cond(it1.col)
4036
4037 although we've originally had "SELECT it2.col", conditions attached
4038 to subsequent outer tables will refer to it1.col, so SJM-Scan will
4039 need to unpack data to there.
4040 That is, if an element from subquery's select list participates in
4041 equality propagation, then we need to unpack it to the first
4042 element equality propagation member that refers to table that is
4043 within the subquery.
4044 */
4045 item_eq= find_item_equal(tab->join->cond_equal, copy_to, &dummy);
4046
4047 if (item_eq)
4048 {
4049 List_iterator<Item> it(item_eq->equal_items);
4050 /* We're interested in field items only */
4051 if (item_eq->get_const())
4052 it++;
4053 Item *item;
4054 while ((item= it++))
4055 {
4056 if (!(item->used_tables() & ~emb_sj_nest->sj_inner_tables))
4057 {
4058 DBUG_ASSERT(item->real_item()->type() == Item::FIELD_ITEM);
4059 copy_to= ((Item_field *) (item->real_item()))->field;
4060 break;
4061 }
4062 }
4063 }
4064 sjm->copy_field[i].set(copy_to, sjm->table->field[i], FALSE);
4065 /* The write_set for source tables must be set up to allow the copying */
4066 bitmap_set_bit(copy_to->table->write_set, copy_to->field_index);
4067 }
4068 sjm_tab->type= JT_ALL;
4069
4070 /* Initialize full scan */
4071 sjm_tab->read_first_record= join_read_record_no_init;
4072 sjm_tab->read_record.copy_field= sjm->copy_field;
4073 sjm_tab->read_record.copy_field_end= sjm->copy_field +
4074 sjm->sjm_table_cols.elements;
4075 sjm_tab->read_record.read_record_func= rr_sequential_and_unpack;
4076 }
4077
4078 sjm_tab->bush_children->end[-1].next_select= end_sj_materialize;
4079
4080 DBUG_RETURN(FALSE);
4081 }
4082
4083
4084
4085 /*
4086 Create subquery IN-equalities assuming use of materialization strategy
4087
4088 SYNOPSIS
4089 create_subq_in_equalities()
4090 thd Thread handle
4091 sjm Semi-join materialization structure
4092 subq_pred The subquery predicate
4093
4094 DESCRIPTION
4095 Create subquery IN-equality predicates. That is, for a subquery
4096
4097 (oe1, oe2, ...) IN (SELECT ie1, ie2, ... FROM ...)
4098
4099 create "oe1=ie1 AND ie1=ie2 AND ..." expression, such that ie1, ie2, ..
4100 refer to the columns of the table that's used to materialize the
4101 subquery.
4102
4103 RETURN
4104 Created condition
4105 */
4106
create_subq_in_equalities(THD * thd,SJ_MATERIALIZATION_INFO * sjm,Item_in_subselect * subq_pred)4107 static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm,
4108 Item_in_subselect *subq_pred)
4109 {
4110 Item *res= NULL;
4111 if (subq_pred->left_expr->cols() == 1)
4112 {
4113 if (!(res= new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr,
4114 new (thd->mem_root) Item_field(thd, sjm->table->field[0]))))
4115 return NULL; /* purecov: inspected */
4116 }
4117 else
4118 {
4119 Item *conj;
4120 for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
4121 {
4122 if (!(conj= new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr->element_index(i),
4123 new (thd->mem_root) Item_field(thd, sjm->table->field[i]))) ||
4124 !(res= and_items(thd, res, conj)))
4125 return NULL; /* purecov: inspected */
4126 }
4127 }
4128 if (res->fix_fields(thd, &res))
4129 return NULL; /* purecov: inspected */
4130 return res;
4131 }
4132
4133
4134 /**
4135 @retval
4136 0 ok
4137 1 error
4138 */
4139
remove_sj_conds(THD * thd,Item ** tree)4140 static bool remove_sj_conds(THD *thd, Item **tree)
4141 {
4142 if (*tree)
4143 {
4144 if (is_cond_sj_in_equality(*tree))
4145 {
4146 *tree= NULL;
4147 return 0;
4148 }
4149 else if ((*tree)->type() == Item::COND_ITEM)
4150 {
4151 Item *item;
4152 List_iterator<Item> li(*(((Item_cond*)*tree)->argument_list()));
4153 while ((item= li++))
4154 {
4155 if (is_cond_sj_in_equality(item))
4156 {
4157 Item_int *tmp= new (thd->mem_root) Item_int(thd, 1);
4158 if (!tmp)
4159 return 1;
4160 li.replace(tmp);
4161 }
4162 }
4163 }
4164 }
4165 return 0;
4166 }
4167
4168
4169 /* Check if given Item was injected by semi-join equality */
is_cond_sj_in_equality(Item * item)4170 static bool is_cond_sj_in_equality(Item *item)
4171 {
4172 if (item->type() == Item::FUNC_ITEM &&
4173 ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
4174 {
4175 Item_func_eq *item_eq= (Item_func_eq*)item;
4176 return MY_TEST(item_eq->in_equality_no != UINT_MAX);
4177 }
4178 return FALSE;
4179 }
4180
4181
4182 /*
4183 Create a temporary table to weed out duplicate rowid combinations
4184
4185 SYNOPSIS
4186
4187 create_sj_weedout_tmp_table()
4188 thd Thread handle
4189
4190 DESCRIPTION
4191 Create a temporary table to weed out duplicate rowid combinations. The
4192 table has a single column that is a concatenation of all rowids in the
4193 combination.
4194
4195 Depending on the needed length, there are two cases:
4196
4197 1. When the length of the column < max_key_length:
4198
4199 CREATE TABLE tmp (col VARBINARY(n) NOT NULL, UNIQUE KEY(col));
4200
4201 2. Otherwise (not a valid SQL syntax but internally supported):
4202
4203 CREATE TABLE tmp (col VARBINARY NOT NULL, UNIQUE CONSTRAINT(col));
4204
4205 The code in this function was produced by extraction of relevant parts
4206 from create_tmp_table().
4207
4208 RETURN
4209 created table
4210 NULL on error
4211 */
4212
4213 bool
create_sj_weedout_tmp_table(THD * thd)4214 SJ_TMP_TABLE::create_sj_weedout_tmp_table(THD *thd)
4215 {
4216 MEM_ROOT *mem_root_save, own_root;
4217 TABLE *table;
4218 TABLE_SHARE *share;
4219 uint temp_pool_slot=MY_BIT_NONE;
4220 char *tmpname,path[FN_REFLEN];
4221 Field **reg_field;
4222 KEY_PART_INFO *key_part_info;
4223 KEY *keyinfo;
4224 uchar *group_buff;
4225 uchar *bitmaps;
4226 uint *blob_field;
4227 bool using_unique_constraint=FALSE;
4228 bool use_packed_rows= FALSE;
4229 Field *field, *key_field;
4230 uint null_pack_length, null_count;
4231 uchar *null_flags;
4232 uchar *pos;
4233 DBUG_ENTER("create_sj_weedout_tmp_table");
4234 DBUG_ASSERT(!is_degenerate);
4235
4236 tmp_table= NULL;
4237 uint uniq_tuple_length_arg= rowid_len + null_bytes;
4238 /*
4239 STEP 1: Get temporary table name
4240 */
4241 if (use_temp_pool && !(test_flags & TEST_KEEP_TMP_TABLES))
4242 temp_pool_slot = bitmap_lock_set_next(&temp_pool);
4243
4244 if (temp_pool_slot != MY_BIT_NONE) // we got a slot
4245 sprintf(path, "%s_%lx_%i", tmp_file_prefix,
4246 current_pid, temp_pool_slot);
4247 else
4248 {
4249 /* if we run out of slots or we are not using tempool */
4250 sprintf(path,"%s%lx_%lx_%x", tmp_file_prefix,current_pid,
4251 (ulong) thd->thread_id, thd->tmp_table++);
4252 }
4253 fn_format(path, path, mysql_tmpdir, "", MY_REPLACE_EXT|MY_UNPACK_FILENAME);
4254
4255 /* STEP 2: Figure if we'll be using a key or blob+constraint */
4256 /* it always has my_charset_bin, so mbmaxlen==1 */
4257 if (uniq_tuple_length_arg >= CONVERT_IF_BIGGER_TO_BLOB)
4258 using_unique_constraint= TRUE;
4259
4260 /* STEP 3: Allocate memory for temptable description */
4261 init_sql_alloc(&own_root, "SJ_TMP_TABLE",
4262 TABLE_ALLOC_BLOCK_SIZE, 0, MYF(MY_THREAD_SPECIFIC));
4263 if (!multi_alloc_root(&own_root,
4264 &table, sizeof(*table),
4265 &share, sizeof(*share),
4266 ®_field, sizeof(Field*) * (1+1),
4267 &blob_field, sizeof(uint)*2,
4268 &keyinfo, sizeof(*keyinfo),
4269 &key_part_info, sizeof(*key_part_info) * 2,
4270 &start_recinfo,
4271 sizeof(*recinfo)*(1*2+4),
4272 &tmpname, (uint) strlen(path)+1,
4273 &group_buff, (!using_unique_constraint ?
4274 uniq_tuple_length_arg : 0),
4275 &bitmaps, bitmap_buffer_size(1)*6,
4276 NullS))
4277 {
4278 if (temp_pool_slot != MY_BIT_NONE)
4279 bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
4280 DBUG_RETURN(TRUE);
4281 }
4282 strmov(tmpname,path);
4283
4284
4285 /* STEP 4: Create TABLE description */
4286 bzero((char*) table,sizeof(*table));
4287 bzero((char*) reg_field,sizeof(Field*)*2);
4288
4289 table->mem_root= own_root;
4290 mem_root_save= thd->mem_root;
4291 thd->mem_root= &table->mem_root;
4292
4293 table->field=reg_field;
4294 table->alias.set("weedout-tmp", sizeof("weedout-tmp")-1,
4295 table_alias_charset);
4296 table->reginfo.lock_type=TL_WRITE; /* Will be updated */
4297 table->db_stat=HA_OPEN_KEYFILE;
4298 table->map=1;
4299 table->temp_pool_slot = temp_pool_slot;
4300 table->copy_blobs= 1;
4301 table->in_use= thd;
4302 table->quick_keys.init();
4303 table->covering_keys.init();
4304 table->keys_in_use_for_query.init();
4305
4306 table->s= share;
4307 init_tmp_table_share(thd, share, "", 0, tmpname, tmpname);
4308 share->blob_field= blob_field;
4309 share->table_charset= NULL;
4310 share->primary_key= MAX_KEY; // Indicate no primary key
4311 share->keys_for_keyread.init();
4312 share->keys_in_use.init();
4313
4314 /* Create the field */
4315 {
4316 LEX_CSTRING field_name= {STRING_WITH_LEN("rowids") };
4317 /*
4318 For the sake of uniformity, always use Field_varstring (altough we could
4319 use Field_string for shorter keys)
4320 */
4321 field= new Field_varstring(uniq_tuple_length_arg, FALSE, &field_name,
4322 share, &my_charset_bin);
4323 if (!field)
4324 DBUG_RETURN(0);
4325 field->table= table;
4326 field->key_start.init(0);
4327 field->part_of_key.init(0);
4328 field->part_of_sortkey.init(0);
4329 field->unireg_check= Field::NONE;
4330 field->flags= (NOT_NULL_FLAG | BINARY_FLAG | NO_DEFAULT_VALUE_FLAG);
4331 field->reset_fields();
4332 field->init(table);
4333 field->orig_table= NULL;
4334
4335 field->field_index= 0;
4336
4337 *(reg_field++)= field;
4338 *blob_field= 0;
4339 *reg_field= 0;
4340
4341 share->fields= 1;
4342 share->blob_fields= 0;
4343 }
4344
4345 uint reclength= field->pack_length();
4346 if (using_unique_constraint)
4347 {
4348 share->db_plugin= ha_lock_engine(0, TMP_ENGINE_HTON);
4349 table->file= get_new_handler(share, &table->mem_root,
4350 share->db_type());
4351 }
4352 else
4353 {
4354 share->db_plugin= ha_lock_engine(0, heap_hton);
4355 table->file= get_new_handler(share, &table->mem_root,
4356 share->db_type());
4357 DBUG_ASSERT(!table->file || uniq_tuple_length_arg <= table->file->max_key_length());
4358 }
4359 if (!table->file)
4360 goto err;
4361
4362 if (table->file->set_ha_share_ref(&share->ha_share))
4363 {
4364 delete table->file;
4365 goto err;
4366 }
4367
4368 null_count=1;
4369
4370 null_pack_length= 1;
4371 reclength += null_pack_length;
4372
4373 share->reclength= reclength;
4374 {
4375 uint alloc_length=ALIGN_SIZE(share->reclength + MI_UNIQUE_HASH_LENGTH+1);
4376 share->rec_buff_length= alloc_length;
4377 if (!(table->record[0]= (uchar*)
4378 alloc_root(&table->mem_root, alloc_length*3)))
4379 goto err;
4380 table->record[1]= table->record[0]+alloc_length;
4381 share->default_values= table->record[1]+alloc_length;
4382 }
4383 setup_tmp_table_column_bitmaps(table, bitmaps);
4384
4385 recinfo= start_recinfo;
4386 null_flags=(uchar*) table->record[0];
4387 pos=table->record[0]+ null_pack_length;
4388 if (null_pack_length)
4389 {
4390 bzero((uchar*) recinfo,sizeof(*recinfo));
4391 recinfo->type=FIELD_NORMAL;
4392 recinfo->length=null_pack_length;
4393 recinfo++;
4394 bfill(null_flags,null_pack_length,255); // Set null fields
4395
4396 table->null_flags= (uchar*) table->record[0];
4397 share->null_fields= null_count;
4398 share->null_bytes= null_pack_length;
4399 }
4400 null_count=1;
4401
4402 {
4403 //Field *field= *reg_field;
4404 uint length;
4405 bzero((uchar*) recinfo,sizeof(*recinfo));
4406 field->move_field(pos,(uchar*) 0,0);
4407
4408 field->reset();
4409 /*
4410 Test if there is a default field value. The test for ->ptr is to skip
4411 'offset' fields generated by initialize_tables
4412 */
4413 // Initialize the table field:
4414 bzero(field->ptr, field->pack_length());
4415
4416 length=field->pack_length();
4417 pos+= length;
4418
4419 /* Make entry for create table */
4420 recinfo->length=length;
4421 if (field->flags & BLOB_FLAG)
4422 recinfo->type= FIELD_BLOB;
4423 else if (use_packed_rows &&
4424 field->real_type() == MYSQL_TYPE_STRING &&
4425 length >= MIN_STRING_LENGTH_TO_PACK_ROWS)
4426 recinfo->type=FIELD_SKIP_ENDSPACE;
4427 else
4428 recinfo->type=FIELD_NORMAL;
4429
4430 field->set_table_name(&table->alias);
4431 }
4432
4433 if (thd->variables.tmp_memory_table_size == ~ (ulonglong) 0) // No limit
4434 share->max_rows= ~(ha_rows) 0;
4435 else
4436 share->max_rows= (ha_rows) (((share->db_type() == heap_hton) ?
4437 MY_MIN(thd->variables.tmp_memory_table_size,
4438 thd->variables.max_heap_table_size) :
4439 thd->variables.tmp_memory_table_size) /
4440 share->reclength);
4441 set_if_bigger(share->max_rows,1); // For dummy start options
4442
4443
4444 //// keyinfo= param->keyinfo;
4445 if (TRUE)
4446 {
4447 DBUG_PRINT("info",("Creating group key in temporary table"));
4448 share->keys=1;
4449 share->uniques= MY_TEST(using_unique_constraint);
4450 table->key_info=keyinfo;
4451 keyinfo->key_part=key_part_info;
4452 keyinfo->flags=HA_NOSAME;
4453 keyinfo->usable_key_parts= keyinfo->user_defined_key_parts= 1;
4454 keyinfo->key_length=0;
4455 keyinfo->rec_per_key=0;
4456 keyinfo->algorithm= HA_KEY_ALG_UNDEF;
4457 keyinfo->name= weedout_key;
4458 {
4459 key_part_info->null_bit=0;
4460 key_part_info->field= field;
4461 key_part_info->offset= field->offset(table->record[0]);
4462 key_part_info->length= (uint16) field->key_length();
4463 key_part_info->type= (uint8) field->key_type();
4464 key_part_info->key_type = FIELDFLAG_BINARY;
4465 if (!using_unique_constraint)
4466 {
4467 if (!(key_field= field->new_key_field(thd->mem_root, table,
4468 group_buff,
4469 key_part_info->length,
4470 field->null_ptr,
4471 field->null_bit)))
4472 goto err;
4473 }
4474 keyinfo->key_length+= key_part_info->length;
4475 }
4476 }
4477
4478 if (unlikely(thd->is_fatal_error)) // If end of memory
4479 goto err;
4480 share->db_record_offset= 1;
4481 table->no_rows= 1; // We don't need the data
4482
4483 // recinfo must point after last field
4484 recinfo++;
4485 if (share->db_type() == TMP_ENGINE_HTON)
4486 {
4487 if (unlikely(create_internal_tmp_table(table, keyinfo, start_recinfo,
4488 &recinfo, 0)))
4489 goto err;
4490 }
4491 if (unlikely(open_tmp_table(table)))
4492 goto err;
4493
4494 thd->mem_root= mem_root_save;
4495 tmp_table= table;
4496 DBUG_RETURN(FALSE);
4497
4498 err:
4499 thd->mem_root= mem_root_save;
4500 free_tmp_table(thd,table); /* purecov: inspected */
4501 if (temp_pool_slot != MY_BIT_NONE)
4502 bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
4503 DBUG_RETURN(TRUE); /* purecov: inspected */
4504 }
4505
4506
4507 /*
4508 SemiJoinDuplicateElimination: Reset the temporary table
4509 */
4510
sj_weedout_delete_rows()4511 int SJ_TMP_TABLE::sj_weedout_delete_rows()
4512 {
4513 DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_delete_rows");
4514 if (tmp_table)
4515 {
4516 int rc= tmp_table->file->ha_delete_all_rows();
4517 DBUG_RETURN(rc);
4518 }
4519 have_degenerate_row= FALSE;
4520 DBUG_RETURN(0);
4521 }
4522
4523
4524 /*
4525 SemiJoinDuplicateElimination: Weed out duplicate row combinations
4526
4527 SYNPOSIS
4528 sj_weedout_check_row()
4529 thd Thread handle
4530
4531 DESCRIPTION
4532 Try storing current record combination of outer tables (i.e. their
4533 rowids) in the temporary table. This records the fact that we've seen
4534 this record combination and also tells us if we've seen it before.
4535
4536 RETURN
4537 -1 Error
4538 1 The row combination is a duplicate (discard it)
4539 0 The row combination is not a duplicate (continue)
4540 */
4541
sj_weedout_check_row(THD * thd)4542 int SJ_TMP_TABLE::sj_weedout_check_row(THD *thd)
4543 {
4544 int error;
4545 SJ_TMP_TABLE::TAB *tab= tabs;
4546 SJ_TMP_TABLE::TAB *tab_end= tabs_end;
4547 uchar *ptr;
4548 uchar *nulls_ptr;
4549
4550 DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_check_row");
4551
4552 if (is_degenerate)
4553 {
4554 if (have_degenerate_row)
4555 DBUG_RETURN(1);
4556
4557 have_degenerate_row= TRUE;
4558 DBUG_RETURN(0);
4559 }
4560
4561 ptr= tmp_table->record[0] + 1;
4562
4563 /* Put the the rowids tuple into table->record[0]: */
4564
4565 // 1. Store the length
4566 if (((Field_varstring*)(tmp_table->field[0]))->length_bytes == 1)
4567 {
4568 *ptr= (uchar)(rowid_len + null_bytes);
4569 ptr++;
4570 }
4571 else
4572 {
4573 int2store(ptr, rowid_len + null_bytes);
4574 ptr += 2;
4575 }
4576
4577 nulls_ptr= ptr;
4578 // 2. Zero the null bytes
4579 if (null_bytes)
4580 {
4581 bzero(ptr, null_bytes);
4582 ptr += null_bytes;
4583 }
4584
4585 // 3. Put the rowids
4586 for (uint i=0; tab != tab_end; tab++, i++)
4587 {
4588 handler *h= tab->join_tab->table->file;
4589 if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
4590 {
4591 /* It's a NULL-complemented row */
4592 *(nulls_ptr + tab->null_byte) |= tab->null_bit;
4593 bzero(ptr + tab->rowid_offset, h->ref_length);
4594 }
4595 else
4596 {
4597 /* Copy the rowid value */
4598 memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
4599 }
4600 }
4601
4602 error= tmp_table->file->ha_write_tmp_row(tmp_table->record[0]);
4603 if (unlikely(error))
4604 {
4605 /* create_internal_tmp_table_from_heap will generate error if needed */
4606 if (!tmp_table->file->is_fatal_error(error, HA_CHECK_DUP))
4607 DBUG_RETURN(1); /* Duplicate */
4608
4609 bool is_duplicate;
4610 if (create_internal_tmp_table_from_heap(thd, tmp_table, start_recinfo,
4611 &recinfo, error, 1, &is_duplicate))
4612 DBUG_RETURN(-1);
4613 if (is_duplicate)
4614 DBUG_RETURN(1);
4615 }
4616 DBUG_RETURN(0);
4617 }
4618
4619
init_dups_weedout(JOIN * join,uint first_table,int first_fanout_table,uint n_tables)4620 int init_dups_weedout(JOIN *join, uint first_table, int first_fanout_table, uint n_tables)
4621 {
4622 THD *thd= join->thd;
4623 DBUG_ENTER("init_dups_weedout");
4624 SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
4625 SJ_TMP_TABLE::TAB *last_tab= sjtabs;
4626 uint jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
4627 uint jt_null_bits= 0; // # null bits in tuple bytes
4628 /*
4629 Walk through the range and remember
4630 - tables that need their rowids to be put into temptable
4631 - the last outer table
4632 */
4633 for (JOIN_TAB *j=join->join_tab + first_table;
4634 j < join->join_tab + first_table + n_tables; j++)
4635 {
4636 if (sj_table_is_included(join, j))
4637 {
4638 last_tab->join_tab= j;
4639 last_tab->rowid_offset= jt_rowid_offset;
4640 jt_rowid_offset += j->table->file->ref_length;
4641 if (j->table->maybe_null)
4642 {
4643 last_tab->null_byte= jt_null_bits / 8;
4644 last_tab->null_bit= jt_null_bits++;
4645 }
4646 last_tab++;
4647 j->table->prepare_for_position();
4648 j->keep_current_rowid= TRUE;
4649 }
4650 }
4651
4652 SJ_TMP_TABLE *sjtbl;
4653 if (jt_rowid_offset) /* Temptable has at least one rowid */
4654 {
4655 size_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
4656 if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
4657 !(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
4658 DBUG_RETURN(TRUE); /* purecov: inspected */
4659 memcpy(sjtbl->tabs, sjtabs, tabs_size);
4660 sjtbl->is_degenerate= FALSE;
4661 sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
4662 sjtbl->rowid_len= jt_rowid_offset;
4663 sjtbl->null_bits= jt_null_bits;
4664 sjtbl->null_bytes= (jt_null_bits + 7)/8;
4665 if (sjtbl->create_sj_weedout_tmp_table(thd))
4666 DBUG_RETURN(TRUE);
4667 join->sj_tmp_tables.push_back(sjtbl->tmp_table, thd->mem_root);
4668 }
4669 else
4670 {
4671 /*
4672 This is a special case where the entire subquery predicate does
4673 not depend on anything at all, ie this is
4674 WHERE const IN (uncorrelated select)
4675 */
4676 if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))))
4677 DBUG_RETURN(TRUE); /* purecov: inspected */
4678 sjtbl->tmp_table= NULL;
4679 sjtbl->is_degenerate= TRUE;
4680 sjtbl->have_degenerate_row= FALSE;
4681 }
4682
4683 sjtbl->next_flush_table= join->join_tab[first_table].flush_weedout_table;
4684 join->join_tab[first_table].flush_weedout_table= sjtbl;
4685 join->join_tab[first_fanout_table].first_weedout_table= sjtbl;
4686 join->join_tab[first_table + n_tables - 1].check_weed_out_table= sjtbl;
4687 DBUG_RETURN(0);
4688 }
4689
4690
4691 /*
4692 @brief
4693 Set up semi-join Loose Scan strategy for execution
4694
4695 @detail
4696 Other strategies are done in setup_semijoin_dups_elimination(),
4697 however, we need to set up Loose Scan earlier, before make_join_select is
4698 called. This is to prevent make_join_select() from switching full index
4699 scans into quick selects (which will break Loose Scan access).
4700
4701 @return
4702 0 OK
4703 1 Error
4704 */
4705
setup_semijoin_loosescan(JOIN * join)4706 int setup_semijoin_loosescan(JOIN *join)
4707 {
4708 uint i;
4709 DBUG_ENTER("setup_semijoin_loosescan");
4710
4711 POSITION *pos= join->best_positions + join->const_tables;
4712 for (i= join->const_tables ; i < join->top_join_tab_count; )
4713 {
4714 JOIN_TAB *tab=join->join_tab + i;
4715 switch (pos->sj_strategy) {
4716 case SJ_OPT_MATERIALIZE:
4717 case SJ_OPT_MATERIALIZE_SCAN:
4718 i+= 1; /* join tabs are embedded in the nest */
4719 pos += pos->n_sj_tables;
4720 break;
4721 case SJ_OPT_LOOSE_SCAN:
4722 {
4723 /* We jump from the last table to the first one */
4724 tab->loosescan_match_tab= tab + pos->n_sj_tables - 1;
4725
4726 /* LooseScan requires records to be produced in order */
4727 if (tab->select && tab->select->quick)
4728 tab->select->quick->need_sorted_output();
4729
4730 for (uint j= i; j < i + pos->n_sj_tables; j++)
4731 join->join_tab[j].inside_loosescan_range= TRUE;
4732
4733 /* Calculate key length */
4734 uint keylen= 0;
4735 uint keyno= pos->loosescan_picker.loosescan_key;
4736 for (uint kp=0; kp < pos->loosescan_picker.loosescan_parts; kp++)
4737 keylen += tab->table->key_info[keyno].key_part[kp].store_length;
4738
4739 tab->loosescan_key= keyno;
4740 tab->loosescan_key_len= keylen;
4741 if (pos->n_sj_tables > 1)
4742 tab[pos->n_sj_tables - 1].do_firstmatch= tab;
4743 i+= pos->n_sj_tables;
4744 pos+= pos->n_sj_tables;
4745 break;
4746 }
4747 default:
4748 {
4749 i++;
4750 pos++;
4751 break;
4752 }
4753 }
4754 }
4755 DBUG_RETURN(FALSE);
4756 }
4757
4758
4759 /*
4760 Setup the strategies to eliminate semi-join duplicates.
4761
4762 SYNOPSIS
4763 setup_semijoin_dups_elimination()
4764 join Join to process
4765 options Join options (needed to see if join buffering will be
4766 used or not)
4767 no_jbuf_after Another bit of information re where join buffering will
4768 be used.
4769
4770 DESCRIPTION
4771 Setup the strategies to eliminate semi-join duplicates. ATM there are 4
4772 strategies:
4773
4774 1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
4775 of row combinations)
4776 2. FirstMatch (pick only the 1st matching row combination of inner tables)
4777 3. LooseScan (scanning the sj-inner table in a way that groups duplicates
4778 together and picking the 1st one)
4779 4. SJ-Materialization.
4780
4781 The join order has "duplicate-generating ranges", and every range is
4782 served by one strategy or a combination of FirstMatch with with some
4783 other strategy.
4784
4785 "Duplicate-generating range" is defined as a range within the join order
4786 that contains all of the inner tables of a semi-join. All ranges must be
4787 disjoint, if tables of several semi-joins are interleaved, then the ranges
4788 are joined together, which is equivalent to converting
4789 SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
4790 to
4791 SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
4792 .
4793
4794 Applicability conditions are as follows:
4795
4796 DuplicateWeedout strategy
4797 ~~~~~~~~~~~~~~~~~~~~~~~~~
4798
4799 (ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
4800 +------+ +=========================+ +---+
4801 (1) (2) (3)
4802
4803 (1) - Prefix of OuterTables (those that participate in
4804 IN-equality and/or are correlated with subquery) and outer
4805 Non-correlated tables.
4806 (2) - The handled range. The range starts with the first sj-inner
4807 table, and covers all sj-inner and outer tables
4808 Within the range, Inner, Outer, outer non-correlated tables
4809 may follow in any order.
4810 (3) - The suffix of outer non-correlated tables.
4811
4812 FirstMatch strategy
4813 ~~~~~~~~~~~~~~~~~~~
4814
4815 (ot|nt)* [ it ((it|nt)* it) ] (nt)*
4816 +------+ +==================+ +---+
4817 (1) (2) (3)
4818
4819 (1) - Prefix of outer and non-correlated tables
4820 (2) - The handled range, which may contain only inner and
4821 non-correlated tables.
4822 (3) - The suffix of outer non-correlated tables.
4823
4824 LooseScan strategy
4825 ~~~~~~~~~~~~~~~~~~
4826
4827 (ot|ct|nt) [ loosescan_tbl (ot|nt|it)* it ] (ot|nt)*
4828 +--------+ +===========+ +=============+ +------+
4829 (1) (2) (3) (4)
4830
4831 (1) - Prefix that may contain any outer tables. The prefix must contain
4832 all the non-trivially correlated outer tables. (non-trivially means
4833 that the correlation is not just through the IN-equality).
4834
4835 (2) - Inner table for which the LooseScan scan is performed.
4836
4837 (3) - The remainder of the duplicate-generating range. It is served by
4838 application of FirstMatch strategy, with the exception that
4839 outer IN-correlated tables are considered to be non-correlated.
4840
4841 (4) - THe suffix of outer and outer non-correlated tables.
4842
4843
4844 The choice between the strategies is made by the join optimizer (see
4845 advance_sj_state() and fix_semijoin_strategies_for_picked_join_order()).
4846 This function sets up all fields/structures/etc needed for execution except
4847 for setup/initialization of semi-join materialization which is done in
4848 setup_sj_materialization() (todo: can't we move that to here also?)
4849
4850 RETURN
4851 FALSE OK
4852 TRUE Out of memory error
4853 */
4854
setup_semijoin_dups_elimination(JOIN * join,ulonglong options,uint no_jbuf_after)4855 int setup_semijoin_dups_elimination(JOIN *join, ulonglong options,
4856 uint no_jbuf_after)
4857 {
4858 uint i;
4859 DBUG_ENTER("setup_semijoin_dups_elimination");
4860
4861 join->complex_firstmatch_tables= table_map(0);
4862
4863 POSITION *pos= join->best_positions + join->const_tables;
4864 for (i= join->const_tables ; i < join->top_join_tab_count; )
4865 {
4866 JOIN_TAB *tab=join->join_tab + i;
4867 switch (pos->sj_strategy) {
4868 case SJ_OPT_MATERIALIZE:
4869 case SJ_OPT_MATERIALIZE_SCAN:
4870 /* Do nothing */
4871 i+= 1;// It used to be pos->n_sj_tables, but now they are embedded in a nest
4872 pos += pos->n_sj_tables;
4873 break;
4874 case SJ_OPT_LOOSE_SCAN:
4875 {
4876 /* Setup already handled by setup_semijoin_loosescan */
4877 i+= pos->n_sj_tables;
4878 pos+= pos->n_sj_tables;
4879 break;
4880 }
4881 case SJ_OPT_DUPS_WEEDOUT:
4882 {
4883 /*
4884 Check for join buffering. If there is one, move the first table
4885 forwards, but do not destroy other duplicate elimination methods.
4886 */
4887 uint first_table= i;
4888
4889 uint join_cache_level= join->thd->variables.join_cache_level;
4890 for (uint j= i; j < i + pos->n_sj_tables; j++)
4891 {
4892 /*
4893 When we'll properly take join buffering into account during
4894 join optimization, the below check should be changed to
4895 "if (join->best_positions[j].use_join_buffer &&
4896 j <= no_jbuf_after)".
4897 For now, use a rough criteria:
4898 */
4899 JOIN_TAB *js_tab=join->join_tab + j;
4900 if (j != join->const_tables && js_tab->use_quick != 2 &&
4901 j <= no_jbuf_after &&
4902 ((js_tab->type == JT_ALL && join_cache_level != 0) ||
4903 (join_cache_level > 2 && (js_tab->type == JT_REF ||
4904 js_tab->type == JT_EQ_REF))))
4905 {
4906 /* Looks like we'll be using join buffer */
4907 first_table= join->const_tables;
4908 /*
4909 Make sure that possible sorting of rows from the head table
4910 is not to be employed.
4911 */
4912 if (join->get_sort_by_join_tab())
4913 {
4914 join->simple_order= 0;
4915 join->simple_group= 0;
4916 join->need_tmp= join->test_if_need_tmp_table();
4917 }
4918 break;
4919 }
4920 }
4921
4922 init_dups_weedout(join, first_table, i, i + pos->n_sj_tables - first_table);
4923 i+= pos->n_sj_tables;
4924 pos+= pos->n_sj_tables;
4925 break;
4926 }
4927 case SJ_OPT_FIRST_MATCH:
4928 {
4929 JOIN_TAB *j;
4930 JOIN_TAB *jump_to= tab-1;
4931
4932 bool complex_range= FALSE;
4933 table_map tables_in_range= table_map(0);
4934
4935 for (j= tab; j != tab + pos->n_sj_tables; j++)
4936 {
4937 tables_in_range |= j->table->map;
4938 if (!j->emb_sj_nest)
4939 {
4940 /*
4941 Got a table that's not within any semi-join nest. This is a case
4942 like this:
4943
4944 SELECT * FROM ot1, nt1 WHERE ot1.col IN (SELECT expr FROM it1, it2)
4945
4946 with a join order of
4947
4948 +----- FirstMatch range ----+
4949 | |
4950 ot1 it1 nt1 nt2 it2 it3 ...
4951 | ^
4952 | +-------- 'j' points here
4953 +------------- SJ_OPT_FIRST_MATCH was set for this table as
4954 it's the first one that produces duplicates
4955
4956 */
4957 DBUG_ASSERT(j != tab); /* table ntX must have an itX before it */
4958
4959 /*
4960 If the table right before us is an inner table (like it1 in the
4961 picture), it should be set to jump back to previous outer-table
4962 */
4963 if (j[-1].emb_sj_nest)
4964 j[-1].do_firstmatch= jump_to;
4965
4966 jump_to= j; /* Jump back to us */
4967 complex_range= TRUE;
4968 }
4969 else
4970 {
4971 j->first_sj_inner_tab= tab;
4972 j->last_sj_inner_tab= tab + pos->n_sj_tables - 1;
4973 }
4974 }
4975 j[-1].do_firstmatch= jump_to;
4976 i+= pos->n_sj_tables;
4977 pos+= pos->n_sj_tables;
4978
4979 if (complex_range)
4980 join->complex_firstmatch_tables|= tables_in_range;
4981 break;
4982 }
4983 case SJ_OPT_NONE:
4984 i++;
4985 pos++;
4986 break;
4987 }
4988 }
4989 DBUG_RETURN(FALSE);
4990 }
4991
4992
4993 /*
4994 Destroy all temporary tables created by NL-semijoin runtime
4995 */
4996
destroy_sj_tmp_tables(JOIN * join)4997 void destroy_sj_tmp_tables(JOIN *join)
4998 {
4999 List_iterator<TABLE> it(join->sj_tmp_tables);
5000 TABLE *table;
5001 while ((table= it++))
5002 {
5003 /*
5004 SJ-Materialization tables are initialized for either sequential reading
5005 or index lookup, DuplicateWeedout tables are not initialized for read
5006 (we only write to them), so need to call ha_index_or_rnd_end.
5007 */
5008 table->file->ha_index_or_rnd_end();
5009 free_tmp_table(join->thd, table);
5010 }
5011 join->sj_tmp_tables.empty();
5012 join->sjm_info_list.empty();
5013 }
5014
5015
5016 /*
5017 Remove all records from all temp tables used by NL-semijoin runtime
5018
5019 SYNOPSIS
5020 clear_sj_tmp_tables()
5021 join The join to remove tables for
5022
5023 DESCRIPTION
5024 Remove all records from all temp tables used by NL-semijoin runtime. This
5025 must be done before every join re-execution.
5026 */
5027
clear_sj_tmp_tables(JOIN * join)5028 int clear_sj_tmp_tables(JOIN *join)
5029 {
5030 int res;
5031 List_iterator<TABLE> it(join->sj_tmp_tables);
5032 TABLE *table;
5033 while ((table= it++))
5034 {
5035 if ((res= table->file->ha_delete_all_rows()))
5036 return res; /* purecov: inspected */
5037 }
5038
5039 SJ_MATERIALIZATION_INFO *sjm;
5040 List_iterator<SJ_MATERIALIZATION_INFO> it2(join->sjm_info_list);
5041 while ((sjm= it2++))
5042 {
5043 sjm->materialized= FALSE;
5044 }
5045 return 0;
5046 }
5047
5048
5049 /*
5050 Check if the table's rowid is included in the temptable
5051
5052 SYNOPSIS
5053 sj_table_is_included()
5054 join The join
5055 join_tab The table to be checked
5056
5057 DESCRIPTION
5058 SemiJoinDuplicateElimination: check the table's rowid should be included
5059 in the temptable. This is so if
5060
5061 1. The table is not embedded within some semi-join nest
5062 2. The has been pulled out of a semi-join nest, or
5063
5064 3. The table is functionally dependent on some previous table
5065
5066 [4. This is also true for constant tables that can't be
5067 NULL-complemented but this function is not called for such tables]
5068
5069 RETURN
5070 TRUE - Include table's rowid
5071 FALSE - Don't
5072 */
5073
sj_table_is_included(JOIN * join,JOIN_TAB * join_tab)5074 static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
5075 {
5076 if (join_tab->emb_sj_nest)
5077 return FALSE;
5078
5079 /* Check if this table is functionally dependent on the tables that
5080 are within the same outer join nest
5081 */
5082 TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;
5083 if (join_tab->type == JT_EQ_REF)
5084 {
5085 table_map depends_on= 0;
5086 uint idx;
5087
5088 for (uint kp= 0; kp < join_tab->ref.key_parts; kp++)
5089 depends_on |= join_tab->ref.items[kp]->used_tables();
5090
5091 Table_map_iterator it(depends_on & ~PSEUDO_TABLE_BITS);
5092 while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
5093 {
5094 JOIN_TAB *ref_tab= join->map2table[idx];
5095 if (embedding != ref_tab->table->pos_in_table_list->embedding)
5096 return TRUE;
5097 }
5098 /* Ok, functionally dependent */
5099 return FALSE;
5100 }
5101 /* Not functionally dependent => need to include*/
5102 return TRUE;
5103 }
5104
5105
5106 /*
5107 Index lookup-based subquery: save some flags for EXPLAIN output
5108
5109 SYNOPSIS
5110 save_index_subquery_explain_info()
5111 join_tab Subquery's join tab (there is only one as index lookup is
5112 only used for subqueries that are single-table SELECTs)
5113 where Subquery's WHERE clause
5114
5115 DESCRIPTION
5116 For index lookup-based subquery (i.e. one executed with
5117 subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
5118 check its EXPLAIN output row should contain
5119 "Using index" (TAB_INFO_FULL_SCAN_ON_NULL)
5120 "Using Where" (TAB_INFO_USING_WHERE)
5121 "Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
5122 and set appropriate flags in join_tab->packed_info.
5123 */
5124
save_index_subquery_explain_info(JOIN_TAB * join_tab,Item * where)5125 static void save_index_subquery_explain_info(JOIN_TAB *join_tab, Item* where)
5126 {
5127 join_tab->packed_info= TAB_INFO_HAVE_VALUE;
5128 if (join_tab->table->covering_keys.is_set(join_tab->ref.key))
5129 join_tab->packed_info |= TAB_INFO_USING_INDEX;
5130 if (where)
5131 join_tab->packed_info |= TAB_INFO_USING_WHERE;
5132 for (uint i = 0; i < join_tab->ref.key_parts; i++)
5133 {
5134 if (join_tab->ref.cond_guards[i])
5135 {
5136 join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
5137 break;
5138 }
5139 }
5140 }
5141
5142
5143 /*
5144 Check if the join can be rewritten to [unique_]indexsubquery_engine
5145
5146 DESCRIPTION
5147 Check if the join can be changed into [unique_]indexsubquery_engine.
5148
5149 The check is done after join optimization, the idea is that if the join
5150 has only one table and uses a [eq_]ref access generated from subselect's
5151 IN-equality then we replace it with a subselect_indexsubquery_engine or a
5152 subselect_uniquesubquery_engine.
5153
5154 RETURN
5155 0 - Ok, rewrite done (stop join optimization and return)
5156 1 - Fatal error (stop join optimization and return)
5157 -1 - No rewrite performed, continue with join optimization
5158 */
5159
rewrite_to_index_subquery_engine(JOIN * join)5160 int rewrite_to_index_subquery_engine(JOIN *join)
5161 {
5162 THD *thd= join->thd;
5163 JOIN_TAB* join_tab=join->join_tab;
5164 SELECT_LEX_UNIT *unit= join->unit;
5165 DBUG_ENTER("rewrite_to_index_subquery_engine");
5166
5167 /*
5168 is this simple IN subquery?
5169 */
5170 /* TODO: In order to use these more efficient subquery engines in more cases,
5171 the following problems need to be solved:
5172 - the code that removes GROUP BY (group_list), also adds an ORDER BY
5173 (order), thus GROUP BY queries (almost?) never pass through this branch.
5174 Solution: remove the test below '!join->order', because we remove the
5175 ORDER clase for subqueries anyway.
5176 - in order to set a more efficient engine, the optimizer needs to both
5177 decide to remove GROUP BY, *and* select one of the JT_[EQ_]REF[_OR_NULL]
5178 access methods, *and* loose scan should be more expensive or
5179 inapliccable. When is that possible?
5180 - Consider expanding the applicability of this rewrite for loose scan
5181 for group by queries.
5182 */
5183 if (!join->group_list && !join->order &&
5184 join->unit->item &&
5185 join->unit->item->substype() == Item_subselect::IN_SUBS &&
5186 join->table_count == 1 && join->conds &&
5187 !join->unit->is_unit_op())
5188 {
5189 if (!join->having)
5190 {
5191 Item *where= join->conds;
5192 if (join_tab[0].type == JT_EQ_REF &&
5193 join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
5194 {
5195 remove_subq_pushed_predicates(join, &where);
5196 save_index_subquery_explain_info(join_tab, where);
5197 join_tab[0].type= JT_UNIQUE_SUBQUERY;
5198 join->error= 0;
5199 DBUG_RETURN(unit->item->
5200 change_engine(new
5201 subselect_uniquesubquery_engine(thd,
5202 join_tab,
5203 unit->item,
5204 where)));
5205 }
5206 else if (join_tab[0].type == JT_REF &&
5207 join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
5208 {
5209 remove_subq_pushed_predicates(join, &where);
5210 save_index_subquery_explain_info(join_tab, where);
5211 join_tab[0].type= JT_INDEX_SUBQUERY;
5212 join->error= 0;
5213 DBUG_RETURN(unit->item->
5214 change_engine(new
5215 subselect_indexsubquery_engine(thd,
5216 join_tab,
5217 unit->item,
5218 where,
5219 NULL,
5220 0)));
5221 }
5222 } else if (join_tab[0].type == JT_REF_OR_NULL &&
5223 join_tab[0].ref.items[0]->name.str == in_left_expr_name.str &&
5224 join->having->name.str == in_having_cond.str)
5225 {
5226 join_tab[0].type= JT_INDEX_SUBQUERY;
5227 join->error= 0;
5228 join->conds= remove_additional_cond(join->conds);
5229 save_index_subquery_explain_info(join_tab, join->conds);
5230 DBUG_RETURN(unit->item->
5231 change_engine(new subselect_indexsubquery_engine(thd,
5232 join_tab,
5233 unit->item,
5234 join->conds,
5235 join->having,
5236 1)));
5237 }
5238 }
5239
5240 DBUG_RETURN(-1); /* Haven't done the rewrite */
5241 }
5242
5243
5244 /**
5245 Remove additional condition inserted by IN/ALL/ANY transformation.
5246
5247 @param conds condition for processing
5248
5249 @return
5250 new conditions
5251 */
5252
remove_additional_cond(Item * conds)5253 static Item *remove_additional_cond(Item* conds)
5254 {
5255 if (conds->name.str == in_additional_cond.str)
5256 return 0;
5257 if (conds->type() == Item::COND_ITEM)
5258 {
5259 Item_cond *cnd= (Item_cond*) conds;
5260 List_iterator<Item> li(*(cnd->argument_list()));
5261 Item *item;
5262 while ((item= li++))
5263 {
5264 if (item->name.str == in_additional_cond.str)
5265 {
5266 li.remove();
5267 if (cnd->argument_list()->elements == 1)
5268 return cnd->argument_list()->head();
5269 return conds;
5270 }
5271 }
5272 }
5273 return conds;
5274 }
5275
5276
5277 /*
5278 Remove the predicates pushed down into the subquery
5279
5280 SYNOPSIS
5281 remove_subq_pushed_predicates()
5282 where IN Must be NULL
5283 OUT The remaining WHERE condition, or NULL
5284
5285 DESCRIPTION
5286 Given that this join will be executed using (unique|index)_subquery,
5287 without "checking NULL", remove the predicates that were pushed down
5288 into the subquery.
5289
5290 If the subquery compares scalar values, we can remove the condition that
5291 was wrapped into trig_cond (it will be checked when needed by the subquery
5292 engine)
5293
5294 If the subquery compares row values, we need to keep the wrapped
5295 equalities in the WHERE clause: when the left (outer) tuple has both NULL
5296 and non-NULL values, we'll do a full table scan and will rely on the
5297 equalities corresponding to non-NULL parts of left tuple to filter out
5298 non-matching records.
5299
5300 TODO: We can remove the equalities that will be guaranteed to be true by the
5301 fact that subquery engine will be using index lookup. This must be done only
5302 for cases where there are no conversion errors of significance, e.g. 257
5303 that is searched in a byte. But this requires homogenization of the return
5304 codes of all Field*::store() methods.
5305 */
5306
remove_subq_pushed_predicates(JOIN * join,Item ** where)5307 static void remove_subq_pushed_predicates(JOIN *join, Item **where)
5308 {
5309 if (join->conds->type() == Item::FUNC_ITEM &&
5310 ((Item_func *)join->conds)->functype() == Item_func::EQ_FUNC &&
5311 ((Item_func *)join->conds)->arguments()[0]->type() == Item::REF_ITEM &&
5312 ((Item_func *)join->conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
5313 test_if_ref (join->conds,
5314 (Item_field *)((Item_func *)join->conds)->arguments()[1],
5315 ((Item_func *)join->conds)->arguments()[0]))
5316 {
5317 *where= 0;
5318 return;
5319 }
5320 }
5321
5322
5323
5324
5325 /**
5326 Optimize all subqueries of a query that were not flattened into a semijoin.
5327
5328 @details
5329 Optimize all immediate children subqueries of a query.
5330
5331 This phase must be called after substitute_for_best_equal_field() because
5332 that function may replace items with other items from a multiple equality,
5333 and we need to reference the correct items in the index access method of the
5334 IN predicate.
5335
5336 @return Operation status
5337 @retval FALSE success.
5338 @retval TRUE error occurred.
5339 */
5340
optimize_unflattened_subqueries()5341 bool JOIN::optimize_unflattened_subqueries()
5342 {
5343 return select_lex->optimize_unflattened_subqueries(false);
5344 }
5345
5346 /**
5347 Optimize all constant subqueries of a query that were not flattened into
5348 a semijoin.
5349
5350 @details
5351 Similar to other constant conditions, constant subqueries can be used in
5352 various constant optimizations. Having optimized constant subqueries before
5353 these constant optimizations, makes it possible to estimate if a subquery
5354 is "cheap" enough to be executed during the optimization phase.
5355
5356 Constant subqueries can be optimized and evaluated independent of the outer
5357 query, therefore if const_only = true, this method can be called early in
5358 the optimization phase of the outer query.
5359
5360 @return Operation status
5361 @retval FALSE success.
5362 @retval TRUE error occurred.
5363 */
5364
optimize_constant_subqueries()5365 bool JOIN::optimize_constant_subqueries()
5366 {
5367 ulonglong save_options= select_lex->options;
5368 bool res;
5369 /*
5370 Constant subqueries may be executed during the optimization phase.
5371 In EXPLAIN mode the optimizer doesn't initialize many of the data structures
5372 needed for execution. In order to make it possible to execute subqueries
5373 during optimization, constant subqueries must be optimized for execution,
5374 not for EXPLAIN.
5375 */
5376 select_lex->options&= ~SELECT_DESCRIBE;
5377 res= select_lex->optimize_unflattened_subqueries(true);
5378 select_lex->options= save_options;
5379 return res;
5380 }
5381
5382
5383 /*
5384 Join tab execution startup function.
5385
5386 SYNOPSIS
5387 join_tab_execution_startup()
5388 tab Join tab to perform startup actions for
5389
5390 DESCRIPTION
5391 Join tab execution startup function. This is different from
5392 tab->read_first_record in the regard that this has actions that are to be
5393 done once per join execution.
5394
5395 Currently there are only two possible startup functions, so we have them
5396 both here inside if (...) branches. In future we could switch to function
5397 pointers.
5398
5399 TODO: consider moving this together with JOIN_TAB::preread_init
5400
5401 RETURN
5402 NESTED_LOOP_OK - OK
5403 NESTED_LOOP_ERROR| NESTED_LOOP_KILLED - Error, abort the join execution
5404 */
5405
join_tab_execution_startup(JOIN_TAB * tab)5406 enum_nested_loop_state join_tab_execution_startup(JOIN_TAB *tab)
5407 {
5408 Item_in_subselect *in_subs;
5409 DBUG_ENTER("join_tab_execution_startup");
5410
5411 if (tab->table->pos_in_table_list &&
5412 (in_subs= tab->table->pos_in_table_list->jtbm_subselect))
5413 {
5414 /* It's a non-merged SJM nest */
5415 DBUG_ASSERT(in_subs->engine->engine_type() ==
5416 subselect_engine::HASH_SJ_ENGINE);
5417 subselect_hash_sj_engine *hash_sj_engine=
5418 ((subselect_hash_sj_engine*)in_subs->engine);
5419 if (!hash_sj_engine->is_materialized)
5420 {
5421 hash_sj_engine->materialize_join->exec();
5422 hash_sj_engine->is_materialized= TRUE;
5423
5424 if (unlikely(hash_sj_engine->materialize_join->error) ||
5425 unlikely(tab->join->thd->is_fatal_error))
5426 DBUG_RETURN(NESTED_LOOP_ERROR);
5427 }
5428 }
5429 else if (tab->bush_children)
5430 {
5431 /* It's a merged SJM nest */
5432 enum_nested_loop_state rc;
5433 SJ_MATERIALIZATION_INFO *sjm= tab->bush_children->start->emb_sj_nest->sj_mat_info;
5434
5435 if (!sjm->materialized)
5436 {
5437 JOIN *join= tab->join;
5438 JOIN_TAB *join_tab= tab->bush_children->start;
5439 JOIN_TAB *save_return_tab= join->return_tab;
5440 /*
5441 Now run the join for the inner tables. The first call is to run the
5442 join, the second one is to signal EOF (this is essential for some
5443 join strategies, e.g. it will make join buffering flush the records)
5444 */
5445 if ((rc= sub_select(join, join_tab, FALSE/* no EOF */)) < 0 ||
5446 (rc= sub_select(join, join_tab, TRUE/* now EOF */)) < 0)
5447 {
5448 join->return_tab= save_return_tab;
5449 DBUG_RETURN(rc); /* it's NESTED_LOOP_(ERROR|KILLED)*/
5450 }
5451 join->return_tab= save_return_tab;
5452 sjm->materialized= TRUE;
5453 }
5454 }
5455
5456 DBUG_RETURN(NESTED_LOOP_OK);
5457 }
5458
5459
5460 /*
5461 Create a dummy temporary table, useful only for the sake of having a
5462 TABLE* object with map,tablenr and maybe_null properties.
5463
5464 This is used by non-mergeable semi-join materilization code to handle
5465 degenerate cases where materialized subquery produced "Impossible WHERE"
5466 and thus wasn't materialized.
5467 */
5468
create_dummy_tmp_table(THD * thd)5469 TABLE *create_dummy_tmp_table(THD *thd)
5470 {
5471 DBUG_ENTER("create_dummy_tmp_table");
5472 TABLE *table;
5473 TMP_TABLE_PARAM sjm_table_param;
5474 sjm_table_param.init();
5475 sjm_table_param.field_count= 1;
5476 List<Item> sjm_table_cols;
5477 const LEX_CSTRING dummy_name= { STRING_WITH_LEN("dummy") };
5478 Item *column_item= new (thd->mem_root) Item_int(thd, 1);
5479 if (!column_item)
5480 DBUG_RETURN(NULL);
5481
5482 sjm_table_cols.push_back(column_item, thd->mem_root);
5483 if (!(table= create_tmp_table(thd, &sjm_table_param,
5484 sjm_table_cols, (ORDER*) 0,
5485 TRUE /* distinct */,
5486 1, /*save_sum_fields*/
5487 thd->variables.option_bits |
5488 TMP_TABLE_ALL_COLUMNS,
5489 HA_POS_ERROR /*rows_limit */,
5490 &dummy_name, TRUE /* Do not open */)))
5491 {
5492 DBUG_RETURN(NULL);
5493 }
5494 DBUG_RETURN(table);
5495 }
5496
5497
5498 /*
5499 A class that is used to catch one single tuple that is sent to the join
5500 output, and save it in Item_cache element(s).
5501
5502 It is very similar to select_singlerow_subselect but doesn't require a
5503 Item_singlerow_subselect item.
5504 */
5505
5506 class select_value_catcher :public select_subselect
5507 {
5508 public:
select_value_catcher(THD * thd_arg,Item_subselect * item_arg)5509 select_value_catcher(THD *thd_arg, Item_subselect *item_arg):
5510 select_subselect(thd_arg, item_arg)
5511 {}
5512 int send_data(List<Item> &items);
5513 int setup(List<Item> *items);
5514 bool assigned; /* TRUE <=> we've caught a value */
5515 uint n_elements; /* How many elements we get */
5516 Item_cache **row; /* Array of cache elements */
5517 };
5518
5519
setup(List<Item> * items)5520 int select_value_catcher::setup(List<Item> *items)
5521 {
5522 assigned= FALSE;
5523 n_elements= items->elements;
5524
5525 if (!(row= (Item_cache**) thd->alloc(sizeof(Item_cache*) * n_elements)))
5526 return TRUE;
5527
5528 Item *sel_item;
5529 List_iterator<Item> li(*items);
5530 for (uint i= 0; (sel_item= li++); i++)
5531 {
5532 if (!(row[i]= sel_item->get_cache(thd)))
5533 return TRUE;
5534 row[i]->setup(thd, sel_item);
5535 }
5536 return FALSE;
5537 }
5538
5539
send_data(List<Item> & items)5540 int select_value_catcher::send_data(List<Item> &items)
5541 {
5542 DBUG_ENTER("select_value_catcher::send_data");
5543 DBUG_ASSERT(!assigned);
5544 DBUG_ASSERT(items.elements == n_elements);
5545
5546 if (unit->offset_limit_cnt)
5547 { // Using limit offset,count
5548 unit->offset_limit_cnt--;
5549 DBUG_RETURN(0);
5550 }
5551
5552 Item *val_item;
5553 List_iterator_fast<Item> li(items);
5554 for (uint i= 0; (val_item= li++); i++)
5555 {
5556 row[i]->store(val_item);
5557 row[i]->cache_value();
5558 }
5559 assigned= TRUE;
5560 DBUG_RETURN(0);
5561 }
5562
5563
5564 /*
5565 Setup JTBM join tabs for execution
5566 */
5567
setup_jtbm_semi_joins(JOIN * join,List<TABLE_LIST> * join_list,Item ** join_where)5568 bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list,
5569 Item **join_where)
5570 {
5571 TABLE_LIST *table;
5572 NESTED_JOIN *nested_join;
5573 List_iterator<TABLE_LIST> li(*join_list);
5574 THD *thd= join->thd;
5575 DBUG_ENTER("setup_jtbm_semi_joins");
5576
5577 while ((table= li++))
5578 {
5579 Item_in_subselect *item;
5580
5581 if ((item= table->jtbm_subselect))
5582 {
5583 Item_in_subselect *subq_pred= item;
5584 double rows;
5585 double read_time;
5586
5587 /*
5588 Perform optimization of the subquery, so that we know estmated
5589 - cost of materialization process
5590 - how many records will be in the materialized temp.table
5591 */
5592 if (subq_pred->optimize(&rows, &read_time))
5593 DBUG_RETURN(TRUE);
5594
5595 subq_pred->jtbm_read_time= read_time;
5596 subq_pred->jtbm_record_count=rows;
5597 JOIN *subq_join= subq_pred->unit->first_select()->join;
5598
5599 if (!subq_join->tables_list || !subq_join->table_count)
5600 {
5601 /*
5602 A special case; subquery's join is degenerate, and it either produces
5603 0 or 1 record. Examples of both cases:
5604
5605 select * from ot where col in (select ... from it where 2>3)
5606 select * from ot where col in (select MY_MIN(it.key) from it)
5607
5608 in this case, the subquery predicate has not been setup for
5609 materialization. In particular, there is no materialized temp.table.
5610 We'll now need to
5611 1. Check whether 1 or 0 records are produced, setup this as a
5612 constant join tab.
5613 2. Create a dummy temporary table, because all of the join
5614 optimization code relies on TABLE object being present (here we
5615 follow a bad tradition started by derived tables)
5616 */
5617 DBUG_ASSERT(subq_pred->engine->engine_type() ==
5618 subselect_engine::SINGLE_SELECT_ENGINE);
5619 subselect_single_select_engine *engine=
5620 (subselect_single_select_engine*)subq_pred->engine;
5621 select_value_catcher *new_sink;
5622 if (!(new_sink=
5623 new (thd->mem_root) select_value_catcher(thd, subq_pred)))
5624 DBUG_RETURN(TRUE);
5625 if (new_sink->setup(&engine->select_lex->join->fields_list) ||
5626 engine->select_lex->join->change_result(new_sink, NULL) ||
5627 engine->exec())
5628 {
5629 DBUG_RETURN(TRUE);
5630 }
5631 subq_pred->is_jtbm_const_tab= TRUE;
5632
5633 if (new_sink->assigned)
5634 {
5635 subq_pred->jtbm_const_row_found= TRUE;
5636 /*
5637 Subselect produced one row, which is saved in new_sink->row.
5638 Inject "left_expr[i] == row[i] equalities into parent's WHERE.
5639 */
5640 Item *eq_cond;
5641 for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
5642 {
5643 eq_cond= new (thd->mem_root)
5644 Item_func_eq(thd, subq_pred->left_expr->element_index(i),
5645 new_sink->row[i]);
5646 if (!eq_cond)
5647 DBUG_RETURN(1);
5648
5649 if (!((*join_where)= and_items(thd, *join_where, eq_cond)) ||
5650 (*join_where)->fix_fields(thd, join_where))
5651 DBUG_RETURN(1);
5652 }
5653 }
5654 else
5655 {
5656 /* Subselect produced no rows. Just set the flag, */
5657 subq_pred->jtbm_const_row_found= FALSE;
5658 }
5659
5660 /* Set up a dummy TABLE*, optimizer code needs JOIN_TABs to have TABLE */
5661 TABLE *dummy_table;
5662 if (!(dummy_table= create_dummy_tmp_table(thd)))
5663 DBUG_RETURN(1);
5664 table->table= dummy_table;
5665 table->table->pos_in_table_list= table;
5666 /*
5667 Note: the table created above may be freed by:
5668 1. JOIN_TAB::cleanup(), when the parent join is a regular join.
5669 2. cleanup_empty_jtbm_semi_joins(), when the parent join is a
5670 degenerate join (e.g. one with "Impossible where").
5671 */
5672 setup_table_map(table->table, table, table->jtbm_table_no);
5673 }
5674 else
5675 {
5676 DBUG_ASSERT(subq_pred->test_set_strategy(SUBS_MATERIALIZATION));
5677 subq_pred->is_jtbm_const_tab= FALSE;
5678 subselect_hash_sj_engine *hash_sj_engine=
5679 ((subselect_hash_sj_engine*)item->engine);
5680
5681 table->table= hash_sj_engine->tmp_table;
5682 table->table->pos_in_table_list= table;
5683
5684 setup_table_map(table->table, table, table->jtbm_table_no);
5685
5686 Item *sj_conds= hash_sj_engine->semi_join_conds;
5687
5688 (*join_where)= and_items(thd, *join_where, sj_conds);
5689 (*join_where)->fix_fields_if_needed(thd, join_where);
5690 }
5691 table->table->maybe_null= MY_TEST(join->mixed_implicit_grouping);
5692 }
5693
5694 if ((nested_join= table->nested_join))
5695 {
5696 if (setup_jtbm_semi_joins(join, &nested_join->join_list, join_where))
5697 DBUG_RETURN(TRUE);
5698 }
5699 }
5700 DBUG_RETURN(FALSE);
5701 }
5702
5703
5704 /*
5705 Cleanup non-merged semi-joins (JBMs) that have empty.
5706
5707 This function is to cleanups for a special case:
5708 Consider a query like
5709
5710 select * from t1 where 1=2 AND t1.col IN (select max(..) ... having 1=2)
5711
5712 For this query, optimization of subquery will short-circuit, and
5713 setup_jtbm_semi_joins() will call create_dummy_tmp_table() so that we have
5714 empty, constant temp.table to stand in as materialized temp. table.
5715
5716 Now, suppose that the upper join is also found to be degenerate. In that
5717 case, no JOIN_TAB array will be produced, and hence, JOIN::cleanup() will
5718 have a problem with cleaning up empty JTBMs (non-empty ones are cleaned up
5719 through Item::cleanup() calls).
5720 */
5721
cleanup_empty_jtbm_semi_joins(JOIN * join,List<TABLE_LIST> * join_list)5722 void cleanup_empty_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list)
5723 {
5724 List_iterator<TABLE_LIST> li(*join_list);
5725 TABLE_LIST *table;
5726 while ((table= li++))
5727 {
5728 if ((table->jtbm_subselect && table->jtbm_subselect->is_jtbm_const_tab))
5729 {
5730 if (table->table)
5731 {
5732 free_tmp_table(join->thd, table->table);
5733 table->table= NULL;
5734 }
5735 }
5736 else if (table->nested_join && table->sj_subq_pred)
5737 {
5738 cleanup_empty_jtbm_semi_joins(join, &table->nested_join->join_list);
5739 }
5740 }
5741 }
5742
5743
5744 /**
5745 Choose an optimal strategy to execute an IN/ALL/ANY subquery predicate
5746 based on cost.
5747
5748 @param join_tables the set of tables joined in the subquery
5749
5750 @notes
5751 The method chooses between the materialization and IN=>EXISTS rewrite
5752 strategies for the execution of a non-flattened subquery IN predicate.
5753 The cost-based decision is made as follows:
5754
5755 1. compute materialize_strategy_cost based on the unmodified subquery
5756 2. reoptimize the subquery taking into account the IN-EXISTS predicates
5757 3. compute in_exists_strategy_cost based on the reoptimized plan
5758 4. compare and set the cheaper strategy
5759 if (materialize_strategy_cost >= in_exists_strategy_cost)
5760 in_strategy = MATERIALIZATION
5761 else
5762 in_strategy = IN_TO_EXISTS
5763 5. if in_strategy = MATERIALIZATION and it is not possible to initialize it
5764 revert to IN_TO_EXISTS
5765 6. if (in_strategy == MATERIALIZATION)
5766 revert the subquery plan to the original one before reoptimizing
5767 else
5768 inject the IN=>EXISTS predicates into the new EXISTS subquery plan
5769
5770 The implementation itself is a bit more complicated because it takes into
5771 account two more factors:
5772 - whether the user allowed both strategies through an optimizer_switch, and
5773 - if materialization was the cheaper strategy, whether it can be executed
5774 or not.
5775
5776 @retval FALSE success.
5777 @retval TRUE error occurred.
5778 */
5779
choose_subquery_plan(table_map join_tables)5780 bool JOIN::choose_subquery_plan(table_map join_tables)
5781 {
5782 enum_reopt_result reopt_result= REOPT_NONE;
5783 Item_in_subselect *in_subs;
5784
5785 /*
5786 IN/ALL/ANY optimizations are not applicable for so called fake select
5787 (this select exists only to filter results of union if it is needed).
5788 */
5789 if (select_lex == select_lex->master_unit()->fake_select_lex)
5790 return 0;
5791
5792 if (is_in_subquery())
5793 {
5794 in_subs= (Item_in_subselect*) unit->item;
5795 if (in_subs->create_in_to_exists_cond(this))
5796 return true;
5797 }
5798 else
5799 return false;
5800
5801 /* A strategy must be chosen earlier. */
5802 DBUG_ASSERT(in_subs->has_strategy());
5803 DBUG_ASSERT(in_to_exists_where || in_to_exists_having);
5804 DBUG_ASSERT(!in_to_exists_where || in_to_exists_where->fixed);
5805 DBUG_ASSERT(!in_to_exists_having || in_to_exists_having->fixed);
5806
5807 /* The original QEP of the subquery. */
5808 Join_plan_state save_qep(table_count);
5809
5810 /*
5811 Compute and compare the costs of materialization and in-exists if both
5812 strategies are possible and allowed by the user (checked during the prepare
5813 phase.
5814 */
5815 if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
5816 in_subs->test_strategy(SUBS_IN_TO_EXISTS))
5817 {
5818 JOIN *outer_join;
5819 JOIN *inner_join= this;
5820 /* Number of unique value combinations filtered by the IN predicate. */
5821 double outer_lookup_keys;
5822 /* Cost and row count of the unmodified subquery. */
5823 double inner_read_time_1, inner_record_count_1;
5824 /* Cost of the subquery with injected IN-EXISTS predicates. */
5825 double inner_read_time_2;
5826 /* The cost to compute IN via materialization. */
5827 double materialize_strategy_cost;
5828 /* The cost of the IN->EXISTS strategy. */
5829 double in_exists_strategy_cost;
5830 double dummy;
5831
5832 /*
5833 A. Estimate the number of rows of the outer table that will be filtered
5834 by the IN predicate.
5835 */
5836 outer_join= unit->outer_select() ? unit->outer_select()->join : NULL;
5837 /*
5838 Get the cost of the outer join if:
5839 (1) It has at least one table, and
5840 (2) It has been already optimized (if there is no join_tab, then the
5841 outer join has not been optimized yet).
5842 */
5843 if (outer_join && outer_join->table_count > 0 && // (1)
5844 outer_join->join_tab && // (2)
5845 !in_subs->const_item())
5846 {
5847 /*
5848 TODO:
5849 Currently outer_lookup_keys is computed as the number of rows in
5850 the partial join including the JOIN_TAB where the IN predicate is
5851 pushed to. In the general case this is a gross overestimate because
5852 due to caching we are interested only in the number of unique keys.
5853 The search key may be formed by columns from much fewer than all
5854 tables in the partial join. Example:
5855 select * from t1, t2 where t1.c1 = t2.key AND t2.c2 IN (select ...);
5856 If the join order: t1, t2, the number of unique lookup keys is ~ to
5857 the number of unique values t2.c2 in the partial join t1 join t2.
5858 */
5859 outer_join->get_partial_cost_and_fanout(in_subs->get_join_tab_idx(),
5860 table_map(-1),
5861 &dummy,
5862 &outer_lookup_keys);
5863 }
5864 else
5865 {
5866 /*
5867 TODO: outer_join can be NULL for DELETE statements.
5868 How to compute its cost?
5869 */
5870 outer_lookup_keys= 1;
5871 }
5872
5873 /*
5874 B. Estimate the cost and number of records of the subquery both
5875 unmodified, and with injected IN->EXISTS predicates.
5876 */
5877 inner_read_time_1= inner_join->best_read;
5878 inner_record_count_1= inner_join->join_record_count;
5879
5880 if (in_to_exists_where && const_tables != table_count)
5881 {
5882 /*
5883 Re-optimize and cost the subquery taking into account the IN-EXISTS
5884 conditions.
5885 */
5886 reopt_result= reoptimize(in_to_exists_where, join_tables, &save_qep);
5887 if (reopt_result == REOPT_ERROR)
5888 return TRUE;
5889
5890 /* Get the cost of the modified IN-EXISTS plan. */
5891 inner_read_time_2= inner_join->best_read;
5892
5893 }
5894 else
5895 {
5896 /* Reoptimization would not produce any better plan. */
5897 inner_read_time_2= inner_read_time_1;
5898 }
5899
5900 /*
5901 C. Compute execution costs.
5902 */
5903 /* C.1 Compute the cost of the materialization strategy. */
5904 //uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list);
5905 uint rowlen= get_tmp_table_rec_length(ref_ptrs,
5906 select_lex->item_list.elements);
5907 /* The cost of writing one row into the temporary table. */
5908 double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1,
5909 rowlen);
5910 /* The cost of a lookup into the unique index of the materialized table. */
5911 double lookup_cost= get_tmp_table_lookup_cost(thd, inner_record_count_1,
5912 rowlen);
5913 /*
5914 The cost of executing the subquery and storing its result in an indexed
5915 temporary table.
5916 */
5917 double materialization_cost= COST_ADD(inner_read_time_1,
5918 COST_MULT(write_cost,
5919 inner_record_count_1));
5920
5921 materialize_strategy_cost= COST_ADD(materialization_cost,
5922 COST_MULT(outer_lookup_keys,
5923 lookup_cost));
5924
5925 /* C.2 Compute the cost of the IN=>EXISTS strategy. */
5926 in_exists_strategy_cost= COST_MULT(outer_lookup_keys, inner_read_time_2);
5927
5928 /* C.3 Compare the costs and choose the cheaper strategy. */
5929 if (materialize_strategy_cost >= in_exists_strategy_cost)
5930 in_subs->set_strategy(SUBS_IN_TO_EXISTS);
5931 else
5932 in_subs->set_strategy(SUBS_MATERIALIZATION);
5933
5934 DBUG_PRINT("info",
5935 ("mat_strategy_cost: %.2f, mat_cost: %.2f, write_cost: %.2f, lookup_cost: %.2f",
5936 materialize_strategy_cost, materialization_cost, write_cost, lookup_cost));
5937 DBUG_PRINT("info",
5938 ("inx_strategy_cost: %.2f, inner_read_time_2: %.2f",
5939 in_exists_strategy_cost, inner_read_time_2));
5940 DBUG_PRINT("info",("outer_lookup_keys: %.2f", outer_lookup_keys));
5941 }
5942
5943 /*
5944 If (1) materialization is a possible strategy based on semantic analysis
5945 during the prepare phase, then if
5946 (2) it is more expensive than the IN->EXISTS transformation, and
5947 (3) it is not possible to create usable indexes for the materialization
5948 strategy,
5949 fall back to IN->EXISTS.
5950 otherwise
5951 use materialization.
5952 */
5953 if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
5954 in_subs->setup_mat_engine())
5955 {
5956 /*
5957 If materialization was the cheaper or the only user-selected strategy,
5958 but it is not possible to execute it due to limitations in the
5959 implementation, fall back to IN-TO-EXISTS.
5960 */
5961 in_subs->set_strategy(SUBS_IN_TO_EXISTS);
5962 }
5963
5964 if (in_subs->test_strategy(SUBS_MATERIALIZATION))
5965 {
5966 /* Restore the original query plan used for materialization. */
5967 if (reopt_result == REOPT_NEW_PLAN)
5968 restore_query_plan(&save_qep);
5969
5970 in_subs->unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
5971 select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
5972
5973 /*
5974 Reset the "LIMIT 1" set in Item_exists_subselect::fix_length_and_dec.
5975 TODO:
5976 Currently we set the subquery LIMIT to infinity, and this is correct
5977 because we forbid at parse time LIMIT inside IN subqueries (see
5978 Item_in_subselect::test_limit). However, once we allow this, here
5979 we should set the correct limit if given in the query.
5980 */
5981 in_subs->unit->global_parameters()->select_limit= NULL;
5982 in_subs->unit->set_limit(unit->global_parameters());
5983 /*
5984 Set the limit of this JOIN object as well, because normally its being
5985 set in the beginning of JOIN::optimize, which was already done.
5986 */
5987 select_limit= in_subs->unit->select_limit_cnt;
5988 }
5989 else if (in_subs->test_strategy(SUBS_IN_TO_EXISTS))
5990 {
5991 if (reopt_result == REOPT_NONE && in_to_exists_where &&
5992 const_tables != table_count)
5993 {
5994 /*
5995 The subquery was not reoptimized with the newly injected IN-EXISTS
5996 conditions either because the user allowed only the IN-EXISTS strategy,
5997 or because materialization was not possible based on semantic analysis.
5998 */
5999 reopt_result= reoptimize(in_to_exists_where, join_tables, NULL);
6000 if (reopt_result == REOPT_ERROR)
6001 return TRUE;
6002 }
6003
6004 if (in_subs->inject_in_to_exists_cond(this))
6005 return TRUE;
6006 /*
6007 If the injected predicate is correlated the IN->EXISTS transformation
6008 make the subquery dependent.
6009 */
6010 if ((in_to_exists_where &&
6011 in_to_exists_where->used_tables() & OUTER_REF_TABLE_BIT) ||
6012 (in_to_exists_having &&
6013 in_to_exists_having->used_tables() & OUTER_REF_TABLE_BIT))
6014 {
6015 in_subs->unit->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
6016 select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
6017 }
6018 select_limit= 1;
6019 }
6020 else
6021 DBUG_ASSERT(FALSE);
6022
6023 return FALSE;
6024 }
6025
6026
6027 /**
6028 Choose a query plan for a table-less subquery.
6029
6030 @notes
6031
6032 @retval FALSE success.
6033 @retval TRUE error occurred.
6034 */
6035
choose_tableless_subquery_plan()6036 bool JOIN::choose_tableless_subquery_plan()
6037 {
6038 DBUG_ASSERT(!tables_list || !table_count);
6039 if (unit->item)
6040 {
6041 DBUG_ASSERT(unit->item->type() == Item::SUBSELECT_ITEM);
6042 Item_subselect *subs_predicate= unit->item;
6043
6044 /*
6045 If the optimizer determined that his query has an empty result,
6046 in most cases the subquery predicate is a known constant value -
6047 either of TRUE, FALSE or NULL. The implementation of
6048 Item_subselect::no_rows_in_result() determines which one.
6049 */
6050 if (zero_result_cause)
6051 {
6052 if (!implicit_grouping)
6053 {
6054 /*
6055 Both group by queries and non-group by queries without aggregate
6056 functions produce empty subquery result. There is no need to further
6057 rewrite the subquery because it will not be executed at all.
6058 */
6059 exec_const_cond= 0;
6060 return FALSE;
6061 }
6062
6063 /* @todo
6064 A further optimization is possible when a non-group query with
6065 MIN/MAX/COUNT is optimized by opt_sum_query. Then, if there are
6066 only MIN/MAX functions over an empty result set, the subquery
6067 result is a NULL value/row, thus the value of subs_predicate is
6068 NULL.
6069 */
6070 }
6071
6072 /*
6073 For IN subqueries, use IN->EXISTS transfomation, unless the subquery
6074 has been converted to a JTBM semi-join. In that case, just leave
6075 everything as-is, setup_jtbm_semi_joins() has special handling for cases
6076 like this.
6077 */
6078 if (subs_predicate->is_in_predicate() &&
6079 !(subs_predicate->substype() == Item_subselect::IN_SUBS &&
6080 ((Item_in_subselect*)subs_predicate)->is_jtbm_merged))
6081 {
6082 Item_in_subselect *in_subs;
6083 in_subs= (Item_in_subselect*) subs_predicate;
6084 in_subs->set_strategy(SUBS_IN_TO_EXISTS);
6085 if (in_subs->create_in_to_exists_cond(this) ||
6086 in_subs->inject_in_to_exists_cond(this))
6087 return TRUE;
6088 tmp_having= having;
6089 }
6090 }
6091 exec_const_cond= zero_result_cause ? 0 : conds;
6092 return FALSE;
6093 }
6094