item_subselect.cc 195 KB
Newer Older
1 2
/* Copyright (c) 2002, 2016, Oracle and/or its affiliates.
   Copyright (c) 2010, 2016, MariaDB
3 4 5

   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
unknown's avatar
unknown committed
6
   the Free Software Foundation; version 2 of the License.
7 8 9 10 11 12 13 14

   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
15
   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */
16

unknown's avatar
unknown committed
17 18 19 20 21
/**
  @file

  @brief
  subselect Item
22

unknown's avatar
unknown committed
23 24 25
  @todo
    - add function from mysql_select that use JOIN* as parameter to JOIN
    methods (sql_select.h/sql_select.cc)
26 27
*/

28
#ifdef USE_PRAGMA_IMPLEMENTATION
29 30 31
#pragma implementation				// gcc: Class implementation
#endif

32
#include "mariadb.h"
33 34 35 36 37 38 39 40
#include "sql_priv.h"
/*
  It is necessary to include set_var.h instead of item.h because there
  are dependencies on include order for set_var.h and item.h. This
  will be resolved later.
*/
#include "sql_class.h"                          // set_var.h: THD
#include "set_var.h"
41
#include "sql_select.h"
42
#include "sql_parse.h"                          // check_stack_overrun
Igor Babaev's avatar
Igor Babaev committed
43
#include "sql_cte.h"
44
#include "sql_test.h"
45

Sergey Petrunya's avatar
Sergey Petrunya committed
46 47
double get_post_group_estimate(JOIN* join, double join_op_rows);

48
LEX_CSTRING exists_outer_expr_name= { STRING_WITH_LEN("<exists outer expr>") };
unknown's avatar
unknown committed
49 50

int check_and_do_in_subquery_rewrites(JOIN *join);
unknown's avatar
unknown committed
51

52 53 54
Item_subselect::Item_subselect(THD *thd_arg):
  Item_result_field(thd_arg), Used_tables_and_const_cache(),
  value_assigned(0), own_engine(0), thd(0), old_engine(0),
55
  have_to_be_excluded(0),
56
  inside_first_fix_fields(0), done_first_fix_fields(FALSE), 
unknown's avatar
unknown committed
57
  expr_cache(0), forced_const(FALSE), substitution(0), engine(0), eliminated(FALSE),
58
  changed(0), is_correlated(FALSE), with_recursive_reference(0)
59
{
60
  DBUG_ENTER("Item_subselect::Item_subselect");
61
  DBUG_PRINT("enter", ("this: %p", this));
62 63
  sortbuffer.str= 0;

unknown's avatar
unknown committed
64 65 66
#ifndef DBUG_OFF
  exec_counter= 0;
#endif
67
  reset();
68
  /*
69
    Item value is NULL if select_result_interceptor didn't change this value
70 71
    (i.e. some rows will be found returned)
  */
72
  null_value= TRUE;
73
  DBUG_VOID_RETURN;
74 75
}

76

77
void Item_subselect::init(st_select_lex *select_lex,
78
			  select_result_interceptor *result)
79
{
80 81 82 83
  /*
    Please see Item_singlerow_subselect::invalidate_and_restore_select_lex(),
    which depends on alterations to the parse tree implemented here.
  */
84 85

  DBUG_ENTER("Item_subselect::init");
86 87
  DBUG_PRINT("enter", ("select_lex: %p  this: %p",
                       select_lex, this));
88 89 90

  select_lex->parent_lex->relink_hack(select_lex);

unknown's avatar
unknown committed
91
  unit= select_lex->master_unit();
unknown's avatar
unknown committed
92

93 94 95
  if (unit->item)
  {
    engine= unit->item->engine;
96
    parsing_place= unit->item->parsing_place;
unknown's avatar
unknown committed
97 98 99 100 101 102 103 104 105 106 107 108 109
    if (unit->item->substype() == EXISTS_SUBS &&
        ((Item_exists_subselect *)unit->item)->exists_transformed)
    {
      /* it is permanent transformation of EXISTS to IN */
      unit->item= this;
      engine->change_result(this, result, FALSE);
    }
    else
    {
      /*
        Item can be changed in JOIN::prepare while engine in JOIN::optimize
        => we do not copy old_engine here
      */
110
      unit->thd->change_item_tree((Item**)&unit->item, this);
unknown's avatar
unknown committed
111 112
      engine->change_result(this, result, TRUE);
    }
113
  }
unknown's avatar
unknown committed
114
  else
115
  {
unknown's avatar
unknown committed
116 117 118 119 120 121 122 123
    SELECT_LEX *outer_select= unit->outer_select();
    /*
      do not take into account expression inside aggregate functions because
      they can access original table fields
    */
    parsing_place= (outer_select->in_sum_expr ?
                    NO_MATTER :
                    outer_select->parsing_place);
Galina Shalygina's avatar
Galina Shalygina committed
124
    if (unit->is_unit_op() && unit->first_select()->next_select())
125
      engine= new subselect_union_engine(unit, result, this);
126
    else
127
      engine= new subselect_single_select_engine(select_lex, result, this);
128
  }
129
  DBUG_PRINT("info", ("engine: %p", engine));
130 131 132
  DBUG_VOID_RETURN;
}

133 134 135 136 137 138
st_select_lex *
Item_subselect::get_select_lex()
{
  return unit->first_select();
}

unknown's avatar
unknown committed
139 140
void Item_subselect::cleanup()
{
unknown's avatar
unknown committed
141
  DBUG_ENTER("Item_subselect::cleanup");
unknown's avatar
unknown committed
142
  Item_result_field::cleanup();
unknown's avatar
unknown committed
143 144
  if (old_engine)
  {
145 146
    if (engine)
      engine->cleanup();
unknown's avatar
unknown committed
147 148 149
    engine= old_engine;
    old_engine= 0;
  }
150 151
  if (engine)
    engine->cleanup();
unknown's avatar
unknown committed
152
  reset();
153 154
  filesort_buffer.free_sort_buffer();
  my_free(sortbuffer.str);
Marko Mäkelä's avatar
Marko Mäkelä committed
155
  sortbuffer.str= 0;
156

unknown's avatar
unknown committed
157
  value_assigned= 0;
158
  expr_cache= 0;
159
  forced_const= FALSE;
unknown's avatar
unknown committed
160 161 162 163
  DBUG_PRINT("info", ("exec_counter: %d", exec_counter));
#ifndef DBUG_OFF
  exec_counter= 0;
#endif
unknown's avatar
unknown committed
164 165 166
  DBUG_VOID_RETURN;
}

167

unknown's avatar
unknown committed
168 169 170 171 172 173
void Item_singlerow_subselect::cleanup()
{
  DBUG_ENTER("Item_singlerow_subselect::cleanup");
  value= 0; row= 0;
  Item_subselect::cleanup();
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
174
}
175

176 177 178 179 180 181 182 183 184 185

void Item_in_subselect::cleanup()
{
  DBUG_ENTER("Item_in_subselect::cleanup");
  if (left_expr_cache)
  {
    left_expr_cache->delete_elements();
    delete left_expr_cache;
    left_expr_cache= NULL;
  }
unknown's avatar
unknown committed
186 187 188 189
  /*
    TODO: This breaks the commented assert in add_strategy().
    in_strategy&= ~SUBS_STRATEGY_CHOSEN;
  */
190
  first_execution= TRUE;
191
  pushed_cond_guards= NULL;
192 193 194 195
  Item_subselect::cleanup();
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
196 197 198 199 200 201 202 203 204 205

void Item_allany_subselect::cleanup()
{
  /*
    The MAX/MIN transformation through injection is reverted through the
    change_item_tree() mechanism. Revert the select_lex object of the
    query to its initial state.
  */
  for (SELECT_LEX *sl= unit->first_select();
       sl; sl= sl->next_select())
unknown's avatar
unknown committed
206
    if (test_set_strategy(SUBS_MAXMIN_INJECTED))
unknown's avatar
unknown committed
207 208 209 210 211
      sl->with_sum_func= false;
  Item_in_subselect::cleanup();
}


unknown's avatar
unknown committed
212 213
Item_subselect::~Item_subselect()
{
214
  DBUG_ENTER("Item_subselect::~Item_subselect");
215
  DBUG_PRINT("enter", ("this: %p", this));
216
  if (own_engine)
217 218
    delete engine;
  else
219 220
    if (engine)  // can be empty in case of EOM
      engine->cleanup();
221
  engine= NULL;
222
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
223 224
}

unknown's avatar
unknown committed
225
bool
226
Item_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
227 228
{
  DBUG_ENTER("Item_subselect::select_transformer");
229
  DBUG_ASSERT(thd == join->thd);
unknown's avatar
unknown committed
230
  DBUG_RETURN(false);
unknown's avatar
unknown committed
231 232 233
}


234
bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
235
{
unknown's avatar
unknown committed
236
  char const *save_where= thd_param->where;
unknown's avatar
unknown committed
237
  uint8 uncacheable;
unknown's avatar
unknown committed
238
  bool res;
unknown's avatar
unknown committed
239

240 241 242 243
  thd= thd_param;

  DBUG_ASSERT(unit->thd == thd);

244 245 246 247 248 249 250 251
  {
    SELECT_LEX *upper= unit->outer_select();
    if (upper->parsing_place == IN_HAVING)
      upper->subquery_in_having= 1;
    /* The subquery is an expression cache candidate */
    upper->expr_cache_may_be_used[upper->parsing_place]= TRUE;
  }

252
  status_var_increment(thd_param->status_var.feature_subquery);
253

254
  DBUG_ASSERT(fixed == 0);
Igor Babaev's avatar
Igor Babaev committed
255
  engine->set_thd((thd= thd_param));
256 257 258 259
  if (!done_first_fix_fields)
  {
    done_first_fix_fields= TRUE;
    inside_first_fix_fields= TRUE;
260 261 262 263 264
    upper_refs.empty();
    /*
      psergey-todo: remove _first_fix_fields calls, we need changes on every
      execution
    */
265 266
  }

Sergey Petrunia's avatar
Sergey Petrunia committed
267
  eliminated= FALSE;
268
  parent_select= thd_param->lex->current_select;
269

270
  if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
unknown's avatar
unknown committed
271
    return TRUE;
Sergey Petrunia's avatar
Sergey Petrunia committed
272
  
273
  for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
274
  {
275 276
    if (sl->tvc)
    {
Galina Shalygina's avatar
Galina Shalygina committed
277
      wrap_tvc_in_derived_table(thd, sl);
278
    }
279
  }
280
  
281
  if (!(res= engine->prepare(thd)))
unknown's avatar
unknown committed
282
  {
283 284
    // all transformation is done (used by prepared statements)
    changed= 1;
285
    inside_first_fix_fields= FALSE;
286 287 288 289 290 291 292

    /*
      Substitute the current item with an Item_in_optimizer that was
      created by Item_in_subselect::select_in_like_transformer and
      call fix_fields for the substituted item which in turn calls
      engine->prepare for the subquery predicate.
    */
293 294
    if (substitution)
    {
295 296 297 298
      /*
        If the top item of the WHERE/HAVING condition changed,
        set correct WHERE/HAVING for PS.
      */
unknown's avatar
unknown committed
299
      if (unit->outer_select()->where == (*ref))
unknown's avatar
unknown committed
300
        unit->outer_select()->where= substitution;
301
      else if (unit->outer_select()->having == (*ref))
unknown's avatar
unknown committed
302
        unit->outer_select()->having= substitution;
unknown's avatar
unknown committed
303

304 305 306 307 308
      (*ref)= substitution;
      substitution->name= name;
      if (have_to_be_excluded)
	engine->exclude();
      substitution= 0;
309
      thd->where= "checking transformed subquery";
310
      res= (*ref)->fix_fields_if_needed(thd, ref);
311
      goto end;
Sergey Petrunya's avatar
Sergey Petrunya committed
312

313
    }
unknown's avatar
unknown committed
314 315
    // Is it one field subselect?
    if (engine->cols() > max_columns)
316
    {
unknown's avatar
unknown committed
317
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
318 319 320 321 322 323
      res= TRUE;
      goto end;
    }
    if (fix_length_and_dec())
    {
      res= TRUE;
324
      goto end;
unknown's avatar
unknown committed
325 326
    }
  }
unknown's avatar
unknown committed
327
  else
328
    goto end;
unknown's avatar
unknown committed
329
  
Igor Babaev's avatar
Igor Babaev committed
330 331
  if ((uncacheable= engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
      with_recursive_reference)
unknown's avatar
unknown committed
332 333
  {
    const_item_cache= 0;
334 335
    if (uncacheable & UNCACHEABLE_RAND)
      used_tables_cache|= RAND_TABLE_BIT;
unknown's avatar
unknown committed
336
  }
337
  fixed= 1;
unknown's avatar
unknown committed
338

339
end:
340
  done_first_fix_fields= FALSE;
Sergey Petrunya's avatar
Sergey Petrunya committed
341
  inside_first_fix_fields= FALSE;
342
  thd->where= save_where;
343 344 345
  return res;
}

346

347
bool Item_subselect::enumerate_field_refs_processor(void *arg)
Sergey Petrunia's avatar
Sergey Petrunia committed
348
{
349 350 351 352
  List_iterator<Ref_to_outside> it(upper_refs);
  Ref_to_outside *upper;
  
  while ((upper= it++))
Sergey Petrunia's avatar
Sergey Petrunia committed
353
  {
354 355
    if (upper->item &&
        upper->item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
Sergey Petrunia's avatar
Sergey Petrunia committed
356 357 358 359 360
      return TRUE;
  }
  return FALSE;
}

361
bool Item_subselect::mark_as_eliminated_processor(void *arg)
Sergey Petrunia's avatar
Sergey Petrunia committed
362 363 364 365 366
{
  eliminated= TRUE;
  return FALSE;
}

367

368 369 370 371 372 373 374 375 376 377
/**
  Remove a subselect item from its unit so that the unit no longer
  represents a subquery.

  @param arg  unused parameter

  @return
    FALSE to force the evaluation of the processor for the subsequent items.
*/

378
bool Item_subselect::eliminate_subselect_processor(void *arg)
379 380 381 382 383 384 385 386
{
  unit->item= NULL;
  unit->exclude_from_tree();
  eliminated= TRUE;
  return FALSE;
}


387
/**
388 389 390
  Adjust the master select of the subquery to be the fake_select which
  represents the whole UNION right above the subquery, instead of the
  last query of the UNION.
391 392 393 394 395

  @param arg  pointer to the fake select

  @return
    FALSE to force the evaluation of the processor for the subsequent items.
396 397
*/

398
bool Item_subselect::set_fake_select_as_master_processor(void *arg)
399 400 401
{
  SELECT_LEX *fake_select= (SELECT_LEX*) arg;
  /*
402 403
    Move the st_select_lex_unit of a subquery from a global ORDER BY clause to
    become a direct child of the fake_select of a UNION. In this way the
unknown's avatar
unknown committed
404 405 406 407
    ORDER BY that is applied to the temporary table that contains the result of
    the whole UNION, and all columns in the subquery are resolved against this
    table. The transformation is applied only for immediate child subqueries of
    a UNION query.
408 409 410 411
  */
  if (unit->outer_select()->master_unit()->fake_select_lex == fake_select)
  {
    /*
unknown's avatar
unknown committed
412 413
      Set the master of the subquery to be the fake select (i.e. the whole
      UNION), instead of the last query in the UNION.
414
    */
unknown's avatar
unknown committed
415 416
    fake_select->add_slave(unit);
    DBUG_ASSERT(unit->outer_select() == fake_select);
417 418 419 420
    /* Adjust the name resolution context hierarchy accordingly. */
    for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
      sl->context.outer_context= &(fake_select->context);
    /*
421 422
      Undo Item_subselect::eliminate_subselect_processor because at that phase
      we don't know yet that the ORDER clause will be moved to the fake select.
423 424 425 426
    */
    unit->item= this;
    eliminated= FALSE;
  }
427
  return FALSE;
428 429 430
}


431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447
bool Item_subselect::mark_as_dependent(THD *thd, st_select_lex *select, 
                                       Item *item)
{
  if (inside_first_fix_fields)
  {
    is_correlated= TRUE;
    Ref_to_outside *upper;
    if (!(upper= new (thd->stmt_arena->mem_root) Ref_to_outside()))
      return TRUE;
    upper->select= select;
    upper->item= item;
    if (upper_refs.push_back(upper, thd->stmt_arena->mem_root))
      return TRUE;
  }
  return FALSE;
}

448

449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470
/*
  Adjust attributes after our parent select has been merged into grandparent

  DESCRIPTION
    Subquery is a composite object which may be correlated, that is, it may
    have
    1. references to tables of the parent select (i.e. one that has the clause
      with the subquery predicate)
    2. references to tables of the grandparent select
    3. references to tables of further ancestors.
    
    Before the pullout, this item indicates:
    - #1 with table bits in used_tables()
    - #2 and #3 with OUTER_REF_TABLE_BIT.

    After parent has been merged with grandparent:
    - references to parent and grandparent tables should be indicated with 
      table bits.
    - references to greatgrandparent and further ancestors - with
      OUTER_REF_TABLE_BIT.
*/

471 472
void Item_subselect::fix_after_pullout(st_select_lex *new_parent,
                                       Item **ref, bool merge)
473 474 475 476 477
{
  recalc_used_tables(new_parent, TRUE);
  parent_select= new_parent;
}

478

479 480 481 482 483
class Field_fixer: public Field_enumerator
{
public:
  table_map used_tables; /* Collect used_tables here */
  st_select_lex *new_parent; /* Select we're in */
484
  virtual void visit_field(Item_field *item)
485 486 487 488 489
  {
    //for (TABLE_LIST *tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local)
    //{
    //  if (tbl->table == field->table)
    //  {
490
        used_tables|= item->field->table->map;
491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
    //    return;
    //  }
    //}
    //used_tables |= OUTER_REF_TABLE_BIT;
  }
};


/*
  Recalculate used_tables_cache 
*/

void Item_subselect::recalc_used_tables(st_select_lex *new_parent, 
                                        bool after_pullout)
{
unknown's avatar
unknown committed
506
  List_iterator_fast<Ref_to_outside> it(upper_refs);
507
  Ref_to_outside *upper;
Monty's avatar
Monty committed
508
  DBUG_ENTER("recalc_used_tables");
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546
  
  used_tables_cache= 0;
  while ((upper= it++))
  {
    bool found= FALSE;
    /*
      Check if
        1. the upper reference refers to the new immediate parent select, or
        2. one of the further ancestors.

      We rely on the fact that the tree of selects is modified by some kind of
      'flattening', i.e. a process where child selects are merged into their
      parents.
      The merged selects are removed from the select tree but keep pointers to
      their parents.
    */
    for (st_select_lex *sel= upper->select; sel; sel= sel->outer_select())
    {
      /* 
        If we've reached the new parent select by walking upwards from
        reference's original select, this means that the reference is now 
        referring to the direct parent:
      */
      if (sel == new_parent)
      {
        found= TRUE;
        /* 
          upper->item may be NULL when we've referred to a grouping function,
          in which case we don't care about what it's table_map really is,
          because item->with_sum_func==1 will ensure correct placement of the
          item.
        */
        if (upper->item)
        {
          // Now, iterate over fields and collect used_tables() attribute:
          Field_fixer fixer;
          fixer.used_tables= 0;
          fixer.new_parent= new_parent;
547
          upper->item->walk(&Item::enumerate_field_refs_processor, 0, &fixer);
548
          used_tables_cache |= fixer.used_tables;
Igor Babaev's avatar
Igor Babaev committed
549
          upper->item->walk(&Item::update_table_bitmaps_processor, FALSE, NULL);
Sergey Petrunya's avatar
Sergey Petrunya committed
550
/*
551 552 553
          if (after_pullout)
            upper->item->fix_after_pullout(new_parent, &(upper->item));
          upper->item->update_used_tables();
Sergey Petrunya's avatar
Sergey Petrunya committed
554
*/          
555 556 557 558 559 560 561 562 563 564 565 566
        }
      }
    }
    if (!found)
      used_tables_cache|= OUTER_REF_TABLE_BIT;
  }
  /* 
    Don't update const_tables_cache yet as we don't yet know which of the
    parent's tables are constant. Parent will call update_used_tables() after
    he has done const table detection, and that will be our chance to update
    const_tables_cache.
  */
Monty's avatar
Monty committed
567 568
  DBUG_PRINT("exit", ("used_tables_cache: %llx", used_tables_cache));
  DBUG_VOID_RETURN;
569 570
}

571 572 573 574 575 576 577 578 579 580 581 582 583 584 585

/**
  Determine if a subquery is expensive to execute during query optimization.

  @details The cost of execution of a subquery is estimated based on an
  estimate of the number of rows the subquery will access during execution.
  This measure is used instead of JOIN::read_time, because it is considered
  to be much more reliable than the cost estimate.

  @return true if the subquery is expensive
  @return false otherwise
*/
bool Item_subselect::is_expensive()
{
  double examined_rows= 0;
586 587 588 589 590 591 592 593 594 595 596 597 598 599 600
  bool all_are_simple= true;

  /* check extremely simple select */
  if (!unit->first_select()->next_select()) // no union
  {
    /*
      such single selects works even without optimization because
      can not makes loops
    */
    SELECT_LEX *sl= unit->first_select();
    JOIN *join = sl->join;
    if (join && !join->tables_list && !sl->first_inner_unit())
      return false;
  }

601 602 603 604

  for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
  {
    JOIN *cur_join= sl->join;
605 606

    /* not optimized subquery */
607
    if (!cur_join)
608 609 610 611 612 613
      return true;

    /*
      If the subquery is not optimised or in the process of optimization
      it supposed to be expensive
    */
614
    if (cur_join->optimization_state != JOIN::OPTIMIZATION_DONE)
615
      return true;
616

617 618 619
    if (!cur_join->tables_list && !sl->first_inner_unit())
      continue;

unknown's avatar
unknown committed
620 621 622 623
    /*
      Subqueries whose result is known after optimization are not expensive.
      Such subqueries have all tables optimized away, thus have no join plan.
    */
624
    if ((cur_join->zero_result_cause || !cur_join->tables_list))
625 626 627 628 629 630
      continue;

    /*
      This is not simple SELECT in union so we can not go by simple condition
    */
    all_are_simple= false;
unknown's avatar
unknown committed
631 632 633 634 635

    /*
      If a subquery is not optimized we cannot estimate its cost. A subquery is
      considered optimized if it has a join plan.
    */
636
    if (!cur_join->join_tab)
637 638 639 640 641 642 643 644 645 646 647 648 649 650
      return true;

    if (sl->first_inner_unit())
    {
      /*
        Subqueries that contain subqueries are considered expensive.
        @todo: accumulate the cost of subqueries.
      */
      return true;
    }

    examined_rows+= cur_join->get_examined_rows();
  }

651
  // here we are sure that subquery is optimized so thd is set
652 653
  return !all_are_simple &&
    (examined_rows > thd->variables.expensive_subquery_limit);
654 655 656
}


657
bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
658
                          void *argument)
659
{
660 661 662 663 664 665 666 667 668 669 670 671
  if (!(unit->uncacheable & ~UNCACHEABLE_DEPENDENT) && engine->is_executed() &&
      !unit->describe)
  {
    /*
      The subquery has already been executed (for real, it wasn't EXPLAIN's
      fake execution) so it should not matter what it has inside.
      
      The actual reason for not walking inside is that parts of the subquery
      (e.g. JTBM join nests and their IN-equality conditions may have been 
       invalidated by irreversible cleanups (those happen after an uncorrelated 
       subquery has been executed).
    */
672
    return (this->*processor)(argument);
673
  }
674 675 676 677 678 679 680 681 682 683 684 685 686 687

  if (walk_subquery)
  {
    for (SELECT_LEX *lex= unit->first_select(); lex; lex= lex->next_select())
    {
      List_iterator<Item> li(lex->item_list);
      Item *item;
      ORDER *order;

      if (lex->where && (lex->where)->walk(processor, walk_subquery, argument))
        return 1;
      if (lex->having && (lex->having)->walk(processor, walk_subquery,
                                             argument))
        return 1;
Sergey Petrunia's avatar
Sergey Petrunia committed
688
      /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */
689 690 691 692 693 694

      while ((item=li++))
      {
        if (item->walk(processor, walk_subquery, argument))
          return 1;
      }
695
      for (order= lex->order_list.first ; order; order= order->next)
696 697 698 699
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
700
      for (order= lex->group_list.first ; order; order= order->next)
701 702 703 704 705 706 707 708 709 710
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
    }
  }
  return (this->*processor)(argument);
}


711
bool Item_subselect::exec()
712
{
713 714
  subselect_engine *org_engine= engine;

715
  DBUG_ENTER("Item_subselect::exec");
716
  DBUG_ASSERT(fixed);
unknown's avatar
unknown committed
717

718 719 720 721
  /*
    Do not execute subselect in case of a fatal error
    or if the query has been killed.
  */
722
  if (unlikely(thd->is_error() || thd->killed))
723
    DBUG_RETURN(true);
724

Sergey Glukhov's avatar
Sergey Glukhov committed
725
  DBUG_ASSERT(!thd->lex->context_analysis_only);
726 727 728 729
  /*
    Simulate a failure in sub-query execution. Used to test e.g.
    out of memory or query being killed conditions.
  */
730
  DBUG_EXECUTE_IF("subselect_exec_fail", DBUG_RETURN(true););
unknown's avatar
unknown committed
731

732
  bool res= engine->exec();
unknown's avatar
unknown committed
733

unknown's avatar
unknown committed
734 735 736
#ifndef DBUG_OFF
  ++exec_counter;
#endif
737
  if (engine != org_engine)
738
  {
739 740 741 742 743 744
    /*
      If the subquery engine changed during execution due to lazy subquery
      optimization, or because the original engine found a more efficient other
      engine, re-execute the subquery with the new engine.
    */
    DBUG_RETURN(exec());
745
  }
746
  DBUG_RETURN(res);
747 748
}

749

unknown's avatar
unknown committed
750 751
void Item_subselect::get_cache_parameters(List<Item> &parameters)
{
unknown's avatar
unknown committed
752 753 754 755 756 757
  Collect_deps_prm prm= {&parameters,      // parameters
    unit->first_select()->nest_level_base, // nest_level_base
    0,                                     // count
    unit->first_select()->nest_level,      // nest_level
    TRUE                                   // collect
  };
758
  walk(&Item::collect_outer_ref_processor, TRUE, &prm);
unknown's avatar
unknown committed
759 760
}

Sergey Petrunya's avatar
Sergey Petrunya committed
761 762 763 764
int Item_in_subselect::optimize(double *out_rows, double *cost)
{
  int res;
  DBUG_ENTER("Item_in_subselect::optimize");
765
  DBUG_ASSERT(fixed);
Sergey Petrunya's avatar
Sergey Petrunya committed
766 767 768 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
  SELECT_LEX *save_select= thd->lex->current_select;
  JOIN *join= unit->first_select()->join;

  thd->lex->current_select= join->select_lex;
  if ((res= join->optimize()))
    DBUG_RETURN(res);

  /* Calculate #rows and cost of join execution */
  join->get_partial_cost_and_fanout(join->table_count - join->const_tables, 
                                    table_map(-1),
                                    cost, out_rows);

  /*
    Adjust join output cardinality. There can be these cases:
    - Have no GROUP BY and no aggregate funcs: we won't get into this 
      function because such join will be processed as a merged semi-join 
      (TODO: does it really mean we don't need to handle such cases here at 
       all? put ASSERT)
    - Have no GROUP BY but have aggregate funcs: output is 1 record.
    - Have GROUP BY and have (or not) aggregate funcs:  need to adjust output 
      cardinality.
  */
  thd->lex->current_select= save_select;
  if (!join->group_list && !join->group_optimized_away &&
      join->tmp_table_param.sum_func_count)
  {
    DBUG_PRINT("info",("Materialized join will have only 1 row (it has "
                       "aggregates but no GROUP BY"));
    *out_rows= 1;
  }
  
  /* Now with grouping */
798
  if (join->group_list_for_estimates)
Sergey Petrunya's avatar
Sergey Petrunya committed
799 800 801 802 803 804 805 806 807 808
  {
    DBUG_PRINT("info",("Materialized join has grouping, trying to estimate it"));
    double output_rows= get_post_group_estimate(join, *out_rows);
    DBUG_PRINT("info",("Got value of %g", output_rows));
    *out_rows= output_rows;
  }

  DBUG_RETURN(res);

}
Sergey Petrunya's avatar
Sergey Petrunya committed
809 810


unknown's avatar
unknown committed
811 812 813 814 815 816 817 818 819 820 821 822 823 824 825
/**
  Check if an expression cache is needed for this subquery

  @param thd             Thread handle

  @details
  The function checks whether a cache is needed for a subquery and whether
  the result of the subquery can be put in cache.

  @retval TRUE  cache is needed
  @retval FALSE otherwise
*/

bool Item_subselect::expr_cache_is_needed(THD *thd)
{
unknown's avatar
unknown committed
826
  return ((engine->uncacheable() & UNCACHEABLE_DEPENDENT) &&
unknown's avatar
unknown committed
827 828 829
          engine->cols() == 1 &&
          optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
830 831
                                     UNCACHEABLE_SIDEEFFECT)) &&
          !with_recursive_reference);
unknown's avatar
unknown committed
832 833 834
}


835 836 837 838 839 840 841 842 843 844 845 846 847
/**
  Check if the left IN argument contains NULL values.

  @retval TRUE  there are NULLs
  @retval FALSE otherwise
*/

inline bool Item_in_subselect::left_expr_has_null()
{
  return (*(optimizer->get_cache()))->null_value;
}


unknown's avatar
unknown committed
848 849 850 851 852 853 854 855 856 857 858
/**
  Check if an expression cache is needed for this subquery

  @param thd             Thread handle

  @details
  The function checks whether a cache is needed for a subquery and whether
  the result of the subquery can be put in cache.

  @note
  This method allows many columns in the subquery because it is supported by
859
  Item_in_optimizer and result of the IN subquery will be scalar in this
unknown's avatar
unknown committed
860 861 862 863 864 865 866 867
  case.

  @retval TRUE  cache is needed
  @retval FALSE otherwise
*/

bool Item_in_subselect::expr_cache_is_needed(THD *thd)
{
unknown's avatar
unknown committed
868
  return (optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
unknown's avatar
unknown committed
869
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
870 871
                                     UNCACHEABLE_SIDEEFFECT)) &&
          !with_recursive_reference);
unknown's avatar
unknown committed
872 873 874
}


875 876 877 878 879 880 881
/*
  Compute the IN predicate if the left operand's cache changed.
*/

bool Item_in_subselect::exec()
{
  DBUG_ENTER("Item_in_subselect::exec");
882
  DBUG_ASSERT(fixed);
883 884 885 886 887 888 889 890 891 892 893 894
  /*
    Initialize the cache of the left predicate operand. This has to be done as
    late as now, because Cached_item directly contains a resolved field (not
    an item, and in some cases (when temp tables are created), these fields
    end up pointing to the wrong field. One solution is to change Cached_item
    to not resolve its field upon creation, but to resolve it dynamically
    from a given Item_ref object.
    TODO: the cache should be applied conditionally based on:
    - rules - e.g. only if the left operand is known to be ordered, and/or
    - on a cost-based basis, that takes into account the cost of a cache
      lookup, the cache hit rate, and the savings per cache hit.
  */
unknown's avatar
unknown committed
895
  if (!left_expr_cache && (test_strategy(SUBS_MATERIALIZATION)))
896 897
    init_left_expr_cache();

898 899 900 901 902 903 904 905
  /*
    If the new left operand is already in the cache, reuse the old result.
    Use the cached result only if this is not the first execution of IN
    because the cache is not valid for the first execution.
  */
  if (!first_execution && left_expr_cache &&
      test_if_item_cache_changed(*left_expr_cache) < 0)
    DBUG_RETURN(FALSE);
906 907 908 909 910 911 912 913 914 915

  /*
    The exec() method below updates item::value, and item::null_value, thus if
    we don't call it, the next call to item::val_int() will return whatever
    result was computed by its previous call.
  */
  DBUG_RETURN(Item_subselect::exec());
}


