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

Hi hackers,

Attached is a progress report on the current version. The patch has
been rebased onto current master and now respects JOIN_ORDER advice
from pg_plan_advice. It keeps two greedy signals, cost and result_size;
"GOO combined" runs both and keeps the cheaper plan. Other greedy
strategies will be considered as the test set is expanded.

The tests cover 33 JOB/JOB-Complex queries with 12–17 FROM relations,
i.e. at and above the default geqo_threshold (12), on a release build
with 5 ANALYZE statistics snapshots. Planning time comes from EXPLAIN
(FORMAT JSON, SUMMARY ON) without execution; each query is planned
once per snapshot, and the median is used.

The attached archive contains the statistics snapshots
(stats-round-N.sql, from pg_dump --statistics-only), the EXPLAIN
(FORMAT JSON) output of DP, GEQO, and GOO per round (plans/), and a
per-round, per-query summary (plan_only.csv). The snapshots contain no
schema or data; restore them into a prepared JOB database without
re-running ANALYZE.

1) Planning time

Planning time DP GEQO GOO combined
Mean 98.31 ms 21.44 ms 3.20 ms
Max 576.99 ms 31.18 ms 4.97 ms
Total (33 queries) 3244 ms 708 ms 106 ms

GOO is faster than GEQO on all 33/33 queries, about 6.7x faster at the
median.

2) Plan stability across ANALYZE rounds

With the same geqo_seed=0 (the default) and only the 5 statistics
snapshots changing (only re-running ANALYZE), count the number of
different join orders each query had across the five rounds:

Different join orders 1 2 3 4 5
DP 28 4 1 0 0
GEQO 3 6 4 9 11
GOO combined 25 7 0 1 0

The number of queries with the same join order in all five rounds is:
DP 28/33, GEQO 3/33, and GOO 25/33.

3) JOIN_ORDER in pg_plan_advice

Test method: target the DP join order, keep only the JOIN_ORDER advice
without constraining join methods, apply it to GOO and GEQO, and compare
whether the join order matches DP.

Algorithm Reproduced DP join order
GOO combined 165/165
GEQO 3/165

4) Plan quality (total cost)

I use the optimizer's objective function, Total Cost, as the comparison
criterion: when estimates are inaccurate, the estimation errors also
strongly affect execution time, so execution time depends on several
factors besides join search.

Using all 165 query/round samples from the five rounds, compare GOO and
GEQO directly; a difference within 1% counts as a tie:

Comparison GOO better Tie (within 1%) GOO worse
GOO vs GEQO 46 81 38

Regarding the LATERAL issue mentioned earlier: like DP/GEQO, GOO
directly reuses the existing join legality check. That check determines
whether the current two clumps can join, but does not guarantee that
the remaining clumps can still form a complete plan after committing.
DP builds every legal join relation at each level, so a dead end in
one combination can usually be bypassed through others; GEQO may
encounter similar issues. As GOO is improved to explore more candidate
paths, such dead ends should become less frequent, but they cannot be
ruled out entirely. This stage does not add special handling inside
GOO; I will evaluate it separately later as an independent join
legality/completeness issue.

Overall, in these tests GOO plans about 6.7x faster than GEQO, keeps a
much more stable join order across ANALYZE rounds, and follows
JOIN_ORDER advice, while its estimated plan cost is broadly comparable
to GEQO's.

For now, I plan to use GOO as the baseline for further join-search
work: it is simple, is a common and well-studied approach to join
ordering, and in these tests it has low planning overhead, relatively
stable plans, and can be tuned through JOIN_ORDER advice.

Next, I will build further optimizations on top of the GOO greedy
algorithm, trading some additional planning time for better plan
quality within an acceptable range; plain GOO could then also serve
as a fallback when the planning budget is exhausted. I am already
experimenting with such GOO-based improvements, and larger benchmark
results will follow.

--
Best regards,
Chengpeng Yan