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

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
6 7 8 9 10 11 12 13 14 15

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

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

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

  @brief
  subselect Item
21

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

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

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

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

unknown's avatar
unknown committed
36

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

59

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

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

74 75 76 77 78 79 80
  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;
81
    own_engine= FALSE;
82
    parsing_place= unit->item->parsing_place;
83 84
    thd->change_item_tree((Item**)&unit->item, this);
    engine->change_result(this, result, TRUE);
85
  }
unknown's avatar
unknown committed
86
  else
87
  {
unknown's avatar
unknown committed
88 89 90 91 92 93 94 95
    SELECT_LEX *outer_select= unit->outer_select();
    /*
      do not take into account expression inside aggregate functions because
      they can access original table fields
    */
    parsing_place= (outer_select->in_sum_expr ?
                    NO_MATTER :
                    outer_select->parsing_place);
96
    if (unit->is_union())
unknown's avatar
unknown committed
97
      engine= new subselect_union_engine(thd, unit, result, this);
98
    else
unknown's avatar
unknown committed
99
      engine= new subselect_single_select_engine(thd, select_lex, result, this);
100
  }
101 102
  {
    SELECT_LEX *upper= unit->outer_select();
103
    if (upper->parsing_place == IN_HAVING)
104
      upper->subquery_in_having= 1;
unknown's avatar
unknown committed
105 106
    /* The subquery is an expression cache candidate */
    upper->expr_cache_may_be_used[upper->parsing_place]= TRUE;
107
  }
108
  DBUG_PRINT("info", ("engine: 0x%lx", (ulong)engine));
109 110 111
  DBUG_VOID_RETURN;
}

112 113 114 115 116 117
st_select_lex *
Item_subselect::get_select_lex()
{
  return unit->first_select();
}

unknown's avatar
unknown committed
118 119
void Item_subselect::cleanup()
{
unknown's avatar
unknown committed
120
  DBUG_ENTER("Item_subselect::cleanup");
unknown's avatar
unknown committed
121
  Item_result_field::cleanup();
unknown's avatar
unknown committed
122 123
  if (old_engine)
  {
124 125
    if (engine)
      engine->cleanup();
unknown's avatar
unknown committed
126 127 128
    engine= old_engine;
    old_engine= 0;
  }
129 130
  if (engine)
    engine->cleanup();
unknown's avatar
unknown committed
131 132
  reset();
  value_assigned= 0;
133
  expr_cache= 0;
134
  forced_const= FALSE;
unknown's avatar
unknown committed
135 136 137 138
  DBUG_PRINT("info", ("exec_counter: %d", exec_counter));
#ifndef DBUG_OFF
  exec_counter= 0;
#endif
unknown's avatar
unknown committed
139 140 141
  DBUG_VOID_RETURN;
}

142

unknown's avatar
unknown committed
143 144 145 146 147 148
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
149
}
150

151 152 153 154 155 156 157 158 159 160

void Item_in_subselect::cleanup()
{
  DBUG_ENTER("Item_in_subselect::cleanup");
  if (left_expr_cache)
  {
    left_expr_cache->delete_elements();
    delete left_expr_cache;
    left_expr_cache= NULL;
  }
unknown's avatar
unknown committed
161 162 163 164
  /*
    TODO: This breaks the commented assert in add_strategy().
    in_strategy&= ~SUBS_STRATEGY_CHOSEN;
  */
165
  first_execution= TRUE;
166
  pushed_cond_guards= NULL;
167 168 169 170
  Item_subselect::cleanup();
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
171 172 173 174 175 176 177 178 179 180

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


unknown's avatar
unknown committed
187 188
Item_subselect::~Item_subselect()
{
189 190
  DBUG_ENTER("Item_subselect::~Item_subselect");
  DBUG_PRINT("enter", ("this: 0x%lx", (ulong) this));
191
  if (own_engine)
192 193 194
    delete engine;
  else
    engine->cleanup();
195
  engine= NULL;
196
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
197 198
}

unknown's avatar
unknown committed
199
bool
200
Item_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
201 202
{
  DBUG_ENTER("Item_subselect::select_transformer");
unknown's avatar
unknown committed
203
  DBUG_RETURN(false);
unknown's avatar
unknown committed
204 205 206
}


207
bool Item_subselect::fix_fields(THD *thd_param, Item **ref)
208
{
unknown's avatar
unknown committed
209
  char const *save_where= thd_param->where;
unknown's avatar
unknown committed
210
  uint8 uncacheable;
unknown's avatar
unknown committed
211
  bool res;
unknown's avatar
unknown committed
212

213
  DBUG_ASSERT(fixed == 0);
unknown's avatar
unknown committed
214 215
  /* There is no reason to get a different THD. */
  DBUG_ASSERT(thd == thd_param);
216 217 218 219
  if (!done_first_fix_fields)
  {
    done_first_fix_fields= TRUE;
    inside_first_fix_fields= TRUE;
220 221 222 223 224
    upper_refs.empty();
    /*
      psergey-todo: remove _first_fix_fields calls, we need changes on every
      execution
    */
225 226
  }

Sergey Petrunia's avatar
Sergey Petrunia committed
227
  eliminated= FALSE;
228
  parent_select= thd_param->lex->current_select;
229

230
  if (check_stack_overrun(thd, STACK_MIN_SIZE, (uchar*)&res))
unknown's avatar
unknown committed
231
    return TRUE;
Sergey Petrunia's avatar
Sergey Petrunia committed
232
  
233
  
234
  if (!(res= engine->prepare()))
unknown's avatar
unknown committed
235
  {
236 237
    // all transformation is done (used by prepared statements)
    changed= 1;
238
    inside_first_fix_fields= FALSE;
239 240 241 242 243 244 245

    /*
      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.
    */
246 247
    if (substitution)
    {
248 249 250 251
      /*
        If the top item of the WHERE/HAVING condition changed,
        set correct WHERE/HAVING for PS.
      */
unknown's avatar
unknown committed
252
      if (unit->outer_select()->where == (*ref))
unknown's avatar
unknown committed
253
        unit->outer_select()->where= substitution;
254
      else if (unit->outer_select()->having == (*ref))
unknown's avatar
unknown committed
255
        unit->outer_select()->having= substitution;
unknown's avatar
unknown committed
256

257 258 259 260 261
      (*ref)= substitution;
      substitution->name= name;
      if (have_to_be_excluded)
	engine->exclude();
      substitution= 0;
262
      thd->where= "checking transformed subquery";
263
      if (!(*ref)->fixed)
264 265
	res= (*ref)->fix_fields(thd, ref);
      goto end;
Sergey Petrunya's avatar
Sergey Petrunya committed
266

267
    }
unknown's avatar
unknown committed
268 269
    // Is it one field subselect?
    if (engine->cols() > max_columns)
270
    {
unknown's avatar
unknown committed
271
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
Sergey Petrunya's avatar
Sergey Petrunya committed
272

273
      goto end;
unknown's avatar
unknown committed
274
    }
275
    fix_length_and_dec();
unknown's avatar
unknown committed
276
  }
unknown's avatar
unknown committed
277
  else
278
    goto end;
unknown's avatar
unknown committed
279 280
  
  if ((uncacheable= engine->uncacheable()))
unknown's avatar
unknown committed
281 282
  {
    const_item_cache= 0;
283 284
    if (uncacheable & UNCACHEABLE_RAND)
      used_tables_cache|= RAND_TABLE_BIT;
unknown's avatar
unknown committed
285
  }
286
  fixed= 1;
unknown's avatar
unknown committed
287

288
end:
289
  done_first_fix_fields= FALSE;
Sergey Petrunya's avatar
Sergey Petrunya committed
290
  inside_first_fix_fields= FALSE;
291
  thd->where= save_where;
292 293 294
  return res;
}

295

Sergey Petrunya's avatar
Sergey Petrunya committed
296
bool Item_subselect::enumerate_field_refs_processor(uchar *arg)
Sergey Petrunia's avatar
Sergey Petrunia committed
297
{
298 299 300 301
  List_iterator<Ref_to_outside> it(upper_refs);
  Ref_to_outside *upper;
  
  while ((upper= it++))
Sergey Petrunia's avatar
Sergey Petrunia committed
302
  {
303
    if (upper->item->walk(&Item::enumerate_field_refs_processor, FALSE, arg))
Sergey Petrunia's avatar
Sergey Petrunia committed
304 305 306 307 308 309 310 311 312 313 314
      return TRUE;
  }
  return FALSE;
}

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

315

316 317 318 319 320 321 322 323 324 325
/**
  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.
*/

326 327 328 329 330 331 332 333 334
bool Item_subselect::eliminate_subselect_processor(uchar *arg)
{
  unit->item= NULL;
  unit->exclude_from_tree();
  eliminated= TRUE;
  return FALSE;
}


335
/**
336 337 338
  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.
339 340 341 342 343

  @param arg  pointer to the fake select

  @return
    FALSE to force the evaluation of the processor for the subsequent items.
344 345 346 347 348 349
*/

bool Item_subselect::set_fake_select_as_master_processor(uchar *arg)
{
  SELECT_LEX *fake_select= (SELECT_LEX*) arg;
  /*
350 351
    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
352 353 354 355
    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.
356 357 358 359
  */
  if (unit->outer_select()->master_unit()->fake_select_lex == fake_select)
  {
    /*
unknown's avatar
unknown committed
360 361
      Set the master of the subquery to be the fake select (i.e. the whole
      UNION), instead of the last query in the UNION.
362
    */
unknown's avatar
unknown committed
363 364
    fake_select->add_slave(unit);
    DBUG_ASSERT(unit->outer_select() == fake_select);
365 366 367 368
    /* 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);
    /*
369 370
      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.
371 372 373 374
    */
    unit->item= this;
    eliminated= FALSE;
  }
375
  return FALSE;
376 377 378
}


379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
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;
}

396

397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424
/*
  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;
}

425

426 427 428 429 430
class Field_fixer: public Field_enumerator
{
public:
  table_map used_tables; /* Collect used_tables here */
  st_select_lex *new_parent; /* Select we're in */
431
  virtual void visit_field(Item_field *item)
432 433 434 435 436
  {
    //for (TABLE_LIST *tbl= new_parent->leaf_tables; tbl; tbl= tbl->next_local)
    //{
    //  if (tbl->table == field->table)
    //  {
437
        used_tables|= item->field->table->map;
438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495
    //    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;
Igor Babaev's avatar
Igor Babaev committed
496
          upper->item->walk(&Item::update_table_bitmaps_processor, FALSE, NULL);
Sergey Petrunya's avatar
Sergey Petrunya committed
497
/*
498 499 500
          if (after_pullout)
            upper->item->fix_after_pullout(new_parent, &(upper->item));
          upper->item->update_used_tables();
Sergey Petrunya's avatar
Sergey Petrunya committed
501
*/          
502 503 504 505 506 507 508 509 510 511 512 513 514 515
        }
      }
    }
    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.
  */
}

516
bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
517
                          uchar *argument)
518
{
519 520 521 522 523 524 525 526 527 528 529 530
  if (!(unit->uncacheable & ~UNCACHEABLE_DEPENDENT) && engine->is_executed() &&
      !unit->describe)
  {
    /*
      The subquery has already been executed (for real, it wasn't EXPLAIN's
      fake execution) so it should not matter what it has inside.
      
      The actual reason for not walking inside is that parts of the subquery
      (e.g. JTBM join nests and their IN-equality conditions may have been 
       invalidated by irreversible cleanups (those happen after an uncorrelated 
       subquery has been executed).
    */
531
    return (this->*processor)(argument);
532
  }
533 534 535 536 537 538 539 540 541 542 543 544 545 546

  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
547
      /* TODO: why does this walk WHERE/HAVING but not ON expressions of outer joins? */
548 549 550 551 552 553

      while ((item=li++))
      {
        if (item->walk(processor, walk_subquery, argument))
          return 1;
      }
554
      for (order= lex->order_list.first ; order; order= order->next)
555 556 557 558
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
559
      for (order= lex->group_list.first ; order; order= order->next)
560 561 562 563 564 565 566 567 568 569
      {
        if ((*order->item)->walk(processor, walk_subquery, argument))
          return 1;
      }
    }
  }
  return (this->*processor)(argument);
}


570
bool Item_subselect::exec()
571
{
572
  int res;
unknown's avatar
unknown committed
573

574 575 576 577 578
  /*
    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
579
    return 1;
580

Sergey Glukhov's avatar
Sergey Glukhov committed
581
  DBUG_ASSERT(!thd->lex->context_analysis_only);
582 583 584 585 586
  /*
    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
587

588
  res= engine->exec();
unknown's avatar
unknown committed
589 590 591
#ifndef DBUG_OFF
  ++exec_counter;
#endif
592 593 594
  if (engine_changed)
  {
    engine_changed= 0;
595
    return exec();
596 597
  }
  return (res);
598 599
}

600

unknown's avatar
unknown committed
601 602
void Item_subselect::get_cache_parameters(List<Item> &parameters)
{
unknown's avatar
unknown committed
603 604 605
  Collect_deps_prm prm= {&parameters,
    unit->first_select()->nest_level_base,
    unit->first_select()->nest_level};
unknown's avatar
unknown committed
606 607 608
  walk(&Item::collect_outer_ref_processor, TRUE, (uchar*)&prm);
}

Sergey Petrunya's avatar
Sergey Petrunya committed
609 610 611 612 613 614 615 616 617 618
int Item_in_subselect::optimize(double *out_rows, double *cost)
{
  int res;
  DBUG_ENTER("Item_in_subselect::optimize");
  SELECT_LEX *save_select= thd->lex->current_select;
  JOIN *join= unit->first_select()->join;

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

Sergey Petrunya's avatar
Sergey Petrunya committed
620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655
  /* Calculate #rows and cost of join execution */
  join->get_partial_cost_and_fanout(join->table_count - join->const_tables, 
                                    table_map(-1),
                                    cost, out_rows);

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

  DBUG_RETURN(res);

}
Sergey Petrunya's avatar
Sergey Petrunya committed
656 657


unknown's avatar
unknown committed
658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
/**
  Check if an expression cache is needed for this subquery

  @param thd             Thread handle

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

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

bool Item_subselect::expr_cache_is_needed(THD *thd)
{
unknown's avatar
unknown committed
673
  return ((engine->uncacheable() & UNCACHEABLE_DEPENDENT) &&
unknown's avatar
unknown committed
674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700
          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)
{
unknown's avatar
unknown committed
701
  return (optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
unknown's avatar
unknown committed
702 703 704 705 706
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
                                     UNCACHEABLE_SIDEEFFECT)));
}


707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725
/*
  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.
  */
unknown's avatar
unknown committed
726
  if (!left_expr_cache && (test_strategy(SUBS_MATERIALIZATION)))
727 728
    init_left_expr_cache();

729 730 731 732 733 734 735 736
  /*
    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);
737 738 739 740 741 742 743 744 745 746

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


747
Item::Type Item_subselect::type() const
748 749 750 751
{
  return SUBSELECT_ITEM;
}

unknown's avatar
unknown committed
752

753 754
void Item_subselect::fix_length_and_dec()
{
755
  engine->fix_length_and_dec(0);
756
}
unknown's avatar
unknown committed
757

unknown's avatar
unknown committed
758

759
table_map Item_subselect::used_tables() const
unknown's avatar
unknown committed
760
{
761
  return (table_map) (engine->uncacheable() ? used_tables_cache : 0L);
unknown's avatar
unknown committed
762 763
}

unknown's avatar
merge  
unknown committed
764

765 766
bool Item_subselect::const_item() const
{
Sergey Glukhov's avatar
Sergey Glukhov committed
767
  return thd->lex->context_analysis_only ? FALSE : const_item_cache;
768 769
}

770
Item *Item_subselect::get_tmp_table_item(THD *thd_arg)
unknown's avatar
unknown committed
771 772
{
  if (!with_sum_func && !const_item())
unknown's avatar
unknown committed
773
    return new Item_field(result_field);
774
  return copy_or_same(thd_arg);
unknown's avatar
unknown committed
775
}
unknown's avatar
merge  
unknown committed
776

777 778
void Item_subselect::update_used_tables()
{
779
  if (!forced_const)
780
  {
781 782 783 784 785 786 787
    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;
    }
788 789 790
  }
}

unknown's avatar
unknown committed
791

792
void Item_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
793
{
794 795 796 797 798 799 800 801
  if (engine)
  {
    str->append('(');
    engine->print(str, query_type);
    str->append(')');
  }
  else
    str->append("(...)");
unknown's avatar
unknown committed
802 803 804
}


unknown's avatar
merge  
unknown committed
805
Item_singlerow_subselect::Item_singlerow_subselect(st_select_lex *select_lex)
806
  :Item_subselect(), value(0)
unknown's avatar
unknown committed
807
{
unknown's avatar
unknown committed
808
  DBUG_ENTER("Item_singlerow_subselect::Item_singlerow_subselect");
809
  init(select_lex, new select_singlerow_subselect(this));
unknown's avatar
unknown committed
810
  maybe_null= 1;
811
  max_columns= UINT_MAX;
unknown's avatar
unknown committed
812
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
813 814
}

815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834
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
835 836
Item_maxmin_subselect::Item_maxmin_subselect(THD *thd_param,
                                             Item_subselect *parent,
837
					     st_select_lex *select_lex,
unknown's avatar
unknown committed
838
					     bool max_arg)
839
  :Item_singlerow_subselect(), was_values(TRUE)
840 841
{
  DBUG_ENTER("Item_maxmin_subselect::Item_maxmin_subselect");
unknown's avatar
unknown committed
842
  max= max_arg;
unknown's avatar
unknown committed
843 844 845 846
  init(select_lex,
       new select_max_min_finder_subselect(this, max_arg,
                                           parent->substype() ==
                                           Item_subselect::ALL_SUBS));
847 848 849
  max_columns= 1;
  maybe_null= 1;
  max_columns= 1;
850 851 852 853 854 855

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

unknown's avatar
unknown committed
858
  /*
unknown's avatar
unknown committed
859
    this subquery always creates during preparation, so we can assign
unknown's avatar
unknown committed
860 861 862 863
    thd here
  */
  thd= thd_param;

