aboutsummaryrefslogtreecommitdiff
path: root/src/backend/optimizer/path/allpaths.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/backend/optimizer/path/allpaths.c')
-rw-r--r--src/backend/optimizer/path/allpaths.c351
1 files changed, 351 insertions, 0 deletions
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
new file mode 100644
index 00000000000..0ed2139095d
--- /dev/null
+++ b/src/backend/optimizer/path/allpaths.c
@@ -0,0 +1,351 @@
+/*-------------------------------------------------------------------------
+ *
+ * allpaths.c--
+ * Routines to find possible search paths for processing a query
+ *
+ * Copyright (c) 1994, Regents of the University of California
+ *
+ *
+ * IDENTIFICATION
+ * $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.1.1.1 1996/07/09 06:21:35 scrappy Exp $
+ *
+ *-------------------------------------------------------------------------
+ */
+#include <string.h>
+
+#include "postgres.h"
+
+#include "nodes/pg_list.h"
+#include "nodes/relation.h"
+#include "nodes/primnodes.h"
+
+#include "optimizer/internal.h"
+
+#include "optimizer/paths.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/clauses.h"
+#include "optimizer/xfunc.h"
+#include "optimizer/cost.h"
+
+#include "commands/creatinh.h"
+
+static void find_rel_paths(Query *root, List *rels);
+static List *find_join_paths(Query *root, List *outer_rels, int levels_left);
+
+/*
+ * find-paths--
+ * Finds all possible access paths for executing a query, returning the
+ * top level list of relation entries.
+ *
+ * 'rels' is the list of single relation entries appearing in the query
+ */
+List *
+find_paths(Query *root, List *rels)
+{
+ int levels_left;
+
+ /*
+ * Set the number of join (not nesting) levels yet to be processed.
+ */
+ levels_left = length(rels);
+
+ if (levels_left <= 0)
+ return NIL;
+
+ /*
+ * Find the base relation paths.
+ */
+ find_rel_paths(root, rels);
+
+ if (levels_left <= 1) {
+ /*
+ * Unsorted single relation, no more processing is required.
+ */
+ return (rels);
+ }else {
+ /*
+ * this means that joins or sorts are required.
+ * set selectivities of clauses that have not been set
+ * by an index.
+ */
+ set_rest_relselec(root, rels);
+
+ return(find_join_paths(root, rels, levels_left-1));
+ }
+}
+
+/*
+ * find-rel-paths--
+ * Finds all paths available for scanning each relation entry in
+ * 'rels'. Sequential scan and any available indices are considered
+ * if possible(indices are not considered for lower nesting levels).
+ * All unique paths are attached to the relation's 'pathlist' field.
+ *
+ * MODIFIES: rels
+ */
+static void
+find_rel_paths(Query *root, List *rels)
+{
+ List *temp;
+ Rel *rel;
+ List *lastpath;
+
+ foreach(temp, rels) {
+ List *sequential_scan_list;
+ List *rel_index_scan_list;
+ List *or_index_scan_list;
+
+ rel = (Rel *)lfirst(temp);
+ sequential_scan_list = lcons(create_seqscan_path(rel),
+ NIL);
+
+ rel_index_scan_list =
+ find_index_paths(root,
+ rel,
+ find_relation_indices(root,rel),
+ rel->clauseinfo,
+ rel->joininfo);
+
+ or_index_scan_list =
+ create_or_index_paths(root, rel, rel->clauseinfo);
+
+ rel->pathlist = add_pathlist(rel,
+ sequential_scan_list,
+ append(rel_index_scan_list,
+ or_index_scan_list));
+
+ /* The unordered path is always the last in the list.
+ * If it is not the cheapest path, prune it.
+ */
+ lastpath = rel->pathlist;
+ while(lnext(lastpath)!=NIL)
+ lastpath=lnext(lastpath);
+ prune_rel_path(rel, (Path*)lfirst(lastpath));
+ /*
+ * if there is a qualification of sequential scan the selec.
+ * value is not set -- so set it explicitly -- Sunita
+ */
+ set_rest_selec(root, rel->clauseinfo);
+ rel->size = compute_rel_size(rel);
+ rel->width = compute_rel_width(rel);
+ }
+ return;
+}
+
+/*
+ * find-join-paths--
+ * Find all possible joinpaths for a query by successively finding ways
+ * to join single relations into join relations.
+ *
+ * if BushyPlanFlag is set, bushy tree plans will be generated:
+ * Find all possible joinpaths(bushy trees) for a query by systematically
+ * finding ways to join relations(both original and derived) together.
+ *
+ * 'outer-rels' is the current list of relations for which join paths
+ * are to be found, i.e., he current list of relations that
+ * have already been derived.
+ * 'levels-left' is the current join level being processed, where '1' is
+ * the "last" level
+ *
+ * Returns the final level of join relations, i.e., the relation that is
+ * the result of joining all the original relations togehter.
+ */
+static List *
+find_join_paths(Query *root, List *outer_rels, int levels_left)
+{
+ List *x;
+ List *new_rels;
+ Rel *rel;
+
+ /*
+ * Determine all possible pairs of relations to be joined at this level.
+ * Determine paths for joining these relation pairs and modify 'new-rels'
+ * accordingly, then eliminate redundant join relations.
+ */
+ new_rels = find_join_rels(root, outer_rels);
+
+ find_all_join_paths(root, new_rels);
+
+ new_rels = prune_joinrels(new_rels);
+
+#if 0
+ /*
+ ** for each expensive predicate in each path in each distinct rel,
+ ** consider doing pullup -- JMH
+ */
+ if (XfuncMode != XFUNC_NOPULL && XfuncMode != XFUNC_OFF)
+ foreach(x, new_rels)
+ xfunc_trypullup((Rel*)lfirst(x));
+#endif
+
+ prune_rel_paths(new_rels);
+
+ if(BushyPlanFlag) {
+ /*
+ * In case of bushy trees
+ * if there is still a join between a join relation and another
+ * relation, add a new joininfo that involves the join relation
+ * to the joininfo list of the other relation
+ */
+ add_new_joininfos(root, new_rels,outer_rels);
+ }
+
+ foreach(x, new_rels) {
+ rel = (Rel*)lfirst(x);
+ rel->size = compute_rel_size(rel);
+ rel->width = compute_rel_width(rel);
+
+/*#define OPTIMIZER_DEBUG*/
+#ifdef OPTIMIZER_DEBUG
+ printf("levels left: %d\n", levels_left);
+ debug_print_rel(root, rel);
+#endif
+ }
+
+ if(BushyPlanFlag) {
+ /*
+ * prune rels that have been completely incorporated into
+ * new join rels
+ */
+ outer_rels = prune_oldrels(outer_rels);
+ /*
+ * merge join rels if then contain the same list of base rels
+ */
+ outer_rels = merge_joinrels(new_rels,outer_rels);
+ root->join_relation_list_ = outer_rels;
+ }
+ else {
+ root->join_relation_list_ = new_rels;
+ }
+
+ if(levels_left == 1) {
+ if(BushyPlanFlag)
+ return(final_join_rels(outer_rels));
+ else
+ return(new_rels);
+ } else {
+ if(BushyPlanFlag)
+ return(find_join_paths(root, outer_rels, levels_left - 1));
+ else
+ return(find_join_paths(root, new_rels, levels_left - 1));
+ }
+}
+
+/*****************************************************************************
+ *
+ *****************************************************************************/
+
+static void
+print_joinclauses(Query *root, List *clauses)
+{
+ List *l;
+ extern void print_expr(Node *expr, List *rtable); /* in print.c */
+
+ foreach(l, clauses) {
+ CInfo *c = lfirst(l);
+
+ print_expr((Node*)c->clause, root->rtable);
+ if (lnext(l)) printf(" ");
+ }
+}
+
+void
+print_path(Query *root, Path *path, int indent)
+{
+ char *ptype = NULL;
+ JoinPath *jp;
+ bool join;
+ int i;
+
+ for(i=0; i < indent; i++)
+ printf("\t");
+
+ switch(nodeTag(path)) {
+ case T_Path:
+ ptype = "SeqScan"; join=false; break;
+ case T_IndexPath:
+ ptype = "IdxScan"; join=false; break;
+ case T_JoinPath:
+ ptype = "Nestloop"; join=true; break;
+ case T_MergePath:
+ ptype = "MergeJoin"; join=true; break;
+ case T_HashPath:
+ ptype = "HashJoin"; join=true; break;
+ default:
+ break;
+ }
+ if (join) {
+ int size = path->parent->size;
+ jp = (JoinPath*)path;
+ printf("%s size=%d cost=%f\n", ptype, size, path->path_cost);
+ switch(nodeTag(path)) {
+ case T_MergePath:
+ case T_HashPath:
+ for(i=0; i < indent+1; i++)
+ printf("\t");
+ printf(" clauses=(");
+ print_joinclauses(root,
+ ((JoinPath*)path)->pathclauseinfo);
+ printf(")\n");
+
+ if (nodeTag(path)==T_MergePath) {
+ MergePath *mp = (MergePath*)path;
+ if (mp->outersortkeys || mp->innersortkeys) {
+ for(i=0; i < indent+1; i++)
+ printf("\t");
+ printf(" sortouter=%d sortinner=%d\n",
+ ((mp->outersortkeys)?1:0),
+ ((mp->innersortkeys)?1:0));
+ }
+ }
+ break;
+ default:
+ break;
+ }
+ print_path(root, jp->outerjoinpath, indent+1);
+ print_path(root, jp->innerjoinpath, indent+1);
+ } else {
+ int size = path->parent->size;
+ int relid = lfirsti(path->parent->relids);
+ printf("%s(%d) size=%d cost=%f",
+ ptype, relid, size, path->path_cost);
+
+ if (nodeTag(path)==T_IndexPath) {
+ List *k, *l;
+
+ printf(" keys=");
+ foreach (k, path->keys) {
+ printf("(");
+ foreach (l, lfirst(k)) {
+ Var *var = lfirst(l);
+ printf("%d.%d", var->varnoold, var->varoattno);
+ if (lnext(l)) printf(", ");
+ }
+ printf(")");
+ if (lnext(k)) printf(", ");
+ }
+ }
+ printf("\n");
+ }
+}
+
+#ifdef OPTIMIZER_DEBUG
+static void
+debug_print_rel(Query *root, Rel *rel)
+{
+ List *l;
+
+ printf("(");
+ foreach(l, rel->relids) {
+ printf("%d ", lfirsti(l));
+ }
+ printf("): size=%d width=%d\n", rel->size, rel->width);
+
+ printf("\tpath list:\n");
+ foreach (l, rel->pathlist) {
+ print_path(root, lfirst(l), 1);
+ }
+ printf("\tcheapest path:\n");
+ print_path(root, rel->cheapestpath, 1);
+}
+#endif /* OPTIMIZER_DEBUG */
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-19 03:36:27 +0000