opt_subselect.cc 231 KB
Newer Older
1
/*
2
   Copyright (c) 2010, 2015, MariaDB
3 4 5 6 7 8 9 10 11 12 13 14

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
iangilfillan's avatar
iangilfillan committed
15
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 USA */
16

17 18 19 20
/**
  @file

  @brief
21
    Semi-join subquery optimizations code
22 23 24 25 26 27 28

*/

#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation				// gcc: Class implementation
#endif

29
#include "mariadb.h"
Sergei Golubchik's avatar
Sergei Golubchik committed
30
#include "sql_base.h"
31
#include "sql_select.h"
Sergei Golubchik's avatar
Sergei Golubchik committed
32
#include "filesort.h"
33
#include "opt_subselect.h"
34
#include "sql_test.h"
35
#include <my_bit.h>
Varun Gupta's avatar
Varun Gupta committed
36
#include "opt_trace.h"
37

38 39 40 41 42 43 44 45 46 47 48 49 50 51
/*
  This file contains optimizations for semi-join subqueries.
  
  Contents
  --------
  1. What is a semi-join subquery
  2. General idea about semi-join execution
  2.1 Correlated vs uncorrelated semi-joins
  2.2 Mergeable vs non-mergeable semi-joins
  3. Code-level view of semi-join processing
  3.1 Conversion
  3.1.1 Merged semi-join TABLE_LIST object
  3.1.2 Non-merged semi-join data structure
  3.2 Semi-joins and query optimization
psergey's avatar
psergey committed
52 53
  3.2.1 Non-merged semi-joins and join optimization
  3.2.2 Merged semi-joins and join optimization
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
  3.3 Semi-joins and query execution

  1. What is a semi-join subquery
  -------------------------------
  We use this definition of semi-join:

    outer_tbl SEMI JOIN inner_tbl ON cond = {set of outer_tbl.row such that
                                             exist inner_tbl.row, for which 
                                             cond(outer_tbl.row,inner_tbl.row)
                                             is satisfied}
  
  That is, semi-join operation is similar to inner join operation, with
  exception that we don't care how many matches a row from outer_tbl has in
  inner_tbl.

69 70
  In SQL terms: a semi-join subquery is an IN subquery that is an AND-part of
  the WHERE/ON clause.
71 72 73

  2. General idea about semi-join execution
  -----------------------------------------
74 75
  We can execute semi-join in a way similar to inner join, with exception that
  we need to somehow ensure that we do not generate record combinations that
76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
  differ only in rows of inner tables.
  There is a number of different ways to achieve this property, implemented by
  a number of semi-join execution strategies.
  Some strategies can handle any semi-joins, other can be applied only to
  semi-joins that have certain properties that are described below:

  2.1 Correlated vs uncorrelated semi-joins
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Uncorrelated semi-joins are special in the respect that they allow to
   - execute the subquery (possible as it's uncorrelated)
   - somehow make sure that generated set does not have duplicates
   - perform an inner join with outer tables.
  
  or, rephrasing in SQL form:

  SELECT ... FROM ot WHERE ot.col IN (SELECT it.col FROM it WHERE uncorr_cond)
    ->
  SELECT ... FROM ot JOIN (SELECT DISTINCT it.col FROM it WHERE uncorr_cond)

  2.2 Mergeable vs non-mergeable semi-joins
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Semi-join operation has some degree of commutability with inner join
  operation: we can join subquery's tables with ouside table(s) and eliminate
  duplicate record combination after that:

    ot1 JOIN ot2 SEMI_JOIN{it1,it2} (it1 JOIN it2) ON sjcond(ot2,it*) ->
              |
              +-------------------------------+
                                              v
    ot1 SEMI_JOIN{it1,it2} (it1 JOIN it2 JOIN ot2) ON sjcond(ot2,it*)
 
  In order for this to work, subquery's top-level operation must be join, and
  grouping or ordering with limit (grouping or ordering with limit are not
  commutative with duplicate removal). In other words, the conversion is
  possible when the subquery doesn't have GROUP BY clause, any aggregate
  functions*, or ORDER BY ... LIMIT clause.

  Definitions:
  - Subquery whose top-level operation is a join is called *mergeable semi-join*
  - All other kinds of semi-join subqueries are considered non-mergeable.

  *- this requirement is actually too strong, but its exceptions are too
  complicated to be considered here.

  3. Code-level view of semi-join processing
  ------------------------------------------
  
psergey's avatar
psergey committed
123 124
  3.1 Conversion and pre-optimization data structures
  ---------------------------------------------------
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
  * When doing JOIN::prepare for the subquery, we detect that it can be
    converted into a semi-join and register it in parent_join->sj_subselects

  * At the start of parent_join->optimize(), the predicate is converted into 
    a semi-join node. A semi-join node is a TABLE_LIST object that is linked
    somewhere in parent_join->join_list (either it is just present there, or
    it is a descendant of some of its members).
  
  There are two kinds of semi-joins:
  - Merged semi-joins
  - Non-merged semi-joins
   
  3.1.1 Merged semi-join TABLE_LIST object
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Merged semi-join object is a TABLE_LIST that contains a sub-join of 
  subquery tables and the semi-join ON expression (in this respect it is 
psergey's avatar
psergey committed
141
  very similar to nested outer join representation)
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158
  Merged semi-join represents this SQL:

    ... SEMI JOIN (inner_tbl1 JOIN ... JOIN inner_tbl_n) ON sj_on_expr
  
  Semi-join objects of this kind have TABLE_LIST::sj_subq_pred set.
 
  3.1.2 Non-merged semi-join data structure
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Non-merged semi-join object is a leaf TABLE_LIST object that has a subquery
  that produces rows. It is similar to a base table and represents this SQL:
    
    ... SEMI_JOIN (SELECT non_mergeable_select) ON sj_on_expr
  
  Subquery items that were converted into semi-joins are removed from the WHERE
  clause. (They do remain in PS-saved WHERE clause, and they replace themselves
  with Item_int(1) on subsequent re-executions).

psergey's avatar
psergey committed
159 160 161 162 163 164
  3.2 Semi-joins and join optimization
  ------------------------------------
  
  3.2.1 Non-merged semi-joins and join optimization
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  For join optimization purposes, non-merged semi-join nests are similar to
Sergey Petrunya's avatar
Sergey Petrunya committed
165 166
  base tables. Each such nest is represented by one one JOIN_TAB, which has 
  two possible access strategies:
psergey's avatar
psergey committed
167 168 169 170 171 172
   - full table scan (representing SJ-Materialization-Scan strategy)
   - eq_ref-like table lookup (representing SJ-Materialization-Lookup)

  Unlike regular base tables, non-merged semi-joins have:
   - non-zero JOIN_TAB::startup_cost, and
   - join_tab->table->is_filled_at_execution()==TRUE, which means one
Sergey Petrunya's avatar
Sergey Petrunya committed
173 174 175 176
     cannot do const table detection, range analysis or other dataset-dependent
     optimizations.
     Instead, get_delayed_table_estimates() will run optimization for the
     subquery and produce an E(materialized table size).
psergey's avatar
psergey committed
177 178 179 180 181 182 183 184
  
  3.2.2 Merged semi-joins and join optimization
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   - optimize_semijoin_nests() does pre-optimization 
   - during join optimization, the join has one JOIN_TAB (or is it POSITION?) 
     array, and suffix-based detection is used, see advance_sj_state()
   - after join optimization is done, get_best_combination() switches 
     the data-structure to prefix-based, multiple JOIN_TAB ranges format.
185 186 187 188

  3.3 Semi-joins and query execution
  ----------------------------------
  * Join executor has hooks for all semi-join strategies.
psergey's avatar
psergey committed
189 190
    TODO elaborate.

191 192
*/

193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437
/*
EqualityPropagationAndSjmNests
******************************

Equalities are used for:
P1. Equality propagation 
P2. Equality substitution [for a certain join order]

The equality propagation is not affected by SJM nests. In fact, it is done 
before we determine the execution plan, i.e. before we even know we will use
SJM-nests for execution.

The equality substitution is affected. 

Substitution without SJMs
=========================
When one doesn't have SJM nests, tables have a strict join order:

  ---------------------------------> 
    t1 -- t2 -- t3 -- t4 --- t5 


       ?  ^
           \
            --(part-of-WHERE)


parts WHERE/ON and ref. expressions are attached at some point along the axis.
Expression is allowed to refer to a table column if the table is to the left of
the attachment point. For any given expression, we have a goal: 

  "Move leftmost allowed attachment point as much as possible to the left"

Substitution with SJMs - task setting
=====================================

When SJM nests are present, there is no global strict table ordering anymore:

   
  ---------------------------------> 

    ot1 -- ot2 --- sjm -- ot4 --- ot5 
                   |
                   |                Main execution
   - - - - - - - - - - - - - - - - - - - - - - - -                 
                   |                 Materialization
      it1 -- it2 --/    


Besides that, we must take into account that
 - values for outer table columns, otN.col, are inaccessible at
   materialization step                                           (SJM-RULE)
 - values for inner table columns, itN.col, are inaccessible at Main execution
   step, except for SJ-Materialization-Scan and columns that are in the 
   subquery's select list.                                        (SJM-RULE)

Substitution with SJMs - solution
=================================

First, we introduce global strict table ordering like this:

  ot1 - ot2 --\                    /--- ot3 -- ot5 
               \--- it1 --- it2 --/

Now, let's see how to meet (SJM-RULE).

SJ-Materialization is only applicable for uncorrelated subqueries. From this, it
follows that any multiple equality will either
1. include only columns of outer tables, or
2. include only columns of inner tables, or
3. include columns of inner and outer tables, joined together through one 
   of IN-equalities.

Cases #1 and #2 can be handled in the same way as with regular inner joins.

Case #3 requires special handling, so that we don't construct violations of
(SJM-RULE). Let's consider possible ways to build violations.

Equality propagation starts with the clause in this form

   top_query_where AND subquery_where AND in_equalities

First, it builds multi-equalities. It can also build a mixed multi-equality

  multiple-equal(ot1.col, ot2.col, ... it1.col, itN.col) 

Multi-equalities are pushed down the OR-clauses in top_query_where and in
subquery_where, so it's possible that clauses like this one are built:

   subquery_cond OR (multiple-equal(it1.col, ot1.col,...) AND ...)
   ^^^^^^^^^^^^^                                 \
         |                                        this must be evaluated
         \- can only be evaluated                 at the main phase.
            at the materialization phase

Finally, equality substitution is started. It does two operations:


1. Field reference substitution 
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(In the code, this is Item_field::replace_equal_field)

This is a process of replacing each reference to "tblX.col" 
with the first element of the multi-equality.          (REF-SUBST-ORIG)

This behaviour can cause problems with Semi-join nests. Suppose, we have a
condition: 

  func(it1.col, it2.col)

and a multi-equality(ot1.col, it1.col). Then, reference to "it1.col" will be 
replaced with "ot1.col", constructing a condition
   
   func(ot1.col, it2.col)

which will be a violation of (SJM-RULE).

In order to avoid this, (REF-SUBST-ORIG) is amended as follows: 

- references to tables "itX.col" that are inner wrt some SJM nest, are
  replaced with references to the first inner table from the same SJM nest.

- references to top-level tables "otX.col" are replaced with references to
  the first element of the multi-equality, no matter if that first element is
  a column of a top-level table or of table from some SJM nest.
                                                              (REF-SUBST-SJM)

  The case where the first element is a table from an SJM nest $SJM is ok, 
  because it can be proven that $SJM uses SJ-Materialization-Scan, and 
  "unpacks" correct column values to the first element during the main
  execution phase.

2. Item_equal elimination
~~~~~~~~~~~~~~~~~~~~~~~~~
(In the code: eliminate_item_equal) This is a process of taking 

  multiple-equal(a,b,c,d,e)

and replacing it with an equivalent expression which is an AND of pair-wise 
equalities:

  a=b AND a=c AND ...

The equalities are picked such that for any given join prefix (t1,t2...) the
subset of equalities that can be evaluated gives the most restrictive
filtering. 

Without SJM nests, it is sufficient to compare every multi-equality member
with the first one:

  elem1=elem2 AND elem1=elem3 AND elem1=elem4 ... 

When SJM nests are present, we should take care not to construct equalities
that violate the (SJM-RULE). This is achieved by generating separate sets of
equalites for top-level tables and for inner tables. That is, for the join
order 

  ot1 - ot2 --\                    /--- ot3 -- ot5 
               \--- it1 --- it2 --/

we will generate
   ot1.col=ot2.col
   ot1.col=ot3.col
   ot1.col=ot5.col
   it2.col=it1.col


2.1 The problem with Item_equals and ORs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
As has been mentioned above, multiple equalities are pushed down into OR
clauses, possibly building clauses like this:

   func(it.col2) OR multiple-equal(it1.col1, it1.col2, ot1.col)      (1)

where the first part of the clause has references to inner tables, while the
second has references to the top-level tables, which is a violation of
(SJM-RULE).

AND-clauses of this kind do not create problems, because make_cond_for_table()
will take them apart. OR-clauses will not be split. It is possible to
split-out the part that's dependent on the inner table:

   func(it.col2) OR it1.col1=it1.col2

but this is a less-restrictive condition than condition (1). Current execution
scheme will still try to generate the "remainder" condition:

   func(it.col2) OR it1.col1=ot1.col

which is a violation of (SJM-RULE).

QQ: "ot1.col=it1.col" is checked at the upper level. Why was it not removed
here?
AA: because has a proper subset of conditions that are found on this level.
    consider a join order of  ot, sjm(it)
    and a condition
      ot.col=it.col AND ( ot.col=it.col='foo' OR it.col2='bar')

    we will produce: 
       table ot:  nothing
       table it:  ot.col=it.col AND (ot.col='foo' OR it.col2='bar')
                                     ^^^^        ^^^^^^^^^^^^^^^^       
                                      |          \ the problem is that 
                                      |            this part condition didnt
                                      |            receive a substitution
                                      |
                                      +--- it was correct to subst, 'ot' is 
                                           the left-most.


Does it make sense to push "inner=outer" down into ORs?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Yes. Consider the query:

  select * from ot 
  where ot.col in (select it.col from it where (it.col='foo' OR it.col='bar'))

here, it may be useful to infer that 

   (ot.col='foo' OR ot.col='bar')       (CASE-FOR-SUBST)

and attach that condition to the table 'ot'.

Possible solutions for Item_equals and ORs
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Solution #1
~~~~~~~~~~~
Let make_cond_for_table() chop analyze the OR clauses it has produced and
discard them if they violate (SJM-RULE). This solution would allow to handle
cases like (CASE-FOR-SUBST) at the expense of making semantics of
make_cond_for_table() complicated.

Solution #2
~~~~~~~~~~~
Before the equality propagation phase, none of the OR clauses violate the
(SJM-RULE). This way, if we remember which tables the original equality
referred to, we can only generate equalities that refer to the outer (or inner)
tables. Note that this will disallow handling of cases like (CASE-FOR-SUBST).

Currently, solution #2 is implemented.
*/

438
LEX_CSTRING weedout_key= {STRING_WITH_LEN("weedout_key")};
439

440
static
Varun Gupta's avatar
Varun Gupta committed
441
bool subquery_types_allow_materialization(THD *thd, Item_in_subselect *in_subs);
442
static bool replace_where_subcondition(JOIN *, Item **, Item *, Item *, bool);
Igor Babaev's avatar
Igor Babaev committed
443 444
static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
                                 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 448
static bool convert_subq_to_jtbm(JOIN *parent_join, 
                                 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 452 453 454 455 456 457 458 459 460 461
bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables);
static SJ_MATERIALIZATION_INFO *
at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
             uint idx, bool *loose_scan);
void best_access_path(JOIN *join, JOIN_TAB *s, 
                             table_map remaining_tables, uint idx, 
                             bool disable_jbuf, double record_count,
                             POSITION *pos, POSITION *loose_scan_pos);

static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm, 
                                Item_in_subselect *subq_pred);
462
static bool remove_sj_conds(THD *thd, Item **tree);
463 464 465 466 467
static bool is_cond_sj_in_equality(Item *item);
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab);
static Item *remove_additional_cond(Item* conds);
static void remove_subq_pushed_predicates(JOIN *join, Item **where);

468 469 470
enum_nested_loop_state 
end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);

471

472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512
/*
  Check if Materialization strategy is allowed for given subquery predicate.

  @param thd           Thread handle
  @param in_subs       The subquery predicate
  @param child_select  The select inside predicate (the function will
                       check it is the only one)

  @return TRUE  - Materialization is applicable 
          FALSE - Otherwise
*/

bool is_materialization_applicable(THD *thd, Item_in_subselect *in_subs,
                                   st_select_lex *child_select)
{
  st_select_lex_unit* parent_unit= child_select->master_unit();
  /*
    Check if the subquery predicate can be executed via materialization.
    The required conditions are:
    0. The materialization optimizer switch was set.
    1. Subquery is a single SELECT (not a UNION).
       TODO: this is a limitation that can be fixed
    2. Subquery is not a table-less query. In this case there is no
       point in materializing.
    2A The upper query is not a table-less SELECT ... FROM DUAL. We
       can't do materialization for SELECT .. FROM DUAL because it
       does not call setup_subquery_materialization(). We could make 
       SELECT ... FROM DUAL call that function but that doesn't seem
       to be the case that is worth handling.
    3. Either the subquery predicate is a top-level predicate, or at
       least one partial match strategy is enabled. If no partial match
       strategy is enabled, then materialization cannot be used for
       non-top-level queries because it cannot handle NULLs correctly.
    4. Subquery is non-correlated
       TODO:
       This condition is too restrictive (limitation). It can be extended to:
       (Subquery is non-correlated ||
        Subquery is correlated to any query outer to IN predicate ||
        (Subquery is correlated to the immediate outer query &&
         Subquery !contains {GROUP BY, ORDER BY [LIMIT],
         aggregate functions}) && subquery predicate is not under "NOT IN"))
513
    5. Subquery does not contain recursive references
514 515 516 517 518 519 520 521 522

  A note about prepared statements: we want the if-branch to be taken on
  PREPARE and each EXECUTE. The rewrites are only done once, but we need 
  select_lex->sj_subselects list to be populated for every EXECUTE. 

  */
  if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION) &&      // 0
        !child_select->is_part_of_union() &&                          // 1
        parent_unit->first_select()->leaf_tables.elements &&          // 2
523
        child_select->outer_select() &&
524
        child_select->outer_select()->leaf_tables.elements &&         // 2A
Varun Gupta's avatar
Varun Gupta committed
525
        subquery_types_allow_materialization(thd, in_subs) &&
526 527 528 529 530
        (in_subs->is_top_level_item() ||                               //3
         optimizer_flag(thd,
                        OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) || //3
         optimizer_flag(thd,
                        OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)) && //3
531 532
        !in_subs->is_correlated &&                                     //4
        !in_subs->with_recursive_reference)                            //5
533 534 535 536 537 538 539
   {
     return TRUE;
   }
  return FALSE;
}


540 541 542
/*
  Check if we need JOIN::prepare()-phase subquery rewrites and if yes, do them

Sergey Petrunya's avatar
Sergey Petrunya committed
543 544 545 546
  SYNOPSIS
     check_and_do_in_subquery_rewrites()
       join  Subquery's join

547 548
  DESCRIPTION
    Check if we need to do
Sergey Petrunya's avatar
Sergey Petrunya committed
549
     - subquery -> mergeable semi-join rewrite
550 551
     - if the subquery can be handled with materialization
     - 'substitution' rewrite for table-less subqueries like "(select 1)"
Sergey Petrunya's avatar
Sergey Petrunya committed
552 553 554
     - IN->EXISTS rewrite
    and, depending on the rewrite, either do it, or record it to be done at a
    later phase.
555 556

  RETURN
Sergey Petrunya's avatar
Sergey Petrunya committed
557 558
    0      - OK
    Other  - Some sort of query error
559 560 561 562 563 564
*/

int check_and_do_in_subquery_rewrites(JOIN *join)
{
  THD *thd=join->thd;
  st_select_lex *select_lex= join->select_lex;
565
  st_select_lex_unit* parent_unit= select_lex->master_unit();
566
  DBUG_ENTER("check_and_do_in_subquery_rewrites");
567 568 569 570 571 572 573 574

  /*
    IN/ALL/ANY rewrites are not applicable for so called fake select
    (this select exists only to filter results of union if it is needed).
  */
  if (select_lex == select_lex->master_unit()->fake_select_lex)
    DBUG_RETURN(0);

575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590
  /*
    If 
      1) this join is inside a subquery (of any type except FROM-clause 
         subquery) and
      2) we aren't just normalizing a VIEW

    Then perform early unconditional subquery transformations:
     - Convert subquery predicate into semi-join, or
     - Mark the subquery for execution using materialization, or
     - Perform IN->EXISTS transformation, or
     - Perform more/less ALL/ANY -> MIN/MAX rewrite
     - Substitute trivial scalar-context subquery with its value

    TODO: for PS, make the whole block execute only on the first execution
  */
  Item_subselect *subselect;
591 592
  if (!thd->lex->is_view_context_analysis() &&          // (1)
      (subselect= parent_unit->item))                   // (2)
593 594
  {
    Item_in_subselect *in_subs= NULL;
595 596 597 598 599 600 601 602 603 604 605 606 607
    Item_allany_subselect *allany_subs= NULL;
    switch (subselect->substype()) {
    case Item_subselect::IN_SUBS:
      in_subs= (Item_in_subselect *)subselect;
      break;
    case Item_subselect::ALL_SUBS:
    case Item_subselect::ANY_SUBS:
      allany_subs= (Item_allany_subselect *)subselect;
      break;
    default:
      break;
    }

608 609 610 611 612 613 614 615 616 617 618 619 620

    /* Resolve expressions and perform semantic analysis for IN query */
    if (in_subs != NULL)
      /*
        TODO: Add the condition below to this if statement when we have proper
        support for is_correlated handling for materialized semijoins.
        If we were to add this condition now, the fix_fields() call in
        convert_subq_to_sj() would force the flag is_correlated to be set
        erroneously for prepared queries.

        thd->stmt_arena->state != Query_arena::PREPARED)
      */
    {
621 622 623 624 625
      SELECT_LEX *current= thd->lex->current_select;
      thd->lex->current_select= current->return_after_parsing();
      char const *save_where= thd->where;
      thd->where= "IN/ALL/ANY subquery";

626 627
      bool failure= in_subs->left_expr->fix_fields_if_needed(thd,
                                                          &in_subs->left_expr);
628 629 630 631 632
      thd->lex->current_select= current;
      thd->where= save_where;
      if (failure)
        DBUG_RETURN(-1); /* purecov: deadcode */

633 634 635 636 637 638 639 640 641 642 643 644 645 646
      /*
        Check if the left and right expressions have the same # of
        columns, i.e. we don't have a case like 
          (oe1, oe2) IN (SELECT ie1, ie2, ie3 ...)

        TODO why do we have this duplicated in IN->EXISTS transformers?
        psergey-todo: fix these: grep for duplicated_subselect_card_check
      */
      if (select_lex->item_list.elements != in_subs->left_expr->cols())
      {
        my_error(ER_OPERAND_COLUMNS, MYF(0), in_subs->left_expr->cols());
        DBUG_RETURN(-1);
      }
    }
647

648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664
    DBUG_PRINT("info", ("Checking if subq can be converted to semi-join"));
    /*
      Check if we're in subquery that is a candidate for flattening into a
      semi-join (which is done in flatten_subqueries()). The
      requirements are:
        1. Subquery predicate is an IN/=ANY subq predicate
        2. Subquery is a single SELECT (not a UNION)
        3. Subquery does not have GROUP BY or ORDER BY
        4. Subquery does not use aggregate functions or HAVING
        5. Subquery predicate is at the AND-top-level of ON/WHERE clause
        6. We are not in a subquery of a single table UPDATE/DELETE that 
             doesn't have a JOIN (TODO: We should handle this at some
             point by switching to multi-table UPDATE/DELETE)
        7. We're not in a table-less subquery like "SELECT 1"
        8. No execution method was already chosen (by a prepared statement)
        9. Parent select is not a table-less select
        10. Neither parent nor child select have STRAIGHT_JOIN option.
unknown's avatar
unknown committed
665 666 667
        11. It is first optimisation (the subquery could be moved from ON
        clause during first optimisation and then be considered for SJ
        on the second when it is too late)
668 669 670 671 672 673
    */
    if (optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
        in_subs &&                                                    // 1
        !select_lex->is_part_of_union() &&                            // 2
        !select_lex->group_list.elements && !join->order &&           // 3
        !join->having && !select_lex->with_sum_func &&                // 4
674
        in_subs->emb_on_expr_nest &&                                  // 5
675
        select_lex->outer_select()->join &&                           // 6
676
        parent_unit->first_select()->leaf_tables.elements &&          // 7
unknown's avatar
unknown committed
677
        !in_subs->has_strategy() &&                                   // 8
678
        select_lex->outer_select()->leaf_tables.elements &&           // 9
679 680
        !((join->select_options |                                     // 10
           select_lex->outer_select()->join->select_options)          // 10
unknown's avatar
unknown committed
681 682
          & SELECT_STRAIGHT_JOIN) &&                                  // 10
        select_lex->first_cond_optimization)                          // 11
683 684 685
    {
      DBUG_PRINT("info", ("Subquery is semi-join conversion candidate"));

Varun Gupta's avatar
Varun Gupta committed
686
      (void)subquery_types_allow_materialization(thd, in_subs);
687

688
      in_subs->is_flattenable_semijoin= TRUE;
689 690

      /* Register the subquery for further processing in flatten_subqueries() */
Igor Babaev's avatar
Igor Babaev committed
691 692 693 694
      if (!in_subs->is_registered_semijoin)
      {
        Query_arena *arena, backup;
        arena= thd->activate_stmt_arena_if_needed(&backup);
695 696
        select_lex->outer_select()->sj_subselects.push_back(in_subs,
                                                            thd->mem_root);
Igor Babaev's avatar
Igor Babaev committed
697 698 699
        if (arena)
          thd->restore_active_arena(arena, &backup);
        in_subs->is_registered_semijoin= TRUE;
Varun Gupta's avatar
Varun Gupta committed
700 701 702
        OPT_TRACE_TRANSFORM(thd, oto0, oto1, select_lex->select_number,
                            "IN (SELECT)", "semijoin");
        oto1.add("chosen", true);
Igor Babaev's avatar
Igor Babaev committed
703
      }
704 705 706
    }
    else
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
707
      DBUG_PRINT("info", ("Subquery can't be converted to merged semi-join"));
708
      /* Test if the user has set a legal combination of optimizer switches. */
709 710 711
      if (!optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS) &&
          !optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION))
        my_error(ER_ILLEGAL_SUBQUERY_OPTIMIZER_SWITCHES, MYF(0));
712 713 714 715 716 717
      /*
        Transform each subquery predicate according to its overloaded
        transformer.
      */
      if (subselect->select_transformer(join))
        DBUG_RETURN(-1);
718

719
      /*
720 721 722 723
        If the subquery predicate is IN/=ANY, analyse and set all possible
        subquery execution strategies based on optimizer switches and syntactic
        properties.
      */
724
      if (in_subs && !in_subs->has_strategy())
725
      {
726 727
        if (is_materialization_applicable(thd, in_subs, select_lex))
        {
unknown's avatar
unknown committed
728
          in_subs->add_strategy(SUBS_MATERIALIZATION);
Sergey Petrunya's avatar
Sergey Petrunya committed
729 730 731 732 733

          /*
            If the subquery is an AND-part of WHERE register for being processed
            with jtbm strategy
          */
734
          if (in_subs->emb_on_expr_nest == NO_JOIN_NEST &&
Sergey Petrunya's avatar
Sergey Petrunya committed
735 736 737
              optimizer_flag(thd, OPTIMIZER_SWITCH_SEMIJOIN))
          {
            in_subs->is_flattenable_semijoin= FALSE;
Igor Babaev's avatar
Igor Babaev committed
738 739 740 741
            if (!in_subs->is_registered_semijoin)
	    {
              Query_arena *arena, backup;
              arena= thd->activate_stmt_arena_if_needed(&backup);
742 743
              select_lex->outer_select()->sj_subselects.push_back(in_subs,
                                                                  thd->mem_root);
Igor Babaev's avatar
Igor Babaev committed
744 745 746 747
              if (arena)
                thd->restore_active_arena(arena, &backup);
              in_subs->is_registered_semijoin= TRUE;
            }
Sergey Petrunya's avatar
Sergey Petrunya committed
748
          }
749
        }
750

751 752 753 754 755 756
        /*
          IN-TO-EXISTS is the only universal strategy. Choose it if the user
          allowed it via an optimizer switch, or if materialization is not
          possible.
        */
        if (optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS) ||
unknown's avatar
unknown committed
757 758
            !in_subs->has_strategy())
          in_subs->add_strategy(SUBS_IN_TO_EXISTS);
759 760
      }

761
      /* Check if max/min optimization applicable */
unknown's avatar
unknown committed
762 763 764 765 766 767 768
      if (allany_subs && !allany_subs->is_set_strategy())
      {
        uchar strategy= (allany_subs->is_maxmin_applicable(join) ?
                         (SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE) :
                         SUBS_IN_TO_EXISTS);
        allany_subs->add_strategy(strategy);
      }
769

770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823
    }
  }
  DBUG_RETURN(0);
}


/**
  @brief Check if subquery's compared types allow materialization.

  @param in_subs Subquery predicate, updated as follows:
    types_allow_materialization TRUE if subquery materialization is allowed.
    sjm_scan_allowed            If types_allow_materialization is TRUE,
                                indicates whether it is possible to use subquery
                                materialization and scan the materialized table.

  @retval TRUE   If subquery types allow materialization.
  @retval FALSE  Otherwise.

  @details
    This is a temporary fix for BUG#36752.
    
    There are two subquery materialization strategies:

    1. Materialize and do index lookups in the materialized table. See 
       BUG#36752 for description of restrictions we need to put on the
       compared expressions.

    2. Materialize and then do a full scan of the materialized table. At the
       moment, this strategy's applicability criteria are even stricter than
       in #1.

       This is so because of the following: consider an uncorrelated subquery
       
       ...WHERE (ot1.col1, ot2.col2 ...) IN (SELECT ie1,ie2,... FROM it1 ...)

       and a join order that could be used to do sjm-materialization: 
          
          SJM-Scan(it1, it1), ot1, ot2
       
       IN-equalities will be parts of conditions attached to the outer tables:

         ot1:  ot1.col1 = ie1 AND ... (C1)
         ot2:  ot1.col2 = ie2 AND ... (C2)
       
       besides those there may be additional references to ie1 and ie2
       generated by equality propagation. The problem with evaluating C1 and
       C2 is that ie{1,2} refer to subquery tables' columns, while we only have 
       current value of materialization temptable. Our solution is to 
        * require that all ie{N} are table column references. This allows 
          to copy the values of materialization temptable columns to the
          original table's columns (see setup_sj_materialization for more
          details)
        * require that compared columns have exactly the same type. This is
          a temporary measure to avoid BUG#36752-type problems.
824 825 826

    JOIN_TAB::keyuse_is_valid_for_access_in_chosen_plan expects that for Semi Join Materialization
    Scan all the items in the select list of the IN Subquery are of the type Item::FIELD_ITEM.
827 828 829
*/

static 
Varun Gupta's avatar
Varun Gupta committed
830
bool subquery_types_allow_materialization(THD* thd, Item_in_subselect *in_subs)
831 832 833
{
  DBUG_ENTER("subquery_types_allow_materialization");

834
  DBUG_ASSERT(in_subs->left_expr->is_fixed());
835 836 837

  List_iterator<Item> it(in_subs->unit->first_select()->item_list);
  uint elements= in_subs->unit->first_select()->item_list.elements;
Varun Gupta's avatar
Varun Gupta committed
838
  const char* cause= NULL;
839 840 841

  in_subs->types_allow_materialization= FALSE;  // Assign default values
  in_subs->sjm_scan_allowed= FALSE;
Varun Gupta's avatar
Varun Gupta committed
842 843 844 845

  OPT_TRACE_TRANSFORM(thd, oto0, oto1,
                     in_subs->get_select_lex()->select_number,
                      "IN (SELECT)", "materialization");
846 847
  
  bool all_are_fields= TRUE;
848
  uint32 total_key_length = 0;
849 850 851 852 853 854
  for (uint i= 0; i < elements; i++)
  {
    Item *outer= in_subs->left_expr->element_index(i);
    Item *inner= it++;
    all_are_fields &= (outer->real_item()->type() == Item::FIELD_ITEM && 
                       inner->real_item()->type() == Item::FIELD_ITEM);
855
    total_key_length += inner->max_length;
856 857
    if (!inner->type_handler()->subquery_type_allows_materialization(inner,
                                                                     outer))
Varun Gupta's avatar
Varun Gupta committed
858 859 860
    {
      oto1.add("possible", false);
      oto1.add("cause", "types mismatch");
861
      DBUG_RETURN(FALSE);
Varun Gupta's avatar
Varun Gupta committed
862
    }
863
  }
864

865 866 867 868
  /*
     Make sure that create_tmp_table will not fail due to too long keys.
     See MDEV-7122. This check is performed inside create_tmp_table also and
     we must do it so that we know the table has keys created.
869 870
     Make sure that the length of the key for the temp_table is atleast
     greater than 0.
871
  */
Varun Gupta's avatar
Varun Gupta committed
872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888
  if (!total_key_length)
    cause= "zero length key for materialized table";
  else if (total_key_length > tmp_table_max_key_length())
    cause= "length of key greater than allowed key length for materialized tables";
  else if (elements > tmp_table_max_key_parts())
    cause= "#keyparts greater than allowed key parts for materialized tables";
  else
  {
    in_subs->types_allow_materialization= TRUE;
    in_subs->sjm_scan_allowed= all_are_fields;
    oto1.add("sjm_scan_allowed", all_are_fields)
        .add("possible", true);
    DBUG_PRINT("info",("subquery_types_allow_materialization: ok, allowed"));
    DBUG_RETURN(TRUE);
  }
  oto1.add("possible", false).add("cause", cause);
  DBUG_RETURN(FALSE);
889 890 891
}