864 865 866
  DBUG_VOID_RETURN;
}

867 868
void Item_maxmin_subselect::cleanup()
{
unknown's avatar
unknown committed
869 870 871
  DBUG_ENTER("Item_maxmin_subselect::cleanup");
  Item_singlerow_subselect::cleanup();

872
  /*
unknown's avatar
unknown committed
873
    By default it is TRUE to avoid TRUE reporting by
874 875 876
    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
877 878
    select_max_min_finder_subselect::send_data() set it back to TRUE if some
    value will be found.
879 880
  */
  was_values= TRUE;
unknown's avatar
unknown committed
881
  DBUG_VOID_RETURN;
882 883 884
}


885
void Item_maxmin_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
886
{
887
  str->append(max?"<max>":"<min>", 5);
888
  Item_singlerow_subselect::print(str, query_type);
unknown's avatar
unknown committed
889 890
}

891

unknown's avatar
unknown committed
892
void Item_singlerow_subselect::reset()
893
{
894
  Item_subselect::reset();
895
  if (value)
unknown's avatar
unknown committed
896 897 898 899
  {
    for(uint i= 0; i < engine->cols(); i++)
      row[i]->set_null();
  }
900 901
}

902

unknown's avatar
unknown committed
903 904 905 906 907 908 909 910 911
/**
  @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
912 913 914 915

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

  @retval false  The subquery was transformed
unknown's avatar
unknown committed
916
*/
unknown's avatar
unknown committed
917
bool
unknown's avatar
unknown committed
918
Item_singlerow_subselect::select_transformer(JOIN *join)
919
{
920
  DBUG_ENTER("Item_singlerow_subselect::select_transformer");
unknown's avatar
unknown committed
921
  if (changed)
unknown's avatar
unknown committed
922
    DBUG_RETURN(false);
923

924
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
925
  Query_arena *arena= thd->stmt_arena;
unknown's avatar
unknown committed
926
 
927
  if (!select_lex->master_unit()->is_union() &&
928
      !select_lex->table_list.elements &&
unknown's avatar
unknown committed
929
      select_lex->item_list.elements == 1 &&
930
      !select_lex->item_list.head()->with_sum_func &&
unknown's avatar
unknown committed
931 932 933 934 935 936 937
      /*
	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
938
      !(select_lex->item_list.head()->type() == FIELD_ITEM ||
939
	select_lex->item_list.head()->type() == REF_ITEM) &&
940
      !join->conds && !join->having &&
941
      /*
unknown's avatar
unknown committed
942
        switch off this optimization for prepare statement,
943 944 945
        because we do not rollback this changes
        TODO: make rollback for it, or special name resolving mode in 5.0.
      */
946
      !arena->is_stmt_prepare_or_first_sp_execute()
unknown's avatar
unknown committed
947
      )
948 949
  {
    have_to_be_excluded= 1;
unknown's avatar
unknown committed
950
    if (thd->lex->describe)
951 952 953
    {
      char warn_buff[MYSQL_ERRMSG_SIZE];
      sprintf(warn_buff, ER(ER_SELECT_REDUCED), select_lex->select_number);
unknown's avatar
unknown committed
954
      push_warning(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
955 956 957
		   ER_SELECT_REDUCED, warn_buff);
    }
    substitution= select_lex->item_list.head();
unknown's avatar
unknown committed
958
    /*
unknown's avatar
unknown committed
959
      as far as we moved content to upper level, field which depend of
unknown's avatar
unknown committed
960 961
      'upper' select is not really dependent => we remove this dependence
    */
962
    substitution->walk(&Item::remove_dependence_processor, 0,
963
		       (uchar *) select_lex->outer_select());
964
  }
unknown's avatar
unknown committed
965
  DBUG_RETURN(false);
966 967
}

unknown's avatar
unknown committed
968

unknown's avatar
unknown committed
969
void Item_singlerow_subselect::store(uint i, Item *item)
unknown's avatar
unknown committed
970
{
971
  row[i]->store(item);
972
  row[i]->cache_value();
unknown's avatar
unknown committed
973 974
}

unknown's avatar
unknown committed
975
enum Item_result Item_singlerow_subselect::result_type() const
unknown's avatar
unknown committed
976
{
977 978 979
  return engine->type();
}

980 981 982 983 984 985 986 987 988
/* 
 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
989
void Item_singlerow_subselect::fix_length_and_dec()
990
{
991 992 993 994 995
  if ((max_columns= engine->cols()) == 1)
  {
    engine->fix_length_and_dec(row= &value);
  }
  else
996
  {
997
    if (!(row= (Item_cache**) sql_alloc(sizeof(Item_cache*)*max_columns)))
998 999 1000
      return;
    engine->fix_length_and_dec(row);
    value= *row;
1001
  }
1002
  unsigned_flag= value->unsigned_flag;
1003 1004 1005 1006 1007 1008 1009
  /*
    If there are not tables in subquery then ability to have NULL value
    depends on SELECT list (if single row subquery have tables then it
    always can be NULL if there are not records fetched).
  */
  if (engine->no_tables())
    maybe_null= engine->may_be_null();
unknown's avatar
unknown committed
1010 1011 1012 1013 1014
  else
  {
    for (uint i= 0; i < max_columns; i++)
      row[i]->maybe_null= TRUE;
  }
1015 1016
}

unknown's avatar
unknown committed
1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040

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

1041 1042 1043 1044
  if (expr_cache)
    DBUG_RETURN(expr_cache);

  if (expr_cache_is_needed(thd) &&
unknown's avatar
unknown committed
1045
      (expr_cache= set_expr_cache(thd)))
1046
    DBUG_RETURN(expr_cache);
unknown's avatar
unknown committed
1047 1048 1049 1050
  DBUG_RETURN(this);
}


unknown's avatar
unknown committed
1051
uint Item_singlerow_subselect::cols()
unknown's avatar
unknown committed
1052
{
1053 1054 1055
  return engine->cols();
}

unknown's avatar
unknown committed
1056
bool Item_singlerow_subselect::check_cols(uint c)
1057 1058 1059
{
  if (c != engine->cols())
  {
unknown's avatar
unknown committed
1060
    my_error(ER_OPERAND_COLUMNS, MYF(0), c);
1061 1062 1063 1064 1065
    return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1066
bool Item_singlerow_subselect::null_inside()
1067 1068 1069 1070 1071 1072 1073 1074 1075
{
  for (uint i= 0; i < max_columns ; i++)
  {
    if (row[i]->null_value)
      return 1;
  }
  return 0;
}

unknown's avatar
unknown committed
1076
void Item_singlerow_subselect::bring_value()
1077
{
1078 1079 1080 1081
  if (!exec() && assigned())
    null_value= 0;
  else
    reset();
unknown's avatar
unknown committed
1082 1083
}

1084
double Item_singlerow_subselect::val_real()
unknown's avatar
unknown committed
1085
{
1086
  DBUG_ASSERT(fixed == 1);
1087
  if (!exec() && !value->null_value)
1088
  {
1089
    null_value= FALSE;
1090
    return value->val_real();
1091 1092
  }
  else
unknown's avatar
unknown committed
1093
  {
1094
    reset();
unknown's avatar
unknown committed
1095
    return 0;
unknown's avatar
unknown committed
1096
  }
unknown's avatar
unknown committed
1097 1098
}

1099
longlong Item_singlerow_subselect::val_int()
unknown's avatar
unknown committed
1100
{
1101
  DBUG_ASSERT(fixed == 1);
1102
  if (!exec() && !value->null_value)
1103
  {
1104
    null_value= FALSE;
1105 1106 1107
    return value->val_int();
  }
  else
unknown's avatar
unknown committed
1108
  {
1109
    reset();
unknown's avatar
unknown committed
1110
    return 0;
unknown's avatar
unknown committed
1111
  }
unknown's avatar
unknown committed
1112 1113
}

unknown's avatar
unknown committed
1114
String *Item_singlerow_subselect::val_str(String *str)
unknown's avatar
unknown committed
1115
{
1116
  if (!exec() && !value->null_value)
1117
  {
1118
    null_value= FALSE;
1119 1120 1121
    return value->val_str(str);
  }
  else
unknown's avatar
unknown committed
1122
  {
1123
    reset();
unknown's avatar
unknown committed
1124
    return 0;
unknown's avatar
unknown committed
1125
  }
unknown's avatar
unknown committed
1126 1127
}

unknown's avatar
unknown committed
1128

unknown's avatar
unknown committed
1129 1130
my_decimal *Item_singlerow_subselect::val_decimal(my_decimal *decimal_value)
{
1131
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1132
  {
1133
    null_value= FALSE;
unknown's avatar
unknown committed
1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145
    return value->val_decimal(decimal_value);
  }
  else
  {
    reset();
    return 0;
  }
}


bool Item_singlerow_subselect::val_bool()
{
1146
  if (!exec() && !value->null_value)
unknown's avatar
unknown committed
1147
  {
1148
    null_value= FALSE;
unknown's avatar
unknown committed
1149 1150 1151 1152 1153 1154 1155 1156 1157 1158
    return value->val_bool();
  }
  else
  {
    reset();
    return 0;
  }
}


1159
Item_exists_subselect::Item_exists_subselect(st_select_lex *select_lex):
1160
  Item_subselect()
unknown's avatar
unknown committed
1161
{
unknown's avatar
unknown committed
1162
  DBUG_ENTER("Item_exists_subselect::Item_exists_subselect");
unknown's avatar
unknown committed
1163
  bool val_bool();
1164
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1165
  max_columns= UINT_MAX;
1166
  null_value= FALSE; //can't be NULL
unknown's avatar
unknown committed
1167 1168
  maybe_null= 0; //can't be NULL
  value= 0;
unknown's avatar
unknown committed
1169 1170 1171
  DBUG_VOID_RETURN;
}

unknown's avatar
unknown committed
1172

1173
void Item_exists_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
1174
{
1175
  str->append(STRING_WITH_LEN("exists"));
1176
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
1177 1178 1179
}


unknown's avatar
unknown committed
1180
bool Item_in_subselect::test_limit(st_select_lex_unit *unit_arg)
1181
{
1182 1183
  if (unit_arg->fake_select_lex &&
      unit_arg->fake_select_lex->test_limit())
1184
    return(1);
unknown's avatar
unknown committed
1185

1186
  SELECT_LEX *sl= unit_arg->first_select();
1187 1188
  for (; sl; sl= sl->next_select())
  {
unknown's avatar
unknown committed
1189
    if (sl->test_limit())
1190 1191 1192 1193 1194
      return(1);
  }
  return(0);
}

1195
Item_in_subselect::Item_in_subselect(Item * left_exp,
unknown's avatar
unknown committed
1196
				     st_select_lex *select_lex):
1197
  Item_exists_subselect(), 
unknown's avatar
unknown committed
1198 1199
  left_expr_cache(0), first_execution(TRUE), in_strategy(SUBS_NOT_TRANSFORMED),
  optimizer(0), pushed_cond_guards(NULL), emb_on_expr_nest(NULL),
1200 1201
  is_jtbm_merged(FALSE), is_jtbm_const_tab(FALSE), 
  is_flattenable_semijoin(FALSE),
Igor Babaev's avatar
Igor Babaev committed
1202
  is_registered_semijoin(FALSE), 
Sergey Petrunya's avatar
Sergey Petrunya committed
1203
  upper_item(0)
unknown's avatar
unknown committed
1204 1205
{
  DBUG_ENTER("Item_in_subselect::Item_in_subselect");
unknown's avatar
unknown committed
1206
  left_expr= left_exp;
1207
  func= &eq_creator;
1208
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1209
  max_columns= UINT_MAX;
1210
  maybe_null= 1;
1211
  abort_on_null= 0;
1212
  reset();
unknown's avatar
unknown committed
1213
  //if test_limit will fail then error will be reported to client
1214
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1215 1216 1217
  DBUG_VOID_RETURN;
}

1218 1219 1220 1221 1222
int Item_in_subselect::get_identifier()
{
  return engine->get_identifier();
}

1223
Item_allany_subselect::Item_allany_subselect(Item * left_exp,
1224
                                             chooser_compare_func_creator fc,
unknown's avatar
unknown committed
1225 1226
					     st_select_lex *select_lex,
					     bool all_arg)
unknown's avatar
unknown committed
1227
  :Item_in_subselect(), func_creator(fc), all(all_arg)
unknown's avatar
unknown committed
1228
{
1229
  DBUG_ENTER("Item_allany_subselect::Item_allany_subselect");
unknown's avatar
unknown committed
1230
  left_expr= left_exp;
1231
  func= func_creator(all_arg);
1232
  init(select_lex, new select_exists_subselect(this));
unknown's avatar
unknown committed
1233
  max_columns= 1;
1234
  abort_on_null= 0;
1235
  reset();
unknown's avatar
unknown committed
1236
  //if test_limit will fail then error will be reported to client
1237
  test_limit(select_lex->master_unit());
unknown's avatar
unknown committed
1238
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
1239 1240
}

unknown's avatar
unknown committed
1241

1242 1243 1244 1245 1246 1247
/**
  Initialize length and decimals for EXISTS  and inherited (IN/ALL/ANY)
  subqueries
*/

void Item_exists_subselect::init_length_and_dec()
1248
{
1249 1250 1251
  decimals= 0;
  max_length= 1;
  max_columns= engine->cols();
1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262
}


void Item_exists_subselect::fix_length_and_dec()
{
  DBUG_ENTER("Item_exists_subselect::fix_length_and_dec");
  init_length_and_dec();
  /*
    We need only 1 row to determine existence (i.e. any EXISTS that is not
    an IN always requires LIMIT 1)
  */
1263
  unit->global_parameters->select_limit= new Item_int((int32) 1);
1264 1265 1266 1267
  DBUG_PRINT("info", ("Set limit to 1"));
  DBUG_VOID_RETURN;
}

1268

1269 1270 1271
void Item_in_subselect::fix_length_and_dec()
{
  DBUG_ENTER("Item_in_subselect::fix_length_and_dec");
1272 1273 1274 1275 1276
  init_length_and_dec();
  /*
    Unlike Item_exists_subselect, LIMIT 1 is set later for
    Item_in_subselect, depending on the chosen strategy.
  */
1277
  DBUG_VOID_RETURN;
1278 1279
}

unknown's avatar
unknown committed
1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303

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

1304 1305 1306 1307
  if (expr_cache)
    DBUG_RETURN(expr_cache);

  if (substype() == EXISTS_SUBS && expr_cache_is_needed(thd) &&
unknown's avatar
unknown committed
1308
      (expr_cache= set_expr_cache(thd)))
1309
    DBUG_RETURN(expr_cache);
unknown's avatar
unknown committed
1310 1311 1312 1313
  DBUG_RETURN(this);
}


1314
double Item_exists_subselect::val_real()
unknown's avatar
unknown committed
1315
{
1316
  DBUG_ASSERT(fixed == 1);
1317
  if (exec())
unknown's avatar
unknown committed
1318
  {
1319
    reset();
unknown's avatar
unknown committed
1320
    return 0;
unknown's avatar
unknown committed
1321
  }
unknown's avatar
unknown committed
1322 1323 1324
  return (double) value;
}

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

1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349

/**
  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
1350 1351
String *Item_exists_subselect::val_str(String *str)
{
1352
  DBUG_ASSERT(fixed == 1);
1353
  if (exec())
1354
    reset();
unknown's avatar
unknown committed
1355
  str->set((ulonglong)value,&my_charset_bin);
1356 1357 1358
  return str;
}

unknown's avatar
unknown committed
1359

1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372
/**
  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
1373 1374 1375
my_decimal *Item_exists_subselect::val_decimal(my_decimal *decimal_value)
{
  DBUG_ASSERT(fixed == 1);
1376
  if (exec())
unknown's avatar
unknown committed
1377 1378 1379 1380 1381 1382 1383 1384 1385
    reset();
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


bool Item_exists_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1386
  if (exec())
unknown's avatar
unknown committed
1387 1388 1389 1390
  {
    reset();
    return 0;
  }
1391
  return value != 0;
unknown's avatar
unknown committed
1392 1393 1394
}


1395
double Item_in_subselect::val_real()
1396
{
unknown's avatar
unknown committed
1397 1398 1399 1400 1401
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1402
  DBUG_ASSERT(fixed == 1);
1403
  null_value= was_null= FALSE;
1404
  if (exec())
1405 1406 1407 1408 1409
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1410
    null_value= TRUE;
1411 1412 1413
  return (double) value;
}

unknown's avatar
unknown committed
1414

1415
longlong Item_in_subselect::val_int()
1416
{
unknown's avatar
unknown committed
1417 1418 1419 1420 1421
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1422
  DBUG_ASSERT(fixed == 1);
1423
  null_value= was_null= FALSE;
1424
  if (exec())
1425 1426 1427 1428 1429
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1430
    null_value= TRUE;
1431 1432 1433
  return value;
}

unknown's avatar
unknown committed
1434

1435 1436
String *Item_in_subselect::val_str(String *str)
{
unknown's avatar
unknown committed
1437 1438 1439 1440 1441
  /*
    As far as Item_in_subselect called only from Item_in_optimizer this
    method should not be used
  */
  DBUG_ASSERT(0);
1442
  DBUG_ASSERT(fixed == 1);
1443
  null_value= was_null= FALSE;
1444
  if (exec())
1445 1446 1447 1448 1449 1450
  {
    reset();
    return 0;
  }
  if (was_null && !value)
  {
1451
    null_value= TRUE;
unknown's avatar
unknown committed
1452
    return 0;
unknown's avatar
unknown committed
1453
  }
unknown's avatar
unknown committed
1454
  str->set((ulonglong)value, &my_charset_bin);
unknown's avatar
unknown committed
1455 1456 1457
  return str;
}

