1/*****************************************************************************
2
3Copyright (c) 1997, 2016, Oracle and/or its affiliates. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc.,
1551 Franklin Street, Suite 500, Boston, MA 02110-1335 USA
16
17*****************************************************************************/
18
19/**************************************************//**
20@file pars/pars0opt.cc
21Simple SQL optimizer
22
23Created 12/21/1997 Heikki Tuuri
24*******************************************************/
25
26#include "pars0opt.h"
27#include "row0sel.h"
28#include "row0ins.h"
29#include "row0upd.h"
30#include "dict0boot.h"
31#include "dict0dict.h"
32#include "dict0mem.h"
33#include "que0que.h"
34#include "pars0grm.h"
35#include "pars0pars.h"
36#include "lock0lock.h"
37
38#define OPT_EQUAL 1 /* comparison by = */
39#define OPT_COMPARISON 2 /* comparison by <, >, <=, or >= */
40
41#define OPT_NOT_COND 1
42#define OPT_END_COND 2
43#define OPT_TEST_COND 3
44#define OPT_SCROLL_COND 4
45
46
47/*******************************************************************//**
48Inverts a comparison operator.
49@return the equivalent operator when the order of the arguments is switched */
50static
51int
52opt_invert_cmp_op(
53/*==============*/
54 int op) /*!< in: operator */
55{
56 if (op == '<') {
57 return('>');
58 } else if (op == '>') {
59 return('<');
60 } else if (op == '=') {
61 return('=');
62 } else if (op == PARS_LE_TOKEN) {
63 return(PARS_GE_TOKEN);
64 } else if (op == PARS_GE_TOKEN) {
65 return(PARS_LE_TOKEN);
66 } else {
67 /* TODO: LIKE operator */
68 ut_error;
69 }
70
71 return(0);
72}
73
74/*******************************************************************//**
75Checks if the value of an expression can be calculated BEFORE the nth table
76in a join is accessed. If this is the case, it can possibly be used in an
77index search for the nth table.
78@return TRUE if already determined */
79static
80ibool
81opt_check_exp_determined_before(
82/*============================*/
83 que_node_t* exp, /*!< in: expression */
84 sel_node_t* sel_node, /*!< in: select node */
85 ulint nth_table) /*!< in: nth table will be accessed */
86{
87 func_node_t* func_node;
88 sym_node_t* sym_node;
89 dict_table_t* table;
90 que_node_t* arg;
91 ulint i;
92
93 ut_ad(exp && sel_node);
94
95 if (que_node_get_type(exp) == QUE_NODE_FUNC) {
96 func_node = static_cast<func_node_t*>(exp);
97
98 arg = func_node->args;
99
100 while (arg) {
101 if (!opt_check_exp_determined_before(arg, sel_node,
102 nth_table)) {
103 return(FALSE);
104 }
105
106 arg = que_node_get_next(arg);
107 }
108
109 return(TRUE);
110 }
111
112 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
113
114 sym_node = static_cast<sym_node_t*>(exp);
115
116 if (sym_node->token_type != SYM_COLUMN) {
117
118 return(TRUE);
119 }
120
121 for (i = 0; i < nth_table; i++) {
122
123 table = sel_node_get_nth_plan(sel_node, i)->table;
124
125 if (sym_node->table == table) {
126
127 return(TRUE);
128 }
129 }
130
131 return(FALSE);
132}
133
134/*******************************************************************//**
135Looks in a comparison condition if a column value is already restricted by
136it BEFORE the nth table is accessed.
137@return expression restricting the value of the column, or NULL if not known */
138static
139que_node_t*
140opt_look_for_col_in_comparison_before(
141/*==================================*/
142 ulint cmp_type, /*!< in: OPT_EQUAL, OPT_COMPARISON */
143 ulint col_no, /*!< in: column number */
144 func_node_t* search_cond, /*!< in: comparison condition */
145 sel_node_t* sel_node, /*!< in: select node */
146 ulint nth_table, /*!< in: nth table in a join (a query
147 from a single table is considered a
148 join of 1 table) */
149 ulint* op) /*!< out: comparison operator ('=',
150 PARS_GE_TOKEN, ... ); this is inverted
151 if the column appears on the right
152 side */
153{
154 sym_node_t* sym_node;
155 dict_table_t* table;
156 que_node_t* exp;
157 que_node_t* arg;
158
159 ut_ad(search_cond);
160
161 ut_a((search_cond->func == '<')
162 || (search_cond->func == '>')
163 || (search_cond->func == '=')
164 || (search_cond->func == PARS_GE_TOKEN)
165 || (search_cond->func == PARS_LE_TOKEN)
166 || (search_cond->func == PARS_LIKE_TOKEN_EXACT)
167 || (search_cond->func == PARS_LIKE_TOKEN_PREFIX)
168 || (search_cond->func == PARS_LIKE_TOKEN_SUFFIX)
169 || (search_cond->func == PARS_LIKE_TOKEN_SUBSTR));
170
171 table = sel_node_get_nth_plan(sel_node, nth_table)->table;
172
173 if ((cmp_type == OPT_EQUAL)
174 && (search_cond->func != '=')
175 && (search_cond->func != PARS_LIKE_TOKEN_EXACT)
176 && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)) {
177
178 return(NULL);
179
180 } else if ((cmp_type == OPT_COMPARISON)
181 && (search_cond->func != '<')
182 && (search_cond->func != '>')
183 && (search_cond->func != PARS_GE_TOKEN)
184 && (search_cond->func != PARS_LE_TOKEN)
185 && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)
186 && (search_cond->func != PARS_LIKE_TOKEN_SUFFIX)) {
187
188 return(NULL);
189 }
190
191 arg = search_cond->args;
192
193 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
194 sym_node = static_cast<sym_node_t*>(arg);
195
196 if ((sym_node->token_type == SYM_COLUMN)
197 && (sym_node->table == table)
198 && (sym_node->col_no == col_no)) {
199
200 /* sym_node contains the desired column id */
201
202 /* Check if the expression on the right side of the
203 operator is already determined */
204
205 exp = que_node_get_next(arg);
206
207 if (opt_check_exp_determined_before(exp, sel_node,
208 nth_table)) {
209 *op = ulint(search_cond->func);
210
211 return(exp);
212 }
213 }
214 }
215
216 exp = search_cond->args;
217 arg = que_node_get_next(arg);
218
219 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
220 sym_node = static_cast<sym_node_t*>(arg);
221
222 if ((sym_node->token_type == SYM_COLUMN)
223 && (sym_node->table == table)
224 && (sym_node->col_no == col_no)) {
225
226 if (opt_check_exp_determined_before(exp, sel_node,
227 nth_table)) {
228 *op = ulint(opt_invert_cmp_op(
229 search_cond->func));
230
231 return(exp);
232 }
233 }
234 }
235
236 return(NULL);
237}
238
239/*******************************************************************//**
240Looks in a search condition if a column value is already restricted by the
241search condition BEFORE the nth table is accessed. Takes into account that
242if we will fetch in an ascending order, we cannot utilize an upper limit for
243a column value; in a descending order, respectively, a lower limit.
244@return expression restricting the value of the column, or NULL if not known */
245static
246que_node_t*
247opt_look_for_col_in_cond_before(
248/*============================*/
249 ulint cmp_type, /*!< in: OPT_EQUAL, OPT_COMPARISON */
250 ulint col_no, /*!< in: column number */
251 func_node_t* search_cond, /*!< in: search condition or NULL */
252 sel_node_t* sel_node, /*!< in: select node */
253 ulint nth_table, /*!< in: nth table in a join (a query
254 from a single table is considered a
255 join of 1 table) */
256 ulint* op) /*!< out: comparison operator ('=',
257 PARS_GE_TOKEN, ... ) */
258{
259 func_node_t* new_cond;
260 que_node_t* exp;
261
262 if (search_cond == NULL) {
263
264 return(NULL);
265 }
266
267 ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
268 ut_a(search_cond->func != PARS_OR_TOKEN);
269 ut_a(search_cond->func != PARS_NOT_TOKEN);
270
271 if (search_cond->func == PARS_AND_TOKEN) {
272 new_cond = static_cast<func_node_t*>(search_cond->args);
273
274 exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
275 new_cond, sel_node,
276 nth_table, op);
277 if (exp) {
278
279 return(exp);
280 }
281
282 new_cond = static_cast<func_node_t*>(
283 que_node_get_next(new_cond));
284
285 exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
286 new_cond, sel_node,
287 nth_table, op);
288 return(exp);
289 }
290
291 exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
292 search_cond, sel_node,
293 nth_table, op);
294 if (exp == NULL) {
295
296 return(NULL);
297 }
298
299 /* If we will fetch in an ascending order, we cannot utilize an upper
300 limit for a column value; in a descending order, respectively, a lower
301 limit */
302
303 if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {
304
305 return(NULL);
306
307 } else if (!sel_node->asc
308 && ((*op == '>') || (*op == PARS_GE_TOKEN))) {
309
310 return(NULL);
311 }
312
313 return(exp);
314}
315
316/*******************************************************************//**
317Calculates the goodness for an index according to a select node. The
318goodness is 4 times the number of first fields in index whose values we
319already know exactly in the query. If we have a comparison condition for
320an additional field, 2 point are added. If the index is unique, and we know
321all the unique fields for the index we add 1024 points. For a clustered index
322we add 1 point.
323@return goodness */
324static
325ulint
326opt_calc_index_goodness(
327/*====================*/
328 dict_index_t* index, /*!< in: index */
329 sel_node_t* sel_node, /*!< in: parsed select node */
330 ulint nth_table, /*!< in: nth table in a join */
331 que_node_t** index_plan, /*!< in/out: comparison expressions for
332 this index */
333 ulint* last_op) /*!< out: last comparison operator, if
334 goodness > 1 */
335{
336 que_node_t* exp;
337 ulint goodness;
338 ulint n_fields;
339 ulint col_no;
340 ulint op;
341 ulint j;
342
343 /* At least for now we don't support using FTS indexes for queries
344 done through InnoDB's own SQL parser. */
345 if (dict_index_is_online_ddl(index) || (index->type & DICT_FTS)) {
346 return(0);
347 }
348
349 goodness = 0;
350
351 /* Note that as higher level node pointers in the B-tree contain
352 page addresses as the last field, we must not put more fields in
353 the search tuple than dict_index_get_n_unique_in_tree(index); see
354 the note in btr_cur_search_to_nth_level. */
355
356 n_fields = dict_index_get_n_unique_in_tree(index);
357
358 for (j = 0; j < n_fields; j++) {
359
360 col_no = dict_index_get_nth_col_no(index, j);
361
362 exp = opt_look_for_col_in_cond_before(
363 OPT_EQUAL, col_no,
364 static_cast<func_node_t*>(sel_node->search_cond),
365 sel_node, nth_table, &op);
366 if (exp) {
367 /* The value for this column is exactly known already
368 at this stage of the join */
369
370 index_plan[j] = exp;
371 *last_op = op;
372 goodness += 4;
373 } else {
374 /* Look for non-equality comparisons */
375
376 exp = opt_look_for_col_in_cond_before(
377 OPT_COMPARISON, col_no,
378 static_cast<func_node_t*>(
379 sel_node->search_cond),
380 sel_node, nth_table, &op);
381 if (exp) {
382 index_plan[j] = exp;
383 *last_op = op;
384 goodness += 2;
385 }
386
387 break;
388 }
389 }
390
391 if (goodness >= 4 * dict_index_get_n_unique(index)) {
392 goodness += 1024;
393
394 if (dict_index_is_clust(index)) {
395
396 goodness += 1024;
397 }
398 }
399
400 /* We have to test for goodness here, as last_op may not be set */
401 if (goodness && dict_index_is_clust(index)) {
402
403 goodness++;
404 }
405
406 return(goodness);
407}
408
409/*******************************************************************//**
410Calculates the number of matched fields based on an index goodness.
411@return number of excatly or partially matched fields */
412UNIV_INLINE
413ulint
414opt_calc_n_fields_from_goodness(
415/*============================*/
416 ulint goodness) /*!< in: goodness */
417{
418 return(((goodness % 1024) + 2) / 4);
419}
420
421/*******************************************************************//**
422Converts a comparison operator to the corresponding search mode PAGE_CUR_GE,
423...
424@return search mode */
425UNIV_INLINE
426page_cur_mode_t
427opt_op_to_search_mode(
428/*==================*/
429 ibool asc, /*!< in: TRUE if the rows should be fetched in an
430 ascending order */
431 ulint op) /*!< in: operator '=', PARS_GE_TOKEN, ... */
432{
433 if (op == '='
434 || op == PARS_LIKE_TOKEN_EXACT
435 || op == PARS_LIKE_TOKEN_PREFIX
436 || op == PARS_LIKE_TOKEN_SUFFIX
437 || op == PARS_LIKE_TOKEN_SUBSTR) {
438
439 if (asc) {
440 return(PAGE_CUR_GE);
441 } else {
442 return(PAGE_CUR_LE);
443 }
444 } else if (op == '<') {
445 ut_a(!asc);
446 return(PAGE_CUR_L);
447 } else if (op == '>') {
448 ut_a(asc);
449 return(PAGE_CUR_G);
450 } else if (op == PARS_GE_TOKEN) {
451 ut_a(asc);
452 return(PAGE_CUR_GE);
453 } else if (op == PARS_LE_TOKEN) {
454 ut_a(!asc);
455 return(PAGE_CUR_LE);
456 } else {
457 ut_error;
458 }
459
460 return(PAGE_CUR_UNSUPP);
461}
462
463/*******************************************************************//**
464Determines if a node is an argument node of a function node.
465@return TRUE if is an argument */
466static
467ibool
468opt_is_arg(
469/*=======*/
470 que_node_t* arg_node, /*!< in: possible argument node */
471 func_node_t* func_node) /*!< in: function node */
472{
473 que_node_t* arg;
474
475 arg = func_node->args;
476
477 while (arg) {
478 if (arg == arg_node) {
479
480 return(TRUE);
481 }
482
483 arg = que_node_get_next(arg);
484 }
485
486 return(FALSE);
487}
488
489/*******************************************************************//**
490Decides if the fetching of rows should be made in a descending order, and
491also checks that the chosen query plan produces a result which satisfies
492the order-by. */
493static
494void
495opt_check_order_by(
496/*===============*/
497 sel_node_t* sel_node) /*!< in: select node; asserts an error
498 if the plan does not agree with the
499 order-by */
500{
501 order_node_t* order_node;
502 dict_table_t* order_table;
503 ulint order_col_no;
504 plan_t* plan;
505 ulint i;
506
507 if (!sel_node->order_by) {
508
509 return;
510 }
511
512 order_node = sel_node->order_by;
513 order_col_no = order_node->column->col_no;
514 order_table = order_node->column->table;
515
516 /* If there is an order-by clause, the first non-exactly matched field
517 in the index used for the last table in the table list should be the
518 column defined in the order-by clause, and for all the other tables
519 we should get only at most a single row, otherwise we cannot presently
520 calculate the order-by, as we have no sort utility */
521
522 for (i = 0; i < sel_node->n_tables; i++) {
523
524 plan = sel_node_get_nth_plan(sel_node, i);
525
526 if (i < sel_node->n_tables - 1) {
527 ut_a(dict_index_get_n_unique(plan->index)
528 <= plan->n_exact_match);
529 } else {
530 ut_a(plan->table == order_table);
531
532 ut_a((dict_index_get_n_unique(plan->index)
533 <= plan->n_exact_match)
534 || (dict_index_get_nth_col_no(plan->index,
535 plan->n_exact_match)
536 == order_col_no));
537 }
538 }
539}
540
541/*******************************************************************//**
542Optimizes a select. Decides which indexes to tables to use. The tables
543are accessed in the order that they were written to the FROM part in the
544select statement. */
545static
546void
547opt_search_plan_for_table(
548/*======================*/
549 sel_node_t* sel_node, /*!< in: parsed select node */
550 ulint i, /*!< in: this is the ith table */
551 dict_table_t* table) /*!< in: table */
552{
553 plan_t* plan;
554 dict_index_t* index;
555 dict_index_t* best_index;
556 ulint n_fields;
557 ulint goodness;
558 ulint last_op = 75946965; /* Eliminate a Purify
559 warning */
560 ulint best_goodness;
561 ulint best_last_op = 0; /* remove warning */
562 que_node_t* index_plan[256];
563 que_node_t* best_index_plan[256];
564
565 plan = sel_node_get_nth_plan(sel_node, i);
566
567 plan->table = table;
568 plan->asc = sel_node->asc;
569 plan->pcur_is_open = FALSE;
570 plan->cursor_at_end = FALSE;
571
572 /* Calculate goodness for each index of the table */
573
574 index = dict_table_get_first_index(table);
575 best_index = index; /* Eliminate compiler warning */
576 best_goodness = 0;
577
578 /* should be do ... until ? comment by Jani */
579 while (index) {
580 goodness = opt_calc_index_goodness(index, sel_node, i,
581 index_plan, &last_op);
582 if (goodness > best_goodness) {
583
584 best_index = index;
585 best_goodness = goodness;
586 n_fields = opt_calc_n_fields_from_goodness(goodness);
587
588 ut_memcpy(best_index_plan, index_plan,
589 n_fields * sizeof(void*));
590 best_last_op = last_op;
591 }
592
593 dict_table_next_uncorrupted_index(index);
594 }
595
596 plan->index = best_index;
597
598 n_fields = opt_calc_n_fields_from_goodness(best_goodness);
599
600 if (n_fields == 0) {
601 plan->tuple = NULL;
602 plan->n_exact_match = 0;
603 } else {
604 plan->tuple = dtuple_create(pars_sym_tab_global->heap,
605 n_fields);
606 dict_index_copy_types(plan->tuple, plan->index, n_fields);
607
608 plan->tuple_exps = static_cast<que_node_t**>(
609 mem_heap_alloc(
610 pars_sym_tab_global->heap,
611 n_fields * sizeof(void*)));
612
613 ut_memcpy(plan->tuple_exps, best_index_plan,
614 n_fields * sizeof(void*));
615 if (best_last_op == '='
616 || best_last_op == PARS_LIKE_TOKEN_EXACT
617 || best_last_op == PARS_LIKE_TOKEN_PREFIX
618 || best_last_op == PARS_LIKE_TOKEN_SUFFIX
619 || best_last_op == PARS_LIKE_TOKEN_SUBSTR) {
620 plan->n_exact_match = n_fields;
621 } else {
622 plan->n_exact_match = n_fields - 1;
623 }
624
625 plan->mode = opt_op_to_search_mode(sel_node->asc,
626 best_last_op);
627 }
628
629 if (dict_index_is_clust(best_index)
630 && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
631
632 plan->unique_search = TRUE;
633 } else {
634 plan->unique_search = FALSE;
635 }
636
637 plan->old_vers_heap = NULL;
638
639 btr_pcur_init(&(plan->pcur));
640 btr_pcur_init(&(plan->clust_pcur));
641}
642
643/*******************************************************************//**
644Looks at a comparison condition and decides if it can, and need, be tested for
645a table AFTER the table has been accessed.
646@return OPT_NOT_COND if not for this table, else OPT_END_COND,
647OPT_TEST_COND, or OPT_SCROLL_COND, where the last means that the
648condition need not be tested, except when scroll cursors are used */
649static
650ulint
651opt_classify_comparison(
652/*====================*/
653 sel_node_t* sel_node, /*!< in: select node */
654 ulint i, /*!< in: ith table in the join */
655 func_node_t* cond) /*!< in: comparison condition */
656{
657 plan_t* plan;
658 ulint n_fields;
659 ulint op;
660 ulint j;
661
662 ut_ad(cond && sel_node);
663
664 plan = sel_node_get_nth_plan(sel_node, i);
665
666 /* Check if the condition is determined after the ith table has been
667 accessed, but not after the i - 1:th */
668
669 if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
670
671 return(OPT_NOT_COND);
672 }
673
674 if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
675
676 return(OPT_NOT_COND);
677 }
678
679 /* If the condition is an exact match condition used in constructing
680 the search tuple, it is classified as OPT_END_COND */
681
682 if (plan->tuple) {
683 n_fields = dtuple_get_n_fields(plan->tuple);
684 } else {
685 n_fields = 0;
686 }
687
688 for (j = 0; j < plan->n_exact_match; j++) {
689
690 if (opt_is_arg(plan->tuple_exps[j], cond)) {
691
692 return(OPT_END_COND);
693 }
694 }
695
696 /* If the condition is an non-exact match condition used in
697 constructing the search tuple, it is classified as OPT_SCROLL_COND.
698 When the cursor is positioned, and if a non-scroll cursor is used,
699 there is no need to test this condition; if a scroll cursor is used
700 the testing is necessary when the cursor is reversed. */
701
702 if ((n_fields > plan->n_exact_match)
703 && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
704
705 return(OPT_SCROLL_COND);
706 }
707
708 /* If the condition is a non-exact match condition on the first field
709 in index for which there is no exact match, and it limits the search
710 range from the opposite side of the search tuple already BEFORE we
711 access the table, it is classified as OPT_END_COND */
712
713 if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
714 && opt_look_for_col_in_comparison_before(
715 OPT_COMPARISON,
716 dict_index_get_nth_col_no(plan->index,
717 plan->n_exact_match),
718 cond, sel_node, i, &op)) {
719
720 if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
721
722 return(OPT_END_COND);
723 }
724
725 if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
726
727 return(OPT_END_COND);
728 }
729 }
730
731 /* Otherwise, cond is classified as OPT_TEST_COND */
732
733 return(OPT_TEST_COND);
734}
735
736/*******************************************************************//**
737Recursively looks for test conditions for a table in a join. */
738static
739void
740opt_find_test_conds(
741/*================*/
742 sel_node_t* sel_node, /*!< in: select node */
743 ulint i, /*!< in: ith table in the join */
744 func_node_t* cond) /*!< in: conjunction of search
745 conditions or NULL */
746{
747 func_node_t* new_cond;
748 ulint fclass;
749 plan_t* plan;
750
751 if (cond == NULL) {
752
753 return;
754 }
755
756 if (cond->func == PARS_AND_TOKEN) {
757 new_cond = static_cast<func_node_t*>(cond->args);
758
759 opt_find_test_conds(sel_node, i, new_cond);
760
761 new_cond = static_cast<func_node_t*>(
762 que_node_get_next(new_cond));
763
764 opt_find_test_conds(sel_node, i, new_cond);
765
766 return;
767 }
768
769 plan = sel_node_get_nth_plan(sel_node, i);
770
771 fclass = opt_classify_comparison(sel_node, i, cond);
772
773 if (fclass == OPT_END_COND) {
774 UT_LIST_ADD_LAST(plan->end_conds, cond);
775
776 } else if (fclass == OPT_TEST_COND) {
777 UT_LIST_ADD_LAST(plan->other_conds, cond);
778
779 }
780}
781
782/*******************************************************************//**
783Normalizes a list of comparison conditions so that a column of the table
784appears on the left side of the comparison if possible. This is accomplished
785by switching the arguments of the operator. */
786static
787void
788opt_normalize_cmp_conds(
789/*====================*/
790 func_node_t* cond, /*!< in: first in a list of comparison
791 conditions, or NULL */
792 dict_table_t* table) /*!< in: table */
793{
794 que_node_t* arg1;
795 que_node_t* arg2;
796 sym_node_t* sym_node;
797
798 while (cond) {
799 arg1 = cond->args;
800 arg2 = que_node_get_next(arg1);
801
802 if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
803
804 sym_node = static_cast<sym_node_t*>(arg2);
805
806 if ((sym_node->token_type == SYM_COLUMN)
807 && (sym_node->table == table)) {
808
809 /* Switch the order of the arguments */
810
811 cond->args = arg2;
812 que_node_list_add_last(NULL, arg2);
813 que_node_list_add_last(arg2, arg1);
814
815 /* Invert the operator */
816 cond->func = opt_invert_cmp_op(cond->func);
817 }
818 }
819
820 cond = UT_LIST_GET_NEXT(cond_list, cond);
821 }
822}
823
824/*******************************************************************//**
825Finds out the search condition conjuncts we can, and need, to test as the ith
826table in a join is accessed. The search tuple can eliminate the need to test
827some conjuncts. */
828static
829void
830opt_determine_and_normalize_test_conds(
831/*===================================*/
832 sel_node_t* sel_node, /*!< in: select node */
833 ulint i) /*!< in: ith table in the join */
834{
835 plan_t* plan;
836
837 plan = sel_node_get_nth_plan(sel_node, i);
838
839 UT_LIST_INIT(plan->end_conds, &func_node_t::cond_list);
840 UT_LIST_INIT(plan->other_conds, &func_node_t::cond_list);
841
842 /* Recursively go through the conjuncts and classify them */
843
844 opt_find_test_conds(
845 sel_node,
846 i,
847 static_cast<func_node_t*>(sel_node->search_cond));
848
849 opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
850 plan->table);
851
852 ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
853}
854
855/*******************************************************************//**
856Looks for occurrences of the columns of the table in the query subgraph and
857adds them to the list of columns if an occurrence of the same column does not
858already exist in the list. If the column is already in the list, puts a value
859indirection to point to the occurrence in the column list, except if the
860column occurrence we are looking at is in the column list, in which case
861nothing is done. */
862void
863opt_find_all_cols(
864/*==============*/
865 ibool copy_val, /*!< in: if TRUE, new found columns are
866 added as columns to copy */
867 dict_index_t* index, /*!< in: index of the table to use */
868 sym_node_list_t* col_list, /*!< in: base node of a list where
869 to add new found columns */
870 plan_t* plan, /*!< in: plan or NULL */
871 que_node_t* exp) /*!< in: expression or condition or
872 NULL */
873{
874 func_node_t* func_node;
875 que_node_t* arg;
876 sym_node_t* sym_node;
877 sym_node_t* col_node;
878 ulint col_pos;
879
880 if (exp == NULL) {
881
882 return;
883 }
884
885 if (que_node_get_type(exp) == QUE_NODE_FUNC) {
886 func_node = static_cast<func_node_t*>(exp);
887
888 for (arg = func_node->args;
889 arg != 0;
890 arg = que_node_get_next(arg)) {
891
892 opt_find_all_cols(
893 copy_val, index, col_list, plan, arg);
894 }
895
896 return;
897 }
898
899 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
900
901 sym_node = static_cast<sym_node_t*>(exp);
902
903 if (sym_node->token_type != SYM_COLUMN) {
904
905 return;
906 }
907
908 if (sym_node->table != index->table) {
909
910 return;
911 }
912
913 /* Look for an occurrence of the same column in the plan column
914 list */
915
916 col_node = UT_LIST_GET_FIRST(*col_list);
917
918 while (col_node) {
919 if (col_node->col_no == sym_node->col_no) {
920
921 if (col_node == sym_node) {
922 /* sym_node was already in a list: do
923 nothing */
924
925 return;
926 }
927
928 /* Put an indirection */
929 sym_node->indirection = col_node;
930 sym_node->alias = col_node;
931
932 return;
933 }
934
935 col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
936 }
937
938 /* The same column did not occur in the list: add it */
939
940 UT_LIST_ADD_LAST(*col_list, sym_node);
941
942 sym_node->copy_val = copy_val;
943
944 /* Fill in the field_no fields in sym_node */
945
946 sym_node->field_nos[SYM_CLUST_FIELD_NO] = dict_index_get_nth_col_pos(
947 dict_table_get_first_index(index->table), sym_node->col_no,
948 NULL);
949 if (!dict_index_is_clust(index)) {
950
951 ut_a(plan);
952
953 col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no,
954 NULL);
955
956 if (col_pos == ULINT_UNDEFINED) {
957
958 plan->must_get_clust = TRUE;
959 }
960
961 sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
962 }
963}
964
965/*******************************************************************//**
966Looks for occurrences of the columns of the table in conditions which are
967not yet determined AFTER the join operation has fetched a row in the ith
968table. The values for these column must be copied to dynamic memory for
969later use. */
970static
971void
972opt_find_copy_cols(
973/*===============*/
974 sel_node_t* sel_node, /*!< in: select node */
975 ulint i, /*!< in: ith table in the join */
976 func_node_t* search_cond) /*!< in: search condition or NULL */
977{
978 func_node_t* new_cond;
979 plan_t* plan;
980
981 if (search_cond == NULL) {
982
983 return;
984 }
985
986 ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);
987
988 if (search_cond->func == PARS_AND_TOKEN) {
989 new_cond = static_cast<func_node_t*>(search_cond->args);
990
991 opt_find_copy_cols(sel_node, i, new_cond);
992
993 new_cond = static_cast<func_node_t*>(
994 que_node_get_next(new_cond));
995
996 opt_find_copy_cols(sel_node, i, new_cond);
997
998 return;
999 }
1000
1001 if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {
1002
1003 /* Any ith table columns occurring in search_cond should be
1004 copied, as this condition cannot be tested already on the
1005 fetch from the ith table */
1006
1007 plan = sel_node_get_nth_plan(sel_node, i);
1008
1009 opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
1010 search_cond);
1011 }
1012}
1013
1014/*******************************************************************//**
1015Classifies the table columns according to whether we use the column only while
1016holding the latch on the page, or whether we have to copy the column value to
1017dynamic memory. Puts the first occurrence of a column to either list in the
1018plan node, and puts indirections to later occurrences of the column. */
1019static
1020void
1021opt_classify_cols(
1022/*==============*/
1023 sel_node_t* sel_node, /*!< in: select node */
1024 ulint i) /*!< in: ith table in the join */
1025{
1026 plan_t* plan;
1027 que_node_t* exp;
1028
1029 plan = sel_node_get_nth_plan(sel_node, i);
1030
1031 /* The final value of the following field will depend on the
1032 environment of the select statement: */
1033
1034 plan->must_get_clust = FALSE;
1035
1036 UT_LIST_INIT(plan->columns, &sym_node_t::col_var_list);
1037
1038 /* All select list columns should be copied: therefore TRUE as the
1039 first argument */
1040
1041 for (exp = sel_node->select_list;
1042 exp != 0;
1043 exp = que_node_get_next(exp)) {
1044
1045 opt_find_all_cols(
1046 TRUE, plan->index, &(plan->columns), plan, exp);
1047 }
1048
1049 opt_find_copy_cols(
1050 sel_node, i, static_cast<func_node_t*>(sel_node->search_cond));
1051
1052 /* All remaining columns in the search condition are temporary
1053 columns: therefore FALSE */
1054
1055 opt_find_all_cols(
1056 FALSE, plan->index, &plan->columns, plan,
1057 static_cast<func_node_t*>(sel_node->search_cond));
1058}
1059
1060/*******************************************************************//**
1061Fills in the info in plan which is used in accessing a clustered index
1062record. The columns must already be classified for the plan node. */
1063static
1064void
1065opt_clust_access(
1066/*=============*/
1067 sel_node_t* sel_node, /*!< in: select node */
1068 ulint n) /*!< in: nth table in select */
1069{
1070 plan_t* plan;
1071 dict_table_t* table;
1072 dict_index_t* clust_index;
1073 dict_index_t* index;
1074 mem_heap_t* heap;
1075 ulint n_fields;
1076 ulint pos;
1077 ulint i;
1078
1079 plan = sel_node_get_nth_plan(sel_node, n);
1080
1081 index = plan->index;
1082
1083 /* The final value of the following field depends on the environment
1084 of the select statement: */
1085
1086 plan->no_prefetch = FALSE;
1087
1088 if (dict_index_is_clust(index)) {
1089 plan->clust_map = NULL;
1090 plan->clust_ref = NULL;
1091
1092 return;
1093 }
1094
1095 table = index->table;
1096
1097 clust_index = dict_table_get_first_index(table);
1098
1099 n_fields = dict_index_get_n_unique(clust_index);
1100
1101 heap = pars_sym_tab_global->heap;
1102
1103 plan->clust_ref = dtuple_create(heap, n_fields);
1104
1105 dict_index_copy_types(plan->clust_ref, clust_index, n_fields);
1106
1107 plan->clust_map = static_cast<ulint*>(
1108 mem_heap_alloc(heap, n_fields * sizeof(ulint)));
1109
1110 for (i = 0; i < n_fields; i++) {
1111 pos = dict_index_get_nth_field_pos(index, clust_index, i);
1112
1113 ut_a(pos != ULINT_UNDEFINED);
1114
1115 /* We optimize here only queries to InnoDB's internal system
1116 tables, and they should not contain column prefix indexes. */
1117
1118 if (dict_is_sys_table(index->table->id)
1119 && (dict_index_get_nth_field(index, pos)->prefix_len != 0
1120 || dict_index_get_nth_field(clust_index, i)
1121 ->prefix_len != 0)) {
1122 ib::error() << "Error in pars0opt.cc: table "
1123 << index->table->name
1124 << " has prefix_len != 0";
1125 }
1126
1127 *(plan->clust_map + i) = pos;
1128
1129 ut_ad(pos != ULINT_UNDEFINED);
1130 }
1131}
1132
1133#ifdef UNIV_SQL_DEBUG
1134/** Print info of a query plan.
1135@param[in,out] sel_node select node */
1136static
1137void
1138opt_print_query_plan(
1139 sel_node_t* sel_node);
1140#endif
1141
1142/*******************************************************************//**
1143Optimizes a select. Decides which indexes to tables to use. The tables
1144are accessed in the order that they were written to the FROM part in the
1145select statement. */
1146void
1147opt_search_plan(
1148/*============*/
1149 sel_node_t* sel_node) /*!< in: parsed select node */
1150{
1151 sym_node_t* table_node;
1152 dict_table_t* table;
1153 order_node_t* order_by;
1154 ulint i;
1155
1156 sel_node->plans = static_cast<plan_t*>(
1157 mem_heap_alloc(
1158 pars_sym_tab_global->heap,
1159 sel_node->n_tables * sizeof(plan_t)));
1160
1161 /* Analyze the search condition to find out what we know at each
1162 join stage about the conditions that the columns of a table should
1163 satisfy */
1164
1165 table_node = sel_node->table_list;
1166
1167 if (sel_node->order_by == NULL) {
1168 sel_node->asc = TRUE;
1169 } else {
1170 order_by = sel_node->order_by;
1171
1172 sel_node->asc = order_by->asc;
1173 }
1174
1175 for (i = 0; i < sel_node->n_tables; i++) {
1176
1177 table = table_node->table;
1178
1179 /* Choose index through which to access the table */
1180
1181 opt_search_plan_for_table(sel_node, i, table);
1182
1183 /* Determine the search condition conjuncts we can test at
1184 this table; normalize the end conditions */
1185
1186 opt_determine_and_normalize_test_conds(sel_node, i);
1187
1188 table_node = static_cast<sym_node_t*>(
1189 que_node_get_next(table_node));
1190 }
1191
1192 table_node = sel_node->table_list;
1193
1194 for (i = 0; i < sel_node->n_tables; i++) {
1195
1196 /* Classify the table columns into those we only need to access
1197 but not copy, and to those we must copy to dynamic memory */
1198
1199 opt_classify_cols(sel_node, i);
1200
1201 /* Calculate possible info for accessing the clustered index
1202 record */
1203
1204 opt_clust_access(sel_node, i);
1205
1206 table_node = static_cast<sym_node_t*>(
1207 que_node_get_next(table_node));
1208 }
1209
1210 /* Check that the plan obeys a possible order-by clause: if not,
1211 an assertion error occurs */
1212
1213 opt_check_order_by(sel_node);
1214
1215#ifdef UNIV_SQL_DEBUG
1216 opt_print_query_plan(sel_node);
1217#endif
1218}
1219
1220#ifdef UNIV_SQL_DEBUG
1221/** Print info of a query plan.
1222@param[in,out] sel_node select node */
1223static
1224void
1225opt_print_query_plan(
1226 sel_node_t* sel_node)
1227{
1228 plan_t* plan;
1229 ulint n_fields;
1230 ulint i;
1231
1232 fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);
1233
1234 fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
1235
1236 if (sel_node->set_x_locks) {
1237 fputs("sets row x-locks; ", stderr);
1238 ut_a(sel_node->row_lock_mode == LOCK_X);
1239 ut_a(!sel_node->consistent_read);
1240 } else if (sel_node->consistent_read) {
1241 fputs("consistent read; ", stderr);
1242 } else {
1243 ut_a(sel_node->row_lock_mode == LOCK_S);
1244 fputs("sets row s-locks; ", stderr);
1245 }
1246
1247 putc('\n', stderr);
1248
1249 for (i = 0; i < sel_node->n_tables; i++) {
1250 plan = sel_node_get_nth_plan(sel_node, i);
1251
1252 if (plan->tuple) {
1253 n_fields = dtuple_get_n_fields(plan->tuple);
1254 } else {
1255 n_fields = 0;
1256 }
1257
1258 fprintf(stderr,
1259 "Index %s of table %s"
1260 "; exact m. %lu, match %lu, end conds %lu\n",
1261 plan->index->name(), plan->index->table->name.m_name,
1262 (unsigned long) plan->n_exact_match,
1263 (unsigned long) n_fields,
1264 (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
1265 }
1266}
1267#endif /* UNIV_SQL_DEBUG */
1268