Обсуждение: Proposal for Merge Join for Non '=' Operators

<div class="WordSection1"><p class="MsoNormal" style="margin-left:0cm;mso-para-margin-left:0gd">I would like to propose
aNew merge join algorithm for optimizing non ‘=’ operators. (‘<’, ‘<=’, ‘>’, ‘>=’)<p class="MsoNormal"
style="margin-left:0cm;mso-para-margin-left:0gd"> <pclass="MsoListParagraphCxSpFirst"
style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l4level1 lfo1"><span
style="mso-list:Ignore">-<spanstyle="font:7.0pt "Times New Roman"">          </span></span>Currently  Merge join is
onlysupported for ‘=’ operator. For ‘<’ or ‘>’ operator it chooses Nest Loop Join, or Nest loop with
materialization.<pclass="MsoListParagraphCxSpMiddle"
style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l4level1 lfo1"><span
style="mso-list:Ignore">-<spanstyle="font:7.0pt "Times New Roman"">          </span></span>I think when tuple from
lowernode is sorted or sorting cost is very less, then we can use Merge Join for Non Equal operator also and which will
givebetter performance than NLJ (for selecting this new cost calculation can be implemented in planner).<p
class="MsoListParagraphCxSpMiddle"style="margin-left:36.0pt;mso-para-margin-left:0gd">  <p
class="MsoListParagraphCxSpMiddle"style="margin-left:36.0pt;mso-para-margin-left:0gd"><b>Example for using merge Join
for< operator.</b><p class="MsoListParagraphCxSpMiddle" style="margin-left:36.0pt;mso-para-margin-left:0gd">
                       T1                    T2<p class="MsoListParagraphCxSpMiddle"
style="margin-left:36.0pt;mso-para-margin-left:0gd">                        3                      1          <p
class="MsoListParagraphCxSpMiddle"style="margin-left:36.0pt;mso-para-margin-left:0gd">                        
4                     2<p class="MsoListParagraphCxSpMiddle" style="margin-left:36.0pt;mso-para-margin-left:0gd">
                       5                      4                      <p class="MsoListParagraphCxSpMiddle"
style="margin-left:36.0pt;mso-para-margin-left:0gd">Outer tuple (3) need to be compared with inner tuple one by one, so
itwill satisfy condition at third inner tuple (as 3<4). So here we can save this point of inner tuple so that next
outertuple can directly start comparison from this tuple.<p class="MsoListParagraphCxSpMiddle"
style="margin-left:57.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l2level1 lfo3"><span
style="mso-list:Ignore">1.<spanstyle="font:7.0pt "Times New Roman"">       </span></span>In this algorithm we can put
onemore optimization: Once outer tuple satisfies the Merge QUAL it can skip the Merge QUAL test with remaining inner
tupleand directly apply Other QUALs, as merge QUAL will always satisfy for remaining tuples.<p
class="MsoListParagraphCxSpMiddle"style="margin-left:36.0pt;mso-para-margin-left:0gd">  <p
class="MsoListParagraphCxSpMiddle"style="margin-left:36.0pt;mso-para-margin-left:0gd"><b>Implementation Detail:</b><p
class="MsoListParagraphCxSpMiddle"style="margin-left:72.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l1
level1lfo4"><span style="mso-list:Ignore">1.<span style="font:7.0pt "Times New Roman"">       </span></span>Need to add
newcost calculation mechanism for this. I still have to work on this part.<p class="MsoListParagraphCxSpMiddle"
style="margin-left:72.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l1level1 lfo4"><span
style="mso-list:Ignore">2.<spanstyle="font:7.0pt "Times New Roman"">       </span></span>Implementing in Executor<p
class="MsoListParagraphCxSpMiddle"style="margin-left:108.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l1
level2lfo4"><span style="mso-list:Ignore">a.<span style="font:7.0pt "Times New Roman"">       </span></span>This
algorithmis almost same as normal merge Join with some changes.<p class="MsoListParagraphCxSpLast"
style="margin-left:108.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l1level2 lfo4"><span
style="mso-list:Ignore">b.<spanstyle="font:7.0pt "Times New Roman"">       </span></span>Both Inner and Outer Data
Sourcesshould be sorted, same as normal merge Join.<p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd"><b>ALGORITHM:</b><pclass="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>MergeQual (R.A < Q.A)</i><p
class="MsoNormal"style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:6.0pt;line-height:normal"><i>r = first
tuplefrom R (Outer Relation)</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:6.0pt;line-height:normal"><i>q= first tuple in Q( Inner
Relation)</i><pclass="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:6.0pt;line-height:normal"><i>save_pos= q;  /* Position
tostart scanning in relation Q*/</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>While(fetch tuple r from R till relation
end)</i><pclass="MsoNormal" style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>{</i><p
class="MsoNormal"style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>            for each tuple q
inQ starting from save_pos</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>           {</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                            Merge Qual
Satisfy</i><pclass="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                            {</i><p
class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                                               
save_pos= q; </i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                                               
Consumeall subsequent tuples and project(just need to match Other Quals if any.)</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                            }</i><p
class="MsoNormal"style="margin-left:78.0pt;mso-para-margin-left:0gd;text-indent:6.0pt;line-height:normal"><i>Else
                                   </i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>                                   Fetch Next
tuplefrom Q;                                                 </i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>           }</i><p class="MsoNormal"
style="margin-left:36.0pt;mso-para-margin-left:0gd;line-height:normal"><i>}</i><pclass="MsoListParagraphCxSpFirst"
style="margin-left:36.0pt;mso-para-margin-left:0gd"> <p class="MsoListParagraphCxSpLast"
style="margin-left:36.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l4level1 lfo1"><span
style="mso-list:Ignore">-<spanstyle="font:7.0pt "Times New Roman"">          </span></span>Performance Comparison:<p
class="MsoNormal"style="margin-left:39.0pt;mso-para-margin-left:0gd">Suppose tuples of inner and outer is already
sortedor Index scan on inner and outer.<p class="MsoNormal"
style="margin-left:39.0pt;mso-para-margin-left:0gd">          <p class="MsoListParagraphCxSpFirst"
style="margin-left:75.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l0level1 lfo5"><span
style="font-family:Symbol"><spanstyle="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">        
</span></span></span>Thencost of NLJ is always O (r*q).<p class="MsoListParagraphCxSpMiddle"
style="margin-left:75.0pt;mso-para-margin-left:0gd;text-indent:-18.0pt;mso-list:l0level1 lfo5"><span
style="font-family:Symbol"><spanstyle="mso-list:Ignore">·<span style="font:7.0pt "Times New Roman"">        
</span></span></span>Thecost of this MJ will be b/w: O (n) to O (r*q).<p class="MsoListParagraphCxSpLast"
style="margin-left:75.0pt;mso-para-margin-left:0gd"> <p class="MsoNormal"
style="margin-left:57.0pt;mso-para-margin-left:0gd">Wherer is number of tuple in R (outer relation) and q is number of
tuplein Q (inner Relation).<p class="MsoNormal" style="margin-left:57.0pt;mso-para-margin-left:0gd"> <p
class="MsoNormal"style="margin-left:21.0pt;mso-para-margin-left:0gd">Please provide your feedback/suggestions.<p
class="MsoNormal"style="margin-left:21.0pt;mso-para-margin-left:0gd"> <p class="MsoNormal"
style="margin-left:21.0pt;mso-para-margin-left:0gd">Thanks& Regards,<p class="MsoNormal"
style="margin-left:21.0pt;mso-para-margin-left:0gd">DilipKumar<p class="MsoNormal" style="margin-left:21.0pt"><span
style="font-size:11.0pt;line-height:150%;font-family:"Calibri","sans-serif""> </span></div>

