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

thank you for a comprehensive review.

On 20.10.10 23.13, Guilhem Bichot wrote:
> Hello Roy,
>
> Really good work. I hope we can close the remaining points in time before I go
> on vacation :-/
> I realize some of my comments are not requests below; to make it clear and given
> the short time available, I marked my comments with different tags:
> REQ means a request for a change, or a question to answer, or tell me why I'm
> wrong (i.e. something which I'd like to be solved before approving the patch)
> BLAH is an observation, which doesn't require any action.
>
> Roy Lyseng a écrit, Le 07.10.2010 17:19:
>> #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.
>> Bug#52068: Optimizer generates invalid semijoin materialization plan
>> When a subquery is subject to a semijoin optimization, it's tables
>
> REQ it's -> its

Fixed
>
>> are merged to the outer query and later are treated as regular tables. This
>> allows a bunch of optimizations to be applied, equality
>> propagation is among them. Equality propagation is done after query
>> execution plan is chosen. It substitutes fields from tables being
>> retrieved later for fields from tables being retrieved earlier.
>> However, it can't be applied as is to any semijoin table.
>> The semijoin materialization strategy differs from other semijoin
>> strategies that the data from materialized semijoin tables isn't used
>> directly but saved to a temporary table first.
>> The materialization isn't isolated in a separate step, it is done
>> inline within the nested loop execution.
>> When it comes to fetching rows from the first table in the block of
>> materialized semijoin tables, sub_select() function is called to
>> materialize the result of the subquery and save it in the
>> materialized table. Later, data from the materialized table is used
>> as they were regular table rows.
>
> REQ "as" -> "as if"

Fixed
>
>> Due to this we can't substitute fields that belong to the semi-join
>> for fields from outer query and vice versa. Example: suppose we have a join
>> order:
>> ot1 ot2 SJ-Mat(it1 it2 it3) ot3
>> and equality ot2.col = it1.col = it2.col
>> If we're looking for best substitute for 'it2.col', we should pick
>> it1.col and not ot2.col.
>> For a field that is not in a materialized semijoin we can use any field,
>> even those that are embedded in a materialized semijoin. This is because
>> such fields are "copied back" to their original join-tab structures when
>> the materialized temporary table is being read.
>> Now we have added another Item_equal::get_first() function that accepts
>> as a parameter a field being substituted and checks whether it belongs
>> to a materialized semijoin.
>> The field to substitute will be from the same materialized semijoin nest
>> (if supplied field is within such nest), otherwise it will be the first
>> field in the multiple equality.
>> The new checks rely on the first_sj_inner_tab and first_sj_inner_tab
>> fields of the join-tab. These fields are therefore set as soon as
>> possible after the join strategy is fixed.
>> Also fixed problem appearing in Bug#52068: When MaterializeScan
>> semijoin strategy was used and there were one or more outer dependent
>> tables before the semijoin tables, the scan over the materialized
>> table was not properly reset for each row of the prefix outer tables.
>> Also fixed problems with pushdown of SJM-aware predicates during
>> make_join_select(): wrong predicates were sometimes generated,
>> make_cond_after_sjm() was called at the wrong position, and
>> make_cond_after_sjm() was never actually considering the pushed-down
>> SJM predicates.
>
>> mysql-test/r/subquery_sj_none_jcl7.result
>> 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.
>> Bug#52068: Optimizer generates invalid semijoin materialization plan
>> Results for three new tests added.
>> Some tests using semijoin materialization show that where clause
>> has moved from the outer query into the materialized inner query.
>> This is caused by the changed call to get_first() in
>> eliminate_item_equal().
>> 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.
>
>> sql/sql_select.cc
>> 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.
>> Bug#52068: Optimizer generates invalid semijoin materialization plan
>> Setting fields first_sj_inner_tab and last_sj_inner_tab moved from
>> setup_semijoin_dups_elimination() to get_best_combination(), so they
>> are set as early as possible after join order optimization.
>> In make_join_select(), the test that determined when to pushdown
>> SJM-specific predicates was wrong, in addition to approving the
>> comments.
>
> REQ approving -> improving?

Bummer...
>
>> The logic of eliminate_item_equal() has been simplified and
>> adjusted so that it generates equalities that are useful also
>> when the semijoin materialization strategy is being used.
>> Some simplification was possible by taking advantage of the new
>> Item_equal::get_first() function.
>> In sub_select_sjm(), moved code that initializes the scan over the
>> materialized table so that it is now performed for each scan of
>> table, instead of only for the first scan.
>> In make_cond_for_table_from_pred(), a number of comments has been
>> added, and TAB characters are replaced by spaces.
>> In make_cond_after_sjm(), make sure that it handles equalities
>> generated for semijoin materialization (with marker=3).
>> Otherwise, removed marker optimizations for this function, as
>> it will only be called once per materialized semijoin nest
>> in a query. Added comments and removed TAB characters.
>
>
>> === modified file 'sql/item_cmpfunc.cc'
>> --- a/sql/item_cmpfunc.cc 2010-09-28 15:17:29 +0000
>> +++ b/sql/item_cmpfunc.cc 2010-10-07 15:15:10 +0000
>> @@ -5816,3 +5816,101 @@ void Item_equal::print(String *str, enum
>> str->append(')');
>> }
>>
>> +
>> +/**
>> + Get the first field of multiple equality, use for semantic checking.
>> +
>> + @retval First field in the multiple equality.
>> +*/
>> +
>> +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.
>
>> +}
>> +
>> +/**
>> + Get the first equal field of multiple equality, use when execution order
>> + must be considered (see details below).
>> +
>> + @param field field to get substitution field for, which must be
>> + present within the multiple equality itself.
>> +
>> + @retval Found first field in the multiple equality.
>> +
>> + @details Get the first field of multiple equality that is equal to the
>> + given field. In order to make semijoin materialization strategy work
>> + correctly we can't propagate equal fields between a materialized semijoin
>> + and the outer query (or any other semijoin) unconditionally.
>> + Thus the field is returned according to following rules:
>> +
>> + 1) If the given field belongs to a materialized semijoin then the
>> + first field in multiple equality which belong to the same semijoin
>> + is returned.
>> + 2) If the given field doesn't belong to a materialized semijoin then
>> + the first field in the multiple equality is returned.
>> +*/
>> +
>> +Item_field* Item_equal::get_first(Item_field *field)
>
> REQ the parameter can be declared as
> "const Item_field *field"

