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  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
   7  * Portions Copyright (c) 1994, Regents of the University of California
   8  *
   9  *
  10  * IDENTIFICATION
  11  *        $Header: /cvsroot/pgsql/src/backend/optimizer/plan/initsplan.c,v 1.45 2000/02/15 20:49:18 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include <sys/types.h>
  16
  17 #include "postgres.h"
  18 #include "catalog/pg_type.h"
  19 #include "nodes/makefuncs.h"
  20 #include "optimizer/clauses.h"
  21 #include "optimizer/cost.h"
  22 #include "optimizer/joininfo.h"
  23 #include "optimizer/pathnode.h"
  24 #include "optimizer/paths.h"
  25 #include "optimizer/planmain.h"
  26 #include "optimizer/tlist.h"
  27 #include "optimizer/var.h"
  28 #include "utils/lsyscache.h"
  29
  30
  31 static void add_restrict_and_join_to_rel(Query *root, Node *clause);
  32 static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
  33                                                                   Relids join_relids);
  34 static void add_vars_to_targetlist(Query *root, List *vars);
  35 static void check_mergejoinable(RestrictInfo *restrictinfo);
  36 static void check_hashjoinable(RestrictInfo *restrictinfo);
  37
  38
  39 /*****************************************************************************
  40  *
  41  *       TARGET LISTS
  42  *
  43  *****************************************************************************/
  44
  45 /*
  46  * make_var_only_tlist
  47  *        Creates rel nodes for every relation mentioned in the target list
  48  *        'tlist' (if a node hasn't already been created) and adds them to
  49  *        *query_relation_list*.  Creates targetlist entries for each member of
  50  *        'tlist' and adds them to the tlist field of the appropriate rel node.
  51  */
  52 void
  53 make_var_only_tlist(Query *root, List *tlist)
  54 {
  55         List       *tlist_vars = pull_var_clause((Node *) tlist, false);
  56
  57         add_vars_to_targetlist(root, tlist_vars);
  58         freeList(tlist_vars);
  59 }
  60
  61 /*
  62  * add_vars_to_targetlist
  63  *        For each variable appearing in the list, add it to the relation's
  64  *        targetlist if not already present.  Rel nodes will also be created
  65  *        if not already present.
  66  */
  67 static void
  68 add_vars_to_targetlist(Query *root, List *vars)
  69 {
  70         List       *temp;
  71
  72         foreach(temp, vars)
  73         {
  74                 Var                *var = (Var *) lfirst(temp);
  75                 RelOptInfo *rel = get_base_rel(root, var->varno);
  76
  77                 add_var_to_tlist(rel, var);
  78         }
  79 }
  80
  81 /*
  82  * add_missing_rels_to_query
  83  *
  84  *        If we have a range variable in the FROM clause that does not appear
  85  *        in the target list nor qualifications, we must add it to the base
  86  *        relation list so that it will be joined.  For instance, "select f.x
  87  *        from foo f, foo f2" is a join of f and f2.  Note that if we have
  88  *        "select foo.x from foo f", it also gets turned into a join (between
  89  *        foo as foo and foo as f).
  90  *
  91  *        To avoid putting useless entries into the per-relation targetlists,
  92  *        this should only be called after all the variables in the targetlist
  93  *        and quals have been processed by the routines above.
  94  */
  95 void
  96 add_missing_rels_to_query(Query *root)
  97 {
  98         int                     varno = 1;
  99         List       *l;
 100
 101         foreach(l, root->rtable)
 102         {
 103                 RangeTblEntry *rte = (RangeTblEntry *) lfirst(l);
 104
 105                 if (rte->inJoinSet)
 106                 {
 107                         RelOptInfo *rel = get_base_rel(root, varno);
 108
 109                         /* If the rel isn't otherwise referenced, give it a dummy
 110                          * targetlist consisting of its own OID.
 111                          */
 112                         if (rel->targetlist == NIL)
 113                         {
 114                                 Var                *var = makeVar(varno, ObjectIdAttributeNumber,
 115                                                                                   OIDOID, -1, 0);
 116                                 add_var_to_tlist(rel, var);
 117                         }
 118                 }
 119                 varno++;
 120         }
 121 }
 122
 123 /*****************************************************************************
 124  *
 125  *        QUALIFICATIONS
 126  *
 127  *****************************************************************************/
 128
 129
 130
 131 /*
 132  * add_restrict_and_join_to_rels
 133  *        Fill RestrictInfo and JoinInfo lists of relation entries for all
 134  *        relations appearing within clauses.  Creates new relation entries if
 135  *        necessary, adding them to *query_relation_list*.
 136  *
 137  * 'clauses': the list of clauses in the cnfify'd query qualification.
 138  */
 139 void
 140 add_restrict_and_join_to_rels(Query *root, List *clauses)
 141 {
 142         List       *clause;
 143
 144         foreach(clause, clauses)
 145                 add_restrict_and_join_to_rel(root, (Node*) lfirst(clause));
 146 }
 147
 148 /*
 149  * add_restrict_and_join_to_rel
 150  *        Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
 151  *        (depending on whether the clause is a join) of each base relation
 152  *        mentioned in the clause.  A RestrictInfo node is created and added to
 153  *        the appropriate list for each rel.  Also, if the clause uses a
 154  *        mergejoinable operator, enter the left- and right-side expressions
 155  *        into the query's lists of equijoined vars.
 156  */
 157 static void
 158 add_restrict_and_join_to_rel(Query *root, Node *clause)
 159 {
 160         RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 161         Relids          relids;
 162         List       *vars;
 163
 164         restrictinfo->clause = (Expr *) clause;
 165         restrictinfo->subclauseindices = NIL;
 166         restrictinfo->mergejoinoperator = InvalidOid;
 167         restrictinfo->left_sortop = InvalidOid;
 168         restrictinfo->right_sortop = InvalidOid;
 169         restrictinfo->hashjoinoperator = InvalidOid;
 170
 171         /*
 172          * Retrieve all relids and vars contained within the clause.
 173          */
 174         clause_get_relids_vars(clause, &relids, &vars);
 175
 176         if (length(relids) == 1)
 177         {
 178                 /*
 179                  * There is only one relation participating in 'clause', so
 180                  * 'clause' must be a restriction clause for that relation.
 181                  */
 182                 RelOptInfo *rel = get_base_rel(root, lfirsti(relids));
 183
 184                 rel->baserestrictinfo = lcons(restrictinfo,
 185                                                                           rel->baserestrictinfo);
 186                 /*
 187                  * Check for a "mergejoinable" clause even though it's not a join
 188                  * clause.  This is so that we can recognize that "a.x = a.y" makes
 189                  * x and y eligible to be considered equal, even when they belong
 190                  * to the same rel.  Without this, we would not recognize that
 191                  * "a.x = a.y AND a.x = b.z AND a.y = c.q" allows us to consider
 192                  * z and q equal after their rels are joined.
 193                  */
 194                 check_mergejoinable(restrictinfo);
 195         }
 196         else
 197         {
 198                 /*
 199                  * 'clause' is a join clause, since there is more than one atom in
 200                  * the relid list.  Set additional RestrictInfo fields for joining.
 201                  *
 202                  * We need the merge info whether or not mergejoin is enabled (for
 203                  * constructing equijoined-var lists), but we don't bother setting
 204                  * hash info if hashjoin is disabled.
 205                  */
 206                 check_mergejoinable(restrictinfo);
 207                 if (enable_hashjoin)
 208                         check_hashjoinable(restrictinfo);
 209                 /*
 210                  * Add clause to the join lists of all the relevant
 211                  * relations.  (If, perchance, 'clause' contains NO vars, then
 212                  * nothing will happen...)
 213                  */
 214                 add_join_info_to_rels(root, restrictinfo, relids);
 215                 /*
 216                  * Add vars used in the join clause to targetlists of member relations,
 217                  * so that they will be emitted by the plan nodes that scan those
 218                  * relations (else they won't be available at the join node!).
 219                  */
 220                 add_vars_to_targetlist(root, vars);
 221         }
 222
 223         /*
 224          * If the clause has a mergejoinable operator, then the two sides
 225          * represent equivalent PathKeyItems for path keys: any path that is
 226          * sorted by one side will also be sorted by the other (after joining,
 227          * that is).  Record the key equivalence for future use.
 228          */
 229         if (restrictinfo->mergejoinoperator != InvalidOid)
 230                 add_equijoined_keys(root, restrictinfo);
 231 }
 232
 233 /*
 234  * add_join_info_to_rels
 235  *        For every relation participating in a join clause, add 'restrictinfo' to
 236  *        the appropriate joininfo list (creating a new list and adding it to the
 237  *        appropriate rel node if necessary).
 238  *
 239  * 'restrictinfo' describes the join clause
 240  * 'join_relids' is the list of relations participating in the join clause
 241  */
 242 static void
 243 add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 244                                           Relids join_relids)
 245 {
 246         List       *join_relid;
 247
 248         /* For every relid, find the joininfo, and add the proper join entries */
 249         foreach(join_relid, join_relids)
 250         {
 251                 int                     cur_relid = lfirsti(join_relid);
 252                 Relids          unjoined_relids = NIL;
 253                 JoinInfo   *joininfo;
 254                 List       *otherrel;
 255
 256                 /* Get the relids not equal to the current relid */
 257                 foreach(otherrel, join_relids)
 258                 {
 259                         if (lfirsti(otherrel) != cur_relid)
 260                                 unjoined_relids = lappendi(unjoined_relids, lfirsti(otherrel));
 261                 }
 262
 263                 /*
 264                  * Find or make the joininfo node for this combination of rels,
 265                  * and add the restrictinfo node to it.
 266                  */
 267                 joininfo = find_joininfo_node(get_base_rel(root, cur_relid),
 268                                                                           unjoined_relids);
 269                 joininfo->jinfo_restrictinfo = lcons(restrictinfo,
 270                                                                                          joininfo->jinfo_restrictinfo);
 271         }
 272 }
 273
 274 /*****************************************************************************
 275  *
 276  *       CHECKS FOR MERGEJOINABLE AND HASHJOINABLE CLAUSES
 277  *
 278  *****************************************************************************/
 279
 280 /*
 281  * check_mergejoinable
 282  *        If the restrictinfo's clause is mergejoinable, set the mergejoin
 283  *        info fields in the restrictinfo.
 284  *
 285  *        Currently, we support mergejoin for binary opclauses where
 286  *        both operands are simple Vars and the operator is a mergejoinable
 287  *        operator.
 288  */
 289 static void
 290 check_mergejoinable(RestrictInfo *restrictinfo)
 291 {
 292         Expr       *clause = restrictinfo->clause;
 293         Var                *left,
 294                            *right;
 295         Oid                     opno,
 296                                 leftOp,
 297                                 rightOp;
 298
 299         if (! is_opclause((Node *) clause))
 300                 return;
 301
 302         left = get_leftop(clause);
 303         right = get_rightop(clause);
 304
 305         /* caution: is_opclause accepts more than I do, so check it */
 306         if (! right)
 307                 return;                                 /* unary opclauses need not apply */
 308         if (!IsA(left, Var) || !IsA(right, Var))
 309                 return;
 310
 311         opno = ((Oper *) clause->oper)->opno;
 312
 313         if (op_mergejoinable(opno,
 314                                                  left->vartype,
 315                                                  right->vartype,
 316                                                  &leftOp,
 317                                                  &rightOp))
 318         {
 319                 restrictinfo->mergejoinoperator = opno;
 320                 restrictinfo->left_sortop = leftOp;
 321                 restrictinfo->right_sortop = rightOp;
 322         }
 323 }
 324
 325 /*
 326  * check_hashjoinable
 327  *        If the restrictinfo's clause is hashjoinable, set the hashjoin
 328  *        info fields in the restrictinfo.
 329  *
 330  *        Currently, we support hashjoin for binary opclauses where
 331  *        both operands are simple Vars and the operator is a hashjoinable
 332  *        operator.
 333  */
 334 static void
 335 check_hashjoinable(RestrictInfo *restrictinfo)
 336 {
 337         Expr       *clause = restrictinfo->clause;
 338         Var                *left,
 339                            *right;
 340         Oid                     opno;
 341
 342         if (! is_opclause((Node *) clause))
 343                 return;
 344
 345         left = get_leftop(clause);
 346         right = get_rightop(clause);
 347
 348         /* caution: is_opclause accepts more than I do, so check it */
 349         if (! right)
 350                 return;                                 /* unary opclauses need not apply */
 351         if (!IsA(left, Var) || !IsA(right, Var))
 352                 return;
 353
 354         opno = ((Oper *) clause->oper)->opno;
 355
 356         if (op_hashjoinable(opno,
 357                                                 left->vartype,
 358                                                 right->vartype))
 359         {
 360                 restrictinfo->hashjoinoperator = opno;
 361         }
 362 }