opt_table_elimination.cc 36.6 KB
Newer Older
Sergey Petrunia's avatar
Sergey Petrunia committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/**
  @file

  @brief
    Table Elimination Module

  @defgroup Table_Elimination Table Elimination Module
  @{
*/

#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation				// gcc: Class implementation
#endif

#include "mysql_priv.h"
Sergey Petrunya's avatar
Sergey Petrunya committed
16
#include "my_bit.h"
Sergey Petrunia's avatar
Sergey Petrunia committed
17 18 19 20
#include "sql_select.h"

/*
  OVERVIEW
Sergey Petrunia's avatar
Sergey Petrunia committed
21 22

  The module has one entry point - eliminate_tables() function, which one 
Sergey Petrunya's avatar
Sergey Petrunya committed
23
  needs to call (once) at some point before the join optimization.
Sergey Petrunia's avatar
Sergey Petrunia committed
24 25 26 27 28 29 30
  eliminate_tables() operates over the JOIN structures. Logically, it
  removes the right sides of outer join nests. Physically, it changes the
  following members:

  * Eliminated tables are marked as constant and moved to the front of the
    join order.

Sergey Petrunya's avatar
Sergey Petrunya committed
31
  * In addition to this, they are recorded in JOIN::eliminated_tables bitmap.
Sergey Petrunia's avatar
Sergey Petrunia committed
32 33 34 35

  * Items that became disused because they were in the ON expression of an 
    eliminated outer join are notified by means of the Item tree walk which 
    calls Item::mark_as_eliminated_processor for every item
Sergey Petrunya's avatar
Sergey Petrunya committed
36 37 38
    - At the moment the only Item that cares whether it was eliminated is 
      Item_subselect with its Item_subselect::eliminated flag which is used
      by EXPLAIN code to check if the subquery should be shown in EXPLAIN.
Sergey Petrunia's avatar
Sergey Petrunia committed
39

Sergey Petrunya's avatar
Sergey Petrunya committed
40
  Table elimination is redone on every PS re-execution.
Sergey Petrunia's avatar
Sergey Petrunia committed
41 42
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
43
class Value_dep : public Sql_alloc
44 45 46 47 48 49
{
public:
  enum {
    VALUE_FIELD,
    VALUE_TABLE,
  } type; /* Type of the object */
Sergey Petrunya's avatar
Sergey Petrunya committed
50 51 52
  
  Value_dep(): bound(FALSE), next(NULL)
  {}
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107

  bool bound;
  Value_dep *next;
};

class Field_value;
class Table_value;
class Outer_join_module;
class Key_module;

/*
  A table field. There is only one such object for any tblX.fieldY
  - the field epends on its table and equalities
  - expressions that use the field are its dependencies
*/
class Field_value : public Value_dep
{
public:
  Field_value(Table_value *table_arg, Field *field_arg) :
    table(table_arg), field(field_arg)
  {
    type= Value_dep::VALUE_FIELD;
  }

  Table_value *table; /* Table this field is from */
  Field *field;
  
  /* 
    Field_deps that belong to one table form a linked list. list members are
    ordered by field_index 
  */
  Field_value *next_table_field;
  uint bitmap_offset; /* Offset of our part of the bitmap */
};


/*
  A table.
  - table depends on any of its unique keys
  - has its fields and embedding outer join as dependency.
*/
class Table_value : public Value_dep
{
public:
  Table_value(TABLE *table_arg) : 
    table(table_arg), fields(NULL), keys(NULL), outer_join_dep(NULL)
  {
    type= Value_dep::VALUE_TABLE;
  }
  TABLE *table;
  Field_value *fields; /* Ordered list of fields that belong to this table */
  Key_module *keys; /* Ordered list of Unique keys in this table */
  Outer_join_module *outer_join_dep; /* Innermost eliminable outer join we're in */
};

Sergey Petrunya's avatar
Sergey Petrunya committed
108

Sergey Petrunya's avatar
Sergey Petrunya committed
109
/*
110
  A 'module'
Sergey Petrunya's avatar
Sergey Petrunya committed
111 112
*/

113
class Module_dep : public Sql_alloc
Sergey Petrunya's avatar
Sergey Petrunya committed
114 115 116
{
public:
  enum {
Sergey Petrunya's avatar
Sergey Petrunya committed
117 118 119 120
    MODULE_EXPRESSION,
    MODULE_MULTI_EQUALITY,
    MODULE_UNIQUE_KEY,
    MODULE_OUTER_JOIN
Sergey Petrunya's avatar
Sergey Petrunya committed
121 122 123 124 125 126
  } type; /* Type of the object */
  
  /* 
    Used to make a linked list of elements that became bound and thus can
    make elements that depend on them bound, too.
  */
127
  Module_dep *next; 
Sergey Petrunya's avatar
Sergey Petrunya committed
128
  uint unknown_args;
Sergey Petrunya's avatar
Sergey Petrunya committed
129

130 131
  Module_dep() : next(NULL), unknown_args(0) {}
};
Sergey Petrunya's avatar
Sergey Petrunya committed
132 133


Sergey Petrunya's avatar
Sergey Petrunya committed
134

Sergey Petrunya's avatar
Sergey Petrunya committed
135
/*
Sergey Petrunya's avatar
Sergey Petrunya committed
136 137
  A "tbl.column= expr" equality dependency.  tbl.column depends on fields 
  used in expr.
Sergey Petrunya's avatar
Sergey Petrunya committed
138
*/
139
class Equality_module : public Module_dep
Sergey Petrunya's avatar
Sergey Petrunya committed
140 141
{
public:
142
  Field_value *field;
Sergey Petrunya's avatar
Sergey Petrunya committed
143
  Item  *expression;
Sergey Petrunya's avatar
Sergey Petrunya committed
144
  
Sergey Petrunya's avatar
Sergey Petrunya committed
145 146
  /* Used during condition analysis only, similar to KEYUSE::level */
  uint level;
Sergey Petrunya's avatar
Sergey Petrunya committed
147 148 149 150
};


/*
Sergey Petrunya's avatar
Sergey Petrunya committed
151 152 153
  A Unique key.
   - Unique key depends on all of its components
   - Key's table is its dependency
Sergey Petrunya's avatar
Sergey Petrunya committed
154
*/
155
class Key_module: public Module_dep
Sergey Petrunya's avatar
Sergey Petrunya committed
156 157
{
public:
158 159
  Key_module(Table_value *table_arg, uint keyno_arg, uint n_parts_arg) :
    table(table_arg), keyno(keyno_arg), next_table_key(NULL)
Sergey Petrunya's avatar
Sergey Petrunya committed
160
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
161
    type= Module_dep::MODULE_UNIQUE_KEY;
162
    unknown_args= n_parts_arg;
Sergey Petrunya's avatar
Sergey Petrunya committed
163
  }
164
  Table_value *table; /* Table this key is from */
Sergey Petrunya's avatar
Sergey Petrunya committed
165
  uint keyno;
Sergey Petrunya's avatar
Sergey Petrunya committed
166
  /* Unique keys form a linked list, ordered by keyno */
167
  Key_module *next_table_key;
Sergey Petrunya's avatar
Sergey Petrunya committed
168 169 170 171 172
};



