pars0opt.cc

Go to the documentation of this file.

/*****************************************************************************

Copyright (c) 1997, 2011, Oracle and/or its affiliates. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free Software
Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with
this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Suite 500, Boston, MA 02110-1335 USA

*****************************************************************************/

/**************************************************/
#include "pars0opt.h"

#ifdef UNIV_NONINL
#include "pars0opt.ic"
#endif

#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"

#define OPT_EQUAL       1       /* comparison by = */
#define OPT_COMPARISON  2       /* comparison by <, >, <=, or >= */

#define OPT_NOT_COND    1
#define OPT_END_COND    2
#define OPT_TEST_COND   3
#define OPT_SCROLL_COND 4


/*******************************************************************/
static
int
opt_invert_cmp_op(
/*==============*/
        int     op)     
{
        if (op == '<') {
                return('>');
        } else if (op == '>') {
                return('<');
        } else if (op == '=') {
                return('=');
        } else if (op == PARS_LE_TOKEN) {
                return(PARS_GE_TOKEN);
        } else if (op == PARS_GE_TOKEN) {
                return(PARS_LE_TOKEN);
        } else {
                /* TODO: LIKE operator */
                ut_error;
        }

        return(0);
}

/*******************************************************************/
static
ibool
opt_check_exp_determined_before(
/*============================*/
        que_node_t*     exp,            
        sel_node_t*     sel_node,       
        ulint           nth_table)      
{
        func_node_t*    func_node;
        sym_node_t*     sym_node;
        dict_table_t*   table;
        que_node_t*     arg;
        ulint           i;

        ut_ad(exp && sel_node);

        if (que_node_get_type(exp) == QUE_NODE_FUNC) {
                func_node = static_cast<func_node_t*>(exp);

                arg = func_node->args;

                while (arg) {
                        if (!opt_check_exp_determined_before(arg, sel_node,
                                                             nth_table)) {
                                return(FALSE);
                        }

                        arg = que_node_get_next(arg);
                }

                return(TRUE);
        }

        ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);

        sym_node = static_cast<sym_node_t*>(exp);

        if (sym_node->token_type != SYM_COLUMN) {

                return(TRUE);
        }

        for (i = 0; i < nth_table; i++) {

                table = sel_node_get_nth_plan(sel_node, i)->table;

                if (sym_node->table == table) {

                        return(TRUE);
                }
        }

        return(FALSE);
}

/*******************************************************************/
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)             
{
        sym_node_t*     sym_node;
        dict_table_t*   table;
        que_node_t*     exp;
        que_node_t*     arg;

        ut_ad(search_cond);

        ut_a((search_cond->func == '<')
             || (search_cond->func == '>')
             || (search_cond->func == '=')
             || (search_cond->func == PARS_GE_TOKEN)
             || (search_cond->func == PARS_LE_TOKEN)
             || (search_cond->func == PARS_LIKE_TOKEN_EXACT)
             || (search_cond->func == PARS_LIKE_TOKEN_PREFIX)
             || (search_cond->func == PARS_LIKE_TOKEN_SUFFIX)
             || (search_cond->func == PARS_LIKE_TOKEN_SUBSTR));

        table = sel_node_get_nth_plan(sel_node, nth_table)->table;

        if ((cmp_type == OPT_EQUAL)
            && (search_cond->func != '=')
            && (search_cond->func != PARS_LIKE_TOKEN_EXACT)
            && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)) {

                return(NULL);

        } else if ((cmp_type == OPT_COMPARISON)
                   && (search_cond->func != '<')
                   && (search_cond->func != '>')
                   && (search_cond->func != PARS_GE_TOKEN)
                   && (search_cond->func != PARS_LE_TOKEN)
                   && (search_cond->func != PARS_LIKE_TOKEN_PREFIX)
                   && (search_cond->func != PARS_LIKE_TOKEN_SUFFIX)) {

                return(NULL);
        }

        arg = search_cond->args;

        if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
                sym_node = static_cast<sym_node_t*>(arg);

                if ((sym_node->token_type == SYM_COLUMN)
                    && (sym_node->table == table)
                    && (sym_node->col_no == col_no)) {

                        /* sym_node contains the desired column id */

                        /* Check if the expression on the right side of the
                        operator is already determined */

                        exp = que_node_get_next(arg);

                        if (opt_check_exp_determined_before(exp, sel_node,
                                                            nth_table)) {
                                *op = search_cond->func;

                                return(exp);
                        }
                }
        }

        exp = search_cond->args;
        arg = que_node_get_next(arg);

        if (que_node_get_type(arg) == QUE_NODE_SYMBOL) {
                sym_node = static_cast<sym_node_t*>(arg);

                if ((sym_node->token_type == SYM_COLUMN)
                    && (sym_node->table == table)
                    && (sym_node->col_no == col_no)) {

                        if (opt_check_exp_determined_before(exp, sel_node,
                                                            nth_table)) {
                                *op = opt_invert_cmp_op(search_cond->func);

                                return(exp);
                        }
                }
        }

        return(NULL);
}

