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@stripped, 2006-07-13 16:39:26+03:00, timour@stripped +4 -0
Preparation for WL#2241 - One-pass hash-join
- Added comments to optimizer code
- Reformatted few statements so that lines are < 80 characters
- No code changes
sql/opt_range.h@stripped, 2006-07-13 16:39:24+03:00, timour@stripped +14 -0
Added comments to optimizer code.
sql/sql_class.h@stripped, 2006-07-13 16:39:24+03:00, timour@stripped +14 -3
Added comments to optimizer code.
sql/sql_select.cc@stripped, 2006-07-13 16:39:24+03:00, timour@stripped +387 -57
Added comments to optimizer code.
sql/sql_select.h@stripped, 2006-07-13 16:39:24+03:00, timour@stripped +191 -15
Added comments to 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-07-13 16:39:31 +03:00
+++ 1.62/sql/opt_range.h 2006-07-13 16:39:31 +03:00
@@ -675,6 +675,20 @@
List_iterator<QUICK_RANGE> rev_it;
};
+/*
+ This class represents a single-table access plan for a range or loose index
+ scan with all relevant cost information 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 cost information
+ for the chosen method and constructs a quick select 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 a table access method, which complicates
+ the query engine.
+*/
class SQL_SELECT :public Sql_alloc {
public:
--- 1.301/sql/sql_class.h 2006-07-13 16:39:31 +03:00
+++ 1.302/sql/sql_class.h 2006-07-13 16:39:31 +03:00
@@ -1635,9 +1635,14 @@
#include <myisam.h>
/*
- Param to create temporary tables when doing SELECT:s
+ Context with information used both when creating and using temporary tables.
+ Temporary tables created with the help of 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,11 @@
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 created
+ depending on the purpose of the table - grouping, duplicate elimination,
+ etc. There is at most one such index.
+ */
KEY *keyinfo;
ha_rows end_write_records;
uint field_count,sum_func_count,func_count;
@@ -1963,7 +1973,8 @@
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-07-13 16:39:31 +03:00
+++ 1.414/sql/sql_select.cc 2006-07-13 16:39:31 +03:00
@@ -536,10 +536,58 @@
/*
- global select optimisation.
- return 0 - success
- 1 - error
- error code saved in field 'error'
+ Global select optimization.
+
+ 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
+ * 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
+ - run one of: exhaustive/greedy/straight search
+ - choice of best access path between:
+ - independent access methods (the selection condition
+ does not reference other tables)
+ - dependent access methods (the selection
+ condition references columns in other tables)
+ 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 'JOIN::error'
*/
int
@@ -791,7 +839,7 @@
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 +1995,35 @@
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 number of result rows returned by the best quick select method.
+
+ SYNOPSIS
+ get_quick_record_count()
+ 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 or several of the 'keys' using the
+ conditions 'select->cond'. The range optimizer compares several different
+ types of quick select methods (range scan, index merge, loose index scan)
+ and selects the cheapest one.
+
+ 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'.
+ 0 - if impossible select (i.e. certainly no rows will be selected)
+ HA_POS_ERROR - cannot use quick select in this case
+*/
static ha_rows get_quick_record_count(THD *thd, SQL_SELECT *select,
TABLE *table,
@@ -1977,11 +2050,57 @@
/*
- 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 INOUT execution plan and context for the current SELECT
+ 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 conditions 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 one of 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 +2116,23 @@
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
KEYUSE *keyuse,*start_keyuse;
table_map outer_join=0;
+ /*
+ 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_TAB pointers. */
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 +2143,10 @@
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 +2178,17 @@
{
/* 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,12 +2218,20 @@
#else
const bool no_partitions_used= FALSE;
#endif
- if ((table->s->system || table->file->stats.records <= 1 ||
+ /*
+ (1) if the table is a system table, or has 1 or 0 records or is a
+ partitioned table, and
+ (2) is not dependent on an outer table, and
+ (3) the row count is exact, and
+ (4) it is not full-text searched
+ */
+ if ((table->s->system || table->file->stats.records <= 1 || /* 1 */
no_partitions_used) &&
- !s->dependent &&
- (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
- !table->fulltext_searched)
+ !s->dependent && /* 2 */
+ (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && /* 3 */
+ !table->fulltext_searched) /* 4 */
{
+ /* Mark the table as a constant table. */
set_position(join,const_count++,s,(KEYUSE*) 0);
}
}
@@ -2131,7 +2278,7 @@
~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 +2298,10 @@
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 constant tables can be found.
+ */
int ref_changed;
do
{
@@ -2348,19 +2498,57 @@
/*****************************************************************************
- 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 independent ref/eq_ref/ref_or_null 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 dependencies 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 separate 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 one of {'=', '<=>', 'IS [NOT] NULL', 'arg1 IN arg2'},
+ and 'val' can be either another field or an expression (including constants).
+
+ KEY_FIELDs are used to analyze fields that may potentially serve as
+ parts of keys for index lookup. If 'field' is part of an index, 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. May be empty if we have
+ KEY_FIELD{t.key=c1} AND KEY_FIELD{t.key=c2}.
+ */
+ 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 +3149,28 @@
}
+/*
+ Compare two keyuse elements.
+
+ SYNOPSIS
+ compare_keyuse()
+ 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 +3194,7 @@
/*
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 +3248,19 @@
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 +3390,22 @@
}
/*
- Update some values in keyuse for faster choose_plan() loop
+ Update some values in keyuse for faster choose_plan() loop.
+
+ SYNOPSIS
+ optimize_keyuse()
+ 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 +3433,12 @@
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 +3457,8 @@
SYNOPSIS
add_group_and_distinct_keys()
- join
- join_tab
+ join 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
@@ -3402,7 +3638,7 @@
rec= keyuse->ref_table_rows;
/*
If there is one 'key_column IS NULL' expression, we can
- use this ref_or_null optimisation of this field
+ use this ref_or_null optimization of this field
*/
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
ref_or_null_part |= keyuse->keypart_map;
@@ -3558,7 +3794,7 @@
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 +4621,8 @@
}
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 +4636,8 @@
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 +4820,25 @@
}
-/*****************************************************************************
- 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 execution plan and context for the current SELECT
+
+ 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
+ FALSE OK
+ TRUE out of memory error
+*/
static bool
get_best_combination(JOIN *join)
@@ -4640,6 +4894,28 @@
}
+/*
+ Create/init a 'ref' access method from a KEYUSE array for a given plan node.
+
+ SYNOPSIS
+ create_ref_for_key()
+ join execution plan and context for the current SELECT
+ j current plan operator
+ org_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
+ FALSE OK
+ TRUE Out of memory error
+*/
+
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
table_map used_tables)
{
@@ -4656,6 +4932,7 @@
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 +4946,8 @@
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 +5416,24 @@
}
+/*
+ Perform push-down analysis and adjust access methods after the analysis.
+
+ SYNOPSIS
+ make_join_select()
+ join execution plan and context for the current SELECT
+ select descriptor of single-table select
+ cond (optional) condition
+
+ DESCRIPTION
+ TODO
+
+ RETURN
+ FALSE OK
+ TRUE - if out of memory error
+ - if the WHERE condition is found to never be true
+*/
+
static bool
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
{
@@ -5613,7 +5907,8 @@
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 +5939,8 @@
}
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 +7920,7 @@
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 +9900,7 @@
/*
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 +10666,22 @@
}
+/*
+ Perform range optimization during execution for each new outer record.
+
+ SYNOPSIS
+ test_if_quick_select()
+ 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 +12427,10 @@
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 +12993,26 @@
}
-/*****************************************************************************
- 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 +14166,7 @@
clear results if there are not rows found for group
(end_send_group/end_write_group)
- SYNOPSYS
+ SYNOPSIS
JOIN::clear()
*/
@@ -13875,7 +14204,8 @@
(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-07-13 16:39:31 +03:00
+++ 1.109/sql/sql_select.h 2006-07-13 16:39:31 +03:00
@@ -24,12 +24,81 @@
#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 in JOIN::keuse. The elements in
+ this array are sorted by table, key, and keypart. 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;
+ /* Index and key part of table used for lookup. */
+ uint key, keypart;
+ /* A bitmap of KEY_OPTIMIZE_[EXISTS | REF_OR_NULL] bits. */
+ uint optimize;
+ /* The set of keyparts used for index lookup. */
key_part_map keypart_map;
+ /*
+ 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 +151,17 @@
} 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 +181,19 @@
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 +213,51 @@
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 records returned by the best independent 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;
+ /* Maximum number of disk seeks needed for one index lookup in ref access. */
+ double worst_seeks;
+
table_map dependent,key_dependent;
- uint use_quick,index;
+ /*
+ Dependency of quick select on table order.
+ '1' - quick select references one table, and can be anywhere in a plan.
+ '2' - quick select references more than one table and needs bindings from
+ previous tables in the plan.
+ */
+ uint use_quick;
+ uint 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 +282,34 @@
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. */
+ /*
+ Points inside join->keyuse to the first keypart of the key chosen for
+ 'ref' or 'eq_ref' or 'ref_or_null' index access method.
+ */
KEYUSE *key;
} POSITION;
@@ -175,15 +323,33 @@
} 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 +371,13 @@
- 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 +428,10 @@
bool skip_sort_order;
bool need_tmp, hidden_group_fields;
+ /*
+ Memory buffer for KEYUSE elements that specify the key parts to be
+ used for 'ref', 'eq_ref', 'ref_or_null' 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 | 13 Jul |
