From: Roy Lyseng Date: April 6 2011 11:57am Subject: bzr commit into mysql-trunk branch (roy.lyseng:3358) Bug#11822517 List-Archive: http://lists.mysql.com/commits/134806 X-Bug: 11822517 Message-Id: <20110406115747.355A51F3@tyr67.norway.sun.com> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============8785819318547584788==" --===============8785819318547584788== MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Content-Disposition: inline #At file:///home/rl136806/mysql/repo/mysql-work5/ based on revid:tor.didriksen@stripped 3358 Roy Lyseng 2011-04-06 Bug#11822517: Refactor call interface of choose_plan() Part 1 - create class Optimize_table_order. This patch creates a class that is used to optimize the join order of tables in a query. The main purpose of the refactoring is to simplify function interfaces and to encapsulate information needed to perform optimization in a dedicated class. The following existing functions are added to the class: choose_table_order() - renamed from choose_plan() check_interleaving_with_nj() advance_sj_state() backout_nj_sj_state() optimize_straight_join() greedy_search() best_extension_by_limited_search() optimize_wo_join_buffering() determine_search_depth() sql/sql_select.cc New class definition, see above for details. sql/sql_select.h Added all_table_map (map of tables in query) to JOIN class. cur_embedding_map has been moved to class Optimize_table_order. Commented const_table_map, found_const_table_map and outer_join. modified: sql/sql_select.cc sql/sql_select.h === modified file 'sql/sql_select.cc' --- a/sql/sql_select.cc 2011-03-29 07:30:44 +0000 +++ b/sql/sql_select.cc 2011-04-06 11:56:55 +0000 @@ -62,7 +62,7 @@ struct st_sargable_param; static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array); static bool make_join_statistics(JOIN *join, TABLE_LIST *leaves, Item *conds, DYNAMIC_ARRAY *keyuse); -static bool optimize_semijoin_nests(JOIN *join, table_map all_table_map); +static bool optimize_semijoin_nests(JOIN *join); static bool update_ref_and_keys(THD *thd, DYNAMIC_ARRAY *keyuse, JOIN_TAB *join_tab, uint tables, Item *conds, @@ -73,23 +73,13 @@ static int sort_keyuse(Key_use *a, Key_u static void set_position(JOIN *join, uint index, JOIN_TAB *table, Key_use *key); static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, Key_use *org_keyuse, table_map used_tables); -static bool choose_plan(JOIN *join, table_map join_tables); static void best_access_path(JOIN *join, JOIN_TAB *s, table_map remaining_tables, uint idx, bool disable_jbuf, double record_count, POSITION *pos, POSITION *loose_scan_pos); -static void optimize_straight_join(JOIN *join, table_map join_tables); -static bool greedy_search(JOIN *join, table_map remaining_tables, - uint depth, uint prune_level); -static bool best_extension_by_limited_search(JOIN *join, - table_map remaining_tables, - uint idx, double record_count, - double read_time, uint depth, - uint prune_level); -static uint determine_search_depth(JOIN* join); C_MODE_START -static int join_tab_cmp(const void *dummy, const void* ptr1, const void* ptr2); -static int join_tab_cmp_straight(const void *dummy, const void* ptr1, const void* ptr2); +static int join_tab_cmp(const void *, const void* ptr1, const void* ptr2); +static int join_tab_cmp_straight(const void *, const void* ptr1, const void* ptr2); static int join_tab_cmp_embedded_first(const void *emb, const void* ptr1, const void *ptr2); C_MODE_END static uint cache_record_length(JOIN *join,uint index); @@ -122,19 +112,10 @@ static Item* substitute_for_best_equal_f void *table_join_idx); static Item *simplify_joins(JOIN *join, List *join_list, Item *conds, bool top, bool in_sj); -static bool check_interleaving_with_nj(JOIN_TAB *next); static void reset_nj_counters(List *join_list); static uint build_bitmap_for_nested_joins(List *join_list, uint first_unused); -static -void advance_sj_state(JOIN *join, const table_map remaining_tables, - const JOIN_TAB *new_join_tab, uint idx, - double *current_record_count, double *current_read_time, - POSITION *loose_scan_pos); -static void backout_nj_sj_state(const table_map remaining_tables, - const JOIN_TAB *tab); - static Item *optimize_cond(JOIN *join, Item *conds, List *join_list, bool build_equalities, @@ -279,6 +260,94 @@ TABLE *create_duplicate_weedout_tmp_tabl Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field, bool *inherited_fl); +/** + This class determines the optimal join order for tables within + a basic query block, ie a query specification clause, possibly extended + with semi joined tables from embedded subqueries. + + This class takes as prerequisite a join class where all dependencies among + tables have been sorted out, all possible access paths have been + sorted out, and all statistics information has been filled in. + + The class has a sole public function that will calculate the most + optimal plan based on the inputs and the environment, such as prune level + and greedy optimizer search depth. For more information, see the + function headers for the private functions greedy_search() and + best_extension_by_limited_search(). +*/ + +class Optimize_table_order +{ +public: + Optimize_table_order(THD *thd, JOIN *join, TABLE_LIST *sjm_nest) + : search_depth(determine_search_depth(join, + thd->variables.optimizer_search_depth)), + prune_level(thd->variables.optimizer_prune_level), + thd(thd), join(join), + cur_embedding_map(0) + { + join->emb_sjm_nest= sjm_nest; + } + ~Optimize_table_order() + { + join->emb_sjm_nest= NULL; + } + /** + Entry point to table join order optimization. + For further description, see class header and private function headers. + + @return false if successful, true if error + */ + bool choose_table_order(); + +private: + const uint search_depth; // Maximum search depth to apply in greedy search + const uint prune_level; // pruning heuristics to be applied + // (0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS) + THD * const thd; // Pointer to current THD + JOIN * const join; // Pointer to the current plan being developed + /** + Bitmap of nested joins embedding the position at the end of the current + partial join. + */ + nested_join_map cur_embedding_map; + /** + @todo: Add remaining Join optimization state members here, + ie emb_sjm_nest, positions, cur_sj_inner_tables. + This is not yet possible because (some of them) are accessed through + best_access_path(), which is currently not part of this class. + */ + + bool check_interleaving_with_nj(JOIN_TAB *next_tab); + void advance_sj_state(table_map remaining_tables, + const JOIN_TAB *tab, uint idx, + double *current_record_count, + double *current_read_time, + POSITION *loose_scan_pos); + void backout_nj_sj_state(const table_map remaining_tables, + const JOIN_TAB *tab); + void optimize_straight_join(table_map join_tables); + bool greedy_search(table_map remaining_tables); + bool best_extension_by_limited_search(table_map remaining_tables, + uint idx, + double record_count, + double read_time, + uint current_search_depth); + void optimize_wo_join_buffering(uint first_tab, uint last_tab, + table_map last_remaining_tables, + bool first_alt, uint no_jbuf_before, + double *reopt_rec_count, double *reopt_cost); + + static uint determine_search_depth(JOIN* join, uint search_depth); + /** + @todo: Add the static functions join_tab_cmp(), join_tab_cmp_straight() and + join_tab_cmp_embedded_first() as static private member functions here. + This is currently not possible because they are fed to my_qsort2(), + which requires C linkage. + @todo: Add best_access_path() as private member function within this class. + Currently not possible because it is called from outside this class. + */ +}; /** This handles SELECT with and without UNION @@ -1953,8 +2022,7 @@ JOIN::optimize() /* Calculate how to do the join */ THD_STAGE_INFO(thd, stage_statistics); - if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) || - thd->is_fatal_error) + if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse)) { DBUG_PRINT("error",("Error: make_join_statistics() failed")); DBUG_RETURN(1); @@ -4625,9 +4693,10 @@ make_join_statistics(JOIN *join, TABLE_L { int error; TABLE *table; + THD * const thd= join->thd; TABLE_LIST *tables= tables_arg; uint i,table_count,const_count,key; - table_map found_const_table_map, all_table_map, found_ref, refs; + table_map found_ref, refs; TABLE **table_vector; JOIN_TAB *stat,*stat_end,*s,**stat_ref; Key_use *keyuse, *start_keyuse; @@ -4636,25 +4705,33 @@ make_join_statistics(JOIN *join, TABLE_L JOIN_TAB *stat_vector[MAX_TABLES+1]; DBUG_ENTER("make_join_statistics"); + /* + Conceptually, this initialization belongs immediately before the call + to table_order.choose_table_order(), but due to the use of the error label, + it must be placed before all 'goto error' statements. + */ + Optimize_table_order table_order(thd, join, NULL); + table_count=join->tables; - stat= new (join->thd->mem_root) JOIN_TAB[table_count]; - stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES); - table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE*)*(table_count*2)); + stat= new (thd->mem_root) JOIN_TAB[table_count]; + stat_ref=(JOIN_TAB**) thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES); + table_vector=(TABLE**) thd->alloc(sizeof(TABLE*)*(table_count*2)); if (!stat || !stat_ref || !table_vector) - DBUG_RETURN(1); // Eom /* purecov: inspected */ + DBUG_RETURN(true); if (!(join->positions= - new (join->thd->mem_root) POSITION[table_count+1])) - DBUG_RETURN(TRUE); + new (thd->mem_root) POSITION[table_count+1])) + DBUG_RETURN(true); if (!(join->best_positions= - new (join->thd->mem_root) POSITION[table_count+1])) - DBUG_RETURN(TRUE); + new (thd->mem_root) POSITION[table_count+1])) + DBUG_RETURN(true); join->best_ref=stat_vector; stat_end=stat+table_count; - found_const_table_map= all_table_map=0; + join->found_const_table_map=0; + join->all_table_map= 0; const_count=0; for (s= stat, i= 0; @@ -4674,7 +4751,7 @@ make_join_statistics(JOIN *join, TABLE_L table->reginfo.join_tab=s; table->reginfo.not_exists_optimize=0; bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->s->keys); - all_table_map|= table->map; + join->all_table_map|= table->map; s->join=join; s->dependent= tables->dep_tables; @@ -4794,7 +4871,7 @@ make_join_statistics(JOIN *join, TABLE_L } if (conds || outer_join) - if (update_ref_and_keys(join->thd, keyuse_array, stat, join->tables, + if (update_ref_and_keys(thd, keyuse_array, stat, join->tables, conds, join->cond_equal, ~outer_join, join->select_lex, &sargables)) goto error; @@ -4817,7 +4894,7 @@ make_join_statistics(JOIN *join, TABLE_L } else { - found_const_table_map|= s->table->map; + join->found_const_table_map|= s->table->map; s->table->pos_in_table_list->optimized_away= TRUE; } } @@ -4863,7 +4940,7 @@ make_join_statistics(JOIN *join, TABLE_L { s->type= JT_CONST; mark_as_null_row(table); - found_const_table_map|= table->map; + join->found_const_table_map|= table->map; join->const_table_map|= table->map; set_position(join, const_count++, s, NULL); goto more_const_tables_found; @@ -4891,7 +4968,7 @@ make_join_statistics(JOIN *join, TABLE_L goto error; // Fatal error } else - found_const_table_map|= table->map; + join->found_const_table_map|= table->map; continue; } } @@ -4911,7 +4988,7 @@ make_join_statistics(JOIN *join, TABLE_L { if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize) { - if (!((~found_const_table_map) & keyuse->used_tables)) + if (!((~join->found_const_table_map) & keyuse->used_tables)) const_ref.set_bit(keyuse->keypart); else refs|=keyuse->used_tables; @@ -4940,7 +5017,7 @@ make_join_statistics(JOIN *join, TABLE_L join->const_table_map|=table->map; set_position(join,const_count++,s,start_keyuse); if (create_ref_for_key(join, s, start_keyuse, - found_const_table_map)) + join->found_const_table_map)) goto error; if ((tmp=join_read_const_table(s, join->positions+const_count-1))) @@ -4949,7 +5026,7 @@ make_join_statistics(JOIN *join, TABLE_L goto error; // Fatal error } else - found_const_table_map|= table->map; + join->found_const_table_map|= table->map; break; } else @@ -5025,13 +5102,13 @@ make_join_statistics(JOIN *join, TABLE_L { ha_rows records; SQL_SELECT *select; - select= make_select(s->table, found_const_table_map, - found_const_table_map, + select= make_select(s->table, join->found_const_table_map, + join->found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error); if (!select) goto error; - records= get_quick_record_count(join->thd, select, s->table, + records= get_quick_record_count(thd, select, s->table, &s->const_keys, join->row_limit); s->quick=select->quick; s->needed_reg=select->needed_reg; @@ -5051,7 +5128,7 @@ make_join_statistics(JOIN *join, TABLE_L { /* Generate empty row */ s->info= "Impossible ON condition"; - found_const_table_map|= s->table->map; + join->found_const_table_map|= s->table->map; s->type= JT_CONST; mark_as_null_row(s->table); // All fields are NULL } @@ -5095,29 +5172,21 @@ make_join_statistics(JOIN *join, TABLE_L join->map2table=stat_ref; join->all_tables= table_vector; join->const_tables=const_count; - join->found_const_table_map=found_const_table_map; if (join->const_tables != join->tables) optimize_keyuse(join, keyuse_array); - if (optimize_semijoin_nests(join, all_table_map)) - DBUG_RETURN(TRUE); /* purecov: inspected */ + if (optimize_semijoin_nests(join)) + DBUG_RETURN(true); + + if (table_order.choose_table_order() || thd->killed) + DBUG_RETURN(true); - /* Find an optimal join order of the non-constant tables. */ - if (join->const_tables != join->tables) - { - if (choose_plan(join, all_table_map & ~join->const_table_map)) - goto error; - } - else - { - memcpy((uchar*) join->best_positions,(uchar*) join->positions, - sizeof(POSITION)*join->const_tables); - join->best_read=1.0; - } /* Generate an execution plan from the found optimal join order. */ - error= join->thd->killed || get_best_combination(join); - DBUG_RETURN(error); + if (get_best_combination(join)) + DBUG_RETURN(true); + + DBUG_RETURN(false); error: /* @@ -5128,19 +5197,16 @@ error: */ for (tables= tables_arg; tables; tables= tables->next_leaf) tables->table->reginfo.join_tab= NULL; - DBUG_RETURN (1); + DBUG_RETURN(true); } -/* +/** Optimize semi-join nests that could be run with sj-materialization - SYNOPSIS - optimize_semijoin_nests() - join The join to optimize semi-join nests for - all_table_map Bitmap of all tables in the join + @param join The join to optimize semi-join nests for - DESCRIPTION + @details Optimize each of the semi-join nests that can be run with materialization. For each of the nests, we - Generate the best join order for this "sub-join" and remember it; @@ -5152,12 +5218,10 @@ error: All obtained information is saved and will be used by the main join optimization pass. - RETURN - FALSE Ok - TRUE Out of memory error + @return false if successful, true if error */ -static bool optimize_semijoin_nests(JOIN *join, table_map all_table_map) +static bool optimize_semijoin_nests(JOIN *join) { DBUG_ENTER("optimize_semijoin_nests"); List_iterator sj_list_it(join->select_lex->sj_nests); @@ -5186,9 +5250,9 @@ static bool optimize_semijoin_nests(JOIN */ if (semijoin_types_allow_materialization(sj_nest)) { - join->emb_sjm_nest= sj_nest; - if (choose_plan(join, all_table_map & ~join->const_table_map)) - DBUG_RETURN(TRUE); /* purecov: inspected */ + Optimize_table_order table_order(join->thd, join, sj_nest); + if (table_order.choose_table_order()) + DBUG_RETURN(true); /* The best plan to run the subquery is now in join->best_positions, save it. @@ -5240,7 +5304,7 @@ static bool optimize_semijoin_nests(JOIN } if (!(sj_nest->nested_join->sjm.positions= (st_position*)join->thd->alloc(sizeof(st_position)*n_tables))) - DBUG_RETURN(TRUE); + DBUG_RETURN(true); memcpy(sj_nest->nested_join->sjm.positions, join->best_positions + join->const_tables, @@ -5276,8 +5340,7 @@ static bool optimize_semijoin_nests(JOIN } } } - join->emb_sjm_nest= NULL; - DBUG_RETURN(FALSE); + DBUG_RETURN(false); } @@ -6403,7 +6466,7 @@ update_ref_and_keys(THD *thd, DYNAMIC_AR } /** - Update some values in keyuse for faster choose_plan() loop. + Update some values in keyuse for faster choose_table_order() loop. */ static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array) @@ -6945,17 +7008,25 @@ public: 'join->positions' of length 'idx'. The chosen access method for 's' and its cost are stored in 'join->positions[idx]'. + Notice also that when calculating a plan for a materialized semi join nest, + this function must not consider key references between tables inside the + semi join nest and those outside of it. The way to control this is to add + the set of outside tables to the @c remaining_tables argument. + @param join pointer to the structure providing all context info for the query @param s the table to be joined by the function @param thd thread for the connection that submitted the query - @param remaining_tables set of tables not included into the partial plan yet + @param remaining_tables set of tables not included in the partial plan yet. + additionally, when calculating a plan for a + materialized semi join nest, this must also contain + all tables outside of the semi join nest. @param idx the length of the partial plan @param disable_jbuf TRUE<=> Don't use join buffering @param record_count estimate for the number of records returned by the partial plan - @param pos OUT Table access plan - @param loose_scan_pos OUT Table plan that uses loosescan, or set cost to + @param[out] pos Table access plan + @param[out] loose_scan_pos Table plan that uses loosescan, or set cost to DBL_MAX if not possible. @return @@ -7537,33 +7608,37 @@ best_access_path(JOIN *join, /** - Selects and invokes a search strategy for an optimal query plan. + Selects and invokes a search strategy for an optimal query join order. The function checks user-configurable parameters that control the search strategy for an optimal plan, selects the search method and then invokes it. Each specific optimization procedure stores the final optimal plan in the array 'join->best_positions', and the cost of the plan in 'join->best_read'. + The function can be invoked to produce a plan for all tables in the query + (in this case, the const tables are usually filtered out), or it can be + invoked to produce a plan for a materialization of a semi join nest. + Set a non-NULL emb_sjm_nest pointer when producing a plan for a semi join + nest to be materialized and a NULL pointer when producing a full query plan. - @param join pointer to the structure providing all context info for - the query - @param join_tables set of the tables in the query - - @retval - FALSE ok - @retval - TRUE Fatal error + @return false if successful, true if error */ -static bool -choose_plan(JOIN *join, table_map join_tables) +bool Optimize_table_order::choose_table_order() { - uint search_depth= join->thd->variables.optimizer_search_depth; - uint prune_level= join->thd->variables.optimizer_prune_level; - bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN); - DBUG_ENTER("choose_plan"); + const bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN); + table_map join_tables; + DBUG_ENTER("Optimize_table_order::choose_table_order"); + + /* Are there any tables to optimize? */ + if (join->const_tables == join->tables) + { + memcpy(join->best_positions, join->positions, + sizeof(POSITION) * join->const_tables); + join->best_read= 1.0; + DBUG_RETURN(false); + } - join->cur_embedding_map= 0; reset_nj_counters(join->join_list); qsort2_cmp jtab_sort_func; @@ -7573,6 +7648,12 @@ choose_plan(JOIN *join, table_map join_t tables from this semi-join as first */ jtab_sort_func= join_tab_cmp_embedded_first; + join_tables= join->all_table_map & ~join->const_table_map; + /* + Inner tables of semi join nest are not allowed to be identified as + const tables. + */ + DBUG_ASSERT((join_tables & join->const_table_map) == 0); } else { @@ -7585,6 +7666,7 @@ choose_plan(JOIN *join, table_map join_t records accessed. */ jtab_sort_func= straight_join ? join_tab_cmp_straight : join_tab_cmp; + join_tables= join->all_table_map & ~join->const_table_map; } my_qsort2(join->best_ref + join->const_tables, join->tables - join->const_tables, sizeof(JOIN_TAB*), @@ -7593,14 +7675,11 @@ choose_plan(JOIN *join, table_map join_t if (straight_join) { - optimize_straight_join(join, join_tables); + optimize_straight_join(join_tables); } else { - if (search_depth == 0) - /* Automatically determine a reasonable value for 'search_depth' */ - search_depth= determine_search_depth(join); - if (greedy_search(join, join_tables, search_depth, prune_level)) + if (greedy_search(join_tables)) DBUG_RETURN(TRUE); } @@ -7610,9 +7689,10 @@ choose_plan(JOIN *join, table_map join_t i.e. they have subqueries, unions or call stored procedures. TODO: calculate a correct cost for a query with subqueries and UNIONs. */ - if (join->thd->lex->is_single_level_stmt()) - join->thd->status_var.last_query_cost= join->best_read; - DBUG_RETURN(FALSE); + if (thd->lex->is_single_level_stmt()) + thd->status_var.last_query_cost= join->best_read; + + DBUG_RETURN(false); } @@ -7642,7 +7722,7 @@ choose_plan(JOIN *join, table_map join_t */ static int -join_tab_cmp(const void *dummy, const void* ptr1, const void* ptr2) +join_tab_cmp(const void *, const void* ptr1, const void* ptr2) { JOIN_TAB *jt1= *(JOIN_TAB**) ptr1; JOIN_TAB *jt2= *(JOIN_TAB**) ptr2; @@ -7664,7 +7744,7 @@ join_tab_cmp(const void *dummy, const vo */ static int -join_tab_cmp_straight(const void *dummy, const void* ptr1, const void* ptr2) +join_tab_cmp_straight(const void *, const void* ptr1, const void* ptr2) { JOIN_TAB *jt1= *(JOIN_TAB**) ptr1; JOIN_TAB *jt2= *(JOIN_TAB**) ptr2; @@ -7687,11 +7767,11 @@ join_tab_cmp_straight(const void *dummy, /* Same as join_tab_cmp but tables from within the given semi-join nest go - first. Used when the optimizing semi-join materialization nests. + first. Used when optimizing semi-join materialization nests. */ static int -join_tab_cmp_embedded_first(const void *emb, const void* ptr1, const void* ptr2) +join_tab_cmp_embedded_first(const void *emb, const void* ptr1, const void* ptr2) { const TABLE_LIST *emb_nest= (TABLE_LIST*) emb; JOIN_TAB *jt1= *(JOIN_TAB**) ptr1; @@ -7748,11 +7828,11 @@ join_tab_cmp_embedded_first(const void * 'greedy_search'. */ -static uint -determine_search_depth(JOIN *join) +uint Optimize_table_order::determine_search_depth(JOIN *join, uint search_depth) { + if (search_depth > 0) + return search_depth; uint table_count= join->tables - join->const_tables; - uint search_depth; /* TODO: this value should be determined dynamically, based on statistics: */ uint max_tables_for_exhaustive_opt= 7; @@ -7779,8 +7859,6 @@ determine_search_depth(JOIN *join) access method. The final optimal plan is stored in the array 'join->best_positions', and the corresponding cost in 'join->best_read'. - @param join pointer to the structure providing all context info for - the query @param join_tables set of the tables in the query @note @@ -7792,14 +7870,12 @@ determine_search_depth(JOIN *join) optimization process to finalize a QEP as it is. */ -static void -optimize_straight_join(JOIN *join, table_map join_tables) +void Optimize_table_order::optimize_straight_join(table_map join_tables) { JOIN_TAB *s; uint idx= join->const_tables; double record_count= 1.0; double read_time= 0.0; - POSITION loose_scan_pos; for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) { @@ -7810,6 +7886,7 @@ optimize_straight_join(JOIN *join, table */ DBUG_ASSERT(!check_interleaving_with_nj(s)); /* Find the best access method from 's' to the current partial plan */ + POSITION loose_scan_pos; best_access_path(join, s, join_tables, idx, FALSE, record_count, join->positions + idx, &loose_scan_pos); @@ -7817,7 +7894,7 @@ optimize_straight_join(JOIN *join, table record_count*= join->positions[idx].records_read; read_time+= join->positions[idx].read_time + record_count / (double) TIME_FOR_COMPARE; - advance_sj_state(join, join_tables, s, idx, &record_count, &read_time, + advance_sj_state(join_tables, s, idx, &record_count, &read_time, &loose_scan_pos); join_tables&= ~(s->table->map); @@ -7827,8 +7904,7 @@ optimize_straight_join(JOIN *join, table if (join->sort_by_table && join->sort_by_table != join->positions[join->const_tables].table->table) read_time+= record_count; // We have to make a temp table - memcpy((uchar*) join->best_positions, (uchar*) join->positions, - sizeof(POSITION)*idx); + memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx); /** * If many plans have identical cost, which one will be used @@ -7980,48 +8056,43 @@ semijoin_order_allows_materialization(co In the future, 'greedy_search' might be extended to support other implementations of 'best_extension', e.g. some simpler quadratic procedure. - @param join pointer to the structure providing all context info - for the query + @par + @c search_depth from Optimize_table_order controls the exhaustiveness + of the search, and @c prune_levelcontrols the pruning heuristics that + should be applied during search. + @param remaining_tables set of tables not included into the partial plan yet - @param search_depth controlls the exhaustiveness of the search - @param prune_level the pruning heuristics that should be applied during - search - @retval - FALSE ok - @retval - TRUE Fatal error + @return false if successful, true if error */ -static bool -greedy_search(JOIN *join, - table_map remaining_tables, - uint search_depth, - uint prune_level) +bool Optimize_table_order::greedy_search(table_map remaining_tables) { double record_count= 1.0; double read_time= 0.0; uint idx= join->const_tables; // index into 'join->best_ref' uint best_idx; - uint size_remain; // cardinality of remaining_tables POSITION best_pos; JOIN_TAB *best_table; // the next plan node to be added to the curr QEP - uint n_tables; // ==join->tables or # tables in the sj-mat nest we're optimizing - DBUG_ENTER("greedy_search"); + DBUG_ENTER("Optimize_table_order::greedy_search"); + + /* Number of tables that we are optimizing */ + const uint n_tables= my_count_bits(remaining_tables & + (join->emb_sjm_nest? + join->emb_sjm_nest->sj_inner_tables : + ~(table_map)0)); - /* number of tables that remain to be optimized */ - n_tables= size_remain= my_count_bits(remaining_tables & - (join->emb_sjm_nest? - join->emb_sjm_nest->sj_inner_tables : - ~(table_map)0)); + /* Number of tables remaining to be optimized */ + uint size_remain= n_tables; do { /* Find the extension of the current QEP with the lowest cost */ join->best_read= DBL_MAX; - if (best_extension_by_limited_search(join, remaining_tables, idx, record_count, - read_time, search_depth, prune_level)) - DBUG_RETURN(TRUE); + if (best_extension_by_limited_search(remaining_tables, idx, + record_count, read_time, + search_depth)) + DBUG_RETURN(true); /* 'best_read < DBL_MAX' means that optimizer managed to find some plan and updated 'best_positions' array accordingly. @@ -8036,7 +8107,7 @@ greedy_search(JOIN *join, */ DBUG_EXECUTE("opt", print_plan(join, n_tables, record_count, read_time, read_time, "optimal");); - DBUG_RETURN(FALSE); + DBUG_RETURN(false); } /* select the first table in the optimal extension as most promising */ @@ -8087,7 +8158,7 @@ greedy_search(JOIN *join, DBUG_EXECUTE("opt", print_plan(join, n_tables, record_count, read_time, read_time, "extended");); - } while (TRUE); + } while (true); } @@ -8227,8 +8298,6 @@ void get_partial_join_cost(JOIN *join, u The parameter 'search_depth' provides control over the recursion depth, and thus the size of the resulting optimal plan. - @param join pointer to the structure providing all context info - for the query @param remaining_tables set of tables not included into the partial plan yet @param idx length of the partial QEP in 'join->positions'; since a depth-first search is used, also corresponds @@ -8237,34 +8306,24 @@ void get_partial_join_cost(JOIN *join, u @param record_count estimate for the number of records returned by the best partial plan @param read_time the cost of the best partial plan - @param search_depth maximum depth of the recursion and thus size of the + @param current_search_depth maximum depth of recursion and thus size of the found optimal plan - (0 < search_depth <= join->tables+1). - @param prune_level pruning heuristics that should be applied during - optimization - (values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS) + (0 < current_search_depth <= join->tables+1). - @retval - FALSE ok - @retval - TRUE Fatal error + @return false if successful, true if error */ -static bool -best_extension_by_limited_search(JOIN *join, - table_map remaining_tables, - uint idx, - double record_count, - double read_time, - uint search_depth, - uint prune_level) +bool Optimize_table_order::best_extension_by_limited_search( + table_map remaining_tables, + uint idx, + double record_count, + double read_time, + uint current_search_depth) { - DBUG_ENTER("best_extension_by_limited_search"); + DBUG_ENTER("Optimize_table_order::best_extension_by_limited_search"); - THD *thd= join->thd; if (thd->killed) // Abort - DBUG_RETURN(TRUE); - + DBUG_RETURN(true); /* 'join' is a partial plan with lower cost than the best plan so far, so continue expanding it further with the tables in 'remaining_tables'. @@ -8278,8 +8337,8 @@ best_extension_by_limited_search(JOIN table_map allowed_tables= ~(table_map)0; if (join->emb_sjm_nest) allowed_tables= join->emb_sjm_nest->sj_inner_tables; - - bool has_sj= !join->select_lex->sj_nests.is_empty(); + const bool has_sj= + !(join->select_lex->sj_nests.is_empty() || join->emb_sjm_nest); JOIN_TAB *s; JOIN_TAB *saved_refs[MAX_TABLES]; @@ -8289,7 +8348,7 @@ best_extension_by_limited_search(JOIN for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++) { - table_map real_table_bit= s->table->map; + const table_map real_table_bit= s->table->map; /* Don't move swap inside conditional code: All items should @@ -8304,11 +8363,12 @@ best_extension_by_limited_search(JOIN (!idx || !check_interleaving_with_nj(s))) { double current_record_count, current_read_time; - POSITION *position= join->positions + idx; + POSITION * const position= join->positions + idx; /* Find the best access method from 's' to the current partial plan */ POSITION loose_scan_pos; - best_access_path(join, s, remaining_tables, idx, FALSE, record_count, + best_access_path(join, s, remaining_tables, + idx, false, record_count, position, &loose_scan_pos); /* Compute the cost of extending the plan with 's' */ @@ -8324,13 +8384,15 @@ best_extension_by_limited_search(JOIN cost (takes 9% of time in a 20-table plan search), hence the if() above, which is also more efficient than the same if() inside advance_sj_state() would be. + Besides, never call advance_sj_state() when calculating the plan + for a materialized semi join nest. */ - advance_sj_state(join, remaining_tables, s, idx, + advance_sj_state(remaining_tables, s, idx, ¤t_record_count, ¤t_read_time, &loose_scan_pos); } else - join->positions[idx].sj_strategy= SJ_OPT_NONE; + position->sj_strategy= SJ_OPT_NONE; /* Expand only partial plans with lower cost than the best QEP so far */ if (current_read_time >= join->best_read) @@ -8359,7 +8421,7 @@ best_extension_by_limited_search(JOIN best_read_time >= current_read_time && /* TODO: What is the reasoning behind this condition? */ (!(s->key_dependent & remaining_tables) || - join->positions[idx].records_read < 2.0)) + position->records_read < 2.0)) { best_record_count= current_record_count; best_read_time= current_read_time; @@ -8377,22 +8439,21 @@ best_extension_by_limited_search(JOIN } } - if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) & allowed_tables ) + if ((current_search_depth > 1) && + (remaining_tables & ~real_table_bit) & allowed_tables ) { /* Explore more best extensions of plan */ - if (best_extension_by_limited_search(join, - remaining_tables & ~real_table_bit, + if (best_extension_by_limited_search(remaining_tables & ~real_table_bit, idx + 1, current_record_count, current_read_time, - search_depth - 1, - prune_level)) - DBUG_RETURN(TRUE); + current_search_depth - 1)) + DBUG_RETURN(true); } else { /* - 'join' is either the best partial QEP with 'search_depth' relations, - or the best complete QEP so far, whichever is smaller. + 'join' is either the best partial QEP with 'current_search_depth' + tables, or the best complete QEP so far, whichever is smaller. */ if (join->sort_by_table && join->sort_by_table != @@ -8405,7 +8466,7 @@ best_extension_by_limited_search(JOIN current_read_time+= current_record_count; if (current_read_time < join->best_read) { - memcpy((uchar*) join->best_positions, (uchar*) join->positions, + memcpy(join->best_positions, join->positions, sizeof(POSITION) * (idx + 1)); join->best_read= current_read_time - 0.001; } @@ -8420,8 +8481,9 @@ best_extension_by_limited_search(JOIN } // Restore previous #rows sorted best_ref[] - memcpy(join->best_ref + idx, saved_refs, sizeof(JOIN_TAB*) * (join->tables-idx)); - DBUG_RETURN(FALSE); + memcpy(join->best_ref + idx, saved_refs, + sizeof(JOIN_TAB*) * (join->tables-idx)); + DBUG_RETURN(false); } @@ -13765,7 +13827,7 @@ static void reset_nj_counters(Listcur_embedding_map - bitmap of pairs of brackets (aka nested + 1. cur_embedding_map - bitmap of pairs of brackets (aka nested joins) we've opened but didn't close. 2. {each NESTED_JOIN structure not simplified away}->counter - number of this nested join's children that have already been added to to @@ -13781,18 +13843,17 @@ static void reset_nj_counters(List
table->pos_in_table_list->embedding; - JOIN *join= next_tab->join; - if (join->cur_embedding_map & ~next_tab->embedding_map) + if (cur_embedding_map & ~next_tab->embedding_map) { /* next_tab is outside of the "pair of brackets" we're currently in. Cannot add it. */ - return TRUE; + return true; } /* @@ -13809,7 +13870,7 @@ static bool check_interleaving_with_nj(J the picture above, we're looking at the 'X' bracket. Don't exit yet as X bracket might have Y pair bracket. */ - join->cur_embedding_map |= next_emb->nested_join->nj_map; + cur_embedding_map |= next_emb->nested_join->nj_map; } if (next_emb->nested_join->join_list.elements != @@ -13820,31 +13881,27 @@ static bool check_interleaving_with_nj(J We're currently at Y or Z-bracket as depicted in the above picture. Mark that we've left it and continue walking up the brackets hierarchy. */ - join->cur_embedding_map &= ~next_emb->nested_join->nj_map; + cur_embedding_map &= ~next_emb->nested_join->nj_map; } - return FALSE; + return false; } -/* +/** Change access methods not to use join buffering and adjust costs accordingly - SYNOPSIS - optimize_wo_join_buffering() - join - first_tab The first tab to do re-optimization for - last_tab The last tab to do re-optimization for - last_remaining_tables Bitmap of tables that are not in the + @param first_tab The first tab to do re-optimization for + @param last_tab The last tab to do re-optimization for + @param last_remaining_tables Bitmap of tables that are not in the [0...last_tab] join prefix - first_alt TRUE <=> Use the LooseScan plan for the first_tab - no_jbuf_before Don't allow to use join buffering before this - table - reopt_rec_count OUT New output record count + @param first_alt TRUE <=> Use the LooseScan plan for the first_tab + @param no_jbuf_before Don not allow join buffering before this table + @param[out] reopt_rec_count New output record count DBL_MAX if we could find no plan. - reopt_cost OUT New join prefix cost + @param[out] reopt_cost New join prefix cost DBL_MAX if we could find no plan. - DESCRIPTION + @details Given a join prefix [0; ... first_tab], change the access to the tables in the [first_tab; last_tab] not to use join buffering. This is needed because some semi-join strategies cannot be used together with the join @@ -13856,16 +13913,16 @@ static bool check_interleaving_with_nj(J forking approach) */ -void optimize_wo_join_buffering(JOIN *join, uint first_tab, uint last_tab, +void Optimize_table_order::optimize_wo_join_buffering( + uint first_tab, uint last_tab, table_map last_remaining_tables, bool first_alt, uint no_jbuf_before, double *reopt_rec_count, double *reopt_cost) { double cost, outer_fanout, inner_fanout= 1.0; table_map reopt_remaining_tables= last_remaining_tables; - uint i; - DBUG_ENTER("optimize_wo_join_buffering"); + DBUG_ENTER("Optimize_table_order::optimize_wo_join_buffering"); if (first_tab > join->const_tables) { @@ -13878,10 +13935,10 @@ void optimize_wo_join_buffering(JOIN *jo outer_fanout= 1.0; } - for (i= first_tab; i <= last_tab; i++) + for (uint i= first_tab; i <= last_tab; i++) reopt_remaining_tables |= join->positions[i].table->table->map; - for (i= first_tab; i <= last_tab; i++) + for (uint i= first_tab; i <= last_tab; i++) { JOIN_TAB *rs= join->positions[i].table; POSITION pos, loose_scan_pos; @@ -13926,23 +13983,19 @@ void optimize_wo_join_buffering(JOIN *jo } -/* +/** Do semi-join optimization step after we've added a new tab to join prefix - SYNOPSIS - advance_sj_state() - join The join we're optimizing - remaining_tables Tables not in the join prefix - new_join_tab Join tab that we are adding to the join prefix - idx Index of this join tab (i.e. number of tables - in the prefix) - current_record_count INOUT Estimate of #records in join prefix's output - current_read_time INOUT Cost to execute the join prefix - loose_scan_pos IN A POSITION with LooseScan plan to access - table new_join_tab - (produced by the last best_access_path call) + @param remaining_tables Tables not in the join prefix + @param new_join_tab Join tab that we are adding to the join prefix + @param idx Index of this join tab (i.e. number of tables + in the prefix) + @param[in,out] current_record_count Estimate of #rows in join prefix's output + @param[in,out] current_read_time Cost to execute the join prefix + @param loose_scan_pos A POSITION with LooseScan plan to access table + new_join_tab (produced by last best_access_path call) - DESCRIPTION + @details Update semi-join optimization state after we've added another tab (table and access method) to the join prefix. @@ -13973,20 +14026,29 @@ void optimize_wo_join_buffering(JOIN *jo See setup_semijoin_dups_elimination() for a description of what kinds of join prefixes each strategy can handle. */ - -static -void advance_sj_state(JOIN *join, table_map remaining_tables, + +void Optimize_table_order::advance_sj_state( + table_map remaining_tables, const JOIN_TAB *new_join_tab, uint idx, double *current_record_count, double *current_read_time, POSITION *loose_scan_pos) { - TABLE_LIST *emb_sj_nest= new_join_tab->emb_sj_nest; - POSITION *pos= join->positions + idx; + TABLE_LIST * const emb_sj_nest= new_join_tab->emb_sj_nest; + POSITION * const pos= join->positions + idx; + + /* + Semi join nests cannot be nested, hence we never need to advance the + semi join state of a materialized semi join query. + In fact, doing this may cause undesirable effects because all tables + within a semi join nest have emb_sj_nest != NULL, which triggers several + of the actions inside this function. + */ + DBUG_ASSERT(join->emb_sjm_nest == NULL); /* Add this table to the join prefix */ remaining_tables &= ~new_join_tab->table->map; - DBUG_ENTER("advance_sj_state"); + DBUG_ENTER("Optimize_table_order::advance_sj_state"); pos->prefix_cost.convert_from_cost(*current_read_time); pos->prefix_record_count= *current_record_count; @@ -14082,7 +14144,7 @@ void advance_sj_state(JOIN *join, table_ Calculate correct costs and fanout */ double reopt_cost, reopt_rec_count; - optimize_wo_join_buffering(join, pos->first_firstmatch_table, idx, + optimize_wo_join_buffering(pos->first_firstmatch_table, idx, remaining_tables, FALSE, idx, &reopt_rec_count, &reopt_cost); if (reopt_cost < DBL_MAX) @@ -14154,7 +14216,7 @@ void advance_sj_state(JOIN *join, table_ somewhere but reserving space for all cases would require too much space. We will re-calculate POSITION structures later on. */ - optimize_wo_join_buffering(join, pos->first_loosescan_table, idx, + optimize_wo_join_buffering(pos->first_loosescan_table, idx, remaining_tables, TRUE, //first_alt pos->first_loosescan_table + n_tables, @@ -14435,6 +14497,20 @@ void advance_sj_state(JOIN *join, table_ /** Nested joins perspective: Remove the last table from the join order. + @details + Remove the last table from the partial join order and update the nested + joins counters and cur_embedding_map. It is ok to call this + function for the first table in join order (for which + check_interleaving_with_nj has not been called) + + This function rolls back changes done by: + - check_interleaving_with_nj(): removes the last table from the partial join + order and update the nested joins counters and cur_embedding_map. It + is ok to call this for the first table in join order (for which + check_interleaving_with_nj() has not been called). + - advance_sj_state(): removes the last table from join->cur_sj_inner_tables + bitmap. + The algorithm is the reciprocal of check_interleaving_with_nj(), hence parent join nest nodes are updated only when the last table in its child node is removed. The ASCII graphic below will clarify. @@ -14468,38 +14544,19 @@ void advance_sj_state(JOIN *join, table_ will however not influence NJ1 since it did not un-cover the last table in NJ2. - SYNOPSIS - backout_nj_sj_state() - last join table to remove, it is assumed to be the last in current - partial join order. - - DESCRIPTION - - Remove the last table from the partial join order and update the nested - joins counters and join->cur_embedding_map. It is ok to call this - function for the first table in join order (for which - check_interleaving_with_nj has not been called) - - This function rolls back changes done by: - - check_interleaving_with_nj(): removes the last table from the partial join - order and update the nested joins counters and join->cur_embedding_map. It - is ok to call this for the first table in join order (for which - check_interleaving_with_nj() has not been called). - - advance_sj_state(): removes the last table from join->cur_sj_inner_tables - bitmap. - - @param remaining_tables remaining tables to optimize, assumed to not contain - tab (@todo but this assumption is violated in practice) + @param remaining_tables remaining tables to optimize, assumed to not contain + tab + (@todo but this assumption is violated in practice) @param tab join table to remove, assumed to be the last in current partial join order. */ -static void backout_nj_sj_state(const table_map remaining_tables, - const JOIN_TAB *tab) +void Optimize_table_order::backout_nj_sj_state(const table_map remaining_tables, + const JOIN_TAB *tab) { /* Restore the nested join state */ TABLE_LIST *last_emb= tab->table->pos_in_table_list->embedding; - JOIN *join= tab->join; + for (;last_emb != NULL; last_emb= last_emb->embedding) { if (last_emb->on_expr) @@ -14510,24 +14567,24 @@ static void backout_nj_sj_state(const ta bool was_fully_covered= nest->is_fully_covered(); if (--nest->counter_ == 0) - join->cur_embedding_map&= ~nest->nj_map; + cur_embedding_map&= ~nest->nj_map; if (!was_fully_covered) break; - join->cur_embedding_map|= nest->nj_map; + cur_embedding_map|= nest->nj_map; } } /* Restore the semijoin state */ - TABLE_LIST *emb_sj_nest= tab->emb_sj_nest; + TABLE_LIST * const emb_sj_nest= tab->emb_sj_nest; if (emb_sj_nest) { /* If we're removing the last SJ-inner table, remove the sj-nest */ if ((remaining_tables & emb_sj_nest->sj_inner_tables) == (emb_sj_nest->sj_inner_tables & ~tab->table->map)) { - tab->join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables; + join->cur_sj_inner_tables &= ~emb_sj_nest->sj_inner_tables; } } } === modified file 'sql/sql_select.h' --- a/sql/sql_select.h 2011-03-29 07:30:44 +0000 +++ b/sql/sql_select.h 2011-04-06 11:56:55 +0000 @@ -1675,11 +1675,10 @@ public: bool first_record,full_join, no_field_update; bool group; /**< If query contains GROUP BY clause */ bool do_send_rows; - table_map const_table_map,found_const_table_map; - /* - Bitmap of all inner tables from outer joins - */ - table_map outer_join; + table_map all_table_map; /**< Set of tables contained in query */ + table_map const_table_map; /**< Set of tables found to be const */ + table_map found_const_table_map; /**< Tables that are const and non-empty */ + table_map outer_join; /**< Bitmap of all inner tables from outer joins */ /* Number of records produced after join + group operation */ ha_rows send_records; ha_rows found_records,examined_rows,row_limit; @@ -1700,20 +1699,15 @@ public: /******* Join optimization state members start *******/ /* - pointer - we're doing optimization for a semi-join materialization nest. - NULL - otherwise + if non-NULL, we are optimizing a materialized semi join nest. + if NULL, we are optimizing a complete join plan. + This member is used only within the class Optimize_table_order, and + within class Loose_scan_opt (called from best_access_path()). */ TABLE_LIST *emb_sjm_nest; /* Current join optimization state */ - POSITION *positions; - - /* - Bitmap of nested joins embedding the position at the end of the current - partial join (valid only during join optimizer run). - */ - nested_join_map cur_embedding_map; - + POSITION *positions; /* Bitmap of inner tables of semi-join nests that have a proper subset of their tables in the current join prefix. That is, of those semi-join --===============8785819318547584788== MIME-Version: 1.0 Content-Type: text/bzr-bundle; charset="us-ascii"; name="bzr/roy.lyseng@stripped" Content-Transfer-Encoding: 7bit Content-Disposition: inline # Bazaar merge directive format 2 (Bazaar 0.90) # revision_id: roy.lyseng@stripped # target_branch: file:///home/rl136806/mysql/repo/mysql-work5/ # testament_sha1: 5e7c478a080a79956eec68410ca3947ac3fadd37 # timestamp: 2011-04-06 13:57:46 +0200 # base_revision_id: tor.didriksen@stripped\ # cgdn0ukb1q3jqn1z # # Begin bundle IyBCYXphYXIgcmV2aXNpb24gYnVuZGxlIHY0CiMKQlpoOTFBWSZTWQdGmQwADu7/gH/4H6V///// //f/6r////9gH31uY3ztvHs4BkSVoYTZorb2a++59tvTDuzQClHcr3rN3W0E7ZjNmFO3ie7UDVPC KEC0DGtbSGbZu5r5765Fu4O+2p9M7cJQQjIBMgmmiNTymxSem1T9U9qZMk0eSAaAaPSAPSaNDTam DTQECEJomgk/ST1HqaZNAAGgGgAGgAAAADRppU/SKnmqbUB6gAAAAaAAAAAADQ0AAJNKJMgKGiMj TRtA1U9QeE2pomj1PUzQ0jIeoeo0DZDU0zUbUwik1NKejQTTaIiHiaj1MTagxDI9R6jTQZA8poaa aaAA0GgkSCAEBNT01DBNKn+mptRk00p6Yk/VNPCjxNCAaHpANNMEb/UJJIziKCt9HkYvmfeL9iUH FKeXswXB1R7vVEkHV8v0H0XxkSWEIF5jEVwvvlGCRUSSo4rAsRb+tzLpYytjEPCKSHIUmxeHZNjq oh0FlaECYJGk0fX+9AcrPq+/P55WGWNOA+E2bVOHmQSWOg4yjGQjEV/Bmjmxo6xau2SM2tSo1e+G L63WzjzqILgPsZMXGLE86j+aDTZaN51KqkOR9krfXm9WqejrevpdEwWx/YycFOXkDQt6Neacnobc exrRjd8UauE9ulNy4qcmfM5nFlVWb4/nzlulLlWal603d9h8Y8ym+krW5I3Z7JZwwlclurN3WX0Z 2itn3rfljxaEXib5zcU6n+mfB3AbKKk+65wuWr0Sgse3NbaKFPSCGkTaQjU0kd7ArOOTCTIaPraJ NJWtLKDrzPHYYWmE5xODGuFxi3O6HtEq0pVEOCSBLhYohzCZKxial8dSKVRN2ZltGLSGUyZWVUrh ZiGMFb2UK01dWUwmP2PuugmWbf1y1zh9vCYIQeIfhHkZ9vT2VyYIQZNQhCysnjSAe6wKJDsQyzgw TSk096wNNqAXy67ZfbsAOEh+dpqbcckMokYwEYSLITCQhhR05WBohI73vIGp1q/9RhlbJK+qo0kx NdYpjZtfrW1YrrVPYjVj0nh6zU78CfeE6te9yju2OssiL0f1jkYyWOWJbzPY92qBHOP7D4D0DQgb BA2JJeHxdT9oCD0eB6Yfh4e9E9QmWh4+C4sieoN59O/397620Mg3087NuG2syhBcpBm9Mnsm5Z4j FM972mVAg3vgzFUtQbwqBSmGN1LC0YYSbkssBlwgR6iLOpZZJh5T8E3xZaYF1fN2siHGHBotm+Is Exe9yVEVfF4tIayAEziFVw6EpciBgYw4U0Uw8sCQl7qMSbO4YthbWVcJTURNlAgTOMK1SiCmZmLt hg4dQMFBYxBlw9YVMFiSga1NhVthYpbkILEYKNEsjArCirrciSKNobD2vSsW8fb548lh+P3j38vi xYT5rEETuRevZUOCbZ+NH4+2CXY2306fD5aXe2pdauJPucZMzsSSsQPkyJ3GNWuryyY2CmNrJdBj YKHQ3ZjCW3wHiUXtyrkERMrLOnjIJBtz9OYFcM2F9fYdDGp7bE2LjRq9M26sLpvh2nyEKjDJjynT YOpbynLEKcE4oooULGelBxMeTA7L9mHAr1geueN9bahF6CBqviUVi76bzCy/GFsJ3F3ba4uccXT7 cYYy1NAtO8gyjJAQnttqsa/3oSiate+yJSy61f+GnJdcZLrjeZF9Ut9psxfjdyw/WuXph3oCoN/J 4gmTG0o0Km2OGXYeAbawoFBZxeHB8sLrtHToHuVUdhyC482l6Ozne29rZK9v08sYmpZGLF52hEw0 kjinqRbgIiFd9G0gMHBsFUqrA6VR0DVaKrrb6BbqvJWutu/Pr8/d97BBYoWGthWdDGexdXE2vsll /GtQqQmN5a73N8ljs5rivG9m58gOMHI3D/o8servymt+1iBEMCVGyw+VrwLfIFQBYiCBe47zDpza diDi1uy1bCdmYdEPo3cV2QwWx8zy4cqpjBAf3shw/O4rQHeHkmdildEKI6cztny0vOdl6jkJSRwo Xh+xBtBfhT6J7jJ50qLQkJ5M3etIj1Qj18og0lWFC9xZkbNKO+TYvfeZ3KTSKodZ06ji3bE1Vhxo t9m7TLmxw0LFohVdo2hRRlxshauhrWylhlD5ra76tVbDnPGuG4wxyQnMvL5jIYOFBHTEg9k4qUlF 4zaDsmWF8Z226wYKfA17986Kx9spJXIV35ws82xZKtRVwoB7w3IGXWk6Xu1x0zQd3pdM+We6W3vl +xVEW9YN146BpIubAoWKxbN+KLeMK5tj1VuHeTgiETBiJMoQ4zrgWMinolxfapVjdJYJy2jIcXgF FT0v6F8vn2/Fs2+E7lOfzcUeHBsgqxQYQjgIZKCZqFWlHPy+7G2cfnQX0fLSlfvTaE1ZoHlUGWfz K5j2l4YTT+5tPuecWFD3w7ShvYDAvoFX2T9oR0TG1YGIQzzJvbSqu2KZi2bJEZx4C9syRJfridV1 lIB7j6hB1L2TCtfa098nfDpTGpuCZXivbG1w51DHvf6kgRnzyy+9t11wijHYoRORk0pUtmZ3Es1u Zo689Di/TusOp6F9O3BHyufxqKiyuXcAY46NwUk2IxpKGVHMdm51jOe7QTyqorMiok1zELPxSPQ1 QCswVF/T64SNVgWyTYg8p4GupPjLmHGslSds+UKdIgglmVmbxs7Kr9qqVKvy6UH9XuW+L8hkjzIG kawx3CW5F6CTUlByFS77yGSuLUgdnNE5WGDGRsimEa5m0XabTrQsD6CoaDQshiehAjVNvUk1Qmah gMpE6ogVZEHmXwkewB22c5ncWG687QOPFi2Mgjr3TLO7Mw0ZyzNAlmJMurvawtI77uqO3XQMVUSa 1yDKWJegkckl0o5zoa6Uwf3Q9+Obmtkvvzmc2zu4J3MPMs7u5kQShWiTu051xMoWoaM3b6Ew7Jvy 2SdaBsk3MeFIuGQy2soQVCj2BdV9vwYZ1q+wBfDgYAZAmyLJnYmyuZdi42kCiH9n6l4zfFkQYEOb uubKACAyEUldYo8StoRZXGcPgJrIZStLsPJShmBdVmbEmJjWySFQJq8UMIdE0xYszysDGemOo112 KzaOUrcYJemwVcS6ez6qD47BJ127AdulAhAmCnM6c6IYR1NlNBIJNkgSJAQb+Sz8VnulCKWFbvZD iv8dCzN6mep251SBbcb5BgFkJ2kNgHD0apGm1xQCVeELXvdCV1bhElFuFzvBd0iC74N+EOsimo4D Bmb1DxJypNBLrFzeu5mUZmERdM89B5g8Y65Mq+x1T2CMDaLG+H7UCS24IjYu+7sIFo3VqXlFcZxT 1Y48ew097Le3ffQgBaOhoKjQtGScYSA0caQOIHdkYH/RlBRGiCQi2ncVKmFVXVWdkvnVbXxEQcEX DqLAEuFwRYGLYDBKHIPLpZVvK8N50TbO1tEXg0F5a4xDYayCgWlIMYrPGpwZWHvn8VuNMi9iyIIF pLOQTakUvpnU7bLREvRW5JpZ2abQ9quq2ErdL+BFMAKZBNlxKiFZmG404nJE5yHYSRa+QrEEaEXm 9ppAUG7awMbqXbbXJsk03Bahjld6D3C0Vo8k8GHXQHUdguga86xwY4cKZXhqLDi3I3abq73Y0VAD YrGJcJRmXw4CggCVVMChhgjlNmZuRHMd3ITkxXGi+gA6k7S78cACfBAvKVlhSyysy4xciQIrHIdf P4DqNgNWXJ30whljeH3BbkVZuGgNZlpollcAF+FFtxCL1OmpZcFVdFGW0AIXz6rKy8jrvkbjECzB WwZYaJDeI9caBQpjeb4DiRwMgbaBOzYtHFzvssKyvMxTWY0J0xtLtVOBhKHXAgPmZyT3So8Djovt jccBuFbFdAdziU2xUgdEPCe8cTTKgcO3nEyhr5rWKoWuya7u4C4UAdwjPaoJJprX0C9zlms0txaO fO9I4m2UxKoEe+aeqvw8mVxOLShIQllUghQYHMarMOGThppeZu0UXLKo87M6bbs108Qddw7QbNYg NcFrxEkwp5Vyqwo94xzAFgBi4yQeRG19r6cyx5NbZnJcwrWw6B1eypehV45Yo5pko7DOWFAr3jAv OmmTazawFkBV2thu7LmwTsoNRnkqrAtqm8cSRkYXyK6WnaBh7m/hnvTHrKr88o5CTjpIGs2uZ79c EVZg1WasmDluiqvRbc7libGHFmrtHCg8236KxQMqihJs6Jw2KV3tkDyYZYrNSHvsieSDR4dZbO1T mDf1gqHci/D2Srg/3b5dfoNFN52fbcylKfXIaaYR9C6p8iJlqJHd26tFj6flJM/oqHHAIGa+p2ID KZnkQkBs7MNPdV7f/H6/2aQ/wA5e0qo0nzQJrfb+PXk+ly4nEGwPkasWkzT6/64jx/Fsz3M6eM1J JZqEM10urNZEfzlQf8xh/7zR+5AMReshEX8d+K5xt7IUJp2P8LgPqOdhYtQFQ+HZGhDYMb3iBkDp W1HXYDZQrAvRD/2AYA76bHzkOO4+h/yQ/jRRRReYuy3/LmwVMNrBUhuvEDMQFcfCqRz/VJ95EQbj MG+/fK6IbnUVA2SLGNaUZnEJafnlEOHR4vqxhLW3q+ZkMUhj30BMgG3CBrqTLZlCvsEmN2CeQXwG rDjY+S4IHPOwHY/v2k+54ktj78J8YF+AInt05YtYSkUntAlT2TjU5JXYIxwXHaT6R5iwLTYuCY3f RLSGTlI0+IVnBKkiDInAKVgpL4QUYirmXoTdMOgQOcEwGJy300ZOacXWtM8JvzDXcKqiO6GAdm/i AZTZHM7hMzkiMoFkOWvbmgZ20RSLBA4u4mICixZpJJt00S8XTEMuaYxUDagpUhKjk2KjA76OzCPN iO9TKPzcs75ytni0CmqAdMG7hQaQgrEDEIB8ZA5+9D10jRa7uN8JiUnSDcg0JL8JBHyDXh+OJ+Ln vQtSXQNyQ6fcpjPdmFXaeUMEHgoodLP0mBKG6kvgOhpRk1nkyKFWzLtt5CzQokQQNqFtihYbG9bZ kQAhpRdHgyY5UNCobClFiTF7Fgp3oYO/nMRBMaFfTFqbRmSdsY4lrKTfmmyEicYT0N1bALbhRJKq 8trJttbIiimimIcLhWfW+7L128whsVGJnJR+To2mfau4/SfyargWAldxSgFAEniYuXEjDy/g03GT yj5CPiNt0x8t4HlJurECiQhBNMfzhZ9bDTS8fcLsRBjhcggYl/2IInqkHEX+ENVuovE0wnbOBaef FpUIv/AMEG1KsWEMCJEQ8hL1+U+xWeZ290iQ2xK1oREsVzvi5sgZknZpcZm+2YnIK8GgKSa+ADeS PDSH6Pr/twB1+sXrYWCQ2Otlo2Slh2duQuVFkieQE9jqD7pu6mEeqEVqm8OPPec/TjEx0LD8yv+7 r9W7E4TkIvsvaBemaCuJel0Z4tCgsFETQZTNktaqjaTH6mNzERDEvkOW7z/LZ4XB7CwIwAzwG7EZ JOYHOFEhoT0gnEfkn0gOmE+IahHeTbj53RneM6X2iIhFOc2QyyQqSJc6e4DHQu9SEyh7aZI6InmP GnVWKinxnSN4/qMUu1DViSNiCSS0A4rpH8775F3VCJnvnrLrqFlWFlYuPlBKe0KHBGTg1ZUqssA7 hUD5ZGsK9RBCCA9TMLEKAMGGRUXNBxrxejAXi97JDIxyQCSClG5tfhbXqtyjPAXdrtpcUiAxIQlC CShGZogsvkpppOZwfPMAp8R/r80n1/GpiPkL9M8rjMc9vQnRZoMrkcFJsSQTLLYRMKyWwBgTGxMQ tgdpDSE0bFQgoPRobYdC0ZUqLuRnf138dbb7lWF5AaeawhlVBzEsYmhGUc+PDC2NWYrWphIasaVt NgBfdZAE16e/I0A46nywFjQ1DPqZ372Ekgp5jwmoujVmjbc+VdvjYkmwRPPW9nJxJiAnd4jT+zIg bbYOQ2lDCoFuIjFgb7zdZpkmDTOssVcaRzSw6ddgiSVVm20J2QqKUBZ40QFAF0wQKtkXvcTc5Sck 7GeIrUJJLpaKSgSZBRFlQnwugzYGfZRKSRmkzDLVFtgjMFe7PHy1zJRFzRY1kxGhqhAsWFzEUJS9 0UuA2sUBo2zJiRCQThJeK4Y/xGZcjEaNNQGPAqNccxitSpL8DDbLgyZghim4uK8c/UNKvFwhoY2D Q0kR2gzE3eg9p7ShznhU3Gqg06wwGI3QpxVlc7TGu8SfccRcFsOsh4SBpIsDyHPRB+liNCqNUj21 UF4NiYih0IijDFiOk0tELWwQrTct6WJZTK6wuuYFOg/IBzH3tjtJwt15escjn2vgTySKxVValVjF gkSNEvWJQgkTvEeBMQPtWUAPxoCxGCMWQG800Jn3yYpWhi4kQNBgojFUwQdclOAD0O/Akmx5iTJm YJGuR6QKGqpsJCaDs7TJEzxMIcT4SPOix4cphckjHqRgLFmCnJ/BC+Zh+5h/Nq1PPhr0uPdbcNoh wNDaMlZW63rA5lC9RvzFzvy2Ii4Fck0InLveyd/U4U0lq2DCCwxSg4T5Xw4zIH/4wBTYVYAd0ska wpSPLRezi971Eb+jfOpMrEuGEooJgoBHAW/NJGPDhHlQ7wZ0JDGghEEhcPe7N1FjjqSE2NsQ0Bqj CeeaA4lrE0wTPpiG0Pt77EW4YD8tp0eQh5+NLnQcmjjNueukPSaqa9DnDn3SeHSImzEVhApLC1Jw JgiCAxCeuJDpDzpBYB7eaz0eKLi21Du4ltvwlp6Lfq0Maf86Tc/Puu8YajESige7EL1ulq6KK4GH kPcnYegTwMnn9TrnwGDceAbu4dH6U9J58w0nVDX2PM8AxaosShRKpWDipzh/TD4zAe1DS9sBDQB2 mSZ5iC8xEEkdzSxJtT85dcE+0NGIY0rGh2BZKLB1qKobWscSuZbEEMxl0psl1DplSqklXRCxYaNL xsCTbS1E4WJdsM7l1swlULwd5FyActkqXzy8655GSDbgrtIgG0MaiC9iUhfYIktGAuiNFx1oDNUc IQ2LeJtiWJKtgetqYMuBBknkwrA0ZKfkwVgdPxwba1v6ryEgxRCU2hC9A8jrM8C1s4qTReqll5hY eU2UL0Wxexsq0XEgcSRED/tvFORRC6UjDFLIMxcMlGSiGM4uJc4wKSucYwjUJWxhIKKRC21pkvjn jmTCJmUlAQ0ghFJvY4TOHKgZtcchZUmEpDKQUBiJIxVKJUbSdCzbrKsQxXsaIIDD1Rlis9I+BNPG OwcHehI0DEgyctqXvOWYwFiLIGoqPRotxJjR2mQzvOo0wxiER5Sf1lAk5YyUakikopRghGWJBkot JfolLt0qzDzzJG4ptw1aTaCBqGjkSWh6hdaoGoWIkdDTYZIsPTVOBA70AEQAjfAcPKQXFrgjflNO jasB4FZO/RqgffAY4XZYAK1z9nXkuvzGIAuVS70Kv+h/KOAgBlga4jp4Bgus8IA9L5d8Mfo9kL3x hfccsUNI6Wf/VnESbFKYfeJNG9BbVfLEJgDYgkWHFrrLPNJLqXXNNBx4pBCQXXM6WdQlQPp7+wDb fkJWiDWv2HuD3KSDs0DrC/8jA7D+QgGijA7iX1SWQLDeeEIddEEPInsQf+vcms38OzdftnfMEm8T U8Qti4nYN7j/90qdcIq09aUwdm8kHqQXwYRhjoF2hNpUhQ8KSGJX+/FRFJkYPznb1B95gl9qmaz7 wMTkhe4/lnhO75e1Ap1HWb4dGYjAQWIxRRElagiggioSsll7kMME/qEkz0kKEMJqx2C3wmwBW5Qr JuyqFQFhipQZUF+RWdrhrg9O9oHwi7hxlIKxH6/JzQn2AVA5rFENrqUQhOCFTUtExJhLrbc7N3ci eh2dUlYtxeoQZPm+BRTjAuaDNE5iaTR0kwPvKK1kXweohoyBXSvT+H9TwMGHyZsIQNCmSClECTaZ QictEgySkpMkyGN95613SLHK6qlvYWuEwKYO1PlEgy7VZYglDhjIIoQYRpMWU5UZWwXJds1jJAcl rwQaJHcJuEtDTnSpL2xAvkeOc4KszeYfNpiB2nkvgoHhcevWylThjcZ8ZSODrWzMSxBUeYbB22wo zsoY7Sge7cco3rzIDMzpBOB8FmCLtbkrJNQ1hEZ3GoKvmcNllb3c5qjYHmjzDSOtqa9q4COi3MqG CJr57S6aMtq3tm26zjvCiTo8RKtR/374HJbG3JorIKdjMM4h4McTwVdn4U8551b3jv9hppktp1d6 AxgITqhRl5LPA0ucGEXFKY9RiWTTLSBgwYYSoVgUQEZliUYgyaQSwRrSHgNjUbZgV3h9Lwvs4oaV w7USGRPT4xOy5+vTOSO5aM5WChTHIMkEqpBTYqFIuQIdwE031MgJwaAtUJ2UCLOAgzVBbDMMkQz6 MdlKeXdeG6bYmZllTBpds3DeaFGcHV0A42F1uUrsTWya28z3SgYOUN5jWWhqmhqJdksmwWIgskPl 6g6lj7KopUkQPUo1Ylnsf0SzKzA/OlOtq/ZpMJJMDKWkiKkFYeFJVSJskREfcyJQlrRopZglqJ74 CGLc0lsdB2ODmGFSI4RAeUg52NzkgFEmgo1EIbKKCwYZliCwKTMDzdz1XtpmIZf9M5hCdvWjBiVG XP5CPHVFZJS5bAppmpbhdBJCFaTdztabRctio4xaOKYSwQMGdZiFOMgcEFo0fCFt6dUO1bjARMRZ MGjRCcbrLHVGLo9KBIJ3WAZuD7iZUt5tQFSQu4GzhiiGL0lJ7CHNdZvG75WHk1tJhC05Hqpn3Avk 6JzvfLfXiglUSv2pQIIMqYmAlu5zgBwmkvqZj308h6nkyGyDzPcpxfyb1gsGiTDabyupB2YHQjBW k29UmdpQyfEaE36aQ8ZiHiBJMzJNWGCU6qQ8zPnHLORHIlJ72djnO08EoSzoBSnQXpNwwgcjLhSH RCpjR2XayUckzXVRnsCMIDJRAd18eKSTvF7DaZfbegrILzDYBgMP6BpJDaNeMzmB7wGozPP/gtmB gZ9ygcMJ/4u5IpwoSAOjTIYA --===============8785819318547584788==--