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