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);
Igor Babaev's avatar
Igor Babaev committed
214
  engine->set_thd((thd= thd_param));
215 216 217 218
  if (!done_first_fix_fields)
  {
    done_first_fix_fields= TRUE;
    inside_first_fix_fields= TRUE;
219 220 221 222 223
    upper_refs.empty();
    /*
      psergey-todo: remove _first_fix_fields calls, we need changes on every
      execution
    */
224 225
  }

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

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

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

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

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

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

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

294

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

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

314

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

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


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

  @param arg  pointer to the fake select

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

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


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

395

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

424

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

515
bool Item_subselect::walk(Item_processor processor, bool walk_subquery,
516
                          uchar *argument)
517
{
518 519 520 521 522 523 524 525 526 527 528 529
  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).
    */
530
    return (this->*processor)(argument);
531
  }
532 533 534 535 536 537 538 539 540 541 542 543 544 545

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

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


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

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

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

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

599

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

Sergey Petrunya's avatar
Sergey Petrunya committed
608 609 610 611 612 613 614 615 616 617
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);
618

Sergey Petrunya's avatar
Sergey Petrunya committed
619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654
  /* 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
655 656


unknown's avatar
unknown committed
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671
/**
  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
672
  return ((engine->uncacheable() & UNCACHEABLE_DEPENDENT) &&
unknown's avatar
unknown committed
673 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
          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
700
  return (optimizer_flag(thd, OPTIMIZER_SWITCH_SUBQUERY_CACHE) &&
unknown's avatar
unknown committed
701 702 703 704 705
          !(engine->uncacheable() & (UNCACHEABLE_RAND |
                                     UNCACHEABLE_SIDEEFFECT)));
}


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

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

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


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

unknown's avatar
unknown committed
751

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

unknown's avatar
unknown committed
757

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

unknown's avatar
merge  
unknown committed
763

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

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

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

unknown's avatar
unknown committed
790

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


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

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

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

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

863 864 865
  DBUG_VOID_RETURN;
}

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

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


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

890

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

901

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

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

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

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

unknown's avatar
unknown committed
967

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

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

979 980 981 982 983 984 985 986 987
/* 
 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
988
void Item_singlerow_subselect::fix_length_and_dec()
989
{
990 991 992 993 994
  if ((max_columns= engine->cols()) == 1)
  {
    engine->fix_length_and_dec(row= &value);
  }
  else
995
  {
996
    if (!(row= (Item_cache**) sql_alloc(sizeof(Item_cache*)*max_columns)))
997 998 999
      return;
    engine->fix_length_and_dec(row);
    value= *row;
1000
  }
1001
  unsigned_flag= value->unsigned_flag;
1002 1003 1004 1005 1006 1007 1008
  /*
    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
1009 1010 1011 1012 1013
  else
  {
    for (uint i= 0; i < max_columns; i++)
      row[i]->maybe_null= TRUE;
  }
1014 1015
}

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

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

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

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


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

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

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

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

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

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

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

unknown's avatar
unknown committed
1127

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


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


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

unknown's avatar
unknown committed
1171

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


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

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

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

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

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

unknown's avatar
unknown committed
1240

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

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


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)
  */
1262 1263
  thd->change_item_tree(&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
  }

  DBUG_RETURN(false);
}

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

/**
  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)
1618
{
1619
  DBUG_ENTER("Item_allany_subselect::transform_into_max_min");
unknown's avatar
unknown committed
1620
  if (!test_strategy(SUBS_MAXMIN_INJECTED | SUBS_MAXMIN_ENGINE))
1621
    DBUG_RETURN(false);
1622 1623 1624 1625 1626 1627 1628 1629 1630
  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
1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644
  /*
    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*/
1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672
  {
    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
1673 1674 1675
    DBUG_EXECUTE("where",
                 print_where(item, "rewrite with MIN/MAX", QT_ORDINARY););

1676 1677
    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
1678
    /*
1679 1680 1681
      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
1682
    */
1683 1684 1685 1686 1687 1688 1689 1690 1691
    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
1692 1693 1694 1695 1696

    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
1697
    set_strategy(SUBS_MAXMIN_INJECTED);
1698 1699 1700 1701 1702 1703 1704
  }
  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
1705 1706 1707 1708
    /*
      Remove other strategies if any (we already changed the query and
      can't apply other strategy).
    */
unknown's avatar
unknown committed
1709
    set_strategy(SUBS_MAXMIN_ENGINE);
1710
  }
unknown's avatar
unknown committed
1711 1712 1713 1714
  /*
    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
1715
  subs= func->create_swap(*(optimizer->get_cache()), subs);
1716 1717
  thd->change_item_tree(place, subs);
  if (subs->fix_fields(thd, &subs))
1718
    DBUG_RETURN(true);
1719 1720 1721 1722
  DBUG_ASSERT(subs == (*place)); // There was no substitutions

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

unknown's avatar
unknown committed
1724
  DBUG_RETURN(false);
1725
}
1726

1727

1728 1729 1730 1731 1732 1733 1734 1735 1736 1737
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;
1738 1739
}

1740 1741 1742 1743 1744 1745
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
1746
  return (abort_on_null || (upper_item && upper_item->is_top_level_item())) &&
1747 1748 1749
      !join->select_lex->master_unit()->uncacheable && !func->eqne_op();
}

1750 1751

/**
1752 1753
  Create the predicates needed to transform a single-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1754

1755 1756 1757
  @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
1758

1759 1760
  @details
  The correlated predicates are created as follows:
1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774

  - 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:
        
1775
      SELECT ie FROM ... WHERE subq_where AND (oe $cmp$ ie)
1776 1777 1778

    = If we need to distinguish between those:

1779
      SELECT ie FROM ...
1780 1781 1782
        WHERE  subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
        HAVING trigcond(<is_not_null_test>(ie))

unknown's avatar
unknown committed
1783 1784
  @retval false If the new conditions were created successfully
  @retval true  Error
1785 1786
*/

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

1799
  DBUG_ENTER("Item_in_subselect::create_single_in_to_exists_cond");
1800

1801 1802
  *where_item= NULL;
  *having_item= NULL;
1803

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

1823 1824 1825
    if (!join_having)
      item->name= (char*) in_having_cond;
    if (fix_having(item, select_lex))
unknown's avatar
unknown committed
1826
      DBUG_RETURN(true);
1827
    *having_item= item;
1828 1829 1830
  }
  else
  {
unknown's avatar
unknown committed
1831 1832
    Item *item= (Item*) select_lex->item_list.head();

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

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

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

1893 1894
        new_having->name= (char*) in_having_cond;
        if (fix_having(new_having, select_lex))
unknown's avatar
unknown committed
1895
          DBUG_RETURN(true);
1896
        *having_item= new_having;
1897 1898
      }
      else
1899
        DBUG_ASSERT(false);
1900
    }
unknown's avatar
unknown committed
1901
  }
unknown's avatar
unknown committed
1902

unknown's avatar
unknown committed
1903
  DBUG_RETURN(false);
unknown's avatar
unknown committed
1904
}
unknown's avatar
unknown committed
1905

1906

1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918
/**
  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
1919 1920
  @retval false  The subquery was transformed
  @retval true   Error
1921 1922
*/

unknown's avatar
unknown committed
1923
bool
unknown's avatar
unknown committed
1924
Item_in_subselect::row_value_transformer(JOIN *join)
unknown's avatar
unknown committed
1925
{
unknown's avatar
unknown committed
1926
  SELECT_LEX *select_lex= join->select_lex;
1927
  uint cols_num= left_expr->cols();
1928

unknown's avatar
unknown committed
1929
  DBUG_ENTER("Item_in_subselect::row_value_transformer");
unknown's avatar
unknown committed
1930

1931
  // psergey: duplicated_subselect_card_check
1932
  if (select_lex->item_list.elements != cols_num)
1933
  {
1934
    my_error(ER_OPERAND_COLUMNS, MYF(0), cols_num);
unknown's avatar
unknown committed
1935
    DBUG_RETURN(true);
1936 1937
  }

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

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

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

unknown's avatar
unknown committed
1960
    thd->lex->current_select= current;
unknown's avatar
unknown committed
1961 1962 1963 1964 1965 1966 1967 1968 1969
    /*
      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;
1970 1971
  }

unknown's avatar
unknown committed
1972
  DBUG_RETURN(false);
1973 1974 1975 1976
}


/**
1977 1978
  Create the predicates needed to transform a multi-column IN/ALL/ANY
  subselect into a correlated EXISTS via predicate injection.
1979

1980
  @details
unknown's avatar
unknown committed
1981 1982 1983 1984 1985 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
  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)
2016 2017 2018 2019 2020

  @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
2021 2022
  @retval false  If the new conditions were created successfully
  @retval true   Error
2023 2024
*/

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

2041
  DBUG_ENTER("Item_in_subselect::create_row_in_to_exists_cond");
2042 2043 2044

  *where_item= NULL;
  *having_item= NULL;
2045

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

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

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

2168
  if (*where_item)
2169
  {
2170
    if (!(*where_item)->fixed && (*where_item)->fix_fields(thd, 0))
unknown's avatar
unknown committed
2171
      DBUG_RETURN(true);
2172
    (*where_item)->top_level_item();
2173
  }
unknown's avatar
unknown committed
2174

2175
  if (*having_item)
2176
  {
2177 2178 2179
    if (!join_having)
      (*having_item)->name= (char*) in_having_cond;
    if (fix_having(*having_item, select_lex))
unknown's avatar
unknown committed
2180
      DBUG_RETURN(true);
2181
    (*having_item)->top_level_item();
2182
  }
unknown's avatar
unknown committed
2183

unknown's avatar
unknown committed
2184
  DBUG_RETURN(false);
unknown's avatar
unknown committed
2185 2186
}

2187

unknown's avatar
unknown committed
2188
bool
unknown's avatar
unknown committed
2189
Item_in_subselect::select_transformer(JOIN *join)
unknown's avatar
unknown committed
2190
{
2191
  return select_in_like_transformer(join);
2192 2193 2194
}


unknown's avatar
unknown committed
2195
/**
2196 2197
  Create the predicates needed to transform an IN/ALL/ANY subselect into a
  correlated EXISTS via predicate injection.
2198

2199
  @param join_arg  Join object of the subquery.
2200

2201 2202 2203 2204
  @retval FALSE  ok
  @retval TRUE   error
*/

2205 2206
bool Item_in_subselect::create_in_to_exists_cond(JOIN *join_arg)
{
unknown's avatar
unknown committed
2207
  bool res;
2208 2209 2210 2211

  DBUG_ASSERT(engine->engine_type() == subselect_engine::SINGLE_SELECT_ENGINE ||
              engine->engine_type() == subselect_engine::UNION_ENGINE);
  /*
2212
    TODO: the call to init_cond_guards allocates and initializes an
2213 2214 2215
    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.
2216
    If the dependency is removed, the call can be moved to a later phase.
2217 2218 2219 2220 2221 2222 2223 2224 2225 2226
  */
  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));
2227

2228 2229 2230
  /*
    The IN=>EXISTS transformation makes non-correlated subqueries correlated.
  */
2231 2232 2233 2234 2235 2236
  if (!left_expr->const_item() || left_expr->is_expensive())
  {
    join_arg->select_lex->uncacheable|= UNCACHEABLE_DEPENDENT_INJECTED;
    join_arg->select_lex->master_unit()->uncacheable|= 
                                         UNCACHEABLE_DEPENDENT_INJECTED;
  }
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

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

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

2432

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


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

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

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 2498
  /*
    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
2499
  if ((thd_arg->lex->context_analysis_only & CONTEXT_ANALYSIS_ONLY_VIEW) &&
Michael Widenius's avatar
Michael Widenius committed
2500
      left_expr && !left_expr->fixed &&
2501 2502
      left_expr->fix_fields(thd_arg, &left_expr))
    return TRUE;
2503
  else
2504 2505 2506 2507
  if (Item_subselect::fix_fields(thd_arg, ref))
    return TRUE;
  fixed= TRUE;
  return FALSE;
2508 2509
}

2510

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

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

2526

2527
/**
2528 2529
  Try to create and initialize an engine to compute a subselect via
  materialization.
2530 2531

  @details
2532 2533 2534 2535 2536
  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,
2537 2538 2539 2540 2541 2542

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

2543
bool Item_in_subselect::setup_mat_engine()
2544
{
2545 2546
  subselect_hash_sj_engine       *mat_engine= NULL;
  subselect_single_select_engine *select_engine;
2547

2548
  DBUG_ENTER("Item_in_subselect::setup_mat_engine");
2549

2550 2551 2552 2553 2554 2555 2556
  /*
    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;
2557

2558 2559 2560
  /* Create/initialize execution objects. */
  if (!(mat_engine= new subselect_hash_sj_engine(thd, this, select_engine)))
    DBUG_RETURN(TRUE);
2561

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

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


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


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


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

unknown's avatar
unknown committed
2635

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


2651 2652 2653 2654 2655 2656 2657 2658
void subselect_engine::set_thd(THD *thd_arg)
{
  thd= thd_arg;
  if (result)
    result->set_thd(thd_arg);
}


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

2670 2671 2672 2673
int subselect_single_select_engine::get_identifier()
{
  return select_lex->select_number; 
}
unknown's avatar
unknown committed
2674

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

unknown's avatar
unknown committed
2685 2686 2687 2688 2689

void subselect_union_engine::cleanup()
{
  DBUG_ENTER("subselect_union_engine::cleanup");
  unit->reinit_exec_mechanism();
2690
  result->cleanup();
2691 2692 2693
  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
2694
  DBUG_VOID_RETURN;
unknown's avatar
unknown committed
2695
}
2696

unknown's avatar
unknown committed
2697

2698 2699 2700 2701 2702 2703
bool subselect_union_engine::is_executed() const
{
  return unit->executed;
}


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

2725

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


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

2747

