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#include "mariadb.h"
18#include "sql_class.h"
19#include "sql_lex.h"
20#include "sql_cte.h"
21#include "sql_view.h" // for make_valid_column_names
22#include "sql_parse.h"
23#include "sql_select.h"
24
25
26/**
27 @brief
28 Add a new element to this with clause
29
30 @param elem The with element to add to this with clause
31
32 @details
33 The method adds the with element 'elem' to the elements
34 in this with clause. The method reports an error if
35 the number of the added element exceeds the value
36 of the constant max_number_of_elements_in_with_clause.
37
38 @retval
39 true if an error is reported
40 false otherwise
41*/
42
43bool With_clause::add_with_element(With_element *elem)
44{
45 if (with_list.elements == max_number_of_elements_in_with_clause)
46 {
47 my_error(ER_TOO_MANY_DEFINITIONS_IN_WITH_CLAUSE, MYF(0));
48 return true;
49 }
50 elem->owner= this;
51 elem->number= with_list.elements;
52 elem->spec->with_element= elem;
53 with_list.link_in_list(elem, &elem->next);
54 return false;
55}
56
57
58/**
59 @brief
60 Check dependencies between tables defined in a list of with clauses
61
62 @param
63 with_clauses_list Pointer to the first clause in the list
64
65 @details
66 For each with clause from the given list the procedure finds all
67 dependencies between tables defined in the clause by calling the
68 method With_clause::checked_dependencies.
69 Additionally, based on the info collected by this method the procedure
70 finds anchors for each recursive definition and moves them at the head
71 of the definition.
72
73 @retval
74 false on success
75 true on failure
76*/
77
78bool check_dependencies_in_with_clauses(With_clause *with_clauses_list)
79{
80 for (With_clause *with_clause= with_clauses_list;
81 with_clause;
82 with_clause= with_clause->next_with_clause)
83 {
84 if (with_clause->check_dependencies())
85 return true;
86 if (with_clause->check_anchors())
87 return true;
88 with_clause->move_anchors_ahead();
89 }
90 return false;
91}
92
93
94/**
95 @brief
96 Check dependencies between tables defined in this with clause
97
98 @details
99 The method performs the following for this with clause:
100 - checks that there are no definitions of the tables with the same name
101 - for each table T defined in this with clause looks for the tables
102 from the same with clause that are used in the query that specifies T
103 and set the dependencies of T on these tables in a bitmap.
104 - builds the transitive closure of the above direct dependencies
105 to find out all recursive definitions.
106
107 @retval
108 true if an error is reported
109 false otherwise
110*/
111
112bool With_clause::check_dependencies()
113{
114 if (dependencies_are_checked)
115 return false;
116 /*
117 Look for for definitions with the same query name.
118 When found report an error and return true immediately.
119 For each table T defined in this with clause look for all other tables
120 from the same with clause that are used in the specification of T.
121 For each such table set the dependency bit in the dependency map of
122 the with element for T.
123 */
124 for (With_element *with_elem= with_list.first;
125 with_elem;
126 with_elem= with_elem->next)
127 {
128 for (With_element *elem= with_list.first;
129 elem != with_elem;
130 elem= elem->next)
131 {
132 if (lex_string_cmp(system_charset_info, with_elem->query_name,
133 elem->query_name) == 0)
134 {
135 my_error(ER_DUP_QUERY_NAME, MYF(0), with_elem->query_name->str);
136 return true;
137 }
138 }
139 if (with_elem->check_dependencies_in_spec())
140 return true;
141 }
142 /* Build the transitive closure of the direct dependencies found above */
143 for (With_element *with_elem= with_list.first;
144 with_elem;
145 with_elem= with_elem->next)
146 with_elem->derived_dep_map= with_elem->base_dep_map;
147 for (With_element *with_elem= with_list.first;
148 with_elem;
149 with_elem= with_elem->next)
150 {
151 table_map with_elem_map= with_elem->get_elem_map();
152 for (With_element *elem= with_list.first; elem; elem= elem->next)
153 {
154 if (elem->derived_dep_map & with_elem_map)
155 elem->derived_dep_map |= with_elem->derived_dep_map;
156 }
157 }
158
159 /*
160 Mark those elements where tables are defined with direct or indirect
161 recursion.
162 */
163 for (With_element *with_elem= with_list.first;
164 with_elem;
165 with_elem= with_elem->next)
166 {
167 if (with_elem->derived_dep_map & with_elem->get_elem_map())
168 with_elem->is_recursive= true;
169 }
170
171 dependencies_are_checked= true;
172 return false;
173}
174
175
176/*
177 This structure describes an element of the stack of embedded units.
178 The stack is used when looking for a definition of a table in
179 with clauses. The definition can be found only in the scopes
180 of the with clauses attached to the units from the stack.
181 The with clauses are looked through from starting from the top
182 element of the stack.
183*/
184
185struct st_unit_ctxt_elem
186{
187 st_unit_ctxt_elem *prev; // the previous element of the stack
188 st_select_lex_unit *unit;
189};
190
191
192/**
193 @brief
194 Find the dependencies of this element on its siblings in its specification
195
196 @details
197 For each table reference ref(T) from the FROM list of every select sl
198 immediately contained in the specification query of this element this
199 method searches for the definition of T in the the with clause which
200 this element belongs to. If such definition is found then the dependency
201 on it is set in sl->with_dep and in this->base_dep_map.
202*/
203
204bool With_element::check_dependencies_in_spec()
205{
206 for (st_select_lex *sl= spec->first_select(); sl; sl= sl->next_select())
207 {
208 st_unit_ctxt_elem ctxt0= {NULL, owner->owner};
209 st_unit_ctxt_elem ctxt1= {&ctxt0, spec};
210 check_dependencies_in_select(sl, &ctxt1, false, &sl->with_dep);
211 base_dep_map|= sl->with_dep;
212 }
213 return false;
214}
215
216
217/**
218 @brief
219 Search for the definition of a table among the elements of this with clause
220
221 @param table The reference to the table that is looked for
222 @param barrier The barrier with element for the search
223
224 @details
225 The function looks through the elements of this with clause trying to find
226 the definition of the given table. When it encounters the element with
227 the same query name as the table's name it returns this element. If no
228 such definitions are found the function returns NULL.
229
230 @retval
231 found with element if the search succeeded
232 NULL - otherwise
233*/
234
235With_element *With_clause::find_table_def(TABLE_LIST *table,
236 With_element *barrier)
237{
238 for (With_element *with_elem= with_list.first;
239 with_elem != barrier;
240 with_elem= with_elem->next)
241 {
242 if (my_strcasecmp(system_charset_info, with_elem->query_name->str,
243 table->table_name.str) == 0 &&
244 !table->is_fqtn)
245 {
246 table->set_derived();
247 return with_elem;
248 }
249 }
250 return NULL;
251}
252
253
254/**
255 @brief
256 Search for the definition of a table in with clauses
257
258 @param tbl The reference to the table that is looked for
259 @param ctxt The context describing in what with clauses of the upper
260 levels the table has to be searched for.
261
262 @details
263 The function looks for the definition of the table tbl in the definitions
264 of the with clauses from the upper levels specified by the parameter ctxt.
265 When it encounters the element with the same query name as the table's name
266 it returns this element. If no such definitions are found the function
267 returns NULL.
268
269 @retval
270 found with element if the search succeeded
271 NULL - otherwise
272*/
273
274With_element *find_table_def_in_with_clauses(TABLE_LIST *tbl,
275 st_unit_ctxt_elem *ctxt)
276{
277 With_element *barrier= NULL;
278 for (st_unit_ctxt_elem *unit_ctxt_elem= ctxt;
279 unit_ctxt_elem;
280 unit_ctxt_elem= unit_ctxt_elem->prev)
281 {
282 st_select_lex_unit *unit= unit_ctxt_elem->unit;
283 With_clause *with_clause= unit->with_clause;
284 if (with_clause &&
285 (tbl->with= with_clause->find_table_def(tbl, barrier)))
286 return tbl->with;
287 barrier= NULL;
288 if (unit->with_element && !unit->with_element->get_owner()->with_recursive)
289 {
290 /*
291 This unit is the specification if the with element unit->with_element.
292 The with element belongs to a with clause without the specifier RECURSIVE.
293 So when searching for the matching definition of tbl this with clause must
294 be looked up to this with element
295 */
296 barrier= unit->with_element;
297 }
298 }
299 return NULL;
300}
301
302
303/**
304 @brief
305 Find the dependencies of this element on its siblings in a select
306
307 @param sl The select where to look for the dependencies
308 @param ctxt The structure specifying the scope of the definitions
309 of the with elements of the upper levels
310 @param in_sbq if true mark dependencies found in subqueries in
311 this->sq_dep_map
312 @param dep_map IN/OUT The bit where to mark the found dependencies
313
314 @details
315 For each table reference ref(T) from the FROM list of the select sl
316 the method searches in with clauses for the definition of the table T.
317 If the found definition belongs to the same with clause as this with
318 element then the method set dependency on T in the in/out parameter
319 dep_map, add if required - in this->sq_dep_map.
320 The parameter ctxt describes the proper context for the search
321 of the definition of T.
322*/
323
324void With_element::check_dependencies_in_select(st_select_lex *sl,
325 st_unit_ctxt_elem *ctxt,
326 bool in_subq,
327 table_map *dep_map)
328{
329 With_clause *with_clause= sl->get_with_clause();
330 for (TABLE_LIST *tbl= sl->table_list.first; tbl; tbl= tbl->next_local)
331 {
332 if (tbl->derived || tbl->nested_join)
333 continue;
334 tbl->with_internal_reference_map= 0;
335 /*
336 If there is a with clause attached to the unit containing sl
337 look first for the definition of tbl in this with clause.
338 If such definition is not found there look in the with
339 clauses of the upper levels.
340 If the definition of tbl is found somewhere in with clauses
341 then tbl->with is set to point to this definition
342 */
343 if (with_clause && !tbl->with)
344 tbl->with= with_clause->find_table_def(tbl, NULL);
345 if (!tbl->with)
346 tbl->with= find_table_def_in_with_clauses(tbl, ctxt);
347
348 if (tbl->with && tbl->with->owner== this->owner)
349 {
350 /*
351 The found definition T of tbl belongs to the same
352 with clause as this with element. In this case:
353 - set the dependence on T in the bitmap dep_map
354 - set tbl->with_internal_reference_map with
355 the bitmap for this definition
356 - set the dependence on T in the bitmap this->sq_dep_map
357 if needed
358 */
359 *dep_map|= tbl->with->get_elem_map();
360 tbl->with_internal_reference_map= get_elem_map();
361 if (in_subq)
362 sq_dep_map|= tbl->with->get_elem_map();
363 else
364 top_level_dep_map|= tbl->with->get_elem_map();
365 }
366 }
367 /* Now look for the dependencies in the subqueries of sl */
368 st_select_lex_unit *inner_unit= sl->first_inner_unit();
369 for (; inner_unit; inner_unit= inner_unit->next_unit())
370 {
371 if (!inner_unit->with_element)
372 check_dependencies_in_unit(inner_unit, ctxt, in_subq, dep_map);
373 }
374}
375
376
377/**
378 @brief
379 Find a recursive reference to this with element in subqueries of a select
380
381 @param sel The select in whose subqueries the reference
382 to be looked for
383
384 @details
385 The function looks for a recursive reference to this with element in
386 subqueries of select sl. When the first such reference is found
387 it is returned as the result.
388 The function assumes that the identification of all CTE references
389 has been performed earlier.
390
391 @retval
392 Pointer to the found recursive reference if the search succeeded
393 NULL - otherwise
394*/
395
396TABLE_LIST *With_element::find_first_sq_rec_ref_in_select(st_select_lex *sel)
397{
398 TABLE_LIST *rec_ref= NULL;
399 st_select_lex_unit *inner_unit= sel->first_inner_unit();
400 for (; inner_unit; inner_unit= inner_unit->next_unit())
401 {
402 st_select_lex *sl= inner_unit->first_select();
403 for (; sl; sl= sl->next_select())
404 {
405 for (TABLE_LIST *tbl= sl->table_list.first; tbl; tbl= tbl->next_local)
406 {
407 if (tbl->derived || tbl->nested_join)
408 continue;
409 if (tbl->with && tbl->with->owner== this->owner &&
410 (tbl->with_internal_reference_map & mutually_recursive))
411 {
412 rec_ref= tbl;
413 return rec_ref;
414 }
415 }
416 if ((rec_ref= find_first_sq_rec_ref_in_select(sl)))
417 return rec_ref;
418 }
419 }
420 return 0;
421}
422
423
424/**
425 @brief
426 Find the dependencies of this element on its siblings in a unit
427
428 @param unit The unit where to look for the dependencies
429 @param ctxt The structure specifying the scope of the definitions
430 of the with elements of the upper levels
431 @param in_sbq if true mark dependencies found in subqueries in
432 this->sq_dep_map
433 @param dep_map IN/OUT The bit where to mark the found dependencies
434
435 @details
436 This method searches in the unit 'unit' for the the references in FROM
437 lists of all selects contained in this unit and in the with clause
438 attached to this unit that refer to definitions of tables from the
439 same with clause as this element.
440 If such definitions are found then the dependencies on them are
441 set in the in/out parameter dep_map and optionally in this->sq_dep_map.
442 The parameter ctxt describes the proper context for the search.
443*/
444
445void With_element::check_dependencies_in_unit(st_select_lex_unit *unit,
446 st_unit_ctxt_elem *ctxt,
447 bool in_subq,
448 table_map *dep_map)
449{
450 if (unit->with_clause)
451 check_dependencies_in_with_clause(unit->with_clause, ctxt, in_subq, dep_map);
452 in_subq |= unit->item != NULL;
453 st_unit_ctxt_elem unit_ctxt_elem= {ctxt, unit};
454 st_select_lex *sl= unit->first_select();
455 for (; sl; sl= sl->next_select())
456 {
457 check_dependencies_in_select(sl, &unit_ctxt_elem, in_subq, dep_map);
458 }
459}
460
461
462/**
463 @brief
464 Find the dependencies of this element on its siblings in a with clause
465
466 @param witt_clause The with clause where to look for the dependencies
467 @param ctxt The structure specifying the scope of the definitions
468 of the with elements of the upper levels
469 @param in_sbq if true mark dependencies found in subqueries in
470 this->sq_dep_map
471 @param dep_map IN/OUT The bit where to mark the found dependencies
472
473 @details
474 This method searches in the with_clause for the the references in FROM
475 lists of all selects contained in the specifications of the with elements
476 from this with_clause that refer to definitions of tables from the
477 same with clause as this element.
478 If such definitions are found then the dependencies on them are
479 set in the in/out parameter dep_map and optionally in this->sq_dep_map.
480 The parameter ctxt describes the proper context for the search.
481*/
482
483void
484With_element::check_dependencies_in_with_clause(With_clause *with_clause,
485 st_unit_ctxt_elem *ctxt,
486 bool in_subq,
487 table_map *dep_map)
488{
489 for (With_element *with_elem= with_clause->with_list.first;
490 with_elem;
491 with_elem= with_elem->next)
492 {
493 check_dependencies_in_unit(with_elem->spec, ctxt, in_subq, dep_map);
494 }
495}
496
497
498/**
499 @brief
500 Find mutually recursive with elements and check that they have ancors
501
502 @details
503 This method performs the following:
504 - for each recursive with element finds all mutually recursive with it
505 - links each group of mutually recursive with elements into a ring chain
506 - checks that every group of mutually recursive with elements contains
507 at least one anchor
508 - checks that after removing any with element with anchor the remaining
509 with elements mutually recursive with the removed one are not recursive
510 anymore
511
512 @retval
513 true if an error is reported
514 false otherwise
515*/
516
517bool With_clause::check_anchors()
518{
519 for (With_element *with_elem= with_list.first;
520 with_elem;
521 with_elem= with_elem->next)
522 {
523 if (!with_elem->is_recursive)
524 continue;
525
526 /*
527 It with_elem is recursive with element find all elements mutually recursive
528 with it (any recursive element is mutually recursive with itself). Mark all
529 these elements in the bitmap->mutually_recursive. Also link all these
530 elements into a ring chain.
531 */
532 if (!with_elem->next_mutually_recursive)
533 {
534 With_element *last_mutually_recursive= with_elem;
535 table_map with_elem_dep= with_elem->derived_dep_map;
536 table_map with_elem_map= with_elem->get_elem_map();
537 for (With_element *elem= with_elem; elem; elem= elem->next)
538 {
539 if (!elem->is_recursive)
540 continue;
541
542 if (elem == with_elem ||
543 ((elem->derived_dep_map & with_elem_map) &&
544 (with_elem_dep & elem->get_elem_map())))
545 {
546 elem->next_mutually_recursive= with_elem;
547 last_mutually_recursive->next_mutually_recursive= elem;
548 last_mutually_recursive= elem;
549 with_elem->mutually_recursive|= elem->get_elem_map();
550 }
551 }
552 for (With_element *elem= with_elem->next_mutually_recursive;
553 elem != with_elem;
554 elem= elem->next_mutually_recursive)
555 elem->mutually_recursive= with_elem->mutually_recursive;
556 }
557
558 /*
559 For each select from the specification of 'with_elem' check whether
560 it is an anchor i.e. does not depend on any with elements mutually
561 recursive with 'with_elem".
562 */
563 for (st_select_lex *sl= with_elem->spec->first_select();
564 sl;
565 sl= sl->next_select())
566 {
567 if (with_elem->is_anchor(sl))
568 {
569 with_elem->with_anchor= true;
570 break;
571 }
572 }
573 }
574
575 /*
576 Check that for any group of mutually recursive with elements
577 - there is at least one anchor
578 - after removing any with element with anchor the remaining with elements
579 mutually recursive with the removed one are not recursive anymore
580 */
581 for (With_element *with_elem= with_list.first;
582 with_elem;
583 with_elem= with_elem->next)
584 {
585 if (!with_elem->is_recursive)
586 continue;
587
588 if (!with_elem->with_anchor)
589 {
590 /*
591 Check that the other with elements mutually recursive with 'with_elem'
592 contain at least one anchor.
593 */
594 With_element *elem= with_elem;
595 while ((elem= elem->get_next_mutually_recursive()) != with_elem)
596 {
597 if (elem->with_anchor)
598 break;
599 }
600 if (elem == with_elem)
601 {
602 my_error(ER_RECURSIVE_WITHOUT_ANCHORS, MYF(0),
603 with_elem->query_name->str);
604 return true;
605 }
606 }
607 else
608 {
609 /* 'with_elem' is a with element with an anchor */
610 With_element *elem= with_elem;
611 /*
612 For the other with elements mutually recursive with 'with_elem'
613 set dependency bits between those elements in the field work_dep_map
614 and build transitive closure of these dependencies
615 */
616 while ((elem= elem->get_next_mutually_recursive()) != with_elem)
617 elem->work_dep_map= elem->base_dep_map & elem->mutually_recursive;
618 elem= with_elem;
619 while ((elem= elem->get_next_mutually_recursive()) != with_elem)
620 {
621 table_map elem_map= elem->get_elem_map();
622 With_element *el= with_elem;
623 while ((el= el->get_next_mutually_recursive()) != with_elem)
624 {
625 if (el->work_dep_map & elem_map)
626 el->work_dep_map|= elem->work_dep_map;
627 }
628 }
629 /* If the transitive closure displays any cycle report an arror */
630 elem= with_elem;
631 while ((elem= elem->get_next_mutually_recursive()) != with_elem)
632 {
633 if (elem->work_dep_map & elem->get_elem_map())
634 {
635 my_error(ER_UNACCEPTABLE_MUTUAL_RECURSION, MYF(0),
636 with_elem->query_name->str);
637 return true;
638 }
639 }
640 }
641 }
642
643 return false;
644}
645
646
647/**
648 @brief
649 Move anchors at the beginning of the specifications for with elements
650
651 @details
652 This method moves anchors at the beginning of the specifications for
653 all recursive with elements.
654*/
655
656void With_clause::move_anchors_ahead()
657{
658 for (With_element *with_elem= with_list.first;
659 with_elem;
660 with_elem= with_elem->next)
661 {
662 if (with_elem->is_recursive)
663 with_elem->move_anchors_ahead();
664 }
665}
666
667
668/**
669 @brief
670 Move anchors at the beginning of the specification of this with element
671
672 @details
673 If the specification of this with element contains anchors the method
674 moves them at the very beginning of the specification.
675 Additionally for the other selects of the specification if none of them
676 contains a recursive reference to this with element or a mutually recursive
677 one the method looks for the first such reference in the first recursive
678 select and set a pointer to it in this->sq_rec_ref.
679*/
680
681void With_element::move_anchors_ahead()
682{
683 st_select_lex *next_sl;
684 st_select_lex *new_pos= spec->first_select();
685 new_pos->linkage= UNION_TYPE;
686 for (st_select_lex *sl= new_pos; sl; sl= next_sl)
687 {
688 next_sl= sl->next_select();
689 if (is_anchor(sl))
690 {
691 sl->move_node(new_pos);
692 if (new_pos == spec->first_select())
693 {
694 enum sub_select_type type= new_pos->linkage;
695 new_pos->linkage= sl->linkage;
696 sl->linkage= type;
697 new_pos->with_all_modifier= sl->with_all_modifier;
698 sl->with_all_modifier= false;
699 }
700 new_pos= sl->next_select();
701 }
702 else if (!sq_rec_ref && no_rec_ref_on_top_level())
703 {
704 sq_rec_ref= find_first_sq_rec_ref_in_select(sl);
705 DBUG_ASSERT(sq_rec_ref != NULL);
706 }
707 }
708 first_recursive= new_pos;
709}
710
711
712/**
713 @brief
714 Perform context analysis for all unreferenced tables defined in with clause
715
716 @param thd The context of the statement containing this with clause
717
718 @details
719 For each unreferenced table T defined in this with clause the method
720 calls the method With_element::prepare_unreferenced that performs
721 context analysis of the element with the definition of T.
722
723 @retval
724 false If context analysis does not report any error
725 true Otherwise
726*/
727
728bool With_clause::prepare_unreferenced_elements(THD *thd)
729{
730 for (With_element *with_elem= with_list.first;
731 with_elem;
732 with_elem= with_elem->next)
733 {
734 if (!with_elem->is_referenced() && with_elem->prepare_unreferenced(thd))
735 return true;
736 }
737
738 return false;
739}
740
741
742/**
743 @brief
744 Save the specification of the given with table as a string
745
746 @param thd The context of the statement containing this with element
747 @param spec_start The beginning of the specification in the input string
748 @param spec_end The end of the specification in the input string
749
750 @details
751 The method creates for a string copy of the specification used in this
752 element. The method is called when the element is parsed. The copy may be
753 used to create clones of the specification whenever they are needed.
754
755 @retval
756 false on success
757 true on failure
758*/
759
760bool With_element::set_unparsed_spec(THD *thd, char *spec_start, char *spec_end)
761{
762 unparsed_spec.length= spec_end - spec_start;
763 unparsed_spec.str= thd->strmake(spec_start, unparsed_spec.length);
764
765 if (!unparsed_spec.str)
766 {
767 my_error(ER_OUTOFMEMORY, MYF(ME_FATALERROR),
768 static_cast<int>(unparsed_spec.length));
769 return true;
770 }
771 return false;
772}
773
774
775/**
776 @brief
777 Create a clone of the specification for the given with table
778
779 @param thd The context of the statement containing this with element
780 @param with_table The reference to the table defined in this element for which
781 the clone is created.
782
783 @details
784 The method creates a clone of the specification used in this element.
785 The clone is created for the given reference to the table defined by
786 this element.
787 The clone is created when the string with the specification saved in
788 unparsed_spec is fed into the parser as an input string. The parsing
789 this string a unit object representing the specification is build.
790 A chain of all table references occurred in the specification is also
791 formed.
792 The method includes the new unit and its sub-unit into hierarchy of
793 the units of the main query. I also insert the constructed chain of the
794 table references into the chain of all table references of the main query.
795
796 @note
797 Clones is created only for not first references to tables defined in
798 the with clause. They are necessary for merged specifications because
799 the optimizer handles any such specification as independent on the others.
800 When a table defined in the with clause is materialized in a temporary table
801 one could do without specification clones. However in this case they
802 are created as well, because currently different table references to a
803 the same temporary table cannot share the same definition structure.
804
805 @retval
806 pointer to the built clone if succeeds
807 NULL - otherwise
808*/
809
810st_select_lex_unit *With_element::clone_parsed_spec(THD *thd,
811 TABLE_LIST *with_table)
812{
813 LEX *lex;
814 st_select_lex_unit *res= NULL;
815 Query_arena backup;
816 Query_arena *arena= thd->activate_stmt_arena_if_needed(&backup);
817
818 if (!(lex= (LEX*) new(thd->mem_root) st_lex_local))
819 {
820 if (arena)
821 thd->restore_active_arena(arena, &backup);
822 return res;
823 }
824 LEX *old_lex= thd->lex;
825 thd->lex= lex;
826
827 bool parse_status= false;
828 Parser_state parser_state;
829 TABLE_LIST *spec_tables;
830 TABLE_LIST *spec_tables_tail;
831 st_select_lex *with_select;
832
833 if (parser_state.init(thd, (char*) unparsed_spec.str, (unsigned int)unparsed_spec.length))
834 goto err;
835 lex_start(thd);
836 lex->stmt_lex= old_lex;
837 with_select= &lex->select_lex;
838 with_select->select_number= ++thd->lex->stmt_lex->current_select_number;
839 parse_status= parse_sql(thd, &parser_state, 0);
840 if (parse_status)
841 goto err;
842
843 if (check_dependencies_in_with_clauses(lex->with_clauses_list))
844 goto err;
845
846 spec_tables= lex->query_tables;
847 spec_tables_tail= 0;
848 for (TABLE_LIST *tbl= spec_tables;
849 tbl;
850 tbl= tbl->next_global)
851 {
852 if (!tbl->derived && !tbl->schema_table &&
853 thd->open_temporary_table(tbl))
854 goto err;
855 spec_tables_tail= tbl;
856 }
857 if (check_table_access(thd, SELECT_ACL, spec_tables, FALSE, UINT_MAX, FALSE))
858 goto err;
859 if (spec_tables)
860 {
861 if (with_table->next_global)
862 {
863 spec_tables_tail->next_global= with_table->next_global;
864 with_table->next_global->prev_global= &spec_tables_tail->next_global;
865 }
866 else
867 {
868 old_lex->query_tables_last= &spec_tables_tail->next_global;
869 }
870 spec_tables->prev_global= &with_table->next_global;
871 with_table->next_global= spec_tables;
872 }
873 res= &lex->unit;
874
875 lex->unit.include_down(with_table->select_lex);
876 lex->unit.set_slave(with_select);
877 old_lex->all_selects_list=
878 (st_select_lex*) (lex->all_selects_list->
879 insert_chain_before(
880 (st_select_lex_node **) &(old_lex->all_selects_list),
881 with_select));
882 if (check_dependencies_in_with_clauses(lex->with_clauses_list))
883 res= NULL;
884 lex_end(lex);
885err:
886 if (arena)
887 thd->restore_active_arena(arena, &backup);
888 thd->lex= old_lex;
889 return res;
890}
891
892
893/**
894 @brief
895 Rename columns of the unit derived from the spec of this with element
896 @param thd The context of the statement containing the with element
897 @param unit The specification of the with element or its clone
898
899 @details
900 The method assumes that the parameter unit is either specification itself
901 of this with element or a clone of this specification. The looks through
902 the column list in this with element. It reports an error if the cardinality
903 of this list differs from the cardinality of select lists in 'unit'.
904 Otherwise it renames the columns of the first select list and sets the flag
905 unit->column_list_is_processed to true preventing renaming columns for the
906 second time.
907
908 @retval
909 true if an error was reported
910 false otherwise
911*/
912
913bool
914With_element::rename_columns_of_derived_unit(THD *thd,
915 st_select_lex_unit *unit)
916{
917 if (unit->columns_are_renamed)
918 return false;
919
920 st_select_lex *select= unit->first_select();
921
922 if (column_list.elements) // The column list is optional
923 {
924 List_iterator_fast<Item> it(select->item_list);
925 List_iterator_fast<LEX_CSTRING> nm(column_list);
926 Item *item;
927 LEX_CSTRING *name;
928
929 if (column_list.elements != select->item_list.elements)
930 {
931 my_error(ER_WITH_COL_WRONG_LIST, MYF(0));
932 return true;
933 }
934
935 Query_arena *arena, backup;
936 arena= thd->activate_stmt_arena_if_needed(&backup);
937
938 /* Rename the columns of the first select in the unit */
939 while ((item= it++, name= nm++))
940 {
941 item->set_name(thd, name->str, (uint) name->length, system_charset_info);
942 item->is_autogenerated_name= false;
943 }
944
945 if (arena)
946 thd->restore_active_arena(arena, &backup);
947 }
948 else
949 make_valid_column_names(thd, select->item_list);
950
951 unit->columns_are_renamed= true;
952
953 return false;
954}
955
956
957/**
958 @brief
959 Perform context analysis the definition of an unreferenced table
960
961 @param thd The context of the statement containing this with element
962
963 @details
964 The method assumes that this with element contains the definition
965 of a table that is not used anywhere. In this case one has to check
966 that context conditions are met.
967
968 @retval
969 true if an error was reported
970 false otherwise
971*/
972
973bool With_element::prepare_unreferenced(THD *thd)
974{
975 bool rc= false;
976 st_select_lex *first_sl= spec->first_select();
977
978 /* Prevent name resolution for field references out of with elements */
979 for (st_select_lex *sl= first_sl;
980 sl;
981 sl= sl->next_select())
982 sl->context.outer_context= 0;
983
984 thd->lex->context_analysis_only|= CONTEXT_ANALYSIS_ONLY_DERIVED;
985 if (!spec->prepared &&
986 (spec->prepare(spec->derived, 0, 0) ||
987 rename_columns_of_derived_unit(thd, spec) ||
988 check_duplicate_names(thd, first_sl->item_list, 1)))
989 rc= true;
990
991 thd->lex->context_analysis_only&= ~CONTEXT_ANALYSIS_ONLY_DERIVED;
992 return rc;
993}
994
995
996bool With_element::is_anchor(st_select_lex *sel)
997{
998 return !(mutually_recursive & sel->with_dep);
999}
1000
1001
1002/**
1003 @brief
1004 Search for the definition of the given table referred in this select node
1005
1006 @param table reference to the table whose definition is searched for
1007
1008 @details
1009 The method looks for the definition of the table whose reference is occurred
1010 in the FROM list of this select node. First it searches for it in the
1011 with clause attached to the unit this select node belongs to. If such a
1012 definition is not found then the embedding units are looked through.
1013
1014 @retval
1015 pointer to the found definition if the search has been successful
1016 NULL - otherwise
1017*/
1018
1019With_element *st_select_lex::find_table_def_in_with_clauses(TABLE_LIST *table)
1020{
1021 With_element *found= NULL;
1022 st_select_lex_unit *master_unit;
1023 st_select_lex *outer_sl;
1024 for (st_select_lex *sl= this; sl; sl= outer_sl)
1025 {
1026 /*
1027 If sl->master_unit() is the spec of a with element then the search for
1028 a definition was already done by With_element::check_dependencies_in_spec
1029 and it was unsuccesful. Yet for units cloned from the spec it has not
1030 been done yet.
1031 */
1032 With_clause *attached_with_clause= sl->get_with_clause();
1033 if (attached_with_clause &&
1034 (found= attached_with_clause->find_table_def(table, NULL)))
1035 break;
1036 master_unit= sl->master_unit();
1037 outer_sl= master_unit->outer_select();
1038 With_element *with_elem= sl->get_with_element();
1039 if (with_elem)
1040 {
1041 With_clause *containing_with_clause= with_elem->get_owner();
1042 With_element *barrier= containing_with_clause->with_recursive ?
1043 NULL : with_elem;
1044 if ((found= containing_with_clause->find_table_def(table, barrier)))
1045 break;
1046 if (outer_sl && !outer_sl->get_with_element())
1047 break;
1048 }
1049 /* Do not look for the table's definition beyond the scope of the view */
1050 if (master_unit->is_view)
1051 break;
1052 }
1053 return found;
1054}
1055
1056
1057/**
1058 @brief
1059 Set the specifying unit in this reference to a with table
1060
1061 @details
1062 The method assumes that the given element with_elem defines the table T
1063 this table reference refers to.
1064 If this is the first reference to T the method just sets its specification
1065 in the field 'derived' as the unit that yields T. Otherwise the method
1066 first creates a clone specification and sets rather this clone in this field.
1067
1068 @retval
1069 false on success
1070 true on failure
1071*/
1072
1073bool TABLE_LIST::set_as_with_table(THD *thd, With_element *with_elem)
1074{
1075 if (table)
1076 {
1077 /*
1078 This table was prematurely identified as a temporary table.
1079 We correct it here, but it's not a nice solution in the case
1080 when the temporary table with this name is not used anywhere
1081 else in the query.
1082 */
1083 thd->mark_tmp_table_as_free_for_reuse(table);
1084 table= 0;
1085 }
1086 with= with_elem;
1087 if (!with_elem->is_referenced() || with_elem->is_recursive)
1088 {
1089 derived= with_elem->spec;
1090 if (derived != select_lex->master_unit() &&
1091 !is_with_table_recursive_reference())
1092 {
1093 derived->move_as_slave(select_lex);
1094 }
1095 }
1096 else
1097 {
1098 if(!(derived= with_elem->clone_parsed_spec(thd, this)))
1099 return true;
1100 }
1101 derived->first_select()->linkage= DERIVED_TABLE_TYPE;
1102 with_elem->inc_references();
1103 return false;
1104}
1105
1106
1107bool TABLE_LIST::is_recursive_with_table()
1108{
1109 return with && with->is_recursive;
1110}
1111
1112
1113/*
1114 A reference to a with table T is recursive if it occurs somewhere
1115 in the query specifying T or in the query specifying one of the tables
1116 mutually recursive with T.
1117*/
1118
1119bool TABLE_LIST::is_with_table_recursive_reference()
1120{
1121 return (with_internal_reference_map &&
1122 (with->get_mutually_recursive() & with_internal_reference_map));
1123}
1124
1125
1126/*
1127 Specifications of with tables with recursive table references
1128 in non-mergeable derived tables are not allowed in this
1129 implementation.
1130*/
1131
1132
1133/*
1134 We say that the specification of a with table T is restricted
1135 if all below is true.
1136 1. Any immediate select of the specification contains at most one
1137 recursive table reference taking into account table references
1138 from mergeable derived tables.
1139 2. Any recursive table reference is not an inner operand of an
1140 outer join operation used in an immediate select of the
1141 specification.
1142 3. Any immediate select from the specification of T does not
1143 contain aggregate functions.
1144 4. The specification of T does not contain recursive table references.
1145
1146 If the specification of T is not restricted we call the corresponding
1147 with element unrestricted.
1148
1149 The SQL standards allows only with elements with restricted specification.
1150 By default we comply with the standards here.
1151
1152 Yet we allow unrestricted specification if the status variable
1153 'standards_compliant_cte' set to 'off'(0).
1154*/
1155
1156
1157/**
1158 @brief
1159 Check if this select makes the including specification unrestricted
1160
1161 @param
1162 only_standards_compliant true if the system variable
1163 'standards_compliant_cte' is set to 'on'
1164 @details
1165 This method checks whether the conditions 1-4 (see the comment above)
1166 are satisfied for this select. If not then mark this element as
1167 unrestricted and report an error if 'only_standards_compliant' is true.
1168
1169 @retval
1170 true if an error is reported
1171 false otherwise
1172*/
1173
1174bool st_select_lex::check_unrestricted_recursive(bool only_standard_compliant)
1175{
1176 With_element *with_elem= get_with_element();
1177 if (!with_elem ||!with_elem->is_recursive)
1178 {
1179 /*
1180 If this select is not from the specifiocation of a with elememt or
1181 if this not a recursive with element then there is nothing to check.
1182 */
1183 return false;
1184 }
1185
1186 /* Check conditions 1-2 for restricted specification*/
1187 table_map unrestricted= 0;
1188 table_map encountered= 0;
1189 if (with_elem->check_unrestricted_recursive(this,
1190 unrestricted,
1191 encountered))
1192 return true;
1193 with_elem->get_owner()->add_unrestricted(unrestricted);
1194
1195
1196 /* Check conditions 3-4 for restricted specification*/
1197 if ((with_sum_func && !with_elem->is_anchor(this)) ||
1198 (with_elem->contains_sq_with_recursive_reference()))
1199 with_elem->get_owner()->add_unrestricted(
1200 with_elem->get_mutually_recursive());
1201
1202 /* Report an error on unrestricted specification if this is required */
1203 if (only_standard_compliant && with_elem->is_unrestricted())
1204 {
1205 my_error(ER_NOT_STANDARD_COMPLIANT_RECURSIVE,
1206 MYF(0), with_elem->query_name->str);
1207 return true;
1208 }
1209
1210 return false;
1211}
1212
1213
1214/**
1215 @brief
1216 Check if a select from the spec of this with element is partially restricted
1217
1218 @param
1219 sel select from the specification of this element where to check
1220 whether conditions 1-2 are satisfied
1221 unrestricted IN/OUT bitmap where to mark unrestricted specs
1222 encountered IN/OUT bitmap where to mark encountered recursive references
1223 @details
1224 This method checks whether the conditions 1-2 (see the comment above)
1225 are satisfied for the select sel.
1226 This method is called recursively for derived tables.
1227
1228 @retval
1229 true if an error is reported
1230 false otherwise
1231*/
1232
1233bool With_element::check_unrestricted_recursive(st_select_lex *sel,
1234 table_map &unrestricted,
1235 table_map &encountered)
1236{
1237 /* Check conditions 1 for restricted specification*/
1238 List_iterator<TABLE_LIST> ti(sel->leaf_tables);
1239 TABLE_LIST *tbl;
1240 while ((tbl= ti++))
1241 {
1242 st_select_lex_unit *unit= tbl->get_unit();
1243 if (unit)
1244 {
1245 if(!tbl->is_with_table())
1246 {
1247 if (check_unrestricted_recursive(unit->first_select(),
1248 unrestricted,
1249 encountered))
1250 return true;
1251 }
1252 if (!(tbl->is_recursive_with_table() && unit->with_element->owner == owner))
1253 continue;
1254 With_element *with_elem= unit->with_element;
1255 if (encountered & with_elem->get_elem_map())
1256 unrestricted|= with_elem->mutually_recursive;
1257 else
1258 encountered|= with_elem->get_elem_map();
1259 }
1260 }
1261 for (With_element *with_elem= owner->with_list.first;
1262 with_elem;
1263 with_elem= with_elem->next)
1264 {
1265 if (!with_elem->is_recursive && (unrestricted & with_elem->get_elem_map()))
1266 continue;
1267 if (encountered & with_elem->get_elem_map())
1268 {
1269 uint cnt= 0;
1270 table_map encountered_mr= encountered & with_elem->mutually_recursive;
1271 for (table_map map= encountered_mr >> with_elem->number;
1272 map != 0;
1273 map>>= 1)
1274 {
1275 if (map & 1)
1276 {
1277 if (cnt)
1278 {
1279 unrestricted|= with_elem->mutually_recursive;
1280 break;
1281 }
1282 else
1283 cnt++;
1284 }
1285 }
1286 }
1287 }
1288
1289
1290 /* Check conditions 2 for restricted specification*/
1291 ti.rewind();
1292 while ((tbl= ti++))
1293 {
1294 if (!tbl->is_with_table_recursive_reference())
1295 continue;
1296 for (TABLE_LIST *tab= tbl; tab; tab= tab->embedding)
1297 {
1298 if (tab->outer_join & (JOIN_TYPE_LEFT | JOIN_TYPE_RIGHT))
1299 {
1300 unrestricted|= mutually_recursive;
1301 break;
1302 }
1303 }
1304 }
1305 return false;
1306}
1307
1308
1309/**
1310 @brief
1311 Check subqueries with recursive table references from FROM list of this select
1312
1313 @details
1314 For each recursive table reference from the FROM list of this select
1315 this method checks:
1316 - whether this reference is within a materialized derived table and
1317 if so it report an error
1318 - whether this reference is within a subquery and if so it set a flag
1319 in this subquery that disallows some optimization strategies for
1320 this subquery.
1321
1322 @retval
1323 true if an error is reported
1324 false otherwise
1325*/
1326
1327bool st_select_lex::check_subqueries_with_recursive_references()
1328{
1329 List_iterator<TABLE_LIST> ti(leaf_tables);
1330 TABLE_LIST *tbl;
1331 while ((tbl= ti++))
1332 {
1333 if (!(tbl->is_with_table_recursive_reference()))
1334 continue;
1335 With_element *rec_elem= tbl->with;
1336 st_select_lex_unit *sl_master;
1337 for (st_select_lex *sl= this; sl; sl= sl_master->outer_select())
1338 {
1339 sl_master= sl->master_unit();
1340 if (sl_master->with_element &&
1341 sl_master->with_element->get_owner() == rec_elem->get_owner())
1342 break;
1343 sl->uncacheable|= UNCACHEABLE_DEPENDENT;
1344 sl_master->uncacheable|= UNCACHEABLE_DEPENDENT;
1345 if (sl_master->derived)
1346 sl_master->derived->register_as_derived_with_rec_ref(rec_elem);
1347 if (sl_master->item)
1348 {
1349 Item_subselect *subq= (Item_subselect *) (sl_master->item);
1350 subq->register_as_with_rec_ref(rec_elem);
1351 }
1352 }
1353 }
1354 return false;
1355}
1356
1357
1358/**
1359 @brief
1360 Print this with clause
1361
1362 @param str Where to print to
1363 @param query_type The mode of printing
1364
1365 @details
1366 The method prints a string representation of this clause in the
1367 string str. The parameter query_type specifies the mode of printing.
1368*/
1369
1370void With_clause::print(String *str, enum_query_type query_type)
1371{
1372 /*
1373 Any with clause contains just definitions of CTE tables.
1374 No data expansion is applied to these definitions.
1375 */
1376 query_type= (enum_query_type) (query_type | QT_NO_DATA_EXPANSION);
1377
1378 str->append(STRING_WITH_LEN("with "));
1379 if (with_recursive)
1380 str->append(STRING_WITH_LEN("recursive "));
1381 for (With_element *with_elem= with_list.first;
1382 with_elem;
1383 with_elem= with_elem->next)
1384 {
1385 if (with_elem != with_list.first)
1386 str->append(", ");
1387 with_elem->print(str, query_type);
1388 }
1389}
1390
1391
1392/**
1393 @brief
1394 Print this with element
1395
1396 @param str Where to print to
1397 @param query_type The mode of printing
1398
1399 @details
1400 The method prints a string representation of this with element in the
1401 string str. The parameter query_type specifies the mode of printing.
1402*/
1403
1404void With_element::print(String *str, enum_query_type query_type)
1405{
1406 str->append(query_name);
1407 str->append(STRING_WITH_LEN(" as "));
1408 str->append('(');
1409 spec->print(str, query_type);
1410 str->append(')');
1411}
1412
1413
1414bool With_element::instantiate_tmp_tables()
1415{
1416 List_iterator_fast<TABLE> li(rec_result->rec_tables);
1417 TABLE *rec_table;
1418 while ((rec_table= li++))
1419 {
1420 if (!rec_table->is_created() &&
1421 instantiate_tmp_table(rec_table,
1422 rec_table->s->key_info,
1423 rec_result->tmp_table_param.start_recinfo,
1424 &rec_result->tmp_table_param.recinfo,
1425 0))
1426 return true;
1427
1428 rec_table->file->extra(HA_EXTRA_WRITE_CACHE);
1429 rec_table->file->extra(HA_EXTRA_IGNORE_DUP_KEY);
1430 }
1431 return false;
1432}
1433
1434