Re: Postgresql 14/15/16/17 partition pruning on dependent table during join

[Andrei Lepikhov]

On 4/11/2024 15:23, Stepan Yankevych wrote:
Let's classify it as possible improvement / new feature for further 
releases.
Optimizer definitely should be able to add that extra (redundant) 
condition *and e.exec_date_id >= 20241021*

or even transform* e.exec_date_id >= co.create_date_id *
to  *e.exec_date_id >= **20241021*
Not sure it would be easy (and make sense) to implement it as a core 
feature. But the idea of the extensibility of the clause deduction 
system looks spectacular to me.


--
regards, Andrei Lepikhov

Re: Postgresql 14/15/16/17 partition pruning on dependent table during join

[Stepan Yankevych]

Let's classify it as possible improvement / new feature for further releases.
Optimizer definitely should be able to add that extra (redundant) condition  
and e.exec_date_id >= 20241021
or even transform e.exec_date_id >= co.create_date_id
to  e.exec_date_id >= 20241021



Stepan Yankevych



From: Andrei Lepikhov 
Sent: Sunday, November 3, 2024 4:42 AM
To: Vijaykumar Jain ; Stepan Yankevych 

Cc: pgsql-performance@lists.postgresql.org 

Subject: Re: Postgresql 14/15/16/17 partition pruning on dependent table during 
join

On 3/11/2024 03:21, Vijaykumar Jain wrote:
> On Fri, 1 Nov 2024 at 18:51, Stepan Yankevych  
> wrote:
>>
>> Partition pruning is not pushing predicate into dependent table during join 
>> in some cases.
>> See example. Predicate highlighted in red
>>
>
> i think your observation is correct.
> you may need to provide redundant predicates for join both tables to
> prune partition (as below).
>
> there is explanation on how dynamic pruning works for some cases, but
> idk which part satisfies this case.
> https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.postgresql.org%2Fdocs%2Fcurrent%2Fddl-partitioning.html%23DDL-PARTITION-PRUNING&data=05%7C02%7CStepan_Yankevych%40epam.com%7Cb0119e5e3c5e47a7dd5f08dcfbb13be0%7Cb41b72d04e9f4c268a69f949f367c91d%7C1%7C0%7C638661985836678039%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=xqVRyWW11KoN0qFb%2FZsTO%2FjijULLW84NSW8lURa5UzY%3D&reserved=0
>
> explain select *
> from public.orders co
> left join public.execution e on e.order_id = co.order_id and
> e.exec_date_id >= co.create_date_id
> where co.order_text in ('Order 5259 - F968FDC8')
> and co.create_date_id = 20241021
> and e.exec_date_id >= 20241021; -- this is redundant but without this
> pruning does not work.
>
> i can be corrected and would be great if someone explains with more
> detail which i cannot due to lack of understanding of dynamic pruning.
I guess you think that Postgres should create an additional clause on
the 'e.exec_date_id from' the chain of:

'co.create_date_id = 20241021 and e.exec_date_id >= co.create_date_id'

but Postgres doesn't have such a functionality yet. It can deduce
clauses from equivalence clauses only. For example, having 'x=1 AND
x=y', Postgres can build a new clause 'y=1'. But it doesn't work for
inequalities [1].
So, to perform partition pruning on the table 'e', you need to add this
redundant clause.

[1]
https://eur01.safelinks.protection.outlook.com/?url=https%3A%2F%2Fwww.postgresql.org%2Fmessage-id%2Fflat%2FCAKJS1f9FK_X_5HKcPcSeimy16Owe3EmPmmGsGWLcKkj_rW9s6A%2540mail.gmail.com&data=05%7C02%7CStepan_Yankevych%40epam.com%7Cb0119e5e3c5e47a7dd5f08dcfbb13be0%7Cb41b72d04e9f4c268a69f949f367c91d%7C1%7C0%7C638661985836699390%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C0%7C%7C%7C&sdata=P3TVf%2FVm2s48xqB00DBaO0LQAlq4%2BGdcXbtpEU0XNi4%3D&reserved=0

--
regards, Andrei Lepikhov

Performance of Query 2 in TPC-H

[Ba Jinsheng]

Please see this case:

TPC-H query 2:

select
s_acctbal,
s_name,
n_name,
p_partkey,
p_mfgr,
s_address,
s_phone,
s_comment
from
PART,
SUPPLIER,
PARTSUPP,
NATION,
REGION
where
p_partkey = ps_partkey
and s_suppkey = ps_suppkey
and p_size = 30
and p_type like '%STEEL'
and s_nationkey = n_nationkey
and n_regionkey = r_regionkey
and r_name = 'ASIA'
and ps_supplycost = (
select
min(ps_supplycost)
from
PARTSUPP,
SUPPLIER,
NATION,
REGION
where
p_partkey = ps_partkey
and s_suppkey = ps_suppkey
and s_nationkey = n_nationkey
and n_regionkey = r_regionkey
and r_name = 'ASIA'
)
order by
s_acctbal desc,
n_name,
s_name,
p_partkey
limit
100;



Its query plan and execution time:


 QUERY PLAN

 Limit  (cost=66275.04..66275.05 rows=1 width=192) (actual 
time=268.349..268.418 rows=100 loops=1)
   ->  Sort  (cost=66275.04..66275.05 rows=1 width=192) (actual 
time=268.348..268.411 rows=100 loops=1)
 Sort Key: supplier.s_acctbal DESC, nation.n_name, supplier.s_name, 
part.p_partkey
 Sort Method: top-N heapsort  Memory: 70kB
 ->  Hash Join  (cost=37831.01..66275.03 rows=1 width=192) (actual 
time=230.386..268.130 rows=485 loops=1)
   Hash Cond: ((part.p_partkey = partsupp.ps_partkey) AND ((SubPlan 
1) = partsupp.ps_supplycost))
   ->  Gather  (cost=1000.00..6425.40 rows=784 width=30) (actual 
time=0.586..0.753 rows=826 loops=1)
 Workers Planned: 2
 Workers Launched: 2
 ->  Parallel Seq Scan on part  (cost=0.00..5347.00 
rows=327 width=30) (actual time=0.082..16.979 rows=275 loops=3)
   Filter: (((p_type)::text ~~ '%STEEL'::text) AND 
(p_size = 30))
   Rows Removed by Filter: 66391
   ->  Hash  (cost=30524.01..30524.01 rows=16 width=172) 
(actual time=228.502..228.506 rows=160240 loops=1)
 Buckets: 65536  Batches: 8  Memory Usage: 4648kB
 ->  Hash Join  (cost=408.01..30524.01 rows=16 
width=172) (actual time=4.820..165.744 rows=160240 loops=1)
   Hash Cond: (partsupp.ps_suppkey = supplier.s_suppkey)
   ->  Seq Scan on partsupp  (cost=0.00..25516.00 
rows=80 width=14) (actual time=0.013..63.459 rows=80 loops=1)
   ->  Hash  (cost=383.01..383.01 rows=2000 width=166) 
(actual time=4.789..4.792 rows=2003 loops=1)
 Buckets: 2048  Batches: 1  Memory Usage: 413kB
 ->  Hash Join  (cost=2.51..383.01 rows=2000 
width=166) (actual time=0.098..3.945 rows=2003 loops=1)
   Hash Cond: (supplier.s_nationkey = 
nation.n_nationkey)
   ->  Seq Scan on supplier  
(cost=0.00..323.00 rows=1 width=144) (actual time=0.013..2.060 rows=1 
loops=1)
   ->  Hash  (cost=2.45..2.45 rows=5 
width=30) (actual time=0.053..0.055 rows=5 loops=1)
 Buckets: 1024  Batches: 1  Memory 
Usage: 9kB
 ->  Hash Join  (cost=1.07..2.45 
rows=5 width=30) (actual time=0.043..0.049 rows=5 loops=1)
   Hash Cond: 
(nation.n_regionkey = region.r_regionkey)
   ->  Seq Scan on nation  
(cost=0.00..1.25 rows=25 width=34) (actual time=0.008..0.010 rows=25 loops=1)
   ->  Hash  (cost=1.06..1.06 
rows=1 width=4) (actual time=0.014..0.014 rows=1 loops=1)
 Buckets: 1024  
Batches: 1  Memory Usage: 9kB
 ->  Seq Scan on region 
 (cost=0.00..1.06 rows=1 width=4) (actual time=0.009..0.010 rows=1 loops=1)
   Filter: (r_name 
= 'ASIA'::bpchar)
   Rows Removed by 
Filter: 4
   SubPlan 1
 ->  Aggregate  (cost=48.70..48.71 rows=1 width=32) (actual 
time=0.018..0.018 rows=1 loops=1311)
   ->  Nested Loop  (cost=0.85..48.70 rows=1 width=6) 
(actual time=0.013..0.017 rows=1 loops=1311)
 Join Filter: (region_1.r_regionkey = 
nation_1.n_regionkey)
 Rows Removed by Join Filte

Re: Performance of Query 2 in TPC-H

[Andrei Lepikhov]

