item_subselect.cc 159 KB
Newer Older
Michael Widenius's avatar
Michael Widenius committed
1
/* Copyright (c) 2002, 2010, Oracle and/or its affiliates.
2 3 4

   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
5
   the Free Software Foundation; version 2 of the License.
6 7 8 9 10 11 12 13 14 15

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

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

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

  @brief
  subselect Item
21

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

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

#include "mysql_priv.h"
#include "sql_select.h"

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

unknown's avatar
unknown committed
36

37
Item_subselect::Item_subselect():
38
  Item_result_field(), value_assigned(0), own_engine(0), thd(0), old_engine(0), 
39 40
  used_tables_cache(0), have_to_be_excluded(0), const_item_cache(1),
  inside_first_fix_fields(0), done_first_fix_fields(FALSE), 
Sergey Petrunya's avatar
Sergey Petrunya committed
41
  substitution(0), expr_cache(0), engine(0), forced_const(FALSE), eliminated(FALSE),
42
  engine_changed(0), changed(0), is_correlated(FALSE)
43
{
44 45
  DBUG_ENTER("Item_subselect::Item_subselect");
  DBUG_PRINT("enter", ("this: 0x%lx", (ulong) this));
46
  with_subselect= 1;
47
  reset();
48
  /*
49
    Item value is NULL if select_result_interceptor didn't change this value
50 51
    (i.e. some rows will be found returned)
  */
52
  null_value= TRUE;
53
  DBUG_VOID_RETURN;
54 55
}

56

57
void Item_subselect::init(st_select_lex *select_lex,
58
			  select_result_interceptor *result)
59
{
60 61 62 63
  /*
    Please see Item_singlerow_subselect::invalidate_and_restore_select_lex(),
    which depends on alterations to the parse tree implemented here.
  */
64 65

  DBUG_ENTER("Item_subselect::init");
66 67
  DBUG_PRINT("enter", ("select_lex: 0x%lx  this: 0x%lx",
                       (ulong) select_lex, (ulong) this));
unknown's avatar
unknown committed
68
  unit= select_lex->master_unit();
unknown's avatar
unknown committed
69
  thd= unit->thd;
unknown's avatar
unknown committed
70

71 72 73 74 75 76 77
  if (unit->item)
  {
    /*
      Item can be changed in JOIN::prepare while engine in JOIN::optimize
      => we do not copy old_engine here
    */
    engine= unit->item->engine;
78
    own_engine= FALSE;
79
    parsing_place= unit->item->parsing_place;
80 81
    thd->change_item_tree((Item**)&unit->item, this);
    engine->change_result(this, result, TRUE);
82
  }
unknown's avatar
unknown committed
83
  else
84
  {
unknown's avatar
unknown committed
85 86 87 88 89 90 91 92
    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);
93
    if (unit->is_union())
unknown's avatar
unknown committed
94
      engine= new subselect_union_engine(thd, unit, result, this);
95
    else
unknown's avatar
unknown committed
96
      engine= new subselect_single_select_engine(thd, select_lex, result, this);
97
  }
98 99
  {
    SELECT_LEX *upper= unit->outer_select();
100
    if (upper->parsing_place == IN_HAVING)
101
      upper->subquery_in_having= 1;
unknown's avatar
unknown committed
102 103
    /* The subquery is an expression cache candidate */
    upper->expr_cache_may_be_used[upper->parsing_place]= TRUE;
104
  }
105
  DBUG_PRINT("info", ("engine: 0x%lx", (ulong)engine));
106 107 108
  DBUG_VOID_RETURN;
}

109 110 111 112 113 114
st_select_lex *
Item_subselect::get_select_lex()
{
  return unit->first_select();
}

unknown's avatar
unknown committed
115 116
void Item_subselect::cleanup()
{
unknown's avatar
unknown committed
117
  DBUG_ENTER("Item_subselect::cleanup");
unknown's avatar
unknown committed
118
  Item_result_field::cleanup();
unknown's avatar
unknown committed
119 120
  if (old_engine)
  {
121 122
    if (engine)
      engine->cleanup();
unknown's avatar
unknown committed
123 124 125
    engine= old_engine;
    old_engine= 0;
  }
126 127
  if (engine)
    engine->cleanup();
unknown's avatar
unknown committed
128
  depends_on.empty();
unknown's avatar
unknown committed
129 130
  reset();
  value_assigned= 0;
131
  expr_cache= 0;
132
  forced_const= FALSE;
unknown's avatar
unknown committed
133 134 135
  DBUG_VOID_RETURN;
}

136

unknown's avatar
unknown committed
137 138 139 140 141 142
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
143
}
144

145 146 147 148 149 150 151 152 153 154 155

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;
  }
  first_execution= TRUE;
156 157
  if (in_strategy & SUBS_MATERIALIZATION)
    in_strategy= 0;
158
  pushed_cond_guards= NULL;
159 160 161 162
  Item_subselect::cleanup();
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
163 164
Item_subselect::~Item_subselect()
{
165 166
  DBUG_ENTER("Item_subselect::~Item_subselect");
  DBUG_PRINT("enter", ("this: 0x%lx", (ulong) this));
167
  if (own_engine)
168 169 170
    delete engine;
  else
    engine->cleanup();
171
  engine= NULL;
172
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
173 174
}

unknown's avatar
unknown committed
175
bool
176
Item_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
177 178
{
  DBUG_ENTER("Item_subselect::select_transformer");
unknown's avatar
unknown committed
179
  DBUG_RETURN(false);
unknown's avatar
unknown committed
180 181 182
}


183
bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
184
{
unknown's avatar
unknown committed
185
  char const *save_where= thd_param->where;
unknown's avatar
unknown committed
186
  uint8 uncacheable;
unknown's avatar
unknown committed
187
  bool res;
unknown's avatar
unknown committed
188

189
  DBUG_ASSERT(fixed == 0);
unknown's avatar
unknown committed
190 191
  /* There is no reason to get a different THD. */
  DBUG_ASSERT(thd == thd_param);
192 193 194 195
  if (!done_first_fix_fields)
  {
    done_first_fix_fields= TRUE;
    inside_first_fix_fields= TRUE;
196 197 198 199 200
    upper_refs.empty();
    /*
      psergey-todo: remove _first_fix_fields calls, we need changes on every
      execution
    */
201 202
  }

Sergey Petrunia's avatar
Sergey Petrunia committed
203
  eliminated= FALSE;
204
  parent_select= thd_param->lex->current_select;
205

206
  if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
unknown's avatar
unknown committed
207
    return TRUE;
Sergey Petrunia's avatar
Sergey Petrunia committed
208
  
unknown's avatar
unknown committed
209

210
  if (!(res= engine->prepare()))
unknown's avatar
unknown committed
211
  {
212 213
    // all transformation is done (used by prepared statements)
    changed= 1;
214
    inside_first_fix_fields= FALSE;
215 216 217 218 219 220 221

    /*
      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.
    */
222 223
    if (substitution)
    {
224 225 226 227
      /*
        If the top item of the WHERE/HAVING condition changed,
        set correct WHERE/HAVING for PS.
      */
unknown's avatar
unknown committed
228
      if (unit->outer_select()->where == (*ref))
unknown's avatar
unknown committed
229
        unit->outer_select()->where= substitution;
230
      else if (unit->outer_select()->having == (*ref))
unknown's avatar
unknown committed
231
        unit->outer_select()->having= substitution;
unknown's avatar
unknown committed
232

233 234 235 236 237
      (*ref)= substitution;
      substitution->name= name;
      if (have_to_be_excluded)
	engine->exclude();
      substitution= 0;
238
      thd->where= "checking transformed subquery";
239
      if (!(*ref)->fixed)
240 241
	res= (*ref)->fix_fields(thd, ref);
      goto end;
Sergey Petrunya's avatar
Sergey Petrunya committed
242

243
    }
unknown's avatar
unknown committed
244 245
    // Is it one field subselect?
    if (engine->cols() > max_columns)
246
    {
unknown's avatar
unknown committed
247
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
Sergey Petrunya's avatar
Sergey Petrunya committed
248

249
      goto end;
unknown's avatar
unknown committed
250
    }
251
    fix_length_and_dec();
unknown's avatar
unknown committed
252
  }
unknown's avatar
unknown committed
253
  else
254
    goto end;
unknown's avatar
unknown committed
255 256
  
  if ((uncacheable= engine->uncacheable()))
unknown's avatar
unknown committed
257 258
  {
    const_item_cache= 0;
259 260
    if (uncacheable & UNCACHEABLE_RAND)
      used_tables_cache|= RAND_TABLE_BIT;
unknown's avatar
unknown committed
261
  }
262
  fixed= 1;
unknown's avatar
unknown committed
263

264
end:
265
  done_first_fix_fields= FALSE;
Sergey Petrunya's avatar
Sergey Petrunya committed
266
  inside_first_fix_fields= FALSE;
267
  thd->where= save_where;
268 269 270
  return res;
}

271

Sergey Petrunya's avatar
Sergey Petrunya committed
272
bool Item_subselect::enumerate_field_refs_processor(uchar *arg)
Sergey Petrunia's avatar
Sergey Petrunia committed
273
{
274 275 276 277
  List_iterator<Ref_to_outside> it(upper_refs);
  Ref_to_outside *upper;
  
  while ((upper= it++))
Sergey Petrunia's avatar
Sergey Petrunia committed
278
  {
279
    if (upper->item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
Sergey Petrunia's avatar
Sergey Petrunia committed
280 281 282 283 284 285 286 287 288 289 290
      return TRUE;
  }
  return FALSE;
}

bool Item_subselect::mark_as_eliminated_processor(uchar *arg)
{
  eliminated= TRUE;
  return FALSE;
}

291

292 293 294 295 296 297 298 299 300 301
/**
  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.
*/

302 303 304 305 306 307 308 309 310
bool Item_subselect::eliminate_subselect_processor(uchar *arg)
{
  unit->item= NULL;
  unit->exclude_from_tree();
  eliminated= TRUE;
  return FALSE;
}


311
/**
312 313 314
  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.
315 316 317 318 319

  @param arg  pointer to the fake select

  @return
    FALSE to force the evaluation of the processor for the subsequent items.
320 321 322 323 324 325
*/

bool Item_subselect::set_fake_select_as_master_processor(uchar *arg)
{
  SELECT_LEX *fake_select= (SELECT_LEX*) arg;
  /*
326 327
    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
328 329 330 331
    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.
332 333 334 335
  */
  if (unit->outer_select()->master_unit()->fake_select_lex == fake_select)
  {
    /*
unknown's avatar
unknown committed
336 337
      Set the master of the subquery to be the fake select (i.e. the whole
      UNION), instead of the last query in the UNION.
338
    */
unknown's avatar
unknown committed
339 340
    fake_select->add_slave(unit);
    DBUG_ASSERT(unit->outer_select() == fake_select);
341 342 343 344
    /* 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);
    /*
345 346
      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.
347 348 349 350
    */
    unit->item= this;
    eliminated= FALSE;
  }
351
  return FALSE;
352 353 354
}


355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371
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;
}

372

373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
/*
  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.
*/

void Item_subselect::fix_after_pullout(st_select_lex *new_parent, Item **ref)
{
  recalc_used_tables(new_parent, TRUE);
  parent_select= new_parent;
}

401

402 403 404 405 406
class Field_fixer: public Field_enumerator
{
public:
  table_map used_tables; /* Collect used_tables here */
  st_select_lex *new_parent; /* Select we're in */
407
  virtual void visit_field(Item_field *item)
408 409 410 411 412
  {
    //for (TABLE_LIST *tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local)
    //{
    //  if (tbl->table == field->table)
    //  {
413
        used_tables|= item->field->table->map;
414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491
    //    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)
{
  List_iterator<Ref_to_outside> it(upper_refs);
  Ref_to_outside *upper;
  
  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;
          upper->item->walk(&Item::enumerate_field_refs_processor, FALSE,
                            (uchar*)&fixer);
          used_tables_cache |= fixer.used_tables;
          /*
          if (after_pullout)
            upper->item->fix_after_pullout(new_parent, &(upper->item));
          upper->item->update_used_tables();
          used_tables_cache |= upper->item->used_tables();
          */
        }
      }
    }
    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.
  */
}

492
bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
493
                          uchar *argument)
494 495 496 497 498 499 500 501 502 503 504 505 506 507 508
{

  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
509
      /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */
510 511 512 513 514 515

      while ((item=li++))
      {
        if (item->walk(processor, walk_subquery, argument))
          return 1;
      }
516
      for (order= lex->order_list.first ; order; order= order->next)
517 518 519 520
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
521
      for (order= lex->group_list.first ; order; order= order->next)
522 523 524 525 526 527 528 529 530 531
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
    }
  }
  return (this->*processor)(argument);
}


532
bool Item_subselect::exec()
533
{
534
  int res;
unknown's avatar
unknown committed
535

536 537 538 539 540
  /*
    Do not execute subselect in case of a fatal error
    or if the query has been killed.
  */
  if (thd->is_error() || thd->killed)
unknown's avatar
unknown committed
541
    return 1;
542

Sergey Glukhov's avatar
Sergey Glukhov committed
543
  DBUG_ASSERT(!thd->lex->context_analysis_only);
544 545 546 547 548
  /*
    Simulate a failure in sub-query execution. Used to test e.g.
    out of memory or query being killed conditions.
  */
  DBUG_EXECUTE_IF("subselect_exec_fail", return 1;);
unknown's avatar
unknown committed
549

550
  res= engine->exec();
unknown's avatar
unknown committed
551

552 553 554
  if (engine_changed)
  {
    engine_changed= 0;
555
    return exec();
556 557
  }
  return (res);
558 559
}

560

