The world's most popular open source database
mysql/src/5.1-dbg/storage/innobase/pars/pars0opt.c File Reference
#include "pars0opt.h"#include "row0sel.h"#include "row0ins.h"#include "row0upd.h"#include "dict0dict.h"#include "dict0mem.h"#include "que0que.h"#include "pars0grm.h"#include "pars0pars.h"#include "lock0lock.h"Include dependency graph for pars0opt.c:
Go to the source code of this file.
Define Documentation
| #define OPT_COMPARISON 2 |
Definition at line 26 of file pars0opt.c.
Referenced by opt_calc_index_goodness(), and opt_look_for_col_in_comparison_before().
| #define OPT_END_COND 2 |
Definition at line 29 of file pars0opt.c.
Referenced by opt_classify_comparison(), and opt_find_test_conds().
| #define OPT_EQUAL 1 |
Definition at line 25 of file pars0opt.c.
Referenced by opt_calc_index_goodness(), and opt_look_for_col_in_comparison_before().
| #define OPT_NOT_COND 1 |
| #define OPT_SCROLL_COND 4 |
Definition at line 31 of file pars0opt.c.
| #define OPT_TEST_COND 3 |
Function Documentation
| static ulint opt_calc_index_goodness | ( | dict_index_t * | index, | |
| sel_node_t * | sel_node, | |||
| ulint | nth_table, | |||
| que_node_t ** | index_plan, | |||
| ulint * | last_op | |||
| ) | [static] |
Definition at line 301 of file pars0opt.c.
References DICT_CLUSTERED, dict_index_get_n_unique(), dict_index_get_n_unique_in_tree(), dict_index_get_nth_col_no(), index(), OPT_COMPARISON, OPT_EQUAL, opt_look_for_col_in_cond_before(), and sel_node_struct::search_cond.
Referenced by opt_search_plan_for_table().
00303 : goodness */ 00304 dict_index_t* index, /* in: index */ 00305 sel_node_t* sel_node, /* in: parsed select node */ 00306 ulint nth_table, /* in: nth table in a join */ 00307 que_node_t** index_plan, /* in/out: comparison expressions for 00308 this index */ 00309 ulint* last_op) /* out: last comparison operator, if 00310 goodness > 1 */ 00311 { 00312 que_node_t* exp; 00313 ulint goodness; 00314 ulint n_fields; 00315 ulint col_no; 00316 ulint op; 00317 ulint j; 00318 00319 goodness = 0; 00320 00321 /* Note that as higher level node pointers in the B-tree contain 00322 page addresses as the last field, we must not put more fields in 00323 the search tuple than dict_index_get_n_unique_in_tree(index); see 00324 the note in btr_cur_search_to_nth_level. */ 00325 00326 n_fields = dict_index_get_n_unique_in_tree(index); 00327 00328 for (j = 0; j < n_fields; j++) { 00329 00330 col_no = dict_index_get_nth_col_no(index, j); 00331 00332 exp = opt_look_for_col_in_cond_before(OPT_EQUAL, col_no, 00333 sel_node->search_cond, 00334 sel_node, nth_table, &op); 00335 if (exp) { 00336 /* The value for this column is exactly known already 00337 at this stage of the join */ 00338 00339 index_plan[j] = exp; 00340 *last_op = op; 00341 goodness += 4; 00342 } else { 00343 /* Look for non-equality comparisons */ 00344 00345 exp = opt_look_for_col_in_cond_before(OPT_COMPARISON, 00346 col_no, sel_node->search_cond, 00347 sel_node, nth_table, &op); 00348 if (exp) { 00349 index_plan[j] = exp; 00350 *last_op = op; 00351 goodness += 2; 00352 } 00353 00354 break; 00355 } 00356 } 00357 00358 if (goodness >= 4 * dict_index_get_n_unique(index)) { 00359 goodness += 1024; 00360 00361 if (index->type & DICT_CLUSTERED) { 00362 00363 goodness += 1024; 00364 } 00365 } 00366 00367 /* We have to test for goodness here, as last_op may note be set */ 00368 if (goodness && index->type & DICT_CLUSTERED) { 00369 00370 goodness++; 00371 } 00372 00373 return(goodness); 00374 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 380 of file pars0opt.c.
Referenced by opt_search_plan_for_table().
00382 : number of excatly or partially matched 00383 fields */ 00384 ulint goodness) /* in: goodness */ 00385 { 00386 return(((goodness % 1024) + 2) / 4); 00387 }
Here is the caller graph for this function:
| static ibool opt_check_exp_determined_before | ( | que_node_t * | exp, | |
| sel_node_t * | sel_node, | |||
| ulint | nth_table | |||
| ) | [static] |
Definition at line 67 of file pars0opt.c.
References func_node_struct::args, FALSE, QUE_NODE_FUNC, que_node_get_next(), que_node_get_type(), QUE_NODE_SYMBOL, sel_node_get_nth_plan(), SYM_COLUMN, sym_node_struct::table, sym_node_struct::token_type, TRUE, ut_a, and ut_ad.
Referenced by opt_classify_comparison(), opt_find_copy_cols(), and opt_look_for_col_in_comparison_before().
00069 : TRUE if already determined */ 00070 que_node_t* exp, /* in: expression */ 00071 sel_node_t* sel_node, /* in: select node */ 00072 ulint nth_table) /* in: nth table will be accessed */ 00073 { 00074 func_node_t* func_node; 00075 sym_node_t* sym_node; 00076 dict_table_t* table; 00077 que_node_t* arg; 00078 ulint i; 00079 00080 ut_ad(exp && sel_node); 00081 00082 if (que_node_get_type(exp) == QUE_NODE_FUNC) { 00083 func_node = exp; 00084 00085 arg = func_node->args; 00086 00087 while (arg) { 00088 if (!opt_check_exp_determined_before(arg, sel_node, 00089 nth_table)) { 00090 return(FALSE); 00091 } 00092 00093 arg = que_node_get_next(arg); 00094 } 00095 00096 return(TRUE); 00097 } 00098 00099 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL); 00100 00101 sym_node = exp; 00102 00103 if (sym_node->token_type != SYM_COLUMN) { 00104 00105 return(TRUE); 00106 } 00107 00108 for (i = 0; i < nth_table; i++) { 00109 00110 table = sel_node_get_nth_plan(sel_node, i)->table; 00111 00112 if (sym_node->table == table) { 00113 00114 return(TRUE); 00115 } 00116 } 00117 00118 return(FALSE); 00119 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_check_order_by | ( | sel_node_t * | sel_node | ) | [static] |
Definition at line 458 of file pars0opt.c.
References sym_node_struct::col_no, order_node_struct::column, dict_index_get_n_unique(), dict_index_get_nth_col_no(), sel_node_struct::n_tables, sel_node_struct::order_by, plan(), sel_node_get_nth_plan(), sym_node_struct::table, and ut_a.
Referenced by opt_search_plan().
00460 : select node; asserts an error 00461 if the plan does not agree with the 00462 order-by */ 00463 { 00464 order_node_t* order_node; 00465 dict_table_t* order_table; 00466 ulint order_col_no; 00467 plan_t* plan; 00468 ulint i; 00469 00470 if (!sel_node->order_by) { 00471 00472 return; 00473 } 00474 00475 order_node = sel_node->order_by; 00476 order_col_no = order_node->column->col_no; 00477 order_table = order_node->column->table; 00478 00479 /* If there is an order-by clause, the first non-exactly matched field 00480 in the index used for the last table in the table list should be the 00481 column defined in the order-by clause, and for all the other tables 00482 we should get only at most a single row, otherwise we cannot presently 00483 calculate the order-by, as we have no sort utility */ 00484 00485 for (i = 0; i < sel_node->n_tables; i++) { 00486 00487 plan = sel_node_get_nth_plan(sel_node, i); 00488 00489 if (i < sel_node->n_tables - 1) { 00490 ut_a(dict_index_get_n_unique(plan->index) 00491 <= plan->n_exact_match); 00492 } else { 00493 ut_a(plan->table == order_table); 00494 00495 ut_a((dict_index_get_n_unique(plan->index) 00496 <= plan->n_exact_match) 00497 || (dict_index_get_nth_col_no(plan->index, 00498 plan->n_exact_match) 00499 == order_col_no)); 00500 } 00501 } 00502 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_classify_cols | ( | sel_node_t * | sel_node, | |
| ulint | i | |||
| ) | [static] |
Definition at line 977 of file pars0opt.c.
References FALSE, opt_find_all_cols(), opt_find_copy_cols(), plan(), que_node_get_next(), sel_node_struct::search_cond, sel_node_get_nth_plan(), sel_node_struct::select_list, TRUE, and UT_LIST_INIT.
Referenced by opt_search_plan().
00979 : select node */ 00980 ulint i) /* in: ith table in the join */ 00981 { 00982 plan_t* plan; 00983 que_node_t* exp; 00984 00985 plan = sel_node_get_nth_plan(sel_node, i); 00986 00987 /* The final value of the following field will depend on the 00988 environment of the select statement: */ 00989 00990 plan->must_get_clust = FALSE; 00991 00992 UT_LIST_INIT(plan->columns); 00993 00994 /* All select list columns should be copied: therefore TRUE as the 00995 first argument */ 00996 00997 exp = sel_node->select_list; 00998 00999 while (exp) { 01000 opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan, 01001 exp); 01002 exp = que_node_get_next(exp); 01003 } 01004 01005 opt_find_copy_cols(sel_node, i, sel_node->search_cond); 01006 01007 /* All remaining columns in the search condition are temporary 01008 columns: therefore FALSE */ 01009 01010 opt_find_all_cols(FALSE, plan->index, &(plan->columns), plan, 01011 sel_node->search_cond); 01012 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static ulint opt_classify_comparison | ( | sel_node_t * | sel_node, | |
| ulint | i, | |||
| func_node_t * | cond | |||
| ) | [static] |
Definition at line 605 of file pars0opt.c.
References cond, dtuple_get_n_fields(), opt_check_exp_determined_before(), OPT_END_COND, opt_is_arg(), OPT_NOT_COND, plan(), sel_node_get_nth_plan(), and ut_ad.
Referenced by opt_find_test_conds().
00607 : OPT_NOT_COND if not for this 00608 table, else OPT_END_COND, 00609 OPT_TEST_COND, or OPT_SCROLL_COND, 00610 where the last means that the 00611 condition need not be tested, except 00612 when scroll cursors are used */ 00613 sel_node_t* sel_node, /* in: select node */ 00614 ulint i, /* in: ith table in the join */ 00615 func_node_t* cond) /* in: comparison condition */ 00616 { 00617 plan_t* plan; 00618 ulint n_fields; 00619 ulint op; 00620 ulint j; 00621 00622 ut_ad(cond && sel_node); 00623 00624 plan = sel_node_get_nth_plan(sel_node, i); 00625 00626 /* Check if the condition is determined after the ith table has been 00627 accessed, but not after the i - 1:th */ 00628 00629 if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) { 00630 00631 return(OPT_NOT_COND); 00632 } 00633 00634 if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) { 00635 00636 return(OPT_NOT_COND); 00637 } 00638 00639 /* If the condition is an exact match condition used in constructing 00640 the search tuple, it is classified as OPT_END_COND */ 00641 00642 if (plan->tuple) { 00643 n_fields = dtuple_get_n_fields(plan->tuple); 00644 } else { 00645 n_fields = 0; 00646 } 00647 00648 for (j = 0; j < plan->n_exact_match; j++) { 00649 00650 if (opt_is_arg(plan->tuple_exps[j], cond)) { 00651 00652 return(OPT_END_COND); 00653 } 00654 } 00655 00656 /* If the condition is an non-exact match condition used in 00657 constructing the search tuple, it is classified as OPT_SCROLL_COND. 00658 When the cursor is positioned, and if a non-scroll cursor is used, 00659 there is no need to test this condition; if a scroll cursor is used 00660 the testing is necessary when the cursor is reversed. */ 00661 00662 if ((n_fields > plan->n_exact_match) 00663 && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) { 00664 00665 return(OPT_SCROLL_COND); 00666 } 00667 00668 /* If the condition is a non-exact match condition on the first field 00669 in index for which there is no exact match, and it limits the search 00670 range from the opposite side of the search tuple already BEFORE we 00671 access the table, it is classified as OPT_END_COND */ 00672 00673 if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match) 00674 && opt_look_for_col_in_comparison_before( 00675 OPT_COMPARISON, 00676 dict_index_get_nth_col_no(plan->index, 00677 plan->n_exact_match), 00678 cond, sel_node, i, &op)) { 00679 00680 if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) { 00681 00682 return(OPT_END_COND); 00683 } 00684 00685 if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) { 00686 00687 return(OPT_END_COND); 00688 } 00689 } 00690 00691 /* Otherwise, cond is classified as OPT_TEST_COND */ 00692 00693 return(OPT_TEST_COND); 00694 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_clust_access | ( | sel_node_t * | sel_node, | |
| ulint | n | |||
| ) | [static] |
Definition at line 1019 of file pars0opt.c.
References DICT_CLUSTERED, dict_index_copy_types(), dict_index_get_n_unique(), dict_index_get_nth_field(), dict_index_get_nth_field_pos(), dict_table_get_first_index(), dtuple_create(), FALSE, sym_tab_struct::heap, index(), mem_heap_alloc(), NULL, pars_sym_tab_global, plan(), pos(), sel_node_get_nth_plan(), ut_a, and ut_ad.
Referenced by opt_search_plan().
01021 : select node */ 01022 ulint n) /* in: nth table in select */ 01023 { 01024 plan_t* plan; 01025 dict_table_t* table; 01026 dict_index_t* clust_index; 01027 dict_index_t* index; 01028 mem_heap_t* heap; 01029 ulint n_fields; 01030 ulint pos; 01031 ulint i; 01032 01033 plan = sel_node_get_nth_plan(sel_node, n); 01034 01035 index = plan->index; 01036 01037 /* The final value of the following field depends on the environment 01038 of the select statement: */ 01039 01040 plan->no_prefetch = FALSE; 01041 01042 if (index->type & DICT_CLUSTERED) { 01043 plan->clust_map = NULL; 01044 plan->clust_ref = NULL; 01045 01046 return; 01047 } 01048 01049 table = index->table; 01050 01051 clust_index = dict_table_get_first_index(table); 01052 01053 n_fields = dict_index_get_n_unique(clust_index); 01054 01055 heap = pars_sym_tab_global->heap; 01056 01057 plan->clust_ref = dtuple_create(heap, n_fields); 01058 01059 dict_index_copy_types(plan->clust_ref, clust_index, n_fields); 01060 01061 plan->clust_map = mem_heap_alloc(heap, n_fields * sizeof(ulint)); 01062 01063 for (i = 0; i < n_fields; i++) { 01064 pos = dict_index_get_nth_field_pos(index, clust_index, i); 01065 01066 ut_a(pos != ULINT_UNDEFINED); 01067 01068 /* We optimize here only queries to InnoDB's internal system 01069 tables, and they should not contain column prefix indexes. */ 01070 01071 if (dict_index_get_nth_field(index, pos)->prefix_len != 0 01072 || dict_index_get_nth_field(clust_index, i) 01073 ->prefix_len != 0) { 01074 fprintf(stderr, 01075 "InnoDB: Error in pars0opt.c: table %s has prefix_len != 0\n", 01076 index->table_name); 01077 } 01078 01079 *(plan->clust_map + i) = pos; 01080 01081 ut_ad(pos != ULINT_UNDEFINED); 01082 } 01083 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_determine_and_normalize_test_conds | ( | sel_node_t * | sel_node, | |
| ulint | i | |||
| ) | [static] |
Definition at line 789 of file pars0opt.c.
References opt_find_test_conds(), opt_normalize_cmp_conds(), plan(), sel_node_struct::search_cond, sel_node_get_nth_plan(), ut_a, UT_LIST_GET_FIRST, UT_LIST_GET_LEN, and UT_LIST_INIT.
Referenced by opt_search_plan().
00791 : select node */ 00792 ulint i) /* in: ith table in the join */ 00793 { 00794 plan_t* plan; 00795 00796 plan = sel_node_get_nth_plan(sel_node, i); 00797 00798 UT_LIST_INIT(plan->end_conds); 00799 UT_LIST_INIT(plan->other_conds); 00800 00801 /* Recursively go through the conjuncts and classify them */ 00802 00803 opt_find_test_conds(sel_node, i, sel_node->search_cond); 00804 00805 opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds), 00806 plan->table); 00807 00808 ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match); 00809 }
Here is the call graph for this function:
Here is the caller graph for this function:
| 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 at line 820 of file pars0opt.c.
References sym_node_struct::alias, func_node_struct::args, sym_node_struct::col_no, sym_node_struct::copy_val, DICT_CLUSTERED, dict_index_get_nth_col_pos(), dict_table_get_first_index(), sym_node_struct::field_nos, index(), sym_node_struct::indirection, NULL, opt_find_all_cols(), plan(), QUE_NODE_FUNC, que_node_get_next(), que_node_get_type(), QUE_NODE_SYMBOL, SYM_CLUST_FIELD_NO, SYM_COLUMN, SYM_SEC_FIELD_NO, sym_node_struct::table, sym_node_struct::token_type, TRUE, ut_a, UT_LIST_ADD_LAST, UT_LIST_GET_FIRST, and UT_LIST_GET_NEXT.
Referenced by opt_classify_cols(), opt_find_all_cols(), opt_find_copy_cols(), and pars_process_assign_list().
00822 : if TRUE, new found columns are 00823 added as columns to copy */ 00824 dict_index_t* index, /* in: index of the table to use */ 00825 sym_node_list_t* col_list, /* in: base node of a list where 00826 to add new found columns */ 00827 plan_t* plan, /* in: plan or NULL */ 00828 que_node_t* exp) /* in: expression or condition or 00829 NULL */ 00830 { 00831 func_node_t* func_node; 00832 que_node_t* arg; 00833 sym_node_t* sym_node; 00834 sym_node_t* col_node; 00835 ulint col_pos; 00836 00837 if (exp == NULL) { 00838 00839 return; 00840 } 00841 00842 if (que_node_get_type(exp) == QUE_NODE_FUNC) { 00843 func_node = exp; 00844 00845 arg = func_node->args; 00846 00847 while (arg) { 00848 opt_find_all_cols(copy_val, index, col_list, plan, 00849 arg); 00850 arg = que_node_get_next(arg); 00851 } 00852 00853 return; 00854 } 00855 00856 ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL); 00857 00858 sym_node = exp; 00859 00860 if (sym_node->token_type != SYM_COLUMN) { 00861 00862 return; 00863 } 00864 00865 if (sym_node->table != index->table) { 00866 00867 return; 00868 } 00869 00870 /* Look for an occurrence of the same column in the plan column 00871 list */ 00872 00873 col_node = UT_LIST_GET_FIRST(*col_list); 00874 00875 while (col_node) { 00876 if (col_node->col_no == sym_node->col_no) { 00877 00878 if (col_node == sym_node) { 00879 /* sym_node was already in a list: do 00880 nothing */ 00881 00882 return; 00883 } 00884 00885 /* Put an indirection */ 00886 sym_node->indirection = col_node; 00887 sym_node->alias = col_node; 00888 00889 return; 00890 } 00891 00892 col_node = UT_LIST_GET_NEXT(col_var_list, col_node); 00893 } 00894 00895 /* The same column did not occur in the list: add it */ 00896 00897 UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node); 00898 00899 sym_node->copy_val = copy_val; 00900 00901 /* Fill in the field_no fields in sym_node */ 00902 00903 sym_node->field_nos[SYM_CLUST_FIELD_NO] 00904 = dict_index_get_nth_col_pos( 00905 dict_table_get_first_index(index->table), 00906 sym_node->col_no); 00907 if (!(index->type & DICT_CLUSTERED)) { 00908 00909 ut_a(plan); 00910 00911 col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no); 00912 00913 if (col_pos == ULINT_UNDEFINED) { 00914 00915 plan->must_get_clust = TRUE; 00916 } 00917 00918 sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos; 00919 } 00920 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_find_copy_cols | ( | sel_node_t * | sel_node, | |
| ulint | i, | |||
| func_node_t * | search_cond | |||
| ) | [static] |
Definition at line 929 of file pars0opt.c.
References func_node_struct::args, func_node_struct::func, NULL, opt_check_exp_determined_before(), opt_find_all_cols(), PARS_AND_TOKEN, plan(), QUE_NODE_FUNC, que_node_get_next(), que_node_get_type(), sel_node_get_nth_plan(), TRUE, and ut_ad.
Referenced by opt_classify_cols().
00931 : select node */ 00932 ulint i, /* in: ith table in the join */ 00933 func_node_t* search_cond) /* in: search condition or NULL */ 00934 { 00935 func_node_t* new_cond; 00936 plan_t* plan; 00937 00938 if (search_cond == NULL) { 00939 00940 return; 00941 } 00942 00943 ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC); 00944 00945 if (search_cond->func == PARS_AND_TOKEN) { 00946 new_cond = search_cond->args; 00947 00948 opt_find_copy_cols(sel_node, i, new_cond); 00949 00950 new_cond = que_node_get_next(new_cond); 00951 00952 opt_find_copy_cols(sel_node, i, new_cond); 00953 00954 return; 00955 } 00956 00957 if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) { 00958 00959 /* Any ith table columns occurring in search_cond should be 00960 copied, as this condition cannot be tested already on the 00961 fetch from the ith table */ 00962 00963 plan = sel_node_get_nth_plan(sel_node, i); 00964 00965 opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan, 00966 search_cond); 00967 } 00968 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_find_test_conds | ( | sel_node_t * | sel_node, | |
| ulint | i, | |||
| func_node_t * | cond | |||
| ) | [static] |
Definition at line 700 of file pars0opt.c.
References cond, NULL, opt_classify_comparison(), OPT_END_COND, OPT_TEST_COND, PARS_AND_TOKEN, plan(), que_node_get_next(), sel_node_get_nth_plan(), and UT_LIST_ADD_LAST.
Referenced by opt_determine_and_normalize_test_conds().
00702 : select node */ 00703 ulint i, /* in: ith table in the join */ 00704 func_node_t* cond) /* in: conjunction of search 00705 conditions or NULL */ 00706 { 00707 func_node_t* new_cond; 00708 ulint class; 00709 plan_t* plan; 00710 00711 if (cond == NULL) { 00712 00713 return; 00714 } 00715 00716 if (cond->func == PARS_AND_TOKEN) { 00717 new_cond = cond->args; 00718 00719 opt_find_test_conds(sel_node, i, new_cond); 00720 00721 new_cond = que_node_get_next(new_cond); 00722 00723 opt_find_test_conds(sel_node, i, new_cond); 00724 00725 return; 00726 } 00727 00728 plan = sel_node_get_nth_plan(sel_node, i); 00729 00730 class = opt_classify_comparison(sel_node, i, cond); 00731 00732 if (class == OPT_END_COND) { 00733 UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond); 00734 00735 } else if (class == OPT_TEST_COND) { 00736 UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond); 00737 00738 } 00739 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static int opt_invert_cmp_op | ( | int | op | ) | [static] |
Definition at line 38 of file pars0opt.c.
References PARS_GE_TOKEN, PARS_LE_TOKEN, and ut_error.
Referenced by opt_look_for_col_in_comparison_before(), and opt_normalize_cmp_conds().
00040 : the equivalent operator when the order of 00041 the arguments is switched */ 00042 int op) /* in: operator */ 00043 { 00044 if (op == '<') { 00045 return('>'); 00046 } else if (op == '>') { 00047 return('<'); 00048 } else if (op == '=') { 00049 return('='); 00050 } else if (op == PARS_LE_TOKEN) { 00051 return(PARS_GE_TOKEN); 00052 } else if (op == PARS_GE_TOKEN) { 00053 return(PARS_LE_TOKEN); 00054 } else { 00055 ut_error; 00056 } 00057 00058 return(0); 00059 }
Here is the caller graph for this function:
| static ibool opt_is_arg | ( | que_node_t * | arg_node, | |
| func_node_t * | func_node | |||
| ) | [static] |
Definition at line 430 of file pars0opt.c.
References func_node_struct::args, FALSE, que_node_get_next(), and TRUE.
Referenced by opt_classify_comparison().
00432 : TRUE if is an argument */ 00433 que_node_t* arg_node, /* in: possible argument node */ 00434 func_node_t* func_node) /* in: function node */ 00435 { 00436 que_node_t* arg; 00437 00438 arg = func_node->args; 00439 00440 while (arg) { 00441 if (arg == arg_node) { 00442 00443 return(TRUE); 00444 } 00445 00446 arg = que_node_get_next(arg); 00447 } 00448 00449 return(FALSE); 00450 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static que_node_t* opt_look_for_col_in_comparison_before | ( | ulint | cmp_type, | |
| ulint | col_no, | |||
| func_node_t * | search_cond, | |||
| sel_node_t * | sel_node, | |||
| ulint | nth_table, | |||
| ulint * | op | |||
| ) | [static] |
Definition at line 126 of file pars0opt.c.
References func_node_struct::args, sym_node_struct::col_no, func_node_struct::func, NULL, opt_check_exp_determined_before(), OPT_COMPARISON, OPT_EQUAL, opt_invert_cmp_op(), PARS_GE_TOKEN, PARS_LE_TOKEN, que_node_get_next(), que_node_get_type(), QUE_NODE_SYMBOL, sel_node_get_nth_plan(), SYM_COLUMN, sym_node_struct::table, plan_struct::table, sym_node_struct::token_type, ut_a, and ut_ad.
Referenced by opt_look_for_col_in_cond_before().
00128 : expression restricting the 00129 value of the column, or NULL if not 00130 known */ 00131 ulint cmp_type, /* in: OPT_EQUAL, OPT_COMPARISON */ 00132 ulint col_no, /* in: column number */ 00133 func_node_t* search_cond, /* in: comparison condition */ 00134 sel_node_t* sel_node, /* in: select node */ 00135 ulint nth_table, /* in: nth table in a join (a query 00136 from a single table is considered a 00137 join of 1 table) */ 00138 ulint* op) /* out: comparison operator ('=', 00139 PARS_GE_TOKEN, ... ); this is inverted 00140 if the column appears on the right 00141 side */ 00142 { 00143 sym_node_t* sym_node; 00144 dict_table_t* table; 00145 que_node_t* exp; 00146 que_node_t* arg; 00147 00148 ut_ad(search_cond); 00149 00150 ut_a((search_cond->func == '<') 00151 || (search_cond->func == '>') 00152 || (search_cond->func == '=') 00153 || (search_cond->func == PARS_GE_TOKEN) 00154 || (search_cond->func == PARS_LE_TOKEN)); 00155 00156 table = sel_node_get_nth_plan(sel_node, nth_table)->table; 00157 00158 if ((cmp_type == OPT_EQUAL) && (search_cond->func != '=')) { 00159 00160 return(NULL); 00161 00162 } else if ((cmp_type == OPT_COMPARISON) 00163 && (search_cond->func != '<') 00164 && (search_cond->func != '>') 00165 && (search_cond->func != PARS_GE_TOKEN) 00166 && (search_cond->func != PARS_LE_TOKEN)) { 00167 00168 return(NULL); 00169 } 00170 00171 arg = search_cond->args; 00172 00173 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) { 00174 sym_node = arg; 00175 00176 if ((sym_node->token_type == SYM_COLUMN) 00177 && (sym_node->table == table) 00178 && (sym_node->col_no == col_no)) { 00179 00180 /* sym_node contains the desired column id */ 00181 00182 /* Check if the expression on the right side of the 00183 operator is already determined */ 00184 00185 exp = que_node_get_next(arg); 00186 00187 if (opt_check_exp_determined_before(exp, sel_node, 00188 nth_table)) { 00189 *op = search_cond->func; 00190 00191 return(exp); 00192 } 00193 } 00194 } 00195 00196 exp = search_cond->args; 00197 arg = que_node_get_next(arg); 00198 00199 if (que_node_get_type(arg) == QUE_NODE_SYMBOL) { 00200 sym_node = arg; 00201 00202 if ((sym_node->token_type == SYM_COLUMN) 00203 && (sym_node->table == table) 00204 && (sym_node->col_no == col_no)) { 00205 00206 if (opt_check_exp_determined_before(exp, sel_node, 00207 nth_table)) { 00208 *op = opt_invert_cmp_op(search_cond->func); 00209 00210 return(exp); 00211 } 00212 } 00213 } 00214 00215 return(NULL); 00216 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static que_node_t* opt_look_for_col_in_cond_before | ( | ulint | cmp_type, | |
| ulint | col_no, | |||
| func_node_t * | search_cond, | |||
| sel_node_t * | sel_node, | |||
| ulint | nth_table, | |||
| ulint * | op | |||
| ) | [static] |
Definition at line 225 of file pars0opt.c.
References func_node_struct::args, sel_node_struct::asc, func_node_struct::func, NULL, opt_look_for_col_in_comparison_before(), PARS_AND_TOKEN, PARS_GE_TOKEN, PARS_LE_TOKEN, PARS_NOT_TOKEN, PARS_OR_TOKEN, QUE_NODE_FUNC, que_node_get_next(), que_node_get_type(), and ut_a.
Referenced by opt_calc_index_goodness().
00227 : expression restricting the 00228 value of the column, or NULL if not 00229 known */ 00230 ulint cmp_type, /* in: OPT_EQUAL, OPT_COMPARISON */ 00231 ulint col_no, /* in: column number */ 00232 func_node_t* search_cond, /* in: search condition or NULL */ 00233 sel_node_t* sel_node, /* in: select node */ 00234 ulint nth_table, /* in: nth table in a join (a query 00235 from a single table is considered a 00236 join of 1 table) */ 00237 ulint* op) /* out: comparison operator ('=', 00238 PARS_GE_TOKEN, ... ) */ 00239 { 00240 func_node_t* new_cond; 00241 que_node_t* exp; 00242 00243 if (search_cond == NULL) { 00244 00245 return(NULL); 00246 } 00247 00248 ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC); 00249 ut_a(search_cond->func != PARS_OR_TOKEN); 00250 ut_a(search_cond->func != PARS_NOT_TOKEN); 00251 00252 if (search_cond->func == PARS_AND_TOKEN) { 00253 new_cond = search_cond->args; 00254 00255 exp = opt_look_for_col_in_cond_before(cmp_type, col_no, 00256 new_cond, sel_node, nth_table, op); 00257 if (exp) { 00258 00259 return(exp); 00260 } 00261 00262 new_cond = que_node_get_next(new_cond); 00263 00264 exp = opt_look_for_col_in_cond_before(cmp_type, col_no, 00265 new_cond, sel_node, nth_table, op); 00266 return(exp); 00267 } 00268 00269 exp = opt_look_for_col_in_comparison_before(cmp_type, col_no, 00270 search_cond, sel_node, nth_table, op); 00271 if (exp == NULL) { 00272 00273 return(NULL); 00274 } 00275 00276 /* If we will fetch in an ascending order, we cannot utilize an upper 00277 limit for a column value; in a descending order, respectively, a lower 00278 limit */ 00279 00280 if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) { 00281 00282 return(NULL); 00283 00284 } else if (!sel_node->asc && ((*op == '>') || (*op == PARS_GE_TOKEN))) { 00285 00286 return(NULL); 00287 } 00288 00289 return(exp); 00290 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_normalize_cmp_conds | ( | func_node_t * | cond, | |
| dict_table_t * | table | |||
| ) | [static] |
Definition at line 747 of file pars0opt.c.
References cond, NULL, opt_invert_cmp_op(), que_node_get_next(), que_node_get_type(), que_node_list_add_last(), QUE_NODE_SYMBOL, SYM_COLUMN, sym_node_struct::table, sym_node_struct::token_type, and UT_LIST_GET_NEXT.
Referenced by opt_determine_and_normalize_test_conds().
00749 : first in a list of comparison 00750 conditions, or NULL */ 00751 dict_table_t* table) /* in: table */ 00752 { 00753 que_node_t* arg1; 00754 que_node_t* arg2; 00755 sym_node_t* sym_node; 00756 00757 while (cond) { 00758 arg1 = cond->args; 00759 arg2 = que_node_get_next(arg1); 00760 00761 if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) { 00762 00763 sym_node = arg2; 00764 00765 if ((sym_node->token_type == SYM_COLUMN) 00766 && (sym_node->table == table)) { 00767 00768 /* Switch the order of the arguments */ 00769 00770 cond->args = arg2; 00771 que_node_list_add_last(NULL, arg2); 00772 que_node_list_add_last(arg2, arg1); 00773 00774 /* Invert the operator */ 00775 cond->func = opt_invert_cmp_op(cond->func); 00776 } 00777 } 00778 00779 cond = UT_LIST_GET_NEXT(cond_list, cond); 00780 } 00781 }
Here is the call graph for this function:
Here is the caller graph for this function:
Definition at line 394 of file pars0opt.c.
References PAGE_CUR_G, PAGE_CUR_GE, PAGE_CUR_L, PAGE_CUR_LE, PARS_GE_TOKEN, PARS_LE_TOKEN, ut_a, and ut_error.
Referenced by opt_search_plan_for_table().
00396 : search mode */ 00397 ibool asc, /* in: TRUE if the rows should be fetched in an 00398 ascending order */ 00399 ulint op) /* in: operator '=', PARS_GE_TOKEN, ... */ 00400 { 00401 if (op == '=') { 00402 if (asc) { 00403 return(PAGE_CUR_GE); 00404 } else { 00405 return(PAGE_CUR_LE); 00406 } 00407 } else if (op == '<') { 00408 ut_a(!asc); 00409 return(PAGE_CUR_L); 00410 } else if (op == '>') { 00411 ut_a(asc); 00412 return(PAGE_CUR_G); 00413 } else if (op == PARS_GE_TOKEN) { 00414 ut_a(asc); 00415 return(PAGE_CUR_GE); 00416 } else if (op == PARS_LE_TOKEN) { 00417 ut_a(!asc); 00418 return(PAGE_CUR_LE); 00419 } else { 00420 ut_error; 00421 } 00422 00423 return(0); 00424 }
Here is the caller graph for this function:
| void opt_print_query_plan | ( | sel_node_t * | sel_node | ) |
Definition at line 1164 of file pars0opt.c.
References sel_node_struct::asc, sel_node_struct::consistent_read, dict_index_name_print(), dtuple_get_n_fields(), LOCK_S, LOCK_X, sel_node_struct::n_tables, NULL, plan(), sel_node_struct::row_lock_mode, sel_node_get_nth_plan(), sel_node_struct::set_x_locks, ut_a, and UT_LIST_GET_LEN.
Referenced by opt_search_plan().
01166 : select node */ 01167 { 01168 plan_t* plan; 01169 ulint n_fields; 01170 ulint i; 01171 01172 fputs("QUERY PLAN FOR A SELECT NODE\n", stderr); 01173 01174 fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr); 01175 01176 if (sel_node->set_x_locks) { 01177 fputs("sets row x-locks; ", stderr); 01178 ut_a(sel_node->row_lock_mode == LOCK_X); 01179 ut_a(!sel_node->consistent_read); 01180 } else if (sel_node->consistent_read) { 01181 fputs("consistent read; ", stderr); 01182 } else { 01183 ut_a(sel_node->row_lock_mode == LOCK_S); 01184 fputs("sets row s-locks; ", stderr); 01185 } 01186 01187 putc('\n', stderr); 01188 01189 for (i = 0; i < sel_node->n_tables; i++) { 01190 plan = sel_node_get_nth_plan(sel_node, i); 01191 01192 if (plan->tuple) { 01193 n_fields = dtuple_get_n_fields(plan->tuple); 01194 } else { 01195 n_fields = 0; 01196 } 01197 01198 fputs("Table ", stderr); 01199 dict_index_name_print(stderr, NULL, plan->index); 01200 fprintf(stderr,"; exact m. %lu, match %lu, end conds %lu\n", 01201 (unsigned long) plan->n_exact_match, 01202 (unsigned long) n_fields, 01203 (unsigned long) UT_LIST_GET_LEN(plan->end_conds)); 01204 } 01205 }
Here is the call graph for this function:
Here is the caller graph for this function:
| void opt_search_plan | ( | sel_node_t * | sel_node | ) |
Definition at line 1091 of file pars0opt.c.
References sel_node_struct::asc, sym_tab_struct::heap, mem_heap_alloc(), sel_node_struct::n_tables, NULL, opt_check_order_by(), opt_classify_cols(), opt_clust_access(), opt_determine_and_normalize_test_conds(), opt_print_query_plan(), opt_search_plan_for_table(), sel_node_struct::order_by, order_by, pars_sym_tab_global, sel_node_struct::plans, que_node_get_next(), sym_node_struct::table, sel_node_struct::table_list, and TRUE.
Referenced by pars_select_statement().
01093 : parsed select node */ 01094 { 01095 sym_node_t* table_node; 01096 dict_table_t* table; 01097 order_node_t* order_by; 01098 ulint i; 01099 01100 sel_node->plans = mem_heap_alloc(pars_sym_tab_global->heap, 01101 sel_node->n_tables * sizeof(plan_t)); 01102 01103 /* Analyze the search condition to find out what we know at each 01104 join stage about the conditions that the columns of a table should 01105 satisfy */ 01106 01107 table_node = sel_node->table_list; 01108 01109 if (sel_node->order_by == NULL) { 01110 sel_node->asc = TRUE; 01111 } else { 01112 order_by = sel_node->order_by; 01113 01114 sel_node->asc = order_by->asc; 01115 } 01116 01117 for (i = 0; i < sel_node->n_tables; i++) { 01118 01119 table = table_node->table; 01120 01121 /* Choose index through which to access the table */ 01122 01123 opt_search_plan_for_table(sel_node, i, table); 01124 01125 /* Determine the search condition conjuncts we can test at 01126 this table; normalize the end conditions */ 01127 01128 opt_determine_and_normalize_test_conds(sel_node, i); 01129 01130 table_node = que_node_get_next(table_node); 01131 } 01132 01133 table_node = sel_node->table_list; 01134 01135 for (i = 0; i < sel_node->n_tables; i++) { 01136 01137 /* Classify the table columns into those we only need to access 01138 but not copy, and to those we must copy to dynamic memory */ 01139 01140 opt_classify_cols(sel_node, i); 01141 01142 /* Calculate possible info for accessing the clustered index 01143 record */ 01144 01145 opt_clust_access(sel_node, i); 01146 01147 table_node = que_node_get_next(table_node); 01148 } 01149 01150 /* Check that the plan obeys a possible order-by clause: if not, 01151 an assertion error occurs */ 01152 01153 opt_check_order_by(sel_node); 01154 01155 #ifdef UNIV_SQL_DEBUG 01156 opt_print_query_plan(sel_node); 01157 #endif 01158 }
Here is the call graph for this function:
Here is the caller graph for this function:
| static void opt_search_plan_for_table | ( | sel_node_t * | sel_node, | |
| ulint | i, | |||
| dict_table_t * | table | |||
| ) | [static] |
Definition at line 510 of file pars0opt.c.
References sel_node_struct::asc, btr_pcur_init(), DICT_CLUSTERED, dict_index_copy_types(), dict_index_get_n_unique(), dict_table_get_first_index(), dict_table_get_next_index(), dtuple_create(), FALSE, sym_tab_struct::heap, index(), mem_heap_alloc(), NULL, opt_calc_index_goodness(), opt_calc_n_fields_from_goodness(), opt_op_to_search_mode(), pars_sym_tab_global, plan(), sel_node_get_nth_plan(), TRUE, dict_index_struct::type, and ut_memcpy().
Referenced by opt_search_plan().
00512 : parsed select node */ 00513 ulint i, /* in: this is the ith table */ 00514 dict_table_t* table) /* in: table */ 00515 { 00516 plan_t* plan; 00517 dict_index_t* index; 00518 dict_index_t* best_index; 00519 ulint n_fields; 00520 ulint goodness; 00521 ulint last_op = 75946965; /* Eliminate a Purify 00522 warning */ 00523 ulint best_goodness; 00524 ulint best_last_op = 0; /* remove warning */ 00525 que_node_t* index_plan[256]; 00526 que_node_t* best_index_plan[256]; 00527 00528 plan = sel_node_get_nth_plan(sel_node, i); 00529 00530 plan->table = table; 00531 plan->asc = sel_node->asc; 00532 plan->pcur_is_open = FALSE; 00533 plan->cursor_at_end = FALSE; 00534 00535 /* Calculate goodness for each index of the table */ 00536 00537 index = dict_table_get_first_index(table); 00538 best_index = index; /* Eliminate compiler warning */ 00539 best_goodness = 0; 00540 00541 /* should be do ... until ? comment by Jani */ 00542 while (index) { 00543 goodness = opt_calc_index_goodness(index, sel_node, i, 00544 index_plan, &last_op); 00545 if (goodness > best_goodness) { 00546 00547 best_index = index; 00548 best_goodness = goodness; 00549 n_fields = opt_calc_n_fields_from_goodness(goodness); 00550 00551 ut_memcpy(best_index_plan, index_plan, 00552 n_fields * sizeof(void*)); 00553 best_last_op = last_op; 00554 } 00555 00556 index = dict_table_get_next_index(index); 00557 } 00558 00559 plan->index = best_index; 00560 00561 n_fields = opt_calc_n_fields_from_goodness(best_goodness); 00562 00563 if (n_fields == 0) { 00564 plan->tuple = NULL; 00565 plan->n_exact_match = 0; 00566 } else { 00567 plan->tuple = dtuple_create(pars_sym_tab_global->heap, 00568 n_fields); 00569 dict_index_copy_types(plan->tuple, plan->index, n_fields); 00570 00571 plan->tuple_exps = mem_heap_alloc(pars_sym_tab_global->heap, 00572 n_fields * sizeof(void*)); 00573 00574 ut_memcpy(plan->tuple_exps, best_index_plan, 00575 n_fields * sizeof(void*)); 00576 if (best_last_op == '=') { 00577 plan->n_exact_match = n_fields; 00578 } else { 00579 plan->n_exact_match = n_fields - 1; 00580 } 00581 00582 plan->mode = opt_op_to_search_mode(sel_node->asc, 00583 best_last_op); 00584 } 00585 00586 if ((best_index->type & DICT_CLUSTERED) 00587 && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) { 00588 00589 plan->unique_search = TRUE; 00590 } else { 00591 plan->unique_search = FALSE; 00592 } 00593 00594 plan->old_vers_heap = NULL; 00595 00596 btr_pcur_init(&(plan->pcur)); 00597 btr_pcur_init(&(plan->clust_pcur)); 00598 }
Here is the call graph for this function:
Here is the caller graph for this function:
Generated on Sat Sep 9 12:55:07 2006 for MySQL 5.1 by
1.4.7