892 893 894 895
/**
  Apply max min optimization of all/any subselect
*/

896
bool JOIN::transform_max_min_subquery()
897
{
898 899
  DBUG_ENTER("JOIN::transform_max_min_subquery");
  Item_subselect *subselect= unit->item;
900 901 902
  if (!subselect || (subselect->substype() != Item_subselect::ALL_SUBS &&
                     subselect->substype() != Item_subselect::ANY_SUBS))
    DBUG_RETURN(0);
903 904
  DBUG_RETURN(((Item_allany_subselect *) subselect)->
              transform_into_max_min(this));
905 906 907
}


908 909 910 911 912 913 914 915 916 917 918 919
/*
  Finalize IN->EXISTS conversion in case we couldn't use materialization.

  DESCRIPTION  Invoke the IN->EXISTS converter
    Replace the Item_in_subselect with its wrapper Item_in_optimizer in WHERE.

  RETURN 
    FALSE - Ok
    TRUE  - Fatal error
*/

bool make_in_exists_conversion(THD *thd, JOIN *join, Item_in_subselect *item)
920 921 922
{
  DBUG_ENTER("make_in_exists_conversion");
  JOIN *child_join= item->unit->first_select()->join;
Sergey Petrunya's avatar
Sergey Petrunya committed
923
  bool res;
924 925 926 927

  /* 
    We're going to finalize IN->EXISTS conversion. 
    Normally, IN->EXISTS conversion takes place inside the 
928
    Item_subselect::fix_fields() call, where item_subselect->is_fixed()==FALSE (as
929 930 931 932 933 934 935 936 937
    fix_fields() haven't finished yet) and item_subselect->changed==FALSE (as 
    the conversion haven't been finalized)

    At the end of Item_subselect::fix_fields() we had to set fixed=TRUE,
    changed=TRUE (the only other option would have been to return error).

    So, now we have to set these back for the duration of select_transformer()
    call.
  */
938 939 940 941 942 943 944 945 946 947
  item->changed= 0;
  item->fixed= 0;

  SELECT_LEX *save_select_lex= thd->lex->current_select;
  thd->lex->current_select= item->unit->first_select();

  res= item->select_transformer(child_join);

  thd->lex->current_select= save_select_lex;

Sergey Petrunya's avatar
Sergey Petrunya committed
948
  if (res)
949 950 951 952 953 954
    DBUG_RETURN(TRUE);

  item->changed= 1;
  item->fixed= 1;

  Item *substitute= item->substitution;
955
  bool do_fix_fields= !item->substitution->is_fixed();
956
  /*
957 958
    The Item_subselect has already been wrapped with Item_in_optimizer, so we
    should search for item->optimizer, not 'item'.
959
  */
960 961
  Item *replace_me= item->optimizer;
  DBUG_ASSERT(replace_me==substitute);
962

963
  Item **tree= (item->emb_on_expr_nest == NO_JOIN_NEST)?
964
                 &join->conds : &(item->emb_on_expr_nest->on_expr);
965 966 967 968 969
  if (replace_where_subcondition(join, tree, replace_me, substitute, 
                                 do_fix_fields))
    DBUG_RETURN(TRUE);
  item->substitution= NULL;
   
970 971 972 973
    /*
      If this is a prepared statement, repeat the above operation for
      prep_where (or prep_on_expr). 
    */
974 975
  if (!thd->stmt_arena->is_conventional())
  {
976
    tree= (item->emb_on_expr_nest == (TABLE_LIST*)NO_JOIN_NEST)?
977 978 979 980 981 982 983 984 985
           &join->select_lex->prep_where : 
           &(item->emb_on_expr_nest->prep_on_expr);

    if (replace_where_subcondition(join, tree, replace_me, substitute, 
                                   FALSE))
      DBUG_RETURN(TRUE);
  }
  DBUG_RETURN(FALSE);
}
986 987


988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007
bool check_for_outer_joins(List<TABLE_LIST> *join_list)
{
  TABLE_LIST *table;
  NESTED_JOIN *nested_join;
  List_iterator<TABLE_LIST> li(*join_list);
  while ((table= li++))
  {
    if ((nested_join= table->nested_join))
    {
      if (check_for_outer_joins(&nested_join->join_list))
        return TRUE;
    }
    
    if (table->outer_join)
      return TRUE;
  }
  return FALSE;
}


1008 1009 1010
void find_and_block_conversion_to_sj(Item *to_find,
				     List_iterator_fast<Item_in_subselect> &li)
{
1011 1012 1013 1014
  if (to_find->type() == Item::FUNC_ITEM &&
     ((Item_func*)to_find)->functype() == Item_func::IN_OPTIMIZER_FUNC)
    to_find= ((Item_in_optimizer*)to_find)->get_wrapped_in_subselect_item();

1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030
  if (to_find->type() != Item::SUBSELECT_ITEM ||
      ((Item_subselect *) to_find)->substype() != Item_subselect::IN_SUBS)
    return;
  Item_in_subselect *in_subq;
  li.rewind();
  while ((in_subq= li++))
  {
    if (in_subq == to_find)
    {
      in_subq->block_conversion_to_sj();
      return;
    }
  }
}


1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080
/*
  Convert semi-join subquery predicates into semi-join join nests

  SYNOPSIS
    convert_join_subqueries_to_semijoins()
 
  DESCRIPTION

    Convert candidate subquery predicates into semi-join join nests. This 
    transformation is performed once in query lifetime and is irreversible.
    
    Conversion of one subquery predicate
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    We start with a join that has a semi-join subquery:

      SELECT ...
      FROM ot, ...
      WHERE oe IN (SELECT ie FROM it1 ... itN WHERE subq_where) AND outer_where

    and convert it into a semi-join nest:

      SELECT ...
      FROM ot SEMI JOIN (it1 ... itN), ...
      WHERE outer_where AND subq_where AND oe=ie

    that is, in order to do the conversion, we need to 

     * Create the "SEMI JOIN (it1 .. itN)" part and add it into the parent
       query's FROM structure.
     * Add "AND subq_where AND oe=ie" into parent query's WHERE (or ON if
       the subquery predicate was in an ON expression)
     * Remove the subquery predicate from the parent query's WHERE

    Considerations when converting many predicates
    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    A join may have at most MAX_TABLES tables. This may prevent us from
    flattening all subqueries when the total number of tables in parent and
    child selects exceeds MAX_TABLES.
    We deal with this problem by flattening children's subqueries first and
    then using a heuristic rule to determine each subquery predicate's
    "priority".

  RETURN 
    FALSE  OK
    TRUE   Error
*/

bool convert_join_subqueries_to_semijoins(JOIN *join)
{
  Query_arena *arena, backup;
Igor Babaev's avatar
Igor Babaev committed
1081
  Item_in_subselect *in_subq;
1082 1083 1084
  THD *thd= join->thd;
  DBUG_ENTER("convert_join_subqueries_to_semijoins");

Igor Babaev's avatar
Igor Babaev committed
1085
  if (join->select_lex->sj_subselects.is_empty())
1086 1087
    DBUG_RETURN(FALSE);

Igor Babaev's avatar
Igor Babaev committed
1088 1089 1090
  List_iterator_fast<Item_in_subselect> li(join->select_lex->sj_subselects);

  while ((in_subq= li++))
1091
  {
Igor Babaev's avatar
Igor Babaev committed
1092
    SELECT_LEX *subq_sel= in_subq->get_select_lex();
1093 1094
    if (subq_sel->handle_derived(thd->lex, DT_MERGE))
      DBUG_RETURN(TRUE);
1095
    if (subq_sel->join->transform_in_predicates_into_in_subq(thd))
1096
      DBUG_RETURN(TRUE);
1097 1098 1099
    subq_sel->update_used_tables();
  }

1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113
  /* 
    Check all candidates to semi-join conversion that occur
    in ON expressions of outer join. Set the flag blocking
    this conversion for them.
  */
  TABLE_LIST *tbl;
  List_iterator<TABLE_LIST> ti(join->select_lex->leaf_tables);
  while ((tbl= ti++))
  {
    TABLE_LIST *embedded;
    TABLE_LIST *embedding= tbl;
    do
    {
      embedded= embedding;
1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
      bool block_conversion_to_sj= false;
      if (embedded->on_expr)
      {
        /*
          Conversion of an IN subquery predicate into semi-join
          is blocked now if the predicate occurs:
          - in the ON expression of an outer join
          - in the ON expression of an inner join embedded directly
            or indirectly in the inner nest of an outer join
	*/
        for (TABLE_LIST *tl= embedded; tl; tl= tl->embedding)
	{
          if (tl->outer_join)
	  {
            block_conversion_to_sj= true;
            break;
          }
        }
      }
      if (block_conversion_to_sj)
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171
      {
	Item *cond= embedded->on_expr;
        if (!cond)
          ;
        else if (cond->type() != Item::COND_ITEM)
          find_and_block_conversion_to_sj(cond, li);
        else if (((Item_cond*) cond)->functype() ==
	         Item_func::COND_AND_FUNC)
	{
          Item *item;
          List_iterator<Item> it(*(((Item_cond*) cond)->argument_list()));
          while ((item= it++))
	  {
	    find_and_block_conversion_to_sj(item, li);
          }
	}
      }
      embedding= embedded->embedding;
    }
    while (embedding &&
           embedding->nested_join->join_list.head() == embedded);
  }

  /* 
    Block conversion to semi-joins for those candidates that
    are encountered in the WHERE condition of the multi-table view
    with CHECK OPTION if this view is used in UPDATE/DELETE.
    (This limitation can be, probably, easily lifted.) 
  */  
  li.rewind();
  while ((in_subq= li++))
  {
    if (in_subq->emb_on_expr_nest != NO_JOIN_NEST &&
        in_subq->emb_on_expr_nest->effective_with_check)
    {
      in_subq->block_conversion_to_sj();
    }
  }
Igor Babaev's avatar
Igor Babaev committed
1172 1173 1174 1175 1176 1177 1178 1179 1180 1181

  if (join->select_options & SELECT_STRAIGHT_JOIN)
  {
    /* Block conversion to semijoins for all candidates */ 
    li.rewind();
    while ((in_subq= li++))
    {
      in_subq->block_conversion_to_sj();
    }
  }
1182
      
Igor Babaev's avatar
Igor Babaev committed
1183
  li.rewind();
1184
  /* First, convert child join's subqueries. We proceed bottom-up here */
Igor Babaev's avatar
Igor Babaev committed
1185
  while ((in_subq= li++)) 
1186
  {
Igor Babaev's avatar
Igor Babaev committed
1187
    st_select_lex *child_select= in_subq->get_select_lex();
1188
    JOIN *child_join= child_select->join;
1189
    child_join->outer_tables = child_join->table_count;
1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200

    /*
      child_select->where contains only the WHERE predicate of the
      subquery itself here. We may be selecting from a VIEW, which has its
      own predicate. The combined predicates are available in child_join->conds,
      which was built by setup_conds() doing prepare_where() for all views.
    */
    child_select->where= child_join->conds;

    if (convert_join_subqueries_to_semijoins(child_join))
      DBUG_RETURN(TRUE);
1201 1202


Igor Babaev's avatar
Igor Babaev committed
1203
    in_subq->sj_convert_priority= 
1204
      MY_TEST(in_subq->do_not_convert_to_sj) * MAX_TABLES * 2 +
Igor Babaev's avatar
Igor Babaev committed
1205
      in_subq->is_correlated * MAX_TABLES + child_join->outer_tables;
1206 1207 1208 1209
  }
  
  // Temporary measure: disable semi-joins when they are together with outer
  // joins.
1210
#if 0  
1211
  if (check_for_outer_joins(join->join_list))
1212
  {
Igor Babaev's avatar
Igor Babaev committed
1213
    in_subq= join->select_lex->sj_subselects.head();
1214 1215
    arena= thd->activate_stmt_arena_if_needed(&backup);
    goto skip_conversion;
1216
  }
1217
#endif
1218 1219 1220 1221 1222 1223 1224
  //dump_TABLE_LIST_struct(select_lex, select_lex->leaf_tables);
  /* 
    2. Pick which subqueries to convert:
      sort the subquery array
      - prefer correlated subqueries over uncorrelated;
      - prefer subqueries that have greater number of outer tables;
  */
Igor Babaev's avatar
Igor Babaev committed
1225 1226
  bubble_sort<Item_in_subselect>(&join->select_lex->sj_subselects,
				 subq_sj_candidate_cmp, NULL);
1227 1228 1229 1230
  // #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
  /* Replace all subqueries to be flattened with Item_int(1) */
  arena= thd->activate_stmt_arena_if_needed(&backup);
 
Igor Babaev's avatar
Igor Babaev committed
1231 1232
  li.rewind();
  while ((in_subq= li++))
1233
  {
1234
    bool remove_item= TRUE;
1235 1236

    /* Stop processing if we've reached a subquery that's attached to the ON clause */
1237
    if (in_subq->do_not_convert_to_sj)
Varun Gupta's avatar
Varun Gupta committed
1238 1239 1240 1241 1242 1243
    {
      OPT_TRACE_TRANSFORM(thd, oto0, oto1,
                          in_subq->get_select_lex()->select_number,
                          "IN (SELECT)", "semijoin");
      oto1.add("converted_to_semi_join", false)
          .add("cause", "subquery attached to the ON clause");
1244
      break;
Varun Gupta's avatar
Varun Gupta committed
1245
    }
1246

Igor Babaev's avatar
Igor Babaev committed
1247
    if (in_subq->is_flattenable_semijoin) 
1248
    {
Varun Gupta's avatar
Varun Gupta committed
1249 1250 1251
      OPT_TRACE_TRANSFORM(thd, oto0, oto1,
                          in_subq->get_select_lex()->select_number,
                          "IN (SELECT)", "semijoin");
1252
      if (join->table_count + 
Igor Babaev's avatar
Igor Babaev committed
1253
          in_subq->unit->first_select()->join->table_count >= MAX_TABLES)
Varun Gupta's avatar
Varun Gupta committed
1254 1255 1256
      {
        oto1.add("converted_to_semi_join", false);
        oto1.add("cause", "table in parent join now exceeds MAX_TABLES");
1257
        break;
Varun Gupta's avatar
Varun Gupta committed
1258
      }
Igor Babaev's avatar
Igor Babaev committed
1259
      if (convert_subq_to_sj(join, in_subq))
1260
        goto restore_arena_and_fail;
Varun Gupta's avatar
Varun Gupta committed
1261
      oto1.add("converted_to_semi_join", true);
1262 1263 1264
    }
    else
    {
1265
      if (join->table_count + 1 >= MAX_TABLES)
1266
        break;
Igor Babaev's avatar
Igor Babaev committed
1267
      if (convert_subq_to_jtbm(join, in_subq, &remove_item))
1268
        goto restore_arena_and_fail;
1269 1270 1271
    }
    if (remove_item)
    {
Igor Babaev's avatar
Igor Babaev committed
1272 1273 1274
      Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
                     &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
      Item *replace_me= in_subq->original_item();
1275
      if (replace_where_subcondition(join, tree, replace_me,
Monty's avatar
Monty committed
1276
                                     new (thd->mem_root) Item_int(thd, 1),
1277
                                     FALSE))
1278
        goto restore_arena_and_fail;
1279
    }
1280
  }
1281
//skip_conversion:
1282 1283 1284 1285
  /* 
    3. Finalize (perform IN->EXISTS rewrite) the subqueries that we didn't
    convert:
  */
Igor Babaev's avatar
Igor Babaev committed
1286
  while (in_subq)
1287
  {
Igor Babaev's avatar
Igor Babaev committed
1288 1289 1290
    JOIN *child_join= in_subq->unit->first_select()->join;
    in_subq->changed= 0;
    in_subq->fixed= 0;
1291 1292

    SELECT_LEX *save_select_lex= thd->lex->current_select;
Igor Babaev's avatar
Igor Babaev committed
1293
    thd->lex->current_select= in_subq->unit->first_select();
1294

Igor Babaev's avatar
Igor Babaev committed
1295
    bool res= in_subq->select_transformer(child_join);
1296 1297 1298

    thd->lex->current_select= save_select_lex;

unknown's avatar
unknown committed
1299
    if (res)
1300 1301
      DBUG_RETURN(TRUE);

Igor Babaev's avatar
Igor Babaev committed
1302 1303
    in_subq->changed= 1;
    in_subq->fixed= 1;
1304

Igor Babaev's avatar
Igor Babaev committed
1305
    Item *substitute= in_subq->substitution;
1306
    bool do_fix_fields= !in_subq->substitution->is_fixed();
Igor Babaev's avatar
Igor Babaev committed
1307 1308 1309
    Item **tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
                   &join->conds : &(in_subq->emb_on_expr_nest->on_expr);
    Item *replace_me= in_subq->original_item();
1310
    if (replace_where_subcondition(join, tree, replace_me, substitute, 
1311 1312
                                   do_fix_fields))
      DBUG_RETURN(TRUE);
Igor Babaev's avatar
Igor Babaev committed
1313
    in_subq->substitution= NULL;
1314 1315 1316 1317 1318
    /*
      If this is a prepared statement, repeat the above operation for
      prep_where (or prep_on_expr). Subquery-to-semijoin conversion is 
      done once for prepared statement.
    */
1319 1320
    if (!thd->stmt_arena->is_conventional())
    {
Igor Babaev's avatar
Igor Babaev committed
1321
      tree= (in_subq->emb_on_expr_nest == NO_JOIN_NEST)?
1322
             &join->select_lex->prep_where : 
Igor Babaev's avatar
Igor Babaev committed
1323
             &(in_subq->emb_on_expr_nest->prep_on_expr);
1324 1325 1326 1327 1328 1329
      /* 
        prep_on_expr/ prep_where may be NULL in some cases. 
        If that is the case, do nothing - simplify_joins() will copy 
        ON/WHERE expression into prep_on_expr/prep_where.
      */
      if (*tree && replace_where_subcondition(join, tree, replace_me, substitute, 
1330 1331 1332
                                     FALSE))
        DBUG_RETURN(TRUE);
    }
1333 1334
    /*
      Revert to the IN->EXISTS strategy in the rare case when the subquery could
1335
      not be flattened.
1336
    */
unknown's avatar
unknown committed
1337
    in_subq->reset_strategy(SUBS_IN_TO_EXISTS);
1338 1339 1340
    if (is_materialization_applicable(thd, in_subq, 
                                      in_subq->unit->first_select()))
    {
unknown's avatar
unknown committed
1341
      in_subq->add_strategy(SUBS_MATERIALIZATION);
1342 1343
    }

Igor Babaev's avatar
Igor Babaev committed
1344
    in_subq= li++;
1345 1346 1347 1348
  }

  if (arena)
    thd->restore_active_arena(arena, &backup);
Igor Babaev's avatar
Igor Babaev committed
1349
  join->select_lex->sj_subselects.empty();
1350
  DBUG_RETURN(FALSE);
1351 1352 1353 1354 1355

restore_arena_and_fail:
  if (arena)
    thd->restore_active_arena(arena, &backup);
  DBUG_RETURN(TRUE);
1356 1357
}

1358

1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383
/*
  Get #output_rows and scan_time estimates for a "delayed" table.

  SYNOPSIS
    get_delayed_table_estimates()
      table         IN    Table to get estimates for
      out_rows      OUT   E(#rows in the table)
      scan_time     OUT   E(scan_time).
      startup_cost  OUT   cost to populate the table.

  DESCRIPTION
    Get #output_rows and scan_time estimates for a "delayed" table. By
    "delayed" here we mean that the table is filled at the start of query
    execution. This means that the optimizer can't use table statistics to 
    get #rows estimate for it, it has to call this function instead.

    This function is expected to make different actions depending on the nature
    of the table. At the moment there is only one kind of delayed tables,
    non-flattenable semi-joins.
*/

void get_delayed_table_estimates(TABLE *table,
                                 ha_rows *out_rows, 
                                 double *scan_time,
                                 double *startup_cost)
1384
{
1385
  Item_in_subselect *item= table->pos_in_table_list->jtbm_subselect;
1386

1387 1388 1389 1390 1391
  DBUG_ASSERT(item->engine->engine_type() ==
              subselect_engine::HASH_SJ_ENGINE);

  subselect_hash_sj_engine *hash_sj_engine=
    ((subselect_hash_sj_engine*)item->engine);
1392

Sergey Petrunya's avatar
Sergey Petrunya committed
1393 1394 1395
  *out_rows= (ha_rows)item->jtbm_record_count;
  *startup_cost= item->jtbm_read_time;

1396
  /* Calculate cost of scanning the temptable */
Sergey Petrunya's avatar
Sergey Petrunya committed
1397 1398
  double data_size= item->jtbm_record_count * 
                    hash_sj_engine->tmp_table->s->reclength;
1399 1400 1401 1402
  /* Do like in handler::read_time */
  *scan_time= data_size/IO_SIZE + 2;
} 

1403

1404 1405 1406 1407
/**
   @brief Replaces an expression destructively inside the expression tree of
   the WHERE clase.

1408 1409 1410 1411 1412
   @note We substitute AND/OR structure because it was copied by
   copy_andor_structure and some changes could be done in the copy but
   should be left permanent, also there could be several layers of AND over
   AND and OR over OR because ::fix_field() possibly is not called.

1413 1414 1415 1416 1417 1418 1419 1420
   @param join The top-level query.
   @param old_cond The expression to be replaced.
   @param new_cond The expression to be substituted.
   @param do_fix_fields If true, Item::fix_fields(THD*, Item**) is called for
   the new expression.
   @return <code>true</code> if there was an error, <code>false</code> if
   successful.
*/
1421

1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439
static bool replace_where_subcondition(JOIN *join, Item **expr, 
                                       Item *old_cond, Item *new_cond,
                                       bool do_fix_fields)
{
  if (*expr == old_cond)
  {
    *expr= new_cond;
    if (do_fix_fields)
      new_cond->fix_fields(join->thd, expr);
    return FALSE;
  }
  
  if ((*expr)->type() == Item::COND_ITEM) 
  {
    List_iterator<Item> li(*((Item_cond*)(*expr))->argument_list());
    Item *item;
    while ((item= li++))
    {
1440
      if (item == old_cond)
1441 1442 1443 1444 1445 1446
      {
        li.replace(new_cond);
        if (do_fix_fields)
          new_cond->fix_fields(join->thd, li.ref());
        return FALSE;
      }
1447 1448 1449 1450 1451 1452
      else if (item->type() == Item::COND_ITEM)
      {
        replace_where_subcondition(join, li.ref(),
                                   old_cond, new_cond,
                                   do_fix_fields);
      }
1453 1454
    }
  }
1455 1456 1457 1458 1459 1460 1461 1462 1463
  /* 
    We can come to here when 
     - we're doing replace operations on both on_expr and prep_on_expr
     - on_expr is the same as prep_on_expr, or they share a sub-tree 
       (so, when we do replace in on_expr, we replace in prep_on_expr, too,
        and when we try doing a replace in prep_on_expr, the item we wanted 
        to replace there has already been replaced)
  */
  return FALSE;
1464 1465
}

Igor Babaev's avatar
Igor Babaev committed
1466 1467
static int subq_sj_candidate_cmp(Item_in_subselect* el1, Item_in_subselect* el2,
                                 void *arg)
1468
{
1469 1470
  return (el1->sj_convert_priority > el2->sj_convert_priority) ? -1 : 
         ( (el1->sj_convert_priority == el2->sj_convert_priority)? 0 : 1);
1471 1472 1473
}


1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527 1528 1529 1530 1531 1532 1533 1534
/**
    @brief
    reset the value of the field in_eqaulity_no for all Item_func_eq
    items in the where clause of the subquery.

    Look for in_equality_no description in Item_func_eq class

    DESCRIPTION
    Lets have an example:
    SELECT t1.a FROM t1 WHERE t1.a IN
      (SELECT t2.a FROM t2 where t2.b IN
          (select t3.b from t3 where t3.c=27 ))

    So for such a query we have the parent, child and
    grandchild select.

    So for the equality t2.b = t3.b we set the value for in_equality_no to
    0 according to its description. Wewe do the same for t1.a = t2.a.
    But when we look at the child select (with the grandchild select merged),
    the query would be

    SELECT t1.a FROM t1 WHERE t1.a IN
      (SELECT t2.a FROM t2 where t2.b = t3.b and t3.c=27)

    and then when the child select is merged into the parent select the query
    would look like

    SELECT t1.a FROM t1, semi-join-nest(t2,t3)
            WHERE t1.a =t2.a and t2.b = t3.b and t3.c=27

    Still we would have in_equality_no set for t2.b = t3.b
    though it does not take part in the semi-join equality for the parent select,
    so we should reset its value to UINT_MAX.

    @param cond WHERE clause of the subquery
*/

static void reset_equality_number_for_subq_conds(Item * cond)
{
  if (!cond)
    return;
  if (cond->type() == Item::COND_ITEM)
  {
    List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
    Item *item;
    while ((item=li++))
    {
      if (item->type() == Item::FUNC_ITEM &&
      ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
        ((Item_func_eq*)item)->in_equality_no= UINT_MAX;
    }
  }
  else
  {
    if (cond->type() == Item::FUNC_ITEM &&
      ((Item_func*)cond)->functype()== Item_func::EQ_FUNC)
        ((Item_func_eq*)cond)->in_equality_no= UINT_MAX;
  }
  return;
}

1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574
/*
  Convert a subquery predicate into a TABLE_LIST semi-join nest

  SYNOPSIS
    convert_subq_to_sj()
       parent_join  Parent join, the one that has subq_pred in its WHERE/ON 
                    clause
       subq_pred    Subquery predicate to be converted
  
  DESCRIPTION
    Convert a subquery predicate into a TABLE_LIST semi-join nest. All the 
    prerequisites are already checked, so the conversion is always successfull.

    Prepared Statements: the transformation is permanent:
     - Changes in TABLE_LIST structures are naturally permanent
     - Item tree changes are performed on statement MEM_ROOT:
        = we activate statement MEM_ROOT 
        = this function is called before the first fix_prepare_information
          call.

    This is intended because the criteria for subquery-to-sj conversion remain
    constant for the lifetime of the Prepared Statement.

  RETURN
    FALSE  OK
    TRUE   Out of memory error
*/

static bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
{
  SELECT_LEX *parent_lex= parent_join->select_lex;
  TABLE_LIST *emb_tbl_nest= NULL;
  List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
  THD *thd= parent_join->thd;
  DBUG_ENTER("convert_subq_to_sj");

  /*
    1. Find out where to put the predicate into.
     Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
  */
1575
  if ((void*)subq_pred->emb_on_expr_nest != (void*)NO_JOIN_NEST)
1576
  {
1577
    if (subq_pred->emb_on_expr_nest->nested_join)
1578 1579 1580 1581 1582 1583 1584 1585
    {
      /*
        We're dealing with

          ... [LEFT] JOIN  ( ... ) ON (subquery AND whatever) ...

        The sj-nest will be inserted into the brackets nest.
      */
1586
      emb_tbl_nest=  subq_pred->emb_on_expr_nest;
1587 1588
      emb_join_list= &emb_tbl_nest->nested_join->join_list;
    }
1589
    else if (!subq_pred->emb_on_expr_nest->outer_join)
1590 1591 1592 1593 1594 1595 1596 1597 1598
    {
      /*
        We're dealing with

          ... INNER JOIN tblX ON (subquery AND whatever) ...

        The sj-nest will be tblX's "sibling", i.e. another child of its
        parent. This is ok because tblX is joined as an inner join.
      */
1599
      emb_tbl_nest= subq_pred->emb_on_expr_nest->embedding;
1600 1601 1602
      if (emb_tbl_nest)
        emb_join_list= &emb_tbl_nest->nested_join->join_list;
    }
1603
    else if (!subq_pred->emb_on_expr_nest->nested_join)
1604
    {
1605
      TABLE_LIST *outer_tbl= subq_pred->emb_on_expr_nest;
1606
      TABLE_LIST *wrap_nest;
1607
      LEX_CSTRING sj_wrap_name= { STRING_WITH_LEN("(sj-wrap)") };
1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626
      /*
        We're dealing with

          ... LEFT JOIN tbl ON (on_expr AND subq_pred) ...

        we'll need to convert it into:

          ... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
                        |                      |
                        |<----- wrap_nest ---->|
        
        Q:  other subqueries may be pointing to this element. What to do?
        A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
            But we'll need to fix other pointers.
        A2: Another way: have TABLE_LIST::next_ptr so the following
            subqueries know the table has been nested.
        A3: changes in the TABLE_LIST::outer_join will make everything work
            automatically.
      */
1627
      if (!(wrap_nest= alloc_join_nest(thd)))
1628 1629 1630 1631 1632
      {
        DBUG_RETURN(TRUE);
      }
      wrap_nest->embedding= outer_tbl->embedding;
      wrap_nest->join_list= outer_tbl->join_list;
1633
      wrap_nest->alias= sj_wrap_name;
1634 1635

      wrap_nest->nested_join->join_list.empty();
1636
      wrap_nest->nested_join->join_list.push_back(outer_tbl, thd->mem_root);
1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671

      outer_tbl->embedding= wrap_nest;
      outer_tbl->join_list= &wrap_nest->nested_join->join_list;

      /*
        wrap_nest will take place of outer_tbl, so move the outer join flag
        and on_expr
      */
      wrap_nest->outer_join= outer_tbl->outer_join;
      outer_tbl->outer_join= 0;

      wrap_nest->on_expr= outer_tbl->on_expr;
      outer_tbl->on_expr= NULL;

      List_iterator<TABLE_LIST> li(*wrap_nest->join_list);
      TABLE_LIST *tbl;
      while ((tbl= li++))
      {
        if (tbl == outer_tbl)
        {
          li.replace(wrap_nest);
          break;
        }
      }
      /*
        Ok now wrap_nest 'contains' outer_tbl and we're ready to add the 
        semi-join nest into it
      */
      emb_join_list= &wrap_nest->nested_join->join_list;
      emb_tbl_nest=  wrap_nest;
    }
  }

  TABLE_LIST *sj_nest;
  NESTED_JOIN *nested_join;
1672
  LEX_CSTRING sj_nest_name= { STRING_WITH_LEN("(sj-nest)") };
1673
  if (!(sj_nest= alloc_join_nest(thd)))
1674 1675 1676 1677 1678 1679 1680
  {
    DBUG_RETURN(TRUE);
  }
  nested_join= sj_nest->nested_join;

  sj_nest->join_list= emb_join_list;
  sj_nest->embedding= emb_tbl_nest;
1681
  sj_nest->alias= sj_nest_name;
1682
  sj_nest->sj_subq_pred= subq_pred;
1683 1684
  sj_nest->original_subq_pred_used_tables= subq_pred->used_tables() |
                                           subq_pred->left_expr->used_tables();
1685 1686
  /* Nests do not participate in those 'chains', so: */
  /* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
1687
  emb_join_list->push_back(sj_nest, thd->mem_root);
1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698

  /* 
    nested_join->used_tables and nested_join->not_null_tables are
    initialized in simplify_joins().
  */
  
  /* 
    2. Walk through subquery's top list and set 'embedding' to point to the
       sj-nest.
  */
  st_select_lex *subq_lex= subq_pred->unit->first_select();
1699
  DBUG_ASSERT(subq_lex->next_select() == NULL);
1700 1701
  nested_join->join_list.empty();
  List_iterator_fast<TABLE_LIST> li(subq_lex->top_join_list);
1702
  TABLE_LIST *tl;
1703 1704 1705 1706
  while ((tl= li++))
  {
    tl->embedding= sj_nest;
    tl->join_list= &nested_join->join_list;
1707
    nested_join->join_list.push_back(tl, thd->mem_root);
1708 1709 1710 1711 1712 1713 1714 1715 1716
  }
  
  /*
    Reconnect the next_leaf chain.
    TODO: Do we have to put subquery's tables at the end of the chain?
          Inserting them at the beginning would be a bit faster.
    NOTE: We actually insert them at the front! That's because the order is
          reversed in this list.
  */
1717
  parent_lex->leaf_tables.append(&subq_lex->leaf_tables);
1718

1719 1720 1721
  if (subq_lex->options & OPTION_SCHEMA_TABLE)
    parent_lex->options |= OPTION_SCHEMA_TABLE;

1722 1723 1724 1725 1726
  /*
    Same as above for next_local chain
    (a theory: a next_local chain always starts with ::leaf_tables
     because view's tables are inserted after the view)
  */
1727 1728 1729 1730
  
  for (tl= (TABLE_LIST*)(parent_lex->table_list.first); tl->next_local; tl= tl->next_local)
  {}

1731
  tl->next_local= subq_lex->join->tables_list;
1732 1733 1734 1735 1736 1737

  /* A theory: no need to re-connect the next_global chain */

  /* 3. Remove the original subquery predicate from the WHERE/ON */

  // The subqueries were replaced for Item_int(1) earlier
unknown's avatar
unknown committed
1738
  subq_pred->reset_strategy(SUBS_SEMI_JOIN);       // for subsequent executions
1739
  /*TODO: also reset the 'm_with_subquery' there. */
1740

1741 1742
  /* n. Adjust the parent_join->table_count counter */
  uint table_no= parent_join->table_count;
1743
  /* n. Walk through child's tables and adjust table->map */
1744 1745
  List_iterator_fast<TABLE_LIST> si(subq_lex->leaf_tables);
  while ((tl= si++))
1746
  {
1747
    tl->set_tablenr(table_no);
1748
    if (tl->is_jtbm())
1749
    {
1750
      tl->jtbm_table_no= table_no;
1751
      Item *dummy= tl->jtbm_subselect;
1752
      tl->jtbm_subselect->fix_after_pullout(parent_lex, &dummy, true);
1753 1754
      DBUG_ASSERT(dummy == tl->jtbm_subselect);
    }
1755 1756 1757 1758 1759 1760
    SELECT_LEX *old_sl= tl->select_lex;
    tl->select_lex= parent_join->select_lex; 
    for (TABLE_LIST *emb= tl->embedding;
         emb && emb->select_lex == old_sl;
         emb= emb->embedding)
      emb->select_lex= parent_join->select_lex;
1761
    table_no++;
1762
  }
1763
  parent_join->table_count += subq_lex->join->table_count;
Sergey Petrunya's avatar
Sergey Petrunya committed
1764
  //parent_join->table_count += subq_lex->leaf_tables.elements;
1765 1766 1767 1768 1769 1770 1771

  /* 
    Put the subquery's WHERE into semi-join's sj_on_expr
    Add the subquery-induced equalities too.
  */
  SELECT_LEX *save_lex= thd->lex->current_select;
  thd->lex->current_select=subq_lex;
1772
  if (subq_pred->left_expr->fix_fields_if_needed(thd, &subq_pred->left_expr))
1773 1774 1775
    DBUG_RETURN(TRUE);
  thd->lex->current_select=save_lex;

1776 1777 1778
  table_map subq_pred_used_tables= subq_pred->used_tables();
  sj_nest->nested_join->sj_corr_tables= subq_pred_used_tables;
  sj_nest->nested_join->sj_depends_on=  subq_pred_used_tables |
1779
                                        subq_pred->left_expr->used_tables();
1780
  sj_nest->sj_on_expr= subq_lex->join->conds;
1781 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 1798

  /*
    Create the IN-equalities and inject them into semi-join's ON expression.
    Additionally, for LooseScan strategy
     - Record the number of IN-equalities.
     - Create list of pointers to (oe1, ..., ieN). We'll need the list to
       see which of the expressions are bound and which are not (for those
       we'll produce a distinct stream of (ie_i1,...ie_ik).

       (TODO: can we just create a list of pointers and hope the expressions
       will not substitute themselves on fix_fields()? or we need to wrap
       them into Item_direct_view_refs and store pointers to those. The
       pointers to Item_direct_view_refs are guaranteed to be stable as 
       Item_direct_view_refs doesn't substitute itself with anything in 
       Item_direct_view_ref::fix_fields.
  */
  sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
  sj_nest->nested_join->sj_outer_expr_list.empty();
1799
  reset_equality_number_for_subq_conds(sj_nest->sj_on_expr);
1800 1801 1802

  if (subq_pred->left_expr->cols() == 1)
  {
1803
    /* add left = select_list_element */
1804
    nested_join->sj_outer_expr_list.push_back(&subq_pred->left_expr,
1805
                                              thd->mem_root);
1806 1807 1808 1809 1810 1811 1812 1813 1814
    /*
      Create Item_func_eq. Note that
      1. this is done on the statement, not execution, arena
      2. if it's a PS then this happens only once - on the first execution.
         On following re-executions, the item will be fix_field-ed normally.
      3. Thus it should be created as if it was fix_field'ed, in particular
         all pointers to items in the execution arena should be protected
         with thd->change_item_tree
    */
1815
    Item_func_eq *item_eq=
1816
      new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr_orig,
1817
                                       subq_lex->ref_pointer_array[0]);
1818 1819
    if (!item_eq)
      DBUG_RETURN(TRUE);
1820 1821
    if (subq_pred->left_expr_orig != subq_pred->left_expr)
      thd->change_item_tree(item_eq->arguments(), subq_pred->left_expr);
1822
    item_eq->in_equality_no= 0;
1823
    sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1824
  }
1825
  else if (subq_pred->left_expr->type() == Item::ROW_ITEM)
1826
  {
1827 1828 1829 1830
    /*
      disassemple left expression and add
      left1 = select_list_element1 and left2 = select_list_element2 ...
    */
1831 1832
    for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
    {
1833
      nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->addr(i),
1834
                                                thd->mem_root);
1835
      Item_func_eq *item_eq=
1836
        new (thd->mem_root)
1837
        Item_func_eq(thd, subq_pred->left_expr_orig->element_index(i),
1838
                     subq_lex->ref_pointer_array[i]);
1839 1840
      if (!item_eq)
        DBUG_RETURN(TRUE);
1841
      DBUG_ASSERT(subq_pred->left_expr->element_index(i)->is_fixed());
1842 1843 1844 1845
      if (subq_pred->left_expr_orig->element_index(i) !=
          subq_pred->left_expr->element_index(i))
        thd->change_item_tree(item_eq->arguments(),
                              subq_pred->left_expr->element_index(i));
1846
      item_eq->in_equality_no= i;
1847
      sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1848 1849
    }
  }