Sergey Petrunya's avatar
Sergey Petrunya committed
561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607
int Item_in_subselect::optimize(double *out_rows, double *cost)
{
  int res;
  DBUG_ENTER("Item_in_subselect::optimize");
  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 */
  if (join->group_list)
  {
    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
608 609


unknown's avatar
unknown committed
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
/**
  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)
{
  return (depends_on.elements &&
          engine->cols() == 1 &&
          optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
                                     UNCACHEABLE_SIDEEFFECT)));
}


/**
  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
  Item_in optimizer and result of the IN subquery will be scalar in this
  case.

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

bool Item_in_subselect::expr_cache_is_needed(THD *thd)
{
  return (depends_on.elements &&
          optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
                                     UNCACHEABLE_SIDEEFFECT)));
}


660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678
/*
  Compute the IN predicate if the left operand's cache changed.
*/

bool Item_in_subselect::exec()
{
  DBUG_ENTER("Item_in_subselect::exec");
  /*
    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.
  */
679
  if (!left_expr_cache && (in_strategy & SUBS_MATERIALIZATION))
680 681
    init_left_expr_cache();

682 683 684 685 686 687 688 689
  /*
    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);
690 691 692 693 694 695 696 697 698 699

  /*
    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());
}


700
Item::Type Item_subselect::type() const
701 702 703 704
{
  return SUBSELECT_ITEM;
}

unknown's avatar
unknown committed
705

706 707
void Item_subselect::fix_length_and_dec()
{
708
  engine->fix_length_and_dec(0);
709
}
unknown's avatar
unknown committed
710

unknown's avatar
unknown committed
711

712
table_map Item_subselect::used_tables() const
unknown's avatar
unknown committed
713
{
714
  return (table_map) (engine->uncacheable() ? used_tables_cache : 0L);
unknown's avatar
unknown committed
715 716
}

unknown's avatar
merge  
unknown committed
717

718 719
bool Item_subselect::const_item() const
{
Sergey Glukhov's avatar
Sergey Glukhov committed
720
  return thd->lex->context_analysis_only ? FALSE : const_item_cache;
721 722
}

723
Item *Item_subselect::get_tmp_table_item(THD *thd_arg)
unknown's avatar
unknown committed
724 725
{
  if (!with_sum_func && !const_item())
unknown's avatar
unknown committed
726
    return new Item_field(result_field);
727
  return copy_or_same(thd_arg);
unknown's avatar
unknown committed
728
}
unknown's avatar
merge  
unknown committed
729

730 731
void Item_subselect::update_used_tables()
{
732
  if (!forced_const)
733
  {
734 735 736 737 738 739 740
    recalc_used_tables(parent_select, FALSE);
    if (!engine->uncacheable())
    {
      // did all used tables become static?
      if (!(used_tables_cache & ~engine->upper_select_const_tables()))
        const_item_cache= 1;
    }
741 742 743
  }
}

unknown's avatar
unknown committed
744

745
void Item_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
746
{
747 748 749 750 751 752 753 754
  if (engine)
  {
    str->append('(');
    engine->print(str, query_type);
    str->append(')');
  }
  else
    str->append("(...)");
unknown's avatar
unknown committed
755 756 757
}


unknown's avatar
merge  
unknown committed
758
Item_singlerow_subselect::Item_singlerow_subselect(st_select_lex *select_lex)
759
  :Item_subselect(), value(0)
unknown's avatar
unknown committed
760
{
unknown's avatar
unknown committed
761
  DBUG_ENTER("Item_singlerow_subselect::Item_singlerow_subselect");
762
  init(select_lex, new select_singlerow_subselect(this));
unknown's avatar
unknown committed
763
  maybe_null= 1;
764
  max_columns= UINT_MAX;
unknown's avatar
unknown committed
765
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
766 767
}

768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
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);
}

unknown's avatar
unknown committed
788 789
Item_maxmin_subselect::Item_maxmin_subselect(THD *thd_param,
                                             Item_subselect *parent,
790
					     st_select_lex *select_lex,
unknown's avatar
unknown committed
791
					     bool max_arg)
792
  :Item_singlerow_subselect(), was_values(TRUE)
793 794
{
  DBUG_ENTER("Item_maxmin_subselect::Item_maxmin_subselect");
unknown's avatar
unknown committed
795 796
  max= max_arg;
  init(select_lex, new select_max_min_finder_subselect(this, max_arg));
797 798 799
  max_columns= 1;
  maybe_null= 1;
  max_columns= 1;
800 801 802 803 804 805

  /*
    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();
806
  const_item_cache= parent->const_item();
807

unknown's avatar
unknown committed
808
  /*
unknown's avatar
unknown committed
809
    this subquery always creates during preparation, so we can assign
unknown's avatar
unknown committed
810 811 812 813
    thd here
  */
  thd= thd_param;

814 815 816
  DBUG_VOID_RETURN;
}

817 818
void Item_maxmin_subselect::cleanup()
{
unknown's avatar
unknown committed
819 820 821
  DBUG_ENTER("Item_maxmin_subselect::cleanup");
  Item_singlerow_subselect::cleanup();

822
  /*
unknown's avatar
unknown committed
823
    By default it is TRUE to avoid TRUE reporting by
824 825 826
    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
827 828
    select_max_min_finder_subselect::send_data() set it back to TRUE if some
    value will be found.
829 830
  */
  was_values= TRUE;
unknown's avatar
unknown committed
831
  DBUG_VOID_RETURN;
832 833 834
}


835
void Item_maxmin_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
836
{
837
  str->append(max?"<max>":"<min>", 5);
838
  Item_singlerow_subselect::print(str, query_type);
unknown's avatar
unknown committed
839 840
}

841

unknown's avatar
unknown committed
842
void Item_singlerow_subselect::reset()
843
{
844
  Item_subselect::reset();
845
  if (value)
846
    value->null_value= TRUE;
847 848
}

849

unknown's avatar
unknown committed
850 851 852 853 854 855 856 857 858
/**
  @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
859 860 861 862

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

  @retval false  The subquery was transformed
unknown's avatar
unknown committed
863
*/
unknown's avatar
unknown committed
864
bool
unknown's avatar
unknown committed
865
Item_singlerow_subselect::select_transformer(JOIN *join)
866
{
867
  DBUG_ENTER("Item_singlerow_subselect::select_transformer");
unknown's avatar
unknown committed
868
  if (changed)
unknown's avatar
unknown committed
869
    DBUG_RETURN(false);
870

871
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
872
  Query_arena *arena= thd->stmt_arena;
unknown's avatar
unknown committed
873
 
874
  if (!select_lex->master_unit()->is_union() &&
875
      !select_lex->table_list.elements &&
unknown's avatar
unknown committed
876
      select_lex->item_list.elements == 1 &&
877
      !select_lex->item_list.head()->with_sum_func &&
unknown's avatar
unknown committed
878 879 880 881 882 883 884
      /*
	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
885
      !(select_lex->item_list.head()->type() == FIELD_ITEM ||
886
	select_lex->item_list.head()->type() == REF_ITEM) &&
887
      !join->conds && !join->having &&
888
      /*
unknown's avatar
unknown committed
889
        switch off this optimization for prepare statement,
890 891 892
        because we do not rollback this changes
        TODO: make rollback for it, or special name resolving mode in 5.0.
      */
893
      !arena->is_stmt_prepare_or_first_sp_execute()
unknown's avatar
unknown committed
894
      )
895 896
  {
    have_to_be_excluded= 1;
unknown's avatar
unknown committed
897
    if (thd->lex->describe)
898 899 900
    {
      char warn_buff[MYSQL_ERRMSG_SIZE];
      sprintf(warn_buff, ER(ER_SELECT_REDUCED), select_lex->select_number);
unknown's avatar
unknown committed
901
      push_warning(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
902 903 904
		   ER_SELECT_REDUCED, warn_buff);
    }
    substitution= select_lex->item_list.head();
unknown's avatar
unknown committed
905
    /*
unknown's avatar
unknown committed
906
      as far as we moved content to upper level, field which depend of
unknown's avatar
unknown committed
907 908
      'upper' select is not really dependent => we remove this dependence
    */
909
    substitution->walk(&Item::remove_dependence_processor, 0,
910
		       (uchar *) select_lex->outer_select());
911
  }
unknown's avatar
unknown committed
912
  DBUG_RETURN(false);
913 914
}

unknown's avatar
unknown committed
915

unknown's avatar
unknown committed
916
void Item_singlerow_subselect::store(uint i, Item *item)
unknown's avatar
unknown committed
917
{
918
  row[i]->store(item);
919
  row[i]->cache_value();
unknown's avatar
unknown committed
920 921
}

unknown's avatar
unknown committed
922
enum Item_result Item_singlerow_subselect::result_type() const
unknown's avatar
unknown committed
923
{
924 925 926
  return engine->type();
}

927 928 929 930 931 932 933 934 935
/* 
 Don't rely on the result type to calculate field type. 
 Ask the engine instead.
*/
enum_field_types Item_singlerow_subselect::field_type() const
{
  return engine->field_type();
}

unknown's avatar
unknown committed
936
void Item_singlerow_subselect::fix_length_and_dec()
937
{
938 939 940 941 942
  if ((max_columns= engine->cols()) == 1)
  {
    engine->fix_length_and_dec(row= &value);
  }
  else
943
  {
944
    if (!(row= (Item_cache**) sql_alloc(sizeof(Item_cache*)*max_columns)))
945 946 947
      return;
    engine->fix_length_and_dec(row);
    value= *row;
948
  }
949
  unsigned_flag= value->unsigned_flag;
950 951 952 953 954 955 956
  /*
    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();
957 958
}

unknown's avatar
unknown committed
959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982

/**
  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
  Item_exp_cache_wrapper with an appropriate expression cache set up there.

  @note
  used from Item::transform()

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

Item* Item_singlerow_subselect::expr_cache_insert_transformer(uchar *thd_arg)
{
  THD *thd= (THD*) thd_arg;
  DBUG_ENTER("Item_singlerow_subselect::expr_cache_insert_transformer");

983 984 985 986 987 988
  if (expr_cache)
    DBUG_RETURN(expr_cache);

  if (expr_cache_is_needed(thd) &&
      (expr_cache= set_expr_cache(thd, depends_on)))
    DBUG_RETURN(expr_cache);
unknown's avatar
unknown committed
989 990 991 992
  DBUG_RETURN(this);
}


unknown's avatar
unknown committed
993
uint Item_singlerow_subselect::cols()
unknown's avatar
unknown committed
994
{
995 996 997
  return engine->cols();
}

unknown's avatar
unknown committed
998
bool Item_singlerow_subselect::check_cols(uint c)
999 1000 1001
{
  if (c != engine->cols())
  {
unknown's avatar
unknown committed
1002
    my_error(ER_OPERAND_COLUMNS, MYF(0), c);
1003 1004 1005 1006 1007
    return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1008
bool Item_singlerow_subselect::null_inside()
1009 1010 1011 1012 1013 1014 1015 1016 1017
{
  for (uint i= 0; i < max_columns ; i++)
  {
    if (row[i]->null_value)
      return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1018
void Item_singlerow_subselect::bring_value()
1019
{
1020 1021 1022 1023
  if (!exec() && assigned())
    null_value= 0;
  else
    reset();
unknown's avatar
unknown committed
1024 1025
}

1026
double Item_singlerow_subselect::val_real()
unknown's avatar
unknown committed
1027
{
1028
  DBUG_ASSERT(fixed == 1);
1029
  if (!exec() && !value->null_value)
1030
  {
1031
    null_value= FALSE;
1032
    return value->val_real();
1033 1034
  }
  else
unknown's avatar
unknown committed
1035
  {
1036
    reset();
unknown's avatar
unknown committed
1037
    return 0;
unknown's avatar
unknown committed
1038
  }
unknown's avatar
unknown committed
1039 1040
}

1041
longlong Item_singlerow_subselect::val_int()
unknown's avatar
unknown committed
1042
{
1043
  DBUG_ASSERT(fixed == 1);
1044
  if (!exec() && !value->null_value)
1045
  {
1046
    null_value= FALSE;
1047 1048 1049
    return value->val_int();
  }
  else
unknown's avatar
unknown committed
1050
  {
1051
    reset();
unknown's avatar
unknown committed
1052
    return 0;
unknown's avatar
unknown committed
1053
  }
unknown's avatar
unknown committed
1054 1055
}

unknown's avatar
unknown committed
1056
String *Item_singlerow_subselect::val_str(String *str)
unknown's avatar
unknown committed
1057
{
1058
  if (!exec() && !value->null_value)
1059
  {
1060
    null_value= FALSE;
1061 1062 1063
    return value->val_str(str);
  }
  else
unknown's avatar
unknown committed
1064
  {
1065
    reset();
unknown's avatar
unknown committed
1066
    return 0;
unknown's avatar
unknown committed
1067
  }
unknown's avatar
unknown committed
1068 1069
}

unknown's avatar
unknown committed
1070

unknown's avatar
unknown committed
1071 1072
my_decimal *Item_singlerow_subselect::val_decimal(my_decimal *decimal_value)
{
1073
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1074
  {
1075
    null_value= FALSE;
unknown's avatar
unknown committed
1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087
    return value->val_decimal(decimal_value);
  }
  else
  {
    reset();
    return 0;
  }
}


bool Item_singlerow_subselect::val_bool()
{
1088
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1089
  {
1090
    null_value= FALSE;
unknown's avatar
unknown committed
1091 1092 1093 1094 1095 1096 1097 1098 1099 1100
    return value->val_bool();
  }
  else
  {
    reset();
    return 0;
  }
}


1101
Item_exists_subselect::Item_exists_subselect(st_select_lex *select_lex):
1102
  Item_subselect()
unknown's avatar
unknown committed
1103
{
unknown's avatar
unknown committed
1104
  DBUG_ENTER("Item_exists_subselect::Item_exists_subselect");
unknown's avatar
unknown committed
1105
  bool val_bool();
1106
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1107
  max_columns= UINT_MAX;
1108
  null_value= FALSE; //can't be NULL
unknown's avatar
unknown committed
1109 1110
  maybe_null= 0; //can't be NULL
  value= 0;
unknown's avatar
unknown committed
1111 1112 1113
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
1114

1115
void Item_exists_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
1116
{
1117
  str->append(STRING_WITH_LEN("exists"));
1118
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
1119 1120 1121
}


unknown's avatar
unknown committed
1122
bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
1123
{
1124 1125
  if (unit_arg->fake_select_lex &&
      unit_arg->fake_select_lex->test_limit())
1126
    return(1);
unknown's avatar
unknown committed
1127

1128
  SELECT_LEX *sl= unit_arg->first_select();
1129 1130
  for (; sl; sl= sl->next_select())
  {
unknown's avatar
unknown committed
1131
    if (sl->test_limit())
1132 1133 1134 1135 1136
      return(1);
  }
  return(0);
}

1137
Item_in_subselect::Item_in_subselect(Item * left_exp,
unknown's avatar
unknown committed
1138
				     st_select_lex *select_lex):
1139
  Item_exists_subselect(), left_expr_cache(0), first_execution(TRUE),
Sergey Petrunya's avatar
Sergey Petrunya committed
1140 1141 1142
  optimizer(0), pushed_cond_guards(NULL), in_strategy(0),
  is_jtbm_merged(FALSE), is_flattenable_semijoin(FALSE), 
  upper_item(0)
unknown's avatar
unknown committed
1143 1144
{
  DBUG_ENTER("Item_in_subselect::Item_in_subselect");
unknown's avatar
unknown committed
1145
  left_expr= left_exp;
1146
  func= &eq_creator;
1147
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1148
  max_columns= UINT_MAX;
1149
  maybe_null= 1;
1150
  abort_on_null= 0;
1151
  reset();
unknown's avatar
unknown committed
1152
  //if test_limit will fail then error will be reported to client
1153
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1154 1155 1156
  DBUG_VOID_RETURN;
}

1157 1158 1159 1160 1161
int Item_in_subselect::get_identifier()
{
  return engine->get_identifier();
}

1162
Item_allany_subselect::Item_allany_subselect(Item * left_exp,
1163
                                             chooser_compare_func_creator fc,
unknown's avatar
unknown committed
1164 1165
					     st_select_lex *select_lex,
					     bool all_arg)
unknown's avatar
unknown committed
1166
  :Item_in_subselect(), func_creator(fc), all(all_arg)
unknown's avatar
unknown committed
1167
{
1168
  DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
unknown's avatar
unknown committed
1169
  left_expr= left_exp;
1170
  func= func_creator(all_arg);
1171
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1172
  max_columns= 1;
1173
  abort_on_null= 0;
1174
  reset();
unknown's avatar
unknown committed
1175
  //if test_limit will fail then error will be reported to client
1176
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1177
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
1178 1179
}

unknown's avatar
unknown committed
1180

1181 1182 1183 1184 1185 1186
/**
  Initialize length and decimals for EXISTS  and inherited (IN/ALL/ANY)
  subqueries
*/

void Item_exists_subselect::init_length_and_dec()
1187
{
1188 1189 1190
  decimals= 0;
  max_length= 1;
  max_columns= engine->cols();
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201
}


void Item_exists_subselect::fix_length_and_dec()
{
  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)
  */
1202
  unit->global_parameters->select_limit= new Item_int((int32) 1);
1203 1204 1205 1206
  DBUG_PRINT("info", ("Set limit to 1"));
  DBUG_VOID_RETURN;
}

1207

1208 1209 1210
void Item_in_subselect::fix_length_and_dec()
{
  DBUG_ENTER("Item_in_subselect::fix_length_and_dec");
1211 1212 1213 1214 1215
  init_length_and_dec();
  /*
    Unlike Item_exists_subselect, LIMIT 1 is set later for
    Item_in_subselect, depending on the chosen strategy.
  */
1216
  DBUG_VOID_RETURN;
1217 1218
}

unknown's avatar
unknown committed
1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242

/**
  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
  Item_exp_cache_wrapper with an appropriate expression cache set up there.

  @note
  used from Item::transform()

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

Item* Item_exists_subselect::expr_cache_insert_transformer(uchar *thd_arg)
{
  THD *thd= (THD*) thd_arg;
  DBUG_ENTER("Item_exists_subselect::expr_cache_insert_transformer");

1243 1244 1245 1246 1247 1248
  if (expr_cache)
    DBUG_RETURN(expr_cache);

  if (substype() == EXISTS_SUBS && expr_cache_is_needed(thd) &&
      (expr_cache= set_expr_cache(thd, depends_on)))
    DBUG_RETURN(expr_cache);
unknown's avatar
unknown committed
1249 1250 1251 1252
  DBUG_RETURN(this);
}


1253
double Item_exists_subselect::val_real()
unknown's avatar
unknown committed
1254
{
1255
  DBUG_ASSERT(fixed == 1);
1256
  if (exec())
unknown's avatar
unknown committed
1257
  {
1258
    reset();
unknown's avatar
unknown committed
1259
    return 0;
unknown's avatar
unknown committed
1260
  }
unknown's avatar
unknown committed
1261 1262 1263
  return (double) value;
}

1264
longlong Item_exists_subselect::val_int()
unknown's avatar
unknown committed
1265
{
1266
  DBUG_ASSERT(fixed == 1);
1267
  if (exec())
unknown's avatar
unknown committed
1268
  {
1269
    reset();
unknown's avatar
unknown committed
1270
    return 0;
unknown's avatar
unknown committed
1271
  }
unknown's avatar
unknown committed
1272 1273 1274
  return value;
}

1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288

/**
  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
1289 1290
String *Item_exists_subselect::val_str(String *str)
{
1291
  DBUG_ASSERT(fixed == 1);
1292
  if (exec())
1293
    reset();
unknown's avatar
unknown committed
1294
  str->set((ulonglong)value,&my_charset_bin);
1295 1296 1297
  return str;
}

unknown's avatar
unknown committed
1298

1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311
/**
  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
1312 1313 1314
my_decimal *Item_exists_subselect::val_decimal(my_decimal *decimal_value)
{
  DBUG_ASSERT(fixed == 1);
1315
  if (exec())
unknown's avatar
unknown committed
1316 1317 1318 1319 1320 1321 1322 1323 1324
    reset();
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


bool Item_exists_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1325
  if (exec())
unknown's avatar
unknown committed
1326 1327 1328 1329
  {
    reset();
    return 0;
  }
1330
  return value != 0;
unknown's avatar
unknown committed
1331 1332 1333
}


1334
double Item_in_subselect::val_real()
1335
{
unknown's avatar
unknown committed
1336 1337 1338 1339 1340
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1341
  DBUG_ASSERT(fixed == 1);
1342
  null_value= was_null= FALSE;
1343
  if (exec())
1344 1345 1346 1347 1348
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1349
    null_value= TRUE;
1350 1351 1352
  return (double) value;
}

unknown's avatar
unknown committed
1353

1354
longlong Item_in_subselect::val_int()
1355
{
unknown's avatar
unknown committed
1356 1357 1358 1359 1360
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1361
  DBUG_ASSERT(fixed == 1);
1362
  null_value= was_null= FALSE;
1363
  if (exec())
1364 1365 1366 1367 1368
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1369
    null_value= TRUE;
1370 1371 1372
  return value;
}

unknown's avatar
unknown committed
1373

1374 1375
String *Item_in_subselect::val_str(String *str)
{
unknown's avatar
unknown committed
1376 1377 1378 1379 1380
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1381
  DBUG_ASSERT(fixed == 1);
1382
  null_value= was_null= FALSE;
1383
  if (exec())
1384 1385 1386 1387 1388 1389
  {
    reset();
    return 0;
  }
  if (was_null && !value)
  {
1390
    null_value= TRUE;
unknown's avatar
unknown committed
1391
    return 0;
unknown's avatar
unknown committed
1392
  }
unknown's avatar
unknown committed
1393
  str->set((ulonglong)value, &my_charset_bin);
unknown's avatar
unknown committed
1394 1395 1396
  return str;
}

unknown's avatar
unknown committed
1397

unknown's avatar
unknown committed
1398 1399 1400
bool Item_in_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1401
  null_value= was_null= FALSE;
1402
  if (forced_const)
1403
    return value;
1404
  if (exec())
unknown's avatar
unknown committed
1405 1406 1407 1408 1409
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1410
    null_value= TRUE;
unknown's avatar
unknown committed
1411 1412 1413 1414 1415 1416 1417 1418 1419 1420
  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);
1421
  null_value= was_null= FALSE;
unknown's avatar
unknown committed
1422
  DBUG_ASSERT(fixed == 1);
1423
  if (exec())
unknown's avatar
unknown committed
1424 1425 1426 1427 1428
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1429
    null_value= TRUE;
unknown's avatar
unknown committed
1430 1431 1432 1433 1434
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


1435
/**
1436
  Prepare a single-column IN/ALL/ANY subselect for rewriting.
1437

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

1440
  @details
1441

1442
  Prepare a single-column subquery to be rewritten. Given the subquery.
1443

1444 1445 1446 1447 1448
  If the subquery has no tables it will be turned to an expression between
  left part and SELECT list.

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

unknown's avatar
unknown committed
1450 1451
  @retval false  The subquery was transformed
  @retval true   Error
1452
*/
1453

unknown's avatar
unknown committed
1454
bool
1455
Item_in_subselect::single_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1456
{
1457
  SELECT_LEX *select_lex= join->select_lex;
1458
  DBUG_ENTER("Item_in_subselect::single_value_transformer");
unknown's avatar
unknown committed
1459

1460 1461 1462 1463
  /*
    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 * ...)
  */
1464
  // psergey: duplicated_subselect_card_check
1465 1466 1467
  if (select_lex->item_list.elements > 1)
  {
    my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
1468
    DBUG_RETURN(true);
1469 1470
  }

1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493
  Item* join_having= join->having ? join->having : join->tmp_having;
  if (!(join_having || select_lex->with_sum_func ||
        select_lex->group_list.elements) &&
      select_lex->table_list.elements == 0 &&
      !select_lex->master_unit()->is_union())
  {
    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,
                     (uchar *) select_lex->outer_select());
    substitution= func->create(left_expr, where_item);
    have_to_be_excluded= 1;
    if (thd->lex->describe)
    {
      char warn_buff[MYSQL_ERRMSG_SIZE];
      sprintf(warn_buff, ER(ER_SELECT_REDUCED), select_lex->select_number);
      push_warning(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
                   ER_SELECT_REDUCED, warn_buff);
    }
unknown's avatar
unknown committed
1494
    DBUG_RETURN(false);
1495 1496
  }

1497 1498 1499 1500
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1501
  if (!substitution)
unknown's avatar
unknown committed
1502
  {
1503
    /* We're invoked for the 1st (or the only) SELECT in the subquery UNION */
1504
    substitution= optimizer;
1505

1506
    SELECT_LEX *current= thd->lex->current_select;
unknown's avatar
unknown committed
1507

1508
    thd->lex->current_select= current->return_after_parsing();
1509
    //optimizer never use Item **ref => we can pass 0 as parameter
1510
    if (!optimizer || optimizer->fix_left(thd, 0))
1511
    {
unknown's avatar
unknown committed
1512
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1513
      DBUG_RETURN(true);
1514
    }
unknown's avatar
unknown committed
1515
    thd->lex->current_select= current;
1516

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

1520
    /*
unknown's avatar
unknown committed
1521
      As far as  Item_ref_in_optimizer do not substitute itself on fix_fields
1522 1523
      we can use same item for all selects.
    */
1524 1525
    expr= new Item_direct_ref(&select_lex->context,
                              (Item**)optimizer->get_cache(),
1526 1527
			      (char *)"<no matter>",
			      (char *)in_left_expr_name);
1528

1529 1530 1531 1532 1533
  }

  DBUG_RETURN(false);
}

1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557

/**
  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)
1558
{
1559
  DBUG_ENTER("Item_allany_subselect::transform_into_max_min");
1560
  if (!(in_strategy & SUBS_MAXMIN))
1561
    DBUG_RETURN(false);
1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605
  Item **place= optimizer->arguments() + 1;
  THD *thd= join->thd;
  SELECT_LEX *select_lex= join->select_lex;
  Item *subs;

  /*
  */
  DBUG_ASSERT(!substitution);

  if (!select_lex->group_list.elements &&
      !select_lex->having &&
      !select_lex->with_sum_func &&
      !(select_lex->next_select()) &&
      select_lex->table_list.elements)
  {
    Item_sum_hybrid *item;
    nesting_map save_allow_sum_func;
    if (func->l_op())
    {
      /*
        (ALL && (> || =>)) || (ANY && (< || =<))
        for ALL condition is inverted
      */
      item= new Item_sum_max(*select_lex->ref_pointer_array);
    }
    else
    {
      /*
        (ALL && (< || =<)) || (ANY && (> || =>))
        for ALL condition is inverted
      */
      item= new Item_sum_min(*select_lex->ref_pointer_array);
    }
    if (upper_item)
      upper_item->set_sum_test(item);
    thd->change_item_tree(select_lex->ref_pointer_array, item);
    {
      List_iterator<Item> it(select_lex->item_list);
      it++;
      thd->change_item_tree(it.ref(), item);
    }

    save_allow_sum_func= thd->lex->allow_sum_func;
    thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
unknown's avatar
unknown committed
1606
    /*
1607 1608 1609
      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
1610
    */
1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626
    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);
    subs= new Item_singlerow_subselect(select_lex);
  }
  else
  {
    Item_maxmin_subselect *item;
    subs= item= new Item_maxmin_subselect(thd, this, select_lex, func->l_op());
    if (upper_item)
      upper_item->set_sub_test(item);
1627
  }
