Drizzled Public API Documentation

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 
28 namespace drizzled {
29 
31 {
32  bool value_assigned; /* value already assigned to subselect */
33 public:
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;
40 protected:
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 
56 public:
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 
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,
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 
149 {
150 protected:
151  Item_cache *value, **row;
152 public:
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 
190  Select_Lex* invalidate_and_restore_select_lex();
191 
192  friend class select_singlerow_subselect;
193 };
194 
195 /* used in static ALL/ANY optimization */
197 {
198 protected:
199  bool max;
200  bool was_values; // Set if we have found at least one row
201 public:
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 
214 {
215 protected:
216  bool value; /* value of this item (boolean: exists/not-exists) */
217 
218 public:
219  Item_exists_subselect(Select_Lex *select_lex);
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();
231  String *val_str(String*);
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 
259 {
260 public:
261  Item *left_expr;
262 protected:
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 
279 public:
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);
317  :
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);
344  trans_res row_value_in_to_exists_transformer(Join * join);
345  virtual bool exec();
346  int64_t val_int();
347  double val_real();
348  String *val_str(String*);
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();
358  bool init_left_expr_cache();
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 */
371 {
372 public:
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 
388 {
389 protected:
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) */
396 public:
397 
398  enum enum_engine_type {ABSTRACT_ENGINE, SINGLE_SELECT_ENGINE,
399  UNION_ENGINE, UNIQUESUBQUERY_ENGINE,
400  INDEXSUBQUERY_ENGINE, HASH_SJ_ENGINE};
401 
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 
461 protected:
462  void set_row(List<Item> &item_list, Item_cache **row);
463 };
464 
465 
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 */
473 public:
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 
501 {
502  Select_Lex_Unit *unit; /* corresponding unit structure */
503 public:
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 
543 {
544 protected:
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 */
553 public:
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 
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;
615 public:
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 
631 inline bool Item_subselect::is_evaluated() const
632 {
633  return engine->is_executed();
634 }
635 
636 
637 inline bool Item_subselect::is_uncacheable() const
638 {
639  return engine->uncacheable();
640 }
641 
642 
650 {
651 protected:
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 
669 public:
670  subselect_hash_sj_engine(Session *session_in, Item_subselect *in_predicate,
671  subselect_single_select_engine *old_engine)
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  {}
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