MonetDB: mosaic - Apply binary search to join on dict compressed...

[Aris Koning]

Changeset: 2b3431097e5c for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=2b3431097e5c
Modified Files:
        monetdb5/modules/mosaic/mosaic_dictionary_templates.h
Branch: mosaic
Log Message:

Apply binary search to join on dict compressed mosaic block.


diffs (73 lines):

diff --git a/monetdb5/modules/mosaic/mosaic_dictionary_templates.h 
b/monetdb5/modules/mosaic/mosaic_dictionary_templates.h
--- a/monetdb5/modules/mosaic/mosaic_dictionary_templates.h
+++ b/monetdb5/modules/mosaic/mosaic_dictionary_templates.h
@@ -541,22 +541,63 @@ MOSprojectionloop_SIGNATURE(METHOD, TPE,
 #endif
 
 #ifdef INNER_COMPRESSED_JOIN_LOOP
+
 MOSjoin_inner_loop_SIGNATURE(METHOD, TPE, NIL, RIGHT_CI_NEXT)
 {
        bte bits                = GET_FINAL_BITS(task, METHOD);
        TPE* dict               = GET_FINAL_DICT(task, METHOD, TPE);
+       BUN dict_size   = GET_FINAL_DICT_COUNT(task, METHOD);
+       BUN key;
+       bool key_found = false;
+
+       BUN kfirst      = 0;
+       BUN klast       = dict_size - 1;
+
+       BUN offset = 0;
+
+       #ifdef HAS_NIL
+       if (IS_NIL(TPE, dict[0]) && ((--klast) && (++dict) && (++offset)) && 
IS_NIL(TPE, lval)) {
+               key_found = true;
+               key = 0;
+       }
+       #endif
+       if (!IS_NIL(TPE, lval))
+       while (kfirst <= klast) {
+               BUN kmiddle     = (klast + kfirst) / 2;
+               if (dict[kmiddle] < lval) {
+                       kfirst = kmiddle + 1;
+                       kmiddle = (klast + kfirst) / 2;
+               }
+               else if(dict[kmiddle] == lval) {
+                       key_found = true;
+                       key = kmiddle + offset;
+                       break;
+               }
+               else {
+                       klast = kmiddle -1;
+                       kmiddle = (klast + kfirst) / 2;
+               }
+       }
+
+       if (!key_found) {
+               return MAL_SUCCEED;
+       }
+
        BitVector base  = MOScodevectorDict(task, METHOD, TPE);
     BUN first = task->start;
     BUN last = first + MOSgetCnt(task->blk);
     for (oid ro = canditer_peekprev(task->ci); !is_oid_nil(ro) && ro < last; 
ro = RIGHT_CI_NEXT(task->ci)) {
         BUN i = (BUN) (ro - first);
                BitVectorChunk j= getBitVector(base,i,bits);
-        TPE rval = dict[j];
-               #ifdef HAS_NIL
-        IF_EQUAL_APPEND_RESULT(true, TPE);
-               #else
-               IF_EQUAL_APPEND_RESULT(false, TPE);
-               #endif
+               {
+                       oid lval = (oid) key;
+                       oid rval = (oid) j;
+                       #ifdef HAS_NIL
+                       IF_EQUAL_APPEND_RESULT(true, oid);
+                       #else
+                       IF_EQUAL_APPEND_RESULT(false, oid);
+                       #endif
+               }
        }
        return MAL_SUCCEED;
 }
_______________________________________________
checkin-list mailing list
checkin-list@monetdb.org
https://www.monetdb.org/mailman/listinfo/checkin-list