1850 1851 1852 1853 1854 1855
  else
  {
    /*
      add row operation
      left = (select_list_element1, select_list_element2, ...)
    */
1856
    Item_row *row= new (thd->mem_root) Item_row(thd, subq_lex->pre_fix);
1857 1858 1859
    /* fix fields on subquery was call so they should be the same */
    if (!row)
      DBUG_RETURN(TRUE);
1860
    DBUG_ASSERT(subq_pred->left_expr->cols() == row->cols());
1861 1862
    nested_join->sj_outer_expr_list.push_back(&subq_pred->left_expr);
    Item_func_eq *item_eq=
1863
      new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr_orig, row);
1864 1865 1866 1867 1868 1869 1870 1871
    if (!item_eq)
      DBUG_RETURN(TRUE);
    for (uint i= 0; i < row->cols(); i++)
    {
      if (row->element_index(i) != subq_lex->ref_pointer_array[i])
        thd->change_item_tree(row->addr(i), subq_lex->ref_pointer_array[i]);
    }
    item_eq->in_equality_no= 0;
1872
    sj_nest->sj_on_expr= and_items(thd, sj_nest->sj_on_expr, item_eq);
1873
  }
1874 1875 1876 1877 1878 1879 1880 1881 1882
  /*
    Fix the created equality and AND

    Note that fix_fields() can actually fail in a meaningful way here. One
    example is when the IN-equality is not valid, because it compares columns
    with incompatible collations. (One can argue it would be more appropriate
    to check for this at name resolution stage, but as a legacy of IN->EXISTS
    we have in here).
  */
1883
  if (sj_nest->sj_on_expr->fix_fields_if_needed(thd, &sj_nest->sj_on_expr))
1884 1885 1886
  {
    DBUG_RETURN(TRUE);
  }
1887 1888 1889 1890 1891

  /*
    Walk through sj nest's WHERE and ON expressions and call
    item->fix_table_changes() for all items.
  */
1892 1893
  sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr,
                                         TRUE);
1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905
  fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);


  /* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
  subq_lex->master_unit()->exclude_level();

  DBUG_EXECUTE("where",
               print_where(sj_nest->sj_on_expr,"SJ-EXPR", QT_ORDINARY););

  /* Inject sj_on_expr into the parent's WHERE or ON */
  if (emb_tbl_nest)
  {
1906
    emb_tbl_nest->on_expr= and_items(thd, emb_tbl_nest->on_expr,
1907
                                     sj_nest->sj_on_expr);
1908
    emb_tbl_nest->on_expr->top_level_item();
1909 1910
    if (emb_tbl_nest->on_expr->fix_fields_if_needed(thd,
                                                    &emb_tbl_nest->on_expr))
1911 1912 1913
    {
      DBUG_RETURN(TRUE);
    }
1914 1915 1916 1917
  }
  else
  {
    /* Inject into the WHERE */
1918
    parent_join->conds= and_items(thd, parent_join->conds, sj_nest->sj_on_expr);
1919
    parent_join->conds->top_level_item();
unknown's avatar
unknown committed
1920 1921 1922 1923
    /*
      fix_fields must update the properties (e.g. st_select_lex::cond_count of
      the correct select_lex.
    */
unknown's avatar
unknown committed
1924 1925
    save_lex= thd->lex->current_select;
    thd->lex->current_select=parent_join->select_lex;
1926
    if (parent_join->conds->fix_fields_if_needed(thd, &parent_join->conds))
1927 1928 1929
    {
      DBUG_RETURN(1);
    }
unknown's avatar
unknown committed
1930
    thd->lex->current_select=save_lex;
1931 1932 1933 1934 1935 1936 1937 1938
    parent_join->select_lex->where= parent_join->conds;
  }

  if (subq_lex->ftfunc_list->elements)
  {
    Item_func_match *ifm;
    List_iterator_fast<Item_func_match> li(*(subq_lex->ftfunc_list));
    while ((ifm= li++))
1939
      parent_lex->ftfunc_list->push_front(ifm, thd->mem_root);
1940 1941
  }

1942
  parent_lex->have_merged_subqueries= TRUE;
1943 1944
  /* Fatal error may have been set to by fix_after_pullout() */
  DBUG_RETURN(thd->is_fatal_error);
1945 1946
}

1947

1948 1949
const int SUBQERY_TEMPTABLE_NAME_MAX_LEN= 20;

1950
static void create_subquery_temptable_name(LEX_STRING *str, uint number)
1951
{
1952
  char *to= str->str;
1953 1954 1955 1956 1957
  DBUG_ASSERT(number < 10000);       
  to= strmov(to, "<subquery");
  to= int10_to_str((int) number, to, 10);
  to[0]= '>';
  to[1]= 0;
1958
  str->length= (size_t) (to - str->str)+1;
1959 1960
}

1961

Sergey Petrunya's avatar
Sergey Petrunya committed
1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975
/*
  Convert subquery predicate into non-mergeable semi-join nest.

  TODO: 
    why does this do IN-EXISTS conversion? Can't we unify it with mergeable
    semi-joins? currently, convert_subq_to_sj() cannot fail to convert (unless
    fatal errors)

    
  RETURN 
    FALSE - Ok
    TRUE  - Fatal error
*/

1976 1977 1978 1979 1980 1981 1982
static bool convert_subq_to_jtbm(JOIN *parent_join, 
                                 Item_in_subselect *subq_pred, 
                                 bool *remove_item)
{
  SELECT_LEX *parent_lex= parent_join->select_lex;
  List<TABLE_LIST> *emb_join_list= &parent_lex->top_join_list;
  TABLE_LIST *emb_tbl_nest= NULL; // will change when we learn to handle outer joins
1983
  TABLE_LIST *tl;
1984
  bool optimization_delayed= TRUE;
1985
  TABLE_LIST *jtbm;
1986
  LEX_STRING tbl_alias;
1987
  THD *thd= parent_join->thd;
1988
  DBUG_ENTER("convert_subq_to_jtbm");
Sergey Petrunya's avatar
Sergey Petrunya committed
1989

1990
  subq_pred->set_strategy(SUBS_MATERIALIZATION);
Sergey Petrunya's avatar
Sergey Petrunya committed
1991 1992
  subq_pred->is_jtbm_merged= TRUE;

1993 1994
  *remove_item= TRUE;

1995
  if (!(tbl_alias.str= (char*)thd->calloc(SUBQERY_TEMPTABLE_NAME_MAX_LEN)) ||
1996
      !(jtbm= alloc_join_nest(thd))) //todo: this is not a join nest!
1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007
  {
    DBUG_RETURN(TRUE);
  }

  jtbm->join_list= emb_join_list;
  jtbm->embedding= emb_tbl_nest;
  jtbm->jtbm_subselect= subq_pred;
  jtbm->nested_join= NULL;

  /* Nests do not participate in those 'chains', so: */
  /* jtbm->next_leaf= jtbm->next_local= jtbm->next_global == NULL*/
2008
  emb_join_list->push_back(jtbm, thd->mem_root);
2009 2010
  
  /* 
Sergey Petrunya's avatar
Sergey Petrunya committed
2011 2012
    Inject the jtbm table into TABLE_LIST::next_leaf list, so that 
    make_join_statistics() and co. can find it.
2013
  */
2014
  parent_lex->leaf_tables.push_back(jtbm, thd->mem_root);
2015

2016 2017 2018
  if (subq_pred->unit->first_select()->options & OPTION_SCHEMA_TABLE)
    parent_lex->options |= OPTION_SCHEMA_TABLE;

2019
  /*
Sergey Petrunya's avatar
Sergey Petrunya committed
2020
    Same as above for TABLE_LIST::next_local chain
2021 2022 2023
    (a theory: a next_local chain always starts with ::leaf_tables
     because view's tables are inserted after the view)
  */
2024
  for (tl= (TABLE_LIST*)(parent_lex->table_list.first); tl->next_local; tl= tl->next_local)
2025
  {}
2026 2027 2028
  tl->next_local= jtbm;

  /* A theory: no need to re-connect the next_global chain */
2029 2030 2031 2032 2033
  if (optimization_delayed)
  {
    DBUG_ASSERT(parent_join->table_count < MAX_TABLES);

    jtbm->jtbm_table_no= parent_join->table_count;
2034

2035
    create_subquery_temptable_name(&tbl_alias,
2036
                                   subq_pred->unit->first_select()->select_number);
2037 2038
    jtbm->alias.str=    tbl_alias.str;
    jtbm->alias.length= tbl_alias.length;
2039
    parent_join->table_count++;
2040
    DBUG_RETURN(thd->is_fatal_error);
2041
  }
2042 2043 2044 2045
  subselect_hash_sj_engine *hash_sj_engine=
    ((subselect_hash_sj_engine*)subq_pred->engine);
  jtbm->table= hash_sj_engine->tmp_table;

2046 2047
  jtbm->table->tablenr= parent_join->table_count;
  jtbm->table->map= table_map(1) << (parent_join->table_count);
2048
  jtbm->jtbm_table_no= jtbm->table->tablenr;
2049

2050 2051
  parent_join->table_count++;
  DBUG_ASSERT(parent_join->table_count < MAX_TABLES);
2052 2053

  Item *conds= hash_sj_engine->semi_join_conds;
2054
  conds->fix_after_pullout(parent_lex, &conds, TRUE);
2055 2056 2057

  DBUG_EXECUTE("where", print_where(conds,"SJ-EXPR", QT_ORDINARY););
  
2058
  create_subquery_temptable_name(&tbl_alias, hash_sj_engine->materialize_join->
2059
                                              select_lex->select_number);
2060 2061
  jtbm->alias.str=    tbl_alias.str;
  jtbm->alias.length= tbl_alias.length;
2062 2063

  parent_lex->have_merged_subqueries= TRUE;
2064

2065
  /* Don't unlink the child subselect, as the subquery will be used. */
2066

2067
  DBUG_RETURN(thd->is_fatal_error);
2068 2069 2070
}


2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081
static TABLE_LIST *alloc_join_nest(THD *thd)
{
  TABLE_LIST *tbl;
  if (!(tbl= (TABLE_LIST*) thd->calloc(ALIGN_SIZE(sizeof(TABLE_LIST))+
                                       sizeof(NESTED_JOIN))))
    return NULL;
  tbl->nested_join= (NESTED_JOIN*) ((uchar*)tbl + 
                                    ALIGN_SIZE(sizeof(TABLE_LIST)));
  return tbl;
}

2082 2083 2084
/*
  @Note  thd->is_fatal_error can be set in case of OOM
*/
2085 2086 2087 2088 2089 2090 2091 2092

void fix_list_after_tbl_changes(SELECT_LEX *new_parent, List<TABLE_LIST> *tlist)
{
  List_iterator<TABLE_LIST> it(*tlist);
  TABLE_LIST *table;
  while ((table= it++))
  {
    if (table->on_expr)
2093
      table->on_expr->fix_after_pullout(new_parent, &table->on_expr, TRUE);
2094 2095 2096 2097 2098 2099
    if (table->nested_join)
      fix_list_after_tbl_changes(new_parent, &table->nested_join->join_list);
  }
}


2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118
static void set_emb_join_nest(List<TABLE_LIST> *tables, TABLE_LIST *emb_sj_nest)
{
  List_iterator<TABLE_LIST> it(*tables);
  TABLE_LIST *tbl;
  while ((tbl= it++))
  {
    /*
      Note: check for nested_join first. 
       derived-merged tables have tbl->table!=NULL &&
       tbl->table->reginfo==NULL.
    */
    if (tbl->nested_join)
      set_emb_join_nest(&tbl->nested_join->join_list, emb_sj_nest);
    else if (tbl->table)
      tbl->table->reginfo.join_tab->emb_sj_nest= emb_sj_nest;

  }
}

2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175
/*
  Pull tables out of semi-join nests, if possible

  SYNOPSIS
    pull_out_semijoin_tables()
      join  The join where to do the semi-join flattening

  DESCRIPTION
    Try to pull tables out of semi-join nests.
     
    PRECONDITIONS
    When this function is called, the join may have several semi-join nests
    but it is guaranteed that one semi-join nest does not contain another.
   
    ACTION
    A table can be pulled out of the semi-join nest if
     - It is a constant table, or
     - It is accessed via eq_ref(outer_tables)

    POSTCONDITIONS
     * Tables that were pulled out have JOIN_TAB::emb_sj_nest == NULL
     * Tables that were not pulled out have JOIN_TAB::emb_sj_nest pointing 
       to semi-join nest they are in.
     * Semi-join nests' TABLE_LIST::sj_inner_tables is updated accordingly

    This operation is (and should be) performed at each PS execution since
    tables may become/cease to be constant across PS reexecutions.
    
  NOTE
    Table pullout may make uncorrelated subquery correlated. Consider this
    example:
    
     ... WHERE oe IN (SELECT it1.primary_key WHERE p(it1, it2) ... ) 
    
    here table it1 can be pulled out (we have it1.primary_key=oe which gives
    us functional dependency). Once it1 is pulled out, all references to it1
    from p(it1, it2) become references to outside of the subquery and thus
    make the subquery (i.e. its semi-join nest) correlated.
    Making the subquery (i.e. its semi-join nest) correlated prevents us from
    using Materialization or LooseScan to execute it. 

  RETURN 
    0 - OK
    1 - Out of memory error
*/

int pull_out_semijoin_tables(JOIN *join)
{
  TABLE_LIST *sj_nest;
  DBUG_ENTER("pull_out_semijoin_tables");
  List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
   
  /* Try pulling out of the each of the semi-joins */
  while ((sj_nest= sj_list_it++))
  {
    List_iterator<TABLE_LIST> child_li(sj_nest->nested_join->join_list);
    TABLE_LIST *tbl;
2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195

    /*
      Don't do table pull-out for nested joins (if we get nested joins here, it
      means these are outer joins. It is theoretically possible to do pull-out
      for some of the outer tables but we dont support this currently.
    */
    bool have_join_nest_children= FALSE;

    set_emb_join_nest(&sj_nest->nested_join->join_list, sj_nest);

    while ((tbl= child_li++))
    {
      if (tbl->nested_join)
      {
        have_join_nest_children= TRUE;
        break;
      }
    }
    
    table_map pulled_tables= 0;
2196
    table_map dep_tables= 0;
2197 2198 2199
    if (have_join_nest_children)
      goto skip;

2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213
    /*
      Calculate set of tables within this semi-join nest that have
      other dependent tables
    */
    child_li.rewind();
    while ((tbl= child_li++))
    {
      TABLE *const table= tbl->table;
      if (table &&
         (table->reginfo.join_tab->dependent &
          sj_nest->nested_join->used_tables))
        dep_tables|= table->reginfo.join_tab->dependent;
    }

2214 2215
    /* Action #1: Mark the constant tables to be pulled out */
    child_li.rewind();
2216 2217 2218 2219 2220
    while ((tbl= child_li++))
    {
      if (tbl->table)
      {
        tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241
#if 0 
        /* 
          Do not pull out tables because they are constant. This operation has
          a problem:
          - Some constant tables may become/cease to be constant across PS
            re-executions
          - Contrary to our initial assumption, it turned out that table pullout 
            operation is not easily undoable.

          The solution is to leave constant tables where they are. This will
          affect only constant tables that are 1-row or empty, tables that are
          constant because they are accessed via eq_ref(const) access will
          still be pulled out as functionally-dependent.

          This will cause us to miss the chance to flatten some of the 
          subqueries, but since const tables do not generate many duplicates,
          it really doesn't matter that much whether they were pulled out or
          not.

          All of this was done as fix for BUG#43768.
        */
2242 2243 2244 2245 2246 2247
        if (tbl->table->map & join->const_table_map)
        {
          pulled_tables |= tbl->table->map;
          DBUG_PRINT("info", ("Table %s pulled out (reason: constant)",
                              tbl->table->alias));
        }
2248
#endif
2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263
      }
    }
    
    /*
      Action #2: Find which tables we can pull out based on
      update_ref_and_keys() data. Note that pulling one table out can allow
      us to pull out some other tables too.
    */
    bool pulled_a_table;
    do 
    {
      pulled_a_table= FALSE;
      child_li.rewind();
      while ((tbl= child_li++))
      {
2264 2265
        if (tbl->table && !(pulled_tables & tbl->table->map) &&
            !(dep_tables & tbl->table->map))
2266 2267 2268 2269 2270 2271 2272 2273
        {
          if (find_eq_ref_candidate(tbl->table, 
                                    sj_nest->nested_join->used_tables & 
                                    ~pulled_tables))
          {
            pulled_a_table= TRUE;
            pulled_tables |= tbl->table->map;
            DBUG_PRINT("info", ("Table %s pulled out (reason: func dep)",
2274
                                tbl->table->alias.c_ptr()));
2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287
            /*
              Pulling a table out of uncorrelated subquery in general makes
              makes it correlated. See the NOTE to this funtion. 
            */
            sj_nest->sj_subq_pred->is_correlated= TRUE;
            sj_nest->nested_join->sj_corr_tables|= tbl->table->map;
            sj_nest->nested_join->sj_depends_on|= tbl->table->map;
          }
        }
      }
    } while (pulled_a_table);
 
    child_li.rewind();
2288
  skip:
2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321
    /*
      Action #3: Move the pulled out TABLE_LIST elements to the parents.
    */
    table_map inner_tables= sj_nest->nested_join->used_tables & 
                            ~pulled_tables;
    /* Record the bitmap of inner tables */
    sj_nest->sj_inner_tables= inner_tables;
    if (pulled_tables)
    {
      List<TABLE_LIST> *upper_join_list= (sj_nest->embedding != NULL)?
                                           (&sj_nest->embedding->nested_join->join_list): 
                                           (&join->select_lex->top_join_list);
      Query_arena *arena, backup;
      arena= join->thd->activate_stmt_arena_if_needed(&backup);
      while ((tbl= child_li++))
      {
        if (tbl->table)
        {
          if (inner_tables & tbl->table->map)
          {
            /* This table is not pulled out */
            tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
          }
          else
          {
            /* This table has been pulled out of the semi-join nest */
            tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
            /*
              Pull the table up in the same way as simplify_joins() does:
              update join_list and embedding pointers but keep next[_local]
              pointers.
            */
            child_li.remove();
2322
            sj_nest->nested_join->used_tables &= ~tbl->table->map;
2323
            upper_join_list->push_back(tbl, join->thd->mem_root);
2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367
            tbl->join_list= upper_join_list;
            tbl->embedding= sj_nest->embedding;
          }
        }
      }

      /* Remove the sj-nest itself if we've removed everything from it */
      if (!inner_tables)
      {
        List_iterator<TABLE_LIST> li(*upper_join_list);
        /* Find the sj_nest in the list. */
        while (sj_nest != li++) ;
        li.remove();
        /* Also remove it from the list of SJ-nests: */
        sj_list_it.remove();
      }

      if (arena)
        join->thd->restore_active_arena(arena, &backup);
    }
  }
  DBUG_RETURN(0);
}


/* 
  Optimize semi-join nests that could be run with sj-materialization

  SYNOPSIS
    optimize_semijoin_nests()
      join           The join to optimize semi-join nests for
      all_table_map  Bitmap of all tables in the join

  DESCRIPTION
    Optimize each of the semi-join nests that can be run with
    materialization. For each of the nests, we
     - Generate the best join order for this "sub-join" and remember it;
     - Remember the sub-join execution cost (it's part of materialization
       cost);
     - Calculate other costs that will be incurred if we decide 
       to use materialization strategy for this semi-join nest.

    All obtained information is saved and will be used by the main join
    optimization pass.
2368 2369 2370
  
  NOTES 
    Because of Join::reoptimize(), this function may be called multiple times.
2371 2372 2373 2374 2375 2376 2377 2378 2379

  RETURN
    FALSE  Ok 
    TRUE   Out of memory error
*/

bool optimize_semijoin_nests(JOIN *join, table_map all_table_map)
{
  DBUG_ENTER("optimize_semijoin_nests");
Varun Gupta's avatar
Varun Gupta committed
2380
  THD *thd= join->thd;
2381 2382
  List_iterator<TABLE_LIST> sj_list_it(join->select_lex->sj_nests);
  TABLE_LIST *sj_nest;
Varun Gupta's avatar
Varun Gupta committed
2383 2384 2385 2386
  Json_writer_object wrapper(thd);
  Json_writer_object trace_semijoin_nest(thd,
                              "execution_plan_for_potential_materialization");
  Json_writer_array trace_steps_array(thd, "steps");
2387
  while ((sj_nest= sj_list_it++))
2388
  {
2389 2390
    /* semi-join nests with only constant tables are not valid */
   /// DBUG_ASSERT(sj_nest->sj_inner_tables & ~join->const_table_map);
2391

2392 2393 2394 2395 2396 2397 2398 2399 2400
    sj_nest->sj_mat_info= NULL;
    /*
      The statement may have been executed with 'semijoin=on' earlier.
      We need to verify that 'semijoin=on' still holds.
     */
    if (optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN) &&
        optimizer_flag(join->thd, OPTIMIZER_SWITCH_MATERIALIZATION))
    {
      if ((sj_nest->sj_inner_tables  & ~join->const_table_map) && /* not everything was pulled out */
2401 2402 2403 2404
          !sj_nest->sj_subq_pred->is_correlated && 
           sj_nest->sj_subq_pred->types_allow_materialization)
      {
        join->emb_sjm_nest= sj_nest;
2405
        if (choose_plan(join, all_table_map &~join->const_table_map))
2406 2407 2408 2409 2410
          DBUG_RETURN(TRUE); /* purecov: inspected */
        /*
          The best plan to run the subquery is now in join->best_positions,
          save it.
        */
2411
        uint n_tables= my_count_bits(sj_nest->sj_inner_tables & ~join->const_table_map);
2412 2413 2414 2415 2416 2417 2418 2419
        SJ_MATERIALIZATION_INFO* sjm;
        if (!(sjm= new SJ_MATERIALIZATION_INFO) ||
            !(sjm->positions= (POSITION*)join->thd->alloc(sizeof(POSITION)*
                                                          n_tables)))
          DBUG_RETURN(TRUE); /* purecov: inspected */
        sjm->tables= n_tables;
        sjm->is_used= FALSE;
        double subjoin_out_rows, subjoin_read_time;
Sergey Petrunya's avatar
Sergey Petrunya committed
2420 2421

        /*
Sergey Petrunya's avatar
Sergey Petrunya committed
2422 2423 2424 2425
        join->get_partial_cost_and_fanout(n_tables + join->const_tables,
                                          table_map(-1),
                                          &subjoin_read_time, 
                                          &subjoin_out_rows);
Sergey Petrunya's avatar
Sergey Petrunya committed
2426 2427 2428 2429
        */
        join->get_prefix_cost_and_fanout(n_tables, 
                                         &subjoin_read_time,
                                         &subjoin_out_rows);
2430 2431 2432

        sjm->materialization_cost.convert_from_cost(subjoin_read_time);
        sjm->rows= subjoin_out_rows;
2433 2434 2435 2436 2437 2438
        
        // Don't use the following list because it has "stale" items. use
        // ref_pointer_array instead:
        //
        //List<Item> &right_expr_list= 
        //  sj_nest->sj_subq_pred->unit->first_select()->item_list;
2439 2440 2441 2442 2443 2444 2445 2446 2447 2448 2449 2450 2451 2452
        /*
          Adjust output cardinality estimates. If the subquery has form

           ... oe IN (SELECT t1.colX, t2.colY, func(X,Y,Z) )

           then the number of distinct output record combinations has an
           upper bound of product of number of records matching the tables 
           that are used by the SELECT clause.
           TODO:
             We can get a more precise estimate if we
              - use rec_per_key cardinality estimates. For simple cases like 
                "oe IN (SELECT t.key ...)" it is trivial. 
              - Functional dependencies between the tables in the semi-join
                nest (the payoff is probably less here?)
2453 2454
          
          See also get_post_group_estimate().
2455
        */
2456
        SELECT_LEX *subq_select= sj_nest->sj_subq_pred->unit->first_select();
2457 2458 2459 2460 2461 2462 2463
        {
          for (uint i=0 ; i < join->const_tables + sjm->tables ; i++)
          {
            JOIN_TAB *tab= join->best_positions[i].table;
            join->map2table[tab->table->tablenr]= tab;
          }
          table_map map= 0;
2464 2465
          for (uint i=0; i < subq_select->item_list.elements; i++)
            map|= subq_select->ref_pointer_array[i]->used_tables();
2466 2467 2468 2469 2470 2471
          map= map & ~PSEUDO_TABLE_BITS;
          Table_map_iterator tm_it(map);
          int tableno;
          double rows= 1.0;
          while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
            rows *= join->map2table[tableno]->table->quick_condition_rows;
2472
          sjm->rows= MY_MIN(sjm->rows, rows);
2473
        }
2474 2475
        memcpy((uchar*) sjm->positions,
               (uchar*) (join->best_positions + join->const_tables),
2476 2477 2478 2479 2480
               sizeof(POSITION) * n_tables);

        /*
          Calculate temporary table parameters and usage costs
        */
2481 2482
        uint rowlen= get_tmp_table_rec_length(subq_select->ref_pointer_array,
                                              subq_select->item_list.elements);
unknown's avatar
unknown committed
2483 2484 2485 2486
        double lookup_cost= get_tmp_table_lookup_cost(join->thd,
                                                      subjoin_out_rows, rowlen);
        double write_cost= get_tmp_table_write_cost(join->thd,
                                                    subjoin_out_rows, rowlen);
2487 2488 2489 2490 2491

        /*
          Let materialization cost include the cost to write the data into the
          temporary table:
        */ 
unknown's avatar
unknown committed
2492
        sjm->materialization_cost.add_io(subjoin_out_rows, write_cost);
2493 2494 2495 2496 2497
        
        /*
          Set the cost to do a full scan of the temptable (will need this to 
          consider doing sjm-scan):
        */ 
2498
        sjm->scan_cost.reset();
2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510
        sjm->scan_cost.add_io(sjm->rows, lookup_cost);

        sjm->lookup_cost.convert_from_cost(lookup_cost);
        sj_nest->sj_mat_info= sjm;
        DBUG_EXECUTE("opt", print_sjm(sjm););
      }
    }
  }
  join->emb_sjm_nest= NULL;
  DBUG_RETURN(FALSE);
}

2511

2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523 2524 2525 2526 2527 2528
/*
  Get estimated record length for semi-join materialization temptable
  
  SYNOPSIS
    get_tmp_table_rec_length()
      items  IN subquery's select list.

  DESCRIPTION
    Calculate estimated record length for semi-join materialization
    temptable. It's an estimate because we don't follow every bit of
    create_tmp_table()'s logic. This isn't necessary as the return value of
    this function is used only for cost calculations.

  RETURN
    Length of the temptable record, in bytes
*/

