Subject: Performance of Query 60 on TPC-DS Benchmark

From: Ba Jinsheng <[email-masked]>
Date: Fri, 22 Nov 2024 11:12:22 +0000

Hi all,

Please see this case:

TPC-DS Query 60:

with ss as (
 select
          i_item_id,sum(ss_ext_sales_price) total_sales
 from
      store_sales,
      date_dim,
         customer_address,
         item
 where
         i_item_id in (select
  i_item_id
from
 item
where i_category in ('Children'))
 and     ss_item_sk              = i_item_sk
 and     ss_sold_date_sk         = d_date_sk
 and     d_year                  = 1999
 and     d_moy                   = 9
 and     ss_addr_sk              = ca_address_sk
 and     ca_gmt_offset           = -6
 group by i_item_id),
 cs as (
 select
          i_item_id,sum(cs_ext_sales_price) total_sales
 from
      catalog_sales,
      date_dim,
         customer_address,
         item
 where
         i_item_id               in (select
  i_item_id
from
 item
where i_category in ('Children'))
 and     cs_item_sk              = i_item_sk
 and     cs_sold_date_sk         = d_date_sk
 and     d_year                  = 1999
 and     d_moy                   = 9
 and     cs_bill_addr_sk         = ca_address_sk
 and     ca_gmt_offset           = -6
 group by i_item_id),
 ws as (
 select
          i_item_id,sum(ws_ext_sales_price) total_sales
 from
      web_sales,
      date_dim,
         customer_address,
         item
 where
         i_item_id               in (select
  i_item_id
from
 item
where i_category in ('Children'))
 and     ws_item_sk              = i_item_sk
 and     ws_sold_date_sk         = d_date_sk
 and     d_year                  = 1999
 and     d_moy                   = 9
 and     ws_bill_addr_sk         = ca_address_sk
 and     ca_gmt_offset           = -6
 group by i_item_id)
  select
  i_item_id
,sum(total_sales) total_sales
 from  (select * from ss
        union all
        select * from cs
        union all
        select * from ws) tmp1
 group by i_item_id
 order by i_item_id
      ,total_sales
 limit 100;

