← Back to branch summary

~ubuntu-branches/ubuntu/trusty/mariadb-5.5/trusty-proposed

« back to all changes in this revision

Viewing changes to sql/opt_table_elimination.cc

  • Committer: Package Import Robot
  • Author(s): Otto Kekäläinen
  • Date: 2013-12-22 10:27:05 UTC
  • Revision ID: package-import@ubuntu.com-20131222102705-mndw7s12mz0szrcn
Tags: upstream-5.5.32
Import upstream version 5.5.32

Show diffs side-by-side

added added

removed removed

Lines of Context:
sql/opt_table_elimination.cc
 
1
/*
 
2
   Copyright (c) 2009, 2011, Monty Program Ab
 
3
 
 
4
   This program is free software; you can redistribute it and/or modify
 
5
   it under the terms of the GNU General Public License as published by
 
6
   the Free Software Foundation; version 2 of the License.
 
7
 
 
8
   This program is distributed in the hope that it will be useful,
 
9
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
   GNU General Public License for more details.
 
12
 
 
13
   You should have received a copy of the GNU General Public License
 
14
   along with this program; if not, write to the Free Software
 
15
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
16
 
 
17
/**
 
18
  @file
 
19
 
 
20
  @brief
 
21
    Table Elimination Module
 
22
 
 
23
  @defgroup Table_Elimination Table Elimination Module
 
24
  @{
 
25
*/
 
26
 
 
27
#ifdef USE_PRAGMA_IMPLEMENTATION
 
28
#pragma implementation                          // gcc: Class implementation
 
29
#endif
 
30
 
 
31
#include "my_bit.h"
 
32
#include "sql_select.h"
 
33
 
 
34
/*
 
35
  OVERVIEW
 
36
  ========
 
37
 
 
38
  This file contains table elimination module. The idea behind table
 
39
  elimination is as follows: suppose we have a left join
 
40
 
 
41
    SELECT * FROM t1 LEFT JOIN 
 
42
      (t2 JOIN t3) ON t2.primary_key=t1.col AND 
 
43
                      t2.primary_key=t2.col
 
44
    WHERE ...
 
45
 
 
46
  such that
 
47
  * columns of the inner tables are not used anywhere ouside the outer join
 
48
    (not in WHERE, not in GROUP/ORDER BY clause, not in select list etc etc),
 
49
  * inner side of the outer join is guaranteed to produce at most one matching
 
50
    record combination for each record combination of outer tables.
 
51
  
 
52
  then the inner side of the outer join can be removed from the query, as it 
 
53
  will always produce only one record combination (either real or 
 
54
  null-complemented one) and we don't care about what that record combination 
 
55
  is.
 
56
 
 
57
 
 
58
  MODULE INTERFACE
 
59
  ================
 
60
 
 
61
  The module has one entry point - the eliminate_tables() function, which one
 
62
  needs to call (once) at some point before join optimization.
 
63
  eliminate_tables() operates over the JOIN structures. Logically, it
 
64
  removes the inner tables of an outer join operation together with the
 
65
  operation itself. Physically, it changes the following members:
 
66
 
 
67
  * Eliminated tables are marked as constant and moved to the front of the
 
68
    join order.
 
69
 
 
70
  * In addition to this, they are recorded in JOIN::eliminated_tables bitmap.
 
71
 
 
72
  * Items that became disused because they were in the ON expression of an 
 
73
    eliminated outer join are notified by means of the Item tree walk which 
 
74
    calls Item::mark_as_eliminated_processor for every item
 
75
    - At the moment the only Item that cares whether it was eliminated is 
 
76
      Item_subselect with its Item_subselect::eliminated flag which is used
 
77
      by EXPLAIN code to check if the subquery should be shown in EXPLAIN.
 
78
 
 
79
  Table elimination is redone on every PS re-execution.
 
80
 
 
81
 
 
82
  TABLE ELIMINATION ALGORITHM FOR ONE OUTER JOIN
 
83
  ==============================================
 
84
 
 
85
  As described above, we can remove inner side of an outer join if it is 
 
86
 
 
87
    1. not referred to from any other parts of the query
 
88
    2. always produces one matching record combination.
 
89
 
 
90
  We check #1 by doing a recursive descent down the join->join_list while
 
91
  maintaining a union of used_tables() attribute of all Item expressions in
 
92
  other parts of the query. When we encounter an outer join, we check if the
 
93
  bitmap of tables on its inner side has intersection with tables that are used
 
94
  elsewhere. No intersection means that inner side of the outer join could 
 
95
  potentially be eliminated.
 
96
 
 
97
  In order to check #2, one needs to prove that inner side of an outer join 
 
98
  is functionally dependent on the outside. The proof is constructed from
 
99
  functional dependencies of intermediate objects:
 
100
 
 
101
  - Inner side of outer join is functionally dependent when each of its tables
 
102
    are functionally dependent. (We assume a table is functionally dependent 
 
103
    when its dependencies allow to uniquely identify one table record, or no
 
104
    records).
 
105
 
 
106
  - Table is functionally dependent when it has got a unique key whose columns
 
107
    are functionally dependent.
 
108
 
 
109
  - A column is functionally dependent when we could locate an AND-part of a
 
110
    certain ON clause in form 
 
111
      
 
112
      tblX.columnY= expr 
 
113
    
 
114
    where expr is functionally depdendent. expr is functionally dependent when 
 
115
    all columns that it refers to are functionally dependent.
 
116
 
 
117
  These relationships are modeled as a bipartite directed graph that has
 
118
  dependencies as edges and two kinds of nodes:
 
119
 
 
120
  Value nodes:
 
121
   - Table column values (each is a value of tblX.columnY)
 
122
   - Table values (each node represents a table inside the join nest we're
 
123
     trying to eliminate).
 
124
  A value has one attribute, it is either bound (i.e. functionally dependent) 
 
125
  or not.
 
126
 
 
127
  Module nodes:
 
128
   - Modules representing tblX.colY=expr equalities. Equality module has 
 
129
      = incoming edges from columns used in expr 
 
130
      = outgoing edge to tblX.colY column.
 
131
   - Nodes representing unique keys. Unique key has
 
132
      = incoming edges from key component value modules
 
133
      = outgoing edge to key's table module
 
134
   - Inner side of outer join module. Outer join module has
 
135
      = incoming edges from table value modules
 
136
      = No outgoing edges. Once we reach it, we know we can eliminate the 
 
137
        outer join.
 
138
  A module may depend on multiple values, and hence its primary attribute is
 
139
  the number of its arguments that are not bound. 
 
140
 
 
141
  The algorithm starts with equality nodes that don't have any incoming edges
 
142
  (their expressions are either constant or depend only on tables that are
 
143
  outside of the outer join in question) and performns a breadth-first
 
144
  traversal. If we reach the outer join nest node, it means outer join is
 
145
  functionally dependent and can be eliminated. Otherwise it cannot be
 
146
  eliminated.
 
147
 
 
148
  HANDLING MULTIPLE NESTED OUTER JOINS
 
149
  ====================================
 
150
 
 
151
  Outer joins that are not nested one within another are eliminated
 
152
  independently. For nested outer joins we have the following considerations:
 
153
  
 
154
  1. ON expressions from children outer joins must be taken into account 
 
155
   
 
156
  Consider this example:
 
157
 
 
158
    SELECT t0.* 
 
159
    FROM 
 
160
      t0  
 
161
    LEFT JOIN 
 
162
      (t1 LEFT JOIN t2 ON t2.primary_key=t1.col1)
 
163
    ON 
 
164
      t1.primary_key=t0.col AND t2.col1=t1.col2
 
165
 
 
166
  Here we cannot eliminate the "... LEFT JOIN t2 ON ..." part alone because the
 
167
  ON clause of top level outer join has references to table t2. 
 
168
  We can eliminate the entire  "... LEFT JOIN (t1 LEFT JOIN t2) ON .." part,
 
169
  but in order to do that, we must look at both ON expressions.
 
170
  
 
171
  2. ON expressions of parent outer joins are useless.
 
172
  Consider an example:
 
173
 
 
174
    SELECT t0.* 
 
175
    FROM
 
176
      t0 
 
177
    LEFT JOIN 
 
178
      (t1 LEFT JOIN t2 ON some_expr)
 
179
    ON
 
180
      t2.primary_key=t1.col  -- (*)
 
181
  
 
182
  Here the uppermost ON expression has a clause that gives us functional
 
183
  dependency of table t2 on t1 and hence could be used to eliminate the
 
184
  "... LEFT JOIN t2 ON..." part.
 
185
  However, we would not actually encounter this situation, because before the
 
186
  table elimination we run simplify_joins(), which, among other things, upon
 
187
  seeing a functional dependency condition like (*) will convert the outer join
 
188
  of
 
189
    
 
190
    "... LEFT JOIN t2 ON ..."
 
191
  
 
192
  into inner join and thus make table elimination not to consider eliminating
 
193
  table t2.
 
194
*/
 
195
 
 
196
class Dep_value;
 
197
  class Dep_value_field;
 
198
  class Dep_value_table;
 
199
 
 
200
 
 
201
class Dep_module;
 
202
  class Dep_module_expr;
 
203
  class Dep_module_goal;
 
204
  class Dep_module_key;
 
205
 
 
206
class Dep_analysis_context;
 
207
 
 
208
 
 
209
/*
 
210
  A value, something that can be bound or not bound. One can also iterate over 
 
211
  unbound modules that depend on this value
 
212
*/
 
213
 
 
214
class Dep_value : public Sql_alloc
 
