Drizzled Public API Documentation

Query Optimizer

Namespaces

namespace  drizzled
 

TODO: Rename this file - func.h is stupid.


Functions

static bool drizzled::make_group_fields (Join *main_join, Join *curr_join)
static void drizzled::calc_group_buffer (Join *join, Order *group)
static bool drizzled::alloc_group_fields (Join *join, Order *group)
static uint32_t drizzled::cache_record_length (Join *join, uint32_t index)
static double drizzled::prev_record_reads (Join *join, uint32_t idx, table_map found_ref)
static bool drizzled::get_best_combination (Join *join)
static void drizzled::set_position (Join *join, uint32_t index, JoinTable *table, optimizer::KeyUse *key)
static bool drizzled::choose_plan (Join *join, table_map join_tables)
static void drizzled::best_access_path (Join *join, JoinTable *s, Session *session, table_map remaining_tables, uint32_t idx, double record_count, double read_time)
static void drizzled::optimize_straight_join (Join *join, table_map join_tables)
static bool drizzled::greedy_search (Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level)
static bool drizzled::best_extension_by_limited_search (Join *join, table_map remaining_tables, uint32_t idx, double record_count, double read_time, uint32_t depth, uint32_t prune_level)
static uint32_t drizzled::determine_search_depth (Join *join)
static bool drizzled::make_simple_join (Join *join, Table *tmp_table)
static void drizzled::make_outerjoin_info (Join *join)
static bool drizzled::make_join_select (Join *join, optimizer::SqlSelect *select, COND *item)
static bool drizzled::make_join_readinfo (Join *join)
static void drizzled::update_depend_map (Join *join)
static void drizzled::update_depend_map (Join *join, Order *order)
static Order * drizzled::remove_constants (Join *join, Order *first_order, COND *cond, bool change_list, bool *simple_order)
static int drizzled::return_zero_rows (Join *join, select_result *res, TableList *tables, List< Item > &fields, bool send_row, uint64_t select_options, const char *info, Item *having)
static COND * drizzled::simplify_joins (Join *join, List< TableList > *join_list, COND *conds, bool top)
static int drizzled::remove_duplicates (Join *join, Table *entry, List< Item > &fields, Item *having)
static int drizzled::setup_without_group (Session *session, Item **ref_pointer_array, TableList *tables, TableList *, List< Item > &fields, List< Item > &all_fields, COND **conds, Order *order, Order *group, bool *hidden_group_fields)
static bool drizzled::make_join_statistics (Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse)
static uint32_t drizzled::build_bitmap_for_nested_joins (List< TableList > *join_list, uint32_t first_unused)
static Table * drizzled::get_sort_by_table (Order *a, Order *b, TableList *tables)
static void drizzled::reset_nj_counters (List< TableList > *join_list)
static bool drizzled::test_if_subpart (Order *a, Order *b)
static void drizzled::restore_prev_nj_state (JoinTable *last)
static bool drizzled::add_ref_to_table_cond (Session *session, JoinTable *join_tab)
static void drizzled::free_blobs (Field **ptr)
static void drizzled::clear_tables (Join *join)
enum_nested_loop_state drizzled::evaluate_join_record (Join *join, JoinTable *join_tab, int error)
 Process one record of the nested loop join.
enum_nested_loop_state drizzled::evaluate_null_complemented_join_record (Join *join, JoinTable *join_tab)
enum_nested_loop_state drizzled::flush_cached_records (Join *join, JoinTable *join_tab, bool skip_last)
enum_nested_loop_state drizzled::end_send (Join *join, JoinTable *, bool end_of_records)
enum_nested_loop_state drizzled::end_write (Join *join, JoinTable *, bool end_of_records)
enum_nested_loop_state drizzled::end_update (Join *join, JoinTable *, bool end_of_records)
enum_nested_loop_state drizzled::end_unique_update (Join *join, JoinTable *, bool end_of_records)
static uint32_t drizzled::used_blob_length (CacheField **ptr)
int drizzled::join_init_cache (Session *session, JoinTable *tables, uint32_t table_count)
static COND * drizzled::build_equal_items (Session *session, COND *cond, COND_EQUAL *inherited, List< TableList > *join_list, COND_EQUAL **cond_equal_ref)
static Item * drizzled::part_of_refkey (Table *form, Field *field)
static bool drizzled::cmp_buffer_with_ref (JoinTable *tab)
static void drizzled::change_cond_ref_to_const (Session *session, list< COND_CMP > &save_list, Item *and_father, Item *cond, Item *field, Item *value)
static bool drizzled::copy_blobs (Field **ptr)
static bool drizzled::eval_const_cond (COND *cond)
bool drizzled::handle_select (Session *session, LEX *lex, select_result *result, uint64_t setup_tables_done_option)
bool drizzled::fix_inner_refs (Session *session, List< Item > &all_fields, Select_Lex *select, Item **ref_pointer_array)
void drizzled::save_index_subquery_explain_info (JoinTable *join_tab, Item *where)
bool drizzled::select_query (Session *session, Item ***rref_pointer_array, TableList *tables, uint32_t wild_num, List< Item > &fields, COND *conds, uint32_t og_num, Order *order, Order *group, Item *having, uint64_t select_options, select_result *result, Select_Lex_Unit *unit, Select_Lex *select_lex)
Item * drizzled::and_items (Item *cond, Item *item)
ha_rows drizzled::get_quick_record_count (Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys, ha_rows limit)
uint32_t drizzled::max_part_bit (key_part_map bits)
static int drizzled::sort_keyuse (optimizer::KeyUse *a, optimizer::KeyUse *b)
bool drizzled::update_ref_and_keys (Session *session, DYNAMIC_ARRAY *keyuse, JoinTable *join_tab, uint32_t tables, COND *cond, COND_EQUAL *, table_map normal_tables, Select_Lex *select_lex, vector< optimizer::SargableParam > &sargables)
void drizzled::optimize_keyuse (Join *join, DYNAMIC_ARRAY *keyuse_array)
void drizzled::add_group_and_distinct_keys (Join *join, JoinTable *join_tab)
int drizzled::join_tab_cmp (const void *ptr1, const void *ptr2)
int drizzled::join_tab_cmp_straight (const void *ptr1, const void *ptr2)
void drizzled::calc_used_field_length (Session *, JoinTable *join_tab)
StoredKey * drizzled::get_store_key (Session *session, optimizer::KeyUse *keyuse, table_map used_tables, KeyPartInfo *key_part, unsigned char *key_buff, uint32_t maybe_null)
bool drizzled::store_val_in_field (Field *field, Item *item, enum_check_fields check_flag)
void drizzled::add_cond_and_fix (Item **e1, Item *e2)
bool drizzled::create_ref_for_key (Join *join, JoinTable *j, optimizer::KeyUse *org_keyuse, table_map used_tables)
bool drizzled::eq_ref_table (Join *join, Order *start_order, JoinTable *tab)
static Item_equal * drizzled::find_item_equal (COND_EQUAL *cond_equal, Field *field, bool *inherited_fl)
static bool drizzled::check_simple_equality (Item *left_item, Item *right_item, Item *item, COND_EQUAL *cond_equal)
static bool drizzled::check_row_equality (Session *session, Item *left_row, Item_row *right_row, COND_EQUAL *cond_equal, List< Item > *eq_list)
static bool drizzled::check_equality (Session *session, Item *item, COND_EQUAL *cond_equal, List< Item > *eq_list)
static COND * drizzled::build_equal_items_for_cond (Session *session, COND *cond, COND_EQUAL *inherited)
static int drizzled::compare_fields_by_table_order (Item_field *field1, Item_field *field2, void *table_join_idx)
static Item * drizzled::eliminate_item_equal (COND *cond, COND_EQUAL *upper_levels, Item_equal *item_equal)
COND * drizzled::substitute_for_best_equal_field (COND *cond, COND_EQUAL *cond_equal, void *table_join_idx)
void drizzled::update_const_equal_items (COND *cond, JoinTable *tab)
Item * drizzled::remove_additional_cond (Item *conds)
static void drizzled::propagate_cond_constants (Session *session, list< COND_CMP > &save_list, COND *and_father, COND *cond)
bool drizzled::check_interleaving_with_nj (JoinTable *next_tab)
COND * drizzled::optimize_cond (Join *join, COND *conds, List< TableList > *join_list, Item::cond_result *cond_value)
COND * drizzled::remove_eq_conds (Session *session, COND *cond, Item::cond_result *cond_value)
static bool drizzled::test_if_equality_guarantees_uniqueness (Item *l, Item *r)
bool drizzled::const_expression_in_where (COND *cond, Item *comp_item, Item **const_item)
Next_select_func drizzled::setup_end_select_func (Join *join)
int drizzled::do_select (Join *join, List< Item > *fields, Table *table)
enum_nested_loop_state drizzled::sub_select_cache (Join *join, JoinTable *join_tab, bool end_of_records)
enum_nested_loop_state drizzled::sub_select (Join *join, JoinTable *join_tab, bool end_of_records)
int drizzled::safe_index_read (JoinTable *tab)
int drizzled::join_read_const (JoinTable *tab)
int drizzled::join_read_key (JoinTable *tab)
int drizzled::join_read_always_key (JoinTable *tab)
int drizzled::join_read_last_key (JoinTable *tab)
int drizzled::join_no_more_records (ReadRecord *)
int drizzled::join_read_next_same_diff (ReadRecord *info)
int drizzled::join_read_next_same (ReadRecord *info)
int drizzled::join_read_prev_same (ReadRecord *info)
int drizzled::join_init_quick_read_record (JoinTable *tab)
int drizzled::init_read_record_seq (JoinTable *tab)
int drizzled::test_if_quick_select (JoinTable *tab)
int drizzled::join_init_read_record (JoinTable *tab)
int drizzled::join_read_first (JoinTable *tab)
int drizzled::join_read_next_different (ReadRecord *info)
int drizzled::join_read_next (ReadRecord *info)
int drizzled::join_read_last (JoinTable *tab)
int drizzled::join_read_prev (ReadRecord *info)
int drizzled::join_read_always_key_or_null (JoinTable *tab)
int drizzled::join_read_next_same_or_null (ReadRecord *info)
enum_nested_loop_state drizzled::end_send_group (Join *join, JoinTable *, bool end_of_records)
enum_nested_loop_state drizzled::end_write_group (Join *join, JoinTable *, bool end_of_records)
bool drizzled::test_if_ref (Item_field *left_item, Item *right_item)
COND * drizzled::make_cond_for_table (COND *cond, table_map tables, table_map used_table, bool exclude_expensive_cond)
static int drizzled::test_if_order_by_key (Order *order, Table *table, uint32_t idx, uint32_t *used_key_parts)
bool drizzled::is_subkey (KeyPartInfo *key_part, KeyPartInfo *ref_key_part, KeyPartInfo *ref_key_part_end)
static uint32_t drizzled::test_if_subkey (Order *order, Table *table, uint32_t ref, uint32_t ref_key_parts, const key_map *usable_keys)
bool drizzled::list_contains_unique_index (Table *table, bool(*find_func)(Field *, void *), void *data)
bool drizzled::find_field_in_order_list (Field *field, void *data)
bool drizzled::find_field_in_item_list (Field *field, void *data)
bool drizzled::test_if_skip_sort_order (JoinTable *tab, Order *order, ha_rows select_limit, bool no_changes, const key_map *map)
int drizzled::create_sort_index (Session *session, Join *join, Order *order, ha_rows filesort_limit, ha_rows select_limit, bool is_order_by)
int drizzled::remove_dup_with_compare (Session *session, Table *table, Field **first_field, uint32_t offset, Item *having)
int drizzled::remove_dup_with_hash_index (Session *session, Table *table, uint32_t field_count, Field **first_field, uint32_t key_length, Item *having)
SortField * drizzled::make_unireg_sortorder (Order *order, uint32_t *length, SortField *sortorder)
bool drizzled::cp_buffer_from_ref (Session *session, table_reference_st *ref)
static bool drizzled::find_order_in_list (Session *session, Item **ref_pointer_array, TableList *tables, Order *order, List< Item > &fields, List< Item > &all_fields, bool is_group_field)
int drizzled::setup_order (Session *session, Item **ref_pointer_array, TableList *tables, List< Item > &fields, List< Item > &all_fields, Order *order)
int drizzled::setup_group (Session *session, Item **ref_pointer_array, TableList *tables, List< Item > &fields, List< Item > &all_fields, Order *order, bool *hidden_group_fields)
Order * drizzled::create_distinct_group (Session *session, Item **ref_pointer_array, Order *order_list, List< Item > &fields, List< Item > &, bool *all_order_by_fields_used)
void drizzled::count_field_types (Select_Lex *select_lex, Tmp_Table_Param *param, List< Item > &fields, bool reset_with_sum_func)
int drizzled::test_if_item_cache_changed (List< Cached_item > &list)
bool drizzled::setup_copy_fields (Session *session, Tmp_Table_Param *param, Item **ref_pointer_array, List< Item > &res_selected_fields, List< Item > &res_all_fields, uint32_t elements, List< Item > &all_fields)
void drizzled::copy_fields (Tmp_Table_Param *param)
bool drizzled::change_to_use_tmp_fields (Session *session, Item **ref_pointer_array, List< Item > &res_selected_fields, List< Item > &res_all_fields, uint32_t elements, List< Item > &all_fields)
bool drizzled::change_refs_to_tmp_fields (Session *session, Item **ref_pointer_array, List< Item > &res_selected_fields, List< Item > &res_all_fields, uint32_t elements, List< Item > &all_fields)
bool drizzled::setup_sum_funcs (Session *session, Item_sum **func_ptr)
void drizzled::init_tmptable_sum_functions (Item_sum **func_ptr)
void drizzled::update_tmptable_sum_func (Item_sum **func_ptr, Table *)
void drizzled::copy_sum_funcs (Item_sum **func_ptr, Item_sum **end_ptr)
bool drizzled::init_sum_functions (Item_sum **func_ptr, Item_sum **end_ptr)
bool drizzled::update_sum_func (Item_sum **func_ptr)
bool drizzled::copy_funcs (Item **func_ptr, const Session *session)
void drizzled::free_underlaid_joins (Session *session, Select_Lex *select)
bool drizzled::change_group_ref (Session *session, Item_func *expr, Order *group_list, bool *changed)
static void drizzled::print_table_array (Session *session, String *str, TableList **table, TableList **end)
void drizzled::print_join (Session *session, String *str, List< TableList > *tables)
 drizzled::Join::Join (Session *session_arg, List< Item > &fields_arg, uint64_t select_options_arg, select_result *result_arg)
void drizzled::Join::reset (Session *session_arg, List< Item > &fields_arg, uint64_t select_options_arg, select_result *result_arg)
bool drizzled::Join::is_top_level_join () const
int drizzled::Join::prepare (Item ***rref_pointer_array, TableList *tables, uint32_t wind_num, COND *conds, uint32_t og_num, Order *order, Order *group, Item *having, Select_Lex *select, Select_Lex_Unit *unit)
void drizzled::Join::remove_subq_pushed_predicates (Item **where)
int drizzled::Join::optimize ()
void drizzled::Join::restore_tmp ()
int drizzled::Join::reinit ()
bool drizzled::Join::init_save_join_tab ()
 Save the original join layout.
bool drizzled::Join::save_join_tab ()
void drizzled::Join::exec ()
int drizzled::Join::destroy ()
bool drizzled::Join::setup_subquery_materialization ()
void drizzled::Join::join_free ()
void drizzled::Join::cleanup (bool full)
bool drizzled::Join::alloc_func_list ()
bool drizzled::Join::make_sum_func_list (List< Item > &all_fields, List< Item > &send_fields, bool before_group_by, bool recompute=false)
bool drizzled::Join::rollup_init ()
bool drizzled::Join::rollup_make_fields (List< Item > &all_fields, List< Item > &fields, Item_sum ***func)
int drizzled::Join::rollup_send_data (uint32_t idx)
int drizzled::Join::rollup_write_data (uint32_t idx, Table *table)
void drizzled::Join::clear ()
bool drizzled::Join::change_result (select_result *result)
void drizzled::Join::cache_const_exprs ()
bool drizzled::JoinCache::store_record_in_cache ()
void drizzled::JoinCache::reset_cache_read ()
void drizzled::JoinCache::reset_cache_write ()

Variables

const char * drizzled::subq_sj_cond_name = "0123456789ABCDEF0123456789abcdef0123456789ABCDEF0123456789abcdef-sj-cond"

Function Documentation

void drizzled::add_group_and_distinct_keys ( Join *  join,
JoinTable *  join_tab 
)

Discover the indexes that can be used for GROUP BY or DISTINCT queries.

If the query has a GROUP BY clause, find all indexes that contain all GROUP BY fields, and add those indexes to join->const_keys.

If the query has a DISTINCT clause, find all indexes that contain all SELECT fields, and add those indexes to join->const_keys. This allows later on such queries to be processed by a QUICK_GROUP_MIN_MAX_SELECT.

Parameters:
join
join_tab
Returns:
None

Definition at line 748 of file sql_select.cc.

References drizzled::JoinTable::const_keys, drizzled::Join::fields_list, drizzled::Join::group_list, and drizzled::Join::select_distinct.

Referenced by drizzled::make_join_statistics().

static bool drizzled::add_ref_to_table_cond ( Session *  session,
JoinTable *  join_tab 
) [static]
bool drizzled::Join::alloc_func_list ( ) [inherited]

Make an array of pointers to sum_functions to speed up sum_func calculation.

Return values:
0ok
1Error

Definition at line 2159 of file join.cc.

References drizzled::Join::fields_list, drizzled::Join::rollup, and drizzled::Join::select_distinct.

Referenced by drizzled::Join::exec(), and drizzled::Join::prepare().

static bool drizzled::alloc_group_fields ( Join *  join,
Order *  group 
) [static]

Get a list of buffers for saveing last group.

Groups are saved in reverse order for easyer check loop.

Definition at line 3274 of file join.cc.

References drizzled::new_Cached_item().

Referenced by drizzled::make_group_fields(), and drizzled::Join::optimize().

static void drizzled::best_access_path ( Join *  join,
JoinTable *  s,
Session *  session,
table_map  remaining_tables,
uint32_t  idx,
double  record_count,
double   
) [static]

Find the best access path for an extension of a partial execution plan and add this path to the plan.

The function finds the best access path to table 's' from the passed partial plan where an access path is the general term for any means to access the data in 's'. An access path may use either an index or a scan, whichever is cheaper. The input partial plan is passed via the array 'join->positions' of length 'idx'. The chosen access method for 's' and its cost are stored in 'join->positions[idx]'.

Parameters:
joinpointer to the structure providing all context info for the query
sthe table to be joined by the function
sessionthread for the connection that submitted the query
remaining_tablesset of tables not included into the partial plan yet
idxthe length of the partial plan
record_countestimate for the number of records returned by the partial plan
read_timethe cost of the partial plan
Returns:
None

Definition at line 3559 of file join.cc.

References drizzled::Table::cursor, drizzled::JoinTable::found_records, drizzled::optimizer::QuickSelectInterface::index, drizzled::Cursor::index_only_read_time(), drizzled::Table::key_info, drizzled::JoinTable::keyuse, drizzled::Table::map, MATCHING_ROWS_IN_OTHER_TABLE, drizzled::max_part_bit(), drizzled::Table::quick_condition_rows, drizzled::optimizer::QuickSelectInterface::read_time, drizzled::JoinTable::read_time, drizzled::JoinTable::records, drizzled::Join::setPosInPartialPlan(), drizzled::Join::sort_by_table, TIME_FOR_COMPARE, drizzled::Join::unit, and drizzled::Session::variables.

Referenced by drizzled::best_extension_by_limited_search(), and drizzled::optimize_straight_join().

static bool drizzled::best_extension_by_limited_search ( Join *  join,
table_map  remaining_tables,
uint32_t  idx,
double  record_count,
double  read_time,
uint32_t  search_depth,
uint32_t  prune_level 
) [static]

Find a good, possibly optimal, query execution plan (QEP) by a possibly exhaustive search.

The procedure searches for the optimal ordering of the query tables in set 'remaining_tables' of size N, and the corresponding optimal access paths to each table. The choice of a table order and an access path for each table constitutes a query execution plan (QEP) that fully specifies how to execute the query.

The maximal size of the found plan is controlled by the parameter 'search_depth'. When search_depth == N, the resulting plan is complete and can be used directly as a QEP. If search_depth < N, the found plan consists of only some of the query tables. Such "partial" optimal plans are useful only as input to query optimization procedures, and cannot be used directly to execute a query.

The algorithm begins with an empty partial plan stored in 'join->positions' and a set of N tables - 'remaining_tables'. Each step of the algorithm evaluates the cost of the partial plan extended by all access plans for each of the relations in 'remaining_tables', expands the current partial plan with the access plan that results in lowest cost of the expanded partial plan, and removes the corresponding relation from 'remaining_tables'. The algorithm continues until it either constructs a complete optimal plan, or constructs an optimal plartial plan with size = search_depth.

The final optimal plan is stored in 'join->best_positions'. The corresponding cost of the optimal plan is in 'join->best_read'.

Note:
The procedure uses a recursive depth-first search where the depth of the recursion (and thus the exhaustiveness of the search) is controlled by the parameter 'search_depth'.
The pseudocode below describes the algorithm of 'best_extension_by_limited_search'. The worst-case complexity of this algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then the complexity of greedy_search is O(N!).
    procedure best_extension_by_limited_search(
      pplan in,             // in, partial plan of tables-joined-so-far
      pplan_cost,           // in, cost of pplan
      remaining_tables,     // in, set of tables not referenced in pplan
      best_plan_so_far,     // in/out, best plan found so far
      best_plan_so_far_cost,// in/out, cost of best_plan_so_far
      search_depth)         // in, maximum size of the plans being considered
    {
      for each table T from remaining_tables
      {
        // Calculate the cost of using table T as above
        cost = complex-series-of-calculations;

        // Add the cost to the cost so far.
        pplan_cost+= cost;

        if (pplan_cost >= best_plan_so_far_cost)
          // pplan_cost already too great, stop search
          continue;

        pplan= expand pplan by best_access_method;
        remaining_tables= remaining_tables - table T;
        if (remaining_tables is not an empty set
            and
            search_depth > 1)
        {
          best_extension_by_limited_search(pplan, pplan_cost,
                                           remaining_tables,
                                           best_plan_so_far,
                                           best_plan_so_far_cost,
                                           search_depth - 1);
        }
        else
        {
          best_plan_so_far_cost= pplan_cost;
          best_plan_so_far= pplan;
        }
      }
    }
