maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #00790
Rev 2734: MWL#17: Table elimination in file:///home/psergey/dev/maria-5.1-table-elim-r11/
At file:///home/psergey/dev/maria-5.1-table-elim-r11/
------------------------------------------------------------
revno: 2734
revision-id: psergey@xxxxxxxxxxxx-20090818150151-uef38y50m8m1mgnu
parent: psergey@xxxxxxxxxxxx-20090818130358-akd84j4m2i91lw5a
committer: Sergey Petrunya <psergey@xxxxxxxxxxxx>
branch nick: maria-5.1-table-elim-r11
timestamp: Tue 2009-08-18 18:01:51 +0300
message:
MWL#17: Table elimination
- Code cleanup
=== modified file 'sql/opt_table_elimination.cc'
--- a/sql/opt_table_elimination.cc 2009-08-18 13:03:58 +0000
+++ b/sql/opt_table_elimination.cc 2009-08-18 15:01:51 +0000
@@ -275,7 +275,7 @@
public:
Outer_join_module(//TABLE_LIST *table_list_arg,
uint n_children)
- // table_list(table_list_arg), parent(NULL)
+ // table_list(table_list_arg)
{
type= Module_dep::MODULE_OUTER_JOIN;
unknown_args= n_children;
@@ -285,9 +285,6 @@
is outer join'ed.
*/
// TABLE_LIST *table_list;
-
- /* Parent eliminable outer join, if any */
-// Outer_join_module *parent;
};
@@ -297,7 +294,7 @@
class Table_elimination
{
public:
- Table_elimination(JOIN *join_arg) : join(join_arg), n_outer_joins(0)
+ Table_elimination(JOIN *join_arg) : join(join_arg)
{
bzero(table_deps, sizeof(table_deps));
}
@@ -310,14 +307,20 @@
/* tablenr -> Table_value* mapping. */
Table_value *table_deps[MAX_KEY];
- /* Outer joins that are candidates for elimination */
- List<Outer_join_module> oj_deps;
- uint n_outer_joins;
-
/* Bitmap of how expressions depend on bits */
MY_BITMAP expr_deps;
};
+void eliminate_tables(JOIN *join);
+
+static bool
+eliminate_tables_for_list(Table_elimination *te,
+ List<TABLE_LIST> *join_list,
+ table_map tables_in_list,
+ Item *on_expr,
+ table_map tables_used_elsewhere);
+static bool
+check_func_dependency(Table_elimination *te, table_map tables, Item* cond);
static
bool build_eq_deps_for_cond(Table_elimination *te, Equality_module **fdeps,
@@ -339,9 +342,10 @@
table_map deps_map);
static
bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules);
-void eliminate_tables(JOIN *join);
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
+
+
#ifndef DBUG_OFF
static void dbug_print_deps(Table_elimination *te);
#endif
@@ -383,10 +387,6 @@
if (build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables))
return TRUE;
}
- /*
- TODO: inject here a "if we have {t.col=const AND t.col=smth_else}, then
- remove the second part" logic.
- */
for (; org_key_fields != *fdeps ; org_key_fields++)
org_key_fields->level= *and_level;
}
@@ -614,7 +614,7 @@
/*
Ok, the results are within the [start, first_free) range, and the useful
- elements have level==and_level. Now, lets remove all unusable elements:
+ elements have level==and_level. Now, remove all unusable elements:
*/
for (Equality_module *old=start ; old != first_free ;)
{
@@ -632,14 +632,31 @@
/*
- Add an Equality_module element for a given predicate, if applicable
+ Add an Equality_module element for left=right condition
+
+ SYNOPSIS
+ add_eq_dep()
+ te Table elimination context
+ eq_mod INOUT Store created Equality_module here and increment ptr if
+ you do so
+ and_level AND-level ()
+ cond Condition we've inferred the left=right equality from.
+ left Left expression
+ right Right expression
+ usable_tables Create Equality_module only if Left_expression's table
+ belongs to this set.
DESCRIPTION
- This function is modeled after add_key_field().
+ Check if the passed equality means that 'left' expr is functionally dependent on
+ the 'right', and if yes, create an Equality_module object for it.
+
+ RETURN
+ FALSE OK
+ TRUE Out of memory
*/
static
-bool add_eq_dep(Table_elimination *te, Equality_module **eq_dep,
+bool add_eq_dep(Table_elimination *te, Equality_module **eq_mod,
uint and_level, Item_func *cond, Item *left, Item *right,
table_map usable_tables)
{
@@ -658,8 +675,8 @@
else
{
/*
- We can't use indexes if the effective collation
- of the operation differ from the field collation.
+ We can't assume there's a functional dependency if the effective
+ collation of the operation differ from the field collation.
*/
if (field->cmp_type() == STRING_RESULT &&
((Field_str*)field)->charset() != cond->compare_collation())
@@ -667,12 +684,12 @@
}
}
- (*eq_dep)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo;
- if (!((*eq_dep)->field= get_field_value(te, field)))
+ (*eq_mod)->type= Module_dep::MODULE_EXPRESSION; //psergey-todo;
+ if (!((*eq_mod)->field= get_field_value(te, field)))
return TRUE;
- (*eq_dep)->expression= right;
- (*eq_dep)->level= and_level;
- (*eq_dep)++;
+ (*eq_mod)->expression= right;
+ (*eq_mod)->level= and_level;
+ (*eq_mod)++;
}
return FALSE;
}
@@ -754,7 +771,6 @@
Outer_join_module *oj_dep;
if (!(oj_dep= new Outer_join_module(/*outer_join, */my_count_bits(deps_map))))
return NULL;
- te->n_outer_joins++;
/*
Collect a bitmap fo tables that we depend on, and also set parent pointer
@@ -786,25 +802,7 @@
if (!(table_dep= get_table_value(te, table)))
return NULL;
}
-
- /*
- Walk from the table up to its embedding outer joins. The goal is to
- find the least embedded outer join nest and set its parent pointer to
- point to the newly created Outer_join_module.
- to set the pointer of its near
- */
- //if (!table_dep->outer_join_dep)
- table_dep->outer_join_dep= oj_dep;
- /*
- else
- {
- Outer_join_module *oj= table_dep->outer_join_dep;
- while (oj->parent)
- oj= oj->parent;
- if (oj != oj_dep)
- oj->parent=oj_dep;
- }
- */
+ table_dep->outer_join_dep= oj_dep;
}
return oj_dep;
}
@@ -815,10 +813,10 @@
that we can figure out which fields the expression depends on.
*/
-class Field_dependency_setter : public Field_enumerator
+class Field_dependency_recorder : public Field_enumerator
{
public:
- Field_dependency_setter(Table_elimination *te_arg): te(te_arg)
+ Field_dependency_recorder(Table_elimination *te_arg): te(te_arg)
{}
void see_field(Field *field)
@@ -856,13 +854,16 @@
/*
Setup equality dependencies
-
+
SYNOPSIS
setup_equality_deps()
te Table elimination context
bound_deps_list OUT Start of linked list of elements that were found to
be bound (caller will use this to see if that
allows to declare further elements bound)
+ DESCRIPTION
+ RETURN
+
*/
static
@@ -907,15 +908,15 @@
Also collect a linked list of equalities that are bound.
*/
Module_dep *bound_dep= NULL;
- Field_dependency_setter deps_setter(te);
+ Field_dependency_recorder deps_recorder(te);
for (Equality_module *eq_dep= te->equality_deps;
eq_dep < te->equality_deps + te->n_equality_deps;
eq_dep++)
{
- deps_setter.expr_offset= eq_dep - te->equality_deps;
+ deps_recorder.expr_offset= eq_dep - te->equality_deps;
eq_dep->unknown_args= 0;
eq_dep->expression->walk(&Item::check_column_usage_processor, FALSE,
- (uchar*)&deps_setter);
+ (uchar*)&deps_recorder);
if (!eq_dep->unknown_args)
{
eq_dep->next= bound_dep;
@@ -935,12 +936,11 @@
SYNOPSIS
eliminate_tables()
join Join to work on
- const_tbl_count INOUT Number of constant tables (this includes
- eliminated tables)
- const_tables INOUT Bitmap of constant tables
DESCRIPTION
- This function is the entry point for table elimination.
+ This is the entry point for table elimination. Grep for MODULE INTERFACE
+ section in this file for calling convention.
+
The idea behind table elimination is that if we have an outer join:
SELECT * FROM t1 LEFT JOIN
@@ -968,12 +968,6 @@
See the OVERVIEW section at the top of this file.
*/
-static uint
-eliminate_tables_for_list(Table_elimination *te,
- List<TABLE_LIST> *join_list,
- Item *on_expr,
- table_map tables_in_list,
- table_map tables_used_elsewhere);
void eliminate_tables(JOIN *join)
{
@@ -1023,101 +1017,54 @@
if (all_tables & ~used_tables)
{
/* There are some tables that we probably could eliminate. Try it. */
+ //psergey-todo: move allocs to somewhere else.
Table_elimination te(join);
uint m= max(thd->lex->current_select->max_equal_elems,1);
uint max_elems= ((thd->lex->current_select->cond_count+1)*2 +
thd->lex->current_select->between_count)*m + 1 + 10;
if (!(te.equality_deps= new Equality_module[max_elems]))
DBUG_VOID_RETURN;
- //Equality_module *eq_deps_end= te.equality_deps;
- //table_map eliminable_tables= 0;
- /*
- if (collect_funcdeps_for_join_list(&te, join->join_list,
- FALSE,
- used_tables,
- &eliminable_tables,
- &eq_deps))
- DBUG_VOID_RETURN;
- */
- eliminate_tables_for_list(&te, join->join_list,
- NULL,
- (table_map(1) << join->tables) - 1,
+
+ eliminate_tables_for_list(&te, join->join_list, all_tables, NULL,
used_tables);
-
- /*te.n_equality_deps= eq_deps_end - te.equality_deps;
-
- Module_dep *bound_modules;
- //Value_dep *bound_values;
- if (setup_equality_deps(&te, &bound_modules))
- DBUG_VOID_RETURN;
-
- run_elimination_wave(&te, bound_modules);
- */
}
DBUG_VOID_RETURN;
}
-////////////////////////////
-
/*
Perform table elimination in a given join list
SYNOPSIS
eliminate_tables_for_list()
- join The join
- leaves_arr OUT Store here an array of leaf (base) tables that
- are descendants of the join_list, and increment
- the pointer to point right above the array.
- join_list Join list to work on
- its_outer_join TRUE <=> join_list is an inner side of an outer
- join
- FALSE <=> otherwise (this is top-level join list)
- tables_in_list Bitmap of tables embedded in the join_list.
+ te Table elimination context
+ join_list Join list to work on
+ list_tables Bitmap of tables embedded in the join_list.
+ on_expr ON expression, if the join list is the inner side
+ of an outer join.
+ NULL means it's not an outer join but rather a
+ top-level join list.
tables_used_elsewhere Bitmap of tables that are referred to from
somewhere outside of the join list (e.g.
- select list, HAVING, etc).
+ select list, HAVING, other ON expressions, etc).
DESCRIPTION
- Perform table elimination for a join list.
- Try eliminating children nests first.
- The "all tables in join nest can produce only one matching record
- combination" property checking is modeled after constant table detection,
- plus we reuse info attempts to eliminate child join nests.
-
+ Perform table elimination in a given join list.
+
RETURN
- Number of children left after elimination. 0 means everything was
- eliminated.
+ TRUE The entire join list eliminated
+ FALSE Join list wasn't eliminated (but some of its possibly were)
*/
-bool try_eliminating(Table_elimination *te, table_map tables_in_list,
- Item* on_expr)
-{
- uint and_level=0;
- Equality_module* eq_dep= te->equality_deps;
- build_eq_deps_for_cond(te, &eq_dep, &and_level, on_expr,
- tables_in_list);
- te->n_equality_deps= eq_dep - te->equality_deps;
- Module_dep *bound_modules;
- get_outer_join_dep(te, tables_in_list);
-
- if (!setup_equality_deps(te, &bound_modules) &&
- run_elimination_wave(te, bound_modules))
- return TRUE; // eliminated
- return FALSE;
-}
-
-
-static uint
+static bool
eliminate_tables_for_list(Table_elimination *te, List<TABLE_LIST> *join_list,
- Item *on_expr,
- table_map tables_in_list,
+ table_map list_tables, Item *on_expr,
table_map tables_used_elsewhere)
{
TABLE_LIST *tbl;
List_iterator<TABLE_LIST> it(*join_list);
table_map tables_used_on_left= 0;
- bool not_eliminated= FALSE;
+ bool all_eliminated= TRUE;
while ((tbl= it++))
{
@@ -1130,26 +1077,25 @@
/* This is "... LEFT JOIN (join_nest) ON cond" */
if (eliminate_tables_for_list(te,
&tbl->nested_join->join_list,
+ tbl->nested_join->used_tables,
tbl->on_expr,
- tbl->nested_join->used_tables,
outside_used_tables))
{
mark_as_eliminated(te->join, tbl);
}
else
- not_eliminated= TRUE;
-
+ all_eliminated= FALSE;
}
else
{
/* This is "... LEFT JOIN tbl ON cond" */
if (!(tbl->table->map & outside_used_tables) &&
- try_eliminating(te, tbl->table->map, tbl->on_expr))
+ check_func_dependency(te, tbl->table->map, tbl->on_expr))
{
mark_as_eliminated(te->join, tbl);
}
else
- not_eliminated= TRUE;
+ all_eliminated= FALSE;
}
tables_used_on_left |= tbl->on_expr->used_tables();
}
@@ -1160,98 +1106,51 @@
}
/* Try eliminating the nest we're called for */
- if (!not_eliminated && on_expr && !(tables_in_list & tables_used_elsewhere))
- return try_eliminating(te, tables_in_list & ~te->join->eliminated_tables,
- on_expr);
-
+ if (all_eliminated && on_expr && !(list_tables & tables_used_elsewhere))
+ {
+ return check_func_dependency(te, list_tables & ~te->join->eliminated_tables,
+ on_expr);
+ }
return FALSE; /* not eliminated */
}
-#if 0
+
/*
- Build functional dependency graph for elements of given join list
+ Check if condition makes the a set of tables functionally-dependent
SYNOPSIS
- collect_funcdeps_for_join_list()
- te Table elimination context.
- join_list Join list to work on
- build_eq_deps TRUE <=> build Equality_module elements for all
- members of the join list, even if they cannot
- be individually eliminated
- tables_used_elsewhere Bitmap of tables that are referred to from
- somewhere outside of this join list (e.g.
- select list, HAVING, ON expressions of parent
- joins, etc).
- eliminable_tables INOUT Tables that can potentially be eliminated
- (needed so we know for which tables to build
- dependencies for)
- eq_dep INOUT End of array of equality dependencies.
+ check_func_dependency()
+ te Table elimination context
+ tables Set of tables we want to be functionally dependent
+ cond Condition to use
DESCRIPTION
- .
+ Check if condition allows to conclude that the table set is functionally
+ dependent on everything else.
+
+ RETURN
+ TRUE - Yes, functionally dependent
+ FALSE - No, or error
*/
-static bool
-collect_funcdeps_for_join_list(Table_elimination *te,
- List<TABLE_LIST> *join_list,
- bool build_eq_deps,
- table_map tables_used_elsewhere,
- table_map *eliminable_tables,
- Equality_module **eq_dep)
+static
+bool check_func_dependency(Table_elimination *te, table_map tables, Item* cond)
{
- TABLE_LIST *tbl;
- List_iterator<TABLE_LIST> it(*join_list);
- table_map tables_used_on_left= 0;
-
- while ((tbl= it++))
+ uint and_level=0;
+ Equality_module* eq_dep= te->equality_deps;
+ if (build_eq_deps_for_cond(te, &eq_dep, &and_level, cond, tables))
+ return TRUE;
+ te->n_equality_deps= eq_dep - te->equality_deps;
+ Module_dep *bound_modules;
+ if (!get_outer_join_dep(te, tables) &&
+ !setup_equality_deps(te, &bound_modules) &&
+ run_elimination_wave(te, bound_modules))
{
- if (tbl->on_expr)
- {
- table_map outside_used_tables= tables_used_elsewhere |
- tables_used_on_left;
- bool eliminable;
- table_map cur_map;
- if (tbl->nested_join)
- {
- /* This is "... LEFT JOIN (join_nest) ON cond" */
- cur_map= tbl->nested_join->used_tables;
- eliminable= !(cur_map & outside_used_tables);
- if (eliminable)
- *eliminable_tables |= cur_map;
- if (collect_funcdeps_for_join_list(te, &tbl->nested_join->join_list,
- eliminable || build_eq_deps,
- outside_used_tables,
- eliminable_tables,
- eq_dep))
- return TRUE;
- }
- else
- {
- /* This is "... LEFT JOIN tbl ON cond" */
- cur_map= tbl->table->map;
- eliminable= !(tbl->table->map & outside_used_tables);
- *eliminable_tables |= cur_map;
- }
-
- if (eliminable || build_eq_deps)
- {
- // build comp_cond from ON expression
- uint and_level=0;
- build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr,
- *eliminable_tables);
- }
-
- if (eliminable && !get_outer_join_dep(te, tbl, cur_map))
- return TRUE;
-
- tables_used_on_left |= tbl->on_expr->used_tables();
- }
+ return TRUE; /* eliminated */
}
return FALSE;
}
-#endif
-////////////////////////////
static
void signal_from_field_to_exprs(Table_elimination* te, Field_value *field_dep,
@@ -1272,18 +1171,18 @@
}
+/*
+ Run the wave.
+ All Func_dep-derived objects are divided into three classes:
+ - Those that have bound=FALSE
+ - Those that have bound=TRUE
+ - Those that have bound=TRUE and are in the list..
+*/
+
static
bool run_elimination_wave(Table_elimination *te, Module_dep *bound_modules)
{
Value_dep *bound_values= NULL;
- /*
- Run the wave.
- All Func_dep-derived objects are divided into three classes:
- - Those that have bound=FALSE
- - Those that have bound=TRUE
- - Those that have bound=TRUE and are in the list..
-
- */
while (bound_modules)
{
for (;bound_modules; bound_modules= bound_modules->next)
@@ -1318,14 +1217,8 @@
}
case Module_dep::MODULE_OUTER_JOIN:
{
- //Outer_join_module *outer_join_dep= (Outer_join_module*)bound_modules;
- //mark_as_eliminated(te->join, outer_join_dep->table_list);
- //if (!--te->n_outer_joins)
- {
- DBUG_PRINT("info", ("Table elimination eliminated everything"
- " it theoretically could"));
- return TRUE;
- }
+ DBUG_PRINT("info", ("Outer join eliminated"));
+ return TRUE;
break;
}
case Module_dep::MODULE_MULTI_EQUALITY:
@@ -1373,10 +1266,20 @@
DBUG_PRINT("info", ("table %s is now bound",
table_dep->table->alias));
/*
- Table is known means
+ Table is known means that
+ - one more element in outer join nest is known
- all its fields are known
- - one more element in outer join nest is known
*/
+ Outer_join_module *outer_join_dep= table_dep->outer_join_dep;
+ if (outer_join_dep->unknown_args &&
+ !--outer_join_dep->unknown_args)
+ {
+ /* Mark as bound and add to the list */
+ outer_join_dep->next= bound_modules;
+ bound_modules= outer_join_dep;
+ break;
+ }
+
for (Field_value *field_dep= table_dep->fields; field_dep;
field_dep= field_dep->next_table_field)
{
@@ -1387,18 +1290,6 @@
signal_from_field_to_exprs(te, field_dep, &bound_modules);
}
}
- //for (
- Outer_join_module *outer_join_dep= table_dep->outer_join_dep;
- // outer_join_dep; outer_join_dep= outer_join_dep->parent)
- {
- if (outer_join_dep->unknown_args &&
- !--outer_join_dep->unknown_args)
- {
- /* Mark as bound and add to the list */
- outer_join_dep->next= bound_modules;
- bound_modules= outer_join_dep;
- }
- }
break;
}
default:
