diff options
| -rw-r--r-- | sql/item_cmpfunc.cc | 6 | ||||
| -rw-r--r-- | sql/opt_subselect.cc | 94 | ||||
| -rw-r--r-- | sql/opt_subselect.h | 2 | ||||
| -rw-r--r-- | sql/sql_join_cache.cc | 2 | ||||
| -rw-r--r-- | sql/sql_select.cc | 698 | ||||
| -rw-r--r-- | sql/sql_select.h | 49 | ||||
| -rw-r--r-- | sql/sql_test.cc | 90 | ||||
| -rw-r--r-- | sql/sql_union.cc | 1 |
8 files changed, 712 insertions, 230 deletions
diff --git a/sql/item_cmpfunc.cc b/sql/item_cmpfunc.cc index 636cf3014a2..8d90da50e0d 100644 --- a/sql/item_cmpfunc.cc +++ b/sql/item_cmpfunc.cc @@ -5733,6 +5733,8 @@ Item_field* Item_equal::get_first(Item_field *field) It's a field from an materialized semi-join. We can substitute it only for a field from the same semi-join. */ +#if 0 + psergey3:remove: JOIN_TAB *first; JOIN *join= field_tab->join; int tab_idx= field_tab - field_tab->join->join_tab; @@ -5746,10 +5748,12 @@ Item_field* Item_equal::get_first(Item_field *field) // Found first tab that doesn't belong to current SJ. break; } +#endif /* Find an item to substitute for. */ while ((item= it++)) { - if (item->field->table->reginfo.join_tab >= first) + //if (item->field->table->reginfo.join_tab >= first) + if (item->field->table->pos_in_table_list->embedding == emb_nest) { /* If we found given field then return NULL to avoid unnecessary diff --git a/sql/opt_subselect.cc b/sql/opt_subselect.cc index 38ab326910e..e62effc76b8 100644 --- a/sql/opt_subselect.cc +++ b/sql/opt_subselect.cc @@ -2607,6 +2607,9 @@ void fix_semijoin_strategies_for_picked_join_order(JOIN *join) } } +enum_nested_loop_state +end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records); + /* Setup semi-join materialization strategy for one semi-join nest @@ -2628,10 +2631,11 @@ void fix_semijoin_strategies_for_picked_join_order(JOIN *join) TRUE Error */ -bool setup_sj_materialization(JOIN_TAB *tab) +bool setup_sj_materialization(JOIN_TAB *sjm_tab) { uint i; DBUG_ENTER("setup_sj_materialization"); + JOIN_TAB *tab= sjm_tab->bush_children->start; TABLE_LIST *emb_sj_nest= tab->table->pos_in_table_list->embedding; SJ_MATERIALIZATION_INFO *sjm= emb_sj_nest->sj_mat_info; THD *thd= tab->join->thd; @@ -2659,10 +2663,13 @@ bool setup_sj_materialization(JOIN_TAB *tab) DBUG_RETURN(TRUE); /* purecov: inspected */ sjm->table->file->extra(HA_EXTRA_WRITE_CACHE); sjm->table->file->extra(HA_EXTRA_IGNORE_DUP_KEY); + //psergey2-todo: need this or can take advantage of re-init functionality? tab->join->sj_tmp_tables.push_back(sjm->table); tab->join->sjm_info_list.push_back(sjm); sjm->materialized= FALSE; + sjm_tab->table= sjm->table; + if (!sjm->is_sj_scan) { KEY *tmp_key; /* The only index on the temporary table. */ @@ -2675,8 +2682,9 @@ bool setup_sj_materialization(JOIN_TAB *tab) temptable. */ TABLE_REF *tab_ref; - if (!(tab_ref= (TABLE_REF*) thd->alloc(sizeof(TABLE_REF)))) - DBUG_RETURN(TRUE); /* purecov: inspected */ + //if (!(tab_ref= (TABLE_REF*) thd->alloc(sizeof(TABLE_REF)))) + // DBUG_RETURN(TRUE); /* purecov: inspected */ + tab_ref= &sjm_tab->ref; tab_ref->key= 0; /* The only temp table index. */ tab_ref->key_length= tmp_key->key_length; if (!(tab_ref->key_buff= @@ -2733,6 +2741,7 @@ bool setup_sj_materialization(JOIN_TAB *tab) if (!(sjm->in_equality= create_subq_in_equalities(thd, sjm, emb_sj_nest->sj_subq_pred))) DBUG_RETURN(TRUE); /* purecov: inspected */ + sjm_tab->type= JT_EQ_REF; } else { @@ -2818,8 +2827,18 @@ bool setup_sj_materialization(JOIN_TAB *tab) /* The write_set for source tables must be set up to allow the copying */ bitmap_set_bit(copy_to->table->write_set, copy_to->field_index); } + sjm_tab->type= JT_ALL; + + /* Initialize full scan */ + sjm_tab->read_first_record= join_read_record_no_init; + sjm_tab->read_record.copy_field= sjm->copy_field; + sjm_tab->read_record.copy_field_end= sjm->copy_field + + sjm->sjm_table_cols.elements; + sjm_tab->read_record.read_record= rr_sequential_and_unpack; } + sjm_tab->bush_children->end[-1].next_select= end_sj_materialize; + DBUG_RETURN(FALSE); } @@ -3919,8 +3938,26 @@ static void remove_subq_pushed_predicates(JOIN *join, Item **where) } -bool do_jtbm_materialization_if_needed(JOIN_TAB *tab) +/* + Join tab execution startup function. + + DESCRIPTION + Join tab execution startup function. This is different from + tab->read_first_record in the regard that this has actions that are to be + done once per join execution. + + Currently there are only two possible startup functions, so we have them + both here inside if (...) branches. In future we could switch to function + pointers. + + RETURN + FALSE Ok + TRUE Error, join execution is not possible. +*/ + +bool join_tab_execution_startup(JOIN_TAB *tab) { + DBUG_ENTER("join_tab_execution_startup"); Item_in_subselect *in_subs; if (tab->table->pos_in_table_list && (in_subs= tab->table->pos_in_table_list->jtbm_subselect)) @@ -3936,9 +3973,54 @@ bool do_jtbm_materialization_if_needed(JOIN_TAB *tab) hash_sj_engine->is_materialized= TRUE; if (hash_sj_engine->materialize_join->error || tab->join->thd->is_fatal_error) - return TRUE; + DBUG_RETURN(TRUE); } } - return FALSE; + else if (tab->bush_children) + { + /* It's a merged SJM nest */ + int rc; // psergey3: todo: error codes! + JOIN *join= tab->join; + SJ_MATERIALIZATION_INFO *sjm= tab->bush_children->start->emb_sj_nest->sj_mat_info; + JOIN_TAB *join_tab= tab->bush_children->start; + + if (!sjm->materialized) + { + /* + Now run the join for the inner tables. The first call is to run the + join, the second one is to signal EOF (this is essential for some + join strategies, e.g. it will make join buffering flush the records) + */ + if ((rc= sub_select(join, join_tab, FALSE/* no EOF */)) < 0 || + (rc= sub_select(join, join_tab, TRUE/* now EOF */)) < 0) + { + //psergey3-todo: set sjm->materialized=TRUE here, too?? + DBUG_RETURN(rc); /* it's NESTED_LOOP_(ERROR|KILLED)*/ + } + /* + Ok, materialization finished. Initialize the access to the temptable + */ + sjm->materialized= TRUE; +#if 0 + psergey3: already done at setup: + if (sjm->is_sj_scan) + { + /* Initialize full scan */ + JOIN_TAB *last_tab= join_tab + (sjm->tables - 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->sjm_table_cols.elements; + last_tab->read_record.read_record= rr_sequential_and_unpack; + } +#endif + } + } + + DBUG_RETURN(0); } diff --git a/sql/opt_subselect.h b/sql/opt_subselect.h index 2f6c9d87367..b0dc4059858 100644 --- a/sql/opt_subselect.h +++ b/sql/opt_subselect.h @@ -372,5 +372,5 @@ void get_delayed_table_estimates(TABLE *table, double *scan_time, double *startup_cost); -bool do_jtbm_materialization_if_needed(JOIN_TAB *tab); +bool join_tab_execution_startup(JOIN_TAB *tab); diff --git a/sql/sql_join_cache.cc b/sql/sql_join_cache.cc index 33e688fae54..13c5e5c8ee3 100644 --- a/sql/sql_join_cache.cc +++ b/sql/sql_join_cache.cc @@ -1778,7 +1778,7 @@ enum_nested_loop_state JOIN_CACHE_BNL::join_matching_records(bool skip_last) /* Start retrieving all records of the joined table */ - if (do_jtbm_materialization_if_needed(join_tab)) + if (join_tab_execution_startup(join_tab)) { rc= NESTED_LOOP_ERROR; goto finish; diff --git a/sql/sql_select.cc b/sql/sql_select.cc index 3cc7dafca76..7d220cdfd2c 100644 --- a/sql/sql_select.cc +++ b/sql/sql_select.cc @@ -96,7 +96,7 @@ static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item); static bool make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after); static bool only_eq_ref_tables(JOIN *join, ORDER *order, table_map tables); static void update_depend_map(JOIN *join); -static void update_depend_map(JOIN *join, ORDER *order); +static void update_depend_map_for_order(JOIN *join, ORDER *order); static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond, bool change_list, bool *simple_order); static int return_zero_rows(JOIN *join, select_result *res,TABLE_LIST *tables, @@ -237,8 +237,6 @@ static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab); void get_partial_join_cost(JOIN *join, uint idx, double *read_time_arg, double *record_count_arg); static uint make_join_orderinfo(JOIN *join); -static int -join_read_record_no_init(JOIN_TAB *tab); Item_equal *find_item_equal(COND_EQUAL *cond_equal, Field *field, bool *inherited_fl); @@ -1008,15 +1006,26 @@ JOIN::optimize() /* Permorm the the optimization on fields evaluation mentioned above for all on expressions. - */ - for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++) + */ + { - if (*tab->on_expr_ref) + List_iterator<JOIN_TAB_RANGE> it(join_tab_ranges); + JOIN_TAB_RANGE *jt_range; + bool first= TRUE; + while ((jt_range= it++)) { - *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref, - tab->cond_equal, - map2table); - (*tab->on_expr_ref)->update_used_tables(); + for (JOIN_TAB *tab= jt_range->start + (first ? const_tables : 0); + tab < jt_range->end; tab++) + { + if (*tab->on_expr_ref) + { + *tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref, + tab->cond_equal, + map2table); + (*tab->on_expr_ref)->update_used_tables(); + } + } + first= FALSE; } } @@ -1026,6 +1035,7 @@ JOIN::optimize() { conds=new Item_int((longlong) 0,1); // Always false } + if (make_join_select(this, select, conds)) { zero_result_cause= @@ -1289,7 +1299,8 @@ JOIN::optimize() if (need_tmp || select_distinct || group_list || order) { for (uint i = const_tables; i < tables; i++) - join_tab[i].table->prepare_for_position(); + table[i]->prepare_for_position(); + } DBUG_EXECUTE("info",TEST_join(this);); @@ -2099,7 +2110,7 @@ JOIN::exec() WHERE clause for any tables after the sorted one. */ JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1]; - JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables]; + JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables]; //psergey2-todo: check this! for (; curr_table < end_table ; curr_table++) { /* @@ -2569,6 +2580,7 @@ make_join_statistics(JOIN *join, TABLE_LIST *tables_arg, COND *conds, all_table_map|= s->table->map; s->join=join; s->info=0; // For describe + s->bush_root_tab= NULL; s->dependent= tables->dep_tables; s->key_dependent= 0; @@ -5852,6 +5864,99 @@ prev_record_reads(JOIN *join, uint idx, table_map found_ref) } +JOIN_TAB *first_linear_tab(JOIN *join, bool after_const_tables) +{ + JOIN_TAB *first= join->join_tab; + if (after_const_tables) + first += join->const_tables; + if (first < join->join_tab + join->top_jtrange_tables) + return first; + else + return NULL; +} + + +/* + A helper function to loop over all join's join_tab in sequential fashion + + DESCRIPTION + Depending on include_bush_roots parameter, JOIN_TABS that represent + SJM-scan/lookups are produced or omitted. + + SJM Bush children are returned right after (or in place of) their container + join tab (TODO: does anybody depend on this? A: make_join_readinfo() seems + to.) +*/ + +JOIN_TAB *next_linear_tab(JOIN* join, JOIN_TAB* tab, bool include_bush_roots) //psergey2: added +{ + if (include_bush_roots && tab->bush_children) + return tab->bush_children->start; + + if (tab->last_leaf_in_bush) + tab= tab->bush_root_tab; + + if (tab->bush_root_tab) + return ++tab; + + if (++tab == join->join_tab + join->top_jtrange_tables /*join->join_tab_ranges.head()->end*/) + return NULL; + + if (!include_bush_roots && tab->bush_children) + { + tab= tab->bush_children->start; + } + return tab; +} + + +/* + A helper function to iterate over all join tables in bush-children-first order + + DESCRIPTION + + For example, for this join plan + + ot1 ot2 sjm ot3 + | +--------+ + | | + it1 it2 it3 + + + the function will return + + ot1-ot2-it1-it2-it3-sjm-ot3 ... + +*/ + +JOIN_TAB *next_depth_first_tab(JOIN* join, JOIN_TAB* tab) //psergey2: added +{ + bool start= FALSE; + if (tab == NULL) + { + /* This means we're starting. */ + if (join->const_tables == join->top_jtrange_tables) + return NULL; + + tab= join->join_tab + join->const_tables; + start= TRUE; + } + + if (tab->last_leaf_in_bush) + return tab->bush_root_tab; + + if ((start? tab: ++tab) == join->join_tab_ranges.head()->end) + return NULL; /* End */ + + if (tab->bush_children) + return tab->bush_children->start; + + return tab; +} + + +static Item *null_ptr= NULL; + /* Set up join struct according to the picked join order in @@ -5866,7 +5971,12 @@ prev_record_reads(JOIN *join, uint idx, table_map found_ref) fix_semijoin_strategies_for_picked_join_order) - create join->join_tab array and put there the JOIN_TABs in the join order - create data structures describing ref access methods. - + + NOTE + In this function we switch from pre-join-optimization JOIN_TABs to + post-join-optimization JOIN_TABs. This is achieved by copying the entire + JOIN_TAB objects. + RETURN FALSE OK TRUE Out of memory @@ -5875,7 +5985,7 @@ prev_record_reads(JOIN *join, uint idx, table_map found_ref) static bool get_best_combination(JOIN *join) { - uint i,tablenr; + uint tablenr; table_map used_tables; JOIN_TAB *join_tab,*j; KEYUSE *keyuse; @@ -5893,11 +6003,73 @@ get_best_combination(JOIN *join) used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read fix_semijoin_strategies_for_picked_join_order(join); - + + /* + psergey2-todo: Here: switch to nested structure when copying. + */ + + JOIN_TAB_RANGE *root_range= new JOIN_TAB_RANGE; + root_range->start= join->join_tab; + /* root_range->end will be set later */ + join->join_tab_ranges.empty(); + join->join_tab_ranges.push_back(root_range); + + JOIN_TAB *sjm_nest_end= NULL; + JOIN_TAB *sjm_saved_tab; /* protected by sjm_nest_end */ + for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++) { TABLE *form; + POSITION *cur_pos= &join->best_positions[tablenr]; + if (cur_pos->sj_strategy == SJ_OPT_MATERIALIZE || + cur_pos->sj_strategy == SJ_OPT_MATERIALIZE_SCAN) + { + /* + Ok, we've entered an SJ-Materialization semi-join (note that this can't + be done recursively, semi-joins are not allowed to be nested). + */ + /* + 1. Put into main join order a JOIN_TAB that represents a lookup or scan + in the temptable. + // TODO: record this join_tab to be processed by + // setup_semijoin_elimination? + */ + bzero(j, sizeof(JOIN_TAB)); + j->join= join; + j->table= NULL; //temporary way to tell SJM tables from others. + j->ref.key = -1; + j->ref.key_parts=0; + j->loosescan_match_tab= NULL; //non-nulls will be set later + j->use_join_cache= FALSE; + j->on_expr_ref= &null_ptr; + j->cache= NULL; + + /* + 2. Proceed with processing SJM nest's join tabs, putting them into the + sub-order + */ + SJ_MATERIALIZATION_INFO *sjm= cur_pos->table->emb_sj_nest->sj_mat_info; + JOIN_TAB *jt= (JOIN_TAB*)join->thd->alloc(sizeof(JOIN_TAB) * sjm->tables); + JOIN_TAB_RANGE *jt_range= new JOIN_TAB_RANGE; + jt_range->start= jt; + jt_range->end= jt + sjm->tables; + //sjm->jt_range= jt_range; + join->join_tab_ranges.push_back(jt_range); + j->bush_children= jt_range; + j->bush_root_tab= NULL; //note: a lot of code depends on bush nodes not containing one another + j->quick= NULL; + sjm_nest_end= jt + sjm->tables; + sjm_saved_tab= j; + j= jt; + //goto loop_end_not_table; + } + *j= *join->best_positions[tablenr].table; + + if (sjm_nest_end) + j->bush_root_tab= sjm_saved_tab; + else + root_range->end= j+1; form=join->table[tablenr]=j->table; used_tables|= form->map; form->reginfo.join_tab=j; @@ -5905,14 +6077,14 @@ get_best_combination(JOIN *join) form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN DBUG_PRINT("info",("type: %d", j->type)); if (j->type == JT_CONST) - continue; // Handled in make_join_stat.. + goto loop_end; // Handled in make_join_stat.. j->loosescan_match_tab= NULL; //non-nulls will be set later j->ref.key = -1; j->ref.key_parts=0; if (j->type == JT_SYSTEM) - continue; + goto loop_end; if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key) || (join->best_positions[tablenr].sj_strategy == SJ_OPT_LOOSE_SCAN)) { @@ -5923,10 +6095,24 @@ get_best_combination(JOIN *join) } else if (create_ref_for_key(join, j, keyuse, used_tables)) DBUG_RETURN(TRUE); // Something went wrong + j->records_read= join->best_positions[tablenr].records_read; + loop_end: + join->map2table[j->table->tablenr]= j; + + // If we've reached the end of sjm nest, switch back to main sequence + if (j + 1 == sjm_nest_end) + { + j->last_leaf_in_bush= TRUE; + j= sjm_saved_tab; + sjm_nest_end= NULL; + } } - for (i=0 ; i < table_count ; i++) - join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i; + join->top_jtrange_tables= join->join_tab_ranges.head()->end - + join->join_tab_ranges.head()->start; + + //for (i=0 ; i < table_count ; i++) + // join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i; update_depend_map(join); DBUG_RETURN(0); } @@ -6175,6 +6361,11 @@ JOIN::make_simple_join(JOIN *parent, TABLE *tmp_table) DBUG_RETURN(TRUE); /* purecov: inspected */ join_tab= parent->join_tab_reexec; + //psergey2: hopefully this is ok: + // join_tab_ranges.head()->start= join_tab; + // join_tab_ranges.head()->end= join_tab + 1; + top_jtrange_tables= 1; + table= &parent->table_reexec[0]; parent->table_reexec[0]= tmp_table; tables= 1; const_tables= 0; @@ -6214,6 +6405,9 @@ JOIN::make_simple_join(JOIN *parent, TABLE *tmp_table) join_tab->do_firstmatch= NULL; join_tab->loosescan_match_tab= NULL; join_tab->emb_sj_nest= NULL; + join_tab->bush_root_tab= NULL; + join_tab->bush_children= NULL; + join_tab->last_leaf_in_bush= FALSE; bzero((char*) &join_tab->read_record,sizeof(join_tab->read_record)); tmp_table->status=0; tmp_table->null_row=0; @@ -6238,6 +6432,7 @@ inline void add_cond_and_fix(Item **e1, Item *e2) } + /** Add to join_tab->select_cond[i] "table.field IS NOT NULL" conditions we've inferred from ref/eq_ref access performed. @@ -6292,9 +6487,13 @@ inline void add_cond_and_fix(Item **e1, Item *e2) static void add_not_null_conds(JOIN *join) { DBUG_ENTER("add_not_null_conds"); - for (uint i=join->const_tables ; i < join->tables ; i++) + + //for (uint i=join->const_tables ; i < join->tables ; i++) + for (JOIN_TAB *tab= first_linear_tab(join, TRUE); + tab; + tab= next_linear_tab(join, tab, FALSE)) //psergey-todo: should be TRUE here? { - JOIN_TAB *tab=join->join_tab+i; + //JOIN_TAB *tab=join->join_tab+i; if ((tab->type == JT_REF || tab->type == JT_EQ_REF || tab->type == JT_REF_OR_NULL) && !tab->table->maybe_null) @@ -6418,58 +6617,68 @@ static void make_outerjoin_info(JOIN *join) { DBUG_ENTER("make_outerjoin_info"); - for (uint i=join->const_tables ; i < join->tables ; i++) - { - JOIN_TAB *tab=join->join_tab+i; - TABLE *table=tab->table; - TABLE_LIST *tbl= table->pos_in_table_list; - TABLE_LIST *embedding= tbl->embedding; + bool top= TRUE; + List_iterator<JOIN_TAB_RANGE> it(join->join_tab_ranges); + JOIN_TAB_RANGE *jt_range; - if (tbl->outer_join) + while ((jt_range= it++)) + { + for (JOIN_TAB *tab=jt_range->start + (top ? join->const_tables : 0); + tab != jt_range->end; tab++) { - /* - Table tab is the only one inner table for outer join. - (Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a - is in the query above.) - */ - tab->last_inner= tab->first_inner= tab; - tab->on_expr_ref= &tbl->on_expr; - tab->cond_equal= tbl->cond_equal; - if (embedding) - tab->first_upper= embedding->nested_join->first_nested; - } - for ( ; embedding ; embedding= embedding->embedding) - { - /* Ignore sj-nests: */ - if (!embedding->on_expr) - continue; - NESTED_JOIN *nested_join= embedding->nested_join; - if (!nested_join->counter) + TABLE *table=tab->table; + if (!table) + continue; //psergey2: fix this when we get SJM+outer joins really working. + TABLE_LIST *tbl= table->pos_in_table_list; + TABLE_LIST *embedding= tbl->embedding; + + if (tbl->outer_join) { /* - Table tab is the first inner table for nested_join. - Save reference to it in the nested join structure. - */ - nested_join->first_nested= tab; - tab->on_expr_ref= &embedding->on_expr; + Table tab is the only one inner table for outer join. + (Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a + is in the query above.) + */ + tab->last_inner= tab->first_inner= tab; + tab->on_expr_ref= &tbl->on_expr; tab->cond_equal= tbl->cond_equal; - if (embedding->embedding) - tab->first_upper= embedding->embedding->nested_join->first_nested; - } - if (!tab->first_inner) - tab->first_inner= nested_join->first_nested; - if (tab->table->reginfo.not_exists_optimize) - tab->first_inner->table->reginfo.not_exists_optimize= 1; - if (++nested_join->counter < nested_join->n_tables) - break; - /* Table tab is the last inner table for nested join. */ - nested_join->first_nested->last_inner= tab; - if (tab->first_inner->table->reginfo.not_exists_optimize) + if (embedding) + tab->first_upper= embedding->nested_join->first_nested; + } + for ( ; embedding ; embedding= embedding->embedding) { - for (JOIN_TAB *join_tab= tab->first_inner; join_tab <= tab; join_tab++) - join_tab->table->reginfo.not_exists_optimize= 1; - } + /* Ignore sj-nests: */ + if (!embedding->on_expr) + continue; + NESTED_JOIN *nested_join= embedding->nested_join; + if (!nested_join->counter) + { + /* + Table tab is the first inner table for nested_join. + Save reference to it in the nested join structure. + */ + nested_join->first_nested= tab; + tab->on_expr_ref= &embedding->on_expr; + tab->cond_equal= tbl->cond_equal; + if (embedding->embedding) + tab->first_upper= embedding->embedding->nested_join->first_nested; + } + if (!tab->first_inner) + tab->first_inner= nested_join->first_nested; + if (tab->table->reginfo.not_exists_optimize) + tab->first_inner->table->reginfo.not_exists_optimize= 1; + if (++nested_join->counter < nested_join->n_tables) + break; + /* Table tab is the last inner table for nested join. */ + nested_join->first_nested->last_inner= tab; + if (tab->first_inner->table->reginfo.not_exists_optimize) + { + for (JOIN_TAB *join_tab= tab->first_inner; join_tab <= tab; join_tab++) + join_tab->table->reginfo.not_exists_optimize= 1; + } + } } + top= FALSE; } DBUG_VOID_RETURN; } @@ -6512,8 +6721,12 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) join->const_table_map, (table_map) 0, TRUE); DBUG_EXECUTE("where",print_where(const_cond,"constants", QT_ORDINARY);); - for (JOIN_TAB *tab= join->join_tab+join->const_tables; - tab < join->join_tab+join->tables ; tab++) + // psergey2: not extracting conditions from inside bushy nests? + //for (JOIN_TAB *tab= join->join_tab+join->const_tables; + // tab < join->join_tab+join->tables ; tab++) + for (JOIN_TAB *tab= first_linear_tab(join, TRUE); + tab; + tab= next_linear_tab(join, tab, FALSE)) { if (*tab->on_expr_ref) { @@ -6552,18 +6765,27 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) OUTER_REF_TABLE_BIT | RAND_TABLE_BIT); JOIN_TAB *tab; table_map current_map; - for (uint i=join->const_tables ; i < join->tables ; i++) + uint i= join->const_tables; + for (tab= next_depth_first_tab(join, NULL); tab; + tab= next_depth_first_tab(join, tab), i++) + //for (uint i=join->const_tables ; i < join->tables ; i++) { - tab= join->join_tab+i; + //tab= join->join_tab+i; /* first_inner is the X in queries like: SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X */ - JOIN_TAB *first_inner_tab= tab->first_inner; - current_map= tab->table->map; + JOIN_TAB *first_inner_tab= tab->first_inner; + //psergey2-todo: change this to table bitmap. + if (tab->table) + current_map= tab->table->map; + else + current_map= tab->bush_children->start->emb_sj_nest->sj_inner_tables; + bool use_quick_range=0; COND *tmp; +// psergey2-todo: is the below ok? seems to be yes. /* Tables that are within SJ-Materialization nests cannot have their conditions referring to preceding non-const tables. @@ -6607,8 +6829,20 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) } tmp= NULL; + if (cond) - tmp= make_cond_for_table(cond, used_tables, current_map, FALSE); + { + if (tab->bush_children) + { + // Reached the materialization tab + tmp= make_cond_after_sjm(cond, cond, save_used_tables, used_tables); + used_tables= save_used_tables | used_tables; + save_used_tables= 0; + } + else + tmp= make_cond_for_table(cond, used_tables, current_map, FALSE); + } + if (cond && !tmp && tab->quick) { // Outer join if (tab->type != JT_ALL) @@ -6806,7 +7040,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) } /* - Push down conditions from all on expressions. + Push down conditions from all ON expressions. Each of these conditions are guarded by a variable that turns if off just before null complemented row for outer joins is formed. Thus, the condition from an @@ -6815,8 +7049,11 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) */ /* First push down constant conditions from on expressions */ - for (JOIN_TAB *join_tab= join->join_tab+join->const_tables; - join_tab < join->join_tab+join->tables ; join_tab++) + //for (JOIN_TAB *join_tab= join->join_tab+join->const_tables; + // join_tab < join->join_tab+join->tables ; join_tab++) + for (JOIN_TAB *join_tab= first_linear_tab(join, TRUE); + join_tab; + join_tab= next_linear_tab(join, join_tab, FALSE)) { if (*join_tab->on_expr_ref) { @@ -6844,7 +7081,8 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) /* Push down non-constant conditions from on expressions */ JOIN_TAB *last_tab= tab; while (first_inner_tab && first_inner_tab->last_inner == last_tab) - { + { + //JOIN_TAB *tab; //psergey2: have our own 'tab' /* Table tab is the last inner table of an outer join. An on expression is always attached to it. @@ -6853,7 +7091,10 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) table_map used_tables2= (join->const_table_map | OUTER_REF_TABLE_BIT | RAND_TABLE_BIT); - for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++) + //for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++) + for (JOIN_TAB *tab= first_linear_tab(join, TRUE); + tab; + tab= next_linear_tab(join, tab, TRUE)) { current_map= tab->table->map; used_tables2|= current_map; @@ -6899,7 +7140,8 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) } first_inner_tab= first_inner_tab->first_upper; } - +#if 0 + psergey2-todo:remove: if (save_used_tables && !(used_tables & ~(tab->emb_sj_nest->sj_inner_tables | join->const_table_map | PSEUDO_TABLE_BITS))) @@ -6925,7 +7167,7 @@ make_join_select(JOIN *join,SQL_SELECT *select,COND *cond) used_tables= save_used_tables | used_tables; save_used_tables= 0; } - +#endif } } DBUG_RETURN(0); @@ -7114,7 +7356,7 @@ void revise_cache_usage(JOIN_TAB *join_tab) SYNOPSIS end_sj_materialize() join The join - join_tab Last join table + join_tab Points to right after the last join_tab in materialization bush end_of_records FALSE <=> This call is made to pass another record combination TRUE <=> EOF (no action) @@ -7132,7 +7374,7 @@ void revise_cache_usage(JOIN_TAB *join_tab) NESTED_LOOP_ERROR */ -static enum_nested_loop_state +enum_nested_loop_state end_sj_materialize(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) { int error; @@ -7407,8 +7649,8 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) bool statistics= test(!(join->select_options & SELECT_DESCRIBE)); bool ordered_set= 0; bool sorted= 1; - uint first_sjm_table= MAX_TABLES; - uint last_sjm_table= MAX_TABLES; + //uint first_sjm_table= MAX_TABLES; + //uint last_sjm_table= MAX_TABLES; DBUG_ENTER("make_join_readinfo"); @@ -7416,15 +7658,14 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) setup_semijoin_dups_elimination(join, options, no_jbuf_after)) DBUG_RETURN(TRUE); /* purecov: inspected */ - for (i=join->const_tables ; i < join->tables ; i++) + //for (i=join->const_tables ; i < join->tables ; i++) + i= 0; + for (JOIN_TAB *tab= first_linear_tab(join, TRUE); + tab; + tab= next_linear_tab(join, tab, TRUE), i++) { - JOIN_TAB *tab=join->join_tab+i; TABLE *table=tab->table; bool icp_other_tables_ok; - tab->read_record.table= table; - tab->read_record.file=table->file; - tab->read_record.unlock_row= rr_unlock_row; - tab->next_select=sub_select; /* normal select */ /* Determine if the set is already ordered for ORDER BY, so it can @@ -7442,24 +7683,42 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) tab->sorted= sorted; sorted= 0; // only first must be sorted - if (tab->loosescan_match_tab) - { - if (!(tab->loosescan_buf= (uchar*)join->thd->alloc(tab-> - loosescan_key_len))) - return TRUE; /* purecov: inspected */ - } - if (sj_is_materialize_strategy(join->best_positions[i].sj_strategy)) + + + //if (sj_is_materialize_strategy(join->best_positions[i].sj_strategy)) + if (tab->bush_children) // SJM { /* This is a start of semi-join nest */ - first_sjm_table= i; - last_sjm_table= i + join->best_positions[i].n_sj_tables; + //first_sjm_table= i; + //last_sjm_table= i + join->best_positions[i].n_sj_tables; + /* + psergey2: dont: if (i == join->const_tables) join->first_select= sub_select_sjm; else tab[-1].next_select= sub_select_sjm; + */ if (setup_sj_materialization(tab)) return TRUE; + table= tab->table; + } + + tab->read_record.table= table; + tab->read_record.file=table->file; + tab->read_record.unlock_row= rr_unlock_row; + + if (!(tab->bush_root_tab && + tab->bush_root_tab->bush_children->end == tab + 1)) + { + tab->next_select=sub_select; /* normal select */ + } + + if (tab->loosescan_match_tab) + { + if (!(tab->loosescan_buf= (uchar*)join->thd->alloc(tab-> + loosescan_key_len))) + return TRUE; /* purecov: inspected */ } table->status=STATUS_NO_RECORD; pick_table_access_method (tab); @@ -7551,7 +7810,8 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) } else { - tab->read_first_record= join_init_read_record; + if (!tab->bush_children) + tab->read_first_record= join_init_read_record; if (i == join->const_tables) { if (tab->select && tab->select->quick) @@ -7629,13 +7889,16 @@ make_join_readinfo(JOIN *join, ulonglong options, uint no_jbuf_after) abort(); /* purecov: deadcode */ } } - join->join_tab[join->tables-1].next_select=0; /* Set by do_select */ + uint n_top_tables= join->join_tab_ranges.head()->end - + join->join_tab_ranges.head()->start; + join->join_tab[n_top_tables - 1].next_select=0; /* Set by do_select */ -/* + /* If a join buffer is used to join a table the ordering by an index for the first non-constant table cannot be employed anymore. */ - for (i=join->const_tables ; i < join->tables ; i++) + //for (i=join->const_tables ; i < join->tables ; i++) + for (i=join->const_tables ; i < n_top_tables ; i++) { JOIN_TAB *tab=join->join_tab+i; if (tab->use_join_cache) @@ -7692,6 +7955,9 @@ bool error_if_full_join(JOIN *join) /** cleanup JOIN_TAB. + + DESCRIPTION + This is invoked when we've finished all join executions. */ void JOIN_TAB::cleanup() @@ -7700,6 +7966,7 @@ void JOIN_TAB::cleanup() select= 0; delete quick; quick= 0; + //psergey3-todo: empty merged SJM temptables here. if (cache) { cache->free(); @@ -7848,7 +8115,7 @@ void JOIN::cleanup(bool full) if (table) { - JOIN_TAB *tab,*end; + JOIN_TAB *tab; /* Only a sorted table may be cached. This sorted table is always the first non const table in join->table @@ -7861,13 +8128,13 @@ void JOIN::cleanup(bool full) if (full) { - for (tab= join_tab, end= tab+tables; tab != end; tab++) + for (tab= top_jtrange_tables?join_tab:NULL; tab; tab= next_linear_tab(this, tab, TRUE)) tab->cleanup(); table= 0; } else { - for (tab= join_tab, end= tab+tables; tab != end; tab++) + for (tab= top_jtrange_tables?join_tab:NULL; tab; tab= next_linear_tab(this, tab, TRUE)) { if (tab->table) tab->table->file->ha_index_or_rnd_end(); @@ -8005,24 +8272,29 @@ only_eq_ref_tables(JOIN *join,ORDER *order,table_map tables) static void update_depend_map(JOIN *join) { - JOIN_TAB *join_tab=join->join_tab, *end=join_tab+join->tables; - - for (; join_tab != end ; join_tab++) - { - TABLE_REF *ref= &join_tab->ref; - table_map depend_map=0; - Item **item=ref->items; - uint i; - for (i=0 ; i < ref->key_parts ; i++,item++) - depend_map|=(*item)->used_tables(); - ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT; - depend_map&= ~OUTER_REF_TABLE_BIT; - for (JOIN_TAB **tab=join->map2table; - depend_map ; - tab++,depend_map>>=1 ) - { - if (depend_map & 1) - ref->depend_map|=(*tab)->ref.depend_map; + List_iterator<JOIN_TAB_RANGE> it(join->join_tab_ranges); + JOIN_TAB_RANGE *jt_range; + + while ((jt_range= it++)) + { + for (JOIN_TAB *join_tab=jt_range->start; join_tab != jt_range->end; + join_tab++) + { + TABLE_REF *ref= &join_tab->ref; + table_map depend_map=0; + Item **item=ref->items; + uint i; + for (i=0 ; i < ref->key_parts ; i++,item++) + depend_map|=(*item)->used_tables(); + ref->depend_map=depend_map & ~OUTER_REF_TABLE_BIT; + depend_map&= ~OUTER_REF_TABLE_BIT; + for (JOIN_TAB **tab=join->map2table; + depend_map ; + tab++,depend_map>>=1 ) + { + if (depend_map & 1) + ref->depend_map|=(*tab)->ref.depend_map; + } } } } @@ -8030,7 +8302,7 @@ static void update_depend_map(JOIN *join) /** Update the dependency map for the sort order. */ -static void update_depend_map(JOIN *join, ORDER *order) +static void update_depend_map_for_order(JOIN *join, ORDER *order) { for (; order ; order=order->next) { @@ -8081,17 +8353,25 @@ remove_const(JOIN *join,ORDER *first_order, COND *cond, return change_list ? 0 : first_order; // No need to sort ORDER *order,**prev_ptr; - table_map first_table= join->join_tab[join->const_tables].table->map; + table_map first_table; table_map not_const_tables= ~join->const_table_map; table_map ref; + bool first_is_base_table= FALSE; DBUG_ENTER("remove_const"); + if (join->join_tab[join->const_tables].table) + { + first_table= join->join_tab[join->const_tables].table->map; + first_is_base_table= TRUE; + } + + prev_ptr= &first_order; *simple_order= *join->join_tab[join->const_tables].on_expr_ref ? 0 : 1; /* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */ - update_depend_map(join, first_order); + update_depend_map_for_order(join, first_order); for (order=first_order; order ; order=order->next) { table_map order_tables=order->item[0]->used_tables(); @@ -8128,7 +8408,7 @@ remove_const(JOIN *join,ORDER *first_order, COND *cond, DBUG_PRINT("info",("removing: %s", order->item[0]->full_name())); continue; } - if ((ref=order_tables & (not_const_tables ^ first_table))) + if (first_is_base_table && (ref=order_tables & (not_const_tables ^ first_table))) { if (!(order_tables & first_table) && only_eq_ref_tables(join,first_order, ref)) @@ -8204,6 +8484,8 @@ static void clear_tables(JOIN *join) must clear only the non-const tables, as const tables are not re-calculated. */ + //psergey2: this should be ok as it walks through TABLE* + // psergey2: What is this for? perhaps, we should reset the SJM temptables, too?? for (uint i=join->const_tables ; i < join->tables ; i++) mark_as_null_row(join->table[i]); // All fields are NULL } @@ -9025,7 +9307,18 @@ static int compare_fields_by_table_order(Item_field *field1, if (outer_ref) return cmp; JOIN_TAB **idx= (JOIN_TAB **) table_join_idx; - cmp= idx[field2->field->table->tablenr]-idx[field1->field->table->tablenr]; + + //psergey2: + JOIN_TAB *tab1= idx[field1->field->table->tablenr]; + if (tab1->bush_root_tab) + tab1= tab1->bush_root_tab; + + JOIN_TAB *tab2= idx[field2->field->table->tablenr]; + if (tab2->bush_root_tab) + tab2= tab2->bush_root_tab; + + cmp= tab2 - tab1; + return cmp < 0 ? -1 : (cmp ? 1 : 0); } @@ -9111,7 +9404,8 @@ Item *eliminate_item_equal(COND *cond, COND_EQUAL *upper_levels, /* Pick the "head" item: the constant one or the first in the join order - that's not inside some SJM nest. + that's not inside some SJM nest. psergey2: out-of-date comment. It is ok + inside SJM, too. */ if (item_const) head= item_const; @@ -12367,8 +12661,11 @@ do_select(JOIN *join,List<Item> *fields,TABLE *table,Procedure *procedure) Next_select_func end_select= setup_end_select_func(join); if (join->tables) { - join->join_tab[join->tables-1].next_select= end_select; - + //join->join_tab[join->tables-1].next_select= end_select; + //psergey3: + //int n_top_tables= join->join_tab_ranges.head()->end - + // join->join_tab_ranges.head()->start; + join->join_tab[join->top_jtrange_tables - 1].next_select= end_select; join_tab=join->join_tab+join->const_tables; } join->send_records=0; @@ -12497,7 +12794,7 @@ int rr_sequential_and_unpack(READ_RECORD *info) RETURN One of enum_nested_loop_state values */ - +#if 0 enum_nested_loop_state sub_select_sjm(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) { @@ -12596,7 +12893,7 @@ sub_select_sjm(JOIN *join, JOIN_TAB *join_tab, bool end_of_records) end_of_records); DBUG_RETURN(rc); } - +#endif /* Fill the join buffer with partial records, retrieve all full matches for them @@ -12848,7 +13145,7 @@ sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records) } join->thd->row_count= 0; - if (do_jtbm_materialization_if_needed(join_tab)) + if (join_tab_execution_startup(join_tab)) DBUG_RETURN(NESTED_LOOP_ERROR); error= (*join_tab->read_first_record)(join_tab); @@ -13627,13 +13924,24 @@ int join_init_read_record(JOIN_TAB *tab) return (*tab->read_record.read_record)(&tab->read_record); } -static int +int join_read_record_no_init(JOIN_TAB *tab) { + Copy_field *save_copy, *save_copy_end; + + save_copy= tab->read_record.copy_field; + save_copy_end= tab->read_record.copy_field_end; + + init_read_record(&tab->read_record, tab->join->thd, tab->table, + tab->select,1,1, FALSE); + + tab->read_record.copy_field= save_copy; + tab->read_record.copy_field_end= save_copy_end; + tab->read_record.read_record= rr_sequential_and_unpack; + return (*tab->read_record.read_record)(&tab->read_record); } - static int join_read_first(JOIN_TAB *tab) { @@ -14276,8 +14584,25 @@ end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)), *****************************************************************************/ /** - @return - 1 if right_item is used removable reference key on left_item + Check if a given equality is guaranteed to be true by use of ref access + + SYNOPSIS + test_if_ref() + root_cond + left_item + right_item + + DESCRIPTION + Check if the given "left_item = right_item" equality is guaranteed to be + true by use of [eq_]ref access method. + + We need root_cond as we can't remove ON expressions even if employed ref + access guarantees that they are true. This is because TODO + + RETURN + TRUE if right_item is used removable reference key on left_item + FALSE Otherwise + */ bool test_if_ref(Item *root_cond, Item_field *left_item,Item *right_item) @@ -14335,7 +14660,8 @@ bool test_if_ref(Item *root_cond, Item_field *left_item,Item *right_item) SYNOPSIS make_cond_for_table() cond Condition to analyze - tables Tables for which "current field values" are available + tables Tables for which "current field values" are available (this + includes used_table) used_table Table that we're extracting the condition for (may also include PSEUDO_TABLE_BITS exclude_expensive_cond Do not push expensive conditions @@ -14369,7 +14695,8 @@ make_cond_for_table(Item *cond, table_map tables, table_map used_table, return make_cond_for_table_from_pred(cond, cond, tables, used_table, exclude_expensive_cond); } - + + static Item * make_cond_for_table_from_pred(Item *root_cond, Item *cond, table_map tables, table_map used_table, @@ -14390,6 +14717,7 @@ make_cond_for_table_from_pred(Item *root_cond, Item *cond, */ !((used_table & 1) && cond->is_expensive())) return (COND*) 0; // Already checked + if (cond->type() == Item::COND_ITEM) { if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) @@ -14464,6 +14792,7 @@ make_cond_for_table_from_pred(Item *root_cond, Item *cond, */ (!used_table && exclude_expensive_cond && cond->is_expensive())) return (COND*) 0; // Can't check this yet + if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK) return cond; // Not boolean op @@ -14490,14 +14819,29 @@ make_cond_for_table_from_pred(Item *root_cond, Item *cond, } +/* + The difference of this from make_cond_for_table() is that we're in the + following state: + 1. conditions referring to 'tables' have been checked + 2. conditions referring to sjm_tables have been checked, too + 3. We need condition that couldn't be checked in #1 or #2 but + can be checked when we get both (tables | sjm_tables). + +*/ static COND * make_cond_after_sjm(Item *root_cond, Item *cond, table_map tables, table_map sjm_tables) { + /* + We assume that conditions that refer to only join prefix tables or + sjm_tables have already been checked. + */ if ((!(cond->used_tables() & ~tables) || !(cond->used_tables() & ~sjm_tables))) return (COND*) 0; // Already checked + + /* AND/OR recursive descent */ if (cond->type() == Item::COND_ITEM) { if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC) @@ -17934,16 +18278,29 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, { table_map used_tables=0; + /* psergey2 uchar sjm_nests[MAX_TABLES]; uint sjm_nests_cur=0; uint sjm_nests_end= 0; uint end_table= join->tables; + */ bool printing_materialize_nest= FALSE; uint select_id= join->select_lex->select_number; - for (uint i=0 ; i < end_table ; i++) + //for (uint i=0 ; i < end_table ; i++) + List_iterator<JOIN_TAB_RANGE> it(join->join_tab_ranges); + JOIN_TAB_RANGE *jt_range; + while ((jt_range= it++)) { - JOIN_TAB *tab=join->join_tab+i; + if (jt_range != join->join_tab_ranges.head()) + { + select_id= jt_range->start->emb_sj_nest->sj_subq_pred->get_identifier(); + printing_materialize_nest= TRUE; + } + + for (JOIN_TAB *tab= jt_range->start + 0; tab < jt_range->end; tab++) + { + //JOIN_TAB *tab=join->join_tab+i; TABLE *table=tab->table; TABLE_LIST *table_list= tab->table->pos_in_table_list; char buff[512]; @@ -17980,28 +18337,31 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, Special processing for SJ-Materialization nests: print the fake table and delay printing of the SJM nest contents until later. */ - uint sj_strategy= join->best_positions[i].sj_strategy; - if (sj_is_materialize_strategy(sj_strategy) && - !printing_materialize_nest) + //uint sj_strategy= join->best_positions[i].sj_strategy; + //if (sj_is_materialize_strategy(sj_strategy) && + // /*!printing_materialize_nest*/) + if (tab->bush_children) { + JOIN_TAB *ctab= tab->bush_children->start; /* table */ int len= my_snprintf(table_name_buffer, sizeof(table_name_buffer)-1, "<subquery%d>", - tab->emb_sj_nest->sj_subq_pred->get_identifier()); + ctab->emb_sj_nest->sj_subq_pred->get_identifier()); item_list.push_back(new Item_string(table_name_buffer, len, cs)); /* partitions */ if (join->thd->lex->describe & DESCRIBE_PARTITIONS) item_list.push_back(item_null); /* type */ - uint type= (sj_strategy == SJ_OPT_MATERIALIZE_SCAN)? JT_ALL : JT_EQ_REF; + uint is_scan= test(ctab->emb_sj_nest->sj_mat_info->is_sj_scan); + uint type= is_scan? JT_ALL : JT_EQ_REF; item_list.push_back(new Item_string(join_type_str[type], strlen(join_type_str[type]), cs)); /* possible_keys */ item_list.push_back(new Item_string("unique_key", strlen("unique_key"), cs)); - if (sj_strategy == SJ_OPT_MATERIALIZE_SCAN) + if (is_scan) { item_list.push_back(item_null); /* key */ item_list.push_back(item_null); /* key_len */ @@ -18012,15 +18372,14 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, /* key */ item_list.push_back(new Item_string("unique_key", strlen("unique_key"), cs)); /* key_len */ - uint klen= tab->emb_sj_nest->sj_mat_info->table->key_info[0].key_length; + uint klen= ctab->emb_sj_nest->sj_mat_info->table->key_info[0].key_length; uint buflen= longlong2str(klen, keylen_str_buf, 10) - keylen_str_buf; item_list.push_back(new Item_string(keylen_str_buf, buflen, cs)); /* ref */ item_list.push_back(new Item_string("func", strlen("func"), cs)); } /* rows */ - ha_rows rows= (sj_strategy == SJ_OPT_MATERIALIZE_SCAN)? - tab->emb_sj_nest->sj_mat_info->rows : 1; + ha_rows rows= is_scan ? ctab->emb_sj_nest->sj_mat_info->rows : 1; item_list.push_back(new Item_int((longlong)rows, MY_INT64_NUM_DECIMAL_DIGITS)); /* filtered */ @@ -18049,8 +18408,8 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, item_list.push_back(new Item_string(str, extra_len, cs)); /* Register the nest for further processing: */ - sjm_nests[sjm_nests_end++]= i; - i += join->best_positions[i].n_sj_tables-1; + // sjm_nests[sjm_nests_end++]= i; + //i += join->best_positions[i].n_sj_tables-1; goto loop_end; } @@ -18215,7 +18574,8 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, else if (tab->type == JT_NEXT || tab->type == JT_ALL) examined_rows= tab->limit ? tab->limit : tab->records; else - examined_rows=(ha_rows)join->best_positions[i].records_read; + //examined_rows=(ha_rows)join->best_positions[i].records_read; + examined_rows=(ha_rows)tab->records_read; item_list.push_back(new Item_int((longlong) (ulonglong) examined_rows, MY_INT64_NUM_DECIMAL_DIGITS)); @@ -18236,7 +18596,7 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, */ float f= 0.0; if (examined_rows) - f= (float) (100.0 * join->best_positions[i].records_read / + f= (float) (100.0 * tab->records_read/*join->best_positions[i].records_read*/ / examined_rows); item_list.push_back(new Item_float(f, 2)); } @@ -18400,25 +18760,6 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, } } - /* - if (sj_is_materialize_strategy(sj_strategy)) - { - if (join->best_positions[i].n_sj_tables == 1) - extra.append(STRING_WITH_LEN("; Materialize")); - else - { - last_sjm_table= i + join->best_positions[i].n_sj_tables - 1; - extra.append(STRING_WITH_LEN("; Start materialize")); - } - if (sj_strategy == SJ_OPT_MATERIALIZE_SCAN) - extra.append(STRING_WITH_LEN("; Scan")); - } - else if (last_sjm_table == i) - { - extra.append(STRING_WITH_LEN("; End materialize")); - } - */ - for (uint part= 0; part < tab->ref.key_parts; part++) { if (tab->ref.cond_guards[part]) @@ -18428,7 +18769,8 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, } } - if (i > 0 && tab[-1].next_select == sub_select_cache) + //if (i > 0 && tab[-1].next_select == sub_select_cache) + if ((tab != jt_range->start) && tab[-1].next_select == sub_select_cache) extra.append(STRING_WITH_LEN("; Using join buffer")); /* Skip initial "; "*/ @@ -18442,19 +18784,21 @@ static void select_describe(JOIN *join, bool need_tmp_table, bool need_order, item_list.push_back(new Item_string(str, len, cs)); } loop_end: + /* psergey2 if (i+1 == end_table && sjm_nests_cur != sjm_nests_end) { printing_materialize_nest= TRUE; i= sjm_nests[sjm_nests_cur++] - 1; end_table= (i+1) + join->best_positions[i+1].n_sj_tables; select_id= join->join_tab[i+1].emb_sj_nest->sj_subq_pred->get_identifier(); - } + }*/ // For next iteration used_tables|=table->map; if (result->send_data(item_list)) join->error= 1; } + } } for (SELECT_LEX_UNIT *unit= join->select_lex->first_inner_unit(); unit; diff --git a/sql/sql_select.h b/sql/sql_select.h index 36ab753a6ae..2299d4dfbdf 100644 --- a/sql/sql_select.h +++ b/sql/sql_select.h @@ -142,13 +142,25 @@ enum enum_nested_loop_state typedef enum_nested_loop_state (*Next_select_func)(JOIN *, struct st_join_table *, bool); + +/* + Function prototype for reading first record for a join tab + + RETURN + 0 - OK + -1 - Record not found + Other - Error +*/ typedef int (*Read_record_func)(struct st_join_table *tab); + Next_select_func setup_end_select_func(JOIN *join); int rr_sequential(READ_RECORD *info); +int rr_sequential_and_unpack(READ_RECORD *info); class JOIN_CACHE; class SJ_TMP_TABLE; +class JOIN_TAB_RANGE; typedef struct st_join_table { st_join_table() {} /* Remove gcc warning */ @@ -173,6 +185,14 @@ typedef struct st_join_table { st_join_table *last_inner; /**< last table table for embedding outer join */ st_join_table *first_upper; /**< first inner table for embedding outer join */ st_join_table *first_unmatched; /**< used for optimization purposes only */ + + /* + psergey2: for join tabs that are inside a bush: root of this bush. + */ + st_join_table *bush_root_tab; + bool last_leaf_in_bush; + + JOIN_TAB_RANGE *bush_children; /* Special content for EXPLAIN 'Extra' column or NULL if none */ const char *info; @@ -211,6 +231,8 @@ typedef struct st_join_table { E(#records) is in found_records. */ double read_time; + + ha_rows records_read; /* Startup cost for execution */ double startup_cost; @@ -292,7 +314,7 @@ typedef struct st_join_table { /* Semi-join strategy to be used for this join table. This is a copy of POSITION::sj_strategy field. This field is set up by the - fix_semijion_strategies_for_picked_join_order. + fix_semijoin_strategies_for_picked_join_order. */ uint sj_strategy; @@ -1365,17 +1387,29 @@ inline bool sj_is_materialize_strategy(uint strategy) } +class JOIN_TAB_RANGE: public Sql_alloc +{ +public: + JOIN_TAB *start; + JOIN_TAB *end; +}; + + class JOIN :public Sql_alloc { JOIN(const JOIN &rhs); /**< not implemented */ JOIN& operator=(const JOIN &rhs); /**< not implemented */ public: - JOIN_TAB *join_tab,**best_ref; + JOIN_TAB *join_tab, **best_ref; JOIN_TAB **map2table; ///< mapping between table indexes and JOIN_TABs JOIN_TAB *join_tab_save; ///< saved join_tab for subquery reexecution + + List<JOIN_TAB_RANGE> join_tab_ranges; + /* Base tables participating in the join. After join optimization is done, the - tables are stored in the join order. + tables are stored in the join order (but the only really important part is + that const tables are first). */ TABLE **table; /** @@ -1387,6 +1421,13 @@ public: uint tables; /**< Number of tables in the join */ uint outer_tables; /**< Number of tables that are not inside semijoin */ uint const_tables; + /* + Number of tables in the top join_tab array. Normally this matches + (join_tab_ranges.head()->end - join_tab_ranges.head()->start). + + We keep it here so that it is saved/restored with JOIN::restore_tmp. + */ + uint top_jtrange_tables; uint send_group_parts; bool group; /**< If query contains GROUP BY clause */ /** @@ -1595,6 +1636,7 @@ public: join_tab= join_tab_save= 0; table= 0; tables= 0; + top_jtrange_tables= 0; const_tables= 0; eliminated_tables= 0; join_list= 0; @@ -1933,6 +1975,7 @@ COND *remove_eq_conds(THD *thd, COND *cond, Item::cond_result *cond_value); int test_if_item_cache_changed(List<Cached_item> &list); void calc_used_field_length(THD *thd, JOIN_TAB *join_tab); int join_init_read_record(JOIN_TAB *tab); +int join_read_record_no_init(JOIN_TAB *tab); void set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key); inline Item * and_items(Item* cond, Item *item) { diff --git a/sql/sql_test.cc b/sql/sql_test.cc index 79fc0d5cc36..8fbfaf9dc76 100644 --- a/sql/sql_test.cc +++ b/sql/sql_test.cc @@ -165,58 +165,66 @@ void TEST_filesort(SORT_FIELD *sortorder,uint s_length) void TEST_join(JOIN *join) { - uint i,ref; + uint ref; + int i; + List_iterator<JOIN_TAB_RANGE> it(join->join_tab_ranges); + JOIN_TAB_RANGE *jt_range; DBUG_ENTER("TEST_join"); - /* - Assemble results of all the calls to full_name() first, - in order not to garble the tabular output below. - */ - String ref_key_parts[MAX_TABLES]; - for (i= 0; i < join->tables; i++) - { - JOIN_TAB *tab= join->join_tab + i; - for (ref= 0; ref < tab->ref.key_parts; ref++) - { - ref_key_parts[i].append(tab->ref.items[ref]->full_name()); - ref_key_parts[i].append(" "); - } - } - DBUG_LOCK_FILE; VOID(fputs("\nInfo about JOIN\n",DBUG_FILE)); - for (i=0 ; i < join->tables ; i++) + + while ((jt_range= it++)) { - JOIN_TAB *tab=join->join_tab+i; - TABLE *form=tab->table; - char key_map_buff[128]; - fprintf(DBUG_FILE,"%-16.16s type: %-7s q_keys: %s refs: %d key: %d len: %d\n", - form->alias, - join_type_str[tab->type], - tab->keys.print(key_map_buff), - tab->ref.key_parts, - tab->ref.key, - tab->ref.key_length); - if (tab->select) + /* + Assemble results of all the calls to full_name() first, + in order not to garble the tabular output below. + */ + String ref_key_parts[MAX_TABLES]; + for (i= 0; i < (jt_range->end - jt_range->start); i++) { - char buf[MAX_KEY/8+1]; - if (tab->use_quick == 2) - fprintf(DBUG_FILE, - " quick select checked for each record (keys: %s)\n", - tab->select->quick_keys.print(buf)); - else if (tab->select->quick) + JOIN_TAB *tab= jt_range->start + i; + for (ref= 0; ref < tab->ref.key_parts; ref++) { - fprintf(DBUG_FILE, " quick select used:\n"); - tab->select->quick->dbug_dump(18, FALSE); + ref_key_parts[i].append(tab->ref.items[ref]->full_name()); + ref_key_parts[i].append(" "); } - else - VOID(fputs(" select used\n",DBUG_FILE)); } - if (tab->ref.key_parts) + + for (i= 0; i < (jt_range->end - jt_range->start); i++) { - fprintf(DBUG_FILE, - " refs: %s\n", ref_key_parts[i].ptr()); + JOIN_TAB *tab= jt_range->start + i; + TABLE *form=tab->table; + char key_map_buff[128]; + fprintf(DBUG_FILE,"%-16.16s type: %-7s q_keys: %s refs: %d key: %d len: %d\n", + form->alias, + join_type_str[tab->type], + tab->keys.print(key_map_buff), + tab->ref.key_parts, + tab->ref.key, + tab->ref.key_length); + if (tab->select) + { + char buf[MAX_KEY/8+1]; + if (tab->use_quick == 2) + fprintf(DBUG_FILE, + " quick select checked for each record (keys: %s)\n", + tab->select->quick_keys.print(buf)); + else if (tab->select->quick) + { + fprintf(DBUG_FILE, " quick select used:\n"); + tab->select->quick->dbug_dump(18, FALSE); + } + else + VOID(fputs(" select used\n",DBUG_FILE)); + } + if (tab->ref.key_parts) + { + fprintf(DBUG_FILE, + " refs: %s\n", ref_key_parts[i].ptr()); + } } + VOID(fputs("\n",DBUG_FILE)); } DBUG_UNLOCK_FILE; DBUG_VOID_RETURN; diff --git a/sql/sql_union.cc b/sql/sql_union.cc index 1080b45d60d..bb97c1f6352 100644 --- a/sql/sql_union.cc +++ b/sql/sql_union.cc @@ -703,6 +703,7 @@ bool st_select_lex_unit::cleanup() { join->tables_list= 0; join->tables= 0; + join->top_jtrange_tables= 0; } error|= fake_select_lex->cleanup(); /* |