Note:
When 'best_extension_by_limited_search' is called for the first time, 'join->best_read' must be set to the largest possible value (e.g. DBL_MAX). The actual implementation provides a way to optionally use pruning heuristic (controlled by the parameter 'prune_level') to reduce the search space by skipping some partial plans.
The parameter 'search_depth' provides control over the recursion depth, and thus the size of the resulting optimal plan.
Parameters:
joinpointer to the structure providing all context info for the query
remaining_tablesset of tables not included into the partial plan yet
idxlength of the partial QEP in 'join->positions'; since a depth-first search is used, also corresponds to the current depth of the search tree; also an index in the array 'join->best_ref';
record_countestimate for the number of records returned by the best partial plan
read_timethe cost of the best partial plan
search_depthmaximum depth of the recursion and thus size of the found optimal plan (0 < search_depth <= join->tables+1).
prune_levelpruning heuristics that should be applied during optimization (values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
Return values:
falseok
trueFatal error

Definition at line 4387 of file join.cc.

References drizzled::best_access_path(), drizzled::Join::best_read, drizzled::check_interleaving_with_nj(), drizzled::Join::copyPartialPlanIntoOptimalPlan(), drizzled::Join::getPosFromPartialPlan(), drizzled::optimizer::Position::hasTableForSorting(), drizzled::optimizer::Position::isConstTable(), drizzled::Table::map, drizzled::restore_prev_nj_state(), drizzled::Join::sort_by_table, and TIME_FOR_COMPARE.

Referenced by drizzled::greedy_search().

static uint32_t drizzled::build_bitmap_for_nested_joins ( List< TableList > *  join_list,
uint32_t  first_unused 
) [static]

Assign each nested join structure a bit in the nested join bitset.

Assign each nested join structure (except "confluent" ones - those that embed only one element) a bit in the nested join bitset.

Parameters:
joinJoin being processed
join_listList of tables
first_unusedNumber of first unused bit in the nest joing bitset before the call
Note:
This function is called after simplify_joins(), when there are no redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so we will not run out of bits in the nested join bitset.
Returns:
First unused bit in the nest join bitset after the call.

Definition at line 6139 of file join.cc.

Referenced by drizzled::Join::optimize().

static COND * drizzled::build_equal_items ( Session *  session,
COND *  cond,
COND_EQUAL *  inherited,
List< TableList > *  join_list,
COND_EQUAL **  cond_equal_ref 
) [static]

Build multiple equalities for a condition and all on expressions that inherit these multiple equalities.

The function first applies the build_equal_items_for_cond function to build all multiple equalities for condition cond utilizing equalities referred through the parameter inherited. The extended set of equalities is returned in the structure referred by the cond_equal_ref parameter. After this the function calls itself recursively for all on expressions whose direct references can be found in join_list and who inherit directly the multiple equalities just having built.

Note:
The on expression used in an outer join operation inherits all equalities from the on expression of the embedding join, if there is any, or otherwise - from the where condition. This fact is not obvious, but presumably can be proved. Consider the following query:
      SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t2.a=t4.a
        WHERE t1.a=t2.a;
If the on expression in the query inherits =(t1.a,t2.a), then we can build the multiple equality =(t1.a,t2.a,t3.a,t4.a) that infers the equality t3.a=t4.a. Although the on expression t1.a=t3.a AND t2.a=t4.a AND t3.a=t4.a is not equivalent to the one in the query the latter can be replaced by the former: the new query will return the same result set as the original one.

Interesting that multiple equality =(t1.a,t2.a,t3.a,t4.a) allows us to use t1.a=t3.a AND t3.a=t4.a under the on condition:

      SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a
        WHERE t1.a=t2.a

This query equivalent to:

      SELECT * FROM (t1 LEFT JOIN (t3,t4) ON t1.a=t3.a AND t3.a=t4.a),t2
        WHERE t1.a=t2.a

Similarly the original query can be rewritten to the query:

      SELECT * FROM (t1,t2) LEFT JOIN (t3,t4) ON t2.a=t4.a AND t3.a=t4.a
        WHERE t1.a=t2.a

that is equivalent to:

      SELECT * FROM (t2 LEFT JOIN (t3,t4)ON t2.a=t4.a AND t3.a=t4.a), t1
        WHERE t1.a=t2.a

Thus, applying equalities from the where condition we basically can get more freedom in performing join operations. Althogh we don't use this property now, it probably makes sense to use it in the future.

Parameters:
sessionThread Cursor
condcondition to build the multiple equalities for
inheritedpath to all inherited multiple equality items
join_listlist of join tables to which the condition refers to
[out]cond_equal_refpointer to the structure to place built equalities in
Returns:
pointer to the transformed condition containing multiple equalities

Definition at line 1999 of file sql_select.cc.

References drizzled::build_equal_items_for_cond(), drizzled::TableList::cond_equal, and drizzled::TableList::on_expr.

static COND* drizzled::build_equal_items_for_cond ( Session *  session,
COND *  cond,
COND_EQUAL *  inherited 
) [static]

Replace all equality predicates in a condition by multiple equality items.

At each 'and' level the function detects items for equality predicates and replaced them by a set of multiple equality items of class Item_equal, taking into account inherited equalities from upper levels. If an equality predicate is used not in a conjunction it's just replaced by a multiple equality predicate. For each 'and' level the function set a pointer to the inherited multiple equalities in the cond_equal field of the associated object of the type Item_cond_and. The function also traverses the cond tree and and for each field reference sets a pointer to the multiple equality item containing the field, if there is any. If this multiple equality equates fields to a constant the function replaces the field reference by the constant in the cases when the field is not of a string type or when the field reference is just an argument of a comparison predicate. The function also determines the maximum number of members in equality lists of each Item_cond_and object assigning it to session->lex().current_select->max_equal_elems.

Note:
Multiple equality predicate =(f1,..fn) is equivalent to the conjuction of f1=f2, .., fn-1=fn. It substitutes any inference from these equality predicates that is equivalent to the conjunction. Thus, =(a1,a2,a3) can substitute for ((a1=a3) AND (a2=a3) AND (a2=a1)) as it is equivalent to ((a1=a2) AND (a2=a3)). The function always makes a substitution of all equality predicates occured in a conjuction for a minimal set of multiple equality predicates. This set can be considered as a canonical representation of the sub-conjunction of the equality predicates. E.g. (t1.a=t2.b AND t2.b>5 AND t1.a=t3.c) is replaced by (=(t1.a,t2.b,t3.c) AND t2.b>5), not by (=(t1.a,t2.b) AND =(t1.a,t3.c) AND t2.b>5); while (t1.a=t2.b AND t2.b>5 AND t3.c=t4.d) is replaced by (=(t1.a,t2.b) AND =(t3.c=t4.d) AND t2.b>5), but if additionally =(t4.d,t2.b) is inherited, it will be replaced by (=(t1.a,t2.b,t3.c,t4.d) AND t2.b>5)

The function performs the substitution in a recursive descent by the condtion tree, passing to the next AND level a chain of multiple equality predicates which have been built at the upper levels. The Item_equal items built at the level are attached to other non-equality conjucts as a sublist. The pointer to the inherited multiple equalities is saved in the and condition object (Item_cond_and). This chain allows us for any field reference occurence easyly to find a multiple equality that must be held for this occurence. For each AND level we do the following:

  • scan it for all equality predicate (=) items
  • join them into disjoint Item_equal() groups
  • process the included OR conditions recursively to do the same for lower AND levels.

We need to do things in this order as lower AND levels need to know about all possible Item_equal objects in upper levels.

Parameters:
sessionthread handle
condcondition(expression) where to make replacement
inheritedpath to all inherited multiple equality items
Returns:
pointer to the transformed condition

Definition at line 1792 of file sql_select.cc.

References drizzled::check_equality(), drizzled::Item_cond::compile(), and drizzled::Item::quick_fix_field().

Referenced by drizzled::build_equal_items().

void drizzled::Join::cache_const_exprs ( ) [inherited]
static void drizzled::calc_group_buffer ( Join *  join,
Order *  group 
) [static]

calc how big buffer we need for comparing group entries.

Definition at line 3189 of file join.cc.

References drizzled::Field::field_length, drizzled::Item::maybe_null, and drizzled::Field::pack_length().

Referenced by drizzled::Join::exec(), and drizzled::Join::optimize().

void drizzled::calc_used_field_length ( Session *  ,
JoinTable *  join_tab 
)

Find how much space the prevous read not const tables takes in cache.

Definition at line 847 of file sql_select.cc.

References drizzled::Table::cursor, drizzled::Field::pack_length(), drizzled::JoinTable::used_blobs, drizzled::JoinTable::used_fieldlength, and drizzled::JoinTable::used_fields.

bool drizzled::change_group_ref ( Session *  session,
Item_func *  expr,
Order *  group_list,
bool *  changed 
)

Replace occurences of group by fields in an expression by ref items.

The function replaces occurrences of group by fields in expr by ref objects for these fields unless they are under aggregate functions. The function also corrects value of the the maybe_null attribute for the items of all subexpressions containing group by fields.

EXAMPLES

      SELECT a+1 FROM t1 GROUP BY a WITH ROLLUP
      SELECT SUM(a)+a FROM t1 GROUP BY a WITH ROLLUP

IMPLEMENTATION

The function recursively traverses the tree of the expr expression, looks for occurrences of the group by fields that are not under aggregate functions and replaces them for the corresponding ref items.

Note:
This substitution is needed GROUP BY queries with ROLLUP if SELECT list contains expressions over group by attributes.
Parameters:
sessionreference to the context
exprexpression to make replacement
group_listlist of references to group by items
changedout: returns 1 if item contains a replaced field item
Todo:

Some functions are not null-preserving. For those functions updating of the maybe_null attribute is an overkill.

Return values:
0if ok
1on error

Definition at line 6202 of file sql_select.cc.

References drizzled::Item::eq(), drizzled::Item::maybe_null, and drizzled::Item::name.

Referenced by drizzled::Join::rollup_init().

bool drizzled::change_refs_to_tmp_fields ( Session *  session,
Item **  ref_pointer_array,
List< Item > &  res_selected_fields,
List< Item > &  res_all_fields,
uint32_t  elements,
List< Item > &  all_fields 
)

Change all sum_func refs to fields to point at fields in tmp table. Change all funcs to be fields in tmp table.

Parameters:
sessionSession pointer
ref_pointer_arrayarray of pointers to top elements of filed list
res_selected_fieldsnew list of items of select item list
res_all_fieldsnew list of all items
elementsnumber of elements in select item list
all_fieldsall fields list
Return values:
0ok
1error

Definition at line 6024 of file sql_select.cc.

References drizzled::Session::is_fatal_error.

Referenced by drizzled::Join::exec().

bool drizzled::Join::change_result ( select_result res) [inherited]

change select_result object of Join.

Parameters:
resnew select_result object
Return values:
falseOK
trueerror

Definition at line 2599 of file join.cc.

References drizzled::Join::fields_list, and drizzled::Join::select_lex.

Referenced by drizzled::select_query().

bool drizzled::change_to_use_tmp_fields ( Session *  session,
Item **  ref_pointer_array,
List< Item > &  res_selected_fields,
List< Item > &  res_all_fields,
uint32_t  elements,
List< Item > &  all_fields 
)

Change all funcs and sum_funcs to fields in tmp table, and create new list of all items.

Parameters:
sessionSession pointer
ref_pointer_arrayarray of pointers to top elements of filed list
res_selected_fieldsnew list of items of select item list
res_all_fieldsnew list of all items
elementsnumber of elements in select item list
all_fieldsall fields list
Return values:
0ok
!=0error

Definition at line 5945 of file sql_select.cc.

References drizzled::Field::orig_table.

Referenced by drizzled::Join::exec().

static bool drizzled::check_equality ( Session *  session,
Item *  item,
COND_EQUAL *  cond_equal,
List< Item > *  eq_list 
) [static]

Eliminate row equalities and form multiple equalities predicates.

This function checks whether the item is a simple equality i.e. the one that equates a field with another field or a constant (field=field_item or field=constant_item), or, a row equality. For a simple equality the function looks for a multiple equality in the lists referenced directly or indirectly by cond_equal inferring the given simple equality. If it doesn't find any, it builds/expands multiple equality that covers the predicate. Row equalities are eliminated substituted for conjunctive regular equalities which are treated in the same way as original equality predicates.

Parameters:
sessionthread handle
itempredicate to process
cond_equalmultiple equalities that must hold together with the predicate
eq_listresults of conversions of row equalities that are not simple enough to form multiple equalities
Return values:
trueif re-writing rules have been applied
falseotherwise, i.e. if the predicate is not an equality, or, if the equality is neither a simple one nor a row equality, or, if the procedure fails by a fatal error.

Definition at line 1706 of file sql_select.cc.

References drizzled::check_row_equality(), and drizzled::check_simple_equality().

Referenced by drizzled::build_equal_items_for_cond().

bool drizzled::check_interleaving_with_nj ( JoinTable *  next_tab)

Check interleaving with an inner tables of an outer join for extension table.

Check if table next_tab can be added to current partial join order, and if yes, record that it has been added.

The function assumes that both current partial join order and its extension with next_tab are valid wrt table dependencies.

     IMPLEMENTATION
       LIMITATIONS ON JOIN order_st
         The nested [outer] joins executioner algorithm imposes these limitations
         on join order:
         1. "Outer tables first" -  any "outer" table must be before any
             corresponding "inner" table.
         2. "No interleaving" - tables inside a nested join must form a continuous
            sequence in join order (i.e. the sequence must not be interrupted by
            tables that are outside of this nested join).

         #1 is checked elsewhere, this function checks #2 provided that #1 has
         been already checked.

       WHY NEED NON-INTERLEAVING
         Consider an example:

           select * from t0 join t1 left join (t2 join t3) on cond1

         The join order "t1 t2 t0 t3" is invalid:

         table t0 is outside of the nested join, so WHERE condition for t0 is
         attached directly to t0 (without triggers, and it may be used to access
         t0). Applying WHERE(t0) to (t2,t0,t3) record is invalid as we may miss
         combinations of (t1, t2, t3) that satisfy condition cond1, and produce a
         null-complemented (t1, t2.NULLs, t3.NULLs) row, which should not have
         been produced.

         If table t0 is not between t2 and t3, the problem doesn't exist:
          If t0 is located after (t2,t3), WHERE(t0) is applied after nested join
           processing has finished.
          If t0 is located before (t2,t3), predicates like WHERE_cond(t0, t2) are
           wrapped into condition triggers, which takes care of correct nested
           join processing.

       HOW IT IS IMPLEMENTED
         The limitations on join order can be rephrased as follows: for valid
         join order one must be able to:
           1. write down the used tables in the join order on one line.
           2. for each nested join, put one '(' and one ')' on the said line
           3. write "LEFT JOIN" and "ON (...)" where appropriate
           4. get a query equivalent to the query we're trying to execute.

         Calls to check_interleaving_with_nj() are equivalent to writing the
         above described line from left to right.
         A single check_interleaving_with_nj(A,B) call is equivalent to writing
         table B and appropriate brackets on condition that table A and
         appropriate brackets is the last what was written. Graphically the
         transition is as follows:

                              +---- current position
                              |
             ... last_tab ))) | ( next_tab )  )..) | ...
                                X          Y   Z   |
                                                   +- need to move to this
                                                      position.

         Notes about the position:
           The caller guarantees that there is no more then one X-bracket by
           checking "!(remaining_tables & s->dependent)" before calling this
           function. X-bracket may have a pair in Y-bracket.

         When "writing" we store/update this auxilary info about the current
         position:
          1. join->cur_embedding_map - bitmap of pairs of brackets (aka nested
             joins) we've opened but didn't close.
          2. {each NestedJoin class not simplified away}->counter - number
             of this nested join's children that have already been added to to
             the partial join order.
  
Parameters:
joinJoin being processed
next_tabTable we're going to extend the current partial join with
Return values:
falseJoin order extended, nested joins info about current join order (see NOTE section) updated.
trueRequested join order extension not allowed.

Definition at line 2623 of file sql_select.cc.

References drizzled::Join::cur_embedding_map, and drizzled::JoinTable::embedding_map.

Referenced by drizzled::best_extension_by_limited_search(), and drizzled::greedy_search().

static bool drizzled::check_row_equality ( Session *  session,
Item *  left_row,
Item_row *  right_row,
COND_EQUAL *  cond_equal,
List< Item > *  eq_list 
) [static]

Convert row equalities into a conjunction of regular equalities.

The function converts a row equality of the form (E1,...,En)=(E'1,...,E'n) into a list of equalities E1=E'1,...,En=E'n. For each of these equalities Ei=E'i the function checks whether it is a simple equality or a row equality. If it is a simple equality it is used to expand multiple equalities of cond_equal. If it is a row equality it converted to a sequence of equalities between row elements. If Ei=E'i is neither a simple equality nor a row equality the item for this predicate is added to eq_list.

Parameters:
sessionthread handle
left_rowleft term of the row equality to be processed
right_rowright term of the row equality to be processed
cond_equalmultiple equalities that must hold together with the predicate
eq_listresults of conversions of row equalities that are not simple enough to form multiple equalities
Return values:
trueif conversion has succeeded (no fatal error)
falseotherwise

Definition at line 1636 of file sql_select.cc.

References drizzled::check_simple_equality(), and drizzled::Item::quick_fix_field().

Referenced by drizzled::check_equality().

static bool drizzled::check_simple_equality ( Item *  left_item,
Item *  right_item,
Item *  item,
COND_EQUAL *  cond_equal 
) [static]

Check whether an equality can be used to build multiple equalities.

This function first checks whether the equality (left_item=right_item) is a simple equality i.e. the one that equates a field with another field or a constant (field=field_item or field=const_item). If this is the case the function looks for a multiple equality in the lists referenced directly or indirectly by cond_equal inferring the given simple equality. If it doesn't find any, it builds a multiple equality that covers the predicate, i.e. the predicate can be inferred from this multiple equality. The built multiple equality could be obtained in such a way: create a binary multiple equality equivalent to the predicate, then merge it, if possible, with one of old multiple equalities. This guarantees that the set of multiple equalities covering equality predicates will be minimal.

EXAMPLE: For the where condition

      WHERE a=b AND b=c AND
            (b=2 OR f=e)

the check_equality will be called for the following equality predicates a=b, b=c, b=2 and f=e.

  • For a=b it will be called with *cond_equal=(0,[]) and will transform cond_equal into (0,[Item_equal(a,b)]).
  • For b=c it will be called with *cond_equal=(0,[Item_equal(a,b)]) and will transform *cond_equal into CE=(0,[Item_equal(a,b,c)]).
  • For b=2 it will be called with *cond_equal=(ptr(CE),[]) and will transform *cond_equal into (ptr(CE),[Item_equal(2,a,b,c)]).
  • For f=e it will be called with *cond_equal=(ptr(CE), []) and will transform *cond_equal into (ptr(CE),[Item_equal(f,e)]).