/*
Sergey Petrunya's avatar
Sergey Petrunya committed
173 174 175
  An outer join nest that is subject to elimination
  - it depends on all tables inside it
  - has its parent outer join as dependency
Sergey Petrunya's avatar
Sergey Petrunya committed
176
*/
177
class Outer_join_module: public Module_dep
Sergey Petrunya's avatar
Sergey Petrunya committed
178 179
{
public:
180 181
  Outer_join_module(TABLE_LIST *table_list_arg, uint n_children) : 
    table_list(table_list_arg), parent(NULL)
Sergey Petrunya's avatar
Sergey Petrunya committed
182
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
183
    type= Module_dep::MODULE_OUTER_JOIN;
184
    unknown_args= n_children;
Sergey Petrunya's avatar
Sergey Petrunya committed
185
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
186 187 188 189
  /* 
    Outer join we're representing. This can be a join nest or a one table that
    is outer join'ed.
  */
Sergey Petrunya's avatar
Sergey Petrunya committed
190
  TABLE_LIST *table_list;
Sergey Petrunya's avatar
Sergey Petrunya committed
191 192 193 194 195
  
  /* 
    Tables within this outer join (and its descendants) that are not yet known
    to be functionally dependent.
  */
196
  table_map missing_tables; //psergey-todo: remove 
Sergey Petrunya's avatar
Sergey Petrunya committed
197
  /* All tables within this outer join and its descendants */ 
198
  table_map all_tables; //psergey-todo: remove 
Sergey Petrunya's avatar
Sergey Petrunya committed
199
  /* Parent eliminable outer join, if any */
200
  Outer_join_module *parent;
Sergey Petrunya's avatar
Sergey Petrunya committed
201 202 203
};


Sergey Petrunya's avatar
Sergey Petrunya committed
204 205 206
/*
  Table elimination context
*/
Sergey Petrunya's avatar
Sergey Petrunya committed
207 208 209
class Table_elimination
{
public:
Sergey Petrunya's avatar
Sergey Petrunya committed
210
  Table_elimination(JOIN *join_arg) : join(join_arg), n_outer_joins(0)
Sergey Petrunya's avatar
Sergey Petrunya committed
211 212 213 214 215 216
  {
    bzero(table_deps, sizeof(table_deps));
  }

  JOIN *join;
  /* Array of equality dependencies */
217
  Equality_module *equality_deps;
Sergey Petrunya's avatar
Sergey Petrunya committed
218 219
  uint n_equality_deps; /* Number of elements in the array */

220 221
  /* tablenr -> Table_value* mapping. */
  Table_value *table_deps[MAX_KEY];
Sergey Petrunya's avatar
Sergey Petrunya committed
222 223

  /* Outer joins that are candidates for elimination */
224
  List<Outer_join_module> oj_deps;
Sergey Petrunya's avatar
Sergey Petrunya committed
225
  uint n_outer_joins;
Sergey Petrunya's avatar
Sergey Petrunya committed
226 227 228 229 230 231

  /* Bitmap of how expressions depend on bits */
  MY_BITMAP expr_deps;
};

static 
232
void build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, 
Sergey Petrunya's avatar
Sergey Petrunya committed
233 234
                            uint *and_level, Item *cond, 
                            table_map usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
235
static 
Sergey Petrunya's avatar
Sergey Petrunya committed
236 237 238 239
void add_eq_dep(Table_elimination *te, Equality_module **eq_dep, 
                uint and_level,
                Item_func *cond, Item *left, Item *right, 
                table_map usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
240
static 
241 242
Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, 
                              Equality_module *end, uint and_level);
Sergey Petrunya's avatar
Sergey Petrunya committed
243

244 245 246 247
static Table_value *get_table_value(Table_elimination *te, TABLE *table);
static Field_value *get_field_value(Table_elimination *te, Field *field);
static 
void run_elimination_wave(Table_elimination *te, Module_dep *bound_modules);
Sergey Petrunya's avatar
Sergey Petrunya committed
248
void eliminate_tables(JOIN *join);
Sergey Petrunya's avatar
Sergey Petrunya committed
249
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
Sergey Petrunya's avatar
Sergey Petrunya committed
250 251 252 253 254

#ifndef DBUG_OFF
static void dbug_print_deps(Table_elimination *te);
#endif 
/*******************************************************************************************/
Sergey Petrunia's avatar
Sergey Petrunia committed
255 256

/*
Sergey Petrunya's avatar
Sergey Petrunya committed
257
  Produce Eq_dep elements for given condition.
Sergey Petrunia's avatar
Sergey Petrunia committed
258 259

  SYNOPSIS
Sergey Petrunya's avatar
Sergey Petrunya committed
260 261 262 263 264 265 266 267
    build_eq_deps_for_cond()
      te                    Table elimination context 
      fdeps          INOUT  Put produced equality conditions here
      and_level      INOUT  AND-level (like in add_key_fields)
      cond                  Condition to process
      usable_tables         Tables which fields we're interested in. That is,
                            Equality_dep represent "tbl.col=expr" and we'll
                            produce them only if tbl is in usable_tables.
Sergey Petrunia's avatar
Sergey Petrunia committed
268
  DESCRIPTION
Sergey Petrunya's avatar
Sergey Petrunya committed
269
    This function is modeled after add_key_fields()
Sergey Petrunya's avatar
Sergey Petrunya committed
270
*/
Sergey Petrunya's avatar
Sergey Petrunya committed
271

Sergey Petrunya's avatar
Sergey Petrunya committed
272
static 
273
void build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps, 
Sergey Petrunya's avatar
Sergey Petrunya committed
274 275
                            uint *and_level, Item *cond, 
                            table_map usable_tables)
Sergey Petrunya's avatar
Sergey Petrunya committed
276 277 278 279
{
  if (cond->type() == Item_func::COND_ITEM)
  {
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
280
    Equality_module *org_key_fields= *fdeps;
Sergey Petrunia's avatar
Sergey Petrunia committed
281
    
Sergey Petrunya's avatar
Sergey Petrunya committed
282 283 284 285 286 287
    /* AND/OR */
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
    {
      Item *item;
      while ((item=li++))
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
288
        build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
289 290 291 292 293 294 295 296 297 298 299
      }
      /* 
        TODO: inject here a "if we have {t.col=const AND t.col=smth_else}, then
        remove the second part" logic.
      */
      for (; org_key_fields != *fdeps ; org_key_fields++)
        org_key_fields->level= *and_level;
    }
    else
    {
      (*and_level)++;
Sergey Petrunya's avatar
Sergey Petrunya committed
300
      build_eq_deps_for_cond(te, fdeps, and_level, li++, usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
301 302 303
      Item *item;
      while ((item=li++))
      {
304
        Equality_module *start_key_fields= *fdeps;
Sergey Petrunya's avatar
Sergey Petrunya committed
305
        (*and_level)++;
Sergey Petrunya's avatar
Sergey Petrunya committed
306
        build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
307 308 309 310 311 312
        *fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps,
                                ++(*and_level));
      }
    }
    return;
  }
Sergey Petrunia's avatar
Sergey Petrunia committed
313

Sergey Petrunya's avatar
Sergey Petrunya committed
314 315
  if (cond->type() != Item::FUNC_ITEM)
    return;
Sergey Petrunya's avatar
Sergey Petrunya committed
316

Sergey Petrunya's avatar
Sergey Petrunya committed
317
  Item_func *cond_func= (Item_func*) cond;
Sergey Petrunya's avatar
Sergey Petrunya committed
318 319 320 321 322
  Item **args= cond_func->arguments();
  Item *fld;

  switch (cond_func->functype()) {
  case Item_func::IN_FUNC:
Sergey Petrunya's avatar
Sergey Petrunya committed
323
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
324
    if (cond_func->argument_count() == 2)
Sergey Petrunya's avatar
Sergey Petrunya committed
325
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
326 327 328
      add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], 
                 usable_tables);
      add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0], 
Sergey Petrunya's avatar
Sergey Petrunya committed
329
                 usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
330
    }
Sergey Petrunya's avatar
Sergey Petrunya committed
331 332 333 334 335
  }
  case Item_func::BETWEEN:
  {
    if (!((Item_func_between*)cond)->negated &&
        args[1]->eq(args[2], ((Item_field*)fld)->field->binary()))
Sergey Petrunya's avatar
Sergey Petrunya committed
336
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
337 338 339 340
      add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1],
                 usable_tables);
      add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0],
                 usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
