MIME-Version: 1.0
References: 
 <CACWDQNX+mFG35dL+CP3BeXRjozJr8HKe3O=_ZPwSTaGQOHoizA@mail.gmail.com>
 <3148f6f9-2429-4ee0-9b1e-860aa1578d4f@vondra.me>
 <CACWDQNU5DUCiC63KJhhuwQga6c=y2yXq+0wZd9J59wovxoAJng@mail.gmail.com>
 <f9fd3172-03d4-4306-babe-a7c88c7cb32c@vondra.me>
 <CACWDQNULuzwQ43VGop5f7JUTOsVLofpMvLih_8vfoRdCJx6+pw@mail.gmail.com>
In-Reply-To: 
 <CACWDQNULuzwQ43VGop5f7JUTOsVLofpMvLih_8vfoRdCJx6+pw@mail.gmail.com>
From: David Rowley <dgrowleyml@gmail.com>
Date: Fri, 31 Oct 2025 14:19:03 +1300
Message-ID: 
 <CAApHDvq2FR2HfXu7Y7h-cfvvJU40e8NX8w=+1TBkF4+wW5H-eA@mail.gmail.com>
Subject: Re: GEQO plans much slower than standard join plans
To: Carlo Sganzerla <carlo@alude.com.br>
Cc: Tomas Vondra <tomas@vondra.me>, pgsql-performance@postgresql.org,
	Rafael Almeida <rafael@alude.com.br>, Leandro Noman <leandro@alude.com.br>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/CAApHDvq2FR2HfXu7Y7h-cfvvJU40e8NX8w%3D%2B1TBkF4%2BwW5H-eA%40mail.gmail.com>
Precedence: bulk

On Thu, 30 Oct 2025 at 03:57, Carlo Sganzerla <carlo@alude.com.br> wrote:
> Yes, I also found that counterintuitive. By turning geqo =3D off (join/fr=
om_collapse_limit were 14) and looking at some metrics we obtained from pg_=
stat_statements, we found that planning times of the affected queries (the =
ones which would make use of GEQO) mostly increased (but not by much), whic=
h is already the documented behavior. However, one particular query with th=
e same structure like the one on treejoin-14-dims.sql (attached to the firs=
t email) had a _decrease_ on planning and execution times, so geqo =3D off =
for this query yielded faster plans than geqo =3D on. This counterintuitive=
 behavior is the reason that I created and shared the script that tried to =
reproduce it. I'm not sure whether you've run it or not, but on every machi=
ne I have run so far I had a 10 fold increase on TPS and a 10 fold decrease=
 on planning times if I turn geqo =3D off.
>
> I guess what I'm trying to show is that, in very particular cases, GEQO m=
ay harm planning times, that's why I felt a little disclaimer could be usef=
ul. I'm not sure what else I can add here.

I think what's happening here is that in the query as you've written
it, there isn't much flexibility in the how the tables are joined.
There are 14 EquivalanceClasses in the 14 table case. "f" cannot be
joined to "c13" without "c12", and joining "c12" requires "c11" and so
on.  For queries that join all on the same column, there'd be fewer
EquivalanceClasses and more flexibility in the join order.

Doing:

\set id random(1,10000)

set join_collapse_limit =3D 14;
set geqo =3D off;

explain (summary on) select * from f
    join c0 on (c0.id =3D f.id)
    join c1 on (c1.id =3D c0.id)
    join c2 on (c1.id =3D c0.id)
    join c3 on (c3.id =3D c2.id)
    join c4 on (c4.id =3D c3.id)
    join c5 on (c5.id =3D c4.id)
    join c6 on (c6.id =3D c5.id)
    join c7 on (c7.id =3D c6.id)
    join c8 on (c8.id =3D c7.id)
    join c9 on (c9.id =3D c8.id)
    join c10 on (c10.id =3D c9.id)
    join c11 on (c11.id =3D c10.id)
    join c12 on (c12.id =3D c11.id)
    join c13 on (c13.id =3D c12.id)
where f.id =3D :id;

Is much slower to plan as it opens up the possibilities for join order
as there's a single EquivalanceClass with 14 members and any
combination is possible.

I've not studied the GEQO code nearly as much as the standard join
search code, but what it seems to do is try random combinations. For
the case you demonstrated in [1], it discovers a large number of pairs
that cannot be joined as there's no join condition between them. I
suspect that's the issue here. The standard search manages to just
incrementally build up towards the final join incrementally as it's
processing the tables in the same order as they appear in the query
and it never hits the case of not finding a join condition between the
pairs it tries.

Maybe there's some way to make GEQO more efficient by precalculating
which pairs might be good ones to try. That likely could be done
fairly efficiently now that we have RelOptInfo.eclass_indexes, or at
least it would help identify ones that there's no point in trying.
Maybe someone wants to study this more than I have and see what might
be possible. I've not quite got the motivation, at least not today.

David

[1] https://www.postgresql.org/message-id/attachment/183634/treejoin-14-dim=
s.sql