Subject: Re: Add a greedy join search algorithm to handle large join problems

From: lakshmi <[email-masked]>
Date: Fri, 13 Feb 2026 16:44:25 +0530

HI all,
I tested the latest GOO patch (v4) on a fresh build from the current
PostgreSQL master. The patch applied cleanly, the server built without
issues, and regression tests passed except for the expected EXPLAIN output
differences due to the new join ordering behavior.

As a quick sanity check, I compared DP, GEQO, and GOO on a small multi-join
query:

     DP planning: ~0.66 ms
     GEQO planning: ~2.28 ms
     GOO planning: ~0.38 ms
Execution times were similar across all three (~1.5–1.7 ms) with no
correctness issues. Even on a small join, GEQO shows higher planning
overhead, while GOO plans faster with comparable execution cost.
I then evaluated scaling using synthetic 15-table and 20-table joins with
EXPLAIN (ANALYZE, TIMING OFF):
     15 tables
     DP: ~22.9 ms | ~23.4 ms
     GEQO: ~46.7 ms | ~20.5 ms
     GOO: ~1.8 ms | ~22.4 ms

      20 tables
      DP: ~48.1 ms | ~30.5 ms
     GEQO: ~51.0 ms | ~26.7 ms
     GOO: ~3.2 ms | ~29.0 ms

Planning time increases notably for DP and remains relatively high for
GEQO, while GOO stays very low even at 20 joins, indicating substantially
reduced planning overhead. Execution costs remain broadly comparable, with
no obvious regressions from GOO in this synthetic workload.

Although this uses a controlled synthetic join graph rather than JOB/TPC-H,
the scaling behavior appears consistent with GOO’s goal of significantly
cheaper planning than DP/GEQO while preserving similar plan quality.

I plan to continue testing with more realistic workloads and will share
further results if anything notable appears.

Thanks for the interesting work.

Regards,
Lakshmi

On Fri, Feb 13, 2026 at 12:33 PM Pavel Stehule <[email-masked]>
wrote:

>
>
> čt 11. 12. 2025 v 18:07 odesílatel Tomas Vondra <[email-masked]> napsal:
>
>> On 12/11/25 07:12, Pavel Stehule wrote:
>> >
>> >
>> > čt 11. 12. 2025 v 3:53 odesílatel John Naylor <[email-masked]
>> > <mailto:[email-masked]>> napsal:
>> >
>> >     On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <[email-masked]
>> >     <mailto:[email-masked]>> wrote:
>> >     > I did however notice an interesting thing - running EXPLAIN on
>> the 99
>> >     > queries (for 3 scales and 0/4 workers, so 6x 99) took this much
>> time:
>> >     >
>> >     > master:       8s
>> >     > master/geqo: 20s
>> >     > master/goo:   5s
>> >
>> >     > It's nice that "goo" seems to be faster than "geqo" - assuming the
>> >     plans
>> >     > are comparable or better. But it surprised me switching to geqo
>> >     makes it
>> >     > slower than master. That goes against my intuition that geqo is
>> >     meant to
>> >     > be cheaper/faster join order planning. But maybe I'm missing
>> >     something.
>> >
>> >     Yeah, that was surprising. It seems that geqo has a large overhead,
>> so
>> >     it takes a larger join problem for the asymptotic behavior to win
>> over
>> >     exhaustive search.
>> >
>> >
>> > If I understand correctly to design - geqo should be slower for any
>> > queries with smaller complexity. The question is how many queries in the
>> > tested model are really complex.
>> >
>>
>> Depends on what you mean by "really complex". TPC-DS queries are not
>> trivial, but the complexity may not be in the number of joins.
>>
>> Of course, setting geqo_threshold to 2 may be too aggressive. Not sure.
>>
>
> I checked the TPC-H queries and almost all queries are simple - 5 x JOIN
> -- 2x nested subselect
>
>
>>
>>
>> regards
>>
>> --
>> Tomas Vondra
>>
>>

---

From: Tomas Vondra <[email-masked]>
Date: Fri, 13 Feb 2026 14:18:24 +0100

Hello,

On 2/13/26 12:14, lakshmi wrote:
> issues, and regression tests passed except for the expected EXPLAIN
> output differences due to the new join ordering behavior.
> 
> As a quick sanity check, I compared DP, GEQO, and GOO on a small multi-
> join query:
> 
>      DP planning: ~0.66 ms
>      GEQO planning: ~2.28 ms
>      GOO planning: ~0.38 ms
> I then evaluated scaling using synthetic 15-table and 20-table joins
> with EXPLAIN (ANALYZE, TIMING OFF):
>      15 tables
>      DP: ~22.9 ms | ~23.4 ms
> reduced planning overhead. Execution costs remain broadly comparable,
> with no obvious regressions from GOO in this synthetic workload.
> 
> Although this uses a controlled synthetic join graph rather than JOB/
> TPC-H, the scaling behavior appears consistent with GOO’s goal of
> significantly cheaper planning than DP/GEQO while preserving similar
> plan quality.
> 

I think we need to know much more about the synthetic benchmark to judge
the plan quality. For example, for OLTP-like schema/queries, processing
only very few rows in each join, the different join methods are likely
to perform about the same. The performance will differ for larger joins
(matching large number of rows / large intermediate results).

The other question is whether the plans produced by the join search
algorithms even differ.

regards

-- 
Tomas Vondra

---

From: Chengpeng Yan <[email-masked]>
Date: Sat, 14 Feb 2026 05:39:33 +0000