unknown's avatar
unknown committed
1458

unknown's avatar
unknown committed
1459 1460 1461
bool Item_in_subselect::val_bool()
{
  DBUG_ASSERT(fixed == 1);
1462
  if (forced_const)
1463
    return value;
unknown's avatar
unknown committed
1464
  null_value= was_null= FALSE;
1465
  if (exec())
unknown's avatar
unknown committed
1466 1467 1468 1469 1470
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1471
    null_value= TRUE;
unknown's avatar
unknown committed
1472 1473 1474 1475 1476 1477 1478 1479 1480 1481
  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);
1482
  null_value= was_null= FALSE;
unknown's avatar
unknown committed
1483
  DBUG_ASSERT(fixed == 1);
1484
  if (exec())
unknown's avatar
unknown committed
1485 1486 1487 1488 1489
  {
    reset();
    return 0;
  }
  if (was_null && !value)
1490
    null_value= TRUE;
unknown's avatar
unknown committed
1491 1492 1493 1494 1495
  int2my_decimal(E_DEC_FATAL_ERROR, value, 0, decimal_value);
  return decimal_value;
}


1496
/**
1497
  Prepare a single-column IN/ALL/ANY subselect for rewriting.
1498

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

1501
  @details
1502

1503
  Prepare a single-column subquery to be rewritten. Given the subquery.
1504

1505 1506 1507 1508 1509
  If the subquery has no tables it will be turned to an expression between
  left part and SELECT list.

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

unknown's avatar
unknown committed
1511 1512
  @retval false  The subquery was transformed
  @retval true   Error
1513
*/
1514

unknown's avatar
unknown committed
1515
bool
1516
Item_in_subselect::single_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1517
{
1518
  SELECT_LEX *select_lex= join->select_lex;
1519
  DBUG_ENTER("Item_in_subselect::single_value_transformer");
unknown's avatar
unknown committed
1520

1521 1522 1523 1524
  /*
    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 * ...)
  */
1525
  // psergey: duplicated_subselect_card_check
1526 1527 1528
  if (select_lex->item_list.elements > 1)
  {
    my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
1529
    DBUG_RETURN(true);
1530 1531
  }

1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554
  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
1555
    DBUG_RETURN(false);
1556 1557
  }

1558 1559 1560 1561
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1562
  if (!substitution)
unknown's avatar
unknown committed
1563
  {
1564
    /* We're invoked for the 1st (or the only) SELECT in the subquery UNION */
1565
    substitution= optimizer;
1566

1567
    SELECT_LEX *current= thd->lex->current_select;
unknown's avatar
unknown committed
1568

1569
    thd->lex->current_select= current->return_after_parsing();
1570
    //optimizer never use Item **ref => we can pass 0 as parameter
1571
    if (!optimizer || optimizer->fix_left(thd, 0))
1572
    {
unknown's avatar
unknown committed
1573
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1574
      DBUG_RETURN(true);
1575
    }
unknown's avatar
unknown committed
1576
    thd->lex->current_select= current;
1577

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

1581
    /*
unknown's avatar
unknown committed
1582
      As far as  Item_ref_in_optimizer do not substitute itself on fix_fields
1583 1584
      we can use same item for all selects.
    */
1585 1586
    expr= new Item_direct_ref(&select_lex->context,
                              (Item**)optimizer->get_cache(),
1587 1588
			      (char *)"<no matter>",
			      (char *)in_left_expr_name);
1589

1590 1591 1592 1593 1594
  }

  DBUG_RETURN(false);
}

1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618

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

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

  @details

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

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

bool Item_allany_subselect::transform_into_max_min(JOIN *join)
1619
{
1620
  DBUG_ENTER("Item_allany_subselect::transform_into_max_min");
unknown's avatar
unknown committed
1621
  if (!test_strategy(SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE))
1622
    DBUG_RETURN(false);
1623 1624 1625 1626 1627 1628 1629 1630 1631
  Item **place= optimizer->arguments() + 1;
  THD *thd= join->thd;
  SELECT_LEX *select_lex= join->select_lex;
  Item *subs;

  /*
  */
  DBUG_ASSERT(!substitution);

unknown's avatar
unknown committed
1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645
  /*
    Check if optimization with aggregate min/max possible
    1 There is no aggregate in the subquery
    2 It is not UNION
    3 There is tables
    4 It is not ALL subquery with possible NULLs in the SELECT list
  */
  if (!select_lex->group_list.elements &&                /*1*/
      !select_lex->having &&                             /*1*/
      !select_lex->with_sum_func &&                      /*1*/
      !(select_lex->next_select()) &&                    /*2*/
      select_lex->table_list.elements &&                 /*3*/
      (!select_lex->ref_pointer_array[0]->maybe_null ||  /*4*/
       substype() != Item_subselect::ALL_SUBS))          /*4*/
1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673
  {
    Item_sum_hybrid *item;
    nesting_map save_allow_sum_func;
    if (func->l_op())
    {
      /*
        (ALL && (> || =>)) || (ANY && (< || =<))
        for ALL condition is inverted
      */
      item= new Item_sum_max(*select_lex->ref_pointer_array);
    }
    else
    {
      /*
        (ALL && (< || =<)) || (ANY && (> || =>))
        for ALL condition is inverted
      */
      item= new Item_sum_min(*select_lex->ref_pointer_array);
    }
    if (upper_item)
      upper_item->set_sum_test(item);
    thd->change_item_tree(select_lex->ref_pointer_array, item);
    {
      List_iterator<Item> it(select_lex->item_list);
      it++;
      thd->change_item_tree(it.ref(), item);
    }

Michael Widenius's avatar
Michael Widenius committed
1674 1675 1676 1677 1678 1679 1680
    DBUG_EXECUTE("where",
                 print_where(item, "rewrite with MIN/MAX", QT_ORDINARY););
    if (thd->variables.sql_mode & MODE_ONLY_FULL_GROUP_BY)
    {
      select_lex->set_non_agg_field_used(false);
    }

1681 1682
    save_allow_sum_func= thd->lex->allow_sum_func;
    thd->lex->allow_sum_func|= 1 << thd->lex->current_select->nest_level;
unknown's avatar
unknown committed
1683
    /*
1684 1685 1686
      Item_sum_(max|min) can't substitute other item => we can use 0 as
      reference, also Item_sum_(max|min) can't be fixed after creation, so
      we do not check item->fixed
unknown's avatar
unknown committed
1687
    */
1688 1689 1690 1691 1692 1693 1694 1695 1696
    if (item->fix_fields(thd, 0))
      DBUG_RETURN(true);
    thd->lex->allow_sum_func= save_allow_sum_func; 
    /* we added aggregate function => we have to change statistic */
    count_field_types(select_lex, &join->tmp_table_param, join->all_fields, 
                      0);
    if (join->prepare_stage2())
      DBUG_RETURN(true);
    subs= new Item_singlerow_subselect(select_lex);
unknown's avatar
unknown committed
1697 1698 1699 1700 1701

    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
1702
    set_strategy(SUBS_MAXMIN_INJECTED);
1703 1704 1705 1706 1707 1708 1709
  }
  else
  {
    Item_maxmin_subselect *item;
    subs= item= new Item_maxmin_subselect(thd, this, select_lex, func->l_op());
    if (upper_item)
      upper_item->set_sub_test(item);
unknown's avatar
unknown committed
1710 1711 1712 1713
    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
1714
    set_strategy(SUBS_MAXMIN_ENGINE);
1715
  }
unknown's avatar
unknown committed
1716 1717 1718 1719
  /*
    The swap is needed for expressions of type 'f1 < ALL ( SELECT ....)'
    where we want to evaluate the sub query even if f1 would be null.
  */
unknown's avatar
unknown committed
1720
  subs= func->create_swap(*(optimizer->get_cache()), subs);
1721 1722
  thd->change_item_tree(place, subs);
  if (subs->fix_fields(thd, &subs))
1723
    DBUG_RETURN(true);
1724 1725 1726 1727
  DBUG_ASSERT(subs == (*place)); // There was no substitutions

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

unknown's avatar
unknown committed
1729
  DBUG_RETURN(false);
1730
}
1731

1732

1733 1734 1735 1736 1737 1738 1739 1740 1741 1742
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;
1743 1744
}

1745 1746 1747 1748 1749 1750
bool Item_allany_subselect::is_maxmin_applicable(JOIN *join)
{
  /*
    Check if max/min optimization applicable: It is top item of
    WHERE condition.
  */
unknown's avatar
unknown committed
1751
  return (abort_on_null || (upper_item && upper_item->is_top_level_item())) &&
1752 1753 1754
      !join->select_lex->master_unit()->uncacheable && !func->eqne_op();
}

1755 1756

/**
1757 1758
  Create the predicates needed to transform a single-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1759

1760 1761 1762
  @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
1763

1764 1765
  @details
  The correlated predicates are created as follows:
1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779

  - 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:
        
1780
      SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
1781 1782 1783

    = If we need to distinguish between those:

1784
      SELECT ie FROM ...
1785 1786 1787
        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
        HAVING trigcond(<is_not_null_test>(ie))

unknown's avatar
unknown committed
1788 1789
  @retval false If the new conditions were created successfully
  @retval true  Error
1790 1791
*/

unknown's avatar
unknown committed
1792
bool
1793 1794 1795
Item_in_subselect::create_single_in_to_exists_cond(JOIN * join,
                                                   Item **where_item,
                                                   Item **having_item)
1796 1797
{
  SELECT_LEX *select_lex= join->select_lex;
unknown's avatar
unknown committed
1798
  /*
1799 1800
    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
1801
  */
1802
  Item* join_having= join->having ? join->having : join->tmp_having;
1803

1804
  DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
1805

1806 1807
  *where_item= NULL;
  *having_item= NULL;
1808

1809
  if (join_having || select_lex->with_sum_func ||
1810 1811
      select_lex->group_list.elements)
  {
unknown's avatar
unknown committed
1812
    Item *item= func->create(expr,
1813 1814
                             new Item_ref_null_helper(&select_lex->context,
                                                      this,
unknown's avatar
unknown committed
1815 1816 1817 1818
                                                      select_lex->
                                                      ref_pointer_array,
                                                      (char *)"<ref>",
                                                      this->full_name()));
1819
    if (!abort_on_null && left_expr->maybe_null)
1820 1821 1822
    {
      /* 
        We can encounter "NULL IN (SELECT ...)". Wrap the added condition
1823
        within a trig_cond.
1824
      */
1825
      item= new Item_func_trig_cond(item, get_cond_guard(0));
1826
    }
1827

1828 1829 1830
    if (!join_having)
      item->name= (char*) in_having_cond;
    if (fix_having(item, select_lex))
unknown's avatar
unknown committed
1831
      DBUG_RETURN(true);
1832
    *having_item= item;
1833 1834 1835
  }
  else
  {
unknown's avatar
unknown committed
1836 1837
    Item *item= (Item*) select_lex->item_list.head();

1838
    if (select_lex->table_list.elements)
1839
    {
1840 1841
      Item *having= item;
      Item *orig_item= item;
1842
       
unknown's avatar
unknown committed
1843
      item= func->create(expr, item);
1844
      if (!abort_on_null && orig_item->maybe_null)
unknown's avatar
unknown committed
1845
      {
1846 1847 1848 1849
	having= new Item_is_not_null_test(this, having);
        if (left_expr->maybe_null)
        {
          if (!(having= new Item_func_trig_cond(having,
1850
                                                get_cond_guard(0))))
unknown's avatar
unknown committed
1851
            DBUG_RETURN(true);
1852
        }
1853 1854
        having->name= (char*) in_having_cond;
        if (fix_having(having, select_lex))
unknown's avatar
unknown committed
1855
          DBUG_RETURN(true);
1856
        *having_item= having;
1857

1858
	item= new Item_cond_or(item,
1859
			       new Item_func_isnull(orig_item));
1860
      }
1861
      /* 
1862 1863
        If we may encounter NULL IN (SELECT ...) and care whether subquery
        result is NULL or FALSE, wrap condition in a trig_cond.
1864 1865 1866
      */
      if (!abort_on_null && left_expr->maybe_null)
      {
1867
        if (!(item= new Item_func_trig_cond(item, get_cond_guard(0))))
unknown's avatar
unknown committed
1868
          DBUG_RETURN(true);
1869
      }
1870

1871 1872 1873 1874 1875
      /*
        TODO: figure out why the following is done here in 
        single_value_transformer but there is no corresponding action in
        row_value_transformer?
      */
1876 1877
      item->name= (char *) in_additional_cond;
      if (!item->fixed && item->fix_fields(thd, 0))
unknown's avatar
unknown committed
1878
        DBUG_RETURN(true);
1879
      *where_item= item;
1880 1881 1882
    }
    else
    {
1883
      if (select_lex->master_unit()->is_union())
1884
      {
1885 1886
        Item *new_having=
          func->create(expr,
1887
                       new Item_ref_null_helper(&select_lex->context, this,
1888 1889 1890
                                            select_lex->ref_pointer_array,
                                            (char *)"<no matter>",
                                            (char *)"<result>"));
1891 1892 1893
        if (!abort_on_null && left_expr->maybe_null)
        {
          if (!(new_having= new Item_func_trig_cond(new_having,
1894
                                                    get_cond_guard(0))))
unknown's avatar
unknown committed
1895
            DBUG_RETURN(true);
1896
        }
1897

1898 1899
        new_having->name= (char*) in_having_cond;
        if (fix_having(new_having, select_lex))
unknown's avatar
unknown committed
1900
          DBUG_RETURN(true);
1901
        *having_item= new_having;
1902 1903
      }
      else
1904
        DBUG_ASSERT(false);
1905
    }
unknown's avatar
unknown committed
1906
  }
unknown's avatar
unknown committed
1907

unknown's avatar
unknown committed
1908
  DBUG_RETURN(false);
unknown's avatar
unknown committed
1909
}
unknown's avatar
unknown committed
1910

1911

1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923
/**
  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
1924 1925
  @retval false  The subquery was transformed
  @retval true   Error
1926 1927
*/

