granicus.if.org Git - postgresql/blob - src/backend/optimizer/path/allpaths.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * allpaths.c--
   4  *        Routines to find possible search paths for processing a query
   5  *
   6  * Copyright (c) 1994, Regents of the University of California
   7  *
   8  *
   9  * IDENTIFICATION
  10  *        $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.18 1998/08/04 00:42:07 momjian Exp $
  11  *
  12  *-------------------------------------------------------------------------
  13  */
  14 #include <string.h>
  15 #include <stdio.h>
  16
  17 #include "postgres.h"
  18
  19 #include "nodes/pg_list.h"
  20 #include "nodes/relation.h"
  21 #include "nodes/primnodes.h"
  22
  23 #include "optimizer/internal.h"
  24
  25 #include "optimizer/paths.h"
  26 #include "optimizer/pathnode.h"
  27 #include "optimizer/clauses.h"
  28 #include "optimizer/xfunc.h"
  29 #include "optimizer/cost.h"
  30
  31 #include "commands/creatinh.h"
  32
  33 #include "optimizer/geqo_gene.h"
  34 #include "optimizer/geqo.h"
  35
  36 #ifdef GEQO
  37 bool            _use_geqo_ = true;
  38
  39 #else
  40 bool            _use_geqo_ = false;
  41
  42 #endif
  43 int32           _use_geqo_rels_ = GEQO_RELS;
  44
  45
  46 static void find_rel_paths(Query *root, List *rels);
  47 static List *find_join_paths(Query *root, List *outer_rels, int levels_needed);
  48
  49 /*
  50  * find-paths--
  51  *        Finds all possible access paths for executing a query, returning the
  52  *        top level list of relation entries.
  53  *
  54  * 'rels' is the list of single relation entries appearing in the query
  55  */
  56 List *
  57 find_paths(Query *root, List *rels)
  58 {
  59         int                     levels_needed;
  60
  61         /*
  62          * Set the number of join (not nesting) levels yet to be processed.
  63          */
  64         levels_needed = length(rels);
  65
  66         if (levels_needed <= 0)
  67                 return NIL;
  68
  69         /*
  70          * Find the base relation paths.
  71          */
  72         find_rel_paths(root, rels);
  73
  74         if (levels_needed <= 1)
  75         {
  76
  77                 /*
  78                  * Unsorted single relation, no more processing is required.
  79                  */
  80                 return rels;
  81         }
  82         else
  83         {
  84
  85                 /*
  86                  * this means that joins or sorts are required. set selectivities
  87                  * of clauses that have not been set by an index.
  88                  */
  89                 set_rest_relselec(root, rels);
  90
  91                 return find_join_paths(root, rels, levels_needed);
  92         }
  93 }
  94
  95 /*
  96  * find-rel-paths--
  97  *        Finds all paths available for scanning each relation entry in
  98  *        'rels'.  Sequential scan and any available indices are considered
  99  *        if possible(indices are not considered for lower nesting levels).
 100  *        All unique paths are attached to the relation's 'pathlist' field.
 101  *
 102  *        MODIFIES: rels
 103  */
 104 static void
 105 find_rel_paths(Query *root, List *rels)
 106 {
 107         List       *temp;
 108         List       *lastpath;
 109
 110         foreach(temp, rels)
 111         {
 112                 List       *sequential_scan_list;
 113                 List       *rel_index_scan_list;
 114                 List       *or_index_scan_list;
 115                 RelOptInfo *rel = (RelOptInfo *) lfirst(temp);
 116
 117                 sequential_scan_list = lcons(create_seqscan_path(rel),
 118                                                                          NIL);
 119
 120                 rel_index_scan_list =
 121                         find_index_paths(root,
 122                                                          rel,
 123                                                          find_relation_indices(root, rel),
 124                                                          rel->clauseinfo,
 125                                                          rel->joininfo);
 126
 127                 or_index_scan_list = create_or_index_paths(root, rel, rel->clauseinfo);
 128
 129                 rel->pathlist = add_pathlist(rel,
 130                                                                          sequential_scan_list,
 131                                                                          append(rel_index_scan_list,
 132                                                                                         or_index_scan_list));
 133
 134                 /*
 135                  * The unordered path is always the last in the list. If it is not
 136                  * the cheapest path, prune it.
 137                  */
 138                 lastpath = rel->pathlist;
 139                 while (lnext(lastpath) != NIL)
 140                         lastpath = lnext(lastpath);
 141                 prune_rel_path(rel, (Path *) lfirst(lastpath));
 142
 143                 /*
 144                  * if there is a qualification of sequential scan the selec. value
 145                  * is not set -- so set it explicitly -- Sunita
 146                  */
 147                 set_rest_selec(root, rel->clauseinfo);
 148                 rel->size = compute_rel_size(rel);
 149                 rel->width = compute_rel_width(rel);
 150         }
 151         return;
 152 }
 153
 154 /*
 155  * find-join-paths--
 156  *        Find all possible joinpaths for a query by successively finding ways
 157  *        to join single relations into join relations.
 158  *
 159  *        if BushyPlanFlag is set, bushy tree plans will be generated:
 160  *        Find all possible joinpaths(bushy trees) for a query by systematically
 161  *        finding ways to join relations(both original and derived) together.
 162  *
 163  * 'outer-rels' is the current list of relations for which join paths
 164  *                              are to be found, i.e., he current list of relations that
 165  *                              have already been derived.
 166  * 'levels-needed' is the number of iterations needed
 167  *
 168  * Returns the final level of join relations, i.e., the relation that is
 169  * the result of joining all the original relations together.
 170  */
 171 static List *
 172 find_join_paths(Query *root, List *outer_rels, int levels_needed)
 173 {
 174         List       *x;
 175         List       *new_rels = NIL;
 176         RelOptInfo                 *rel;
 177
 178         /*******************************************
 179          * genetic query optimizer entry point     *
 180          *        <utesch@aut.tu-freiberg.de>              *
 181          *******************************************/
 182
 183         if ((_use_geqo_) && length(root->base_relation_list_) >= _use_geqo_rels_)
 184                 return lcons(geqo(root), NIL);  /* returns *one* RelOptInfo, so lcons it */
 185
 186         /*******************************************
 187          * rest will be deprecated in case of GEQO *
 188          *******************************************/
 189
 190         while (--levels_needed)
 191         {
 192
 193                 /*
 194                  * Determine all possible pairs of relations to be joined at this
 195                  * level. Determine paths for joining these relation pairs and
 196                  * modify 'new-rels' accordingly, then eliminate redundant join
 197                  * relations.
 198                  */
 199                 new_rels = find_join_rels(root, outer_rels);
 200
 201                 find_all_join_paths(root, new_rels);
 202
 203                 prune_joinrels(new_rels);
 204
 205 #if 0
 206
 207                 /*
 208                  * * for each expensive predicate in each path in each distinct
 209                  * rel, * consider doing pullup  -- JMH
 210                  */
 211                 if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
 212                         foreach(x, new_rels)
 213                                 xfunc_trypullup((RelOptInfo *) lfirst(x));
 214 #endif
 215
 216                 prune_rel_paths(new_rels);
 217
 218                 if (BushyPlanFlag)
 219                 {
 220
 221                         /*
 222                          * In case of bushy trees if there is still a join between a
 223                          * join relation and another relation, add a new joininfo that
 224                          * involves the join relation to the joininfo list of the
 225                          * other relation
 226                          */
 227                         add_new_joininfos(root, new_rels, outer_rels);
 228                 }
 229
 230                 foreach(x, new_rels)
 231                 {
 232                         rel = (RelOptInfo *) lfirst(x);
 233                         if (rel->size <= 0)
 234                                 rel->size = compute_rel_size(rel);
 235                         rel->width = compute_rel_width(rel);
 236
 237                         /* #define OPTIMIZER_DEBUG */
 238 #ifdef OPTIMIZER_DEBUG
 239                         printf("levels left: %d\n", levels_left);
 240                         debug_print_rel(root, rel);
 241 #endif
 242                 }
 243
 244                 if (BushyPlanFlag)
 245                 {
 246
 247                         /*
 248                          * prune rels that have been completely incorporated into new
 249                          * join rels
 250                          */
 251                         outer_rels = prune_oldrels(outer_rels);
 252
 253                         /*
 254                          * merge join rels if then contain the same list of base rels
 255                          */
 256                         outer_rels = merge_joinrels(new_rels, outer_rels);
 257                         root->join_relation_list_ = outer_rels;
 258                 }
 259                 else
 260                         root->join_relation_list_ = new_rels;
 261                 if (!BushyPlanFlag)
 262                         outer_rels = new_rels;
 263         }
 264
 265         if (BushyPlanFlag)
 266                 return final_join_rels(outer_rels);
 267         else
 268                 return new_rels;
 269 }
 270
 271 /*****************************************************************************
 272  *
 273  *****************************************************************************/
 274
 275 #ifdef OPTIMIZER_DEBUG
 276 static void
 277 print_joinclauses(Query *root, List *clauses)
 278 {
 279         List       *l;
 280         extern void print_expr(Node *expr, List *rtable);       /* in print.c */
 281
 282         foreach(l, clauses)
 283         {
 284                 CInfo      *c = lfirst(l);
 285
 286                 print_expr((Node *) c->clause, root->rtable);
 287                 if (lnext(l))
 288                         printf(" ");
 289         }
 290 }
 291
 292 static void
 293 print_path(Query *root, Path *path, int indent)
 294 {
 295         char       *ptype = NULL;
 296         JoinPath   *jp;
 297         bool            join = false;
 298         int                     i;
 299
 300         for (i = 0; i < indent; i++)
 301                 printf("\t");
 302
 303         switch (nodeTag(path))
 304         {
 305                 case T_Path:
 306                         ptype = "SeqScan";
 307                         join = false;
 308                         break;
 309                 case T_IndexPath:
 310                         ptype = "IdxScan";
 311                         join = false;
 312                         break;
 313                 case T_JoinPath:
 314                         ptype = "Nestloop";
 315                         join = true;
 316                         break;
 317                 case T_MergePath:
 318                         ptype = "MergeJoin";
 319                         join = true;
 320                         break;
 321                 case T_HashPath:
 322                         ptype = "HashJoin";
 323                         join = true;
 324                         break;
 325                 default:
 326                         break;
 327         }
 328         if (join)
 329         {
 330                 int                     size = path->parent->size;
 331
 332                 jp = (JoinPath *) path;
 333                 printf("%s size=%d cost=%f\n", ptype, size, path->path_cost);
 334                 switch (nodeTag(path))
 335                 {
 336                         case T_MergePath:
 337                         case T_HashPath:
 338                                 for (i = 0; i < indent + 1; i++)
 339                                         printf("\t");
 340                                 printf("   clauses=(");
 341                                 print_joinclauses(root,
 342                                                                   ((JoinPath *) path)->pathclauseinfo);
 343                                 printf(")\n");
 344
 345                                 if (nodeTag(path) == T_MergePath)
 346                                 {
 347                                         MergePath  *mp = (MergePath *) path;
 348
 349                                         if (mp->outersortkeys || mp->innersortkeys)
 350                                         {
 351                                                 for (i = 0; i < indent + 1; i++)
 352                                                         printf("\t");
 353                                                 printf("   sortouter=%d sortinner=%d\n",
 354                                                            ((mp->outersortkeys) ? 1 : 0),
 355                                                            ((mp->innersortkeys) ? 1 : 0));
 356                                         }
 357                                 }
 358                                 break;
 359                         default:
 360                                 break;
 361                 }
 362                 print_path(root, jp->outerjoinpath, indent + 1);
 363                 print_path(root, jp->innerjoinpath, indent + 1);
 364         }
 365         else
 366         {
 367                 int                     size = path->parent->size;
 368                 int                     relid = lfirsti(path->parent->relids);
 369
 370                 printf("%s(%d) size=%d cost=%f",
 371                            ptype, relid, size, path->path_cost);
 372
 373                 if (nodeTag(path) == T_IndexPath)
 374                 {
 375                         List       *k,
 376                                            *l;
 377
 378                         printf(" keys=");
 379                         foreach(k, path->keys)
 380                         {
 381                                 printf("(");
 382                                 foreach(l, lfirst(k))
 383                                 {
 384                                         Var                *var = lfirst(l);
 385
 386                                         printf("%d.%d", var->varnoold, var->varoattno);
 387                                         if (lnext(l))
 388                                                 printf(", ");
 389                                 }
 390                                 printf(")");
 391                                 if (lnext(k))
 392                                         printf(", ");
 393                         }
 394                 }
 395                 printf("\n");
 396         }
 397 }
 398
 399 static void
 400 debug_print_rel(Query *root, RelOptInfo *rel)
 401 {
 402         List       *l;
 403
 404         printf("(");
 405         foreach(l, rel->relids)
 406                 printf("%d ", lfirsti(l));
 407         printf("): size=%d width=%d\n", rel->size, rel->width);
 408
 409         printf("\tpath list:\n");
 410         foreach(l, rel->pathlist)
 411                 print_path(root, lfirst(l), 1);
 412         printf("\tcheapest path:\n");
 413         print_path(root, rel->cheapestpath, 1);
 414 }
 415
 416 #endif                                                  /* OPTIMIZER_DEBUG */