Note:
Now only fields that have the same type definitions (verified by the Field::eq_def method) are placed to the same multiple equalities. Because of this some equality predicates are not eliminated and can be used in the constant propagation procedure. We could weeken the equlity test as soon as at least one of the equal fields is to be equal to a constant. It would require a more complicated implementation: we would have to store, in general case, its own constant for each fields from the multiple equality. But at the same time it would allow us to get rid of constant propagation completely: it would be done by the call to build_equal_items_for_cond.

The implementation does not follow exactly the above rules to build a new multiple equality for the equality predicate. If it processes the equality of the form field1=field2, it looks for multiple equalities me1 containig field1 and me2 containing field2. If only one of them is found the fuction expands it with the lacking field. If multiple equalities for both fields are found they are merged. If both searches fail a new multiple equality containing just field1 and field2 is added to the existing multiple equalities. If the function processes the predicate of the form field1=const, it looks for a multiple equality containing field1. If found, the function checks the constant of the multiple equality. If the value is unknown, it is setup to const. Otherwise the value is compared with const and the evaluation of the equality predicate is performed. When expanding/merging equality predicates from the upper levels the function first copies them for the current level. It looks acceptable, as this happens rarely. The implementation without copying would be much more complicated.

Parameters:
left_itemleft term of the quality to be checked
right_itemright term of the equality to be checked
itemequality item if the equality originates from a condition predicate, 0 if the equality is the result of row elimination
cond_equalmultiple equalities that must hold together with the equality
Return values:
trueif the predicate is a simple equality predicate to be used for building multiple equalities
falseotherwise

Definition at line 1447 of file sql_select.cc.

References drizzled::Item::const_item(), drizzled::Field::eq_def(), drizzled::find_item_equal(), drizzled::Item_equal::merge(), drizzled::Item::name, and drizzled::Item::quick_fix_field().

Referenced by drizzled::check_equality(), and drizzled::check_row_equality().

static bool drizzled::choose_plan ( Join *  join,
table_map  join_tables 
) [static]

Selects and invokes a search strategy for an optimal query plan.

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

Parameters:
joinpointer to the structure providing all context info for the query
join_tablesset of the tables in the query
Return values:
falseok
trueFatal error

Definition at line 3492 of file join.cc.

References drizzled::Join::best_read, drizzled::Join::cur_embedding_map, drizzled::determine_search_depth(), drizzled::greedy_search(), drizzled::Join::join_list, drizzled::join_tab_cmp(), drizzled::join_tab_cmp_straight(), drizzled::optimize_straight_join(), drizzled::reset_nj_counters(), drizzled::Session::status_var, drizzled::Join::tables, and drizzled::Session::variables.

Referenced by drizzled::make_join_statistics().

void drizzled::Join::cleanup ( bool  full) [inherited]

Cleanup this Join, possibly for reuse

Free resources of given join.

Parameters:
filltrue if we should free all resources, call with full==1 should be last, before it this function can be called with full==0
Note:
With subquery this function definitely will be called several times, but even for simple query it can be called several times.

Definition at line 2067 of file join.cc.

References drizzled::Table::cursor, drizzled::Join::tables, and drizzled::Join::tmp_join.

Referenced by drizzled::Join::destroy(), and drizzled::Join::join_free().

void drizzled::Join::clear ( ) [inherited]

clear results if there are not rows found for group (end_send_group/end_write_group)

Definition at line 2576 of file join.cc.

References drizzled::copy_fields().

static int drizzled::compare_fields_by_table_order ( Item_field *  field1,
Item_field *  field2,
void *  table_join_idx 
) [static]

Compare field items by table order in the execution plan.

field1 considered as better than field2 if the table containing field1 is accessed earlier than the table containing field2. The function finds out what of two fields is better according this criteria.

Parameters:
field1first field item to compare
field2second field item to compare
table_join_idxindex to tables determining table order
Return values:
1if field1 is better than field2
-1if field2 is better than field1
0otherwise

Definition at line 2071 of file sql_select.cc.

References drizzled::Item_field::used_tables().

Referenced by drizzled::substitute_for_best_equal_field().

bool drizzled::const_expression_in_where ( COND *  cond,
Item *  comp_item,
Item **  const_item 
)

Return true if the item is a const value in all the WHERE clause.

Definition at line 2912 of file sql_select.cc.

References drizzled::Item::eq().

Referenced by drizzled::remove_constants().

void drizzled::copy_fields ( Tmp_Table_Param *  param)

Make a copy of all simple SELECT'ed items.

This is done at the start of a new group so that we can retrieve these later when the group changes.

Definition at line 5915 of file sql_select.cc.

Referenced by drizzled::Join::clear(), drizzled::end_unique_update(), drizzled::end_update(), and drizzled::optimizer::QuickGroupMinMaxSelect::get_next().

bool drizzled::copy_funcs ( Item **  func_ptr,
const Session *  session 
)

Copy result of functions to record in tmp_table.

Definition at line 6127 of file sql_select.cc.

References drizzled::Session::is_error().

Referenced by drizzled::end_unique_update(), and drizzled::end_update().

void drizzled::copy_sum_funcs ( Item_sum **  func_ptr,
Item_sum **  end_ptr 
)

Copy result of sum functions to record in tmp_table.

Definition at line 6094 of file sql_select.cc.

Referenced by drizzled::Join::rollup_write_data().

void drizzled::count_field_types ( Select_Lex *  select_lex,
Tmp_Table_Param *  param,
List< Item > &  fields,
bool  reset_with_sum_func 
)

Update join with count of the different type of fields.

Definition at line 5679 of file sql_select.cc.

Referenced by drizzled::Join::exec(), drizzled::Join::optimize(), and drizzled::Join::prepare().

Order * drizzled::create_distinct_group ( Session *  session,
Item **  ref_pointer_array,
Order *  order_list,
List< Item > &  fields,
List< Item > &  ,
bool *  all_order_by_fields_used 
)

Create a group by that consist of all non const fields.

Try to use the fields in the order given by 'order' to allow one to optimize away 'order by'.

Definition at line 5610 of file sql_select.cc.

Referenced by drizzled::Join::optimize().

int drizzled::Join::destroy ( ) [inherited]
static uint32_t drizzled::determine_search_depth ( Join *  join) [static]

Heuristic procedure to automatically guess a reasonable degree of exhaustiveness for the greedy search procedure.

The procedure estimates the optimization time and selects a search depth big enough to result in a near-optimal QEP, that doesn't take too long to find. If the number of tables in the query exceeds some constant, then search_depth is set to this constant.

Parameters:
joinpointer to the structure providing all context info for the query
Note:
This is an extremely simplistic implementation that serves as a stub for a more advanced analysis of the join. Ideally the search depth should be determined by learning from previous query optimizations, because it will depend on the CPU power (and other factors).
Todo:
this value should be determined dynamically, based on statistics: uint32_t max_tables_for_exhaustive_opt= 7;
Todo:
this value could be determined by some mapping of the form: depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
Returns:
A positive integer that specifies the search depth (and thus the exhaustiveness) of the depth-first search algorithm used by 'greedy_search'.

Definition at line 4534 of file join.cc.

References drizzled::Join::tables.

Referenced by drizzled::choose_plan().

int drizzled::do_select ( Join *  join,
List< Item > *  fields,
Table *  table 
)

Make a join of all tables and write it on socket or to table.

Return values:
0if ok
1if error is sent
-1if error should be sent

Definition at line 3041 of file sql_select.cc.

References drizzled::Table::cursor, drizzled::Session::is_error(), drizzled::Join::join_free(), drizzled::setup_end_select_func(), drizzled::sub_select(), and drizzled::Join::tables.

Referenced by drizzled::Join::exec().

static Item* drizzled::eliminate_item_equal ( COND *  cond,
COND_EQUAL *  upper_levels,
Item_equal *  item_equal 
) [static]

Generate minimal set of simple equalities equivalent to a multiple equality.

The function retrieves the fields of the multiple equality item item_equal and for each field f:

  • if item_equal contains const it generates the equality f=const_item;
  • otherwise, if f is not the first field, generates the equality f=item_equal->get_first(). All generated equality are added to the cond conjunction.
Parameters:
condcondition to add the generated equality to
upper_levelsstructure to access multiple equality of upper levels
item_equalmultiple equality to generate simple equality from
Note:
Before generating an equality function checks that it has not been generated for multiple equalities of the upper levels. E.g. for the following where condition WHERE a=5 AND ((a=b AND b=c) OR c>4) the upper level AND condition will contain =(5,a), while the lower level AND condition will contain =(5,a,b,c). When splitting =(5,a,b,c) into a separate equality predicates we should omit 5=a, as we have it already in the upper level. The following where condition gives us a more complicated case: WHERE t1.a=t2.b AND t3.c=t4.d AND (t2.b=t3.c OR t4.e>5 ...) AND ... Given the tables are accessed in the order t1->t2->t3->t4 for the selected query execution plan the lower level multiple equality =(t1.a,t2.b,t3.c,t4.d) formally should be converted to t1.a=t2.b AND t1.a=t3.c AND t1.a=t4.d. But t1.a=t2.a will be generated for the upper level. Also t3.c=t4.d will be generated there. So only t1.a=t3.c should be left in the lower level. If cond is equal to 0, then not more then one equality is generated and a pointer to it is returned as the result of the function.
Returns:
  • The condition with generated simple equalities or a pointer to the simple generated equality, if success.
  • 0, otherwise.

Definition at line 2133 of file sql_select.cc.

References drizzled::Item_field::find_item_equal(), drizzled::Item::quick_fix_field(), and drizzled::Item::val_int().

Referenced by drizzled::substitute_for_best_equal_field().

enum_nested_loop_state drizzled::end_unique_update ( Join *  join,
JoinTable *  ,
bool  end_of_records 
)

Like end_update, but this is done with unique constraints instead of keys.

Definition at line 3114 of file join.cc.

References drizzled::copy_fields(), drizzled::copy_funcs(), drizzled::Table::cursor, drizzled::Table::get_dup_key(), and drizzled::update_tmptable_sum_func().

Referenced by drizzled::setup_end_select_func().

enum_nested_loop_state drizzled::end_update ( Join *  join,
JoinTable *  ,
bool  end_of_records 
)
bool drizzled::eq_ref_table ( Join *  join,
Order *  start_order,
JoinTable *  tab 
)

Add to join_tab->select_cond[i] "table.field IS NOT NULL" conditions we've inferred from ref/eq_ref access performed.

This function is a part of "Early NULL-values filtering for ref access" optimization.

Example of this optimization: For query SELECT * FROM t1,t2 WHERE t2.key=t1.field
and plan " any-access(t1), ref(t2.key=t1.field) "
add "t1.field IS NOT NULL" to t1's table condition.

Description of the optimization:

We look through equalities choosen to perform ref/eq_ref access, pick equalities that have form "tbl.part_of_key = othertbl.field" (where othertbl is a non-const table and othertbl.field may be NULL) and add them to conditions on correspoding tables (othertbl in this example).

Exception from that is the case when referred_tab->join != join. I.e. don't add NOT NULL constraints from any embedded subquery. Consider this query:

      SELECT A.f2 FROM t1 LEFT JOIN t2 A ON A.f2 = f1
      WHERE A.f3=(SELECT MIN(f3) FROM  t2 C WHERE A.f4 = C.f4) OR A.f3 IS NULL;
      @endocde
      Here condition A.f3 IS NOT NULL is going to be added to the WHERE
      condition of the embedding query.
      Another example:
      SELECT * FROM t10, t11 WHERE (t10.a < 10 OR t10.a IS NULL)
      AND t11.b <=> t10.b AND (t11.a = (SELECT MAX(a) FROM t12
      WHERE t12.b = t10.a ));
      Here condition t10.a IS NOT NULL is going to be added.
      In both cases addition of NOT NULL condition will erroneously reject
      some rows of the result set.
      referred_tab->join != join constraint would disallow such additions.

      This optimization doesn't affect the choices that ref, range, or join
      optimizer make. This was intentional because this was added after 4.1
      was GA.

    Implementation overview
      1. update_ref_and_keys() accumulates info about null-rejecting
         predicates in in KeyField::null_rejecting
      1.1 add_key_part saves these to KeyUse.
      2. create_ref_for_key copies them to table_reference_st.
      3. add_not_null_conds adds "x IS NOT NULL" to join_tab->select_cond of
         appropiate JoinTable members.
*/
void add_not_null_conds(Join *join)
{
  for (uint32_t i= join->const_tables; i < join->tables; i++)
  {
    JoinTable *tab=join->join_tab+i;
    if ((tab->type == AM_REF || tab->type == AM_EQ_REF ||
         tab->type == AM_REF_OR_NULL) &&
        !tab->table->maybe_null)
    {
      for (uint32_t keypart= 0; keypart < tab->ref.key_parts; keypart++)
      {
        if (tab->ref.null_rejecting & (1 << keypart))
        {
          Item *item= tab->ref.items[keypart];
          Item *notnull;
          assert(item->type() == Item::FIELD_ITEM);
          Item_field *not_null_item= (Item_field*)item;
          JoinTable *referred_tab= not_null_item->field->getTable()->reginfo.join_tab;
          /*
            For UPDATE queries such as:
            UPDATE t1 SET t1.f2=(SELECT MAX(t2.f4) FROM t2 WHERE t2.f3=t1.f1);
            not_null_item is the t1.f1, but it's referred_tab is 0.
          */
          if (!referred_tab || referred_tab->join != join)
            continue;
          if (!(notnull= new Item_func_isnotnull(not_null_item)))
            return;
          /*
            We need to do full fix_fields() call here in order to have correct
            notnull->const_item(). This is needed e.g. by test_quick_select
            when it is called from make_join_select after this function is
            called.
          */
          if (notnull->fix_fields(join->session, &notnull))
            return;
          add_cond_and_fix(&referred_tab->select_cond, notnull);
        }
      }
    }
  }
  return;
}

COND *add_found_match_trig_cond(JoinTable *tab, COND *cond, JoinTable *root_tab)
{
  COND *tmp;
  assert(cond != 0);
  if (tab == root_tab)
    return cond;
  if ((tmp= add_found_match_trig_cond(tab->first_upper, cond, root_tab)))
    tmp= new Item_func_trig_cond(tmp, &tab->found);
  if (tmp)
  {
    tmp->quick_fix_field();
    tmp->update_used_tables();
  }
  return tmp;
}

