/* * Copyright (C) 2008 Search Solution Corporation. All rights reserved by Search Solution. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2 of the License. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * */ /* * query_planner.h - Query plan */ #ifndef _QUERY_PLANNER_H_ #define _QUERY_PLANNER_H_ #ident "$Id$" #include "optimizer.h" #include "query_bitset.h" #define QO_CPU_WEIGHT 0.0025 typedef enum { QO_PLANTYPE_SCAN, QO_PLANTYPE_SORT, QO_PLANTYPE_JOIN, QO_PLANTYPE_FOLLOW, QO_PLANTYPE_WORST } QO_PLANTYPE; typedef enum { QO_SCANMETHOD_SEQ_SCAN, QO_SCANMETHOD_INDEX_SCAN } QO_SCANMETHOD; typedef enum { QO_JOINMETHOD_NL_JOIN, QO_JOINMETHOD_IDX_JOIN, QO_JOINMETHOD_MERGE_JOIN } QO_JOINMETHOD; typedef struct qo_plan_vtbl QO_PLAN_VTBL; struct qo_plan_vtbl { const char *plan_string; void (*fprint_fn) (QO_PLAN *, FILE *, int); void (*walk_fn) (QO_PLAN *, void (*)(QO_PLAN *, void *), void *, void (*)(QO_PLAN *, void *), void *); void (*free_fn) (QO_PLAN *); void (*cost_fn) (QO_PLAN *); void (*default_cost) (QO_PLAN *); void (*info_fn) (QO_PLAN *, FILE *, int); const char *info_string; }; typedef enum { PLAN_COMP_UNK = -2, PLAN_COMP_LT = -1, PLAN_COMP_EQ = 0, PLAN_COMP_GT = 1 } QO_PLAN_COMPARE_RESULT; struct qo_plan { QO_INFO *info; int refcount; /* * A plan is "top-rooted" if it is a top level plan */ bool top_rooted; /* * A plan is "well-rooted" if it is a scan plan, or if it is a follow * plan whose subplan is itself well-rooted. These are plans that * won't require the construction of any temporary files during * execution. The current generation of XASL can't cope with * temporary files for some kinds of queries (in particular, those * with subqueries in the select list), so we have to be sure to * avoid generating plans that require that kind of implementation. */ bool well_rooted; /* CPU and IO cost which are fixed against join position(inner or outer) */ double fixed_cpu_cost, fixed_io_cost; /* CPU and IO cost which are variable according to join position */ double variable_cpu_cost, variable_io_cost; BITSET sarged_terms; QO_EQCLASS *order; PT_NODE *iscan_sort_list; /* sorting fields */ /* * The set of correlated subqueries that are "covered" by this plan. * These are the subqueries that must be reevaluated every time a new * candidate row is produced by this plan. */ BITSET subqueries; QO_PLANTYPE plan_type; QO_PLAN_VTBL *vtbl; union { struct { QO_PLAN *link; } free; struct { QO_SCANMETHOD scan_method; /* SEQ_SCAN, INDEX_SCAN */ QO_NODE *node; BITSET terms; bool equi; BITSET kf_terms; QO_NODE_INDEX_ENTRY *index; } scan; /* * Sort nodes are now really "build a temp file" nodes; the * created temp file may be sorted or unsorted. If sorted, the * `order' field indicates the sorting order; if unsorted, the * `order' field is NULL. The `tmpnum' field is assigned during * plan finalization; it is the logical number of the temporary * file to be created at runtime. */ struct { SORT_TYPE sort_type; #if 0 /* DO NOT DELETE ME - need future work */ SORT_LIST *sort_list; #endif QO_PLAN *subplan; XASL_NODE *xasl; } sort; struct { JOIN_TYPE join_type; /* JOIN_INNER, _LEFT, _RIGHT, _OUTER */ QO_JOINMETHOD join_method; /* NL_JOIN, MERGE_JOIN */ QO_PLAN *outer; QO_PLAN *inner; BITSET join_terms; /* all join edges */ BITSET during_join_terms; /* during join terms */ BITSET other_outer_join_terms; /* for merge outer join only */ BITSET after_join_terms; /* after join terms */ } join; struct { QO_PLAN *head; QO_TERM *path; } follow; } plan_un; }; #define qo_plan_add_ref(p) ((p->refcount)++, (p)) #define qo_plan_del_ref(p) do { \ QO_PLAN *__p = (p); \ if ((__p) && --(__p->refcount) == 0) \ qo_plan_free(__p); \ } while(0) #define qo_plan_release(p) do { \ QO_PLAN *__p = (p); \ if ((__p) && (__p->refcount) == 0) \ qo_plan_free(__p); \ } while(0) #define NPLANS 4 /* Maximum number of plans to keep in a PlanVec */ typedef struct qo_planvec QO_PLANVEC; struct qo_planvec { bool overflow; int nplans; QO_PLAN *plan[NPLANS]; }; struct qo_info { struct qo_info *next; /* * The environment relative to which all of the following sets, etc. * make sense. */ QO_ENV *env; /* * The Planner instance to which this Info node belongs. I wish * we didn't have to do this, but there are just enough occassions * where we need the back pointer that it is easier just to include * it and be done with it. This pointer is NULL if this info node * has been "detached" from the planner; this happens when the * winning plan is "finalized". */ QO_PLANNER *planner; /* * The lowest-cost plan without regard to ordering. */ QO_PLANVEC best_no_order; /* * The set of nodes joined by the plans at this node. */ BITSET nodes; /* * All of the terms accounted for by the plans in this node and their * descendents, i.e., the complement of the terms remaining to be * dealt with. */ BITSET terms; /* * The equivalence classes represented by all of the attributes * (segments) joined together in this node. */ BITSET eqclasses; /* * 'projected_segs' is the set of segments (attributes) that need to * be projected from this plan produced by this node in order to * satisfy the needs of upper level plans. 'projected_size' is the * number of bytes per record required by 'projected_segs'. * 'cardinality' is the estimated cardinality of the results produced * by plans at this node. */ BITSET projected_segs; int projected_size; double cardinality; /* * One plan for each equivalence class, in each case the best we have * seen so far. This vector is NULL after a node is detached. */ QO_PLANVEC *planvec; /* * The last join level. */ int join_unit; /* * `detached' is true iff the node has been detached; we can no * longer just use the value of `plans' as the indicator because * dependent derived tables can give rise to join graphs that couple * nodes together without creating an equivalence class, and thus * without the need to populate the `plans' vector. */ int detached; }; struct qo_planner { /* * The struct that encapsulates the information involved in searching * for an optimal query plan. */ /* * The environment that supplies the various nodes, edges, segments, etc. */ QO_ENV *env; /* * The relations being considered in this join; there are N of them. */ QO_NODE *node; unsigned int N; /* * The join terms (e.g., employee.dno = dept.dno); there are T of * them, E of which are actual edges in the join graph. node_mask is * a bit mask used to mask out non-node terms from node bitsets. * M is simply 2^N, and is the size of the join_info vector that will * be allocated. */ QO_TERM *term; unsigned int E, M, T; unsigned long node_mask; /* * The last join level. */ int join_unit; /* * The path segments involved in the various join terms, and the * equivalence classes implied by those joins (e.g., if we have join * terms c1 = c2 and c2 = c3, (c1,c2,c3) is an equivalence class for * the purposes of determining sort orderings). */ QO_SEGMENT *segment; unsigned int S; QO_EQCLASS *eqclass; unsigned int EQ; /* * The partitions (strong components) of the join graph. */ QO_PARTITION *partition; unsigned int P; /* * The (level-1 correlated) subqueries used in this query. */ QO_SUBQUERY *subqueries; BITSET all_subqueries; unsigned int Q; /* * The final set of segments to be projected out of the top-level * plan produced by this planner. */ BITSET final_segs; QO_INFO **node_info; QO_INFO **join_info; QO_INFO **cp_info; QO_INFO *best_info; QO_PLAN *worst_plan; QO_INFO *worst_info; /* alloced info list */ QO_INFO *info_list; /* * true iff qo_planner_cleanup() needs to be called before freeing * this planner. This is needed to help clean up after aborts, when * control flow takes an unexpected longjmp. */ int cleanup_needed; }; extern void qo_plans_stats (FILE *); #if !defined(WINDOWS) extern double log2 (double); #endif extern QO_PLAN *qo_planner_search (QO_ENV *); extern void qo_planner_free (QO_PLANNER *); extern void qo_info_stats (FILE *); #endif /* _QUERY_PLANNER_H_ */