2014-04-09 Dilip kumar <dilip.kumar@huawei.com>:

> I would like to propose a New merge join algorithm for optimizing non ‘=’
> operators. (‘<’, ‘<=’, ‘>’, ‘>=’)

Do you have a real-world example use case of such joins, to offset the
extra planner time that will likely have to be paid (even for queries
for which the functionality ends up not being used)?

I guess there might be queries that join on “values that are not too
far apart” or something, but as those cases (there typically not being
a lot of “inner” rows that join with each “outer” row) are probably
executed efficiently using a nested loop + index scan, I don’t see the
point (yet). Are you aiming for the case where the inner relation is
difficult to compute and cannot be accessed using an index scan?

> selecting this new cost calculation can be implemented in planner

Hmm. Of course, the difficult part will be adding support for this in
the planner, but you don’t seem to have any plans for implementing
that?

Nicolas

--
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

On 09 April 2014 13:31, Nicolas Barbier Wrote
> Do you have a real-world example use case of such joins, to offset the
> extra planner time that will likely have to be paid (even for queries
> for which the functionality ends up not being used)?
> 
> I guess there might be queries that join on “values that are not too
> far apart” or something, but as those cases (there typically not being
> a lot of “inner” rows that join with each “outer” row) are probably
> executed efficiently using a nested loop + index scan, I don’t see the
> point (yet). Are you aiming for the case where the inner relation is
> difficult to compute and cannot be accessed using an index scan?

I think this will be more useful when Both the relation are Big and are of almost equal size.

Here we can compare the cost of existing methods and new approach..
For such case planner can select 
Either    (1). NLJ [Outer(seq scan) JOIN Inner (Materialize))OR  (2). NLJ [Outer(seq scan) JOIN Inner (Index)) As you
mentioned.   
 
In approach (1), cost will be:    NLJ Cost : Outer Tuple * Inner Tuple    + I/O cost : Seq Page Cost (Inner rel pages +
outerrel pages).
 
    * And relation can be too big for materialization.

In approach (2), Cost will be:        NLJ Cost : OuterTuple * Inner Tuple in Path    { Inner Tuple in Path -> Join
selectivity* Number of inner tuple}    + I/O Cost : OuterTuple * Index Rescan Cost    { Index Rescan Cost will depend
upon(how many pages fetched in scan)} 
 
    * This will be costly because I/O cost will increase for doing multiple index rescan(for each outer).

