/*------------------------------------------------------------------------

 *

 * geqo_eval.c

 *    Routines to evaluate query trees

 *

 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group

 * Portions Copyright (c) 1994, Regents of the University of California

 *

 * src/backend/optimizer/geqo/geqo_eval.c

 *

 *-------------------------------------------------------------------------

 */

/* contributed by:

   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=

   *  Martin Utesch        * Institute of Automatic Control    *

   =               = University of Mining and Technology =

   *  utesch@aut.tu-freiberg.de  * Freiberg, Germany           *

   =*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=

 */

#include "postgres.h"

#include <float.h>

#include <limits.h>

#include <math.h>

#include "optimizer/geqo.h"

#include "optimizer/joininfo.h"

#include "optimizer/pathnode.h"

#include "optimizer/paths.h"

#include "utils/memutils.h"

/* A "clump" of already-joined relations within gimme_tree */

typedef struct

{

  RelOptInfo *joinrel;    /* joinrel for the set of relations */

  int     size;     /* number of input relations in clump */

} Clump;

static List *merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump,

             int num_gene, bool force);

static bool desirable_join(PlannerInfo *root,

               RelOptInfo *outer_rel, RelOptInfo *inner_rel);

/*

 * geqo_eval

 *

 * Returns cost of a query tree as an individual of the population.

 *

 * If no legal join order can be extracted from the proposed tour,

 * returns DBL_MAX.

 */

Cost

geqo_eval(PlannerInfo *root, Gene *tour, int num_gene)

{

  MemoryContext mycontext;

  MemoryContext oldcxt;

  RelOptInfo *joinrel;

  Cost    fitness;

  int     savelength;

  struct HTAB *savehash;

  /*

   * Create a private memory context that will hold all temp storage

   * allocated inside gimme_tree().

   *

   * Since geqo_eval() will be called many times, we can't afford to let all

   * that memory go unreclaimed until end of statement.  Note we make the

   * temp context a child of the planner's normal context, so that it will

   * be freed even if we abort via ereport(ERROR).

   */

  mycontext = AllocSetContextCreate(CurrentMemoryContext,

                    "GEQO",

                    ALLOCSET_DEFAULT_SIZES);

  oldcxt = MemoryContextSwitchTo(mycontext);

  /*

   * gimme_tree will add entries to root->join_rel_list, which may or may

   * not already contain some entries.  The newly added entries will be

   * recycled by the MemoryContextDelete below, so we must ensure that the

   * list is restored to its former state before exiting.  We can do this by

   * truncating the list to its original length.  NOTE this assumes that any

   * added entries are appended at the end!

   *

   * We also must take care not to mess up the outer join_rel_hash, if there

   * is one.  We can do this by just temporarily setting the link to NULL.

   * (If we are dealing with enough join rels, which we very likely are, a

   * new hash table will get built and used locally.)

   *

   * join_rel_level[] shouldn't be in use, so just Assert it isn't.

   */

  savelength = list_length(root->join_rel_list);

  savehash = root->join_rel_hash;

  Assert(root->join_rel_level == NULL);

  root->join_rel_hash = NULL;

  /* construct the best path for the given combination of relations */

  joinrel = gimme_tree(root, tour, num_gene);

  /*

   * compute fitness, if we found a valid join

   *

   * XXX geqo does not currently support optimization for partial result

   * retrieval, nor do we take any cognizance of possible use of

   * parameterized paths --- how to fix?

   */

  if (joinrel)

  {

    Path     *best_path = joinrel->cheapest_total_path;

    fitness = best_path->total_cost;

  }

  else

    fitness = DBL_MAX;

  /*

   * Restore join_rel_list to its former state, and put back original

   * hashtable if any.

   */

  root->join_rel_list = list_truncate(root->join_rel_list,

                    savelength);

  root->join_rel_hash = savehash;

  /* release all the memory acquired within gimme_tree */

  MemoryContextSwitchTo(oldcxt);

  MemoryContextDelete(mycontext);

  return fitness;

}

/*

 * gimme_tree

 *    Form planner estimates for a join tree constructed in the specified

 *    order.

 *

 *   'tour' is the proposed join order, of length 'num_gene'

 *

 * Returns a new join relation whose cheapest path is the best plan for

 * this join order.  NB: will return NULL if join order is invalid and

 * we can't modify it into a valid order.

 *

 * The original implementation of this routine always joined in the specified

 * order, and so could only build left-sided plans (and right-sided and

 * mixtures, as a byproduct of the fact that make_join_rel() is symmetric).

 * It could never produce a "bushy" plan.  This had a couple of big problems,

 * of which the worst was that there are situations involving join order

 * restrictions where the only valid plans are bushy.

 *

 * The present implementation takes the given tour as a guideline, but

 * postpones joins that are illegal or seem unsuitable according to some

 * heuristic rules.  This allows correct bushy plans to be generated at need,

 * and as a nice side-effect it seems to materially improve the quality of the

 * generated plans.  Note however that since it's just a heuristic, it can

 * still fail in some cases.  (In particular, we might clump together

 * relations that actually mustn't be joined yet due to LATERAL restrictions;

 * since there's no provision for un-clumping, this must lead to failure.)

 */

RelOptInfo *

gimme_tree(PlannerInfo *root, Gene *tour, int num_gene)