#define ICP_COND_USES_INDEX_ONLY 10


void JoinTable::cleanup()
{
  safe_delete(select);
  safe_delete(quick);

  if (cache.buff)
  {
    size_t size= cache.end - cache.buff;
    global_join_buffer.sub(size);
    free(cache.buff);
  }
  cache.buff= 0;
  limit= 0;
  if (table)
  {
    if (table->key_read)
    {
      table->key_read= 0;
      table->cursor->extra(HA_EXTRA_NO_KEYREAD);
    }
    table->cursor->ha_index_or_rnd_end();
    /*
      We need to reset this for next select
      (Tested in part_of_refkey)
    */
    table->reginfo.join_tab= 0;
  }
  read_record.end_read_record();
}

bool only_eq_ref_tables(Join *join,Order *order,table_map tables)
{
  for (JoinTable **tab=join->map2table ; tables ; tab++, tables>>=1)
  {
    if (tables & 1 && !eq_ref_table(join, order, *tab))
      return 0;
  }
  return 1;
}

These can't be optimized:

  SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.X,t1.a
  SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b=t2.b ORDER BY t1.a,t2.c
  SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.b,t1.a

Definition at line 1277 of file sql_select.cc.

References drizzled::JoinTable::first_inner, drizzled::table_reference_st::items, drizzled::table_reference_st::key_parts, drizzled::Table::map, and drizzled::JoinTable::type.

enum_nested_loop_state drizzled::evaluate_join_record ( Join *  join,
JoinTable *  join_tab,
int  error 
)

Process one record of the nested loop join.

This function will evaluate parts of WHERE/ON clauses that are applicable to the partial record on hand and in case of success submit this record to the next level of the nested loop.

Definition at line 2654 of file join.cc.

References drizzled::JoinTable::first_unmatched, drizzled::JoinTable::first_upper, drizzled::JoinTable::found, drizzled::JoinTable::found_match, drizzled::Session::is_error(), drizzled::JoinTable::last_inner, drizzled::Join::return_tab, and drizzled::Session::row_count.

Referenced by drizzled::sub_select().

enum_nested_loop_state drizzled::evaluate_null_complemented_join_record ( Join *  join,
JoinTable *  join_tab 
)

Construct a NULL complimented partial join record and feed it to the next level of the nested loop. This function is used in case we have an OUTER join and no matching record was found.

Definition at line 2778 of file join.cc.

References drizzled::JoinTable::first_unmatched, drizzled::JoinTable::first_upper, drizzled::JoinTable::found, drizzled::JoinTable::last_inner, drizzled::JoinTable::not_null_compl, and drizzled::Join::return_tab.

Referenced by drizzled::sub_select().

void drizzled::Join::exec ( ) [inherited]

Exec select.

Todo:
Note, that create_sort_index calls test_if_skip_sort_order and may finally replace sorting with index scan if there is a LIMIT clause in the query. It's never shown in EXPLAIN!
Todo:
When can we have here session->net.report_error not zero?

Definition at line 1386 of file join.cc.

References drizzled::Join::all_fields, drizzled::Join::alloc_func_list(), drizzled::calc_group_buffer(), drizzled::change_refs_to_tmp_fields(), drizzled::change_to_use_tmp_fields(), drizzled::optimizer::SqlSelect::cond, drizzled::count_field_types(), drizzled::Table::cursor, drizzled::do_select(), drizzled::Session::examined_row_count, drizzled::Join::exec_tmp_table1, drizzled::Join::fields_list, drizzled::JoinTable::first_inner, drizzled::Join::group_list, drizzled::Session::is_error(), drizzled::Session::is_fatal_error, drizzled::Join::items0, drizzled::Join::join_free(), drizzled::JoinTable::keyuse, drizzled::make_group_fields(), drizzled::Join::make_sum_func_list(), drizzled::Table::map, drizzled::Join::no_order, drizzled::Join::ref_pointer_array, drizzled::Join::select_distinct, drizzled::Join::select_lex, drizzled::Session::sent_row_count, drizzled::Session::set_proc_info(), drizzled::setup_copy_fields(), drizzled::setup_sum_funcs(), drizzled::Join::skip_sort_order, drizzled::JoinTable::sorted, drizzled::Join::sum_funcs2, drizzled::Join::tables, drizzled::Join::tables_list, drizzled::test_if_skip_sort_order(), drizzled::test_if_subpart(), drizzled::Join::tmp_all_fields1, drizzled::Join::tmp_fields_list1, drizzled::Join::tmp_having, drizzled::Join::tmp_join, drizzled::Join::unit, drizzled::Item::val_int(), and drizzled::Join::zero_result_cause.

Referenced by drizzled::subselect_hash_sj_engine::exec(), and drizzled::select_query().

bool drizzled::find_field_in_item_list ( Field *  field,
void *  data 
)

Helper function for list_contains_unique_index. Find a field reference in a dynamic list of Items. Finds a direct reference of the Field in the list.

Parameters:
[in]fieldThe field to search for.
[in]dataList<Item> *.The list to search in
Return values:
1found
0not found.

Definition at line 4435 of file sql_select.cc.

Referenced by drizzled::Join::optimize().

bool drizzled::find_field_in_order_list ( Field *  field,
void *  data 
)

Helper function for list_contains_unique_index. Find a field reference in a list of order_st structures. Finds a direct reference of the Field in the list.

Parameters:
fieldThe field to search for.
dataorder_st *.The list to search in
Return values:
1found
0not found.

Definition at line 4405 of file sql_select.cc.

Referenced by drizzled::Join::optimize().

static Item_equal* drizzled::find_item_equal ( COND_EQUAL *  cond_equal,
Field *  field,
bool *  inherited_fl 
) [static]

Find the multiple equality predicate containing a field.

The function retrieves the multiple equalities accessed through the con_equal structure from current level and up looking for an equality containing field. It stops retrieval as soon as the equality is found and set up inherited_fl to true if it's found on upper levels.

Parameters:
cond_equalmultiple equalities to search in
fieldfield to look for
[out]inherited_flset up to true if multiple equality is found on upper levels (not on current level of cond_equal)
Returns:
  • Item_equal for the found multiple equality predicate if a success;
  • NULL otherwise.

Definition at line 1345 of file sql_select.cc.

References drizzled::Item_equal::contains().

Referenced by drizzled::check_simple_equality().

static bool drizzled::find_order_in_list ( Session *  session,
Item **  ref_pointer_array,
TableList *  tables,
Order *  order,
List< Item > &  fields,
List< Item > &  all_fields,
bool  is_group_field 
) [static]

Resolve an ORDER BY or GROUP BY column reference.

Given a column reference (represented by 'order') from a GROUP BY or order_st BY clause, find the actual column it represents. If the column being resolved is from the GROUP BY clause, the procedure searches the SELECT list 'fields' and the columns in the FROM list 'tables'. If 'order' is from the ORDER BY clause, only the SELECT list is being searched.

If 'order' is resolved to an Item, then order->item is set to the found Item. If there is no item for the found column (that is, it was resolved into a table field), order->item is 'fixed' and is added to all_fields and ref_pointer_array.

ref_pointer_array and all_fields are updated.

Parameters:
[in]sessionPointer to current thread structure
[in,out]ref_pointer_arrayAll select, group and order by fields
[in]tablesList of tables to search in (usually FROM clause)
[in]orderColumn reference to be resolved
[in]fieldsList of fields to search in (usually SELECT list)
[in,out]all_fieldsAll select, group and order by fields
[in]is_group_fieldTrue if order is a GROUP field, false if order_st by field
Return values:
falseif OK
trueif error occurred

Definition at line 5333 of file sql_select.cc.

References drizzled::Item::basic_const_item(), drizzled::Item::fixed, drizzled::Session::is_fatal_error, and drizzled::Item::val_int().

Referenced by drizzled::setup_group(), and drizzled::setup_order().

void drizzled::free_underlaid_joins ( Session *  ,
Select_Lex *  select 
)

Free joins of subselect of this select.

Parameters:
sessionSession pointer
selectpointer to Select_Lex which subselects joins we will free

Definition at line 6151 of file sql_select.cc.

Referenced by drizzled::delete_query(), drizzled::insert_query(), drizzled::sql_set_variables(), and drizzled::update_query().

static Table * drizzled::get_sort_by_table ( Order *  a,
Order *  b,
TableList *  tables 
) [static]

Return table number if there is only one table in sort order and group and order is compatible, else return 0.

Definition at line 6177 of file join.cc.

References drizzled::Table::map, drizzled::TableList::next_leaf, drizzled::TableList::table, and drizzled::Item::used_tables().

Referenced by drizzled::Join::optimize().

static bool drizzled::greedy_search ( Join *  join,
table_map  remaining_tables,
uint32_t  search_depth,
uint32_t  prune_level 
) [static]

Find a good, possibly optimal, query execution plan (QEP) by a greedy search.

The search procedure uses a hybrid greedy/exhaustive search with controlled exhaustiveness. The search is performed in N = card(remaining_tables) steps. Each step evaluates how promising is each of the unoptimized tables, selects the most promising table, and extends the current partial QEP with that table. Currenly the most 'promising' table is the one with least expensive extension.\

There are two extreme cases:

  1. When (card(remaining_tables) < search_depth), the estimate finds the best complete continuation of the partial QEP. This continuation can be used directly as a result of the search.
  2. When (search_depth == 1) the 'best_extension_by_limited_search' consideres the extension of the current QEP with each of the remaining unoptimized tables.

All other cases are in-between these two extremes. Thus the parameter 'search_depth' controlls the exhaustiveness of the search. The higher the value, the longer the optimizaton time and possibly the better the resulting plan. The lower the value, the fewer alternative plans are estimated, but the more likely to get a bad QEP.

All intermediate and final results of the procedure are stored in 'join':

  • join->positions : modified for every partial QEP that is explored
  • join->best_positions: modified for the current best complete QEP
  • join->best_read : modified for the current best complete QEP
  • join->best_ref : might be partially reordered

The final optimal plan is stored in 'join->best_positions', and its corresponding cost in 'join->best_read'.

Note:
The following pseudocode describes the algorithm of 'greedy_search':
    procedure greedy_search
    input: remaining_tables
    output: pplan;
    {
      pplan = <>;
      do {
        (t, a) = best_extension(pplan, remaining_tables);
        pplan = concat(pplan, (t, a));
        remaining_tables = remaining_tables - t;
      } while (remaining_tables != {})
      return pplan;
    }

where 'best_extension' is a placeholder for a procedure that selects the most "promising" of all tables in 'remaining_tables'. Currently this estimate is performed by calling 'best_extension_by_limited_search' to evaluate all extensions of the current QEP of size 'search_depth', thus the complexity of 'greedy_search' mainly depends on that of 'best_extension_by_limited_search'.

If 'best_extension()' == 'best_extension_by_limited_search()', then the worst-case complexity of this algorithm is <= O(N*N^search_depth/search_depth). When serch_depth >= N, then the complexity of greedy_search is O(N!).
In the future, 'greedy_search' might be extended to support other implementations of 'best_extension', e.g. some simpler quadratic procedure.
Parameters:
joinpointer to the structure providing all context info for the query
remaining_tablesset of tables not included into the partial plan yet
search_depthcontrolls the exhaustiveness of the search
prune_levelthe pruning heuristics that should be applied during search
Return values:
falseok
trueFatal error

Definition at line 4199 of file join.cc.

References drizzled::best_extension_by_limited_search(), drizzled::Join::best_read, drizzled::check_interleaving_with_nj(), drizzled::Join::getPosFromOptimalPlan(), drizzled::Join::getPosFromPartialPlan(), drizzled::Table::map, and drizzled::Join::setPosInPartialPlan().

Referenced by drizzled::choose_plan().

bool drizzled::handle_select ( Session *  session,
LEX *  lex,
select_result *  result,
uint64_t  setup_tables_done_option 
)
bool drizzled::Join::init_save_join_tab ( ) [inherited]

Save the original join layout.

Saves the original join layout so it can be reused in re-execution and for EXPLAIN.

Returns:
Operation status
Return values:
0success.
1error occurred.

Definition at line 1353 of file join.cc.

References drizzled::Join::restore_tmp(), and drizzled::Join::tmp_join.

Referenced by drizzled::Join::optimize().

bool drizzled::is_subkey ( KeyPartInfo *  key_part,
KeyPartInfo *  ref_key_part,
KeyPartInfo *  ref_key_part_end 
) [inline]

Test if a second key is the subkey of the first one.

Parameters:
key_partFirst key parts
ref_key_partSecond key parts
ref_key_part_endLast+1 part of the second key
Note:
Second key MUST be shorter than the first one.
Return values:
1is a subkey
0no sub key

Definition at line 4284 of file sql_select.cc.

Referenced by drizzled::test_if_subkey().

drizzled::Join::Join ( Session session_arg,
List< Item > &  fields_arg,
uint64_t  select_options_arg,
select_result result_arg 
) [inherited]

Constructors

Definition at line 140 of file join.cc.

References drizzled::Join::fields_list, drizzled::Join::rollup, and drizzled::Join::select_distinct.

void drizzled::Join::join_free ( ) [inherited]

Release memory and, if possible, the open tables held by this execution plan (and nested plans). It's used to release some tables before the end of execution in order to increase concurrency and reduce memory consumption.

Partially cleanup Join after it has executed: close index or rnd read (table cursors), free quick selects.

This function is called in the end of execution of a Join, before the used tables are unlocked and closed.

For a join that is resolved using a temporary table, the first sweep is performed against actual tables and an intermediate result is inserted into the temprorary table. The last sweep is performed against the temporary table. Therefore, the base tables and associated buffers used to fill the temporary table are no longer needed, and this function is called to free them.

For a join that is performed without a temporary table, this function is called after all rows are sent, but before EOF packet is sent.