341 342 343
    }
    break;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
344 345
  case Item_func::EQ_FUNC:
  case Item_func::EQUAL_FUNC:
Sergey Petrunya's avatar
Sergey Petrunya committed
346
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
347 348 349 350
    add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], 
               usable_tables);
    add_eq_dep(te, fdeps, *and_level, cond_func, args[1], args[0],
               usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
351 352
    break;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
353 354 355 356 357 358 359
  case Item_func::ISNULL_FUNC:
  {
    Item *tmp=new Item_null;
    if (unlikely(!tmp))                       // Should never be true
      return;
    add_eq_dep(te, fdeps, *and_level, cond_func, args[0], args[1], 
               usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
360
    break;
Sergey Petrunya's avatar
Sergey Petrunya committed
361 362 363
  }
  case Item_func::MULT_EQUAL_FUNC:
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
364 365 366 367 368 369 370 371 372 373 374 375 376
    Item_equal *item_equal= (Item_equal *) cond;
    Item *const_item= item_equal->get_const();
    Item_equal_iterator it(*item_equal);
    Item_field *item;
    if (const_item)
    {
      /*
        For each field field1 from item_equal consider the equality 
        field1=const_item as a condition allowing an index access of the table
        with field1 by the keys value of field1.
      */   
      while ((item= it++))
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
377 378
        add_eq_dep(te, fdeps, *and_level, cond_func, item, const_item, 
                   usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
379 380 381 382 383 384 385 386 387 388 389 390 391 392
      }
    }
    else 
    {
      /*
        Consider all pairs of different fields included into item_equal.
        For each of them (field1, field1) consider the equality 
        field1=field2 as a condition allowing an index access of the table
        with field1 by the keys value of field2.
      */   
      Item_equal_iterator fi(*item_equal);
      while ((item= fi++))
      {
        Field *field= item->field;
Sergey Petrunya's avatar
Sergey Petrunya committed
393 394
        Item_field *item2;
        while ((item2= it++))
Sergey Petrunya's avatar
Sergey Petrunya committed
395
        {
Sergey Petrunya's avatar
Sergey Petrunya committed
396
          if (!field->eq(item2->field))
Sergey Petrunya's avatar
Sergey Petrunya committed
397
          {
Sergey Petrunya's avatar
Sergey Petrunya committed
398 399
            add_eq_dep(te, fdeps, *and_level, cond_func, item, item2, 
                       usable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
400 401 402 403 404 405 406
          }
        }
        it.rewind();
      }
    }
    break;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
407 408 409
  default:
    break;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
410
}
Sergey Petrunia's avatar
Sergey Petrunia committed
411

Sergey Petrunya's avatar
Sergey Petrunya committed
412

Sergey Petrunya's avatar
Sergey Petrunya committed
413
/*
414
  Perform an OR operation on two (adjacent) Equality_module arrays.
Sergey Petrunya's avatar
Sergey Petrunya committed
415 416 417

  SYNOPSIS
     merge_func_deps()
Sergey Petrunya's avatar
Sergey Petrunya committed
418 419 420 421
       start        Start of left OR-part
       new_fields   Start of right OR-part
       end          End of right OR-part
       and_level    AND-level.
Sergey Petrunya's avatar
Sergey Petrunya committed
422 423

  DESCRIPTION
424
  This function is invoked for two adjacent arrays of Equality_module elements:
Sergey Petrunya's avatar
Sergey Petrunya committed
425 426 427 428 429 430

                      $LEFT_PART             $RIGHT_PART
             +-----------------------+-----------------------+
            start                new_fields                 end
         
  The goal is to produce an array which would correspnd to the combined 
Sergey Petrunia's avatar
Sergey Petrunia committed
431
  
Sergey Petrunya's avatar
Sergey Petrunya committed
432
    $LEFT_PART OR $RIGHT_PART
Sergey Petrunia's avatar
Sergey Petrunia committed
433
  
Sergey Petrunya's avatar
Sergey Petrunya committed
434 435 436
  condition. This is achieved as follows: First, we apply distrubutive law:
  
    (fdep_A_1 AND fdep_A_2 AND ...)  OR  (fdep_B_1 AND fdep_B_2 AND ...) =
Sergey Petrunia's avatar
Sergey Petrunia committed
437

Sergey Petrunya's avatar
Sergey Petrunya committed
438
     = AND_ij (fdep_A_[i] OR fdep_B_[j])
Sergey Petrunia's avatar
Sergey Petrunia committed
439
  
Sergey Petrunya's avatar
Sergey Petrunya committed
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458
  Then we walk over the obtained "fdep_A_[i] OR fdep_B_[j]" pairs, and 
   - Discard those that that have left and right part referring to different
     columns. We can't infer anything useful from "col1=expr1 OR col2=expr2".
   - When left and right parts refer to the same column,  we check if they are 
     essentially the same. 
     = If they are the same, we keep one copy 
       "t.col=expr OR t.col=expr"  -> "t.col=expr 
     = if they are different , then we discard both
      "t.col=expr1 OR t.col=expr2" -> (nothing useful)

  (no per-table or for-index FUNC_DEPS exist yet at this phase).

  See also merge_key_fields().

  RETURN 
    End of the result array
*/

static 
459 460
Equality_module *merge_func_deps(Equality_module *start, Equality_module *new_fields, 
                              Equality_module *end, uint and_level)
Sergey Petrunya's avatar
Sergey Petrunya committed
461 462 463 464 465 466
{
  if (start == new_fields)
    return start;				// Impossible or
  if (new_fields == end)
    return start;				// No new fields, skip all

467
  Equality_module *first_free=new_fields;
Sergey Petrunya's avatar
Sergey Petrunya committed
468 469

  for (; new_fields != end ; new_fields++)
Sergey Petrunia's avatar
Sergey Petrunia committed
470
  {
471
    for (Equality_module *old=start ; old != first_free ; old++)
Sergey Petrunya's avatar
Sergey Petrunya committed
472 473 474 475 476 477 478 479 480 481 482
    {
      /* 
         TODO: does it make sense to attempt to merging multiple-equalities? 
         A: YES.  
           (a=b=c) OR (a=b=d)  produce "a=b". 
         QQ: 
           What to use for merging? Trivial N*M algorithm or pre-sort and then
           merge ordered sequences?
      */
      if (old->field == new_fields->field)
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
483
	if (!new_fields->expression->const_item())
Sergey Petrunya's avatar
Sergey Petrunya committed
484 485 486 487 488
	{
	  /*
	    If the value matches, we can use the key reference.
	    If not, we keep it until we have examined all new values
	  */
Sergey Petrunya's avatar
Sergey Petrunya committed
489
	  if (old->expression->eq(new_fields->expression, old->field->field->binary()))
Sergey Petrunya's avatar
Sergey Petrunya committed
490 491 492 493
	  {
	    old->level= and_level;
	  }
	}
Sergey Petrunya's avatar
Sergey Petrunya committed
494
	else if (old->expression->eq_by_collation(new_fields->expression, 
Sergey Petrunya's avatar
Sergey Petrunya committed
495 496 497 498 499 500 501 502 503 504 505 506 507 508 509
                                           old->field->field->binary(),
                                           old->field->field->charset()))
	{
	  old->level= and_level;
	}
	else
	{
          /* The expressions are different. */
	  if (old == --first_free)		// If last item
	    break;
	  *old= *first_free;			// Remove old value
	  old--;				// Retry this value
	}
      }
    }
Sergey Petrunia's avatar
Sergey Petrunia committed
510
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
511 512 513 514 515

  /* 
    Ok, the results are within the [start, first_free) range, and the useful
    elements have level==and_level. Now, lets remove all unusable elements:
  */
516
  for (Equality_module *old=start ; old != first_free ;)
Sergey Petrunia's avatar
Sergey Petrunia committed
517
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
518 519 520 521 522 523 524 525 526 527 528
    if (old->level != and_level)
    {						// Not used in all levels
      if (old == --first_free)
	break;
      *old= *first_free;			// Remove old value
      continue;
    }
    old++;
  }
  return first_free;
}
Sergey Petrunia's avatar
Sergey Petrunia committed
529

Sergey Petrunya's avatar
Sergey Petrunya committed
530 531

/*
532
  Add an Equality_module element for a given predicate, if applicable 
Sergey Petrunya's avatar
Sergey Petrunya committed
533 534 535

  DESCRIPTION 
    This function is modeled after add_key_field().
Sergey Petrunya's avatar
Sergey Petrunya committed
536 537 538
*/

static 
539
void add_eq_dep(Table_elimination *te, Equality_module **eq_dep,
Sergey Petrunya's avatar
Sergey Petrunya committed
540 541
                uint and_level, Item_func *cond, 
                Item *left, Item *right, table_map usable_tables)
Sergey Petrunya's avatar
Sergey Petrunya committed
542
{
Sergey Petrunya's avatar
Sergey Petrunya committed
543 544 545
  if ((left->used_tables() & usable_tables) &&
      !(right->used_tables() & RAND_TABLE_BIT) &&
      left->real_item()->type() == Item::FIELD_ITEM)
Sergey Petrunya's avatar
Sergey Petrunya committed
546
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
547 548
    Field *field= ((Item_field*)left->real_item())->field;
    if (field->result_type() == STRING_RESULT)
Sergey Petrunya's avatar
Sergey Petrunya committed
549
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
550 551 552 553 554 555 556 557 558 559 560 561 562 563 564
      if (right->result_type() != STRING_RESULT)
      {
        if (field->cmp_type() != right->result_type())
          return;
      }
      else
      {
        /*
          We can't use indexes if the effective collation
          of the operation differ from the field collation.
        */
        if (field->cmp_type() == STRING_RESULT &&
            ((Field_str*)field)->charset() != cond->compare_collation())
          return;
      }
Sergey Petrunya's avatar
Sergey Petrunya committed
565 566
    }

Sergey Petrunya's avatar
Sergey Petrunya committed
567 568 569 570 571 572 573
    /* Store possible eq field */
    (*eq_dep)->type=  Module_dep::MODULE_EXPRESSION; //psergey-todo;
    (*eq_dep)->field= get_field_value(te, field); 
    (*eq_dep)->expression= right;
    (*eq_dep)->level= and_level;
    (*eq_dep)++;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
574 575
}