The query plan and execution time:

                                                                                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=98552.85..98569.84 rows=100 width=49) (actual time=1383.955..1390.492 rows=100 loops=1)
   ->  Incremental Sort  (cost=98552.85..98583.60 rows=181 width=49) (actual time=1383.954..1390.485 rows=100 loops=1)
         Sort Key: item.i_item_id, (sum((sum(store_sales.ss_ext_sales_price))))
         Presorted Key: item.i_item_id
         Full-sort Groups: 4  Sort Method: quicksort  Average Memory: 27kB  Peak Memory: 27kB
         ->  GroupAggregate  (cost=98552.71..98575.46 rows=181 width=49) (actual time=1383.795..1390.437 rows=101 loops=1)
               Group Key: item.i_item_id
               ->  Merge Append  (cost=98552.71..98572.29 rows=181 width=49) (actual time=1383.782..1390.362 rows=225 loops=1)
                     Sort Key: item.i_item_id
                     ->  Finalize GroupAggregate  (cost=46679.80..46689.63 rows=103 width=49) (actual time=840.270..846.360 rows=94 loops=1)
                           Group Key: item.i_item_id
                           ->  Gather Merge  (cost=46679.80..46687.88 rows=61 width=49) (actual time=840.260..846.296 rows=95 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=45679.79..45681.01 rows=61 width=49) (actual time=837.065..837.346 rows=318 loops=2)
                                       Group Key: item.i_item_id
                                       ->  Sort  (cost=45679.79..45679.94 rows=61 width=23) (actual time=837.050..837.090 rows=950 loops=2)
                                             Sort Key: item.i_item_id
                                             Sort Method: quicksort  Memory: 186kB
                                             Worker 0:  Sort Method: quicksort  Memory: 190kB
                                             ->  Nested Loop  (cost=3433.99..45677.98 rows=61 width=23) (actual time=13.422..835.693 rows=2334 loops=2)
                                                   ->  Parallel Hash Join  (cost=3433.70..45634.97 rows=138 width=27) (actual time=13.315..807.438 rows=5426 loops=2)
                                                         Hash Cond: (store_sales.ss_sold_date_sk = date_dim.d_date_sk)
                                                         ->  Nested Loop  (cost=1383.92..42700.04 rows=337185 width=31) (actual time=5.641..777.130 rows=267191 loops=2)
                                                               ->  Parallel Hash Semi Join  (cost=1383.49..2781.24 rows=2107 width=21) (actual time=5.589..10.939 rows=1931 loops=2)
                                                                     Hash Cond: (item.i_item_id = item_1.i_item_id)
                                                                     ->  Parallel Seq Scan on item  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.006..2.443 rows=9000 loops=2)
                                                                     ->  Parallel Hash  (cost=1370.35..1370.35 rows=1051 width=17) (actual time=5.534..5.535 rows=893 loops=2)
                                                                           Buckets: 2048  Batches: 1  Memory Usage: 144kB
                                                                           ->  Parallel Seq Scan on item item_1  (cost=0.00..1370.35 rows=1051 width=17) (actual time=0.019..5.219 rows=893 loops=2)
                                                                                 Filter: (i_category = 'Children'::bpchar)
                                                                                 Rows Removed by Filter: 8107
                                                               ->  Index Scan using store_sales_pkey on store_sales  (cost=0.43..17.20 rows=175 width=18) (actual time=0.009..0.373 rows=138 loops=3862)
                                                                     Index Cond: (ss_item_sk = item.i_item_sk)
                                                         ->  Parallel Hash  (cost=2049.55..2049.55 rows=18 width=4) (actual time=7.245..7.245 rows=15 loops=2)
                                                               Buckets: 1024  Batches: 1  Memory Usage: 40kB
                                                               ->  Parallel Seq Scan on date_dim  (cost=0.00..2049.55 rows=18 width=4) (actual time=5.373..7.183 rows=15 loops=2)
                                                                     Filter: ((d_year = 1999) AND (d_moy = 9))
                                                                     Rows Removed by Filter: 36510
                                                   ->  Index Scan using customer_address_pkey on customer_address  (cost=0.29..0.31 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=10851)
                                                         Index Cond: (ca_address_sk = store_sales.ss_addr_sk)
                                                         Filter: (ca_gmt_offset = '-6'::numeric)
                                                         Rows Removed by Filter: 1
                     ->  Finalize GroupAggregate  (cost=32453.97..32458.96 rows=52 width=49) (actual time=389.645..389.890 rows=81 loops=1)
                           Group Key: item_2.i_item_id
                           ->  Gather Merge  (cost=32453.97..32458.07 rows=31 width=49) (actual time=389.639..389.839 rows=82 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=31453.96..31454.58 rows=31 width=49) (actual time=386.201..386.419 rows=302 loops=2)
                                       Group Key: item_2.i_item_id
                                       ->  Sort  (cost=31453.96..31454.03 rows=31 width=23) (actual time=386.185..386.211 rows=574 loops=2)
                                             Sort Key: item_2.i_item_id
                                             Sort Method: quicksort  Memory: 102kB
                                             Worker 0:  Sort Method: quicksort  Memory: 90kB
                                             ->  Nested Loop  (cost=3433.98..31453.19 rows=31 width=23) (actual time=8.611..385.536 rows=1209 loops=2)
                                                   ->  Parallel Hash Join  (cost=3433.69..31431.56 rows=69 width=27) (actual time=8.559..371.927 rows=2784 loops=2)
                                                         Hash Cond: (catalog_sales.cs_sold_date_sk = date_dim_1.d_date_sk)
                                                         ->  Nested Loop  (cost=1383.92..28938.79 rows=168751 width=31) (actual time=3.845..356.671 rows=134113 loops=2)
                                                               ->  Parallel Hash Semi Join  (cost=1383.49..2781.24 rows=2107 width=21) (actual time=3.798..8.414 rows=1931 loops=2)
                                                                     Hash Cond: (item_2.i_item_id = item_3.i_item_id)
                                                                     ->  Parallel Seq Scan on item item_2  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.004..2.278 rows=9000 loops=2)
                                                                     ->  Parallel Hash  (cost=1370.35..1370.35 rows=1051 width=17) (actual time=3.739..3.740 rows=893 loops=2)
                                                                           Buckets: 2048  Batches: 1  Memory Usage: 176kB
                                                                           ->  Parallel Seq Scan on item item_3  (cost=0.00..1370.35 rows=1051 width=17) (actual time=0.024..3.448 rows=893 loops=2)
                                                                                 Filter: (i_category = 'Children'::bpchar)
                                                                                 Rows Removed by Filter: 8107
                                                               ->  Index Scan using catalog_sales_pkey on catalog_sales  (cost=0.43..11.53 rows=88 width=18) (actual time=0.007..0.168 rows=69 loops=3862)
                                                                     Index Cond: (cs_item_sk = item_2.i_item_sk)
                                                         ->  Parallel Hash  (cost=2049.55..2049.55 rows=18 width=4) (actual time=4.146..4.146 rows=15 loops=2)
                                                               Buckets: 1024  Batches: 1  Memory Usage: 40kB
                                                               ->  Parallel Seq Scan on date_dim date_dim_1  (cost=0.00..2049.55 rows=18 width=4) (actual time=2.764..4.105 rows=15 loops=2)
                                                                     Filter: ((d_year = 1999) AND (d_moy = 9))
                                                                     Rows Removed by Filter: 36510
                                                   ->  Index Scan using customer_address_pkey on customer_address customer_address_1  (cost=0.29..0.31 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=5568)
                                                         Index Cond: (ca_address_sk = catalog_sales.cs_bill_addr_sk)
                                                         Filter: (ca_gmt_offset = '-6'::numeric)
                                                         Rows Removed by Filter: 1
                     ->  Finalize GroupAggregate  (cost=19418.92..19421.35 rows=26 width=49) (actual time=153.863..154.080 rows=52 loops=1)
                           Group Key: item_4.i_item_id
                           ->  Gather Merge  (cost=19418.92..19420.91 rows=15 width=49) (actual time=153.858..154.047 rows=53 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=18418.91..18419.21 rows=15 width=49) (actual time=150.236..150.343 rows=174 loops=2)
                                       Group Key: item_4.i_item_id
                                       ->  Sort  (cost=18418.91..18418.95 rows=15 width=23) (actual time=150.224..150.235 rows=245 loops=2)
                                             Sort Key: item_4.i_item_id
                                             Sort Method: quicksort  Memory: 52kB
                                             Worker 0:  Sort Method: quicksort  Memory: 42kB
                                             ->  Nested Loop  (cost=3433.98..18418.62 rows=15 width=23) (actual time=8.291..149.887 rows=573 loops=2)
                                                   ->  Parallel Hash Join  (cost=3433.69..18407.53 rows=35 width=27) (actual time=7.812..143.442 rows=1329 loops=2)
                                                         Hash Cond: (web_sales.ws_sold_date_sk = date_dim_2.d_date_sk)
                                                         ->  Nested Loop  (cost=1383.92..16136.69 rows=84211 width=31) (actual time=3.658..134.414 rows=66762 loops=2)
                                                               ->  Parallel Hash Semi Join  (cost=1383.49..2781.24 rows=2107 width=21) (actual time=3.614..7.859 rows=1931 loops=2)
                                                                     Hash Cond: (item_4.i_item_id = item_5.i_item_id)
                                                                     ->  Parallel Seq Scan on item item_4  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.003..2.403 rows=9000 loops=2)
                                                                     ->  Parallel Hash  (cost=1370.35..1370.35 rows=1051 width=17) (actual time=3.559..3.560 rows=893 loops=2)
                                                                           Buckets: 2048  Batches: 1  Memory Usage: 144kB
                                                                           ->  Parallel Seq Scan on item item_5  (cost=0.00..1370.35 rows=1051 width=17) (actual time=0.022..3.323 rows=893 loops=2)
                                                                                 Filter: (i_category = 'Children'::bpchar)
                                                                                 Rows Removed by Filter: 8107
                                                               ->  Index Scan using web_sales_pkey on web_sales  (cost=0.42..5.91 rows=43 width=18) (actual time=0.005..0.060 rows=35 loops=3862)
                                                                     Index Cond: (ws_item_sk = item_4.i_item_sk)
                                                         ->  Parallel Hash  (cost=2049.55..2049.55 rows=18 width=4) (actual time=3.873..3.873 rows=15 loops=2)
                                                               Buckets: 1024  Batches: 1  Memory Usage: 40kB
                                                               ->  Parallel Seq Scan on date_dim date_dim_2  (cost=0.00..2049.55 rows=18 width=4) (actual time=2.509..3.834 rows=15 loops=2)
                                                                     Filter: ((d_year = 1999) AND (d_moy = 9))
                                                                     Rows Removed by Filter: 36510
                                                   ->  Index Scan using customer_address_pkey on customer_address customer_address_2  (cost=0.29..0.32 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=2658)
                                                         Index Cond: (ca_address_sk = web_sales.ws_bill_addr_sk)
                                                         Filter: (ca_gmt_offset = '-6'::numeric)
                                                         Rows Removed by Filter: 1
 Planning Time: 4.921 ms
 Execution Time: 1390.888 ms
