item_subselect.cc 147 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"

unknown's avatar
unknown committed
34

35
Item_subselect::Item_subselect():
unknown's avatar
unknown committed
36
  Item_result_field(), value_assigned(0), thd(0), substitution(0),
37 38
  expr_cache(0), engine(0), old_engine(0), used_tables_cache(0),
  have_to_be_excluded(0), const_item_cache(1), inside_first_fix_fields(0),
39
  done_first_fix_fields(FALSE), forced_const(FALSE), eliminated(FALSE),
40
  engine_changed(0), changed(0), is_correlated(FALSE)
41
{
42
  with_subselect= 1;
43
  reset();
44
  /*
45
    Item value is NULL if select_result_interceptor didn't change this value
46 47
    (i.e. some rows will be found returned)
  */
48
  null_value= TRUE;
49 50
}

51

52
void Item_subselect::init(st_select_lex *select_lex,
53
			  select_result_interceptor *result)
54
{
55 56 57 58
  /*
    Please see Item_singlerow_subselect::invalidate_and_restore_select_lex(),
    which depends on alterations to the parse tree implemented here.
  */
59 60

  DBUG_ENTER("Item_subselect::init");
unknown's avatar
unknown committed
61
  DBUG_PRINT("enter", ("select_lex: 0x%lx", (long) select_lex));
unknown's avatar
unknown committed
62
  unit= select_lex->master_unit();
unknown's avatar
unknown committed
63
  thd= unit->thd;
unknown's avatar
unknown committed
64

65 66 67 68 69 70 71
  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;
72
    parsing_place= unit->item->parsing_place;
73 74
    unit->item->engine= 0;
    unit->item= this;
unknown's avatar
unknown committed
75
    engine->change_result(this, result);
76
  }
unknown's avatar
unknown committed
77
  else
78
  {
unknown's avatar
unknown committed
79
    SELECT_LEX *outer_select= unit->outer_select();
unknown's avatar
unknown committed
80
    DBUG_ASSERT(thd);
unknown's avatar
unknown committed
81 82 83 84 85 86 87
    /*
      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);
88
    if (unit->is_union())
unknown's avatar
unknown committed
89
      engine= new subselect_union_engine(thd, unit, result, this);
90
    else
unknown's avatar
unknown committed
91
      engine= new subselect_single_select_engine(thd, select_lex, result, this);
92
  }
93 94
  {
    SELECT_LEX *upper= unit->outer_select();
95
    if (upper->parsing_place == IN_HAVING)
96
      upper->subquery_in_having= 1;
unknown's avatar
unknown committed
97 98
    /* The subquery is an expression cache candidate */
    upper->expr_cache_may_be_used[upper->parsing_place]= TRUE;
99
  }
100 101 102
  DBUG_VOID_RETURN;
}

103 104 105 106 107 108
st_select_lex *
Item_subselect::get_select_lex()
{
  return unit->first_select();
}

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

130

unknown's avatar
unknown committed
131 132 133 134 135 136
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
137
}
138

139 140 141 142 143 144 145 146 147 148 149

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;
150 151
  if (in_strategy & SUBS_MATERIALIZATION)
    in_strategy= 0;
152
  pushed_cond_guards= NULL;
153 154 155 156
  Item_subselect::cleanup();
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
157 158
Item_subselect::~Item_subselect()
{
159
  delete engine;
160
  engine= NULL;
unknown's avatar
unknown committed
161 162
}

unknown's avatar
unknown committed
163
bool
164
Item_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
165 166
{
  DBUG_ENTER("Item_subselect::select_transformer");
unknown's avatar
unknown committed
167
  DBUG_RETURN(false);
unknown's avatar
unknown committed
168 169 170
}


171
bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
172
{
unknown's avatar
unknown committed
173
  char const *save_where= thd_param->where;
unknown's avatar
unknown committed
174
  uint8 uncacheable;
unknown's avatar
unknown committed
175
  bool res;
unknown's avatar
unknown committed
176

177
  DBUG_ASSERT(fixed == 0);
unknown's avatar
unknown committed
178 179
  /* There is no reason to get a different THD. */
  DBUG_ASSERT(thd == thd_param);
180 181 182 183
  if (!done_first_fix_fields)
  {
    done_first_fix_fields= TRUE;
    inside_first_fix_fields= TRUE;
184 185 186 187 188
    upper_refs.empty();
    /*
      psergey-todo: remove _first_fix_fields calls, we need changes on every
      execution
    */
189 190
  }

Sergey Petrunia's avatar
Sergey Petrunia committed
191
  eliminated= FALSE;
192
  parent_select= thd_param->lex->current_select;
193

194
  if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
unknown's avatar
unknown committed
195
    return TRUE;
Sergey Petrunia's avatar
Sergey Petrunia committed
196
  
unknown's avatar
unknown committed
197

198
  if (!(res= engine->prepare()))
unknown's avatar
unknown committed
199
  {
200 201
    // all transformation is done (used by prepared statements)
    changed= 1;
202
    inside_first_fix_fields= FALSE;
203 204 205 206 207 208 209

    /*
      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.
    */
210 211
    if (substitution)
    {
212 213 214 215
      /*
        If the top item of the WHERE/HAVING condition changed,
        set correct WHERE/HAVING for PS.
      */
unknown's avatar
unknown committed
216
      if (unit->outer_select()->where == (*ref))
unknown's avatar
unknown committed
217
        unit->outer_select()->where= substitution;
218
      else if (unit->outer_select()->having == (*ref))
unknown's avatar
unknown committed
219
        unit->outer_select()->having= substitution;
unknown's avatar
unknown committed
220

221 222 223 224 225
      (*ref)= substitution;
      substitution->name= name;
      if (have_to_be_excluded)
	engine->exclude();
      substitution= 0;
226
      thd->where= "checking transformed subquery";
227
      if (!(*ref)->fixed)
228 229
	res= (*ref)->fix_fields(thd, ref);
      goto end;
230
//psergey-merge:  done_first_fix_fields= FALSE;
231
    }
unknown's avatar
unknown committed
232 233
    // Is it one field subselect?
    if (engine->cols() > max_columns)
234
    {
unknown's avatar
unknown committed
235
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
236
//psergey-merge:  done_first_fix_fields= FALSE;
237
      goto end;
unknown's avatar
unknown committed
238
    }
239
    fix_length_and_dec();
unknown's avatar
unknown committed
240
  }
unknown's avatar
unknown committed
241
  else
242
    goto end;
unknown's avatar
unknown committed
243 244
  
  if ((uncacheable= engine->uncacheable()))
unknown's avatar
unknown committed
245 246
  {
    const_item_cache= 0;
247 248
    if (uncacheable & UNCACHEABLE_RAND)
      used_tables_cache|= RAND_TABLE_BIT;
unknown's avatar
unknown committed
249
  }
250
  fixed= 1;
unknown's avatar
unknown committed
251

252
end:
253
  done_first_fix_fields= FALSE;
254
  thd->where= save_where;
255 256 257
  return res;
}

258

Sergey Petrunya's avatar
Sergey Petrunya committed
259
bool Item_subselect::enumerate_field_refs_processor(uchar *arg)
Sergey Petrunia's avatar
Sergey Petrunia committed
260
{
261 262 263 264
  List_iterator<Ref_to_outside> it(upper_refs);
  Ref_to_outside *upper;
  
  while ((upper= it++))
Sergey Petrunia's avatar
Sergey Petrunia committed
265
  {
266
    if (upper->item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
Sergey Petrunia's avatar
Sergey Petrunia committed
267 268 269 270 271 272 273 274 275 276 277
      return TRUE;
  }
  return FALSE;
}

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

278

279 280 281 282 283 284 285 286 287 288
/**
  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.
*/

289 290 291 292 293 294 295 296 297
bool Item_subselect::eliminate_subselect_processor(uchar *arg)
{
  unit->item= NULL;
  unit->exclude_from_tree();
  eliminated= TRUE;
  return FALSE;
}


298
/**
299 300 301
  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.
302 303 304 305 306

  @param arg  pointer to the fake select

  @return
    FALSE to force the evaluation of the processor for the subsequent items.
307 308 309 310 311 312
*/

bool Item_subselect::set_fake_select_as_master_processor(uchar *arg)
{
  SELECT_LEX *fake_select= (SELECT_LEX*) arg;
  /*
313 314
    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
315 316 317 318
    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.
319 320 321 322
  */
  if (unit->outer_select()->master_unit()->fake_select_lex == fake_select)
  {
    /*
unknown's avatar
unknown committed
323 324
      Set the master of the subquery to be the fake select (i.e. the whole
      UNION), instead of the last query in the UNION.
325
    */
unknown's avatar
unknown committed
326 327
    fake_select->add_slave(unit);
    DBUG_ASSERT(unit->outer_select() == fake_select);
328 329 330 331
    /* 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);
    /*
332 333
      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.
334 335 336 337
    */
    unit->item= this;
    eliminated= FALSE;
  }
338
  return FALSE;
339 340 341
}


342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358
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;
}

359

360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387
/*
  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;
}

388

389 390 391 392 393
class Field_fixer: public Field_enumerator
{
public:
  table_map used_tables; /* Collect used_tables here */
  st_select_lex *new_parent; /* Select we're in */
394
  virtual void visit_field(Item_field *item)
395 396 397 398 399
  {
    //for (TABLE_LIST *tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local)
    //{
    //  if (tbl->table == field->table)
    //  {
400
        used_tables|= item->field->table->map;
401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 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
    //    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.
  */
}

479
bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
480
                          uchar *argument)
481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
{

  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
496
      /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */
497 498 499 500 501 502

      while ((item=li++))
      {
        if (item->walk(processor, walk_subquery, argument))
          return 1;
      }
503
      for (order= lex->order_list.first ; order; order= order->next)
504 505 506 507
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
508
      for (order= lex->group_list.first ; order; order= order->next)
509 510 511 512 513 514 515 516 517 518
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
    }
  }
  return (this->*processor)(argument);
}


519
bool Item_subselect::exec()
520
{
521
  int res;
unknown's avatar
unknown committed
522

523 524 525 526 527
  /*
    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
528
    return 1;
529

Sergey Glukhov's avatar
Sergey Glukhov committed
530
  DBUG_ASSERT(!thd->lex->context_analysis_only);
531 532 533 534 535
  /*
    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
536

537
  res= engine->exec();
unknown's avatar
unknown committed
538

539 540 541
  if (engine_changed)
  {
    engine_changed= 0;
542
    return exec();
543 544
  }
  return (res);
545 546
}

547

unknown's avatar
unknown committed
548 549 550 551 552 553 554 555 556 557 558 559 560 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
/**
  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)));
}


598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616
/*
  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.
  */
617
  if (!left_expr_cache && (in_strategy & SUBS_MATERIALIZATION))
618 619
    init_left_expr_cache();

620 621 622 623 624 625 626 627
  /*
    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);
628 629 630 631 632 633 634 635 636 637

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


638
Item::Type Item_subselect::type() const
639 640 641 642
{
  return SUBSELECT_ITEM;
}

unknown's avatar
unknown committed
643

644 645
void Item_subselect::fix_length_and_dec()
{
646
  engine->fix_length_and_dec(0);
647
}
unknown's avatar
unknown committed
648

unknown's avatar
unknown committed
649

650
table_map Item_subselect::used_tables() const
unknown's avatar
unknown committed
651
{
652
  return (table_map) (engine->uncacheable() ? used_tables_cache : 0L);
unknown's avatar
unknown committed
653 654
}

unknown's avatar
merge  
unknown committed
655

656 657
bool Item_subselect::const_item() const
{
Sergey Glukhov's avatar
Sergey Glukhov committed
658
  return thd->lex->context_analysis_only ? FALSE : const_item_cache;
659 660
}

661
Item *Item_subselect::get_tmp_table_item(THD *thd_arg)
unknown's avatar
unknown committed
662 663
{
  if (!with_sum_func && !const_item())
unknown's avatar
unknown committed
664
    return new Item_field(result_field);
665
  return copy_or_same(thd_arg);
unknown's avatar
unknown committed
666
}
unknown's avatar
merge  
unknown committed
667

668 669
void Item_subselect::update_used_tables()
{
670
  if (!forced_const)
671
  {
672 673 674 675 676 677 678
    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;
    }
679 680 681
  }
}

unknown's avatar
unknown committed
682

683
void Item_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
684
{
685 686 687 688 689 690 691 692
  if (engine)
  {
    str->append('(');
    engine->print(str, query_type);
    str->append(')');
  }
  else
    str->append("(...)");
unknown's avatar
unknown committed
693 694 695
}


unknown's avatar
merge  
unknown committed
696
Item_singlerow_subselect::Item_singlerow_subselect(st_select_lex *select_lex)
697
  :Item_subselect(), value(0)
unknown's avatar
unknown committed
698
{
unknown's avatar
unknown committed
699
  DBUG_ENTER("Item_singlerow_subselect::Item_singlerow_subselect");
700
  init(select_lex, new select_singlerow_subselect(this));
unknown's avatar
unknown committed
701
  maybe_null= 1;
702
  max_columns= UINT_MAX;
unknown's avatar
unknown committed
703
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
704 705
}

706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725
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
726 727
Item_maxmin_subselect::Item_maxmin_subselect(THD *thd_param,
                                             Item_subselect *parent,
728
					     st_select_lex *select_lex,
unknown's avatar
unknown committed
729
					     bool max_arg)
730
  :Item_singlerow_subselect(), was_values(TRUE)
731 732
{
  DBUG_ENTER("Item_maxmin_subselect::Item_maxmin_subselect");
unknown's avatar
unknown committed
733 734
  max= max_arg;
  init(select_lex, new select_max_min_finder_subselect(this, max_arg));
735 736 737
  max_columns= 1;
  maybe_null= 1;
  max_columns= 1;
738 739 740 741 742 743

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

unknown's avatar
unknown committed
746
  /*
unknown's avatar
unknown committed
747
    this subquery always creates during preparation, so we can assign
unknown's avatar
unknown committed
748 749 750 751
    thd here
  */
  thd= thd_param;

752 753 754
  DBUG_VOID_RETURN;
}

