Below is the list of changes that have just been committed into a local
5.1 repository of timka. When timka does a push these changes will
be propagated to the main repository and, within 24 hours after the
push, to the public repository.
For information on how to access the public repository
see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html
ChangeSet
1.2208 06/06/27 19:45:09 timour@stripped +4 -0
This patch adds comments to old optimizer-related code. There are no code changes.
The only changes to the source are that few statements are split into more lines
to align code on < 80 characters.
sql/sql_select.h
1.109 06/06/27 19:45:05 timour@stripped +182 -15
Commented old optimizer code.
sql/sql_select.cc
1.414 06/06/27 19:45:05 timour@stripped +374 -52
Commented old optimizer code.
sql/sql_class.h
1.302 06/06/27 19:45:04 timour@stripped +10 -3
Commented old optimizer code.
sql/opt_range.h
1.62 06/06/27 19:45:04 timour@stripped +14 -0
Commented old optimizer code.
# This is a BitKeeper patch. What follows are the unified diffs for the
# set of deltas contained in the patch. The rest of the patch, the part
# that BitKeeper cares about, is below these diffs.
# User: timour
# Host: lamia.home
# Root: /home/timka/mysql/src/5.1-commented
--- 1.61/sql/opt_range.h 2006-06-04 18:52:12 +03:00
+++ 1.62/sql/opt_range.h 2006-06-27 19:45:04 +03:00
@@ -675,6 +675,20 @@ private:
List_iterator<QUICK_RANGE> rev_it;
};
+/*
+ This class represents a single-table access plan for a range or loose index
+ scan with all relevant statistics and the actual QUICK_* object used for data
+ access. The method test_quick_select() runs the range optimizer, chooses
+ the best range/loose scan access method, stores the statistics of the chosen
+ method and constructs the object that represents it.
+
+ TODO:
+ Remove this class. It is reduntant and limiting. Such a class assumes that
+ one range/loose scan access method can be chosen once and for all, thus
+ limiting future optimizations. In addition this is yet another way to
+ represent the information about table access methods, which complicates
+ the query engine.
+*/
class SQL_SELECT :public Sql_alloc {
public:
--- 1.301/sql/sql_class.h 2006-06-22 14:27:43 +03:00
+++ 1.302/sql/sql_class.h 2006-06-27 19:45:04 +03:00
@@ -1635,9 +1635,14 @@ public:
#include <myisam.h>
/*
- Param to create temporary tables when doing SELECT:s
+ Context with information used both when creating and using temporary tables.
+ The temporary tables created with this context are used only internally by
+ the query execution engine.
+
NOTE
- This structure is copied using memcpy as a part of JOIN.
+ - This structure is used not only at table creation time, but also at
+ query execution time.
+ - This structure is copied using memcpy as a part of JOIN.
*/
class TMP_TABLE_PARAM :public Sql_alloc
@@ -1655,6 +1660,7 @@ public:
byte *group_buff;
Item **items_to_copy; /* Fields in tmp table */
MI_COLUMNDEF *recinfo,*start_recinfo;
+ /* After tmp table creation, points to an index on the table */
KEY *keyinfo;
ha_rows end_write_records;
uint field_count,sum_func_count,func_count;
@@ -1963,7 +1969,8 @@ public:
List<my_var> var_list;
List<Item_func_set_user_var> vars;
List<Item_splocal> local_vars;
- select_dumpvar(void) { var_list.empty(); local_vars.empty(); vars.empty(); row_count=0;}
+ select_dumpvar(void)
+ { var_list.empty(); local_vars.empty(); vars.empty(); row_count=0;}
~select_dumpvar() {}
int prepare(List<Item> &list, SELECT_LEX_UNIT *u);
bool send_data(List<Item> &items);
--- 1.413/sql/sql_select.cc 2006-06-18 13:20:28 +03:00
+++ 1.414/sql/sql_select.cc 2006-06-27 19:45:05 +03:00
@@ -536,10 +536,57 @@ bool JOIN::test_in_subselect(Item **wher
/*
- global select optimisation.
- return 0 - success
- 1 - error
- error code saved in field 'error'
+ Global select optimisation.
+
+ SYNOPSIS
+ JOIN::optimize()
+
+ DESCRIPTION
+ Entry point to the query optimization phase of SELECT statements. This
+ phase applies both logical (equivalent) query rewrites, cost-based
+ join optimization, and rule-based access path selection. Once an optimal
+ plan is found, the method creates/initializes all structures needed for
+ query execution. The main optimization phases are outlined in the pseudocode
+ below:
+
+ JOIN::optimize()
+ {
+ A. Logical transformations
+ * equality/constant propagation
+ * partition pruning (through range optimzer)
+ * COUNT/MIN/MAX constant substitution
+ * ORDER BY optimization
+ B. Cost-based optimization
+ * Preparation phase
+ - plan structure creation/initialization
+ - constant table analysis
+ - equality condition optimization (ref optimizer)
+ - range condition optimization (range optimizer)
+ - single-index range optimization
+ - index merge optimization
+ - loose index scan optimization
+ - cost/intermediate result sizes precomputation
+ * Join cost-based optimization
+ - exhaustive/greedy/straight search
+ - choice of best access path between:
+ - binding-free access methods
+ - binding-requiring access methods
+ - best join method search (hash jon vs nested loops)
+ C. Post-join order optimization
+ * determine push-down conditions
+ * inject outer-join guarding conditions
+ * adjust data access methods after push-down analysis
+ (several times)
+ * optimize ORDER BY/DISTINCT
+ D. Code generation
+ * set data access functions
+ * try to optimize away sorting/distinct
+ * pre-create temporary tables
+ }
+
+ RETURN
+ 0 - success
+ 1 - error, error code saved in field 'error'
*/
int
@@ -791,7 +838,7 @@ JOIN::optimize()
error= -1; /* if goto err */
- /* Optimize distinct away if possible */
+ /* Optimize DISTINCT away if possible. */
{
ORDER *org_order= order;
order=remove_const(this, order,conds,1, &simple_order);
@@ -1947,10 +1994,29 @@ err:
DBUG_RETURN(join->error);
}
-/*****************************************************************************
- Create JOIN_TABS, make a guess about the table types,
- Approximate how many records will be used in each table
-*****************************************************************************/
+
+/*
+ Estimate the # of result records returned by the best range scan method.
+
+ SYNOPSIS
+ thd thread for the connection that submitted the query
+ select single-table select that uses an index
+ table table that we select from
+ keys candidate indexes for index scan
+ limit maximimum number of rows to select
+
+ DESCRIPTION
+ The function calls the range optimizer to estimate the cost of the cheapest
+ QUICK_* index access method to scan one of the 'keys' using the conditions
+ 'select->cond'.
+ If the best index access method is cheaper than a table and an index scan,
+ then the range optimizer also constructs the corresponding QUICK_* object
+ and assigns it to select->quick. In most cases this is the QUICK_* object
+ used at later (optimization and execution) phases.
+
+ RETURN
+ Estimated # of result rows selected from 'table'.
+*/
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
TABLE *table,
@@ -1977,11 +2043,58 @@ static ha_rows get_quick_record_count(TH
/*
- Calculate the best possible join and initialize the join structure
+ Initialize the join structure and find the best possible join plan.
- RETURN VALUES
- 0 ok
- 1 Fatal error
+ SYNOPSIS
+ make_join_statistics()
+ join [in/ou] pointer to the structure providing all context info
+ for the query
+ tables [in] all leaf tables in the FROM clause
+ conds [in] WHERE clause
+ keyuse_array [out] memory for keys/keyparts that can be used for index
+ ref lookup
+ DESCRIPTION
+ Entry point to the cost-based optimizer. This procedure roughly does:
+ 1. Create/initialize all query-plan related operators
+ - create and initialize plan-related arrays
+ (JOIN::join_tab, JOIN::best_ref, JOIN::positions,
+ JOIN::best_positions)
+ - perform constant table analysis for trivial cases.
+ 2. If there is an outer join, build transitive closure for the relation
+ 'to be dependent on' for outer joins.
+ 3. Perform 'ref' optimization for equi-join conditions and compute
+ equi-join statistics via update_ref_and_keys().
+ Analyze the WHERE and ON conditons for conjunctions of equi-join
+ conditions that can be used for index access, and create a graph
+ of all such conditions, where the nodes are tables, the arcs are
+ the conditions, and each arc is marked with the number of matched rows.
+ The graph is stored as an array of pairs of arcs in JOIN::keyuse.
+ In addition:
+ - determine constant columns (suitable for index access)
+ - accumulate information about null-rejecting predicates.
+ 4. Constant table analysis:
+ - read all constant tables found up to this point (in 1. above)
+ - discover constant tables
+ - find tables with 0 and 1 rows
+ - use the result of phase 3. ('ref' optimization) to discover
+ table access by PK or constant references.
+ - read all discovered constant tables
+ 5. Pre-calculate estimates for the number of matched records in each table:
+ - determine constant columns (suitable for index access) for
+ GROUP BY/DISTINCT,
+ - get_quick_record_count() - perform range analysis.
+ 6. Update the statistics of all equi-join conditions found via
+ optimize_keyuse()
+ 7. Perform cost-based join optimization via choose_plan().
+ - call the exhaustive, greedy, straight join optimizers
+ - use best_access_path() - join-order dependent choice of best
+ access path for equi-join conditons
+ 8. Generate an execution plan from the found optimal join order via
+ get_best_combination().
+
+ RETURN
+ FALSE ok
+ TRUE Fatal error
*/
static bool
@@ -1997,12 +2110,23 @@ make_join_statistics(JOIN *join, TABLE_L
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
KEYUSE *keyuse,*start_keyuse;
table_map outer_join=0;
+ /*
+ Automatic storage for intermediate join plans during optimization.
+ The join optimizer (choose_plan()) uses the memory of stat_vector
+ via the pointer JOIN::best_ref.
+ */
JOIN_TAB *stat_vector[MAX_TABLES+1];
DBUG_ENTER("make_join_statistics");
table_count=join->tables;
+ /*
+ Allocate memory for query plan representation and intermediate data
+ structures used for query optimization.
+ */
stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
+ /* TODO: we don't have to allocate MAX_TABLES JOIN_TABs. */
stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
+ /* TODO: why table_vector needs to be twice table_count? */
table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2));
if (!stat || !stat_ref || !table_vector)
DBUG_RETURN(1); // Eom /* purecov: inspected */
@@ -2013,6 +2137,10 @@ make_join_statistics(JOIN *join, TABLE_L
found_const_table_map= all_table_map=0;
const_count=0;
+ /*
+ Initialize all query plan related data structures from the list of
+ base (leaf) tables in the query.
+ */
for (s= stat, i= 0;
tables;
s++, tables= tables->next_leaf, i++)
@@ -2044,12 +2172,17 @@ make_join_statistics(JOIN *join, TABLE_L
{
/* s is the only inner table of an outer join */
#ifdef WITH_PARTITION_STORAGE_ENGINE
- if ((!table->file->stats.records || table->no_partitions_used) && !embedding)
+ if ((!table->file->stats.records || table->no_partitions_used) &&
+ !embedding)
#else
if (!table->file->stats.records && !embedding)
#endif
- { // Empty table
- s->dependent= 0; // Ignore LEFT JOIN depend.
+ {
+ /*
+ If 'table' is empty, then set it as a constant table and
+ ignore the LEFT JOIN dependency.
+ */
+ s->dependent= 0;
set_position(join,const_count++,s,(KEYUSE*) 0);
continue;
}
@@ -2079,6 +2212,11 @@ make_join_statistics(JOIN *join, TABLE_L
#else
const bool no_partitions_used= FALSE;
#endif
+ /*
+ If the table is a system table, or has 1 or 0 records, and is not
+ dependent on an outer table, and the row count is exact, and it is
+ not full-text searched then mark it as a constant table.
+ */
if ((table->s->system || table->file->stats.records <= 1 ||
no_partitions_used) &&
!s->dependent &&
@@ -2131,7 +2269,7 @@ make_join_statistics(JOIN *join, TABLE_L
~outer_join, join->select_lex))
DBUG_RETURN(1);
- /* Read tables with 0 or 1 rows (system tables) */
+ /* Read all constant tables (with 0 or 1 rows) found up to this point. */
join->const_table_map= 0;
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
@@ -2151,7 +2289,10 @@ make_join_statistics(JOIN *join, TABLE_L
found_const_table_map|= s->table->map;
}
- /* loop until no more const tables are found */
+ /*
+ Constant table analysis. Discover and read all constant tables
+ until no more constand tables can be found.
+ */
int ref_changed;
do
{
@@ -2348,19 +2489,59 @@ make_join_statistics(JOIN *join, TABLE_L
/*****************************************************************************
- Check with keys are used and with tables references with tables
- Updates in stat:
- keys Bitmap of all used keys
- const_keys Bitmap of all keys with may be used with quick_select
- keyuse Pointer to possible keys
+ RefOptimizerModule - this module analyzes all equality conditions to
+ determine the best 'ref' and 'eq_ref' index access methods. Entry point:
+ update_ref_and_keys().
+
+ The 'ref' optimizer determines the fields (and expressions over them) that
+ reference fields in other tables via an equality, and analyzes which keys
+ and key parts can be used for index lookup based on these references. The
+ main outcomes of the 'ref' optmizer are:
+
+ * A bi-directional graph of all equi-join conditions represented as an
+ array of KEYUSE elements. This array is stored in JOIN::keyuse in
+ table, key, keypart order. Each JOIN_TAB::keyuse points to the
+ first KEYUSE element with the same table as JOIN_TAB::table.
+
+ * The table dependecies needed by the optimizer to determine what
+ tables must be before certain table so that they provide the
+ necessary column bindings for the equality conditions.
+
+ * Computed properties of the equality conditions such as null-rejecting
+ and the result size of each seprate condition.
+
+ Updates in JOIN_TAB:
+ JOIN_TAB::keys Bitmap of all used keys
+ JOIN_TAB::const_keys Bitmap of all keys that may be used with quick_select
+ JOIN_TAB::keyuse Pointer to possible keys
*****************************************************************************/
-typedef struct key_field_t { // Used when finding key fields
- Field *field;
- Item *val; // May be empty if diff constant
+/*
+ A KEY_FIELD is a descriptor of a condition of the form (field <op> val).
+ Currently 'op' is only '=', and 'val' can be either another field or
+ an expression (including constants).
+
+ KEY_FIELDs are used to analyse fields that may potentially serve as
+ parts of keys for index lookup. If such a field is usable for index
+ lookup, then add_key_part() creates a corresponding KEYUSE object
+ and inserts it into the JOIN::keyuse array which is passed by
+ update_ref_and_keys().
+
+ The structure is used only during analysis of the candidate fields for
+ index 'ref' access.
+*/
+
+typedef struct key_field_t {
+ Field *field; /* Field on the left side of an equality. */
+ /*
+ Value to the right of an equality. It is Item_field if to the right of
+ an equality there is another field, or it can be any other expression.
+ May be empty if diff constant (whatever 'diff' means).
+ */
+ Item *val;
uint level;
uint optimize;
- bool eq_func;
+ bool eq_func; /* Currently always TRUE. */
/*
If true, the condition this struct represents will not be satisfied
when val IS NULL.
@@ -2961,6 +3142,28 @@ add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
}
+/*
+ Compare two keyuse elements.
+
+ SYNOPSIS
+ compare_keuse
+ a first KEYUSE element
+ b second KEYUSE element
+
+ DESCRIPTION
+ Compare KEYUSE elements so that they are sorted as follows:
+ - by table
+ - by key for each table
+ - by keypart for each key
+ - const values first
+ - ref_or_null last
+
+ RETURN
+ 0 if a = b
+ < 0 if a < b
+ 0 if a b
+*/
+
static int
sort_keyuse(KEYUSE *a,KEYUSE *b)
{
@@ -2984,7 +3187,7 @@ sort_keyuse(KEYUSE *a,KEYUSE *b)
/*
Add to KEY_FIELD array all 'ref' access candidates within nested join
- SYNPOSIS
+ SYNOPSIS
add_key_fields_for_nj()
nested_join_table IN Nested join pseudo-table to process
end INOUT End of the key field array
@@ -3038,14 +3241,19 @@ static void add_key_fields_for_nj(TABLE_
update_ref_and_keys()
thd
keyuse OUT Put here ordered array of KEYUSE structures
- join_tab Array in tablenr_order
+ join_tab Array of plan nodes in tablenr_order
tables Number of tables in join
cond WHERE condition (note that the function analyzes
join_tab[i]->on_expr too)
+ cond_equal list of multiple equalities
normal_tables tables not inner w.r.t some outer join (ones for which
we can make ref access based the WHERE clause)
select_lex current SELECT
-
+
+ DESCRIPTION
+ Entry point to the 'ref' optimizer.
+ TODO
+
RETURN
0 - OK
1 - Out of memory.
@@ -3175,7 +3383,22 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR
}
/*
- Update some values in keyuse for faster choose_plan() loop
+ Update some values in keyuse for faster choose_plan() loop.
+
+ SYNOPSIS
+ update_keyuse_statistics()
+ join current (incomplete) join plan
+ keyuse_array array of KEYUSE elements being updated
+
+ DESCRIPTION
+ This function computes keyuse->ref_table_rows, which most likely
+ has the meaning of "total number of rows in the equi-join result".
+
+ TODO
+ Check if this is the real meaning of ref_table_rows.
+
+ RETURN
+ None
*/
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array)
@@ -3203,6 +3426,12 @@ static void optimize_keyuse(JOIN *join,
if (map == 1) // Only one table
{
TABLE *tmp_table=join->all_tables[tablenr];
+ /*
+ TODO: Here we set ref_table_rows = |referenced table|, which
+ is not the same as what the previous comment says -
+ |outer_table| / |inner_table|.
+ What is the _real_ meaning of KEYUSE::ref_table_rows?
+ */
keyuse->ref_table_rows= max(tmp_table->file->stats.records, 100);
}
}
@@ -3221,8 +3450,8 @@ static void optimize_keyuse(JOIN *join,
SYNOPSIS
add_group_and_distinct_keys()
- join
- join_tab
+ join pointer to the structure providing all context info for the query
+ join_tab current plan node
DESCRIPTION
If the query has a GROUP BY clause, find all indexes that contain all
@@ -3558,7 +3787,7 @@ best_access_path(JOIN *join,
We also have a property that "range optimizer produces equal or
tighter set of scan intervals than ref(const) optimizer". Each
of the intervals in (**) are "tightest possible" intervals when
- one limits itself to using keyparts 1..K (which we do in #2).
+ one limits itself to using keyparts 1..K (which we do in #2).
From here it follows that range access used either one, or
both of the (I1) and (I2) intervals:
@@ -4385,7 +4614,8 @@ best_extension_by_limited_search(JOIN
}
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
- { /* Recursively expand the current partial plan */
+ {
+ /* Recursively expand the current partial plan */
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
best_extension_by_limited_search(join,
remaining_tables & ~real_table_bit,
@@ -4399,7 +4629,8 @@ best_extension_by_limited_search(JOIN
swap_variables(JOIN_TAB*, join->best_ref[idx], *pos);
}
else
- { /*
+ {
+ /*
'join' is either the best partial QEP with 'search_depth' relations,
or the best complete QEP so far, whichever is smaller.
*/
@@ -4582,9 +4813,25 @@ prev_record_reads(JOIN *join,table_map f
}
-/*****************************************************************************
- Set up join struct according to best position.
-*****************************************************************************/
+/*
+ Set up the query execution context and its plan operators according to the
+ optimal plan.
+
+ SYNOPSIS
+ get_best_combination()
+ join pointer to the structure providing all context info for the query
+
+ DESCRIPTION
+ Complete optimal query plans are stored in the array join->best_positions,
+ where each position consists of a plan operator and some extra information
+ (cost, key, etc.). This procedure allocates memory for the executable
+ representation of a plan in join->join_plan, and initializes each plan
+ operator from the corresponding best_positions element.
+
+ RETURN
+ TRUE if error (memory allocation)
+ FALSE on success
+*/
static bool
get_best_combination(JOIN *join)
@@ -4640,6 +4887,29 @@ get_best_combination(JOIN *join)
}
+/*
+ Create/init a 'ref' access method from a KEYUSE array for a given plan node.
+
+ SYNOPSIS
+ create_ref_for_key()
+ join pointer to the structure providing all context info for
+ the query
+ j current plan operator
+ pop_keyuse equality conditions for the current plan operator
+ used_tables set of tables in the plan before this plan operator
+
+ DESCRIPTION
+ Given a KEYUSE structure that specifies the fields that can be used
+ for index access, create and set up the structure used for index look up
+ via one of the access methods {JT_FT, JT_CONST, JT_REF_OR_NULL, JT_REF,
+ JT_EQ_REF} for the plan operator 'j'. Generally the procedure sets up the
+ structure j->ref (of type TABLE_REF), and the access method j->type.
+
+ RETURN
+ TRUE on error
+ FALSE if success
+*/
+
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
table_map used_tables)
{
@@ -4656,6 +4926,7 @@ static bool create_ref_for_key(JOIN *joi
key=keyuse->key;
keyinfo=table->key_info+key;
+ /* Calculate the length of the used key. */
if (ftkey)
{
Item_func_match *ifm=(Item_func_match *)keyuse->val;
@@ -4669,9 +4940,8 @@ static bool create_ref_for_key(JOIN *joi
keyparts=length=0;
uint found_part_ref_or_null= 0;
/*
- Calculate length for the used key
Stop if there is a missing key part or when we find second key_part
- with KEY_OPTIMIZE_REF_OR_NULL
+ with KEY_OPTIMIZE_REF_OR_NULL.
*/
do
{
@@ -5140,6 +5410,23 @@ make_outerjoin_info(JOIN *join)
}
+/*
+ Perform push-down analysys and adjust access methods after the analysis.
+
+ SYNOPSIS
+ make_join_select()
+ join reference to the info fully describing the query
+ select descriptor of single-table select
+ cond (optional) condition
+
+ DESCRIPTION
+ TODO
+
+ RETURN
+ TRUE if something wrong
+ FALSE on success
+*/
+
static bool
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
{
@@ -5613,7 +5900,8 @@ make_join_readinfo(JOIN *join, uint opti
if (tab->select && tab->select->quick)
{
if (statistics)
- statistic_increment(join->thd->status_var.select_full_range_join_count,
+ statistic_increment(join->thd->status_var.
+ select_full_range_join_count,
&LOCK_status);
}
else
@@ -5644,7 +5932,8 @@ make_join_readinfo(JOIN *join, uint opti
}
break;
default:
- DBUG_PRINT("error",("Table type %d found",tab->type)); /* purecov: deadcode */
+ /* purecov: deadcode */
+ DBUG_PRINT("error",("Table type %d found",tab->type));
break; /* purecov: deadcode */
case JT_UNKNOWN:
case JT_MAYBE_REF:
@@ -7624,7 +7913,7 @@ static void reset_nj_counters(List<TABLE
The limitations on join order can be rephrased as follows: for valid
join order one must be able to:
1. write down the used tables in the join order on one line.
- 2. for each nested join, put one '(' and one ')' on the said line
+ 2. for each nested join, put one '(' and one ')' on the said line
3. write "LEFT JOIN" and "ON (...)" where appropriate
4. get a query equivalent to the query we're trying to execute.
@@ -9604,7 +9893,7 @@ sub_select_cache(JOIN *join,JOIN_TAB *jo
/*
Retrieve records ends with a given beginning from the result of a join
- SYNPOSIS
+ SYNOPSIS
sub_select()
join pointer to the structure providing all context info for the query
join_tab the first next table of the execution plan to be retrieved
@@ -10370,6 +10659,21 @@ join_init_quick_read_record(JOIN_TAB *ta
}
+/*
+ Perform range optimization during execution for each new outer record.
+
+ SYNOPSIS
+ tab current plan node
+
+ DESCRIPTION
+ TODO
+
+ RETURN
+ -1 if impossible select (i.e. certainly no rows will be selected)
+ 0 if can't use quick_select
+ 1 if found usable ranges and quick select has been successfully created.
+*/
+
static int
test_if_quick_select(JOIN_TAB *tab)
{
@@ -12115,10 +12419,10 @@ join_init_cache(THD *thd,JOIN_TAB *table
cache->length=length+blobs*sizeof(char*);
cache->blobs=blobs;
- *blob_ptr=0; /* End sequentel */
+ *blob_ptr=0; /* End sequentel */
size=max(thd->variables.join_buff_size, cache->length);
if (!(cache->buff=(uchar*) my_malloc(size,MYF(0))))
- DBUG_RETURN(1); /* Don't use cache */ /* purecov: inspected */
+ DBUG_RETURN(1); /* Don't use cache */ /* purecov: inspected */
cache->end=cache->buff+size;
reset_cache_write(cache);
DBUG_RETURN(0);
@@ -12681,9 +12985,26 @@ create_distinct_group(THD *thd, Item **r
}
-/*****************************************************************************
- Update join with count of the different type of fields
-*****************************************************************************/
+/*
+ Update TMP_TABLE_PARAM with count of the different type of fields.
+
+ SYNOPSIS
+ count_field_types()
+ param [out] parameter to create_tmp_table
+ fields [in] the fields of the temp table
+ reset_with_sum_func [in] if TRUE reset Field::with_sum_func
+
+ DESCRIPTION
+ Compute and update the following counters/members in 'param':
+ param->field_count
+ param->sum_func_count
+ param->func_count
+ param->hidden_field_count
+ param->quick_group
+
+ RETURN
+ None
+*/
void
count_field_types(TMP_TABLE_PARAM *param, List<Item> &fields,
@@ -13837,7 +14158,7 @@ int JOIN::rollup_write_data(uint idx, TA
clear results if there are not rows found for group
(end_send_group/end_write_group)
- SYNOPSYS
+ SYNOPSIS
JOIN::clear()
*/
@@ -13875,7 +14196,8 @@ static void select_describe(JOIN *join,
(ulong)join->select_lex, join->select_lex->type,
message ? message : "NULL"));
/* Don't log this into the slow query log */
- thd->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
+ thd->server_status&= ~(SERVER_QUERY_NO_INDEX_USED |
+ SERVER_QUERY_NO_GOOD_INDEX_USED);
join->unit->offset_limit_cnt= 0;
/*
--- 1.108/sql/sql_select.h 2006-06-18 13:20:28 +03:00
+++ 1.109/sql/sql_select.h 2006-06-27 19:45:05 +03:00
@@ -24,12 +24,79 @@
#include "procedure.h"
#include <myisam.h>
+
+/*
+ A KEYUSE represents an equality condition of the form (table.field = val),
+ where the field is indexed by 'keypart' in 'key', and 'val' is either a
+ constant, a field from other table, or an expression over field(s) from
+ other table(s). If 'val' is not a constant, then the KEYUSE specifies an
+ equi-join condition, and 'table' must be put in the join plan after all
+ tables in 'used_tables'.
+
+ At an abstract level a KEYUSE instance can be viewed as a directed arc
+ of an equi-join graph, where the arc originates from the table(s)
+ containing the column(s) that produce the values used for index lookup
+ into 'table', and the arc points into 'table'.
+
+ For instance, assuming there t1-- a ->- c ---
+ is only an index t3(c), the query: |
+ SELECT * FROM t1,t2,t3 V
+ WHERE t1.a = t3.c AND t3
+ t2.b = t3.c; ^
+ would generate two arcs |
+ (instances of KEYUSE): t2-- b ->- c --
+
+ If there were indexes t1(a), and t2(b), then the equi-join graph
+ would have two additional arcs "c->a" and "c->b" recording the fact
+ that it is possible to perform lookup in either direction.
+
+ t1-- a ->- c --- --- c -<- b --- t2
+ ^ | | ^
+ | | | |
+ -- a -<- c - v v-- c ->- b ----|
+ t3
+ The query:
+ SELECT * FROM t1,t2,t3 WHERE t1.a+t2.b = t3.c;
+ can be viewed as a graph with one "multi-source" arc:
+
+ t1-- a ---
+ |
+ --- c --> t3
+ |
+ t2-- b ---
+
+ The graph of all equi-join conditions usable for index lookup is stored
+ as an ordered sequence of KEYUSE elements sorted by table, key, keypart,
+ and stored in JOIN::keuse. Each JOIN_TAB::keyuse points to the first
+ array element with the same table.
+*/
+
typedef struct keyuse_t {
+ /*
+ Table into which we perform the lookup via 'key' with value 'val'.
+ */
TABLE *table;
- Item *val; /* or value if no field */
+ /*
+ Value used for lookup into 'key'. It may be an Item_field, a
+ constant or any other expression. If 'val' contains a field from
+ another table, then we have a join condition, and the table(s) of
+ the field(s) in 'val' should be before 'table' in the join plan.
+ */
+ Item *val;
+ /*
+ All tables used in 'val', that is all tables that provide bindings
+ for the expression 'val'. These tables must be in the plan before
+ executing the equi-join described by a KEYUSE.
+ */
table_map used_tables;
- uint key, keypart, optimize;
- key_part_map keypart_map;
+ /* Index and key part of table used for look up. */
+ uint key, keypart;
+ uint optimize; /* TODO: what is the meaning of this member? */
+ key_part_map keypart_map; /* Position 'keypart' set to TRUE. */
+ /*
+ Total rows (most likely) matched by the equi-join condition:
+ (table.field = val)
+ */
ha_rows ref_table_rows;
/*
If true, the comparison this value was created from will not be
@@ -82,9 +149,17 @@ typedef struct st_join_cache {
} JOIN_CACHE;
+/****************************************************************************
+ * Strucutres that represent query plan nodes, and partial and complete
+ * query plans used during query optimization and execution.
+ *****************************************************************************/
+
/*
- The structs which holds the join connections and join states
+ Types of data access methods (table or index access). Depending on the
+ chosen 'type', we get different flavors (join types) of the basic nested
+ loops join algorithm.
*/
+
enum join_type { JT_UNKNOWN,JT_SYSTEM,JT_CONST,JT_EQ_REF,JT_REF,JT_MAYBE_REF,
JT_ALL, JT_RANGE, JT_NEXT, JT_FT, JT_REF_OR_NULL,
JT_UNIQUE_SUBQUERY, JT_INDEX_SUBQUERY, JT_INDEX_MERGE};
@@ -104,6 +179,19 @@ typedef int (*Read_record_func)(struct s
Next_select_func setup_end_select_func(JOIN *join);
+/*
+ Query plan node.
+
+ If the operation is the first one in a query plan, then it specifies
+ a table retrieval operation from 'table'. A plan node at any other position
+ after the first one specifies a table retrieval operation from 'table'
+ and a join between the result of the previous plan nodes, and the
+ retrieved tuples from 'table'.
+
+ TODO:
+ Add detailed description once agreed upon terminology.
+*/
+
typedef struct st_join_table {
st_join_table() {} /* Remove gcc warning */
TABLE *table;
@@ -123,16 +211,43 @@ typedef struct st_join_table {
Read_record_func read_first_record;
Next_select_func next_select;
READ_RECORD read_record;
- double worst_seeks;
- key_map const_keys; /* Keys with constant part */
- key_map checked_keys; /* Keys checked in find_best */
+
+ /*
+ Keys with SARGable conditions (constant <op> key_field). These are the
+ candidate keys considered by the ref and range optimizers.
+ */
+ key_map const_keys;
+ /*
+ TODO: Keys set in update_ref_and_keys(), used after optimization in
+ make_join_select(). Can be removed.
+ */
+ key_map checked_keys;
key_map needed_reg;
- key_map keys; /* all keys with can be used */
- ha_rows records,found_records,read_time;
+ key_map keys; /* all keys that can be used */
+
+ /*
+ Cost information for the plan node.
+ */
+ /* Estimated # of scanned records = either |table| or 1 if const table. */
+ ha_rows records;
+ /* Estimated # of result records returned by the best table access method. */
+ ha_rows found_records;
+ /*
+ Cost to compute the result records. TODO: does it include CPU cost of the
+ WHERE clause?
+ */
+ ha_rows read_time;
+ double worst_seeks; /* Upper bound for extreme cost values. */
+
table_map dependent,key_dependent;
uint use_quick,index;
uint status; // Save status for cache
uint used_fields,used_fieldlength,used_blobs;
+ /*
+ Access method to the data in 'table'. In some cases also describes a
+ variation of the join algorithm (e.g. index-nested loops join if
+ JT_EQ_REF).
+ */
enum join_type type;
bool cached_eq_ref_table,eq_ref_table,not_used_in_distinct;
bool sorted;
@@ -157,11 +272,35 @@ enum_nested_loop_state sub_select(JOIN *
end_of_records);
-typedef struct st_position /* Used in find_best */
+/*
+ A POSITION describes one operation in a join plan with its cost and
+ index lookup information. This structure is used only during cost-based
+ optimization (sql_select.cc:make_join_statistics()) for the purpose of
+ reordering the joined tables. Once an optimal order is found, the
+ corresponding plan is copied into JOIN::join_tab.
+
+ TODO:
+ This structure can be merged with JON_TAB and removed. Plans can be
+ reordered by numbering each plan operator and reordering arrays of integers.
+*/
+
+typedef struct st_position
{
+ /*
+ The number of result records selected from 'table' by the select operation
+ executed at this position. That is:
+ records_read = selectivity(access_condition) * cardinality(table)
+ where 'access_condition' is whatever condition was chosen for index
+ access, depending on the access method ('ref', 'range', etc.)
+ */
double records_read;
- double read_time;
- JOIN_TAB *table;
+ double read_time; /* The cost to read and filter the data. */
+ JOIN_TAB *table; /* Table being read. */
+ /*
+ Key parts that participate in equality or equi-join conditions
+ that can be used for lookup via 'ref' or 'eq_ref'.
+ TODO: check if this is a duplicate of table->keyuse and remove if so.
+ */
KEYUSE *key;
} POSITION;
@@ -175,15 +314,33 @@ typedef struct st_rollup
} ROLLUP;
+/*
+ Query execution plan and context for a query.
+*/
+
class JOIN :public Sql_alloc
{
JOIN(const JOIN &rhs); /* not implemented */
JOIN& operator=(const JOIN &rhs); /* not implemented */
public:
- JOIN_TAB *join_tab,**best_ref;
+ /*
+ Optimal query execution plan. Allocated by get_best_combination(), and
+ initialized from JOIN::best_positions (see below) after optimization.
+ */
+ JOIN_TAB *join_tab;
+ /*
+ Array of plan operators representing the current (partial) best plan.
+ The array is allocated automatically in make_join_statistics() as
+ stat_vector[MAX_TABLES+1] and is valid only inside make_join_statistics().
+ Initially (*best_ref[i]) == join_tab[i]. The optimizer reorders best_ref.
+ */
+ JOIN_TAB **best_ref;
+
JOIN_TAB **map2table; // mapping between table indexes and JOIN_TABs
JOIN_TAB *join_tab_save; // saved join_tab for subquery reexecution
- TABLE **table,**all_tables,*sort_by_table;
+ TABLE **table; /* TODO: looks like it is a duplicate of 'all_tables'. */
+ TABLE **all_tables; /* TODO: looks like it is a duplicate of 'table'. */
+ TABLE *sort_by_table;
uint tables,const_tables;
uint send_group_parts;
bool sort_and_group,first_record,full_join,group, no_field_update;
@@ -205,7 +362,13 @@ public:
- on each fetch iteration we add num_rows to fetch to fetch_limit
*/
ha_rows fetch_limit;
- POSITION positions[MAX_TABLES+1],best_positions[MAX_TABLES+1];
+ /* Partial query plan during optimization. Updated at each plan extension. */
+ POSITION positions[MAX_TABLES+1];
+ /*
+ Current best complete query plan during optimization. After optimization
+ contains the optimal query plan.
+ */
+ POSITION best_positions[MAX_TABLES+1];
/*
Bitmap of nested joins embedding the position at the end of the current
@@ -256,6 +419,10 @@ public:
bool skip_sort_order;
bool need_tmp, hidden_group_fields;
+ /*
+ Key parts participating in equality conditions. These key parts can
+ be used for 'ref' or 'eq_ref' index access.
+ */
DYNAMIC_ARRAY keyuse;
Item::cond_result cond_value;
List<Item> all_fields; // to store all fields that used in query
| Thread |
|---|
| • bk commit into 5.1 tree (timour:1.2208) | timour | 27 Jun |
