MonetDB: Oct2014 - Reimplemented rangejoin, now using imprints o...

Roberto Cornacchia roberto.cornacchia at gmail.com
Wed Jan 28 15:33:17 CET 2015


On 28 January 2015 at 15:12, Sjoerd Mullender <sjoerd at 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 at 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 at monetdb.org
> > https://www.monetdb.org/mailman/listinfo/developers-list
> >
>
>
> --
> Sjoerd Mullender
>
>
> _______________________________________________
> developers-list mailing list
> developers-list at monetdb.org
> https://www.monetdb.org/mailman/listinfo/developers-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.monetdb.org/pipermail/developers-list/attachments/20150128/d4bd5ee0/attachment.html>


More information about the developers-list mailing list