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