For a simple SELECT with no subqueries this function performs a full cleanup of the Join and calls unlockReadTables to free used base tables.

If a Join is executed for a subquery or if it has a subquery, we can't do the full cleanup and need to do a partial cleanup only.

  • If a Join is not the top level join, we must not unlock the tables because the outer select may not have been evaluated yet, and we can't unlock only selected tables of a query.
  • Additionally, if this Join corresponds to a correlated subquery, we should not free quick selects and join buffers because they will be needed for the next execution of the correlated subquery.
  • However, if this is a Join for a [sub]select, which is not a correlated subquery itself, but has subqueries, we can free it fully and also free Joins of all its subqueries. The exception is a subquery in SELECT list, e.g:
    SELECT a, (select cmax(b) from t1) group by c
    This subquery will not be evaluated at first sweep and its value will not be inserted into the temporary table. Instead, it's evaluated when selecting from the temporary table. Therefore, it can't be freed here even though it's not correlated.
Todo:
Unlock tables even if the join isn't top level select in the tree

Definition at line 1998 of file join.cc.

References drizzled::Join::cleanup(), drizzled::Join::select_lex, and drizzled::Session::unlockReadTables().

Referenced by drizzled::do_select(), and drizzled::Join::exec().

int drizzled::join_read_always_key_or_null ( JoinTable *  tab)

Reading of key with key reference and one part that may be NULL.

Definition at line 3773 of file sql_select.cc.

References drizzled::table_reference_st::null_ref_key.

Referenced by drizzled::optimizer::Index::getStats().

int drizzled::join_read_const ( JoinTable *  tab)

Read a (constant) table when there is at most one matching row.

Parameters:
tabTable to read
Return values:
0Row was found
-1Row was not found
1Got an error (other than row not found) during read

Definition at line 3382 of file sql_select.cc.

References drizzled::Table::cursor, drizzled::Cursor::index_read_idx_map(), drizzled::table_reference_st::key, drizzled::table_reference_st::key_buff, drizzled::table_reference_st::key_parts, and drizzled::Table::report_error().

Referenced by drizzled::optimizer::Const::getStats().

int drizzled::join_read_last_key ( JoinTable *  tab)
int drizzled::join_tab_cmp ( const void *  ptr1,
const void *  ptr2 
)

Compare two JoinTable objects based on the number of accessed records.

Parameters:
ptr1pointer to first JoinTable object
ptr2pointer to second JoinTable object

NOTES The order relation implemented by join_tab_cmp() is not transitive, i.e. it is possible to choose such a, b and c that (a < b) && (b < c) but (c < a). This implies that result of a sort using the relation implemented by join_tab_cmp() depends on the order in which elements are compared, i.e. the result is implementation-specific. Example: a: dependent = 0x0 table->map = 0x1 found_records = 3 ptr = 0x907e6b0 b: dependent = 0x0 table->map = 0x2 found_records = 3 ptr = 0x907e838 c: dependent = 0x6 table->map = 0x10 found_records = 2 ptr = 0x907ecd0

Return values:
1if first is bigger
-1if second is bigger
0if equal

Definition at line 813 of file sql_select.cc.

References drizzled::JoinTable::found_records, and drizzled::Table::map.

Referenced by drizzled::choose_plan().

int drizzled::join_tab_cmp_straight ( const void *  ptr1,
const void *  ptr2 
)

Same as join_tab_cmp, but for use with SELECT_STRAIGHT_JOIN.

Definition at line 832 of file sql_select.cc.

References drizzled::Table::map.

Referenced by drizzled::choose_plan().

bool drizzled::list_contains_unique_index ( Table *  table,
bool(*)(Field *, void *)  find_func,
void *  data 
)

Check if GROUP BY/DISTINCT can be optimized away because the set is already known to be distinct.

Used in removing the GROUP BY/DISTINCT of the following types of statements:

    SELECT [DISTINCT] <unique_key_cols>... FROM <single_table_ref>
      [GROUP BY <unique_key_cols>,...]

If (a,b,c is distinct) then <any combination of a,b,c>,{whatever} is also distinct

This function checks if all the key parts of any of the unique keys of the table are referenced by a list : either the select list through find_field_in_item_list or GROUP BY list through find_field_in_order_list. If the above holds and the key parts cannot contain NULLs then we can safely remove the GROUP BY/DISTINCT, as no result set can be more distinct than an unique key.

Parameters:
tableThe table to operate on.
find_funcfunction to iterate over the list and search for a field
Return values:
1found
0not found.

Definition at line 4365 of file sql_select.cc.

References drizzled::Table::key_info.

Referenced by drizzled::Join::optimize().

static bool drizzled::make_group_fields ( Join *  main_join,
Join *  curr_join 
) [static]

Declarations of static functions used in this source file.

allocate group fields or take prepared (cached).

Parameters:
main_joinjoin of current select
curr_joincurrent join (join of current select or temporary copy of it)
Return values:
0ok
1failed

Definition at line 3170 of file join.cc.

References drizzled::alloc_group_fields(), and drizzled::Join::group_list.

Referenced by drizzled::Join::exec().

static bool drizzled::make_join_readinfo ( Join *  join) [static]

Todo:
Is abort() the correct thing to call here? I call this here because it was what was called in the default case for the switch statement that used to be here.
Todo:
Is abort() the correct thing to call here? I call this here because it was what was called in the default case for the switch statement that used to be here.

Definition at line 5093 of file join.cc.

References drizzled::Table::cursor, drizzled::JoinTable::insideout_buf, drizzled::JoinTable::insideout_match_tab, drizzled::Table::key_info, drizzled::JoinTable::sorted, drizzled::sub_select(), drizzled::Join::tables, and drizzled::JoinTable::type.

Referenced by drizzled::Join::optimize().

static void drizzled::make_outerjoin_info ( Join *  join) [static]

Fill in outer join related info for the execution plan structure.

For each outer join operation left after simplification of the original query the function set up the following pointers in the linear structure join->join_tab representing the selected execution plan. The first inner table t0 for the operation is set to refer to the last inner table tk through the field t0->last_inner. Any inner table ti for the operation are set to refer to the first inner table ti->first_inner. The first inner table t0 for the operation is set to refer to the first inner table of the embedding outer join operation, if there is any, through the field t0->first_upper. The on expression for the outer join operation is attached to the corresponding first inner table through the field t0->on_expr_ref. Here ti are structures of the JoinTable type.

EXAMPLE. For the query:

        SELECT * FROM t1
                      LEFT JOIN
                      (t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
                      ON (t1.a=t2.a AND t1.b=t3.b)
          WHERE t1.c > 5,

given the execution plan with the table order t1,t2,t3,t4 is selected, the following references will be set; t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2] t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2], on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.

Parameters:
joinreference to the info fully describing the query
Note:
The function assumes that the simplification procedure has been already applied to the join query (see simplify_joins). This function can be called only after the execution plan has been chosen.

Definition at line 4658 of file join.cc.

References drizzled::TableList::cond_equal, drizzled::JoinTable::cond_equal, drizzled::JoinTable::first_inner, drizzled::JoinTable::first_upper, drizzled::JoinTable::last_inner, drizzled::TableList::on_expr, drizzled::JoinTable::on_expr_ref, and drizzled::TableList::outer_join.

Referenced by drizzled::Join::optimize().

bool drizzled::Join::make_sum_func_list ( List< Item > &  field_list,
List< Item > &  send_fields,
bool  before_group_by,
bool  recompute = false 
) [inherited]

Initialize 'sum_funcs' array with all Item_sum objects.

Parameters:
field_listAll items
send_fieldsItems in select list
before_group_bySet to 1 if this is called before GROUP BY handling
recomputeSet to true if sum_funcs must be recomputed
Return values:
0ok
1error

Definition at line 2211 of file join.cc.

References drizzled::Item::const_item(), drizzled::Join::rollup, drizzled::Join::rollup_make_fields(), and drizzled::Join::select_lex.

Referenced by drizzled::Join::exec(), and drizzled::Join::optimize().

uint32_t drizzled::max_part_bit ( key_part_map  bits)

Add all keys with uses 'field' for some keypart.

If field->and_level != and_level then only mark key_part as const_part.

Definition at line 498 of file sql_select.cc.

Referenced by drizzled::best_access_path().

int drizzled::Join::optimize ( ) [inherited]

global select optimisation.

Note:
error code saved in field 'error'
Return values:
0success
1error

Definition at line 613 of file join.cc.

References drizzled::add_ref_to_table_cond(), drizzled::Join::all_fields, drizzled::alloc_group_fields(), drizzled::Join::best_read, drizzled::build_bitmap_for_nested_joins(), drizzled::Join::cache_const_exprs(), drizzled::calc_group_buffer(), drizzled::count_field_types(), drizzled::create_distinct_group(), drizzled::Join::exec_tmp_table1, drizzled::Join::fields_list, drizzled::find_field_in_item_list(), drizzled::find_field_in_order_list(), drizzled::get_sort_by_table(), drizzled::Join::group_list, drizzled::Join::group_optimized_away, drizzled::in_left_expr_name, drizzled::Join::init_save_join_tab(), drizzled::Session::is_error(), drizzled::Item::is_expensive(), drizzled::Session::is_fatal_error, drizzled::Join::join_list, drizzled::list_contains_unique_index(), drizzled::make_join_readinfo(), drizzled::make_join_statistics(), drizzled::make_outerjoin_info(), drizzled::Join::make_sum_func_list(), drizzled::Table::map, drizzled::Join::map2table, drizzled::Item::name, drizzled::Join::no_order, drizzled::Join::optimized, drizzled::Session::options, drizzled::optimizer::SqlSelect::quick, drizzled::remove_additional_cond(), drizzled::remove_constants(), drizzled::reset_nj_counters(), drizzled::Join::rollup, drizzled::Join::select, drizzled::Join::select_distinct, drizzled::Join::select_lex, drizzled::Session::set_proc_info(), drizzled::Join::setup_subquery_materialization(), drizzled::setup_sum_funcs(), drizzled::simplify_joins(), drizzled::Join::skip_sort_order, drizzled::Join::sort_by_table, drizzled::substitute_for_best_equal_field(), drizzled::Join::tables, drizzled::Join::tables_list, drizzled::test_if_skip_sort_order(), drizzled::test_if_subpart(), drizzled::Join::tmp_having, drizzled::Item::top_level_item(), drizzled::JoinTable::type, drizzled::Join::unit, drizzled::Session::unlockSomeTables(), drizzled::Session::used_tables, drizzled::Item_func::used_tables(), drizzled::Session::variables, and drizzled::Join::zero_result_cause.

Referenced by drizzled::subselect_hash_sj_engine::exec(), and drizzled::select_query().

void drizzled::optimize_keyuse ( Join *  join,
DYNAMIC_ARRAY *  keyuse_array 
)

Update some values in keyuse for faster choose_plan() loop.

Definition at line 696 of file sql_select.cc.

References drizzled::Table::cursor.

Referenced by drizzled::make_join_statistics().

static void drizzled::optimize_straight_join ( Join *  join,
table_map  join_tables 
) [static]

Select the best ways to access the tables in a query without reordering them.

Find the best access paths for each query table and compute their costs according to their order in the array 'join->best_ref' (thus without reordering the join tables). The function calls sequentially 'best_access_path' for each table in the query to select the best table access method. The final optimal plan is stored in the array 'join->best_positions', and the corresponding cost in 'join->best_read'.

Parameters:
joinpointer to the structure providing all context info for the query
join_tablesset of the tables in the query
Note:
This function can be applied to:
  • queries with STRAIGHT_JOIN
  • internally to compute the cost of an arbitrary QEP
Thus 'optimize_straight_join' can be used at any stage of the query optimization process to finalize a QEP as it is.

Definition at line 4089 of file join.cc.

References drizzled::best_access_path(), drizzled::Join::best_read, drizzled::Join::copyPartialPlanIntoOptimalPlan(), drizzled::Join::getPosFromPartialPlan(), drizzled::optimizer::Position::hasTableForSorting(), drizzled::Table::map, drizzled::Join::sort_by_table, and TIME_FOR_COMPARE.

Referenced by drizzled::choose_plan().

int drizzled::Join::prepare ( Item ***  rref_pointer_array,
TableList tables_init,
uint32_t  wild_num,
COND *  conds_init,
uint32_t  og_num,
Order order_init,
Order group_init,
Item having_init,
Select_Lex *  select_lex_arg,
Select_Lex_Unit *  unit_arg 
) [inherited]
void drizzled::print_join ( Session *  session,
String *  str,
List< TableList > *  tables 
)

Print joins from the FROM clause.

Parameters:
sessionthread Cursor
strstring where table should be printed
tableslist of tables in join

Definition at line 6279 of file sql_select.cc.

Referenced by drizzled::TableList::print().

Item * drizzled::remove_additional_cond ( Item *  conds)

Remove additional condition inserted by IN/ALL/ANY transformation.

Parameters:
condscondition for processing
Returns:
new conditions

Definition at line 2449 of file sql_select.cc.

References drizzled::in_additional_cond, and drizzled::Item::name.

Referenced by drizzled::Join::optimize().

static Order * drizzled::remove_constants ( Join *  join,
Order *  first_order,
COND *  cond,
bool  change_list,
bool *  simple_order 
) [static]

Remove all constants and check if order_st only contains simple expressions.

simple_order is set to 1 if sort_order only uses fields from head table and the head table is not a LEFT JOIN table.

Parameters:
joinJoin handler
first_orderList of SORT or GROUP order
condWHERE statement
change_listSet to 1 if we should remove things from list. If this is not set, then only simple_order is calculated.
simple_orderSet to 1 if we are only using simple expressions
Returns:
Returns new sort order

Definition at line 5202 of file join.cc.

References drizzled::const_expression_in_where(), drizzled::Table::map, drizzled::JoinTable::on_expr_ref, drizzled::Item::str_value, drizzled::Join::tables, drizzled::update_depend_map(), drizzled::Item::used_tables(), drizzled::Item::val_str(), and drizzled::Item::with_subselect.

