List:Commits« Previous MessageNext Message »
From:Guilhem Bichot Date:October 21 2010 8:30pm
Subject:Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)
Bug#45174 Bug#50019 Bug#52068
View as plain text  
Hi again,

Roy Lyseng a écrit, Le 21.10.2010 16:18:
>>> #At file:///home/rl136806/mysql/repo/mysql-work5/ based on
>>> revid:tor.didriksen@stripped
>>>
>>> 3260 Roy Lyseng 2010-10-07
>>> Bug#45174: Incorrectly applied equality propagation caused wrong result
>>> on a query with a materialized semi-join.
>>> Bug#50019: Wrong result for IN-query with materialization.

>>> Ex: select * from ot where a in(select b from it where b>0);
>>> The clause "b>0" is now evaluated on the inner query materialization.
>>> Performance-wise this is never worse when using MaterializeScan and
>>> usually better for MaterializeLookup. For the latter strategy, the
>>> best possible solution is probably to evaluate the clause in both
>>> queries, this can be subject for a later feature development.
>>
>> REQ question: should we create a WL for this later hypothetical 
>> development?
> 
> Could be a good idea. We may also combine this with work that converts 
> an SJM operation to a materialized-derived-query-like execution plan. 
> Then most of this SJM special handling will no longer be needed.

I recommend writing down your ideas in some WL when you get the time. I 
think the materialized-derived-query-like idea is worth it.

