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