LCOV - code coverage report
Current view: top level - src/backend/optimizer/geqo - geqo_eval.c (source / functions) Hit Total Coverage
Test: PostgreSQL 13devel Lines: 57 64 89.1 %
Date: 2019-11-21 15:06:52 Functions: 4 4 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*------------------------------------------------------------------------
       2             :  *
       3             :  * geqo_eval.c
       4             :  *    Routines to evaluate query trees
       5             :  *
       6             :  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
       7             :  * Portions Copyright (c) 1994, Regents of the University of California
       8             :  *
       9             :  * src/backend/optimizer/geqo/geqo_eval.c
      10             :  *
      11             :  *-------------------------------------------------------------------------
      12             :  */
      13             : 
      14             : /* contributed by:
      15             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      16             :    *  Martin Utesch              * Institute of Automatic Control      *
      17             :    =                             = University of Mining and Technology =
      18             :    *  utesch@aut.tu-freiberg.de  * Freiberg, Germany                   *
      19             :    =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=
      20             :  */
      21             : 
      22             : #include "postgres.h"
      23             : 
      24             : #include <float.h>
      25             : #include <limits.h>
      26             : #include <math.h>
      27             : 
      28             : #include "optimizer/geqo.h"
      29             : #include "optimizer/joininfo.h"
      30             : #include "optimizer/pathnode.h"
      31             : #include "optimizer/paths.h"
      32             : #include "utils/memutils.h"
      33             : 
      34             : 
      35             : /* A "clump" of already-joined relations within gimme_tree */
      36             : typedef struct
      37             : {
      38             :     RelOptInfo *joinrel;        /* joinrel for the set of relations */
      39             :     int         size;           /* number of input relations in clump */
      40             : } Clump;
      41             : 
      42             : static List *merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump,
      43             :                          int num_gene, bool force);
      44             : static bool desirable_join(PlannerInfo *root,
      45             :                            RelOptInfo *outer_rel, RelOptInfo *inner_rel);
      46             : 
      47             : 
      48             : /*
      49             :  * geqo_eval
      50             :  *
      51             :  * Returns cost of a query tree as an individual of the population.
      52             :  *
      53             :  * If no legal join order can be extracted from the proposed tour,
      54             :  * returns DBL_MAX.
      55             :  */
      56             : Cost
      57         512 : geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)
      58             : {
      59             :     MemoryContext mycontext;
      60             :     MemoryContext oldcxt;
      61             :     RelOptInfo *joinrel;
      62             :     Cost        fitness;
      63             :     int         savelength;
      64             :     struct HTAB *savehash;
      65             : 
      66             :     /*
      67             :      * Create a private memory context that will hold all temp storage
      68             :      * allocated inside gimme_tree().
      69             :      *
      70             :      * Since geqo_eval() will be called many times, we can't afford to let all
      71             :      * that memory go unreclaimed until end of statement.  Note we make the
      72             :      * temp context a child of the planner's normal context, so that it will
      73             :      * be freed even if we abort via ereport(ERROR).
      74             :      */
      75         512 :     mycontext = AllocSetContextCreate(CurrentMemoryContext,
      76             :                                       "GEQO",
      77             :                                       ALLOCSET_DEFAULT_SIZES);
      78         512 :     oldcxt = MemoryContextSwitchTo(mycontext);
      79             : 
      80             :     /*
      81             :      * gimme_tree will add entries to root->join_rel_list, which may or may
      82             :      * not already contain some entries.  The newly added entries will be
      83             :      * recycled by the MemoryContextDelete below, so we must ensure that the
      84             :      * list is restored to its former state before exiting.  We can do this by
      85             :      * truncating the list to its original length.  NOTE this assumes that any
      86             :      * added entries are appended at the end!
      87             :      *
      88             :      * We also must take care not to mess up the outer join_rel_hash, if there
      89             :      * is one.  We can do this by just temporarily setting the link to NULL.
      90             :      * (If we are dealing with enough join rels, which we very likely are, a
      91             :      * new hash table will get built and used locally.)
      92             :      *
      93             :      * join_rel_level[] shouldn't be in use, so just Assert it isn't.
      94             :      */
      95         512 :     savelength = list_length(root->join_rel_list);
      96         512 :     savehash = root->join_rel_hash;
      97             :     Assert(root->join_rel_level == NULL);
      98             : 
      99         512 :     root->join_rel_hash = NULL;
     100             : 
     101             :     /* construct the best path for the given combination of relations */
     102         512 :     joinrel = gimme_tree(root, tour, num_gene);
     103             : 
     104             :     /*
     105             :      * compute fitness, if we found a valid join
     106             :      *
     107             :      * XXX geqo does not currently support optimization for partial result
     108             :      * retrieval, nor do we take any cognizance of possible use of
     109             :      * parameterized paths --- how to fix?
     110             :      */
     111         512 :     if (joinrel)
     112             :     {
     113         512 :         Path       *best_path = joinrel->cheapest_total_path;
     114             : 
     115         512 :         fitness = best_path->total_cost;
     116             :     }
     117             :     else
     118           0 :         fitness = DBL_MAX;
     119             : 
     120             :     /*
     121             :      * Restore join_rel_list to its former state, and put back original
     122             :      * hashtable if any.
     123             :      */
     124         512 :     root->join_rel_list = list_truncate(root->join_rel_list,
     125             :                                         savelength);
     126         512 :     root->join_rel_hash = savehash;
     127             : 
     128             :     /* release all the memory acquired within gimme_tree */
     129         512 :     MemoryContextSwitchTo(oldcxt);
     130         512 :     MemoryContextDelete(mycontext);
     131             : 
     132         512 :     return fitness;
     133             : }
     134             : 
     135             : /*
     136             :  * gimme_tree
     137             :  *    Form planner estimates for a join tree constructed in the specified
     138             :  *    order.
     139             :  *
     140             :  *   'tour' is the proposed join order, of length 'num_gene'
     141             :  *
     142             :  * Returns a new join relation whose cheapest path is the best plan for
     143             :  * this join order.  NB: will return NULL if join order is invalid and
     144             :  * we can't modify it into a valid order.
     145             :  *
     146             :  * The original implementation of this routine always joined in the specified
     147             :  * order, and so could only build left-sided plans (and right-sided and
     148             :  * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).
     149             :  * It could never produce a "bushy" plan.  This had a couple of big problems,
     150             :  * of which the worst was that there are situations involving join order
     151             :  * restrictions where the only valid plans are bushy.
     152             :  *
     153             :  * The present implementation takes the given tour as a guideline, but
     154             :  * postpones joins that are illegal or seem unsuitable according to some
     155             :  * heuristic rules.  This allows correct bushy plans to be generated at need,
     156             :  * and as a nice side-effect it seems to materially improve the quality of the
     157             :  * generated plans.  Note however that since it's just a heuristic, it can
     158             :  * still fail in some cases.  (In particular, we might clump together
     159             :  * relations that actually mustn't be joined yet due to LATERAL restrictions;
     160             :  * since there's no provision for un-clumping, this must lead to failure.)
     161             :  */
     162             : RelOptInfo *
     163         516 : gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
     164             : {
     165         516 :     GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;
     166             :     List       *clumps;
     167             :     int         rel_count;
     168             : 
     169             :     /*
     170             :      * Sometimes, a relation can't yet be joined to others due to heuristics
     171             :      * or actual semantic restrictions.  We maintain a list of "clumps" of
     172             :      * successfully joined relations, with larger clumps at the front. Each
     173             :      * new relation from the tour is added to the first clump it can be joined
     174             :      * to; if there is none then it becomes a new clump of its own. When we
     175             :      * enlarge an existing clump we check to see if it can now be merged with
     176             :      * any other clumps.  After the tour is all scanned, we forget about the
     177             :      * heuristics and try to forcibly join any remaining clumps.  If we are
     178             :      * unable to merge all the clumps into one, fail.
     179             :      */
     180         516 :     clumps = NIL;
     181             : 
     182        3096 :     for (rel_count = 0; rel_count < num_gene; rel_count++)
     183             :     {
     184             :         int         cur_rel_index;
     185             :         RelOptInfo *cur_rel;
     186             :         Clump      *cur_clump;
     187             : 
     188             :         /* Get the next input relation */
     189        2580 :         cur_rel_index = (int) tour[rel_count];
     190        2580 :         cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
     191             :                                           cur_rel_index - 1);
     192             : 
     193             :         /* Make it into a single-rel clump */
     194        2580 :         cur_clump = (Clump *) palloc(sizeof(Clump));
     195        2580 :         cur_clump->joinrel = cur_rel;
     196        2580 :         cur_clump->size = 1;
     197             : 
     198             :         /* Merge it into the clumps list, using only desirable joins */
     199        2580 :         clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
     200             :     }
     201             : 
     202         516 :     if (list_length(clumps) > 1)
     203             :     {
     204             :         /* Force-join the remaining clumps in some legal order */
     205             :         List       *fclumps;
     206             :         ListCell   *lc;
     207             : 
     208           0 :         fclumps = NIL;
     209           0 :         foreach(lc, clumps)
     210             :         {
     211           0 :             Clump      *clump = (Clump *) lfirst(lc);
     212             : 
     213           0 :             fclumps = merge_clump(root, fclumps, clump, num_gene, true);
     214             :         }
     215           0 :         clumps = fclumps;
     216             :     }
     217             : 
     218             :     /* Did we succeed in forming a single join relation? */
     219         516 :     if (list_length(clumps) != 1)
     220           0 :         return NULL;
     221             : 
     222         516 :     return ((Clump *) linitial(clumps))->joinrel;
     223             : }
     224             : 
     225             : /*
     226             :  * Merge a "clump" into the list of existing clumps for gimme_tree.
     227             :  *
     228             :  * We try to merge the clump into some existing clump, and repeat if
     229             :  * successful.  When no more merging is possible, insert the clump
     230             :  * into the list, preserving the list ordering rule (namely, that
     231             :  * clumps of larger size appear earlier).
     232             :  *
     233             :  * If force is true, merge anywhere a join is legal, even if it causes
     234             :  * a cartesian join to be performed.  When force is false, do only
     235             :  * "desirable" joins.
     236             :  */
     237             : static List *
     238        4644 : merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,
     239             :             bool force)
     240             : {
     241             :     ListCell   *lc;
     242             :     int         pos;
     243             : 
     244             :     /* Look for a clump that new_clump can join to */
     245        7044 :     foreach(lc, clumps)
     246             :     {
     247        4464 :         Clump      *old_clump = (Clump *) lfirst(lc);
     248             : 
     249        8928 :         if (force ||
     250        4464 :             desirable_join(root, old_clump->joinrel, new_clump->joinrel))
     251             :         {
     252             :             RelOptInfo *joinrel;
     253             : 
     254             :             /*
     255             :              * Construct a RelOptInfo representing the join of these two input
     256             :              * relations.  Note that we expect the joinrel not to exist in
     257             :              * root->join_rel_list yet, and so the paths constructed for it
     258             :              * will only include the ones we want.
     259             :              */
     260        3232 :             joinrel = make_join_rel(root,
     261             :                                     old_clump->joinrel,
     262             :                                     new_clump->joinrel);
     263             : 
     264             :             /* Keep searching if join order is not valid */
     265        3232 :             if (joinrel)
     266             :             {
     267             :                 /* Create paths for partitionwise joins. */
     268        2064 :                 generate_partitionwise_join_paths(root, joinrel);
     269             : 
     270             :                 /*
     271             :                  * Except for the topmost scan/join rel, consider gathering
     272             :                  * partial paths.  We'll do the same for the topmost scan/join
     273             :                  * rel once we know the final targetlist (see
     274             :                  * grouping_planner).
     275             :                  */
     276        2064 :                 if (old_clump->size + new_clump->size < num_gene)
     277        1548 :                     generate_gather_paths(root, joinrel, false);
     278             : 
     279             :                 /* Find and save the cheapest paths for this joinrel */
     280        2064 :                 set_cheapest(joinrel);
     281             : 
     282             :                 /* Absorb new clump into old */
     283        2064 :                 old_clump->joinrel = joinrel;
     284        2064 :                 old_clump->size += new_clump->size;
     285        2064 :                 pfree(new_clump);
     286             : 
     287             :                 /* Remove old_clump from list */
     288        2064 :                 clumps = foreach_delete_current(clumps, lc);
     289             : 
     290             :                 /*
     291             :                  * Recursively try to merge the enlarged old_clump with
     292             :                  * others.  When no further merge is possible, we'll reinsert
     293             :                  * it into the list.
     294             :                  */
     295        2064 :                 return merge_clump(root, clumps, old_clump, num_gene, force);
     296             :             }
     297             :         }
     298             :     }
     299             : 
     300             :     /*
     301             :      * No merging is possible, so add new_clump as an independent clump, in
     302             :      * proper order according to size.  We can be fast for the common case
     303             :      * where it has size 1 --- it should always go at the end.
     304             :      */
     305        2580 :     if (clumps == NIL || new_clump->size == 1)
     306        2040 :         return lappend(clumps, new_clump);
     307             : 
     308             :     /* Else search for the place to insert it */
     309         660 :     for (pos = 0; pos < list_length(clumps); pos++)
     310             :     {
     311         540 :         Clump      *old_clump = (Clump *) list_nth(clumps, pos);
     312             : 
     313         540 :         if (new_clump->size > old_clump->size)
     314         420 :             break;              /* new_clump belongs before old_clump */
     315             :     }
     316         540 :     clumps = list_insert_nth(clumps, pos, new_clump);
     317             : 
     318         540 :     return clumps;
     319             : }
     320             : 
     321             : /*
     322             :  * Heuristics for gimme_tree: do we want to join these two relations?
     323             :  */
     324             : static bool
     325        4464 : desirable_join(PlannerInfo *root,
     326             :                RelOptInfo *outer_rel, RelOptInfo *inner_rel)
     327             : {
     328             :     /*
     329             :      * Join if there is an applicable join clause, or if there is a join order
     330             :      * restriction forcing these rels to be joined.
     331             :      */
     332        5696 :     if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
     333        1232 :         have_join_order_restriction(root, outer_rel, inner_rel))
     334        3232 :         return true;
     335             : 
     336             :     /* Otherwise postpone the join till later. */
     337        1232 :     return false;
     338             : }

Generated by: LCOV version 1.13