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