1 #ifndef ITEM_SUBSELECT_INCLUDED
2 #define ITEM_SUBSELECT_INCLUDED
3
4 /* Copyright (c) 2002, 2011, Oracle and/or its affiliates.
5
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; version 2 of the License.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
18
19 /* subselect Item */
20
21 #ifdef USE_PRAGMA_INTERFACE
22 #pragma interface /* gcc class implementation */
23 #endif
24
25 #include <queues.h>
26
27 class st_select_lex;
28 class st_select_lex_unit;
29 class JOIN;
30 class select_result_interceptor;
31 class subselect_engine;
32 class subselect_hash_sj_engine;
33 class Item_bool_func2;
34 class Comp_creator;
35 class With_element;
36
37 typedef class st_select_lex SELECT_LEX;
38
39 /**
40 Convenience typedef used in this file, and further used by any files
41 including this file.
42 */
43 typedef Comp_creator* (*chooser_compare_func_creator)(bool invert);
44 class Cached_item;
45
46 /* base class for subselects */
47
48 class Item_subselect :public Item_result_field,
49 protected Used_tables_and_const_cache
50 {
51 /*
52 Set to TRUE if the value is assigned for the subselect
53 FALSE: subquery not executed or the subquery returns an empty result
54 */
55 bool value_assigned;
56 bool own_engine; /* the engine was not taken from other Item_subselect */
57 protected:
58 /* thread handler, will be assigned in fix_fields only */
59 THD *thd;
60 /* old engine if engine was changed */
61 subselect_engine *old_engine;
62 /* allowed number of columns (1 for single value subqueries) */
63 uint max_columns;
64 /* where subquery is placed */
65 enum_parsing_place parsing_place;
66 /* work with 'substitution' */
67 bool have_to_be_excluded;
68
69 bool inside_first_fix_fields;
70 bool done_first_fix_fields;
71 Item *expr_cache;
72 /*
73 Set to TRUE if at optimization or execution time we determine that this
74 item's value is a constant. We need this member because it is not possible
75 to substitute 'this' with a constant item.
76 */
77 bool forced_const;
78 #ifndef DBUG_OFF
79 /* Count the number of times this subquery predicate has been executed. */
80 uint exec_counter;
81 #endif
82 public:
83 /*
84 Used inside Item_subselect::fix_fields() according to this scenario:
85 > Item_subselect::fix_fields
86 > engine->prepare
87 > child_join->prepare
88 (Here we realize we need to do the rewrite and set
89 substitution= some new Item, eg. Item_in_optimizer )
90 < child_join->prepare
91 < engine->prepare
92 *ref= substitution;
93 substitution= NULL;
94 < Item_subselect::fix_fields
95 */
96 /* TODO make this protected member again. */
97 Item *substitution;
98 /* engine that perform execution of subselect (single select or union) */
99 /* TODO make this protected member again. */
100 subselect_engine *engine;
101 /* unit of subquery */
102 st_select_lex_unit *unit;
103 /* Cached buffers used when calling filesort in sub queries */
104 Filesort_buffer filesort_buffer;
105 LEX_STRING sortbuffer;
106 /* A reference from inside subquery predicate to somewhere outside of it */
107 class Ref_to_outside : public Sql_alloc
108 {
109 public:
110 st_select_lex *select; /* Select where the reference is pointing to */
111 /*
112 What is being referred. This may be NULL when we're referring to an
113 aggregate function.
114 */
115 Item *item;
116 };
117 /*
118 References from within this subquery to somewhere outside of it (i.e. to
119 parent select, grandparent select, etc)
120 */
121 List<Ref_to_outside> upper_refs;
122 st_select_lex *parent_select;
123
124 /*
125 TRUE<=>Table Elimination has made it redundant to evaluate this select
126 (and so it is not part of QEP, etc)
127 */
128 bool eliminated;
129
130 /* subquery is transformed */
131 bool changed;
132
133 /* TRUE <=> The underlying SELECT is correlated w.r.t some ancestor select */
134 bool is_correlated;
135
136 /*
137 TRUE <=> the subquery contains a recursive reference in the FROM list
138 of one of its selects. In this case some of subquery optimization
139 strategies cannot be applied for the subquery;
140 */
141 bool with_recursive_reference;
142
143 /* To link Item_subselects containing references to the same recursive CTE */
144 Item_subselect *next_with_rec_ref;
145
146 enum subs_type {UNKNOWN_SUBS, SINGLEROW_SUBS,
147 EXISTS_SUBS, IN_SUBS, ALL_SUBS, ANY_SUBS};
148
149 Item_subselect(THD *thd);
150
substype()151 virtual subs_type substype() { return UNKNOWN_SUBS; }
is_exists_predicate()152 bool is_exists_predicate()
153 {
154 return substype() == Item_subselect::EXISTS_SUBS;
155 }
is_in_predicate()156 bool is_in_predicate()
157 {
158 return (substype() == Item_subselect::IN_SUBS ||
159 substype() == Item_subselect::ALL_SUBS ||
160 substype() == Item_subselect::ANY_SUBS);
161 }
162
163 /*
164 We need this method, because some compilers do not allow 'this'
165 pointer in constructor initialization list, but we need to pass a pointer
166 to subselect Item class to select_result_interceptor's constructor.
167 */
168 virtual void init (st_select_lex *select_lex,
169 select_result_interceptor *result);
170
171 ~Item_subselect();
172 void cleanup();
reset()173 virtual void reset()
174 {
175 eliminated= FALSE;
176 null_value= 1;
177 }
178 /**
179 Set the subquery result to a default value consistent with the semantics of
180 the result row produced for queries with implicit grouping.
181 */
182 void no_rows_in_result()= 0;
183 virtual bool select_transformer(JOIN *join);
assigned()184 bool assigned() { return value_assigned; }
assigned(bool a)185 void assigned(bool a) { value_assigned= a; }
186 enum Type type() const;
is_null()187 bool is_null()
188 {
189 update_null_value();
190 return null_value;
191 }
192 bool fix_fields(THD *thd, Item **ref);
with_subquery()193 bool with_subquery() const { DBUG_ASSERT(fixed); return true; }
194 bool mark_as_dependent(THD *thd, st_select_lex *select, Item *item);
195 void fix_after_pullout(st_select_lex *new_parent, Item **ref, bool merge);
196 void recalc_used_tables(st_select_lex *new_parent, bool after_pullout);
197 virtual bool exec();
198 /*
199 If subquery optimization or execution determines that the subquery has
200 an empty result, mark the subquery predicate as a constant value.
201 */
make_const()202 void make_const()
203 {
204 used_tables_cache= 0;
205 const_item_cache= 0;
206 forced_const= TRUE;
207 }
208 virtual bool fix_length_and_dec();
209 table_map used_tables() const;
not_null_tables()210 table_map not_null_tables() const { return 0; }
211 bool const_item() const;
get_used_tables_cache()212 inline table_map get_used_tables_cache() { return used_tables_cache; }
213 Item *get_tmp_table_item(THD *thd);
214 void update_used_tables();
215 virtual void print(String *str, enum_query_type query_type);
have_guarded_conds()216 virtual bool have_guarded_conds() { return FALSE; }
change_engine(subselect_engine * eng)217 bool change_engine(subselect_engine *eng)
218 {
219 old_engine= engine;
220 engine= eng;
221 return eng == 0;
222 }
engine_changed(subselect_engine * eng)223 bool engine_changed(subselect_engine *eng) { return engine != eng; }
224 /*
225 True if this subquery has been already evaluated. Implemented only for
226 single select and union subqueries only.
227 */
228 bool is_evaluated() const;
229 bool is_uncacheable() const;
230 bool is_expensive();
231
232 /*
233 Used by max/min subquery to initialize value presence registration
234 mechanism. Engine call this method before rexecution query.
235 */
reset_value_registration()236 virtual void reset_value_registration() {}
place()237 enum_parsing_place place() { return parsing_place; }
238 bool walk(Item_processor processor, bool walk_subquery, void *arg);
239 bool mark_as_eliminated_processor(void *arg);
240 bool eliminate_subselect_processor(void *arg);
241 bool set_fake_select_as_master_processor(void *arg);
242 bool enumerate_field_refs_processor(void *arg);
check_vcol_func_processor(void * arg)243 bool check_vcol_func_processor(void *arg)
244 {
245 return mark_unsupported_function("select ...", arg, VCOL_IMPOSSIBLE);
246 }
247 /**
248 Callback to test if an IN predicate is expensive.
249
250 @notes
251 The return value affects the behavior of make_cond_for_table().
252
253 @retval TRUE if the predicate is expensive
254 @retval FALSE otherwise
255 */
is_expensive_processor(void * arg)256 bool is_expensive_processor(void *arg) { return is_expensive(); }
257 bool update_table_bitmaps_processor(void *arg);
258
259 /**
260 Get the SELECT_LEX structure associated with this Item.
261 @return the SELECT_LEX structure associated with this Item
262 */
263 st_select_lex* get_select_lex();
264 virtual bool expr_cache_is_needed(THD *);
265 virtual void get_cache_parameters(List<Item> ¶meters);
is_subquery_processor(void * opt_arg)266 virtual bool is_subquery_processor (void *opt_arg) { return 1; }
exists2in_processor(void * opt_arg)267 bool exists2in_processor(void *opt_arg) { return 0; }
limit_index_condition_pushdown_processor(void * opt_arg)268 bool limit_index_condition_pushdown_processor(void *opt_arg)
269 {
270 return TRUE;
271 }
272
273 void register_as_with_rec_ref(With_element *with_elem);
274 void init_expr_cache_tracker(THD *thd);
275
build_clone(THD * thd)276 Item* build_clone(THD *thd) { return 0; }
get_copy(THD * thd)277 Item* get_copy(THD *thd) { return 0; }
278
279 st_select_lex *wrap_tvc_into_select(THD *thd, st_select_lex *tvc_sl);
280
281 friend class select_result_interceptor;
282 friend class Item_in_optimizer;
283 friend bool Item_field::fix_fields(THD *, Item **);
284 friend int Item_field::fix_outer_field(THD *, Field **, Item **);
285 friend bool Item_ref::fix_fields(THD *, Item **);
286 friend void mark_select_range_as_dependent(THD*,
287 st_select_lex*, st_select_lex*,
288 Field*, Item*, Item_ident*,
289 bool);
290 friend bool convert_join_subqueries_to_semijoins(JOIN *join);
291 };
292
293 /* single value subselect */
294
295 class Item_cache;
296 class Item_singlerow_subselect :public Item_subselect
297 {
298 protected:
299 Item_cache *value, **row;
300 public:
301 Item_singlerow_subselect(THD *thd_arg, st_select_lex *select_lex);
Item_singlerow_subselect(THD * thd_arg)302 Item_singlerow_subselect(THD *thd_arg): Item_subselect(thd_arg), value(0), row (0)
303 {}
304
305 void cleanup();
substype()306 subs_type substype() { return SINGLEROW_SUBS; }
307
308 void reset();
309 void no_rows_in_result();
310 bool select_transformer(JOIN *join);
311 void store(uint i, Item* item);
312 double val_real();
313 longlong val_int ();
314 String *val_str (String *);
315 my_decimal *val_decimal(my_decimal *);
316 bool val_bool();
317 bool get_date(MYSQL_TIME *ltime, ulonglong fuzzydate);
318 const Type_handler *type_handler() const;
319 bool fix_length_and_dec();
320
321 uint cols() const;
element_index(uint i)322 Item* element_index(uint i) { return reinterpret_cast<Item*>(row[i]); }
addr(uint i)323 Item** addr(uint i) { return (Item**)row + i; }
324 bool check_cols(uint c);
325 bool null_inside();
326 void bring_value();
327
328 /**
329 This method is used to implement a special case of semantic tree
330 rewriting, mandated by a SQL:2003 exception in the specification.
331 The only caller of this method is handle_sql2003_note184_exception(),
332 see the code there for more details.
333 Note that this method breaks the object internal integrity, by
334 removing it's association with the corresponding SELECT_LEX,
335 making this object orphan from the parse tree.
336 No other method, beside the destructor, should be called on this
337 object, as it is now invalid.
338 @return the SELECT_LEX structure that was given in the constructor.
339 */
340 st_select_lex* invalidate_and_restore_select_lex();
341
342 Item* expr_cache_insert_transformer(THD *thd, uchar *unused);
343
344 friend class select_singlerow_subselect;
345 };
346
347 /* used in static ALL/ANY optimization */
348 class select_max_min_finder_subselect;
349 class Item_maxmin_subselect :public Item_singlerow_subselect
350 {
351 protected:
352 bool max;
353 bool was_values; // Set if we have found at least one row
354 public:
355 Item_maxmin_subselect(THD *thd, Item_subselect *parent,
356 st_select_lex *select_lex, bool max);
357 virtual void print(String *str, enum_query_type query_type);
358 void cleanup();
any_value()359 bool any_value() { return was_values; }
register_value()360 void register_value() { was_values= TRUE; }
reset_value_registration()361 void reset_value_registration() { was_values= FALSE; }
362 void no_rows_in_result();
363 };
364
365 /* exists subselect */
366
367 class Item_exists_subselect :public Item_subselect
368 {
369 protected:
370 Item_func_not *upper_not;
371 bool value; /* value of this item (boolean: exists/not-exists) */
372 bool abort_on_null;
373
374 void init_length_and_dec();
375 bool select_prepare_to_be_in();
376
377 public:
378 /*
379 Used by subquery optimizations to keep track about in which clause this
380 subquery predicate is located:
381 NO_JOIN_NEST - the predicate is an AND-part of the WHERE
382 join nest pointer - the predicate is an AND-part of ON expression
383 of a join nest
384 NULL - for all other locations
385 */
386 TABLE_LIST *emb_on_expr_nest;
387 /**
388 Reference on the Item_in_optimizer wrapper of this subquery
389 */
390 Item_in_optimizer *optimizer;
391 /* true if we got this from EXISTS or to IN */
392 bool exists_transformed;
393
394 Item_exists_subselect(THD *thd_arg, st_select_lex *select_lex);
Item_exists_subselect(THD * thd_arg)395 Item_exists_subselect(THD *thd_arg):
396 Item_subselect(thd_arg), upper_not(NULL), abort_on_null(0),
397 emb_on_expr_nest(NULL), optimizer(0), exists_transformed(0)
398 {}
399
substype()400 subs_type substype() { return EXISTS_SUBS; }
reset()401 void reset()
402 {
403 eliminated= FALSE;
404 value= 0;
405 }
406 void no_rows_in_result();
407
type_handler()408 const Type_handler *type_handler() const { return &type_handler_longlong; }
409 longlong val_int();
410 double val_real();
411 String *val_str(String*);
412 my_decimal *val_decimal(my_decimal *);
413 bool val_bool();
get_date(MYSQL_TIME * ltime,ulonglong fuzzydate)414 bool get_date(MYSQL_TIME *ltime, ulonglong fuzzydate)
415 { return get_date_from_int(ltime, fuzzydate); }
416 bool fix_fields(THD *thd, Item **ref);
417 bool fix_length_and_dec();
418 void print(String *str, enum_query_type query_type);
419 bool select_transformer(JOIN *join);
top_level_item()420 void top_level_item() { abort_on_null=1; }
is_top_level_item()421 inline bool is_top_level_item() { return abort_on_null; }
422 bool exists2in_processor(void *opt_arg);
423
424 Item* expr_cache_insert_transformer(THD *thd, uchar *unused);
425
mark_as_condition_AND_part(TABLE_LIST * embedding)426 void mark_as_condition_AND_part(TABLE_LIST *embedding)
427 {
428 emb_on_expr_nest= embedding;
429 }
under_not(Item_func_not * upper)430 virtual void under_not(Item_func_not *upper) { upper_not= upper; };
431
set_exists_transformed()432 void set_exists_transformed() { exists_transformed= TRUE; }
433
434 friend class select_exists_subselect;
435 friend class subselect_uniquesubquery_engine;
436 friend class subselect_indexsubquery_engine;
437 };
438
439
440 TABLE_LIST * const NO_JOIN_NEST=(TABLE_LIST*)0x1;
441
442 /*
443 Possible methods to execute an IN predicate. These are set by the optimizer
444 based on user-set optimizer switches, semantic analysis and cost comparison.
445 */
446 #define SUBS_NOT_TRANSFORMED 0 /* No execution method was chosen for this IN. */
447 /* The Final decision about the strategy is made. */
448 #define SUBS_STRATEGY_CHOSEN 1
449 #define SUBS_SEMI_JOIN 2 /* IN was converted to semi-join. */
450 #define SUBS_IN_TO_EXISTS 4 /* IN was converted to correlated EXISTS. */
451 #define SUBS_MATERIALIZATION 8 /* Execute IN via subquery materialization. */
452 /* Partial matching substrategies of MATERIALIZATION. */
453 #define SUBS_PARTIAL_MATCH_ROWID_MERGE 16
454 #define SUBS_PARTIAL_MATCH_TABLE_SCAN 32
455 /* ALL/ANY will be transformed with max/min optimization */
456 /* The subquery has not aggregates, transform it into a MAX/MIN query. */
457 #define SUBS_MAXMIN_INJECTED 64
458 /* The subquery has aggregates, use a special max/min subselect engine. */
459 #define SUBS_MAXMIN_ENGINE 128
460
461
462 /**
463 Representation of IN subquery predicates of the form
464 "left_expr IN (SELECT ...)".
465
466 @details
467 This class has:
468 - A "subquery execution engine" (as a subclass of Item_subselect) that allows
469 it to evaluate subqueries. (and this class participates in execution by
470 having was_null variable where part of execution result is stored.
471 - Transformation methods (todo: more on this).
472
473 This class is not used directly, it is "wrapped" into Item_in_optimizer
474 which provides some small bits of subquery evaluation.
475 */
476
477 class Item_in_subselect :public Item_exists_subselect
478 {
479 protected:
480 /*
481 Cache of the left operand of the subquery predicate. Allocated in the
482 runtime memory root, for each execution, thus need not be freed.
483 */
484 List<Cached_item> *left_expr_cache;
485 bool first_execution;
486
487 /*
488 expr & optimizer used in subselect rewriting to store Item for
489 all JOIN in UNION
490 */
491 Item *expr;
492 bool was_null;
493 /* A bitmap of possible execution strategies for an IN predicate. */
494 uchar in_strategy;
495 protected:
496 /* Used to trigger on/off conditions that were pushed down to subselect */
497 bool *pushed_cond_guards;
498 Comp_creator *func;
499
500 protected:
501 bool init_cond_guards();
502 bool select_in_like_transformer(JOIN *join);
503 bool single_value_transformer(JOIN *join);
504 bool row_value_transformer(JOIN * join);
505 bool fix_having(Item *having, st_select_lex *select_lex);
506 bool create_single_in_to_exists_cond(JOIN * join,
507 Item **where_item,
508 Item **having_item);
509 bool create_row_in_to_exists_cond(JOIN * join,
510 Item **where_item,
511 Item **having_item);
512 public:
513 Item *left_expr;
514 /*
515 Important for PS/SP: left_expr_orig is the item that left_expr originally
516 pointed at. That item is allocated on the statement arena, while
517 left_expr could later be changed to something on the execution arena.
518 */
519 Item *left_expr_orig;
520 /* Priority of this predicate in the convert-to-semi-join-nest process. */
521 int sj_convert_priority;
522 /* May be TRUE only for the candidates to semi-join conversion */
523 bool do_not_convert_to_sj;
524 /*
525 Types of left_expr and subquery's select list allow to perform subquery
526 materialization. Currently, we set this to FALSE when it as well could
527 be TRUE. This is to be properly addressed with fix for BUG#36752.
528 */
529 bool types_allow_materialization;
530
531 /*
532 Same as above, but they also allow to scan the materialized table.
533 */
534 bool sjm_scan_allowed;
535
536 /*
537 JoinTaB Materialization (JTBM) members
538 */
539
540 /*
541 TRUE <=> This subselect has been converted into non-mergeable semi-join
542 table.
543 */
544 bool is_jtbm_merged;
545
546 /* (Applicable if is_jtbm_merged==TRUE) Time required to run the materialized join */
547 double jtbm_read_time;
548
549 /* (Applicable if is_jtbm_merged==TRUE) Number of output rows in materialized join */
550 double jtbm_record_count;
551
552 /*
553 (Applicable if is_jtbm_merged==TRUE) TRUE <=> The materialized subselect is
554 a degenerate subselect which produces 0 or 1 rows, which we know at
555 optimization phase.
556 Examples:
557 1. subquery has "Impossible WHERE":
558
559 SELECT * FROM ot WHERE ot.column IN (SELECT it.col FROM it WHERE 2 > 3)
560
561 2. Subquery produces one row which opt_sum.cc is able to get with one lookup:
562
563 SELECT * FROM ot WHERE ot.column IN (SELECT MAX(it.key_col) FROM it)
564 */
565 bool is_jtbm_const_tab;
566
567 /*
568 (Applicable if is_jtbm_const_tab==TRUE) Whether the subquery has produced
569 the row (or not)
570 */
571 bool jtbm_const_row_found;
572
573 /*
574 TRUE<=>this is a flattenable semi-join, false otherwise.
575 */
576 bool is_flattenable_semijoin;
577
578 /*
579 TRUE<=>registered in the list of semijoins in outer select
580 */
581 bool is_registered_semijoin;
582
583 /*
584 Used to determine how this subselect item is represented in the item tree,
585 in case there is a need to locate it there and replace with something else.
586 Two options are possible:
587 1. This item is there 'as-is'.
588 1. This item is wrapped within Item_in_optimizer.
589 */
original_item()590 Item *original_item()
591 {
592 return (is_flattenable_semijoin && !exists_transformed ?
593 (Item*)this :
594 (Item*)optimizer);
595 }
596
get_cond_guard(int i)597 bool *get_cond_guard(int i)
598 {
599 return pushed_cond_guards ? pushed_cond_guards + i : NULL;
600 }
set_cond_guard_var(int i,bool v)601 void set_cond_guard_var(int i, bool v)
602 {
603 if ( pushed_cond_guards)
604 pushed_cond_guards[i]= v;
605 }
have_guarded_conds()606 bool have_guarded_conds() { return MY_TEST(pushed_cond_guards); }
607
608 Item_func_not_all *upper_item; // point on NOT/NOP before ALL/SOME subquery
609
610 /*
611 SET to TRUE if IN subquery is converted from an IN predicate
612 */
613 bool converted_from_in_predicate;
614
615 Item_in_subselect(THD *thd_arg, Item * left_expr, st_select_lex *select_lex);
Item_in_subselect(THD * thd_arg)616 Item_in_subselect(THD *thd_arg):
617 Item_exists_subselect(thd_arg), left_expr_cache(0), first_execution(TRUE),
618 in_strategy(SUBS_NOT_TRANSFORMED),
619 pushed_cond_guards(NULL), func(NULL), do_not_convert_to_sj(FALSE),
620 is_jtbm_merged(FALSE), is_jtbm_const_tab(FALSE), upper_item(0),
621 converted_from_in_predicate(FALSE) {}
622 void cleanup();
substype()623 subs_type substype() { return IN_SUBS; }
reset()624 void reset()
625 {
626 eliminated= FALSE;
627 value= 0;
628 null_value= 0;
629 was_null= 0;
630 }
631 bool select_transformer(JOIN *join);
632 bool create_in_to_exists_cond(JOIN *join_arg);
633 bool inject_in_to_exists_cond(JOIN *join_arg);
634
635 virtual bool exec();
636 longlong val_int();
637 double val_real();
638 String *val_str(String*);
639 my_decimal *val_decimal(my_decimal *);
update_null_value()640 void update_null_value () { (void) val_bool(); }
641 bool val_bool();
642 bool test_limit(st_select_lex_unit *unit);
643 void print(String *str, enum_query_type query_type);
precedence()644 enum precedence precedence() const { return IN_PRECEDENCE; }
645 bool fix_fields(THD *thd, Item **ref);
646 bool fix_length_and_dec();
647 void fix_after_pullout(st_select_lex *new_parent, Item **ref, bool merge);
const_item()648 bool const_item() const
649 {
650 return Item_subselect::const_item() && left_expr->const_item();
651 }
652 void update_used_tables();
653 bool setup_mat_engine();
654 bool init_left_expr_cache();
655 /* Inform 'this' that it was computed, and contains a valid result. */
set_first_execution()656 void set_first_execution() { if (first_execution) first_execution= FALSE; }
657 bool expr_cache_is_needed(THD *thd);
658 inline bool left_expr_has_null();
659
disable_cond_guard_for_const_null_left_expr(int i)660 void disable_cond_guard_for_const_null_left_expr(int i)
661 {
662 if (left_expr->const_item() && !left_expr->is_expensive())
663 {
664 if (left_expr->element_index(i)->is_null())
665 set_cond_guard_var(i,FALSE);
666 }
667 }
668
669 int optimize(double *out_rows, double *cost);
670 /*
671 Return the identifier that we could use to identify the subquery for the
672 user.
673 */
674 int get_identifier();
675
block_conversion_to_sj()676 void block_conversion_to_sj () { do_not_convert_to_sj= TRUE; }
677
test_strategy(uchar strategy)678 bool test_strategy(uchar strategy)
679 { return MY_TEST(in_strategy & strategy); }
680
681 /**
682 Test that the IN strategy was chosen for execution. This is so
683 when the CHOSEN flag is ON, and there is no other strategy.
684 */
test_set_strategy(uchar strategy)685 bool test_set_strategy(uchar strategy)
686 {
687 DBUG_ASSERT(strategy == SUBS_SEMI_JOIN ||
688 strategy == SUBS_IN_TO_EXISTS ||
689 strategy == SUBS_MATERIALIZATION ||
690 strategy == SUBS_PARTIAL_MATCH_ROWID_MERGE ||
691 strategy == SUBS_PARTIAL_MATCH_TABLE_SCAN ||
692 strategy == SUBS_MAXMIN_INJECTED ||
693 strategy == SUBS_MAXMIN_ENGINE);
694 return ((in_strategy & SUBS_STRATEGY_CHOSEN) &&
695 (in_strategy & ~SUBS_STRATEGY_CHOSEN) == strategy);
696 }
697
is_set_strategy()698 bool is_set_strategy()
699 { return MY_TEST(in_strategy & SUBS_STRATEGY_CHOSEN); }
700
has_strategy()701 bool has_strategy()
702 { return in_strategy != SUBS_NOT_TRANSFORMED; }
703
add_strategy(uchar strategy)704 void add_strategy (uchar strategy)
705 {
706 DBUG_ENTER("Item_in_subselect::add_strategy");
707 DBUG_PRINT("enter", ("current: %u add: %u",
708 (uint) in_strategy, (uint) strategy));
709 DBUG_ASSERT(strategy != SUBS_NOT_TRANSFORMED);
710 DBUG_ASSERT(!(strategy & SUBS_STRATEGY_CHOSEN));
711 /*
712 TODO: PS re-execution breaks this condition, because
713 check_and_do_in_subquery_rewrites() is called for each reexecution
714 and re-adds the same strategies.
715 DBUG_ASSERT(!(in_strategy & SUBS_STRATEGY_CHOSEN));
716 */
717 in_strategy|= strategy;
718 DBUG_VOID_RETURN;
719 }
720
reset_strategy(uchar strategy)721 void reset_strategy(uchar strategy)
722 {
723 DBUG_ENTER("Item_in_subselect::reset_strategy");
724 DBUG_PRINT("enter", ("current: %u new: %u",
725 (uint) in_strategy, (uint) strategy));
726 DBUG_ASSERT(strategy != SUBS_NOT_TRANSFORMED);
727 in_strategy= strategy;
728 DBUG_VOID_RETURN;
729 }
730
set_strategy(uchar strategy)731 void set_strategy(uchar strategy)
732 {
733 DBUG_ENTER("Item_in_subselect::set_strategy");
734 DBUG_PRINT("enter", ("current: %u set: %u",
735 (uint) in_strategy,
736 (uint) (SUBS_STRATEGY_CHOSEN | strategy)));
737 /* Check that only one strategy is set for execution. */
738 DBUG_ASSERT(strategy == SUBS_SEMI_JOIN ||
739 strategy == SUBS_IN_TO_EXISTS ||
740 strategy == SUBS_MATERIALIZATION ||
741 strategy == SUBS_PARTIAL_MATCH_ROWID_MERGE ||
742 strategy == SUBS_PARTIAL_MATCH_TABLE_SCAN ||
743 strategy == SUBS_MAXMIN_INJECTED ||
744 strategy == SUBS_MAXMIN_ENGINE);
745 in_strategy= (SUBS_STRATEGY_CHOSEN | strategy);
746 DBUG_VOID_RETURN;
747 }
748
walk(Item_processor processor,bool walk_subquery,void * arg)749 bool walk(Item_processor processor, bool walk_subquery, void *arg)
750 {
751 return left_expr->walk(processor, walk_subquery, arg) ||
752 Item_subselect::walk(processor, walk_subquery, arg);
753 }
754
exists2in_processor(void * opt_arg)755 bool exists2in_processor(void *opt_arg __attribute__((unused)))
756 {
757 return 0;
758 };
759
760 friend class Item_ref_null_helper;
761 friend class Item_is_not_null_test;
762 friend class Item_in_optimizer;
763 friend class subselect_indexsubquery_engine;
764 friend class subselect_hash_sj_engine;
765 friend class subselect_partial_match_engine;
766 friend class Item_exists_subselect;
767 };
768
769
770 /* ALL/ANY/SOME subselect */
771 class Item_allany_subselect :public Item_in_subselect
772 {
773 public:
774 chooser_compare_func_creator func_creator;
775 bool all;
776
777 Item_allany_subselect(THD *thd_arg, Item * left_expr,
778 chooser_compare_func_creator fc,
779 st_select_lex *select_lex, bool all);
780
781 void cleanup();
782 // only ALL subquery has upper not
substype()783 subs_type substype() { return all?ALL_SUBS:ANY_SUBS; }
784 bool select_transformer(JOIN *join);
create_comp_func(bool invert)785 void create_comp_func(bool invert) { func= func_creator(invert); }
786 void print(String *str, enum_query_type query_type);
787 bool is_maxmin_applicable(JOIN *join);
788 bool transform_into_max_min(JOIN *join);
789 void no_rows_in_result();
790 };
791
792
793 class subselect_engine: public Sql_alloc,
794 public Type_handler_hybrid_field_type
795 {
796 protected:
797 select_result_interceptor *result; /* results storage class */
798 THD *thd; /* pointer to current THD */
799 Item_subselect *item; /* item, that use this engine */
800 bool maybe_null; /* may be null (first item in select) */
801 public:
802
803 enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
804 UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
805 INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE,
806 ROWID_MERGE_ENGINE, TABLE_SCAN_ENGINE};
807
subselect_engine(Item_subselect * si,select_result_interceptor * res)808 subselect_engine(Item_subselect *si,
809 select_result_interceptor *res):
810 Type_handler_hybrid_field_type(&type_handler_varchar),
811 thd(NULL)
812 {
813 result= res;
814 item= si;
815 maybe_null= 0;
816 }
~subselect_engine()817 virtual ~subselect_engine() {}; // to satisfy compiler
818 virtual void cleanup()= 0;
819
820 /*
821 Also sets "thd" for subselect_engine::result.
822 Should be called before prepare().
823 */
824 void set_thd(THD *thd_arg);
get_thd()825 THD * get_thd() { return thd ? thd : current_thd; }
826 virtual int prepare(THD *)= 0;
827 virtual bool fix_length_and_dec(Item_cache** row)= 0;
828 /*
829 Execute the engine
830
831 SYNOPSIS
832 exec()
833
834 DESCRIPTION
835 Execute the engine. The result of execution is subquery value that is
836 either captured by previously set up select_result-based 'sink' or
837 stored somewhere by the exec() method itself.
838
839 A required side effect: If at least one pushed-down predicate is
840 disabled, subselect_engine->no_rows() must return correct result after
841 the exec() call.
842
843 RETURN
844 0 - OK
845 1 - Either an execution error, or the engine was "changed", and the
846 caller should call exec() again for the new engine.
847 */
848 virtual int exec()= 0;
849 virtual uint cols() const= 0; /* return number of columns in select */
850 virtual uint8 uncacheable()= 0; /* query is uncacheable */
851 virtual void exclude()= 0;
may_be_null()852 virtual bool may_be_null() { return maybe_null; };
853 virtual table_map upper_select_const_tables()= 0;
854 static table_map calc_const_tables(TABLE_LIST *);
855 static table_map calc_const_tables(List<TABLE_LIST> &list);
856 virtual void print(String *str, enum_query_type query_type)= 0;
857 virtual bool change_result(Item_subselect *si,
858 select_result_interceptor *result,
859 bool temp= FALSE)= 0;
860 virtual bool no_tables()= 0;
is_executed()861 virtual bool is_executed() const { return FALSE; }
862 /* Check if subquery produced any rows during last query execution */
863 virtual bool no_rows() = 0;
engine_type()864 virtual enum_engine_type engine_type() { return ABSTRACT_ENGINE; }
get_identifier()865 virtual int get_identifier() { DBUG_ASSERT(0); return 0; }
force_reexecution()866 virtual void force_reexecution() {}
867 protected:
868 bool set_row(List<Item> &item_list, Item_cache **row);
869 };
870
871
872 class subselect_single_select_engine: public subselect_engine
873 {
874 bool prepared; /* simple subselect is prepared */
875 bool executed; /* simple subselect is executed */
876 st_select_lex *select_lex; /* corresponding select_lex */
877 JOIN * join; /* corresponding JOIN structure */
878 public:
879 subselect_single_select_engine(st_select_lex *select,
880 select_result_interceptor *result,
881 Item_subselect *item);
882 void cleanup();
883 int prepare(THD *thd);
884 bool fix_length_and_dec(Item_cache** row);
885 int exec();
886 uint cols() const;
887 uint8 uncacheable();
888 void exclude();
889 table_map upper_select_const_tables();
890 void print (String *str, enum_query_type query_type);
891 bool change_result(Item_subselect *si,
892 select_result_interceptor *result,
893 bool temp);
894 bool no_tables();
895 bool may_be_null();
is_executed()896 bool is_executed() const { return executed; }
897 bool no_rows();
engine_type()898 virtual enum_engine_type engine_type() { return SINGLE_SELECT_ENGINE; }
899 int get_identifier();
900 void force_reexecution();
change_select(st_select_lex * new_select)901 void change_select(st_select_lex *new_select) { select_lex= new_select; }
902
903 friend class subselect_hash_sj_engine;
904 friend class Item_in_subselect;
905 friend bool setup_jtbm_semi_joins(JOIN *join, List<TABLE_LIST> *join_list,
906 Item **join_where);
907
908 };
909
910
911 class subselect_union_engine: public subselect_engine
912 {
913 st_select_lex_unit *unit; /* corresponding unit structure */
914 public:
915 subselect_union_engine(st_select_lex_unit *u,
916 select_result_interceptor *result,
917 Item_subselect *item);
918 void cleanup();
919 int prepare(THD *);
920 bool fix_length_and_dec(Item_cache** row);
921 int exec();
922 uint cols() const;
923 uint8 uncacheable();
924 void exclude();
925 table_map upper_select_const_tables();
926 void print (String *str, enum_query_type query_type);
927 bool change_result(Item_subselect *si,
928 select_result_interceptor *result,
929 bool temp= FALSE);
930 bool no_tables();
931 bool is_executed() const;
932 void force_reexecution();
933 bool no_rows();
engine_type()934 virtual enum_engine_type engine_type() { return UNION_ENGINE; }
935 };
936
937
938 struct st_join_table;
939
940
941 /*
942 A subquery execution engine that evaluates the subquery by doing one index
943 lookup in a unique index.
944
945 This engine is used to resolve subqueries in forms
946
947 outer_expr IN (SELECT tbl.unique_key FROM tbl WHERE subq_where)
948
949 or, tuple-based:
950
951 (oe1, .. oeN) IN (SELECT uniq_key_part1, ... uniq_key_partK
952 FROM tbl WHERE subqwhere)
953
954 i.e. the subquery is a single table SELECT without GROUP BY, aggregate
955 functions, etc.
956 */
957
958 class subselect_uniquesubquery_engine: public subselect_engine
959 {
960 protected:
961 st_join_table *tab;
962 Item *cond; /* The WHERE condition of subselect */
963 /*
964 TRUE<=> last execution produced empty set. Valid only when left
965 expression is NULL.
966 */
967 bool empty_result_set;
968 public:
969
970 // constructor can assign THD because it will be called after JOIN::prepare
subselect_uniquesubquery_engine(THD * thd_arg,st_join_table * tab_arg,Item_subselect * subs,Item * where)971 subselect_uniquesubquery_engine(THD *thd_arg, st_join_table *tab_arg,
972 Item_subselect *subs, Item *where)
973 :subselect_engine(subs, 0), tab(tab_arg), cond(where)
974 {}
975 ~subselect_uniquesubquery_engine();
976 void cleanup();
977 int prepare(THD *);
978 bool fix_length_and_dec(Item_cache** row);
979 int exec();
cols()980 uint cols() const { return 1; }
uncacheable()981 uint8 uncacheable() { return UNCACHEABLE_DEPENDENT_INJECTED; }
982 void exclude();
upper_select_const_tables()983 table_map upper_select_const_tables() { return 0; }
984 void print (String *str, enum_query_type query_type);
985 bool change_result(Item_subselect *si,
986 select_result_interceptor *result,
987 bool temp= FALSE);
988 bool no_tables();
989 int index_lookup(); /* TIMOUR: this method needs refactoring. */
990 int scan_table();
991 bool copy_ref_key(bool skip_constants);
no_rows()992 bool no_rows() { return empty_result_set; }
engine_type()993 virtual enum_engine_type engine_type() { return UNIQUESUBQUERY_ENGINE; }
994 };
995
996
997 class subselect_indexsubquery_engine: public subselect_uniquesubquery_engine
998 {
999 /* FALSE for 'ref', TRUE for 'ref-or-null'. */
1000 bool check_null;
1001 /*
1002 The "having" clause. This clause (further referred to as "artificial
1003 having") was inserted by subquery transformation code. It contains
1004 Item(s) that have a side-effect: they record whether the subquery has
1005 produced a row with NULL certain components. We need to use it for cases
1006 like
1007 (oe1, oe2) IN (SELECT t.key, t.no_key FROM t1)
1008 where we do index lookup on t.key=oe1 but need also to check if there
1009 was a row such that t.no_key IS NULL.
1010
1011 NOTE: This is currently here and not in the uniquesubquery_engine. Ideally
1012 it should have been in uniquesubquery_engine in order to allow execution of
1013 subqueries like
1014
1015 (oe1, oe2) IN (SELECT primary_key, non_key_maybe_null_field FROM tbl)
1016
1017 We could use uniquesubquery_engine for the first component and let
1018 Item_is_not_null_test( non_key_maybe_null_field) to handle the second.
1019
1020 However, subqueries like the above are currently not handled by index
1021 lookup-based subquery engines, the engine applicability check misses
1022 them: it doesn't switch the engine for case of artificial having and
1023 [eq_]ref access (only for artificial having + ref_or_null or no having).
1024 The above example subquery is handled as a full-blown SELECT with eq_ref
1025 access to one table.
1026
1027 Due to this limitation, the "artificial having" currently needs to be
1028 checked by only in indexsubquery_engine.
1029 */
1030 Item *having;
1031 public:
1032
1033 // constructor can assign THD because it will be called after JOIN::prepare
subselect_indexsubquery_engine(THD * thd_arg,st_join_table * tab_arg,Item_subselect * subs,Item * where,Item * having_arg,bool chk_null)1034 subselect_indexsubquery_engine(THD *thd_arg, st_join_table *tab_arg,
1035 Item_subselect *subs, Item *where,
1036 Item *having_arg, bool chk_null)
1037 :subselect_uniquesubquery_engine(thd_arg, tab_arg, subs, where),
1038 check_null(chk_null),
1039 having(having_arg)
1040 {}
1041 int exec();
1042 void print (String *str, enum_query_type query_type);
engine_type()1043 virtual enum_engine_type engine_type() { return INDEXSUBQUERY_ENGINE; }
1044 };
1045
1046 /*
1047 This function is actually defined in sql_parse.cc, but it depends on
1048 chooser_compare_func_creator defined in this file.
1049 */
1050 Item * all_any_subquery_creator(THD *thd, Item *left_expr,
1051 chooser_compare_func_creator cmp,
1052 bool all,
1053 SELECT_LEX *select_lex);
1054
1055
is_evaluated()1056 inline bool Item_subselect::is_evaluated() const
1057 {
1058 return engine->is_executed();
1059 }
1060
1061
is_uncacheable()1062 inline bool Item_subselect::is_uncacheable() const
1063 {
1064 return engine->uncacheable();
1065 }
1066
1067 /**
1068 Compute an IN predicate via a hash semi-join. This class is responsible for
1069 the materialization of the subquery, and the selection of the correct and
1070 optimal execution method (e.g. direct index lookup, or partial matching) for
1071 the IN predicate.
1072 */
1073
1074 class subselect_hash_sj_engine : public subselect_engine
1075 {
1076 public:
1077 /* The table into which the subquery is materialized. */
1078 TABLE *tmp_table;
1079 /* TRUE if the subquery was materialized into a temp table. */
1080 bool is_materialized;
1081 /*
1082 The old engine already chosen at parse time and stored in permanent memory.
1083 Through this member we can re-create and re-prepare materialize_join for
1084 each execution of a prepared statement. We also reuse the functionality
1085 of subselect_single_select_engine::[prepare | cols].
1086 */
1087 subselect_single_select_engine *materialize_engine;
1088 /*
1089 QEP to execute the subquery and materialize its result into a
1090 temporary table. Created during the first call to exec().
1091 */
1092 JOIN *materialize_join;
1093 /*
1094 A conjunction of all the equality conditions between all pairs of expressions
1095 that are arguments of an IN predicate. We need these to post-filter some
1096 IN results because index lookups sometimes match values that are actually
1097 not equal to the search key in SQL terms.
1098 */
1099 Item_cond_and *semi_join_conds;
1100 Name_resolution_context *semi_join_conds_context;
1101
1102
subselect_hash_sj_engine(THD * thd_arg,Item_subselect * in_predicate,subselect_single_select_engine * old_engine)1103 subselect_hash_sj_engine(THD *thd_arg, Item_subselect *in_predicate,
1104 subselect_single_select_engine *old_engine)
1105 : subselect_engine(in_predicate, NULL),
1106 tmp_table(NULL), is_materialized(FALSE), materialize_engine(old_engine),
1107 materialize_join(NULL), semi_join_conds(NULL), lookup_engine(NULL),
1108 count_partial_match_columns(0), count_null_only_columns(0),
1109 count_columns_with_nulls(0), strategy(UNDEFINED)
1110 {}
1111 ~subselect_hash_sj_engine();
1112
1113 bool init(List<Item> *tmp_columns, uint subquery_id);
1114 void cleanup();
1115 int prepare(THD *);
1116 int exec();
1117 void print(String *str, enum_query_type query_type);
cols()1118 uint cols() const { return materialize_engine->cols(); }
uncacheable()1119 uint8 uncacheable() { return materialize_engine->uncacheable(); }
upper_select_const_tables()1120 table_map upper_select_const_tables() { return 0; }
no_rows()1121 bool no_rows() { return !tmp_table->file->stats.records; }
engine_type()1122 virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
1123 /*
1124 TODO: factor out all these methods in a base subselect_index_engine class
1125 because all of them have dummy implementations and should never be called.
1126 */
1127 bool fix_length_and_dec(Item_cache** row);//=>base class
1128 void exclude(); //=>base class
1129 //=>base class
1130 bool change_result(Item_subselect *si,
1131 select_result_interceptor *result,
1132 bool temp= FALSE);
1133 bool no_tables();//=>base class
1134
1135 protected:
1136 /* The engine used to compute the IN predicate. */
1137 subselect_engine *lookup_engine;
1138 /* Keyparts of the only non-NULL composite index in a rowid merge. */
1139 MY_BITMAP non_null_key_parts;
1140 /* Keyparts of the single column indexes with NULL, one keypart per index. */
1141 MY_BITMAP partial_match_key_parts;
1142 uint count_partial_match_columns;
1143 uint count_null_only_columns;
1144 uint count_columns_with_nulls;
1145 /* Possible execution strategies that can be used to compute hash semi-join.*/
1146 enum exec_strategy {
1147 UNDEFINED,
1148 COMPLETE_MATCH, /* Use regular index lookups. */
1149 PARTIAL_MATCH, /* Use some partial matching strategy. */
1150 PARTIAL_MATCH_MERGE, /* Use partial matching through index merging. */
1151 PARTIAL_MATCH_SCAN, /* Use partial matching through table scan. */
1152 IMPOSSIBLE /* Subquery materialization is not applicable. */
1153 };
1154 /* The chosen execution strategy. Computed after materialization. */
1155 exec_strategy strategy;
1156 exec_strategy get_strategy_using_schema();
1157 exec_strategy get_strategy_using_data();
1158 ulonglong rowid_merge_buff_size(bool has_non_null_key,
1159 bool has_covering_null_row,
1160 MY_BITMAP *partial_match_key_parts);
1161 void choose_partial_match_strategy(bool has_non_null_key,
1162 bool has_covering_null_row,
1163 MY_BITMAP *partial_match_key_parts);
1164 bool make_semi_join_conds();
1165 subselect_uniquesubquery_engine* make_unique_engine();
1166
1167 };
1168
1169
1170 /*
1171 Distinguish the type of (0-based) row numbers from the type of the index into
1172 an array of row numbers.
1173 */
1174 typedef ha_rows rownum_t;
1175
1176
1177 /*
1178 An Ordered_key is an in-memory table index that allows O(log(N)) time
1179 lookups of a multi-part key.
1180
1181 If the index is over a single column, then this column may contain NULLs, and
1182 the NULLs are stored and tested separately for NULL in O(1) via is_null().
1183 Multi-part indexes assume that the indexed columns do not contain NULLs.
1184
1185 TODO:
1186 = Due to the unnatural assymetry between single and multi-part indexes, it
1187 makes sense to somehow refactor or extend the class.
1188
1189 = This class can be refactored into a base abstract interface, and two
1190 subclasses:
1191 - one to represent single-column indexes, and
1192 - another to represent multi-column indexes.
1193 Such separation would allow slightly more efficient implementation of
1194 the single-column indexes.
1195 = The current design requires such indexes to be fully recreated for each
1196 PS (re)execution, however most of the comprising objects can be reused.
1197 */
1198
1199 class Ordered_key : public Sql_alloc
1200 {
1201 protected:
1202 /*
1203 Index of the key in an array of keys. This index allows to
1204 construct (sub)sets of keys represented by bitmaps.
1205 */
1206 uint keyid;
1207 /* The table being indexed. */
1208 TABLE *tbl;
1209 /* The columns being indexed. */
1210 Item_field **key_columns;
1211 /* Number of elements in 'key_columns' (number of key parts). */
1212 uint key_column_count;
1213 /*
1214 An expression, or sequence of expressions that forms the search key.
1215 The search key is a sequence when it is Item_row. Each element of the
1216 sequence is accessible via Item::element_index(int i).
1217 */
1218 Item *search_key;
1219
1220 /* Value index related members. */
1221 /*
1222 The actual value index, consists of a sorted sequence of row numbers.
1223 */
1224 rownum_t *key_buff;
1225 /* Number of elements in key_buff. */
1226 ha_rows key_buff_elements;
1227 /* Current element in 'key_buff'. */
1228 ha_rows cur_key_idx;
1229 /*
1230 Mapping from row numbers to row ids. The element row_num_to_rowid[i]
1231 contains a buffer with the rowid for the row numbered 'i'.
1232 The memory for this member is not maintanined by this class because
1233 all Ordered_key indexes of the same table share the same mapping.
1234 */
1235 uchar *row_num_to_rowid;
1236 /*
1237 A sequence of predicates to compare the search key with the corresponding
1238 columns of a table row from the index.
1239 */
1240 Item_func_lt **compare_pred;
1241
1242 /* Null index related members. */
1243 MY_BITMAP null_key;
1244 /* Count of NULLs per column. */
1245 ha_rows null_count;
1246 /* The row number that contains the first NULL in a column. */
1247 rownum_t min_null_row;
1248 /* The row number that contains the last NULL in a column. */
1249 rownum_t max_null_row;
1250
1251 protected:
1252 bool alloc_keys_buffers();
1253 /*
1254 Quick sort comparison function that compares two rows of the same table
1255 indentfied with their row numbers.
1256 */
1257 int cmp_keys_by_row_data(rownum_t a, rownum_t b);
1258 static int cmp_keys_by_row_data_and_rownum(Ordered_key *key,
1259 rownum_t* a, rownum_t* b);
1260
1261 int cmp_key_with_search_key(rownum_t row_num);
1262
1263 public:
1264 Ordered_key(uint keyid_arg, TABLE *tbl_arg,
1265 Item *search_key_arg, ha_rows null_count_arg,
1266 ha_rows min_null_row_arg, ha_rows max_null_row_arg,
1267 uchar *row_num_to_rowid_arg);
1268 ~Ordered_key();
1269 void cleanup();
1270 /* Initialize a multi-column index. */
1271 bool init(MY_BITMAP *columns_to_index);
1272 /* Initialize a single-column index. */
1273 bool init(int col_idx);
1274
get_column_count()1275 uint get_column_count() { return key_column_count; }
get_keyid()1276 uint get_keyid() { return keyid; }
get_field(uint i)1277 Field *get_field(uint i)
1278 {
1279 DBUG_ASSERT(i < key_column_count);
1280 return key_columns[i]->field;
1281 }
get_min_null_row()1282 rownum_t get_min_null_row() { return min_null_row; }
get_max_null_row()1283 rownum_t get_max_null_row() { return max_null_row; }
get_null_key()1284 MY_BITMAP * get_null_key() { return &null_key; }
get_null_count()1285 ha_rows get_null_count() { return null_count; }
1286 /*
1287 Get the search key element that corresponds to the i-th key part of this
1288 index.
1289 */
get_search_key(uint i)1290 Item *get_search_key(uint i)
1291 {
1292 return search_key->element_index(key_columns[i]->field->field_index);
1293 }
add_key(rownum_t row_num)1294 void add_key(rownum_t row_num)
1295 {
1296 /* The caller must know how many elements to add. */
1297 DBUG_ASSERT(key_buff_elements && cur_key_idx < key_buff_elements);
1298 key_buff[cur_key_idx]= row_num;
1299 ++cur_key_idx;
1300 }
1301
1302 bool sort_keys();
1303 double null_selectivity();
1304
1305 /*
1306 Position the current element at the first row that matches the key.
1307 The key itself is propagated by evaluating the current value(s) of
1308 this->search_key.
1309 */
1310 bool lookup();
1311 /* Move the current index cursor to the first key. */
first()1312 void first()
1313 {
1314 DBUG_ASSERT(key_buff_elements);
1315 cur_key_idx= 0;
1316 }
1317 /* TODO */
1318 bool next_same();
1319 /* Move the current index cursor to the next key. */
next()1320 bool next()
1321 {
1322 DBUG_ASSERT(key_buff_elements);
1323 if (cur_key_idx < key_buff_elements - 1)
1324 {
1325 ++cur_key_idx;
1326 return TRUE;
1327 }
1328 return FALSE;
1329 };
1330 /* Return the current index element. */
current()1331 rownum_t current()
1332 {
1333 DBUG_ASSERT(key_buff_elements && cur_key_idx < key_buff_elements);
1334 return key_buff[cur_key_idx];
1335 }
1336
set_null(rownum_t row_num)1337 void set_null(rownum_t row_num)
1338 {
1339 bitmap_set_bit(&null_key, (uint)row_num);
1340 }
is_null(rownum_t row_num)1341 bool is_null(rownum_t row_num)
1342 {
1343 /*
1344 Indexes consisting of only NULLs do not have a bitmap buffer at all.
1345 Their only initialized member is 'n_bits', which is equal to the number
1346 of temp table rows.
1347 */
1348 if (null_count == tbl->file->stats.records)
1349 {
1350 DBUG_ASSERT(tbl->file->stats.records == null_key.n_bits);
1351 return TRUE;
1352 }
1353 if (row_num > max_null_row || row_num < min_null_row)
1354 return FALSE;
1355 return bitmap_is_set(&null_key, (uint)row_num);
1356 }
1357 void print(String *str);
1358 };
1359
1360
1361 class subselect_partial_match_engine : public subselect_engine
1362 {
1363 protected:
1364 /* The temporary table that contains a materialized subquery. */
1365 TABLE *tmp_table;
1366 /*
1367 The engine used to check whether an IN predicate is TRUE or not. If not
1368 TRUE, then subselect_rowid_merge_engine further distinguishes between
1369 FALSE and UNKNOWN.
1370 */
1371 subselect_uniquesubquery_engine *lookup_engine;
1372 /* A list of equalities between each pair of IN operands. */
1373 List<Item> *equi_join_conds;
1374 /*
1375 True if there is an all NULL row in tmp_table. If so, then if there is
1376 no complete match, there is a guaranteed partial match.
1377 */
1378 bool has_covering_null_row;
1379
1380 /*
1381 True if all nullable columns of tmp_table consist of only NULL values.
1382 If so, then if there is a match in the non-null columns, there is a
1383 guaranteed partial match.
1384 */
1385 bool has_covering_null_columns;
1386 uint count_columns_with_nulls;
1387
1388 protected:
1389 virtual bool partial_match()= 0;
1390 public:
1391 subselect_partial_match_engine(subselect_uniquesubquery_engine *engine_arg,
1392 TABLE *tmp_table_arg, Item_subselect *item_arg,
1393 select_result_interceptor *result_arg,
1394 List<Item> *equi_join_conds_arg,
1395 bool has_covering_null_row_arg,
1396 bool has_covering_null_columns_arg,
1397 uint count_columns_with_nulls_arg);
prepare(THD * thd_arg)1398 int prepare(THD *thd_arg) { set_thd(thd_arg); return 0; }
1399 int exec();
fix_length_and_dec(Item_cache **)1400 bool fix_length_and_dec(Item_cache**) { return FALSE; }
cols()1401 uint cols() const { /* TODO: what is the correct value? */ return 1; }
uncacheable()1402 uint8 uncacheable() { return UNCACHEABLE_DEPENDENT; }
exclude()1403 void exclude() {}
upper_select_const_tables()1404 table_map upper_select_const_tables() { return 0; }
1405 bool change_result(Item_subselect*,
1406 select_result_interceptor*,
1407 bool temp= FALSE)
1408 { DBUG_ASSERT(FALSE); return false; }
no_tables()1409 bool no_tables() { return false; }
no_rows()1410 bool no_rows()
1411 {
1412 /*
1413 TODO: It is completely unclear what is the semantics of this
1414 method. The current result is computed so that the call to no_rows()
1415 from Item_in_optimizer::val_int() sets Item_in_optimizer::null_value
1416 correctly.
1417 */
1418 return !(((Item_in_subselect *) item)->null_value);
1419 }
1420 void print(String*, enum_query_type);
1421
1422 friend void subselect_hash_sj_engine::cleanup();
1423 };
1424
1425
1426 class subselect_rowid_merge_engine: public subselect_partial_match_engine
1427 {
1428 protected:
1429 /*
1430 Mapping from row numbers to row ids. The rowids are stored sequentially
1431 in the array - rowid[i] is located in row_num_to_rowid + i * rowid_length.
1432 */
1433 uchar *row_num_to_rowid;
1434 /*
1435 A subset of all the keys for which there is a match for the same row.
1436 Used during execution. Computed for each outer reference
1437 */
1438 MY_BITMAP matching_keys;
1439 /*
1440 The columns of the outer reference that are NULL. Computed for each
1441 outer reference.
1442 */
1443 MY_BITMAP matching_outer_cols;
1444 /*
1445 Indexes of row numbers, sorted by <column_value, row_number>. If an
1446 index may contain NULLs, the NULLs are stored efficiently in a bitmap.
1447
1448 The indexes are sorted by the selectivity of their NULL sub-indexes, the
1449 one with the fewer NULLs is first. Thus, if there is any index on
1450 non-NULL columns, it is contained in keys[0].
1451 */
1452 Ordered_key **merge_keys;
1453 /* The number of elements in merge_keys. */
1454 uint merge_keys_count;
1455 /* The NULL bitmaps of merge keys.*/
1456 MY_BITMAP **null_bitmaps;
1457 /*
1458 An index on all non-NULL columns of 'tmp_table'. The index has the
1459 logical form: <[v_i1 | ... | v_ik], rownum>. It allows to find the row
1460 number where the columns c_i1,...,c1_k contain the values v_i1,...,v_ik.
1461 If such an index exists, it is always the first element of 'merge_keys'.
1462 */
1463 Ordered_key *non_null_key;
1464 /*
1465 Priority queue of Ordered_key indexes, one per NULLable column.
1466 This queue is used by the partial match algorithm in method exec().
1467 */
1468 QUEUE pq;
1469 protected:
1470 /*
1471 Comparison function to compare keys in order of decreasing bitmap
1472 selectivity.
1473 */
1474 static int cmp_keys_by_null_selectivity(Ordered_key **k1, Ordered_key **k2);
1475 /*
1476 Comparison function used by the priority queue pq, the 'smaller' key
1477 is the one with the smaller current row number.
1478 */
1479 static int cmp_keys_by_cur_rownum(void *arg, uchar *k1, uchar *k2);
1480
1481 bool test_null_row(rownum_t row_num);
1482 bool exists_complementing_null_row(MY_BITMAP *keys_to_complement);
1483 bool partial_match();
1484 public:
subselect_rowid_merge_engine(subselect_uniquesubquery_engine * engine_arg,TABLE * tmp_table_arg,uint merge_keys_count_arg,bool has_covering_null_row_arg,bool has_covering_null_columns_arg,uint count_columns_with_nulls_arg,Item_subselect * item_arg,select_result_interceptor * result_arg,List<Item> * equi_join_conds_arg)1485 subselect_rowid_merge_engine(subselect_uniquesubquery_engine *engine_arg,
1486 TABLE *tmp_table_arg, uint merge_keys_count_arg,
1487 bool has_covering_null_row_arg,
1488 bool has_covering_null_columns_arg,
1489 uint count_columns_with_nulls_arg,
1490 Item_subselect *item_arg,
1491 select_result_interceptor *result_arg,
1492 List<Item> *equi_join_conds_arg)
1493 :subselect_partial_match_engine(engine_arg, tmp_table_arg,
1494 item_arg, result_arg, equi_join_conds_arg,
1495 has_covering_null_row_arg,
1496 has_covering_null_columns_arg,
1497 count_columns_with_nulls_arg),
1498 merge_keys_count(merge_keys_count_arg), non_null_key(NULL)
1499 {}
1500 ~subselect_rowid_merge_engine();
1501 bool init(MY_BITMAP *non_null_key_parts, MY_BITMAP *partial_match_key_parts);
1502 void cleanup();
engine_type()1503 virtual enum_engine_type engine_type() { return ROWID_MERGE_ENGINE; }
1504 };
1505
1506
1507 class subselect_table_scan_engine: public subselect_partial_match_engine
1508 {
1509 protected:
1510 bool partial_match();
1511 public:
1512 subselect_table_scan_engine(subselect_uniquesubquery_engine *engine_arg,
1513 TABLE *tmp_table_arg, Item_subselect *item_arg,
1514 select_result_interceptor *result_arg,
1515 List<Item> *equi_join_conds_arg,
1516 bool has_covering_null_row_arg,
1517 bool has_covering_null_columns_arg,
1518 uint count_columns_with_nulls_arg);
1519 void cleanup();
engine_type()1520 virtual enum_engine_type engine_type() { return TABLE_SCAN_ENGINE; }
1521 };
1522 #endif /* ITEM_SUBSELECT_INCLUDED */
1523