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