2748 2749 2750 2751
/**
  Create and prepare the JOIN object that represents the query execution
  plan for the subquery.

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

int subselect_union_engine::prepare()
{
2810
  return unit->prepare(thd, result, SELECT_NO_UNLOCK);
unknown's avatar
unknown committed
2811 2812
}

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

2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 2838 2839 2840 2841

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


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

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

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

2895
void subselect_uniquesubquery_engine::fix_length_and_dec(Item_cache **row)
2896 2897 2898 2899 2900
{
  //this never should be called
  DBUG_ASSERT(0);
}

2901 2902 2903 2904
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);

2905
int subselect_single_select_engine::exec()
unknown's avatar
unknown committed
2906 2907
{
  DBUG_ENTER("subselect_single_select_engine::exec");
2908 2909 2910 2911

  if (optimize_error)
    DBUG_RETURN(1);

unknown's avatar
unknown committed
2912 2913 2914
  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
2915

2916
  if (!join->optimized)
unknown's avatar
unknown committed
2917
  {
2918 2919 2920
    SELECT_LEX_UNIT *unit= select_lex->master_unit();

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

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

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

3038

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

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

  RETURN
    FALSE - OK
    TRUE  - Error
*/

int subselect_uniquesubquery_engine::scan_table()
3058 3059 3060
{
  int error;
  TABLE *table= tab->table;
3061 3062 3063 3064 3065
  DBUG_ENTER("subselect_uniquesubquery_engine::scan_table");

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

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

3137 3138

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

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

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 3247 3248 3249 3250 3251
/*
  @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;
}


3252 3253 3254 3255 3256
/*
  Execute subselect

  SYNOPSIS
    subselect_uniquesubquery_engine::exec()
3257

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

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

3309 3310 3311
  if (!tab->preread_init_done && tab->preread_init())
    DBUG_RETURN(1);

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

3338
  DBUG_RETURN(error != 0);
3339 3340
}

3341

3342
/*
3343
  TIMOUR: write comment
3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359
*/

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));
3360 3361

  if (error && error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
3362
  {
3363 3364 3365 3366 3367 3368
    /*
      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);
3369 3370
  }

3371 3372 3373 3374 3375 3376 3377
  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);
3378 3379 3380 3381
}



3382
subselect_uniquesubquery_engine::~subselect_uniquesubquery_engine()
3383
{
3384
  /* Tell handler we don't need the index anymore */
3385 3386
  //psergey-merge-todo: the following was gone in 6.0:
 //psergey-merge: don't need this after all: tab->table->file->ha_index_end();
3387 3388
}

3389

3390 3391 3392 3393
/*
  Index-lookup subselect 'engine' - run the subquery

  SYNOPSIS
3394
    subselect_indexsubquery_engine:exec()
3395 3396 3397
      full_scan 

  DESCRIPTION
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 3426 3427 3428 3429 3430
    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.
3431

3432 3433 3434 3435
    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.
3436 3437 3438 3439 3440 3441

  RETURN
    0
    1
*/

3442
int subselect_indexsubquery_engine::exec()
3443
{
3444
  DBUG_ENTER("subselect_indexsubquery_engine");
3445
  int error;
3446
  bool null_finding= 0;
3447
  TABLE *table= tab->table;
3448

3449
  ((Item_in_subselect *) item)->value= 0;
3450 3451
  empty_result_set= TRUE;
  null_keypart= 0;
3452
  table->status= 0;
3453

3454 3455
  if (check_null)
  {
3456
    /* We need to check for NULL if there wasn't a matching value */
3457
    *tab->ref.null_ref_key= 0;			// Search first for not null
3458 3459 3460
    ((Item_in_subselect *) item)->was_null= 0;
  }

3461 3462 3463 3464
  /* Copy the ref key and check for nulls... */
  if (copy_ref_key())
    DBUG_RETURN(1);

3465 3466 3467 3468 3469 3470 3471 3472 3473 3474
  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);
  }

3475 3476 3477
  if (!tab->preread_init_done && tab->preread_init())
    DBUG_RETURN(1);

3478 3479
  if (null_keypart)
    DBUG_RETURN(scan_table());
3480 3481

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

3532

unknown's avatar
unknown committed
3533 3534
uint subselect_single_select_engine::cols()
{
3535 3536 3537 3538
  //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
3539 3540
}

unknown's avatar
unknown committed
3541

unknown's avatar
unknown committed
3542 3543
uint subselect_union_engine::cols()
{
3544 3545
  DBUG_ASSERT(unit->is_prepared());  // should be called after fix_fields()
  return unit->types.elements;
unknown's avatar
unknown committed
3546 3547
}

unknown's avatar
unknown committed
3548

3549
uint8 subselect_single_select_engine::uncacheable()
3550 3551 3552 3553
{
  return select_lex->uncacheable;
}

unknown's avatar
unknown committed
3554

3555
uint8 subselect_union_engine::uncacheable()
3556 3557 3558 3559
{
  return unit->uncacheable;
}

unknown's avatar
unknown committed
3560

unknown's avatar
unknown committed
3561 3562 3563 3564 3565 3566 3567 3568 3569
void subselect_single_select_engine::exclude()
{
  select_lex->master_unit()->exclude_level();
}

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

unknown's avatar
unknown committed
3571

3572
void subselect_uniquesubquery_engine::exclude()
3573 3574 3575 3576
{
  //this never should be called
  DBUG_ASSERT(0);
}
3577 3578


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


table_map subselect_single_select_engine::upper_select_const_tables()
{
3597
  return calc_const_tables(select_lex->outer_select()->leaf_tables);
3598 3599
}

unknown's avatar
merge  
unknown committed
3600

3601 3602
table_map subselect_union_engine::upper_select_const_tables()
{
3603
  return calc_const_tables(unit->outer_select()->leaf_tables);
3604
}
unknown's avatar
merge  
unknown committed
3605 3606


3607 3608
void subselect_single_select_engine::print(String *str,
                                           enum_query_type query_type)
unknown's avatar
unknown committed
3609
{
3610
  select_lex->print(thd, str, query_type);
unknown's avatar
unknown committed
3611 3612 3613
}


3614
void subselect_union_engine::print(String *str, enum_query_type query_type)
unknown's avatar
unknown committed
3615
{
3616
  unit->print(str, query_type);
unknown's avatar
unknown committed
3617 3618 3619
}


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

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

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

unknown's avatar
unknown committed
3697 3698
/**
  change select_result object of engine.
3699

unknown's avatar
unknown committed
3700 3701
  @param si		new subselect Item
  @param res		new select_result object
3702
  @param temp           temporary assignment
3703

unknown's avatar
unknown committed
3704
  @retval
unknown's avatar
unknown committed
3705
    FALSE OK
unknown's avatar
unknown committed
3706
  @retval
unknown's avatar
unknown committed
3707
    TRUE  error
3708 3709
*/

3710 3711 3712 3713
bool
subselect_single_select_engine::change_result(Item_subselect *si,
                                              select_result_interceptor *res,
                                              bool temp)
