File plan_generation.c¶
File List > cubrid > src > optimizer > plan_generation.c
Go to the documentation of this file
/*
* Copyright 2008 Search Solution Corporation
* Copyright 2016 CUBRID Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*
*/
/*
* plan_generation.c - Generate XASL trees from query optimizer plans
*/
#ident "$Id$"
#include <assert.h>
#include "optimizer.h"
#include "config.h"
#include "object_primitive.h"
#include "query_bitset.h"
#include "query_graph.h"
#include "query_planner.h"
#include "parser.h"
#include "parser_support.h"
#include "system_parameter.h"
#include "xasl.h"
#include "xasl_generation.h"
#include "xasl_predicate.hpp"
typedef int (*ELIGIBILITY_FN) (QO_TERM *);
static XASL_NODE *make_scan_proc (QO_ENV * env);
static XASL_NODE *make_mergelist_proc (QO_ENV * env, QO_PLAN * plan, XASL_NODE * left, PT_NODE * left_list,
BITSET * left_exprs, PT_NODE * left_elist, XASL_NODE * rght, PT_NODE * rght_list,
BITSET * rght_exprs, PT_NODE * rght_elist);
static XASL_NODE *make_hashjoin_proc (QO_ENV * env, QO_PLAN * plan, XASL_NODE * outer_xasl, XASL_NODE * inner_xasl,
PROJECTION_INFO * projection_info);
static XASL_NODE *make_fetch_proc (QO_ENV * env, QO_PLAN * plan);
static XASL_NODE *make_buildlist_proc (QO_ENV * env, PT_NODE * namelist);
static XASL_NODE *check_merge_xasl (QO_ENV * env, XASL_NODE * xasl);
static XASL_NODE *check_hashjoin_xasl (QO_ENV * env, XASL_NODE * xasl);
static XASL_NODE *init_class_scan_proc (QO_ENV * env, XASL_NODE * xasl, QO_PLAN * plan);
static XASL_NODE *init_list_scan_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * list, PT_NODE * namelist,
BITSET * predset, int *poslist);
static XASL_NODE *add_access_spec (QO_ENV *, XASL_NODE *, QO_PLAN *);
static XASL_NODE *add_scan_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * scan);
static XASL_NODE *add_fetch_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * proc);
static XASL_NODE *add_uncorrelated (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * sub);
static XASL_NODE *add_subqueries (QO_ENV * env, XASL_NODE * xasl, BITSET *);
static XASL_NODE *add_sort_spec (QO_ENV *, XASL_NODE *, QO_PLAN *, DB_VALUE *, bool);
static XASL_NODE *add_if_predicate (QO_ENV *, XASL_NODE *, PT_NODE *);
static XASL_NODE *add_during_join_predicate (QO_ENV *, XASL_NODE *, PT_NODE *);
static XASL_NODE *add_after_join_predicate (QO_ENV *, XASL_NODE *, PT_NODE *);
static PT_NODE *make_pred_from_bitset (QO_ENV * env, BITSET * predset, ELIGIBILITY_FN safe);
static void make_pred_from_plan (QO_ENV * env, QO_PLAN * plan, PT_NODE ** key_access_pred, PT_NODE ** access_pred,
QO_XASL_INDEX_INFO * qo_index_infop, PT_NODE ** hash_pred);
static PT_NODE *make_if_pred_from_plan (QO_ENV * env, QO_PLAN * plan);
static PT_NODE *make_instnum_pred_from_plan (QO_ENV * env, QO_PLAN * plan);
static PT_NODE *make_namelist_from_projected_segs (QO_ENV * env, QO_PLAN * plan);
static PT_NODE *make_namelist_from_bitset (QO_ENV * env, BITSET * bitset);
static XASL_NODE *gen_outer (QO_ENV *, QO_PLAN *, BITSET *, XASL_NODE *, XASL_NODE *, XASL_NODE *);
static XASL_NODE *gen_hashjoin (QO_ENV * env, QO_PLAN * plan, BITSET * pred_set, BITSET * subqueries,
XASL_NODE * inner_scans, XASL_NODE * fetches, XASL_NODE * xasl);
static XASL_NODE *gen_inner (QO_ENV *, QO_PLAN *, BITSET *, BITSET *, XASL_NODE *, XASL_NODE *);
static XASL_NODE *preserve_info (QO_ENV * env, QO_PLAN * plan, XASL_NODE * xasl);
static int is_normal_access_term (QO_TERM *);
static int is_normal_if_term (QO_TERM *);
static int is_after_join_term (QO_TERM *);
static int is_totally_after_join_term (QO_TERM *);
static int is_follow_if_term (QO_TERM *);
static int is_always_true (QO_TERM *);
static QO_XASL_INDEX_INFO *qo_get_xasl_index_info (QO_ENV * env, QO_PLAN * plan);
static void qo_free_xasl_index_info (QO_ENV * env, QO_XASL_INDEX_INFO * info);
static bool qo_validate_regu_var_for_limit (REGU_VARIABLE * var_p);
static bool qo_get_limit_from_instnum_pred (PARSER_CONTEXT * parser, PRED_EXPR * pred, REGU_PTR_LIST * lower,
REGU_PTR_LIST * upper);
static bool qo_get_limit_from_eval_term (PARSER_CONTEXT * parser, PRED_EXPR * pred, REGU_PTR_LIST * lower,
REGU_PTR_LIST * upper);
static REGU_PTR_LIST regu_ptr_list_create ();
static void regu_ptr_list_free (REGU_PTR_LIST list);
static REGU_PTR_LIST regu_ptr_list_add_regu (REGU_VARIABLE * var_p, REGU_PTR_LIST list);
static bool qo_check_seg_belongs_to_range_term (QO_PLAN * subplan, QO_ENV * env, int seg_idx);
static int qo_check_plan_index_for_multi_range_opt (PT_NODE * orderby_nodes, PT_NODE * orderby_sort_list,
QO_PLAN * plan, bool * is_valid, int *first_col_idx_pos,
bool * reverse);
static int qo_check_terms_for_multiple_range_opt (QO_PLAN * plan, int first_sort_col_idx, bool * can_optimize);
static bool qo_check_subqueries_for_multi_range_opt (QO_PLAN * plan, int sort_col_idx_pos);
static int qo_check_subplans_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * plan, QO_PLAN * sortplan, bool * is_valid,
bool * seen);
static bool qo_check_subplan_join_cond_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * subplan, QO_PLAN * sort_plan);
static bool qo_check_parent_eq_class_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * subplan, QO_PLAN * sort_plan);
static XASL_NODE *make_sort_limit_proc (QO_ENV * env, QO_PLAN * plan, PT_NODE * namelist, XASL_NODE * xasl);
static PT_NODE *qo_get_orderby_num_upper_bound_node (PARSER_CONTEXT * parser, PT_NODE * orderby_for,
bool * is_new_node);
static int qo_get_multi_col_range_segs (QO_ENV * env, QO_PLAN * plan, QO_INDEX_ENTRY * index_entryp,
BITSET * multi_col_segs, BITSET * multi_col_range_segs, BITSET * index_segs);
static int qo_init_projection_info (QO_ENV * env, QO_PLAN * plan, BITSET * pred_set, PROJECTION_INFO * info);
static void qo_clear_projection_info (QO_ENV * env, PROJECTION_INFO * info);
static void qo_clear_projection_part_info (PARSER_CONTEXT * parser, PROJECTION_PART_INFO * part_info);
static void qo_clear_projection_final_info (PARSER_CONTEXT * parser, PROJECTION_FINAL_INFO * final_info);
static int qo_init_merge_info (QO_ENV * env, QO_PLAN * plan, PROJECTION_INFO * projection_info,
QFILE_LIST_MERGE_INFO * merge_info);
/*
* make_scan_proc () -
* return: XASL_NODE *
* env(in): The optimizer environment
*/
static XASL_NODE *
make_scan_proc (QO_ENV * env)
{
return ptqo_to_scan_proc (QO_ENV_PARSER (env), NULL, NULL, NULL, NULL, NULL, NULL, NULL);
}
/*
* make_fetch_proc () -
* return:
* env(in):
* plan(in):
*/
static XASL_NODE *
make_fetch_proc (QO_ENV * env, QO_PLAN * plan)
{
XASL_NODE *xasl;
PT_NODE *access_pred;
PT_NODE *if_pred;
make_pred_from_plan (env, plan, NULL, &access_pred, NULL, NULL);
if_pred = make_if_pred_from_plan (env, plan);
xasl =
pt_to_fetch_proc (QO_ENV_PARSER (env), QO_NODE_ENTITY_SPEC (QO_TERM_TAIL (plan->plan_un.follow.path)), access_pred);
xasl = add_if_predicate (env, xasl, if_pred);
/* free pointer node list */
parser_free_tree (QO_ENV_PARSER (env), access_pred);
parser_free_tree (QO_ENV_PARSER (env), if_pred);
return xasl;
}
/*
* make_mergelist_proc () -
* return: XASL_NODE *
* env(in): The optimizer environment
* plan(in): The (sub)plan to generate code for merge
* left(in): The XASL node that should build a sorted outer result
* left_list(in): The expr, name list used to create the left XASL node
* left_exprs(in): The join terms bitset of left expr segs
* left_elist(in): The join terms expr list of left expr segs
* rght(in): The XASL node that should build a sorted inner result
* rght_list(in): The expr, name list used to create the right XASL node
* rght_exprs(in): The join terms bitset of right expr segs
* rght_elist(in): The join terms expr list of right expr segs
*
* Note: Make a MERGELIST_PROC XASL node that will eventually reside
* on the merge_list_ptr of some other XASL node.
* Thes initializes the left and right procs things
* live in such a specialized environment that there is no need
* to initialize anything other than the type and the access
* spec; the scan evidently uses the val_list, etc. from the
* outer block.
*/
static XASL_NODE *
make_mergelist_proc (QO_ENV * env, QO_PLAN * plan, XASL_NODE * left, PT_NODE * left_list, BITSET * left_exprs,
PT_NODE * left_elist, XASL_NODE * rght, PT_NODE * rght_list, BITSET * rght_exprs,
PT_NODE * rght_elist)
{
XASL_NODE *merge = NULL;
PARSER_CONTEXT *parser = NULL;
QFILE_LIST_MERGE_INFO *ls_merge;
PT_NODE *outer_attr, *inner_attr;
int i, left_epos, rght_epos, cnt, seg_idx, ncols;
int left_nlen, left_elen, rght_nlen, rght_elen, nlen;
SORT_LIST *order, *prev_order;
QO_TERM *term;
BITSET_ITERATOR bi;
BITSET term_segs;
bitset_init (&term_segs, env);
if (env == NULL || plan == NULL)
{
goto exit_on_error;
}
parser = QO_ENV_PARSER (env);
merge = ptqo_to_merge_list_proc (parser, left, rght, plan->plan_un.join.join_type);
if (merge == NULL || left == NULL || left_list == NULL || rght == NULL || rght_list == NULL)
{
goto exit_on_error;
}
ls_merge = &merge->proc.mergelist.ls_merge;
ls_merge->join_type = plan->plan_un.join.join_type;
ncols = ls_merge->ls_column_cnt = bitset_cardinality (&(plan->plan_un.join.join_terms));
assert (ncols > 0);
ls_merge->ls_outer_column = (int *) pt_alloc_packing_buf (ncols * sizeof (int));
if (ls_merge->ls_outer_column == NULL)
{
goto exit_on_error;
}
ls_merge->ls_outer_unique = (int *) pt_alloc_packing_buf (ncols * sizeof (int));
if (ls_merge->ls_outer_unique == NULL)
{
goto exit_on_error;
}
ls_merge->ls_inner_column = (int *) pt_alloc_packing_buf (ncols * sizeof (int));
if (ls_merge->ls_inner_column == NULL)
{
goto exit_on_error;
}
ls_merge->ls_inner_unique = (int *) pt_alloc_packing_buf (ncols * sizeof (int));
if (ls_merge->ls_inner_unique == NULL)
{
goto exit_on_error;
}
left->orderby_list = NULL;
rght->orderby_list = NULL;
cnt = 0; /* init */
left_epos = rght_epos = 0; /* init */
for (i = bitset_iterate (&(plan->plan_un.join.join_terms), &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
if (ls_merge->join_type == JOIN_INNER && QO_IS_PATH_TERM (term))
{
/* mark merge join spec as single-fetch */
ls_merge->single_fetch = QPROC_SINGLE_OUTER;
}
if (BITSET_MEMBER (*left_exprs, i) && left_elist != NULL)
{
/* Then we added an "extra" column for the expression to the left_elist. We want to treat that expression as
* the outer expression, but we want to leave it off of the list of segments that are projected out of the
* merge. Take it off, but remember it in "outer_attr" so that we can fix up domain info in a little while. */
ls_merge->ls_outer_column[cnt] = left_epos++;
outer_attr = left_elist;
left_elist = left_elist->next;
}
else
{
/* Determine which attributes are involved in this predicate. */
bitset_assign (&term_segs, &(QO_TERM_SEGS (term)));
bitset_intersect (&term_segs, &((plan->plan_un.join.outer)->info->projected_segs));
seg_idx = bitset_first_member (&term_segs);
if (seg_idx == -1)
{
goto exit_on_error;
}
outer_attr = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_idx));
ls_merge->ls_outer_column[cnt] = pt_find_attribute (parser, outer_attr, left_list);
}
ls_merge->ls_outer_unique[cnt] = false; /* currently, unused */
if (BITSET_MEMBER (*rght_exprs, i) && rght_elist != NULL)
{
/* This situation is exactly analogous to the one above, except that we're concerned with the right (inner)
* side this time. */
ls_merge->ls_inner_column[cnt] = rght_epos++;
inner_attr = rght_elist;
rght_elist = rght_elist->next;
}
else
{
/* Determine which attributes are involved in this predicate. */
bitset_assign (&term_segs, &(QO_TERM_SEGS (term)));
bitset_intersect (&term_segs, &((plan->plan_un.join.inner)->info->projected_segs));
seg_idx = bitset_first_member (&term_segs);
if (seg_idx == -1)
{
goto exit_on_error;
}
inner_attr = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_idx));
ls_merge->ls_inner_column[cnt] = pt_find_attribute (parser, inner_attr, rght_list);
}
ls_merge->ls_inner_unique[cnt] = false; /* currently, unused */
/* set outer list order entry */
prev_order = NULL;
for (order = left->orderby_list; order; order = order->next)
{
if (order->pos_descr.pos_no == ls_merge->ls_outer_column[cnt])
{
/* found order entry */
break;
}
prev_order = order;
}
/* not found outer order entry */
if (order == NULL)
{
order = ptqo_single_orderby (parser);
if (order == NULL)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "left_order != NULL");
goto exit_on_error;
}
order->s_order = S_ASC;
order->pos_descr.pos_no = ls_merge->ls_outer_column[cnt];
order->pos_descr.dom = pt_xasl_node_to_domain (parser, outer_attr);
if (prev_order == NULL)
{
left->orderby_list = order;
}
else
{
prev_order->next = order;
}
}
/* set inner list order entry */
prev_order = NULL;
for (order = rght->orderby_list; order; order = order->next)
{
if (order->pos_descr.pos_no == ls_merge->ls_inner_column[cnt])
{
/* found order entry */
break;
}
prev_order = order;
}
/* not found inner order entry */
if (order == NULL)
{
order = ptqo_single_orderby (parser);
if (order == NULL)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "right_order != NULL");
goto exit_on_error;
}
order->s_order = S_ASC;
order->pos_descr.pos_no = ls_merge->ls_inner_column[cnt];
order->pos_descr.dom = pt_xasl_node_to_domain (parser, inner_attr);
if (prev_order == NULL)
{
rght->orderby_list = order;
}
else
{
prev_order->next = order;
}
}
cnt++;
} /* for (i = ... ) */
assert (cnt == ncols);
left_elen = bitset_cardinality (left_exprs);
left_nlen = pt_length_of_list (left_list) - left_elen;
rght_elen = bitset_cardinality (rght_exprs);
rght_nlen = pt_length_of_list (rght_list) - rght_elen;
nlen = ls_merge->ls_pos_cnt = left_nlen + rght_nlen;
ls_merge->ls_outer_inner_list = (int *) pt_alloc_packing_buf (nlen * sizeof (int));
if (ls_merge->ls_outer_inner_list == NULL)
{
goto exit_on_error;
}
ls_merge->ls_pos_list = (int *) pt_alloc_packing_buf (nlen * sizeof (int));
if (ls_merge->ls_pos_list == NULL)
{
goto exit_on_error;
}
/* these could be sorted out arbitrily. This could make it easier to avoid the wrapper buildlist_proc, when no
* expressions, predicates, subqueries, fetches, or aggregation is involved. For now, we always build the same thing,
* with simple column concatenation. */
for (i = 0; i < left_nlen; i++)
{
ls_merge->ls_outer_inner_list[i] = QFILE_OUTER_LIST;
ls_merge->ls_pos_list[i] = i + left_elen;
}
for (i = 0; i < nlen - left_nlen; i++)
{
ls_merge->ls_outer_inner_list[left_nlen + i] = QFILE_INNER_LIST;
ls_merge->ls_pos_list[left_nlen + i] = i + rght_elen;
}
/* make outer_spec_list, outer_val_list, inner_spec_list, and inner_val_list */
if (ls_merge->join_type != JOIN_INNER)
{
PT_NODE *other_pred;
int *poslist;
/* set poslist of outer XASL node */
poslist = NULL; /* init */
if (left_elen > 0)
{
/* proceed to name list and skip out join edge exprs */
for (i = 0; i < left_elen; i++)
{
left_list = left_list->next;
}
poslist = (int *) malloc (left_nlen * sizeof (int));
if (poslist == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, left_nlen * sizeof (int));
goto exit_on_error;
}
for (i = 0; i < left_nlen; i++)
{
poslist[i] = i + left_elen;
}
}
/* sets xasl->spec_list and xasl->val_list */
merge = ptqo_to_list_scan_proc (parser, merge, SCAN_PROC, left, left_list, NULL, poslist);
/* dealloc */
if (poslist != NULL)
{
free_and_init (poslist);
}
if (merge == NULL)
{
goto exit_on_error;
}
merge->proc.mergelist.outer_spec_list = merge->spec_list;
merge->proc.mergelist.outer_val_list = merge->val_list;
/* set poslist of inner XASL node */
poslist = NULL; /* init */
if (rght_elen > 0)
{
/* proceed to name list and skip out join edge exprs */
for (i = 0; i < rght_elen; i++)
{
rght_list = rght_list->next;
}
poslist = (int *) malloc (rght_nlen * sizeof (int));
if (poslist == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, rght_nlen * sizeof (int));
goto exit_on_error;
}
for (i = 0; i < rght_nlen; i++)
{
poslist[i] = i + rght_elen;
}
}
/* sets xasl->spec_list and xasl->val_list */
merge = ptqo_to_list_scan_proc (parser, merge, SCAN_PROC, rght, rght_list, NULL, poslist);
/* dealloc */
if (poslist)
{
free_and_init (poslist);
}
if (merge == NULL)
{
goto exit_on_error;
}
merge->proc.mergelist.inner_spec_list = merge->spec_list;
merge->proc.mergelist.inner_val_list = merge->val_list;
merge->spec_list = NULL;
merge->val_list = NULL;
/* add outer join terms */
other_pred = make_pred_from_bitset (env, &(plan->plan_un.join.during_join_terms), is_always_true);
if (other_pred)
{
merge->during_join_pred = pt_to_pred_expr (parser, other_pred);
/* free pointer node list */
parser_free_tree (parser, other_pred);
}
}
else
{
merge->proc.mergelist.outer_spec_list = NULL;
merge->proc.mergelist.outer_val_list = NULL;
merge->proc.mergelist.inner_spec_list = NULL;
merge->proc.mergelist.inner_val_list = NULL;
}
exit_on_end:
bitset_delset (&term_segs);
return merge;
exit_on_error:
merge = NULL;
goto exit_on_end;
}
/*
* make_hashjoin_proc() -
* return: XASL node for hash join execution; NULL on error.
* env(in): Optimization environment.
* plan(in): Execution plan for hash join.
* outer_xasl(in): XASL node for outer input of the hash join.
* inner_xasl(in): XASL node for inner input of the hash join.
* projection_info(in): Projection information used in the hash join execution plan.
*/
static XASL_NODE *
make_hashjoin_proc (QO_ENV * env, QO_PLAN * plan, XASL_NODE * outer_xasl, XASL_NODE * inner_xasl,
PROJECTION_INFO * projection_info)
{
PARSER_CONTEXT *parser = NULL;
PT_NODE *during_join_pred = NULL, *pred;
PROJECTION_PART_INFO *outer_info, *inner_info;
XASL_NODE *xasl = NULL;
HASHJOIN_PROC_NODE *proc;
REGU_VARIABLE_LIST regu;
int *pos_list = NULL;
int pos_cnt, pos_index, found_index;
int error = NO_ERROR;
assert (env != NULL);
assert (plan != NULL && plan->plan_type == QO_PLANTYPE_JOIN
&& plan->plan_un.join.join_method == QO_JOINMETHOD_HASH_JOIN);
assert (outer_xasl != NULL);
assert (inner_xasl != NULL);
assert (projection_info != NULL);
outer_info = &projection_info->outer;
inner_info = &projection_info->inner;
parser = QO_ENV_PARSER (env);
if (parser == NULL)
{
/* impossible case */
assert (false);
goto error_exit;
}
xasl = pt_to_hashjoin_proc (parser, outer_xasl, inner_xasl);
if (xasl == NULL)
{
goto error_exit;
}
proc = &xasl->proc.hashjoin;
/* proc->outer.regu_list_pred */
if (outer_info->pred_count > 0)
{
pos_cnt = outer_info->pred_count;
pos_list = (int *) malloc (pos_cnt * sizeof (int));
if (pos_list == NULL)
{
error = ER_OUT_OF_VIRTUAL_MEMORY;
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, error, 1, pos_cnt * sizeof (int));
goto error_exit;
}
pred = outer_info->pred_list;
for (pos_index = 0; pos_index < pos_cnt; pos_index++)
{
found_index = pt_find_attribute (parser, pred, outer_info->name_list);
if (found_index == -1)
{
free_and_init (pos_list);
goto error_exit;
}
pos_list[pos_index] = found_index;
pred = pred->next;
}
proc->outer.regu_list_pred =
pt_to_position_regu_variable_list (parser, outer_info->pred_list, outer_xasl->val_list, pos_list);
free_and_init (pos_list);
if (proc->outer.regu_list_pred == NULL)
{
goto error_exit;
}
for (regu = proc->outer.regu_list_pred; regu != NULL; regu = regu->next)
{
regu->value.value.pos_descr.pos_no += outer_info->expr_count;
}
}
/* proc->inner.regu_list_pred */
if (inner_info->pred_count > 0)
{
pos_cnt = inner_info->pred_count;
pos_list = (int *) malloc (pos_cnt * sizeof (int));
if (pos_list == NULL)
{
error = ER_OUT_OF_VIRTUAL_MEMORY;
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, error, 1, pos_cnt * sizeof (int));
goto error_exit;
}
pred = inner_info->pred_list;
for (pos_index = 0; pos_index < pos_cnt; pos_index++)
{
found_index = pt_find_attribute (parser, pred, inner_info->name_list);
if (found_index == -1)
{
free_and_init (pos_list);
goto error_exit;
}
pos_list[pos_index] = found_index;
pred = pred->next;
}
proc->inner.regu_list_pred =
pt_to_position_regu_variable_list (parser, inner_info->pred_list, inner_xasl->val_list, pos_list);
free_and_init (pos_list);
if (proc->inner.regu_list_pred == NULL)
{
goto error_exit;
}
for (regu = proc->inner.regu_list_pred; regu != NULL; regu = regu->next)
{
regu->value.value.pos_descr.pos_no += inner_info->expr_count;
}
}
/* during join predicate */
if (!bitset_is_empty (&plan->plan_un.join.during_join_terms))
{
during_join_pred = make_pred_from_bitset (env, &plan->plan_un.join.during_join_terms, is_always_true);
if (during_join_pred == NULL)
{
goto error_exit;
}
xasl = add_during_join_predicate (env, xasl, during_join_pred);
parser_free_tree (parser, during_join_pred);
}
/* merge_info */
error = qo_init_merge_info (env, plan, projection_info, &proc->merge_info);
if (error != NO_ERROR)
{
goto error_exit;
}
ASSERT_NO_ERROR_OR_INTERRUPTED ();
assert (!pt_has_error (parser));
return xasl;
error_exit:
if (error == NO_ERROR && pt_has_error (parser))
{
pt_report_to_ersys (parser, PT_SEMANTIC);
pt_reset_error (parser);
}
if (error == NO_ERROR || er_errid () == NO_ERROR)
{
assert_release_error (er_errid () != NO_ERROR);
}
return NULL;
}
/*
* make_buildlist_proc () -
* return: XASL_NODE *
* env(in): The optimizer environment
* namelist(in): The list of names to use as input to and output from this
* node
*/
static XASL_NODE *
make_buildlist_proc (QO_ENV * env, PT_NODE * namelist)
{
return pt_skeleton_buildlist_proc (QO_ENV_PARSER (env), namelist);
}
/*
* bitset_has_path () -
* return: int 1 iff path term is present, 0 otherwise
* env(in): The optimizer environment
* predset(in): The bitset of predicates to turn into a predicate tree
*/
static int
bitset_has_path (QO_ENV * env, BITSET * predset)
{
BITSET_ITERATOR bi;
int i;
for (i = bitset_iterate (predset, &bi); i != -1; i = bitset_next_member (&bi))
{
QO_TERM *term;
term = QO_ENV_TERM (env, i);
if (QO_IS_PATH_TERM (term))
{
return 1;
}
}
return 0;
}
/*
* mark_access_as_outer_join () - mark aan xasl proc's access spec
* as left outer join
* return:
* parser(in): The parser environment
* xasl(in): The already allocated node to be initialized
*/
static void
mark_access_as_outer_join (PARSER_CONTEXT * parser, XASL_NODE * xasl)
{
ACCESS_SPEC_TYPE *access;
for (access = xasl->spec_list; access; access = access->next)
{
access->single_fetch = QPROC_NO_SINGLE_OUTER;
}
}
/*
* init_class_scan_proc () -
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The already allocated node to be initialized
* plan(in): The plan from which to initialize the scan proc
*
* Note: Take a BUILDwhatever skeleton and flesh it out as a scan
* gadget. Don't mess with any other fields than you absolutely
* must: they may have already been initialized by other
* routines.
*/
static XASL_NODE *
init_class_scan_proc (QO_ENV * env, XASL_NODE * xasl, QO_PLAN * plan)
{
PARSER_CONTEXT *parser;
PT_NODE *spec;
PT_NODE *key_pred;
PT_NODE *access_pred, *hash_pred;
PT_NODE *if_pred;
PT_NODE *after_join_pred;
QO_XASL_INDEX_INFO *info;
parser = QO_ENV_PARSER (env);
spec = QO_NODE_ENTITY_SPEC (plan->plan_un.scan.node);
info = qo_get_xasl_index_info (env, plan);
make_pred_from_plan (env, plan, &key_pred, &access_pred, info, &hash_pred);
xasl = ptqo_to_scan_proc (parser, plan, xasl, spec, key_pred, access_pred, info, hash_pred);
/* free pointer node list */
parser_free_tree (parser, key_pred);
parser_free_tree (parser, access_pred);
parser_free_tree (parser, hash_pred);
if (xasl)
{
after_join_pred = make_pred_from_bitset (env, &(plan->sarged_terms), is_after_join_term);
if_pred = make_if_pred_from_plan (env, plan);
xasl = add_after_join_predicate (env, xasl, after_join_pred);
xasl = add_if_predicate (env, xasl, if_pred);
/* free pointer node list */
parser_free_tree (parser, after_join_pred);
parser_free_tree (parser, if_pred);
}
if (info)
{
qo_free_xasl_index_info (env, info);
}
return xasl;
}
/*
* init_list_scan_proc () -
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The already allocated node to be initialized
* listfile(in): The buildlist proc node for the list file to be scanned
* namelist(in): The list of names (columns) to be retrieved from the file
* predset(in): A bitset of predicates to be added to the access spec
* poslist(in):
*
* Note: Take a BUILDwhatever skeleton and flesh it out as a scan
* gadget. Don't mess with any other fields than you absolutely
* must: they may have already been initialized by other
* routines.
*/
static XASL_NODE *
init_list_scan_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * listfile, PT_NODE * namelist, BITSET * predset,
int *poslist)
{
PT_NODE *access_pred, *if_pred, *after_join_pred, *instnum_pred;
if (xasl)
{
access_pred = make_pred_from_bitset (env, predset, is_normal_access_term);
if_pred = make_pred_from_bitset (env, predset, is_normal_if_term);
after_join_pred = make_pred_from_bitset (env, predset, is_after_join_term);
instnum_pred = make_pred_from_bitset (env, predset, is_totally_after_join_term);
xasl = ptqo_to_list_scan_proc (QO_ENV_PARSER (env), xasl, SCAN_PROC, listfile, namelist, access_pred, poslist);
if (env->pt_tree->node_type == PT_SELECT && env->pt_tree->info.query.q.select.connect_by)
{
pt_set_level_node_etc (QO_ENV_PARSER (env), if_pred, &xasl->level_val);
pt_set_isleaf_node_etc (QO_ENV_PARSER (env), if_pred, &xasl->isleaf_val);
pt_set_iscycle_node_etc (QO_ENV_PARSER (env), if_pred, &xasl->iscycle_val);
pt_set_connect_by_operator_node_etc (QO_ENV_PARSER (env), if_pred, xasl);
pt_set_qprior_node_etc (QO_ENV_PARSER (env), if_pred, xasl);
}
xasl = add_if_predicate (env, xasl, if_pred);
xasl = add_after_join_predicate (env, xasl, after_join_pred);
xasl = pt_to_instnum_pred (QO_ENV_PARSER (env), xasl, instnum_pred);
/* free pointer node list */
parser_free_tree (QO_ENV_PARSER (env), access_pred);
parser_free_tree (QO_ENV_PARSER (env), if_pred);
parser_free_tree (QO_ENV_PARSER (env), after_join_pred);
parser_free_tree (QO_ENV_PARSER (env), instnum_pred);
}
return xasl;
}
/*
* add_access_spec () -
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to twiddle
* plan(in):
*/
static XASL_NODE *
add_access_spec (QO_ENV * env, XASL_NODE * xasl, QO_PLAN * plan)
{
PARSER_CONTEXT *parser;
PT_NODE *class_spec;
PT_NODE *key_pred = NULL;
PT_NODE *access_pred = NULL;
PT_NODE *if_pred = NULL;
PT_NODE *instnum_pred = NULL;
QO_XASL_INDEX_INFO *info = NULL;
if (!xasl)
{ /* may be invalid argument */
return xasl;
}
assert (plan->plan_type == QO_PLANTYPE_SCAN);
parser = QO_ENV_PARSER (env);
class_spec = QO_NODE_ENTITY_SPEC (plan->plan_un.scan.node);
/* set the type for XASL generation */
if (PT_IS_VALUE_QUERY (env->pt_tree))
{
PT_SET_VALUE_QUERY (class_spec);
}
info = qo_get_xasl_index_info (env, plan);
make_pred_from_plan (env, plan, &key_pred, &access_pred, info, NULL);
xasl->spec_list = pt_to_spec_list (parser, class_spec, key_pred, access_pred, plan, info, NULL, NULL);
if (xasl->spec_list == NULL)
{
goto exit_on_error;
}
xasl->val_list = pt_to_val_list (parser, class_spec->info.spec.id);
if (xasl->val_list == NULL)
{
goto exit_on_error;
}
if_pred = make_if_pred_from_plan (env, plan);
instnum_pred = make_instnum_pred_from_plan (env, plan);
if (env->pt_tree->node_type == PT_SELECT && env->pt_tree->info.query.q.select.connect_by)
{
pt_set_level_node_etc (parser, if_pred, &xasl->level_val);
pt_set_isleaf_node_etc (parser, if_pred, &xasl->isleaf_val);
pt_set_iscycle_node_etc (parser, if_pred, &xasl->iscycle_val);
pt_set_connect_by_operator_node_etc (parser, if_pred, xasl);
pt_set_qprior_node_etc (parser, if_pred, xasl);
}
xasl = add_if_predicate (env, xasl, if_pred);
xasl = pt_to_instnum_pred (QO_ENV_PARSER (env), xasl, instnum_pred);
success:
/* free pointer node list */
parser_free_tree (parser, key_pred);
parser_free_tree (parser, access_pred);
parser_free_tree (parser, if_pred);
parser_free_tree (parser, instnum_pred);
qo_free_xasl_index_info (env, info);
return xasl;
exit_on_error:
xasl = NULL;
goto success;
}
/*
* add_scan_proc () - Add the scan proc to the end of xasl's scan_ptr list
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to receive the scan block
* scan(in): The scanproc to be added
*/
static XASL_NODE *
add_scan_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * scan)
{
XASL_NODE *xp;
if (xasl)
{
for (xp = xasl; xp->scan_ptr; xp = xp->scan_ptr)
;
xp->scan_ptr = scan;
}
else
xasl = NULL;
return xasl;
}
/*
* add_fetch_proc () - Create a fetch proc and add it to the *head*
* of the list of fetch procs in xasl->fptr
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to receive the fetch block
* procs(in): The fetch proc to be added
*/
static XASL_NODE *
add_fetch_proc (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * procs)
{
XASL_NODE *f;
if (xasl)
{
/*
* The idea here is that we want these fetches to run *every
* time* a new candidate row is produced by xasl, which means
* they should go at the end of this proc's fptr_list.
*/
for (f = xasl; f->fptr_list; f = f->fptr_list)
;
f->fptr_list = procs;
}
else
{
xasl = NULL;
}
return xasl;
}
/*
* add_uncorrelated () - Add the scan proc to the *head* of the list of
* scanprocs in xasl->scan_ptr
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to receive the scan block
* sub(in): The XASL thing to be added to xasl's list of uncorrelated
* "subqueries"
*/
static XASL_NODE *
add_uncorrelated (QO_ENV * env, XASL_NODE * xasl, XASL_NODE * sub)
{
if (xasl && sub)
{
xasl->aptr_list = pt_remove_xasl (pt_append_xasl (xasl->aptr_list, sub), xasl);
}
else
{
xasl = NULL;
}
return xasl;
}
/*
* add_subqueries () - Add the xasl trees for the subqueries to the xasl node
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to receive the scan block
* subqueries(in): A bitset representing the correlated subqueries that
* should be tacked onto xasl
*
* Note: Because of the way the outer driver controls
* things, we never have to worry about subqueries that nested
* deeper than one, so there is no ordering that needs to be
* maintained here; we can just put these guys on the d-list in
* any convenient order.
*/
static XASL_NODE *
add_subqueries (QO_ENV * env, XASL_NODE * xasl, BITSET * subqueries)
{
BITSET_ITERATOR bi;
int i;
XASL_NODE *sub_xasl;
QO_SUBQUERY *subq;
if (xasl)
{
for (i = bitset_iterate (subqueries, &bi); i != -1; i = bitset_next_member (&bi))
{
subq = &env->subqueries[i];
sub_xasl = (XASL_NODE *) subq->node->info.query.xasl;
if (sub_xasl)
{
if (bitset_is_empty (&(subq->nodes)))
{ /* uncorrelated */
xasl->aptr_list = pt_remove_xasl (pt_append_xasl (xasl->aptr_list, sub_xasl), xasl);
}
else
{ /* correlated */
xasl->dptr_list = pt_remove_xasl (pt_append_xasl (xasl->dptr_list, sub_xasl), xasl);
}
}
}
}
return xasl;
}
/*
* add_sort_spec () -
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL node that should build a sorted result
* plan(in): The plan that needs sorting
* instnum_flag(in): instnum indicator
*/
static XASL_NODE *
add_sort_spec (QO_ENV * env, XASL_NODE * xasl, QO_PLAN * plan, DB_VALUE * ordby_val, bool instnum_flag)
{
QO_PLAN *subplan;
subplan = plan->plan_un.sort.subplan;
/*
* xasl->orderby_list for m-join is added in make_mergelist_proc()
*/
if (instnum_flag)
{
if (xasl && subplan->plan_type == QO_PLANTYPE_JOIN
&& subplan->plan_un.join.join_method == QO_JOINMETHOD_MERGE_JOIN)
{
PT_NODE *instnum_pred;
instnum_pred = make_instnum_pred_from_plan (env, plan);
xasl = pt_to_instnum_pred (QO_ENV_PARSER (env), xasl, instnum_pred);
/* free pointer node list */
parser_free_tree (QO_ENV_PARSER (env), instnum_pred);
}
}
if (xasl && plan->plan_un.sort.sort_type == SORT_LIMIT)
{
/* setup ORDER BY list here */
int ordbynum_flag;
QO_LIMIT_INFO *limit_infop;
PARSER_CONTEXT *parser = QO_ENV_PARSER (env);
PT_NODE *query = QO_ENV_PT_TREE (env);
PT_NODE *upper_bound = NULL, *save_next = NULL;
bool free_upper_bound = false;
xasl->orderby_list = pt_to_orderby (parser, query->info.query.order_by, query);
XASL_CLEAR_FLAG (xasl, XASL_SKIP_ORDERBY_LIST);
xasl->orderby_limit = NULL;
/* A SORT-LIMIT plan can only handle the upper limit of the orderby_num predicate. This is because the
* orderby_num pred will be applied twice: once for the SORT-LIMIT plan and once for the top plan. If the lower
* bound is evaluated twice, some tuples are lost. */
upper_bound = query->info.query.orderby_for;
upper_bound = qo_get_orderby_num_upper_bound_node (parser, upper_bound, &free_upper_bound);
if (upper_bound == NULL)
{
/* Must have an upper limit if we're considering a SORT-LIMIT plan. */
return NULL;
}
save_next = upper_bound->next;
upper_bound->next = NULL;
ordbynum_flag = 0;
xasl->ordbynum_pred = pt_to_pred_expr_with_arg (parser, upper_bound, &ordbynum_flag);
upper_bound->next = save_next;
if (free_upper_bound)
{
parser_free_tree (parser, upper_bound);
}
if (ordbynum_flag & PT_PRED_ARG_ORDBYNUM_CONTINUE)
{
xasl->ordbynum_flag = XASL_ORDBYNUM_FLAG_SCAN_CONTINUE;
}
xasl->ordbynum_val = ordby_val;
limit_infop = qo_get_key_limit_from_ordbynum (parser, plan, xasl, false);
if (limit_infop)
{
if ((qo_is_iscan (subplan) || qo_is_iscan_from_orderby (subplan))
&& (subplan->skip_orderby_opt == QO_PLAN_SKIP_ORDERBY_USE
|| subplan->skip_orderby_opt == QO_PLAN_SKIP_ORDERBY_CAN_USE))
{
assert (xasl->instnum_pred == NULL);
assert (xasl->ordbynum_pred != NULL);
assert (xasl->save_instnum_val == NULL);
xasl->instnum_pred = xasl->ordbynum_pred;
xasl->ordbynum_pred = NULL;
xasl->save_instnum_val = xasl->instnum_val;
xasl->instnum_val = xasl->ordbynum_val;
xasl->instnum_flag = xasl->ordbynum_flag;
xasl->ordbynum_val = NULL;
xasl->ordbynum_flag = 0;
KEY_INFO *key_infop = &xasl->spec_list->indexptr->key_info;
key_infop->key_limit_l = limit_infop->lower;
key_infop->key_limit_u = limit_infop->upper;
key_infop->key_limit_reset = false;
XASL_SET_FLAG (xasl, XASL_SKIP_ORDERBY_LIST);
}
else
{
xasl->orderby_limit = limit_infop->upper;
}
db_private_free (NULL, limit_infop);
}
}
return xasl;
}
/*
* add_if_predicate () - Tack the predicate onto the XASL node's if_pred list
* return: XASL_NODE *
* env(in): The optimizer environment
* xasl(in): The XASL block to which we should add the predicate
* pred(in): The pt predicate to tacked on to xasl
*/
static XASL_NODE *
add_if_predicate (QO_ENV * env, XASL_NODE * xasl, PT_NODE * pred)
{
PARSER_CONTEXT *parser;
if (xasl && pred)
{
parser = QO_ENV_PARSER (env);
xasl->if_pred = pt_to_pred_expr (parser, pred);
}
return xasl;
}
/*
* add_during_join_predicate () -
* return:
* env(in):
* xasl(in):
* pred(in):
*/
static XASL_NODE *
add_during_join_predicate (QO_ENV * env, XASL_NODE * xasl, PT_NODE * pred)
{
PARSER_CONTEXT *parser;
if (xasl && pred)
{
parser = QO_ENV_PARSER (env);
xasl->during_join_pred = pt_to_pred_expr (parser, pred);
}
return xasl;
}
/*
* add_after_join_predicate () -
* return:
* env(in):
* xasl(in):
* pred(in):
*/
static XASL_NODE *
add_after_join_predicate (QO_ENV * env, XASL_NODE * xasl, PT_NODE * pred)
{
PARSER_CONTEXT *parser;
if (xasl && pred)
{
parser = QO_ENV_PARSER (env);
xasl->after_join_pred = pt_to_pred_expr (parser, pred);
}
return xasl;
}
/*
* path_access_term () -
* return:
* term(in):
*/
static int
path_access_term (QO_TERM * term)
{
return QO_IS_PATH_TERM (term);
}
/*
* path_if_term () -
* return:
* term(in):
*/
static int
path_if_term (QO_TERM * term)
{
return !QO_IS_PATH_TERM (term) && !is_totally_after_join_term (term);
}
/*
* is_normal_access_term () -
* return:
* term(in):
*/
static int
is_normal_access_term (QO_TERM * term)
{
if (!bitset_is_empty (&(QO_TERM_SUBQUERIES (term))))
{
return 0;
}
if (QO_TERM_CLASS (term) == QO_TC_OTHER
/* || QO_TERM_CLASS(term) == QO_TC_DURING_JOIN || */
/* nl outer join treats during join terms as sarged terms of inner */
|| QO_TERM_CLASS (term) == QO_TC_AFTER_JOIN || QO_TERM_CLASS (term) == QO_TC_TOTALLY_AFTER_JOIN)
{
return 0;
}
return 1;
}
/*
* is_normal_if_term () -
* return:
* term(in):
*/
static int
is_normal_if_term (QO_TERM * term)
{
if (!bitset_is_empty (&(QO_TERM_SUBQUERIES (term))))
{
return 1;
}
if (QO_TERM_CLASS (term) == QO_TC_OTHER)
{
return 1;
}
return 0;
}
/*
* is_after_join_term () -
* return:
* term(in):
*/
static int
is_after_join_term (QO_TERM * term)
{
if (!bitset_is_empty (&(QO_TERM_SUBQUERIES (term))))
{
return 0;
}
if (QO_TERM_CLASS (term) == QO_TC_AFTER_JOIN)
{
return 1;
}
return 0;
}
/*
* is_totally_after_join_term () -
* return:
* term(in):
*/
static int
is_totally_after_join_term (QO_TERM * term)
{
if (!bitset_is_empty (&(QO_TERM_SUBQUERIES (term))))
{
return 0;
}
if (QO_TERM_CLASS (term) == QO_TC_TOTALLY_AFTER_JOIN)
{
return 1;
}
return 0;
}
/*
* is_follow_if_term () -
* return:
* term(in):
*/
static int
is_follow_if_term (QO_TERM * term)
{
if (QO_TERM_CLASS (term) == QO_TC_DURING_JOIN /* ? */
|| QO_TERM_CLASS (term) == QO_TC_AFTER_JOIN || QO_TERM_CLASS (term) == QO_TC_TOTALLY_AFTER_JOIN)
{
return 0;
}
return 1;
}
/*
* is_always_true () -
* return:
* term(in):
*/
static int
is_always_true (QO_TERM * term)
{
return true;
}
/*
* make_pred_from_bitset () -
* return: PT_NODE *
* env(in): The optimizer environment
* predset(in): The bitset of predicates to turn into a predicate tree
* safe(in): A function to test whether a particular term should be
* put on a predicate
*
* Note: make pred_info * style predicates from a bitset of conjuncts.
* use only those conjuncts that can be put on an access pred.
*/
static PT_NODE *
make_pred_from_bitset (QO_ENV * env, BITSET * predset, ELIGIBILITY_FN safe)
{
PARSER_CONTEXT *parser;
PT_NODE *pred_list, *pointer, *prev, *curr;
BITSET_ITERATOR bi;
int i;
QO_TERM *term;
bool found;
PT_NODE *pt_expr;
double cmp;
parser = QO_ENV_PARSER (env);
pred_list = NULL; /* init */
for (i = bitset_iterate (predset, &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
/* Don't ever let one of our fabricated terms find its way into the predicate; that will cause serious confusion. */
if (QO_IS_FAKE_TERM (term) || !(*safe) (term))
{
continue;
}
/* We need to use predicate pointer. modifying WHERE clause structure in place gives us no way to compile the
* query if the optimizer bails out. */
pt_expr = QO_TERM_PT_EXPR (term);
if (pt_expr == NULL)
{
/* is possible ? */
goto exit_on_error;
}
pointer = pt_point (parser, pt_expr);
if (pointer == NULL)
{
goto exit_on_error;
}
/* set AND predicate evaluation pred_order desc, selectivity asc, rank asc */
pointer->info.pointer.sel = QO_TERM_SELECTIVITY (term);
pointer->info.pointer.rank = QO_TERM_RANK (term);
pointer->info.pointer.pred_order = QO_TERM_PRED_ORDER (term);
/* insert to the AND predicate list by descending order of (selectivity, rank) vector; this order is used at
* pt_to_pred_expr_with_arg() */
found = false; /* init */
prev = NULL; /* init */
for (curr = pred_list; curr; curr = curr->next)
{
cmp = pointer->info.pointer.pred_order - curr->info.pointer.pred_order;
if (cmp == 0)
{ /* same selectivity, re-compare rank */
cmp = curr->info.pointer.sel - pointer->info.pointer.sel;
}
if (cmp == 0)
{ /* same selectivity, re-compare rank */
cmp = curr->info.pointer.rank - pointer->info.pointer.rank;
}
if (cmp <= 0)
{
pointer->next = curr;
if (prev == NULL)
{ /* very the first */
pred_list = pointer;
}
else
{
prev->next = pointer;
}
found = true;
break;
}
prev = curr;
}
/* append to the predicate list */
if (found == false)
{
if (prev == NULL)
{ /* very the first */
pointer->next = pred_list;
pred_list = pointer;
}
else
{ /* very the last */
prev->next = pointer;
}
}
}
return pred_list;
exit_on_error:
if (pred_list)
{
parser_free_tree (parser, pred_list);
}
return NULL;
}
/*
* make_pred_from_plan () -
* return:
* env(in): The optimizer environment
* plan(in): Query plan
* key_predp(in): Index information of query plan.
* Predicate tree to be used as key filter
* predp(in): Predicate tree to be used as data filter
* qo_index_infop(in):
*
* Note: Make a PT_NODE * style predicate from a bitset of conjuncts.
* Splits sargs into key filter predicates and data filter predicates.
*/
static void
make_pred_from_plan (QO_ENV * env, QO_PLAN * plan, PT_NODE ** key_predp, PT_NODE ** predp,
QO_XASL_INDEX_INFO * qo_index_infop, PT_NODE ** hash_predp)
{
QO_INDEX_ENTRY *index_entryp = NULL;
/* initialize output parameter */
if (key_predp != NULL)
{
*key_predp = NULL;
}
if (predp != NULL)
{
*predp = NULL;
}
if (hash_predp != NULL)
{
*hash_predp = NULL;
}
if (plan->plan_type == QO_PLANTYPE_FOLLOW)
{
/* Don't allow predicates to migrate to fetch_proc access specs; the special handling of NULL doesn't look at the
* access spec, so it will miss predicates that are deposited there. Always put these things on the if_pred for
* now. This needs to get fixed. >>>> Note the same problem is encountered when emulating follow with >>>> joins.
* The access pred must return a row, even if its null. >>>> the rest or the predicate may then be applied. */
return;
}
/* This is safe guard code - DO NOT DELETE ME */
do
{
/* exclude key-range terms from key-filter terms */
bitset_difference (&(plan->plan_un.scan.kf_terms), &(plan->plan_un.scan.terms));
/* exclude key-range terms from sarged terms */
bitset_difference (&(plan->sarged_terms), &(plan->plan_un.scan.terms));
/* exclude key-filter terms from sarged terms */
bitset_difference (&(plan->sarged_terms), &(plan->plan_un.scan.kf_terms));
}
while (0);
/* make predicate list for hash key */
if (hash_predp != NULL)
{
*hash_predp = make_pred_from_bitset (env, &(plan->plan_un.scan.hash_terms), is_always_true);
}
/* if key filter(predicates) is not required */
if (predp != NULL && (key_predp == NULL || qo_index_infop == NULL))
{
*predp = (make_pred_from_bitset (env, &(plan->sarged_terms), bitset_has_path (env, &(plan->sarged_terms))
? path_access_term : is_normal_access_term));
return;
}
/* make predicate list for key filter */
if (key_predp != NULL)
{
if (qo_index_infop && qo_index_infop->need_copy_multi_range_term != -1 && qo_index_infop->need_copy_to_sarg_term)
{
bitset_add (&(plan->sarged_terms), qo_index_infop->need_copy_multi_range_term);
}
else if (qo_index_infop->need_copy_multi_range_term != -1)
{
index_entryp = qo_index_infop->ni_entry->head;
if (index_entryp && index_entryp->constraints && index_entryp->constraints->func_index_info
&& index_entryp->cover_segments == false)
{
/* if predicate has function index column then do not permit key-filter. so force-copy to sarg */
bitset_add (&(plan->sarged_terms), qo_index_infop->need_copy_multi_range_term);
}
else
{
/*force-copy multi col range pred to key filter */
bitset_add (&(plan->plan_un.scan.kf_terms), qo_index_infop->need_copy_multi_range_term);
}
}
*key_predp = make_pred_from_bitset (env, &(plan->plan_un.scan.kf_terms), is_always_true);
}
/* make predicate list for data filter */
if (predp != NULL)
{
*predp = (make_pred_from_bitset (env, &(plan->sarged_terms), bitset_has_path (env, &(plan->sarged_terms))
? path_access_term : is_normal_access_term));
}
}
/*
* make_if_pred_from_plan () -
* return:
* env(in):
* plan(in):
*/
static PT_NODE *
make_if_pred_from_plan (QO_ENV * env, QO_PLAN * plan)
{
ELIGIBILITY_FN test;
if (plan->plan_type == QO_PLANTYPE_FOLLOW)
{
/*
* Put all predicates on the if_pred right now, because the "dead
* end" handling for NULLs won't look at predicates on the access
* spec.
*
* This needs to get fixed.
*/
test = is_follow_if_term;
}
else
{
test = bitset_has_path (env, &(plan->sarged_terms)) ? path_if_term : is_normal_if_term;
}
return make_pred_from_bitset (env, &(plan->sarged_terms), test);
}
/*
* make_instnum_pred_from_plan () -
* return:
* env(in):
* plan(in):
*/
static PT_NODE *
make_instnum_pred_from_plan (QO_ENV * env, QO_PLAN * plan)
{
/* is it enough? */
return make_pred_from_bitset (env, &(plan->sarged_terms), is_totally_after_join_term);
}
/*
* make_namelist_from_projected_segs () -
* return: PT_NODE *
* env(in): The optimizer environment
* plan(in): he plan whose projected segments need to be put into a name list
*
* Note: Take a bitset of segment indexes and produce a name list
* suitable for creating the outptr_list member of a buildlist
* proc. This is used by the creators of temporary list files:
* merge joins and sorts.
*
* In the interests of sanity, the elements in the list appear
* in the same order as the indexes in the scan of the bitset.
*/
static PT_NODE *
make_namelist_from_projected_segs (QO_ENV * env, QO_PLAN * plan)
{
return make_namelist_from_bitset (env, &plan->info->projected_segs);
}
/*
* make_namelist_from_bitset() -
* return: List of PT_NAME nodes corresponding to the given segment bitset.
* env(in): Optimization environment.
* bitset(in): Bitset of segments to extract PT_NAME nodes from.
*/
static PT_NODE *
make_namelist_from_bitset (QO_ENV * env, BITSET * bitset)
{
PARSER_CONTEXT *parser;
PT_NODE *node, *name_list = NULL;
QO_SEGMENT *seg;
BITSET name_segs_set;
BITSET_ITERATOR bitset_iter;
int bitset_index;
assert (env != NULL);
assert (bitset != NULL);
parser = QO_ENV_PARSER (env);
bitset_init (&name_segs_set, env);
bitset_assign (&name_segs_set, bitset);
for (bitset_index = bitset_iterate (bitset, &bitset_iter); bitset_index != -1;
bitset_index = bitset_next_member (&bitset_iter))
{
seg = QO_ENV_SEG (env, bitset_index);
if (seg->is_function_index)
{
node = QO_SEG_PT_NODE (seg);
if (node->node_type != PT_NAME)
{
/*
* Only table column names or constants are allowed as function arguments in a function-based index.
* Complex or nested expressions are not allowed.
* This is checked by calling pt_is_nested_expr in pt_is_function_index_expr.
*/
qo_expr_segs (env, node, &name_segs_set);
}
}
}
if (!bitset_is_empty (&name_segs_set))
{
for (bitset_index = bitset_iterate (&name_segs_set, &bitset_iter); bitset_index != -1;
bitset_index = bitset_next_member (&bitset_iter))
{
seg = QO_ENV_SEG (env, bitset_index);
node = QO_SEG_PT_NODE (seg);
if (node->node_type == PT_NAME)
{
name_list = parser_append_node (pt_point (parser, node), name_list);
}
else
{
/*
* Each segment must be of type PT_NAME,
* unless it is a function expression for a function-based index that has already been created.
* This is because segments are added using as_attr_list or referenced_attrs,
* which are both lists of type PT_NAME in the build_graph_for_entity function.
*
* Function expressions are added as segments in the build_query_graph_function_index function.
* A function expression is only added if a function-based index with the same expression already exists.
* QO_SEG_FUNC_INDEX(seg) is set to true when a function expression is added to a segment.
*
* Only PT_NAME segments are allowed,
* except for function expressions that match an existing function-based index.
*/
assert_release_error (QO_SEG_FUNC_INDEX (seg));
/* Nothing to do */
}
}
}
bitset_delset (&name_segs_set);
return name_list;
}
/*
* check_merge_xasl () -
* return:
* env(in):
* xasl(in):
*/
static XASL_NODE *
check_merge_xasl (QO_ENV * env, XASL_NODE * xasl)
{
XASL_NODE *merge;
int i, ncols;
/*
* NULL is actually a semi-common case; it can arise under timeout
* conditions, etc.
*/
if (xasl == NULL)
{
return NULL;
}
/*
* The mergelist proc isn't necessarily the first thing on the
* aptr_list; some other procs may have found their way in front of
* it, and that's not incorrect. Search until we find a mergelist
* proc; is there any way to have more than one?
*/
for (merge = xasl->aptr_list; merge && merge->type != MERGELIST_PROC; merge = merge->next)
;
if (merge == NULL
/*
* Make sure there are two things on the aptr list.
*/
|| merge->type != MERGELIST_PROC || merge->aptr_list == NULL /* left */
|| merge->aptr_list->next == NULL /* right */
/*
* Make sure both buildlist gadgets look well-formed.
*/
|| xasl->spec_list == NULL || xasl->val_list == NULL || xasl->outptr_list == NULL
/*
* Make sure the merge_list_info looks plausible.
*/
|| merge->proc.mergelist.outer_xasl == NULL || merge->proc.mergelist.inner_xasl == NULL
|| merge->proc.mergelist.ls_merge.ls_column_cnt <= 0)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "false");
xasl = NULL;
}
if (merge != NULL)
{
ncols = merge->proc.mergelist.ls_merge.ls_column_cnt;
for (i = 0; i < ncols; i++)
{
if (merge->proc.mergelist.ls_merge.ls_outer_column[i] < 0
|| merge->proc.mergelist.ls_merge.ls_inner_column[i] < 0)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "false");
xasl = NULL;
break;
}
}
}
return xasl;
}
/*
* check_hashjoin_xasl() -
* return: Validated XASL node for hash join; NULL on error.
* env(in): Optimization environment.
* xasl(in): XASL node for hash join execution.
*/
static XASL_NODE *
check_hashjoin_xasl (QO_ENV * env, XASL_NODE * xasl)
{
XASL_NODE *hashjoin_xasl;
HASHJOIN_PROC_NODE *proc;
QFILE_LIST_MERGE_INFO *merge_info = NULL;
int value_cnt, value_index;
if (xasl == NULL)
{
/* impossible case */
assert (false);
goto error_exit;
}
/* Validate that the top-level XASL node is well-formed. */
if (xasl->spec_list == NULL || xasl->val_list == NULL || xasl->outptr_list == NULL)
{
goto error_exit;
}
/* The HASHJOIN_PROC XASL node may not appear first in aptr_list.
* Other types of XASL nodes may come before it, which is valid.
* Search until the HASHJOIN_PROC XASL node is found. */
for (hashjoin_xasl = xasl->aptr_list; hashjoin_xasl != NULL; hashjoin_xasl = hashjoin_xasl->next)
{
if (hashjoin_xasl->type == HASHJOIN_PROC)
{
break;
}
}
if (hashjoin_xasl == NULL || hashjoin_xasl->type != HASHJOIN_PROC || hashjoin_xasl->aptr_list == NULL /* outer */
|| hashjoin_xasl->aptr_list->next == NULL /* inner */ )
{
goto error_exit;
}
assert (hashjoin_xasl->aptr_list->next->next == NULL);
proc = &hashjoin_xasl->proc.hashjoin;
if (proc->outer.xasl == NULL || proc->inner.xasl == NULL)
{
goto error_exit;
}
merge_info = &proc->merge_info;
value_cnt = merge_info->ls_column_cnt;
if (value_cnt <= 0)
{
goto error_exit;
}
for (value_index = 0; value_index < value_cnt; value_index++)
{
if (merge_info->ls_outer_column[value_index] < 0 || merge_info->ls_inner_column[value_index] < 0)
{
goto error_exit;
}
}
ASSERT_NO_ERROR_OR_INTERRUPTED ();
return xasl;
error_exit:
assert_release_error (er_errid () != NO_ERROR);
return NULL;
}
/*
* make_outer_instnum () -
* return:
* env(in):
* outer(in):
* plan(in):
*/
static void
make_outer_instnum (QO_ENV * env, QO_PLAN * outer, QO_PLAN * plan)
{
int t;
BITSET_ITERATOR iter;
QO_TERM *termp;
for (t = bitset_iterate (&(plan->sarged_terms), &iter); t != -1; t = bitset_next_member (&iter))
{
termp = QO_ENV_TERM (env, t);
if (is_totally_after_join_term (termp))
{
bitset_add (&(outer->sarged_terms), t);
}
}
}
/*
* gen_outer () -
* return: XASL_NODE *
* env(in): The optimizer environment
* plan(in): The (sub)plan to generate code for
* subqueries(in): The set of subqueries that need to be reevaluated every
* time a new row is produced by plan
* inner_scans(in): A list of scan
* fetches(in): A list of fetch procs that should be executed every time plan
* produces a new row
* xasl(in): The xasl node that is receiving the various procs we generate
*/
static XASL_NODE *
gen_outer (QO_ENV * env, QO_PLAN * plan, BITSET * subqueries, XASL_NODE * inner_scans, XASL_NODE * fetches,
XASL_NODE * xasl)
{
PARSER_CONTEXT *parser;
XASL_NODE *scan, *listfile, *merge, *fetch;
QO_PLAN *outer, *inner;
JOIN_TYPE join_type = NO_JOIN;
QO_TERM *term;
int i;
BITSET_ITERATOR bi;
BITSET new_subqueries;
BITSET fake_subqueries;
BITSET predset;
BITSET taj_terms;
if (env == NULL)
{
return NULL;
}
parser = QO_ENV_PARSER (env);
if (parser == NULL || plan == NULL || xasl == NULL)
{
return NULL;
}
bitset_init (&new_subqueries, env);
bitset_init (&fake_subqueries, env);
bitset_init (&predset, env);
bitset_init (&taj_terms, env);
/* set subqueries */
bitset_assign (&new_subqueries, subqueries);
bitset_union (&new_subqueries, &(plan->subqueries));
/* set predicates */
bitset_assign (&predset, &(plan->sarged_terms));
switch (plan->plan_type)
{
case QO_PLANTYPE_JOIN:
join_type = plan->plan_un.join.join_type;
/*
* The join terms may be EMPTY if this "join" is actually a
* cartesian product, or if it has been implemented as an
* index scan on the inner term (in which case it has already
* been placed in the inner plan as the index term).
*/
bitset_union (&predset, &(plan->plan_un.join.join_terms));
/* outer join could have terms classed as AFTER JOIN TERM; setting after join terms to merged list scan */
if (IS_OUTER_JOIN_TYPE (join_type))
{
bitset_union (&predset, &(plan->plan_un.join.during_join_terms));
bitset_union (&predset, &(plan->plan_un.join.after_join_terms));
}
break;
case QO_PLANTYPE_FOLLOW:
/* include follow edge */
bitset_add (&predset, QO_TERM_IDX (plan->plan_un.follow.path));
break;
default:
break;
}
/*
* Because this routine tail-calls itself in several common cases, we
* could implement those tail calls with a loop back to the beginning
* of the code. However, because these calls won't get very deep in
* practice (~10 deep), I've left the code as is in the interest of
* clarity.
*/
switch (plan->plan_type)
{
case QO_PLANTYPE_SCAN:
/*
* This case only needs to attach the access spec to the incoming
* XASL node. The remainder of the interesting initialization
* (e.g., the val list) of that XASL node is expected to be
* performed by the caller.
*/
xasl = add_access_spec (env, xasl, plan);
xasl = add_scan_proc (env, xasl, inner_scans);
xasl = add_fetch_proc (env, xasl, fetches);
xasl = add_subqueries (env, xasl, &new_subqueries);
break;
case QO_PLANTYPE_SORT:
/*
* check for top level plan
*/
if (plan->top_rooted)
{
if (plan->plan_un.sort.sort_type == SORT_TEMP)
{
; /* nop */
}
else
{
/* SORT-LIMIT plans should never be top rooted */
assert (plan->plan_un.sort.sort_type != SORT_LIMIT);
xasl = gen_outer (env, plan->plan_un.sort.subplan, &new_subqueries, inner_scans, fetches, xasl);
return xasl;
}
}
/*
* If inner_scans is not empty, this plan is really a subplan of
* some outer join node, and we need to make xasl scan the
* contents of the temp file intended to be created by this plan.
* If not, we're really at the "top" of a tree (we haven't gone
* through a join node yet) and we can simply recurse, tacking on
* our sort spec after the recursion. The exception to this rule is
* the SORT-LIMIT plan which must always be working on a temp file.
*/
if (inner_scans != NULL || plan->plan_un.sort.sort_type == SORT_LIMIT)
{
PT_NODE *namelist = NULL;
namelist = make_namelist_from_projected_segs (env, plan);
if (plan->plan_un.sort.sort_type == SORT_LIMIT)
{
listfile = make_sort_limit_proc (env, plan, namelist, xasl);
}
else
{
listfile = make_buildlist_proc (env, namelist);
listfile = gen_outer (env, plan->plan_un.sort.subplan, &EMPTY_SET, NULL, NULL, listfile);
listfile = add_sort_spec (env, listfile, plan, xasl->ordbynum_val, false);
}
xasl = add_uncorrelated (env, xasl, listfile);
xasl = init_list_scan_proc (env, xasl, listfile, namelist, &(plan->sarged_terms), NULL);
if (namelist)
{
parser_free_tree (parser, namelist);
}
xasl = add_scan_proc (env, xasl, inner_scans);
xasl = add_fetch_proc (env, xasl, fetches);
xasl = add_subqueries (env, xasl, &new_subqueries);
}
else
{
xasl = gen_outer (env, plan->plan_un.sort.subplan, &new_subqueries, inner_scans, fetches, xasl);
xasl = add_sort_spec (env, xasl, plan, NULL, true /* add instnum pred */ );
}
break;
case QO_PLANTYPE_JOIN:
outer = plan->plan_un.join.outer;
inner = plan->plan_un.join.inner;
switch (plan->plan_un.join.join_method)
{
case QO_JOINMETHOD_NL_JOIN:
/* check for cselect of method */
if (join_type == JOIN_CSELECT)
{
xasl = pt_gen_simple_merge_plan (parser, QO_ENV_PT_TREE (env), plan, xasl);
break;
}
[[fallthrough]];
case QO_JOINMETHOD_IDX_JOIN:
for (i = bitset_iterate (&(plan->plan_un.join.join_terms), &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
if (QO_IS_FAKE_TERM (term))
{
bitset_union (&fake_subqueries, &(QO_TERM_SUBQUERIES (term)));
}
}
bitset_difference (&new_subqueries, &fake_subqueries);
for (i = bitset_iterate (&predset, &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
if (is_totally_after_join_term (term))
{
bitset_add (&taj_terms, i);
}
else if (is_normal_access_term (term))
{
/* Check if join term can be pushed to key filter instead of sargable terms. The index used for inner
* index scan must include all term segments that belong to inner node */
if (qo_is_index_covering_scan (inner) || qo_plan_multi_range_opt (inner))
{
/* Coverage indexes and indexes using multi range optimization are certified to include segments
* from inner node */
bitset_add (&(inner->plan_un.scan.kf_terms), i);
bitset_difference (&predset, &(inner->plan_un.scan.kf_terms));
}
else if (qo_is_iscan (plan))
{
/* check that index covers all segments */
BITSET term_segs, index_segs;
QO_INDEX_ENTRY *idx_entryp = NULL;
int j;
/* create bitset including index segments */
bitset_init (&index_segs, env);
idx_entryp = inner->plan_un.scan.index->head;
for (j = 0; j < idx_entryp->nsegs; j++)
{
bitset_add (&index_segs, idx_entryp->seg_idxs[j]);
}
/* create bitset including term segments that belong to inner node */
bitset_init (&term_segs, env);
bitset_union (&term_segs, &term->segments);
bitset_intersect (&term_segs, &(QO_NODE_SEGS (plan->plan_un.scan.node)));
/* check that term_segs is covered by index_segs */
bitset_difference (&term_segs, &index_segs);
if (bitset_is_empty (&term_segs))
{
/* safe to add term to key filter terms */
bitset_add (&(inner->plan_un.scan.kf_terms), i);
bitset_difference (&predset, &(inner->plan_un.scan.kf_terms));
}
}
}
}
/* exclude totally after join term and push into inner */
bitset_difference (&predset, &taj_terms);
/* copy hash join term to inner for hash list scan */
if (qo_is_seq_scan (inner) && !bitset_is_empty (&(plan->plan_un.join.hash_terms)))
{
bitset_assign (&(inner->plan_un.scan.hash_terms), &(plan->plan_un.join.hash_terms));
}
/*
* In case of outer join, we should not use sarg terms as key filter terms.
* If not, a term, which should be applied after single scan, can be applied
* during btree_range_search. It means that there can be no records fetched
* by single scan due to key filtering, and null records can be returned
* by scan_handle_single_scan. It might lead to making a wrong result.
*/
scan = gen_inner (env, inner, &predset, &new_subqueries, inner_scans, fetches);
if (scan)
{
if (IS_OUTER_JOIN_TYPE (join_type))
{
mark_access_as_outer_join (parser, scan);
}
}
bitset_assign (&new_subqueries, &fake_subqueries);
make_outer_instnum (env, outer, plan);
xasl = gen_outer (env, outer, &new_subqueries, scan, NULL, xasl);
break;
case QO_JOINMETHOD_MERGE_JOIN:
/*
* The optimizer isn't supposed to produce plans in which a
* merge join isn't "shielded" by a sort (temp file) plan,
* precisely because XASL has a difficult time coping with
* that. Because of that, inner_scans should ALWAYS be NULL
* here.
*/
assert (inner_scans == NULL);
if (inner_scans)
{
xasl = NULL;
break;
}
/*
* In this case, we have to hold on to the accumulated
* predicates and subqueries, and tack them on to the scan
* proc that eventually reads the result of the join. The
* subplans for the two join components should start with
* clean slates.
*/
{
XASL_NODE *left_xasl, *rght_xasl;
PT_NODE *left_elist, *left_nlist, *left_list, *left;
PT_NODE *rght_elist, *rght_nlist, *rght_list, *rght;
PT_NODE *seg_nlist, *pt_expr;
int left_nlen, rght_nlen, seg_nlen;
int *seg_pos_list;
BITSET plan_segs, temp_segs, left_exprs, rght_exprs;
bitset_init (&plan_segs, env);
bitset_init (&temp_segs, env);
bitset_init (&left_exprs, env);
bitset_init (&rght_exprs, env);
/* init */
left_nlist = rght_nlist = left_list = NULL;
left_elist = rght_elist = rght_list = NULL;
seg_nlist = NULL;
seg_pos_list = NULL;
/* find outer/inner segs from expr and name */
bitset_assign (&plan_segs, &((plan->info)->projected_segs));
for (i = bitset_iterate (&predset, &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
if (BITSET_MEMBER (plan->plan_un.join.join_terms, i))
{ /* is m-join edge */
BITSET_CLEAR (temp_segs); /* init */
pt_expr = QO_TERM_PT_EXPR (term);
qo_expr_segs (env, pt_left_part (pt_expr), &temp_segs);
/* is lhs matching outer ? */
if (bitset_intersects (&temp_segs, &((outer->info)->projected_segs)))
{
left = pt_left_part (pt_expr);
rght = pt_right_part (pt_expr);
if (pt_expr->info.expr.op == PT_RANGE && rght != NULL)
{
rght = rght->info.expr.arg1;
}
}
else
{
rght = pt_left_part (pt_expr);
left = pt_right_part (pt_expr);
if (pt_expr->info.expr.op == PT_RANGE && left != NULL)
{
left = left->info.expr.arg1;
}
}
if (!pt_is_name_node (left))
{
/* append to the expr list */
left_elist = parser_append_node (pt_point (parser, left), left_elist);
bitset_add (&left_exprs, i);
}
else
{
bitset_union (&plan_segs, &(QO_TERM_SEGS (term)));
}
if (!pt_is_name_node (rght))
{
/* append to the expr list */
rght_elist = parser_append_node (pt_point (parser, rght), rght_elist);
bitset_add (&rght_exprs, i);
}
else
{
bitset_union (&plan_segs, &(QO_TERM_SEGS (term)));
}
}
else
{
bitset_union (&plan_segs, &(QO_TERM_SEGS (term)));
}
}
/* build outer segs namelist */
bitset_assign (&temp_segs, &((outer->info)->projected_segs)); /* save */
bitset_intersect (&((outer->info)->projected_segs), &plan_segs);
left_nlist = make_namelist_from_projected_segs (env, outer);
left_nlen = pt_length_of_list (left_nlist); /* only names include */
/* make expr, name list */
left_list = parser_append_node (left_nlist, left_elist);
left_xasl = make_buildlist_proc (env, left_list);
left_xasl->parallelism = xasl->parallelism;
left_xasl = gen_outer (env, outer, &EMPTY_SET, NULL, NULL, left_xasl);
bitset_assign (&((outer->info)->projected_segs), &temp_segs); /* restore */
/* build inner segs namelist */
bitset_assign (&temp_segs, &((inner->info)->projected_segs)); /* save */
bitset_intersect (&((inner->info)->projected_segs), &plan_segs);
rght_nlist = make_namelist_from_projected_segs (env, inner);
rght_nlen = pt_length_of_list (rght_nlist); /* only names include */
/* make expr, name list */
rght_list = parser_append_node (rght_nlist, rght_elist);
rght_xasl = make_buildlist_proc (env, rght_list);
rght_xasl->parallelism = xasl->parallelism;
rght_xasl = gen_outer (env, inner, &EMPTY_SET, NULL, NULL, rght_xasl);
bitset_assign (&((inner->info)->projected_segs), &temp_segs); /* restore */
merge =
make_mergelist_proc (env, plan, left_xasl, left_list, &left_exprs, left_elist, rght_xasl, rght_list,
&rght_exprs, rght_elist);
if (merge == NULL)
{
xasl = NULL; /* cause error */
if (left_list)
parser_free_tree (parser, left_list);
if (rght_list)
parser_free_tree (parser, rght_list);
if (seg_nlist)
parser_free_tree (parser, seg_nlist);
if (seg_pos_list)
free_and_init (seg_pos_list);
bitset_delset (&plan_segs);
bitset_delset (&temp_segs);
bitset_delset (&left_exprs);
bitset_delset (&rght_exprs);
break;
}
xasl = add_uncorrelated (env, xasl, merge);
/* filter out already applied terms */
bitset_difference (&predset, &(plan->plan_un.join.join_terms));
if (IS_OUTER_JOIN_TYPE (join_type))
{
bitset_difference (&predset, &(plan->plan_un.join.during_join_terms));
}
/* set referenced segments */
bitset_assign (&plan_segs, &((plan->info)->projected_segs));
for (i = bitset_iterate (&predset, &bi); i != -1; i = bitset_next_member (&bi))
{
term = QO_ENV_TERM (env, i);
bitset_union (&plan_segs, &(QO_TERM_SEGS (term)));
}
/* generate left name list of projected segs */
bitset_assign (&temp_segs, &((outer->info)->projected_segs));
bitset_intersect (&temp_segs, &plan_segs);
seg_nlist = make_namelist_from_bitset (env, &temp_segs);
/* generate right name list of projected segs */
bitset_assign (&temp_segs, &((inner->info)->projected_segs));
bitset_intersect (&temp_segs, &plan_segs);
seg_nlist = parser_append_node (make_namelist_from_bitset (env, &temp_segs), seg_nlist);
seg_nlen = pt_length_of_list (seg_nlist);
/* set used column position in name list and filter out unnecessary join edge segs from projected segs */
if (seg_nlen > 0 && seg_nlen < left_nlen + rght_nlen)
{
QFILE_LIST_MERGE_INFO *ls_merge;
int outer_inner, pos = 0, p;
PT_NODE *attr;
seg_pos_list = (int *) malloc (seg_nlen * sizeof (int));
if (seg_pos_list == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, seg_nlen * sizeof (int));
xasl = NULL; /* cause error */
if (left_list)
{
parser_free_tree (parser, left_list);
}
if (rght_list)
{
parser_free_tree (parser, rght_list);
}
if (seg_nlist)
{
parser_free_tree (parser, seg_nlist);
}
if (seg_pos_list)
{
free_and_init (seg_pos_list);
}
bitset_delset (&plan_segs);
bitset_delset (&temp_segs);
bitset_delset (&left_exprs);
bitset_delset (&rght_exprs);
break;
}
ls_merge = &merge->proc.mergelist.ls_merge;
p = 0; /* init */
for (attr = seg_nlist; attr; attr = attr->next)
{
pos = pt_find_attribute (parser, attr, left_list);
if (pos == -1)
{ /* not found in left */
pos = pt_find_attribute (parser, attr, rght_list);
if (pos == -1)
{ /* not found in right */
break; /* cause error */
}
outer_inner = QFILE_INNER_LIST;
}
else
{
outer_inner = QFILE_OUTER_LIST;
}
for (i = 0; i < ls_merge->ls_pos_cnt; i++)
{
if (ls_merge->ls_outer_inner_list[i] == outer_inner && ls_merge->ls_pos_list[i] == pos)
{ /* found */
seg_pos_list[p] = i; /* save position */
break;
}
}
if (i >= ls_merge->ls_pos_cnt)
{ /* error */
pos = -1;
break; /* cause error */
}
p++; /* increase */
}
if (pos == -1)
{ /* error */
xasl = NULL; /* cause error */
if (left_list)
{
parser_free_tree (parser, left_list);
}
if (rght_list)
{
parser_free_tree (parser, rght_list);
}
if (seg_nlist)
{
parser_free_tree (parser, seg_nlist);
}
if (seg_pos_list)
{
free_and_init (seg_pos_list);
}
bitset_delset (&plan_segs);
bitset_delset (&temp_segs);
bitset_delset (&left_exprs);
bitset_delset (&rght_exprs);
break;
}
}
if (xasl)
{
xasl = init_list_scan_proc (env, xasl, merge, seg_nlist, &predset, seg_pos_list);
xasl = add_fetch_proc (env, xasl, fetches);
xasl = add_subqueries (env, xasl, &new_subqueries);
}
if (left_list)
{
parser_free_tree (parser, left_list);
}
if (rght_list)
{
parser_free_tree (parser, rght_list);
}
if (seg_nlist)
{
parser_free_tree (parser, seg_nlist);
}
if (seg_pos_list)
{
free_and_init (seg_pos_list);
}
bitset_delset (&plan_segs);
bitset_delset (&temp_segs);
bitset_delset (&left_exprs);
bitset_delset (&rght_exprs);
}
/*
* This can be removed after we trust ourselves some more.
*/
xasl = check_merge_xasl (env, xasl);
break;
case QO_JOINMETHOD_HASH_JOIN:
/*
* In this case, we have to hold on to the accumulated predicates and subqueries,
* and tack them on to the scan proc that eventually reads the result of the join.
* The subplans for the two join components should start with clean slates.
*/
xasl = gen_hashjoin (env, plan, &predset, &new_subqueries, inner_scans, fetches, xasl);
break;
default:
break;
}
break;
case QO_PLANTYPE_FOLLOW:
/*
* Add the fetch proc to the head of the list of fetch procs
* before recursing. This means that it will be later in the
* list than fetch procs that are added during the recursion,
* which means that those fetches will happen earlier at runtime,
* which is exactly what we want. Pass it on down to the inner
* call, since we don't know exactly where we want to stick it
* yet.
*/
fetch = make_fetch_proc (env, plan);
fetch = add_fetch_proc (env, fetch, fetches);
fetch = add_subqueries (env, fetch, &new_subqueries);
make_outer_instnum (env, plan->plan_un.follow.head, plan);
xasl = gen_outer (env, plan->plan_un.follow.head, &EMPTY_SET, inner_scans, fetch, xasl);
break;
case QO_PLANTYPE_WORST:
xasl = NULL;
break;
}
bitset_delset (&taj_terms);
bitset_delset (&predset);
bitset_delset (&fake_subqueries);
bitset_delset (&new_subqueries);
return xasl;
}
/*
* gen_hashjoin() -
* return: XASL node for hash join execution; NULL on error.
* env(in): Optimization environment.
* plan(in): Execution plan for hash join.
* pred_set(in): Bitset of predicates (SARGable, join, during-join, after-join).
* subqueries(in): Bitset of correlated subqueries to reevaluate for each produced row.
* inner_scans(in): List of SCAN_PROC XASL nodes to append to the scan_ptr list.
* fetches(in): List of OBJFETCH_PROC XASL nodes to execute for each produced row.
* xasl(in): Top-level XASL node that will include the HASHJOIN_PROC node.
*/
static XASL_NODE *
gen_hashjoin (QO_ENV * env, QO_PLAN * plan, BITSET * pred_set, BITSET * subqueries, XASL_NODE * inner_scans,
XASL_NODE * fetches, XASL_NODE * xasl)
{
QO_PLAN *outer_plan, *inner_plan;
PROJECTION_INFO projection_info;
PROJECTION_PART_INFO *outer_info, *inner_info;
PROJECTION_FINAL_INFO *final_info;
XASL_NODE *hashjoin_xasl = NULL;
XASL_NODE *outer_xasl = NULL, *inner_xasl = NULL;
int parallelism;
int error = NO_ERROR;
assert (env != NULL);
assert (plan != NULL);
assert (plan->plan_type == QO_PLANTYPE_JOIN);
assert (plan->plan_un.join.join_method == QO_JOINMETHOD_HASH_JOIN);
assert (pred_set != NULL);
assert (xasl != NULL);
assert (xasl->selected_upd_list == NULL);
outer_plan = plan->plan_un.join.outer;
inner_plan = plan->plan_un.join.inner;
assert (outer_plan != NULL);
assert (inner_plan != NULL);
switch (plan->parallel_opt_use)
{
case PLAN_PARALLEL_OPT_USE:
parallelism = xasl->parallelism;
break;
case PLAN_PARALLEL_OPT_NO:
case PLAN_PARALLEL_OPT_CANNOT_USE:
parallelism = 0; /* disable */
break;
case PLAN_PARALLEL_OPT_CAN_USE:
parallelism = -1; /* auto-compute */
break;
default:
/* impossible case */
assert (false);
parallelism = 0;
break;
}
/* projection_info */
error = qo_init_projection_info (env, plan, pred_set, &projection_info);
if (error != NO_ERROR)
{
goto error_exit;
}
outer_info = &projection_info.outer;
inner_info = &projection_info.inner;
final_info = &projection_info.final;
/* outer_xasl */
outer_xasl = make_buildlist_proc (env, outer_info->expr_name_list);
if (outer_xasl == NULL)
{
goto error_exit;
}
outer_xasl->parallelism = parallelism;
outer_xasl = gen_outer (env, outer_plan, &EMPTY_SET, NULL, NULL, outer_xasl);
if (outer_xasl == NULL)
{
goto error_exit;
}
outer_xasl->orderby_list = NULL;
/* inner_xasl */
inner_xasl = make_buildlist_proc (env, inner_info->expr_name_list);
if (inner_xasl == NULL)
{
goto error_exit;
}
inner_xasl->parallelism = parallelism;
inner_xasl = gen_outer (env, inner_plan, &EMPTY_SET, NULL, NULL, inner_xasl);
if (inner_xasl == NULL)
{
goto error_exit;
}
inner_xasl->orderby_list = NULL;
/* hashjoin_xasl */
hashjoin_xasl = make_hashjoin_proc (env, plan, outer_xasl, inner_xasl, &projection_info);
if (hashjoin_xasl == NULL)
{
goto error_exit;
}
hashjoin_xasl->parallelism = parallelism;
/* buildlist_proc */
xasl = add_uncorrelated (env, xasl, hashjoin_xasl);
if (xasl == NULL)
{
goto error_exit;
}
xasl = init_list_scan_proc (env, xasl, hashjoin_xasl, final_info->name_list, pred_set, NULL);
xasl = add_scan_proc (env, xasl, inner_scans);
xasl = add_fetch_proc (env, xasl, fetches);
xasl = add_subqueries (env, xasl, subqueries);
xasl = check_hashjoin_xasl (env, xasl);
if (xasl == NULL)
{
goto error_exit;
}
ASSERT_NO_ERROR_OR_INTERRUPTED ();
cleanup:
qo_clear_projection_info (env, &projection_info);
return xasl;
error_exit:
if (pt_has_error (QO_ENV_PARSER (env)))
{
pt_report_to_ersys (QO_ENV_PARSER (env), PT_SEMANTIC);
pt_reset_error (QO_ENV_PARSER (env));
}
assert_release_error (er_errid () != NO_ERROR);
xasl = NULL;
goto cleanup;
}
/*
* gen_inner () -
* return: XASL_NODE *
* env(in): The optimizer environment
* plan(in): The (sub)plan to generate code for
* predset(in): The predicates being pushed down from above
* subqueries(in): The subqueries inherited from enclosing plans
* inner_scans(in): A list of inner scan procs to be put on this scan's
* scan_ptr list
* fetches(in): A list of fetch procs to be run every time plan produces
* a new row
*/
static XASL_NODE *
gen_inner (QO_ENV * env, QO_PLAN * plan, BITSET * predset, BITSET * subqueries, XASL_NODE * inner_scans,
XASL_NODE * fetches)
{
XASL_NODE *scan, *listfile, *fetch;
PT_NODE *namelist;
BITSET new_subqueries;
/*
* All of the rationale about ordering, etc. presented in the
* comments in gen_outer also applies here.
*/
scan = NULL;
bitset_init (&new_subqueries, env);
bitset_assign (&new_subqueries, subqueries);
bitset_union (&new_subqueries, &(plan->subqueries));
switch (plan->plan_type)
{
case QO_PLANTYPE_SCAN:
/*
* For nl-join and idx-join, we push join edge to sarg term of
* inner scan to filter out unsatisfied records earlier.
*/
bitset_union (&(plan->sarged_terms), predset);
scan = init_class_scan_proc (env, scan, plan);
scan = add_scan_proc (env, scan, inner_scans);
scan = add_fetch_proc (env, scan, fetches);
scan = add_subqueries (env, scan, &new_subqueries);
break;
case QO_PLANTYPE_FOLLOW:
#if 1
/*
* We have to take care of any sargs that have been passed down
* from above. Go ahead and destructively union them into this
* plan's sarg set: no one will ever look at the plan again
* anyway.
*/
bitset_union (&(plan->sarged_terms), predset);
fetch = make_fetch_proc (env, plan);
fetch = add_fetch_proc (env, fetch, fetches);
fetch = add_subqueries (env, fetch, &new_subqueries);
/*
* Now proceed on with inner generation, passing the augmented
* list of fetch procs.
*/
scan = gen_inner (env, plan->plan_un.follow.head, &EMPTY_SET, &EMPTY_SET, inner_scans, fetch);
break;
#else
/* Fall through */
#endif
case QO_PLANTYPE_JOIN:
/*
* These aren't supposed to show up, but if they do just take the
* conservative approach of treating them like a sort and
* whacking their results into a temporary file, and then scan
* that file.
*/
case QO_PLANTYPE_SORT:
/* check for sort type */
QO_ASSERT (env, plan->plan_un.sort.sort_type == SORT_TEMP);
namelist = make_namelist_from_projected_segs (env, plan);
listfile = make_buildlist_proc (env, namelist);
listfile = gen_outer (env, plan, &EMPTY_SET, NULL, NULL, listfile);
scan = make_scan_proc (env);
scan = init_list_scan_proc (env, scan, listfile, namelist, predset, NULL);
if (namelist)
{
parser_free_tree (env->parser, namelist);
}
scan = add_scan_proc (env, scan, inner_scans);
scan = add_fetch_proc (env, scan, fetches);
scan = add_subqueries (env, scan, &new_subqueries);
scan = add_uncorrelated (env, scan, listfile);
break;
case QO_PLANTYPE_WORST:
/*
* This case should never arise.
*/
scan = NULL;
break;
}
bitset_delset (&new_subqueries);
return scan;
}
/*
* preserve_info () -
* return: XASL_NODE *
* env(in): The optimizer environment
* plan(in): The plan from which the xasl tree was generated
* xasl(in): The generated xasl tree
*/
static XASL_NODE *
preserve_info (QO_ENV * env, QO_PLAN * plan, XASL_NODE * xasl)
{
QO_SUMMARY *summary;
PARSER_CONTEXT *parser;
PT_NODE *select;
if (xasl != NULL)
{
parser = QO_ENV_PARSER (env);
select = QO_ENV_PT_TREE (env);
summary = (QO_SUMMARY *) parser_alloc (parser, sizeof (QO_SUMMARY));
if (summary)
{
summary->fixed_cpu_cost = plan->fixed_cpu_cost;
summary->fixed_io_cost = plan->fixed_io_cost;
summary->variable_cpu_cost = plan->variable_cpu_cost;
summary->variable_io_cost = plan->variable_io_cost;
summary->cardinality = (plan->info)->group_rows;
summary->xasl = xasl;
select->info.query.q.select.qo_summary = summary;
}
else
{
xasl = NULL;
}
/* save info for derived table size estimation */
if (plan != NULL && xasl != NULL)
{
xasl->projected_size = (plan->info)->projected_size;
/* If no aggregate function, group_rows is the same as cardinality. */
xasl->cardinality = (plan->info)->group_rows;
}
}
return xasl;
}
/*
* qo_to_xasl () -
* return: XASL_NODE *
* plan(in): The (already optimized) select statement to generate code for
* xasl(in): The XASL block for the root of the plan
*
* Note: Create an XASL tree from the QO_PLAN tree associated with
* 'select'. In essence, this takes the entity specs from the
* from part of 'select' and produces a collection of access
* specs that will do the right thing. It also distributes the
* predicates in the where part across those access specs. The
* caller shouldn't have to do anything for the from part or the
* where part, but it must still take care of all of the other
* grunge, such as setting up the code for the select list
* expressions, etc.
*/
xasl_node *
qo_to_xasl (QO_PLAN * plan, xasl_node * xasl)
{
QO_ENV *env;
XASL_NODE *lastxasl;
if (plan && xasl && (env = (plan->info)->env))
{
xasl = gen_outer (env, plan, &EMPTY_SET, NULL, NULL, xasl);
lastxasl = xasl;
while (lastxasl)
{
/*
* Don't consider only scan pointers here; it's quite
* possible that the correlated subqueries might depend on
* values retrieved by a fetch proc that lives on an fptr.
*/
if (lastxasl->scan_ptr)
{
lastxasl = lastxasl->scan_ptr;
}
else if (lastxasl->fptr_list)
{
lastxasl = lastxasl->fptr_list;
}
else
{
break;
}
}
(void) pt_set_dptr (env->parser, env->pt_tree->info.query.q.select.list, lastxasl, MATCH_ALL);
xasl = preserve_info (env, plan, xasl);
}
else
{
xasl = NULL;
}
if (xasl == NULL)
{
int level;
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "xasl != NULL");
qo_get_optimization_param (&level, QO_PARAM_LEVEL);
if (PLAN_DUMP_ENABLED (level))
{
fprintf (stderr, "*** XASL generation failed ***\n");
}
#if defined(CUBRID_DEBUG)
else
{
fprintf (stderr, "*** XASL generation failed ***\n");
fprintf (stderr, "*** %s ***\n", er_msg ());
}
#endif /* CUBRID_DEBUG */
}
return xasl;
}
/*
* qo_plan_iscan_sort_list () - get after index scan PT_SORT_SPEC list
* return: SORT_LIST *
* plan(in): QO_PLAN
*/
PT_NODE *
qo_plan_iscan_sort_list (QO_PLAN * plan)
{
return plan->iscan_sort_list;
}
/*
* qo_plan_skip_orderby () - check the plan info for order by
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_plan_skip_orderby (QO_PLAN * plan)
{
return ((plan->plan_type == QO_PLANTYPE_SORT
&& (plan->plan_un.sort.sort_type == SORT_DISTINCT
|| plan->plan_un.sort.sort_type == SORT_ORDERBY)) ? false : true);
}
/*
* qo_plan_skip_groupby () - check the plan info for order by
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_plan_skip_groupby (QO_PLAN * plan)
{
return (plan->plan_type == QO_PLANTYPE_SCAN && plan->plan_un.scan.index
&& plan->plan_un.scan.index->head->groupby_skip) ? true : false;
}
/*
* qo_is_index_covering_scan () - check the plan info for covering index scan
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_is_index_covering_scan (QO_PLAN * plan)
{
assert (plan != NULL);
assert (plan->info != NULL);
assert (plan->info->env != NULL);
if (qo_is_interesting_order_scan (plan))
{
if (plan->plan_un.scan.index_cover == true)
{
assert (plan->plan_un.scan.index->head);
assert (plan->plan_un.scan.index->head->cover_segments);
assert (!qo_is_prefix_index (plan->plan_un.scan.index->head));
return true;
}
}
return false;
}
/*
* qo_is_index_iss_scan () - check the plan info for index skip scan
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_is_index_iss_scan (QO_PLAN * plan)
{
assert (plan != NULL);
assert (plan->info != NULL);
assert (plan->info->env != NULL);
if (qo_is_interesting_order_scan (plan))
{
if (plan->plan_un.scan.index_iss == true)
{
assert (plan->plan_un.scan.index->head);
assert (plan->plan_un.scan.index->head->is_iss_candidate);
assert (QO_ENTRY_MULTI_COL (plan->plan_un.scan.index->head));
assert (plan->plan_un.scan.index_loose == false);
assert (plan->multi_range_opt_use != PLAN_MULTI_RANGE_OPT_USE);
assert (!qo_is_filter_index (plan->plan_un.scan.index->head));
return true;
}
}
return false;
}
/*
* qo_is_index_loose_scan () - check the plan info for loose index scan
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_is_index_loose_scan (QO_PLAN * plan)
{
assert (plan != NULL);
assert (plan->info != NULL);
assert (plan->info->env != NULL);
if (qo_is_iscan (plan))
{
if (plan->plan_un.scan.index_loose == true)
{
assert (plan->plan_un.scan.index->head);
assert (plan->plan_un.scan.index->head->ils_prefix_len > 0);
assert (QO_ENTRY_MULTI_COL (plan->plan_un.scan.index->head));
assert (plan->plan_un.scan.index_cover == true);
assert (!qo_is_prefix_index (plan->plan_un.scan.index->head));
assert (plan->plan_un.scan.index_iss == false);
assert (plan->multi_range_opt_use != PLAN_MULTI_RANGE_OPT_USE);
return true;
}
}
return false;
}
/*
* qo_is_index_mro_scan () - check the plan info for multi range opt scan
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_is_index_mro_scan (QO_PLAN * plan)
{
assert (plan != NULL);
assert (plan->info != NULL);
assert (plan->info->env != NULL);
if (qo_is_interesting_order_scan (plan))
{
if (plan->multi_range_opt_use == PLAN_MULTI_RANGE_OPT_USE)
{
assert (plan->plan_un.scan.index->head);
assert (QO_ENTRY_MULTI_COL (plan->plan_un.scan.index->head));
assert (plan->plan_un.scan.index_iss == false);
assert (plan->plan_un.scan.index_loose == false);
assert (!qo_is_filter_index (plan->plan_un.scan.index->head));
return true;
}
}
return false;
}
/*
* qo_plan_multi_range_opt () - check the plan info for multi range opt
* return: true/false
* plan(in): QO_PLAN
*/
bool
qo_plan_multi_range_opt (QO_PLAN * plan)
{
assert (plan != NULL);
assert (plan->info != NULL);
assert (plan->info->env != NULL);
if (plan != NULL && plan->multi_range_opt_use == PLAN_MULTI_RANGE_OPT_USE)
{
#if !defined(NDEBUG)
if (qo_is_interesting_order_scan (plan))
{
assert (plan->plan_un.scan.index->head);
assert (QO_ENTRY_MULTI_COL (plan->plan_un.scan.index->head));
assert (plan->plan_un.scan.index_iss == false);
assert (plan->plan_un.scan.index_loose == false);
assert (!qo_is_filter_index (plan->plan_un.scan.index->head));
}
#endif
return true;
}
return false;
}
/******************************************************************************
* qo_xasl support functions
*****************************************************************************/
/*
* qo_get_xasl_index_info () -
* return: QO_XASL_INDEX_INFO structure which contains index information
* needed for XASL generation
* env(in): The environment
* plan(in): The plan from which to initialize the scan proc
*
* Note: The term expression array <term_exprs> is returned in index
* definition order. i.e. For multi-column indexes, you can create
* a sequence key from the expression array in the order that they
* are returned.
*/
static QO_XASL_INDEX_INFO *
qo_get_xasl_index_info (QO_ENV * env, QO_PLAN * plan)
{
int nterms, nsegs, nkfterms, multi_term_num;;
QO_NODE_INDEX_ENTRY *ni_entryp;
QO_INDEX_ENTRY *index_entryp;
QO_XASL_INDEX_INFO *index_infop;
int t, i, j, pos;
BITSET_ITERATOR iter;
QO_TERM *termp;
BITSET multi_col_segs, multi_col_range_segs, index_segs;
if (!qo_is_interesting_order_scan (plan))
{
return NULL; /* give up */
}
assert (plan->plan_un.scan.index != NULL);
bitset_init (&multi_col_segs, env);
bitset_init (&multi_col_range_segs, env);
bitset_init (&index_segs, env);
/* if no index scan terms, no index scan */
nterms = bitset_cardinality (&(plan->plan_un.scan.terms));
nkfterms = bitset_cardinality (&(plan->plan_un.scan.kf_terms));
/* pointer to QO_NODE_INDEX_ENTRY structure in QO_PLAN */
ni_entryp = plan->plan_un.scan.index;
/* pointer to linked list of index node, 'head' field(QO_INDEX_ENTRY structure) of QO_NODE_INDEX_ENTRY */
index_entryp = (ni_entryp)->head;
/* number of indexed segments */
nsegs = index_entryp->nsegs; /* nsegs == nterms ? */
/* support also full range indexes */
if (nterms <= 0 && nkfterms <= 0 && bitset_cardinality (&(plan->sarged_terms)) == 0)
{
if (qo_is_filter_index (index_entryp) || qo_is_index_loose_scan (plan) || qo_is_iscan_from_groupby (plan)
|| qo_is_iscan_from_orderby (plan)
|| PT_SPEC_SPECIAL_INDEX_SCAN (QO_NODE_ENTITY_SPEC (plan->plan_un.scan.node)))
{
/* Do not return if: 1. filtered index. 2. skip group by or skip order by 3. loose scan. 4. scan for b-tree
* node info or key info. */
;
}
else
{ /* is invalid case */
assert (false);
return NULL; /* give up */
}
}
/* allocate QO_XASL_INDEX_INFO structure */
index_infop = (QO_XASL_INDEX_INFO *) malloc (sizeof (QO_XASL_INDEX_INFO));
if (index_infop == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, sizeof (QO_XASL_INDEX_INFO));
goto error;
}
if (qo_is_index_iss_scan (plan))
{
assert (index_entryp->is_iss_candidate);
/* allow space for the first element (NULL actually), for instance in term_exprs */
nterms++;
}
/* check multi column index term */
multi_term_num =
qo_get_multi_col_range_segs (env, plan, index_entryp, &multi_col_segs, &multi_col_range_segs, &index_segs);
if (multi_term_num != -1)
{
/* case of term having multiple columns */
termp = QO_ENV_TERM (env, multi_term_num);
if (!bitset_subset (&index_segs, &multi_col_segs))
{
/* need to add sarg term (data filter) */
index_infop->need_copy_multi_range_term = multi_term_num;
index_infop->need_copy_to_sarg_term = true;
}
else if (!bitset_subset (&multi_col_range_segs, &multi_col_segs)
|| QO_TERM_IS_FLAGED (termp, QO_TERM_MULTI_COLL_CONST))
{
/* need to add key filter term (index key filter) */
index_infop->need_copy_multi_range_term = multi_term_num;
index_infop->need_copy_to_sarg_term = false;
}
else
{
/* don't need to force-copy any filter */
index_infop->need_copy_multi_range_term = -1;
index_infop->need_copy_to_sarg_term = false;
}
/* add multi column term's segs ex) index(a,b,c), (a,b) in .. and c = 1 : nterms = 2 + 2 -1 */
nterms = nterms + bitset_cardinality (&multi_col_range_segs) - 1;
}
else
{
index_infop->need_copy_multi_range_term = -1;
index_infop->need_copy_to_sarg_term = false;
}
if (nterms == 0)
{
index_infop->nterms = 0;
index_infop->term_exprs = NULL;
index_infop->multi_col_pos = NULL;
index_infop->ni_entry = ni_entryp;
return index_infop;
}
index_infop->nterms = nterms;
index_infop->term_exprs = (PT_NODE **) malloc (nterms * sizeof (PT_NODE *));
index_infop->multi_col_pos = (int *) malloc (nterms * sizeof (int));
if (index_infop->term_exprs == NULL)
{
er_set (ER_ERROR_SEVERITY, ARG_FILE_LINE, ER_OUT_OF_VIRTUAL_MEMORY, 1, nterms * sizeof (PT_NODE *));
goto error;
}
if (qo_is_index_iss_scan (plan))
{
assert (index_entryp->is_iss_candidate);
index_infop->term_exprs[0] = NULL;
index_infop->multi_col_pos[0] = -1;
}
index_infop->ni_entry = ni_entryp;
/* Make 'term_expr[]' array from the given index terms in order of the 'seg_idx[]' array of the associated index. */
/* for all index scan terms */
for (t = bitset_iterate (&(plan->plan_un.scan.terms), &iter); t != -1; t = bitset_next_member (&iter))
{
/* pointer to QO_TERM denoted by number 't' */
termp = QO_ENV_TERM (env, t);
if (!QO_TERM_IS_FLAGED (termp, QO_TERM_MULTI_COLL_PRED))
{
/* Find the matching segment in the segment index array to determine the array position to store the expression.
* We're using the 'index_seg[]' array of the term to find its segment index */
pos = -1;
for (i = 0; i < termp->can_use_index && pos == -1; i++)
{
for (j = 0; j < nsegs; j++)
{
if (i >= (int) (sizeof (termp->index_seg) / sizeof (termp->index_seg[0])))
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "false");
goto error;
}
if ((index_entryp->seg_idxs[j]) == QO_SEG_IDX (termp->index_seg[i]))
{
pos = j;
break;
}
}
}
/* always, pos != -1 and 0 <= pos < nterms */
assert (pos >= 0 && pos < nterms);
if (pos < 0 || pos >= nterms)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "pos >= 0 and pos < nterms");
goto error;
}
/* if the index is Index Skip Scan, the first column should have never been found in a term */
assert (!qo_is_index_iss_scan (plan) || pos != 0);
index_infop->term_exprs[pos] = QO_TERM_PT_EXPR (termp);
index_infop->multi_col_pos[pos] = -1;
}
else
{
/* case of multi column term */
/* not need can_use_index's iteration because multi col term having other node's segments isn't indexable */
/* ex) (a.col1,a.col2) in ((a.col1,b.col2)) is not indexable */
for (i = 0; i < termp->multi_col_cnt; i++)
{
pos = -1;
for (j = 0; j < nsegs; j++)
{
if ((index_entryp->seg_idxs[j]) == (termp->multi_col_segs[i]))
{
pos = j;
break;
}
}
/* if the index is Index Skip Scan, the first column should have never been found in a term */
assert (!qo_is_index_iss_scan (plan) || pos != 0);
if (pos != -1 && BITSET_MEMBER (multi_col_range_segs, index_entryp->seg_idxs[pos]))
{
/* always, pos != -1 and 0 <= pos < nterms */
assert (pos >= 0 && pos < nterms);
if (pos < 0 || pos >= nterms)
{
er_set (ER_WARNING_SEVERITY, ARG_FILE_LINE, ER_FAILED_ASSERTION, 1, "pos >= 0 and pos < nterms");
goto error;
}
index_infop->term_exprs[pos] = QO_TERM_PT_EXPR (termp);
index_infop->multi_col_pos[pos] = i;
}
}
}
}
bitset_delset (&multi_col_segs);
bitset_delset (&multi_col_range_segs);
bitset_delset (&index_segs);
/* return QO_XASL_INDEX_INFO */
return index_infop;
error:
/* malloc error */
qo_free_xasl_index_info (env, index_infop);
return NULL;
}
/*
* qo_free_xasl_index_info () -
* return: void
* env(in): The environment
* info(in): Information structure (QO_XASL_INDEX_INFO)
*
* Note: Free the memory occupied by the QO_XASL_INDEX_INFO
*/
static void
qo_free_xasl_index_info (QO_ENV * env, QO_XASL_INDEX_INFO * info)
{
if (info)
{
if (info->term_exprs)
{
free_and_init (info->term_exprs);
}
/* DEALLOCATE (env, info->term_exprs); */
if (info->multi_col_pos)
{
free_and_init (info->multi_col_pos);
}
/* DEALLOCATE (env, info->multi_col_pos); */
free_and_init (info);
/* DEALLOCATE(env, info); */
}
}
/*
* qo_xasl_get_num_terms () - Return the number of terms in the array
* return: int
* info(in): Pointer to info structure
*/
int
qo_xasl_get_num_terms (QO_XASL_INDEX_INFO * info)
{
return info->nterms;
}
/*
* qo_xasl_get_terms () - Return a point to the NULL terminated list
* of TERM expressions
* return: PT_NODE **
* info(in): Pointer to info structure
*/
PT_NODE **
qo_xasl_get_terms (QO_XASL_INDEX_INFO * info)
{
return info->term_exprs;
}
/*
* qo_add_hq_iterations_access_spec () - adds hierarchical query iterations
* access spec on single table
* return:
* plan(in):
* xasl(in):
*/
xasl_node *
qo_add_hq_iterations_access_spec (QO_PLAN * plan, xasl_node * xasl)
{
PARSER_CONTEXT *parser;
QO_ENV *env;
PT_NODE *class_spec;
PT_NODE *key_pred = NULL;
PT_NODE *access_pred = NULL;
PT_NODE *if_pred = NULL;
QO_XASL_INDEX_INFO *index_info;
if (!plan)
{
return NULL;
}
if (plan->plan_type == QO_PLANTYPE_SORT)
{
QO_PLAN *subplan = plan->plan_un.sort.subplan;
while (subplan && subplan->plan_type == QO_PLANTYPE_SORT)
{
subplan = subplan->plan_un.sort.subplan;
}
if (subplan && subplan->plan_type == QO_PLANTYPE_SCAN)
{
plan = subplan;
}
else
{
return NULL;
}
}
else if (plan->plan_type != QO_PLANTYPE_SCAN)
{
return NULL;
}
class_spec = plan->plan_un.scan.node->entity_spec;
env = plan->info->env;
parser = QO_ENV_PARSER (env);
index_info = qo_get_xasl_index_info (env, plan);
make_pred_from_plan (env, plan, &key_pred, &access_pred, index_info, NULL);
xasl->spec_list = pt_to_spec_list (parser, class_spec, key_pred, access_pred, plan, index_info, NULL, NULL);
if_pred = make_if_pred_from_plan (env, plan);
if (if_pred)
{
xasl->if_pred = pt_to_pred_expr (parser, if_pred);
}
/* free pointer node list */
parser_free_tree (parser, key_pred);
parser_free_tree (parser, access_pred);
parser_free_tree (parser, if_pred);
qo_free_xasl_index_info (env, index_info);
if (xasl->spec_list == NULL)
{
return NULL;
}
return xasl;
}
/*
* regu_ptr_list_create () - creates and initializes a REGU_PTR_LIST - a linked
* list of POINTERS to REGU VARIBLES
* return: a new node, or NULL on error
*/
static REGU_PTR_LIST
regu_ptr_list_create ()
{
REGU_PTR_LIST p;
p = (REGU_PTR_LIST) db_private_alloc (NULL, sizeof (struct regu_ptr_list_node));
if (!p)
{
return NULL;
}
p->next = NULL;
p->var_p = NULL;
return p;
}
/*
* regu_ptr_list_free () - iterates over a linked list of regu var pointers
* and frees each node (the containing node, NOT the
* actual REGU_VARIABLE).
* list(in): the REGU_PTR_LIST. It can be NULL.
* return:
*/
static void
regu_ptr_list_free (REGU_PTR_LIST list)
{
REGU_PTR_LIST next;
while (list)
{
next = list->next;
db_private_free (NULL, list);
list = next;
}
}
/*
* regu_ptr_list_add_regu () - adds a pointer to a regu variable to the list,
* initializing the list if required.
*
* regu(in): REGU_VAR ptr to add to the head of the list
* list(in): the initial list. It can be NULL - in this case it will be initialised.
* return: the list with the added element, or NULL on error.
*/
static REGU_PTR_LIST
regu_ptr_list_add_regu (REGU_VARIABLE * var_p, REGU_PTR_LIST list)
{
REGU_PTR_LIST node;
if (!var_p)
{
return list;
}
node = (REGU_PTR_LIST) db_private_alloc (NULL, sizeof (struct regu_ptr_list_node));
if (!node)
{
regu_ptr_list_free (list);
return NULL;
}
node->next = list;
node->var_p = var_p;
return node;
}
static bool
qo_validate_regu_var_for_limit (REGU_VARIABLE * var_p)
{
if (var_p == NULL)
{
return true;
}
if (var_p->type == TYPE_DBVAL)
{
return true;
}
else if (var_p->type == TYPE_POS_VALUE)
{
return true;
}
else if (var_p->type == TYPE_INARITH && var_p->value.arithptr)
{
struct arith_list_node *aptr = var_p->value.arithptr;
return (qo_validate_regu_var_for_limit (aptr->leftptr) && qo_validate_regu_var_for_limit (aptr->rightptr)
&& qo_validate_regu_var_for_limit (aptr->thirdptr));
}
return false;
}
/*
* qo_get_limit_from_eval_term () - get lower and upper limits from an
* eval term involving instnum
* return: true on success.
* parser(in):
* pred(in): the predicate expression.
* lower(out): lower limit node
* upper(out): upper limit node
*
* Note: handles terms of the form:
* instnum rel_op value/hostvar
* value/hostvar rel_op instnum
*/
static bool
qo_get_limit_from_eval_term (PARSER_CONTEXT * parser, PRED_EXPR * pred, REGU_PTR_LIST * lower, REGU_PTR_LIST * upper)
{
REGU_VARIABLE *lhs, *rhs;
REL_OP op;
PT_NODE *node_one = NULL;
TP_DOMAIN *dom_bigint = tp_domain_resolve_default (DB_TYPE_BIGINT);
REGU_VARIABLE *regu_one, *regu_low;
if (pred == NULL || pred->type != T_EVAL_TERM || pred->pe.m_eval_term.et_type != T_COMP_EVAL_TERM)
{
return false;
}
lhs = pred->pe.m_eval_term.et.et_comp.lhs;
rhs = pred->pe.m_eval_term.et.et_comp.rhs;
op = pred->pe.m_eval_term.et.et_comp.rel_op;
if (!lhs || !rhs)
{
return false;
}
if (op != R_LE && op != R_LT && op != R_GE && op != R_GT && op != R_EQ)
{
return false;
}
/* the TYPE_CONSTANT regu variable must be instnum, otherwise it would not be accepted by the parser */
/* switch the ops to transform into instnum rel_op value/hostvar */
if (rhs->type == TYPE_CONSTANT)
{
rhs = pred->pe.m_eval_term.et.et_comp.lhs;
lhs = pred->pe.m_eval_term.et.et_comp.rhs;
switch (op)
{
case R_LE:
op = R_GE;
break;
case R_LT:
op = R_GT;
break;
case R_GE:
op = R_LE;
break;
case R_GT:
op = R_LT;
break;
default:
break;
}
}
if (lhs->type != TYPE_CONSTANT || !qo_validate_regu_var_for_limit (rhs))
{
return false;
}
/* Bring every accepted relation to a form similar to lower < rownum <= upper. */
switch (op)
{
case R_EQ:
/* decrement node value for lower, but remember current value for upper */
node_one = pt_make_integer_value (parser, 1);
if (!node_one)
{
return false;
}
if (!(regu_one = pt_to_regu_variable (parser, node_one, UNBOX_AS_VALUE))
|| !(regu_low = pt_make_regu_arith (rhs, regu_one, NULL, T_SUB, dom_bigint)))
{
parser_free_node (parser, node_one);
return false;
}
regu_low->domain = dom_bigint;
*lower = regu_ptr_list_add_regu (regu_low, *lower);
*upper = regu_ptr_list_add_regu (rhs, *upper);
break;
case R_LE:
*upper = regu_ptr_list_add_regu (rhs, *upper);
break;
case R_LT:
/* decrement node value */
node_one = pt_make_integer_value (parser, 1);
if (!node_one)
{
return false;
}
if (!(regu_one = pt_to_regu_variable (parser, node_one, UNBOX_AS_VALUE))
|| !(regu_low = pt_make_regu_arith (rhs, regu_one, NULL, T_SUB, dom_bigint)))
{
parser_free_node (parser, node_one);
return false;
}
regu_low->domain = dom_bigint;
*upper = regu_ptr_list_add_regu (regu_low, *upper);
break;
case R_GE:
/* decrement node value for lower */
node_one = pt_make_integer_value (parser, 1);
if (!node_one)
{
return false;
}
if (!(regu_one = pt_to_regu_variable (parser, node_one, UNBOX_AS_VALUE))
|| !(regu_low = pt_make_regu_arith (rhs, regu_one, NULL, T_SUB, dom_bigint)))
{
parser_free_node (parser, node_one);
return false;
}
regu_low->domain = dom_bigint;
*lower = regu_ptr_list_add_regu (regu_low, *lower);
break;
case R_GT:
/* leave node value as it is */
*lower = regu_ptr_list_add_regu (rhs, *lower);
break;
default:
break;
}
if (node_one)
{
parser_free_node (parser, node_one);
}
return true;
}
/*
* qo_get_limit_from_instnum_pred () - get lower and upper limits from an
* instnum predicate
* return: true if successful
* parser(in):
* pred(in): the predicate expression
* lower(out): lower limit node
* upper(out): upper limit node
*/
static bool
qo_get_limit_from_instnum_pred (PARSER_CONTEXT * parser, PRED_EXPR * pred, REGU_PTR_LIST * lower, REGU_PTR_LIST * upper)
{
if (pred == NULL)
{
return false;
}
if (pred->type == T_PRED && pred->pe.m_pred.bool_op == B_AND)
{
return (qo_get_limit_from_instnum_pred (parser, pred->pe.m_pred.lhs, lower, upper)
&& qo_get_limit_from_instnum_pred (parser, pred->pe.m_pred.rhs, lower, upper));
}
if (pred->type == T_EVAL_TERM)
{
return qo_get_limit_from_eval_term (parser, pred, lower, upper);
}
return false;
}
/*
* qo_get_key_limit_from_instnum () - creates a keylimit node from an
* instnum predicate, if possible.
* return: a new node, or NULL if a keylimit node cannot be
* initialized (not necessarily an error)
* parser(in): the parser context
* plan (in): the query plan
* xasl (in): the full XASL node
*/
QO_LIMIT_INFO *
qo_get_key_limit_from_instnum (PARSER_CONTEXT * parser, QO_PLAN * plan, xasl_node * xasl)
{
REGU_PTR_LIST lower = NULL, upper = NULL, ptr = NULL;
QO_LIMIT_INFO *limit_infop = NULL;
TP_DOMAIN *dom_bigint = tp_domain_resolve_default (DB_TYPE_BIGINT);
if (xasl == NULL || xasl->instnum_pred == NULL || plan == NULL)
{
return NULL;
}
switch (plan->plan_type)
{
case QO_PLANTYPE_SCAN:
if (!qo_is_interesting_order_scan (plan))
{
return NULL;
}
break;
case QO_PLANTYPE_JOIN:
/* only allow inner joins */
if (plan->plan_un.join.join_type != JOIN_INNER)
{
return NULL;
}
if (plan->plan_un.join.join_method == QO_JOINMETHOD_HASH_JOIN)
{
return NULL;
}
break;
default:
return NULL;
}
/* get lower and upper limits */
if (!qo_get_limit_from_instnum_pred (parser, xasl->instnum_pred, &lower, &upper))
{
return NULL;
}
/* not having upper limit is not helpful */
if (upper == NULL)
{
regu_ptr_list_free (lower);
return NULL;
}
limit_infop = (QO_LIMIT_INFO *) db_private_alloc (NULL, sizeof (QO_LIMIT_INFO));
if (limit_infop == NULL)
{
regu_ptr_list_free (lower);
regu_ptr_list_free (upper);
return NULL;
}
limit_infop->lower = limit_infop->upper = NULL;
/* upper limit */
limit_infop->upper = upper->var_p;
ptr = upper->next;
while (ptr)
{
limit_infop->upper = pt_make_regu_arith (limit_infop->upper, ptr->var_p, NULL, T_LEAST, dom_bigint);
if (!limit_infop->upper)
{
regu_ptr_list_free (upper);
regu_ptr_list_free (lower);
db_private_free (NULL, limit_infop);
return NULL;
}
limit_infop->upper->domain = dom_bigint;
ptr = ptr->next;
}
regu_ptr_list_free (upper);
if (lower)
{
limit_infop->lower = lower->var_p;
ptr = lower->next;
while (ptr)
{
limit_infop->lower = pt_make_regu_arith (limit_infop->lower, ptr->var_p, NULL, T_GREATEST, dom_bigint);
if (!limit_infop->lower)
{
regu_ptr_list_free (lower);
db_private_free (NULL, limit_infop);
return NULL;
}
limit_infop->lower->domain = dom_bigint;
ptr = ptr->next;
}
regu_ptr_list_free (lower);
}
return limit_infop;
}
/*
* qo_get_key_limit_from_ordbynum () - creates a keylimit node from an
* orderby_num predicate, if possible.
* return: a new node, or NULL if a keylimit node cannot be
* initialized (not necessarily an error)
* parser(in): the parser context
* plan (in): the query plan
* xasl (in): the full XASL node
* ignore_lower (in): generate key limit even if ordbynum has a lower limit
*/
QO_LIMIT_INFO *
qo_get_key_limit_from_ordbynum (PARSER_CONTEXT * parser, QO_PLAN * plan, xasl_node * xasl, bool ignore_lower)
{
REGU_PTR_LIST lower = NULL, upper = NULL, ptr = NULL;
QO_LIMIT_INFO *limit_infop;
TP_DOMAIN *dom_bigint = tp_domain_resolve_default (DB_TYPE_BIGINT);
if (xasl == NULL || xasl->ordbynum_pred == NULL)
{
return NULL;
}
/* get lower and upper limits */
if (!qo_get_limit_from_instnum_pred (parser, xasl->ordbynum_pred, &lower, &upper))
{
return NULL;
}
/* having a lower limit, or not having upper limit is not helpful */
if (upper == NULL || (lower != NULL && !ignore_lower))
{
regu_ptr_list_free (lower);
regu_ptr_list_free (upper);
return NULL;
}
limit_infop = (QO_LIMIT_INFO *) db_private_alloc (NULL, sizeof (QO_LIMIT_INFO));
if (!limit_infop)
{
regu_ptr_list_free (lower);
regu_ptr_list_free (upper);
return NULL;
}
limit_infop->lower = limit_infop->upper = NULL;
/* upper limit */
limit_infop->upper = upper->var_p;
ptr = upper->next;
while (ptr)
{
limit_infop->upper = pt_make_regu_arith (limit_infop->upper, ptr->var_p, NULL, T_LEAST, dom_bigint);
if (!limit_infop->upper)
{
regu_ptr_list_free (upper);
regu_ptr_list_free (lower);
db_private_free (NULL, limit_infop);
return NULL;
}
limit_infop->upper->domain = dom_bigint;
ptr = ptr->next;
}
regu_ptr_list_free (upper);
regu_ptr_list_free (lower);
return limit_infop;
}
/*
* qo_check_iscan_for_multi_range_opt () - check that current index scan can
* use multi range key-limit
* optimization
*
* return : true/false
* plan (in) : index scan plan
*
* Note: The optimization requires a series of conditions to be met:
* For single table case:
* - valid order by for condition
* -> the upper limit has to be less than multi_range_opt_limit
* system parameter
* -> the expression should look like: LIMIT n,
ORDERBY_NUM </<= n,
* n > ORDERBY_NUM
* or AND operator on ORDERBY_NUM valid expressions.
* -> lower limit is not allowed
* - index scan with no data filter
* - order by columns should occupy consecutive positions in index and
* the ordering should match all columns (or all should be reversed)
* - index access keys have multiple key ranges, but only one range
* column
* - The generic case that uses multi range optimization is the
* following:
* SELECT ... FROM table
* WHERE col_1 = ? AND col_2 = ? AND ...
* AND col_(j) IN (?,?,...)
* AND col_(j+1) = ? AND ... AND col_(p-1) = ?
* ORDER BY col_(p) [ASC/DESC] [, col_(p2) [ASC/DESC], ...]
* FOR ordbynum_pred / LIMIT n
*/
bool
qo_check_iscan_for_multi_range_opt (QO_PLAN * plan)
{
QO_ENV *env = NULL;
bool can_optimize = 0;
PT_NODE *col = NULL, *query = NULL, *select_list = NULL;
int error = NO_ERROR;
bool multi_range_optimize = false;
int first_col_idx_pos = -1, i = 0;
PT_NODE *orderby_nodes = NULL, *point = NULL, *name = NULL;
PARSER_CONTEXT *parser = NULL;
bool reverse = false;
PT_NODE *order_by = NULL;
PT_MISC_TYPE all_distinct;
if (plan == NULL)
{
return false;
}
if (!qo_is_iscan (plan))
{
return false;
}
if (QO_NODE_IS_CLASS_HIERARCHY (plan->plan_un.scan.node))
{
/* for now, multi range optimization can only work on one index, therefore class hierarchies are not accepted */
return false;
}
assert (plan->info->env && plan->info->env->parser);
env = plan->info->env;
parser = env->parser;
query = QO_ENV_PT_TREE (env);
if (!PT_IS_SELECT (query))
{
return false;
}
if ((query->info.query.q.select.hint & PT_HINT_NO_MULTI_RANGE_OPT) != 0)
{
/* NO_MULTI_RANGE_OPT was hinted */
return false;
}
if (pt_has_aggregate (parser, query))
{
// CBRD-22696
//
// MRO XASL is flawed when query has aggregate. MRO depends on order by list, which is generated based on
// query's select list. Then it uses pointers from XASL outptr_list, which is normally also generated based
// on query's select list.
//
// In case of group by and/or aggregates, XASL outptr_list is used as input list for group by/aggregate. As a
// consequence, MRO is broken; sometimes it will fallback to normal index scan (because pointers do not match),
// but sometimes a safe-guard is hit (when order by position number is not found in outptr_list).
//
// until a proper fix is found, MRO is disabled for aggregate queries.
return false;
}
all_distinct = query->info.query.all_distinct;
order_by = query->info.query.order_by;
if (order_by == NULL || all_distinct == PT_DISTINCT)
{
return false;
}
if (query->info.query.orderby_for == NULL)
{
return false;
}
select_list = pt_get_select_list (parser, query);
assert (select_list != NULL);
/* create a list of pointers to the names referenced in order by */
for (col = order_by; col != NULL; col = col->next)
{
i = col->info.sort_spec.pos_descr.pos_no;
if (i <= 0)
{
goto exit;
}
name = select_list;
while (--i > 0)
{
name = name->next;
if (name == NULL)
{
goto exit;
}
}
if (!PT_IS_NAME_NODE (name))
{
goto exit;
}
point = pt_point (parser, name);
orderby_nodes = parser_append_node (point, orderby_nodes);
}
/* verify that the index used for scan contains all order by columns in the right order and with the right ordering
* (or reversed ordering) */
error =
qo_check_plan_index_for_multi_range_opt (orderby_nodes, order_by, plan, &can_optimize, &first_col_idx_pos,
&reverse);
if (error != NO_ERROR || !can_optimize)
{
goto exit;
}
/* check scan terms and key filter terms to verify that multi range optimization is applicable */
error = qo_check_terms_for_multiple_range_opt (plan, first_col_idx_pos, &can_optimize);
if (error != NO_ERROR || !can_optimize)
{
goto exit;
}
/* make sure that correlated subqueries may not affect the results obtained with multiple range optimization */
can_optimize = qo_check_subqueries_for_multi_range_opt (plan, first_col_idx_pos);
if (!can_optimize)
{
goto exit;
}
/* check a valid range */
if (!pt_check_ordby_num_for_multi_range_opt (parser, query, &env->multi_range_opt_candidate, NULL))
{
goto exit;
}
/* all conditions were met, so multi range optimization can be applied */
multi_range_optimize = true;
plan->plan_un.scan.index->head->use_descending = reverse;
plan->plan_un.scan.index->head->first_sort_column = first_col_idx_pos;
plan->use_iscan_descending = reverse;
exit:
if (orderby_nodes != NULL)
{
parser_free_tree (parser, orderby_nodes);
}
return multi_range_optimize;
}
/*
* qo_check_plan_index_for_multi_range_opt () - check if the index of index
* scan plan can use multi range
* key-limit optimization
*
* return : error code
* orderby_nodes (in) : list of pointer to the names of order by columns
* orderby_sort_list (in) : list of PT_SORT_SPEC for the order by columns
* plan (in) : current plan to check
* is_valid (out) : true/false
* first_col_idx_pos (out) : position in index for the first sort column
* reverse (out) : true if the index has to be reversed in order to
* use multiple range optimization, false otherwise
*
* NOTE: In order to be compatible with multi range optimization, the index of
* index scan plan must meet the next conditions:
* - index should cover all order by columns and their positions in
* index should be consecutive (in the same order as in the order by
* clause).
* - column ordering should either match in both order by clause and
* index, or should all be reversed.
*/
static int
qo_check_plan_index_for_multi_range_opt (PT_NODE * orderby_nodes, PT_NODE * orderby_sort_list, QO_PLAN * plan,
bool * is_valid, int *first_col_idx_pos, bool * reverse)
{
int i = 0, seg_idx = -1;
QO_INDEX_ENTRY *index_entryp = NULL;
QO_ENV *env = NULL;
PT_NODE *orderby_node = NULL;
PT_NODE *orderby_sort_column = NULL;
PT_NODE *n = NULL, *save_next = NULL;
TP_DOMAIN *key_type = NULL;
assert (plan != NULL && orderby_nodes != NULL && is_valid != NULL && first_col_idx_pos != NULL && reverse != NULL);
*is_valid = false;
*reverse = false;
*first_col_idx_pos = -1;
if (!qo_is_iscan (plan))
{
return NO_ERROR;
}
if (plan->plan_un.scan.index == NULL || plan->plan_un.scan.index->head == NULL)
{
return NO_ERROR;
}
if (plan->info->env == NULL)
{
return NO_ERROR;
}
env = plan->info->env;
index_entryp = plan->plan_un.scan.index->head;
key_type = index_entryp->key_type;
if (key_type == NULL || (TP_DOMAIN_TYPE (key_type) != DB_TYPE_MIDXKEY))
{
return NO_ERROR;
}
key_type = key_type->setdomain;
/* look for the first order by column */
orderby_node = orderby_nodes;
CAST_POINTER_TO_NODE (orderby_node);
assert (orderby_node->node_type == PT_NAME);
orderby_sort_column = orderby_sort_list;
assert (orderby_sort_column->node_type == PT_SORT_SPEC);
for (i = 0; i < index_entryp->nsegs; i++, key_type = key_type->next)
{
if (!key_type)
{
return NO_ERROR;
}
seg_idx = index_entryp->seg_idxs[i];
if (seg_idx < 0)
{
continue;
}
n = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_idx));
CAST_POINTER_TO_NODE (n);
if (n && n->node_type == PT_NAME && pt_name_equal (env->parser, orderby_node, n))
{
if (i == 0)
{
/* MRO cannot apply */
return NO_ERROR;
}
if (key_type->is_desc != (orderby_sort_column->info.sort_spec.asc_or_desc == PT_DESC))
{
/* order in index does not match order in order by clause, but reversed index may work */
*reverse = true;
}
break;
}
}
if (i == index_entryp->nsegs)
{
/* order by node was not found */
return NO_ERROR;
}
if (index_entryp->first_sort_column != -1)
{
assert (index_entryp->first_sort_column == i);
}
*first_col_idx_pos = i;
/* order by node was found, check that all nodes occupy consecutive positions in index */
for (orderby_node = orderby_nodes->next, i = i + 1, key_type = key_type->next, orderby_sort_column =
orderby_sort_list->next; orderby_node != NULL && orderby_sort_column != NULL && i < index_entryp->nsegs;
i++, orderby_sort_column = orderby_sort_column->next, key_type = key_type->next)
{
if (key_type == NULL)
{
return NO_ERROR;
}
seg_idx = index_entryp->seg_idxs[i];
if (seg_idx < 0)
{
return NO_ERROR;
}
save_next = orderby_node->next;
CAST_POINTER_TO_NODE (orderby_node);
n = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_idx));
CAST_POINTER_TO_NODE (n);
if (n == NULL || n->node_type != PT_NAME || !pt_name_equal (env->parser, orderby_node, n))
{
/* order by columns do not match the columns in index */
return NO_ERROR;
}
if ((*reverse ? !key_type->is_desc : key_type->is_desc) !=
(orderby_sort_column->info.sort_spec.asc_or_desc == PT_DESC))
{
/* normally, key_type->is_desc must match sort order == PT_DESC, if reversed, !key_type->is_desc must match
* instead. */
return NO_ERROR;
}
orderby_node = save_next;
}
if (orderby_node != NULL)
{
/* there are order by columns left */
return NO_ERROR;
}
/* all segments in index matched columns in order by list */
*is_valid = true;
return NO_ERROR;
}
/*
* qo_check_plan_for_multiple_ranges_limit_opt () - check the plan to find out
* if multiple ranges key
* limit optimization can be
* used
*
* return : error_code
* parser(in) : parser context
* plan(in) : plan to check
* idx_col(in) : first sort column position in index
* can_optimize(out) : true/false if optimization is allowed/not allowed
*
* Note: Check that all columns that come before the first sort column (on
* the left side of the sort column) in the index are either in an
* equality term, or in a key list term. Only one column should be in
* a key list term.
* Also check all terms in the environment to see if there is any
* data filter
*/
static int
qo_check_terms_for_multiple_range_opt (QO_PLAN * plan, int first_sort_col_idx, bool * can_optimize)
{
int t, i, j, pos, s, seg_idx;
BITSET_ITERATOR iter_t, iter_s;
QO_TERM *termp = NULL;
QO_ENV *env = NULL;
QO_INDEX_ENTRY *index_entryp = NULL;
QO_NODE *node_of_plan = NULL;
int *used_cols = NULL;
int kl_terms = 0;
assert (can_optimize != NULL);
*can_optimize = false;
if (plan == NULL || plan->info == NULL || plan->plan_un.scan.index == NULL || !qo_is_interesting_order_scan (plan))
{
return NO_ERROR;
}
env = plan->info->env;
if (env == NULL)
{
return NO_ERROR;
}
index_entryp = plan->plan_un.scan.index->head;
if (index_entryp == NULL)
{
return NO_ERROR;
}
node_of_plan = plan->plan_un.scan.node;
if (node_of_plan == NULL)
{
return NO_ERROR;
}
/* index columns that are used in terms */
used_cols = (int *) malloc (first_sort_col_idx * sizeof (int));
if (!used_cols)
{
return ER_FAILED;
}
for (i = 0; i < first_sort_col_idx; i++)
{
used_cols[i] = 0;
}
/* check all index scan terms */
for (t = bitset_iterate (&(plan->plan_un.scan.terms), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
termp = QO_ENV_TERM (env, t);
assert (!QO_TERM_IS_FLAGED (termp, QO_TERM_NON_IDX_SARG_COLL));
pos = -1;
for (i = 0; i < termp->can_use_index && i < 2 && pos == -1; i++)
{
for (j = 0; j < index_entryp->nsegs; j++)
{
if ((index_entryp->seg_idxs[j] == QO_SEG_IDX (termp->index_seg[i])))
{
pos = j;
break;
}
}
}
if (pos == -1)
{
free_and_init (used_cols);
return NO_ERROR;
}
if (pos < first_sort_col_idx)
{
used_cols[pos]++;
/* only helpful if term is equality or key list */
switch (QO_TERM_PT_EXPR (termp)->info.expr.op)
{
case PT_EQ:
break;
case PT_IS_IN:
case PT_EQ_SOME:
kl_terms++;
break;
case PT_RANGE:
{
PT_NODE *between_and;
between_and = QO_TERM_PT_EXPR (termp)->info.expr.arg2;
if (PT_IS_EXPR_NODE (between_and) && between_and->info.expr.op == PT_BETWEEN_EQ_NA)
{
kl_terms++;
}
else
{
free_and_init (used_cols);
return NO_ERROR;
}
}
break;
default:
free_and_init (used_cols);
return NO_ERROR;
}
}
}
/* check key list terms */
if (kl_terms > 1)
{
free_and_init (used_cols);
return NO_ERROR;
}
/* check all key filter terms */
for (t = bitset_iterate (&(plan->plan_un.scan.kf_terms), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
termp = QO_ENV_TERM (env, t);
assert (!QO_TERM_IS_FLAGED (termp, QO_TERM_NON_IDX_SARG_COLL));
pos = -1;
for (i = 0; i < termp->can_use_index && i < 2 && pos == -1; i++)
{
for (j = 0; j < index_entryp->nsegs; j++)
{
if ((index_entryp->seg_idxs[j] == QO_SEG_IDX (termp->index_seg[i])))
{
pos = j;
break;
}
}
}
if (pos == -1)
{
if (termp->can_use_index == 0)
{
continue;
}
free_and_init (used_cols);
return NO_ERROR;
}
if (pos < first_sort_col_idx)
{
/* for key filter terms we are only interested if it is an eq term */
if (QO_TERM_PT_EXPR (termp)->info.expr.op == PT_EQ)
{
used_cols[pos]++;
}
}
}
/* check used columns */
for (i = 0; i < first_sort_col_idx; i++)
{
if (used_cols[i] == 0)
{
free_and_init (used_cols);
return NO_ERROR;
}
}
free_and_init (used_cols);
/* check all segments in all terms in environment for data filter */
for (t = 0; t < env->nterms; t++)
{
termp = QO_ENV_TERM (env, t);
if (QO_TERM_IS_FLAGED (termp, QO_TERM_NON_IDX_SARG_COLL))
{
return NO_ERROR;
}
if (bitset_is_empty (&(termp->segments)))
{
/*
* We decided not to support MRO (Multiple Row Optimization) if the return value
* of the bitset_is_empty() function is checked and found to be true.
* This is related to the CBRD-24914 issue, which involves a core dump occurring
* when term->pt_expr is converted to PT_VALUE resulting in an always true/false condition.
* Therefore, in the process of reducing the equality term, some parts of the
* always true condition have been removed. In cases of an always false condition
* or an always true condition that has not been removed, this implementation does not support MRO optimization.
*/
return NO_ERROR; /* give up */
}
for (s = bitset_iterate (&(termp->segments), &iter_s); s != -1; s = bitset_next_member (&iter_s))
{
bool found = false;
if (QO_SEG_HEAD (QO_ENV_SEG (env, s)) != node_of_plan)
{
continue;
}
seg_idx = s;
for (i = 0; i < index_entryp->nsegs; i++)
{
if (seg_idx == index_entryp->seg_idxs[i])
{
found = true;
break;
}
}
if (!found)
{
/* data filter */
return NO_ERROR;
}
}
}
*can_optimize = true;
return NO_ERROR;
}
/*
* qo_check_subqueries_for_multi_range_opt () - check that there are not
* subqueries that may invalidate
* multiple range optimization
*
* return : false if invalidated, true otherwise
* plan (in) : the plan that refers to the table that has the
* order by columns
* sort_col_idx_pos (in) : position in index for the first sort column
*
* NOTE: If there are terms containing correlated subqueries, and if they
* refer to the node of the sort plan, then the affected segments must
* appear in index before the first sort column (and the segment must
* not belong to the range term).
*/
static bool
qo_check_subqueries_for_multi_range_opt (QO_PLAN * plan, int sort_col_idx_pos)
{
QO_ENV *env = NULL;
QO_SUBQUERY *subq = NULL;
int i, s, t, seg_idx, i_seg_idx, ts;
QO_NODE *node_of_plan = NULL;
BITSET_ITERATOR iter_t, iter_ts;
QO_TERM *term = NULL;
assert (plan != NULL && plan->info->env != NULL && plan->plan_type == QO_PLANTYPE_SCAN
&& plan->plan_un.scan.index != NULL);
env = plan->info->env;
node_of_plan = plan->plan_un.scan.node;
/* for each sub-query */
for (s = 0; s < env->nsubqueries; s++)
{
subq = QO_ENV_SUBQUERY (env, s);
/* for each term this sub-query belongs to */
for (t = bitset_iterate (&(subq->terms), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
term = QO_ENV_TERM (env, t);
for (ts = bitset_iterate (&(term->segments), &iter_ts); ts != -1; ts = bitset_next_member (&iter_ts))
{
bool found = false;
if (QO_SEG_HEAD (QO_ENV_SEG (env, t)) != node_of_plan)
{
continue;
}
seg_idx = ts;
/* try to find the segment in index */
for (i = 0; i < sort_col_idx_pos; i++)
{
i_seg_idx = plan->plan_un.scan.index->head->seg_idxs[i];
if (i_seg_idx == seg_idx)
{
if (qo_check_seg_belongs_to_range_term (plan, env, seg_idx))
{
return false;
}
break;
}
}
if (!found)
{
/* the segment was not found before the first sort column */
return false;
}
}
}
}
return true;
}
/*
* qo_check_seg_belongs_to_range_term () - checks the segment if it is a range
* term
*
* return : true or false
* subplan (in) : the subplan possibly containing the RANGE expression
* env (in) : optimizer environment
* seg_idx (in) : index of the segment that needs checking
*
* NOTE: Returns true if the specified subplan contains a term that
* references the given segment in a RANGE expression
* (t.i in (1,2,3) would be an example).
* Used in keylimit for multiple key ranges in joins optimization.
* Scan terms, key filter terms and also sarged terms must all be
* checked to cover all cases.
*/
static bool
qo_check_seg_belongs_to_range_term (QO_PLAN * subplan, QO_ENV * env, int seg_idx)
{
int t, u;
BITSET_ITERATOR iter, iter_s;
assert (subplan->plan_type == QO_PLANTYPE_SCAN);
if (subplan->plan_type != QO_PLANTYPE_SCAN)
{
return false;
}
for (t = bitset_iterate (&(subplan->plan_un.scan.terms), &iter); t != -1; t = bitset_next_member (&iter))
{
QO_TERM *termp = QO_ENV_TERM (env, t);
BITSET *segs = &(QO_TERM_SEGS (termp));
if (!segs)
{
continue;
}
for (u = bitset_iterate (segs, &iter_s); u != -1; u = bitset_next_member (&iter_s))
{
if (u == seg_idx)
{
PT_NODE *node = QO_TERM_PT_EXPR (termp);
if (!node)
{
continue;
}
switch (node->info.expr.op)
{
case PT_IS_IN:
case PT_EQ_SOME:
case PT_RANGE:
return true;
default:
continue;
}
}
}
}
for (t = bitset_iterate (&(subplan->plan_un.scan.kf_terms), &iter); t != -1; t = bitset_next_member (&iter))
{
QO_TERM *termp = QO_ENV_TERM (env, t);
BITSET *segs = &(QO_TERM_SEGS (termp));
if (!segs)
{
continue;
}
for (u = bitset_iterate (segs, &iter_s); u != -1; u = bitset_next_member (&iter_s))
{
if (u == seg_idx)
{
PT_NODE *node = QO_TERM_PT_EXPR (termp);
if (!node)
{
continue;
}
switch (node->info.expr.op)
{
case PT_IS_IN:
case PT_EQ_SOME:
case PT_RANGE:
return true;
default:
continue;
}
}
}
}
for (t = bitset_iterate (&(subplan->sarged_terms), &iter); t != -1; t = bitset_next_member (&iter))
{
QO_TERM *termp = QO_ENV_TERM (env, t);
BITSET *segs = &(QO_TERM_SEGS (termp));
if (!segs)
{
continue;
}
for (u = bitset_iterate (segs, &iter_s); u != -1; u = bitset_next_member (&iter_s))
{
if (u == seg_idx)
{
PT_NODE *node = QO_TERM_PT_EXPR (termp);
if (!node)
{
continue;
}
switch (node->info.expr.op)
{
case PT_IS_IN:
case PT_EQ_SOME:
case PT_RANGE:
return true;
default:
continue;
}
}
}
}
return false;
}
/*
* qo_check_join_for_multi_range_opt () - check if join plan can make use of
* multi range key-limit optimization
*
* return : true/false
* plan (in) : join plan
*
* NOTE: The current join plan has to meet a series of conditions in order
* to use the multi range optimization:
* - Has at least an index scan subplan that can make use of multi
* range optimization (as if there would be no joins)
* - The sort plan (that uses multi range optimization) edges:
* - Segments used to join other "outer-more" scans must also belong
* to index (no data filter).
* - Segments use to join other "inner-more" scans must belong to
* index (no data filter), they must be positioned before the first
* sorting column, and they cannot be in a range term (in order
* to avoid filtering the results obtained after top n sorting).
*/
bool
qo_check_join_for_multi_range_opt (QO_PLAN * plan)
{
QO_PLAN *sort_plan = NULL;
int error = NO_ERROR;
bool can_optimize = true;
/* verify that this is a valid join for multi range optimization */
if (plan == NULL || plan->plan_type != QO_PLANTYPE_JOIN || plan->plan_un.join.join_type != JOIN_INNER
|| plan->plan_un.join.join_method == QO_JOINMETHOD_MERGE_JOIN
|| plan->plan_un.join.join_method == QO_JOINMETHOD_HASH_JOIN)
{
return false;
}
assert (plan->info->env && plan->info->env->pt_tree);
if (!PT_IS_SELECT (plan->info->env->pt_tree))
{
return false;
}
if (((QO_ENV_PT_TREE (plan->info->env))->info.query.q.select.hint & PT_HINT_NO_MULTI_RANGE_OPT) != 0)
{
/* NO_MULTI_RANGE_OPT was hinted */
return false;
}
/* first must find an index scan subplan that can apply multi range optimization */
error = qo_find_subplan_using_multi_range_opt (plan, &sort_plan, NULL);
if (error != NO_ERROR || sort_plan == NULL)
{
/* error finding subplan or no subplan was found */
return false;
}
/* check all join conditions */
error = qo_check_subplans_for_multi_range_opt (NULL, plan, sort_plan, &can_optimize, NULL);
if (error != NO_ERROR || !can_optimize)
{
return false;
}
/* all conditions are met, multi range optimization may be used */
return true;
}
/*
* qo_check_subplans_for_multi_range_opt () - verify that join conditions do
* not invalidate the multi range
* optimization
*
* return : error code
* parent (in) : join node that contains sub-plans
* plan (in) : current plan to verify
* sortplan (in) : the plan that refers to the order by table
* is_valid (out) : is_valid is true if optimization can be applied
* otherwise it is set on false
* sort_col_idx_pos (in) : position in index for the first sort column
* seen (in/out) : flag to remember that the sort plan was passed.
* all scan plans that are met after this flag was set
* are potential suspect scans ("to the right" of the
* order by table
*
* NOTE: 1. *seen should be false when the function is called for root plan or
* it should be left as NULL.
* 2. checks all sub-plans at the right of sort plan in the join chain.
* the sub-plans in the left can invalidate the optimization only if
* the join term acts as data filter, which was already checked at a
* previous step (see qo_check_terms_for_multiple_range_opt).
* Check the comment on qo_check_join_for_multi_range_opt for more
* details.
*/
static int
qo_check_subplans_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * plan, QO_PLAN * sortplan, bool * is_valid,
bool * seen)
{
int error = NO_ERROR;
bool dummy = false;
if (seen == NULL)
{
seen = &dummy;
}
if (plan->plan_type == QO_PLANTYPE_SCAN)
{
if (*seen)
{
if (parent == NULL)
{
*is_valid = false;
goto exit;
}
*is_valid = qo_check_subplan_join_cond_for_multi_range_opt (parent, plan, sortplan);
if (*is_valid == true)
{
*is_valid = qo_check_parent_eq_class_for_multi_range_opt (parent, plan, sortplan);
}
return NO_ERROR;
}
if (plan == sortplan)
{
*seen = true;
}
*is_valid = true;
return NO_ERROR;
}
else if (plan->plan_type == QO_PLANTYPE_JOIN)
{
if (qo_plan_multi_range_opt (plan))
{
/* plan->multi_range_opt_use == PLAN_MULTI_RANGE_OPT_USE */
/* already checked and the plan can use multi range opt */
*is_valid = true;
/* sort plan is somewhere in the subtree of this plan */
*seen = true;
return NO_ERROR;
}
else if (plan->multi_range_opt_use == PLAN_MULTI_RANGE_OPT_CANNOT_USE)
{
/* already checked and the plan cannot use multi range opt */
*is_valid = false;
return NO_ERROR;
}
/* this must be the first time current plan is checked for multi range optimization */
error = qo_check_subplans_for_multi_range_opt (plan, plan->plan_un.join.outer, sortplan, is_valid, seen);
if (error != NO_ERROR || !*is_valid)
{
/* mark the plan for future checks */
plan->multi_range_opt_use = PLAN_MULTI_RANGE_OPT_CANNOT_USE;
return error;
}
error = qo_check_subplans_for_multi_range_opt (plan, plan->plan_un.join.inner, sortplan, is_valid, seen);
if (error != NO_ERROR || !*is_valid)
{
/* mark the plan for future checks */
plan->multi_range_opt_use = PLAN_MULTI_RANGE_OPT_CANNOT_USE;
return error;
}
return NO_ERROR;
}
/* a case we have not foreseen? Be conservative. */
*is_valid = false;
exit:
return error;
}
/*
* qo_check_subplan_join_cond_for_multi_range_opt () - validate a given
* subplan for multi range
* key-limit optimization.
*
* return : true if valid, false otherwise
* parent (in) : join plan that contains current subplan
* subplan (in) : the subplan that is verified at current step
* sort_plan (in) : the subplan that refers to the table that has the order by
* columns
* is_outer (in) : The position of sort plan relative to sub-plan in the join
* chain. If true, sort plan must be position to the left in
* the chain (is "outer-more"), otherwise it must be to the
* right ("inner-more").
*
* NOTE: The function checks the join conditions between sub-plan and
* sort-plan. It is supposed that sort-plan is outer and sub-plan is
* inner in this join.
*/
static bool
qo_check_subplan_join_cond_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * subplan, QO_PLAN * sort_plan)
{
QO_ENV *env = NULL;
QO_NODE *node_of_sort_table = NULL, *node_of_subplan = NULL;
BITSET_ITERATOR iter_t, iter_n, iter_segs;
QO_TERM *jt = NULL;
QO_NODE *jn = NULL;
int t, n, seg_idx, k, k_seg_idx;
QO_NODE *seg_node = NULL;
bool is_jterm_relevant;
assert (parent != NULL && parent->plan_type == QO_PLANTYPE_JOIN);
assert (sort_plan != NULL && sort_plan->plan_un.scan.node != NULL && sort_plan->plan_un.scan.node->info != NULL);
if (sort_plan->plan_un.scan.node->info->n <= 0 || sort_plan->plan_un.scan.index == NULL
|| sort_plan->plan_un.scan.index->n <= 0)
{
return false;
}
env = sort_plan->info->env;
node_of_sort_table = sort_plan->plan_un.scan.node;
node_of_subplan = subplan->plan_un.scan.node;
assert (node_of_sort_table != NULL && node_of_subplan != NULL);
/*
* Scan all the parent's join terms: jt.
* If jt is a valid join-term (is a join between sub-plan and sort plan),
* the segment that belong to the sort plan must be positioned in index
* before the first sort column and it must not be in a range term.
*/
for (t = bitset_iterate (&(parent->plan_un.join.join_terms), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
jt = QO_ENV_TERM (env, t);
assert (jt != NULL);
is_jterm_relevant = false;
for (n = bitset_iterate (&(jt->nodes), &iter_n); n != -1; n = bitset_next_member (&iter_n))
{
jn = QO_ENV_NODE (env, n);
assert (jn != NULL);
if (jn == node_of_subplan)
{
is_jterm_relevant = true;
break;
}
}
if (!is_jterm_relevant)
{
continue;
}
for (n = bitset_iterate (&(jt->nodes), &iter_n); n != -1; n = bitset_next_member (&iter_n))
{
jn = QO_ENV_NODE (env, n);
assert (jn != NULL);
if (jn != node_of_sort_table)
{
continue;
}
/* there is a join term t that references the nodes used in sub-plan and sort plan. */
for (seg_idx = bitset_iterate (&(jt->segments), &iter_segs); seg_idx != -1;
seg_idx = bitset_next_member (&iter_segs))
{
bool found = false;
seg_node = QO_SEG_HEAD (QO_ENV_SEG (env, seg_idx));
if (seg_node != node_of_sort_table)
{
continue;
}
/* seg node refer to the order by table */
for (k = 0; k < sort_plan->plan_un.scan.index->head->first_sort_column; k++)
{
k_seg_idx = sort_plan->plan_un.scan.index->head->seg_idxs[k];
if (k_seg_idx == seg_idx)
{
/* seg_idx was found before the first sort column */
if (qo_check_seg_belongs_to_range_term (sort_plan, env, seg_idx))
{
return false;
}
found = true;
break;
}
}
if (!found)
{
/* seg_idx was not found before the first sort column */
return false;
}
}
}
}
return true;
}
/*
* qo_check_parent_eq_class_for_multi_range_opt () - validate a given subplan
* for multi range key-limit
* optimization.
*
* return : true if valid, false otherwise
* parent (in) : join plan that contains current subplan
* subplan (in) : the subplan that is verified at current step
* sort_plan (in) : the subplan that refers to the table that has the order by
* columns
*
* NOTE: Same as qo_check_subplan_join_cond_for_multi_range_opt, except that
* it checks the EQCLASSES.
*/
static bool
qo_check_parent_eq_class_for_multi_range_opt (QO_PLAN * parent, QO_PLAN * subplan, QO_PLAN * sort_plan)
{
QO_ENV *env = NULL;
QO_NODE *node_of_sort_table = NULL, *node_of_crt_table = NULL, *node = NULL;
int eq_idx, t, k, seg_idx, k_seg_idx;
QO_EQCLASS *eq = NULL;
bool is_eqclass_relevant = false;
BITSET_ITERATOR iter_t;
assert (parent != NULL && parent->plan_type == QO_PLANTYPE_JOIN);
assert (subplan != NULL && subplan->plan_type == QO_PLANTYPE_SCAN);
assert (sort_plan != NULL && sort_plan->plan_un.scan.node != NULL && sort_plan->plan_un.scan.node->info != NULL);
if (sort_plan->plan_un.scan.node->info->n <= 0 || sort_plan->plan_un.scan.index == NULL
|| sort_plan->plan_un.scan.index->n <= 0)
{
return false;
}
env = parent->info->env;
node_of_sort_table = sort_plan->plan_un.scan.node;
node_of_crt_table = subplan->plan_un.scan.node;
for (eq_idx = 0; eq_idx < env->neqclasses; eq_idx++)
{
eq = QO_ENV_EQCLASS (env, eq_idx);
is_eqclass_relevant = false;
for (t = bitset_iterate (&QO_EQCLASS_SEGS (eq), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
node = QO_SEG_HEAD (QO_ENV_SEG (env, t));
if (node == node_of_crt_table)
{
is_eqclass_relevant = true;
break;
}
}
if (!is_eqclass_relevant)
{
continue;
}
/* here: we have an equivalence class that has a segment belonging to our current class. Must see if it also has
* segments belonging to the sort table: iterate again over it. */
for (t = bitset_iterate (&QO_EQCLASS_SEGS (eq), &iter_t); t != -1; t = bitset_next_member (&iter_t))
{
bool found = false;
node = QO_SEG_HEAD (QO_ENV_SEG (env, t));
if (node != node_of_sort_table)
{
continue;
}
seg_idx = t;
/* try to find the segment in the index that is used when scanning the order by table - take that info from
* the subplan (sortplan) rather than from the node info, because the node info lists all the indexes, not
* only those that are used at this particular scan. */
for (k = 0; k < sort_plan->plan_un.scan.index->head->first_sort_column; k++)
{
k_seg_idx = sort_plan->plan_un.scan.index->head->seg_idxs[k];
if (k_seg_idx == seg_idx)
{
/* we found the segment before the first sort column */
if (qo_check_seg_belongs_to_range_term (sort_plan, env, seg_idx))
{
return false;
}
found = true;
break;
}
}
if (!found)
{
/* seg_idx was not found before the first sort column */
return false;
}
}
}
return true;
}
/*
* qo_find_subplan_using_multi_range_opt () - finds an index scan plan that
* may use multi range key-limit
* optimization.
*
* return : error code
* plan (in) : current node in plan tree
* result (out) : plan with multi range optimization
* join_idx (out) : the position of the optimized plan in join chain
*
* NOTE : Leave result or join_idx NULL if they are not what you are looking
* for.
*/
int
qo_find_subplan_using_multi_range_opt (QO_PLAN * plan, QO_PLAN ** result, int *join_idx)
{
int error = NO_ERROR;
if (result != NULL)
{
*result = NULL;
}
if (plan == NULL)
{
return NO_ERROR;
}
if (plan->plan_type == QO_PLANTYPE_JOIN && plan->plan_un.join.join_type == JOIN_INNER)
{
if (join_idx != NULL)
{
*join_idx++;
}
error = qo_find_subplan_using_multi_range_opt (plan->plan_un.join.outer, result, join_idx);
if (error != NO_ERROR || (result != NULL && *result != NULL))
{
return NO_ERROR;
}
if (join_idx != NULL)
{
*join_idx++;
}
return qo_find_subplan_using_multi_range_opt (plan->plan_un.join.inner, result, join_idx);
}
else if (qo_is_interesting_order_scan (plan))
{
if (qo_plan_multi_range_opt (plan))
{
if (result != NULL)
{
*result = plan;
}
}
return NO_ERROR;
}
return NO_ERROR;
}
/*
* make_sort_limit_proc () - make sort limit xasl node
* return : xasl proc on success, NULL on error
* env (in) : optimizer environment
* plan (in) : query plan
* namelist (in) : list of segments referenced by nodes in the plan
* xasl (in) : top xasl
*/
static XASL_NODE *
make_sort_limit_proc (QO_ENV * env, QO_PLAN * plan, PT_NODE * namelist, XASL_NODE * xasl)
{
PARSER_CONTEXT *parser;
XASL_NODE *listfile = NULL;
PT_NODE *new_order_by = NULL, *node_list = NULL;
PT_NODE *order_by, *statement;
parser = QO_ENV_PARSER (env);
statement = QO_ENV_PT_TREE (env);
order_by = statement->info.query.order_by;
if (xasl->ordbynum_val == NULL)
{
/* If orderbynum_val is NULL, we're probably somewhere in a subplan and orderbynum_val is set for the upper XASL
* level. Try to find the ORDERBY_NUM node and use the node->etc pointer which is set to the orderby_num val */
if (statement->info.query.orderby_for == NULL)
{
/* we should not create a sort_limit proc without an orderby_for predicate. */
assert_release (false);
listfile = NULL;
goto cleanup;
}
parser_walk_tree (parser, statement->info.query.orderby_for, pt_get_numbering_node_etc, &xasl->ordbynum_val, NULL,
NULL);
if (xasl->ordbynum_val == NULL)
{
assert_release (false);
listfile = NULL;
goto cleanup;
}
}
/* make o copy of the namelist to extend it with expressions from the ORDER BY clause. The extended list will be used
* to generate the internal listfile scan but will not be used for the actual XASL node. */
node_list = parser_copy_tree_list (parser, namelist);
if (node_list == NULL)
{
listfile = NULL;
goto cleanup;
}
/* set new SORT_SPEC list based on the position of items in the node_list */
new_order_by = pt_set_orderby_for_sort_limit_plan (parser, statement, node_list);
if (new_order_by == NULL)
{
listfile = NULL;
goto cleanup;
}
statement->info.query.order_by = new_order_by;
listfile = make_buildlist_proc (env, node_list);
listfile = gen_outer (env, plan->plan_un.sort.subplan, &EMPTY_SET, NULL, NULL, listfile);
listfile = add_sort_spec (env, listfile, plan, xasl->ordbynum_val, false);
cleanup:
if (node_list != NULL)
{
parser_free_tree (parser, node_list);
}
if (new_order_by != NULL)
{
parser_free_tree (parser, new_order_by);
}
statement->info.query.order_by = order_by;
return listfile;
}
/*
* qo_get_orderby_num_upper_bound_node () - get the node which represents the
* upper bound predicate of an
* orderby_num predicate
* return : node or NULL
* parser (in) : parser context
* orderby_for (in) : orderby_for predicate list
* is_new_node (in/out) : if a new node was created, free_node is set to true
* and caller must free the returned node
*
* Note: A NULL return indicates that this function either found no upper
* bound or that it found several predicates which specify an upper bound
* for the ORDERBY_NUM predicate.
*/
static PT_NODE *
qo_get_orderby_num_upper_bound_node (PARSER_CONTEXT * parser, PT_NODE * orderby_for, bool * is_new_node)
{
PT_NODE *left = NULL, *right = NULL;
PT_NODE *save_next;
PT_OP_TYPE op;
bool free_left = false, free_right = false;
*is_new_node = false;
if (orderby_for == NULL || !PT_IS_EXPR_NODE (orderby_for) || orderby_for->or_next != NULL)
{
/* orderby_for must be an expression containing only AND predicates */
assert (false);
return NULL;
}
/* Ranges for ORDERBY_NUM predicates have already been merged (see qo_reduce_order_by). If the code below finds more
* than one upper bound, this is an error. */
if (orderby_for->next != NULL)
{
save_next = orderby_for->next;
orderby_for->next = NULL;
right = save_next;
left = orderby_for;
left = qo_get_orderby_num_upper_bound_node (parser, left, &free_left);
right = qo_get_orderby_num_upper_bound_node (parser, right, &free_right);
orderby_for->next = save_next;
if (left != NULL)
{
if (right != NULL)
{
/* There should be exactly one upper bound */
if (free_left)
{
parser_free_tree (parser, left);
}
if (free_right)
{
parser_free_tree (parser, right);
}
return NULL;
}
*is_new_node = free_left;
return left;
}
else
{
/* If right is NULL, the orderby_num pred is invalid and we messed something up somewhere. If it is not NULL,
* this is the node we are looking for. */
*is_new_node = free_right;
return right;
}
}
op = orderby_for->info.expr.op;
/* look for orderby_num < argument */
if (PT_IS_EXPR_NODE (orderby_for->info.expr.arg1) && orderby_for->info.expr.arg1->info.expr.op == PT_ORDERBY_NUM)
{
left = orderby_for->info.expr.arg1;
right = orderby_for->info.expr.arg2;
}
else
{
left = orderby_for->info.expr.arg2;
right = orderby_for->info.expr.arg1;
if (!PT_IS_EXPR_NODE (left) || left->info.expr.op != PT_ORDERBY_NUM)
{
/* could not find ORDERBY_NUM argument */
return NULL;
}
/* Verify operator. If LE, LT then reverse it. */
switch (op)
{
case PT_LE:
op = PT_GE;
break;
case PT_LT:
op = PT_GT;
break;
case PT_GE:
op = PT_LE;
break;
case PT_GT:
op = PT_LT;
break;
default:
break;
}
}
if (op == PT_LE || op == PT_LT)
{
return orderby_for;
}
if (op == PT_BETWEEN)
{
/* construct new predicate for ORDERBY_NUM from BETWEEN expr. */
PT_NODE *new_node;
if (!PT_IS_EXPR_NODE (right) || right->info.expr.op != PT_BETWEEN_AND)
{
return NULL;
}
new_node = parser_new_node (parser, PT_EXPR);
if (new_node == NULL)
{
return NULL;
}
new_node->info.expr.op = PT_LE;
new_node->info.expr.arg1 = parser_copy_tree (parser, left);
if (new_node->info.expr.arg1 == NULL)
{
parser_free_tree (parser, new_node);
return NULL;
}
new_node->info.expr.arg2 = parser_copy_tree (parser, right->info.expr.arg2);
if (new_node->info.expr.arg2 == NULL)
{
parser_free_tree (parser, new_node);
return NULL;
}
*is_new_node = true;
return new_node;
}
/* Any other comparison operator is unusable */
return NULL;
}
/*
* qo_get_multi_col_range_segs () -
* return:
* env(in): The optimizer environment
* plan(in): Query plan
* qo_index_infop(in):
* multi_col_segs(out): (a,b) in ... a,b's segment number bit
* multi_col_range_segs(out): range segments in multiple column term
*
* Note: return multiple column term's number
* output are multi column term's segments and range key filter segments and index col segments
*/
static int
qo_get_multi_col_range_segs (QO_ENV * env, QO_PLAN * plan, QO_INDEX_ENTRY * index_entryp,
BITSET * multi_col_segs, BITSET * multi_col_range_segs, BITSET * index_segs)
{
BITSET_ITERATOR iter;
QO_TERM *termp = NULL;
int multi_term = -1;
/* find term having multiple columns ex) (col1,col2) in ... */
for (multi_term = bitset_iterate (&(plan->plan_un.scan.terms), &iter); multi_term != -1;
multi_term = bitset_next_member (&iter))
{
termp = QO_ENV_TERM (env, multi_term);
if (QO_TERM_IS_FLAGED (termp, QO_TERM_MULTI_COLL_PRED))
{
bitset_assign (multi_col_segs, &(QO_TERM_SEGS (termp)));
break;
}
}
if (index_entryp)
{
bitset_assign (index_segs, &(index_entryp->index_segs));
}
bitset_assign (multi_col_range_segs, &(plan->plan_un.scan.multi_col_range_segs));
return multi_term;
}
/*
* qo_init_projection_info() -
* return: Error code (NO_ERROR if successful, error code otherwise).
* env(in): Optimization environment.
* plan(in): Execution plan for hash join.
* pred_set(in): Bitset of predicates (join, during-join, after-join, sarg).
* info(in/out): Projection information used in the hash join execution plan.
*/
static int
qo_init_projection_info (QO_ENV * env, QO_PLAN * plan, BITSET * pred_set, PROJECTION_INFO * info)
{
PARSER_CONTEXT *parser;
PT_NODE *term_expr, *pred_node;
PT_NODE *outer_part, *inner_part;
PT_NODE *name_list;
PT_NODE *hash_key = NULL;
QO_PLAN *outer_plan, *inner_plan;
QO_TERM *term;
BITSET plan_segs_set, during_segs_set, temp_segs_set;
BITSET_ITERATOR term_iter, during_iter;
int term_index, during_index;
PROJECTION_PART_INFO *outer_info, *inner_info;
PROJECTION_FINAL_INFO *final_info;
int error = NO_ERROR;
assert (env != NULL);
assert (plan != NULL);
assert (pred_set != NULL);
assert (plan->plan_type == QO_PLANTYPE_JOIN);
assert (plan->plan_un.join.join_method == QO_JOINMETHOD_HASH_JOIN);
parser = QO_ENV_PARSER (env);
assert (parser != NULL);
bitset_init (&plan_segs_set, env);
bitset_init (&during_segs_set, env);
bitset_init (&temp_segs_set, env);
outer_plan = plan->plan_un.join.outer;
inner_plan = plan->plan_un.join.inner;
assert (outer_plan != NULL);
assert (inner_plan != NULL);
memset (info, 0, sizeof (PROJECTION_INFO));
bitset_init (&info->outer.exprs_set, env);
bitset_init (&info->inner.exprs_set, env);
outer_info = &info->outer;
inner_info = &info->inner;
final_info = &info->final;
bitset_assign (&plan_segs_set, &plan->info->projected_segs);
for (term_index = bitset_iterate (pred_set, &term_iter); term_index != -1;
term_index = bitset_next_member (&term_iter))
{
term = QO_ENV_TERM (env, term_index);
if (BITSET_MEMBER (plan->plan_un.join.join_terms, term_index))
{
BITSET_CLEAR (temp_segs_set);
term_expr = QO_TERM_PT_EXPR (term);
if (term_expr->info.expr.op == PT_RANGE)
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
qo_expr_segs (env, pt_left_part (term_expr), &temp_segs_set);
if (bitset_intersects (&temp_segs_set, &outer_plan->info->projected_segs))
{
outer_part = pt_left_part (term_expr);
inner_part = pt_right_part (term_expr);
}
else if (bitset_intersects (&temp_segs_set, &inner_plan->info->projected_segs))
{
inner_part = pt_left_part (term_expr);
outer_part = pt_right_part (term_expr);
}
else
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
if (!pt_is_name_node (outer_part))
{
outer_info->expr_list = parser_append_node (pt_point (parser, outer_part), outer_info->expr_list);
bitset_add (&outer_info->exprs_set, term_index);
}
if (!pt_is_name_node (inner_part))
{
inner_info->expr_list = parser_append_node (pt_point (parser, inner_part), inner_info->expr_list);
bitset_add (&inner_info->exprs_set, term_index);
}
}
else if (BITSET_MEMBER (plan->plan_un.join.during_join_terms, term_index))
{
bitset_assign (&temp_segs_set, &QO_TERM_SEGS (term));
bitset_intersect (&temp_segs_set, &outer_plan->info->projected_segs);
for (during_index = bitset_iterate (&temp_segs_set, &during_iter);
during_index != -1; during_index = bitset_next_member (&during_iter))
{
pred_node = QO_SEG_PT_NODE (QO_ENV_SEG (env, during_index));
if (pred_node->node_type != PT_NAME)
{
qo_expr_segs (env, pred_node, &temp_segs_set);
}
}
bitset_union (&during_segs_set, &temp_segs_set);
bitset_assign (&temp_segs_set, &QO_TERM_SEGS (term));
bitset_intersect (&temp_segs_set, &inner_plan->info->projected_segs);
for (during_index = bitset_iterate (&temp_segs_set, &during_iter);
during_index != -1; during_index = bitset_next_member (&during_iter))
{
pred_node = QO_SEG_PT_NODE (QO_ENV_SEG (env, during_index));
if (pred_node->node_type != PT_NAME)
{
qo_expr_segs (env, pred_node, &temp_segs_set);
}
}
bitset_union (&during_segs_set, &temp_segs_set);
}
else
{
/* Nothing to do */
}
bitset_union (&plan_segs_set, &QO_TERM_SEGS (term));
} /* for (bitset_iterate (pred_set, &term_iter)) */
/* during_join_pred */
if (!bitset_is_empty (&during_segs_set))
{
bitset_assign (&temp_segs_set, &during_segs_set);
bitset_intersect (&temp_segs_set, &outer_plan->info->projected_segs);
for (during_index = bitset_iterate (&temp_segs_set, &during_iter); during_index != -1;
during_index = bitset_next_member (&during_iter))
{
pred_node = QO_SEG_PT_NODE (QO_ENV_SEG (env, during_index));
if (pred_node->node_type == PT_NAME)
{
outer_info->pred_list = parser_append_node (pt_point (parser, pred_node), outer_info->pred_list);
}
}
bitset_assign (&temp_segs_set, &during_segs_set);
bitset_intersect (&temp_segs_set, &inner_plan->info->projected_segs);
for (during_index = bitset_iterate (&temp_segs_set, &during_iter); during_index != -1;
during_index = bitset_next_member (&during_iter))
{
pred_node = QO_SEG_PT_NODE (QO_ENV_SEG (env, during_index));
if (pred_node->node_type == PT_NAME)
{
inner_info->pred_list = parser_append_node (pt_point (parser, pred_node), inner_info->pred_list);
}
}
}
/* hash_key */
hash_key = pt_make_integer_value (parser, -1);
if (hash_key == NULL)
{
goto error_exit;
}
/* outer_info */
outer_info->expr_list = parser_append_node (outer_info->expr_list /* back */ , hash_key /* front */ );
outer_info->expr_count = pt_length_of_list (outer_info->expr_list);
bitset_assign (&temp_segs_set, &outer_plan->info->projected_segs);
bitset_intersect (&temp_segs_set, &plan_segs_set);
outer_info->name_list = make_namelist_from_bitset (env, &temp_segs_set);
outer_info->name_count = pt_length_of_list (outer_info->name_list);
outer_info->expr_name_list =
parser_append_node (outer_info->name_list /* back */ , outer_info->expr_list /* front */ );
assert (outer_info->expr_name_list != NULL);
outer_info->expr_name_count = pt_length_of_list (outer_info->expr_name_list);
assert (outer_info->expr_name_count > 0);
assert (outer_info->expr_name_count == outer_info->expr_count + outer_info->name_count);
assert (outer_info->expr_count == bitset_cardinality (&outer_info->exprs_set) + 1 /* hash_key */ );
outer_info->pred_count = pt_length_of_list (outer_info->pred_list);
/* hash_key */
hash_key = pt_make_integer_value (parser, -1);
if (hash_key == NULL)
{
goto error_exit;
}
/* inner_info */
inner_info->expr_list = parser_append_node (inner_info->expr_list /* back */ , hash_key /* front */ );
inner_info->expr_count = pt_length_of_list (inner_info->expr_list);
bitset_assign (&temp_segs_set, &inner_plan->info->projected_segs);
bitset_intersect (&temp_segs_set, &plan_segs_set);
inner_info->name_list = make_namelist_from_bitset (env, &temp_segs_set);
inner_info->name_count = pt_length_of_list (inner_info->name_list);
inner_info->expr_name_list =
parser_append_node (inner_info->name_list /* back */ , inner_info->expr_list /* front */ );
assert (inner_info->expr_name_list != NULL);
inner_info->expr_name_count = pt_length_of_list (inner_info->expr_name_list);
assert (inner_info->expr_name_count > 0);
assert (inner_info->expr_name_count == inner_info->expr_count + inner_info->name_count);
assert (inner_info->expr_count == bitset_cardinality (&inner_info->exprs_set) + 1 /* hash_key */ );
inner_info->pred_count = pt_length_of_list (inner_info->pred_list);
/* final_info */
bitset_difference (pred_set, &plan->plan_un.join.join_terms);
if (IS_OUTER_JOIN_TYPE (plan->plan_un.join.join_type))
{
bitset_difference (pred_set, &plan->plan_un.join.during_join_terms);
}
bitset_assign (&plan_segs_set, &plan->info->projected_segs);
for (term_index = bitset_iterate (pred_set, &term_iter); term_index != -1;
term_index = bitset_next_member (&term_iter))
{
term = QO_ENV_TERM (env, term_index);
bitset_union (&plan_segs_set, &QO_TERM_SEGS (term));
}
bitset_assign (&temp_segs_set, &outer_plan->info->projected_segs);
bitset_intersect (&temp_segs_set, &plan_segs_set);
name_list = make_namelist_from_bitset (env, &temp_segs_set);
final_info->name_list = parser_append_node (name_list, final_info->name_list);
bitset_assign (&temp_segs_set, &inner_plan->info->projected_segs);
bitset_intersect (&temp_segs_set, &plan_segs_set);
name_list = make_namelist_from_bitset (env, &temp_segs_set);
final_info->name_list = parser_append_node (name_list, final_info->name_list);
final_info->name_count = pt_length_of_list (final_info->name_list);
ASSERT_NO_ERROR_OR_INTERRUPTED ();
assert (!pt_has_error (parser));
cleanup:
bitset_delset (&plan_segs_set);
bitset_delset (&during_segs_set);
bitset_delset (&temp_segs_set);
return error;
error_exit:
qo_clear_projection_info (env, info);
assert (!pt_has_error (parser));
if (error == NO_ERROR || er_errid () == NO_ERROR)
{
assert_release_error (er_errid () != NO_ERROR);
error = er_errid ();
}
goto cleanup;
}
/*
* qo_clear_projection_info() -
* return: None.
* env(in): Optimization environment.
* info(in): Projection information to clear.
*/
static void
qo_clear_projection_info (QO_ENV * env, PROJECTION_INFO * info)
{
PARSER_CONTEXT *parser;
assert (env != NULL);
assert (info != NULL);
parser = QO_ENV_PARSER (env);
assert (parser != NULL);
if (info != NULL)
{
qo_clear_projection_part_info (parser, &info->outer);
qo_clear_projection_part_info (parser, &info->inner);
qo_clear_projection_final_info (parser, &info->final);
}
}
/*
* qo_clean_projection_info() -
* return: None.
* parser(in): Parser context.
* info(in): Projection part information to clear.
*/
static void
qo_clear_projection_part_info (PARSER_CONTEXT * parser, PROJECTION_PART_INFO * info)
{
assert (parser != NULL);
assert (info != NULL);
if (info != NULL)
{
/* No need to free name_list and expr_list;
* they are linked through expr_name_list. */
if (info->expr_name_list)
{
parser_free_tree (parser, info->expr_name_list);
}
if (info->pred_list)
{
parser_free_tree (parser, info->pred_list);
}
bitset_delset (&info->exprs_set);
}
}
/*
* qo_clear_projection_final_info() -
* return: None.
* parser(in): Parser context
* info(in): Projection final information to clear.
*/
static void
qo_clear_projection_final_info (PARSER_CONTEXT * parser, PROJECTION_FINAL_INFO * info)
{
assert (parser != NULL);
assert (info != NULL);
if (info != NULL)
{
if (info->name_list)
{
parser_free_tree (parser, info->name_list);
}
}
}
/*
* qo_init_merge_info() -
* return: Error code (NO_ERROR if successful, error code otherwise).
* env(in): Optimization environment.
* plan(in): Execution plan for hash join.
* projection_info(in/out): Projection information used in the hash join execution plan.
* merge_info(in/out): Information used to merge the joined result.
*/
static int
qo_init_merge_info (QO_ENV * env, QO_PLAN * plan, PROJECTION_INFO * projection_info, QFILE_LIST_MERGE_INFO * merge_info)
{
PARSER_CONTEXT *parser = NULL;
PT_NODE *outer_part, *inner_part;
PT_NODE *outer_expr, *inner_expr;
PT_NODE *name_node;
int outer_expr_pos, inner_expr_pos;
QO_PLAN *outer_plan, *inner_plan;
QO_TERM *term;
BITSET term_segs_set;
BITSET_ITERATOR term_iter, seg_iter;
int term_index, seg_index;
PROJECTION_PART_INFO *outer_info, *inner_info;
PROJECTION_FINAL_INFO *final_info;
int *all_value_indexes = NULL;
int value_cnt, value_index, found_index;
int pos_cnt, pos_index;
bool need_update_pos;
int error = NO_ERROR;
assert (env != NULL);
assert (plan != NULL);
assert (projection_info != NULL);
assert (merge_info != NULL);
parser = QO_ENV_PARSER (env);
assert (parser != NULL);
bitset_init (&term_segs_set, env);
outer_plan = plan->plan_un.join.outer;
inner_plan = plan->plan_un.join.inner;
assert (outer_plan != NULL);
assert (inner_plan != NULL);
outer_info = &projection_info->outer;
inner_info = &projection_info->inner;
final_info = &projection_info->final;
/* join_type */
merge_info->join_type = plan->plan_un.join.join_type;
/* ls_column_cnt */
merge_info->ls_column_cnt = bitset_cardinality (&plan->plan_un.join.join_terms);
value_cnt = merge_info->ls_column_cnt;
assert (value_cnt > 0);
/* ls_outer_column, ls_inner_column, ls_outer_unique, ls_inner_unique */
all_value_indexes = (int *) pt_alloc_packing_buf (sizeof (int) * value_cnt * 4);
if (all_value_indexes == NULL)
{
goto error_exit;
}
memset (all_value_indexes, 0, sizeof (int) * value_cnt * 4);
merge_info->ls_outer_column = all_value_indexes;
merge_info->ls_inner_column = all_value_indexes + value_cnt;
/* Unused, but required to avoid faults in qdump_print_list_merge_info. */
merge_info->ls_outer_unique = all_value_indexes + value_cnt * 2;
merge_info->ls_inner_unique = all_value_indexes + value_cnt * 3;
outer_expr = outer_info->expr_list;
inner_expr = inner_info->expr_list;
/* after hash_key */
outer_expr_pos = 1;
inner_expr_pos = 1;
value_index = 0;
for (term_index = bitset_iterate (&plan->plan_un.join.join_terms, &term_iter);
term_index != -1; term_index = bitset_next_member (&term_iter))
{
assert (value_index < value_cnt);
term = QO_ENV_TERM (env, term_index);
if (BITSET_MEMBER (outer_info->exprs_set, term_index) && outer_expr != NULL)
{
/*
* Then we added an "extra" column for the expression to the outer_expr_list.
* We want to treat that expression as the outer expression,
* but we want to leave it off of the list of segments that are projected out of the merge.
* Take it off, but remember it in outer_part so that we can fix up domain info in a little while.
*/
merge_info->ls_outer_column[value_index] = outer_expr_pos;
assert (outer_expr_pos < outer_info->expr_count);
outer_part = outer_expr;
assert (outer_part != NULL);
outer_expr = outer_expr->next;
outer_expr_pos++;
}
else
{
bitset_assign (&term_segs_set, &QO_TERM_SEGS (term));
bitset_intersect (&term_segs_set, &outer_plan->info->projected_segs);
seg_index = bitset_iterate (&term_segs_set, &seg_iter);
if (seg_index == -1)
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
assert (bitset_next_member (&seg_iter) == -1);
outer_part = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_index));
found_index = pt_find_attribute (parser, outer_part, outer_info->expr_name_list);
if (found_index == -1)
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
merge_info->ls_outer_column[value_index] = found_index;
}
if (BITSET_MEMBER (inner_info->exprs_set, term_index) && inner_expr != NULL)
{
/*
* This situation is exactly analogous to the one above,
* except that we're concerned with the right (inner) side this time.
*/
merge_info->ls_inner_column[value_index] = inner_expr_pos;
assert (inner_expr_pos < inner_info->expr_count);
inner_part = inner_expr;
assert (inner_part != NULL);
inner_expr = inner_expr->next;
inner_expr_pos++;
}
else
{
bitset_assign (&term_segs_set, &QO_TERM_SEGS (term));
bitset_intersect (&term_segs_set, &inner_plan->info->projected_segs);
seg_index = bitset_iterate (&term_segs_set, &seg_iter);
if (seg_index == -1)
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
assert (bitset_next_member (&seg_iter) == -1);
inner_part = QO_SEG_PT_NODE (QO_ENV_SEG (env, seg_index));
found_index = pt_find_attribute (parser, inner_part, inner_info->expr_name_list);
if (found_index == -1)
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
merge_info->ls_inner_column[value_index] = found_index;
}
merge_info->ls_outer_unique[value_index] = false; /* Unused */
merge_info->ls_inner_unique[value_index] = false; /* Unused */
value_index++;
}
assert (value_index == value_cnt);
/* ls_pos_cnt */
pos_cnt = outer_info->name_count + inner_info->name_count;
assert (pos_cnt > 0);
/*
* Reduce the projected segments of the outer and inner plans by filtering out unnecessary segments.
* The positions of the remaining segments must be set.
*
* e.g.
* drop table if exists probe_input, build_input;
* create table probe_input (c1 int);
* create table build_input (c1 int);
*
* -- segs_len: 1 (b.c1)
* -- outer_segs_len + inner_segs_len: 2 (a.c1, b.c1)
* select --+ recompile use_hash
* b.c1 from probe_input a, build_input b where a.c1 = b.c1;
*/
need_update_pos = false;
if (final_info->name_count != 0 && final_info->name_count < pos_cnt)
{
pos_cnt = final_info->name_count;
need_update_pos = true;
}
merge_info->ls_pos_cnt = pos_cnt;
/* ls_outer_inner_list, ls_pos_list */
all_value_indexes = NULL;
all_value_indexes = (int *) pt_alloc_packing_buf (sizeof (int) * pos_cnt * 2);
if (all_value_indexes == NULL)
{
goto error_exit;
}
memset (all_value_indexes, 0, sizeof (int) * pos_cnt * 2);
merge_info->ls_outer_inner_list = all_value_indexes;
merge_info->ls_pos_list = all_value_indexes + pos_cnt;
if (need_update_pos)
{
name_node = final_info->name_list;
for (pos_index = 0; pos_index < pos_cnt; pos_index++)
{
assert (name_node != NULL);
if ((found_index = pt_find_attribute (parser, name_node, outer_info->expr_name_list)) != -1)
{
merge_info->ls_outer_inner_list[pos_index] = QFILE_OUTER_LIST;
}
else if ((found_index = pt_find_attribute (parser, name_node, inner_info->expr_name_list)) != -1)
{
merge_info->ls_outer_inner_list[pos_index] = QFILE_INNER_LIST;
}
else
{
/* impossible case */
assert_release_error (false);
goto error_exit;
}
merge_info->ls_pos_list[pos_index] = found_index;
name_node = name_node->next;
}
}
else
{
/*
* these could be sorted out arbitrily.
* This could make it easier to avoid the wrapper buildlist_proc,
* when no expressions, predicates, subqueries, fetches, or aggregation is involved.
* For now, we always build the same thing, with simple column concatenation.
*/
for (pos_index = 0; pos_index < outer_info->name_count; pos_index++)
{
merge_info->ls_outer_inner_list[pos_index] = QFILE_OUTER_LIST;
merge_info->ls_pos_list[pos_index] = outer_info->expr_count + pos_index;
}
for (pos_index = 0; pos_index < inner_info->name_count; pos_index++)
{
merge_info->ls_outer_inner_list[outer_info->name_count + pos_index] = QFILE_INNER_LIST;
merge_info->ls_pos_list[outer_info->name_count + pos_index] = inner_info->expr_count + pos_index;
}
}
ASSERT_NO_ERROR_OR_INTERRUPTED ();
assert (!pt_has_error (parser));
cleanup:
bitset_delset (&term_segs_set);
return error;
error_exit:
if (error == NO_ERROR && pt_has_error (parser))
{
pt_report_to_ersys (parser, PT_SEMANTIC);
pt_reset_error (parser);
}
if (error == NO_ERROR || er_errid () == NO_ERROR)
{
assert_release_error (er_errid () != NO_ERROR);
error = er_errid ();
}
goto cleanup;
}