916
Item::Type Item_subselect::type() const
917 918 919 920
{
  return SUBSELECT_ITEM;
}

unknown's avatar
unknown committed
921

922
bool Item_subselect::fix_length_and_dec()
923
{
924 925 926
  if (engine->fix_length_and_dec(0))
    return TRUE;
  return FALSE;
927
}
unknown's avatar
unknown committed
928

unknown's avatar
unknown committed
929

930
table_map Item_subselect::used_tables() const
unknown's avatar
unknown committed
931
{
932 933
  return (table_map) ((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN)? 
                      used_tables_cache : 0L);
unknown's avatar
unknown committed
934 935
}

unknown's avatar
merge  
unknown committed
936

937 938
bool Item_subselect::const_item() const
{
939
  DBUG_ASSERT(thd);
Igor Babaev's avatar
Igor Babaev committed
940
  return (thd->lex->context_analysis_only || with_recursive_reference ?
unknown's avatar
unknown committed
941 942
          FALSE :
          forced_const || const_item_cache);
943 944
}

945
Item *Item_subselect::get_tmp_table_item(THD *thd_arg)
unknown's avatar
unknown committed
946
{
947
  if (!Item_subselect::with_sum_func() && !const_item())
948
    return new (thd->mem_root) Item_temptable_field(thd_arg, result_field);
949
  return copy_or_same(thd_arg);
unknown's avatar
unknown committed
950
}
unknown's avatar
merge  
unknown committed
951

952 953
void Item_subselect::update_used_tables()
{
954
  if (!forced_const)
955
  {
956
    recalc_used_tables(parent_select, FALSE);
Igor Babaev's avatar
Igor Babaev committed
957
    if (!(engine->uncacheable() & ~UNCACHEABLE_EXPLAIN))
958 959
    {
      // did all used tables become static?
Igor Babaev's avatar
Igor Babaev committed
960 961
      if (!(used_tables_cache & ~engine->upper_select_const_tables()) &&
          ! with_recursive_reference)
962 963
        const_item_cache= 1;
    }
964 965 966
  }
}

unknown's avatar
unknown committed
967

968
void Item_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
969
{
970
  if (query_type & QT_ITEM_SUBSELECT_ID_ONLY)
971
  {
Michael Widenius's avatar
Michael Widenius committed
972
    str->append(STRING_WITH_LEN("(subquery#"));
973
    if (unit && unit->first_select())
974 975
    {
      char buf[64];
976
      ll2str(unit->first_select()->select_number, buf, 10, 0); 
977 978 979 980 981 982 983 984
      str->append(buf);
    }
    else
      str->append("NULL"); // TODO: what exactly does this mean?

    str->append(")");
    return;
  }
985 986 987 988 989 990 991 992
  if (engine)
  {
    str->append('(');
    engine->print(str, query_type);
    str->append(')');
  }
  else
    str->append("(...)");
unknown's avatar
unknown committed
993 994 995
}


996 997
Item_singlerow_subselect::Item_singlerow_subselect(THD *thd, st_select_lex *select_lex):
  Item_subselect(thd), value(0)
unknown's avatar
unknown committed
998
{
unknown's avatar
unknown committed
999
  DBUG_ENTER("Item_singlerow_subselect::Item_singlerow_subselect");
1000
  init(select_lex, new (thd->mem_root) select_singlerow_subselect(thd, this));
unknown's avatar
unknown committed
1001
  maybe_null= 1;
1002
  max_columns= UINT_MAX;
unknown's avatar
unknown committed
1003
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
1004 1005
}

1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
st_select_lex *
Item_singlerow_subselect::invalidate_and_restore_select_lex()
{
  DBUG_ENTER("Item_singlerow_subselect::invalidate_and_restore_select_lex");
  st_select_lex *result= get_select_lex();

  DBUG_ASSERT(result);

  /*
    This code restore the parse tree in it's state before the execution of
    Item_singlerow_subselect::Item_singlerow_subselect(),
    and in particular decouples this object from the SELECT_LEX,
    so that the SELECT_LEX can be used with a different flavor
    or Item_subselect instead, as part of query rewriting.
  */
  unit->item= NULL;

  DBUG_RETURN(result);
}

1026
Item_maxmin_subselect::Item_maxmin_subselect(THD *thd,
unknown's avatar
unknown committed
1027
                                             Item_subselect *parent,
1028
					     st_select_lex *select_lex,
1029 1030
					     bool max_arg):
  Item_singlerow_subselect(thd), was_values(TRUE)
1031 1032
{
  DBUG_ENTER("Item_maxmin_subselect::Item_maxmin_subselect");
unknown's avatar
unknown committed
1033
  max= max_arg;
unknown's avatar
unknown committed
1034
  init(select_lex,
1035
       new (thd->mem_root) select_max_min_finder_subselect(thd,
1036
             this, max_arg, parent->substype() == Item_subselect::ALL_SUBS));
1037 1038 1039
  max_columns= 1;
  maybe_null= 1;
  max_columns= 1;
1040 1041 1042 1043 1044 1045

  /*
    Following information was collected during performing fix_fields()
    of Items belonged to subquery, which will be not repeated
  */
  used_tables_cache= parent->get_used_tables_cache();
1046
  const_item_cache= parent->const_item();
1047

1048 1049 1050
  DBUG_VOID_RETURN;
}

1051 1052
void Item_maxmin_subselect::cleanup()
{
unknown's avatar
unknown committed
1053 1054 1055
  DBUG_ENTER("Item_maxmin_subselect::cleanup");
  Item_singlerow_subselect::cleanup();

1056
  /*
unknown's avatar
unknown committed
1057
    By default it is TRUE to avoid TRUE reporting by
1058 1059 1060
    Item_func_not_all/Item_func_nop_all if this item was never called.

    Engine exec() set it to FALSE by reset_value_registration() call.
unknown's avatar
unknown committed
1061 1062
    select_max_min_finder_subselect::send_data() set it back to TRUE if some
    value will be found.
1063 1064
  */
  was_values= TRUE;
unknown's avatar
unknown committed
1065
  DBUG_VOID_RETURN;
1066 1067 1068
}


1069
void Item_maxmin_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
1070
{
1071
  str->append(max?"<max>":"<min>", 5);
1072
  Item_singlerow_subselect::print(str, query_type);
unknown's avatar
unknown committed
1073 1074
}

1075

unknown's avatar
unknown committed
1076 1077
void Item_maxmin_subselect::no_rows_in_result()
{
unknown's avatar
unknown committed
1078 1079 1080 1081 1082 1083 1084 1085
  /*
    Subquery predicates outside of the SELECT list must be evaluated in order
    to possibly filter the special result row generated for implicit grouping
    if the subquery is in the HAVING clause.
    If the predicate is constant, we need its actual value in the only result
    row for queries with implicit grouping.
  */
  if (parsing_place != SELECT_LIST || const_item())
unknown's avatar
unknown committed
1086
    return;
1087
  value= (new (thd->mem_root) Item_null(thd))->get_cache(thd);
unknown's avatar
unknown committed
1088 1089 1090 1091 1092 1093
  null_value= 0;
  was_values= 0;
  make_const();
}


unknown's avatar
unknown committed
1094 1095
void Item_singlerow_subselect::no_rows_in_result()
{
unknown's avatar
unknown committed
1096 1097 1098 1099 1100 1101 1102 1103
  /*
    Subquery predicates outside of the SELECT list must be evaluated in order
    to possibly filter the special result row generated for implicit grouping
    if the subquery is in the HAVING clause.
    If the predicate is constant, we need its actual value in the only result
    row for queries with implicit grouping.
  */
  if (parsing_place != SELECT_LIST || const_item())
unknown's avatar
unknown committed
1104
    return;
1105
  value= (new (thd->mem_root) Item_null(thd))->get_cache(thd);
unknown's avatar
unknown committed
1106 1107 1108 1109 1110
  reset();
  make_const();
}


unknown's avatar
unknown committed
1111
void Item_singlerow_subselect::reset()
1112
{
1113
  Item_subselect::reset();
1114
  if (value)
unknown's avatar
unknown committed
1115 1116 1117 1118
  {
    for(uint i= 0; i < engine->cols(); i++)
      row[i]->set_null();
  }
1119 1120
}

1121

unknown's avatar
unknown committed
1122 1123 1124 1125 1126 1127 1128 1129 1130
/**
  @todo
  - We cant change name of Item_field or Item_ref, because it will
  prevent it's correct resolving, but we should save name of
  removed item => we do not make optimization if top item of
  list is field or reference.
  - switch off this optimization for prepare statement,
  because we do not rollback this changes.
  Make rollback for it, or special name resolving mode in 5.0.
unknown's avatar
unknown committed
1131 1132 1133 1134

  @param join  Join object of the subquery (i.e. 'child' join).

  @retval false  The subquery was transformed
unknown's avatar
unknown committed
1135
*/
unknown's avatar
unknown committed
1136
bool
unknown's avatar
unknown committed
1137
Item_singlerow_subselect::select_transformer(JOIN *join)
1138
{
1139
  DBUG_ENTER("Item_singlerow_subselect::select_transformer");
unknown's avatar
unknown committed
1140
  if (changed)
unknown's avatar
unknown committed
1141
    DBUG_RETURN(false);
1142
  DBUG_ASSERT(join->thd == thd);
1143

1144
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
1145
  Query_arena *arena= thd->stmt_arena;
1146

1147
  if (!select_lex->master_unit()->is_unit_op() &&
1148
      !select_lex->table_list.elements &&
unknown's avatar
unknown committed
1149
      select_lex->item_list.elements == 1 &&
1150
      !select_lex->item_list.head()->with_sum_func() &&
unknown's avatar
unknown committed
1151 1152 1153 1154 1155 1156 1157
      /*
	We cant change name of Item_field or Item_ref, because it will
	prevent it's correct resolving, but we should save name of
	removed item => we do not make optimization if top item of
	list is field or reference.
	TODO: solve above problem
      */
unknown's avatar
unknown committed
1158
      !(select_lex->item_list.head()->type() == FIELD_ITEM ||
1159
	select_lex->item_list.head()->type() == REF_ITEM) &&
1160
      !join->conds && !join->having &&
1161
      /*
unknown's avatar
unknown committed
1162
        switch off this optimization for prepare statement,
1163 1164 1165
        because we do not rollback this changes
        TODO: make rollback for it, or special name resolving mode in 5.0.
      */
1166
      !arena->is_stmt_prepare_or_first_sp_execute()
unknown's avatar
unknown committed
1167
      )
1168 1169
  {
    have_to_be_excluded= 1;
unknown's avatar
unknown committed
1170
    if (thd->lex->describe)
1171 1172
    {
      char warn_buff[MYSQL_ERRMSG_SIZE];
1173 1174
      sprintf(warn_buff, ER_THD(thd, ER_SELECT_REDUCED),
              select_lex->select_number);
1175
      push_warning(thd, Sql_condition::WARN_LEVEL_NOTE,
1176 1177 1178
		   ER_SELECT_REDUCED, warn_buff);
    }
    substitution= select_lex->item_list.head();
unknown's avatar
unknown committed
1179
    /*
unknown's avatar
unknown committed
1180
      as far as we moved content to upper level we have to fix dependences & Co
unknown's avatar
unknown committed
1181
    */
1182 1183
    substitution->fix_after_pullout(select_lex->outer_select(),
                                    &substitution, TRUE);
1184
  }
unknown's avatar
unknown committed
1185
  DBUG_RETURN(false);
1186 1187
}

unknown's avatar
unknown committed
1188

unknown's avatar
unknown committed
1189
void Item_singlerow_subselect::store(uint i, Item *item)
unknown's avatar
unknown committed
1190
{
1191
  row[i]->store(item);
1192
  row[i]->cache_value();
unknown's avatar
unknown committed
1193 1194
}

1195 1196 1197
const Type_handler *Item_singlerow_subselect::type_handler() const
{
  return engine->type_handler();
1198 1199
}

1200
bool Item_singlerow_subselect::fix_length_and_dec()
1201
{
1202 1203
  if ((max_columns= engine->cols()) == 1)
  {
1204 1205
    if (engine->fix_length_and_dec(row= &value))
      return TRUE;
1206 1207
  }
  else
1208
  {
1209
    if (!(row= (Item_cache**) current_thd->alloc(sizeof(Item_cache*) *
1210 1211 1212
                                                 max_columns)) ||
        engine->fix_length_and_dec(row))
      return TRUE;
1213
    value= *row;
1214
  }
1215
  unsigned_flag= value->unsigned_flag;
1216 1217 1218 1219 1220 1221 1222
  /*
    If there are not tables in subquery then ability to have NULL value
    depends on SELECT list (if single row subquery have tables then it
    always can be NULL if there are not records fetched).
  */
  if (engine->no_tables())
    maybe_null= engine->may_be_null();
unknown's avatar
unknown committed
1223 1224 1225 1226 1227
  else
  {
    for (uint i= 0; i < max_columns; i++)
      row[i]->maybe_null= TRUE;
  }
1228
  return FALSE;
1229 1230
}

unknown's avatar
unknown committed
1231 1232 1233 1234 1235 1236 1237 1238 1239

/**
  Add an expression cache for this subquery if it is needed

  @param thd_arg         Thread handle

  @details
  The function checks whether an expression cache is needed for this item
  and if if so wraps the item into an item of the class
1240
  Item_cache_wrapper with an appropriate expression cache set up there.
unknown's avatar
unknown committed
1241 1242 1243 1244 1245 1246 1247 1248 1249

  @note
  used from Item::transform()

  @return
  new wrapper item if an expression cache is needed,
  this item - otherwise
*/

1250 1251
Item* Item_singlerow_subselect::expr_cache_insert_transformer(THD *tmp_thd,
                                                              uchar *unused)
unknown's avatar
unknown committed
1252 1253 1254
{
  DBUG_ENTER("Item_singlerow_subselect::expr_cache_insert_transformer");

1255 1256
  DBUG_ASSERT(thd == tmp_thd);

1257 1258 1259
  if (expr_cache)
    DBUG_RETURN(expr_cache);

1260 1261
  if (expr_cache_is_needed(tmp_thd) &&
      (expr_cache= set_expr_cache(tmp_thd)))
1262
  {
1263
    init_expr_cache_tracker(tmp_thd);
1264
    DBUG_RETURN(expr_cache);
1265
  }
unknown's avatar
unknown committed
1266 1267 1268 1269
  DBUG_RETURN(this);
}


1270
uint Item_singlerow_subselect::cols() const
unknown's avatar
unknown committed
1271
{
1272 1273 1274
  return engine->cols();
}

unknown's avatar
unknown committed
1275
bool Item_singlerow_subselect::check_cols(uint c)
1276 1277 1278
{
  if (c != engine->cols())
  {
unknown's avatar
unknown committed
1279
    my_error(ER_OPERAND_COLUMNS, MYF(0), c);
1280 1281 1282 1283 1284
    return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1285
bool Item_singlerow_subselect::null_inside()
1286 1287 1288 1289 1290 1291 1292 1293 1294
{
  for (uint i= 0; i < max_columns ; i++)
  {
    if (row[i]->null_value)
      return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1295
void Item_singlerow_subselect::bring_value()
1296
{
1297 1298 1299 1300
  if (!exec() && assigned())
    null_value= 0;
  else
    reset();
unknown's avatar
unknown committed
1301 1302
}

1303
double Item_singlerow_subselect::val_real()
unknown's avatar
unknown committed
1304
{
1305
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1306 1307
  if (forced_const)
    return value->val_real();
1308
  if (!exec() && !value->null_value)
1309
  {
1310
    null_value= FALSE;
1311
    return value->val_real();
1312 1313
  }
  else
unknown's avatar
unknown committed
1314
  {
1315
    reset();
unknown's avatar
unknown committed
1316
    return 0;
unknown's avatar
unknown committed
1317
  }
unknown's avatar
unknown committed
1318 1319
}

1320
longlong Item_singlerow_subselect::val_int()
unknown's avatar
unknown committed
1321
{
1322
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1323 1324
  if (forced_const)
    return value->val_int();
1325
  if (!exec() && !value->null_value)
1326
  {
1327
    null_value= FALSE;
1328 1329 1330
    return value->val_int();
  }
  else
unknown's avatar
unknown committed
1331
  {
1332
    reset();
unknown's avatar
unknown committed
1333
    return 0;
unknown's avatar
unknown committed
1334
  }
unknown's avatar
unknown committed
1335 1336
}

unknown's avatar
unknown committed
1337
String *Item_singlerow_subselect::val_str(String *str)
unknown's avatar
unknown committed
1338
{
unknown's avatar
unknown committed
1339 1340 1341
  DBUG_ASSERT(fixed == 1);
  if (forced_const)
    return value->val_str(str);
1342
  if (!exec() && !value->null_value)
1343
  {
1344
    null_value= FALSE;
1345 1346 1347
    return value->val_str(str);
  }
  else
unknown's avatar
unknown committed
1348
  {
1349
    reset();
unknown's avatar
unknown committed
1350
    return 0;
unknown's avatar
unknown committed
1351
  }
unknown's avatar
unknown committed
1352 1353
}

unknown's avatar
unknown committed
1354

1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372
bool Item_singlerow_subselect::val_native(THD *thd, Native *to)
{
  DBUG_ASSERT(fixed == 1);
  if (forced_const)
    return value->val_native(thd, to);
  if (!exec() && !value->null_value)
  {
    null_value= false;
    return value->val_native(thd, to);
  }
  else
  {
    reset();
    return true;
  }
}


unknown's avatar
unknown committed
1373 1374
my_decimal *Item_singlerow_subselect::val_decimal(my_decimal *decimal_value)
{
unknown's avatar
unknown committed
1375 1376 1377
  DBUG_ASSERT(fixed == 1);
  if (forced_const)
    return value->val_decimal(decimal_value);
1378
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1379
  {
1380
    null_value= FALSE;
unknown's avatar
unknown committed
1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392
    return value->val_decimal(decimal_value);
  }
  else
  {
    reset();
    return 0;
  }
}


bool Item_singlerow_subselect::val_bool()
{
unknown's avatar
unknown committed
1393 1394 1395
  DBUG_ASSERT(fixed == 1);
  if (forced_const)
    return value->val_bool();
1396
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1397
  {
1398
    null_value= FALSE;
unknown's avatar
unknown committed
1399 1400 1401 1402 1403 1404 1405 1406 1407 1408
    return value->val_bool();
  }
  else
  {
    reset();
    return 0;
  }
}


1409
bool Item_singlerow_subselect::get_date(THD *thd, MYSQL_TIME *ltime, date_mode_t fuzzydate)
1410 1411 1412
{
  DBUG_ASSERT(fixed == 1);
  if (forced_const)
1413
    return value->get_date(thd, ltime, fuzzydate);
1414 1415 1416
  if (!exec() && !value->null_value)
  {
    null_value= FALSE;
1417
    return value->get_date(thd, ltime, fuzzydate);
1418 1419 1420 1421
  }
  else
  {
    reset();
1422
    return 1;
1423 1424 1425 1426
  }
}


1427
Item_exists_subselect::Item_exists_subselect(THD *thd,
1428
                                             st_select_lex *select_lex):
1429
  Item_subselect(thd), upper_not(NULL), abort_on_null(0),
unknown's avatar
unknown committed
1430
  emb_on_expr_nest(NULL), optimizer(0), exists_transformed(0)
unknown's avatar
unknown committed
1431
{
unknown's avatar
unknown committed
1432
  DBUG_ENTER("Item_exists_subselect::Item_exists_subselect");
1433 1434


1435
  init(select_lex, new (thd->mem_root) select_exists_subselect(thd, this));
unknown's avatar
unknown committed
1436
  max_columns= UINT_MAX;
1437
  null_value= FALSE; //can't be NULL
unknown's avatar
unknown committed
1438 1439
  maybe_null= 0; //can't be NULL
  value= 0;
unknown's avatar
unknown committed
1440 1441 1442
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
1443

1444
void Item_exists_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
1445
{
1446
  str->append(STRING_WITH_LEN("exists"));
1447
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
1448 1449 1450
}


unknown's avatar
unknown committed
1451
bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
1452
{
1453 1454
  if (unlikely(unit_arg->fake_select_lex &&
               unit_arg->fake_select_lex->test_limit()))
1455
    return(1);
unknown's avatar
unknown committed
1456

1457
  SELECT_LEX *sl= unit_arg->first_select();
1458 1459
  for (; sl; sl= sl->next_select())
  {
1460
    if (unlikely(sl->test_limit()))
1461 1462 1463 1464 1465
      return(1);
  }
  return(0);
}

1466
Item_in_subselect::Item_in_subselect(THD *thd, Item * left_exp,
unknown's avatar
unknown committed
1467
				     st_select_lex *select_lex):
1468
  Item_exists_subselect(thd), left_expr_cache(0), first_execution(TRUE),
unknown's avatar
unknown committed
1469
  in_strategy(SUBS_NOT_TRANSFORMED),
1470 1471 1472
  pushed_cond_guards(NULL), do_not_convert_to_sj(FALSE), is_jtbm_merged(FALSE),
  is_jtbm_const_tab(FALSE), is_flattenable_semijoin(FALSE),
  is_registered_semijoin(FALSE),
Sergey Petrunya's avatar
Sergey Petrunya committed
1473
  upper_item(0)
unknown's avatar
unknown committed
1474 1475
{
  DBUG_ENTER("Item_in_subselect::Item_in_subselect");
unknown's avatar
unknown committed
1476
  DBUG_PRINT("info", ("in_strategy: %u", (uint)in_strategy));
1477

1478
  left_expr_orig= left_expr= left_exp;
1479 1480
  /* prepare to possible disassembling the item in convert_subq_to_sj() */
  if (left_exp->type() == Item::ROW_ITEM)
1481 1482
    left_expr_orig= new (thd->mem_root)
      Item_row(thd, static_cast<Item_row*>(left_exp));
1483
  func= &eq_creator;
1484
  init(select_lex, new (thd->mem_root) select_exists_subselect(thd, this));
unknown's avatar
unknown committed
1485
  max_columns= UINT_MAX;
1486 1487
  maybe_null= 1;
  reset();
unknown's avatar
unknown committed
1488
  //if test_limit will fail then error will be reported to client
1489
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1490 1491 1492
  DBUG_VOID_RETURN;
}

1493 1494 1495 1496 1497
int Item_in_subselect::get_identifier()
{
  return engine->get_identifier();
}

1498
Item_allany_subselect::Item_allany_subselect(THD *thd, Item * left_exp,
1499
                                             chooser_compare_func_creator fc,
unknown's avatar
unknown committed
1500
					     st_select_lex *select_lex,
1501 1502
					     bool all_arg):
  Item_in_subselect(thd), func_creator(fc), all(all_arg)
unknown's avatar
unknown committed
1503
{
1504
  DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
1505
  left_expr_orig= left_expr= left_exp;
1506 1507
  /* prepare to possible disassembling the item in convert_subq_to_sj() */
  if (left_exp->type() == Item::ROW_ITEM)
1508 1509
    left_expr_orig= new (thd->mem_root)
      Item_row(thd, static_cast<Item_row*>(left_exp));
1510
  func= func_creator(all_arg);
1511
  init(select_lex, new (thd->mem_root) select_exists_subselect(thd, this));
unknown's avatar
unknown committed
1512
  max_columns= 1;
1513
  abort_on_null= 0;
1514
  reset();
unknown's avatar
unknown committed
1515
  //if test_limit will fail then error will be reported to client
1516
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1517
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
1518 1519
}

unknown's avatar
unknown committed
1520

1521 1522 1523 1524 1525 1526
/**
  Initialize length and decimals for EXISTS  and inherited (IN/ALL/ANY)
  subqueries
*/

void Item_exists_subselect::init_length_and_dec()
1527
{
1528 1529 1530
  decimals= 0;
  max_length= 1;
  max_columns= engine->cols();
1531 1532 1533
}


1534
bool Item_exists_subselect::fix_length_and_dec()
1535
{
1536 1537 1538 1539 1540 1541
  DBUG_ENTER("Item_exists_subselect::fix_length_and_dec");
  init_length_and_dec();
  /*
    We need only 1 row to determine existence (i.e. any EXISTS that is not
    an IN always requires LIMIT 1)
  */
1542 1543 1544
  Item *item= new (thd->mem_root) Item_int(thd, (int32) 1);
  if (!item)
    DBUG_RETURN(TRUE);
1545
  thd->change_item_tree(&unit->global_parameters()->select_limit,
1546
                        item);
1547
  DBUG_PRINT("info", ("Set limit to 1"));
1548
  DBUG_RETURN(FALSE);
1549 1550
}

1551

1552
bool Item_in_subselect::fix_length_and_dec()
1553 1554
{
  DBUG_ENTER("Item_in_subselect::fix_length_and_dec");
1555 1556 1557 1558 1559
  init_length_and_dec();
  /*
    Unlike Item_exists_subselect, LIMIT 1 is set later for
    Item_in_subselect, depending on the chosen strategy.
  */
1560
  DBUG_RETURN(FALSE);
1561 1562
}

unknown's avatar
unknown committed
1563 1564 1565 1566 1567 1568 1569 1570 1571

/**
  Add an expression cache for this subquery if it is needed

  @param thd_arg         Thread handle

  @details
  The function checks whether an expression cache is needed for this item
  and if if so wraps the item into an item of the class
1572
  Item_cache_wrapper with an appropriate expression cache set up there.
unknown's avatar
unknown committed
1573 1574 1575 1576 1577 1578 1579 1580 1581

  @note
  used from Item::transform()

  @return
  new wrapper item if an expression cache is needed,
  this item - otherwise
*/

1582 1583
Item* Item_exists_subselect::expr_cache_insert_transformer(THD *tmp_thd,
                                                           uchar *unused)
unknown's avatar
unknown committed
1584 1585
{
  DBUG_ENTER("Item_exists_subselect::expr_cache_insert_transformer");
1586
  DBUG_ASSERT(thd == tmp_thd);
unknown's avatar
unknown committed
1587

1588 1589 1590
  if (expr_cache)
    DBUG_RETURN(expr_cache);

1591 1592
  if (substype() == EXISTS_SUBS && expr_cache_is_needed(tmp_thd) &&
      (expr_cache= set_expr_cache(tmp_thd)))
1593
  {
1594
    init_expr_cache_tracker(tmp_thd);
1595
    DBUG_RETURN(expr_cache);
1596
  }
unknown's avatar
unknown committed
1597 1598 1599 1600
  DBUG_RETURN(this);
}


unknown's avatar
unknown committed
1601 1602
void Item_exists_subselect::no_rows_in_result()
{
unknown's avatar
unknown committed
1603 1604 1605 1606 1607 1608 1609 1610
  /*
    Subquery predicates outside of the SELECT list must be evaluated in order
    to possibly filter the special result row generated for implicit grouping
    if the subquery is in the HAVING clause.
    If the predicate is constant, we need its actual value in the only result
    row for queries with implicit grouping.
  */
  if (parsing_place != SELECT_LIST || const_item())
unknown's avatar
unknown committed
1611
    return;
unknown's avatar
unknown committed
1612 1613 1614 1615 1616
  value= 0;
  null_value= 0;
  make_const();
}

1617
double Item_exists_subselect::val_real()
unknown's avatar
unknown committed
1618
{
1619
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1620
  if (!forced_const && exec())
unknown's avatar
unknown committed
1621
  {
1622
    reset();
unknown's avatar
unknown committed
1623
    return 0;
unknown's avatar
unknown committed
1624
  }
unknown's avatar
unknown committed
1625 1626 1627
  return (double) value;
}

1628
longlong Item_exists_subselect::val_int()
unknown's avatar
unknown committed
1629
{
1630
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1631
  if (!forced_const && exec())
unknown's avatar
unknown committed
1632
  {
1633
    reset();
unknown's avatar
unknown committed
1634
    return 0;
unknown's avatar
unknown committed
1635
  }
unknown's avatar
unknown committed
1636 1637 1638
  return value;
}

1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652

/**
  Return the result of EXISTS as a string value

  Converts the true/false result into a string value.
  Note that currently this cannot be NULL, so if the query exection fails
  it will return 0.

  @param decimal_value[out]    buffer to hold the resulting string value
  @retval                      Pointer to the converted string.
                               Can't be a NULL pointer, as currently
                               EXISTS cannot return NULL.
*/

unknown's avatar
unknown committed
1653 1654
String *Item_exists_subselect::val_str(String *str)
{
1655
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1656
  if (!forced_const && exec())
1657
    reset();
unknown's avatar
unknown committed
1658
  str->set((ulonglong)value,&my_charset_bin);
1659 1660 1661
  return str;
}

unknown's avatar
unknown committed
1662

1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675
/**
  Return the result of EXISTS as a decimal value

  Converts the true/false result into a decimal value.
  Note that currently this cannot be NULL, so if the query exection fails
  it will return 0.

  @param decimal_value[out]    Buffer to hold the resulting decimal value
  @retval                      Pointer to the converted decimal.
                               Can't be a NULL pointer, as currently
                               EXISTS cannot return NULL.
*/

unknown's avatar
unknown committed
1676 1677 1678
my_decimal *Item_exists_subselect::val_decimal(my_decimal *decimal_value)
{
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1679
  if (!forced_const && exec())
unknown's avatar
unknown committed
1680 1681 1682 1683 1684 1685 1686 1687 1688
    reset();
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


bool Item_exists_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1689
  if (!forced_const && exec())
unknown's avatar
unknown committed
1690 1691 1692 1693
  {
    reset();
    return 0;
  }
1694
  return value != 0;
unknown's avatar
unknown committed
1695 1696 1697
}


1698
double Item_in_subselect::val_real()
1699
{
unknown's avatar
unknown committed
1700 1701 1702 1703 1704
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1705
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1706 1707 1708 1709
  if (forced_const)
    return value;
  DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
              ! engine->is_executed());
1710
  null_value= was_null= FALSE;
1711
  if (exec())
1712 1713 1714 1715 1716
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1717
    null_value= TRUE;
1718 1719 1720
  return (double) value;
}

unknown's avatar
unknown committed
1721

1722
longlong Item_in_subselect::val_int()
1723
{
unknown's avatar
unknown committed
1724 1725 1726 1727 1728
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1729
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1730 1731 1732 1733
  if (forced_const)
    return value;
  DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
              ! engine->is_executed());
1734
  null_value= was_null= FALSE;
1735
  if (exec())
1736 1737 1738 1739 1740
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1741
    null_value= TRUE;
1742 1743 1744
  return value;
}

unknown's avatar
unknown committed
1745

1746 1747
String *Item_in_subselect::val_str(String *str)
{
unknown's avatar
unknown committed
1748 1749 1750 1751 1752
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1753
  DBUG_ASSERT(fixed == 1);
unknown's avatar
unknown committed
1754 1755 1756 1757
  if (forced_const)
    goto value_is_ready;
  DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
              ! engine->is_executed());
1758
  null_value= was_null= FALSE;
1759
  if (exec())
1760 1761 1762 1763 1764 1765
  {
    reset();
    return 0;
  }
  if (was_null && !value)
  {
1766
    null_value= TRUE;
unknown's avatar
unknown committed
1767
    return 0;
unknown's avatar
unknown committed
1768
  }
unknown's avatar
unknown committed
1769
value_is_ready:
unknown's avatar
unknown committed
1770
  str->set((ulonglong)value, &my_charset_bin);
unknown's avatar
unknown committed
1771 1772 1773
  return str;
}

unknown's avatar
unknown committed
1774

unknown's avatar
unknown committed
1775 1776 1777
bool Item_in_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1778
  if (forced_const)
1779
    return value;
unknown's avatar
unknown committed
1780
  DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
Igor Babaev's avatar
Igor Babaev committed
1781
              ! engine->is_executed() || with_recursive_reference);
unknown's avatar
unknown committed
1782
  null_value= was_null= FALSE;
1783
  if (exec())
unknown's avatar
unknown committed
1784 1785 1786 1787 1788
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1789
    null_value= TRUE;
unknown's avatar
unknown committed
1790 1791 1792 1793 1794 1795 1796 1797 1798 1799
  return value;
}