2529
static uint get_tmp_table_rec_length(Ref_ptr_array p_items, uint elements)
2530 2531 2532
{
  uint len= 0;
  Item *item;
2533
  //List_iterator<Item> it(items);
2534
  for (uint i= 0; i < elements ; i++)
2535
  {
2536
    item = p_items[i];
2537 2538 2539 2540 2541 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 2558 2559 2560 2561 2562 2563 2564 2565 2566 2567 2568
    switch (item->result_type()) {
    case REAL_RESULT:
      len += sizeof(double);
      break;
    case INT_RESULT:
      if (item->max_length >= (MY_INT32_NUM_DECIMAL_DIGITS - 1))
        len += 8;
      else
        len += 4;
      break;
    case STRING_RESULT:
      enum enum_field_types type;
      /* DATE/TIME and GEOMETRY fields have STRING_RESULT result type.  */
      if ((type= item->field_type()) == MYSQL_TYPE_DATETIME ||
          type == MYSQL_TYPE_TIME || type == MYSQL_TYPE_DATE ||
          type == MYSQL_TYPE_TIMESTAMP || type == MYSQL_TYPE_GEOMETRY)
        len += 8;
      else
        len += item->max_length;
      break;
    case DECIMAL_RESULT:
      len += 10;
      break;
    case ROW_RESULT:
    default:
      DBUG_ASSERT(0); /* purecov: deadcode */
      break;
    }
  }
  return len;
}

unknown's avatar
unknown committed
2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580

/**
  The cost of a lookup into a unique hash/btree index on a temporary table
  with 'row_count' rows each of size 'row_size'.

  @param thd  current query context
  @param row_count  number of rows in the temp table
  @param row_size   average size in bytes of the rows

  @return  the cost of one lookup
*/

2581
double
unknown's avatar
unknown committed
2582
get_tmp_table_lookup_cost(THD *thd, double row_count, uint row_size)
unknown's avatar
unknown committed
2583 2584 2585 2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600
{
  if (row_count * row_size > thd->variables.max_heap_table_size)
    return (double) DISK_TEMPTABLE_LOOKUP_COST;
  else
    return (double) HEAP_TEMPTABLE_LOOKUP_COST;
}

/**
  The cost of writing a row into a temporary table with 'row_count' unique
  rows each of size 'row_size'.

  @param thd  current query context
  @param row_count  number of rows in the temp table
  @param row_size   average size in bytes of the rows

  @return  the cost of writing one row
*/

2601
double
unknown's avatar
unknown committed
2602
get_tmp_table_write_cost(THD *thd, double row_count, uint row_size)
unknown's avatar
unknown committed
2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613
{
  double lookup_cost= get_tmp_table_lookup_cost(thd, row_count, row_size);
  /*
    TODO:
    This is an optimistic estimate. Add additional costs resulting from
    actually writing the row to memory/disk and possible index reorganization.
  */
  return lookup_cost;
}


2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629
/*
  Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate

  SYNOPSIS
    find_eq_ref_candidate()
      table             Table to be checked
      sj_inner_tables   Bitmap of inner tables. eq_ref(inner_table) doesn't
                        count.

  DESCRIPTION
    Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate

  TODO
    Check again if it is feasible to factor common parts with constant table
    search

Sergey Petrunya's avatar
Sergey Petrunya committed
2630 2631
    Also check if it's feasible to factor common parts with table elimination

2632 2633 2634 2635 2636 2637 2638 2639 2640 2641 2642
  RETURN
    TRUE  - There exists an eq_ref(outer-tables) candidate
    FALSE - Otherwise
*/

bool find_eq_ref_candidate(TABLE *table, table_map sj_inner_tables)
{
  KEYUSE *keyuse= table->reginfo.join_tab->keyuse;

  if (keyuse)
  {
2643
    do
2644
    {
2645
      uint key= keyuse->key;
2646
      KEY *keyinfo;
2647
      key_part_map bound_parts= 0;
2648 2649 2650 2651
      bool is_excluded_key= keyuse->is_for_hash_join(); 
      if (!is_excluded_key)
      {
        keyinfo= table->key_info + key;
2652
        is_excluded_key= !MY_TEST(keyinfo->flags & HA_NOSAME);
2653 2654
      }
      if (!is_excluded_key)
2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666
      {
        do  /* For all equalities on all key parts */
        {
          /* Check if this is "t.keypart = expr(outer_tables) */
          if (!(keyuse->used_tables & sj_inner_tables) &&
              !(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
          {
            bound_parts |= 1 << keyuse->keypart;
          }
          keyuse++;
        } while (keyuse->key == key && keyuse->table == table);

2667
        if (bound_parts == PREV_BITS(uint, keyinfo->user_defined_key_parts))
2668 2669 2670 2671 2672 2673 2674
          return TRUE;
      }
      else
      {
        do
        {
          keyuse++;
2675
        } while (keyuse->key == key && keyuse->table == table);
2676
      }
2677
    } while (keyuse->table == table);
2678 2679 2680 2681
  }
  return FALSE;
}

2682

2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730
/*
  Do semi-join optimization step after we've added a new tab to join prefix

  SYNOPSIS
    advance_sj_state()
      join                        The join we're optimizing
      remaining_tables            Tables not in the join prefix
      new_join_tab                Join tab we've just added to the join prefix
      idx                         Index of this join tab (i.e. number of tables
                                  in the prefix minus one)
      current_record_count INOUT  Estimate of #records in join prefix's output
      current_read_time    INOUT  Cost to execute the join prefix
      loose_scan_pos       IN     A POSITION with LooseScan plan to access 
                                  table new_join_tab
                                  (produced by the last best_access_path call)

  DESCRIPTION
    Update semi-join optimization state after we've added another tab (table 
    and access method) to the join prefix.
    
    The state is maintained in join->positions[#prefix_size]. Each of the
    available strategies has its own state variables.
    
    for each semi-join strategy
    {
      update strategy's state variables;

      if (join prefix has all the tables that are needed to consider
          using this strategy for the semi-join(s))
      {
        calculate cost of using the strategy
        if ((this is the first strategy to handle the semi-join nest(s)  ||
            the cost is less than other strategies))
        {
          // Pick this strategy
          pos->sj_strategy= ..
          ..
        }
      }

    Most of the new state is saved join->positions[idx] (and hence no undo
    is necessary). Several members of class JOIN are updated also, these
    changes can be rolled back with restore_prev_sj_state().

    See setup_semijoin_dups_elimination() for a description of what kinds of
    join prefixes each strategy can handle.
*/

2731
bool is_multiple_semi_joins(JOIN *join, POSITION *prefix, uint idx, table_map inner_tables)
2732 2733 2734 2735 2736 2737 2738
{
  for (int i= (int)idx; i >= 0; i--)
  {
    TABLE_LIST *emb_sj_nest;
    if ((emb_sj_nest= prefix[i].table->emb_sj_nest))
    {
      if (inner_tables & emb_sj_nest->sj_inner_tables)
2739 2740
        return !MY_TEST(inner_tables == (emb_sj_nest->sj_inner_tables &
                                         ~join->const_table_map));
2741 2742 2743 2744
    }
  }
  return FALSE;
}
2745

2746 2747 2748

void advance_sj_state(JOIN *join, table_map remaining_tables, uint idx, 
                      double *current_record_count, double *current_read_time,
2749 2750 2751
                      POSITION *loose_scan_pos)
{
  POSITION *pos= join->positions + idx;
2752 2753 2754 2755 2756 2757 2758 2759 2760
  const JOIN_TAB *new_join_tab= pos->table; 
  Semi_join_strategy_picker *pickers[]=
  {
    &pos->firstmatch_picker,
    &pos->loosescan_picker,
    &pos->sjmat_picker,
    &pos->dups_weedout_picker,
    NULL,
  };
2761 2762 2763

  if (join->emb_sjm_nest)
  {
2764 2765 2766 2767 2768 2769
    /* 
      We're performing optimization inside SJ-Materialization nest:
       - there are no other semi-joins inside semi-join nests
       - attempts to build semi-join strategies here will confuse
         the optimizer, so bail out.
    */
2770
    pos->sj_strategy= SJ_OPT_NONE;
2771 2772 2773
    return;
  }

2774 2775 2776 2777 2778
  /* 
    Update join->cur_sj_inner_tables (Used by FirstMatch in this function and
    LooseScan detector in best_access_path)
  */
  remaining_tables &= ~new_join_tab->table->map;
Monty's avatar
Monty committed
2779 2780
  table_map dups_producing_tables, UNINIT_VAR(prev_dups_producing_tables),
    UNINIT_VAR(prev_sjm_lookup_tables);
2781 2782 2783 2784 2785 2786

  if (idx == join->const_tables)
    dups_producing_tables= 0;
  else
    dups_producing_tables= pos[-1].dups_producing_tables;

2787 2788
  TABLE_LIST *emb_sj_nest;
  if ((emb_sj_nest= new_join_tab->emb_sj_nest))
2789
    dups_producing_tables |= emb_sj_nest->sj_inner_tables;
2790

Monty's avatar
Monty committed
2791
  Semi_join_strategy_picker **strategy, **prev_strategy= 0;
2792 2793
  if (idx == join->const_tables)
  {
2794 2795 2796 2797
    /* First table, initialize pickers */
    for (strategy= pickers; *strategy != NULL; strategy++)
      (*strategy)->set_empty();
    pos->inner_tables_handled_with_other_sjs= 0;
2798 2799 2800
  }
  else
  {
2801
    for (strategy= pickers; *strategy != NULL; strategy++)
2802
    {
2803
      (*strategy)->set_from_prev(pos - 1);
2804
    }
2805 2806 2807 2808 2809 2810 2811 2812 2813
    pos->inner_tables_handled_with_other_sjs=
       pos[-1].inner_tables_handled_with_other_sjs;
  }

  pos->prefix_cost.convert_from_cost(*current_read_time);
  pos->prefix_record_count= *current_record_count;

  {
    pos->sj_strategy= SJ_OPT_NONE;
2814

2815
    for (strategy= pickers; *strategy != NULL; strategy++)
2816
    {
2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827
      table_map handled_fanout;
      sj_strategy_enum sj_strategy;
      double rec_count= *current_record_count;
      double read_time= *current_read_time;
      if ((*strategy)->check_qep(join, idx, remaining_tables, 
                                 new_join_tab,
                                 &rec_count,
                                 &read_time,
                                 &handled_fanout,
                                 &sj_strategy,
                                 loose_scan_pos))
2828 2829
      {
        /*
2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840
          It's possible to use the strategy. Use it, if
           - it removes semi-join fanout that was not removed before
           - using it is cheaper than using something else,
               and {if some other strategy has removed fanout
               that this strategy is trying to remove, then it
               did remove the fanout only for one semi-join}
               This is to avoid a situation when
                1. strategy X removes fanout for semijoin X,Y
                2. using strategy Z is cheaper, but it only removes
                   fanout from semijoin X.
                3. We have no clue what to do about fanount of semi-join Y.
2841
        */
2842
        if ((dups_producing_tables & handled_fanout) ||
2843
            (read_time < *current_read_time &&
2844 2845
             !(handled_fanout & pos->inner_tables_handled_with_other_sjs)))
        {
2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877
          DBUG_ASSERT(pos->sj_strategy != sj_strategy);
          /*
            If the strategy choosen first time or
            the strategy replace strategy which was used to exectly the same
            tables
          */
          if (pos->sj_strategy == SJ_OPT_NONE ||
              handled_fanout ==
                (prev_dups_producing_tables ^ dups_producing_tables))
          {
            prev_strategy= strategy;
            if (pos->sj_strategy == SJ_OPT_NONE)
            {
              prev_dups_producing_tables= dups_producing_tables;
              prev_sjm_lookup_tables= join->sjm_lookup_tables;
            }
            /* Mark strategy as used */
            (*strategy)->mark_used();
            pos->sj_strategy= sj_strategy;
            if (sj_strategy == SJ_OPT_MATERIALIZE)
              join->sjm_lookup_tables |= handled_fanout;
            else
              join->sjm_lookup_tables &= ~handled_fanout;
            *current_read_time= read_time;
            *current_record_count= rec_count;
            dups_producing_tables &= ~handled_fanout;
            //TODO: update bitmap of semi-joins that were handled together with
            // others.
            if (is_multiple_semi_joins(join, join->positions, idx,
                                       handled_fanout))
              pos->inner_tables_handled_with_other_sjs |= handled_fanout;
          }
Igor Babaev's avatar
Igor Babaev committed
2878
          else
2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2889 2890
          {
            /* Conflict fall to most general variant */
            (*prev_strategy)->set_empty();
            dups_producing_tables= prev_dups_producing_tables;
            join->sjm_lookup_tables= prev_sjm_lookup_tables;
            // mark it 'none' to avpoid loops
            pos->sj_strategy= SJ_OPT_NONE;
            // next skip to last;
            strategy= pickers +
              (sizeof(pickers)/sizeof(Semi_join_strategy_picker*) - 3);
            continue;
          }
2891 2892 2893 2894 2895 2896
        }
        else
        {
          /* We decided not to apply the strategy. */
          (*strategy)->set_empty();
        }
2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909 2910
      }
    }
  }

  if ((emb_sj_nest= new_join_tab->emb_sj_nest))
  {
    join->cur_sj_inner_tables |= emb_sj_nest->sj_inner_tables;

    /* Remove the sj_nest if all of its SJ-inner tables are in cur_table_map */
    if (!(remaining_tables &
          emb_sj_nest->sj_inner_tables & ~new_join_tab->table->map))
      join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
  }

2911 2912
  pos->prefix_cost.convert_from_cost(*current_read_time);
  pos->prefix_record_count= *current_record_count;
2913
  pos->dups_producing_tables= dups_producing_tables;
2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939
}


void Sj_materialization_picker::set_from_prev(struct st_position *prev)
{
  if (prev->sjmat_picker.is_used)
    set_empty();
  else
  {
    sjm_scan_need_tables= prev->sjmat_picker.sjm_scan_need_tables; 
    sjm_scan_last_inner=  prev->sjmat_picker.sjm_scan_last_inner;
  }
  is_used= FALSE;
}


bool Sj_materialization_picker::check_qep(JOIN *join,
                                          uint idx,
                                          table_map remaining_tables, 
                                          const JOIN_TAB *new_join_tab,
                                          double *record_count,
                                          double *read_time,
                                          table_map *handled_fanout,
                                          sj_strategy_enum *strategy,
                                          POSITION *loose_scan_pos)
{
2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965
  bool sjm_scan;
  SJ_MATERIALIZATION_INFO *mat_info;
  if ((mat_info= at_sjmat_pos(join, remaining_tables,
                              new_join_tab, idx, &sjm_scan)))
  {
    if (sjm_scan)
    {
      /*
        We can't yet evaluate this option yet. This is because we can't
        accout for fanout of sj-inner tables yet:

          ntX  SJM-SCAN(it1 ... itN) | ot1 ... otN  |
                                     ^(1)           ^(2)

        we're now at position (1). SJM temptable in general has multiple
        records, so at point (1) we'll get the fanout from sj-inner tables (ie
        there will be multiple record combinations).

        The final join result will not contain any semi-join produced
        fanout, i.e. tables within SJM-SCAN(...) will not contribute to
        the cardinality of the join output.  Extra fanout produced by 
        SJM-SCAN(...) will be 'absorbed' into fanout produced by ot1 ...  otN.

        The simple way to model this is to remove SJM-SCAN(...) fanout once
        we reach the point #2.
      */
2966
      sjm_scan_need_tables=
2967 2968 2969
        new_join_tab->emb_sj_nest->sj_inner_tables | 
        new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
        new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
2970
      sjm_scan_last_inner= idx;
2971 2972 2973 2974
    }
    else
    {
      /* This is SJ-Materialization with lookups */
2975
      Cost_estimate prefix_cost; 
2976 2977 2978 2979
      signed int first_tab= (int)idx - mat_info->tables;
      double prefix_rec_count;
      if (first_tab < (int)join->const_tables)
      {
2980
        prefix_cost.reset();
2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992
        prefix_rec_count= 1.0;
      }
      else
      {
        prefix_cost= join->positions[first_tab].prefix_cost;
        prefix_rec_count= join->positions[first_tab].prefix_record_count;
      }

      double mat_read_time= prefix_cost.total_cost();
      mat_read_time += mat_info->materialization_cost.total_cost() +
                       prefix_rec_count * mat_info->lookup_cost.total_cost();

2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003
      /*
        NOTE: When we pick to use SJM[-Scan] we don't memcpy its POSITION
        elements to join->positions as that makes it hard to return things
        back when making one step back in join optimization. That's done 
        after the QEP has been chosen.
      */
      *read_time=    mat_read_time;
      *record_count= prefix_rec_count;
      *handled_fanout= new_join_tab->emb_sj_nest->sj_inner_tables;
      *strategy= SJ_OPT_MATERIALIZE;
      return TRUE;
3004 3005 3006 3007
    }
  }
  
  /* 4.A SJM-Scan second phase check */
3008 3009
  if (sjm_scan_need_tables && /* Have SJM-Scan prefix */
      !(sjm_scan_need_tables & remaining_tables))
3010 3011
  {
    TABLE_LIST *mat_nest= 
3012
      join->positions[sjm_scan_last_inner].table->emb_sj_nest;
3013 3014 3015 3016
    SJ_MATERIALIZATION_INFO *mat_info= mat_nest->sj_mat_info;

    double prefix_cost;
    double prefix_rec_count;
3017
    int first_tab= sjm_scan_last_inner + 1 - mat_info->tables;
3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041
    /* Get the prefix cost */
    if (first_tab == (int)join->const_tables)
    {
      prefix_rec_count= 1.0;
      prefix_cost= 0.0;
    }
    else
    {
      prefix_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
      prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
    }

    /* Add materialization cost */
    prefix_cost += mat_info->materialization_cost.total_cost() +
                   prefix_rec_count * mat_info->scan_cost.total_cost();
    prefix_rec_count *= mat_info->rows;
    
    uint i;
    table_map rem_tables= remaining_tables;
    for (i= idx; i != (first_tab + mat_info->tables - 1); i--)
      rem_tables |= join->positions[i].table->table->map;

    POSITION curpos, dummy;
    /* Need to re-run best-access-path as we prefix_rec_count has changed */
3042
    bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
3043 3044
    for (i= first_tab + mat_info->tables; i <= idx; i++)
    {
3045 3046
      best_access_path(join, join->positions[i].table, rem_tables, i,
                       disable_jbuf, prefix_rec_count, &curpos, &dummy);
3047 3048 3049 3050
      prefix_rec_count *= curpos.records_read;
      prefix_cost += curpos.read_time;
    }

3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125
    *strategy= SJ_OPT_MATERIALIZE_SCAN;
    *read_time=    prefix_cost;
    *record_count= prefix_rec_count;
    *handled_fanout= mat_nest->sj_inner_tables;
    return TRUE;
  }
  return FALSE;
}


void LooseScan_picker::set_from_prev(struct st_position *prev)
{
  if (prev->loosescan_picker.is_used)
    set_empty();
  else
  {
    first_loosescan_table= prev->loosescan_picker.first_loosescan_table;
    loosescan_need_tables= prev->loosescan_picker.loosescan_need_tables;
  }
  is_used= FALSE;
}


bool LooseScan_picker::check_qep(JOIN *join,
                                 uint idx,
                                 table_map remaining_tables, 
                                 const JOIN_TAB *new_join_tab,
                                 double *record_count, 
                                 double *read_time,
                                 table_map *handled_fanout,
                                 sj_strategy_enum *strategy,
                                 struct st_position *loose_scan_pos)
{
  POSITION *first= join->positions + first_loosescan_table; 
  /* 
    LooseScan strategy can't handle interleaving between tables from the 
    semi-join that LooseScan is handling and any other tables.

    If we were considering LooseScan for the join prefix (1)
       and the table we're adding creates an interleaving (2)
    then 
       stop considering loose scan
  */
  if ((first_loosescan_table != MAX_TABLES) &&   // (1)
      (first->table->emb_sj_nest->sj_inner_tables & remaining_tables) && //(2)
      new_join_tab->emb_sj_nest != first->table->emb_sj_nest) //(2)
  {
    first_loosescan_table= MAX_TABLES;
  }

  /*
    If we got an option to use LooseScan for the current table, start
    considering using LooseScan strategy
  */
  if (loose_scan_pos->read_time != DBL_MAX && !join->outer_join)
  {
    first_loosescan_table= idx;
    loosescan_need_tables=
      new_join_tab->emb_sj_nest->sj_inner_tables | 
      new_join_tab->emb_sj_nest->nested_join->sj_depends_on |
      new_join_tab->emb_sj_nest->nested_join->sj_corr_tables;
  }
  
  if ((first_loosescan_table != MAX_TABLES) && 
      !(remaining_tables & loosescan_need_tables) &&
      (new_join_tab->table->map & loosescan_need_tables))
  {
    /* 
      Ok we have LooseScan plan and also have all LooseScan sj-nest's
      inner tables and outer correlated tables into the prefix.
    */

    first= join->positions + first_loosescan_table; 
    uint n_tables= my_count_bits(first->table->emb_sj_nest->sj_inner_tables);
    /* Got a complete LooseScan range. Calculate its cost */
3126
    /*
3127 3128 3129
      The same problem as with FirstMatch - we need to save POSITIONs
      somewhere but reserving space for all cases would require too
      much space. We will re-calculate POSITION structures later on. 
3130
    */
3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151
    bool disable_jbuf= (join->thd->variables.join_cache_level == 0);
    optimize_wo_join_buffering(join, first_loosescan_table, idx,
                               remaining_tables, 
                               TRUE,  //first_alt
                               disable_jbuf ? join->table_count :
                                 first_loosescan_table + n_tables,
                               record_count,
                               read_time);
    /*
      We don't yet have any other strategies that could handle this
      semi-join nest (the other options are Duplicate Elimination or
      Materialization, which need at least the same set of tables in 
      the join prefix to be considered) so unconditionally pick the 
      LooseScan.
    */
    *strategy= SJ_OPT_LOOSE_SCAN;
    *handled_fanout= first->table->emb_sj_nest->sj_inner_tables;
    return TRUE;
  }
  return FALSE;
}
3152

3153 3154 3155 3156 3157 3158 3159 3160 3161
void Firstmatch_picker::set_from_prev(struct st_position *prev)
{
  if (prev->firstmatch_picker.is_used)
    invalidate_firstmatch_prefix();
  else
  {
    first_firstmatch_table= prev->firstmatch_picker.first_firstmatch_table;
    first_firstmatch_rtbl=  prev->firstmatch_picker.first_firstmatch_rtbl;
    firstmatch_need_tables= prev->firstmatch_picker.firstmatch_need_tables;
3162
  }
3163 3164
  is_used= FALSE;
}
3165

3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178
bool Firstmatch_picker::check_qep(JOIN *join,
                                  uint idx,
                                  table_map remaining_tables, 
                                  const JOIN_TAB *new_join_tab,
                                  double *record_count,
                                  double *read_time,
                                  table_map *handled_fanout,
                                  sj_strategy_enum *strategy,
                                  POSITION *loose_scan_pos)
{
  if (new_join_tab->emb_sj_nest &&
      optimizer_flag(join->thd, OPTIMIZER_SWITCH_FIRSTMATCH) &&
      !join->outer_join)
3179
  {
3180 3181 3182 3183 3184 3185
    const table_map outer_corr_tables=
      new_join_tab->emb_sj_nest->nested_join->sj_corr_tables |
      new_join_tab->emb_sj_nest->nested_join->sj_depends_on;
    const table_map sj_inner_tables=
      new_join_tab->emb_sj_nest->sj_inner_tables & ~join->const_table_map;

3186
    /* 
3187 3188 3189 3190 3191 3192 3193 3194 3195
      Enter condition:
       1. The next join tab belongs to semi-join nest
          (verified for the encompassing code block above).
       2. We're not in a duplicate producer range yet
       3. All outer tables that
           - the subquery is correlated with, or
           - referred to from the outer_expr 
          are in the join prefix
       4. All inner tables are still part of remaining_tables.
3196
    */
3197 3198 3199 3200
    if (!join->cur_sj_inner_tables &&              // (2)
        !(remaining_tables & outer_corr_tables) && // (3)
        (sj_inner_tables ==                        // (4)
         ((remaining_tables | new_join_tab->table->map) & sj_inner_tables)))
3201
    {
3202 3203 3204 3205
      /* Start tracking potential FirstMatch range */
      first_firstmatch_table= idx;
      firstmatch_need_tables= sj_inner_tables;
      first_firstmatch_rtbl= remaining_tables;
3206
    }
3207

3208
    if (in_firstmatch_prefix())
3209
    {
3210
      if (outer_corr_tables & first_firstmatch_rtbl)
3211
      {
3212 3213 3214 3215 3216
        /*
          Trying to add an sj-inner table whose sj-nest has an outer correlated 
          table that was not in the prefix. This means FirstMatch can't be used.
        */
        invalidate_firstmatch_prefix();
3217 3218 3219
      }
      else
      {
3220 3221
        /* Record that we need all of this semi-join's inner tables, too */
        firstmatch_need_tables|= sj_inner_tables;
3222
      }
3223 3224 3225
    
      if (in_firstmatch_prefix() && 
          !(firstmatch_need_tables & remaining_tables))
3226
      {
3227
        /*
3228
          Got a complete FirstMatch range. Calculate correct costs and fanout
3229
        */
3230 3231 3232

        if (idx == first_firstmatch_table && 
            optimizer_flag(join->thd, OPTIMIZER_SWITCH_SEMIJOIN_WITH_CACHE))
3233
        {
3234 3235 3236 3237 3238 3239
          /* 
            An important special case: only one inner table, and @@optimizer_switch
            allows join buffering.
             - read_time is the same (i.e. FirstMatch doesn't add any cost
             - remove fanout added by the last table
          */
Igor Babaev's avatar
Igor Babaev committed
3240 3241
          if (*record_count)
            *record_count /= join->positions[idx].records_read;
3242 3243 3244
        }
        else
        {
3245 3246 3247 3248
          optimize_wo_join_buffering(join, first_firstmatch_table, idx,
                                     remaining_tables, FALSE, idx,
                                     record_count, 
                                     read_time);
3249
        }
3250 3251 3252 3253 3254 3255 3256 3257 3258 3259
        /*
          We ought to save the alternate POSITIONs produced by
          optimize_wo_join_buffering but the problem is that providing save
          space uses too much space. Instead, we will re-calculate the
          alternate POSITIONs after we've picked the best QEP.
        */
        *handled_fanout= firstmatch_need_tables;
        /* *record_count and *read_time were set by the above call */
        *strategy= SJ_OPT_FIRST_MATCH;
        return TRUE;
3260
      }
3261 3262
    }
  }
3263 3264
  else
    invalidate_firstmatch_prefix();
3265 3266
  return FALSE;
}
3267 3268


3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279
void Duplicate_weedout_picker::set_from_prev(POSITION *prev)
{
  if (prev->dups_weedout_picker.is_used)
    set_empty();
  else
  {
    dupsweedout_tables=      prev->dups_weedout_picker.dupsweedout_tables;
    first_dupsweedout_table= prev->dups_weedout_picker.first_dupsweedout_table;
  }
  is_used= FALSE;
}
3280 3281


3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326
bool Duplicate_weedout_picker::check_qep(JOIN *join,
                                         uint idx,
                                         table_map remaining_tables, 
                                         const JOIN_TAB *new_join_tab,
                                         double *record_count,
                                         double *read_time,
                                         table_map *handled_fanout,
                                         sj_strategy_enum *strategy,
                                         POSITION *loose_scan_pos
                                         )
{
  TABLE_LIST *nest;
  if ((nest= new_join_tab->emb_sj_nest))
  {
    if (!dupsweedout_tables)
      first_dupsweedout_table= idx;

    dupsweedout_tables |= nest->sj_inner_tables |
                          nest->nested_join->sj_depends_on |
                          nest->nested_join->sj_corr_tables;
  }
  
  if (dupsweedout_tables)
  {
    /* we're in the process of constructing a DuplicateWeedout range */
    TABLE_LIST *emb= new_join_tab->table->pos_in_table_list->embedding;
    /* and we've entered an inner side of an outer join*/
    if (emb && emb->on_expr)
      dupsweedout_tables |= emb->nested_join->used_tables;
  }
  
  /* If this is the last table that we need for DuplicateWeedout range */
  if (dupsweedout_tables && !(remaining_tables & ~new_join_tab->table->map &
                              dupsweedout_tables))
  {
    /*
      Ok, reached a state where we could put a dups weedout point.
      Walk back and calculate
        - the join cost (this is needed as the accumulated cost may assume 
          some other duplicate elimination method)
        - extra fanout that will be removed by duplicate elimination
        - duplicate elimination cost
      There are two cases:
        1. We have other strategy/ies to remove all of the duplicates.
        2. We don't.
3327
      
3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350
      We need to calculate the cost in case #2 also because we need to make
      choice between this join order and others.
    */
    uint first_tab= first_dupsweedout_table;
    double dups_cost;
    double prefix_rec_count;
    double sj_inner_fanout= 1.0;
    double sj_outer_fanout= 1.0;
    uint temptable_rec_size;
    if (first_tab == join->const_tables)
    {
      prefix_rec_count= 1.0;
      temptable_rec_size= 0;
      dups_cost= 0.0;
    }
    else
    {
      dups_cost= join->positions[first_tab - 1].prefix_cost.total_cost();
      prefix_rec_count= join->positions[first_tab - 1].prefix_record_count;
      temptable_rec_size= 8; /* This is not true but we'll make it so */
    }
    
    table_map dups_removed_fanout= 0;
3351
    double current_fanout= prefix_rec_count;
3352 3353 3354
    for (uint j= first_dupsweedout_table; j <= idx; j++)
    {
      POSITION *p= join->positions + j;
3355 3356
      current_fanout *= p->records_read;
      dups_cost += p->read_time + current_fanout / TIME_FOR_COMPARE;
3357
      if (p->table->emb_sj_nest)
3358
      {
3359 3360 3361 3362
        sj_inner_fanout *= p->records_read;
        dups_removed_fanout |= p->table->table->map;
      }
      else
3363
      {
3364 3365
        sj_outer_fanout *= p->records_read;
        temptable_rec_size += p->table->table->file->ref_length;
3366 3367
      }
    }
3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394

    /*
      Add the cost of temptable use. The table will have sj_outer_fanout
      records, and we will make 
      - sj_outer_fanout table writes
      - sj_inner_fanout*sj_outer_fanout  lookups.

    */
    double one_lookup_cost= get_tmp_table_lookup_cost(join->thd,
                                                      sj_outer_fanout,
                                                      temptable_rec_size);
    double one_write_cost= get_tmp_table_write_cost(join->thd,
                                                    sj_outer_fanout,
                                                    temptable_rec_size);

    double write_cost= join->positions[first_tab].prefix_record_count* 
                       sj_outer_fanout * one_write_cost;
    double full_lookup_cost= join->positions[first_tab].prefix_record_count* 
                             sj_outer_fanout* sj_inner_fanout * 
                             one_lookup_cost;
    dups_cost += write_cost + full_lookup_cost;
    
    *read_time= dups_cost;
    *record_count= prefix_rec_count * sj_outer_fanout;
    *handled_fanout= dups_removed_fanout;
    *strategy= SJ_OPT_DUPS_WEEDOUT;
    return TRUE;
3395
  }
3396
  return FALSE;
3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408
}


/*
  Remove the last join tab from from join->cur_sj_inner_tables bitmap
  we assume remaining_tables doesnt contain @tab.
*/

void restore_prev_sj_state(const table_map remaining_tables, 
                                  const JOIN_TAB *tab, uint idx)
{
  TABLE_LIST *emb_sj_nest;
Igor Babaev's avatar
Igor Babaev committed
3409 3410 3411 3412 3413 3414 3415

  if (tab->emb_sj_nest)
  {
    table_map subq_tables= tab->emb_sj_nest->sj_inner_tables;
    tab->join->sjm_lookup_tables &= ~subq_tables;
  }

3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447
  if ((emb_sj_nest= tab->emb_sj_nest))
  {
    /* If we're removing the last SJ-inner table, remove the sj-nest */
    if ((remaining_tables & emb_sj_nest->sj_inner_tables) == 
        (emb_sj_nest->sj_inner_tables & ~tab->table->map))
    {
      tab->join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables;
    }
  }
}


/*
  Given a semi-join nest, find out which of the IN-equalities are bound

  SYNOPSIS
    get_bound_sj_equalities()
      sj_nest           Semi-join nest
      remaining_tables  Tables that are not yet bound

  DESCRIPTION
    Given a semi-join nest, find out which of the IN-equalities have their
    left part expression bound (i.e. the said expression doesn't refer to
    any of remaining_tables and can be evaluated).

  RETURN
    Bitmap of bound IN-equalities.
*/

ulonglong get_bound_sj_equalities(TABLE_LIST *sj_nest, 
                                  table_map remaining_tables)
{
3448 3449
  List_iterator<Item_ptr> li(sj_nest->nested_join->sj_outer_expr_list);
  Item **item;
3450 3451 3452 3453 3454 3455 3456 3457 3458 3459
  uint i= 0;
  ulonglong res= 0;
  while ((item= li++))
  {
    /*
      Q: should this take into account equality propagation and how?
      A: If e->outer_side is an Item_field, walk over the equality
         class and see if there is an element that is bound?
      (this is an optional feature)
    */
3460
    if (!(item[0]->used_tables() & remaining_tables))
3461 3462 3463
    {
      res |= 1ULL << i;
    }
3464
    i++;
3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510
  }
  return res;
}


/*
  Check if the last tables of the partial join order allow to use
  sj-materialization strategy for them

  SYNOPSIS
    at_sjmat_pos()
      join              
      remaining_tables
      tab                the last table's join tab
      idx                last table's index
      loose_scan    OUT  TRUE <=> use LooseScan

  RETURN
    TRUE   Yes, can apply sj-materialization
    FALSE  No, some of the requirements are not met
*/

static SJ_MATERIALIZATION_INFO *
at_sjmat_pos(const JOIN *join, table_map remaining_tables, const JOIN_TAB *tab,
             uint idx, bool *loose_scan)
{
  /*
   Check if 
    1. We're in a semi-join nest that can be run with SJ-materialization
    2. All the tables correlated through the IN subquery are in the prefix
  */
  TABLE_LIST *emb_sj_nest= tab->emb_sj_nest;
  table_map suffix= remaining_tables & ~tab->table->map;
  if (emb_sj_nest && emb_sj_nest->sj_mat_info &&
      !(suffix & emb_sj_nest->sj_inner_tables))
  {
    /* 
      Walk back and check if all immediately preceding tables are from
      this semi-join.
    */
    uint n_tables= my_count_bits(tab->emb_sj_nest->sj_inner_tables);
    for (uint i= 1; i < n_tables ; i++)
    {
      if (join->positions[idx - i].table->emb_sj_nest != tab->emb_sj_nest)
        return NULL;
    }
3511 3512 3513
    *loose_scan= MY_TEST(remaining_tables & ~tab->table->map &
                                (emb_sj_nest->sj_inner_tables |
                                 emb_sj_nest->nested_join->sj_depends_on));
3514 3515 3516 3517 3518 3519 3520 3521 3522
    if (*loose_scan && !emb_sj_nest->sj_subq_pred->sjm_scan_allowed)
      return NULL;
    else
      return emb_sj_nest->sj_mat_info;
  }
  return NULL;
}


3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541
/*
  Re-calculate values of join->best_positions[start..end].prefix_record_count
*/

static void recalculate_prefix_record_count(JOIN *join, uint start, uint end)
{
  for (uint j= start; j < end ;j++)
  {
    double prefix_count;
    if (j == join->const_tables)
      prefix_count= 1.0;
    else
      prefix_count= join->best_positions[j-1].prefix_record_count *
                    join->best_positions[j-1].records_read;

    join->best_positions[j].prefix_record_count= prefix_count;
  }
}

3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586

/*
  Fix semi-join strategies for the picked join order

  SYNOPSIS
    fix_semijoin_strategies_for_picked_join_order()
      join  The join with the picked join order

  DESCRIPTION
    Fix semi-join strategies for the picked join order. This is a step that
    needs to be done right after we have fixed the join order. What we do
    here is switch join's semi-join strategy description from backward-based
    to forwards based.
    
    When join optimization is in progress, we re-consider semi-join
    strategies after we've added another table. Here's an illustration.
    Suppose the join optimization is underway:

    1) ot1  it1  it2 
                 sjX  -- looking at (ot1, it1, it2) join prefix, we decide
                         to use semi-join strategy sjX.

    2) ot1  it1  it2  ot2 
                 sjX  sjY -- Having added table ot2, we now may consider
                             another semi-join strategy and decide to use a 
                             different strategy sjY. Note that the record
                             of sjX has remained under it2. That is
                             necessary because we need to be able to get
                             back to (ot1, it1, it2) join prefix.
      what makes things even worse is that there are cases where the choice
      of sjY changes the way we should access it2. 

    3) [ot1  it1  it2  ot2  ot3]
                  sjX  sjY  -- This means that after join optimization is
                               finished, semi-join info should be read
                               right-to-left (while nearly all plan refinement
                               functions, EXPLAIN, etc proceed from left to 
                               right)

    This function does the needed reversal, making it possible to read the
    join and semi-join order from left to right.
*/    

void fix_semijoin_strategies_for_picked_join_order(JOIN *join)
{
3587
  uint table_count=join->table_count;
3588 3589 3590
  uint tablenr;
  table_map remaining_tables= 0;
  table_map handled_tabs= 0;
Igor Babaev's avatar
Igor Babaev committed
3591
  join->sjm_lookup_tables= 0;
Igor Babaev's avatar
Igor Babaev committed
3592
  join->sjm_scan_tables= 0;
3593 3594 3595 3596
  for (tablenr= table_count - 1 ; tablenr != join->const_tables - 1; tablenr--)
  {
    POSITION *pos= join->best_positions + tablenr;
    JOIN_TAB *s= pos->table;
3597
    uint UNINIT_VAR(first); // Set by every branch except SJ_OPT_NONE which doesn't use it
3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609

    if ((handled_tabs & s->table->map) || pos->sj_strategy == SJ_OPT_NONE)
    {
      remaining_tables |= s->table->map;
      continue;
    }
    
    if (pos->sj_strategy == SJ_OPT_MATERIALIZE)
    {
      SJ_MATERIALIZATION_INFO *sjm= s->emb_sj_nest->sj_mat_info;
      sjm->is_used= TRUE;
      sjm->is_sj_scan= FALSE;
3610
      memcpy((uchar*) (pos - sjm->tables + 1), (uchar*) sjm->positions,
3611
             sizeof(POSITION) * sjm->tables);
3612 3613
      recalculate_prefix_record_count(join, tablenr - sjm->tables + 1,
                                      tablenr);
3614 3615 3616
      first= tablenr - sjm->tables + 1;
      join->best_positions[first].n_sj_tables= sjm->tables;
      join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE;
3617 3618
      for (uint i= first; i < first+ sjm->tables; i++)
        join->sjm_lookup_tables |= join->best_positions[i].table->table->map;
3619 3620 3621
    }
    else if (pos->sj_strategy == SJ_OPT_MATERIALIZE_SCAN)
    {
3622
      POSITION *first_inner= join->best_positions + pos->sjmat_picker.sjm_scan_last_inner;
3623 3624 3625
      SJ_MATERIALIZATION_INFO *sjm= first_inner->table->emb_sj_nest->sj_mat_info;
      sjm->is_used= TRUE;
      sjm->is_sj_scan= TRUE;
3626
      first= pos->sjmat_picker.sjm_scan_last_inner - sjm->tables + 1;
3627 3628
      memcpy((uchar*) (join->best_positions + first),
             (uchar*) sjm->positions, sizeof(POSITION) * sjm->tables);
3629
      recalculate_prefix_record_count(join, first, first + sjm->tables);
3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650
      join->best_positions[first].sj_strategy= SJ_OPT_MATERIALIZE_SCAN;
      join->best_positions[first].n_sj_tables= sjm->tables;
      /* 
        Do what advance_sj_state did: re-run best_access_path for every table
        in the [last_inner_table + 1; pos..) range
      */
      double prefix_rec_count;
      /* Get the prefix record count */
      if (first == join->const_tables)
        prefix_rec_count= 1.0;
      else
        prefix_rec_count= join->best_positions[first-1].prefix_record_count;
      
      /* Add materialization record count*/
      prefix_rec_count *= sjm->rows;
      
      uint i;
      table_map rem_tables= remaining_tables;
      for (i= tablenr; i != (first + sjm->tables - 1); i--)
        rem_tables |= join->best_positions[i].table->table->map;

Igor Babaev's avatar
Igor Babaev committed
3651 3652 3653
      for (i= first; i < first+ sjm->tables; i++)
        join->sjm_scan_tables |= join->best_positions[i].table->table->map;

3654 3655 3656 3657
      POSITION dummy;
      join->cur_sj_inner_tables= 0;
      for (i= first + sjm->tables; i <= tablenr; i++)
      {
3658 3659
        best_access_path(join, join->best_positions[i].table, rem_tables, i, 
                         FALSE, prefix_rec_count,
3660
                         join->best_positions + i, &dummy);
3661 3662 3663 3664 3665 3666 3667
        prefix_rec_count *= join->best_positions[i].records_read;
        rem_tables &= ~join->best_positions[i].table->table->map;
      }
    }
 
    if (pos->sj_strategy == SJ_OPT_FIRST_MATCH)
    {
3668
      first= pos->firstmatch_picker.first_firstmatch_table;
3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700
      join->best_positions[first].sj_strategy= SJ_OPT_FIRST_MATCH;
      join->best_positions[first].n_sj_tables= tablenr - first + 1;
      POSITION dummy; // For loose scan paths
      double record_count= (first== join->const_tables)? 1.0: 
                           join->best_positions[tablenr - 1].prefix_record_count;
      
      table_map rem_tables= remaining_tables;
      uint idx;
      for (idx= first; idx <= tablenr; idx++)
      {
        rem_tables |= join->best_positions[idx].table->table->map;
      }
      /*
        Re-run best_access_path to produce best access methods that do not use
        join buffering
      */ 
      join->cur_sj_inner_tables= 0;
      for (idx= first; idx <= tablenr; idx++)
      {
        if (join->best_positions[idx].use_join_buffer)
        {
           best_access_path(join, join->best_positions[idx].table, 
                            rem_tables, idx, TRUE /* no jbuf */,
                            record_count, join->best_positions + idx, &dummy);
        }
        record_count *= join->best_positions[idx].records_read;
        rem_tables &= ~join->best_positions[idx].table->table->map;
      }
    }

    if (pos->sj_strategy == SJ_OPT_LOOSE_SCAN) 
    {
3701
      first= pos->loosescan_picker.first_loosescan_table;
3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724
      POSITION *first_pos= join->best_positions + first;
      POSITION loose_scan_pos; // For loose scan paths
      double record_count= (first== join->const_tables)? 1.0: 
                           join->best_positions[tablenr - 1].prefix_record_count;
      
      table_map rem_tables= remaining_tables;
      uint idx;
      for (idx= first; idx <= tablenr; idx++)
        rem_tables |= join->best_positions[idx].table->table->map;
      /*
        Re-run best_access_path to produce best access methods that do not use
        join buffering
      */ 
      join->cur_sj_inner_tables= 0;
      for (idx= first; idx <= tablenr; idx++)
      {
        if (join->best_positions[idx].use_join_buffer || (idx == first))
        {
           best_access_path(join, join->best_positions[idx].table,
                            rem_tables, idx, TRUE /* no jbuf */,
                            record_count, join->best_positions + idx,
                            &loose_scan_pos);
           if (idx==first)
3725
           {
3726
             join->best_positions[idx]= loose_scan_pos;
3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740
             /*
               If LooseScan is based on ref access (including the "degenerate"
               one with 0 key parts), we should use full index scan.

               Unfortunately, lots of code assumes that if tab->type==JT_ALL && 
               tab->quick!=NULL, then quick select should be used. The only
               simple way to fix this is to remove the quick select:
             */
             if (join->best_positions[idx].key)
             {
               delete join->best_positions[idx].table->quick;
               join->best_positions[idx].table->quick= NULL;
             }
           }
3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754
        }
        rem_tables &= ~join->best_positions[idx].table->table->map;
        record_count *= join->best_positions[idx].records_read;
      }
      first_pos->sj_strategy= SJ_OPT_LOOSE_SCAN;
      first_pos->n_sj_tables= my_count_bits(first_pos->table->emb_sj_nest->sj_inner_tables);
    }

    if (pos->sj_strategy == SJ_OPT_DUPS_WEEDOUT)
    {
      /* 
        Duplicate Weedout starting at pos->first_dupsweedout_table, ending at
        this table.
      */
3755
      first= pos->dups_weedout_picker.first_dupsweedout_table;
3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770
      join->best_positions[first].sj_strategy= SJ_OPT_DUPS_WEEDOUT;
      join->best_positions[first].n_sj_tables= tablenr - first + 1;
    }
    
    uint i_end= first + join->best_positions[first].n_sj_tables;
    for (uint i= first; i < i_end; i++)
    {
      if (i != first)
        join->best_positions[i].sj_strategy= SJ_OPT_NONE;
      handled_tabs |= join->best_positions[i].table->table->map;
    }

    if (tablenr != first)
      pos->sj_strategy= SJ_OPT_NONE;
    remaining_tables |= s->table->map;
3771
    join->join_tab[first].sj_strategy= join->best_positions[first].sj_strategy;
Sergey Petrunya's avatar
Sergey Petrunya committed
3772
    join->join_tab[first].n_sj_tables= join->best_positions[first].n_sj_tables;
3773 3774 3775
  }
}

3776

3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797
/*
  Setup semi-join materialization strategy for one semi-join nest
  
  SYNOPSIS

  setup_sj_materialization()
    tab  The first tab in the semi-join

  DESCRIPTION
    Setup execution structures for one semi-join materialization nest:
    - Create the materialization temporary table
    - If we're going to do index lookups
        create TABLE_REF structure to make the lookus
    - else (if we're going to do a full scan of the temptable)
        create Copy_field structures to do copying.

  RETURN
    FALSE  Ok
    TRUE   Error
*/

3798
bool setup_sj_materialization_part1(JOIN_TAB *sjm_tab)
3799
{
3800
  JOIN_TAB *tab= sjm_tab->bush_children->start;
3801
  TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
3802 3803 3804 3805
  SJ_MATERIALIZATION_INFO *sjm;
  THD *thd;

  DBUG_ENTER("setup_sj_materialization");
3806 3807 3808 3809 3810
  
  /* Walk out of outer join nests until we reach the semi-join nest we're in */
  while (!emb_sj_nest->sj_mat_info)
    emb_sj_nest= emb_sj_nest->embedding;

3811 3812
  sjm= emb_sj_nest->sj_mat_info;
  thd= tab->join->thd;
3813
  /* First the calls come to the materialization function */
3814

3815
  DBUG_ASSERT(sjm->is_used);
3816 3817 3818 3819
  /* 
    Set up the table to write to, do as select_union::create_result_table does
  */
  sjm->sjm_table_param.init();
3820
  sjm->sjm_table_param.bit_fields_as_long= TRUE;
3821
  SELECT_LEX *subq_select= emb_sj_nest->sj_subq_pred->unit->first_select();
3822
  const LEX_CSTRING sj_materialize_name= { STRING_WITH_LEN("sj-materialize") };
3823 3824 3825 3826 3827 3828 3829 3830 3831
  List_iterator<Item> it(subq_select->item_list);
  Item *item;
  while((item= it++))
  {
    /*
      This semi-join replaced the subquery (subq_select) and so on
      re-executing it will not be prepared. To use the Items from its
      select list we have to prepare (fix_fields) them
    */
3832
    if (item->fix_fields_if_needed(thd, it.ref()))
3833 3834
      DBUG_RETURN(TRUE);
    item= *(it.ref()); // it can be changed by fix_fields
3835
    DBUG_ASSERT(!item->name.length || item->name.length == strlen(item->name.str));
3836 3837
    sjm->sjm_table_cols.push_back(item, thd->mem_root);
  }
3838 3839

  sjm->sjm_table_param.field_count= subq_select->item_list.elements;
Igor Babaev's avatar
Igor Babaev committed
3840
  sjm->sjm_table_param.force_not_null_cols= TRUE;
3841 3842 3843 3844 3845

  if (!(sjm->table= create_tmp_table(thd, &sjm->sjm_table_param, 
                                     sjm->sjm_table_cols, (ORDER*) 0, 
                                     TRUE /* distinct */, 
                                     1, /*save_sum_fields*/
3846
                                     thd->variables.option_bits | TMP_TABLE_ALL_COLUMNS, 
3847
                                     HA_POS_ERROR /*rows_limit */, 
3848
                                     &sj_materialize_name)))
3849
    DBUG_RETURN(TRUE); /* purecov: inspected */
Igor Babaev's avatar
Igor Babaev committed
3850
  sjm->table->map=  emb_sj_nest->nested_join->used_tables;
3851 3852
  sjm->table->file->extra(HA_EXTRA_WRITE_CACHE);
  sjm->table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
Sergey Petrunya's avatar
Sergey Petrunya committed
3853

3854 3855
  tab->join->sj_tmp_tables.push_back(sjm->table, thd->mem_root);
  tab->join->sjm_info_list.push_back(sjm, thd->mem_root);
3856 3857
  
  sjm->materialized= FALSE;
3858
  sjm_tab->table= sjm->table;
Sergey Petrunya's avatar
Sergey Petrunya committed
3859
  sjm->table->pos_in_table_list= emb_sj_nest;
3860 3861 3862 3863
 
  DBUG_RETURN(FALSE);
}

3864 3865 3866 3867 3868
/**
   @retval
   FALSE ok
   TRUE  error
*/
3869 3870 3871 3872 3873 3874

bool setup_sj_materialization_part2(JOIN_TAB *sjm_tab)
{
  DBUG_ENTER("setup_sj_materialization_part2");
  JOIN_TAB *tab= sjm_tab->bush_children->start;
  TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding;
3875 3876 3877
  /* Walk out of outer join nests until we reach the semi-join nest we're in */
  while (!emb_sj_nest->sj_mat_info)
    emb_sj_nest= emb_sj_nest->embedding;
3878 3879 3880
  SJ_MATERIALIZATION_INFO *sjm= emb_sj_nest->sj_mat_info;
  THD *thd= tab->join->thd;
  uint i;
3881

3882 3883 3884 3885 3886
  if (!sjm->is_sj_scan)
  {
    KEY           *tmp_key; /* The only index on the temporary table. */
    uint          tmp_key_parts; /* Number of keyparts in tmp_key. */
    tmp_key= sjm->table->key_info;
3887
    tmp_key_parts= tmp_key->user_defined_key_parts;
3888 3889 3890 3891 3892 3893
    
    /*
      Create/initialize everything we will need to index lookups into the
      temptable.
    */
    TABLE_REF *tab_ref;
3894
    tab_ref= &sjm_tab->ref;
3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917
    tab_ref->key= 0; /* The only temp table index. */
    tab_ref->key_length= tmp_key->key_length;
    if (!(tab_ref->key_buff=
          (uchar*) thd->calloc(ALIGN_SIZE(tmp_key->key_length) * 2)) ||
        !(tab_ref->key_copy=
          (store_key**) thd->alloc((sizeof(store_key*) *
                                    (tmp_key_parts + 1)))) ||
        !(tab_ref->items=
          (Item**) thd->alloc(sizeof(Item*) * tmp_key_parts)))
      DBUG_RETURN(TRUE); /* purecov: inspected */

    tab_ref->key_buff2=tab_ref->key_buff+ALIGN_SIZE(tmp_key->key_length);
    tab_ref->key_err=1;
    tab_ref->null_rejecting= 1;
    tab_ref->disable_cache= FALSE;

    KEY_PART_INFO *cur_key_part= tmp_key->key_part;
    store_key **ref_key= tab_ref->key_copy;
    uchar *cur_ref_buff= tab_ref->key_buff;
    
    for (i= 0; i < tmp_key_parts; i++, cur_key_part++, ref_key++)
    {
      tab_ref->items[i]= emb_sj_nest->sj_subq_pred->left_expr->element_index(i);
3918
      int null_count= MY_TEST(cur_key_part->field->real_maybe_null());
3919 3920 3921 3922
      *ref_key= new store_key_item(thd, cur_key_part->field,
                                   /* TODO:
                                      the NULL byte is taken into account in
                                      cur_key_part->store_length, so instead of
3923
                                      cur_ref_buff + MY_TEST(maybe_null), we could
3924 3925 3926
                                      use that information instead.
                                   */
                                   cur_ref_buff + null_count,
3927
                                   null_count ? cur_ref_buff : 0,
unknown's avatar
unknown committed
3928 3929
                                   cur_key_part->length, tab_ref->items[i],
                                   FALSE);
3930 3931
      if (!*ref_key)
        DBUG_RETURN(TRUE);
3932 3933 3934
      cur_ref_buff+= cur_key_part->store_length;
    }
    *ref_key= NULL; /* End marker. */
Sergey Petrunya's avatar
Sergey Petrunya committed
3935 3936 3937 3938 3939 3940 3941 3942 3943 3944
      
    /*
      We don't ever have guarded conditions for SJM tables, but code at SQL
      layer depends on cond_guards array being alloced.
    */
    if (!(tab_ref->cond_guards= (bool**) thd->calloc(sizeof(uint*)*tmp_key_parts)))
    {
      DBUG_RETURN(TRUE);
    }

3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956
    tab_ref->key_err= 1;
    tab_ref->key_parts= tmp_key_parts;
    sjm->tab_ref= tab_ref;

    /*
      Remove the injected semi-join IN-equalities from join_tab conds. This
      needs to be done because the IN-equalities refer to columns of
      sj-inner tables which are not available after the materialization
      has been finished.
    */
    for (i= 0; i < sjm->tables; i++)
    {
3957 3958 3959
      if (remove_sj_conds(thd, &tab[i].select_cond) ||
          (tab[i].select && remove_sj_conds(thd, &tab[i].select->cond)))
        DBUG_RETURN(TRUE);
3960 3961 3962 3963
    }
    if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm,
                                                      emb_sj_nest->sj_subq_pred)))
      DBUG_RETURN(TRUE); /* purecov: inspected */
3964
    sjm_tab->type= JT_EQ_REF;
Sergey Petrunya's avatar
Sergey Petrunya committed
3965
    sjm_tab->select_cond= sjm->in_equality;
3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995
  }
  else
  {
    /*
      We'll be doing full scan of the temptable.  
      Setup copying of temptable columns back to the record buffers
      for their source tables. We need this because IN-equalities
      refer to the original tables.

      EXAMPLE

      Consider the query:
        SELECT * FROM ot WHERE ot.col1 IN (SELECT it.col2 FROM it)
      
      Suppose it's executed with SJ-Materialization-scan. We choose to do scan
      if we can't do the lookup, i.e. the join order is (it, ot). The plan
      would look as follows:

        table    access method      condition
         it      materialize+scan    -
         ot      (whatever)          ot1.col1=it.col2 (C2)

      The condition C2 refers to current row of table it. The problem is
      that by the time we evaluate C2, we would have finished with scanning
      it itself and will be scanning the temptable. 

      At the moment, our solution is to copy back: when we get the next
      temptable record, we copy its columns to their corresponding columns
      in the record buffers for the source tables. 
    */
3996 3997 3998
    if (!(sjm->copy_field= new Copy_field[sjm->sjm_table_cols.elements]))
      DBUG_RETURN(TRUE);

3999
    //it.rewind();
4000
    Ref_ptr_array p_items= emb_sj_nest->sj_subq_pred->unit->first_select()->ref_pointer_array;
4001 4002 4003 4004
    for (uint i=0; i < sjm->sjm_table_cols.elements; i++)
    {
      bool dummy;
      Item_equal *item_eq;
4005
      //Item *item= (it++)->real_item();
4006
      Item *item= p_items[i]->real_item();
4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021
      DBUG_ASSERT(item->type() == Item::FIELD_ITEM);
      Field *copy_to= ((Item_field*)item)->field;
      /*
        Tricks with Item_equal are due to the following: suppose we have a
        query:
        
        ... WHERE cond(ot.col) AND ot.col IN (SELECT it2.col FROM it1,it2
                                               WHERE it1.col= it2.col)
         then equality propagation will create an 
         
           Item_equal(it1.col, it2.col, ot.col) 
         
         then substitute_for_best_equal_field() will change the conditions
         according to the join order:

4022 4023 4024 4025 4026
         table | attached condition
         ------+--------------------
          it1  |
          it2  | it1.col=it2.col
          ot   | cond(it1.col)
4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039

         although we've originally had "SELECT it2.col", conditions attached 
         to subsequent outer tables will refer to it1.col, so SJM-Scan will
         need to unpack data to there. 
         That is, if an element from subquery's select list participates in 
         equality propagation, then we need to unpack it to the first
         element equality propagation member that refers to table that is
         within the subquery.
      */
      item_eq= find_item_equal(tab->join->cond_equal, copy_to, &dummy);

      if (item_eq)
      {
4040
        List_iterator<Item> it(item_eq->equal_items);
4041 4042 4043
        /* We're interested in field items only */
        if (item_eq->get_const())
          it++;
4044
        Item *item;
4045 4046 4047 4048
        while ((item= it++))
        {
          if (!(item->used_tables() & ~emb_sj_nest->sj_inner_tables))
          {
4049
            DBUG_ASSERT(item->real_item()->type() == Item::FIELD_ITEM);
4050
            copy_to= ((Item_field *) (item->real_item()))->field;
4051 4052 4053 4054 4055 4056 4057 4058
            break;
          }
        }
      }
      sjm->copy_field[i].set(copy_to, sjm->table->field[i], FALSE);
      /* The write_set for source tables must be set up to allow the copying */
      bitmap_set_bit(copy_to->table->write_set, copy_to->field_index);
    }
4059 4060 4061 4062 4063 4064 4065
    sjm_tab->type= JT_ALL;

    /* Initialize full scan */
    sjm_tab->read_first_record= join_read_record_no_init;
    sjm_tab->read_record.copy_field= sjm->copy_field;
    sjm_tab->read_record.copy_field_end= sjm->copy_field +
                                         sjm->sjm_table_cols.elements;
4066
    sjm_tab->read_record.read_record_func= rr_sequential_and_unpack;
4067 4068
  }

