1 /*
2 Copyright (c) 2016, 2017 MariaDB
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17 #ifndef SQL_CTE_INCLUDED
18 #define SQL_CTE_INCLUDED
19 #include "sql_list.h"
20 #include "sql_lex.h"
21 #include "sql_select.h"
22
23 class select_unit;
24 struct st_unit_ctxt_elem;
25
26
27 /**
28 @class With_element_head
29 @brief Head of the definition of a CTE table
30
31 It contains the name of the CTE and it contains the position of the subchain
32 of table references used in the definition in the global chain of table
33 references used in the query where this definition is encountered.
34 */
35
36 class With_element_head : public Sql_alloc
37 {
38 /* The name of the defined CTE */
39 LEX_CSTRING *query_name;
40
41 public:
42 /*
43 The structure describing the subchain of the table references used in
44 the specification of the defined CTE in the global chain of table
45 references used in the query. The structure is fully defined only
46 after the CTE definition has been parsed.
47 */
48 TABLE_CHAIN tables_pos;
49
With_element_head(LEX_CSTRING * name)50 With_element_head(LEX_CSTRING *name)
51 : query_name(name)
52 {
53 tables_pos.set_start_pos(0);
54 tables_pos.set_end_pos(0);
55 }
56 friend class With_element;
57 };
58
59
60 /**
61 @class With_element
62 @brief Definition of a CTE table
63
64 It contains a reference to the name of the table introduced by this with element,
65 and a reference to the unit that specificies this table. Also it contains
66 a reference to the with clause to which this element belongs to.
67 */
68
69 class With_element : public Sql_alloc
70 {
71 private:
72 With_clause *owner; // with clause this object belongs to
73 With_element *next; // next element in the with clause
74 uint number; // number of the element in the with clause (starting from 0)
75 table_map elem_map; // The map where with only one 1 set in this->number
76 /*
77 The map base_dep_map has 1 in the i-th position if the query that
78 specifies this with element contains a reference to the with element number i
79 in the query FROM list.
80 (In this case this with element depends directly on the i-th with element.)
81 */
82 table_map base_dep_map;
83 /*
84 The map derived_dep_map has 1 in i-th position if this with element depends
85 directly or indirectly from the i-th with element.
86 */
87 table_map derived_dep_map;
88 /*
89 The map sq_dep_map has 1 in i-th position if there is a reference to this
90 with element somewhere in subqueries of the specifications of the tables
91 defined in the with clause containing this element;
92 */
93 table_map sq_dep_map;
94 table_map work_dep_map; // dependency map used for work
95 /* Dependency map of with elements mutually recursive with this with element */
96 table_map mutually_recursive;
97 /*
98 Dependency map built only for the top level references i.e. for those that
99 are encountered in from lists of the selects of the specification unit
100 */
101 table_map top_level_dep_map;
102 /*
103 Points to a recursive reference in subqueries.
104 Used only for specifications without recursive references on the top level.
105 */
106 TABLE_LIST *sq_rec_ref;
107 /*
108 The next with element from the circular chain of the with elements
109 mutually recursive with this with element.
110 (If This element is simply recursive than next_mutually_recursive contains
111 the pointer to itself. If it's not recursive than next_mutually_recursive
112 is set to NULL.)
113 */
114 With_element *next_mutually_recursive;
115 /*
116 Total number of references to this element in the FROM lists of
117 the queries that are in the scope of the element (including
118 subqueries and specifications of other with elements).
119 */
120 uint references;
121
122 /*
123 true <=> this With_element is referred in the query in which the
124 element is defined
125 */
126 bool referenced;
127
128 /*
129 true <=> this With_element is needed for the execution of the query
130 in which the element is defined
131 */
132 bool is_used_in_query;
133
134 /*
135 Unparsed specification of the query that specifies this element.
136 It's used to build clones of the specification if they are needed.
137 */
138 LEX_CSTRING unparsed_spec;
139 /* Offset of the specification in the input string */
140 my_ptrdiff_t unparsed_spec_offset;
141
142 /* True if the with element is used a prepared statement */
143 bool stmt_prepare_mode;
144
145 /* Return the map where 1 is set only in the position for this element */
get_elem_map()146 table_map get_elem_map() { return (table_map) 1 << number; }
147
148 public:
149 /*
150 Contains the name of the defined With element and the position of
151 the subchain of the tables references used by its definition in the
152 global chain of TABLE_LIST objects created for the whole query.
153 */
154 With_element_head *head;
155 /*
156 Optional list of column names to name the columns of the table introduced
157 by this with element. It is used in the case when the names are not
158 inherited from the query that specified the table. Otherwise the list is
159 always empty.
160 */
161 List <LEX_CSTRING> column_list;
162 /* The query that specifies the table introduced by this with element */
163 st_select_lex_unit *spec;
164 /*
165 Set to true is recursion is used (directly or indirectly)
166 for the definition of this element
167 */
168 bool is_recursive;
169 /*
170 For a simple recursive CTE: the number of references to the CTE from
171 outside of the CTE specification.
172 For a CTE mutually recursive with other CTEs : the total number of
173 references to all these CTEs outside of their specification.
174 Each of these mutually recursive CTEs has the same value in this field.
175 */
176 uint rec_outer_references;
177 /*
178 Any non-recursive select in the specification of a recursive
179 with element is a called anchor. In the case mutually recursive
180 elements the specification of some them may be without any anchor.
181 Yet at least one of them must contain an anchor.
182 All anchors of any recursivespecification are moved ahead before
183 the prepare stage.
184 */
185 /* Set to true if this is a recursive element with an anchor */
186 bool with_anchor;
187 /*
188 Set to the first recursive select of the unit specifying the element
189 after all anchor have been moved to the head of the unit.
190 */
191 st_select_lex *first_recursive;
192
193 /*
194 The number of the last performed iteration for recursive table
195 (the number of the initial non-recursive step is 0, the number
196 of the first iteration is 1).
197 */
198 uint level;
199
200 /*
201 The pointer to the object used to materialize this with element
202 if it's recursive. This object is built at the end of prepare
203 stage and is used at the execution stage.
204 */
205 select_union_recursive *rec_result;
206
207 /* List of Item_subselects containing recursive references to this CTE */
208 SQL_I_List<Item_subselect> sq_with_rec_ref;
209 /* List of derived tables containing recursive references to this CTE */
210 SQL_I_List<TABLE_LIST> derived_with_rec_ref;
211
With_element(With_element_head * h,List<LEX_CSTRING> list,st_select_lex_unit * unit)212 With_element(With_element_head *h,
213 List <LEX_CSTRING> list,
214 st_select_lex_unit *unit)
215 : next(NULL), base_dep_map(0), derived_dep_map(0),
216 sq_dep_map(0), work_dep_map(0), mutually_recursive(0),
217 top_level_dep_map(0), sq_rec_ref(NULL),
218 next_mutually_recursive(NULL), references(0),
219 referenced(false), is_used_in_query(false),
220 head(h), column_list(list), spec(unit),
221 is_recursive(false), rec_outer_references(0), with_anchor(false),
222 level(0), rec_result(NULL)
223 { unit->with_element= this; }
224
get_name()225 LEX_CSTRING *get_name() { return head->query_name; }
get_name_str()226 const char *get_name_str() { return get_name()->str; }
227
set_tables_start_pos(TABLE_LIST ** pos)228 void set_tables_start_pos(TABLE_LIST **pos)
229 { head->tables_pos.set_start_pos(pos); }
set_tables_end_pos(TABLE_LIST ** pos)230 void set_tables_end_pos(TABLE_LIST **pos)
231 { head->tables_pos.set_end_pos(pos); }
232
233 bool check_dependencies_in_spec();
234
235 void check_dependencies_in_select(st_select_lex *sl, st_unit_ctxt_elem *ctxt,
236 bool in_subq, table_map *dep_map);
237
238 void check_dependencies_in_unit(st_select_lex_unit *unit,
239 st_unit_ctxt_elem *ctxt,
240 bool in_subq,
241 table_map *dep_map);
242
243 void check_dependencies_in_with_clause(With_clause *with_clause,
244 st_unit_ctxt_elem *ctxt,
245 bool in_subq,
246 table_map *dep_map);
247
set_dependency_on(With_element * with_elem)248 void set_dependency_on(With_element *with_elem)
249 { base_dep_map|= with_elem->get_elem_map(); }
250
check_dependency_on(With_element * with_elem)251 bool check_dependency_on(With_element *with_elem)
252 { return base_dep_map & with_elem->get_elem_map(); }
253
254 TABLE_LIST *find_first_sq_rec_ref_in_select(st_select_lex *sel);
255
256 bool set_unparsed_spec(THD *thd, char *spec_start, char *spec_end,
257 my_ptrdiff_t spec_offset);
258
259 st_select_lex_unit *clone_parsed_spec(LEX *old_lex, TABLE_LIST *with_table);
260
is_referenced()261 bool is_referenced() { return referenced; }
262
is_hanging_recursive()263 bool is_hanging_recursive() { return is_recursive && !rec_outer_references; }
264
inc_references()265 void inc_references() { references++; }
266
267 bool rename_columns_of_derived_unit(THD *thd, st_select_lex_unit *unit);
268
269 bool prepare_unreferenced(THD *thd);
270
271 bool check_unrestricted_recursive(st_select_lex *sel,
272 table_map &unrestricted,
273 table_map &encountered);
274
275 void print(String *str, enum_query_type query_type);
276
get_owner()277 With_clause *get_owner() { return owner; }
278
contains_sq_with_recursive_reference()279 bool contains_sq_with_recursive_reference()
280 { return sq_dep_map & mutually_recursive; }
281
no_rec_ref_on_top_level()282 bool no_rec_ref_on_top_level()
283 { return !(top_level_dep_map & mutually_recursive); }
284
get_mutually_recursive()285 table_map get_mutually_recursive() { return mutually_recursive; }
286
get_next_mutually_recursive()287 With_element *get_next_mutually_recursive()
288 { return next_mutually_recursive; }
289
get_sq_rec_ref()290 TABLE_LIST *get_sq_rec_ref() { return sq_rec_ref; }
291
292 bool is_anchor(st_select_lex *sel);
293
294 void move_anchors_ahead();
295
296 bool is_unrestricted();
297
298 bool is_with_prepared_anchor();
299
300 void mark_as_with_prepared_anchor();
301
302 bool is_cleaned();
303
304 void mark_as_cleaned();
305
306 void reset_recursive_for_exec();
307
308 void cleanup_stabilized();
309
310 void set_as_stabilized();
311
312 bool is_stabilized();
313
314 bool all_are_stabilized();
315
316 bool instantiate_tmp_tables();
317
318 void prepare_for_next_iteration();
319
320 friend class With_clause;
321
322 friend
323 bool LEX::resolve_references_to_cte(TABLE_LIST *tables,
324 TABLE_LIST **tables_last);
325 friend
326 bool LEX::resolve_references_to_cte_in_hanging_cte();
327 };
328
329 const uint max_number_of_elements_in_with_clause= sizeof(table_map)*8;
330
331 /**
332 @class With_clause
333 @brief Set of with_elements
334
335 It has a reference to the first with element from this with clause.
336 This reference allows to navigate through all the elements of the with clause.
337 It contains a reference to the unit to which this with clause is attached.
338 It also contains a flag saying whether this with clause was specified as recursive.
339 */
340
341 class With_clause : public Sql_alloc
342 {
343 private:
344 st_select_lex_unit *owner; // the unit this with clause attached to
345
346 /* The list of all with elements from this with clause */
347 SQL_I_List<With_element> with_list;
348 /*
349 The with clause immediately containing this with clause if there is any,
350 otherwise NULL. Now used only at parsing.
351 */
352 With_clause *embedding_with_clause;
353 /*
354 The next with the clause of the chain of with clauses encountered
355 in the current statement
356 */
357 With_clause *next_with_clause;
358 /* Set to true if dependencies between with elements have been checked */
359 bool dependencies_are_checked;
360
361 /*
362 The bitmap of all recursive with elements whose specifications
363 are not complied with restrictions imposed by the SQL standards
364 on recursive specifications.
365 */
366 table_map unrestricted;
367 /*
368 The bitmap of all recursive with elements whose anchors
369 has been already prepared.
370 */
371 table_map with_prepared_anchor;
372 table_map cleaned;
373 /*
374 The bitmap of all recursive with elements that
375 has been already materialized
376 */
377 table_map stabilized;
378
379 public:
380 /* If true the specifier RECURSIVE is present in the with clause */
381 bool with_recursive;
382
With_clause(bool recursive_fl,With_clause * emb_with_clause)383 With_clause(bool recursive_fl, With_clause *emb_with_clause)
384 : owner(NULL),
385 embedding_with_clause(emb_with_clause), next_with_clause(NULL),
386 dependencies_are_checked(false), unrestricted(0),
387 with_prepared_anchor(0), cleaned(0), stabilized(0),
388 with_recursive(recursive_fl)
389 { }
390
391 bool add_with_element(With_element *elem);
392
393 /* Add this with clause to the list of with clauses used in the statement */
add_to_list(With_clause ** & last_next)394 void add_to_list(With_clause ** &last_next)
395 {
396 *last_next= this;
397 last_next= &this->next_with_clause;
398 }
399
set_owner(st_select_lex_unit * unit)400 void set_owner(st_select_lex_unit *unit) { owner= unit; }
401
pop()402 With_clause *pop() { return embedding_with_clause; }
403
404 bool check_dependencies();
405
406 bool check_anchors();
407
408 void move_anchors_ahead();
409
410 With_element *find_table_def(TABLE_LIST *table, With_element *barrier);
411
412 With_element *find_table_def_in_with_clauses(TABLE_LIST *table);
413
414 bool prepare_unreferenced_elements(THD *thd);
415
add_unrestricted(table_map map)416 void add_unrestricted(table_map map) { unrestricted|= map; }
417
418 void print(String *str, enum_query_type query_type);
419
420 friend class With_element;
421
422 friend
423 bool LEX::check_dependencies_in_with_clauses();
424
425 friend
426 bool LEX::resolve_references_to_cte_in_hanging_cte();
427 };
428
429 inline
is_unrestricted()430 bool With_element::is_unrestricted()
431 {
432 return owner->unrestricted & get_elem_map();
433 }
434
435 inline
436
is_with_prepared_anchor()437 bool With_element::is_with_prepared_anchor()
438 {
439 return owner->with_prepared_anchor & get_elem_map();
440 }
441
442 inline
mark_as_with_prepared_anchor()443 void With_element::mark_as_with_prepared_anchor()
444 {
445 owner->with_prepared_anchor|= mutually_recursive;
446 }
447
448
449 inline
is_cleaned()450 bool With_element::is_cleaned()
451 {
452 return owner->cleaned & get_elem_map();
453 }
454
455
456 inline
mark_as_cleaned()457 void With_element::mark_as_cleaned()
458 {
459 owner->cleaned|= get_elem_map();
460 }
461
462
463 inline
reset_recursive_for_exec()464 void With_element::reset_recursive_for_exec()
465 {
466 DBUG_ASSERT(is_recursive);
467 level= 0;
468 owner->with_prepared_anchor&= ~mutually_recursive;
469 owner->cleaned&= ~get_elem_map();
470 cleanup_stabilized();
471 spec->columns_are_renamed= false;
472 }
473
474
475
476 inline
cleanup_stabilized()477 void With_element::cleanup_stabilized()
478 {
479 owner->stabilized&= ~mutually_recursive;
480 }
481
482
483 inline
set_as_stabilized()484 void With_element::set_as_stabilized()
485 {
486 owner->stabilized|= get_elem_map();
487 }
488
489
490 inline
is_stabilized()491 bool With_element::is_stabilized()
492 {
493 return owner->stabilized & get_elem_map();
494 }
495
496
497 inline
all_are_stabilized()498 bool With_element::all_are_stabilized()
499 {
500 return (owner->stabilized & mutually_recursive) == mutually_recursive;
501 }
502
503
504 inline
prepare_for_next_iteration()505 void With_element::prepare_for_next_iteration()
506 {
507 With_element *with_elem= this;
508 while ((with_elem= with_elem->get_next_mutually_recursive()) != this)
509 {
510 TABLE *rec_table= with_elem->rec_result->first_rec_table_to_update;
511 if (rec_table)
512 rec_table->reginfo.join_tab->preread_init_done= false;
513 }
514 }
515
516
517 inline
set_with_clause(With_clause * with_cl)518 void st_select_lex_unit::set_with_clause(With_clause *with_cl)
519 {
520 with_clause= with_cl;
521 if (with_clause)
522 with_clause->set_owner(this);
523 }
524
525
526 inline
set_with_clause(With_clause * with_clause)527 void st_select_lex::set_with_clause(With_clause *with_clause)
528 {
529 master_unit()->with_clause= with_clause;
530 if (with_clause)
531 with_clause->set_owner(master_unit());
532 }
533
534 #endif /* SQL_CTE_INCLUDED */
535