Thread

Add a greedy join search algorithm to handle large join problems

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-02T03:48:26Z

Hi hackers,

This patch implements GOO (Greedy Operator Ordering), a greedy
join-order search method for large join problems, based on Fegaras (DEXA
’98) [1]. The algorithm repeatedly selects, among all legal joins, the
join pair with the lowest estimated total cost, merges them, and
continues until a single join remains. Patch attached.

To get an initial sense of performance, I reused the star join /
snowflake examples and the testing script from the thread in [2]. The
star-join GUC in that SQL workload was replaced with
`enable_goo_join_search`, so the same tests can run under DP (standard
dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
GOO. Other planner settings, including join_collapse_limit, remained at
their defaults.

On my local machine, a single-client pgbench run produces the following
throughput (tps):

                    |    DP    |   GEQO   |    GOO
--------------------+----------+----------+-----------
starjoin    (inner) |  1762.52 |  192.13  |  6168.89
starjoin    (outer) |  1683.92 |  173.90  |  5626.56
snowflake   (inner) |  1829.04 |  133.40  |  3929.57
snowflake   (outer) |  1397.93 |   99.65  |  3040.52

Open questions:
* The paper ranks joins by estimated result size, while this prototype
  reuses the existing planner total_cost. This makes the implementation
  straightforward, but it may be worth exploring row-based rule.
* The prototype allocates through multiple memory contexts, aiming to
  reduce memory usage during candidate evaluation. Suggestions on
  simplification are welcome.
* Planning performance vs GEQO: On the star/snowflake benchmarks above,
  GOO reduces planning time significantly compared to GEQO. Broader
  evaluation on more representative workloads (e.g., TPC-H / TPC-DS /
  JOB) is TODO, covering both planning speed and plan quality.
* There is no tuning knob like `geqo_seed` for GEQO if GOO produces a
  poor ordering.
* The long-term integration is open:
  * fully replace GEQO,
  * keep GEQO available and optionally try both,
  * or use GOO as a starting point for GEQO.

Comments and review would be appreciated.

References:
[1] Leonidas Fegaras, “A New Heuristic for Optimizing Large Queries”,
DEXA ’98. ACM Digital Library:
https://dl.acm.org/doi/10.5555/648311.754892 A publicly accessible
PostScript version is available from the author's page:
https://lambda.uta.edu/order.ps
[2] Star/snowflake join thread and benchmarks:
https://www.postgresql.org/message-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51%40vondra.me


--
Best regards,
Chengpeng Yan

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

Dilip Kumar <dilipbalaut@gmail.com> — 2025-12-02T05:36:50Z

On Tue, Dec 2, 2025 at 9:18 AM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
>
> Hi hackers,
>
> This patch implements GOO (Greedy Operator Ordering), a greedy
> join-order search method for large join problems, based on Fegaras (DEXA
> ’98) [1]. The algorithm repeatedly selects, among all legal joins, the
> join pair with the lowest estimated total cost, merges them, and
> continues until a single join remains. Patch attached.

Interesting.

> To get an initial sense of performance, I reused the star join /
> snowflake examples and the testing script from the thread in [2]. The
> star-join GUC in that SQL workload was replaced with
> `enable_goo_join_search`, so the same tests can run under DP (standard
> dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
> tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
> GOO. Other planner settings, including join_collapse_limit, remained at
> their defaults.
>
> On my local machine, a single-client pgbench run produces the following
> throughput (tps):
>
>                     |    DP    |   GEQO   |    GOO
> --------------------+----------+----------+-----------
> starjoin    (inner) |  1762.52 |  192.13  |  6168.89
> starjoin    (outer) |  1683.92 |  173.90  |  5626.56
> snowflake   (inner) |  1829.04 |  133.40  |  3929.57
> snowflake   (outer) |  1397.93 |   99.65  |  3040.52
>

Is pgbench the right workload to test this, I mean what are we trying
to compare here the planning time taken by DP vs GEQO vs GOO or the
quality of the plans generated by different join ordering algorithms
or both?  All pgbench queries are single table scans and there is no
involvement of the join search, so I am not sure how we can justify
these gains?


-- 
Regards,
Dilip Kumar
Google

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-02T10:22:51Z

Hi,

Thanks for taking a look.

> On Dec 2, 2025, at 13:36, Dilip Kumar <dilipbalaut@gmail.com> wrote:
> 
> Is pgbench the right workload to test this, I mean what are we trying
> to compare here the planning time taken by DP vs GEQO vs GOO or the
> quality of the plans generated by different join ordering algorithms
> or both?  All pgbench queries are single table scans and there is no
> involvement of the join search, so I am not sure how we can justify
> these gains?

Just to clarify: as noted in the cover mail, the numbers are not from
default pgbench queries, but from the star-join / snowflake workloads in
thread [1], using the benchmark included in the v5-0001 patch. These
workloads contain multi-table joins and do trigger join search; you can
reproduce them by configuring the GUCs as described in the cover mail.

The benchmark tables contain no data, so execution time is negligible;
the results mainly reflect planning time of the different join-ordering
methods, which is intentional for this microbenchmark.

A broader evaluation on TPC-H / TPC-DS / JOB is TODO, covering both
planning time and plan quality. That should provide a more
representative picture of GOO, beyond this synthetic setup.

References: 
[1] Star/snowflake join thread and benchmarks:
https://www.postgresql.org/message-id/a22ec6e0-92ae-43e7-85c1-587df2a65f51%40vondra.me

--
Best regards,
Chengpeng Yan

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

Tomas Vondra <tomas@vondra.me> — 2025-12-02T10:56:13Z

On 12/2/25 04:48, Chengpeng Yan wrote:
> Hi hackers,
> 
> This patch implements GOO (Greedy Operator Ordering), a greedy
> join-order search method for large join problems, based on Fegaras (DEXA
> ’98) [1]. The algorithm repeatedly selects, among all legal joins, the
> join pair with the lowest estimated total cost, merges them, and
> continues until a single join remains. Patch attached.
> 
> To get an initial sense of performance, I reused the star join /
> snowflake examples and the testing script from the thread in [2]. The
> star-join GUC in that SQL workload was replaced with
> `enable_goo_join_search`, so the same tests can run under DP (standard
> dynamic programming) / GEQO(Genetic Query Optimizer) / GOO. For these
> tests, geqo_threshold was set to 15 for DP, and to 5 for both GEQO and
> GOO. Other planner settings, including join_collapse_limit, remained at
> their defaults.
> 
> On my local machine, a single-client pgbench run produces the following
> throughput (tps):
> 
>                     |    DP    |   GEQO   |    GOO
> --------------------+----------+----------+-----------
> starjoin    (inner) |  1762.52 |  192.13  |  6168.89
> starjoin    (outer) |  1683.92 |  173.90  |  5626.56
> snowflake   (inner) |  1829.04 |  133.40  |  3929.57
> snowflake   (outer) |  1397.93 |   99.65  |  3040.52
> 

Seems interesting, and also much more ambitious than what I intended to
do in the starjoin thread (which is meant to be just a simplistic
heuristics on top of the regular join order planning).

I think a much broader evaluation will be needed, comparing not just the
planning time, but also the quality of the final plan. Which for the
starjoin tests does not really matter, as the plans are all equal in
this regard.


regards

-- 
Tomas Vondra

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-02T13:04:11Z

Hi,

> On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
> 
> I think a much broader evaluation will be needed, comparing not just the
> planning time, but also the quality of the final plan. Which for the
> starjoin tests does not really matter, as the plans are all equal in
> this regard.

Many thanks for your feedback. 

You are absolutely right — plan quality is also very important. In my
initial email I only showed the improvements in planning time, but did
not provide results regarding plan quality. I will run tests on more
complex join scenarios, evaluating both planning time and plan quality.

Thanks again!
--
Best regards,
Chengpeng Yan

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

Tomas Vondra <tomas@vondra.me> — 2025-12-09T19:20:32Z

On 12/2/25 14:04, Chengpeng Yan wrote:
> Hi,
> 
> 
> 
>> On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
>>
>> I think a much broader evaluation will be needed, comparing not just the
>> planning time, but also the quality of the final plan. Which for the
>> starjoin tests does not really matter, as the plans are all equal in
>> this regard.
> 
> 
> Many thanks for your feedback. 
> 
> You are absolutely right — plan quality is also very important. In my
> initial email I only showed the improvements in planning time, but did
> not provide results regarding plan quality. I will run tests on more
> complex join scenarios, evaluating both planning time and plan quality.
> 

I was trying to do some simple experiments by comparing plans for TPC-DS
queries, but unfortunately I get a lot of crashes with the patch. All
the backtraces look very similar - see the attached example. The root
cause seems to be that sort_inner_and_outer() sees

    inner_path = NULL

I haven't investigated this very much, but I suppose the GOO code should
be calling set_cheapest() from somewhere.

regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2025-12-09T23:30:47Z


On 12/9/25 20:20, Tomas Vondra wrote:
> On 12/2/25 14:04, Chengpeng Yan wrote:
>> Hi,
>>
>>
>>
>>> On Dec 2, 2025, at 18:56, Tomas Vondra <tomas@vondra.me> wrote:
>>>
>>> I think a much broader evaluation will be needed, comparing not just the
>>> planning time, but also the quality of the final plan. Which for the
>>> starjoin tests does not really matter, as the plans are all equal in
>>> this regard.
>>
>>
>> Many thanks for your feedback. 
>>
>> You are absolutely right — plan quality is also very important. In my
>> initial email I only showed the improvements in planning time, but did
>> not provide results regarding plan quality. I will run tests on more
>> complex join scenarios, evaluating both planning time and plan quality.
>>
> 
> I was trying to do some simple experiments by comparing plans for TPC-DS
> queries, but unfortunately I get a lot of crashes with the patch. All
> the backtraces look very similar - see the attached example. The root
> cause seems to be that sort_inner_and_outer() sees
> 
>     inner_path = NULL
> 
> I haven't investigated this very much, but I suppose the GOO code should
> be calling set_cheapest() from somewhere.
> 

FWIW after looking at the failing queries for a bit, and a bit of
tweaking, it seems the issue is about aggregates in the select list. For
example this TPC-DS query fails (Q7):

 select  i_item_id,
        avg(ss_quantity) agg1,
        avg(ss_list_price) agg2,
        avg(ss_coupon_amt) agg3,
        avg(ss_sales_price) agg4
 from store_sales, customer_demographics, date_dim, item, promotion
 where ss_sold_date_sk = d_date_sk and
       ss_item_sk = i_item_sk and
       ss_cdemo_sk = cd_demo_sk and
       ss_promo_sk = p_promo_sk and
       cd_gender = 'F' and
       cd_marital_status = 'W' and
       cd_education_status = 'Primary' and
       (p_channel_email = 'N' or p_channel_event = 'N') and
       d_year = 1998
 group by i_item_id
 order by i_item_id
 LIMIT 100;

but if I remove the aggregates, it plans just fine:

 select i_item_id
 from store_sales, customer_demographics, date_dim, item, promotion
 where ss_sold_date_sk = d_date_sk and
       ss_item_sk = i_item_sk and
       ss_cdemo_sk = cd_demo_sk and
       ss_promo_sk = p_promo_sk and
       cd_gender = 'F' and
       cd_marital_status = 'W' and
       cd_education_status = 'Primary' and
       (p_channel_email = 'N' or p_channel_event = 'N') and
       d_year = 1998
 group by i_item_id
 order by i_item_id
 LIMIT 100;

The backtrace matches the one I already posted, I'm not going to post
that again.

I looked at a couple more failing queries, and removing the aggregates
fixes them too. Maybe there are other issues/crashes, of course.


regards

-- 
Tomas Vondra

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-10T05:20:01Z

Hi,

> On Dec 10, 2025, at 07:30, Tomas Vondra <tomas@vondra.me> wrote:
>
> I looked at a couple more failing queries, and removing the aggregates
> fixes them too. Maybe there are other issues/crashes, of course.

Thanks a lot for pointing this out. I also noticed the same issue when
testing TPC-H Q5. The root cause was that in the goo algorithm I forgot
to handle the case of eager aggregation. This has been fixed in the v2
patch (after the fix, the v2 version works correctly for all TPC-H
queries). I will continue testing it on TPC-DS as well.

Sorry that I didn’t push the related changes earlier. I was running more
experiments on the greedy strategy, and I still needed some time to
organize and analyze the results. During this process, I found that the
current greedy strategy may lead to suboptimal plan quality in some
cases. Because of that, I plan to first evaluate a few basic greedy
heuristics on TPC-H to understand their behavior and limitations. If
there are meaningful results or conclusions, I will share them for
discussion.

Based on some preliminary testing, I’m leaning toward keeping the greedy
strategy simple and explainable, and focusing on the following
indicators together with the planner’s cost estimates:
* join cardinality (number of output rows)
* selectivity (join_size / (left_size * right_size))
* estimated result size in bytes(joinrel->reltarget->width * joinrel->rows)
* cheapest total path cost (cheapest_total_path->total_cost)

At the moment, I’m inclined to prioritize join cardinality with input
size as a secondary factor, but I’d like to validate this step by step:
first by testing these simple heuristics on TPC-H (as a relatively
simple workload) and summarizing some initial conclusions there. After
that, I plan to run more comprehensive experiments on more complex
benchmarks such as JOB and TPC-DS and report the results.

Do you have any thoughts or suggestions on this direction?

Thanks again for your feedback and help.

--
Best regards,
Chengpeng Yan

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

Tomas Vondra <tomas@vondra.me> — 2025-12-10T10:20:14Z

On 12/10/25 06:20, Chengpeng Yan wrote:
> Hi,
> 
>> On Dec 10, 2025, at 07:30, Tomas Vondra <tomas@vondra.me> wrote:
>> 
>> I looked at a couple more failing queries, and removing the aggregates
>> fixes them too. Maybe there are other issues/crashes, of course.
> 
> Thanks a lot for pointing this out. I also noticed the same issue when
> testing TPC-H Q5. The root cause was that in the goo algorithm I forgot
> to handle the case of eager aggregation. This has been fixed in the v2
> patch (after the fix, the v2 version works correctly for all TPC-H
> queries). I will continue testing it on TPC-DS as well.
> 

I can confirm v2 makes it work for planning all 99 TPC-DS queries, i.e.
there are no more crashes during EXPLAIN.

Comparing the plans from master/geqo and master/goo, I see about 80% of
them changed. I haven't done any evaluation of how good the plans are,
really. I'll see if I can get some numbers next, but it'll take a while.

It's also tricky as plan choices depend on GUCs like random_page_cost,
and if those values are not good enough, the optimizer may still end up
with a bad plan. I'm not sure what's the best approach.

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

Where master/geqo means

  geqo_threshold=2

and master/goo means

  geqo_threshold=2
  enable_goo_join_search = on

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.

> Sorry that I didn’t push the related changes earlier. I was running more
> experiments on the greedy strategy, and I still needed some time to
> organize and analyze the results. During this process, I found that the
> current greedy strategy may lead to suboptimal plan quality in some
> cases. Because of that, I plan to first evaluate a few basic greedy
> heuristics on TPC-H to understand their behavior and limitations. If
> there are meaningful results or conclusions, I will share them for
> discussion.
> 
> Based on some preliminary testing, I’m leaning toward keeping the greedy
> strategy simple and explainable, and focusing on the following
> indicators together with the planner’s cost estimates:
> * join cardinality (number of output rows)
> * selectivity (join_size / (left_size * right_size))
> * estimated result size in bytes(joinrel->reltarget->width * joinrel->rows)
> * cheapest total path cost (cheapest_total_path->total_cost)
> 
> At the moment, I’m inclined to prioritize join cardinality with input
> size as a secondary factor, but I’d like to validate this step by step:
> first by testing these simple heuristics on TPC-H (as a relatively
> simple workload) and summarizing some initial conclusions there. After
> that, I plan to run more comprehensive experiments on more complex
> benchmarks such as JOB and TPC-DS and report the results.
> 
> Do you have any thoughts or suggestions on this direction?
> 
> Thanks again for your feedback and help.
> 

No opinion.

IIUC it's a simplified heuristics, replacing the "full" join planning
algorithm. So inevitably there will be cases when it produces plans that
are "worse" than the actual join order planning. I don't have a great
intuition what's the right trade off yet. Or am I missing something?

regards

-- 
Tomas Vondra

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

John Naylor <johncnaylorls@gmail.com> — 2025-12-11T02:53:09Z

On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me> 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.

--
John Naylor
Amazon Web Services

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

Pavel Stehule <pavel.stehule@gmail.com> — 2025-12-11T06:12:29Z

čt 11. 12. 2025 v 3:53 odesílatel John Naylor <johncnaylorls@gmail.com>
napsal:

> On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me> 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.



>
> --
> John Naylor
> Amazon Web Services
>
>
>

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

Tomas Vondra <tomas@vondra.me> — 2025-12-11T17:07:54Z

On 12/11/25 07:12, Pavel Stehule wrote:
> 
> 
> čt 11. 12. 2025 v 3:53 odesílatel John Naylor <johncnaylorls@gmail.com
> <mailto:johncnaylorls@gmail.com>> napsal:
> 
>     On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me
>     <mailto:tomas@vondra.me>> 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.


regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2025-12-11T17:30:46Z

Hi,

Here's a more complete set of results from a TPC-DS run. See the
run-queries-2.sh script for more details. There are also .sql files with
DDL to create the database, etc. It does not include the parts to
generate the data etc. (you'll need to the generator from TPC site).

The attached CSV has results for scales 1 and 10, with 0 and 4 parallel
workers. It runs three configurations:

- master (geqo=off, threshold=12)
- master-geqo (goo=off, threshold=2)
- master-goo (goo=on, threshold=2)

There's a couple more fields, e.g. whether it's cold/cached run, etc.

A very simple summary of the results is the total duration of the run,
for all 99 queries combined:

  scale  workers     caching     master     master-geqo    master-goo
  ===================================================================
      1        0        cold        816             399          1124
                        warm        784             369          1097
               4        cold        797             384          1085
                        warm        774             366          1069
  -------------------------------------------------------------------
     10        0        cold       2760            2653          2340
                        warm       2580            2470          2177
               4        cold       2563            2423          1969
                        warm       2439            2325          1859

This is interesting, and also a bit funny.

The funny part is that geqo seems to do better than master - on scale 1
it's pretty clear, on scale 10 the difference is much smaller.

The interesting part is that "goo" is doing worse than master (or geqo)
on scale 1, and better on scale 10. I wonder how would it do on larger
scales, but I don't have such results.

There's a PDF with per-query results too.

This may be a little bit misleading because the statement timeout was
set to 300s, and there's a couple queries that did not complete before
this timeout. Maybe it'd be better to not include these queries. I
haven't tried, though.

It might be interesting to look at some of the queries that got worse,
and check why. Maybe that'd help you with picking the heuristics?

FWIW I still think no heuristics can be perfect, so getting slower plans
for some queries should not be treated as "hard failure". The other
thing is the quality of plans depends on GUCs like random_page_cost, and
I kept them at default values.

Anyway, I hope this is helpful input.


regards

-- 
Tomas Vondra

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

Pavel Stehule <pavel.stehule@gmail.com> — 2025-12-11T17:33:52Z

čt 11. 12. 2025 v 18:07 odesílatel Tomas Vondra <tomas@vondra.me> napsal:

> On 12/11/25 07:12, Pavel Stehule wrote:
> >
> >
> > čt 11. 12. 2025 v 3:53 odesílatel John Naylor <johncnaylorls@gmail.com
> > <mailto:johncnaylorls@gmail.com>> napsal:
> >
> >     On Wed, Dec 10, 2025 at 5:20 PM Tomas Vondra <tomas@vondra.me
> >     <mailto:tomas@vondra.me>> 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
>
>

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-12T09:50:38Z

> On Dec 10, 2025, at 18:20, Tomas Vondra <tomas@vondra.me> wrote:
> 
> I can confirm v2 makes it work for planning all 99 TPC-DS queries, i.e.
> there are no more crashes during EXPLAIN.

Thanks a lot for testing this — much appreciated.

> It's also tricky as plan choices depend on GUCs like random_page_cost,
> and if those values are not good enough, the optimizer may still end up
> with a bad plan. I'm not sure what's the best approach.

I agree that many other cost-related parameters can influence the join
order. For now, I’m still running my tests with the default settings,
and I’m not entirely sure how large the impact of those cost parameters
will be. This is something I’ll probably consider at a later stage.

> 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.

One additional advantage of goo is that its memory usage should be
better than DP/GEQO (though I haven’t done any measurements yet).
But I don’t think this is the main concern at the moment — I’m just
mentioning it briefly here. What matters more right now is the plan
quality itself.

> On Dec 12, 2025, at 01:30, Tomas Vondra <tomas@vondra.me> wrote:
> 
> A very simple summary of the results is the total duration of the run,
> for all 99 queries combined:
> 
>  scale  workers     caching     master     master-geqo    master-goo
>  ===================================================================
>      1        0        cold        816             399          1124
>                        warm        784             369          1097
>               4        cold        797             384          1085
>                        warm        774             366          1069
>  -------------------------------------------------------------------
>     10        0        cold       2760            2653          2340
>                        warm       2580            2470          2177
>               4        cold       2563            2423          1969
>                        warm       2439            2325          1859
> 
> This is interesting, and also a bit funny.
> 
> The funny part is that geqo seems to do better than master - on scale 1
> it's pretty clear, on scale 10 the difference is much smaller.
> 
> The interesting part is that "goo" is doing worse than master (or geqo)
> on scale 1, and better on scale 10. I wonder how would it do on larger
> scales, but I don't have such results.

It’s interesting to see that goo performs better at scale 10. I’ll try
to dig into the results and understand the reasons behind this in
follow-up work.

> It might be interesting to look at some of the queries that got worse,
> and check why. Maybe that'd help you with picking the heuristics?
> 
> FWIW I still think no heuristics can be perfect, so getting slower plans
> for some queries should not be treated as "hard failure".

I agree that no set of heuristics can be perfect. The best we can do is
to look at existing workloads and understand why certain heuristics
don’t work there, and then evolve them toward strategies that are more
general and more aligned with the nature of joins themselves. There
doesn’t seem to be a silver bullet here — it really comes down to
analyzing specific SQL queries case by case.

Finally, thank you very much for the testing you did and for all the
insights you shared — it helped a lot.

--
Best regards,
Chengpeng Yan

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-16T14:38:03Z

Recently, I have been testing the TPC-H SF=1 dataset using four simple
greedy join-ordering strategies: join cardinality (estimated output
rows), selectivity, estimated result size in bytes, and cheapest total
path cost. These can be roughly seen as either output-oriented
heuristics (rows / selectivity / result size), which try to optimize the
shape of intermediate results, or a cost-oriented heuristic, which
prefers the locally cheapest join step.

The main goal of these experiments is to check whether the current
greedy rules show obvious structural weaknesses, and to use the observed
behavior as input for thinking about how a greedy rule might evolve.
While there is unlikely to be a perfect greedy strategy, I am hoping to
identify approaches that behave reasonably well across many cases and
avoid clear pathological behavior.

In the attached files, v3-0001 is identical to the previously submitted
v2-0001 patch and contains the core implementation of the GOO algorithm.
The v3-0002 patch adds testing-only code to evaluate different greedy
rules, including a GUC (goo_greedy_strategy) used only for switching
strategies during experiments.

All tests were performed on the TPC-H SF=1 dataset. After loading the
data, I ran the following commands before executing the benchmarks:

```
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();
```

The detailed benchmark results are summarized in tpch.pdf. Execution
times are reported as ratios, using the DP-based optimizer’s execution
time as the baseline (1.0).

The compressed archive tpch_tests_result.zip contains summary.csv, which
is the raw data used to generate tpch.pdf and was produced by the
run_job.sh script. It also includes files (xxx_plan.txt), which were
generated by the run_analysis.sh script and record the EXPLAIN ANALYZE
outputs for the same query under different join-ordering algorithms, to
make plan differences easier to compare.

Based on the TPC-H results, my high-level observations are:
* The threeoutput-oriented greedy rules (rows, selectivity, result size)
show noticeable regressions compared to DP overall, with a relatively
large number of outliers.
* Using total path cost as the greedy key produces results that are
generally closer to DP, but still shows some clear outliers.

To understand why these regressions occur, I mainly looked at Q20 and
Q7, which show particularly large and consistent regressions and expose
different failure modes.

In Q20, there is a join between partsupp and an aggregated lineitem
subquery. For this join, the planner’s rowcount estimate is wrong by
orders of magnitude (tens of rows estimated versus hundreds of thousands
actually produced). As a result, output-oriented greedy rules strongly
prefer this join very early, because it appears to be extremely
shrinking. In reality, it processes large inputs and produces a large
intermediate, and this early misordering can significantly amplify
downstream join costs. This makes Q20 a clear outlier for output-based
greedy rules when estimates are severely wrong.

Q7 exposes a different issue. The cost-based greedy rule tends to choose
a locally cheap join early, but that join creates an intermediate which
later joins become much more expensive to process. In this case, an
early commitment under relatively weak constraints leads to a
many-to-many intermediate that is only filtered after fact-table joins
are applied. This illustrates how a purely cost-driven greedy rule can
make locally reasonable decisions that turn out to be globally harmful.

Taken together, these outliers suggest that all four single-metric
greedy rules tested so far have structural limitations. Output-oriented
rules appear fragile when join rowcount estimates are badly wrong, while
cost-oriented greedy decisions can still lead to locally reasonable but
globally poor plans.

One question this naturally raises is whether making irreversible greedy
choices based only on a local ranking signal is sufficient, or whether
some mechanism is needed to make the approach more robust and to limit
the impact of such outliers.

As a next step, based on the current results, I plan to ignore
selectivity (which performs poorly in many cases), treat rows as largely
redundant with result_size, and move on to testing on the JOB benchmark.
I also plan to compare the behavior of DP, GEQO, and GOO on JOB, and to
use those results to better understand which signals are most useful for
guiding greedy decisions.

I would be very interested in hearing people’s thoughts on these
observations and on possible directions to explore next.


--
Best regards,
Chengpeng Yan

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

Tomas Vondra <tomas@vondra.me> — 2025-12-27T17:00:10Z

Hi,

On 12/16/25 15:38, Chengpeng Yan wrote:
> Recently, I have been testing the TPC-H SF=1 dataset using four simple
> greedy join-ordering strategies: join cardinality (estimated output
> rows), selectivity, estimated result size in bytes, and cheapest total
> path cost. These can be roughly seen as either output-oriented
> heuristics (rows / selectivity / result size), which try to optimize the
> shape of intermediate results, or a cost-oriented heuristic, which
> prefers the locally cheapest join step.
> 
> The main goal of these experiments is to check whether the current
> greedy rules show obvious structural weaknesses, and to use the observed
> behavior as input for thinking about how a greedy rule might evolve.
> While there is unlikely to be a perfect greedy strategy, I am hoping to
> identify approaches that behave reasonably well across many cases and
> avoid clear pathological behavior.
> 
> In the attached files, v3-0001 is identical to the previously submitted
> v2-0001 patch and contains the core implementation of the GOO algorithm.
> The v3-0002 patch adds testing-only code to evaluate different greedy
> rules, including a GUC (goo_greedy_strategy) used only for switching
> strategies during experiments.
> 
> All tests were performed on the TPC-H SF=1 dataset. After loading the
> data, I ran the following commands before executing the benchmarks:
> 
> ```
> 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();
> ```
> 

You realize this does not actually change shared buffers size, right?
Because that requires a restart, not just pg_reload_conf. Are you sure
you're running with 4GB shared buffers?

> The detailed benchmark results are summarized in tpch.pdf. Execution
> times are reported as ratios, using the DP-based optimizer’s execution
> time as the baseline (1.0).
> 
> The compressed archive tpch_tests_result.zip contains summary.csv, which
> is the raw data used to generate tpch.pdf and was produced by the
> run_job.sh script. It also includes files (xxx_plan.txt), which were
> generated by the run_analysis.sh script and record the EXPLAIN ANALYZE
> outputs for the same query under different join-ordering algorithms, to
> make plan differences easier to compare.
> 

I'm not sure SF=1 is sufficient for making any clear conclusions. No
matter what the shared_buffers value is, it's going to fit into RAM, the
runs are going to be fully cached.

> Based on the TPC-H results, my high-level observations are:
> * The threeoutput-oriented greedy rules (rows, selectivity, result size)
> show noticeable regressions compared to DP overall, with a relatively
> large number of outliers.
> * Using total path cost as the greedy key produces results that are
> generally closer to DP, but still shows some clear outliers.
> 
> To understand why these regressions occur, I mainly looked at Q20 and
> Q7, which show particularly large and consistent regressions and expose
> different failure modes.
> 
> In Q20, there is a join between partsupp and an aggregated lineitem
> subquery. For this join, the planner’s rowcount estimate is wrong by
> orders of magnitude (tens of rows estimated versus hundreds of thousands
> actually produced). As a result, output-oriented greedy rules strongly
> prefer this join very early, because it appears to be extremely
> shrinking. In reality, it processes large inputs and produces a large
> intermediate, and this early misordering can significantly amplify
> downstream join costs. This makes Q20 a clear outlier for output-based
> greedy rules when estimates are severely wrong.
> 

I don't quite see how we could make good decisions if the estimates are
this wrong. Garbage in, garbage out. AFAICS this affects both the
regular DP planning, which heavily relies on the costing, but also the
approaches on heuristics, which still rely on estimates in some way.

If the aggregate subquery is 1000x off, why should any of the following
decisions be right? The approaches may have different tolerance for
estimation errors - some may be "defensive" and handle misestimates
better, but the trade off is that it may pick slower plans when the
estimates are exact.

I don't think there's an "optimal" approach picking the best plan in
both cases. If there was, join ordering wouldn't be such a challenge.

> Q7 exposes a different issue. The cost-based greedy rule tends to choose
> a locally cheap join early, but that join creates an intermediate which
> later joins become much more expensive to process. In this case, an
> early commitment under relatively weak constraints leads to a
> many-to-many intermediate that is only filtered after fact-table joins
> are applied. This illustrates how a purely cost-driven greedy rule can
> make locally reasonable decisions that turn out to be globally harmful.
> 
> Taken together, these outliers suggest that all four single-metric
> greedy rules tested so far have structural limitations. Output-oriented
> rules appear fragile when join rowcount estimates are badly wrong, while
> cost-oriented greedy decisions can still lead to locally reasonable but
> globally poor plans.
> 

I don't think Q20 is about greediness. Poor estimates are going to be an
issue for all approaches relying on them in some way.

The issue with Q7 seems pretty inherent to greedy algorithms. Picking
solutions that are optimal locally but not globally is the definition of
"greedy". I don't think it matters which exact metric is used, this flaw
is built-in. And I don't think it's solvable.

> One question this naturally raises is whether making irreversible greedy
> choices based only on a local ranking signal is sufficient, or whether
> some mechanism is needed to make the approach more robust and to limit
> the impact of such outliers.
> 

Sufficient for what? Sufficient to replace DP or to replace GEQO?

I don't think we'd want to replace DP with such greedy algorithm. With
accurate estimates and modest number of joins, we should be able to find
the best join (more or less).

But this thread is not about replacing DP, I see GOO more as a GEQO
replacement, right? Or did the goal change?

> As a next step, based on the current results, I plan to ignore
> selectivity (which performs poorly in many cases), treat rows as largely
> redundant with result_size, and move on to testing on the JOB benchmark.
> I also plan to compare the behavior of DP, GEQO, and GOO on JOB, and to
> use those results to better understand which signals are most useful for
> guiding greedy decisions.
> 

I'm not sure ignoring selectivity entirely is a good plan, though. Yes,
if the selectivity/estimate is significantly off, the plan may be poor.
But what exactly do you plan to use instead? Isn't a lot of the metrics
(output size, ...) derived from the selectivity/estimate anyway?

I agree the JOB benchmark may be a better fit for this. The TPC-H is
pretty simple, and even for TPC-DS the number of joins is not all that
high. Sorry if my initial feedback suggested these are the proper
benchmarks to evaluate this.

I suggest the evaluation should focus on cases where we expect GOO to
actually be used in practice - as a replacement for GEQO. Only when it
proves useful/acceptable for that use case (for sufficiently many joins
etc.), we can start comparing with DP to figure out if we need to adjust
the thresholds and so on.

Another suggestion is to also test with larger data sets. The problems
with SF=10 or SF=100 may be very different, even with TPC-H. Also,
consider testing with "cold" cases, as if there's nothing cached by
restarting the Postgres instance and drop page cache between runs.

> I would be very interested in hearing people’s thoughts on these
> observations and on possible directions to explore next.
> 

I realized the paper mentioned at the beginning of this thread is from
1998. That doesn't make it wrong, but I was wondering if there are some
newer papers about join order search, with interesting
alternative/better approaches.

An interesting paper I found is this CIDR21 paper:

Simplicity Done Right for Join Ordering
Axel Hertzschuch, Claudio Hartmann, Dirk Habich, Wolfgang Lehner
https://vldb.org/cidrdb/2021/simplicity-done-right-for-join-ordering.html
https://vldb.org/cidrdb/papers/2021/cidr2021_paper01.pdfl

Which does something similar to our approach, although it seems to be
more a replacement for the DP and not just for GEQO. It's meant to be
cheaper, but also more resilient to poor join orders, as it cares about
"upper bound" (~worst case) for the join orders.

It goes beyond the scope of GOO, as the paper also talks about sampling
to determine some of the estimates. But maybe it'd be useful (better
than GEQO) even without that?

I find the focus on the "worst case" (and only trusting baserel
estimates) interesting. I wonder if it might help with the common
nestloop problem, where we opt to believe a very optimistic low
cardinality estimate, only to end with a sequence of nestloops that
never complete.

regards

-- 
Tomas Vondra

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2025-12-28T02:54:16Z

> On Dec 28, 2025, at 01:00, Tomas Vondra <tomas@vondra.me> wrote:
> 
> You realize this does not actually change shared buffers size, right?
> Because that requires a restart, not just pg_reload_conf. Are you sure
> you're running with 4GB shared buffers?

Good catch, and sorry for not mentioning that explicitly. I did restart
the instance and verified that the new shared_buffers setting was in
effect. I’ll make sure to call this out clearly in future descriptions.

> I'm not sure SF=1 is sufficient for making any clear conclusions. No
> matter what the shared_buffers value is, it's going to fit into RAM, the
> runs are going to be fully cached.

Thanks for the comment. I agree that TPC-H at SF=1 is too small to
support strong conclusions. I mainly used SF=1 as a convenient starting
point to quickly validate ideas and iterate on the implementation. I’ve
already run experiments on JOB and plan to share those results next,
where the behavior should be more representative and the conclusions
more meaningful.

> I don't quite see how we could make good decisions if the estimates are
> this wrong. Garbage in, garbage out. AFAICS this affects both the
> regular DP planning, which heavily relies on the costing, but also the
> approaches on heuristics, which still rely on estimates in some way.
> 
> If the aggregate subquery is 1000x off, why should any of the following
> decisions be right? The approaches may have different tolerance for
> estimation errors - some may be "defensive" and handle misestimates
> better, but the trade off is that it may pick slower plans when the
> estimates are exact.
> 
> I don't think there's an "optimal" approach picking the best plan in
> both cases. If there was, join ordering wouldn't be such a challenge.
> 
> I don't think Q20 is about greediness. Poor estimates are going to be an
> issue for all approaches relying on them in some way.
> 
> The issue with Q7 seems pretty inherent to greedy algorithms. Picking
> solutions that are optimal locally but not globally is the definition of
> "greedy". I don't think it matters which exact metric is used, this flaw
> is built-in. And I don't think it's solvable.

I agree that all approaches are affected by estimation errors, but as
you noted, they differ in how much error they can tolerate. In its
current form, GOO is still quite fragile in this respect and can exhibit
severe regressions when estimates are badly off. Based on additional
experiments, I also agree that a single greedy rule inevitably has cases
where it performs extremely poorly; as a result, my current direction is
no longer to further tune the greedy criterion itself, but to improve
the robustness of the existing greedy choices through additional
mechanisms.

Regarding Q20, I agree that this is not fundamentally a “greedy” issue.
If the rowcount estimates were reasonably accurate, the extreme behavior
observed there would likely be avoided. At the same time, when estimates
are wrong by orders of magnitude, the current GOO approach does not
handle this well, and improving robustness under such severe
misestimation is exactly one of the main aspects I am currently working
on.

I have already run additional experiments in this direction, using
result_size and cost as the base signals, and will share the results
separately.

> Sufficient for what? Sufficient to replace DP or to replace GEQO?
> 
> I don't think we'd want to replace DP with such greedy algorithm. With
> accurate estimates and modest number of joins, we should be able to find
> the best join (more or less).
> 
> But this thread is not about replacing DP, I see GOO more as a GEQO
> replacement, right? Or did the goal change?

The goal has always been to use GOO as a replacement for GEQO, not DP.

> I'm not sure ignoring selectivity entirely is a good plan, though. Yes,
> if the selectivity/estimate is significantly off, the plan may be poor.
> But what exactly do you plan to use instead? Isn't a lot of the metrics
> (output size, ...) derived from the selectivity/estimate anyway?
> 
> I agree the JOB benchmark may be a better fit for this. The TPC-H is
> pretty simple, and even for TPC-DS the number of joins is not all that
> high. Sorry if my initial feedback suggested these are the proper
> benchmarks to evaluate this.
> 
> I suggest the evaluation should focus on cases where we expect GOO to
> actually be used in practice - as a replacement for GEQO. Only when it
> proves useful/acceptable for that use case (for sufficiently many joins
> etc.), we can start comparing with DP to figure out if we need to adjust
> the thresholds and so on.
> 
> Another suggestion is to also test with larger data sets. The problems
> with SF=10 or SF=100 may be very different, even with TPC-H. Also,
> consider testing with "cold" cases, as if there's nothing cached by
> restarting the Postgres instance and drop page cache between runs.

Thanks for the feedback.

I’ve already run experiments on the JOB benchmark and will share the
results shortly, including a comparison against GEQO, with DP used as a
baseline. I agree that the primary goal at this stage is to show that
the approach is good enough for the intended use case first, before
looking into secondary aspects such as threshold tuning.

Larger scale factors and cold-cache runs are also part of my upcoming
evaluation plan, and I agree those are important dimensions to cover.

Regarding selectivity, I agree the situation is not entirely clear-cut.
As you noted, result_size is also derived from selectivity to some
extent, and many bad cases share similar characteristics. However, in my
initial TPC-H SF=1 experiments, selectivity-based greedy rules already
showed many poor cases, and I expect this to become worse in more
complex scenarios. For now, I therefore focused on cost and result_size:
cost because it is a first-class concept in PostgreSQL, and result_size
because it is commonly cited in the literature as a more robust signal
for greedy join ordering. If you think selectivity is still an important
signal to evaluate, I can certainly add further experiments for it, but
based on the above I have not pursued additional selectivity-focused
tests so far.
> 
> I realized the paper mentioned at the beginning of this thread is from
> 1998. That doesn't make it wrong, but I was wondering if there are some
> newer papers about join order search, with interesting
> alternative/better approaches.
> 
> An interesting paper I found is this CIDR21 paper:
> 
> Simplicity Done Right for Join Ordering
> Axel Hertzschuch, Claudio Hartmann, Dirk Habich, Wolfgang Lehner
> https://vldb.org/cidrdb/2021/simplicity-done-right-for-join-ordering.html
> https://vldb.org/cidrdb/papers/2021/cidr2021_paper01.pdfl
> 
> Which does something similar to our approach, although it seems to be
> more a replacement for the DP and not just for GEQO. It's meant to be
> cheaper, but also more resilient to poor join orders, as it cares about
> "upper bound" (~worst case) for the join orders.
> 
> It goes beyond the scope of GOO, as the paper also talks about sampling
> to determine some of the estimates. But maybe it'd be useful (better
> than GEQO) even without that?
> 
> I find the focus on the "worst case" (and only trusting baserel
> estimates) interesting. I wonder if it might help with the common
> nestloop problem, where we opt to believe a very optimistic low
> cardinality estimate, only to end with a sequence of nestloops that
> never complete.

Thanks for the pointer. I’ve also been looking at more recent work on
join ordering, and there are indeed several ideas that seem relevant to
the current direction, including the paper you mentioned. These are
definitely directions I plan to consider more seriously.

My current plan is to first establish a reasonably solid baseline using
relatively simple techniques—reducing extreme regressions and getting
overall plan quality closer to DP. Once that is in place, I’d like to
step back, summarize which recent papers and ideas seem most applicable,
and then experiment with more advanced approaches incrementally,
building on that foundation.

Thanks for all the detailed feedback and the many useful insights
throughout this discussion.

--
Best regards,
Chengpeng Yan

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-05-03T12:46:46Z

> On Feb 14, 2026, at 13:39, Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
>
> 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.

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

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

John Naylor <johncnaylorls@gmail.com> — 2026-05-05T05:40:13Z

On Sun, May 3, 2026 at 7:46 PM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
> > On Feb 14, 2026, at 13:39, Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
> > 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.

> 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

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.

> 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.

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

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-05-11T14:33:50Z

Hi,

> On May 5, 2026, at 13:40, John Naylor <johncnaylorls@gmail.com> wrote:
>
> 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.

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:

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

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

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

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.

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

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

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

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.

>> 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.
>
> 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.

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

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

John Naylor <johncnaylorls@gmail.com> — 2026-05-12T11:51:50Z

On Mon, May 11, 2026 at 9:33 PM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:

> > On May 5, 2026, at 13:40, John Naylor <johncnaylorls@gmail.com> wrote:
> > 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.
>
> 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].

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"

