Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1vrsXB-00AnYL-0C for pgsql-hackers@arkaria.postgresql.org; Mon, 16 Feb 2026 06:56:41 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.96) (envelope-from ) id 1vrsX9-00447w-3D for pgsql-hackers@arkaria.postgresql.org; Mon, 16 Feb 2026 06:56:40 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1vrsX9-00447o-1Q for pgsql-hackers@lists.postgresql.org; Mon, 16 Feb 2026 06:56:39 +0000 Received: from mail-dl1-x1243.google.com ([2607:f8b0:4864:20::1243]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.98.2) (envelope-from ) id 1vrsX6-00000000qU6-15GN for pgsql-hackers@lists.postgresql.org; Mon, 16 Feb 2026 06:56:38 +0000 Received: by mail-dl1-x1243.google.com with SMTP id a92af1059eb24-1233bc1117fso2643745c88.0 for ; Sun, 15 Feb 2026 22:56:37 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1771224996; cv=none; d=google.com; s=arc-20240605; b=fcABmqY4RV8cHUZ39zj4Qv9FnvsHYPM3uRdeJCTMFMiGO6hya168xyj5xEAhZ+zcxz OeKB6B9NjvQCZdws8IMZTn9J3oEXYEP++Lft/y17MpHaEFMTs8GTKkYkli3qjuvTs8ca WwsHcKdk/ync0thR2mYHP5vQ1DrlbUXtI0qxArG5iSH4ipgvSazJLRHaHp1tWubzidTE D6mt1CM7/KkkWRgKTIZ2TKyvYi+uCoJPz/AqhdP/Th7MhXCJnllHVEtRv15/1Cb4+ovY RSa4xtOwbCsgq9gfkGvGXjRMpkGUA3yVgus3w8MB05xCKa7ikuIuKCG4zDJeY3WkSbjh 0HmQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=EGwjEQPBPoIjVkc0jP4EhSwXiBp0/wL1JgEa/q5voJw=; fh=n2i5kcT7Vn0AyL4e4aYmQNto/SRoG1OjXL8cUbHcyxA=; b=HnvChk9unzV1Yo6yWmomtOvnv6qbaK9lB1Aw7hSFjUw8YndaO/zyuMyQQdSflUMYEn wywTDVhsJFnsTz0RY7JfmcgU1ssYW74qTB/kSkRhRq5NW3rnJpVf2jdQIifgZ2W9nszn yFdwooZl04DJOurZbCw184U+6UC+jn0qGnE2pNp8zrQBmg7Pe1VMkp+3cOCGqWWBYuyH 6UHbTfjrq3kDsvDlG9FNIhgNy1hFEh0coPrtOmZ8NjuQIrXP32TJhBLhyqr/P9lEGXNz kfxqLZjstma3iR6k/kTWOJgPfGHKM9/uGnn2bpNkGsxnGQiqdGRGCppQBi9xuJU+5ok+ aCiA==; darn=lists.postgresql.org ARC-Authentication-Results: i=1; mx.google.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1771224996; x=1771829796; darn=lists.postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=EGwjEQPBPoIjVkc0jP4EhSwXiBp0/wL1JgEa/q5voJw=; b=f3nku7Bn+Qf8X2LhSSL8BABrSfFkfmnP0uHkKfSiStPGKolITwJsEXFfSr/9z9x/hQ ufYlqecjsbMm2KU2OPvZSflXR6fm8FikgADpGmAWAGVZ4Gui2GsP8qQE8Q22ikv05AoU 0en3m1x4VbvQ87F2Ij+x4uD7G9jDj7u3+nzJigaSohhaRJdFvAAppeAP8DecdVBM4h+2 p+/vxmEWFDgQMbwszCMP6eRPRSuqsdCU3HAdpcuzZ5nxwskaMN1IQOq3xLsM4lBsySR2 cuaMs2E97lJWnWlcZ1UDC5LnYUbahHhk2kV/JqQLFvyVll0Su/o/VNlgOKkorBPQYuhZ HHaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1771224996; x=1771829796; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-gg:x-gm-message-state:from:to:cc:subject:date :message-id:reply-to; bh=EGwjEQPBPoIjVkc0jP4EhSwXiBp0/wL1JgEa/q5voJw=; b=jCyd7CKaPwdr0YbkKFNTcjXOQS+U+4hFjl9Fo2Sb4M8z2IhcC0XmRkAa16ODZeSYEm RNnmBwouk40Gfy0PqPd+5meNjLSZoXUEnDRd4pa1FjYAAYX2KbqkZZ1x44+K5xM54xya AJlLKCqCFVcVzLq5mxBLFL4dnNjdl+W8lRSRgiFS8ugHtXd5fNP8ujFFdKKCou/ixTbG 1J8ymEqEh6iAviyU90JT2g9Bzd9yqNjqNJT6JV7Dy7tCEyBB74CPoiNxI2h22vPzYh7h XnvVvOVFpxyjIHSLFASdA+IFMHBPELyx3ybGSt2qYFRPw5SlVKwnAPGuyECRlPs8KMtM VMAg== X-Forwarded-Encrypted: i=1; AJvYcCWjvLNRDYnZI8Ajd6tZOrnSKoHcw5Dr0kTLyfuLyLvP6vMTPf73ngrLcsTkhJIr3E5/5aWGeebUR/gKanzm@lists.postgresql.org X-Gm-Message-State: AOJu0YwkAbMNnbZWTiKelB6/Jau7f6SNk/sGoDHw7TuRqdF3ZTD2l6gm L6C29k2+wGtUbdyf0vZsRgSEV5/PgPgHFFb+OUzP1CfExXl9t//ZTMFqVb4jOgTEyek6AfNmyxa UXrKf4yHiz6AUJwUu2RoLfh9PlOf8iiONDDkCXtU= X-Gm-Gg: AZuq6aKiGTw1SIYD3ML6f6mbQ9sl8XIXeiriZkGgAIbo/VzF86cp1nm+E2jJwzDf3l4 Pn8pB9enzUjRSC1IMQK3quV96u0aRLFfmy5jzr//JMjen34c0ZNjvio5rQJqqEfIhowgRtakigT PnLFpOB34rmbdBzcW8dweX/N6FP/6RGAnv4cQpRFeBI32SelqgBJcXx145kZPxXzh8yWvBYEqo5 scpztAE/Nnl2SByQccNq/ManieqoRP+mwnHDgAcEraWIwvMckIb/SaVwz1jwycl2d2tCEiTOMie U/df1vw= X-Received: by 2002:a05:7301:4106:b0:2ba:6484:24c9 with SMTP id 5a478bee46e88-2bac71d477fmr3805474eec.2.1771224996017; Sun, 15 Feb 2026 22:56:36 -0800 (PST) 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> <938E2286-9B0D-4F8D-A916-8E0E35D55034@Outlook.com> <982de4a4-71b6-4d1d-afe2-35b1c5d43529@vondra.me> <8927A117-A7EA-41E8-94B3-0B4F7767DA8B@outlook.com> In-Reply-To: From: lakshmi Date: Mon, 16 Feb 2026 12:29:24 +0530 X-Gm-Features: AaiRm52a0CmdnHurBUPx2s6RZfdycp2xCz8sIfj2gDOngbf4ymf0CXGBxqpPu40 Message-ID: Subject: Re: Add a greedy join search algorithm to handle large join problems To: Chengpeng Yan Cc: Pavel Stehule , Tomas Vondra , John Naylor , "pgsql-hackers@lists.postgresql.org" Content-Type: multipart/alternative; boundary="000000000000b47910064aeb74a9" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000b47910064aeb74a9 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Chengpeng, I ran a quick comparison of the GOO v5 greedy strategies on a multi-join workload to look at execution quality in addition to planning time. Here are the results from one representative query: -cost: planning ~1.8 ms | execution ~32.8 ms -result_size: planning ~2.1 ms | execution ~29.3 ms -combined: planning ~3.7 ms | execution ~29.4 ms All three strategies keep planning time very low, which continues to support GOO=E2=80=99s intended scalability advantage over DP and GEQO. In this test, the cost strategy shows noticeably higher execution time, while result_size and combined produce similar and better execution performance. Since combined has slightly higher planning overhead without a clear execution benefit here, result_size appears to provide the best trade-off for this synthetic workload. I plan to continue testing with a few JOB-based queries to evaluate plan quality in a more realistic setting and will share further results if anything notable appears. Thanks again for the continued work on this patch series. Regards, Lakshmi On Mon, Feb 16, 2026 at 11:57=E2=80=AFAM lakshmi w= rote: > Hi Chengpeng, > > I tested the v5 patch on a clean build from current PostgreSQL master.The > patch applied cleanly, the server built successfully, and make > check-world passed without new failures. > I then compared DP, GEQO, and GOO on synthetic multi-join workloads. > > *15-table join* > > - > > DP: planning ~19.1 ms | execution ~21.0 ms > - > > GEQO: planning ~46.6 ms | execution ~17.7 ms > - > > GOO v5: planning ~1.0 ms | execution ~19.5 ms > > *20-table join* > > - > > DP: planning ~25.1 ms | execution ~28.2 ms > - > > GEQO: planning ~27.5 ms | execution ~23.5 ms > - > > GOO v5: planning ~1.5 ms | execution ~28.9 ms > > Across both join sizes, GOO v5 keeps planning time extremely low (roug= hly > an order of magnitude lower than DP/GEQO) while execution times remain > in a comparable range, with no obvious regressions in this synthetic > workload. This appears consistent with the goal of reducing planning > overhead for large join problems while preserving similar plan quality= . > > These tests use controlled synthetic joins rather than JOB/TPC-H, so > they mainly validate planning-time scaling and basic plan sanity. I pl= an to > continue with more realistic workloads and strategy comparisons and wi= ll > share further results if anything notable appears. > > Thanks for the continued work on this patch series. > > Regards, > Lakshmi > > > On Sat, Feb 14, 2026 at 11:09=E2=80=AFAM Chengpeng Yan > wrote: > >> >> > 2026=E5=B9=B42=E6=9C=8813=E6=97=A5 19:14=EF=BC=8Clakshmi =E5=86=99=E9=81=93=EF=BC=9A >> > >> > HI all, >> > I tested the latest GOO patch (v4) on a fresh build from the current >> PostgreSQL master. The patch applied cleanly, the server built without >> issues, and regression tests passed except for the expected EXPLAIN outp= ut >> differences due to the new join ordering behavior. >> > >> > As a quick sanity check, I compared DP, GEQO, and GOO on a small >> multi-join query: >> > >> > DP planning: ~0.66 ms >> > GEQO planning: ~2.28 ms >> > GOO planning: ~0.38 ms >> > Execution times were similar across all three (~1.5=E2=80=931.7 ms) wi= th no >> correctness issues. Even on a small join, GEQO shows higher planning >> overhead, while GOO plans faster with comparable execution cost. >> > I then evaluated scaling using synthetic 15-table and 20-table joins >> with EXPLAIN (ANALYZE, TIMING OFF): >> > 15 tables >> > DP: ~22.9 ms | ~23.4 ms >> > GEQO: ~46.7 ms | ~20.5 ms >> > GOO: ~1.8 ms | ~22.4 ms >> > >> > 20 tables >> > DP: ~48.1 ms | ~30.5 ms >> > GEQO: ~51.0 ms | ~26.7 ms >> > GOO: ~3.2 ms | ~29.0 ms >> > >> > Planning time increases notably for DP and remains relatively high for >> GEQO, while GOO stays very low even at 20 joins, indicating substantiall= y >> > reduced planning overhead. Execution costs remain broadly comparable, >> with no obvious regressions from GOO in this synthetic workload. >> > >> > Although this uses a controlled synthetic join graph rather than >> JOB/TPC-H, the scaling behavior appears consistent with GOO=E2=80=99s go= al of >> significantly cheaper planning than DP/GEQO while preserving similar pla= n >> quality. >> > >> > I plan to continue testing with more realistic workloads and will shar= e >> further results if anything notable appears. >> > >> > Thanks for the interesting work. >> > >> > Regards, >> > Lakshmi >> >> Hi, >> >> Thank you very much for testing v4 and sharing the results. I really >> appreciate the effort and the detailed feedback. >> >> I also agree with Tomas=E2=80=99s point that we need better benchmark co= ntext to >> evaluate plan quality, not only planning time. >> >> I=E2=80=99ve prepared a v5 refresh on top of v4, still split into two pa= tches >> (v5-0001 and v5-0002). >> I also ran `make check-world` on current master with v5 applied, and it >> passes on my side. >> >> Compared with v4: >> >> [PATCH v5 1/2] >> - keeps the base GOO join-search path focused on a single greedy signal >> (cost); >> - fixes issues found during recent testing (mainly around candidate >> probing/cleanup and failure paths); >> - improves stability/determinism in candidate selection (including tie >> handling); >> - updates regression outputs accordingly. >> >> [PATCH v5 2/2] >> - extends `goo_greedy_strategy` and adds the `selectivity` heuristic >> suggested by Tomas; >> - improves combined mode so multiple greedy signals are evaluated in a >> common framework, and the final plan is selected by lowest estimated >> `total_cost`; >> - keeps strategy-layer changes isolated from the base path for easier >> comparison and review. >> >> My current next steps are: >> >> 1. Continue evaluating plan quality on more datasets/workloads. I=E2=80= =99ve >> already collected several candidate tests: some are JOB-based >> variants, and others are synthetic workloads. Next, I plan to >> consolidate these into a unified test set (with reproducible >> setup/details), publish it, and run broader comparative evaluation. >> >> 2. Prototype a hybrid handoff approach: use greedy contraction first to >> reduce the join graph, then let DP optimize the reduced problem. The >> goal is a smoother transition around the threshold, avoiding abrupt >> plan-shape changes from a hard optimizer switch. >> >> 3. Explore more join-ordering improvements incrementally, including >> ideas from =E2=80=9CSimplicity Done Right for Join Ordering=E2=80=9D and= related >> work. >> >> Thanks again for the careful testing and detailed feedback. >> >> -- >> Best regards, >> Chengpeng Yan >> > --000000000000b47910064aeb74a9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Hi Chengpeng,