215
{
 
216
public:
 
217
  Dep_value(): bound(FALSE) {}
 
218
  virtual ~Dep_value(){} /* purecov: inspected */ /* stop compiler warnings */
 
219
  
 
220
  bool is_bound() { return bound; }
 
221
  void make_bound() { bound= TRUE; }
 
222
 
 
223
  /* Iteration over unbound modules that depend on this value */
 
224
  typedef char *Iterator;
 
225
  virtual Iterator init_unbound_modules_iter(char *buf)=0;
 
226
  virtual Dep_module* get_next_unbound_module(Dep_analysis_context *dac,
 
227
                                              Iterator iter) = 0;
 
228
  static const size_t iterator_size;
 
229
protected:
 
230
  bool bound;
 
231
};
 
232
 
 
233
 
 
234
/*
 
235
  A table field value. There is exactly only one such object for any tblX.fieldY
 
236
  - the field depends on its table and equalities
 
237
  - expressions that use the field are its dependencies
 
238
*/
 
239
 
 
240
class Dep_value_field : public Dep_value
 
241
{
 
242
public:
 
243
  Dep_value_field(Dep_value_table *table_arg, Field *field_arg) :
 
244
    table(table_arg), field(field_arg)
 
245
  {}
 
246
 
 
247
  Dep_value_table *table; /* Table this field is from */
 
248
  Field *field; /* Field this object is representing */
 
249
  
 
250
  /* Iteration over unbound modules that are our dependencies */
 
251
  Iterator init_unbound_modules_iter(char *buf);
 
252
  Dep_module* get_next_unbound_module(Dep_analysis_context *dac, 
 
253
                                      Iterator iter);
 
254
  
 
255
  void make_unbound_modules_iter_skip_keys(Iterator iter);
 
256
  
 
257
  static const size_t iterator_size;
 
258
private:
 
259
  /* 
 
260
    Field_deps that belong to one table form a linked list, ordered by
 
261
    field_index 
 
262
  */
 
263
  Dep_value_field *next_table_field;
 
264
 
 
265
  /*
 
266
    Offset to bits in Dep_analysis_context::expr_deps (see comment to that 
 
267
    member for semantics of the bits).
 
268
  */
 
269
  uint bitmap_offset;
 
270
 
 
271
  class Module_iter
 
272
  {
 
273
  public:
 
274
    /* if not null, return this and advance */
 
275
    Dep_module_key *key_dep;
 
276
    /* Otherwise, this and advance */
 
277
    uint equality_no;
 
278
  };
 
279
  friend class Dep_analysis_context;
 
280
  friend class Field_dependency_recorder; 
 
281
  friend class Dep_value_table;
 
282
};
 
283
 
 
284
const size_t Dep_value_field::iterator_size=
 
285
  ALIGN_SIZE(sizeof(Dep_value_field::Module_iter));
 
286
 
 
287
 
 
288
/*
 
289
  A table value. There is one Dep_value_table object for every table that can
 
290
  potentially be eliminated.
 
291
 
 
292
  Table becomes bound as soon as some of its unique keys becomes bound
 
293
  Once the table is bound:
 
294
   - all of its fields are bound
 
295
   - its embedding outer join has one less unknown argument
 
296
*/
 
297
 
 
298
class Dep_value_table : public Dep_value
 
299
{
 
300
public:
 
301
  Dep_value_table(TABLE *table_arg) : 
 
302
    table(table_arg), fields(NULL), keys(NULL)
 
303
  {}
 
304
  TABLE *table;  /* Table this object is representing */
 
305
  /* Ordered list of fields that belong to this table */
 
306
  Dep_value_field *fields;
 
307
  Dep_module_key *keys; /* Ordered list of Unique keys in this table */
 
308
 
 
309
  /* Iteration over unbound modules that are our dependencies */
 
310
  Iterator init_unbound_modules_iter(char *buf);
 
311
  Dep_module* get_next_unbound_module(Dep_analysis_context *dac, 
 
312
                                      Iterator iter);
 
313
  static const size_t iterator_size;
 
314
private:
 
315
  class Module_iter
 
316
  {
 
317
  public:
 
318
    /* Space for field iterator */
 
319
    char buf[Dep_value_field::iterator_size];
 
320
    /* !NULL <=> iterating over depdenent modules of this field */
 
321
    Dep_value_field *field_dep; 
 
322
    bool returned_goal;
 
323
  };
 
324
};
 
325
 
 
326
 
 
327
const size_t Dep_value_table::iterator_size=
 
328
  ALIGN_SIZE(sizeof(Dep_value_table::Module_iter));
 
329
 
 
330
const size_t Dep_value::iterator_size=
 
331
  max(Dep_value_table::iterator_size, Dep_value_field::iterator_size);
 
332
 
 
333
 
 
334
/*
 
335
  A 'module'. Module has unsatisfied dependencies, number of whose is stored in
 
336
  unbound_args. Modules also can be linked together in a list.
 
337
*/
 
338
 
 
339
class Dep_module : public Sql_alloc
 
340
{
 
341
public:
 
342
  virtual ~Dep_module(){}  /* purecov: inspected */ /* stop compiler warnings */
 
343
  
 
344
  /* Mark as bound. Currently is non-virtual and does nothing */
 
345
  void make_bound() {};
 
346
 
 
347
  /* 
 
348
    The final module will return TRUE here. When we see that TRUE was returned,
 
349
    that will mean that functional dependency check succeeded.
 
350
  */
 
351
  virtual bool is_final () { return FALSE; }
 
352
 
 
353
  /* 
 
354
    Increment number of bound arguments. this is expected to change
 
355
    is_applicable() from false to true after sufficient set of arguments is
 
356
    bound.
 
357
  */
 
358
  void touch() { unbound_args--; }
 
359
  bool is_applicable() { return !test(unbound_args); }
 
360
  
 
361
  /* Iteration over values that */
 
362
  typedef char *Iterator;
 
363
  virtual Iterator init_unbound_values_iter(char *buf)=0;
 
364
  virtual Dep_value* get_next_unbound_value(Dep_analysis_context *dac,
 
365
                                            Iterator iter)=0;
 
366
  static const size_t iterator_size;
 
367
protected:
 
368
  uint unbound_args;
 
369
  
 
370
  Dep_module() : unbound_args(0) {}
 
371
  /* to bump unbound_args when constructing depedendencies */
 
372
  friend class Field_dependency_recorder; 
 
373
  friend class Dep_analysis_context;
 
374
};
 
375
 
 
376
 
 
377
/*
 
378
  This represents either
 
379
   - "tbl.column= expr" equality dependency, i.e. tbl.column depends on fields
 
380
     used in the expression, or
 
381
   - tbl1.col1=tbl2.col2=... multi-equality.
 
382
*/
 
383
 
 
384
class Dep_module_expr : public Dep_module
 
385
{
 
386
public:
 
387
  Dep_value_field *field;
 
388
  Item  *expr;
 
389
  
 
390
  List<Dep_value_field> *mult_equal_fields;
 
391
  /* Used during condition analysis only, similar to KEYUSE::level */
 
392
  uint level;
 
393
 
 
394
  Iterator init_unbound_values_iter(char *buf);
 
395
  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
 
396
  static const size_t iterator_size;
 
397
private:
 
398
  class Value_iter
 
399
  {
 
400
  public:
 
401
    Dep_value_field *field;
 
402
    List_iterator<Dep_value_field> it;
 
403
  };
 
404
};
 
405
 
 
406
const size_t Dep_module_expr::iterator_size=
 
407
  ALIGN_SIZE(sizeof(Dep_module_expr::Value_iter));
 
408
 
 
409
 
 
410
/*
 
411
  A Unique key module
 
412
   - Unique key has all of its components as arguments
 
413
   - Once unique key is bound, its table value is known
 
414
*/
 
415
 
 
416
class Dep_module_key: public Dep_module
 
417
{
 
418
public:
 
419
  Dep_module_key(Dep_value_table *table_arg, uint keyno_arg, uint n_parts_arg) :
 
420
    table(table_arg), keyno(keyno_arg), next_table_key(NULL)
 
421
  {
 
422
    unbound_args= n_parts_arg;
 
423
  }
 
424
  Dep_value_table *table; /* Table this key is from */
 
425
  uint keyno;  /* The index we're representing */
 
426
  /* Unique keys form a linked list, ordered by keyno */
 
427
  Dep_module_key *next_table_key;
 
428
  
 
429
  Iterator init_unbound_values_iter(char *buf);
 
430
  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter);
 
431
  static const size_t iterator_size;
 
432
private:
 
433
  class Value_iter
 
434
  {
 
435
  public:
 
436
    Dep_value_table *table;
 
437
  };
 
438
};
 
439
 
 
440
const size_t Dep_module_key::iterator_size= 
 
441
  ALIGN_SIZE(sizeof(Dep_module_key::Value_iter));
 
442
 
 
443
const size_t Dep_module::iterator_size=
 
444
  max(Dep_module_expr::iterator_size, Dep_module_key::iterator_size);
 
445
 
 
446
 
 
447
/*
 
448
  A module that represents outer join that we're trying to eliminate. If we 
 
449
  manage to declare this module to be bound, then outer join can be eliminated.
 
450
*/
 
451
 
 
452
class Dep_module_goal: public Dep_module
 
453
{
 
454
public:
 
455
  Dep_module_goal(uint n_children)  
 
456
  {
 
457
    unbound_args= n_children;
 
458
  }
 
459
  bool is_final() { return TRUE; }
 
460
  /* 
 
461
    This is the goal module, so the running wave algorithm should terminate
 
462
    once it sees that this module is applicable and should never try to apply
 
463
    it, hence no use for unbound value iterator implementation.
 
464
  */
 
465
  Iterator init_unbound_values_iter(char *buf)
 
466
  { 
 
467
    DBUG_ASSERT(0); 
 
468
    return NULL;
 
469
  }
 
470
  Dep_value* get_next_unbound_value(Dep_analysis_context *dac, Iterator iter)
 
471
  {
 
472
    DBUG_ASSERT(0); 
 
473
    return NULL;
 
474
  }
 
475
};
 
476
 
 
477
 
 
478
/*
 
479
  Functional dependency analyzer context
 
480
*/
 
