maria-developers team mailing list archive
-
maria-developers team
-
Mailing list archive
-
Message #04116
Re: [Commits] Rev 2983: MWL#89 - Automatic merge with 5.3 in file:///home/tsk/mprog/src/5.3-mwl89-merge/
Hello Sergey,
Thank you for the review, you manged to spot a couple of real omissions/
problems with the implementation. I implemented or responded to all your
review suggestions except two. The two ones that I didn't implement are
marked with 'timour-todo'. All remaining replies are marked with 'timour:'.
We already discussed the two issues I didn't address this time. They
are not critical, but are time-consuming. I will add them to my todo for
the task to complete after completing the regression test.
The patch that addresses your review was merged with the latest 5.3 and
pushed into 5.3-mwl89. If you have no objections, I'd like to push to 5.3
ASAP. Specifically, please look at my change to sort_and_filter_keyuse().
Timour
On 05/16/2011 02:18 PM, Sergey Petrunya wrote:
Hi Timour,
Congratulations on having pushed MWL#89 into 5.3-main! This is quite an
achievement which really moves us forward.
I've been studying the new code and has got some feedback which I thought
I need to share. Please find the notes below, marked with 'psergey'.
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/filesort.cc 5.3-timours-wl/sql/filesort.cc
> > --- 5.3-timours-wl-clean/sql/filesort.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/filesort.cc 2011-05-11 20:08:50.000000000 +0100
> > @@ -612,10 +612,34 @@
> > }
> > DBUG_RETURN(HA_POS_ERROR); /* purecov: inspected */
> > }
> > +
> > + bool write_record= false;
> > if (error == 0)
> > + {
> > param->examined_rows++;
> > -
> > - if (error == 0 && (!select || select->skip_record(thd) > 0))
> > + if (select && select->cond)
> > + {
> > + /*
> > + If the condition 'select->cond' contains a subquery, restore the
> > + original read/write sets of the table 'sort_form' because when
> > + SQL_SELECT::skip_record evaluates this condition. it may include a
psergey:
- The last sentence doesn't parse, please fix.
timour:
I hope this is clearer:
If the condition 'select->cond' contains a subquery, this subquery
may be correlated to some field of table 'sort_form'. For simplicity
we treat every subquery in 'select->cond' as potentially correlated.
If 'select->cond' contains a subquery, restore the original read/write
sets of the table 'sort_form'.
- Why is the check done *for each record we enumerate*? Please move it outside
of the loop.
timour:
The reason the check is done inside the loop is because either before, or after
the check, but still inside the loop, some other code needed the original
read/write sets.
- I suspect that now, with Sanja's subquery code, each subquery has a list of
references it makes to outside, so this shortcut is not necessary (let's
discuss that on the next optimizer call)
timour-todo:
- Implement Item_subselect::register_field_in_read_map, using
class Item_subselect :public Item_result_field
{
List<Ref_to_outside> upper_refs;
}
- remove the current hack that resets the read set for each record
> > + correlated subquery predicate, such that some field in the subquery
> > + refers to 'sort_form'.
> > + */
> > + if (select->cond->with_subselect)
> > + sort_form->column_bitmaps_set(save_read_set, save_write_set,
> > + save_vcol_set);
> > + write_record= (select->skip_record(thd) > 0);
> > + if (select->cond->with_subselect)
> > + sort_form->column_bitmaps_set(&sort_form->tmp_set,
> > + &sort_form->tmp_set,
> > + &sort_form->tmp_set);
> > + }
> > + else
> > + write_record= true;
> > + }
> > +
> > + if (write_record)
> > {
> > if (idx == param->keys)
> > {
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/item_cmpfunc.cc 5.3-timours-wl/sql/item_cmpfunc.cc
> > --- 5.3-timours-wl-clean/sql/item_cmpfunc.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/item_cmpfunc.cc 2011-05-11 20:08:50.000000000 +0100
> > @@ -2072,6 +2072,18 @@
> > }
> >
> >
> > +bool Item_in_optimizer::is_expensive_processor(uchar *arg)
> > +{
> > + return args[1]->is_expensive_processor(arg);
> > +}
> > +
> > +
> > +bool Item_in_optimizer::is_expensive()
> > +{
> > + return args[1]->is_expensive();
> > +}
> > +
psergey: what about the cases when args[0] is expensive? It should either be
checked, or a comment here is needed with explanation why we don't need to check it.
timour:
Your suggestion seems reasonable. args[1] is the subquery wrapped by
Item_in_optimizer, and I have been focused on that one only. A recent bug from RQG
showed that there might be a subquery on the left side of an IN. There is hardly
any such example in the test suite. I changed is_expensive to be expensive if
either operand of IN is expensive, and all tests passed, so I'll keep it.
> > longlong Item_func_eq::val_int()
> > {
> > DBUG_ASSERT(fixed == 1);
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/item.h 5.3-timours-wl/sql/item.h
> > --- 5.3-timours-wl-clean/sql/item.h 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/item.h 2011-05-11 20:08:50.000000000 +0100
> > @@ -510,7 +521,7 @@
> > SUBSELECT_ITEM, ROW_ITEM, CACHE_ITEM, TYPE_HOLDER,
> > PARAM_ITEM, TRIGGER_FIELD_ITEM, DECIMAL_ITEM,
> > XPATH_NODESET, XPATH_NODESET_CMP,
> > - VIEW_FIXER_ITEM, EXPR_CACHE_ITEM};
> > + VIEW_FIXER_ITEM, EXPR_CACHE_ITEM, UNKNOWN_ITEM};
psergey: When I grep for UNKNOWN_ITEM, I find only this occurence. Why add it?
timour: This is not my code, it is part of a patch by Sanja:
revno: 2881
revision-id: sanja@xxxxxxxxxxxx-20110124113117-v3otndf9uu20p5n6
parent: timour@xxxxxxxxxxxx-20110118171555-xglvrq7nnwp71ua3
committer: sanja@xxxxxxxxxxxx
branch nick: work-maria-5.3-mwl89-valgrind
timestamp: Mon 2011-01-24 13:31:17 +0200
message:
Fix of problem with WHERE/HAVING consist of alone outer reference field by wrapping it.
The problem is that the change:
- virtual enum Type type() const =0;
+ virtual enum Type type() const { return UNKNOWN_ITEM; };
is gone now, I suppose some merge made it obsolete. Since a pure virtual
method is better, I'll just remove UNKNOWN_ITEM.
> >
> > enum cond_result { COND_UNDEF,COND_OK,COND_TRUE,COND_FALSE };
> >
...
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/item_subselect.cc 5.3-timours-wl/sql/item_subselect.cc
> > --- 5.3-timours-wl-clean/sql/item_subselect.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/item_subselect.cc 2011-05-11 20:08:50.000000000 +0100
...
> > @@ -1659,49 +1696,40 @@
> > {
> > if (!(new_having= new Item_func_trig_cond(new_having,
> > get_cond_guard(0))))
> > - DBUG_RETURN(RES_ERROR);
> > + DBUG_RETURN(true);
> > }
> > - new_having->name= (char*)in_having_cond;
> > - select_lex->having= join->having= new_having;
> > - select_lex->having_fix_field= 1;
> > -
> > - /*
> > - we do not check join->having->fixed, because comparison function
> > - (from func->create) can't be fixed after creation
> > - */
> > - tmp= join->having->fix_fields(thd, 0);
> > - select_lex->having_fix_field= 0;
> > - if (tmp)
> > - DBUG_RETURN(RES_ERROR);
> > +
> > + new_having->name= (char*) in_having_cond;
> > + if (fix_having(new_having, select_lex))
> > + DBUG_RETURN(true);
> > + *having_item= new_having;
> > }
> > else
> > - {
> > - // it is single select without tables => possible optimization
> > - // remove the dependence mark since the item is moved to upper
> > - // select and is not outer anymore.
> > - item->walk(&Item::remove_dependence_processor, 0,
> > - (uchar *) select_lex->outer_select());
> > - item= func->create(left_expr, item);
> > - // fix_field of item will be done in time of substituting
> > - substitution= item;
> > - have_to_be_excluded= 1;
> > - if (thd->lex->describe)
> > - {
> > - char warn_buff[MYSQL_ERRMSG_SIZE];
> > - sprintf(warn_buff, ER(ER_SELECT_REDUCED), select_lex->select_number);
> > - push_warning(thd, MYSQL_ERROR::WARN_LEVEL_NOTE,
> > - ER_SELECT_REDUCED, warn_buff);
> > - }
> > - DBUG_RETURN(RES_REDUCE);
> > - }
> > + DBUG_ASSERT(FALSE);
psergey: (one)
> > }
> > }
> >
> > - DBUG_RETURN(RES_OK);
> > + DBUG_RETURN(false);
psergey: (two). I think using both 'false' and 'FALSE' in the same patch is
too much. Please change to TRUE/FALSE since we have it everywhere else.
timour:
This is an artifact of my attemt to change less code. It should be 'false'.
We use 'false' is as many places. I don't see any reason for having
the defines TRUE/FALSE, and would rather remove them in all new code.
So fixed to lower case as is used elsewhere in the patch.
> > }
> >
> >
> > -Item_subselect::trans_res
> > +/**
> > + Wrap a multi-column IN/ALL/ANY subselect into an Item_in_optimizer.
> > +
> > + @param join Join object of the subquery (i.e. 'child' join).
> > +
> > + @details
> > + The subquery predicate is wrapped into an Item_in_optimizer. Later the query
> > + optimization phase chooses whether the subquery under the Item_in_optimizer
> > + will be further transformed into an equivalent correlated EXISTS by injecting
> > + additional predicates, or will be executed via subquery materialization in its
> > + unmodified form.
> > +
> > + @retval false The subquery was transformed
> > + @retval true Error
> > +*/
> > +
> > +bool
> > Item_in_subselect::row_value_transformer(JOIN *join)
> > {
> > SELECT_LEX *select_lex= join->select_lex;
...
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/opt_subselect.cc 5.3-timours-wl/sql/opt_subselect.cc
> > --- 5.3-timours-wl-clean/sql/opt_subselect.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/opt_subselect.cc 2011-05-11 20:08:50.000000000 +0100
> > @@ -175,63 +189,80 @@
> > else
> > {
> > DBUG_PRINT("info", ("Subquery can't be converted to semi-join"));
> > - /*
> > - Check if the subquery predicate can be executed via materialization.
> > - The required conditions are:
> > - 1. Subquery predicate is an IN/=ANY subq predicate
> > - 2. Subquery is a single SELECT (not a UNION)
> > - 3. Subquery is not a table-less query. In this case there is no
> > - point in materializing.
> > - 3A The upper query is not a table-less SELECT ... FROM DUAL. We
> > + /* Test if the user has set a legal combination of optimizer switches. */
> > + if (!optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS) &&
> > + !optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION))
> > + my_error(ER_ILLEGAL_SUBQUERY_OPTIMIZER_SWITCHES, MYF(0));
> > +
> > + if (in_subs)
> > + {
> > + /* Subquery predicate is an IN/=ANY predicate. */
> > + if (optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS))
> > + in_subs->in_strategy|= SUBS_IN_TO_EXISTS;
> > + if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION))
> > + in_subs->in_strategy|= SUBS_MATERIALIZATION;
> > +
> > + /*
> > + Check if the subquery predicate can be executed via materialization.
> > + The required conditions are:
> > + 1. Subquery is a single SELECT (not a UNION)
> > + 2. Subquery is not a table-less query. In this case there is no
> > + point in materializing.
> > + 2A The upper query is not a table-less SELECT ... FROM DUAL. We
> > can't do materialization for SELECT .. FROM DUAL because it
> > does not call setup_subquery_materialization(). We could make
> > SELECT ... FROM DUAL call that function but that doesn't seem
> > to be the case that is worth handling.
> > - 4. Either the subquery predicate is a top-level predicate, or at
> > - least one partial match strategy is enabled. If no partial match
> > - strategy is enabled, then materialization cannot be used for
> > - non-top-level queries because it cannot handle NULLs correctly.
> > - 5. Subquery is non-correlated
> > - TODO:
> > - This is an overly restrictive condition. It can be extended to:
> > - (Subquery is non-correlated ||
> > - Subquery is correlated to any query outer to IN predicate ||
> > - (Subquery is correlated to the immediate outer query &&
> > - Subquery !contains {GROUP BY, ORDER BY [LIMIT],
> > - aggregate functions}) && subquery predicate is not under "NOT IN"))
> > - 6. No execution method was already chosen (by a prepared statement).
> > -
> > - (*) The subquery must be part of a SELECT statement. The current
> > - condition also excludes multi-table update statements.
> > -
> > - Determine whether we will perform subquery materialization before
> > - calling the IN=>EXISTS transformation, so that we know whether to
> > - perform the whole transformation or only that part of it which wraps
> > - Item_in_subselect in an Item_in_optimizer.
> > - */
> > - if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION) &&
> > - in_subs && // 1
> > - !select_lex->is_part_of_union() && // 2
> > - select_lex->master_unit()->first_select()->leaf_tables && // 3
> > - thd->lex->sql_command == SQLCOM_SELECT && // *
> > - select_lex->outer_select()->leaf_tables && // 3A
> > - subquery_types_allow_materialization(in_subs) &&
> > - // psergey-todo: duplicated_subselect_card_check: where it's done?
> > - (in_subs->is_top_level_item() ||
> > - optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) ||
> > - optimizer_flag(thd, OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)) &&//4
> > - !in_subs->is_correlated && // 5
> > - in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
> > - {
> > - in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
> > - }
> > -
> > - Item_subselect::trans_res trans_res;
> > - if ((trans_res= subselect->select_transformer(join)) !=
> > - Item_subselect::RES_OK)
> > - {
> > - DBUG_RETURN((trans_res == Item_subselect::RES_ERROR));
> > + 3. Either the subquery predicate is a top-level predicate, or at
> > + least one partial match strategy is enabled. If no partial match
> > + strategy is enabled, then materialization cannot be used for
> > + non-top-level queries because it cannot handle NULLs correctly.
> > + 4. Subquery is non-correlated
> > + TODO:
> > + This is an overly restrictive condition. It can be extended to:
> > + (Subquery is non-correlated ||
> > + Subquery is correlated to any query outer to IN predicate ||
> > + (Subquery is correlated to the immediate outer query &&
> > + Subquery !contains {GROUP BY, ORDER BY [LIMIT],
> > + aggregate functions}) && subquery predicate is not under "NOT IN"))
> > +
> > + (*) The subquery must be part of a SELECT statement. The current
> > + condition also excludes multi-table update statements.
> > + */
> > + if (!(in_subs->in_strategy & SUBS_MATERIALIZATION &&
> > + !select_lex->is_part_of_union() && // 1
> > + parent_unit->first_select()->leaf_tables && // 2
> > + thd->lex->sql_command == SQLCOM_SELECT && // *
> > + select_lex->outer_select()->leaf_tables && // 2A
> > + subquery_types_allow_materialization(in_subs) &&
> > + // psergey-todo: duplicated_subselect_card_check: where it's done?
> > + (in_subs->is_top_level_item() || //3
> > + optimizer_flag(thd,
> > + OPTIMIZER_SWITCH_PARTIAL_MATCH_ROWID_MERGE) || //3
> > + optimizer_flag(thd,
> > + OPTIMIZER_SWITCH_PARTIAL_MATCH_TABLE_SCAN)) && //3
> > + !in_subs->is_correlated)) //4
> > + {
> > + /* Materialization is not possible based on syntactic properties. */
> > + in_subs->in_strategy&= ~SUBS_MATERIALIZATION;
> > + }
> > +
> > + if (!in_subs->in_strategy)
> > + {
> > + /*
> > + If neither materialization is possible, nor the user chose
> > + IN-TO-EXISTS, choose IN-TO-EXISTS as the only universal strategy.
> > + */
> > + in_subs->in_strategy|= SUBS_IN_TO_EXISTS;
> > + }
> > }
psergey: The above seems unneccessarily convoluted. This is not apprent from
the patch, but the resulting code looks like this:
if (in_subs)
{
/* Subquery predicate is an IN/=ANY predicate. */
if (optimizer_flag(thd, OPTIMIZER_SWITCH_IN_TO_EXISTS))
in_subs->in_strategy|= SUBS_IN_TO_EXISTS;
if (optimizer_flag(thd, OPTIMIZER_SWITCH_MATERIALIZATION))
in_subs->in_strategy|= SUBS_MATERIALIZATION;
/* a long comment */
if (!(long condition))
{
/* Materialization is not possible based on syntactic properties. */
in_subs->in_strategy&= ~SUBS_MATERIALIZATION;
}
...
Is there any particular reason to first set SUBS_MATERIALIZATION flag, and
then optionally clear it? It seems it would be more straightforward to only
set it when materialization is really applicable?
timour:
The idea was to separate setting the strategy based on user-supplied
switches, and based on syntactic properties. This was helpful during
development. However I see value in your suggestion as well, so changed
as requested.
> > +
> > + /*
> > + Transform each subquery predicate according to its overloaded
> > + transformer.
> > + */
> > + if (subselect->select_transformer(join))
> > + DBUG_RETURN(-11);
> > }
> > }
> > DBUG_RETURN(0);
...
> > @@ -1830,15 +1919,15 @@
> > - sj_inner_fanout*sj_outer_fanout lookups.
> >
> > */
> > - double one_lookup_cost;
> > - if (sj_outer_fanout*temptable_rec_size >
> > - join->thd->variables.max_heap_table_size)
> > - one_lookup_cost= DISK_TEMPTABLE_LOOKUP_COST;
> > - else
> > - one_lookup_cost= HEAP_TEMPTABLE_LOOKUP_COST;
> > + double one_lookup_cost= get_tmp_table_lookup_cost(join->thd,
> > + sj_outer_fanout,
> > + temptable_rec_size);
> > + double one_write_cost= get_tmp_table_write_cost(join->thd,
> > + sj_outer_fanout,
> > + temptable_rec_size);
> >
> > double write_cost= join->positions[first_tab].prefix_record_count*
> > - sj_outer_fanout * one_lookup_cost;
> > + sj_outer_fanout * one_write_cost;
> > double full_lookup_cost= join->positions[first_tab].prefix_record_count*
> > sj_outer_fanout* sj_inner_fanout *
> > one_lookup_cost;
> > @@ -3360,9 +3449,23 @@
> > JOIN_TAB* join_tab=join->join_tab;
> > SELECT_LEX_UNIT *unit= join->unit;
> > DBUG_ENTER("rewrite_to_index_subquery_engine");
> > +
> > /*
> > is this simple IN subquery?
> > */
> > + /* TODO: In order to use these more efficient subquery engines in more cases,
> > + the following problems need to be solved:
> > + - the code that removes GROUP BY (group_list), also adds an ORDER BY
> > + (order), thus GROUP BY queries (almost?) never pass through this branch.
> > + Solution: remove the test below '!join->order', because we remove the
> > + ORDER clase for subqueries anyway.
> > + - in order to set a more efficient engine, the optimizer needs to both
> > + decide to remove GROUP BY, *and* select one of the JT_[EQ_]REF[_OR_NULL]
> > + access methods, *and* loose scan should be more expensive or
> > + inapliccable. When is that possible?
> > + - Consider expanding the applicability of this rewrite for loose scan
> > + for group by queries.
> > + */
> > if (!join->group_list && !join->order &&
> > join->unit->item &&
> > join->unit->item->substype() == Item_subselect::IN_SUBS &&
> > @@ -3503,3 +3606,349 @@
> > }
> >
> >
> > +/**
> > + Optimize all subqueries of a query that have were flattened into a semijoin.
psergey: a typo on the above line?
timour: Yes, fixed.
> > +
> > + @details
> > + Optimize all immediate children subqueries of a query.
> > +
> > + This phase must be called after substitute_for_best_equal_field() because
> > + that function may replace items with other items from a multiple equality,
> > + and we need to reference the correct items in the index access method of the
> > + IN predicate.
> > +
> > + @return Operation status
> > + @retval FALSE success.
> > + @retval TRUE error occurred.
> > +*/
> > +
> > +bool JOIN::optimize_unflattened_subqueries()
> > +{
> > + return select_lex->optimize_unflattened_subqueries();
> > +}
> > +
> > +
> > +/**
> > + Choose an optimal strategy to execute an IN/ALL/ANY subquery predicate
> > + based on cost.
> > +
> > + @param join_tables the set of tables joined in the subquery
> > +
> > + @notes
> > + The method chooses between the materialization and IN=>EXISTS rewrite
> > + strategies for the execution of a non-flattened subquery IN predicate.
> > + The cost-based decision is made as follows:
> > +
> > + 1. compute materialize_strategy_cost based on the unmodified subquery
> > + 2. reoptimize the subquery taking into account the IN-EXISTS predicates
> > + 3. compute in_exists_strategy_cost based on the reoptimized plan
> > + 4. compare and set the cheaper strategy
> > + if (materialize_strategy_cost >= in_exists_strategy_cost)
> > + in_strategy = MATERIALIZATION
> > + else
> > + in_strategy = IN_TO_EXISTS
> > + 5. if in_strategy = MATERIALIZATION and it is not possible to initialize it
> > + revert to IN_TO_EXISTS
> > + 6. if (in_strategy == MATERIALIZATION)
> > + revert the subquery plan to the original one before reoptimizing
> > + else
> > + inject the IN=>EXISTS predicates into the new EXISTS subquery plan
> > +
> > + The implementation itself is a bit more complicated because it takes into
> > + account two more factors:
> > + - whether the user allowed both strategies through an optimizer_switch, and
> > + - if materialization was the cheaper strategy, whether it can be executed
> > + or not.
> > +
> > + @retval FALSE success.
> > + @retval TRUE error occurred.
> > +*/
> > +
> > +bool JOIN::choose_subquery_plan(table_map join_tables)
> > +{
> > + Query_plan_state save_qep; /* The original QEP of the subquery. */
> > + enum_reopt_result reopt_result= REOPT_NONE;
> > + Item_in_subselect *in_subs;
> > +
> > + if (select_lex->master_unit()->item &&
> > + select_lex->master_unit()->item->is_in_predicate())
> > + {
> > + in_subs= (Item_in_subselect*) select_lex->master_unit()->item;
> > + if (in_subs->create_in_to_exists_cond(this))
> > + return true;
> > + }
> > + else
> > + return false;
> > +
> > + DBUG_ASSERT(in_subs->in_strategy); /* A strategy must be chosen earlier. */
> > + DBUG_ASSERT(in_to_exists_where || in_to_exists_having);
> > + DBUG_ASSERT(!in_to_exists_where || in_to_exists_where->fixed);
> > + DBUG_ASSERT(!in_to_exists_having || in_to_exists_having->fixed);
> > +
> > + /*
> > + Compute and compare the costs of materialization and in-exists if both
> > + strategies are possible and allowed by the user (checked during the prepare
> > + phase.
> > + */
> > + if (in_subs->in_strategy & SUBS_MATERIALIZATION &&
> > + in_subs->in_strategy & SUBS_IN_TO_EXISTS)
psergey: when I write conditions like the one above, Monty tells me to change
it to
in_subs->in_strategy & (SUBS_MATERIALIZATION |SUBS_IN_TO_EXISTS)
Did he not tell the same to you?
timour:
No. There is always something new to learn :). However, your suggestion
is wrong. The two are not equivalent. For instance if:
- in_subs->in_strategy = SUBS_IN_TO_EXISTS (binary(10)),
- (SUBS_MATERIALIZATION | SUBS_IN_TO_EXISTS) = binary(110)
then
in_subs->in_strategy & (SUBS_MATERIALIZATION |SUBS_IN_TO_EXISTS) == binary(10)
which is TRUE in our case. This is clearly not the FALSE we would expect.
Any better suggestion?
> > + {
> > + JOIN *outer_join;
> > + JOIN *inner_join= this;
> > + /* Number of (partial) rows of the outer JOIN filtered by the IN predicate. */
> > + double outer_record_count;
> > + /* Number of unique value combinations filtered by the IN predicate. */
> > + double outer_lookup_keys;
> > + /* Cost and row count of the unmodified subquery. */
> > + double inner_read_time_1, inner_record_count_1;
> > + /* Cost of the subquery with injected IN-EXISTS predicates. */
> > + double inner_read_time_2;
> > + /* The cost to compute IN via materialization. */
> > + double materialize_strategy_cost;
> > + /* The cost of the IN->EXISTS strategy. */
> > + double in_exists_strategy_cost;
> > + double dummy;
> > +
> > + /*
> > + A. Estimate the number of rows of the outer table that will be filtered
> > + by the IN predicate.
> > + */
> > + outer_join= unit->outer_select() ? unit->outer_select()->join : NULL;
> > + if (outer_join)
> > + {
> > + uint outer_partial_plan_len;
> > + /*
> > + Make_cond_for_table is called for predicates only in the WHERE/ON
> > + clauses. In all other cases, predicates are not pushed to any
> > + JOIN_TAB, and their joi_tab_idx remains MAX_TABLES. Such predicates
> > + are evaluated for each complete row of the outer join.
> > + */
> > + outer_partial_plan_len= (in_subs->get_join_tab_idx() == MAX_TABLES) ?
> > + outer_join->tables :
> > + in_subs->get_join_tab_idx() + 1;
> > + outer_join->get_partial_join_cost(outer_partial_plan_len, &dummy,
> > + &outer_record_count);
> > + if (outer_join->tables > outer_join->const_tables)
> > + outer_lookup_keys= prev_record_reads(outer_join->best_positions,
> > + outer_partial_plan_len,
> > + in_subs->used_tables());
> > + else
> > + {
> > + /* If all tables are constant, positions is undefined. */
> > + outer_lookup_keys= 1;
> > + }
> > + }
> > + else
> > + {
> > + /*
> > + TODO: outer_join can be NULL for DELETE statements.
> > + How to compute its cost?
> > + */
> > + outer_record_count= 1;
> > + outer_lookup_keys=1;
> > + }
> > + /*
> > + There cannot be more lookup keys than the total number of records.
> > + TODO: this a temporary solution until we find a better way to compute
> > + get_partial_join_cost() and prev_record_reads() in a consitent manner,
> > + where it is guaranteed that (outer_lookup_keys <= outer_record_count).
> > + */
> > + if (outer_lookup_keys > outer_record_count)
> > + outer_lookup_keys= outer_record_count;
> > +
> > + /*
> > + B. Estimate the cost and number of records of the subquery both
> > + unmodified, and with injected IN->EXISTS predicates.
> > + */
> > + inner_read_time_1= inner_join->best_read;
> > + inner_record_count_1= inner_join->record_count;
> > +
> > + if (in_to_exists_where && const_tables != tables)
> > + {
> > + /*
> > + Re-optimize and cost the subquery taking into account the IN-EXISTS
> > + conditions.
> > + */
> > + reopt_result= reoptimize(in_to_exists_where, join_tables, &save_qep);
> > + if (reopt_result == REOPT_ERROR)
> > + return TRUE;
> > +
> > + /* Get the cost of the modified IN-EXISTS plan. */
> > + inner_read_time_2= inner_join->best_read;
> > +
> > + }
> > + else
> > + {
> > + /* Reoptimization would not produce any better plan. */
> > + inner_read_time_2= inner_read_time_1;
> > + }
> > +
> > + /*
> > + C. Compute execution costs.
> > + */
> > + /* C.1 Compute the cost of the materialization strategy. */
> > + uint rowlen= get_tmp_table_rec_length(unit->first_select()->item_list);
> > + /* The cost of writing one row into the temporary table. */
> > + double write_cost= get_tmp_table_write_cost(thd, inner_record_count_1,
> > + rowlen);
> > + /* The cost of a lookup into the unique index of the materialized table. */
> > + double lookup_cost= get_tmp_table_lookup_cost(thd, inner_record_count_1,
> > + rowlen);
> > + /*
> > + The cost of executing the subquery and storing its result in an indexed
> > + temporary table.
> > + */
> > + double materialization_cost= inner_read_time_1 +
> > + write_cost * inner_record_count_1;
> > +
> > + materialize_strategy_cost= materialization_cost +
> > + outer_record_count * lookup_cost;
> > +
> > + /* C.2 Compute the cost of the IN=>EXISTS strategy. */
> > + in_exists_strategy_cost= outer_lookup_keys * inner_read_time_2;
> > +
> > + /* C.3 Compare the costs and choose the cheaper strategy. */
> > + if (materialize_strategy_cost >= in_exists_strategy_cost)
> > + in_subs->in_strategy&= ~SUBS_MATERIALIZATION;
> > + else
> > + in_subs->in_strategy&= ~SUBS_IN_TO_EXISTS;
> > + }
> > +
> > + /*
> > + If (1) materialization is a possible strategy based on semantic analysis
> > + during the prepare phase, then if
> > + (2) it is more expensive than the IN->EXISTS transformation, and
> > + (3) it is not possible to create usable indexes for the materialization
> > + strategy,
> > + fall back to IN->EXISTS.
> > + otherwise
> > + use materialization.
> > + */
> > + if (in_subs->in_strategy & SUBS_MATERIALIZATION &&
> > + in_subs->setup_mat_engine())
> > + {
> > + /*
> > + If materialization was the cheaper or the only user-selected strategy,
> > + but it is not possible to execute it due to limitations in the
> > + implementation, fall back to IN-TO-EXISTS.
> > + */
> > + in_subs->in_strategy&= ~SUBS_MATERIALIZATION;
> > + in_subs->in_strategy|= SUBS_IN_TO_EXISTS;
> > + }
> > +
> > + if (in_subs->in_strategy & SUBS_MATERIALIZATION)
> > + {
> > + /* Restore the original query plan used for materialization. */
> > + if (reopt_result == REOPT_NEW_PLAN)
> > + restore_query_plan(&save_qep);
> > +
> > + /* TODO: should we set/unset this flag for both select_lex and its unit? */
> > + in_subs->unit->uncacheable&= ~UNCACHEABLE_DEPENDENT;
> > + select_lex->uncacheable&= ~UNCACHEABLE_DEPENDENT;
> > +
> > + /*
> > + Reset the "LIMIT 1" set in Item_exists_subselect::fix_length_and_dec.
> > + TODO:
> > + Currently we set the subquery LIMIT to infinity, and this is correct
> > + because we forbid at parse time LIMIT inside IN subqueries (see
> > + Item_in_subselect::test_limit). However, once we allow this, here
> > + we should set the correct limit if given in the query.
> > + */
> > + in_subs->unit->global_parameters->select_limit= NULL;
> > + in_subs->unit->set_limit(unit->global_parameters);
> > + /*
> > + Set the limit of this JOIN object as well, because normally its being
> > + set in the beginning of JOIN::optimize, which was already done.
> > + */
> > + select_limit= in_subs->unit->select_limit_cnt;
> > + }
> > + else if (in_subs->in_strategy & SUBS_IN_TO_EXISTS)
> > + {
> > + if (reopt_result == REOPT_NONE && in_to_exists_where &&
> > + const_tables != tables)
> > + {
> > + /*
> > + The subquery was not reoptimized either because the user allowed only the
> > + IN-EXISTS strategy, or because materialization was not possible based on
> > + semantic analysis. Clenup the original plan and reoptimize.
> > + */
> > + for (uint i= 0; i < tables; i++)
> > + {
> > + join_tab[i].keyuse= NULL;
> > + join_tab[i].checked_keys.clear_all();
> > + }
> > + if ((reopt_result= reoptimize(in_to_exists_where, join_tables, NULL)) ==
> > + REOPT_ERROR)
> > + return TRUE;
> > + }
> > +
> > + if (in_subs->inject_in_to_exists_cond(this))
> > + return TRUE;
> > + }
> > + else
> > + DBUG_ASSERT(FALSE);
> > +
> > + return FALSE;
> > +}
> > +
> > +
> > +/**
> > + Choose a query plan for a table-less subquery.
> > +
> > + @notes
> > +
> > + @retval FALSE success.
> > + @retval TRUE error occurred.
> > +*/
> > +
> > +bool JOIN::choose_tableless_subquery_plan()
> > +{
> > + DBUG_ASSERT(!tables_list || !tables);
> > + if (select_lex->master_unit()->item)
> > + {
> > + DBUG_ASSERT(select_lex->master_unit()->item->type() ==
> > + Item::SUBSELECT_ITEM);
> > + Item_subselect *subs_predicate= select_lex->master_unit()->item;
> > +
> > + /*
> > + If the optimizer determined that his query has an empty result,
> > + in most cases the subquery predicate is a known constant value -
> > + either FALSE or NULL. The implementation of Item_subselect::reset()
> > + determines which one.
> > + */
> > + if (zero_result_cause)
> > + {
> > + if (!implicit_grouping)
> > + {
> > + /*
> > + Both group by queries and non-group by queries without aggregate
> > + functions produce empty subquery result.
> > + */
> > + subs_predicate->reset();
> > + subs_predicate->make_const();
> > + return FALSE;
> > + }
> > +
> > + /* TODO:
> > + A further optimization is possible when a non-group query with
> > + MIN/MAX/COUNT is optimized by opt_sum_query. Then, if there are
> > + only MIN/MAX functions over an empty result set, the subquery
> > + result is a NULL value/row, thus the value of subs_predicate is
> > + NULL.
> > + */
> > + }
> > +
> > + if (subs_predicate->is_in_predicate())
> > + {
> > + Item_in_subselect *in_subs;
> > + in_subs= (Item_in_subselect*) subs_predicate;
> > + in_subs->in_strategy= SUBS_IN_TO_EXISTS;
> > + if (in_subs->create_in_to_exists_cond(this) ||
> > + in_subs->inject_in_to_exists_cond(this))
> > + return TRUE;
> > + tmp_having= having;
> > + }
> > + }
> > + return FALSE;
> > +}
> > +
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/sql_lex.cc 5.3-timours-wl/sql/sql_lex.cc
> > --- 5.3-timours-wl-clean/sql/sql_lex.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/sql_lex.cc 2011-05-11 20:08:50.000000000 +0100
> > @@ -1684,6 +1684,31 @@
> > slave= 0;
> > }
> >
> > +
> > +void st_select_lex_node::add_slave(st_select_lex_node *slave_arg)
> > +{
> > + for (; slave; slave= slave->next)
> > + if (slave == slave_arg)
> > + return;
> > +
> > + if (slave)
> > + {
> > + st_select_lex_node *slave_arg_slave= slave_arg->slave;
> > + /* Insert in the front of list of slaves if any. */
> > + slave_arg->include_neighbour(slave);
> > + /* include_neighbour() sets slave_arg->slave=0, restore it. */
> > + slave_arg->slave= slave_arg_slave;
> > + /* Count on include_neighbour() setting the master. */
> > + DBUG_ASSERT(slave_arg->master == this);
> > + }
> > + else
> > + {
> > + slave= slave_arg;
> > + slave_arg->master= this;
> > + }
> > +}
psergey:
1. Suppose slave_arg is already in the list of slaves (based on the function's
code, this seems to be possible) Why does this function adjust this->slave in
this case?
timour:
I don't get your question - the loop in the beginning of the method above
looks for slave_arg in the list of slaves, and if there is a match, it
returns. So it doesn't adjust anything in this case. There is another problem
with it, see my comment below.
2. I've made the following change:
=== modified file 'sql/sql_lex.cc'
--- sql/sql_lex.cc 2011-05-05 12:24:28 +0000
+++ sql/sql_lex.cc 2011-05-13 21:34:49 +0000
@@ -1693,6 +1693,7 @@ void st_select_lex_node::add_slave(st_se
if (slave)
{
+ DBUG_ASSERT(0);
st_select_lex_node *slave_arg_slave= slave_arg->slave;
/* Insert in the front of list of slaves if any. */
slave_arg->include_neighbour(slave);
and all t/subselect*.test still passed. I think the code inside if () { ... }
is deadcode. If yes, please remove it, if not, please add coverage to the
testsuite.
timour-todo:
This code was added to fix a Valgrind problem, there is a description of
the problem in the commit, but, alas, there is no test case.
- Apparently there is a bug in the FOR loop above that searches for slave_arg,
because it modifies this->slave, so that in the end of the loop it is NULL.
Thus the "if (slave)" branch will never be true.
- Even after fixing this problem, the if branch still seems to be dead code
with respect to existing test cases.
Analysis:
The method passes beyound the first for loop in these test files:
union subselect subselect_*
> > +
> > +
> > /*
> > include on level down (but do not link)
> >
...
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/sql_list.h 5.3-timours-wl/sql/sql_list.h
> > --- 5.3-timours-wl-clean/sql/sql_list.h 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/sql_list.h 2011-05-11 20:08:50.000000000 +0100
> > @@ -260,7 +260,7 @@
> > list_node *node= first;
> > list_node *list_first= list->first;
> > elements=0;
> > - while (node && node != list_first)
> > + while (node->info && node != list_first)
psergey:
Why the above change? Does this mean that List<T> now can contain (T*)NULL ?
timour:
Exactly the opposite. Look at the change - the original code from Igor assumed
that 'node' may be NULL, which is never the case. However, 'node->info' is
NULL for the last node. If you change back to the original code, you should
get an infinite loop because the condition was wrong.
To make the condition clearer I changed it to:
while (node != &end_of_list && node != list_first)
which is equivalent, because of how end_of_list->info is initialized.
> > {
> > prev= &node->next;
> > node= node->next;
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/sql_select.cc 5.3-timours-wl/sql/sql_select.cc
> > --- 5.3-timours-wl-clean/sql/sql_select.cc 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/sql_select.cc 2011-05-11 20:08:50.000000000 +0100
...
> > @@ -882,6 +887,7 @@
> > "Impossible HAVING" : "Impossible WHERE";
> > tables= 0;
> > error= 0;
> > + choose_tableless_subquery_plan();
> > goto setup_subq_exit;
> > }
psergey: there are three instances of this piece of code:
if (.. we've figured out this is a degenerate join which produces no rows ...)
{
...
choose_tableless_subquery_plan();
goto setup_subq_exit;
}
I'm afraid if somebody invents a fourth way to figure out that the join is
degenerate, they will forget to make call to choose_tableless_subquery_plan().
Could you prevent this by introducing
empty_join_output:
choose_tableless_subquery_plan();
... whatever else ...
setup_subq_exit:
and using appropriate goto's?
timour:
Fixed. It turned out the call to choose_tableless_subquery_plan() can
be moved to the setup_subq_exit label (guarded by an IF).
> > }
> > @@ -926,12 +932,13 @@
> > */
> > if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
> > {
> > - if (res == HA_ERR_KEY_NOT_FOUND)
> > + if (res == HA_ERR_KEY_NOT_FOUND || res < 0)
psergey: What is this for? I am looking at opt_sum_query code and I don't
see any cases where it will return a negative value?
timour:
This was an equivalent rewrite of the old code, where there was a branch
checking for (res < 0). The original 5.3 code:
if (res == HA_ERR_KEY_NOT_FOUND)
{
DBUG_PRINT("info",("No matching min/max row"));
zero_result_cause= "No matching min/max row";
tables= 0;
error=0;
goto setup_subq_exit;
}
if (res > 1)
{
error= res;
DBUG_PRINT("error",("Error from opt_sum_query"));
DBUG_RETURN(1);
}
if (res < 0)
{
DBUG_PRINT("info",("No matching min/max row"));
zero_result_cause= "No matching min/max row";
tables= 0;
error=0;
goto setup_subq_exit;
}
..........
Indeed, now that I looked at opt_sum_query(), I also didn't find any
way it can return a negative. Perhaps it could in the past, and no one
fixed the caller code. I put an assert (res >= 0), and all worked fine,
so I removed this test. Thanks for spotting this.
> > {
> > DBUG_PRINT("info",("No matching min/max row"));
> > zero_result_cause= "No matching min/max row";
> > tables= 0;
> > error=0;
> > + choose_tableless_subquery_plan();
> > goto setup_subq_exit;
> > }
> > if (res > 1)
...
> > @@ -9036,11 +9070,16 @@
> > *simple_order=0; // Must do a temp table to sort
> > else if (!(order_tables & not_const_tables))
> > {
> > - if (order->item[0]->with_subselect &&
> > - !(join->select_lex->options & SELECT_DESCRIBE))
> > - order->item[0]->val_str(&order->item[0]->str_value);
> > + if (order->item[0]->with_subselect)
> > + {
> > + /*
> > + Delay the evaluation of constant ORDER and/or GROUP expressions that
> > + contain subqueries until the execution phase.
> > + */
> > + join->exec_const_order_group_cond.push_back(order->item[0]);
psergey: I'm wondering why would one want to evaluate them at all in that
case?
If we have
SELECT ... GROUP BY const_subquery_expression, ...
we don't need to evaluate const_subquery_expression at all, do we?
timour:
There was some long disucssion on IRC about this, unfortunately I don't
remeber the reasoning. Right now, off the top of my head - there is a
difference if the result is NULL or not. I think there were some other
subtle differences here too. So this is not arbitrary. If you really
think it is necessary, I can dig out the reasoning one more time.
> > + }
> > DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
> > - continue; // skip const item
> > + continue;
> > }
> > else
> > {
...
> > @@ -20316,5 +20363,154 @@
> >
> >
> > /**
> > + Save a query execution plan so that the caller can revert to it if needed,
> > + and reset the current query plan so that it can be reoptimized.
> > +
> > + @param save_to The object into which the current query plan state is saved
> > +*/
> > +
> > +void JOIN::save_query_plan(Query_plan_state *save_to)
> > +{
> > + if (keyuse.elements)
> > + {
> > + DYNAMIC_ARRAY tmp_keyuse;
> > + /* Swap the current and the backup keyuse internal arrays. */
> > + tmp_keyuse= keyuse;
> > + keyuse= save_to->keyuse; /* keyuse is reset to an empty array. */
> > + save_to->keyuse= tmp_keyuse;
> > +
> > + for (uint i= 0; i < tables; i++)
> > + {
> > + save_to->join_tab_keyuse[i]= join_tab[i].keyuse;
> > + join_tab[i].keyuse= NULL;
> > + save_to->join_tab_checked_keys[i]= join_tab[i].checked_keys;
> > + join_tab[i].checked_keys.clear_all();
> > + }
> > + }
> > + memcpy((uchar*) save_to->best_positions, (uchar*) best_positions,
> > + sizeof(POSITION) * (tables + 1));
> > + memset(best_positions, 0, sizeof(POSITION) * (tables + 1));
> > +}
> > +
> > +
> > +/**
> > + Restore a query execution plan previously saved by the caller.
> > +
> > + @param The object from which the current query plan state is restored.
> > +*/
> > +
> > +void JOIN::restore_query_plan(Query_plan_state *restore_from)
> > +{
> > + if (restore_from->keyuse.elements)
> > + {
> > + DYNAMIC_ARRAY tmp_keyuse;
> > + tmp_keyuse= keyuse;
> > + keyuse= restore_from->keyuse;
> > + restore_from->keyuse= tmp_keyuse;
> > +
> > + for (uint i= 0; i < tables; i++)
> > + {
> > + join_tab[i].keyuse= restore_from->join_tab_keyuse[i];
> > + join_tab[i].checked_keys= restore_from->join_tab_checked_keys[i];
> > + }
> > +
> > + }
> > + memcpy((uchar*) best_positions, (uchar*) restore_from->best_positions,
> > + sizeof(POSITION) * (tables + 1));
> > +}
> > +
> > +
> > +/**
> > + Reoptimize a query plan taking into account an additional conjunct to the
> > + WHERE clause.
> > +
> > + @param added_where An extra conjunct to the WHERE clause to reoptimize with
> > + @param join_tables The set of tables to reoptimize
> > + @param save_to If != NULL, save here the state of the current query plan
> > +
> > + @notes
> > + Given a query plan that was already optimized taking into account some WHERE
> > + clause 'C', reoptimize this plan with a new WHERE clause 'C AND added_where'.
> > + The reoptimization works as follows:
> > +
> > + 1. Call update_ref_and_keys *only* for the new conditions 'added_where'
> > + that are about to be injected into the query.
> > + 2. Expand if necessary the original KEYUSE array JOIN::keyuse to
> > + accommodate the new REF accesses computed for the 'added_where' condition.
> > + 3. Add the new KEYUSEs into JOIN::keyuse.
> > + 4. Re-sort and re-filter the JOIN::keyuse array with the newly added
> > + KEYUSE elements.
psergey:
I think the above scheme has some flaws. What if the initial filtering
has discarded elements that would be useful with the new injected condition?
Consider this example:
create table ten (a int);
insert into ten values (0),(1),(2),(3),(4),(5),(6),(7),(8),(9);
create table one_k (a int);
insert into one_k select A.a + B.a*10 + C.a*100 from ten A, ten B, ten C;
create table t11 (kp1 int, kp2 int, a int, filler char(100), key(kp1, kp2));
insert into t11 select a/100, a, a, 'filler' from one_k;
If I debug this query:
explain select a from one_k where a in (select kp1 from t11 where kp2=10 and a=4) or a+1 < 100000;
I see that the optimizer considers access to t11 via lookup on t11.kp1=...
but not on (t11.kp1=... AND t11.kp2=..).
Please note that from user point of view this will look like a regression.
timour:
Thank you for spotting this! Indeed, sort_and_filter_keyuse() was filtering the
keyparts for which there is no key prefix. It may happen that the IN-EXISTS
transformation adds exactly those condition(s) that would provide the necessary
index prefix. This worked before MWL#89 because the IN-EXISTS transformation
happened much earlier during prepare, so during optimization all conditions
were present.
I fixed this problem by adding one extra parameter 'skip_unprefixed_keyparts'
to sort_and_filter_keyuse() that controls whether it should filter keyparts
without a prefix. Then sort_and_filter_keyuse() is called with
'skip_unprefixed_keyparts' if the current join is a subquery, and the subquery
may be executed via the IN-EXISTS strategy.
I also simplified the your example to the below test. The difference in
EXPLAIN between right/wrong plan is the chosen key (key1 instead of key 3),
the key length (10 instead of 5), and the access method is 'index_subquery'
instead of 'ref'.
drop table if exists t1, t2;
create table t1 (c1 int);
insert into t1 values (1), (2), (3);
create table t2 (kp1 int, kp2 int, c2 int, filler char(100));
insert into t2 values (0,0,0,'filler'),(0,1,1,'filler'),(0,2,2,'filler'),(0,3,3,'filler');
create index key1 on t2 (kp1, kp2);
create index key2 on t2 (kp1);
create index key3 on t2 (kp2);
analyze table t2;
explain
select c1 from t1 where c1 in (select kp1 from t2 where kp2 = 10 and c2 = 4) or c1 > 7;
select c1 from t1 where c1 in (select kp1 from t2 where kp2 = 10 and c2 = 4) or c1 > 7;
-- New plan:
+----+--------------------+-------+----------------+----------------+------+---------+------------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------------+-------+----------------+----------------+------+---------+------------+------+-------------+
| 1 | PRIMARY | t1 | ALL | NULL | NULL | NULL | NULL | 3 | Using where |
| 2 | DEPENDENT SUBQUERY | t2 | index_subquery | key1,key2,key3 | key1 | 10 | func,const | 1 | Using where |
+----+--------------------+-------+----------------+----------------+------+---------+------------+------+-------------+
-- Old plan:
+----+--------------------+-------+------+----------------+------+---------+-------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+--------------------+-------+------+----------------+------+---------+-------+------+-------------+
| 1 | PRIMARY | t1 | ALL | NULL | NULL | NULL | NULL | 3 | Using where |
| 2 | DEPENDENT SUBQUERY | t2 | ref | key1,key2,key3 | key3 | 5 | const | 1 | Using where |
+----+--------------------+-------+------+----------------+------+---------+-------+------+-------------+
Interestingly, there is no single test case in whole test suite that
exposes this problem. No other EXPLAIN was affected after this change.
> > +
> > + @retval REOPT_NEW_PLAN there is a new plan.
> > + @retval REOPT_OLD_PLAN no new improved plan was produced, use the old one.
> > + @retval REOPT_ERROR an irrecovarable error occured during reoptimization.
> > +*/
> > +
> > +JOIN::enum_reopt_result
> > +JOIN::reoptimize(Item *added_where, table_map join_tables,
> > + Query_plan_state *save_to)
> > +{
psergey:
This function looks very odd. We touch "keyuse" only when
restore_from->keyuse.elements!=NULL
What about the case when
this->keyuse.elements!=NULL && restore_from->keyuse.elements==NULL
?
This looks like a possible scenario to me. Suppose that
- original (i.e. Materialization) plan produces no KEYUSE-s
- IN-to-EXISTS plan does produce KEYUSE
and we're restoring from IN-to-EXISTS to Materialization plan?
timour:
As discussed on IRC, your comment is about JOIN::restore_query_plan().
In simple words - if the original plan had no keyuses, there is no
keyuses to restore. If IN-TO-EXISTS produced new keyuses, those
are exactly the ones that we don't want to restore. We want to
restore the original (materialization) plan, which in your example
has no keyuses, so there are no keyuses to restore. Also look at
JOIN::save_query_plan(), its logic is paired with restore().
Let me know if I missed something or misunderstood your comment.
> > + DYNAMIC_ARRAY added_keyuse;
> > + SARGABLE_PARAM *sargables= 0; /* Used only as a dummy parameter. */
> > + uint org_keyuse_elements;
> > +
> > + /* Re-run the REF optimizer to take into account the new conditions. */
> > + if (update_ref_and_keys(thd, &added_keyuse, join_tab, tables, added_where,
> > + ~outer_join, select_lex, &sargables))
> > + {
> > + delete_dynamic(&added_keyuse);
> > + return REOPT_ERROR;
> > + }
> > +
> > + if (!added_keyuse.elements)
> > + {
> > + delete_dynamic(&added_keyuse);
> > + return REOPT_OLD_PLAN;
> > + }
> > +
> > + if (save_to)
> > + save_query_plan(save_to);
> > +
> > + if (!keyuse.buffer &&
> > + my_init_dynamic_array(&keyuse, sizeof(KEYUSE), 20, 64))
> > + {
> > + delete_dynamic(&added_keyuse);
> > + return REOPT_ERROR;
> > + }
> > +
> > + org_keyuse_elements= save_to ? save_to->keyuse.elements : keyuse.elements;
> > + allocate_dynamic(&keyuse, org_keyuse_elements + added_keyuse.elements);
> > +
> > + /* If needed, add the access methods from the original query plan. */
> > + if (save_to)
> > + {
> > + DBUG_ASSERT(!keyuse.elements);
> > + memcpy(keyuse.buffer,
> > + save_to->keyuse.buffer,
> > + (size_t) save_to->keyuse.elements * keyuse.size_of_element);
> > + keyuse.elements= save_to->keyuse.elements;
> > + }
> > +
> > + /* Add the new access methods to the keyuse array. */
> > + memcpy(keyuse.buffer + keyuse.elements * keyuse.size_of_element,
> > + added_keyuse.buffer,
> > + (size_t) added_keyuse.elements * added_keyuse.size_of_element);
> > + keyuse.elements+= added_keyuse.elements;
> > + /* added_keyuse contents is copied, and it is no longer needed. */
> > + delete_dynamic(&added_keyuse);
> > +
> > + if (sort_and_filter_keyuse(&keyuse))
> > + return REOPT_ERROR;
> > + optimize_keyuse(this, &keyuse);
> > +
> > + /* Re-run the join optimizer to compute a new query plan. */
> > + if (choose_plan(this, join_tables))
> > + return REOPT_ERROR;
> > +
> > + return REOPT_NEW_PLAN;
> > +}
> > +
> > +
> > +/**
> > @} (end of group Query_Optimizer)
> > */
> > diff -urN --exclude='.*' 5.3-timours-wl-clean/sql/sql_select.h 5.3-timours-wl/sql/sql_select.h
> > --- 5.3-timours-wl-clean/sql/sql_select.h 2011-05-11 20:12:50.000000000 +0100
> > +++ 5.3-timours-wl/sql/sql_select.h 2011-05-11 20:08:50.000000000 +0100
> > @@ -603,8 +603,53 @@
> >
> > class JOIN :public Sql_alloc
> > {
> > +private:
> > JOIN(const JOIN &rhs); /**< not implemented */
> > JOIN& operator=(const JOIN &rhs); /**< not implemented */
> > +
> > +protected:
> > +
> > + /**
> > + The subset of the state of a JOIN that represents an optimized query
> > + execution plan. Allows saving/restoring different plans for the same query.
> > + */
> > + class Query_plan_state {
psergey: I have a concern about naming. This is really a join plan state, not
a query plan state. We may get into mess if at some point we'll need to save
plan state for the whole query.
Is it still possible to rename this to something like Join_plan_state?
timour:
Sure, done.
> > + public:
> > + DYNAMIC_ARRAY keyuse; /* Copy of the JOIN::keyuse array. */
> > + POSITION best_positions[MAX_TABLES+1]; /* Copy of JOIN::best_positions */
> > + /* Copies of the JOIN_TAB::keyuse pointers for each JOIN_TAB. */
> > + KEYUSE *join_tab_keyuse[MAX_TABLES];
> > + /* Copies of JOIN_TAB::checked_keys for each JOIN_TAB. */
> > + key_map join_tab_checked_keys[MAX_TABLES];
> > + public:
> > + Query_plan_state()
> > + {
> > + keyuse.elements= 0;
> > + keyuse.buffer= NULL;
> > + }
> > + Query_plan_state(JOIN *join);
> > + ~Query_plan_state()
> > + {
> > + delete_dynamic(&keyuse);
> > + }
> > + };
> > +
> > + /* Results of reoptimizing a JOIN via JOIN::reoptimize(). */
> > + enum enum_reopt_result {
> > + REOPT_NEW_PLAN, /* there is a new reoptimized plan */
> > + REOPT_OLD_PLAN, /* no new improved plan can be found, use the old one */
> > + REOPT_ERROR, /* an irrecovarable error occured during reoptimization */
> > + REOPT_NONE /* not yet reoptimized */
> > + };
> > +
> > + /* Support for plan reoptimization with rewritten conditions. */
> > + enum_reopt_result reoptimize(Item *added_where, table_map join_tables,
> > + Query_plan_state *save_to);
> > + void save_query_plan(Query_plan_state *save_to);
> > + void restore_query_plan(Query_plan_state *restore_from);
> > + /* Choose a subquery plan for a table-less subquery. */
> > + bool choose_tableless_subquery_plan();
> > +
> > public:
> > JOIN_TAB *join_tab,**best_ref;
> > JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs
> > @@ -702,6 +747,13 @@
> > account the changes made by test_if_skip_sort_order()).
> > */
> > double best_read;
> > + /*
> > + Estimated result rows (fanout) of the whole query. If this is a subquery
psergey: I think it would be better to change "whole query" to "join
operation" or "the select" here.
timour:
Done.
> > + that is reexecuted multiple times, this value includes the estiamted # of
> > + reexecutions. This value is equal to the multiplication of all
> > + join->positions[i].records_read of a JOIN.
> > + */
> > + double record_count;
> > List<Item> *fields;
> > List<Cached_item> group_fields, group_fields_cache;
> > TABLE *tmp_table;
..
> > @@ -1233,6 +1313,9 @@
> > if (!inited)
> > {
> > inited=1;
psergey: I don't understand why this wasn't needed before MWL#89, but is
needed after MWL#89. Do you still remember why you've added it?
timour:
You could find out with 'bzr gannotate' :). Anyway, this is the commit:
--------------------------------------------
revno: 2842.3.5
committer: timour@xxxxxxxxxxxx
branch nick: 5.3-mwl89-lpb-676411
timestamp: Fri 2010-11-19 17:01:48 +0200
message:
Fix for LP BUG#676411 and MySQL BUG#52317
This is a backport of the fix for
MySQL BUG#52317: Assertion failing in Field_varstring::store () at field.cc:6833
The orginal comment by Oystein is:
In order for EXPLAIN to print const-refs, a Store_key_const_item object
is created. This is different for normal execution of subqueries where
a temporary store_key_item object is used instead. The problem is that
EXPLAIN will execute subqueries. This leads to a scenario where a
store_key_const_item object it told to write to its underlying field.
This results in a failing assert since the write set of the underlying
table does not reflect this.
The resolution is to do the same trick as for store_key_item::copy_inner().
That is, temporarily change the write set to allow writes to all columns.
This is only necessary in debug version since non-debug version does not
contain asserts on write_set.
--------------------------------------------
> > + TABLE *table= to_field->table;
> > + my_bitmap_map *old_map= dbug_tmp_use_all_columns(table,
> > + table->write_set);
> > if ((res= item->save_in_field(to_field, 1)))
> > {
> > if (!err)
Follow ups
References
