public inbox for [email protected]
help / color / mirror / Atom feedFrom: Chengpeng Yan <[email protected]>
To: Tomas Vondra <[email protected]>
Cc: [email protected] <[email protected]>
Cc: John Naylor <[email protected]>
Subject: Re: Add a greedy join search algorithm to handle large join problems
Date: Mon, 5 Jan 2026 04:15:25 +0000
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
<[email protected]>
Hi,
Recently, I have been testing the JOB dataset using three greedy
strategies: result_size, cost, and combined. The result_size and cost
strategies are the same heuristics previously tested on TPC-H with SF =
1.
The combined strategy runs GOO twice, once greedy by cost and once by
result_size, producing two complete candidate plans, and then selects
the one with the lower final estimated total_cost. This allows GOO to
compare plans generated under different greedy criteria.
In the attached files, v4-0001 is identical to the previously submitted
v3-0001 patch and contains the core GOO implementation. All
experiment-related changes are in v4-0002, which adds simple, test-only
support for evaluating different greedy strategies and will be
optimized. The v4_tests archive contains scripts for generating
v4_job.pdf (run_job.sh) and for collecting EXPLAIN ANALYZE results under
different greedy strategies (run_analysis.sh).
The detailed results are included in v4_job.pdf. The results report both
the measured execution times and their ratios relative to the DP
execution time, with color coding used to highlight outliers (<0.5 dark
green, 0.5–0.8 green, 1.2x-2x light red, 2x-10x red, 10+ dark red).
Looking more closely at JOB, only a subset of queries exceeds
PostgreSQL’s default geqo_threshold of 12 relations and therefore
exercises GEQO. This includes the 17-table queries (29a, 29b, 29c), the
14-table queries (28a, 28b, 28c, 33a, 33b, 33c), and the 12-table
queries (24a, 24b, 26a, 26b, 26c, 27a, 27b, 27c, 30a, 30b, 30c), for a
total of about 20 queries.
I therefore also extracted results for this GEQO-relevant subset from
the full JOB runs. The detailed results are included in
v4_job_geqo_range.pdf, derived directly from v4_job.pdf. On this subset,
GOO variants tend to show more favorable behavior overall, particularly
in terms of tail robustness.
For reproducibility, JOB was run using the same configuration as in the
previous experiments. The following commands were executed after loading
the data and before running the benchmarks.
Settings requiring a restart (e.g., shared_buffers) were applied via a
server restart prior to benchmarking; other settings were applied using
ALTER SYSTEM followed by pg_reload_conf().
```sql
VACUUM FREEZE ANALYZE;
CHECKPOINT;
ALTER SYSTEM SET join_collapse_limit = 100;
ALTER SYSTEM SET max_parallel_workers_per_gather = 0;
ALTER SYSTEM SET statement_timeout = 600000;
ALTER SYSTEM SET shared_buffers = '4GB';
ALTER SYSTEM SET effective_cache_size = '8GB';
ALTER SYSTEM SET work_mem = '1GB';
SELECT pg_reload_conf();
```
Full JOB results (ratio = algo / DP, lower is better):
Overall summary
algo n gmean p90 p95 max
---------------- --- ------ ------ ------ ------
GOO(combined) 113 0.953 1.94 3.15 8.68
GOO(result_size) 113 0.969 2.63 4.45 67.53
GEQO 113 1.066 1.50 2.06 16.81
GOO(cost) 113 1.496 5.80 16.20 431.32
Tail behavior
algo >=2x >=5x >=10x
---------------- ----- ----- ------
GOO(combined) 11 3 0
GOO(result_size) 18 5 2
GEQO 9 2 2
GOO(cost) 30 15 7
Workload sum (total execution time, ms)
algo total_ms ratio_to_dp
---------------- ------------ ------------
DP 115710.85 1.000
GOO(cost) 798600.41 6.902
GOO(result_size) 139100.42 1.202
GOO(combined) 154027.19 1.331
GEQO 173464.38 1.499
Observations:
* GOO(cost) shows severe tail behavior (max 431×, p99 327×), with many
bad cases.
* GOO(result_size) performs reasonably on average (gmean 0.969) but has
a poor tail (max 67×).
* GOO(combined) is the most robust variant: it achieves the best gmean
(0.953), shows no regressions ≥10×, and significantly reduces the worst
case (max 8.68×), trading some average workload time for improved tail
behavior.
* GEQO is generally slower on JOB (gmean 1.066) and also exhibits ≥10×
regressions (max 16.8×).
Conclusions:
1. All non-DP algorithms have cases that outperform DP, which typically
arise in situations where the cost estimates no longer reflect the
relative execution costs of alternative plans, often due to severe
cardinality misestimation. This patch set does not attempt to fix
cardinality estimation; instead, it focuses on reducing tail risk among
greedy plans under the existing cost model.
2. Based on the current JOB results, further tuning of a single greedy
heuristic is not the immediate priority: each single-strategy variant
still shows corner cases with large regressions. The next direction is
to reduce catastrophic plans (tail risk), rather than to optimize one
specific greedy criterion.
3. GOO(combined) improves robustness by reducing extreme regressions.
Increasing plan diversity via multiple greedy criteria appears
effective: different heuristics fail for different reasons, and the
combined variant selects the cheapest plan among candidates from
different greedy strategies, helping avoid extreme outliers with minimal
additional planning overhead.
Next, I include brief notes on a small set of representative JOB queries
to illustrate where greedy join ordering behaves relatively well or
poorly. Under severe cardinality misestimation, neither DP-based nor
heuristic approaches can reliably select good plans (“garbage in,
garbage out”); different algorithms simply exhibit different tolerances
to such errors. These examples document how specific join-ordering
choices interact with misestimation and help identify where the current
GOO implementation is more or less fragile.
For regressions, I focus on GOO(result_size) (12b, 3b, 11b) and
GOO(combined) (15a, 17b). I also include a few cases where
GOO(result_size) outperforms DP (29c, 31a). The full plan-level
analyses are in the attached v4_bad_case_analysis.txt and are optional
background; the summary points below are sufficient for the main
conclusions.
## GOO(result_size) bad case analysis
TL;DR:
* 12b: Estimation error misleads the greedy choice, causing a highly
selective predicate to be applied too late; with accurate estimates, the
regression can be avoided.
* 3b: An inherent weakness of result_size-based greediness, where small
estimated results hide expensive scans or repeated execution.
* 11b: Row count underestimation leads to a non-materialized NLJ with
repeated execution; accurate estimates or materialization / Hash Join
largely avoid the regression.
## GOO(combined) bad case analysis
GOO(combined) regressions mainly fall into two categories:
1. failures of the cost model itself (15a), and
2. cases where cost and result_size share the same structural weakness
(17b).
TL;DR:
* 15a: The selector chooses the cost-greedy plan due to lower estimated
cost, even though the result_size plan is much faster in reality. This
reflects cost model unreliability; in such cases, plan diversity
collapses back to a single fragile choice. This is an expected
limitation when both candidate plans depend on the same cost signal;
suggestions on improving plan diversity or adding lightweight safeguards
are welcome.
* 17b: Both greedy strategies converge to similarly bad plans (~3× DP),
indicating a structural limitation of greedy enumeration rather than a
selector issue.
## Representative cases where GOO(result_size) outperforms DP
In addition to regressions, I include a small number of cases where
greedy join ordering outperforms DP. These cases are not meant to
suggest that greedy ordering makes intrinsically better decisions, but
to illustrate different failure modes: avoiding fan-out amplification
under severe underestimation (29c, 31a).
TL;DR:
* 29c: Under severe cardinality underestimation, DP introduces early
fan-out, producing large intermediates and repeated inner execution.
GOO(result_size) starts from a highly selective predicate and avoids the
fan-out explosion.
* 31a: DP chooses an early multiplying join under severe
underestimation, causing row counts to explode. GOO(result_size) delays
the multiplying join until a more selective prefix is built.
## Discussion and next steps
On JOB, the combined variant behaves reasonably well overall: it reduces
extreme regressions compared to the single-heuristic variants, and looks
competitive with GEQO on aggregate measures. This does not show that it
is “good enough” in general, but it seems like a promising direction and
worth broader evaluation.
The results are clearly workload- and query-dependent. TPC-H and TPC-DS
provide limited coverage of scenarios where GEQO is exercised, while
JOB, as a commonly used and well-recognized benchmark, includes a subset
of queries that reflect cases where GEQO is actually used. That said,
JOB is still limited in overall join graph size. I therefore plan to
explore more complex workloads with larger join graphs and queries
involving more relations to better approximate real-world GEQO usage.
Suggestions for suitable workloads or query sets would be very welcome.
Evaluating plan quality in isolation is inherently difficult, since join
ordering is only one component of plan selection, alongside cardinality
estimation, operator costing, and other planner decisions. As seen on
JOB, even DP does not always produce the fastest plan, suggesting that
improvements in join ordering alone do not consistently translate into
end-to-end plan quality gains. This makes it less clear how such
improvements should be measured, or how average and tail behavior should
be weighed.
Planning time and memory usage, in contrast, follow more directly from
the algorithmic structure, and I plan to add explicit measurements for
them in future. Beyond plan quality, I am also interested in addressing
areas where GEQO is less satisfactory in practice, such as tunability
and graceful degradation (e.g., using DP up to a resource limit and
completing planning with a greedy step). Broader evaluation across
workloads should help clarify both aspects.
Given the current JOB results and the fact that this implementation
matches what seems to be a common baseline in industry systems and much
of the literature, my next step is to treat the current implementation
as a starting point and expand evaluation: more workloads and
configurations. I also plan to incorporate selectivity into the greedy
strategy and re-run the evaluations.
There is also a large body of academic work proposing additional
mechanisms to improve robustness. Many of these ideas do not seem to
have a clear “production” consensus, and few systems implement them, so
I would prefer to explore them incrementally based on evidence: first
establish behavior of the baseline across a wider range of tests, then
evaluate a small number of well-motivated improvments and measure their
impact.
--
Best regards,
Chengpeng Yan
This document provides detailed analyses of representative queries from
the JOB workload that illustrate both failure modes and success cases of
greedy join ordering (GOO).
These case studies are intended to complement the summary discussion in
the main email and are not required for understanding the overall
results.
## GOO(result_size) bad case analysis
TL;DR:
* 12b: Estimation error misleads the greedy choice, causing a highly
selective predicate to be applied too late; with accurate estimates, the
regression can be avoided.
* 3b: An inherent weakness of result_size-based greediness, where small
estimated results hide expensive scans or repeated execution.
* 11b: Row count underestimation leads to a non-materialized NLJ with
repeated execution; accurate estimates or materialization / Hash Join
largely avoid the regression.
Detailed analysis
* 12b: The regression occurs because a highly selective predicate is
applied too late. Due to estimation error, the optimizer fails to
recognize its selectivity and starts from a large table, forcing a
full sequential scan. The selective predicate is applied only as a
late join filter instead of an index condition. This highlights a risk
of result_size-based greediness: it may favor small estimated outputs
while ignoring the cost of scanning large inputs and the benefit of
early predicate application.
* 3b: The planner joins a very large table using a highly selective but
unindexed filter early. Although this yields a small intermediate
result, it requires a full scan of the large table and leads to
repeated rescans later. This is not mainly an estimation issue: even
with correct estimates, result_size-based greediness systematically
prefers small-but-expensive subplans because it ignores how the rows
are produced.
* 11b: The greedy strategy produces a very small intermediate result
early, but at the cost of building an expensive subplan and delaying the
(keyword -> movie_keyword) join. This causes that side to become a
parameterless inner of a Nested Loop join and be re-executed multiple
times. Cardinality underestimation prevents materialization or a switch
to Hash Join. Forcing materialization or Hash Join largely avoids the
regression, indicating a structural issue rather than a pure estimation
problem.
## GOO(combined) bad case analysis
GOO(combined) regressions mainly fall into two categories:
1. failures of the cost model itself (15a), and
2. cases where cost and result_size share the same structural weakness
(17b).
TL;DR:
* 15a: The selector chooses the cost-greedy plan due to lower estimated
cost, even though the result_size plan is much faster in reality. This
reflects cost model unreliability; in such cases, plan diversity
collapses back to a single fragile choice.
* 17b: Both greedy strategies converge to similarly bad plans (~3× DP),
indicating a structural limitation of greedy enumeration rather than a
selector issue.
Detailed analysis
* 15a: GOO(combined) selects the cost-greedy plan because it has a lower
estimated total_cost, while the result_size plan executes fastest. The
cost-based plan joins the many-to-many table movie_keyword too early,
inflating intermediate results and amplifying downstream work. The
root cause is cardinality underestimation (fanout and correlation) on
this join, which makes the plan appear cheap to the cost model but
expensive at execution time.
* 17b: Both greedy strategies perform poorly. The query forms a fan-out
star around movie_id, where locally attractive joins duplicate keys
early and force expensive downstream probes to be repeated many times.
This is a systematic limitation of myopic greedy join ordering: even
with accurate local estimates, a one-step objective cannot account for
fan-out–induced amplification of later work. As a result, both cost
and result_size fail for the same structural reason.
## Representative cases where GOO(result_size) outperforms DP
In addition to regressions, I include a small number of cases where
greedy join ordering outperforms DP. These cases are not meant to
suggest that greedy ordering makes intrinsically better decisions, but
to illustrate different failure modes: avoiding fan-out amplification
under severe underestimation (29c, 31a).
TL;DR:
* 29c: Under severe cardinality underestimation, DP introduces early
fan-out, producing large intermediates and repeated inner execution.
GOO(result_size) starts from a highly selective predicate and avoids the
fan-out explosion.
* 31a: DP chooses an early multiplying join under severe
underestimation, causing row counts to explode. GOO(result_size) delays
the multiplying join until a more selective prefix is built.
Detailed analysis:
* 29c: DP assumes an early join prefix is nearly singleton, but in
reality it produces a very large number of rows, leading to massive
fan-out and repeated inner scans/probes. Once execution enters a “many
loops × inner cost” regime, the error becomes catastrophic.
GOO(result_size) anchors the plan on a highly selective base predicate
and only expands after a small prefix is established, keeping
intermediate results small even under severe misestimation.
* 31a: This case exhibits a similar fan-out failure mode, but for a
different reason. DP treats an early join as nearly one-to-one when it
is actually high-multiplicity, causing rows to multiply much earlier
than expected. Unlike 29c, there is no single highly selective starting
predicate. GOO(result_size) still performs better by postponing the
multiplying join until after a more selective prefix is formed, so the
multiplicative effect applies to fewer rows.
Attachments:
[application/pdf] v4_job.pdf (32.4K, ../[email protected]/3-v4_job.pdf)
download
[application/pdf] v4_job_geqo_range.pdf (16.3K, ../[email protected]/4-v4_job_geqo_range.pdf)
download
[text/plain] v4_bad_case_analysis.txt (5.6K, ../[email protected]/5-v4_bad_case_analysis.txt)
download | inline:
This document provides detailed analyses of representative queries from
the JOB workload that illustrate both failure modes and success cases of
greedy join ordering (GOO).
These case studies are intended to complement the summary discussion in
the main email and are not required for understanding the overall
results.
## GOO(result_size) bad case analysis
TL;DR:
* 12b: Estimation error misleads the greedy choice, causing a highly
selective predicate to be applied too late; with accurate estimates, the
regression can be avoided.
* 3b: An inherent weakness of result_size-based greediness, where small
estimated results hide expensive scans or repeated execution.
* 11b: Row count underestimation leads to a non-materialized NLJ with
repeated execution; accurate estimates or materialization / Hash Join
largely avoid the regression.
Detailed analysis
* 12b: The regression occurs because a highly selective predicate is
applied too late. Due to estimation error, the optimizer fails to
recognize its selectivity and starts from a large table, forcing a
full sequential scan. The selective predicate is applied only as a
late join filter instead of an index condition. This highlights a risk
of result_size-based greediness: it may favor small estimated outputs
while ignoring the cost of scanning large inputs and the benefit of
early predicate application.
* 3b: The planner joins a very large table using a highly selective but
unindexed filter early. Although this yields a small intermediate
result, it requires a full scan of the large table and leads to
repeated rescans later. This is not mainly an estimation issue: even
with correct estimates, result_size-based greediness systematically
prefers small-but-expensive subplans because it ignores how the rows
are produced.
* 11b: The greedy strategy produces a very small intermediate result
early, but at the cost of building an expensive subplan and delaying the
(keyword -> movie_keyword) join. This causes that side to become a
parameterless inner of a Nested Loop join and be re-executed multiple
times. Cardinality underestimation prevents materialization or a switch
to Hash Join. Forcing materialization or Hash Join largely avoids the
regression, indicating a structural issue rather than a pure estimation
problem.
## GOO(combined) bad case analysis
GOO(combined) regressions mainly fall into two categories:
1. failures of the cost model itself (15a), and
2. cases where cost and result_size share the same structural weakness
(17b).
TL;DR:
* 15a: The selector chooses the cost-greedy plan due to lower estimated
cost, even though the result_size plan is much faster in reality. This
reflects cost model unreliability; in such cases, plan diversity
collapses back to a single fragile choice.
* 17b: Both greedy strategies converge to similarly bad plans (~3× DP),
indicating a structural limitation of greedy enumeration rather than a
selector issue.
Detailed analysis
* 15a: GOO(combined) selects the cost-greedy plan because it has a lower
estimated total_cost, while the result_size plan executes fastest. The
cost-based plan joins the many-to-many table movie_keyword too early,
inflating intermediate results and amplifying downstream work. The
root cause is cardinality underestimation (fanout and correlation) on
this join, which makes the plan appear cheap to the cost model but
expensive at execution time.
* 17b: Both greedy strategies perform poorly. The query forms a fan-out
star around movie_id, where locally attractive joins duplicate keys
early and force expensive downstream probes to be repeated many times.
This is a systematic limitation of myopic greedy join ordering: even
with accurate local estimates, a one-step objective cannot account for
fan-out–induced amplification of later work. As a result, both cost
and result_size fail for the same structural reason.
## Representative cases where GOO(result_size) outperforms DP
In addition to regressions, I include a small number of cases where
greedy join ordering outperforms DP. These cases are not meant to
suggest that greedy ordering makes intrinsically better decisions, but
to illustrate different failure modes: avoiding fan-out amplification
under severe underestimation (29c, 31a).
TL;DR:
* 29c: Under severe cardinality underestimation, DP introduces early
fan-out, producing large intermediates and repeated inner execution.
GOO(result_size) starts from a highly selective predicate and avoids the
fan-out explosion.
* 31a: DP chooses an early multiplying join under severe
underestimation, causing row counts to explode. GOO(result_size) delays
the multiplying join until a more selective prefix is built.
Detailed analysis:
* 29c: DP assumes an early join prefix is nearly singleton, but in
reality it produces a very large number of rows, leading to massive
fan-out and repeated inner scans/probes. Once execution enters a “many
loops × inner cost” regime, the error becomes catastrophic.
GOO(result_size) anchors the plan on a highly selective base predicate
and only expands after a small prefix is established, keeping
intermediate results small even under severe misestimation.
* 31a: This case exhibits a similar fan-out failure mode, but for a
different reason. DP treats an early join as nearly one-to-one when it
is actually high-multiplicity, causing rows to multiply much earlier
than expected. Unlike 29c, there is no single highly selective starting
predicate. GOO(result_size) still performs better by postponing the
multiplying join until after a more selective prefix is formed, so the
multiplicative effect applies to fewer rows.
[application/zip] v4_tests.zip (33.6K, ../[email protected]/6-v4_tests.zip)
download
[application/octet-stream] v4-0001-Add-GOO-Greedy-Operator-Ordering-join-sear.patch (63.5K, ../[email protected]/7-v4-0001-Add-GOO-Greedy-Operator-Ordering-join-sear.patch)
download | inline diff:
From 79c4d3fa7d83a24b3937ed2e4d5568bcb949e820 Mon Sep 17 00:00:00 2001
From: Chengpeng Yan <[email protected]>
Date: Wed, 10 Dec 2025 12:52:17 +0800
Subject: [PATCH v4 1/2] Add GOO (Greedy Operator Ordering) join search
as an alternative to GEQO
Introduce a greedy join search algorithm (GOO) to handle
large join problems. GOO builds join relations iteratively, maintaining
a list of clumps (join components) and committing to the cheapest
legal join at each step until only one clump remains.
Signed-off-by: Chengpeng Yan <[email protected]>
---
src/backend/optimizer/path/Makefile | 1 +
src/backend/optimizer/path/allpaths.c | 4 +
src/backend/optimizer/path/goo.c | 612 +++++++++++++++
src/backend/optimizer/path/meson.build | 1 +
src/backend/utils/misc/guc_parameters.dat | 9 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/goo.h | 23 +
src/include/optimizer/paths.h | 1 +
src/test/regress/expected/goo.out | 700 ++++++++++++++++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/parallel_schedule | 9 +-
src/test/regress/sql/goo.sql | 364 +++++++++
12 files changed, 1724 insertions(+), 4 deletions(-)
create mode 100644 src/backend/optimizer/path/goo.c
create mode 100644 src/include/optimizer/goo.h
create mode 100644 src/test/regress/expected/goo.out
create mode 100644 src/test/regress/sql/goo.sql
diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile
index 1e199ff66f7..3bc825cd845 100644
--- a/src/backend/optimizer/path/Makefile
+++ b/src/backend/optimizer/path/Makefile
@@ -17,6 +17,7 @@ OBJS = \
clausesel.o \
costsize.o \
equivclass.o \
+ goo.o \
indxpath.o \
joinpath.o \
joinrels.o \
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4c43fd0b19b..4574b1f44cc 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -35,6 +35,7 @@
#include "optimizer/clauses.h"
#include "optimizer/cost.h"
#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
@@ -3845,6 +3846,9 @@ make_rel_from_joinlist(PlannerInfo *root, List *joinlist)
if (join_search_hook)
return (*join_search_hook) (root, levels_needed, initial_rels);
+ /* WIP: for now use geqo_threshold for testing */
+ else if (enable_goo_join_search && levels_needed >= geqo_threshold)
+ return goo_join_search(root, levels_needed, initial_rels);
else if (enable_geqo && levels_needed >= geqo_threshold)
return geqo(root, levels_needed, initial_rels);
else
diff --git a/src/backend/optimizer/path/goo.c b/src/backend/optimizer/path/goo.c
new file mode 100644
index 00000000000..247dbb5f921
--- /dev/null
+++ b/src/backend/optimizer/path/goo.c
@@ -0,0 +1,612 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.c
+ * Greedy operator ordering (GOO) join search for large join problems
+ *
+ * GOO is a deterministic greedy operator ordering algorithm that constructs
+ * join relations iteratively, always committing to the cheapest legal join at
+ * each step. The algorithm maintains a list of "clumps" (join components),
+ * initially one per base relation. At each iteration, it evaluates all legal
+ * pairs of clumps, selects the pair that produces the cheapest join according
+ * to the planner's cost model, and replaces those two clumps with the
+ * resulting joinrel. This continues until only one clump remains.
+ *
+ * ALGORITHM COMPLEXITY:
+ *
+ * Time Complexity: O(n^3) where n is the number of base relations.
+ * - The algorithm performs (n - 1) iterations, merging two clumps each time.
+ * - At iteration i, there are (n - i + 1) remaining clumps, requiring
+ * O((n-i)^2) pair evaluations to find the cheapest join.
+ * - Total: Sum of (n-i)^2 for i=1 to n-1 ≈ O(n^3)
+ *
+ * REFERENCES:
+ *
+ * This implementation is based on the algorithm described in:
+ *
+ * Leonidas Fegaras, "A New Heuristic for Optimizing Large Queries",
+ * Proceedings of the 9th International Conference on Database and Expert
+ * Systems Applications (DEXA '98), August 1998, Pages 726-735.
+ * https://dl.acm.org/doi/10.5555/648311.754892
+ *
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/backend/optimizer/path/goo.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+
+#include "miscadmin.h"
+#include "nodes/bitmapset.h"
+#include "nodes/pathnodes.h"
+#include "optimizer/geqo.h"
+#include "optimizer/goo.h"
+#include "optimizer/joininfo.h"
+#include "optimizer/pathnode.h"
+#include "optimizer/paths.h"
+#include "utils/hsearch.h"
+#include "utils/memutils.h"
+
+/*
+ * Configuration defaults. These are exposed as GUCs in guc_tables.c.
+ */
+bool enable_goo_join_search = false;
+
+/*
+ * Working state for a single GOO search invocation.
+ *
+ * This structure holds all the state needed during a greedy join order search.
+ * It manages three memory contexts with different lifetimes to avoid memory
+ * bloat during large join searches.
+ *
+ * TODO: Consider using the extension_state mechanism in PlannerInfo (similar
+ * to GEQO's approach) instead of passing GooState separately.
+ */
+typedef struct GooState
+{
+ PlannerInfo *root; /* global planner state */
+ MemoryContext goo_cxt; /* long-lived (per-search) allocations */
+ MemoryContext cand_cxt; /* per-iteration candidate storage */
+ MemoryContext scratch_cxt; /* per-candidate speculative evaluation */
+ List *clumps; /* remaining join components (RelOptInfo *) */
+
+ /*
+ * "clumps" are similar to GEQO's concept (see geqo_eval.c): join
+ * components that haven't been merged yet. Initially one per base
+ * relation, gradually merged until one remains.
+ */
+ bool clause_pair_present; /* any clause-connected pair exists? */
+} GooState;
+
+/*
+ * Candidate join between two clumps.
+ *
+ * This structure holds the greedy metrics from a speculative joinrel
+ * evaluation. We create this lightweight structure in cand_cxt after discarding
+ * the actual joinrel from scratch_cxt, allowing us to compare many candidates
+ * without exhausting memory.
+ */
+typedef struct GooCandidate
+{
+ RelOptInfo *left; /* left input clump */
+ RelOptInfo *right; /* right input clump */
+ Cost total_cost; /* total cost of cheapest path */
+} GooCandidate;
+
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels);
+static void goo_destroy_state(GooState * state);
+static RelOptInfo *goo_search_internal(GooState * state);
+static void goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash);
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+static RelOptInfo *goo_commit_join(GooState * state, GooCandidate * cand);
+static bool goo_candidate_better(GooCandidate * a, GooCandidate * b);
+static bool goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right);
+
+/*
+ * goo_join_search
+ * Entry point for Greedy Operator Ordering join search algorithm.
+ *
+ * This function is called from make_rel_from_joinlist() when
+ * enable_goo_join_search is true and the number of relations meets or
+ * exceeds geqo_threshold.
+ *
+ * Returns the final RelOptInfo representing the join of all base relations,
+ * or errors out if no valid join order can be found.
+ */
+RelOptInfo *
+goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels)
+{
+ GooState *state;
+ RelOptInfo *result;
+ int base_rel_count;
+ struct HTAB *base_hash;
+
+ /* Initialize search state and memory contexts */
+ state = goo_init_state(root, initial_rels);
+
+ /*
+ * Save initial state of join_rel_list and join_rel_hash so we can restore
+ * them if the search fails.
+ */
+ base_rel_count = list_length(root->join_rel_list);
+ base_hash = root->join_rel_hash;
+
+ /* Run the main greedy search loop */
+ result = goo_search_internal(state);
+
+ if (result == NULL)
+ {
+ /* Restore planner state before reporting error */
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+ elog(ERROR, "GOO join search failed to find a valid join order");
+ }
+
+ goo_destroy_state(state);
+ return result;
+}
+
+/*
+ * goo_init_state
+ * Initialize per-search state and memory contexts.
+ *
+ * Creates the GooState structure and three memory contexts with different
+ * lifetimes:
+ *
+ * - goo_cxt: Lives for the entire search, holds the clumps list and state.
+ * - cand_cxt: Reset after each iteration, holds candidate structures during
+ * the comparison phase.
+ * - scratch_cxt: Reset after each candidate evaluation, holds speculative
+ * joinrels that are discarded before committing to a choice.
+ *
+ * The three-context design prevents memory bloat during large join searches
+ * where we may evaluate hundreds or thousands of candidate joins.
+ */
+static GooState * goo_init_state(PlannerInfo *root, List *initial_rels)
+{
+ MemoryContext oldcxt;
+ GooState *state;
+
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ state = palloc(sizeof(GooState));
+ state->root = root;
+ state->clumps = NIL;
+ state->clause_pair_present = false;
+
+ /* Create the three-level memory context hierarchy */
+ state->goo_cxt = AllocSetContextCreate(root->planner_cxt, "GOOStateContext",
+ ALLOCSET_DEFAULT_SIZES);
+ state->cand_cxt = AllocSetContextCreate(state->goo_cxt, "GOOCandidateContext",
+ ALLOCSET_SMALL_SIZES);
+ state->scratch_cxt = AllocSetContextCreate(
+ state->goo_cxt, "GOOScratchContext", ALLOCSET_SMALL_SIZES);
+
+ /*
+ * Copy the initial_rels list into goo_cxt. This becomes our working
+ * clumps list that we'll modify throughout the search.
+ */
+ MemoryContextSwitchTo(state->goo_cxt);
+ state->clumps = list_copy(initial_rels);
+
+ MemoryContextSwitchTo(oldcxt);
+
+ return state;
+}
+
+/*
+ * goo_destroy_state
+ * Free all memory allocated for the GOO search.
+ *
+ * Deletes the goo_cxt memory context (which recursively deletes cand_cxt
+ * and scratch_cxt as children) and then frees the state structure itself.
+ * This is called after the search completes successfully or fails.
+ */
+static void
+goo_destroy_state(GooState * state)
+{
+ MemoryContextDelete(state->goo_cxt);
+ pfree(state);
+}
+
+/*
+ * goo_search_internal
+ * Main greedy search loop.
+ *
+ * Implements a two-pass algorithm at each iteration:
+ *
+ * Pass 1: Scan all clump pairs to detect whether any clause-connected pairs
+ * exist. This sets the clause_pair_present flag.
+ *
+ * Pass 2: Evaluate all viable candidate pairs, keeping track of the best one
+ * according to our comparison criteria. If clause_pair_present is true,
+ * we skip Cartesian products entirely to avoid expensive cross joins.
+ *
+ * After selecting the best candidate, we permanently create its joinrel in
+ * planner_cxt and replace the two input clumps with this new joinrel. This
+ * continues until only one clump remains.
+ *
+ * The function runs primarily in goo_cxt, temporarily switching to planner_cxt
+ * when creating permanent joinrels and to scratch_cxt when evaluating
+ * speculative candidates.
+ *
+ * Returns the final joinrel spanning all base relations, or NULL on failure.
+ */
+static RelOptInfo *
+goo_search_internal(GooState * state)
+{
+ PlannerInfo *root = state->root;
+ RelOptInfo *final_rel = NULL;
+ MemoryContext oldcxt;
+
+ /*
+ * Switch to goo_cxt for the entire search process. This ensures that all
+ * operations on state->clumps and related structures happen in the
+ * correct memory context.
+ */
+ oldcxt = MemoryContextSwitchTo(state->goo_cxt);
+
+ while (list_length(state->clumps) > 1)
+ {
+ ListCell *lc1;
+ int i;
+ GooCandidate *best_candidate = NULL;
+
+ /* Allow query cancellation during long join searches */
+ CHECK_FOR_INTERRUPTS();
+
+ /* Reset candidate context for this iteration */
+ MemoryContextReset(state->cand_cxt);
+ state->clause_pair_present = false;
+
+ /*
+ * Pass 1: Scan all pairs to detect clause-connected joins.
+ *
+ * We need to know whether ANY clause-connected pairs exist before we
+ * can decide whether to skip Cartesian products. This quick scan
+ * allows us to prefer well-connected joins without completely
+ * forbidding Cartesian products (which may be necessary for
+ * disconnected query graphs).
+ */
+ for (i = 0, lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1), i++)
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+
+ /* Check if this pair has a join clause or order restriction */
+ if (have_relevant_joinclause(root, left, right) ||
+ have_join_order_restriction(root, left, right))
+ {
+ /* Found at least one clause-connected pair */
+ state->clause_pair_present = true;
+ break;
+ }
+ }
+
+ if (state->clause_pair_present)
+ break;
+ }
+
+ /*
+ * Pass 2: Evaluate all viable candidate pairs and select the best.
+ *
+ * For each pair that passes the pruning check, we do a full
+ * speculative evaluation using make_join_rel() to get accurate costs.
+ * The candidate with the best cost (according to
+ * goo_candidate_better) is remembered and will be committed after
+ * this pass.
+ *
+ * TODO: It might be worth caching cost estimates if the same join
+ * pair appears in multiple iterations.
+ */
+ for (lc1 = list_head(state->clumps); lc1 != NULL;
+ lc1 = lnext(state->clumps, lc1))
+ {
+ RelOptInfo *left = lfirst_node(RelOptInfo, lc1);
+ ListCell *lc2 = lnext(state->clumps, lc1);
+
+ for (; lc2 != NULL; lc2 = lnext(state->clumps, lc2))
+ {
+ RelOptInfo *right = lfirst_node(RelOptInfo, lc2);
+ GooCandidate *cand;
+
+ cand = goo_build_candidate(state, left, right);
+ if (cand == NULL)
+ continue;
+
+ /* Track the best candidate seen so far */
+ if (best_candidate == NULL ||
+ goo_candidate_better(cand, best_candidate))
+ best_candidate = cand;
+ }
+ }
+
+ /* We must have at least one valid join candidate */
+ if (best_candidate == NULL)
+ elog(ERROR, "GOO join search failed to find any valid join candidates");
+
+ /*
+ * Commit the best candidate: create the joinrel permanently and
+ * update the clumps list.
+ */
+ final_rel = goo_commit_join(state, best_candidate);
+
+ if (final_rel == NULL)
+ elog(ERROR, "GOO join search failed to commit join");
+ }
+
+ /* Switch back to the original context before returning */
+ MemoryContextSwitchTo(oldcxt);
+
+ return final_rel;
+}
+
+/*
+ * goo_candidate_prunable
+ * Determine whether a candidate pair should be skipped.
+ *
+ * We use a two-level pruning strategy:
+ *
+ * 1. Pairs with join clauses or join-order restrictions are never prunable.
+ * These represent natural joins or required join orders (e.g., from outer
+ * joins or LATERAL references).
+ *
+ * 2. If clause_pair_present is true (meaning at least one clause-connected
+ * pair exists in this iteration), we prune Cartesian products to avoid
+ * evaluating expensive cross joins when better options are available.
+ *
+ * However, if NO clause-connected pairs exist in an iteration, we allow
+ * Cartesian products to be considered. This ensures we can always make
+ * progress even with disconnected query graphs.
+ *
+ * Returns true if the pair should be pruned (skipped), false otherwise.
+ */
+static bool
+goo_candidate_prunable(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ bool has_clause = have_relevant_joinclause(root, left, right);
+ bool has_restriction = have_join_order_restriction(root, left, right);
+
+ if (has_clause || has_restriction)
+ return false; /* never prune clause-connected joins */
+
+ return state->clause_pair_present;
+}
+
+/*
+ * goo_build_candidate
+ * Evaluate a potential join between two clumps and return a candidate.
+ *
+ * This function performs a speculative join evaluation to extract greedy metrics
+ * without permanently creating the joinrel. The process is:
+ *
+ * 1. Check basic viability (pruning, overlapping relids).
+ * 2. Switch to scratch_cxt and create the joinrel using make_join_rel().
+ * 3. Generate paths (including partitionwise and parallel variants).
+ * 4. Extract the greedy metrics from the cheapest path.
+ * 5. Discard the joinrel by calling goo_reset_probe_state().
+ * 6. Create a lightweight GooCandidate in cand_cxt with the extracted metrics.
+ *
+ * This evaluate-and-discard pattern prevents memory bloat when evaluating
+ * many candidates. The winning candidate will be rebuilt permanently later
+ * by goo_commit_join().
+ *
+ * Returns a GooCandidate structure, or NULL if the join is illegal or
+ * overlapping. Assumes the caller is in goo_cxt.
+ */
+static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
+ RelOptInfo *right)
+{
+ PlannerInfo *root = state->root;
+ MemoryContext oldcxt;
+ int saved_rel_len;
+ struct HTAB *saved_hash;
+ RelOptInfo *joinrel;
+ Cost total_cost;
+ GooCandidate *cand;
+
+ /* Skip if this pair should be pruned */
+ if (goo_candidate_prunable(state, left, right))
+ return NULL;
+
+ /* Sanity check: ensure the clumps don't overlap */
+ if (bms_overlap(left->relids, right->relids))
+ return NULL;
+
+ /*
+ * Save state before speculative join evaluation. We'll create the joinrel
+ * in scratch_cxt and then discard it.
+ */
+ saved_rel_len = list_length(root->join_rel_list);
+ saved_hash = root->join_rel_hash;
+
+ /* Switch to scratch_cxt for speculative joinrel creation */
+ oldcxt = MemoryContextSwitchTo(state->scratch_cxt);
+
+ /*
+ * Temporarily disable join_rel_hash so make_join_rel() doesn't find or
+ * cache this speculative joinrel.
+ */
+ root->join_rel_hash = NULL;
+
+ /*
+ * Create the joinrel and generate all its paths.
+ *
+ * TODO: This is the most expensive part of GOO. Each candidate evaluation
+ * performs full path generation via make_join_rel().
+ */
+ joinrel = make_join_rel(root, left, right);
+
+ if (joinrel == NULL)
+ {
+ /* Invalid or illegal join, clean up and return NULL */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+ return NULL;
+ }
+
+ bool is_top_rel = bms_equal(joinrel->relids, root->all_query_rels);
+
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!is_top_rel)
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+
+ if (joinrel->grouped_rel != NULL && !is_top_rel)
+ {
+ RelOptInfo *grouped_rel = joinrel->grouped_rel;
+
+ Assert(IS_GROUPED_REL(grouped_rel));
+
+ generate_grouped_paths(root, grouped_rel, joinrel);
+ set_cheapest(grouped_rel);
+ }
+
+ total_cost = joinrel->cheapest_total_path->total_cost;
+
+ /*
+ * Switch back to goo_cxt and discard the speculative joinrel.
+ * goo_reset_probe_state() will clean up join_rel_list, join_rel_hash, and
+ * reset scratch_cxt to free all the joinrel's memory.
+ */
+ MemoryContextSwitchTo(oldcxt);
+ goo_reset_probe_state(state, saved_rel_len, saved_hash);
+
+ /*
+ * Now create the candidate structure in cand_cxt. This will survive until
+ * the end of this iteration (when cand_cxt is reset).
+ */
+ oldcxt = MemoryContextSwitchTo(state->cand_cxt);
+ cand = palloc(sizeof(GooCandidate));
+ cand->left = left;
+ cand->right = right;
+ cand->total_cost = total_cost;
+ MemoryContextSwitchTo(oldcxt);
+
+ return cand;
+}
+
+/*
+ * goo_reset_probe_state
+ * Clean up after a speculative joinrel evaluation.
+ *
+ * Reverts the planner's join_rel_list and join_rel_hash to their saved state,
+ * removing any joinrels that were created during speculative evaluation.
+ * Also resets scratch_cxt to free all memory used by the discarded joinrel
+ * and its paths.
+ *
+ * This function is called after extracting cost metrics from a speculative
+ * joinrel that we don't want to keep.
+ */
+static void
+goo_reset_probe_state(GooState * state, int saved_rel_len,
+ struct HTAB *saved_hash)
+{
+ PlannerInfo *root = state->root;
+
+ /* Remove speculative joinrels from the planner's lists */
+ root->join_rel_list = list_truncate(root->join_rel_list, saved_rel_len);
+ root->join_rel_hash = saved_hash;
+
+ /* Free all memory used during speculative evaluation */
+ MemoryContextReset(state->scratch_cxt);
+}
+
+/*
+ * goo_commit_join
+ * Permanently create the chosen join and update the clumps list.
+ *
+ * After selecting the best candidate in an iteration, we need to permanently
+ * create its joinrel (with all paths) and integrate it into the planner state.
+ * This function:
+ *
+ * 1. Switches to planner_cxt and creates the joinrel using make_join_rel().
+ * Unlike the speculative evaluation, this joinrel is kept permanently.
+ * 2. Generates partitionwise and parallel path variants.
+ * 3. Determines the cheapest paths.
+ * 4. Updates state->clumps by removing the two input clumps and adding the
+ * new joinrel as a single clump.
+ *
+ * The next iteration will treat this joinrel as an atomic unit that can be
+ * joined with other remaining clumps.
+ *
+ * Returns the newly created joinrel. Assumes the caller is in goo_cxt.
+ */
+static RelOptInfo *
+goo_commit_join(GooState * state, GooCandidate * cand)
+{
+ MemoryContext oldcxt;
+ PlannerInfo *root = state->root;
+ RelOptInfo *joinrel;
+
+ /*
+ * Create the joinrel permanently in planner_cxt. Unlike the speculative
+ * evaluation in goo_build_candidate(), this joinrel will be kept and
+ * added to root->join_rel_list for use by the rest of the planner.
+ */
+ oldcxt = MemoryContextSwitchTo(root->planner_cxt);
+
+ joinrel = make_join_rel(root, cand->left, cand->right);
+ if (joinrel == NULL)
+ {
+ MemoryContextSwitchTo(oldcxt);
+ elog(ERROR, "GOO join search failed to create join relation");
+ }
+
+ /* Generate additional path variants, just like standard_join_search() */
+ bool is_top_rel = bms_equal(joinrel->relids, root->all_query_rels);
+
+ generate_partitionwise_join_paths(root, joinrel);
+ if (!is_top_rel)
+ generate_useful_gather_paths(root, joinrel, false);
+ set_cheapest(joinrel);
+
+ if (joinrel->grouped_rel != NULL && !is_top_rel)
+ {
+ RelOptInfo *grouped_rel = joinrel->grouped_rel;
+
+ Assert(IS_GROUPED_REL(grouped_rel));
+
+ generate_grouped_paths(root, grouped_rel, joinrel);
+ set_cheapest(grouped_rel);
+ }
+
+ /*
+ * Switch back to goo_cxt and update the clumps list. Remove the two input
+ * clumps and add the new joinrel as a single clump.
+ */
+ MemoryContextSwitchTo(oldcxt);
+
+ state->clumps = list_delete_ptr(state->clumps, cand->left);
+ state->clumps = list_delete_ptr(state->clumps, cand->right);
+ state->clumps = lappend(state->clumps, joinrel);
+
+ return joinrel;
+}
+
+/*
+ * goo_candidate_better
+ * Compare two join candidates and determine which is better.
+ *
+ * Returns true if candidate 'a' should be preferred over candidate 'b'.
+ */
+static bool
+goo_candidate_better(GooCandidate * a, GooCandidate * b)
+{
+ return (a->total_cost < b->total_cost);
+}
diff --git a/src/backend/optimizer/path/meson.build b/src/backend/optimizer/path/meson.build
index 12f36d85cb6..e5046365a37 100644
--- a/src/backend/optimizer/path/meson.build
+++ b/src/backend/optimizer/path/meson.build
@@ -5,6 +5,7 @@ backend_sources += files(
'clausesel.c',
'costsize.c',
'equivclass.c',
+ 'goo.c',
'indxpath.c',
'joinpath.c',
'joinrels.c',
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index 3b9d8349078..a8ce31ab8a7 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -840,6 +840,15 @@
boot_val => 'true',
},
+/* WIP: for now keep this in QUERY_TUNING_GEQO group for testing convenience */
+{ name => 'enable_goo_join_search', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_GEQO',
+ short_desc => 'Enables the planner\'s use of GOO join search for large join problems.',
+ long_desc => 'Greedy Operator Ordering (GOO) is a deterministic join search algorithm for queries with many relations.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'enable_goo_join_search',
+ boot_val => 'false',
+},
+
{ name => 'enable_group_by_reordering', type => 'bool', context => 'PGC_USERSET', group => 'QUERY_TUNING_METHOD',
short_desc => 'Enables reordering of GROUP BY keys.',
flags => 'GUC_EXPLAIN',
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index dc9e2255f8a..8284e8b1da7 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -456,6 +456,7 @@
# - Genetic Query Optimizer -
#geqo = on
+#enable_goo_join_search = off
#geqo_threshold = 12
#geqo_effort = 5 # range 1-10
#geqo_pool_size = 0 # selects default based on effort
diff --git a/src/include/optimizer/goo.h b/src/include/optimizer/goo.h
new file mode 100644
index 00000000000..0080dfa2ac8
--- /dev/null
+++ b/src/include/optimizer/goo.h
@@ -0,0 +1,23 @@
+/*-------------------------------------------------------------------------
+ *
+ * goo.h
+ * prototype for the greedy operator ordering join search
+ *
+ * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1994, Regents of the University of California
+ *
+ * IDENTIFICATION
+ * src/include/optimizer/goo.h
+ *
+ *-------------------------------------------------------------------------
+ */
+#ifndef GOO_H
+#define GOO_H
+
+#include "nodes/pathnodes.h"
+#include "nodes/pg_list.h"
+
+extern RelOptInfo *goo_join_search(PlannerInfo *root, int levels_needed,
+ List *initial_rels);
+
+#endif /* GOO_H */
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index f6a62df0b43..5b3ebe5f1d2 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -21,6 +21,7 @@
* allpaths.c
*/
extern PGDLLIMPORT bool enable_geqo;
+extern PGDLLIMPORT bool enable_goo_join_search;
extern PGDLLIMPORT bool enable_eager_aggregate;
extern PGDLLIMPORT int geqo_threshold;
extern PGDLLIMPORT double min_eager_agg_group_size;
diff --git a/src/test/regress/expected/goo.out b/src/test/regress/expected/goo.out
new file mode 100644
index 00000000000..0b41634c968
--- /dev/null
+++ b/src/test/regress/expected/goo.out
@@ -0,0 +1,700 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+ANALYZE;
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ QUERY PLAN
+----------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_2".column1)
+ -> Hash Join
+ Hash Cond: ("*VALUES*".column1 = "*VALUES*_1".column1)
+ -> Values Scan on "*VALUES*"
+ -> Hash
+ -> Values Scan on "*VALUES*_1"
+ -> Hash
+ -> Values Scan on "*VALUES*_2"
+(10 rows)
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ QUERY PLAN
+-------------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t5
+ Filter: (f = 3)
+ -> Nested Loop
+ -> Seq Scan on t1
+ Filter: (a = 1)
+ -> Seq Scan on t2
+ Filter: (c = 2)
+(9 rows)
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+ count
+-------
+ 1
+(1 row)
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+ QUERY PLAN
+---------------------------------------------------------------------------
+ Aggregate
+ -> Nested Loop
+ Join Filter: (fact.dim4_id = dim4.id)
+ -> Hash Join
+ Hash Cond: (dim3.id = fact.dim3_id)
+ -> Seq Scan on dim3
+ -> Hash
+ -> Hash Join
+ Hash Cond: (dim2.id = fact.dim2_id)
+ -> Seq Scan on dim2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (fact.dim1_id = dim1.id)
+ -> Seq Scan on fact
+ -> Hash
+ -> Seq Scan on dim1
+ Filter: (id < 5)
+ -> Seq Scan on dim4
+(18 rows)
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ QUERY PLAN
+----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t3.b = t1.b)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t15
+(58 rows)
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t1.a = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Hash Join
+ Hash Cond: (t3.b = t4.c)
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+-- Results should match
+EXECUTE goo_plan;
+ count
+-------
+ 10
+(1 row)
+
+EXECUTE standard_plan;
+ count
+-------
+ 10
+(1 row)
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+ QUERY PLAN
+----------------------------------------------------------------------------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t16.q = t18.q)
+ -> Hash Join
+ Hash Cond: (t15.p = t17.p)
+ -> Hash Join
+ Hash Cond: (t14.o = t16.o)
+ -> Hash Join
+ Hash Cond: (t13.n = t15.n)
+ -> Hash Join
+ Hash Cond: (t12.m = t14.m)
+ -> Hash Join
+ Hash Cond: (t11.l = t13.l)
+ -> Hash Join
+ Hash Cond: (t10.k = t12.k)
+ -> Hash Join
+ Hash Cond: (t9.j = t11.j)
+ -> Hash Join
+ Hash Cond: (t8.i = t10.i)
+ -> Hash Join
+ Hash Cond: (t7.h = t9.h)
+ -> Hash Join
+ Hash Cond: (t6.g = t8.g)
+ -> Hash Join
+ Hash Cond: (t5.f = t7.f)
+ -> Hash Join
+ Hash Cond: (t4.e = t6.e)
+ -> Hash Join
+ Hash Cond: (t3.d = t5.d)
+ -> Hash Join
+ Hash Cond: (t2.c = t4.c)
+ -> Hash Join
+ Hash Cond: (t1.b = t3.b)
+ -> Hash Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+ -> Hash
+ -> Seq Scan on t5
+ -> Hash
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t7
+ -> Hash
+ -> Seq Scan on t8
+ -> Hash
+ -> Seq Scan on t9
+ -> Hash
+ -> Seq Scan on t10
+ -> Hash
+ -> Seq Scan on t11
+ -> Hash
+ -> Seq Scan on t12
+ -> Hash
+ -> Seq Scan on t13
+ -> Hash
+ -> Seq Scan on t14
+ -> Hash
+ -> Seq Scan on t15
+ -> Hash
+ -> Seq Scan on t16
+ -> Hash
+ -> Seq Scan on t17
+ -> Hash
+ -> Seq Scan on t18
+(70 rows)
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+ QUERY PLAN
+-------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (t2.a = t1.a)
+ -> Seq Scan on t2
+ -> Hash
+ -> Nested Loop
+ -> Hash Join
+ Hash Cond: (t6.e = t5.f)
+ -> Seq Scan on t6
+ -> Hash
+ -> Seq Scan on t5
+ Filter: (d < 3)
+ -> Seq Scan on t1
+ Filter: (a < 5)
+(14 rows)
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+ QUERY PLAN
+----------------------------------------------
+ Aggregate
+ -> Hash Left Join
+ Hash Cond: (t3.d = t4.c)
+ -> Hash Left Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Left Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+ -> Hash
+ -> Seq Scan on t4
+(14 rows)
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+ QUERY PLAN
+----------------------------------
+ Aggregate
+ -> Nested Loop
+ -> Seq Scan on t1
+ -> Materialize
+ -> Seq Scan on t2
+(5 rows)
+
+SELECT count(*)
+FROM t1, t2;
+ count
+-------
+ 100
+(1 row)
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+ QUERY PLAN
+----------------------------------------
+ Aggregate
+ -> Hash Full Join
+ Hash Cond: (t2.a = t3.b)
+ -> Hash Full Join
+ Hash Cond: (t1.a = t2.a)
+ -> Seq Scan on t1
+ -> Hash
+ -> Seq Scan on t2
+ -> Hash
+ -> Seq Scan on t3
+(10 rows)
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+ QUERY PLAN
+------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (b.b = c.c)
+ -> Hash Join
+ Hash Cond: (a.a = b.a)
+ -> Seq Scan on t1 a
+ -> Hash
+ -> Seq Scan on t1 b
+ -> Hash
+ -> Seq Scan on t2 c
+(10 rows)
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+ANALYZE;
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+ QUERY PLAN
+-----------------------------------------------------------------
+ Aggregate
+ -> Hash Join
+ Hash Cond: (chain1a.val = chain2a.id)
+ -> Hash Join
+ Hash Cond: (chain1b.val = chain1c.id)
+ -> Hash Join
+ Hash Cond: (chain1a.id = chain1b.id)
+ -> Seq Scan on chain1a
+ -> Hash
+ -> Seq Scan on chain1b
+ -> Hash
+ -> Seq Scan on chain1c
+ -> Hash
+ -> Hash Join
+ Hash Cond: (chain2b.val = chain2c.id)
+ -> Hash Join
+ Hash Cond: (chain2a.val = chain2b.id)
+ -> Seq Scan on chain2a
+ -> Hash
+ -> Seq Scan on chain2b
+ -> Hash
+ -> Seq Scan on chain2c
+(22 rows)
+
+--
+-- Eager aggregation with GOO join search
+-- Ensure grouped_rel handling when eager aggregation is enabled.
+--
+SET enable_eager_aggregate = on;
+SET min_eager_agg_group_size = 0;
+CREATE TEMP TABLE center_tbl (id int PRIMARY KEY);
+CREATE TEMP TABLE arm1_tbl (center_id int, payload int);
+CREATE TEMP TABLE arm2_tbl (center_id int, payload int);
+INSERT INTO center_tbl SELECT i FROM generate_series(1, 10) i;
+INSERT INTO arm1_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+INSERT INTO arm2_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+ANALYZE center_tbl;
+ANALYZE arm1_tbl;
+ANALYZE arm2_tbl;
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+ QUERY PLAN
+----------------------------------------------------------
+ HashAggregate
+ Output: c.id, count(*)
+ Group Key: c.id
+ -> Hash Join
+ Output: c.id
+ Hash Cond: (c.id = a2.center_id)
+ -> Hash Join
+ Output: c.id, a1.center_id
+ Inner Unique: true
+ Hash Cond: (a1.center_id = c.id)
+ -> Seq Scan on pg_temp.arm1_tbl a1
+ Output: a1.center_id, a1.payload
+ -> Hash
+ Output: c.id
+ -> Seq Scan on pg_temp.center_tbl c
+ Output: c.id
+ -> Hash
+ Output: a2.center_id
+ -> Seq Scan on pg_temp.arm2_tbl a2
+ Output: a2.center_id
+(20 rows)
+
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+ id | count
+----+-------
+ 8 | 10000
+ 10 | 10000
+ 9 | 10000
+ 7 | 10000
+ 1 | 10000
+ 5 | 10000
+ 4 | 10000
+ 2 | 10000
+ 6 | 10000
+ 3 | 10000
+(10 rows)
+
+RESET min_eager_agg_group_size;
+RESET enable_eager_aggregate;
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+RESET geqo_threshold;
+RESET enable_goo_join_search;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 3b37fafa65b..cb0c84cebff 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -153,6 +153,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_distinct_reordering | on
enable_eager_aggregate | on
enable_gathermerge | on
+ enable_goo_join_search | off
enable_group_by_reordering | on
enable_hashagg | on
enable_hashjoin | on
@@ -173,7 +174,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | 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/parallel_schedule b/src/test/regress/parallel_schedule
index cc6d799bcea..14e3a475906 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -68,6 +68,12 @@ test: select_into select_distinct select_distinct_on select_implicit select_havi
# ----------
test: brin gin gist spgist privileges init_privs security_label collate matview lock replica_identity rowsecurity object_address tablesample groupingsets drop_operator password identity generated_stored join_hash
+# ----------
+# Additional JOIN ORDER tests
+# WIP: need to find an appropriate group for this test
+# ----------
+test: goo
+
# ----------
# Additional BRIN tests
# ----------
@@ -98,9 +104,6 @@ test: maintain_every
# no relation related tests can be put in this group
test: publication subscription
-# ----------
-# Another group of parallel tests
-# select_views depends on create_view
# ----------
test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combocid tsearch tsdicts foreign_data window xmlmap functional_deps advisory_lock indirect_toast equivclass stats_rewrite
diff --git a/src/test/regress/sql/goo.sql b/src/test/regress/sql/goo.sql
new file mode 100644
index 00000000000..ab048d8e34e
--- /dev/null
+++ b/src/test/regress/sql/goo.sql
@@ -0,0 +1,364 @@
+--
+-- GOO (Greedy Operator Ordering) Join Search Tests
+--
+-- This test suite validates the GOO join ordering algorithm and verifies
+-- correct behavior for various query patterns.
+--
+
+-- Create test tables with various sizes and join patterns
+CREATE TEMP TABLE t1 (a int, b int);
+CREATE TEMP TABLE t2 (a int, c int);
+CREATE TEMP TABLE t3 (b int, d int);
+CREATE TEMP TABLE t4 (c int, e int);
+CREATE TEMP TABLE t5 (d int, f int);
+CREATE TEMP TABLE t6 (e int, g int);
+CREATE TEMP TABLE t7 (f int, h int);
+CREATE TEMP TABLE t8 (g int, i int);
+CREATE TEMP TABLE t9 (h int, j int);
+CREATE TEMP TABLE t10 (i int, k int);
+CREATE TEMP TABLE t11 (j int, l int);
+CREATE TEMP TABLE t12 (k int, m int);
+CREATE TEMP TABLE t13 (l int, n int);
+CREATE TEMP TABLE t14 (m int, o int);
+CREATE TEMP TABLE t15 (n int, p int);
+CREATE TEMP TABLE t16 (o int, q int);
+CREATE TEMP TABLE t17 (p int, r int);
+CREATE TEMP TABLE t18 (q int, s int);
+
+-- Populate with small amount of data
+INSERT INTO t1 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t2 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t3 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t4 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t5 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t6 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t7 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t8 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t9 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t10 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t11 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t12 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t13 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t14 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t15 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t16 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t17 SELECT i, i FROM generate_series(1,10) i;
+INSERT INTO t18 SELECT i, i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+--
+-- Basic 3-way join (sanity check)
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+SELECT count(*)
+FROM (VALUES (1),(2)) AS a(x)
+JOIN (VALUES (1),(2)) AS b(x) USING (x)
+JOIN (VALUES (1),(3)) AS c(x) USING (x);
+
+--
+-- Disconnected graph (Cartesian products required)
+--
+-- This tests GOO's ability to handle queries where some relations
+-- have no join clauses connecting them. GOO should allow Cartesian
+-- products when no clause-connected joins are available.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+SELECT count(*)
+FROM t1, t2, t5
+WHERE t1.a = 1 AND t2.c = 2 AND t5.f = 3;
+
+--
+-- Star schema (fact table with multiple dimension tables)
+--
+-- Test GOO with a typical star schema join pattern.
+--
+CREATE TEMP TABLE fact (id int, dim1_id int, dim2_id int, dim3_id int, dim4_id int, value int);
+CREATE TEMP TABLE dim1 (id int, name text);
+CREATE TEMP TABLE dim2 (id int, name text);
+CREATE TEMP TABLE dim3 (id int, name text);
+CREATE TEMP TABLE dim4 (id int, name text);
+
+INSERT INTO fact SELECT i, i, i, i, i, i FROM generate_series(1,100) i;
+INSERT INTO dim1 SELECT i, 'dim1_'||i FROM generate_series(1,10) i;
+INSERT INTO dim2 SELECT i, 'dim2_'||i FROM generate_series(1,10) i;
+INSERT INTO dim3 SELECT i, 'dim3_'||i FROM generate_series(1,10) i;
+INSERT INTO dim4 SELECT i, 'dim4_'||i FROM generate_series(1,10) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM fact
+JOIN dim1 ON fact.dim1_id = dim1.id
+JOIN dim2 ON fact.dim2_id = dim2.id
+JOIN dim3 ON fact.dim3_id = dim3.id
+JOIN dim4 ON fact.dim4_id = dim4.id
+WHERE dim1.id < 5;
+
+--
+-- Long join chain
+--
+-- Tests GOO with a large join involving 15 relations.
+--
+SET geqo_threshold = 8;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+-- Execute to verify correctness
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n;
+
+--
+-- Bushy tree support
+--
+-- Verify that GOO can produce bushy join trees, not just left-deep or right-deep.
+-- With appropriate cost model, GOO should join (t1,t2) and (t3,t4) first,
+-- then join those results (bushy tree).
+--
+SET geqo_threshold = 4;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2, t3, t4
+WHERE t1.a = t2.a
+ AND t3.b = t4.c
+ AND t1.a = t3.b;
+
+--
+-- Compare GOO vs standard join search
+--
+-- Run the same query with GOO and standard join search to verify both
+-- produce valid plans. Results should be identical even if plans differ.
+--
+SET enable_goo_join_search = on;
+PREPARE goo_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE goo_plan;
+
+SET enable_goo_join_search = off;
+SET geqo_threshold = default;
+PREPARE standard_plan AS
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e;
+
+EXECUTE standard_plan;
+
+-- Results should match
+EXECUTE goo_plan;
+EXECUTE standard_plan;
+
+--
+-- Large join (18 relations)
+--
+-- Test GOO with a large number of relations.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 10;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+JOIN t2 ON t1.a = t2.a
+JOIN t3 ON t1.b = t3.b
+JOIN t4 ON t2.c = t4.c
+JOIN t5 ON t3.d = t5.d
+JOIN t6 ON t4.e = t6.e
+JOIN t7 ON t5.f = t7.f
+JOIN t8 ON t6.g = t8.g
+JOIN t9 ON t7.h = t9.h
+JOIN t10 ON t8.i = t10.i
+JOIN t11 ON t9.j = t11.j
+JOIN t12 ON t10.k = t12.k
+JOIN t13 ON t11.l = t13.l
+JOIN t14 ON t12.m = t14.m
+JOIN t15 ON t13.n = t15.n
+JOIN t16 ON t14.o = t16.o
+JOIN t17 ON t15.p = t17.p
+JOIN t18 ON t16.q = t18.q;
+
+--
+-- Mixed connected and disconnected components
+--
+-- Query with two connected components that need a Cartesian product between them.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 JOIN t2 ON t1.a = t2.a,
+ t5 JOIN t6 ON t5.f = t6.e
+WHERE t1.a < 5 AND t5.d < 3;
+
+--
+-- Outer joins
+--
+-- Verify GOO handles outer joins correctly (respects join order restrictions)
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+LEFT JOIN t2 ON t1.a = t2.a
+LEFT JOIN t3 ON t2.a = t3.b
+LEFT JOIN t4 ON t3.d = t4.c;
+
+--
+-- Complete Cartesian products (disconnected graphs)
+--
+-- Test GOO's ability to handle queries with no join clauses at all.
+--
+SET enable_goo_join_search = on;
+SET geqo_threshold = 2;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1, t2;
+
+SELECT count(*)
+FROM t1, t2;
+
+--
+-- Join order restrictions with FULL OUTER JOIN
+--
+-- FULL OUTER JOIN creates strong ordering constraints that GOO must respect
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1
+FULL OUTER JOIN t2 ON t1.a = t2.a
+FULL OUTER JOIN t3 ON t2.a = t3.b;
+
+--
+-- Self-join handling
+--
+-- Test GOO with the same table appearing multiple times. GOO must correctly
+-- handle self-joins that were not removed by Self-Join Elimination.
+--
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM t1 a
+JOIN t1 b ON a.a = b.a
+JOIN t2 c ON b.b = c.c;
+
+--
+-- Complex bushy tree pattern
+--
+-- Create a query that naturally leads to bushy tree: multiple independent
+-- join chains that need to be combined
+--
+CREATE TEMP TABLE chain1a (id int, val int);
+CREATE TEMP TABLE chain1b (id int, val int);
+CREATE TEMP TABLE chain1c (id int, val int);
+CREATE TEMP TABLE chain2a (id int, val int);
+CREATE TEMP TABLE chain2b (id int, val int);
+CREATE TEMP TABLE chain2c (id int, val int);
+
+INSERT INTO chain1a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain1c SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2a SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2b SELECT i, i FROM generate_series(1,100) i;
+INSERT INTO chain2c SELECT i, i FROM generate_series(1,100) i;
+
+ANALYZE;
+
+EXPLAIN (COSTS OFF)
+SELECT count(*)
+FROM chain1a
+JOIN chain1b ON chain1a.id = chain1b.id
+JOIN chain1c ON chain1b.val = chain1c.id
+JOIN chain2a ON chain1a.val = chain2a.id -- Cross-chain join
+JOIN chain2b ON chain2a.val = chain2b.id
+JOIN chain2c ON chain2b.val = chain2c.id;
+
+--
+-- Eager aggregation with GOO join search
+-- Ensure grouped_rel handling when eager aggregation is enabled.
+--
+SET enable_eager_aggregate = on;
+SET min_eager_agg_group_size = 0;
+
+CREATE TEMP TABLE center_tbl (id int PRIMARY KEY);
+CREATE TEMP TABLE arm1_tbl (center_id int, payload int);
+CREATE TEMP TABLE arm2_tbl (center_id int, payload int);
+
+INSERT INTO center_tbl SELECT i FROM generate_series(1, 10) i;
+INSERT INTO arm1_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+INSERT INTO arm2_tbl SELECT i%10 + 1, i FROM generate_series(1, 1000) i;
+
+ANALYZE center_tbl;
+ANALYZE arm1_tbl;
+ANALYZE arm2_tbl;
+
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+
+SELECT c.id, count(*)
+FROM center_tbl c
+JOIN arm1_tbl a1 ON c.id = a1.center_id
+JOIN arm2_tbl a2 ON c.id = a2.center_id
+GROUP BY c.id;
+
+RESET min_eager_agg_group_size;
+RESET enable_eager_aggregate;
+
+-- Cleanup
+DEALLOCATE goo_plan;
+DEALLOCATE standard_plan;
+
+RESET geqo_threshold;
+RESET enable_goo_join_search;
--
2.39.3 (Apple Git-146)
[application/octet-stream] v4-0002-add-a-GUC-goo_greedy_strategy-to-choose-di.patch (8.3K, ../[email protected]/8-v4-0002-add-a-GUC-goo_greedy_strategy-to-choose-di.patch)
download | inline diff:
From 27f806771780a651211912df08b95e26c650f36d Mon Sep 17 00:00:00 2001
From: Chengpeng Yan <[email protected]>
Date: Tue, 16 Dec 2025 20:15:44 +0800
Subject: [PATCH v4 2/2] add a GUC goo_greedy_strategy to choose
different GOO greedy strategic to test
Signed-off-by: Chengpeng Yan <[email protected]>
---
src/backend/optimizer/path/goo.c | 122 +++++++++++++++++++++-
src/backend/utils/misc/guc_parameters.dat | 10 ++
src/backend/utils/misc/guc_tables.c | 7 ++
src/include/optimizer/paths.h | 7 ++
4 files changed, 145 insertions(+), 1 deletion(-)
diff --git a/src/backend/optimizer/path/goo.c b/src/backend/optimizer/path/goo.c
index 247dbb5f921..bbada782960 100644
--- a/src/backend/optimizer/path/goo.c
+++ b/src/backend/optimizer/path/goo.c
@@ -55,6 +55,7 @@
* Configuration defaults. These are exposed as GUCs in guc_tables.c.
*/
bool enable_goo_join_search = false;
+int goo_greedy_strategy = GOO_GREEDY_STRATEGY_RESULT_SIZE;
/*
* Working state for a single GOO search invocation.
@@ -94,6 +95,7 @@ typedef struct GooCandidate
{
RelOptInfo *left; /* left input clump */
RelOptInfo *right; /* right input clump */
+ double result_size; /* estimated result size in bytes */
Cost total_cost; /* total cost of cheapest path */
} GooCandidate;
@@ -129,6 +131,105 @@ goo_join_search(PlannerInfo *root, int levels_needed,
int base_rel_count;
struct HTAB *base_hash;
+ /* If COMBINED mode, try both strategies and return the better one */
+ if (goo_greedy_strategy == GOO_GREEDY_STRATEGY_COMBINED)
+ {
+ RelOptInfo *result_cost;
+ RelOptInfo *result_size;
+ Cost cost_result_cost;
+ Cost size_result_cost;
+ int saved_strategy;
+ List *saved_join_rel_list_cost;
+ struct HTAB *saved_join_rel_hash_cost;
+
+ /* Save the original strategy */
+ saved_strategy = goo_greedy_strategy;
+
+ /*
+ * First try: COST strategy
+ */
+ goo_greedy_strategy = GOO_GREEDY_STRATEGY_COST;
+ state = goo_init_state(root, initial_rels);
+ base_rel_count = list_length(root->join_rel_list);
+ base_hash = root->join_rel_hash;
+
+ result_cost = goo_search_internal(state);
+
+ if (result_cost == NULL)
+ {
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+ elog(ERROR, "GOO join search (COST strategy) failed to find a valid join order");
+ }
+
+ cost_result_cost = result_cost->cheapest_total_path->total_cost;
+ goo_destroy_state(state);
+
+ /*
+ * Save the COST strategy's join_rel_list and join_rel_hash. If COST
+ * strategy wins, we'll restore these instead of re-running.
+ */
+ saved_join_rel_list_cost = root->join_rel_list;
+ saved_join_rel_hash_cost = root->join_rel_hash;
+
+ /*
+ * Second try: RESULT_SIZE strategy
+ *
+ * Reset the planner state to start fresh. We need to clear all
+ * intermediate join relations created by the first search.
+ */
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+
+ goo_greedy_strategy = GOO_GREEDY_STRATEGY_RESULT_SIZE;
+ state = goo_init_state(root, initial_rels);
+
+ result_size = goo_search_internal(state);
+
+ if (result_size == NULL)
+ {
+ root->join_rel_list = list_truncate(root->join_rel_list, base_rel_count);
+ root->join_rel_hash = base_hash;
+ elog(ERROR, "GOO join search (RESULT_SIZE strategy) failed to find a valid join order");
+ }
+
+ size_result_cost = result_size->cheapest_total_path->total_cost;
+ goo_destroy_state(state);
+
+ /* Restore the original strategy */
+ goo_greedy_strategy = saved_strategy;
+
+ /*
+ * Compare the two results and return the one with lower cost
+ */
+ if (cost_result_cost <= size_result_cost)
+ {
+ /*
+ * COST strategy won. Restore the COST strategy's join relations
+ * instead of re-running the search.
+ */
+ root->join_rel_list = saved_join_rel_list_cost;
+ root->join_rel_hash = saved_join_rel_hash_cost;
+
+ elog(DEBUG1, "GOO COMBINED mode: COST strategy chosen (cost: %.2f vs %.2f)",
+ cost_result_cost, size_result_cost);
+
+ return result_cost;
+ }
+ else
+ {
+ /*
+ * RESULT_SIZE strategy won. The join relations are already in
+ * place, so we can return the result directly.
+ */
+ elog(DEBUG1, "GOO COMBINED mode: RESULT_SIZE strategy chosen (cost: %.2f vs %.2f)",
+ size_result_cost, cost_result_cost);
+
+ return result_size;
+ }
+ }
+
+ /* Normal single-strategy mode */
/* Initialize search state and memory contexts */
state = goo_init_state(root, initial_rels);
@@ -417,6 +518,8 @@ static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
int saved_rel_len;
struct HTAB *saved_hash;
RelOptInfo *joinrel;
+ double join_rows;
+ double result_size;
Cost total_cost;
GooCandidate *cand;
@@ -477,6 +580,9 @@ static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
set_cheapest(grouped_rel);
}
+ join_rows = joinrel->rows;
+
+ result_size = join_rows * joinrel->reltarget->width;
total_cost = joinrel->cheapest_total_path->total_cost;
/*
@@ -495,6 +601,7 @@ static GooCandidate * goo_build_candidate(GooState * state, RelOptInfo *left,
cand = palloc(sizeof(GooCandidate));
cand->left = left;
cand->right = right;
+ cand->result_size = result_size;
cand->total_cost = total_cost;
MemoryContextSwitchTo(oldcxt);
@@ -608,5 +715,18 @@ goo_commit_join(GooState * state, GooCandidate * cand)
static bool
goo_candidate_better(GooCandidate * a, GooCandidate * b)
{
- return (a->total_cost < b->total_cost);
+ switch (goo_greedy_strategy)
+ {
+ case GOO_GREEDY_STRATEGY_COMBINED:
+ /* Should not be called in COMBINED mode */
+ elog(ERROR, "goo_candidate_better should not be called in COMBINED mode");
+ return false;
+
+ case GOO_GREEDY_STRATEGY_COST:
+ return a->total_cost < b->total_cost;
+
+ case GOO_GREEDY_STRATEGY_RESULT_SIZE:
+ default:
+ return a->result_size < b->result_size;
+ }
}
diff --git a/src/backend/utils/misc/guc_parameters.dat b/src/backend/utils/misc/guc_parameters.dat
index a8ce31ab8a7..2a017195820 100644
--- a/src/backend/utils/misc/guc_parameters.dat
+++ b/src/backend/utils/misc/guc_parameters.dat
@@ -1154,6 +1154,16 @@
max => 'MAX_KILOBYTES',
},
+/* WIP: only for testing */
+{ name => 'goo_greedy_strategy', type => 'enum', context => 'PGC_USERSET', group => 'QUERY_TUNING_GEQO',
+ short_desc => 'Selects the heuristic used by GOO to compare join candidates.',
+ long_desc => 'Valid values are cost, result_size, and combined.',
+ flags => 'GUC_EXPLAIN',
+ variable => 'goo_greedy_strategy',
+ boot_val => 'GOO_GREEDY_STRATEGY_RESULT_SIZE',
+ options => 'goo_greedy_strategy_options',
+},
+
{ name => 'gss_accept_delegation', type => 'bool', context => 'PGC_SIGHUP', group => 'CONN_AUTH_AUTH',
short_desc => 'Sets whether GSSAPI delegation should be accepted from the client.',
variable => 'pg_gss_accept_delegation',
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index f87b558c2c6..11b299453fa 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -411,6 +411,13 @@ static const struct config_enum_entry plan_cache_mode_options[] = {
{NULL, 0, false}
};
+static const struct config_enum_entry goo_greedy_strategy_options[] = {
+ {"cost", GOO_GREEDY_STRATEGY_COST, false},
+ {"result_size", GOO_GREEDY_STRATEGY_RESULT_SIZE, false},
+ {"combined", GOO_GREEDY_STRATEGY_COMBINED, false},
+ {NULL, 0, false}
+};
+
static const struct config_enum_entry password_encryption_options[] = {
{"md5", PASSWORD_TYPE_MD5, false},
{"scram-sha-256", PASSWORD_TYPE_SCRAM_SHA_256, false},
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 5b3ebe5f1d2..c42610b34b3 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -16,12 +16,19 @@
#include "nodes/pathnodes.h"
+typedef enum GooGreedyStrategy
+{
+ GOO_GREEDY_STRATEGY_COST,
+ GOO_GREEDY_STRATEGY_RESULT_SIZE,
+ GOO_GREEDY_STRATEGY_COMBINED
+} GooGreedyStrategy;
/*
* allpaths.c
*/
extern PGDLLIMPORT bool enable_geqo;
extern PGDLLIMPORT bool enable_goo_join_search;
+extern PGDLLIMPORT int goo_greedy_strategy;
extern PGDLLIMPORT bool enable_eager_aggregate;
extern PGDLLIMPORT int geqo_threshold;
extern PGDLLIMPORT double min_eager_agg_group_size;
--
2.39.3 (Apple Git-146)
view thread (2+ messages)
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: Add a greedy join search algorithm to handle large join problems
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox