public inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
To: Chengpeng Yan <[email protected]>
Cc: [email protected] <[email protected]>
Cc: John Naylor <[email protected]>
Subject: Re: Add a greedy join search algorithm to handle large join problems
Date: Tue, 9 Dec 2025 20:20:32 +0100
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<[email protected]>
<[email protected]>
On 12/2/25 14:04, Chengpeng Yan wrote:
> Hi,
>
>
>
>> On Dec 2, 2025, at 18:56, Tomas Vondra <[email protected]> wrote:
>>
>> I think a much broader evaluation will be needed, comparing not just the
>> planning time, but also the quality of the final plan. Which for the
>> starjoin tests does not really matter, as the plans are all equal in
>> this regard.
>
>
> Many thanks for your feedback.
>
> You are absolutely right — plan quality is also very important. In my
> initial email I only showed the improvements in planning time, but did
> not provide results regarding plan quality. I will run tests on more
> complex join scenarios, evaluating both planning time and plan quality.
>
I was trying to do some simple experiments by comparing plans for TPC-DS
queries, but unfortunately I get a lot of crashes with the patch. All
the backtraces look very similar - see the attached example. The root
cause seems to be that sort_inner_and_outer() sees
inner_path = NULL
I haven't investigated this very much, but I suppose the GOO code should
be calling set_cheapest() from somewhere.
regards
--
Tomas Vondra
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x0000562fccfe03a6 in sort_inner_and_outer (root=0x562ff6a6f608, joinrel=0x562ff6a2ae90, outerrel=0x562ff6a779e8, innerrel=0x562ff6aa4248, jointype=JOIN_INNER, extra=0x7ffc86f03c30) at joinpath.c:1409
1409 PATH_PARAM_BY_REL(inner_path, outerrel))
(gdb) bt
#0 0x0000562fccfe03a6 in sort_inner_and_outer (root=0x562ff6a6f608, joinrel=0x562ff6a2ae90, outerrel=0x562ff6a779e8, innerrel=0x562ff6aa4248, jointype=JOIN_INNER, extra=0x7ffc86f03c30) at joinpath.c:1409
#1 add_paths_to_joinrel (root=root@entry=0x562ff6a6f608, joinrel=joinrel@entry=0x562ff6a2ae90, outerrel=outerrel@entry=0x562ff6a779e8, innerrel=innerrel@entry=0x562ff6aa4248, jointype=<optimized out>, jointype@entry=JOIN_INNER,
sjinfo=sjinfo@entry=0x7ffc86f03da0, restrictlist=0x562ff6a2a980) at joinpath.c:289
#2 0x0000562fccfe2630 in populate_joinrel_with_paths (root=root@entry=0x562ff6a6f608, rel1=0x562ff6a779e8, rel2=0x562ff6aa4248, joinrel=0x562ff6a2ae90, sjinfo=sjinfo@entry=0x7ffc86f03da0, restrictlist=restrictlist@entry=0x562ff6a2a980)
at joinrels.c:1105
#3 0x0000562fccfe315e in make_grouped_join_rel (root=0x562ff6a6f608, rel1=<optimized out>, rel2=<optimized out>, joinrel=<optimized out>, sjinfo=0x7ffc86f03da0, restrictlist=0x562ff6a2a980) at joinrels.c:1056
#4 0x0000562fccfe34c1 in make_grouped_join_rel (root=0x562ff6a6f608, rel1=0x562ff6a779e8, rel2=0x562ff6aa79b0, joinrel=0x562ff6a96d10, sjinfo=<optimized out>, restrictlist=<optimized out>) at joinrels.c:931
#5 make_join_rel (root=root@entry=0x562ff6a6f608, rel1=rel1@entry=0x562ff6a779e8, rel2=rel2@entry=0x562ff6aa79b0) at joinrels.c:770
#6 0x0000562fccfd97c9 in goo_build_candidate (state=0x562ff6a9e018, left=0x562ff6a779e8, right=0x562ff6aa79b0) at goo.c:457
#7 goo_search_internal (state=0x562ff6a9e018) at goo.c:326
#8 goo_join_search (root=<optimized out>, levels_needed=<optimized out>, initial_rels=<optimized out>) at goo.c:143
#9 0x0000562fccff4cd2 in query_planner (root=root@entry=0x562ff6a6f608, qp_callback=qp_callback@entry=0x562fccff5370 <standard_qp_callback>, qp_extra=qp_extra@entry=0x7ffc86f04060) at planmain.c:297
#10 0x0000562fccffa708 in grouping_planner (root=root@entry=0x562ff6a6f608, tuple_fraction=<optimized out>, tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1684
#11 0x0000562fccffd501 in subquery_planner (glob=<optimized out>, parse=<optimized out>, parse@entry=0x562ff6a6bc68, plan_name=<optimized out>, parent_root=parent_root@entry=0x562ff6a3e1f0, hasRecursion=hasRecursion@entry=false,
tuple_fraction=tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1251
#12 0x0000562fccfc851a in set_subquery_pathlist (root=0x562ff6a3e1f0, rel=<optimized out>, rti=6, rte=<optimized out>) at allpaths.c:2773
#13 set_rel_size (root=0x562ff6a3e1f0, rel=<optimized out>, rti=6, rte=<optimized out>) at allpaths.c:467
#14 0x0000562fccfc8014 in set_append_rel_size (root=<optimized out>, rel=0x562ff6a69b98, rti=1, rte=<optimized out>) at allpaths.c:1200
#15 set_rel_size (root=<optimized out>, rel=0x562ff6a69b98, rti=1, rte=<optimized out>) at allpaths.c:428
#16 0x0000562fccfcb5d9 in set_base_rel_sizes (root=<optimized out>) at allpaths.c:335
#17 make_one_rel (root=0x562ff6a3e1f0, joinlist=0x562ff6a6a488) at allpaths.c:190
#18 0x0000562fccff4cd2 in query_planner (root=root@entry=0x562ff6a3e1f0, qp_callback=qp_callback@entry=0x562fccff5370 <standard_qp_callback>, qp_extra=qp_extra@entry=0x7ffc86f04580) at planmain.c:297
#19 0x0000562fccffa708 in grouping_planner (root=root@entry=0x562ff6a3e1f0, tuple_fraction=<optimized out>, tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1684
#20 0x0000562fccffd501 in subquery_planner (glob=glob@entry=0x562ff6a31978, parse=<optimized out>, parse@entry=0x562ff693fd58, plan_name=plan_name@entry=0x0, parent_root=parent_root@entry=0x0, hasRecursion=hasRecursion@entry=false, tuple_fraction=0,
setops=setops@entry=0x0) at planner.c:1251
#21 0x0000562fccffda80 in standard_planner (parse=0x562ff693fd58,
query_string=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
cursorOptions=2048, boundParams=0x0, es=0x562ff6a316c0) at planner.c:470
#22 0x0000562fccffdffd in planner (parse=parse@entry=0x562ff693fd58,
query_string=query_string@entry=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"..., cursorOptions=<optimized out>, boundParams=<optimized out>, es=<optimized out>) at planner.c:324
#23 0x0000562fcd0d357a in pg_plan_query (querytree=querytree@entry=0x562ff693fd58,
query_string=query_string@entry=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"..., cursorOptions=cursorOptions@entry=2048, boundParams=boundParams@entry=0x0, es=es@entry=0x562ff6a316c0) at postgres.c:905
#24 0x0000562fcceb2ae6 in standard_ExplainOneQuery (query=0x562ff693fd58, cursorOptions=2048, into=0x0, es=0x562ff6a316c0,
queryString=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
params=0x0, queryEnv=0x0) at explain.c:354
#25 0x0000562fcceb2cbc in ExplainOneQuery (query=<optimized out>, cursorOptions=<optimized out>, into=<optimized out>, es=<optimized out>, pstate=<optimized out>, params=<optimized out>) at explain.c:310
#26 0x0000562fcceb2da5 in ExplainQuery (pstate=0x562ff6933d28, stmt=0x562ff693fbb8, params=0x0, dest=0x562ff6933ca0) at explain.c:224
#27 0x0000562fcd0d8fbb in standard_ProcessUtility (pstmt=0x562ff693fc50,
queryString=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
readOnlyTree=<optimized out>, context=PROCESS_UTILITY_TOPLEVEL, params=0x0, queryEnv=0x0, dest=0x562ff6933ca0, qc=0x7ffc86f04ac0) at utility.c:868
#28 0x0000562fcd0d739c in PortalRunUtility (portal=portal@entry=0x562ff69907a8, pstmt=0x562ff693fc50, isTopLevel=isTopLevel@entry=true, setHoldSnapshot=setHoldSnapshot@entry=true, dest=dest@entry=0x562ff6933ca0, qc=qc@entry=0x7ffc86f04ac0)
at pquery.c:1148
#29 0x0000562fcd0d7737 in FillPortalStore (portal=portal@entry=0x562ff69907a8, isTopLevel=isTopLevel@entry=true) at pquery.c:1021
#30 0x0000562fcd0d7a1d in PortalRun (portal=portal@entry=0x562ff69907a8, count=count@entry=9223372036854775807, isTopLevel=isTopLevel@entry=true, dest=dest@entry=0x7ff204b2d420, altdest=altdest@entry=0x7ff204b2d420, qc=qc@entry=0x7ffc86f04ca0)
at pquery.c:755
#31 0x0000562fcd0d3a40 in exec_simple_query (
query_string=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...)
at postgres.c:1279
#32 0x0000562fcd0d590e in PostgresMain (dbname=<optimized out>, username=<optimized out>) at postgres.c:4775
#33 0x0000562fcd0d017f in BackendMain (startup_data=<optimized out>, startup_data_len=<optimized out>) at backend_startup.c:124
#34 0x0000562fcd03675a in postmaster_child_launch (child_type=<optimized out>, child_slot=1, startup_data=startup_data@entry=0x7ffc86f05130, startup_data_len=startup_data_len@entry=24, client_sock=client_sock@entry=0x7ffc86f05150)
at launch_backend.c:268
#35 0x0000562fcd03a010 in BackendStartup (client_sock=0x7ffc86f05150) at postmaster.c:3598
--Type <RET> for more, q to quit, c to continue without paging--
#36 ServerLoop () at postmaster.c:1713
#37 0x0000562fcd03b882 in PostmasterMain (argc=argc@entry=3, argv=argv@entry=0x562ff6900c20) at postmaster.c:1403
#38 0x0000562fccd6520a in main (argc=3, argv=0x562ff6900c20) at main.c:231
Attachments:
[text/plain] crash.txt (8.2K, 2-crash.txt)
download | inline:
Program terminated with signal SIGSEGV, Segmentation fault.
#0 0x0000562fccfe03a6 in sort_inner_and_outer (root=0x562ff6a6f608, joinrel=0x562ff6a2ae90, outerrel=0x562ff6a779e8, innerrel=0x562ff6aa4248, jointype=JOIN_INNER, extra=0x7ffc86f03c30) at joinpath.c:1409
1409 PATH_PARAM_BY_REL(inner_path, outerrel))
(gdb) bt
#0 0x0000562fccfe03a6 in sort_inner_and_outer (root=0x562ff6a6f608, joinrel=0x562ff6a2ae90, outerrel=0x562ff6a779e8, innerrel=0x562ff6aa4248, jointype=JOIN_INNER, extra=0x7ffc86f03c30) at joinpath.c:1409
#1 add_paths_to_joinrel (root=root@entry=0x562ff6a6f608, joinrel=joinrel@entry=0x562ff6a2ae90, outerrel=outerrel@entry=0x562ff6a779e8, innerrel=innerrel@entry=0x562ff6aa4248, jointype=<optimized out>, jointype@entry=JOIN_INNER,
sjinfo=sjinfo@entry=0x7ffc86f03da0, restrictlist=0x562ff6a2a980) at joinpath.c:289
#2 0x0000562fccfe2630 in populate_joinrel_with_paths (root=root@entry=0x562ff6a6f608, rel1=0x562ff6a779e8, rel2=0x562ff6aa4248, joinrel=0x562ff6a2ae90, sjinfo=sjinfo@entry=0x7ffc86f03da0, restrictlist=restrictlist@entry=0x562ff6a2a980)
at joinrels.c:1105
#3 0x0000562fccfe315e in make_grouped_join_rel (root=0x562ff6a6f608, rel1=<optimized out>, rel2=<optimized out>, joinrel=<optimized out>, sjinfo=0x7ffc86f03da0, restrictlist=0x562ff6a2a980) at joinrels.c:1056
#4 0x0000562fccfe34c1 in make_grouped_join_rel (root=0x562ff6a6f608, rel1=0x562ff6a779e8, rel2=0x562ff6aa79b0, joinrel=0x562ff6a96d10, sjinfo=<optimized out>, restrictlist=<optimized out>) at joinrels.c:931
#5 make_join_rel (root=root@entry=0x562ff6a6f608, rel1=rel1@entry=0x562ff6a779e8, rel2=rel2@entry=0x562ff6aa79b0) at joinrels.c:770
#6 0x0000562fccfd97c9 in goo_build_candidate (state=0x562ff6a9e018, left=0x562ff6a779e8, right=0x562ff6aa79b0) at goo.c:457
#7 goo_search_internal (state=0x562ff6a9e018) at goo.c:326
#8 goo_join_search (root=<optimized out>, levels_needed=<optimized out>, initial_rels=<optimized out>) at goo.c:143
#9 0x0000562fccff4cd2 in query_planner (root=root@entry=0x562ff6a6f608, qp_callback=qp_callback@entry=0x562fccff5370 <standard_qp_callback>, qp_extra=qp_extra@entry=0x7ffc86f04060) at planmain.c:297
#10 0x0000562fccffa708 in grouping_planner (root=root@entry=0x562ff6a6f608, tuple_fraction=<optimized out>, tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1684
#11 0x0000562fccffd501 in subquery_planner (glob=<optimized out>, parse=<optimized out>, parse@entry=0x562ff6a6bc68, plan_name=<optimized out>, parent_root=parent_root@entry=0x562ff6a3e1f0, hasRecursion=hasRecursion@entry=false,
tuple_fraction=tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1251
#12 0x0000562fccfc851a in set_subquery_pathlist (root=0x562ff6a3e1f0, rel=<optimized out>, rti=6, rte=<optimized out>) at allpaths.c:2773
#13 set_rel_size (root=0x562ff6a3e1f0, rel=<optimized out>, rti=6, rte=<optimized out>) at allpaths.c:467
#14 0x0000562fccfc8014 in set_append_rel_size (root=<optimized out>, rel=0x562ff6a69b98, rti=1, rte=<optimized out>) at allpaths.c:1200
#15 set_rel_size (root=<optimized out>, rel=0x562ff6a69b98, rti=1, rte=<optimized out>) at allpaths.c:428
#16 0x0000562fccfcb5d9 in set_base_rel_sizes (root=<optimized out>) at allpaths.c:335
#17 make_one_rel (root=0x562ff6a3e1f0, joinlist=0x562ff6a6a488) at allpaths.c:190
#18 0x0000562fccff4cd2 in query_planner (root=root@entry=0x562ff6a3e1f0, qp_callback=qp_callback@entry=0x562fccff5370 <standard_qp_callback>, qp_extra=qp_extra@entry=0x7ffc86f04580) at planmain.c:297
#19 0x0000562fccffa708 in grouping_planner (root=root@entry=0x562ff6a3e1f0, tuple_fraction=<optimized out>, tuple_fraction@entry=0, setops=setops@entry=0x0) at planner.c:1684
#20 0x0000562fccffd501 in subquery_planner (glob=glob@entry=0x562ff6a31978, parse=<optimized out>, parse@entry=0x562ff693fd58, plan_name=plan_name@entry=0x0, parent_root=parent_root@entry=0x0, hasRecursion=hasRecursion@entry=false, tuple_fraction=0,
setops=setops@entry=0x0) at planner.c:1251
#21 0x0000562fccffda80 in standard_planner (parse=0x562ff693fd58,
query_string=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
cursorOptions=2048, boundParams=0x0, es=0x562ff6a316c0) at planner.c:470
#22 0x0000562fccffdffd in planner (parse=parse@entry=0x562ff693fd58,
query_string=query_string@entry=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"..., cursorOptions=<optimized out>, boundParams=<optimized out>, es=<optimized out>) at planner.c:324
#23 0x0000562fcd0d357a in pg_plan_query (querytree=querytree@entry=0x562ff693fd58,
query_string=query_string@entry=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"..., cursorOptions=cursorOptions@entry=2048, boundParams=boundParams@entry=0x0, es=es@entry=0x562ff6a316c0) at postgres.c:905
#24 0x0000562fcceb2ae6 in standard_ExplainOneQuery (query=0x562ff693fd58, cursorOptions=2048, into=0x0, es=0x562ff6a316c0,
queryString=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
params=0x0, queryEnv=0x0) at explain.c:354
#25 0x0000562fcceb2cbc in ExplainOneQuery (query=<optimized out>, cursorOptions=<optimized out>, into=<optimized out>, es=<optimized out>, pstate=<optimized out>, params=<optimized out>) at explain.c:310
#26 0x0000562fcceb2da5 in ExplainQuery (pstate=0x562ff6933d28, stmt=0x562ff693fbb8, params=0x0, dest=0x562ff6933ca0) at explain.c:224
#27 0x0000562fcd0d8fbb in standard_ProcessUtility (pstmt=0x562ff693fc50,
queryString=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...,
readOnlyTree=<optimized out>, context=PROCESS_UTILITY_TOPLEVEL, params=0x0, queryEnv=0x0, dest=0x562ff6933ca0, qc=0x7ffc86f04ac0) at utility.c:868
#28 0x0000562fcd0d739c in PortalRunUtility (portal=portal@entry=0x562ff69907a8, pstmt=0x562ff693fc50, isTopLevel=isTopLevel@entry=true, setHoldSnapshot=setHoldSnapshot@entry=true, dest=dest@entry=0x562ff6933ca0, qc=qc@entry=0x7ffc86f04ac0)
at pquery.c:1148
#29 0x0000562fcd0d7737 in FillPortalStore (portal=portal@entry=0x562ff69907a8, isTopLevel=isTopLevel@entry=true) at pquery.c:1021
#30 0x0000562fcd0d7a1d in PortalRun (portal=portal@entry=0x562ff69907a8, count=count@entry=9223372036854775807, isTopLevel=isTopLevel@entry=true, dest=dest@entry=0x7ff204b2d420, altdest=altdest@entry=0x7ff204b2d420, qc=qc@entry=0x7ffc86f04ca0)
at pquery.c:755
#31 0x0000562fcd0d3a40 in exec_simple_query (
query_string=0x562ff69069e0 "EXPLAIN (COSTS OFF)\n with ss as (\n select i_item_id,sum(ss_ext_sales_price) total_sales\n from\n \tstore_sales,\n \tdate_dim,\n customer_address,\n item\n where i_item_id in (select\n i_ite"...)
at postgres.c:1279
#32 0x0000562fcd0d590e in PostgresMain (dbname=<optimized out>, username=<optimized out>) at postgres.c:4775
#33 0x0000562fcd0d017f in BackendMain (startup_data=<optimized out>, startup_data_len=<optimized out>) at backend_startup.c:124
#34 0x0000562fcd03675a in postmaster_child_launch (child_type=<optimized out>, child_slot=1, startup_data=startup_data@entry=0x7ffc86f05130, startup_data_len=startup_data_len@entry=24, client_sock=client_sock@entry=0x7ffc86f05150)
at launch_backend.c:268
#35 0x0000562fcd03a010 in BackendStartup (client_sock=0x7ffc86f05150) at postmaster.c:3598
--Type <RET> for more, q to quit, c to continue without paging--
#36 ServerLoop () at postmaster.c:1713
#37 0x0000562fcd03b882 in PostmasterMain (argc=argc@entry=3, argv=argv@entry=0x562ff6900c20) at postmaster.c:1403
#38 0x0000562fccd6520a in main (argc=3, argv=0x562ff6900c20) at main.c:231
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: Add a greedy join search algorithm to handle large join problems
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox