drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
pars0opt.cc
1/*****************************************************************************
2
3Copyright (C) 1997, 2009, Innobase Oy. All Rights Reserved.
4
5This program is free software; you can redistribute it and/or modify it under
6the terms of the GNU General Public License as published by the Free Software
7Foundation; version 2 of the License.
8
9This program is distributed in the hope that it will be useful, but WITHOUT
10ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
11FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
12
13You should have received a copy of the GNU General Public License along with
14this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
15St, Fifth Floor, Boston, MA 02110-1301 USA
16
17*****************************************************************************/
18
19/**************************************************/
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.hh"
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/*******************************************************************/
54static
55int
56opt_invert_cmp_op(
57/*==============*/
58 int op)
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 {
72 }
73
74 return(0);
75}
76
77/*******************************************************************/
82static
83ibool
84opt_check_exp_determined_before(
85/*============================*/
86 que_node_t* exp,
87 sel_node_t* sel_node,
88 ulint nth_table)
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 = static_cast<func_node_t *>(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 = static_cast<sym_node_t *>(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/*******************************************************************/
141static
142que_node_t*
143opt_look_for_col_in_comparison_before(
144/*==================================*/
145 ulint cmp_type,
146 ulint col_no,
147 func_node_t* search_cond,
148 sel_node_t* sel_node,
149 ulint nth_table,
152 ulint* op)
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 = static_cast<sym_node_t *>(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 = static_cast<sym_node_t *>(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/*******************************************************************/
238static
239que_node_t*
240opt_look_for_col_in_cond_before(
241/*============================*/
242 ulint cmp_type,
243 ulint col_no,
244 func_node_t* search_cond,
245 sel_node_t* sel_node,
246 ulint nth_table,
249 ulint* op)
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 = static_cast<func_node_t *>(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 = static_cast<func_node_t *>(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/*******************************************************************/
316static
317ulint
318opt_calc_index_goodness(
319/*====================*/
320 dict_index_t* index,
321 sel_node_t* sel_node,
322 ulint nth_table,
323 que_node_t** index_plan,
325 ulint* last_op)
327{
328 que_node_t* exp;
329 ulint goodness;
330 ulint n_fields;
331 ulint col_no;
332 ulint op= 0;
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,
350 static_cast<func_node_t *>(sel_node->search_cond),
351 sel_node, nth_table, &op);
352 if (exp) {
353 /* The value for this column is exactly known already
354 at this stage of the join */
355
356 index_plan[j] = exp;
357 *last_op = op;
358 goodness += 4;
359 } else {
360 /* Look for non-equality comparisons */
361
362 exp = opt_look_for_col_in_cond_before(
363 OPT_COMPARISON, col_no, static_cast<func_node_t *>(sel_node->search_cond),
364 sel_node, nth_table, &op);
365 if (exp) {
366 index_plan[j] = exp;
367 *last_op = op;
368 goodness += 2;
369 }
370
371 break;
372 }
373 }
374
375 if (goodness >= 4 * dict_index_get_n_unique(index)) {
376 goodness += 1024;
377
378 if (dict_index_is_clust(index)) {
379
380 goodness += 1024;
381 }
382 }
383
384 /* We have to test for goodness here, as last_op may note be set */
385 if (goodness && dict_index_is_clust(index)) {
386
387 goodness++;
388 }
389
390 return(goodness);
391}
392
393/*******************************************************************/
396UNIV_INLINE
397ulint
398opt_calc_n_fields_from_goodness(
399/*============================*/
400 ulint goodness)
401{
402 return(((goodness % 1024) + 2) / 4);
403}
404
405/*******************************************************************/
409UNIV_INLINE
410ulint
411opt_op_to_search_mode(
412/*==================*/
413 ibool asc,
415 ulint op)
416{
417 if (op == '=') {
418 if (asc) {
419 return(PAGE_CUR_GE);
420 } else {
421 return(PAGE_CUR_LE);
422 }
423 } else if (op == '<') {
424 ut_a(!asc);
425 return(PAGE_CUR_L);
426 } else if (op == '>') {
427 ut_a(asc);
428 return(PAGE_CUR_G);
429 } else if (op == PARS_GE_TOKEN) {
430 ut_a(asc);
431 return(PAGE_CUR_GE);
432 } else if (op == PARS_LE_TOKEN) {
433 ut_a(!asc);
434 return(PAGE_CUR_LE);
435 } else {
436 ut_error;
437 }
438
439 return(0);
440}
441
442/*******************************************************************/
445static
446ibool
447opt_is_arg(
448/*=======*/
449 que_node_t* arg_node,
450 func_node_t* func_node)
451{
452 que_node_t* arg;
453
454 arg = func_node->args;
455
456 while (arg) {
457 if (arg == arg_node) {
458
459 return(TRUE);
460 }
461
462 arg = que_node_get_next(arg);
463 }
464
465 return(FALSE);
466}
467
468/*******************************************************************/
472static
473void
474opt_check_order_by(
475/*===============*/
476 sel_node_t* sel_node)
479{
480 order_node_t* order_node;
481 dict_table_t* order_table;
482 ulint order_col_no;
483 plan_t* plan;
484 ulint i;
485
486 if (!sel_node->order_by) {
487
488 return;
489 }
490
491 order_node = sel_node->order_by;
492 order_col_no = order_node->column->col_no;
493 order_table = order_node->column->table;
494
495 /* If there is an order-by clause, the first non-exactly matched field
496 in the index used for the last table in the table list should be the
497 column defined in the order-by clause, and for all the other tables
498 we should get only at most a single row, otherwise we cannot presently
499 calculate the order-by, as we have no sort utility */
500
501 for (i = 0; i < sel_node->n_tables; i++) {
502
503 plan = sel_node_get_nth_plan(sel_node, i);
504
505 if (i < sel_node->n_tables - 1) {
507 <= plan->n_exact_match);
508 } else {
509 ut_a(plan->table == order_table);
510
512 <= plan->n_exact_match)
514 plan->n_exact_match)
515 == order_col_no));
516 }
517 }
518}
519
520/*******************************************************************/
524static
525void
526opt_search_plan_for_table(
527/*======================*/
528 sel_node_t* sel_node,
529 ulint i,
530 dict_table_t* table)
531{
532 plan_t* plan;
533 dict_index_t* index;
534 dict_index_t* best_index;
535 ulint n_fields;
536 ulint goodness;
537 ulint last_op = 75946965; /* Eliminate a Purify
538 warning */
539 ulint best_goodness;
540 ulint best_last_op = 0; /* remove warning */
541 que_node_t* index_plan[256];
542 que_node_t* best_index_plan[256];
543
544 plan = sel_node_get_nth_plan(sel_node, i);
545
546 plan->table = table;
547 plan->asc = sel_node->asc;
548 plan->pcur_is_open = FALSE;
549 plan->cursor_at_end = FALSE;
550
551 /* Calculate goodness for each index of the table */
552
553 index = dict_table_get_first_index(table);
554 best_index = index; /* Eliminate compiler warning */
555 best_goodness = 0;
556
557 /* should be do ... until ? comment by Jani */
558 while (index) {
559 goodness = opt_calc_index_goodness(index, sel_node, i,
560 index_plan, &last_op);
561 if (goodness > best_goodness) {
562
563 best_index = index;
564 best_goodness = goodness;
565 n_fields = opt_calc_n_fields_from_goodness(goodness);
566
567 ut_memcpy(best_index_plan, index_plan,
568 n_fields * sizeof(void*));
569 best_last_op = last_op;
570 }
571
572 index = dict_table_get_next_index(index);
573 }
574
575 plan->index = best_index;
576
577 n_fields = opt_calc_n_fields_from_goodness(best_goodness);
578
579 if (n_fields == 0) {
580 plan->tuple = NULL;
581 plan->n_exact_match = 0;
582 } else {
583 plan->tuple = dtuple_create(pars_sym_tab_global->heap,
584 n_fields);
585 dict_index_copy_types(plan->tuple, plan->index, n_fields);
586
587 plan->tuple_exps = static_cast<void **>(mem_heap_alloc(pars_sym_tab_global->heap,
588 n_fields * sizeof(void*)));
589
590 ut_memcpy(plan->tuple_exps, best_index_plan,
591 n_fields * sizeof(void*));
592 if (best_last_op == '=') {
593 plan->n_exact_match = n_fields;
594 } else {
595 plan->n_exact_match = n_fields - 1;
596 }
597
598 plan->mode = opt_op_to_search_mode(sel_node->asc,
599 best_last_op);
600 }
601
602 if (dict_index_is_clust(best_index)
603 && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
604
605 plan->unique_search = TRUE;
606 } else {
607 plan->unique_search = FALSE;
608 }
609
610 plan->old_vers_heap = NULL;
611
612 btr_pcur_init(&(plan->pcur));
613 btr_pcur_init(&(plan->clust_pcur));
614}
615
616/*******************************************************************/
622static
623ulint
624opt_classify_comparison(
625/*====================*/
626 sel_node_t* sel_node,
627 ulint i,
628 func_node_t* cond)
629{
630 plan_t* plan;
631 ulint n_fields;
632 ulint op;
633 ulint j;
634
635 ut_ad(cond && sel_node);
636
637 plan = sel_node_get_nth_plan(sel_node, i);
638
639 /* Check if the condition is determined after the ith table has been
640 accessed, but not after the i - 1:th */
641
642 if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
643
644 return(OPT_NOT_COND);
645 }
646
647 if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
648
649 return(OPT_NOT_COND);
650 }
651
652 /* If the condition is an exact match condition used in constructing
653 the search tuple, it is classified as OPT_END_COND */
654
655 if (plan->tuple) {
656 n_fields = dtuple_get_n_fields(plan->tuple);
657 } else {
658 n_fields = 0;
659 }
660
661 for (j = 0; j < plan->n_exact_match; j++) {
662
663 if (opt_is_arg(plan->tuple_exps[j], cond)) {
664
665 return(OPT_END_COND);
666 }
667 }
668
669 /* If the condition is an non-exact match condition used in
670 constructing the search tuple, it is classified as OPT_SCROLL_COND.
671 When the cursor is positioned, and if a non-scroll cursor is used,
672 there is no need to test this condition; if a scroll cursor is used
673 the testing is necessary when the cursor is reversed. */
674
675 if ((n_fields > plan->n_exact_match)
676 && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
677
678 return(OPT_SCROLL_COND);
679 }
680
681 /* If the condition is a non-exact match condition on the first field
682 in index for which there is no exact match, and it limits the search
683 range from the opposite side of the search tuple already BEFORE we
684 access the table, it is classified as OPT_END_COND */
685
686 if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
687 && opt_look_for_col_in_comparison_before(
688 OPT_COMPARISON,
690 plan->n_exact_match),
691 cond, sel_node, i, &op)) {
692
693 if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
694
695 return(OPT_END_COND);
696 }
697
698 if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
699
700 return(OPT_END_COND);
701 }
702 }
703
704 /* Otherwise, cond is classified as OPT_TEST_COND */
705
706 return(OPT_TEST_COND);
707}
708
709/*******************************************************************/
711static
712void
713opt_find_test_conds(
714/*================*/
715 sel_node_t* sel_node,
716 ulint i,
717 func_node_t* cond)
719{
720 func_node_t* new_cond;
721 ulint func_class;
722 plan_t* plan;
723
724 if (cond == NULL) {
725
726 return;
727 }
728
729 if (cond->func == PARS_AND_TOKEN) {
730 new_cond = static_cast<func_node_t *>(cond->args);
731
732 opt_find_test_conds(sel_node, i, new_cond);
733
734 new_cond = static_cast<func_node_t *>(que_node_get_next(new_cond));
735
736 opt_find_test_conds(sel_node, i, new_cond);
737
738 return;
739 }
740
741 plan = sel_node_get_nth_plan(sel_node, i);
742
743 func_class = opt_classify_comparison(sel_node, i, cond);
744
745 if (func_class == OPT_END_COND) {
746 UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond);
747
748 } else if (func_class == OPT_TEST_COND) {
749 UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond);
750
751 }
752}
753
754/*******************************************************************/
758static
759void
760opt_normalize_cmp_conds(
761/*====================*/
762 func_node_t* cond,
764 dict_table_t* table)
765{
766 que_node_t* arg1;
767 que_node_t* arg2;
768 sym_node_t* sym_node;
769
770 while (cond) {
771 arg1 = cond->args;
772 arg2 = que_node_get_next(arg1);
773
774 if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
775
776 sym_node = static_cast<sym_node_t *>(arg2);
777
778 if ((sym_node->token_type == SYM_COLUMN)
779 && (sym_node->table == table)) {
780
781 /* Switch the order of the arguments */
782
783 cond->args = arg2;
784 que_node_list_add_last(NULL, arg2);
785 que_node_list_add_last(arg2, arg1);
786
787 /* Invert the operator */
788 cond->func = opt_invert_cmp_op(cond->func);
789 }
790 }
791
792 cond = UT_LIST_GET_NEXT(cond_list, cond);
793 }
794}
795
796/*******************************************************************/
800static
801void
802opt_determine_and_normalize_test_conds(
803/*===================================*/
804 sel_node_t* sel_node,
805 ulint i)
806{
807 plan_t* plan;
808
809 plan = sel_node_get_nth_plan(sel_node, i);
810
811 UT_LIST_INIT(plan->end_conds);
813
814 /* Recursively go through the conjuncts and classify them */
815
816 opt_find_test_conds(sel_node, i, static_cast<func_node_t *>(sel_node->search_cond));
817
818 opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
819 plan->table);
820
822}
823
824/*******************************************************************/
831UNIV_INTERN
832void
834/*==============*/
835 ibool copy_val,
837 dict_index_t* index,
838 sym_node_list_t* col_list,
840 plan_t* plan,
841 que_node_t* exp)
843{
844 func_node_t* func_node;
845 que_node_t* arg;
846 sym_node_t* sym_node;
847 sym_node_t* col_node;
848 ulint col_pos;
849
850 if (exp == NULL) {
851
852 return;
853 }
854
855 if (que_node_get_type(exp) == QUE_NODE_FUNC) {
856 func_node = static_cast<func_node_t *>(exp);
857
858 arg = func_node->args;
859
860 while (arg) {
861 opt_find_all_cols(copy_val, index, col_list, plan,
862 arg);
863 arg = que_node_get_next(arg);
864 }
865
866 return;
867 }
868
869 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
870
871 sym_node = static_cast<sym_node_t *>(exp);
872
873 if (sym_node->token_type != SYM_COLUMN) {
874
875 return;
876 }
877
878 if (sym_node->table != index->table) {
879
880 return;
881 }
882
883 /* Look for an occurrence of the same column in the plan column
884 list */
885
886 col_node = UT_LIST_GET_FIRST(*col_list);
887
888 while (col_node) {
889 if (col_node->col_no == sym_node->col_no) {
890
891 if (col_node == sym_node) {
892 /* sym_node was already in a list: do
893 nothing */
894
895 return;
896 }
897
898 /* Put an indirection */
899 sym_node->indirection = col_node;
900 sym_node->alias = col_node;
901
902 return;
903 }
904
905 col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
906 }
907
908 /* The same column did not occur in the list: add it */
909
910 UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node);
911
912 sym_node->copy_val = copy_val;
913
914 /* Fill in the field_no fields in sym_node */
915
916 sym_node->field_nos[SYM_CLUST_FIELD_NO] = dict_index_get_nth_col_pos(
917 dict_table_get_first_index(index->table), sym_node->col_no);
918 if (!dict_index_is_clust(index)) {
919
920 ut_a(plan);
921
922 col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no);
923
924 if (col_pos == ULINT_UNDEFINED) {
925
926 plan->must_get_clust = TRUE;
927 }
928
929 sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
930 }
931}
932
933/*******************************************************************/
938static
939void
940opt_find_copy_cols(
941/*===============*/
942 sel_node_t* sel_node,
943 ulint i,
944 func_node_t* search_cond)
945{
946 func_node_t* new_cond;
947 plan_t* plan;
948
949 if (search_cond == NULL) {
950
951 return;
952 }
953
954 ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);
955
956 if (search_cond->func == PARS_AND_TOKEN) {
957 new_cond = static_cast<func_node_t *>(search_cond->args);
958
959 opt_find_copy_cols(sel_node, i, new_cond);
960
961 new_cond = static_cast<func_node_t *>(que_node_get_next(new_cond));
962
963 opt_find_copy_cols(sel_node, i, new_cond);
964
965 return;
966 }
967
968 if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {
969
970 /* Any ith table columns occurring in search_cond should be
971 copied, as this condition cannot be tested already on the
972 fetch from the ith table */
973
974 plan = sel_node_get_nth_plan(sel_node, i);
975
976 opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
977 search_cond);
978 }
979}
980
981/*******************************************************************/
986static
987void
988opt_classify_cols(
989/*==============*/
990 sel_node_t* sel_node,
991 ulint i)
992{
993 plan_t* plan;
994 que_node_t* exp;
995
996 plan = sel_node_get_nth_plan(sel_node, i);
997
998 /* The final value of the following field will depend on the
999 environment of the select statement: */
1000
1001 plan->must_get_clust = FALSE;
1002
1003 UT_LIST_INIT(plan->columns);
1004
1005 /* All select list columns should be copied: therefore TRUE as the
1006 first argument */
1007
1008 exp = sel_node->select_list;
1009
1010 while (exp) {
1011 opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
1012 exp);
1013 exp = que_node_get_next(exp);
1014 }
1015
1016 opt_find_copy_cols(sel_node, i, static_cast<func_node_t *>(sel_node->search_cond));
1017
1018 /* All remaining columns in the search condition are temporary
1019 columns: therefore FALSE */
1020
1021 opt_find_all_cols(FALSE, plan->index, &(plan->columns), plan,
1022 sel_node->search_cond);
1023}
1024
1025/*******************************************************************/
1028static
1029void
1030opt_clust_access(
1031/*=============*/
1032 sel_node_t* sel_node,
1033 ulint n)
1034{
1035 plan_t* plan;
1036 dict_table_t* table;
1037 dict_index_t* clust_index;
1038 dict_index_t* index;
1039 mem_heap_t* heap;
1040 ulint n_fields;
1041 ulint pos;
1042 ulint i;
1043
1044 plan = sel_node_get_nth_plan(sel_node, n);
1045
1046 index = plan->index;
1047
1048 /* The final value of the following field depends on the environment
1049 of the select statement: */
1050
1051 plan->no_prefetch = FALSE;
1052
1053 if (dict_index_is_clust(index)) {
1054 plan->clust_map = NULL;
1055 plan->clust_ref = NULL;
1056
1057 return;
1058 }
1059
1060 table = index->table;
1061
1062 clust_index = dict_table_get_first_index(table);
1063
1064 n_fields = dict_index_get_n_unique(clust_index);
1065
1066 heap = pars_sym_tab_global->heap;
1067
1068 plan->clust_ref = dtuple_create(heap, n_fields);
1069
1070 dict_index_copy_types(plan->clust_ref, clust_index, n_fields);
1071
1072 plan->clust_map = static_cast<unsigned long *>(mem_heap_alloc(heap, n_fields * sizeof(ulint)));
1073
1074 for (i = 0; i < n_fields; i++) {
1075 pos = dict_index_get_nth_field_pos(index, clust_index, i);
1076
1077 ut_a(pos != ULINT_UNDEFINED);
1078
1079 /* We optimize here only queries to InnoDB's internal system
1080 tables, and they should not contain column prefix indexes. */
1081
1082 if (dict_index_get_nth_field(index, pos)->prefix_len != 0
1083 || dict_index_get_nth_field(clust_index, i)
1084 ->prefix_len != 0) {
1085 fprintf(stderr,
1086 "InnoDB: Error in pars0opt.c:"
1087 " table %s has prefix_len != 0\n",
1088 index->table_name);
1089 }
1090
1091 *(plan->clust_map + i) = pos;
1092
1093 ut_ad(pos != ULINT_UNDEFINED);
1094 }
1095}
1096
1097/*******************************************************************/
1101UNIV_INTERN
1102void
1104/*============*/
1105 sel_node_t* sel_node)
1106{
1107 sym_node_t* table_node;
1108 dict_table_t* table;
1109 order_node_t* order_by;
1110 ulint i;
1111
1112 sel_node->plans = static_cast<plan_t *>(mem_heap_alloc(pars_sym_tab_global->heap,
1113 sel_node->n_tables * sizeof(plan_t)));
1114
1115 /* Analyze the search condition to find out what we know at each
1116 join stage about the conditions that the columns of a table should
1117 satisfy */
1118
1119 table_node = sel_node->table_list;
1120
1121 if (sel_node->order_by == NULL) {
1122 sel_node->asc = TRUE;
1123 } else {
1124 order_by = sel_node->order_by;
1125
1126 sel_node->asc = order_by->asc;
1127 }
1128
1129 for (i = 0; i < sel_node->n_tables; i++) {
1130
1131 table = table_node->table;
1132
1133 /* Choose index through which to access the table */
1134
1135 opt_search_plan_for_table(sel_node, i, table);
1136
1137 /* Determine the search condition conjuncts we can test at
1138 this table; normalize the end conditions */
1139
1140 opt_determine_and_normalize_test_conds(sel_node, i);
1141
1142 table_node = static_cast<sym_node_t *>(que_node_get_next(table_node));
1143 }
1144
1145 table_node = sel_node->table_list;
1146
1147 for (i = 0; i < sel_node->n_tables; i++) {
1148
1149 /* Classify the table columns into those we only need to access
1150 but not copy, and to those we must copy to dynamic memory */
1151
1152 opt_classify_cols(sel_node, i);
1153
1154 /* Calculate possible info for accessing the clustered index
1155 record */
1156
1157 opt_clust_access(sel_node, i);
1158
1159 table_node = static_cast<sym_node_t *>(que_node_get_next(table_node));
1160 }
1161
1162 /* Check that the plan obeys a possible order-by clause: if not,
1163 an assertion error occurs */
1164
1165 opt_check_order_by(sel_node);
1166
1167#ifdef UNIV_SQL_DEBUG
1168 opt_print_query_plan(sel_node);
1169#endif
1170}
1171
1172/********************************************************************/
1174UNIV_INTERN
1175void
1177/*=================*/
1178 sel_node_t* sel_node)
1179{
1180 plan_t* plan;
1181 ulint n_fields;
1182 ulint i;
1183
1184 fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);
1185
1186 fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
1187
1188 if (sel_node->set_x_locks) {
1189 fputs("sets row x-locks; ", stderr);
1190 ut_a(sel_node->row_lock_mode == LOCK_X);
1191 ut_a(!sel_node->consistent_read);
1192 } else if (sel_node->consistent_read) {
1193 fputs("consistent read; ", stderr);
1194 } else {
1195 ut_a(sel_node->row_lock_mode == LOCK_S);
1196 fputs("sets row s-locks; ", stderr);
1197 }
1198
1199 putc('\n', stderr);
1200
1201 for (i = 0; i < sel_node->n_tables; i++) {
1202 plan = sel_node_get_nth_plan(sel_node, i);
1203
1204 if (plan->tuple) {
1205 n_fields = dtuple_get_n_fields(plan->tuple);
1206 } else {
1207 n_fields = 0;
1208 }
1209
1210 fputs("Table ", stderr);
1211 dict_index_name_print(stderr, NULL, plan->index);
1212 fprintf(stderr,"; exact m. %lu, match %lu, end conds %lu\n",
1213 (unsigned long) plan->n_exact_match,
1214 (unsigned long) n_fields,
1215 (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
1216 }
1217}
UNIV_INLINE void btr_pcur_init(btr_pcur_t *pcur)
UNIV_INLINE dtuple_t * dtuple_create(mem_heap_t *heap, ulint n_fields)
UNIV_INLINE ulint dtuple_get_n_fields(const dtuple_t *tuple)
UNIV_INLINE ulint dict_index_get_nth_col_no(const dict_index_t *index, ulint pos)
UNIV_INLINE ulint dict_index_get_n_unique(const dict_index_t *index)
UNIV_INLINE ulint dict_index_is_clust(const dict_index_t *index) __attribute__((pure))
UNIV_INLINE ulint dict_index_get_n_fields(const dict_index_t *index)
UNIV_INLINE ulint dict_index_get_n_unique_in_tree(const dict_index_t *index)
UNIV_INLINE void * mem_heap_alloc(mem_heap_t *heap, ulint n)
UNIV_INTERN void opt_print_query_plan(sel_node_t *sel_node)
Definition pars0opt.cc:1176
UNIV_INTERN void opt_search_plan(sel_node_t *sel_node)
Definition pars0opt.cc:1103
UNIV_INTERN 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)
Definition pars0opt.cc:833
@ SYM_COLUMN
Definition pars0sym.h:144
#define SYM_CLUST_FIELD_NO
Definition pars0sym.h:132
#define SYM_SEC_FIELD_NO
Definition pars0sym.h:134
UNIV_INLINE ulint que_node_get_type(que_node_t *node)
UNIV_INLINE que_node_t * que_node_list_add_last(que_node_t *node_list, que_node_t *node)
UNIV_INLINE que_node_t * que_node_get_next(que_node_t *node)
UNIV_INLINE plan_t * sel_node_get_nth_plan(sel_node_t *node, ulint i)
que_node_t * args
Definition pars0pars.h:646
sym_node_t * column
Definition pars0pars.h:659
que_node_t ** tuple_exps
Definition row0sel.h:223
sym_node_list_t columns
Definition row0sel.h:244
ibool unique_search
Definition row0sel.h:234
ibool pcur_is_open
Definition row0sel.h:210
ibool cursor_at_end
Definition row0sel.h:212
ulint * clust_map
Definition row0sel.h:266
ibool must_get_clust
Definition row0sel.h:258
ulint n_exact_match
Definition row0sel.h:231
btr_pcur_t clust_pcur
Definition row0sel.h:272
mem_heap_t * old_vers_heap
Definition row0sel.h:275
dtuple_t * tuple
Definition row0sel.h:229
btr_pcur_t pcur
Definition row0sel.h:207
ulint mode
Definition row0sel.h:230
dict_table_t * table
Definition row0sel.h:204
dtuple_t * clust_ref
Definition row0sel.h:269
ibool no_prefetch
Definition row0sel.h:243
ibool asc
Definition row0sel.h:209
dict_index_t * index
Definition row0sel.h:206
sym_node_t * table_list
Definition row0sel.h:295
ibool set_x_locks
Definition row0sel.h:298
que_node_t * select_list
Definition row0sel.h:293
ulint row_lock_mode
Definition row0sel.h:301
que_node_t * search_cond
Definition row0sel.h:308
ibool consistent_read
Definition row0sel.h:312
order_node_t * order_by
Definition row0sel.h:314
plan_t * plans
Definition row0sel.h:305
sym_node_t * alias
Definition pars0sym.h:178
enum sym_tab_entry token_type
Definition pars0sym.h:208
ulint field_nos[2]
Definition pars0sym.h:191
dict_table_t * table
Definition pars0sym.h:212
sym_node_t * indirection
Definition pars0sym.h:173
#define ut_error
Definition ut0dbg.h:115
#define ut_ad(EXPR)
Definition ut0dbg.h:127
#define ut_a(EXPR)
Definition ut0dbg.h:105
#define UT_LIST_GET_LEN(BASE)
Definition ut0lst.h:216
#define UT_LIST_GET_FIRST(BASE)
Definition ut0lst.h:223
#define UT_LIST_ADD_LAST(NAME, BASE, N)
Definition ut0lst.h:118
#define UT_LIST_GET_NEXT(NAME, N)
Definition ut0lst.h:200
#define UT_LIST_INIT(BASE)
Definition ut0lst.h:83
UNIV_INLINE void * ut_memcpy(void *dest, const void *sour, ulint n)