LCOV - differential code coverage report
Current view: top level - src/backend/optimizer/geqo - geqo_eval.c (source / functions) Coverage Total Hit UBC CBC
Current: Differential Code Coverage 16@8cea358b128 vs 17@8cea358b128 Lines: 89.2 % 65 58 7 58
Current Date: 2024-04-14 14:21:10 Functions: 100.0 % 4 4 4
Baseline: 16@8cea358b128 Branches: 71.4 % 42 30 12 30
Baseline Date: 2024-04-14 14:21:09 Line coverage date bins:
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed (240..) days: 89.2 % 65 58 7 58
Function coverage date bins:
(240..) days: 100.0 % 4 4 4
Branch coverage date bins:
(240..) days: 71.4 % 42 30 12 30

 Age         Owner                    Branch data    TLA  Line data    Source code
                                  1                 :                : /*------------------------------------------------------------------------
                                  2                 :                :  *
                                  3                 :                :  * geqo_eval.c
                                  4                 :                :  *    Routines to evaluate query trees
                                  5                 :                :  *
                                  6                 :                :  * Portions Copyright (c) 1996-2024, 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
 5386 tgl@sss.pgh.pa.us          57                 :CBC         384 : 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                 :                :      */
 7653                            75                 :            384 :     mycontext = AllocSetContextCreate(CurrentMemoryContext,
                                 76                 :                :                                       "GEQO",
                                 77                 :                :                                       ALLOCSET_DEFAULT_SIZES);
 8691                            78                 :            384 :     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                 :                :      */
 5386                            95                 :            384 :     savelength = list_length(root->join_rel_list);
                                 96                 :            384 :     savehash = root->join_rel_hash;
 5251                            97         [ -  + ]:            384 :     Assert(root->join_rel_level == NULL);
                                 98                 :                : 
 5386                            99                 :            384 :     root->join_rel_hash = NULL;
                                100                 :                : 
                                101                 :                :     /* construct the best path for the given combination of relations */
                                102                 :            384 :     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                 :                :      */
 3351                           111         [ +  - ]:            384 :     if (joinrel)
                                112                 :                :     {
                                113                 :            384 :         Path       *best_path = joinrel->cheapest_total_path;
                                114                 :                : 
                                115                 :            384 :         fitness = best_path->total_cost;
                                116                 :                :     }
                                117                 :                :     else
 3351 tgl@sss.pgh.pa.us         118                 :UBC           0 :         fitness = DBL_MAX;
                                119                 :                : 
                                120                 :                :     /*
                                121                 :                :      * Restore join_rel_list to its former state, and put back original
                                122                 :                :      * hashtable if any.
                                123                 :                :      */
 5386 tgl@sss.pgh.pa.us         124                 :CBC         384 :     root->join_rel_list = list_truncate(root->join_rel_list,
                                125                 :                :                                         savelength);
                                126                 :            384 :     root->join_rel_hash = savehash;
                                127                 :                : 
                                128                 :                :     /* release all the memory acquired within gimme_tree */
 9099                           129                 :            384 :     MemoryContextSwitchTo(oldcxt);
 8691                           130                 :            384 :     MemoryContextDelete(mycontext);
                                131                 :                : 
 9357 bruce@momjian.us          132                 :            384 :     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 *
 5386 tgl@sss.pgh.pa.us         163                 :            387 : gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)
                                164                 :                : {
                                165                 :            387 :     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                 :                :      */
 5383                           180                 :            387 :     clumps = NIL;
                                181                 :                : 
 7387                           182         [ +  + ]:           2322 :     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 */
 7790                           189                 :           1935 :         cur_rel_index = (int) tour[rel_count];
 5383                           190                 :           1935 :         cur_rel = (RelOptInfo *) list_nth(private->initial_rels,
                                191                 :                :                                           cur_rel_index - 1);
                                192                 :                : 
                                193                 :                :         /* Make it into a single-rel clump */
                                194                 :           1935 :         cur_clump = (Clump *) palloc(sizeof(Clump));
                                195                 :           1935 :         cur_clump->joinrel = cur_rel;
                                196                 :           1935 :         cur_clump->size = 1;
                                197                 :                : 
                                198                 :                :         /* Merge it into the clumps list, using only desirable joins */
 2225 rhaas@postgresql.org      199                 :           1935 :         clumps = merge_clump(root, clumps, cur_clump, num_gene, false);
                                200                 :                :     }
                                201                 :                : 
 5383 tgl@sss.pgh.pa.us         202         [ -  + ]:            387 :     if (list_length(clumps) > 1)
                                203                 :                :     {
                                204                 :                :         /* Force-join the remaining clumps in some legal order */
                                205                 :                :         List       *fclumps;
                                206                 :                :         ListCell   *lc;
                                207                 :                : 
 5383 tgl@sss.pgh.pa.us         208                 :UBC           0 :         fclumps = NIL;
                                209   [ #  #  #  #  :              0 :         foreach(lc, clumps)
                                              #  # ]
                                210                 :                :         {
                                211                 :              0 :             Clump      *clump = (Clump *) lfirst(lc);
                                212                 :                : 
 2225 rhaas@postgresql.org      213                 :              0 :             fclumps = merge_clump(root, fclumps, clump, num_gene, true);
                                214                 :                :         }
 5383 tgl@sss.pgh.pa.us         215                 :              0 :         clumps = fclumps;
                                216                 :                :     }
                                217                 :                : 
                                218                 :                :     /* Did we succeed in forming a single join relation? */
 5383 tgl@sss.pgh.pa.us         219         [ -  + ]:CBC         387 :     if (list_length(clumps) != 1)
 3351 tgl@sss.pgh.pa.us         220                 :UBC           0 :         return NULL;
                                221                 :                : 
 5383 tgl@sss.pgh.pa.us         222                 :CBC         387 :     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 *
 2225 rhaas@postgresql.org      238                 :           3483 : 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 */
 5383 tgl@sss.pgh.pa.us         245   [ +  +  +  +  :           5451 :     foreach(lc, clumps)
                                              +  + ]
                                246                 :                :     {
                                247                 :           3516 :         Clump      *old_clump = (Clump *) lfirst(lc);
                                248                 :                : 
                                249   [ +  -  +  + ]:           7032 :         if (force ||
                                250                 :           3516 :             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                 :           2376 :             joinrel = make_join_rel(root,
                                261                 :                :                                     old_clump->joinrel,
                                262                 :                :                                     new_clump->joinrel);
                                263                 :                : 
                                264                 :                :             /* Keep searching if join order is not valid */
                                265         [ +  + ]:           2376 :             if (joinrel)
                                266                 :                :             {
                                267                 :                :                 /* Create paths for partitionwise joins. */
 2249 peter_e@gmx.net           268                 :           1548 :                 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                 :                :                  */
  440 tgl@sss.pgh.pa.us         276         [ +  + ]:           1548 :                 if (!bms_equal(joinrel->relids, root->all_query_rels))
 1468 tomas.vondra@postgre      277                 :           1161 :                     generate_useful_gather_paths(root, joinrel, false);
                                278                 :                : 
                                279                 :                :                 /* Find and save the cheapest paths for this joinrel */
 5383 tgl@sss.pgh.pa.us         280                 :           1548 :                 set_cheapest(joinrel);
                                281                 :                : 
                                282                 :                :                 /* Absorb new clump into old */
                                283                 :           1548 :                 old_clump->joinrel = joinrel;
                                284                 :           1548 :                 old_clump->size += new_clump->size;
                                285                 :           1548 :                 pfree(new_clump);
                                286                 :                : 
                                287                 :                :                 /* Remove old_clump from list */
 1735                           288                 :           1548 :                 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                 :                :                  */
 2225 rhaas@postgresql.org      295                 :           1548 :                 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                 :                :      */
 5383 tgl@sss.pgh.pa.us         305   [ +  +  +  + ]:           1935 :     if (clumps == NIL || new_clump->size == 1)
                                306                 :           1500 :         return lappend(clumps, new_clump);
                                307                 :                : 
                                308                 :                :     /* Else search for the place to insert it */
 1734                           309         [ +  + ]:            510 :     for (pos = 0; pos < list_length(clumps); pos++)
                                310                 :                :     {
                                311                 :            435 :         Clump      *old_clump = (Clump *) list_nth(clumps, pos);
                                312                 :                : 
                                313         [ +  + ]:            435 :         if (new_clump->size > old_clump->size)
                                314                 :            360 :             break;              /* new_clump belongs before old_clump */
                                315                 :                :     }
                                316                 :            435 :     clumps = list_insert_nth(clumps, pos, new_clump);
                                317                 :                : 
 5383                           318                 :            435 :     return clumps;
                                319                 :                : }
                                320                 :                : 
                                321                 :                : /*
                                322                 :                :  * Heuristics for gimme_tree: do we want to join these two relations?
                                323                 :                :  */
                                324                 :                : static bool
 6888                           325                 :           3516 : 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                 :                :      */
 6267                           332   [ +  +  -  + ]:           4656 :     if (have_relevant_joinclause(root, outer_rel, inner_rel) ||
                                333                 :           1140 :         have_join_order_restriction(root, outer_rel, inner_rel))
 6884                           334                 :           2376 :         return true;
                                335                 :                : 
                                336                 :                :     /* Otherwise postpone the join till later. */
 7387                           337                 :           1140 :     return false;
                                338                 :                : }
        

Generated by: LCOV version 2.1-beta2-3-g6141622