<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On 28 January 2015 at 15:12, Sjoerd Mullender <span dir="ltr"><<a href="mailto:sjoerd@monetdb.org" target="_blank">sjoerd@monetdb.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><span class=""><br>
</span>Our next step will likely be that we do an on-the-fly sort of the left<br>
input and then use the binary search version.  A back-of-the-envelope<br>
(*) calculation tells us that this will be faster than doing either an<br>
imprints or nested-loop version quite soon.  The sort is O(n log n) and<br>
the binary search that follows is O(m log n) where n is the size of the<br>
left input and m the size of the right input.  </blockquote><div><br></div><div>That makes sense.</div><div>The approach I currently use is n logn + m logm + m + n</div><div>So a bit less efficient than the one you mention.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">Both imprints and nested<br>
loop are O(n m) (with different constant factors).  So the condition has<br>
to do with comparing m and log n.  But until this is implemented we have<br>
no idea about the constant factor that is involved here.  But it's<br>
likely that we'll initially just always sort the left side unless the<br>
right is very short (max 2 or 3 entries?).<br></blockquote><div><br></div><div>Yep. And when their size are comparable, it won't matter much which one you sort. </div><div><br></div><div><br></div><div>Thanks for the preview, looking forward to the next developments of the rangejoin.</div><div>Roberto</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span class=""><br>
> On 27 January 2015 at 14:09, Sjoerd Mullender <<a href="mailto:commits@monetdb.org">commits@monetdb.org</a>> wrote:<br>
><br>
>> Changeset: 5147add3bb38 for MonetDB<br>
>> URL: <a href="http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=5147add3bb38" target="_blank">http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=5147add3bb38</a><br>
>> Modified Files:<br>
>>         gdk/ChangeLog.Oct2014<br>
>>         gdk/gdk_join.c<br>
>>         gdk/gdk_private.h<br>
>>         gdk/gdk_select.c<br>
>> Branch: Oct2014<br>
>> Log Message:<br>
>><br>
>> Reimplemented rangejoin, now using imprints or binary search if possible.<br>
>><br>
>><br>
><br>
><br>
><br>
</span>> _______________________________________________<br>
> developers-list mailing list<br>
> <a href="mailto:developers-list@monetdb.org">developers-list@monetdb.org</a><br>
> <a href="https://www.monetdb.org/mailman/listinfo/developers-list" target="_blank">https://www.monetdb.org/mailman/listinfo/developers-list</a><br>
><br>
<span class=""><font color="#888888"><br>
<br>
--<br>
Sjoerd Mullender<br>
<br>
</font></span><br>_______________________________________________<br>
developers-list mailing list<br>
<a href="mailto:developers-list@monetdb.org">developers-list@monetdb.org</a><br>
<a href="https://www.monetdb.org/mailman/listinfo/developers-list" target="_blank">https://www.monetdb.org/mailman/listinfo/developers-list</a><br>
<br></blockquote></div></div></div>