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

Roberto Cornacchia roberto.cornacchia at
Wed Jan 28 14:49:51 CET 2015

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
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
Best, Roberto

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the developers-list mailing list