my_decimal *Item_in_subselect::val_decimal(my_decimal *decimal_value)
{
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
1800 1801 1802 1803
  if (forced_const)
    goto value_is_ready;
  DBUG_ASSERT((engine->uncacheable() & ~UNCACHEABLE_EXPLAIN) ||
              ! engine->is_executed());
1804
  null_value= was_null= FALSE;
unknown's avatar
unknown committed
1805
  DBUG_ASSERT(fixed == 1);
1806
  if (exec())
unknown's avatar
unknown committed
1807 1808 1809 1810 1811
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1812
    null_value= TRUE;
unknown's avatar
unknown committed
1813
value_is_ready:
unknown's avatar
unknown committed
1814 1815 1816 1817 1818
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


1819
/**
1820
  Prepare a single-column IN/ALL/ANY subselect for rewriting.
1821

1822
  @param join  Join object of the subquery (i.e. 'child' join).
1823

1824
  @details
1825

1826
  Prepare a single-column subquery to be rewritten. Given the subquery.
1827

1828 1829
  If the subquery has no tables it will be turned to an expression between
  left part and SELECT list.
1830

1831 1832
  In other cases the subquery will be wrapped with  Item_in_optimizer which
  allow later to turn it to EXISTS or MAX/MIN.
1833

unknown's avatar
unknown committed
1834 1835
  @retval false  The subquery was transformed
  @retval true   Error
1836
*/
1837

unknown's avatar
unknown committed
1838
bool
1839
Item_in_subselect::single_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1840
{
1841
  SELECT_LEX *select_lex= join->select_lex;
1842
  DBUG_ENTER("Item_in_subselect::single_value_transformer");
1843
  DBUG_ASSERT(thd == join->thd);
unknown's avatar
unknown committed
1844

1845 1846 1847 1848
  /*
    Check that the right part of the subselect contains no more than one
    column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
  */
1849
  // psergey: duplicated_subselect_card_check
1850 1851 1852
  if (select_lex->item_list.elements > 1)
  {
    my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
1853
    DBUG_RETURN(true);
1854 1855
  }

1856 1857 1858
  Item* join_having= join->having ? join->having : join->tmp_having;
  if (!(join_having || select_lex->with_sum_func ||
        select_lex->group_list.elements) &&
1859
      select_lex->table_list.elements == 0 && !join->conds &&
1860
      !select_lex->master_unit()->is_unit_op())
1861
  {
1862 1863 1864 1865 1866 1867 1868
    Item *where_item= (Item*) select_lex->item_list.head();
    /*
      it is single select without tables => possible optimization
      remove the dependence mark since the item is moved to upper
      select and is not outer anymore.
    */
    where_item->walk(&Item::remove_dependence_processor, 0,
1869
                     select_lex->outer_select());
1870
    /*
Sergei Golubchik's avatar
Sergei Golubchik committed
1871 1872
      fix_field of substitution item will be done in time of
      substituting.
1873 1874 1875 1876 1877 1878
      Note that real_item() should be used instead of
      original left expression because left_expr can be
      runtime created Ref item which is deleted at the end
      of the statement. Thus one of 'substitution' arguments
      can be broken in case of PS.
    */ 
1879
    substitution= func->create(thd, left_expr, where_item);
1880 1881
    have_to_be_excluded= 1;
    if (thd->lex->describe)
1882
    {
1883
      char warn_buff[MYSQL_ERRMSG_SIZE];
1884 1885
      sprintf(warn_buff, ER_THD(thd, ER_SELECT_REDUCED),
              select_lex->select_number);
1886
      push_warning(thd, Sql_condition::WARN_LEVEL_NOTE,
1887
                   ER_SELECT_REDUCED, warn_buff);
1888
    }
unknown's avatar
unknown committed
1889
    DBUG_RETURN(false);
1890 1891
  }

1892 1893 1894 1895
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1896
  if (!substitution)
unknown's avatar
unknown committed
1897
  {
1898
    /* We're invoked for the 1st (or the only) SELECT in the subquery UNION */
1899
    substitution= optimizer;
1900

1901
    SELECT_LEX *current= thd->lex->current_select;
unknown's avatar
unknown committed
1902

1903
    thd->lex->current_select= current->return_after_parsing();
unknown's avatar
unknown committed
1904
    if (!optimizer || optimizer->fix_left(thd))
1905
    {
unknown's avatar
unknown committed
1906
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1907
      DBUG_RETURN(true);
1908
    }
unknown's avatar
unknown committed
1909
    thd->lex->current_select= current;
1910

1911 1912 1913
    /* We will refer to upper level cache array => we have to save it for SP */
    optimizer->keep_top_level_cache();

1914
    /*
1915
      As far as  Item_in_optimizer does not substitute itself on fix_fields
1916 1917
      we can use same item for all selects.
    */
Monty's avatar
Monty committed
1918
    expr= new (thd->mem_root) Item_direct_ref(thd, &select_lex->context,
1919
                              (Item**)optimizer->get_cache(),
1920 1921
                              "<no matter>",
			      &in_left_expr_name);
1922
  }
1923

1924 1925 1926
  DBUG_RETURN(false);
}

1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950

/**
  Apply transformation max/min  transwormation to ALL/ANY subquery if it is
  possible.

  @param join  Join object of the subquery (i.e. 'child' join).

  @details

  If this is an ALL/ANY single-value subselect, try to rewrite it with
  a MIN/MAX subselect. We can do that if a possible NULL result of the
  subselect can be ignored.
  E.g. SELECT * FROM t1 WHERE b > ANY (SELECT a FROM t2) can be rewritten
  with SELECT * FROM t1 WHERE b > (SELECT MAX(a) FROM t2).
  We can't check that this optimization is safe if it's not a top-level
  item of the WHERE clause (e.g. because the WHERE clause can contain IS
  NULL/IS NOT NULL functions). If so, we rewrite ALL/ANY with NOT EXISTS
  later in this method.

  @retval false  The subquery was transformed
  @retval true   Error
*/

bool Item_allany_subselect::transform_into_max_min(JOIN *join)
1951
{
1952
  DBUG_ENTER("Item_allany_subselect::transform_into_max_min");
unknown's avatar
unknown committed
1953
  if (!test_strategy(SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE))
1954
    DBUG_RETURN(false);
1955 1956 1957
  Item **place= optimizer->arguments() + 1;
  SELECT_LEX *select_lex= join->select_lex;
  Item *subs;
1958
  DBUG_ASSERT(thd == join->thd);
1959 1960 1961 1962 1963

  /*
  */
  DBUG_ASSERT(!substitution);

unknown's avatar
unknown committed
1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977
  /*
    Check if optimization with aggregate min/max possible
    1 There is no aggregate in the subquery
    2 It is not UNION
    3 There is tables
    4 It is not ALL subquery with possible NULLs in the SELECT list
  */
  if (!select_lex->group_list.elements &&                /*1*/
      !select_lex->having &&                             /*1*/
      !select_lex->with_sum_func &&                      /*1*/
      !(select_lex->next_select()) &&                    /*2*/
      select_lex->table_list.elements &&                 /*3*/
      (!select_lex->ref_pointer_array[0]->maybe_null ||  /*4*/
       substype() != Item_subselect::ALL_SUBS))          /*4*/
1978
  {
1979 1980 1981 1982 1983 1984 1985 1986
    Item_sum_hybrid *item;
    nesting_map save_allow_sum_func;
    if (func->l_op())
    {
      /*
        (ALL && (> || =>)) || (ANY && (< || =<))
        for ALL condition is inverted
      */
1987 1988
      item= new (thd->mem_root) Item_sum_max(thd,
                                             select_lex->ref_pointer_array[0]);
1989 1990 1991 1992 1993 1994 1995
    }
    else
    {
      /*
        (ALL && (< || =<)) || (ANY && (> || =>))
        for ALL condition is inverted
      */
1996 1997
      item= new (thd->mem_root) Item_sum_min(thd,
                                             select_lex->ref_pointer_array[0]);
1998 1999 2000
    }
    if (upper_item)
      upper_item->set_sum_test(item);
2001
    thd->change_item_tree(&select_lex->ref_pointer_array[0], item);
2002 2003 2004 2005 2006 2007
    {
      List_iterator<Item> it(select_lex->item_list);
      it++;
      thd->change_item_tree(it.ref(), item);
    }

Michael Widenius's avatar
Michael Widenius committed
2008 2009 2010
    DBUG_EXECUTE("where",
                 print_where(item, "rewrite with MIN/MAX", QT_ORDINARY););

2011
    save_allow_sum_func= thd->lex->allow_sum_func;
2012
    thd->lex->allow_sum_func.set_bit(thd->lex->current_select->nest_level);
unknown's avatar
unknown committed
2013
    /*
2014 2015 2016
      Item_sum_(max|min) can't substitute other item => we can use 0 as
      reference, also Item_sum_(max|min) can't be fixed after creation, so
      we do not check item->fixed
unknown's avatar
unknown committed
2017
    */
2018 2019 2020 2021 2022 2023 2024 2025
    if (item->fix_fields(thd, 0))
      DBUG_RETURN(true);
    thd->lex->allow_sum_func= save_allow_sum_func; 
    /* we added aggregate function => we have to change statistic */
    count_field_types(select_lex, &join->tmp_table_param, join->all_fields, 
                      0);
    if (join->prepare_stage2())
      DBUG_RETURN(true);
2026
    subs= new (thd->mem_root) Item_singlerow_subselect(thd, select_lex);
2027

unknown's avatar
unknown committed
2028 2029 2030 2031
    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
2032
    set_strategy(SUBS_MAXMIN_INJECTED);
2033 2034 2035 2036
  }
  else
  {
    Item_maxmin_subselect *item;
Monty's avatar
Monty committed
2037
    subs= item= new (thd->mem_root) Item_maxmin_subselect(thd, this, select_lex, func->l_op());
2038 2039
    if (upper_item)
      upper_item->set_sub_test(item);
unknown's avatar
unknown committed
2040 2041 2042 2043
    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
2044
    set_strategy(SUBS_MAXMIN_ENGINE);
2045
  }
2046
  /*
unknown's avatar
unknown committed
2047 2048
    The swap is needed for expressions of type 'f1 < ALL ( SELECT ....)'
    where we want to evaluate the sub query even if f1 would be null.
2049
  */
2050
  subs= func->create_swap(thd, *(optimizer->get_cache()), subs);
2051 2052
  thd->change_item_tree(place, subs);
  if (subs->fix_fields(thd, &subs))
2053
    DBUG_RETURN(true);
2054 2055 2056 2057
  DBUG_ASSERT(subs == (*place)); // There was no substitutions

  select_lex->master_unit()->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
  select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
2058

unknown's avatar
unknown committed
2059
  DBUG_RETURN(false);
2060
}
2061

2062

2063 2064 2065
bool Item_in_subselect::fix_having(Item *having, SELECT_LEX *select_lex)
{
  bool fix_res= 0;
2066
  DBUG_ASSERT(thd);
2067
  if (!having->is_fixed())
2068 2069 2070 2071 2072 2073
  {
    select_lex->having_fix_field= 1;
    fix_res= having->fix_fields(thd, 0);
    select_lex->having_fix_field= 0;
  }
  return fix_res;
2074 2075
}

2076 2077 2078 2079 2080 2081
bool Item_allany_subselect::is_maxmin_applicable(JOIN *join)
{
  /*
    Check if max/min optimization applicable: It is top item of
    WHERE condition.
  */
unknown's avatar
unknown committed
2082
  return (abort_on_null || (upper_item && upper_item->is_top_level_item())) &&
2083
      !(join->select_lex->master_unit()->uncacheable & ~UNCACHEABLE_EXPLAIN) && !func->eqne_op();
2084 2085 2086 2087
}


/**
2088 2089
  Create the predicates needed to transform a single-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
2090

2091 2092 2093
  @param join[in]  Join object of the subquery (i.e. 'child' join).
  @param where_item[out]   the in-to-exists addition to the where clause
  @param having_item[out]  the in-to-exists addition to the having clause
2094

2095 2096
  @details
  The correlated predicates are created as follows:
2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110

  - If the subquery has aggregates, GROUP BY, or HAVING, convert to

    SELECT ie FROM ...  HAVING subq_having AND 
                               trigcond(oe $cmp$ ref_or_null_helper<ie>)
                                   
    the addition is wrapped into trigger only when we want to distinguish
    between NULL and FALSE results.

  - Otherwise (no aggregates/GROUP BY/HAVING) convert it to one of the
    following:

    = If we don't need to distinguish between NULL and FALSE subquery:
        
2111
      SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
2112 2113 2114

    = If we need to distinguish between those:

2115
      SELECT ie FROM ...
2116 2117 2118
        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
        HAVING trigcond(<is_not_null_test>(ie))

unknown's avatar
unknown committed
2119 2120
  @retval false If the new conditions were created successfully
  @retval true  Error
2121 2122
*/

unknown's avatar
unknown committed
2123
bool
Monty's avatar
Monty committed
2124
Item_in_subselect::create_single_in_to_exists_cond(JOIN *join,
2125 2126
                                                   Item **where_item,
                                                   Item **having_item)
2127 2128
{
  SELECT_LEX *select_lex= join->select_lex;
2129
  DBUG_ASSERT(thd == join->thd);
unknown's avatar
unknown committed
2130
  /*
2131 2132
    The non-transformed HAVING clause of 'join' may be stored in two ways
    during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
unknown's avatar
unknown committed
2133
  */
2134 2135
  Item* join_having= join->having ? join->having : join->tmp_having;
  DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
2136

2137 2138
  *where_item= NULL;
  *having_item= NULL;
2139

2140
  if (join_having || select_lex->with_sum_func ||
2141 2142
      select_lex->group_list.elements)
  {
2143 2144
    const char *tmp= this->full_name();
    LEX_CSTRING field_name= {tmp, safe_strlen(tmp)};
2145
    Item *item= func->create(thd, expr,
2146
                             new (thd->mem_root) Item_ref_null_helper(
2147
                                                      thd,
2148
                                                      &select_lex->context,
2149
                                                      this,
2150 2151
                                                      &select_lex->
                                                      ref_pointer_array[0],  
unknown's avatar
unknown committed
2152
                                                      (char *)"<ref>",
2153
                                                      &field_name));
2154
    if (!abort_on_null && left_expr->maybe_null)
2155 2156 2157
    {
      /* 
        We can encounter "NULL IN (SELECT ...)". Wrap the added condition
2158
        within a trig_cond.
2159
      */
2160
      disable_cond_guard_for_const_null_left_expr(0);
Monty's avatar
Monty committed
2161
      item= new (thd->mem_root) Item_func_trig_cond(thd, item, get_cond_guard(0));
2162
    }
2163

2164
    if (!join_having)
2165
      item->name= in_having_cond;
2166
    if (fix_having(item, select_lex))
unknown's avatar
unknown committed
2167
      DBUG_RETURN(true);
2168
    *having_item= item;
2169 2170 2171
  }
  else
  {
2172 2173 2174 2175
    Item *item= (Item*) select_lex->item_list.head();
    if (item->type() != REF_ITEM ||
        ((Item_ref*)item)->ref_type() != Item_ref::VIEW_REF)
      item= item->real_item();
unknown's avatar
unknown committed
2176

2177
    if (select_lex->table_list.elements)
2178
    {
2179 2180
      Item *having= item;
      Item *orig_item= item;
2181
       
2182
      item= func->create(thd, expr, item);
2183
      if (!abort_on_null && orig_item->maybe_null)
unknown's avatar
unknown committed
2184
      {
2185
	having= new (thd->mem_root) Item_is_not_null_test(thd, this, having);
2186 2187
        if (left_expr->maybe_null)
        {
2188
          disable_cond_guard_for_const_null_left_expr(0);
2189
          if (!(having= new (thd->mem_root) Item_func_trig_cond(thd, having,
2190
                                                            get_cond_guard(0))))
unknown's avatar
unknown committed
2191
            DBUG_RETURN(true);
2192
        }
2193
        having->name= in_having_cond;
2194
        if (fix_having(having, select_lex))
unknown's avatar
unknown committed
2195
          DBUG_RETURN(true);
2196
        *having_item= having;
2197

2198 2199
	item= new (thd->mem_root) Item_cond_or(thd, item,
                               new (thd->mem_root) Item_func_isnull(thd, orig_item));
2200
      }
2201
      /* 
2202 2203
        If we may encounter NULL IN (SELECT ...) and care whether subquery
        result is NULL or FALSE, wrap condition in a trig_cond.
2204 2205 2206
      */
      if (!abort_on_null && left_expr->maybe_null)
      {
2207
        disable_cond_guard_for_const_null_left_expr(0);
2208
        if (!(item= new (thd->mem_root) Item_func_trig_cond(thd, item,
2209
                                                            get_cond_guard(0))))
unknown's avatar
unknown committed
2210
          DBUG_RETURN(true);
2211
      }
2212

2213 2214 2215 2216 2217
      /*
        TODO: figure out why the following is done here in 
        single_value_transformer but there is no corresponding action in
        row_value_transformer?
      */
2218
      item->name= in_additional_cond;
2219
      if (item->fix_fields_if_needed(thd, 0))
unknown's avatar
unknown committed
2220
        DBUG_RETURN(true);
2221
      *where_item= item;
2222 2223 2224
    }
    else
    {
2225
      if (select_lex->master_unit()->is_unit_op())
2226
      {
2227
        LEX_CSTRING field_name= {STRING_WITH_LEN("<result>") };
2228
        Item *new_having=
2229 2230
          func->create(thd, expr,
                       new (thd->mem_root) Item_ref_null_helper(thd,
2231 2232
                                                  &select_lex->context,
                                                  this,
2233
                                                  &select_lex->ref_pointer_array[0],
2234
                                                  (char *)"<no matter>",
2235
                                                  &field_name));
2236 2237
        if (!abort_on_null && left_expr->maybe_null)
        {
2238
          disable_cond_guard_for_const_null_left_expr(0);
2239
          if (!(new_having= new (thd->mem_root) Item_func_trig_cond(thd, new_having,
2240
                                                            get_cond_guard(0))))
unknown's avatar
unknown committed
2241
            DBUG_RETURN(true);
2242
        }
2243

2244
        new_having->name= in_having_cond;
2245
        if (fix_having(new_having, select_lex))
unknown's avatar
unknown committed
2246
          DBUG_RETURN(true);
2247
        *having_item= new_having;
2248 2249
      }
      else
2250
        DBUG_ASSERT(false);
2251
    }
unknown's avatar
unknown committed
2252
  }
unknown's avatar
unknown committed
2253

unknown's avatar
unknown committed
2254
  DBUG_RETURN(false);
unknown's avatar
unknown committed
2255
}
unknown's avatar
unknown committed
2256

2257

2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269
/**
  Wrap a multi-column IN/ALL/ANY subselect into an Item_in_optimizer.

  @param join  Join object of the subquery (i.e. 'child' join).

  @details
  The subquery predicate is wrapped into an Item_in_optimizer. Later the query
  optimization phase chooses whether the subquery under the Item_in_optimizer
  will be further transformed into an equivalent correlated EXISTS by injecting
  additional predicates, or will be executed via subquery materialization in its
  unmodified form.

unknown's avatar
unknown committed
2270 2271
  @retval false  The subquery was transformed
  @retval true   Error
2272 2273
*/

unknown's avatar
unknown committed
2274
bool
unknown's avatar
unknown committed
2275
Item_in_subselect::row_value_transformer(JOIN *join)
unknown's avatar
unknown committed
2276
{
unknown's avatar
unknown committed
2277
  SELECT_LEX *select_lex= join->select_lex;
2278
  uint cols_num= left_expr->cols();
2279

unknown's avatar
unknown committed
2280
  DBUG_ENTER("Item_in_subselect::row_value_transformer");
2281
  DBUG_ASSERT(thd == join->thd);
unknown's avatar
unknown committed
2282

2283
  // psergey: duplicated_subselect_card_check
2284
  if (select_lex->item_list.elements != cols_num)
2285
  {
2286
    my_error(ER_OPERAND_COLUMNS, MYF(0), cols_num);
unknown's avatar
unknown committed
2287
    DBUG_RETURN(true);
2288 2289
  }

2290 2291 2292 2293
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
2294
  if (!substitution)
unknown's avatar
unknown committed
2295
  {
2296
    //first call for this unit
2297
    SELECT_LEX_UNIT *master_unit= select_lex->master_unit();
2298
    substitution= optimizer;
2299

2300 2301
    SELECT_LEX *current= thd->lex->current_select;
    thd->lex->current_select= current->return_after_parsing();
unknown's avatar
unknown committed
2302
    if (!optimizer || optimizer->fix_left(thd))
2303
    {
unknown's avatar
unknown committed
2304
      thd->lex->current_select= current;
unknown's avatar
unknown committed
2305
      DBUG_RETURN(true);
2306
    }
2307

unknown's avatar
unknown committed
2308
    // we will refer to upper level cache array => we have to save it in PS
2309 2310
    optimizer->keep_top_level_cache();

unknown's avatar
unknown committed
2311
    thd->lex->current_select= current;
unknown's avatar
unknown committed
2312 2313 2314
    /*
      The uncacheable property controls a number of actions, e.g. whether to
      save/restore (via init_save_join_tab/restore_tmp) the original JOIN for
2315
      plans with a temp table where the original JOIN was overridden by
unknown's avatar
unknown committed
2316 2317 2318 2319 2320
      make_simple_join. The UNCACHEABLE_EXPLAIN is ignored by EXPLAIN, thus
      non-correlated subqueries will not appear as such to EXPLAIN.
    */
    master_unit->uncacheable|= UNCACHEABLE_EXPLAIN;
    select_lex->uncacheable|= UNCACHEABLE_EXPLAIN;
2321 2322
  }

unknown's avatar
unknown committed
2323
  DBUG_RETURN(false);
2324 2325 2326 2327
}


/**
2328 2329
  Create the predicates needed to transform a multi-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
2330

2331
  @details
unknown's avatar
unknown committed
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
  The correlated predicates are created as follows:

  - If the subquery has aggregates, GROUP BY, or HAVING, convert to

    (l1, l2, l3) IN (SELECT v1, v2, v3 ... HAVING having)
    =>
    EXISTS (SELECT ... HAVING having and
                              (l1 = v1 or is null v1) and
                              (l2 = v2 or is null v2) and
                              (l3 = v3 or is null v3) and
                              is_not_null_test(v1) and
                              is_not_null_test(v2) and
                              is_not_null_test(v3))

    where is_not_null_test used to register nulls in case if we have
    not found matching to return correct NULL value.

  - Otherwise (no aggregates/GROUP BY/HAVING) convert the subquery as follows:

    (l1, l2, l3) IN (SELECT v1, v2, v3 ... WHERE where)
    =>
    EXISTS (SELECT ... WHERE where and
                             (l1 = v1 or is null v1) and
                             (l2 = v2 or is null v2) and
                             (l3 = v3 or is null v3)
                       HAVING is_not_null_test(v1) and
                              is_not_null_test(v2) and
                              is_not_null_test(v3))
    where is_not_null_test registers NULLs values but reject rows.

    in case when we do not need correct NULL, we have simplier construction:
    EXISTS (SELECT ... WHERE where and
                             (l1 = v1) and
                             (l2 = v2) and
                             (l3 = v3)
2367 2368 2369 2370 2371

  @param join[in]  Join object of the subquery (i.e. 'child' join).
  @param where_item[out]   the in-to-exists addition to the where clause
  @param having_item[out]  the in-to-exists addition to the having clause

unknown's avatar
unknown committed
2372 2373
  @retval false  If the new conditions were created successfully
  @retval true   Error
2374 2375
*/

unknown's avatar
unknown committed
2376
bool
2377 2378 2379
Item_in_subselect::create_row_in_to_exists_cond(JOIN * join,
                                                Item **where_item,
                                                Item **having_item)
2380 2381 2382
{
  SELECT_LEX *select_lex= join->select_lex;
  uint cols_num= left_expr->cols();
2383
  /*
2384 2385
    The non-transformed HAVING clause of 'join' may be stored in two ways
    during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
2386 2387 2388
  */
  Item* join_having= join->having ? join->having : join->tmp_having;
  bool is_having_used= (join_having || select_lex->with_sum_func ||
2389 2390
                        select_lex->group_list.first ||
                        !select_lex->table_list.elements);
2391
  LEX_CSTRING list_ref= { STRING_WITH_LEN("<list ref>")};
2392
  DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
2393
  DBUG_ASSERT(thd == join->thd);
2394 2395 2396

  *where_item= NULL;
  *having_item= NULL;
2397

2398
  if (is_having_used)
unknown's avatar
unknown committed
2399
  {
unknown's avatar
unknown committed
2400
    /* TODO: say here explicitly if the order of AND parts matters or not. */
2401 2402
    Item *item_having_part2= 0;
    for (uint i= 0; i < cols_num; i++)
unknown's avatar
unknown committed
2403
    {
2404
      DBUG_ASSERT((left_expr->is_fixed() &&
2405

2406
                  select_lex->ref_pointer_array[i]->is_fixed()) ||
unknown's avatar
unknown committed
2407 2408 2409
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
2410
      if (select_lex->ref_pointer_array[i]->
2411
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
2412
        DBUG_RETURN(true);
2413

2414
      Item *item_eq=
Monty's avatar
Monty committed
2415 2416 2417 2418 2419 2420
        new (thd->mem_root)
        Item_func_eq(thd, new (thd->mem_root)
                     Item_direct_ref(thd, &select_lex->context,
                                     (*optimizer->get_cache())->
                                     addr(i),
                                     (char *)"<no matter>",
2421
                                     &in_left_expr_name),
Monty's avatar
Monty committed
2422 2423
                     new (thd->mem_root)
                     Item_ref(thd, &select_lex->context,
2424
                              &select_lex->ref_pointer_array[i],
Monty's avatar
Monty committed
2425
                              (char *)"<no matter>",
2426
                              &list_ref));
Monty's avatar
Monty committed
2427 2428 2429 2430
      Item *item_isnull=
        new (thd->mem_root)
        Item_func_isnull(thd,
                         new (thd->mem_root)
2431
                         Item_ref(thd, &select_lex->context,
2432
                                  &select_lex->ref_pointer_array[i],
unknown's avatar
unknown committed
2433
                                  (char *)"<no matter>",
2434
                                  &list_ref));
Monty's avatar
Monty committed
2435 2436
      Item *col_item= new (thd->mem_root)
        Item_cond_or(thd, item_eq, item_isnull);
Igor Babaev's avatar
Igor Babaev committed
2437 2438
      if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
          get_cond_guard(i))
2439
      {
2440
        disable_cond_guard_for_const_null_left_expr(i);
Monty's avatar
Monty committed
2441 2442
        if (!(col_item= new (thd->mem_root)
              Item_func_trig_cond(thd, col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2443
          DBUG_RETURN(true);
2444
      }
2445
      *having_item= and_items(thd, *having_item, col_item);
2446

2447
      Item *item_nnull_test= 
Monty's avatar
Monty committed
2448 2449 2450 2451
         new (thd->mem_root)
        Item_is_not_null_test(thd, this,
                              new (thd->mem_root)
                              Item_ref(thd, &select_lex->context,
2452 2453
                                       &select_lex->
                                       ref_pointer_array[i],
Monty's avatar
Monty committed
2454
                                       (char *)"<no matter>",
2455
                                       &list_ref));
Igor Babaev's avatar
Igor Babaev committed
2456 2457
      if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
          get_cond_guard(i) )
2458
      {
2459
        disable_cond_guard_for_const_null_left_expr(i);
2460
        if (!(item_nnull_test= 
Monty's avatar
Monty committed
2461 2462
              new (thd->mem_root)
              Item_func_trig_cond(thd, item_nnull_test, get_cond_guard(i))))
unknown's avatar
unknown committed
2463
          DBUG_RETURN(true);
2464
      }
2465
      item_having_part2= and_items(thd, item_having_part2, item_nnull_test);
2466
      item_having_part2->top_level_item();
unknown's avatar
unknown committed
2467
    }
2468
    *having_item= and_items(thd, *having_item, item_having_part2);
2469
  }
2470
  else
2471
  {
2472 2473 2474
    for (uint i= 0; i < cols_num; i++)
    {
      Item *item, *item_isnull;
2475 2476
      DBUG_ASSERT((left_expr->is_fixed() &&
                  select_lex->ref_pointer_array[i]->is_fixed()) ||
unknown's avatar
unknown committed
2477 2478 2479
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
2480
      if (select_lex->ref_pointer_array[i]->
2481
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
2482
        DBUG_RETURN(true);
Monty's avatar
Monty committed
2483 2484 2485 2486 2487 2488 2489
      item= new (thd->mem_root)
        Item_func_eq(thd,
                     new (thd->mem_root)
                     Item_direct_ref(thd, &select_lex->context,
                                     (*optimizer->get_cache())->
                                     addr(i),
                                     (char *)"<no matter>",
2490
                                     &in_left_expr_name),
Monty's avatar
Monty committed
2491 2492
                     new (thd->mem_root)
                     Item_direct_ref(thd, &select_lex->context,
2493 2494
                                     &select_lex->
                                     ref_pointer_array[i],
Monty's avatar
Monty committed
2495
                                     (char *)"<no matter>",
2496
                                     &list_ref));
2497
      if (!abort_on_null && select_lex->ref_pointer_array[i]->maybe_null)
2498
      {
2499
        Item *having_col_item=
Monty's avatar
Monty committed
2500 2501 2502 2503
          new (thd->mem_root)
          Item_is_not_null_test(thd, this,
                                new (thd->mem_root)
                                Item_ref(thd, &select_lex->context, 
2504
                                         &select_lex->ref_pointer_array[i],
Monty's avatar
Monty committed
2505
                                         (char *)"<no matter>",
2506
                                         &list_ref));
2507
        
Monty's avatar
Monty committed
2508 2509 2510
        item_isnull= new (thd->mem_root)
          Item_func_isnull(thd,
                           new (thd->mem_root)
2511
                           Item_direct_ref(thd, &select_lex->context,
2512 2513
                                           &select_lex->
                                           ref_pointer_array[i],
unknown's avatar
unknown committed
2514
                                           (char *)"<no matter>",
2515
                                           &list_ref));
Monty's avatar
Monty committed
2516
        item= new (thd->mem_root) Item_cond_or(thd, item, item_isnull);
Igor Babaev's avatar
Igor Babaev committed
2517
        if (left_expr->element_index(i)->maybe_null && get_cond_guard(i))
2518
        {
2519
          disable_cond_guard_for_const_null_left_expr(i);
Monty's avatar
Monty committed
2520 2521
          if (!(item= new (thd->mem_root)
                Item_func_trig_cond(thd, item, get_cond_guard(i))))
unknown's avatar
unknown committed
2522
            DBUG_RETURN(true);
Monty's avatar
Monty committed
2523 2524
          if (!(having_col_item= new (thd->mem_root)
                Item_func_trig_cond(thd, having_col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2525
            DBUG_RETURN(true);
2526
        }
2527
        *having_item= and_items(thd, *having_item, having_col_item);
2528
      }
Igor Babaev's avatar
Igor Babaev committed
2529 2530
      if (!abort_on_null && left_expr->element_index(i)->maybe_null &&
          get_cond_guard(i))
2531
      {
Monty's avatar
Monty committed
2532 2533
        if (!(item= new (thd->mem_root)
              Item_func_trig_cond(thd, item, get_cond_guard(i))))
2534 2535
          DBUG_RETURN(true);
      }
2536
      *where_item= and_items(thd, *where_item, item);
2537
    }
unknown's avatar
unknown committed
2538
  }
2539

2540
  if (*where_item)
2541
  {
2542
    if ((*where_item)->fix_fields_if_needed(thd, 0))
unknown's avatar
unknown committed
2543
      DBUG_RETURN(true);
2544
    (*where_item)->top_level_item();
2545
  }
unknown's avatar
unknown committed
2546

2547
  if (*having_item)
2548
  {
2549
    if (!join_having)
2550
      (*having_item)->name= in_having_cond;
2551
    if (fix_having(*having_item, select_lex))
unknown's avatar
unknown committed
2552
      DBUG_RETURN(true);
2553
    (*having_item)->top_level_item();
2554
  }
unknown's avatar
unknown committed
2555

unknown's avatar
unknown committed
2556
  DBUG_RETURN(false);
unknown's avatar
unknown committed
2557 2558
}

2559

unknown's avatar
unknown committed
2560
bool
unknown's avatar
unknown committed
2561
Item_in_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2562
{
2563
  return select_in_like_transformer(join);
2564 2565
}

unknown's avatar
unknown committed
2566 2567 2568 2569 2570 2571
bool
Item_exists_subselect::select_transformer(JOIN *join)
{
  return select_prepare_to_be_in();
}

2572

unknown's avatar
unknown committed
2573
/**
2574 2575
  Create the predicates needed to transform an IN/ALL/ANY subselect into a
  correlated EXISTS via predicate injection.
2576

2577
  @param join_arg  Join object of the subquery.
2578

2579 2580 2581 2582
  @retval FALSE  ok
  @retval TRUE   error
*/

2583 2584
bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
{
unknown's avatar
unknown committed
2585
  bool res;
2586 2587 2588 2589

  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE ||
              engine->engine_type() == subselect_engine::UNION_ENGINE);
  /*
2590
    TODO: the call to init_cond_guards allocates and initializes an
2591 2592 2593
    array of booleans that may not be used later because we may choose
    materialization.
    The two calls below to create_XYZ_cond depend on this boolean array.
2594
    If the dependency is removed, the call can be moved to a later phase.
2595 2596 2597 2598 2599 2600 2601 2602 2603 2604
  */
  init_cond_guards();
  if (left_expr->cols() == 1)
    res= create_single_in_to_exists_cond(join_arg,
                                         &(join_arg->in_to_exists_where),
                                         &(join_arg->in_to_exists_having));
  else
    res= create_row_in_to_exists_cond(join_arg,
                                      &(join_arg->in_to_exists_where),
                                      &(join_arg->in_to_exists_having));
2605

2606 2607 2608
  /*
    The IN=>EXISTS transformation makes non-correlated subqueries correlated.
  */
2609 2610 2611 2612 2613 2614
  if (!left_expr->const_item() || left_expr->is_expensive())
  {
    join_arg->select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
    join_arg->select_lex->master_unit()->uncacheable|= 
                                         UNCACHEABLE_DEPENDENT_INJECTED;
  }
2615 2616 2617
  /*
    The uncacheable property controls a number of actions, e.g. whether to
    save/restore (via init_save_join_tab/restore_tmp) the original JOIN for
2618
    plans with a temp table where the original JOIN was overridden by
2619 2620 2621 2622 2623
    make_simple_join. The UNCACHEABLE_EXPLAIN is ignored by EXPLAIN, thus
    non-correlated subqueries will not appear as such to EXPLAIN.
  */
  join_arg->select_lex->master_unit()->uncacheable|= UNCACHEABLE_EXPLAIN;
  join_arg->select_lex->uncacheable|= UNCACHEABLE_EXPLAIN;
unknown's avatar
unknown committed
2624
  return (res);
2625 2626 2627
}


2628 2629 2630 2631 2632 2633 2634 2635 2636 2637
/**
  Transform an IN/ALL/ANY subselect into a correlated EXISTS via injecting
  correlated in-to-exists predicates.

  @param join_arg  Join object of the subquery.

  @retval FALSE  ok
  @retval TRUE   error
*/

2638
bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
2639
{
2640 2641 2642
  SELECT_LEX *select_lex= join_arg->select_lex;
  Item *where_item= join_arg->in_to_exists_where;
  Item *having_item= join_arg->in_to_exists_having;
2643

2644
  DBUG_ENTER("Item_in_subselect::inject_in_to_exists_cond");
2645
  DBUG_ASSERT(thd == join_arg->thd);
2646

Igor Babaev's avatar
Igor Babaev committed
2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 2667
  if (select_lex->min_max_opt_list.elements)
  {
    /*
      MIN/MAX optimizations have been applied to Item_sum objects
      of the subquery this subquery predicate in opt_sum_query().
      Injection of new condition invalidates this optimizations.
      Thus those optimizations must be rolled back.
    */
    List_iterator_fast<Item_sum> it(select_lex->min_max_opt_list);
    Item_sum *item;
    while ((item= it++))
    {
      item->clear();
      item->reset_forced_const();
    }
    if (where_item)
      where_item->update_used_tables();
    if (having_item)
      having_item->update_used_tables();
  }

2668 2669
  if (where_item)
  {
unknown's avatar
unknown committed
2670
    List<Item> *and_args= NULL;
unknown's avatar
unknown committed
2671
    /*
unknown's avatar
unknown committed
2672 2673 2674 2675 2676 2677 2678
      If the top-level Item of the WHERE clause is an AND, detach the multiple
      equality list that was attached to the end of the AND argument list by
      build_equal_items_for_cond(). The multiple equalities must be detached
      because fix_fields merges lower level AND arguments into the upper AND.
      As a result, the arguments from lower-level ANDs are concatenated after
      the multiple equalities. When the multiple equality list is treated as
      such, it turns out that it contains non-Item_equal object which is wrong.
unknown's avatar
unknown committed
2679
    */
unknown's avatar
unknown committed
2680 2681 2682 2683 2684 2685 2686 2687
    if (join_arg->conds && join_arg->conds->type() == Item::COND_ITEM &&
        ((Item_cond*) join_arg->conds)->functype() == Item_func::COND_AND_FUNC)
    {
      and_args= ((Item_cond*) join_arg->conds)->argument_list();
      if (join_arg->cond_equal)
        and_args->disjoin((List<Item> *) &join_arg->cond_equal->current_level);
    }

2688
    where_item= and_items(thd, join_arg->conds, where_item);
2689
    if (where_item->fix_fields_if_needed(thd, 0))
2690
      DBUG_RETURN(true);
2691
    // TIMOUR TODO: call optimize_cond() for the new where clause
2692
    thd->change_item_tree(&select_lex->where, where_item);
2693
    select_lex->where->top_level_item();
2694
    join_arg->conds= select_lex->where;
unknown's avatar
unknown committed
2695 2696 2697 2698 2699 2700

    /* Attach back the list of multiple equalities to the new top-level AND. */
    if (and_args && join_arg->cond_equal)
    {
      /* The argument list of the top-level AND may change after fix fields. */
      and_args= ((Item_cond*) join_arg->conds)->argument_list();
2701 2702 2703 2704
      List_iterator<Item_equal> li(join_arg->cond_equal->current_level);
      Item_equal *elem;
      while ((elem= li++))
      {
2705
        and_args->push_back(elem, thd->mem_root);
2706
      }
unknown's avatar
unknown committed
2707
    }
unknown's avatar
unknown committed
2708
  }
2709

2710
  if (having_item)
2711
  {
2712
    Item* join_having= join_arg->having ? join_arg->having:join_arg->tmp_having;
2713
    having_item= and_items(thd, join_having, having_item);
2714 2715
    if (fix_having(having_item, select_lex))
      DBUG_RETURN(true);
2716
    // TIMOUR TODO: call optimize_cond() for the new having clause
2717
    thd->change_item_tree(&select_lex->having, having_item);
2718
    select_lex->having->top_level_item();
2719
    join_arg->having= select_lex->having;
2720
  }
2721
  join_arg->thd->change_item_tree(&unit->global_parameters()->select_limit,
2722 2723
                                  new (thd->mem_root)
                                  Item_int(thd, (int32) 1));
2724
  unit->select_limit_cnt= 1;
unknown's avatar
unknown committed
2725

2726
  DBUG_RETURN(false);
2727 2728 2729
}


unknown's avatar
unknown committed
2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 2749
/*
  If this select can potentially be converted by EXISTS->IN conversion, wrap it
  in an Item_in_optimizer object. Final decision whether to do the conversion
  is done at a later phase.
*/

bool Item_exists_subselect::select_prepare_to_be_in()
{
  bool trans_res= FALSE;
  DBUG_ENTER("Item_exists_subselect::select_prepare_to_be_in");
  if (!optimizer &&
      thd->lex->sql_command == SQLCOM_SELECT &&
      !unit->first_select()->is_part_of_union() &&
      optimizer_flag(thd, OPTIMIZER_SWITCH_EXISTS_TO_IN) &&
      (is_top_level_item() ||
       (upper_not && upper_not->is_top_level_item())))
  {
    Query_arena *arena, backup;
    bool result;
    arena= thd->activate_stmt_arena_if_needed(&backup);
Monty's avatar
Monty committed
2750
    result= (!(optimizer= new (thd->mem_root) Item_in_optimizer(thd, new (thd->mem_root) Item_int(thd, 1), this)));
unknown's avatar
unknown committed
2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777
    if (arena)
      thd->restore_active_arena(arena, &backup);
    if (result)
      trans_res= TRUE;
    else
      substitution= optimizer;
  }
  DBUG_RETURN(trans_res);
}

/**
  Check if 'func' is an equality in form "inner_table.column = outer_expr"

  @param func              Expression to check
  @param local_field  OUT  Return "inner_table.column" here
  @param outer_expr   OUT  Return outer_expr here

  @return true - 'func' is an Equality.
*/

static bool check_equality_for_exist2in(Item_func *func,
                                        Item_ident **local_field,
                                        Item **outer_exp)
{
  Item **args;
  if (func->functype() != Item_func::EQ_FUNC)
    return FALSE;
2778
  DBUG_ASSERT(func->argument_count() == 2);
unknown's avatar
unknown committed
2779 2780 2781 2782 2783 2784 2785 2786 2787 2788 2789 2790 2791 2792 2793 2794 2795
  args= func->arguments();
  if (args[0]->real_type() == Item::FIELD_ITEM &&
      args[0]->all_used_tables() != OUTER_REF_TABLE_BIT &&
      args[1]->all_used_tables() == OUTER_REF_TABLE_BIT)
  {
    /* It is Item_field or Item_direct_view_ref) */
    DBUG_ASSERT(args[0]->type() == Item::FIELD_ITEM ||
                args[0]->type() == Item::REF_ITEM);
    *local_field= (Item_ident *)args[0];
    *outer_exp= args[1];
    return TRUE;
  }
  else if (args[1]->real_type() == Item::FIELD_ITEM &&
           args[1]->all_used_tables() != OUTER_REF_TABLE_BIT &&
           args[0]->all_used_tables() == OUTER_REF_TABLE_BIT)
  {
    /* It is Item_field or Item_direct_view_ref) */
Oleksandr Byelkin's avatar
Oleksandr Byelkin committed
2796 2797
    DBUG_ASSERT(args[1]->type() == Item::FIELD_ITEM ||
                args[1]->type() == Item::REF_ITEM);
unknown's avatar
unknown committed
2798 2799 2800 2801 2802 2803 2804 2805 2806 2807
    *local_field= (Item_ident *)args[1];
    *outer_exp= args[0];
    return TRUE;
  }

  return FALSE;
}

typedef struct st_eq_field_outer
{
2808
  Item **eq_ref;
unknown's avatar
unknown committed
2809 2810 2811 2812 2813 2814 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846
  Item_ident *local_field;
  Item *outer_exp;
} EQ_FIELD_OUTER;


/**
  Check if 'conds' is a set of AND-ed outer_expr=inner_table.col equalities

  @detail
    Check if 'conds' has form

    outer1=inner_tbl1.col1 AND ... AND outer2=inner_tbl1.col2 AND remainder_cond

  @param  conds    Condition to be checked
  @parm   result   Array to collect EQ_FIELD_OUTER elements describing
                   inner-vs-outer equalities the function has found.
  @return
    false - some inner-vs-outer equalities were found
    true  - otherwise.
*/

static bool find_inner_outer_equalities(Item **conds,
                                        Dynamic_array<EQ_FIELD_OUTER> &result)
{
  bool found=  FALSE;
  EQ_FIELD_OUTER element;
  if (is_cond_and(*conds))
  {
    List_iterator<Item> li(*((Item_cond*)*conds)->argument_list());
    Item *item;
    while ((item= li++))
    {
      if (item->type() == Item::FUNC_ITEM &&
          check_equality_for_exist2in((Item_func *)item,
                                      &element.local_field,
                                      &element.outer_exp))
      {
        found= TRUE;
2847
        element.eq_ref= li.ref();
unknown's avatar
unknown committed
2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858
        if (result.append(element))
          goto alloc_err;
      }
    }
  }
  else if ((*conds)->type() == Item::FUNC_ITEM &&
           check_equality_for_exist2in((Item_func *)*conds,
                                       &element.local_field,
                                       &element.outer_exp))
  {
    found= TRUE;
2859
    element.eq_ref= conds;
unknown's avatar
unknown committed
2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876
    if (result.append(element))
      goto alloc_err;
  }

  return !found;
alloc_err:
  return TRUE;
}

/**
  Converts EXISTS subquery to IN subquery if it is possible and has sense

  @param opt_arg         Pointer on THD

  @return TRUE in case of error and FALSE otherwise.
*/

2877
bool Item_exists_subselect::exists2in_processor(void *opt_arg)
unknown's avatar
unknown committed
2878 2879 2880 2881
{
  THD *thd= (THD *)opt_arg;
  SELECT_LEX *first_select=unit->first_select(), *save_select;
  JOIN *join= first_select->join;
2882
  Item **eq_ref= NULL;
unknown's avatar
unknown committed
2883 2884 2885 2886 2887 2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902
  Item_ident *local_field= NULL;
  Item *outer_exp= NULL;
  Item *left_exp= NULL; Item_in_subselect *in_subs;
  Query_arena *arena= NULL, backup;
  int res= FALSE;
  List<Item> outer;
  Dynamic_array<EQ_FIELD_OUTER> eqs(5, 5);
  bool will_be_correlated;
  DBUG_ENTER("Item_exists_subselect::exists2in_processor");

  if (!optimizer ||
      !optimizer_flag(thd, OPTIMIZER_SWITCH_EXISTS_TO_IN) ||
      (!is_top_level_item() && (!upper_not ||
                                !upper_not->is_top_level_item())) ||
      first_select->is_part_of_union() ||
      first_select->group_list.elements ||
      first_select->order_list.elements ||
      join->having ||
      first_select->with_sum_func ||
      !first_select->leaf_tables.elements||
Igor Babaev's avatar
Igor Babaev committed
2903 2904
      !join->conds ||
      with_recursive_reference)
unknown's avatar
unknown committed
2905 2906 2907 2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927
    DBUG_RETURN(FALSE);

  DBUG_ASSERT(first_select->order_list.elements == 0 &&
              first_select->group_list.elements == 0 &&
              first_select->having == NULL);

  if (find_inner_outer_equalities(&join->conds, eqs))
    DBUG_RETURN(FALSE);

  DBUG_ASSERT(eqs.elements() != 0);

  save_select= thd->lex->current_select;
  thd->lex->current_select= first_select;

  /* check that the subquery has only dependencies we are going pull out */
  {
    List<Item> unused;
    Collect_deps_prm prm= {&unused,          // parameters
      unit->first_select()->nest_level_base, // nest_level_base
      0,                                     // count
      unit->first_select()->nest_level,      // nest_level
      FALSE                                  // collect
    };
2928
    walk(&Item::collect_outer_ref_processor, TRUE, &prm);
unknown's avatar
unknown committed
2929 2930 2931 2932 2933 2934 2935 2936 2937 2938 2939 2940 2941 2942 2943 2944 2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963
    DBUG_ASSERT(prm.count > 0);
    DBUG_ASSERT(prm.count >= (uint)eqs.elements());
    will_be_correlated= prm.count > (uint)eqs.elements();
    if (upper_not && will_be_correlated)
      goto out;
  }

  if ((uint)eqs.elements() > (first_select->item_list.elements +
                              first_select->select_n_reserved))
    goto out;
  /* It is simple query */
  DBUG_ASSERT(first_select->join->all_fields.elements ==
              first_select->item_list.elements);

  arena= thd->activate_stmt_arena_if_needed(&backup);

  while (first_select->item_list.elements > (uint)eqs.elements())
  {
    first_select->item_list.pop();
    first_select->join->all_fields.elements--;
  }
  {
    List_iterator<Item> it(first_select->item_list);

    for (uint i= 0; i < (uint)eqs.elements(); i++)
    {
      Item *item= it++;
      eq_ref= eqs.at(i).eq_ref;
      local_field= eqs.at(i).local_field;
      outer_exp= eqs.at(i).outer_exp;
      /* Add the field to the SELECT_LIST */
      if (item)
        it.replace(local_field);
      else
      {
2964
        first_select->item_list.push_back(local_field, thd->mem_root);
unknown's avatar
unknown committed
2965 2966 2967 2968 2969 2970
        first_select->join->all_fields.elements++;
      }
      first_select->ref_pointer_array[i]= (Item *)local_field;

      /* remove the parts from condition */
      if (!upper_not || !local_field->maybe_null)
Monty's avatar
Monty committed
2971
        *eq_ref= new (thd->mem_root) Item_int(thd, 1);
unknown's avatar
unknown committed
2972 2973
      else
      {
Monty's avatar
Monty committed
2974 2975 2976 2977 2978 2979 2980 2981
        *eq_ref= new (thd->mem_root)
          Item_func_isnotnull(thd,
                              new (thd->mem_root)
                              Item_field(thd,
                                         ((Item_field*)(local_field->
                                                        real_item()))->context,
                                         ((Item_field*)(local_field->
                                                        real_item()))->field));
unknown's avatar
unknown committed
2982 2983 2984 2985 2986 2987
        if((*eq_ref)->fix_fields(thd, (Item **)eq_ref))
        {
          res= TRUE;
          goto out;
        }
      }
2988
      outer_exp->fix_after_pullout(unit->outer_select(), &outer_exp, FALSE);
unknown's avatar
unknown committed
2989
      outer_exp->update_used_tables();
2990
      outer.push_back(outer_exp, thd->mem_root);
unknown's avatar
unknown committed
2991 2992 2993 2994 2995 2996 2997 2998 2999 3000
    }
  }

  join->conds->update_used_tables();

  /* make IN SUBQUERY and put outer_exp as left part */
  if (eqs.elements() == 1)
    left_exp= outer_exp;
  else
  {
Monty's avatar
Monty committed
3001
    if (!(left_exp= new (thd->mem_root) Item_row(thd, outer)))
unknown's avatar
unknown committed
3002 3003 3004 3005 3006 3007 3008 3009 3010 3011
    {
      res= TRUE;
      goto out;
    }
  }

  /* make EXISTS->IN permanet (see Item_subselect::init()) */
  set_exists_transformed();

  first_select->select_limit= NULL;
3012
  if (!(in_subs= new (thd->mem_root) Item_in_subselect(thd, left_exp,
3013
                                                         first_select)))
unknown's avatar
unknown committed
3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042
  {
    res= TRUE;
    goto out;
  }
  in_subs->set_exists_transformed();
  optimizer->arguments()[0]= left_exp;
  optimizer->arguments()[1]= in_subs;
  in_subs->optimizer= optimizer;
  DBUG_ASSERT(is_top_level_item() ||
              (upper_not && upper_not->is_top_level_item()));
  in_subs->top_level_item();
  {
    SELECT_LEX *current= thd->lex->current_select;
    optimizer->reset_cache(); // renew cache, and we will not keep it
    thd->lex->current_select= unit->outer_select();
    DBUG_ASSERT(optimizer);
    if (optimizer->fix_left(thd))
    {
      res= TRUE;
      /*
        We should not restore thd->lex->current_select because it will be
        reset on exit from this procedure
      */
      goto out;
    }
    /*
      As far as  Item_ref_in_optimizer do not substitute itself on fix_fields
      we can use same item for all selects.
    */
Monty's avatar
Monty committed
3043 3044 3045 3046
    in_subs->expr= new (thd->mem_root)
      Item_direct_ref(thd, &first_select->context,
                      (Item**)optimizer->get_cache(),
                      (char *)"<no matter>",
3047
                      &in_left_expr_name);
unknown's avatar
unknown committed
3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065
    if (in_subs->fix_fields(thd, optimizer->arguments() + 1))
    {
      res= TRUE;
      /*
        We should not restore thd->lex->current_select because it will be
        reset on exit from this procedure
      */
      goto out;
    }
    {
      /* Move dependence list */
      List_iterator_fast<Ref_to_outside> it(upper_refs);
      Ref_to_outside *upper;
      while ((upper= it++))
      {
        uint i;
        for (i= 0; i < (uint)eqs.elements(); i++)
          if (eqs.at(i).outer_exp->
3066
              walk(&Item::find_item_processor, TRUE, upper->item))
unknown's avatar
unknown committed
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
            break;
        if (i == (uint)eqs.elements() &&
            (in_subs->upper_refs.push_back(upper, thd->stmt_arena->mem_root)))
          goto out;
      }
    }
    in_subs->update_used_tables();
    /*
      The engine of the subquery is fixed so above fix_fields() is not
      complete and should be fixed
    */
    in_subs->upper_refs= upper_refs;
    upper_refs.empty();
    thd->lex->current_select= current;
  }

  DBUG_ASSERT(unit->item == in_subs);
  DBUG_ASSERT(join == first_select->join);
  /*
    Fix dependency info
  */
  in_subs->is_correlated= will_be_correlated;
  if (!will_be_correlated)
  {
    first_select->uncacheable&= ~UNCACHEABLE_DEPENDENT_GENERATED;
    unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_GENERATED;
  }
  /*
    set possible optimization strategies
  */
  in_subs->emb_on_expr_nest= emb_on_expr_nest;
  res= check_and_do_in_subquery_rewrites(join);
  first_select->join->prepare_stage2();

  first_select->fix_prepare_information(thd, &join->conds, &join->having);

  if (upper_not)
  {
    Item *exp;
    if (eqs.elements() == 1)
    {
      exp= (optimizer->arguments()[0]->maybe_null ?
Monty's avatar
Monty committed
3109 3110 3111 3112 3113 3114 3115 3116 3117
            (Item*) new (thd->mem_root)
            Item_cond_and(thd,
                          new (thd->mem_root)
                          Item_func_isnotnull(thd,
                                              new (thd->mem_root)
                                              Item_direct_ref(thd,
                                                              &unit->outer_select()->context,
                                                              optimizer->arguments(),
                                                              (char *)"<no matter>",
3118
                                                              &exists_outer_expr_name)),
Monty's avatar
Monty committed
3119
                          optimizer) :
unknown's avatar
unknown committed
3120 3121 3122 3123 3124 3125 3126 3127 3128 3129
            (Item *)optimizer);
    }
    else
    {
      List<Item> *and_list= new List<Item>;
      if (!and_list)
      {
        res= TRUE;
        goto out;
      }
3130
      for (size_t i= 0; i < eqs.elements(); i++)
unknown's avatar
unknown committed
3131 3132 3133 3134
      {
        if (optimizer->arguments()[0]->maybe_null)
        {
          and_list->
Monty's avatar
Monty committed
3135 3136 3137 3138 3139
            push_front(new (thd->mem_root)
                       Item_func_isnotnull(thd,
                                           new (thd->mem_root)
                                           Item_direct_ref(thd,
                                                           &unit->outer_select()->context,
3140
                                                           optimizer->arguments()[0]->addr((int)i),
Monty's avatar
Monty committed
3141
                                                           (char *)"<no matter>",
3142
                                                           &exists_outer_expr_name)),
3143
                       thd->mem_root);
unknown's avatar
unknown committed
3144 3145 3146 3147
        }
      }
      if (and_list->elements > 0)
      {
3148
        and_list->push_front(optimizer, thd->mem_root);
Monty's avatar
Monty committed
3149
        exp= new (thd->mem_root) Item_cond_and(thd, *and_list);
unknown's avatar
unknown committed
3150 3151 3152 3153 3154
      }
      else
        exp= optimizer;
    }
    upper_not->arguments()[0]= exp;
3155
    if (exp->fix_fields_if_needed(thd, upper_not->arguments()))
unknown's avatar
unknown committed
3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169
    {
      res= TRUE;
      goto out;
    }
  }

out:
  thd->lex->current_select= save_select;
  if (arena)
    thd->restore_active_arena(arena, &backup);
  DBUG_RETURN(res);
}


unknown's avatar
unknown committed
3170
/**
unknown's avatar
unknown committed
3171
  Prepare IN/ALL/ANY/SOME subquery transformation and call the appropriate
unknown's avatar
unknown committed
3172
  transformation function.
3173

unknown's avatar
unknown committed
3174 3175
  @param join    JOIN object of transforming subquery

3176 3177
  @notes
  To decide which transformation procedure (scalar or row) applicable here
unknown's avatar
unknown committed
3178 3179
  we have to call fix_fields() for the left expression to be able to call
  cols() method on it. Also this method makes arena management for
3180 3181
  underlying transformation methods.

unknown's avatar
unknown committed
3182 3183
  @retval  false  OK
  @retval  true   Error
3184 3185
*/

unknown's avatar
unknown committed
3186
bool
3187
Item_in_subselect::select_in_like_transformer(JOIN *join)
3188
{
3189
  Query_arena *arena= 0, backup;
3190
  SELECT_LEX *current= thd->lex->current_select;
3191
  const char *save_where= thd->where;
unknown's avatar
unknown committed
3192
  bool trans_res= true;
3193 3194 3195
  bool result;

  DBUG_ENTER("Item_in_subselect::select_in_like_transformer");
3196
  DBUG_ASSERT(thd == join->thd);
unknown's avatar
unknown committed
3197

unknown's avatar
unknown committed
3198 3199 3200 3201 3202 3203
  /*
    IN/SOME/ALL/ANY subqueries aren't support LIMIT clause. Without it
    ORDER BY clause becomes meaningless thus we drop it here.
  */
  for (SELECT_LEX *sl= current->master_unit()->first_select();
       sl; sl= sl->next_select())
3204
  {
unknown's avatar
unknown committed
3205
    if (sl->join)
3206
    {
unknown's avatar
unknown committed
3207 3208
      sl->join->order= 0;
      sl->join->skip_sort_order= 1;
3209 3210 3211
    }
  }

3212 3213 3214 3215 3216 3217
  thd->where= "IN/ALL/ANY subquery";

  /*
    In some optimisation cases we will not need this Item_in_optimizer
    object, but we can't know it here, but here we need address correct
    reference on left expresion.
3218

Sergey Petrunya's avatar
Sergey Petrunya committed
3219 3220
    note: we won't need Item_in_optimizer when handling degenerate cases
    like "... IN (SELECT 1)"
3221
  */
3222
  arena= thd->activate_stmt_arena_if_needed(&backup);
3223 3224
  if (!optimizer)
  {
3225 3226
    optimizer= new (thd->mem_root) Item_in_optimizer(thd, left_expr_orig, this);
    if ((result= !optimizer))
3227
      goto out;
3228 3229
  }

3230
  thd->lex->current_select= current->return_after_parsing();
unknown's avatar
unknown committed
3231
  result= optimizer->fix_left(thd);
3232
  thd->lex->current_select= current;
3233 3234 3235 3236 3237 3238 3239 3240

  if (changed)
  {
    trans_res= false;
    goto out;
  }


3241
  if (result)
3242
    goto out;
3243 3244 3245 3246 3247 3248 3249 3250

  /*
    Both transformers call fix_fields() only for Items created inside them,
    and all that items do not make permanent changes in current item arena
    which allow to us call them with changed arena (if we do not know nature
    of Item, we have to call fix_fields() for it only with original arena to
    avoid memory leack)
  */
unknown's avatar
unknown committed
3251
  if (left_expr->cols() == 1)
unknown's avatar
unknown committed
3252
    trans_res= single_value_transformer(join);
3253 3254 3255 3256 3257
  else
  {
    /* we do not support row operation for ALL/ANY/SOME */
    if (func != &eq_creator)
    {
unknown's avatar
unknown committed
3258
      if (arena)
unknown's avatar
unknown committed
3259
        thd->restore_active_arena(arena, &backup);
3260
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
3261
      DBUG_RETURN(true);
3262
    }
unknown's avatar
unknown committed
3263
    trans_res= row_value_transformer(join);
3264
  }
3265
out:
3266
  if (arena)
unknown's avatar
unknown committed
3267
    thd->restore_active_arena(arena, &backup);
3268
  thd->where= save_where;
unknown's avatar
unknown committed
3269
  DBUG_RETURN(trans_res);
unknown's avatar
unknown committed
3270 3271
}

3272

3273
void Item_in_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3274
{
unknown's avatar
unknown committed
3275
  if (test_strategy(SUBS_IN_TO_EXISTS))
3276
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
3277 3278
  else
  {
3279
    left_expr->print(str, query_type);
3280
    str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
3281
  }
3282
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
3283 3284
}

3285
bool Item_exists_subselect::fix_fields(THD *thd, Item **ref)
unknown's avatar
unknown committed
3286 3287 3288
{
  DBUG_ENTER("Item_exists_subselect::fix_fields");
  if (exists_transformed)
Monty's avatar
Monty committed
3289
    DBUG_RETURN( !( (*ref)= new (thd->mem_root) Item_int(thd, 1)));
3290
  DBUG_RETURN(Item_subselect::fix_fields(thd, ref));
unknown's avatar
unknown committed
3291 3292
}

unknown's avatar
unknown committed
3293

3294
bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
3295
{
3296 3297
  uint outer_cols_num;
  List<Item> *inner_cols;
3298
  char const *save_where= thd_arg->where;
unknown's avatar
unknown committed
3299
  DBUG_ENTER("Item_in_subselect::fix_fields");
3300

3301 3302
  thd= thd_arg;
  DBUG_ASSERT(unit->thd == thd);
3303

unknown's avatar
unknown committed
3304
  if (test_strategy(SUBS_SEMI_JOIN))
Monty's avatar
Monty committed
3305
    DBUG_RETURN( !( (*ref)= new (thd->mem_root) Item_int(thd, 1)) );
3306

3307
  thd->where= "IN/ALL/ANY subquery";
3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330
  /*
    Check if the outer and inner IN operands match in those cases when we
    will not perform IN=>EXISTS transformation. Currently this is when we
    use subquery materialization.

    The condition below is true when this method was called recursively from
    inside JOIN::prepare for the JOIN object created by the call chain
    Item_subselect::fix_fields -> subselect_single_select_engine::prepare,
    which creates a JOIN object for the subquery and calls JOIN::prepare for
    the JOIN of the subquery.
    Notice that in some cases, this doesn't happen, and the check_cols()
    test for each Item happens later in
    Item_in_subselect::row_value_in_to_exists_transformer.
    The reason for this mess is that our JOIN::prepare phase works top-down
    instead of bottom-up, so we first do name resoluton and semantic checks
    for the outer selects, then for the inner.
  */
  if (engine &&
      engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE &&
      ((subselect_single_select_engine*)engine)->join)
  {
    outer_cols_num= left_expr->cols();

3331
    if (unit->is_unit_op())
3332 3333 3334 3335 3336 3337
      inner_cols= &(unit->types);
    else
      inner_cols= &(unit->first_select()->item_list);
    if (outer_cols_num != inner_cols->elements)
    {
      my_error(ER_OPERAND_COLUMNS, MYF(0), outer_cols_num);
3338
      goto err;
3339 3340 3341 3342 3343 3344 3345 3346 3347
    }
    if (outer_cols_num > 1)
    {
      List_iterator<Item> inner_col_it(*inner_cols);
      Item *inner_col;
      for (uint i= 0; i < outer_cols_num; i++)
      {
        inner_col= inner_col_it++;
        if (inner_col->check_cols(left_expr->element_index(i)->cols()))
3348
          goto err;
3349 3350 3351 3352
      }
    }
  }

3353
  if (left_expr && left_expr->fix_fields_if_needed(thd_arg, &left_expr))
3354
    goto err;
3355
  else
3356
  if (Item_subselect::fix_fields(thd_arg, ref))
3357
    goto err;
3358
  fixed= TRUE;
3359
  thd->where= save_where;
unknown's avatar
unknown committed
3360
  DBUG_RETURN(FALSE);
3361 3362 3363

err:
  thd->where= save_where;
3364
  DBUG_RETURN(TRUE);
3365 3366 3367
}


3368 3369
void Item_in_subselect::fix_after_pullout(st_select_lex *new_parent,
                                          Item **ref, bool merge)
unknown's avatar
unknown committed
3370
{
3371 3372
  left_expr->fix_after_pullout(new_parent, &left_expr, merge);
  Item_subselect::fix_after_pullout(new_parent, ref, merge);
3373
  used_tables_cache |= left_expr->used_tables();
unknown's avatar
unknown committed
3374 3375
}

3376
void Item_in_subselect::update_used_tables()
unknown's avatar
unknown committed
3377
{
3378 3379
  Item_subselect::update_used_tables();
  left_expr->update_used_tables();
3380 3381
  //used_tables_cache |= left_expr->used_tables();
  used_tables_cache= Item_subselect::used_tables() | left_expr->used_tables();
unknown's avatar
unknown committed
3382 3383
}

3384

3385
/**
3386 3387
  Try to create and initialize an engine to compute a subselect via
  materialization.
3388 3389

  @details
3390 3391 3392 3393 3394
  The method creates a new engine for materialized execution, and initializes
  the engine. The initialization may fail
  - either because it wasn't possible to create the needed temporary table
    and its index,
  - or because of a memory allocation error,
3395 3396 3397 3398 3399

  @returns
    @retval TRUE  memory allocation error occurred
    @retval FALSE an execution method was chosen successfully
*/
unknown's avatar
unknown committed
3400

3401
bool Item_in_subselect::setup_mat_engine()
3402
{
3403 3404
  subselect_hash_sj_engine       *mat_engine= NULL;
  subselect_single_select_engine *select_engine;
3405

3406
  DBUG_ENTER("Item_in_subselect::setup_mat_engine");
3407
  DBUG_ASSERT(thd);
3408

3409 3410 3411 3412 3413 3414 3415
  /*
    The select_engine (that executes transformed IN=>EXISTS subselects) is
    pre-created at parse time, and is stored in statment memory (preserved
    across PS executions).
  */
  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE);
  select_engine= (subselect_single_select_engine*) engine;
3416

3417 3418 3419
  /* Create/initialize execution objects. */
  if (!(mat_engine= new subselect_hash_sj_engine(thd, this, select_engine)))
    DBUG_RETURN(TRUE);
3420

3421 3422
  if (mat_engine->prepare(thd) ||
      mat_engine->init(&select_engine->join->fields_list,
Sergey Petrunya's avatar
Sergey Petrunya committed
3423
                       engine->get_identifier()))
3424
    DBUG_RETURN(TRUE);
3425

3426 3427
  engine= mat_engine;
  DBUG_RETURN(FALSE);
3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445
}


/**
  Initialize the cache of the left operand of the IN predicate.

  @note This method has the same purpose as alloc_group_fields(),
  but it takes a different kind of collection of items, and the
  list we push to is dynamically allocated.

  @retval TRUE  if a memory allocation error occurred or the cache is
                not applicable to the current query
  @retval FALSE if success
*/

bool Item_in_subselect::init_left_expr_cache()
{
  JOIN *outer_join;
3446
  DBUG_ASSERT(thd);
3447 3448 3449 3450 3451 3452

  outer_join= unit->outer_select()->join;
  /*
    An IN predicate might be evaluated in a query for which all tables have
    been optimzied away.
  */ 
3453
  if (!outer_join || !outer_join->table_count || !outer_join->tables_list)
3454 3455 3456 3457 3458 3459 3460 3461 3462
    return TRUE;

  if (!(left_expr_cache= new List<Cached_item>))
    return TRUE;

  for (uint i= 0; i < left_expr->cols(); i++)
  {
    Cached_item *cur_item_cache= new_Cached_item(thd,
                                                 left_expr->element_index(i),
3463
                                                 FALSE);
3464 3465
    if (!cur_item_cache || left_expr_cache->push_front(cur_item_cache,
                                                       thd->mem_root))
3466 3467 3468 3469 3470 3471
      return TRUE;
  }
  return FALSE;
}


3472
bool Item_in_subselect::init_cond_guards()
3473
{
3474
  DBUG_ASSERT(thd);
3475
  uint cols_num= left_expr->cols();
3476 3477
  if (!abort_on_null && !pushed_cond_guards &&
      (left_expr->maybe_null || cols_num > 1))
3478 3479 3480 3481 3482 3483 3484
  {
    if (!(pushed_cond_guards= (bool*)thd->alloc(sizeof(bool) * cols_num)))
        return TRUE;
    for (uint i= 0; i < cols_num; i++)
      pushed_cond_guards[i]= TRUE;
  }
  return FALSE;
3485 3486 3487
}


unknown's avatar
unknown committed
3488
bool
unknown's avatar
unknown committed
3489
Item_allany_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
3490
{
3491
  DBUG_ENTER("Item_allany_subselect::select_transformer");
unknown's avatar
unknown committed
3492
  DBUG_ASSERT((in_strategy & ~(SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE |
unknown's avatar
unknown committed
3493
                               SUBS_IN_TO_EXISTS | SUBS_STRATEGY_CHOSEN)) == 0);
3494 3495
  if (upper_item)
    upper_item->show= 1;
3496
  DBUG_RETURN(select_in_like_transformer(join));
unknown's avatar
unknown committed
3497 3498
}

unknown's avatar
unknown committed
3499

3500
void Item_allany_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3501
{
unknown's avatar
unknown committed
3502
  if (test_strategy(SUBS_IN_TO_EXISTS))
3503
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
3504 3505
  else
  {
3506
    left_expr->print(str, query_type);
unknown's avatar
unknown committed
3507
    str->append(' ');
unknown's avatar
unknown committed
3508 3509
    str->append(func->symbol(all));
    str->append(all ? " all " : " any ", 5);
unknown's avatar
unknown committed
3510
  }
3511
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
3512 3513 3514
}


unknown's avatar
unknown committed
3515 3516
void Item_allany_subselect::no_rows_in_result()
{
unknown's avatar
unknown committed
3517 3518 3519 3520 3521 3522 3523 3524
  /*
    Subquery predicates outside of the SELECT list must be evaluated in order
    to possibly filter the special result row generated for implicit grouping
    if the subquery is in the HAVING clause.
    If the predicate is constant, we need its actual value in the only result
    row for queries with implicit grouping.
  */
  if (parsing_place != SELECT_LIST || const_item())
unknown's avatar
unknown committed
3525
    return;
unknown's avatar
unknown committed
3526 3527 3528 3529 3530 3531 3532
  value= 0;
  null_value= 0;
  was_null= 0;
  make_const();
}


3533 3534 3535 3536 3537 3538 3539 3540
void subselect_engine::set_thd(THD *thd_arg)
{
  thd= thd_arg;
  if (result)
    result->set_thd(thd_arg);
}


3541
subselect_single_select_engine::
3542
subselect_single_select_engine(st_select_lex *select,
3543
			       select_result_interceptor *result_arg,
3544
			       Item_subselect *item_arg)
3545
  :subselect_engine(item_arg, result_arg),
3546
   prepared(0), executed(0),
3547
   select_lex(select), join(0)
unknown's avatar
unknown committed
3548
{
3549
  select_lex->master_unit()->item= item_arg;
unknown's avatar
unknown committed
3550 3551
}

3552 3553 3554 3555
int subselect_single_select_engine::get_identifier()
{
  return select_lex->select_number; 
}
unknown's avatar
unknown committed
3556

Igor Babaev's avatar
Igor Babaev committed
3557 3558 3559 3560 3561
void subselect_single_select_engine::force_reexecution()
{ 
  executed= false;
}

unknown's avatar
unknown committed
3562 3563
void subselect_single_select_engine::cleanup()
{
unknown's avatar
unknown committed
3564
  DBUG_ENTER("subselect_single_select_engine::cleanup");
3565
  prepared= executed= 0;
3566
  join= 0;
3567
  result->cleanup();
3568
  select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
unknown's avatar
unknown committed
3569
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
3570
}
3571

unknown's avatar
unknown committed
3572 3573 3574 3575 3576

void subselect_union_engine::cleanup()
{
  DBUG_ENTER("subselect_union_engine::cleanup");
  unit->reinit_exec_mechanism();
3577
  result->cleanup();
3578 3579 3580
  unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
  for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
    sl->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
unknown's avatar
unknown committed
3581
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
3582
}
3583

unknown's avatar
unknown committed
3584

3585 3586 3587 3588 3589
bool subselect_union_engine::is_executed() const
{
  return unit->executed;
}

Igor Babaev's avatar
Igor Babaev committed
3590 3591 3592 3593 3594
void subselect_union_engine::force_reexecution()
{ 
  unit->executed= false;
}

3595

3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613
/*
  Check if last execution of the subquery engine produced any rows

  SYNOPSIS
    subselect_union_engine::no_rows()

  DESCRIPTION
    Check if last execution of the subquery engine produced any rows. The
    return value is undefined if last execution ended in an error.

  RETURN
    TRUE  - Last subselect execution has produced no rows
    FALSE - Otherwise
*/

bool subselect_union_engine::no_rows()
{
  /* Check if we got any rows when reading UNION result from temp. table: */
3614 3615 3616 3617 3618 3619 3620 3621
  if (unit->fake_select_lex)
  {
    JOIN *join= unit->fake_select_lex->join;
    if (join)
      return MY_TEST(!join->send_records);
    return false;
  }
  return MY_TEST(!(((select_union_direct *)(unit->get_union_result()))
3622
                                                            ->send_records));
3623 3624
}

3625

unknown's avatar
unknown committed
3626 3627 3628
void subselect_uniquesubquery_engine::cleanup()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
Sergey Petrunya's avatar
Sergey Petrunya committed
3629 3630 3631 3632 3633 3634 3635 3636
  /* 
    Note for mergers: we don't have to, and actually must not de-initialize
    tab->table->file here.
    - We don't have to, because free_tmp_table() will call ha_index_or_rnd_end
    - We must not do it, because tab->table may be a derived table which 
      has been already dropped by close_thread_tables(), while we here are
      called from cleanup_items()
  */
unknown's avatar
unknown committed
3637 3638 3639 3640
  DBUG_VOID_RETURN;
}


3641
subselect_union_engine::subselect_union_engine(st_select_lex_unit *u,
3642
					       select_result_interceptor *result_arg,
3643
					       Item_subselect *item_arg)
3644
  :subselect_engine(item_arg, result_arg)
unknown's avatar
unknown committed
3645 3646
{
  unit= u;
3647
  unit->item= item_arg;
unknown's avatar
unknown committed
3648 3649
}

3650

3651 3652 3653 3654
/**
  Create and prepare the JOIN object that represents the query execution
  plan for the subquery.

3655
  @details
3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676
  This method is called from Item_subselect::fix_fields. For prepared
  statements it is called both during the PREPARE and EXECUTE phases in the
  following ways:
  - During PREPARE the optimizer needs some properties
    (join->fields_list.elements) of the JOIN to proceed with preparation of
    the remaining query (namely to complete ::fix_fields for the subselect
    related classes. In the end of PREPARE the JOIN is deleted.
  - When we EXECUTE the query, Item_subselect::fix_fields is called again, and
    the JOIN object is re-created again, prepared and executed. In the end of
    execution it is deleted.
  In all cases the JOIN is created in runtime memory (not in the permanent
  memory root).

  @todo
  Re-check what properties of 'join' are needed during prepare, and see if
  we can avoid creating a JOIN during JOIN::prepare of the outer join.

  @retval 0  if success
  @retval 1  if error
*/

3677
int subselect_single_select_engine::prepare(THD *thd)
unknown's avatar
unknown committed
3678
{
unknown's avatar
unknown committed
3679 3680
  if (prepared)
    return 0;
3681
  set_thd(thd);
3682 3683 3684 3685
  if (select_lex->join)
  {
    select_lex->cleanup();
  }
3686 3687
  join= new JOIN(thd, select_lex->item_list,
		 select_lex->options | SELECT_NO_UNLOCK, result);
3688
  if (!join || !result)
3689
    return 1; /* Fatal error is set already. */
unknown's avatar
unknown committed
3690
  prepared= 1;
3691 3692
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
3693
  if (join->prepare(select_lex->table_list.first,
unknown's avatar
unknown committed
3694
		    select_lex->with_wild,
unknown's avatar
unknown committed
3695
		    select_lex->where,
unknown's avatar
unknown committed
3696 3697
		    select_lex->order_list.elements +
		    select_lex->group_list.elements,
3698
		    select_lex->order_list.first,
3699
                    false,
3700
		    select_lex->group_list.first,
unknown's avatar
unknown committed
3701
		    select_lex->having,
3702
		    NULL, select_lex,
3703
		    select_lex->master_unit()))
unknown's avatar
unknown committed
3704
    return 1;
3705
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
3706 3707 3708
  return 0;
}

3709
int subselect_union_engine::prepare(THD *thd_arg)
unknown's avatar
unknown committed
3710
{
3711
  set_thd(thd_arg);
3712
  return unit->prepare(unit->derived, result, SELECT_NO_UNLOCK);
unknown's avatar
unknown committed
3713 3714
}

3715
int subselect_uniquesubquery_engine::prepare(THD *)
3716
{
3717 3718
  /* Should never be called. */
  DBUG_ASSERT(FALSE);
3719 3720 3721
  return 1;
}

3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743

/*
  Check if last execution of the subquery engine produced any rows

  SYNOPSIS
    subselect_single_select_engine::no_rows()

  DESCRIPTION
    Check if last execution of the subquery engine produced any rows. The
    return value is undefined if last execution ended in an error.

  RETURN
    TRUE  - Last subselect execution has produced no rows
    FALSE - Otherwise
*/

bool subselect_single_select_engine::no_rows()
{ 
  return !item->assigned();
}


3744 3745
/**
 Makes storage for the output values for the subquery and calcuates
3746
 their data and column types and their nullability.
3747 3748
*/
bool subselect_engine::set_row(List<Item> &item_list, Item_cache **row)
3749
{
3750
  Item *sel_item;
3751
  List_iterator_fast<Item> li(item_list);
3752
  set_handler(&type_handler_varchar);
3753 3754 3755
  for (uint i= 0; (sel_item= li++); i++)
  {
    item->max_length= sel_item->max_length;
3756
    set_handler(sel_item->type_handler());
3757
    item->decimals= sel_item->decimals;
3758
    item->unsigned_flag= sel_item->unsigned_flag;
unknown's avatar
unknown committed
3759
    maybe_null= sel_item->maybe_null;
3760
    if (!(row[i]= sel_item->get_cache(thd)))
3761
      return TRUE;
3762
    row[i]->setup(thd, sel_item);
3763
 //psergey-backport-timours:   row[i]->store(sel_item);
3764
  }
3765
  if (item_list.elements > 1)
3766
    set_handler(&type_handler_row);
3767
  return FALSE;
3768 3769
}

3770
bool subselect_single_select_engine::fix_length_and_dec(Item_cache **row)
3771
{
3772
  DBUG_ASSERT(row || select_lex->item_list.elements==1);
3773 3774
  if (set_row(select_lex->item_list, row))
    return TRUE;
3775
  item->collation.set(row[0]->collation);
unknown's avatar
unknown committed
3776 3777
  if (cols() != 1)
    maybe_null= 0;
3778
  return FALSE;
3779 3780
}

3781
bool subselect_union_engine::fix_length_and_dec(Item_cache **row)
3782 3783 3784 3785
{
  DBUG_ASSERT(row || unit->first_select()->item_list.elements==1);

  if (unit->first_select()->item_list.elements == 1)
3786
  {
3787 3788
    if (set_row(unit->types, row))
      return TRUE;
3789 3790
    item->collation.set(row[0]->collation);
  }
3791 3792
  else
  {
3793
    bool maybe_null_saved= maybe_null;
3794 3795
    if (set_row(unit->types, row))
      return TRUE;
3796
    maybe_null= maybe_null_saved;
3797
  }
3798
  return FALSE;
3799
}
unknown's avatar
unknown committed
3800

3801
bool subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
3802 3803 3804
{
  //this never should be called
  DBUG_ASSERT(0);
3805
  return FALSE;
3806 3807
}

Konstantin Osipov's avatar
Konstantin Osipov committed
3808 3809
int  read_first_record_seq(JOIN_TAB *tab);
int rr_sequential(READ_RECORD *info);
3810 3811 3812
int join_read_always_key_or_null(JOIN_TAB *tab);
int join_read_next_same_or_null(READ_RECORD *info);

3813
int subselect_single_select_engine::exec()
unknown's avatar
unknown committed
3814 3815
{
  DBUG_ENTER("subselect_single_select_engine::exec");
3816

unknown's avatar
unknown committed
3817 3818 3819
  char const *save_where= thd->where;
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
Michael Widenius's avatar
Michael Widenius committed
3820

3821
  if (join->optimization_state == JOIN::NOT_OPTIMIZED)
unknown's avatar
unknown committed
3822
  {
3823 3824
    SELECT_LEX_UNIT *unit= select_lex->master_unit();

3825
    unit->set_limit(unit->global_parameters());
unknown's avatar
unknown committed
3826 3827
    if (join->optimize())
    {
unknown's avatar
unknown committed
3828
      thd->where= save_where;
3829
      executed= 1;
unknown's avatar
unknown committed
3830
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
3831
      DBUG_RETURN(join->error ? join->error : 1);
unknown's avatar
unknown committed
3832
    }
unknown's avatar
unknown committed
3833
    if (!select_lex->uncacheable && thd->lex->describe && 
3834
        !(join->select_options & SELECT_DESCRIBE))
unknown's avatar
unknown committed
3835
    {
3836 3837 3838
      item->update_used_tables();
      if (item->const_item())
      {
3839 3840 3841 3842 3843 3844 3845 3846
        /*
          It's necessary to keep original JOIN table because
          create_sort_index() function may overwrite original
          JOIN_TAB::type and wrong optimization method can be
          selected on re-execution.
        */
        select_lex->uncacheable|= UNCACHEABLE_EXPLAIN;
        select_lex->master_unit()->uncacheable|= UNCACHEABLE_EXPLAIN;
3847
      }
unknown's avatar
unknown committed
3848
    }
3849
    if (item->engine_changed(this))
Igor Babaev's avatar
Igor Babaev committed
3850 3851
    {
      thd->lex->current_select= save_select;
3852
      DBUG_RETURN(1);
Igor Babaev's avatar
Igor Babaev committed
3853
    }
unknown's avatar
unknown committed
3854
  }
3855 3856 3857
  if (select_lex->uncacheable &&
      select_lex->uncacheable != UNCACHEABLE_EXPLAIN
      && executed)
unknown's avatar
unknown committed
3858 3859
  {
    if (join->reinit())
3860
    {
unknown's avatar
unknown committed
3861 3862
      thd->where= save_where;
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
3863
      DBUG_RETURN(1);
3864
    }
3865
    item->reset();
unknown's avatar
unknown committed
3866 3867 3868 3869
    item->assigned((executed= 0));
  }
  if (!executed)
  {
3870
    item->reset_value_registration();
3871 3872 3873
    JOIN_TAB *changed_tabs[MAX_TABLES];
    JOIN_TAB **last_changed_tab= changed_tabs;
    if (item->have_guarded_conds())
3874 3875
    {
      /*
3876
        For at least one of the pushed predicates the following is true:
3877 3878 3879 3880
        We should not apply optimizations based on the condition that was
        pushed down into the subquery. Those optimizations are ref[_or_null]
        acceses. Change them to be full table scans.
      */
3881 3882 3883
      JOIN_TAB *tab;
      for (tab= first_linear_tab(join, WITH_BUSH_ROOTS, WITHOUT_CONST_TABLES);
           tab; tab= next_linear_tab(join, tab, WITH_BUSH_ROOTS))
3884
      {
3885
        if (tab && tab->keyuse)
3886
        {
3887 3888 3889 3890 3891 3892
          for (uint i= 0; i < tab->ref.key_parts; i++)
          {
            bool *cond_guard= tab->ref.cond_guards[i];
            if (cond_guard && !*cond_guard)
            {
              /* Change the access method to full table scan */
3893
              tab->save_read_first_record= tab->read_first_record;
3894 3895
              tab->save_read_record= tab->read_record.read_record_func;
              tab->read_record.read_record_func= rr_sequential;
Konstantin Osipov's avatar
Konstantin Osipov committed
3896
              tab->read_first_record= read_first_record_seq;
3897 3898 3899
              tab->read_record.record= tab->table->record[0];
              tab->read_record.thd= join->thd;
              tab->read_record.ref_length= tab->table->file->ref_length;
3900
              tab->read_record.unlock_row= rr_unlock_row;
3901 3902 3903 3904
              *(last_changed_tab++)= tab;
              break;
            }
          }
3905 3906 3907 3908
        }
      }
    }
    
unknown's avatar
unknown committed
3909
    join->exec();
3910

3911 3912
    /* Enable the optimizations back */
    for (JOIN_TAB **ptab= changed_tabs; ptab != last_changed_tab; ptab++)
3913
    {
3914 3915 3916
      JOIN_TAB *tab= *ptab;
      tab->read_record.record= 0;
      tab->read_record.ref_length= 0;
3917 3918
      tab->read_first_record= tab->save_read_first_record;
      tab->read_record.read_record_func= tab->save_read_record;
3919
    }
unknown's avatar
unknown committed
3920
    executed= 1;
Igor Babaev's avatar
Igor Babaev committed
3921 3922
    if (!(uncacheable() & ~UNCACHEABLE_EXPLAIN) &&
        !item->with_recursive_reference)
unknown's avatar
unknown committed
3923
      item->make_const();
unknown's avatar
unknown committed
3924 3925
    thd->where= save_where;
    thd->lex->current_select= save_select;
3926
    DBUG_RETURN(join->error || thd->is_fatal_error || thd->is_error());
unknown's avatar
unknown committed
3927
  }
unknown's avatar
unknown committed
3928 3929
  thd->where= save_where;
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
3930 3931 3932
  DBUG_RETURN(0);
}

3933
int subselect_union_engine::exec()
unknown's avatar
unknown committed
3934
{
unknown's avatar
unknown committed
3935
  char const *save_where= thd->where;
3936
  int res= unit->exec();
unknown's avatar
unknown committed
3937
  thd->where= save_where;
3938
  return res;
unknown's avatar
unknown committed
3939 3940
}

3941

3942
/*
3943
  Search for at least one row satisfying select condition
3944 3945 3946 3947 3948 3949 3950 3951
 
  SYNOPSIS
    subselect_uniquesubquery_engine::scan_table()

  DESCRIPTION
    Scan the table using sequential access until we find at least one row
    satisfying select condition.
    
3952 3953
    The caller must set this->empty_result_set=FALSE before calling this
    function. This function will set it to TRUE if it finds a matching row.
3954 3955 3956 3957 3958 3959 3960

  RETURN
    FALSE - OK
    TRUE  - Error
*/

int subselect_uniquesubquery_engine::scan_table()
3961 3962 3963
{
  int error;
  TABLE *table= tab->table;
3964 3965
  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");

3966 3967 3968 3969 3970 3971 3972 3973
  if ((table->file->inited &&
       (error= table->file->ha_index_end())) ||
      (error= table->file->ha_rnd_init(1)))
  {
    (void) report_error(table, error);
    DBUG_RETURN(true);
  }

3974
  table->file->extra_opt(HA_EXTRA_CACHE,
3975
                         get_thd()->variables.read_buff_size);
3976 3977
  table->null_row= 0;
  for (;;)
3978
  {
3979
    error=table->file->ha_rnd_next(table->record[0]);
3980 3981
    if (unlikely(error))
    {
3982 3983 3984 3985 3986 3987 3988 3989 3990 3991
      if (error == HA_ERR_END_OF_FILE)
      {
        error= 0;
        break;
      }
      else
      {
        error= report_error(table, error);
        break;
      }
3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 4005
    }

    if (!cond || cond->val_int())
    {
      empty_result_set= FALSE;
      break;
    }
  }

  table->file->ha_rnd_end();
  DBUG_RETURN(error != 0);
}


4006 4007
/**
  Copy ref key for index access into the only subquery table.
unknown's avatar
unknown committed
4008

4009
  @details
4010 4011 4012 4013 4014 4015
    Copy ref key and check for conversion problems.
    If there is an error converting the left IN operand to the column type of
    the right IN operand count it as no match. In this case IN has the value of
    FALSE. We mark the subquery table cursor as having no more rows (to ensure
    that the processing that follows will not find a match) and return FALSE,
    so IN is not treated as returning NULL.
4016

4017 4018 4019
  @returns
    @retval FALSE The outer ref was copied into an index lookup key.
    @retval TRUE  The outer ref cannot possibly match any row, IN is FALSE.
4020 4021
*/

4022
bool subselect_uniquesubquery_engine::copy_ref_key(bool skip_constants)
4023 4024 4025
{
  DBUG_ENTER("subselect_uniquesubquery_engine::copy_ref_key");

4026 4027 4028
  for (store_key **copy= tab->ref.key_copy ; *copy ; copy++)
  {
    enum store_key::store_key_result store_res;
4029
    if (skip_constants && (*copy)->store_key_is_const())
Igor Babaev's avatar
Igor Babaev committed
4030
      continue;
4031 4032 4033 4034 4035 4036 4037 4038 4039
    store_res= (*copy)->copy();
    tab->ref.key_err= store_res;

    if (store_res == store_key::STORE_KEY_FATAL)
    {
      /*
       Error converting the left IN operand to the column type of the right
       IN operand. 
      */
4040
      DBUG_RETURN(true);
4041 4042
    }
  }
4043
  DBUG_RETURN(false);
4044 4045 4046
}


4047 4048
/**
  Execute subselect via unique index lookup
4049

4050
  @details
4051 4052 4053 4054 4055 4056 4057 4058 4059
    Find rows corresponding to the ref key using index access.
    If some part of the lookup key is NULL, then we're evaluating
      NULL IN (SELECT ... )
    This is a special case, we don't need to search for NULL in the table,
    instead, the result value is 
      - NULL  if select produces empty row set
      - FALSE otherwise.

    In some cases (IN subselect is a top level item, i.e. abort_on_null==TRUE)
4060
    the caller doesn't distinguish between NULL and FALSE result and we just
4061
    return FALSE. 
4062 4063 4064 4065 4066
    Otherwise we make a full table scan to see if there is at least one 
    matching row.
    
    The result of this function (info about whether a row was found) is
    stored in this->empty_result_set.
4067
    
4068 4069 4070 4071
  @returns
    @retval 0  OK
    @retval 1  notify caller to call Item_subselect::reset(),
               in most cases reset() sets the result to NULL
4072
*/
4073

4074
int subselect_uniquesubquery_engine::exec()
4075 4076 4077 4078
{
  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
  int error;
  TABLE *table= tab->table;
4079
  empty_result_set= TRUE;
unknown's avatar
unknown committed
4080
  table->status= 0;
4081
  Item_in_subselect *in_subs= (Item_in_subselect *) item;
4082 4083 4084

  if (!tab->preread_init_done && tab->preread_init())
    DBUG_RETURN(1);
4085
 
4086
  if (in_subs->left_expr_has_null())
4087 4088
  {
    /*
4089 4090
      The case when all values in left_expr are NULL is handled by
      Item_in_optimizer::val_int().
4091
    */
4092 4093 4094 4095
    if (in_subs->is_top_level_item())
      DBUG_RETURN(1); /* notify caller to call reset() and set NULL value. */
    else
      DBUG_RETURN(scan_table());
4096
  }
4097

4098
  if (copy_ref_key(true))
unknown's avatar
unknown committed
4099
  {
4100 4101
    /* We know that there will be no rows even if we scan. */
    in_subs->value= 0;
unknown's avatar
unknown committed
4102 4103
    DBUG_RETURN(0);
  }
4104

4105 4106 4107 4108 4109 4110 4111
  if (!table->file->inited &&
      (error= table->file->ha_index_init(tab->ref.key, 0)))
  {
    (void) report_error(table, error);
    DBUG_RETURN(true);
  }

4112 4113 4114 4115 4116
  error= table->file->ha_index_read_map(table->record[0],
                                        tab->ref.key_buff,
                                        make_prev_keypart_map(tab->
                                                              ref.key_parts),
                                        HA_READ_KEY_EXACT);
4117 4118
  if (unlikely(error &&
               error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE))
4119
    error= report_error(table, error);
4120 4121
  else
  {
4122 4123
    error= 0;
    table->null_row= 0;
4124 4125 4126 4127 4128 4129 4130
    if (!table->status && (!cond || cond->val_int()))
    {
      ((Item_in_subselect *) item)->value= 1;
      empty_result_set= FALSE;
    }
    else
      ((Item_in_subselect *) item)->value= 0;
4131
  }
4132

4133
  DBUG_RETURN(error != 0);
4134 4135
}

4136

4137
/*
4138
  TIMOUR: write comment
4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154
*/

int subselect_uniquesubquery_engine::index_lookup()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::index_lookup");
  int error;
  TABLE *table= tab->table;
 
  if (!table->file->inited)
    table->file->ha_index_init(tab->ref.key, 0);
  error= table->file->ha_index_read_map(table->record[0],
                                        tab->ref.key_buff,
                                        make_prev_keypart_map(tab->
                                                              ref.key_parts),
                                        HA_READ_KEY_EXACT);
  DBUG_PRINT("info", ("lookup result: %i", error));
4155

4156 4157
  if (unlikely(error && error != HA_ERR_KEY_NOT_FOUND &&
               error != HA_ERR_END_OF_FILE))
4158
  {
4159 4160 4161 4162 4163 4164
    /*
      TIMOUR: I don't understand at all when do we need to call report_error.
      In most places where we access an index, we don't do this. Why here?
    */
    error= report_error(table, error);
    DBUG_RETURN(error);
4165 4166
  }

4167 4168 4169 4170 4171 4172 4173
  table->null_row= 0;
  if (!error && (!cond || cond->val_int()))
    ((Item_in_subselect *) item)->value= 1;
  else
    ((Item_in_subselect *) item)->value= 0;

  DBUG_RETURN(0);
4174 4175 4176 4177
}



4178
subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
4179
{
4180
  /* Tell handler we don't need the index anymore */
4181 4182
  //psergey-merge-todo: the following was gone in 6.0:
 //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
4183 4184
}

4185

4186 4187
/**
  Execute subselect via unique index lookup
4188

4189
  @details
4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203
    The engine is used to resolve subqueries in form

      oe IN (SELECT key FROM tbl WHERE subq_where) 

    The value of the predicate is calculated as follows: 
    1. If oe IS NULL, this is a special case, do a full table scan on
       table tbl and search for row that satisfies subq_where. If such 
       row is found, return NULL, otherwise return FALSE.
    2. Make an index lookup via key=oe, search for a row that satisfies
       subq_where. If found, return TRUE.
    3. If check_null==TRUE, make another lookup via key=NULL, search for a 
       row that satisfies subq_where. If found, return NULL, otherwise
       return FALSE.

4204
  @todo
4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222
    The step #1 can be optimized further when the index has several key
    parts. Consider a subquery:
    
      (oe1, oe2) IN (SELECT keypart1, keypart2 FROM tbl WHERE subq_where)

    and suppose we need to evaluate it for {oe1, oe2}=={const1, NULL}.
    Current code will do a full table scan and obtain correct result. There
    is a better option: instead of evaluating

      SELECT keypart1, keypart2 FROM tbl WHERE subq_where            (1)

    and checking if it has produced any matching rows, evaluate
    
      SELECT keypart2 FROM tbl WHERE subq_where AND keypart1=const1  (2)

    If this query produces a row, the result is NULL (as we're evaluating 
    "(const1, NULL) IN { (const1, X), ... }", which has a value of UNKNOWN,
    i.e. NULL).  If the query produces no rows, the result is FALSE.
4223

4224 4225 4226 4227
    We currently evaluate (1) by doing a full table scan. (2) can be
    evaluated by doing a "ref" scan on "keypart1=const1", which can be much
    cheaper. We can use index statistics to quickly check whether "ref" scan
    will be cheaper than full table scan.
4228

4229 4230 4231 4232
  @returns
    @retval 0  OK
    @retval 1  notify caller to call Item_subselect::reset(),
               in most cases reset() sets the result to NULL
4233 4234
*/

4235
int subselect_indexsubquery_engine::exec()
4236
{
4237
  DBUG_ENTER("subselect_indexsubquery_engine");
4238
  int error;
4239
  bool null_finding= 0;
4240
  TABLE *table= tab->table;
4241
  Item_in_subselect *in_subs= (Item_in_subselect *) item;
4242

4243
  ((Item_in_subselect *) item)->value= 0;
4244
  empty_result_set= TRUE;
4245
  table->status= 0;
4246

4247 4248
  if (check_null)
  {
4249
    /* We need to check for NULL if there wasn't a matching value */
4250
    *tab->ref.null_ref_key= 0;			// Search first for not null
4251 4252 4253
    ((Item_in_subselect *) item)->was_null= 0;
  }

4254
  if (!tab->preread_init_done && tab->preread_init())
4255 4256
    DBUG_RETURN(1);

4257
  if (in_subs->left_expr_has_null())
4258
  {
4259 4260 4261
    /*
      The case when all values in left_expr are NULL is handled by
      Item_in_optimizer::val_int().
4262
    */
4263 4264 4265 4266
    if (in_subs->is_top_level_item())
      DBUG_RETURN(1); /* notify caller to call reset() and set NULL value. */
    else
      DBUG_RETURN(scan_table());
4267 4268
  }

4269
  if (copy_ref_key(true))
4270 4271 4272 4273 4274
  {
    /* We know that there will be no rows even if we scan. */
    in_subs->value= 0;
    DBUG_RETURN(0);
  }
4275

4276 4277 4278 4279 4280 4281
  if (!table->file->inited &&
      (error= table->file->ha_index_init(tab->ref.key, 1)))
  {
    (void) report_error(table, error);
    DBUG_RETURN(true);
  }
Sergei Golubchik's avatar
Sergei Golubchik committed
4282

4283 4284 4285 4286 4287
  error= table->file->ha_index_read_map(table->record[0],
                                        tab->ref.key_buff,
                                        make_prev_keypart_map(tab->
                                                              ref.key_parts),
                                        HA_READ_KEY_EXACT);
4288 4289
  if (unlikely(error &&
               error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE))
4290
    error= report_error(table, error);
4291 4292
  else
  {
4293
    for (;;)
4294
    {
4295 4296 4297
      error= 0;
      table->null_row= 0;
      if (!table->status)
4298
      {
4299
        if ((!cond || cond->val_int()) && (!having || having->val_int()))
4300
        {
4301
          empty_result_set= FALSE;
4302 4303 4304 4305 4306 4307
          if (null_finding)
            ((Item_in_subselect *) item)->was_null= 1;
          else
            ((Item_in_subselect *) item)->value= 1;
          break;
        }
4308 4309 4310
        error= table->file->ha_index_next_same(table->record[0],
                                               tab->ref.key_buff,
                                               tab->ref.key_length);
4311
        if (unlikely(error && error != HA_ERR_END_OF_FILE))
4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323
        {
          error= report_error(table, error);
          break;
        }
      }
      else
      {
        if (!check_null || null_finding)
          break;			/* We don't need to check nulls */
        *tab->ref.null_ref_key= 1;
        null_finding= 1;
        /* Check if there exists a row with a null value in the index */
4324
        if (unlikely((error= (safe_index_read(tab) == 1))))
4325
          break;
4326
      }
4327 4328
    }
  }
4329
  DBUG_RETURN(error != 0);
4330 4331
}

4332

4333
uint subselect_single_select_engine::cols() const
unknown's avatar
unknown committed
4334
{
4335 4336 4337 4338
  //psergey-sj-backport: the following assert was gone in 6.0:
  //DBUG_ASSERT(select_lex->join != 0); // should be called after fix_fields()
  //return select_lex->join->fields_list.elements;
  return select_lex->item_list.elements;
unknown's avatar
unknown committed
4339 4340
}

unknown's avatar
unknown committed
4341

4342
uint subselect_union_engine::cols() const
unknown's avatar
unknown committed
4343
{
4344 4345
  DBUG_ASSERT(unit->is_prepared());  // should be called after fix_fields()
  return unit->types.elements;
unknown's avatar
unknown committed
4346 4347
}

unknown's avatar
unknown committed
4348

4349
uint8 subselect_single_select_engine::uncacheable()
4350 4351 4352 4353
{
  return select_lex->uncacheable;
}

unknown's avatar
unknown committed
4354

4355
uint8 subselect_union_engine::uncacheable()
4356 4357 4358 4359
{
  return unit->uncacheable;
}

unknown's avatar
unknown committed
4360

unknown's avatar
unknown committed
4361 4362 4363 4364 4365 4366 4367 4368 4369
void subselect_single_select_engine::exclude()
{
  select_lex->master_unit()->exclude_level();
}

void subselect_union_engine::exclude()
{
  unit->exclude_level();
}
4370

unknown's avatar
unknown committed
4371

4372
void subselect_uniquesubquery_engine::exclude()
4373 4374 4375 4376
{
  //this never should be called
  DBUG_ASSERT(0);
}
4377 4378


4379
table_map subselect_engine::calc_const_tables(List<TABLE_LIST> &list)
4380 4381
{
  table_map map= 0;
4382 4383 4384 4385
  List_iterator<TABLE_LIST> ti(list);
  TABLE_LIST *table;
  //for (; table; table= table->next_leaf)
  while ((table= ti++))
4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396
  {
    TABLE *tbl= table->table;
    if (tbl && tbl->const_table)
      map|= tbl->map;
  }
  return map;
}


table_map subselect_single_select_engine::upper_select_const_tables()
{
4397
  return calc_const_tables(select_lex->outer_select()->leaf_tables);
4398 4399
}

unknown's avatar
merge  
unknown committed
4400

4401 4402
table_map subselect_union_engine::upper_select_const_tables()
{
4403
  return calc_const_tables(unit->outer_select()->leaf_tables);
4404
}
unknown's avatar
merge  
unknown committed
4405 4406


4407 4408
void subselect_single_select_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
4409
{
4410 4411 4412
  With_clause* with_clause= select_lex->get_with_clause();
  if (with_clause)
    with_clause->print(str, query_type);
4413
  select_lex->print(get_thd(), str, query_type);
unknown's avatar
unknown committed
4414 4415 4416
}


4417
void subselect_union_engine::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
4418
{
4419
  unit->print(str, query_type);
unknown's avatar
unknown committed
4420 4421 4422
}


4423 4424
void subselect_uniquesubquery_engine::print(String *str,
                                            enum_query_type query_type)
unknown's avatar
unknown committed
4425
{
4426
  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
4427
  tab->ref.items[0]->print(str, query_type);
4428
  str->append(STRING_WITH_LEN(" in "));
4429 4430 4431 4432 4433 4434 4435 4436 4437
  if (tab->table->s->table_category == TABLE_CATEGORY_TEMPORARY)
  {
    /*
      Temporary tables' names change across runs, so they can't be used for
      EXPLAIN EXTENDED.
    */
    str->append(STRING_WITH_LEN("<temporary table>"));
  }
  else
Michael Widenius's avatar
Michael Widenius committed
4438
    str->append(&tab->table->s->table_name);
unknown's avatar
unknown committed
4439
  KEY *key_info= tab->table->key_info+ tab->ref.key;
4440
  str->append(STRING_WITH_LEN(" on "));
4441
  str->append(&key_info->name);
unknown's avatar
unknown committed
4442 4443
  if (cond)
  {
4444
    str->append(STRING_WITH_LEN(" where "));
4445
    cond->print(str, query_type);
unknown's avatar
unknown committed
4446 4447 4448 4449
  }
  str->append(')');
}

4450 4451 4452 4453 4454 4455 4456 4457 4458
/*
TODO:
The above ::print method should be changed as below. Do it after
all other tests pass.

void subselect_uniquesubquery_engine::print(String *str)
{
  KEY *key_info= tab->table->key_info + tab->ref.key;
  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
4459
  for (uint i= 0; i < key_info->user_defined_key_parts; i++)
4460 4461
    tab->ref.items[i]->print(str);
  str->append(STRING_WITH_LEN(" in "));
Michael Widenius's avatar
Michael Widenius committed
4462
  str->append(&tab->table->s->table_name);
4463
  str->append(STRING_WITH_LEN(" on "));
4464
  str->append(&key_info->name);
4465 4466 4467 4468 4469 4470 4471 4472
  if (cond)
  {
    str->append(STRING_WITH_LEN(" where "));
    cond->print(str);
  }
  str->append(')');
}
*/
unknown's avatar
unknown committed
4473

4474 4475
void subselect_indexsubquery_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
4476
{
4477
  str->append(STRING_WITH_LEN("<index_lookup>("));
4478
  tab->ref.items[0]->print(str, query_type);
4479
  str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
4480
  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
unknown's avatar
unknown committed
4481
  KEY *key_info= tab->table->key_info+ tab->ref.key;
4482
  str->append(STRING_WITH_LEN(" on "));
4483
  str->append(&key_info->name);
unknown's avatar
unknown committed
4484
  if (check_null)
4485
    str->append(STRING_WITH_LEN(" checking NULL"));
4486
  if (cond)
unknown's avatar
unknown committed
4487
  {
4488
    str->append(STRING_WITH_LEN(" where "));
4489
    cond->print(str, query_type);
unknown's avatar
unknown committed
4490
  }
4491 4492 4493
  if (having)
  {
    str->append(STRING_WITH_LEN(" having "));
4494
    having->print(str, query_type);
4495
  }
unknown's avatar
unknown committed
4496 4497
  str->append(')');
}
4498

unknown's avatar
unknown committed
4499 4500
/**
  change select_result object of engine.
4501

unknown's avatar
unknown committed
4502 4503
  @param si		new subselect Item
  @param res		new select_result object
4504
  @param temp           temporary assignment
4505

unknown's avatar
unknown committed
4506
  @retval
unknown's avatar
unknown committed
4507
    FALSE OK
unknown's avatar
unknown committed
4508
  @retval
unknown's avatar
unknown committed
4509
    TRUE  error
4510 4511
*/

4512 4513 4514 4515
bool
subselect_single_select_engine::change_result(Item_subselect *si,
                                              select_result_interceptor *res,
                                              bool temp)
4516
{
unknown's avatar
unknown committed
4517
  DBUG_ENTER("subselect_single_select_engine::change_result");
4518
  item= si;
4519
  if (temp)
4520 4521 4522 4523 4524 4525
  {
    /*
      Here we reuse change_item_tree to roll back assignment.  It has
      nothing special about Item* pointer so it is safe conversion. We do
      not change the interface to be compatible with MySQL.
    */
4526
    thd->change_item_tree((Item**) &result, (Item*)res);
4527
  }
4528 4529
  else
    result= res;
4530 4531 4532 4533 4534 4535 4536 4537

  /*
    We can't use 'result' below as gcc 4.2.4's alias optimization
    assumes that result was not changed by thd->change_item_tree().
    I tried to find a solution to make gcc happy, but could not find anything
    that would not require a lot of extra code that would be harder to manage
    than the current code.
  */
4538
  DBUG_RETURN(select_lex->join->change_result(res, NULL));
4539 4540 4541
}


unknown's avatar
unknown committed
4542 4543
/**
  change select_result object of engine.
4544

unknown's avatar
unknown committed
4545 4546
  @param si		new subselect Item
  @param res		new select_result object
4547

unknown's avatar
unknown committed
4548
  @retval
unknown's avatar
unknown committed
4549
    FALSE OK
unknown's avatar
unknown committed
4550
  @retval
unknown's avatar
unknown committed
4551
    TRUE  error
4552 4553
*/

unknown's avatar
unknown committed
4554
bool subselect_union_engine::change_result(Item_subselect *si,
4555 4556
                                           select_result_interceptor *res,
                                           bool temp)
4557 4558 4559
{
  item= si;
  int rc= unit->change_result(res, result);
4560 4561 4562 4563
  if (temp)
    thd->change_item_tree((Item**) &result, (Item*)res);
  else
    result= res;
4564 4565 4566 4567
  return rc;
}


unknown's avatar
unknown committed
4568 4569
/**
  change select_result emulation, never should be called.
4570

unknown's avatar
unknown committed
4571 4572
  @param si		new subselect Item
  @param res		new select_result object
4573

unknown's avatar
unknown committed
4574
  @retval
unknown's avatar
unknown committed
4575
    FALSE OK
unknown's avatar
unknown committed
4576
  @retval
unknown's avatar
unknown committed
4577
    TRUE  error
4578 4579
*/

4580 4581 4582 4583 4584
bool
subselect_uniquesubquery_engine::change_result(Item_subselect *si,
                                               select_result_interceptor *res,
                                               bool temp
                                               __attribute__((unused)))
4585 4586
{
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
4587
  return TRUE;
4588
}
4589 4590


unknown's avatar
unknown committed
4591 4592
/**
  Report about presence of tables in subquery.
4593

unknown's avatar
unknown committed
4594
  @retval
4595
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
4596
  @retval
4597 4598 4599 4600 4601 4602 4603 4604
    FALSE there are some tables in subquery
*/
bool subselect_single_select_engine::no_tables()
{
  return(select_lex->table_list.elements == 0);
}


4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620
/*
  Check statically whether the subquery can return NULL

  SINOPSYS
    subselect_single_select_engine::may_be_null()

  RETURN
    FALSE  can guarantee that the subquery never return NULL
    TRUE   otherwise
*/
bool subselect_single_select_engine::may_be_null()
{
  return ((no_tables() && !join->conds && !join->having) ? maybe_null : 1);
}


unknown's avatar
unknown committed
4621 4622
/**
  Report about presence of tables in subquery.
4623

unknown's avatar
unknown committed
4624
  @retval
4625
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
4626
  @retval
4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639
    FALSE there are some tables in subquery
*/
bool subselect_union_engine::no_tables()
{
  for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
  {
    if (sl->table_list.elements)
      return FALSE;
  }
  return TRUE;
}


unknown's avatar
unknown committed
4640 4641
/**
  Report about presence of tables in subquery.
4642

unknown's avatar
unknown committed
4643
  @retval
4644
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
4645
  @retval
4646 4647 4648 4649 4650 4651
    FALSE there are some tables in subquery
*/

bool subselect_uniquesubquery_engine::no_tables()
{
  /* returning value is correct, but this method should never be called */
4652
  DBUG_ASSERT(FALSE);
4653 4654
  return 0;
}
4655 4656 4657 4658 4659 4660 4661


/******************************************************************************
  WL#1110 - Implementation of class subselect_hash_sj_engine
******************************************************************************/


4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675
/**
  Check if an IN predicate should be executed via partial matching using
  only schema information.

  @details
  This test essentially has three results:
  - partial matching is applicable, but cannot be executed due to a
    limitation in the total number of indexes, as a result we can't
    use subquery materialization at all.
  - partial matching is either applicable or not, and this can be
    determined by looking at 'this->max_keys'.
  If max_keys > 1, then we need partial matching because there are
  more indexes than just the one we use during materialization to
  remove duplicates.
4676 4677 4678 4679 4680 4681 4682 4683 4684

  @note
  TIMOUR: The schema-based analysis for partial matching can be done once for
  prepared statement and remembered. It is done here to remove the need to
  save/restore all related variables between each re-execution, thus making
  the code simpler.

  @retval PARTIAL_MATCH  if a partial match should be used
  @retval COMPLETE_MATCH if a complete match (index lookup) should be used
4685 4686
*/

4687 4688
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_schema()
4689 4690 4691 4692
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;

  if (item_in->is_top_level_item())
4693
    return COMPLETE_MATCH;
4694 4695
  else
  {
Igor Babaev's avatar
Igor Babaev committed
4696
    List_iterator<Item> inner_col_it(*item_in->unit->get_column_types(false));
4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715
    Item *outer_col, *inner_col;

    for (uint i= 0; i < item_in->left_expr->cols(); i++)
    {
      outer_col= item_in->left_expr->element_index(i);
      inner_col= inner_col_it++;

      if (!inner_col->maybe_null && !outer_col->maybe_null)
        bitmap_set_bit(&non_null_key_parts, i);
      else
      {
        bitmap_set_bit(&partial_match_key_parts, i);
        ++count_partial_match_columns;
      }
    }
  }

  /* If no column contains NULLs use regular hash index lookups. */
  if (count_partial_match_columns)
4716 4717
    return PARTIAL_MATCH;
  return COMPLETE_MATCH;
4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728
}


/**
  Test whether an IN predicate must be computed via partial matching
  based on the NULL statistics for each column of a materialized subquery.

  @details The procedure analyzes column NULL statistics, updates the
  matching type of columns that cannot be NULL or that contain only NULLs.
  Based on this, the procedure determines the final execution strategy for
  the [NOT] IN predicate.
4729 4730 4731

  @retval PARTIAL_MATCH  if a partial match should be used
  @retval COMPLETE_MATCH if a complete match (index lookup) should be used
4732 4733
*/

4734 4735
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_data()
4736 4737 4738 4739 4740 4741
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
  Item *outer_col;

4742 4743 4744 4745 4746 4747
  /*
    If we already determined that a complete match is enough based on schema
    information, nothing can be better.
  */
  if (strategy == COMPLETE_MATCH)
    return COMPLETE_MATCH;
4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763

  for (uint i= 0; i < item_in->left_expr->cols(); i++)
  {
    if (!bitmap_is_set(&partial_match_key_parts, i))
      continue;
    outer_col= item_in->left_expr->element_index(i);
    /*
      If column 'i' doesn't contain NULLs, and the corresponding outer reference
      cannot have a NULL value, then 'i' is a non-nullable column.
    */
    if (result_sink->get_null_count_of_col(i) == 0 && !outer_col->maybe_null)
    {
      bitmap_clear_bit(&partial_match_key_parts, i);
      bitmap_set_bit(&non_null_key_parts, i);
      --count_partial_match_columns;
    }
unknown's avatar
unknown committed
4764
    if (result_sink->get_null_count_of_col(i) == tmp_table->file->stats.records)
4765
      ++count_null_only_columns;
unknown's avatar
unknown committed
4766 4767
    if (result_sink->get_null_count_of_col(i))
      ++count_columns_with_nulls;
4768 4769 4770 4771
  }

  /* If no column contains NULLs use regular hash index lookups. */
  if (!count_partial_match_columns)
4772 4773 4774
    return COMPLETE_MATCH;
  return PARTIAL_MATCH;
}
4775

4776 4777 4778 4779

void
subselect_hash_sj_engine::choose_partial_match_strategy(
  bool has_non_null_key, bool has_covering_null_row,
4780
  MY_BITMAP *partial_match_key_parts_arg)
4781
{
4782
  ulonglong pm_buff_size;
4783 4784 4785 4786 4787

  DBUG_ASSERT(strategy == PARTIAL_MATCH);
  /*
    Choose according to global optimizer switch. If only one of the switches is
    'ON', then the remaining strategy is the only possible one. The only cases
4788
    when this will be overridden is when the total size of all buffers for the
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
    merge strategy is bigger than the 'rowid_merge_buff_size' system variable,
    or if there isn't enough physical memory to allocate the buffers.
  */
  if (!optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
       optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
    strategy= PARTIAL_MATCH_SCAN;
  else if
     ( optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) &&
      !optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN))
    strategy= PARTIAL_MATCH_MERGE;

  /*
    If both switches are ON, or both are OFF, we interpret that as "let the
    optimizer decide". Perform a cost based choice between the two partial
    matching strategies.
  */
  /*
    TIMOUR: the above interpretation of the switch values could be changed to:
    - if both are ON - let the optimizer decide,
    - if both are OFF - do not use partial matching, therefore do not use
      materialization in non-top-level predicates.
    The problem with this is that we know for sure if we need partial matching
    only after the subquery is materialized, and this is too late to revert to
    the IN=>EXISTS strategy.
  */
  if (strategy == PARTIAL_MATCH)
  {
    /*
      TIMOUR: Currently we use a super simplistic measure. This will be
      addressed in a separate task.
    */
    if (tmp_table->file->stats.records < 100)
      strategy= PARTIAL_MATCH_SCAN;
    else
      strategy= PARTIAL_MATCH_MERGE;
  }

  /* Check if there is enough memory for the rowid merge strategy. */
  if (strategy == PARTIAL_MATCH_MERGE)
  {
    pm_buff_size= rowid_merge_buff_size(has_non_null_key,
                                        has_covering_null_row,
4831
                                        partial_match_key_parts_arg);
4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846
    if (pm_buff_size > thd->variables.rowid_merge_buff_size)
      strategy= PARTIAL_MATCH_SCAN;
  }
}


/*
  Compute the memory size of all buffers proportional to the number of rows
  in tmp_table.

  @details
  If the result is bigger than thd->variables.rowid_merge_buff_size, partial
  matching via merging is not applicable.
*/

4847
ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
4848 4849 4850
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
4851 4852
  /* Total size of all buffers used by partial matching. */
  ulonglong buff_size;
4853 4854 4855 4856
  ha_rows row_count= tmp_table->file->stats.records;
  uint rowid_length= tmp_table->file->ref_length;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
unknown's avatar
unknown committed
4857
  ha_rows max_null_row;
4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879

  /* Size of the subselect_rowid_merge_engine::row_num_to_rowid buffer. */
  buff_size= row_count * rowid_length * sizeof(uchar);

  if (has_non_null_key)
  {
    /* Add the size of Ordered_key::key_buff of the only non-NULL key. */
    buff_size+= row_count * sizeof(rownum_t);
  }

  if (!has_covering_null_row)
  {
    for (uint i= 0; i < partial_match_key_parts->n_bits; i++)
    {
      if (!bitmap_is_set(partial_match_key_parts, i) ||
          result_sink->get_null_count_of_col(i) == row_count)
        continue; /* In these cases we wouldn't construct Ordered keys. */

      /* Add the size of Ordered_key::key_buff */
      buff_size+= (row_count - result_sink->get_null_count_of_col(i)) *
                         sizeof(rownum_t);
      /* Add the size of Ordered_key::null_key */
unknown's avatar
unknown committed
4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891
      max_null_row= result_sink->get_max_null_of_col(i);
      if (max_null_row >= UINT_MAX)
      {
        /*
          There can be at most UINT_MAX bits in a MY_BITMAP that is used to
          store NULLs in an Ordered_key. Return a number of bytes bigger than
          the maximum allowed memory buffer for partial matching to disable
          the rowid merge strategy.
        */
        return ULONGLONG_MAX;
      }
      buff_size+= bitmap_buffer_size(max_null_row);
4892 4893 4894 4895
    }
  }

  return buff_size;
4896 4897 4898 4899 4900 4901 4902 4903 4904 4905
}


/*
  Initialize a MY_BITMAP with a buffer allocated on the current
  memory root.
  TIMOUR: move to bitmap C file?
*/

static my_bool
4906
my_bitmap_init_memroot(MY_BITMAP *map, uint n_bits, MEM_ROOT *mem_root)
4907 4908 4909 4910 4911
{
  my_bitmap_map *bitmap_buf;

  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(mem_root,
                                                bitmap_buffer_size(n_bits))) ||
4912
      my_bitmap_init(map, bitmap_buf, n_bits, FALSE))