Sergey Petrunya's avatar
Sergey Petrunya committed
576

Sergey Petrunya's avatar
Sergey Petrunya committed
577
/*
578
  Get a Table_value object for the given table, creating it if necessary.
Sergey Petrunya's avatar
Sergey Petrunya committed
579 580
*/

581
static Table_value *get_table_value(Table_elimination *te, TABLE *table)
Sergey Petrunya's avatar
Sergey Petrunya committed
582
{
Sergey Petrunya's avatar
Sergey Petrunya committed
583 584 585
  Table_value *tbl_dep;
  if (!(tbl_dep= new Table_value(table)))
    return NULL;
Sergey Petrunya's avatar
Sergey Petrunya committed
586

Sergey Petrunya's avatar
Sergey Petrunya committed
587
  Key_module **key_list= &(tbl_dep->keys);
Sergey Petrunya's avatar
Sergey Petrunya committed
588 589 590 591 592 593
  /* Add dependencies for unique keys */
  for (uint i=0; i < table->s->keys; i++)
  {
    KEY *key= table->key_info + i; 
    if ((key->flags & (HA_NOSAME | HA_END_SPACE_KEY)) == HA_NOSAME)
    {
594
      Key_module *key_dep= new Key_module(tbl_dep, i, key->key_parts);
Sergey Petrunya's avatar
Sergey Petrunya committed
595 596
      *key_list= key_dep;
      key_list= &(key_dep->next_table_key);
Sergey Petrunia's avatar
Sergey Petrunia committed
597 598
    }
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
599
  return te->table_deps[table->tablenr]= tbl_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
600 601
}

Sergey Petrunya's avatar
Sergey Petrunya committed
602

Sergey Petrunya's avatar
Sergey Petrunya committed
603
/* 
604
  Get a Field_value object for the given field, creating it if necessary
Sergey Petrunya's avatar
Sergey Petrunya committed
605 606
*/

607
static Field_value *get_field_value(Table_elimination *te, Field *field)
Sergey Petrunya's avatar
Sergey Petrunya committed
608 609
{
  TABLE *table= field->table;
610
  Table_value *tbl_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
611

Sergey Petrunya's avatar
Sergey Petrunya committed
612
  /* First, get the table*/
Sergey Petrunya's avatar
Sergey Petrunya committed
613
  if (!(tbl_dep= te->table_deps[table->tablenr]))
Sergey Petrunya's avatar
Sergey Petrunya committed
614 615 616 617
  {
    if (!(tbl_dep= get_table_value(te, table)))
      return NULL;
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
618 619
 
  /* Try finding the field in field list */
620
  Field_value **pfield= &(tbl_dep->fields);
Sergey Petrunya's avatar
Sergey Petrunya committed
621 622 623 624 625 626
  while (*pfield && (*pfield)->field->field_index < field->field_index)
  {
    pfield= &((*pfield)->next_table_field);
  }
  if (*pfield && (*pfield)->field->field_index == field->field_index)
    return *pfield;
Sergey Petrunya's avatar
Sergey Petrunya committed
627
  
Sergey Petrunya's avatar
Sergey Petrunya committed
628
  /* Create the field and insert it in the list */
629
  Field_value *new_field= new Field_value(tbl_dep, field);
Sergey Petrunya's avatar
Sergey Petrunya committed
630 631
  new_field->next_table_field= *pfield;
  *pfield= new_field;
Sergey Petrunya's avatar
Sergey Petrunya committed
632

Sergey Petrunya's avatar
Sergey Petrunya committed
633 634 635 636
  return new_field;
}


Sergey Petrunya's avatar
Sergey Petrunya committed
637
/*
638
  Create an Outer_join_module object for the given outer join
Sergey Petrunya's avatar
Sergey Petrunya committed
639 640

  DESCRIPTION
641
    Outer_join_module objects for children (or further descendants) are always
Sergey Petrunya's avatar
Sergey Petrunya committed
642 643 644 645
    created before the parents.
*/

static 
646
Outer_join_module *get_outer_join_dep(Table_elimination *te, 
Sergey Petrunya's avatar
Sergey Petrunya committed
647 648
                                      TABLE_LIST *outer_join, 
                                      table_map deps_map)
Sergey Petrunya's avatar
Sergey Petrunya committed
649
{
650 651
  Outer_join_module *oj_dep;
  oj_dep= new Outer_join_module(outer_join, my_count_bits(deps_map));
Sergey Petrunya's avatar
Sergey Petrunya committed
652
  te->n_outer_joins++;
Sergey Petrunya's avatar
Sergey Petrunya committed
653 654 655 656 657
  
  /* 
    Collect a bitmap fo tables that we depend on, and also set parent pointer
    for descendant outer join elements.
  */
Sergey Petrunya's avatar
Sergey Petrunya committed
658 659 660
  Table_map_iterator it(deps_map);
  int idx;
  while ((idx= it.next_bit()) != Table_map_iterator::BITMAP_END)
Sergey Petrunia's avatar
Sergey Petrunia committed
661
  {
662
    Table_value *table_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
663 664
    if (!(table_dep= te->table_deps[idx]))
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
665 666 667 668 669
      /*
        We get here only when ON expression had no references to inner tables
        and Table_map objects weren't created for them. This is a rare/
        unimportant case so it's ok to do not too efficient searches.
      */
Sergey Petrunya's avatar
Sergey Petrunya committed
670
      TABLE *table= NULL;
Sergey Petrunya's avatar
Sergey Petrunya committed
671 672
      for (TABLE_LIST *tlist= te->join->select_lex->leaf_tables; tlist;
           tlist=tlist->next_leaf)
Sergey Petrunya's avatar
Sergey Petrunya committed
673
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
674
        if (tlist->table->tablenr == (uint)idx)
Sergey Petrunya's avatar
Sergey Petrunya committed
675
        {
Sergey Petrunya's avatar
Sergey Petrunya committed
676
          table=tlist->table;
Sergey Petrunya's avatar
Sergey Petrunya committed
677 678 679 680
          break;
        }
      }
      DBUG_ASSERT(table);
Sergey Petrunya's avatar
Sergey Petrunya committed
681 682
      if (!(table_dep= get_table_value(te, table)))
        return NULL;
Sergey Petrunya's avatar
Sergey Petrunya committed
683
    }
Sergey Petrunya's avatar
Sergey Petrunya committed
684 685 686 687
    
    /* 
      Walk from the table up to its embedding outer joins. The goal is to
      find the least embedded outer join nest and set its parent pointer to
688
      point to the newly created Outer_join_module.
Sergey Petrunya's avatar
Sergey Petrunya committed
689 690
      to set the pointer of its near 
    */
Sergey Petrunya's avatar
Sergey Petrunya committed
691 692 693 694
    if (!table_dep->outer_join_dep)
      table_dep->outer_join_dep= oj_dep;
    else
    {
695
      Outer_join_module *oj= table_dep->outer_join_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
696 697
      while (oj->parent)
        oj= oj->parent;
698 699
      if (oj != oj_dep)
        oj->parent=oj_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
700
    }
Sergey Petrunia's avatar
Sergey Petrunia committed
701
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
702
  return oj_dep;
Sergey Petrunia's avatar
Sergey Petrunia committed
703 704
}

Sergey Petrunya's avatar
Sergey Petrunya committed
705

Sergey Petrunia's avatar
Sergey Petrunia committed
706
/*
Sergey Petrunya's avatar
Sergey Petrunya committed
707
  Build functional dependency graph for elements of given join list
Sergey Petrunia's avatar
Sergey Petrunia committed
708

Sergey Petrunia's avatar
Sergey Petrunia committed
709
  SYNOPSIS
Sergey Petrunya's avatar
Sergey Petrunya committed
710
    collect_funcdeps_for_join_list()
Sergey Petrunya's avatar
Sergey Petrunya committed
711 712
      te                       Table elimination context.
      join_list                Join list to work on 
713
      build_eq_deps            TRUE <=> build Equality_module elements for all
Sergey Petrunya's avatar
Sergey Petrunya committed
714 715 716 717 718 719 720 721 722 723
                               members of the join list, even if they cannot 
                               be individually eliminated
      tables_used_elsewhere    Bitmap of tables that are referred to from
                               somewhere outside of this join list (e.g.
                               select list, HAVING, ON expressions of parent
                               joins, etc).
      eliminable_tables  INOUT Tables that can potentially be eliminated
                               (needed so we know for which tables to build 
                               dependencies for)
      eq_dep             INOUT End of array of equality dependencies.
Sergey Petrunya's avatar
Sergey Petrunya committed
724

Sergey Petrunia's avatar
Sergey Petrunia committed
725
  DESCRIPTION
Sergey Petrunya's avatar
Sergey Petrunya committed
726
    .
Sergey Petrunia's avatar
Sergey Petrunia committed
727
*/
Sergey Petrunya's avatar
Sergey Petrunya committed
728

Sergey Petrunya's avatar
Sergey Petrunya committed
729
static bool
Sergey Petrunya's avatar
Sergey Petrunya committed
730 731 732 733 734
collect_funcdeps_for_join_list(Table_elimination *te,
                               List<TABLE_LIST> *join_list,
                               bool build_eq_deps,
                               table_map tables_used_elsewhere,
                               table_map *eliminable_tables,
735
                               Equality_module **eq_dep)
Sergey Petrunia's avatar
Sergey Petrunia committed
736 737
{
  TABLE_LIST *tbl;
Sergey Petrunya's avatar
Sergey Petrunya committed
738 739
  List_iterator<TABLE_LIST> it(*join_list);
  table_map tables_used_on_left= 0;
Sergey Petrunia's avatar
Sergey Petrunia committed
740 741 742

  while ((tbl= it++))
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
743
    if (tbl->on_expr)
Sergey Petrunia's avatar
Sergey Petrunia committed
744
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
745 746
      table_map outside_used_tables= tables_used_elsewhere | 
                                     tables_used_on_left;
Sergey Petrunya's avatar
Sergey Petrunya committed
747 748
      bool eliminable;
      table_map cur_map;
Sergey Petrunya's avatar
Sergey Petrunya committed
749
      if (tbl->nested_join)
Sergey Petrunia's avatar
Sergey Petrunia committed
750
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
751
        /* This is  "... LEFT JOIN (join_nest) ON cond" */
Sergey Petrunya's avatar
Sergey Petrunya committed
752 753 754 755
        cur_map= tbl->nested_join->used_tables; 
        eliminable= !(cur_map & outside_used_tables);
        if (eliminable)
          *eliminable_tables |= cur_map;
Sergey Petrunya's avatar
Sergey Petrunya committed
756 757 758 759 760 761
        if (collect_funcdeps_for_join_list(te, &tbl->nested_join->join_list,
                                           eliminable || build_eq_deps,
                                           outside_used_tables,
                                           eliminable_tables,
                                           eq_dep))
          return TRUE;
Sergey Petrunya's avatar
Sergey Petrunya committed
762 763 764 765
      }
      else
      {
        /* This is  "... LEFT JOIN tbl ON cond" */
Sergey Petrunya's avatar
Sergey Petrunya committed
766 767 768
        cur_map= tbl->table->map;
        eliminable= !(tbl->table->map & outside_used_tables);
        *eliminable_tables |= cur_map;
Sergey Petrunia's avatar
Sergey Petrunia committed
769 770
      }

Sergey Petrunya's avatar
Sergey Petrunya committed
771
      if (eliminable || build_eq_deps)
Sergey Petrunya's avatar
Sergey Petrunya committed
772
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
773 774
        // build comp_cond from ON expression
        uint and_level=0;
Sergey Petrunya's avatar
Sergey Petrunya committed
775
        build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr, 
Sergey Petrunya's avatar
Sergey Petrunya committed
776
                                *eliminable_tables);