Fixed.
>
>> === modified file 'sql/item_cmpfunc.h'
>> --- a/sql/item_cmpfunc.h 2010-08-12 00:26:10 +0000
>> +++ b/sql/item_cmpfunc.h 2010-10-07 15:15:10 +0000
>> @@ -1634,7 +1634,8 @@ public:
>> void add(Item_field *f);
>> uint members();
>> bool contains(Field *field);
>> - Item_field* get_first() { return fields.head(); }
>> + Item_field* get_first();
>> + Item_field* get_first(Item_field *field);
>
> BLAH As already discussed in a previous round of comments, I wanted to add
> "const" at the declarations' end, to stress that those only read data, but as
> you observed, compiler does not permit. To be more precise (I always get caught
> by this): declaring
> Item_field* get_first() const
> {
> return fields.head();
> }
> means that "fields" becomes a constant list; thus head() can be applied to it
> only if it is a const function, which it is not. If I make head() be a const
> function in sql_list.h, it gets better. But not quite:
> the iterator in get_first(field) is then a problem:
> List_iterator<Item_field> it(fields);
> because as "fields" is a constant list, it can be iterated only with a
> const_iterator, and we don't have that in sql_list.h. I gave up :-)

</BLAH>
>
>> === 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.
>
>> @@ -8639,16 +8635,13 @@ static bool fix_semijoin_strategies_for_
>>
>> static bool get_best_combination(JOIN *join)
>> {
>> - uint i,tablenr;
>> table_map used_tables;
>> - JOIN_TAB *join_tab,*j;
>> KEYUSE *keyuse;
>> - uint table_count;
>> + uint table_count= join->tables;
>
> REQ make it "const uint"

Done.
>
>> + case SJ_OPT_FIRST_MATCH:
>> + /*
>> + Remember the first and last semijoin inner tables; this serves to tell
>> + a JOIN_TAB's semijoin strategy (like in check_join_cache_usage()).
>> + */
>> + JOIN_TAB *last_sj_tab= tab + pos->n_sj_tables - 1;
>> + JOIN_TAB *last_sj_inner=
>> + (pos->sj_strategy == SJ_OPT_DUPS_WEEDOUT) ?
>> + /* Range may end with non-inner table so cannot set last_sj_inner_tab */
>> + NULL : last_sj_tab;
>> + for (JOIN_TAB *tab_in_range= tab; + tab_in_range <= last_sj_tab; +
>> tab_in_range++)
>
> REQ there is trailing whitespace in those for() lines.

Good observation.
>
>> @@ -9678,32 +9710,32 @@ static bool make_join_select(JOIN *join,
>
> REQ You seem to understand well what make_join_select() does; could you
> please add a short doxygen comment for it?

Done.
>
>> DBUG_ASSERT(save_used_tables ? tab->emb_sj_nest != NULL : TRUE);
>
> BLAH save_used_tables is set here:
> if (tab->emb_sj_nest &&
> tab->emb_sj_nest->sj_mat_exec &&
> !(used_tables & tab->emb_sj_nest->sj_inner_tables))
> {
> save_used_tables= used_tables;
> At your option, the two first expressions in the if() clause could maybe
> be replaced with
> sj_is_materialize_strategy(tab->get_sj_strategy())

Done.
>
>> - if (save_used_tables && !(used_tables & -
> ~(tab->emb_sj_nest->sj_inner_tables |
>> - join->const_table_map | PSEUDO_TABLE_BITS)))
>
> REQ Do I understand correctly: this test was wrong because, if there were 2
> inner tables and we were positioned after the first and before the second,
> used_tables would be:
> const tables + some pseudo table bits + first inner
> and so the if() above would be true, which is not correct, as we are not
> yet at the last inner so should not call make_cond_after_sjm()?
> Is that what you call "make_cond_after_sjm() was called at the wrong
> position" in the commit comment?

Yes, that was the problem.

> I put back the old code, ran the test suite, and no SELECT gave bad
> results. Is it normal? Maybe we need some test to cover that?

I hit this problem and fixed it before attacking the problems in 
make_cond_after_sjm(), so the code was basically non-functional when I did this.

I tested it now, and it breaks for me with wrong results.

In the case of the ot1 - it2 - it3 - ot4 join, it will enter the SJM nest on 
it2, and call make_cond_after_sjm() with the prefix ot1 - it2. Furthermore, it 
will update used_tables so that the next run through the loop will be with the 
prefix ot1 - it2 - it3, when it should generate any conditions for it2 - it3.
>
>> + /*
>> + 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...

>
>> + 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...

It means that if (head == item), "item" must be the first item that is within an 
SJM nest. 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.

>
>> + The design is not pretty, but the alternative is to have a hairy
>> + check for SJM-related conditions inside make_cond_for_table().
>> + */
>> + eq_item->marker= 3;
>> + }
>> eq_item->set_cmp_func();
>> eq_item->quick_fix_field();
>> }
>> @@ -16897,21 +16927,8 @@ sub_select_sjm(JOIN *join, JOIN_TAB *joi
>> Ok, materialization finished. Initialize the access to the temptable
>> */
>> sjm->materialized= TRUE;
>> +
>> join_tab->read_record.read_record= join_no_more_records;
>> - if (sjm->is_scan)
>> - {
>> - /* Initialize full scan */
>> - JOIN_TAB *last_tab= join_tab + (sjm->table_count - 1);
>> - init_read_record(&last_tab->read_record, join->thd,
>> - sjm->table, NULL, TRUE, TRUE, FALSE);
>> -
>> - DBUG_ASSERT(last_tab->read_record.read_record == rr_sequential);
>> - last_tab->read_first_record= join_read_record_no_init;
>> - last_tab->read_record.copy_field= sjm->copy_field;
>> - last_tab->read_record.copy_field_end= sjm->copy_field +
>> - sjm->table_cols.elements;
>> - last_tab->read_record.read_record= rr_sequential_and_unpack;
>> - }
>> }
>>
>> if (sjm->is_scan)
>> @@ -16919,6 +16936,15 @@ sub_select_sjm(JOIN *join, JOIN_TAB *joi
>> /* Do full scan of the materialized table */
>
> REQ I'd change comment to something like:
> /* For each prefix partial record, initialize full scan of the
> materialized table */

Done, with two small modifications.
>
>> JOIN_TAB *last_tab= join_tab + (sjm->table_count - 1);
>>
>> + init_read_record(&last_tab->read_record, join->thd,
>> + sjm->table, NULL, TRUE, TRUE, FALSE);
>> +
>> + last_tab->read_first_record= join_read_record_no_init;
>> + last_tab->read_record.copy_field= sjm->copy_field;
>> + last_tab->read_record.copy_field_end= sjm->copy_field +
>> + sjm->table_cols.elements;
>> + last_tab->read_record.read_record= rr_sequential_and_unpack;
>> +
>> Item *save_cond= last_tab->select_cond;
>
> BLAH Out of curiosity, I don't understand why we need to save/restore the cond;
> no subquery_sj test fails without this. But this is not related to your patch,
> you can keep it.

Probably not, but like you said, it's not related to this bug ;)
>
>> last_tab->set_select_cond(sjm->join_cond, __LINE__);
>> rc= sub_select(join, last_tab, end_of_records);
>> @@ -18837,13 +18863,14 @@ static bool replace_subcondition(JOIN *j
>> cond Condition to analyze
>> tables Tables for which "current field values" are available
>> used_table Table that we're extracting the condition for (may - also include
>> PSEUDO_TABLE_BITS
>> + also include PSEUDO_TABLE_BITS, and may be zero)
>> exclude_expensive_cond Do not push expensive conditions
>>
>> DESCRIPTION
>> Extract the condition that can be checked after reading the table
>> specified in 'used_table', given that current-field values for tables
>> specified in 'tables' bitmap are available.
>> + If 'used_table' is 0 (zero), extract conditions for all tables in 'tables'.
>
> BLAH "0 (zero)" is funny; keep it if you like, or just choose between 0 and zero.

Replaced with 0.
>
>> static Item *
>> make_cond_for_table_from_pred(Item *root_cond, Item *cond,
>> table_map tables, table_map used_table,
>> bool exclude_expensive_cond)
>> {
>> - if (used_table && !(cond->used_tables() & used_table)
> &&
>> - /*
>> - Exclude constant conditions not checked at optimization time if
>> + /*
>> + Ignore this condition if
>> + 1. We are extracting conditions for a specific table, and
>> + 2. that table is not referenced by the condition, and
>> + 3. exclude constant conditions not checked at optimization time if
>> the table we are pushing conditions to is the first one.
>> As a result, such conditions are not considered as already checked
>> and will be checked at execution time, attached to the first table.
>
> BIG PRAISE thank for the wealth of new comments, which do make those functions
> more understandable for me. Simply put: before you added comments, I never dared
> to parse those bitmap &~ things.

Thank you, it is mutual :)
>
>> -
>> + */
>> + if (used_table && // 1
>> + !(cond->used_tables() & used_table) && // 2
>> + /*
>> psergey: TODO: "used_table & 1" doesn't make sense in nearly any
>> context. Look at setup_table_map(), table bits reflect the order the tables
>> were encountered by the parser. Check what we should
>> replace this condition with.
>> */
>> - !((used_table & 1) && cond->is_expensive()))
>> - return (Item*) 0; // Already checked
>> + !((used_table & 1) && cond->is_expensive())) // 3
>> + return (Item*) NULL; // Already checked
>
> REQ in all places where (Item*)0 is changed to (Item*)NULL, I'd go even
> further and just use NULL without a cast; my gcc seems to be ok with it.

Fixed.
>
>> else
>> - { // Or list
>> + { // Or list
>> Item_cond_or *new_cond=new Item_cond_or;
>> if (!new_cond)
>> - return (Item*) 0; // OOM /* purecov: inspected */
>> + return (Item*) NULL;
>> List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
>> Item *item;
>> while ((item=li++))
>> {
>> - Item *fix=make_cond_for_table_from_pred(root_cond, item,
>> + Item *fix=make_cond_for_table_from_pred(root_cond, item,
>> tables, 0L,
>
> BLAH It took me a while to figure out why when splitting OR we pass 0L, whereas
> when splitting AND we pass used_table; with an example I was able to understand
> (boils down to: AND-ed parts can be pushed down independently but not OR-ed
> parts), but I cannot find a short comment which would clearly explain it and
> could be added in code.

Food for a later fix, I guess...
>
>> exclude_expensive_cond);
>> if (!fix)
>> - return (Item*) 0; // Always true
>> + return (Item*) NULL; // Always true
>> new_cond->argument_list()->push_back(fix);
>> }
>> /*
>> @@ -18952,20 +18985,25 @@ make_cond_for_table_from_pred(Item *root
>> }
>>
>> /*
>> - Because the following test takes a while and it can be done
>> - table_count times, we mark each item that we have examined with the result
>> - of the test
>> - */
>> + Omit this condition if
>> + 1. It has been marked as omittable before, or
>> + 2. All tables referred by the condition are not available, or
>
> REQ I'd change "All" to "Some" in (2).

Done.
>
>> + 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...
>
>> + */
>> + 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...
>
>> + (cond->used_tables() & ~tables) || // 2
>> + (!used_table && exclude_expensive_cond &&
> cond->is_expensive())) // 3
>> + return (Item*) NULL;
>>
>> - if (cond->marker == 3 || (cond->used_tables() & ~tables) ||
>> - /*
>> - When extracting constant conditions, treat expensive conditions as
>> - non-constant, so that they are not evaluated at optimization time.
>> - */
>> - (!used_table && exclude_expensive_cond &&
> cond->is_expensive()))
>> - return (Item*) 0; // Can't check this yet
>> + /*
>> + Extract this condition if
>> + 1. It has already been marked as applicable, or
>> + 2. It is not a <comparison predicate> (=, <, >, <=, >=,
> <=>)
>> + */
>> if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK)
>> - return cond; // Not boolean op
>> + return cond;
>>
>> /* Remove equalities that are guaranteed to be true by use of 'ref' access
>> @@ -18993,19 +19031,19 @@ make_cond_for_table_from_pred(Item *root
>> Item *left_item= ((Item_func*) cond)->arguments()[0]->real_item();
>> Item *right_item= ((Item_func*) cond)->arguments()[1]->real_item();
>> if (left_item->type() == Item::FIELD_ITEM &&
>> - test_if_ref(root_cond, (Item_field*) left_item,right_item))
>> + test_if_ref(root_cond, (Item_field*) left_item,right_item))
>> {
>> - cond->marker=3; // Checked when read
>> - return (Item*) 0;
>> + cond->marker=3; // Condition can be omitted
>> + return (Item*) NULL;
>> }
>> if (right_item->type() == Item::FIELD_ITEM &&
>> - test_if_ref(root_cond, (Item_field*) right_item,left_item))
>> + test_if_ref(root_cond, (Item_field*) right_item,left_item))
>> {
>> - cond->marker=3; // Checked when read
>> - return (Item*) 0;
>> + cond->marker=3; // Condition can be omitted
>
> BLAH I wondered: but who checks this marker later? Looks like in
> make_join_select(), make_cond_for_table() may be called with the same predicate
> again and again: for example, one "normal call" and one call for engine
> condition pushdown.
> Apparently this marker thing is only an optimization.

Yes, it is only supposed to be used for local matters, such as inside 
make_join_select() and make_cond_for_table(). Which is why I find it nice to be 
able to remove it from eliminate_item_equal().
>
>> + 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)
>
> REQ the code of make_cond_after_sjm() is 90% copy-paste from
> make_cond_for_table_from_pred() (even some indentation errors are
> identical); could you please put a comment in both functions which
> suggests to keep them in sync?

Yes, will do.
>
> 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.

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.
>
> I looked at the changes in pushed conditions introduced by the patch (by
> "pushed", I mean conditions which we attach to each table, evaluated after a row
> has been read from the table; not index/engine condition pushdown). It will be
> more understandable for you, if you use the same method as I did: I prepared a
> playground for this. I have prepared a custom version of the optimizer trace
> tree (you can get it from tree mysql-next-mr-guilhem at usual machine). It has
> your patch applied, both the code and test file changes. As for the result
> files, I ran
> ./mtr --record t/subquery_sj*.test --opt-trace-protocol
> which generates the optimizer trace of each SELECT or EXPLAIN SELECT (good work
> Jorgen). So the result files show conditions "after your patch".
> If you then revert only the code piece of your patch by applying the patch
> attached to this mail, you can re-run tests and see the differences; the
> differences in the optimizer traces will show what condition
> disappears/appears/moves. Remember: the "result" file is after-your-patch; the
> "reject" file is before-your-patch. The interesting test is subquery_sj_mat. For
> browsing differences, I warmly recommend a GUI diff tool, which shows line
> numbers and can do text searches (I use kdiff3). Please ignore the differences
> of records' counts in the trace, they are probably due to InnoDB's "random"
> statistics. Conditions generated by make_cond_after_sjm() are named
> "attached_after_semijoin_materialization" in the optimizer trace.
>
> Below I go through some noteworthy changes of subquery_sj_mat which I observed
> by the procedure above.
>
> 1) I see a good change, the last query of the test for BUG#52068 (line 109510 of
> the result file): after your patch we have make_cond_after_sjm() which produces
> "it2.a=ot1.a" which is then attached to the mat-scan-SJM, so tested before we
> reach the last table in plan (ot4). That is a win.
>
> 2) Another win, the last query of the test for BUG#45174 (line 108683 of the
> result file): your patch moves a condition from after-SJM to inside-SJM (from
> "attached_after_semijoin_materialization" to "attached"-to-t2)
>
> REQ 3) This time make_cond_after_sjm() produces a condition only after your
> patch: at line 2359 of the result file:
> "select * from t2 where t2.a in (select a from t1)"
> mat-lookup is used, which, I guess, looks up value of t2.a in the materialized
> table, but make_cond_after_sjm() produces
> "t1.a=t2.a"
> which is think is a superfluous condition to check (as index lookup should
> already guarantee this?).
> There are other examples, in the queries which follow the one above (just scroll
> down in the diff). Unfortunately it seems to be often such unneeded conditions
> (repeating what the index lookup already implements), for mat-lookup, and added
> by the patch.
> Somehow it makes the questionable comment ("a regular semi-join etc") be wrong
> more often.
> On the one hand, I don't see this as a big problem: I'm not sure this is a real
> speed penalty to check this, even for every row.
> On the other hand, I cannot explain why we see this change. Could you please
> have a look, to be sure?

Answered by Guilhem :)
>
> REQ 4) at line 65381 of the result file: query
> explain select *
> from t0 where a in
> (select t2.a+t3.a from t1 left join (t2 join t3) on t2.a=t1.a and t3.a=t1.a);
> is worrying: before the patch it used to have a condition attached to t3, i.e.
> evaluated inside materialization, which had the potential to make the
> materialized table smaller. The patch moves this condition out into a
> make_cond_after_sjm() condition (so, the materialized table will be bigger). I
> don't understand what can explain the move, and if it has to be. I don't think
> it can be be explained the same way as the "kp1<20" move which we discussed in a
> previous mail. I don't see that equality propagation plays a direct role here.
> Could you please investigate this?

Answered by Guilhem :)
>
> 5) In subquery_sj_mat, line 65488 of the result file, query
> explain extended select left(a1,7), left(a2,Y)
> from t1_16
> where a1 in (select b1 from t2_16 where b1 > '0')
> we have MatScan; your patch adds a make_cond_after_sjm condition, which seems to
> be key to give correct query results. I don't really understand why; I thought
> that the make_cond_after_sjm condition was just an optimization. Bah, no need to
> research, this is a good thing.

No, it is a necessary condition (!) for SJM-scan...
>
>> {
>> + 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. It could mean that cond is passed as an 
in/out argument. Comments are welcome.
>
>> if ((!(cond->used_tables() & ~tables) || !(cond->used_tables() &
> ~sjm_tables)))
>> - return (Item*) 0; // Already checked
>> + return (Item*) NULL; // Already checked
>> if (cond->type() == Item::COND_ITEM)
>> {
>> if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
>> @@ -19044,49 +19084,49 @@ make_cond_after_sjm(Item *root_cond, Ite
>> /* Create new top level AND item */
>> Item_cond_and *new_cond=new Item_cond_and;
>> if (!new_cond)
>> - return (Item*) 0; // OOM /* purecov: inspected */
>> + return (Item*) NULL;
>> List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
>> Item *item;
>> while ((item=li++))
>> {
>> - Item *fix=make_cond_after_sjm(root_cond, item, tables, sjm_tables);
>> - if (fix)
>> - new_cond->argument_list()->push_back(fix);
>> + Item *fix=make_cond_after_sjm(root_cond, item, tables, sjm_tables);
>> + if (fix)
>> + new_cond->argument_list()->push_back(fix);
>> }
>> switch (new_cond->argument_list()->elements) {
>> case 0:
>> - return (Item*) 0; // Always true
>> + return (Item*) NULL; // Always true
>> case 1:
>> - return new_cond->argument_list()->head();
>> + return new_cond->argument_list()->head();
>> default:
>> /*
>> - Item_cond_and do not need fix_fields for execution, its parameters
>> - are fixed or do not need fix_fields, too
>> + Item_cond_and do not need fix_fields for execution, its parameters
>> + are fixed or do not need fix_fields, too
>> */
>> - new_cond->quick_fix_field();
>> - new_cond->used_tables_cache=
>> - ((Item_cond_and*) cond)->used_tables_cache &
>> - tables;
>> - return new_cond;
>> + new_cond->quick_fix_field();
>> + new_cond->used_tables_cache=
>> + ((Item_cond_and*) cond)->used_tables_cache &
>> + tables;
>> + return new_cond;
>> }
>> }
>> else
>> - { // Or list
>> + { // Or list
>> Item_cond_or *new_cond=new Item_cond_or;
>> if (!new_cond)
>> - return (Item*) 0; // OOM /* purecov: inspected */
>> + return (Item*) NULL;
>> List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
>> Item *item;
>> while ((item=li++))
>> {
>> - Item *fix= make_cond_after_sjm(root_cond, item, tables, 0L);
>> - if (!fix)
>> - return (Item*) 0; // Always true
>> - new_cond->argument_list()->push_back(fix);
>> + Item *fix= make_cond_after_sjm(root_cond, item, tables, 0L);
>> + if (!fix)
>> + return (Item*) NULL; // Always true
>> + new_cond->argument_list()->push_back(fix);
>> }
>> /*
>> - Item_cond_and do not need fix_fields for execution, its parameters
>> - are fixed or do not need fix_fields, too
>> + Item_cond_and do not need fix_fields for execution, its parameters
>> + are fixed or do not need fix_fields, too
>> */
>> new_cond->quick_fix_field();
>> new_cond->used_tables_cache= ((Item_cond_or*) cond)->used_tables_cache;
>> @@ -19095,16 +19135,10 @@ make_cond_after_sjm(Item *root_cond, Ite
>> }
>> }
>>
>> - /*
>> - Because the following test takes a while and it can be done
>> - table_count times, we mark each item that we have examined with the result
>> - of the test
>> - */
>> -
>> - if (cond->marker == 3 || (cond->used_tables() & ~(tables |
> sjm_tables)))
>> - return (Item*) 0; // Can't check this yet
>> - if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK)
>> - return cond; // Not boolean op
>> + if (cond->used_tables() & ~(tables | sjm_tables))
>> + return (Item*) NULL; // Can't check this yet
>> + if (cond->eq_cmp_result() == Item::COND_OK)
>> + return cond; // Not a <comparison predicate>
>>
>> /* Remove equalities that are guaranteed to be true by use of 'ref' access
>> @@ -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.
>
> 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 :)

Thanks,
Roy
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