4913 4914 4915 4916 4917 4918
    return TRUE;
  bitmap_clear_all(map);
  return FALSE;
}


4919 4920 4921 4922
/**
  Create all structures needed for IN execution that can live between PS
  reexecution.

4923
  @param tmp_columns the items that produce the data for the temp table
4924 4925
  @param subquery_id subquery's identifier (to make "<subquery%d>" name for
                                            EXPLAIN)
4926 4927

  @details
4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940
  - Create a temporary table to store the result of the IN subquery. The
    temporary table has one hash index on all its columns.
  - Create a new result sink that sends the result stream of the subquery to
    the temporary table,

  @notice:
    Currently Item_subselect::init() already chooses and creates at parse
    time an engine with a corresponding JOIN to execute the subquery.

  @retval TRUE  if error
  @retval FALSE otherwise
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
4941
bool subselect_hash_sj_engine::init(List<Item> *tmp_columns, uint subquery_id)
4942
{
4943
  THD *thd= get_thd();
4944
  select_unit *result_sink;
4945
  /* Options to create_tmp_table. */
4946
  ulonglong tmp_create_options= thd->variables.option_bits | TMP_TABLE_ALL_COLUMNS;
4947
                             /* | TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM */
4948

4949
  DBUG_ENTER("subselect_hash_sj_engine::init");
4950

4951
  if (my_bitmap_init_memroot(&non_null_key_parts, tmp_columns->elements,
4952
                            thd->mem_root) ||
4953
      my_bitmap_init_memroot(&partial_match_key_parts, tmp_columns->elements,
4954 4955
                            thd->mem_root))
    DBUG_RETURN(TRUE);
4956 4957 4958 4959 4960 4961

  /*
    Create and initialize a select result interceptor that stores the
    result stream in a temporary table. The temporary table itself is
    managed (created/filled/etc) internally by the interceptor.
  */
4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974
/*
  TIMOUR:
  Select a more efficient result sink when we know there is no need to collect
  data statistics.

  if (strategy == COMPLETE_MATCH)
  {
    if (!(result= new select_union))
      DBUG_RETURN(TRUE);
  }
  else if (strategy == PARTIAL_MATCH)
  {
  if (!(result= new select_materialize_with_stats))
4975
    DBUG_RETURN(TRUE);
4976 4977
  }
*/
4978
  if (!(result_sink= new (thd->mem_root) select_materialize_with_stats(thd)))
4979
    DBUG_RETURN(TRUE);
Sergey Petrunya's avatar
Sergey Petrunya committed
4980
    
4981
  char buf[32];
4982 4983 4984
  LEX_CSTRING name;
  name.length= my_snprintf(buf, sizeof(buf), "<subquery%u>", subquery_id);
  if (!(name.str= (char*) thd->memdup(buf, name.length + 1)))