I ran a quick comparison of the GOO= v5 greedy strategies on a multi-join workload to look at execution quality= in addition to planning time.

Here are the results from one represen= tative query:

=C2=A0 =C2=A0 =C2=A0 =C2=A0-cost: planning ~1.8 ms | ex= ecution ~32.8 ms

=C2=A0 =C2=A0 =C2=A0 =C2=A0-result_size: planning ~2= .1 ms | execution ~29.3 ms

=C2=A0 =C2=A0 =C2=A0 =C2=A0-combined: plan= ning ~3.7 ms | execution ~29.4 ms

All three strategies keep planning = time very low, which continues to support GOO=E2=80=99s intended scalabilit= y advantage over DP and GEQO.

In this test, the cost=C2=A0strategy sh= ows noticeably higher execution time, while result_size and combined produc= e similar and better execution performance. Since combined has slightly hig= her planning overhead without a clear execution benefit here, result_size a= ppears to provide the best trade-off for this synthetic workload.

I p= lan to continue testing with a few JOB-based queries to evaluate plan quali= ty in a more realistic setting and will share further results if anything n= otable appears.

Thanks again for the continued work on this patch ser= ies.

Regards,
Lakshmi


On Mon, Feb 16, 202= 6 at 11:57=E2=80=AFAM lakshmi <lakshmigcdac@gmail.com> wrote:

Hi Chengpeng,

I tested the= v5 patch on a clean build from current PostgreSQL master.The patch applied= cleanly, the server built successfully, and=C2=A0=C2=A0make check-wo= rld=C2=A0=C2=A0passed without new failures.
I then compared DP, G= EQO, and GOO on synthetic multi-join workloads.

15-table = join

  • DP: planning ~19.1 ms | execution ~21.0 ms

  • GEQO: planning ~46.6 ms | execution ~17.7 ms

  • GO= O v5: planning ~1.0 ms | execution ~19.5 ms

20-tabl= e join

  • DP: planning ~25.1 ms | execution ~28.2 ms<= /p>

  • GEQO: planning ~27.5 ms | execution ~23.5 ms

  • = GOO v5: planning ~1.5 ms | execution ~28.9 ms

    <= span>Across both join sizes, GOO v5 keeps planning time extremely low=C2=A0= (roughly an order of magnitude lower than DP/GEQO) while execu= tion=C2=A0times remain in a comparable range, with no obvious = regressions in this=C2=A0synthetic workload. This appears cons= istent with the goal of reducing=C2=A0planning overhead for la= rge join problems while preserving similar plan=C2=A0quality.<= br>
    These tests use controlled synthetic joins rather than JOB/TPC-H, so= they mainly validate planning-time scaling and basic plan sanity. I plan t= o continue with more realistic workloads and strategy comparisons and will = share further results if anything notable appears.

    Tha= nks for the continued work on this patch series.

    Regards,
    L= akshmi