755 756
void Item_maxmin_subselect::cleanup()
{
unknown's avatar
unknown committed
757 758 759
  DBUG_ENTER("Item_maxmin_subselect::cleanup");
  Item_singlerow_subselect::cleanup();

760
  /*
unknown's avatar
unknown committed
761
    By default it is TRUE to avoid TRUE reporting by
762 763 764
    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
765 766
    select_max_min_finder_subselect::send_data() set it back to TRUE if some
    value will be found.
767 768
  */
  was_values= TRUE;
unknown's avatar
unknown committed
769
  DBUG_VOID_RETURN;
770 771 772
}


773
void Item_maxmin_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
774
{
775
  str->append(max?"<max>":"<min>", 5);
776
  Item_singlerow_subselect::print(str, query_type);
unknown's avatar
unknown committed
777 778
}

779

unknown's avatar
unknown committed
780
void Item_singlerow_subselect::reset()
781
{
782
  Item_subselect::reset();
783
  if (value)
784
    value->null_value= TRUE;
785 786
}

787

unknown's avatar
unknown committed
788 789 790 791 792 793 794 795 796
/**
  @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
797 798 799 800

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

  @retval false  The subquery was transformed
unknown's avatar
unknown committed
801
*/
unknown's avatar
unknown committed
802
bool
unknown's avatar
unknown committed
803
Item_singlerow_subselect::select_transformer(JOIN *join)
804
{
805
  DBUG_ENTER("Item_singlerow_subselect::select_transformer");
unknown's avatar
unknown committed
806
  if (changed)
unknown's avatar
unknown committed
807
    DBUG_RETURN(false);
808

809
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
810
  Query_arena *arena= thd->stmt_arena;
unknown's avatar
unknown committed
811
 
812
  if (!select_lex->master_unit()->is_union() &&
813
      !select_lex->table_list.elements &&
unknown's avatar
unknown committed
814
      select_lex->item_list.elements == 1 &&
815
      !select_lex->item_list.head()->with_sum_func &&
unknown's avatar
unknown committed
816 817 818 819 820 821 822
      /*
	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
823
      !(select_lex->item_list.head()->type() == FIELD_ITEM ||
824
	select_lex->item_list.head()->type() == REF_ITEM) &&
825
      !join->conds && !join->having &&
826
      /*
unknown's avatar
unknown committed
827
        switch off this optimization for prepare statement,
828 829 830
        because we do not rollback this changes
        TODO: make rollback for it, or special name resolving mode in 5.0.
      */
831
      !arena->is_stmt_prepare_or_first_sp_execute()
unknown's avatar
unknown committed
832
      )
833 834
  {
    have_to_be_excluded= 1;
unknown's avatar
unknown committed
835
    if (thd->lex->describe)
836 837 838
    {
      char warn_buff[MYSQL_ERRMSG_SIZE];
      sprintf(warn_buff, ER(ER_SELECT_REDUCED), select_lex->select_number);
unknown's avatar
unknown committed
839
      push_warning(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
840 841 842
		   ER_SELECT_REDUCED, warn_buff);
    }
    substitution= select_lex->item_list.head();
unknown's avatar
unknown committed
843
    /*
unknown's avatar
unknown committed
844
      as far as we moved content to upper level, field which depend of
unknown's avatar
unknown committed
845 846
      'upper' select is not really dependent => we remove this dependence
    */
847
    substitution->walk(&Item::remove_dependence_processor, 0,
848
		       (uchar *) select_lex->outer_select());
849
  }
unknown's avatar
unknown committed
850
  DBUG_RETURN(false);
851 852
}

unknown's avatar
unknown committed
853

unknown's avatar
unknown committed
854
void Item_singlerow_subselect::store(uint i, Item *item)
unknown's avatar
unknown committed
855
{
856
  row[i]->store(item);
857 858
  //psergey-merge: can do without that: row[i]->cache_value();
  //psergey-backport-timours: ^ really, without that ^ 
859
  //psergey-try-merge-again:
860
  row[i]->cache_value();
unknown's avatar
unknown committed
861 862
}

unknown's avatar
unknown committed
863
enum Item_result Item_singlerow_subselect::result_type() const
unknown's avatar
unknown committed
864
{
865 866 867
  return engine->type();
}

868 869 870 871 872 873 874 875 876
/* 
 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
877
void Item_singlerow_subselect::fix_length_and_dec()
878
{
879 880 881 882 883
  if ((max_columns= engine->cols()) == 1)
  {
    engine->fix_length_and_dec(row= &value);
  }
  else
884
  {
885
    if (!(row= (Item_cache**) sql_alloc(sizeof(Item_cache*)*max_columns)))
886 887 888
      return;
    engine->fix_length_and_dec(row);
    value= *row;
889
  }
890
  unsigned_flag= value->unsigned_flag;
891 892 893 894 895 896 897
  /*
    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();
898 899
}

unknown's avatar
unknown committed
900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923

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

924 925 926 927 928 929
  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
930 931 932 933
  DBUG_RETURN(this);
}


unknown's avatar
unknown committed
934
uint Item_singlerow_subselect::cols()
unknown's avatar
unknown committed
935
{
936 937 938
  return engine->cols();
}

unknown's avatar
unknown committed
939
bool Item_singlerow_subselect::check_cols(uint c)
940 941 942
{
  if (c != engine->cols())
  {
unknown's avatar
unknown committed
943
    my_error(ER_OPERAND_COLUMNS, MYF(0), c);
944 945 946 947 948
    return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
949
bool Item_singlerow_subselect::null_inside()
950 951 952 953 954 955 956 957 958
{
  for (uint i= 0; i < max_columns ; i++)
  {
    if (row[i]->null_value)
      return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
959
void Item_singlerow_subselect::bring_value()
960
{
961 962 963 964
  if (!exec() && assigned())
    null_value= 0;
  else
    reset();
unknown's avatar
unknown committed
965 966
}

967
double Item_singlerow_subselect::val_real()
unknown's avatar
unknown committed
968
{
969
  DBUG_ASSERT(fixed == 1);
970
  if (!exec() && !value->null_value)
971
  {
972
    null_value= FALSE;
973
    return value->val_real();
974 975
  }
  else
unknown's avatar
unknown committed
976
  {
977
    reset();
unknown's avatar
unknown committed
978
    return 0;
unknown's avatar
unknown committed
979
  }
unknown's avatar
unknown committed
980 981
}

982
longlong Item_singlerow_subselect::val_int()
unknown's avatar
unknown committed
983
{
984
  DBUG_ASSERT(fixed == 1);
985
  if (!exec() && !value->null_value)
986
  {
987
    null_value= FALSE;
988 989 990
    return value->val_int();
  }
  else
unknown's avatar
unknown committed
991
  {
992
    reset();
unknown's avatar
unknown committed
993
    return 0;
unknown's avatar
unknown committed
994
  }
unknown's avatar
unknown committed
995 996
}

unknown's avatar
unknown committed
997
String *Item_singlerow_subselect::val_str(String *str)
unknown's avatar
unknown committed
998
{
999
  if (!exec() && !value->null_value)
1000
  {
1001
    null_value= FALSE;
1002 1003 1004
    return value->val_str(str);
  }
  else
unknown's avatar
unknown committed
1005
  {
1006
    reset();
unknown's avatar
unknown committed
1007
    return 0;
unknown's avatar
unknown committed
1008
  }
unknown's avatar
unknown committed
1009 1010
}

unknown's avatar
unknown committed
1011

unknown's avatar
unknown committed
1012 1013
my_decimal *Item_singlerow_subselect::val_decimal(my_decimal *decimal_value)
{
1014
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1015
  {
1016
    null_value= FALSE;
unknown's avatar
unknown committed
1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
    return value->val_decimal(decimal_value);
  }
  else
  {
    reset();
    return 0;
  }
}


bool Item_singlerow_subselect::val_bool()
{
1029
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1030
  {
1031
    null_value= FALSE;
unknown's avatar
unknown committed
1032 1033 1034 1035 1036 1037 1038 1039 1040 1041
    return value->val_bool();
  }
  else
  {
    reset();
    return 0;
  }
}


1042
Item_exists_subselect::Item_exists_subselect(st_select_lex *select_lex):
1043
  Item_subselect()
unknown's avatar
unknown committed
1044
{
unknown's avatar
unknown committed
1045
  DBUG_ENTER("Item_exists_subselect::Item_exists_subselect");
unknown's avatar
unknown committed
1046
  bool val_bool();
1047
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1048
  max_columns= UINT_MAX;
1049
  null_value= FALSE; //can't be NULL
unknown's avatar
unknown committed
1050 1051
  maybe_null= 0; //can't be NULL
  value= 0;
unknown's avatar
unknown committed
1052 1053 1054
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
1055

1056
void Item_exists_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
1057
{
1058
  str->append(STRING_WITH_LEN("exists"));
1059
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
1060 1061 1062
}


unknown's avatar
unknown committed
1063
bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
1064
{
1065 1066
  if (unit_arg->fake_select_lex &&
      unit_arg->fake_select_lex->test_limit())
1067
    return(1);
unknown's avatar
unknown committed
1068

1069
  SELECT_LEX *sl= unit_arg->first_select();
1070 1071
  for (; sl; sl= sl->next_select())
  {
unknown's avatar
unknown committed
1072
    if (sl->test_limit())
1073 1074 1075 1076 1077
      return(1);
  }
  return(0);
}

1078
Item_in_subselect::Item_in_subselect(Item * left_exp,
unknown's avatar
unknown committed
1079
				     st_select_lex *select_lex):
1080
  Item_exists_subselect(), left_expr_cache(0), first_execution(TRUE),
1081
  optimizer(0), pushed_cond_guards(NULL), in_strategy(0), upper_item(0)
unknown's avatar
unknown committed
1082 1083
{
  DBUG_ENTER("Item_in_subselect::Item_in_subselect");
unknown's avatar
unknown committed
1084
  left_expr= left_exp;
1085
  func= &eq_creator;
1086
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1087
  max_columns= UINT_MAX;
1088
  maybe_null= 1;
1089
  abort_on_null= 0;
1090
  reset();
unknown's avatar
unknown committed
1091
  //if test_limit will fail then error will be reported to client
1092
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1093 1094 1095
  DBUG_VOID_RETURN;
}

1096 1097 1098 1099 1100
int Item_in_subselect::get_identifier()
{
  return engine->get_identifier();
}

1101
Item_allany_subselect::Item_allany_subselect(Item * left_exp,
1102
                                             chooser_compare_func_creator fc,
unknown's avatar
unknown committed
1103 1104
					     st_select_lex *select_lex,
					     bool all_arg)
unknown's avatar
unknown committed
1105
  :Item_in_subselect(), func_creator(fc), all(all_arg)
unknown's avatar
unknown committed
1106
{
1107
  DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
unknown's avatar
unknown committed
1108
  left_expr= left_exp;
1109
  func= func_creator(all_arg);
1110
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1111
  max_columns= 1;
1112
  abort_on_null= 0;
1113
  reset();
unknown's avatar
unknown committed
1114
  //if test_limit will fail then error will be reported to client
1115
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1116
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
1117 1118
}

unknown's avatar
unknown committed
1119

1120 1121
void Item_exists_subselect::fix_length_and_dec()
{
1122
   decimals= 0;
1123
   max_length= 1;
unknown's avatar
unknown committed
1124
   max_columns= engine->cols();
1125
  /* We need only 1 row to determine existence */
1126
  unit->global_parameters->select_limit= new Item_int((int32) 1);
1127 1128
}

unknown's avatar
unknown committed
1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152

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

1153 1154 1155 1156 1157 1158
  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
1159 1160 1161 1162
  DBUG_RETURN(this);
}


1163
double Item_exists_subselect::val_real()
unknown's avatar
unknown committed
1164
{
1165
  DBUG_ASSERT(fixed == 1);
1166
  if (exec())
unknown's avatar
unknown committed
1167
  {
1168
    reset();
unknown's avatar
unknown committed
1169
    return 0;
unknown's avatar
unknown committed
1170
  }
unknown's avatar
unknown committed
1171 1172 1173
  return (double) value;
}

1174
longlong Item_exists_subselect::val_int()
unknown's avatar
unknown committed
1175
{
1176
  DBUG_ASSERT(fixed == 1);
1177
  if (exec())
unknown's avatar
unknown committed
1178
  {
1179
    reset();
unknown's avatar
unknown committed
1180
    return 0;
unknown's avatar
unknown committed
1181
  }
unknown's avatar
unknown committed
1182 1183 1184
  return value;
}

1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198

/**
  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
1199 1200
String *Item_exists_subselect::val_str(String *str)
{
1201
  DBUG_ASSERT(fixed == 1);
1202
  if (exec())
1203
    reset();
unknown's avatar
unknown committed
1204
  str->set((ulonglong)value,&my_charset_bin);
1205 1206 1207
  return str;
}

unknown's avatar
unknown committed
1208

1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221
/**
  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
1222 1223 1224
my_decimal *Item_exists_subselect::val_decimal(my_decimal *decimal_value)
{
  DBUG_ASSERT(fixed == 1);
1225
  if (exec())
unknown's avatar
unknown committed
1226 1227 1228 1229 1230 1231 1232 1233 1234
    reset();
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


bool Item_exists_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1235
  if (exec())
unknown's avatar
unknown committed
1236 1237 1238 1239
  {
    reset();
    return 0;
  }
1240
  return value != 0;
unknown's avatar
unknown committed
1241 1242 1243
}


1244
double Item_in_subselect::val_real()
1245
{
unknown's avatar
unknown committed
1246 1247 1248 1249 1250
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1251
  DBUG_ASSERT(fixed == 1);
1252
  null_value= was_null= FALSE;
1253
  if (exec())
1254 1255 1256 1257 1258
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1259
    null_value= TRUE;
1260 1261 1262
  return (double) value;
}

unknown's avatar
unknown committed
1263

1264
longlong Item_in_subselect::val_int()
1265
{
unknown's avatar
unknown committed
1266 1267 1268 1269 1270
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1271
  DBUG_ASSERT(fixed == 1);
1272
  null_value= was_null= FALSE;
1273
  if (exec())
1274 1275 1276 1277 1278
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1279
    null_value= TRUE;
1280 1281 1282
  return value;
}

unknown's avatar
unknown committed
1283

1284 1285
String *Item_in_subselect::val_str(String *str)
{
unknown's avatar
unknown committed
1286 1287 1288 1289 1290
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1291
  DBUG_ASSERT(fixed == 1);
1292
  null_value= was_null= FALSE;
1293
  if (exec())
1294 1295 1296 1297 1298 1299
  {
    reset();
    return 0;
  }
  if (was_null && !value)
  {
1300
    null_value= TRUE;
unknown's avatar
unknown committed
1301
    return 0;
unknown's avatar
unknown committed
1302
  }
unknown's avatar
unknown committed
1303
  str->set((ulonglong)value, &my_charset_bin);
unknown's avatar
unknown committed
1304 1305 1306
  return str;
}

unknown's avatar
unknown committed
1307

unknown's avatar
unknown committed
1308 1309 1310
bool Item_in_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1311
  null_value= was_null= FALSE;
1312
  if (forced_const)
1313
    return value;
1314
  if (exec())
unknown's avatar
unknown committed
1315 1316 1317 1318 1319
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1320
    null_value= TRUE;
unknown's avatar
unknown committed
1321 1322 1323 1324 1325 1326 1327 1328 1329 1330
  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);
1331
  null_value= was_null= FALSE;
unknown's avatar
unknown committed
1332
  DBUG_ASSERT(fixed == 1);
1333
  if (exec())
unknown's avatar
unknown committed
1334 1335 1336 1337 1338
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1339
    null_value= TRUE;
unknown's avatar
unknown committed
1340 1341 1342 1343 1344
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


1345 1346
/**
  Rewrite a single-column IN/ALL/ANY subselect.
1347

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

1350
  @details
unknown's avatar
unknown committed
1351
  Rewrite a single-column subquery using rule-based approach. Given the subquery
1352

1353
     oe $cmp$ (SELECT ie FROM ... WHERE subq_where ... HAVING subq_having)
1354

unknown's avatar
unknown committed
1355
  First, try to convert the subquery to a scalar-result subquery in one of
1356 1357 1358 1359
  the forms:
    
     - oe $cmp$ (SELECT MAX(...) )  // handled by Item_singlerow_subselect
     - oe $cmp$ <max>(SELECT ...)   // handled by Item_maxmin_subselect
1360

1361 1362 1363 1364 1365 1366 1367 1368 1369
  If that fails, check if the subquery is a single select without tables,
  and substitute the subquery predicate with "oe $cmp$ ie".
   
  If that fails, 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
1370 1371
  @retval false  The subquery was transformed
  @retval true   Error
1372
*/
1373

