granicus.if.org Git - postgresql/blob - src/backend/optimizer/plan/initsplan.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * initsplan.c--
   4  *        Target list, qualification, joininfo initialization routines
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.14 1998/08/04 16:44:14 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <sys/types.h>
  15
  16 #include "postgres.h"
  17
  18 #include "nodes/pg_list.h"
  19 #include "nodes/plannodes.h"
  20 #include "nodes/parsenodes.h"
  21 #include "nodes/relation.h"
  22 #include "nodes/makefuncs.h"
  23
  24 #include "utils/lsyscache.h"
  25 #include "utils/palloc.h"
  26
  27 #include "optimizer/internal.h"
  28 #include "optimizer/planmain.h"
  29 #include "optimizer/joininfo.h"
  30 #include "optimizer/pathnode.h"
  31 #include "optimizer/tlist.h"
  32 #include "optimizer/var.h"
  33 #include "optimizer/clauses.h"
  34 #include "optimizer/cost.h"
  35
  36 extern int      Quiet;
  37
  38 static void add_clause_to_rels(Query *root, List *clause);
  39 static void
  40 add_join_clause_info_to_rels(Query *root, CInfo *clauseinfo,
  41                                                          List *join_relids);
  42 static void add_vars_to_rels(Query *root, List *vars, List *join_relids);
  43
  44 static MergeOrder *mergejoinop(Expr *clause);
  45 static Oid      hashjoinop(Expr *clause);
  46
  47
  48 /*****************************************************************************
  49  *
  50  *       TARGET LISTS
  51  *
  52  *****************************************************************************/
  53
  54 /*
  55  * initialize_rel_nodes--
  56  *        Creates rel nodes for every relation mentioned in the target list
  57  *        'tlist' (if a node hasn't already been created) and adds them to
  58  *        *query-relation-list*.  Creates targetlist entries for each member of
  59  *        'tlist' and adds them to the tlist field of the appropriate rel node.
  60  *
  61  *        Returns nothing.
  62  */
  63 void
  64 initialize_base_rels_list(Query *root, List *tlist)
  65 {
  66         List       *tlist_vars = NIL;
  67         List       *l = NIL;
  68         List       *tvar = NIL;
  69
  70         foreach(l, tlist)
  71         {
  72                 TargetEntry *entry = (TargetEntry *) lfirst(l);
  73
  74                 tlist_vars = append(tlist_vars, pull_var_clause(entry->expr));
  75         }
  76
  77         /* now, the target list only contains Var nodes */
  78         foreach(tvar, tlist_vars)
  79         {
  80                 Var                *var;
  81                 Index           varno;
  82                 RelOptInfo                 *result;
  83
  84                 var = (Var *) lfirst(tvar);
  85                 varno = var->varno;
  86                 result = get_base_rel(root, varno);
  87
  88                 add_tl_element(result, var);
  89         }
  90 }
  91
  92 /*
  93  * add_missing_variables_to_base_rels -
  94  *        If we have range variable(s) in the FROM clause that does not appear
  95  *        in the target list nor qualifications, we add it to the base relation
  96  *        list. For instance, "select f.x from foo f, foo f2" is a join of f and
  97  *        f2. Note that if we have "select foo.x from foo f", it also gets turned
  98  *        into a join.
  99  */
 100 void
 101 add_missing_vars_to_base_rels(Query *root, List *tlist)
 102 {
 103         List       *l;
 104         int                     varno;
 105
 106         varno = 1;
 107         foreach(l, root->rtable)
 108         {
 109                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
 110                 List       *relids;
 111                 RelOptInfo                 *result;
 112                 Var                *var;
 113
 114                 relids = lconsi(varno, NIL);
 115                 if (rte->inFromCl &&
 116                         !rel_member(relids, root->base_relation_list_))
 117                 {
 118
 119                         var = makeVar(varno, -2, 26, -1, 0, varno, -2);
 120                         /* add it to base_relation_list_ */
 121                         result = get_base_rel(root, varno);
 122                         add_tl_element(result, var);
 123                 }
 124                 pfree(relids);
 125                 varno++;
 126         }
 127
 128         return;
 129 }
 130
 131 /*****************************************************************************
 132  *
 133  *        QUALIFICATIONS
 134  *
 135  *****************************************************************************/
 136
 137
 138
 139 /*
 140  * initialize-qualification--
 141  *        Initializes ClauseInfo and JoinInfo fields of relation entries for all
 142  *        relations appearing within clauses.  Creates new relation entries if
 143  *        necessary, adding them to *query-relation-list*.
 144  *
 145  *        Returns nothing of interest.
 146  */
 147 void
 148 initialize_base_rels_jinfo(Query *root, List *clauses)
 149 {
 150         List       *clause;
 151
 152         foreach(clause, clauses)
 153                 add_clause_to_rels(root, lfirst(clause));
 154         return;
 155 }
 156
 157 /*
 158  * add-clause-to-rels--
 159  *        Add clause information to either the 'ClauseInfo' or 'JoinInfo' field
 160  *        of a relation entry(depending on whether or not the clause is a join)
 161  *        by creating a new ClauseInfo node and setting appropriate fields
 162  *        within the nodes.
 163  *
 164  *        Returns nothing of interest.
 165  */
 166 static void
 167 add_clause_to_rels(Query *root, List *clause)
 168 {
 169         List       *relids;
 170         List       *vars;
 171         CInfo      *clauseinfo = makeNode(CInfo);
 172
 173         /*
 174          * Retrieve all relids and vars contained within the clause.
 175          */
 176         clause_relids_vars((Node *) clause, &relids, &vars);
 177
 178
 179         clauseinfo->clause = (Expr *) clause;
 180         clauseinfo->notclause = contains_not((Node *) clause);
 181         clauseinfo->selectivity = 0;
 182         clauseinfo->indexids = NIL;
 183         clauseinfo->mergejoinorder = (MergeOrder *) NULL;
 184         clauseinfo->hashjoinoperator = (Oid) 0;
 185
 186
 187
 188         if (length(relids) == 1)
 189         {
 190                 RelOptInfo                 *rel = get_base_rel(root, lfirsti(relids));
 191
 192                 /*
 193                  * There is only one relation participating in 'clause', so
 194                  * 'clause' must be a restriction clause.
 195                  */
 196
 197                 /*
 198                  * the selectivity of the clause must be computed regardless of
 199                  * whether it's a restriction or a join clause
 200                  */
 201                 if (is_funcclause((Node *) clause))
 202                 {
 203
 204                         /*
 205                          * XXX If we have a func clause set selectivity to 1/3, really
 206                          * need a true selectivity function.
 207                          */
 208                         clauseinfo->selectivity = (Cost) 0.3333333;
 209                 }
 210                 else
 211                 {
 212                         clauseinfo->selectivity =
 213                                 compute_clause_selec(root, (Node *) clause,
 214                                                                          NIL);
 215                 }
 216                 rel->clauseinfo = lcons(clauseinfo,
 217                                                                 rel->clauseinfo);
 218         }
 219         else
 220         {
 221
 222                 /*
 223                  * 'clause' is a join clause, since there is more than one atom in
 224                  * the relid list.
 225                  */
 226
 227                 if (is_funcclause((Node *) clause))
 228                 {
 229
 230                         /*
 231                          * XXX If we have a func clause set selectivity to 1/3, really
 232                          * need a true selectivity function.
 233                          */
 234                         clauseinfo->selectivity = (Cost) 0.3333333;
 235                 }
 236                 else
 237                 {
 238                         clauseinfo->selectivity =
 239                                 compute_clause_selec(root, (Node *) clause,
 240                                                                          NIL);
 241                 }
 242                 add_join_clause_info_to_rels(root, clauseinfo, relids);
 243                 add_vars_to_rels(root, vars, relids);
 244         }
 245 }
 246
 247 /*
 248  * add-join-clause-info-to-rels--
 249  *        For every relation participating in a join clause, add 'clauseinfo' to
 250  *        the appropriate joininfo node(creating a new one and adding it to the
 251  *        appropriate rel node if necessary).
 252  *
 253  * 'clauseinfo' describes the join clause
 254  * 'join-relids' is the list of relations participating in the join clause
 255  *
 256  * Returns nothing.
 257  *
 258  */
 259 static void
 260 add_join_clause_info_to_rels(Query *root, CInfo *clauseinfo, List *join_relids)
 261 {
 262         List       *join_relid;
 263
 264         foreach(join_relid, join_relids)
 265         {
 266                 JInfo      *joininfo;
 267                 List       *other_rels = NIL;
 268                 List       *rel;
 269
 270                 foreach(rel, join_relids)
 271                 {
 272                         if (lfirsti(rel) != lfirsti(join_relid))
 273                                 other_rels = lappendi(other_rels, lfirsti(rel));
 274                 }
 275
 276                 joininfo =
 277                         find_joininfo_node(get_base_rel(root, lfirsti(join_relid)),
 278                                                            other_rels);
 279                 joininfo->jinfoclauseinfo =
 280                         lcons(copyObject((void *) clauseinfo), joininfo->jinfoclauseinfo);
 281
 282         }
 283 }
 284
 285 /*
 286  * add-vars-to-rels--
 287  *        For each variable appearing in a clause,
 288  *        (1) If a targetlist entry for the variable is not already present in
 289  *                the appropriate relation's target list, add one.
 290  *        (2) If a targetlist entry is already present, but the var is part of a
 291  *                join clause, add the relids of the join relations to the JoinList
 292  *                entry of the targetlist entry.
 293  *
 294  *        'vars' is the list of var nodes
 295  *        'join-relids' is the list of relids appearing in the join clause
 296  *              (if this is a join clause)
 297  *
 298  *        Returns nothing.
 299  */
 300 static void
 301 add_vars_to_rels(Query *root, List *vars, List *join_relids)
 302 {
 303         Var                *var;
 304         List       *temp = NIL;
 305         RelOptInfo                 *rel = (RelOptInfo *) NULL;
 306         TargetEntry *tlistentry;
 307
 308         foreach(temp, vars)
 309         {
 310                 var = (Var *) lfirst(temp);
 311                 rel = get_base_rel(root, var->varno);
 312                 tlistentry = tlistentry_member(var, rel->targetlist);
 313                 if (tlistentry == NULL)
 314                         /* add a new entry */
 315                         add_tl_element(rel, var);
 316         }
 317 }
 318
 319 /*****************************************************************************
 320  *
 321  *       JOININFO
 322  *
 323  *****************************************************************************/
 324
 325 /*
 326  * initialize-join-clause-info--
 327  *        Set the MergeJoinable or HashJoinable field for every joininfo node
 328  *        (within a rel node) and the MergeJoinOrder or HashJoinOp field for
 329  *        each clauseinfo node(within a joininfo node) for all relations in a
 330  *        query.
 331  *
 332  *        Returns nothing.
 333  */
 334 void
 335 initialize_join_clause_info(List *rel_list)
 336 {
 337         List       *x,
 338                            *y,
 339                            *z;
 340         RelOptInfo                 *rel;
 341         JInfo      *joininfo;
 342         CInfo      *clauseinfo;
 343         Expr       *clause;
 344
 345         foreach(x, rel_list)
 346         {
 347                 rel = (RelOptInfo *) lfirst(x);
 348                 foreach(y, rel->joininfo)
 349                 {
 350                         joininfo = (JInfo *) lfirst(y);
 351                         foreach(z, joininfo->jinfoclauseinfo)
 352                         {
 353                                 clauseinfo = (CInfo *) lfirst(z);
 354                                 clause = clauseinfo->clause;
 355                                 if (join_clause_p((Node *) clause))
 356                                 {
 357                                         MergeOrder *sortop = (MergeOrder *) NULL;
 358                                         Oid                     hashop = (Oid) NULL;
 359
 360                                         if (_enable_mergejoin_)
 361                                                 sortop = mergejoinop(clause);
 362                                         if (_enable_hashjoin_)
 363                                                 hashop = hashjoinop(clause);
 364
 365                                         if (sortop)
 366                                         {
 367                                                 clauseinfo->mergejoinorder = sortop;
 368                                                 joininfo->mergejoinable = true;
 369                                         }
 370                                         if (hashop)
 371                                         {
 372                                                 clauseinfo->hashjoinoperator = hashop;
 373                                                 joininfo->hashjoinable = true;
 374                                         }
 375                                 }
 376                         }
 377                 }
 378         }
 379 }
 380
 381 /*
 382  * mergejoinop--
 383  *        Returns the mergejoin operator of an operator iff 'clause' is
 384  *        mergejoinable, i.e., both operands are single vars and the operator is
 385  *        a mergejoinable operator.
 386  */
 387 static MergeOrder *
 388 mergejoinop(Expr *clause)
 389 {
 390         Oid                     leftOp,
 391                                 rightOp;
 392         bool            sortable;
 393
 394         sortable = op_mergejoinable(((Oper *) clause->oper)->opno,
 395                                                                 (get_leftop(clause))->vartype,
 396                                                                 (get_rightop(clause))->vartype,
 397                                                                 &leftOp,
 398                                                                 &rightOp);
 399
 400         if (sortable)
 401         {
 402                 MergeOrder *morder = makeNode(MergeOrder);
 403
 404                 morder->join_operator = ((Oper *) clause->oper)->opno;
 405                 morder->left_operator = leftOp;
 406                 morder->right_operator = rightOp;
 407                 morder->left_type = (get_leftop(clause))->vartype;
 408                 morder->right_type = (get_rightop(clause))->vartype;
 409                 return (morder);
 410         }
 411         else
 412                 return (NULL);
 413 }
 414
 415 /*
 416  * hashjoinop--
 417  *        Returns the hashjoin operator of an operator iff 'clause' is
 418  *        hashjoinable, i.e., both operands are single vars and the operator is
 419  *        a hashjoinable operator.
 420  */
 421 static Oid
 422 hashjoinop(Expr *clause)
 423 {
 424         return (op_hashjoinable(((Oper *) clause->oper)->opno,
 425                                                         (get_leftop(clause))->vartype,
 426                                                         (get_rightop(clause))->vartype));
 427 }