On 11/4/24 15:42, Ba Jinsheng wrote:
The estimated cost is reduced by 90%, and the execution time is reduced 
by 68%. The second query plan includes the operation Memoize, while the 
first query plan does not. I am wondering if we can optimize the logic 
anywhere to enable the second query plan.

Thanks for the curious case.
I discovered this case superficially yet, but have some results to discuss.
Postgres doesn't consider the Memoize case here because, inside the 
JOIN's inner input, we reference the p_partkey column twice, which is 
the primary key of the 'part' table. So, the cardinality of such a join 
will always be 1. That's what we exactly watch there:


->  Nested Loop  (cost=1049.15..16228.66 rows=1 width=34) (actual 
time=0.617..39.544 rows=485 loops=1)


And all the joins upstairs are also NestLoop, because of this original 
error. So, if you want to find a solution - discuss how to estimate 
correctly clauses like:

(x=PRIMARY KEY) AND (y=PRIMARY KEY).

The second thing here is: if you replace '=' with 'IN':
and ps_supplycost = (select min(ps_supplycost) ...
and ps_supplycost IN (select min(ps_supplycost) ...

You will have pulled up a subquery. On my laptop, this trick accelerated 
the query from 333ms to 44ms. That's exactly one of the tricks (IMO) 
that swarm64 used years ago to show that it is faster than upstream 
Postgres.
I want to work around this optimisation a bit later because to do a 
pull-up, we need to prove the single result of the subquery beforehand.


Also, playing with AQO, as usual, I found two alternative query plans 
that the optimiser can find in the case of more or less correct 
cardinality prediction. See these plans in the attachment. I hope they 
can be useful for your further analysis.


--
regards, Andrei Lepikhov
 Limit  (cost=16231.61..16231.62 rows=1 width=195) (actual time=44.053..44.115 
rows=100 loops=1)
   ->  Sort  (cost=16231.61..16231.62 rows=1 width=195) (actual 
time=44.051..44.109 rows=100 loops=1)
 Sort Key: supplier.s_acctbal DESC, nation.n_name, supplier.s_name, 
part.p_partkey
 Sort Method: top-N heapsort  Memory: 69kB
 ->  Nested Loop  (cost=1049.43..16231.60 rows=1 width=195) (actual 
time=0.649..43.628 rows=485 loops=1)
   Join Filter: (region.r_regionkey = nation.n_regionkey)
   ->  Nested Loop  (cost=1049.43..16230.53 rows=1 width=199) 
(actual time=0.642..42.753 rows=485 loops=1)
 Join Filter: (nation.n_nationkey = supplier.s_nationkey)
 Rows Removed by Join Filter: 6381
 ->  Nested Loop  (cost=1049.43..16228.97 rows=1 width=170) 
(actual time=0.629..41.048 rows=485 loops=1)
   ->  Nested Loop  (cost=1049.15..16228.66 rows=1 
width=34) (actual time=0.617..39.544 rows=485 loops=1)
 ->  Gather  (cost=1000.00..6458.40 rows=804 
width=30) (actual time=0.422..10.338 rows=826 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on part  
(cost=0.00..5378.00 rows=335 width=30) (actual time=0.072..14.345 rows=275 
loops=3)
 Filter: (((p_type)::text ~~ 
'%STEEL'::text) AND (p_size = 30))
 Rows Removed by Filter: 66391
 ->  Hash Join  (cost=49.15..61.23 rows=1 
width=8) (actual time=0.034..0.034 rows=1 loops=826)
   Hash Cond: (partsupp.ps_supplycost = 
(min(partsupp_1.ps_supplycost)))
   ->  Index Scan using partsupp_pkey on 
partsupp  (cost=0.42..12.50 rows=4 width=14) (actual time=0.004..0.005 rows=4 
loops=485)
 Index Cond: (ps_partkey = 
part.p_partkey)
   ->  Hash  (cost=48.71..48.71 rows=1 
width=32) (actual time=0.029..0.029 rows=1 loops=826)
 Buckets: 1024  Batches: 1  Memory 
Usage: 9kB
 ->  Aggregate  (cost=48.70..48.71 
rows=1 width=32) (actual time=0.029..0.029 rows=1 loops=826)
   ->  Nested Loop  
(cost=0.85..48.70 rows=1 width=6) (actual time=0.022..0.028 rows=1 loops=826)
 Join Filter: 
(region_1.r_regionkey = nation_1.n_regionkey)
 Rows Removed by Join 
Filter: 3
 ->  Seq Scan on region 
region_1  (cost=0.00..1.06 rows=1 width=4) (actual time=0.001..0.002 rows=1 
loops=826)
   Filter: (r_name 
= 'ASIA'::bpchar)
   Rows Removed by 
Filter: 4