3714 3715
{
  item= si;
3716
  if (temp)
3717 3718 3719 3720 3721 3722
  {
    /*
      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.
    */
3723
    thd->change_item_tree((Item**) &result, (Item*)res);
3724
  }
3725 3726
  else
    result= res;
3727 3728 3729 3730 3731 3732 3733 3734 3735

  /*
    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);
3736 3737 3738
}


unknown's avatar
unknown committed
3739 3740
/**
  change select_result object of engine.
3741

unknown's avatar
unknown committed
3742 3743
  @param si		new subselect Item
  @param res		new select_result object
3744

unknown's avatar
unknown committed
3745
  @retval
unknown's avatar
unknown committed
3746
    FALSE OK
unknown's avatar
unknown committed
3747
  @retval
unknown's avatar
unknown committed
3748
    TRUE  error
3749 3750
*/

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


unknown's avatar
unknown committed
3765 3766
/**
  change select_result emulation, never should be called.
3767

unknown's avatar
unknown committed
3768 3769
  @param si		new subselect Item
  @param res		new select_result object
3770

unknown's avatar
unknown committed
3771
  @retval
unknown's avatar
unknown committed
3772
    FALSE OK
unknown's avatar
unknown committed
3773
  @retval
unknown's avatar
unknown committed
3774
    TRUE  error
3775 3776
*/

3777 3778 3779 3780 3781
bool
subselect_uniquesubquery_engine::change_result(Item_subselect *si,
                                               select_result_interceptor *res,
                                               bool temp
                                               __attribute__((unused)))
3782 3783
{
  DBUG_ASSERT(0);
unknown's avatar
unknown committed
3784
  return TRUE;
3785
}
3786 3787


unknown's avatar
unknown committed
3788 3789
/**
  Report about presence of tables in subquery.
3790

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


3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817
/*
  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
3818 3819
/**
  Report about presence of tables in subquery.
3820

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

unknown's avatar
unknown committed
3840
  @retval
3841
    TRUE  there are not tables used in subquery
unknown's avatar
unknown committed
3842
  @retval
3843 3844 3845 3846 3847 3848
    FALSE there are some tables in subquery
*/

bool subselect_uniquesubquery_engine::no_tables()
{
  /* returning value is correct, but this method should never be called */
3849
  DBUG_ASSERT(FALSE);
3850 3851
  return 0;
}
3852 3853 3854 3855 3856 3857 3858


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


3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872
/**
  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.
3873 3874 3875 3876 3877 3878 3879 3880 3881

  @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
3882 3883
*/

3884 3885
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_schema()
3886 3887 3888 3889
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;

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


/**
  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.
3926 3927 3928

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

3931 3932
subselect_hash_sj_engine::exec_strategy
subselect_hash_sj_engine::get_strategy_using_data()
3933 3934 3935 3936 3937 3938
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
  select_materialize_with_stats *result_sink=
    (select_materialize_with_stats *) result;
  Item *outer_col;

3939 3940 3941 3942 3943 3944
  /*
    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;
3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960

  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
3961
    if (result_sink->get_null_count_of_col(i) == tmp_table->file->stats.records)
3962
      ++count_null_only_columns;
unknown's avatar
unknown committed
3963 3964
    if (result_sink->get_null_count_of_col(i))
      ++count_columns_with_nulls;
3965 3966 3967 3968
  }

  /* If no column contains NULLs use regular hash index lookups. */
  if (!count_partial_match_columns)
3969 3970 3971
    return COMPLETE_MATCH;
  return PARTIAL_MATCH;
}
3972

3973 3974 3975 3976 3977 3978

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)
{
3979
  ulonglong pm_buff_size;
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 4039 4040 4041 4042 4043

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

4044
ulonglong subselect_hash_sj_engine::rowid_merge_buff_size(
4045 4046 4047
  bool has_non_null_key, bool has_covering_null_row,
  MY_BITMAP *partial_match_key_parts)
{
4048 4049
  /* Total size of all buffers used by partial matching. */
  ulonglong buff_size;
4050 4051 4052 4053
  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
4054
  ha_rows max_null_row;
4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076

  /* 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
4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088
      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);
4089 4090 4091 4092
    }
  }

  return buff_size;
4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115
}


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


4116 4117 4118 4119
/**
  Create all structures needed for IN execution that can live between PS
  reexecution.

4120
  @param tmp_columns the items that produce the data for the temp table
4121 4122
  @param subquery_id subquery's identifier (to make "<subquery%d>" name for
                                            EXPLAIN)
4123 4124

  @details
4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137
  - 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
4138
bool subselect_hash_sj_engine::init(List<Item> *tmp_columns, uint subquery_id)
4139
{
4140
  select_union *result_sink;
4141 4142 4143
  /* Options to create_tmp_table. */
  ulonglong tmp_create_options= thd->options | TMP_TABLE_ALL_COLUMNS;
                             /* | TMP_TABLE_FORCE_MYISAM; TIMOUR: force MYISAM */
4144

4145
  DBUG_ENTER("subselect_hash_sj_engine::init");
4146

4147 4148 4149 4150 4151
  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);
4152 4153 4154 4155 4156 4157

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

4184
  result_sink->get_tmp_table_param()->materialized_subquery= true;
Igor Babaev's avatar
Igor Babaev committed
4185 4186 4187 4188 4189
  if (item->substype() == Item_subselect::IN_SUBS && 
      ((Item_in_subselect*)item)->is_jtbm_merged)
  {
    result_sink->get_tmp_table_param()->force_not_null_cols= true;
  }
4190 4191
  if (result_sink->create_result_table(thd, tmp_columns, TRUE,
                                       tmp_create_options,
4192
				       name, TRUE, TRUE))
4193 4194
    DBUG_RETURN(TRUE);

4195 4196
  tmp_table= result_sink->table;
  result= result_sink;
4197 4198

  /*
4199 4200 4201 4202 4203 4204 4205
    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.
4206 4207 4208
  */
  if (tmp_table->s->keys == 0)
  {
4209 4210
    //fprintf(stderr, "Q: %s\n", current_thd->query());
    DBUG_ASSERT(0);
4211 4212 4213 4214 4215
    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);
4216
    tmp_table= NULL;
4217 4218 4219 4220 4221 4222 4223 4224 4225
    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.
  */
4226 4227 4228
  DBUG_ASSERT(tmp_table->s->keys == 1 &&
              ((Item_in_subselect *) item)->left_expr->cols() ==
              tmp_table->key_info->key_parts);
4229

4230 4231 4232
  if (make_semi_join_conds() ||
      /* A unique_engine is used both for complete and partial matching. */
      !(lookup_engine= make_unique_engine()))
4233
    DBUG_RETURN(TRUE);
4234

4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245
  /*
    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);

4246 4247
  DBUG_RETURN(FALSE);
}
4248 4249


4250 4251 4252
/*
  Create an artificial condition to post-filter those rows matched by index
  lookups that cannot be distinguished by the index lookup procedure.
4253

4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268
  @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()
{
4269 4270 4271 4272 4273
  /*
    Table reference for tmp_table that is used to resolve column references
    (Item_fields) to columns in tmp_table.
  */
  TABLE_LIST *tmp_table_ref;
4274 4275 4276 4277 4278 4279 4280 4281 4282 4283
  /* 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);

4284 4285 4286
  if (!(tmp_table_ref= (TABLE_LIST*) thd->alloc(sizeof(TABLE_LIST))))
    DBUG_RETURN(TRUE);

4287
  tmp_table_ref->init_one_table("", tmp_table->alias.c_ptr(), TL_READ);
4288 4289
  tmp_table_ref->table= tmp_table;

4290
  context= new Name_resolution_context;
4291 4292 4293
  context->init();
  context->first_name_resolution_table=
    context->last_name_resolution_table= tmp_table_ref;
4294
  semi_join_conds_context= context;
4295
  
4296
  for (uint i= 0; i < item_in->left_expr->cols(); i++)
4297 4298 4299 4300 4301
  {
    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;

4302 4303 4304 4305
    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)))
4306
    {
4307 4308
      delete semi_join_conds;
      semi_join_conds= NULL;
4309 4310 4311
      DBUG_RETURN(TRUE);
    }
  }
4312
  if (semi_join_conds->fix_fields(thd, (Item**)&semi_join_conds))
4313 4314 4315 4316 4317 4318 4319
    DBUG_RETURN(TRUE);

  DBUG_RETURN(FALSE);
}


/**
4320 4321 4322 4323 4324 4325 4326 4327 4328 4329 4330 4331 4332 4333
  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
4334
  Item_iterator_row it(item_in->left_expr);
4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350
  /* 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
4351
  tab->table= tmp_table;
4352
  tab->preread_init_done= FALSE;
unknown's avatar
unknown committed
4353
  tab->ref.tmp_table_index_lookup_init(thd, tmp_key, it, FALSE);
4354 4355 4356 4357 4358 4359

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


4360 4361 4362 4363 4364 4365 4366
subselect_hash_sj_engine::~subselect_hash_sj_engine()
{
  delete lookup_engine;
  delete result;
  if (tmp_table)
    free_tmp_table(thd, tmp_table);
}
4367 4368


4369
int subselect_hash_sj_engine::prepare()
4370 4371 4372 4373 4374
{
  /*
    Create and optimize the JOIN that will be used to materialize
    the subquery if not yet created.
  */
4375
  return materialize_engine->prepare();
4376 4377 4378 4379 4380 4381
}


/**
  Cleanup performed after each PS execution.

4382
  @details
4383 4384 4385 4386 4387
  Called in the end of JOIN::prepare for PS from Item_subselect::cleanup.
*/

void subselect_hash_sj_engine::cleanup()
{
4388
  enum_engine_type lookup_engine_type= lookup_engine->engine_type();
4389
  is_materialized= FALSE;
4390 4391 4392 4393 4394
  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;
4395
  materialize_engine->cleanup();
4396 4397 4398 4399 4400 4401
  /*
    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;
4402 4403 4404 4405 4406 4407 4408 4409 4410 4411 4412 4413 4414 4415 4416 4417
  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. */
4418 4419 4420
  DBUG_ASSERT(tmp_table);
  free_tmp_table(thd, tmp_table);
  tmp_table= NULL;
4421 4422 4423
}


4424 4425 4426 4427 4428 4429
/*
  Get fanout produced by tables specified in the table_map
*/

double get_fanout_with_deps(JOIN *join, table_map tset)
{
4430 4431 4432 4433
  /* Handle the case of "Impossible WHERE" */
  if (join->table_count == 0)
    return 0.0;

4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458
  /* 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))
  {
4459 4460 4461 4462 4463 4464 4465
    /* 
      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 && 
4466 4467 4468 4469 4470
        tab->records_read != 0)
    {
      fanout *= rows2double(tab->records_read);
    }
  } 
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 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556
  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


4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574
/*
  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
*/

4575
double get_post_group_estimate(JOIN* join, double join_op_rows)
4576 4577 4578 4579 4580 4581 4582 4583
{
  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)
4584 4585 4586 4587
    {
      /* Each join output record will be in its own group */
      return join_op_rows;
    }
4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599
    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);
4600 4601 4602

#if 0
  /* The following will be needed when making use of index stats: */
4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620
  /* 
    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);
4621 4622
#endif

4623 4624 4625 4626
  return out_rows;
}


4627 4628 4629
/**
  Execute a subquery IN predicate via materialization.

4630
  @details
4631 4632 4633 4634 4635 4636 4637 4638 4639 4640
  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;
4641
  SELECT_LEX *save_select= thd->lex->current_select;
4642
  subselect_partial_match_engine *pm_engine= NULL;
4643
  int res= 0;
4644 4645 4646 4647 4648 4649 4650

  DBUG_ENTER("subselect_hash_sj_engine::exec");

  /*
    Optimize and materialize the subquery during the first execution of
    the subquery predicate.
  */
4651
  thd->lex->current_select= materialize_engine->select_lex;
4652 4653
  /* The subquery should be optimized, and materialized only once. */
  DBUG_ASSERT(materialize_join->optimized && !is_materialized);
4654
  materialize_join->exec();
4655 4656
  if ((res= test(materialize_join->error || thd->is_fatal_error ||
                 thd->is_error())))
4657
    goto err;
4658

4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 4671 4672 4673 4674 4675 4676 4677 4678
  /*
    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. */
4679 4680
    item_in->reset();
    item_in->make_const();
4681 4682 4683 4684
    item_in->set_first_execution();
    DBUG_RETURN(FALSE);
  }

4685 4686 4687 4688 4689 4690 4691 4692 4693
  /*
    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();
4694 4695
  if (strategy == PARTIAL_MATCH)
  {
4696
    uint count_pm_keys; /* Total number of keys needed for partial matching. */
unknown's avatar
unknown committed
4697 4698 4699 4700
    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;
4701 4702
    select_materialize_with_stats *result_sink=
      (select_materialize_with_stats *) result;
unknown's avatar
unknown committed
4703
    uint field_count= tmp_table->s->fields;
4704

unknown's avatar
unknown committed
4705 4706 4707 4708 4709 4710 4711 4712
    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);
4713

unknown's avatar
unknown committed
4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727
    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
4728 4729 4730 4731 4732 4733 4734
    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;
4735 4736
    else
      count_pm_keys= count_partial_match_columns - count_null_only_columns +
unknown's avatar
unknown committed
4737
                     (nn_key_parts ? 1 : 0);
4738

4739
    choose_partial_match_strategy(test(nn_key_parts),
unknown's avatar
unknown committed
4740
                                  has_covering_null_row,
4741 4742 4743 4744
                                  &partial_match_key_parts);
    DBUG_ASSERT(strategy == PARTIAL_MATCH_MERGE ||
                strategy == PARTIAL_MATCH_SCAN);
    if (strategy == PARTIAL_MATCH_MERGE)
4745
    {
4746
      pm_engine=
unknown's avatar
unknown committed
4747
        new subselect_rowid_merge_engine(thd, (subselect_uniquesubquery_engine*)
4748 4749
                                         lookup_engine, tmp_table,
                                         count_pm_keys,
unknown's avatar
unknown committed
4750 4751
                                         has_covering_null_row,
                                         has_covering_null_columns,
unknown's avatar
unknown committed
4752
                                         count_columns_with_nulls,
4753 4754 4755 4756 4757 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767
                                         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;
      }
4768
    }
