Hi Sergey,
Here's what I've found.
Regards,
Igor.
Sergey Petrunia wrote:
> Below is the list of changes that have just been committed into a local
> 6.0 repository of sergefp. When sergefp 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, 2008-05-28 09:54:00+04:00, sergefp@stripped +9 -0
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Moved LooseScan functionality from READ_RECORD functions to join runtime.
> (This enables use of insideout together with range access)
> - Let best_access_path() save the number of the index to be used by the
> insideout scan and #keyparts (just keeping a flag wasn't enough for
> full-index insideout scans).
> - Made setup_semijoin_dups_elimination() define and use an enum instead
> of numeric constants.
>
> mysql-test/r/subselect_sj2.result@stripped, 2008-05-28 09:53:38+04:00,
> sergefp@stripped +27 -0
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Testcase
>
> mysql-test/t/subselect_sj2.test@stripped, 2008-05-28 09:53:38+04:00, sergefp@stripped
> +22 -0
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Testcase
>
> sql/handler.cc@stripped, 2008-05-28 09:53:38+04:00, sergefp@stripped +2 -3
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Move key_uses_partial_cols() out of class DsMrr_impl, it is now used
> otside of it, too.
>
> sql/handler.h@stripped, 2008-05-28 09:53:38+04:00, sergefp@stripped +1 -1
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Move key_uses_partial_cols() out of class DsMrr_impl, it is now used
> otside of it, too.
>
> sql/mysql_priv.h@stripped, 2008-05-28 09:53:38+04:00, sergefp@stripped +1 -0
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Added 'no_loosescan' to @@optimizer_switch
>
> sql/mysqld.cc@stripped, 2008-05-28 09:53:39+04:00, sergefp@stripped +3 -2
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Added 'no_loosescan' to @@optimizer_switch
>
> sql/sql_select.cc@stripped, 2008-05-28 09:53:39+04:00, sergefp@stripped +134 -132
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Moved LooseScan functionality from READ_RECORD functions to join runtime
> - Let best_access_path() save the number of the index to be used by the
> insideout scan and #keyparts (just keeping a flag wasn't enough for
> full-index insideout scans).
> - Made setup_semijoin_dups_elimination() define and use an enum instead
> of numeric constants.
>
> sql/sql_select.h@stripped, 2008-05-28 09:53:40+04:00, sergefp@stripped +19 -6
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Moved LooseScan functionality from READ_RECORD functions to join runtime
> - Let best_access_path() save insideout index and #keyparts.
>
> sql/structs.h@stripped, 2008-05-28 09:53:40+04:00, sergefp@stripped +0 -1
> BUG#35468: Slowdown and wrong result for uncorrelated subquery w/o where
> - Moved LooseScan functionality from READ_RECORD functions to join runtime
>
> diff -Nrup a/mysql-test/r/subselect_sj2.result b/mysql-test/r/subselect_sj2.result
> --- a/mysql-test/r/subselect_sj2.result 2008-05-03 12:27:40 +04:00
> +++ b/mysql-test/r/subselect_sj2.result 2008-05-28 09:53:38 +04:00
> @@ -654,3 +654,30 @@ call p1();
> a
> drop procedure p1;
> drop table t1;
> +create table t0 (a int);
> +insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
> +create table t1 (a int) as select A.a + 10 *(B.a + 10*C.a) as a from t0 A, t0 B, t0
> C;
> +create table t2 (id int, a int, primary key(id), key(a)) as select a as id, a as a
> from t1;
> +show create table t2;
> +Table Create Table
> +t2 CREATE TABLE `t2` (
> + `id` int(11) NOT NULL DEFAULT '0',
> + `a` int(11) DEFAULT NULL,
> + PRIMARY KEY (`id`),
> + KEY `a` (`a`)
> +) ENGINE=MyISAM DEFAULT CHARSET=latin1
> +set @a=0;
> +create table t3 as select * from t2 limit 0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +alter table t3 add primary key(id), add key(a);
> +The following must use loose index scan over t3, key a:
> +explain select count(a) from t2 where a in ( SELECT a FROM t3);
> +id select_type table type possible_keys key key_len ref rows Extra
> +1 PRIMARY t3 index a a 5 NULL 30000 Using index; LooseScan
> +1 PRIMARY t2 ref a a 5 test.t3.a 1 Using index
> +select count(a) from t2 where a in ( SELECT a FROM t3);
> +count(a)
> +1000
> +drop table t0,t1,t2,t3;
> diff -Nrup a/mysql-test/t/subselect_sj2.test b/mysql-test/t/subselect_sj2.test
> --- a/mysql-test/t/subselect_sj2.test 2008-05-03 12:27:40 +04:00
> +++ b/mysql-test/t/subselect_sj2.test 2008-05-28 09:53:38 +04:00
> @@ -837,3 +837,25 @@ delimiter ;|
> call p1();
> drop procedure p1;
> drop table t1;
> +
> +#
> +# BUG#35468 "Slowdown and wrong result for uncorrelated subquery w/o where"
> +#
> +
> +create table t0 (a int);
> +insert into t0 values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
> +create table t1 (a int) as select A.a + 10 *(B.a + 10*C.a) as a from t0 A, t0 B, t0
> C;
> +create table t2 (id int, a int, primary key(id), key(a)) as select a as id, a as a
> from t1;
> +show create table t2;
> +set @a=0;
> +create table t3 as select * from t2 limit 0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +insert into t3 select @a:=@a+1, t2.a from t2, t0;
> +
> +alter table t3 add primary key(id), add key(a);
> +--echo The following must use loose index scan over t3, key a:
> +explain select count(a) from t2 where a in ( SELECT a FROM t3);
> +select count(a) from t2 where a in ( SELECT a FROM t3);
> +
> +drop table t0,t1,t2,t3;
> diff -Nrup a/sql/handler.cc b/sql/handler.cc
> --- a/sql/handler.cc 2008-04-07 19:26:37 +04:00
> +++ b/sql/handler.cc 2008-05-28 09:53:38 +04:00
> @@ -4575,7 +4575,7 @@ ha_rows DsMrr_impl::dsmrr_info_const(uin
> @retval FALSE No
> */
>
> -bool DsMrr_impl::key_uses_partial_cols(uint keyno)
> +bool key_uses_partial_cols(TABLE *table, uint keyno)
> {
> KEY_PART_INFO *kp= table->key_info[keyno].key_part;
> KEY_PART_INFO *kp_end= kp + table->key_info[keyno].key_parts;
> @@ -4587,7 +4587,6 @@ bool DsMrr_impl::key_uses_partial_cols(u
> return FALSE;
> }
>
> -
> /**
> DS-MRR Internals: Choose between Default MRR implementation and DS-MRR
>
> @@ -4621,7 +4620,7 @@ bool DsMrr_impl::choose_mrr_impl(uint ke
> (*flags & HA_MRR_INDEX_ONLY) || (*flags & HA_MRR_SORTED) ||
> (keyno == table->s->primary_key &&
> h->primary_key_is_clustered()) ||
> - key_uses_partial_cols(keyno))
> + key_uses_partial_cols(table, keyno))
> {
> /* Use the default implementation */
> *flags |= HA_MRR_USE_DEFAULT_IMPL;
> diff -Nrup a/sql/handler.h b/sql/handler.h
> --- a/sql/handler.h 2008-04-14 14:09:57 +04:00
> +++ b/sql/handler.h 2008-05-28 09:53:38 +04:00
> @@ -2318,6 +2318,7 @@ private:
> };
>
>
> +bool key_uses_partial_cols(TABLE *table, uint keyno);
>
> /**
> A Disk-Sweep MRR interface implementation
> @@ -2378,7 +2379,6 @@ public:
> void *seq_init_param, uint n_ranges, uint *bufsz,
> uint *flags, COST_VECT *cost);
> private:
> - bool key_uses_partial_cols(uint keyno);
> bool choose_mrr_impl(uint keyno, ha_rows rows, uint *flags, uint *bufsz,
> COST_VECT *cost);
> bool get_disk_sweep_mrr_cost(uint keynr, ha_rows rows, uint flags,
> diff -Nrup a/sql/mysql_priv.h b/sql/mysql_priv.h
> --- a/sql/mysql_priv.h 2008-04-14 14:09:59 +04:00
> +++ b/sql/mysql_priv.h 2008-05-28 09:53:38 +04:00
> @@ -556,6 +556,7 @@ enum open_table_mode
> /* @@optimizer_switch flags */
> #define OPTIMIZER_SWITCH_NO_MATERIALIZATION 1
> #define OPTIMIZER_SWITCH_NO_SEMIJOIN 2
> +#define OPTIMIZER_SWITCH_NO_LOOSE_SCAN 4
>
>
> /*
> diff -Nrup a/sql/mysqld.cc b/sql/mysqld.cc
> --- a/sql/mysqld.cc 2008-04-21 11:30:29 +04:00
> +++ b/sql/mysqld.cc 2008-05-28 09:53:39 +04:00
> @@ -321,7 +321,7 @@ TYPELIB sql_mode_typelib= { array_elemen
>
> static const char *optimizer_switch_names[]=
> {
> - "no_materialization", "no_semijoin",
> + "no_materialization", "no_semijoin","no_loosescan",
<inssert space>
> NullS
> };
>
> @@ -329,7 +329,8 @@ static const char *optimizer_switch_name
> static const unsigned int optimizer_switch_names_len[]=
> {
> /*no_materialization*/ 19,
> - /*no_semijoin*/ 11
> + /*no_semijoin*/ 11,
> + /*no_loosescan*/ 12,
> };
>
> TYPELIB optimizer_switch_typelib= { array_elements(optimizer_switch_names)-1,"",
> diff -Nrup a/sql/sql_select.cc b/sql/sql_select.cc
> --- a/sql/sql_select.cc 2008-05-03 06:16:34 +04:00
> +++ b/sql/sql_select.cc 2008-05-28 09:53:39 +04:00
> @@ -156,13 +156,11 @@ static int join_read_always_key(JOIN_TAB
> static int join_read_last_key(JOIN_TAB *tab);
> static int join_no_more_records(READ_RECORD *info);
> static int join_read_next(READ_RECORD *info);
> -static int join_read_next_different(READ_RECORD *info);
> static int join_init_quick_read_record(JOIN_TAB *tab);
> static int test_if_quick_select(JOIN_TAB *tab);
> static int join_init_read_record(JOIN_TAB *tab);
> static int join_read_first(JOIN_TAB *tab);
> static int join_read_next_same(READ_RECORD *info);
> -static int join_read_next_same_diff(READ_RECORD *info);
> static int join_read_last(JOIN_TAB *tab);
> static int join_read_prev_same(READ_RECORD *info);
> static int join_read_prev(READ_RECORD *info);
> @@ -1042,6 +1040,12 @@ static
> int setup_semijoin_dups_elimination(JOIN *join, ulonglong options, uint
> no_jbuf_after)
> {
> table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
> + enum sj_strategy_enum {
> + SJ_STRATEGY_INVALID,
> + SJ_STRATEGY_INSIDEOUT,
> + SJ_STRATEGY_DUPS_WEEDOUT,
> + SJ_STRATEGY_DUPS_WEEDOUT_JBUF
> + };
> struct {
> /*
> 0 - invalid (EOF marker),
> @@ -1049,7 +1053,7 @@ int setup_semijoin_dups_elimination(JOIN
> 2 - Temptable (maybe confluent),
> 3 - Temptable with join buffering
> */
> - uint strategy;
> + enum sj_strategy_enum strategy;
> uint start_idx; /* Left range bound */
> uint end_idx; /* Right range bound */
> /*
> @@ -1073,7 +1077,7 @@ int setup_semijoin_dups_elimination(JOIN
> /*
> First pass: locate the duplicate-generating ranges and pick the strategies.
> */
> - for (i=join->const_tables ; i < join->tables ; i++)
> + for (i= join->const_tables ; i < join->tables ; i++)
> {
> JOIN_TAB *tab=join->join_tab+i;
> TABLE *table=tab->table;
> @@ -1091,7 +1095,7 @@ int setup_semijoin_dups_elimination(JOIN
> be that it overlaps with anther semi-join's range. we don't
> support InsideOut for joined ranges)
> */
> - if (join->best_positions[i].use_insideout_scan)
> + if (join->best_positions[i].insideout_key != MAX_KEY)
> emb_insideout_nest= tab->emb_sj_nest;
> }
>
> @@ -1161,7 +1165,7 @@ int setup_semijoin_dups_elimination(JOIN
> bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
> {
> /* Save that this range is handled with InsideOut: */
> - dups_ranges[cur_range].strategy= 1;
> + dups_ranges[cur_range].strategy= SJ_STRATEGY_INSIDEOUT;
> end_of_range= TRUE;
> }
> else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
> @@ -1170,7 +1174,9 @@ int setup_semijoin_dups_elimination(JOIN
> This is a complete range to be handled with either DuplicateWeedout
> or FirstMatch
> */
> - dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
> + dups_ranges[cur_range].strategy=
> + dealing_with_jbuf? SJ_STRATEGY_DUPS_WEEDOUT_JBUF:
> + SJ_STRATEGY_DUPS_WEEDOUT;
> /*
> This will hold tables from within the range that need to be put
> into the join buffer before we can use the FirstMatch on its tail.
> @@ -1186,7 +1192,7 @@ int setup_semijoin_dups_elimination(JOIN
> emb_sj_map= emb_outer_tables= 0;
> emb_insideout_nest= NULL;
> dealing_with_jbuf= FALSE;
> - dups_ranges[++cur_range].strategy= 0;
> + dups_ranges[++cur_range].strategy= SJ_STRATEGY_INVALID;
> }
> else
> {
> @@ -1200,18 +1206,27 @@ int setup_semijoin_dups_elimination(JOIN
> THD *thd= join->thd;
> SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
> /*
> - Second pass: setup the chosen strategies
> + The second pass: setup the chosen strategies
> */
> for (int j= 0; j < cur_range; j++)
> {
> JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
> JOIN_TAB *jump_to;
> - if (dups_ranges[j].strategy == 1) // InsideOut strategy
> + if (dups_ranges[j].strategy == SJ_STRATEGY_INSIDEOUT)
> {
> + /* We jump from the last table to the first one */
> tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
> +
> + /* Calculate key length */
> + uint nparts= join->positions[dups_ranges[j].start_idx].insideout_parts;
> + uint keyno= join->positions[dups_ranges[j].start_idx].insideout_key;
> + uint keylen= 0;
> + for (uint kp=0; kp < nparts; kp++)
> + keylen += tab->table->key_info[keyno].key_part[kp].store_length;
> + tab->insideout_key_len= keylen;
> jump_to= tab++;
> }
> - else // DuplicateWeedout strategy
> + else // DuplicateWeedout or FirstMatch
> {
> SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
> table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
> @@ -5381,7 +5396,12 @@ best_access_path(JOIN *join,
> table_map best_ref_depends_map= 0;
> double tmp;
> ha_rows rec;
> - uint best_is_sj_inside_out= 0;
> + uint best_is_sj_inside_out= MAX_KEY;
> + uint best_sj_keyparts;
> + bool try_sj_inside_out= FALSE;
> + uint sj_insideout_quick_select= 0; // 0=can't use, 1= consider, 2= use
> + uint sj_insideout_quick_max_sj_keypart;
> + uint sj_inside_out_scan= MAX_KEY;
> DBUG_ENTER("best_access_path");
>
> if (s->keyuse)
> @@ -5391,14 +5411,13 @@ best_access_path(JOIN *join,
> double best_records= DBL_MAX;
> uint max_key_part=0;
> ulonglong bound_sj_equalities= 0;
> - bool try_sj_inside_out= FALSE;
> /*
> Discover the bound equalites. We need to do this, if
> 1. The next table is an SJ-inner table, and
> 2. It is the first table from that semijoin, and
> 3. We're not within a semi-join range (i.e. all semi-joins either have
> all or none of their tables in join_table_map), except
> - s->emb_sj_nest (which we've just entered).
> + s->emb_sj_nest (which we've just entered, see #2).
> 4. All non-IN-equality correlation references from this sj-nest are
> bound
> 5. But some of the IN-equalities aren't (so this can't be handled by
> @@ -5411,12 +5430,17 @@ best_access_path(JOIN *join,
> join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables
> && // (3)
> !(remaining_tables &
> s->emb_sj_nest->nested_join->sj_corr_tables) &&
> // (4)
> - remaining_tables & s->emb_sj_nest->nested_join->sj_depends_on)
> // (5)
> + remaining_tables & s->emb_sj_nest->nested_join->sj_depends_on
> &&// (5)
> + !test(thd->variables.optimizer_switch &
> OPTIMIZER_SWITCH_NO_LOOSE_SCAN))
> {
> /* This table is an InsideOut scan candidate */
> bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
> remaining_tables);
> try_sj_inside_out= TRUE;
> + if (s->quick && s->quick->get_type() ==
> QUICK_SELECT_I::QS_TYPE_RANGE)
> + sj_insideout_quick_select= 1;
> + DBUG_PRINT("info", ("Will try InsideOut scan, bound_map=%llx",
> + (longlong)bound_sj_equalities));
> }
>
> /* Test how we can use keys */
> @@ -5437,6 +5461,9 @@ best_access_path(JOIN *join,
> start_key= keyuse;
> ulonglong handled_sj_equalities=0;
> key_part_map sj_insideout_map= 0;
> + uint max_sj_keypart= 0;
> + DBUG_PRINT("info", ("Considering ref access on key %s",
> + keyuse->table->key_info[keyuse->key].name));
>
> do /* For each keypart */
> {
> @@ -5484,6 +5511,7 @@ best_access_path(JOIN *join,
> {
> handled_sj_equalities |= 1ULL << keyuse->sj_pred_no;
> sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
> + set_if_bigger(max_sj_keypart, keyuse->keypart);
> }
> }
>
> @@ -5502,7 +5530,7 @@ best_access_path(JOIN *join,
> if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
> rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
>
> - bool sj_inside_out_scan= FALSE;
> + sj_inside_out_scan= MAX_KEY;
> /*
> ft-keys require special treatment
> */
> @@ -5519,49 +5547,65 @@ best_access_path(JOIN *join,
> {
> found_constraint= 1;
> /*
> - Check if InsideOut scan is applicable:
> - 1. All IN-equalities are either "bound" or "handled"
> - 2. Index keyparts are
> - ...
> + Check if we can use InsideOut semi-join strategy. We can if
> + 1. This is the right table at right location
> + 2. All IN-equalities are either
> + - "bound", ie. the outer_expr part refers to the preceding tables
> + - "handled", ie. covered by the index we're considering
> + 3. Index order allows to enumerate subquery's duplicate groups in
> + order. This happens when the index definition matches this
> + pattern:
> +
> + (handled_col|bound_col)* (other_col|bound_col)
> +
> */
> - if (try_sj_inside_out &&
> - table->covering_keys.is_set(key) &&
> - (handled_sj_equalities | bound_sj_equalities) == // (1)
> - PREV_BITS(ulonglong, s->emb_sj_nest->sj_in_exprs)) // (1)
> - {
> - uint n_fixed_parts= max_part_bit(found_part);
> - if (n_fixed_parts != keyinfo->key_parts &&
> - (PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
> - PREV_BITS(uint, keyinfo->key_parts))
> + if (try_sj_inside_out && // (1)
> + (handled_sj_equalities | bound_sj_equalities) == // (2)
> + PREV_BITS(ulonglong, s->emb_sj_nest->sj_in_exprs) && //
> (2)
> + (PREV_BITS(key_part_map, max_sj_keypart+1)) & // (3)
<del> ')'
> + (found_part | sj_insideout_map) == // (3)
)
> + (found_part | sj_insideout_map) && // (3)
> + !key_uses_partial_cols(s->table, key))
> + {
> + /* Ok, can use the strategy */
> + sj_inside_out_scan= key;
> + if (sj_insideout_quick_select == 1 && s->quick->index ==
> key)
^please introduce mnemonic
constants here and other related contexts.
> {
> - /*
> - Not all parts are fixed. Produce bitmap of remaining bits and
> - check if all of them are covered.
> - */
> - sj_inside_out_scan= TRUE;
> - DBUG_PRINT("info", ("Using sj InsideOut scan"));
> - if (!n_fixed_parts)
> - {
> - /*
> - It's a confluent ref scan.
> -
> - That is, all found KEYUSE elements refer to IN-equalities,
> - and there is really no ref access because there is no
> - t.keypart0 = {bound expression}
> + sj_insideout_quick_select= 2;
> + sj_insideout_quick_max_sj_keypart= max_sj_keypart;
> + }
> + DBUG_PRINT("info", ("Can use InsideOut scan"));
>
> - Calculate the cost of complete loose index scan.
> - */
> - records= (double)s->table->file->stats.records;
> + /*
> + Check if this is a confluent where there are no usable bound
> + IN-equalities, e.g. we have
> +
> + outer_expr IN (SELECT innertbl.key FROM ...)
> +
> + and outer_expr cannot be evaluated yet, so it's actually full
> + index scan and not a ref access
> + */
> + if (!(found_part & 1 ) && /* no usable ref access for 1st key
> part */
> + table->covering_keys.is_set(key))
> + {
> + DBUG_PRINT("info", ("Can use full index scan for InsideOut"));
> + /* Calculate the cost of complete loose index scan. */
> + records= rows2double(s->table->file->stats.records);
>
> - /* The cost is entire index scan cost (divided by 2) */
> - best_time= s->table->file->index_only_read_time(key,
> records);
> + /* The cost is entire index scan cost (divided by 2) */
> + best_time= s->table->file->index_only_read_time(key, records);
>
> - /* Now figure how many different keys we will get */
> - ulong rpc;
> - if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
> - records= records / rpc;
> - start_key= NULL;
> - }
> + /*
> + Now figure how many different keys we will get (for now we
^out
> + ignore the fact that we have "keypart_i=const" restriction for
> + some key components, that may make us think think that loose
> + scan will produce more distinct records than it actually will)
> + */
> + ulong rpc;
> + if ((rpc= keyinfo->rec_per_key[max_sj_keypart]))
> + records= records / rpc;
> + start_key= NULL;
> + /* Fall through */
> }
> }
>
> @@ -5816,7 +5860,7 @@ best_access_path(JOIN *join,
> tmp= best_time; // Do nothing
> }
>
> - if (sj_inside_out_scan && !start_key)
> + if ((sj_inside_out_scan != MAX_KEY) && !start_key)
> {
> tmp= tmp/2;
> if (records)
> @@ -5833,8 +5877,9 @@ best_access_path(JOIN *join,
> best_max_key_part= max_key_part;
> best_ref_depends_map= found_ref;
> best_is_sj_inside_out= sj_inside_out_scan;
> + best_sj_keyparts= max_sj_keypart;
> }
> - }
> + } /* for each key */
> records= best_records;
> }
>
> @@ -5873,6 +5918,7 @@ best_access_path(JOIN *join,
> ! s->table->covering_keys.is_clear_all() && best_key
> && !s->quick) &&// (3)
> !(s->table->force_index && best_key && !s->quick))
> // (4)
> { // Check full join
> + sj_inside_out_scan= MAX_KEY;
> ha_rows rnd_records= s->found_records;
> /*
> If there is a filtering condition on the table (i.e. ref analyzer found
> @@ -5912,6 +5958,11 @@ best_access_path(JOIN *join,
> tmp= record_count *
> (s->quick->read_time +
> (s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
> +
> + if (sj_insideout_quick_select == 2 && idx == join->const_tables)
> + {
> + sj_inside_out_scan= s->quick->index;
> + }
> }
> else
> {
> @@ -5963,7 +6014,8 @@ best_access_path(JOIN *join,
> best_key= 0;
> /* range/index_merge/ALL/index access method are "independent", so: */
> best_ref_depends_map= 0;
> - best_is_sj_inside_out= FALSE;
> + best_is_sj_inside_out= sj_inside_out_scan;
> + best_sj_keyparts= sj_insideout_quick_max_sj_keypart;
> }
> }
>
> @@ -5973,7 +6025,8 @@ best_access_path(JOIN *join,
> join->positions[idx].key= best_key;
> join->positions[idx].table= s;
> join->positions[idx].ref_depend_map= best_ref_depends_map;
> - join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
> + join->positions[idx].insideout_key= best_is_sj_inside_out;
> + join->positions[idx].insideout_parts= best_sj_keyparts + 1;
>
> if (!best_key &&
> idx == join->const_tables &&
> @@ -6916,7 +6969,7 @@ get_best_combination(JOIN *join)
> DBUG_PRINT("info",("type: %d", j->type));
> if (j->type == JT_CONST)
> continue; // Handled in make_join_stat..
> -
> + j->insideout_match_tab= NULL;
> j->ref.key = -1;
> j->ref.key_parts=0;
>
> @@ -6925,6 +6978,7 @@ get_best_combination(JOIN *join)
> if (j->keys.is_clear_all() || !(keyuse=
> join->best_positions[tablenr].key))
> {
> j->type=JT_ALL;
> + j->index= join->best_positions[tablenr].insideout_key;
> if (tablenr != join->const_tables)
> join->full_join=1;
> }
> @@ -7219,6 +7273,7 @@ make_simple_join(JOIN *join,TABLE *tmp_t
> join_tab->ref.key_parts= 0;
> join_tab->flush_weedout_table= join_tab->check_weed_out_table= NULL;
> join_tab->do_firstmatch= NULL;
> + join_tab->insideout_match_tab= NULL;
> bzero((char*) &join_tab->read_record,sizeof(join_tab->read_record));
> tmp_table->status=0;
> tmp_table->null_row=0;
> @@ -8252,9 +8307,8 @@ make_join_readinfo(JOIN *join, ulonglong
> sorted= 0; // only first must be sorted
> if (tab->insideout_match_tab)
> {
> - if (!(tab->insideout_buf=
> (uchar*)join->thd->alloc(tab->table->key_info
> - [tab->index].
> - key_length)))
> + if (!(tab->insideout_buf=
> + (uchar*)join->thd->alloc(tab->insideout_key_len)))
> return TRUE;
> }
> switch (tab->type) {
> @@ -8315,8 +8369,7 @@ make_join_readinfo(JOIN *join, ulonglong
> if (tab->type == JT_REF)
> {
> tab->read_first_record= join_read_always_key;
> - tab->read_record.read_record= tab->insideout_match_tab?
> - join_read_next_same_diff : join_read_next_same;
> + tab->read_record.read_record= join_read_next_same;
> }
> else
> {
> @@ -13431,9 +13484,25 @@ sub_select(JOIN *join,JOIN_TAB *join_tab
> Note: psergey has added the 2nd part of the following condition; the
> change should probably be made in 5.1, too.
> */
> + bool skip_over= FALSE;
> while (rc == NESTED_LOOP_OK && join->return_tab >= join_tab)
> {
> + if (join_tab->insideout_match_tab &&
> join_tab->insideout_match_tab->found_match)
> + {
> + KEY *key= join_tab->table->key_info + join_tab->index;
> + key_copy(join_tab->insideout_buf, info->record, key,
> + join_tab->insideout_key_len);
> + skip_over= TRUE;
> + }
> error= info->read_record(info);
> +
> + if (skip_over && !error &&
> + !key_cmp(join_tab->table->key_info[join_tab->index].key_part,
> + join_tab->insideout_buf, join_tab->insideout_key_len))
> + {
> + continue;
> + }
> +
> rc= evaluate_join_record(join, join_tab, error);
> }
>
> @@ -14160,37 +14229,6 @@ join_no_more_records(READ_RECORD *info _
> return -1;
> }
>
> -static int
> -join_read_next_same_diff(READ_RECORD *info)
> -{
> - TABLE *table= info->table;
> - JOIN_TAB *tab=table->reginfo.join_tab;
> - if (tab->insideout_match_tab->found_match)
> - {
> - KEY *key= tab->table->key_info + tab->index;
> - do
> - {
> - int error;
> - /* Save index tuple from record to the buffer */
> - key_copy(tab->insideout_buf, info->record, key, 0);
> -
> - if ((error=table->file->index_next_same(table->record[0],
> - tab->ref.key_buff,
> - tab->ref.key_length)))
> - {
> - if (error != HA_ERR_END_OF_FILE)
> - return report_error(table, error);
> - table->status= STATUS_GARBAGE;
> - return -1;
> - }
> - } while (!key_cmp(tab->table->key_info[tab->index].key_part,
> - tab->insideout_buf, key->key_length));
> - tab->insideout_match_tab->found_match= 0;
> - return 0;
> - }
> - else
> - return join_read_next_same(info);
> -}
>
> static int
> join_read_next_same(READ_RECORD *info)
> @@ -14287,17 +14325,7 @@ join_read_first(JOIN_TAB *tab)
> tab->read_record.file=table->file;
> tab->read_record.index=tab->index;
> tab->read_record.record=table->record[0];
> - if (tab->insideout_match_tab)
> - {
> - tab->read_record.do_insideout_scan= tab;
> - tab->read_record.read_record=join_read_next_different;
> - tab->insideout_match_tab->found_match= 0;
> - }
> - else
> - {
> - tab->read_record.read_record=join_read_next;
> - tab->read_record.do_insideout_scan= 0;
> - }
> + tab->read_record.read_record=join_read_next;
>
> if (!table->file->inited)
> table->file->ha_index_init(tab->index, tab->sorted);
> @@ -14308,32 +14336,6 @@ join_read_first(JOIN_TAB *tab)
> return -1;
> }
> return 0;
> -}
> -
> -
> -static int
> -join_read_next_different(READ_RECORD *info)
> -{
> - JOIN_TAB *tab= info->do_insideout_scan;
> - if (tab->insideout_match_tab->found_match)
> - {
> - KEY *key= tab->table->key_info + tab->index;
> - do
> - {
> - int error;
> - /* Save index tuple from record to the buffer */
> - key_copy(tab->insideout_buf, info->record, key, 0);
> -
> - if ((error=info->file->index_next(info->record)))
> - return report_error(info->table, error);
> -
> - } while (!key_cmp(tab->table->key_info[tab->index].key_part,
> - tab->insideout_buf, key->key_length));
> - tab->insideout_match_tab->found_match= 0;
> - return 0;
> - }
> - else
> - return join_read_next(info);
> }
>
>
> diff -Nrup a/sql/sql_select.h b/sql/sql_select.h
> --- a/sql/sql_select.h 2007-12-21 22:27:47 +03:00
> +++ b/sql/sql_select.h 2008-05-28 09:53:40 +04:00
> @@ -273,13 +273,18 @@ typedef struct st_join_table {
> struct st_join_table *do_firstmatch;
>
> /*
> - ptr - this join tab should do an InsideOut scan. Points
> - to the tab for which we'll need to check tab->found_match.
> -
> + ptr - We're doing and InsideOut scan, and this is the first (aka
> + "driving" join tab). ptr to the last tab, for which we'll need
> + to check tab->found_match to see if the current value group had
> + a match.
> NULL - Not an insideout scan.
> */
> struct st_join_table *insideout_match_tab;
> - uchar *insideout_buf; // Buffer to save index tuple to be able to skip dups
> + /* Buffer to save index tuple to be able to skip duplicates */
> + uchar *insideout_buf;
> +
> + /* How many key components to store in the above */
> + uint insideout_key_len;
>
> /* Used by InsideOut scan. Just set to true when have found a row. */
> bool found_match;
> @@ -349,8 +354,16 @@ typedef struct st_position
>
> /* If ref-based access is used: bitmap of tables this table depends on */
> table_map ref_depend_map;
> -
> - bool use_insideout_scan;
> +
> + /*
> + keyno - This is an insideout scan on this key. If keyuse is NULL then
> + this is a full index scan, otherwise this is a ref + insideout
> + scan (and keyno matches the KEUSE's)
> + MAX_KEY - This is not an InsideOut scan
> + */
> + uint insideout_key;
> + /* Number of key parts to be used by insideout */
> + uint insideout_parts;
> } POSITION;
>
>
> diff -Nrup a/sql/structs.h b/sql/structs.h
> --- a/sql/structs.h 2008-04-01 17:44:55 +04:00
> +++ b/sql/structs.h 2008-05-28 09:53:40 +04:00
> @@ -137,7 +137,6 @@ typedef struct st_read_record { /* Par
> uchar *cache,*cache_pos,*cache_end,*read_positions;
> IO_CACHE *io_cache;
> bool print_error, ignore_not_found_rows;
> - struct st_join_table *do_insideout_scan;
> } READ_RECORD;
>
>
>