/*******************************************************************/
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)             
{
        func_node_t*    new_cond;
        que_node_t*     exp;

        if (search_cond == NULL) {

                return(NULL);
        }

        ut_a(que_node_get_type(search_cond) == QUE_NODE_FUNC);
        ut_a(search_cond->func != PARS_OR_TOKEN);
        ut_a(search_cond->func != PARS_NOT_TOKEN);

        if (search_cond->func == PARS_AND_TOKEN) {
                new_cond = static_cast<func_node_t*>(search_cond->args);

                exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
                                                      new_cond, sel_node,
                                                      nth_table, op);
                if (exp) {

                        return(exp);
                }

                new_cond = static_cast<func_node_t*>(
                        que_node_get_next(new_cond));

                exp = opt_look_for_col_in_cond_before(cmp_type, col_no,
                                                      new_cond, sel_node,
                                                      nth_table, op);
                return(exp);
        }

        exp = opt_look_for_col_in_comparison_before(cmp_type, col_no,
                                                    search_cond, sel_node,
                                                    nth_table, op);
        if (exp == NULL) {

                return(NULL);
        }

        /* If we will fetch in an ascending order, we cannot utilize an upper
        limit for a column value; in a descending order, respectively, a lower
        limit */

        if (sel_node->asc && ((*op == '<') || (*op == PARS_LE_TOKEN))) {

                return(NULL);

        } else if (!sel_node->asc
                   && ((*op == '>') || (*op == PARS_GE_TOKEN))) {

                return(NULL);
        }

        return(exp);
}

/*******************************************************************/
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)        
{
        que_node_t*     exp;
        ulint           goodness;
        ulint           n_fields;
        ulint           col_no;
        ulint           op;
        ulint           j;

        /* At least for now we don't support using FTS indexes for queries
        done through InnoDB's own SQL parser. */
        if (dict_index_is_online_ddl(index) || (index->type & DICT_FTS)) {
                return(0);
        }

        goodness = 0;

        /* Note that as higher level node pointers in the B-tree contain
        page addresses as the last field, we must not put more fields in
        the search tuple than dict_index_get_n_unique_in_tree(index); see
        the note in btr_cur_search_to_nth_level. */

        n_fields = dict_index_get_n_unique_in_tree(index);

        for (j = 0; j < n_fields; j++) {

                col_no = dict_index_get_nth_col_no(index, j);

                exp = opt_look_for_col_in_cond_before(
                        OPT_EQUAL, col_no,
                        static_cast<func_node_t*>(sel_node->search_cond),
                        sel_node, nth_table, &op);
                if (exp) {
                        /* The value for this column is exactly known already
                        at this stage of the join */

                        index_plan[j] = exp;
                        *last_op = op;
                        goodness += 4;
                } else {
                        /* Look for non-equality comparisons */

                        exp = opt_look_for_col_in_cond_before(
                                OPT_COMPARISON, col_no,
                                static_cast<func_node_t*>(
                                        sel_node->search_cond),
                                sel_node, nth_table, &op);
                        if (exp) {
                                index_plan[j] = exp;
                                *last_op = op;
                                goodness += 2;
                        }

                        break;
                }
        }

        if (goodness >= 4 * dict_index_get_n_unique(index)) {
                goodness += 1024;

                if (dict_index_is_clust(index)) {

                        goodness += 1024;
                }
        }

        /* We have to test for goodness here, as last_op may not be set */
        if (goodness && dict_index_is_clust(index)) {

                goodness++;
        }

        return(goodness);
}

/*******************************************************************/
UNIV_INLINE
ulint
opt_calc_n_fields_from_goodness(
/*============================*/
        ulint   goodness)       
{
        return(((goodness % 1024) + 2) / 4);
}

/*******************************************************************/
UNIV_INLINE
ulint
opt_op_to_search_mode(
/*==================*/
        ibool   asc,    
        ulint   op)     
{
        if (op == '='
            || op == PARS_LIKE_TOKEN_EXACT
            || op == PARS_LIKE_TOKEN_PREFIX
            || op == PARS_LIKE_TOKEN_SUFFIX
            || op == PARS_LIKE_TOKEN_SUBSTR) {

                if (asc) {
                        return(PAGE_CUR_GE);
                } else {
                        return(PAGE_CUR_LE);
                }
        } else if (op == '<') {
                ut_a(!asc);
                return(PAGE_CUR_L);
        } else if (op == '>') {
                ut_a(asc);
                return(PAGE_CUR_G);
        } else if (op == PARS_GE_TOKEN) {
                ut_a(asc);
                return(PAGE_CUR_GE);
        } else if (op == PARS_LE_TOKEN) {
                ut_a(!asc);
                return(PAGE_CUR_LE);
        } else {
                ut_error;
        }

        return(0);
}

/*******************************************************************/
static
ibool
opt_is_arg(
/*=======*/
        que_node_t*     arg_node,       
        func_node_t*    func_node)      
{
        que_node_t*     arg;

        arg = func_node->args;

        while (arg) {
                if (arg == arg_node) {

                        return(TRUE);
                }

                arg = que_node_get_next(arg);
        }

        return(FALSE);
}

/*******************************************************************/
static
void
opt_check_order_by(
/*===============*/
        sel_node_t*     sel_node)       
{
        order_node_t*   order_node;
        dict_table_t*   order_table;
        ulint           order_col_no;
        plan_t*         plan;
        ulint           i;

        if (!sel_node->order_by) {

                return;
        }

        order_node = sel_node->order_by;
        order_col_no = order_node->column->col_no;
        order_table = order_node->column->table;

        /* If there is an order-by clause, the first non-exactly matched field
        in the index used for the last table in the table list should be the
        column defined in the order-by clause, and for all the other tables
        we should get only at most a single row, otherwise we cannot presently
        calculate the order-by, as we have no sort utility */

        for (i = 0; i < sel_node->n_tables; i++) {

                plan = sel_node_get_nth_plan(sel_node, i);

                if (i < sel_node->n_tables - 1) {
                        ut_a(dict_index_get_n_unique(plan->index)
                             <= plan->n_exact_match);
                } else {
                        ut_a(plan->table == order_table);

                        ut_a((dict_index_get_n_unique(plan->index)
                              <= plan->n_exact_match)
                             || (dict_index_get_nth_col_no(plan->index,
                                                           plan->n_exact_match)
                                 == order_col_no));
                }
        }
}

