Subject: Re: Asymmetric partition-wise JOIN

From: Andrei Lepikhov <[email-masked]>
Date: Tue, 2 Apr 2024 10:07:35 +0700

On 15/10/2023 13:25, Alexander Korotkov wrote:
> Great!  I'm looking forward to the revised patch.
Revising the code and opinions before restarting this work, I found two 
different possible strategies mentioned in the thread:
1. 'Common Resources' shares the materialised result of the inner table 
scan (a hash table in the case of HashJoin) to join each partition one 
by one. It gives us a profit in the case of parallel append and possibly 
other cases, like the one shown in the initial message.
2. 'Individual strategies' - By limiting the AJ feature to cases when 
the JOIN clause contains a partitioning expression, we can push an 
additional scan clause into each copy of the inner table scan, reduce 
the number of tuples scanned, and even prune something because of proven 
zero input.

I see the pros and cons of both approaches. The first option is more 
straightforward, and its outcome is obvious in the case of parallel 
append. But how can we guarantee the same join type for each join? Why 
should we ignore the positive effect of different strategies for 
different partitions?
The second strategy is more expensive for the optimiser, especially in 
the multipartition case. But as I can predict, it is easier to implement 
and looks more natural for the architecture. What do you think about that?

-- 
regards,
Andrei Lepikhov
Postgres Professional

---

From: Alexander Korotkov <[email-masked]>
Date: Thu, 1 Aug 2024 21:56:12 +0300

Hi!

> and looks more natural for the architecture. What do you think about that?

Actually, the idea I tried to express is the combination of #1 and #2:
to build individual plan for every partition, but consider the 'Common
Resources'.  Let me explain this a bit more.

Right now, we basically we consider the following properties during
selection of paths.
1) Cost.  The cheaper path wins.  There a two criteria though: startup
cost and total cost.  So, we can keep both paths with cheaper startup
costs and paths with cheaper total cost.
2) Pathkeys.  We can keep a path with more expensive path, which has
pathkeys potentially useful in future.

My idea is to introduce a new property for paths selection.
3) Usage of common resources.  The common resource can be: hash
representation of relation, memoize over relation scan, etc.  We can
exclude the cost of common resource generation from the path cost, but
keep the reference for the common resource with its generation cost.
If one path uses more common resources than another path, it could
cost-dominate another one only if its cheaper together with its extra
common resources cost.  If one path uses less or equal common
resources than another, it could normally cost-dominate another one.

Using these rules, we can gather the the plurality of paths for each
child join taking common resources into account.  After that we can
apply some global optimization finding generation of which common
resources can reduce the global cost.

However, I understand this is huge amount of work given we have to
introduce new basic optimizer concepts.  I get that the main
application of this patch is sharding.  If we have global tables
residing each shard, we can push down any joins with them.  Given this
patch gives some optimization for non-sharded case, I think we
*probably* can accept its concept even that it this optimization is
obviously not perfect.

------
Regards,
Alexander Korotkov
Supabase

---

From: Andrei Lepikhov <[email-masked]>
Date: Mon, 19 Aug 2024 10:43:35 +0200

> Resources'.  Let me explain this a bit more.
Thanks for keeping your eye on it!
> resources than another, it could normally cost-dominate another one.
The most challenging part for me is the cost calculation, which is 
bonded with estimations of other paths. To correctly estimate the 
effect, we need to remember at least the whole number of paths sharing 
resources.
Also, I wonder if it can cause some corner cases where prediction error 
on a shared resource will cause an even worse situation upstream.
I think we could push off here from an example and a counter-example, 
but I still can't find them.

> *probably* can accept its concept even that it this optimization is
Yes, right now sharding is the most profitable case. We can push down 
parts of the plan which references only some common resources: 
FunctionScan, ValueScan, tables which can be proved are existed 
everywhere and provide the same output. But for now it is too far from 
the core code, IMO. - So, I search for cases that can be helpful for a 
single instance.

-- 
regards,
Andrei Lepikhov
Postgres Professional