unknown's avatar
unknown committed
1928
bool
unknown's avatar
unknown committed
1929
Item_in_subselect::row_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1930
{
unknown's avatar
unknown committed
1931
  SELECT_LEX *select_lex= join->select_lex;
1932
  uint cols_num= left_expr->cols();
1933

unknown's avatar
unknown committed
1934
  DBUG_ENTER("Item_in_subselect::row_value_transformer");
unknown's avatar
unknown committed
1935

1936
  // psergey: duplicated_subselect_card_check
1937
  if (select_lex->item_list.elements != cols_num)
1938
  {
1939
    my_error(ER_OPERAND_COLUMNS, MYF(0), cols_num);
unknown's avatar
unknown committed
1940
    DBUG_RETURN(true);
1941 1942
  }

1943 1944 1945 1946
  /*
    Wrap the current IN predicate in an Item_in_optimizer. The actual
    substitution in the Item tree takes place in Item_subselect::fix_fields.
  */
1947
  if (!substitution)
unknown's avatar
unknown committed
1948
  {
1949
    //first call for this unit
1950
    SELECT_LEX_UNIT *master_unit= select_lex->master_unit();
1951
    substitution= optimizer;
1952

1953 1954
    SELECT_LEX *current= thd->lex->current_select;
    thd->lex->current_select= current->return_after_parsing();
1955
    //optimizer never use Item **ref => we can pass 0 as parameter
1956
    if (!optimizer || optimizer->fix_left(thd, 0))
1957
    {
unknown's avatar
unknown committed
1958
      thd->lex->current_select= current;
unknown's avatar
unknown committed
1959
      DBUG_RETURN(true);
1960
    }
1961

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

unknown's avatar
unknown committed
1965
    thd->lex->current_select= current;
unknown's avatar
unknown committed
1966 1967 1968 1969 1970 1971 1972 1973 1974
    /*
      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;
1975 1976
  }

unknown's avatar
unknown committed
1977
  DBUG_RETURN(false);
1978 1979 1980 1981
}


/**
1982 1983
  Create the predicates needed to transform a multi-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1984

1985
  @details
unknown's avatar
unknown committed
1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020
  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)
2021 2022 2023 2024 2025

  @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
2026 2027
  @retval false  If the new conditions were created successfully
  @retval true   Error
2028 2029
*/

unknown's avatar
unknown committed
2030
bool
2031 2032 2033
Item_in_subselect::create_row_in_to_exists_cond(JOIN * join,
                                                Item **where_item,
                                                Item **having_item)
2034 2035 2036
{
  SELECT_LEX *select_lex= join->select_lex;
  uint cols_num= left_expr->cols();
2037
  /*
2038 2039
    The non-transformed HAVING clause of 'join' may be stored in two ways
    during JOIN::optimize: this->tmp_having= this->having; this->having= 0;
2040 2041 2042
  */
  Item* join_having= join->having ? join->having : join->tmp_having;
  bool is_having_used= (join_having || select_lex->with_sum_func ||
2043 2044 2045
                        select_lex->group_list.first ||
                        !select_lex->table_list.elements);

2046
  DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
2047 2048 2049

  *where_item= NULL;
  *having_item= NULL;
2050

2051
  if (is_having_used)
unknown's avatar
unknown committed
2052
  {
unknown's avatar
unknown committed
2053
    /* TODO: say here explicitly if the order of AND parts matters or not. */
2054 2055
    Item *item_having_part2= 0;
    for (uint i= 0; i < cols_num; i++)
unknown's avatar
unknown committed
2056
    {
2057
      DBUG_ASSERT((left_expr->fixed &&
2058

2059
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
2060 2061 2062
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
2063
      if (select_lex->ref_pointer_array[i]->
2064
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
2065
        DBUG_RETURN(true);
2066 2067
      Item *item_eq=
        new Item_func_eq(new
unknown's avatar
unknown committed
2068 2069 2070 2071 2072
                         Item_ref(&select_lex->context,
                                  (*optimizer->get_cache())->
                                  addr(i),
                                  (char *)"<no matter>",
                                  (char *)in_left_expr_name),
2073
                         new
unknown's avatar
unknown committed
2074 2075 2076
                         Item_ref(&select_lex->context,
                                  select_lex->ref_pointer_array + i,
                                  (char *)"<no matter>",
unknown's avatar
unknown committed
2077
                                  (char *)"<list ref>"));
2078 2079
      Item *item_isnull=
        new Item_func_isnull(new
unknown's avatar
unknown committed
2080 2081 2082
                             Item_ref(&select_lex->context,
                                      select_lex->ref_pointer_array+i,
                                      (char *)"<no matter>",
unknown's avatar
unknown committed
2083
                                      (char *)"<list ref>"));
2084
      Item *col_item= new Item_cond_or(item_eq, item_isnull);
unknown's avatar
unknown committed
2085
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
2086 2087
      {
        if (!(col_item= new Item_func_trig_cond(col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2088
          DBUG_RETURN(true);
2089
      }
2090 2091
      *having_item= and_items(*having_item, col_item);

2092 2093 2094 2095 2096 2097 2098
      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
2099
      if (!abort_on_null && left_expr->element_index(i)->maybe_null)
2100 2101 2102
      {
        if (!(item_nnull_test= 
              new Item_func_trig_cond(item_nnull_test, get_cond_guard(i))))
unknown's avatar
unknown committed
2103
          DBUG_RETURN(true);
2104 2105
      }
      item_having_part2= and_items(item_having_part2, item_nnull_test);
2106
      item_having_part2->top_level_item();
unknown's avatar
unknown committed
2107
    }
2108
    *having_item= and_items(*having_item, item_having_part2);
2109
  }
2110
  else
2111
  {
2112 2113 2114
    for (uint i= 0; i < cols_num; i++)
    {
      Item *item, *item_isnull;
2115
      DBUG_ASSERT((left_expr->fixed &&
2116
                  select_lex->ref_pointer_array[i]->fixed) ||
unknown's avatar
unknown committed
2117 2118 2119
                  (select_lex->ref_pointer_array[i]->type() == REF_ITEM &&
                   ((Item_ref*)(select_lex->ref_pointer_array[i]))->ref_type() ==
                    Item_ref::OUTER_REF));
2120
      if (select_lex->ref_pointer_array[i]->
2121
          check_cols(left_expr->element_index(i)->cols()))
unknown's avatar
unknown committed
2122
        DBUG_RETURN(true);
2123 2124
      item=
        new Item_func_eq(new
unknown's avatar
unknown committed
2125 2126
                         Item_direct_ref(&select_lex->context,
                                         (*optimizer->get_cache())->
2127 2128 2129 2130
                                         addr(i),
                                         (char *)"<no matter>",
                                         (char *)in_left_expr_name),
                         new
unknown's avatar
unknown committed
2131 2132 2133 2134
                         Item_direct_ref(&select_lex->context,
                                         select_lex->
                                         ref_pointer_array+i,
                                         (char *)"<no matter>",
unknown's avatar
unknown committed
2135
                                         (char *)"<list ref>"));
2136 2137
      if (!abort_on_null)
      {
2138 2139 2140 2141 2142 2143 2144 2145 2146
        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>"));
        
        
2147 2148
        item_isnull= new
          Item_func_isnull(new
unknown's avatar
unknown committed
2149 2150 2151 2152
                           Item_direct_ref(&select_lex->context,
                                           select_lex->
                                           ref_pointer_array+i,
                                           (char *)"<no matter>",
unknown's avatar
unknown committed
2153
                                           (char *)"<list ref>"));
2154
        item= new Item_cond_or(item, item_isnull);
2155 2156 2157 2158
        /* 
          TODO: why we create the above for cases where the right part
                cant be NULL?
        */
unknown's avatar
unknown committed
2159
        if (left_expr->element_index(i)->maybe_null)
2160 2161
        {
          if (!(item= new Item_func_trig_cond(item, get_cond_guard(i))))
unknown's avatar
unknown committed
2162
            DBUG_RETURN(true);
2163 2164
          if (!(having_col_item= 
                  new Item_func_trig_cond(having_col_item, get_cond_guard(i))))
unknown's avatar
unknown committed
2165
            DBUG_RETURN(true);
2166
        }
2167
        *having_item= and_items(*having_item, having_col_item);
2168
      }
2169
      *where_item= and_items(*where_item, item);
2170
    }
unknown's avatar
unknown committed
2171
  }
2172

2173
  if (*where_item)
2174
  {
2175
    if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
unknown's avatar
unknown committed
2176
      DBUG_RETURN(true);
2177
    (*where_item)->top_level_item();
2178
  }
unknown's avatar
unknown committed
2179

2180
  if (*having_item)
2181
  {
2182 2183 2184
    if (!join_having)
      (*having_item)->name= (char*) in_having_cond;
    if (fix_having(*having_item, select_lex))
unknown's avatar
unknown committed
2185
      DBUG_RETURN(true);
2186
    (*having_item)->top_level_item();
2187
  }
unknown's avatar
unknown committed
2188

unknown's avatar
unknown committed
2189
  DBUG_RETURN(false);
unknown's avatar
unknown committed
2190 2191
}

2192

unknown's avatar
unknown committed
2193
bool
unknown's avatar
unknown committed
2194
Item_in_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2195
{
2196
  return select_in_like_transformer(join);
2197 2198 2199
}


unknown's avatar
unknown committed
2200
/**
2201 2202
  Create the predicates needed to transform an IN/ALL/ANY subselect into a
  correlated EXISTS via predicate injection.
2203

2204
  @param join_arg  Join object of the subquery.
2205

2206 2207 2208 2209
  @retval FALSE  ok
  @retval TRUE   error
*/

2210 2211
bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
{
unknown's avatar
unknown committed
2212
  bool res;
2213 2214 2215 2216

  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE ||
              engine->engine_type() == subselect_engine::UNION_ENGINE);
  /*
2217
    TODO: the call to init_cond_guards allocates and initializes an
2218 2219 2220
    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.
2221
    If the dependency is removed, the call can be moved to a later phase.
2222 2223 2224 2225 2226 2227 2228 2229 2230 2231
  */
  init_cond_guards();
  if (left_expr->cols() == 1)
    res= create_single_in_to_exists_cond(join_arg,
                                         &(join_arg->in_to_exists_where),
                                         &(join_arg->in_to_exists_having));
  else
    res= create_row_in_to_exists_cond(join_arg,
                                      &(join_arg->in_to_exists_where),
                                      &(join_arg->in_to_exists_having));
2232

2233 2234 2235 2236
  /*
    The IN=>EXISTS transformation makes non-correlated subqueries correlated.
  */
  join_arg->select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
2237 2238 2239 2240 2241 2242 2243 2244 2245
  /*
    The uncacheable property controls a number of actions, e.g. whether to
    save/restore (via init_save_join_tab/restore_tmp) the original JOIN for
    plans with a temp table where the original JOIN was overriden by
    make_simple_join. The UNCACHEABLE_EXPLAIN is ignored by EXPLAIN, thus
    non-correlated subqueries will not appear as such to EXPLAIN.
  */
  join_arg->select_lex->master_unit()->uncacheable|= UNCACHEABLE_EXPLAIN;
  join_arg->select_lex->uncacheable|= UNCACHEABLE_EXPLAIN;
unknown's avatar
unknown committed
2246
  return (res);
2247 2248 2249
}


2250 2251 2252 2253 2254 2255 2256 2257 2258 2259
/**
  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
*/

2260
bool Item_in_subselect::inject_in_to_exists_cond(JOIN *join_arg)
2261
{
2262 2263 2264
  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;
2265

2266 2267 2268 2269
  DBUG_ENTER("Item_in_subselect::inject_in_to_exists_cond");

  if (where_item)
  {
unknown's avatar
unknown committed
2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287
    List<Item> *and_args= NULL;
    /*
      If the top-level Item of the WHERE clause is an AND, detach the multiple
      equality list that was attached to the end of the AND argument list by
      build_equal_items_for_cond(). The multiple equalities must be detached
      because fix_fields merges lower level AND arguments into the upper AND.
      As a result, the arguments from lower-level ANDs are concatenated after
      the multiple equalities. When the multiple equality list is treated as
      such, it turns out that it contains non-Item_equal object which is wrong.
    */
    if (join_arg->conds && join_arg->conds->type() == Item::COND_ITEM &&
        ((Item_cond*) join_arg->conds)->functype() == Item_func::COND_AND_FUNC)
    {
      and_args= ((Item_cond*) join_arg->conds)->argument_list();
      if (join_arg->cond_equal)
        and_args->disjoin((List<Item> *) &join_arg->cond_equal->current_level);
    }

2288 2289 2290
    where_item= and_items(join_arg->conds, where_item);
    if (!where_item->fixed && where_item->fix_fields(thd, 0))
      DBUG_RETURN(true);
2291
    // TIMOUR TODO: call optimize_cond() for the new where clause
2292 2293 2294
    thd->change_item_tree(&select_lex->where, where_item);
    select_lex->where->top_level_item();
    join_arg->conds= select_lex->where;
unknown's avatar
unknown committed
2295 2296 2297 2298 2299 2300

    /* Attach back the list of multiple equalities to the new top-level AND. */
    if (and_args && join_arg->cond_equal)
    {
      /* The argument list of the top-level AND may change after fix fields. */
      and_args= ((Item_cond*) join_arg->conds)->argument_list();
2301 2302 2303 2304 2305 2306
      List_iterator<Item_equal> li(join_arg->cond_equal->current_level);
      Item_equal *elem;
      while ((elem= li++))
      {
        and_args->push_back(elem);
      }
unknown's avatar
unknown committed
2307
    }
2308
  }
2309

2310 2311 2312 2313 2314 2315
  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);
2316
    // TIMOUR TODO: call optimize_cond() for the new having clause
2317 2318 2319 2320
    thd->change_item_tree(&select_lex->having, having_item);
    select_lex->having->top_level_item();
    join_arg->having= select_lex->having;
  }
2321 2322 2323
  join_arg->thd->change_item_tree(&unit->global_parameters->select_limit,
                                  new Item_int((int32) 1));
  unit->select_limit_cnt= 1;
2324

2325
  DBUG_RETURN(false);
2326 2327 2328
}


unknown's avatar
unknown committed
2329
/**
unknown's avatar
unknown committed
2330
  Prepare IN/ALL/ANY/SOME subquery transformation and call the appropriate
unknown's avatar
unknown committed
2331
  transformation function.
2332

unknown's avatar
unknown committed
2333 2334
  @param join    JOIN object of transforming subquery

2335 2336
  @notes
  To decide which transformation procedure (scalar or row) applicable here
unknown's avatar
unknown committed
2337 2338
  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
2339 2340
  underlying transformation methods.

unknown's avatar
unknown committed
2341 2342
  @retval  false  OK
  @retval  true   Error
2343 2344
*/

unknown's avatar
unknown committed
2345
bool
2346
Item_in_subselect::select_in_like_transformer(JOIN *join)
2347
{
unknown's avatar
unknown committed
2348
  Query_arena *arena, backup;
2349
  SELECT_LEX *current= thd->lex->current_select;
2350
  const char *save_where= thd->where;
unknown's avatar
unknown committed
2351
  bool trans_res= true;
2352 2353 2354
  bool result;

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

unknown's avatar
unknown committed
2356 2357 2358 2359 2360 2361
  /*
    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())
2362
  {
unknown's avatar
unknown committed
2363
    if (sl->join)
2364
    {
unknown's avatar
unknown committed
2365 2366
      sl->join->order= 0;
      sl->join->skip_sort_order= 1;
2367 2368 2369
    }
  }

2370
  if (changed)
unknown's avatar
unknown committed
2371
    DBUG_RETURN(false);
2372 2373 2374 2375 2376 2377 2378

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

2380
    //psergey: he means degenerate cases like "... IN (SELECT 1)"
2381 2382 2383
  */
  if (!optimizer)
  {
unknown's avatar
unknown committed
2384
    arena= thd->activate_stmt_arena_if_needed(&backup);
2385 2386
    result= (!(optimizer= new Item_in_optimizer(left_expr, this)));
    if (arena)
unknown's avatar
unknown committed
2387
      thd->restore_active_arena(arena, &backup);
2388 2389 2390 2391
    if (result)
      goto err;
  }

2392
  thd->lex->current_select= current->return_after_parsing();
2393
  result= (!left_expr->fixed &&
2394
           left_expr->fix_fields(thd, optimizer->arguments()));
2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 2407 2408
  /* 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)
  */
2409
  arena= thd->activate_stmt_arena_if_needed(&backup);
unknown's avatar
unknown committed
2410
  if (left_expr->cols() == 1)
unknown's avatar
unknown committed
2411
    trans_res= single_value_transformer(join);
2412 2413 2414 2415 2416
  else
  {
    /* we do not support row operation for ALL/ANY/SOME */
    if (func != &eq_creator)
    {
unknown's avatar
unknown committed
2417
      if (arena)
unknown's avatar
unknown committed
2418
        thd->restore_active_arena(arena, &backup);
2419
      my_error(ER_OPERAND_COLUMNS, MYF(0), 1);
unknown's avatar
unknown committed
2420
      DBUG_RETURN(true);
2421
    }
unknown's avatar
unknown committed
2422
    trans_res= row_value_transformer(join);
2423 2424
  }
  if (arena)
unknown's avatar
unknown committed
2425
    thd->restore_active_arena(arena, &backup);
2426 2427
err:
  thd->where= save_where;
unknown's avatar
unknown committed
2428
  DBUG_RETURN(trans_res);
unknown's avatar
unknown committed
2429 2430
}

2431

2432
void Item_in_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2433
{
unknown's avatar
unknown committed
2434
  if (test_strategy(SUBS_IN_TO_EXISTS))
2435
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2436 2437
  else
  {
2438
    left_expr->print(str, query_type);
2439
    str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
2440
  }
2441
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2442 2443 2444
}


2445
bool Item_in_subselect::fix_fields(THD *thd_arg, Item **ref)
2446
{
2447 2448
  uint outer_cols_num;
  List<Item> *inner_cols;
2449

unknown's avatar
unknown committed
2450
  if (test_strategy(SUBS_SEMI_JOIN))
2451 2452
    return !( (*ref)= new Item_int(1));

2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497
  /*
    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
2498
  if ((thd_arg->lex->context_analysis_only & CONTEXT_ANALYSIS_ONLY_VIEW) &&
Michael Widenius's avatar
Michael Widenius committed
2499
      left_expr && !left_expr->fixed &&
2500 2501 2502 2503 2504 2505
      left_expr->fix_fields(thd_arg, &left_expr))
    return TRUE;
  if (Item_subselect::fix_fields(thd_arg, ref))
    return TRUE;
  fixed= TRUE;
  return FALSE;
2506 2507
}

2508

2509 2510 2511 2512
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);
2513
  used_tables_cache |= left_expr->used_tables();
2514 2515 2516 2517 2518 2519 2520 2521
}

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

2523

2524
/**
2525 2526
  Try to create and initialize an engine to compute a subselect via
  materialization.
2527 2528

  @details
2529 2530 2531 2532 2533
  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,
2534 2535 2536 2537 2538 2539

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

2540
bool Item_in_subselect::setup_mat_engine()
2541
{
2542 2543
  subselect_hash_sj_engine       *mat_engine= NULL;
  subselect_single_select_engine *select_engine;
2544

2545
  DBUG_ENTER("Item_in_subselect::setup_mat_engine");
2546

2547 2548 2549 2550 2551 2552 2553
  /*
    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;
2554

2555 2556 2557
  /* Create/initialize execution objects. */
  if (!(mat_engine= new subselect_hash_sj_engine(thd, this, select_engine)))
    DBUG_RETURN(TRUE);
2558

Sergey Petrunya's avatar
Sergey Petrunya committed
2559 2560
  if (mat_engine->init(&select_engine->join->fields_list,
                       engine->get_identifier()))
2561
    DBUG_RETURN(TRUE);
2562

2563 2564
  engine= mat_engine;
  DBUG_RETURN(FALSE);
2565 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 2581 2582 2583 2584 2585 2586 2587 2588
}


/**
  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.
  */ 
2589
  if (!outer_join || !outer_join->table_count || !outer_join->tables_list)
2590 2591 2592 2593 2594 2595 2596 2597 2598
    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),
2599
                                                 FALSE);
2600 2601 2602 2603 2604 2605 2606
    if (!cur_item_cache || left_expr_cache->push_front(cur_item_cache))
      return TRUE;
  }
  return FALSE;
}


2607
bool Item_in_subselect::init_cond_guards()
2608
{
2609 2610 2611 2612 2613 2614 2615 2616 2617
  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;
2618 2619 2620
}


unknown's avatar
unknown committed
2621
bool
unknown's avatar
unknown committed
2622
Item_allany_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2623
{
2624
  DBUG_ENTER("Item_allany_subselect::select_transformer");
unknown's avatar
unknown committed
2625
  DBUG_ASSERT((in_strategy & ~(SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE |
unknown's avatar
unknown committed
2626
                               SUBS_IN_TO_EXISTS | SUBS_STRATEGY_CHOSEN)) == 0);
2627 2628
  if (upper_item)
    upper_item->show= 1;
2629
  DBUG_RETURN(select_in_like_transformer(join));
unknown's avatar
unknown committed
2630 2631
}

unknown's avatar
unknown committed
2632

2633
void Item_allany_subselect::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
2634
{
unknown's avatar
unknown committed
2635
  if (test_strategy(SUBS_IN_TO_EXISTS))
2636
    str->append(STRING_WITH_LEN("<exists>"));
unknown's avatar
unknown committed
2637 2638
  else
  {
2639
    left_expr->print(str, query_type);
unknown's avatar
unknown committed
2640
    str->append(' ');
unknown's avatar
unknown committed
2641 2642
    str->append(func->symbol(all));
    str->append(all ? " all " : " any ", 5);
unknown's avatar
unknown committed
2643
  }
2644
  Item_subselect::print(str, query_type);
unknown's avatar
unknown committed
2645 2646 2647
}


2648 2649 2650 2651 2652 2653 2654 2655
void subselect_engine::set_thd(THD *thd_arg)
{
  thd= thd_arg;
  if (result)
    result->set_thd(thd_arg);
}


2656
subselect_single_select_engine::
unknown's avatar
unknown committed
2657
subselect_single_select_engine(THD *thd_arg, st_select_lex *select,
2658
			       select_result_interceptor *result_arg,
2659
			       Item_subselect *item_arg)
unknown's avatar
unknown committed
2660
  :subselect_engine(thd_arg, item_arg, result_arg),
Michael Widenius's avatar
Michael Widenius committed
2661
   prepared(0), executed(0), optimize_error(0),
2662
   select_lex(select), join(0)
unknown's avatar
unknown committed
2663
{
2664
  select_lex->master_unit()->item= item_arg;
unknown's avatar
unknown committed
2665 2666
}

2667 2668 2669 2670
int subselect_single_select_engine::get_identifier()
{
  return select_lex->select_number; 
}
unknown's avatar
unknown committed
2671

unknown's avatar
unknown committed
2672 2673
void subselect_single_select_engine::cleanup()
{
unknown's avatar
unknown committed
2674
  DBUG_ENTER("subselect_single_select_engine::cleanup");
Michael Widenius's avatar
Michael Widenius committed
2675
  prepared= executed= optimize_error= 0;
2676
  join= 0;
2677
  result->cleanup();
2678
  select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
unknown's avatar
unknown committed
2679
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2680
}
2681

unknown's avatar
unknown committed
2682 2683 2684 2685 2686

void subselect_union_engine::cleanup()
{
  DBUG_ENTER("subselect_union_engine::cleanup");
  unit->reinit_exec_mechanism();
2687
  result->cleanup();
2688 2689 2690
  unit->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
  for (SELECT_LEX *sl= unit->first_select(); sl; sl= sl->next_select())
    sl->uncacheable&= ~UNCACHEABLE_DEPENDENT_INJECTED;
unknown's avatar
unknown committed
2691
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2692
}
2693

unknown's avatar
unknown committed
2694

2695 2696 2697 2698 2699 2700
bool subselect_union_engine::is_executed() const
{
  return unit->executed;
}


2701 2702 2703 2704 2705 2706 2707 2708 2709 2710 2711 2712 2713 2714 2715 2716 2717 2718 2719 2720 2721
/*
  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);
}

2722

unknown's avatar
unknown committed
2723 2724 2725
void subselect_uniquesubquery_engine::cleanup()
{
  DBUG_ENTER("subselect_uniquesubquery_engine::cleanup");
2726 2727 2728
  /* 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
2729 2730 2731 2732
  DBUG_VOID_RETURN;
}


unknown's avatar
unknown committed
2733
subselect_union_engine::subselect_union_engine(THD *thd_arg, st_select_lex_unit *u,
2734
					       select_result_interceptor *result_arg,
2735
					       Item_subselect *item_arg)
unknown's avatar
unknown committed
2736
  :subselect_engine(thd_arg, item_arg, result_arg)
unknown's avatar
unknown committed
2737 2738
{
  unit= u;
2739
  if (!result_arg)				//out of memory
2740
    current_thd->fatal_error();
2741
  unit->item= item_arg;
unknown's avatar
unknown committed
2742 2743
}

2744

2745 2746 2747 2748
/**
  Create and prepare the JOIN object that represents the query execution
  plan for the subquery.

2749
  @details
2750 2751 2752 2753 2754 2755 2756 2757 2758 2759 2760 2761 2762 2763 2764 2765 2766 2767 2768 2769 2770
  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
2771 2772
int subselect_single_select_engine::prepare()
{
unknown's avatar
unknown committed
2773 2774
  if (prepared)
    return 0;
2775 2776 2777 2778
  if (select_lex->join)
  {
    select_lex->cleanup();
  }
2779 2780
  join= new JOIN(thd, select_lex->item_list,
		 select_lex->options | SELECT_NO_UNLOCK, result);
2781 2782
  if (!join || !result)
  {
2783
    thd->fatal_error();				//out of memory
2784 2785
    return 1;
  }
unknown's avatar
unknown committed
2786
  prepared= 1;
2787 2788
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
unknown's avatar
unknown committed
2789
  if (join->prepare(&select_lex->ref_pointer_array,
2790
		    select_lex->table_list.first,
unknown's avatar
unknown committed
2791
		    select_lex->with_wild,
unknown's avatar
unknown committed
2792
		    select_lex->where,
unknown's avatar
unknown committed
2793 2794
		    select_lex->order_list.elements +
		    select_lex->group_list.elements,
2795 2796
		    select_lex->order_list.first,
		    select_lex->group_list.first,
unknown's avatar
unknown committed
2797
		    select_lex->having,
2798
		    NULL, select_lex,
2799
		    select_lex->master_unit()))
unknown's avatar
unknown committed
2800
    return 1;
2801
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2802 2803 2804 2805 2806
  return 0;
}

int subselect_union_engine::prepare()
{
2807
  return unit->prepare(thd, result, SELECT_NO_UNLOCK);
unknown's avatar
unknown committed
2808 2809
}

2810
int subselect_uniquesubquery_engine::prepare()
2811
{
2812 2813
  /* Should never be called. */
  DBUG_ASSERT(FALSE);
2814 2815 2816
  return 1;
}