1628 1629 1630 1631
  /* fix fields is already called for  left expression */
  subs= func->create(left_expr, subs);
  thd->change_item_tree(place, subs);
  if (subs->fix_fields(thd, &subs))
1632
    DBUG_RETURN(true);
1633 1634 1635 1636
  DBUG_ASSERT(subs == (*place)); // There was no substitutions

  select_lex->master_unit()->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
  select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
1637 1638 1639 1640
  /*
    Remove other strategies if there was (we already changed the query and
    can't apply other strategy).
  */
1641
  in_strategy= SUBS_MAXMIN;
1642

unknown's avatar
unknown committed
1643
  DBUG_RETURN(false);
1644
}
1645

1646

1647 1648 1649 1650 1651 1652 1653 1654 1655 1656
bool Item_in_subselect::fix_having(Item *having, SELECT_LEX *select_lex)
{
  bool fix_res= 0;
  if (!having->fixed)
  {
    select_lex->having_fix_field= 1;
    fix_res= having->fix_fields(thd, 0);
    select_lex->having_fix_field= 0;
  }
  return fix_res;
1657 1658
}

1659 1660 1661 1662 1663 1664 1665 1666 1667 1668
bool Item_allany_subselect::is_maxmin_applicable(JOIN *join)
{
  /*
    Check if max/min optimization applicable: It is top item of
    WHERE condition.
  */
  return (abort_on_null || (upper_item && upper_item->top_level())) &&
      !join->select_lex->master_unit()->uncacheable && !func->eqne_op();
}

1669 1670

/**
1671 1672
  Create the predicates needed to transform a single-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1673

1674 1675 1676
  @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
1677

1678 1679
  @details
  The correlated predicates are created as follows:
1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693

  - 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:
        
1694
      SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
1695 1696 1697

    = If we need to distinguish between those:

1698
      SELECT ie FROM ...
1699 1700 1701
        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
        HAVING trigcond(<is_not_null_test>(ie))

unknown's avatar
unknown committed
1702 1703
  @retval false If the new conditions were created successfully
  @retval true  Error
1704 1705
*/

unknown's avatar
unknown committed
1706
bool
1707 1708 1709
Item_in_subselect::create_single_in_to_exists_cond(JOIN * join,
                                                   Item **where_item,
                                                   Item **having_item)
1710 1711
{
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
1712
  /*
1713 1714
    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
1715
  */
1716
  Item* join_having= join->having ? join->having : join->tmp_having;
1717

1718
  DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
1719

1720 1721
  *where_item= NULL;
  *having_item= NULL;
1722

1723
  if (join_having || select_lex->with_sum_func ||
1724 1725
      select_lex->group_list.elements)
  {
unknown's avatar
unknown committed
1726
    Item *item= func->create(expr,
1727 1728
                             new Item_ref_null_helper(&select_lex->context,
                                                      this,
unknown's avatar
unknown committed
1729 1730 1731 1732
                                                      select_lex->
                                                      ref_pointer_array,
                                                      (char *)"<ref>",
                                                      this->full_name()));
1733
    if (!abort_on_null && left_expr->maybe_null)
1734 1735 1736
    {
      /* 
        We can encounter "NULL IN (SELECT ...)". Wrap the added condition
1737
        within a trig_cond.
1738
      */
1739
      item= new Item_func_trig_cond(item, get_cond_guard(0));
1740
    }
1741

1742 1743 1744
    if (!join_having)
      item->name= (char*) in_having_cond;
    if (fix_having(item, select_lex))
unknown's avatar
unknown committed
1745
      DBUG_RETURN(true);
1746
    *having_item= item;
1747 1748 1749
  }
  else
  {
unknown's avatar
unknown committed
1750 1751
    Item *item= (Item*) select_lex->item_list.head();

1752
    if (select_lex->table_list.elements)
1753
    {
1754 1755
      Item *having= item;
      Item *orig_item= item;
1756
       
unknown's avatar
unknown committed
1757
      item= func->create(expr, item);
1758
      if (!abort_on_null && orig_item->maybe_null)
unknown's avatar
unknown committed
1759
      {
1760 1761 1762 1763
	having= new Item_is_not_null_test(this, having);
        if (left_expr->maybe_null)
        {
          if (!(having= new Item_func_trig_cond(having,
1764
                                                get_cond_guard(0))))
unknown's avatar
unknown committed
1765
            DBUG_RETURN(true);
1766
        }
1767 1768
        having->name= (char*) in_having_cond;
        if (fix_having(having, select_lex))
unknown's avatar
unknown committed
1769
          DBUG_RETURN(true);
1770
        *having_item= having;
1771

1772
	item= new Item_cond_or(item,
1773
			       new Item_func_isnull(orig_item));
1774
      }
1775
      /* 
1776 1777
        If we may encounter NULL IN (SELECT ...) and care whether subquery
        result is NULL or FALSE, wrap condition in a trig_cond.
1778 1779 1780
      */
      if (!abort_on_null && left_expr->maybe_null)
      {
1781
        if (!(item= new Item_func_trig_cond(item, get_cond_guard(0))))
unknown's avatar
unknown committed
1782
          DBUG_RETURN(true);
1783
      }
1784

1785 1786 1787 1788 1789
      /*
        TODO: figure out why the following is done here in 
        single_value_transformer but there is no corresponding action in
        row_value_transformer?
      */
1790 1791
      item->name= (char *) in_additional_cond;
      if (!item->fixed && item->fix_fields(thd, 0))
unknown's avatar
unknown committed
1792
        DBUG_RETURN(true);
1793
      *where_item= item;
1794 1795 1796
    }
    else
    {
1797
      if (select_lex->master_unit()->is_union())
1798
      {
1799 1800
        Item *new_having=
          func->create(expr,
1801
                       new Item_ref_null_helper(&select_lex->context, this,
1802 1803 1804
                                            select_lex->ref_pointer_array,
                                            (char *)"<no matter>",
                                            (char *)"<result>"));
1805 1806 1807
        if (!abort_on_null && left_expr->maybe_null)
        {
          if (!(new_having= new Item_func_trig_cond(new_having,
1808
                                                    get_cond_guard(0))))
unknown's avatar
unknown committed
1809
            DBUG_RETURN(true);
1810
        }
1811

1812 1813
        new_having->name= (char*) in_having_cond;
        if (fix_having(new_having, select_lex))
unknown's avatar
unknown committed
1814
          DBUG_RETURN(true);
1815
        *having_item= new_having;
1816 1817
      }
      else
1818
        DBUG_ASSERT(false);
1819
    }
unknown's avatar
unknown committed
1820
  }
unknown's avatar
unknown committed
1821

unknown's avatar
unknown committed
1822
  DBUG_RETURN(false);
unknown's avatar
unknown committed
1823
}
unknown's avatar
unknown committed
1824

1825

1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837
/**
  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
1838 1839
  @retval false  The subquery was transformed
  @retval true   Error
1840 1841
*/

unknown's avatar
unknown committed
1842
bool
unknown's avatar
unknown committed
1843
Item_in_subselect::row_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1844
{
unknown's avatar
unknown committed
1845
  SELECT_LEX *select_lex= join->select_lex;
1846
  uint cols_num= left_expr->cols();
1847

unknown's avatar
unknown committed
1848
  DBUG_ENTER("Item_in_subselect::row_value_transformer");
unknown's avatar
unknown committed
1849

1850
  // psergey: duplicated_subselect_card_check
1851
  if (select_lex->item_list.elements != cols_num)
1852
  {
1853
    my_error(ER_OPERAND_COLUMNS, MYF(0), cols_num);
unknown's avatar
unknown committed
1854
    DBUG_RETURN(true);
1855 1856
  }

1857 1858 1859 1860
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1861
  if (!substitution)
unknown's avatar
unknown committed
1862
  {
1863
    //first call for this unit
1864
    SELECT_LEX_UNIT *master_unit= select_lex->master_unit();
1865
    substitution= optimizer;
1866

1867 1868
    SELECT_LEX *current= thd->lex->current_select;
    thd->lex->current_select= current->return_after_parsing();
1869
    //optimizer never use Item **ref => we can pass 0 as parameter
1870
    if (!optimizer || optimizer->fix_left(thd, 0))
1871
    {
unknown's avatar
unknown committed
1872
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1873
      DBUG_RETURN(true);
1874
    }
1875

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

unknown's avatar
unknown committed
1879
    thd->lex->current_select= current;
unknown's avatar
unknown committed
1880 1881 1882 1883 1884 1885 1886 1887 1888
    /*
      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
      plans with a temp table where the original JOIN was overriden by
      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;
1889 1890
  }

unknown's avatar
unknown committed
1891
  DBUG_RETURN(false);
1892 1893 1894 1895
}


/**
1896 1897
  Create the predicates needed to transform a multi-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1898

1899
  @details
unknown's avatar
unknown committed
1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934
  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)
1935 1936 1937 1938 1939

  @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
1940 1941
  @retval false  If the new conditions were created successfully
  @retval true   Error
1942 1943
*/

unknown's avatar
unknown committed
1944
bool
1945 1946 1947
Item_in_subselect::create_row_in_to_exists_cond(JOIN * join,
                                                Item **where_item,
                                                Item **having_item)
1948 1949 1950
{
  SELECT_LEX *select_lex= join->select_lex;
  uint cols_num= left_expr->cols();
1951
  /*
1952 1953
    The non-transformed HAVING clause of 'join' may be stored in two ways
    during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
1954 1955 1956
  */
  Item* join_having= join->having ? join->having : join->tmp_having;
  bool is_having_used= (join_having || select_lex->with_sum_func ||
1957 1958 1959
                        select_lex->group_list.first ||
                        !select_lex->table_list.elements);

1960
  DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
1961 1962 1963

  *where_item= NULL;
  *having_item= NULL;
1964

1965
  if (is_having_used)
unknown's avatar
unknown committed
1966
  {
unknown's avatar
unknown committed
1967
    /* TODO: say here explicitly if the order of AND parts matters or not. */
1968 1969
    Item *item_having_part2= 0;
    for (uint i= 0; i < cols_num; i++)
unknown's avatar
unknown committed
1970
    {
1971
      DBUG_ASSERT((left_expr->fixed &&
1972

1973
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
1974 1975 1976
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
1977
      if (select_lex->ref_pointer_array[i]->
1978
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
1979
        DBUG_RETURN(true);
1980 1981
      Item *item_eq=
        new Item_func_eq(new
unknown's avatar
unknown committed
1982 1983 1984 1985 1986
                         Item_ref(&select_lex->context,
                                  (*optimizer->get_cache())->
                                  addr(i),
                                  (char *)"<no matter>",
                                  (char *)in_left_expr_name),
1987
                         new
unknown's avatar
unknown committed
1988 1989 1990
                         Item_ref(&select_lex->context,
                                  select_lex->ref_pointer_array + i,
                                  (char *)"<no matter>",
unknown's avatar
unknown committed
1991
                                  (char *)"<list ref>"));
1992 1993
      Item *item_isnull=
        new Item_func_isnull(new
unknown's avatar
unknown committed
1994 1995 1996
                             Item_ref(&select_lex->context,
                                      select_lex->ref_pointer_array+i,
                                      (char *)"<no matter>",
unknown's avatar
unknown committed
1997
                                      (char *)"<list ref>"));
1998
      Item *col_item= new Item_cond_or(item_eq, item_isnull);
unknown's avatar
unknown committed
1999
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
2000 2001
      {
        if (!(col_item= new Item_func_trig_cond(col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2002
          DBUG_RETURN(true);
2003
      }
2004 2005
      *having_item= and_items(*having_item, col_item);

2006 2007 2008 2009 2010 2011 2012
      Item *item_nnull_test= 
         new Item_is_not_null_test(this,
                                   new Item_ref(&select_lex->context,
                                                select_lex->
                                                ref_pointer_array + i,
                                                (char *)"<no matter>",
                                                (char *)"<list ref>"));
unknown's avatar
unknown committed
2013
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
2014 2015 2016
      {
        if (!(item_nnull_test= 
              new Item_func_trig_cond(item_nnull_test, get_cond_guard(i))))
unknown's avatar
unknown committed
2017
          DBUG_RETURN(true);
2018 2019
      }
      item_having_part2= and_items(item_having_part2, item_nnull_test);
2020
      item_having_part2->top_level_item();
unknown's avatar
unknown committed
2021
    }
2022
    *having_item= and_items(*having_item, item_having_part2);
2023
  }
2024
  else
2025
  {
2026 2027 2028
    for (uint i= 0; i < cols_num; i++)
    {
      Item *item, *item_isnull;
2029
      DBUG_ASSERT((left_expr->fixed &&
2030
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
2031 2032 2033
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
2034
      if (select_lex->ref_pointer_array[i]->
2035
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
2036
        DBUG_RETURN(true);
2037 2038
      item=
        new Item_func_eq(new
unknown's avatar
unknown committed
2039 2040
                         Item_direct_ref(&select_lex->context,
                                         (*optimizer->get_cache())->
2041 2042 2043 2044
                                         addr(i),
                                         (char *)"<no matter>",
                                         (char *)in_left_expr_name),
                         new
unknown's avatar
unknown committed
2045 2046 2047 2048
                         Item_direct_ref(&select_lex->context,
                                         select_lex->
                                         ref_pointer_array+i,
                                         (char *)"<no matter>",
unknown's avatar
unknown committed
2049
                                         (char *)"<list ref>"));
2050 2051
      if (!abort_on_null)
      {
2052 2053 2054 2055 2056 2057 2058 2059 2060
        Item *having_col_item=
          new Item_is_not_null_test(this,
                                    new
                                    Item_ref(&select_lex->context, 
                                             select_lex->ref_pointer_array + i,
                                             (char *)"<no matter>",
                                             (char *)"<list ref>"));
        
        
2061 2062
        item_isnull= new
          Item_func_isnull(new
unknown's avatar
unknown committed
2063 2064 2065 2066
                           Item_direct_ref(&select_lex->context,
                                           select_lex->
                                           ref_pointer_array+i,
                                           (char *)"<no matter>",
unknown's avatar
unknown committed
2067
                                           (char *)"<list ref>"));
2068
        item= new Item_cond_or(item, item_isnull);
2069 2070 2071 2072
        /* 
          TODO: why we create the above for cases where the right part
                cant be NULL?
        */
unknown's avatar
unknown committed
2073
        if (left_expr->element_index(i)->maybe_null)
2074 2075
        {
          if (!(item= new Item_func_trig_cond(item, get_cond_guard(i))))
unknown's avatar
unknown committed
2076
            DBUG_RETURN(true);
2077 2078
          if (!(having_col_item= 
                  new Item_func_trig_cond(having_col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2079
            DBUG_RETURN(true);
2080
        }
2081
        *having_item= and_items(*having_item, having_col_item);
2082
      }
2083
      *where_item= and_items(*where_item, item);
2084
    }
unknown's avatar
unknown committed
2085
  }
2086

2087
  if (*where_item)
2088
  {
2089
    if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
unknown's avatar
unknown committed
2090
      DBUG_RETURN(true);
2091
    (*where_item)->top_level_item();
2092
  }
unknown's avatar
unknown committed
2093

2094
  if (*having_item)
2095
  {
2096 2097 2098
    if (!join_having)
      (*having_item)->name= (char*) in_having_cond;
    if (fix_having(*having_item, select_lex))
unknown's avatar
unknown committed
2099
      DBUG_RETURN(true);
2100
    (*having_item)->top_level_item();
2101
  }
unknown's avatar
unknown committed
2102

unknown's avatar
unknown committed
2103
  DBUG_RETURN(false);
unknown's avatar
unknown committed
2104 2105
}

2106

unknown's avatar
unknown committed
2107
bool
unknown's avatar
unknown committed
2108
Item_in_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2109
{
2110
  return select_in_like_transformer(join);
2111 2112 2113
}


unknown's avatar
unknown committed
2114
/**
2115 2116
  Create the predicates needed to transform an IN/ALL/ANY subselect into a
  correlated EXISTS via predicate injection.
2117

2118
  @param join_arg  Join object of the subquery.
2119

2120 2121 2122 2123
  @retval FALSE  ok
  @retval TRUE   error
*/

2124 2125
bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
{
unknown's avatar
unknown committed
2126
  bool res;
2127 2128 2129 2130

  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE ||
              engine->engine_type() == subselect_engine::UNION_ENGINE);
  /*
2131
    TODO: the call to init_cond_guards allocates and initializes an
2132 2133 2134
    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.
2135
    If the dependency is removed, the call can be moved to a later phase.
2136 2137 2138 2139 2140 2141 2142 2143 2144 2145
  */
  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));
2146

2147 2148 2149 2150
  /*
    The IN=>EXISTS transformation makes non-correlated subqueries correlated.
  */
  join_arg->select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
2151 2152 2153 2154 2155 2156 2157 2158 2159
  /*
    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
    plans with a temp table where the original JOIN was overriden by
    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
2160
  return (res);
2161 2162 2163
}


2164 2165 2166 2167 2168 2169 2170 2171 2172 2173
/**
  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
*/

2174
bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
2175
{
2176 2177 2178
  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;
2179

2180 2181 2182 2183
  DBUG_ENTER("Item_in_subselect::inject_in_to_exists_cond");

  if (where_item)
  {
unknown's avatar
unknown committed
2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201
    List<Item> *and_args= NULL;
    /*
      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.
    */
    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);
    }

2202 2203 2204
    where_item= and_items(join_arg->conds, where_item);
    if (!where_item->fixed && where_item->fix_fields(thd, 0))
      DBUG_RETURN(true);
2205
    // TIMOUR TODO: call optimize_cond() for the new where clause
2206 2207 2208
    thd->change_item_tree(&select_lex->where, where_item);
    select_lex->where->top_level_item();
    join_arg->conds= select_lex->where;
unknown's avatar
unknown committed
2209 2210 2211 2212 2213 2214 2215 2216

    /* 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();
      and_args->concat((List<Item> *) &join_arg->cond_equal->current_level);
    }
2217
  }
2218

2219 2220 2221 2222 2223 2224
  if (having_item)
  {
    Item* join_having= join_arg->having ? join_arg->having:join_arg->tmp_having;
    having_item= and_items(join_having, having_item);
    if (fix_having(having_item, select_lex))
      DBUG_RETURN(true);
2225
    // TIMOUR TODO: call optimize_cond() for the new having clause
2226 2227 2228 2229
    thd->change_item_tree(&select_lex->having, having_item);
    select_lex->having->top_level_item();
    join_arg->having= select_lex->having;
  }
2230 2231 2232
  join_arg->thd->change_item_tree(&unit->global_parameters->select_limit,
                                  new Item_int((int32) 1));
  unit->select_limit_cnt= 1;
2233

2234
  DBUG_RETURN(false);
2235 2236 2237
}


unknown's avatar
unknown committed
2238
/**
unknown's avatar
unknown committed
2239
  Prepare IN/ALL/ANY/SOME subquery transformation and call the appropriate
unknown's avatar
unknown committed
2240
  transformation function.
2241

unknown's avatar
unknown committed
2242 2243
  @param join    JOIN object of transforming subquery

2244 2245
  @notes
  To decide which transformation procedure (scalar or row) applicable here
unknown's avatar
unknown committed
2246 2247
  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
2248 2249
  underlying transformation methods.

unknown's avatar
unknown committed
2250 2251
  @retval  false  OK
  @retval  true   Error
2252 2253
*/

unknown's avatar
unknown committed
2254
bool
2255
Item_in_subselect::select_in_like_transformer(JOIN *join)
2256
{
unknown's avatar
unknown committed
2257
  Query_arena *arena, backup;
2258
  SELECT_LEX *current= thd->lex->current_select;
2259
  const char *save_where= thd->where;
unknown's avatar
unknown committed
2260
  bool trans_res= true;
2261 2262 2263
  bool result;

  DBUG_ENTER("Item_in_subselect::select_in_like_transformer");
unknown's avatar
unknown committed
2264

unknown's avatar
unknown committed
2265 2266 2267 2268 2269 2270
  /*
    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())
2271
  {
unknown's avatar
unknown committed
2272
    if (sl->join)
2273
    {
unknown's avatar
unknown committed
2274 2275
      sl->join->order= 0;
      sl->join->skip_sort_order= 1;
2276 2277 2278
    }
  }

2279
  if (changed)
unknown's avatar
unknown committed
2280
    DBUG_RETURN(false);
2281 2282 2283 2284 2285 2286 2287

  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.
2288

2289
    //psergey: he means degenerate cases like "... IN (SELECT 1)"
2290 2291 2292
  */
  if (!optimizer)
  {
unknown's avatar
unknown committed
2293
    arena= thd->activate_stmt_arena_if_needed(&backup);
2294 2295
    result= (!(optimizer= new Item_in_optimizer(left_expr, this)));
    if (arena)
unknown's avatar
unknown committed
2296
      thd->restore_active_arena(arena, &backup);
2297 2298 2299 2300
    if (result)
      goto err;
  }

2301
  thd->lex->current_select= current->return_after_parsing();
2302
  result= (!left_expr->fixed &&
2303
           left_expr->fix_fields(thd, optimizer->arguments()));
2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317
  /* fix_fields can change reference to left_expr, we need reassign it */
  left_expr= optimizer->arguments()[0];

  thd->lex->current_select= current;
  if (result)
    goto err;

  /*
    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)
  */
2318
  arena= thd->activate_stmt_arena_if_needed(&backup);
unknown's avatar
unknown committed
2319
  if (left_expr->cols() == 1)
unknown's avatar
unknown committed
2320
    trans_res= single_value_transformer(join);
2321 2322 2323 2324 2325
  else
  {
    /* we do not support row operation for ALL/ANY/SOME */
    if (func != &eq_creator)
    {
unknown's avatar
unknown committed
2326
      if (arena)
unknown's avatar
unknown committed
2327
        thd->restore_active_arena(arena, &backup);
2328
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
2329
      DBUG_RETURN(true);
2330
    }
unknown's avatar
unknown committed
2331
    trans_res= row_value_transformer(join);
2332 2333
  }
  if (arena)
unknown's avatar
unknown committed
2334
    thd->restore_active_arena(arena, &backup);
2335 2336
err:
  thd->where= save_where;
unknown's avatar
unknown committed
2337
  DBUG_RETURN(trans_res);
unknown's avatar
unknown committed
2338 2339
}

2340

2341
void Item_in_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2342
{
2343
  if (in_strategy & SUBS_IN_TO_EXISTS)
2344
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2345 2346
  else
  {
2347
    left_expr->print(str, query_type);
2348
    str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
2349
  }
2350
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2351 2352 2353
}


2354
bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
2355
{
2356 2357
  uint outer_cols_num;
  List<Item> *inner_cols;
2358

2359
  if (in_strategy & SUBS_SEMI_JOIN)
2360 2361
    return !( (*ref)= new Item_int(1));

2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406
  /*
    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();

    if (unit->is_union())
      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);
      return TRUE;
    }
    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()))
          return TRUE;
      }
    }
  }

Sergey Glukhov's avatar
Sergey Glukhov committed
2407
  if ((thd_arg->lex->context_analysis_only & CONTEXT_ANALYSIS_ONLY_VIEW) &&
Michael Widenius's avatar
Michael Widenius committed
2408
      left_expr && !left_expr->fixed &&
2409 2410 2411 2412 2413 2414 2415
      left_expr->fix_fields(thd_arg, &left_expr))
    return TRUE;
  if (Item_subselect::fix_fields(thd_arg, ref))
    return TRUE;

  fixed= TRUE;
  return FALSE;
2416 2417
}

2418

2419 2420 2421 2422 2423 2424 2425 2426 2427 2428 2429 2430
void Item_in_subselect::fix_after_pullout(st_select_lex *new_parent, Item **ref)
{
  left_expr->fix_after_pullout(new_parent, &left_expr);
  Item_subselect::fix_after_pullout(new_parent, ref);
}

void Item_in_subselect::update_used_tables()
{
  Item_subselect::update_used_tables();
  left_expr->update_used_tables();
  used_tables_cache |= left_expr->used_tables();
}
2431

2432

2433
/**
2434 2435
  Try to create and initialize an engine to compute a subselect via
  materialization.
2436 2437

  @details
2438 2439 2440 2441 2442
  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,
2443 2444 2445 2446 2447 2448

  @returns
    @retval TRUE  memory allocation error occurred
    @retval FALSE an execution method was chosen successfully
*/

2449
bool Item_in_subselect::setup_mat_engine()
2450
{
2451 2452
  subselect_hash_sj_engine       *mat_engine= NULL;
  subselect_single_select_engine *select_engine;
2453

2454
  DBUG_ENTER("Item_in_subselect::setup_mat_engine");
2455

2456 2457 2458 2459 2460 2461 2462
  /*
    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;
2463

2464 2465 2466
  /* Create/initialize execution objects. */
  if (!(mat_engine= new subselect_hash_sj_engine(thd, this, select_engine)))
    DBUG_RETURN(TRUE);
2467

Sergey Petrunya's avatar
Sergey Petrunya committed
2468 2469
  if (mat_engine->init(&select_engine->join->fields_list,
                       engine->get_identifier()))
2470
    DBUG_RETURN(TRUE);
2471

2472 2473
  engine= mat_engine;
  DBUG_RETURN(FALSE);
2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497
}


/**
  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;

  outer_join= unit->outer_select()->join;
  /*
    An IN predicate might be evaluated in a query for which all tables have
    been optimzied away.
  */ 
2498
  if (!outer_join || !outer_join->table_count || !outer_join->tables_list)
2499 2500 2501 2502 2503 2504 2505 2506 2507
    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),
2508
                                                 FALSE);
2509 2510 2511 2512 2513 2514 2515
    if (!cur_item_cache || left_expr_cache->push_front(cur_item_cache))
      return TRUE;
  }
  return FALSE;
}


2516
bool Item_in_subselect::init_cond_guards()
2517
{
2518 2519 2520 2521 2522 2523 2524 2525 2526
  uint cols_num= left_expr->cols();
  if (!abort_on_null && left_expr->maybe_null && !pushed_cond_guards)
  {
    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;
2527 2528 2529
}


unknown's avatar
unknown committed
2530
bool
unknown's avatar
unknown committed
2531
Item_allany_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2532
{
2533
  DBUG_ENTER("Item_allany_subselect::select_transformer");
2534 2535
  DBUG_ASSERT((in_strategy & ~(SUBS_MAXMIN | SUBS_IN_TO_EXISTS)) == 0);
  in_strategy|= SUBS_IN_TO_EXISTS;
2536 2537
  if (upper_item)
    upper_item->show= 1;
2538
  DBUG_RETURN(select_in_like_transformer(join));
unknown's avatar
unknown committed
2539 2540
}

unknown's avatar
unknown committed
2541

2542
void Item_allany_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2543
{
2544
  if (in_strategy & SUBS_IN_TO_EXISTS)
2545
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2546 2547
  else
  {
2548
    left_expr->print(str, query_type);
unknown's avatar
unknown committed
2549
    str->append(' ');
unknown's avatar
unknown committed
2550 2551
    str->append(func->symbol(all));
    str->append(all ? " all " : " any ", 5);
unknown's avatar
unknown committed
2552
  }
2553
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2554 2555 2556
}


2557 2558 2559 2560 2561 2562 2563 2564
void subselect_engine::set_thd(THD *thd_arg)
{
  thd= thd_arg;
  if (result)
    result->set_thd(thd_arg);
}


2565
subselect_single_select_engine::
unknown's avatar
unknown committed
2566
subselect_single_select_engine(THD *thd_arg, st_select_lex *select,
2567
			       select_result_interceptor *result_arg,
2568
			       Item_subselect *item_arg)
unknown's avatar
unknown committed
2569
  :subselect_engine(thd_arg, item_arg, result_arg),
2570
   prepared(0), executed(0), select_lex(select), join(0)
unknown's avatar
unknown committed
2571
{
2572
  select_lex->master_unit()->item= item_arg;
unknown's avatar
unknown committed
2573 2574
}

2575 2576 2577 2578
int subselect_single_select_engine::get_identifier()
{
  return select_lex->select_number; 
}
unknown's avatar
unknown committed
2579

unknown's avatar
unknown committed
2580 2581
void subselect_single_select_engine::cleanup()
{
unknown's avatar
unknown committed
2582
  DBUG_ENTER("subselect_single_select_engine::cleanup");
2583
  prepared= executed= 0;
2584
  join= 0;
2585
  result->cleanup();
2586
  select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
unknown's avatar
unknown committed
2587
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2588
}
2589

unknown's avatar
unknown committed
2590 2591 2592 2593 2594

void subselect_union_engine::cleanup()
{
  DBUG_ENTER("subselect_union_engine::cleanup");
  unit->reinit_exec_mechanism();
2595
  result->cleanup();
2596 2597 2598
  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
2599
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2600
}
2601

unknown's avatar
unknown committed
2602

2603 2604 2605 2606 2607 2608
bool subselect_union_engine::is_executed() const
{
  return unit->executed;
}


2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629
/*
  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: */
  return test(!unit->fake_select_lex->join->send_records);
}

2630

unknown's avatar
unknown committed
2631 2632 2633
void subselect_uniquesubquery_engine::cleanup()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
2634 2635 2636
  /* Tell handler we don't need the index anymore */
  if (tab->table->file->inited)
    tab->table->file->ha_index_end();
unknown's avatar
unknown committed
2637 2638 2639 2640
  DBUG_VOID_RETURN;
}


unknown's avatar
unknown committed
2641
subselect_union_engine::subselect_union_engine(THD *thd_arg, st_select_lex_unit *u,
2642
					       select_result_interceptor *result_arg,
2643
					       Item_subselect *item_arg)
unknown's avatar
unknown committed
2644
  :subselect_engine(thd_arg, item_arg, result_arg)
unknown's avatar
unknown committed
2645 2646
{
  unit= u;
2647
  if (!result_arg)				//out of memory
2648
    current_thd->fatal_error();
2649
  unit->item= item_arg;
unknown's avatar
unknown committed
2650 2651
}

2652

2653 2654 2655 2656
/**
  Create and prepare the JOIN object that represents the query execution
  plan for the subquery.

2657
  @details
2658 2659 2660 2661 2662 2663 2664 2665 2666 2667 2668 2669 2670 2671 2672 2673 2674 2675 2676 2677 2678
  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
*/

unknown's avatar
unknown committed
2679 2680
int subselect_single_select_engine::prepare()
{
unknown's avatar
unknown committed
2681 2682
  if (prepared)
    return 0;
2683 2684 2685 2686
  if (select_lex->join)
  {
    select_lex->cleanup();
  }
2687 2688
  join= new JOIN(thd, select_lex->item_list,
		 select_lex->options | SELECT_NO_UNLOCK, result);
2689 2690
  if (!join || !result)
  {
2691
    thd->fatal_error();				//out of memory
2692 2693
    return 1;
  }
unknown's avatar
unknown committed
2694
  prepared= 1;
2695 2696
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
unknown's avatar
unknown committed
2697
  if (join->prepare(&select_lex->ref_pointer_array,
2698
		    select_lex->table_list.first,
unknown's avatar
unknown committed
2699
		    select_lex->with_wild,
unknown's avatar
unknown committed
2700
		    select_lex->where,
unknown's avatar
unknown committed
2701 2702
		    select_lex->order_list.elements +
		    select_lex->group_list.elements,
2703 2704
		    select_lex->order_list.first,
		    select_lex->group_list.first,
unknown's avatar
unknown committed
2705
		    select_lex->having,
2706
		    NULL, select_lex,
2707
		    select_lex->master_unit()))
unknown's avatar
unknown committed
2708
    return 1;
2709
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2710 2711 2712 2713 2714
  return 0;
}

int subselect_union_engine::prepare()
{
2715
  return unit->prepare(thd, result, SELECT_NO_UNLOCK);
unknown's avatar
unknown committed
2716 2717
}

2718
int subselect_uniquesubquery_engine::prepare()
2719
{
2720 2721
  /* Should never be called. */
  DBUG_ASSERT(FALSE);
2722 2723 2724
  return 1;
}

2725 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746

/*
  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();
}


2747 2748 2749 2750 2751
/* 
 makes storage for the output values for the subquery and calcuates 
 their data and column types and their nullability.
*/ 
void subselect_engine::set_row(List<Item> &item_list, Item_cache **row)
2752
{
2753
  Item *sel_item;
2754
  List_iterator_fast<Item> li(item_list);
2755
  res_type= STRING_RESULT;
2756
  res_field_type= MYSQL_TYPE_VAR_STRING;
2757 2758 2759 2760
  for (uint i= 0; (sel_item= li++); i++)
  {
    item->max_length= sel_item->max_length;
    res_type= sel_item->result_type();
2761
    res_field_type= sel_item->field_type();
2762
    item->decimals= sel_item->decimals;
2763
    item->unsigned_flag= sel_item->unsigned_flag;
unknown's avatar
unknown committed
2764
    maybe_null= sel_item->maybe_null;
2765
    if (!(row[i]= Item_cache::get_cache(sel_item)))
2766
      return;
2767
    row[i]->setup(sel_item);
2768
 //psergey-backport-timours:   row[i]->store(sel_item);
2769
  }
2770
  if (item_list.elements > 1)
2771
    res_type= ROW_RESULT;
2772 2773
}

2774
void subselect_single_select_engine::fix_length_and_dec(Item_cache **row)
2775
{
2776
  DBUG_ASSERT(row || select_lex->item_list.elements==1);
2777
  set_row(select_lex->item_list, row);
2778
  item->collation.set(row[0]->collation);
unknown's avatar
unknown committed
2779 2780
  if (cols() != 1)
    maybe_null= 0;
2781 2782 2783 2784 2785 2786 2787
}

void subselect_union_engine::fix_length_and_dec(Item_cache **row)
{
  DBUG_ASSERT(row || unit->first_select()->item_list.elements==1);

  if (unit->first_select()->item_list.elements == 1)
2788
  {
2789
    set_row(unit->types, row);
2790 2791
    item->collation.set(row[0]->collation);
  }
2792 2793
  else
  {
2794 2795 2796
    bool maybe_null_saved= maybe_null;
    set_row(unit->types, row);
    maybe_null= maybe_null_saved;
2797 2798
  }
}
unknown's avatar
unknown committed
2799

2800
void subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
2801 2802 2803 2804 2805
{
  //this never should be called
  DBUG_ASSERT(0);
}

2806 2807 2808 2809
int  init_read_record_seq(JOIN_TAB *tab);
int join_read_always_key_or_null(JOIN_TAB *tab);
int join_read_next_same_or_null(READ_RECORD *info);

2810
int subselect_single_select_engine::exec()
unknown's avatar
unknown committed
2811 2812
{
  DBUG_ENTER("subselect_single_select_engine::exec");
unknown's avatar
unknown committed
2813 2814 2815
  char const *save_where= thd->where;
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
2816
  if (!join->optimized)
unknown's avatar
unknown committed
2817
  {
2818 2819 2820
    SELECT_LEX_UNIT *unit= select_lex->master_unit();

    unit->set_limit(unit->global_parameters);
unknown's avatar
unknown committed
2821 2822
    if (join->optimize())
    {
unknown's avatar
unknown committed
2823
      thd->where= save_where;
unknown's avatar
unknown committed
2824
      executed= 1;
unknown's avatar
unknown committed
2825
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2826
      DBUG_RETURN(join->error ? join->error : 1);
unknown's avatar
unknown committed
2827
    }
unknown's avatar
unknown committed
2828
    if (!select_lex->uncacheable && thd->lex->describe && 
2829
        !(join->select_options & SELECT_DESCRIBE))
unknown's avatar
unknown committed
2830
    {
2831 2832 2833
      item->update_used_tables();
      if (item->const_item())
      {
2834 2835 2836 2837 2838 2839 2840 2841
        /*
          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;
2842 2843 2844 2845 2846 2847
        /*
          Force join->join_tmp creation, because this subquery will be replaced
          by a simple select from the materialization temp table by optimize()
          called by EXPLAIN and we need to preserve the initial query structure
          so we can display it.
        */
2848
        if (join->need_tmp && join->init_save_join_tab())
2849 2850
          DBUG_RETURN(1);                        /* purecov: inspected */
      }
unknown's avatar
unknown committed
2851
    }
2852 2853 2854 2855
    if (item->engine_changed)
    {
      DBUG_RETURN(1);
    }
unknown's avatar
unknown committed
2856
  }
2857 2858 2859
  if (select_lex->uncacheable &&
      select_lex->uncacheable != UNCACHEABLE_EXPLAIN
      && executed)
unknown's avatar
unknown committed
2860 2861
  {
    if (join->reinit())
2862
    {
unknown's avatar
unknown committed
2863 2864
      thd->where= save_where;
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2865
      DBUG_RETURN(1);
2866
    }
2867
    item->reset();
unknown's avatar
unknown committed
2868 2869 2870 2871
    item->assigned((executed= 0));
  }
  if (!executed)
  {
2872
    item->reset_value_registration();
2873 2874 2875
    JOIN_TAB *changed_tabs[MAX_TABLES];
    JOIN_TAB **last_changed_tab= changed_tabs;
    if (item->have_guarded_conds())
2876 2877
    {
      /*
2878
        For at least one of the pushed predicates the following is true:
2879 2880 2881 2882
        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.
      */
2883 2884
      for (JOIN_TAB *tab= first_linear_tab(join, WITHOUT_CONST_TABLES); tab;
           tab= next_linear_tab(join, tab, WITH_BUSH_ROOTS))
2885
      {
2886
        if (tab && tab->keyuse)
2887
        {
2888 2889 2890 2891 2892 2893
          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 */
2894 2895
              tab->save_read_first_record= tab->read_first_record;
              tab->save_read_record= tab->read_record.read_record;
2896 2897 2898 2899
              tab->read_first_record= init_read_record_seq;
              tab->read_record.record= tab->table->record[0];
              tab->read_record.thd= join->thd;
              tab->read_record.ref_length= tab->table->file->ref_length;
2900
              tab->read_record.unlock_row= rr_unlock_row;
2901 2902 2903 2904
              *(last_changed_tab++)= tab;
              break;
            }
          }
2905 2906 2907 2908
        }
      }
    }
    
unknown's avatar
unknown committed
2909
    join->exec();
2910

2911 2912
    /* Enable the optimizations back */
    for (JOIN_TAB **ptab= changed_tabs; ptab != last_changed_tab; ptab++)
2913
    {
2914 2915 2916
      JOIN_TAB *tab= *ptab;
      tab->read_record.record= 0;
      tab->read_record.ref_length= 0;
2917 2918
      tab->read_first_record= tab->save_read_first_record; 
      tab->read_record.read_record= tab->save_read_record;
2919
    }
unknown's avatar
unknown committed
2920
    executed= 1;
unknown's avatar
unknown committed
2921 2922
    thd->where= save_where;
    thd->lex->current_select= save_select;
2923
    DBUG_RETURN(join->error||thd->is_fatal_error);
unknown's avatar
unknown committed
2924
  }
unknown's avatar
unknown committed
2925 2926
  thd->where= save_where;
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2927 2928 2929
  DBUG_RETURN(0);
}

2930
int subselect_union_engine::exec()
unknown's avatar
unknown committed
2931
{
unknown's avatar
unknown committed
2932
  char const *save_where= thd->where;
2933
  int res= unit->exec();
unknown's avatar
unknown committed
2934
  thd->where= save_where;
2935
  return res;
unknown's avatar
unknown committed
2936 2937
}

2938

2939
/*
2940
  Search for at least one row satisfying select condition
2941 2942 2943 2944 2945 2946 2947 2948
 
  SYNOPSIS
    subselect_uniquesubquery_engine::scan_table()

  DESCRIPTION
    Scan the table using sequential access until we find at least one row
    satisfying select condition.
    
2949 2950
    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.
2951 2952 2953 2954 2955 2956 2957

  RETURN
    FALSE - OK
    TRUE  - Error
*/

int subselect_uniquesubquery_engine::scan_table()
2958 2959 2960
{
  int error;
  TABLE *table= tab->table;
2961 2962 2963 2964 2965
  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");

  if (table->file->inited)
    table->file->ha_index_end();
 
2966 2967
  if (table->file->ha_rnd_init_with_error(1))
    DBUG_RETURN(1);
2968 2969 2970 2971
  table->file->extra_opt(HA_EXTRA_CACHE,
                         current_thd->variables.read_buff_size);
  table->null_row= 0;
  for (;;)
2972
  {
2973
    error=table->file->ha_rnd_next(table->record[0]);
2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989
    if (error) {
      if (error == HA_ERR_RECORD_DELETED)
      {
        error= 0;
        continue;
      }
      if (error == HA_ERR_END_OF_FILE)
      {
        error= 0;
        break;
      }
      else
      {
        error= report_error(table, error);
        break;
      }
2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011
    }

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

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


/*
  Copy ref key and check for null parts in it

  SYNOPSIS
    subselect_uniquesubquery_engine::copy_ref_key()

  DESCRIPTION
    Copy ref key and check for null parts in it.
unknown's avatar
unknown committed
3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036
    Depending on the nullability and conversion problems this function
    recognizes and processes the following states :
      1. Partial match on top level. This means IN has a value of FALSE
         regardless of the data in the subquery table.
         Detected by finding a NULL in the left IN operand of a top level
         expression.
         We may actually skip reading the subquery, so return TRUE to skip
         the table scan in subselect_uniquesubquery_engine::exec and make
         the value of the IN predicate a NULL (that is equal to FALSE on
         top level).
      2. No exact match when IN is nested inside another predicate.
         Detected by finding a NULL in the left IN operand when IN is not
         a top level predicate.
         We cannot have an exact match. But we must proceed further with a
         table scan to find out if it's a partial match (and IN has a value
         of NULL) or no match (and IN has a value of FALSE).
         So we return FALSE to continue with the scan and see if there are
         any record that would constitute a partial match (as we cannot
         determine that from the index).
      3. Error converting the left IN operand to the column type of the
         right IN operand. This counts as no match (and 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.

3037 3038

  RETURN
unknown's avatar
unknown committed
3039 3040 3041 3042 3043
    FALSE - The value of the IN predicate is not known. Proceed to find the
            value of the IN predicate using the determined values of
            null_keypart and table->status.
    TRUE  - IN predicate has a value of NULL. Stop the processing right there
            and return NULL to the outer predicates.
3044 3045 3046 3047 3048 3049 3050
*/

bool subselect_uniquesubquery_engine::copy_ref_key()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::copy_ref_key");

  for (store_key **copy= tab->ref.key_copy ; *copy ; copy++)
3051
  {
3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062
    tab->ref.key_err= (*copy)->copy();

    /*
      When there is a NULL part in the key we don't need to make index
      lookup for such key thus we don't need to copy whole key.
      If we later should do a sequential scan return OK. Fail otherwise.

      See also the comment for the subselect_uniquesubquery_engine::exec()
      function.
    */
    null_keypart= (*copy)->null_key;
unknown's avatar
unknown committed
3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086
    if (null_keypart)
    {
      bool top_level= ((Item_in_subselect *) item)->is_top_level_item();
      if (top_level)
      {
        /* Partial match on top level */
        DBUG_RETURN(1);
      }
      else
      {
        /* No exact match when IN is nested inside another predicate */
        break;
      }
    }

    /*
      Check if the error is equal to STORE_KEY_FATAL. This is not expressed 
      using the store_key::store_key_result enum because ref.key_err is a 
      boolean and we want to detect both TRUE and STORE_KEY_FATAL from the 
      space of the union of the values of [TRUE, FALSE] and 
      store_key::store_key_result.  
      TODO: fix the variable an return types.
    */
    if (tab->ref.key_err & 1)
3087
    {
unknown's avatar
unknown committed
3088 3089 3090 3091
      /*
       Error converting the left IN operand to the column type of the right
       IN operand. 
      */
3092
      tab->table->status= STATUS_NOT_FOUND;
unknown's avatar
unknown committed
3093
      break;
3094
    }
3095
  }
3096 3097 3098
  DBUG_RETURN(0);
}

3099

3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149
/*
  @retval  1  A NULL was found in the outer reference, index lookup is
              not applicable, the outer ref is unsusable as a lookup key,
              use some other method to find a match.
  @retval  0  The outer ref was copied into an index lookup key.
  @retval -1  The outer ref cannot possibly match any row, IN is FALSE.
*/
/* TIMOUR: this method is a variant of copy_ref_key(), needs refactoring. */

int subselect_uniquesubquery_engine::copy_ref_key_simple()
{
  for (store_key **copy= tab->ref.key_copy ; *copy ; copy++)
  {
    enum store_key::store_key_result store_res;
    store_res= (*copy)->copy();
    tab->ref.key_err= store_res;

    /*
      When there is a NULL part in the key we don't need to make index
      lookup for such key thus we don't need to copy whole key.
      If we later should do a sequential scan return OK. Fail otherwise.

      See also the comment for the subselect_uniquesubquery_engine::exec()
      function.
    */
    null_keypart= (*copy)->null_key;
    if (null_keypart)
      return 1;

    /*
      Check if the error is equal to STORE_KEY_FATAL. This is not expressed 
      using the store_key::store_key_result enum because ref.key_err is a 
      boolean and we want to detect both TRUE and STORE_KEY_FATAL from the 
      space of the union of the values of [TRUE, FALSE] and 
      store_key::store_key_result.  
      TODO: fix the variable an return types.
    */
    if (store_res == store_key::STORE_KEY_FATAL)
    {
      /*
       Error converting the left IN operand to the column type of the right
       IN operand. 
      */
      return -1;
    }
  }
  return 0;
}


3150 3151 3152 3153 3154
/*
  Execute subselect

  SYNOPSIS
    subselect_uniquesubquery_engine::exec()
3155

3156 3157 3158 3159 3160 3161 3162 3163 3164 3165
  DESCRIPTION
    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)
3166
    the caller doesn't distinguish between NULL and FALSE result and we just
3167
    return FALSE. 
3168 3169 3170 3171 3172
    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.
3173 3174 3175 3176 3177 3178
  NOTE
    
  RETURN
    FALSE - ok
    TRUE  - an error occured while scanning
*/
3179

3180
int subselect_uniquesubquery_engine::exec()
3181 3182 3183 3184
{
  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
  int error;
  TABLE *table= tab->table;
3185
  empty_result_set= TRUE;
unknown's avatar
unknown committed
3186
  table->status= 0;
3187 3188 3189
 
  /* TODO: change to use of 'full_scan' here? */
  if (copy_ref_key())
3190 3191 3192 3193 3194
  {
    /*
      TIMOUR: copy_ref_key() == 1 means NULL result, not error, why return 1?
      Check who reiles on this result.
    */
3195
    DBUG_RETURN(1);
3196
  }
unknown's avatar
unknown committed
3197 3198 3199 3200 3201 3202 3203 3204 3205
  if (table->status)
  {
    /* 
      We know that there will be no rows even if we scan. 
      Can be set in copy_ref_key.
    */
    ((Item_in_subselect *) item)->value= 0;
    DBUG_RETURN(0);
  }
3206 3207 3208 3209

  if (null_keypart)
    DBUG_RETURN(scan_table());
 
3210
  if (!table->file->inited)
3211
    table->file->ha_index_init(tab->ref.key, 0);
3212 3213 3214 3215 3216
  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);
3217 3218
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3219
    error= report_error(table, error);
3220 3221
  else
  {
3222 3223
    error= 0;
    table->null_row= 0;
3224 3225 3226 3227 3228 3229 3230
    if (!table->status && (!cond || cond->val_int()))
    {
      ((Item_in_subselect *) item)->value= 1;
      empty_result_set= FALSE;
    }
    else
      ((Item_in_subselect *) item)->value= 0;
3231
  }
3232

3233
  DBUG_RETURN(error != 0);
3234 3235
}

3236

3237
/*
3238
  TIMOUR: write comment
3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254
*/

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));
3255 3256

  if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3257
  {
3258 3259 3260 3261 3262 3263
    /*
      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);
3264 3265
  }

3266 3267 3268 3269 3270 3271 3272
  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);
3273 3274 3275 3276
}



3277
subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
3278
{
3279
  /* Tell handler we don't need the index anymore */
3280 3281
  //psergey-merge-todo: the following was gone in 6.0:
 //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
3282 3283
}

3284

3285 3286 3287 3288
/*
  Index-lookup subselect 'engine' - run the subquery

  SYNOPSIS
3289
    subselect_indexsubquery_engine:exec()
3290 3291 3292
      full_scan 

  DESCRIPTION
3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325
    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.

  TODO
    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.
3326

3327 3328 3329 3330
    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.
3331 3332 3333 3334 3335 3336

  RETURN
    0
    1
*/

3337
int subselect_indexsubquery_engine::exec()
3338
{
3339
  DBUG_ENTER("subselect_indexsubquery_engine::exec");
3340
  int error;
3341
  bool null_finding= 0;
3342
  TABLE *table= tab->table;
3343

3344
  ((Item_in_subselect *) item)->value= 0;
3345 3346
  empty_result_set= TRUE;
  null_keypart= 0;
3347
  table->status= 0;
3348

3349 3350
  if (check_null)
  {
3351
    /* We need to check for NULL if there wasn't a matching value */
3352
    *tab->ref.null_ref_key= 0;			// Search first for not null
3353 3354 3355
    ((Item_in_subselect *) item)->was_null= 0;
  }

3356 3357 3358 3359
  /* Copy the ref key and check for nulls... */
  if (copy_ref_key())
    DBUG_RETURN(1);

3360 3361 3362 3363 3364 3365 3366 3367 3368 3369
  if (table->status)
  {
    /* 
      We know that there will be no rows even if we scan. 
      Can be set in copy_ref_key.
    */
    ((Item_in_subselect *) item)->value= 0;
    DBUG_RETURN(0);
  }

3370 3371
  if (null_keypart)
    DBUG_RETURN(scan_table());
3372 3373

  if (!table->file->inited)
3374
    table->file->ha_index_init(tab->ref.key, 1);
3375 3376 3377 3378 3379
  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);
3380 3381
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3382
    error= report_error(table, error);
3383 3384
  else
  {
3385
    for (;;)
3386
    {
3387 3388 3389
      error= 0;
      table->null_row= 0;
      if (!table->status)
3390
      {
3391
        if ((!cond || cond->val_int()) && (!having || having->val_int()))
3392
        {
3393
          empty_result_set= FALSE;
3394 3395 3396 3397 3398 3399
          if (null_finding)
            ((Item_in_subselect *) item)->was_null= 1;
          else
            ((Item_in_subselect *) item)->value= 1;
          break;
        }
3400 3401 3402
        error= table->file->ha_index_next_same(table->record[0],
                                               tab->ref.key_buff,
                                               tab->ref.key_length);
3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417
        if (error && error != HA_ERR_END_OF_FILE)
        {
          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 */
        if ((error= (safe_index_read(tab) == 1)))
          break;
3418
      }
3419 3420
    }
  }
3421
  DBUG_RETURN(error != 0);
3422 3423
}

3424

unknown's avatar
unknown committed
3425 3426
uint subselect_single_select_engine::cols()
{
3427 3428 3429 3430
  //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
3431 3432
}

unknown's avatar
unknown committed
3433

unknown's avatar
unknown committed
3434 3435
uint subselect_union_engine::cols()
{
3436 3437
  DBUG_ASSERT(unit->is_prepared());  // should be called after fix_fields()
  return unit->types.elements;
unknown's avatar
unknown committed
3438 3439
}

unknown's avatar
unknown committed
3440

3441
uint8 subselect_single_select_engine::uncacheable()
3442 3443 3444 3445
{
  return select_lex->uncacheable;
}

unknown's avatar
unknown committed
3446

3447
uint8 subselect_union_engine::uncacheable()
3448 3449 3450 3451
{
  return unit->uncacheable;
}

unknown's avatar
unknown committed
3452

unknown's avatar
unknown committed
3453 3454 3455 3456 3457 3458 3459 3460 3461
void subselect_single_select_engine::exclude()
{
  select_lex->master_unit()->exclude_level();
}

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

unknown's avatar
unknown committed
3463

3464
void subselect_uniquesubquery_engine::exclude()
3465 3466 3467 3468
{
  //this never should be called
  DBUG_ASSERT(0);
}
3469 3470 3471 3472 3473


table_map subselect_engine::calc_const_tables(TABLE_LIST *table)
{
  table_map map= 0;
unknown's avatar
unknown committed
3474
  for (; table; table= table->next_leaf)
3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485
  {
    TABLE *tbl= table->table;
    if (tbl && tbl->const_table)
      map|= tbl->map;
  }
  return map;
}


table_map subselect_single_select_engine::upper_select_const_tables()
{
3486
  return calc_const_tables(select_lex->outer_select()->leaf_tables);
3487 3488
}

unknown's avatar
merge  
unknown committed
3489

3490 3491
table_map subselect_union_engine::upper_select_const_tables()
{
3492
  return calc_const_tables(unit->outer_select()->leaf_tables);
3493
}
unknown's avatar
merge  
unknown committed
3494 3495


3496 3497
void subselect_single_select_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3498
{
3499
  select_lex->print(thd, str, query_type);
unknown's avatar
unknown committed
3500 3501 3502
}


3503
void subselect_union_engine::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3504
{
3505
  unit->print(str, query_type);
unknown's avatar
unknown committed
3506 3507 3508
}


3509 3510
void subselect_uniquesubquery_engine::print(String *str,
                                            enum_query_type query_type)
unknown's avatar
unknown committed
3511
{
3512
  char *table_name= tab->table->s->table_name.str;
3513
  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
3514
  tab->ref.items[0]->print(str, query_type);
3515
  str->append(STRING_WITH_LEN(" in "));
3516 3517 3518 3519 3520 3521 3522 3523 3524 3525
  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
    str->append(table_name, tab->table->s->table_name.length);
unknown's avatar
unknown committed
3526
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3527
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3528
  str->append(key_info->name);
unknown's avatar
unknown committed
3529 3530
  if (cond)
  {
3531
    str->append(STRING_WITH_LEN(" where "));
3532
    cond->print(str, query_type);
unknown's avatar
unknown committed
3533 3534 3535 3536
  }
  str->append(')');
}

3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559
/*
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>("));
  for (uint i= 0; i < key_info->key_parts; i++)
    tab->ref.items[i]->print(str);
  str->append(STRING_WITH_LEN(" in "));
  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
  str->append(STRING_WITH_LEN(" on "));
  str->append(key_info->name);
  if (cond)
  {
    str->append(STRING_WITH_LEN(" where "));
    cond->print(str);
  }
  str->append(')');
}
*/
unknown's avatar
unknown committed
3560

3561 3562
void subselect_indexsubquery_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3563
{
3564
  str->append(STRING_WITH_LEN("<index_lookup>("));
3565
  tab->ref.items[0]->print(str, query_type);
3566
  str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
3567
  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
unknown's avatar
unknown committed
3568
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3569
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3570
  str->append(key_info->name);
unknown's avatar
unknown committed
3571
  if (check_null)
3572
    str->append(STRING_WITH_LEN(" checking NULL"));
3573
  if (cond)
unknown's avatar
unknown committed
3574
  {
3575
    str->append(STRING_WITH_LEN(" where "));
3576
    cond->print(str, query_type);
unknown's avatar
unknown committed
3577
  }
3578 3579 3580
  if (having)
  {
    str->append(STRING_WITH_LEN(" having "));
3581
    having->print(str, query_type);
3582
  }
unknown's avatar
unknown committed
3583 3584
  str->append(')');
}
3585

unknown's avatar
unknown committed
3586 3587
/**
  change select_result object of engine.
3588

unknown's avatar
unknown committed
3589 3590
  @param si		new subselect Item
  @param res		new select_result object
3591
  @param temp           temporary assignment
3592

unknown's avatar
unknown committed
3593
  @retval
unknown's avatar
unknown committed
3594
    FALSE OK
unknown's avatar
unknown committed
3595
  @retval
unknown's avatar
unknown committed
3596
    TRUE  error
3597 3598
*/

3599 3600 3601 3602
bool
subselect_single_select_engine::change_result(Item_subselect *si,
                                              select_result_interceptor *res,
                                              bool temp)
3603 3604
{
  item= si;
3605
  if (temp)
3606 3607 3608 3609 3610 3611
  {
    /*
      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.
    */
3612
    thd->change_item_tree((Item**) &result, (Item*)res);
3613
  }
3614 3615
  else
    result= res;
3616 3617 3618 3619 3620 3621 3622 3623 3624

  /*
    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.
  */
  return select_lex->join->change_result(res);
3625 3626 3627
}


unknown's avatar
unknown committed
3628 3629
/**
  change select_result object of engine.
3630

unknown's avatar
unknown committed
3631 3632
  @param si		new subselect Item
  @param res		new select_result object
3633

unknown's avatar
unknown committed
3634
  @retval
unknown's avatar
unknown committed
3635
    FALSE OK
unknown's avatar
unknown committed
3636
  @retval
unknown's avatar
unknown committed
3637
    TRUE  error
3638 3639
*/

unknown's avatar
unknown committed
3640
bool subselect_union_engine::change_result(Item_subselect *si,
3641 3642
                                           select_result_interceptor *res,
                                           bool temp)
3643 3644 3645
{
  item= si;
  int rc= unit->change_result(res, result);
3646 3647 3648 3649
  if (temp)
    thd->change_item_tree((Item**) &result, (Item*)res);
  else
    result= res;
3650 3651 3652 3653
  return rc;
}


unknown's avatar
unknown committed
3654 3655
/**
  change select_result emulation, never should be called.
3656

unknown's avatar
unknown committed
3657 3658
  @param si		new subselect Item
  @param res		new select_result object
3659

unknown's avatar
unknown committed
3660
  @retval
unknown's avatar
unknown committed
3661
    FALSE OK
unknown's avatar
unknown committed
3662
  @retval
unknown's avatar
unknown committed
3663
    TRUE  error
3664 3665
*/

3666 3667 3668 3669 3670
bool
subselect_uniquesubquery_engine::change_result(Item_subselect *si,
                                               select_result_interceptor *res,
                                               bool temp
                                               __attribute__((unused)))
3671 3672
{
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
3673
  return TRUE;
3674
}
3675 3676


unknown's avatar
unknown committed
3677 3678
/**
  Report about presence of tables in subquery.
3679

unknown's avatar
unknown committed
3680
  @retval
3681
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3682
  @retval
3683 3684 3685 3686 3687 3688 3689 3690
    FALSE there are some tables in subquery
*/
bool subselect_single_select_engine::no_tables()
{
  return(select_lex->table_list.elements == 0);
}


3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706
/*
  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
3707 3708
/**
  Report about presence of tables in subquery.
3709

unknown's avatar
unknown committed
3710
  @retval
3711
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3712
  @retval
3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725
    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
3726 3727
/**
  Report about presence of tables in subquery.
3728

unknown's avatar
unknown committed
3729
  @retval
3730
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3731
  @retval
3732 3733 3734 3735 3736 3737
    FALSE there are some tables in subquery
*/

bool subselect_uniquesubquery_engine::no_tables()
{
  /* returning value is correct, but this method should never be called */
3738
  DBUG_ASSERT(FALSE);
3739 3740
  return 0;
}
3741 3742 3743 3744 3745 3746 3747


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


3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761
/**
  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.
3762 3763 3764 3765 3766 3767 3768 3769 3770

  @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
3771 3772
*/

3773 3774
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_schema()
3775 3776 3777 3778
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;

  if (item_in->is_top_level_item())
3779
    return COMPLETE_MATCH;
3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801
  else
  {
    List_iterator<Item> inner_col_it(*item_in->unit->get_unit_column_types());
    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)
3802 3803
    return PARTIAL_MATCH;
  return COMPLETE_MATCH;
3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814
}


/**
  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.
3815 3816 3817

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

3820 3821
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_data()
3822 3823 3824 3825 3826 3827
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
  Item *outer_col;

3828 3829 3830 3831 3832 3833
  /*
    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;
3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856

  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;
    }
    if (result_sink->get_null_count_of_col(i) ==
               tmp_table->file->stats.records)
      ++count_null_only_columns;
  }

  /* If no column contains NULLs use regular hash index lookups. */
  if (!count_partial_match_columns)
3857 3858 3859
    return COMPLETE_MATCH;
  return PARTIAL_MATCH;
}
3860

3861 3862 3863 3864 3865 3866

void
subselect_hash_sj_engine::choose_partial_match_strategy(
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
3867
  ulonglong pm_buff_size;
3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928 3929 3930 3931

  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
    when this will be overriden is when the total size of all buffers for the
    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,
                                        partial_match_key_parts);
    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.
*/

3932
ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
3933 3934 3935
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
3936 3937
  /* Total size of all buffers used by partial matching. */
  ulonglong buff_size;
3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964 3965 3966 3967 3968
  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;

  /* 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 */
      buff_size+= bitmap_buffer_size(result_sink->get_max_null_of_col(i));
    }
  }

  return buff_size;