> 2026年2月13日 19:14，lakshmi <[email-masked]> 写道：
>
> HI all,
> I tested the latest GOO patch (v4) on a fresh build from the current PostgreSQL master. The patch applied cleanly, the server built without issues, and regression tests passed except for the expected EXPLAIN output differences due to the new join ordering behavior.
>
> As a quick sanity check, I compared DP, GEQO, and GOO on a small multi-join query:
>
>      DP planning: ~0.66 ms
>      GEQO planning: ~2.28 ms
>      GOO planning: ~0.38 ms
> Execution times were similar across all three (~1.5–1.7 ms) with no correctness issues. Even on a small join, GEQO shows higher planning overhead, while GOO plans faster with comparable execution cost.
> I then evaluated scaling using synthetic 15-table and 20-table joins with EXPLAIN (ANALYZE, TIMING OFF):
>      15 tables
>      DP: ~22.9 ms | ~23.4 ms
> Planning time increases notably for DP and remains relatively high for GEQO, while GOO stays very low even at 20 joins, indicating substantially
> reduced planning overhead. Execution costs remain broadly comparable, with no obvious regressions from GOO in this synthetic workload.
>
> Although this uses a controlled synthetic join graph rather than JOB/TPC-H, the scaling behavior appears consistent with GOO’s goal of significantly cheaper planning than DP/GEQO while preserving similar plan quality.
>
> I plan to continue testing with more realistic workloads and will share further results if anything notable appears.
>

Hi,

Thank you very much for testing v4 and sharing the results. I really
appreciate the effort and the detailed feedback.

I also agree with Tomas’s point that we need better benchmark context to
evaluate plan quality, not only planning time.

I’ve prepared a v5 refresh on top of v4, still split into two patches
(v5-0001 and v5-0002).
I also ran `make check-world` on current master with v5 applied, and it
passes on my side.

Compared with v4:

[PATCH v5 1/2]
- keeps the base GOO join-search path focused on a single greedy signal
(cost);
- fixes issues found during recent testing (mainly around candidate
probing/cleanup and failure paths);
- improves stability/determinism in candidate selection (including tie
handling);
- updates regression outputs accordingly.

[PATCH v5 2/2]
- extends `goo_greedy_strategy` and adds the `selectivity` heuristic
suggested by Tomas;
- improves combined mode so multiple greedy signals are evaluated in a
common framework, and the final plan is selected by lowest estimated
`total_cost`;
- keeps strategy-layer changes isolated from the base path for easier
comparison and review.

My current next steps are:

1. Continue evaluating plan quality on more datasets/workloads. I’ve
already collected several candidate tests: some are JOB-based
variants, and others are synthetic workloads. Next, I plan to
consolidate these into a unified test set (with reproducible
setup/details), publish it, and run broader comparative evaluation.

2. Prototype a hybrid handoff approach: use greedy contraction first to
reduce the join graph, then let DP optimize the reduced problem. The
goal is a smoother transition around the threshold, avoiding abrupt
plan-shape changes from a hard optimizer switch.

3. Explore more join-ordering improvements incrementally, including
ideas from “Simplicity Done Right for Join Ordering” and related
work.

Thanks again for the careful testing and detailed feedback.

--
Best regards,
Chengpeng Yan

---

From: lakshmi <[email-masked]>
Date: Mon, 16 Feb 2026 11:57:21 +0530

Hi Chengpeng,

I tested the v5 patch on a clean build from current PostgreSQL master.The
patch applied cleanly, the server built successfully, and  make
check-world  passed
without new failures.
I then compared DP, GEQO, and GOO on synthetic multi-join workloads.

*15-table join*

   -

   DP: planning ~19.1 ms | execution ~21.0 ms
   -

   GEQO: planning ~46.6 ms | execution ~17.7 ms
   -

   GOO v5: planning ~1.0 ms | execution ~19.5 ms

*20-table join*

   -

   DP: planning ~25.1 ms | execution ~28.2 ms
   -

   GEQO: planning ~27.5 ms | execution ~23.5 ms
   -

   GOO v5: planning ~1.5 ms | execution ~28.9 ms

   Across both join sizes, GOO v5 keeps planning time extremely low (roughly
   an order of magnitude lower than DP/GEQO) while execution times remain
   in a comparable range, with no obvious regressions in this synthetic
   workload. This appears consistent with the goal of reducing planning
   overhead for large join problems while preserving similar plan quality.

   These tests use controlled synthetic joins rather than JOB/TPC-H, so
   they mainly validate planning-time scaling and basic plan sanity. I plan to
   continue with more realistic workloads and strategy comparisons and will
   share further results if anything notable appears.

   Thanks for the continued work on this patch series.

   Regards,
   Lakshmi

On Sat, Feb 14, 2026 at 11:09 AM Chengpeng Yan <[email-masked]>
wrote:

> > Although this uses a controlled synthetic join graph rather than
> JOB/TPC-H, the scaling behavior appears consistent with GOO’s goal of
> significantly cheaper planning than DP/GEQO while preserving similar plan
> quality.
> >

---

From: lakshmi <[email-masked]>
Date: Mon, 16 Feb 2026 12:29:24 +0530

Hi Chengpeng,

I ran a quick comparison of the GOO v5 greedy strategies on a multi-join
workload to look at execution quality in addition to planning time.

Here are the results from one representative query:

       -cost: planning ~1.8 ms | execution ~32.8 ms

       -result_size: planning ~2.1 ms | execution ~29.3 ms

       -combined: planning ~3.7 ms | execution ~29.4 ms

All three strategies keep planning time very low, which continues to
support GOO’s intended scalability advantage over DP and GEQO.

In this test, the cost strategy shows noticeably higher execution time,
while result_size and combined produce similar and better execution
performance. Since combined has slightly higher planning overhead without a
clear execution benefit here, result_size appears to provide the best
trade-off for this synthetic workload.

I plan to continue testing with a few JOB-based queries to evaluate plan
quality in a more realistic setting and will share further results if
anything notable appears.

Thanks again for the continued work on this patch series.

Regards,
Lakshmi

On Mon, Feb 16, 2026 at 11:57 AM lakshmi <[email-masked]> wrote:

> check-world  passed without new failures.

---

From: Tomas Vondra <[email-masked]>
Date: Mon, 16 Feb 2026 09:44:37 +0100

Hi Lakshmi,

can you share the join workload you used to test (or at least some
example joins with 15 and 20 relations)? Have you modified any of the
planner parameters affecting join search (join_collapse_limit,
geqo_threshold, ...)?

regards
Tomas

On 2/16/26 07:59, lakshmi wrote:
> performance. Since combined has slightly higher planning overhead
> without a clear execution benefit here, result_size appears to provide
> the best trade-off for this synthetic workload.
> 
> On Mon, Feb 16, 2026 at 11:57 AM lakshmi <[email-masked]
> <mailto:[email-masked]>> wrote:
> 
>     Hi Chengpeng,
> 
>     I tested the v5 patch on a clean build from current PostgreSQL
>     master.The patch applied cleanly, the server built successfully,
>     and  |make check-world|  passed without new failures.
>       *
>       *
>       *
>       *
>       *
>       *
>         Across both join sizes, GOO v5 keeps planning time extremely
>         low (roughly an order of magnitude lower than DP/GEQO) while
>         execution times remain in a comparable range, with no obvious
>         regressions in this synthetic workload. This appears consistent
>         with the goal of reducing planning overhead for large join
>         problems while preserving similar plan quality.
> 
>         These tests use controlled synthetic joins rather than JOB/TPC-
>         H, so they mainly validate planning-time scaling and basic plan
>         sanity. I plan to continue with more realistic workloads and
>         strategy comparisons and will share further results if anything
>         notable appears.
> 
>     On Sat, Feb 14, 2026 at 11:09 AM Chengpeng Yan
>     <[email-masked] <mailto:[email-masked]>> wrote:
> 
> 
>         > 2026年2月13日 19:14，lakshmi <[email-masked] <mailto:[email-masked]>> 写道：
>         > 
>         > HI all,

-- 
Tomas Vondra

---

From: lakshmi <[email-masked]>
Date: Mon, 16 Feb 2026 16:14:16 +0530

Hi Tomas,

Thank you for the question.
The 15-table and 20-table results I shared were obtained using a synthetic
join workload designed to stress join-order planning and measure
planning-time scaling, rather than a JOB or TPC-H query.
Each query is essentially a left-deep chain of equality joins over simple
tables. For reference, the structure is equivalent to:

15-table join

SELECT count(*)

FROM t1

JOIN t2 ON t1.id = t2.id

JOIN t3 ON t2.id = t3.id

 ...

JOIN t15 ON t14.id = t15.id;

20-table join

SELECT count(*)

FROM t1

JOIN t2 ON t1.id = t2.id

JOIN t3 ON t2.id = t3.id

...

JOIN t20 ON t19.id = t20.id;

Regarding planner settings:

-geqo_threshold was set to:

                 a high value (e.g., 100) to force DP

                 a low value (e.g., 2) to allow GEQO/GOO

-enable_goo_join_search was toggled on/off depending on the comparison
being     measured.

-Other planner parameters, including join_collapse_limit, were left at
their default values.

So these experiments mainly evaluate planning-time scaling and basic plan
sanity on a controlled join graph, rather than realistic workload plan
quality.

I’m currently preparing additional tests using selected JOB queries to
provide more meaningful plan-quality comparisons and will share those
results once available.

Regards
Lakshmi

---

From: Chengpeng Yan <[email-masked]>
Date: Sun, 3 May 2026 12:46:46 +0000

> On Feb 14, 2026, at 13:39, Chengpeng Yan <[email-masked]> wrote:
>

Hi,

I ran the current pure-GOO variants on JOB and JOB-Complex [1], 143
queries in total. JOB-Complex uses the same IMDB/JOB setting, but adds
harder predicates and more challenging join patterns. The tested
variants were:

DP / GEQO / GOO(cost) / GOO(result_size) / GOO(selectivity) / GOO(combined)

The benchmark uses the same setup as my previous JOB measurements. It
prepares the IMDB-backed workloads, applies the same Postgres GUC
settings used in the previous runs, runs one warmup pass and three
measured repetitions for each query/variant pair, and reports the median
of the measured repetitions. Each measured execution is collected with:

EXPLAIN (ANALYZE, TIMING OFF, SUMMARY ON, FORMAT JSON, SETTINGS ON)

Planning time and execution time are parsed separately. Planning time is
still reported, but the main metric below is execution time, because it
better reflects the quality of the chosen plan. I will attach
v5-job-benchmark-result.xlsx with both planning-time and execution-time
results, and v5-job-benchmark-execution-result.pdf as the execution-time
PDF view. The color convention is the same as in the earlier tables.
Timeouts use a 10-minute statement_timeout.

The scripts, workload definitions, and reproduction details are in the
benchmark repository [2]. I used a repository rather than a single
script because the evaluation now includes multiple workloads, several
algorithm variants, and enough setup details that keeping the workload
definitions and run protocol together makes reproduction and review
easier.

As expected from the previous discussion, planning time is low for the
GOO variants. GOO(combined) is about 5.2x faster than GEQO in planning
time in this run.

The execution-time picture is mixed. GOO(combined) has clear positives,
but does not look robust enough to replace GEQO directly.

Compared with GEQO over the 143 comparable queries:

GOO(combined) faster by 20%-2x: 6 queries
GOO(combined) faster by 2x-10x: 8 queries
GOO(combined) faster by >10x: 7 queries

GOO(combined) within +/-20% of GEQO: 82 queries

GOO(combined) slower by 20%-2x: 10 queries
GOO(combined) slower by 2x-10x: 26 queries
GOO(combined) slower by >10x: 4 queries

timeouts: 0 for GEQO, 0 for GOO(combined)

On execution-time sum, GOO(combined) is better than GEQO:

GEQO: 430459 ms
GOO(combined): 292194 ms

That is about 1.47x faster than GEQO on the workload sum. However, in
the execution-time distribution, the result is not one-sided: there are
meaningful wins and meaningful regressions.

Some cases where GOO(combined) is much better than GEQO:

job_complex q15: 229 ms vs 114942 ms, about 503x faster
job_complex q18: 2456 ms vs 116014 ms, about 47x faster
job 26c: 859 ms vs 25735 ms, about 30x faster
job 26a: 359 ms vs 8107 ms, about 23x faster
job_complex q23: 1121 ms vs 15711 ms, about 14x faster
job_complex q05: 462 ms vs 5678 ms, about 12x faster

Some cases where GOO(combined) is much worse than GEQO:

job_complex q28: 56563 ms vs 272 ms, about 208x slower
job_complex q20: 1918 ms vs 88 ms, about 22x slower
job_complex q12: 70750 ms vs 3456 ms, about 20x slower
job 28b: 1390 ms vs 103 ms, about 14x slower

## Selectivity

One topic from the earlier discussion was whether selectivity should be
ignored. Based on this run, I do not think selectivity is good enough as
a primary greedy strategy.

GOO(selectivity) has low planning time, but its execution-time behavior
is poor:

execution-time sum: about 16.46x DP and 4.76x GEQO
timeouts: 6
cases >=2x GEQO: 110

Some examples:

job 24b: 87569 ms vs GEQO 13.7 ms, about 6374x slower
job 29a: 56080 ms vs GEQO 8.9 ms, about 6334x slower
job 31b: 207334 ms vs GEQO 165 ms, about 1259x slower
job_complex q03: 14345 ms vs GEQO 25 ms, about 574x slower
job_complex q04: 15026 ms vs GEQO 26 ms, about 589x slower

This does not mean that selectivity is meaningless, or that GOO itself
is useless. The more precise issue is that a greedy join search commits
much earlier than DP or GEQO. If an early estimate is wrong, that error
is more likely to be amplified into the final join order.

For selectivity specifically, the main problem seems to be that it is
scale-free. It optimizes the relative reduction of one join pair, not
the absolute size of the intermediate result. A join can have a very low
estimated selectivity and still produce a large intermediate if the
inputs are large. Result_size is also estimate-dependent, but it at
least includes the estimated output size; cost includes Postgres's
normal physical cost model. Selectivity throws away much of that scale
information, which makes it a brittle primary greedy key on these
workloads.

In GOO(combined), the selectivity candidate was never selected as the
final plan, so it did not improve the combined variant in this run.
There were a few positive standalone selectivity cases, but they were
rare compared with the tail risk.

## GOO(combined)

GOO(combined) is still the best pure-GOO variant in this run. It reduces
planning time and avoids several severe GEQO bad cases.

At the same time, the remaining regressions suggest three limitations:

1. A greedy path is more sensitive to estimation errors and local-choice
mistakes. A locally reasonable early join can be globally poor once
the rest of the join graph is considered.

2. Sometimes none of the current greedy variants produces a good
candidate. For example, in q20, 28b, 19a, and q03, all current GOO
candidates are clearly worse than GEQO. In that case, improving only
the final selector would not be enough.

3. Sometimes a good GOO candidate exists, but the final estimated-cost
selector does not choose it. For example, in q28, q12, and 15a,
result_size produced a much better plan, but the final cost-based
choice selected a worse one.

If we continue improving pure GOO, I think the two natural directions
are:

* increase the diversity of greedy strategies, so different queries
have a better chance of getting at least one good candidate;

* once such a good candidate exists, make the final selector more
likely to pick it. In several cases a faster GOO candidate existed,
but it had a higher estimated cost and was not selected.

The CIDR 2021 paper "Simplicity Done Right for Join Ordering" is
relevant to both ideas: its E-block suggests another
enumeration/candidate-generation direction, and its U-block gives an
upper-bound style signal that could be used as a risk-aware selector
input. I think that is a good fit in principle, but it would not be a
small extension to the current GOO patch. E-block would require a
different enumeration path, and U-block would require extra metadata
such as maximum value frequency for join attributes. For this patch
series, I would prefer to keep the scope focused on plan
search rather than also changing the estimation side.

There is also a usability issue. The current pure-GOO variants do have
some tuning surface: users can switch between cost and result_size, or
use a combined mode. That is easy to try, but not necessarily easy to
tune. It is often unclear which strategy should be preferred for a given
query, and in some tail cases neither strategy produces a good plan.

GOO(combined) with cost and result_size may already be a useful baseline
or candidate generator, but the regressions above do not support making
it the default GEQO replacement. One possible advantage over GEQO is
that GOO may work better with pg_plan_advice, but I need to understand
the details better before making a stronger claim.

So my current conclusion is not that GOO has no value. It is fast to
plan, and it can avoid some GEQO bad cases. The issue is that pure GOO
appears to have structural robustness limits in some tail cases.

Because of that, I plan to switch the next experiment to a direction
closer to the earlier community discussion about making the transition
from DP to heuristic search more gradual [3]. The idea is to give
planning a fixed effort budget, use exact DP while the budget allows it,
and complete the remaining search space with GOO when the DP quota is
not enough.

This seems smoother, easier to tune, and possibly easier to accept:
increasing the effort should naturally allow either deeper DP or more
greedy completions, instead of switching abruptly from DP to a pure
greedy or GEQO-style method. I already have a demo implementation under
test, and I will share the code and benchmark results separately once
the numbers are ready.

References:

[1] JOB-Complex: https://github.com/DataManagementLab/JOB-Complex

[2] Benchmark repository:
https://github.com/Reminiscent/join-order-benchmark

[3] Earlier discussion about replacing GEQO more gradually:
https://www.postgresql.org/message-id/flat/CAFBsxsE3Sb889r-Xvun%2BiAa5Onjy71m8nzp6JSH387JJF-YmrA%40mail.gmail.com

--
Best regards,
Chengpeng Yan

---

From: John Naylor <[email-masked]>
Date: Tue, 5 May 2026 12:40:13 +0700

> harder predicates and more challenging join patterns. The tested

Thanks for those results. As Tomas mentioned above, evaluation should
focus on cases where DP won't be used. Joins with a small number of
relations aren't going to tell us anything, especially since (I think)
GEGO will at times accidentally cover the entire seach space. Indeed,
there are quite a few queries where GOO is worse than GEQO by around
2-3x, but also small enough to be handled by DP anyway, so reporting
them is a distraction.

