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

Sjoerd Mullender sjoerd at
Wed Jan 28 15:12:09 CET 2015

On 28/01/15 14:49, Roberto Cornacchia wrote:
> Hi Sjoerd,
> This is very welcome!
> If I read well, this will use, in order of preference:
> 1. binary search (if l is sorted)
> 2. imprints if available

No, if *possible*.  I.e. we make then if needed.

> 3. nested loop otherwise


> We use rangejoin extensively within Spinque and the previous one (just
> nested loop) has never an option.
> So far we have been using our own version which is perhaps naive but proved
> to be effective:
> - sort all inputs if not sorted already
> - perform a mergejon-like fast scan
> Though simple, I have not found so far a case where this strategy would not
> outperform nested loops by far. The cost of sorting was always far less
> than the cost of a full nested loop.
> I was wondering what your thoughts about this would be. Could this strategy
> replace the number 3 above? Does it make sense to keep the vanilla nested
> loop?
> Best, Roberto

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.  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?).

(*) on a whiteboard ;-)

> On 27 January 2015 at 14:09, Sjoerd Mullender <commits at> wrote:
>> Changeset: 5147add3bb38 for MonetDB
>> URL:;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

Sjoerd Mullender

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 291 bytes
Desc: OpenPGP digital signature
URL: <>

More information about the developers-list mailing list