Sergey Petrunya's avatar
Sergey Petrunya committed
777
      }
Sergey Petrunya's avatar
Sergey Petrunya committed
778

Sergey Petrunya's avatar
Sergey Petrunya committed
779
      if (eliminable && !get_outer_join_dep(te, tbl, cur_map))
Sergey Petrunya's avatar
Sergey Petrunya committed
780
        return TRUE;
Sergey Petrunya's avatar
Sergey Petrunya committed
781 782

      tables_used_on_left |= tbl->on_expr->used_tables();
Sergey Petrunya's avatar
Sergey Petrunya committed
783
    }
Sergey Petrunia's avatar
Sergey Petrunia committed
784
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
785
  return FALSE;
Sergey Petrunia's avatar
Sergey Petrunia committed
786 787 788
}


Sergey Petrunya's avatar
Sergey Petrunya committed
789
/*
Sergey Petrunya's avatar
Sergey Petrunya committed
790
  This is used to analyze expressions in "tbl.col=expr" dependencies so
Sergey Petrunya's avatar
Sergey Petrunya committed
791
  that we can figure out which fields the expression depends on.
Sergey Petrunia's avatar
Sergey Petrunia committed
792 793
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
794
class Field_dependency_setter : public Field_enumerator
Sergey Petrunia's avatar
Sergey Petrunia committed
795
{
Sergey Petrunya's avatar
Sergey Petrunya committed
796 797 798 799 800
public:
  Field_dependency_setter(Table_elimination *te_arg): te(te_arg)
  {}
  
  void see_field(Field *field)
Sergey Petrunia's avatar
Sergey Petrunia committed
801
  {
802
    Table_value *tbl_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
803
    if ((tbl_dep= te->table_deps[field->table->tablenr]))
Sergey Petrunia's avatar
Sergey Petrunia committed
804
    {
805
      for (Field_value *field_dep= tbl_dep->fields; field_dep; 
Sergey Petrunya's avatar
Sergey Petrunya committed
806
           field_dep= field_dep->next_table_field)
Sergey Petrunia's avatar
Sergey Petrunia committed
807
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
808
        if (field->field_index == field_dep->field->field_index)
Sergey Petrunia's avatar
Sergey Petrunia committed
809
        {
Sergey Petrunya's avatar
Sergey Petrunya committed
810 811 812 813 814
          uint offs= field_dep->bitmap_offset + expr_offset;
          if (!bitmap_is_set(&te->expr_deps, offs))
            te->equality_deps[expr_offset].unknown_args++;
          bitmap_set_bit(&te->expr_deps, offs);
          return;
Sergey Petrunia's avatar
Sergey Petrunia committed
815 816
        }
      }
Sergey Petrunya's avatar
Sergey Petrunya committed
817 818 819 820 821 822
      /* 
        We got here if didn't find this field. It's not a part of 
        a unique key, and/or there is no field=expr element for it.
        Bump the dependency anyway, this will signal that this dependency
        cannot be satisfied.
      */