2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838

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


2839 2840 2841 2842 2843
/* 
 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)
2844
{
2845
  Item *sel_item;
2846
  List_iterator_fast<Item> li(item_list);
2847
  res_type= STRING_RESULT;
2848
  res_field_type= MYSQL_TYPE_VAR_STRING;
2849 2850 2851 2852
  for (uint i= 0; (sel_item= li++); i++)
  {
    item->max_length= sel_item->max_length;
    res_type= sel_item->result_type();
2853
    res_field_type= sel_item->field_type();
2854
    item->decimals= sel_item->decimals;
2855
    item->unsigned_flag= sel_item->unsigned_flag;
unknown's avatar
unknown committed
2856
    maybe_null= sel_item->maybe_null;
2857
    if (!(row[i]= Item_cache::get_cache(sel_item)))
2858
      return;
2859
    row[i]->setup(sel_item);
2860
 //psergey-backport-timours:   row[i]->store(sel_item);
2861
  }
2862
  if (item_list.elements > 1)
2863
    res_type= ROW_RESULT;
2864 2865
}

2866
void subselect_single_select_engine::fix_length_and_dec(Item_cache **row)
2867
{
2868
  DBUG_ASSERT(row || select_lex->item_list.elements==1);
2869
  set_row(select_lex->item_list, row);
2870
  item->collation.set(row[0]->collation);
unknown's avatar
unknown committed
2871 2872
  if (cols() != 1)
    maybe_null= 0;
2873 2874 2875 2876 2877 2878 2879
}

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)
2880
  {
2881
    set_row(unit->types, row);
2882 2883
    item->collation.set(row[0]->collation);
  }
2884 2885
  else
  {
2886 2887 2888
    bool maybe_null_saved= maybe_null;
    set_row(unit->types, row);
    maybe_null= maybe_null_saved;
2889 2890
  }
}
unknown's avatar
unknown committed
2891

2892
void subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
2893 2894 2895 2896 2897
{
  //this never should be called
  DBUG_ASSERT(0);
}

2898 2899 2900 2901
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);

2902
int subselect_single_select_engine::exec()
unknown's avatar
unknown committed
2903 2904
{
  DBUG_ENTER("subselect_single_select_engine::exec");
2905 2906 2907 2908

  if (optimize_error)
    DBUG_RETURN(1);

unknown's avatar
unknown committed
2909 2910 2911
  char const *save_where= thd->where;
  SELECT_LEX *save_select= thd->lex->current_select;
  thd->lex->current_select= select_lex;
Michael Widenius's avatar
Michael Widenius committed
2912

2913
  if (!join->optimized)
unknown's avatar
unknown committed
2914
  {
2915 2916 2917
    SELECT_LEX_UNIT *unit= select_lex->master_unit();

    unit->set_limit(unit->global_parameters);
unknown's avatar
unknown committed
2918 2919
    if (join->optimize())
    {
unknown's avatar
unknown committed
2920
      thd->where= save_where;
Michael Widenius's avatar
Michael Widenius committed
2921
      executed= optimize_error= 1;
unknown's avatar
unknown committed
2922
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2923
      DBUG_RETURN(join->error ? join->error : 1);
unknown's avatar
unknown committed
2924
    }
unknown's avatar
unknown committed
2925
    if (!select_lex->uncacheable && thd->lex->describe && 
2926
        !(join->select_options & SELECT_DESCRIBE))
unknown's avatar
unknown committed
2927
    {
2928 2929 2930
      item->update_used_tables();
      if (item->const_item())
      {
2931 2932 2933 2934 2935 2936 2937 2938
        /*
          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;
2939 2940 2941 2942 2943 2944
        /*
          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.
        */
2945
        if (join->need_tmp && join->init_save_join_tab())
2946 2947
          DBUG_RETURN(1);                        /* purecov: inspected */
      }
unknown's avatar
unknown committed
2948
    }
2949 2950 2951 2952
    if (item->engine_changed)
    {
      DBUG_RETURN(1);
    }
unknown's avatar
unknown committed
2953
  }
2954 2955 2956
  if (select_lex->uncacheable &&
      select_lex->uncacheable != UNCACHEABLE_EXPLAIN
      && executed)
unknown's avatar
unknown committed
2957 2958
  {
    if (join->reinit())
2959
    {
unknown's avatar
unknown committed
2960 2961
      thd->where= save_where;
      thd->lex->current_select= save_select;
unknown's avatar
unknown committed
2962
      DBUG_RETURN(1);
2963
    }
2964
    item->reset();
unknown's avatar
unknown committed
2965 2966 2967 2968
    item->assigned((executed= 0));
  }
  if (!executed)
  {
2969
    item->reset_value_registration();
2970 2971 2972
    JOIN_TAB *changed_tabs[MAX_TABLES];
    JOIN_TAB **last_changed_tab= changed_tabs;
    if (item->have_guarded_conds())
2973 2974
    {
      /*
2975
        For at least one of the pushed predicates the following is true:
2976 2977 2978 2979
        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.
      */
2980 2981
      for (JOIN_TAB *tab= first_linear_tab(join, WITHOUT_CONST_TABLES); tab;
           tab= next_linear_tab(join, tab, WITH_BUSH_ROOTS))
2982
      {
2983
        if (tab && tab->keyuse)
2984
        {
2985 2986 2987 2988 2989 2990
          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 */
2991 2992
              tab->save_read_first_record= tab->read_first_record;
              tab->save_read_record= tab->read_record.read_record;
2993 2994 2995 2996
              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;
2997
              tab->read_record.unlock_row= rr_unlock_row;
2998 2999 3000 3001
              *(last_changed_tab++)= tab;
              break;
            }
          }
3002 3003 3004 3005
        }
      }
    }
    
unknown's avatar
unknown committed
3006
    join->exec();
3007

3008 3009
    /* Enable the optimizations back */
    for (JOIN_TAB **ptab= changed_tabs; ptab != last_changed_tab; ptab++)
3010
    {
3011 3012 3013
      JOIN_TAB *tab= *ptab;
      tab->read_record.record= 0;
      tab->read_record.ref_length= 0;
3014 3015
      tab->read_first_record= tab->save_read_first_record; 
      tab->read_record.read_record= tab->save_read_record;
3016
    }
unknown's avatar
unknown committed
3017
    executed= 1;
unknown's avatar
unknown committed
3018 3019
    thd->where= save_where;
    thd->lex->current_select= save_select;
3020
    DBUG_RETURN(join->error || thd->is_fatal_error || thd->is_error());
unknown's avatar
unknown committed
3021
  }
unknown's avatar
unknown committed
3022 3023
  thd->where= save_where;
  thd->lex->current_select= save_select;
unknown's avatar
unknown committed
3024 3025 3026
  DBUG_RETURN(0);
}

3027
int subselect_union_engine::exec()
unknown's avatar
unknown committed
3028
{
unknown's avatar
unknown committed
3029
  char const *save_where= thd->where;
3030
  int res= unit->exec();
unknown's avatar
unknown committed
3031
  thd->where= save_where;
3032
  return res;
unknown's avatar
unknown committed
3033 3034
}

3035

3036
/*
3037
  Search for at least one row satisfying select condition
3038 3039 3040 3041 3042 3043 3044 3045
 
  SYNOPSIS
    subselect_uniquesubquery_engine::scan_table()

  DESCRIPTION
    Scan the table using sequential access until we find at least one row
    satisfying select condition.
    
3046 3047
    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.
3048 3049 3050 3051 3052 3053 3054

  RETURN
    FALSE - OK
    TRUE  - Error
*/

int subselect_uniquesubquery_engine::scan_table()
3055 3056 3057
{
  int error;
  TABLE *table= tab->table;
3058 3059 3060 3061 3062
  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");

  if (table->file->inited)
    table->file->ha_index_end();
 
3063 3064
  if (table->file->ha_rnd_init_with_error(1))
    DBUG_RETURN(1);
3065 3066 3067 3068
  table->file->extra_opt(HA_EXTRA_CACHE,
                         current_thd->variables.read_buff_size);
  table->null_row= 0;
  for (;;)
3069
  {
3070
    error=table->file->ha_rnd_next(table->record[0]);
3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086
    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;
      }
3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108
    }

    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
3109 3110 3111 3112 3113 3114 3115 3116 3117 3118 3119 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133
    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.

3134 3135

  RETURN
unknown's avatar
unknown committed
3136 3137 3138 3139 3140
    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.
3141 3142 3143 3144 3145 3146 3147
*/

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++)
3148
  {
3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159
    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
3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183
    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)
3184
    {
unknown's avatar
unknown committed
3185 3186 3187 3188
      /*
       Error converting the left IN operand to the column type of the right
       IN operand. 
      */
3189
      tab->table->status= STATUS_NOT_FOUND;
unknown's avatar
unknown committed
3190
      break;
3191
    }
3192
  }
3193 3194 3195
  DBUG_RETURN(0);
}

3196

