[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@ak.jp.nec.com>
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On 2015-06-10 PM 01:42, Kouhei Kaigai wrote:
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.
Unless I am missing something (of your idea or how hash join works), it seems
that there is no way to apply the filter qual (hash_func(X) % 4 = 0, etc.) at
the Hash node. So, that qual would not be able to limit what gets into the
inner hash table, right? Perhaps the qual needs to be pushed all the way down
to the Hash's underlying scan if that makes sense.
Thanks,
Amit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On Wed, Jun 10, 2015 at 2:16 PM, Amit Langote <Langote_Amit_f8@lab.ntt.co.jp
wrote:
Perhaps the qual needs to be pushed all the way down
to the Hash's underlying scan if that makes sense.
And that is a Pandora's box of troubles IMHO unless done in a very careful
manner.
On 2015-06-10 PM 05:53, Atri Sharma wrote:
On Wed, Jun 10, 2015 at 2:16 PM, Amit Langote <Langote_Amit_f8@lab.ntt.co.jp
wrote:
Perhaps the qual needs to be pushed all the way down
to the Hash's underlying scan if that makes sense.And that is a Pandora's box of troubles IMHO unless done in a very careful
manner.
More appropriately, that's a predicate (should not have called it a qual)
derived from partitioning-optimization specific knowledge.
Thanks,
Amit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On 2015-06-10 PM 01:42, Kouhei Kaigai wrote:
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.Unless I am missing something (of your idea or how hash join works), it seems
that there is no way to apply the filter qual (hash_func(X) % 4 = 0, etc.) at
the Hash node. So, that qual would not be able to limit what gets into the
inner hash table, right? Perhaps the qual needs to be pushed all the way down
to the Hash's underlying scan if that makes sense.
Really? It seems to me just below of the ExecProcNode() in MultiExecHash()
is my expected location to filter out obviously unmatched tuples.
As long as we can construct a qualifier based on CHECK() constraint
of the other side, ExecQual() makes a decision whether fetched tuple
should be loaded to inner hash-table, or not.
Thanks,
--
NEC Business Creation Division / PG-Strom Project
KaiGai Kohei <kaigai@ak.jp.nec.com>
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
How to use this optimization ?
select *
from table join partitioned_table on (
table.part_id = partitioned_table.id
and hash_func_mod(table.part_id) = hash_func_mod(partitioned_table.id)
)
Import Notes
Resolved by subject fallback
On Wed, Jun 10, 2015 at 8:33 PM, Kouhei Kaigai <kaigai@ak.jp.nec.com> wrote:
On 2015-06-10 PM 01:42, Kouhei Kaigai wrote:
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.Unless I am missing something (of your idea or how hash join works), it seems
that there is no way to apply the filter qual (hash_func(X) % 4 = 0, etc.) at
the Hash node. So, that qual would not be able to limit what gets into the
inner hash table, right? Perhaps the qual needs to be pushed all the way down
to the Hash's underlying scan if that makes sense.Really? It seems to me just below of the ExecProcNode() in MultiExecHash()
is my expected location to filter out obviously unmatched tuples.
As long as we can construct a qualifier based on CHECK() constraint
of the other side, ExecQual() makes a decision whether fetched tuple
should be loaded to inner hash-table, or not.
Ah that's an idea. I was thinking of unmodified MultiExecHash().
Thanks,
Amit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
On Wed, Jun 10, 2015 at 8:48 PM, Rosiński Krzysztof 2 - Detal
<Krzysztof.Rosinski2@orange.com> wrote:
How to use this optimization ?
select *
from table join partitioned_table on (
table.part_id = partitioned_table.id
and hash_func_mod(table.part_id) = hash_func_mod(partitioned_table.id)
)
If I read the proposed idea correctly, you wouldn't need to add that
second condition.
Thanks,
Amit
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers