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