drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
subselect.h
1/* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2 * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3 *
4 * Copyright (C) 2008 Sun Microsystems, Inc.
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
20#pragma once
21
22#include <drizzled/comp_creator.h>
23#include <drizzled/item/ref.h>
24#include <drizzled/item/field.h>
25#include <drizzled/item/bin_string.h>
26#include <drizzled/util/test.h>
27
28namespace drizzled {
29
30class Item_subselect : public Item_result_field
31{
32 bool value_assigned; /* value already assigned to subselect */
33public:
34 /* thread handler, will be assigned in fix_fields only */
35 Session *session;
36 /* substitution instead of subselect in case of optimization */
37 Item *substitution;
38 /* unit of subquery */
39 Select_Lex_Unit *unit;
40protected:
41 /* engine that perform execution of subselect (single select or union) */
42 subselect_engine *engine;
43 /* old engine if engine was changed */
44 subselect_engine *old_engine;
45 /* cache of used external tables */
46 table_map used_tables_cache;
47 /* allowed number of columns (1 for single value subqueries) */
48 uint32_t max_columns;
49 /* where subquery is placed */
50 enum_parsing_place parsing_place;
51 /* work with 'substitution' */
52 bool have_to_be_excluded;
53 /* cache of constant state */
54 bool const_item_cache;
55
56public:
57 /* changed engine indicator */
58 bool engine_changed;
59 /* subquery is transformed */
60 bool changed;
61
62 /* TRUE <=> The underlying SELECT is correlated w.r.t some ancestor select */
63 bool is_correlated;
64
65 enum trans_res {RES_OK, RES_REDUCE, RES_ERROR};
66 enum subs_type {UNKNOWN_SUBS, SINGLEROW_SUBS,
67 EXISTS_SUBS, IN_SUBS, ALL_SUBS, ANY_SUBS};
68
69 Item_subselect();
70
71 virtual subs_type substype() { return UNKNOWN_SUBS; }
72
73 /*
74 We need this method, because some compilers do not allow 'this'
75 pointer in constructor initialization list, but we need to pass a pointer
76 to subselect Item class to select_result_interceptor's constructor.
77 */
78 virtual void init (Select_Lex *select_lex,
79 select_result_interceptor *result);
80
81 ~Item_subselect();
82 void cleanup();
83 virtual void reset()
84 {
85 null_value= 1;
86 }
87 virtual trans_res select_transformer(Join *join);
88 bool assigned() { return value_assigned; }
89 void assigned(bool a) { value_assigned= a; }
90 enum Type type() const;
91 bool is_null()
92 {
94 return null_value;
95 }
96 bool fix_fields(Session *session, Item **ref);
97 virtual bool exec();
98 virtual void fix_length_and_dec();
99 table_map used_tables() const;
100 table_map not_null_tables() const { return 0; }
101 bool const_item() const;
102 inline table_map get_used_tables_cache() { return used_tables_cache; }
103 inline bool get_const_item_cache() { return const_item_cache; }
104 Item *get_tmp_table_item(Session *session);
105 void update_used_tables();
106 virtual void print(String *str);
107 virtual bool have_guarded_conds() { return false; }
108 bool change_engine(subselect_engine *eng)
109 {
110 old_engine= engine;
111 engine= eng;
112 engine_changed= 1;
113 return eng == 0;
114 }
115 /*
116 True if this subquery has been already evaluated. Implemented only for
117 single select and union subqueries only.
118 */
119 bool is_evaluated() const;
120 bool is_uncacheable() const;
121
122 /*
123 Used by max/min subquery to initialize value presence registration
124 mechanism. Engine call this method before rexecution query.
125 */
126 virtual void reset_value_registration() {}
127 enum_parsing_place place() { return parsing_place; }
128 bool walk(Item_processor processor, bool walk_subquery, unsigned char *arg);
129
134 Select_Lex* get_select_lex();
135
136 friend class select_result_interceptor;
137 friend class Item_in_optimizer;
138 friend bool Item_field::fix_fields(Session *, Item **);
139 friend int Item_field::fix_outer_field(Session *, Field **, Item **);
140 friend bool Item_ref::fix_fields(Session *, Item **);
141 friend void mark_select_range_as_dependent(Session*,
142 Select_Lex*, Select_Lex*,
143 Field*, Item*, Item_ident*);
144};
145
146/* single value subselect */
147
148class Item_singlerow_subselect :public Item_subselect
149{
150protected:
151 Item_cache *value, **row;
152public:
153 Item_singlerow_subselect(Select_Lex *select_lex);
154 Item_singlerow_subselect() :Item_subselect(), value(0), row (0) {}
155
156 void cleanup();
157 subs_type substype() { return SINGLEROW_SUBS; }
158
159 void reset();
160 trans_res select_transformer(Join *join);
161 void store(uint32_t i, Item* item);
162 double val_real();
163 int64_t val_int ();
164 String *val_str (String *);
166 bool val_bool();
167 enum Item_result result_type() const;
168 enum_field_types field_type() const;
169 void fix_length_and_dec();
170
171 uint32_t cols();
172 Item* element_index(uint32_t i) { return reinterpret_cast<Item*>(row[i]); }
173 Item** addr(uint32_t i) { return (Item**)row + i; }
174 bool check_cols(uint32_t c);
175 bool null_inside();
176 void bring_value();
177
191
192 friend class select_singlerow_subselect;
193};
194
195/* used in static ALL/ANY optimization */
196class Item_maxmin_subselect :public Item_singlerow_subselect
197{
198protected:
199 bool max;
200 bool was_values; // Set if we have found at least one row
201public:
202 Item_maxmin_subselect(Session *session, Item_subselect *parent,
203 Select_Lex *select_lex, bool max);
204 virtual void print(String *str);
205 void cleanup();
206 bool any_value() { return was_values; }
207 void register_value() { was_values= true; }
208 void reset_value_registration() { was_values= false; }
209};
210
211/* exists subselect */
212
213class Item_exists_subselect :public Item_subselect
214{
215protected:
216 bool value; /* value of this item (boolean: exists/not-exists) */
217
218public:
219 Item_exists_subselect(Select_Lex *select_lex);
220 Item_exists_subselect(): Item_subselect() {}
221
222 subs_type substype() { return EXISTS_SUBS; }
223 void reset()
224 {
225 value= 0;
226 }
227
228 enum Item_result result_type() const { return INT_RESULT;}
229 int64_t val_int();
230 double val_real();
233 bool val_bool();
234 void fix_length_and_dec();
235 virtual void print(String *str);
236
237 friend class select_exists_subselect;
238 friend class subselect_uniquesubquery_engine;
239 friend class subselect_indexsubquery_engine;
240};
241
242
257
258class Item_in_subselect :public Item_exists_subselect
259{
260public:
261 Item *left_expr;
262protected:
263 /*
264 Cache of the left operand of the subquery predicate. Allocated in the
265 runtime memory root, for each execution, thus need not be freed.
266 */
267 List<Cached_item> *left_expr_cache;
268 bool first_execution;
269
270 /*
271 expr & optimizer used in subselect rewriting to store Item for
272 all JOIN in UNION
273 */
274 Item *expr;
275 Item_in_optimizer *optimizer;
276 bool was_null;
277 bool abort_on_null;
278
279public:
280 /* Used to trigger on/off conditions that were pushed down to subselect */
281 bool *pushed_cond_guards;
282
283 /* Priority of this predicate in the convert-to-semi-join-nest process. */
284 int sj_convert_priority;
285
286 /*
287 Location of the subquery predicate. It is either
288 - pointer to join nest if the subquery predicate is in the ON expression
289 - (TableList*)1 if the predicate is in the WHERE.
290 */
291 TableList *expr_join_nest;
292
293 /* The method chosen to execute the IN predicate. */
294 enum enum_exec_method {
295 NOT_TRANSFORMED, /* No execution method was chosen for this IN. */
296 SEMI_JOIN, /* IN was converted to semi-join nest and should be removed. */
297 IN_TO_EXISTS, /* IN was converted to correlated EXISTS. */
298 MATERIALIZATION /* IN will be executed via subquery materialization. */
299 };
300 enum_exec_method exec_method;
301
302 bool *get_cond_guard(int i)
303 {
304 return pushed_cond_guards ? pushed_cond_guards + i : NULL;
305 }
306 void set_cond_guard_var(int i, bool v)
307 {
308 if ( pushed_cond_guards)
309 pushed_cond_guards[i]= v;
310 }
311 bool have_guarded_conds() { return test(pushed_cond_guards); }
312
313 Item_func_not_all *upper_item; // point on NOT/NOP before ALL/SOME subquery
314
315 Item_in_subselect(Item * left_expr, Select_Lex *select_lex);
316 Item_in_subselect()
317 :
318 Item_exists_subselect(),
319 left_expr(NULL),
320 left_expr_cache(NULL),
321 first_execution(true),
322 optimizer(NULL),
323 abort_on_null(false),
324 pushed_cond_guards(NULL),
325 sj_convert_priority(0),
326 expr_join_nest(NULL),
327 exec_method(NOT_TRANSFORMED),
328 upper_item(NULL)
329 {}
330 void cleanup();
331 subs_type substype() { return IN_SUBS; }
332 void reset()
333 {
334 value= 0;
335 null_value= 0;
336 was_null= 0;
337 }
338 trans_res select_transformer(Join *join);
339 trans_res select_in_like_transformer(Join *join, const Comp_creator *func);
340 trans_res single_value_transformer(Join *join, const Comp_creator *func);
341 trans_res row_value_transformer(Join * join);
343 const Comp_creator *func);
345 virtual bool exec();
346 int64_t val_int();
347 double val_real();
350 void update_null_value () { (void) val_bool(); }
351 bool val_bool();
352 void top_level_item() { abort_on_null=1; }
353 inline bool is_top_level_item() { return abort_on_null; }
354 bool test_limit(Select_Lex_Unit *unit);
355 virtual void print(String *str);
356 bool fix_fields(Session *session, Item **ref);
357 bool setup_engine();
359 bool is_expensive_processor(unsigned char *arg);
360
361 friend class Item_ref_null_helper;
362 friend class Item_is_not_null_test;
363 friend class Item_in_optimizer;
364 friend class subselect_indexsubquery_engine;
365 friend class subselect_hash_sj_engine;
366};
367
368
369/* ALL/ANY/SOME subselect */
370class Item_allany_subselect :public Item_in_subselect
371{
372public:
373 chooser_compare_func_creator func_creator;
374 Comp_creator *func;
375 bool all;
376
377 Item_allany_subselect(Item * left_expr, chooser_compare_func_creator fc,
378 Select_Lex *select_lex, bool all);
379
380 // only ALL subquery has upper not
381 subs_type substype() { return all?ALL_SUBS:ANY_SUBS; }
382 trans_res select_transformer(Join *join);
383 virtual void print(String *str);
384};
385
386
387class subselect_engine: public memory::SqlAlloc
388{
389protected:
390 select_result_interceptor *result; /* results storage class */
391 Session *session; /* pointer to current Session */
392 Item_subselect *item; /* item, that use this engine */
393 enum Item_result res_type; /* type of results */
394 enum_field_types res_field_type; /* column type of the results */
395 bool maybe_null; /* may be null (first item in select) */
396public:
397
398 enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
399 UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
400 INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE};
401
402 subselect_engine(Item_subselect *si, select_result_interceptor *res)
403 :session(NULL)
404 {
405 result= res;
406 item= si;
407 res_type= STRING_RESULT;
408 res_field_type= DRIZZLE_TYPE_VARCHAR;
409 maybe_null= 0;
410 }
411 virtual ~subselect_engine() {} // to satisfy compiler
412 virtual void cleanup()= 0;
413
414 /*
415 Also sets "session" for subselect_engine::result.
416 Should be called before prepare().
417 */
418 void set_session(Session *session_arg);
419 Session * get_session() { return session; }
420 virtual int prepare()= 0;
421 virtual void fix_length_and_dec(Item_cache** row)= 0;
422 /*
423 Execute the engine
424
425 SYNOPSIS
426 exec()
427
428 DESCRIPTION
429 Execute the engine. The result of execution is subquery value that is
430 either captured by previously set up select_result-based 'sink' or
431 stored somewhere by the exec() method itself.
432
433 A required side effect: If at least one pushed-down predicate is
434 disabled, subselect_engine->no_rows() must return correct result after
435 the exec() call.
436
437 RETURN
438 0 - OK
439 1 - Either an execution error, or the engine was "changed", and the
440 caller should call exec() again for the new engine.
441 */
442 virtual int exec()= 0;
443 virtual uint32_t cols()= 0; /* return number of columns in select */
444 virtual bool uncacheable()= 0; /* query is uncacheable */
445 virtual bool uncacheable(uint32_t bit_pos)= 0; /* query is uncacheable */
446 enum Item_result type() { return res_type; }
447 enum_field_types field_type() { return res_field_type; }
448 virtual void exclude()= 0;
449 virtual bool may_be_null() { return maybe_null; }
450 virtual table_map upper_select_const_tables()= 0;
451 static table_map calc_const_tables(TableList *);
452 virtual void print(String *str)= 0;
453 virtual bool change_result(Item_subselect *si,
454 select_result_interceptor *result)= 0;
455 virtual bool no_tables()= 0;
456 virtual bool is_executed() const { return false; }
457 /* Check if subquery produced any rows during last query execution */
458 virtual bool no_rows() = 0;
459 virtual enum_engine_type engine_type() { return ABSTRACT_ENGINE; }
460
461protected:
462 void set_row(List<Item> &item_list, Item_cache **row);
463};
464
465
466class subselect_single_select_engine: public subselect_engine
467{
468 bool prepared; /* simple subselect is prepared */
469 bool optimized; /* simple subselect is optimized */
470 bool executed; /* simple subselect is executed */
471 Select_Lex *select_lex; /* corresponding select_lex */
472 Join * join; /* corresponding JOIN structure */
473public:
474 subselect_single_select_engine(Select_Lex *select,
476 Item_subselect *item);
477 void cleanup();
478 int prepare();
479 void fix_length_and_dec(Item_cache** row);
480 int exec();
481 uint32_t cols();
482 bool uncacheable();
483 bool uncacheable(uint32_t bit_pos);
484 void exclude();
485 table_map upper_select_const_tables();
486 virtual void print (String *str);
488 bool no_tables();
489 bool may_be_null();
490 bool is_executed() const { return executed; }
491 bool no_rows();
492 virtual enum_engine_type engine_type() { return SINGLE_SELECT_ENGINE; }
493 void save_join_if_explain();
494
495 friend class subselect_hash_sj_engine;
496 friend class Item_in_subselect;
497};
498
499
500class subselect_union_engine: public subselect_engine
501{
502 Select_Lex_Unit *unit; /* corresponding unit structure */
503public:
504 subselect_union_engine(Select_Lex_Unit *u,
506 Item_subselect *item);
507 void cleanup();
508 int prepare();
509 void fix_length_and_dec(Item_cache** row);
510 int exec();
511 uint32_t cols();
512 bool uncacheable();
513 bool uncacheable(uint32_t bit_pos);
514 void exclude();
515 table_map upper_select_const_tables();
516 virtual void print (String *str);
518 bool no_tables();
519 bool is_executed() const;
520 bool no_rows();
521 virtual enum_engine_type engine_type() { return UNION_ENGINE; }
522};
523
524
525/*
526 A subquery execution engine that evaluates the subquery by doing one index
527 lookup in a unique index.
528
529 This engine is used to resolve subqueries in forms
530
531 outer_expr IN (SELECT tbl.unique_key FROM tbl WHERE subq_where)
532
533 or, tuple-based:
534
535 (oe1, .. oeN) IN (SELECT uniq_key_part1, ... uniq_key_partK
536 FROM tbl WHERE subqwhere)
537
538 i.e. the subquery is a single table SELECT without GROUP BY, aggregate
539 functions, etc.
540*/
541
542class subselect_uniquesubquery_engine: public subselect_engine
543{
544protected:
545 JoinTable *tab;
546 Item *cond; /* The WHERE condition of subselect */
547 /*
548 TRUE<=> last execution produced empty set. Valid only when left
549 expression is NULL.
550 */
551 bool empty_result_set;
552 bool null_keypart; /* TRUE <=> constructed search tuple has a NULL */
553public:
554
555 // constructor can assign Session because it will be called after Join::prepare
556 subselect_uniquesubquery_engine(Session *session_arg, JoinTable *tab_arg,
557 Item_subselect *subs, Item *where)
558 :subselect_engine(subs, 0), tab(tab_arg), cond(where)
559 {
560 set_session(session_arg);
561 }
562 void cleanup();
563 int prepare();
564 void fix_length_and_dec(Item_cache** row);
565 int exec();
566 uint32_t cols() { return 1; }
567 bool uncacheable() { return true; }
568 bool uncacheable(uint32_t) { return true; }
569 void exclude();
570 table_map upper_select_const_tables() { return 0; }
571 virtual void print (String *str);
573 bool no_tables();
574 int scan_table();
575 bool copy_ref_key();
576 bool no_rows() { return empty_result_set; }
577 virtual enum_engine_type engine_type() { return UNIQUESUBQUERY_ENGINE; }
578};
579
580
581class subselect_indexsubquery_engine: public subselect_uniquesubquery_engine
582{
583 /* FALSE for 'ref', TRUE for 'ref-or-null'. */
584 bool check_null;
585 /*
586 The "having" clause. This clause (further reffered to as "artificial
587 having") was inserted by subquery transformation code. It contains
588 Item(s) that have a side-effect: they record whether the subquery has
589 produced a row with NULL certain components. We need to use it for cases
590 like
591 (oe1, oe2) IN (SELECT t.key, t.no_key FROM t1)
592 where we do index lookup on t.key=oe1 but need also to check if there
593 was a row such that t.no_key IS NULL.
594
595 NOTE: This is currently here and not in the uniquesubquery_engine. Ideally
596 it should have been in uniquesubquery_engine in order to allow execution of
597 subqueries like
598
599 (oe1, oe2) IN (SELECT primary_key, non_key_maybe_null_field FROM tbl)
600
601 We could use uniquesubquery_engine for the first component and let
602 Item_is_not_null_test( non_key_maybe_null_field) to handle the second.
603
604 However, subqueries like the above are currently not handled by index
605 lookup-based subquery engines, the engine applicability check misses
606 them: it doesn't switch the engine for case of artificial having and
607 [eq_]ref access (only for artifical having + ref_or_null or no having).
608 The above example subquery is handled as a full-blown SELECT with eq_ref
609 access to one table.
610
611 Due to this limitation, the "artificial having" currently needs to be
612 checked by only in indexsubquery_engine.
613 */
614 Item *having;
615public:
616
617 // constructor can assign Session because it will be called after Join::prepare
618 subselect_indexsubquery_engine(Session *session_arg, JoinTable *tab_arg,
619 Item_subselect *subs, Item *where,
620 Item *having_arg, bool chk_null)
621 :subselect_uniquesubquery_engine(session_arg, tab_arg, subs, where),
622 check_null(chk_null),
623 having(having_arg)
624 {}
625 int exec();
626 virtual void print (String *str);
627 virtual enum_engine_type engine_type() { return INDEXSUBQUERY_ENGINE; }
628};
629
630
631inline bool Item_subselect::is_evaluated() const
632{
633 return engine->is_executed();
634}
635
636
637inline bool Item_subselect::is_uncacheable() const
638{
639 return engine->uncacheable();
640}
641
642
648
649class subselect_hash_sj_engine: public subselect_uniquesubquery_engine
650{
651protected:
652 /* TRUE if the subquery was materialized into a temp table. */
653 bool is_materialized;
654 /*
655 The old engine already chosen at parse time and stored in permanent memory.
656 Through this member we can re-create and re-prepare materialize_join for
657 each execution of a prepared statement. We akso resuse the functionality
658 of subselect_single_select_engine::[prepare | cols].
659 */
660 subselect_single_select_engine *materialize_engine;
661 /*
662 QEP to execute the subquery and materialize its result into a
663 temporary table. Created during the first call to exec().
664 */
665 Join *materialize_join;
666 /* Temp table context of the outer select's JOIN. */
667 Tmp_Table_Param *tmp_param;
668
669public:
670 subselect_hash_sj_engine(Session *session_in, Item_subselect *in_predicate,
672 :subselect_uniquesubquery_engine(session_in, NULL, in_predicate, NULL),
673 is_materialized(false), materialize_engine(old_engine),
674 materialize_join(NULL), tmp_param(NULL)
675 {}
676 ~subselect_hash_sj_engine();
677
678 bool init_permanent(List<Item> *tmp_columns);
679 void init_runtime();
680 void cleanup();
681 int prepare() { return 0; }
682 int exec();
683 virtual void print (String *str);
684 uint32_t cols()
685 {
686 return materialize_engine->cols();
687 }
688 virtual enum_engine_type engine_type() { return HASH_SJ_ENGINE; }
689};
690
691} /* namespace drizzled */
692
virtual void print(String *str)
type::Decimal * val_decimal(type::Decimal *)
Definition subselect.cc:822
virtual void print(String *str)
Definition subselect.cc:715
bool fix_fields(Session *, Item **)
int fix_outer_field(Session *session, Field **field, Item **reference)
trans_res select_in_like_transformer(Join *join, const Comp_creator *func)
virtual void print(String *str)
type::Decimal * val_decimal(type::Decimal *)
Definition subselect.cc:933
trans_res single_value_in_to_exists_transformer(Join *join, const Comp_creator *func)
trans_res row_value_in_to_exists_transformer(Join *join)
String * val_str(String *)
Definition subselect.cc:888
virtual void print(String *str)
Definition subselect.cc:485
bool fix_fields(Session *, Item **)
Definition ref.cc:113
trans_res select_transformer(Join *join)
Definition subselect.cc:511
type::Decimal * val_decimal(type::Decimal *)
Definition subselect.cc:673
Select_Lex * invalidate_and_restore_select_lex()
Definition subselect.cc:425
Select_Lex * get_select_lex()
Definition subselect.cc:134
friend void mark_select_range_as_dependent(Session *, Select_Lex *, Select_Lex *, Field *, Item *, Item_ident *)
Definition item.cc:797
table_map not_null_tables() const
Definition subselect.h:100
table_map used_tables() const
Definition subselect.cc:379
virtual void print(String *str)
Definition subselect.cc:408
bool null_value
Definition item.h:124
virtual void update_null_value()
Definition item.cc:518
bool init_permanent(List< Item > *tmp_columns)
virtual void print(String *str)
bool change_result(Item_subselect *si, select_result_interceptor *result)
bool change_result(Item_subselect *si, select_result_interceptor *result)
bool change_result(Item_subselect *si, select_result_interceptor *result)
TODO: Rename this file - func.h is stupid.