481
class Dep_analysis_context
 
482
{
 
483
public:
 
484
  bool setup_equality_modules_deps(List<Dep_module> *bound_modules);
 
485
  bool run_wave(List<Dep_module> *new_bound_modules);
 
486
 
 
487
  /* Tables that we're looking at eliminating */
 
488
  table_map usable_tables;
 
489
  
 
490
  /* Array of equality dependencies */
 
491
  Dep_module_expr *equality_mods;
 
492
  uint n_equality_mods; /* Number of elements in the array */
 
493
  uint n_equality_mods_alloced;
 
494
 
 
495
  /* tablenr -> Dep_value_table* mapping. */
 
496
  Dep_value_table *table_deps[MAX_KEY];
 
497
  
 
498
  /* Element for the outer join we're attempting to eliminate */
 
499
  Dep_module_goal *outer_join_dep;
 
500
 
 
501
  /* 
 
502
    Bitmap of how expressions depend on bits. Given a Dep_value_field object,
 
503
    one can check bitmap_is_set(expr_deps, field_val->bitmap_offset + expr_no)
 
504
    to see if expression equality_mods[expr_no] depends on the given field.
 
505
  */
 
506
  MY_BITMAP expr_deps;
 
507
  
 
508
  Dep_value_table *create_table_value(TABLE *table);
 
509
  Dep_value_field *get_field_value(Field *field);
 
510
 
 
511
#ifndef DBUG_OFF
 
512
  void dbug_print_deps();
 
513
#endif 
 
514
};
 
515
 
 
516
 
 
517
void eliminate_tables(JOIN *join);
 
518
 
 
519
static bool
 
520
eliminate_tables_for_list(JOIN *join, 
 
521
                          List<TABLE_LIST> *join_list,
 
522
                          table_map tables_in_list,
 
523
                          Item *on_expr,
 
524
                          table_map tables_used_elsewhere);
 
525
static
 
526
bool check_func_dependency(JOIN *join, 
 
527
                           table_map dep_tables,
 
528
                           List_iterator<TABLE_LIST> *it, 
 
529
                           TABLE_LIST *oj_tbl,
 
530
                           Item* cond);
 
531
static 
 
532
void build_eq_mods_for_cond(Dep_analysis_context *dac, 
 
533
                            Dep_module_expr **eq_mod, uint *and_level, 
 
534
                            Item *cond);
 
535
static 
 
536
void check_equality(Dep_analysis_context *dac, Dep_module_expr **eq_mod, 
 
537
                    uint and_level, Item_func *cond, Item *left, Item *right);
 
538
static 
 
539
Dep_module_expr *merge_eq_mods(Dep_module_expr *start, 
 
540
                                 Dep_module_expr *new_fields, 
 
541
                                 Dep_module_expr *end, uint and_level);
 
542
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
 
543
static 
 
544
void add_module_expr(Dep_analysis_context *dac, Dep_module_expr **eq_mod,
 
545
                     uint and_level, Dep_value_field *field_val, Item *right,
 
546
                     List<Dep_value_field>* mult_equal_fields);
 
547
 
 
548
 
 
549
/*****************************************************************************/
 
550
 
 
551
/*
 
552
  Perform table elimination
 
553
 
 
554
  SYNOPSIS
 
555
    eliminate_tables()
 
556
      join                   Join to work on
 
557
 
 
558
  DESCRIPTION
 
559
    This is the entry point for table elimination. Grep for MODULE INTERFACE
 
560
    section in this file for calling convention.
 
561
 
 
562
    The idea behind table elimination is that if we have an outer join:
 
563
   
 
564
      SELECT * FROM t1 LEFT JOIN 
 
565
        (t2 JOIN t3) ON t2.primary_key=t1.col AND 
 
566
                        t3.primary_key=t2.col
 
567
    such that
 
568
 
 
569
    1. columns of the inner tables are not used anywhere ouside the outer
 
570
       join (not in WHERE, not in GROUP/ORDER BY clause, not in select list 
 
571
       etc etc), and
 
572
    2. inner side of the outer join is guaranteed to produce at most one
 
573
       record combination for each record combination of outer tables.
 
574
    
 
575
    then the inner side of the outer join can be removed from the query.
 
576
    This is because it will always produce one matching record (either a
 
577
    real match or a NULL-complemented record combination), and since there
 
578
    are no references to columns of the inner tables anywhere, it doesn't
 
579
    matter which record combination it was.
 
580
 
 
581
    This function primary handles checking #1. It collects a bitmap of
 
582
    tables that are not used in select list/GROUP BY/ORDER BY/HAVING/etc and
 
583
    thus can possibly be eliminated.
 
584
 
 
585
    After this, if #1 is met, the function calls eliminate_tables_for_list()
 
586
    that checks #2.
 
587
  
 
588
  SIDE EFFECTS
 
589
    See the OVERVIEW section at the top of this file.
 
590
 
 
591
*/
 
592
 
 
593
void eliminate_tables(JOIN *join)
 
594
{
 
595
  THD* thd= join->thd;
 
596
  Item *item;
 
597
  table_map used_tables;
 
598
  DBUG_ENTER("eliminate_tables");
 
599
  
 
600
  DBUG_ASSERT(join->eliminated_tables == 0);
 
601
 
 
602
  /* If there are no outer joins, we have nothing to eliminate: */
 
603
  if (!join->outer_join)
 
604
    DBUG_VOID_RETURN;
 
605
 
 
606
  if (!optimizer_flag(thd, OPTIMIZER_SWITCH_TABLE_ELIMINATION))
 
607
    DBUG_VOID_RETURN; /* purecov: inspected */
 
608
 
 
609
  /* Find the tables that are referred to from WHERE/HAVING */
 
610
  used_tables= (join->conds?  join->conds->used_tables() : 0) | 
 
611
               (join->having? join->having->used_tables() : 0);
 
612
  
 
613
  /* Add tables referred to from the select list */
 
614
  List_iterator<Item> it(join->fields_list);
 
615
  while ((item= it++))
 
616
    used_tables |= item->used_tables();
 
617
 
 
618
  /* Add tables referred to from ORDER BY and GROUP BY lists */
 
619
  ORDER *all_lists[]= { join->order, join->group_list};
 
620
  for (int i=0; i < 2; i++)
 
621
  {
 
622
    for (ORDER *cur_list= all_lists[i]; cur_list; cur_list= cur_list->next)
 
623
      used_tables |= (*(cur_list->item))->used_tables();
 
624
  }
 
625
  
 
626
  if (join->select_lex == &thd->lex->select_lex)
 
627
  {
 
628
 
 
629
    /* Multi-table UPDATE: don't eliminate tables referred from SET statement */
 
630
    if (thd->lex->sql_command == SQLCOM_UPDATE_MULTI)
 
631
    {
 
632
      /* Multi-table UPDATE and DELETE: don't eliminate the tables we modify: */
 
633
      used_tables |= thd->table_map_for_update;
 
634
      List_iterator<Item> it2(thd->lex->value_list);
 
635
      while ((item= it2++))
 
636
        used_tables |= item->used_tables();
 
637
    }
 
638
 
 
639
    if (thd->lex->sql_command == SQLCOM_DELETE_MULTI)
 
640
    {
 
641
      TABLE_LIST *tbl;
 
642
      for (tbl= (TABLE_LIST*)thd->lex->auxiliary_table_list.first;
 
643
           tbl; tbl= tbl->next_local)
 
644
      {
 
645
        used_tables |= tbl->table->map;
 
646
      }
 
647
    }
 
648
  }
 
649
  
 
650
  table_map all_tables= join->all_tables_map();
 
651
  if (all_tables & ~used_tables)
 
652
  {
 
653
    /* There are some tables that we probably could eliminate. Try it. */
 
654
    eliminate_tables_for_list(join, join->join_list, all_tables, NULL,
 
655
                              used_tables);
 
656
  }
 
657
  DBUG_VOID_RETURN;
 
658
}
 
659
 
 
660
 
 
661
/*
 
662
  Perform table elimination in a given join list
 
663
 
 
664
  SYNOPSIS
 
665
    eliminate_tables_for_list()
 
666
      join                    The join we're working on
 
667
      join_list               Join list to eliminate tables from (and if
 
668
                              on_expr !=NULL, then try eliminating join_list
 
669
                              itself)
 
670
      list_tables             Bitmap of tables embedded in the join_list.
 
671
      on_expr                 ON expression, if the join list is the inner side
 
672
                              of an outer join.
 
673
                              NULL means it's not an outer join but rather a
 
674
                              top-level join list.
 
675
      tables_used_elsewhere   Bitmap of tables that are referred to from
 
676
                              somewhere outside of the join list (e.g.
 
677
                              select list, HAVING, other ON expressions, etc).
 
678
 
 
679
  DESCRIPTION
 
680
    Perform table elimination in a given join list:
 
681
    - First, walk through join list members and try doing table elimination for
 
682
      them.
 
683
    - Then, if the join list itself is an inner side of outer join
 
684
      (on_expr!=NULL), then try to eliminate the entire join list.
 
685
 
 
686
    See "HANDLING MULTIPLE NESTED OUTER JOINS" section at the top of this file
 
687
    for more detailed description and justification.
 
688
    
 
689
  RETURN
 
690
    TRUE   The entire join list eliminated
 
691
    FALSE  Join list wasn't eliminated (but some of its child outer joins 
 
692
           possibly were)
 
693
*/
 
694
 
 
695
static bool
 
696
eliminate_tables_for_list(JOIN *join, List<TABLE_LIST> *join_list,
 
697
                          table_map list_tables, Item *on_expr,
 
698
                          table_map tables_used_elsewhere)
 