Sergey Petrunya's avatar
Sergey Petrunya committed
823 824 825
      te->equality_deps[expr_offset].unknown_args++;
    }
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
826

Sergey Petrunya's avatar
Sergey Petrunya committed
827
  Table_elimination *te;
Sergey Petrunya's avatar
Sergey Petrunya committed
828 829
  /* Offset of the expression we're processing in the dependency bitmap */
  uint expr_offset; 
Sergey Petrunya's avatar
Sergey Petrunya committed
830
};
Sergey Petrunia's avatar
Sergey Petrunia committed
831

Sergey Petrunya's avatar
Sergey Petrunya committed
832

Sergey Petrunya's avatar
Sergey Petrunya committed
833 834 835 836 837 838 839 840 841 842 843
/*
  Setup equality dependencies
  
  SYNOPSIS
    setup_equality_deps()
      te                    Table elimination context
      bound_deps_list  OUT  Start of linked list of elements that were found to
                            be bound (caller will use this to see if that
                            allows to declare further elements bound)
*/

Sergey Petrunya's avatar
Sergey Petrunya committed
844
static 
845
bool setup_equality_deps(Table_elimination *te, Module_dep **bound_deps_list)
Sergey Petrunya's avatar
Sergey Petrunya committed
846 847 848
{
  DBUG_ENTER("setup_equality_deps");
  
Sergey Petrunya's avatar
Sergey Petrunya committed
849
  /*
850
    Count Field_value objects and assign each of them a unique bitmap_offset.
Sergey Petrunya's avatar
Sergey Petrunya committed
851
  */
Sergey Petrunya's avatar
Sergey Petrunya committed
852
  uint offset= 0;
853
  for (Table_value **tbl_dep=te->table_deps; 
Sergey Petrunya's avatar
Sergey Petrunya committed
854 855 856 857 858
       tbl_dep < te->table_deps + MAX_TABLES;
       tbl_dep++)
  {
    if (*tbl_dep)
    {
859
      for (Field_value *field_dep= (*tbl_dep)->fields;
Sergey Petrunya's avatar
Sergey Petrunya committed
860 861
           field_dep;
           field_dep= field_dep->next_table_field)
Sergey Petrunia's avatar
Sergey Petrunia committed
862
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
863 864
        field_dep->bitmap_offset= offset;
        offset += te->n_equality_deps;
Sergey Petrunia's avatar
Sergey Petrunia committed
865 866 867
      }
    }
  }
Sergey Petrunya's avatar
Sergey Petrunya committed
868 869 870 871 872 873 874 875 876 877
 
  void *buf;
  if (!(buf= current_thd->alloc(bitmap_buffer_size(offset))) ||
      bitmap_init(&te->expr_deps, (my_bitmap_map*)buf, offset, FALSE))
  {
    DBUG_RETURN(TRUE);
  }
  bitmap_clear_all(&te->expr_deps);

  /* 
Sergey Petrunya's avatar
Sergey Petrunya committed
878 879 880 881
    Analyze all "field=expr" dependencies, and have te->expr_deps encode
    dependencies of expressions from fields.

    Also collect a linked list of equalities that are bound.
Sergey Petrunya's avatar
Sergey Petrunya committed
882
  */
883
  Module_dep *bound_dep= NULL;
Sergey Petrunya's avatar
Sergey Petrunya committed
884
  Field_dependency_setter deps_setter(te);
885
  for (Equality_module *eq_dep= te->equality_deps; 
Sergey Petrunya's avatar
Sergey Petrunya committed
886 887 888 889 890
       eq_dep < te->equality_deps + te->n_equality_deps;
       eq_dep++)
  {
    deps_setter.expr_offset= eq_dep - te->equality_deps;
    eq_dep->unknown_args= 0;
Sergey Petrunya's avatar
Sergey Petrunya committed
891
    eq_dep->expression->walk(&Item::check_column_usage_processor, FALSE, 
Sergey Petrunya's avatar
Sergey Petrunya committed
892 893 894 895 896 897 898 899 900
                      (uchar*)&deps_setter);
    if (!eq_dep->unknown_args)
    {
      eq_dep->next= bound_dep;
      bound_dep= eq_dep;
    }
  }
  *bound_deps_list= bound_dep;

Sergey Petrunya's avatar
Sergey Petrunya committed
901
  DBUG_EXECUTE("test", dbug_print_deps(te); );
Sergey Petrunya's avatar
Sergey Petrunya committed
902
  DBUG_RETURN(FALSE);
Sergey Petrunia's avatar
Sergey Petrunia committed
903 904 905 906
}


/*
Sergey Petrunya's avatar
Sergey Petrunya committed
907
  Perform table elimination
Sergey Petrunia's avatar
Sergey Petrunia committed
908

Sergey Petrunia's avatar
Sergey Petrunia committed
909
  SYNOPSIS
Sergey Petrunya's avatar
Sergey Petrunya committed
910 911 912 913 914
    eliminate_tables()
      join                   Join to work on
      const_tbl_count INOUT  Number of constant tables (this includes
                             eliminated tables)
      const_tables    INOUT  Bitmap of constant tables
Sergey Petrunia's avatar
Sergey Petrunia committed
915 916

  DESCRIPTION
Sergey Petrunya's avatar
Sergey Petrunya committed
917 918 919 920 921 922 923
    This function is the entry point for table elimination. 
    The idea behind table elimination is that if we have an outer join:
   
      SELECT * FROM t1 LEFT JOIN 
        (t2 JOIN t3) ON t3.primary_key=t1.col AND 
                        t4.primary_key=t2.col
    such that
Sergey Petrunia's avatar
Sergey Petrunia committed
924

Sergey Petrunya's avatar
Sergey Petrunya committed
925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942
    1. columns of the inner tables are not used anywhere ouside the outer
       join (not in WHERE, not in GROUP/ORDER BY clause, not in select list 
       etc etc), and
    2. inner side of the outer join is guaranteed to produce at most one
       record combination for each record combination of outer tables.
    
    then the inner side of the outer join can be removed from the query.
    This is because it will always produce one matching record (either a
    real match or a NULL-complemented record combination), and since there
    are no references to columns of the inner tables anywhere, it doesn't
    matter which record combination it was.

    This function primary handles checking #1. It collects a bitmap of
    tables that are not used in select list/GROUP BY/ORDER BY/HAVING/etc and
    thus can possibly be eliminated.
  
  SIDE EFFECTS
    See the OVERVIEW section at the top of this file.
Sergey Petrunia's avatar
Sergey Petrunia committed
943 944 945

*/

