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