Less than half of the JOB-Complex queries have at least 12 "joins"
(BTW, is that number in the pdf actual joins or is it base
relations?), but the results (and summary results) include small joins
as well. Looking at the queries where one of GOO/GEQO is much better
than the other do seem to happen with large join problems.

> the details better before making a stronger claim.

Given that all heuristic join enumeration methods can produce
spectacularly bad plans, the ability to influence the plan is more
crucial with large join problems with small ones. Features should be
orthogonal in general, and in this case, integrating well with plan
advice seems like a strong deciding factor.

--
John Naylor
Amazon Web Services

---

From: Chengpeng Yan <[email-masked]>
Date: Mon, 11 May 2026 14:33:50 +0000

Hi,

> On May 5, 2026, at 13:40, John Naylor <[email-masked]> wrote:
>

Thanks for taking a look and pointing this out. You're right. Sorry
about that. Including the smaller join queries in the summary made the
result harder to interpret, because those are normally handled by
standard DP search and are not the main target of this patch.

For the comparison below, I only use queries involving at least 12 base
relations, i.e. the default GEQO threshold boundary. The number shown in
the PDF is the number of base relations in the query's flat FROM list,
not the number of join operators. In JOB + JOB-Complex, 33 of the 143
queries meet that threshold: 20 from JOB and 13 from JOB-Complex.

I reran the v4 patch on those 33 queries, with DP / GEQO /
GOO(combined). This version does not include selectivity in the combined
candidate set; GOO(combined) only chooses between the GOO(cost) and
GOO(result_size) plans. The protocol and GUC settings are the same as
before: one warmup pass, three measured repetitions, median reported,
10-minute statement_timeout, and:

The command checklist and run protocol are documented in the benchmark
repository [1][2]. I attached v4-job-benchmark-result-20260511.xlsx with
both planning and execution numbers, and
v4-job-benchmark-execution-result-20260511.pdf as a PDF view of the
execution-time sheet.

The detailed comparison below uses round1, which is the baseline
workbook attached here.

For planning time, GOO(combined) is still much cheaper than GEQO:

GEQO: 722 ms
GOO(combined): 108 ms

That is about 6.7x lower planning time for GOO(combined).

For execution time, compared with GEQO over the 33 comparable queries:

GOO(combined) faster by 20%-2x: 5 queries
GOO(combined) faster by 2x-10x: 4 queries
GOO(combined) faster by >10x: 4 queries

GOO(combined) within +/-20% of GEQO: 9 queries

GOO(combined) slower by 20%-2x: 5 queries
GOO(combined) slower by 2x-10x: 4 queries
GOO(combined) slower by >10x: 2 queries

On execution-time sum:

GEQO: 574582 ms
GOO(combined): 87706 ms

That is about 6.55x faster for GOO(combined) in this round, but the
distribution is not one-sided.

job_complex q19: 1125 ms vs 430902 ms, about 383x faster
job_complex q17: 975 ms vs 97105 ms, about 100x faster
job 26c: 880 ms vs 25859 ms, about 29x faster
job 29c: 31 ms vs 416 ms, about 14x faster

job_complex q20: 1912 ms vs 78 ms, about 25x slower
job_complex q12: 71628 ms vs 3324 ms, about 22x slower
job 29a: 84 ms vs 9 ms, about 9.4x slower
job 30a: 1768 ms vs 423 ms, about 4.2x slower

So I would still describe the execution-time picture as mixed. Both
methods have bad cases.

> advice seems like a strong deciding factor.

I agree. For large joins, cardinality estimation, the cost model, and
the join-order search all interact. Even a better search method can
choose a bad plan if the cardinality estimates or cost model give it
misleading input. So the ability to tune or influence the chosen plan
becomes especially important.

After reading more of the pg_plan_advice discussion and code, my current
understanding is that GOO should be easier than GEQO to integrate with
join order advice. Please correct me if this understanding is wrong. My
reading of the pg_plan_advice discussion is that advice can only
reliably nudge the planner towards plans it would have considered
anyway; with GEQO, not all join orders are explored, so join-order
advice can only constrain the options that the genetic search actually
considers [3][4].

GOO seems to have a useful property here: candidate generation is
explicit. At each contraction step it evaluates legal pair joins, so an
advice implementation could reject or prefer candidate pairs at that
point. This does not make impossible advice feasible, and it still would
need careful integration, but it seems less dependent on whether GEQO
happened to generate a compatible join sequence.

I also noticed a statistics-sensitivity issue while rerunning the
large-query subset. I ran five rounds over the same 33 queries and the
same DP / GEQO / GOO(combined) variants. Each round refreshed statistics
before executing the measured queries. I saved the statistics snapshot
with pg_dump --statistics-only and kept the per-round result
spreadsheets; these are in round_artifacts-20260511.zip, organized as
round1 through round5. The per-run measured repetitions are
comparatively stable; the large differences below correspond to changed
plans after refreshed statistics, not just measurement noise.

Execution-time sum:

| round | DP ms | GEQO ms | GOO(combined) ms |
| --- | ---: | ---: | ---: |
| round1 | 41091 | 574582 | 87706 |
| round2 | 41331 | 51205 | 85038 |
| round3 | 40493 | 95580 | 85561 |
| round4 | 41464 | 99228 | 83930 |
| round5 | 41611 | 126544 | 85578 |

GOO(combined) has the lower execution-time sum in four of the five
rounds. The exact bucket counts are not identical in every round, but
each round still has both large GOO(combined) wins and large
regressions. More importantly, GEQO varies much more across statistics
snapshots: its execution-time sum ranges from 51s to 575s, while
GOO(combined) stays in the 84s-88s range.

The large GEQO swings seem to follow this pattern: small changes in
sampled statistics change the estimated-cost ordering among close GEQO
join orders; some selected orders delay selective joins and produce much
larger intermediate results. For example, job_complex q19 ranges from
2.5s to 431s across the five rounds, job_complex q17 ranges from 0.96s
to 97s, job 26a ranges from 0.26s to 8.2s, and job 26c ranges from 0.65s
to 26s.