/*******************************************************************/
static
void
opt_search_plan_for_table(
/*======================*/
        sel_node_t*     sel_node,       
        ulint           i,              
        dict_table_t*   table)          
{
        plan_t*         plan;
        dict_index_t*   index;
        dict_index_t*   best_index;
        ulint           n_fields;
        ulint           goodness;
        ulint           last_op         = 75946965;     /* Eliminate a Purify
                                                        warning */
        ulint           best_goodness;
        ulint           best_last_op = 0; /* remove warning */
        que_node_t*     index_plan[256];
        que_node_t*     best_index_plan[256];

        plan = sel_node_get_nth_plan(sel_node, i);

        plan->table = table;
        plan->asc = sel_node->asc;
        plan->pcur_is_open = FALSE;
        plan->cursor_at_end = FALSE;

        /* Calculate goodness for each index of the table */

        index = dict_table_get_first_index(table);
        best_index = index; /* Eliminate compiler warning */
        best_goodness = 0;

        /* should be do ... until ? comment by Jani */
        while (index) {
                goodness = opt_calc_index_goodness(index, sel_node, i,
                                                   index_plan, &last_op);
                if (goodness > best_goodness) {

                        best_index = index;
                        best_goodness = goodness;
                        n_fields = opt_calc_n_fields_from_goodness(goodness);

                        ut_memcpy(best_index_plan, index_plan,
                                  n_fields * sizeof(void*));
                        best_last_op = last_op;
                }

                dict_table_next_uncorrupted_index(index);
        }

        plan->index = best_index;

        n_fields = opt_calc_n_fields_from_goodness(best_goodness);

        if (n_fields == 0) {
                plan->tuple = NULL;
                plan->n_exact_match = 0;
        } else {
                plan->tuple = dtuple_create(pars_sym_tab_global->heap,
                                            n_fields);
                dict_index_copy_types(plan->tuple, plan->index, n_fields);

                plan->tuple_exps = static_cast<que_node_t**>(
                        mem_heap_alloc(
                                pars_sym_tab_global->heap,
                                n_fields * sizeof(void*)));

                ut_memcpy(plan->tuple_exps, best_index_plan,
                          n_fields * sizeof(void*));
                if (best_last_op == '='
                    || best_last_op == PARS_LIKE_TOKEN_EXACT
                    || best_last_op == PARS_LIKE_TOKEN_PREFIX
                    || best_last_op == PARS_LIKE_TOKEN_SUFFIX
                    || best_last_op == PARS_LIKE_TOKEN_SUBSTR) {
                        plan->n_exact_match = n_fields;
                } else {
                        plan->n_exact_match = n_fields - 1;
                }

                plan->mode = opt_op_to_search_mode(sel_node->asc,
                                                   best_last_op);
        }

        if (dict_index_is_clust(best_index)
            && (plan->n_exact_match >= dict_index_get_n_unique(best_index))) {

                plan->unique_search = TRUE;
        } else {
                plan->unique_search = FALSE;
        }

        plan->old_vers_heap = NULL;

        btr_pcur_init(&(plan->pcur));
        btr_pcur_init(&(plan->clust_pcur));
}

/*******************************************************************/
static
ulint
opt_classify_comparison(
/*====================*/
        sel_node_t*     sel_node,       
        ulint           i,              
        func_node_t*    cond)           
{
        plan_t* plan;
        ulint   n_fields;
        ulint   op;
        ulint   j;

        ut_ad(cond && sel_node);

        plan = sel_node_get_nth_plan(sel_node, i);

        /* Check if the condition is determined after the ith table has been
        accessed, but not after the i - 1:th */

        if (!opt_check_exp_determined_before(cond, sel_node, i + 1)) {

                return(OPT_NOT_COND);
        }

        if ((i > 0) && opt_check_exp_determined_before(cond, sel_node, i)) {

                return(OPT_NOT_COND);
        }

        /* If the condition is an exact match condition used in constructing
        the search tuple, it is classified as OPT_END_COND */

        if (plan->tuple) {
                n_fields = dtuple_get_n_fields(plan->tuple);
        } else {
                n_fields = 0;
        }

        for (j = 0; j < plan->n_exact_match; j++) {

                if (opt_is_arg(plan->tuple_exps[j], cond)) {

                        return(OPT_END_COND);
                }
        }

        /* If the condition is an non-exact match condition used in
        constructing the search tuple, it is classified as OPT_SCROLL_COND.
        When the cursor is positioned, and if a non-scroll cursor is used,
        there is no need to test this condition; if a scroll cursor is used
        the testing is necessary when the cursor is reversed. */

        if ((n_fields > plan->n_exact_match)
            && opt_is_arg(plan->tuple_exps[n_fields - 1], cond)) {

                return(OPT_SCROLL_COND);
        }

        /* If the condition is a non-exact match condition on the first field
        in index for which there is no exact match, and it limits the search
        range from the opposite side of the search tuple already BEFORE we
        access the table, it is classified as OPT_END_COND */

        if ((dict_index_get_n_fields(plan->index) > plan->n_exact_match)
            && opt_look_for_col_in_comparison_before(
                    OPT_COMPARISON,
                    dict_index_get_nth_col_no(plan->index,
                                              plan->n_exact_match),
                    cond, sel_node, i, &op)) {

                if (sel_node->asc && ((op == '<') || (op == PARS_LE_TOKEN))) {

                        return(OPT_END_COND);
                }

                if (!sel_node->asc && ((op == '>') || (op == PARS_GE_TOKEN))) {

                        return(OPT_END_COND);
                }
        }

        /* Otherwise, cond is classified as OPT_TEST_COND */

        return(OPT_TEST_COND);
}

