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.32 1999/07/15 15:19:22 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
  30 #include "optimizer/internal.h"
  31 #include "optimizer/planmain.h"
  32 #include "optimizer/joininfo.h"
  33 #include "optimizer/pathnode.h"
  34 #include "optimizer/tlist.h"
  35 #include "optimizer/var.h"
  36 #include "optimizer/clauses.h"
  37 #include "optimizer/cost.h"
  38
  39 extern int      Quiet;
  40
  41 static void add_restrict_and_join_to_rel(Query *root, List *clause);
  42 static void add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
  43                                           Relids join_relids);
  44 static void add_vars_to_targetlist(Query *root, List *vars, Relids join_relids);
  45
  46 static MergeOrder *mergejoinop(Expr *clause);
  47 static Oid      hashjoinop(Expr *clause);
  48
  49
  50 /*****************************************************************************
  51  *
  52  *       TARGET LISTS
  53  *
  54  *****************************************************************************/
  55
  56 /*
  57  * make_var_only_tlist
  58  *        Creates rel nodes for every relation mentioned in the target list
  59  *        'tlist' (if a node hasn't already been created) and adds them to
  60  *        *query_relation_list*.  Creates targetlist entries for each member of
  61  *        'tlist' and adds them to the tlist field of the appropriate rel node.
  62  */
  63 void
  64 make_var_only_tlist(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 = nconc(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 = (Var *) lfirst(tvar);
  81                 Index           varno;
  82                 RelOptInfo *result;
  83
  84                 varno = var->varno;
  85                 result = get_base_rel(root, varno);
  86
  87                 add_var_to_tlist(result, var);
  88         }
  89 }
  90
  91 /*
  92  * add_missing_vars_to_tlist
  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_tlist(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                 Relids          relids;
 110                 RelOptInfo *result;
 111                 Var                *var;
 112
 113                 relids = lconsi(varno, NIL);
 114                 if (rte->inFromCl && !rel_member(relids, root->base_rel_list))
 115                 {
 116                         var = makeVar(varno, ObjectIdAttributeNumber,
 117                                                   OIDOID, -1, 0, varno, ObjectIdAttributeNumber);
 118                         /* add it to base_rel_list */
 119                         result = get_base_rel(root, varno);
 120                         add_var_to_tlist(result, var);
 121                 }
 122                 pfree(relids);
 123                 varno++;
 124         }
 125
 126         return;
 127 }
 128
 129 /*****************************************************************************
 130  *
 131  *        QUALIFICATIONS
 132  *
 133  *****************************************************************************/
 134
 135
 136
 137 /*
 138  * add_restrict_and_join_to_rels-
 139  *        Initializes RestrictInfo and JoinInfo fields of relation entries for all
 140  *        relations appearing within clauses.  Creates new relation entries if
 141  *        necessary, adding them to *query_relation_list*.
 142  *
 143  *        Returns nothing of interest.
 144  */
 145 void
 146 add_restrict_and_join_to_rels(Query *root, List *clauses)
 147 {
 148         List       *clause;
 149
 150         foreach(clause, clauses)
 151                 add_restrict_and_join_to_rel(root, lfirst(clause));
 152         return;
 153 }
 154
 155 /*
 156  * add_restrict_and_join_to_rel-
 157  *        Add clause information to either the 'RestrictInfo' or 'JoinInfo' field
 158  *        of a relation entry(depending on whether or not the clause is a join)
 159  *        by creating a new RestrictInfo node and setting appropriate fields
 160  *        within the nodes.
 161  *
 162  *        Returns nothing of interest.
 163  */
 164 static void
 165 add_restrict_and_join_to_rel(Query *root, List *clause)
 166 {
 167         Relids          relids;
 168         List       *vars;
 169         RestrictInfo *restrictinfo = makeNode(RestrictInfo);
 170
 171         /*
 172          * Retrieve all relids and vars contained within the clause.
 173          */
 174         clause_get_relids_vars((Node *) clause, &relids, &vars);
 175
 176         restrictinfo->clause = (Expr *) clause;
 177         restrictinfo->notclause = contains_not((Node *) clause);
 178         restrictinfo->selectivity = 0;
 179         restrictinfo->indexids = NIL;
 180         restrictinfo->mergejoinorder = (MergeOrder *) NULL;
 181         restrictinfo->hashjoinoperator = (Oid) 0;
 182
 183         if (length(relids) == 1)
 184         {
 185
 186                 /*
 187                  * There is only one relation participating in 'clause', so
 188                  * 'clause' must be a restriction clause.
 189                  */
 190                 RelOptInfo *rel = get_base_rel(root, lfirsti(relids));
 191
 192                 /*
 193                  * The selectivity of the clause must be computed regardless of
 194                  * whether it's a restriction or a join clause
 195                  */
 196                 if (is_funcclause((Node *) clause))
 197
 198                         /*
 199                          * XXX If we have a func clause set selectivity to 1/3, really
 200                          * need a true selectivity function.
 201                          */
 202                         restrictinfo->selectivity = (Cost) 0.3333333;
 203                 else
 204                         restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
 205
 206                 rel->restrictinfo = lcons(restrictinfo, rel->restrictinfo);
 207         }
 208         else
 209         {
 210
 211                 /*
 212                  * 'clause' is a join clause, since there is more than one atom in
 213                  * the relid list.
 214                  */
 215                 if (is_funcclause((Node *) clause))
 216
 217                         /*
 218                          * XXX If we have a func clause set selectivity to 1/3, really
 219                          * need a true selectivity function.
 220                          */
 221                         restrictinfo->selectivity = (Cost) 0.3333333;
 222                 else
 223                         restrictinfo->selectivity = compute_clause_selec(root, (Node *) clause, NIL);
 224
 225                 add_join_info_to_rels(root, restrictinfo, relids);
 226                 /* we are going to be doing a join, so add var to targetlist */
 227                 add_vars_to_targetlist(root, vars, relids);
 228         }
 229 }
 230
 231 /*
 232  * add_join_info_to_rels
 233  *        For every relation participating in a join clause, add 'restrictinfo' to
 234  *        the appropriate joininfo node(creating a new one and adding it to the
 235  *        appropriate rel node if necessary).
 236  *
 237  * 'restrictinfo' describes the join clause
 238  * 'join_relids' is the list of relations participating in the join clause
 239  *
 240  */
 241 static void
 242 add_join_info_to_rels(Query *root, RestrictInfo *restrictinfo,
 243                                           Relids join_relids)
 244 {
 245         List       *join_relid;
 246
 247         /* For every relid, find the rel, and add the proper join entries */
 248         foreach(join_relid, join_relids)
 249         {
 250                 JoinInfo   *joininfo;
 251                 Relids          unjoined_relids = NIL;
 252                 List       *rel;
 253
 254                 /* Get the relids not equal to the current relid */
 255                 foreach(rel, join_relids)
 256                 {
 257                         if (lfirsti(rel) != lfirsti(join_relid))
 258                                 unjoined_relids = lappendi(unjoined_relids, lfirsti(rel));
 259                 }
 260
 261                 joininfo = find_joininfo_node(get_base_rel(root, lfirsti(join_relid)),
 262                                                                           unjoined_relids);
 263                 joininfo->jinfo_restrictinfo = lcons(copyObject((void *) restrictinfo),
 264                                                                                    joininfo->jinfo_restrictinfo);
 265         }
 266 }
 267
 268 /*
 269  * add_vars_to_targetlist
 270  *        For each variable appearing in a clause,
 271  *        (1) If a targetlist entry for the variable is not already present in
 272  *                the appropriate relation's target list, add one.
 273  *        (2) If a targetlist entry is already present, but the var is part of a
 274  *                join clause, add the relids of the join relations to the JoinList
 275  *                entry of the targetlist entry.
 276  *
 277  *        'vars' is the list of var nodes
 278  *        'join_relids' is the list of relids appearing in the join clause
 279  *              (if this is a join clause)
 280  *
 281  *        Returns nothing.
 282  */
 283 static void
 284 add_vars_to_targetlist(Query *root, List *vars, Relids join_relids)
 285 {
 286         Var                *var;
 287         List       *temp = NIL;
 288         RelOptInfo *rel = (RelOptInfo *) NULL;
 289         TargetEntry *tlistentry;
 290
 291         foreach(temp, vars)
 292         {
 293                 var = (Var *) lfirst(temp);
 294                 rel = get_base_rel(root, var->varno);
 295                 tlistentry = tlistentry_member(var, rel->targetlist);
 296                 if (tlistentry == NULL)
 297                         /* add a new entry */
 298                         add_var_to_tlist(rel, var);
 299         }
 300 }
 301
 302 /*****************************************************************************
 303  *
 304  *       JOININFO
 305  *
 306  *****************************************************************************/
 307
 308 /*
 309  * set_joininfo_mergeable_hashable
 310  *        Set the MergeJoinable or HashJoinable field for every joininfo node
 311  *        (within a rel node) and the mergejoinorder or hashjoinop field for
 312  *        each restrictinfo node(within a joininfo node) for all relations in a
 313  *        query.
 314  *
 315  *        Returns nothing.
 316  */
 317 void
 318 set_joininfo_mergeable_hashable(List *rel_list)
 319 {
 320         List       *x,
 321                            *y,
 322                            *z;
 323         RelOptInfo *rel;
 324         JoinInfo   *joininfo;
 325         RestrictInfo *restrictinfo;
 326         Expr       *clause;
 327
 328         foreach(x, rel_list)
 329         {
 330                 rel = (RelOptInfo *) lfirst(x);
 331                 foreach(y, rel->joininfo)
 332                 {
 333                         joininfo = (JoinInfo *) lfirst(y);
 334                         foreach(z, joininfo->jinfo_restrictinfo)
 335                         {
 336                                 restrictinfo = (RestrictInfo *) lfirst(z);
 337                                 clause = restrictinfo->clause;
 338                                 if (is_joinable((Node *) clause))
 339                                 {
 340                                         MergeOrder *sortop = (MergeOrder *) NULL;
 341                                         Oid                     hashop = (Oid) NULL;
 342
 343                                         if (_enable_mergejoin_)
 344                                                 sortop = mergejoinop(clause);
 345                                         if (sortop)
 346                                         {
 347                                                 restrictinfo->mergejoinorder = sortop;
 348                                                 joininfo->mergejoinable = true;
 349                                         }
 350
 351                                         if (_enable_hashjoin_)
 352                                                 hashop = hashjoinop(clause);
 353                                         if (hashop)
 354                                         {
 355                                                 restrictinfo->hashjoinoperator = hashop;
 356                                                 joininfo->hashjoinable = true;
 357                                         }
 358                                 }
 359                         }
 360                 }
 361         }
 362 }
 363
 364 /*
 365  * mergejoinop
 366  *        Returns the mergejoin operator of an operator iff 'clause' is
 367  *        mergejoinable, i.e., both operands are single vars and the operator is
 368  *        a mergejoinable operator.
 369  */
 370 static MergeOrder *
 371 mergejoinop(Expr *clause)
 372 {
 373         Var                *left,
 374                            *right;
 375         Oid                     opno,
 376                                 leftOp,
 377                                 rightOp;
 378         bool            sortable;
 379
 380         if (!is_opclause((Node *) clause))
 381                 return NULL;
 382
 383         left = get_leftop(clause);
 384         right = get_rightop(clause);
 385
 386         /* caution: is_opclause accepts more than I do, so check it */
 387         if (!right)
 388                 return NULL;                    /* unary opclauses need not apply */
 389         if (!IsA(left, Var) ||!IsA(right, Var))
 390                 return NULL;
 391
 392         opno = ((Oper *) clause->oper)->opno;
 393
 394         sortable = op_mergejoinable(opno,
 395                                                                 left->vartype,
 396                                                                 right->vartype,
 397                                                                 &leftOp,
 398                                                                 &rightOp);
 399
 400         if (sortable)
 401         {
 402                 MergeOrder *morder = makeNode(MergeOrder);
 403
 404                 morder->join_operator = opno;
 405                 morder->left_operator = leftOp;
 406                 morder->right_operator = rightOp;
 407                 morder->left_type = left->vartype;
 408                 morder->right_type = right->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         Var                *left,
 425                            *right;
 426
 427         if (!is_opclause((Node *) clause))
 428                 return InvalidOid;
 429
 430         left = get_leftop(clause);
 431         right = get_rightop(clause);
 432
 433         /* caution: is_opclause accepts more than I do, so check it */
 434         if (!right)
 435                 return InvalidOid;              /* unary opclauses need not apply */
 436         if (!IsA(left, Var) ||!IsA(right, Var))
 437                 return InvalidOid;
 438
 439         return op_hashjoinable(((Oper *) clause->oper)->opno,
 440                                                    left->vartype,
 441                                                    right->vartype);
 442 }