Subject: Performance of TPC-DS Query 95

From: Ba Jinsheng <[email-masked]>
Date: Mon, 25 Nov 2024 20:54:36 +0000

Hi all,

Please see this case.

TPC-DS query 95:
with ws_wh as
(select ws1.ws_order_number,ws1.ws_warehouse_sk wh1,ws2.ws_warehouse_sk wh2
 from web_sales ws1,web_sales ws2
 where ws1.ws_order_number = ws2.ws_order_number
   and ws1.ws_warehouse_sk <> ws2.ws_warehouse_sk)
 select
   count(distinct ws_order_number) as "order count"
  ,sum(ws_ext_ship_cost) as "total shipping cost"
  ,sum(ws_net_profit) as "total net profit"
from
   web_sales ws1
  ,date_dim
  ,customer_address
  ,web_site
where
    d_date between '1999-5-01' and
           (cast('1999-5-01' as date) + interval '60 days')
and ws1.ws_ship_date_sk = d_date_sk
and ws1.ws_ship_addr_sk = ca_address_sk
and ca_state = 'TX'
and ws1.ws_web_site_sk = web_site_sk
and web_company_name = 'pri'
and ws1.ws_order_number in (select ws_order_number
                            from ws_wh)
and ws1.ws_order_number in (select wr_order_number
                            from web_returns,ws_wh
                            where wr_order_number = ws_wh.ws_order_number)
order by count(distinct ws_order_number)
limit 100;

Its execution time is nearly 1 min:

                                                                                         QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=771620.21..771620.21 rows=1 width=72) (actual time=56669.478..56669.563 rows=1 loops=1)
   CTE ws_wh
     ->  Hash Join  (cost=37772.14..198810.77 rows=7242361 width=12) (actual time=211.161..1443.926 rows=6644004 loops=1)
           Hash Cond: (ws1_1.ws_order_number = ws2.ws_order_number)
           Join Filter: (ws1_1.ws_warehouse_sk <> ws2.ws_warehouse_sk)
           Rows Removed by Join Filter: 2381030
           ->  Seq Scan on web_sales ws1_1  (cost=0.00..25968.84 rows=719384 width=8) (actual time=0.014..106.870 rows=719384 loops=1)
           ->  Hash  (cost=25968.84..25968.84 rows=719384 width=8) (actual time=210.247..210.248 rows=719384 loops=1)
                 Buckets: 262144  Batches: 8  Memory Usage: 5563kB
                 ->  Seq Scan on web_sales ws2  (cost=0.00..25968.84 rows=719384 width=8) (actual time=0.005..111.802 rows=719384 loops=1)
   ->  Sort  (cost=572809.44..572809.45 rows=1 width=72) (actual time=56669.477..56669.559 rows=1 loops=1)
         Sort Key: (count(DISTINCT ws1.ws_order_number))
         Sort Method: quicksort  Memory: 25kB
         ->  Aggregate  (cost=572809.42..572809.43 rows=1 width=72) (actual time=56669.456..56669.538 rows=1 loops=1)
               ->  Sort  (cost=572809.37..572809.38 rows=5 width=16) (actual time=56669.424..56669.510 rows=121 loops=1)
                     Sort Key: ws1.ws_order_number
                     Sort Method: quicksort  Memory: 29kB
                     ->  Nested Loop Semi Join  (cost=390001.60..572809.31 rows=5 width=16) (actual time=5814.554..56669.277 rows=121 loops=1)
                           Join Filter: (ws1.ws_order_number = ws_wh.ws_order_number)
                           Rows Removed by Join Filter: 400808138
                           ->  Hash Join  (cost=390001.60..414560.96 rows=5 width=24) (actual time=4939.833..4940.928 rows=121 loops=1)
                                 Hash Cond: (ws1.ws_order_number = web_returns.wr_order_number)
                                 ->  Gather  (cost=1003.03..25562.31 rows=8 width=16) (actual time=2.891..3.674 rows=148 loops=1)
                                       Workers Planned: 2
                                       Workers Launched: 2
                                       ->  Nested Loop  (cost=3.03..24561.51 rows=3 width=16) (actual time=4.531..75.030 rows=49 loops=3)
                                             ->  Nested Loop  (cost=2.74..24548.21 rows=42 width=20) (actual time=1.566..72.683 rows=584 loops=3)
                                                   ->  Hash Join  (cost=2.44..22672.82 rows=49957 width=24) (actual time=0.158..58.416 rows=31830 loops=3)
                                                         Hash Cond: (ws1.ws_web_site_sk = web_site.web_site_sk)
                                                         ->  Parallel Seq Scan on web_sales ws1  (cost=0.00..21772.43 rows=299743 width=28) (actual time=0.054..24.308 rows=239795 loops=3)
                                                         ->  Hash  (cost=2.38..2.38 rows=5 width=4) (actual time=0.047..0.047 rows=5 loops=3)
                                                               Buckets: 1024  Batches: 1  Memory Usage: 9kB
                                                               ->  Seq Scan on web_site  (cost=0.00..2.38 rows=5 width=4) (actual time=0.036..0.042 rows=5 loops=3)
                                                                     Filter: (web_company_name = 'pri'::bpchar)
                                                                     Rows Removed by Filter: 25
                                                   ->  Memoize  (cost=0.30..0.33 rows=1 width=4) (actual time=0.000..0.000 rows=0 loops=95491)
                                                         Cache Key: ws1.ws_ship_date_sk
                                                         Cache Mode: logical
                                                         Hits: 67  Misses: 413  Evictions: 0  Overflows: 0  Memory Usage: 28kB
                                                         Worker 0:  Hits: 44145  Misses: 1934  Evictions: 0  Overflows: 0  Memory Usage: 131kB
                                                         Worker 1:  Hits: 46993  Misses: 1939  Evictions: 0  Overflows: 0  Memory Usage: 131kB
                                                         ->  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=4286)
                                                               Index Cond: (d_date_sk = ws1.ws_ship_date_sk)
                                                               Filter: ((d_date >= '1999-05-01'::date) AND (d_date <= '1999-06-30 00:00:00'::timestamp without time zone))
                                                               Rows Removed by Filter: 1
                                             ->  Index Scan using customer_address_pkey on customer_address  (cost=0.29..0.32 rows=1 width=4) (actual time=0.004..0.004 rows=0 loops=1752)
                                                   Index Cond: (ca_address_sk = ws1.ws_ship_addr_sk)
                                                   Filter: (ca_state = 'TX'::bpchar)
                                                   Rows Removed by Filter: 1
                                 ->  Hash  (cost=388535.46..388535.46 rows=37049 width=8) (actual time=4936.733..4936.734 rows=42249 loops=1)
                                       Buckets: 65536  Batches: 1  Memory Usage: 2163kB
                                       ->  HashAggregate  (cost=388164.97..388535.46 rows=37049 width=8) (actual time=4926.772..4931.933 rows=42249 loops=1)
                                             Group Key: web_returns.wr_order_number
                                             Batches: 1  Memory Usage: 3345kB
                                             ->  Hash Join  (cost=2942.67..365438.21 rows=9090701 width=8) (actual time=230.033..4014.732 rows=8677946 loops=1)
                                                   Hash Cond: (ws_wh_1.ws_order_number = web_returns.wr_order_number)
                                                   ->  CTE Scan on ws_wh ws_wh_1  (cost=0.00..144847.22 rows=7242361 width=4) (actual time=211.163..2765.479 rows=6644004 loops=1)
                                                   ->  Hash  (cost=2045.63..2045.63 rows=71763 width=4) (actual time=18.445..18.445 rows=71763 loops=1)
                                                         Buckets: 131072  Batches: 1  Memory Usage: 3547kB
                                                         ->  Seq Scan on web_returns  (cost=0.00..2045.63 rows=71763 width=4) (actual time=0.025..10.838 rows=71763 loops=1)
                           ->  CTE Scan on ws_wh  (cost=0.00..144847.22 rows=7242361 width=4) (actual time=0.002..232.953 rows=3312465 loops=121)
 Planning Time: 2.967 ms
 Execution Time: 56689.671 ms
(63 rows)

If applying this patch:

diff --git a/src/backend/optimizer/plan/analyzejoins.c b/src/backend/optimizer/plan/analyzejoins.c
index c3fd4a81f8..c99282cda6 100644
--- a/src/backend/optimizer/plan/analyzejoins.c
+++ b/src/backend/optimizer/plan/analyzejoins.c
@@ -1231,7 +1231,7 @@ innerrel_is_unique(PlannerInfo *root,
        }

        /* No cached information, so try to make the proof. */
-       if (is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
+       if (!is_innerrel_unique_for(root, joinrelids, outerrelids, innerrel,
                                                           jointype, restrictlist))
        {
                /*

The execution time is reduced to 6 seconds:

                                                                                            QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=441755.76..441755.77 rows=1 width=72) (actual time=6508.013..6508.256 rows=1 loops=1)
   CTE ws_wh
     ->  Hash Join  (cost=37772.14..74062.53 rows=7095248 width=12) (actual time=203.407..560.264 rows=719205 loops=1)
           Hash Cond: (ws1_1.ws_order_number = ws2.ws_order_number)
           Join Filter: (ws1_1.ws_warehouse_sk <> ws2.ws_warehouse_sk)
           Rows Removed by Join Filter: 255623
           ->  Seq Scan on web_sales ws1_1  (cost=0.00..25968.84 rows=719384 width=8) (actual time=0.021..95.808 rows=719384 loops=1)
           ->  Hash  (cost=25968.84..25968.84 rows=719384 width=8) (actual time=202.456..202.457 rows=719384 loops=1)
                 Buckets: 262144  Batches: 8  Memory Usage: 5563kB
                 ->  Seq Scan on web_sales ws2  (cost=0.00..25968.84 rows=719384 width=8) (actual time=0.017..105.868 rows=719384 loops=1)
   ->  Sort  (cost=367693.24..367693.24 rows=1 width=72) (actual time=6508.012..6508.252 rows=1 loops=1)
         Sort Key: (count(DISTINCT ws1.ws_order_number))
         Sort Method: quicksort  Memory: 25kB
         ->  Aggregate  (cost=367693.22..367693.23 rows=1 width=72) (actual time=6507.989..6508.230 rows=1 loops=1)
               ->  Sort  (cost=367693.16..367693.18 rows=5 width=16) (actual time=6507.943..6508.189 rows=121 loops=1)
                     Sort Key: ws1.ws_order_number
                     Sort Method: quicksort  Memory: 29kB
                     ->  Nested Loop Semi Join  (cost=189126.19..367693.11 rows=5 width=16) (actual time=998.191..6508.088 rows=121 loops=1)
                           Join Filter: (ws1.ws_order_number = ws_wh.ws_order_number)
                           Rows Removed by Join Filter: 43344728
                           ->  Nested Loop  (cost=189126.19..212112.41 rows=5 width=24) (actual time=909.308..911.031 rows=121 loops=1)
                                 Join Filter: (web_site.web_site_sk = ws1.ws_web_site_sk)
                                 Rows Removed by Join Filter: 4359
                                 ->  Hash Join  (cost=189126.19..212107.84 rows=29 width=28) (actual time=909.243..910.378 rows=896 loops=1)
                                       Hash Cond: (ws1.ws_order_number = web_returns.wr_order_number)
                                       ->  Gather  (cost=3050.28..26031.49 rows=45 width=20) (actual time=10.506..11.281 rows=1103 loops=1)
                                             Workers Planned: 2
                                             Workers Launched: 2
                                             ->  Nested Loop  (cost=2050.28..25026.99 rows=19 width=20) (actual time=8.162..64.689 rows=368 loops=3)
                                                   ->  Parallel Hash Join  (cost=2049.99..24947.90 rows=242 width=24) (actual time=6.293..52.376 rows=4465 loops=3)
                                                         Hash Cond: (ws1.ws_ship_date_sk = date_dim.d_date_sk)
                                                         ->  Parallel Seq Scan on web_sales ws1  (cost=0.00..21772.43 rows=299743 width=28) (actual time=0.024..24.598 rows=239795 loops=3)
                                                         ->  Parallel Hash  (cost=2049.55..2049.55 rows=35 width=4) (actual time=5.895..5.896 rows=20 loops=3)
                                                               Buckets: 1024  Batches: 1  Memory Usage: 40kB
                                                               ->  Parallel Seq Scan on date_dim  (cost=0.00..2049.55 rows=35 width=4) (actual time=4.855..5.816 rows=20 loops=3)
                                                                     Filter: ((d_date >= '1999-05-01'::date) AND (d_date <= '1999-06-30 00:00:00'::timestamp without time zone))
                                                                     Rows Removed by Filter: 24329
                                                   ->  Index Scan using customer_address_pkey on customer_address  (cost=0.29..0.32 rows=1 width=4) (actual time=0.003..0.003 rows=0 loops=13394)
                                                         Index Cond: (ca_address_sk = ws1.ws_ship_addr_sk)
                                                         Filter: (ca_state = 'TX'::bpchar)
                                                         Rows Removed by Filter: 1
                                       ->  Hash  (cost=185612.75..185612.75 rows=37053 width=8) (actual time=898.519..898.521 rows=42249 loops=1)
                                             Buckets: 65536  Batches: 1  Memory Usage: 2163kB
                                             ->  HashAggregate  (cost=185242.22..185612.75 rows=37053 width=8) (actual time=888.235..893.423 rows=42249 loops=1)
                                                   Group Key: web_returns.wr_order_number
                                                   Batches: 1  Memory Usage: 3345kB
                                                   ->  Hash Join  (cost=2942.67..163474.00 rows=8707289 width=8) (actual time=223.693..825.681 rows=518567 loops=1)
                                                         Hash Cond: (ws_wh_1.ws_order_number = web_returns.wr_order_number)
                                                         ->  CTE Scan on ws_wh ws_wh_1  (cost=0.00..141904.96 rows=7095248 width=4) (actual time=203.411..706.045 rows=719205 loops=1)
                                                         ->  Hash  (cost=2045.63..2045.63 rows=71763 width=4) (actual time=19.983..19.983 rows=71763 loops=1)
                                                               Buckets: 131072  Batches: 1  Memory Usage: 3547kB
                                                               ->  Seq Scan on web_returns  (cost=0.00..2045.63 rows=71763 width=4) (actual time=0.026..12.516 rows=71763 loops=1)
                                 ->  Materialize  (cost=0.00..2.40 rows=5 width=4) (actual time=0.000..0.000 rows=5 loops=896)
                                       ->  Seq Scan on web_site  (cost=0.00..2.38 rows=5 width=4) (actual time=0.046..0.052 rows=5 loops=1)
                                             Filter: (web_company_name = 'pri'::bpchar)
                                             Rows Removed by Filter: 25
                           ->  CTE Scan on ws_wh  (cost=0.00..141904.96 rows=7095248 width=4) (actual time=0.001..25.301 rows=358222 loops=121)
 Planning Time: 3.432 ms
 Execution Time: 6512.766 ms
(59 rows)

The difference between both query plans is the second one uses Materialize instead of Memoize. From the code, it seems that changing the usage of the cache brings performance improvement unexpectedly.

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: David Rowley <[email-masked]>
Date: Tue, 26 Nov 2024 11:41:22 +1300

> The difference between both query plans is the second one uses Materialize instead of Memoize. From the code, it seems that changing the usage of the cache brings performance improvement unexpected…

What's going on here is that you've introduced a new bug which has the
Hash Join effectively perform a semi-join rather than an inner join so
that it only joins the first matching inner-side row instead of all
matching inner-side rows for each outer-side row. The bug is fairly
evident when to see that the Hash Join produces 6644004 rows without
your change and only 719205 rows after you added the bug.

I'm not sure what you expect us to do here, but just in case you're
not aware, we're not going to prioritise performance over correct
results.

I expect the problem you've introduced will be more evident if you use
EXPLAIN ANALYZE VERBOSE. The verbose option will show which joins are
marked "Inner Unique". If you want to learn more about the
optimisation you've broken, see [1].

David

[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=9c7f5229ad68d7e0e4dd149e3f80257893e404d4