At file:///home/psergey/dev/maria-5.1-table-elim-r5/
------------------------------------------------------------
revno: 2734
revision-id: psergey(a)askmonty.org-20090813204452-o8whzlbio19cgkyv
parent: psergey(a)askmonty.org-20090813191053-g1xfeieoti4bqgbc
committer: Sergey Petrunya <psergey(a)askmonty.org>
branch nick: maria-5.1-table-elim-r5
timestamp: Fri 2009-08-14 00:44:52 +0400
message:
MWL#17: Table elimination
- More function renames, added comments
=== modified file 'sql/opt_table_elimination.cc'
--- a/sql/opt_table_elimination.cc 2009-08-13 19:10:53 +0000
+++ b/sql/opt_table_elimination.cc 2009-08-13 20:44:52 +0000
@@ -93,11 +93,9 @@
/*
- A field.
- - Depends on table or equality
- - Has expressions it participates as dependencies
-
- There is no counter, bound fields are in $list, not bound are not.
+ A table field. There is only one such object for any tblX.fieldY
+ - the field epends on its table and equalities
+ - expressions that use the field are its dependencies
*/
class Field_dep : public Func_dep
{
@@ -107,19 +105,23 @@
{
type= Func_dep::FD_FIELD;
}
- /* Table we're from. It also has pointers to keys that we're part of */
- Table_dep *table;
+
+ Table_dep *table; /* Table this field is from */
Field *field;
+ /*
+ Field_deps that belong to one table form a linked list. list members are
+ ordered by field_index
+ */
Field_dep *next_table_field;
uint bitmap_offset; /* Offset of our part of the bitmap */
};
/*
- A unique key.
- - Depends on all its components
- - Has its table as dependency
+ A Unique key.
+ - Unique key depends on all of its components
+ - Key's table is its dependency
*/
class Key_dep: public Func_dep
{
@@ -133,14 +135,15 @@
Table_dep *table; /* Table this key is from */
uint keyno;
uint n_missing_keyparts;
+ /* Unique keys form a linked list, ordered by keyno */
Key_dep *next_table_key;
};
/*
- A table.
- - Depends on any of its unique keys
- - Has its fields and embedding outer join as dependency.
+ A table.
+ - table depends on any of its unique keys
+ - has its fields and embedding outer join as dependency.
*/
class Table_dep : public Func_dep
{
@@ -151,16 +154,16 @@
type= Func_dep::FD_TABLE;
}
TABLE *table;
- Field_dep *fields; /* Fields that belong to this table */
- Key_dep *keys; /* Unique keys */
- Outer_join_dep *outer_join_dep;
+ Field_dep *fields; /* Ordered list of fields that belong to this table */
+ Key_dep *keys; /* Ordered list of Unique keys in this table */
+ Outer_join_dep *outer_join_dep; /* Innermost eliminable outer join we're in */
};
/*
- An outer join nest.
- - Depends on all tables inside it.
- - (And that's it).
+ An outer join nest that is subject to elimination
+ - it depends on all tables inside it
+ - has its parent outer join as dependency
*/
class Outer_join_dep: public Func_dep
{
@@ -171,14 +174,27 @@
{
type= Func_dep::FD_OUTER_JOIN;
}
+ /*
+ Outer join we're representing. This can be a join nest or a one table that
+ is outer join'ed.
+ */
TABLE_LIST *table_list;
+
+ /*
+ Tables within this outer join (and its descendants) that are not yet known
+ to be functionally dependent.
+ */
table_map missing_tables;
+ /* All tables within this outer join and its descendants */
table_map all_tables;
+ /* Parent eliminable outer join, if any */
Outer_join_dep *parent;
};
-/* TODO need this? */
+/*
+ Table elimination context
+*/
class Table_elimination
{
public:
@@ -204,20 +220,22 @@
static
-void build_funcdeps_for_cond(Table_elimination *te, Equality_dep **fdeps,
- uint *and_level, Item *cond,
- table_map usable_tables);
+void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps,
+ uint *and_level, Item *cond,
+ table_map usable_tables);
static
-void add_funcdep(Table_elimination *te,
- Equality_dep **eq_dep, uint and_level,
- Item_func *cond, Field *field,
- bool eq_func, Item **value,
- uint num_values, table_map usable_tables);
+void add_eq_dep(Table_elimination *te,
+ Equality_dep **eq_dep, uint and_level,
+ Item_func *cond, Field *field,
+ bool eq_func, Item **value,
+ uint num_values, table_map usable_tables);
static
Equality_dep *merge_func_deps(Equality_dep *start, Equality_dep *new_fields,
Equality_dep *end, uint and_level);
-Field_dep *get_field_dep(Table_elimination *te, Field *field);
+static Table_dep *get_table_dep(Table_elimination *te, TABLE *table);
+static Field_dep *get_field_dep(Table_elimination *te, Field *field);
+
void eliminate_tables(JOIN *join);
static void mark_as_eliminated(JOIN *join, TABLE_LIST *tbl);
@@ -228,24 +246,25 @@
/*******************************************************************************************/
/*
- Produce FUNC_DEP elements for the given item (i.e. condition) and add them
- to fdeps array.
+ Produce Eq_dep elements for given condition.
SYNOPSIS
- build_funcdeps_for_cond()
- fdeps INOUT Put created FUNC_DEP structures here
-
+ build_eq_deps_for_cond()
+ te Table elimination context
+ fdeps INOUT Put produced equality conditions here
+ and_level INOUT AND-level (like in add_key_fields)
+ cond Condition to process
+ usable_tables Tables which fields we're interested in. That is,
+ Equality_dep represent "tbl.col=expr" and we'll
+ produce them only if tbl is in usable_tables.
DESCRIPTION
- a
-
- SEE ALSO
- add_key_fields()
-
+ This function is modeled after add_key_fields()
*/
+
static
-void build_funcdeps_for_cond(Table_elimination *te,
- Equality_dep **fdeps, uint *and_level, Item *cond,
- table_map usable_tables)
+void build_eq_deps_for_cond(Table_elimination *te, Equality_dep **fdeps,
+ uint *and_level, Item *cond,
+ table_map usable_tables)
{
if (cond->type() == Item_func::COND_ITEM)
{
@@ -258,7 +277,7 @@
Item *item;
while ((item=li++))
{
- build_funcdeps_for_cond(te, fdeps, and_level, item, usable_tables);
+ build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables);
}
/*
TODO: inject here a "if we have {t.col=const AND t.col=smth_else}, then
@@ -270,13 +289,13 @@
else
{
(*and_level)++;
- build_funcdeps_for_cond(te, fdeps, and_level, li++, usable_tables);
+ build_eq_deps_for_cond(te, fdeps, and_level, li++, usable_tables);
Item *item;
while ((item=li++))
{
Equality_dep *start_key_fields= *fdeps;
(*and_level)++;
- build_funcdeps_for_cond(te, fdeps, and_level, item, usable_tables);
+ build_eq_deps_for_cond(te, fdeps, and_level, item, usable_tables);
*fdeps= merge_func_deps(org_key_fields, start_key_fields, *fdeps,
++(*and_level));
}
@@ -304,11 +323,11 @@
values--;
DBUG_ASSERT(cond_func->functype() != Item_func::IN_FUNC ||
cond_func->argument_count() != 2);
- add_funcdep(te, fdeps, *and_level, cond_func,
- ((Item_field*)(cond_func->key_item()->real_item()))->field,
- 0, values,
- cond_func->argument_count()-1,
- usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func,
+ ((Item_field*)(cond_func->key_item()->real_item()))->field,
+ 0, values,
+ cond_func->argument_count()-1,
+ usable_tables);
}
if (cond_func->functype() == Item_func::BETWEEN)
{
@@ -321,8 +340,8 @@
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
{
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
- add_funcdep(te, fdeps, *and_level, cond_func,
- field_item->field, 0, values, 1, usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func,
+ field_item->field, 0, values, 1, usable_tables);
}
}
}
@@ -336,19 +355,19 @@
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
{
- add_funcdep(te, fdeps, *and_level, cond_func,
- ((Item_field*)(cond_func->arguments()[0])->real_item())->field,
- equal_func,
- cond_func->arguments()+1, 1, usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func,
+ ((Item_field*)(cond_func->arguments()[0])->real_item())->field,
+ equal_func,
+ cond_func->arguments()+1, 1, usable_tables);
}
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
cond_func->functype() != Item_func::LIKE_FUNC &&
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
{
- add_funcdep(te, fdeps, *and_level, cond_func,
- ((Item_field*)(cond_func->arguments()[1])->real_item())->field,
- equal_func,
- cond_func->arguments(),1,usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func,
+ ((Item_field*)(cond_func->arguments()[1])->real_item())->field,
+ equal_func,
+ cond_func->arguments(),1,usable_tables);
}
break;
}
@@ -360,10 +379,10 @@
Item *tmp=new Item_null;
if (unlikely(!tmp)) // Should never be true
return;
- add_funcdep(te, fdeps, *and_level, cond_func,
- ((Item_field*)(cond_func->arguments()[0])->real_item())->field,
- cond_func->functype() == Item_func::ISNULL_FUNC,
- &tmp, 1, usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func,
+ ((Item_field*)(cond_func->arguments()[0])->real_item())->field,
+ cond_func->functype() == Item_func::ISNULL_FUNC,
+ &tmp, 1, usable_tables);
}
break;
case Item_func::OPTIMIZE_EQUAL:
@@ -380,8 +399,8 @@
*/
while ((item= it++))
{
- add_funcdep(te, fdeps, *and_level, cond_func, item->field,
- TRUE, &const_item, 1, usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func, item->field,
+ TRUE, &const_item, 1, usable_tables);
}
}
else
@@ -400,8 +419,8 @@
{
if (!field->eq(item->field))
{
- add_funcdep(te, fdeps, *and_level, cond_func, field/*item*/,
- TRUE, (Item **) &item, 1, usable_tables);
+ add_eq_dep(te, fdeps, *and_level, cond_func, field,
+ TRUE, (Item **) &item, 1, usable_tables);
}
}
it.rewind();
@@ -411,15 +430,19 @@
}
}
+
/*
- Perform an OR operation on two (adjacent) FUNC_DEP arrays.
+ Perform an OR operation on two (adjacent) Equality_dep arrays.
SYNOPSIS
merge_func_deps()
+ start Start of left OR-part
+ new_fields Start of right OR-part
+ end End of right OR-part
+ and_level AND-level.
DESCRIPTION
-
- This function is invoked for two adjacent arrays of FUNC_DEP elements:
+ This function is invoked for two adjacent arrays of Equality_dep elements:
$LEFT_PART $RIGHT_PART
+-----------------------+-----------------------+
@@ -527,17 +550,18 @@
/*
- Add a funcdep for a given equality.
+ Add an Equality_dep element for a given predicate, if applicable
+
+ DESCRIPTION
+ This function is modeled after add_key_field().
*/
static
-void add_funcdep(Table_elimination *te,
- Equality_dep **eq_dep, uint and_level,
- Item_func *cond, Field *field,
- bool eq_func, Item **value,
- uint num_values, table_map usable_tables)
+void add_eq_dep(Table_elimination *te, Equality_dep **eq_dep,
+ uint and_level, Item_func *cond, Field *field,
+ bool eq_func, Item **value, uint num_values,
+ table_map usable_tables)
{
- // Field *field= item_field->field;
if (!(field->table->map & usable_tables))
return;
@@ -606,7 +630,11 @@
}
-Table_dep *get_table_dep(Table_elimination *te, TABLE *table)
+/*
+ Get a Table_dep object for the given table, creating it if necessary.
+*/
+
+static Table_dep *get_table_dep(Table_elimination *te, TABLE *table)
{
Table_dep *tbl_dep= new Table_dep(table);
Key_dep **key_list= &(tbl_dep->keys);
@@ -625,19 +653,21 @@
return te->table_deps[table->tablenr] = tbl_dep;
}
+
/*
- Given a field, get its dependency element: if it already exists, find it,
- otherwise create it.
+ Get a Field_dep object for the given field, creating it if necessary
*/
-Field_dep *get_field_dep(Table_elimination *te, Field *field)
+static Field_dep *get_field_dep(Table_elimination *te, Field *field)
{
TABLE *table= field->table;
Table_dep *tbl_dep;
+ /* First, get the table*/
if (!(tbl_dep= te->table_deps[table->tablenr]))
tbl_dep= get_table_dep(te, table);
-
+
+ /* Try finding the field in field list */
Field_dep **pfield= &(tbl_dep->fields);
while (*pfield && (*pfield)->field->field_index < field->field_index)
{
@@ -646,20 +676,34 @@
if (*pfield && (*pfield)->field->field_index == field->field_index)
return *pfield;
+ /* Create the field and insert it in the list */
Field_dep *new_field= new Field_dep(tbl_dep, field);
-
new_field->next_table_field= *pfield;
*pfield= new_field;
+
return new_field;
}
+/*
+ Create an Outer_join_dep object for the given outer join
+
+ DESCRIPTION
+ Outer_join_dep objects for children (or further descendants) are always
+ created before the parents.
+*/
+
+static
Outer_join_dep *get_outer_join_dep(Table_elimination *te,
TABLE_LIST *outer_join, table_map deps_map)
{
Outer_join_dep *oj_dep;
oj_dep= new Outer_join_dep(outer_join, deps_map);
-
+
+ /*
+ Collect a bitmap fo tables that we depend on, and also set parent pointer
+ for descendant outer join elements.
+ */
Table_map_iterator it(deps_map);
int idx;
while ((idx= it.next_bit()) != Table_map_iterator::BITMAP_END)
@@ -667,6 +711,11 @@
Table_dep *table_dep;
if (!(table_dep= te->table_deps[idx]))
{
+ /*
+ We get here only when ON expression had no references to inner tables
+ and Table_map objects weren't created for them. This is a rare/
+ unimportant case so it's ok to do not too efficient searches.
+ */
TABLE *table= NULL;
for (TABLE_LIST *tlist= te->join->select_lex->leaf_tables; tlist;
tlist=tlist->next_leaf)
@@ -680,7 +729,13 @@
DBUG_ASSERT(table);
table_dep= get_table_dep(te, table);
}
-
+
+ /*
+ 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_dep.
+ to set the pointer of its near
+ */
if (!table_dep->outer_join_dep)
table_dep->outer_join_dep= oj_dep;
else
@@ -690,43 +745,35 @@
oj= oj->parent;
oj->parent=oj_dep;
}
-
}
return oj_dep;
}
/*
- Perform table elimination in a given join list
+ Build functional dependency graph for elements of given join list
SYNOPSIS
collect_funcdeps_for_join_list()
- te Table elimination context.
- join_list Join list to work on
- its_outer_join TRUE <=> the join_list is an inner side of an
- outer join
- FALSE <=> otherwise (this is top-level join
- list, simplify_joins flattens out all
- other kinds of join lists)
-
- tables_in_list Bitmap of tables embedded in the 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).
+ te Table elimination context.
+ join_list Join list to work on
+ build_eq_deps TRUE <=> build Equality_dep 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.
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.
-
- RETURN
- Number of children left after elimination. 0 means everything was
- eliminated.
+ .
*/
-static uint
+static void
collect_funcdeps_for_join_list(Table_elimination *te,
List<TABLE_LIST> *join_list,
bool build_eq_deps,
@@ -771,7 +818,7 @@
{
// build comp_cond from ON expression
uint and_level=0;
- build_funcdeps_for_cond(te, eq_dep, &and_level, tbl->on_expr,
+ build_eq_deps_for_cond(te, eq_dep, &and_level, tbl->on_expr,
*eliminable_tables);
}
@@ -781,19 +828,13 @@
tables_used_on_left |= tbl->on_expr->used_tables();
}
}
- return 0;
+ return;
}
+
/*
- Analyze exising FUNC_DEP array and add elements for tables and uniq keys
-
- SYNOPSIS
-
- DESCRIPTION
- Add FUNC_DEP elements
-
- RETURN
- .
+ This is used to analyse expressions in "tbl.col=expr" dependencies so
+ that we can figure out which fields the expression depends on.
*/
class Field_dependency_setter : public Field_enumerator
@@ -819,20 +860,41 @@
return;
}
}
- /* We didn't find the field. Bump the dependency anyway */
+ /*
+ We got here if didn't find this field. It's not a part of
+ a unique key, and/or there is no field=expr element for it.
+ Bump the dependency anyway, this will signal that this dependency
+ cannot be satisfied.
+ */
te->equality_deps[expr_offset].unknown_args++;
}
}
+
Table_elimination *te;
- uint expr_offset; /* Offset of the expression we're processing */
+ /* Offset of the expression we're processing in the dependency bitmap */
+ uint expr_offset;
};
+/*
+ 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)
+*/
+
static
bool setup_equality_deps(Table_elimination *te, Func_dep **bound_deps_list)
{
DBUG_ENTER("setup_equality_deps");
+ /*
+ Count Field_dep objects and assign each of them a unique bitmap_offset.
+ */
uint offset= 0;
for (Table_dep **tbl_dep=te->table_deps;
tbl_dep < te->table_deps + MAX_TABLES;
@@ -859,7 +921,10 @@
bitmap_clear_all(&te->expr_deps);
/*
- Walk through all field=expr elements and collect all fields.
+ Analyze all "field=expr" dependencies, and have te->expr_deps encode
+ dependencies of expressions from fields.
+
+ Also collect a linked list of equalities that are bound.
*/
Func_dep *bound_dep= NULL;
Field_dependency_setter deps_setter(te);