Sergey Petrunya's avatar
Sergey Petrunya committed
946
void eliminate_tables(JOIN *join)
Sergey Petrunia's avatar
Sergey Petrunia committed
947
{
Sergey Petrunya's avatar
Sergey Petrunya committed
948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
  THD* thd= join->thd;
  Item *item;
  table_map used_tables;
  DBUG_ENTER("eliminate_tables");
  
  DBUG_ASSERT(join->eliminated_tables == 0);

  /* If there are no outer joins, we have nothing to eliminate: */
  if (!join->outer_join)
    DBUG_VOID_RETURN;

  /* Find the tables that are referred to from WHERE/HAVING */
  used_tables= (join->conds?  join->conds->used_tables() : 0) | 
               (join->having? join->having->used_tables() : 0);
  
  /* Add tables referred to from the select list */
  List_iterator<Item> it(join->fields_list);
  while ((item= it++))
    used_tables |= item->used_tables();
 
  /* Add tables referred to from ORDER BY and GROUP BY lists */
  ORDER *all_lists[]= { join->order, join->group_list};
  for (int i=0; i < 2; i++)
Sergey Petrunia's avatar
Sergey Petrunia committed
971
  {
Sergey Petrunya's avatar
Sergey Petrunya committed
972 973 974 975 976 977 978 979 980 981 982
    for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next)
      used_tables |= (*(cur_list->item))->used_tables();
  }
  
  if (join->select_lex == &thd->lex->select_lex)
  {
    /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */
    used_tables |= thd->table_map_for_update;

    /* Multi-table UPDATE: don't eliminate tables referred from SET statement */
    if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI)
Sergey Petrunya's avatar
Sergey Petrunya committed
983
    {
Sergey Petrunya's avatar
Sergey Petrunya committed
984 985 986 987 988 989 990 991 992 993 994 995 996 997
      List_iterator<Item> it2(thd->lex->value_list);
      while ((item= it2++))
        used_tables |= item->used_tables();
    }
  }
  
  table_map all_tables= join->all_tables_map();
  if (all_tables & ~used_tables)
  {
    /* There are some tables that we probably could eliminate. Try it. */
    Table_elimination te(join);
    uint m= max(thd->lex->current_select->max_equal_elems,1);
    uint max_elems= ((thd->lex->current_select->cond_count+1)*2 +
                      thd->lex->current_select->between_count)*m + 1 + 10; 
998
    if (!(te.equality_deps= new Equality_module[max_elems]))
Sergey Petrunya's avatar
Sergey Petrunya committed
999
      DBUG_VOID_RETURN;
1000
    Equality_module *eq_deps_end= te.equality_deps;
Sergey Petrunya's avatar
Sergey Petrunya committed
1001
    table_map eliminable_tables= 0;
Sergey Petrunya's avatar
Sergey Petrunya committed
1002 1003 1004 1005 1006 1007
    if (collect_funcdeps_for_join_list(&te, join->join_list,
                                       FALSE,
                                       used_tables,
                                       &eliminable_tables,
                                       &eq_deps_end))
      DBUG_VOID_RETURN;
Sergey Petrunya's avatar
Sergey Petrunya committed
1008
    te.n_equality_deps= eq_deps_end - te.equality_deps;
1009 1010 1011
    
    Module_dep *bound_modules;
    //Value_dep  *bound_values;
Sergey Petrunya's avatar
Sergey Petrunya committed
1012 1013
    if (setup_equality_deps(&te, &bound_modules))
      DBUG_VOID_RETURN;
1014 1015 1016 1017 1018
    
    run_elimination_wave(&te, bound_modules);
  }
  DBUG_VOID_RETURN;
}
Sergey Petrunya's avatar
Sergey Petrunya committed
1019 1020


1021 1022 1023 1024 1025 1026 1027 1028 1029
static 
void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep,
                                Module_dep **bound_modules)
{
  for (uint i=0; i < te->n_equality_deps; i++)
  {
    if (bitmap_is_set(&te->expr_deps, field_dep->bitmap_offset + i) &&
        te->equality_deps[i].unknown_args &&
        !--te->equality_deps[i].unknown_args)
Sergey Petrunya's avatar
Sergey Petrunya committed
1030
    {
1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056
      /* Mark as bound and add to the list */
      Equality_module* eq_dep= &te->equality_deps[i];
      eq_dep->next= *bound_modules;
      *bound_modules= eq_dep;
    }
  }
}


