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