699
{
 
700
  TABLE_LIST *tbl;
 
701
  List_iterator<TABLE_LIST> it(*join_list);
 
702
  table_map tables_used_on_left= 0;
 
703
  bool all_eliminated= TRUE;
 
704
 
 
705
  while ((tbl= it++))
 
706
  {
 
707
    if (tbl->on_expr)
 
708
    {
 
709
      table_map outside_used_tables= tables_used_elsewhere | 
 
710
                                     tables_used_on_left;
 
711
      if (on_expr)
 
712
        outside_used_tables |= on_expr->used_tables();
 
713
      if (tbl->nested_join)
 
714
      {
 
715
        /* This is  "... LEFT JOIN (join_nest) ON cond" */
 
716
        if (eliminate_tables_for_list(join,
 
717
                                      &tbl->nested_join->join_list, 
 
718
                                      tbl->nested_join->used_tables, 
 
719
                                      tbl->on_expr,
 
720
                                      outside_used_tables))
 
721
        {
 
722
          mark_as_eliminated(join, tbl);
 
723
        }
 
724
        else
 
725
          all_eliminated= FALSE;
 
726
      }
 
727
      else
 
728
      {
 
729
        /* This is  "... LEFT JOIN tbl ON cond" */
 
730
        if (!(tbl->table->map & outside_used_tables) &&
 
731
            check_func_dependency(join, tbl->table->map, NULL, tbl, 
 
732
                                  tbl->on_expr))
 
733
        {
 
734
          mark_as_eliminated(join, tbl);
 
735
        }
 
736
        else
 
737
          all_eliminated= FALSE;
 
738
      }
 
739
      tables_used_on_left |= tbl->on_expr->used_tables();
 
740
    }
 
741
    else
 
742
    {
 
743
      DBUG_ASSERT(!tbl->nested_join || tbl->sj_on_expr);
 
744
      //psergey-todo: is the following really correct or we'll need to descend
 
745
      //down all ON clauses: ? 
 
746
      if (tbl->sj_on_expr)
 
747
        tables_used_on_left |= tbl->sj_on_expr->used_tables();
 
748
    }
 
749
  }
 
750
 
 
751
  /* Try eliminating the nest we're called for */
 
752
  if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere))
 
753
  {
 
754
    it.rewind();
 
755
    return check_func_dependency(join, list_tables & ~join->eliminated_tables,
 
756
                                 &it, NULL, on_expr);
 
757
  }
 
758
  return FALSE; /* not eliminated */
 
759
}
 
760
 
 
761
 
 
762
/*
 
763
  Check if given condition makes given set of tables functionally dependent
 
764
 
 
765
  SYNOPSIS
 
766
    check_func_dependency()
 
767
      join         Join we're procesing
 
768
      dep_tables   Tables that we check to be functionally dependent (on
 
769
                   everything else)
 
770
      it           Iterator that enumerates these tables, or NULL if we're 
 
771
                   checking one single table and it is specified in oj_tbl
 
772
                   parameter.
 
773
      oj_tbl       NULL, or one single table that we're checking
 
774
      cond         Condition to use to prove functional dependency
 
775
 
 
776
  DESCRIPTION
 
777
    Check if we can use given condition to infer that the set of given tables
 
778
    is functionally dependent on everything else.
 
779
 
 
780
  RETURN 
 
781
    TRUE  - Yes, functionally dependent
 
782
    FALSE - No, or error
 
783
*/
 
784
 
 
785
static
 
786
bool check_func_dependency(JOIN *join,
 
787
                           table_map dep_tables,
 
788
                           List_iterator<TABLE_LIST> *it, 
 
789
                           TABLE_LIST *oj_tbl,
 
790
                           Item* cond)
 
791
{
 
792
  Dep_analysis_context dac;
 
793
  
 
794
  /* 
 
795
    Pre-alloc some Dep_module_expr structures. We don't need this to be
 
796
    guaranteed upper bound.
 
797
  */
 
798
  dac.n_equality_mods_alloced= 
 
799
    join->thd->lex->current_select->max_equal_elems +
 
800
    (join->thd->lex->current_select->cond_count+1)*2 +
 
801
    join->thd->lex->current_select->between_count;
 
802
 
 
803
  bzero(dac.table_deps, sizeof(dac.table_deps));
 
804
  if (!(dac.equality_mods= new Dep_module_expr[dac.n_equality_mods_alloced]))
 
805
    return FALSE; /* purecov: inspected */
 
806
 
 
807
  Dep_module_expr* last_eq_mod= dac.equality_mods;
 
808
  
 
809
  /* Create Dep_value_table objects for all tables we're trying to eliminate */
 
810
  if (oj_tbl)
 
811
  {
 
812
    if (!dac.create_table_value(oj_tbl->table))
 
813
      return FALSE; /* purecov: inspected */
 
814
  }
 
815
  else
 
816
  {
 
817
    TABLE_LIST *tbl; 
 
818
    while ((tbl= (*it)++))
 
819
    {
 
820
      if (tbl->table && (tbl->table->map & dep_tables))
 
821
      {
 
822
        if (!dac.create_table_value(tbl->table))
 
823
          return FALSE; /* purecov: inspected */
 
824
      }
 
825
    }
 
826
  }
 
827
  dac.usable_tables= dep_tables;
 
828
 
 
829
  /*
 
830
    Analyze the the ON expression and create Dep_module_expr objects and
 
831
      Dep_value_field objects for the used fields.
 
832
  */
 
833
  uint and_level=0;
 
834
  build_eq_mods_for_cond(&dac, &last_eq_mod, &and_level, cond);
 
835
  if (!(dac.n_equality_mods= last_eq_mod - dac.equality_mods))
 
836
    return FALSE;  /* No useful conditions */
 
837
 
 
838
  List<Dep_module> bound_modules;
 
839
 
 
840
  if (!(dac.outer_join_dep= new Dep_module_goal(my_count_bits(dep_tables))) ||
 
841
      dac.setup_equality_modules_deps(&bound_modules))
 
842
  {
 
843
    return FALSE; /* OOM, default to non-dependent */ /* purecov: inspected */
 
844
  }
 
845
  
 
846
  DBUG_EXECUTE("test", dac.dbug_print_deps(); );
 
847
  
 
848
  return dac.run_wave(&bound_modules);
 
849
}
 
850
 
 
851
 
 
852
/*
 
853
  Running wave functional dependency check algorithm
 
854
 
 
855
  SYNOPSIS
 
856
   Dep_analysis_context::run_wave()
 
857
     new_bound_modules  List of bound modules to start the running wave from. 
 
858
                        The list is destroyed during execution
 
859
  
 
860
  DESCRIPTION
 
861
    This function uses running wave algorithm to check if the join nest is
 
862
    functionally-dependent. 
 
863
    We start from provided list of bound modules, and then run the wave across 
 
864
    dependency edges, trying the reach the Dep_module_goal module. If we manage
 
865
    to reach it, then the join nest is functionally-dependent, otherwise it is
 
866
    not.
 
867
 
 
868
  RETURN 
 
869
    TRUE   Yes, functionally dependent
 
870
    FALSE  No.
 
871
*/
 
872
 
 
873
bool Dep_analysis_context::run_wave(List<Dep_module> *new_bound_modules)
 
874
{
 
875
  List<Dep_value> new_bound_values;
 
876
  
 
877
  Dep_value *value;
 
878
  Dep_module *module;
 
879
 
 
880
  while (!new_bound_modules->is_empty())
 
881
  {
 
882
    /*
 
883
      The "wave" is in new_bound_modules list. Iterate over values that can be
 
884
      reached from these modules but are not yet bound, and collect the next
 
885
      wave generation in new_bound_values list.
 
886
    */
 
887
    List_iterator<Dep_module> modules_it(*new_bound_modules);
 
888
    while ((module= modules_it++))
 
889
    {
 
890
      char iter_buf[Dep_module::iterator_size + ALIGN_MAX_UNIT];
 
891
      Dep_module::Iterator iter;
 
892
      iter= module->init_unbound_values_iter(iter_buf);
 
893
      while ((value= module->get_next_unbound_value(this, iter)))
 
894
      {
 
895
        value->make_bound();
 
896
        new_bound_values.push_back(value);
 
897
      }
 
898
    }
 
899
    new_bound_modules->empty();
 
900
    
 
901
    /*
 
902
      Now walk over list of values we've just found to be bound and check which
 
903
      unbound modules can be reached from them. If there are some modules that
 
904
      became bound, collect them in new_bound_modules list.
 
905
    */
 
906
    List_iterator<Dep_value> value_it(new_bound_values);
 
907
    while ((value= value_it++))
 
908
    {
 
909
      char iter_buf[Dep_value::iterator_size + ALIGN_MAX_UNIT];
 
910
      Dep_value::Iterator iter;
 
911
      iter= value->init_unbound_modules_iter(iter_buf);
 
912
      while ((module= value->get_next_unbound_module(this, iter)))
 
913
      {
 
914
        module->touch();
 
915
        if (!module->is_applicable())
 
916
          continue;
 
917
        if (module->is_final())
 
918
          return TRUE; /* Functionally dependent */
 
919
        module->make_bound();
 
920
        new_bound_modules->push_back(module);
 
921
      }
 
922
    }
 
923
    new_bound_values.empty();
 
924
  }
 
925
  return FALSE;
 
926
}
 
927
 
 
928
 
 
929
/*
 
930
  This is used to analyze expressions in "tbl.col=expr" dependencies so
 
931
  that we can figure out which fields the expression depends on.
 
932
*/
 
933
 
 
934
class Field_dependency_recorder : public Field_enumerator
 