On Sat, Feb 14, 2026 at 11:09=E2=80=AFAM Chengpeng Yan = <chengpen= g_yan@outlook.com> wrote:

> 2026=E5=B9=B42=E6=9C=8813=E6=97=A5 19:14=EF=BC=8Clakshmi <lakshmigcdac@gmail.com= > =E5=86=99=E9=81=93=EF=BC=9A
>
> HI all,
> I tested the latest GOO patch (v4) on a fresh build from the current P= ostgreSQL master. The patch applied cleanly, the server built without issue= s, and regression tests passed except for the expected EXPLAIN output diffe= rences due to the new join ordering behavior.
>
> As a quick sanity check, I compared DP, GEQO, and GOO on a small multi= -join query:
>
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 DP planning: ~0.66 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GEQO planning: ~2.28 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GOO planning: ~0.38 ms
> Execution times were similar across all three (~1.5=E2=80=931.7 ms) wi= th no correctness issues. Even on a small join, GEQO shows higher planning = overhead, while GOO plans faster with comparable execution cost.
> I then evaluated scaling using synthetic 15-table and 20-table joins w= ith EXPLAIN (ANALYZE, TIMING OFF):
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 15 tables
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 DP: ~22.9 ms | ~23.4 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GEQO: ~46.7 ms | ~20.5 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GOO: ~1.8 ms | ~22.4 ms
>
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 20 tables
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 DP: ~48.1 ms | ~30.5 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GEQO: ~51.0 ms | ~26.7 ms
>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 GOO: ~3.2 ms | ~29.0 ms
>
> Planning time increases notably for DP and remains relatively high for= GEQO, while GOO stays very low even at 20 joins, indicating substantially<= br> > reduced planning overhead. Execution costs remain broadly comparable, = with no obvious regressions from GOO in this synthetic workload.
>
> Although this uses a controlled synthetic join graph rather than JOB/T= PC-H, the scaling behavior appears consistent with GOO=E2=80=99s goal of si= gnificantly cheaper planning than DP/GEQO while preserving similar plan qua= lity.
>
> I plan to continue testing with more realistic workloads and will shar= e further results if anything notable appears.
>
> Thanks for the interesting work.
>
> Regards,
> Lakshmi

