[idea] table partition + hash join

Hello,

It might be a corner case optimization, however, it looks
to me worth to share the idea and have discussion.

Table partition + Hash join pushdown
------------------------------------
Hash-join logic works most effectively when inner relation
can be stored within a hash table. So, it is a meaningful
optimization if we can filter out inner tuples not to be
referenced in join preliminary.

Let's assume a table which is partitioned to four portions,
and individual child relations have constraint by hash-value
of its ID field.

tbl_parent
+ tbl_child_0 ... CHECK(hash_func(id) % 4 = 0)
+ tbl_child_1 ... CHECK(hash_func(id) % 4 = 1)
+ tbl_child_2 ... CHECK(hash_func(id) % 4 = 2)
+ tbl_child_3 ... CHECK(hash_func(id) % 4 = 3)

If someone tried to join another relation with tbl_parent
using equivalence condition, like X = tbl_parent.ID, we
know inner tuples that does not satisfies the condition
hash_func(X) % 4 = 0
shall be never joined to the tuples in tbl_child_0.
So, we can omit to load these tuples to inner hash table
preliminary, then it potentially allows to split the
inner hash-table.

Current typical plan structure is below:

HashJoin
-> Append
-> SeqScan on tbl_child_0
-> SeqScan on tbl_child_1
-> SeqScan on tbl_child_2
-> SeqScan on tbl_child_3
-> Hash
-> SeqScan on other_table

It may be rewritable to:

Append
-> HashJoin
-> SeqScan on tbl_child_0
-> Hash ... Filter: hash_func(X) % 4 = 0
-> SeqScan on other_table
-> HashJoin
-> SeqScan on tbl_child_1
-> Hash ... Filter: hash_func(X) % 4 = 1
-> SeqScan on other_table
-> HashJoin
-> SeqScan on tbl_child_2
-> Hash ... Filter: hash_func(X) % 4 = 2
-> SeqScan on other_table
-> HashJoin
-> SeqScan on tbl_child_3
-> Hash ... Filter: hash_func(X) % 4 = 3
-> SeqScan on other_table

Good:
- Reduction of inner hash table size, eventually,
it may reduce nBatches of HashJoin.

Bad:
- Inner relation has to be scanned multiple times.
- Additional CPU cost to evaluate relevant CHECK()
constraint when Hash loads inner relation.

So, unless Hash plan does not expect inner hash split,
above plan is never chosen because of extra cost.
However, it may make sense if work_mem is not enough
to load all the inner relation at once.

Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai(at)ak(dot)jp(dot)nec(dot)com>