static 
void run_elimination_wave(Table_elimination *te, Module_dep *bound_modules)
{
  Value_dep *bound_values= NULL;
  /* 
    Run the wave.
    All Func_dep-derived objects are divided into three classes:
    - Those that have bound=FALSE
    - Those that have bound=TRUE 
    - Those that have bound=TRUE and are in the list..

  */
  while (bound_modules)
  {
    for (;bound_modules; bound_modules= bound_modules->next)
    {
      switch (bound_modules->type)
Sergey Petrunya's avatar
Sergey Petrunya committed
1057
      {
Sergey Petrunya's avatar
Sergey Petrunya committed
1058
        case Module_dep::MODULE_EXPRESSION:
Sergey Petrunya's avatar
Sergey Petrunya committed
1059
        {
Sergey Petrunya's avatar
Sergey Petrunya committed
1060
          /*  It's a field=expr and we got to know the expr, so we know the field */
1061
          Equality_module *eq_dep= (Equality_module*)bound_modules;
Sergey Petrunya's avatar
Sergey Petrunya committed
1062
          if (!eq_dep->field->bound)
Sergey Petrunya's avatar
Sergey Petrunya committed
1063
          {
Sergey Petrunya's avatar
Sergey Petrunya committed
1064 1065
            /* Mark as bound and add to the list */
            eq_dep->field->bound= TRUE;
1066 1067
            eq_dep->field->next= bound_values;
            bound_values= eq_dep->field;
Sergey Petrunya's avatar
Sergey Petrunya committed
1068
          }
Sergey Petrunya's avatar
Sergey Petrunya committed
1069
          break;
Sergey Petrunya's avatar
Sergey Petrunya committed
1070
        }
Sergey Petrunya's avatar
Sergey Petrunya committed
1071
        case Module_dep::MODULE_UNIQUE_KEY:
1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083
        {
          /* Unique key is known means the table is known */
          Table_value *table_dep=((Key_module*)bound_modules)->table;
          if (!table_dep->bound)
          {
            /* Mark as bound and add to the list */
            table_dep->bound= TRUE;
            table_dep->next= bound_values;
            bound_values= table_dep;
          }
          break;
        }
Sergey Petrunya's avatar
Sergey Petrunya committed
1084
        case Module_dep::MODULE_OUTER_JOIN:
1085 1086 1087
        {
          Outer_join_module *outer_join_dep= (Outer_join_module*)bound_modules;
          mark_as_eliminated(te->join, outer_join_dep->table_list);
Sergey Petrunya's avatar
Sergey Petrunya committed
1088 1089 1090 1091 1092 1093
          if (!--te->n_outer_joins)
          {
            DBUG_PRINT("info", ("Table elimination eliminated everything" 
                                " it theoretically could"));
            return;
          }
1094 1095
          break;
        }
Sergey Petrunya's avatar
Sergey Petrunya committed
1096
        case Module_dep::MODULE_MULTI_EQUALITY:
1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
        default:
          DBUG_ASSERT(0);
      }
    }

    for (;bound_values; bound_values=bound_values->next)
    {
      switch (bound_values->type)
      {
        case Value_dep::VALUE_FIELD:
Sergey Petrunya's avatar
Sergey Petrunya committed
1107 1108
        {
          /*
Sergey Petrunya's avatar
Sergey Petrunya committed
1109 1110 1111
            Field became known. Check out
            - unique keys we belong to
            - expressions that depend on us.
Sergey Petrunya's avatar
Sergey Petrunya committed
1112
          */
1113 1114
          Field_value *field_dep= (Field_value*)bound_values;
          for (Key_module *key_dep= field_dep->table->keys; key_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
1115 1116 1117 1118 1119
               key_dep= key_dep->next_table_key)
          {
            DBUG_PRINT("info", ("key %s.%s is now bound",
                                key_dep->table->table->alias, 
                                key_dep->table->table->key_info[key_dep->keyno].name));
Sergey Petrunya's avatar
Sergey Petrunya committed
1120
            if (field_dep->field->part_of_key.is_set(key_dep->keyno) && 
1121
                key_dep->unknown_args && !--key_dep->unknown_args)
Sergey Petrunya's avatar
Sergey Petrunya committed
1122
            {
1123 1124 1125
              /* Mark as bound and add to the list */
              key_dep->next= bound_modules;
              bound_modules= key_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
1126
            }
Sergey Petrunya's avatar
Sergey Petrunya committed
1127
          }
1128
          signal_from_field_to_exprs(te, field_dep, &bound_modules);
Sergey Petrunya's avatar
Sergey Petrunya committed
1129
          break;
Sergey Petrunya's avatar
Sergey Petrunya committed
1130
        }
1131
        case Value_dep::VALUE_TABLE:
Sergey Petrunya's avatar
Sergey Petrunya committed
1132
        {
1133
          Table_value *table_dep=(Table_value*)bound_values; 
Sergey Petrunya's avatar
Sergey Petrunya committed
1134 1135 1136 1137 1138 1139 1140
          DBUG_PRINT("info", ("table %s is now bound",
                              table_dep->table->alias));
          /*
            Table is known means
            - all its fields are known
            - one more element in outer join nest is known
          */
1141
          for (Field_value *field_dep= table_dep->fields; field_dep; 
Sergey Petrunya's avatar
Sergey Petrunya committed
1142 1143 1144 1145 1146 1147
               field_dep= field_dep->next_table_field)
          {
            if (!field_dep->bound)
            {
              /* Mark as bound and add to the list */
              field_dep->bound= TRUE;
1148
              signal_from_field_to_exprs(te, field_dep, &bound_modules);
Sergey Petrunya's avatar
Sergey Petrunya committed
1149 1150
            }
          }
1151 1152
          for (Outer_join_module *outer_join_dep= table_dep->outer_join_dep;
               outer_join_dep; outer_join_dep= outer_join_dep->parent)
Sergey Petrunya's avatar
Sergey Petrunya committed
1153
          {
1154 1155 1156 1157 1158 1159 1160
            if (outer_join_dep->unknown_args && 
                !--outer_join_dep->unknown_args)
            {
              /* Mark as bound and add to the list */
              outer_join_dep->next= bound_modules;
              bound_modules= outer_join_dep;
            }
Sergey Petrunya's avatar
Sergey Petrunya committed
1161 1162 1163
          }
          break;
        }
1164
        default: 
Sergey Petrunya's avatar
Sergey Petrunya committed
1165
          DBUG_ASSERT(0);
Sergey Petrunya's avatar
Sergey Petrunya committed
1166
      }
Sergey Petrunya's avatar
Sergey Petrunya committed
1167
    }
Sergey Petrunya's avatar
Sergey Petrunya committed
1168
  }
Sergey Petrunia's avatar
Sergey Petrunia committed
1169 1170
}

Sergey Petrunya's avatar
Sergey Petrunya committed
1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206

/* 
  Mark one table or the whole join nest as eliminated.
*/
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl)
{
  TABLE *table;
  /*
    NOTE: there are TABLE_LIST object that have
    tbl->table!= NULL && tbl->nested_join!=NULL and 
    tbl->table == tbl->nested_join->join_list->element(..)->table
  */
  if (tbl->nested_join)
  {
    TABLE_LIST *child;
    List_iterator<TABLE_LIST> it(tbl->nested_join->join_list);
    while ((child= it++))
      mark_as_eliminated(join, child);
  }
  else if ((table= tbl->table))
  {
    JOIN_TAB *tab= tbl->table->reginfo.join_tab;
    if (!(join->const_table_map & tab->table->map))
    {
      DBUG_PRINT("info", ("Eliminated table %s", table->alias));
      tab->type= JT_CONST;
      join->eliminated_tables |= table->map;
      join->const_table_map|= table->map;
      set_position(join, join->const_tables++, tab, (KEYUSE*)0);
    }
  }

  if (tbl->on_expr)
    tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL);
}

Sergey Petrunya's avatar
Sergey Petrunya committed
1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217

#ifndef DBUG_OFF
static 
void dbug_print_deps(Table_elimination *te)
{
  DBUG_ENTER("dbug_print_deps");
  DBUG_LOCK_FILE;
  
  fprintf(DBUG_FILE,"deps {\n");
  
  /* Start with printing equalities */
1218
  for (Equality_module *eq_dep= te->equality_deps; 
Sergey Petrunya's avatar
Sergey Petrunya committed
1219 1220 1221 1222 1223
       eq_dep != te->equality_deps + te->n_equality_deps; eq_dep++)
  {
    char buf[128];
    String str(buf, sizeof(buf), &my_charset_bin);
    str.length(0);
Sergey Petrunya's avatar
Sergey Petrunya committed
1224
    eq_dep->expression->print(&str, QT_ORDINARY);
Sergey Petrunya's avatar
Sergey Petrunya committed
1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235
    fprintf(DBUG_FILE, "  equality%d: %s -> %s.%s\n", 
            eq_dep - te->equality_deps,
            str.c_ptr(),
            eq_dep->field->table->table->alias,
            eq_dep->field->field->field_name);
  }
  fprintf(DBUG_FILE,"\n");

  /* Then tables and their fields */
  for (uint i=0; i < MAX_TABLES; i++)
  {
1236
    Table_value *table_dep;
Sergey Petrunya's avatar
Sergey Petrunya committed
1237 1238 1239 1240 1241
    if ((table_dep= te->table_deps[i]))
    {
      /* Print table */
      fprintf(DBUG_FILE, "  table %s\n", table_dep->table->alias);
      /* Print fields */
1242
      for (Field_value *field_dep= table_dep->fields; field_dep; 
Sergey Petrunya's avatar
Sergey Petrunya committed
1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261
           field_dep= field_dep->next_table_field)
      {
        fprintf(DBUG_FILE, "    field %s.%s ->", table_dep->table->alias,
                field_dep->field->field_name);
        uint ofs= field_dep->bitmap_offset;
        for (uint bit= ofs; bit < ofs + te->n_equality_deps; bit++)
        {
          if (bitmap_is_set(&te->expr_deps, bit))
            fprintf(DBUG_FILE, " equality%d ", bit - ofs);
        }
        fprintf(DBUG_FILE, "\n");
      }
    }
  }
  fprintf(DBUG_FILE,"\n}\n");
  DBUG_UNLOCK_FILE;
  DBUG_VOID_RETURN;
}

1262
#endif 
Sergey Petrunia's avatar
Sergey Petrunia committed
1263 1264 1265 1266
/**
  @} (end of group Table_Elimination)
*/