I do not think this means GOO(combined) is generally more stable. In
these runs, GEQO sometimes selected very different join orders after
refreshed statistics, while GOO(combined) changed less severely. One
possible reason is the different search shape: GOO(combined) compares a
small number of greedy completions, while GEQO searches among full join
sequences, where close estimated costs can lead to a very different
selected sequence. I would treat this as an observed behavior in this
benchmark rather than a general property of GOO.

My current summary is:

1. GOO(combined) still has much lower planning time than GEQO.
2. On execution time for large joins, both GEQO and GOO(combined) have
good and bad cases.
3. GOO may have a better path to work with plan advice, because the
search is deterministic and exposes explicit pair-join decision
points where advice could reject or prefer candidate pairs.
4. In this benchmark subset, GOO(combined) is more stable across
refreshed statistics, while GEQO is more sensitive to small
statistics changes.

As I mentioned in the previous message, the remaining GOO(combined)
regressions fall into two groups: sometimes neither cost nor result_size
finds a good greedy candidate, and sometimes a good greedy candidate
exists but the final estimated-cost selector chooses a slower plan.

So I am still looking at the two follow-up directions mentioned earlier,
both building on the current GOO work. One is to improve pure-GOO
candidate generation and the final selector, for example by adding more
diverse strategies and making the selector consider signals beyond final
estimated cost. The other is to use exact DP for a prefix of the problem
and fall back to GOO when the DP budget is not enough. The first
direction may need broader changes across planner or estimation-related
code, so I am currently focusing more on the second direction and will
share the code and numbers once I have a clearer result.

References:

[1] Benchmark reproduction notes:
https://github.com/Reminiscent/join-order-benchmark/blob/main/REPRODUCE.md

[2] Benchmark run protocol:
https://github.com/Reminiscent/join-order-benchmark/blob/main/BENCHMARK_RUNS.md

[3] pg_plan_advice / GEQO discussion:
https://www.postgresql.org/message-id/CA%2BTgmoYD55R8XqgbFbKhC4Uipu-gxA1msDOsUAZ9q38iCN8dQA%40mail.gmail.com

[4] Same pg_plan_advice thread, GEQO note:
https://www.postgresql.org/message-id/CA%2BTgmoZpQDJOz_W34Wkp-JA%3DMQpzLeV6dsDGt%3D04U0AD6c65RA%40mail.gmail.com

--
Best regards,
Chengpeng Yan

---

From: John Naylor <[email-masked]>
Date: Tue, 12 May 2026 18:51:50 +0700

> advice can only constrain the options that the genetic search actually

I believe that's the current thinking, but note this from the plan
advice README:

"XXX Need to investigate whether and how well supplying advice works with GEQO"

> happened to generate a compatible join sequence.

That's a reasonable hypothesis. I'm not sure what you mean by "careful
integration". Would some aspects of the patch need to change?

> | round | DP ms | GEQO ms | GOO(combined) ms |

That's an interesting finding! We'll want to keep this behavior in
mind and see how reproducible it is. You mentioned you didn't want to
draw any general conclusions (reasonable), but a 10x variation just
from statistics does put a new perspective on the test results.

> code,

I agree we should try to avoid strategies that depend on changing other areas.

> so I am currently focusing more on the second direction and will

I've mentioned elsewhere that graceful degradation is a good property
(and a prerequisite for robustness), and cliff behavior is one
disadvantage of the GEQO search. However, it's not going to scale:
There will always be large join problems where a heuristic search will
find terrible plans, and that means severe regressions are possible,
as we've seen. Further, this direction opens up another large design
space that I fear will complicate testing and review, and it's already
hard enough.

So, the above doesn't seem like a logical next step from the data thus
far. (To be clear, I think it's good future work, but that presumes
getting to a first commit).

To my mind, we still need more data to inform future direction. The
most important things IMO are
- plan advice -- My current thinking is, the plan advice aspect is the
"wild card" that could immediately improve user experience with large
joins. Conversely, without the ability to fix regressions, any new
approach is risky. How well does plan advice work with GEQO? Does it
work with GOO already or would that need additional coding?
- more large join benchmarks (I see you have additional benchmarks in
your repository above)

--
John Naylor
Amazon Web Services

---

From: Tomas Vondra <[email-masked]>
Date: Tue, 12 May 2026 15:42:32 +0200

> from statistics does put a new perspective on the test results.

After reading this, my thinking was "we should assume the estimates are
accurate" because with bogus estimates we can end up with arbitrarily
bad plans. Garbage in, garbage out.

But maybe it's not as black-and-white? I agree if one method is much
more robust (i.e. performs better with estimates that are close enough
to the actual values), then that seems like an important feature for
this type of heuristics.

I wonder how "bad" the estimates are in the presented example, both in
the good and bad runs.

> I agree we should try to avoid strategies that depend on changing other areas.

IMHO it's futile to search for a perfect heuristics. It we had that, we
wouldn't need the DP mode at all. This can't be the criteria, because no
heuristics would pass that.

Regarding the two proposed directions, it's not very clear to me why the
first direction would require broader changes, particularly changes that
would be unnecessary for the second direction (DP for prefix).

To me it seems the second approach is actually an advanced version of
the first one. How to you pick the prefix to handle by DP if not by some
heuristics, requiring this new signals?

> space that I fear will complicate testing and review, and it's already

TBH I don't quite understand what the proposed approach with "using
exact DP for a prefix of the problem" is meant to do. As of now we split
the join problem into smaller parts per join_collapse_limit (=8). If
these problems are "too large" for DP (geqo_threshold=12), we use the
heuristics (GEQO) mode. Or do I misremember this?

Maybe I'm just "too used" to this, but this seems reasonable to me. Try
searching for a "perfect" solution first (within reason), and only for
large problems fall back to something approximate. Sensible, no?

To got to the GEQO/GOO code, people have to adjust the limits, so that
(join_collapse_limit >= geqo_threshold). AFAIK almost no one does that,
so most join problems are smaller that geqo_threshold and so handled by
regular DP (for smaller subproblems).