(113 rows)

Here, if we apply the following patch:

diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
index 5be8da9e09..02d3b6dfc9 100644
--- a/src/backend/optimizer/path/joinpath.c
+++ b/src/backend/optimizer/path/joinpath.c
@@ -1202,7 +1202,6 @@ try_partial_hashjoin_path(PlannerInfo *root,
         */
        initial_cost_hashjoin(root, &workspace, jointype, hashclauses,
                                                  outer_path, inner_path, extra, parallel_hash);
-       if (!add_partial_path_precheck(joinrel, workspace.total_cost, NIL))
                return;

        /* Might be good enough to be worth trying, so let's try it. */

The query plan and execution time are much better:

                                                                                                  QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=14368.57..67274.24 rows=100 width=49) (actual time=620.122..717.451 rows=100 loops=1)
   ->  Incremental Sort  (cost=14368.57..110127.84 rows=181 width=49) (actual time=620.121..717.442 rows=100 loops=1)
         Sort Key: item.i_item_id, (sum((sum(store_sales.ss_ext_sales_price))))
         Presorted Key: item.i_item_id
         Full-sort Groups: 4  Sort Method: quicksort  Average Memory: 27kB  Peak Memory: 27kB
         ->  GroupAggregate  (cost=13836.61..110119.69 rows=181 width=49) (actual time=525.705..717.358 rows=101 loops=1)
               Group Key: item.i_item_id
               ->  Merge Append  (cost=13836.61..110116.53 rows=181 width=49) (actual time=518.454..717.227 rows=225 loops=1)
                     Sort Key: item.i_item_id
                     ->  Finalize GroupAggregate  (cost=4612.20..53673.79 rows=103 width=49) (actual time=209.830..322.526 rows=94 loops=1)
                           Group Key: item.i_item_id
                           ->  Gather Merge  (cost=4612.20..53672.05 rows=61 width=49) (actual time=206.661..322.418 rows=95 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=3612.19..52665.17 rows=61 width=49) (actual time=26.067..373.585 rows=274 loops=2)
                                       Group Key: item.i_item_id
                                       ->  Nested Loop  (cost=3612.19..52664.11 rows=61 width=23) (actual time=21.399..373.040 rows=798 loops=2)
                                             ->  Nested Loop  (cost=3611.90..52621.09 rows=138 width=27) (actual time=21.309..362.794 rows=1882 loops=2)
                                                   ->  Nested Loop  (cost=3611.59..43612.90 rows=337185 width=31) (actual time=19.858..328.844 rows=94367 loops=2)
                                                         ->  Merge Semi Join  (cost=3611.16..3694.10 rows=2107 width=21) (actual time=19.780..20.884 rows=696 loops=2)
                                                               Merge Cond: (item.i_item_id = item_1.i_item_id)
                                                               ->  Sort  (cost=2051.70..2078.17 rows=10588 width=21) (actual time=10.082..10.432 rows=3195 loops=2)
                                                                     Sort Key: item.i_item_id
                                                                     Sort Method: quicksort  Memory: 873kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 407kB
                                                                     ->  Parallel Seq Scan on item  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.021..4.535 rows=9000 loops=2)
                                                               ->  Sort  (cost=1559.47..1563.93 rows=1786 width=17) (actual time=9.690..9.753 rows=950 loops=2)
                                                                     Sort Key: item_1.i_item_id
                                                                     Sort Method: quicksort  Memory: 49kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 49kB
                                                                     ->  Seq Scan on item item_1  (cost=0.00..1463.00 rows=1786 width=17) (actual time=0.012..8.720 rows=1786 loops=2)
                                                                           Filter: (i_category = 'Children'::bpchar)
                                                                           Rows Removed by Filter: 16214
                                                         ->  Index Scan using store_sales_pkey on store_sales  (cost=0.43..17.20 rows=175 width=18) (actual time=0.010..0.418 rows=135 loops=1393)
                                                               Index Cond: (ss_item_sk = item.i_item_sk)
                                                   ->  Memoize  (cost=0.30..0.33 rows=1 width=4) (actual time=0.000..0.000 rows=0 loops=188734)
                                                         Cache Key: store_sales.ss_sold_date_sk
                                                         Cache Mode: logical
                                                         Hits: 22594  Misses: 1824  Evictions: 0  Overflows: 0  Memory Usage: 123kB
                                                         Worker 0:  Hits: 162492  Misses: 1824  Evictions: 0  Overflows: 0  Memory Usage: 123kB
                                                         ->  Index Scan using date_dim_pkey on date_dim  (cost=0.29..0.32 rows=1 width=4) (actual time=0.003..0.003 rows=0 loops=3648)
                                                               Index Cond: (d_date_sk = store_sales.ss_sold_date_sk)
                                                               Filter: ((d_year = 1999) AND (d_moy = 9))
                                                               Rows Removed by Filter: 1
                                             ->  Index Scan using customer_address_pkey on customer_address  (cost=0.29..0.31 rows=1 width=4) (actual time=0.005..0.005 rows=0 loops=3763)
                                                   Index Cond: (ca_address_sk = store_sales.ss_addr_sk)
                                                   Filter: (ca_gmt_offset = '-6'::numeric)
                                                   Rows Removed by Filter: 1
                     ->  Finalize GroupAggregate  (cost=4612.19..35681.87 rows=52 width=49) (actual time=182.160..244.227 rows=81 loops=1)
                           Group Key: item_2.i_item_id
                           ->  Gather Merge  (cost=4612.19..35680.99 rows=31 width=49) (actual time=181.280..244.127 rows=82 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=3612.18..34677.49 rows=31 width=49) (actual time=25.641..237.968 rows=228 loops=2)
                                       Group Key: item_2.i_item_id
                                       ->  Nested Loop  (cost=3612.18..34676.95 rows=31 width=23) (actual time=23.407..237.595 rows=421 loops=2)
                                             ->  Nested Loop  (cost=3611.89..34655.32 rows=69 width=27) (actual time=21.110..231.354 rows=1001 loops=2)
                                                   ->  Nested Loop  (cost=3611.59..29851.66 rows=168751 width=31) (actual time=20.479..211.999 rows=48619 loops=2)
                                                         ->  Merge Semi Join  (cost=3611.16..3694.10 rows=2107 width=21) (actual time=20.406..21.491 rows=713 loops=2)
                                                               Merge Cond: (item_2.i_item_id = item_3.i_item_id)
                                                               ->  Sort  (cost=2051.70..2078.17 rows=10588 width=21) (actual time=10.180..10.521 rows=3232 loops=2)
                                                                     Sort Key: item_2.i_item_id
                                                                     Sort Method: quicksort  Memory: 869kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 411kB
                                                                     ->  Parallel Seq Scan on item item_2  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.018..4.695 rows=9000 loops=2)
                                                               ->  Sort  (cost=1559.47..1563.93 rows=1786 width=17) (actual time=10.219..10.283 rows=952 loops=2)
                                                                     Sort Key: item_3.i_item_id
                                                                     Sort Method: quicksort  Memory: 49kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 49kB
                                                                     ->  Seq Scan on item item_3  (cost=0.00..1463.00 rows=1786 width=17) (actual time=0.016..9.364 rows=1786 loops=2)
                                                                           Filter: (i_category = 'Children'::bpchar)
                                                                           Rows Removed by Filter: 16214
                                                         ->  Index Scan using catalog_sales_pkey on catalog_sales  (cost=0.43..11.53 rows=88 width=18) (actual time=0.009..0.254 rows=68 loops=1426)
                                                               Index Cond: (cs_item_sk = item_2.i_item_sk)
                                                   ->  Memoize  (cost=0.30..0.33 rows=1 width=4) (actual time=0.000..0.000 rows=0 loops=97238)
                                                         Cache Key: catalog_sales.cs_sold_date_sk
                                                         Cache Mode: logical
                                                         Hits: 10090  Misses: 1812  Evictions: 0  Overflows: 0  Memory Usage: 122kB
                                                         Worker 0:  Hits: 83505  Misses: 1831  Evictions: 0  Overflows: 0  Memory Usage: 123kB
                                                         ->  Index Scan using date_dim_pkey on date_dim date_dim_1  (cost=0.29..0.32 rows=1 width=4) (actual time=0.002..0.002 rows=0 loops=3643)
                                                               Index Cond: (d_date_sk = catalog_sales.cs_sold_date_sk)
                                                               Filter: ((d_year = 1999) AND (d_moy = 9))
                                                               Rows Removed by Filter: 1
                                             ->  Index Scan using customer_address_pkey on customer_address customer_address_1  (cost=0.29..0.31 rows=1 width=4) (actual time=0.006..0.006 rows=0 loops=2002)
                                                   Index Cond: (ca_address_sk = catalog_sales.cs_bill_addr_sk)
                                                   Filter: (ca_gmt_offset = '-6'::numeric)
                                                   Rows Removed by Filter: 1
                     ->  Finalize GroupAggregate  (cost=4612.19..20758.50 rows=26 width=49) (actual time=126.461..150.410 rows=52 loops=1)
                           Group Key: item_4.i_item_id
                           ->  Gather Merge  (cost=4612.19..20758.06 rows=15 width=49) (actual time=126.445..150.331 rows=53 loops=1)
                                 Workers Planned: 1
                                 Workers Launched: 1
                                 ->  Partial GroupAggregate  (cost=3612.18..19756.36 rows=15 width=49) (actual time=20.098..142.150 rows=184 loops=2)
                                       Group Key: item_4.i_item_id
                                       ->  Nested Loop  (cost=3612.18..19756.10 rows=15 width=23) (actual time=18.958..141.896 rows=258 loops=2)
                                             ->  Nested Loop  (cost=3611.89..19745.01 rows=35 width=27) (actual time=18.933..138.234 rows=588 loops=2)
                                                   ->  Nested Loop  (cost=3611.59..17049.55 rows=84211 width=31) (actual time=17.422..126.542 rows=28404 loops=2)
                                                         ->  Merge Semi Join  (cost=3611.16..3694.10 rows=2107 width=21) (actual time=17.373..18.498 rows=840 loops=2)
                                                               Merge Cond: (item_4.i_item_id = item_5.i_item_id)
                                                               ->  Sort  (cost=2051.70..2078.17 rows=10588 width=21) (actual time=8.744..9.131 rows=3858 loops=2)
                                                                     Sort Key: item_4.i_item_id
                                                                     Sort Method: quicksort  Memory: 817kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 463kB
                                                                     ->  Parallel Seq Scan on item item_4  (cost=0.00..1343.88 rows=10588 width=21) (actual time=0.019..4.199 rows=9000 loops=2)
                                                               ->  Sort  (cost=1559.47..1563.93 rows=1786 width=17) (actual time=8.624..8.683 rows=951 loops=2)
                                                                     Sort Key: item_5.i_item_id
                                                                     Sort Method: quicksort  Memory: 49kB
                                                                     Worker 0:  Sort Method: quicksort  Memory: 49kB
                                                                     ->  Seq Scan on item item_5  (cost=0.00..1463.00 rows=1786 width=17) (actual time=0.011..7.950 rows=1786 loops=2)
                                                                           Filter: (i_category = 'Children'::bpchar)
                                                                           Rows Removed by Filter: 16214
                                                         ->  Index Scan using web_sales_pkey on web_sales  (cost=0.42..5.91 rows=43 width=18) (actual time=0.008..0.122 rows=34 loops=1681)
                                                               Index Cond: (ws_item_sk = item_4.i_item_sk)
                                                   ->  Memoize  (cost=0.30..0.33 rows=1 width=4) (actual time=0.000..0.000 rows=0 loops=56807)
                                                         Cache Key: web_sales.ws_sold_date_sk
                                                         Cache Mode: logical
                                                         Hits: 3438  Misses: 1557  Evictions: 0  Overflows: 0  Memory Usage: 105kB
                                                         Worker 0:  Hits: 49988  Misses: 1824  Evictions: 0  Overflows: 0  Memory Usage: 123kB
                                                         ->  Index Scan using date_dim_pkey on date_dim date_dim_2  (cost=0.29..0.32 rows=1 width=4) (actual time=0.002..0.002 rows=0 loops=3381)
                                                               Index Cond: (d_date_sk = web_sales.ws_sold_date_sk)
                                                               Filter: ((d_year = 1999) AND (d_moy = 9))
                                                               Rows Removed by Filter: 1
                                             ->  Index Scan using customer_address_pkey on customer_address customer_address_2  (cost=0.29..0.32 rows=1 width=4) (actual time=0.006..0.006 rows=0 loops=1176)
                                                   Index Cond: (ca_address_sk = web_sales.ws_bill_addr_sk)
                                                   Filter: (ca_gmt_offset = '-6'::numeric)
                                                   Rows Removed by Filter: 1
 Planning Time: 4.561 ms
 Execution Time: 718.016 ms