/*******************************************************************/
static
void
opt_find_test_conds(
/*================*/
        sel_node_t*     sel_node,       
        ulint           i,              
        func_node_t*    cond)           
{
        func_node_t*    new_cond;
        ulint           fclass;
        plan_t*         plan;

        if (cond == NULL) {

                return;
        }

        if (cond->func == PARS_AND_TOKEN) {
                new_cond = static_cast<func_node_t*>(cond->args);

                opt_find_test_conds(sel_node, i, new_cond);

                new_cond = static_cast<func_node_t*>(
                        que_node_get_next(new_cond));

                opt_find_test_conds(sel_node, i, new_cond);

                return;
        }

        plan = sel_node_get_nth_plan(sel_node, i);

        fclass = opt_classify_comparison(sel_node, i, cond);

        if (fclass == OPT_END_COND) {
                UT_LIST_ADD_LAST(cond_list, plan->end_conds, cond);

        } else if (fclass == OPT_TEST_COND) {
                UT_LIST_ADD_LAST(cond_list, plan->other_conds, cond);

        }
}

/*******************************************************************/
static
void
opt_normalize_cmp_conds(
/*====================*/
        func_node_t*    cond,   
        dict_table_t*   table)  
{
        que_node_t*     arg1;
        que_node_t*     arg2;
        sym_node_t*     sym_node;

        while (cond) {
                arg1 = cond->args;
                arg2 = que_node_get_next(arg1);

                if (que_node_get_type(arg2) == QUE_NODE_SYMBOL) {

                        sym_node = static_cast<sym_node_t*>(arg2);

                        if ((sym_node->token_type == SYM_COLUMN)
                            && (sym_node->table == table)) {

                                /* Switch the order of the arguments */

                                cond->args = arg2;
                                que_node_list_add_last(NULL, arg2);
                                que_node_list_add_last(arg2, arg1);

                                /* Invert the operator */
                                cond->func = opt_invert_cmp_op(cond->func);
                        }
                }

                cond = UT_LIST_GET_NEXT(cond_list, cond);
        }
}

/*******************************************************************/
static
void
opt_determine_and_normalize_test_conds(
/*===================================*/
        sel_node_t*     sel_node,       
        ulint           i)              
{
        plan_t* plan;

        plan = sel_node_get_nth_plan(sel_node, i);

        UT_LIST_INIT(plan->end_conds);
        UT_LIST_INIT(plan->other_conds);

        /* Recursively go through the conjuncts and classify them */

        opt_find_test_conds(
                sel_node,
                i,
                static_cast<func_node_t*>(sel_node->search_cond));

        opt_normalize_cmp_conds(UT_LIST_GET_FIRST(plan->end_conds),
                                plan->table);

        ut_a(UT_LIST_GET_LEN(plan->end_conds) >= plan->n_exact_match);
}

/*******************************************************************/
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)            
{
        func_node_t*    func_node;
        que_node_t*     arg;
        sym_node_t*     sym_node;
        sym_node_t*     col_node;
        ulint           col_pos;

        if (exp == NULL) {

                return;
        }

        if (que_node_get_type(exp) == QUE_NODE_FUNC) {
                func_node = static_cast<func_node_t*>(exp);

                for (arg = func_node->args;
                     arg != 0;
                     arg = que_node_get_next(arg)) {

                        opt_find_all_cols(
                                copy_val, index, col_list, plan, arg);
                }

                return;
        }

        ut_a(que_node_get_type(exp) == QUE_NODE_SYMBOL);

        sym_node = static_cast<sym_node_t*>(exp);

        if (sym_node->token_type != SYM_COLUMN) {

                return;
        }

        if (sym_node->table != index->table) {

                return;
        }

        /* Look for an occurrence of the same column in the plan column
        list */

        col_node = UT_LIST_GET_FIRST(*col_list);

        while (col_node) {
                if (col_node->col_no == sym_node->col_no) {

                        if (col_node == sym_node) {
                                /* sym_node was already in a list: do
                                nothing */

                                return;
                        }

                        /* Put an indirection */
                        sym_node->indirection = col_node;
                        sym_node->alias = col_node;

                        return;
                }

                col_node = UT_LIST_GET_NEXT(col_var_list, col_node);
        }

        /* The same column did not occur in the list: add it */

        UT_LIST_ADD_LAST(col_var_list, *col_list, sym_node);

        sym_node->copy_val = copy_val;

        /* Fill in the field_no fields in sym_node */

        sym_node->field_nos[SYM_CLUST_FIELD_NO] = dict_index_get_nth_col_pos(
                dict_table_get_first_index(index->table), sym_node->col_no);
        if (!dict_index_is_clust(index)) {

                ut_a(plan);

                col_pos = dict_index_get_nth_col_pos(index, sym_node->col_no);

                if (col_pos == ULINT_UNDEFINED) {

                        plan->must_get_clust = TRUE;
                }

                sym_node->field_nos[SYM_SEC_FIELD_NO] = col_pos;
        }
}