>>> === modified file 'sql/item_cmpfunc.cc'
>>> +Item_field* Item_equal::get_first()
>>> +{
>>> + return fields.head();
>>
>> REQ This one is so small that I would leave it inline as it was (we 
>> can move the
>> new comment to item_cmpfunc.h)...?
> 
> I did it for symmetry reasons... But I can move it back.

then I think it's better to move it back, in order to have it inline.

>>> === modified file 'sql/sql_select.cc'
>>> --- a/sql/sql_select.cc 2010-09-30 14:53:11 +0000
>>> +++ b/sql/sql_select.cc 2010-10-07 15:15:10 +0000
>>> @@ -4338,7 +4330,8 @@ int pull_out_semijoin_tables(JOIN *join)
>>> pointers.
>>> */
>>> child_li.remove();
>>> - upper_join_list->push_back(tbl);
>>> + if (upper_join_list->push_back(tbl))
>>> + DBUG_RETURN(TRUE);
>>
>> REQ I think we should restore the active arena before returning TRUE, 
>> even
>> though this is an error. Who knows what happens if we don't restore 
>> it... Also,
>> I would add unlikely() around the if(), it should happen rarely.
> 
> Fixed the arena problem.
> If you don't mind, I'll skip unlikely here, as this call is not 
> performance-sensitive.

as you like.

>>> @@ -9678,32 +9710,32 @@ static bool make_join_select(JOIN *join,

>>> + /*
>>> + 1. We are inside a materialized semijoin nest, and
>>> + 2. All inner tables of the nest are covered.
>>> + */ + if (save_used_tables && // 1
>>> + !(tab->emb_sj_nest->sj_inner_tables & ~used_tables)) // 2
>>> {
>>> /*
>>> - We have reached the end of semi join nest. That is, the join order
>>
>>> @@ -10866,8 +10898,7 @@ make_join_readinfo(JOIN *join, ulonglong
>>> uint last_sjm_table= MAX_TABLES;
>>> DBUG_ENTER("make_join_readinfo");
>>>
>>> - if (!join->select_lex->sj_nests.is_empty() &&
>>> - setup_semijoin_dups_elimination(join, options, no_jbuf_after))
>>> + if (setup_semijoin_dups_elimination(join, options, no_jbuf_after))
>>> DBUG_RETURN(TRUE); /* purecov: inspected */
>>>
>>> for (i=join->const_tables ; i < join->tables ; i++)
>>> @@ -12516,17 +12547,18 @@ Item *eliminate_item_equal(Item *cond, C
>>> Item_equal *item_equal)
>>> {
>>> List<Item> eq_list;
>>> - Item_func_eq *eq_item= 0;
>>> + Item_func_eq *eq_item= NULL;
>>> if (((Item *) item_equal)->const_item() &&
> !item_equal->val_int())
>>> return new Item_int((longlong) 0,1); Item *item_const= 
>>> item_equal->get_const();
>>> Item_equal_iterator it(*item_equal);
>>> Item *head;
>>> - if (item_const)
>>> - head= item_const;
>>> - else
>>> + if (!item_const)
>>> {
>>> - head= item_equal->get_first();
>>> + /*
>>> + If there is a const item, match all field items with the const item,
>>> + otherwise match the second and subsequent field items with the 
>>> first one:
>>> + */
>>> it++;
>>> }
>>> Item_field *item_field;
>>> @@ -12537,7 +12569,7 @@ Item *eliminate_item_equal(Item *cond, C
>>> if (upper)
>>> { if (item_const && upper->get_const())
>>> - item= 0;
>>> + item= NULL;
>>> else
>>> {
>>> Item_equal_iterator li(*item_equal);
>>> @@ -12552,57 +12584,55 @@ Item *eliminate_item_equal(Item *cond, C
>>> {
>>> if (eq_item)
>>> eq_list.push_back(eq_item);
>>> +
>>> /*
>>> - item_field might refer to a table that is within a semi-join
>>> - materialization nest. In that case, the join order looks like this:
>>> + item_field may refer to a table that is within a semijoin
>>> + materialization nest. In that case, the join order may look like:
>>>
>>> - outer_tbl1 outer_tbl2 SJM (inner_tbl1 inner_tbl2) outer_tbl3 + ot1 
>>> ot2 SJM
>>> (it1 it2) ot3
>>> - We must not construct equalities like + We must not construct general
>>> equalities like
>>> - outer_tbl1.col = inner_tbl1.col + ot1.col = it1.col
>>> because they would get attached to inner_tbl1 and will get evaluated
>>> during materialization phase, when we don't have current value of
>>> - outer_tbl1.col.
>>> + ot1.col. When such equalities are generated, add a special marker to
>>> + the condition so that it will be evaluated after the inner tables
>>> + have been materialized, and the materialized table is joined with the
>>> + outer tables.
>>> + */
>>> +
>>> + bool need_marker= FALSE;
>>> + /*
>>> + If there is a const item, match against this one.
>>> + Otherwise, match against the first field item in the multiple 
>>> equality,
>>> + unless the item is within a materialized semijoin nest, where we match
>>> + against the first item within the SJM nest (if the item is not the 
>>> first
>>> + item within the SJM nest), or match against the first item in the
>>> + list (if the item is the first one in the SJM list).
>>
>> REQ About the final "or match..." part above: isn't it strange to build
>> equality fo=fi where "fi" is a field of the first SJM inner table, and 
>> "fo" is a
>> field of an outer, preceding table? Doesn't it go against the idea 
>> that outer
>> and inner fields should be separated when propagating
>> equalities? Why is the _first_ field of the SJM an exception?
> 
> These fields are all in one multiple equality, so that means that the 
> equality has to be enforced by the correct number of equality 
> predicates, and when necessary data is available. This is priority 1.
> 
> Priority 2 is to evaluate each equality as early as possible, this means 
> that we try to substitute a field reference with the first field 
> reference in the multiple equality list (with some exceptions).
> 
> The reason for the special treatment of the first equality in the SJM 
> nest is that it serves two purposes: It is a substitution point for all 
> equal fields located inside the SJM nest, and it is used to equate rows 
> within the SJM nest with rows outside of the nest.
> 
> Hope this explanation helps...

What I don't understand is why here it's not evil to equate outer fields 
with inner fields. I thought doing this was the cause of BUG#45174?
If we here create equality ot.a=it1.a, why won't this equality be used 
when materializing the table and produce a bug? There is even a comment 
in this same function which says "we must not construct general 
equalities like ot1.col=it1.col"...?

>>> + The latter equalities are the ones that must be tagged with a marker,
>>> + to prevent them from being evaluated at the wrong place.
>>> */
>>> - TABLE_LIST *emb_nest= - 
>>> item_field->field->table->pos_in_table_list->embedding;
>>> - if (!item_const && emb_nest && emb_nest->sj_mat_exec)
>>> + head= item_const ? item_const : item_equal->get_first(item);
>>> + if (head == item)
>>
>> REQ this if(head==item) branch, I don't understand.
> 
> Notice that we skip the list head when there is no const item...

yes, makes sense to favour const item.

> It means that if (head == item), "item" must be the first item that is 
> within an SJM nest.

Can't it instead be, in some cases, that "item" is merely the first of 
all items of the Item_equal?

> This is the case where we need to match against the 
> head of the list (which must be outside of the SJM nest).

>>
>>> {
>>> - /* - Find the first equal expression that refers to a table that is
>>> - within the semijoin nest. If we can't find it, do nothing
>>> - */
>>> - List_iterator<Item_field> fit(item_equal->fields);
>>> - Item_field *head_in_sjm;
>>> - bool found= FALSE;
>>> - while ((head_in_sjm= fit++))
>>> - {
>>> - if (head_in_sjm->used_tables() & emb_nest->sj_inner_tables)
>>> - {
>>> - if (head_in_sjm == item_field)
>>> - {
>>> - /* This is the first table inside the semi-join*/
>>> - eq_item= new Item_func_eq(item_field, head);
>>> - /* Tell make_cond_for_table don't use this. */
>>> - eq_item->marker=3;
>>> - }
>>> - else
>>> - {
>>> - eq_item= new Item_func_eq(item_field, head_in_sjm);
>>> - found= TRUE;
>>> - }
>>> - break;
>>> - }
>>> - }
>>> - if (!found)
>>> - continue;
>>> + head= item_equal->get_first();
>>> + need_marker= TRUE;
>>> }
>>> - else
>>> - eq_item= new Item_func_eq(item_field, head);
>>> + eq_item= new Item_func_eq(item_field, head);
>>> if (!eq_item)
>>> return 0;
>>> + if (need_marker)
>>> + {
>>> + /*
>>> + Setting 'marker= 3' means that make_cond_for_table() will ignore this
>>> + condition, but make_cond_after_sjm() will pick it up.
>>
>> REQ why is it needed to make make_cond_for_table() ignore this 
>> first-table
>> condition (I see a comment says that otherwise the condition would be 
>> evaluated
>> at the wrong place?).
>> I removed this "if(need_marker)" block, and no test output changed. 
>> Could you
>> please give an example, possibly add it to a test file to improve 
>> coverage?
> 
> I think that I have misunderstood the use of marker for SJM-related 
> conditions.
> 
> I assumed that setting marker=3 was to prevent make_cond_for_table() in 
> picking up the condition. However, make_cond_for_table() will never pick 
> up the condition in any case, because the condition's used_tables will 
> not match the table set supplied to make_cond_for_table(). Hence, I 
> propose to remove the need_marker variable and setting marker in 
> eliminate_item_equal(), as I do not see that it has any function.

proposal accepted.

>>> + 3. We are extracting constant conditions, the condition is
>>> + considered 'expensive', and we want to delay evaluation of such + 
>>> conditions
>>> to the execution phase.
>>
>> REQ Actually, "!used_table" may not always mean "extracting constant
>> condition"; we see that used_table==0 when we split an OR a few lines
>> above in the same function; and your comment describes used_table==0 as
>> "extract conditions for all tables in 'tables'".
> 
> Done. I am not sure the comment is 100% correct, but you may consider it...

ok, I'll check the new commit when it arrives.

>>
>>> + */
>>> + if (cond->marker == 3 || // 1
>>
>> REQ I think it's time to:
>> - add a doxygen comment near the declaration of "marker" in item.h
>> - make this an enum with meaningful names
> 
> Can we do this as a separate issue? This fix is getting huge already...

Yes, we can postpone this.

>>> + return (Item*) NULL;
>>> }
>>> }
>>> - cond->marker=2;
>>> + cond->marker=2; // Mark condition as applicable
>>> return cond;
>>> }
>>>
>>> @@ -19034,9 +19072,11 @@ static Item *
>>> make_cond_after_sjm(Item *root_cond, Item *cond, table_map tables,
>>> table_map sjm_tables)

>> This function has comment:
>> "A regular semi-join materialization is always non-correlated, ie
>> the subquery is always resolved by performing a lookup generated in
>> create_subquery_equalities, hence this function should never produce
>> any condition for regular semi-join materialization.
>> For a scan semi-join materialization, this function may return a 
>> condition to be
>> checked."
>>
>> but, I see that this function does produce a condition for
>> materialization-lookup in some cases, before and after your patch. For 
>> example,
>> in subquery_sj_mat.test, in the section for BUG#45174, for the 
>> "EXPLAIN SELECT
>> varchar_nokey etc", a condition is produced by make_cond_after_sjm(). 
>> This
>> happens before and after your patch, though the produced conditions are
>> different (and I find that your patch makes things better, as it 
>> manages to test
>> more conditions on t2 when materializing; more conditions at low 
>> levels, is
>> better :-).
>>
>> So this comment looks wrong, but this isn't due to your patch.
> 
> Nevertheless, it is a good catch, and it's definitely something that 
> should be kept in sync.

Then I suggest you amend this wrong comment.

> I eliminated the call to make_join_after_sjm() in case of SJM-lookup, to 
> eliminate generating the redundant after-condition. There were no result 
> changes after this fix.

ok

>>> {
>>> + if (!cond)
>>> + return (Item*) NULL;
>>
>> REQ but make_cond_for_table() behaves differently: it crashes if
>> cond is NULL. Can we make those two twins have the same expectations 
>> on 'cond'?
> 
> I think that if I should do that, then there are also quite a few "if 
> (cond)" expressions that can be removed from the callers. But I also 
> wonder if we should change these functions to follow "normal" error 
> handling practice, ie returning TRUE on failure and FALSE otherwise.

Apparently those functions may have only OS malloc errors (in "new"). In 
this case they return NULL. It will lead to bad query results (I tested: 
simulated failures of all "new" operator calls in those functions).
So indeed, returning NULL in this case is wrong, there should be an 
error instead.
It can either be a TRUE/FALSE bool error return code, then have "cond" 
as in/out parameter as you suggest. Or keep Item* as return code, but 
use a special impossible pointer to signal error; 0x1 is used in some 
places of the code already as an "impossible pointer value".
But I'm not asking you to implement any of this; the shortest course of 
action would probably be to just keep make_cond_after_sjm() as it was 
before the patch, i.e. require that cond!=NULL in this function.
Then I can file a bug about those OOM problems.
How does this sound?

> It 
> could mean that cond is passed as an in/out argument. Comments are welcome.

>>> @@ -19117,17 +19151,14 @@ make_cond_after_sjm(Item *root_cond, Ite
>>> if (left_item->type() == Item::FIELD_ITEM &&
>>> test_if_ref(root_cond, (Item_field*) left_item,right_item))
>>> {
>>> - cond->marker=3; // Checked when read
>>> return (Item*) 0;
>>> }
>>> if (right_item->type() == Item::FIELD_ITEM &&
>>> test_if_ref(root_cond, (Item_field*) right_item,left_item))
>>> {
>>> - cond->marker=3; // Checked when read
>>> return (Item*) 0;
>>> }
>>> }
>>> - cond->marker=2;
>>
>> REQ The commit comment says that we remove all the cond->marker things 
>> in this
>> function because we will not come back to this condition. Is it the 
>> only reason,
>> or also to support the "not pretty design" described earlier (which 
>> would be a
>> ugly ;-).
> 
> It also means that the un-pretty design is supported as little as possible.
> 
>> By default, I would have preferred make_cond_after_sjm() and
>> make_cond_for_table_from_pred() to stay as identical as possible, so 
>> that one
>> day we can merge them in one function and kill this horrible 
>> copy-pasting.
> 
> I can re-introduce the marker settings to make_cond_after_sjm(), to keep 
> them similar.

I think it would be great, to facilitate future unification.

>> BLAH In my simplified view, make_cond_after_sjm() should be as simple 
>> as a call to
>> make_cond_for_table_from_pred(cond, cond, 0, tables|sjm_tables);
>>
> 
> But it's not... We must ensure that we only handle conditions that span 
> both SJM-tables and non-SJM-tables... And please do not try to persuade 
> me to introduce another marker value :)

Then maybe make_cond_after_sjm() could look like this
{
   a first test specific of this function, to make sure we handle 
conditions than span etc etc;
   if test above is ok, then fall through into a call to 
make_cond_for_table_from_pred();
}
(this isn't something to do for you; just continuing the discussion).

PS: I have replaced the next-mr-guilhem tree with something else (I 
needed to test something on pb2 and this tree is registered in pb2; let 
me know if you need it again and I'll restore it).

-- 
Mr. Guilhem Bichot <guilhem.bichot@stripped>
Oracle / MySQL / Optimizer team, Lead Software Engineer
Bordeaux, France
www.oracle.com / www.mysql.com
Thread
bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260) Bug#45174Bug#50019 Bug#52068Roy Lyseng7 Oct
  • Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)Bug#45174 Bug#50019 Bug#52068Guilhem Bichot20 Oct
    • Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)Bug#45174 Bug#50019 Bug#52068Guilhem Bichot21 Oct
    • Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)Bug#45174 Bug#50019 Bug#52068Roy Lyseng21 Oct
      • Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)Bug#45174 Bug#50019 Bug#52068Guilhem Bichot21 Oct
        • Re: bzr commit into mysql-next-mr-bugfixing branch (roy.lyseng:3260)Bug#45174 Bug#50019 Bug#52068Roy Lyseng21 Oct