> 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.

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

> 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.

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.

> 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,

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
> share the code and numbers once I have a clearer result.

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

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

Tomas Vondra <tomas@vondra.me> — 2026-05-12T13:42:32Z

On 5/12/26 13:51, John Naylor wrote:
> On Mon, May 11, 2026 at 9:33 PM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
> 
>> ...
>> 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.
> 
> 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.
> 

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.

>> 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,
> 
> 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?

>> so I am currently focusing more on the second direction and will
>> share the code and numbers once I have a clearer result.
> 
> 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.
> 

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?

> 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)
> 

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

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

John Naylor <johncnaylorls@gmail.com> — 2026-05-13T04:34:41Z

On Tue, May 12, 2026 at 8:42 PM Tomas Vondra <tomas@vondra.me> wrote:
>
> On 5/12/26 13:51, John Naylor wrote:
> > On Mon, May 11, 2026 at 9:33 PM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:

> >> 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.
> >
> > 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.
> >
>
> 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.

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
> the good and bad runs.

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.

> >> 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,
> >
> > 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.

Agreed.

> 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?

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 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?

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.

> 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.

+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

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

Chengpeng Yan <chengpeng_yan@outlook.com> — 2026-05-13T06:06:16Z

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 <tomas@vondra.me> wrote:
> 
> 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 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.

