Subject: Re: should we have a fast-path planning for OLTP starjoins?

From: Robert Haas <[email-masked]>
Date: Sat, 3 Jan 2026 14:23:01 -0500

On Wed, Dec 24, 2025 at 1:16 PM Tom Lane <[email-masked]> wrote:
> Having said that, I'm starting to wonder whether "do this stuff in a
> separate pass before the main optimizer" is the wrong structural
> decision.  Should we be injecting the logic at some later point
> where we've gathered more information?  At least in principle,
> we should be able to build all base-relation Paths before we start
> to think about join order; would having those help?

I've been wondering for a while about making cardinality estimation a
separate pass from path construction. One reason is that we currently
come up with different row count estimates for partitionwise and
non-partitionwise paths for the same rel, which doesn't really make
sense. We could do partitionwise estimates for joins that could be
done partitionwise even if partitionwise join is not selected or even
if it is entirely disabled, and I think we'd get more accurate
estimates (as we should for baserels also). But I wonder if it might
help with this problem, too. Like, suppose we try to construct a
star-join path using some fast-path, and as we go we compute
cardinality estimates for the joinrels we consider building. At any
point, we can decide to give up, e.g. because we find a row-count
inflating join, or something that otherwise doesn't meet the criteria
for the fast path. At that point, we can fall back and do the standard
join search, and all the cardinality estimates we used are still
available and don't need to be recomputed, so the only effort we've
wasted is the effort of constructing paths for some rels. Those paths
probably do need to be discarded, unless our fast-path always computes
the full path set for each rel it considers. But being able to reuse
the cardinality estimates would limit the wasted work.

Your idea of building base-relation paths early, thus also getting
base-relation cardinality estimates, has some of the same advantages
and might be easier to implement. It would mean that we lose any join
cardinality estimates that the fast-path algorithm computes, so I
think it's probably at least modestly worse if you ignore
implementation complexity, but I can almost hear you telling me that
we cannot and should not ignore implementation complexity, which is
fair enough as far as it goes.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Tomas Vondra <[email-masked]>
Date: Fri, 29 May 2026 00:11:32 +0200

Hi,

I got into a couple discussions regarding this patch in Vancouver last week.

Some of the questions were about possible overlap with the "foreign key
joins" patch Joel is working on. That patch needs to prove some of the
same questions about joins (e.g. which joins can't change cardinality).
So it seems plausible some this join planning patch could leverage some
of the information eventually introduced by that patch, and maybe apply
the optimization in more cases. Not sure.

But re-reading the old thread, this doesn't seem to be why it got stuck.
We already can identify dimensions joined on foreign keys, and that
seems like a good start.

IIRC the thing that worried me was that just sticking the joins at the
end is pretty heavy-handed. It can easily end up making the plan worse,
if one of the other joins increases the cardinality. Would that be
common? Probably not, but it seems unnecessarily risky.

Ideally, we'd do join that reduce cardinality first (with the regular DP
join search), then join all the dimensions, and finally do all joins
that expand cardinality (again, using the regular DP). But the earlier
patches worked by adjusting the join tree in query_planner(), i.e. way
before we get to calculate join cardinalities.

My plan (mentioned even during the Vancouver hallway track) was to
invent a new type of jointree "entry" representing the dimensions, and
modifying the join_search_one_level() et al to "expand" it whenever we
decide to join it. So it'd get the join group, and replace it with a
sequence of joins of all the dimensions. We'd try it in various places,
and could pick the best plan. But it seemed pretty complex and invasive,
so I kept postponing the work.

I started hacking on it this week, but I also started thinking if there
might be a better solution, that would fit into the current join search
more naturally. And I think I actually found a good approach.

It works like this:

1) query_planner()

Determine if the query includes a starjoin (or multiple), and remember
the relids included in the starjoin cluster. Pick a "canonical" join
order for each starjoin cluster we found (e.g. with dimensions in relid
order).

2) standard_join_search()/join_search_one_level()

When constructing the join rels (e.g. in make_join_rel or right before
it's called), check that the new rel would violate the canonical order.
If it would, refuse to create it, just like we do for various other join
restrictions.

The new join restriction is that if the join result includes a subset of
the starjoin cluster, then it has to include the fact + prefix of the
list of dimensions (which is the canonical join order).

Note: It should be possible to make the restriction even more strict, if
needed (e.g. to effectively join all dimensions at once, with no other
joins in between).

The attached patch v6 does this. It's a bit of a PoC quality, but it
should be good enough for testing and experiments (it does pass
check-world for me, but some parts still need more care / cleanup).

I also did a buch of tests to see how effective it is, and it seems
pretty effective. It gives me ~80% throughput of join_collapse_limit=1,
even with extreme number of dimensions (e.g. 16), with disabled geqo and
join_collapse_limit=16 (so it's all in one join list). The current code
drops to ~1% of join_collapse_limit=1, so this is about two orders of
magnitude faster.

Yes, this is in situations when the join does nothing during execution
(the fact table is empty). So in practice the improvement will be
smaller, but it can still be a substantial speedup, depending on how
much other work it's doing.

Attached are a couple charts from a test with 1-15 dimensions (scripts
attached too). I was wondering how geqo affects this, so I tried with
geqo=on/off, and with join_collapse_limit=1/8/16.

With join_collapse_limit=1 there's no difference between any of the runs
(master, patches with on/off). Here's an example of results:

  dims   master(1)   master  sj/off    sj/on  master   sj/off   sj/on
  -------------------------------------------------------------------
  1          49485    48797   48966    49118     99%      99%     99%
  3          26886    22003   21319    24322     82%      79%     90%
  5          17759     7923    7634    15434     45%      43%     87%
  7          13110     2122    2071    11290     16%      16%     86%
  9          10390      462     445     8709      4%       4%     84%
  11          7781       87      86     6488      1%       1%     83%
  13          5948       14      14     5749      0%       0%     97%
  15          5237        1       1     4227      0%       0%     81%

The first column is for master with join_collapse_limit=1, which I take
as the best possible throughtput, if we eliminate the join order search
almost completely. The rest is with geqo=off and join_collapse_limit=16.

So that's the 80% of possible throughput, pretty good IMO. Especially
considering master is at 1 tps.

There are a couple more interesting charts, and a CSV with raw results.
A funny (but not entirely surprising) detail is that geqo=on helps a bit
(from 1tps to ~90tps for 15 dimensions), but it's still far from the
limit=1 throughput of ~5200 tps. The fastpath join order does better.

I'm sure the code needs cleanups and fixes, but I like the approach way
more than the original plan (inventing a new group join entry).

Any comments regarding this alternative approach?

regards

-- 
Tomas Vondra
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 1c575e56ff6..4adb334470c 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -164,6 +164,7 @@ bool		enable_parallel_hash = true;
 bool		enable_partition_pruning = true;
 bool		enable_presorted_aggregate = true;
 bool		enable_async_append = true;
+bool		enable_starjoin_ordering = true;
 
 typedef struct
 {
diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c
index 443e2dca7c0..24c00c03ebb 100644
--- a/src/backend/optimizer/path/joinrels.c
+++ b/src/backend/optimizer/path/joinrels.c
@@ -32,6 +32,9 @@ static void make_rels_by_clause_joins(PlannerInfo *root,
 static void make_rels_by_clauseless_joins(PlannerInfo *root,
 										  RelOptInfo *old_rel,
 										  List *other_rels);
+static bool starjoin_order_invalid(PlannerInfo *root,
+								   RelOptInfo *rel1,
+								   RelOptInfo *rel2);
 static bool has_join_restriction(PlannerInfo *root, RelOptInfo *rel);
 static bool has_legal_joinclause(PlannerInfo *root, RelOptInfo *rel);
 static bool restriction_is_constant_false(List *restrictlist,
@@ -709,6 +712,14 @@ make_join_rel(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
 	/* We should never try to join two overlapping sets of rels. */
 	Assert(!bms_overlap(rel1->relids, rel2->relids));
 
+	/*
+	 * If this join would be a redundant ordering of a previously detected
+	 * starjoin cluster, skip it. All cluster orderings have identical cost;
+	 * we keep only the canonical one chosen when building starjoin clusters.
+	 */
+	if (starjoin_order_invalid(root, rel1, rel2))
+		return NULL;
+
 	/* Construct Relids set that identifies the joinrel (without OJ as yet). */
 	joinrelids = bms_union(rel1->relids, rel2->relids);
 
@@ -2112,3 +2123,107 @@ get_matching_part_pairs(PlannerInfo *root, RelOptInfo *joinrel,
 		*parts2 = lappend(*parts2, child_rel2);
 	}
 }
+
+/*
+ * starjoin_order_invalid
+ *		Return true if the proposed join (rel1, rel2) would build a
+ *		non-canonical ordering of a starjoin cluster.
+ *
+ * For every star cluster in root->starjoin_clusters, we enforce the canonical
+ * decomposition of any joinrel containinig the fact and at least one cluster
+ * dimension - the dimensions must form a prefix of the order determined when
+ * collecting the starjoin clusters.
+ *
+ * This rule preserves exactly one decomposition per joinrel relid set, so
+ * each canonical joinrel is still built; redundant orderings are pruned.
+ *
+ * We might forbid additional joins, for example we might forbid joinrels
+ * containing a cluster dimension without the fact.
+ */
+static bool
+starjoin_order_invalid(PlannerInfo *root, RelOptInfo *rel1, RelOptInfo *rel2)
+{
+	ListCell   *lc;
+	Relids		join_relids;
+	bool		violates = false;
+
+	/* No starjoin optimization outside the stardard DP join search. */
+	if (root->join_rel_level == NULL)
+		return false;
+
+	/* no starjoins found (maybe because the option is disabled) */
+	if (root->starjoin_clusters == NIL)
+		return false;
+
+	/* relids of the result */
+	join_relids = bms_union(rel1->relids, rel2->relids);
+
+	/* does this contradict any of the clusters we know about */
+	foreach(lc, root->starjoin_clusters)
+	{
+		StarJoinClusterInfo *c = (StarJoinClusterInfo *) lfirst(lc);
+		Relids	dims;
+		int		ndims;
+		int		idx;
+
+		/*
+		 * If all dimensions are on one side of the join, we've already
+		 * checked the canonical order earlier, when building it. No need
+		 * to redo the check again.
+		 */
+		dims = bms_intersect(rel1->relids, c->dim_relids);
+		if (bms_is_empty(dims))
+		{
+			bms_free(dims);
+			continue;
+		}
+		bms_free(dims);
+
+		dims = bms_intersect(rel2->relids, c->dim_relids);
+		if (bms_is_empty(dims))
+		{
+			bms_free(dims);
+			continue;
+		}
+		bms_free(dims);
+
+		/* the canonical ordering has to include the fact */
+		if (!bms_is_member(c->fact_relid, join_relids))
+		{
+			violates = true;
+			break;
+		}
+
+		/*
+		 * Count the prefix length covered by this join. We simply use the
+		 * bitmap of cluster dimensions. For now that's fine, but it we
+		 * choose to allow snowflake joins, we'll need to rethink it and use
+		 * a list or something where the order is not determined by relid
+		 * (probably?)
+		 */
+		ndims = 0;
+		idx = -1;
+		while ((idx = bms_next_member(c->dim_relids, idx)) >= 0)
+		{
+			/* found end of dimension prefix */
+			if (!bms_is_member(idx, join_relids))
+				break;
+
+			ndims++;
+		}
+
+		dims = bms_intersect(join_relids, c->dim_relids);
+		if (bms_num_members(dims) != ndims)
+		{
+			bms_free(dims);
+			violates = true;
+			break;
+		}
+
+		bms_free(dims);
+	}
+
+	bms_free(join_relids);
+
+	return violates;
+}
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index b38422c47a4..4dbc0512d4e 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -4295,3 +4295,260 @@ check_memoizable(RestrictInfo *restrictinfo)
 	if (OidIsValid(typentry->hash_proc) && OidIsValid(typentry->eq_opr))
 		restrictinfo->right_hasheqoperator = typentry->eq_opr;
 }
+
+
+
+/*
+ * starjoins_canonicalize
+ *		Detect star-shaped sub-joins and determine canonical join order.
+ *
+ * A starjoin cluster is a fact relation joined to two or more dimensions
+ * via an equality condition matching a foreign key, satisfying these
+ * conditions:
+ *
+ *	1. The dimension is a plain base relation (RELOPT_BASEREL).
+ *
+ *	2. All join columns on the fact are NOT NULL.
+ *
+ *	3. The dimension has no local restriction quals (baserestrictinfo).
+ *
+ *	4. The dimension has no relevant join clauses to any rel other than
+ *	   the fact (checked via have_relevant_joinclause, which also covers
+ *	   equivalence-class joins).
+ *
+ *	5. The dimension does not participate in any SpecialJoinInfo.
+ *
+ *	6. The dimension has no lateral references in or out.
+ *
+ *	7. The dimension is not constrained by any PlaceHolderInfo.
+ *
+ * Under these conditions, the join is strictly cardinality-preserving with
+ * respect to the fact table. And all join orderings for a cluster produce
+ * identical row counts and identical per-step costs. The join_search can
+ * therefore consider only a single canonical ordering without losing the
+ * optimal plan.
+ *
+ * Dimensions that fail the preconditions are simply not added to any
+ * cluster; the planner then handles them in the ordinary way.  A fact
+ * with fewer than two qualifying dimensions produces no cluster (there
+ * is nothing to deduplicate).
+ *
+ * Must be called after match_foreign_keys_to_quals(), and after lateral,
+ * PHV and SpecialJoinInfo information have been finalized.
+ */
+void
+generate_starjoin_clusters(PlannerInfo *root)
+{
+	int			nrels;
+	List	  **fact_dims;
+	int			f;
+	ListCell   *lc;
+
+	/* do nothing if optimization not enabled */
+	if (!enable_starjoin_ordering)
+		return;
+
+	/* also, do nothing if there are no foreign key joins */
+	if (root->fkey_list == NIL)
+		return;
+
+	nrels = root->simple_rel_array_size;
+	fact_dims = (List **) palloc0(nrels * sizeof(List *));
+
+	/*
+	 * Group fully-matched FKs by referencing (fact) relid, collecting
+	 * candidate dimension relids. match_foreign_keys_to_quals() has
+	 * already filtered fkey_list to fully-matched FKs.
+	 */
+	foreach(lc, root->fkey_list)
+	{
+		ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
+		Index		fact_rti = fkinfo->con_relid;
+		Index		dim_rti = fkinfo->ref_relid;
+
+		/*
+		 * Expect valid RTI on both sides (otherwise should not have kept
+		 * this foreign key. Similarly, we shouldn't get a FK with the
+		 * same RTI on both ends.
+		 */
+		Assert(fact_rti < root->simple_rel_array_size);
+		Assert(dim_rti < root->simple_rel_array_size);
+		Assert(fact_rti != dim_rti);
+
+		/*
+		 * With duplicate foreign keys we might have already included this
+		 * candidate dimension.
+		 */
+		if (list_member_int(fact_dims[fact_rti], dim_rti))
+			continue;
+
+		/* found a candidate dimension, stash it to the list */
+		fact_dims[fact_rti] = lappend_int(fact_dims[fact_rti], dim_rti);
+	}
+
+	/*
+	 * For each candidate fact, validate which dimensions meet the other
+	 * requirements, and build a StarJoinClusterInfo if at least two
+	 * dimensions qualify.
+	 */
+	for (f = 1; f < nrels; f++)
+	{
+		RelOptInfo *fact_rel;
+		Relids		dim_relids = NULL;
+		int			ndims = 0;
+		ListCell   *lc2;
+		StarJoinClusterInfo *cluster;
+
+		/*
+		 * Can't be a fact if there are no potential dimensions (we need
+		 * at least two for a starjoin optimization to matter).
+		 */
+		if (list_length(fact_dims[f]) < 2)
+			continue;
+
+		/* has to be a baserel (how else could it be, if it has a FK?) */
+		fact_rel = root->simple_rel_array[f];
+		if (fact_rel == NULL || fact_rel->reloptkind != RELOPT_BASEREL)
+			continue;
+
+		/* count dimensions matching the requirements */
+		foreach(lc2, fact_dims[f])
+		{
+			Index		d = (Index) lfirst_int(lc2);
+			RelOptInfo *dim_rel = root->simple_rel_array[d];
+			ForeignKeyOptInfo *fkinfo = NULL;
+			ListCell   *lc3;
+			bool		ok = true;
+			int			colno;
+			int			r;
+
+			/* has to be a baserel (it's referenced by a FK, so?) */
+			if (dim_rel == NULL || dim_rel->reloptkind != RELOPT_BASEREL)
+				continue;
+
+			/* No local restriction quals on the dimension. */
+			if (dim_rel->baserestrictinfo != NIL)
+				continue;
+
+			/* No lateral references in or out. */
+			if (!bms_is_empty(dim_rel->lateral_relids))
+				continue;
+			if (!bms_is_empty(dim_rel->lateral_referencers))
+				continue;
+
+			/* Find the matching FK so we can check NOT NULL on conkey cols */
+			foreach(lc3, root->fkey_list)
+			{
+				ForeignKeyOptInfo *fki = (ForeignKeyOptInfo *) lfirst(lc3);
+
+				if ((fki->con_relid == f) && (fki->ref_relid == d))
+				{
+					fkinfo = fki;
+					break;
+				}
+			}
+
+			/* we should have found a FK, that's how we got the array */
+			Assert(fkinfo != NULL);
+
+			/*
+			 * Make sure all columns on the fact side are NOT NULL. We
+			 * know the FK is fully matched by the join, so use that.
+			 */
+			for (colno = 0; colno < fkinfo->nkeys; colno++)
+			{
+				if (!bms_is_member(fkinfo->conkey[colno],
+								   fact_rel->notnullattnums))
+				{
+					ok = false;
+					break;
+				}
+			}
+			if (!ok)
+				continue;
+
+			/*
+			 * Should not be involved in any SpecialJoinInfo (for now the
+			 * starjoin is done only for inner joins).
+			 *
+			 * XXX We could relax this, and allow left joins, as long as the
+			 * target has a unique constraint.
+			 */
+			foreach(lc3, root->join_info_list)
+			{
+				SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc3);
+
+				if (bms_is_member(d, sjinfo->min_lefthand) ||
+					bms_is_member(d, sjinfo->min_righthand) ||
+					bms_is_member(d, sjinfo->syn_lefthand) ||
+					bms_is_member(d, sjinfo->syn_righthand))
+				{
+					ok = false;
+					break;
+				}
+			}
+			if (!ok)
+				continue;
+
+			/* Not constrained by any PlaceHolderInfo. */
+			foreach(lc3, root->placeholder_list)
+			{
+				PlaceHolderInfo *phi = (PlaceHolderInfo *) lfirst(lc3);
+
+				if (bms_is_member((int) d, phi->ph_eval_at) ||
+					bms_is_member((int) d, phi->ph_lateral) ||
+					bms_is_member((int) d, phi->ph_needed))
+				{
+					ok = false;
+					break;
+				}
+			}
+			if (!ok)
+				continue;
+
+			/*
+			 * The dimension must have no relevant join clause to any rel
+			 * other than the fact.  have_relevant_joinclause() also covers
+			 * equivalence-class joins.
+			 */
+			for (r = 1; r < nrels; r++)
+			{
+				RelOptInfo *other_rel;
+
+				if (r == (int) d || r == f)
+					continue;
+				other_rel = root->simple_rel_array[r];
+				if (other_rel == NULL ||
+					other_rel->reloptkind != RELOPT_BASEREL)
+					continue;
+				if (have_relevant_joinclause(root, dim_rel, other_rel))
+				{
+					ok = false;
+					break;
+				}
+			}
+			if (!ok)
+				continue;
+
+			/* Qualifies as a dimension. */
+			dim_relids = bms_add_member(dim_relids, (int) d);
+			ndims++;
+		}
+
+		/* we need at least 2 dimensions for this optimization to matter */
+		if (ndims < 2)
+		{
+			bms_free(dim_relids);
+			continue;
+		}
+
+		/* remember this cluster */
+		cluster = makeNode(StarJoinClusterInfo);
+		cluster->fact_relid = (Index) f;
+		cluster->dim_relids = dim_relids;
+
+		root->starjoin_clusters = lappend(root->starjoin_clusters, cluster);
+	}
+
+	pfree(fact_dims);
+}
diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c
index 02495e22e24..5734aecfd98 100644
--- a/src/backend/optimizer/plan/planmain.c
+++ b/src/backend/optimizer/plan/planmain.c
@@ -80,6 +80,7 @@ query_planner(PlannerInfo *root,
 	root->group_expr_list = NIL;
 	root->tlist_vars = NIL;
 	root->fkey_list = NIL;
+	root->starjoin_clusters = NIL;
 	root->initial_rels = NIL;
 
 	/*
@@ -262,6 +263,14 @@ query_planner(PlannerInfo *root,
 	 */
 	match_foreign_keys_to_quals(root);
 
+	/*
+	 * Detect star-shaped sub-joins so that join_search can skip enumerating
+	 * equivalent join orderings.  Must be done after foreign keys are
+	 * matched to quals and after lateral, PHV and SpecialJoinInfo info is
+	 * available.
+	 */
+	generate_starjoin_clusters(root);
+
 	/*
 	 * Look for join OR clauses that we can extract single-relation
 	 * restriction OR clauses from.
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index afaa058b046..f175611a6d9 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -1034,6 +1034,14 @@
   boot_val => 'true',
 },
 
+{ name => 'enable_starjoin_ordering', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
+  short_desc => 'Enables collapsing of redundant join orderings in star-shaped queries.',
+  long_desc => 'When enabled, the planner detects star joins (a fact table joined to multiple dimension tables via foreign keys referencing unique keys, with NOT NULL FK columns and no dimension-side restrictions) and avoids enumerating equivalent join orderings, since they have identical cost.',
+  flags => 'GUC_EXPLAIN',
+  variable => 'enable_starjoin_ordering',
+  boot_val => 'true',
+},
+
 { name => 'enable_tidscan', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
   short_desc => 'Enables the planner\'s use of TID scan plans.',
   flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index ac38cddaaf9..9e8812b64f5 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -448,6 +448,7 @@
 #enable_distinct_reordering = on
 #enable_self_join_elimination = on
 #enable_eager_aggregate = on
+#enable_starjoin_ordering = on
 
 # - Planner Cost Constants -
 
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 27a2c6815b7..4e39c906ccd 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -512,6 +512,14 @@ struct PlannerInfo
 	/* list of ForeignKeyOptInfos */
 	List	   *fkey_list;
 
+	/*
+	 * List of StarJoinClusterInfo entries describing detected star-shaped
+	 * sub-joins (a fact table joined to multiple FK-unique dimensions).
+	 * Used by join_search to skip enumeration of equivalent join orderings.
+	 * Populated by identify_star_join_clusters().  Not serialized.
+	 */
+	List	   *starjoin_clusters pg_node_attr(read_write_ignore);
+
 	/* desired pathkeys for query_planner() */
 	List	   *query_pathkeys;
 
@@ -1500,6 +1508,34 @@ typedef struct ForeignKeyOptInfo
 	List	   *rinfos[INDEX_MAX_KEYS];
 } ForeignKeyOptInfo;
 
+/*
+ * StarJoinClusterInfo
+ *		Description of a star-shaped sub-join detected by the planner.
+ *
+ * A "star cluster" consists of a single "fact" base relation joined to a
+ * set of "dimension" base relations.  For the cluster to be recognized,
+ * each dimension must be joined to the fact via an equality condition that
+ * matches a foreign key on the fact referencing the dimension. The columns
+ * on the fact must all be NOT NULL, and the dimension must have no other
+ * join clauses, no local restriction quals, no participation in special
+ * joins or lateral references, etc. (see generate_starjoin_cluster for
+ * the full list of preconditions).
+ *
+ * When all of these conditions hold, every join ordering that has the fact
+ * as the driver produces exactly the same row count and the same per-step
+ * cost.  join_search can therefore consider just one canonical ordering of
+ * the cluster without compromising plan quality.
+ *
+ * The bimap of dimensions determines the canonical join order.
+ */
+typedef struct StarJoinClusterInfo
+{
+	NodeTag		type;
+	Index		fact_relid;	/* index of the fact relation */
+	Relids		dim_relids;	/* indexes of the dimension relations */
+} StarJoinClusterInfo;
+
+
 /*
  * StatisticExtInfo
  *		Information about extended statistics for planning/optimization
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index f2fd5d31507..766aba773ef 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -70,6 +70,7 @@ extern PGDLLIMPORT bool enable_parallel_hash;
 extern PGDLLIMPORT bool enable_partition_pruning;
 extern PGDLLIMPORT bool enable_presorted_aggregate;
 extern PGDLLIMPORT bool enable_async_append;
+extern PGDLLIMPORT bool enable_starjoin_ordering;
 extern PGDLLIMPORT int constraint_exclusion;
 
 extern double index_pages_fetched(double tuples_fetched, BlockNumber pages,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index 71c043a25e8..1c8e9ef038a 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -104,6 +104,7 @@ extern RestrictInfo *build_implied_join_equality(PlannerInfo *root,
 												 Index security_level);
 extern void rebuild_joinclause_attr_needed(PlannerInfo *root);
 extern void match_foreign_keys_to_quals(PlannerInfo *root);
+extern void generate_starjoin_clusters(PlannerInfo *root);
 
 /*
  * prototypes for plan/analyzejoins.c
diff --git a/src/test/modules/unsafe_tests/Makefile b/src/test/modules/unsafe_tests/Makefile
index a85c854392d..dcfac290eaa 100644
--- a/src/test/modules/unsafe_tests/Makefile
+++ b/src/test/modules/unsafe_tests/Makefile
@@ -1,6 +1,6 @@
 # src/test/modules/unsafe_tests/Makefile
 
-REGRESS = rolenames setconfig alter_system_table guc_privs
+REGRESS = setconfig alter_system_table guc_privs
 REGRESS_OPTS = \
 	--create-role=regress_authenticated_user_db_sr \
 	--create-role=regress_authenticated_user_db_ssa \
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index 78bf022f7b4..8b62f343200 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -10143,3 +10143,60 @@ SELECT COUNT(*) FROM onek t1 LEFT JOIN tenk1 t2
  19000
 (1 row)
 
+--
+-- Star-join collapse: FK-unique star clusters get a canonical join order
+--
+CREATE TABLE sj_d1 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_d2 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_d3 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_f (
+    id int PRIMARY KEY,
+    d1 int NOT NULL REFERENCES sj_d1,
+    d2 int NOT NULL REFERENCES sj_d2,
+    d3 int NOT NULL REFERENCES sj_d3
+);
+ANALYZE sj_f, sj_d1, sj_d2, sj_d3;
+-- With the collapse enabled (default), the resulting plan must be identical
+-- to the plan produced with the optimization disabled.
+SET enable_starjoin_ordering = on;
+EXPLAIN (COSTS OFF)
+SELECT * FROM sj_f
+  JOIN sj_d1 ON sj_f.d1 = sj_d1.id
+  JOIN sj_d2 ON sj_f.d2 = sj_d2.id
+  JOIN sj_d3 ON sj_f.d3 = sj_d3.id;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Nested Loop
+   Join Filter: (sj_d3.id = sj_f.d3)
+   ->  Nested Loop
+         Join Filter: (sj_d2.id = sj_f.d2)
+         ->  Nested Loop
+               Join Filter: (sj_d1.id = sj_f.d1)
+               ->  Seq Scan on sj_f
+               ->  Seq Scan on sj_d1
+         ->  Seq Scan on sj_d2
+   ->  Seq Scan on sj_d3
+(10 rows)
+
+SET enable_starjoin_ordering = off;
+EXPLAIN (COSTS OFF)
+SELECT * FROM sj_f
+  JOIN sj_d1 ON sj_f.d1 = sj_d1.id
+  JOIN sj_d2 ON sj_f.d2 = sj_d2.id
+  JOIN sj_d3 ON sj_f.d3 = sj_d3.id;
+                   QUERY PLAN                    
+-------------------------------------------------
+ Nested Loop
+   Join Filter: (sj_d3.id = sj_f.d3)
+   ->  Nested Loop
+         Join Filter: (sj_d2.id = sj_f.d2)
+         ->  Nested Loop
+               Join Filter: (sj_d1.id = sj_f.d1)
+               ->  Seq Scan on sj_f
+               ->  Seq Scan on sj_d1
+         ->  Seq Scan on sj_d2
+   ->  Seq Scan on sj_d3
+(10 rows)
+
+RESET enable_starjoin_ordering;
+DROP TABLE sj_f, sj_d1, sj_d2, sj_d3;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 132b56a5864..ca6c1acd00c 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -179,8 +179,9 @@ select name, setting from pg_settings where name like 'enable%';
  enable_self_join_elimination   | on
  enable_seqscan                 | on
  enable_sort                    | on
+ enable_starjoin_ordering       | on
  enable_tidscan                 | on
-(25 rows)
+(26 rows)
 
 -- There are always wait event descriptions for various types.  InjectionPoint
 -- may be present or absent, depending on history since last postmaster start.
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index fae19113cef..ade308aca56 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -3891,3 +3891,36 @@ SELECT COUNT(*) FROM onek t1 LEFT JOIN tenk1 t2
     ON (t2.thousand = t1.tenthous OR t2.thousand = t1.thousand);
 SELECT COUNT(*) FROM onek t1 LEFT JOIN tenk1 t2
     ON (t2.thousand = t1.tenthous OR t2.thousand = t1.thousand);
+
+--
+-- Star-join collapse: FK-unique star clusters get a canonical join order
+--
+CREATE TABLE sj_d1 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_d2 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_d3 (id int PRIMARY KEY, v text);
+CREATE TABLE sj_f (
+    id int PRIMARY KEY,
+    d1 int NOT NULL REFERENCES sj_d1,
+    d2 int NOT NULL REFERENCES sj_d2,
+    d3 int NOT NULL REFERENCES sj_d3
+);
+ANALYZE sj_f, sj_d1, sj_d2, sj_d3;
+
+-- With the collapse enabled (default), the resulting plan must be identical
+-- to the plan produced with the optimization disabled.
+SET enable_starjoin_ordering = on;
+EXPLAIN (COSTS OFF)
+SELECT * FROM sj_f
+  JOIN sj_d1 ON sj_f.d1 = sj_d1.id
+  JOIN sj_d2 ON sj_f.d2 = sj_d2.id
+  JOIN sj_d3 ON sj_f.d3 = sj_d3.id;
+
+SET enable_starjoin_ordering = off;
+EXPLAIN (COSTS OFF)
+SELECT * FROM sj_f
+  JOIN sj_d1 ON sj_f.d1 = sj_d1.id
+  JOIN sj_d2 ON sj_f.d2 = sj_d2.id
+  JOIN sj_d3 ON sj_f.d3 = sj_d3.id;
+
+RESET enable_starjoin_ordering;
+DROP TABLE sj_f, sj_d1, sj_d2, sj_d3;

---

From: Bruce Momjian <[email-masked]>
Date: Sat, 30 May 2026 14:18:35 -0400

> common? Probably not, but it seems unnecessarily risky.

Right.

> before we get to calculate join cardinalities.

Yes, I remember discussing that.

> If it would, refuse to create it, just like we do for various other join

This is how you avoid the factorial explosion of plan options, right?

> list of dimensions (which is the canonical join order).

Sorry, I got lost here.  What is "prefix?"  I looked at the patch and
also could not understand it.

> needed (e.g. to effectively join all dimensions at once, with no other

The patch is quite small.

>   dims   master(1)   master  sj/off    sj/on  master   sj/off   sj/on

Impressive.

-- 
  Bruce Momjian  <[email-masked]>        https://momjian.us
  EDB                                      https://enterprisedb.com

  Do not let urgent matters crowd out time for investment in the future.

---

From: Tomas Vondra <[email-masked]>
Date: Sat, 30 May 2026 20:57:20 +0200

> This is how you avoid the factorial explosion of plan options, right?

Yes, exactly.

> also could not understand it.

Apologies, it may not be obvious from the code / comments (I'll try to
improve that in the next version).

Let's say we're joining "F" with dimensions D1, D2, D3. Then the
starjoins_canonicalize() finds the cluster, and picks a canonical join
order. Could be [F, D1, D2, D3] - in this order. Or whatever other
permutation of the dimensions, it's all equal.

Then starjoin_order_invalid() ensures that whatever join relation we
produce, it only even contains a prefix of this list. So a join relation
can contain [F], [F, D1], [F, D1, D2], [F, D1, D2, D3]. But it can't
contain e.g. [F, D2], because that skips the D1 - it's not a prefix.

The patch only applies this to relations from the cluster. There can be
other relations in the join "in between" the dimensions - that does not
make the join order "invalid".

So for example there may be joins to non-dimensions A and B, and we will
consider joins [F, A, D1, B, D2, D3] and so on as valid. The joins to A
and B joins can increase/decrease cardinality, but thanks to this we
should find the right place to join the dimensions.

We could even make it a bit stricter, and require that all dimensions
join "at once". I.e. after joining a dimension, only dimensions can be
joined (until all dimensions are joined). So [F, D1, A, D2] would not be
allowed. This would further reduce the number of join orders considered.

> Impressive.

Indeed. I like how it fits into the existing approach. It's a bit like
having yet another "join order restriction".

regards

-- 
Tomas Vondra

---

From: Bruce Momjian <[email-masked]>
Date: Sat, 30 May 2026 16:16:11 -0400

> permutation of the dimensions, it's all equal.

Uh, are D1, D2, D3 in relid order at this point?

> contain e.g. [F, D2], because that skips the D1 - it's not a prefix.

Okay, prefix like a multi-column index prefix of columns.

> should find the right place to join the dimensions.

Okay, so if D1, D2, and D3 are all "cluster" joins then aren't they are
1:1, so why would you ever put something like B between them?  If B
reduces columns, it would be before the cluster, and if it expands them
it would be after cluster.  So if B is 1:1 too, in what cases might it
be better to join B between dimension joins?

> allowed. This would further reduce the number of join orders considered.

Right, I guess that is what I am asking above.

> having yet another "join order restriction".

This would be a big feature improvement for OLAP workloads.

---

From: Tomas Vondra <[email-masked]>
Date: Sat, 30 May 2026 23:16:21 +0200

> Uh, are D1, D2, D3 in relid order at this point?

I don't think the patch is explicitly enforcing relid order. It might be
using it indirectly due to how it walks the relations, but there's
nothing particularly special about relid order.

Right.

Right.

> Right, I guess that is what I am asking above.

You're right. It's simply not implemented.

> This would be a big feature improvement for OLAP workloads.

It would be helpful for many queries, yes. Although I want to point out
those queries usually do other stuff (other non-dimension joins, ...),
and actually process data (while the benchmark matches no rows in the
fact table, which amplifies the planning part). So in practice the
improvements would be smaller.

regards

-- 
Tomas Vondra

---

From: Robert Haas <[email-masked]>
Date: Mon, 1 Jun 2026 10:00:27 -0400

> order for each starjoin cluster we found (e.g. with dimensions in relid

I like the idea of trying to avoid considering a bunch of join orders
that are not meaningfully different from each other, but I think we're
only really guaranteed that two join orders are equivalent if both of
them are exactly one-to-one, with the row count neither increasing nor
decreasing. (Even then, it's not 100% equivalent, but probably close
enough.) I don't remember off-hand whether your definition of starjoin
also includes joins that can reduce the row count. If it does, then I
think we might need to be smarter than just putting the dimensions in
relid order. If it does not, then maybe we need to think about whether
the optimization is going to apply to a sufficiently broad range of
cases. Maybe it's fine: if a fact table is joined to lots of dimension
tables, then some of them might have restriction clauses but probably
many of them won't.

This is making me wonder whether we could improve on GEQO by
transforming it from a "plan this query" thing to a "restrict the join
order" thing. For instance, suppose we have two tables T1 and T2 and
we wonder whether swapping the order in which they are joined matters.
We pick a few random partial join orders of tables in the query
excluding T1 and T2 and then check whether appending T1 and then T2
produces significantly different results from appending T2 and then
T1. So for example say we pick (), (T3), (T3-T4), and (T5-T3). We then
test the cost/row count of T1-T2 vs. T2-T1, the cost/row count of
T3-T1-T2 vs. T3-T2-T1, similarly for T3-T4-T1-T2 vs. T3-T4-T2-T1,
similarly for T5-T3-T1-T2 vs. T5-T3-T2-T1. If we see that swapping the
order of T1 and T2 routinely has minimal effect on the outcome, then
it's probably safe to pick one or the other to be joined first and
disregard all the join orders where the two are swapped. By repeating
this kind of testing for various pairs of tables, we could possibly
prune the join search space for large join problems considerably, and
then still do an exhaustive test of the remaining join orders. Maybe
that would produce better results than GEQO currently does (or maybe
not).

Although I kind of like this idea and think it's interesting, it's
probably not going to be a good enough idea to compete with what
you're doing, because your idea is working even when the number of
dimensions is very small, and this seems like it would be a
significantly more expensive test. So the question is probably whether
there are cases where your cheaper test loses too much. I'm not sure
of the answer. My intuition is that join planning is pretty hard and
that shortcuts will tend to have cases where they behave really badly,
but my intuition is also that we are wasting a whole lot of CPU cycles
testing cases that are nearly equivalent to each other. I'm not sure
which of those two intuitions is more correct in this case.

---

From: Tomas Vondra <[email-masked]>
Date: Mon, 1 Jun 2026 17:35:16 +0200

On 6/1/26 16:00, Robert Haas wrote:
> relid order.

For the purpose of this optimization, the dimensions have to be 1:1
joins. There must not be any additional restrictions, it needs to be a
join on a FK, etc. So the relid order works fine.

> If it does not, then maybe we need to think about whether

In my experience it does apply to a significant number of queries, but
there's a selection bias (people don't talk to me about queries that
have no problems). Still, if the optimization costs virtually nothing, I
don't think that's a problem (we already do stuff like matching joins to
FK constraints anyway).

Also, I think there are ways to use this optimization to more queries.
For example it directly extends to snowflake joins - by adding "layers"
of dimensions, recursively. It's not such a massive benefit, because
snowflake joins have restrictions that substantially limit the search
space. But it would allow increasing join_collapse_limit.

The other idea is that Joel Jacobson's patch with KEY joins might allow
proving more joins are 1:1, not just joins on foreign keys. But I
haven't thought about that very much, and I'm not sure it's very useful
for such joins (it's probably not a starjoin-like query, and does not
have so many number of join orders).

> that would produce better results than GEQO currently does (or maybe

I'm not opposed to improving GEQO, but I don't think it's an alternative
to this optimization. It's still going to be a heuristics that skips
parts of the search space too early. 99.999% of deployments are not even
using GEQO for any queries.

The optimization helps a lot both in cases where GEQO is not applicable
(with fewer than geqo_threshold, and I doubt we want to lower that), and
in cases where GEQO is supposed to be helpful (i.e. it beats GEQO with
many joins).

So I think it's orthogonal, and it might even mean we don't need GEQO as
often. In any case, I see this as an orthogonal discussion. There's
already a thread discussing changes to GEQO, or replacing it with a new
heuristics.

> which of those two intuitions is more correct in this case.

Right, exactly. I agree this needs some testing how much overhead this
adds to large queries that don't benefit from it. I'll do that, but I
don't expect that to be an issue (because we already do the heavy work
of matching the FKeys already). It might require a smarter way to
represent the clusters or some other optimizations, of course.

regards

-- 
Tomas Vondra

---

From: "Joel Jacobson" <[email-masked]>
Date: Mon, 01 Jun 2026 18:20:48 +0200

> have so many number of join orders).

I find this thread very interesting, and like Tomas explained,
I'm interested in examining if there could possibly be an opportunity
for some shared infrastructure here.  I intend to conduct such research
in the upcoming weeks, and report back with my findings.

Just to clarify one thing; a key join is always backed by an underlying
foreign key (referential constraint). What I think Tomas means with
"not just joins on foreign keys" is that that key joins not only works
between two base tables, but also through derived tables.
To explain what that means, maybe an example is easiest,
a good one I recommend is: https://keyjoin.org/#sec7.3.1

/Joel