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

Hello Chengpeng,

I finally had some time to look at this patch series again, and I wonder
what are your plans with it for the PG20 cycle.

FWIW attached is a v6 of the most patches, which is merely v5 rebased to
current master (the was a bit of bitrot). I haven't done any changes. I
have a couple minor comments, but but let me share some high level ideas
first about improvements to join search in general.

---

It'd be great to improve or join planning capabilities - people keep
building larger and larger joins, and our join search is not great when
handling such complex joins. People can increase join_collapse_limit,
and maybe it works fine, but it's risky. And GEQO is a bit of a hit and
miss, unfortunately.

So as I already wrote a couple months ago, +100 to working on a GEQO
replacement. I think it'd be a huge step forward for the users, if it
succeeds (and I hope it will).

That being said, I'm a bit unsure about the proposed direction of using
a greedy algorithm in a somewhat simple way.

I happened to be reading some recent papers about join order search,
because of a separate problem of replacing join_collapse_limit with
something less blunt (I'll start a separate thread about it). And there
seems to be a number of very promising approaches to join order search,
some of which seem like a better fit than the proposed GOO.

Let me explain why I think so.

For starters, consider this "join ordering" CMU lecture [1] from 2025.
That's Andy Pavlo's lecture, which generally are great overviews of the
particular field, including the new ides/approaches.

At the beginning, it divided the queries by "size" (number of relations
joined, for simplicity), and it maps these cases to approaches:

1) small => solve optimally

2) medium => search space linearization

3) large => graceful greediness

Our standard_join_search is clearly for the "small" case. I believe GOO
is a "graceful greediness" approach - it certainly does not do any
linearization, at least as I understand it. So it'd be good for "large"
problems (which I think is 1000+ tables).

The way I understand this, this suggests there are approaches that can
do much better for "medium" queries with up to ~1000 tables (and that's
going to be ~99.999% of user queries). So by going to GOO right away,
we're probably failing to find much better plans.

In particular, I find the papers about the "LinDP" family of algorithms
extremely intriguing:

- Adaptive Optimization of Very Large Join Queries (Radke, Neumann),
2018 [2]

- LinDP++: Generalizing Linearized DP to Crossproducts and Non-Inner
Joins (Radke, Neumann), 2019 [3]

- Optimizing Linearized Join Enumeration by Adapting to the Query
Structure (Birler, Stoian, Neumann), 2025 [4]

Highly recommended papers, BTW. It was a fun weekend read. T. Neumann is
a guarantee of a great read.

So maybe we should try implementing one of these algorithms first?

I don't actually think it'd be more code than the current GOO code, and
it seems to have a reasonably sound theory behind it.

Of course, we may still need some "fallback" mode with heuristics, for
joins too large even for the LinDP algorithms. So maybe that's where GOO
would come into play? But do we have an idea how large joins it can
actually solve in practice? Maybe the LinDP algorithms are universally
better, even for large joins?

---

Now, a couple comments about the v5 (or v6) patch.

First, I generally like the code. I haven't done a deep thorough review,
but I find it quite readable. I also like how much smaller it is than
the GEQO code - it's 24kB vs. 172kB. Of course, that only matters if GOO
can do good enough job (compared to GEQO).

While messing with the patch, I fond a relatively simple query that
fails to find a plan:

CREATE TABLE t1 (a int, b int);
CREATE TABLE t2 (a int, b int);
CREATE TABLE t3 (a int, b int);
CREATE TABLE t4 (a int, b int);

SET enable_goo_join_search=on;
SET geqo_threshold = 2;

SELECT 1 FROM
t2 B, t3 C,
LATERAL (SELECT t1.a, t1.b FROM t1 WHERE t1.b = C.a OFFSET 0) A,
LATERAL (SELECT t4.a, t4.b FROM t4 WHERE t4.b = B.a OFFSET 0) D
WHERE A.a = B.a AND C.a = D.a;

ERROR: GOO join search failed: all strategies exhausted without a valid
join order

I'm not really sure what's causing this, but I see GEQO has this comment
about LATERAL joins:

* In particular, we might clump together relations that actually
* mustn't be joined yet due to LATERAL restrictions; since there's no
* provision for un-clumping, this must lead to failure.

Could this be causing issues for GOO? If it merges clumps it shouldn't
have merged, what happens then? Does it just fail?

IMHO that's not a behavior we could accept. A practical join search
algorithm needs to be able to recover in some way, especially if it's
used as a fallback for joins that are "too large" for the DP case.

regards

[1] https://15799.courses.cs.cmu.edu/spring2025/notes/07-joins1.pdf

[2] Adaptive Optimization of Very Large Join Queries

[3] https://db.in.tum.de/~radke/papers/lindp++.pdf

[4] https://db.in.tum.de/~birler/papers/adaptivelindp.pdf

--
Tomas Vondra