unknown's avatar
unknown committed
1374
bool
1375
Item_in_subselect::single_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1376
{
1377
  SELECT_LEX *select_lex= join->select_lex;
1378
  DBUG_ENTER("Item_in_subselect::single_value_transformer");
unknown's avatar
unknown committed
1379

1380 1381 1382 1383
  /*
    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 * ...)
  */
1384
  // psergey: duplicated_subselect_card_check
1385 1386 1387
  if (select_lex->item_list.elements > 1)
  {
    my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
1388
    DBUG_RETURN(true);
1389 1390
  }

1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401
  /*
    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.
  */
1402
  if ((abort_on_null || (upper_item && upper_item->top_level())) &&
1403
      !select_lex->master_unit()->uncacheable && !func->eqne_op())
1404
  {
1405 1406
    if (substitution)
    {
1407
      /* It is second (third, ...) SELECT of UNION => All is done */
unknown's avatar
unknown committed
1408
      DBUG_RETURN(false);
1409 1410
    }

1411 1412
    Item *subs;
    if (!select_lex->group_list.elements &&
unknown's avatar
unknown committed
1413
        !select_lex->having &&
1414
	!select_lex->with_sum_func &&
1415 1416
	!(select_lex->next_select()) &&
        select_lex->table_list.elements)
1417
    {
1418
      Item_sum_hybrid *item;
unknown's avatar
unknown committed
1419
      nesting_map save_allow_sum_func;
unknown's avatar
unknown committed
1420
      if (func->l_op())
1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435
      {
	/*
	  (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);
      }
1436 1437
      if (upper_item)
        upper_item->set_sum_test(item);
1438
      *select_lex->ref_pointer_array= item;
1439 1440 1441 1442 1443
      {
	List_iterator<Item> it(select_lex->item_list);
	it++;
	it.replace(item);
      }
unknown's avatar
merge  
unknown committed
1444

unknown's avatar
unknown committed
1445 1446
      save_allow_sum_func= thd->lex->allow_sum_func;
      thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
1447 1448
      /*
	Item_sum_(max|min) can't substitute other item => we can use 0 as
unknown's avatar
unknown committed
1449 1450
        reference, also Item_sum_(max|min) can't be fixed after creation, so
        we do not check item->fixed
1451
      */
1452
      if (item->fix_fields(thd, 0))
unknown's avatar
unknown committed
1453
	DBUG_RETURN(true);
unknown's avatar
unknown committed
1454
      thd->lex->allow_sum_func= save_allow_sum_func; 
1455
      /* we added aggregate function => we have to change statistic */
1456 1457
      count_field_types(select_lex, &join->tmp_table_param, join->all_fields, 
                        0);
unknown's avatar
unknown committed
1458

unknown's avatar
unknown committed
1459
      subs= new Item_singlerow_subselect(select_lex);
1460 1461 1462
    }
    else
    {
1463
      Item_maxmin_subselect *item;
unknown's avatar
unknown committed
1464
      subs= item= new Item_maxmin_subselect(thd, this, select_lex, func->l_op());
1465 1466
      if (upper_item)
        upper_item->set_sub_test(item);
1467
    }
1468
    /* fix fields is already called for  left expression */
unknown's avatar
unknown committed
1469
    substitution= func->create(left_expr, subs);
unknown's avatar
unknown committed
1470
    DBUG_RETURN(false);
1471 1472
  }

1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495
  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
1496
    DBUG_RETURN(false);
1497 1498
  }

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

1509
    SELECT_LEX *current= thd->lex->current_select;
unknown's avatar
unknown committed
1510

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

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

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

unknown's avatar
unknown committed
1532 1533 1534 1535 1536 1537 1538 1539 1540
    /*
      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;
1541
  }
1542

unknown's avatar
unknown committed
1543
  DBUG_RETURN(false);
1544
}
1545

1546

1547 1548 1549 1550 1551 1552 1553 1554 1555 1556
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;
1557 1558 1559 1560
}


/**
1561 1562
  Create the predicates needed to transform a single-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1563

1564 1565 1566
  @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
1567

1568 1569
  @details
  The correlated predicates are created as follows:
1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583

  - 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:
        
1584
      SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
1585 1586 1587

    = If we need to distinguish between those:

1588
      SELECT ie FROM ...
1589 1590 1591
        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
        HAVING trigcond(<is_not_null_test>(ie))

unknown's avatar
unknown committed
1592 1593
  @retval false If the new conditions were created successfully
  @retval true  Error
1594 1595
*/

unknown's avatar
unknown committed
1596
bool
1597 1598 1599
Item_in_subselect::create_single_in_to_exists_cond(JOIN * join,
                                                   Item **where_item,
                                                   Item **having_item)
1600 1601
{
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
1602
  /*
1603 1604
    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
1605
  */
1606
  Item* join_having= join->having ? join->having : join->tmp_having;
1607

1608
  DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
1609

1610 1611
  *where_item= NULL;
  *having_item= NULL;
1612

1613
  if (join_having || select_lex->with_sum_func ||
1614 1615
      select_lex->group_list.elements)
  {
unknown's avatar
unknown committed
1616
    Item *item= func->create(expr,
1617 1618
                             new Item_ref_null_helper(&select_lex->context,
                                                      this,
unknown's avatar
unknown committed
1619 1620 1621 1622
                                                      select_lex->
                                                      ref_pointer_array,
                                                      (char *)"<ref>",
                                                      this->full_name()));
1623
    if (!abort_on_null && left_expr->maybe_null)
1624 1625 1626
    {
      /* 
        We can encounter "NULL IN (SELECT ...)". Wrap the added condition
1627
        within a trig_cond.
1628
      */
1629
      item= new Item_func_trig_cond(item, get_cond_guard(0));
1630
    }
1631

1632 1633 1634
    if (!join_having)
      item->name= (char*) in_having_cond;
    if (fix_having(item, select_lex))
unknown's avatar
unknown committed
1635
      DBUG_RETURN(true);
1636
    *having_item= item;
1637 1638 1639
  }
  else
  {
unknown's avatar
unknown committed
1640 1641
    Item *item= (Item*) select_lex->item_list.head();

1642
    if (select_lex->table_list.elements)
1643
    {
1644 1645
      Item *having= item;
      Item *orig_item= item;
1646
       
unknown's avatar
unknown committed
1647
      item= func->create(expr, item);
1648
      if (!abort_on_null && orig_item->maybe_null)
unknown's avatar
unknown committed
1649
      {
1650 1651 1652 1653
	having= new Item_is_not_null_test(this, having);
        if (left_expr->maybe_null)
        {
          if (!(having= new Item_func_trig_cond(having,
1654
                                                get_cond_guard(0))))
unknown's avatar
unknown committed
1655
            DBUG_RETURN(true);
1656
        }
1657 1658
        having->name= (char*) in_having_cond;
        if (fix_having(having, select_lex))
unknown's avatar
unknown committed
1659
          DBUG_RETURN(true);
1660
        *having_item= having;
1661

1662
	item= new Item_cond_or(item,
1663
			       new Item_func_isnull(orig_item));
1664
      }
1665
      /* 
1666 1667
        If we may encounter NULL IN (SELECT ...) and care whether subquery
        result is NULL or FALSE, wrap condition in a trig_cond.
1668 1669 1670
      */
      if (!abort_on_null && left_expr->maybe_null)
      {
1671
        if (!(item= new Item_func_trig_cond(item, get_cond_guard(0))))
unknown's avatar
unknown committed
1672
          DBUG_RETURN(true);
1673
      }
1674

1675 1676 1677 1678 1679
      /*
        TODO: figure out why the following is done here in 
        single_value_transformer but there is no corresponding action in
        row_value_transformer?
      */
1680 1681
      item->name= (char *) in_additional_cond;
      if (!item->fixed && item->fix_fields(thd, 0))
unknown's avatar
unknown committed
1682
        DBUG_RETURN(true);
1683
      *where_item= item;
1684 1685 1686
    }
    else
    {
1687
      if (select_lex->master_unit()->is_union())
1688
      {
1689 1690
        Item *new_having=
          func->create(expr,
1691
                       new Item_ref_null_helper(&select_lex->context, this,
1692 1693 1694
                                            select_lex->ref_pointer_array,
                                            (char *)"<no matter>",
                                            (char *)"<result>"));
1695 1696 1697
        if (!abort_on_null && left_expr->maybe_null)
        {
          if (!(new_having= new Item_func_trig_cond(new_having,
1698
                                                    get_cond_guard(0))))
unknown's avatar
unknown committed
1699
            DBUG_RETURN(true);
1700
        }
1701

1702 1703
        new_having->name= (char*) in_having_cond;
        if (fix_having(new_having, select_lex))
unknown's avatar
unknown committed
1704
          DBUG_RETURN(true);
1705
        *having_item= new_having;
1706 1707
      }
      else
1708
        DBUG_ASSERT(FALSE);
1709
    }
unknown's avatar
unknown committed
1710
  }
unknown's avatar
unknown committed
1711

unknown's avatar
unknown committed
1712
  DBUG_RETURN(false);
unknown's avatar
unknown committed
1713
}
unknown's avatar
unknown committed
1714

1715

1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727
/**
  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
1728 1729
  @retval false  The subquery was transformed
  @retval true   Error
1730 1731
*/

unknown's avatar
unknown committed
1732
bool
unknown's avatar
unknown committed
1733
Item_in_subselect::row_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1734
{
unknown's avatar
unknown committed
1735
  SELECT_LEX *select_lex= join->select_lex;
1736
  uint cols_num= left_expr->cols();
1737

unknown's avatar
unknown committed
1738
  DBUG_ENTER("Item_in_subselect::row_value_transformer");
unknown's avatar
unknown committed
1739

1740
  // psergey: duplicated_subselect_card_check
1741
  if (select_lex->item_list.elements != cols_num)
1742
  {
1743
    my_error(ER_OPERAND_COLUMNS, MYF(0), cols_num);
unknown's avatar
unknown committed
1744
    DBUG_RETURN(true);
1745 1746
  }

1747 1748 1749 1750
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1751
  if (!substitution)
unknown's avatar
unknown committed
1752
  {
1753
    //first call for this unit
1754
    SELECT_LEX_UNIT *master_unit= select_lex->master_unit();
1755
    substitution= optimizer;
1756

1757 1758
    SELECT_LEX *current= thd->lex->current_select;
    thd->lex->current_select= current->return_after_parsing();
1759
    //optimizer never use Item **ref => we can pass 0 as parameter
1760
    if (!optimizer || optimizer->fix_left(thd, 0))
1761
    {
unknown's avatar
unknown committed
1762
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1763
      DBUG_RETURN(true);
1764
    }
1765

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

unknown's avatar
unknown committed
1769
    thd->lex->current_select= current;
unknown's avatar
unknown committed
1770 1771 1772 1773 1774 1775 1776 1777 1778
    /*
      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;
1779 1780
  }

unknown's avatar
unknown committed
1781
  DBUG_RETURN(false);
1782 1783 1784 1785
}


/**
1786 1787
  Create the predicates needed to transform a multi-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1788

1789
  @details
unknown's avatar
unknown committed
1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801 1802 1803 1804 1805 1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824
  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)
1825 1826 1827 1828 1829

  @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
1830 1831
  @retval false  If the new conditions were created successfully
  @retval true   Error
1832 1833
*/

unknown's avatar
unknown committed
1834
bool
1835 1836 1837
Item_in_subselect::create_row_in_to_exists_cond(JOIN * join,
                                                Item **where_item,
                                                Item **having_item)
1838 1839 1840
{
  SELECT_LEX *select_lex= join->select_lex;
  uint cols_num= left_expr->cols();
1841
  /*
1842 1843
    The non-transformed HAVING clause of 'join' may be stored in two ways
    during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
1844 1845 1846
  */
  Item* join_having= join->having ? join->having : join->tmp_having;
  bool is_having_used= (join_having || select_lex->with_sum_func ||
1847 1848 1849
                        select_lex->group_list.first ||
                        !select_lex->table_list.elements);

1850
  DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
1851 1852 1853

  *where_item= NULL;
  *having_item= NULL;
1854

1855
  if (is_having_used)
unknown's avatar
unknown committed
1856
  {
unknown's avatar
unknown committed
1857
    /* TODO: say here explicitly if the order of AND parts matters or not. */
1858 1859
    Item *item_having_part2= 0;
    for (uint i= 0; i < cols_num; i++)
unknown's avatar
unknown committed
1860
    {
1861
      DBUG_ASSERT((left_expr->fixed &&
1862

1863
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
1864 1865 1866
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
1867
      if (select_lex->ref_pointer_array[i]->
1868
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
1869
        DBUG_RETURN(true);
1870 1871
      Item *item_eq=
        new Item_func_eq(new
unknown's avatar
unknown committed
1872 1873 1874 1875 1876
                         Item_ref(&select_lex->context,
                                  (*optimizer->get_cache())->
                                  addr(i),
                                  (char *)"<no matter>",
                                  (char *)in_left_expr_name),
1877
                         new
unknown's avatar
unknown committed
1878 1879 1880
                         Item_ref(&select_lex->context,
                                  select_lex->ref_pointer_array + i,
                                  (char *)"<no matter>",
unknown's avatar
unknown committed
1881
                                  (char *)"<list ref>"));
1882 1883
      Item *item_isnull=
        new Item_func_isnull(new
unknown's avatar
unknown committed
1884 1885 1886
                             Item_ref(&select_lex->context,
                                      select_lex->ref_pointer_array+i,
                                      (char *)"<no matter>",
unknown's avatar
unknown committed
1887
                                      (char *)"<list ref>"));
1888
      Item *col_item= new Item_cond_or(item_eq, item_isnull);
unknown's avatar
unknown committed
1889
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
1890 1891
      {
        if (!(col_item= new Item_func_trig_cond(col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
1892
          DBUG_RETURN(true);
1893
      }
1894 1895
      *having_item= and_items(*having_item, col_item);

1896 1897 1898 1899 1900 1901 1902
      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
1903
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
1904 1905 1906
      {
        if (!(item_nnull_test= 
              new Item_func_trig_cond(item_nnull_test, get_cond_guard(i))))
unknown's avatar
unknown committed
1907
          DBUG_RETURN(true);
1908 1909
      }
      item_having_part2= and_items(item_having_part2, item_nnull_test);
1910
      item_having_part2->top_level_item();
unknown's avatar
unknown committed
1911
    }
1912
    *having_item= and_items(*having_item, item_having_part2);
1913
  }
1914
  else
1915
  {
1916 1917 1918
    for (uint i= 0; i < cols_num; i++)
    {
      Item *item, *item_isnull;
1919
      DBUG_ASSERT((left_expr->fixed &&
1920
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
1921 1922 1923
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
1924
      if (select_lex->ref_pointer_array[i]->
1925
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
1926
        DBUG_RETURN(true);
1927 1928
      item=
        new Item_func_eq(new
unknown's avatar
unknown committed
1929 1930
                         Item_direct_ref(&select_lex->context,
                                         (*optimizer->get_cache())->
1931 1932 1933 1934
                                         addr(i),
                                         (char *)"<no matter>",
                                         (char *)in_left_expr_name),
                         new
unknown's avatar
unknown committed
1935 1936 1937 1938
                         Item_direct_ref(&select_lex->context,
                                         select_lex->
                                         ref_pointer_array+i,
                                         (char *)"<no matter>",
unknown's avatar
unknown committed
1939
                                         (char *)"<list ref>"));
1940 1941
      if (!abort_on_null)
      {
1942 1943 1944 1945 1946 1947 1948 1949 1950
        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>"));
        
        
1951 1952
        item_isnull= new
          Item_func_isnull(new
unknown's avatar
unknown committed
1953 1954 1955 1956
                           Item_direct_ref(&select_lex->context,
                                           select_lex->
                                           ref_pointer_array+i,
                                           (char *)"<no matter>",
unknown's avatar
unknown committed
1957
                                           (char *)"<list ref>"));
1958
        item= new Item_cond_or(item, item_isnull);
1959 1960 1961 1962
        /* 
          TODO: why we create the above for cases where the right part
                cant be NULL?
        */
unknown's avatar
unknown committed
1963
        if (left_expr->element_index(i)->maybe_null)
1964 1965
        {
          if (!(item= new Item_func_trig_cond(item, get_cond_guard(i))))
unknown's avatar
unknown committed
1966
            DBUG_RETURN(true);
1967 1968
          if (!(having_col_item= 
                  new Item_func_trig_cond(having_col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
1969
            DBUG_RETURN(true);
1970
        }
1971
        *having_item= and_items(*having_item, having_col_item);
1972
      }
1973
      *where_item= and_items(*where_item, item);
1974
    }
unknown's avatar
unknown committed
1975
  }
1976

1977
  if (*where_item)
1978
  {
1979
    if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
unknown's avatar
unknown committed
1980
      DBUG_RETURN(true);
1981
    (*where_item)->top_level_item();
1982
  }
unknown's avatar
unknown committed
1983

1984
  if (*having_item)
1985
  {
1986 1987 1988
    if (!join_having)
      (*having_item)->name= (char*) in_having_cond;
    if (fix_having(*having_item, select_lex))
unknown's avatar
unknown committed
1989
      DBUG_RETURN(true);
1990
    (*having_item)->top_level_item();
1991
  }
unknown's avatar
unknown committed
1992

unknown's avatar
unknown committed
1993
  DBUG_RETURN(false);
unknown's avatar
unknown committed
1994 1995
}

1996

unknown's avatar
unknown committed
1997
bool
unknown's avatar
unknown committed
1998
Item_in_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
1999
{
2000
  return select_in_like_transformer(join);
2001 2002 2003
}


unknown's avatar
unknown committed
2004
/**
2005 2006
  Create the predicates needed to transform an IN/ALL/ANY subselect into a
  correlated EXISTS via predicate injection.
2007

2008
  @param join_arg  Join object of the subquery.
2009

2010 2011 2012 2013
  @retval FALSE  ok
  @retval TRUE   error
*/

2014 2015
bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
{
unknown's avatar
unknown committed
2016
  bool res;
2017 2018 2019 2020

  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE ||
              engine->engine_type() == subselect_engine::UNION_ENGINE);
  /*
2021
    TODO: the call to init_cond_guards allocates and initializes an
2022 2023 2024
    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.
2025
    If the dependency is removed, the call can be moved to a later phase.
2026 2027
  */
  init_cond_guards();
unknown's avatar
unknown committed
2028 2029 2030
  /*
    The IN=>EXISTS transformation makes non-correlated subqueries correlated.
  */
2031 2032 2033 2034 2035 2036 2037 2038 2039
  join_arg->select_lex->uncacheable|= UNCACHEABLE_DEPENDENT;
  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));
unknown's avatar
unknown committed
2040
  return (res);
2041 2042 2043
}


2044 2045 2046 2047 2048 2049 2050 2051 2052 2053
/**
  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
*/

2054
bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
2055
{
2056 2057 2058
  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;
2059

2060 2061 2062 2063 2064 2065 2066
  DBUG_ENTER("Item_in_subselect::inject_in_to_exists_cond");

  if (where_item)
  {
    where_item= and_items(join_arg->conds, where_item);
    if (!where_item->fixed && where_item->fix_fields(thd, 0))
      DBUG_RETURN(true);
2067
    // TIMOUR TODO: call optimize_cond() for the new where clause
2068 2069 2070 2071
    thd->change_item_tree(&select_lex->where, where_item);
    select_lex->where->top_level_item();
    join_arg->conds= select_lex->where;
  }
2072

2073 2074 2075 2076 2077 2078
  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);
2079
    // TIMOUR TODO: call optimize_cond() for the new having clause
2080 2081 2082 2083
    thd->change_item_tree(&select_lex->having, having_item);
    select_lex->having->top_level_item();
    join_arg->having= select_lex->having;
  }
2084

2085
  DBUG_RETURN(false);
2086 2087 2088
}


unknown's avatar
unknown committed
2089
/**
unknown's avatar
unknown committed
2090
  Prepare IN/ALL/ANY/SOME subquery transformation and call the appropriate
unknown's avatar
unknown committed
2091
  transformation function.
2092

unknown's avatar
unknown committed
2093 2094
  @param join    JOIN object of transforming subquery

2095 2096
  @notes
  To decide which transformation procedure (scalar or row) applicable here
unknown's avatar
unknown committed
2097 2098
  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
2099 2100
  underlying transformation methods.

unknown's avatar
unknown committed
2101 2102
  @retval  false  OK
  @retval  true   Error
2103 2104
*/

unknown's avatar
unknown committed
2105
bool
2106
Item_in_subselect::select_in_like_transformer(JOIN *join)
2107
{
unknown's avatar
unknown committed
2108
  Query_arena *arena, backup;
2109
  SELECT_LEX *current= thd->lex->current_select;
2110
  const char *save_where= thd->where;
unknown's avatar
unknown committed
2111
  bool trans_res= true;
2112 2113 2114
  bool result;

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

unknown's avatar
unknown committed
2116 2117 2118 2119 2120 2121
  /*
    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())
2122
  {
unknown's avatar
unknown committed
2123
    if (sl->join)
2124
    {
unknown's avatar
unknown committed
2125 2126
      sl->join->order= 0;
      sl->join->skip_sort_order= 1;
2127 2128 2129
    }
  }

2130
  if (changed)
unknown's avatar
unknown committed
2131
    DBUG_RETURN(false);
2132 2133 2134 2135 2136 2137 2138

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

2140
    //psergey: he means degenerate cases like "... IN (SELECT 1)"
2141 2142 2143
  */
  if (!optimizer)
  {
unknown's avatar
unknown committed
2144
    arena= thd->activate_stmt_arena_if_needed(&backup);
2145 2146
    result= (!(optimizer= new Item_in_optimizer(left_expr, this)));
    if (arena)
unknown's avatar
unknown committed
2147
      thd->restore_active_arena(arena, &backup);
2148 2149 2150 2151
    if (result)
      goto err;
  }

2152
  thd->lex->current_select= current->return_after_parsing();
2153
  result= (!left_expr->fixed &&
2154
           left_expr->fix_fields(thd, optimizer->arguments()));
2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168
  /* 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)
  */
2169
  arena= thd->activate_stmt_arena_if_needed(&backup);
unknown's avatar
unknown committed
2170
  if (left_expr->cols() == 1)
unknown's avatar
unknown committed
2171
    trans_res= single_value_transformer(join);
2172 2173 2174 2175 2176
  else
  {
    /* we do not support row operation for ALL/ANY/SOME */
    if (func != &eq_creator)
    {
unknown's avatar
unknown committed
2177
      if (arena)
unknown's avatar
unknown committed
2178
        thd->restore_active_arena(arena, &backup);
2179
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
2180
      DBUG_RETURN(true);
2181
    }
unknown's avatar
unknown committed
2182
    trans_res= row_value_transformer(join);
2183 2184
  }
  if (arena)
unknown's avatar
unknown committed
2185
    thd->restore_active_arena(arena, &backup);
2186 2187
err:
  thd->where= save_where;
unknown's avatar
unknown committed
2188
  DBUG_RETURN(trans_res);
unknown's avatar
unknown committed
2189 2190
}

2191

2192
void Item_in_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2193
{
2194
  if (in_strategy & SUBS_IN_TO_EXISTS)
2195
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2196 2197
  else
  {
2198
    left_expr->print(str, query_type);
2199
    str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
2200
  }
2201
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2202 2203 2204
}


2205
bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
2206
{
2207 2208
  uint outer_cols_num;
  List<Item> *inner_cols;
2209

2210
  if (in_strategy & SUBS_SEMI_JOIN)
2211 2212
    return !( (*ref)= new Item_int(1));

2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257
  /*
    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
2258
  if ((thd_arg->lex->context_analysis_only & CONTEXT_ANALYSIS_ONLY_VIEW) &&
Michael Widenius's avatar
Michael Widenius committed
2259
      left_expr && !left_expr->fixed &&
2260 2261 2262 2263 2264 2265 2266
      left_expr->fix_fields(thd_arg, &left_expr))
    return TRUE;
  if (Item_subselect::fix_fields(thd_arg, ref))
    return TRUE;

  fixed= TRUE;
  return FALSE;
2267 2268
}

2269

2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281
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();
}
2282

2283

2284
/**
2285 2286
  Try to create and initialize an engine to compute a subselect via
  materialization.
2287 2288

  @details
2289 2290 2291 2292 2293
  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,
2294 2295 2296 2297 2298 2299

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

2300
bool Item_in_subselect::setup_mat_engine()
2301
{
2302 2303
  subselect_hash_sj_engine       *mat_engine= NULL;
  subselect_single_select_engine *select_engine;
2304

2305
  DBUG_ENTER("Item_in_subselect::setup_mat_engine");
2306

2307 2308 2309 2310 2311 2312 2313
  /*
    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;
2314

2315 2316 2317
  /* Create/initialize execution objects. */
  if (!(mat_engine= new subselect_hash_sj_engine(thd, this, select_engine)))
    DBUG_RETURN(TRUE);
2318

2319
  if (mat_engine->init(&select_engine->join->fields_list))
2320
    DBUG_RETURN(TRUE);
2321

2322 2323
  engine= mat_engine;
  DBUG_RETURN(FALSE);
2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357
}


/**
  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.
  */ 
  if (!outer_join || !outer_join->tables || !outer_join->tables_list)
    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),
2358
                                                 FALSE);
2359 2360 2361 2362 2363 2364 2365
    if (!cur_item_cache || left_expr_cache->push_front(cur_item_cache))
      return TRUE;
  }
  return FALSE;
}


2366
bool Item_in_subselect::init_cond_guards()
2367
{
2368 2369 2370 2371 2372 2373 2374 2375 2376
  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;
2377 2378 2379
}


unknown's avatar
unknown committed
2380
bool
unknown's avatar
unknown committed
2381
Item_allany_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2382
{
2383
  DBUG_ENTER("Item_allany_subselect::select_transformer");
2384
  in_strategy= SUBS_IN_TO_EXISTS;
2385 2386
  if (upper_item)
    upper_item->show= 1;
2387
  DBUG_RETURN(select_in_like_transformer(join));
unknown's avatar
unknown committed
2388 2389
}

unknown's avatar
unknown committed
2390

2391
void Item_allany_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2392
{
2393
  if (in_strategy & SUBS_IN_TO_EXISTS)
2394
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2395 2396
  else
  {
2397
    left_expr->print(str, query_type);
unknown's avatar
unknown committed
2398
    str->append(' ');
unknown's avatar
unknown committed
2399 2400
    str->append(func->symbol(all));
    str->append(all ? " all " : " any ", 5);
unknown's avatar
unknown committed
2401
  }
2402
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2403 2404 2405
}


2406 2407 2408 2409 2410 2411 2412 2413
void subselect_engine::set_thd(THD *thd_arg)
{
  thd= thd_arg;
  if (result)
    result->set_thd(thd_arg);
}


2414
subselect_single_select_engine::
unknown's avatar
unknown committed
2415
subselect_single_select_engine(THD *thd_arg, st_select_lex *select,
2416
			       select_result_interceptor *result_arg,
2417
			       Item_subselect *item_arg)
unknown's avatar
unknown committed
2418
  :subselect_engine(thd_arg, item_arg, result_arg),
2419
   prepared(0), executed(0), select_lex(select), join(0)
unknown's avatar
unknown committed
2420
{
2421
  select_lex->master_unit()->item= item_arg;
unknown's avatar
unknown committed
2422 2423
}

2424 2425 2426 2427
int subselect_single_select_engine::get_identifier()
{
  return select_lex->select_number; 
}
unknown's avatar
unknown committed
2428

unknown's avatar
unknown committed
2429 2430
void subselect_single_select_engine::cleanup()
{
unknown's avatar
unknown committed
2431
  DBUG_ENTER("subselect_single_select_engine::cleanup");
2432
  prepared= executed= 0;
2433
  join= 0;
2434
  result->cleanup();
unknown's avatar
unknown committed
2435
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2436
}
2437

unknown's avatar
unknown committed
2438 2439 2440 2441 2442

void subselect_union_engine::cleanup()
{
  DBUG_ENTER("subselect_union_engine::cleanup");
  unit->reinit_exec_mechanism();
2443
  result->cleanup();
unknown's avatar
unknown committed
2444
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2445
}
2446

unknown's avatar
unknown committed
2447

2448 2449 2450 2451 2452 2453
bool subselect_union_engine::is_executed() const
{
  return unit->executed;
}


2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474
/*
  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);
}

2475

unknown's avatar
unknown committed
2476 2477 2478
void subselect_uniquesubquery_engine::cleanup()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
2479 2480 2481
  /* 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
2482 2483 2484 2485
  DBUG_VOID_RETURN;
}


unknown's avatar
unknown committed
2486
subselect_union_engine::subselect_union_engine(THD *thd_arg, st_select_lex_unit *u,
2487
					       select_result_interceptor *result_arg,
2488
					       Item_subselect *item_arg)
unknown's avatar
unknown committed
2489
  :subselect_engine(thd_arg, item_arg, result_arg)
unknown's avatar
unknown committed
2490 2491
{
  unit= u;
2492
  if (!result_arg)				//out of memory
2493
    current_thd->fatal_error();
2494
  unit->item= item_arg;
unknown's avatar
unknown committed
2495 2496
}

2497

2498 2499 2500 2501
/**
  Create and prepare the JOIN object that represents the query execution
  plan for the subquery.

2502
  @details
2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 2523
  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
2524 2525
int subselect_single_select_engine::prepare()
{
unknown's avatar
unknown committed
2526 2527
  if (prepared)
    return 0;
2528 2529 2530 2531
  if (select_lex->join)
  {
    select_lex->cleanup();
  }
2532 2533
  join= new JOIN(thd, select_lex->item_list,
		 select_lex->options | SELECT_NO_UNLOCK, result);
2534 2535
  if (!join || !result)
  {
2536
    thd->fatal_error();				//out of memory
2537 2538
    return 1;
  }
unknown's avatar
unknown committed
2539
  prepared= 1;
2540 2541
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
unknown's avatar
unknown committed
2542
  if (join->prepare(&select_lex->ref_pointer_array,
2543
		    select_lex->table_list.first,
unknown's avatar
unknown committed
2544
		    select_lex->with_wild,
unknown's avatar
unknown committed
2545
		    select_lex->where,
unknown's avatar
unknown committed
2546 2547
		    select_lex->order_list.elements +
		    select_lex->group_list.elements,
2548 2549
		    select_lex->order_list.first,
		    select_lex->group_list.first,
unknown's avatar
unknown committed
2550
		    select_lex->having,
2551
		    NULL, select_lex,
2552
		    select_lex->master_unit()))
unknown's avatar
unknown committed
2553
    return 1;
2554
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2555 2556 2557 2558 2559
  return 0;
}

int subselect_union_engine::prepare()
{
2560
  return unit->prepare(thd, result, SELECT_NO_UNLOCK);
unknown's avatar
unknown committed
2561 2562
}

2563
int subselect_uniquesubquery_engine::prepare()
2564
{
2565 2566
  /* Should never be called. */
  DBUG_ASSERT(FALSE);
2567 2568 2569
  return 1;
}

2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588 2589 2590 2591

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


2592 2593 2594 2595 2596
/* 
 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)
2597
{
2598
  Item *sel_item;
2599
  List_iterator_fast<Item> li(item_list);
2600
  res_type= STRING_RESULT;
2601
  res_field_type= MYSQL_TYPE_VAR_STRING;
2602 2603 2604 2605
  for (uint i= 0; (sel_item= li++); i++)
  {
    item->max_length= sel_item->max_length;
    res_type= sel_item->result_type();
2606
    res_field_type= sel_item->field_type();
2607
    item->decimals= sel_item->decimals;
2608
    item->unsigned_flag= sel_item->unsigned_flag;
unknown's avatar
unknown committed
2609
    maybe_null= sel_item->maybe_null;
2610
    if (!(row[i]= Item_cache::get_cache(sel_item)))
2611
      return;
2612
    row[i]->setup(sel_item);
2613
 //psergey-backport-timours:   row[i]->store(sel_item);
2614
  }
2615
  if (item_list.elements > 1)
2616
    res_type= ROW_RESULT;
2617 2618
}

2619
void subselect_single_select_engine::fix_length_and_dec(Item_cache **row)
2620
{
2621
  DBUG_ASSERT(row || select_lex->item_list.elements==1);
2622
  set_row(select_lex->item_list, row);
2623
  item->collation.set(row[0]->collation);
unknown's avatar
unknown committed
2624 2625
  if (cols() != 1)
    maybe_null= 0;
2626 2627 2628 2629 2630 2631 2632
}

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)
2633
  {
2634
    set_row(unit->types, row);
2635 2636
    item->collation.set(row[0]->collation);
  }
2637 2638
  else
  {
2639 2640 2641
    bool maybe_null_saved= maybe_null;
    set_row(unit->types, row);
    maybe_null= maybe_null_saved;
2642 2643
  }
}
unknown's avatar
unknown committed
2644

2645
void subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
2646 2647 2648 2649 2650
{
  //this never should be called
  DBUG_ASSERT(0);
}

2651 2652 2653 2654
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);

2655
int subselect_single_select_engine::exec()
unknown's avatar
unknown committed
2656 2657
{
  DBUG_ENTER("subselect_single_select_engine::exec");
unknown's avatar
unknown committed
2658 2659 2660
  char const *save_where= thd->where;
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
2661
  if (!join->optimized)
unknown's avatar
unknown committed
2662
  {
2663 2664 2665
    SELECT_LEX_UNIT *unit= select_lex->master_unit();

    unit->set_limit(unit->global_parameters);
unknown's avatar
unknown committed
2666 2667
    if (join->optimize())
    {
unknown's avatar
unknown committed
2668
      thd->where= save_where;
unknown's avatar
unknown committed
2669
      executed= 1;
unknown's avatar
unknown committed
2670
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2671
      DBUG_RETURN(join->error ? join->error : 1);
unknown's avatar
unknown committed
2672
    }
unknown's avatar
unknown committed
2673
    if (!select_lex->uncacheable && thd->lex->describe && 
2674
        !(join->select_options & SELECT_DESCRIBE))
unknown's avatar
unknown committed
2675
    {
2676 2677 2678
      item->update_used_tables();
      if (item->const_item())
      {
2679 2680 2681 2682 2683 2684 2685 2686
        /*
          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;
2687 2688 2689 2690 2691 2692
        /*
          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.
        */
2693
        if (join->need_tmp && join->init_save_join_tab())
2694 2695
          DBUG_RETURN(1);                        /* purecov: inspected */
      }
unknown's avatar
unknown committed
2696
    }
2697 2698 2699 2700
    if (item->engine_changed)
    {
      DBUG_RETURN(1);
    }
unknown's avatar
unknown committed
2701
  }
2702 2703 2704
  if (select_lex->uncacheable &&
      select_lex->uncacheable != UNCACHEABLE_EXPLAIN
      && executed)
unknown's avatar
unknown committed
2705 2706
  {
    if (join->reinit())
2707
    {
unknown's avatar
unknown committed
2708 2709
      thd->where= save_where;
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2710
      DBUG_RETURN(1);
2711
    }
2712
    item->reset();
unknown's avatar
unknown committed
2713 2714 2715 2716
    item->assigned((executed= 0));
  }
  if (!executed)
  {
2717
    item->reset_value_registration();
2718 2719 2720
    JOIN_TAB *changed_tabs[MAX_TABLES];
    JOIN_TAB **last_changed_tab= changed_tabs;
    if (item->have_guarded_conds())
2721 2722
    {
      /*
2723
        For at least one of the pushed predicates the following is true:
2724 2725 2726 2727 2728 2729 2730
        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.
      */
      for (uint i=join->const_tables ; i < join->tables ; i++)
      {
        JOIN_TAB *tab=join->join_tab+i;
2731
        if (tab && tab->keyuse)
2732
        {
2733 2734 2735 2736 2737 2738
          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 */
2739 2740
              tab->save_read_first_record= tab->read_first_record;
              tab->save_read_record= tab->read_record.read_record;
2741 2742 2743 2744
              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;
2745
              tab->read_record.unlock_row= rr_unlock_row;
2746 2747 2748 2749
              *(last_changed_tab++)= tab;
              break;
            }
          }
2750 2751 2752 2753
        }
      }
    }
    
unknown's avatar
unknown committed
2754
    join->exec();
2755

2756 2757
    /* Enable the optimizations back */
    for (JOIN_TAB **ptab= changed_tabs; ptab != last_changed_tab; ptab++)
2758
    {
2759 2760 2761
      JOIN_TAB *tab= *ptab;
      tab->read_record.record= 0;
      tab->read_record.ref_length= 0;
2762 2763
      tab->read_first_record= tab->save_read_first_record; 
      tab->read_record.read_record= tab->save_read_record;
2764
    }
unknown's avatar
unknown committed
2765
    executed= 1;
unknown's avatar
unknown committed
2766 2767
    thd->where= save_where;
    thd->lex->current_select= save_select;
2768
    DBUG_RETURN(join->error||thd->is_fatal_error);
unknown's avatar
unknown committed
2769
  }
