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