#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<TABLE_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<TABLE_LIST> *join_list);
static uint build_bitmap_for_nested_joins(List<TABLE_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<TABLE_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<TABLE_LIST> 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(List<TABLE
When "writing" we store/update this auxilary info about the current
position:
- 1. join->cur_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
TRUE Requested join order extension not allowed.
*/
-static bool check_interleaving_with_nj(JOIN_TAB *next_tab)
+bool Optimize_table_order::check_interleaving_with_nj(JOIN_TAB *next_tab)
{
TABLE_LIST *next_emb= next_tab->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
Attachment: [text/bzr-bundle] bzr/roy.lyseng@oracle.com-20110406115655-i0e8qdd8zx9l7gni.bundle