unknown's avatar
unknown committed
2770 2771
  thd->where= save_where;
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2772 2773 2774
  DBUG_RETURN(0);
}

2775
int subselect_union_engine::exec()
unknown's avatar
unknown committed
2776
{
unknown's avatar
unknown committed
2777
  char const *save_where= thd->where;
2778
  int res= unit->exec();
unknown's avatar
unknown committed
2779
  thd->where= save_where;
2780
  return res;
unknown's avatar
unknown committed
2781 2782
}

2783

2784
/*
2785
  Search for at least one row satisfying select condition
2786 2787 2788 2789 2790 2791 2792 2793
 
  SYNOPSIS
    subselect_uniquesubquery_engine::scan_table()

  DESCRIPTION
    Scan the table using sequential access until we find at least one row
    satisfying select condition.
    
2794 2795
    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.
2796 2797 2798 2799 2800 2801 2802

  RETURN
    FALSE - OK
    TRUE  - Error
*/

int subselect_uniquesubquery_engine::scan_table()
2803 2804 2805
{
  int error;
  TABLE *table= tab->table;
2806 2807 2808 2809 2810
  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");

  if (table->file->inited)
    table->file->ha_index_end();
 
2811 2812
  if (table->file->ha_rnd_init_with_error(1))
    DBUG_RETURN(1);
2813 2814 2815 2816
  table->file->extra_opt(HA_EXTRA_CACHE,
                         current_thd->variables.read_buff_size);
  table->null_row= 0;
  for (;;)
2817
  {
2818
    error=table->file->ha_rnd_next(table->record[0]);
2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834
    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;
      }
2835 2836 2837 2838 2839 2840 2841 2842 2843 2844 2845 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856
    }

    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
2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881
    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.

2882 2883

  RETURN
unknown's avatar
unknown committed
2884 2885 2886 2887 2888
    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.
2889 2890 2891 2892 2893 2894 2895
*/

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++)
2896
  {
2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907
    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
2908 2909 2910 2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923 2924 2925 2926 2927 2928 2929 2930 2931
    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)
2932
    {
unknown's avatar
unknown committed
2933 2934 2935 2936
      /*
       Error converting the left IN operand to the column type of the right
       IN operand. 
      */
2937
      tab->table->status= STATUS_NOT_FOUND;
unknown's avatar
unknown committed
2938
      break;
2939
    }
2940
  }
2941 2942 2943
  DBUG_RETURN(0);
}

2944

2945 2946 2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 2992 2993 2994
/*
  @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;
}


2995 2996 2997 2998 2999
/*
  Execute subselect

  SYNOPSIS
    subselect_uniquesubquery_engine::exec()
3000

3001 3002 3003 3004 3005 3006 3007 3008 3009 3010
  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)
3011
    the caller doesn't distinguish between NULL and FALSE result and we just
3012
    return FALSE. 
3013 3014 3015 3016 3017
    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.
3018 3019 3020 3021 3022 3023
  NOTE
    
  RETURN
    FALSE - ok
    TRUE  - an error occured while scanning
*/
3024

3025
int subselect_uniquesubquery_engine::exec()
3026 3027 3028 3029
{
  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
  int error;
  TABLE *table= tab->table;
3030
  empty_result_set= TRUE;
unknown's avatar
unknown committed
3031
  table->status= 0;
3032 3033 3034
 
  /* TODO: change to use of 'full_scan' here? */
  if (copy_ref_key())
3035 3036 3037 3038 3039
  {
    /*
      TIMOUR: copy_ref_key() == 1 means NULL result, not error, why return 1?
      Check who reiles on this result.
    */
3040
    DBUG_RETURN(1);
3041
  }
unknown's avatar
unknown committed
3042 3043 3044 3045 3046 3047 3048 3049 3050
  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);
  }
3051 3052 3053 3054

  if (null_keypart)
    DBUG_RETURN(scan_table());
 
3055
  if (!table->file->inited)
3056
    table->file->ha_index_init(tab->ref.key, 0);
3057 3058 3059 3060 3061
  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);
3062 3063
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3064
    error= report_error(table, error);
3065 3066
  else
  {
3067 3068
    error= 0;
    table->null_row= 0;
3069 3070 3071 3072 3073 3074 3075
    if (!table->status && (!cond || cond->val_int()))
    {
      ((Item_in_subselect *) item)->value= 1;
      empty_result_set= FALSE;
    }
    else
      ((Item_in_subselect *) item)->value= 0;
3076
  }
3077

3078
  DBUG_RETURN(error != 0);
3079 3080
}

3081

3082
/*
3083
  TIMOUR: write comment
3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099
*/

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));
3100 3101

  if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3102
  {
3103 3104 3105 3106 3107 3108
    /*
      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);
3109 3110
  }

3111 3112 3113 3114 3115 3116 3117
  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);
3118 3119 3120 3121
}



3122
subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
3123
{
3124
  /* Tell handler we don't need the index anymore */
3125 3126
  //psergey-merge-todo: the following was gone in 6.0:
 //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
3127 3128
}

3129

3130 3131 3132 3133
/*
  Index-lookup subselect 'engine' - run the subquery

  SYNOPSIS
3134
    subselect_indexsubquery_engine:exec()
3135 3136 3137
      full_scan 

  DESCRIPTION
3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170
    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.
3171

3172 3173 3174 3175
    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.
3176 3177 3178 3179 3180 3181

  RETURN
    0
    1
*/

3182
int subselect_indexsubquery_engine::exec()
3183
{
3184
  DBUG_ENTER("subselect_indexsubquery_engine::exec");
3185
  int error;
3186
  bool null_finding= 0;
3187
  TABLE *table= tab->table;
3188

3189
  ((Item_in_subselect *) item)->value= 0;
3190 3191
  empty_result_set= TRUE;
  null_keypart= 0;
3192
  table->status= 0;
3193

3194 3195
  if (check_null)
  {
3196
    /* We need to check for NULL if there wasn't a matching value */
3197
    *tab->ref.null_ref_key= 0;			// Search first for not null
3198 3199 3200
    ((Item_in_subselect *) item)->was_null= 0;
  }

3201 3202 3203 3204
  /* Copy the ref key and check for nulls... */
  if (copy_ref_key())
    DBUG_RETURN(1);

3205 3206 3207 3208 3209 3210 3211 3212 3213 3214
  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);
  }

3215 3216
  if (null_keypart)
    DBUG_RETURN(scan_table());
3217 3218

  if (!table->file->inited)
3219
    table->file->ha_index_init(tab->ref.key, 1);
3220 3221 3222 3223 3224
  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);
3225 3226
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3227
    error= report_error(table, error);
3228 3229
  else
  {
3230
    for (;;)
3231
    {
3232 3233 3234
      error= 0;
      table->null_row= 0;
      if (!table->status)
3235
      {
3236
        if ((!cond || cond->val_int()) && (!having || having->val_int()))
3237
        {
3238
          empty_result_set= FALSE;
3239 3240 3241 3242 3243 3244
          if (null_finding)
            ((Item_in_subselect *) item)->was_null= 1;
          else
            ((Item_in_subselect *) item)->value= 1;
          break;
        }
3245 3246 3247
        error= table->file->ha_index_next_same(table->record[0],
                                               tab->ref.key_buff,
                                               tab->ref.key_length);
3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262
        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;
3263
      }
3264 3265
    }
  }
3266
  DBUG_RETURN(error != 0);
3267 3268
}

3269

unknown's avatar
unknown committed
3270 3271
uint subselect_single_select_engine::cols()
{
3272 3273 3274 3275
  //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
3276 3277
}

unknown's avatar
unknown committed
3278

unknown's avatar
unknown committed
3279 3280
uint subselect_union_engine::cols()
{
3281 3282
  DBUG_ASSERT(unit->is_prepared());  // should be called after fix_fields()
  return unit->types.elements;
unknown's avatar
unknown committed
3283 3284
}

unknown's avatar
unknown committed
3285

3286
uint8 subselect_single_select_engine::uncacheable()
3287 3288 3289 3290
{
  return select_lex->uncacheable;
}

unknown's avatar
unknown committed
3291

3292
uint8 subselect_union_engine::uncacheable()
3293 3294 3295 3296
{
  return unit->uncacheable;
}

unknown's avatar
unknown committed
3297

unknown's avatar
unknown committed
3298 3299 3300 3301 3302 3303 3304 3305 3306
void subselect_single_select_engine::exclude()
{
  select_lex->master_unit()->exclude_level();
}

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

unknown's avatar
unknown committed
3308