4769 4770

    if (strategy == PARTIAL_MATCH_SCAN)
4771
    {
4772
      if (!(pm_engine=
unknown's avatar
unknown committed
4773
            new subselect_table_scan_engine(thd, (subselect_uniquesubquery_engine*)
4774 4775 4776
                                            lookup_engine, tmp_table,
                                            item, result,
                                            semi_join_conds->argument_list(),
unknown's avatar
unknown committed
4777
                                            has_covering_null_row,
unknown's avatar
unknown committed
4778 4779
                                            has_covering_null_columns,
                                            count_columns_with_nulls)))
4780 4781 4782 4783 4784
      {
        /* This is an irrecoverable error. */
        res= 1;
        goto err;
      }
4785 4786 4787
    }
  }

4788 4789
  if (pm_engine)
    lookup_engine= pm_engine;
4790 4791 4792 4793 4794
  item_in->change_engine(lookup_engine);

err:
  thd->lex->current_select= save_select;
  DBUG_RETURN(res);
4795 4796 4797 4798 4799 4800 4801 4802 4803 4804 4805 4806
}


/**
  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(" ), "));
4807 4808 4809

  if (lookup_engine)
    lookup_engine->print(str, query_type);
4810 4811
  else
    str->append(STRING_WITH_LEN(
4812
           "<engine selected at execution time>"
4813 4814
         ));
}
4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832

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,
4833 4834
                                             select_result_interceptor *res,
                                             bool temp __attribute__((unused)))
4835 4836 4837 4838 4839 4840
{
  DBUG_ASSERT(FALSE);
  return TRUE;
}


4841 4842 4843 4844
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),
4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865
    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()
{
4866 4867
  my_free((char*) key_buff, MYF(0));
  bitmap_free(&null_key);
4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884
}


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

4885

4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902
/*
  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
4903 4904 4905
  if (!key_columns || !compare_pred)
    return TRUE; /* Revert to table scan partial match. */

4906 4907 4908 4909 4910 4911 4912 4913 4914 4915 4916 4917 4918 4919 4920 4921 4922 4923 4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958
  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;
}


4959 4960 4961 4962
/*
  Allocate the buffers for both the row number, and the NULL-bitmap indexes.
*/

