Thread: [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 -> SeqScanon 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 whenHash 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>
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
<div dir="ltr"><br /><div class="gmail_extra"><br /><div class="gmail_quote">On Wed, Jun 10, 2015 at 2:16 PM, Amit Langote<span dir="ltr"><<a href="mailto:Langote_Amit_f8@lab.ntt.co.jp" target="_blank">Langote_Amit_f8@lab.ntt.co.jp</a>></span>wrote:<br /><blockquote class="gmail_quote" style="margin:0px0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br /> Perhaps the qual needs tobe pushed all the way down<br /> to the Hash's underlying scan if that makes sense.<br /></blockquote></div><br clear="all"/><br />And that is a Pandora's box of troubles IMHO unless done in a very careful manner. <br /></div></div>
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
> 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>
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
<div class="WordSection1"><p class="MsoNormal"><span lang="EN-US">How to use this optimization ?</span><p class="MsoNormal"><spanlang="EN-US"> </span><p class="MsoNormal"><span lang="EN-US">select * </span><p class="MsoNormal"><spanlang="EN-US">from table join partitioned_table on (</span><p class="MsoNormal"><span lang="EN-US"> table.part_id = partitioned_table.id </span><p class="MsoNormal"><span lang="EN-US"> and hash_func_mod(table.part_id)= hash_func_mod(partitioned_table.id)</span><p class="MsoNormal"><span lang="EN-US">)</span><pclass="MsoNormal"><span lang="EN-US"> </span><p class="MsoNormal"><span lang="EN-US"> </span></div>
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