4985
    DBUG_RETURN(TRUE);
4986

4987
  result_sink->get_tmp_table_param()->materialized_subquery= true;
Igor Babaev's avatar
Igor Babaev committed
4988 4989 4990 4991 4992
  if (item->substype() == Item_subselect::IN_SUBS && 
      ((Item_in_subselect*)item)->is_jtbm_merged)
  {
    result_sink->get_tmp_table_param()->force_not_null_cols= true;
  }
4993 4994
  if (result_sink->create_result_table(thd, tmp_columns, TRUE,
                                       tmp_create_options,
4995
				       &name, TRUE, TRUE, FALSE, 0))
4996 4997
    DBUG_RETURN(TRUE);

4998 4999
  tmp_table= result_sink->table;
  result= result_sink;
5000 5001

  /*
5002
    If the subquery has blobs, or the total key length is bigger than
5003
    some length, or the total number of key parts is more than the
5004
    allowed maximum (currently MAX_REF_PARTS == 32), then the created
5005 5006 5007 5008
    index cannot be used for lookups and we can't use hash semi
    join. If this is the case, delete the temporary table since it
    will not be used, and tell the caller we failed to initialize the
    engine.
5009 5010 5011
  */
  if (tmp_table->s->keys == 0)
  {
5012 5013
    //fprintf(stderr, "Q: %s\n", current_thd->query());
    DBUG_ASSERT(0);
5014 5015 5016
    DBUG_ASSERT(
      tmp_table->s->uniques ||
      tmp_table->key_info->key_length >= tmp_table->file->max_key_length() ||
5017 5018
      tmp_table->key_info->user_defined_key_parts >
      tmp_table->file->max_key_parts());
5019
    free_tmp_table(thd, tmp_table);
5020
    tmp_table= NULL;
5021 5022 5023 5024 5025 5026 5027 5028 5029
    delete result;
    result= NULL;
    DBUG_RETURN(TRUE);
  }

  /*
    Make sure there is only one index on the temp table, and it doesn't have
    the extra key part created when s->uniques > 0.
  */
5030 5031
  DBUG_ASSERT(tmp_table->s->keys == 1 &&
              ((Item_in_subselect *) item)->left_expr->cols() ==
5032
              tmp_table->key_info->user_defined_key_parts);
5033

5034 5035 5036
  if (make_semi_join_conds() ||
      /* A unique_engine is used both for complete and partial matching. */
      !(lookup_engine= make_unique_engine()))
5037
    DBUG_RETURN(TRUE);
5038

5039 5040 5041 5042
  /*
    Repeat name resolution for 'cond' since cond is not part of any
    clause of the query, and it is not 'fixed' during JOIN::prepare.
  */
5043 5044
  if (semi_join_conds &&
      semi_join_conds->fix_fields_if_needed(thd, (Item**)&semi_join_conds))
5045 5046 5047
    DBUG_RETURN(TRUE);
  /* Let our engine reuse this query plan for materialization. */
  materialize_join= materialize_engine->join;
5048
  materialize_join->change_result(result, NULL);
5049

5050 5051
  DBUG_RETURN(FALSE);
}
5052 5053


5054 5055 5056
/*
  Create an artificial condition to post-filter those rows matched by index
  lookups that cannot be distinguished by the index lookup procedure.
5057

5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072
  @notes
  The need for post-filtering may occur e.g. because of
  truncation. Prepared statements execution requires that fix_fields is
  called for every execution. In order to call fix_fields we need to
  create a Name_resolution_context and a corresponding TABLE_LIST for
  the temporary table for the subquery, so that all column references
  to the materialized subquery table can be resolved correctly.

  @returns
    @retval TRUE  memory allocation error occurred
    @retval FALSE the conditions were created and resolved (fixed)
*/