/*******************************************************************/
static
void
opt_find_copy_cols(
/*===============*/
        sel_node_t*     sel_node,       
        ulint           i,              
        func_node_t*    search_cond)    
{
        func_node_t*    new_cond;
        plan_t*         plan;

        if (search_cond == NULL) {

                return;
        }

        ut_ad(que_node_get_type(search_cond) == QUE_NODE_FUNC);

        if (search_cond->func == PARS_AND_TOKEN) {
                new_cond = static_cast<func_node_t*>(search_cond->args);

                opt_find_copy_cols(sel_node, i, new_cond);

                new_cond = static_cast<func_node_t*>(
                        que_node_get_next(new_cond));

                opt_find_copy_cols(sel_node, i, new_cond);

                return;
        }

        if (!opt_check_exp_determined_before(search_cond, sel_node, i + 1)) {

                /* Any ith table columns occurring in search_cond should be
                copied, as this condition cannot be tested already on the
                fetch from the ith table */

                plan = sel_node_get_nth_plan(sel_node, i);

                opt_find_all_cols(TRUE, plan->index, &(plan->columns), plan,
                                  search_cond);
        }
}

/*******************************************************************/
static
void
opt_classify_cols(
/*==============*/
        sel_node_t*     sel_node,       
        ulint           i)              
{
        plan_t*         plan;
        que_node_t*     exp;

        plan = sel_node_get_nth_plan(sel_node, i);

        /* The final value of the following field will depend on the
        environment of the select statement: */

        plan->must_get_clust = FALSE;

        UT_LIST_INIT(plan->columns);

        /* All select list columns should be copied: therefore TRUE as the
        first argument */

        for (exp = sel_node->select_list;
             exp != 0;
             exp = que_node_get_next(exp)) {

                opt_find_all_cols(
                        TRUE, plan->index, &(plan->columns), plan, exp);
        }

        opt_find_copy_cols(
                sel_node, i, static_cast<func_node_t*>(sel_node->search_cond));

        /* All remaining columns in the search condition are temporary
        columns: therefore FALSE */

        opt_find_all_cols(
                FALSE, plan->index, &plan->columns, plan,
                static_cast<func_node_t*>(sel_node->search_cond));
}

/*******************************************************************/
static
void
opt_clust_access(
/*=============*/
        sel_node_t*     sel_node,       
        ulint           n)              
{
        plan_t*         plan;
        dict_table_t*   table;
        dict_index_t*   clust_index;
        dict_index_t*   index;
        mem_heap_t*     heap;
        ulint           n_fields;
        ulint           pos;
        ulint           i;

        plan = sel_node_get_nth_plan(sel_node, n);

        index = plan->index;

        /* The final value of the following field depends on the environment
        of the select statement: */

        plan->no_prefetch = FALSE;

        if (dict_index_is_clust(index)) {
                plan->clust_map = NULL;
                plan->clust_ref = NULL;

                return;
        }

        table = index->table;

        clust_index = dict_table_get_first_index(table);

        n_fields = dict_index_get_n_unique(clust_index);

        heap = pars_sym_tab_global->heap;

        plan->clust_ref = dtuple_create(heap, n_fields);

        dict_index_copy_types(plan->clust_ref, clust_index, n_fields);

        plan->clust_map = static_cast<ulint*>(
                mem_heap_alloc(heap, n_fields * sizeof(ulint)));

        for (i = 0; i < n_fields; i++) {
                pos = dict_index_get_nth_field_pos(index, clust_index, i);

                ut_a(pos != ULINT_UNDEFINED);

                /* We optimize here only queries to InnoDB's internal system
                tables, and they should not contain column prefix indexes. */

                if (dict_index_get_nth_field(index, pos)->prefix_len != 0
                    || dict_index_get_nth_field(clust_index, i)
                    ->prefix_len != 0) {
                        fprintf(stderr,
                                "InnoDB: Error in pars0opt.cc:"
                                " table %s has prefix_len != 0\n",
                                index->table_name);
                }

                *(plan->clust_map + i) = pos;

                ut_ad(pos != ULINT_UNDEFINED);
        }
}