935
{
 
936
public:
 
937
  Field_dependency_recorder(Dep_analysis_context *ctx_arg): ctx(ctx_arg)
 
938
  {}
 
939
  
 
940
  void visit_field(Item_field *item)
 
941
  {
 
942
    Field *field= item->field;
 
943
    Dep_value_table *tbl_dep;
 
944
    if ((tbl_dep= ctx->table_deps[field->table->tablenr]))
 
945
    {
 
946
      for (Dep_value_field *field_dep= tbl_dep->fields; field_dep; 
 
947
           field_dep= field_dep->next_table_field)
 
948
      {
 
949
        if (field->field_index == field_dep->field->field_index)
 
950
        {
 
951
          uint offs= field_dep->bitmap_offset + expr_offset;
 
952
          if (!bitmap_is_set(&ctx->expr_deps, offs))
 
953
            ctx->equality_mods[expr_offset].unbound_args++;
 
954
          bitmap_set_bit(&ctx->expr_deps, offs);
 
955
          return;
 
956
        }
 
957
      }
 
958
      /* 
 
959
        We got here if didn't find this field. It's not a part of 
 
960
        a unique key, and/or there is no field=expr element for it.
 
961
        Bump the dependency anyway, this will signal that this dependency
 
962
        cannot be satisfied.
 
963
      */
 
964
      ctx->equality_mods[expr_offset].unbound_args++;
 
965
    }
 
966
    else
 
967
      visited_other_tables= TRUE;
 
968
  }
 
969
 
 
970
  Dep_analysis_context *ctx;
 
971
  /* Offset of the expression we're processing in the dependency bitmap */
 
972
  uint expr_offset;
 
973
 
 
974
  bool visited_other_tables;
 
975
};
 
976
 
 
977
 
 
978
 
 
979
 
 
980
/*
 
981
  Setup inbound dependency relationships for tbl.col=expr equalities
 
982
 
 
983
  SYNOPSIS
 
984
    setup_equality_modules_deps()
 
985
      bound_deps_list  Put here modules that were found not to depend on 
 
986
                       any non-bound columns.
 
987
 
 
988
  DESCRIPTION
 
989
    Setup inbound dependency relationships for tbl.col=expr equalities:
 
990
      - allocate a bitmap where we store such dependencies
 
991
      - for each "tbl.col=expr" equality, analyze the expr part and find out
 
992
        which fields it refers to and set appropriate dependencies.
 
993
    
 
994
  RETURN
 
995
    FALSE  OK
 
996
    TRUE   Out of memory
 
997
*/
 
998
 
 
999
bool Dep_analysis_context::setup_equality_modules_deps(List<Dep_module> 
 
1000
                                                       *bound_modules)
 
1001
{
 
1002
  DBUG_ENTER("setup_equality_modules_deps");
 
1003
 
 
1004
  /*
 
1005
    Count Dep_value_field objects and assign each of them a unique 
 
1006
    bitmap_offset value.
 
1007
  */
 
1008
  uint offset= 0;
 
1009
  for (Dep_value_table **tbl_dep= table_deps; 
 
1010
       tbl_dep < table_deps + MAX_TABLES;
 
1011
       tbl_dep++)
 
1012
  {
 
1013
    if (*tbl_dep)
 
1014
    {
 
1015
      for (Dep_value_field *field_dep= (*tbl_dep)->fields;
 
1016
           field_dep;
 
1017
           field_dep= field_dep->next_table_field)
 
1018
      {
 
1019
        field_dep->bitmap_offset= offset;
 
1020
        offset += n_equality_mods;
 
1021
      }
 
1022
    }
 
1023
  }
 
1024
 
 
1025
  void *buf;
 
1026
  if (!(buf= current_thd->alloc(bitmap_buffer_size(offset))) ||
 
1027
      bitmap_init(&expr_deps, (my_bitmap_map*)buf, offset, FALSE))
 
1028
  {
 
1029
    DBUG_RETURN(TRUE); /* purecov: inspected */
 
1030
  }
 
1031
  bitmap_clear_all(&expr_deps);
 
1032
 
 
1033
  /* 
 
1034
    Analyze all "field=expr" dependencies, and have expr_deps encode
 
1035
    dependencies of expressions from fields.
 
1036
 
 
1037
    Also collect a linked list of equalities that are bound.
 
1038
  */
 
1039
  Field_dependency_recorder deps_recorder(this);
 
1040
  for (Dep_module_expr *eq_mod= equality_mods; 
 
1041
       eq_mod < equality_mods + n_equality_mods;
 
1042
       eq_mod++)
 
1043
  {
 
1044
    deps_recorder.expr_offset= eq_mod - equality_mods;
 
1045
    deps_recorder.visited_other_tables= FALSE;
 
1046
    eq_mod->unbound_args= 0;
 
1047
    
 
1048
    if (eq_mod->field)
 
1049
    {
 
1050
      /* Regular tbl.col=expr(tblX1.col1, tblY1.col2, ...) */
 
1051
      eq_mod->expr->walk(&Item::enumerate_field_refs_processor, FALSE, 
 
1052
                               (uchar*)&deps_recorder);
 
1053
    }
 
1054
    else 
 
1055
    {
 
1056
      /* It's a multi-equality */
 
1057
      eq_mod->unbound_args= !test(eq_mod->expr);
 
1058
      List_iterator<Dep_value_field> it(*eq_mod->mult_equal_fields);
 
1059
      Dep_value_field* field_val;
 
1060
      while ((field_val= it++))
 
1061
      {
 
1062
        uint offs= field_val->bitmap_offset + eq_mod - equality_mods;
 
1063
        bitmap_set_bit(&expr_deps, offs);
 
1064
      }
 
1065
    }
 
1066
 
 
1067
    if (!eq_mod->unbound_args)
 
1068
      bound_modules->push_back(eq_mod);
 
1069
  }
 
1070
 
 
1071
  DBUG_RETURN(FALSE);
 
1072
}
 
1073
 
 
1074
 
 
1075
/*
 
1076
  Ordering that we're using whenever we need to maintain a no-duplicates list
 
1077
  of field value objects.
 
1078
*/
 
1079
 
 
1080
static 
 
1081
int compare_field_values(Dep_value_field *a, Dep_value_field *b, void *unused)
 
1082
{
 
1083
  uint a_ratio= a->field->table->tablenr*MAX_FIELDS +
 
1084
                a->field->field_index;
 
1085
 
 
1086
  uint b_ratio= b->field->table->tablenr*MAX_FIELDS +
 
1087
                b->field->field_index;
 
1088
  return (a_ratio < b_ratio)? -1 : ((a_ratio == b_ratio)? 0 : 1);
 
1089
}
 
1090
 
 
1091
 
 
1092
/*
 
1093
  Produce Dep_module_expr elements for given condition.
 
1094
 
 
1095
  SYNOPSIS
 
1096
    build_eq_mods_for_cond()
 
1097
      ctx              Table elimination context
 
1098
      eq_mod    INOUT  Put produced equality conditions here
 
1099
      and_level INOUT  AND-level (like in add_key_fields)
 
1100
      cond             Condition to process
 
1101
 
 
1102
  DESCRIPTION
 
1103
    Analyze the given condition and produce an array of Dep_module_expr 
 
1104
    dependencies from it. The idea of analysis is as follows:
 
1105
    There are useful equalities that have form 
 
1106
        
 
1107
        eliminable_tbl.field = expr      (denote as useful_equality)
 
1108
 
 
1109
    The condition is composed of useful equalities and other conditions that
 
1110
    are combined together with AND and OR operators. We process the condition
 
1111
    in recursive fashion according to these basic rules:
 
1112
 
 
1113
      useful_equality1 AND useful_equality2 -> make array of two 
 
1114
                                               Dep_module_expr objects
 
1115
 
 
1116
      useful_equality AND other_cond -> discard other_cond
 
1117
      
 
1118
      useful_equality OR other_cond -> discard everything
 
1119
      
 
1120
      useful_equality1 OR useful_equality2 -> check if both sides of OR are the
 
1121
                                              same equality. If yes, that's the
 
1122
                                              result, otherwise discard 
 
1123
                                              everything.
 
1124
 
 
1125
    The rules are used to map the condition into an array Dep_module_expr
 
1126
    elements. The array will specify functional dependencies that logically 
 
1127
    follow from the condition.
 
1128
 
 
1129
  SEE ALSO
 
1130
    This function is modeled after add_key_fields()
 
1131
*/
 
1132
 
 
1133
static 
 
1134
void build_eq_mods_for_cond(Dep_analysis_context *ctx, 
 
1135
                            Dep_module_expr **eq_mod,
 
1136
                            uint *and_level, Item *cond)
 
