Drizzled Public API Documentation

pars0opt.cc

00001 /*****************************************************************************
00002 
00003 Copyright (C) 1997, 2009, Innobase Oy. All Rights Reserved.
00004 
00005 This program is free software; you can redistribute it and/or modify it under
00006 the terms of the GNU General Public License as published by the Free Software
00007 Foundation; version 2 of the License.
00008 
00009 This program is distributed in the hope that it will be useful, but WITHOUT
00010 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00011 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
00012 
00013 You should have received a copy of the GNU General Public License along with
00014 this program; if not, write to the Free Software Foundation, Inc., 51 Franklin
00015 St, Fifth Floor, Boston, MA 02110-1301 USA
00016 
00017 *****************************************************************************/
00018 
00019 /**************************************************/
00026 #include "pars0opt.h"
00027 
00028 #ifdef UNIV_NONINL
00029 #include "pars0opt.ic"
00030 #endif
00031 
00032 #include "row0sel.h"
00033 #include "row0ins.h"
00034 #include "row0upd.h"
00035 #include "dict0dict.h"
00036 #include "dict0mem.h"
00037 #include "que0que.h"
00038 #include "pars0grm.hh"
00039 #include "pars0pars.h"
00040 #include "lock0lock.h"
00041 
00042 #define OPT_EQUAL 1 /* comparison by = */
00043 #define OPT_COMPARISON  2 /* comparison by <, >, <=, or >= */
00044 
00045 #define OPT_NOT_COND  1
00046 #define OPT_END_COND  2
00047 #define OPT_TEST_COND 3
00048 #define OPT_SCROLL_COND 4
00049 
00050 
00051 /*******************************************************************/
00054 static
00055 int
00056 opt_invert_cmp_op(
00057 /*==============*/
00058   int op) 
00059 {
00060   if (op == '<') {
00061     return('>');
00062   } else if (op == '>') {
00063     return('<');
00064   } else if (op == '=') {
00065     return('=');
00066   } else if (op == PARS_LE_TOKEN) {
00067     return(PARS_GE_TOKEN);
00068   } else if (op == PARS_GE_TOKEN) {
00069     return(PARS_LE_TOKEN);
00070   } else {
00071     ut_error;
00072   }
00073 
00074   return(0);
00075 }
00076 
00077 /*******************************************************************/
00082 static
00083 ibool
00084 opt_check_exp_determined_before(
00085 /*============================*/
00086   que_node_t* exp,    
00087   sel_node_t* sel_node, 
00088   ulint   nth_table)  
00089 {
00090   func_node_t*  func_node;
00091   sym_node_t* sym_node;
00092   dict_table_t* table;
00093   que_node_t* arg;
00094   ulint   i;
00095 
00096   ut_ad(exp && sel_node);
00097 
00098   if (que_node_get_type(exp) == QUE_NODE_FUNC) {
00099     func_node = static_cast<func_node_t *>(exp);
00100 
00101     arg = func_node->args;
00102 
00103     while (arg) {
00104       if (!opt_check_exp_determined_before(arg, sel_node,
00105                    nth_table)) {
00106         return(FALSE);
00107       }
00108 
00109       arg = que_node_get_next(arg);
00110     }
00111 
00112     return(TRUE);
00113   }
00114 
00115   ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
00116 
00117   sym_node = static_cast<sym_node_t *>(exp);
00118 
00119   if (sym_node->token_type != SYM_COLUMN) {
00120 
00121     return(TRUE);
00122   }
00123 
00124   for (i = 0; i < nth_table; i++) {
00125 
00126     table = sel_node_get_nth_plan(sel_node, i)->table;
00127 
00128     if (sym_node->table == table) {
00129 
00130       return(TRUE);
00131     }
00132   }
00133 
00134   return(FALSE);
00135 }
00136 
00137 /*******************************************************************/
00141 static
00142 que_node_t*
00143 opt_look_for_col_in_comparison_before(
00144 /*==================================*/
00145   ulint   cmp_type, 
00146   ulint   col_no,   
00147   func_node_t*  search_cond,  
00148   sel_node_t* sel_node, 
00149   ulint   nth_table,  
00152   ulint*    op)   
00156 {
00157   sym_node_t* sym_node;
00158   dict_table_t* table;
00159   que_node_t* exp;
00160   que_node_t* arg;
00161 
00162   ut_ad(search_cond);
00163 
00164   ut_a((search_cond->func == '<')
00165        || (search_cond->func == '>')
00166        || (search_cond->func == '=')
00167        || (search_cond->func == PARS_GE_TOKEN)
00168        || (search_cond->func == PARS_LE_TOKEN));
00169 
00170   table = sel_node_get_nth_plan(sel_node, nth_table)->table;
00171 
00172   if ((cmp_type == OPT_EQUAL) && (search_cond->func != '=')) {
00173 
00174     return(NULL);
00175 
00176   } else if ((cmp_type == OPT_COMPARISON)
00177        && (search_cond->func != '<')
00178        && (search_cond->func != '>')
00179        && (search_cond->func != PARS_GE_TOKEN)
00180        && (search_cond->func != PARS_LE_TOKEN)) {
00181 
00182     return(NULL);
00183   }
00184 
00185   arg = search_cond->args;
00186 
00187   if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
00188     sym_node = static_cast<sym_node_t *>(arg);
00189 
00190     if ((sym_node->token_type == SYM_COLUMN)
00191         && (sym_node->table == table)
00192         && (sym_node->col_no == col_no)) {
00193 
00194       /* sym_node contains the desired column id */
00195 
00196       /* Check if the expression on the right side of the
00197       operator is already determined */
00198 
00199       exp = que_node_get_next(arg);
00200 
00201       if (opt_check_exp_determined_before(exp, sel_node,
00202                   nth_table)) {
00203         *op = search_cond->func;
00204 
00205         return(exp);
00206       }
00207     }
00208   }
00209 
00210   exp = search_cond->args;
00211   arg = que_node_get_next(arg);
00212 
00213   if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
00214     sym_node = static_cast<sym_node_t *>(arg);
00215 
00216     if ((sym_node->token_type == SYM_COLUMN)
00217         && (sym_node->table == table)
00218         && (sym_node->col_no == col_no)) {
00219 
00220       if (opt_check_exp_determined_before(exp, sel_node,
00221                   nth_table)) {
00222         *op = opt_invert_cmp_op(search_cond->func);
00223 
00224         return(exp);
00225       }
00226     }
00227   }
00228 
00229   return(NULL);
00230 }
00231 
00232 /*******************************************************************/
00238 static
00239 que_node_t*
00240 opt_look_for_col_in_cond_before(
00241 /*============================*/
00242   ulint   cmp_type, 
00243   ulint   col_no,   
00244   func_node_t*  search_cond,  
00245   sel_node_t* sel_node, 
00246   ulint   nth_table,  
00249   ulint*    op)   
00251 {
00252   func_node_t*  new_cond;
00253   que_node_t* exp;
00254 
00255   if (search_cond == NULL) {
00256 
00257     return(NULL);
00258   }
00259 
00260   ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
00261   ut_a(search_cond->func != PARS_OR_TOKEN);
00262   ut_a(search_cond->func != PARS_NOT_TOKEN);
00263 
00264   if (search_cond->func == PARS_AND_TOKEN) {
00265     new_cond = static_cast<func_node_t *>(search_cond->args);
00266 
00267     exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
00268                   new_cond, sel_node,
00269                   nth_table, op);
00270     if (exp) {
00271 
00272       return(exp);
00273     }
00274 
00275     new_cond = static_cast<func_node_t *>(que_node_get_next(new_cond));
00276 
00277     exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
00278                   new_cond, sel_node,
00279                   nth_table, op);
00280     return(exp);
00281   }
00282 
00283   exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
00284                 search_cond, sel_node,
00285                 nth_table, op);
00286   if (exp == NULL) {
00287 
00288     return(NULL);
00289   }
00290 
00291   /* If we will fetch in an ascending order, we cannot utilize an upper
00292   limit for a column value; in a descending order, respectively, a lower
00293   limit */
00294 
00295   if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {
00296 
00297     return(NULL);
00298 
00299   } else if (!sel_node->asc
00300        && ((*op == '>') || (*op == PARS_GE_TOKEN))) {
00301 
00302     return(NULL);
00303   }
00304 
00305   return(exp);
00306 }
00307 
00308 /*******************************************************************/
00316 static
00317 ulint
00318 opt_calc_index_goodness(
00319 /*====================*/
00320   dict_index_t* index,    
00321   sel_node_t* sel_node, 
00322   ulint   nth_table,  
00323   que_node_t**  index_plan, 
00325   ulint*    last_op)  
00327 {
00328   que_node_t* exp;
00329   ulint   goodness;
00330   ulint   n_fields;
00331   ulint   col_no;
00332   ulint   op= 0;
00333   ulint   j;
00334 
00335   goodness = 0;
00336 
00337   /* Note that as higher level node pointers in the B-tree contain
00338   page addresses as the last field, we must not put more fields in
00339   the search tuple than dict_index_get_n_unique_in_tree(index); see
00340   the note in btr_cur_search_to_nth_level. */
00341 
00342   n_fields = dict_index_get_n_unique_in_tree(index);
00343 
00344   for (j = 0; j < n_fields; j++) {
00345 
00346     col_no = dict_index_get_nth_col_no(index, j);
00347 
00348     exp = opt_look_for_col_in_cond_before(
00349       OPT_EQUAL, col_no,
00350                         static_cast<func_node_t *>(sel_node->search_cond),
00351       sel_node, nth_table, &op);
00352     if (exp) {
00353       /* The value for this column is exactly known already
00354       at this stage of the join */
00355 
00356       index_plan[j] = exp;
00357       *last_op = op;
00358       goodness += 4;
00359     } else {
00360       /* Look for non-equality comparisons */
00361 
00362       exp = opt_look_for_col_in_cond_before(
00363         OPT_COMPARISON, col_no, static_cast<func_node_t *>(sel_node->search_cond),
00364         sel_node, nth_table, &op);
00365       if (exp) {
00366         index_plan[j] = exp;
00367         *last_op = op;
00368         goodness += 2;
00369       }
00370 
00371       break;
00372     }
00373   }
00374 
00375   if (goodness >= 4 * dict_index_get_n_unique(index)) {
00376     goodness += 1024;
00377 
00378     if (dict_index_is_clust(index)) {
00379 
00380       goodness += 1024;
00381     }
00382   }
00383 
00384   /* We have to test for goodness here, as last_op may note be set */
00385   if (goodness && dict_index_is_clust(index)) {
00386 
00387     goodness++;
00388   }
00389 
00390   return(goodness);
00391 }
00392 
00393 /*******************************************************************/
00396 UNIV_INLINE
00397 ulint
00398 opt_calc_n_fields_from_goodness(
00399 /*============================*/
00400   ulint goodness) 
00401 {
00402   return(((goodness % 1024) + 2) / 4);
00403 }
00404 
00405 /*******************************************************************/
00409 UNIV_INLINE
00410 ulint
00411 opt_op_to_search_mode(
00412 /*==================*/
00413   ibool asc,  
00415   ulint op) 
00416 {
00417   if (op == '=') {
00418     if (asc) {
00419       return(PAGE_CUR_GE);
00420     } else {
00421       return(PAGE_CUR_LE);
00422     }
00423   } else if (op == '<') {
00424     ut_a(!asc);
00425     return(PAGE_CUR_L);
00426   } else if (op == '>') {
00427     ut_a(asc);
00428     return(PAGE_CUR_G);
00429   } else if (op == PARS_GE_TOKEN) {
00430     ut_a(asc);
00431     return(PAGE_CUR_GE);
00432   } else if (op == PARS_LE_TOKEN) {
00433     ut_a(!asc);
00434     return(PAGE_CUR_LE);
00435   } else {
00436     ut_error;
00437   }
00438 
00439   return(0);
00440 }
00441 
00442 /*******************************************************************/
00445 static
00446 ibool
00447 opt_is_arg(
00448 /*=======*/
00449   que_node_t* arg_node, 
00450   func_node_t*  func_node)  
00451 {
00452   que_node_t* arg;
00453 
00454   arg = func_node->args;
00455 
00456   while (arg) {
00457     if (arg == arg_node) {
00458 
00459       return(TRUE);
00460     }
00461 
00462     arg = que_node_get_next(arg);
00463   }
00464 
00465   return(FALSE);
00466 }
00467 
00468 /*******************************************************************/
00472 static
00473 void
00474 opt_check_order_by(
00475 /*===============*/
00476   sel_node_t* sel_node) 
00479 {
00480   order_node_t* order_node;
00481   dict_table_t* order_table;
00482   ulint   order_col_no;
00483   plan_t*   plan;
00484   ulint   i;
00485 
00486   if (!sel_node->order_by) {
00487 
00488     return;
00489   }
00490 
00491   order_node = sel_node->order_by;
00492   order_col_no = order_node->column->col_no;
00493   order_table = order_node->column->table;
00494 
00495   /* If there is an order-by clause, the first non-exactly matched field
00496   in the index used for the last table in the table list should be the
00497   column defined in the order-by clause, and for all the other tables
00498   we should get only at most a single row, otherwise we cannot presently
00499   calculate the order-by, as we have no sort utility */
00500 
00501   for (i = 0; i < sel_node->n_tables; i++) {
00502 
00503     plan = sel_node_get_nth_plan(sel_node, i);
00504 
00505     if (i < sel_node->n_tables - 1) {
00506       ut_a(dict_index_get_n_unique(plan->index)
00507            <= plan->n_exact_match);
00508     } else {
00509       ut_a(plan->table == order_table);
00510 
00511       ut_a((dict_index_get_n_unique(plan->index)
00512             <= plan->n_exact_match)
00513            || (dict_index_get_nth_col_no(plan->index,
00514                  plan->n_exact_match)
00515          == order_col_no));
00516     }
00517   }
00518 }
00519 
00520 /*******************************************************************/
00524 static
00525 void
00526 opt_search_plan_for_table(
00527 /*======================*/
00528   sel_node_t* sel_node, 
00529   ulint   i,    
00530   dict_table_t* table)    
00531 {
00532   plan_t*   plan;
00533   dict_index_t* index;
00534   dict_index_t* best_index;
00535   ulint   n_fields;
00536   ulint   goodness;
00537   ulint   last_op   = 75946965; /* Eliminate a Purify
00538               warning */
00539   ulint   best_goodness;
00540   ulint   best_last_op = 0; /* remove warning */
00541   que_node_t* index_plan[256];
00542   que_node_t* best_index_plan[256];
00543 
00544   plan = sel_node_get_nth_plan(sel_node, i);
00545 
00546   plan->table = table;
00547   plan->asc = sel_node->asc;
00548   plan->pcur_is_open = FALSE;
00549   plan->cursor_at_end = FALSE;
00550 
00551   /* Calculate goodness for each index of the table */
00552 
00553   index = dict_table_get_first_index(table);
00554   best_index = index; /* Eliminate compiler warning */
00555   best_goodness = 0;
00556 
00557   /* should be do ... until ? comment by Jani */
00558   while (index) {
00559     goodness = opt_calc_index_goodness(index, sel_node, i,
00560                index_plan, &last_op);
00561     if (goodness > best_goodness) {
00562 
00563       best_index = index;
00564       best_goodness = goodness;
00565       n_fields = opt_calc_n_fields_from_goodness(goodness);
00566 
00567       ut_memcpy(best_index_plan, index_plan,
00568           n_fields * sizeof(void*));
00569       best_last_op = last_op;
00570     }
00571 
00572     index = dict_table_get_next_index(index);
00573   }
00574 
00575   plan->index = best_index;
00576 
00577   n_fields = opt_calc_n_fields_from_goodness(best_goodness);
00578 
00579   if (n_fields == 0) {
00580     plan->tuple = NULL;
00581     plan->n_exact_match = 0;
00582   } else {
00583     plan->tuple = dtuple_create(pars_sym_tab_global->heap,
00584               n_fields);
00585     dict_index_copy_types(plan->tuple, plan->index, n_fields);
00586 
00587     plan->tuple_exps = static_cast<void **>(mem_heap_alloc(pars_sym_tab_global->heap,
00588               n_fields * sizeof(void*)));
00589 
00590     ut_memcpy(plan->tuple_exps, best_index_plan,
00591         n_fields * sizeof(void*));
00592     if (best_last_op == '=') {
00593       plan->n_exact_match = n_fields;
00594     } else {
00595       plan->n_exact_match = n_fields - 1;
00596     }
00597 
00598     plan->mode = opt_op_to_search_mode(sel_node->asc,
00599                best_last_op);
00600   }
00601 
00602   if (dict_index_is_clust(best_index)
00603       && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {
00604 
00605     plan->unique_search = TRUE;
00606   } else {
00607     plan->unique_search = FALSE;
00608   }
00609 
00610   plan->old_vers_heap = NULL;
00611 
00612   btr_pcur_init(&(plan->pcur));
00613   btr_pcur_init(&(plan->clust_pcur));
00614 }
00615 
00616 /*******************************************************************/
00622 static
00623 ulint
00624 opt_classify_comparison(
00625 /*====================*/
00626   sel_node_t* sel_node, 
00627   ulint   i,    
00628   func_node_t*  cond)   
00629 {
00630   plan_t* plan;
00631   ulint n_fields;
00632   ulint op;
00633   ulint j;
00634 
00635   ut_ad(cond && sel_node);
00636 
00637   plan = sel_node_get_nth_plan(sel_node, i);
00638 
00639   /* Check if the condition is determined after the ith table has been
00640   accessed, but not after the i - 1:th */
00641 
00642   if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {
00643 
00644     return(OPT_NOT_COND);
00645   }
00646 
00647   if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {
00648 
00649     return(OPT_NOT_COND);
00650   }
00651 
00652   /* If the condition is an exact match condition used in constructing
00653   the search tuple, it is classified as OPT_END_COND */
00654 
00655   if (plan->tuple) {
00656     n_fields = dtuple_get_n_fields(plan->tuple);
00657   } else {
00658     n_fields = 0;
00659   }
00660 
00661   for (j = 0; j < plan->n_exact_match; j++) {
00662 
00663     if (opt_is_arg(plan->tuple_exps[j], cond)) {
00664 
00665       return(OPT_END_COND);
00666     }
00667   }
00668 
00669   /* If the condition is an non-exact match condition used in
00670   constructing the search tuple, it is classified as OPT_SCROLL_COND.
00671   When the cursor is positioned, and if a non-scroll cursor is used,
00672   there is no need to test this condition; if a scroll cursor is used
00673   the testing is necessary when the cursor is reversed. */
00674 
00675   if ((n_fields > plan->n_exact_match)
00676       && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {
00677 
00678     return(OPT_SCROLL_COND);
00679   }
00680 
00681   /* If the condition is a non-exact match condition on the first field
00682   in index for which there is no exact match, and it limits the search
00683   range from the opposite side of the search tuple already BEFORE we
00684   access the table, it is classified as OPT_END_COND */
00685 
00686   if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
00687       && opt_look_for_col_in_comparison_before(
00688         OPT_COMPARISON,
00689         dict_index_get_nth_col_no(plan->index,
00690                 plan->n_exact_match),
00691         cond, sel_node, i, &op)) {
00692 
00693     if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {
00694 
00695       return(OPT_END_COND);
00696     }
00697 
00698     if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {
00699 
00700       return(OPT_END_COND);
00701     }
00702   }
00703 
00704   /* Otherwise, cond is classified as OPT_TEST_COND */
00705 
00706   return(OPT_TEST_COND);
00707 }
00708 
00709 /*******************************************************************/
00711 static
00712 void
00713 opt_find_test_conds(
00714 /*================*/
00715   sel_node_t* sel_node, 
00716   ulint   i,    
00717   func_node_t*  cond)   
00719 {
00720   func_node_t*  new_cond;
00721   ulint   func_class;
00722   plan_t*   plan;
00723 
00724   if (cond == NULL) {
00725 
00726     return;
00727   }
00728 
00729   if (cond->func == PARS_AND_TOKEN) {
00730     new_cond = static_cast<func_node_t *>(cond->args);
00731 
00732     opt_find_test_conds(sel_node, i, new_cond);
00733 
00734     new_cond = static_cast<func_node_t *>(que_node_get_next(new_cond));
00735 
00736     opt_find_test_conds(sel_node, i, new_cond);
00737 
00738     return;
00739   }
00740 
00741   plan = sel_node_get_nth_plan(sel_node, i);
00742 
00743   func_class = opt_classify_comparison(sel_node, i, cond);
00744 
00745   if (func_class == OPT_END_COND) {
00746     UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond);
00747 
00748   } else if (func_class == OPT_TEST_COND) {
00749     UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond);
00750 
00751   }
00752 }
00753 
00754 /*******************************************************************/
00758 static
00759 void
00760 opt_normalize_cmp_conds(
00761 /*====================*/
00762   func_node_t*  cond, 
00764   dict_table_t* table)  
00765 {
00766   que_node_t* arg1;
00767   que_node_t* arg2;
00768   sym_node_t* sym_node;
00769 
00770   while (cond) {
00771     arg1 = cond->args;
00772     arg2 = que_node_get_next(arg1);
00773 
00774     if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {
00775 
00776       sym_node = static_cast<sym_node_t *>(arg2);
00777 
00778       if ((sym_node->token_type == SYM_COLUMN)
00779           && (sym_node->table == table)) {
00780 
00781         /* Switch the order of the arguments */
00782 
00783         cond->args = arg2;
00784         que_node_list_add_last(NULL, arg2);
00785         que_node_list_add_last(arg2, arg1);
00786 
00787         /* Invert the operator */
00788         cond->func = opt_invert_cmp_op(cond->func);
00789       }
00790     }
00791 
00792     cond = UT_LIST_GET_NEXT(cond_list, cond);
00793   }
00794 }
00795 
00796 /*******************************************************************/
00800 static
00801 void
00802 opt_determine_and_normalize_test_conds(
00803 /*===================================*/
00804   sel_node_t* sel_node, 
00805   ulint   i)    
00806 {
00807   plan_t* plan;
00808 
00809   plan = sel_node_get_nth_plan(sel_node, i);
00810 
00811   UT_LIST_INIT(plan->end_conds);
00812   UT_LIST_INIT(plan->other_conds);
00813 
00814   /* Recursively go through the conjuncts and classify them */
00815 
00816   opt_find_test_conds(sel_node, i, static_cast<func_node_t *>(sel_node->search_cond));
00817 
00818   opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
00819         plan->table);
00820 
00821   ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
00822 }
00823 
00824 /*******************************************************************/
00831 UNIV_INTERN
00832 void
00833 opt_find_all_cols(
00834 /*==============*/
00835   ibool   copy_val, 
00837   dict_index_t* index,    
00838   sym_node_list_t* col_list,  
00840   plan_t*   plan,   
00841   que_node_t* exp)    
00843 {
00844   func_node_t*  func_node;
00845   que_node_t* arg;
00846   sym_node_t* sym_node;
00847   sym_node_t* col_node;
00848   ulint   col_pos;
00849 
00850   if (exp == NULL) {
00851 
00852     return;
00853   }
00854 
00855   if (que_node_get_type(exp) == QUE_NODE_FUNC) {
00856     func_node = static_cast<func_node_t *>(exp);
00857 
00858     arg = func_node->args;
00859 
00860     while (arg) {
00861       opt_find_all_cols(copy_val, index, col_list, plan,
00862             arg);
00863       arg = que_node_get_next(arg);
00864     }
00865 
00866     return;
00867   }
00868 
00869   ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);
00870 
00871   sym_node = static_cast<sym_node_t *>(exp);
00872 
00873   if (sym_node->token_type != SYM_COLUMN) {
00874 
00875     return;
00876   }
00877 
00878   if (sym_node->table != index->table) {
00879 
00880     return;
00881   }
00882 
00883   /* Look for an occurrence of the same column in the plan column
00884   list */
00885 
00886   col_node = UT_LIST_GET_FIRST(*col_list);
00887 
00888   while (col_node) {
00889     if (col_node->col_no == sym_node->col_no) {
00890 
00891       if (col_node == sym_node) {
00892         /* sym_node was already in a list: do
00893         nothing */
00894 
00895         return;
00896       }
00897 
00898       /* Put an indirection */
00899       sym_node->indirection = col_node;
00900       sym_node->alias = col_node;
00901 
00902       return;
00903     }
00904 
00905     col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
00906   }
00907 
00908   /* The same column did not occur in the list: add it */
00909 
00910   UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node);
00911 
00912   sym_node->copy_val = copy_val;
00913 
00914   /* Fill in the field_no fields in sym_node */
00915 
00916   sym_node->field_nos[SYM_CLUST_FIELD_NO] = dict_index_get_nth_col_pos(
00917     dict_table_get_first_index(index->table), sym_node->col_no);
00918   if (!dict_index_is_clust(index)) {
00919 
00920     ut_a(plan);
00921 
00922     col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no);
00923 
00924     if (col_pos == ULINT_UNDEFINED) {
00925 
00926       plan->must_get_clust = TRUE;
00927     }
00928 
00929     sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
00930   }
00931 }
00932 
00933 /*******************************************************************/
00938 static
00939 void
00940 opt_find_copy_cols(
00941 /*===============*/
00942   sel_node_t* sel_node, 
00943   ulint   i,    
00944   func_node_t*  search_cond)  
00945 {
00946   func_node_t*  new_cond;
00947   plan_t*   plan;
00948 
00949   if (search_cond == NULL) {
00950 
00951     return;
00952   }
00953 
00954   ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);
00955 
00956   if (search_cond->func == PARS_AND_TOKEN) {
00957     new_cond = static_cast<func_node_t *>(search_cond->args);
00958 
00959     opt_find_copy_cols(sel_node, i, new_cond);
00960 
00961     new_cond = static_cast<func_node_t *>(que_node_get_next(new_cond));
00962 
00963     opt_find_copy_cols(sel_node, i, new_cond);
00964 
00965     return;
00966   }
00967 
00968   if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {
00969 
00970     /* Any ith table columns occurring in search_cond should be
00971     copied, as this condition cannot be tested already on the
00972     fetch from the ith table */
00973 
00974     plan = sel_node_get_nth_plan(sel_node, i);
00975 
00976     opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
00977           search_cond);
00978   }
00979 }
00980 
00981 /*******************************************************************/
00986 static
00987 void
00988 opt_classify_cols(
00989 /*==============*/
00990   sel_node_t* sel_node, 
00991   ulint   i)    
00992 {
00993   plan_t*   plan;
00994   que_node_t* exp;
00995 
00996   plan = sel_node_get_nth_plan(sel_node, i);
00997 
00998   /* The final value of the following field will depend on the
00999   environment of the select statement: */
01000 
01001   plan->must_get_clust = FALSE;
01002 
01003   UT_LIST_INIT(plan->columns);
01004 
01005   /* All select list columns should be copied: therefore TRUE as the
01006   first argument */
01007 
01008   exp = sel_node->select_list;
01009 
01010   while (exp) {
01011     opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
01012           exp);
01013     exp = que_node_get_next(exp);
01014   }
01015 
01016   opt_find_copy_cols(sel_node, i, static_cast<func_node_t *>(sel_node->search_cond));
01017 
01018   /* All remaining columns in the search condition are temporary
01019   columns: therefore FALSE */
01020 
01021   opt_find_all_cols(FALSE, plan->index, &(plan->columns), plan,
01022         sel_node->search_cond);
01023 }
01024 
01025 /*******************************************************************/
01028 static
01029 void
01030 opt_clust_access(
01031 /*=============*/
01032   sel_node_t* sel_node, 
01033   ulint   n)    
01034 {
01035   plan_t*   plan;
01036   dict_table_t* table;
01037   dict_index_t* clust_index;
01038   dict_index_t* index;
01039   mem_heap_t* heap;
01040   ulint   n_fields;
01041   ulint   pos;
01042   ulint   i;
01043 
01044   plan = sel_node_get_nth_plan(sel_node, n);
01045 
01046   index = plan->index;
01047 
01048   /* The final value of the following field depends on the environment
01049   of the select statement: */
01050 
01051   plan->no_prefetch = FALSE;
01052 
01053   if (dict_index_is_clust(index)) {
01054     plan->clust_map = NULL;
01055     plan->clust_ref = NULL;
01056 
01057     return;
01058   }
01059 
01060   table = index->table;
01061 
01062   clust_index = dict_table_get_first_index(table);
01063 
01064   n_fields = dict_index_get_n_unique(clust_index);
01065 
01066   heap = pars_sym_tab_global->heap;
01067 
01068   plan->clust_ref = dtuple_create(heap, n_fields);
01069 
01070   dict_index_copy_types(plan->clust_ref, clust_index, n_fields);
01071 
01072   plan->clust_map = static_cast<unsigned long *>(mem_heap_alloc(heap, n_fields * sizeof(ulint)));
01073 
01074   for (i = 0; i < n_fields; i++) {
01075     pos = dict_index_get_nth_field_pos(index, clust_index, i);
01076 
01077     ut_a(pos != ULINT_UNDEFINED);
01078 
01079     /* We optimize here only queries to InnoDB's internal system
01080     tables, and they should not contain column prefix indexes. */
01081 
01082     if (dict_index_get_nth_field(index, pos)->prefix_len != 0
01083         || dict_index_get_nth_field(clust_index, i)
01084         ->prefix_len != 0) {
01085       fprintf(stderr,
01086         "InnoDB: Error in pars0opt.c:"
01087         " table %s has prefix_len != 0\n",
01088         index->table_name);
01089     }
01090 
01091     *(plan->clust_map + i) = pos;
01092 
01093     ut_ad(pos != ULINT_UNDEFINED);
01094   }
01095 }
01096 
01097 /*******************************************************************/
01101 UNIV_INTERN
01102 void
01103 opt_search_plan(
01104 /*============*/
01105   sel_node_t* sel_node) 
01106 {
01107   sym_node_t* table_node;
01108   dict_table_t* table;
01109   order_node_t* order_by;
01110   ulint   i;
01111 
01112   sel_node->plans = static_cast<plan_t *>(mem_heap_alloc(pars_sym_tab_global->heap,
01113            sel_node->n_tables * sizeof(plan_t)));
01114 
01115   /* Analyze the search condition to find out what we know at each
01116   join stage about the conditions that the columns of a table should
01117   satisfy */
01118 
01119   table_node = sel_node->table_list;
01120 
01121   if (sel_node->order_by == NULL) {
01122     sel_node->asc = TRUE;
01123   } else {
01124     order_by = sel_node->order_by;
01125 
01126     sel_node->asc = order_by->asc;
01127   }
01128 
01129   for (i = 0; i < sel_node->n_tables; i++) {
01130 
01131     table = table_node->table;
01132 
01133     /* Choose index through which to access the table */
01134 
01135     opt_search_plan_for_table(sel_node, i, table);
01136 
01137     /* Determine the search condition conjuncts we can test at
01138     this table; normalize the end conditions */
01139 
01140     opt_determine_and_normalize_test_conds(sel_node, i);
01141 
01142     table_node = static_cast<sym_node_t *>(que_node_get_next(table_node));
01143   }
01144 
01145   table_node = sel_node->table_list;
01146 
01147   for (i = 0; i < sel_node->n_tables; i++) {
01148 
01149     /* Classify the table columns into those we only need to access
01150     but not copy, and to those we must copy to dynamic memory */
01151 
01152     opt_classify_cols(sel_node, i);
01153 
01154     /* Calculate possible info for accessing the clustered index
01155     record */
01156 
01157     opt_clust_access(sel_node, i);
01158 
01159     table_node = static_cast<sym_node_t *>(que_node_get_next(table_node));
01160   }
01161 
01162   /* Check that the plan obeys a possible order-by clause: if not,
01163   an assertion error occurs */
01164 
01165   opt_check_order_by(sel_node);
01166 
01167 #ifdef UNIV_SQL_DEBUG
01168   opt_print_query_plan(sel_node);
01169 #endif
01170 }
01171 
01172 /********************************************************************/
01174 UNIV_INTERN
01175 void
01176 opt_print_query_plan(
01177 /*=================*/
01178   sel_node_t* sel_node) 
01179 {
01180   plan_t* plan;
01181   ulint n_fields;
01182   ulint i;
01183 
01184   fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);
01185 
01186   fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);
01187 
01188   if (sel_node->set_x_locks) {
01189     fputs("sets row x-locks; ", stderr);
01190     ut_a(sel_node->row_lock_mode == LOCK_X);
01191     ut_a(!sel_node->consistent_read);
01192   } else if (sel_node->consistent_read) {
01193     fputs("consistent read; ", stderr);
01194   } else {
01195     ut_a(sel_node->row_lock_mode == LOCK_S);
01196     fputs("sets row s-locks; ", stderr);
01197   }
01198 
01199   putc('\n', stderr);
01200 
01201   for (i = 0; i < sel_node->n_tables; i++) {
01202     plan = sel_node_get_nth_plan(sel_node, i);
01203 
01204     if (plan->tuple) {
01205       n_fields = dtuple_get_n_fields(plan->tuple);
01206     } else {
01207       n_fields = 0;
01208     }
01209 
01210     fputs("Table ", stderr);
01211     dict_index_name_print(stderr, NULL, plan->index);
01212     fprintf(stderr,"; exact m. %lu, match %lu, end conds %lu\n",
01213       (unsigned long) plan->n_exact_match,
01214       (unsigned long) n_fields,
01215       (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
01216   }
01217 }