3309
void subselect_uniquesubquery_engine::exclude()
3310 3311 3312 3313
{
  //this never should be called
  DBUG_ASSERT(0);
}
3314 3315 3316 3317 3318


table_map subselect_engine::calc_const_tables(TABLE_LIST *table)
{
  table_map map= 0;
unknown's avatar
unknown committed
3319
  for (; table; table= table->next_leaf)
3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330
  {
    TABLE *tbl= table->table;
    if (tbl && tbl->const_table)
      map|= tbl->map;
  }
  return map;
}


table_map subselect_single_select_engine::upper_select_const_tables()
{
3331
  return calc_const_tables(select_lex->outer_select()->leaf_tables);
3332 3333
}

unknown's avatar
merge  
unknown committed
3334

3335 3336
table_map subselect_union_engine::upper_select_const_tables()
{
3337
  return calc_const_tables(unit->outer_select()->leaf_tables);
3338
}
unknown's avatar
merge  
unknown committed
3339 3340


3341 3342
void subselect_single_select_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3343
{
3344
  select_lex->print(thd, str, query_type);
unknown's avatar
unknown committed
3345 3346 3347
}


3348
void subselect_union_engine::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3349
{
3350
  unit->print(str, query_type);
unknown's avatar
unknown committed
3351 3352 3353
}


3354 3355
void subselect_uniquesubquery_engine::print(String *str,
                                            enum_query_type query_type)
unknown's avatar
unknown committed
3356
{
3357
  char *table_name= tab->table->s->table_name.str;
3358
  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
3359
  tab->ref.items[0]->print(str, query_type);
3360
  str->append(STRING_WITH_LEN(" in "));
3361 3362 3363 3364 3365 3366 3367 3368 3369 3370
  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
3371
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3372
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3373
  str->append(key_info->name);
unknown's avatar
unknown committed
3374 3375
  if (cond)
  {
3376
    str->append(STRING_WITH_LEN(" where "));
3377
    cond->print(str, query_type);
unknown's avatar
unknown committed
3378 3379 3380 3381
  }
  str->append(')');
}

3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404
/*
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
3405

3406 3407
void subselect_indexsubquery_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3408
{
3409
  str->append(STRING_WITH_LEN("<index_lookup>("));
3410
  tab->ref.items[0]->print(str, query_type);
3411
  str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
3412
  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
unknown's avatar
unknown committed
3413
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3414
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3415
  str->append(key_info->name);
unknown's avatar
unknown committed
3416
  if (check_null)
3417
    str->append(STRING_WITH_LEN(" checking NULL"));
3418
  if (cond)
unknown's avatar
unknown committed
3419
  {
3420
    str->append(STRING_WITH_LEN(" where "));
3421
    cond->print(str, query_type);
unknown's avatar
unknown committed
3422
  }
3423 3424 3425
  if (having)
  {
    str->append(STRING_WITH_LEN(" having "));
3426
    having->print(str, query_type);
3427
  }
unknown's avatar
unknown committed
3428 3429
  str->append(')');
}
3430

unknown's avatar
unknown committed
3431 3432
/**
  change select_result object of engine.
3433

unknown's avatar
unknown committed
3434 3435
  @param si		new subselect Item
  @param res		new select_result object
3436

unknown's avatar
unknown committed
3437
  @retval
unknown's avatar
unknown committed
3438
    FALSE OK
unknown's avatar
unknown committed
3439
  @retval
unknown's avatar
unknown committed
3440
    TRUE  error
3441 3442
*/

unknown's avatar
unknown committed
3443
bool subselect_single_select_engine::change_result(Item_subselect *si,
3444
                                                 select_result_interceptor *res)
3445 3446 3447 3448 3449 3450 3451
{
  item= si;
  result= res;
  return select_lex->join->change_result(result);
}


unknown's avatar
unknown committed
3452 3453
/**
  change select_result object of engine.
3454

unknown's avatar
unknown committed
3455 3456
  @param si		new subselect Item
  @param res		new select_result object
3457

unknown's avatar
unknown committed
3458
  @retval
unknown's avatar
unknown committed
3459
    FALSE OK
unknown's avatar
unknown committed
3460
  @retval
unknown's avatar
unknown committed
3461
    TRUE  error
3462 3463
*/

unknown's avatar
unknown committed
3464
bool subselect_union_engine::change_result(Item_subselect *si,
3465
                                           select_result_interceptor *res)
3466 3467 3468 3469 3470 3471 3472 3473
{
  item= si;
  int rc= unit->change_result(res, result);
  result= res;
  return rc;
}


unknown's avatar
unknown committed
3474 3475
/**
  change select_result emulation, never should be called.
3476

unknown's avatar
unknown committed
3477 3478
  @param si		new subselect Item
  @param res		new select_result object
3479

unknown's avatar
unknown committed
3480
  @retval
unknown's avatar
unknown committed
3481
    FALSE OK
unknown's avatar
unknown committed
3482
  @retval
unknown's avatar
unknown committed
3483
    TRUE  error
3484 3485
*/

unknown's avatar
unknown committed
3486
bool subselect_uniquesubquery_engine::change_result(Item_subselect *si,
3487
                                                    select_result_interceptor *res)
3488 3489
{
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
3490
  return TRUE;
3491
}
3492 3493


unknown's avatar
unknown committed
3494 3495
/**
  Report about presence of tables in subquery.
3496

unknown's avatar
unknown committed
3497
  @retval
3498
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3499
  @retval
3500 3501 3502 3503 3504 3505 3506 3507
    FALSE there are some tables in subquery
*/
bool subselect_single_select_engine::no_tables()
{
  return(select_lex->table_list.elements == 0);
}


3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523
/*
  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
3524 3525
/**
  Report about presence of tables in subquery.
3526

unknown's avatar
unknown committed
3527
  @retval
3528
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3529
  @retval
3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542
    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
3543 3544
/**
  Report about presence of tables in subquery.
3545

unknown's avatar
unknown committed
3546
  @retval
3547
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3548
  @retval
3549 3550 3551 3552 3553 3554
    FALSE there are some tables in subquery
*/

bool subselect_uniquesubquery_engine::no_tables()
{
  /* returning value is correct, but this method should never be called */
3555
  DBUG_ASSERT(FALSE);
3556 3557
  return 0;
}
3558 3559 3560 3561 3562 3563 3564


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


3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578
/**
  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.
3579 3580 3581 3582 3583 3584 3585 3586 3587

  @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
3588 3589
*/

3590 3591
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_schema()
3592 3593 3594 3595
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;

  if (item_in->is_top_level_item())
3596
    return COMPLETE_MATCH;
3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618
  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)
3619 3620
    return PARTIAL_MATCH;
  return COMPLETE_MATCH;
3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631
}


/**
  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.
3632 3633 3634

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

3637 3638
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_data()
3639 3640 3641 3642 3643 3644
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
  Item *outer_col;

3645 3646 3647 3648 3649 3650
  /*
    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;
3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673

  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)
3674 3675 3676
    return COMPLETE_MATCH;
  return PARTIAL_MATCH;
}
3677

3678 3679 3680 3681 3682 3683

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)
{
3684
  ulonglong pm_buff_size;
3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748

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

3749
ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
3750 3751 3752
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
3753 3754
  /* Total size of all buffers used by partial matching. */
  ulonglong buff_size;
3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785
  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;
3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808
}


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


3809 3810 3811 3812
/**
  Create all structures needed for IN execution that can live between PS
  reexecution.

3813 3814 3815
  @param tmp_columns the items that produce the data for the temp table

  @details
3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828
  - 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
*/

3829
bool subselect_hash_sj_engine::init(List<Item> *tmp_columns)
3830
{
3831
  select_union *result_sink;
3832 3833 3834
  /* Options to create_tmp_table. */
  ulonglong tmp_create_options= thd->options | TMP_TABLE_ALL_COLUMNS;
                             /* | TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM */
3835

3836
  DBUG_ENTER("subselect_hash_sj_engine::init");
3837

3838 3839 3840 3841 3842
  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);
3843 3844 3845 3846 3847 3848

  /*
    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.
  */
3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861
/*
  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))
3862
    DBUG_RETURN(TRUE);
3863 3864
  }
*/
3865
  if (!(result_sink= new select_materialize_with_stats))
3866
    DBUG_RETURN(TRUE);
3867 3868 3869 3870
  result_sink->get_tmp_table_param()->materialized_subquery= true;
  if (result_sink->create_result_table(thd, tmp_columns, TRUE,
                                       tmp_create_options,
                                       "materialized subselect", TRUE))
3871 3872
    DBUG_RETURN(TRUE);

3873 3874
  tmp_table= result_sink->table;
  result= result_sink;
3875 3876

  /*
3877 3878 3879 3880 3881 3882 3883
    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.
3884 3885 3886 3887 3888 3889 3890 3891
  */
  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);
3892
    tmp_table= NULL;
3893 3894 3895 3896 3897 3898 3899 3900 3901
    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.
  */
3902 3903 3904
  DBUG_ASSERT(tmp_table->s->keys == 1 &&
              ((Item_in_subselect *) item)->left_expr->cols() ==
              tmp_table->key_info->key_parts);
3905

3906 3907 3908
  if (make_semi_join_conds() ||
      /* A unique_engine is used both for complete and partial matching. */
      !(lookup_engine= make_unique_engine()))
3909
    DBUG_RETURN(TRUE);
3910

3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921
  /*
    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);

3922 3923
  DBUG_RETURN(FALSE);
}
3924 3925


3926 3927 3928
/*
  Create an artificial condition to post-filter those rows matched by index
  lookups that cannot be distinguished by the index lookup procedure.
3929

3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944
  @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()
{
3945 3946 3947 3948 3949
  /*
    Table reference for tmp_table that is used to resolve column references
    (Item_fields) to columns in tmp_table.
  */
  TABLE_LIST *tmp_table_ref;
3950 3951 3952 3953 3954 3955 3956 3957 3958 3959
  /* 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);

3960 3961 3962 3963 3964 3965
  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
    DBUG_RETURN(TRUE);

  tmp_table_ref->init_one_table("", "materialized subselect", TL_READ);
  tmp_table_ref->table= tmp_table;

3966
  context= new Name_resolution_context;
3967 3968 3969 3970
  context->init();
  context->first_name_resolution_table=
    context->last_name_resolution_table= tmp_table_ref;
  
3971
  for (uint i= 0; i < item_in->left_expr->cols(); i++)
3972 3973 3974 3975 3976
  {
    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;

3977 3978 3979 3980
    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)))
3981
    {
3982 3983
      delete semi_join_conds;
      semi_join_conds= NULL;
3984 3985 3986
      DBUG_RETURN(TRUE);
    }
  }
3987
  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
3988 3989 3990 3991 3992 3993 3994
    DBUG_RETURN(TRUE);

  DBUG_RETURN(FALSE);
}


/**
3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 4005 4006 4007 4008
  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
4009
  Item_iterator_row it(item_in->left_expr);
4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025
  /* 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
4026 4027
  tab->table= tmp_table;
  tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
4028 4029 4030 4031 4032 4033

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


4034 4035 4036 4037 4038 4039 4040
subselect_hash_sj_engine::~subselect_hash_sj_engine()
{
  delete lookup_engine;
  delete result;
  if (tmp_table)
    free_tmp_table(thd, tmp_table);
}
4041 4042


4043
int subselect_hash_sj_engine::prepare()
4044 4045 4046 4047 4048
{
  /*
    Create and optimize the JOIN that will be used to materialize
    the subquery if not yet created.
  */
4049
  return materialize_engine->prepare();
4050 4051 4052 4053 4054 4055
}


/**
  Cleanup performed after each PS execution.

4056
  @details
4057 4058 4059 4060 4061
  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
*/

void subselect_hash_sj_engine::cleanup()
{
4062
  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
4063
  is_materialized= FALSE;
4064 4065 4066 4067 4068
  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;
4069
  materialize_engine->cleanup();
4070 4071 4072 4073 4074 4075
  /*
    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;
4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091
  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. */
4092 4093 4094
  DBUG_ASSERT(tmp_table);
  free_tmp_table(thd, tmp_table);
  tmp_table= NULL;
4095 4096 4097 4098 4099 4100
}


/**
  Execute a subquery IN predicate via materialization.

4101
  @details
4102 4103 4104 4105 4106 4107 4108 4109 4110 4111
  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;
4112
  SELECT_LEX *save_select= thd->lex->current_select;
4113
  subselect_partial_match_engine *pm_engine= NULL;
4114
  int res= 0;
4115 4116 4117 4118 4119 4120 4121

  DBUG_ENTER("subselect_hash_sj_engine::exec");

  /*
    Optimize and materialize the subquery during the first execution of
    the subquery predicate.
  */
4122
  thd->lex->current_select= materialize_engine->select_lex;