(128 rows)

I think the key difference is that the patch disables the usage of Hash Join, which incurs a worse performance.

I also tried to execute `set enable_hashjoin = off;` and also observed the performance improvement.

Environment:
For the benchmark, I used 1 GB data, and my entire data folder can be downloaded here: https://drive.google.com/file/d/1iK5gfyKudfn2BczpoZbNRY_IAD_rITZu/view?usp=sharing
The connection string is: postgresql://ubuntu:ubuntu(at)127(dot)0(dot)0(dot)1:5432/tpcds"
tpch=# select version();
                                             version
--------------------------------------------------------------------------------------------------
 PostgreSQL 17.0 on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0, 64-bit
(1 row)

Best regards,

Jinsheng Ba

Notice: This email is generated from the account of an NUS alumnus. Contents, views, and opinions therein are solely those of the sender.

---

From: Andrei Lepikhov <[email-masked]>
Date: Fri, 22 Nov 2024 21:32:57 +0700

> Join, which incurs a worse performance.
I see here a problem with a number of groups: when predicting it 
incorrectly, Postgres doesn't use the Memoize node. Disabling HashJoin 
puts NestLoop+Memoize at the place of the best path, which is chosen later.
Unfortunately, we can't see a prediction on the number of groups in 
Memoize and can only guess the issue.