1137
{
 
1138
  if (cond->type() == Item_func::COND_ITEM)
 
1139
  {
 
1140
    List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
 
1141
    uint orig_offset= *eq_mod - ctx->equality_mods;
 
1142
    
 
1143
    /* AND/OR */
 
1144
    if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
 
1145
    {
 
1146
      Item *item;
 
1147
      while ((item=li++))
 
1148
        build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
 
1149
 
 
1150
      for (Dep_module_expr *mod_exp= ctx->equality_mods + orig_offset;
 
1151
           mod_exp != *eq_mod ; mod_exp++)
 
1152
      {
 
1153
        mod_exp->level= *and_level;
 
1154
      }
 
1155
    }
 
1156
    else
 
1157
    {
 
1158
      Item *item;
 
1159
      (*and_level)++;
 
1160
      build_eq_mods_for_cond(ctx, eq_mod, and_level, li++);
 
1161
      while ((item=li++))
 
1162
      {
 
1163
        Dep_module_expr *start_key_fields= *eq_mod;
 
1164
        (*and_level)++;
 
1165
        build_eq_mods_for_cond(ctx, eq_mod, and_level, item);
 
1166
        *eq_mod= merge_eq_mods(ctx->equality_mods + orig_offset, 
 
1167
                               start_key_fields, *eq_mod,
 
1168
                               ++(*and_level));
 
1169
      }
 
1170
    }
 
1171
    return;
 
1172
  }
 
1173
 
 
1174
  if (cond->type() != Item::FUNC_ITEM)
 
1175
    return;
 
1176
 
 
1177
  Item_func *cond_func= (Item_func*) cond;
 
1178
  Item **args= cond_func->arguments();
 
1179
 
 
1180
  switch (cond_func->functype()) {
 
1181
  case Item_func::BETWEEN:
 
1182
  {
 
1183
    Item *fld;
 
1184
    if (!((Item_func_between*)cond)->negated &&
 
1185
        (fld= args[0]->real_item())->type() == Item::FIELD_ITEM &&
 
1186
        args[1]->eq(args[2], ((Item_field*)fld)->field->binary()))
 
1187
    {
 
1188
      check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
 
1189
      check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
 
1190
    }
 
1191
    break;
 
1192
  }
 
1193
  case Item_func::EQ_FUNC:
 
1194
  case Item_func::EQUAL_FUNC:
 
1195
  {
 
1196
    check_equality(ctx, eq_mod, *and_level, cond_func, args[0], args[1]);
 
1197
    check_equality(ctx, eq_mod, *and_level, cond_func, args[1], args[0]);
 
1198
    break;
 
1199
  }
 
1200
  case Item_func::ISNULL_FUNC:
 
1201
  {
 
1202
    Item *tmp=new Item_null;
 
1203
    if (tmp)
 
1204
      check_equality(ctx, eq_mod, *and_level, cond_func, args[0], tmp);
 
1205
    break;
 
1206
  }
 
1207
  case Item_func::MULT_EQUAL_FUNC:
 
1208
  {
 
1209
    /*
 
1210
      The condition is a 
 
1211
 
 
1212
        tbl1.field1 = tbl2.field2 = tbl3.field3 [= const_expr]
 
1213
 
 
1214
      multiple-equality. Do two things:
 
1215
       - Collect List<Dep_value_field> of tblX.colY where tblX is one of the
 
1216
         tables we're trying to eliminate.
 
1217
       - rembember if there was a bound value, either const_expr or tblY.colZ
 
1218
         swher tblY is not a table that we're trying to eliminate.
 
1219
      Store all collected information in a Dep_module_expr object.
 
1220
    */
 
1221
    Item_equal *item_equal= (Item_equal*)cond;
 
1222
    List<Dep_value_field> *fvl;
 
1223
    if (!(fvl= new List<Dep_value_field>))
 
1224
      break; /* purecov: inspected */
 
1225
 
 
1226
    Item_equal_fields_iterator it(*item_equal);
 
1227
    Item *item;
 
1228
    Item *bound_item= item_equal->get_const();
 
1229
    while ((item= it++))
 
1230
    {
 
1231
      Field *equal_field= it.get_curr_field();
 
1232
      if ((item->used_tables() & ctx->usable_tables))
 
1233
      {
 
1234
        Dep_value_field *field_val;
 
1235
        if ((field_val= ctx->get_field_value(equal_field)))
 
1236
          fvl->push_back(field_val);
 
1237
      }
 
1238
      else
 
1239
      {
 
1240
        if (!bound_item)
 
1241
          bound_item= item;
 
1242
      }
 
1243
    }
 
1244
    /* 
 
1245
      Multiple equality is only useful if it includes at least one field from
 
1246
      the table that we could potentially eliminate:
 
1247
    */
 
1248
    if (fvl->elements)
 
1249
    {
 
1250
      
 
1251
      bubble_sort<Dep_value_field>(fvl, compare_field_values, NULL);
 
1252
      add_module_expr(ctx, eq_mod, *and_level, NULL, bound_item, fvl);
 
1253
    }
 
1254
    break;
 
1255
  }
 
1256
  default:
 
1257
    break;
 
1258
  }
 
1259
}
 
1260
 
 
1261
 
 
1262
/*
 
1263
  Perform an OR operation on two (adjacent) Dep_module_expr arrays.
 
1264
 
 
1265
  SYNOPSIS
 
1266
     merge_eq_mods()
 
1267
       start        Start of left OR-part
 
1268
       new_fields   Start of right OR-part
 
1269
       end          End of right OR-part
 
1270
       and_level    AND-level (like in add_key_fields)
 
1271
 
 
1272
  DESCRIPTION
 
1273
  This function is invoked for two adjacent arrays of Dep_module_expr elements:
 
1274
 
 
1275
                      $LEFT_PART             $RIGHT_PART
 
1276
             +-----------------------+-----------------------+
 
1277
            start                new_fields                 end
 
1278
         
 
1279
  The goal is to produce an array which would correspond to the combined 
 
1280
  
 
1281
    $LEFT_PART OR $RIGHT_PART
 
1282
  
 
1283
  condition. This is achieved as follows: First, we apply distrubutive law:
 
1284
  
 
1285
    (fdep_A_1 AND fdep_A_2 AND ...)  OR  (fdep_B_1 AND fdep_B_2 AND ...) =
 
1286
 
 
1287
     = AND_ij (fdep_A_[i] OR fdep_B_[j])
 
1288
  
 
1289
  Then we walk over the obtained "fdep_A_[i] OR fdep_B_[j]" pairs, and 
 
1290
   - Discard those that that have left and right part referring to different
 
1291
     columns. We can't infer anything useful from "col1=expr1 OR col2=expr2".
 
1292
   - When left and right parts refer to the same column,  we check if they are 
 
1293
     essentially the same. 
 
1294
     = If they are the same, we keep one copy 
 
1295
       "t.col=expr OR t.col=expr"  -> "t.col=expr 
 
1296
     = if they are different , then we discard both
 
1297
      "t.col=expr1 OR t.col=expr2" -> (nothing useful)
 
1298
 
 
1299
  (no per-table or for-index FUNC_DEPS exist yet at this phase).
 
1300
 
 
1301
  See also merge_key_fields().
 
1302
 
 
1303
  RETURN 
 
1304
    End of the result array
 
1305
*/
 
1306
 
 
1307
static 
 
1308
Dep_module_expr *merge_eq_mods(Dep_module_expr *start, 
 
1309
                               Dep_module_expr *new_fields,
 
1310
                               Dep_module_expr *end, uint and_level)
 
1311
{
 
1312
  if (start == new_fields)
 
1313
    return start;  /*  (nothing) OR (...) -> (nothing) */
 
1314
  if (new_fields == end)
 
1315
    return start;  /*  (...) OR (nothing) -> (nothing) */
 
1316
 
 
1317
  Dep_module_expr *first_free= new_fields;
 
1318
 
 
1319
  for (; new_fields != end ; new_fields++)
 
1320
  {
 
1321
    for (Dep_module_expr *old=start ; old != first_free ; old++)
 
1322
    {
 
1323
      if (old->field == new_fields->field)
 
1324
      {
 
1325
        if (!old->field)
 
1326
        {
 
1327
          /*
 
1328
            OR-ing two multiple equalities. We must compute an intersection of
 
1329
            used fields, and check the constants according to these rules:
 
1330
 
 
1331
              a=b=c=d  OR a=c=e=f   ->  a=c  (compute intersection)
 
1332
              a=const1 OR a=b       ->  (nothing)
 
1333
              a=const1 OR a=const1  ->  a=const1 
 
1334
              a=const1 OR a=const2  ->  (nothing)
 
1335
            
 
1336
            If we're performing an OR operation over multiple equalities, e.g.
 
1337
 
 
1338
              (a=b=c AND p=q) OR (a=b AND v=z)
 
1339
            
 
1340
            then we'll need to try combining each equality with each. ANDed
 
1341
            equalities are guaranteed to be disjoint, so we'll only get one
 
1342
            hit.
 
1343
          */
 
1344
          Field *eq_field= old->mult_equal_fields->head()->field;
 
1345
          if (old->expr && new_fields->expr &&
 
1346
              old->expr->eq_by_collation(new_fields->expr, eq_field->binary(),
 
1347
                                         eq_field->charset()))
 
1348
          {
 
1349
            /* Ok, keep */
 
1350
          }
 
1351
          else
 
1352
          {
 
1353
            /* no single constant/bound item. */
 
1354
            old->expr= NULL;
 
1355
          }
 
1356
           
 
1357
          List <Dep_value_field> *fv;
 
1358
          if (!(fv= new List<Dep_value_field>))
 
1359
            break; /* purecov: inspected */
 
1360
 
 
1361
          List_iterator<Dep_value_field> it1(*old->mult_equal_fields);
 
1362
          List_iterator<Dep_value_field> it2(*new_fields->mult_equal_fields);
 
1363
          Dep_value_field *lfield= it1++;
 
1364
          Dep_value_field *rfield= it2++;
 
1365
          /* Intersect two ordered lists */
 
1366
          while (lfield && rfield)
 
1367
          {
 
1368
            if (lfield == rfield)
 
1369
            {
 
1370
              fv->push_back(lfield);
 
1371
              lfield=it1++;
 
1372
              rfield=it2++;
 
1373
            }
 
1374
            else
 
1375
            {
 
1376
              if (compare_field_values(lfield, rfield, NULL) < 0)
 
1377
                lfield= it1++;
 
1378
              else
 
1379
                rfield= it2++;
 
1380
            }
 
1381
          }
 
1382
 
 
1383
          if (fv->elements + test(old->expr) > 1)
 
1384
          {
 
1385
            old->mult_equal_fields= fv;
 
1386
            old->level= and_level;
 
1387
          }
 
1388
        }
 
1389
        else if (!new_fields->expr->const_item())
 
1390
        {
 
1391
          /*
 
1392
            If the value matches, we can use the key reference.
 
1393
            If not, we keep it until we have examined all new values
 
1394
          */
 
1395
          if (old->expr->eq(new_fields->expr, 
 
1396
                            old->field->field->binary()))
 
1397
          {
 
1398
            old->level= and_level;
 
1399
          }
 
1400
        }
 
1401
        else if (old->expr->eq_by_collation(new_fields->expr,
 
1402
                                            old->field->field->binary(),
 
1403
                                            old->field->field->charset()))
 
1404
        {
 
1405
          old->level= and_level;
 
1406
        }
 
1407
        else
 
1408
        {
 
1409
          /* The expressions are different. */
 
1410
          if (old == --first_free)                // If last item
 
1411
            break;
 
1412
          *old= *first_free;                        // Remove old value
 
1413
          old--;                                // Retry this value
 
1414
        }
 
1415
      }
 
1416
    }
 
1417
  }
 
1418
 
 
1419
  /* 
 
1420
    Ok, the results are within the [start, first_free) range, and the useful
 
1421
    elements have level==and_level. Now, remove all unusable elements:
 
1422
  */
 
1423
  for (Dep_module_expr *old=start ; old != first_free ;)
 
1424
  {
 
1425
    if (old->level != and_level)
 
1426
    {                                                // Not used in all levels
 
1427
      if (old == --first_free)
 
1428
        break;
 
1429
      *old= *first_free;                        // Remove old value
 
1430
      continue;
 
1431
    }
 
1432
    old++;
 
1433
  }
 
1434
  return first_free;
 
1435
}
 
1436
 
 
1437
 
 
1438
/*
 
1439
  Add an Dep_module_expr element for left=right condition
 
1440
 
 
1441
  SYNOPSIS
 
1442
    check_equality()
 
1443
      fda               Table elimination context
 
1444
      eq_mod     INOUT  Store created Dep_module_expr here and increment ptr if
 
1445
                        you do so
 
1446
      and_level         AND-level (like in add_key_fields)
 
1447
      cond              Condition we've inferred the left=right equality from.
 
1448
      left              Left expression
 
1449
      right             Right expression
 
1450
      usable_tables     Create Dep_module_expr only if Left_expression's table 
 
1451
                        belongs to this set.
 
1452
 
 
1453
  DESCRIPTION 
 
1454
    Check if the passed left=right equality is such that 
 
1455
     - 'left' is an Item_field referring to a field in a table we're checking
 
1456
       to be functionally depdendent,
 
1457
     - the equality allows to conclude that 'left' expression is functionally 
 
1458
       dependent on the 'right',
 
1459
    and if so, create an Dep_module_expr object.
 
1460
*/
 
1461
 
 
1462
static 
 
1463
void check_equality(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
 
1464
                    uint and_level, Item_func *cond, Item *left, Item *right)
 
1465
{
 
1466
  if ((left->used_tables() & ctx->usable_tables) &&
 
1467
      !(right->used_tables() & RAND_TABLE_BIT) &&
 
1468
      left->real_item()->type() == Item::FIELD_ITEM)
 
1469
  {
 
1470
    Field *field= ((Item_field*)left->real_item())->field;
 
1471
    if (field->result_type() == STRING_RESULT)
 
1472
    {
 
1473
      if (right->result_type() != STRING_RESULT)
 
1474
      {
 
1475
        if (field->cmp_type() != right->result_type())
 
1476
          return;
 
1477
      }
 
1478
      else
 
1479
      {
 
1480
        /*
 
1481
          We can't assume there's a functional dependency if the effective
 
1482
          collation of the operation differ from the field collation.
 
1483
        */
 
1484
        if (field->cmp_type() == STRING_RESULT &&
 
1485
            ((Field_str*)field)->charset() != cond->compare_collation())
 
1486
          return;
 
1487
      }
 
1488
    }
 
1489
    Dep_value_field *field_val;
 
1490
    if ((field_val= ctx->get_field_value(field)))
 
1491
      add_module_expr(ctx, eq_mod, and_level, field_val, right, NULL);
 
1492
  }
 
1493
}
 
1494
 
 
1495
 
 
1496
/* 
 
1497
  Add a Dep_module_expr object with the specified parameters. 
 
1498
  
 
1499
  DESCRIPTION
 
1500
    Add a Dep_module_expr object with the specified parameters. Re-allocate
 
1501
    the ctx->equality_mods array if it has no space left.
 
1502
*/
 
1503
 
 
1504
static 
 
1505
void add_module_expr(Dep_analysis_context *ctx, Dep_module_expr **eq_mod,
 
1506
                     uint and_level, Dep_value_field *field_val, 
 
1507
                     Item *right, List<Dep_value_field>* mult_equal_fields)
 
1508
{
 
1509
  if (*eq_mod == ctx->equality_mods + ctx->n_equality_mods_alloced)
 
1510
  {
 
1511
    /* 
 
1512
      We've filled the entire equality_mods array. Replace it with a bigger
 
1513
      one. We do it somewhat inefficiently but it doesn't matter.
 
1514
    */
 
1515
    /* purecov: begin inspected */
 
1516
    Dep_module_expr *new_arr;
 
1517
    if (!(new_arr= new Dep_module_expr[ctx->n_equality_mods_alloced *2]))
 
1518
      return;
 
1519
    ctx->n_equality_mods_alloced *= 2;
 
1520
    for (int i= 0; i < *eq_mod - ctx->equality_mods; i++)
 
1521
      new_arr[i]= ctx->equality_mods[i];
 
1522
 
 
1523
    ctx->equality_mods= new_arr;
 
1524
    *eq_mod= new_arr + (*eq_mod - ctx->equality_mods);
 
1525
    /* purecov: end */
 
1526
  }
 
1527
 
 
1528
  (*eq_mod)->field= field_val;
 
1529
  (*eq_mod)->expr= right;
 
1530
  (*eq_mod)->level= and_level;
 
1531
  (*eq_mod)->mult_equal_fields= mult_equal_fields;
 
1532
  (*eq_mod)++;
 
1533
}
 
1534
 
 
1535
 
 
1536
/*
 
1537
  Create a Dep_value_table object for the given table
 
1538
 
 
1539
  SYNOPSIS
 
1540
    Dep_analysis_context::create_table_value()
 
1541
      table  Table to create object for
 
1542
 
 
1543
  DESCRIPTION
 
1544
    Create a Dep_value_table object for the given table. Also create
 
1545
    Dep_module_key objects for all unique keys in the table.
 
1546
 
 
1547
  RETURN
 
1548
    Created table value object
 
1549
    NULL if out of memory
 
1550
*/
 
1551
 
 
1552
Dep_value_table *Dep_analysis_context::create_table_value(TABLE *table)
 
1553
{
 
1554
  Dep_value_table *tbl_dep;
 
1555
  if (!(tbl_dep= new Dep_value_table(table)))
 
1556
    return NULL; /* purecov: inspected */
 
1557
 
 
1558
  Dep_module_key **key_list= &(tbl_dep->keys);
 
1559
  /* Add dependencies for unique keys */
 
1560
  for (uint i=0; i < table->s->keys; i++)
 
1561
  {
 
1562
    KEY *key= table->key_info + i; 
 
1563
    if (key->flags & HA_NOSAME)
 
1564
    {
 
1565
      Dep_module_key *key_dep;
 
1566
      if (!(key_dep= new Dep_module_key(tbl_dep, i, key->key_parts)))
 
1567
        return NULL;
 
1568
      *key_list= key_dep;
 
1569
      key_list= &(key_dep->next_table_key);
 
1570
    }
 
1571
  }
 
1572
  return table_deps[table->tablenr]= tbl_dep;
 
1573
}
 
1574
 
 
1575
 
 
1576
/* 
 
1577
  Get a Dep_value_field object for the given field, creating it if necessary
 
1578
 
 
1579
  SYNOPSIS
 
1580
   Dep_analysis_context::get_field_value()
 
1581
      field  Field to create object for
 
1582
        
 
1583
  DESCRIPTION
 
1584
    Get a Dep_value_field object for the given field. First, we search for it 
 
1585
    in the list of Dep_value_field objects we have already created. If we don't 
 
1586
    find it, we create a new Dep_value_field and put it into the list of field
 
1587
    objects we have for the table.
 
1588
 
 
1589
  RETURN
 
1590
    Created field value object
 
1591
    NULL if out of memory
 
1592
*/
 
1593
 
 
1594
Dep_value_field *Dep_analysis_context::get_field_value(Field *field)
 
1595
{
 
1596
  TABLE *table= field->table;
 
1597
  Dep_value_table *tbl_dep= table_deps[table->tablenr];
 
1598
 
 
1599
  /* Try finding the field in field list */
 
1600
  Dep_value_field **pfield= &(tbl_dep->fields);
 
1601
  while (*pfield && (*pfield)->field->field_index < field->field_index)
 
1602
  {
 
1603
    pfield= &((*pfield)->next_table_field);
 
1604
  }
 
1605
  if (*pfield && (*pfield)->field->field_index == field->field_index)
 
1606
    return *pfield;
 
1607
  
 
1608
  /* Create the field and insert it in the list */
 
1609
  Dep_value_field *new_field= new Dep_value_field(tbl_dep, field);
 
1610
  new_field->next_table_field= *pfield;
 
1611
  *pfield= new_field;
 
1612
 
 
1613
  return new_field;
 
1614
}
 
1615
 
 
1616
 
 
1617
/* 
 
1618
  Iteration over unbound modules that are our dependencies.
 
1619
  for those we have:
 
1620
    - dependendencies of our fields
 
1621
    - outer join we're in 
 
1622
*/
 
1623
char *Dep_value_table::init_unbound_modules_iter(char *buf)
 
1624
{
 
1625
  Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
 
1626
  iter->field_dep= fields;
 
1627
  if (fields)
 
1628
  {
 
1629
    fields->init_unbound_modules_iter(iter->buf);
 
1630
    fields->make_unbound_modules_iter_skip_keys(iter->buf);
 
1631
  }
 
1632
  iter->returned_goal= FALSE;
 
1633
  return (char*)iter;
 
1634
}
 
1635
 
 
1636
 
 
1637
Dep_module* 
 
1638
Dep_value_table::get_next_unbound_module(Dep_analysis_context *dac,
 
1639
                                         char *iter)
 