3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991
}


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

static my_bool
bitmap_init_memroot(MY_BITMAP *map, uint n_bits, MEM_ROOT *mem_root)
{
  my_bitmap_map *bitmap_buf;

  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(mem_root,
                                                bitmap_buffer_size(n_bits))) ||
      bitmap_init(map, bitmap_buf, n_bits, FALSE))
    return TRUE;
  bitmap_clear_all(map);
  return FALSE;
}


3992 3993 3994 3995
/**
  Create all structures needed for IN execution that can live between PS
  reexecution.

3996
  @param tmp_columns the items that produce the data for the temp table
3997 3998
  @param subquery_id subquery's identifier (to make "<subquery%d>" name for
                                            EXPLAIN)
3999 4000

  @details
4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013
  - 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
4014
bool subselect_hash_sj_engine::init(List<Item> *tmp_columns, uint subquery_id)
4015
{
4016
  select_union *result_sink;
4017 4018 4019
  /* Options to create_tmp_table. */
  ulonglong tmp_create_options= thd->options | TMP_TABLE_ALL_COLUMNS;
                             /* | TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM */
4020

4021
  DBUG_ENTER("subselect_hash_sj_engine::init");
4022

4023 4024 4025 4026 4027
  if (bitmap_init_memroot(&non_null_key_parts, tmp_columns->elements,
                            thd->mem_root) ||
      bitmap_init_memroot(&partial_match_key_parts, tmp_columns->elements,
                            thd->mem_root))
    DBUG_RETURN(TRUE);