bool subselect_hash_sj_engine::make_semi_join_conds()
{
5073 5074 5075 5076 5077
  /*
    Table reference for tmp_table that is used to resolve column references
    (Item_fields) to columns in tmp_table.
  */
  TABLE_LIST *tmp_table_ref;
5078 5079 5080
  /* Name resolution context for all tmp_table columns created below. */
  Name_resolution_context *context;
  Item_in_subselect *item_in= (Item_in_subselect *) item;
5081
  LEX_CSTRING table_name;
5082 5083 5084
  DBUG_ENTER("subselect_hash_sj_engine::make_semi_join_conds");
  DBUG_ASSERT(semi_join_conds == NULL);

Monty's avatar
Monty committed
5085
  if (!(semi_join_conds= new (thd->mem_root) Item_cond_and(thd)))
5086 5087
    DBUG_RETURN(TRUE);

5088 5089 5090
  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
    DBUG_RETURN(TRUE);

5091 5092 5093
  table_name.str=    tmp_table->alias.c_ptr();
  table_name.length= tmp_table->alias.length(),
  tmp_table_ref->init_one_table(&empty_clex_str, &table_name, NULL, TL_READ);
5094 5095
  tmp_table_ref->table= tmp_table;

5096
  context= new Name_resolution_context;
5097 5098 5099
  context->init();
  context->first_name_resolution_table=
    context->last_name_resolution_table= tmp_table_ref;
5100
  semi_join_conds_context= context;
5101
  
5102
  for (uint i= 0; i < item_in->left_expr->cols(); i++)
5103
  {
5104 5105
    /* New equi-join condition for the current column. */
    Item_func_eq *eq_cond;
5106 5107 5108
    /* Item for the corresponding field from the materialized temp table. */
    Item_field *right_col_item;

5109
    if (!(right_col_item= new (thd->mem_root)
5110
          Item_temptable_field(thd, context, tmp_table->field[i])) ||
5111 5112 5113 5114
        !(eq_cond= new (thd->mem_root)
          Item_func_eq(thd, item_in->left_expr->element_index(i),
                       right_col_item)) ||
        (((Item_cond_and*)semi_join_conds)->add(eq_cond, thd->mem_root)))
5115
    {
5116 5117
      delete semi_join_conds;
      semi_join_conds= NULL;
5118 5119 5120
      DBUG_RETURN(TRUE);
    }
  }
5121
  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
5122 5123 5124 5125 5126 5127 5128
    DBUG_RETURN(TRUE);

  DBUG_RETURN(FALSE);
}


/**
5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142
  Create a new uniquesubquery engine for the execution of an IN predicate.

  @details
  Create and initialize a new JOIN_TAB, and Table_ref objects to perform
  lookups into the indexed temporary table.

  @retval A new subselect_hash_sj_engine object
  @retval NULL if a memory allocation error occurs
*/

subselect_uniquesubquery_engine*
subselect_hash_sj_engine::make_unique_engine()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
unknown's avatar
unknown committed
5143
  Item_iterator_row it(item_in->left_expr);
5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159
  /* The only index on the temporary table. */
  KEY *tmp_key= tmp_table->key_info;
  JOIN_TAB *tab;

  DBUG_ENTER("subselect_hash_sj_engine::make_unique_engine");

  /*
    Create and initialize the JOIN_TAB that represents an index lookup
    plan operator into the materialized subquery result. Notice that:
    - this JOIN_TAB has no corresponding JOIN (and doesn't need one), and
    - here we initialize only those members that are used by
      subselect_uniquesubquery_engine, so these objects are incomplete.
  */
  if (!(tab= (JOIN_TAB*) thd->alloc(sizeof(JOIN_TAB))))
    DBUG_RETURN(NULL);

unknown's avatar
unknown committed
5160
  tab->table= tmp_table;
5161
  tab->preread_init_done= FALSE;
unknown's avatar
unknown committed
5162
  tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
5163 5164 5165 5166 5167 5168

  DBUG_RETURN(new subselect_uniquesubquery_engine(thd, tab, item,
                                                  semi_join_conds));
}


5169 5170 5171 5172 5173 5174 5175
subselect_hash_sj_engine::~subselect_hash_sj_engine()
{
  delete lookup_engine;
  delete result;
  if (tmp_table)
    free_tmp_table(thd, tmp_table);
}
5176 5177


5178
int subselect_hash_sj_engine::prepare(THD *thd_arg)
5179 5180 5181 5182 5183
{
  /*
    Create and optimize the JOIN that will be used to materialize
    the subquery if not yet created.
  */
5184 5185
  set_thd(thd_arg);
  return materialize_engine->prepare(thd);
5186 5187 5188 5189 5190 5191
}


/**
  Cleanup performed after each PS execution.

5192
  @details
5193 5194 5195 5196 5197
  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
*/

void subselect_hash_sj_engine::cleanup()
{
5198
  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
5199
  is_materialized= FALSE;
5200 5201 5202 5203 5204
  bitmap_clear_all(&non_null_key_parts);
  bitmap_clear_all(&partial_match_key_parts);
  count_partial_match_columns= 0;
  count_null_only_columns= 0;
  strategy= UNDEFINED;
5205
  materialize_engine->cleanup();
5206 5207 5208 5209 5210 5211
  /*
    Restore the original Item_in_subselect engine. This engine is created once
    at parse time and stored across executions, while all other materialization
    related engines are created and chosen for each execution.
  */
  ((Item_in_subselect *) item)->engine= materialize_engine;
5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227
  if (lookup_engine_type == TABLE_SCAN_ENGINE ||
      lookup_engine_type == ROWID_MERGE_ENGINE)
  {
    subselect_engine *inner_lookup_engine;
    inner_lookup_engine=
      ((subselect_partial_match_engine*) lookup_engine)->lookup_engine;
    /*
      Partial match engines are recreated for each PS execution inside
      subselect_hash_sj_engine::exec().
    */
    delete lookup_engine;
    lookup_engine= inner_lookup_engine;
  }
  DBUG_ASSERT(lookup_engine->engine_type() == UNIQUESUBQUERY_ENGINE);
  lookup_engine->cleanup();
  result->cleanup(); /* Resets the temp table as well. */
5228 5229 5230
  DBUG_ASSERT(tmp_table);
  free_tmp_table(thd, tmp_table);
  tmp_table= NULL;
5231 5232 5233
}


5234 5235 5236 5237 5238 5239
/*
  Get fanout produced by tables specified in the table_map
*/

double get_fanout_with_deps(JOIN *join, table_map tset)
{
5240 5241 5242 5243
  /* Handle the case of "Impossible WHERE" */
  if (join->table_count == 0)
    return 0.0;

5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268
  /* First, recursively get all tables we depend on */
  table_map deps_to_check= tset;
  table_map checked_deps= 0;
  table_map further_deps;
  do
  {
    further_deps= 0;
    Table_map_iterator tm_it(deps_to_check);
    int tableno;
    while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
    {
      /* get tableno's dependency tables that are not in needed_set */
      further_deps |= join->map2table[tableno]->ref.depend_map & ~checked_deps;
    }

    checked_deps |= deps_to_check;
    deps_to_check= further_deps;
  } while (further_deps != 0);

  
  /* Now, walk the join order and calculate the fanout */
  double fanout= 1;
  for (JOIN_TAB *tab= first_top_level_tab(join, WITHOUT_CONST_TABLES); tab;
       tab= next_top_level_tab(join, tab))
  {
5269 5270 5271 5272 5273 5274 5275
    /* 
      Ignore SJM nests. They have tab->table==NULL. There is no point to walk
      inside them, because GROUP BY clause cannot refer to tables from within
      subquery.
    */
    if (!tab->is_sjm_nest() && (tab->table->map & checked_deps) && 
        !tab->emb_sj_nest && 
5276 5277
        tab->records_read != 0)
    {
5278
      fanout *= tab->records_read;
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 5314 5315 5316 5317 5318 5319 5320 5321 5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333 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
  return fanout;
}


#if 0
void check_out_index_stats(JOIN *join)
{
  ORDER *order;
  uint n_order_items;

  /*
    First, collect the keys that we can use in each table.
    We can use a key if 
    - all tables refer to it.
  */
  key_map key_start_use[MAX_TABLES];
  key_map key_infix_use[MAX_TABLES];
  table_map key_used=0;
  table_map non_key_used= 0;
  
  bzero(&key_start_use, sizeof(key_start_use)); //psergey-todo: safe initialization!
  bzero(&key_infix_use, sizeof(key_infix_use));
  
  for (order= join->group_list; order; order= order->next)
  {
    Item *item= order->item[0];

    if (item->real_type() == Item::FIELD_ITEM)
    {
      if (item->used_tables() & OUTER_REF_TABLE_BIT)
        continue; /* outside references are like constants for us */

      Field *field= ((Item_field*)item->real_item())->field;
      uint table_no= field->table->tablenr;
      if (!(non_key_used && table_map(1) << table_no) && 
          !field->part_of_key.is_clear_all())
      {
        key_map infix_map= field->part_of_key;
        infix_map.subtract(field->key_start);
        key_start_use[table_no].merge(field->key_start);
        key_infix_use[table_no].merge(infix_map);
        key_used |= table_no;
      }
      continue;
    }
    /* 
      Note: the below will cause clauses like GROUP BY YEAR(date) not to be
      handled. 
    */
    non_key_used |= item->used_tables();
  }
  
  Table_map_iterator tm_it(key_used & ~non_key_used);
  int tableno;
  while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
  {
    key_map::iterator key_it(key_start_use);
    int keyno;
    while ((keyno = tm_it.next_bit()) != key_map::iterator::BITMAP_END)
    {
      for (order= join->group_list; order; order= order->next)
      {
        Item *item= order->item[0];
        if (item->used_tables() & (table_map(1) << tableno))
        {
          DBUG_ASSERT(item->real_type() == Item::FIELD_ITEM);
        }
      }
      /*
      if (continuation)
      {
        walk through list and find which key parts are occupied;
        // note that the above can't be made any faster.
      }
      else
        use rec_per_key[0];
      
      find out the cardinality.
      check if cardinality decreases if we use it;
      */
    }
  }
}
#endif


5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384
/*
  Get an estimate of how many records will be produced after the GROUP BY
  operation.

  @param join           Join we're operating on 
  @param join_op_rows   How many records will be produced by the join
                        operations (this is what join optimizer produces)
  
  @seealso
     See also optimize_semijoin_nests(), grep for "Adjust output cardinality 
     estimates".  Very similar code there that is not joined with this one
     because we operate on different data structs and too much effort is
     needed to abstract them out.

  @return
     Number of records we expect to get after the GROUP BY operation
*/

5385
double get_post_group_estimate(JOIN* join, double join_op_rows)
5386 5387 5388 5389
{
  table_map tables_in_group_list= table_map(0);

  /* Find out which tables are used in GROUP BY list */
5390
  for (ORDER *order= join->group_list_for_estimates; order; order= order->next)
5391 5392
  {
    Item *item= order->item[0];
5393 5394
    table_map item_used_tables= item->used_tables();
    if (item_used_tables & RAND_TABLE_BIT)
5395 5396 5397 5398
    {
      /* Each join output record will be in its own group */
      return join_op_rows;
    }
5399
    tables_in_group_list|= item_used_tables;
5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410
  }
  tables_in_group_list &= ~PSEUDO_TABLE_BITS;

  /*
    Use join fanouts to calculate the max. number of records in the group-list
  */
  double fanout_rows[MAX_KEY];
  bzero(&fanout_rows, sizeof(fanout_rows));
  double out_rows;
  
  out_rows= get_fanout_with_deps(join, tables_in_group_list);
5411 5412 5413

#if 0
  /* The following will be needed when making use of index stats: */
5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431
  /* 
    Also generate max. number of records for each of the tables mentioned 
    in the group-list. We'll use that a baseline number that we'll try to 
    reduce by using
     - #table-records 
     - index statistics.
  */
  Table_map_iterator tm_it(tables_in_group_list);
  int tableno;
  while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
  {
    fanout_rows[tableno]= get_fanout_with_deps(join, table_map(1) << tableno);
  }
  
  /*
    Try to bring down estimates using index statistics.
  */
  //check_out_index_stats(join);
5432 5433
#endif

5434
  return out_rows;
5435 5436 5437 5438 5439 5440
}


/**
  Execute a subquery IN predicate via materialization.

5441
  @details
5442 5443 5444 5445 5446 5447 5448 5449 5450 5451
  If needed materialize the subquery into a temporary table, then
  copmpute the predicate via a lookup into this table.

  @retval TRUE  if error
  @retval FALSE otherwise
*/

int subselect_hash_sj_engine::exec()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
5452
  SELECT_LEX *save_select= thd->lex->current_select;
5453
  subselect_partial_match_engine *pm_engine= NULL;
5454
  int res= 0;
5455 5456 5457 5458 5459 5460 5461

  DBUG_ENTER("subselect_hash_sj_engine::exec");

  /*
    Optimize and materialize the subquery during the first execution of
    the subquery predicate.
  */
5462
  thd->lex->current_select= materialize_engine->select_lex;
5463
  /* The subquery should be optimized, and materialized only once. */
5464 5465
  DBUG_ASSERT(materialize_join->optimization_state == JOIN::OPTIMIZATION_DONE &&
              !is_materialized);
5466
  materialize_join->exec();
5467 5468
  if (unlikely((res= MY_TEST(materialize_join->error || thd->is_fatal_error ||
                             thd->is_error()))))
5469
    goto err;
5470

5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490
  /*
    TODO:
    - Unlock all subquery tables as we don't need them. To implement this
      we need to add new functionality to JOIN::join_free that can unlock
      all tables in a subquery (and all its subqueries).
    - The temp table used for grouping in the subquery can be freed
      immediately after materialization (yet it's done together with
      unlocking).
  */
  is_materialized= TRUE;
  /*
    If the subquery returned no rows, the temporary table is empty, so we know
    directly that the result of IN is FALSE. We first update the table
    statistics, then we test if the temporary table for the query result is
    empty.
  */
  tmp_table->file->info(HA_STATUS_VARIABLE);
  if (!tmp_table->file->stats.records)
  {
    /* The value of IN will not change during this execution. */
5491 5492
    item_in->reset();
    item_in->make_const();
5493
    item_in->set_first_execution();
5494
    thd->lex->current_select= save_select;
5495 5496 5497
    DBUG_RETURN(FALSE);
  }

5498 5499 5500 5501 5502 5503 5504 5505 5506
  /*
    TIMOUR: The schema-based analysis for partial matching can be done once for
    prepared statement and remembered. It is done here to remove the need to
    save/restore all related variables between each re-execution, thus making
    the code simpler.
  */
  strategy= get_strategy_using_schema();
  /* This call may discover that we don't need partial matching at all. */
  strategy= get_strategy_using_data();
5507 5508
  if (strategy == PARTIAL_MATCH)
  {
5509
    uint count_pm_keys; /* Total number of keys needed for partial matching. */
unknown's avatar
unknown committed
5510 5511 5512 5513
    MY_BITMAP *nn_key_parts= NULL; /* Key parts of the only non-NULL index. */
    uint count_non_null_columns= 0; /* Number of columns in nn_key_parts. */
    bool has_covering_null_row;
    bool has_covering_null_columns;
5514 5515
    select_materialize_with_stats *result_sink=
      (select_materialize_with_stats *) result;
unknown's avatar
unknown committed
5516
    uint field_count= tmp_table->s->fields;
5517

unknown's avatar
unknown committed
5518 5519 5520 5521 5522 5523 5524 5525
    if (count_partial_match_columns < field_count)
    {
      nn_key_parts= &non_null_key_parts;
      count_non_null_columns= bitmap_bits_set(nn_key_parts);
    }
    has_covering_null_row= (result_sink->get_max_nulls_in_row() == field_count);
    has_covering_null_columns= (count_non_null_columns +
                                count_null_only_columns == field_count);
5526

unknown's avatar
unknown committed
5527 5528 5529 5530 5531 5532 5533 5534 5535 5536 5537
    if (has_covering_null_row && has_covering_null_columns)
    {
      /*
        The whole table consist of only NULL values. The result of IN is
        a constant UNKNOWN.
      */
      DBUG_ASSERT(tmp_table->file->stats.records == 1);
      item_in->value= 0;
      item_in->null_value= 1;
      item_in->make_const();
      item_in->set_first_execution();
5538
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
5539 5540
      DBUG_RETURN(FALSE);
    }
5541

unknown's avatar
unknown committed
5542 5543
    if (has_covering_null_row)
    {
Sergei Golubchik's avatar
Sergei Golubchik committed
5544
      DBUG_ASSERT(count_partial_match_columns == field_count);
unknown's avatar
unknown committed
5545 5546 5547 5548
      count_pm_keys= 0;
    }
    else if (has_covering_null_columns)
      count_pm_keys= 1;
5549 5550
    else
      count_pm_keys= count_partial_match_columns - count_null_only_columns +
unknown's avatar
unknown committed
5551
                     (nn_key_parts ? 1 : 0);
5552

5553
    choose_partial_match_strategy(MY_TEST(nn_key_parts),
unknown's avatar
unknown committed
5554
                                  has_covering_null_row,
5555 5556 5557 5558
                                  &partial_match_key_parts);
    DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE ||
                strategy == PARTIAL_MATCH_SCAN);
    if (strategy == PARTIAL_MATCH_MERGE)
5559
    {
5560
      pm_engine=
5561
        new subselect_rowid_merge_engine((subselect_uniquesubquery_engine*)
5562 5563
                                         lookup_engine, tmp_table,
                                         count_pm_keys,
unknown's avatar
unknown committed
5564 5565
                                         has_covering_null_row,
                                         has_covering_null_columns,
unknown's avatar
unknown committed
5566
                                         count_columns_with_nulls,
5567 5568 5569
                                         item, result,
                                         semi_join_conds->argument_list());
      if (!pm_engine ||
5570
          pm_engine->prepare(thd) ||
5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582
          ((subselect_rowid_merge_engine*) pm_engine)->
            init(nn_key_parts, &partial_match_key_parts))
      {
        /*
          The call to init() would fail if there was not enough memory to allocate
          all buffers for the rowid merge strategy. In this case revert to table
          scanning which doesn't need any big buffers.
        */
        delete pm_engine;
        pm_engine= NULL;
        strategy= PARTIAL_MATCH_SCAN;
      }
5583
    }
5584 5585

    if (strategy == PARTIAL_MATCH_SCAN)
5586
    {
5587
      if (!(pm_engine=
5588
            new subselect_table_scan_engine((subselect_uniquesubquery_engine*)
5589 5590 5591
                                            lookup_engine, tmp_table,
                                            item, result,
                                            semi_join_conds->argument_list(),
unknown's avatar
unknown committed
5592
                                            has_covering_null_row,
unknown's avatar
unknown committed
5593
                                            has_covering_null_columns,
5594 5595
                                            count_columns_with_nulls)) ||
          pm_engine->prepare(thd))
5596 5597 5598 5599 5600
      {
        /* This is an irrecoverable error. */
        res= 1;
        goto err;
      }
5601 5602 5603
    }
  }

5604 5605
  if (pm_engine)
    lookup_engine= pm_engine;
5606 5607 5608 5609 5610
  item_in->change_engine(lookup_engine);

err:
  thd->lex->current_select= save_select;
  DBUG_RETURN(res);
5611 5612 5613 5614 5615 5616 5617 5618 5619 5620 5621 5622
}


/**
  Print the state of this engine into a string for debugging and views.
*/

void subselect_hash_sj_engine::print(String *str, enum_query_type query_type)
{
  str->append(STRING_WITH_LEN(" <materialize> ("));
  materialize_engine->print(str, query_type);
  str->append(STRING_WITH_LEN(" ), "));
5623 5624 5625

  if (lookup_engine)
    lookup_engine->print(str, query_type);
5626 5627
  else
    str->append(STRING_WITH_LEN(
5628
           "<engine selected at execution time>"
5629 5630
         ));
}
5631

5632
bool subselect_hash_sj_engine::fix_length_and_dec(Item_cache** row)
5633 5634
{
  DBUG_ASSERT(FALSE);
5635
  return FALSE;
5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 5646 5647 5648 5649
}

void subselect_hash_sj_engine::exclude()
{
  DBUG_ASSERT(FALSE);
}

bool subselect_hash_sj_engine::no_tables()
{
  DBUG_ASSERT(FALSE);
  return FALSE;
}

bool subselect_hash_sj_engine::change_result(Item_subselect *si,
5650 5651
                                             select_result_interceptor *res,
                                             bool temp __attribute__((unused)))
5652 5653 5654 5655 5656 5657
{
  DBUG_ASSERT(FALSE);
  return TRUE;
}


5658 5659 5660 5661
Ordered_key::Ordered_key(uint keyid_arg, TABLE *tbl_arg, Item *search_key_arg,
                         ha_rows null_count_arg, ha_rows min_null_row_arg,
                         ha_rows max_null_row_arg, uchar *row_num_to_rowid_arg)
  : keyid(keyid_arg), tbl(tbl_arg), search_key(search_key_arg),
5662 5663 5664 5665 5666 5667 5668 5669 5670 5671 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 5682
    row_num_to_rowid(row_num_to_rowid_arg), null_count(null_count_arg)
{
  DBUG_ASSERT(tbl->file->stats.records > null_count);
  key_buff_elements= tbl->file->stats.records - null_count;
  cur_key_idx= HA_POS_ERROR;

  DBUG_ASSERT((null_count && min_null_row_arg && max_null_row_arg) ||
              (!null_count && !min_null_row_arg && !max_null_row_arg));
  if (null_count)
  {
    /* The counters are 1-based, for key access we need 0-based indexes. */
    min_null_row= min_null_row_arg - 1;
    max_null_row= max_null_row_arg - 1;
  }
  else
    min_null_row= max_null_row= 0;
}


Ordered_key::~Ordered_key()
{
5683
  my_free(key_buff);
5684
  my_bitmap_free(&null_key);
5685 5686 5687 5688 5689 5690 5691 5692 5693 5694 5695 5696 5697 5698 5699 5700 5701
}


/*
  Cleanup that needs to be done for each PS (re)execution.
*/

void Ordered_key::cleanup()
{
  /*
    Currently these keys are recreated for each PS re-execution, thus
    there is nothing to cleanup, the whole object goes away after execution
    is over. All handler related initialization/deinitialization is done by
    the parent subselect_rowid_merge_engine object.
  */
}

5702

5703 5704 5705 5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 5719
/*
  Initialize a multi-column index.
*/

bool Ordered_key::init(MY_BITMAP *columns_to_index)
{
  THD *thd= tbl->in_use;
  uint cur_key_col= 0;
  Item_field *cur_tmp_field;
  Item_func_lt *fn_less_than;

  key_column_count= bitmap_bits_set(columns_to_index);
  key_columns= (Item_field**) thd->alloc(key_column_count *
                                         sizeof(Item_field*));
  compare_pred= (Item_func_lt**) thd->alloc(key_column_count *
                                            sizeof(Item_func_lt*));

unknown's avatar
unknown committed
5720 5721 5722
  if (!key_columns || !compare_pred)
    return TRUE; /* Revert to table scan partial match. */

5723 5724 5725 5726
  for (uint i= 0; i < columns_to_index->n_bits; i++)
  {
    if (!bitmap_is_set(columns_to_index, i))
      continue;
Monty's avatar
Monty committed
5727
    cur_tmp_field= new (thd->mem_root) Item_field(thd, tbl->field[i]);
5728
    /* Create the predicate (tmp_column[i] < outer_ref[i]). */
Monty's avatar
Monty committed
5729
    fn_less_than= new (thd->mem_root) Item_func_lt(thd, cur_tmp_field,
5730 5731 5732 5733 5734 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
                                   search_key->element_index(i));
    fn_less_than->fix_fields(thd, (Item**) &fn_less_than);
    key_columns[cur_key_col]= cur_tmp_field;
    compare_pred[cur_key_col]= fn_less_than;
    ++cur_key_col;
  }

  if (alloc_keys_buffers())
  {
    /* TIMOUR revert to partial match via table scan. */
    return TRUE;
  }
  return FALSE;
}


/*
  Initialize a single-column index.
*/

bool Ordered_key::init(int col_idx)
{
  THD *thd= tbl->in_use;

  key_column_count= 1;

  // TIMOUR: check for mem allocation err, revert to scan

  key_columns= (Item_field**) thd->alloc(sizeof(Item_field*));
  compare_pred= (Item_func_lt**) thd->alloc(sizeof(Item_func_lt*));

Monty's avatar
Monty committed
5761
  key_columns[0]= new (thd->mem_root) Item_field(thd, tbl->field[col_idx]);
5762
  /* Create the predicate (tmp_column[i] < outer_ref[i]). */
Monty's avatar
Monty committed
5763
  compare_pred[0]= new (thd->mem_root) Item_func_lt(thd, key_columns[0],
5764 5765 5766 5767 5768 5769 5770 5771 5772 5773 5774 5775
                                    search_key->element_index(col_idx));
  compare_pred[0]->fix_fields(thd, (Item**)&compare_pred[0]);

  if (alloc_keys_buffers())
  {
    /* TIMOUR revert to partial match via table scan. */
    return TRUE;
  }
  return FALSE;
}


5776 5777 5778 5779
/*
  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
*/

5780 5781 5782 5783
bool Ordered_key::alloc_keys_buffers()
{
  DBUG_ASSERT(key_buff_elements > 0);

5784
  if (!(key_buff= (rownum_t*) my_malloc((size_t)(key_buff_elements * 
5785
    sizeof(rownum_t)), MYF(MY_WME | MY_THREAD_SPECIFIC))))
5786 5787 5788 5789 5790 5791 5792
    return TRUE;

  /*
    TIMOUR: it is enough to create bitmaps with size
    (max_null_row - min_null_row), and then use min_null_row as
    lookup offset.
  */
5793
  /* Notice that max_null_row is max array index, we need count, so +1. */
5794
  if (my_bitmap_init(&null_key, NULL, (uint)(max_null_row + 1), FALSE))
5795 5796 5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 5815
    return TRUE;

  cur_key_idx= HA_POS_ERROR;

  return FALSE;
}


/*
  Quick sort comparison function that compares two rows of the same table
  indentfied with their row numbers.

  @retval -1
  @retval  0
  @retval +1
*/

int
Ordered_key::cmp_keys_by_row_data(ha_rows a, ha_rows b)
{
  uchar *rowid_a, *rowid_b;
Sergei Golubchik's avatar
Sergei Golubchik committed
5816
  int error;
5817
  int cmp_res;
5818 5819 5820 5821 5822 5823 5824 5825 5826
  /* The length in bytes of the rowids (positions) of tmp_table. */
  uint rowid_length= tbl->file->ref_length;

  if (a == b)
    return 0;
  /* Get the corresponding rowids. */
  rowid_a= row_num_to_rowid + a * rowid_length;
  rowid_b= row_num_to_rowid + b * rowid_length;
  /* Fetch the rows for comparison. */
5827
  if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[0], rowid_a))))
Michael Widenius's avatar
Michael Widenius committed
5828
  {
Michael Widenius's avatar
Michael Widenius committed
5829
    /* purecov: begin inspected */
5830
    tbl->file->print_error(error, MYF(ME_FATAL));  // Sets fatal_error
Michael Widenius's avatar
Michael Widenius committed
5831
    return 0;
Michael Widenius's avatar
Michael Widenius committed
5832
    /* purecov: end */
Michael Widenius's avatar
Michael Widenius committed
5833
  }
5834
  if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[1], rowid_b))))
Michael Widenius's avatar
Michael Widenius committed
5835
  {
Michael Widenius's avatar
Michael Widenius committed
5836
    /* purecov: begin inspected */
5837
    tbl->file->print_error(error, MYF(ME_FATAL));  // Sets fatal_error
Michael Widenius's avatar
Michael Widenius committed
5838
    return 0;
Michael Widenius's avatar
Michael Widenius committed
5839
    /* purecov: end */
Michael Widenius's avatar
Michael Widenius committed
5840
  }    
5841 5842 5843 5844 5845 5846 5847 5848 5849 5850 5851 5852 5853 5854 5855 5856 5857 5858 5859 5860 5861 5862 5863 5864 5865 5866 5867 5868
  /*
    Compare the two rows by the corresponding values of the indexed
    columns.
  */
  for (uint i= 0; i < key_column_count; i++)
  {
    Field *cur_field= key_columns[i]->field;
    if ((cmp_res= cur_field->cmp_offset(tbl->s->rec_buff_length)))
      return (cmp_res > 0 ? 1 : -1);
  }
  return 0;
}


int
Ordered_key::cmp_keys_by_row_data_and_rownum(Ordered_key *key,
                                             rownum_t* a, rownum_t* b)
{
  /* The result of comparing the two keys according to their row data. */
  int cmp_row_res= key->cmp_keys_by_row_data(*a, *b);
  if (cmp_row_res)
    return cmp_row_res;
  return (*a < *b) ? -1 : (*a > *b) ? 1 : 0;
}


void Ordered_key::sort_keys()
{
5869
  my_qsort2(key_buff, (size_t) key_buff_elements, sizeof(rownum_t),
5870 5871 5872 5873 5874 5875
            (qsort2_cmp) &cmp_keys_by_row_data_and_rownum, (void*) this);
  /* Invalidate the current row position. */
  cur_key_idx= HA_POS_ERROR;
}


5876
/*
5877 5878 5879
  The fraction of rows that do not contain NULL in the columns indexed by
  this key.

5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891
  @retval  1  if there are no NULLs
  @retval  0  if only NULLs
*/

double Ordered_key::null_selectivity()
{
  /* We should not be processing empty tables. */
  DBUG_ASSERT(tbl->file->stats.records);
  return (1 - (double) null_count / (double) tbl->file->stats.records);
}


5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906 5907 5908 5909 5910 5911 5912
/*
  Compare the value(s) of the current key in 'search_key' with the
  data of the current table record.

  @notes The comparison result follows from the way compare_pred
  is created in Ordered_key::init. Currently compare_pred compares
  a field in of the current row with the corresponding Item that
  contains the search key.

  @param row_num  Number of the row (not index in the key_buff array)

  @retval -1  if (current row  < search_key)
  @retval  0  if (current row == search_key)
  @retval +1  if (current row  > search_key)
*/

int Ordered_key::cmp_key_with_search_key(rownum_t row_num)
{
  /* The length in bytes of the rowids (positions) of tmp_table. */
  uint rowid_length= tbl->file->ref_length;
  uchar *cur_rowid= row_num_to_rowid + row_num * rowid_length;
Sergei Golubchik's avatar
Sergei Golubchik committed
5913
  int error;
5914
  int cmp_res;
5915

5916
  if (unlikely((error= tbl->file->ha_rnd_pos(tbl->record[0], cur_rowid))))
Michael Widenius's avatar
Michael Widenius committed
5917
  {
Michael Widenius's avatar
Michael Widenius committed
5918
    /* purecov: begin inspected */
5919
    tbl->file->print_error(error, MYF(ME_FATAL));  // Sets fatal_error
Michael Widenius's avatar
Michael Widenius committed
5920
    return 0;
Michael Widenius's avatar
Michael Widenius committed
5921
    /* purecov: end */
Michael Widenius's avatar
Michael Widenius committed
5922
  }
5923 5924 5925 5926 5927 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 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

  for (uint i= 0; i < key_column_count; i++)
  {
    cmp_res= compare_pred[i]->get_comparator()->compare();
    /* Unlike Arg_comparator::compare_row() here there should be no NULLs. */
    DBUG_ASSERT(!compare_pred[i]->null_value);
    if (cmp_res)
      return (cmp_res > 0 ? 1 : -1);
  }
  return 0;
}