> 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.

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.

> 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?

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.

> 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?

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

> 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.

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.

> 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.

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.

> 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.

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

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

Tomas Vondra <tomas@vondra.me> — 2026-05-13T11:54:20Z


On 5/13/26 06:34, John Naylor wrote:
> On Tue, May 12, 2026 at 8:42 PM Tomas Vondra <tomas@vondra.me> wrote:
>>
>> On 5/12/26 13:51, John Naylor wrote:
>>> On Mon, May 11, 2026 at 9:33 PM Chengpeng Yan <chengpeng_yan@outlook.com> wrote:
> 
>>>> 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.
>>>
>>> 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.
>>>
>>
>> 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.
> 
> 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
>> the good and bad runs.
> 
> 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.
> 

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?

>>>> 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,
>>>
>>> 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.
> 
> Agreed.
> 
>> 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?
> 
> 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.
> 

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.

>> 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?
> 
> 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.
> 

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?


>> 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.
> 
> +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)
> 

Yeah, that was my guess too.


regards

-- 
Tomas Vondra

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

Tomas Vondra <tomas@vondra.me> — 2026-05-13T12:22:53Z

Hi!

On 5/13/26 08:06, Chengpeng Yan wrote:
> 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.
> 

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.

>> On May 12, 2026, at 21:42, Tomas Vondra <tomas@vondra.me> wrote:
>>
>> 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 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.
> 

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?

