Below is the list of changes that have just been committed into a local
5.1 repository of psergey. When psergey 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-09-27 22:56:50+04:00, sergefp@stripped +4 -0
BUG#14940: Slow join order is chosen:
- Re-worked the prev_record_reads() function to return the lower bound of
number of different table access scans that will be performed.
mysql-test/r/join.result@stripped, 2006-09-27 22:56:47+04:00, sergefp@stripped +28 -0
BUG#14940: testcase
mysql-test/t/join.test@stripped, 2006-09-27 22:56:47+04:00, sergefp@stripped +21 -0
BUG#14940: testcase
sql/sql_select.cc@stripped, 2006-09-27 22:56:47+04:00, sergefp@stripped +91 -11
BUG#14940: Slow join order is chosen:
- Re-worked the prev_record_reads() function to return the lower bound of
number of different table access scans that will be performed.
sql/sql_select.h@stripped, 2006-09-27 22:56:47+04:00, sergefp@stripped +14 -0
BUG#14940: Slow join order is chosen:
- Added comments in struct POSITION
- Added POSITION::ref_depend_map: bitmap of tables that the table access
method depends on.
# 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: sergefp
# Host: pylon.mylan
# Root: /home/psergey/mysql-5.1-bug14940-r10a
--- 1.430/sql/sql_select.cc 2006-09-27 22:56:55 +04:00
+++ 1.431/sql/sql_select.cc 2006-09-27 22:56:55 +04:00
@@ -70,7 +70,7 @@
static void find_best(JOIN *join,table_map rest_tables,uint index,
double record_count,double read_time);
static uint cache_record_length(JOIN *join,uint index);
-static double prev_record_reads(JOIN *join,table_map found_ref);
+static double prev_record_reads(JOIN *join, uint idx, table_map found_ref);
static bool get_best_combination(JOIN *join);
static store_key *get_store_key(THD *thd,
KEYUSE *keyuse, table_map used_tables,
@@ -3373,6 +3373,7 @@
join->positions[idx].table= table;
join->positions[idx].key=key;
join->positions[idx].records_read=1.0; /* This is a const table */
+ join->positions[idx].ref_depend_map= 0;
/* Move the const table as down as possible in best_ref */
JOIN_TAB **pos=join->best_ref+idx+1;
@@ -3430,6 +3431,7 @@
double best= DBL_MAX;
double best_time= DBL_MAX;
double records= DBL_MAX;
+ table_map best_ref_depends_map;
double tmp;
ha_rows rec;
@@ -3458,13 +3460,20 @@
/* Calculate how many key segments of the current key we can use */
start_key= keyuse;
- do
- { /* for each keypart */
+
+ do /* For each keypart */
+ {
uint keypart= keyuse->keypart;
table_map best_part_found_ref= 0;
double best_prev_record_reads= DBL_MAX;
- do
+
+ do /* For each way to access the keypart */
{
+
+ /*
+ if 1. expression doesn't refer to forward tables
+ 2. we won't get two ref-or-null's
+ */
if (!(remaining_tables & keyuse->used_tables) &&
!(ref_or_null_part && (keyuse->optimize &
KEY_OPTIMIZE_REF_OR_NULL)))
@@ -3472,8 +3481,9 @@
found_part|= keyuse->keypart_map;
if (!(keyuse->used_tables & ~join->const_table_map))
const_part|= keyuse->keypart_map;
- double tmp= prev_record_reads(join, (found_ref |
- keyuse->used_tables));
+
+ double tmp= prev_record_reads(join, idx, (found_ref |
+ keyuse->used_tables));
if (tmp < best_prev_record_reads)
{
best_part_found_ref= keyuse->used_tables;
@@ -3512,7 +3522,7 @@
Really, there should be records=0.0 (yes!)
but 1.0 would be probably safer
*/
- tmp= prev_record_reads(join, found_ref);
+ tmp= prev_record_reads(join, idx, found_ref);
records= 1.0;
}
else
@@ -3527,7 +3537,7 @@
max_key_part= (uint) ~0;
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
{
- tmp = prev_record_reads(join, found_ref);
+ tmp = prev_record_reads(join, idx, found_ref);
records=1.0;
}
else
@@ -3757,6 +3767,7 @@
best_records= records;
best_key= start_key;
best_max_key_part= max_key_part;
+ best_ref_depends_map= found_ref;
}
}
records= best_records;
@@ -3885,6 +3896,8 @@
best= tmp;
records= rows2double(rnd_records);
best_key= 0;
+ /* range/index_merge/ALL/index access method are "independent", so: */
+ best_ref_depends_map= 0;
}
}
@@ -3893,6 +3906,7 @@
join->positions[idx].read_time= best;
join->positions[idx].key= best_key;
join->positions[idx].table= s;
+ join->positions[idx].ref_depend_map= best_ref_depends_map;
if (!best_key &&
idx == join->const_tables &&
@@ -4660,17 +4674,81 @@
}
+/*
+ Get the number of different row combinations for given subset of join tables
+
+ SYNOPSIS
+ prev_record_reads()
+ join The join structure
+ found_ref Bitmap of tables in join->positions
+
+ DESCRIPTION
+ Get the number of different record combinations for given subset of join
+ tables.
+ This is used as follows: Suppose we have a table accessed with ref-based
+ method. The access depends on tables specified in bitmap found_ref.
+
+ We want to count only different table accesses. The assume two table
+ accesses are different if we can't definitely guarantee they are the
+ same. Example: consider a query
+
+ SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
+
+ And a join order:
+ t1, ref access on t1.key=c1
+ t2, ref access on t1.key=c2
+ t3, ref access on t3.key=t1.field
+
+ The number of [different] accesses are:
+ t1: 1 ref access scan
+ t2: #records_read(t1) ref access scans, 1 distinct scan.
+ t3: #records_read(t1) * #records_read(t2) ref access scans,
+ but only #records_read(t1) distinct ref access scans.
+
+ The reason for having this function (at least the latest version of it)
+ is: we need to account for buffering in join execution. e.g. border case:
+ if we have ref(const), or ref(expr) with small number of different
+ values of expr as a non-first table in the join, the access to this table
+ will likely go into disk cache and not require disk seeks.
+
+ At some point in the future we'll need a proper model (e.g. assume an LRU
+ disk cache of some size). For now we just count identical ref scans as
+ one.
+
+ RETURN
+ Expected number of row combinations
+*/
+
static double
-prev_record_reads(JOIN *join,table_map found_ref)
+prev_record_reads(JOIN *join, uint idx, table_map found_ref)
{
double found=1.0;
found_ref&= ~OUTER_REF_TABLE_BIT;
- for (POSITION *pos=join->positions ; found_ref ; pos++)
+ for (POSITION *pos=join->positions + idx - 1 ; pos!=join->positions - 1 ;
+ pos--)
{
if (pos->table->table->map & found_ref)
{
found_ref&= ~pos->table->table->map;
- found*=pos->records_read;
+ found_ref|= pos->ref_depend_map;
+ /*
+ For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
+ with no matching row we will get position[t2].records_read==0.
+ Actually the size of output is one null-complemented row, therefore
+ we will use value of 1 whenever we get records_read==0.
+
+ Note
+ - the above case can't occur if inner part of outer join has more
+ than one table: table with no matches will not be marked as const.
+
+ - Ideally we should add 1 to records_read for every possible null-
+ complemented row. We're not doing it because: 1. it will require
+ non-trivial code and add overhead. 2. The value of records_read
+ is an inprecise estimate and adding 1 (or, in the worst case,
+ #max_nested_outer_joins=64-1) will not make it any more precise.
+ */
+ if (pos->records_read)
+ found*= pos->records_read;
}
}
return found;
@@ -10242,6 +10320,7 @@
tab->info="const row not found";
/* Mark for EXPLAIN that the row was not found */
pos->records_read=0.0;
+ pos->ref_depend_map= 0;
if (!table->maybe_null || error > 0)
DBUG_RETURN(error);
}
@@ -10267,6 +10346,7 @@
tab->info="unique row not found";
/* Mark for EXPLAIN that the row was not found */
pos->records_read=0.0;
+ pos->ref_depend_map= 0;
if (!table->maybe_null || error > 0)
DBUG_RETURN(error);
}
--- 1.110/sql/sql_select.h 2006-09-27 22:56:55 +04:00
+++ 1.111/sql/sql_select.h 2006-09-27 22:56:55 +04:00
@@ -176,7 +176,13 @@
*/
typedef struct st_position
{
+ /*
+ Number of records we will retrieve from this table per each row
+ combination of previous tables.
+ PROD{over all positions}(pos[i]->records_read) = E(#rows in join output)
+ */
double records_read;
+
/*
Cost accessing the table in course of the entire complete join execution,
i.e. cost of one access method use (e.g. 'range' or 'ref' scan ) times
@@ -184,7 +190,15 @@
*/
double read_time;
JOIN_TAB *table;
+
+ /*
+ NULL - 'index' or 'range' or 'index_merge' or 'ALL' access is used.
+ Other - [eq_]ref[_or_null] access is used. Pointer to {t.keypart1 = expr}
+ */
KEYUSE *key;
+
+ /* If ref-based access is used: bitmap of tables this table depends on */
+ table_map ref_depend_map;
} POSITION;
--- 1.40/mysql-test/r/join.result 2006-09-27 22:56:55 +04:00
+++ 1.41/mysql-test/r/join.result 2006-09-27 22:56:55 +04:00
@@ -776,3 +776,31 @@
1 SIMPLE t2 ALL a,b NULL NULL NULL 1000 Using where
1 SIMPLE t3 ref b b 5 test.t2.b 1 Using where
drop table t1, t2, t3;
+create table t1 (a int);
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+create table t2 (a int, b int, primary key(a));
+insert into t2 select @v:=A.a+10*B.a, @v from t1 A, t1 B;
+explain select * from t1;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10
+show status like '%cost%';
+Variable_name Value
+Last_query_cost 4.016090
+select 'The cost of accessing t1 (dont care if it changes' '^';
+The cost of accessing t1 (dont care if it changes
+The cost of accessing t1 (dont care if it changes^
+select 'vv: Following query must use ALL(t1), eq_ref(A), eq_ref(B): vv' Z;
+Z
+vv: Following query must use ALL(t1), eq_ref(A), eq_ref(B): vv
+explain select * from t1, t2 A, t2 B where A.a = t1.a and B.a=A.b;
+id select_type table type possible_keys key key_len ref rows Extra
+1 SIMPLE t1 ALL NULL NULL NULL NULL 10
+1 SIMPLE A eq_ref PRIMARY PRIMARY 4 test.t1.a 1
+1 SIMPLE B eq_ref PRIMARY PRIMARY 4 test.A.b 1
+show status like '%cost%';
+Variable_name Value
+Last_query_cost 24.016090
+select '^^: The above should be ~= 20 + cost(select * from t1). Value less than 20 is an error' Z;
+Z
+^^: The above should be ~= 20 + cost(select * from t1). Value less than 20 is an error
+drop table t1, t2;
--- 1.34/mysql-test/t/join.test 2006-09-27 22:56:55 +04:00
+++ 1.35/mysql-test/t/join.test 2006-09-27 22:56:55 +04:00
@@ -609,3 +609,24 @@
drop table t1, t2, t3;
+# BUG#14940 {Wrong query plan is chosen because of odd results of
+# prev_record_reads() function }
+create table t1 (a int);
+insert into t1 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
+
+create table t2 (a int, b int, primary key(a));
+insert into t2 select @v:=A.a+10*B.a, @v from t1 A, t1 B;
+
+explain select * from t1;
+show status like '%cost%';
+select 'The cost of accessing t1 (dont care if it changes' '^';
+
+select 'vv: Following query must use ALL(t1), eq_ref(A), eq_ref(B): vv' Z;
+
+explain select * from t1, t2 A, t2 B where A.a = t1.a and B.a=A.b;
+show status like '%cost%';
+select '^^: The above should be ~= 20 + cost(select * from t1). Value less than 20 is an error' Z;
+
+
+
+drop table t1, t2;
| Thread |
|---|
| • bk commit into 5.1 tree (sergefp:1.2279) BUG#14940 | Sergey Petrunia | 27 Sep |