/*
  Find a key in a sorted array of keys via binary search.

  see create_subq_in_equalities()
*/

bool Ordered_key::lookup()
{
  DBUG_ASSERT(key_buff_elements);

  ha_rows lo= 0;
  ha_rows hi= key_buff_elements - 1;
  ha_rows mid;
  int cmp_res;

  while (lo <= hi)
  {
    mid= lo + (hi - lo) / 2;
    cmp_res= cmp_key_with_search_key(key_buff[mid]);
    /*
      In order to find the minimum match, check if the pevious element is
      equal or smaller than the found one. If equal, we need to search further
      to the left.
    */
    if (!cmp_res && mid > 0)
      cmp_res= !cmp_key_with_search_key(key_buff[mid - 1]) ? 1 : 0;

    if (cmp_res == -1)
    {
      /* row[mid] < search_key */
      lo= mid + 1;
    }
    else if (cmp_res == 1)
    {
      /* row[mid] > search_key */
      if (!mid)
        goto not_found;
      hi= mid - 1;
    }
    else
    {
      /* row[mid] == search_key */
      cur_key_idx= mid;
      return TRUE;
    }
  }
not_found:
  cur_key_idx= HA_POS_ERROR;
  return FALSE;
}


/*
  Move the current index pointer to the next key with the same column
  values as the current key. Since the index is sorted, all such keys
  are contiguous.
*/

bool Ordered_key::next_same()
{
  DBUG_ASSERT(key_buff_elements);

  if (cur_key_idx < key_buff_elements - 1)
  {
    /*
      TIMOUR:
      The below is quite inefficient, since as a result we will fetch every
      row (except the last one) twice. There must be a more efficient way,
      e.g. swapping record[0] and record[1], and reading only the new record.
    */
    if (!cmp_keys_by_row_data(key_buff[cur_key_idx], key_buff[cur_key_idx + 1]))
    {
      ++cur_key_idx;
      return TRUE;
    }
  }
  return FALSE;
}


6016 6017 6018 6019 6020 6021 6022 6023
void Ordered_key::print(String *str)
{
  uint i;
  str->append("{idx=");
  str->qs_append(keyid);
  str->append(", (");
  for (i= 0; i < key_column_count - 1; i++)
  {
6024
    str->append(&key_columns[i]->field->field_name);
6025 6026
    str->append(", ");
  }
6027
  str->append(&key_columns[i]->field->field_name);
6028 6029 6030 6031 6032 6033 6034 6035 6036 6037 6038 6039 6040 6041 6042 6043
  str->append("), ");

  str->append("null_bitmap: (bits=");
  str->qs_append(null_key.n_bits);
  str->append(", nulls= ");
  str->qs_append((double)null_count);
  str->append(", min_null= ");
  str->qs_append((double)min_null_row);
  str->append(", max_null= ");
  str->qs_append((double)max_null_row);
  str->append("), ");

  str->append('}');
}


6044
subselect_partial_match_engine::subselect_partial_match_engine(
6045
  subselect_uniquesubquery_engine *engine_arg,
6046 6047 6048
  TABLE *tmp_table_arg, Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
6049
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
6050 6051
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
6052
  :subselect_engine(item_arg, result_arg),
6053 6054
   tmp_table(tmp_table_arg), lookup_engine(engine_arg),
   equi_join_conds(equi_join_conds_arg),
unknown's avatar
unknown committed
6055
   has_covering_null_row(has_covering_null_row_arg),
unknown's avatar
unknown committed
6056 6057
   has_covering_null_columns(has_covering_null_columns_arg),
   count_columns_with_nulls(count_columns_with_nulls_arg)
6058 6059 6060 6061 6062 6063
{}


int subselect_partial_match_engine::exec()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
6064
  int lookup_res;
6065

6066 6067 6068 6069
  DBUG_ASSERT(!(item_in->left_expr_has_null() &&
                item_in->is_top_level_item()));

  if (!item_in->left_expr_has_null())
6070
  {
6071 6072
    /* Try to find a matching row by index lookup. */
    if (lookup_engine->copy_ref_key(false))
6073
    {
6074
      /* The result is FALSE based on the outer reference. */
6075 6076
      item_in->value= 0;
      item_in->null_value= 0;
6077
      return 0;
6078
    }
6079
    else
6080
    {
6081 6082 6083
      /* Search for a complete match. */
      if ((lookup_res= lookup_engine->index_lookup()))
      {
6084
        /* An error occurred during lookup(). */
6085 6086 6087 6088 6089 6090 6091 6092 6093 6094 6095 6096 6097 6098 6099
        item_in->value= 0;
        item_in->null_value= 0;
        return lookup_res;
      }
      else if (item_in->value || !count_columns_with_nulls)
      {
        /*
          A complete match was found, the result of IN is TRUE.
          If no match was found, and there are no NULLs in the materialized
          subquery, then the result is guaranteed to be false because this
          branch is executed when the outer reference has no NULLs as well.
          Notice: (this->item == lookup_engine->item)
        */
        return 0;
      }
6100 6101 6102
    }
  }

unknown's avatar
unknown committed
6103
  if (has_covering_null_row)
6104 6105 6106 6107 6108 6109 6110 6111 6112 6113 6114 6115 6116 6117 6118 6119 6120 6121 6122 6123 6124 6125 6126 6127 6128 6129 6130 6131 6132 6133 6134 6135 6136 6137 6138 6139 6140 6141 6142 6143 6144 6145 6146 6147 6148 6149 6150 6151 6152 6153 6154 6155 6156 6157 6158
  {
    /*
      If there is a NULL-only row that coveres all columns the result of IN
      is UNKNOWN. 
    */
    item_in->value= 0;
    /*
      TIMOUR: which one is the right way to propagate an UNKNOWN result?
      Should we also set empty_result_set= FALSE; ???
    */
    //item_in->was_null= 1;
    item_in->null_value= 1;
    return 0;
  }

  /*
    There is no complete match. Look for a partial match (UNKNOWN result), or
    no match (FALSE).
  */
  if (tmp_table->file->inited)
    tmp_table->file->ha_index_end();

  if (partial_match())
  {
    /* The result of IN is UNKNOWN. */
    item_in->value= 0;
    /*
      TIMOUR: which one is the right way to propagate an UNKNOWN result?
      Should we also set empty_result_set= FALSE; ???
    */
    //item_in->was_null= 1;
    item_in->null_value= 1;
  }
  else
  {
    /* The result of IN is FALSE. */
    item_in->value= 0;
    /*
      TIMOUR: which one is the right way to propagate an UNKNOWN result?
      Should we also set empty_result_set= FALSE; ???
    */
    //item_in->was_null= 0;
    item_in->null_value= 0;
  }

  return 0;
}


void subselect_partial_match_engine::print(String *str,
                                           enum_query_type query_type)
{
  /*
    Should never be called as the actual engine cannot be known at query
    optimization time.
unknown's avatar
unknown committed
6159
    DBUG_ASSERT(FALSE);
6160 6161 6162 6163
  */
}


6164 6165 6166
/*
  @param non_null_key_parts  
  @param partial_match_key_parts  A union of all single-column NULL key parts.
6167 6168 6169 6170

  @retval FALSE  the engine was initialized successfully
  @retval TRUE   there was some (memory allocation) error during initialization,
                 such errors should be interpreted as revert to other strategy
6171 6172 6173 6174 6175 6176
*/

bool
subselect_rowid_merge_engine::init(MY_BITMAP *non_null_key_parts,
                                   MY_BITMAP *partial_match_key_parts)
{
6177
  THD *thd= get_thd();
6178 6179 6180 6181 6182 6183
  /* The length in bytes of the rowids (positions) of tmp_table. */
  uint rowid_length= tmp_table->file->ref_length;
  ha_rows row_count= tmp_table->file->stats.records;
  rownum_t cur_rownum= 0;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
6184
  uint cur_keyid= 0;
6185 6186 6187
  Item_in_subselect *item_in= (Item_in_subselect*) item;
  int error;

unknown's avatar
unknown committed
6188
  if (merge_keys_count == 0)
6189
  {
unknown's avatar
unknown committed
6190 6191
    DBUG_ASSERT(bitmap_bits_set(partial_match_key_parts) == 0 ||
                has_covering_null_row);
6192 6193 6194 6195
    /* There is nothing to initialize, we will only do regular lookups. */
    return FALSE;
  }

unknown's avatar
unknown committed
6196 6197 6198 6199 6200 6201 6202
  /*
    If all nullable columns contain only NULLs, there must be one index
    over all non-null columns.
  */
  DBUG_ASSERT(!has_covering_null_columns ||
              (has_covering_null_columns &&
               merge_keys_count == 1 && non_null_key_parts));
6203 6204
  /*
    Allocate buffers to hold the merged keys and the mapping between rowids and
unknown's avatar
unknown committed
6205 6206
    row numbers. All small buffers are allocated in the runtime memroot. Big
    buffers are allocated from the OS via malloc.
6207
  */
unknown's avatar
unknown committed
6208
  if (!(merge_keys= (Ordered_key**) thd->alloc(merge_keys_count *
6209
                                               sizeof(Ordered_key*))) ||
unknown's avatar
unknown committed
6210 6211
      !(null_bitmaps= (MY_BITMAP**) thd->alloc(merge_keys_count *
                                               sizeof(MY_BITMAP*))) ||
6212
      !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length),
6213
        MYF(MY_WME | MY_THREAD_SPECIFIC))))
6214 6215 6216 6217 6218
    return TRUE;

  /* Create the only non-NULL key if there is any. */
  if (non_null_key_parts)
  {
6219
    non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
6220 6221 6222
                                  0, 0, 0, row_num_to_rowid);
    if (non_null_key->init(non_null_key_parts))
      return TRUE;
6223 6224 6225
    merge_keys[cur_keyid]= non_null_key;
    merge_keys[cur_keyid]->first();
    ++cur_keyid;
6226 6227 6228
  }

  /*
unknown's avatar
unknown committed
6229 6230
    If all nullable columns contain NULLs, the only key that is needed is the
    only non-NULL key that is already created above.
6231
  */
unknown's avatar
unknown committed
6232
  if (!has_covering_null_columns)
6233
  {
6234 6235
    if (my_bitmap_init_memroot(&matching_keys, merge_keys_count, thd->mem_root) ||
        my_bitmap_init_memroot(&matching_outer_cols, merge_keys_count, thd->mem_root))
6236 6237 6238 6239 6240 6241 6242 6243
      return TRUE;

    /*
      Create one single-column NULL-key for each column in
      partial_match_key_parts.
    */
    for (uint i= 0; i < partial_match_key_parts->n_bits; i++)
    {
unknown's avatar
unknown committed
6244 6245 6246
      /* Skip columns that have no NULLs, or contain only NULLs. */
      if (!bitmap_is_set(partial_match_key_parts, i) ||
          result_sink->get_null_count_of_col(i) == row_count)
6247 6248
        continue;

unknown's avatar
unknown committed
6249
      merge_keys[cur_keyid]= new Ordered_key(
6250 6251 6252 6253 6254 6255
                                     cur_keyid, tmp_table,
                                     item_in->left_expr->element_index(i),
                                     result_sink->get_null_count_of_col(i),
                                     result_sink->get_min_null_of_col(i),
                                     result_sink->get_max_null_of_col(i),
                                     row_num_to_rowid);
unknown's avatar
unknown committed
6256 6257 6258
      if (merge_keys[cur_keyid]->init(i))
        return TRUE;
      merge_keys[cur_keyid]->first();
6259
      ++cur_keyid;
6260 6261
    }
  }
unknown's avatar
unknown committed
6262
  DBUG_ASSERT(cur_keyid == merge_keys_count);
6263 6264

  /* Populate the indexes with data from the temporary table. */
6265
  if (unlikely(tmp_table->file->ha_rnd_init_with_error(1)))
6266
    return TRUE;
6267 6268 6269 6270 6271 6272 6273 6274 6275 6276 6277
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
                             current_thd->variables.read_buff_size);
  tmp_table->null_row= 0;
  while (TRUE)
  {
    error= tmp_table->file->ha_rnd_next(tmp_table->record[0]);
    /*
      This is a temp table that we fully own, there should be no other
      cause to stop the iteration than EOF.
    */
    DBUG_ASSERT(!error || error == HA_ERR_END_OF_FILE);
6278
    if (unlikely(error == HA_ERR_END_OF_FILE))
6279 6280 6281 6282 6283 6284 6285 6286 6287 6288 6289 6290 6291 6292 6293 6294 6295 6296 6297
    {
      DBUG_ASSERT(cur_rownum == tmp_table->file->stats.records);
      break;
    }

    /*
      Save the position of this record in the row_num -> rowid mapping.
    */
    tmp_table->file->position(tmp_table->record[0]);
    memcpy(row_num_to_rowid + cur_rownum * rowid_length,
           tmp_table->file->ref, rowid_length);

    /* Add the current row number to the corresponding keys. */
    if (non_null_key)
    {
      /* By definition there are no NULLs in the non-NULL key. */
      non_null_key->add_key(cur_rownum);
    }

unknown's avatar
unknown committed
6298
    for (uint i= (non_null_key ? 1 : 0); i < merge_keys_count; i++)
6299 6300 6301 6302 6303
    {
      /*
        Check if the first and only indexed column contains NULL in the curent
        row, and add the row number to the corresponding key.
      */
6304
      if (merge_keys[i]->get_field(0)->is_null())
6305 6306 6307 6308 6309 6310 6311 6312 6313
        merge_keys[i]->set_null(cur_rownum);
      else
        merge_keys[i]->add_key(cur_rownum);
    }
    ++cur_rownum;
  }

  tmp_table->file->ha_rnd_end();

6314
  /* Sort all the keys by their NULL selectivity. */
unknown's avatar
unknown committed
6315
  my_qsort(merge_keys, merge_keys_count, sizeof(Ordered_key*),
6316 6317
           (qsort_cmp) cmp_keys_by_null_selectivity);

6318
  /* Sort the keys in each of the indexes. */
unknown's avatar
unknown committed
6319
  for (uint i= 0; i < merge_keys_count; i++)
6320 6321
    merge_keys[i]->sort_keys();

unknown's avatar
unknown committed
6322
  if (init_queue(&pq, merge_keys_count, 0, FALSE,
6323 6324
                 subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
                 0, 0))
6325 6326 6327 6328 6329 6330 6331 6332
    return TRUE;

  return FALSE;
}


subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
{
6333
  /* None of the resources below is allocated if there are no ordered keys. */
unknown's avatar
unknown committed
6334
  if (merge_keys_count)
6335
  {
6336
    my_free(row_num_to_rowid);
unknown's avatar
unknown committed
6337
    for (uint i= 0; i < merge_keys_count; i++)
6338 6339 6340 6341 6342
      delete merge_keys[i];
    delete_queue(&pq);
    if (tmp_table->file->inited == handler::RND)
      tmp_table->file->ha_rnd_end();
  }
6343 6344 6345 6346 6347
}


void subselect_rowid_merge_engine::cleanup()
{
6348 6349 6350
}


6351
/*
6352 6353 6354 6355 6356 6357 6358 6359 6360
  Quick sort comparison function to compare keys in order of decreasing bitmap
  selectivity, so that the most selective keys come first.

  @param  k1 first key to compare
  @param  k2 second key to compare

  @retval  1  if k1 is less selective than k2
  @retval  0  if k1 is equally selective as k2
  @retval -1  if k1 is more selective than k2
6361 6362 6363
*/

int
6364 6365
subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
                                                           Ordered_key **k2)
6366
{
6367 6368 6369
  double k1_sel= (*k1)->null_selectivity();
  double k2_sel= (*k2)->null_selectivity();
  if (k1_sel < k2_sel)
6370
    return 1;
6371 6372 6373
  if (k1_sel > k2_sel)
    return -1;
  return 0;
6374 6375 6376 6377 6378 6379 6380 6381 6382 6383 6384 6385 6386 6387 6388 6389 6390 6391 6392 6393 6394
}


/*
*/

int
subselect_rowid_merge_engine::cmp_keys_by_cur_rownum(void *arg,
                                                     uchar *k1, uchar *k2)
{
  rownum_t r1= ((Ordered_key*) k1)->current();
  rownum_t r2= ((Ordered_key*) k2)->current();

  return (r1 < r2) ? -1 : (r1 > r2) ? 1 : 0;
}


/*
  Check if certain table row contains a NULL in all columns for which there is
  no match in the corresponding value index.

unknown's avatar
unknown committed
6395 6396 6397 6398
  @note
  There is no need to check the columns that contain only NULLs, because
  those are guaranteed to match.

6399 6400 6401 6402 6403 6404
  @retval TRUE if a NULL row exists
  @retval FALSE otherwise
*/

bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num)
{
6405
  Ordered_key *cur_key;
unknown's avatar
unknown committed
6406
  for (uint i = 0; i < merge_keys_count; i++)
6407
  {
6408
    cur_key= merge_keys[i];
unknown's avatar
unknown committed
6409
    if (bitmap_is_set(&matching_keys, cur_key->get_keyid()))
6410 6411
    {
      /*
unknown's avatar
unknown committed
6412 6413
        The key 'i' (with id 'cur_keyid') already matches a value in row
        'row_num', thus we skip it as it can't possibly match a NULL.
6414 6415 6416
      */
      continue;
    }
6417
    if (!cur_key->is_null(row_num))
6418 6419 6420 6421 6422 6423
      return FALSE;
  }
  return TRUE;
}


unknown's avatar
unknown committed
6424 6425
/**
  Test if a subset of NULL-able columns contains a row of NULLs.
unknown's avatar
unknown committed
6426 6427
  @retval TRUE  if such a row exists
  @retval FALSE no complementing null row
unknown's avatar
unknown committed
6428 6429 6430 6431 6432 6433 6434
*/

bool subselect_rowid_merge_engine::
exists_complementing_null_row(MY_BITMAP *keys_to_complement)
{
  rownum_t highest_min_row= 0;
  rownum_t lowest_max_row= UINT_MAX;
unknown's avatar
unknown committed
6435
  uint count_null_keys, i;
unknown's avatar
unknown committed
6436 6437
  Ordered_key *cur_key;

unknown's avatar
unknown committed
6438
  if (!count_columns_with_nulls)
unknown's avatar
unknown committed
6439 6440
  {
    /*
unknown's avatar
unknown committed
6441 6442
      If there are both NULLs and non-NUll values in the outer reference, and
      the subquery contains no NULLs, a complementing NULL row cannot exist.
unknown's avatar
unknown committed
6443
    */
unknown's avatar
unknown committed
6444
    return FALSE;
unknown's avatar
unknown committed
6445 6446
  }

unknown's avatar
unknown committed
6447
  for (i= (non_null_key ? 1 : 0), count_null_keys= 0; i < merge_keys_count; i++)
unknown's avatar
unknown committed
6448 6449 6450 6451
  {
    cur_key= merge_keys[i];
    if (bitmap_is_set(keys_to_complement, cur_key->get_keyid()))
      continue;
unknown's avatar
unknown committed
6452 6453 6454 6455 6456
    if (!cur_key->get_null_count())
    {
      /* If there is column without NULLs, there cannot be a partial match. */
      return FALSE;
    }
unknown's avatar
unknown committed
6457 6458 6459 6460
    if (cur_key->get_min_null_row() > highest_min_row)
      highest_min_row= cur_key->get_min_null_row();
    if (cur_key->get_max_null_row() < lowest_max_row)
      lowest_max_row= cur_key->get_max_null_row();
unknown's avatar
unknown committed
6461
    null_bitmaps[count_null_keys++]= cur_key->get_null_key();
unknown's avatar
unknown committed
6462 6463 6464 6465 6466 6467 6468 6469 6470 6471
  }

  if (lowest_max_row < highest_min_row)
  {
    /* The intersection of NULL rows is empty. */
    return FALSE;
  }

  return bitmap_exists_intersection((const MY_BITMAP**) null_bitmaps,
                                    count_null_keys,
unknown's avatar
unknown committed
6472
                                    (uint)highest_min_row, (uint)lowest_max_row);
unknown's avatar
unknown committed
6473 6474 6475
}


6476 6477 6478 6479 6480 6481 6482 6483 6484 6485 6486 6487
/*
  @retval TRUE  there is a partial match (UNKNOWN)
  @retval FALSE  there is no match at all (FALSE)
*/

bool subselect_rowid_merge_engine::partial_match()
{
  Ordered_key *min_key; /* Key that contains the current minimum position. */
  rownum_t min_row_num; /* Current row number of min_key. */
  Ordered_key *cur_key;
  rownum_t cur_row_num;
  uint count_nulls_in_search_key= 0;
unknown's avatar
unknown committed
6488
  uint max_null_in_any_row=
unknown's avatar
unknown committed
6489
    ((select_materialize_with_stats *) result)->get_max_nulls_in_row();
6490
  bool res= FALSE;
6491 6492 6493

  /* If there is a non-NULL key, it must be the first key in the keys array. */
  DBUG_ASSERT(!non_null_key || (non_null_key && merge_keys[0] == non_null_key));
unknown's avatar
unknown committed
6494 6495
  /* The prioryty queue for keys must be empty. */
  DBUG_ASSERT(!pq.elements);
6496 6497

  /* All data accesses during execution are via handler::ha_rnd_pos() */
6498
  if (unlikely(tmp_table->file->ha_rnd_init_with_error(0)))
6499 6500 6501 6502
  {
    res= FALSE;
    goto end;
  }
6503

6504 6505
  /* Check if there is a match for the columns of the only non-NULL key. */
  if (non_null_key && !non_null_key->lookup())
6506 6507 6508 6509
  {
    res= FALSE;
    goto end;
  }
6510 6511

  /*
unknown's avatar
unknown committed
6512 6513 6514 6515
    If all nullable columns contain only NULLs, then there is a guranteed
    partial match, and we don't need to search for a matching row.
  */
  if (has_covering_null_columns)
6516 6517 6518 6519
  {
    res= TRUE;
    goto end;
  }
6520 6521 6522 6523 6524 6525 6526

  if (non_null_key)
    queue_insert(&pq, (uchar *) non_null_key);
  /*
    Do not add the non_null_key, since it was already processed above.
  */
  bitmap_clear_all(&matching_outer_cols);
6527
  for (uint i= MY_TEST(non_null_key); i < merge_keys_count; i++)
6528 6529
  {
    DBUG_ASSERT(merge_keys[i]->get_column_count() == 1);
unknown's avatar
unknown committed
6530
    if (merge_keys[i]->get_search_key(0)->null_value)
6531 6532
    {
      ++count_nulls_in_search_key;
6533
      bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
6534 6535 6536 6537 6538 6539 6540
    }
    else if (merge_keys[i]->lookup())
      queue_insert(&pq, (uchar *) merge_keys[i]);
  }

  /*
    If the outer reference consists of only NULLs, or if it has NULLs in all
unknown's avatar
unknown committed
6541 6542
    nullable columns (above we guarantee there is a match for the non-null
    coumns), the result is UNKNOWN.
6543
  */
6544
  if (count_nulls_in_search_key == merge_keys_count - MY_TEST(non_null_key))
6545 6546 6547 6548
  {
    res= TRUE;
    goto end;
  }
6549

unknown's avatar
unknown committed
6550 6551 6552 6553 6554 6555 6556 6557 6558 6559 6560 6561 6562 6563 6564 6565 6566
  /*
    If the outer row has NULLs in some columns, and
    there is no match for any of the remaining columns, and
    there is a subquery row with NULLs in all unmatched columns,
    then there is a partial match, otherwise the result is FALSE.
  */
  if (count_nulls_in_search_key && !pq.elements)
  {
    DBUG_ASSERT(!non_null_key);
    /*
      Check if the intersection of all NULL bitmaps of all keys that
      are not in matching_outer_cols is non-empty.
    */
    res= exists_complementing_null_row(&matching_outer_cols);
    goto end;
  }

6567 6568
  /*
    If there is no NULL (sub)row that covers all NULL columns, and there is no
unknown's avatar
unknown committed
6569 6570 6571 6572
    match for any of the NULL columns, the result is FALSE. Notice that if there
    is a non-null key, and there is only one matching key, the non-null key is
    the matching key. This is so, because this method returns FALSE if the
    non-null key doesn't have a match.
6573
  */
unknown's avatar
unknown committed
6574 6575 6576 6577
  if (!count_nulls_in_search_key &&
      (!pq.elements ||
       (pq.elements == 1 && non_null_key &&
        max_null_in_any_row < merge_keys_count-1)))
6578
  {
unknown's avatar
unknown committed
6579
    if (!pq.elements)
unknown's avatar
unknown committed
6580
    {
unknown's avatar
unknown committed
6581 6582 6583 6584 6585 6586
      DBUG_ASSERT(!non_null_key);
      /*
        The case of a covering null row is handled by
        subselect_partial_match_engine::exec()
      */
      DBUG_ASSERT(max_null_in_any_row != tmp_table->s->fields);
unknown's avatar
unknown committed
6587
    }
6588 6589 6590
    res= FALSE;
    goto end;
  }
6591 6592 6593

  DBUG_ASSERT(pq.elements);

unknown's avatar
unknown committed
6594
  min_key= (Ordered_key*) queue_remove_top(&pq);
6595
  min_row_num= min_key->current();
6596
  bitmap_set_bit(&matching_keys, min_key->get_keyid());
6597 6598 6599 6600 6601 6602 6603 6604 6605 6606
  bitmap_union(&matching_keys, &matching_outer_cols);
  if (min_key->next_same())
    queue_insert(&pq, (uchar *) min_key);

  if (pq.elements == 0)
  {
    /*
      Check the only matching row of the only key min_key for NULL matches
      in the other columns.
    */
6607 6608
    res= test_null_row(min_row_num);
    goto end;
6609 6610 6611 6612
  }

  while (TRUE)
  {
unknown's avatar
unknown committed
6613
    cur_key= (Ordered_key*) queue_remove_top(&pq);
6614 6615 6616
    cur_row_num= cur_key->current();

    if (cur_row_num == min_row_num)
6617
      bitmap_set_bit(&matching_keys, cur_key->get_keyid());
6618 6619 6620 6621 6622
    else
    {
      /* Follows from the correct use of priority queue. */
      DBUG_ASSERT(cur_row_num > min_row_num);
      if (test_null_row(min_row_num))
6623 6624 6625 6626
      {
        res= TRUE;
        goto end;
      }
6627 6628 6629 6630
      else
      {
        min_key= cur_key;
        min_row_num= cur_row_num;
unknown's avatar
unknown committed
6631
        bitmap_clear_all(&matching_keys);
6632
        bitmap_set_bit(&matching_keys, min_key->get_keyid());
6633 6634 6635 6636 6637 6638 6639 6640 6641 6642
        bitmap_union(&matching_keys, &matching_outer_cols);
      }
    }

    if (cur_key->next_same())
      queue_insert(&pq, (uchar *) cur_key);

    if (pq.elements == 0)
    {
      /* Check the last row of the last column in PQ for NULL matches. */
6643 6644
      res= test_null_row(min_row_num);
      goto end;
6645 6646 6647
    }
  }

6648
  /* We should never get here - all branches must be handled explicitly above. */
6649
  DBUG_ASSERT(FALSE);
6650 6651

end:
unknown's avatar
unknown committed
6652 6653
  if (!has_covering_null_columns)
    bitmap_clear_all(&matching_keys);
unknown's avatar
unknown committed
6654
  queue_remove_all(&pq);
6655 6656
  tmp_table->file->ha_rnd_end();
  return res;
6657 6658 6659
}


6660
subselect_table_scan_engine::subselect_table_scan_engine(
6661
  subselect_uniquesubquery_engine *engine_arg,
6662 6663 6664 6665
  TABLE *tmp_table_arg,
  Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
6666
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
6667 6668
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
6669
  :subselect_partial_match_engine(engine_arg, tmp_table_arg, item_arg,
6670
                                  result_arg, equi_join_conds_arg,
unknown's avatar
unknown committed
6671
                                  has_covering_null_row_arg,
unknown's avatar
unknown committed
6672 6673
                                  has_covering_null_columns_arg,
                                  count_columns_with_nulls_arg)
6674
{}
6675

6676 6677 6678 6679 6680 6681 6682

/*
  TIMOUR:
  This method is based on subselect_uniquesubquery_engine::scan_table().
  Consider refactoring somehow, 80% of the code is the same.

  for each row_i in tmp_table
6683
  {
6684 6685
    count_matches= 0;
    for each row element row_i[j]
6686
    {
6687 6688
      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
        ++count_matches;
6689
    }
6690 6691
    if (count_matches == outer_ref.elements)
      return TRUE
6692
  }
6693 6694
  return FALSE
*/
6695

6696 6697 6698 6699 6700 6701 6702
bool subselect_table_scan_engine::partial_match()
{
  List_iterator_fast<Item> equality_it(*equi_join_conds);
  Item *cur_eq;
  uint count_matches;
  int error;
  bool res;
6703

6704
  if (unlikely(tmp_table->file->ha_rnd_init_with_error(1)))
6705 6706 6707 6708 6709
  {
    res= FALSE;
    goto end;
  }

6710
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
6711
                             get_thd()->variables.read_buff_size);
6712
  for (;;)
6713
  {
6714
    error= tmp_table->file->ha_rnd_next(tmp_table->record[0]);
6715 6716
    if (unlikely(error))
    {
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
      if (error == HA_ERR_END_OF_FILE)
      {
        error= 0;
        break;
      }
      else
      {
        error= report_error(tmp_table, error);
        break;
      }
    }

    equality_it.rewind();
    count_matches= 0;
    while ((cur_eq= equality_it++))
    {
      DBUG_ASSERT(cur_eq->type() == Item::FUNC_ITEM &&
                  ((Item_func*)cur_eq)->functype() == Item_func::EQ_FUNC);
      if (!cur_eq->val_int() && !cur_eq->null_value)
        break;
      ++count_matches;
    }
    if (count_matches == tmp_table->s->fields)
    {
      res= TRUE; /* Found a matching row. */
      goto end;
    }
6744
  }
6745 6746 6747

  res= FALSE;
end:
6748
  tmp_table->file->ha_rnd_end();
6749 6750
  return res;
}
6751

6752 6753 6754

void subselect_table_scan_engine::cleanup()
{
6755
}
unknown's avatar
unknown committed
6756

6757

Igor Babaev's avatar
Igor Babaev committed
6758 6759 6760 6761 6762 6763 6764
void Item_subselect::register_as_with_rec_ref(With_element *with_elem)
{
  with_elem->sq_with_rec_ref.link_in_list(this, &this->next_with_rec_ref);
  with_recursive_reference= true;
}


6765 6766 6767 6768 6769 6770
/*
  Create an execution tracker for the expression cache we're using for this
  subselect; add the tracker to the query plan.
*/

void Item_subselect::init_expr_cache_tracker(THD *thd)
6771 6772 6773 6774 6775 6776 6777 6778 6779 6780
{
  if(!expr_cache)
    return;

  Explain_query *qw= thd->lex->explain;
  DBUG_ASSERT(qw);
  Explain_node *node= qw->get_node(unit->first_select()->select_number);
  if (!node)
    return;
  DBUG_ASSERT(expr_cache->type() == Item::EXPR_CACHE_ITEM);
6781
  node->cache_tracker= ((Item_cache_wrapper *)expr_cache)->init_tracker(qw->mem_root);
6782
}