/*******************************************************************/
UNIV_INTERN
void
opt_search_plan(
/*============*/
        sel_node_t*     sel_node)       
{
        sym_node_t*     table_node;
        dict_table_t*   table;
        order_node_t*   order_by;
        ulint           i;

        sel_node->plans = static_cast<plan_t*>(
                mem_heap_alloc(
                        pars_sym_tab_global->heap,
                        sel_node->n_tables * sizeof(plan_t)));

        /* Analyze the search condition to find out what we know at each
        join stage about the conditions that the columns of a table should
        satisfy */

        table_node = sel_node->table_list;

        if (sel_node->order_by == NULL) {
                sel_node->asc = TRUE;
        } else {
                order_by = sel_node->order_by;

                sel_node->asc = order_by->asc;
        }

        for (i = 0; i < sel_node->n_tables; i++) {

                table = table_node->table;

                /* Choose index through which to access the table */

                opt_search_plan_for_table(sel_node, i, table);

                /* Determine the search condition conjuncts we can test at
                this table; normalize the end conditions */

                opt_determine_and_normalize_test_conds(sel_node, i);

                table_node = static_cast<sym_node_t*>(
                        que_node_get_next(table_node));
        }

        table_node = sel_node->table_list;

        for (i = 0; i < sel_node->n_tables; i++) {

                /* Classify the table columns into those we only need to access
                but not copy, and to those we must copy to dynamic memory */

                opt_classify_cols(sel_node, i);

                /* Calculate possible info for accessing the clustered index
                record */

                opt_clust_access(sel_node, i);

                table_node = static_cast<sym_node_t*>(
                        que_node_get_next(table_node));
        }

        /* Check that the plan obeys a possible order-by clause: if not,
        an assertion error occurs */

        opt_check_order_by(sel_node);

#ifdef UNIV_SQL_DEBUG
        opt_print_query_plan(sel_node);
#endif
}

/********************************************************************/
UNIV_INTERN
void
opt_print_query_plan(
/*=================*/
        sel_node_t*     sel_node)       
{
        plan_t* plan;
        ulint   n_fields;
        ulint   i;

        fputs("QUERY PLAN FOR A SELECT NODE\n", stderr);

        fputs(sel_node->asc ? "Asc. search; " : "Desc. search; ", stderr);

        if (sel_node->set_x_locks) {
                fputs("sets row x-locks; ", stderr);
                ut_a(sel_node->row_lock_mode == LOCK_X);
                ut_a(!sel_node->consistent_read);
        } else if (sel_node->consistent_read) {
                fputs("consistent read; ", stderr);
        } else {
                ut_a(sel_node->row_lock_mode == LOCK_S);
                fputs("sets row s-locks; ", stderr);
        }

        putc('\n', stderr);

        for (i = 0; i < sel_node->n_tables; i++) {
                plan = sel_node_get_nth_plan(sel_node, i);

                if (plan->tuple) {
                        n_fields = dtuple_get_n_fields(plan->tuple);
                } else {
                        n_fields = 0;
                }

                fputs("Table ", stderr);
                dict_index_name_print(stderr, NULL, plan->index);
                fprintf(stderr,"; exact m. %lu, match %lu, end conds %lu\n",
                        (unsigned long) plan->n_exact_match,
                        (unsigned long) n_fields,
                        (unsigned long) UT_LIST_GET_LEN(plan->end_conds));
        }
}