3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246
/*
  @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;
}


3247 3248 3249 3250 3251
/*
  Execute subselect

  SYNOPSIS
    subselect_uniquesubquery_engine::exec()
3252

3253 3254 3255 3256 3257 3258 3259 3260 3261 3262
  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)
3263
    the caller doesn't distinguish between NULL and FALSE result and we just
3264
    return FALSE. 
3265 3266 3267 3268 3269
    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.
3270 3271 3272 3273 3274 3275
  NOTE
    
  RETURN
    FALSE - ok
    TRUE  - an error occured while scanning
*/
3276

3277
int subselect_uniquesubquery_engine::exec()
3278 3279 3280 3281
{
  DBUG_ENTER("subselect_uniquesubquery_engine::exec");
  int error;
  TABLE *table= tab->table;
3282
  empty_result_set= TRUE;
unknown's avatar
unknown committed
3283
  table->status= 0;
3284 3285 3286
 
  /* TODO: change to use of 'full_scan' here? */
  if (copy_ref_key())
3287 3288 3289 3290 3291
  {
    /*
      TIMOUR: copy_ref_key() == 1 means NULL result, not error, why return 1?
      Check who reiles on this result.
    */
3292
    DBUG_RETURN(1);
3293
  }
unknown's avatar
unknown committed
3294 3295 3296 3297 3298 3299 3300 3301 3302
  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);
  }
3303

3304 3305 3306
  if (!tab->preread_init_done && tab->preread_init())
    DBUG_RETURN(1);

3307 3308 3309
  if (null_keypart)
    DBUG_RETURN(scan_table());
 
3310
  if (!table->file->inited)
3311
    table->file->ha_index_init(tab->ref.key, 0);
3312 3313 3314 3315 3316
  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);
3317 3318
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3319
    error= report_error(table, error);
3320 3321
  else
  {
3322 3323
    error= 0;
    table->null_row= 0;
3324 3325 3326 3327 3328 3329 3330
    if (!table->status && (!cond || cond->val_int()))
    {
      ((Item_in_subselect *) item)->value= 1;
      empty_result_set= FALSE;
    }
    else
      ((Item_in_subselect *) item)->value= 0;
3331
  }
3332

3333
  DBUG_RETURN(error != 0);
3334 3335
}

3336

3337
/*
3338
  TIMOUR: write comment
3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354
*/

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));
3355 3356

  if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3357
  {
3358 3359 3360 3361 3362 3363
    /*
      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);
3364 3365
  }

3366 3367 3368 3369 3370 3371 3372
  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);
3373 3374 3375 3376
}



3377
subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
3378
{
3379
  /* Tell handler we don't need the index anymore */
3380 3381
  //psergey-merge-todo: the following was gone in 6.0:
 //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
3382 3383
}

3384

3385 3386 3387 3388
/*
  Index-lookup subselect 'engine' - run the subquery

  SYNOPSIS
3389
    subselect_indexsubquery_engine:exec()
3390 3391 3392
      full_scan 

  DESCRIPTION
3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425
    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.
3426

3427 3428 3429 3430
    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.
3431 3432 3433 3434 3435 3436

  RETURN
    0
    1
*/

3437
int subselect_indexsubquery_engine::exec()
3438
{
3439
  DBUG_ENTER("subselect_indexsubquery_engine");
3440
  int error;
3441
  bool null_finding= 0;
3442
  TABLE *table= tab->table;
3443

3444
  ((Item_in_subselect *) item)->value= 0;
3445 3446
  empty_result_set= TRUE;
  null_keypart= 0;
3447
  table->status= 0;
3448

3449 3450
  if (check_null)
  {
3451
    /* We need to check for NULL if there wasn't a matching value */
3452
    *tab->ref.null_ref_key= 0;			// Search first for not null
3453 3454 3455
    ((Item_in_subselect *) item)->was_null= 0;
  }

3456 3457 3458 3459
  /* Copy the ref key and check for nulls... */
  if (copy_ref_key())
    DBUG_RETURN(1);

3460 3461 3462 3463 3464 3465 3466 3467 3468 3469
  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);
  }

3470 3471 3472
  if (!tab->preread_init_done && tab->preread_init())
    DBUG_RETURN(1);

3473 3474
  if (null_keypart)
    DBUG_RETURN(scan_table());
3475 3476

  if (!table->file->inited)
3477
    table->file->ha_index_init(tab->ref.key, 1);
3478 3479 3480 3481 3482
  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);
3483 3484
  if (error &&
      error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3485
    error= report_error(table, error);
3486 3487
  else
  {
3488
    for (;;)
3489
    {
3490 3491 3492
      error= 0;
      table->null_row= 0;
      if (!table->status)
3493
      {
3494
        if ((!cond || cond->val_int()) && (!having || having->val_int()))
3495
        {
3496
          empty_result_set= FALSE;
3497 3498 3499 3500 3501 3502
          if (null_finding)
            ((Item_in_subselect *) item)->was_null= 1;
          else
            ((Item_in_subselect *) item)->value= 1;
          break;
        }
3503 3504 3505
        error= table->file->ha_index_next_same(table->record[0],
                                               tab->ref.key_buff,
                                               tab->ref.key_length);
3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520
        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;
3521
      }
3522 3523
    }
  }
3524
  DBUG_RETURN(error != 0);
3525 3526
}

3527

unknown's avatar
unknown committed
3528 3529
uint subselect_single_select_engine::cols()
{
3530 3531 3532 3533
  //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
3534 3535
}

unknown's avatar
unknown committed
3536

unknown's avatar
unknown committed
3537 3538
uint subselect_union_engine::cols()
{
3539 3540
  DBUG_ASSERT(unit->is_prepared());  // should be called after fix_fields()
  return unit->types.elements;
unknown's avatar
unknown committed
3541 3542
}

unknown's avatar
unknown committed
3543

3544
uint8 subselect_single_select_engine::uncacheable()
3545 3546 3547 3548
{
  return select_lex->uncacheable;
}

unknown's avatar
unknown committed
3549

3550
uint8 subselect_union_engine::uncacheable()
3551 3552 3553 3554
{
  return unit->uncacheable;
}

unknown's avatar
unknown committed
3555

unknown's avatar
unknown committed
3556 3557 3558 3559 3560 3561 3562 3563 3564
void subselect_single_select_engine::exclude()
{
  select_lex->master_unit()->exclude_level();
}

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

unknown's avatar
unknown committed
3566

3567
void subselect_uniquesubquery_engine::exclude()
3568 3569 3570 3571
{
  //this never should be called
  DBUG_ASSERT(0);
}
3572 3573


3574
table_map subselect_engine::calc_const_tables(List<TABLE_LIST> &list)
3575 3576
{
  table_map map= 0;
3577 3578 3579 3580
  List_iterator<TABLE_LIST> ti(list);
  TABLE_LIST *table;
  //for (; table; table= table->next_leaf)
  while ((table= ti++))
3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591
  {
    TABLE *tbl= table->table;
    if (tbl && tbl->const_table)
      map|= tbl->map;
  }
  return map;
}


table_map subselect_single_select_engine::upper_select_const_tables()
{
3592
  return calc_const_tables(select_lex->outer_select()->leaf_tables);
3593 3594
}

unknown's avatar
merge  
unknown committed
3595

3596 3597
table_map subselect_union_engine::upper_select_const_tables()
{
3598
  return calc_const_tables(unit->outer_select()->leaf_tables);
3599
}
unknown's avatar
merge  
unknown committed
3600 3601


3602 3603
void subselect_single_select_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3604
{
3605
  select_lex->print(thd, str, query_type);
unknown's avatar
unknown committed
3606 3607 3608
}


3609
void subselect_union_engine::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3610
{
3611
  unit->print(str, query_type);
unknown's avatar
unknown committed
3612 3613 3614
}


3615 3616
void subselect_uniquesubquery_engine::print(String *str,
                                            enum_query_type query_type)
unknown's avatar
unknown committed
3617
{
3618
  char *table_name= tab->table->s->table_name.str;
3619
  str->append(STRING_WITH_LEN("<primary_index_lookup>("));
3620
  tab->ref.items[0]->print(str, query_type);
3621
  str->append(STRING_WITH_LEN(" in "));
3622 3623 3624 3625 3626 3627 3628 3629 3630 3631
  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
3632
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3633
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3634
  str->append(key_info->name);
unknown's avatar
unknown committed
3635 3636
  if (cond)
  {
3637
    str->append(STRING_WITH_LEN(" where "));
3638
    cond->print(str, query_type);
unknown's avatar
unknown committed
3639 3640 3641 3642
  }
  str->append(')');
}

3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665
/*
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
3666

3667 3668
void subselect_indexsubquery_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3669
{
3670
  str->append(STRING_WITH_LEN("<index_lookup>("));
3671
  tab->ref.items[0]->print(str, query_type);
3672
  str->append(STRING_WITH_LEN(" in "));
unknown's avatar
unknown committed
3673
  str->append(tab->table->s->table_name.str, tab->table->s->table_name.length);
unknown's avatar
unknown committed
3674
  KEY *key_info= tab->table->key_info+ tab->ref.key;
3675
  str->append(STRING_WITH_LEN(" on "));
unknown's avatar
unknown committed
3676
  str->append(key_info->name);
unknown's avatar
unknown committed
3677
  if (check_null)
3678
    str->append(STRING_WITH_LEN(" checking NULL"));
3679
  if (cond)
unknown's avatar
unknown committed
3680
  {
3681
    str->append(STRING_WITH_LEN(" where "));
3682
    cond->print(str, query_type);
unknown's avatar
unknown committed
3683
  }
3684 3685 3686
  if (having)
  {
    str->append(STRING_WITH_LEN(" having "));
3687
    having->print(str, query_type);
3688
  }
unknown's avatar
unknown committed
3689 3690
  str->append(')');
}
3691

unknown's avatar
unknown committed
3692 3693
/**
  change select_result object of engine.
3694

unknown's avatar
unknown committed
3695 3696
  @param si		new subselect Item
  @param res		new select_result object
3697
  @param temp           temporary assignment
3698

unknown's avatar
unknown committed
3699
  @retval
unknown's avatar
unknown committed
3700
    FALSE OK
unknown's avatar
unknown committed
3701
  @retval
unknown's avatar
unknown committed
3702
    TRUE  error
3703 3704
*/

3705 3706 3707 3708
bool
subselect_single_select_engine::change_result(Item_subselect *si,
                                              select_result_interceptor *res,
                                              bool temp)
3709 3710
{
  item= si;
3711
  if (temp)
3712 3713 3714 3715 3716 3717
  {
    /*
      Here we reuse change_item_tree to roll back assignment.  It has
      nothing special about Item* pointer so it is safe conversion. We do
      not change the interface to be compatible with MySQL.
    */
3718
    thd->change_item_tree((Item**) &result, (Item*)res);
3719
  }
3720 3721
  else
    result= res;
3722 3723 3724 3725 3726 3727 3728 3729 3730

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


unknown's avatar
unknown committed
3734 3735
/**
  change select_result object of engine.
3736

unknown's avatar
unknown committed
3737 3738
  @param si		new subselect Item
  @param res		new select_result object
3739

unknown's avatar
unknown committed
3740
  @retval
unknown's avatar
unknown committed
3741
    FALSE OK
unknown's avatar
unknown committed
3742
  @retval
unknown's avatar
unknown committed
3743
    TRUE  error
3744 3745
*/

unknown's avatar
unknown committed
3746
bool subselect_union_engine::change_result(Item_subselect *si,
3747 3748
                                           select_result_interceptor *res,
                                           bool temp)
3749 3750 3751
{
  item= si;
  int rc= unit->change_result(res, result);
3752 3753 3754 3755
  if (temp)
    thd->change_item_tree((Item**) &result, (Item*)res);
  else
    result= res;
3756 3757 3758 3759
  return rc;
}


unknown's avatar
unknown committed
3760 3761
/**
  change select_result emulation, never should be called.
3762

unknown's avatar
unknown committed
3763 3764
  @param si		new subselect Item
  @param res		new select_result object
3765

unknown's avatar
unknown committed
3766
  @retval
unknown's avatar
unknown committed
3767
    FALSE OK
unknown's avatar
unknown committed
3768
  @retval
unknown's avatar
unknown committed
3769
    TRUE  error
3770 3771
*/

3772 3773 3774 3775 3776
bool
subselect_uniquesubquery_engine::change_result(Item_subselect *si,
                                               select_result_interceptor *res,
                                               bool temp
                                               __attribute__((unused)))
3777 3778
{
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
3779
  return TRUE;
3780
}
3781 3782


unknown's avatar
unknown committed
3783 3784
/**
  Report about presence of tables in subquery.
3785

unknown's avatar
unknown committed
3786
  @retval
3787
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3788
  @retval
3789 3790 3791 3792 3793 3794 3795 3796
    FALSE there are some tables in subquery
*/
bool subselect_single_select_engine::no_tables()
{
  return(select_lex->table_list.elements == 0);
}


3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812
/*
  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
3813 3814
/**
  Report about presence of tables in subquery.
3815

unknown's avatar
unknown committed
3816
  @retval
3817
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3818
  @retval
3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831
    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
3832 3833
/**
  Report about presence of tables in subquery.
3834

unknown's avatar
unknown committed
3835
  @retval
3836
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3837
  @retval
3838 3839 3840 3841 3842 3843
    FALSE there are some tables in subquery
*/

bool subselect_uniquesubquery_engine::no_tables()
{
  /* returning value is correct, but this method should never be called */
3844
  DBUG_ASSERT(FALSE);
3845 3846
  return 0;
}
3847 3848 3849 3850 3851 3852 3853


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


3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867
/**
  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.
3868 3869 3870 3871 3872 3873 3874 3875 3876

  @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
3877 3878
*/

3879 3880
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_schema()
3881 3882 3883 3884
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;

  if (item_in->is_top_level_item())
3885
    return COMPLETE_MATCH;
3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907
  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)
3908 3909
    return PARTIAL_MATCH;
  return COMPLETE_MATCH;
3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920
}


/**
  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.
3921 3922 3923

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

3926 3927
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_data()
3928 3929 3930 3931 3932 3933
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
  Item *outer_col;

3934 3935 3936 3937 3938 3939
  /*
    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;
3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955

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

  /* If no column contains NULLs use regular hash index lookups. */
  if (!count_partial_match_columns)
3964 3965 3966
    return COMPLETE_MATCH;
  return PARTIAL_MATCH;
}
3967

3968 3969 3970 3971 3972 3973

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)
{
3974
  ulonglong pm_buff_size;
3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038

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

4039
ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
4040 4041 4042
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
4043 4044
  /* Total size of all buffers used by partial matching. */
  ulonglong buff_size;
4045 4046 4047 4048
  ha_rows row_count= tmp_table->file->stats.records;
  uint rowid_length= tmp_table->file->ref_length;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
unknown's avatar
unknown committed
4049
  ha_rows max_null_row;
4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071

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

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

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

      /* Add the size of Ordered_key::key_buff */
      buff_size+= (row_count - result_sink->get_null_count_of_col(i)) *
                         sizeof(rownum_t);
      /* Add the size of Ordered_key::null_key */
unknown's avatar
unknown committed
4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083
      max_null_row= result_sink->get_max_null_of_col(i);
      if (max_null_row >= UINT_MAX)
      {
        /*
          There can be at most UINT_MAX bits in a MY_BITMAP that is used to
          store NULLs in an Ordered_key. Return a number of bytes bigger than
          the maximum allowed memory buffer for partial matching to disable
          the rowid merge strategy.
        */
        return ULONGLONG_MAX;
      }
      buff_size+= bitmap_buffer_size(max_null_row);
4084 4085 4086 4087
    }
  }

  return buff_size;
4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110
}


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


4111 4112 4113 4114
/**
  Create all structures needed for IN execution that can live between PS
  reexecution.

4115
  @param tmp_columns the items that produce the data for the temp table
4116 4117
  @param subquery_id subquery's identifier (to make "<subquery%d>" name for
                                            EXPLAIN)
4118 4119

  @details
4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132
  - Create a temporary table to store the result of the IN subquery. The
    temporary table has one hash index on all its columns.
  - Create a new result sink that sends the result stream of the subquery to
    the temporary table,

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

  @retval TRUE  if error
  @retval FALSE otherwise
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
4133
bool subselect_hash_sj_engine::init(List<Item> *tmp_columns, uint subquery_id)
4134
{
4135
  select_union *result_sink;
4136 4137 4138
  /* Options to create_tmp_table. */
  ulonglong tmp_create_options= thd->options | TMP_TABLE_ALL_COLUMNS;
                             /* | TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM */
4139

4140
  DBUG_ENTER("subselect_hash_sj_engine::init");
4141

4142 4143 4144 4145 4146
  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);
4147 4148 4149 4150 4151 4152

  /*
    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.
  */
4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165
/*
  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))
4166
    DBUG_RETURN(TRUE);
4167 4168
  }
*/
4169
  if (!(result_sink= new select_materialize_with_stats))
4170
    DBUG_RETURN(TRUE);
Sergey Petrunya's avatar
Sergey Petrunya committed
4171
    
4172
  char buf[32];
4173
  uint len= my_snprintf(buf, sizeof(buf), "<subquery%d>", subquery_id);
4174 4175 4176 4177 4178
  char *name;
  if (!(name= (char*)thd->alloc(len + 1)))
    DBUG_RETURN(TRUE);
  memcpy(name, buf, len+1);

