MIME-Version: 1.0
References: <3FF63E99-AB4F-41A9-BC78-AAB28823FBD0@Outlook.com>
 <6db6d2ec-7529-4add-9a95-178fc318311d@vondra.me>
 <313ACE5A-CBF1-43B3-9181-10D3E8ADF424@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>
In-Reply-To: <a43d5bc7-4676-48e0-a5ae-d01f29fb97e6@vondra.me>
From: John Naylor <johncnaylorls@gmail.com>
Date: Wed, 13 May 2026 11:34:41 +0700
Message-ID: 
 <CANWCAZZqm9wcn_W0S=V_WSt2h6zGUSQTfz3nFOUoj97=r5z_9A@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/CANWCAZZqm9wcn_W0S%3DV_WSt2h6zGUSQTfz3nFOUoj97%3Dr5z_9A%40mail.gmail.com>
Precedence: bulk

On Tue, May 12, 2026 at 8:42=E2=80=AFPM Tomas Vondra <tomas@vondra.me> wrot=
e:
>
> On 5/12/26 13:51, John Naylor wrote:
> > On Mon, May 11, 2026 at 9:33=E2=80=AFPM Chengpeng Yan <chengpeng_yan@ou=
tlook.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 resu=
lts.

> 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 earlie=
r,
> >> both building on the current GOO work. One is to improve pure-GOO
> >> candidate generation and the final selector, for example by adding mor=
e
> >> diverse strategies and making the selector consider signals beyond fin=
al
> >> estimated cost. The other is to use exact DP for a prefix of the probl=
em
> >> and fall back to GOO when the DP budget is not enough. The first
> >> direction may need broader changes across planner or estimation-relate=
d
> >> 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 (=3D8). If
> these problems are "too large" for DP (geqo_threshold=3D12), 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 >=3D 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