Drizzled Public API Documentation

pars0opt.cc
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., 51 Franklin
15 St, Fifth Floor, Boston, MA 02110-1301 USA
16 
17 *****************************************************************************/
18 
19 /**************************************************/
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 /*******************************************************************/
54 static
55 int
56 opt_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 {
71  ut_error;
72  }
73 
74  return(0);
75 }
76 
77 /*******************************************************************/
82 static
83 ibool
84 opt_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 /*******************************************************************/
141 static
142 que_node_t*
143 opt_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 /*******************************************************************/
238 static
239 que_node_t*
240 opt_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 /*******************************************************************/
316 static
317 ulint
318 opt_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 /*******************************************************************/
396 UNIV_INLINE
397 ulint
398 opt_calc_n_fields_from_goodness(
399 /*============================*/
400  ulint goodness)
401 {
402  return(((goodness % 1024) + 2) / 4);
403 }
404 
405 /*******************************************************************/
409 UNIV_INLINE
410 ulint
411 opt_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 /*******************************************************************/
445 static
446 ibool
447 opt_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 /*******************************************************************/
472 static
473 void
474 opt_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 /*******************************************************************/
524 static
525 void
526 opt_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 /*******************************************************************/
622 static
623 ulint
624 opt_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 /*******************************************************************/
711 static
712 void
713 opt_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 /*******************************************************************/
758 static
759 void
760 opt_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 /*******************************************************************/
800 static
801 void
802 opt_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);
812  UT_LIST_INIT(plan->other_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 
821  ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
822 }
823 
824 /*******************************************************************/
831 UNIV_INTERN
832 void
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 
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 /*******************************************************************/
938 static
939 void
940 opt_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 /*******************************************************************/
986 static
987 void
988 opt_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 /*******************************************************************/
1028 static
1029 void
1030 opt_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 /*******************************************************************/
1101 UNIV_INTERN
1102 void
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 /********************************************************************/
1174 UNIV_INTERN
1175 void
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 }
#define UT_LIST_GET_LEN(BASE)
Definition: ut0lst.h:217
ibool pcur_is_open
Definition: row0sel.h:210
plan_t * plans
Definition: row0sel.h:305
UNIV_INLINE ulint dict_index_get_nth_col_no(const dict_index_t *index, ulint pos)
#define UT_LIST_GET_NEXT(NAME, N)
Definition: ut0lst.h:201
ulint mode
Definition: row0sel.h:230
ibool copy_val
Definition: pars0sym.h:187
UNIV_INTERN ulint dict_index_get_nth_field_pos(const dict_index_t *index, const dict_index_t *index2, ulint n)
Definition: dict0dict.cc:585
#define SYM_SEC_FIELD_NO
Definition: pars0sym.h:134
enum sym_tab_entry token_type
Definition: pars0sym.h:208
UNIV_INLINE ulint dict_index_get_n_fields(const dict_index_t *index)
UNIV_INLINE que_node_t * que_node_list_add_last(que_node_t *node_list, que_node_t *node)
UNIV_INLINE plan_t * sel_node_get_nth_plan(sel_node_t *node, ulint i)
UNIV_INLINE dtuple_t * dtuple_create(mem_heap_t *heap, ulint n_fields)
sym_node_t * table_list
Definition: row0sel.h:295
#define SYM_CLUST_FIELD_NO
Definition: pars0sym.h:132
UNIV_INLINE void * ut_memcpy(void *dest, const void *sour, ulint n)
mem_heap_t * heap
Definition: pars0sym.h:255
UNIV_INTERN ulint dict_index_get_nth_col_pos(const dict_index_t *index, ulint n)
Definition: dict0dict.cc:502
que_node_t ** tuple_exps
Definition: row0sel.h:223
ibool unique_search
Definition: row0sel.h:234
UNIV_INTERN void dict_index_copy_types(dtuple_t *tuple, const dict_index_t *index, ulint n_fields)
Definition: dict0dict.cc:1932
ulint n_exact_match
Definition: row0sel.h:231
dict_index_t * index
Definition: row0sel.h:206
ibool consistent_read
Definition: row0sel.h:312
UNIV_INLINE ulint dtuple_get_n_fields(const dtuple_t *tuple)
ibool set_x_locks
Definition: row0sel.h:298
ibool no_prefetch
Definition: row0sel.h:243
UNIV_INLINE ulint dict_index_get_n_unique_in_tree(const dict_index_t *index)
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
order_node_t * order_by
Definition: row0sel.h:314
ibool must_get_clust
Definition: row0sel.h:258
UNIV_INLINE void btr_pcur_init(btr_pcur_t *pcur)
sym_node_t * column
Definition: pars0pars.h:662
dict_table_t * table
Definition: pars0sym.h:212
que_node_t * args
Definition: pars0pars.h:649
que_node_t * select_list
Definition: row0sel.h:293
UNIV_INLINE ulint dict_index_is_clust(const dict_index_t *index) __attribute__((pure))
btr_pcur_t clust_pcur
Definition: row0sel.h:272
dict_table_t * table
Definition: row0sel.h:204
#define ut_a(EXPR)
Definition: ut0dbg.h:105
btr_pcur_t pcur
Definition: row0sel.h:207
UNIV_INLINE void * mem_heap_alloc(mem_heap_t *heap, ulint n)
mem_heap_t * old_vers_heap
Definition: row0sel.h:275
dict_table_t * table
Definition: dict0mem.h:341
UNIV_INTERN void opt_search_plan(sel_node_t *sel_node)
Definition: pars0opt.cc:1103
UNIV_INTERN void opt_print_query_plan(sel_node_t *sel_node)
Definition: pars0opt.cc:1176
sym_node_list_t columns
Definition: row0sel.h:244
#define UT_LIST_ADD_LAST(NAME, BASE, N)
Definition: ut0lst.h:119
#define UT_LIST_GET_FIRST(BASE)
Definition: ut0lst.h:224
#define ut_ad(EXPR)
Definition: ut0dbg.h:127
sym_node_t * alias
Definition: pars0sym.h:178
#define UT_LIST_INIT(BASE)
Definition: ut0lst.h:84
#define ut_error
Definition: ut0dbg.h:115
ulint * clust_map
Definition: row0sel.h:266
UNIV_INLINE ulint dict_index_get_n_unique(const dict_index_t *index)
UNIV_INLINE ulint que_node_get_type(que_node_t *node)
const char * table_name
Definition: dict0mem.h:340
ulint n_tables
Definition: row0sel.h:302
dtuple_t * tuple
Definition: row0sel.h:229
ulint row_lock_mode
Definition: row0sel.h:301
ibool cursor_at_end
Definition: row0sel.h:212
dtuple_t * clust_ref
Definition: row0sel.h:269
ulint field_nos[2]
Definition: pars0sym.h:191
que_node_t * search_cond
Definition: row0sel.h:308
ibool asc
Definition: row0sel.h:209
UNIV_INTERN void dict_index_name_print(FILE *file, trx_t *trx, const dict_index_t *index)
Definition: dict0dict.cc:4775
UNIV_INLINE que_node_t * que_node_get_next(que_node_t *node)
sym_node_t * indirection
Definition: pars0sym.h:173