1 /*****************************************************************************
2
3 Copyright (c) 1997, 2021, Oracle and/or its affiliates.
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 "dict0boot.h"
44 #include "dict0dict.h"
45 #include "dict0mem.h"
46 #include "que0que.h"
47 #include "pars0grm.h"
48 #include "pars0pars.h"
49 #include "lock0lock.h"
50
51 #define OPT_EQUAL 1 /* comparison by = */
52 #define OPT_COMPARISON 2 /* comparison by <, >, <=, or >= */
53
54 #define OPT_NOT_COND 1
55 #define OPT_END_COND 2
56 #define OPT_TEST_COND 3
57 #define OPT_SCROLL_COND 4
58
59
60 /*******************************************************************//**
61 Inverts a comparison operator.
62 @return the equivalent operator when the order of the arguments is switched */
63 static
64 int
opt_invert_cmp_op(int op)65 opt_invert_cmp_op(
66 /*==============*/
67 int op) /*!< in: operator */
68 {
69 if (op == '<') {
70 return('>');
71 } else if (op == '>') {
72 return('<');
73 } else if (op == '=') {
74 return('=');
75 } else if (op == PARS_LE_TOKEN) {
76 return(PARS_GE_TOKEN);
77 } else if (op == PARS_GE_TOKEN) {
78 return(PARS_LE_TOKEN);
79 } else {
80 /* TODO: LIKE operator */
81 ut_error;
82 }
83
84 return(0);
85 }
86
87 /*******************************************************************//**
88 Checks if the value of an expression can be calculated BEFORE the nth table
89 in a join is accessed. If this is the case, it can possibly be used in an
90 index search for the nth table.
91 @return TRUE if already determined */
92 static
93 ibool
opt_check_exp_determined_before(que_node_t * exp,sel_node_t * sel_node,ulint nth_table)94 opt_check_exp_determined_before(
95 /*============================*/
96 que_node_t* exp, /*!< in: expression */
97 sel_node_t* sel_node, /*!< in: select node */
98 ulint nth_table) /*!< in: nth table will be accessed */
99 {
100 func_node_t* func_node;
101 sym_node_t* sym_node;
102 dict_table_t* table;
103 que_node_t* arg;
104 ulint i;
105
106 ut_ad(exp && sel_node);
107
108 if (que_node_get_type(exp) == QUE_NODE_FUNC) {
109 func_node = static_cast<func_node_t*>(exp);
110
111 arg = func_node->args;
112
113 while (arg) {
114 if (!opt_check_exp_determined_before(arg, sel_node,
115 nth_table)) {
116 return(FALSE);
117 }
118
119 arg = que_node_get_next(arg);
120 }
121
122 return(TRUE);
123 }
124
125 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
126
127 sym_node = static_cast<sym_node_t*>(exp);
128
129 if (sym_node->token_type != SYM_COLUMN) {
130
131 return(TRUE);
132 }
133
134 for (i = 0; i < nth_table; i++) {
135
136 table = sel_node_get_nth_plan(sel_node, i)->table;
137
138 if (sym_node->table == table) {
139
140 return(TRUE);
141 }
142 }
143
144 return(FALSE);
145 }
146
147 /*******************************************************************//**
148 Looks in a comparison condition if a column value is already restricted by
149 it BEFORE the nth table is accessed.
150 @return expression restricting the value of the column, or NULL if not known */
151 static
152 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)153 opt_look_for_col_in_comparison_before(
154 /*==================================*/
155 ulint cmp_type, /*!< in: OPT_EQUAL, OPT_COMPARISON */
156 ulint col_no, /*!< in: column number */
157 func_node_t* search_cond, /*!< in: comparison condition */
158 sel_node_t* sel_node, /*!< in: select node */
159 ulint nth_table, /*!< in: nth table in a join (a query
160 from a single table is considered a
161 join of 1 table) */
162 ulint* op) /*!< out: comparison operator ('=',
163 PARS_GE_TOKEN, ... ); this is inverted
164 if the column appears on the right
165 side */
166 {
167 sym_node_t* sym_node;
168 dict_table_t* table;
169 que_node_t* exp;
170 que_node_t* arg;
171
172 ut_ad(search_cond);
173
174 ut_a((search_cond->func == '<')
175 || (search_cond->func == '>')
176 || (search_cond->func == '=')
177 || (search_cond->func == PARS_GE_TOKEN)
178 || (search_cond->func == PARS_LE_TOKEN)
179 || (search_cond->func == PARS_LIKE_TOKEN_EXACT)
180 || (search_cond->func == PARS_LIKE_TOKEN_PREFIX)
181 || (search_cond->func == PARS_LIKE_TOKEN_SUFFIX)
182 || (search_cond->func == PARS_LIKE_TOKEN_SUBSTR));
183
184 table = sel_node_get_nth_plan(sel_node, nth_table)->table;
185
186 if ((cmp_type == OPT_EQUAL)
187 && (search_cond->func != '=')
188 && (search_cond->func != PARS_LIKE_TOKEN_EXACT)
189 && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)) {
190
191 return(NULL);
192
193 } else if ((cmp_type == OPT_COMPARISON)
194 && (search_cond->func != '<')
195 && (search_cond->func != '>')
196 && (search_cond->func != PARS_GE_TOKEN)
197 && (search_cond->func != PARS_LE_TOKEN)
198 && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)
199 && (search_cond->func != PARS_LIKE_TOKEN_SUFFIX)) {
200
201 return(NULL);
202 }
203
204 arg = search_cond->args;
205
206 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
207 sym_node = static_cast<sym_node_t*>(arg);
208
209 if ((sym_node->token_type == SYM_COLUMN)
210 && (sym_node->table == table)
211 && (sym_node->col_no == col_no)) {
212
213 /* sym_node contains the desired column id */
214
215 /* Check if the expression on the right side of the
216 operator is already determined */
217
218 exp = que_node_get_next(arg);
219
220 if (opt_check_exp_determined_before(exp, sel_node,
221 nth_table)) {
222 *op = search_cond->func;
223
224 return(exp);
225 }
226 }
227 }
228
229 exp = search_cond->args;
230 arg = que_node_get_next(arg);
231
232 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
233 sym_node = static_cast<sym_node_t*>(arg);
234
235 if ((sym_node->token_type == SYM_COLUMN)
236 && (sym_node->table == table)
237 && (sym_node->col_no == col_no)) {
238
239 if (opt_check_exp_determined_before(exp, sel_node,
240 nth_table)) {
241 *op = opt_invert_cmp_op(search_cond->func);
242
243 return(exp);
244 }
245 }
246 }
247
248 return(NULL);
249 }
250
251 /*******************************************************************//**
252 Looks in a search condition if a column value is already restricted by the
253 search condition BEFORE the nth table is accessed. Takes into account that
254 if we will fetch in an ascending order, we cannot utilize an upper limit for
255 a column value; in a descending order, respectively, a lower limit.
256 @return expression restricting the value of the column, or NULL if not known */
257 static
258 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)259 opt_look_for_col_in_cond_before(
260 /*============================*/
261 ulint cmp_type, /*!< in: OPT_EQUAL, OPT_COMPARISON */
262 ulint col_no, /*!< in: column number */
263 func_node_t* search_cond, /*!< in: search condition or NULL */
264 sel_node_t* sel_node, /*!< in: select node */
265 ulint nth_table, /*!< in: nth table in a join (a query
266 from a single table is considered a
267 join of 1 table) */
268 ulint* op) /*!< out: comparison operator ('=',
269 PARS_GE_TOKEN, ... ) */
270 {
271 func_node_t* new_cond;
272 que_node_t* exp;
273
274 if (search_cond == NULL) {
275
276 return(NULL);
277 }
278
279 ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
280 ut_a(search_cond->func != PARS_OR_TOKEN);
281 ut_a(search_cond->func != PARS_NOT_TOKEN);
282
283 if (search_cond->func == PARS_AND_TOKEN) {
284 new_cond = static_cast<func_node_t*>(search_cond->args);
285
286 exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
287 new_cond, sel_node,
288 nth_table, op);
289 if (exp) {
290
291 return(exp);
292 }
293
294 new_cond = static_cast<func_node_t*>(
295 que_node_get_next(new_cond));
296
297 exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
298 new_cond, sel_node,
299 nth_table, op);
300 return(exp);
301 }
302
303 exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
304 search_cond, sel_node,
305 nth_table, op);
306 if (exp == NULL) {
307
308 return(NULL);
309 }
310
311 /* If we will fetch in an ascending order, we cannot utilize an upper
312 limit for a column value; in a descending order, respectively, a lower
313 limit */
314
315 if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {
316
317 return(NULL);
318
319 } else if (!sel_node->asc
320 && ((*op == '>') || (*op == PARS_GE_TOKEN))) {
321
322 return(NULL);
323 }
324
325 return(exp);
326 }
327
328 /*******************************************************************//**
329 Calculates the goodness for an index according to a select node. The
330 goodness is 4 times the number of first fields in index whose values we
331 already know exactly in the query. If we have a comparison condition for
332 an additional field, 2 point are added. If the index is unique, and we know
333 all the unique fields for the index we add 1024 points. For a clustered index
334 we add 1 point.
335 @return goodness */
336 static
337 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)338 opt_calc_index_goodness(
339 /*====================*/
340 dict_index_t* index, /*!< in: index */
341 sel_node_t* sel_node, /*!< in: parsed select node */
342 ulint nth_table, /*!< in: nth table in a join */
343 que_node_t** index_plan, /*!< in/out: comparison expressions for
344 this index */
345 ulint* last_op) /*!< out: last comparison operator, if
346 goodness > 1 */
347 {
348 que_node_t* exp;
349 ulint goodness;
350 ulint n_fields;
351 ulint col_no;
352 ulint op;
353 ulint j;
354
355 /* At least for now we don't support using FTS indexes for queries
356 done through InnoDB's own SQL parser. */
357 if (dict_index_is_online_ddl(index) || (index->type & DICT_FTS)) {
358 return(0);
359 }
360
361 goodness = 0;
362
363 /* Note that as higher level node pointers in the B-tree contain
364 page addresses as the last field, we must not put more fields in
365 the search tuple than dict_index_get_n_unique_in_tree(index); see
366 the note in btr_cur_search_to_nth_level. */
367
368 n_fields = dict_index_get_n_unique_in_tree(index);
369
370 for (j = 0; j < n_fields; j++) {
371
372 col_no = dict_index_get_nth_col_no(index, j);
373
374 exp = opt_look_for_col_in_cond_before(
375 OPT_EQUAL, col_no,
376 static_cast<func_node_t*>(sel_node->search_cond),
377 sel_node, nth_table, &op);
378 if (exp) {
379 /* The value for this column is exactly known already
380 at this stage of the join */
381
382 index_plan[j] = exp;
383 *last_op = op;
384 goodness += 4;
385 } else {
386 /* Look for non-equality comparisons */
387
388 exp = opt_look_for_col_in_cond_before(
389 OPT_COMPARISON, col_no,
390 static_cast<func_node_t*>(
391 sel_node->search_cond),
392 sel_node, nth_table, &op);
393 if (exp) {
394 index_plan[j] = exp;
395 *last_op = op;
396 goodness += 2;
397 }
398
399 break;
400 }
401 }
402
403 if (goodness >= 4 * dict_index_get_n_unique(index)) {
404 goodness += 1024;
405
406 if (dict_index_is_clust(index)) {
407
408 goodness += 1024;
409 }
410 }
411
412 /* We have to test for goodness here, as last_op may not be set */
413 if (goodness && dict_index_is_clust(index)) {
414
415 goodness++;
416 }
417
418 return(goodness);
419 }
420
421 /*******************************************************************//**
422 Calculates the number of matched fields based on an index goodness.
423 @return number of excatly or partially matched fields */
424 UNIV_INLINE
425 ulint
opt_calc_n_fields_from_goodness(ulint goodness)426 opt_calc_n_fields_from_goodness(
427 /*============================*/
428 ulint goodness) /*!< in: goodness */
429 {
430 return(((goodness % 1024) + 2) / 4);
431 }
432
433 /*******************************************************************//**
434 Converts a comparison operator to the corresponding search mode PAGE_CUR_GE,
435 ...
436 @return search mode */
437 UNIV_INLINE
438 page_cur_mode_t
opt_op_to_search_mode(ibool asc,ulint op)439 opt_op_to_search_mode(
440 /*==================*/
441 ibool asc, /*!< in: TRUE if the rows should be fetched in an
442 ascending order */
443 ulint op) /*!< in: operator '=', PARS_GE_TOKEN, ... */
444 {
445 if (op == '='
446 || op == PARS_LIKE_TOKEN_EXACT
447 || op == PARS_LIKE_TOKEN_PREFIX
448 || op == PARS_LIKE_TOKEN_SUFFIX
449 || op == PARS_LIKE_TOKEN_SUBSTR) {
450
451 if (asc) {
452 return(PAGE_CUR_GE);
453 } else {
454 return(PAGE_CUR_LE);
455 }
456 } else if (op == '<') {
457 ut_a(!asc);
458 return(PAGE_CUR_L);
459 } else if (op == '>') {
460 ut_a(asc);
461 return(PAGE_CUR_G);
462 } else if (op == PARS_GE_TOKEN) {
463 ut_a(asc);
464 return(PAGE_CUR_GE);
465 } else if (op == PARS_LE_TOKEN) {
466 ut_a(!asc);
467 return(PAGE_CUR_LE);
468 } else {
469 ut_error;
470 }
471
472 return(PAGE_CUR_UNSUPP);
473 }
474
475 /*******************************************************************//**
476 Determines if a node is an argument node of a function node.
477 @return TRUE if is an argument */
478 static
479 ibool
opt_is_arg(que_node_t * arg_node,func_node_t * func_node)480 opt_is_arg(
481 /*=======*/
482 que_node_t* arg_node, /*!< in: possible argument node */
483 func_node_t* func_node) /*!< in: function node */
484 {
485 que_node_t* arg;
486
487 arg = func_node->args;
488
489 while (arg) {
490 if (arg == arg_node) {
491
492 return(TRUE);
493 }
494
495 arg = que_node_get_next(arg);
496 }
497
498 return(FALSE);
499 }
500
501 /*******************************************************************//**
502 Decides if the fetching of rows should be made in a descending order, and
503 also checks that the chosen query plan produces a result which satisfies
504 the order-by. */
505 static
506 void
opt_check_order_by(sel_node_t * sel_node)507 opt_check_order_by(
508 /*===============*/
509 sel_node_t* sel_node) /*!< in: select node; asserts an error
510 if the plan does not agree with the
511 order-by */
512 {
513 order_node_t* order_node;
514 dict_table_t* order_table;
515 ulint order_col_no;
516 plan_t* plan;
517 ulint i;
518
519 if (!sel_node->order_by) {
520
521 return;
522 }
523
524 order_node = sel_node->order_by;
525 order_col_no = order_node->column->col_no;
526 order_table = order_node->column->table;
527
528 /* If there is an order-by clause, the first non-exactly matched field
529 in the index used for the last table in the table list should be the
530 column defined in the order-by clause, and for all the other tables
531 we should get only at most a single row, otherwise we cannot presently
532 calculate the order-by, as we have no sort utility */
533
534 for (i = 0; i < sel_node->n_tables; i++) {
535
536 plan = sel_node_get_nth_plan(sel_node, i);
537
538 if (i < sel_node->n_tables - 1) {
539 ut_a(dict_index_get_n_unique(plan->index)
540 <= plan->n_exact_match);
541 } else {
542 ut_a(plan->table == order_table);
543
544 ut_a((dict_index_get_n_unique(plan->index)
545 <= plan->n_exact_match)
546 || (dict_index_get_nth_col_no(plan->index,
547 plan->n_exact_match)
548 == order_col_no));
549 }
550 }
551 }
552
553 /*******************************************************************//**
554 Optimizes a select. Decides which indexes to tables to use. The tables
555 are accessed in the order that they were written to the FROM part in the
556 select statement. */
557 static
558 void
opt_search_plan_for_table(sel_node_t * sel_node,ulint i,dict_table_t * table)559 opt_search_plan_for_table(
560 /*======================*/
561 sel_node_t* sel_node, /*!< in: parsed select node */
562 ulint i, /*!< in: this is the ith table */
563 dict_table_t* table) /*!< in: table */
564 {
565 plan_t* plan;
566 dict_index_t* index;
567 dict_index_t* best_index;
568 ulint n_fields;
569 ulint goodness;
570 ulint last_op = 75946965; /* Eliminate a Purify
571 warning */
572 ulint best_goodness;
573 ulint best_last_op = 0; /* remove warning */
574 que_node_t* index_plan[256];
575 que_node_t* best_index_plan[256];
576
577 plan = sel_node_get_nth_plan(sel_node, i);
578
579 plan->table = table;
580 plan->asc = sel_node->asc;
581 plan->pcur_is_open = FALSE;
582 plan->cursor_at_end = FALSE;
583
584 /* Calculate goodness for each index of the table */
585
586 index = dict_table_get_first_index(table);
587 best_index = index; /* Eliminate compiler warning */
588 best_goodness = 0;
589
590 /* should be do ... until ? comment by Jani */
591 while (index) {
592 goodness = opt_calc_index_goodness(index, sel_node, i,
593 index_plan, &last_op);
594 if (goodness > best_goodness) {
595
596 best_index = index;
597 best_goodness = goodness;
598 n_fields = opt_calc_n_fields_from_goodness(goodness);
599
600 ut_memcpy(best_index_plan, index_plan,
601 n_fields * sizeof(void*));
602 best_last_op = last_op;
603 }
604
605 dict_table_next_uncorrupted_index(index);
606 }
607
608 plan->index = best_index;
609
610 n_fields = opt_calc_n_fields_from_goodness(best_goodness);
611
612 if (n_fields == 0) {
613 plan->tuple = NULL;
614 plan->n_exact_match = 0;
615 } else {
616 plan->tuple = dtuple_create(pars_sym_tab_global->heap,
617 n_fields);
618 dict_index_copy_types(plan->tuple, plan->index, n_fields);
619
620 plan->tuple_exps = static_cast<que_node_t**>(
621 mem_heap_alloc(
622 pars_sym_tab_global->heap,
623 n_fields * sizeof(void*)));
624
625 ut_memcpy(plan->tuple_exps, best_index_plan,
626 n_fields * sizeof(void*));
627 if (best_last_op == '='
628 || best_last_op == PARS_LIKE_TOKEN_EXACT
629 || best_last_op == PARS_LIKE_TOKEN_PREFIX
630 || best_last_op == PARS_LIKE_TOKEN_SUFFIX
631 || best_last_op == PARS_LIKE_TOKEN_SUBSTR) {
632 plan->n_exact_match = n_fields;
633 } else {
634 plan->n_exact_match = n_fields - 1;
635 }
636
637 plan->mode = opt_op_to_search_mode(sel_node->asc,
638 best_last_op);
639 }
640
641 if (dict_index_is_clust(best_index)
642 && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
643
644 plan->unique_search = TRUE;
645 } else {
646 plan->unique_search = FALSE;
647 }
648
649 plan->old_vers_heap = NULL;
650
651 btr_pcur_init(&(plan->pcur));
652 btr_pcur_init(&(plan->clust_pcur));
653 }
654
655 /*******************************************************************//**
656 Looks at a comparison condition and decides if it can, and need, be tested for
657 a table AFTER the table has been accessed.
658 @return OPT_NOT_COND if not for this table, else OPT_END_COND,
659 OPT_TEST_COND, or OPT_SCROLL_COND, where the last means that the
660 condition need not be tested, except when scroll cursors are used */
661 static
662 ulint
opt_classify_comparison(sel_node_t * sel_node,ulint i,func_node_t * cond)663 opt_classify_comparison(
664 /*====================*/
665 sel_node_t* sel_node, /*!< in: select node */
666 ulint i, /*!< in: ith table in the join */
667 func_node_t* cond) /*!< in: comparison condition */
668 {
669 plan_t* plan;
670 ulint n_fields;
671 ulint op;
672 ulint j;
673
674 ut_ad(cond && sel_node);
675
676 plan = sel_node_get_nth_plan(sel_node, i);
677
678 /* Check if the condition is determined after the ith table has been
679 accessed, but not after the i - 1:th */
680
681 if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
682
683 return(OPT_NOT_COND);
684 }
685
686 if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
687
688 return(OPT_NOT_COND);
689 }
690
691 /* If the condition is an exact match condition used in constructing
692 the search tuple, it is classified as OPT_END_COND */
693
694 if (plan->tuple) {
695 n_fields = dtuple_get_n_fields(plan->tuple);
696 } else {
697 n_fields = 0;
698 }
699
700 for (j = 0; j < plan->n_exact_match; j++) {
701
702 if (opt_is_arg(plan->tuple_exps[j], cond)) {
703
704 return(OPT_END_COND);
705 }
706 }
707
708 /* If the condition is an non-exact match condition used in
709 constructing the search tuple, it is classified as OPT_SCROLL_COND.
710 When the cursor is positioned, and if a non-scroll cursor is used,
711 there is no need to test this condition; if a scroll cursor is used
712 the testing is necessary when the cursor is reversed. */
713
714 if ((n_fields > plan->n_exact_match)
715 && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
716
717 return(OPT_SCROLL_COND);
718 }
719
720 /* If the condition is a non-exact match condition on the first field
721 in index for which there is no exact match, and it limits the search
722 range from the opposite side of the search tuple already BEFORE we
723 access the table, it is classified as OPT_END_COND */
724
725 if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
726 && opt_look_for_col_in_comparison_before(
727 OPT_COMPARISON,
728 dict_index_get_nth_col_no(plan->index,
729 plan->n_exact_match),
730 cond, sel_node, i, &op)) {
731
732 if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
733
734 return(OPT_END_COND);
735 }
736
737 if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
738
739 return(OPT_END_COND);
740 }
741 }
742
743 /* Otherwise, cond is classified as OPT_TEST_COND */
744
745 return(OPT_TEST_COND);
746 }
747
748 /*******************************************************************//**
749 Recursively looks for test conditions for a table in a join. */
750 static
751 void
opt_find_test_conds(sel_node_t * sel_node,ulint i,func_node_t * cond)752 opt_find_test_conds(
753 /*================*/
754 sel_node_t* sel_node, /*!< in: select node */
755 ulint i, /*!< in: ith table in the join */
756 func_node_t* cond) /*!< in: conjunction of search
757 conditions or NULL */
758 {
759 func_node_t* new_cond;
760 ulint fclass;
761 plan_t* plan;
762
763 if (cond == NULL) {
764
765 return;
766 }
767
768 if (cond->func == PARS_AND_TOKEN) {
769 new_cond = static_cast<func_node_t*>(cond->args);
770
771 opt_find_test_conds(sel_node, i, new_cond);
772
773 new_cond = static_cast<func_node_t*>(
774 que_node_get_next(new_cond));
775
776 opt_find_test_conds(sel_node, i, new_cond);
777
778 return;
779 }
780
781 plan = sel_node_get_nth_plan(sel_node, i);
782
783 fclass = opt_classify_comparison(sel_node, i, cond);
784
785 if (fclass == OPT_END_COND) {
786 UT_LIST_ADD_LAST(plan->end_conds, cond);
787
788 } else if (fclass == OPT_TEST_COND) {
789 UT_LIST_ADD_LAST(plan->other_conds, cond);
790
791 }
792 }
793
794 /*******************************************************************//**
795 Normalizes a list of comparison conditions so that a column of the table
796 appears on the left side of the comparison if possible. This is accomplished
797 by switching the arguments of the operator. */
798 static
799 void
opt_normalize_cmp_conds(func_node_t * cond,dict_table_t * table)800 opt_normalize_cmp_conds(
801 /*====================*/
802 func_node_t* cond, /*!< in: first in a list of comparison
803 conditions, or NULL */
804 dict_table_t* table) /*!< in: table */
805 {
806 que_node_t* arg1;
807 que_node_t* arg2;
808 sym_node_t* sym_node;
809
810 while (cond) {
811 arg1 = cond->args;
812 arg2 = que_node_get_next(arg1);
813
814 if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
815
816 sym_node = static_cast<sym_node_t*>(arg2);
817
818 if ((sym_node->token_type == SYM_COLUMN)
819 && (sym_node->table == table)) {
820
821 /* Switch the order of the arguments */
822
823 cond->args = arg2;
824 que_node_list_add_last(NULL, arg2);
825 que_node_list_add_last(arg2, arg1);
826
827 /* Invert the operator */
828 cond->func = opt_invert_cmp_op(cond->func);
829 }
830 }
831
832 cond = UT_LIST_GET_NEXT(cond_list, cond);
833 }
834 }
835
836 /*******************************************************************//**
837 Finds out the search condition conjuncts we can, and need, to test as the ith
838 table in a join is accessed. The search tuple can eliminate the need to test
839 some conjuncts. */
840 static
841 void
opt_determine_and_normalize_test_conds(sel_node_t * sel_node,ulint i)842 opt_determine_and_normalize_test_conds(
843 /*===================================*/
844 sel_node_t* sel_node, /*!< in: select node */
845 ulint i) /*!< in: ith table in the join */
846 {
847 plan_t* plan;
848
849 plan = sel_node_get_nth_plan(sel_node, i);
850
851 UT_LIST_INIT(plan->end_conds, &func_node_t::cond_list);
852 UT_LIST_INIT(plan->other_conds, &func_node_t::cond_list);
853
854 /* Recursively go through the conjuncts and classify them */
855
856 opt_find_test_conds(
857 sel_node,
858 i,
859 static_cast<func_node_t*>(sel_node->search_cond));
860
861 opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
862 plan->table);
863
864 ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
865 }
866
867 /*******************************************************************//**
868 Looks for occurrences of the columns of the table in the query subgraph and
869 adds them to the list of columns if an occurrence of the same column does not
870 already exist in the list. If the column is already in the list, puts a value
871 indirection to point to the occurrence in the column list, except if the
872 column occurrence we are looking at is in the column list, in which case
873 nothing is done. */
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_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, &sym_node_t::col_var_list);
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_is_sys_table(index->table->id)
1131 && (dict_index_get_nth_field(index, pos)->prefix_len != 0
1132 || dict_index_get_nth_field(clust_index, i)
1133 ->prefix_len != 0)) {
1134 ib::error() << "Error in pars0opt.cc: table "
1135 << index->table->name
1136 << " has prefix_len != 0";
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 void
opt_search_plan(sel_node_t * sel_node)1150 opt_search_plan(
1151 /*============*/
1152 sel_node_t* sel_node) /*!< in: parsed select node */
1153 {
1154 sym_node_t* table_node;
1155 dict_table_t* table;
1156 order_node_t* order_by;
1157 ulint i;
1158
1159 sel_node->plans = static_cast<plan_t*>(
1160 mem_heap_alloc(
1161 pars_sym_tab_global->heap,
1162 sel_node->n_tables * sizeof(plan_t)));
1163
1164 /* Analyze the search condition to find out what we know at each
1165 join stage about the conditions that the columns of a table should
1166 satisfy */
1167
1168 table_node = sel_node->table_list;
1169
1170 if (sel_node->order_by == NULL) {
1171 sel_node->asc = TRUE;
1172 } else {
1173 order_by = sel_node->order_by;
1174
1175 sel_node->asc = order_by->asc;
1176 }
1177
1178 for (i = 0; i < sel_node->n_tables; i++) {
1179
1180 table = table_node->table;
1181
1182 /* Choose index through which to access the table */
1183
1184 opt_search_plan_for_table(sel_node, i, table);
1185
1186 /* Determine the search condition conjuncts we can test at
1187 this table; normalize the end conditions */
1188
1189 opt_determine_and_normalize_test_conds(sel_node, i);
1190
1191 table_node = static_cast<sym_node_t*>(
1192 que_node_get_next(table_node));
1193 }
1194
1195 table_node = sel_node->table_list;
1196
1197 for (i = 0; i < sel_node->n_tables; i++) {
1198
1199 /* Classify the table columns into those we only need to access
1200 but not copy, and to those we must copy to dynamic memory */
1201
1202 opt_classify_cols(sel_node, i);
1203
1204 /* Calculate possible info for accessing the clustered index
1205 record */
1206
1207 opt_clust_access(sel_node, i);
1208
1209 table_node = static_cast<sym_node_t*>(
1210 que_node_get_next(table_node));
1211 }
1212
1213 /* Check that the plan obeys a possible order-by clause: if not,
1214 an assertion error occurs */
1215
1216 opt_check_order_by(sel_node);
1217
1218 #ifdef UNIV_SQL_DEBUG
1219 opt_print_query_plan(sel_node);
1220 #endif
1221 }
1222
1223 #if 1//def UNIV_SQL_DEBUG
1224 /********************************************************************//**
1225 Prints info of a query plan. */
1226 void
opt_print_query_plan(sel_node_t * sel_node)1227 opt_print_query_plan(
1228 /*=================*/
1229 sel_node_t* sel_node) /*!< in: select node */
1230 {
1231 plan_t* plan;
1232 ulint n_fields;
1233 ulint i;
1234
1235 fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);
1236
1237 fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
1238
1239 if (sel_node->set_x_locks) {
1240 fputs("sets row x-locks; ", stderr);
1241 ut_a(sel_node->row_lock_mode == LOCK_X);
1242 ut_a(!sel_node->consistent_read);
1243 } else if (sel_node->consistent_read) {
1244 fputs("consistent read; ", stderr);
1245 } else {
1246 ut_a(sel_node->row_lock_mode == LOCK_S);
1247 fputs("sets row s-locks; ", stderr);
1248 }
1249
1250 putc('\n', stderr);
1251
1252 for (i = 0; i < sel_node->n_tables; i++) {
1253 plan = sel_node_get_nth_plan(sel_node, i);
1254
1255 if (plan->tuple) {
1256 n_fields = dtuple_get_n_fields(plan->tuple);
1257 } else {
1258 n_fields = 0;
1259 }
1260
1261 fprintf(stderr,
1262 "Index %s of table %s"
1263 "; exact m. %lu, match %lu, end conds %lu\n",
1264 plan->index->name(), plan->index->table_name,
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 #endif /* UNIV_SQL_DEBUG */
1271