But let's say someone adjusts the GUCs, gets to GOO, and it handles a
prefix of the problem using the DP approach. How is that different from
keeping the (join_collapse_limit < geqo_threshold) and not even getting
to GOO? Why not to just leave join_collapse_limit to a low value?

> - more large join benchmarks (I see you have additional benchmarks in

Right. When replacing one heuristics with a different one, there will
almost certainly be regressions. Each heuristics will explore a slightly
different subset of the solution space, and it's a matter of luck which
gets a substantially better solution.

I don't have a fully formed idea how to evaluate this, but I think the
only way to "prove" a the new heuristics is better is to test a lot of
complex join queries, and look at the overall statistics. See how long
the planning took, see how many queries got faster/slower, etc.

The JOB is certainly one option to do that, and it's valuable because
the queries are meant to be realistic / from actual application. But
there's not all that many of them.

I think it would be useful to write a script that generates joins of
arbitrary complexity (number of relations, how connected they are), and
see how it works on those. It could even generate data to get estimates
with adjustable inaccuracy.

regards

-- 
Tomas Vondra

---

From: John Naylor <[email-masked]>
Date: Wed, 13 May 2026 11:34:41 +0700

> to the actual values), then that seems like an important feature for

Exactly. (The operative word being "if")

At the very least, this variation can complicate getting reliable test results.

> I wonder how "bad" the estimates are in the presented example, both in

Yeah, one deliberate feature of JOB is that it has real-world data
distribution that confound DBMS's common assumptions about data
independance etc. I wonder if a synthetic benchmark with more
uniform/independent data would have less variation here.

> heuristics would pass that.

Agreed.

> large problems fall back to something approximate. Sensible, no?

Yes, I'm very much in favor of that concept. My concern was, trying to
do this now may be trying to do too much at once.

> to GOO? Why not to just leave join_collapse_limit to a low value?

One flavor of the second idea above (found in the literature) is to
start with DP, and after some new GUC limit (under the hood: # of
times calling make_join_rel), pick one of the incomplete subproblems
and finish with a heuristic search. It switches strategy on the fly,
rather than choosing upfront. That's the difference from now, although
I'm not sure offhand how join_collase_limit chooses its subproblems
out of the bigger problem.

> with adjustable inaccuracy.

+1