4028 4029 4030 4031 4032 4033

  /*
    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.
  */
4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 4044 4045 4046
/*
  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))
4047
    DBUG_RETURN(TRUE);
4048 4049
  }
*/
4050
  if (!(result_sink= new select_materialize_with_stats))
4051
    DBUG_RETURN(TRUE);
Sergey Petrunya's avatar
Sergey Petrunya committed
4052
    
4053
  char buf[32];
4054
  uint len= my_snprintf(buf, sizeof(buf), "<subquery%d>", subquery_id);
4055 4056 4057 4058 4059
  char *name;
  if (!(name= (char*)thd->alloc(len + 1)))
    DBUG_RETURN(TRUE);
  memcpy(name, buf, len+1);

4060 4061 4062
  result_sink->get_tmp_table_param()->materialized_subquery= true;
  if (result_sink->create_result_table(thd, tmp_columns, TRUE,
                                       tmp_create_options,
4063
                         name, TRUE))
4064 4065
    DBUG_RETURN(TRUE);

4066 4067
  tmp_table= result_sink->table;
  result= result_sink;
4068 4069

  /*
4070 4071 4072 4073 4074 4075 4076
    If the subquery has blobs, or the total key lenght is bigger than
    some length, or the total number of key parts is more than the
    allowed maximum (currently MAX_REF_PARTS == 16), then the created
    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.
4077 4078 4079 4080 4081 4082 4083 4084
  */
  if (tmp_table->s->keys == 0)
  {
    DBUG_ASSERT(
      tmp_table->s->uniques ||
      tmp_table->key_info->key_length >= tmp_table->file->max_key_length() ||
      tmp_table->key_info->key_parts > tmp_table->file->max_key_parts());
    free_tmp_table(thd, tmp_table);
4085
    tmp_table= NULL;
4086 4087 4088 4089 4090 4091 4092 4093 4094
    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.
  */
4095 4096 4097
  DBUG_ASSERT(tmp_table->s->keys == 1 &&
              ((Item_in_subselect *) item)->left_expr->cols() ==
              tmp_table->key_info->key_parts);
4098

4099 4100 4101
  if (make_semi_join_conds() ||
      /* A unique_engine is used both for complete and partial matching. */
      !(lookup_engine= make_unique_engine()))
4102
    DBUG_RETURN(TRUE);
4103

4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114
  /*
    Repeat name resolution for 'cond' since cond is not part of any
    clause of the query, and it is not 'fixed' during JOIN::prepare.
  */
  if (semi_join_conds && !semi_join_conds->fixed &&
      semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
    DBUG_RETURN(TRUE);
  /* Let our engine reuse this query plan for materialization. */
  materialize_join= materialize_engine->join;
  materialize_join->change_result(result);

4115 4116
  DBUG_RETURN(FALSE);
}
4117 4118


4119 4120 4121
/*
  Create an artificial condition to post-filter those rows matched by index
  lookups that cannot be distinguished by the index lookup procedure.
4122

4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137
  @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()
{
4138 4139 4140 4141 4142
  /*
    Table reference for tmp_table that is used to resolve column references
    (Item_fields) to columns in tmp_table.
  */
  TABLE_LIST *tmp_table_ref;
4143 4144 4145 4146 4147 4148 4149 4150 4151 4152
  /* Name resolution context for all tmp_table columns created below. */
  Name_resolution_context *context;
  Item_in_subselect *item_in= (Item_in_subselect *) item;

  DBUG_ENTER("subselect_hash_sj_engine::make_semi_join_conds");
  DBUG_ASSERT(semi_join_conds == NULL);

  if (!(semi_join_conds= new Item_cond_and))
    DBUG_RETURN(TRUE);

4153 4154 4155
  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
    DBUG_RETURN(TRUE);

4156
  tmp_table_ref->init_one_table("", tmp_table->alias.c_ptr(), TL_READ);
4157 4158
  tmp_table_ref->table= tmp_table;

4159
  context= new Name_resolution_context;
4160 4161 4162
  context->init();
  context->first_name_resolution_table=
    context->last_name_resolution_table= tmp_table_ref;
4163
  semi_join_conds_context= context;
4164
  
4165
  for (uint i= 0; i < item_in->left_expr->cols(); i++)
4166 4167 4168 4169 4170
  {
    Item_func_eq *eq_cond; /* New equi-join condition for the current column. */
    /* Item for the corresponding field from the materialized temp table. */
    Item_field *right_col_item;

4171 4172 4173 4174
    if (!(right_col_item= new Item_field(thd, context, tmp_table->field[i])) ||
        !(eq_cond= new Item_func_eq(item_in->left_expr->element_index(i),
                                    right_col_item)) ||
        (((Item_cond_and*)semi_join_conds)->add(eq_cond)))
4175
    {
4176 4177
      delete semi_join_conds;
      semi_join_conds= NULL;
4178 4179 4180
      DBUG_RETURN(TRUE);
    }
  }
4181
  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
4182 4183 4184 4185 4186 4187 4188
    DBUG_RETURN(TRUE);

  DBUG_RETURN(FALSE);
}


/**
4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202
  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
4203
  Item_iterator_row it(item_in->left_expr);
4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219
  /* 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
4220 4221
  tab->table= tmp_table;
  tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
4222 4223 4224 4225 4226 4227

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


4228 4229 4230 4231 4232 4233 4234
subselect_hash_sj_engine::~subselect_hash_sj_engine()
{
  delete lookup_engine;
  delete result;
  if (tmp_table)
    free_tmp_table(thd, tmp_table);
}
4235 4236


4237
int subselect_hash_sj_engine::prepare()
4238 4239 4240 4241 4242
{
  /*
    Create and optimize the JOIN that will be used to materialize
    the subquery if not yet created.
  */
4243
  return materialize_engine->prepare();
4244 4245 4246 4247 4248 4249
}


/**
  Cleanup performed after each PS execution.

4250
  @details
4251 4252 4253 4254 4255
  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
*/

void subselect_hash_sj_engine::cleanup()
{
4256
  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
4257
  is_materialized= FALSE;
4258 4259 4260 4261 4262
  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;
4263
  materialize_engine->cleanup();
4264 4265 4266 4267 4268 4269
  /*
    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;
4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285
  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. */
4286 4287 4288
  DBUG_ASSERT(tmp_table);
  free_tmp_table(thd, tmp_table);
  tmp_table= NULL;
4289 4290 4291
}


4292 4293 4294 4295 4296 4297
/*
  Get fanout produced by tables specified in the table_map
*/

double get_fanout_with_deps(JOIN *join, table_map tset)
{
4298 4299 4300 4301
  /* Handle the case of "Impossible WHERE" */
  if (join->table_count == 0)
    return 0.0;

4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326
  /* 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))
  {
4327 4328 4329 4330 4331 4332
    if ((tab->table->map & checked_deps) && !tab->emb_sj_nest && 
        tab->records_read != 0)
    {
      fanout *= rows2double(tab->records_read);
    }
  } 
4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 4367 4368 4369 4370 4371 4372 4373 4374 4375 4376 4377 4378 4379 4380 4381 4382 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417 4418
  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


4419 4420 4421 4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436
/*
  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
*/

4437
double get_post_group_estimate(JOIN* join, double join_op_rows)
4438 4439 4440 4441 4442 4443 4444 4445
{
  table_map tables_in_group_list= table_map(0);

  /* Find out which tables are used in GROUP BY list */
  for (ORDER *order= join->group_list; order; order= order->next)
  {
    Item *item= order->item[0];
    if (item->used_tables() & RAND_TABLE_BIT)
4446 4447 4448 4449
    {
      /* Each join output record will be in its own group */
      return join_op_rows;
    }
4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461
    tables_in_group_list|= item->used_tables();
  }
  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);
4462 4463 4464

#if 0
  /* The following will be needed when making use of index stats: */
4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482
  /* 
    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);
4483 4484
#endif

4485 4486 4487 4488
  return out_rows;
}


4489 4490 4491
/**
  Execute a subquery IN predicate via materialization.

4492
  @details
4493 4494 4495 4496 4497 4498 4499 4500 4501 4502
  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;
4503
  SELECT_LEX *save_select= thd->lex->current_select;
4504
  subselect_partial_match_engine *pm_engine= NULL;
4505
  int res= 0;
4506 4507 4508 4509 4510 4511 4512

  DBUG_ENTER("subselect_hash_sj_engine::exec");

  /*
    Optimize and materialize the subquery during the first execution of
    the subquery predicate.
  */
4513
  thd->lex->current_select= materialize_engine->select_lex;
4514 4515
  /* The subquery should be optimized, and materialized only once. */
  DBUG_ASSERT(materialize_join->optimized && !is_materialized);
4516 4517 4518
  materialize_join->exec();
  if ((res= test(materialize_join->error || thd->is_fatal_error)))
    goto err;
4519

4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539
  /*
    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. */
4540 4541
    item_in->reset();
    item_in->make_const();
4542 4543 4544 4545
    item_in->set_first_execution();
    DBUG_RETURN(FALSE);
  }

4546 4547 4548 4549 4550 4551 4552 4553 4554
  /*
    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();
4555 4556
  if (strategy == PARTIAL_MATCH)
  {
4557 4558 4559
    uint count_pm_keys; /* Total number of keys needed for partial matching. */
    MY_BITMAP *nn_key_parts; /* The key parts of the only non-NULL index. */
    uint covering_null_row_width;
4560 4561 4562 4563 4564 4565
    select_materialize_with_stats *result_sink=
      (select_materialize_with_stats *) result;

    nn_key_parts= (count_partial_match_columns < tmp_table->s->fields) ?
                  &non_null_key_parts : NULL;

4566 4567 4568 4569 4570 4571
    if (result_sink->get_max_nulls_in_row() ==
        tmp_table->s->fields -
        (nn_key_parts ? bitmap_bits_set(nn_key_parts) : 0))
      covering_null_row_width= result_sink->get_max_nulls_in_row();
    else
      covering_null_row_width= 0;
4572

4573
    if (covering_null_row_width)
4574 4575 4576 4577 4578
      count_pm_keys= nn_key_parts ? 1 : 0;
    else
      count_pm_keys= count_partial_match_columns - count_null_only_columns +
        (nn_key_parts ? 1 : 0);

4579 4580 4581 4582 4583 4584
    choose_partial_match_strategy(test(nn_key_parts),
                                  test(covering_null_row_width),
                                  &partial_match_key_parts);
    DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE ||
                strategy == PARTIAL_MATCH_SCAN);
    if (strategy == PARTIAL_MATCH_MERGE)
4585
    {
4586
      pm_engine=
unknown's avatar
unknown committed
4587
        new subselect_rowid_merge_engine(thd, (subselect_uniquesubquery_engine*)
4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605
                                         lookup_engine, tmp_table,
                                         count_pm_keys,
                                         covering_null_row_width,
                                         item, result,
                                         semi_join_conds->argument_list());
      if (!pm_engine ||
          ((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;
      }
4606
    }
4607 4608

    if (strategy == PARTIAL_MATCH_SCAN)
4609
    {
4610
      if (!(pm_engine=
unknown's avatar
unknown committed
4611
            new subselect_table_scan_engine(thd, (subselect_uniquesubquery_engine*)
4612 4613 4614 4615 4616 4617 4618 4619 4620
                                            lookup_engine, tmp_table,
                                            item, result,
                                            semi_join_conds->argument_list(),
                                            covering_null_row_width)))
      {
        /* This is an irrecoverable error. */
        res= 1;
        goto err;
      }
4621 4622 4623
    }
  }

4624 4625
  if (pm_engine)
    lookup_engine= pm_engine;
4626 4627 4628 4629 4630
  item_in->change_engine(lookup_engine);

err:
  thd->lex->current_select= save_select;
  DBUG_RETURN(res);
4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642
}


/**
  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(" ), "));
4643 4644 4645

  if (lookup_engine)
    lookup_engine->print(str, query_type);
4646 4647
  else
    str->append(STRING_WITH_LEN(
4648
           "<engine selected at execution time>"
4649 4650
         ));
}
4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668

void subselect_hash_sj_engine::fix_length_and_dec(Item_cache** row)
{
  DBUG_ASSERT(FALSE);
}

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,
4669 4670
                                             select_result_interceptor *res,
                                             bool temp __attribute__((unused)))
4671 4672 4673 4674 4675 4676
{
  DBUG_ASSERT(FALSE);
  return TRUE;
}


4677 4678 4679 4680
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),
4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701
    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()
{
4702 4703
  my_free((char*) key_buff, MYF(0));
  bitmap_free(&null_key);
4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720
}


/*
  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.
  */
}

4721

4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767 4768 4769 4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781 4782 4783 4784 4785 4786 4787 4788 4789 4790 4791 4792 4793 4794
/*
  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);

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

  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*));

  for (uint i= 0; i < columns_to_index->n_bits; i++)
  {
    if (!bitmap_is_set(columns_to_index, i))
      continue;
    cur_tmp_field= new Item_field(tbl->field[i]);
    /* Create the predicate (tmp_column[i] < outer_ref[i]). */
    fn_less_than= new Item_func_lt(cur_tmp_field,
                                   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*));

  key_columns[0]= new Item_field(tbl->field[col_idx]);
  /* Create the predicate (tmp_column[i] < outer_ref[i]). */
  compare_pred[0]= new Item_func_lt(key_columns[0],
                                    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;
}


4795 4796 4797 4798
/*
  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
*/

4799 4800 4801 4802
bool Ordered_key::alloc_keys_buffers()
{
  DBUG_ASSERT(key_buff_elements > 0);

4803 4804
  if (!(key_buff= (rownum_t*) my_malloc((size_t)(key_buff_elements * 
    sizeof(rownum_t)), MYF(MY_WME))))
4805 4806 4807 4808 4809 4810 4811
    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.
  */
4812
  /* Notice that max_null_row is max array index, we need count, so +1. */
4813
  if (bitmap_init(&null_key, NULL, (uint)(max_null_row + 1), FALSE))
4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876
    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;
  int error, cmp_res;
  /* 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. */
  error= tbl->file->ha_rnd_pos(tbl->record[0], rowid_a);
  DBUG_ASSERT(!error);
  error= tbl->file->ha_rnd_pos(tbl->record[1], rowid_b);
  DBUG_ASSERT(!error);
  /*
    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()
{
4877
  my_qsort2(key_buff, (size_t) key_buff_elements, sizeof(rownum_t),
4878 4879 4880 4881 4882 4883
            (qsort2_cmp) &cmp_keys_by_row_data_and_rownum, (void*) this);
  /* Invalidate the current row position. */
  cur_key_idx= HA_POS_ERROR;
}


4884
/*
4885 4886 4887
  The fraction of rows that do not contain NULL in the columns indexed by
  this key.

4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899
  @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);
}


4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017
/*
  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;
  int error, cmp_res;

  error= tbl->file->ha_rnd_pos(tbl->record[0], cur_rowid);
  DBUG_ASSERT(!error);

  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;
}


5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045
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++)
  {
    str->append(key_columns[i]->field->field_name);
    str->append(", ");
  }
  str->append(key_columns[i]->field->field_name);
  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('}');
}


5046
subselect_partial_match_engine::subselect_partial_match_engine(
unknown's avatar
unknown committed
5047
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5048 5049 5050 5051
  TABLE *tmp_table_arg, Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
  uint covering_null_row_width_arg)
unknown's avatar
unknown committed
5052
  :subselect_engine(thd_arg, item_arg, result_arg),
5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148
   tmp_table(tmp_table_arg), lookup_engine(engine_arg),
   equi_join_conds(equi_join_conds_arg),
   covering_null_row_width(covering_null_row_width_arg)
{}


int subselect_partial_match_engine::exec()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  int res;

  /* Try to find a matching row by index lookup. */
  res= lookup_engine->copy_ref_key_simple();
  if (res == -1)
  {
    /* The result is FALSE based on the outer reference. */
    item_in->value= 0;
    item_in->null_value= 0;
    return 0;
  }
  else if (res == 0)
  {
    /* Search for a complete match. */
    if ((res= lookup_engine->index_lookup()))
    {
      /* An error occured during lookup(). */
      item_in->value= 0;
      item_in->null_value= 0;
      return res;
    }
    else if (item_in->value)
    {
      /*
        A complete match was found, the result of IN is TRUE.
        Notice: (this->item == lookup_engine->item)
      */
      return 0;
    }
  }

  if (covering_null_row_width == tmp_table->s->fields)
  {
    /*
      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
5149
    DBUG_ASSERT(FALSE);
5150 5151 5152 5153
  */
}


5154 5155 5156 5157
/*
  @param non_null_key_parts  
  @param partial_match_key_parts  A union of all single-column NULL key parts.
  @param count_partial_match_columns Number of NULL keyparts (set bits above).
5158 5159 5160 5161

  @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
5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173
*/

bool
subselect_rowid_merge_engine::init(MY_BITMAP *non_null_key_parts,
                                   MY_BITMAP *partial_match_key_parts)
{
  /* 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;
5174
  uint cur_keyid= 0;
5175 5176 5177 5178 5179 5180 5181 5182 5183
  Item_in_subselect *item_in= (Item_in_subselect*) item;
  int error;

  if (keys_count == 0)
  {
    /* There is nothing to initialize, we will only do regular lookups. */
    return FALSE;
  }

5184 5185 5186 5187 5188 5189 5190
  DBUG_ASSERT(!covering_null_row_width || (covering_null_row_width &&
                                           keys_count == 1 &&
                                           non_null_key_parts));
  /*
    Allocate buffers to hold the merged keys and the mapping between rowids and
    row numbers.
  */
5191 5192
  if (!(merge_keys= (Ordered_key**) thd->alloc(keys_count *
                                               sizeof(Ordered_key*))) ||
5193 5194
      !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length),
        MYF(MY_WME))))
5195 5196 5197 5198 5199
    return TRUE;

  /* Create the only non-NULL key if there is any. */
  if (non_null_key_parts)
  {
5200
    non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
5201 5202 5203
                                  0, 0, 0, row_num_to_rowid);
    if (non_null_key->init(non_null_key_parts))
      return TRUE;
5204 5205 5206
    merge_keys[cur_keyid]= non_null_key;
    merge_keys[cur_keyid]->first();
    ++cur_keyid;
5207 5208 5209 5210
  }

  /*
    If there is a covering NULL row, the only key that is needed is the
5211 5212
    only non-NULL key that is already created above. We create keys on
    NULL-able columns only if there is no covering NULL row.
5213
  */
5214
  if (!covering_null_row_width)
5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230
  {
    if (bitmap_init_memroot(&matching_keys, keys_count, thd->mem_root) ||
        bitmap_init_memroot(&matching_outer_cols, keys_count, thd->mem_root) ||
        bitmap_init_memroot(&null_only_columns, keys_count, thd->mem_root))
      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++)
    {
      if (!bitmap_is_set(partial_match_key_parts, i))
        continue;

      if (result_sink->get_null_count_of_col(i) == row_count)
unknown's avatar
unknown committed
5231
      {
5232
        bitmap_set_bit(&null_only_columns, cur_keyid);
unknown's avatar
unknown committed
5233 5234
        continue;
      }
5235 5236
      else
      {
5237 5238 5239 5240 5241 5242 5243 5244
        merge_keys[cur_keyid]= new Ordered_key(
                                     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);
        if (merge_keys[cur_keyid]->init(i))
5245
          return TRUE;
5246
        merge_keys[cur_keyid]->first();
5247
      }
5248
      ++cur_keyid;
5249 5250
    }
  }
unknown's avatar
unknown committed
5251
  DBUG_ASSERT(cur_keyid == keys_count);
5252 5253

  /* Populate the indexes with data from the temporary table. */
5254 5255
  if (tmp_table->file->ha_rnd_init_with_error(1))
    return TRUE;
5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307
  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]);
    if (error == HA_ERR_RECORD_DELETED)
    {
      /* We get this for duplicate records that should not be in tmp_table. */
      continue;
    }
    /*
      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);
    if (error == HA_ERR_END_OF_FILE)
    {
      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);
    }

    for (uint i= (non_null_key ? 1 : 0); i < keys_count; i++)
    {
      /*
        Check if the first and only indexed column contains NULL in the curent
        row, and add the row number to the corresponding key.
      */
      if (tmp_table->field[merge_keys[i]->get_field_idx(0)]->is_null())
        merge_keys[i]->set_null(cur_rownum);
      else
        merge_keys[i]->add_key(cur_rownum);
    }
    ++cur_rownum;
  }

  tmp_table->file->ha_rnd_end();

5308 5309 5310 5311
  /* Sort all the keys by their NULL selectivity. */
  my_qsort(merge_keys, keys_count, sizeof(Ordered_key*),
           (qsort_cmp) cmp_keys_by_null_selectivity);

5312 5313 5314 5315 5316
  /* Sort the keys in each of the indexes. */
  for (uint i= 0; i < keys_count; i++)
    merge_keys[i]->sort_keys();

  if (init_queue(&pq, keys_count, 0, FALSE,
5317 5318
                 subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
                 0, 0))
5319 5320 5321 5322 5323 5324 5325 5326
    return TRUE;

  return FALSE;
}


subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
{
5327 5328 5329 5330 5331 5332 5333 5334 5335 5336
  /* None of the resources below is allocated if there are no ordered keys. */
  if (keys_count)
  {
    my_free((char*) row_num_to_rowid, MYF(0));
    for (uint i= 0; i < keys_count; i++)
      delete merge_keys[i];
    delete_queue(&pq);
    if (tmp_table->file->inited == handler::RND)
      tmp_table->file->ha_rnd_end();
  }
5337 5338 5339 5340 5341
}


void subselect_rowid_merge_engine::cleanup()
{
5342 5343 5344
}


5345
/*
5346 5347 5348 5349 5350 5351 5352 5353 5354
  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
5355 5356 5357
*/

int
5358 5359
subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
                                                           Ordered_key **k2)
5360
{
5361 5362 5363
  double k1_sel= (*k1)->null_selectivity();
  double k2_sel= (*k2)->null_selectivity();
  if (k1_sel < k2_sel)
5364
    return 1;
5365 5366 5367
  if (k1_sel > k2_sel)
    return -1;
  return 0;
5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394
}


/*
*/

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.

  @retval TRUE if a NULL row exists
  @retval FALSE otherwise
*/

bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num)
{
5395 5396
  Ordered_key *cur_key;
  uint cur_id;
5397 5398
  for (uint i = 0; i < keys_count; i++)
  {
5399 5400 5401
    cur_key= merge_keys[i];
    cur_id= cur_key->get_keyid();
    if (bitmap_is_set(&matching_keys, cur_id))
5402 5403
    {
      /*
5404 5405
        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.
5406 5407 5408
      */
      continue;
    }
5409
    if (!cur_key->is_null(row_num))
5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427
      return FALSE;
  }
  return TRUE;
}


/*
  @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;
5428
  bool res= FALSE;
5429 5430 5431

  /* 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
5432 5433
  /* The prioryty queue for keys must be empty. */
  DBUG_ASSERT(!pq.elements);
5434 5435

  /* All data accesses during execution are via handler::ha_rnd_pos() */
5436 5437 5438 5439 5440
  if (tmp_table->file->ha_rnd_init_with_error(0))
  {
    res= FALSE;
    goto end;
  }
5441

5442 5443
  /* Check if there is a match for the columns of the only non-NULL key. */
  if (non_null_key && !non_null_key->lookup())
5444 5445 5446 5447
  {
    res= FALSE;
    goto end;
  }
5448 5449 5450 5451 5452 5453

  /*
    If there is a NULL (sub)row that covers all NULL-able columns,
    then there is a guranteed partial match, and we don't need to search
    for the matching row.
   */
5454 5455 5456 5457 5458
  if (covering_null_row_width)
  {
    res= TRUE;
    goto end;
  }
5459 5460 5461 5462 5463 5464 5465 5466 5467 5468

  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);
  for (uint i= test(non_null_key); i < keys_count; i++)
  {
    DBUG_ASSERT(merge_keys[i]->get_column_count() == 1);
unknown's avatar
unknown committed
5469
    if (merge_keys[i]->get_search_key(0)->null_value)
5470 5471
    {
      ++count_nulls_in_search_key;
5472
      bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484
    }
    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
    nullable columns, the result is UNKNOWN.
  */
  if (count_nulls_in_search_key ==
      ((Item_in_subselect *) item)->left_expr->cols() -
      (non_null_key ? non_null_key->get_column_count() : 0))
5485 5486 5487 5488
  {
    res= TRUE;
    goto end;
  }
5489 5490 5491 5492 5493 5494

  /*
    If there is no NULL (sub)row that covers all NULL columns, and there is no
    single match for any of the NULL columns, the result is FALSE.
  */
  if (pq.elements - test(non_null_key) == 0)
5495 5496 5497 5498
  {
    res= FALSE;
    goto end;
  }
5499 5500 5501

  DBUG_ASSERT(pq.elements);

unknown's avatar
unknown committed
5502
  min_key= (Ordered_key*) queue_remove_top(&pq);
5503 5504
  min_row_num= min_key->current();
  bitmap_copy(&matching_keys, &null_only_columns);
5505
  bitmap_set_bit(&matching_keys, min_key->get_keyid());
5506 5507 5508 5509 5510 5511 5512 5513 5514 5515
  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.
    */
5516 5517
    res= test_null_row(min_row_num);
    goto end;
5518 5519 5520 5521
  }

  while (TRUE)
  {
unknown's avatar
unknown committed
5522
    cur_key= (Ordered_key*) queue_remove_top(&pq);
5523 5524 5525
    cur_row_num= cur_key->current();

    if (cur_row_num == min_row_num)
5526
      bitmap_set_bit(&matching_keys, cur_key->get_keyid());
5527 5528 5529 5530 5531
    else
    {
      /* Follows from the correct use of priority queue. */
      DBUG_ASSERT(cur_row_num > min_row_num);
      if (test_null_row(min_row_num))
5532 5533 5534 5535
      {
        res= TRUE;
        goto end;
      }
5536 5537 5538 5539 5540
      else
      {
        min_key= cur_key;
        min_row_num= cur_row_num;
        bitmap_copy(&matching_keys, &null_only_columns);
5541
        bitmap_set_bit(&matching_keys, min_key->get_keyid());
5542 5543 5544 5545 5546 5547 5548 5549 5550 5551
        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. */
5552 5553
      res= test_null_row(min_row_num);
      goto end;
5554 5555 5556
    }
  }

5557
  /* We should never get here - all branches must be handled explicitly above. */
5558
  DBUG_ASSERT(FALSE);
5559 5560

end:
unknown's avatar
unknown committed
5561
  queue_remove_all(&pq);
5562 5563
  tmp_table->file->ha_rnd_end();
  return res;
5564 5565 5566
}


5567
subselect_table_scan_engine::subselect_table_scan_engine(
unknown's avatar
unknown committed
5568
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5569 5570 5571 5572 5573
  TABLE *tmp_table_arg,
  Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
  uint covering_null_row_width_arg)
unknown's avatar
unknown committed
5574
  :subselect_partial_match_engine(thd_arg, engine_arg, tmp_table_arg, item_arg,
5575 5576 5577
                                  result_arg, equi_join_conds_arg,
                                  covering_null_row_width_arg)
{}
5578

5579 5580 5581 5582 5583 5584 5585

/*
  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
5586
  {
5587 5588
    count_matches= 0;
    for each row element row_i[j]
5589
    {
5590 5591
      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
        ++count_matches;
5592
    }
5593 5594
    if (count_matches == outer_ref.elements)
      return TRUE
5595
  }
5596 5597
  return FALSE
*/
5598

5599 5600 5601 5602 5603 5604 5605
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;
5606

5607 5608 5609 5610 5611 5612
  if (tmp_table->file->ha_rnd_init_with_error(1))
  {
    res= FALSE;
    goto end;
  }

5613 5614
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
                             current_thd->variables.read_buff_size);
5615
  /*
5616 5617
  TIMOUR:
  scan_table() also calls "table->null_row= 0;", why, do we need it?
5618
  */
5619
  for (;;)
5620
  {
5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652 5653 5654
    error= tmp_table->file->ha_rnd_next(tmp_table->record[0]);
    if (error) {
      if (error == HA_ERR_RECORD_DELETED)
      {
        error= 0;
        continue;
      }
      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;
    }
5655
  }
5656 5657 5658

  res= FALSE;
end:
5659
  tmp_table->file->ha_rnd_end();
5660 5661
  return res;
}
5662

5663 5664 5665

void subselect_table_scan_engine::cleanup()
{
5666
}