4179 4180 4181
  result_sink->get_tmp_table_param()->materialized_subquery= true;
  if (result_sink->create_result_table(thd, tmp_columns, TRUE,
                                       tmp_create_options,
4182
				       name, TRUE, TRUE))
4183 4184
    DBUG_RETURN(TRUE);

4185 4186
  tmp_table= result_sink->table;
  result= result_sink;
4187 4188

  /*
4189 4190 4191 4192 4193 4194 4195
    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.
4196 4197 4198
  */
  if (tmp_table->s->keys == 0)
  {
4199 4200
    //fprintf(stderr, "Q: %s\n", current_thd->query());
    DBUG_ASSERT(0);
4201 4202 4203 4204 4205
    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);
4206
    tmp_table= NULL;
4207 4208 4209 4210 4211 4212 4213 4214 4215
    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.
  */
4216 4217 4218
  DBUG_ASSERT(tmp_table->s->keys == 1 &&
              ((Item_in_subselect *) item)->left_expr->cols() ==
              tmp_table->key_info->key_parts);
4219

4220 4221 4222
  if (make_semi_join_conds() ||
      /* A unique_engine is used both for complete and partial matching. */
      !(lookup_engine= make_unique_engine()))
4223
    DBUG_RETURN(TRUE);
4224

4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235
  /*
    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);

4236 4237
  DBUG_RETURN(FALSE);
}
4238 4239


4240 4241 4242
/*
  Create an artificial condition to post-filter those rows matched by index
  lookups that cannot be distinguished by the index lookup procedure.
4243

4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258
  @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()
{
4259 4260 4261 4262 4263
  /*
    Table reference for tmp_table that is used to resolve column references
    (Item_fields) to columns in tmp_table.
  */
  TABLE_LIST *tmp_table_ref;
4264 4265 4266 4267 4268 4269 4270 4271 4272 4273
  /* 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);

4274 4275 4276
  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
    DBUG_RETURN(TRUE);

4277
  tmp_table_ref->init_one_table("", tmp_table->alias.c_ptr(), TL_READ);
4278 4279
  tmp_table_ref->table= tmp_table;

4280
  context= new Name_resolution_context;
4281 4282 4283
  context->init();
  context->first_name_resolution_table=
    context->last_name_resolution_table= tmp_table_ref;
4284
  semi_join_conds_context= context;
4285
  
4286
  for (uint i= 0; i < item_in->left_expr->cols(); i++)
4287 4288 4289 4290 4291
  {
    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;

4292 4293 4294 4295
    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)))
4296
    {
4297 4298
      delete semi_join_conds;
      semi_join_conds= NULL;
4299 4300 4301
      DBUG_RETURN(TRUE);
    }
  }
4302
  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
4303 4304 4305 4306 4307 4308 4309
    DBUG_RETURN(TRUE);

  DBUG_RETURN(FALSE);
}


/**
4310 4311 4312 4313 4314 4315 4316 4317 4318 4319 4320 4321 4322 4323
  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
4324
  Item_iterator_row it(item_in->left_expr);
4325 4326 4327 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340
  /* 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
4341
  tab->table= tmp_table;
4342
  tab->preread_init_done= FALSE;
unknown's avatar
unknown committed
4343
  tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
4344 4345 4346 4347 4348 4349

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


4350 4351 4352 4353 4354 4355 4356
subselect_hash_sj_engine::~subselect_hash_sj_engine()
{
  delete lookup_engine;
  delete result;
  if (tmp_table)
    free_tmp_table(thd, tmp_table);
}
4357 4358


4359
int subselect_hash_sj_engine::prepare()
4360 4361 4362 4363 4364
{
  /*
    Create and optimize the JOIN that will be used to materialize
    the subquery if not yet created.
  */
4365
  return materialize_engine->prepare();
4366 4367 4368 4369 4370 4371
}


/**
  Cleanup performed after each PS execution.

4372
  @details
4373 4374 4375 4376 4377
  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
*/

void subselect_hash_sj_engine::cleanup()
{
4378
  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
4379
  is_materialized= FALSE;
4380 4381 4382 4383 4384
  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;
4385
  materialize_engine->cleanup();
4386 4387 4388 4389 4390 4391
  /*
    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;
4392 4393 4394 4395 4396 4397 4398 4399 4400 4401 4402 4403 4404 4405 4406 4407
  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. */
4408 4409 4410
  DBUG_ASSERT(tmp_table);
  free_tmp_table(thd, tmp_table);
  tmp_table= NULL;
4411 4412 4413
}


4414 4415 4416 4417 4418 4419
/*
  Get fanout produced by tables specified in the table_map
*/

double get_fanout_with_deps(JOIN *join, table_map tset)
{
4420 4421 4422 4423
  /* Handle the case of "Impossible WHERE" */
  if (join->table_count == 0)
    return 0.0;

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
  /* First, recursively get all tables we depend on */
  table_map deps_to_check= tset;
  table_map checked_deps= 0;
  table_map further_deps;
  do
  {
    further_deps= 0;
    Table_map_iterator tm_it(deps_to_check);
    int tableno;
    while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
    {
      /* get tableno's dependency tables that are not in needed_set */
      further_deps |= join->map2table[tableno]->ref.depend_map & ~checked_deps;
    }

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

  
  /* Now, walk the join order and calculate the fanout */
  double fanout= 1;
  for (JOIN_TAB *tab= first_top_level_tab(join, WITHOUT_CONST_TABLES); tab;
       tab= next_top_level_tab(join, tab))
  {
4449 4450 4451 4452 4453 4454 4455
    /* 
      Ignore SJM nests. They have tab->table==NULL. There is no point to walk
      inside them, because GROUP BY clause cannot refer to tables from within
      subquery.
    */
    if (!tab->is_sjm_nest() && (tab->table->map & checked_deps) && 
        !tab->emb_sj_nest && 
4456 4457 4458 4459 4460
        tab->records_read != 0)
    {
      fanout *= rows2double(tab->records_read);
    }
  } 
4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 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
  return fanout;
}


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

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

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

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


4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 4558 4559 4560 4561 4562 4563 4564
/*
  Get an estimate of how many records will be produced after the GROUP BY
  operation.

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

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

4565
double get_post_group_estimate(JOIN* join, double join_op_rows)
4566 4567 4568 4569 4570 4571 4572 4573
{
  table_map tables_in_group_list= table_map(0);

  /* Find out which tables are used in GROUP BY list */
  for (ORDER *order= join->group_list; order; order= order->next)
  {
    Item *item= order->item[0];
    if (item->used_tables() & RAND_TABLE_BIT)
4574 4575 4576 4577
    {
      /* Each join output record will be in its own group */
      return join_op_rows;
    }
4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589
    tables_in_group_list|= item->used_tables();
  }
  tables_in_group_list &= ~PSEUDO_TABLE_BITS;

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

#if 0
  /* The following will be needed when making use of index stats: */
4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610
  /* 
    Also generate max. number of records for each of the tables mentioned 
    in the group-list. We'll use that a baseline number that we'll try to 
    reduce by using
     - #table-records 
     - index statistics.
  */
  Table_map_iterator tm_it(tables_in_group_list);
  int tableno;
  while ((tableno = tm_it.next_bit()) != Table_map_iterator::BITMAP_END)
  {
    fanout_rows[tableno]= get_fanout_with_deps(join, table_map(1) << tableno);
  }
  
  /*
    Try to bring down estimates using index statistics.
  */
  //check_out_index_stats(join);
4611 4612
#endif

4613 4614 4615 4616
  return out_rows;
}


4617 4618 4619
/**
  Execute a subquery IN predicate via materialization.

4620
  @details
4621 4622 4623 4624 4625 4626 4627 4628 4629 4630
  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;
4631
  SELECT_LEX *save_select= thd->lex->current_select;
4632
  subselect_partial_match_engine *pm_engine= NULL;
4633
  int res= 0;
4634 4635 4636 4637 4638 4639 4640

  DBUG_ENTER("subselect_hash_sj_engine::exec");

  /*
    Optimize and materialize the subquery during the first execution of
    the subquery predicate.
  */
4641
  thd->lex->current_select= materialize_engine->select_lex;
4642 4643
  /* The subquery should be optimized, and materialized only once. */
  DBUG_ASSERT(materialize_join->optimized && !is_materialized);
4644
  materialize_join->exec();
4645 4646
  if ((res= test(materialize_join->error || thd->is_fatal_error ||
                 thd->is_error())))
4647
    goto err;
4648

4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668
  /*
    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. */
4669 4670
    item_in->reset();
    item_in->make_const();
4671 4672 4673 4674
    item_in->set_first_execution();
    DBUG_RETURN(FALSE);
  }

4675 4676 4677 4678 4679 4680 4681 4682 4683
  /*
    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();
4684 4685
  if (strategy == PARTIAL_MATCH)
  {
4686
    uint count_pm_keys; /* Total number of keys needed for partial matching. */
unknown's avatar
unknown committed
4687 4688 4689 4690
    MY_BITMAP *nn_key_parts= NULL; /* Key parts of the only non-NULL index. */
    uint count_non_null_columns= 0; /* Number of columns in nn_key_parts. */
    bool has_covering_null_row;
    bool has_covering_null_columns;
4691 4692
    select_materialize_with_stats *result_sink=
      (select_materialize_with_stats *) result;
unknown's avatar
unknown committed
4693
    uint field_count= tmp_table->s->fields;
4694

unknown's avatar
unknown committed
4695 4696 4697 4698 4699 4700 4701 4702
    if (count_partial_match_columns < field_count)
    {
      nn_key_parts= &non_null_key_parts;
      count_non_null_columns= bitmap_bits_set(nn_key_parts);
    }
    has_covering_null_row= (result_sink->get_max_nulls_in_row() == field_count);
    has_covering_null_columns= (count_non_null_columns +
                                count_null_only_columns == field_count);
4703

unknown's avatar
unknown committed
4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717
    if (has_covering_null_row && has_covering_null_columns)
    {
      /*
        The whole table consist of only NULL values. The result of IN is
        a constant UNKNOWN.
      */
      DBUG_ASSERT(tmp_table->file->stats.records == 1);
      item_in->value= 0;
      item_in->null_value= 1;
      item_in->make_const();
      item_in->set_first_execution();
      DBUG_RETURN(FALSE);
    }

unknown's avatar
unknown committed
4718 4719 4720 4721 4722 4723 4724
    if (has_covering_null_row)
    {
      DBUG_ASSERT(count_partial_match_columns = field_count);
      count_pm_keys= 0;
    }
    else if (has_covering_null_columns)
      count_pm_keys= 1;
4725 4726
    else
      count_pm_keys= count_partial_match_columns - count_null_only_columns +
unknown's avatar
unknown committed
4727
                     (nn_key_parts ? 1 : 0);
4728

4729
    choose_partial_match_strategy(test(nn_key_parts),
unknown's avatar
unknown committed
4730
                                  has_covering_null_row,
4731 4732 4733 4734
                                  &partial_match_key_parts);
    DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE ||
                strategy == PARTIAL_MATCH_SCAN);
    if (strategy == PARTIAL_MATCH_MERGE)
4735
    {
4736
      pm_engine=
unknown's avatar
unknown committed
4737
        new subselect_rowid_merge_engine(thd, (subselect_uniquesubquery_engine*)
4738 4739
                                         lookup_engine, tmp_table,
                                         count_pm_keys,
unknown's avatar
unknown committed
4740 4741
                                         has_covering_null_row,
                                         has_covering_null_columns,
unknown's avatar
unknown committed
4742
                                         count_columns_with_nulls,
4743 4744 4745 4746 4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757
                                         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;
      }
4758
    }
4759 4760

    if (strategy == PARTIAL_MATCH_SCAN)
4761
    {
4762
      if (!(pm_engine=
unknown's avatar
unknown committed
4763
            new subselect_table_scan_engine(thd, (subselect_uniquesubquery_engine*)
4764 4765 4766
                                            lookup_engine, tmp_table,
                                            item, result,
                                            semi_join_conds->argument_list(),
unknown's avatar
unknown committed
4767
                                            has_covering_null_row,
unknown's avatar
unknown committed
4768 4769
                                            has_covering_null_columns,
                                            count_columns_with_nulls)))
4770 4771 4772 4773 4774
      {
        /* This is an irrecoverable error. */
        res= 1;
        goto err;
      }
4775 4776 4777
    }
  }

4778 4779
  if (pm_engine)
    lookup_engine= pm_engine;
4780 4781 4782 4783 4784
  item_in->change_engine(lookup_engine);

err:
  thd->lex->current_select= save_select;
  DBUG_RETURN(res);
4785 4786 4787 4788 4789 4790 4791 4792 4793 4794 4795 4796
}


/**
  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(" ), "));
4797 4798 4799

  if (lookup_engine)
    lookup_engine->print(str, query_type);
4800 4801
  else
    str->append(STRING_WITH_LEN(
4802
           "<engine selected at execution time>"
4803 4804
         ));
}
4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822

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,
4823 4824
                                             select_result_interceptor *res,
                                             bool temp __attribute__((unused)))
4825 4826 4827 4828 4829 4830
{
  DBUG_ASSERT(FALSE);
  return TRUE;
}


4831 4832 4833 4834
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),
4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855
    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()
{
4856 4857
  my_free((char*) key_buff, MYF(0));
  bitmap_free(&null_key);
4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874
}


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

4875

4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892
/*
  Initialize a multi-column index.
*/

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

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

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

4896 4897 4898 4899 4900 4901 4902 4903 4904 4905 4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948
  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;
}


4949 4950 4951 4952
/*
  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
*/

4953 4954 4955 4956
bool Ordered_key::alloc_keys_buffers()
{
  DBUG_ASSERT(key_buff_elements > 0);

4957 4958
  if (!(key_buff= (rownum_t*) my_malloc((size_t)(key_buff_elements * 
    sizeof(rownum_t)), MYF(MY_WME))))
4959 4960 4961 4962 4963 4964 4965
    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.
  */
4966
  /* Notice that max_null_row is max array index, we need count, so +1. */
4967
  if (bitmap_init(&null_key, NULL, (uint)(max_null_row + 1), FALSE))
4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030
    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()
{
5031
  my_qsort2(key_buff, (size_t) key_buff_elements, sizeof(rownum_t),
5032 5033 5034 5035 5036 5037
            (qsort2_cmp) &cmp_keys_by_row_data_and_rownum, (void*) this);
  /* Invalidate the current row position. */
  cur_key_idx= HA_POS_ERROR;
}


5038
/*
5039 5040 5041
  The fraction of rows that do not contain NULL in the columns indexed by
  this key.

5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053
  @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);
}


5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171
/*
  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;
}


5172 5173 5174 5175 5176 5177 5178 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199
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('}');
}


5200
subselect_partial_match_engine::subselect_partial_match_engine(
unknown's avatar
unknown committed
5201
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5202 5203 5204
  TABLE *tmp_table_arg, Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
5205
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
5206 5207
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
unknown's avatar
unknown committed
5208
  :subselect_engine(thd_arg, item_arg, result_arg),
5209 5210
   tmp_table(tmp_table_arg), lookup_engine(engine_arg),
   equi_join_conds(equi_join_conds_arg),
unknown's avatar
unknown committed
5211
   has_covering_null_row(has_covering_null_row_arg),
unknown's avatar
unknown committed
5212 5213
   has_covering_null_columns(has_covering_null_columns_arg),
   count_columns_with_nulls(count_columns_with_nulls_arg)
5214 5215 5216 5217 5218 5219
{}


int subselect_partial_match_engine::exec()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
unknown's avatar
unknown committed
5220
  int copy_res, lookup_res;
5221 5222

  /* Try to find a matching row by index lookup. */
unknown's avatar
unknown committed
5223 5224
  copy_res= lookup_engine->copy_ref_key_simple();
  if (copy_res == -1)
5225 5226 5227 5228 5229 5230
  {
    /* The result is FALSE based on the outer reference. */
    item_in->value= 0;
    item_in->null_value= 0;
    return 0;
  }
unknown's avatar
unknown committed
5231
  else if (copy_res == 0)
5232 5233
  {
    /* Search for a complete match. */
unknown's avatar
unknown committed
5234
    if ((lookup_res= lookup_engine->index_lookup()))
5235 5236 5237 5238
    {
      /* An error occured during lookup(). */
      item_in->value= 0;
      item_in->null_value= 0;
unknown's avatar
unknown committed
5239
      return lookup_res;
5240
    }
unknown's avatar
unknown committed
5241
    else if (item_in->value || !count_columns_with_nulls)
5242 5243 5244
    {
      /*
        A complete match was found, the result of IN is TRUE.
unknown's avatar
unknown committed
5245 5246 5247
        If no match was found, and there are no NULLs in the materialized
        subquery, then the result is guaranteed to be false because this
        branch is executed when the outer reference has no NULLs as well.
5248 5249 5250 5251 5252 5253
        Notice: (this->item == lookup_engine->item)
      */
      return 0;
    }
  }

unknown's avatar
unknown committed
5254
  if (has_covering_null_row)
5255 5256 5257 5258 5259 5260 5261 5262 5263 5264 5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309
  {
    /*
      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
5310
    DBUG_ASSERT(FALSE);
5311 5312 5313 5314
  */
}


5315 5316 5317
/*
  @param non_null_key_parts  
  @param partial_match_key_parts  A union of all single-column NULL key parts.
5318 5319 5320 5321

  @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
5322 5323 5324 5325 5326 5327 5328 5329 5330 5331 5332 5333
*/

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;
unknown's avatar
unknown committed
5334
  uint cur_keyid= 0;
5335 5336 5337
  Item_in_subselect *item_in= (Item_in_subselect*) item;
  int error;

unknown's avatar
unknown committed
5338
  if (merge_keys_count == 0)
5339
  {
unknown's avatar
unknown committed
5340 5341
    DBUG_ASSERT(bitmap_bits_set(partial_match_key_parts) == 0 ||
                has_covering_null_row);
5342 5343 5344 5345
    /* There is nothing to initialize, we will only do regular lookups. */
    return FALSE;
  }

unknown's avatar
unknown committed
5346 5347 5348 5349 5350 5351 5352
  /*
    If all nullable columns contain only NULLs, there must be one index
    over all non-null columns.
  */
  DBUG_ASSERT(!has_covering_null_columns ||
              (has_covering_null_columns &&
               merge_keys_count == 1 && non_null_key_parts));
5353 5354
  /*
    Allocate buffers to hold the merged keys and the mapping between rowids and
unknown's avatar
unknown committed
5355 5356
    row numbers. All small buffers are allocated in the runtime memroot. Big
    buffers are allocated from the OS via malloc.
5357
  */
unknown's avatar
unknown committed
5358
  if (!(merge_keys= (Ordered_key**) thd->alloc(merge_keys_count *
5359
                                               sizeof(Ordered_key*))) ||
unknown's avatar
unknown committed
5360 5361
      !(null_bitmaps= (MY_BITMAP**) thd->alloc(merge_keys_count *
                                               sizeof(MY_BITMAP*))) ||
5362 5363
      !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length),
        MYF(MY_WME))))
