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.10 1998/02/10 04:01:11 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 *mergesortop(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                 Rel                *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                 Rel                *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, -1, 26, 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         {
 154                 add_clause_to_rels(root, lfirst(clause));
 155         }
 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         CInfo      *clauseinfo = makeNode(CInfo);
 174
 175         /*
 176          * Retrieve all relids and vars contained within the clause.
 177          */
 178         clause_relids_vars((Node *) clause, &relids, &vars);
 179
 180
 181         clauseinfo->clause = (Expr *) clause;
 182         clauseinfo->notclause = contains_not((Node *) clause);
 183         clauseinfo->selectivity = 0;
 184         clauseinfo->indexids = NIL;
 185         clauseinfo->mergesortorder = (MergeOrder *) NULL;
 186         clauseinfo->hashjoinoperator = (Oid) 0;
 187
 188
 189
 190         if (length(relids) == 1)
 191         {
 192                 Rel                *rel = get_base_rel(root, lfirsti(relids));
 193
 194                 /*
 195                  * There is only one relation participating in 'clause', so
 196                  * 'clause' must be a restriction clause.
 197                  */
 198
 199                 /*
 200                  * the selectivity of the clause must be computed regardless of
 201                  * whether it's a restriction or a join clause
 202                  */
 203                 if (is_funcclause((Node *) clause))
 204                 {
 205
 206                         /*
 207                          * XXX If we have a func clause set selectivity to 1/3, really
 208                          * need a true selectivity function.
 209                          */
 210                         clauseinfo->selectivity = (Cost) 0.3333333;
 211                 }
 212                 else
 213                 {
 214                         clauseinfo->selectivity =
 215                                 compute_clause_selec(root, (Node *) clause,
 216                                                                          NIL);
 217                 }
 218                 rel->clauseinfo = lcons(clauseinfo,
 219                                                                 rel->clauseinfo);
 220         }
 221         else
 222         {
 223
 224                 /*
 225                  * 'clause' is a join clause, since there is more than one atom in
 226                  * the relid list.
 227                  */
 228
 229                 if (is_funcclause((Node *) clause))
 230                 {
 231
 232                         /*
 233                          * XXX If we have a func clause set selectivity to 1/3, really
 234                          * need a true selectivity function.
 235                          */
 236                         clauseinfo->selectivity = (Cost) 0.3333333;
 237                 }
 238                 else
 239                 {
 240                         clauseinfo->selectivity =
 241                                 compute_clause_selec(root, (Node *) clause,
 242                                                                          NIL);
 243                 }
 244                 add_join_clause_info_to_rels(root, clauseinfo, relids);
 245                 add_vars_to_rels(root, vars, relids);
 246         }
 247 }
 248
 249 /*
 250  * add-join-clause-info-to-rels--
 251  *        For every relation participating in a join clause, add 'clauseinfo' to
 252  *        the appropriate joininfo node(creating a new one and adding it to the
 253  *        appropriate rel node if necessary).
 254  *
 255  * 'clauseinfo' describes the join clause
 256  * 'join-relids' is the list of relations participating in the join clause
 257  *
 258  * Returns nothing.
 259  *
 260  */
 261 static void
 262 add_join_clause_info_to_rels(Query *root, CInfo *clauseinfo, List *join_relids)
 263 {
 264         List       *join_relid;
 265
 266         foreach(join_relid, join_relids)
 267         {
 268                 JInfo      *joininfo;
 269                 List       *other_rels = NIL;
 270                 List       *rel;
 271
 272                 foreach(rel, join_relids)
 273                 {
 274                         if (lfirsti(rel) != lfirsti(join_relid))
 275                                 other_rels = lappendi(other_rels, lfirsti(rel));
 276                 }
 277
 278                 joininfo =
 279                         find_joininfo_node(get_base_rel(root, lfirsti(join_relid)),
 280                                                            other_rels);
 281                 joininfo->jinfoclauseinfo =
 282                         lcons(copyObject((void *) clauseinfo), joininfo->jinfoclauseinfo);
 283
 284         }
 285 }
 286
 287 /*
 288  * add-vars-to-rels--
 289  *        For each variable appearing in a clause,
 290  *        (1) If a targetlist entry for the variable is not already present in
 291  *                the appropriate relation's target list, add one.
 292  *        (2) If a targetlist entry is already present, but the var is part of a
 293  *                join clause, add the relids of the join relations to the JoinList
 294  *                entry of the targetlist entry.
 295  *
 296  *        'vars' is the list of var nodes
 297  *        'join-relids' is the list of relids appearing in the join clause
 298  *              (if this is a join clause)
 299  *
 300  *        Returns nothing.
 301  */
 302 static void
 303 add_vars_to_rels(Query *root, List *vars, List *join_relids)
 304 {
 305         Var                *var;
 306         List       *temp = NIL;
 307         Rel                *rel = (Rel *) NULL;
 308         TargetEntry *tlistentry;
 309
 310         foreach(temp, vars)
 311         {
 312                 var = (Var *) lfirst(temp);
 313                 rel = get_base_rel(root, var->varno);
 314                 tlistentry = tlistentry_member(var, rel->targetlist);
 315                 if (tlistentry == NULL)
 316                         /* add a new entry */
 317                         add_tl_element(rel, var);
 318         }
 319 }
 320
 321 /*****************************************************************************
 322  *
 323  *       JOININFO
 324  *
 325  *****************************************************************************/
 326
 327 /*
 328  * initialize-join-clause-info--
 329  *        Set the MergeSortable or HashJoinable field for every joininfo node
 330  *        (within a rel node) and the MergeSortOrder or HashJoinOp field for
 331  *        each clauseinfo node(within a joininfo node) for all relations in a
 332  *        query.
 333  *
 334  *        Returns nothing.
 335  */
 336 void
 337 initialize_join_clause_info(List *rel_list)
 338 {
 339         List       *x,
 340                            *y,
 341                            *z;
 342         Rel                *rel;
 343         JInfo      *joininfo;
 344         CInfo      *clauseinfo;
 345         Expr       *clause;
 346
 347         foreach(x, rel_list)
 348         {
 349                 rel = (Rel *) lfirst(x);
 350                 foreach(y, rel->joininfo)
 351                 {
 352                         joininfo = (JInfo *) lfirst(y);
 353                         foreach(z, joininfo->jinfoclauseinfo)
 354                         {
 355                                 clauseinfo = (CInfo *) lfirst(z);
 356                                 clause = clauseinfo->clause;
 357                                 if (join_clause_p((Node *) clause))
 358                                 {
 359                                         MergeOrder *sortop = (MergeOrder *) NULL;
 360                                         Oid                     hashop = (Oid) NULL;
 361
 362                                         if (_enable_mergesort_)
 363                                                 sortop = mergesortop(clause);
 364                                         if (_enable_hashjoin_)
 365                                                 hashop = hashjoinop(clause);
 366
 367                                         if (sortop)
 368                                         {
 369                                                 clauseinfo->mergesortorder = sortop;
 370                                                 joininfo->mergesortable = true;
 371                                         }
 372                                         if (hashop)
 373                                         {
 374                                                 clauseinfo->hashjoinoperator = hashop;
 375                                                 joininfo->hashjoinable = true;
 376                                         }
 377                                 }
 378                         }
 379                 }
 380         }
 381 }
 382
 383 /*
 384  * mergesortop--
 385  *        Returns the mergesort operator of an operator iff 'clause' is
 386  *        mergesortable, i.e., both operands are single vars and the operator is
 387  *        a mergesortable operator.
 388  */
 389 static MergeOrder *
 390 mergesortop(Expr *clause)
 391 {
 392         Oid                     leftOp,
 393                                 rightOp;
 394         bool            sortable;
 395
 396         sortable = op_mergesortable(((Oper *) clause->oper)->opno,
 397                                                                 (get_leftop(clause))->vartype,
 398                                                                 (get_rightop(clause))->vartype,
 399                                                                 &leftOp,
 400                                                                 &rightOp);
 401
 402         if (sortable)
 403         {
 404                 MergeOrder *morder = makeNode(MergeOrder);
 405
 406                 morder->join_operator = ((Oper *) clause->oper)->opno;
 407                 morder->left_operator = leftOp;
 408                 morder->right_operator = rightOp;
 409                 morder->left_type = (get_leftop(clause))->vartype;
 410                 morder->right_type = (get_rightop(clause))->vartype;
 411                 return (morder);
 412         }
 413         else
 414                 return (NULL);
 415 }
 416
 417 /*
 418  * hashjoinop--
 419  *        Returns the hashjoin operator of an operator iff 'clause' is
 420  *        hashjoinable, i.e., both operands are single vars and the operator is
 421  *        a hashjoinable operator.
 422  */
 423 static Oid
 424 hashjoinop(Expr *clause)
 425 {
 426         return (op_hashjoinable(((Oper *) clause->oper)->opno,
 427                                                         (get_leftop(clause))->vartype,
 428                                                         (get_rightop(clause))->vartype));
 429 }