49
47
#include "drizzled/lock.h"
50
48
#include "drizzled/item/outer_ref.h"
51
49
#include "drizzled/index_hint.h"
52
#include "drizzled/memory/multi_malloc.h"
53
#include "drizzled/records.h"
54
#include "drizzled/internal/iocache.h"
56
#include "drizzled/sql_union.h"
57
#include "drizzled/optimizer/key_field.h"
58
#include "drizzled/optimizer/position.h"
59
#include "drizzled/optimizer/sargable_param.h"
60
#include "drizzled/optimizer/key_use.h"
61
#include "drizzled/optimizer/range.h"
62
#include "drizzled/optimizer/quick_range_select.h"
63
#include "drizzled/optimizer/quick_ror_intersect_select.h"
65
53
using namespace std;
70
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b);
55
const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
56
"MAYBE_REF","ALL","range","index",
57
"ref_or_null","unique_subquery","index_subquery",
61
struct st_sargable_param;
63
static void optimize_keyuse(JOIN *join, DYNAMIC_ARRAY *keyuse_array);
64
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds,
65
DYNAMIC_ARRAY *keyuse);
66
static bool update_ref_and_keys(Session *session, DYNAMIC_ARRAY *keyuse,
68
uint32_t tables, COND *conds,
69
COND_EQUAL *cond_equal,
70
table_map table_map, Select_Lex *select_lex,
71
st_sargable_param **sargables);
72
static int sort_keyuse(KEYUSE *a,KEYUSE *b);
73
static void set_position(JOIN *join,uint32_t index,JOIN_TAB *table,KEYUSE *key);
74
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
75
table_map used_tables);
76
static bool choose_plan(JOIN *join,table_map join_tables);
78
static void best_access_path(JOIN *join, JOIN_TAB *s, Session *session,
79
table_map remaining_tables, uint32_t idx,
80
double record_count, double read_time);
81
static void optimize_straight_join(JOIN *join, table_map join_tables);
82
static bool greedy_search(JOIN *join, table_map remaining_tables,
83
uint32_t depth, uint32_t prune_level);
84
static bool best_extension_by_limited_search(JOIN *join,
85
table_map remaining_tables,
86
uint32_t idx, double record_count,
87
double read_time, uint32_t depth,
88
uint32_t prune_level);
89
static uint32_t determine_search_depth(JOIN* join);
90
extern "C" int join_tab_cmp(const void* ptr1, const void* ptr2);
91
extern "C" int join_tab_cmp_straight(const void* ptr1, const void* ptr2);
93
TODO: 'find_best' is here only temporarily until 'greedy_search' is
96
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index,
97
double record_count,double read_time);
98
static uint32_t cache_record_length(JOIN *join,uint32_t index);
99
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
100
static bool get_best_combination(JOIN *join);
101
static store_key *get_store_key(Session *session,
102
KEYUSE *keyuse, table_map used_tables,
103
KEY_PART_INFO *key_part, unsigned char *key_buff,
104
uint32_t maybe_null);
105
static bool make_simple_join(JOIN *join,Table *tmp_table);
106
static void make_outerjoin_info(JOIN *join);
107
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
108
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
109
static bool only_eq_ref_tables(JOIN *join, order_st *order, table_map tables);
110
static void update_depend_map(JOIN *join);
111
static void update_depend_map(JOIN *join, order_st *order);
112
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond,
113
bool change_list, bool *simple_order);
114
static int return_zero_rows(JOIN *join, select_result *res,TableList *tables,
115
List<Item> &fields, bool send_row,
116
uint64_t select_options, const char *info,
71
118
static COND *build_equal_items(Session *session, COND *cond,
72
119
COND_EQUAL *inherited,
73
120
List<TableList> *join_list,
74
121
COND_EQUAL **cond_equal_ref);
122
static COND* substitute_for_best_equal_field(COND *cond,
123
COND_EQUAL *cond_equal,
124
void *table_join_idx);
125
static COND *simplify_joins(JOIN *join, List<TableList> *join_list,
126
COND *conds, bool top, bool in_sj);
127
static bool check_interleaving_with_nj(JOIN_TAB *last, JOIN_TAB *next);
128
static void restore_prev_nj_state(JOIN_TAB *last);
129
static void reset_nj_counters(List<TableList> *join_list);
130
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
131
uint32_t first_unused);
134
void advance_sj_state(const table_map remaining_tables, const JOIN_TAB *tab);
135
static void restore_prev_sj_state(const table_map remaining_tables,
136
const JOIN_TAB *tab);
138
static COND *optimize_cond(JOIN *join, COND *conds,
139
List<TableList> *join_list,
140
Item::cond_result *cond_value);
141
static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
142
static int do_select(JOIN *join,List<Item> *fields,Table *tmp_table);
144
static enum_nested_loop_state
145
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
147
static enum_nested_loop_state
148
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab);
149
static enum_nested_loop_state
150
flush_cached_records(JOIN *join, JOIN_TAB *join_tab, bool skip_last);
151
static enum_nested_loop_state
152
end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
153
static enum_nested_loop_state
154
end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
155
static enum_nested_loop_state
156
end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
157
static enum_nested_loop_state
158
end_unique_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
160
static int join_read_const_table(JOIN_TAB *tab, POSITION *pos);
161
static int join_read_system(JOIN_TAB *tab);
162
static int join_read_const(JOIN_TAB *tab);
163
static int join_read_key(JOIN_TAB *tab);
164
static int join_read_always_key(JOIN_TAB *tab);
165
static int join_read_last_key(JOIN_TAB *tab);
166
static int join_no_more_records(READ_RECORD *info);
167
static int join_read_next(READ_RECORD *info);
168
static int join_read_next_different(READ_RECORD *info);
169
static int join_init_quick_read_record(JOIN_TAB *tab);
170
static int test_if_quick_select(JOIN_TAB *tab);
171
static int join_init_read_record(JOIN_TAB *tab);
172
static int join_read_first(JOIN_TAB *tab);
173
static int join_read_next_same(READ_RECORD *info);
174
static int join_read_next_same_diff(READ_RECORD *info);
175
static int join_read_last(JOIN_TAB *tab);
176
static int join_read_prev_same(READ_RECORD *info);
177
static int join_read_prev(READ_RECORD *info);
178
int join_read_always_key_or_null(JOIN_TAB *tab);
179
int join_read_next_same_or_null(READ_RECORD *info);
180
static COND *make_cond_for_table(COND *cond,table_map table,
181
table_map used_table,
182
bool exclude_expensive_cond);
76
183
static Item* part_of_refkey(Table *form,Field *field);
77
static bool cmp_buffer_with_ref(JoinTable *tab);
78
static void change_cond_ref_to_const(Session *session,
79
vector<COND_CMP>& save_list,
84
static bool copy_blobs(Field **ptr);
184
static bool test_if_skip_sort_order(JOIN_TAB *tab,order_st *order,
185
ha_rows select_limit, bool no_changes,
187
static bool list_contains_unique_index(Table *table,
188
bool (*find_func) (Field *, void *), void *data);
189
static bool find_field_in_item_list (Field *field, void *data);
190
static bool find_field_in_order_list (Field *field, void *data);
191
static int create_sort_index(Session *session, JOIN *join, order_st *order,
192
ha_rows filesort_limit, ha_rows select_limit,
194
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields,
196
static int remove_dup_with_compare(Session *session, Table *entry, Field **field,
197
uint32_t offset, Item *having);
198
static int remove_dup_with_hash_index(Session *session,Table *table,
199
uint32_t field_count, Field **first_field,
200
uint32_t key_length, Item *having);
201
static int join_init_cache(Session *session,JOIN_TAB *tables,uint32_t table_count);
202
static uint32_t used_blob_length(CACHE_FIELD **ptr);
203
static bool store_record_in_cache(JOIN_CACHE *cache);
204
static void reset_cache_read(JOIN_CACHE *cache);
205
static void reset_cache_write(JOIN_CACHE *cache);
206
static void read_cached_record(JOIN_TAB *tab);
207
static bool cmp_buffer_with_ref(JOIN_TAB *tab);
208
static order_st *create_distinct_group(Session *session, Item **ref_pointer_array,
209
order_st *order, List<Item> &fields,
210
List<Item> &all_fields,
211
bool *all_order_by_fields_used);
212
static bool test_if_subpart(order_st *a,order_st *b);
213
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
214
static void calc_group_buffer(JOIN *join,order_st *group);
215
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
216
static bool alloc_group_fields(JOIN *join,order_st *group);
217
// Create list for using with tempory table
218
static bool change_to_use_tmp_fields(Session *session, Item **ref_pointer_array,
219
List<Item> &new_list1,
220
List<Item> &new_list2,
221
uint32_t elements, List<Item> &items);
222
// Create list for using with tempory table
223
static bool change_refs_to_tmp_fields(Session *session, Item **ref_pointer_array,
224
List<Item> &new_list1,
225
List<Item> &new_list2,
226
uint32_t elements, List<Item> &items);
227
static void init_tmptable_sum_functions(Item_sum **func);
228
static void update_tmptable_sum_func(Item_sum **func,Table *tmp_table);
229
static void copy_sum_funcs(Item_sum **func_ptr, Item_sum **end);
230
static bool add_ref_to_table_cond(Session *session, JOIN_TAB *join_tab);
231
static bool setup_sum_funcs(Session *session, Item_sum **func_ptr);
232
static bool init_sum_functions(Item_sum **func, Item_sum **end);
233
static bool update_sum_func(Item_sum **func);
234
void select_describe(JOIN *join, bool need_tmp_table,bool need_order,
235
bool distinct, const char *message=NULL);
236
static Item *remove_additional_cond(Item* conds);
237
static void add_group_and_distinct_keys(JOIN *join, JOIN_TAB *join_tab);
238
static bool test_if_ref(Item_field *left_item,Item *right_item);
239
static bool replace_where_subcondition(JOIN *join, Item *old_cond,
240
Item *new_cond, bool fix_fields);
86
242
static bool eval_const_cond(COND *cond)
88
244
return ((Item_func*) cond)->val_int() ? true : false;
92
249
This is used to mark equalities that were made from i-th IN-equality.
93
250
We limit semi-join InsideOut optimization to handling max 64 inequalities,
418
Function to setup clauses without sum functions.
420
inline int setup_without_group(Session *session, Item **ref_pointer_array,
424
List<Item> &all_fields,
427
order_st *group, bool *hidden_group_fields)
430
nesting_map save_allow_sum_func=session->lex->allow_sum_func ;
432
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
433
res= setup_conds(session, tables, leaves, conds);
435
session->lex->allow_sum_func|= 1 << session->lex->current_select->nest_level;
436
res= res || setup_order(session, ref_pointer_array, tables, fields, all_fields,
438
session->lex->allow_sum_func&= ~(1 << session->lex->current_select->nest_level);
439
res= res || setup_group(session, ref_pointer_array, tables, fields, all_fields,
440
group, hidden_group_fields);
441
session->lex->allow_sum_func= save_allow_sum_func;
265
445
/*****************************************************************************
266
446
Check fields, find best join, do the select and output fields.
267
447
mysql_select assumes that all tables are already opened
268
448
*****************************************************************************/
451
Prepare of whole select (including sub queries in future).
454
Add check of calculation of GROUP functions and fields:
455
SELECT COUNT(*)+table.col1 from table1;
463
JOIN::prepare(Item ***rref_pointer_array,
464
TableList *tables_init,
465
uint32_t wild_num, COND *conds_init, uint32_t og_num,
466
order_st *order_init, order_st *group_init,
468
Select_Lex *select_lex_arg,
469
Select_Lex_Unit *unit_arg)
471
// to prevent double initialization on EXPLAIN
477
group_list= group_init;
479
tables_list= tables_init;
480
select_lex= select_lex_arg;
481
select_lex->join= this;
482
join_list= &select_lex->top_join_list;
483
union_part= unit_arg->is_union();
485
session->lex->current_select->is_item_list_lookup= 1;
487
If we have already executed SELECT, then it have not sense to prevent
488
its table from update (see unique_table())
490
if (session->derived_tables_processing)
491
select_lex->exclude_from_table_unique_test= true;
493
/* Check that all tables, fields, conds and order are ok */
495
if (!(select_options & OPTION_SETUP_TABLES_DONE) &&
496
setup_tables_and_check_access(session, &select_lex->context, join_list,
497
tables_list, &select_lex->leaf_tables,
501
TableList *table_ptr;
502
for (table_ptr= select_lex->leaf_tables;
504
table_ptr= table_ptr->next_leaf)
507
if (setup_wild(session, tables_list, fields_list, &all_fields, wild_num) ||
508
select_lex->setup_ref_array(session, og_num) ||
509
setup_fields(session, (*rref_pointer_array), fields_list, MARK_COLUMNS_READ,
511
setup_without_group(session, (*rref_pointer_array), tables_list,
512
select_lex->leaf_tables, fields_list,
513
all_fields, &conds, order, group_list,
514
&hidden_group_fields))
515
return(-1); /* purecov: inspected */
517
ref_pointer_array= *rref_pointer_array;
521
nesting_map save_allow_sum_func= session->lex->allow_sum_func;
522
session->where="having clause";
523
session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
524
select_lex->having_fix_field= 1;
525
bool having_fix_rc= (!having->fixed &&
526
(having->fix_fields(session, &having) ||
527
having->check_cols(1)));
528
select_lex->having_fix_field= 0;
529
if (having_fix_rc || session->is_error())
530
return(-1); /* purecov: inspected */
531
session->lex->allow_sum_func= save_allow_sum_func;
535
Item_subselect *subselect;
536
Item_in_subselect *in_subs= NULL;
538
Are we in a subquery predicate?
539
TODO: the block below will be executed for every PS execution without need.
541
if ((subselect= select_lex->master_unit()->item))
543
bool do_semijoin= !test(session->variables.optimizer_switch &
544
OPTIMIZER_SWITCH_NO_SEMIJOIN);
545
if (subselect->substype() == Item_subselect::IN_SUBS)
546
in_subs= (Item_in_subselect*)subselect;
549
Check if we're in subquery that is a candidate for flattening into a
550
semi-join (which is done done in flatten_subqueries()). The
552
1. Subquery predicate is an IN/=ANY subq predicate
553
2. Subquery is a single SELECT (not a UNION)
554
3. Subquery does not have GROUP BY or order_st BY
555
4. Subquery does not use aggregate functions or HAVING
556
5. Subquery predicate is at the AND-top-level of ON/WHERE clause
557
6. No execution method was already chosen (by a prepared statement).
559
(*). We are not in a subquery of a single table UPDATE/DELETE that
560
doesn't have a JOIN (TODO: We should handle this at some
561
point by switching to multi-table UPDATE/DELETE)
563
(**). We're not in a confluent table-less subquery, like
567
!select_lex->master_unit()->first_select()->next_select() && // 2
568
!select_lex->group_list.elements && !order && // 3
569
!having && !select_lex->with_sum_func && // 4
570
session->session_marker && // 5
571
select_lex->outer_select()->join && // (*)
572
select_lex->master_unit()->first_select()->leaf_tables && // (**)
574
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
577
if (!in_subs->left_expr->fixed &&
578
in_subs->left_expr->fix_fields(session, &in_subs->left_expr))
583
Check that the right part of the subselect contains no more than one
584
column. E.g. in SELECT 1 IN (SELECT * ..) the right part is (SELECT * ...)
586
if (subselect->substype() == Item_subselect::IN_SUBS &&
587
(select_lex->item_list.elements !=
588
((Item_in_subselect*)subselect)->left_expr->cols()))
590
my_error(ER_OPERAND_COLUMNS, MYF(0), ((Item_in_subselect*)subselect)->left_expr->cols());
595
/* Register the subquery for further processing */
596
select_lex->outer_select()->join->sj_subselects.append(session->mem_root, in_subs);
597
in_subs->expr_join_nest= (TableList*)session->session_marker;
601
bool do_materialize= !test(session->variables.optimizer_switch &
602
OPTIMIZER_SWITCH_NO_MATERIALIZATION);
604
Check if the subquery predicate can be executed via materialization.
605
The required conditions are:
606
1. Subquery predicate is an IN/=ANY subq predicate
607
2. Subquery is a single SELECT (not a UNION)
608
3. Subquery is not a table-less query. In this case there is no
609
point in materializing.
610
4. Subquery predicate is a top-level predicate
611
(this implies it is not negated)
612
TODO: this is a limitation that should be lifeted once we
613
implement correct NULL semantics (WL#3830)
614
5. Subquery is non-correlated
616
This is an overly restrictive condition. It can be extended to:
617
(Subquery is non-correlated ||
618
Subquery is correlated to any query outer to IN predicate ||
619
(Subquery is correlated to the immediate outer query &&
620
Subquery !contains {GROUP BY, order_st BY [LIMIT],
621
aggregate functions) && subquery predicate is not under "NOT IN"))
622
6. No execution method was already chosen (by a prepared statement).
624
(*) The subquery must be part of a SELECT statement. The current
625
condition also excludes multi-table update statements.
627
We have to determine whether we will perform subquery materialization
628
before calling the IN=>EXISTS transformation, so that we know whether to
629
perform the whole transformation or only that part of it which wraps
630
Item_in_subselect in an Item_in_optimizer.
632
if (do_materialize &&
634
!select_lex->master_unit()->first_select()->next_select() && // 2
635
select_lex->master_unit()->first_select()->leaf_tables && // 3
636
session->lex->sql_command == SQLCOM_SELECT) // *
638
if (in_subs->is_top_level_item() && // 4
639
!in_subs->is_correlated && // 5
640
in_subs->exec_method == Item_in_subselect::NOT_TRANSFORMED) // 6
641
in_subs->exec_method= Item_in_subselect::MATERIALIZATION;
644
Item_subselect::trans_res trans_res;
645
if ((trans_res= subselect->select_transformer(this)) !=
646
Item_subselect::RES_OK)
648
return((trans_res == Item_subselect::RES_ERROR));
657
for (ord= order; ord; ord= ord->next)
659
Item *item= *ord->item;
660
if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
661
item->split_sum_func(session, ref_pointer_array, all_fields);
665
if (having && having->with_sum_func)
666
having->split_sum_func(session, ref_pointer_array, all_fields,
668
if (select_lex->inner_sum_func_list)
670
Item_sum *end=select_lex->inner_sum_func_list;
671
Item_sum *item_sum= end;
674
item_sum= item_sum->next;
675
item_sum->split_sum_func(session, ref_pointer_array,
676
all_fields, item_sum->ref_by, false);
677
} while (item_sum != end);
680
if (select_lex->inner_refs_list.elements &&
681
fix_inner_refs(session, all_fields, select_lex, ref_pointer_array))
685
Check if there are references to un-aggregated columns when computing
686
aggregate functions with implicit grouping (there is no GROUP BY).
688
MODE_ONLY_FULL_GROUP_BY is enabled here by default
690
if (!group_list && select_lex->full_group_by_flag == (NON_AGG_FIELD_USED | SUM_FUNC_USED))
692
my_message(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,
693
ER(ER_MIX_OF_GROUP_FUNC_AND_FIELDS), MYF(0));
697
/* Caclulate the number of groups */
699
for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
704
goto err; /* purecov: inspected */
706
if (result && result->prepare(fields_list, unit_arg))
707
goto err; /* purecov: inspected */
709
/* Init join struct */
710
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
711
ref_pointer_array_size= all_fields.elements*sizeof(Item*);
712
this->group= group_list != 0;
715
#ifdef RESTRICTED_GROUP
716
if (sum_func_count && !group_list && (func_count || field_count))
718
my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
722
if (select_lex->olap == ROLLUP_TYPE && rollup_init())
724
if (alloc_func_list())
730
return(-1); /* purecov: inspected */
735
Remove the predicates pushed down into the subquery
738
JOIN::remove_subq_pushed_predicates()
739
where IN Must be NULL
740
OUT The remaining WHERE condition, or NULL
743
Given that this join will be executed using (unique|index)_subquery,
744
without "checking NULL", remove the predicates that were pushed down
747
If the subquery compares scalar values, we can remove the condition that
748
was wrapped into trig_cond (it will be checked when needed by the subquery
751
If the subquery compares row values, we need to keep the wrapped
752
equalities in the WHERE clause: when the left (outer) tuple has both NULL
753
and non-NULL values, we'll do a full table scan and will rely on the
754
equalities corresponding to non-NULL parts of left tuple to filter out
755
non-matching records.
757
TODO: We can remove the equalities that will be guaranteed to be true by the
758
fact that subquery engine will be using index lookup. This must be done only
759
for cases where there are no conversion errors of significance, e.g. 257
760
that is searched in a byte. But this requires homogenization of the return
761
codes of all Field*::store() methods.
764
void JOIN::remove_subq_pushed_predicates(Item **where)
766
if (conds->type() == Item::FUNC_ITEM &&
767
((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
768
((Item_func *)conds)->arguments()[0]->type() == Item::REF_ITEM &&
769
((Item_func *)conds)->arguments()[1]->type() == Item::FIELD_ITEM &&
770
test_if_ref ((Item_field *)((Item_func *)conds)->arguments()[1],
771
((Item_func *)conds)->arguments()[0]))
271
780
Index lookup-based subquery: save some flags for EXPLAIN output
819
Check if the table's rowid is included in the temptable
822
sj_table_is_included()
824
join_tab The table to be checked
827
SemiJoinDuplicateElimination: check the table's rowid should be included
828
in the temptable. This is so if
830
1. The table is not embedded within some semi-join nest
831
2. The has been pulled out of a semi-join nest, or
833
3. The table is functionally dependent on some previous table
835
[4. This is also true for constant tables that can't be
836
NULL-complemented but this function is not called for such tables]
839
true - Include table's rowid
843
static bool sj_table_is_included(JOIN *join, JOIN_TAB *join_tab)
845
if (join_tab->emb_sj_nest)
848
/* Check if this table is functionally dependent on the tables that
849
are within the same outer join nest
851
TableList *embedding= join_tab->table->pos_in_table_list->embedding;
852
if (join_tab->type == JT_EQ_REF)
854
Table_map_iterator it(join_tab->ref.depend_map & ~PSEUDO_TABLE_BITS);
856
while ((idx= it.next_bit())!=Table_map_iterator::BITMAP_END)
858
JOIN_TAB *ref_tab= join->join_tab + idx;
859
if (embedding == ref_tab->table->pos_in_table_list->embedding)
862
/* Ok, functionally dependent */
865
/* Not functionally dependent => need to include*/
871
Setup the strategies to eliminate semi-join duplicates.
874
setup_semijoin_dups_elimination()
876
options Join options (needed to see if join buffering will be
878
no_jbuf_after Another bit of information re where join buffering will
882
Setup the strategies to eliminate semi-join duplicates. ATM there are 3
885
1. DuplicateWeedout (use of temptable to remove duplicates based on rowids
887
2. FirstMatch (pick only the 1st matching row combination of inner tables)
888
3. InsideOut (scanning the sj-inner table in a way that groups duplicates
889
together and picking the 1st one)
891
The join order has "duplicate-generating ranges", and every range is
892
served by one strategy or a combination of FirstMatch with with some
895
"Duplicate-generating range" is defined as a range within the join order
896
that contains all of the inner tables of a semi-join. All ranges must be
897
disjoint, if tables of several semi-joins are interleaved, then the ranges
898
are joined together, which is equivalent to converting
899
SELECT ... WHERE oe1 IN (SELECT ie1 ...) AND oe2 IN (SELECT ie2 )
901
SELECT ... WHERE (oe1, oe2) IN (SELECT ie1, ie2 ... ...)
904
Applicability conditions are as follows:
906
DuplicateWeedout strategy
907
~~~~~~~~~~~~~~~~~~~~~~~~~
909
(ot|nt)* [ it ((it|ot|nt)* (it|ot))] (nt)*
910
+------+ +=========================+ +---+
913
(1) - Prefix of OuterTables (those that participate in
914
IN-equality and/or are correlated with subquery) and outer
915
Noncorrelated Tables.
916
(2) - The handled range. The range starts with the first sj-inner
917
table, and covers all sj-inner and outer tables
918
Within the range, Inner, Outer, outer Noncorrelated tables
919
may follow in any order.
920
(3) - The suffix of outer Noncorrelated tables.
925
(ot|nt)* [ it ((it|nt)* it) ] (nt)*
926
+------+ +==================+ +---+
929
(1) - Prefix of outer and non-correlated tables
930
(2) - The handled range, which may contain only inner and
931
non-correlated tables.
932
(3) - The suffix of outer Noncorrelated tables.
937
(ot|ct|nt) [ insideout_tbl (ot|nt|it)* it ] (ot|nt)*
938
+--------+ +===========+ +=============+ +------+
941
(1) - Prefix that may contain any outer tables. The prefix must contain
942
all the non-trivially correlated outer tables. (non-trivially means
943
that the correlation is not just through the IN-equality).
945
(2) - Inner table for which the InsideOut scan is performed.
947
(3) - The remainder of the duplicate-generating range. It is served by
948
application of FirstMatch strategy, with the exception that
949
outer IN-correlated tables are considered to be non-correlated.
951
(4) - THe suffix of outer and outer non-correlated tables.
953
If several strategies are applicable, their relative priorities are:
958
This function walks over the join order and sets up the strategies by
959
setting appropriate members in join_tab structures.
963
true Out of memory error
967
int setup_semijoin_dups_elimination(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
969
table_map cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
972
0 - invalid (EOF marker),
974
2 - Temptable (maybe confluent),
975
3 - Temptable with join buffering
978
uint32_t start_idx; /* Left range bound */
979
uint32_t end_idx; /* Right range bound */
981
For Temptable strategy: Bitmap of all outer and correlated tables from
982
all involved join nests.
984
table_map outer_tables;
985
} dups_ranges [MAX_TABLES];
987
TableList *emb_insideout_nest= NULL;
988
table_map emb_sj_map= 0; /* A bitmap of sj-nests (that is, their sj-inner
989
tables) whose ranges we're in */
990
table_map emb_outer_tables= 0; /* sj-outer tables for those sj-nests */
991
table_map range_start_map= 0; /* table_map at current range start */
992
bool dealing_with_jbuf= false; /* true <=> table within cur range uses join buf */
997
First pass: locate the duplicate-generating ranges and pick the strategies.
999
for (i=join->const_tables ; i < join->tables ; i++)
1001
JOIN_TAB *tab=join->join_tab+i;
1002
Table *table=tab->table;
1003
cur_map |= table->map;
1005
if (tab->emb_sj_nest) // Encountered an sj-inner table
1009
dups_ranges[cur_range].start_idx= i;
1010
range_start_map= cur_map & ~table->map;
1012
Remember if this is a possible start of range that is covered by
1013
the InsideOut strategy (the reason that it is not covered could
1014
be that it overlaps with anther semi-join's range. we don't
1015
support InsideOut for joined ranges)
1017
if (join->best_positions[i].use_insideout_scan)
1018
emb_insideout_nest= tab->emb_sj_nest;
1021
emb_sj_map |= tab->emb_sj_nest->sj_inner_tables;
1022
emb_outer_tables |= tab->emb_sj_nest->nested_join->sj_depends_on;
1024
if (tab->emb_sj_nest != emb_insideout_nest)
1027
Two different semi-joins interleave. This cannot be handled by
1030
emb_insideout_nest= NULL;
1034
if (emb_sj_map) /* We're in duplicate-generating range */
1036
if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
1037
tab->type == JT_ALL && tab->use_quick != 2 && !tab->first_inner &&
1038
i <= no_jbuf_after && !dealing_with_jbuf)
1041
This table uses join buffering, which makes use of FirstMatch or
1042
InsideOut strategies impossible for the current and (we assume)
1043
preceding duplicate-producing ranges.
1044
That is, for the join order:
1046
x x [ x x] x [x x x] x [x x X* x] x
1048
+-----+ +-----+ | join buffering use
1051
we'll have to remove r1 and r2 and use duplicate-elimination
1052
strategy that spans all the tables, starting from the very 1st
1055
dealing_with_jbuf= true;
1056
emb_insideout_nest= false;
1059
Absorb all preceding duplicate-eliminating ranges. Their strategies
1062
for (int prev_range= 0; prev_range < cur_range; prev_range++)
1064
dups_ranges[cur_range].outer_tables |=
1065
dups_ranges[prev_range].outer_tables;
1067
dups_ranges[0].start_idx= 0; /* Will need to start from the 1st table */
1068
dups_ranges[0].outer_tables= dups_ranges[cur_range].outer_tables;
1073
Check if we are at the end of duplicate-producing range. We are if
1075
1. It's an InsideOut range (which presumes all correlated tables are
1076
in the prefix), and all inner tables are in the join order prefix,
1078
2. It's a DuplicateElimination range (possibly covering several
1079
SJ-nests), and all inner, outer, and correlated tables of all
1080
sj-nests are in the join order prefix.
1082
bool end_of_range= false;
1083
if (emb_insideout_nest &&
1084
bitmap_covers(cur_map, emb_insideout_nest->sj_inner_tables))
1086
/* Save that this range is handled with InsideOut: */
1087
dups_ranges[cur_range].strategy= 1;
1090
else if (bitmap_covers(cur_map, emb_outer_tables | emb_sj_map))
1093
This is a complete range to be handled with either DuplicateWeedout
1096
dups_ranges[cur_range].strategy= dealing_with_jbuf? 3 : 2;
1098
This will hold tables from within the range that need to be put
1099
into the join buffer before we can use the FirstMatch on its tail.
1101
dups_ranges[cur_range].outer_tables= emb_outer_tables &
1108
dups_ranges[cur_range].end_idx= i+1;
1109
emb_sj_map= emb_outer_tables= 0;
1110
emb_insideout_nest= NULL;
1111
dealing_with_jbuf= false;
1112
dups_ranges[++cur_range].strategy= 0;
1117
Session *session= join->session;
1118
SJ_TMP_TABLE **next_sjtbl_ptr= &join->sj_tmp_tables;
1120
Second pass: setup the chosen strategies
1122
for (int j= 0; j < cur_range; j++)
1124
JOIN_TAB *tab=join->join_tab + dups_ranges[j].start_idx;
1126
if (dups_ranges[j].strategy == 1) // InsideOut strategy
1128
tab->insideout_match_tab= join->join_tab + dups_ranges[j].end_idx - 1;
1131
else // DuplicateWeedout strategy
1133
SJ_TMP_TABLE::TAB sjtabs[MAX_TABLES];
1134
table_map weed_cur_map= join->const_table_map | PSEUDO_TABLE_BITS;
1135
uint32_t jt_rowid_offset= 0; // # tuple bytes are already occupied (w/o NULL bytes)
1136
uint32_t jt_null_bits= 0; // # null bits in tuple bytes
1137
SJ_TMP_TABLE::TAB *last_tab= sjtabs;
1138
uint32_t rowid_keep_flags= JOIN_TAB::CALL_POSITION | JOIN_TAB::KEEP_ROWID;
1139
JOIN_TAB *last_outer_tab= tab - 1;
1141
Walk through the range and remember
1142
- tables that need their rowids to be put into temptable
1143
- the last outer table
1145
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1147
if (sj_table_is_included(join, tab))
1149
last_tab->join_tab= tab;
1150
last_tab->rowid_offset= jt_rowid_offset;
1151
jt_rowid_offset += tab->table->file->ref_length;
1152
if (tab->table->maybe_null)
1154
last_tab->null_byte= jt_null_bits / 8;
1155
last_tab->null_bit= jt_null_bits++;
1158
tab->table->prepare_for_position();
1159
tab->rowid_keep_flags= rowid_keep_flags;
1161
weed_cur_map |= tab->table->map;
1162
if (!tab->emb_sj_nest && bitmap_covers(weed_cur_map,
1163
dups_ranges[j].outer_tables))
1164
last_outer_tab= tab;
1167
if (jt_rowid_offset) /* Temptable has at least one rowid */
1169
SJ_TMP_TABLE *sjtbl;
1170
uint32_t tabs_size= (last_tab - sjtabs) * sizeof(SJ_TMP_TABLE::TAB);
1171
if (!(sjtbl= (SJ_TMP_TABLE*)session->alloc(sizeof(SJ_TMP_TABLE))) ||
1172
!(sjtbl->tabs= (SJ_TMP_TABLE::TAB*) session->alloc(tabs_size)))
1174
memcpy(sjtbl->tabs, sjtabs, tabs_size);
1175
sjtbl->tabs_end= sjtbl->tabs + (last_tab - sjtabs);
1176
sjtbl->rowid_len= jt_rowid_offset;
1177
sjtbl->null_bits= jt_null_bits;
1178
sjtbl->null_bytes= (jt_null_bits + 7)/8;
1180
*next_sjtbl_ptr= sjtbl;
1181
next_sjtbl_ptr= &(sjtbl->next);
1185
create_duplicate_weedout_tmp_table(session,
1190
join->join_tab[dups_ranges[j].start_idx].flush_weedout_table= sjtbl;
1191
join->join_tab[dups_ranges[j].end_idx - 1].check_weed_out_table= sjtbl;
1193
tab= last_outer_tab + 1;
1194
jump_to= last_outer_tab;
1197
/* Create the FirstMatch tail */
1198
for (; tab < join->join_tab + dups_ranges[j].end_idx; tab++)
1200
if (tab->emb_sj_nest)
1201
tab->do_firstmatch= jump_to;
1210
static void cleanup_sj_tmp_tables(JOIN *join)
1212
for (SJ_TMP_TABLE *sj_tbl= join->sj_tmp_tables; sj_tbl;
1213
sj_tbl= sj_tbl->next)
1215
if (sj_tbl->tmp_table)
1217
sj_tbl->tmp_table->free_tmp_table(join->session);
1220
join->sj_tmp_tables= NULL;
1223
uint32_t make_join_orderinfo(JOIN *join);
1226
global select optimisation.
1229
error code saved in field 'error'
1240
// to prevent double initialization on EXPLAIN
1245
session->set_proc_info("optimizing");
1246
row_limit= ((select_distinct || order || group_list) ? HA_POS_ERROR :
1247
unit->select_limit_cnt);
1248
/* select_limit is used to decide if we are likely to scan the whole table */
1249
select_limit= unit->select_limit_cnt;
1250
if (having || (select_options & OPTION_FOUND_ROWS))
1251
select_limit= HA_POS_ERROR;
1252
do_send_rows = (unit->select_limit_cnt) ? 1 : 0;
1253
// Ignore errors of execution if option IGNORE present
1254
if (session->lex->ignore)
1255
session->lex->current_select->no_error= 1;
1257
#ifdef HAVE_REF_TO_FIELDS // Not done yet
1258
/* Add HAVING to WHERE if possible */
1259
if (having && !group_list && !sum_func_count)
1266
else if ((conds=new Item_cond_and(conds,having)))
1269
Item_cond_and can't be fixed after creation, so we do not check
1272
conds->fix_fields(session, &conds);
1273
conds->change_ref_to_fields(session, tables_list);
1274
conds->top_level_item();
1280
/* Convert all outer joins to inner joins if possible */
1281
conds= simplify_joins(this, join_list, conds, true, false);
1282
build_bitmap_for_nested_joins(join_list, 0);
1284
conds= optimize_cond(this, conds, join_list, &cond_value);
1285
if (session->is_error())
1292
having= optimize_cond(this, having, join_list, &having_value);
1293
if (session->is_error())
1298
if (select_lex->where)
1299
select_lex->cond_value= cond_value;
1300
if (select_lex->having)
1301
select_lex->having_value= having_value;
1303
if (cond_value == Item::COND_FALSE || having_value == Item::COND_FALSE ||
1304
(!unit->select_limit_cnt && !(select_options & OPTION_FOUND_ROWS)))
1305
{ /* Impossible cond */
1306
zero_result_cause= having_value == Item::COND_FALSE ?
1307
"Impossible HAVING" : "Impossible WHERE";
1313
/* Optimize count(*), cmin() and cmax() */
1314
if (tables_list && tmp_table_param.sum_func_count && ! group_list)
1318
opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
1319
to the WHERE conditions,
1320
or 1 if all items were resolved,
1321
or 0, or an error number HA_ERR_...
1323
if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
1325
if (res == HA_ERR_KEY_NOT_FOUND)
1327
zero_result_cause= "No matching min/max row";
1338
zero_result_cause= "No matching min/max row";
1342
zero_result_cause= "Select tables optimized away";
1343
tables_list= 0; // All tables resolved
1345
Extract all table-independent conditions and replace the WHERE
1346
clause with them. All other conditions were computed by opt_sum_query
1347
and the MIN/MAX/COUNT function(s) have been replaced by constants,
1348
so there is no need to compute the whole WHERE clause again.
1349
Notice that make_cond_for_table() will always succeed to remove all
1350
computed conditions, because opt_sum_query() is applicable only to
1352
Preserve conditions for EXPLAIN.
1354
if (conds && !(session->lex->describe & DESCRIBE_EXTENDED))
1356
COND *table_independent_conds=
1357
make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
1358
conds= table_independent_conds;
1367
error= -1; // Error is sent to client
1368
sort_by_table= get_sort_by_table(order, group_list, select_lex->leaf_tables);
1370
/* Calculate how to do the join */
1371
session->set_proc_info("statistics");
1372
if (make_join_statistics(this, select_lex->leaf_tables, conds, &keyuse) ||
1373
session->is_fatal_error)
1378
/* Remove distinct if only const tables */
1379
select_distinct= select_distinct && (const_tables != tables);
1380
session->set_proc_info("preparing");
1381
if (result->initialize_tables(this))
1383
return(1); // error == -1
1385
if (const_table_map != found_const_table_map &&
1386
!(select_options & SELECT_DESCRIBE) &&
1388
!(conds->used_tables() & RAND_TABLE_BIT) ||
1389
select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
1391
zero_result_cause= "no matching row in const table";
1395
if (!(session->options & OPTION_BIG_SELECTS) &&
1396
best_read > (double) session->variables.max_join_size &&
1397
!(select_options & SELECT_DESCRIBE))
1398
{ /* purecov: inspected */
1399
my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
1403
if (const_tables && !session->locked_tables &&
1404
!(select_options & SELECT_NO_UNLOCK))
1405
mysql_unlock_some_tables(session, table, const_tables);
1406
if (!conds && outer_join)
1408
/* Handle the case where we have an OUTER JOIN without a WHERE */
1409
conds=new Item_int((int64_t) 1,1); // Always true
1411
select= make_select(*table, const_table_map,
1412
const_table_map, conds, 1, &error);
1414
{ /* purecov: inspected */
1415
error= -1; /* purecov: inspected */
1419
reset_nj_counters(join_list);
1420
make_outerjoin_info(this);
1423
Among the equal fields belonging to the same multiple equality
1424
choose the one that is to be retrieved first and substitute
1425
all references to these in where condition for a reference for
1430
conds= substitute_for_best_equal_field(conds, cond_equal, map2table);
1431
conds->update_used_tables();
1435
Permorm the the optimization on fields evaluation mentioned above
1436
for all on expressions.
1438
for (JOIN_TAB *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
1440
if (*tab->on_expr_ref)
1442
*tab->on_expr_ref= substitute_for_best_equal_field(*tab->on_expr_ref,
1445
(*tab->on_expr_ref)->update_used_tables();
1449
if (conds &&!outer_join && const_table_map != found_const_table_map &&
1450
(select_options & SELECT_DESCRIBE) &&
1451
select_lex->master_unit() == &session->lex->unit) // upper level SELECT
1453
conds=new Item_int((int64_t) 0,1); // Always false
1455
if (make_join_select(this, select, conds))
1458
"Impossible WHERE noticed after reading const tables";
1459
return(0); // error == 0
1462
error= -1; /* if goto err */
1464
/* Optimize distinct away if possible */
1466
order_st *org_order= order;
1467
order=remove_constants(this, order,conds,1, &simple_order);
1468
if (session->is_error())
1475
If we are using order_st BY NULL or order_st BY const_expression,
1476
return result in any order (even if we are using a GROUP BY)
1478
if (!order && org_order)
1482
Check if we can optimize away GROUP BY/DISTINCT.
1483
We can do that if there are no aggregate functions, the
1484
fields in DISTINCT clause (if present) and/or columns in GROUP BY
1485
(if present) contain direct references to all key parts of
1486
an unique index (in whatever order) and if the key parts of the
1487
unique index cannot contain NULLs.
1488
Note that the unique keys for DISTINCT and GROUP BY should not
1489
be the same (as long as they are unique).
1491
The FROM clause must contain a single non-constant table.
1493
if (tables - const_tables == 1 && (group_list || select_distinct) &&
1494
!tmp_table_param.sum_func_count &&
1495
(!join_tab[const_tables].select ||
1496
!join_tab[const_tables].select->quick ||
1497
join_tab[const_tables].select->quick->get_type() !=
1498
QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
1501
list_contains_unique_index(join_tab[const_tables].table,
1502
find_field_in_order_list,
1503
(void *) group_list))
1506
We have found that grouping can be removed since groups correspond to
1507
only one row anyway, but we still have to guarantee correct result
1508
order. The line below effectively rewrites the query from GROUP BY
1509
<fields> to order_st BY <fields>. There are two exceptions:
1510
- if skip_sort_order is set (see above), then we can simply skip
1512
- we can only rewrite order_st BY if the order_st BY fields are 'compatible'
1513
with the GROUP BY ones, i.e. either one is a prefix of another.
1514
We only check if the order_st BY is a prefix of GROUP BY. In this case
1515
test_if_subpart() copies the ASC/DESC attributes from the original
1517
If GROUP BY is a prefix of order_st BY, then it is safe to leave
1520
if (!order || test_if_subpart(group_list, order))
1521
order= skip_sort_order ? 0 : group_list;
1523
If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
1524
rewritten to IGNORE INDEX FOR order_st BY(fields).
1526
join_tab->table->keys_in_use_for_order_by=
1527
join_tab->table->keys_in_use_for_group_by;
1531
if (select_distinct &&
1532
list_contains_unique_index(join_tab[const_tables].table,
1533
find_field_in_item_list,
1534
(void *) &fields_list))
1539
if (group_list || tmp_table_param.sum_func_count)
1541
if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
1544
else if (select_distinct && tables - const_tables == 1)
1547
We are only using one table. In this case we change DISTINCT to a
1549
- The GROUP BY can be done through indexes (no sort) and the order_st
1550
BY only uses selected fields.
1551
(In this case we can later optimize away GROUP BY and order_st BY)
1552
- We are scanning the whole table without LIMIT
1554
- We are using CALC_FOUND_ROWS
1555
- We are using an order_st BY that can't be optimized away.
1557
We don't want to use this optimization when we are using LIMIT
1558
because in this case we can just create a temporary table that
1559
holds LIMIT rows and stop when this table is full.
1561
JOIN_TAB *tab= &join_tab[const_tables];
1562
bool all_order_fields_used;
1564
skip_sort_order= test_if_skip_sort_order(tab, order, select_limit, 1,
1565
&tab->table->keys_in_use_for_order_by);
1566
if ((group_list=create_distinct_group(session, select_lex->ref_pointer_array,
1567
order, fields_list, all_fields,
1568
&all_order_fields_used)))
1570
bool skip_group= (skip_sort_order &&
1571
test_if_skip_sort_order(tab, group_list, select_limit, 1,
1572
&tab->table->keys_in_use_for_group_by) != 0);
1573
count_field_types(select_lex, &tmp_table_param, all_fields, 0);
1574
if ((skip_group && all_order_fields_used) ||
1575
select_limit == HA_POS_ERROR ||
1576
(order && !skip_sort_order))
1578
/* Change DISTINCT to GROUP BY */
1581
if (all_order_fields_used)
1583
if (order && skip_sort_order)
1586
Force MySQL to read the table in sorted order to get result in
1589
tmp_table_param.quick_group=0;
1593
group=1; // For end_write_group
1598
else if (session->is_fatal_error) // End of memory
1603
order_st *old_group_list;
1604
group_list= remove_constants(this, (old_group_list= group_list), conds,
1605
rollup.state == ROLLUP::STATE_NONE,
1607
if (session->is_error())
1612
if (old_group_list && !group_list)
1615
if (!group_list && group)
1617
order=0; // The output has only one row
1619
select_distinct= 0; // No need in distinct for 1 row
1620
group_optimized_away= 1;
1623
calc_group_buffer(this, group_list);
1624
send_group_parts= tmp_table_param.group_parts; /* Save org parts */
1626
if (test_if_subpart(group_list, order) ||
1627
(!group_list && tmp_table_param.sum_func_count))
1630
// Can't use sort on head table if using row cache
1640
Check if we need to create a temporary table.
1641
This has to be done if all tables are not already read (const tables)
1642
and one of the following conditions holds:
1643
- We are using DISTINCT (simple distinct's are already optimized away)
1644
- We are using an order_st BY or GROUP BY on fields not in the first table
1645
- We are using different order_st BY and GROUP BY orders
1646
- The user wants us to buffer the result.
1648
need_tmp= (const_tables != tables &&
1649
((select_distinct || !simple_order || !simple_group) ||
1650
(group_list && order) ||
1651
test(select_options & OPTION_BUFFER_RESULT)));
1653
uint32_t no_jbuf_after= make_join_orderinfo(this);
1654
uint64_t select_opts_for_readinfo=
1655
(select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
1657
sj_tmp_tables= NULL;
1658
if (!select_lex->sj_nests.is_empty())
1659
setup_semijoin_dups_elimination(this, select_opts_for_readinfo,
1662
// No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1663
if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1666
/* Create all structures needed for materialized subquery execution. */
1667
if (setup_subquery_materialization())
1671
is this simple IN subquery?
1673
if (!group_list && !order &&
1674
unit->item && unit->item->substype() == Item_subselect::IN_SUBS &&
1675
tables == 1 && conds &&
1681
if (join_tab[0].type == JT_EQ_REF &&
1682
join_tab[0].ref.items[0]->name == in_left_expr_name)
1684
remove_subq_pushed_predicates(&where);
1685
save_index_subquery_explain_info(join_tab, where);
1686
join_tab[0].type= JT_UNIQUE_SUBQUERY;
1690
subselect_uniquesubquery_engine(session,
1695
else if (join_tab[0].type == JT_REF &&
1696
join_tab[0].ref.items[0]->name == in_left_expr_name)
1698
remove_subq_pushed_predicates(&where);
1699
save_index_subquery_explain_info(join_tab, where);
1700
join_tab[0].type= JT_INDEX_SUBQUERY;
1704
subselect_indexsubquery_engine(session,
1711
} else if (join_tab[0].type == JT_REF_OR_NULL &&
1712
join_tab[0].ref.items[0]->name == in_left_expr_name &&
1713
having->name == in_having_cond)
1715
join_tab[0].type= JT_INDEX_SUBQUERY;
1717
conds= remove_additional_cond(conds);
1718
save_index_subquery_explain_info(join_tab, conds);
1720
change_engine(new subselect_indexsubquery_engine(session,
1730
Need to tell handlers that to play it safe, it should fetch all
1731
columns of the primary key of the tables: this is because MySQL may
1732
build row pointers for the rows, and for all columns of the primary key
1733
the read set has not necessarily been set by the server code.
1735
if (need_tmp || select_distinct || group_list || order)
1737
for (uint32_t i = const_tables; i < tables; i++)
1738
join_tab[i].table->prepare_for_position();
1741
if (const_tables != tables)
1744
Because filesort always does a full table scan or a quick range scan
1745
we must add the removed reference to the select for the table.
1746
We only need to do this when we have a simple_order or simple_group
1747
as in other cases the join is done before the sort.
1749
if ((order || group_list) &&
1750
(join_tab[const_tables].type != JT_ALL) &&
1751
(join_tab[const_tables].type != JT_REF_OR_NULL) &&
1752
((order && simple_order) || (group_list && simple_group)))
1754
if (add_ref_to_table_cond(session,&join_tab[const_tables])) {
1759
if (!(select_options & SELECT_BIG_RESULT) &&
1762
!test_if_skip_sort_order(&join_tab[const_tables], group_list,
1763
unit->select_limit_cnt, 0,
1764
&join_tab[const_tables].table->
1765
keys_in_use_for_group_by))) ||
1767
tmp_table_param.quick_group)
1769
need_tmp=1; simple_order=simple_group=0; // Force tmp table without sort
1774
Force using of tmp table if sorting by a SP or UDF function due to
1775
their expensive and probably non-deterministic nature.
1777
for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1779
Item *item= *tmp_order->item;
1780
if (item->is_expensive())
1782
/* Force tmp table without sort */
1783
need_tmp=1; simple_order=simple_group=0;
1791
if (select_options & SELECT_DESCRIBE)
1799
The loose index scan access method guarantees that all grouping or
1800
duplicate row elimination (for distinct) is already performed
1801
during data retrieval, and that all MIN/MAX functions are already
1802
computed for each group. Thus all MIN/MAX functions should be
1803
treated as regular functions, and there is no need to perform
1804
grouping in the main execution loop.
1805
Notice that currently loose index scan is applicable only for
1806
single table queries, thus it is sufficient to test only the first
1807
join_tab element of the plan for its access method.
1809
if (join_tab->is_using_loose_index_scan())
1810
tmp_table_param.precomputed_group_by= true;
1812
/* Create a tmp table if distinct or if the sort is too complicated */
1815
session->set_proc_info("Creating tmp table");
1817
init_items_ref_array();
1819
tmp_table_param.hidden_field_count= (all_fields.elements -
1820
fields_list.elements);
1821
order_st *tmp_group= ((!simple_group && !(test_flags & TEST_NO_KEY_GROUP)) ? group_list :
1824
Pushing LIMIT to the temporary table creation is not applicable
1825
when there is order_st BY or GROUP BY or there is no GROUP BY, but
1826
there are aggregate functions, because in all these cases we need
1829
ha_rows tmp_rows_limit= ((order == 0 || skip_sort_order) &&
1831
!session->lex->current_select->with_sum_func) ?
1832
select_limit : HA_POS_ERROR;
1834
if (!(exec_tmp_table1=
1835
create_tmp_table(session, &tmp_table_param, all_fields,
1837
group_list ? 0 : select_distinct,
1838
group_list && simple_group,
1847
We don't have to store rows in temp table that doesn't match HAVING if:
1848
- we are sorting the table and writing complete group rows to the
1850
- We are using DISTINCT without resolving the distinct as a GROUP BY
1853
If having is not handled here, it will be checked before the row
1854
is sent to the client.
1857
(sort_and_group || (exec_tmp_table1->distinct && !group_list)))
1860
/* if group or order on first table, sort first */
1861
if (group_list && simple_group)
1863
session->set_proc_info("Sorting for group");
1864
if (create_sort_index(session, this, group_list,
1865
HA_POS_ERROR, HA_POS_ERROR, false) ||
1866
alloc_group_fields(this, group_list) ||
1867
make_sum_func_list(all_fields, fields_list, 1) ||
1868
setup_sum_funcs(session, sum_funcs))
1876
if (make_sum_func_list(all_fields, fields_list, 0) ||
1877
setup_sum_funcs(session, sum_funcs))
1882
if (!group_list && ! exec_tmp_table1->distinct && order && simple_order)
1884
session->set_proc_info("Sorting for order");
1885
if (create_sort_index(session, this, order,
1886
HA_POS_ERROR, HA_POS_ERROR, true))
1895
Optimize distinct when used on some of the tables
1896
SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
1897
In this case we can stop scanning t2 when we have found one t1.a
1900
if (exec_tmp_table1->distinct)
1902
table_map used_tables= session->used_tables;
1903
JOIN_TAB *last_join_tab= join_tab+tables-1;
1906
if (used_tables & last_join_tab->table->map)
1908
last_join_tab->not_used_in_distinct=1;
1909
} while (last_join_tab-- != join_tab);
1910
/* Optimize "select distinct b from t1 order by key_part_1 limit #" */
1911
if (order && skip_sort_order)
1913
/* Should always succeed */
1914
if (test_if_skip_sort_order(&join_tab[const_tables],
1915
order, unit->select_limit_cnt, 0,
1916
&join_tab[const_tables].table->
1917
keys_in_use_for_order_by))
1923
If this join belongs to an uncacheable subquery save
1926
if (select_lex->uncacheable && !is_top_level_join() &&
1927
init_save_join_tab())
1928
return(-1); /* purecov: inspected */
1937
Restore values in temporary join.
1939
void JOIN::restore_tmp()
1941
memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1948
unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1949
select_lex->offset_limit->val_uint() :
1954
if (exec_tmp_table1)
1956
exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
1957
exec_tmp_table1->file->ha_delete_all_rows();
1958
free_io_cache(exec_tmp_table1);
1959
filesort_free_buffers(exec_tmp_table1,0);
1961
if (exec_tmp_table2)
1963
exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
1964
exec_tmp_table2->file->ha_delete_all_rows();
1965
free_io_cache(exec_tmp_table2);
1966
filesort_free_buffers(exec_tmp_table2,0);
1969
set_items_ref_array(items0);
1972
memcpy(join_tab, join_tab_save, sizeof(JOIN_TAB) * tables);
1977
/* Reset of sum functions */
1980
Item_sum *func, **func_ptr= sum_funcs;
1981
while ((func= *(func_ptr++)))
1989
@brief Save the original join layout
1991
@details Saves the original join layout so it can be reused in
1992
re-execution and for EXPLAIN.
1994
@return Operation status
1996
@retval 1 error occurred.
2000
JOIN::init_save_join_tab()
2002
if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
2003
return 1; /* purecov: inspected */
2004
error= 0; // Ensure that tmp_join.error= 0
2011
JOIN::save_join_tab()
2013
if (!join_tab_save && select_lex->master_unit()->uncacheable)
2015
if (!(join_tab_save= (JOIN_TAB*)session->memdup((unsigned char*) join_tab,
2016
sizeof(JOIN_TAB) * tables)))
2027
Note, that create_sort_index calls test_if_skip_sort_order and may
2028
finally replace sorting with index scan if there is a LIMIT clause in
2029
the query. It's never shown in EXPLAIN!
2032
When can we have here session->net.report_error not zero?
2036
List<Item> *columns_list= &fields_list;
2039
session->set_proc_info("executing");
2042
if (!tables_list && (tables || !select_lex->with_sum_func))
2044
/* Only test of functions */
2045
if (select_options & SELECT_DESCRIBE)
2046
select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
2049
result->send_fields(*columns_list, Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2051
We have to test for 'conds' here as the WHERE may not be constant
2052
even if we don't have any tables for prepared statements or if
2053
conds uses something like 'rand()'.
2055
if (cond_value != Item::COND_FALSE &&
2056
(!conds || conds->val_int()) &&
2057
(!having || having->val_int()))
2059
if (do_send_rows && result->send_data(fields_list))
2063
error= (int) result->send_eof();
2064
send_records= ((select_options & OPTION_FOUND_ROWS) ? 1 : session->sent_row_count);
2069
error= (int) result->send_eof();
2073
/* Single select (without union) always returns 0 or 1 row */
2074
session->limit_found_rows= send_records;
2075
session->examined_row_count= 0;
2079
Don't reset the found rows count if there're no tables as
2080
FOUND_ROWS() may be called. Never reset the examined row count here.
2081
It must be accumulated from all join iterations of all join parts.
2084
session->limit_found_rows= 0;
2086
if (zero_result_cause)
2088
(void) return_zero_rows(this, result, select_lex->leaf_tables,
2090
send_row_on_empty_set(),
2097
if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
2100
if (select_options & SELECT_DESCRIBE)
2103
Check if we managed to optimize order_st BY away and don't use temporary
2104
table to resolve order_st BY: in that case, we only may need to do
2105
filesort for GROUP BY.
2107
if (!order && !no_order && (!skip_sort_order || !need_tmp))
2109
/* Reset 'order' to 'group_list' and reinit variables describing 'order' */
2111
simple_order= simple_group;
2114
if (order && (order != group_list || !(select_options & SELECT_BIG_RESULT)))
2116
if (const_tables == tables
2117
|| ((simple_order || skip_sort_order)
2118
&& test_if_skip_sort_order(&join_tab[const_tables], order, select_limit, 0, &join_tab[const_tables].table->keys_in_use_for_query)))
2122
select_describe(this, need_tmp, order != 0 && !skip_sort_order, select_distinct, !tables ? "No tables used" : NULL);
2126
JOIN *curr_join= this;
2127
List<Item> *curr_all_fields= &all_fields;
2128
List<Item> *curr_fields_list= &fields_list;
2129
Table *curr_tmp_table= 0;
2131
Initialize examined rows here because the values from all join parts
2132
must be accumulated in examined_row_count. Hence every join
2133
iteration must count from zero.
2135
curr_join->examined_rows= 0;
2137
/* Create a tmp table if distinct or if the sort is too complicated */
2143
We are in a non cacheable sub query. Get the saved join structure
2145
(curr_join may have been modified during last exection and we need
2148
curr_join= tmp_join;
2150
curr_tmp_table= exec_tmp_table1;
2152
/* Copy data to the temporary table */
2153
session->set_proc_info("Copying to tmp table");
2154
if (! curr_join->sort_and_group && curr_join->const_tables != curr_join->tables)
2155
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2156
if ((tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2161
curr_tmp_table->file->info(HA_STATUS_VARIABLE);
2163
if (curr_join->having)
2164
curr_join->having= curr_join->tmp_having= 0; // Allready done
2166
/* Change sum_fields reference to calculated fields in tmp_table */
2167
curr_join->all_fields= *curr_all_fields;
2170
items1= items0 + all_fields.elements;
2171
if (sort_and_group || curr_tmp_table->group)
2173
if (change_to_use_tmp_fields(session, items1,
2174
tmp_fields_list1, tmp_all_fields1,
2175
fields_list.elements, all_fields))
2180
if (change_refs_to_tmp_fields(session, items1,
2181
tmp_fields_list1, tmp_all_fields1,
2182
fields_list.elements, all_fields))
2185
curr_join->tmp_all_fields1= tmp_all_fields1;
2186
curr_join->tmp_fields_list1= tmp_fields_list1;
2187
curr_join->items1= items1;
2189
curr_all_fields= &tmp_all_fields1;
2190
curr_fields_list= &tmp_fields_list1;
2191
curr_join->set_items_ref_array(items1);
2193
if (sort_and_group || curr_tmp_table->group)
2195
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count
2196
+ curr_join->tmp_table_param.func_count;
2197
curr_join->tmp_table_param.sum_func_count= 0;
2198
curr_join->tmp_table_param.func_count= 0;
2202
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.func_count;
2203
curr_join->tmp_table_param.func_count= 0;
2206
if (curr_tmp_table->group)
2207
{ // Already grouped
2208
if (!curr_join->order && !curr_join->no_order && !skip_sort_order)
2209
curr_join->order= curr_join->group_list; /* order by group */
2210
curr_join->group_list= 0;
2214
If we have different sort & group then we must sort the data by group
2215
and copy it to another tmp table
2216
This code is also used if we are using distinct something
2217
we haven't been able to store in the temporary table yet
2218
like SEC_TO_TIME(SUM(...)).
2221
if ((curr_join->group_list && (!test_if_subpart(curr_join->group_list, curr_join->order) || curr_join->select_distinct))
2222
|| (curr_join->select_distinct && curr_join->tmp_table_param.using_indirect_summary_function))
2223
{ /* Must copy to another table */
2224
/* Free first data from old join */
2225
curr_join->join_free();
2226
if (make_simple_join(curr_join, curr_tmp_table))
2228
calc_group_buffer(curr_join, group_list);
2229
count_field_types(select_lex, &curr_join->tmp_table_param,
2230
curr_join->tmp_all_fields1,
2231
curr_join->select_distinct && !curr_join->group_list);
2232
curr_join->tmp_table_param.hidden_field_count= curr_join->tmp_all_fields1.elements
2233
- curr_join->tmp_fields_list1.elements;
2235
if (exec_tmp_table2)
2236
curr_tmp_table= exec_tmp_table2;
2239
/* group data to new table */
2242
If the access method is loose index scan then all MIN/MAX
2243
functions are precomputed, and should be treated as regular
2244
functions. See extended comment in JOIN::exec.
2246
if (curr_join->join_tab->is_using_loose_index_scan())
2247
curr_join->tmp_table_param.precomputed_group_by= true;
2249
if (!(curr_tmp_table=
2250
exec_tmp_table2= create_tmp_table(session,
2251
&curr_join->tmp_table_param,
2254
curr_join->select_distinct &&
2255
!curr_join->group_list,
2256
1, curr_join->select_options,
2260
curr_join->exec_tmp_table2= exec_tmp_table2;
2262
if (curr_join->group_list)
2264
session->set_proc_info("Creating sort index");
2265
if (curr_join->join_tab == join_tab && save_join_tab())
2269
if (create_sort_index(session, curr_join, curr_join->group_list,
2270
HA_POS_ERROR, HA_POS_ERROR, false) ||
2271
make_group_fields(this, curr_join))
2275
sortorder= curr_join->sortorder;
2278
session->set_proc_info("Copying to group table");
2280
if (curr_join != this)
2284
curr_join->sum_funcs= sum_funcs2;
2285
curr_join->sum_funcs_end= sum_funcs_end2;
2289
curr_join->alloc_func_list();
2290
sum_funcs2= curr_join->sum_funcs;
2291
sum_funcs_end2= curr_join->sum_funcs_end;
2294
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list, 1, true))
2296
curr_join->group_list= 0;
2298
if (!curr_join->sort_and_group && (curr_join->const_tables != curr_join->tables))
2299
curr_join->join_tab[curr_join->const_tables].sorted= 0;
2301
if (setup_sum_funcs(curr_join->session, curr_join->sum_funcs)
2302
|| (tmp_error= do_select(curr_join, (List<Item> *) 0, curr_tmp_table)))
2307
end_read_record(&curr_join->join_tab->read_record);
2308
curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
2309
curr_join->join_tab[0].table= 0; // Table is freed
2311
// No sum funcs anymore
2314
items2= items1 + all_fields.elements;
2315
if (change_to_use_tmp_fields(session, items2,
2316
tmp_fields_list2, tmp_all_fields2,
2317
fields_list.elements, tmp_all_fields1))
2319
curr_join->tmp_fields_list2= tmp_fields_list2;
2320
curr_join->tmp_all_fields2= tmp_all_fields2;
2322
curr_fields_list= &curr_join->tmp_fields_list2;
2323
curr_all_fields= &curr_join->tmp_all_fields2;
2324
curr_join->set_items_ref_array(items2);
2325
curr_join->tmp_table_param.field_count+= curr_join->tmp_table_param.sum_func_count;
2326
curr_join->tmp_table_param.sum_func_count= 0;
2328
if (curr_tmp_table->distinct)
2329
curr_join->select_distinct=0; /* Each row is unique */
2331
curr_join->join_free(); /* Free quick selects */
2332
if (curr_join->select_distinct && ! curr_join->group_list)
2334
session->set_proc_info("Removing duplicates");
2335
if (curr_join->tmp_having)
2336
curr_join->tmp_having->update_used_tables();
2338
if (remove_duplicates(curr_join, curr_tmp_table,
2339
*curr_fields_list, curr_join->tmp_having))
2342
curr_join->tmp_having=0;
2343
curr_join->select_distinct=0;
2345
curr_tmp_table->reginfo.lock_type= TL_UNLOCK;
2346
if (make_simple_join(curr_join, curr_tmp_table))
2348
calc_group_buffer(curr_join, curr_join->group_list);
2349
count_field_types(select_lex, &curr_join->tmp_table_param, *curr_all_fields, 0);
2353
if (curr_join->group || curr_join->tmp_table_param.sum_func_count)
2355
if (make_group_fields(this, curr_join))
2361
init_items_ref_array();
2362
items3= ref_pointer_array + (all_fields.elements*4);
2363
setup_copy_fields(session, &curr_join->tmp_table_param,
2364
items3, tmp_fields_list3, tmp_all_fields3,
2365
curr_fields_list->elements, *curr_all_fields);
2366
tmp_table_param.save_copy_funcs= curr_join->tmp_table_param.copy_funcs;
2367
tmp_table_param.save_copy_field= curr_join->tmp_table_param.copy_field;
2368
tmp_table_param.save_copy_field_end= curr_join->tmp_table_param.copy_field_end;
2369
curr_join->tmp_all_fields3= tmp_all_fields3;
2370
curr_join->tmp_fields_list3= tmp_fields_list3;
2374
curr_join->tmp_table_param.copy_funcs= tmp_table_param.save_copy_funcs;
2375
curr_join->tmp_table_param.copy_field= tmp_table_param.save_copy_field;
2376
curr_join->tmp_table_param.copy_field_end= tmp_table_param.save_copy_field_end;
2378
curr_fields_list= &tmp_fields_list3;
2379
curr_all_fields= &tmp_all_fields3;
2380
curr_join->set_items_ref_array(items3);
2382
if (curr_join->make_sum_func_list(*curr_all_fields, *curr_fields_list,
2384
setup_sum_funcs(curr_join->session, curr_join->sum_funcs) ||
2385
session->is_fatal_error)
2388
if (curr_join->group_list || curr_join->order)
2390
session->set_proc_info("Sorting result");
2391
/* If we have already done the group, add HAVING to sorted table */
2392
if (curr_join->tmp_having && ! curr_join->group_list && ! curr_join->sort_and_group)
2394
// Some tables may have been const
2395
curr_join->tmp_having->update_used_tables();
2396
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables];
2397
table_map used_tables= (curr_join->const_table_map |
2398
curr_table->table->map);
2400
Item* sort_table_cond= make_cond_for_table(curr_join->tmp_having, used_tables, used_tables, 0);
2401
if (sort_table_cond)
2403
if (!curr_table->select)
2404
if (!(curr_table->select= new SQL_SELECT))
2406
if (!curr_table->select->cond)
2407
curr_table->select->cond= sort_table_cond;
2408
else // This should never happen
2410
if (!(curr_table->select->cond=
2411
new Item_cond_and(curr_table->select->cond,
2415
Item_cond_and do not need fix_fields for execution, its parameters
2416
are fixed or do not need fix_fields, too
2418
curr_table->select->cond->quick_fix_field();
2420
curr_table->select_cond= curr_table->select->cond;
2421
curr_table->select_cond->top_level_item();
2422
curr_join->tmp_having= make_cond_for_table(curr_join->tmp_having,
2429
curr_join->select_limit= HA_POS_ERROR;
2433
We can abort sorting after session->select_limit rows if we there is no
2434
WHERE clause for any tables after the sorted one.
2436
JOIN_TAB *curr_table= &curr_join->join_tab[curr_join->const_tables+1];
2437
JOIN_TAB *end_table= &curr_join->join_tab[curr_join->tables];
2438
for (; curr_table < end_table ; curr_table++)
2441
table->keyuse is set in the case there was an original WHERE clause
2442
on the table that was optimized away.
2444
if (curr_table->select_cond ||
2445
(curr_table->keyuse && !curr_table->first_inner))
2447
/* We have to sort all rows */
2448
curr_join->select_limit= HA_POS_ERROR;
2453
if (curr_join->join_tab == join_tab && save_join_tab())
2456
Here we sort rows for order_st BY/GROUP BY clause, if the optimiser
2457
chose FILESORT to be faster than INDEX SCAN or there is no
2458
suitable index present.
2459
Note, that create_sort_index calls test_if_skip_sort_order and may
2460
finally replace sorting with index scan if there is a LIMIT clause in
2461
the query. XXX: it's never shown in EXPLAIN!
2462
OPTION_FOUND_ROWS supersedes LIMIT and is taken into account.
2464
if (create_sort_index(session, curr_join,
2465
curr_join->group_list ?
2466
curr_join->group_list : curr_join->order,
2467
curr_join->select_limit,
2468
(select_options & OPTION_FOUND_ROWS ?
2469
HA_POS_ERROR : unit->select_limit_cnt),
2470
curr_join->group_list ? true : false))
2473
sortorder= curr_join->sortorder;
2474
if (curr_join->const_tables != curr_join->tables &&
2475
!curr_join->join_tab[curr_join->const_tables].table->sort.io_cache)
2478
If no IO cache exists for the first table then we are using an
2479
INDEX SCAN and no filesort. Thus we should not remove the sorted
2480
attribute on the INDEX SCAN.
2486
/* XXX: When can we have here session->is_error() not zero? */
2487
if (session->is_error())
2489
error= session->is_error();
2492
curr_join->having= curr_join->tmp_having;
2493
curr_join->fields= curr_fields_list;
2495
session->set_proc_info("Sending data");
2496
result->send_fields(*curr_fields_list,
2497
Protocol::SEND_NUM_ROWS | Protocol::SEND_EOF);
2498
error= do_select(curr_join, curr_fields_list, NULL);
2499
session->limit_found_rows= curr_join->send_records;
2501
/* Accumulate the counts from all join iterations of all join parts. */
2502
session->examined_row_count+= curr_join->examined_rows;
2505
With EXPLAIN EXTENDED we have to restore original ref_array
2506
for a derived table which is always materialized.
2507
Otherwise we would not be able to print the query correctly.
2509
if (items0 && (session->lex->describe & DESCRIBE_EXTENDED) && select_lex->linkage == DERIVED_TABLE_TYPE)
2510
set_items_ref_array(items0);
2519
Return error that hold JOIN.
2523
select_lex->join= 0;
2527
if (join_tab != tmp_join->join_tab)
2529
JOIN_TAB *tab, *end;
2530
for (tab= join_tab, end= tab+tables ; tab != end ; tab++)
2533
tmp_join->tmp_join= 0;
2534
tmp_table_param.copy_field=0;
2535
return(tmp_join->destroy());
2540
if (exec_tmp_table1)
2541
exec_tmp_table1->free_tmp_table(session);
2542
if (exec_tmp_table2)
2543
exec_tmp_table2->free_tmp_table(session);
2545
delete_dynamic(&keyuse);
306
2550
An entry point to single-unit select (a select without UNION).
308
@param session thread Cursor
2552
@param session thread handler
309
2553
@param rref_pointer_array a reference to ref_pointer_array of
310
2554
the top-level select_lex for this query
311
2555
@param tables list of all tables used in this query.
2729
Convert a subquery predicate into a TableList semi-join nest
2732
convert_subq_to_sj()
2733
parent_join Parent join, the one that has subq_pred in its WHERE/ON
2735
subq_pred Subquery predicate to be converted
2738
Convert a subquery predicate into a TableList semi-join nest. All the
2739
prerequisites are already checked, so the conversion is always successfull.
2741
Prepared Statements: the transformation is permanent:
2742
- Changes in TableList structures are naturally permanent
2743
- Item tree changes are performed on statement MEM_ROOT:
2744
= we activate statement MEM_ROOT
2745
= this function is called before the first fix_prepare_information
2748
This is intended because the criteria for subquery-to-sj conversion remain
2749
constant for the lifetime of the Prepared Statement.
2753
true Out of memory error
2756
bool convert_subq_to_sj(JOIN *parent_join, Item_in_subselect *subq_pred)
2758
Select_Lex *parent_lex= parent_join->select_lex;
2759
TableList *emb_tbl_nest= NULL;
2760
List<TableList> *emb_join_list= &parent_lex->top_join_list;
2761
Session *session= parent_join->session;
2764
1. Find out where to put the predicate into.
2765
Note: for "t1 LEFT JOIN t2" this will be t2, a leaf.
2767
if ((void*)subq_pred->expr_join_nest != (void*)1)
2769
if (subq_pred->expr_join_nest->nested_join)
2774
... [LEFT] JOIN ( ... ) ON (subquery AND whatever) ...
2776
The sj-nest will be inserted into the brackets nest.
2778
emb_tbl_nest= subq_pred->expr_join_nest;
2779
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2781
else if (!subq_pred->expr_join_nest->outer_join)
2786
... INNER JOIN tblX ON (subquery AND whatever) ...
2788
The sj-nest will be tblX's "sibling", i.e. another child of its
2789
parent. This is ok because tblX is joined as an inner join.
2791
emb_tbl_nest= subq_pred->expr_join_nest->embedding;
2793
emb_join_list= &emb_tbl_nest->nested_join->join_list;
2795
else if (!subq_pred->expr_join_nest->nested_join)
2797
TableList *outer_tbl= subq_pred->expr_join_nest;
2798
TableList *wrap_nest;
2802
... LEFT JOIN tbl ON (on_expr AND subq_pred) ...
2804
we'll need to convert it into:
2806
... LEFT JOIN ( tbl SJ (subq_tables) ) ON (on_expr AND subq_pred) ...
2808
|<----- wrap_nest ---->|
2810
Q: other subqueries may be pointing to this element. What to do?
2811
A1: simple solution: copy *subq_pred->expr_join_nest= *parent_nest.
2812
But we'll need to fix other pointers.
2813
A2: Another way: have TableList::next_ptr so the following
2814
subqueries know the table has been nested.
2815
A3: changes in the TableList::outer_join will make everything work
2818
if (!(wrap_nest= alloc_join_nest(parent_join->session)))
2822
wrap_nest->embedding= outer_tbl->embedding;
2823
wrap_nest->join_list= outer_tbl->join_list;
2824
wrap_nest->alias= (char*) "(sj-wrap)";
2826
wrap_nest->nested_join->join_list.empty();
2827
wrap_nest->nested_join->join_list.push_back(outer_tbl);
2829
outer_tbl->embedding= wrap_nest;
2830
outer_tbl->join_list= &wrap_nest->nested_join->join_list;
2833
wrap_nest will take place of outer_tbl, so move the outer join flag
2836
wrap_nest->outer_join= outer_tbl->outer_join;
2837
outer_tbl->outer_join= 0;
2839
wrap_nest->on_expr= outer_tbl->on_expr;
2840
outer_tbl->on_expr= NULL;
2842
List_iterator<TableList> li(*wrap_nest->join_list);
2846
if (tbl == outer_tbl)
2848
li.replace(wrap_nest);
2853
Ok now wrap_nest 'contains' outer_tbl and we're ready to add the
2854
semi-join nest into it
2856
emb_join_list= &wrap_nest->nested_join->join_list;
2857
emb_tbl_nest= wrap_nest;
2862
nested_join_st *nested_join;
2863
if (!(sj_nest= alloc_join_nest(parent_join->session)))
2867
nested_join= sj_nest->nested_join;
2869
sj_nest->join_list= emb_join_list;
2870
sj_nest->embedding= emb_tbl_nest;
2871
sj_nest->alias= (char*) "(sj-nest)";
2872
/* Nests do not participate in those 'chains', so: */
2873
/* sj_nest->next_leaf= sj_nest->next_local= sj_nest->next_global == NULL*/
2874
emb_join_list->push_back(sj_nest);
2877
nested_join->used_tables and nested_join->not_null_tables are
2878
initialized in simplify_joins().
2882
2. Walk through subquery's top list and set 'embedding' to point to the
2885
Select_Lex *subq_lex= subq_pred->unit->first_select();
2886
nested_join->join_list.empty();
2887
List_iterator_fast<TableList> li(subq_lex->top_join_list);
2888
TableList *tl, *last_leaf;
2891
tl->embedding= sj_nest;
2892
tl->join_list= &nested_join->join_list;
2893
nested_join->join_list.push_back(tl);
2897
Reconnect the next_leaf chain.
2898
TODO: Do we have to put subquery's tables at the end of the chain?
2899
Inserting them at the beginning would be a bit faster.
2900
NOTE: We actually insert them at the front! That's because the order is
2901
reversed in this list.
2903
for (tl= parent_lex->leaf_tables; tl->next_leaf; tl= tl->next_leaf) {};
2904
tl->next_leaf= subq_lex->leaf_tables;
2908
Same as above for next_local chain
2909
(a theory: a next_local chain always starts with ::leaf_tables
2910
because view's tables are inserted after the view)
2912
for (tl= parent_lex->leaf_tables; tl->next_local; tl= tl->next_local) {};
2913
tl->next_local= subq_lex->leaf_tables;
2915
/* A theory: no need to re-connect the next_global chain */
2917
/* 3. Remove the original subquery predicate from the WHERE/ON */
2919
// The subqueries were replaced for Item_int(1) earlier
2920
subq_pred->exec_method= Item_in_subselect::SEMI_JOIN; // for subsequent executions
2921
/*TODO: also reset the 'with_subselect' there. */
2923
/* n. Adjust the parent_join->tables counter */
2924
uint32_t table_no= parent_join->tables;
2925
/* n. Walk through child's tables and adjust table->map */
2926
for (tl= subq_lex->leaf_tables; tl; tl= tl->next_leaf, table_no++)
2928
tl->table->tablenr= table_no;
2929
tl->table->map= ((table_map)1) << table_no;
2930
Select_Lex *old_sl= tl->select_lex;
2931
tl->select_lex= parent_join->select_lex;
2932
for(TableList *emb= tl->embedding; emb && emb->select_lex == old_sl; emb= emb->embedding)
2933
emb->select_lex= parent_join->select_lex;
2935
parent_join->tables += subq_lex->join->tables;
2938
Put the subquery's WHERE into semi-join's sj_on_expr
2939
Add the subquery-induced equalities too.
2941
Select_Lex *save_lex= session->lex->current_select;
2942
session->lex->current_select=subq_lex;
2943
if (!subq_pred->left_expr->fixed &&
2944
subq_pred->left_expr->fix_fields(session, &subq_pred->left_expr))
2946
session->lex->current_select=save_lex;
2948
sj_nest->nested_join->sj_corr_tables= subq_pred->used_tables();
2949
sj_nest->nested_join->sj_depends_on= subq_pred->used_tables() |
2950
subq_pred->left_expr->used_tables();
2951
sj_nest->sj_on_expr= subq_lex->where;
2954
Create the IN-equalities and inject them into semi-join's ON expression.
2955
Additionally, for InsideOut strategy
2956
- Record the number of IN-equalities.
2957
- Create list of pointers to (oe1, ..., ieN). We'll need the list to
2958
see which of the expressions are bound and which are not (for those
2959
we'll produce a distinct stream of (ie_i1,...ie_ik).
2961
(TODO: can we just create a list of pointers and hope the expressions
2962
will not substitute themselves on fix_fields()? or we need to wrap
2963
them into Item_direct_view_refs and store pointers to those. The
2964
pointers to Item_direct_view_refs are guaranteed to be stable as
2965
Item_direct_view_refs doesn't substitute itself with anything in
2966
Item_direct_view_ref::fix_fields.
2968
sj_nest->sj_in_exprs= subq_pred->left_expr->cols();
2969
sj_nest->nested_join->sj_outer_expr_list.empty();
2971
if (subq_pred->left_expr->cols() == 1)
2973
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr);
2975
Item *item_eq= new Item_func_eq(subq_pred->left_expr,
2976
subq_lex->ref_pointer_array[0]);
2977
item_eq->name= (char*)subq_sj_cond_name;
2978
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2982
for (uint32_t i= 0; i < subq_pred->left_expr->cols(); i++)
2984
nested_join->sj_outer_expr_list.push_back(subq_pred->left_expr->
2987
new Item_func_eq(subq_pred->left_expr->element_index(i),
2988
subq_lex->ref_pointer_array[i]);
2989
item_eq->name= (char*)subq_sj_cond_name + (i % 64);
2990
sj_nest->sj_on_expr= and_items(sj_nest->sj_on_expr, item_eq);
2993
/* Fix the created equality and AND */
2994
sj_nest->sj_on_expr->fix_fields(parent_join->session, &sj_nest->sj_on_expr);
2997
Walk through sj nest's WHERE and ON expressions and call
2998
item->fix_table_changes() for all items.
3000
sj_nest->sj_on_expr->fix_after_pullout(parent_lex, &sj_nest->sj_on_expr);
3001
fix_list_after_tbl_changes(parent_lex, &sj_nest->nested_join->join_list);
3004
/* Unlink the child select_lex so it doesn't show up in EXPLAIN: */
3005
subq_lex->master_unit()->exclude_level();
3007
/* Inject sj_on_expr into the parent's WHERE or ON */
3010
emb_tbl_nest->on_expr= and_items(emb_tbl_nest->on_expr,
3011
sj_nest->sj_on_expr);
3012
emb_tbl_nest->on_expr->fix_fields(parent_join->session, &emb_tbl_nest->on_expr);
3016
/* Inject into the WHERE */
3017
parent_join->conds= and_items(parent_join->conds, sj_nest->sj_on_expr);
3018
parent_join->conds->fix_fields(parent_join->session, &parent_join->conds);
3019
parent_join->select_lex->where= parent_join->conds;
3027
Convert candidate subquery predicates to semi-joins
3030
JOIN::flatten_subqueries()
3033
Convert candidate subquery predicates to semi-joins.
3040
bool JOIN::flatten_subqueries()
3042
Item_in_subselect **in_subq;
3043
Item_in_subselect **in_subq_end;
3045
if (sj_subselects.elements() == 0)
3048
/* 1. Fix children subqueries */
3049
for (in_subq= sj_subselects.front(), in_subq_end= sj_subselects.back();
3050
in_subq != in_subq_end; in_subq++)
3052
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3053
child_join->outer_tables = child_join->tables;
3054
if (child_join->flatten_subqueries())
3056
(*in_subq)->sj_convert_priority=
3057
(*in_subq)->is_correlated * MAX_TABLES + child_join->outer_tables;
3060
bool outer_join_disable_semi_join= false;
3062
* Temporary measure: disable semi-joins when they are together with outer
3065
* @see LP Bug #314911
3067
for (TableList *tbl= select_lex->leaf_tables; tbl; tbl=tbl->next_leaf)
3069
TableList *embedding= tbl->embedding;
3070
if (tbl->on_expr || (tbl->embedding && !(embedding->sj_on_expr &&
3071
!embedding->embedding)))
3073
in_subq= sj_subselects.front();
3074
outer_join_disable_semi_join= true;
3078
if (! outer_join_disable_semi_join)
3081
2. Pick which subqueries to convert:
3082
sort the subquery array
3083
- prefer correlated subqueries over uncorrelated;
3084
- prefer subqueries that have greater number of outer tables;
3086
sj_subselects.sort(subq_sj_candidate_cmp);
3087
// #tables-in-parent-query + #tables-in-subquery < MAX_TABLES
3088
/* Replace all subqueries to be flattened with Item_int(1) */
3089
for (in_subq= sj_subselects.front();
3090
in_subq != in_subq_end &&
3091
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3094
if (replace_where_subcondition(this, *in_subq, new Item_int(1), false))
3098
for (in_subq= sj_subselects.front();
3099
in_subq != in_subq_end &&
3100
tables + ((*in_subq)->sj_convert_priority % MAX_TABLES) < MAX_TABLES;
3103
if (convert_subq_to_sj(this, *in_subq))
3108
/* 3. Finalize those we didn't convert */
3109
for (; in_subq!= in_subq_end; in_subq++)
3111
JOIN *child_join= (*in_subq)->unit->first_select()->join;
3112
Item_subselect::trans_res res;
3113
(*in_subq)->changed= 0;
3114
(*in_subq)->fixed= 0;
3115
res= (*in_subq)->select_transformer(child_join);
3116
if (res == Item_subselect::RES_ERROR)
3119
(*in_subq)->changed= 1;
3120
(*in_subq)->fixed= 1;
3122
Item *substitute= (*in_subq)->substitution;
3123
bool do_fix_fields= !(*in_subq)->substitution->fixed;
3124
if (replace_where_subcondition(this, *in_subq, substitute, do_fix_fields))
3127
//if ((*in_subq)->fix_fields(session, (*in_subq)->ref_ptr))
3130
sj_subselects.clear();
3135
Setup for execution all subqueries of a query, for which the optimizer
3136
chose hash semi-join.
3138
@details Iterate over all subqueries of the query, and if they are under an
3139
IN predicate, and the optimizer chose to compute it via hash semi-join:
3140
- try to initialize all data structures needed for the materialized execution
3141
of the IN predicate,
3142
- if this fails, then perform the IN=>EXISTS transformation which was
3143
previously blocked during JOIN::prepare.
3145
This method is part of the "code generation" query processing phase.
3147
This phase must be called after substitute_for_best_equal_field() because
3148
that function may replace items with other items from a multiple equality,
3149
and we need to reference the correct items in the index access method of the
3152
@return Operation status
3153
@retval false success.
3154
@retval true error occurred.
3156
bool JOIN::setup_subquery_materialization()
3158
for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
3159
un= un->next_unit())
3161
for (Select_Lex *sl= un->first_select(); sl; sl= sl->next_select())
3163
Item_subselect *subquery_predicate= sl->master_unit()->item;
3164
if (subquery_predicate &&
3165
subquery_predicate->substype() == Item_subselect::IN_SUBS)
3167
Item_in_subselect *in_subs= (Item_in_subselect*) subquery_predicate;
3168
if (in_subs->exec_method == Item_in_subselect::MATERIALIZATION &&
3169
in_subs->setup_engine())
3179
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3182
find_eq_ref_candidate()
3183
table Table to be checked
3184
sj_inner_tables Bitmap of inner tables. eq_ref(inner_table) doesn't
3188
Check if table's KEYUSE elements have an eq_ref(outer_tables) candidate
3191
Check again if it is feasible to factor common parts with constant table
3195
true - There exists an eq_ref(outer-tables) candidate
3199
bool find_eq_ref_candidate(Table *table, table_map sj_inner_tables)
3201
KEYUSE *keyuse= table->reginfo.join_tab->keyuse;
3206
while (1) /* For each key */
3209
KEY *keyinfo= table->key_info + key;
3210
key_part_map bound_parts= 0;
3211
if ((keyinfo->flags & HA_NOSAME) == HA_NOSAME)
3213
do /* For all equalities on all key parts */
3215
/* Check if this is "t.keypart = expr(outer_tables) */
3216
if (!(keyuse->used_tables & sj_inner_tables) &&
3217
!(keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL))
3219
bound_parts |= 1 << keyuse->keypart;
3222
} while (keyuse->key == key && keyuse->table == table);
3224
if (bound_parts == PREV_BITS(uint, keyinfo->key_parts))
3226
if (keyuse->table != table)
3234
if (keyuse->table != table)
3237
while (keyuse->key == key);
3246
Pull tables out of semi-join nests, if possible
3249
pull_out_semijoin_tables()
3250
join The join where to do the semi-join flattening
3253
Try to pull tables out of semi-join nests.
3256
When this function is called, the join may have several semi-join nests
3257
(possibly within different semi-join nests), but it is guaranteed that
3258
one semi-join nest does not contain another.
3261
A table can be pulled out of the semi-join nest if
3262
- It is a constant table
3266
* Pulled out tables have JOIN_TAB::emb_sj_nest == NULL (like the outer
3268
* Tables that were not pulled out have JOIN_TAB::emb_sj_nest.
3269
* Semi-join nests TableList::sj_inner_tables
3271
This operation is (and should be) performed at each PS execution since
3272
tables may become/cease to be constant across PS reexecutions.
3276
1 - Out of memory error
3279
int pull_out_semijoin_tables(JOIN *join)
3282
List_iterator<TableList> sj_list_it(join->select_lex->sj_nests);
3284
/* Try pulling out of the each of the semi-joins */
3285
while ((sj_nest= sj_list_it++))
3287
/* Action #1: Mark the constant tables to be pulled out */
3288
table_map pulled_tables= 0;
3290
List_iterator<TableList> child_li(sj_nest->nested_join->join_list);
3292
while ((tbl= child_li++))
3296
tbl->table->reginfo.join_tab->emb_sj_nest= sj_nest;
3297
if (tbl->table->map & join->const_table_map)
3299
pulled_tables |= tbl->table->map;
3305
Action #2: Find which tables we can pull out based on
3306
update_ref_and_keys() data. Note that pulling one table out can allow
3307
us to pull out some other tables too.
3309
bool pulled_a_table;
3312
pulled_a_table= false;
3314
while ((tbl= child_li++))
3316
if (tbl->table && !(pulled_tables & tbl->table->map))
3318
if (find_eq_ref_candidate(tbl->table,
3319
sj_nest->nested_join->used_tables &
3322
pulled_a_table= true;
3323
pulled_tables |= tbl->table->map;
3327
} while (pulled_a_table);
3330
if ((sj_nest)->nested_join->used_tables == pulled_tables)
3332
(sj_nest)->sj_inner_tables= 0;
3333
while ((tbl= child_li++))
3336
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
3341
/* Record the bitmap of inner tables, mark the inner tables */
3342
table_map inner_tables=(sj_nest)->nested_join->used_tables &
3344
(sj_nest)->sj_inner_tables= inner_tables;
3345
while ((tbl= child_li++))
3349
if (inner_tables & tbl->table->map)
3350
tbl->table->reginfo.join_tab->emb_sj_nest= (sj_nest);
3352
tbl->table->reginfo.join_tab->emb_sj_nest= NULL;
462
3360
/*****************************************************************************
463
Create JoinTableS, make a guess about the table types,
3361
Create JOIN_TABS, make a guess about the table types,
464
3362
Approximate how many records will be used in each table
465
3363
*****************************************************************************/
466
ha_rows get_quick_record_count(Session *session, optimizer::SqlSelect *select, Table *table, const key_map *keys,ha_rows limit)
3366
static ha_rows get_quick_record_count(Session *session, SQL_SELECT *select,
3368
const key_map *keys,ha_rows limit)
469
3371
if (check_stack_overrun(session, STACK_MIN_SIZE, NULL))
484
3386
return(HA_POS_ERROR); /* This shouldn't happend */
3390
This structure is used to collect info on potentially sargable
3391
predicates in order to check whether they become sargable after
3392
reading const tables.
3393
We form a bitmap of indexes that can be used for sargable predicates.
3394
Only such indexes are involved in range analysis.
3396
typedef struct st_sargable_param
3398
Field *field; /* field against which to check sargability */
3399
Item **arg_value; /* values of potential keys for lookups */
3400
uint32_t num_values; /* number of values in the above array */
3404
Calculate the best possible join and initialize the join structure.
3413
make_join_statistics(JOIN *join, TableList *tables, COND *conds,
3414
DYNAMIC_ARRAY *keyuse_array)
3418
uint32_t i,table_count,const_count,key;
3419
table_map found_const_table_map, all_table_map, found_ref, refs;
3420
key_map const_ref, eq_part;
3421
Table **table_vector;
3422
JOIN_TAB *stat,*stat_end,*s,**stat_ref;
3423
KEYUSE *keyuse,*start_keyuse;
3424
table_map outer_join=0;
3425
SARGABLE_PARAM *sargables= 0;
3426
JOIN_TAB *stat_vector[MAX_TABLES+1];
3428
table_count=join->tables;
3429
stat=(JOIN_TAB*) join->session->calloc(sizeof(JOIN_TAB)*table_count);
3430
stat_ref=(JOIN_TAB**) join->session->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
3431
table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
3432
if (!stat || !stat_ref || !table_vector)
3433
return(1); // Eom /* purecov: inspected */
3435
join->best_ref=stat_vector;
3437
stat_end=stat+table_count;
3438
found_const_table_map= all_table_map=0;
3443
s++, tables= tables->next_leaf, i++)
3445
TableList *embedding= tables->embedding;
3448
s->const_keys.init();
3449
s->checked_keys.init();
3450
s->needed_reg.init();
3451
table_vector[i]=s->table=table=tables->table;
3452
table->pos_in_table_list= tables;
3453
error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
3456
table->file->print_error(error, MYF(0));
3459
table->quick_keys.clear_all();
3460
table->reginfo.join_tab=s;
3461
table->reginfo.not_exists_optimize=0;
3462
memset(table->const_key_parts, 0,
3463
sizeof(key_part_map)*table->s->keys);
3464
all_table_map|= table->map;
3466
s->info=0; // For describe
3468
s->dependent= tables->dep_tables;
3469
s->key_dependent= 0;
3470
if (tables->schema_table)
3471
table->file->stats.records= 2;
3472
table->quick_condition_rows= table->file->stats.records;
3474
s->on_expr_ref= &tables->on_expr;
3475
if (*s->on_expr_ref)
3477
/* s is the only inner table of an outer join */
3478
if (!table->file->stats.records && !embedding)
3480
s->dependent= 0; // Ignore LEFT JOIN depend.
3481
set_position(join,const_count++,s,(KEYUSE*) 0);
3484
outer_join|= table->map;
3485
s->embedding_map= 0;
3486
for (;embedding; embedding= embedding->embedding)
3487
s->embedding_map|= embedding->nested_join->nj_map;
3490
if (embedding && !(embedding->sj_on_expr && ! embedding->embedding))
3492
/* s belongs to a nested join, maybe to several embedded joins */
3493
s->embedding_map= 0;
3496
nested_join_st *nested_join= embedding->nested_join;
3497
s->embedding_map|=nested_join->nj_map;
3498
s->dependent|= embedding->dep_tables;
3499
embedding= embedding->embedding;
3500
outer_join|= nested_join->used_tables;
3505
if ((table->file->stats.records <= 1) &&
3507
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && !join->no_const_tables)
3509
set_position(join,const_count++,s,(KEYUSE*) 0);
3513
join->outer_join=outer_join;
3515
if (join->outer_join)
3518
Build transitive closure for relation 'to be dependent on'.
3519
This will speed up the plan search for many cases with outer joins,
3520
as well as allow us to catch illegal cross references/
3521
Warshall's algorithm is used to build the transitive closure.
3522
As we use bitmaps to represent the relation the complexity
3523
of the algorithm is O((number of tables)^2).
3525
for (i= 0, s= stat ; i < table_count ; i++, s++)
3527
for (uint32_t j= 0 ; j < table_count ; j++)
3529
table= stat[j].table;
3530
if (s->dependent & table->map)
3531
s->dependent |= table->reginfo.join_tab->dependent;
3534
s->table->maybe_null= 1;
3536
/* Catch illegal cross references for outer joins */
3537
for (i= 0, s= stat ; i < table_count ; i++, s++)
3539
if (s->dependent & s->table->map)
3541
join->tables=0; // Don't use join->table
3542
my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
3545
s->key_dependent= s->dependent;
3549
if (conds || outer_join)
3550
if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
3551
conds, join->cond_equal,
3552
~outer_join, join->select_lex, &sargables))
3555
/* Read tables with 0 or 1 rows (system tables) */
3556
join->const_table_map= 0;
3558
for (POSITION *p_pos=join->positions, *p_end=p_pos+const_count;
3565
join->const_table_map|=s->table->map;
3566
if ((tmp=join_read_const_table(s, p_pos)))
3569
return(1); // Fatal error
3572
found_const_table_map|= s->table->map;
3575
/* loop until no more const tables are found */
3579
more_const_tables_found:
3584
We only have to loop from stat_vector + const_count as
3585
set_position() will move all const_tables first in stat_vector
3588
for (JOIN_TAB **pos=stat_vector+const_count ; (s= *pos) ; pos++)
3593
If equi-join condition by a key is null rejecting and after a
3594
substitution of a const table the key value happens to be null
3595
then we can state that there are no matches for this equi-join.
3597
if ((keyuse= s->keyuse) && *s->on_expr_ref && !s->embedding_map)
3600
When performing an outer join operation if there are no matching rows
3601
for the single row of the outer table all the inner tables are to be
3602
null complemented and thus considered as constant tables.
3603
Here we apply this consideration to the case of outer join operations
3604
with a single inner table only because the case with nested tables
3605
would require a more thorough analysis.
3606
TODO. Apply single row substitution to null complemented inner tables
3607
for nested outer join operations.
3609
while (keyuse->table == table)
3611
if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
3612
keyuse->val->is_null() && keyuse->null_rejecting)
3615
table->mark_as_null_row();
3616
found_const_table_map|= table->map;
3617
join->const_table_map|= table->map;
3618
set_position(join,const_count++,s,(KEYUSE*) 0);
3619
goto more_const_tables_found;
3625
if (s->dependent) // If dependent on some table
3627
// All dep. must be constants
3628
if (s->dependent & ~(found_const_table_map))
3630
if (table->file->stats.records <= 1L &&
3631
(table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
3632
!table->pos_in_table_list->embedding)
3636
join->const_table_map|=table->map;
3637
set_position(join,const_count++,s,(KEYUSE*) 0);
3638
if ((tmp= join_read_const_table(s, join->positions+const_count-1)))
3641
return(1); // Fatal error
3644
found_const_table_map|= table->map;
3648
/* check if table can be read by key or table only uses const refs */
3649
if ((keyuse=s->keyuse))
3652
while (keyuse->table == table)
3654
start_keyuse=keyuse;
3656
s->keys.set_bit(key); // QQ: remove this ?
3659
const_ref.clear_all();
3660
eq_part.clear_all();
3663
if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
3665
if (!((~found_const_table_map) & keyuse->used_tables))
3666
const_ref.set_bit(keyuse->keypart);
3668
refs|=keyuse->used_tables;
3669
eq_part.set_bit(keyuse->keypart);
3672
} while (keyuse->table == table && keyuse->key == key);
3674
if (eq_part.is_prefix(table->key_info[key].key_parts) &&
3675
!table->pos_in_table_list->embedding)
3677
if ((table->key_info[key].flags & (HA_NOSAME))
3680
if (const_ref == eq_part)
3681
{ // Found everything for ref.
3685
join->const_table_map|=table->map;
3686
set_position(join,const_count++,s,start_keyuse);
3687
if (create_ref_for_key(join, s, start_keyuse,
3688
found_const_table_map))
3690
if ((tmp=join_read_const_table(s,
3691
join->positions+const_count-1)))
3694
return(1); // Fatal error
3697
found_const_table_map|= table->map;
3701
found_ref|= refs; // Table is const if all refs are const
3703
else if (const_ref == eq_part)
3704
s->const_keys.set_bit(key);
3709
} while (join->const_table_map & found_ref && ref_changed);
3712
Update info on indexes that can be used for search lookups as
3713
reading const tables may has added new sargable predicates.
3715
if (const_count && sargables)
3717
for( ; sargables->field ; sargables++)
3719
Field *field= sargables->field;
3720
JOIN_TAB *join_tab= field->table->reginfo.join_tab;
3721
key_map possible_keys= field->key_start;
3722
possible_keys.intersect(field->table->keys_in_use_for_query);
3724
for (uint32_t j=0; j < sargables->num_values; j++)
3725
is_const&= sargables->arg_value[j]->const_item();
3727
join_tab[0].const_keys.merge(possible_keys);
3731
if (pull_out_semijoin_tables(join))
3734
/* Calc how many (possible) matched records in each table */
3736
for (s=stat ; s < stat_end ; s++)
3738
if (s->type == JT_SYSTEM || s->type == JT_CONST)
3740
/* Only one matching row */
3741
s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
3744
/* Approximate found rows and time to read them */
3745
s->found_records=s->records=s->table->file->stats.records;
3746
s->read_time=(ha_rows) s->table->file->scan_time();
3749
Set a max range of how many seeks we can expect when using keys
3750
This is can't be to high as otherwise we are likely to use
3753
s->worst_seeks= cmin((double) s->found_records / 10,
3754
(double) s->read_time*3);
3755
if (s->worst_seeks < 2.0) // Fix for small tables
3759
Add to stat->const_keys those indexes for which all group fields or
3760
all select distinct fields participate in one index.
3762
add_group_and_distinct_keys(join, s);
3764
if (!s->const_keys.is_clear_all() &&
3765
!s->table->pos_in_table_list->embedding)
3769
select= make_select(s->table, found_const_table_map,
3770
found_const_table_map,
3771
*s->on_expr_ref ? *s->on_expr_ref : conds,
3775
records= get_quick_record_count(join->session, select, s->table,
3776
&s->const_keys, join->row_limit);
3777
s->quick=select->quick;
3778
s->needed_reg=select->needed_reg;
3780
if (records == 0 && s->table->reginfo.impossible_range)
3783
Impossible WHERE or ON expression
3784
In case of ON, we mark that the we match one empty NULL row.
3785
In case of WHERE, don't set found_const_table_map to get the
3786
caller to abort with a zero row result.
3788
join->const_table_map|= s->table->map;
3789
set_position(join,const_count++,s,(KEYUSE*) 0);
3791
if (*s->on_expr_ref)
3793
/* Generate empty row */
3794
s->info= "Impossible ON condition";
3795
found_const_table_map|= s->table->map;
3797
s->table->mark_as_null_row(); // All fields are NULL
3800
if (records != HA_POS_ERROR)
3802
s->found_records=records;
3803
s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
3809
join->join_tab=stat;
3810
join->map2table=stat_ref;
3811
join->table= join->all_tables=table_vector;
3812
join->const_tables=const_count;
3813
join->found_const_table_map=found_const_table_map;
3815
/* Find an optimal join order of the non-constant tables. */
3816
if (join->const_tables != join->tables)
3818
optimize_keyuse(join, keyuse_array);
3819
if (choose_plan(join, all_table_map & ~join->const_table_map))
3824
memcpy(join->best_positions, join->positions,
3825
sizeof(POSITION)*join->const_tables);
3826
join->best_read=1.0;
3828
/* Generate an execution plan from the found optimal join order. */
3829
return(join->session->killed || get_best_combination(join));
487
3833
/*****************************************************************************
488
3834
Check with keys are used and with tables references with tables
489
3835
Updates in stat:
492
3838
keyuse Pointer to possible keys
493
3839
*****************************************************************************/
3841
/// Used when finding key fields
3842
typedef struct key_field_t {
3844
Item *val; ///< May be empty if diff constant
3846
uint optimize; // KEY_OPTIMIZE_*
3849
If true, the condition this struct represents will not be satisfied
3852
bool null_rejecting;
3853
bool *cond_guard; /* See KEYUSE::cond_guard */
3854
uint32_t sj_pred_no; /* See KEYUSE::sj_pred_no */
3858
Merge new key definitions to old ones, remove those not used in both.
3860
This is called for OR between different levels.
3862
To be able to do 'ref_or_null' we merge a comparison of a column
3863
and 'column IS NULL' to one test. This is useful for sub select queries
3864
that are internally transformed to something like:.
3867
SELECT * FROM t1 WHERE t1.key=outer_ref_field or t1.key IS NULL
3870
KEY_FIELD::null_rejecting is processed as follows: @n
3871
result has null_rejecting=true if it is set for both ORed references.
3873
- (t2.key = t1.field OR t2.key = t1.field) -> null_rejecting=true
3874
- (t2.key = t1.field OR t2.key <=> t1.field) -> null_rejecting=false
3877
The result of this is that we're missing some 'ref' accesses.
3878
OptimizerTeam: Fix this
3882
merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
3885
if (start == new_fields)
3886
return start; // Impossible or
3887
if (new_fields == end)
3888
return start; // No new fields, skip all
3890
KEY_FIELD *first_free=new_fields;
3892
/* Mark all found fields in old array */
3893
for (; new_fields != end ; new_fields++)
3895
for (KEY_FIELD *old=start ; old != first_free ; old++)
3897
if (old->field == new_fields->field)
3900
NOTE: below const_item() call really works as "!used_tables()", i.e.
3901
it can return false where it is feasible to make it return true.
3903
The cause is as follows: Some of the tables are already known to be
3904
const tables (the detection code is in make_join_statistics(),
3905
above the update_ref_and_keys() call), but we didn't propagate
3906
information about this: Table::const_table is not set to true, and
3907
Item::update_used_tables() hasn't been called for each item.
3908
The result of this is that we're missing some 'ref' accesses.
3909
TODO: OptimizerTeam: Fix this
3911
if (!new_fields->val->const_item())
3914
If the value matches, we can use the key reference.
3915
If not, we keep it until we have examined all new values
3917
if (old->val->eq(new_fields->val, old->field->binary()))
3919
old->level= and_level;
3920
old->optimize= ((old->optimize & new_fields->optimize &
3921
KEY_OPTIMIZE_EXISTS) |
3922
((old->optimize | new_fields->optimize) &
3923
KEY_OPTIMIZE_REF_OR_NULL));
3924
old->null_rejecting= (old->null_rejecting &&
3925
new_fields->null_rejecting);
3928
else if (old->eq_func && new_fields->eq_func &&
3929
old->val->eq_by_collation(new_fields->val,
3930
old->field->binary(),
3931
old->field->charset()))
3934
old->level= and_level;
3935
old->optimize= ((old->optimize & new_fields->optimize &
3936
KEY_OPTIMIZE_EXISTS) |
3937
((old->optimize | new_fields->optimize) &
3938
KEY_OPTIMIZE_REF_OR_NULL));
3939
old->null_rejecting= (old->null_rejecting &&
3940
new_fields->null_rejecting);
3942
else if (old->eq_func && new_fields->eq_func &&
3943
((old->val->const_item() && old->val->is_null()) ||
3944
new_fields->val->is_null()))
3946
/* field = expression OR field IS NULL */
3947
old->level= and_level;
3948
old->optimize= KEY_OPTIMIZE_REF_OR_NULL;
3950
Remember the NOT NULL value unless the value does not depend
3953
if (!old->val->used_tables() && old->val->is_null())
3954
old->val= new_fields->val;
3955
/* The referred expression can be NULL: */
3956
old->null_rejecting= 0;
3961
We are comparing two different const. In this case we can't
3962
use a key-lookup on this so it's better to remove the value
3963
and let the range optimzier handle it
3965
if (old == --first_free) // If last item
3967
*old= *first_free; // Remove old value
3968
old--; // Retry this value
3973
/* Remove all not used items */
3974
for (KEY_FIELD *old=start ; old != first_free ;)
3976
if (old->level != and_level)
3977
{ // Not used in all levels
3978
if (old == --first_free)
3980
*old= *first_free; // Remove old value
3990
Add a possible key to array of possible keys if it's usable as a key
3992
@param key_fields Pointer to add key, if usable
3993
@param and_level And level, to be stored in KEY_FIELD
3994
@param cond Condition predicate
3995
@param field Field used in comparision
3996
@param eq_func True if we used =, <=> or IS NULL
3997
@param value Value used for comparison with field
3998
@param usable_tables Tables which can be used for key optimization
3999
@param sargables IN/OUT Array of found sargable candidates
4002
If we are doing a NOT NULL comparison on a NOT NULL field in a outer join
4003
table, we store this to be able to do not exists optimization later.
4006
*key_fields is incremented if we stored a key in the array
4010
add_key_field(KEY_FIELD **key_fields,uint32_t and_level, Item_func *cond,
4011
Field *field, bool eq_func, Item **value, uint32_t num_values,
4012
table_map usable_tables, SARGABLE_PARAM **sargables)
4014
uint32_t exists_optimize= 0;
4015
if (!(field->flags & PART_KEY_FLAG))
4017
// Don't remove column IS NULL on a LEFT JOIN table
4018
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4019
!field->table->maybe_null || field->null_ptr)
4020
return; // Not a key. Skip it
4021
exists_optimize= KEY_OPTIMIZE_EXISTS;
4022
assert(num_values == 1);
4026
table_map used_tables=0;
4028
for (uint32_t i=0; i<num_values; i++)
4030
used_tables|=(value[i])->used_tables();
4031
if (!((value[i])->used_tables() & (field->table->map | RAND_TABLE_BIT)))
4036
if (!(usable_tables & field->table->map))
4038
if (!eq_func || (*value)->type() != Item::NULL_ITEM ||
4039
!field->table->maybe_null || field->null_ptr)
4040
return; // Can't use left join optimize
4041
exists_optimize= KEY_OPTIMIZE_EXISTS;
4045
JOIN_TAB *stat=field->table->reginfo.join_tab;
4046
key_map possible_keys=field->key_start;
4047
possible_keys.intersect(field->table->keys_in_use_for_query);
4048
stat[0].keys.merge(possible_keys); // Add possible keys
4051
Save the following cases:
4053
Field LIKE constant where constant doesn't start with a wildcard
4054
Field = field2 where field2 is in a different table
4061
stat[0].key_dependent|=used_tables;
4064
for (uint32_t i=0; i<num_values; i++)
4066
if (!(is_const&= value[i]->const_item()))
4070
stat[0].const_keys.merge(possible_keys);
4074
Save info to be able check whether this predicate can be
4075
considered as sargable for range analisis after reading const tables.
4076
We do not save info about equalities as update_const_equal_items
4077
will take care of updating info on keys from sargable equalities.
4080
(*sargables)->field= field;
4081
(*sargables)->arg_value= value;
4082
(*sargables)->num_values= num_values;
4085
We can't always use indexes when comparing a string index to a
4086
number. cmp_type() is checked to allow compare of dates to numbers.
4087
eq_func is NEVER true when num_values > 1
4092
Additional optimization: if we're processing
4093
"t.key BETWEEN c1 AND c1" then proceed as if we were processing
4095
TODO: This is a very limited fix. A more generic fix is possible.
4096
There are 2 options:
4097
A) Make equality propagation code be able to handle BETWEEN
4098
(including cases like t1.key BETWEEN t2.key AND t3.key)
4099
B) Make range optimizer to infer additional "t.key = c" equalities
4100
and use them in equality propagation process (see details in
4103
if ((cond->functype() != Item_func::BETWEEN) ||
4104
((Item_func_between*) cond)->negated ||
4105
!value[0]->eq(value[1], field->binary()))
4110
if (field->result_type() == STRING_RESULT)
4112
if ((*value)->result_type() != STRING_RESULT)
4114
if (field->cmp_type() != (*value)->result_type())
4120
We can't use indexes if the effective collation
4121
of the operation differ from the field collation.
4123
if (field->cmp_type() == STRING_RESULT &&
4124
((Field_str*)field)->charset() != cond->compare_collation())
4131
For the moment eq_func is always true. This slot is reserved for future
4132
extensions where we want to remembers other things than just eq comparisons
4135
/* Store possible eq field */
4136
(*key_fields)->field= field;
4137
(*key_fields)->eq_func= eq_func;
4138
(*key_fields)->val= *value;
4139
(*key_fields)->level= and_level;
4140
(*key_fields)->optimize= exists_optimize;
4142
If the condition has form "tbl.keypart = othertbl.field" and
4143
othertbl.field can be NULL, there will be no matches if othertbl.field
4145
We use null_rejecting in add_not_null_conds() to add
4146
'othertbl.field IS NOT NULL' to tab->select_cond.
4148
(*key_fields)->null_rejecting= ((cond->functype() == Item_func::EQ_FUNC ||
4149
cond->functype() == Item_func::MULT_EQUAL_FUNC) &&
4150
((*value)->type() == Item::FIELD_ITEM) &&
4151
((Item_field*)*value)->field->maybe_null());
4152
(*key_fields)->cond_guard= NULL;
4153
(*key_fields)->sj_pred_no= (cond->name >= subq_sj_cond_name &&
4154
cond->name < subq_sj_cond_name + 64)?
4155
cond->name - subq_sj_cond_name: UINT_MAX;
4160
Add possible keys to array of possible keys originated from a simple
4163
@param key_fields Pointer to add key, if usable
4164
@param and_level And level, to be stored in KEY_FIELD
4165
@param cond Condition predicate
4166
@param field Field used in comparision
4167
@param eq_func True if we used =, <=> or IS NULL
4168
@param value Value used for comparison with field
4169
Is NULL for BETWEEN and IN
4170
@param usable_tables Tables which can be used for key optimization
4171
@param sargables IN/OUT Array of found sargable candidates
4174
If field items f1 and f2 belong to the same multiple equality and
4175
a key is added for f1, the the same key is added for f2.
4178
*key_fields is incremented if we stored a key in the array
4182
add_key_equal_fields(KEY_FIELD **key_fields, uint32_t and_level,
4183
Item_func *cond, Item_field *field_item,
4184
bool eq_func, Item **val,
4185
uint32_t num_values, table_map usable_tables,
4186
SARGABLE_PARAM **sargables)
4188
Field *field= field_item->field;
4189
add_key_field(key_fields, and_level, cond, field,
4190
eq_func, val, num_values, usable_tables, sargables);
4191
Item_equal *item_equal= field_item->item_equal;
4195
Add to the set of possible key values every substitution of
4196
the field for an equal field included into item_equal
4198
Item_equal_iterator it(*item_equal);
4200
while ((item= it++))
4202
if (!field->eq(item->field))
4204
add_key_field(key_fields, and_level, cond, item->field,
4205
eq_func, val, num_values, usable_tables,
4213
add_key_fields(JOIN *join, KEY_FIELD **key_fields, uint32_t *and_level,
4214
COND *cond, table_map usable_tables,
4215
SARGABLE_PARAM **sargables)
4217
if (cond->type() == Item_func::COND_ITEM)
4219
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
4220
KEY_FIELD *org_key_fields= *key_fields;
4222
if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
4226
add_key_fields(join, key_fields, and_level, item, usable_tables,
4228
for (; org_key_fields != *key_fields ; org_key_fields++)
4229
org_key_fields->level= *and_level;
4234
add_key_fields(join, key_fields, and_level, li++, usable_tables,
4239
KEY_FIELD *start_key_fields= *key_fields;
4241
add_key_fields(join, key_fields, and_level, item, usable_tables,
4243
*key_fields=merge_key_fields(org_key_fields,start_key_fields,
4244
*key_fields,++(*and_level));
4251
Subquery optimization: Conditions that are pushed down into subqueries
4252
are wrapped into Item_func_trig_cond. We process the wrapped condition
4253
but need to set cond_guard for KEYUSE elements generated from it.
4256
if (cond->type() == Item::FUNC_ITEM &&
4257
((Item_func*)cond)->functype() == Item_func::TRIG_COND_FUNC)
4259
Item *cond_arg= ((Item_func*)cond)->arguments()[0];
4260
if (!join->group_list && !join->order &&
4262
join->unit->item->substype() == Item_subselect::IN_SUBS &&
4263
!join->unit->is_union())
4265
KEY_FIELD *save= *key_fields;
4266
add_key_fields(join, key_fields, and_level, cond_arg, usable_tables,
4268
// Indicate that this ref access candidate is for subquery lookup:
4269
for (; save != *key_fields; save++)
4270
save->cond_guard= ((Item_func_trig_cond*)cond)->get_trig_var();
4276
/* If item is of type 'field op field/constant' add it to key_fields */
4277
if (cond->type() != Item::FUNC_ITEM)
4279
Item_func *cond_func= (Item_func*) cond;
4280
switch (cond_func->select_optimize()) {
4281
case Item_func::OPTIMIZE_NONE:
4283
case Item_func::OPTIMIZE_KEY:
4287
if (cond_func->key_item()->real_item()->type() == Item::FIELD_ITEM &&
4288
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4290
values= cond_func->arguments()+1;
4291
if (cond_func->functype() == Item_func::NE_FUNC &&
4292
cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4293
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4295
assert(cond_func->functype() != Item_func::IN_FUNC ||
4296
cond_func->argument_count() != 2);
4297
add_key_equal_fields(key_fields, *and_level, cond_func,
4298
(Item_field*) (cond_func->key_item()->real_item()),
4300
cond_func->argument_count()-1,
4301
usable_tables, sargables);
4303
if (cond_func->functype() == Item_func::BETWEEN)
4305
values= cond_func->arguments();
4306
for (uint32_t i= 1 ; i < cond_func->argument_count() ; i++)
4308
Item_field *field_item;
4309
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM
4311
!(cond_func->arguments()[i]->used_tables() & OUTER_REF_TABLE_BIT))
4313
field_item= (Item_field *) (cond_func->arguments()[i]->real_item());
4314
add_key_equal_fields(key_fields, *and_level, cond_func,
4315
field_item, 0, values, 1, usable_tables,
4322
case Item_func::OPTIMIZE_OP:
4324
bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
4325
cond_func->functype() == Item_func::EQUAL_FUNC);
4327
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4328
!(cond_func->arguments()[0]->used_tables() & OUTER_REF_TABLE_BIT))
4330
add_key_equal_fields(key_fields, *and_level, cond_func,
4331
(Item_field*) (cond_func->arguments()[0])->real_item(),
4333
cond_func->arguments()+1, 1, usable_tables,
4336
if (cond_func->arguments()[1]->real_item()->type() == Item::FIELD_ITEM &&
4337
cond_func->functype() != Item_func::LIKE_FUNC &&
4338
!(cond_func->arguments()[1]->used_tables() & OUTER_REF_TABLE_BIT))
4340
add_key_equal_fields(key_fields, *and_level, cond_func,
4341
(Item_field*) (cond_func->arguments()[1])->real_item(),
4343
cond_func->arguments(),1,usable_tables,
4348
case Item_func::OPTIMIZE_NULL:
4349
/* column_name IS [NOT] NULL */
4350
if (cond_func->arguments()[0]->real_item()->type() == Item::FIELD_ITEM &&
4351
!(cond_func->used_tables() & OUTER_REF_TABLE_BIT))
4353
Item *tmp=new Item_null;
4354
if (unlikely(!tmp)) // Should never be true
4356
add_key_equal_fields(key_fields, *and_level, cond_func,
4357
(Item_field*) (cond_func->arguments()[0])->real_item(),
4358
cond_func->functype() == Item_func::ISNULL_FUNC,
4359
&tmp, 1, usable_tables, sargables);
4362
case Item_func::OPTIMIZE_EQUAL:
4363
Item_equal *item_equal= (Item_equal *) cond;
4364
Item *const_item= item_equal->get_const();
4365
Item_equal_iterator it(*item_equal);
4370
For each field field1 from item_equal consider the equality
4371
field1=const_item as a condition allowing an index access of the table
4372
with field1 by the keys value of field1.
4374
while ((item= it++))
4376
add_key_field(key_fields, *and_level, cond_func, item->field,
4377
true, &const_item, 1, usable_tables, sargables);
4383
Consider all pairs of different fields included into item_equal.
4384
For each of them (field1, field1) consider the equality
4385
field1=field2 as a condition allowing an index access of the table
4386
with field1 by the keys value of field2.
4388
Item_equal_iterator fi(*item_equal);
4389
while ((item= fi++))
4391
Field *field= item->field;
4392
while ((item= it++))
4394
if (!field->eq(item->field))
4396
add_key_field(key_fields, *and_level, cond_func, field,
4397
true, (Item **) &item, 1, usable_tables,
497
4409
Add all keys with uses 'field' for some keypart.
499
4411
If field->and_level != and_level then only mark key_part as const_part.
501
uint32_t max_part_bit(key_part_map bits)
4415
max_part_bit(key_part_map bits)
504
4418
for (found=0; bits & 1 ; found++,bits>>=1) ;
508
static int sort_keyuse(optimizer::KeyUse *a, optimizer::KeyUse *b)
4423
add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
4425
Field *field=key_field->field;
4426
Table *form= field->table;
4429
if (key_field->eq_func && !(key_field->optimize & KEY_OPTIMIZE_EXISTS))
4431
for (uint32_t key= 0 ; key < form->sizeKeys() ; key++)
4433
if (!(form->keys_in_use_for_query.is_set(key)))
4436
uint32_t key_parts= (uint32_t) form->key_info[key].key_parts;
4437
for (uint32_t part=0 ; part < key_parts ; part++)
4439
if (field->eq(form->key_info[key].key_part[part].field))
4441
keyuse.table= field->table;
4442
keyuse.val = key_field->val;
4444
keyuse.keypart=part;
4445
keyuse.keypart_map= (key_part_map) 1 << part;
4446
keyuse.used_tables=key_field->val->used_tables();
4447
keyuse.optimize= key_field->optimize & KEY_OPTIMIZE_REF_OR_NULL;
4448
keyuse.null_rejecting= key_field->null_rejecting;
4449
keyuse.cond_guard= key_field->cond_guard;
4450
keyuse.sj_pred_no= key_field->sj_pred_no;
4451
insert_dynamic(keyuse_array,(unsigned char*) &keyuse);
4459
sort_keyuse(KEYUSE *a,KEYUSE *b)
511
if (a->getTable()->tablenr != b->getTable()->tablenr)
512
return static_cast<int>((a->getTable()->tablenr - b->getTable()->tablenr));
513
if (a->getKey() != b->getKey())
514
return static_cast<int>((a->getKey() - b->getKey()));
515
if (a->getKeypart() != b->getKeypart())
516
return static_cast<int>((a->getKeypart() - b->getKeypart()));
4462
if (a->table->tablenr != b->table->tablenr)
4463
return (int) (a->table->tablenr - b->table->tablenr);
4464
if (a->key != b->key)
4465
return (int) (a->key - b->key);
4466
if (a->keypart != b->keypart)
4467
return (int) (a->keypart - b->keypart);
517
4468
// Place const values before other ones
518
if ((res= test((a->getUsedTables() & ~OUTER_REF_TABLE_BIT)) -
519
test((b->getUsedTables() & ~OUTER_REF_TABLE_BIT))))
4469
if ((res= test((a->used_tables & ~OUTER_REF_TABLE_BIT)) -
4470
test((b->used_tables & ~OUTER_REF_TABLE_BIT))))
521
4472
/* Place rows that are not 'OPTIMIZE_REF_OR_NULL' first */
522
return static_cast<int>(((a->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL) -
523
(b->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)));
4473
return (int) ((a->optimize & KEY_OPTIMIZE_REF_OR_NULL) -
4474
(b->optimize & KEY_OPTIMIZE_REF_OR_NULL));
4479
Add to KEY_FIELD array all 'ref' access candidates within nested join.
4481
This function populates KEY_FIELD array with entries generated from the
4482
ON condition of the given nested join, and does the same for nested joins
4483
contained within this nested join.
4485
@param[in] nested_join_table Nested join pseudo-table to process
4486
@param[in,out] end End of the key field array
4487
@param[in,out] and_level And-level
4488
@param[in,out] sargables Array of found sargable candidates
4492
We can add accesses to the tables that are direct children of this nested
4493
join (1), and are not inner tables w.r.t their neighbours (2).
4495
Example for #1 (outer brackets pair denotes nested join this function is
4498
... LEFT JOIN (t1 LEFT JOIN (t2 ... ) ) ON cond
4502
... LEFT JOIN (t1 LEFT JOIN t2 ) ON cond
4504
In examples 1-2 for condition cond, we can add 'ref' access candidates to
4508
... LEFT JOIN (t1, t2 LEFT JOIN t3 ON inner_cond) ON cond
4510
Here we can add 'ref' access candidates for t1 and t2, but not for t3.
4513
static void add_key_fields_for_nj(JOIN *join, TableList *nested_join_table,
4514
KEY_FIELD **end, uint32_t *and_level,
4515
SARGABLE_PARAM **sargables)
4517
List_iterator<TableList> li(nested_join_table->nested_join->join_list);
4518
List_iterator<TableList> li2(nested_join_table->nested_join->join_list);
4519
bool have_another = false;
4520
table_map tables= 0;
4522
assert(nested_join_table->nested_join);
4524
while ((table= li++) || (have_another && (li=li2, have_another=false,
4527
if (table->nested_join)
4529
if (!table->on_expr)
4531
/* It's a semi-join nest. Walk into it as if it wasn't a nest */
4534
li= List_iterator<TableList>(table->nested_join->join_list);
4537
add_key_fields_for_nj(join, table, end, and_level, sargables);
4540
if (!table->on_expr)
4541
tables |= table->table->map;
4543
if (nested_join_table->on_expr)
4544
add_key_fields(join, end, and_level, nested_join_table->on_expr, tables,
779
4808
/* Intersect the keys of all group fields. */
780
4809
cur_item= indexed_fields_it++;
781
possible_keys|= cur_item->field->part_of_key;
4810
possible_keys.merge(cur_item->field->part_of_key);
782
4811
while ((cur_item= indexed_fields_it++))
784
possible_keys&= cur_item->field->part_of_key;
787
if (possible_keys.any())
788
join_tab->const_keys|= possible_keys;
792
Compare two JoinTable objects based on the number of accessed records.
794
@param ptr1 pointer to first JoinTable object
795
@param ptr2 pointer to second JoinTable object
4813
possible_keys.intersect(cur_item->field->part_of_key);
4816
if (!possible_keys.is_clear_all())
4817
join_tab->const_keys.merge(possible_keys);
4821
/*****************************************************************************
4822
Go through all combinations of not marked tables and find the one
4823
which uses least records
4824
*****************************************************************************/
4826
/** Save const tables first as used tables. */
4829
set_position(JOIN *join,uint32_t idx,JOIN_TAB *table,KEYUSE *key)
4831
join->positions[idx].table= table;
4832
join->positions[idx].key=key;
4833
join->positions[idx].records_read=1.0; /* This is a const table */
4834
join->positions[idx].ref_depend_map= 0;
4836
/* Move the const table as down as possible in best_ref */
4837
JOIN_TAB **pos=join->best_ref+idx+1;
4838
JOIN_TAB *next=join->best_ref[idx];
4839
for (;next != table ; pos++)
4841
JOIN_TAB *tmp=pos[0];
4845
join->best_ref[idx]=table;
4850
Given a semi-join nest, find out which of the IN-equalities are bound
4853
get_bound_sj_equalities()
4854
sj_nest Semi-join nest
4855
remaining_tables Tables that are not yet bound
4858
Given a semi-join nest, find out which of the IN-equalities have their
4859
left part expression bound (i.e. the said expression doesn't refer to
4860
any of remaining_tables and can be evaluated).
4863
Bitmap of bound IN-equalities.
4866
uint64_t get_bound_sj_equalities(TableList *sj_nest,
4867
table_map remaining_tables)
4869
List_iterator<Item> li(sj_nest->nested_join->sj_outer_expr_list);
4873
while ((item= li++))
4876
Q: should this take into account equality propagation and how?
4877
A: If e->outer_side is an Item_field, walk over the equality
4878
class and see if there is an element that is bound?
4879
(this is an optional feature)
4881
if (!(item->used_tables() & remaining_tables))
4891
Find the best access path for an extension of a partial execution
4892
plan and add this path to the plan.
4894
The function finds the best access path to table 's' from the passed
4895
partial plan where an access path is the general term for any means to
4896
access the data in 's'. An access path may use either an index or a scan,
4897
whichever is cheaper. The input partial plan is passed via the array
4898
'join->positions' of length 'idx'. The chosen access method for 's' and its
4899
cost are stored in 'join->positions[idx]'.
4901
@param join pointer to the structure providing all context info
4903
@param s the table to be joined by the function
4904
@param session thread for the connection that submitted the query
4905
@param remaining_tables set of tables not included into the partial plan yet
4906
@param idx the length of the partial plan
4907
@param record_count estimate for the number of records returned by the
4909
@param read_time the cost of the partial plan
4916
best_access_path(JOIN *join,
4919
table_map remaining_tables,
4921
double record_count,
4924
KEYUSE *best_key= 0;
4925
uint32_t best_max_key_part= 0;
4926
bool found_constraint= 0;
4927
double best= DBL_MAX;
4928
double best_time= DBL_MAX;
4929
double records= DBL_MAX;
4930
table_map best_ref_depends_map= 0;
4933
uint32_t best_is_sj_inside_out= 0;
4936
{ /* Use key if possible */
4937
Table *table= s->table;
4938
KEYUSE *keyuse,*start_key=0;
4939
double best_records= DBL_MAX;
4940
uint32_t max_key_part=0;
4941
uint64_t bound_sj_equalities= 0;
4942
bool try_sj_inside_out= false;
4944
Discover the bound equalites. We need to do this, if
4945
1. The next table is an SJ-inner table, and
4946
2. It is the first table from that semijoin, and
4947
3. We're not within a semi-join range (i.e. all semi-joins either have
4948
all or none of their tables in join_table_map), except
4949
s->emb_sj_nest (which we've just entered).
4950
3. All correlation references from this sj-nest are bound
4952
if (s->emb_sj_nest && // (1)
4953
s->emb_sj_nest->sj_in_exprs < 64 &&
4954
((remaining_tables & s->emb_sj_nest->sj_inner_tables) == // (2)
4955
s->emb_sj_nest->sj_inner_tables) && // (2)
4956
join->cur_emb_sj_nests == s->emb_sj_nest->sj_inner_tables && // (3)
4957
!(remaining_tables & s->emb_sj_nest->nested_join->sj_corr_tables)) // (4)
4959
/* This table is an InsideOut scan candidate */
4960
bound_sj_equalities= get_bound_sj_equalities(s->emb_sj_nest,
4962
try_sj_inside_out= true;
4965
/* Test how we can use keys */
4966
rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE; // Assumed records/key
4967
for (keyuse=s->keyuse ; keyuse->table == table ;)
4969
key_part_map found_part= 0;
4970
table_map found_ref= 0;
4971
uint32_t key= keyuse->key;
4972
KEY *keyinfo= table->key_info+key;
4973
/* Bitmap of keyparts where the ref access is over 'keypart=const': */
4974
key_part_map const_part= 0;
4975
/* The or-null keypart in ref-or-null access: */
4976
key_part_map ref_or_null_part= 0;
4978
/* Calculate how many key segments of the current key we can use */
4980
uint64_t handled_sj_equalities=0;
4981
key_part_map sj_insideout_map= 0;
4983
do /* For each keypart */
4985
uint32_t keypart= keyuse->keypart;
4986
table_map best_part_found_ref= 0;
4987
double best_prev_record_reads= DBL_MAX;
4989
do /* For each way to access the keypart */
4993
if 1. expression doesn't refer to forward tables
4994
2. we won't get two ref-or-null's
4996
if (!(remaining_tables & keyuse->used_tables) &&
4997
!(ref_or_null_part && (keyuse->optimize &
4998
KEY_OPTIMIZE_REF_OR_NULL)))
5000
found_part|= keyuse->keypart_map;
5001
if (!(keyuse->used_tables & ~join->const_table_map))
5002
const_part|= keyuse->keypart_map;
5004
double tmp2= prev_record_reads(join, idx, (found_ref |
5005
keyuse->used_tables));
5006
if (tmp2 < best_prev_record_reads)
5008
best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
5009
best_prev_record_reads= tmp2;
5011
if (rec > keyuse->ref_table_rows)
5012
rec= keyuse->ref_table_rows;
5014
If there is one 'key_column IS NULL' expression, we can
5015
use this ref_or_null optimisation of this field
5017
if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
5018
ref_or_null_part |= keyuse->keypart_map;
5021
if (try_sj_inside_out && keyuse->sj_pred_no != UINT_MAX)
5023
if (!(remaining_tables & keyuse->used_tables))
5024
bound_sj_equalities |= 1UL << keyuse->sj_pred_no;
5027
handled_sj_equalities |= 1UL << keyuse->sj_pred_no;
5028
sj_insideout_map |= ((key_part_map)1) << keyuse->keypart;
5033
} while (keyuse->table == table && keyuse->key == key &&
5034
keyuse->keypart == keypart);
5035
found_ref|= best_part_found_ref;
5036
} while (keyuse->table == table && keyuse->key == key);
5039
Assume that that each key matches a proportional part of table.
5041
if (!found_part && !handled_sj_equalities)
5042
continue; // Nothing usable found
5044
if (rec < MATCHING_ROWS_IN_OTHER_TABLE)
5045
rec= MATCHING_ROWS_IN_OTHER_TABLE; // Fix for small tables
5047
bool sj_inside_out_scan= false;
5049
found_constraint= 1;
5051
Check if InsideOut scan is applicable:
5052
1. All IN-equalities are either "bound" or "handled"
5053
2. Index keyparts are
5056
if (try_sj_inside_out &&
5057
table->covering_keys.is_set(key) &&
5058
(handled_sj_equalities | bound_sj_equalities) == // (1)
5059
PREV_BITS(uint64_t, s->emb_sj_nest->sj_in_exprs)) // (1)
5061
uint32_t n_fixed_parts= max_part_bit(found_part);
5062
if (n_fixed_parts != keyinfo->key_parts &&
5063
(PREV_BITS(uint, n_fixed_parts) | sj_insideout_map) ==
5064
PREV_BITS(uint, keyinfo->key_parts))
5067
Not all parts are fixed. Produce bitmap of remaining bits and
5068
check if all of them are covered.
5070
sj_inside_out_scan= true;
5074
It's a confluent ref scan.
5076
That is, all found KEYUSE elements refer to IN-equalities,
5077
and there is really no ref access because there is no
5078
t.keypart0 = {bound expression}
5080
Calculate the cost of complete loose index scan.
5082
records= (double)s->table->file->stats.records;
5084
/* The cost is entire index scan cost (divided by 2) */
5085
best_time= s->table->file->index_only_read_time(key, records);
5087
/* Now figure how many different keys we will get */
5089
if ((rpc= keyinfo->rec_per_key[keyinfo->key_parts-1]))
5090
records= records / rpc;
5097
Check if we found full key
5099
if (found_part == PREV_BITS(uint,keyinfo->key_parts) &&
5102
max_key_part= UINT32_MAX;
5103
if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
5105
tmp = prev_record_reads(join, idx, found_ref);
5111
{ /* We found a const key */
5113
ReuseRangeEstimateForRef-1:
5114
We get here if we've found a ref(const) (c_i are constants):
5115
"(keypart1=c1) AND ... AND (keypartN=cN)" [ref_const_cond]
5117
If range optimizer was able to construct a "range"
5118
access on this index, then its condition "quick_cond" was
5119
eqivalent to ref_const_cond (*), and we can re-use E(#rows)
5120
from the range optimizer.
5122
Proof of (*): By properties of range and ref optimizers
5123
quick_cond will be equal or tighther than ref_const_cond.
5124
ref_const_cond already covers "smallest" possible interval -
5125
a singlepoint interval over all keyparts. Therefore,
5126
quick_cond is equivalent to ref_const_cond (if it was an
5127
empty interval we wouldn't have got here).
5129
if (table->quick_keys.is_set(key))
5130
records= (double) table->quick_rows[key];
5133
/* quick_range couldn't use key! */
5134
records= (double) s->records/rec;
5139
if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
5140
{ /* Prefer longer keys */
5142
((double) s->records / (double) rec *
5144
((double) (table->s->max_key_length-keyinfo->key_length) /
5145
(double) table->s->max_key_length)));
5147
records=2.0; /* Can't be as good as a unique */
5150
ReuseRangeEstimateForRef-2: We get here if we could not reuse
5151
E(#rows) from range optimizer. Make another try:
5153
If range optimizer produced E(#rows) for a prefix of the ref
5154
access we're considering, and that E(#rows) is lower then our
5155
current estimate, make an adjustment. The criteria of when we
5156
can make an adjustment is a special case of the criteria used
5157
in ReuseRangeEstimateForRef-3.
5159
if (table->quick_keys.is_set(key) &&
5160
const_part & (1 << table->quick_key_parts[key]) &&
5161
table->quick_n_ranges[key] == 1 &&
5162
records > (double) table->quick_rows[key])
5164
records= (double) table->quick_rows[key];
5167
/* Limit the number of matched rows */
5169
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5170
if (table->covering_keys.is_set(key))
5172
/* we can use only index tree */
5173
tmp= record_count * table->file->index_only_read_time(key, tmp);
5176
tmp= record_count*cmin(tmp,s->worst_seeks);
5182
Use as much key-parts as possible and a uniq key is better
5183
than a not unique key
5184
Set tmp to (previous record count) * (records / combination)
5186
if ((found_part & 1) &&
5187
(!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
5188
found_part == PREV_BITS(uint,keyinfo->key_parts)))
5190
max_key_part= max_part_bit(found_part);
5192
ReuseRangeEstimateForRef-3:
5193
We're now considering a ref[or_null] access via
5194
(t.keypart1=e1 AND ... AND t.keypartK=eK) [ OR
5195
(same-as-above but with one cond replaced
5196
with "t.keypart_i IS NULL")] (**)
5198
Try re-using E(#rows) from "range" optimizer:
5199
We can do so if "range" optimizer used the same intervals as
5200
in (**). The intervals used by range optimizer may be not
5201
available at this point (as "range" access might have choosen to
5202
create quick select over another index), so we can't compare
5203
them to (**). We'll make indirect judgements instead.
5204
The sufficient conditions for re-use are:
5205
(C1) All e_i in (**) are constants, i.e. found_ref==false. (if
5206
this is not satisfied we have no way to know which ranges
5207
will be actually scanned by 'ref' until we execute the
5209
(C2) max #key parts in 'range' access == K == max_key_part (this
5210
is apparently a necessary requirement)
5212
We also have a property that "range optimizer produces equal or
5213
tighter set of scan intervals than ref(const) optimizer". Each
5214
of the intervals in (**) are "tightest possible" intervals when
5215
one limits itself to using keyparts 1..K (which we do in #2).
5216
From here it follows that range access used either one, or
5217
both of the (I1) and (I2) intervals:
5219
(t.keypart1=c1 AND ... AND t.keypartK=eK) (I1)
5220
(same-as-above but with one cond replaced
5221
with "t.keypart_i IS NULL") (I2)
5223
The remaining part is to exclude the situation where range
5224
optimizer used one interval while we're considering
5225
ref-or-null and looking for estimate for two intervals. This
5226
is done by last limitation:
5228
(C3) "range optimizer used (have ref_or_null?2:1) intervals"
5230
if (table->quick_keys.is_set(key) && !found_ref && //(C1)
5231
table->quick_key_parts[key] == max_key_part && //(C2)
5232
table->quick_n_ranges[key] == 1+((ref_or_null_part)?1:0)) //(C3)
5234
tmp= records= (double) table->quick_rows[key];
5238
/* Check if we have statistic about the distribution */
5239
if ((records= keyinfo->rec_per_key[max_key_part-1]))
5242
Fix for the case where the index statistics is too
5244
(1) We're considering ref(const) and there is quick select
5246
(2) and that quick select uses more keyparts (i.e. it will
5247
scan equal/smaller interval then this ref(const))
5248
(3) and E(#rows) for quick select is higher then our
5251
We'll use E(#rows) from quick select.
5253
Q: Why do we choose to use 'ref'? Won't quick select be
5254
cheaper in some cases ?
5255
TODO: figure this out and adjust the plan choice if needed.
5257
if (!found_ref && table->quick_keys.is_set(key) && // (1)
5258
table->quick_key_parts[key] > max_key_part && // (2)
5259
records < (double)table->quick_rows[key]) // (3)
5260
records= (double)table->quick_rows[key];
5267
Assume that the first key part matches 1% of the file
5268
and that the whole key matches 10 (duplicates) or 1
5270
Assume also that more key matches proportionally more
5272
This gives the formula:
5273
records = (x * (b-a) + a*c-b)/(c-1)
5275
b = records matched by whole key
5276
a = records matched by first key part (1% of all records?)
5277
c = number of key parts in key
5278
x = used key parts (1 <= x <= c)
5281
if (!(rec_per_key=(double)
5282
keyinfo->rec_per_key[keyinfo->key_parts-1]))
5283
rec_per_key=(double) s->records/rec+1;
5287
else if (rec_per_key/(double) s->records >= 0.01)
5291
double a=s->records*0.01;
5292
if (keyinfo->key_parts > 1)
5293
tmp= (max_key_part * (rec_per_key - a) +
5294
a*keyinfo->key_parts - rec_per_key)/
5295
(keyinfo->key_parts-1);
5298
set_if_bigger(tmp,1.0);
5300
records = (uint32_t) tmp;
5303
if (ref_or_null_part)
5305
/* We need to do two key searches to find key */
5311
ReuseRangeEstimateForRef-4: We get here if we could not reuse
5312
E(#rows) from range optimizer. Make another try:
5314
If range optimizer produced E(#rows) for a prefix of the ref
5315
access we're considering, and that E(#rows) is lower then our
5316
current estimate, make the adjustment.
5318
The decision whether we can re-use the estimate from the range
5319
optimizer is the same as in ReuseRangeEstimateForRef-3,
5320
applied to first table->quick_key_parts[key] key parts.
5322
if (table->quick_keys.is_set(key) &&
5323
table->quick_key_parts[key] <= max_key_part &&
5324
const_part & (1 << table->quick_key_parts[key]) &&
5325
table->quick_n_ranges[key] == 1 + ((ref_or_null_part &
5326
const_part) ? 1 : 0) &&
5327
records > (double) table->quick_rows[key])
5329
tmp= records= (double) table->quick_rows[key];
5333
/* Limit the number of matched rows */
5334
set_if_smaller(tmp, (double) session->variables.max_seeks_for_key);
5335
if (table->covering_keys.is_set(key))
5337
/* we can use only index tree */
5338
tmp= record_count * table->file->index_only_read_time(key, tmp);
5341
tmp= record_count * cmin(tmp,s->worst_seeks);
5344
tmp= best_time; // Do nothing
5347
if (sj_inside_out_scan && !start_key)
5355
if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
5357
best_time= tmp + records/(double) TIME_FOR_COMPARE;
5359
best_records= records;
5360
best_key= start_key;
5361
best_max_key_part= max_key_part;
5362
best_ref_depends_map= found_ref;
5363
best_is_sj_inside_out= sj_inside_out_scan;
5366
records= best_records;
5370
Don't test table scan if it can't be better.
5371
Prefer key lookup if we would use the same key for scanning.
5373
Don't do a table scan on InnoDB tables, if we can read the used
5374
parts of the row from any of the used index.
5375
This is because table scans uses index and we would not win
5376
anything by using a table scan.
5378
A word for word translation of the below if-statement in sergefp's
5379
understanding: we check if we should use table scan if:
5380
(1) The found 'ref' access produces more records than a table scan
5381
(or index scan, or quick select), or 'ref' is more expensive than
5383
(2) This doesn't hold: the best way to perform table scan is to to perform
5384
'range' access using index IDX, and the best way to perform 'ref'
5385
access is to use the same index IDX, with the same or more key parts.
5386
(note: it is not clear how this rule is/should be extended to
5387
index_merge quick selects)
5388
(3) See above note about InnoDB.
5389
(4) NOT ("FORCE INDEX(...)" is used for table and there is 'ref' access
5390
path, but there is no quick select)
5391
If the condition in the above brackets holds, then the only possible
5392
"table scan" access method is ALL/index (there is no quick select).
5393
Since we have a 'ref' access path, and FORCE INDEX instructs us to
5394
choose it over ALL/index, there is no need to consider a full table
5397
if ((records >= s->found_records || best > s->read_time) && // (1)
5398
!(s->quick && best_key && s->quick->index == best_key->key && // (2)
5399
best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
5400
!((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) && // (3)
5401
! s->table->covering_keys.is_clear_all() && best_key && !s->quick) &&// (3)
5402
!(s->table->force_index && best_key && !s->quick)) // (4)
5403
{ // Check full join
5404
ha_rows rnd_records= s->found_records;
5406
If there is a filtering condition on the table (i.e. ref analyzer found
5407
at least one "table.keyXpartY= exprZ", where exprZ refers only to tables
5408
preceding this table in the join order we're now considering), then
5409
assume that 25% of the rows will be filtered out by this condition.
5411
This heuristic is supposed to force tables used in exprZ to be before
5412
this table in join order.
5414
if (found_constraint)
5415
rnd_records-= rnd_records/4;
5418
If applicable, get a more accurate estimate. Don't use the two
5421
if (s->table->quick_condition_rows != s->found_records)
5422
rnd_records= s->table->quick_condition_rows;
5425
Range optimizer never proposes a RANGE if it isn't better
5426
than FULL: so if RANGE is present, it's always preferred to FULL.
5427
Here we estimate its cost.
5433
- read record range through 'quick'
5434
- skip rows which does not satisfy WHERE constraints
5436
We take into account possible use of join cache for ALL/index
5437
access (see first else-branch below), but we don't take it into
5438
account here for range/index_merge access. Find out why this is so.
5441
(s->quick->read_time +
5442
(s->found_records - rnd_records)/(double) TIME_FOR_COMPARE);
5446
/* Estimate cost of reading table. */
5447
tmp= s->table->file->scan_time();
5448
if (s->table->map & join->outer_join) // Can't use join cache
5451
For each record we have to:
5452
- read the whole table record
5453
- skip rows which does not satisfy join condition
5457
(s->records - rnd_records)/(double) TIME_FOR_COMPARE);
5461
/* We read the table as many times as join buffer becomes full. */
5462
tmp*= (1.0 + floor((double) cache_record_length(join,idx) *
5464
(double) session->variables.join_buff_size));
5466
We don't make full cartesian product between rows in the scanned
5467
table and existing records because we skip all rows from the
5468
scanned table, which does not satisfy join condition when
5469
we read the table (see flush_cached_records for details). Here we
5470
take into account cost to read and skip these records.
5472
tmp+= (s->records - rnd_records)/(double) TIME_FOR_COMPARE;
5477
We estimate the cost of evaluating WHERE clause for found records
5478
as record_count * rnd_records / TIME_FOR_COMPARE. This cost plus
5479
tmp give us total cost of using Table SCAN
5481
if (best == DBL_MAX ||
5482
(tmp + record_count/(double) TIME_FOR_COMPARE*rnd_records <
5483
best + record_count/(double) TIME_FOR_COMPARE*records))
5486
If the table has a range (s->quick is set) make_join_select()
5487
will ensure that this will be used
5490
records= rows2double(rnd_records);
5492
/* range/index_merge/ALL/index access method are "independent", so: */
5493
best_ref_depends_map= 0;
5494
best_is_sj_inside_out= false;
5498
/* Update the cost information for the current partial plan */
5499
join->positions[idx].records_read= records;
5500
join->positions[idx].read_time= best;
5501
join->positions[idx].key= best_key;
5502
join->positions[idx].table= s;
5503
join->positions[idx].ref_depend_map= best_ref_depends_map;
5504
join->positions[idx].use_insideout_scan= best_is_sj_inside_out;
5507
idx == join->const_tables &&
5508
s->table == join->sort_by_table &&
5509
join->unit->select_limit_cnt >= records)
5510
join->sort_by_table= (Table*) 1; // Must use temporary table
5517
Selects and invokes a search strategy for an optimal query plan.
5519
The function checks user-configurable parameters that control the search
5520
strategy for an optimal plan, selects the search method and then invokes
5521
it. Each specific optimization procedure stores the final optimal plan in
5522
the array 'join->best_positions', and the cost of the plan in
5525
@param join pointer to the structure providing all context info for
5527
@param join_tables set of the tables in the query
5530
'MAX_TABLES+2' denotes the old implementation of find_best before
5531
the greedy version. Will be removed when greedy_search is approved.
5540
choose_plan(JOIN *join, table_map join_tables)
5542
uint32_t search_depth= join->session->variables.optimizer_search_depth;
5543
uint32_t prune_level= join->session->variables.optimizer_prune_level;
5544
bool straight_join= test(join->select_options & SELECT_STRAIGHT_JOIN);
5546
join->cur_embedding_map= 0;
5547
reset_nj_counters(join->join_list);
5549
if (SELECT_STRAIGHT_JOIN option is set)
5550
reorder tables so dependent tables come after tables they depend
5551
on, otherwise keep tables in the order they were specified in the query
5553
Apply heuristic: pre-sort all access plans with respect to the number of
5556
my_qsort(join->best_ref + join->const_tables,
5557
join->tables - join->const_tables, sizeof(JOIN_TAB*),
5558
straight_join ? join_tab_cmp_straight : join_tab_cmp);
5559
join->cur_emb_sj_nests= 0;
5562
optimize_straight_join(join, join_tables);
5566
if (search_depth == MAX_TABLES+2)
5568
TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
5569
the greedy version. Will be removed when greedy_search is approved.
5571
join->best_read= DBL_MAX;
5572
if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
5577
if (search_depth == 0)
5578
/* Automatically determine a reasonable value for 'search_depth' */
5579
search_depth= determine_search_depth(join);
5580
if (greedy_search(join, join_tables, search_depth, prune_level))
5586
Store the cost of this query into a user variable
5587
Don't update last_query_cost for statements that are not "flat joins" :
5588
i.e. they have subqueries, unions or call stored procedures.
5589
TODO: calculate a correct cost for a query with subqueries and UNIONs.
5591
if (join->session->lex->is_single_level_stmt())
5592
join->session->status_var.last_query_cost= join->best_read;
5598
Compare two JOIN_TAB objects based on the number of accessed records.
5600
@param ptr1 pointer to first JOIN_TAB object
5601
@param ptr2 pointer to second JOIN_TAB object
798
5604
The order relation implemented by join_tab_cmp() is not transitive,
5656
Heuristic procedure to automatically guess a reasonable degree of
5657
exhaustiveness for the greedy search procedure.
5659
The procedure estimates the optimization time and selects a search depth
5660
big enough to result in a near-optimal QEP, that doesn't take too long to
5661
find. If the number of tables in the query exceeds some constant, then
5662
search_depth is set to this constant.
5664
@param join pointer to the structure providing all context info for
5668
This is an extremely simplistic implementation that serves as a stub for a
5669
more advanced analysis of the join. Ideally the search depth should be
5670
determined by learning from previous query optimizations, because it will
5671
depend on the CPU power (and other factors).
5674
this value should be determined dynamically, based on statistics:
5675
uint32_t max_tables_for_exhaustive_opt= 7;
5678
this value could be determined by some mapping of the form:
5679
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5682
A positive integer that specifies the search depth (and thus the
5683
exhaustiveness) of the depth-first search algorithm used by
5688
determine_search_depth(JOIN *join)
5690
uint32_t table_count= join->tables - join->const_tables;
5691
uint32_t search_depth;
5692
/* TODO: this value should be determined dynamically, based on statistics: */
5693
uint32_t max_tables_for_exhaustive_opt= 7;
5695
if (table_count <= max_tables_for_exhaustive_opt)
5696
search_depth= table_count+1; // use exhaustive for small number of tables
5699
TODO: this value could be determined by some mapping of the form:
5700
depth : table_count -> [max_tables_for_exhaustive_opt..MAX_EXHAUSTIVE]
5702
search_depth= max_tables_for_exhaustive_opt; // use greedy search
5704
return search_depth;
5709
Select the best ways to access the tables in a query without reordering them.
5711
Find the best access paths for each query table and compute their costs
5712
according to their order in the array 'join->best_ref' (thus without
5713
reordering the join tables). The function calls sequentially
5714
'best_access_path' for each table in the query to select the best table
5715
access method. The final optimal plan is stored in the array
5716
'join->best_positions', and the corresponding cost in 'join->best_read'.
5718
@param join pointer to the structure providing all context info for
5720
@param join_tables set of the tables in the query
5723
This function can be applied to:
5724
- queries with STRAIGHT_JOIN
5725
- internally to compute the cost of an arbitrary QEP
5727
Thus 'optimize_straight_join' can be used at any stage of the query
5728
optimization process to finalize a QEP as it is.
5732
optimize_straight_join(JOIN *join, table_map join_tables)
5735
uint32_t idx= join->const_tables;
5736
double record_count= 1.0;
5737
double read_time= 0.0;
5739
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
5741
/* Find the best access method from 's' to the current partial plan */
5742
advance_sj_state(join_tables, s);
5743
best_access_path(join, s, join->session, join_tables, idx,
5744
record_count, read_time);
5745
/* compute the cost of the new plan extended with 's' */
5746
record_count*= join->positions[idx].records_read;
5747
read_time+= join->positions[idx].read_time;
5748
join_tables&= ~(s->table->map);
5752
read_time+= record_count / (double) TIME_FOR_COMPARE;
5753
if (join->sort_by_table &&
5754
join->sort_by_table != join->positions[join->const_tables].table->table)
5755
read_time+= record_count; // We have to make a temp table
5756
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
5757
join->best_read= read_time;
5762
Find a good, possibly optimal, query execution plan (QEP) by a greedy search.
5764
The search procedure uses a hybrid greedy/exhaustive search with controlled
5765
exhaustiveness. The search is performed in N = card(remaining_tables)
5766
steps. Each step evaluates how promising is each of the unoptimized tables,
5767
selects the most promising table, and extends the current partial QEP with
5768
that table. Currenly the most 'promising' table is the one with least
5769
expensive extension.\
5771
There are two extreme cases:
5772
-# When (card(remaining_tables) < search_depth), the estimate finds the
5773
best complete continuation of the partial QEP. This continuation can be
5774
used directly as a result of the search.
5775
-# When (search_depth == 1) the 'best_extension_by_limited_search'
5776
consideres the extension of the current QEP with each of the remaining
5779
All other cases are in-between these two extremes. Thus the parameter
5780
'search_depth' controlls the exhaustiveness of the search. The higher the
5781
value, the longer the optimizaton time and possibly the better the
5782
resulting plan. The lower the value, the fewer alternative plans are
5783
estimated, but the more likely to get a bad QEP.
5785
All intermediate and final results of the procedure are stored in 'join':
5786
- join->positions : modified for every partial QEP that is explored
5787
- join->best_positions: modified for the current best complete QEP
5788
- join->best_read : modified for the current best complete QEP
5789
- join->best_ref : might be partially reordered
5791
The final optimal plan is stored in 'join->best_positions', and its
5792
corresponding cost in 'join->best_read'.
5795
The following pseudocode describes the algorithm of 'greedy_search':
5798
procedure greedy_search
5799
input: remaining_tables
5804
(t, a) = best_extension(pplan, remaining_tables);
5805
pplan = concat(pplan, (t, a));
5806
remaining_tables = remaining_tables - t;
5807
} while (remaining_tables != {})
5812
where 'best_extension' is a placeholder for a procedure that selects the
5813
most "promising" of all tables in 'remaining_tables'.
5814
Currently this estimate is performed by calling
5815
'best_extension_by_limited_search' to evaluate all extensions of the
5816
current QEP of size 'search_depth', thus the complexity of 'greedy_search'
5817
mainly depends on that of 'best_extension_by_limited_search'.
5820
If 'best_extension()' == 'best_extension_by_limited_search()', then the
5821
worst-case complexity of this algorithm is <=
5822
O(N*N^search_depth/search_depth). When serch_depth >= N, then the
5823
complexity of greedy_search is O(N!).
5826
In the future, 'greedy_search' might be extended to support other
5827
implementations of 'best_extension', e.g. some simpler quadratic procedure.
5829
@param join pointer to the structure providing all context info
5831
@param remaining_tables set of tables not included into the partial plan yet
5832
@param search_depth controlls the exhaustiveness of the search
5833
@param prune_level the pruning heuristics that should be applied during
5843
greedy_search(JOIN *join,
5844
table_map remaining_tables,
5845
uint32_t search_depth,
5846
uint32_t prune_level)
5848
double record_count= 1.0;
5849
double read_time= 0.0;
5850
uint32_t idx= join->const_tables; // index into 'join->best_ref'
5852
uint32_t size_remain; // cardinality of remaining_tables
5854
JOIN_TAB *best_table; // the next plan node to be added to the curr QEP
5856
/* number of tables that remain to be optimized */
5857
size_remain= my_count_bits(remaining_tables);
5860
/* Find the extension of the current QEP with the lowest cost */
5861
join->best_read= DBL_MAX;
5862
if (best_extension_by_limited_search(join, remaining_tables, idx, record_count,
5863
read_time, search_depth, prune_level))
5866
if (size_remain <= search_depth)
5869
'join->best_positions' contains a complete optimal extension of the
5870
current partial QEP.
5875
/* select the first table in the optimal extension as most promising */
5876
best_pos= join->best_positions[idx];
5877
best_table= best_pos.table;
5879
Each subsequent loop of 'best_extension_by_limited_search' uses
5880
'join->positions' for cost estimates, therefore we have to update its
5883
join->positions[idx]= best_pos;
5885
/* find the position of 'best_table' in 'join->best_ref' */
5887
JOIN_TAB *pos= join->best_ref[best_idx];
5888
while (pos && best_table != pos)
5889
pos= join->best_ref[++best_idx];
5890
assert((pos != NULL)); // should always find 'best_table'
5891
/* move 'best_table' at the first free position in the array of joins */
5892
std::swap(join->best_ref[idx], join->best_ref[best_idx]);
5894
/* compute the cost of the new plan extended with 'best_table' */
5895
record_count*= join->positions[idx].records_read;
5896
read_time+= join->positions[idx].read_time;
5898
remaining_tables&= ~(best_table->table->map);
5906
Find a good, possibly optimal, query execution plan (QEP) by a possibly
5909
The procedure searches for the optimal ordering of the query tables in set
5910
'remaining_tables' of size N, and the corresponding optimal access paths to
5911
each table. The choice of a table order and an access path for each table
5912
constitutes a query execution plan (QEP) that fully specifies how to
5915
The maximal size of the found plan is controlled by the parameter
5916
'search_depth'. When search_depth == N, the resulting plan is complete and
5917
can be used directly as a QEP. If search_depth < N, the found plan consists
5918
of only some of the query tables. Such "partial" optimal plans are useful
5919
only as input to query optimization procedures, and cannot be used directly
5922
The algorithm begins with an empty partial plan stored in 'join->positions'
5923
and a set of N tables - 'remaining_tables'. Each step of the algorithm
5924
evaluates the cost of the partial plan extended by all access plans for
5925
each of the relations in 'remaining_tables', expands the current partial
5926
plan with the access plan that results in lowest cost of the expanded
5927
partial plan, and removes the corresponding relation from
5928
'remaining_tables'. The algorithm continues until it either constructs a
5929
complete optimal plan, or constructs an optimal plartial plan with size =
5932
The final optimal plan is stored in 'join->best_positions'. The
5933
corresponding cost of the optimal plan is in 'join->best_read'.
5936
The procedure uses a recursive depth-first search where the depth of the
5937
recursion (and thus the exhaustiveness of the search) is controlled by the
5938
parameter 'search_depth'.
5941
The pseudocode below describes the algorithm of
5942
'best_extension_by_limited_search'. The worst-case complexity of this
5943
algorithm is O(N*N^search_depth/search_depth). When serch_depth >= N, then
5944
the complexity of greedy_search is O(N!).
5947
procedure best_extension_by_limited_search(
5948
pplan in, // in, partial plan of tables-joined-so-far
5949
pplan_cost, // in, cost of pplan
5950
remaining_tables, // in, set of tables not referenced in pplan
5951
best_plan_so_far, // in/out, best plan found so far
5952
best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5953
search_depth) // in, maximum size of the plans being considered
5955
for each table T from remaining_tables
5957
// Calculate the cost of using table T as above
5958
cost = complex-series-of-calculations;
5960
// Add the cost to the cost so far.
5963
if (pplan_cost >= best_plan_so_far_cost)
5964
// pplan_cost already too great, stop search
5967
pplan= expand pplan by best_access_method;
5968
remaining_tables= remaining_tables - table T;
5969
if (remaining_tables is not an empty set
5973
best_extension_by_limited_search(pplan, pplan_cost,
5976
best_plan_so_far_cost,
5981
best_plan_so_far_cost= pplan_cost;
5982
best_plan_so_far= pplan;
5989
When 'best_extension_by_limited_search' is called for the first time,
5990
'join->best_read' must be set to the largest possible value (e.g. DBL_MAX).
5991
The actual implementation provides a way to optionally use pruning
5992
heuristic (controlled by the parameter 'prune_level') to reduce the search
5993
space by skipping some partial plans.
5996
The parameter 'search_depth' provides control over the recursion
5997
depth, and thus the size of the resulting optimal plan.
5999
@param join pointer to the structure providing all context info
6001
@param remaining_tables set of tables not included into the partial plan yet
6002
@param idx length of the partial QEP in 'join->positions';
6003
since a depth-first search is used, also corresponds
6004
to the current depth of the search tree;
6005
also an index in the array 'join->best_ref';
6006
@param record_count estimate for the number of records returned by the
6008
@param read_time the cost of the best partial plan
6009
@param search_depth maximum depth of the recursion and thus size of the
6011
(0 < search_depth <= join->tables+1).
6012
@param prune_level pruning heuristics that should be applied during
6014
(values: 0 = EXHAUSTIVE, 1 = PRUNE_BY_TIME_OR_ROWS)
6023
best_extension_by_limited_search(JOIN *join,
6024
table_map remaining_tables,
6026
double record_count,
6028
uint32_t search_depth,
6029
uint32_t prune_level)
6031
Session *session= join->session;
6032
if (session->killed) // Abort
6036
'join' is a partial plan with lower cost than the best plan so far,
6037
so continue expanding it further with the tables in 'remaining_tables'.
6040
double best_record_count= DBL_MAX;
6041
double best_read_time= DBL_MAX;
6043
for (JOIN_TAB **pos= join->best_ref + idx ; (s= *pos) ; pos++)
6045
table_map real_table_bit= s->table->map;
6046
if ((remaining_tables & real_table_bit) &&
6047
!(remaining_tables & s->dependent) &&
6048
(!idx || !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6050
double current_record_count, current_read_time;
6051
advance_sj_state(remaining_tables, s);
6054
psergey-insideout-todo:
6055
when best_access_path() detects it could do an InsideOut scan or
6056
some other scan, have it return an insideout scan and a flag that
6057
requests to "fork" this loop iteration. (Q: how does that behave
6058
when the depth is insufficient??)
6060
/* Find the best access method from 's' to the current partial plan */
6061
best_access_path(join, s, session, remaining_tables, idx,
6062
record_count, read_time);
6063
/* Compute the cost of extending the plan with 's' */
6064
current_record_count= record_count * join->positions[idx].records_read;
6065
current_read_time= read_time + join->positions[idx].read_time;
6067
/* Expand only partial plans with lower cost than the best QEP so far */
6068
if ((current_read_time +
6069
current_record_count / (double) TIME_FOR_COMPARE) >= join->best_read)
6071
restore_prev_nj_state(s);
6072
restore_prev_sj_state(remaining_tables, s);
6077
Prune some less promising partial plans. This heuristic may miss
6078
the optimal QEPs, thus it results in a non-exhaustive search.
6080
if (prune_level == 1)
6082
if (best_record_count > current_record_count ||
6083
best_read_time > current_read_time ||
6084
(idx == join->const_tables && s->table == join->sort_by_table)) // 's' is the first table in the QEP
6086
if (best_record_count >= current_record_count &&
6087
best_read_time >= current_read_time &&
6088
/* TODO: What is the reasoning behind this condition? */
6089
(!(s->key_dependent & remaining_tables) ||
6090
join->positions[idx].records_read < 2.0))
6092
best_record_count= current_record_count;
6093
best_read_time= current_read_time;
6098
restore_prev_nj_state(s);
6099
restore_prev_sj_state(remaining_tables, s);
6104
if ( (search_depth > 1) && (remaining_tables & ~real_table_bit) )
6105
{ /* Recursively expand the current partial plan */
6106
std::swap(join->best_ref[idx], *pos);
6107
if (best_extension_by_limited_search(join,
6108
remaining_tables & ~real_table_bit,
6110
current_record_count,
6115
std::swap(join->best_ref[idx], *pos);
6119
'join' is either the best partial QEP with 'search_depth' relations,
6120
or the best complete QEP so far, whichever is smaller.
6122
current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
6123
if (join->sort_by_table &&
6124
join->sort_by_table !=
6125
join->positions[join->const_tables].table->table)
6126
/* We have to make a temp table */
6127
current_read_time+= current_record_count;
6128
if ((search_depth == 1) || (current_read_time < join->best_read))
6130
memcpy(join->best_positions, join->positions,
6131
sizeof(POSITION) * (idx + 1));
6132
join->best_read= current_read_time - 0.001;
6135
restore_prev_nj_state(s);
6136
restore_prev_sj_state(remaining_tables, s);
6145
- TODO: this function is here only temporarily until 'greedy_search' is
6146
tested and accepted.
6153
find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count,
6156
Session *session= join->session;
6157
if (session->killed)
6161
read_time+=record_count/(double) TIME_FOR_COMPARE;
6162
if (join->sort_by_table &&
6163
join->sort_by_table !=
6164
join->positions[join->const_tables].table->table)
6165
read_time+=record_count; // We have to make a temp table
6166
if (read_time < join->best_read)
6168
memcpy(join->best_positions, join->positions, sizeof(POSITION)*idx);
6169
join->best_read= read_time - 0.001;
6173
if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
6174
return(false); /* Found better before */
6177
double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
6178
for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
6180
table_map real_table_bit=s->table->map;
6181
if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
6182
(!idx|| !check_interleaving_with_nj(join->positions[idx-1].table, s)))
6184
double records, best;
6185
advance_sj_state(rest_tables, s);
6186
best_access_path(join, s, session, rest_tables, idx, record_count,
6188
records= join->positions[idx].records_read;
6189
best= join->positions[idx].read_time;
6191
Go to the next level only if there hasn't been a better key on
6192
this level! This will cut down the search for a lot simple cases!
6194
double current_record_count=record_count*records;
6195
double current_read_time=read_time+best;
6196
if (best_record_count > current_record_count ||
6197
best_read_time > current_read_time ||
6198
(idx == join->const_tables && s->table == join->sort_by_table))
6200
if (best_record_count >= current_record_count &&
6201
best_read_time >= current_read_time &&
6202
(!(s->key_dependent & rest_tables) || records < 2.0))
6204
best_record_count=current_record_count;
6205
best_read_time=current_read_time;
6207
std::swap(join->best_ref[idx], *pos);
6208
if (find_best(join,rest_tables & ~real_table_bit,idx+1,
6209
current_record_count,current_read_time))
6211
std::swap(join->best_ref[idx], *pos);
6213
restore_prev_nj_state(s);
6214
restore_prev_sj_state(rest_tables, s);
6215
if (join->select_options & SELECT_STRAIGHT_JOIN)
6216
break; // Don't test all combinations
847
6224
Find how much space the prevous read not const tables takes in cache.
849
void calc_used_field_length(Session *, JoinTable *join_tab)
6227
static void calc_used_field_length(Session *, JOIN_TAB *join_tab)
851
6229
uint32_t null_fields,blobs,fields,rec_length;
852
6230
Field **f_ptr,*field;
6231
MY_BITMAP *read_set= join_tab->table->read_set;;
854
6233
null_fields= blobs= fields= rec_length=0;
855
6234
for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
857
if (field->isReadSet())
6236
if (bitmap_is_set(read_set, field->field_index))
859
6238
uint32_t flags=field->flags;
861
6240
rec_length+=field->pack_length();
862
6241
if (flags & BLOB_FLAG)
864
6243
if (!(flags & NOT_NULL_FLAG))
868
6247
if (null_fields)
871
6250
rec_length+=sizeof(bool);
874
uint32_t blob_length=(uint32_t) (join_tab->table->cursor->stats.mean_rec_length-
875
(join_tab->table->getRecordLength()- rec_length));
876
rec_length+= max((uint32_t)4,blob_length);
878
join_tab->used_fields= fields;
879
join_tab->used_fieldlength= rec_length;
880
join_tab->used_blobs= blobs;
883
StoredKey *get_store_key(Session *session,
884
optimizer::KeyUse *keyuse,
885
table_map used_tables,
886
KEY_PART_INFO *key_part,
887
unsigned char *key_buff,
890
Item_ref *key_use_val= static_cast<Item_ref *>(keyuse->getVal());
891
if (! ((~used_tables) & keyuse->getUsedTables())) // if const item
6253
uint32_t blob_length=(uint32_t) (join_tab->table->file->stats.mean_rec_length-
6254
(join_tab->table->getRecordLength()- rec_length));
6255
rec_length+=(uint32_t) cmax((uint32_t)4,blob_length);
6257
join_tab->used_fields=fields;
6258
join_tab->used_fieldlength=rec_length;
6259
join_tab->used_blobs=blobs;
6264
cache_record_length(JOIN *join,uint32_t idx)
6267
JOIN_TAB **pos,**end;
6268
Session *session=join->session;
6270
for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
6274
JOIN_TAB *join_tab= *pos;
6275
if (!join_tab->used_fieldlength) /* Not calced yet */
6276
calc_used_field_length(session, join_tab);
6277
length+=join_tab->used_fieldlength;
6284
Get the number of different row combinations for subset of partial join
6288
join The join structure
6289
idx Number of tables in the partial join order (i.e. the
6290
partial join order is in join->positions[0..idx-1])
6291
found_ref Bitmap of tables for which we need to find # of distinct
6295
Given a partial join order (in join->positions[0..idx-1]) and a subset of
6296
tables within that join order (specified in found_ref), find out how many
6297
distinct row combinations of subset tables will be in the result of the
6300
This is used as follows: Suppose we have a table accessed with a ref-based
6301
method. The ref access depends on current rows of tables in found_ref.
6302
We want to count # of different ref accesses. We assume two ref accesses
6303
will be different if at least one of access parameters is different.
6304
Example: consider a query
6306
SELECT * FROM t1, t2, t3 WHERE t1.key=c1 AND t2.key=c2 AND t3.key=t1.field
6309
t1, ref access on t1.key=c1
6310
t2, ref access on t2.key=c2
6311
t3, ref access on t3.key=t1.field
6313
For t1: n_ref_scans = 1, n_distinct_ref_scans = 1
6314
For t2: n_ref_scans = records_read(t1), n_distinct_ref_scans=1
6315
For t3: n_ref_scans = records_read(t1)*records_read(t2)
6316
n_distinct_ref_scans = #records_read(t1)
6318
The reason for having this function (at least the latest version of it)
6319
is that we need to account for buffering in join execution.
6321
An edge-case example: if we have a non-first table in join accessed via
6322
ref(const) or ref(param) where there is a small number of different
6323
values of param, then the access will likely hit the disk cache and will
6324
not require any disk seeks.
6326
The proper solution would be to assume an LRU disk cache of some size,
6327
calculate probability of cache hits, etc. For now we just count
6328
identical ref accesses as one.
6331
Expected number of row combinations
6335
prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
6338
POSITION *pos_end= join->positions - 1;
6339
for (POSITION *pos= join->positions + idx - 1; pos != pos_end; pos--)
6341
if (pos->table->table->map & found_ref)
6343
found_ref|= pos->ref_depend_map;
6345
For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
6346
with no matching row we will get position[t2].records_read==0.
6347
Actually the size of output is one null-complemented row, therefore
6348
we will use value of 1 whenever we get records_read==0.
6351
- the above case can't occur if inner part of outer join has more
6352
than one table: table with no matches will not be marked as const.
6354
- Ideally we should add 1 to records_read for every possible null-
6355
complemented row. We're not doing it because: 1. it will require
6356
non-trivial code and add overhead. 2. The value of records_read
6357
is an inprecise estimate and adding 1 (or, in the worst case,
6358
#max_nested_outer_joins=64-1) will not make it any more precise.
6360
if (pos->records_read > DBL_EPSILON)
6361
found*= pos->records_read;
6369
Set up join struct according to best position.
6373
get_best_combination(JOIN *join)
6376
table_map used_tables;
6377
JOIN_TAB *join_tab,*j;
6379
uint32_t table_count;
6380
Session *session=join->session;
6382
table_count=join->tables;
6383
if (!(join->join_tab=join_tab=
6384
(JOIN_TAB*) session->alloc(sizeof(JOIN_TAB)*table_count)))
6389
used_tables= OUTER_REF_TABLE_BIT; // Outer row is already read
6390
for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
6393
*j= *join->best_positions[tablenr].table;
6394
form=join->table[tablenr]=j->table;
6395
used_tables|= form->map;
6396
form->reginfo.join_tab=j;
6397
if (!*j->on_expr_ref)
6398
form->reginfo.not_exists_optimize=0; // Only with LEFT JOIN
6399
if (j->type == JT_CONST)
6400
continue; // Handled in make_join_stat..
6405
if (j->type == JT_SYSTEM)
6407
if (j->keys.is_clear_all() || !(keyuse= join->best_positions[tablenr].key))
6410
if (tablenr != join->const_tables)
6413
else if (create_ref_for_key(join, j, keyuse, used_tables))
6414
return(true); // Something went wrong
6417
for (i=0 ; i < table_count ; i++)
6418
join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
6419
update_depend_map(join);
6424
static bool create_ref_for_key(JOIN *join, JOIN_TAB *j, KEYUSE *org_keyuse,
6425
table_map used_tables)
6427
KEYUSE *keyuse=org_keyuse;
6428
Session *session= join->session;
6429
uint32_t keyparts,length,key;
6433
/* Use best key from find_best */
6436
keyinfo=table->key_info+key;
6440
uint32_t found_part_ref_or_null= 0;
6442
Calculate length for the used key
6443
Stop if there is a missing key part or when we find second key_part
6444
with KEY_OPTIMIZE_REF_OR_NULL
6448
if (!(~used_tables & keyuse->used_tables))
6450
if (keyparts == keyuse->keypart &&
6451
!(found_part_ref_or_null & keyuse->optimize))
6454
length+= keyinfo->key_part[keyuse->keypart].store_length;
6455
found_part_ref_or_null|= keyuse->optimize;
6459
} while (keyuse->table == table && keyuse->key == key);
6462
/* set up fieldref */
6463
keyinfo=table->key_info+key;
6464
j->ref.key_parts=keyparts;
6465
j->ref.key_length=length;
6466
j->ref.key=(int) key;
6467
if (!(j->ref.key_buff= (unsigned char*) session->calloc(ALIGN_SIZE(length)*2)) ||
6468
!(j->ref.key_copy= (store_key**) session->alloc((sizeof(store_key*) *
6470
!(j->ref.items= (Item**) session->alloc(sizeof(Item*)*keyparts)) ||
6471
!(j->ref.cond_guards= (bool**) session->alloc(sizeof(uint*)*keyparts)))
6475
j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
6477
j->ref.null_rejecting= 0;
6478
j->ref.disable_cache= false;
6481
store_key **ref_key= j->ref.key_copy;
6482
unsigned char *key_buff=j->ref.key_buff, *null_ref_key= 0;
6483
bool keyuse_uses_no_tables= true;
6486
for (i=0 ; i < keyparts ; keyuse++,i++)
6488
while (keyuse->keypart != i ||
6489
((~used_tables) & keyuse->used_tables))
6490
keyuse++; /* Skip other parts */
6492
uint32_t maybe_null= test(keyinfo->key_part[i].null_bit);
6493
j->ref.items[i]=keyuse->val; // Save for cond removal
6494
j->ref.cond_guards[i]= keyuse->cond_guard;
6495
if (keyuse->null_rejecting)
6496
j->ref.null_rejecting |= 1 << i;
6497
keyuse_uses_no_tables= keyuse_uses_no_tables && !keyuse->used_tables;
6498
if (!keyuse->used_tables &&
6499
!(join->select_options & SELECT_DESCRIBE))
6500
{ // Compare against constant
6501
store_key_item tmp(session, keyinfo->key_part[i].field,
6502
key_buff + maybe_null,
6503
maybe_null ? key_buff : 0,
6504
keyinfo->key_part[i].length, keyuse->val);
6505
if (session->is_fatal_error)
6510
*ref_key++= get_store_key(session,
6511
keyuse,join->const_table_map,
6512
&keyinfo->key_part[i],
6513
key_buff, maybe_null);
6515
Remember if we are going to use REF_OR_NULL
6516
But only if field _really_ can be null i.e. we force JT_REF
6517
instead of JT_REF_OR_NULL in case if field can't be null
6519
if ((keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL) && maybe_null)
6520
null_ref_key= key_buff;
6521
key_buff+=keyinfo->key_part[i].store_length;
6524
*ref_key=0; // end_marker
6525
if (j->type == JT_CONST)
6526
j->table->const_table= 1;
6527
else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
6528
keyparts != keyinfo->key_parts || null_ref_key)
6530
/* Must read with repeat */
6531
j->type= null_ref_key ? JT_REF_OR_NULL : JT_REF;
6532
j->ref.null_ref_key= null_ref_key;
6534
else if (keyuse_uses_no_tables)
6537
This happen if we are using a constant expression in the ON part
6539
SELECT * FROM a LEFT JOIN b ON b.key=30
6540
Here we should not mark the table as a 'const' as a field may
6541
have a 'normal' value or a NULL value.
6553
get_store_key(Session *session, KEYUSE *keyuse, table_map used_tables,
6554
KEY_PART_INFO *key_part, unsigned char *key_buff, uint32_t maybe_null)
6556
if (!((~used_tables) & keyuse->used_tables)) // if const item
893
6558
return new store_key_const_item(session,
894
6559
key_part->field,
895
6560
key_buff + maybe_null,
896
6561
maybe_null ? key_buff : 0,
897
6562
key_part->length,
900
else if (key_use_val->type() == Item::FIELD_ITEM ||
901
(key_use_val->type() == Item::REF_ITEM &&
902
key_use_val->ref_type() == Item_ref::OUTER_REF &&
903
(*(Item_ref**)((Item_ref*)key_use_val)->ref)->ref_type() == Item_ref::DIRECT_REF &&
904
key_use_val->real_item()->type() == Item::FIELD_ITEM))
6565
else if (keyuse->val->type() == Item::FIELD_ITEM ||
6566
(keyuse->val->type() == Item::REF_ITEM &&
6567
((Item_ref*)keyuse->val)->ref_type() == Item_ref::OUTER_REF &&
6568
(*(Item_ref**)((Item_ref*)keyuse->val)->ref)->ref_type() ==
6569
Item_ref::DIRECT_REF &&
6570
keyuse->val->real_item()->type() == Item::FIELD_ITEM))
906
6571
return new store_key_field(session,
907
6572
key_part->field,
908
6573
key_buff + maybe_null,
909
6574
maybe_null ? key_buff : 0,
910
6575
key_part->length,
911
((Item_field*) key_use_val->real_item())->field,
912
key_use_val->full_name());
6576
((Item_field*) keyuse->val->real_item())->field,
6577
keyuse->val->full_name());
914
6578
return new store_key_item(session,
915
6579
key_part->field,
916
6580
key_buff + maybe_null,
917
6581
maybe_null ? key_buff : 0,
918
6582
key_part->length,
6827
Fill in outer join related info for the execution plan structure.
6829
For each outer join operation left after simplification of the
6830
original query the function set up the following pointers in the linear
6831
structure join->join_tab representing the selected execution plan.
6832
The first inner table t0 for the operation is set to refer to the last
6833
inner table tk through the field t0->last_inner.
6834
Any inner table ti for the operation are set to refer to the first
6835
inner table ti->first_inner.
6836
The first inner table t0 for the operation is set to refer to the
6837
first inner table of the embedding outer join operation, if there is any,
6838
through the field t0->first_upper.
6839
The on expression for the outer join operation is attached to the
6840
corresponding first inner table through the field t0->on_expr_ref.
6841
Here ti are structures of the JOIN_TAB type.
6843
EXAMPLE. For the query:
6847
(t2, t3 LEFT JOIN t4 ON t3.a=t4.a)
6848
ON (t1.a=t2.a AND t1.b=t3.b)
6852
given the execution plan with the table order t1,t2,t3,t4
6853
is selected, the following references will be set;
6854
t4->last_inner=[t4], t4->first_inner=[t4], t4->first_upper=[t2]
6855
t2->last_inner=[t4], t2->first_inner=t3->first_inner=[t2],
6856
on expression (t1.a=t2.a AND t1.b=t3.b) will be attached to
6857
*t2->on_expr_ref, while t3.a=t4.a will be attached to *t4->on_expr_ref.
6859
@param join reference to the info fully describing the query
6862
The function assumes that the simplification procedure has been
6863
already applied to the join query (see simplify_joins).
6864
This function can be called only after the execution plan
6869
make_outerjoin_info(JOIN *join)
6871
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6873
JOIN_TAB *tab=join->join_tab+i;
6874
Table *table=tab->table;
6875
TableList *tbl= table->pos_in_table_list;
6876
TableList *embedding= tbl->embedding;
6878
if (tbl->outer_join)
6881
Table tab is the only one inner table for outer join.
6882
(Like table t4 for the table reference t3 LEFT JOIN t4 ON t3.a=t4.a
6883
is in the query above.)
6885
tab->last_inner= tab->first_inner= tab;
6886
tab->on_expr_ref= &tbl->on_expr;
6887
tab->cond_equal= tbl->cond_equal;
6889
tab->first_upper= embedding->nested_join->first_nested;
6891
for ( ; embedding ; embedding= embedding->embedding)
6893
/* Ignore sj-nests: */
6894
if (!embedding->on_expr)
6896
nested_join_st *nested_join= embedding->nested_join;
6897
if (!nested_join->counter_)
6900
Table tab is the first inner table for nested_join.
6901
Save reference to it in the nested join structure.
6903
nested_join->first_nested= tab;
6904
tab->on_expr_ref= &embedding->on_expr;
6905
tab->cond_equal= tbl->cond_equal;
6906
if (embedding->embedding)
6907
tab->first_upper= embedding->embedding->nested_join->first_nested;
6909
if (!tab->first_inner)
6910
tab->first_inner= nested_join->first_nested;
6911
if (++nested_join->counter_ < nested_join->join_list.elements)
6913
/* Table tab is the last inner table for nested join. */
6914
nested_join->first_nested->last_inner= tab;
6922
make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
6924
Session *session= join->session;
6927
add_not_null_conds(join);
6928
table_map used_tables;
6929
if (cond) /* Because of QUICK_GROUP_MIN_MAX_SELECT */
6930
{ /* there may be a select without a cond. */
6931
if (join->tables > 1)
6932
cond->update_used_tables(); // Tablenr may have changed
6933
if (join->const_tables == join->tables &&
6934
session->lex->current_select->master_unit() ==
6935
&session->lex->unit) // not upper level SELECT
6936
join->const_table_map|=RAND_TABLE_BIT;
6937
{ // Check const tables
6939
make_cond_for_table(cond,
6940
join->const_table_map,
6942
for (JOIN_TAB *tab= join->join_tab+join->const_tables;
6943
tab < join->join_tab+join->tables ; tab++)
6945
if (*tab->on_expr_ref)
6947
JOIN_TAB *cond_tab= tab->first_inner;
6948
COND *tmp= make_cond_for_table(*tab->on_expr_ref,
6949
join->const_table_map,
6953
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
6956
tmp->quick_fix_field();
6957
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
6958
new Item_cond_and(cond_tab->select_cond,
6960
if (!cond_tab->select_cond)
6962
cond_tab->select_cond->quick_fix_field();
6965
if (const_cond && !const_cond->val_int())
6967
return(1); // Impossible const condition
6971
used_tables=((select->const_tables=join->const_table_map) |
6972
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
6973
for (uint32_t i=join->const_tables ; i < join->tables ; i++)
6975
JOIN_TAB *tab=join->join_tab+i;
6977
first_inner is the X in queries like:
6978
SELECT * FROM t1 LEFT OUTER JOIN (t2 JOIN t3) ON X
6980
JOIN_TAB *first_inner_tab= tab->first_inner;
6981
table_map current_map= tab->table->map;
6982
bool use_quick_range=0;
6986
Following force including random expression in last table condition.
6987
It solve problem with select like SELECT * FROM t1 WHERE rand() > 0.5
6989
if (i == join->tables-1)
6990
current_map|= OUTER_REF_TABLE_BIT | RAND_TABLE_BIT;
6991
used_tables|=current_map;
6993
if (tab->type == JT_REF && tab->quick &&
6994
(uint32_t) tab->ref.key == tab->quick->index &&
6995
tab->ref.key_length < tab->quick->max_used_key_length)
6997
/* Range uses longer key; Use this instead of ref on key */
7002
tab->ref.key_parts=0; // Don't use ref key.
7003
join->best_positions[i].records_read= rows2double(tab->quick->records);
7005
We will use join cache here : prevent sorting of the first
7006
table only and sort at the end.
7008
if (i != join->const_tables && join->tables > join->const_tables + 1)
7014
tmp= make_cond_for_table(cond,used_tables,current_map, 0);
7015
if (cond && !tmp && tab->quick)
7017
if (tab->type != JT_ALL)
7020
Don't use the quick method
7021
We come here in the case where we have 'key=constant' and
7022
the test is removed by make_cond_for_table()
7030
Hack to handle the case where we only refer to a table
7031
in the ON part of an OUTER JOIN. In this case we want the code
7032
below to check if we should use 'quick' instead.
7034
tmp= new Item_int((int64_t) 1,1); // Always true
7038
if (tmp || !cond || tab->type == JT_REF || tab->type == JT_REF_OR_NULL ||
7039
tab->type == JT_EQ_REF)
7041
SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
7042
session->memdup((unsigned char*) select,
7045
return(1); // End of memory
7047
If tab is an inner table of an outer join operation,
7048
add a match guard to the pushed down predicate.
7049
The guard will turn the predicate on only after
7050
the first match for outer tables is encountered.
7055
Because of QUICK_GROUP_MIN_MAX_SELECT there may be a select without
7056
a cond, so neutralize the hack above.
7058
if (!(tmp= add_found_match_trig_cond(first_inner_tab, tmp, 0)))
7060
tab->select_cond=sel->cond=tmp;
7061
/* Push condition to storage engine if this is enabled
7062
and the condition is not guarded */
7063
tab->table->file->pushed_cond= NULL;
7064
if (session->variables.engine_condition_pushdown)
7067
make_cond_for_table(tmp, current_map, current_map, 0);
7070
/* Push condition to handler */
7071
if (!tab->table->file->cond_push(push_cond))
7072
tab->table->file->pushed_cond= push_cond;
7077
tab->select_cond= sel->cond= NULL;
7079
sel->head=tab->table;
7082
/* Use quick key read if it's a constant and it's not used
7084
if (tab->needed_reg.is_clear_all() && tab->type != JT_EQ_REF
7085
&& (tab->type != JT_REF || (uint32_t) tab->ref.key == tab->quick->index))
7087
sel->quick=tab->quick; // Use value from get_quick_...
7088
sel->quick_keys.clear_all();
7089
sel->needed_reg.clear_all();
7097
uint32_t ref_key=(uint32_t) sel->head->reginfo.join_tab->ref.key+1;
7098
if (i == join->const_tables && ref_key)
7100
if (!tab->const_keys.is_clear_all() &&
7101
tab->table->reginfo.impossible_range)
7104
else if (tab->type == JT_ALL && ! use_quick_range)
7106
if (!tab->const_keys.is_clear_all() &&
7107
tab->table->reginfo.impossible_range)
7108
return(1); // Impossible range
7110
We plan to scan all rows.
7111
Check again if we should use an index.
7112
We could have used an column from a previous table in
7113
the index if we are using limit and this is the first table
7116
if ((cond && (!tab->keys.is_subset(tab->const_keys) && i > 0)) ||
7117
(!tab->const_keys.is_clear_all() && (i == join->const_tables) && (join->unit->select_limit_cnt < join->best_positions[i].records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
7119
/* Join with outer join condition */
7120
COND *orig_cond=sel->cond;
7121
sel->cond= and_conds(sel->cond, *tab->on_expr_ref);
7124
We can't call sel->cond->fix_fields,
7125
as it will break tab->on_expr if it's AND condition
7126
(fix_fields currently removes extra AND/OR levels).
7127
Yet attributes of the just built condition are not needed.
7128
Thus we call sel->cond->quick_fix_field for safety.
7130
if (sel->cond && !sel->cond->fixed)
7131
sel->cond->quick_fix_field();
7133
if (sel->test_quick_select(session, tab->keys,
7134
used_tables & ~ current_map,
7135
(join->select_options &
7138
join->unit->select_limit_cnt), 0,
7142
Before reporting "Impossible WHERE" for the whole query
7143
we have to check isn't it only "impossible ON" instead
7145
sel->cond=orig_cond;
7146
if (!*tab->on_expr_ref ||
7147
sel->test_quick_select(session, tab->keys,
7148
used_tables & ~ current_map,
7149
(join->select_options &
7152
join->unit->select_limit_cnt),0,
7154
return(1); // Impossible WHERE
7157
sel->cond=orig_cond;
7159
/* Fix for EXPLAIN */
7161
join->best_positions[i].records_read= (double)sel->quick->records;
7165
sel->needed_reg=tab->needed_reg;
7166
sel->quick_keys.clear_all();
7168
if (!sel->quick_keys.is_subset(tab->checked_keys) ||
7169
!sel->needed_reg.is_subset(tab->checked_keys))
7171
tab->keys=sel->quick_keys;
7172
tab->keys.merge(sel->needed_reg);
7173
tab->use_quick= (!sel->needed_reg.is_clear_all() &&
7174
(select->quick_keys.is_clear_all() ||
7176
(select->quick->records >= 100L)))) ?
7178
sel->read_tables= used_tables & ~current_map;
7180
if (i != join->const_tables && tab->use_quick != 2)
7181
{ /* Read with cache */
7183
(tmp=make_cond_for_table(cond,
7184
join->const_table_map |
7188
tab->cache.select=(SQL_SELECT*)
7189
session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
7190
tab->cache.select->cond=tmp;
7191
tab->cache.select->read_tables=join->const_table_map;
7198
Push down conditions from all on expressions.
7199
Each of these conditions are guarded by a variable
7200
that turns if off just before null complemented row for
7201
outer joins is formed. Thus, the condition from an
7202
'on expression' are guaranteed not to be checked for
7203
the null complemented row.
7206
/* First push down constant conditions from on expressions */
7207
for (JOIN_TAB *join_tab= join->join_tab+join->const_tables;
7208
join_tab < join->join_tab+join->tables ; join_tab++)
7210
if (*join_tab->on_expr_ref)
7212
JOIN_TAB *cond_tab= join_tab->first_inner;
7213
tmp= make_cond_for_table(*join_tab->on_expr_ref,
7214
join->const_table_map,
7218
tmp= new Item_func_trig_cond(tmp, &cond_tab->not_null_compl);
7221
tmp->quick_fix_field();
7222
cond_tab->select_cond= !cond_tab->select_cond ? tmp :
7223
new Item_cond_and(cond_tab->select_cond,tmp);
7224
if (!cond_tab->select_cond)
7226
cond_tab->select_cond->quick_fix_field();
7230
/* Push down non-constant conditions from on expressions */
7231
JOIN_TAB *last_tab= tab;
7232
while (first_inner_tab && first_inner_tab->last_inner == last_tab)
7235
Table tab is the last inner table of an outer join.
7236
An on expression is always attached to it.
7238
COND *on_expr= *first_inner_tab->on_expr_ref;
7240
table_map used_tables2= (join->const_table_map |
7241
OUTER_REF_TABLE_BIT | RAND_TABLE_BIT);
7242
for (tab= join->join_tab+join->const_tables; tab <= last_tab ; tab++)
7244
current_map= tab->table->map;
7245
used_tables2|= current_map;
7246
COND *tmp_cond= make_cond_for_table(on_expr, used_tables2,
7250
JOIN_TAB *cond_tab= tab < first_inner_tab ? first_inner_tab : tab;
7252
First add the guards for match variables of
7253
all embedding outer join operations.
7255
if (!(tmp_cond= add_found_match_trig_cond(cond_tab->first_inner,
7260
Now add the guard turning the predicate off for
7261
the null complemented row.
7263
tmp_cond= new Item_func_trig_cond(tmp_cond,
7267
tmp_cond->quick_fix_field();
7268
/* Add the predicate to other pushed down predicates */
7269
cond_tab->select_cond= !cond_tab->select_cond ? tmp_cond :
7270
new Item_cond_and(cond_tab->select_cond,
7272
if (!cond_tab->select_cond)
7274
cond_tab->select_cond->quick_fix_field();
7277
first_inner_tab= first_inner_tab->first_upper;
1215
7286
Check if given expression uses only table fields covered by the given index
2744
9590
if (!(left_const && right_const) &&
2745
9591
args[0]->result_type() == args[1]->result_type())
2749
resolve_const_item(session, &args[1], args[0]);
2750
func->update_used_tables();
2751
change_cond_ref_to_const(session, save_list, and_father, and_father,
2754
else if (left_const)
2756
resolve_const_item(session, &args[0], args[1]);
2757
func->update_used_tables();
2758
change_cond_ref_to_const(session, save_list, and_father, and_father,
9595
resolve_const_item(session, &args[1], args[0]);
9596
func->update_used_tables();
9597
change_cond_ref_to_const(session, save_list, and_father, and_father,
9600
else if (left_const)
9602
resolve_const_item(session, &args[0], args[1]);
9603
func->update_used_tables();
9604
change_cond_ref_to_const(session, save_list, and_father, and_father,
9614
Simplify joins replacing outer joins by inner joins whenever it's
9617
The function, during a retrieval of join_list, eliminates those
9618
outer joins that can be converted into inner join, possibly nested.
9619
It also moves the on expressions for the converted outer joins
9620
and from inner joins to conds.
9621
The function also calculates some attributes for nested joins:
9625
- on_expr_dep_tables
9626
The first two attributes are used to test whether an outer join can
9627
be substituted for an inner join. The third attribute represents the
9628
relation 'to be dependent on' for tables. If table t2 is dependent
9629
on table t1, then in any evaluated execution plan table access to
9630
table t2 must precede access to table t2. This relation is used also
9631
to check whether the query contains invalid cross-references.
9632
The forth attribute is an auxiliary one and is used to calculate
9634
As the attribute dep_tables qualifies possibles orders of tables in the
9635
execution plan, the dependencies required by the straight join
9636
modifiers are reflected in this attribute as well.
9637
The function also removes all braces that can be removed from the join
9638
expression without changing its meaning.
9641
An outer join can be replaced by an inner join if the where condition
9642
or the on expression for an embedding nested join contains a conjunctive
9643
predicate rejecting null values for some attribute of the inner tables.
9647
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9649
the predicate t2.b < 5 rejects nulls.
9650
The query is converted first to:
9652
SELECT * FROM t1 INNER JOIN t2 ON t2.a=t1.a WHERE t2.b < 5
9654
then to the equivalent form:
9656
SELECT * FROM t1, t2 ON t2.a=t1.a WHERE t2.b < 5 AND t2.a=t1.a
9660
Similarly the following query:
9662
SELECT * from t1 LEFT JOIN (t2, t3) ON t2.a=t1.a t3.b=t1.b
9667
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a t3.b=t1.b
9671
One conversion might trigger another:
9673
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a
9674
LEFT JOIN t3 ON t3.b=t2.b
9675
WHERE t3 IS NOT NULL =>
9676
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t1.a, t3
9677
WHERE t3 IS NOT NULL AND t3.b=t2.b =>
9678
SELECT * FROM t1, t2, t3
9679
WHERE t3 IS NOT NULL AND t3.b=t2.b AND t2.a=t1.a
9682
The function removes all unnecessary braces from the expression
9683
produced by the conversions.
9686
SELECT * FROM t1, (t2, t3) WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9688
finally is converted to:
9690
SELECT * FROM t1, t2, t3 WHERE t2.c < 5 AND t2.a=t1.a AND t3.b=t1.b
9695
It also will remove braces from the following queries:
9697
SELECT * from (t1 LEFT JOIN t2 ON t2.a=t1.a) LEFT JOIN t3 ON t3.b=t2.b
9698
SELECT * from (t1, (t2,t3)) WHERE t1.a=t2.a AND t2.b=t3.b.
9701
The benefit of this simplification procedure is that it might return
9702
a query for which the optimizer can evaluate execution plan with more
9703
join orders. With a left join operation the optimizer does not
9704
consider any plan where one of the inner tables is before some of outer
9708
The function is implemented by a recursive procedure. On the recursive
9709
ascent all attributes are calculated, all outer joins that can be
9710
converted are replaced and then all unnecessary braces are removed.
9711
As join list contains join tables in the reverse order sequential
9712
elimination of outer joins does not require extra recursive calls.
9715
Remove all semi-joins that have are within another semi-join (i.e. have
9716
an "ancestor" semi-join nest)
9719
Here is an example of a join query with invalid cross references:
9721
SELECT * FROM t1 LEFT JOIN t2 ON t2.a=t3.a LEFT JOIN t3 ON t3.b=t1.b
9724
@param join reference to the query info
9725
@param join_list list representation of the join to be converted
9726
@param conds conditions to add on expressions for converted joins
9727
@param top true <=> conds is the where condition
9730
- The new condition, if success
9735
simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top,
9739
nested_join_st *nested_join;
9740
TableList *prev_table= 0;
9741
List_iterator<TableList> li(*join_list);
9744
Try to simplify join operations from join_list.
9745
The most outer join operation is checked for conversion first.
9747
while ((table= li++))
9749
table_map used_tables;
9750
table_map not_null_tables= (table_map) 0;
9752
if ((nested_join= table->nested_join))
9755
If the element of join_list is a nested join apply
9756
the procedure to its nested join list first.
9760
Item *expr= table->on_expr;
9762
If an on expression E is attached to the table,
9763
check all null rejected predicates in this expression.
9764
If such a predicate over an attribute belonging to
9765
an inner table of an embedded outer join is found,
9766
the outer join is converted to an inner join and
9767
the corresponding on expression is added to E.
9769
expr= simplify_joins(join, &nested_join->join_list,
9770
expr, false, in_sj || table->sj_on_expr);
9772
if (!table->prep_on_expr || expr != table->on_expr)
9776
table->on_expr= expr;
9777
table->prep_on_expr= expr->copy_andor_structure(join->session);
9780
nested_join->used_tables= (table_map) 0;
9781
nested_join->not_null_tables=(table_map) 0;
9782
conds= simplify_joins(join, &nested_join->join_list, conds, top,
9783
in_sj || table->sj_on_expr);
9784
used_tables= nested_join->used_tables;
9785
not_null_tables= nested_join->not_null_tables;
9789
if (!table->prep_on_expr)
9790
table->prep_on_expr= table->on_expr;
9791
used_tables= table->table->map;
9793
not_null_tables= conds->not_null_tables();
9796
if (table->embedding)
9798
table->embedding->nested_join->used_tables|= used_tables;
9799
table->embedding->nested_join->not_null_tables|= not_null_tables;
9802
if (!table->outer_join || (used_tables & not_null_tables))
9805
For some of the inner tables there are conjunctive predicates
9806
that reject nulls => the outer join can be replaced by an inner join.
9808
table->outer_join= 0;
9811
/* Add ON expression to the WHERE or upper-level ON condition. */
9814
conds= and_conds(conds, table->on_expr);
9815
conds->top_level_item();
9816
/* conds is always a new item as both cond and on_expr existed */
9817
assert(!conds->fixed);
9818
conds->fix_fields(join->session, &conds);
9821
conds= table->on_expr;
9822
table->prep_on_expr= table->on_expr= 0;
9830
Only inner tables of non-convertible outer joins
9831
remain with on_expr.
9835
table->dep_tables|= table->on_expr->used_tables();
9836
if (table->embedding)
9838
table->dep_tables&= ~table->embedding->nested_join->used_tables;
9840
Embedding table depends on tables used
9841
in embedded on expressions.
9843
table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
9846
table->dep_tables&= ~table->table->map;
9851
/* The order of tables is reverse: prev_table follows table */
9852
if (prev_table->straight)
9853
prev_table->dep_tables|= used_tables;
9854
if (prev_table->on_expr)
9856
prev_table->dep_tables|= table->on_expr_dep_tables;
9857
table_map prev_used_tables= prev_table->nested_join ?
9858
prev_table->nested_join->used_tables :
9859
prev_table->table->map;
9861
If on expression contains only references to inner tables
9862
we still make the inner tables dependent on the outer tables.
9863
It would be enough to set dependency only on one outer table
9864
for them. Yet this is really a rare case.
9866
if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
9867
prev_table->dep_tables|= used_tables;
9874
Flatten nested joins that can be flattened.
9875
no ON expression and not a semi-join => can be flattened.
9878
while ((table= li++))
9880
nested_join= table->nested_join;
9881
if (table->sj_on_expr && !in_sj)
9884
If this is a semi-join that is not contained within another semi-join,
9885
leave it intact (otherwise it is flattened)
9887
join->select_lex->sj_nests.push_back(table);
9889
else if (nested_join && !table->on_expr)
9892
List_iterator<TableList> it(nested_join->join_list);
9895
tbl->embedding= table->embedding;
9896
tbl->join_list= table->join_list;
9898
li.replace(nested_join->join_list);
9906
Assign each nested join structure a bit in nested_join_map.
9908
Assign each nested join structure (except "confluent" ones - those that
9909
embed only one element) a bit in nested_join_map.
9911
@param join Join being processed
9912
@param join_list List of tables
9913
@param first_unused Number of first unused bit in nested_join_map before the
9917
This function is called after simplify_joins(), when there are no
9918
redundant nested joins, #non_confluent_nested_joins <= #tables_in_join so
9919
we will not run out of bits in nested_join_map.
9922
First unused bit in nested_join_map after the call.
9925
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list,
9926
uint32_t first_unused)
9928
List_iterator<TableList> li(*join_list);
9930
while ((table= li++))
9932
nested_join_st *nested_join;
9933
if ((nested_join= table->nested_join))
9936
It is guaranteed by simplify_joins() function that a nested join
9937
that has only one child is either
9938
- a single-table view (the child is the underlying table), or
9939
- a single-table semi-join nest
9941
We don't assign bits to such sj-nests because
9942
1. it is redundant (a "sequence" of one table cannot be interleaved
9944
2. we could run out bits in nested_join_map otherwise.
9946
if (nested_join->join_list.elements != 1)
9948
/* Don't assign bits to sj-nests */
9950
nested_join->nj_map= (nested_join_map) 1 << first_unused++;
9951
first_unused= build_bitmap_for_nested_joins(&nested_join->join_list,
9956
return(first_unused);
9961
Set nested_join_st::counter=0 in all nested joins in passed list.
9963
Recursively set nested_join_st::counter=0 for all nested joins contained in
9964
the passed join_list.
9966
@param join_list List of nested joins to process. It may also contain base
9967
tables which will be ignored.
9970
static void reset_nj_counters(List<TableList> *join_list)
9972
List_iterator<TableList> li(*join_list);
9974
while ((table= li++))
9976
nested_join_st *nested_join;
9977
if ((nested_join= table->nested_join))
9979
nested_join->counter_= 0;
9980
reset_nj_counters(&nested_join->join_list);
2767
9988
Check interleaving with an inner tables of an outer join for
3585
int safe_index_read(JoinTable *tab)
10902
SemiJoinDuplicateElimination: Weed out duplicate row combinations
10905
do_sj_dups_weedout()
10909
1 The row combination is a duplicate (discard it)
10910
0 The row combination is not a duplicate (continue)
10913
int do_sj_dups_weedout(Session *session, SJ_TMP_TABLE *sjtbl)
10916
SJ_TMP_TABLE::TAB *tab= sjtbl->tabs;
10917
SJ_TMP_TABLE::TAB *tab_end= sjtbl->tabs_end;
10918
unsigned char *ptr= sjtbl->tmp_table->record[0] + 1;
10919
unsigned char *nulls_ptr= ptr;
10921
/* Put the the rowids tuple into table->record[0]: */
10923
// 1. Store the length
10924
if (((Field_varstring*)(sjtbl->tmp_table->field[0]))->length_bytes == 1)
10926
*ptr= (unsigned char)(sjtbl->rowid_len + sjtbl->null_bytes);
10931
int2store(ptr, sjtbl->rowid_len + sjtbl->null_bytes);
10935
// 2. Zero the null bytes
10936
if (sjtbl->null_bytes)
10938
memset(ptr, 0, sjtbl->null_bytes);
10939
ptr += sjtbl->null_bytes;
10942
// 3. Put the rowids
10943
for (uint32_t i=0; tab != tab_end; tab++, i++)
10945
handler *h= tab->join_tab->table->file;
10946
if (tab->join_tab->table->maybe_null && tab->join_tab->table->null_row)
10948
/* It's a NULL-complemented row */
10949
*(nulls_ptr + tab->null_byte) |= tab->null_bit;
10950
memset(ptr + tab->rowid_offset, 0, h->ref_length);
10954
/* Copy the rowid value */
10955
if (tab->join_tab->rowid_keep_flags & JOIN_TAB::CALL_POSITION)
10956
h->position(tab->join_tab->table->record[0]);
10957
memcpy(ptr + tab->rowid_offset, h->ref, h->ref_length);
10961
error= sjtbl->tmp_table->file->ha_write_row(sjtbl->tmp_table->record[0]);
10964
/* create_myisam_from_heap will generate error if needed */
10965
if (sjtbl->tmp_table->file->is_fatal_error(error, HA_CHECK_DUP) &&
10966
create_myisam_from_heap(session, sjtbl->tmp_table, sjtbl->start_recinfo,
10967
&sjtbl->recinfo, error, 1))
10969
//return (error == HA_ERR_FOUND_DUPP_KEY || error== HA_ERR_FOUND_DUPP_UNIQUE) ? 1: -1;
10977
SemiJoinDuplicateElimination: Reset the temporary table
10980
int do_sj_reset(SJ_TMP_TABLE *sj_tbl)
10982
if (sj_tbl->tmp_table)
10983
return sj_tbl->tmp_table->file->ha_delete_all_rows();
10988
Process one record of the nested loop join.
10990
This function will evaluate parts of WHERE/ON clauses that are
10991
applicable to the partial record on hand and in case of success
10992
submit this record to the next level of the nested loop.
10995
static enum_nested_loop_state
10996
evaluate_join_record(JOIN *join, JOIN_TAB *join_tab,
10999
bool not_used_in_distinct=join_tab->not_used_in_distinct;
11000
ha_rows found_records=join->found_records;
11001
COND *select_cond= join_tab->select_cond;
11003
if (error > 0 || (join->session->is_error())) // Fatal error
11004
return NESTED_LOOP_ERROR;
11006
return NESTED_LOOP_NO_MORE_ROWS;
11007
if (join->session->killed) // Aborted by user
11009
join->session->send_kill_message();
11010
return NESTED_LOOP_KILLED; /* purecov: inspected */
11012
if (!select_cond || select_cond->val_int())
11015
There is no select condition or the attached pushed down
11016
condition is true => a match is found.
11019
while (join_tab->first_unmatched && found)
11022
The while condition is always false if join_tab is not
11023
the last inner join table of an outer join operation.
11025
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11027
Mark that a match for current outer table is found.
11028
This activates push down conditional predicates attached
11029
to the all inner tables of the outer join.
11031
first_unmatched->found= 1;
11032
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11034
if (tab->table->reginfo.not_exists_optimize)
11035
return NESTED_LOOP_NO_MORE_ROWS;
11036
/* Check all predicates that has just been activated. */
11038
Actually all predicates non-guarded by first_unmatched->found
11039
will be re-evaluated again. It could be fixed, but, probably,
11040
it's not worth doing now.
11042
if (tab->select_cond && !tab->select_cond->val_int())
11044
/* The condition attached to table tab is false */
11045
if (tab == join_tab)
11050
Set a return point if rejected predicate is attached
11051
not to the last table of the current nest level.
11053
join->return_tab= tab;
11054
return NESTED_LOOP_OK;
11059
Check whether join_tab is not the last inner table
11060
for another embedding outer join.
11062
if ((first_unmatched= first_unmatched->first_upper) &&
11063
first_unmatched->last_inner != join_tab)
11064
first_unmatched= 0;
11065
join_tab->first_unmatched= first_unmatched;
11068
JOIN_TAB *return_tab= join->return_tab;
11069
join_tab->found_match= true;
11070
if (join_tab->check_weed_out_table)
11072
int res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table);
11074
return NESTED_LOOP_ERROR;
11076
return NESTED_LOOP_OK;
11078
else if (join_tab->do_firstmatch)
11081
We should return to the join_tab->do_firstmatch after we have
11082
enumerated all the suffixes for current prefix row combination
11084
return_tab= join_tab->do_firstmatch;
11088
It was not just a return to lower loop level when one
11089
of the newly activated predicates is evaluated as false
11090
(See above join->return_tab= tab).
11092
join->examined_rows++;
11093
join->session->row_count++;
11097
enum enum_nested_loop_state rc;
11098
/* A match from join_tab is found for the current partial join. */
11099
rc= (*join_tab->next_select)(join, join_tab+1, 0);
11100
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11102
if (return_tab < join->return_tab)
11103
join->return_tab= return_tab;
11105
if (join->return_tab < join_tab)
11106
return NESTED_LOOP_OK;
11108
Test if this was a SELECT DISTINCT query on a table that
11109
was not in the field list; In this case we can abort if
11110
we found a row, as no new rows can be added to the result.
11112
if (not_used_in_distinct && found_records != join->found_records)
11113
return NESTED_LOOP_NO_MORE_ROWS;
11116
join_tab->read_record.file->unlock_row();
11121
The condition pushed down to the table join_tab rejects all rows
11122
with the beginning coinciding with the current partial join.
11124
join->examined_rows++;
11125
join->session->row_count++;
11126
join_tab->read_record.file->unlock_row();
11128
return NESTED_LOOP_OK;
11135
Construct a NULL complimented partial join record and feed it to the next
11136
level of the nested loop. This function is used in case we have
11137
an OUTER join and no matching record was found.
11140
static enum_nested_loop_state
11141
evaluate_null_complemented_join_record(JOIN *join, JOIN_TAB *join_tab)
11144
The table join_tab is the first inner table of a outer join operation
11145
and no matches has been found for the current outer row.
11147
JOIN_TAB *last_inner_tab= join_tab->last_inner;
11148
/* Cache variables for faster loop */
11150
for ( ; join_tab <= last_inner_tab ; join_tab++)
11152
/* Change the the values of guard predicate variables. */
11153
join_tab->found= 1;
11154
join_tab->not_null_compl= 0;
11155
/* The outer row is complemented by nulls for each inner tables */
11156
restore_record(join_tab->table,s->default_values); // Make empty record
11157
join_tab->table->mark_as_null_row(); // For group by without error
11158
select_cond= join_tab->select_cond;
11159
/* Check all attached conditions for inner table rows. */
11160
if (select_cond && !select_cond->val_int())
11161
return NESTED_LOOP_OK;
11165
The row complemented by nulls might be the first row
11166
of embedding outer joins.
11167
If so, perform the same actions as in the code
11168
for the first regular outer join row above.
11172
JOIN_TAB *first_unmatched= join_tab->first_unmatched;
11173
if ((first_unmatched= first_unmatched->first_upper) &&
11174
first_unmatched->last_inner != join_tab)
11175
first_unmatched= 0;
11176
join_tab->first_unmatched= first_unmatched;
11177
if (!first_unmatched)
11179
first_unmatched->found= 1;
11180
for (JOIN_TAB *tab= first_unmatched; tab <= join_tab; tab++)
11182
if (tab->select_cond && !tab->select_cond->val_int())
11184
join->return_tab= tab;
11185
return NESTED_LOOP_OK;
11190
The row complemented by nulls satisfies all conditions
11191
attached to inner tables.
11192
Send the row complemented by nulls to be joined with the
11195
return (*join_tab->next_select)(join, join_tab+1, 0);
11199
static enum_nested_loop_state
11200
flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skip_last)
11202
enum_nested_loop_state rc= NESTED_LOOP_OK;
11206
join_tab->table->null_row= 0;
11207
if (!join_tab->cache.records)
11208
return NESTED_LOOP_OK; /* Nothing to do */
11210
(void) store_record_in_cache(&join_tab->cache); // Must save this for later
11211
if (join_tab->use_quick == 2)
11213
if (join_tab->select->quick)
11214
{ /* Used quick select last. reset it */
11215
delete join_tab->select->quick;
11216
join_tab->select->quick=0;
11219
/* read through all records */
11220
if ((error=join_init_read_record(join_tab)))
11222
reset_cache_write(&join_tab->cache);
11223
return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
11226
for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
11228
tmp->status=tmp->table->status;
11229
tmp->table->status=0;
11232
info= &join_tab->read_record;
11235
if (join->session->killed)
11237
join->session->send_kill_message();
11238
return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
11240
SQL_SELECT *select=join_tab->select;
11241
if (rc == NESTED_LOOP_OK &&
11242
(!join_tab->cache.select || !join_tab->cache.select->skip_record()))
11245
reset_cache_read(&join_tab->cache);
11246
for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
11248
read_cached_record(join_tab);
11249
if (!select || !select->skip_record())
11252
if (!join_tab->check_weed_out_table ||
11253
!(res= do_sj_dups_weedout(join->session, join_tab->check_weed_out_table)))
11255
rc= (join_tab->next_select)(join,join_tab+1,0);
11256
if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
11258
reset_cache_write(&join_tab->cache);
11263
return NESTED_LOOP_ERROR;
11267
} while (!(error=info->read_record(info)));
11270
read_cached_record(join_tab); // Restore current record
11271
reset_cache_write(&join_tab->cache);
11272
if (error > 0) // Fatal error
11273
return NESTED_LOOP_ERROR; /* purecov: inspected */
11274
for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
11275
tmp2->table->status=tmp2->status;
11276
return NESTED_LOOP_OK;
11279
int safe_index_read(JOIN_TAB *tab)
3588
11282
Table *table= tab->table;
3589
if ((error=table->cursor->index_read_map(table->record[0],
11283
if ((error=table->file->index_read_map(table->record[0],
3590
11284
tab->ref.key_buff,
3591
11285
make_prev_keypart_map(tab->ref.key_parts),
3592
11286
HA_READ_KEY_EXACT)))
15337
/** Allocate memory needed for other rollup functions. */
15339
bool JOIN::rollup_init()
15344
tmp_table_param.quick_group= 0; // Can't create groups in tmp table
15345
rollup.state= ROLLUP::STATE_INITED;
15348
Create pointers to the different sum function groups
15349
These are updated by rollup_make_fields()
15351
tmp_table_param.group_parts= send_group_parts;
15353
if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
15355
sizeof(List<Item>) +
15356
ref_pointer_array_size)
15357
* send_group_parts )))
15360
rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
15361
rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
15362
ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
15365
Prepare space for field list for the different levels
15366
These will be filled up in rollup_make_fields()
15368
for (i= 0 ; i < send_group_parts ; i++)
15370
rollup.null_items[i]= new (session->mem_root) Item_null_result();
15371
List<Item> *rollup_fields= &rollup.fields[i];
15372
rollup_fields->empty();
15373
rollup.ref_pointer_arrays[i]= ref_array;
15374
ref_array+= all_fields.elements;
15376
for (i= 0 ; i < send_group_parts; i++)
15378
for (j=0 ; j < fields_list.elements ; j++)
15379
rollup.fields[i].push_back(rollup.null_items[i]);
15381
List_iterator<Item> it(all_fields);
15383
while ((item= it++))
15385
order_st *group_tmp;
15386
bool found_in_group= 0;
15388
for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
15390
if (*group_tmp->item == item)
15392
item->maybe_null= 1;
15394
if (item->const_item())
15397
For ROLLUP queries each constant item referenced in GROUP BY list
15398
is wrapped up into an Item_func object yielding the same value
15399
as the constant item. The objects of the wrapper class are never
15400
considered as constant items and besides they inherit all
15401
properties of the Item_result_field class.
15402
This wrapping allows us to ensure writing constant items
15403
into temporary tables whenever the result of the ROLLUP
15404
operation has to be written into a temporary table, e.g. when
15405
ROLLUP is used together with DISTINCT in the SELECT list.
15406
Usually when creating temporary tables for a intermidiate
15407
result we do not include fields for constant expressions.
15409
Item* new_item= new Item_func_rollup_const(item);
15412
new_item->fix_fields(session, (Item **) 0);
15413
session->change_item_tree(it.ref(), new_item);
15414
for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
15416
if (*tmp->item == item)
15417
session->change_item_tree(tmp->item, new_item);
15422
if (item->type() == Item::FUNC_ITEM && !found_in_group)
15424
bool changed= false;
15425
if (change_group_ref(session, (Item_func *) item, group_list, &changed))
15428
We have to prevent creation of a field in a temporary table for
15429
an expression that contains GROUP BY attributes.
15430
Marking the expression item as 'with_sum_func' will ensure this.
15433
item->with_sum_func= 1;
15441
Fill up rollup structures with pointers to fields to use.
15443
Creates copies of item_sum items for each sum level.
15445
@param fields_arg List of all fields (hidden and real ones)
15446
@param sel_fields Pointer to selected fields
15447
@param func Store here a pointer to all fields
15451
In this case func is pointing to next not used element.
15456
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields,
15459
List_iterator_fast<Item> it(fields_arg);
15460
Item *first_field= sel_fields.head();
15464
Create field lists for the different levels
15466
The idea here is to have a separate field list for each rollup level to
15467
avoid all runtime checks of which columns should be NULL.
15469
The list is stored in reverse order to get sum function in such an order
15470
in func that it makes it easy to reset them with init_sum_functions()
15472
Assuming: SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15474
rollup.fields[0] will contain list where a,b,c is NULL
15475
rollup.fields[1] will contain list where b,c is NULL
15477
rollup.ref_pointer_array[#] points to fields for rollup.fields[#]
15479
sum_funcs_end[0] points to all sum functions
15480
sum_funcs_end[1] points to all sum functions, except grand totals
15484
for (level=0 ; level < send_group_parts ; level++)
15487
uint32_t pos= send_group_parts - level -1;
15488
bool real_fields= 0;
15490
List_iterator<Item> new_it(rollup.fields[pos]);
15491
Item **ref_array_start= rollup.ref_pointer_arrays[pos];
15492
order_st *start_group;
15494
/* Point to first hidden field */
15495
Item **ref_array= ref_array_start + fields_arg.elements-1;
15497
/* Remember where the sum functions ends for the previous level */
15498
sum_funcs_end[pos+1]= *func;
15500
/* Find the start of the group for this level */
15501
for (i= 0, start_group= group_list ;
15503
start_group= start_group->next)
15507
while ((item= it++))
15509
if (item == first_field)
15511
real_fields= 1; // End of hidden fields
15512
ref_array= ref_array_start;
15515
if (item->type() == Item::SUM_FUNC_ITEM && !item->const_item() &&
15516
(!((Item_sum*) item)->depended_from() ||
15517
((Item_sum *)item)->depended_from() == select_lex))
15521
This is a top level summary function that must be replaced with
15522
a sum function that is reset for this level.
15524
NOTE: This code creates an object which is not that nice in a
15525
sub select. Fortunately it's not common to have rollup in
15528
item= item->copy_or_same(session);
15529
((Item_sum*) item)->make_unique();
15530
*(*func)= (Item_sum*) item;
15535
/* Check if this is something that is part of this group by */
15536
order_st *group_tmp;
15537
for (group_tmp= start_group, i= pos ;
15538
group_tmp ; group_tmp= group_tmp->next, i++)
15540
if (*group_tmp->item == item)
15543
This is an element that is used by the GROUP BY and should be
15544
set to NULL in this level
15546
Item_null_result *null_item= new (session->mem_root) Item_null_result();
15549
item->maybe_null= 1; // Value will be null sometimes
15550
null_item->result_field= item->get_tmp_table_field();
15559
(void) new_it++; // Point to next item
15560
new_it.replace(item); // Replace previous
15567
sum_funcs_end[0]= *func; // Point to last function
15572
Send all rollup levels higher than the current one to the client.
15576
SELECT a, b, c SUM(b) FROM t1 GROUP BY a,b WITH ROLLUP
15579
@param idx Level we are on:
15580
- 0 = Total sum level
15581
- 1 = First group changed (a)
15582
- 2 = Second group changed (a,b)
15587
1 If send_data_failed()
15590
int JOIN::rollup_send_data(uint32_t idx)
15593
for (i= send_group_parts ; i-- > idx ; )
15595
/* Get reference pointers to sum functions in place */
15596
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15597
ref_pointer_array_size);
15598
if ((!having || having->val_int()))
15600
if (send_records < unit->select_limit_cnt && do_send_rows &&
15601
result->send_data(rollup.fields[i]))
15606
/* Restore ref_pointer_array */
15607
set_items_ref_array(current_ref_pointer_array);
15612
Write all rollup levels higher than the current one to a temp table.
15616
SELECT a, b, SUM(c) FROM t1 GROUP BY a,b WITH ROLLUP
15619
@param idx Level we are on:
15620
- 0 = Total sum level
15621
- 1 = First group changed (a)
15622
- 2 = Second group changed (a,b)
15623
@param table reference to temp table
15628
1 if write_data_failed()
15631
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
15634
for (i= send_group_parts ; i-- > idx ; )
15636
/* Get reference pointers to sum functions in place */
15637
memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
15638
ref_pointer_array_size);
15639
if ((!having || having->val_int()))
15643
List_iterator_fast<Item> it(rollup.fields[i]);
15644
while ((item= it++))
15646
if (item->type() == Item::NULL_ITEM && item->is_result_field())
15647
item->save_in_result_field(1);
15649
copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
15650
if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
15652
if (create_myisam_from_heap(session, table_arg,
15653
tmp_table_param.start_recinfo,
15654
&tmp_table_param.recinfo,
15660
/* Restore ref_pointer_array */
15661
set_items_ref_array(current_ref_pointer_array);
15666
clear results if there are not rows found for group
15667
(end_send_group/end_write_group)
15672
clear_tables(this);
15673
copy_fields(&tmp_table_param);
15677
Item_sum *func, **func_ptr= sum_funcs;
15678
while ((func= *(func_ptr++)))
15686
Send a description about what how the select will be done to stdout.
15689
void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
15690
bool distinct,const char *message)
15692
List<Item> field_list;
15693
List<Item> item_list;
15694
Session *session=join->session;
15695
select_result *result=join->result;
15696
Item *item_null= new Item_null();
15697
const CHARSET_INFO * const cs= system_charset_info;
15699
/* Don't log this into the slow query log */
15700
session->server_status&= ~(SERVER_QUERY_NO_INDEX_USED | SERVER_QUERY_NO_GOOD_INDEX_USED);
15701
join->unit->offset_limit_cnt= 0;
15704
NOTE: the number/types of items pushed into item_list must be in sync with
15705
EXPLAIN column types as they're "defined" in Session::send_explain_fields()
15709
item_list.push_back(new Item_int((int32_t)
15710
join->select_lex->select_number));
15711
item_list.push_back(new Item_string(join->select_lex->type,
15712
strlen(join->select_lex->type), cs));
15713
for (uint32_t i=0 ; i < 7; i++)
15714
item_list.push_back(item_null);
15715
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15716
item_list.push_back(item_null);
15718
item_list.push_back(new Item_string(message,strlen(message),cs));
15719
if (result->send_data(item_list))
15722
else if (join->select_lex == join->unit->fake_select_lex)
15725
here we assume that the query will return at least two rows, so we
15726
show "filesort" in EXPLAIN. Of course, sometimes we'll be wrong
15727
and no filesort will be actually done, but executing all selects in
15728
the UNION to provide precise EXPLAIN information will hardly be
15731
char table_name_buffer[NAME_LEN];
15734
item_list.push_back(new Item_null);
15736
item_list.push_back(new Item_string(join->select_lex->type,
15737
strlen(join->select_lex->type),
15741
Select_Lex *sl= join->unit->first_select();
15742
uint32_t len= 6, lastop= 0;
15743
memcpy(table_name_buffer, STRING_WITH_LEN("<union"));
15744
for (; sl && len + lastop + 5 < NAME_LEN; sl= sl->next_select())
15747
lastop= snprintf(table_name_buffer + len, NAME_LEN - len,
15748
"%u,", sl->select_number);
15750
if (sl || len + lastop >= NAME_LEN)
15752
memcpy(table_name_buffer + len, STRING_WITH_LEN("...>") + 1);
15758
table_name_buffer[len - 1]= '>'; // change ',' to '>'
15760
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15763
item_list.push_back(new Item_string(join_type_str[JT_ALL],
15764
strlen(join_type_str[JT_ALL]),
15766
/* possible_keys */
15767
item_list.push_back(item_null);
15769
item_list.push_back(item_null);
15771
item_list.push_back(item_null);
15773
item_list.push_back(item_null);
15775
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15776
item_list.push_back(item_null);
15778
item_list.push_back(item_null);
15780
if (join->unit->global_parameters->order_list.first)
15781
item_list.push_back(new Item_string("Using filesort",
15784
item_list.push_back(new Item_string("", 0, cs));
15786
if (result->send_data(item_list))
15791
table_map used_tables=0;
15792
for (uint32_t i=0 ; i < join->tables ; i++)
15794
JOIN_TAB *tab=join->join_tab+i;
15795
Table *table=tab->table;
15796
TableList *table_list= tab->table->pos_in_table_list;
15798
char buff1[512], buff2[512], buff3[512];
15799
char keylen_str_buf[64];
15800
String extra(buff, sizeof(buff),cs);
15801
char table_name_buffer[NAME_LEN];
15802
String tmp1(buff1,sizeof(buff1),cs);
15803
String tmp2(buff2,sizeof(buff2),cs);
15804
String tmp3(buff3,sizeof(buff3),cs);
15813
item_list.push_back(new Item_uint((uint32_t)
15814
join->select_lex->select_number));
15816
item_list.push_back(new Item_string(join->select_lex->type,
15817
strlen(join->select_lex->type),
15819
if (tab->type == JT_ALL && tab->select && tab->select->quick)
15821
quick_type= tab->select->quick->get_type();
15822
if ((quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE) ||
15823
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT) ||
15824
(quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION))
15825
tab->type = JT_INDEX_MERGE;
15827
tab->type = JT_RANGE;
15830
if (table->derived_select_number)
15832
/* Derived table name generation */
15833
int len= snprintf(table_name_buffer, sizeof(table_name_buffer)-1,
15835
table->derived_select_number);
15836
item_list.push_back(new Item_string(table_name_buffer, len, cs));
15840
TableList *real_table= table->pos_in_table_list;
15841
item_list.push_back(new Item_string(real_table->alias,
15842
strlen(real_table->alias),
15845
/* "type" column */
15846
item_list.push_back(new Item_string(join_type_str[tab->type],
15847
strlen(join_type_str[tab->type]),
15849
/* Build "possible_keys" value and add it to item_list */
15850
if (!tab->keys.is_clear_all())
15853
for (j=0 ; j < table->s->keys ; j++)
15855
if (tab->keys.is_set(j))
15859
tmp1.append(table->key_info[j].name,
15860
strlen(table->key_info[j].name),
15861
system_charset_info);
15866
item_list.push_back(new Item_string(tmp1.ptr(),tmp1.length(),cs));
15868
item_list.push_back(item_null);
15870
/* Build "key", "key_len", and "ref" values and add them to item_list */
15871
if (tab->ref.key_parts)
15873
KEY *key_info=table->key_info+ tab->ref.key;
15874
register uint32_t length;
15875
item_list.push_back(new Item_string(key_info->name,
15876
strlen(key_info->name),
15877
system_charset_info));
15878
length= int64_t2str(tab->ref.key_length, keylen_str_buf, 10) -
15880
item_list.push_back(new Item_string(keylen_str_buf, length,
15881
system_charset_info));
15882
for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
15886
tmp2.append((*ref)->name(), strlen((*ref)->name()),
15887
system_charset_info);
15889
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15891
else if (tab->type == JT_NEXT)
15893
KEY *key_info=table->key_info+ tab->index;
15894
register uint32_t length;
15895
item_list.push_back(new Item_string(key_info->name,
15896
strlen(key_info->name),cs));
15897
length= int64_t2str(key_info->key_length, keylen_str_buf, 10) -
15899
item_list.push_back(new Item_string(keylen_str_buf,
15901
system_charset_info));
15902
item_list.push_back(item_null);
15904
else if (tab->select && tab->select->quick)
15906
tab->select->quick->add_keys_and_lengths(&tmp2, &tmp3);
15907
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15908
item_list.push_back(new Item_string(tmp3.ptr(),tmp3.length(),cs));
15909
item_list.push_back(item_null);
15913
if (table_list->schema_table && table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
15915
const char *tmp_buff;
15917
if (table_list->has_db_lookup_value)
15919
f_idx= table_list->schema_table->idx_field1;
15920
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15921
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15923
if (table_list->has_table_lookup_value)
15925
if (table_list->has_db_lookup_value)
15927
f_idx= table_list->schema_table->idx_field2;
15928
tmp_buff= table_list->schema_table->fields_info[f_idx].field_name;
15929
tmp2.append(tmp_buff, strlen(tmp_buff), cs);
15932
item_list.push_back(new Item_string(tmp2.ptr(),tmp2.length(),cs));
15934
item_list.push_back(item_null);
15937
item_list.push_back(item_null);
15938
item_list.push_back(item_null);
15939
item_list.push_back(item_null);
15942
/* Add "rows" field to item_list. */
15943
if (table_list->schema_table)
15946
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15947
item_list.push_back(item_null);
15949
item_list.push_back(item_null);
15953
double examined_rows;
15954
if (tab->select && tab->select->quick)
15955
examined_rows= rows2double(tab->select->quick->records);
15956
else if (tab->type == JT_NEXT || tab->type == JT_ALL)
15957
examined_rows= rows2double(tab->limit ? tab->limit :
15958
tab->table->file->records());
15960
examined_rows= join->best_positions[i].records_read;
15962
item_list.push_back(new Item_int((int64_t) (uint64_t) examined_rows,
15963
MY_INT64_NUM_DECIMAL_DIGITS));
15965
/* Add "filtered" field to item_list. */
15966
if (join->session->lex->describe & DESCRIBE_EXTENDED)
15970
f= (float) (100.0 * join->best_positions[i].records_read /
15972
item_list.push_back(new Item_float(f, 2));
15976
/* Build "Extra" field and add it to item_list. */
15977
bool key_read=table->key_read;
15978
if ((tab->type == JT_NEXT || tab->type == JT_CONST) &&
15979
table->covering_keys.is_set(tab->index))
15981
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT &&
15982
!((QUICK_ROR_INTERSECT_SELECT*)tab->select->quick)->need_to_fetch_row)
15986
item_list.push_back(new Item_string(tab->info,strlen(tab->info),cs));
15987
else if (tab->packed_info & TAB_INFO_HAVE_VALUE)
15989
if (tab->packed_info & TAB_INFO_USING_INDEX)
15990
extra.append(STRING_WITH_LEN("; Using index"));
15991
if (tab->packed_info & TAB_INFO_USING_WHERE)
15992
extra.append(STRING_WITH_LEN("; Using where"));
15993
if (tab->packed_info & TAB_INFO_FULL_SCAN_ON_NULL)
15994
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
15995
/* Skip initial "; "*/
15996
const char *str= extra.ptr();
15997
uint32_t len= extra.length();
16003
item_list.push_back(new Item_string(str, len, cs));
16007
uint32_t keyno= MAX_KEY;
16008
if (tab->ref.key_parts)
16009
keyno= tab->ref.key;
16010
else if (tab->select && tab->select->quick)
16011
keyno = tab->select->quick->index;
16013
if (keyno != MAX_KEY && keyno == table->file->pushed_idx_cond_keyno &&
16014
table->file->pushed_idx_cond)
16015
extra.append(STRING_WITH_LEN("; Using index condition"));
16017
if (quick_type == QUICK_SELECT_I::QS_TYPE_ROR_UNION ||
16018
quick_type == QUICK_SELECT_I::QS_TYPE_ROR_INTERSECT ||
16019
quick_type == QUICK_SELECT_I::QS_TYPE_INDEX_MERGE)
16021
extra.append(STRING_WITH_LEN("; Using "));
16022
tab->select->quick->add_info_string(&extra);
16026
if (tab->use_quick == 2)
16028
/* 4 bits per 1 hex digit + terminating '\0' */
16029
char buf[MAX_KEY / 4 + 1];
16030
extra.append(STRING_WITH_LEN("; Range checked for each "
16031
"record (index map: 0x"));
16032
extra.append(tab->keys.print(buf));
16035
else if (tab->select->cond)
16037
const COND *pushed_cond= tab->table->file->pushed_cond;
16039
if (session->variables.engine_condition_pushdown && pushed_cond)
16041
extra.append(STRING_WITH_LEN("; Using where with pushed "
16043
if (session->lex->describe & DESCRIBE_EXTENDED)
16045
extra.append(STRING_WITH_LEN(": "));
16046
((COND *)pushed_cond)->print(&extra, QT_ORDINARY);
16050
extra.append(STRING_WITH_LEN("; Using where"));
16055
if (quick_type == QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX)
16056
extra.append(STRING_WITH_LEN("; Using index for group-by"));
16058
extra.append(STRING_WITH_LEN("; Using index"));
16060
if (table->reginfo.not_exists_optimize)
16061
extra.append(STRING_WITH_LEN("; Not exists"));
16063
if (quick_type == QUICK_SELECT_I::QS_TYPE_RANGE &&
16064
!(((QUICK_RANGE_SELECT*)(tab->select->quick))->mrr_flags &
16065
HA_MRR_USE_DEFAULT_IMPL))
16067
extra.append(STRING_WITH_LEN("; Using MRR"));
16070
if (table_list->schema_table &&
16071
table_list->schema_table->i_s_requested_object & OPTIMIZE_I_S_TABLE)
16073
if (!table_list->table_open_method)
16074
extra.append(STRING_WITH_LEN("; Skip_open_table"));
16075
else if (table_list->table_open_method == OPEN_FRM_ONLY)
16076
extra.append(STRING_WITH_LEN("; Open_frm_only"));
16078
extra.append(STRING_WITH_LEN("; Open_full_table"));
16079
if (table_list->has_db_lookup_value &&
16080
table_list->has_table_lookup_value)
16081
extra.append(STRING_WITH_LEN("; Scanned 0 databases"));
16082
else if (table_list->has_db_lookup_value ||
16083
table_list->has_table_lookup_value)
16084
extra.append(STRING_WITH_LEN("; Scanned 1 database"));
16086
extra.append(STRING_WITH_LEN("; Scanned all databases"));
16088
if (need_tmp_table)
16091
extra.append(STRING_WITH_LEN("; Using temporary"));
16096
extra.append(STRING_WITH_LEN("; Using filesort"));
16098
if (distinct & test_all_bits(used_tables,session->used_tables))
16099
extra.append(STRING_WITH_LEN("; Distinct"));
16101
if (tab->insideout_match_tab)
16103
extra.append(STRING_WITH_LEN("; LooseScan"));
16106
if (tab->flush_weedout_table)
16107
extra.append(STRING_WITH_LEN("; Start temporary"));
16108
else if (tab->check_weed_out_table)
16109
extra.append(STRING_WITH_LEN("; End temporary"));
16110
else if (tab->do_firstmatch)
16112
extra.append(STRING_WITH_LEN("; FirstMatch("));
16113
Table *prev_table=tab->do_firstmatch->table;
16114
if (prev_table->derived_select_number)
16116
char namebuf[NAME_LEN];
16117
/* Derived table name generation */
16118
int len= snprintf(namebuf, sizeof(namebuf)-1,
16120
prev_table->derived_select_number);
16121
extra.append(namebuf, len);
16124
extra.append(prev_table->pos_in_table_list->alias);
16125
extra.append(STRING_WITH_LEN(")"));
16128
for (uint32_t part= 0; part < tab->ref.key_parts; part++)
16130
if (tab->ref.cond_guards[part])
16132
extra.append(STRING_WITH_LEN("; Full scan on NULL key"));
16137
if (i > 0 && tab[-1].next_select == sub_select_cache)
16138
extra.append(STRING_WITH_LEN("; Using join buffer"));
16140
/* Skip initial "; "*/
16141
const char *str= extra.ptr();
16142
uint32_t len= extra.length();
16148
item_list.push_back(new Item_string(str, len, cs));
16150
// For next iteration
16151
used_tables|=table->map;
16152
if (result->send_data(item_list))
16156
for (Select_Lex_Unit *unit= join->select_lex->first_inner_unit();
16158
unit= unit->next_unit())
16160
if (mysql_explain_union(session, unit, result))
16167
bool mysql_explain_union(Session *session, Select_Lex_Unit *unit, select_result *result)
16170
Select_Lex *first= unit->first_select();
16172
for (Select_Lex *sl= first;
16174
sl= sl->next_select())
16176
// drop UNCACHEABLE_EXPLAIN, because it is for internal usage only
16177
uint8_t uncacheable= (sl->uncacheable & ~UNCACHEABLE_EXPLAIN);
16178
sl->type= (((&session->lex->select_lex)==sl)?
16179
(sl->first_inner_unit() || sl->next_select() ?
16180
"PRIMARY" : "SIMPLE"):
16182
((sl->linkage == DERIVED_TABLE_TYPE) ?
16184
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16185
"DEPENDENT SUBQUERY":
16186
(uncacheable?"UNCACHEABLE SUBQUERY":
16188
((uncacheable & UNCACHEABLE_DEPENDENT) ?
16190
uncacheable?"UNCACHEABLE UNION":
16192
sl->options|= SELECT_DESCRIBE;
16194
if (unit->is_union())
16196
unit->fake_select_lex->select_number= UINT_MAX; // jost for initialization
16197
unit->fake_select_lex->type= "UNION RESULT";
16198
unit->fake_select_lex->options|= SELECT_DESCRIBE;
16199
if (!(res= unit->prepare(session, result, SELECT_NO_UNLOCK | SELECT_DESCRIBE)))
16201
res|= unit->cleanup();
16205
session->lex->current_select= first;
16206
unit->set_limit(unit->global_parameters);
16207
res= mysql_select(session, &first->ref_pointer_array,
16208
(TableList*) first->table_list.first,
16209
first->with_wild, first->item_list,
16211
first->order_list.elements +
16212
first->group_list.elements,
16213
(order_st*) first->order_list.first,
16214
(order_st*) first->group_list.first,
16216
first->options | session->options | SELECT_DESCRIBE,
16217
result, unit, first);
16219
return(res || session->is_error());
6541
16223
static void print_table_array(Session *session, String *str, TableList **table,
6542
16224
TableList **end)
added
removed
drizzled/sql_select.cc