Hi,

Thank you very much for testing v4 and sharing the results. I really
appreciate the effort and the detailed feedback.

I also agree with Tomas=E2=80=99s point that we need better benchmark conte= xt to
evaluate plan quality, not only planning time.

I=E2=80=99ve prepared a v5 refresh on top of v4, still split into two patch= es
(v5-0001 and v5-0002).
I also ran `make check-world` on current master with v5 applied, and it
passes on my side.

Compared with v4:

[PATCH v5 1/2]
- keeps the base GOO join-search path focused on a single greedy signal
(cost);
- fixes issues found during recent testing (mainly around candidate
probing/cleanup and failure paths);
- improves stability/determinism in candidate selection (including tie
handling);
- updates regression outputs accordingly.

[PATCH v5 2/2]
- extends `goo_greedy_strategy` and adds the `selectivity` heuristic
suggested by Tomas;
- improves combined mode so multiple greedy signals are evaluated in a
common framework, and the final plan is selected by lowest estimated
`total_cost`;
- keeps strategy-layer changes isolated from the base path for easier
comparison and review.

My current next steps are:

1. Continue evaluating plan quality on more datasets/workloads. I=E2=80=99v= e
already collected several candidate tests: some are JOB-based
variants, and others are synthetic workloads. Next, I plan to
consolidate these into a unified test set (with reproducible
setup/details), publish it, and run broader comparative evaluation.

2. Prototype a hybrid handoff approach: use greedy contraction first to
reduce the join graph, then let DP optimize the reduced problem. The
goal is a smoother transition around the threshold, avoiding abrupt
plan-shape changes from a hard optimizer switch.

3. Explore more join-ordering improvements incrementally, including
ideas from =E2=80=9CSimplicity Done Right for Join Ordering=E2=80=9D and re= lated
work.

Thanks again for the careful testing and detailed feedback.

--
Best regards,
Chengpeng Yan
--000000000000b47910064aeb74a9--