4069 4070
  sjm_tab->bush_children->end[-1].next_select= end_sj_materialize;

4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103
  DBUG_RETURN(FALSE);
}



/*
  Create subquery IN-equalities assuming use of materialization strategy
  
  SYNOPSIS
    create_subq_in_equalities()
      thd        Thread handle
      sjm        Semi-join materialization structure
      subq_pred  The subquery predicate

  DESCRIPTION
    Create subquery IN-equality predicates. That is, for a subquery
    
      (oe1, oe2, ...) IN (SELECT ie1, ie2, ... FROM ...)
    
    create "oe1=ie1 AND ie1=ie2 AND ..." expression, such that ie1, ie2, ..
    refer to the columns of the table that's used to materialize the
    subquery.

  RETURN 
    Created condition
*/

static Item *create_subq_in_equalities(THD *thd, SJ_MATERIALIZATION_INFO *sjm, 
                                Item_in_subselect *subq_pred)
{
  Item *res= NULL;
  if (subq_pred->left_expr->cols() == 1)
  {
Monty's avatar
Monty committed
4104 4105
    if (!(res= new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr,
                                new (thd->mem_root) Item_field(thd, sjm->table->field[0]))))
4106 4107 4108 4109 4110 4111 4112
      return NULL; /* purecov: inspected */
  }
  else
  {
    Item *conj;
    for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
    {
Monty's avatar
Monty committed
4113 4114
      if (!(conj= new (thd->mem_root) Item_func_eq(thd, subq_pred->left_expr->element_index(i),
                                   new (thd->mem_root) Item_field(thd, sjm->table->field[i]))) ||
4115
          !(res= and_items(thd, res, conj)))
4116 4117 4118 4119 4120 4121 4122 4123 4124
        return NULL; /* purecov: inspected */
    }
  }
  if (res->fix_fields(thd, &res))
    return NULL; /* purecov: inspected */
  return res;
}


4125 4126 4127 4128 4129
/**
  @retval
  0 ok
  1 error
*/
4130

4131
static bool remove_sj_conds(THD *thd, Item **tree)
4132 4133 4134 4135 4136 4137
{
  if (*tree)
  {
    if (is_cond_sj_in_equality(*tree))
    {
      *tree= NULL;
4138
      return 0;
4139 4140 4141 4142 4143 4144 4145 4146
    }
    else if ((*tree)->type() == Item::COND_ITEM) 
    {
      Item *item;
      List_iterator<Item> li(*(((Item_cond*)*tree)->argument_list()));
      while ((item= li++))
      {
        if (is_cond_sj_in_equality(item))
4147 4148 4149 4150 4151 4152
        {
          Item_int *tmp= new (thd->mem_root) Item_int(thd, 1);
          if (!tmp)
            return 1;
          li.replace(tmp);
        }
4153 4154 4155
      }
    }
  }
4156
  return 0;
4157 4158
}

4159

4160 4161 4162 4163 4164 4165 4166
/* Check if given Item was injected by semi-join equality */
static bool is_cond_sj_in_equality(Item *item)
{
  if (item->type() == Item::FUNC_ITEM &&
      ((Item_func*)item)->functype()== Item_func::EQ_FUNC)
  {
    Item_func_eq *item_eq= (Item_func_eq*)item;
4167
    return MY_TEST(item_eq->in_equality_no != UINT_MAX);
4168 4169 4170 4171 4172 4173 4174 4175 4176 4177
  }
  return FALSE;
}


/*
  Create a temporary table to weed out duplicate rowid combinations

  SYNOPSIS

Sergey Petrunya's avatar
Sergey Petrunya committed
4178
    create_sj_weedout_tmp_table()
4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203
      thd                    Thread handle

  DESCRIPTION
    Create a temporary table to weed out duplicate rowid combinations. The
    table has a single column that is a concatenation of all rowids in the
    combination. 

    Depending on the needed length, there are two cases:

    1. When the length of the column < max_key_length:

      CREATE TABLE tmp (col VARBINARY(n) NOT NULL, UNIQUE KEY(col));

    2. Otherwise (not a valid SQL syntax but internally supported):

      CREATE TABLE tmp (col VARBINARY NOT NULL, UNIQUE CONSTRAINT(col));

    The code in this function was produced by extraction of relevant parts
    from create_tmp_table().

  RETURN
    created table
    NULL on error
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
4204 4205
bool
SJ_TMP_TABLE::create_sj_weedout_tmp_table(THD *thd)
4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220
{
  MEM_ROOT *mem_root_save, own_root;
  TABLE *table;
  TABLE_SHARE *share;
  uint  temp_pool_slot=MY_BIT_NONE;
  char	*tmpname,path[FN_REFLEN];
  Field **reg_field;
  KEY_PART_INFO *key_part_info;
  KEY *keyinfo;
  uchar *group_buff;
  uchar *bitmaps;
  uint *blob_field;
  bool using_unique_constraint=FALSE;
  bool use_packed_rows= FALSE;
  Field *field, *key_field;
4221
  uint null_pack_length, null_count;
4222 4223
  uchar *null_flags;
  uchar *pos;
Sergey Petrunya's avatar
Sergey Petrunya committed
4224 4225 4226 4227 4228
  DBUG_ENTER("create_sj_weedout_tmp_table");
  DBUG_ASSERT(!is_degenerate);

  tmp_table= NULL;
  uint uniq_tuple_length_arg= rowid_len + null_bytes;
4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241
  /*
    STEP 1: Get temporary table name
  */
  if (use_temp_pool && !(test_flags & TEST_KEEP_TMP_TABLES))
    temp_pool_slot = bitmap_lock_set_next(&temp_pool);

  if (temp_pool_slot != MY_BIT_NONE) // we got a slot
    sprintf(path, "%s_%lx_%i", tmp_file_prefix,
	    current_pid, temp_pool_slot);
  else
  {
    /* if we run out of slots or we are not using tempool */
    sprintf(path,"%s%lx_%lx_%x", tmp_file_prefix,current_pid,
4242
            (ulong) thd->thread_id, thd->tmp_table++);
4243 4244 4245 4246
  }
  fn_format(path, path, mysql_tmpdir, "", MY_REPLACE_EXT|MY_UNPACK_FILENAME);

  /* STEP 2: Figure if we'll be using a key or blob+constraint */
4247
  /* it always has my_charset_bin, so mbmaxlen==1 */
4248 4249 4250 4251
  if (uniq_tuple_length_arg >= CONVERT_IF_BIGGER_TO_BLOB)
    using_unique_constraint= TRUE;

  /* STEP 3: Allocate memory for temptable description */
4252 4253
  init_sql_alloc(&own_root, "SJ_TMP_TABLE",
                 TABLE_ALLOC_BLOCK_SIZE, 0, MYF(MY_THREAD_SPECIFIC));
4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265
  if (!multi_alloc_root(&own_root,
                        &table, sizeof(*table),
                        &share, sizeof(*share),
                        &reg_field, sizeof(Field*) * (1+1),
                        &blob_field, sizeof(uint)*2,
                        &keyinfo, sizeof(*keyinfo),
                        &key_part_info, sizeof(*key_part_info) * 2,
                        &start_recinfo,
                        sizeof(*recinfo)*(1*2+4),
                        &tmpname, (uint) strlen(path)+1,
                        &group_buff, (!using_unique_constraint ?
                                      uniq_tuple_length_arg : 0),
4266
                        &bitmaps, bitmap_buffer_size(1)*6,
4267 4268 4269 4270
                        NullS))
  {
    if (temp_pool_slot != MY_BIT_NONE)
      bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
Sergey Petrunya's avatar
Sergey Petrunya committed
4271
    DBUG_RETURN(TRUE);
4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284
  }
  strmov(tmpname,path);
  

  /* STEP 4: Create TABLE description */
  bzero((char*) table,sizeof(*table));
  bzero((char*) reg_field,sizeof(Field*)*2);

  table->mem_root= own_root;
  mem_root_save= thd->mem_root;
  thd->mem_root= &table->mem_root;

  table->field=reg_field;
4285 4286
  table->alias.set("weedout-tmp", sizeof("weedout-tmp")-1,
                   table_alias_charset);
4287
  table->reginfo.lock_type=TL_WRITE;	/* Will be updated */
4288
  table->db_stat=HA_OPEN_KEYFILE;