5364 5365 5366 5367 5368
    return TRUE;

  /* Create the only non-NULL key if there is any. */
  if (non_null_key_parts)
  {
unknown's avatar
unknown committed
5369
    non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
5370 5371 5372
                                  0, 0, 0, row_num_to_rowid);
    if (non_null_key->init(non_null_key_parts))
      return TRUE;
unknown's avatar
unknown committed
5373 5374 5375
    merge_keys[cur_keyid]= non_null_key;
    merge_keys[cur_keyid]->first();
    ++cur_keyid;
5376 5377 5378
  }

  /*
unknown's avatar
unknown committed
5379 5380
    If all nullable columns contain NULLs, the only key that is needed is the
    only non-NULL key that is already created above.
5381
  */
unknown's avatar
unknown committed
5382
  if (!has_covering_null_columns)
5383
  {
unknown's avatar
unknown committed
5384 5385
    if (bitmap_init_memroot(&matching_keys, merge_keys_count, thd->mem_root) ||
        bitmap_init_memroot(&matching_outer_cols, merge_keys_count, thd->mem_root))
5386 5387 5388 5389 5390 5391 5392 5393
      return TRUE;

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

unknown's avatar
unknown committed
5399
      merge_keys[cur_keyid]= new Ordered_key(
5400 5401 5402 5403 5404 5405
                                     cur_keyid, tmp_table,
                                     item_in->left_expr->element_index(i),
                                     result_sink->get_null_count_of_col(i),
                                     result_sink->get_min_null_of_col(i),
                                     result_sink->get_max_null_of_col(i),
                                     row_num_to_rowid);
unknown's avatar
unknown committed
5406 5407 5408
      if (merge_keys[cur_keyid]->init(i))
        return TRUE;
      merge_keys[cur_keyid]->first();
5409
      ++cur_keyid;
5410 5411
    }
  }
unknown's avatar
unknown committed
5412
  DBUG_ASSERT(cur_keyid == merge_keys_count);
5413 5414

  /* Populate the indexes with data from the temporary table. */
5415 5416
  if (tmp_table->file->ha_rnd_init_with_error(1))
    return TRUE;
5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 5444 5445 5446 5447 5448 5449 5450 5451 5452
  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);
    }

unknown's avatar
unknown committed
5453
    for (uint i= (non_null_key ? 1 : 0); i < merge_keys_count; i++)
5454 5455 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468
    {
      /*
        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();

5469
  /* Sort all the keys by their NULL selectivity. */
unknown's avatar
unknown committed
5470
  my_qsort(merge_keys, merge_keys_count, sizeof(Ordered_key*),
5471 5472
           (qsort_cmp) cmp_keys_by_null_selectivity);

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

unknown's avatar
unknown committed
5477
  if (init_queue(&pq, merge_keys_count, 0, FALSE,
5478 5479
                 subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
                 0, 0))
5480 5481 5482 5483 5484 5485 5486 5487
    return TRUE;

  return FALSE;
}


subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
{
5488
  /* None of the resources below is allocated if there are no ordered keys. */
unknown's avatar
unknown committed
5489
  if (merge_keys_count)
5490 5491
  {
    my_free((char*) row_num_to_rowid, MYF(0));
unknown's avatar
unknown committed
5492
    for (uint i= 0; i < merge_keys_count; i++)
5493 5494 5495 5496 5497
      delete merge_keys[i];
    delete_queue(&pq);
    if (tmp_table->file->inited == handler::RND)
      tmp_table->file->ha_rnd_end();
  }
5498 5499 5500 5501 5502
}


void subselect_rowid_merge_engine::cleanup()
{
5503 5504 5505
}


5506
/*
5507 5508 5509 5510 5511 5512 5513 5514 5515
  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
5516 5517 5518
*/

int
5519 5520
subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
                                                           Ordered_key **k2)
5521
{
5522 5523 5524
  double k1_sel= (*k1)->null_selectivity();
  double k2_sel= (*k2)->null_selectivity();
  if (k1_sel < k2_sel)
5525
    return 1;
5526 5527 5528
  if (k1_sel > k2_sel)
    return -1;
  return 0;
5529 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549
}


/*
*/

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

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


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

unknown's avatar
unknown committed
5550 5551 5552 5553
  @note
  There is no need to check the columns that contain only NULLs, because
  those are guaranteed to match.

5554 5555 5556 5557 5558 5559
  @retval TRUE if a NULL row exists
  @retval FALSE otherwise
*/

bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num)
{
5560
  Ordered_key *cur_key;
unknown's avatar
unknown committed
5561
  for (uint i = 0; i < merge_keys_count; i++)
5562
  {
5563
    cur_key= merge_keys[i];
unknown's avatar
unknown committed
5564
    if (bitmap_is_set(&matching_keys, cur_key->get_keyid()))
5565 5566
    {
      /*
unknown's avatar
unknown committed
5567 5568
        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.
5569 5570 5571
      */
      continue;
    }
5572
    if (!cur_key->is_null(row_num))
5573 5574 5575 5576 5577 5578
      return FALSE;
  }
  return TRUE;
}


unknown's avatar
unknown committed
5579 5580
/**
  Test if a subset of NULL-able columns contains a row of NULLs.
unknown's avatar
unknown committed
5581 5582
  @retval TRUE  if such a row exists
  @retval FALSE no complementing null row
unknown's avatar
unknown committed
5583 5584 5585 5586 5587 5588 5589
*/

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

unknown's avatar
unknown committed
5593
  if (!count_columns_with_nulls)
unknown's avatar
unknown committed
5594 5595
  {
    /*
unknown's avatar
unknown committed
5596 5597
      If there are both NULLs and non-NUll values in the outer reference, and
      the subquery contains no NULLs, a complementing NULL row cannot exist.
unknown's avatar
unknown committed
5598
    */
unknown's avatar
unknown committed
5599
    return FALSE;
unknown's avatar
unknown committed
5600 5601
  }

unknown's avatar
unknown committed
5602
  for (i= (non_null_key ? 1 : 0), count_null_keys= 0; i < merge_keys_count; i++)
unknown's avatar
unknown committed
5603 5604 5605 5606
  {
    cur_key= merge_keys[i];
    if (bitmap_is_set(keys_to_complement, cur_key->get_keyid()))
      continue;
unknown's avatar
unknown committed
5607 5608 5609 5610 5611
    if (!cur_key->get_null_count())
    {
      /* If there is column without NULLs, there cannot be a partial match. */
      return FALSE;
    }
unknown's avatar
unknown committed
5612 5613 5614 5615
    if (cur_key->get_min_null_row() > highest_min_row)
      highest_min_row= cur_key->get_min_null_row();
    if (cur_key->get_max_null_row() < lowest_max_row)
      lowest_max_row= cur_key->get_max_null_row();
unknown's avatar
unknown committed
5616
    null_bitmaps[count_null_keys++]= cur_key->get_null_key();
unknown's avatar
unknown committed
5617 5618 5619 5620 5621 5622 5623 5624 5625 5626
  }

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

  return bitmap_exists_intersection((const MY_BITMAP**) null_bitmaps,
                                    count_null_keys,
unknown's avatar
unknown committed
5627
                                    (uint)highest_min_row, (uint)lowest_max_row);
unknown's avatar
unknown committed
5628 5629 5630
}


5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642
/*
  @retval TRUE  there is a partial match (UNKNOWN)
  @retval FALSE  there is no match at all (FALSE)
*/

bool subselect_rowid_merge_engine::partial_match()
{
  Ordered_key *min_key; /* Key that contains the current minimum position. */
  rownum_t min_row_num; /* Current row number of min_key. */
  Ordered_key *cur_key;
  rownum_t cur_row_num;
  uint count_nulls_in_search_key= 0;
unknown's avatar
unknown committed
5643
  uint max_null_in_any_row=
unknown's avatar
unknown committed
5644
    ((select_materialize_with_stats *) result)->get_max_nulls_in_row();
5645
  bool res= FALSE;
5646 5647 5648

  /* 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
5649 5650
  /* The prioryty queue for keys must be empty. */
  DBUG_ASSERT(!pq.elements);
5651 5652

  /* All data accesses during execution are via handler::ha_rnd_pos() */
5653 5654 5655 5656 5657
  if (tmp_table->file->ha_rnd_init_with_error(0))
  {
    res= FALSE;
    goto end;
  }
5658

5659 5660
  /* Check if there is a match for the columns of the only non-NULL key. */
  if (non_null_key && !non_null_key->lookup())
5661 5662 5663 5664
  {
    res= FALSE;
    goto end;
  }
5665 5666

  /*
unknown's avatar
unknown committed
5667 5668 5669 5670
    If all nullable columns contain only NULLs, then there is a guranteed
    partial match, and we don't need to search for a matching row.
  */
  if (has_covering_null_columns)
5671 5672 5673 5674
  {
    res= TRUE;
    goto end;
  }
5675 5676 5677 5678 5679 5680 5681

  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);
unknown's avatar
unknown committed
5682
  for (uint i= test(non_null_key); i < merge_keys_count; i++)
5683 5684
  {
    DBUG_ASSERT(merge_keys[i]->get_column_count() == 1);
unknown's avatar
unknown committed
5685
    if (merge_keys[i]->get_search_key(0)->null_value)
5686 5687
    {
      ++count_nulls_in_search_key;
5688
      bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
5689 5690 5691 5692 5693 5694 5695
    }
    else if (merge_keys[i]->lookup())
      queue_insert(&pq, (uchar *) merge_keys[i]);
  }

  /*
    If the outer reference consists of only NULLs, or if it has NULLs in all
unknown's avatar
unknown committed
5696 5697
    nullable columns (above we guarantee there is a match for the non-null
    coumns), the result is UNKNOWN.
5698
  */
unknown's avatar
unknown committed
5699
  if (count_nulls_in_search_key == merge_keys_count - test(non_null_key))
5700 5701 5702 5703
  {
    res= TRUE;
    goto end;
  }
5704

unknown's avatar
unknown committed
5705 5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 5719 5720 5721
  /*
    If the outer row has NULLs in some columns, and
    there is no match for any of the remaining columns, and
    there is a subquery row with NULLs in all unmatched columns,
    then there is a partial match, otherwise the result is FALSE.
  */
  if (count_nulls_in_search_key && !pq.elements)
  {
    DBUG_ASSERT(!non_null_key);
    /*
      Check if the intersection of all NULL bitmaps of all keys that
      are not in matching_outer_cols is non-empty.
    */
    res= exists_complementing_null_row(&matching_outer_cols);
    goto end;
  }

5722 5723
  /*
    If there is no NULL (sub)row that covers all NULL columns, and there is no
unknown's avatar
unknown committed
5724 5725 5726 5727
    match for any of the NULL columns, the result is FALSE. Notice that if there
    is a non-null key, and there is only one matching key, the non-null key is
    the matching key. This is so, because this method returns FALSE if the
    non-null key doesn't have a match.
5728
  */
unknown's avatar
unknown committed
5729 5730 5731 5732
  if (!count_nulls_in_search_key &&
      (!pq.elements ||
       (pq.elements == 1 && non_null_key &&
        max_null_in_any_row < merge_keys_count-1)))
5733
  {
unknown's avatar
unknown committed
5734
    if (!pq.elements)
unknown's avatar
unknown committed
5735
    {
unknown's avatar
unknown committed
5736 5737 5738 5739 5740 5741
      DBUG_ASSERT(!non_null_key);
      /*
        The case of a covering null row is handled by
        subselect_partial_match_engine::exec()
      */
      DBUG_ASSERT(max_null_in_any_row != tmp_table->s->fields);
unknown's avatar
unknown committed
5742
    }
5743 5744 5745
    res= FALSE;
    goto end;
  }
5746 5747 5748

  DBUG_ASSERT(pq.elements);

unknown's avatar
unknown committed
5749
  min_key= (Ordered_key*) queue_remove_top(&pq);
5750
  min_row_num= min_key->current();
5751
  bitmap_set_bit(&matching_keys, min_key->get_keyid());
5752 5753 5754 5755 5756 5757 5758 5759 5760 5761
  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.
    */
5762 5763
    res= test_null_row(min_row_num);
    goto end;
5764 5765 5766 5767
  }

  while (TRUE)
  {
unknown's avatar
unknown committed
5768
    cur_key= (Ordered_key*) queue_remove_top(&pq);
5769 5770 5771
    cur_row_num= cur_key->current();

    if (cur_row_num == min_row_num)
5772
      bitmap_set_bit(&matching_keys, cur_key->get_keyid());
5773 5774 5775 5776 5777
    else
    {
      /* Follows from the correct use of priority queue. */
      DBUG_ASSERT(cur_row_num > min_row_num);
      if (test_null_row(min_row_num))
5778 5779 5780 5781
      {
        res= TRUE;
        goto end;
      }
5782 5783 5784 5785
      else
      {
        min_key= cur_key;
        min_row_num= cur_row_num;
unknown's avatar
unknown committed
5786
        bitmap_clear_all(&matching_keys);
5787
        bitmap_set_bit(&matching_keys, min_key->get_keyid());
5788 5789 5790 5791 5792 5793 5794 5795 5796 5797
        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. */
5798 5799
      res= test_null_row(min_row_num);
      goto end;
5800 5801 5802
    }
  }

5803
  /* We should never get here - all branches must be handled explicitly above. */
5804
  DBUG_ASSERT(FALSE);
5805 5806

end:
unknown's avatar
unknown committed
5807 5808
  if (!has_covering_null_columns)
    bitmap_clear_all(&matching_keys);
unknown's avatar
unknown committed
5809
  queue_remove_all(&pq);
5810 5811
  tmp_table->file->ha_rnd_end();
  return res;
5812 5813 5814
}


5815
subselect_table_scan_engine::subselect_table_scan_engine(
unknown's avatar
unknown committed
5816
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5817 5818 5819 5820
  TABLE *tmp_table_arg,
  Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
5821
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
5822 5823
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
unknown's avatar
unknown committed
5824
  :subselect_partial_match_engine(thd_arg, engine_arg, tmp_table_arg, item_arg,
5825
                                  result_arg, equi_join_conds_arg,
unknown's avatar
unknown committed
5826
                                  has_covering_null_row_arg,
unknown's avatar
unknown committed
5827 5828
                                  has_covering_null_columns_arg,
                                  count_columns_with_nulls_arg)
5829
{}
5830

5831 5832 5833 5834 5835 5836 5837

/*
  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
5838
  {
5839 5840
    count_matches= 0;
    for each row element row_i[j]
5841
    {
5842 5843
      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
        ++count_matches;
5844
    }
5845 5846
    if (count_matches == outer_ref.elements)
      return TRUE
5847
  }
5848 5849
  return FALSE
*/
5850

5851 5852 5853 5854 5855 5856 5857
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;
5858

5859 5860 5861 5862 5863 5864
  if (tmp_table->file->ha_rnd_init_with_error(1))
  {
    res= FALSE;
    goto end;
  }

5865 5866 5867
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
                             current_thd->variables.read_buff_size);
  for (;;)
5868
  {
5869 5870 5871 5872 5873 5874 5875 5876 5877 5878 5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902
    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;
    }
5903
  }
5904 5905 5906

  res= FALSE;
end:
5907
  tmp_table->file->ha_rnd_end();
5908 5909
  return res;
}
5910

5911 5912 5913

void subselect_table_scan_engine::cleanup()
{
5914
}
unknown's avatar
unknown committed
5915