From: Date: April 5 2005 12:42am Subject: bk commit into 4.1 tree (sergefp:1.2170) BUG#8877 List-Archive: http://lists.mysql.com/internals/23637 X-Bug: 8877 Message-Id: <20050404224227.88F4B37BB5@newbox.mylan> Below is the list of changes that have just been committed into a local 4.1 repository of psergey. When psergey does a push these changes will be propagated to the main repository and, within 24 hours after the push, to the public repository. For information on how to access the public repository see http://dev.mysql.com/doc/mysql/en/installing-source-tree.html ChangeSet 1.2170 05/04/05 02:42:23 sergefp@stripped +2 -0 Fix for BUG#8877: Implementation of "Early NULL-values filtering for ref access" (attempt2+post-review fixes) 1. update_ref_and_keys() accumulates info about null-rejecting predicates in in KEY_FIELD::null_rejecting, add_key_part saves these to KEYUSE. 2. create_ref_for_key copies them to TABLE_REF. 3. add_not_null_conds adds "x IS NOT NULL" to join_tab->select_cond of appropiate JOIN_TAB members. Includes code cleanups: * add_key_field() params: s/COND/Item_func/ (as only Item_funcs are passed to it) * add_key_fields() params: JOIN_TAB *stat removed (wasn't used) sql/sql_select.h 1.73 05/04/05 02:42:20 sergefp@stripped +10 -0 Fix for BUG#8877: Implementation of "Early NULL-values filtering for ref access" (attempt2) sql/sql_select.cc 1.392 05/04/05 02:42:20 sergefp@stripped +152 -12 Fix for BUG#8877: Implementation of "Early NULL-values filtering for ref access" 1. update_ref_and_keys() accumulates info about null-rejecting predicates in in KEY_FIELD::null_rejecting, add_key_part saves these to KEYUSE. 2. create_ref_for_key copies them to TABLE_REF. 3. add_not_null_conds adds "x IS NOT NULL" to join_tab->select_cond of appropiate JOIN_TAB members. Includes code cleanups: * add_key_field() params: s/COND/Item_func/ (as only Item_funcs are passed to it) * add_key_fields() params: JOIN_TAB *stat removed (wasn't used) # This is a BitKeeper patch. What follows are the unified diffs for the # set of deltas contained in the patch. The rest of the patch, the part # that BitKeeper cares about, is below these diffs. # User: sergefp # Host: newbox.mylan # Root: /home/psergey/mysql-4.1-bug8877 --- 1.391/sql/sql_select.cc 2005-03-30 23:11:05 +04:00 +++ 1.392/sql/sql_select.cc 2005-04-05 02:42:20 +04:00 @@ -1995,6 +1995,11 @@ uint level; uint optimize; bool eq_func; + /* + If true, the condition this struct represents will not be satisfied + when val IS NULL. + */ + bool null_rejecting; } KEY_FIELD; /* Values in optimize */ @@ -2011,6 +2016,12 @@ that are internally transformed to something like: SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL + + KEY_FIELD::null_rejecting is processed as follows: + result has null_rejecting=true if it is set for both ORed references. + for example: + (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true + (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false */ static KEY_FIELD * @@ -2044,6 +2055,8 @@ KEY_OPTIMIZE_EXISTS) | ((old->optimize | new_fields->optimize) & KEY_OPTIMIZE_REF_OR_NULL)); + old->null_rejecting= old->null_rejecting && + new_fields->null_rejecting; } } else if (old->eq_func && new_fields->eq_func && @@ -2055,6 +2068,8 @@ KEY_OPTIMIZE_EXISTS) | ((old->optimize | new_fields->optimize) & KEY_OPTIMIZE_REF_OR_NULL)); + old->null_rejecting= old->null_rejecting && + new_fields->null_rejecting; } else if (old->eq_func && new_fields->eq_func && (old->val->is_null() || new_fields->val->is_null())) @@ -2065,6 +2080,8 @@ /* Remember the NOT NULL value */ if (old->val->is_null()) old->val= new_fields->val; + /* The referred expression can be NULL: */ + old->null_rejecting= false; } else { @@ -2119,7 +2136,7 @@ */ static void -add_key_field(KEY_FIELD **key_fields,uint and_level, COND *cond, +add_key_field(KEY_FIELD **key_fields,uint and_level, Item_func *cond, Field *field,bool eq_func,Item **value, uint num_values, table_map usable_tables) { @@ -2221,12 +2238,29 @@ (*key_fields)->val= *value; (*key_fields)->level= and_level; (*key_fields)->optimize= exists_optimize; + /* + If the condition has form "tbl.keypart = othertbl.field" and + othertbl.field can be NULL, there will be no matches if othertbl.field + has NULL value. + */ + (*key_fields)->null_rejecting= (cond->functype() == Item_func::EQ_FUNC) && + ((*value)->type() == Item::FIELD_ITEM) && + ((Item_field*)*value)->field->maybe_null(); (*key_fields)++; } - +/* + SYNOPSIS + add_key_fields() + key_fields Add KEY_FIELD entries to this array (and move the + pointer) + and_level AND-level (a value that is different for every n-way + AND operation) + cond Condition to analyze + usable_tables Value to pass to add_key_field +*/ static void -add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level, +add_key_fields(KEY_FIELD **key_fields,uint *and_level, COND *cond, table_map usable_tables) { if (cond->type() == Item_func::COND_ITEM) @@ -2238,20 +2272,20 @@ { Item *item; while ((item=li++)) - add_key_fields(stat,key_fields,and_level,item,usable_tables); + add_key_fields(key_fields,and_level,item,usable_tables); for (; org_key_fields != *key_fields ; org_key_fields++) org_key_fields->level= *and_level; } else { (*and_level)++; - add_key_fields(stat,key_fields,and_level,li++,usable_tables); + add_key_fields(key_fields,and_level,li++,usable_tables); Item *item; while ((item=li++)) { KEY_FIELD *start_key_fields= *key_fields; (*and_level)++; - add_key_fields(stat,key_fields,and_level,item,usable_tables); + add_key_fields(key_fields,and_level,item,usable_tables); *key_fields=merge_key_fields(org_key_fields,start_key_fields, *key_fields,++(*and_level)); } @@ -2363,6 +2397,7 @@ keyuse.keypart_map= (key_part_map) 1 << part; keyuse.used_tables=key_field->val->used_tables(); keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL; + keyuse.null_rejecting= key_field->null_rejecting; VOID(insert_dynamic(keyuse_array,(gptr) &keyuse)); } } @@ -2456,8 +2491,22 @@ /* Update keyuse array with all possible keys we can use to fetch rows - join_tab is a array in tablenr_order - stat is a reference array in 'prefered' order. + + SYNOPSIS + update_ref_and_keys() + thd + keyuse OUT Put here ordered array of KEYUSE structures + join_tab Array in tablenr_order + tables Number of tables in join + cond WHERE condition (note that the function analyzes + join_tab[i]->on_expr too) + normal_tables tables not inner w.r.t some outer join (ones for which + we can make ref access based the WHERE clause) + select_lex current SELECT + + RETURN + 0 - OK + 1 - Out of memory. */ static bool @@ -2478,7 +2527,7 @@ return TRUE; if (cond) { - add_key_fields(join_tab,&end,&and_level,cond,normal_tables); + add_key_fields(&end,&and_level,cond,normal_tables); for (; field != end ; field++) { add_key_part(keyuse,field); @@ -2492,7 +2541,7 @@ { if (join_tab[i].on_expr) { - add_key_fields(join_tab,&end,&and_level,join_tab[i].on_expr, + add_key_fields(&end,&and_level,join_tab[i].on_expr, join_tab[i].table->map); } } @@ -3232,6 +3281,7 @@ } j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length); j->ref.key_err=1; + j->ref.null_rejecting= 0; keyuse=org_keyuse; store_key **ref_key= j->ref.key_copy; @@ -3256,6 +3306,8 @@ uint maybe_null= test(keyinfo->key_part[i].null_bit); j->ref.items[i]=keyuse->val; // Save for cond removal + if (keyuse->null_rejecting) + j->ref.null_rejecting |= 1 << i; keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables; if (!keyuse->used_tables && !(join->select_options & SELECT_DESCRIBE)) @@ -3410,12 +3462,99 @@ } +inline void add_cond_and_fix(Item **e1, Item *e2) +{ + if (*e1) + { + Item *res; + if ((res= new Item_cond_and(*e1, e2))) + { + *e1= res; + res->quick_fix_field(); + } + } + else + *e1= e2; +} + + +/* + Add to join_tab->select_cond[i] "table.field IS NOT NULL" conditions we've + inferred from ref/eq_ref access performed. + + SYNOPSIS + add_not_null_conds() + join Join to process + + NOTES + This function is a part of "Early NULL-values filtering for ref access" + optimization. + + Example of this optimization: + For query SELECT * FROM t1,t2 WHERE t2.key=t1.field + and plan " any-access(t1), ref(t2.key=t1.field) " + add "t1.field IS NOT NULL" to t1's table condition. + Description of the optimization: + + We look through equalities choosen to perform ref/eq_ref access, + pick equalities that have form "tbl.part_of_key = othertbl.field" + (where othertbl is a non-const table and othertbl.field may be NULL) + and add them to conditions on correspoding tables (othertbl in this + example). + + This optimization doesn't affect the choices that ref, range, or join + optimizer make. This was intentional because this was added after 4.1 + was GA. + + Implementation overview + 1. update_ref_and_keys() accumulates info about null-rejecting + predicates in in KEY_FIELD::null_rejecting + 1.1 add_key_part saves these to KEYUSE. + 2. create_ref_for_key copies them to TABLE_REF. + 3. add_not_null_conds adds "x IS NOT NULL" to join_tab->select_cond of + appropiate JOIN_TAB members. +*/ + +static void add_not_null_conds(JOIN *join) +{ + DBUG_ENTER("add_not_null_conds"); + for (uint i=join->const_tables ; i < join->tables ; i++) + { + JOIN_TAB *tab=join->join_tab+i; + if ((tab->type == JT_REF || tab->type == JT_REF_OR_NULL) && + !tab->table->maybe_null) + { + for (uint keypart= 0; keypart < tab->ref.key_parts; keypart++) + { + if (tab->ref.null_rejecting & (1 << keypart)) + { + Item *item= tab->ref.items[keypart]; + DBUG_ASSERT(item->type() == Item::FIELD_ITEM); + Item_field *not_null_item= (Item_field*)item; + JOIN_TAB *referred_tab= not_null_item->field->table->reginfo.join_tab; + Item_func_isnotnull *null_rej; + if (!(null_rej= new Item_func_isnotnull(not_null_item))) + DBUG_VOID_RETURN; + + null_rej->quick_fix_field(); + //psergey-todo: Flatten AND's + DBUG_EXECUTE("where",print_where(null_rej, + referred_tab->table->table_name);); + add_cond_and_fix(&referred_tab->select_cond, null_rej); + } + } + } + } + DBUG_VOID_RETURN; +} + static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) { DBUG_ENTER("make_join_select"); if (select) { + add_not_null_conds(join); table_map used_tables; if (join->tables > 1) cond->update_used_tables(); // Tablenr may have changed @@ -3472,13 +3611,14 @@ } if (tmp) { - DBUG_EXECUTE("where",print_where(tmp,tab->table->table_name);); SQL_SELECT *sel=tab->select=(SQL_SELECT*) join->thd->memdup((gptr) select, sizeof(SQL_SELECT)); if (!sel) DBUG_RETURN(1); // End of memory - tab->select_cond=sel->cond=tmp; + add_cond_and_fix(&tab->select_cond, tmp); + sel->cond= tab->select_cond; sel->head=tab->table; + DBUG_EXECUTE("where",print_where(tmp,tab->table->table_name);); if (tab->quick) { /* Use quick key read if it's a constant and it's not used --- 1.72/sql/sql_select.h 2005-03-16 09:46:11 +03:00 +++ 1.73/sql/sql_select.h 2005-04-05 02:42:20 +04:00 @@ -31,6 +31,11 @@ uint key, keypart, optimize; key_part_map keypart_map; ha_rows ref_table_rows; + /* + If true, the comparison this value was created from will not be + satisfied if val has NULL 'value'. + */ + bool null_rejecting; } KEYUSE; class store_key; @@ -45,6 +50,11 @@ byte *key_buff2; // key_buff+key_length store_key **key_copy; // Item **items; // val()'s for each keypart + /* + (null_rejecting & (1<