4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306
  table->map=1;
  table->temp_pool_slot = temp_pool_slot;
  table->copy_blobs= 1;
  table->in_use= thd;
  table->quick_keys.init();
  table->covering_keys.init();
  table->keys_in_use_for_query.init();

  table->s= share;
  init_tmp_table_share(thd, share, "", 0, tmpname, tmpname);
  share->blob_field= blob_field;
  share->table_charset= NULL;
  share->primary_key= MAX_KEY;               // Indicate no primary key
  share->keys_for_keyread.init();
  share->keys_in_use.init();

  /* Create the field */
  {
4307
    LEX_CSTRING field_name= {STRING_WITH_LEN("rowids") };
4308 4309 4310 4311
    /*
      For the sake of uniformity, always use Field_varstring (altough we could
      use Field_string for shorter keys)
    */
4312 4313
    field= new Field_varstring(uniq_tuple_length_arg, FALSE, &field_name,
                               share, &my_charset_bin);
4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347
    if (!field)
      DBUG_RETURN(0);
    field->table= table;
    field->key_start.init(0);
    field->part_of_key.init(0);
    field->part_of_sortkey.init(0);
    field->unireg_check= Field::NONE;
    field->flags= (NOT_NULL_FLAG | BINARY_FLAG | NO_DEFAULT_VALUE_FLAG);
    field->reset_fields();
    field->init(table);
    field->orig_table= NULL;
     
    field->field_index= 0;
    
    *(reg_field++)= field;
    *blob_field= 0;
    *reg_field= 0;

    share->fields= 1;
    share->blob_fields= 0;
  }

  uint reclength= field->pack_length();
  if (using_unique_constraint)
  { 
    share->db_plugin= ha_lock_engine(0, TMP_ENGINE_HTON);
    table->file= get_new_handler(share, &table->mem_root,
                                 share->db_type());
  }
  else
  {
    share->db_plugin= ha_lock_engine(0, heap_hton);
    table->file= get_new_handler(share, &table->mem_root,
                                 share->db_type());
4348
    DBUG_ASSERT(!table->file || uniq_tuple_length_arg <= table->file->max_key_length());
4349 4350 4351 4352
  }
  if (!table->file)
    goto err;

4353 4354 4355 4356 4357 4358
  if (table->file->set_ha_share_ref(&share->ha_share))
  {
    delete table->file;
    goto err;
  }

4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418 4419 4420
  null_count=1;
  
  null_pack_length= 1;
  reclength += null_pack_length;

  share->reclength= reclength;
  {
    uint alloc_length=ALIGN_SIZE(share->reclength + MI_UNIQUE_HASH_LENGTH+1);
    share->rec_buff_length= alloc_length;
    if (!(table->record[0]= (uchar*)
                            alloc_root(&table->mem_root, alloc_length*3)))
      goto err;
    table->record[1]= table->record[0]+alloc_length;
    share->default_values= table->record[1]+alloc_length;
  }
  setup_tmp_table_column_bitmaps(table, bitmaps);

  recinfo= start_recinfo;
  null_flags=(uchar*) table->record[0];
  pos=table->record[0]+ null_pack_length;
  if (null_pack_length)
  {
    bzero((uchar*) recinfo,sizeof(*recinfo));
    recinfo->type=FIELD_NORMAL;
    recinfo->length=null_pack_length;
    recinfo++;
    bfill(null_flags,null_pack_length,255);	// Set null fields

    table->null_flags= (uchar*) table->record[0];
    share->null_fields= null_count;
    share->null_bytes= null_pack_length;
  }
  null_count=1;

  {
    //Field *field= *reg_field;
    uint length;
    bzero((uchar*) recinfo,sizeof(*recinfo));
    field->move_field(pos,(uchar*) 0,0);

    field->reset();
    /*
      Test if there is a default field value. The test for ->ptr is to skip
      'offset' fields generated by initalize_tables
    */
    // Initialize the table field:
    bzero(field->ptr, field->pack_length());

    length=field->pack_length();
    pos+= length;

    /* Make entry for create table */
    recinfo->length=length;
    if (field->flags & BLOB_FLAG)
      recinfo->type= FIELD_BLOB;
    else if (use_packed_rows &&
             field->real_type() == MYSQL_TYPE_STRING &&
	     length >= MIN_STRING_LENGTH_TO_PACK_ROWS)
      recinfo->type=FIELD_SKIP_ENDSPACE;
    else
      recinfo->type=FIELD_NORMAL;

4421
    field->set_table_name(&table->alias);
4422 4423
  }

4424
  if (thd->variables.tmp_memory_table_size == ~ (ulonglong) 0)	// No limit
4425 4426 4427
    share->max_rows= ~(ha_rows) 0;
  else
    share->max_rows= (ha_rows) (((share->db_type() == heap_hton) ?
4428 4429 4430
                                 MY_MIN(thd->variables.tmp_memory_table_size,
                                        thd->variables.max_heap_table_size) :
                                 thd->variables.tmp_memory_table_size) /
4431 4432 4433 4434 4435 4436 4437 4438 4439
			         share->reclength);
  set_if_bigger(share->max_rows,1);		// For dummy start options


  //// keyinfo= param->keyinfo;
  if (TRUE)
  {
    DBUG_PRINT("info",("Creating group key in temporary table"));
    share->keys=1;
4440
    share->uniques= MY_TEST(using_unique_constraint);
4441 4442 4443
    table->key_info=keyinfo;
    keyinfo->key_part=key_part_info;
    keyinfo->flags=HA_NOSAME;
4444
    keyinfo->usable_key_parts= keyinfo->user_defined_key_parts= 1;
4445 4446 4447
    keyinfo->key_length=0;
    keyinfo->rec_per_key=0;
    keyinfo->algorithm= HA_KEY_ALG_UNDEF;
4448
    keyinfo->name= weedout_key;
4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459
    {
      key_part_info->null_bit=0;
      key_part_info->field=  field;
      key_part_info->offset= field->offset(table->record[0]);
      key_part_info->length= (uint16) field->key_length();
      key_part_info->type=   (uint8) field->key_type();
      key_part_info->key_type = FIELDFLAG_BINARY;
      if (!using_unique_constraint)
      {
	if (!(key_field= field->new_key_field(thd->mem_root, table,
                                              group_buff,
4460
                                              key_part_info->length,
4461 4462 4463 4464 4465 4466 4467 4468
                                              field->null_ptr,
                                              field->null_bit)))
	  goto err;
      }
      keyinfo->key_length+=  key_part_info->length;
    }
  }

4469
  if (unlikely(thd->is_fatal_error))            // If end of memory
4470 4471
    goto err;
  share->db_record_offset= 1;
4472 4473 4474 4475
  table->no_rows= 1;              		// We don't need the data

  // recinfo must point after last field
  recinfo++;
4476 4477
  if (share->db_type() == TMP_ENGINE_HTON)
  {
4478 4479
    if (unlikely(create_internal_tmp_table(table, keyinfo, start_recinfo,
                                           &recinfo, 0)))
4480 4481
      goto err;
  }
4482
  if (unlikely(open_tmp_table(table)))
4483 4484 4485
    goto err;

  thd->mem_root= mem_root_save;
Sergey Petrunya's avatar
Sergey Petrunya committed
4486 4487
  tmp_table= table;
  DBUG_RETURN(FALSE);
4488 4489 4490 4491 4492 4493

err:
  thd->mem_root= mem_root_save;
  free_tmp_table(thd,table);                    /* purecov: inspected */
  if (temp_pool_slot != MY_BIT_NONE)
    bitmap_lock_clear_bit(&temp_pool, temp_pool_slot);
Sergey Petrunya's avatar
Sergey Petrunya committed
4494
  DBUG_RETURN(TRUE);				/* purecov: inspected */
4495 4496 4497 4498 4499 4500 4501
}


/*
  SemiJoinDuplicateElimination: Reset the temporary table
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
4502
int SJ_TMP_TABLE::sj_weedout_delete_rows()
4503
{
Sergey Petrunya's avatar
Sergey Petrunya committed
4504 4505
  DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_delete_rows");
  if (tmp_table)
4506
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
4507
    int rc= tmp_table->file->ha_delete_all_rows();
4508 4509
    DBUG_RETURN(rc);
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
4510
  have_degenerate_row= FALSE;
4511 4512 4513
  DBUG_RETURN(0);
}

Sergey Petrunya's avatar
Sergey Petrunya committed
4514

4515 4516 4517 4518
/*
  SemiJoinDuplicateElimination: Weed out duplicate row combinations

  SYNPOSIS
Sergey Petrunya's avatar
Sergey Petrunya committed
4519
    sj_weedout_check_row()
4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532
      thd    Thread handle

  DESCRIPTION
    Try storing current record combination of outer tables (i.e. their
    rowids) in the temporary table. This records the fact that we've seen 
    this record combination and also tells us if we've seen it before.

  RETURN
    -1  Error
    1   The row combination is a duplicate (discard it)
    0   The row combination is not a duplicate (continue)
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
4533
int SJ_TMP_TABLE::sj_weedout_check_row(THD *thd)
4534 4535
{
  int error;
Sergey Petrunya's avatar
Sergey Petrunya committed
4536 4537
  SJ_TMP_TABLE::TAB *tab= tabs;
  SJ_TMP_TABLE::TAB *tab_end= tabs_end;
4538 4539 4540
  uchar *ptr;
  uchar *nulls_ptr;

Sergey Petrunya's avatar
Sergey Petrunya committed
4541
  DBUG_ENTER("SJ_TMP_TABLE::sj_weedout_check_row");
4542

Sergey Petrunya's avatar
Sergey Petrunya committed
4543
  if (is_degenerate)
4544
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
4545
    if (have_degenerate_row) 
4546 4547
      DBUG_RETURN(1);

Sergey Petrunya's avatar
Sergey Petrunya committed
4548
    have_degenerate_row= TRUE;
4549 4550 4551
    DBUG_RETURN(0);
  }

Sergey Petrunya's avatar
Sergey Petrunya committed
4552
  ptr= tmp_table->record[0] + 1;
4553 4554 4555 4556

  /* Put the the rowids tuple into table->record[0]: */

  // 1. Store the length 
Sergey Petrunya's avatar
Sergey Petrunya committed
4557
  if (((Field_varstring*)(tmp_table->field[0]))->length_bytes == 1)
4558
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
4559
    *ptr= (uchar)(rowid_len + null_bytes);
4560 4561 4562 4563
    ptr++;
  }
  else
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
4564
    int2store(ptr, rowid_len + null_bytes);
4565 4566 4567
    ptr += 2;
  }

4568
  nulls_ptr= ptr;
4569
  // 2. Zero the null bytes 
Sergey Petrunya's avatar
Sergey Petrunya committed
4570
  if (null_bytes)
4571
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
4572 4573
    bzero(ptr, null_bytes);
    ptr += null_bytes; 
4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592
  }

  // 3. Put the rowids
  for (uint i=0; tab != tab_end; tab++, i++)
  {
    handler *h= tab->join_tab->table->file;
    if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
    {
      /* It's a NULL-complemented row */
      *(nulls_ptr + tab->null_byte) |= tab->null_bit;
      bzero(ptr + tab->rowid_offset, h->ref_length);
    }
    else
    {
      /* Copy the rowid value */
      memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
    }
  }

Sergey Petrunya's avatar
Sergey Petrunya committed
4593
  error= tmp_table->file->ha_write_tmp_row(tmp_table->record[0]);
4594
  if (unlikely(error))
4595 4596
  {
    /* create_internal_tmp_table_from_heap will generate error if needed */
Sergey Petrunya's avatar
Sergey Petrunya committed
4597
    if (!tmp_table->file->is_fatal_error(error, HA_CHECK_DUP))
4598
      DBUG_RETURN(1); /* Duplicate */
4599 4600

    bool is_duplicate;
Sergey Petrunya's avatar
Sergey Petrunya committed
4601
    if (create_internal_tmp_table_from_heap(thd, tmp_table, start_recinfo,
4602
                                            &recinfo, error, 1, &is_duplicate))
4603
      DBUG_RETURN(-1);
4604 4605
    if (is_duplicate)
      DBUG_RETURN(1);
4606 4607 4608 4609 4610
  }
  DBUG_RETURN(0);
}


4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625 4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653 4654 4655
int init_dups_weedout(JOIN *join, uint first_table, int first_fanout_table, uint n_tables)
{
  THD *thd= join->thd;
  DBUG_ENTER("init_dups_weedout");
  SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
  SJ_TMP_TABLE::TAB *last_tab= sjtabs;
  uint jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
  uint jt_null_bits= 0;    // # null bits in tuple bytes
  /*
    Walk through the range and remember
     - tables that need their rowids to be put into temptable
     - the last outer table
  */
  for (JOIN_TAB *j=join->join_tab + first_table; 
       j < join->join_tab + first_table + n_tables; j++)
  {
    if (sj_table_is_included(join, j))
    {
      last_tab->join_tab= j;
      last_tab->rowid_offset= jt_rowid_offset;
      jt_rowid_offset += j->table->file->ref_length;
      if (j->table->maybe_null)
      {
        last_tab->null_byte= jt_null_bits / 8;
        last_tab->null_bit= jt_null_bits++;
      }
      last_tab++;
      j->table->prepare_for_position();
      j->keep_current_rowid= TRUE;
    }
  }

  SJ_TMP_TABLE *sjtbl;
  if (jt_rowid_offset) /* Temptable has at least one rowid */
  {
    size_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
    if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))) ||
        !(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) thd->alloc(tabs_size)))
      DBUG_RETURN(TRUE); /* purecov: inspected */
    memcpy(sjtbl->tabs, sjtabs, tabs_size);
    sjtbl->is_degenerate= FALSE;
    sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
    sjtbl->rowid_len= jt_rowid_offset;
    sjtbl->null_bits= jt_null_bits;
    sjtbl->null_bytes= (jt_null_bits + 7)/8;
Sergey Petrunya's avatar
Sergey Petrunya committed
4656 4657
    if (sjtbl->create_sj_weedout_tmp_table(thd))
      DBUG_RETURN(TRUE);
4658
    join->sj_tmp_tables.push_back(sjtbl->tmp_table, thd->mem_root);
4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681
  }
  else
  {
    /* 
      This is a special case where the entire subquery predicate does 
      not depend on anything at all, ie this is 
        WHERE const IN (uncorrelated select)
    */
    if (!(sjtbl= (SJ_TMP_TABLE*)thd->alloc(sizeof(SJ_TMP_TABLE))))
      DBUG_RETURN(TRUE); /* purecov: inspected */
    sjtbl->tmp_table= NULL;
    sjtbl->is_degenerate= TRUE;
    sjtbl->have_degenerate_row= FALSE;
  }

  sjtbl->next_flush_table= join->join_tab[first_table].flush_weedout_table;
  join->join_tab[first_table].flush_weedout_table= sjtbl;
  join->join_tab[first_fanout_table].first_weedout_table= sjtbl;
  join->join_tab[first_table + n_tables - 1].check_weed_out_table= sjtbl;
  DBUG_RETURN(0);
}


4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749
/*
  @brief
    Set up semi-join Loose Scan strategy for execution

  @detail
    Other strategies are done in setup_semijoin_dups_elimination(),
    however, we need to set up Loose Scan earlier, before make_join_select is
    called. This is to prevent make_join_select() from switching full index
    scans into quick selects (which will break Loose Scan access).

  @return
    0  OK
    1  Error
*/

int setup_semijoin_loosescan(JOIN *join)
{
  uint i;
  DBUG_ENTER("setup_semijoin_loosescan");

  POSITION *pos= join->best_positions + join->const_tables;
  for (i= join->const_tables ; i < join->top_join_tab_count; )
  {
    JOIN_TAB *tab=join->join_tab + i;
    switch (pos->sj_strategy) {
      case SJ_OPT_MATERIALIZE:
      case SJ_OPT_MATERIALIZE_SCAN:
        i+= 1; /* join tabs are embedded in the nest */
        pos += pos->n_sj_tables;
        break;
      case SJ_OPT_LOOSE_SCAN:
      {
        /* We jump from the last table to the first one */
        tab->loosescan_match_tab= tab + pos->n_sj_tables - 1;

        /* LooseScan requires records to be produced in order */
        if (tab->select && tab->select->quick)
          tab->select->quick->need_sorted_output();

        for (uint j= i; j < i + pos->n_sj_tables; j++)
          join->join_tab[j].inside_loosescan_range= TRUE;

        /* Calculate key length */
        uint keylen= 0;
        uint keyno= pos->loosescan_picker.loosescan_key;
        for (uint kp=0; kp < pos->loosescan_picker.loosescan_parts; kp++)
          keylen += tab->table->key_info[keyno].key_part[kp].store_length;

        tab->loosescan_key= keyno;
        tab->loosescan_key_len= keylen;
        if (pos->n_sj_tables > 1) 
          tab[pos->n_sj_tables - 1].do_firstmatch= tab;
        i+= pos->n_sj_tables;
        pos+= pos->n_sj_tables;
        break;
      }
      default:
      {
        i++;
        pos++;
        break;
      }
    }
  }
  DBUG_RETURN(FALSE);
}


4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767 4768 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850
/*
  Setup the strategies to eliminate semi-join duplicates.
  
  SYNOPSIS
    setup_semijoin_dups_elimination()
      join           Join to process
      options        Join options (needed to see if join buffering will be 
                     used or not)
      no_jbuf_after  Another bit of information re where join buffering will
                     be used.

  DESCRIPTION
    Setup the strategies to eliminate semi-join duplicates. ATM there are 4
    strategies:

    1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
                         of row combinations)
    2. FirstMatch (pick only the 1st matching row combination of inner tables)
    3. LooseScan (scanning the sj-inner table in a way that groups duplicates
                  together and picking the 1st one)
    4. SJ-Materialization.
    
    The join order has "duplicate-generating ranges", and every range is
    served by one strategy or a combination of FirstMatch with with some
    other strategy.
    
    "Duplicate-generating range" is defined as a range within the join order
    that contains all of the inner tables of a semi-join. All ranges must be
    disjoint, if tables of several semi-joins are interleaved, then the ranges
    are joined together, which is equivalent to converting
      SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
    to
      SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
    .

    Applicability conditions are as follows:

    DuplicateWeedout strategy
    ~~~~~~~~~~~~~~~~~~~~~~~~~

      (ot|nt)*  [ it ((it|ot|nt)* (it|ot))]  (nt)*
      +------+  +=========================+  +---+
        (1)                 (2)               (3)

       (1) - Prefix of OuterTables (those that participate in 
             IN-equality and/or are correlated with subquery) and outer 
             Non-correlated tables.
       (2) - The handled range. The range starts with the first sj-inner
             table, and covers all sj-inner and outer tables 
             Within the range,  Inner, Outer, outer non-correlated tables
             may follow in any order.
       (3) - The suffix of outer non-correlated tables.
    
    FirstMatch strategy
    ~~~~~~~~~~~~~~~~~~~

      (ot|nt)*  [ it ((it|nt)* it) ]  (nt)*
      +------+  +==================+  +---+
        (1)             (2)          (3)

      (1) - Prefix of outer and non-correlated tables
      (2) - The handled range, which may contain only inner and
            non-correlated tables.
      (3) - The suffix of outer non-correlated tables.

    LooseScan strategy 
    ~~~~~~~~~~~~~~~~~~

     (ot|ct|nt) [ loosescan_tbl (ot|nt|it)* it ]  (ot|nt)*
     +--------+   +===========+ +=============+   +------+
        (1)           (2)          (3)              (4)
     
      (1) - Prefix that may contain any outer tables. The prefix must contain
            all the non-trivially correlated outer tables. (non-trivially means
            that the correlation is not just through the IN-equality).
      
      (2) - Inner table for which the LooseScan scan is performed.

      (3) - The remainder of the duplicate-generating range. It is served by 
            application of FirstMatch strategy, with the exception that
            outer IN-correlated tables are considered to be non-correlated.

      (4) - THe suffix of outer and outer non-correlated tables.

  
  The choice between the strategies is made by the join optimizer (see
  advance_sj_state() and fix_semijoin_strategies_for_picked_join_order()).
  This function sets up all fields/structures/etc needed for execution except
  for setup/initialization of semi-join materialization which is done in 
  setup_sj_materialization() (todo: can't we move that to here also?)

  RETURN
    FALSE  OK 
    TRUE   Out of memory error
*/

int setup_semijoin_dups_elimination(JOIN *join, ulonglong options, 
                                    uint no_jbuf_after)
{
  uint i;
  DBUG_ENTER("setup_semijoin_dups_elimination");
4851 4852
  
  join->complex_firstmatch_tables= table_map(0);
4853

4854
  POSITION *pos= join->best_positions + join->const_tables;
4855
  for (i= join->const_tables ; i < join->top_join_tab_count; )
4856 4857 4858 4859 4860 4861
  {
    JOIN_TAB *tab=join->join_tab + i;
    switch (pos->sj_strategy) {
      case SJ_OPT_MATERIALIZE:
      case SJ_OPT_MATERIALIZE_SCAN:
        /* Do nothing */
4862 4863
        i+= 1;// It used to be pos->n_sj_tables, but now they are embedded in a nest
        pos += pos->n_sj_tables;
4864 4865 4866
        break;
      case SJ_OPT_LOOSE_SCAN:
      {
4867
        /* Setup already handled by setup_semijoin_loosescan */
Sergey Petrunya's avatar
Sergey Petrunya committed
4868
        i+= pos->n_sj_tables;
4869
        pos+= pos->n_sj_tables;
4870 4871 4872 4873 4874 4875 4876 4877 4878
        break;
      }
      case SJ_OPT_DUPS_WEEDOUT:
      {
        /*
          Check for join buffering. If there is one, move the first table
          forwards, but do not destroy other duplicate elimination methods.
        */
        uint first_table= i;
4879

4880
        uint join_cache_level= join->thd->variables.join_cache_level;
4881 4882
        for (uint j= i; j < i + pos->n_sj_tables; j++)
        {
4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893
          /*
            When we'll properly take join buffering into account during
            join optimization, the below check should be changed to 
            "if (join->best_positions[j].use_join_buffer && 
                 j <= no_jbuf_after)".
            For now, use a rough criteria:
          */
          JOIN_TAB *js_tab=join->join_tab + j; 
          if (j != join->const_tables && js_tab->use_quick != 2 &&
              j <= no_jbuf_after &&
              ((js_tab->type == JT_ALL && join_cache_level != 0) ||
Igor Babaev's avatar
Igor Babaev committed
4894 4895
               (join_cache_level > 2 && (js_tab->type == JT_REF || 
                                         js_tab->type == JT_EQ_REF))))
4896
          {
4897
            /* Looks like we'll be using join buffer */
4898
            first_table= join->const_tables;
Igor Babaev's avatar
Igor Babaev committed
4899 4900 4901 4902 4903 4904 4905 4906 4907
            /* 
              Make sure that possible sorting of rows from the head table 
              is not to be employed.
            */
            if (join->get_sort_by_join_tab())
	    {
              join->simple_order= 0;
              join->simple_group= 0;
              join->need_tmp= join->test_if_need_tmp_table();
4908 4909 4910 4911 4912
            }
            break;
          }
        }

4913
        init_dups_weedout(join, first_table, i, i + pos->n_sj_tables - first_table);
Sergey Petrunya's avatar
Sergey Petrunya committed
4914
        i+= pos->n_sj_tables;
4915
        pos+= pos->n_sj_tables;
4916 4917 4918 4919
        break;
      }
      case SJ_OPT_FIRST_MATCH:
      {
4920 4921
        JOIN_TAB *j;
        JOIN_TAB *jump_to= tab-1;
4922 4923 4924 4925

        bool complex_range= FALSE;
        table_map tables_in_range= table_map(0);

4926 4927
        for (j= tab; j != tab + pos->n_sj_tables; j++)
        {
4928
          tables_in_range |= j->table->map;
4929
          if (!j->emb_sj_nest)
4930 4931 4932 4933 4934 4935 4936 4937 4938
          {
            /* 
              Got a table that's not within any semi-join nest. This is a case
              like this:

              SELECT * FROM ot1, nt1 WHERE ot1.col IN (SELECT expr FROM it1, it2)

              with a join order of 

4939 4940 4941
                   +----- FirstMatch range ----+
                   |                           |
              ot1 it1 nt1 nt2 it2 it3 ...
4942
                   |   ^
4943
                   |   +-------- 'j' points here
4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957
                   +------------- SJ_OPT_FIRST_MATCH was set for this table as
                                  it's the first one that produces duplicates
              
            */
            DBUG_ASSERT(j != tab);  /* table ntX must have an itX before it */

            /* 
              If the table right before us is an inner table (like it1 in the
              picture), it should be set to jump back to previous outer-table
            */
            if (j[-1].emb_sj_nest)
              j[-1].do_firstmatch= jump_to;

            jump_to= j; /* Jump back to us */
4958
            complex_range= TRUE;
4959
          }
4960 4961 4962 4963 4964 4965 4966
          else
          {
            j->first_sj_inner_tab= tab;
            j->last_sj_inner_tab= tab + pos->n_sj_tables - 1;
          }
        }
        j[-1].do_firstmatch= jump_to;
Sergey Petrunya's avatar
Sergey Petrunya committed
4967
        i+= pos->n_sj_tables;
4968
        pos+= pos->n_sj_tables;
4969 4970 4971

        if (complex_range)
          join->complex_firstmatch_tables|= tables_in_range;
4972 4973 4974
        break;
      }
      case SJ_OPT_NONE:
Sergey Petrunya's avatar
Sergey Petrunya committed
4975
        i++;
4976
        pos++;
4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156
        break;
    }
  }
  DBUG_RETURN(FALSE);
}


/*
  Destroy all temporary tables created by NL-semijoin runtime
*/

void destroy_sj_tmp_tables(JOIN *join)
{
  List_iterator<TABLE> it(join->sj_tmp_tables);
  TABLE *table;
  while ((table= it++))
  {
    /* 
      SJ-Materialization tables are initialized for either sequential reading 
      or index lookup, DuplicateWeedout tables are not initialized for read 
      (we only write to them), so need to call ha_index_or_rnd_end.
    */
    table->file->ha_index_or_rnd_end();
    free_tmp_table(join->thd, table);
  }
  join->sj_tmp_tables.empty();
  join->sjm_info_list.empty();
}


/*
  Remove all records from all temp tables used by NL-semijoin runtime

  SYNOPSIS
    clear_sj_tmp_tables()
      join  The join to remove tables for

  DESCRIPTION
    Remove all records from all temp tables used by NL-semijoin runtime. This 
    must be done before every join re-execution.
*/

int clear_sj_tmp_tables(JOIN *join)
{
  int res;
  List_iterator<TABLE> it(join->sj_tmp_tables);
  TABLE *table;
  while ((table= it++))
  {
    if ((res= table->file->ha_delete_all_rows()))
      return res; /* purecov: inspected */
  }

  SJ_MATERIALIZATION_INFO *sjm;
  List_iterator<SJ_MATERIALIZATION_INFO> it2(join->sjm_info_list);
  while ((sjm= it2++))
  {
    sjm->materialized= FALSE;
  }
  return 0;
}


/*
  Check if the table's rowid is included in the temptable

  SYNOPSIS
    sj_table_is_included()
      join      The join
      join_tab  The table to be checked

  DESCRIPTION
    SemiJoinDuplicateElimination: check the table's rowid should be included
    in the temptable. This is so if

    1. The table is not embedded within some semi-join nest
    2. The has been pulled out of a semi-join nest, or

    3. The table is functionally dependent on some previous table

    [4. This is also true for constant tables that can't be
        NULL-complemented but this function is not called for such tables]

  RETURN
    TRUE  - Include table's rowid
    FALSE - Don't
*/

static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
{
  if (join_tab->emb_sj_nest)
    return FALSE;
  
  /* Check if this table is functionally dependent on the tables that
     are within the same outer join nest
  */
  TABLE_LIST *embedding= join_tab->table->pos_in_table_list->embedding;
  if (join_tab->type == JT_EQ_REF)
  {
    table_map depends_on= 0;
    uint idx;

    for (uint kp= 0; kp < join_tab->ref.key_parts; kp++)
      depends_on |= join_tab->ref.items[kp]->used_tables();

    Table_map_iterator it(depends_on & ~PSEUDO_TABLE_BITS);
    while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
    {
      JOIN_TAB *ref_tab= join->map2table[idx];
      if (embedding != ref_tab->table->pos_in_table_list->embedding)
        return TRUE;
    }
    /* Ok, functionally dependent */
    return FALSE;
  }
  /* Not functionally dependent => need to include*/
  return TRUE;
}


/*
  Index lookup-based subquery: save some flags for EXPLAIN output

  SYNOPSIS
    save_index_subquery_explain_info()
      join_tab  Subquery's join tab (there is only one as index lookup is
                only used for subqueries that are single-table SELECTs)
      where     Subquery's WHERE clause

  DESCRIPTION
    For index lookup-based subquery (i.e. one executed with
    subselect_uniquesubquery_engine or subselect_indexsubquery_engine),
    check its EXPLAIN output row should contain 
      "Using index" (TAB_INFO_FULL_SCAN_ON_NULL) 
      "Using Where" (TAB_INFO_USING_WHERE)
      "Full scan on NULL key" (TAB_INFO_FULL_SCAN_ON_NULL)
    and set appropriate flags in join_tab->packed_info.
*/

static void save_index_subquery_explain_info(JOIN_TAB *join_tab, Item* where)
{
  join_tab->packed_info= TAB_INFO_HAVE_VALUE;
  if (join_tab->table->covering_keys.is_set(join_tab->ref.key))
    join_tab->packed_info |= TAB_INFO_USING_INDEX;
  if (where)
    join_tab->packed_info |= TAB_INFO_USING_WHERE;
  for (uint i = 0; i < join_tab->ref.key_parts; i++)
  {
    if (join_tab->ref.cond_guards[i])
    {
      join_tab->packed_info |= TAB_INFO_FULL_SCAN_ON_NULL;
      break;
    }
  }
}


/*
  Check if the join can be rewritten to [unique_]indexsubquery_engine

  DESCRIPTION
    Check if the join can be changed into [unique_]indexsubquery_engine.

    The check is done after join optimization, the idea is that if the join
    has only one table and uses a [eq_]ref access generated from subselect's
    IN-equality then we replace it with a subselect_indexsubquery_engine or a
    subselect_uniquesubquery_engine.

  RETURN 
    0 - Ok, rewrite done (stop join optimization and return)
    1 - Fatal error (stop join optimization and return)
   -1 - No rewrite performed, continue with join optimization
*/

int rewrite_to_index_subquery_engine(JOIN *join)
{
  THD *thd= join->thd;
  JOIN_TAB* join_tab=join->join_tab;
  SELECT_LEX_UNIT *unit= join->unit;
  DBUG_ENTER("rewrite_to_index_subquery_engine");
5157

5158 5159 5160
  /*
    is this simple IN subquery?
  */
5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173
  /* TODO: In order to use these more efficient subquery engines in more cases,
     the following problems need to be solved:
     - the code that removes GROUP BY (group_list), also adds an ORDER BY
       (order), thus GROUP BY queries (almost?) never pass through this branch.
       Solution: remove the test below '!join->order', because we remove the
       ORDER clase for subqueries anyway.
     - in order to set a more efficient engine, the optimizer needs to both
       decide to remove GROUP BY, *and* select one of the JT_[EQ_]REF[_OR_NULL]
       access methods, *and* loose scan should be more expensive or
       inapliccable. When is that possible?
     - Consider expanding the applicability of this rewrite for loose scan
       for group by queries.
  */
5174 5175 5176
  if (!join->group_list && !join->order &&
      join->unit->item && 
      join->unit->item->substype() == Item_subselect::IN_SUBS &&
5177
      join->table_count == 1 && join->conds &&
5178
      !join->unit->is_unit_op())
5179 5180 5181 5182 5183
  {
    if (!join->having)
    {
      Item *where= join->conds;
      if (join_tab[0].type == JT_EQ_REF &&
5184
	  join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197
      {
        remove_subq_pushed_predicates(join, &where);
        save_index_subquery_explain_info(join_tab, where);
        join_tab[0].type= JT_UNIQUE_SUBQUERY;
        join->error= 0;
        DBUG_RETURN(unit->item->
                    change_engine(new
                                  subselect_uniquesubquery_engine(thd,
                                                                  join_tab,
                                                                  unit->item,
                                                                  where)));
      }
      else if (join_tab[0].type == JT_REF &&
5198
	       join_tab[0].ref.items[0]->name.str == in_left_expr_name.str)
5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213
      {
	remove_subq_pushed_predicates(join, &where);
        save_index_subquery_explain_info(join_tab, where);
        join_tab[0].type= JT_INDEX_SUBQUERY;
        join->error= 0;
        DBUG_RETURN(unit->item->
                    change_engine(new
                                  subselect_indexsubquery_engine(thd,
                                                                 join_tab,
                                                                 unit->item,
                                                                 where,
                                                                 NULL,
                                                                 0)));
      }
    } else if (join_tab[0].type == JT_REF_OR_NULL &&
5214 5215
	       join_tab[0].ref.items[0]->name.str == in_left_expr_name.str &&
               join->having->name.str == in_having_cond.str)
5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245
    {
      join_tab[0].type= JT_INDEX_SUBQUERY;
      join->error= 0;
      join->conds= remove_additional_cond(join->conds);
      save_index_subquery_explain_info(join_tab, join->conds);
      DBUG_RETURN(unit->item->
		  change_engine(new subselect_indexsubquery_engine(thd,
								   join_tab,
								   unit->item,
								   join->conds,
                                                                   join->having,
								   1)));
    }
  }

  DBUG_RETURN(-1); /* Haven't done the rewrite */
}


/**
  Remove additional condition inserted by IN/ALL/ANY transformation.

  @param conds   condition for processing

  @return
    new conditions
*/

static Item *remove_additional_cond(Item* conds)
{
5246
  if (conds->name.str == in_additional_cond.str)
5247 5248 5249 5250 5251 5252 5253 5254
    return 0;
  if (conds->type() == Item::COND_ITEM)
  {
    Item_cond *cnd= (Item_cond*) conds;
    List_iterator<Item> li(*(cnd->argument_list()));
    Item *item;
    while ((item= li++))
    {
5255
      if (item->name.str == in_additional_cond.str)
5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313
      {
	li.remove();
	if (cnd->argument_list()->elements == 1)
	  return cnd->argument_list()->head();
	return conds;
      }
    }
  }
  return conds;
}


/*
  Remove the predicates pushed down into the subquery

  SYNOPSIS
    remove_subq_pushed_predicates()
      where   IN  Must be NULL
              OUT The remaining WHERE condition, or NULL

  DESCRIPTION
    Given that this join will be executed using (unique|index)_subquery,
    without "checking NULL", remove the predicates that were pushed down
    into the subquery.

    If the subquery compares scalar values, we can remove the condition that
    was wrapped into trig_cond (it will be checked when needed by the subquery
    engine)

    If the subquery compares row values, we need to keep the wrapped
    equalities in the WHERE clause: when the left (outer) tuple has both NULL
    and non-NULL values, we'll do a full table scan and will rely on the
    equalities corresponding to non-NULL parts of left tuple to filter out
    non-matching records.

    TODO: We can remove the equalities that will be guaranteed to be true by the
    fact that subquery engine will be using index lookup. This must be done only
    for cases where there are no conversion errors of significance, e.g. 257
    that is searched in a byte. But this requires homogenization of the return 
    codes of all Field*::store() methods.
*/

static void remove_subq_pushed_predicates(JOIN *join, Item **where)
{
  if (join->conds->type() == Item::FUNC_ITEM &&
      ((Item_func *)join->conds)->functype() == Item_func::EQ_FUNC &&
      ((Item_func *)join->conds)->arguments()[0]->type() == Item::REF_ITEM &&
      ((Item_func *)join->conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
      test_if_ref (join->conds,
                   (Item_field *)((Item_func *)join->conds)->arguments()[1],
                   ((Item_func *)join->conds)->arguments()[0]))
  {
    *where= 0;
    return;
  }
}


Sergey Petrunya's avatar
Sergey Petrunya committed
5314 5315


5316
/**
5317
  Optimize all subqueries of a query that were not flattened into a semijoin.
5318

5319 5320
  @details
  Optimize all immediate children subqueries of a query.
5321 5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333

  This phase must be called after substitute_for_best_equal_field() because
  that function may replace items with other items from a multiple equality,
  and we need to reference the correct items in the index access method of the
  IN predicate.

  @return Operation status
  @retval FALSE     success.
  @retval TRUE      error occurred.
*/

bool JOIN::optimize_unflattened_subqueries()
{
5334 5335 5336 5337 5338 5339 5340 5341 5342 5343 5344 5345 5346 5347 5348 5349 5350 5351 5352 5353 5354 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370
  return select_lex->optimize_unflattened_subqueries(false);
}

/**
  Optimize all constant subqueries of a query that were not flattened into
  a semijoin.

  @details
  Similar to other constant conditions, constant subqueries can be used in
  various constant optimizations. Having optimized constant subqueries before
  these constant optimizations, makes it possible to estimate if a subquery
  is "cheap" enough to be executed during the optimization phase.

  Constant subqueries can be optimized and evaluated independent of the outer
  query, therefore if const_only = true, this method can be called early in
  the optimization phase of the outer query.

  @return Operation status
  @retval FALSE     success.
  @retval TRUE      error occurred.
*/
 
bool JOIN::optimize_constant_subqueries()
{
  ulonglong save_options= select_lex->options;
  bool res;
  /*
    Constant subqueries may be executed during the optimization phase.
    In EXPLAIN mode the optimizer doesn't initialize many of the data structures
    needed for execution. In order to make it possible to execute subqueries
    during optimization, constant subqueries must be optimized for execution,
    not for EXPLAIN.
  */
  select_lex->options&= ~SELECT_DESCRIBE;
  res= select_lex->optimize_unflattened_subqueries(true);
  select_lex->options= save_options;
  return res;
5371 5372 5373
}


5374
/*
5375 5376 5377 5378 5379
  Join tab execution startup function.

  SYNOPSIS
    join_tab_execution_startup()
      tab  Join tab to perform startup actions for
5380 5381 5382 5383 5384 5385 5386 5387 5388

  DESCRIPTION
    Join tab execution startup function. This is different from
    tab->read_first_record in the regard that this has actions that are to be
    done once per join execution.

    Currently there are only two possible startup functions, so we have them
    both here inside if (...) branches. In future we could switch to function
    pointers.
Sergey Petrunya's avatar
Sergey Petrunya committed
5389 5390

  TODO: consider moving this together with JOIN_TAB::preread_init
5391 5392
  
  RETURN 
psergey's avatar
psergey committed
5393 5394
    NESTED_LOOP_OK - OK
    NESTED_LOOP_ERROR| NESTED_LOOP_KILLED - Error, abort the join execution
5395 5396
*/

psergey's avatar
psergey committed
5397
enum_nested_loop_state join_tab_execution_startup(JOIN_TAB *tab)
5398 5399
{
  Item_in_subselect *in_subs;
5400
  DBUG_ENTER("join_tab_execution_startup");
Sergey Petrunya's avatar
Sergey Petrunya committed
5401
  
5402 5403 5404
  if (tab->table->pos_in_table_list && 
      (in_subs= tab->table->pos_in_table_list->jtbm_subselect))
  {
psergey's avatar
psergey committed
5405
    /* It's a non-merged SJM nest */
5406 5407 5408 5409 5410 5411 5412 5413 5414
    DBUG_ASSERT(in_subs->engine->engine_type() ==
                subselect_engine::HASH_SJ_ENGINE);
    subselect_hash_sj_engine *hash_sj_engine=
      ((subselect_hash_sj_engine*)in_subs->engine);
    if (!hash_sj_engine->is_materialized)
    {
      hash_sj_engine->materialize_join->exec();
      hash_sj_engine->is_materialized= TRUE; 

5415 5416
      if (unlikely(hash_sj_engine->materialize_join->error) ||
          unlikely(tab->join->thd->is_fatal_error))
psergey's avatar
psergey committed
5417
        DBUG_RETURN(NESTED_LOOP_ERROR);
5418 5419
    }
  }
5420 5421 5422
  else if (tab->bush_children)
  {
    /* It's a merged SJM nest */
psergey's avatar
psergey committed
5423
    enum_nested_loop_state rc;
5424 5425 5426 5427
    SJ_MATERIALIZATION_INFO *sjm= tab->bush_children->start->emb_sj_nest->sj_mat_info;

    if (!sjm->materialized)
    {
5428 5429 5430
      JOIN *join= tab->join;
      JOIN_TAB *join_tab= tab->bush_children->start;
      JOIN_TAB *save_return_tab= join->return_tab;
5431 5432 5433 5434 5435 5436 5437 5438
      /*
        Now run the join for the inner tables. The first call is to run the
        join, the second one is to signal EOF (this is essential for some
        join strategies, e.g. it will make join buffering flush the records)
      */
      if ((rc= sub_select(join, join_tab, FALSE/* no EOF */)) < 0 ||
          (rc= sub_select(join, join_tab, TRUE/* now EOF */)) < 0)
      {
5439
        join->return_tab= save_return_tab;
5440 5441
        DBUG_RETURN(rc); /* it's NESTED_LOOP_(ERROR|KILLED)*/
      }
5442
      join->return_tab= save_return_tab;
5443 5444 5445 5446
      sjm->materialized= TRUE;
    }
  }

psergey's avatar
psergey committed
5447
  DBUG_RETURN(NESTED_LOOP_OK);
5448
}
5449

Sergey Petrunya's avatar
Sergey Petrunya committed
5450

5451 5452 5453 5454 5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467
/*
  Create a dummy temporary table, useful only for the sake of having a 
  TABLE* object with map,tablenr and maybe_null properties.
  
  This is used by non-mergeable semi-join materilization code to handle
  degenerate cases where materialized subquery produced "Impossible WHERE" 
  and thus wasn't materialized.
*/

TABLE *create_dummy_tmp_table(THD *thd)
{
  DBUG_ENTER("create_dummy_tmp_table");
  TABLE *table;
  TMP_TABLE_PARAM sjm_table_param;
  sjm_table_param.init();
  sjm_table_param.field_count= 1;
  List<Item> sjm_table_cols;
5468
  const LEX_CSTRING dummy_name= { STRING_WITH_LEN("dummy") };
Monty's avatar
Monty committed
5469
  Item *column_item= new (thd->mem_root) Item_int(thd, 1);
5470 5471 5472
  if (!column_item)
    DBUG_RETURN(NULL);

5473
  sjm_table_cols.push_back(column_item, thd->mem_root);
5474 5475 5476 5477
  if (!(table= create_tmp_table(thd, &sjm_table_param, 
                                sjm_table_cols, (ORDER*) 0, 
                                TRUE /* distinct */, 
                                1, /*save_sum_fields*/
5478 5479
                                thd->variables.option_bits |
                                TMP_TABLE_ALL_COLUMNS, 
5480
                                HA_POS_ERROR /*rows_limit */, 
5481
                                &dummy_name, TRUE /* Do not open */)))
5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499
  {
    DBUG_RETURN(NULL);
  }
  DBUG_RETURN(table);
}


/*
  A class that is used to catch one single tuple that is sent to the join
  output, and save it in Item_cache element(s).

  It is very similar to select_singlerow_subselect but doesn't require a 
  Item_singlerow_subselect item.
*/

class select_value_catcher :public select_subselect
{
public:
5500 5501
  select_value_catcher(THD *thd_arg, Item_subselect *item_arg):
    select_subselect(thd_arg, item_arg)
5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515
  {}
  int send_data(List<Item> &items);
  int setup(List<Item> *items);
  bool assigned;  /* TRUE <=> we've caught a value */
  uint n_elements; /* How many elements we get */
  Item_cache **row; /* Array of cache elements */
};


int select_value_catcher::setup(List<Item> *items)
{
  assigned= FALSE;
  n_elements= items->elements;
 
5516
  if (!(row= (Item_cache**) thd->alloc(sizeof(Item_cache*) * n_elements)))
5517 5518 5519 5520 5521 5522
    return TRUE;
  
  Item *sel_item;
  List_iterator<Item> li(*items);
  for (uint i= 0; (sel_item= li++); i++)
  {
5523
    if (!(row[i]= sel_item->get_cache(thd)))
5524
      return TRUE;
5525
    row[i]->setup(thd, sel_item);
5526 5527 5528 5529 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554
  }
  return FALSE;
}


int select_value_catcher::send_data(List<Item> &items)
{
  DBUG_ENTER("select_value_catcher::send_data");
  DBUG_ASSERT(!assigned);
  DBUG_ASSERT(items.elements == n_elements);

  if (unit->offset_limit_cnt)
  {				          // Using limit offset,count
    unit->offset_limit_cnt--;
    DBUG_RETURN(0);
  }

  Item *val_item;
  List_iterator_fast<Item> li(items);
  for (uint i= 0; (val_item= li++); i++)
  {
    row[i]->store(val_item);
    row[i]->cache_value();
  }
  assigned= TRUE;
  DBUG_RETURN(0);
}


5555 5556
/**
  @brief
5557
    Set missing links on multiply equalities
5558

5559 5560 5561 5562 5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641
  @param thd               the thread handle
  @param cond              the condition to set links for
  @param inherited         path to all inherited multiple equality items
  @param build_cond_equal  flag to control if COND_EQUAL for AND-condition
                           should be built

  @details
    The method traverses cond and set links for the upper COND_EQUAL levels
    where needed.
    If build_cond_equal is set to true it builds for each AND-level except the
    external one COND_EQUAL.
*/

static
void set_cond_equal_links(THD *thd, Item *cond, COND_EQUAL *inherited,
                          bool build_cond_equal)
{
  if (cond->type() == Item::FUNC_ITEM &&
      ((Item_func*) cond)->functype() == Item_func::MULT_EQUAL_FUNC)
  {
    ((Item_equal *)cond)->upper_levels= inherited;
    if (inherited)
      inherited->increase_references();
  }

  if (cond->type() != Item::COND_ITEM)
    return;

  List_iterator<Item> it(*((Item_cond *)cond)->argument_list());
  Item *item;
  while ((item=it++))
  {
    if (item->type() != Item::COND_ITEM ||
        ((Item_cond*) item)->functype() != Item_func::COND_AND_FUNC)
    {
      set_cond_equal_links(thd, item, inherited, build_cond_equal);
      continue;
    }
    Item_cond_and *and_item= (Item_cond_and *)item;
    if (build_cond_equal)
    {
      COND_EQUAL new_cond_equal;
      List_iterator<Item> li(*and_item->argument_list());
      Item *elem;

      while ((elem=li++))
      {
        if (elem->type() == Item::FUNC_ITEM &&
            ((Item_func*) elem)->functype() == Item_func::MULT_EQUAL_FUNC)
        {
          if (new_cond_equal.current_level.push_back((Item_equal *)elem,
                                                     thd->mem_root))
            return;
          li.remove();
        }
      }
      List<Item> *equal_list=
        (List<Item> *)&and_item->m_cond_equal.current_level;
      and_item->m_cond_equal.copy(new_cond_equal);
      and_item->argument_list()->append(equal_list);
    }
    and_item->m_cond_equal.upper_levels= inherited;
    and_item->m_cond_equal.clean_references();
    if (inherited)
      inherited->increase_references();

    set_cond_equal_links(thd, item, &and_item->m_cond_equal,
                         build_cond_equal);
  }
}


/**
  @brief
    Conjunct conditions after optimize_cond() call

  @param thd               the thread handle
  @param cond              the condition where to attach new conditions
  @param cond_eq           IN/OUT the multiple equalities of cond
  @param new_conds         IN/OUT the list of conditions needed to add
  @param cond_value        the returned value of the condition
  @param build_cond_equal  flag to control if COND_EQUAL elements for
                           AND-conditions should be built
5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652 5653 5654 5655 5656

  @details
    The method creates new condition through conjunction of cond and
    the conditions from new_conds list.
    The method is called after optimize_cond() for cond. The result
    of the conjunction should be the same as if it was done before the
    the optimize_cond() call.

  @retval NULL       if an error occurs
  @retval otherwise  the created condition
*/

Item *and_new_conditions_to_optimized_cond(THD *thd, Item *cond,
                                           COND_EQUAL **cond_eq,
                                           List<Item> &new_conds,
5657 5658
                                           Item::cond_result *cond_value,
                                           bool build_cond_equal)
5659 5660
{
  COND_EQUAL new_cond_equal;
5661
  COND_EQUAL *inherited= 0;
5662 5663 5664 5665 5666 5667 5668 5669 5670 5671 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 5682 5683 5684 5685
  Item *item;
  Item_equal *equality;
  bool is_simplified_cond= false;
  List_iterator<Item> li(new_conds);
  List_iterator_fast<Item_equal> it(new_cond_equal.current_level);

  /*
    Creates multiple equalities new_cond_equal from new_conds list
    equalities. If multiple equality can't be created or the condition
    from new_conds list isn't an equality the method leaves it in new_conds
    list.

    The equality can't be converted into the multiple equality if it
    is a knowingly false or true equality.
    For example, (3 = 1) equality.
  */
  while ((item=li++))
  {
    if (item->type() == Item::FUNC_ITEM &&
        ((Item_func *) item)->functype() == Item_func::EQ_FUNC &&
        check_simple_equality(thd,
                             Item::Context(Item::ANY_SUBST,
                             ((Item_func_equal *)item)->compare_type_handler(),
                             ((Item_func_equal *)item)->compare_collation()),
5686 5687
                             ((Item_func *)item)->arguments()[0],
                             ((Item_func *)item)->arguments()[1],
5688 5689 5690 5691 5692 5693 5694 5695 5696 5697 5698 5699 5700 5701 5702 5703 5704 5705 5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733
                             &new_cond_equal))
      li.remove();
  }

  it.rewind();
  if (cond && cond->type() == Item::COND_ITEM &&
      ((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  {
    /*
      cond is an AND-condition.
      The method conjugates the AND-condition cond, created multiple
      equalities new_cond_equal and remain conditions from new_conds.

      First, the method disjoins multiple equalities of cond and
      merges new_cond_equal multiple equalities with these equalities.
      It checks if after the merge the multiple equalities are knowingly
      true or false equalities.
      It attaches to cond the conditions from new_conds list and the result
      of the merge of multiple equalities. The multiple equalities are
      attached only to the upper level of AND-condition cond. So they
      should be pushed down to the inner levels of cond AND-condition
      if needed. It is done by propagate_new_equalities().
    */
    COND_EQUAL *cond_equal= &((Item_cond_and *) cond)->m_cond_equal;
    List<Item_equal> *cond_equalities= &cond_equal->current_level;
    List<Item> *and_args= ((Item_cond_and *)cond)->argument_list();
    and_args->disjoin((List<Item> *) cond_equalities);
    and_args->append(&new_conds);

    while ((equality= it++))
    {
      equality->upper_levels= 0;
      equality->merge_into_list(thd, cond_equalities, false, false);
    }
    List_iterator_fast<Item_equal> ei(*cond_equalities);
    while ((equality= ei++))
    {
      if (equality->const_item() && !equality->val_int())
        is_simplified_cond= true;
      equality->fixed= 0;
      if (equality->fix_fields(thd, NULL))
        return NULL;
    }

    and_args->append((List<Item> *) cond_equalities);
    *cond_eq= &((Item_cond_and *) cond)->m_cond_equal;
5734
    inherited= &((Item_cond_and *)cond)->m_cond_equal;
5735 5736 5737 5738 5739 5740 5741 5742 5743 5744 5745 5746 5747 5748 5749 5750 5751 5752 5753 5754 5755 5756 5757 5758 5759 5760 5761 5762 5763 5764 5765 5766 5767 5768 5769 5770 5771 5772 5773 5774 5775

    propagate_new_equalities(thd, cond, cond_equalities,
                             cond_equal->upper_levels,
                             &is_simplified_cond);
    cond= cond->propagate_equal_fields(thd,
                                       Item::Context_boolean(),
                                       cond_equal);
  }
  else
  {
    /*
      cond isn't AND-condition or is NULL.
      There can be several cases:

      1. cond is a multiple equality.
         In this case cond is merged with the multiple equalities of
         new_cond_equal.
         The new condition is created with the conjunction of new_conds
         list conditions and the result of merge of multiple equalities.
      2. cond is NULL
         The new condition is created from the conditions of new_conds
         list and multiple equalities from new_cond_equal.
      3. Otherwise
         In this case the new condition is created from cond, remain conditions
         from new_conds list and created multiple equalities from
         new_cond_equal.
    */
    List<Item> new_conds_list;
    /* Flag is set to true if cond is a multiple equality */
    bool is_mult_eq= (cond && cond->type() == Item::FUNC_ITEM &&
        ((Item_func*) cond)->functype() == Item_func::MULT_EQUAL_FUNC);

    if (cond && !is_mult_eq &&
        new_conds_list.push_back(cond, thd->mem_root))
      return NULL;

    if (new_conds.elements > 0)
    {
      li.rewind();
      while ((item=li++))
      {
5776
        if (!item->is_fixed() && item->fix_fields(thd, NULL))
5777 5778 5779 5780
          return NULL;
        if (item->const_item() && !item->val_int())
          is_simplified_cond= true;
      }
5781
      new_conds_list.append(&new_conds);
5782 5783
    }

5784 5785 5786 5787 5788 5789 5790
    if (is_mult_eq)
    {
      Item_equal *eq_cond= (Item_equal *)cond;
      eq_cond->upper_levels= 0;
      eq_cond->merge_into_list(thd, &new_cond_equal.current_level,
                               false, false);

5791 5792 5793 5794 5795
      while ((equality= it++))
      {
        if (equality->const_item() && !equality->val_int())
          is_simplified_cond= true;
      }
5796 5797 5798

      if (new_cond_equal.current_level.elements +
          new_conds_list.elements == 1)
5799
      {
5800 5801 5802 5803 5804
        it.rewind();
        equality= it++;
        equality->fixed= 0;
        if (equality->fix_fields(thd, NULL))
          return NULL;
5805
      }
5806
      (*cond_eq)->copy(new_cond_equal);
5807
    }
5808
    new_conds_list.append((List<Item> *)&new_cond_equal.current_level);
5809 5810 5811 5812 5813 5814 5815 5816 5817

    if (new_conds_list.elements > 1)
    {
      Item_cond_and *and_cond=
        new (thd->mem_root) Item_cond_and(thd, new_conds_list);

      and_cond->m_cond_equal.copy(new_cond_equal);
      cond= (Item *)and_cond;
      *cond_eq= &((Item_cond_and *)cond)->m_cond_equal;
5818
      inherited= &((Item_cond_and *)cond)->m_cond_equal;
5819 5820 5821 5822 5823 5824 5825
    }
    else
    {
      List_iterator_fast<Item> iter(new_conds_list);
      cond= iter++;
    }

5826
    if (!cond->is_fixed() && cond->fix_fields(thd, NULL))
5827 5828 5829 5830 5831 5832 5833 5834 5835 5836 5837 5838 5839 5840 5841
      return NULL;

    if (new_cond_equal.current_level.elements > 0)
      cond= cond->propagate_equal_fields(thd,
                                         Item::Context_boolean(),
                                         &new_cond_equal);
  }

  /*
    If it was found that some of the created condition parts are knowingly
    true or false equalities the method calls removes_eq_cond() to remove them
    from cond and set the cond_value to the appropriate value.
  */
  if (is_simplified_cond)
    cond= cond->remove_eq_conds(thd, cond_value, true);
5842 5843 5844 5845 5846 5847

  if (cond)
  {
    set_cond_equal_links(thd, cond, inherited, build_cond_equal);
  }

5848 5849 5850 5851 5852 5853 5854 5855 5856 5857 5858 5859 5860 5861 5862 5863 5864 5865 5866 5867 5868 5869 5870 5871 5872 5873 5874 5875 5876 5877 5878 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906 5907 5908 5909 5910 5911 5912 5913 5914 5915 5916 5917 5918 5919 5920 5921 5922 5923 5924 5925
  return cond;
}


/**
  @brief  Materialize a degenerate jtbm semi join

  @param thd        thread handler
  @param tbl        table list for the target jtbm semi join table
  @param subq_pred  IN subquery predicate with the degenerate jtbm semi join
  @param eq_list    IN/OUT the list where to add produced equalities

  @details
    The method materializes the degenerate jtbm semi join for the
    subquery from the IN subquery predicate subq_pred taking table
    as the target for materialization.
    Any degenerate table is guaranteed to produce 0 or 1 record.
    Examples of both cases:

    select * from ot where col in (select ... from it where 2>3)
    select * from ot where col in (select MY_MIN(it.key) from it)

    in this case, there is no necessity to create a temp.table for
    materialization.
    We now just need to
    1. Check whether 1 or 0 records are produced, setup this as a
       constant join tab.
    2. Create a dummy temporary table, because all of the join
       optimization code relies on TABLE object being present.

    In the case when materialization produces one row the function
    additionally creates equalities between the expressions from the
    left part of the IN subquery predicate and the corresponding
    columns of the produced row. These equalities are added to the
    list eq_list. They are supposed to be conjuncted with the condition
    of the WHERE clause.

  @retval TRUE   if an error occurs
  @retval FALSE  otherwise
*/

bool execute_degenerate_jtbm_semi_join(THD *thd,
                                       TABLE_LIST *tbl,
                                       Item_in_subselect *subq_pred,
                                       List<Item> &eq_list)
{
  DBUG_ENTER("execute_degenerate_jtbm_semi_join");
  select_value_catcher *new_sink;

  DBUG_ASSERT(subq_pred->engine->engine_type() ==
              subselect_engine::SINGLE_SELECT_ENGINE);
  subselect_single_select_engine *engine=
    (subselect_single_select_engine*)subq_pred->engine;
  if (!(new_sink= new (thd->mem_root) select_value_catcher(thd, subq_pred)))
    DBUG_RETURN(TRUE);
  if (new_sink->setup(&engine->select_lex->join->fields_list) ||
      engine->select_lex->join->change_result(new_sink, NULL) ||
      engine->exec())
  {
    DBUG_RETURN(TRUE);
  }
  subq_pred->is_jtbm_const_tab= TRUE;

  if (new_sink->assigned)
  {
    /*
      Subselect produced one row, which is saved in new_sink->row.
      Save "left_expr[i] == row[i]" equalities into the eq_list.
    */
    subq_pred->jtbm_const_row_found= TRUE;

    Item *eq_cond;
    for (uint i= 0; i < subq_pred->left_expr->cols(); i++)
    {
      eq_cond=
        new (thd->mem_root) Item_func_eq(thd,
                                         subq_pred->left_expr->element_index(i),
                                         new_sink->row[i]);
5926 5927
      if (!eq_cond || eq_cond->fix_fields(thd, NULL) ||
          eq_list.push_back(eq_cond, thd->mem_root))
5928 5929 5930 5931 5932 5933 5934 5935 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 5961 5962 5963 5964 5965 5966 5967 5968 5969 5970 5971 5972 5973 5974 5975
        DBUG_RETURN(TRUE);
    }
  }
  else
  {
    /* Subselect produced no rows. Just set the flag */
    subq_pred->jtbm_const_row_found= FALSE;
  }

  TABLE *dummy_table;
  if (!(dummy_table= create_dummy_tmp_table(thd)))
    DBUG_RETURN(TRUE);
  tbl->table= dummy_table;
  tbl->table->pos_in_table_list= tbl;
  /*
    Note: the table created above may be freed by:
    1. JOIN_TAB::cleanup(), when the parent join is a regular join.
    2. cleanup_empty_jtbm_semi_joins(), when the parent join is a
       degenerate join (e.g. one with "Impossible where").
  */
  setup_table_map(tbl->table, tbl, tbl->jtbm_table_no);
  DBUG_RETURN(FALSE);
}


/**
  @brief
    Execute degenerate jtbm semi joins before optimize_cond() for parent

  @param join       the parent join for jtbm semi joins
  @param join_list  the list of tables where jtbm semi joins are processed
  @param eq_list    IN/OUT the list where to add equalities produced after
                    materialization of single-row degenerate jtbm semi joins

  @details
    The method traverses join_list trying to find any degenerate jtbm semi
    joins for subqueries of IN predicates. For each degenerate jtbm
    semi join execute_degenerate_jtbm_semi_join() is called. As a result
    of this call new equalities that substitute for single-row materialized
    jtbm semi join are added to eq_list.

    In the case when a table is nested in another table 'nested_join' the
    method is recursively called for the join_list of the 'nested_join' trying
    to find in the list any degenerate jtbm semi joins. Currently a jtbm semi
    join may occur in a mergeable semi join nest.

  @retval TRUE   if an error occurs
  @retval FALSE  otherwise
5976 5977
*/

5978 5979 5980 5981 5982 5983 5984 5985 5986 5987 5988 5989 5990 5991 5992 5993 5994 5995 5996 5997 5998 5999 6000 6001 6002 6003 6004 6005 6006 6007 6008 6009 6010 6011 6012 6013 6014 6015 6016 6017 6018 6019 6020 6021 6022 6023 6024 6025 6026 6027 6028 6029 6030 6031 6032 6033 6034 6035 6036 6037 6038 6039 6040 6041 6042 6043 6044 6045 6046 6047 6048 6049 6050 6051 6052 6053 6054 6055 6056 6057 6058 6059 6060
bool setup_degenerate_jtbm_semi_joins(JOIN *join,
                                      List<TABLE_LIST> *join_list,
				      List<Item> &eq_list)
{
  TABLE_LIST *table;
  NESTED_JOIN *nested_join;
  List_iterator<TABLE_LIST> li(*join_list);
  THD *thd= join->thd;
  DBUG_ENTER("setup_degenerate_jtbm_semi_joins");

  while ((table= li++))
  {
    Item_in_subselect *subq_pred;

    if ((subq_pred= table->jtbm_subselect))
    {
      JOIN *subq_join= subq_pred->unit->first_select()->join;

      if (!subq_join->tables_list || !subq_join->table_count)
      {
        if (execute_degenerate_jtbm_semi_join(thd,
                                              table,
                                              subq_pred,
                                              eq_list))
          DBUG_RETURN(TRUE);
        join->is_orig_degenerated= true;
      }
    }
    if ((nested_join= table->nested_join))
    {
      if (setup_degenerate_jtbm_semi_joins(join,
                                           &nested_join->join_list,
                                           eq_list))
	DBUG_RETURN(TRUE);
    }
  }
  DBUG_RETURN(FALSE);
}


/**
  @brief
    Optimize jtbm semi joins for materialization

  @param join       the parent join for jtbm semi joins
  @param join_list  the list of TABLE_LIST objects where jtbm semi join
                    can occur
  @param eq_list    IN/OUT the list where to add produced equalities

  @details
    This method is called by the optimizer after the call of
    optimize_cond() for parent select.
    The method traverses join_list trying to find any jtbm semi joins for
    subqueries from IN predicates and optimizes them.
    After the optimization some of jtbm semi joins may become degenerate.
    For example the subquery 'SELECT MAX(b) FROM t2' from the query

    SELECT * FROM t1 WHERE 4 IN (SELECT MAX(b) FROM t2);

    will become degenerate if there is an index on t2.b.
    If a subquery becomes degenerate it is handled by the function
    execute_degenerate_jtbm_semi_join().

    Otherwise the method creates a temporary table in which the subquery
    of the jtbm semi join will be materialied.

    The function saves the equalities between all pairs of the expressions
    from the left part of the IN subquery predicate and the corresponding
    columns of the subquery from the predicate in eq_list appending them
    to the list. The equalities of eq_list will be later conjucted with the
    condition of the WHERE clause.

    In the case when a table is nested in another table 'nested_join' the
    method is recursively called for the join_list of the 'nested_join' trying
    to find in the list any degenerate jtbm semi joins. Currently a jtbm semi
    join may occur in a mergeable semi join nest.

  @retval TRUE   if an error occurs
  @retval FALSE  otherwise
*/

bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list,
                           List<Item> &eq_list)
6061 6062 6063 6064
{
  TABLE_LIST *table;
  NESTED_JOIN *nested_join;
  List_iterator<TABLE_LIST> li(*join_list);
Monty's avatar
Monty committed
6065
  THD *thd= join->thd;
6066
  DBUG_ENTER("setup_jtbm_semi_joins");
6067

6068 6069
  while ((table= li++))
  {
6070
    Item_in_subselect *subq_pred;
6071
    
6072
    if ((subq_pred= table->jtbm_subselect))
6073 6074 6075 6076 6077
    {
      double rows;
      double read_time;

      /*
6078
        Perform optimization of the subquery, so that we know estimated
6079 6080 6081 6082 6083 6084 6085 6086 6087 6088 6089 6090
        - cost of materialization process 
        - how many records will be in the materialized temp.table
      */
      if (subq_pred->optimize(&rows, &read_time))
        DBUG_RETURN(TRUE);

      subq_pred->jtbm_read_time= read_time;
      subq_pred->jtbm_record_count=rows;
      JOIN *subq_join= subq_pred->unit->first_select()->join;

      if (!subq_join->tables_list || !subq_join->table_count)
      {
6091 6092 6093
        if (!join->is_orig_degenerated &&
            execute_degenerate_jtbm_semi_join(thd, table, subq_pred,
                                               eq_list))
6094 6095 6096 6097 6098 6099 6100
          DBUG_RETURN(TRUE);
      }
      else
      {
        DBUG_ASSERT(subq_pred->test_set_strategy(SUBS_MATERIALIZATION));
        subq_pred->is_jtbm_const_tab= FALSE;
        subselect_hash_sj_engine *hash_sj_engine=
6101
          ((subselect_hash_sj_engine*)subq_pred->engine);
6102 6103 6104 6105 6106 6107
        
        table->table= hash_sj_engine->tmp_table;
        table->table->pos_in_table_list= table;

        setup_table_map(table->table, table, table->jtbm_table_no);

6108 6109 6110 6111
        List_iterator<Item> li(*hash_sj_engine->semi_join_conds->argument_list());
        Item *item;
        while ((item=li++))
        {
6112
          item->update_used_tables();
6113 6114 6115
          if (eq_list.push_back(item, thd->mem_root))
            DBUG_RETURN(TRUE);
        }
6116
      }
Sergei Golubchik's avatar
Sergei Golubchik committed
6117
      table->table->maybe_null= MY_TEST(join->mixed_implicit_grouping);
6118 6119 6120
    }
    if ((nested_join= table->nested_join))
    {
6121
      if (setup_jtbm_semi_joins(join, &nested_join->join_list, eq_list))
6122 6123 6124 6125 6126 6127 6128
        DBUG_RETURN(TRUE);
    }
  }
  DBUG_RETURN(FALSE);
}


6129 6130 6131 6132 6133 6134 6135 6136 6137 6138 6139 6140 6141 6142 6143 6144 6145 6146
/*
  Cleanup non-merged semi-joins (JBMs) that have empty.

  This function is to cleanups for a special case:  
  Consider a query like 

    select * from t1 where 1=2 AND t1.col IN (select max(..) ... having 1=2)

  For this query, optimization of subquery will short-circuit, and 
  setup_jtbm_semi_joins() will call create_dummy_tmp_table() so that we have
  empty, constant temp.table to stand in as materialized temp. table.

  Now, suppose that the upper join is also found to be degenerate. In that
  case, no JOIN_TAB array will be produced, and hence, JOIN::cleanup() will
  have a problem with cleaning up empty JTBMs (non-empty ones are cleaned up
  through Item::cleanup() calls).
*/

6147
void cleanup_empty_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list)
6148
{
6149
  List_iterator<TABLE_LIST> li(*join_list);
6150 6151 6152 6153 6154 6155 6156 6157 6158 6159 6160
  TABLE_LIST *table;
  while ((table= li++))
  {
    if ((table->jtbm_subselect && table->jtbm_subselect->is_jtbm_const_tab))
    {
      if (table->table)
      {
        free_tmp_table(join->thd, table->table);
        table->table= NULL;
      }
    }
6161 6162 6163 6164
    else if (table->nested_join && table->sj_subq_pred)
    {
      cleanup_empty_jtbm_semi_joins(join, &table->nested_join->join_list);
    }
6165 6166 6167 6168
  }
}


6169 6170 6171 6172 6173 6174 6175 6176 6177 6178 6179 6180 6181 6182 6183 6184 6185 6186 6187 6188 6189 6190 6191 6192 6193 6194 6195 6196 6197 6198 6199 6200 6201 6202 6203 6204
/**
  Choose an optimal strategy to execute an IN/ALL/ANY subquery predicate
  based on cost.

  @param join_tables  the set of tables joined in the subquery

  @notes
  The method chooses between the materialization and IN=>EXISTS rewrite
  strategies for the execution of a non-flattened subquery IN predicate.
  The cost-based decision is made as follows:

  1. compute materialize_strategy_cost based on the unmodified subquery
  2. reoptimize the subquery taking into account the IN-EXISTS predicates
  3. compute in_exists_strategy_cost based on the reoptimized plan
  4. compare and set the cheaper strategy
     if (materialize_strategy_cost >= in_exists_strategy_cost)
       in_strategy = MATERIALIZATION
     else
       in_strategy = IN_TO_EXISTS
  5. if in_strategy = MATERIALIZATION and it is not possible to initialize it
       revert to IN_TO_EXISTS
  6. if (in_strategy == MATERIALIZATION)
       revert the subquery plan to the original one before reoptimizing
     else
       inject the IN=>EXISTS predicates into the new EXISTS subquery plan

  The implementation itself is a bit more complicated because it takes into
  account two more factors:
  - whether the user allowed both strategies through an optimizer_switch, and
  - if materialization was the cheaper strategy, whether it can be executed
    or not.

  @retval FALSE     success.
  @retval TRUE      error occurred.
*/

6205
bool JOIN::choose_subquery_plan(table_map join_tables)
unknown's avatar
unknown committed
6206
{
6207
  enum_reopt_result reopt_result= REOPT_NONE;
6208 6209
  Item_in_subselect *in_subs;

6210 6211 6212 6213 6214 6215 6216
  /*
    IN/ALL/ANY optimizations are not applicable for so called fake select
    (this select exists only to filter results of union if it is needed).
  */
  if (select_lex == select_lex->master_unit()->fake_select_lex)
    return 0;

6217
  if (is_in_subquery())
6218
  {
6219
    in_subs= (Item_in_subselect*) unit->item;
6220 6221 6222 6223 6224
    if (in_subs->create_in_to_exists_cond(this))
      return true;
  }
  else
    return false;
6225

unknown's avatar
unknown committed
6226 6227
  /* A strategy must be chosen earlier. */
  DBUG_ASSERT(in_subs->has_strategy());
6228
  DBUG_ASSERT(in_to_exists_where || in_to_exists_having);
6229 6230
  DBUG_ASSERT(!in_to_exists_where || in_to_exists_where->is_fixed());
  DBUG_ASSERT(!in_to_exists_having || in_to_exists_having->is_fixed());
6231

6232 6233
  /* The original QEP of the subquery. */
  Join_plan_state save_qep(table_count);
6234

6235
  /*
6236 6237 6238
    Compute and compare the costs of materialization and in-exists if both
    strategies are possible and allowed by the user (checked during the prepare
    phase.
6239
  */
unknown's avatar
unknown committed
6240 6241
  if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
      in_subs->test_strategy(SUBS_IN_TO_EXISTS))
6242
  {
unknown's avatar
unknown committed
6243
    JOIN *outer_join;
6244
    JOIN *inner_join= this;
unknown's avatar
unknown committed
6245 6246 6247
    /* Number of unique value combinations filtered by the IN predicate. */
    double outer_lookup_keys;
    /* Cost and row count of the unmodified subquery. */
6248
    double inner_read_time_1, inner_record_count_1;
unknown's avatar
unknown committed
6249
    /* Cost of the subquery with injected IN-EXISTS predicates. */
unknown's avatar
unknown committed
6250
    double inner_read_time_2;
6251
    /* The cost to compute IN via materialization. */
6252
    double materialize_strategy_cost;
6253
    /* The cost of the IN->EXISTS strategy. */
6254
    double in_exists_strategy_cost;
unknown's avatar
unknown committed
6255
    double dummy;
6256

unknown's avatar
unknown committed
6257 6258 6259 6260 6261
    /*
      A. Estimate the number of rows of the outer table that will be filtered
      by the IN predicate.
    */
    outer_join= unit->outer_select() ? unit->outer_select()->join : NULL;
6262 6263 6264 6265 6266 6267 6268
    /*
      Get the cost of the outer join if:
      (1) It has at least one table, and
      (2) It has been already optimized (if there is no join_tab, then the
          outer join has not been optimized yet).
    */
    if (outer_join && outer_join->table_count > 0 && // (1)
6269 6270
        outer_join->join_tab &&                      // (2)
        !in_subs->const_item())
unknown's avatar
unknown committed
6271
    {
unknown's avatar
unknown committed
6272 6273 6274 6275 6276 6277 6278 6279 6280 6281 6282 6283
      /*
        TODO:
        Currently outer_lookup_keys is computed as the number of rows in
        the partial join including the JOIN_TAB where the IN predicate is
        pushed to. In the general case this is a gross overestimate because
        due to caching we are interested only in the number of unique keys.
        The search key may be formed by columns from much fewer than all
        tables in the partial join. Example:
        select * from t1, t2 where t1.c1 = t2.key AND t2.c2 IN (select ...);
        If the join order: t1, t2, the number of unique lookup keys is ~ to
        the number of unique values t2.c2 in the partial join t1 join t2.
      */
6284
      outer_join->get_partial_cost_and_fanout(in_subs->get_join_tab_idx(),
Sergey Petrunya's avatar
Sergey Petrunya committed
6285 6286
                                              table_map(-1),
                                              &dummy,
unknown's avatar
unknown committed
6287
                                              &outer_lookup_keys);
unknown's avatar
unknown committed
6288
    }
6289 6290
    else
    {
6291 6292 6293 6294
      /*
        TODO: outer_join can be NULL for DELETE statements.
        How to compute its cost?
      */
unknown's avatar
unknown committed
6295
      outer_lookup_keys= 1;
6296 6297
    }

unknown's avatar
unknown committed
6298 6299 6300 6301
    /*
      B. Estimate the cost and number of records of the subquery both
      unmodified, and with injected IN->EXISTS predicates.
    */
unknown's avatar
unknown committed
6302
    inner_read_time_1= inner_join->best_read;
6303
    inner_record_count_1= inner_join->join_record_count;
6304

Sergey Petrunya's avatar
Sergey Petrunya committed
6305
    if (in_to_exists_where && const_tables != table_count)
6306 6307
    {
      /*
6308 6309
        Re-optimize and cost the subquery taking into account the IN-EXISTS
        conditions.
6310
      */
unknown's avatar
unknown committed
6311 6312
      reopt_result= reoptimize(in_to_exists_where, join_tables, &save_qep);
      if (reopt_result == REOPT_ERROR)
6313 6314
        return TRUE;

unknown's avatar
unknown committed
6315
      /* Get the cost of the modified IN-EXISTS plan. */
unknown's avatar
unknown committed
6316 6317
      inner_read_time_2= inner_join->best_read;

6318 6319 6320 6321 6322
    }
    else
    {
      /* Reoptimization would not produce any better plan. */
      inner_read_time_2= inner_read_time_1;
6323
    }
6324 6325

    /*
unknown's avatar
unknown committed
6326
      C. Compute execution costs.
6327
    */
unknown's avatar
unknown committed
6328
    /* C.1 Compute the cost of the materialization strategy. */
6329
    //uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list);
6330
    uint rowlen= get_tmp_table_rec_length(ref_ptrs, 
6331
                                          select_lex->item_list.elements);
unknown's avatar
unknown committed
6332 6333 6334
    /* The cost of writing one row into the temporary table. */
    double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1,
                                                rowlen);
6335
    /* The cost of a lookup into the unique index of the materialized table. */
unknown's avatar
unknown committed
6336 6337
    double lookup_cost= get_tmp_table_lookup_cost(thd, inner_record_count_1,
                                                  rowlen);
6338
    /*
unknown's avatar
unknown committed
6339 6340
      The cost of executing the subquery and storing its result in an indexed
      temporary table.
6341
    */
unknown's avatar
unknown committed
6342 6343 6344
    double materialization_cost= inner_read_time_1 +
                                 write_cost * inner_record_count_1;

6345
    materialize_strategy_cost= materialization_cost +
unknown's avatar
unknown committed
6346
                               outer_lookup_keys * lookup_cost;
6347

unknown's avatar
unknown committed
6348 6349
    /* C.2 Compute the cost of the IN=>EXISTS strategy. */
    in_exists_strategy_cost= outer_lookup_keys * inner_read_time_2;
6350

unknown's avatar
unknown committed
6351
    /* C.3 Compare the costs and choose the cheaper strategy. */
6352
    if (materialize_strategy_cost >= in_exists_strategy_cost)
unknown's avatar
unknown committed
6353
      in_subs->set_strategy(SUBS_IN_TO_EXISTS);
6354
    else
unknown's avatar
unknown committed
6355
      in_subs->set_strategy(SUBS_MATERIALIZATION);
unknown's avatar
unknown committed
6356 6357 6358 6359 6360 6361 6362 6363

    DBUG_PRINT("info",
               ("mat_strategy_cost: %.2f, mat_cost: %.2f, write_cost: %.2f, lookup_cost: %.2f",
                materialize_strategy_cost, materialization_cost, write_cost, lookup_cost));
    DBUG_PRINT("info",
               ("inx_strategy_cost: %.2f, inner_read_time_2: %.2f",
                in_exists_strategy_cost, inner_read_time_2));
    DBUG_PRINT("info",("outer_lookup_keys: %.2f", outer_lookup_keys));
6364
  }
6365 6366

  /*
6367
    If (1) materialization is a possible strategy based on semantic analysis
6368 6369 6370 6371 6372
    during the prepare phase, then if
      (2) it is more expensive than the IN->EXISTS transformation, and
      (3) it is not possible to create usable indexes for the materialization
          strategy,
      fall back to IN->EXISTS.
6373 6374
    otherwise
      use materialization.
6375
  */
unknown's avatar
unknown committed
6376
  if (in_subs->test_strategy(SUBS_MATERIALIZATION) &&
6377
      in_subs->setup_mat_engine())
6378 6379
  {
    /*
6380 6381 6382
      If materialization was the cheaper or the only user-selected strategy,
      but it is not possible to execute it due to limitations in the
      implementation, fall back to IN-TO-EXISTS.
6383
    */
unknown's avatar
unknown committed
6384
    in_subs->set_strategy(SUBS_IN_TO_EXISTS);
6385
  }
6386

unknown's avatar
unknown committed
6387
  if (in_subs->test_strategy(SUBS_MATERIALIZATION))
6388
  {
6389 6390
    /* Restore the original query plan used for materialization. */
    if (reopt_result == REOPT_NEW_PLAN)
unknown's avatar
unknown committed
6391
      restore_query_plan(&save_qep);
6392

6393 6394
    in_subs->unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
    select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
6395

6396 6397 6398 6399 6400 6401 6402 6403
    /*
      Reset the "LIMIT 1" set in Item_exists_subselect::fix_length_and_dec.
      TODO:
      Currently we set the subquery LIMIT to infinity, and this is correct
      because we forbid at parse time LIMIT inside IN subqueries (see
      Item_in_subselect::test_limit). However, once we allow this, here
      we should set the correct limit if given in the query.
    */
6404 6405
    in_subs->unit->global_parameters()->select_limit= NULL;
    in_subs->unit->set_limit(unit->global_parameters());
6406 6407 6408 6409 6410
    /*
      Set the limit of this JOIN object as well, because normally its being
      set in the beginning of JOIN::optimize, which was already done.
    */
    select_limit= in_subs->unit->select_limit_cnt;
6411
  }
unknown's avatar
unknown committed
6412
  else if (in_subs->test_strategy(SUBS_IN_TO_EXISTS))
6413
  {
unknown's avatar
unknown committed
6414
    if (reopt_result == REOPT_NONE && in_to_exists_where &&
Sergey Petrunya's avatar
Sergey Petrunya committed
6415
        const_tables != table_count)
6416
    {
6417
      /*
unknown's avatar
unknown committed
6418 6419 6420
        The subquery was not reoptimized with the newly injected IN-EXISTS
        conditions either because the user allowed only the IN-EXISTS strategy,
        or because materialization was not possible based on semantic analysis.
6421
      */
unknown's avatar
unknown committed
6422 6423
      reopt_result= reoptimize(in_to_exists_where, join_tables, NULL);
      if (reopt_result == REOPT_ERROR)
6424 6425 6426 6427 6428
        return TRUE;
    }

    if (in_subs->inject_in_to_exists_cond(this))
      return TRUE;
6429
    /*
unknown's avatar
unknown committed
6430 6431
      If the injected predicate is correlated the IN->EXISTS transformation
      make the subquery dependent.
6432
    */
unknown's avatar
unknown committed
6433 6434 6435 6436 6437 6438 6439 6440
    if ((in_to_exists_where &&
         in_to_exists_where->used_tables() & OUTER_REF_TABLE_BIT) ||
        (in_to_exists_having &&
         in_to_exists_having->used_tables() & OUTER_REF_TABLE_BIT))
    {
      in_subs->unit->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
      select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
    }
6441
    select_limit= 1;
6442 6443 6444 6445
  }
  else
    DBUG_ASSERT(FALSE);

6446
  return FALSE;
6447
}
6448 6449 6450 6451 6452 6453 6454 6455 6456 6457 6458 6459 6460


/**
  Choose a query plan for a table-less subquery.

  @notes

  @retval FALSE     success.
  @retval TRUE      error occurred.
*/

bool JOIN::choose_tableless_subquery_plan()
{
Sergey Petrunya's avatar
Sergey Petrunya committed
6461
  DBUG_ASSERT(!tables_list || !table_count);
6462
  if (unit->item)
6463
  {
6464 6465
    DBUG_ASSERT(unit->item->type() == Item::SUBSELECT_ITEM);
    Item_subselect *subs_predicate= unit->item;
6466 6467 6468 6469

    /*
      If the optimizer determined that his query has an empty result,
      in most cases the subquery predicate is a known constant value -
unknown's avatar
unknown committed
6470 6471
      either of TRUE, FALSE or NULL. The implementation of
      Item_subselect::no_rows_in_result() determines which one.
6472 6473 6474 6475 6476 6477 6478
    */
    if (zero_result_cause)
    {
      if (!implicit_grouping)
      {
        /*
          Both group by queries and non-group by queries without aggregate
unknown's avatar
unknown committed
6479 6480
          functions produce empty subquery result. There is no need to further
          rewrite the subquery because it will not be executed at all.
6481
        */
6482
        exec_const_cond= 0;
6483 6484 6485
        return FALSE;
      }

unknown's avatar
unknown committed
6486
      /* @todo
6487 6488 6489 6490 6491 6492 6493
         A further optimization is possible when a non-group query with
         MIN/MAX/COUNT is optimized by opt_sum_query. Then, if there are
         only MIN/MAX functions over an empty result set, the subquery
         result is a NULL value/row, thus the value of subs_predicate is
         NULL.
      */
    }
6494 6495 6496 6497 6498 6499 6500 6501 6502 6503
    
    /*
      For IN subqueries, use IN->EXISTS transfomation, unless the subquery 
      has been converted to a JTBM semi-join. In that case, just leave
      everything as-is, setup_jtbm_semi_joins() has special handling for cases
      like this.
    */
    if (subs_predicate->is_in_predicate() && 
        !(subs_predicate->substype() == Item_subselect::IN_SUBS && 
          ((Item_in_subselect*)subs_predicate)->is_jtbm_merged))
6504 6505 6506
    {
      Item_in_subselect *in_subs;
      in_subs= (Item_in_subselect*) subs_predicate;
unknown's avatar
unknown committed
6507
      in_subs->set_strategy(SUBS_IN_TO_EXISTS);
6508 6509 6510 6511 6512 6513
      if (in_subs->create_in_to_exists_cond(this) ||
          in_subs->inject_in_to_exists_cond(this))
        return TRUE;
      tmp_having= having;
    }
  }
6514
  exec_const_cond= zero_result_cause ? 0 : conds;
6515 6516
  return FALSE;
}
6517 6518


6519
bool Item::pushable_equality_checker_for_subquery(uchar *arg)
6520
{
6521 6522 6523
  return
  get_corresponding_field_pair(this,
                            ((Item_in_subselect *)arg)->corresponding_fields);
6524 6525 6526
}


6527 6528 6529 6530 6531 6532 6533
/*
  Checks if 'item' or some item equal to it is equal to the field from
  some Field_pair of 'pair_list' and returns matching Field_pair or
  NULL if the matching Field_pair wasn't found.
*/

Field_pair *find_matching_field_pair(Item *item, List<Field_pair> pair_list)
6534
{
6535 6536 6537 6538 6539
  Field_pair *field_pair= get_corresponding_field_pair(item, pair_list);
  if (field_pair)
    return field_pair;

  Item_equal *item_equal= item->get_item_equal();
6540 6541 6542 6543 6544 6545 6546 6547
  if (item_equal)
  {
    Item_equal_fields_iterator it(*item_equal);
    Item *equal_item;
    while ((equal_item= it++))
    {
      if (equal_item->const_item())
        continue;
6548 6549 6550
      field_pair= get_corresponding_field_pair(equal_item, pair_list);
      if (field_pair)
        return field_pair;
6551 6552
    }
  }
6553 6554 6555 6556 6557 6558 6559 6560
  return NULL;
}


bool Item_field::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
{
  if (find_matching_field_pair(((Item *) this), subq_pred->corresponding_fields))
    return true;
6561 6562 6563 6564 6565 6566 6567 6568 6569
  return false;
}


bool Item_direct_view_ref::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
{
  if (item_equal)
  {
    DBUG_ASSERT(real_item()->type() == Item::FIELD_ITEM);
6570
    if (get_corresponding_field_pair(((Item *)this), subq_pred->corresponding_fields))
6571 6572 6573 6574 6575 6576 6577 6578 6579 6580 6581 6582 6583 6584 6585 6586 6587 6588 6589 6590 6591 6592 6593 6594 6595 6596 6597 6598 6599 6600 6601 6602 6603 6604 6605 6606 6607 6608 6609 6610 6611 6612 6613 6614 6615 6616 6617 6618 6619 6620 6621 6622 6623 6624 6625 6626 6627 6628 6629 6630 6631 6632 6633
      return true;
  }
  return (*ref)->excl_dep_on_in_subq_left_part(subq_pred);
}


bool Item_equal::excl_dep_on_in_subq_left_part(Item_in_subselect *subq_pred)
{
  Item *left_item = get_const();
  Item_equal_fields_iterator it(*this);
  Item *item;
  if (!left_item)
  {
    while ((item=it++))
    {
      if (item->excl_dep_on_in_subq_left_part(subq_pred))
      {
        left_item= item;
        break;
      }
    }
  }
  if (!left_item)
    return false;
  while ((item=it++))
  {
    if (item->excl_dep_on_in_subq_left_part(subq_pred))
      return true;
  }
  return false;
}


/**
  @brief
    Get corresponding item from the select of the right part of IN subquery

  @param thd        the thread handle
  @param item       the item from the left part of subq_pred for which
                    corresponding item should be found
  @param subq_pred  the IN subquery predicate

  @details
    This method looks through the fields of the select of the right part of
    the IN subquery predicate subq_pred trying to find the corresponding
    item 'new_item' for item. If item has equal items it looks through
    the fields of the select of the right part of subq_pred for each equal
    item trying to find the corresponding item.
    The method assumes that the given item is either a field item or
    a reference to a field item.

  @retval <item*>  reference to the corresponding item
  @retval NULL     if item was not found
*/

static
Item *get_corresponding_item(THD *thd, Item *item,
                             Item_in_subselect *subq_pred)
{
  DBUG_ASSERT(item->type() == Item::FIELD_ITEM ||
              (item->type() == Item::REF_ITEM &&
              ((Item_ref *) item)->ref_type() == Item_ref::VIEW_REF));

6634
  Field_pair *field_pair;
6635 6636 6637 6638 6639 6640 6641 6642
  Item_equal *item_equal= item->get_item_equal();

  if (item_equal)
  {
    Item_equal_fields_iterator it(*item_equal);
    Item *equal_item;
    while ((equal_item= it++))
    {
6643 6644 6645 6646
      field_pair=
        get_corresponding_field_pair(equal_item, subq_pred->corresponding_fields);
      if (field_pair)
        return field_pair->corresponding_item;
6647 6648 6649
    }
  }
  else
6650 6651 6652 6653 6654 6655 6656
  {
    field_pair=
        get_corresponding_field_pair(item, subq_pred->corresponding_fields);
    if (field_pair)
        return field_pair->corresponding_item;
  }
  return NULL;
6657 6658 6659 6660 6661 6662 6663 6664 6665 6666 6667 6668 6669 6670 6671 6672 6673 6674 6675 6676 6677 6678 6679 6680 6681 6682 6683 6684 6685 6686 6687 6688 6689 6690 6691 6692 6693 6694 6695 6696 6697 6698 6699 6700 6701 6702 6703 6704 6705 6706 6707 6708 6709 6710 6711 6712 6713 6714 6715 6716 6717 6718 6719 6720 6721 6722 6723 6724 6725 6726 6727 6728 6729 6730 6731 6732 6733 6734 6735 6736 6737 6738 6739 6740 6741 6742 6743 6744 6745 6746 6747 6748 6749 6750 6751 6752 6753 6754 6755 6756 6757 6758 6759 6760 6761 6762 6763 6764 6765 6766 6767 6768 6769 6770 6771 6772 6773 6774 6775 6776 6777 6778 6779 6780 6781 6782 6783 6784 6785 6786 6787 6788 6789 6790 6791 6792 6793 6794 6795 6796 6797 6798 6799 6800 6801 6802 6803 6804 6805 6806 6807 6808 6809 6810 6811 6812 6813 6814 6815 6816 6817 6818 6819 6820 6821 6822 6823 6824 6825 6826 6827 6828 6829 6830 6831 6832 6833 6834 6835 6836 6837 6838 6839 6840 6841 6842 6843 6844 6845 6846 6847 6848 6849 6850 6851 6852 6853 6854 6855 6856 6857 6858 6859 6860 6861 6862 6863 6864 6865 6866 6867 6868 6869 6870 6871 6872 6873 6874 6875 6876 6877 6878 6879 6880 6881 6882 6883 6884 6885 6886 6887 6888 6889 6890 6891 6892 6893 6894 6895 6896 6897 6898 6899 6900 6901 6902 6903 6904 6905 6906 6907 6908 6909 6910 6911 6912 6913 6914 6915 6916 6917 6918 6919 6920 6921 6922 6923 6924 6925 6926 6927 6928 6929 6930 6931
}


Item *Item_field::in_subq_field_transformer_for_where(THD *thd, uchar *arg)
{
  Item_in_subselect *subq_pred= (Item_in_subselect *)arg;
  Item *producing_item= get_corresponding_item(thd, this, subq_pred);
  if (producing_item)
    return producing_item->build_clone(thd);
  return this;
}


Item *Item_direct_view_ref::in_subq_field_transformer_for_where(THD *thd,
                                                                uchar *arg)
{
  if (item_equal)
  {
    Item_in_subselect *subq_pred= (Item_in_subselect *)arg;
    Item *producing_item= get_corresponding_item(thd, this, subq_pred);
    DBUG_ASSERT (producing_item != NULL);
    return producing_item->build_clone(thd);
  }
  return this;
}


/**
  @brief
    Transforms item so it can be pushed into the IN subquery HAVING clause

  @param thd        the thread handle
  @param in_item    the item for which pushable item should be created
  @param subq_pred  the IN subquery predicate

  @details
    This method finds for in_item that is a field from the left part of the
    IN subquery predicate subq_pred its corresponding item from the right part
    of subq_pred.
    If corresponding item is found, a shell for this item is created.
    This shell can be pushed into the HAVING part of subq_pred select.

  @retval <item*>  reference to the created corresponding item shell for in_item
  @retval NULL     if mistake occurs
*/

static Item*
get_corresponding_item_for_in_subq_having(THD *thd, Item *in_item,
                                          Item_in_subselect *subq_pred)
{
  Item *new_item= get_corresponding_item(thd, in_item, subq_pred);

  if (new_item)
  {
    Item_ref *ref=
      new (thd->mem_root) Item_ref(thd,
                                   &subq_pred->unit->first_select()->context,
                                   NullS, NullS,
                                   &new_item->name);
    if (!ref)
      DBUG_ASSERT(0);
    return ref;
  }
  return new_item;
}


Item *Item_field::in_subq_field_transformer_for_having(THD *thd, uchar *arg)
{
  return get_corresponding_item_for_in_subq_having(thd, this,
                                                   (Item_in_subselect *)arg);
}


Item *Item_direct_view_ref::in_subq_field_transformer_for_having(THD *thd,
                                                                 uchar *arg)
{
  if (!item_equal)
    return this;
  else
  {
    Item *new_item= get_corresponding_item_for_in_subq_having(thd, this,
                                                    (Item_in_subselect *)arg);
    if (!new_item)
      return this;
    return new_item;
  }
}


/**
  @brief
    Find fields that are used in the GROUP BY of the select

  @param thd            the thread handle
  @param sel            the select of the IN subquery predicate
  @param fields         fields of the left part of the IN subquery predicate
  @param grouping_list  GROUP BY clause

  @details
    This method traverses fields which are used in the GROUP BY of
    sel and saves them with their corresponding items from fields.
*/

bool grouping_fields_in_the_in_subq_left_part(THD *thd,
                                              st_select_lex *sel,
                                              List<Field_pair> *fields,
                                              ORDER *grouping_list)
{
  DBUG_ENTER("grouping_fields_in_the_in_subq_left_part");
  sel->grouping_tmp_fields.empty();
  List_iterator<Field_pair> it(*fields);
  Field_pair *item;
  while ((item= it++))
  {
    for (ORDER *ord= grouping_list; ord; ord= ord->next)
    {
      if ((*ord->item)->eq(item->corresponding_item, 0))
      {
        if (sel->grouping_tmp_fields.push_back(item, thd->mem_root))
          DBUG_RETURN(TRUE);
      }
    }
  }
  DBUG_RETURN(FALSE);
}


/**
  @brief
    Extract condition that can be pushed into select of this IN subquery

  @param thd   the thread handle
  @param cond  current condition

  @details
    This function builds the most restrictive condition depending only on
    the list of fields of the left part of this IN subquery predicate
    (directly or indirectly through equality) that can be extracted from the
    given condition cond and pushes it into this IN subquery.

    Example of the transformation:

    SELECT * FROM t1
    WHERE a>3 AND b>10 AND
          (a,b) IN (SELECT x,MAX(y) FROM t2 GROUP BY x);

    =>

    SELECT * FROM t1
    WHERE a>3 AND b>10 AND
          (a,b) IN (SELECT x,max(y)
                    FROM t2
                    WHERE x>3
                    GROUP BY x
                    HAVING MAX(y)>10);


    In details:
    1. Check what pushable formula can be extracted from cond
    2. Build a clone PC of the formula that can be extracted
       (the clone is built only if the extracted formula is a AND subformula
        of cond or conjunction of such subformulas)
    3. If there is no HAVING clause prepare PC to be conjuncted with
       WHERE clause of this subquery. Otherwise do 4-7.
    4. Check what formula PC_where can be extracted from PC to be pushed
       into the WHERE clause of the subquery
    5. Build PC_where and if PC_where is a conjunct(s) of PC remove it from PC
       getting PC_having
    6. Prepare PC_where to be conjuncted with the WHERE clause of
       the IN subquery
    7. Prepare PC_having to be conjuncted with the HAVING clause of
       the IN subquery

  @note
    This method is similar to pushdown_cond_for_derived()

  @retval TRUE   if an error occurs
  @retval FALSE  otherwise
*/

bool Item_in_subselect::pushdown_cond_for_in_subquery(THD *thd, Item *cond)
{
  DBUG_ENTER("Item_in_subselect::pushdown_cond_for_in_subquery");
  Item *remaining_cond= NULL;

  if (!cond)
    DBUG_RETURN(FALSE);

  st_select_lex *sel = unit->first_select();

  if (is_jtbm_const_tab)
    DBUG_RETURN(FALSE);

  if (!sel->cond_pushdown_is_allowed())
    DBUG_RETURN(FALSE);

  /*
    Create a list of Field_pair items for this IN subquery.
    It consists of the pairs of fields from the left part of this IN subquery
    predicate 'left_part' and the respective fields from the select of the
    right part of the IN subquery 'sel' (the field from left_part with the
    corresponding field from the sel projection list).
    Attach this list to the IN subquery.
  */
  corresponding_fields.empty();
  List_iterator_fast<Item> it(sel->join->fields_list);
  Item *item;
  for (uint i= 0; i < left_expr->cols(); i++)
  {
    item= it++;
    Item *elem= left_expr->element_index(i);

    if (elem->real_item()->type() != Item::FIELD_ITEM)
      continue;

    if (corresponding_fields.push_back(
          new Field_pair(((Item_field *)(elem->real_item()))->field,
                                         item)))
      DBUG_RETURN(TRUE);
  }

  /* 1. Check what pushable formula can be extracted from cond */
  Item *extracted_cond;
  cond->check_pushable_cond(&Item::pushable_cond_checker_for_subquery,
                            (uchar *)this);
  /* 2. Build a clone PC of the formula that can be extracted */
  extracted_cond=
    cond->build_pushable_cond(thd,
                              &Item::pushable_equality_checker_for_subquery,
                              (uchar *)this);
  /* Nothing to push */
  if (!extracted_cond)
  {
    DBUG_RETURN(FALSE);
  }

  /* Collect fields that are used in the GROUP BY of sel */
  st_select_lex *save_curr_select= thd->lex->current_select;
  if (sel->have_window_funcs())
  {
    if (sel->group_list.first || sel->join->implicit_grouping)
      goto exit;
    ORDER *common_partition_fields=
       sel->find_common_window_func_partition_fields(thd);
    if (!common_partition_fields)
      goto exit;

    if (grouping_fields_in_the_in_subq_left_part(thd, sel, &corresponding_fields,
                                                 common_partition_fields))
      DBUG_RETURN(TRUE);
  }
  else if (grouping_fields_in_the_in_subq_left_part(thd, sel,
                                                    &corresponding_fields,
                                                    sel->group_list.first))
    DBUG_RETURN(TRUE);

  /* Do 4-6 */
  sel->pushdown_cond_into_where_clause(thd, extracted_cond,
                                    &remaining_cond,
                                    &Item::in_subq_field_transformer_for_where,
                                    (uchar *) this);
  if (!remaining_cond)
    goto exit;
  /*
    7. Prepare PC_having to be conjuncted with the HAVING clause of
       the IN subquery
  */
  remaining_cond=
    remaining_cond->transform(thd,
                              &Item::in_subq_field_transformer_for_having,
                              (uchar *)this);
  if (!remaining_cond)
    goto exit;

6932
  sel->mark_or_conds_to_avoid_pushdown(remaining_cond);
6933 6934 6935 6936 6937

exit:
  thd->lex->current_select= save_curr_select;
  DBUG_RETURN(FALSE);
}