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