MonetDB: Oct2014 - Avoid binary search in dense candidate list.

[Sjoerd Mullender]

Changeset: c92cb164b9e6 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=c92cb164b9e6
Modified Files:
        gdk/gdk_select.c
Branch: Oct2014
Log Message:

Avoid binary search in dense candidate list.


diffs (19 lines):

diff --git a/gdk/gdk_select.c b/gdk/gdk_select.c
--- a/gdk/gdk_select.c
+++ b/gdk/gdk_select.c
@@ -192,6 +192,15 @@ BAT_hashselect(BAT *b, BAT *s, BAT *bn, 
                l = BUNfirst(b);
                h = BUNlast(b);
        }
+       if (s && BATtdense(s)) {
+               /* no need for binary search in s, we just adjust the
+                * boundaries */
+               if (s->tseqbase > seq)
+                       l += s->tseqbase - seq;
+               if (s->tseqbase + BATcount(s) < seq + (h - l))
+                       h -= seq + BATcount(b) - (s->tseqbase + BATcount(s));
+               s = NULL;
+       }
        b = BATmirror(b);       /* BATprepareHash works on HEAD column */
        if (BATprepareHash(b)) {
                BBPreclaim(bn);
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list