-- 
regards, Andrei Lepikhov

---

From: Andrei Lepikhov <[email-masked]>
Date: Sun, 24 Nov 2024 19:04:17 +0700

> Join, which incurs a worse performance.
Discovering your case a little more I found out the origins of the 
problem: Memoize+NestLoop was not chosen because top-query LIMIT node 
wasn't counted in estimation on lower levels of the query. At first, I 
found that join prediction is overestimated, that is unusual. Look at this:

->  Merge Semi Join  (cost=3611.16..3694.10 rows=2107 width=21) (actual 
time=28.195..30.243 rows=498 loops=2)
       Merge Cond: (item_2.i_item_id = item_3.i_item_id)
       ->  Sort  (cost=2051.70..2078.17 rows=10588 width=21) (actual 
time=14.113..14.625 rows=2416 loops=2)
             Sort Key: item_2.i_item_id
             Sort Method: quicksort  Memory: 938kB
             Worker 0:  Sort Method: quicksort  Memory: 247kB
             ->  Parallel Seq Scan on item item_2  (cost=0.00..1343.88 
rows=10588 width=21) (actual time=0.029..5.954 rows=9000 loops=2)
       ->  Sort  (cost=1559.47..1563.93 rows=1786 width=17) (actual 
time=14.072..14.247 rows=950 loops=2)
             Sort Key: item_3.i_item_id
             Sort Method: quicksort  Memory: 49kB
             Worker 0:  Sort Method: quicksort  Memory: 49kB
             ->  Seq Scan on item item_3  (cost=0.00..1463.00 rows=1786 
width=17) (actual time=0.018..12.638 rows=1786 loops=2)
                   Filter: (i_category = 'Children'::bpchar)
                   Rows Removed by Filter: 16214

Because of that the Memoize node wasn't chosen. Executing this specific 
part of the query:

SET max_parallel_workers_per_gather = 1;
SET parallel_setup_cost = 0.001;
SET parallel_tuple_cost = 0.00005;
SET min_parallel_table_scan_size = 0;
EXPLAIN (ANALYZE)
SELECT * FROM item i1
WHERE i_item_id IN (SELECT i_item_id FROM item i2 WHERE i2.i_category IN 
('Children'));

I found that prediction was correct:
Merge Semi Join  (cost=3611.16..3694.10 rows=2107 width=21)
                  (actual time=19.878..26.321 rows=1931 loops=2)

So, top-level nodes just didn't pull more tuples than possible because 
of LIMIT. If you remove LIMIT 100 from the query, you can see that your 
plan (NestLoop+Memoize) works 24s, much worse than the 3s Postgres (with 
HashJoin) created without your changes.
In toto, this example demonstrates the problem of planning queries that 
need only fractional results.
I may be wrong, but is this a problem of an Append node?

-- 
regards, Andrei Lepikhov

---

From: Nikita Malakhov <[email-masked]>
Date: Thu, 28 Nov 2024 10:58:04 +0300

Hi!

I would rather do not exclude add_partial_path_precheck, but modify it to
check just path costs
and do not count key chains length:

 foreach(p1, parent_rel->partial_pathlist)
{
   Path   *old_path = (Path *) lfirst(p1);
   if (total_cost > old_path->total_cost * STD_FUZZ_FACTOR)
      return false;
   if (old_path->total_cost > total_cost * STD_FUZZ_FACTOR)
      return true;
}

While running this modification I've got the following plan on current
master:

        QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------->
 Limit  (cost=70.29..70.47 rows=3 width=100) (actual time=0.079..0.083
rows=0 loops=1)
   ->  Incremental Sort  (cost=70.29..70.47 rows=3 width=100) (actual
time=0.078..0.082 rows=0 loops=1)
         Sort Key: item.i_item_id,
(sum((sum(store_sales.ss_ext_sales_price))))
         Presorted Key: item.i_item_id
         Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 25kB
 Peak Memory: 25kB
         ->  GroupAggregate  (cost=70.26..70.32 rows=3 width=100) (actual
time=0.033..0.037 rows=0 loops=1)
               Group Key: item.i_item_id
               ->  Sort  (cost=70.26..70.27 rows=3 width=100) (actual
time=0.033..0.036 rows=0 loops=1)
                     Sort Key: item.i_item_id
                     Sort Method: quicksort  Memory: 25kB
                     ->  Append  (cost=23.42..70.23 rows=3 width=100)
(actual time=0.030..0.033 rows=0 loops=1)
                           ->  GroupAggregate  (cost=23.42..23.44 rows=1
width=100) (actual time=0.013..0.015 rows=0 loops=1)
                                 Group Key: item.i_item_id
                                 ->  Sort  (cost=23.42..23.43 rows=1
width=82) (actual time=0.013..0.014 rows=0 loops=1)
                                       Sort Key: item.i_item_id
                                       Sort Method: quicksort  Memory: 25kB
                                       ->  Nested Loop  (cost=10.96..23.41
rows=1 width=82) (actual time=0.006..0.008 rows=0 loops=1)
                                             ->  Nested Loop
 (cost=10.81..22.96 rows=1 width=86) (actual time=0.006..0.008 rows=0
loops=1)
                                                   ->  Nested Loop
 (cost=10.66..22.33 rows=2 width=90) (actual time=0.006..0.007 rows=0
loops=1)
                                                         ->  Hash Semi Join
 (cost=10.51..21.03 rows=1 width=72) (actual time=0.005..0.006 rows=0
loops=1)
                                                               Hash Cond:
(item.i_item_id = item_1.i_item_id)
                                                               ->  Seq Scan
