1
/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
* vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
4
* Copyright (C) 2008 Sun Microsystems
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.
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.
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
20
#ifndef DRIZZLED_ITEM_SUBSELECT_H
21
#define DRIZZLED_ITEM_SUBSELECT_H
26
#include "drizzled/comp_creator.h"
27
#include "drizzled/item/ref.h"
28
#include "drizzled/item/field.h"
29
#include "drizzled/item/bin_string.h"
35
class Select_Lex_Unit;
37
class select_result_interceptor;
38
class subselect_engine;
39
class subselect_hash_sj_engine;
40
class Item_bool_func2;
42
class Item_in_optimizer;
43
class Item_func_not_all;
44
class Tmp_Table_Param;
47
/* base class for subselects */
49
class Item_subselect :public Item_result_field
51
bool value_assigned; /* value already assigned to subselect */
53
/* thread handler, will be assigned in fix_fields only */
55
/* substitution instead of subselect in case of optimization */
57
/* unit of subquery */
58
Select_Lex_Unit *unit;
60
/* engine that perform execution of subselect (single select or union) */
61
subselect_engine *engine;
62
/* old engine if engine was changed */
63
subselect_engine *old_engine;
64
/* cache of used external tables */
65
table_map used_tables_cache;
66
/* allowed number of columns (1 for single value subqueries) */
68
/* where subquery is placed */
69
enum_parsing_place parsing_place;
70
/* work with 'substitution' */
71
bool have_to_be_excluded;
72
/* cache of constant state */
73
bool const_item_cache;
76
/* changed engine indicator */
78
/* subquery is transformed */
81
/* TRUE <=> The underlying SELECT is correlated w.r.t some ancestor select */
84
enum trans_res {RES_OK, RES_REDUCE, RES_ERROR};
85
enum subs_type {UNKNOWN_SUBS, SINGLEROW_SUBS,
86
EXISTS_SUBS, IN_SUBS, ALL_SUBS, ANY_SUBS};
90
virtual subs_type substype() { return UNKNOWN_SUBS; }
93
We need this method, because some compilers do not allow 'this'
94
pointer in constructor initialization list, but we need to pass a pointer
95
to subselect Item class to select_result_interceptor's constructor.
97
virtual void init (Select_Lex *select_lex,
98
select_result_interceptor *result);
106
virtual trans_res select_transformer(JOIN *join);
107
bool assigned() { return value_assigned; }
108
void assigned(bool a) { value_assigned= a; }
109
enum Type type() const;
115
bool fix_fields(Session *session, Item **ref);
117
virtual void fix_length_and_dec();
118
table_map used_tables() const;
119
table_map not_null_tables() const { return 0; }
120
bool const_item() const;
121
inline table_map get_used_tables_cache() { return used_tables_cache; }
122
inline bool get_const_item_cache() { return const_item_cache; }
123
Item *get_tmp_table_item(Session *session);
124
void update_used_tables();
125
virtual void print(String *str, enum_query_type query_type);
126
virtual bool have_guarded_conds() { return false; }
127
bool change_engine(subselect_engine *eng)
135
True if this subquery has been already evaluated. Implemented only for
136
single select and union subqueries only.
138
bool is_evaluated() const;
139
bool is_uncacheable() const;
142
Used by max/min subquery to initialize value presence registration
143
mechanism. Engine call this method before rexecution query.
145
virtual void reset_value_registration() {}
146
enum_parsing_place place() { return parsing_place; }
147
bool walk(Item_processor processor, bool walk_subquery, unsigned char *arg);
150
Get the Select_Lex structure associated with this Item.
151
@return the Select_Lex structure associated with this Item
153
Select_Lex* get_select_lex();
155
friend class select_result_interceptor;
156
friend class Item_in_optimizer;
157
friend bool Item_field::fix_fields(Session *, Item **);
158
friend int Item_field::fix_outer_field(Session *, Field **, Item **);
159
friend bool Item_ref::fix_fields(Session *, Item **);
160
friend void mark_select_range_as_dependent(Session*,
161
Select_Lex*, Select_Lex*,
162
Field*, Item*, Item_ident*);
165
/* single value subselect */
168
class Item_singlerow_subselect :public Item_subselect
171
Item_cache *value, **row;
173
Item_singlerow_subselect(Select_Lex *select_lex);
174
Item_singlerow_subselect() :Item_subselect(), value(0), row (0) {}
177
subs_type substype() { return SINGLEROW_SUBS; }
180
trans_res select_transformer(JOIN *join);
181
void store(uint32_t i, Item* item);
184
String *val_str (String *);
185
my_decimal *val_decimal(my_decimal *);
187
enum Item_result result_type() const;
188
enum_field_types field_type() const;
189
void fix_length_and_dec();
192
Item* element_index(uint32_t i) { return reinterpret_cast<Item*>(row[i]); }
193
Item** addr(uint32_t i) { return (Item**)row + i; }
194
bool check_cols(uint32_t c);
199
This method is used to implement a special case of semantic tree
200
rewriting, mandated by a SQL:2003 exception in the specification.
201
The only caller of this method is handle_sql2003_note184_exception(),
202
see the code there for more details.
203
Note that this method breaks the object internal integrity, by
204
removing it's association with the corresponding Select_Lex,
205
making this object orphan from the parse tree.
206
No other method, beside the destructor, should be called on this
207
object, as it is now invalid.
208
@return the Select_Lex structure that was given in the constructor.
210
Select_Lex* invalidate_and_restore_select_lex();
212
friend class select_singlerow_subselect;
215
/* used in static ALL/ANY optimization */
216
class select_max_min_finder_subselect;
217
class Item_maxmin_subselect :public Item_singlerow_subselect
221
bool was_values; // Set if we have found at least one row
223
Item_maxmin_subselect(Session *session, Item_subselect *parent,
224
Select_Lex *select_lex, bool max);
225
virtual void print(String *str, enum_query_type query_type);
227
bool any_value() { return was_values; }
228
void register_value() { was_values= true; }
229
void reset_value_registration() { was_values= false; }
232
/* exists subselect */
234
class Item_exists_subselect :public Item_subselect
237
bool value; /* value of this item (boolean: exists/not-exists) */
240
Item_exists_subselect(Select_Lex *select_lex);
241
Item_exists_subselect(): Item_subselect() {}
243
subs_type substype() { return EXISTS_SUBS; }
249
enum Item_result result_type() const { return INT_RESULT;}
252
String *val_str(String*);
253
my_decimal *val_decimal(my_decimal *);
255
void fix_length_and_dec();
256
virtual void print(String *str, enum_query_type query_type);
258
friend class select_exists_subselect;
259
friend class subselect_uniquesubquery_engine;
260
friend class subselect_indexsubquery_engine;
265
Representation of IN subquery predicates of the form
266
"left_expr IN (SELECT ...)".
270
- A "subquery execution engine" (as a subclass of Item_subselect) that allows
271
it to evaluate subqueries. (and this class participates in execution by
272
having was_null variable where part of execution result is stored.
273
- Transformation methods (todo: more on this).
275
This class is not used directly, it is "wrapped" into Item_in_optimizer
276
which provides some small bits of subquery evaluation.
279
class Item_in_subselect :public Item_exists_subselect
285
Cache of the left operand of the subquery predicate. Allocated in the
286
runtime memory root, for each execution, thus need not be freed.
288
List<Cached_item> *left_expr_cache;
289
bool first_execution;
292
expr & optimizer used in subselect rewriting to store Item for
296
Item_in_optimizer *optimizer;
301
/* Used to trigger on/off conditions that were pushed down to subselect */
302
bool *pushed_cond_guards;
304
/* Priority of this predicate in the convert-to-semi-join-nest process. */
305
int sj_convert_priority;
308
Location of the subquery predicate. It is either
309
- pointer to join nest if the subquery predicate is in the ON expression
310
- (TableList*)1 if the predicate is in the WHERE.
312
TableList *expr_join_nest;
314
/* The method chosen to execute the IN predicate. */
315
enum enum_exec_method {
316
NOT_TRANSFORMED, /* No execution method was chosen for this IN. */
317
SEMI_JOIN, /* IN was converted to semi-join nest and should be removed. */
318
IN_TO_EXISTS, /* IN was converted to correlated EXISTS. */
319
MATERIALIZATION /* IN will be executed via subquery materialization. */
321
enum_exec_method exec_method;
323
bool *get_cond_guard(int i)
325
return pushed_cond_guards ? pushed_cond_guards + i : NULL;
327
void set_cond_guard_var(int i, bool v)
329
if ( pushed_cond_guards)
330
pushed_cond_guards[i]= v;
332
bool have_guarded_conds() { return test(pushed_cond_guards); }
334
Item_func_not_all *upper_item; // point on NOT/NOP before ALL/SOME subquery
336
Item_in_subselect(Item * left_expr, Select_Lex *select_lex);
339
Item_exists_subselect(),
341
left_expr_cache(NULL),
342
first_execution(true),
344
abort_on_null(false),
345
pushed_cond_guards(NULL),
346
sj_convert_priority(0),
347
expr_join_nest(NULL),
348
exec_method(NOT_TRANSFORMED),
352
subs_type substype() { return IN_SUBS; }
359
trans_res select_transformer(JOIN *join);
360
trans_res select_in_like_transformer(JOIN *join, const Comp_creator *func);
361
trans_res single_value_transformer(JOIN *join, const Comp_creator *func);
362
trans_res row_value_transformer(JOIN * join);
363
trans_res single_value_in_to_exists_transformer(JOIN * join,
364
const Comp_creator *func);
365
trans_res row_value_in_to_exists_transformer(JOIN * join);
369
String *val_str(String*);
370
my_decimal *val_decimal(my_decimal *);
371
void update_null_value () { (void) val_bool(); }
373
void top_level_item() { abort_on_null=1; }
374
inline bool is_top_level_item() { return abort_on_null; }
375
bool test_limit(Select_Lex_Unit *unit);
376
virtual void print(String *str, enum_query_type query_type);
377
bool fix_fields(Session *session, Item **ref);
379
bool init_left_expr_cache();
380
bool is_expensive_processor(unsigned char *arg);
382
friend class Item_ref_null_helper;
383
friend class Item_is_not_null_test;
384
friend class Item_in_optimizer;
385
friend class subselect_indexsubquery_engine;
386
friend class subselect_hash_sj_engine;
390
/* ALL/ANY/SOME subselect */
391
class Item_allany_subselect :public Item_in_subselect
394
chooser_compare_func_creator func_creator;
398
Item_allany_subselect(Item * left_expr, chooser_compare_func_creator fc,
399
Select_Lex *select_lex, bool all);
401
// only ALL subquery has upper not
402
subs_type substype() { return all?ALL_SUBS:ANY_SUBS; }
403
trans_res select_transformer(JOIN *join);
404
virtual void print(String *str, enum_query_type query_type);
408
class subselect_engine: public memory::SqlAlloc
411
select_result_interceptor *result; /* results storage class */
412
Session *session; /* pointer to current Session */
413
Item_subselect *item; /* item, that use this engine */
414
enum Item_result res_type; /* type of results */
415
enum_field_types res_field_type; /* column type of the results */
416
bool maybe_null; /* may be null (first item in select) */
419
enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
420
UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
421
INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE};
423
subselect_engine(Item_subselect *si, select_result_interceptor *res)
428
res_type= STRING_RESULT;
429
res_field_type= DRIZZLE_TYPE_VARCHAR;
432
virtual ~subselect_engine() {}; // to satisfy compiler
433
virtual void cleanup()= 0;
436
Also sets "session" for subselect_engine::result.
437
Should be called before prepare().
439
void set_session(Session *session_arg);
440
Session * get_session() { return session; }
441
virtual int prepare()= 0;
442
virtual void fix_length_and_dec(Item_cache** row)= 0;
450
Execute the engine. The result of execution is subquery value that is
451
either captured by previously set up select_result-based 'sink' or
452
stored somewhere by the exec() method itself.
454
A required side effect: If at least one pushed-down predicate is
455
disabled, subselect_engine->no_rows() must return correct result after
460
1 - Either an execution error, or the engine was "changed", and the
461
caller should call exec() again for the new engine.
463
virtual int exec()= 0;
464
virtual uint32_t cols()= 0; /* return number of columns in select */
465
virtual uint8_t uncacheable()= 0; /* query is uncacheable */
466
enum Item_result type() { return res_type; }
467
enum_field_types field_type() { return res_field_type; }
468
virtual void exclude()= 0;
469
virtual bool may_be_null() { return maybe_null; };
470
virtual table_map upper_select_const_tables()= 0;
471
static table_map calc_const_tables(TableList *);
472
virtual void print(String *str, enum_query_type query_type)= 0;
473
virtual bool change_result(Item_subselect *si,
474
select_result_interceptor *result)= 0;
475
virtual bool no_tables()= 0;
476
virtual bool is_executed() const { return false; }
477
/* Check if subquery produced any rows during last query execution */
478
virtual bool no_rows() = 0;
479
virtual enum_engine_type engine_type() { return ABSTRACT_ENGINE; }
482
void set_row(List<Item> &item_list, Item_cache **row);
486
class subselect_single_select_engine: public subselect_engine
488
bool prepared; /* simple subselect is prepared */
489
bool optimized; /* simple subselect is optimized */
490
bool executed; /* simple subselect is executed */
491
Select_Lex *select_lex; /* corresponding select_lex */
492
JOIN * join; /* corresponding JOIN structure */
494
subselect_single_select_engine(Select_Lex *select,
495
select_result_interceptor *result,
496
Item_subselect *item);
499
void fix_length_and_dec(Item_cache** row);
502
uint8_t uncacheable();
504
table_map upper_select_const_tables();
505
virtual void print (String *str, enum_query_type query_type);
506
bool change_result(Item_subselect *si, select_result_interceptor *result);
509
bool is_executed() const { return executed; }
511
virtual enum_engine_type engine_type() { return SINGLE_SELECT_ENGINE; }
513
friend class subselect_hash_sj_engine;
514
friend class Item_in_subselect;
518
class subselect_union_engine: public subselect_engine
520
Select_Lex_Unit *unit; /* corresponding unit structure */
522
subselect_union_engine(Select_Lex_Unit *u,
523
select_result_interceptor *result,
524
Item_subselect *item);
527
void fix_length_and_dec(Item_cache** row);
530
uint8_t uncacheable();
532
table_map upper_select_const_tables();
533
virtual void print (String *str, enum_query_type query_type);
534
bool change_result(Item_subselect *si, select_result_interceptor *result);
536
bool is_executed() const;
538
virtual enum_engine_type engine_type() { return UNION_ENGINE; }
546
A subquery execution engine that evaluates the subquery by doing one index
547
lookup in a unique index.
549
This engine is used to resolve subqueries in forms
551
outer_expr IN (SELECT tbl.unique_key FROM tbl WHERE subq_where)
555
(oe1, .. oeN) IN (SELECT uniq_key_part1, ... uniq_key_partK
556
FROM tbl WHERE subqwhere)
558
i.e. the subquery is a single table SELECT without GROUP BY, aggregate
562
class subselect_uniquesubquery_engine: public subselect_engine
566
Item *cond; /* The WHERE condition of subselect */
568
TRUE<=> last execution produced empty set. Valid only when left
571
bool empty_result_set;
572
bool null_keypart; /* TRUE <=> constructed search tuple has a NULL */
575
// constructor can assign Session because it will be called after JOIN::prepare
576
subselect_uniquesubquery_engine(Session *session_arg, JoinTable *tab_arg,
577
Item_subselect *subs, Item *where)
578
:subselect_engine(subs, 0), tab(tab_arg), cond(where)
580
set_session(session_arg);
584
void fix_length_and_dec(Item_cache** row);
586
uint32_t cols() { return 1; }
587
uint8_t uncacheable() { return UNCACHEABLE_DEPENDENT; }
589
table_map upper_select_const_tables() { return 0; }
590
virtual void print (String *str, enum_query_type query_type);
591
bool change_result(Item_subselect *si, select_result_interceptor *result);
595
bool no_rows() { return empty_result_set; }
596
virtual enum_engine_type engine_type() { return UNIQUESUBQUERY_ENGINE; }
600
class subselect_indexsubquery_engine: public subselect_uniquesubquery_engine
602
/* FALSE for 'ref', TRUE for 'ref-or-null'. */
605
The "having" clause. This clause (further reffered to as "artificial
606
having") was inserted by subquery transformation code. It contains
607
Item(s) that have a side-effect: they record whether the subquery has
608
produced a row with NULL certain components. We need to use it for cases
610
(oe1, oe2) IN (SELECT t.key, t.no_key FROM t1)
611
where we do index lookup on t.key=oe1 but need also to check if there
612
was a row such that t.no_key IS NULL.
614
NOTE: This is currently here and not in the uniquesubquery_engine. Ideally
615
it should have been in uniquesubquery_engine in order to allow execution of
618
(oe1, oe2) IN (SELECT primary_key, non_key_maybe_null_field FROM tbl)
620
We could use uniquesubquery_engine for the first component and let
621
Item_is_not_null_test( non_key_maybe_null_field) to handle the second.
623
However, subqueries like the above are currently not handled by index
624
lookup-based subquery engines, the engine applicability check misses
625
them: it doesn't switch the engine for case of artificial having and
626
[eq_]ref access (only for artifical having + ref_or_null or no having).
627
The above example subquery is handled as a full-blown SELECT with eq_ref
630
Due to this limitation, the "artificial having" currently needs to be
631
checked by only in indexsubquery_engine.
636
// constructor can assign Session because it will be called after JOIN::prepare
637
subselect_indexsubquery_engine(Session *session_arg, JoinTable *tab_arg,
638
Item_subselect *subs, Item *where,
639
Item *having_arg, bool chk_null)
640
:subselect_uniquesubquery_engine(session_arg, tab_arg, subs, where),
641
check_null(chk_null),
645
virtual void print (String *str, enum_query_type query_type);
646
virtual enum_engine_type engine_type() { return INDEXSUBQUERY_ENGINE; }
650
inline bool Item_subselect::is_evaluated() const
652
return engine->is_executed();
656
inline bool Item_subselect::is_uncacheable() const
658
return engine->uncacheable();
663
Compute an IN predicate via a hash semi-join. The subquery is materialized
664
during the first evaluation of the IN predicate. The IN predicate is executed
665
via the functionality inherited from subselect_uniquesubquery_engine.
668
class subselect_hash_sj_engine: public subselect_uniquesubquery_engine
671
/* TRUE if the subquery was materialized into a temp table. */
672
bool is_materialized;
674
The old engine already chosen at parse time and stored in permanent memory.
675
Through this member we can re-create and re-prepare materialize_join for
676
each execution of a prepared statement. We akso resuse the functionality
677
of subselect_single_select_engine::[prepare | cols].
679
subselect_single_select_engine *materialize_engine;
681
QEP to execute the subquery and materialize its result into a
682
temporary table. Created during the first call to exec().
684
JOIN *materialize_join;
685
/* Temp table context of the outer select's JOIN. */
686
Tmp_Table_Param *tmp_param;
689
subselect_hash_sj_engine(Session *session_in, Item_subselect *in_predicate,
690
subselect_single_select_engine *old_engine)
691
:subselect_uniquesubquery_engine(session_in, NULL, in_predicate, NULL),
692
is_materialized(false), materialize_engine(old_engine),
693
materialize_join(NULL), tmp_param(NULL)
695
~subselect_hash_sj_engine();
697
bool init_permanent(List<Item> *tmp_columns);
700
int prepare() { return 0; }
702
virtual void print (String *str, enum_query_type query_type);
705
return materialize_engine->cols();
707
virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
710
} /* namespace drizzled */
712
#endif /* DRIZZLED_ITEM_SUBSELECT_H */