MonetDB: Oct2014 - Reimplemented rangejoin, now using imprints o...
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
Thanks for the preview, looking forward to the next developments of the
> > On 27 January 2015 at 14:09, Sjoerd Mullender <commits at monetdb.org>
> >> 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
> > _______________________________________________
> > 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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the developers-list