[idea] table partition + hash join

From: Kouhei Kaigai <kaigai(at)ak(dot)jp(dot)nec(dot)com>
To: "pgsql-hackers(at)postgreSQL(dot)org" <pgsql-hackers(at)postgresql(dot)org>
Subject: [idea] table partition + hash join
Date: 2015-06-10 04:42:33
Message-ID: 9A28C8860F777E439AA12E8AEA7694F8010F672B@BPXM15GP.gisp.nec.co.jp
Views: Raw Message | Whole Thread | Download mbox | Resend email
Lists: pgsql-hackers


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_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:

-> 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:

-> 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

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

- 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.

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


Browse pgsql-hackers by date

  From Date Subject
Next Message Michael Paquier 2015-06-10 05:41:14 Expending the use of xlog_internal.h's macros
Previous Message Jim Nasby 2015-06-10 04:17:03 Re: The Future of Aggregation