{

  GeqoPrivateData *private = (GeqoPrivateData *) root->join_search_private;

  List     *clumps;

  int     rel_count;

  /*

   * Sometimes, a relation can't yet be joined to others due to heuristics

   * or actual semantic restrictions.  We maintain a list of "clumps" of

   * successfully joined relations, with larger clumps at the front. Each

   * new relation from the tour is added to the first clump it can be joined

   * to; if there is none then it becomes a new clump of its own. When we

   * enlarge an existing clump we check to see if it can now be merged with

   * any other clumps.  After the tour is all scanned, we forget about the

   * heuristics and try to forcibly join any remaining clumps.  If we are

   * unable to merge all the clumps into one, fail.

   */

  clumps = NIL;

  for (rel_count = 0; rel_count < num_gene; rel_count++)

  {

    int     cur_rel_index;

    RelOptInfo *cur_rel;

    Clump    *cur_clump;

    /* Get the next input relation */

    cur_rel_index = (int) tour[rel_count];

    cur_rel = (RelOptInfo *) list_nth(private->initial_rels,

                      cur_rel_index - 1);

    /* Make it into a single-rel clump */

    cur_clump = (Clump *) palloc(sizeof(Clump));

    cur_clump->joinrel = cur_rel;

    cur_clump->size = 1;

    /* Merge it into the clumps list, using only desirable joins */

    clumps = merge_clump(root, clumps, cur_clump, num_gene, false);

  }

  if (list_length(clumps) > 1)

  {

    /* Force-join the remaining clumps in some legal order */

    List     *fclumps;

    ListCell   *lc;

    fclumps = NIL;

    foreach(lc, clumps)

    {

      Clump    *clump = (Clump *) lfirst(lc);

      fclumps = merge_clump(root, fclumps, clump, num_gene, true);

    }

    clumps = fclumps;

  }

  /* Did we succeed in forming a single join relation? */

  if (list_length(clumps) != 1)

    return NULL;

  return ((Clump *) linitial(clumps))->joinrel;

}

/*

 * Merge a "clump" into the list of existing clumps for gimme_tree.

 *

 * We try to merge the clump into some existing clump, and repeat if

 * successful.  When no more merging is possible, insert the clump

 * into the list, preserving the list ordering rule (namely, that

 * clumps of larger size appear earlier).

 *

 * If force is true, merge anywhere a join is legal, even if it causes

 * a cartesian join to be performed.  When force is false, do only

 * "desirable" joins.

 */

static List *

merge_clump(PlannerInfo *root, List *clumps, Clump *new_clump, int num_gene,

      bool force)

{

  ListCell   *lc;

  int     pos;

  /* Look for a clump that new_clump can join to */

  foreach(lc, clumps)

  {

    Clump    *old_clump = (Clump *) lfirst(lc);

    if (force ||

      desirable_join(root, old_clump->joinrel, new_clump->joinrel))

    {

      RelOptInfo *joinrel;

      /*

       * Construct a RelOptInfo representing the join of these two input

       * relations.  Note that we expect the joinrel not to exist in

       * root->join_rel_list yet, and so the paths constructed for it

       * will only include the ones we want.

       */

      joinrel = make_join_rel(root,

                  old_clump->joinrel,

                  new_clump->joinrel);

      /* Keep searching if join order is not valid */

      if (joinrel)

      {

        /* Create paths for partitionwise joins. */

        generate_partitionwise_join_paths(root, joinrel);

        /*

         * Except for the topmost scan/join rel, consider gathering

         * partial paths.  We'll do the same for the topmost scan/join

         * rel once we know the final targetlist (see

         * grouping_planner).

         */

        if (!bms_equal(joinrel->relids, root->all_query_rels))

          generate_useful_gather_paths(root, joinrel, false);

        /* Find and save the cheapest paths for this joinrel */

        set_cheapest(joinrel);

        /* Absorb new clump into old */

        old_clump->joinrel = joinrel;

        old_clump->size += new_clump->size;

        pfree(new_clump);

        /* Remove old_clump from list */

        clumps = foreach_delete_current(clumps, lc);

        /*

         * Recursively try to merge the enlarged old_clump with

         * others.  When no further merge is possible, we'll reinsert

         * it into the list.

         */

        return merge_clump(root, clumps, old_clump, num_gene, force);

      }

    }

  }

  /*

   * No merging is possible, so add new_clump as an independent clump, in

   * proper order according to size.  We can be fast for the common case

   * where it has size 1 --- it should always go at the end.

   */

  if (clumps == NIL || new_clump->size == 1)

    return lappend(clumps, new_clump);

  /* Else search for the place to insert it */

  for (pos = 0; pos < list_length(clumps); pos++)

  {

    Clump    *old_clump = (Clump *) list_nth(clumps, pos);

    if (new_clump->size > old_clump->size)

      break;       /* new_clump belongs before old_clump */

  }

  clumps = list_insert_nth(clumps, pos, new_clump);

  return clumps;

}

/*

 * Heuristics for gimme_tree: do we want to join these two relations?

 */

static bool

desirable_join(PlannerInfo *root,

         RelOptInfo *outer_rel, RelOptInfo *inner_rel)

{

  /*

   * Join if there is an applicable join clause, or if there is a join order

   * restriction forcing these rels to be joined.

   */

  if (have_relevant_joinclause(root, outer_rel, inner_rel) ||

    have_join_order_restriction(root, outer_rel, inner_rel))

    return true;

  /* Otherwise postpone the join till later. */

  return false;

}