1640
{
 
1641
  Module_iter *di= (Module_iter*)iter;
 
1642
  while (di->field_dep)
 
1643
  {
 
1644
    Dep_module *res;
 
1645
    if ((res= di->field_dep->get_next_unbound_module(dac, di->buf)))
 
1646
      return res;
 
1647
    if ((di->field_dep= di->field_dep->next_table_field))
 
1648
    {
 
1649
      char *field_iter= ((Module_iter*)iter)->buf;
 
1650
      di->field_dep->init_unbound_modules_iter(field_iter);
 
1651
      di->field_dep->make_unbound_modules_iter_skip_keys(field_iter);
 
1652
    }
 
1653
  }
 
1654
  
 
1655
  if (!di->returned_goal)
 
1656
  {
 
1657
    di->returned_goal= TRUE;
 
1658
    return dac->outer_join_dep;
 
1659
  }
 
1660
  return NULL;
 
1661
}
 
1662
 
 
1663
 
 
1664
char *Dep_module_expr::init_unbound_values_iter(char *buf)
 
1665
{
 
1666
  Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
 
1667
  iter->field= field;
 
1668
  if (!field)
 
1669
  {
 
1670
    new (&iter->it) List_iterator<Dep_value_field>(*mult_equal_fields);
 
1671
  }
 
1672
  return (char*)iter;
 
1673
}
 
1674
 
 
1675
 
 
1676
Dep_value* Dep_module_expr::get_next_unbound_value(Dep_analysis_context *dac,
 
1677
                                                   char *buf)
 
1678
{
 
1679
  Dep_value *res;
 
1680
  if (field)
 
1681
  {
 
1682
    res= ((Value_iter*)buf)->field;
 
1683
    ((Value_iter*)buf)->field= NULL;
 
1684
    return (!res || res->is_bound())? NULL : res;
 
1685
  }
 
1686
  else
 
1687
  {
 
1688
    while ((res= ((Value_iter*)buf)->it++))
 
1689
    {
 
1690
      if (!res->is_bound())
 
1691
        return res;
 
1692
    }
 
1693
    return NULL;
 
1694
  }
 
1695
}
 
1696
 
 
1697
 
 
1698
char *Dep_module_key::init_unbound_values_iter(char *buf)
 
1699
{
 
1700
  Value_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Value_iter);
 
1701
  iter->table= table;
 
1702
  return (char*)iter;
 
1703
}
 
1704
 
 
1705
 
 
1706
Dep_value* Dep_module_key::get_next_unbound_value(Dep_analysis_context *dac,
 
1707
                                                  Dep_module::Iterator iter)
 
1708
{
 
1709
  Dep_value* res= ((Value_iter*)iter)->table;
 
1710
  ((Value_iter*)iter)->table= NULL;
 
1711
  return res;
 
1712
}
 
1713
 
 
1714
 
 
1715
Dep_value::Iterator Dep_value_field::init_unbound_modules_iter(char *buf)
 
1716
{
 
1717
  Module_iter *iter= ALIGN_PTR(my_ptrdiff_t(buf), Module_iter);
 
1718
  iter->key_dep= table->keys;
 
1719
  iter->equality_no= 0;
 
1720
  return (char*)iter;
 
1721
}
 
1722
 
 
1723
 
 
1724
void 
 
1725
Dep_value_field::make_unbound_modules_iter_skip_keys(Dep_value::Iterator iter)
 
1726
{
 
1727
  ((Module_iter*)iter)->key_dep= NULL;
 
1728
}
 
1729
 
 
1730
 
 
1731
Dep_module* Dep_value_field::get_next_unbound_module(Dep_analysis_context *dac,
 
1732
                                                     Dep_value::Iterator iter)
 
1733
{
 
1734
  Module_iter *di= (Module_iter*)iter;
 
1735
  Dep_module_key *key_dep= di->key_dep;
 
1736
  
 
1737
  /* 
 
1738
    First, enumerate all unique keys that are 
 
1739
    - not yet applicable
 
1740
    - have this field as a part of them
 
1741
  */
 
1742
  while (key_dep && (key_dep->is_applicable() ||
 
1743
         !field->part_of_key.is_set(key_dep->keyno)))
 
1744
  {
 
1745
    key_dep= key_dep->next_table_key;
 
1746
  }
 
1747
 
 
1748
  if (key_dep)
 
1749
  {
 
1750
    di->key_dep= key_dep->next_table_key;
 
1751
    return key_dep;
 
1752
  }
 
1753
  else 
 
1754
    di->key_dep= NULL;
 
1755
  
 
1756
  /*
 
1757
    Then walk through [multi]equalities and find those that
 
1758
     - depend on this field
 
1759
     - and are not bound yet.
 
1760
  */
 
1761
  uint eq_no= di->equality_no;
 
1762
  while (eq_no < dac->n_equality_mods && 
 
1763
         (!bitmap_is_set(&dac->expr_deps, bitmap_offset + eq_no) ||
 
1764
         dac->equality_mods[eq_no].is_applicable()))
 
1765
  {
 
1766
    eq_no++;
 
1767
  }
 
1768
  
 
1769
  if (eq_no < dac->n_equality_mods)
 
1770
  {
 
1771
    di->equality_no= eq_no+1;
 
1772
    return &dac->equality_mods[eq_no];
 
1773
  }
 
1774
  return NULL;
 
1775
}
 
1776
 
 
1777
 
 
1778
/* 
 
1779
  Mark one table or the whole join nest as eliminated.
 
1780
*/
 
1781
 
 
1782
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl)
 
1783
{
 
1784
  TABLE *table;
 
1785
  /*
 
1786
    NOTE: there are TABLE_LIST object that have
 
1787
    tbl->table!= NULL && tbl->nested_join!=NULL and 
 
1788
    tbl->table == tbl->nested_join->join_list->element(..)->table
 
1789
  */
 
1790
  if (tbl->nested_join)
 
1791
  {
 
1792
    TABLE_LIST *child;
 
1793
    List_iterator<TABLE_LIST> it(tbl->nested_join->join_list);
 
1794
    while ((child= it++))
 
1795
      mark_as_eliminated(join, child);
 
1796
  }
 
1797
  else if ((table= tbl->table))
 
1798
  {
 
1799
    JOIN_TAB *tab= tbl->table->reginfo.join_tab;
 
1800
    if (!(join->const_table_map & tab->table->map))
 
1801
    {
 
1802
      DBUG_PRINT("info", ("Eliminated table %s", table->alias.c_ptr()));
 
1803
      tab->type= JT_CONST;
 
1804
      join->eliminated_tables |= table->map;
 
1805
      join->const_table_map|= table->map;
 
1806
      set_position(join, join->const_tables++, tab, (KEYUSE*)0);
 
1807
    }
 
1808
  }
 
1809
 
 
1810
  if (tbl->on_expr)
 
1811
    tbl->on_expr->walk(&Item::mark_as_eliminated_processor, FALSE, NULL);
 
1812
}
 
1813
 
 
1814
 
 
1815
#ifndef DBUG_OFF
 
1816
/* purecov: begin inspected */
 
1817
void Dep_analysis_context::dbug_print_deps()
 
1818
{
 
1819
  DBUG_ENTER("dbug_print_deps");
 
1820
  DBUG_LOCK_FILE;
 
1821
  
 
1822
  fprintf(DBUG_FILE,"deps {\n");
 
1823
  
 
1824
  /* Start with printing equalities */
 
1825
  for (Dep_module_expr *eq_mod= equality_mods; 
 
1826
       eq_mod != equality_mods + n_equality_mods; eq_mod++)
 
1827
  {
 
1828
    char buf[128];
 
1829
    String str(buf, sizeof(buf), &my_charset_bin);
 
1830
    str.length(0);
 
1831
    eq_mod->expr->print(&str, QT_ORDINARY);
 
1832
    if (eq_mod->field)
 
1833
    {
 
1834
      fprintf(DBUG_FILE, "  equality%ld: %s -> %s.%s\n", 
 
1835
              (long)(eq_mod - equality_mods),
 
1836
              str.c_ptr(),
 
1837
              eq_mod->field->table->table->alias.c_ptr(),
 
1838
              eq_mod->field->field->field_name);
 
1839
    }
 
1840
    else
 
1841
    {
 
1842
      fprintf(DBUG_FILE, "  equality%ld: multi-equality", 
 
1843
              (long)(eq_mod - equality_mods));
 
1844
    }
 
1845
  }
 
1846
  fprintf(DBUG_FILE,"\n");
 
1847
 
 
1848
  /* Then tables and their fields */
 
1849
  for (uint i=0; i < MAX_TABLES; i++)
 
1850
  {
 
1851
    Dep_value_table *table_dep;
 
1852
    if ((table_dep= table_deps[i]))
 
1853
    {
 
1854
      /* Print table */
 
1855
      fprintf(DBUG_FILE, "  table %s\n", table_dep->table->alias.c_ptr());
 
1856
      /* Print fields */
 
1857
      for (Dep_value_field *field_dep= table_dep->fields; field_dep; 
 
1858
           field_dep= field_dep->next_table_field)
 
1859
      {
 
1860
        fprintf(DBUG_FILE, "    field %s.%s ->",
 
1861
                table_dep->table->alias.c_ptr(),
 
1862
                field_dep->field->field_name);
 
1863
        uint ofs= field_dep->bitmap_offset;
 
1864
        for (uint bit= ofs; bit < ofs + n_equality_mods; bit++)
 
1865
        {
 
1866
          if (bitmap_is_set(&expr_deps, bit))
 
1867
            fprintf(DBUG_FILE, " equality%d ", bit - ofs);
 
1868
        }
 
1869
        fprintf(DBUG_FILE, "\n");
 
1870
      }
 
1871
    }
 
1872
  }
 
1873
  fprintf(DBUG_FILE,"\n}\n");
 
1874
  DBUG_UNLOCK_FILE;
 
1875
  DBUG_VOID_RETURN;
 
1876
}
 
1877
/* purecov: end */
 
1878
 
 
1879
#endif 
 
1880
/**
 
1881
  @} (end of group Table_Elimination)
 
1882
*/
 
1883