on item  (cost=0.00..10.40 rows=40 width=72) (actual time=0.005..0.005
rows=0 l>
                                                               ->  Hash
 (cost=10.50..10.50 rows=1 width=68) (never executed)
                                                                     ->
 Seq Scan on item item_1  (cost=0.00..10.50 rows=1 width=68) (never
executed)

 Filter: (i_category = 'Children'::bpchar)
                                                         ->  Index Scan
using store_sales_pkey on store_sales  (cost=0.15..1.28 rows=2 width=26)
(never exe>
                                                               Index Cond:
(ss_item_sk = item.i_item_sk)
                                                   ->  Memoize
 (cost=0.15..0.30 rows=1 width=4) (never executed)
                                                         Cache Key:
store_sales.ss_addr_sk
                                                         Cache Mode: logical
                                                         ->  Index Scan
using customer_address_pkey on customer_address  (cost=0.14..0.29 rows=1
width=4) (>
                                                               Index Cond:
(ca_address_sk = store_sales.ss_addr_sk)
                                                               Filter:
(ca_gmt_offset = '-6'::numeric)
                                             ->  Index Scan using
date_dim_pkey on date_dim  (cost=0.15..0.30 rows=1 width=4) (never executed)
                                                   Index Cond: (d_date_sk =
store_sales.ss_sold_date_sk)
                                                   Filter: ((d_year = 1999)
AND (d_moy = 9))
                           ->  GroupAggregate  (cost=23.37..23.39 rows=1
width=100) (actual time=0.008..0.009 rows=0 loops=1)
                                 Group Key: item_2.i_item_id
                                 ->  Sort  (cost=23.37..23.37 rows=1
width=82) (actual time=0.008..0.009 rows=0 loops=1)
                                       Sort Key: item_2.i_item_id
                                       Sort Method: quicksort  Memory: 25kB
                                       ->  Nested Loop  (cost=10.95..23.36
rows=1 width=82) (actual time=0.002..0.003 rows=0 loops=1)
                                             ->  Nested Loop
 (cost=10.81..22.83 rows=1 width=86) (actual time=0.002..0.002 rows=0
loops=1)
                                                   ->  Nested Loop
 (cost=10.66..22.30 rows=1 width=90) (actual time=0.001..0.002 rows=0
loops=1)
                                                         ->  Hash Semi Join
 (cost=10.51..21.03 rows=1 width=72) (actual time=0.001..0.002 rows=0
loops=1)
                                                               Hash Cond:
(item_2.i_item_id = item_3.i_item_id)
                                                               ->  Seq Scan
on item item_2  (cost=0.00..10.40 rows=40 width=72) (actual
time=0.001..0.001 r>
                                                               ->  Hash
 (cost=10.50..10.50 rows=1 width=68) (never executed)
                                                                     ->
 Seq Scan on item item_3  (cost=0.00..10.50 rows=1 width=68) (never
executed)

 Filter: (i_category = 'Children'::bpchar)
                                                         ->  Index Scan
using catalog_sales_pkey on catalog_sales  (cost=0.15..1.26 rows=1
width=26) (never>
                                                               Index Cond:
(cs_item_sk = item_2.i_item_sk)
                                                   ->  Index Scan using
date_dim_pkey on date_dim date_dim_1  (cost=0.15..0.34 rows=1 width=4)
(never execu>
                                                         Index Cond:
(d_date_sk = catalog_sales.cs_sold_date_sk)
                                                         Filter: ((d_year =
1999) AND (d_moy = 9))
                                             ->  Index Scan using
customer_address_pkey on customer_address customer_address_1
 (cost=0.14..0.33 rows=1 wid>
                                                   Index Cond:
(ca_address_sk = catalog_sales.cs_bill_addr_sk)
                                                   Filter: (ca_gmt_offset =
'-6'::numeric)
                           ->  GroupAggregate  (cost=23.37..23.39 rows=1
width=100) (actual time=0.008..0.008 rows=0 loops=1)
                                 Group Key: item_4.i_item_id
                                 ->  Sort  (cost=23.37..23.37 rows=1
width=82) (actual time=0.007..0.008 rows=0 loops=1)
                                       Sort Key: item_4.i_item_id
                                       Sort Method: quicksort  Memory: 25kB
                                       ->  Nested Loop  (cost=10.95..23.36
rows=1 width=82) (actual time=0.001..0.001 rows=0 loops=1)
                                             ->  Nested Loop
 (cost=10.81..22.83 rows=1 width=86) (actual time=0.001..0.001 rows=0
loops=1)
                                                   ->  Nested Loop
 (cost=10.66..22.30 rows=1 width=90) (actual time=0.001..0.001 rows=0
loops=1)
                                                         ->  Hash Semi Join
 (cost=10.51..21.03 rows=1 width=72) (actual time=0.001..0.001 rows=0
loops=1)
                                                               Hash Cond:
(item_4.i_item_id = item_5.i_item_id)
                                                               ->  Seq Scan
on item item_4  (cost=0.00..10.40 rows=40 width=72) (actual
time=0.000..0.000 r>
                                                               ->  Hash
 (cost=10.50..10.50 rows=1 width=68) (never executed)
                                                                     ->
 Seq Scan on item item_5  (cost=0.00..10.50 rows=1 width=68) (never
executed)

 Filter: (i_category = 'Children'::bpchar)
                                                         ->  Index Scan
using web_sales_pkey on web_sales  (cost=0.15..1.26 rows=1 width=26) (never
execute>
                                                               Index Cond:
(ws_item_sk = item_4.i_item_sk)
                                                   ->  Index Scan using
date_dim_pkey on date_dim date_dim_2  (cost=0.15..0.34 rows=1 width=4)
(never execu>
                                                         Index Cond:
(d_date_sk = web_sales.ws_sold_date_sk)
                                                         Filter: ((d_year =
1999) AND (d_moy = 9))
                                             ->  Index Scan using
customer_address_pkey on customer_address customer_address_2
 (cost=0.14..0.33 rows=1 wid>
                                                   Index Cond:
(ca_address_sk = web_sales.ws_bill_addr_sk)
                                                   Filter: (ca_gmt_offset =
'-6'::numeric)
 Planning Time: 2.630 ms
 Execution Time: 0.330 ms
(82 rows)

-- 
Regards,

--
Nikita Malakhov
Postgres Professional
The Russian Postgres Company
https://postgrespro.ru/

---

From: Nikita Malakhov <[email-masked]>
Date: Fri, 29 Nov 2024 17:27:18 +0300

Hi!

Please check the following proposal (patch in attach).
The main idea is to reject only obviously worse paths (costs considerably
more
than compared one), and to pass pre-calculated startup cost to precheck
function
for more accurate comparison.

Regards,
Nikita Malakhov
Postgres Professional