4123 4124
  /* The subquery should be optimized, and materialized only once. */
  DBUG_ASSERT(materialize_join->optimized && !is_materialized);
4125 4126 4127
  materialize_join->exec();
  if ((res= test(materialize_join->error || thd->is_fatal_error)))
    goto err;
4128

4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148
  /*
    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. */
4149 4150
    item_in->reset();
    item_in->make_const();
4151 4152 4153 4154
    item_in->set_first_execution();
    DBUG_RETURN(FALSE);
  }

4155 4156 4157 4158 4159 4160 4161 4162 4163
  /*
    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();
4164 4165
  if (strategy == PARTIAL_MATCH)
  {
4166 4167 4168
    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;
4169 4170 4171 4172 4173 4174
    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;

4175 4176 4177 4178 4179 4180
    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;
4181

4182
    if (covering_null_row_width)
4183 4184 4185 4186 4187
      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);

4188 4189 4190 4191 4192 4193
    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)
4194
    {
4195
      pm_engine=
unknown's avatar
unknown committed
4196
        new subselect_rowid_merge_engine(thd, (subselect_uniquesubquery_engine*)
4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214
                                         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;
      }
4215
    }
4216 4217

    if (strategy == PARTIAL_MATCH_SCAN)
4218
    {
4219
      if (!(pm_engine=
unknown's avatar
unknown committed
4220
            new subselect_table_scan_engine(thd, (subselect_uniquesubquery_engine*)
4221 4222 4223 4224 4225 4226 4227 4228 4229
                                            lookup_engine, tmp_table,
                                            item, result,
                                            semi_join_conds->argument_list(),
                                            covering_null_row_width)))
      {
        /* This is an irrecoverable error. */
        res= 1;
        goto err;
      }
4230 4231 4232
    }
  }

4233 4234
  if (pm_engine)
    lookup_engine= pm_engine;
4235 4236 4237 4238 4239
  item_in->change_engine(lookup_engine);

err:
  thd->lex->current_select= save_select;
  DBUG_RETURN(res);
4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251
}


/**
  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(" ), "));
4252 4253 4254

  if (lookup_engine)
    lookup_engine->print(str, query_type);
4255 4256
  else
    str->append(STRING_WITH_LEN(
4257
           "<engine selected at execution time>"
4258 4259
         ));
}
4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284

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,
                                             select_result_interceptor *res)
{
  DBUG_ASSERT(FALSE);
  return TRUE;
}


4285 4286 4287 4288
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),
4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309
    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()
{
4310 4311
  my_free((char*) key_buff, MYF(0));
  bitmap_free(&null_key);
4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323 4324 4325 4326 4327 4328
}


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

4329

4330 4331 4332 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
/*
  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;
}


4403 4404 4405 4406
/*
  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
*/

4407 4408 4409 4410
bool Ordered_key::alloc_keys_buffers()
{
  DBUG_ASSERT(key_buff_elements > 0);

4411 4412
  if (!(key_buff= (rownum_t*) my_malloc((size_t)(key_buff_elements * 
    sizeof(rownum_t)), MYF(MY_WME))))
4413 4414 4415 4416 4417 4418 4419
    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.
  */
4420
  /* Notice that max_null_row is max array index, we need count, so +1. */
4421
  if (bitmap_init(&null_key, NULL, (uint)(max_null_row + 1), FALSE))
4422 4423 4424 4425 4426 4427 4428 4429 4430 4431 4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484
    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()
{
4485
  my_qsort2(key_buff, (size_t) key_buff_elements, sizeof(rownum_t),
4486 4487 4488 4489 4490 4491
            (qsort2_cmp) &cmp_keys_by_row_data_and_rownum, (void*) this);
  /* Invalidate the current row position. */
  cur_key_idx= HA_POS_ERROR;
}


4492
/*
4493 4494 4495
  The fraction of rows that do not contain NULL in the columns indexed by
  this key.

4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507
  @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);
}


4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 4622 4623 4624 4625
/*
  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;
}


4626 4627 4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641 4642 4643 4644 4645 4646 4647 4648 4649 4650 4651 4652 4653
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('}');
}


4654
subselect_partial_match_engine::subselect_partial_match_engine(
unknown's avatar
unknown committed
4655
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
4656 4657 4658 4659
  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
4660
  :subselect_engine(thd_arg, item_arg, result_arg),
4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756
   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
4757
    DBUG_ASSERT(FALSE);
4758 4759 4760 4761
  */
}


4762 4763 4764 4765
/*
  @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).
4766 4767 4768 4769

  @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
4770 4771 4772 4773 4774 4775 4776 4777 4778 4779 4780 4781
*/

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;
4782
  uint cur_keyid= 0;
4783 4784 4785 4786 4787 4788 4789 4790 4791
  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;
  }

4792 4793 4794 4795 4796 4797 4798
  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.
  */
4799 4800
  if (!(merge_keys= (Ordered_key**) thd->alloc(keys_count *
                                               sizeof(Ordered_key*))) ||
4801 4802
      !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length),
        MYF(MY_WME))))
4803 4804 4805 4806 4807
    return TRUE;

  /* Create the only non-NULL key if there is any. */
  if (non_null_key_parts)
  {
4808
    non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
4809 4810 4811
                                  0, 0, 0, row_num_to_rowid);
    if (non_null_key->init(non_null_key_parts))
      return TRUE;
4812 4813 4814
    merge_keys[cur_keyid]= non_null_key;
    merge_keys[cur_keyid]->first();
    ++cur_keyid;
4815 4816 4817 4818
  }

  /*
    If there is a covering NULL row, the only key that is needed is the
4819 4820
    only non-NULL key that is already created above. We create keys on
    NULL-able columns only if there is no covering NULL row.
4821
  */
4822
  if (!covering_null_row_width)
4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838
  {
    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
4839
      {
4840
        bitmap_set_bit(&null_only_columns, cur_keyid);
unknown's avatar
unknown committed
4841 4842
        continue;
      }
4843 4844
      else
      {
4845 4846 4847 4848 4849 4850 4851 4852
        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))
4853
          return TRUE;
4854
        merge_keys[cur_keyid]->first();
4855
      }
4856
      ++cur_keyid;
4857 4858
    }
  }
unknown's avatar
unknown committed
4859
  DBUG_ASSERT(cur_keyid == keys_count);
4860 4861

  /* Populate the indexes with data from the temporary table. */
4862 4863
  if (tmp_table->file->ha_rnd_init_with_error(1))
    return TRUE;
4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915
  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();

4916 4917 4918 4919
  /* Sort all the keys by their NULL selectivity. */
  my_qsort(merge_keys, keys_count, sizeof(Ordered_key*),
           (qsort_cmp) cmp_keys_by_null_selectivity);

4920 4921 4922 4923 4924
  /* 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,
4925 4926
                 subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
                 0, 0))
4927 4928 4929 4930 4931 4932 4933 4934
    return TRUE;

  return FALSE;
}


subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
{
4935 4936 4937 4938 4939 4940 4941 4942 4943 4944
  /* 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();
  }
4945 4946 4947 4948 4949
}


void subselect_rowid_merge_engine::cleanup()
{
4950 4951 4952
}


4953
/*
4954 4955 4956 4957 4958 4959 4960 4961 4962
  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
4963 4964 4965
*/

int
4966 4967
subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
                                                           Ordered_key **k2)
4968
{
4969 4970 4971
  double k1_sel= (*k1)->null_selectivity();
  double k2_sel= (*k2)->null_selectivity();
  if (k1_sel < k2_sel)
4972
    return 1;
4973 4974 4975
  if (k1_sel > k2_sel)
    return -1;
  return 0;
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
}


/*
*/

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)
{
5003 5004
  Ordered_key *cur_key;
  uint cur_id;
5005 5006
  for (uint i = 0; i < keys_count; i++)
  {
5007 5008 5009
    cur_key= merge_keys[i];
    cur_id= cur_key->get_keyid();
    if (bitmap_is_set(&matching_keys, cur_id))
5010 5011
    {
      /*
5012 5013
        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.
5014 5015 5016
      */
      continue;
    }
5017
    if (!cur_key->is_null(row_num))
5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035
      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;
5036
  bool res= FALSE;
5037 5038 5039

  /* 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
5040 5041
  /* The prioryty queue for keys must be empty. */
  DBUG_ASSERT(!pq.elements);
5042 5043

  /* All data accesses during execution are via handler::ha_rnd_pos() */
5044 5045 5046 5047 5048
  if (tmp_table->file->ha_rnd_init_with_error(0))
  {
    res= FALSE;
    goto end;
  }
5049

5050 5051
  /* Check if there is a match for the columns of the only non-NULL key. */
  if (non_null_key && !non_null_key->lookup())
5052 5053 5054 5055
  {
    res= FALSE;
    goto end;
  }
5056 5057 5058 5059 5060 5061

  /*
    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.
   */
5062 5063 5064 5065 5066
  if (covering_null_row_width)
  {
    res= TRUE;
    goto end;
  }
5067 5068 5069 5070 5071 5072 5073 5074 5075 5076

  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
5077
    if (merge_keys[i]->get_search_key(0)->null_value)
5078 5079
    {
      ++count_nulls_in_search_key;
5080
      bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092
    }
    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))
5093 5094 5095 5096
  {
    res= TRUE;
    goto end;
  }
5097 5098 5099 5100 5101 5102

  /*
    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)
5103 5104 5105 5106
  {
    res= FALSE;
    goto end;
  }
5107 5108 5109

  DBUG_ASSERT(pq.elements);

unknown's avatar
unknown committed
5110
  min_key= (Ordered_key*) queue_remove_top(&pq);
5111 5112
  min_row_num= min_key->current();
  bitmap_copy(&matching_keys, &null_only_columns);
5113
  bitmap_set_bit(&matching_keys, min_key->get_keyid());
5114 5115 5116 5117 5118 5119 5120 5121 5122 5123
  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.
    */
5124 5125
    res= test_null_row(min_row_num);
    goto end;
5126 5127 5128 5129
  }

  while (TRUE)
  {
unknown's avatar
unknown committed
5130
    cur_key= (Ordered_key*) queue_remove_top(&pq);
5131 5132 5133
    cur_row_num= cur_key->current();

    if (cur_row_num == min_row_num)
5134
      bitmap_set_bit(&matching_keys, cur_key->get_keyid());
5135 5136 5137 5138 5139
    else
    {
      /* Follows from the correct use of priority queue. */
      DBUG_ASSERT(cur_row_num > min_row_num);
      if (test_null_row(min_row_num))
5140 5141 5142 5143
      {
        res= TRUE;
        goto end;
      }
5144 5145 5146 5147 5148
      else
      {
        min_key= cur_key;
        min_row_num= cur_row_num;
        bitmap_copy(&matching_keys, &null_only_columns);
5149
        bitmap_set_bit(&matching_keys, min_key->get_keyid());
5150 5151 5152 5153 5154 5155 5156 5157 5158 5159
        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. */
5160 5161
      res= test_null_row(min_row_num);
      goto end;
5162 5163 5164
    }
  }

5165
  /* We should never get here - all branches must be handled explicitly above. */
5166
  DBUG_ASSERT(FALSE);
5167 5168

end:
unknown's avatar
unknown committed
5169
  queue_remove_all(&pq);
5170 5171
  tmp_table->file->ha_rnd_end();
  return res;
5172 5173 5174
}


5175
subselect_table_scan_engine::subselect_table_scan_engine(
unknown's avatar
unknown committed
5176
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5177 5178 5179 5180 5181
  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
5182
  :subselect_partial_match_engine(thd_arg, engine_arg, tmp_table_arg, item_arg,
5183 5184 5185
                                  result_arg, equi_join_conds_arg,
                                  covering_null_row_width_arg)
{}
5186

5187 5188 5189 5190 5191 5192 5193

/*
  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
5194
  {
5195 5196
    count_matches= 0;
    for each row element row_i[j]
5197
    {
5198 5199
      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
        ++count_matches;
5200
    }
5201 5202
    if (count_matches == outer_ref.elements)
      return TRUE
5203
  }
5204 5205
  return FALSE
*/
5206

5207 5208 5209 5210 5211 5212 5213
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;
5214

5215 5216 5217 5218 5219 5220
  if (tmp_table->file->ha_rnd_init_with_error(1))
  {
    res= FALSE;
    goto end;
  }

5221 5222
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
                             current_thd->variables.read_buff_size);
5223
  /*
5224 5225
  TIMOUR:
  scan_table() also calls "table->null_row= 0;", why, do we need it?
5226
  */
5227
  for (;;)
5228
  {
5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 5261 5262
    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;
    }
5263
  }
5264 5265 5266

  res= FALSE;
end:
5267
  tmp_table->file->ha_rnd_end();
5268 5269
  return res;
}
5270

5271 5272 5273

void subselect_table_scan_engine::cleanup()
{
5274
}