4963 4964 4965 4966
bool Ordered_key::alloc_keys_buffers()
{
  DBUG_ASSERT(key_buff_elements > 0);

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


5048
/*
5049 5050 5051
  The fraction of rows that do not contain NULL in the columns indexed by
  this key.

5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063
  @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);
}


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 5172 5173 5174 5175 5176 5177 5178 5179 5180 5181
/*
  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;
}


5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 5205 5206 5207 5208 5209
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('}');
}


5210
subselect_partial_match_engine::subselect_partial_match_engine(
unknown's avatar
unknown committed
5211
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5212 5213 5214
  TABLE *tmp_table_arg, Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
5215
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
5216 5217
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
unknown's avatar
unknown committed
5218
  :subselect_engine(thd_arg, item_arg, result_arg),
5219 5220
   tmp_table(tmp_table_arg), lookup_engine(engine_arg),
   equi_join_conds(equi_join_conds_arg),
unknown's avatar
unknown committed
5221
   has_covering_null_row(has_covering_null_row_arg),
unknown's avatar
unknown committed
5222 5223
   has_covering_null_columns(has_covering_null_columns_arg),
   count_columns_with_nulls(count_columns_with_nulls_arg)
5224 5225 5226 5227 5228 5229
{}


int subselect_partial_match_engine::exec()
{
  Item_in_subselect *item_in= (Item_in_subselect *) item;
unknown's avatar
unknown committed
5230
  int copy_res, lookup_res;
5231 5232

  /* Try to find a matching row by index lookup. */
unknown's avatar
unknown committed
5233 5234
  copy_res= lookup_engine->copy_ref_key_simple();
  if (copy_res == -1)
5235 5236 5237 5238 5239 5240
  {
    /* 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
5241
  else if (copy_res == 0)
5242 5243
  {
    /* Search for a complete match. */
unknown's avatar
unknown committed
5244
    if ((lookup_res= lookup_engine->index_lookup()))
5245 5246 5247 5248
    {
      /* An error occured during lookup(). */
      item_in->value= 0;
      item_in->null_value= 0;
unknown's avatar
unknown committed
5249
      return lookup_res;
5250
    }
unknown's avatar
unknown committed
5251
    else if (item_in->value || !count_columns_with_nulls)
5252 5253 5254
    {
      /*
        A complete match was found, the result of IN is TRUE.
unknown's avatar
unknown committed
5255 5256 5257
        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.
5258 5259 5260 5261 5262 5263
        Notice: (this->item == lookup_engine->item)
      */
      return 0;
    }
  }

unknown's avatar
unknown committed
5264
  if (has_covering_null_row)
5265 5266 5267 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 5286 5287 5288 5289 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 5305 5306 5307 5308 5309 5310 5311 5312 5313 5314 5315 5316 5317 5318 5319
  {
    /*
      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
5320
    DBUG_ASSERT(FALSE);
5321 5322 5323 5324
  */
}


5325 5326 5327
/*
  @param non_null_key_parts  
  @param partial_match_key_parts  A union of all single-column NULL key parts.
5328 5329 5330 5331

  @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
5332 5333 5334 5335 5336 5337 5338 5339 5340 5341 5342 5343
*/

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
5344
  uint cur_keyid= 0;
5345 5346 5347
  Item_in_subselect *item_in= (Item_in_subselect*) item;
  int error;

unknown's avatar
unknown committed
5348
  if (merge_keys_count == 0)
5349
  {
unknown's avatar
unknown committed
5350 5351
    DBUG_ASSERT(bitmap_bits_set(partial_match_key_parts) == 0 ||
                has_covering_null_row);
5352 5353 5354 5355
    /* There is nothing to initialize, we will only do regular lookups. */
    return FALSE;
  }

unknown's avatar
unknown committed
5356 5357 5358 5359 5360 5361 5362
  /*
    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));
5363 5364
  /*
    Allocate buffers to hold the merged keys and the mapping between rowids and
unknown's avatar
unknown committed
5365 5366
    row numbers. All small buffers are allocated in the runtime memroot. Big
    buffers are allocated from the OS via malloc.
5367
  */
unknown's avatar
unknown committed
5368
  if (!(merge_keys= (Ordered_key**) thd->alloc(merge_keys_count *
5369
                                               sizeof(Ordered_key*))) ||
unknown's avatar
unknown committed
5370 5371
      !(null_bitmaps= (MY_BITMAP**) thd->alloc(merge_keys_count *
                                               sizeof(MY_BITMAP*))) ||
5372 5373
      !(row_num_to_rowid= (uchar*) my_malloc((size_t)(row_count * rowid_length),
        MYF(MY_WME))))
5374 5375 5376 5377 5378
    return TRUE;

  /* Create the only non-NULL key if there is any. */
  if (non_null_key_parts)
  {
unknown's avatar
unknown committed
5379
    non_null_key= new Ordered_key(cur_keyid, tmp_table, item_in->left_expr,
5380 5381 5382
                                  0, 0, 0, row_num_to_rowid);
    if (non_null_key->init(non_null_key_parts))
      return TRUE;
unknown's avatar
unknown committed
5383 5384 5385
    merge_keys[cur_keyid]= non_null_key;
    merge_keys[cur_keyid]->first();
    ++cur_keyid;
5386 5387 5388
  }

  /*
unknown's avatar
unknown committed
5389 5390
    If all nullable columns contain NULLs, the only key that is needed is the
    only non-NULL key that is already created above.
5391
  */
unknown's avatar
unknown committed
5392
  if (!has_covering_null_columns)
5393
  {
unknown's avatar
unknown committed
5394 5395
    if (bitmap_init_memroot(&matching_keys, merge_keys_count, thd->mem_root) ||
        bitmap_init_memroot(&matching_outer_cols, merge_keys_count, thd->mem_root))
5396 5397 5398 5399 5400 5401 5402 5403
      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
5404 5405 5406
      /* 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)
5407 5408
        continue;

unknown's avatar
unknown committed
5409
      merge_keys[cur_keyid]= new Ordered_key(
5410 5411 5412 5413 5414 5415
                                     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
5416 5417 5418
      if (merge_keys[cur_keyid]->init(i))
        return TRUE;
      merge_keys[cur_keyid]->first();
5419
      ++cur_keyid;
5420 5421
    }
  }
unknown's avatar
unknown committed
5422
  DBUG_ASSERT(cur_keyid == merge_keys_count);
5423 5424

  /* Populate the indexes with data from the temporary table. */
5425 5426
  if (tmp_table->file->ha_rnd_init_with_error(1))
    return TRUE;
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 5453 5454 5455 5456 5457 5458 5459 5460 5461 5462
  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
5463
    for (uint i= (non_null_key ? 1 : 0); i < merge_keys_count; i++)
5464 5465 5466 5467 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478
    {
      /*
        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();

5479
  /* Sort all the keys by their NULL selectivity. */
unknown's avatar
unknown committed
5480
  my_qsort(merge_keys, merge_keys_count, sizeof(Ordered_key*),
5481 5482
           (qsort_cmp) cmp_keys_by_null_selectivity);

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

unknown's avatar
unknown committed
5487
  if (init_queue(&pq, merge_keys_count, 0, FALSE,
5488 5489
                 subselect_rowid_merge_engine::cmp_keys_by_cur_rownum, NULL,
                 0, 0))
5490 5491 5492 5493 5494 5495 5496 5497
    return TRUE;

  return FALSE;
}


subselect_rowid_merge_engine::~subselect_rowid_merge_engine()
{
5498
  /* None of the resources below is allocated if there are no ordered keys. */
unknown's avatar
unknown committed
5499
  if (merge_keys_count)
5500 5501
  {
    my_free((char*) row_num_to_rowid, MYF(0));
unknown's avatar
unknown committed
5502
    for (uint i= 0; i < merge_keys_count; i++)
5503 5504 5505 5506 5507
      delete merge_keys[i];
    delete_queue(&pq);
    if (tmp_table->file->inited == handler::RND)
      tmp_table->file->ha_rnd_end();
  }
5508 5509 5510 5511 5512
}


void subselect_rowid_merge_engine::cleanup()
{
5513 5514 5515
}


5516
/*
5517 5518 5519 5520 5521 5522 5523 5524 5525
  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
5526 5527 5528
*/

int
5529 5530
subselect_rowid_merge_engine::cmp_keys_by_null_selectivity(Ordered_key **k1,
                                                           Ordered_key **k2)
5531
{
5532 5533 5534
  double k1_sel= (*k1)->null_selectivity();
  double k2_sel= (*k2)->null_selectivity();
  if (k1_sel < k2_sel)
5535
    return 1;
5536 5537 5538
  if (k1_sel > k2_sel)
    return -1;
  return 0;
5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554 5555 5556 5557 5558 5559
}


/*
*/

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
5560 5561 5562 5563
  @note
  There is no need to check the columns that contain only NULLs, because
  those are guaranteed to match.

5564 5565 5566 5567 5568 5569
  @retval TRUE if a NULL row exists
  @retval FALSE otherwise
*/

bool subselect_rowid_merge_engine::test_null_row(rownum_t row_num)
{
5570
  Ordered_key *cur_key;
unknown's avatar
unknown committed
5571
  for (uint i = 0; i < merge_keys_count; i++)
5572
  {
5573
    cur_key= merge_keys[i];
unknown's avatar
unknown committed
5574
    if (bitmap_is_set(&matching_keys, cur_key->get_keyid()))
5575 5576
    {
      /*
unknown's avatar
unknown committed
5577 5578
        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.
5579 5580 5581
      */
      continue;
    }
5582
    if (!cur_key->is_null(row_num))
5583 5584 5585 5586 5587 5588
      return FALSE;
  }
  return TRUE;
}


unknown's avatar
unknown committed
5589 5590
/**
  Test if a subset of NULL-able columns contains a row of NULLs.
unknown's avatar
unknown committed
5591 5592
  @retval TRUE  if such a row exists
  @retval FALSE no complementing null row
unknown's avatar
unknown committed
5593 5594 5595 5596 5597 5598 5599
*/

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
5600
  uint count_null_keys, i;
unknown's avatar
unknown committed
5601 5602
  Ordered_key *cur_key;

unknown's avatar
unknown committed
5603
  if (!count_columns_with_nulls)
unknown's avatar
unknown committed
5604 5605
  {
    /*
unknown's avatar
unknown committed
5606 5607
      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
5608
    */
unknown's avatar
unknown committed
5609
    return FALSE;
unknown's avatar
unknown committed
5610 5611
  }

unknown's avatar
unknown committed
5612
  for (i= (non_null_key ? 1 : 0), count_null_keys= 0; i < merge_keys_count; i++)
unknown's avatar
unknown committed
5613 5614 5615 5616
  {
    cur_key= merge_keys[i];
    if (bitmap_is_set(keys_to_complement, cur_key->get_keyid()))
      continue;
unknown's avatar
unknown committed
5617 5618 5619 5620 5621
    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
5622 5623 5624 5625
    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
5626
    null_bitmaps[count_null_keys++]= cur_key->get_null_key();
unknown's avatar
unknown committed
5627 5628 5629 5630 5631 5632 5633 5634 5635 5636
  }

  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
5637
                                    (uint)highest_min_row, (uint)lowest_max_row);
unknown's avatar
unknown committed
5638 5639 5640
}


5641 5642 5643 5644 5645 5646 5647 5648 5649 5650 5651 5652
/*
  @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
5653
  uint max_null_in_any_row=
unknown's avatar
unknown committed
5654
    ((select_materialize_with_stats *) result)->get_max_nulls_in_row();
5655
  bool res= FALSE;
5656 5657 5658

  /* 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
5659 5660
  /* The prioryty queue for keys must be empty. */
  DBUG_ASSERT(!pq.elements);