>> 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.
> 
> 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.
> 

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, ...

>> 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?
> 
> 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.
> 

+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.


>> 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?
> 
> This is a very good question. I need to better understand the current
> implementation and think about this more carefully before giving an
> answer.
> 
>> 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.
> 
> 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.
> 

+1

>> 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.
> 
> 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.
> 

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.

>> 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.
> 
> 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.
> 

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


regards

-- 
Tomas Vondra

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

John Naylor <johncnaylorls@gmail.com> — 2026-05-14T05:59:55Z

On Wed, May 13, 2026 at 6:54 PM Tomas Vondra <tomas@vondra.me> wrote:
>
> On 5/13/26 06:34, John Naylor wrote:
> > On Tue, May 12, 2026 at 8:42 PM Tomas Vondra <tomas@vondra.me> wrote:

> >> 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?
> >
> > 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.
> >
>
> 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 ...

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.

> 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?

That's a good question.

--
John Naylor
Amazon Web Services

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

Tomas Vondra <tomas@vondra.me> — 2026-05-14T08:49:09Z


On 5/14/26 07:59, John Naylor wrote:
> On Wed, May 13, 2026 at 6:54 PM Tomas Vondra <tomas@vondra.me> wrote:
>>
>> On 5/13/26 06:34, John Naylor wrote:
>>> On Tue, May 12, 2026 at 8:42 PM Tomas Vondra <tomas@vondra.me> wrote:
> 
>>>> 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?
>>>
>>> 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.
>>>
>>
>> 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 ...
> 
> 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.
> 

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

> 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.
> 

Agreed.


regards

-- 
Tomas Vondra