At file:///home/psergey/dev/maria-5.1-table-elim-r5/ ------------------------------------------------------------ revno: 2733 revision-id: psergey@askmonty.org-20090813191053-g1xfeieoti4bqgbc parent: psergey@askmonty.org-20090813093613-hy7tdlsgdy83xszq committer: Sergey Petrunya <psergey@askmonty.org> branch nick: maria-5.1-table-elim-r5 timestamp: Thu 2009-08-13 23:10:53 +0400 message: MWL#17: Table elimination - Better comments === modified file 'sql/opt_table_elimination.cc' --- a/sql/opt_table_elimination.cc 2009-08-13 09:36:13 +0000 +++ b/sql/opt_table_elimination.cc 2009-08-13 19:10:53 +0000 @@ -20,19 +20,16 @@ OVERVIEW The module has one entry point - eliminate_tables() function, which one - needs to call (once) sometime after update_ref_and_keys() but before the - join optimization. + needs to call (once) at some point before the join optimization. eliminate_tables() operates over the JOIN structures. Logically, it removes the right sides of outer join nests. Physically, it changes the following members: * Eliminated tables are marked as constant and moved to the front of the join order. + * In addition to this, they are recorded in JOIN::eliminated_tables bitmap. - * All join nests have their NESTED_JOIN::n_tables updated to discount - the eliminated tables - * Items that became disused because they were in the ON expression of an eliminated outer join are notified by means of the Item tree walk which calls Item::mark_as_eliminated_processor for every item @@ -40,26 +37,13 @@ Item_subselect with its Item_subselect::eliminated flag which is used by EXPLAIN code to check if the subquery should be shown in EXPLAIN. - Table elimination is redone on every PS re-execution. (TODO reasons?) + Table elimination is redone on every PS re-execution. */ + /* - A structure that represents a functional dependency of something over - something else. This can be one of: - - 1. A "tbl.field = expr" equality. The field depends on the expression. - - 2. An Item_equal(...) multi-equality. Each participating field depends on - every other participating field. (TODO???) - - 3. A UNIQUE_KEY(field1, field2, fieldN). The key depends on the fields that - it is composed of. - - 4. A table (which is within an outer join nest). Table depends on a unique - key (value of a unique key identifies a table record) - - 5. An outer join nest. It depends on all tables it contains. - + An abstract structure that represents some entity that's being dependent on + some other entity. */ class Func_dep : public Sql_alloc @@ -73,9 +57,14 @@ FD_UNIQUE_KEY, FD_TABLE, FD_OUTER_JOIN - } type; - Func_dep *next; - bool bound; + } type; /* Type of the object */ + + /* + Used to make a linked list of elements that became bound and thus can + make elements that depend on them bound, too. + */ + Func_dep *next; + bool bound; /* TRUE<=> The entity is considered bound */ Func_dep() : next(NULL), bound(FALSE) {} }; @@ -84,10 +73,10 @@ class Table_dep; class Outer_join_dep; + /* - An equality - - Depends on multiple fields (those in its expression), unknown_args is a - counter of unsatisfied dependencies. + A "tbl.column= expr" equality dependency. tbl.column depends on fields + used in expr. */ class Equality_dep : public Func_dep { @@ -95,8 +84,11 @@ Field_dep *field; Item *val; - uint level; /* Used during condition analysis only */ - uint unknown_args; /* Number of yet unknown arguments */ + /* Used during condition analysis only, similar to KEYUSE::level */ + uint level; + + /* Number of fields referenced from *val that are not yet 'bound' */ + uint unknown_args; }; @@ -139,7 +131,7 @@ type= Func_dep::FD_UNIQUE_KEY; } Table_dep *table; /* Table this key is from */ - uint keyno; // TODO do we care about this + uint keyno; uint n_missing_keyparts; Key_dep *next_table_key; }; === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2009-08-13 09:24:02 +0000 +++ b/sql/sql_select.cc 2009-08-13 19:10:53 +0000 @@ -114,7 +114,7 @@ COND *conds, bool top); static bool check_interleaving_with_nj(JOIN_TAB *next); static void restore_prev_nj_state(JOIN_TAB *last); -static void reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list); +static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list); static uint build_bitmap_for_nested_joins(List<TABLE_LIST> *join_list, uint first_unused); @@ -8791,23 +8791,26 @@ tables which will be ignored. */ -static void reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list) +static uint reset_nj_counters(JOIN *join, List<TABLE_LIST> *join_list) { List_iterator<TABLE_LIST> li(*join_list); TABLE_LIST *table; DBUG_ENTER("reset_nj_counters"); + uint n=0; while ((table= li++)) { NESTED_JOIN *nested_join; if ((nested_join= table->nested_join)) { nested_join->counter= 0; - nested_join->n_tables= my_count_bits(nested_join->used_tables & - ~join->eliminated_tables); - reset_nj_counters(join, &nested_join->join_list); + //nested_join->n_tables= my_count_bits(nested_join->used_tables & + // ~join->eliminated_tables); + nested_join->n_tables= reset_nj_counters(join, &nested_join->join_list); } + if (table->table && (table->table->map & ~join->eliminated_tables)) + n++; } - DBUG_VOID_RETURN; + DBUG_RETURN(n); }