5661 5662

  /* All data accesses during execution are via handler::ha_rnd_pos() */
5663 5664 5665 5666 5667
  if (tmp_table->file->ha_rnd_init_with_error(0))
  {
    res= FALSE;
    goto end;
  }
5668

5669 5670
  /* Check if there is a match for the columns of the only non-NULL key. */
  if (non_null_key && !non_null_key->lookup())
5671 5672 5673 5674
  {
    res= FALSE;
    goto end;
  }
5675 5676

  /*
unknown's avatar
unknown committed
5677 5678 5679 5680
    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)
5681 5682 5683 5684
  {
    res= TRUE;
    goto end;
  }
5685 5686 5687 5688 5689 5690 5691

  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
5692
  for (uint i= test(non_null_key); i < merge_keys_count; i++)
5693 5694
  {
    DBUG_ASSERT(merge_keys[i]->get_column_count() == 1);
unknown's avatar
unknown committed
5695
    if (merge_keys[i]->get_search_key(0)->null_value)
5696 5697
    {
      ++count_nulls_in_search_key;
5698
      bitmap_set_bit(&matching_outer_cols, merge_keys[i]->get_keyid());
5699 5700 5701 5702 5703 5704 5705
    }
    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
5706 5707
    nullable columns (above we guarantee there is a match for the non-null
    coumns), the result is UNKNOWN.
5708
  */
unknown's avatar
unknown committed
5709
  if (count_nulls_in_search_key == merge_keys_count - test(non_null_key))
5710 5711 5712 5713
  {
    res= TRUE;
    goto end;
  }
5714

unknown's avatar
unknown committed
5715 5716 5717 5718 5719 5720 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731
  /*
    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;
  }

5732 5733
  /*
    If there is no NULL (sub)row that covers all NULL columns, and there is no
unknown's avatar
unknown committed
5734 5735 5736 5737
    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.
5738
  */
unknown's avatar
unknown committed
5739 5740 5741 5742
  if (!count_nulls_in_search_key &&
      (!pq.elements ||
       (pq.elements == 1 && non_null_key &&
        max_null_in_any_row < merge_keys_count-1)))
5743
  {
unknown's avatar
unknown committed
5744
    if (!pq.elements)
unknown's avatar
unknown committed
5745
    {
unknown's avatar
unknown committed
5746 5747 5748 5749 5750 5751
      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
5752
    }
5753 5754 5755
    res= FALSE;
    goto end;
  }
5756 5757 5758

  DBUG_ASSERT(pq.elements);

unknown's avatar
unknown committed
5759
  min_key= (Ordered_key*) queue_remove_top(&pq);
5760
  min_row_num= min_key->current();
5761
  bitmap_set_bit(&matching_keys, min_key->get_keyid());
5762 5763 5764 5765 5766 5767 5768 5769 5770 5771
  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.
    */
5772 5773
    res= test_null_row(min_row_num);
    goto end;
5774 5775 5776 5777
  }

  while (TRUE)
  {
unknown's avatar
unknown committed
5778
    cur_key= (Ordered_key*) queue_remove_top(&pq);
5779 5780 5781
    cur_row_num= cur_key->current();

    if (cur_row_num == min_row_num)
5782
      bitmap_set_bit(&matching_keys, cur_key->get_keyid());
5783 5784 5785 5786 5787
    else
    {
      /* Follows from the correct use of priority queue. */
      DBUG_ASSERT(cur_row_num > min_row_num);
      if (test_null_row(min_row_num))
5788 5789 5790 5791
      {
        res= TRUE;
        goto end;
      }
5792 5793 5794 5795
      else
      {
        min_key= cur_key;
        min_row_num= cur_row_num;
unknown's avatar
unknown committed
5796
        bitmap_clear_all(&matching_keys);
5797
        bitmap_set_bit(&matching_keys, min_key->get_keyid());
5798 5799 5800 5801 5802 5803 5804 5805 5806 5807
        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. */
5808 5809
      res= test_null_row(min_row_num);
      goto end;
5810 5811 5812
    }
  }

5813
  /* We should never get here - all branches must be handled explicitly above. */
5814
  DBUG_ASSERT(FALSE);
5815 5816

end:
unknown's avatar
unknown committed
5817 5818
  if (!has_covering_null_columns)
    bitmap_clear_all(&matching_keys);
unknown's avatar
unknown committed
5819
  queue_remove_all(&pq);
5820 5821
  tmp_table->file->ha_rnd_end();
  return res;
5822 5823 5824
}


5825
subselect_table_scan_engine::subselect_table_scan_engine(
unknown's avatar
unknown committed
5826
  THD *thd_arg, subselect_uniquesubquery_engine *engine_arg,
5827 5828 5829 5830
  TABLE *tmp_table_arg,
  Item_subselect *item_arg,
  select_result_interceptor *result_arg,
  List<Item> *equi_join_conds_arg,
unknown's avatar
unknown committed
5831
  bool has_covering_null_row_arg,
unknown's avatar
unknown committed
5832 5833
  bool has_covering_null_columns_arg,
  uint count_columns_with_nulls_arg)
unknown's avatar
unknown committed
5834
  :subselect_partial_match_engine(thd_arg, engine_arg, tmp_table_arg, item_arg,
5835
                                  result_arg, equi_join_conds_arg,
unknown's avatar
unknown committed
5836
                                  has_covering_null_row_arg,
unknown's avatar
unknown committed
5837 5838
                                  has_covering_null_columns_arg,
                                  count_columns_with_nulls_arg)
5839
{}
5840

5841 5842 5843 5844 5845 5846 5847

/*
  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
5848
  {
5849 5850
    count_matches= 0;
    for each row element row_i[j]
5851
    {
5852 5853
      if (outer_ref[j] is NULL || row_i[j] is NULL || outer_ref[j] == row_i[j])
        ++count_matches;
5854
    }
5855 5856
    if (count_matches == outer_ref.elements)
      return TRUE
5857
  }
5858 5859
  return FALSE
*/
5860

5861 5862 5863 5864 5865 5866 5867
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;
5868

5869 5870 5871 5872 5873 5874
  if (tmp_table->file->ha_rnd_init_with_error(1))
  {
    res= FALSE;
    goto end;
  }

5875 5876 5877
  tmp_table->file->extra_opt(HA_EXTRA_CACHE,
                             current_thd->variables.read_buff_size);
  for (;;)
5878
  {
5879 5880 5881 5882 5883 5884 5885 5886 5887 5888 5889 5890 5891 5892 5893 5894 5895 5896 5897 5898 5899 5900 5901 5902 5903 5904 5905 5906 5907 5908 5909 5910 5911 5912
    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;
    }
5913
  }
5914 5915 5916

  res= FALSE;
end:
5917
  tmp_table->file->ha_rnd_end();
5918 5919
  return res;
}
5920

5921 5922 5923

void subselect_table_scan_engine::cleanup()
{
5924
}
unknown's avatar
unknown committed
5925