MIME-Version: 1.0
References: <3FF63E99-AB4F-41A9-BC78-AAB28823FBD0@Outlook.com>
 <5abd6054-413c-4f48-9172-d8b31062b266@vondra.me>
 <cb313155-24c4-4838-a46b-44968993a6e2@vondra.me>
 <938E2286-9B0D-4F8D-A916-8E0E35D55034@Outlook.com>
 <e82d4302-2450-4915-93a5-7df75f69c385@vondra.me>
 <CANWCAZY529EPHyo1kLnEzjFBq-UaDPc3KErK=ApqDZZ1Oc-XHg@mail.gmail.com>
 <CAFj8pRCO5ocbr-wFWx5QsKdfkW-=XuQ6zkW5FES7ERQZQHtpwQ@mail.gmail.com>
 <982de4a4-71b6-4d1d-afe2-35b1c5d43529@vondra.me>
 <CAFj8pRASJuRQKHOoBTnR5aRUeRKpNAmrYQcBrQb=yqeZ_8me9Q@mail.gmail.com>
 <CAEvyyTi1M6JhHb6sR+xK-kp2bezMoADSC+RY2A+DbdEn+_BLxA@mail.gmail.com>
 <8927A117-A7EA-41E8-94B3-0B4F7767DA8B@outlook.com>
 <DBCBD9E0-27EC-4F50-A568-3E99FCF2F7B7@outlook.com>
 <CANWCAZbbTazxGeMU=qdyi1kBr_Nkjv1n6vZR-hW30QbqVqkx1Q@mail.gmail.com>
 <4383D1E9-8F01-429E-9C18-1EFE12FF9196@outlook.com>
 <CANWCAZaetVkaZnR_fxw1DAUrSJ+sQ1PT6UFdwHarHUNNPzWueg@mail.gmail.com>
 <a43d5bc7-4676-48e0-a5ae-d01f29fb97e6@vondra.me>
 <CANWCAZZqm9wcn_W0S=V_WSt2h6zGUSQTfz3nFOUoj97=r5z_9A@mail.gmail.com>
 <8e9509d3-b6a3-4604-bd26-8777386de216@vondra.me>
In-Reply-To: <8e9509d3-b6a3-4604-bd26-8777386de216@vondra.me>
From: John Naylor <johncnaylorls@gmail.com>
Date: Thu, 14 May 2026 12:59:55 +0700
Message-ID: 
 <CANWCAZZkHwULLrZhyXbsyi5adXjwDTKFX0PZ9Z5pep1zh2=gAw@mail.gmail.com>
Subject: Re: Add a greedy join search algorithm to handle large join problems
To: Tomas Vondra <tomas@vondra.me>
Cc: Chengpeng Yan <chengpeng_yan@outlook.com>,
 lakshmi <lakshmigcdac@gmail.com>,
	Pavel Stehule <pavel.stehule@gmail.com>,
	"pgsql-hackers@lists.postgresql.org" <pgsql-hackers@lists.postgresql.org>,
 Robert Haas <robertmhaas@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CANWCAZZkHwULLrZhyXbsyi5adXjwDTKFX0PZ9Z5pep1zh2%3DgAw%40mail.gmail.com>
Precedence: bulk

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

> >> To got to the GEQO/GOO code, people have to adjust the limits, so that
> >> (join_collapse_limit >=3D geqo_threshold). AFAIK almost no one does th=
at,
> >> so most join problems are smaller that geqo_threshold and so handled b=
y
> >> 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 fro=
m
> >> keeping the (join_collapse_limit < geqo_threshold) and not even gettin=
g
> >> 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