With unnaturally uniform/independent data, I'm curious if the
stats-dependent variation seen above for GEQO would disappear/lessen.
(I'm not sure how hard adjustable inaccuracy would be)

--
John Naylor
Amazon Web Services

---

From: Chengpeng Yan <[email-masked]>
Date: Wed, 13 May 2026 06:06:16 +0000

Hi Tomas,

Thanks for the detailed comments. I do not think I can answer all of the
questions yet, but I would like to first align my current understanding
and reply to the parts where I have some thoughts. For the remaining
parts, I think I need more analysis/research before making stronger
claims.

> On May 12, 2026, at 21:42, Tomas Vondra <[email-masked]> wrote:
> 

I agree with this point. My earlier benchmark was more of an end-to-end
test with current postgres estimates, including cases where the
estimates can be quite wrong. I used that setup because complex join
estimates seem very hard to make accurate in all cases, so these errors
are likely to remain part of the practical problem.

But for evaluating the join-order algorithm itself, I agree we also need
a setup where the estimates are closer to the actual values, for example
by first measuring actual row counts/cardinalities and then using those
values instead of normal planner estimates. That would answer a
different question: the current results show end-to-end behavior with
the current postgres estimator, while the additional setup would better
isolate the search algorithm.

If the estimates are very wrong, the selected plan may be dominated by
estimator error rather than by the search method. In that case, I am not
yet sure how much a win/loss between two heuristics proves about the
join search algorithm itself. On the other hand, if the estimates are
close enough and one method is still more robust, I agree that would be
an important property for this kind of heuristic.

For the presented examples, I need to look more carefully at the good
and bad runs. From a first look at some severe regressions, the issue
seems to be that some intermediate join row estimates are off by orders
of magnitude, but I do not want to claim that as the full answer before
doing a more systematic analysis.

> heuristics would pass that.

Agreed. I did not mean that the goal should be a heuristic with no bad
cases. That would not be realistic.

What I had in mind was a weaker practical goal: assuming planning time
stays acceptable and plan advice can still be used to correct bad cases,
can the default setting reduce the probability of severe bad cases? For
example, using purely made-up numbers, if the new algorithm's default
setting has severe regressions in 10% of cases, can we reduce that to 5%
or lower? The point is to reduce the probability of bad cases, not to
eliminate them.

I am not fully sure yet whether this is the right goal/criterion,
though.

> heuristics, requiring this new signals?

That's fair. The DP-prefix approach still needs a heuristic to choose
the frontier seed, so it does not avoid the ranking problem. What I
meant was mostly about scope, not a strict dependency between the two
directions. The current GOO variants mostly use signals already
available in postgres at that point, such as estimated cost and
estimated result size. If those signals are wrong, different variants
may still share similar failure patterns. To get a substantially
different signal, we might need something outside the current GOO patch.

For example, the CIDR 2021 paper "Simplicity Done Right for Join
Ordering" seems like one possible direction for the first approach. My
current reading is that it is not only changing a local choice inside
the current GOO rule. It also changes the way candidate joins are
formed/connected, and it may need extra statistics about join
attributes, such as maximum value frequency, to make the risk signal
work. That seems broader than only changing the GOO search rule.

That is why I originally looked at the DP-prefix direction first: not
because I think it is definitely the better direction, but because it
seemed more contained to the join search algorithm and could initially
reuse existing signals like cost/result size. Better signals could still
be used later for prefix/frontier selection if that direction turns out
to be useful. I am probably still missing some of the tradeoffs, and I
need to study the paper, the failure cases, and other people's views
more carefully.

After this discussion, it may make more sense to first make the pure GOO
baseline and the evaluation framework clearer, and then decide which
follow-up direction is worth pursuing.

> to GOO? Why not to just leave join_collapse_limit to a low value?

This is a very good question. I need to better understand the current
implementation and think about this more carefully before giving an
answer.

> the planning took, see how many queries got faster/slower, etc.

Agreed. I think we need to test many more large join queries. As
mentioned above, I think it would be useful to keep the current-estimate
and accurate-estimate evaluations separate, because they answer related
but different questions.

> there's not all that many of them.

Yes. In addition to JOB and JOB-Complex, the benchmark repository also
has an extended IMDB-backed workload, `imdb_ceb_3k`, with 842 queries
involving at least 12 base relations [1]. It uses the same IMDB
schema/data family, so it should be a useful larger test set after the
smaller JOB/JOB-Complex subset.

I have not run that full set for this patch yet, but I plan to use it
for the next round of evaluation.

> with adjustable inaccuracy.

That makes sense, but I need to think more about it. I am not sure yet
whether this would be easy to design in a useful way.

References:

[1] Benchmark workloads:
https://github.com/Reminiscent/join-order-benchmark/blob/main/WORKLOADS.md
--
Best regards,
Chengpeng Yan

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 13 May 2026 13:54:20 +0200

> uniform/independent data would have less variation here.

Yes, that's my understanding too. What does that mean for using JOB to
evaluate these patches? If the optimizer does substantial estimation
errors, what can we conclude from heuristics performing well or poorly
on those queries?

I initially though "garbage in, garbage out", but maybe if a heuristics
performs systemically better (on a large number of random test cases),
maybe it handles "risk" better?

> do this now may be trying to do too much at once.

Probably. I understood the goal of GOO to be a drop-in replacement GEQO,
and my intuition is to keep the scope limited to that goal.

That does not mean GOO can't do more later, but I'd definitely structure
it with doing a "simplest possible" GEQO replacement first, and then
maybe do more smart stuff later.

> out of the bigger problem.

Not sure, for two reasons.

How often do we expect this to be used? AFAIK GEQO is not used very
often in practice, because geqo_threshold is so much higher than
join_collapse_limit. So even huge joins get divided into problems
handled by DP. We might invest a lot of time and complexity into
something that gets used extremely rarely ...

Also, couldn't this easily lead to unpredictable planning behavior? Say
the budget relies on counting "make_join_rel" calls, or something like
that. Then someone adds or removes an index on one of the tables, and we
suddenly start to consider fewer/more candidate orders. Or maybe someone
refactors the code a little bit, moving the calls. And suddenly, we hit
the threshold at a different place. But maybe it's OK for a heuristics?

> (I'm not sure how hard adjustable inaccuracy would be)

Yeah, that was my guess too.

regards

-- 
Tomas Vondra

---

From: Tomas Vondra <[email-masked]>
Date: Wed, 13 May 2026 14:22:53 +0200

Hi!

> parts, I think I need more analysis/research before making stronger

That's fine. No one expect you to have all the answers right away. It's
a matter for future research. Also, it's just random ideas, and some of
them may be misguided - feel free to push back against that, please.

> doing a more systematic analysis.

Agreed. Seeing results for joins with accurate estimates would be helpful.

I initially thought we should probably just ignore behavior on examples
with too inaccurate estimates (because the "exact" DP would likely make
bogus decisions too).

But maybe one of the heuristics is somehow more robust, and that seems
like a quality of it's own?

> I am not fully sure yet whether this is the right goal/criterion,

That sounds like a sensible goal. It's more or less what I had in mind
when I proposed evaluating the heuristics on random joins generated by a
script. Seeing on what fraction of the cases is "A" better than "B",
vice versa, by how much, ...

> follow-up direction is worth pursuing.

+1 to do "simple GOO" first, followed by various improvements. It could
even be implemented in one patch series, but structured like that. It
makes review / discussions way simpler.

+1

> for the next round of evaluation.

Maybe it'd make sense to evaluate GEQO/GOO even with smaller joins?

I don't know if that tells us anything, or which geqo_threshold values
are interesting. Maybe not all the way back to 2, because as John wrote
earlier, for small problems GEQO may actually cover the whole space.

But maybe if we run the tests with geqo_threshold=2..12 for joins of
different sizes, it'd tell us a couple things:

a) At which value it starts producing plans different from DP?

b) How the planning time grows for DP/GEQO/GOO, and where the DP gets
too expensive.

c) How the execution time changes for DP/GEQO/GOO.

I honestly don't know what exactly it makes sense to test. In cases like
this I usually run a lot of tests (generated randomly) for different
combinations of parameters, and then "ask questions" on the data.

> whether this would be easy to design in a useful way.

Me neither. But it seems like an interesting thought experiment.

regards

-- 
Tomas Vondra

---

From: John Naylor <[email-masked]>
Date: Thu, 14 May 2026 12:59:55 +0700

> something that gets used extremely rarely ...

That's a risk to keep in mind.

In cases where planning time is a substantial part of the runtime
(like in your thread on OLTP star joins), a user could lower the
threshold for greedy search, since it's fast. That's not an option
currently because GEQO is slow.

With a dynamic strategy, I imagine join_collapse_limit would mean
something different (one technique in the literature is to refine the
greedy output on subproblems of size 4-7), or be replaced with a
different tuning knob.

Anyway, these questions reinforce that this is potential follow-up work.

> the threshold at a different place. But maybe it's OK for a heuristics?

That's a good question.

--
John Naylor
Amazon Web Services

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 14 May 2026 10:49:09 +0200

> currently because GEQO is slow.

Perhaps. But there's also the discussion in [1], where Tom asked if
maybe it's time to update the join_collapse_limit/geqo_threshold
defaults, and Andrei responds join_collapse_limit=40/geqo_threshold=14
worked OK for the case he was investigating.

Those values are not meant to be the new defaults, but chances are it's
time to update the defaults in some way. And that may alter the chance
of actually triggering GEQO.

[1] https://www.postgresql.org/message-id/3525339.1770668216%40sss.pgh.pa.us

Agreed.

regards

-- 
Tomas Vondra