On 28 January 2015 at 15:12, Sjoerd Mullender <sjoerd@monetdb.org> wrote:

Our next step will likely be that we do an on-the-fly sort of the left
input and then use the binary search version. A back-of-the-envelope
(*) calculation tells us that this will be faster than doing either an
imprints or nested-loop version quite soon. The sort is O(n log n) and
the binary search that follows is O(m log n) where n is the size of the
left input and m the size of the right input.

That makes sense.

The approach I currently use is n logn + m logm + m + n

So a bit less efficient than the one you mention.

Both imprints and nested
loop are O(n m) (with different constant factors). So the condition has
to do with comparing m and log n. But until this is implemented we have
no idea about the constant factor that is involved here. But it's
likely that we'll initially just always sort the left side unless the
right is very short (max 2 or 3 entries?).

Yep. And when their size are comparable, it won't matter much which one you sort.

Thanks for the preview, looking forward to the next developments of the rangejoin.

Roberto

> On 27 January 2015 at 14:09, Sjoerd Mullender <commits@monetdb.org> wrote:
>
>> Changeset: 5147add3bb38 for MonetDB
>> URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=5147add3bb38
>> Modified Files:
>> gdk/ChangeLog.Oct2014
>> gdk/gdk_join.c
>> gdk/gdk_private.h
>> gdk/gdk_select.c
>> Branch: Oct2014
>> Log Message:
>>
>> Reimplemented rangejoin, now using imprints or binary search if possible.
>>
>>
>
>
>
> _______________________________________________
> developers-list mailing list
> developers-list@monetdb.org
> https://www.monetdb.org/mailman/listinfo/developers-list
>

--
Sjoerd Mullender

_______________________________________________
developers-list mailing list
developers-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/developers-list