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