Referenced by drizzled::Join::optimize().

int drizzled::remove_dup_with_hash_index ( Session *  session,
Table *  table,
uint32_t  field_count,
Field **  first_field,
uint32_t  key_length,
Item *  having 
)

Generate a hash index for each row to quickly find duplicate rows.

Note:
Note that this will not work on tables with blobs!

Definition at line 5111 of file sql_select.cc.

References drizzled::Table::cursor, and drizzled::Item::val_int().

COND * drizzled::remove_eq_conds ( Session *  session,
COND *  cond,
Item::cond_result *  cond_value 
)

Remove const and eq items.

Returns:
Return new item, or NULL if no condition
cond_value is set to according:
  • COND_OK : query is possible (field = constant)
  • COND_TRUE : always true ( 1 = 1 )
  • COND_FALSE : always false ( 1 = 2 )

Definition at line 2708 of file sql_select.cc.

References drizzled::Item::eq(), drizzled::Session::first_successful_insert_id_in_prev_stmt, drizzled::Item::maybe_null, drizzled::Session::options, drizzled::Session::substitute_null_with_insert_id, and drizzled::Field::table.

Referenced by drizzled::delete_query(), and drizzled::update_query().

static void drizzled::reset_nj_counters ( List< TableList > *  join_list) [static]

Set NestedJoin::counter=0 in all nested joins in passed list.

Recursively set NestedJoin::counter=0 for all nested joins contained in the passed join_list.

Parameters:
join_listList of nested joins to process. It may also contain base tables which will be ignored.

Definition at line 6210 of file join.cc.

Referenced by drizzled::choose_plan(), and drizzled::Join::optimize().

static void drizzled::restore_prev_nj_state ( JoinTable *  last) [static]

Nested joins perspective: Remove the last table from the join order.

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.

A table nesting such as t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] is represented by the below join nest tree.

                     NJ1
                  _/ /  \
                _/  /    NJ2
              _/   /     / \ 
             /    /     /   \
   t1 x [ (t2 x t3) x (t4 x t5) ]
  

At the point in time when check_interleaving_with_nj() adds the table t5 to the query execution plan, QEP, it also directs the node named NJ2 to mark the table as covered. NJ2 does so by incrementing its counter member. Since all of NJ2's tables are now covered by the QEP, the algorithm proceeds up the tree to NJ1, incrementing its counter as well. All join nests are now completely covered by the QEP.

restore_prev_nj_state() does the above in reverse. As seen above, the node NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means that the plan covers t2, t3, and NJ2, and that the sub-plan (t4 x t5) completely covers NJ2. The removal of t5 from the partial plan will first decrement NJ2's counter to 1. It will then detect that NJ2 went from being completely to partially covered, and hence the algorithm must continue upwards to NJ1 and decrement its counter to 2. A subsequent removal of t4 will however not influence NJ1 since it did not un-cover the last table in NJ2.

SYNOPSIS restore_prev_nj_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)

Parameters:
lastjoin table to remove, it is assumed to be the last in current partial join order.

Definition at line 6296 of file join.cc.

References drizzled::Join::cur_embedding_map, and drizzled::NestedJoin::is_fully_covered().

Referenced by drizzled::best_extension_by_limited_search().

void drizzled::Join::restore_tmp ( ) [inherited]

Restore values in temporary join.

Definition at line 1296 of file join.cc.

References drizzled::Join::tmp_join.

Referenced by drizzled::Join::init_save_join_tab().

bool drizzled::Join::rollup_init ( ) [inherited]
bool drizzled::Join::rollup_make_fields ( List< Item > &  fields_arg,
List< Item > &  sel_fields,
Item_sum ***  func 
) [inherited]

Fill up rollup structures with pointers to fields to use.

Creates copies of item_sum items for each sum level.

Parameters:
fields_argList of all fields (hidden and real ones)
sel_fieldsPointer to selected fields
funcStore here a pointer to all fields
Return values:
0if ok; In this case func is pointing to next not used element.
1on error

Definition at line 2370 of file join.cc.

References drizzled::Item::const_item(), drizzled::Join::group_list, drizzled::Item::maybe_null, drizzled::Session::mem_root, drizzled::Join::rollup, and drizzled::Join::select_lex.

Referenced by drizzled::Join::make_sum_func_list().

int drizzled::Join::rollup_send_data ( uint32_t  idx) [inherited]

Send all rollup levels higher than the current one to the client.

SAMPLE

      SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
Parameters:
idxLevel we are on:

  • 0 = Total sum level
  • 1 = First group changed (a)
  • 2 = Second group changed (a,b)
Return values:
0ok
1If send_data_failed()

Definition at line 2500 of file join.cc.

References drizzled::Join::ref_pointer_array, drizzled::Join::ref_pointer_array_size, drizzled::Join::rollup, and drizzled::Item::val_int().

int drizzled::Join::rollup_write_data ( uint32_t  idx,
Table table_arg 
) [inherited]

Write all rollup levels higher than the current one to a temp table.

SAMPLE

      SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
Parameters:
idxLevel we are on:

  • 0 = Total sum level
  • 1 = First group changed (a)
  • 2 = Second group changed (a,b)
tablereference to temp table
Return values:
0ok
1if write_data_failed()

Definition at line 2541 of file join.cc.

References drizzled::copy_sum_funcs(), drizzled::Table::cursor, drizzled::Join::ref_pointer_array, drizzled::Join::ref_pointer_array_size, drizzled::Join::rollup, and drizzled::Item::val_int().

bool drizzled::select_query ( Session *  session,
Item ***  rref_pointer_array,
TableList *  tables,
uint32_t  wild_num,
List< Item > &  fields,
COND *  conds,
uint32_t  og_num,
Order *  order,
Order *  group,
Item *  having,
uint64_t  select_options,
select_result *  result,
Select_Lex_Unit *  unit,
Select_Lex *  select_lex 
)

An entry point to single-unit select (a select without UNION).

Parameters:
sessionthread Cursor
rref_pointer_arraya reference to ref_pointer_array of the top-level select_lex for this query
tableslist of all tables used in this query. The tables have been pre-opened.
wild_numnumber of wildcards used in the top level select of this query. For example statement SELECT *, t1.*, catalog.t2.* FROM t0, t1, t2; has 3 wildcards.
fieldslist of items in SELECT list of the top-level select e.g. SELECT a, b, c FROM t1 will have Item_field for a, b and c in this list.
condstop level item of an expression representing WHERE clause of the top level select
og_numtotal number of ORDER BY and GROUP BY clauses arguments
orderlinked list of ORDER BY agruments
grouplinked list of GROUP BY arguments
havingtop level item of HAVING expression
select_optionsselect options (BIG_RESULT, etc)
resultan instance of result set handling class. This object is responsible for send result set rows to the client or inserting them into a table.
select_lexthe only Select_Lex of this query
unittop-level UNIT of this query UNIT is an artificial object created by the parser for every SELECT clause. e.g. SELECT * FROM t1 WHERE a1 IN (SELECT * FROM t2) has 2 unions.
Return values:
falsesuccess
truean error

Definition at line 357 of file sql_select.cc.

References drizzled::Join::change_result(), drizzled::Join::conds_history, drizzled::Join::exec(), drizzled::Join::having_history, drizzled::Session::is_error(), drizzled::Join::optimize(), drizzled::Join::prepare(), drizzled::Session::set_proc_info(), drizzled::Join::tmp_having, and drizzled::Session::used_tables.

Referenced by drizzled::handle_select().

static void drizzled::set_position ( Join *  join,
uint32_t  idx,
JoinTable *  table,
optimizer::KeyUse *  key 
) [static]

Save const tables first as used tables.

Definition at line 3450 of file join.cc.

References drizzled::Join::setPosInPartialPlan().

Referenced by drizzled::make_join_statistics().

bool drizzled::setup_copy_fields ( Session *  session,
Tmp_Table_Param *  param,
Item **  ref_pointer_array,
List< Item > &  res_selected_fields,
List< Item > &  res_all_fields,
uint32_t  elements,
List< Item > &  all_fields 
)

Setup copy_fields to save fields at start of new group.

Setup copy_fields to save fields at start of new group

Only FIELD_ITEM:s and FUNC_ITEM:s needs to be saved between groups. Change old item_field to use a new field with points at saved fieldvalue This function is only called before use of send_fields.

Parameters:
sessionSession pointer
paramtemporary table parameters
ref_pointer_arrayarray of pointers to top elements of filed list
res_selected_fieldsnew list of items of select item list
res_all_fieldsnew list of all items
elementsnumber of elements in select item list
all_fieldsall fields list
Todo:
In most cases this result will be sent to the user. This should be changed to use copy_int or copy_real depending on how the value is to be used: In some cases this may be an argument in a group function, like: IF(ISNULL(col),0,COUNT(*))
Return values:
0ok
!=0error

Definition at line 5778 of file sql_select.cc.

References drizzled::Session::mem_root, drizzled::Item::name, and drizzled::Field::pack_length().

Referenced by drizzled::Join::exec().

Next_select_func drizzled::setup_end_select_func ( Join *  join)

Rows produced by a join sweep may end up in a temporary table or be sent to a client. Setup the function of the nested loop join algorithm which handles final fully constructed and matched records.

Parameters:
joinjoin to setup the function for.
Returns:
end_select function to use. This function can't fail.

Definition at line 2976 of file sql_select.cc.

References drizzled::end_unique_update(), and drizzled::end_update().

Referenced by drizzled::do_select().

int drizzled::setup_group ( Session *  session,
Item **  ref_pointer_array,
TableList *  tables,
List< Item > &  fields,
List< Item > &  all_fields,
Order *  order,
bool *  hidden_group_fields 
)

Intitialize the GROUP BY list.

Parameters:
sessionThread Cursor
ref_pointer_arrayWe store references to all fields that was not in 'fields' here.
fieldsAll fields in the select part. Any item in 'order' that is part of these list is replaced by a pointer to this fields.
all_fieldsTotal list of all unique fields used by the select. All items in 'order' that was not part of fields will be added first to this list.
orderThe fields we should do GROUP BY on.
hidden_group_fieldsPointer to flag that is set to 1 if we added any fields to all_fields.
Todo:
change ER_WRONG_FIELD_WITH_GROUP to more detailed ER_NON_GROUPING_FIELD_USED
Return values:
0ok
1error (probably out of memory)

Definition at line 5512 of file sql_select.cc.

References drizzled::Item::const_item(), drizzled::find_order_in_list(), and drizzled::Item::used_tables().

Referenced by drizzled::setup_without_group().

int drizzled::setup_order ( Session *  session,
Item **  ref_pointer_array,
TableList *  tables,
List< Item > &  fields,
List< Item > &  all_fields,
Order *  order 
)

Change order to point at item in select list.

If item isn't a number and doesn't exits in the select list, add it the the field list.

Definition at line 5470 of file sql_select.cc.

References drizzled::find_order_in_list().

Referenced by drizzled::delete_query(), and drizzled::setup_without_group().

bool drizzled::Join::setup_subquery_materialization ( ) [inherited]

Setup for execution all subqueries of a query, for which the optimizer chose hash semi-join.

Iterate over all subqueries of the query, and if they are under an IN predicate, and the optimizer chose to compute it via hash semi-join:

  • try to initialize all data structures needed for the materialized execution of the IN predicate,
  • if this fails, then perform the IN=>EXISTS transformation which was previously blocked during Join::prepare.

This method is part of the "code generation" query processing phase.

This phase must be called after substitute_for_best_equal_field() because that function may replace items with other items from a multiple equality, and we need to reference the correct items in the index access method of the IN predicate.

Returns:
Operation status
Return values:
falsesuccess.
trueerror occurred.

Definition at line 1935 of file join.cc.

References drizzled::Join::select_lex, and drizzled::Item_in_subselect::setup_engine().

Referenced by drizzled::Join::optimize().

bool drizzled::setup_sum_funcs ( Session *  session,
Item_sum **  func_ptr 
)

Call ::setup for all sum functions.

Parameters:
sessionthread Cursor
func_ptrsum function list
Return values:
falseok
trueerror

Definition at line 6067 of file sql_select.cc.

Referenced by drizzled::Join::exec(), and drizzled::Join::optimize().

static int drizzled::setup_without_group ( Session *  session,
Item **  ref_pointer_array,
TableList *  tables,
TableList *  ,
List< Item > &  fields,
List< Item > &  all_fields,
COND **  conds,
Order *  order,
Order *  group,
bool *  hidden_group_fields 
) [static]

Function to setup clauses without sum functions.

Definition at line 5641 of file join.cc.

References drizzled::setup_group(), and drizzled::setup_order().

Referenced by drizzled::Join::prepare().

static COND * drizzled::simplify_joins ( Join *  join,
List< TableList > *  join_list,
COND *  conds,
bool  top 
) [static]

Simplify joins replacing outer joins by inner joins whenever it's possible.

The function, during a retrieval of join_list, eliminates those outer joins that can be converted into inner join, possibly nested. It also moves the on expressions for the converted outer joins and from inner joins to conds. The function also calculates some attributes for nested joins:

  • used_tables
  • not_null_tables
  • dep_tables.
  • on_expr_dep_tables The first two attributes are used to test whether an outer join can be substituted for an inner join. The third attribute represents the relation 'to be dependent on' for tables. If table t2 is dependent on table t1, then in any evaluated execution plan table access to table t2 must precede access to table t2. This relation is used also to check whether the query contains invalid cross-references. The forth attribute is an auxiliary one and is used to calculate dep_tables. As the attribute dep_tables qualifies possibles orders of tables in the execution plan, the dependencies required by the straight join modifiers are reflected in this attribute as well. The function also removes all braces that can be removed from the join expression without changing its meaning.
Note:
An outer join can be replaced by an inner join if the where condition or the on expression for an embedding nested join contains a conjunctive predicate rejecting null values for some attribute of the inner tables.

E.g. in the query:

      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5

the predicate t2.b < 5 rejects nulls. The query is converted first to:

      SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5