In New Approach(3) Cost will be:    (since here for each outer tuple we need not to scan complete Inner Tuple.)    MJ
Cost: Outer Tuple * Inner Tuple in Path + (every outer tuple need to scan some tuple before reach to qualifying tuple)
 + I/O Cost : Index Scan Cost                   {Only one scan}      
 
    So for This Best case cost will be : MJ Cost : Outer Tuple * Inner Tuple in Path + I/O Cost : Index Scan Cost
    Worst case cost will be:  MJ Cost : Outer Tuple * Inner Tuple + I/O Cost : Index Scan Cost
 
    So for many case approach(3) can be cheaper, that can be detected by planner cost calculation.


> > selecting this new cost calculation can be implemented in planner
> 
> Hmm. Of course, the difficult part will be adding support for this in
> the planner, but you don’t seem to have any plans for implementing that?
>

Yes, I have plan to implement this part, but it's not completed yet.

Thanks & Regards,
Dilip

Dilip kumar <dilip.kumar@huawei.com> writes:
> On 09 April 2014 13:31, Nicolas Barbier Wrote
>> Do you have a real-world example use case of such joins, to offset the
>> extra planner time that will likely have to be paid (even for queries
>> for which the functionality ends up not being used)?

> I think this will be more useful when Both the relation are Big and are of almost equal size.

I'm not following how this would help much.  Consider "a.x < b.y" where
we know that the inputs are sorted by x/y.  I think you are saying that
for a given b row, we could scan forward from the beginning of a, but
stop as soon as we find a row with a.x >= b.y.  Great ... but instead of
comparing M*N rows, we are comparing M*N/2 rows.  So it's still O(N^2),
though with a slightly smaller constant.  Is this going to be worth the
added time to sort the inputs?

It's slightly more promising for range constraints (that is, "a.x
between b.y and b.z") but even then you have to assume that the ranges
are narrow, at which point a nestloop join using an inner indexscan on
a.x might do about as well.

So personally, I suspect there's a reason why this isn't a standard
join algorithm already.  If you want to try it, I'd suggest that you
focus on getting to where you can do some performance testing ASAP,
without doing much code polishing or worrying about teaching the
planner how to cost it.
        regards, tom lane

On 09 April 2014 19:14, Tom Lane Wrote:
>
> I'm not following how this would help much.  Consider "a.x < b.y" where
> we know that the inputs are sorted by x/y.  I think you are saying that
> for a given b row, we could scan forward from the beginning of a, but
> stop as soon as we find a row with a.x >= b.y.  Great ... but instead
> of comparing M*N rows, we are comparing M*N/2 rows.  So it's still
> O(N^2), though with a slightly smaller constant.  Is this going to be
> worth the added time to sort the inputs?
>
> It's slightly more promising for range constraints (that is, "a.x
> between b.y and b.z") but even then you have to assume that the ranges
> are narrow, at which point a nestloop join using an inner indexscan on
> a.x might do about as well.
>
> So personally, I suspect there's a reason why this isn't a standard
> join algorithm already.  If you want to try it, I'd suggest that you
> focus on getting to where you can do some performance testing ASAP,
> without doing much code polishing or worrying about teaching the
> planner how to cost it.

As per your suggestion have done quick hack and done the performance testing for one specific scenario.

I shall perform some more test, for that I need to do some more hack in the code and I will post them soon..

Test Scenario:
    Create table t1 (a int, b int);
    Create table t2 (a int, b int);

    Random record inserted in t1 and t2, as per attached files. (10K records are inserted in both the tables)

    Performance is taken for the query : select count(*) from t1,t2 where t1.b < t2.b;

Test Result:
    Nest Loop Join :     Time: 36038.842 ms
    Merge Join     :  Time: 19774.975 ms

    Number of record selected: 42291979



Thanks & Regards,
Dilip

On 10 April 2014 14:21, I wrote

>
> I shall perform some more test, for that I need to do some more hack in
> the code and I will post them soon..
>
> Test Scenario:
>     Create table t1 (a int, b int);
>     Create table t2 (a int, b int);
>
>     Random record inserted in t1 and t2, as per attached files. (10K
> records are inserted in both the tables)
>
>     Performance is taken for the query : select count(*) from t1,t2
> where t1.b < t2.b;
>
> Test Result:
>     Nest Loop Join :     Time: 36038.842 ms
>     Merge Join     :  Time: 19774.975 ms

>     Number of record selected: 42291979
I have some more testing with index and multiple conditions..
Test Scenario:    Create table t1 (a int, b int);    Create table t2 (a int, b int);
Create index t1_idx t1(b);Create index t1_idx t1(b);
Query: select count(*) from t1,t2 where t1.b<t2.b and t1.b > 12000;
Test Result:     Nest Loop Join with Index Scan   : 1653.506 ms    Sort Merge Join for (seq scan)   : 610.257ms

From above both the scenario Sort merge join for < operator is faster than NLJ (using seq scan or index scan).

Any suggestion for other performance scenarios are welcome..
Thanks & Regards,
Dilip Kumar