then to the equivalent form:

      SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a

Similarly the following query:

      SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
        WHERE t2.c < 5

is converted to:

      SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b

One conversion might trigger another:

      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
                       LEFT JOIN t3 ON t3.b=t2.b
        WHERE t3 IS NOT NULL =>
      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
        WHERE t3 IS NOT NULL AND t3.b=t2.b =>
      SELECT * FROM t1, t2, t3
        WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a

The function removes all unnecessary braces from the expression produced by the conversions. E.g.

      SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b

finally is converted to:

      SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b

It also will remove braces from the following queries:

      SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
      SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.

The benefit of this simplification procedure is that it might return a query for which the optimizer can evaluate execution plan with more join orders. With a left join operation the optimizer does not consider any plan where one of the inner tables is before some of outer tables.

IMPLEMENTATION The function is implemented by a recursive procedure. On the recursive ascent all attributes are calculated, all outer joins that can be converted are replaced and then all unnecessary braces are removed. As join list contains join tables in the reverse order sequential elimination of outer joins does not require extra recursive calls.

SEMI-JOIN NOTES Remove all semi-joins that have are within another semi-join (i.e. have an "ancestor" semi-join nest)

EXAMPLES Here is an example of a join query with invalid cross references:

      SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
Parameters:
joinreference to the query info
join_listlist representation of the join to be converted
condsconditions to add on expressions for converted joins
toptrue <=> conds is the where condition
Returns:
  • The new condition, if success
  • 0, otherwise

Definition at line 5428 of file join.cc.

References drizzled::Table::map, drizzled::TableList::on_expr, drizzled::TableList::outer_join, drizzled::TableList::prep_on_expr, drizzled::TableList::straight, drizzled::TableList::table, and drizzled::Item::used_tables().

Referenced by drizzled::Join::optimize().

bool drizzled::store_val_in_field ( Field *  field,
Item *  item,
enum_check_fields  check_flag 
)

This function is only called for const items on fields which are keys.

Returns:
returns 1 if there was some conversion made when the field was stored.

Definition at line 926 of file sql_select.cc.

References drizzled::Session::cuted_fields, and drizzled::Table::in_use.

Referenced by drizzled::matching_cond().

enum_nested_loop_state drizzled::sub_select ( Join *  join,
JoinTable *  join_tab,
bool  end_of_records 
)

Retrieve records ends with a given beginning from the result of a join.

For a given partial join record consisting of records from the tables preceding the table join_tab in the execution plan, the function retrieves all matching full records from the result set and send them to the result set stream.

Note:
The function effectively implements the final (n-k) nested loops of nested loops join algorithm, where k is the ordinal number of the join_tab table and n is the total number of tables in the join query. It performs nested loops joins with all conjunctive predicates from the where condition pushed as low to the tables as possible. E.g. for the query
      SELECT * FROM t1,t2,t3
      WHERE t1.a=t2.a AND t2.b=t3.b AND t1.a BETWEEN 5 AND 9
the predicate (t1.a BETWEEN 5 AND 9) will be pushed to table t1, given the selected plan prescribes to nest retrievals of the joined tables in the following order: t1,t2,t3. A pushed down predicate are attached to the table which it pushed to, at the field join_tab->select_cond. When executing a nested loop of level k the function runs through the rows of 'join_tab' and for each row checks the pushed condition attached to the table. If it is false the function moves to the next row of the table. If the condition is true the function recursively executes (n-k-1) remaining embedded nested loops. The situation becomes more complicated if outer joins are involved in the execution plan. In this case the pushed down predicates can be checked only at certain conditions. Suppose for the query
      SELECT * FROM t1 LEFT JOIN (t2,t3) ON t3.a=t1.a
      WHERE t1>2 AND (t2.b>5 OR t2.b IS NULL)
the optimizer has chosen a plan with the table order t1,t2,t3. The predicate P1=t1>2 will be pushed down to the table t1, while the predicate P2=(t2.b>5 OR t2.b IS NULL) will be attached to the table t2. But the second predicate can not be unconditionally tested right after a row from t2 has been read. This can be done only after the first row with t3.a=t1.a has been encountered. Thus, the second predicate P2 is supplied with a guarded value that are stored in the field 'found' of the first inner table for the outer join (table t2). When the first row with t3.a=t1.a for the current row of table t1 appears, the value becomes true. For now on the predicate is evaluated immediately after the row of table t2 has been read. When the first row with t3.a=t1.a has been encountered all conditions attached to the inner tables t2,t3 must be evaluated. Only when all of them are true the row is sent to the output stream. If not, the function returns to the lowest nest level that has a false attached condition. The predicates from on expressions are also pushed down. If in the the above example the on expression were (t3.a=t1.a AND t2.a=t1.a), then t1.a=t2.a would be pushed down to table t2, and without any guard. If after the run through all rows of table t2, the first inner table for the outer join operation, it turns out that no matches are found for the current row of t1, then current row from table t1 is complemented by nulls for t2 and t3. Then the pushed down predicates are checked for the composed row almost in the same way as it had been done for the first row with a match. The only difference is the predicates from on expressions are not checked.
IMPLEMENTATION
The function forms output rows for a current partial join of k tables tables recursively. For each partial join record ending with a certain row from join_tab it calls sub_select that builds all possible matching tails from the result set. To be able check predicates conditionally items of the class Item_func_trig_cond are employed. An object of this class is constructed from an item of class COND and a pointer to a guarding boolean variable. When the value of the guard variable is true the value of the object is the same as the value of the predicate, otherwise it's just returns true. To carry out a return to a nested loop level of join table t the pointer to t is remembered in the field 'return_tab' of the join structure. Consider the following query:
        SELECT * FROM t1,
                      LEFT JOIN
                      (t2, t3 LEFT JOIN (t4,t5) ON t5.a=t3.a)
                      ON t4.a=t2.a
           WHERE (t2.b=5 OR t2.b IS NULL) AND (t4.b=2 OR t4.b IS NULL)
Suppose the chosen execution plan dictates the order t1,t2,t3,t4,t5 and suppose for a given joined rows from tables t1,t2,t3 there are no rows in the result set yet. When first row from t5 that satisfies the on condition t5.a=t3.a is found, the pushed down predicate t4.b=2 OR t4.b IS NULL becomes 'activated', as well the predicate t4.a=t2.a. But the predicate (t2.b=5 OR t2.b IS NULL) can not be checked until t4.a=t2.a becomes true. In order not to re-evaluate the predicates that were already evaluated as attached pushed down predicates, a pointer to the the first most inner unmatched table is maintained in join_tab->first_unmatched. Thus, when the first row from t5 with t5.a=t3.a is found this pointer for t5 is changed from t4 to t2.
STRUCTURE NOTES
join_tab->first_unmatched points always backwards to the first inner table of the embedding nested join, if any.
Parameters:
joinpointer to the structure providing all context info for the query
join_tabthe first next table of the execution plan to be retrieved
end_recordstrue when we need to perform final steps of retrival
Returns:
return one of enum_nested_loop_state, except NESTED_LOOP_NO_MORE_ROWS.

Definition at line 3297 of file sql_select.cc.

References drizzled::evaluate_join_record(), drizzled::evaluate_null_complemented_join_record(), drizzled::JoinTable::found, drizzled::Join::resume_nested_loop, drizzled::Join::return_tab, drizzled::Session::row_count, and drizzled::Join::tables.

Referenced by drizzled::do_select(), and drizzled::make_join_readinfo().

COND * drizzled::substitute_for_best_equal_field ( COND *  cond,
COND_EQUAL *  cond_equal,
void *  table_join_idx 
)

Substitute every field reference in a condition by the best equal field and eliminate all multiple equality predicates.

The function retrieves the cond condition and for each encountered multiple equality predicate it sorts the field references in it according to the order of tables specified by the table_join_idx parameter. Then it eliminates the multiple equality predicate it replacing it by the conjunction of simple equality predicates equating every field from the multiple equality to the first field in it, or to the constant, if there is any. After this the function retrieves all other conjuncted predicates substitute every field reference by the field reference to the first equal field or equal constant if there are any.

Parameters:
condcondition to process
cond_equalmultiple equalities to take into consideration
table_join_idxindex to tables determining field preference
Note:
At the first glance full sort of fields in multiple equality seems to be an overkill. Yet it's not the case due to possible new fields in multiple equality item of lower levels. We want the order in them to comply with the order of upper levels.
Returns:
The transformed condition

Definition at line 2230 of file sql_select.cc.

References drizzled::compare_fields_by_table_order(), drizzled::eliminate_item_equal(), and drizzled::Item_equal::sort().

Referenced by drizzled::Join::optimize().

static int drizzled::test_if_order_by_key ( Order *  order,
Table *  table,
uint32_t  idx,
uint32_t *  used_key_parts 
) [static]

Test if one can use the key to resolve order_st BY.

Parameters:
orderSort order
tableTable to sort
idxIndex to check
used_key_partsReturn value for used key parts.
Note:
used_key_parts is set to correct key parts used if return value != 0 (On other cases, used_key_part may be changed)
Return values:
1key is ok.
0Key can't be used
-1Reverse key can be used

Definition at line 4199 of file sql_select.cc.

References drizzled::Table::cursor, and drizzled::Table::key_info.

Referenced by drizzled::test_if_skip_sort_order(), and drizzled::test_if_subkey().

bool drizzled::test_if_skip_sort_order ( JoinTable *  tab,
Order *  order,
ha_rows  select_limit,
bool  no_changes,
const key_map *  map 
)

Test if we can skip the ORDER BY by using an index.

SYNOPSIS test_if_skip_sort_order() tab order select_limit no_changes map

If we can use an index, the JoinTable / tab->select struct is changed to use the index.

The index must cover all fields in <order>, or it will not be considered.

Todo:
  • sergeyp: Results of all index merge selects actually are ordered by clustered PK values.
Return values:
0We have to use filesort to do the sorting
1We can use an index.

Definition at line 4479 of file sql_select.cc.

References drizzled::optimizer::SqlSelect::cond, drizzled::Table::cursor, drizzled::Join::getPosFromOptimalPlan(), drizzled::Join::group_list, drizzled::join_read_last_key(), drizzled::table_reference_st::key, drizzled::Table::key_info, drizzled::table_reference_st::key_parts, drizzled::JoinTable::keyuse, drizzled::JoinTable::limit, drizzled::JoinTable::pre_idx_push_select_cond, drizzled::optimizer::SqlSelect::quick, drizzled::Table::quick_condition_rows, drizzled::Join::tables, drizzled::test_if_order_by_key(), drizzled::test_if_subkey(), drizzled::JoinTable::type, and drizzled::Join::unit.

Referenced by drizzled::Join::exec(), and drizzled::Join::optimize().

static uint32_t drizzled::test_if_subkey ( Order *  order,
Table *  table,
uint32_t  ref,
uint32_t  ref_key_parts,
const key_map *  usable_keys 
) [static]

Test if we can use one of the 'usable_keys' instead of 'ref' key for sorting.

Parameters:
refNumber of key, used for WHERE clause
usable_keysKeys for testing
Returns:
  • MAX_KEY If we can't use other key
  • the number of found key Otherwise

Definition at line 4305 of file sql_select.cc.

References drizzled::is_subkey(), drizzled::Table::key_info, and drizzled::test_if_order_by_key().

Referenced by drizzled::test_if_skip_sort_order().

static bool drizzled::test_if_subpart ( Order *  a,
Order *  b 
) [static]

Return 1 if second is a subpart of first argument.

If first parts has different direction, change it to second part (group is sorted like order)

Definition at line 6232 of file join.cc.

Referenced by drizzled::Join::exec(), and drizzled::Join::optimize().

void drizzled::update_const_equal_items ( COND *  cond,
JoinTable *  tab 
)

Check appearance of new constant items in multiple equalities of a condition after reading a constant table.

The function retrieves the cond condition and for each encountered multiple equality checks whether new constants have appeared after reading the constant (single row) table tab. If so it adjusts the multiple equality appropriately.

Parameters:
condcondition whose multiple equalities are to be checked
tableconstant table that has been read

Definition at line 2310 of file sql_select.cc.

References drizzled::JoinTable::const_keys, drizzled::Table::key_info, drizzled::Field::key_start, drizzled::JoinTable::keyuse, drizzled::Table::map, and drizzled::Item_equal::update_const().

static void drizzled::update_depend_map ( Join *  join,
Order *  order 
) [static]

Update the dependency map for the sort order.

Definition at line 5164 of file join.cc.

References drizzled::Join::map2table, and drizzled::Item::used_tables().

static void drizzled::update_depend_map ( Join *  join) [static]
bool drizzled::update_ref_and_keys ( Session *  session,
DYNAMIC_ARRAY *  keyuse,
JoinTable *  join_tab,
uint32_t  tables,
COND *  cond,
COND_EQUAL *  ,
table_map  normal_tables,
Select_Lex *  select_lex,
vector< optimizer::SargableParam > &  sargables 
)

Update keyuse array with all possible keys we can use to fetch rows.

Parameters:
session
[out]keyusePut here ordered array of KeyUse structures
join_tabArray in tablenr_order
tablesNumber of tables in join
condWHERE condition (note that the function analyzes join_tab[i]->on_expr too)
normal_tablesTables not inner w.r.t some outer join (ones for which we can make ref access based the WHERE clause)
select_lexcurrent SELECT
[out]sargablesstd::vector of found sargable candidates
Return values:
0OK
1Out of memory.

Definition at line 544 of file sql_select.cc.

References drizzled::JoinTable::checked_keys, drizzled::Join::join_list, drizzled::JoinTable::keyuse, drizzled::Table::map, and drizzled::JoinTable::on_expr_ref.

Referenced by drizzled::make_join_statistics().

void drizzled::update_tmptable_sum_func ( Item_sum **  func_ptr,
Table *   
)

Update record 0 in tmp_table from record 1.

Definition at line 6086 of file sql_select.cc.

Referenced by drizzled::end_unique_update(), and drizzled::end_update().