LCOV - code coverage report
Current view: top level - gdk - gdk_join.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 1389 2178 63.8 %
Date: 2021-09-14 19:48:19 Functions: 23 28 82.1 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : #include "monetdb_config.h"
      10             : #include "gdk.h"
      11             : #include "gdk_private.h"
      12             : #include "gdk_calc_private.h"
      13             : 
      14             : /*
      15             :  * All join variants produce some sort of join on two input BATs,
      16             :  * optionally subject to up to two candidate lists.  Only values in
      17             :  * the input BATs that are mentioned in the associated candidate list
      18             :  * (if provided) are eligible.  They all return two output BATs in the
      19             :  * first two arguments.  The join operations differ in the way in
      20             :  * which tuples from the two inputs are matched.
      21             :  *
      22             :  * The outputs consist of two aligned BATs (i.e. same length and same
      23             :  * hseqbase (0@0)) that contain the OIDs of the input BATs that match.
      24             :  * The candidate lists, if given, contain the OIDs of the associated
      25             :  * input BAT which must be considered for matching.  The input BATs
      26             :  * must have the same type.
      27             :  *
      28             :  * All functions also have a parameter nil_matches which indicates
      29             :  * whether NIL must be considered an ordinary value that can match, or
      30             :  * whether NIL must be considered to never match.
      31             :  *
      32             :  * The join functions that are provided here are:
      33             :  * BATjoin
      34             :  *      normal equi-join
      35             :  * BATleftjoin
      36             :  *      normal equi-join, but the left output is sorted
      37             :  * BATouterjoin
      38             :  *      equi-join, but the left output is sorted, and if there is no
      39             :  *      match for a value in the left input, there is still an output
      40             :  *      with NIL in the right output
      41             :  * BATsemijoin
      42             :  *      equi-join, but the left output is sorted, and if there are
      43             :  *      multiple matches, only one is returned (i.e., the left output
      44             :  *      is also key)
      45             :  * BATthetajoin
      46             :  *      theta-join: an extra operator must be provided encoded as an
      47             :  *      integer (macros JOIN_EQ, JOIN_NE, JOIN_LT, JOIN_LE, JOIN_GT,
      48             :  *      JOIN_GE); values match if the left input has the given
      49             :  *      relationship with the right input; order of the outputs is not
      50             :  *      guaranteed
      51             :  * BATbandjoin
      52             :  *      band-join: two extra input values (c1, c2) must be provided as
      53             :  *      well as Booleans (li, hi) that indicate whether the value
      54             :  *      ranges are inclusive or not; values in the left and right
      55             :  *      inputs match if right - c1 <[=] left <[=] right + c2; if c1 or
      56             :  *      c2 is NIL, there are no matches
      57             :  * BATrangejoin
      58             :  *      range-join: the right input consists of two aligned BATs,
      59             :  *      values match if the left value is between two corresponding
      60             :  *      right values; two extra Boolean parameters, li and hi,
      61             :  *      indicate whether equal values match
      62             :  *
      63             :  * In addition to these functions, there are two more functions that
      64             :  * are closely related:
      65             :  * BATintersect
      66             :  *      intersection: return a candidate list with OIDs of tuples in
      67             :  *      the left input whose value occurs in the right input
      68             :  * BATdiff
      69             :  *      difference: return a candidate list with OIDs of tuples in the
      70             :  *      left input whose value does not occur in the right input
      71             :  */
      72             : 
      73             : /* Perform a bunch of sanity checks on the inputs to a join. */
      74             : static gdk_return
      75      800796 : joinparamcheck(BAT *l, BAT *r1, BAT *r2, BAT *sl, BAT *sr, const char *func)
      76             : {
      77     2126180 :         if (ATOMtype(l->ttype) != ATOMtype(r1->ttype) ||
      78         312 :             (r2 && ATOMtype(l->ttype) != ATOMtype(r2->ttype))) {
      79          65 :                 GDKerror("%s: inputs not compatible.\n", func);
      80           0 :                 return GDK_FAIL;
      81             :         }
      82      800731 :         if (r2 &&
      83         156 :             (BATcount(r1) != BATcount(r2) || r1->hseqbase != r2->hseqbase)) {
      84           0 :                 GDKerror("%s: right inputs not aligned.\n", func);
      85           0 :                 return GDK_FAIL;
      86             :         }
      87      800731 :         if ((sl && !BATiscand(sl)) || (sr && !BATiscand(sr))) {
      88           0 :                 GDKerror("%s: argument not a candidate list.\n", func);
      89           0 :                 return GDK_FAIL;
      90             :         }
      91             :         return GDK_SUCCEED;
      92             : }
      93             : 
      94             : #define INCRSIZELOG     (8 + (SIZEOF_OID / 2))
      95             : #define INCRSIZE        (1 << INCRSIZELOG)
      96             : 
      97             : /* Create the result bats for a join, returns the absolute maximum
      98             :  * number of outputs that could possibly be generated. */
      99             : static BUN
     100       93640 : joininitresults(BAT **r1p, BAT **r2p, BUN lcnt, BUN rcnt, bool lkey, bool rkey,
     101             :                 bool semi, bool nil_on_miss, bool only_misses, bool min_one,
     102             :                 BUN estimate)
     103             : {
     104             :         BAT *r1, *r2;
     105             :         BUN maxsize, size;
     106             : 
     107             :         /* if nil_on_miss is set, we really need a right output */
     108       93640 :         assert(!nil_on_miss || r2p != NULL);
     109             : 
     110       93640 :         lkey |= lcnt <= 1;
     111       93640 :         rkey |= rcnt <= 1;
     112             : 
     113       93640 :         *r1p = NULL;
     114       93640 :         if (r2p)
     115       37876 :                 *r2p = NULL;
     116       93640 :         if (lcnt == 0) {
     117             :                 /* there is nothing to match */
     118             :                 maxsize = 0;
     119       80586 :         } else if (!only_misses && !nil_on_miss && rcnt == 0) {
     120             :                 /* if right is empty, we have no hits, so if we don't
     121             :                  * want misses, the result is empty */
     122             :                 maxsize = 0;
     123       80666 :         } else if (rkey | semi | only_misses) {
     124             :                 /* each entry left matches at most one on right, in
     125             :                  * case nil_on_miss is also set, each entry matches
     126             :                  * exactly one (see below) */
     127             :                 maxsize = lcnt;
     128       57906 :         } else if (lkey) {
     129             :                 /* each entry on right is matched at most once */
     130        9916 :                 if (nil_on_miss) {
     131             :                         /* one entry left could match all right, and
     132             :                          * all other entries left match nil */
     133           0 :                         maxsize = lcnt + rcnt - 1;
     134             :                 } else {
     135             :                         maxsize = rcnt;
     136             :                 }
     137       47990 :         } else if (rcnt == 0) {
     138             :                 /* nil_on_miss must be true due to previous checks, so
     139             :                  * all values on left miss */
     140             :                 maxsize = lcnt;
     141       48014 :         } else if (BUN_MAX / lcnt >= rcnt) {
     142             :                 /* in the worst case we have a full cross product */
     143       48095 :                 maxsize = lcnt * rcnt;
     144             :         } else {
     145             :                 /* a BAT cannot grow larger than BUN_MAX */
     146             :                 maxsize = BUN_MAX;
     147             :         }
     148       93640 :         size = estimate == BUN_NONE ? lcnt < rcnt ? lcnt : rcnt : estimate;
     149             :         if (size < INCRSIZE)
     150             :                 size = INCRSIZE;
     151             :         if (size > maxsize)
     152             :                 size = maxsize;
     153       93640 :         if ((rkey | semi | only_misses) & nil_on_miss) {
     154             :                 /* see comment above: each entry left matches exactly
     155             :                  * once */
     156             :                 size = maxsize;
     157             :         }
     158       93640 :         if (min_one && size < lcnt)
     159             :                 size = lcnt;
     160             : 
     161       93640 :         if (maxsize == 0) {
     162       12732 :                 r1 = BATdense(0, 0, 0);
     163       12681 :                 if (r1 == NULL) {
     164             :                         return BUN_NONE;
     165             :                 }
     166       12681 :                 if (r2p) {
     167        1030 :                         r2 = BATdense(0, 0, 0);
     168        1034 :                         if (r2 == NULL) {
     169           0 :                                 BBPreclaim(r1);
     170           0 :                                 return BUN_NONE;
     171             :                         }
     172        1034 :                         *r2p = r2;
     173             :                 }
     174       12685 :                 *r1p = r1;
     175       12685 :                 return 0;
     176             :         }
     177             : 
     178       80908 :         r1 = COLnew(0, TYPE_oid, size, TRANSIENT);
     179       79594 :         if (r1 == NULL) {
     180             :                 return BUN_NONE;
     181             :         }
     182       79594 :         r1->tnil = false;
     183       79594 :         r1->tnonil = true;
     184       79594 :         r1->tkey = true;
     185       79594 :         r1->tsorted = true;
     186       79594 :         r1->trevsorted = true;
     187       79594 :         r1->tseqbase = 0;
     188       79594 :         r1->theap->dirty = true;
     189       79594 :         *r1p = r1;
     190       79594 :         if (r2p) {
     191       35867 :                 r2 = COLnew(0, TYPE_oid, size, TRANSIENT);
     192       36256 :                 if (r2 == NULL) {
     193           0 :                         BBPreclaim(r1);
     194           0 :                         return BUN_NONE;
     195             :                 }
     196       36256 :                 r2->tnil = false;
     197       36256 :                 r2->tnonil = true;
     198       36256 :                 r2->tkey = true;
     199       36256 :                 r2->tsorted = true;
     200       36256 :                 r2->trevsorted = true;
     201       36256 :                 r2->tseqbase = 0;
     202       36256 :                 r2->theap->dirty = true;
     203       36256 :                 *r2p = r2;
     204             :         }
     205             :         return maxsize;
     206             : }
     207             : 
     208             : #define VALUE(s, x)     (s##vars ?                                      \
     209             :                          s##vars + VarHeapVal(s##vals, (x), s##i.width) : \
     210             :                          s##vals ? (const char *) s##vals + ((x) * s##i.width) : \
     211             :                          (s##val = BUNtoid(s, (x)), (const char *) &s##val))
     212             : #define FVALUE(s, x)    ((const char *) s##vals + ((x) * s##i.width))
     213             : 
     214             : #define APPEND(b, o)            (((oid *) b->theap->base)[b->batCount++] = (o))
     215             : 
     216             : static inline gdk_return
     217   145103499 : maybeextend(BAT *restrict r1, BAT *restrict r2,
     218             :             BUN cnt, BUN lcur, BUN lcnt, BUN maxsize)
     219             : {
     220   145103499 :         if (BATcount(r1) + cnt > BATcapacity(r1)) {
     221             :                 /* make some extra space by extrapolating how much more
     222             :                  * we need (fraction of l we've seen so far is used to
     223             :                  * estimate a new size but with a shallow slope so that
     224             :                  * a skewed join doesn't overwhelm, whilst making sure
     225             :                  * there is somewhat significant progress) */
     226        2086 :                 BUN newcap = (BUN) (lcnt / (lcnt / 4.0 + lcur * .75) * (BATcount(r1) + cnt));
     227        2086 :                 newcap = (newcap + INCRSIZE - 1) & ~(((BUN) 1 << INCRSIZELOG) - 1);
     228        2086 :                 if (newcap < cnt + BATcount(r1))
     229           0 :                         newcap = cnt + BATcount(r1) + INCRSIZE;
     230             :                 /* if close to maxsize, then just use maxsize */
     231        2086 :                 if (newcap + INCRSIZE > maxsize)
     232             :                         newcap = maxsize;
     233             :                 /* make sure heap.free is set properly before
     234             :                  * extending */
     235        2086 :                 BATsetcount(r1, BATcount(r1));
     236        2091 :                 if (BATextend(r1, newcap) != GDK_SUCCEED)
     237             :                         return GDK_FAIL;
     238        2094 :                 if (r2) {
     239        1360 :                         BATsetcount(r2, BATcount(r2));
     240        1360 :                         if (BATextend(r2, newcap) != GDK_SUCCEED)
     241             :                                 return GDK_FAIL;
     242        1360 :                         assert(BATcapacity(r1) == BATcapacity(r2));
     243             :                 }
     244             :         }
     245             :         return GDK_SUCCEED;
     246             : }
     247             : 
     248             : /* Return BATs through r1p and r2p for the case that there is no
     249             :  * match between l and r, taking all flags into consideration.
     250             :  *
     251             :  * This means, if nil_on_miss is set or only_misses is set, *r1p is a
     252             :  * copy of the left candidate list or a dense list of all "head"
     253             :  * values of l, and *r2p (if r2p is not NULL) is all nil.  If neither
     254             :  * of those flags is set, the result is two empty BATs. */
     255             : static gdk_return
     256      619823 : nomatch(BAT **r1p, BAT **r2p, BAT *l, BAT *r, struct canditer *restrict lci,
     257             :         bool nil_on_miss, bool only_misses, const char *func, lng t0)
     258             : {
     259             :         BAT *r1, *r2 = NULL;
     260             : 
     261      619823 :         MT_thread_setalgorithm(__func__);
     262      620361 :         if (lci->ncand == 0 || !(nil_on_miss | only_misses)) {
     263             :                 /* return empty BATs */
     264      598620 :                 if ((r1 = BATdense(0, 0, 0)) == NULL)
     265             :                         return GDK_FAIL;
     266      597556 :                 if (r2p) {
     267      465139 :                         if ((r2 = BATdense(0, 0, 0)) == NULL) {
     268           0 :                                 BBPreclaim(r1);
     269           0 :                                 return GDK_FAIL;
     270             :                         }
     271      466565 :                         *r2p = r2;
     272             :                 }
     273             :         } else {
     274       21741 :                 r1 = canditer_slice(lci, 0, lci->ncand);
     275       21748 :                 if (r2p) {
     276           0 :                         if ((r2 = BATconstant(0, TYPE_void, &oid_nil, lci->ncand, TRANSIENT)) == NULL) {
     277           0 :                                 BBPreclaim(r1);
     278           0 :                                 return GDK_FAIL;
     279             :                         }
     280           0 :                         *r2p = r2;
     281             :                 }
     282             :         }
     283      620730 :         *r1p = r1;
     284      620730 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT ",r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT
     285             :                   ",nil_on_miss=%s,only_misses=%s"
     286             :                   " - > " ALGOBATFMT "," ALGOOPTBATFMT
     287             :                   " (%s -- " LLFMT "usec)\n",
     288             :                   ALGOBATPAR(l), ALGOBATPAR(r), ALGOOPTBATPAR(lci->s),
     289             :                   nil_on_miss ? "true" : "false",
     290             :                   only_misses ? "true" : "false",
     291             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
     292             :                   func, GDKusec() - t0);
     293             :         return GDK_SUCCEED;
     294             : }
     295             : 
     296             : /* Implementation of join where there is a single value (possibly
     297             :  * repeated multiple times) on the left.  This means we can use a
     298             :  * point select to find matches in the right column. */
     299             : static gdk_return
     300       66660 : selectjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
     301             :            struct canditer *lci, struct canditer *rci,
     302             :            bool nil_matches, lng t0, bool swapped, const char *reason)
     303             : {
     304       66660 :         BATiter li = bat_iterator(l);
     305             :         const void *v;
     306             :         BAT *bn = NULL;
     307             : 
     308       66688 :         assert(lci->ncand > 0);
     309       66688 :         assert(lci->ncand == 1 || (l->tsorted && l->trevsorted));
     310             : 
     311       66688 :         MT_thread_setalgorithm(__func__);
     312       66696 :         oid o = canditer_next(lci);
     313       66666 :         v = BUNtail(li, o - l->hseqbase);
     314             : 
     315      130711 :         if (!nil_matches &&
     316       64040 :             (*ATOMcompare(l->ttype))(v, ATOMnilptr(l->ttype)) == 0) {
     317             :                 /* NIL doesn't match anything */
     318          93 :                 bat_iterator_end(&li);
     319          93 :                 return nomatch(r1p, r2p, l, r, lci, false, false,
     320             :                                reason, t0);
     321             :         }
     322             : 
     323       66578 :         bn = BATselect(r, rci->s, v, NULL, true, true, false);
     324       66336 :         bat_iterator_end(&li);
     325       66548 :         if (bn == NULL) {
     326             :                 return GDK_FAIL;
     327             :         }
     328       66548 :         if (BATcount(bn) == 0) {
     329       15225 :                 BBPunfix(bn->batCacheid);
     330       15275 :                 return nomatch(r1p, r2p, l, r, lci, false, false,
     331             :                                reason, t0);
     332             :         }
     333       51323 :         BAT *r1 = COLnew(0, TYPE_oid, lci->ncand * BATcount(bn), TRANSIENT);
     334       51292 :         if (r1 == NULL) {
     335           0 :                 BBPunfix(bn->batCacheid);
     336           0 :                 return GDK_FAIL;
     337             :         }
     338       51292 :         r1->tsorted = true;
     339       51292 :         r1->trevsorted = lci->ncand == 1;
     340       51292 :         r1->tseqbase = BATcount(bn) == 1 && lci->tpe == cand_dense ? o : oid_nil;
     341       51292 :         r1->tkey = BATcount(bn) == 1;
     342       51292 :         r1->tnil = false;
     343       51292 :         r1->tnonil = true;
     344             :         BAT *r2 = NULL;
     345       51292 :         if (r2p) {
     346       47423 :                 r2 = COLnew(0, TYPE_oid, lci->ncand * BATcount(bn), TRANSIENT);
     347       47431 :                 if (r2 == NULL) {
     348           0 :                         BBPunfix(bn->batCacheid);
     349           0 :                         BBPreclaim(r1);
     350           0 :                         return GDK_FAIL;
     351             :                 }
     352       47431 :                 r2->tsorted = lci->ncand == 1 || BATcount(bn) == 1;
     353       47431 :                 r2->trevsorted = BATcount(bn) == 1;
     354       47431 :                 r2->tseqbase = lci->ncand == 1 && BATtdense(bn) ? bn->tseqbase : oid_nil;
     355       47431 :                 r2->tkey = lci->ncand == 1;
     356       47431 :                 r2->tnil = false;
     357       47431 :                 r2->tnonil = true;
     358             :         }
     359       51300 :         if (BATtdense(bn)) {
     360       51027 :                 oid *o1p = (oid *) Tloc(r1, 0);
     361       51027 :                 oid *o2p = r2 ? (oid *) Tloc(r2, 0) : NULL;
     362             :                 oid bno = bn->tseqbase;
     363       51027 :                 BUN p, q = BATcount(bn);
     364             : 
     365             :                 do {
     366      532042 :                         for (p = 0; p < q; p++) {
     367      364256 :                                 *o1p++ = o;
     368             :                         }
     369      167786 :                         if (o2p) {
     370      495106 :                                 for (p = 0; p < q; p++) {
     371      346054 :                                         *o2p++ = bno + p;
     372             :                                 }
     373             :                         }
     374      167786 :                         o = canditer_next(lci);
     375      167787 :                 } while (!is_oid_nil(o));
     376             :         } else {
     377         273 :                 oid *o1p = (oid *) Tloc(r1, 0);
     378         273 :                 oid *o2p = r2 ? (oid *) Tloc(r2, 0) : NULL;
     379         273 :                 const oid *bnp = (const oid *) Tloc(bn, 0);
     380         273 :                 BUN p, q = BATcount(bn);
     381             : 
     382             :                 do {
     383    27762058 :                         for (p = 0; p < q; p++) {
     384    27760089 :                                 *o1p++ = o;
     385             :                         }
     386        1969 :                         if (o2p) {
     387    27767142 :                                 for (p = 0; p < q; p++) {
     388    27765186 :                                         *o2p++ = bnp[p];
     389             :                                 }
     390             :                         }
     391        1969 :                         o = canditer_next(lci);
     392        1969 :                 } while (!is_oid_nil(o));
     393             :         }
     394       51301 :         BATsetcount(r1, lci->ncand * BATcount(bn));
     395       51334 :         *r1p = r1;
     396       51334 :         if (r2p) {
     397       47453 :                 BATsetcount(r2, lci->ncand * BATcount(bn));
     398       47454 :                 *r2p = r2;
     399             :         }
     400       51335 :         BBPunfix(bn->batCacheid);
     401       51336 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
     402             :                   "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
     403             :                   "sr=" ALGOOPTBATFMT ",nil_matches=%s;%s %s "
     404             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
     405             :                   ALGOBATPAR(l), ALGOBATPAR(r),
     406             :                   ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
     407             :                   nil_matches ? "true" : "false",
     408             :                   swapped ? " swapped" : "", reason,
     409             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
     410             :                   GDKusec() - t0);
     411             : 
     412             :         return GDK_SUCCEED;
     413             : }
     414             : 
     415             : #if SIZEOF_OID == SIZEOF_INT
     416             : #define binsearch_oid(indir, offset, vals, lo, hi, v, ordering, last) binsearch_int(indir, offset, (const int *) vals, lo, hi, (int) (v), ordering, last)
     417             : #endif
     418             : #if SIZEOF_OID == SIZEOF_LNG
     419             : #define binsearch_oid(indir, offset, vals, lo, hi, v, ordering, last) binsearch_lng(indir, offset, (const lng *) vals, lo, hi, (lng) (v), ordering, last)
     420             : #endif
     421             : 
     422             : /* Implementation of join where the right-hand side is dense, and if
     423             :  * there is a right candidate list, it too is dense.  In case
     424             :  * nil_on_miss is not set, we use a range select (BATselect) to find
     425             :  * the matching values in the left column and then calculate the
     426             :  * corresponding matches from the right.  If nil_on_miss is set, we
     427             :  * need to do some more work. */
     428             : static gdk_return
     429       27153 : mergejoin_void(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
     430             :                struct canditer *restrict lci, struct canditer *restrict rci,
     431             :                bool nil_on_miss, bool only_misses, lng t0, bool swapped,
     432             :                const char *reason)
     433             : {
     434             :         oid lo, hi;
     435             :         BUN i;
     436             :         oid o, *o1p = NULL, *o2p = NULL;
     437             :         BAT *r1 = NULL, *r2 = NULL;
     438             : 
     439             :         /* r is dense, and if there is a candidate list, it too is
     440             :          * dense.  This means we don't have to do any searches, we
     441             :          * only need to compare ranges to know whether a value from l
     442             :          * has a match in r */
     443       46541 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
     444       27153 :         assert(r->tsorted || r->trevsorted);
     445       27153 :         assert(BATcount(l) > 0);
     446       27153 :         assert(rci->tpe == cand_dense);
     447       27153 :         assert(BATcount(r) > 0);
     448             : 
     449       27153 :         MT_thread_setalgorithm(__func__);
     450             :         /* figure out range [lo..hi) of values in r that we need to match */
     451       27176 :         lo = r->tseqbase;
     452       27176 :         hi = lo + BATcount(r);
     453             :         /* restrict [lo..hi) range further using candidate list */
     454       27176 :         if (rci->seq > r->hseqbase)
     455           0 :                 lo += rci->seq - r->hseqbase;
     456       27176 :         if (rci->seq + rci->ncand < r->hseqbase + BATcount(r))
     457           0 :                 hi -= r->hseqbase + BATcount(r) - rci->seq - rci->ncand;
     458             : 
     459             :         /* at this point, the matchable values in r are [lo..hi) */
     460       27176 :         if (!nil_on_miss) {
     461       27176 :                 r1 = BATselect(l, lci->s, &lo, &hi, true, false, only_misses);
     462       27166 :                 if (r1 == NULL)
     463             :                         return GDK_FAIL;
     464       27166 :                 if (only_misses && !l->tnonil) {
     465             :                         /* also look for NILs */
     466           0 :                         r2 = BATselect(l, lci->s, &oid_nil, NULL, true, false, false);
     467           0 :                         if (r2 == NULL) {
     468           0 :                                 BBPreclaim(r1);
     469           0 :                                 return GDK_FAIL;
     470             :                         }
     471           0 :                         if (BATcount(r2) > 0) {
     472           0 :                                 BAT *mg = BATmergecand(r1, r2);
     473           0 :                                 BBPunfix(r1->batCacheid);
     474           0 :                                 BBPunfix(r2->batCacheid);
     475             :                                 r1 = mg;
     476           0 :                                 if (r1 == NULL)
     477             :                                         return GDK_FAIL;
     478             :                         } else {
     479           0 :                                 BBPunfix(r2->batCacheid);
     480             :                         }
     481             :                         r2 = NULL;
     482             :                 }
     483       27166 :                 *r1p = r1;
     484       27166 :                 if (r2p == NULL)
     485       25944 :                         goto doreturn2;
     486        1222 :                 if (BATcount(r1) == 0) {
     487          44 :                         r2 = BATdense(0, 0, 0);
     488          44 :                         if (r2 == NULL) {
     489           0 :                                 BBPreclaim(r1);
     490           0 :                                 return GDK_FAIL;
     491             :                         }
     492        1178 :                 } else if (BATtdense(r1) && BATtdense(l)) {
     493         132 :                         r2 = BATdense(0, l->tseqbase + r1->tseqbase - l->hseqbase + r->hseqbase - r->tseqbase, BATcount(r1));
     494         132 :                         if (r2 == NULL) {
     495           0 :                                 BBPreclaim(r1);
     496           0 :                                 return GDK_FAIL;
     497             :                         }
     498             :                 } else {
     499        1046 :                         r2 = COLnew(0, TYPE_oid, BATcount(r1), TRANSIENT);
     500        1053 :                         if (r2 == NULL) {
     501           0 :                                 BBPreclaim(r1);
     502           0 :                                 return GDK_FAIL;
     503             :                         }
     504        1053 :                         BATiter li = bat_iterator(l);
     505        1049 :                         const oid *lp = (const oid *) li.base;
     506        1049 :                         const oid *o1p = (const oid *) Tloc(r1, 0);
     507        1049 :                         oid *o2p = (oid *) Tloc(r2, 0);
     508        1049 :                         hi = BATcount(r1);
     509        1049 :                         if (complex_cand(l)) {
     510             :                                 /* this is actually generic code */
     511           0 :                                 for (o = 0; o < hi; o++)
     512           0 :                                         o2p[o] = BUNtoid(l, BUNtoid(r1, o) - l->hseqbase) - r->tseqbase + r->hseqbase;
     513        1049 :                         } else if (BATtdense(r1)) {
     514         447 :                                 lo = r1->tseqbase - l->hseqbase;
     515         447 :                                 if (r->tseqbase == r->hseqbase) {
     516         434 :                                         memcpy(o2p, lp + lo, hi * SIZEOF_OID);
     517             :                                 } else {
     518          13 :                                         hi += lo;
     519     5085027 :                                         for (o = 0; lo < hi; o++, lo++) {
     520     5085014 :                                                 o2p[o] = lp[lo] - r->tseqbase + r->hseqbase;
     521             :                                         }
     522             :                                 }
     523         602 :                         } else if (BATtdense(l)) {
     524           0 :                                 for (o = 0; o < hi; o++) {
     525           0 :                                         o2p[o] = o1p[o] - l->hseqbase + l->tseqbase - r->tseqbase + r->hseqbase;
     526             :                                 }
     527             :                         } else {
     528    54612610 :                                 for (o = 0; o < hi; o++) {
     529    54612008 :                                         o2p[o] = lp[o1p[o] - l->hseqbase] - r->tseqbase + r->hseqbase;
     530             :                                 }
     531             :                         }
     532        1049 :                         bat_iterator_end(&li);
     533        1055 :                         r2->tkey = l->tkey;
     534        1055 :                         r2->tsorted = l->tsorted;
     535        1055 :                         r2->trevsorted = l->trevsorted;
     536        1055 :                         r2->tnil = false;
     537        1055 :                         r2->tnonil = true;
     538        1055 :                         BATsetcount(r2, BATcount(r1));
     539             :                 }
     540        1232 :                 *r2p = r2;
     541        1232 :                 goto doreturn2;
     542             :         }
     543             :         /* nil_on_miss is set, this means we must have a second output */
     544           0 :         assert(r2p);
     545           0 :         if (BATtdense(l)) {
     546             :                 /* if l is dense, we can further restrict the [lo..hi)
     547             :                  * range to values in l that match with values in r */
     548           0 :                 o = lo;
     549           0 :                 i = lci->seq - l->hseqbase;
     550           0 :                 if (l->tseqbase + i > lo)
     551           0 :                         lo = l->tseqbase + i;
     552           0 :                 i = canditer_last(lci) + 1 - l->hseqbase;
     553           0 :                 if (l->tseqbase + i < hi)
     554           0 :                         hi = l->tseqbase + i;
     555           0 :                 if (lci->tpe == cand_dense) {
     556             :                         /* l is dense, and so is the left candidate
     557             :                          * list (if it exists); this means we don't
     558             :                          * have to actually look at any values in l:
     559             :                          * we can just do some arithmetic; it also
     560             :                          * means that r1 will be dense, and if
     561             :                          * nil_on_miss is not set, or if all values in
     562             :                          * l match, r2 will too */
     563           0 :                         if (hi <= lo) {
     564           0 :                                 return nomatch(r1p, r2p, l, r, lci,
     565             :                                                nil_on_miss, only_misses,
     566             :                                                "mergejoin_void", t0);
     567             :                         }
     568             : 
     569             :                         /* at this point, the matched values in l and
     570             :                          * r (taking candidate lists into account) are
     571             :                          * [lo..hi) which we can translate back to the
     572             :                          * respective OID values that we can store in
     573             :                          * r1 and r2; note that r1 will be dense since
     574             :                          * all values in l will match something (even
     575             :                          * if nil since nil_on_miss is set) */
     576           0 :                         *r1p = r1 = BATdense(0, lci->seq, lci->ncand);
     577           0 :                         if (r1 == NULL)
     578             :                                 return GDK_FAIL;
     579           0 :                         if (hi - lo < lci->ncand) {
     580             :                                 /* we need to fill in nils in r2 for
     581             :                                  * missing values */
     582           0 :                                 *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
     583           0 :                                 if (r2 == NULL) {
     584           0 :                                         BBPreclaim(*r1p);
     585           0 :                                         return GDK_FAIL;
     586             :                                 }
     587           0 :                                 o2p = (oid *) Tloc(r2, 0);
     588           0 :                                 i = l->tseqbase + lci->seq - l->hseqbase;
     589           0 :                                 lo -= i;
     590           0 :                                 hi -= i;
     591           0 :                                 i += r->hseqbase - r->tseqbase;
     592           0 :                                 for (o = 0; o < lo; o++)
     593           0 :                                         *o2p++ = oid_nil;
     594           0 :                                 for (o = lo; o < hi; o++)
     595           0 :                                         *o2p++ = o + i;
     596           0 :                                 for (o = hi; o < lci->ncand; o++)
     597           0 :                                         *o2p++ = oid_nil;
     598           0 :                                 r2->tnonil = false;
     599           0 :                                 r2->tnil = true;
     600             :                                 /* sorted of no nils at end */
     601           0 :                                 r2->tsorted = hi == lci->ncand;
     602             :                                 /* reverse sorted if single non-nil at start */
     603           0 :                                 r2->trevsorted = lo == 0 && hi == 1;
     604           0 :                                 r2->tseqbase = oid_nil;
     605             :                                 /* (hi - lo) different OIDs in r2,
     606             :                                  * plus one for nil */
     607           0 :                                 r2->tkey = hi - lo + 1 == lci->ncand;
     608           0 :                                 BATsetcount(r2, lci->ncand);
     609             :                         } else {
     610             :                                 /* no missing values */
     611           0 :                                 *r2p = r2 = BATdense(0, r->hseqbase + lo - r->tseqbase, lci->ncand);
     612           0 :                                 if (r2 == NULL) {
     613           0 :                                         BBPreclaim(*r1p);
     614           0 :                                         return GDK_FAIL;
     615             :                                 }
     616             :                         }
     617           0 :                         goto doreturn;
     618             :                 }
     619             :                 /* l is dense, but the candidate list exists and is
     620             :                  * not dense; we can, by manipulating the range
     621             :                  * [lo..hi), just look at the candidate list values */
     622             : 
     623             :                 /* translate lo and hi to l's OID values that now need
     624             :                  * to match */
     625           0 :                 lo = lo - l->tseqbase + l->hseqbase;
     626           0 :                 hi = hi - l->tseqbase + l->hseqbase;
     627             : 
     628           0 :                 *r1p = r1 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
     629           0 :                 *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
     630           0 :                 if (r1 == NULL || r2 == NULL) {
     631           0 :                         BBPreclaim(r1);
     632           0 :                         BBPreclaim(r2);
     633           0 :                         return GDK_FAIL;
     634             :                 }
     635           0 :                 o1p = (oid *) Tloc(r1, 0);
     636           0 :                 o2p = (oid *) Tloc(r2, 0);
     637           0 :                 r2->tnil = false;
     638           0 :                 r2->tnonil = true;
     639           0 :                 r2->tkey = true;
     640           0 :                 r2->tsorted = true;
     641           0 :                 o = canditer_next(lci);
     642           0 :                 for (i = 0; i < lci->ncand && o < lo; i++) {
     643           0 :                         *o1p++ = o;
     644           0 :                         *o2p++ = oid_nil;
     645           0 :                         o = canditer_next(lci);
     646             :                 }
     647           0 :                 if (i > 0) {
     648           0 :                         r2->tnil = true;
     649           0 :                         r2->tnonil = false;
     650           0 :                         r2->tkey = i == 1;
     651             :                 }
     652           0 :                 for (; i < lci->ncand && o < hi; i++) {
     653           0 :                         *o1p++ = o;
     654           0 :                         *o2p++ = o - l->hseqbase + l->tseqbase - r->tseqbase + r->hseqbase;
     655           0 :                         o = canditer_next(lci);
     656             :                 }
     657           0 :                 if (i < lci->ncand) {
     658           0 :                         r2->tkey = !r2->tnil && lci->ncand - i == 1;
     659           0 :                         r2->tnil = true;
     660           0 :                         r2->tnonil = false;
     661           0 :                         r2->tsorted = false;
     662           0 :                         for (; i < lci->ncand; i++) {
     663           0 :                                 *o1p++ = o;
     664           0 :                                 *o2p++ = oid_nil;
     665           0 :                                 o = canditer_next(lci);
     666             :                         }
     667             :                 }
     668           0 :                 BATsetcount(r1, lci->ncand);
     669           0 :                 r1->tseqbase = BATcount(r1) == 1 ? *(oid*)Tloc(r1, 0) : oid_nil;
     670           0 :                 r1->tsorted = true;
     671           0 :                 r1->trevsorted = BATcount(r1) <= 1;
     672           0 :                 r1->tnil = false;
     673           0 :                 r1->tnonil = true;
     674           0 :                 r1->tkey = true;
     675           0 :                 BATsetcount(r2, BATcount(r1));
     676           0 :                 r2->tseqbase = r2->tnil || BATcount(r2) > 1 ? oid_nil : BATcount(r2) == 1 ? *(oid*)Tloc(r2, 0) : 0;
     677           0 :                 r2->trevsorted = BATcount(r2) <= 1;
     678           0 :                 goto doreturn;
     679             :         }
     680             :         /* l is not dense, so we need to look at the values and check
     681             :          * whether they are in the range [lo..hi) */
     682             : 
     683             :         /* do indirection through the candidate list to look at the
     684             :          * value */
     685             : 
     686           0 :         *r1p = r1 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
     687           0 :         *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
     688           0 :         if (r1 == NULL || r2 == NULL) {
     689           0 :                 BBPreclaim(r1);
     690           0 :                 BBPreclaim(r2);
     691           0 :                 return GDK_FAIL;
     692             :         }
     693           0 :         o1p = (oid *) Tloc(r1, 0);
     694           0 :         o2p = (oid *) Tloc(r2, 0);
     695           0 :         r2->tnil = false;
     696           0 :         r2->tnonil = true;
     697           0 :         if (complex_cand(l)) {
     698           0 :                 for (i = 0; i < lci->ncand; i++) {
     699           0 :                         oid c = canditer_next(lci);
     700             : 
     701           0 :                         o = BUNtoid(l, c - l->hseqbase);
     702           0 :                         *o1p++ = c;
     703           0 :                         if (o >= lo && o < hi) {
     704           0 :                                 *o2p++ = o - r->tseqbase + r->hseqbase;
     705             :                         } else {
     706           0 :                                 *o2p++ = oid_nil;
     707           0 :                                 r2->tnil = true;
     708           0 :                                 r2->tnonil = false;
     709             :                         }
     710             :                 }
     711             :         } else {
     712           0 :                 BATiter li = bat_iterator(l);
     713           0 :                 const oid *lvals = (const oid *) li.base;
     714           0 :                 for (i = 0; i < lci->ncand; i++) {
     715           0 :                         oid c = canditer_next(lci);
     716             : 
     717           0 :                         o = lvals[c - l->hseqbase];
     718           0 :                         *o1p++ = c;
     719           0 :                         if (o >= lo && o < hi) {
     720           0 :                                 *o2p++ = o - r->tseqbase + r->hseqbase;
     721             :                         } else {
     722           0 :                                 *o2p++ = oid_nil;
     723           0 :                                 r2->tnil = true;
     724           0 :                                 r2->tnonil = false;
     725             :                         }
     726             :                 }
     727           0 :                 bat_iterator_end(&li);
     728             :         }
     729           0 :         r1->tsorted = true;
     730           0 :         r1->trevsorted = BATcount(r1) <= 1;
     731           0 :         r1->tkey = true;
     732           0 :         r1->tseqbase = oid_nil;
     733           0 :         r1->tnil = false;
     734           0 :         r1->tnonil = true;
     735           0 :         BATsetcount(r1, lci->ncand);
     736           0 :         BATsetcount(r2, lci->ncand);
     737           0 :         r2->tsorted = l->tsorted || BATcount(r2) <= 1;
     738           0 :         r2->trevsorted = l->trevsorted || BATcount(r2) <= 1;
     739           0 :         r2->tkey = l->tkey || BATcount(r2) <= 1;
     740           0 :         r2->tseqbase = oid_nil;
     741             : 
     742           0 :   doreturn:
     743           0 :         if (r1->tkey)
     744           0 :                 virtualize(r1);
     745           0 :         if (r2->tkey && r2->tsorted)
     746           0 :                 virtualize(r2);
     747           0 :   doreturn2:
     748       27176 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
     749             :                   "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
     750             :                   "sr=" ALGOOPTBATFMT ","
     751             :                   "nil_on_miss=%s,only_misses=%s;%s %s "
     752             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
     753             :                   ALGOBATPAR(l), ALGOBATPAR(r),
     754             :                   ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
     755             :                   nil_on_miss ? "true" : "false",
     756             :                   only_misses ? "true" : "false",
     757             :                   swapped ? " swapped" : "", reason,
     758             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
     759             :                   GDKusec() - t0);
     760             : 
     761             :         return GDK_SUCCEED;
     762             : }
     763             : 
     764             : /* Implementation of mergejoin (see below) for the special case that
     765             :  * the values are of type int, and some more conditions are met. */
     766             : static gdk_return
     767        8747 : mergejoin_int(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
     768             :               bool nil_matches, BUN estimate, lng t0, bool swapped,
     769             :               const char *reason)
     770             : {
     771             :         BAT *r1, *r2;
     772             :         BUN lstart, lend, lcnt;
     773             :         BUN rstart, rend;
     774             :         BUN lscan, rscan;       /* opportunistic scan window */
     775             :         BUN maxsize;
     776             :         const int *lvals, *rvals;
     777             :         int v;
     778             :         BUN nl, nr;
     779             :         oid lv;
     780             :         BUN i;
     781        8747 :         BATiter li = bat_iterator(l);
     782        8876 :         BATiter ri = bat_iterator(r);
     783             : 
     784       26645 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
     785        8879 :         assert(r->tsorted || r->trevsorted);
     786             : 
     787        8879 :         MT_thread_setalgorithm(__func__);
     788             :         lstart = rstart = 0;
     789        8885 :         lend = BATcount(l);
     790             :         lcnt = lend - lstart;
     791        8885 :         rend = BATcount(r);
     792        8885 :         lvals = (const int *) li.base;
     793        8885 :         rvals = (const int *) ri.base;
     794        8885 :         assert(!r->tvarsized || !r->ttype);
     795             : 
     796             :         /* basic properties will be adjusted if necessary later on,
     797             :          * they were initially set by joininitresults() */
     798             : 
     799        8885 :         if (lend == 0 || rend == 0) {
     800             :                 /* there are no matches */
     801           0 :                 bat_iterator_end(&li);
     802           0 :                 bat_iterator_end(&ri);
     803           0 :                 return nomatch(r1p, r2p, l, r,
     804           0 :                                &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
     805             :                                false, false, __func__, t0);
     806             :         }
     807             : 
     808        8748 :         if ((maxsize = joininitresults(r1p, r2p, BATcount(l), BATcount(r),
     809        8885 :                                        l->tkey, r->tkey, false, false,
     810             :                                        false, false, estimate)) == BUN_NONE) {
     811           0 :                 bat_iterator_end(&li);
     812           0 :                 bat_iterator_end(&ri);
     813           0 :                 return GDK_FAIL;
     814             :         }
     815        8748 :         r1 = *r1p;
     816        8748 :         r2 = r2p ? *r2p : NULL;
     817             : 
     818             :         /* determine opportunistic scan window for l and r */
     819       53434 :         for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
     820       44686 :                 nl >>= 1;
     821       67458 :         for (nr = rend - rstart, rscan = 4; nr > 0; rscan++)
     822       58710 :                 nr >>= 1;
     823             : 
     824        8748 :         if (!nil_matches) {
     825             :                 /* skip over nils at the start of the columns */
     826        5762 :                 if (lscan < lend - lstart && is_int_nil(lvals[lstart + lscan])) {
     827           0 :                         lstart = binsearch_int(NULL, 0, lvals, lstart + lscan,
     828             :                                                lend - 1, int_nil, 1, 1);
     829             :                 } else {
     830        5763 :                         while (is_int_nil(lvals[lstart]))
     831           1 :                                 lstart++;
     832             :                 }
     833        5762 :                 if (rscan < rend - rstart && is_int_nil(rvals[rstart + rscan])) {
     834           0 :                         rstart = binsearch_int(NULL, 0, rvals, rstart + rscan,
     835             :                                                rend - 1, int_nil, 1, 1);
     836             :                 } else {
     837        5762 :                         while (is_int_nil(rvals[rstart]))
     838           0 :                                 rstart++;
     839             :                 }
     840             :         }
     841             :         /* from here on we don't have to worry about nil values */
     842             : 
     843      471144 :         while (lstart < lend && rstart < rend) {
     844      464759 :                 v = rvals[rstart];
     845             : 
     846      464759 :                 if (lscan < lend - lstart && lvals[lstart + lscan] < v) {
     847       13660 :                         lstart = binsearch_int(NULL, 0, lvals, lstart + lscan,
     848             :                                                lend - 1, v, 1, 0);
     849             :                 } else {
     850             :                         /* scan l for v */
     851      567486 :                         while (lstart < lend && lvals[lstart] < v)
     852      116387 :                                 lstart++;
     853             :                 }
     854      467635 :                 if (lstart >= lend) {
     855             :                         /* nothing found */
     856             :                         break;
     857             :                 }
     858             : 
     859             :                 /* Here we determine the next value in l that we are
     860             :                  * going to try to match in r.  We will also count the
     861             :                  * number of occurrences in l of that value.
     862             :                  * Afterwards, v points to the value and nl is the
     863             :                  * number of times it occurs.  Also, lstart will
     864             :                  * point to the next value to be considered (ready for
     865             :                  * the next iteration).
     866             :                  * If there are many equal values in l (more than
     867             :                  * lscan), we will use binary search to find the end
     868             :                  * of the sequence.  Obviously, we can do this only if
     869             :                  * l is actually sorted (lscan > 0). */
     870             :                 nl = 1;         /* we'll match (at least) one in l */
     871             :                 nr = 0;         /* maybe we won't match anything in r */
     872      466512 :                 v = lvals[lstart];
     873      466512 :                 if (l->tkey) {
     874             :                         /* if l is key, there is a single value */
     875       88590 :                         lstart++;
     876      377922 :                 } else if (lscan < lend - lstart &&
     877      370638 :                            v == lvals[lstart + lscan]) {
     878             :                         /* lots of equal values: use binary search to
     879             :                          * find end */
     880       22890 :                         nl = binsearch_int(NULL, 0, lvals, lstart + lscan,
     881             :                                            lend - 1, v, 1, 1);
     882       22897 :                         nl -= lstart;
     883       22897 :                         lstart += nl;
     884             :                 } else {
     885             :                         /* just scan */
     886     1576318 :                         while (++lstart < lend && v == lvals[lstart])
     887     1221286 :                                 nl++;
     888             :                 }
     889             :                 /* lstart points one beyond the value we're
     890             :                  * going to match: ready for the next iteration. */
     891             : 
     892             :                 /* First we find the first value in r that is at
     893             :                  * least as large as v, then we find the first
     894             :                  * value in r that is larger than v.  The difference
     895             :                  * is the number of values equal to v and is stored in
     896             :                  * nr.
     897             :                  * We will use binary search on r to find both ends of
     898             :                  * the sequence of values that are equal to v in case
     899             :                  * the position is "too far" (more than rscan
     900             :                  * away). */
     901             : 
     902             :                 /* first find the location of the first value in r
     903             :                  * that is >= v, then find the location of the first
     904             :                  * value in r that is > v; the difference is the
     905             :                  * number of values equal to v */
     906             : 
     907             :                 /* look ahead a little (rscan) in r to see whether
     908             :                  * we're better off doing a binary search */
     909      466519 :                 if (rscan < rend - rstart && rvals[rstart + rscan] < v) {
     910             :                         /* value too far away in r: use binary
     911             :                          * search */
     912       18975 :                         rstart = binsearch_int(NULL, 0, rvals, rstart + rscan,
     913             :                                                rend - 1, v, 1, 0);
     914             :                 } else {
     915             :                         /* scan r for v */
     916      482026 :                         while (rstart < rend && rvals[rstart] < v)
     917       34482 :                                 rstart++;
     918             :                 }
     919      471145 :                 if (rstart == rend) {
     920             :                         /* nothing found */
     921             :                         break;
     922             :                 }
     923             : 
     924             :                 /* now find the end of the sequence of equal values v */
     925             : 
     926             :                 /* if r is key, there is zero or one match, otherwise
     927             :                  * look ahead a little (rscan) in r to see whether
     928             :                  * we're better off doing a binary search */
     929      469833 :                 if (r->tkey) {
     930      236962 :                         if (rstart < rend && v == rvals[rstart]) {
     931             :                                 nr = 1;
     932      235779 :                                 rstart++;
     933             :                         }
     934      232871 :                 } else if (rscan < rend - rstart &&
     935      231020 :                            v == rvals[rstart + rscan]) {
     936             :                         /* range too large: use binary search */
     937       71781 :                         nr = binsearch_int(NULL, 0, rvals, rstart + rscan,
     938             :                                            rend - 1, v, 1, 1);
     939       72036 :                         nr -= rstart;
     940       72036 :                         rstart += nr;
     941             :                 } else {
     942             :                         /* scan r for end of range */
     943     1380246 :                         while (rstart < rend && v == rvals[rstart]) {
     944     1219156 :                                 nr++;
     945     1219156 :                                 rstart++;
     946             :                         }
     947             :                 }
     948             :                 /* rstart points to first value > v or end of
     949             :                  * r, and nr is the number of values in r that
     950             :                  * are equal to v */
     951      233126 :                 if (nr == 0) {
     952             :                         /* no entries in r found */
     953           0 :                         continue;
     954             :                 }
     955             :                 /* make space: nl values in l match nr values in r, so
     956             :                  * we need to add nl * nr values in the results */
     957      472492 :                 if (maybeextend(r1, r2, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
     958           0 :                         goto bailout;
     959             : 
     960             :                 /* maintain properties */
     961      464800 :                 if (nl > 1) {
     962             :                         /* value occurs multiple times in l, so entry
     963             :                          * in r will be repeated multiple times: hence
     964             :                          * r2 is not key and not dense */
     965      310788 :                         if (r2) {
     966      145148 :                                 r2->tkey = false;
     967      145148 :                                 r2->tseqbase = oid_nil;
     968             :                         }
     969             :                         /* multiple different values will be inserted
     970             :                          * in r1 (always in order), so not reverse
     971             :                          * ordered anymore */
     972      310788 :                         r1->trevsorted = false;
     973             :                 }
     974      464800 :                 if (nr > 1) {
     975             :                         /* value occurs multiple times in r, so entry
     976             :                          * in l will be repeated multiple times: hence
     977             :                          * r1 is not key and not dense */
     978      195249 :                         r1->tkey = false;
     979      195249 :                         r1->tseqbase = oid_nil;
     980             :                         /* multiple different values will be inserted
     981             :                          * in r2 (in order), so not reverse ordered
     982             :                          * anymore */
     983      195249 :                         if (r2) {
     984      123120 :                                 r2->trevsorted = false;
     985      123120 :                                 if (nl > 1) {
     986             :                                         /* multiple values in l match
     987             :                                          * multiple values in r, so an
     988             :                                          * ordered sequence will be
     989             :                                          * inserted multiple times in
     990             :                                          * r2, so r2 is not ordered
     991             :                                          * anymore */
     992       87053 :                                         r2->tsorted = false;
     993             :                                 }
     994             :                         }
     995             :                 }
     996      464800 :                 if (BATcount(r1) > 0) {
     997             :                         /* a new, higher value will be inserted into
     998             :                          * r1, so r1 is not reverse ordered anymore */
     999      457101 :                         r1->trevsorted = false;
    1000             :                         /* a new higher value will be added to r2 */
    1001      457101 :                         if (r2) {
    1002      233728 :                                 r2->trevsorted = false;
    1003             :                         }
    1004      457101 :                         if (BATtdense(r1) &&
    1005      258783 :                             ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
    1006          62 :                                 r1->tseqbase = oid_nil;
    1007             :                         }
    1008             :                 }
    1009             : 
    1010      464800 :                 if (r2 &&
    1011      239386 :                     BATcount(r2) > 0 &&
    1012      233607 :                     BATtdense(r2) &&
    1013       80600 :                     ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rstart - nr) {
    1014         183 :                         r2->tseqbase = oid_nil;
    1015             :                 }
    1016             : 
    1017             :                 /* insert values */
    1018      464800 :                 lv = l->hseqbase + lstart - nl;
    1019    16026289 :                 for (i = 0; i < nl; i++) {
    1020             :                         BUN j;
    1021             : 
    1022   118659953 :                         for (j = 0; j < nr; j++) {
    1023   103098464 :                                 APPEND(r1, lv);
    1024             :                         }
    1025    15561489 :                         if (r2) {
    1026    15016269 :                                 oid rv = r->hseqbase + rstart - nr;
    1027             : 
    1028   110786300 :                                 for (j = 0; j < nr; j++) {
    1029    95770031 :                                         APPEND(r2, rv);
    1030    95770031 :                                         rv++;
    1031             :                                 }
    1032             :                         }
    1033    15561489 :                         lv++;
    1034             :                 }
    1035             :         }
    1036             :         /* also set other bits of heap to correct value to indicate size */
    1037        8820 :         BATsetcount(r1, BATcount(r1));
    1038        8775 :         if (r2) {
    1039        6415 :                 BATsetcount(r2, BATcount(r2));
    1040        6415 :                 assert(BATcount(r1) == BATcount(r2));
    1041             :         }
    1042        8775 :         if (BATcount(r1) > 0) {
    1043        6772 :                 if (BATtdense(r1))
    1044        5475 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    1045        6772 :                 if (r2 && BATtdense(r2))
    1046        3779 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    1047             :         } else {
    1048        2003 :                 r1->tseqbase = 0;
    1049        2003 :                 if (r2) {
    1050        1552 :                         r2->tseqbase = 0;
    1051             :                 }
    1052             :         }
    1053        8775 :         bat_iterator_end(&li);
    1054        8864 :         bat_iterator_end(&ri);
    1055        8845 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
    1056             :                   "nil_matches=%s;%s %s "
    1057             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
    1058             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    1059             :                   nil_matches ? "true" : "false",
    1060             :                   swapped ? " swapped" : "", reason,
    1061             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    1062             :                   GDKusec() - t0);
    1063             : 
    1064             :         return GDK_SUCCEED;
    1065             : 
    1066             :   bailout:
    1067           0 :         bat_iterator_end(&li);
    1068           0 :         bat_iterator_end(&ri);
    1069           0 :         BBPreclaim(r1);
    1070           0 :         BBPreclaim(r2);
    1071           0 :         return GDK_FAIL;
    1072             : }
    1073             : 
    1074             : /* Implementation of mergejoin (see below) for the special case that
    1075             :  * the values are of type lng, and some more conditions are met. */
    1076             : static gdk_return
    1077         207 : mergejoin_lng(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
    1078             :               bool nil_matches, BUN estimate, lng t0, bool swapped,
    1079             :               const char *reason)
    1080             : {
    1081             :         BAT *r1, *r2;
    1082             :         BUN lstart, lend, lcnt;
    1083             :         BUN rstart, rend;
    1084             :         BUN lscan, rscan;       /* opportunistic scan window */
    1085             :         BUN maxsize;
    1086             :         const lng *lvals, *rvals;
    1087             :         lng v;
    1088             :         BUN nl, nr;
    1089             :         oid lv;
    1090             :         BUN i;
    1091         207 :         BATiter li = bat_iterator(l);
    1092         212 :         BATiter ri = bat_iterator(r);
    1093             : 
    1094         636 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    1095         212 :         assert(r->tsorted || r->trevsorted);
    1096             : 
    1097         212 :         MT_thread_setalgorithm(__func__);
    1098             :         lstart = rstart = 0;
    1099         212 :         lend = BATcount(l);
    1100             :         lcnt = lend - lstart;
    1101         212 :         rend = BATcount(r);
    1102         212 :         lvals = (const lng *) li.base;
    1103         212 :         rvals = (const lng *) ri.base;
    1104         212 :         assert(!r->tvarsized || !r->ttype);
    1105             : 
    1106             :         /* basic properties will be adjusted if necessary later on,
    1107             :          * they were initially set by joininitresults() */
    1108             : 
    1109         212 :         if (lend == 0 || rend == 0) {
    1110             :                 /* there are no matches */
    1111           0 :                 bat_iterator_end(&li);
    1112           0 :                 bat_iterator_end(&ri);
    1113           0 :                 return nomatch(r1p, r2p, l, r,
    1114           0 :                                &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
    1115             :                                false, false, __func__, t0);
    1116             :         }
    1117             : 
    1118         211 :         if ((maxsize = joininitresults(r1p, r2p, BATcount(l), BATcount(r),
    1119         212 :                                        l->tkey, r->tkey, false, false,
    1120             :                                        false, false, estimate)) == BUN_NONE) {
    1121           0 :                 bat_iterator_end(&li);
    1122           0 :                 bat_iterator_end(&ri);
    1123           0 :                 return GDK_FAIL;
    1124             :         }
    1125         211 :         r1 = *r1p;
    1126         211 :         r2 = r2p ? *r2p : NULL;
    1127             : 
    1128             :         /* determine opportunistic scan window for l and r */
    1129        1607 :         for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
    1130        1396 :                 nl >>= 1;
    1131        1576 :         for (nr = rend - rstart, rscan = 4; nr > 0; rscan++)
    1132        1365 :                 nr >>= 1;
    1133             : 
    1134         211 :         if (!nil_matches) {
    1135             :                 /* skip over nils at the start of the columns */
    1136         136 :                 if (lscan < lend - lstart && is_lng_nil(lvals[lstart + lscan])) {
    1137           0 :                         lstart = binsearch_lng(NULL, 0, lvals, lstart + lscan,
    1138             :                                                lend - 1, lng_nil, 1, 1);
    1139             :                 } else {
    1140         136 :                         while (is_lng_nil(lvals[lstart]))
    1141           0 :                                 lstart++;
    1142             :                 }
    1143         136 :                 if (rscan < rend - rstart && is_lng_nil(rvals[rstart + rscan])) {
    1144           0 :                         rstart = binsearch_lng(NULL, 0, rvals, rstart + rscan,
    1145             :                                                rend - 1, lng_nil, 1, 1);
    1146             :                 } else {
    1147         136 :                         while (is_lng_nil(rvals[rstart]))
    1148           0 :                                 rstart++;
    1149             :                 }
    1150             :         }
    1151             :         /* from here on we don't have to worry about nil values */
    1152             : 
    1153      396465 :         while (lstart < lend && rstart < rend) {
    1154      396319 :                 v = rvals[rstart];
    1155             : 
    1156      396319 :                 if (lscan < lend - lstart && lvals[lstart + lscan] < v) {
    1157        1687 :                         lstart = binsearch_lng(NULL, 0, lvals, lstart + lscan,
    1158             :                                                lend - 1, v, 1, 0);
    1159             :                 } else {
    1160             :                         /* scan l for v */
    1161      486642 :                         while (lstart < lend && lvals[lstart] < v)
    1162       92010 :                                 lstart++;
    1163             :                 }
    1164      396929 :                 if (lstart >= lend) {
    1165             :                         /* nothing found */
    1166             :                         break;
    1167             :                 }
    1168             : 
    1169             :                 /* Here we determine the next value in l that we are
    1170             :                  * going to try to match in r.  We will also count the
    1171             :                  * number of occurrences in l of that value.
    1172             :                  * Afterwards, v points to the value and nl is the
    1173             :                  * number of times it occurs.  Also, lstart will
    1174             :                  * point to the next value to be considered (ready for
    1175             :                  * the next iteration).
    1176             :                  * If there are many equal values in l (more than
    1177             :                  * lscan), we will use binary search to find the end
    1178             :                  * of the sequence.  Obviously, we can do this only if
    1179             :                  * l is actually sorted (lscan > 0). */
    1180             :                 nl = 1;         /* we'll match (at least) one in l */
    1181             :                 nr = 0;         /* maybe we won't match anything in r */
    1182      396886 :                 v = lvals[lstart];
    1183      396886 :                 if (l->tkey) {
    1184             :                         /* if l is key, there is a single value */
    1185      350057 :                         lstart++;
    1186       46829 :                 } else if (lscan < lend - lstart &&
    1187       46713 :                            v == lvals[lstart + lscan]) {
    1188             :                         /* lots of equal values: use binary search to
    1189             :                          * find end */
    1190         395 :                         nl = binsearch_lng(NULL, 0, lvals, lstart + lscan,
    1191             :                                            lend - 1, v, 1, 1);
    1192         395 :                         nl -= lstart;
    1193         395 :                         lstart += nl;
    1194             :                 } else {
    1195             :                         /* just scan */
    1196       78608 :                         while (++lstart < lend && v == lvals[lstart])
    1197       32174 :                                 nl++;
    1198             :                 }
    1199             :                 /* lstart points one beyond the value we're
    1200             :                  * going to match: ready for the next iteration. */
    1201             : 
    1202             :                 /* First we find the first value in r that is at
    1203             :                  * least as large as v, then we find the first
    1204             :                  * value in r that is larger than v.  The difference
    1205             :                  * is the number of values equal to v and is stored in
    1206             :                  * nr.
    1207             :                  * We will use binary search on r to find both ends of
    1208             :                  * the sequence of values that are equal to v in case
    1209             :                  * the position is "too far" (more than rscan
    1210             :                  * away). */
    1211             : 
    1212             :                 /* first find the location of the first value in r
    1213             :                  * that is >= v, then find the location of the first
    1214             :                  * value in r that is > v; the difference is the
    1215             :                  * number of values equal to v */
    1216             : 
    1217             :                 /* look ahead a little (rscan) in r to see whether
    1218             :                  * we're better off doing a binary search */
    1219      396886 :                 if (rscan < rend - rstart && rvals[rstart + rscan] < v) {
    1220             :                         /* value too far away in r: use binary
    1221             :                          * search */
    1222        1469 :                         rstart = binsearch_lng(NULL, 0, rvals, rstart + rscan,
    1223             :                                                rend - 1, v, 1, 0);
    1224             :                 } else {
    1225             :                         /* scan r for v */
    1226     1454919 :                         while (rstart < rend && rvals[rstart] < v)
    1227     1059502 :                                 rstart++;
    1228             :                 }
    1229      396866 :                 if (rstart == rend) {
    1230             :                         /* nothing found */
    1231             :                         break;
    1232             :                 }
    1233             : 
    1234             :                 /* now find the end of the sequence of equal values v */
    1235             : 
    1236             :                 /* if r is key, there is zero or one match, otherwise
    1237             :                  * look ahead a little (rscan) in r to see whether
    1238             :                  * we're better off doing a binary search */
    1239      396843 :                 if (r->tkey) {
    1240      362766 :                         if (rstart < rend && v == rvals[rstart]) {
    1241             :                                 nr = 1;
    1242       69060 :                                 rstart++;
    1243             :                         }
    1244       34077 :                 } else if (rscan < rend - rstart &&
    1245       34032 :                            v == rvals[rstart + rscan]) {
    1246             :                         /* range too large: use binary search */
    1247           0 :                         nr = binsearch_lng(NULL, 0, rvals, rstart + rscan,
    1248             :                                            rend - 1, v, 1, 1);
    1249           0 :                         nr -= rstart;
    1250           0 :                         rstart += nr;
    1251             :                 } else {
    1252             :                         /* scan r for end of range */
    1253       72844 :                         while (rstart < rend && v == rvals[rstart]) {
    1254       38767 :                                 nr++;
    1255       38767 :                                 rstart++;
    1256             :                         }
    1257             :                 }
    1258             :                 /* rstart points to first value > v or end of
    1259             :                  * r, and nr is the number of values in r that
    1260             :                  * are equal to v */
    1261       34077 :                 if (nr == 0) {
    1262             :                         /* no entries in r found */
    1263      293585 :                         continue;
    1264             :                 }
    1265             :                 /* make space: nl values in l match nr values in r, so
    1266             :                  * we need to add nl * nr values in the results */
    1267      103258 :                 if (maybeextend(r1, r2, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
    1268           0 :                         goto bailout;
    1269             : 
    1270             :                 /* maintain properties */
    1271      102669 :                 if (nl > 1) {
    1272             :                         /* value occurs multiple times in l, so entry
    1273             :                          * in r will be repeated multiple times: hence
    1274             :                          * r2 is not key and not dense */
    1275        9529 :                         if (r2) {
    1276        4525 :                                 r2->tkey = false;
    1277        4525 :                                 r2->tseqbase = oid_nil;
    1278             :                         }
    1279             :                         /* multiple different values will be inserted
    1280             :                          * in r1 (always in order), so not reverse
    1281             :                          * ordered anymore */
    1282        9529 :                         r1->trevsorted = false;
    1283             :                 }
    1284      102669 :                 if (nr > 1) {
    1285             :                         /* value occurs multiple times in r, so entry
    1286             :                          * in l will be repeated multiple times: hence
    1287             :                          * r1 is not key and not dense */
    1288        1313 :                         r1->tkey = false;
    1289        1313 :                         r1->tseqbase = oid_nil;
    1290             :                         /* multiple different values will be inserted
    1291             :                          * in r2 (in order), so not reverse ordered
    1292             :                          * anymore */
    1293        1313 :                         if (r2) {
    1294        1313 :                                 r2->trevsorted = false;
    1295        1313 :                                 if (nl > 1) {
    1296             :                                         /* multiple values in l match
    1297             :                                          * multiple values in r, so an
    1298             :                                          * ordered sequence will be
    1299             :                                          * inserted multiple times in
    1300             :                                          * r2, so r2 is not ordered
    1301             :                                          * anymore */
    1302          51 :                                         r2->tsorted = false;
    1303             :                                 }
    1304             :                         }
    1305             :                 }
    1306      102669 :                 if (BATcount(r1) > 0) {
    1307             :                         /* a new, higher value will be inserted into
    1308             :                          * r1, so r1 is not reverse ordered anymore */
    1309      102515 :                         r1->trevsorted = false;
    1310             :                         /* a new higher value will be added to r2 */
    1311      102515 :                         if (r2) {
    1312       95811 :                                 r2->trevsorted = false;
    1313             :                         }
    1314      102515 :                         if (BATtdense(r1) &&
    1315       36434 :                             ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
    1316          46 :                                 r1->tseqbase = oid_nil;
    1317             :                         }
    1318             :                 }
    1319             : 
    1320      102669 :                 if (r2 &&
    1321       95953 :                     BATcount(r2) > 0 &&
    1322       95898 :                     BATtdense(r2) &&
    1323       35282 :                     ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rstart - nr) {
    1324          28 :                         r2->tseqbase = oid_nil;
    1325             :                 }
    1326             : 
    1327             :                 /* insert values */
    1328      102669 :                 lv = l->hseqbase + lstart - nl;
    1329      243146 :                 for (i = 0; i < nl; i++) {
    1330             :                         BUN j;
    1331             : 
    1332      286236 :                         for (j = 0; j < nr; j++) {
    1333      145759 :                                 APPEND(r1, lv);
    1334             :                         }
    1335      140477 :                         if (r2) {
    1336      122150 :                                 oid rv = r->hseqbase + rstart - nr;
    1337             : 
    1338      249481 :                                 for (j = 0; j < nr; j++) {
    1339      127331 :                                         APPEND(r2, rv);
    1340      127331 :                                         rv++;
    1341             :                                 }
    1342             :                         }
    1343      140477 :                         lv++;
    1344             :                 }
    1345             :         }
    1346             :         /* also set other bits of heap to correct value to indicate size */
    1347         212 :         BATsetcount(r1, BATcount(r1));
    1348         212 :         if (r2) {
    1349         191 :                 BATsetcount(r2, BATcount(r2));
    1350         191 :                 assert(BATcount(r1) == BATcount(r2));
    1351             :         }
    1352         212 :         if (BATcount(r1) > 0) {
    1353         184 :                 if (BATtdense(r1))
    1354         117 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    1355         184 :                 if (r2 && BATtdense(r2))
    1356          91 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    1357             :         } else {
    1358          28 :                 r1->tseqbase = 0;
    1359          28 :                 if (r2) {
    1360          19 :                         r2->tseqbase = 0;
    1361             :                 }
    1362             :         }
    1363         212 :         bat_iterator_end(&li);
    1364         212 :         bat_iterator_end(&ri);
    1365         212 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
    1366             :                   "nil_matches=%s;%s %s "
    1367             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
    1368             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    1369             :                   nil_matches ? "true" : "false",
    1370             :                   swapped ? " swapped" : "", reason,
    1371             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    1372             :                   GDKusec() - t0);
    1373             : 
    1374             :         return GDK_SUCCEED;
    1375             : 
    1376             :   bailout:
    1377           0 :         bat_iterator_end(&li);
    1378           0 :         bat_iterator_end(&ri);
    1379           0 :         BBPreclaim(r1);
    1380           0 :         BBPreclaim(r2);
    1381           0 :         return GDK_FAIL;
    1382             : }
    1383             : 
    1384             : /* Implementation of mergejoin (see below) for the special case that
    1385             :  * the values are of type oid, and the right-hand side is a candidate
    1386             :  * list with exception, and some more conditions are met. */
    1387             : static gdk_return
    1388           0 : mergejoin_cand(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
    1389             :                bool nil_matches, BUN estimate, lng t0, bool swapped,
    1390             :                const char *reason)
    1391             : {
    1392             : /* the comments in this function have not been checked after making a
    1393             :  * copy of mergejoin below and adapting it to a mask right-hand side */
    1394             :         BAT *r1, *r2;
    1395             :         BUN lstart, lend, lcnt;
    1396             :         struct canditer lci, rci;
    1397             :         BUN lscan;              /* opportunistic scan window */
    1398             :         BUN maxsize;
    1399             :         const oid *lvals;
    1400             :         oid v;
    1401             :         BUN nl, nr;
    1402             :         oid lv;
    1403             :         BUN i;
    1404           0 :         BATiter li = bat_iterator(l);
    1405             : 
    1406           0 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    1407             : 
    1408           0 :         MT_thread_setalgorithm(__func__);
    1409             :         lstart = 0;
    1410           0 :         lend = BATcount(l);
    1411             :         lcnt = lend - lstart;
    1412           0 :         if (l->ttype == TYPE_void) {
    1413           0 :                 assert(!is_oid_nil(l->tseqbase));
    1414           0 :                 lcnt = canditer_init(&lci, NULL, l);
    1415             :                 lvals = NULL;
    1416             :         } else {
    1417           0 :                 lci = (struct canditer) {.tpe = cand_dense}; /* not used */
    1418           0 :                 lvals = (const oid *) li.base;
    1419           0 :                 assert(lvals != NULL);
    1420             :         }
    1421             : 
    1422           0 :         assert(complex_cand(r));
    1423           0 :         canditer_init(&rci, NULL, r);
    1424             : 
    1425             :         /* basic properties will be adjusted if necessary later on,
    1426             :          * they were initially set by joininitresults() */
    1427             : 
    1428           0 :         if (lend == 0 || rci.ncand == 0) {
    1429             :                 /* there are no matches */
    1430           0 :                 bat_iterator_end(&li);
    1431           0 :                 return nomatch(r1p, r2p, l, r,
    1432           0 :                                &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
    1433             :                                false, false, __func__, t0);
    1434             :         }
    1435             : 
    1436           0 :         if ((maxsize = joininitresults(r1p, r2p, BATcount(l), BATcount(r),
    1437           0 :                                        l->tkey, r->tkey, false, false,
    1438             :                                        false, false, estimate)) == BUN_NONE) {
    1439           0 :                 bat_iterator_end(&li);
    1440           0 :                 return GDK_FAIL;
    1441             :         }
    1442           0 :         r1 = *r1p;
    1443           0 :         r2 = r2p ? *r2p : NULL;
    1444             : 
    1445             :         /* determine opportunistic scan window for l and r */
    1446           0 :         for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
    1447           0 :                 nl >>= 1;
    1448             : 
    1449           0 :         if (!nil_matches) {
    1450             :                 /* skip over nils at the start of the columns */
    1451           0 :                 if (lscan < lend - lstart && lvals && is_oid_nil(lvals[lstart + lscan])) {
    1452           0 :                         lstart = binsearch_oid(NULL, 0, lvals, lstart + lscan,
    1453             :                                                lend - 1, oid_nil, 1, 1);
    1454           0 :                 } else if (lvals) {
    1455           0 :                         while (is_oid_nil(lvals[lstart]))
    1456           0 :                                 lstart++;
    1457             :                 } /* else l is candidate list: no nils */
    1458             :         }
    1459             :         /* from here on we don't have to worry about nil values */
    1460             : 
    1461           0 :         while (lstart < lend && rci.next < rci.ncand) {
    1462           0 :                 v = canditer_peek(&rci);
    1463             : 
    1464           0 :                 if (lvals) {
    1465           0 :                         if (lscan < lend - lstart &&
    1466           0 :                             lvals[lstart + lscan] < v) {
    1467           0 :                                 lstart = binsearch_oid(NULL, 0, lvals,
    1468             :                                                        lstart + lscan,
    1469             :                                                        lend - 1, v, 1, 0);
    1470             :                         } else {
    1471             :                                 /* scan l for v */
    1472           0 :                                 while (lstart < lend && lvals[lstart] < v)
    1473           0 :                                         lstart++;
    1474             :                         }
    1475             :                 } else {
    1476           0 :                         lstart = canditer_search(&lci, v, true);
    1477           0 :                         canditer_setidx(&lci, lstart);
    1478             :                 }
    1479           0 :                 if (lstart >= lend) {
    1480             :                         /* nothing found */
    1481             :                         break;
    1482             :                 }
    1483             : 
    1484             :                 /* Here we determine the next value in l that we are
    1485             :                  * going to try to match in r.  We will also count the
    1486             :                  * number of occurrences in l of that value.
    1487             :                  * Afterwards, v points to the value and nl is the
    1488             :                  * number of times it occurs.  Also, lstart will
    1489             :                  * point to the next value to be considered (ready for
    1490             :                  * the next iteration).
    1491             :                  * If there are many equal values in l (more than
    1492             :                  * lscan), we will use binary search to find the end
    1493             :                  * of the sequence.  Obviously, we can do this only if
    1494             :                  * l is actually sorted (lscan > 0). */
    1495             :                 nl = 1;         /* we'll match (at least) one in l */
    1496             :                 nr = 0;         /* maybe we won't match anything in r */
    1497           0 :                 v = lvals ? lvals[lstart] : canditer_next(&lci);
    1498           0 :                 if (l->tkey || lvals == NULL) {
    1499             :                         /* if l is key, there is a single value */
    1500           0 :                         lstart++;
    1501           0 :                 } else if (lscan < lend - lstart &&
    1502           0 :                            v == lvals[lstart + lscan]) {
    1503             :                         /* lots of equal values: use binary search to
    1504             :                          * find end */
    1505           0 :                         nl = binsearch_oid(NULL, 0, lvals, lstart + lscan,
    1506             :                                            lend - 1, v, 1, 1);
    1507           0 :                         nl -= lstart;
    1508           0 :                         lstart += nl;
    1509             :                 } else {
    1510             :                         /* just scan */
    1511           0 :                         while (++lstart < lend && v == lvals[lstart])
    1512           0 :                                 nl++;
    1513             :                 }
    1514             :                 /* lstart points one beyond the value we're
    1515             :                  * going to match: ready for the next iteration. */
    1516             : 
    1517             :                 /* First we find the first value in r that is at
    1518             :                  * least as large as v, then we find the first
    1519             :                  * value in r that is larger than v.  The difference
    1520             :                  * is the number of values equal to v and is stored in
    1521             :                  * nr.
    1522             :                  * We will use binary search on r to find both ends of
    1523             :                  * the sequence of values that are equal to v in case
    1524             :                  * the position is "too far" (more than rscan
    1525             :                  * away). */
    1526             : 
    1527             :                 /* first find the location of the first value in r
    1528             :                  * that is >= v, then find the location of the first
    1529             :                  * value in r that is > v; the difference is the
    1530             :                  * number of values equal to v */
    1531           0 :                 nr = canditer_search(&rci, v, true);
    1532           0 :                 canditer_setidx(&rci, nr);
    1533           0 :                 if (nr == rci.ncand) {
    1534             :                         /* nothing found */
    1535             :                         break;
    1536             :                 }
    1537             : 
    1538             :                 /* now find the end of the sequence of equal values v */
    1539             : 
    1540             :                 /* if r is key, there is zero or one match, otherwise
    1541             :                  * look ahead a little (rscan) in r to see whether
    1542             :                  * we're better off doing a binary search */
    1543           0 :                 if (canditer_peek(&rci) == v) {
    1544             :                         nr = 1;
    1545           0 :                         canditer_next(&rci);
    1546             :                 } else {
    1547             :                         /* rci points to first value > v or end of
    1548             :                          * r, and nr is the number of values in r that
    1549             :                          * are equal to v */
    1550             :                         /* no entries in r found */
    1551           0 :                         continue;
    1552             :                 }
    1553             :                 /* make space: nl values in l match nr values in r, so
    1554             :                  * we need to add nl * nr values in the results */
    1555           0 :                 if (maybeextend(r1, r2, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
    1556           0 :                         goto bailout;
    1557             : 
    1558             :                 /* maintain properties */
    1559           0 :                 if (nl > 1) {
    1560             :                         /* value occurs multiple times in l, so entry
    1561             :                          * in r will be repeated multiple times: hence
    1562             :                          * r2 is not key and not dense */
    1563           0 :                         if (r2) {
    1564           0 :                                 r2->tkey = false;
    1565           0 :                                 r2->tseqbase = oid_nil;
    1566             :                         }
    1567             :                         /* multiple different values will be inserted
    1568             :                          * in r1 (always in order), so not reverse
    1569             :                          * ordered anymore */
    1570           0 :                         r1->trevsorted = false;
    1571             :                 }
    1572           0 :                 if (BATcount(r1) > 0) {
    1573             :                         /* a new, higher value will be inserted into
    1574             :                          * r1, so r1 is not reverse ordered anymore */
    1575           0 :                         r1->trevsorted = false;
    1576             :                         /* a new higher value will be added to r2 */
    1577           0 :                         if (r2) {
    1578           0 :                                 r2->trevsorted = false;
    1579             :                         }
    1580           0 :                         if (BATtdense(r1) &&
    1581           0 :                             ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
    1582           0 :                                 r1->tseqbase = oid_nil;
    1583             :                         }
    1584             :                 }
    1585             : 
    1586           0 :                 if (r2 &&
    1587           0 :                     BATcount(r2) > 0 &&
    1588           0 :                     BATtdense(r2) &&
    1589           0 :                     ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rci.next - nr) {
    1590           0 :                         r2->tseqbase = oid_nil;
    1591             :                 }
    1592             : 
    1593             :                 /* insert values */
    1594           0 :                 lv = l->hseqbase + lstart - nl;
    1595           0 :                 for (i = 0; i < nl; i++) {
    1596             :                         BUN j;
    1597             : 
    1598           0 :                         for (j = 0; j < nr; j++) {
    1599           0 :                                 APPEND(r1, lv);
    1600             :                         }
    1601           0 :                         if (r2) {
    1602           0 :                                 oid rv = r->hseqbase + rci.next - nr;
    1603             : 
    1604           0 :                                 for (j = 0; j < nr; j++) {
    1605           0 :                                         APPEND(r2, rv);
    1606           0 :                                         rv++;
    1607             :                                 }
    1608             :                         }
    1609           0 :                         lv++;
    1610             :                 }
    1611             :         }
    1612             :         /* also set other bits of heap to correct value to indicate size */
    1613           0 :         BATsetcount(r1, BATcount(r1));
    1614           0 :         if (r2) {
    1615           0 :                 BATsetcount(r2, BATcount(r2));
    1616           0 :                 assert(BATcount(r1) == BATcount(r2));
    1617             :         }
    1618           0 :         if (BATcount(r1) > 0) {
    1619           0 :                 if (BATtdense(r1))
    1620           0 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    1621           0 :                 if (r2 && BATtdense(r2))
    1622           0 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    1623             :         } else {
    1624           0 :                 r1->tseqbase = 0;
    1625           0 :                 if (r2) {
    1626           0 :                         r2->tseqbase = 0;
    1627             :                 }
    1628             :         }
    1629           0 :         bat_iterator_end(&li);
    1630           0 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
    1631             :                   "nil_matches=%s;%s %s "
    1632             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
    1633             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    1634             :                   nil_matches ? "true" : "false",
    1635             :                   swapped ? " swapped" : "", reason,
    1636             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    1637             :                   GDKusec() - t0);
    1638             : 
    1639             :         return GDK_SUCCEED;
    1640             : 
    1641             :   bailout:
    1642           0 :         bat_iterator_end(&li);
    1643           0 :         BBPreclaim(r1);
    1644           0 :         BBPreclaim(r2);
    1645           0 :         return GDK_FAIL;
    1646             : }
    1647             : 
    1648             : /* Perform a "merge" join on l and r (if both are sorted) with
    1649             :  * optional candidate lists, or join using binary search on r if l is
    1650             :  * not sorted.  The return BATs have already been created by the
    1651             :  * caller.
    1652             :  *
    1653             :  * If nil_matches is set, nil values are treated as ordinary values
    1654             :  * that can match; otherwise nil values never match.
    1655             :  *
    1656             :  * If nil_on_miss is set, a nil value is returned in r2 if there is no
    1657             :  * match in r for a particular value in l (left outer join).
    1658             :  *
    1659             :  * If semi is set, only a single set of values in r1/r2 is returned if
    1660             :  * there is a match of l in r, no matter how many matches there are in
    1661             :  * r; otherwise all matches are returned.
    1662             :  *
    1663             :  * If max_one is set, only a single match is allowed.  This is like
    1664             :  * semi, but enforces the single match.
    1665             :  *
    1666             :  * t0 and swapped are only for debugging (ALGOMASK set in GDKdebug).
    1667             :  */
    1668             : static gdk_return
    1669       16473 : mergejoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
    1670             :           struct canditer *restrict lci, struct canditer *restrict rci,
    1671             :           bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
    1672             :           bool not_in, bool max_one, bool min_one, BUN estimate,
    1673             :           lng t0, bool swapped,
    1674             :           const char *reason)
    1675             : {
    1676             :         /* [lr]scan determine how far we look ahead in l/r in order to
    1677             :          * decide whether we want to do a binary search or a scan */
    1678             :         BUN lscan, rscan;
    1679             :         const void *lvals, *rvals; /* the values of l/r (NULL if dense) */
    1680             :         const char *lvars, *rvars; /* the indirect values (NULL if fixed size) */
    1681       16473 :         const void *nil = ATOMnilptr(l->ttype);
    1682       16473 :         int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
    1683             :         const void *v;          /* points to value under consideration */
    1684             :         const void *prev = NULL;
    1685             :         BUN nl, nr;
    1686             :         bool insert_nil;
    1687             :         /* equal_order is set if we can scan both BATs in the same
    1688             :          * order, so when both are sorted or both are reverse sorted
    1689             :          * -- important to know in order to skip over values; if l is
    1690             :          * not sorted, this must be set to true and we will always do a
    1691             :          * binary search on all of r */
    1692             :         bool equal_order;
    1693             :         /* [lr]ordering is either 1 or -1 depending on the order of
    1694             :          * l/r: it determines the comparison function used */
    1695             :         int lordering, rordering;
    1696             :         oid lv;
    1697             :         BUN i, j;               /* counters */
    1698       16473 :         oid lval = oid_nil, rval = oid_nil; /* temporary space to point v to */
    1699             :         struct canditer llci, rrci;
    1700             :         struct canditer *mlci, xlci;
    1701             :         struct canditer *mrci, xrci;
    1702             : 
    1703       16473 :         if (lci->tpe == cand_dense && lci->ncand == BATcount(l) &&
    1704       16428 :             rci->tpe == cand_dense && rci->ncand == BATcount(r) &&
    1705       15858 :             !nil_on_miss && !semi && !max_one && !min_one && !only_misses &&
    1706       10731 :             !not_in &&
    1707        9232 :             l->tsorted && r->tsorted) {
    1708             :                 /* special cases with far fewer options */
    1709        9147 :                 if (complex_cand(r))
    1710           0 :                         return mergejoin_cand(r1p, r2p, l, r, nil_matches,
    1711             :                                               estimate, t0, swapped, __func__);
    1712       18217 :                 switch (ATOMbasetype(l->ttype)) {
    1713        8791 :                 case TYPE_int:
    1714        8791 :                         return mergejoin_int(r1p, r2p, l, r, nil_matches,
    1715             :                                              estimate, t0, swapped, __func__);
    1716         210 :                 case TYPE_lng:
    1717         210 :                         return mergejoin_lng(r1p, r2p, l, r, nil_matches,
    1718             :                                              estimate, t0, swapped, __func__);
    1719             :                 }
    1720             :         }
    1721             : 
    1722       22343 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    1723        7472 :         assert(r->tsorted || r->trevsorted);
    1724             : 
    1725        7472 :         BATiter li = bat_iterator(l);
    1726        7474 :         BATiter ri = bat_iterator(r);
    1727        7475 :         MT_thread_setalgorithm(__func__);
    1728        7472 :         if (BATtvoid(l)) {
    1729             :                 /* l->ttype == TYPE_void && is_oid_nil(l->tseqbase) is
    1730             :                  * handled by selectjoin */
    1731          87 :                 assert(!is_oid_nil(l->tseqbase));
    1732          87 :                 canditer_init(&llci, NULL, l);
    1733          86 :                 lvals = NULL;
    1734             :         } else {
    1735        7385 :                 lvals = li.base;                              /* non NULL */
    1736        7385 :                 llci = (struct canditer) {.tpe = cand_dense}; /* not used */
    1737             :         }
    1738        7471 :         rrci = (struct canditer) {.tpe = cand_dense};
    1739        7471 :         if (BATtvoid(r)) {
    1740           0 :                 if (!is_oid_nil(r->tseqbase))
    1741           0 :                         canditer_init(&rrci, NULL, r);
    1742             :                 rvals = NULL;
    1743             :         } else {
    1744        7471 :                 rvals = ri.base;
    1745             :         }
    1746        7468 :         if (l->tvarsized && l->ttype) {
    1747         241 :                 assert(r->tvarsized && r->ttype);
    1748         241 :                 lvars = li.vh->base;
    1749         241 :                 rvars = ri.vh->base;
    1750             :         } else {
    1751        7227 :                 assert(!r->tvarsized || !r->ttype);
    1752             :                 lvars = rvars = NULL;
    1753             :         }
    1754             : 
    1755        7468 :         if (not_in && rci->ncand > 0 && !r->tnonil &&
    1756        1397 :             ((BATtvoid(l) && l->tseqbase == oid_nil) ||
    1757        1397 :              (BATtvoid(r) && r->tseqbase == oid_nil) ||
    1758        1397 :              (rvals && cmp(nil, VALUE(r, (r->tsorted ? rci->seq : canditer_last(rci)) - r->hseqbase)) == 0))) {
    1759           0 :                 bat_iterator_end(&li);
    1760           0 :                 bat_iterator_end(&ri);
    1761           0 :                 return nomatch(r1p, r2p, l, r, lci, false, false,
    1762             :                                __func__, t0);
    1763             :         }
    1764             : 
    1765        7468 :         if (lci->ncand == 0 ||
    1766        7468 :             rci->ncand == 0 ||
    1767        7468 :             (!nil_matches &&
    1768        7225 :              ((l->ttype == TYPE_void && is_oid_nil(l->tseqbase)) ||
    1769        7225 :               (r->ttype == TYPE_void && is_oid_nil(r->tseqbase)))) ||
    1770        7468 :             (l->ttype == TYPE_void && is_oid_nil(l->tseqbase) &&
    1771           0 :              (r->tnonil ||
    1772           0 :               (r->ttype == TYPE_void && !is_oid_nil(r->tseqbase)))) ||
    1773        7468 :             (r->ttype == TYPE_void && is_oid_nil(r->tseqbase) &&
    1774           0 :              (l->tnonil ||
    1775           0 :               (l->ttype == TYPE_void && !is_oid_nil(l->tseqbase))))) {
    1776             :                 /* there are no matches */
    1777           0 :                 bat_iterator_end(&li);
    1778           0 :                 bat_iterator_end(&ri);
    1779           0 :                 return nomatch(r1p, r2p, l, r, lci, nil_on_miss, only_misses,
    1780             :                                __func__, t0);
    1781             :         }
    1782             : 
    1783        7468 :         BUN maxsize = joininitresults(r1p, r2p, lci->ncand, rci->ncand,
    1784        7468 :                                       l->tkey, r->tkey, semi | max_one,
    1785             :                                       nil_on_miss, only_misses, min_one,
    1786             :                                       estimate);
    1787        7454 :         if (maxsize == BUN_NONE) {
    1788           0 :                 bat_iterator_end(&li);
    1789           0 :                 bat_iterator_end(&ri);
    1790           0 :                 return GDK_FAIL;
    1791             :         }
    1792        7454 :         BAT *r1 = *r1p;
    1793        7454 :         BAT *r2 = r2p ? *r2p : NULL;
    1794             : 
    1795        7454 :         if (lci->tpe == cand_mask) {
    1796             :                 mlci = lci;
    1797           0 :                 canditer_init(&xlci, l, NULL);
    1798             :                 lci = &xlci;
    1799             :         } else {
    1800             :                 mlci = NULL;
    1801        7454 :                 xlci = (struct canditer) {.tpe = cand_dense}; /* not used */
    1802             :         }
    1803        7454 :         if (rci->tpe == cand_mask) {
    1804             :                 mrci = rci;
    1805           0 :                 canditer_init(&xrci, r, NULL);
    1806             :                 rci = &xrci;
    1807             :         } else {
    1808             :                 mrci = NULL;
    1809        7454 :                 xrci = (struct canditer) {.tpe = cand_dense}; /* not used */
    1810             :         }
    1811             : 
    1812        7454 :         if (l->tsorted || l->trevsorted) {
    1813        5758 :                 equal_order = (l->tsorted && r->tsorted) ||
    1814         450 :                         (l->trevsorted && r->trevsorted &&
    1815         194 :                          !BATtvoid(l) && !BATtvoid(r));
    1816        5758 :                 lordering = l->tsorted && (r->tsorted || !equal_order) ? 1 : -1;
    1817        5758 :                 rordering = equal_order ? lordering : -lordering;
    1818        5758 :                 if (!l->tnonil && !nil_matches && !nil_on_miss) {
    1819        2868 :                         nl = binsearch(NULL, 0, l->ttype, lvals, lvars, li.width, 0, BATcount(l), nil, l->tsorted ? 1 : -1, l->tsorted ? 1 : 0);
    1820        2664 :                         nl = canditer_search(lci, nl + l->hseqbase, true);
    1821        2662 :                         if (l->tsorted) {
    1822        2462 :                                 canditer_setidx(lci, nl);
    1823         200 :                         } else if (l->trevsorted) {
    1824         200 :                                 lci->ncand = nl;
    1825             :                         }
    1826             :                 }
    1827             :                 /* determine opportunistic scan window for l */
    1828       11505 :                 lscan = 4 + ilog2(lci->ncand);
    1829             :         } else {
    1830             :                 /* if l not sorted, we will always use binary search
    1831             :                  * on r */
    1832        1696 :                 assert(!BATtvoid(l)); /* void is always sorted */
    1833             :                 lscan = 0;
    1834             :                 equal_order = true;
    1835             :                 lordering = 1;
    1836        1696 :                 rordering = r->tsorted ? 1 : -1;
    1837             :         }
    1838             :         /* determine opportunistic scan window for r; if l is not
    1839             :          * sorted this is only used to find range of equal values */
    1840        7449 :         rscan = 4 + ilog2(rci->ncand);
    1841             : 
    1842        7449 :         if (!equal_order) {
    1843             :                 /* we go through r backwards */
    1844         259 :                 canditer_setidx(rci, rci->ncand);
    1845             :         }
    1846             :         /* At this point the various variables that help us through
    1847             :          * the algorithm have been set.  The table explains them.  The
    1848             :          * first two columns are the inputs, the next three columns
    1849             :          * are the variables, the final two columns indicate how the
    1850             :          * variables can be used.
    1851             :          *
    1852             :          * l/r    sl/sr | vals  cand  off | result   value being matched
    1853             :          * -------------+-----------------+----------------------------------
    1854             :          * dense  NULL  | NULL  NULL  set | i        off==nil?nil:i+off
    1855             :          * dense  dense | NULL  NULL  set | i        off==nil?nil:i+off
    1856             :          * dense  set   | NULL  set   set | cand[i]  off==nil?nil:cand[i]+off
    1857             :          * set    NULL  | set   NULL  0   | i        vals[i]
    1858             :          * set    dense | set   NULL  0   | i        vals[i]
    1859             :          * set    set   | set   set   0   | cand[i]  vals[cand[i]]
    1860             :          *
    1861             :          * If {l,r}off is lng_nil, all values in the corresponding bat
    1862             :          * are oid_nil because the bat has type VOID and the tseqbase
    1863             :          * is nil.
    1864             :          */
    1865             : 
    1866             :         /* Before we start adding values to r1 and r2, the properties
    1867             :          * are as follows:
    1868             :          * tseqbase - 0
    1869             :          * tkey - true
    1870             :          * tsorted - true
    1871             :          * trevsorted - true
    1872             :          * tnil - false
    1873             :          * tnonil - true
    1874             :          * We will modify these as we go along.
    1875             :          */
    1876      461126 :         while (lci->next < lci->ncand) {
    1877      456369 :                 if (lscan == 0) {
    1878             :                         /* always search r completely */
    1879      300173 :                         assert(equal_order);
    1880      300173 :                         canditer_reset(rci);
    1881             :                 } else {
    1882             :                         /* If l is sorted (lscan > 0), we look at the
    1883             :                          * next value in r to see whether we can jump
    1884             :                          * over a large section of l using binary
    1885             :                          * search.  We do this by looking ahead in l
    1886             :                          * (lscan far, to be precise) and seeing if
    1887             :                          * the value there is still too "small"
    1888             :                          * (definition depends on sort order of l).
    1889             :                          * If it is, we use binary search on l,
    1890             :                          * otherwise we scan l for the next position
    1891             :                          * with a value greater than or equal to the
    1892             :                          * value in r.
    1893             :                          * The next value to match in r is the first
    1894             :                          * if equal_order is set, the last
    1895             :                          * otherwise.
    1896             :                          * When skipping over values in l, we count
    1897             :                          * how many we skip in nlx.  We need this in
    1898             :                          * case only_misses or nil_on_miss is set, and
    1899             :                          * to properly set the dense property in the
    1900             :                          * first output BAT. */
    1901             :                         BUN nlx = 0; /* number of non-matching values in l */
    1902             : 
    1903      156196 :                         if (equal_order) {
    1904      155581 :                                 if (rci->next == rci->ncand)
    1905             :                                         v = NULL; /* no more values */
    1906      153404 :                                 else if (mrci) {
    1907           0 :                                         oid rv = canditer_mask_next(mrci, canditer_peek(rci), true);
    1908           0 :                                         v = rv == oid_nil ? NULL : VALUE(r, rv - r->hseqbase);
    1909             :                                 } else
    1910      153404 :                                         v = VALUE(r, canditer_peek(rci) - r->hseqbase);
    1911             :                         } else {
    1912         615 :                                 if (rci->next == 0)
    1913             :                                         v = NULL; /* no more values */
    1914         539 :                                 else if (mrci) {
    1915           0 :                                         oid rv = canditer_mask_next(mrci, canditer_peekprev(rci), false);
    1916           0 :                                         v = rv == oid_nil ? NULL : VALUE(r, rv - r->hseqbase);
    1917             :                                 } else
    1918         539 :                                         v = VALUE(r, canditer_peekprev(rci) - r->hseqbase);
    1919             :                         }
    1920             :                         /* here, v points to next value in r, or if
    1921             :                          * we're at the end of r, v is NULL */
    1922             :                         if (v == NULL) {
    1923        2253 :                                 nlx = lci->ncand - lci->next;
    1924             :                         } else {
    1925      154006 :                                 if (lscan < lci->ncand - lci->next) {
    1926      132598 :                                         lv = canditer_idx(lci, lci->next + lscan);
    1927      132886 :                                         lv -= l->hseqbase;
    1928      132886 :                                         if (lvals) {
    1929      131734 :                                                 if (lordering * cmp(VALUE(l, lv), v) < 0) {
    1930        1652 :                                                         nlx = binsearch(NULL, 0, l->ttype, lvals, lvars, li.width, lv, BATcount(l), v, lordering, 0);
    1931        1652 :                                                         nlx = canditer_search(lci, nlx + l->hseqbase, true);
    1932        1652 :                                                         nlx -= lci->next;
    1933             :                                                 }
    1934             :                                         } else {
    1935        1152 :                                                 assert(lordering == 1);
    1936        1152 :                                                 if (canditer_idx(&llci, lv) < *(const oid *)v) {
    1937           8 :                                                         nlx = canditer_search(&llci, *(const oid *)v, true);
    1938           8 :                                                         nlx = canditer_search(lci, nlx + l->hseqbase, true);
    1939           8 :                                                         nlx -= lci->next;
    1940             :                                                 }
    1941             :                                         }
    1942      132840 :                                         if (mlci) {
    1943           0 :                                                 lv = canditer_mask_next(mlci, lci->seq + lci->next + nlx, true);
    1944           0 :                                                 if (lv == oid_nil)
    1945           0 :                                                         nlx = lci->ncand - lci->next;
    1946             :                                                 else
    1947           0 :                                                         nlx = lv - lci->seq - lci->next;
    1948             :                                         }
    1949      132840 :                                         if (lci->next + nlx == lci->ncand)
    1950             :                                                 v = NULL;
    1951             :                                 }
    1952             :                         }
    1953      135093 :                         if (nlx > 0) {
    1954        3913 :                                 if (only_misses) {
    1955        2296 :                                         if (maybeextend(r1, r2, nlx, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
    1956           0 :                                                 goto bailout;
    1957      349376 :                                         while (nlx > 0) {
    1958      347080 :                                                 lv = canditer_next(lci);
    1959      347081 :                                                 if (mlci == NULL || canditer_contains(mlci, lv))
    1960      347081 :                                                         APPEND(r1, lv);
    1961      347081 :                                                 nlx--;
    1962             :                                         }
    1963        2296 :                                         if (r1->trevsorted && BATcount(r1) > 1)
    1964         911 :                                                 r1->trevsorted = false;
    1965        1617 :                                 } else if (nil_on_miss) {
    1966           0 :                                         if (r2->tnonil) {
    1967           0 :                                                 r2->tnil = true;
    1968           0 :                                                 r2->tnonil = false;
    1969           0 :                                                 r2->tseqbase = oid_nil;
    1970           0 :                                                 r2->tsorted = false;
    1971           0 :                                                 r2->trevsorted = false;
    1972           0 :                                                 r2->tkey = false;
    1973             :                                         }
    1974           0 :                                         if (maybeextend(r1, r2, nlx, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
    1975           0 :                                                 goto bailout;
    1976           0 :                                         while (nlx > 0) {
    1977           0 :                                                 lv = canditer_next(lci);
    1978           0 :                                                 if (mlci == NULL || canditer_contains(mlci, lv)) {
    1979           0 :                                                         APPEND(r1, lv);
    1980           0 :                                                         APPEND(r2, oid_nil);
    1981             :                                                 }
    1982           0 :                                                 nlx--;
    1983             :                                         }
    1984           0 :                                         if (r1->trevsorted && BATcount(r1) > 1)
    1985           0 :                                                 r1->trevsorted = false;
    1986             :                                 } else {
    1987        1617 :                                         canditer_setidx(lci, lci->next + nlx);
    1988             :                                 }
    1989             :                         }
    1990      156501 :                         if (v == NULL) {
    1991             :                                 /* we have exhausted the inputs */
    1992             :                                 break;
    1993             :                         }
    1994             :                 }
    1995             : 
    1996             :                 /* Here we determine the next value in l that we are
    1997             :                  * going to try to match in r.  We will also count the
    1998             :                  * number of occurrences in l of that value.
    1999             :                  * Afterwards, v points to the value and nl is the
    2000             :                  * number of times it occurs.  Also, lci will point to
    2001             :                  * the next value to be considered (ready for the next
    2002             :                  * iteration).
    2003             :                  * If there are many equal values in l (more than
    2004             :                  * lscan), we will use binary search to find the end
    2005             :                  * of the sequence.  Obviously, we can do this only if
    2006             :                  * l is actually sorted (lscan > 0). */
    2007             :                 nl = 1;         /* we'll match (at least) one in l */
    2008             :                 nr = 0;         /* maybe we won't match anything in r */
    2009      447819 :                 lv = canditer_peek(lci);
    2010      447751 :                 if (mlci) {
    2011           0 :                         lv = canditer_mask_next(mlci, lv, true);
    2012           0 :                         if (lv == oid_nil)
    2013             :                                 break;
    2014           0 :                         canditer_setidx(lci, canditer_search(lci, lv, true));
    2015             :                 }
    2016      451541 :                 v = VALUE(l, lv - l->hseqbase);
    2017      451541 :                 if (l->tkey) {
    2018             :                         /* if l is key, there is a single value */
    2019      333541 :                 } else if (lscan > 0 &&
    2020       87114 :                            lscan < lci->ncand - lci->next &&
    2021       42966 :                            cmp(v, VALUE(l, canditer_idx(lci, lci->next + lscan) - l->hseqbase)) == 0) {
    2022             :                         /* lots of equal values: use binary search to
    2023             :                          * find end */
    2024         942 :                         assert(lvals != NULL);
    2025         942 :                         nl = binsearch(NULL, 0,
    2026         942 :                                        l->ttype, lvals, lvars,
    2027         942 :                                        li.width, lci->next + lscan,
    2028             :                                        BATcount(l),
    2029             :                                        v, lordering, 1);
    2030         944 :                         nl = canditer_search(lci, nl + l->hseqbase, true);
    2031         942 :                         nl -= lci->next;
    2032             :                 } else {
    2033      332477 :                         struct canditer ci = *lci; /* work on copy */
    2034             :                         nl = 0; /* it will be incremented again */
    2035             :                         do {
    2036      526316 :                                 canditer_next(&ci);
    2037      518679 :                                 nl++;
    2038      514926 :                         } while (ci.next < ci.ncand &&
    2039      518679 :                                  cmp(v, VALUE(l, canditer_peek(&ci) - l->hseqbase)) == 0);
    2040             :                 }
    2041             :                 /* lci->next + nl is the position for the next iteration */
    2042             : 
    2043      442213 :                 if ((!nil_matches || not_in) && !l->tnonil && cmp(v, nil) == 0) {
    2044         651 :                         if (not_in) {
    2045             :                                 /* just skip the whole thing: nils
    2046             :                                  * don't cause any output */
    2047           1 :                                 canditer_setidx(lci, lci->next + nl);
    2048           1 :                                 continue;
    2049             :                         }
    2050             :                         /* v is nil and nils don't match anything, set
    2051             :                          * to NULL to indicate nil */
    2052             :                         v = NULL;
    2053             :                 }
    2054             : 
    2055             :                 /* First we find the "first" value in r that is "at
    2056             :                  * least as large" as v, then we find the "first"
    2057             :                  * value in r that is "larger" than v.  The difference
    2058             :                  * is the number of values equal to v and is stored in
    2059             :                  * nr.  The definitions of "larger" and "first" depend
    2060             :                  * on the orderings of l and r.  If equal_order is
    2061             :                  * set, we go through r from low to high (this
    2062             :                  * includes the case that l is not sorted); otherwise
    2063             :                  * we go through r from high to low.
    2064             :                  * In either case, we will use binary search on r to
    2065             :                  * find both ends of the sequence of values that are
    2066             :                  * equal to v in case the position is "too far" (more
    2067             :                  * than rscan away). */
    2068             :                 if (v == NULL) {
    2069             :                         nr = 0; /* nils don't match anything */
    2070      441047 :                 } else if (r->ttype == TYPE_void && is_oid_nil(r->tseqbase)) {
    2071           0 :                         if (is_oid_nil(*(const oid *) v)) {
    2072             :                                 /* all values in r match */
    2073           0 :                                 nr = rci->ncand;
    2074             :                         } else {
    2075             :                                 /* no value in r matches */
    2076             :                                 nr = 0;
    2077             :                         }
    2078             :                         /* in either case, we're done after this */
    2079           0 :                         canditer_setidx(rci, equal_order ? rci->ncand : 0);
    2080      441047 :                 } else if (equal_order) {
    2081             :                         /* first find the location of the first value
    2082             :                          * in r that is >= v, then find the location
    2083             :                          * of the first value in r that is > v; the
    2084             :                          * difference is the number of values equal
    2085             :                          * v; we change rci */
    2086             : 
    2087             :                         /* look ahead a little (rscan) in r to
    2088             :                          * see whether we're better off doing
    2089             :                          * a binary search */
    2090      440509 :                         if (rvals) {
    2091      440509 :                                 if (rscan < rci->ncand - rci->next &&
    2092      392648 :                                     rordering * cmp(v, VALUE(r, canditer_idx(rci, rci->next + rscan) - r->hseqbase)) > 0) {
    2093             :                                         /* value too far away in r:
    2094             :                                          * use binary search */
    2095      109714 :                                         lv = binsearch(NULL, 0, r->ttype, rvals, rvars, ri.width, rci->next + rscan, BATcount(r), v, rordering, 0);
    2096      121385 :                                         lv = canditer_search(rci, lv + r->hseqbase, true);
    2097      120188 :                                         canditer_setidx(rci, lv);
    2098             :                                 } else {
    2099             :                                         /* scan r for v */
    2100      362638 :                                         while (rci->next < rci->ncand) {
    2101      361204 :                                                 if (rordering * cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) <= 0)
    2102             :                                                         break;
    2103       29416 :                                                 canditer_next(rci);
    2104             :                                         }
    2105             :                                 }
    2106      879198 :                                 if (rci->next < rci->ncand &&
    2107      429512 :                                     cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) == 0) {
    2108             :                                         /* if we found an equal value,
    2109             :                                          * look for the last equal
    2110             :                                          * value */
    2111      229079 :                                         if (r->tkey) {
    2112             :                                                 /* r is key, there can
    2113             :                                                  * only be a single
    2114             :                                                  * equal value */
    2115             :                                                 nr = 1;
    2116      128081 :                                                 canditer_next(rci);
    2117      200672 :                                         } else if (rscan < rci->ncand - rci->next &&
    2118       99676 :                                                    cmp(v, VALUE(r, canditer_idx(rci, rci->next + rscan) - r->hseqbase)) == 0) {
    2119             :                                                 /* many equal values:
    2120             :                                                  * use binary search
    2121             :                                                  * to find the end */
    2122       65649 :                                                 nr = binsearch(NULL, 0, r->ttype, rvals, rvars, ri.width, rci->next + rscan, BATcount(r), v, rordering, 1);
    2123       65650 :                                                 nr = canditer_search(rci, nr + r->hseqbase, true);
    2124       65651 :                                                 nr -= rci->next;
    2125       65651 :                                                 canditer_setidx(rci, rci->next + nr);
    2126             :                                         } else {
    2127             :                                                 /* scan r for end of
    2128             :                                                  * range */
    2129             :                                                 do {
    2130       93735 :                                                         nr++;
    2131       93735 :                                                         canditer_next(rci);
    2132       93410 :                                                 } while (rci->next < rci->ncand &&
    2133       93735 :                                                          cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) == 0);
    2134             :                                         }
    2135             :                                 }
    2136             :                         } else {
    2137           0 :                                 assert(rordering == 1);
    2138           0 :                                 rval = canditer_search(&rrci, *(const oid*)v, true) + r->hseqbase;
    2139           0 :                                 lv = canditer_search(rci, rval, true);
    2140           0 :                                 canditer_setidx(rci, lv);
    2141           0 :                                 nr = (canditer_idx(&rrci, canditer_peek(rci) - r->hseqbase) == *(oid*)v);
    2142           0 :                                 if (nr == 1)
    2143           0 :                                         canditer_next(rci);
    2144             :                         }
    2145             :                         /* rci points to first value > v or end of r,
    2146             :                          * and nr is the number of values in r that
    2147             :                          * are equal to v */
    2148             :                 } else {
    2149             :                         /* first find the location of the first value
    2150             :                          * in r that is > v, then find the location
    2151             :                          * of the first value in r that is >= v; the
    2152             :                          * difference is the number of values equal
    2153             :                          * v; we change rci */
    2154             : 
    2155             :                         /* look back from the end a little
    2156             :                          * (rscan) in r to see whether we're
    2157             :                          * better off doing a binary search */
    2158         538 :                         if (rvals) {
    2159         538 :                                 if (rci->next > rscan &&
    2160         183 :                                     rordering * cmp(v, VALUE(r, canditer_idx(rci, rci->next - rscan) - r->hseqbase)) < 0) {
    2161             :                                         /* value too far away
    2162             :                                          * in r: use binary
    2163             :                                          * search */
    2164          28 :                                         lv = binsearch(NULL, 0, r->ttype, rvals, rvars, ri.width, 0, rci->next - rscan, v, rordering, 1);
    2165          28 :                                         lv = canditer_search(rci, lv + r->hseqbase, true);
    2166          28 :                                         canditer_setidx(rci, lv);
    2167             :                                 } else {
    2168             :                                         /* scan r for v */
    2169        1465 :                                         while (rci->next > 0 &&
    2170        1460 :                                                rordering * cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) < 0)
    2171         956 :                                                 canditer_prev(rci);
    2172             :                                 }
    2173        1054 :                                 if (rci->next > 0 &&
    2174         517 :                                     cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) == 0) {
    2175             :                                         /* if we found an equal value,
    2176             :                                          * look for the last equal
    2177             :                                          * value */
    2178         509 :                                         if (r->tkey) {
    2179             :                                                 /* r is key, there can only be a single equal value */
    2180             :                                                 nr = 1;
    2181         324 :                                                 canditer_prev(rci);
    2182         272 :                                         } else if (rci->next > rscan &&
    2183          87 :                                                    cmp(v, VALUE(r, canditer_idx(rci, rci->next - rscan) - r->hseqbase)) == 0) {
    2184             :                                                 /* use binary search to find the start */
    2185          74 :                                                 nr = binsearch(NULL, 0, r->ttype, rvals, rvars, ri.width, 0, rci->next - rscan, v, rordering, 0);
    2186          74 :                                                 nr = canditer_search(rci, nr + r->hseqbase, true);
    2187          74 :                                                 nr = rci->next - nr;
    2188          74 :                                                 canditer_setidx(rci, rci->next - nr);
    2189             :                                         } else {
    2190             :                                                 /* scan r for start of range */
    2191             :                                                 do {
    2192         368 :                                                         canditer_prev(rci);
    2193         368 :                                                         nr++;
    2194         283 :                                                 } while (rci->next > 0 &&
    2195         368 :                                                          cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) == 0);
    2196             :                                         }
    2197             :                                 }
    2198             :                         } else {
    2199           0 :                                 lv = canditer_search(&rrci, *(const oid *)v, true);
    2200           0 :                                 lv = canditer_search(rci, lv + r->hseqbase, true);
    2201           0 :                                 nr = (canditer_idx(rci, lv) == *(const oid*)v);
    2202           0 :                                 canditer_setidx(rci, lv);
    2203             :                         }
    2204             :                         /* rci points to first value > v
    2205             :                          * or end of r, and nr is the number of values
    2206             :                          * in r that are equal to v */
    2207             :                 }
    2208             : 
    2209      105839 :                 if (nr == 0) {
    2210             :                         /* no entries in r found */
    2211      225843 :                         if (!(nil_on_miss | only_misses)) {
    2212      200883 :                                 if (min_one) {
    2213           0 :                                         GDKerror("not enough matches");
    2214           0 :                                         goto bailout;
    2215             :                                 }
    2216      205178 :                                 if (lscan > 0 &&
    2217        4295 :                                     (equal_order ? rci->next == rci->ncand : rci->next == 0)) {
    2218             :                                         /* nothing more left to match
    2219             :                                          * in r */
    2220             :                                         break;
    2221             :                                 }
    2222      200850 :                                 canditer_setidx(lci, lci->next + nl);
    2223      200088 :                                 continue;
    2224             :                         }
    2225             :                         /* insert a nil to indicate a non-match */
    2226             :                         insert_nil = true;
    2227             :                         nr = 1;
    2228       24960 :                         if (r2) {
    2229           0 :                                 r2->tnil = true;
    2230           0 :                                 r2->tnonil = false;
    2231           0 :                                 r2->tsorted = false;
    2232           0 :                                 r2->trevsorted = false;
    2233           0 :                                 r2->tseqbase = oid_nil;
    2234           0 :                                 r2->tkey = false;
    2235             :                         }
    2236      229241 :                 } else if (nr > 1 && max_one) {
    2237          35 :                         GDKerror("more than one match");
    2238          35 :                         goto bailout;
    2239      229206 :                 } else if (only_misses) {
    2240             :                         /* we had a match, so we're not interested */
    2241       95457 :                         canditer_setidx(lci, lci->next + nl);
    2242       95635 :                         continue;
    2243             :                 } else {
    2244             :                         insert_nil = false;
    2245      133749 :                         if (semi) {
    2246             :                                 /* for semi-join, only insert single
    2247             :                                  * value */
    2248             :                                 nr = 1;
    2249             :                         }
    2250             :                 }
    2251             :                 /* make space: nl values in l match nr values in r, so
    2252             :                  * we need to add nl * nr values in the results */
    2253      158709 :                 if (maybeextend(r1, r2, nl * nr, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
    2254           0 :                         goto bailout;
    2255             : 
    2256             :                 /* maintain properties */
    2257      159012 :                 if (nl > 1) {
    2258       37967 :                         if (r2) {
    2259             :                                 /* value occurs multiple times in l,
    2260             :                                  * so entry in r will be repeated
    2261             :                                  * multiple times: hence r2 is not key
    2262             :                                  * and not dense */
    2263       14395 :                                 r2->tkey = false;
    2264       14395 :                                 r2->tseqbase = oid_nil;
    2265             :                         }
    2266             :                         /* multiple different values will be inserted
    2267             :                          * in r1 (always in order), so not reverse
    2268             :                          * ordered anymore */
    2269       37967 :                         r1->trevsorted = false;
    2270             :                 }
    2271      159012 :                 if (nr > 1) {
    2272             :                         /* value occurs multiple times in r, so entry
    2273             :                          * in l will be repeated multiple times: hence
    2274             :                          * r1 is not key and not dense */
    2275       65946 :                         r1->tkey = false;
    2276       65946 :                         if (r2) {
    2277             :                                 /* multiple different values will be
    2278             :                                  * inserted in r2 (in order), so not
    2279             :                                  * reverse ordered anymore */
    2280       65378 :                                 r2->trevsorted = false;
    2281       65378 :                                 if (nl > 1) {
    2282             :                                         /* multiple values in l match
    2283             :                                          * multiple values in r, so an
    2284             :                                          * ordered sequence will be
    2285             :                                          * inserted multiple times in
    2286             :                                          * r2, so r2 is not ordered
    2287             :                                          * anymore */
    2288        7128 :                                         r2->tsorted = false;
    2289             :                                 }
    2290             :                         }
    2291             :                 }
    2292      159012 :                 if (lscan == 0) {
    2293             :                         /* deduce relative positions of r matches for
    2294             :                          * this and previous value in v */
    2295       97328 :                         if (prev && r2) {
    2296             :                                 /* keyness or r2 can only be assured
    2297             :                                  * as long as matched values are
    2298             :                                  * ordered */
    2299       85966 :                                 int ord = rordering * cmp(prev, v ? v : nil);
    2300       86790 :                                 if (ord < 0) {
    2301             :                                         /* previous value in l was
    2302             :                                          * less than current */
    2303       29092 :                                         r2->trevsorted = false;
    2304       29092 :                                         r2->tkey &= r2->tsorted;
    2305       57698 :                                 } else if (ord > 0) {
    2306             :                                         /* previous value was
    2307             :                                          * greater */
    2308       28420 :                                         r2->tsorted = false;
    2309       28420 :                                         r2->tkey &= r2->trevsorted;
    2310             :                                 } else {
    2311             :                                         /* value can be equal if
    2312             :                                          * intervening values in l
    2313             :                                          * didn't match anything; if
    2314             :                                          * multiple values match in r,
    2315             :                                          * r2 won't be sorted */
    2316       29278 :                                         r2->tkey = false;
    2317       29278 :                                         if (nr > 1) {
    2318       29251 :                                                 r2->tsorted = false;
    2319       29251 :                                                 r2->trevsorted = false;
    2320             :                                         }
    2321             :                                 }
    2322             :                         }
    2323       98152 :                         prev = v ? v : nil;
    2324             :                 }
    2325      159836 :                 if (BATcount(r1) > 0) {
    2326             :                         /* a new, higher value will be inserted into
    2327             :                          * r1, so r1 is not reverse ordered anymore */
    2328      154602 :                         r1->trevsorted = false;
    2329      154602 :                         if (r2) {
    2330             :                                 /* depending on whether l and r are
    2331             :                                  * ordered the same or not, a new
    2332             :                                  * higher or lower value will be added
    2333             :                                  * to r2 */
    2334       86429 :                                 if (equal_order)
    2335       86276 :                                         r2->trevsorted = false;
    2336             :                                 else {
    2337         153 :                                         r2->tsorted = false;
    2338         153 :                                         r2->tseqbase = oid_nil;
    2339             :                                 }
    2340             :                         }
    2341             :                 }
    2342             : 
    2343             :                 /* insert values: first the left output */
    2344             :                 BUN nladded = 0;
    2345      400026 :                 for (i = 0; i < nl; i++) {
    2346      241746 :                         lv = canditer_next(lci);
    2347      240190 :                         if (mlci == NULL || canditer_contains(mlci, lv)) {
    2348      240190 :                                 nladded++;
    2349    30824799 :                                 for (j = 0; j < nr; j++)
    2350    30584609 :                                         APPEND(r1, lv);
    2351             :                         }
    2352             :                 }
    2353             :                 nl = nladded;
    2354             :                 /* then the right output, various different ways of
    2355             :                  * doing it */
    2356      158280 :                 if (r2 == NULL) {
    2357             :                         /* nothing to do */
    2358       86952 :                 } else if (insert_nil) {
    2359             :                         do {
    2360           0 :                                 for (i = 0; i < nr; i++) {
    2361           0 :                                         APPEND(r2, oid_nil);
    2362             :                                 }
    2363           0 :                         } while (--nl > 0);
    2364       86952 :                 } else if (equal_order) {
    2365       86650 :                         struct canditer ci = *rci; /* work on copy */
    2366       86650 :                         if (r2->batCount > 0 &&
    2367       86953 :                             BATtdense(r2) &&
    2368         790 :                             ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != canditer_idx(&ci, ci.next - nr))
    2369          77 :                                 r2->tseqbase = oid_nil;
    2370             :                         do {
    2371      119007 :                                 canditer_setidx(&ci, ci.next - nr);
    2372    30569685 :                                 for (i = 0; i < nr; i++) {
    2373    30451005 :                                         APPEND(r2, canditer_next(&ci));
    2374             :                                 }
    2375      118680 :                         } while (--nl > 0);
    2376             :                 } else {
    2377         302 :                         if (r2->batCount > 0 &&
    2378         153 :                             BATtdense(r2) &&
    2379           0 :                             ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != canditer_peek(rci))
    2380           0 :                                 r2->tseqbase = oid_nil;
    2381             :                         do {
    2382        2854 :                                 struct canditer ci = *rci; /* work on copy */
    2383        6659 :                                 for (i = 0; i < nr; i++) {
    2384        3805 :                                         APPEND(r2, canditer_next(&ci));
    2385             :                                 }
    2386        2854 :                         } while (--nl > 0);
    2387             :                 }
    2388             :         }
    2389             :         /* also set other bits of heap to correct value to indicate size */
    2390        7426 :         BATsetcount(r1, BATcount(r1));
    2391        7434 :         r1->tseqbase = oid_nil;
    2392        7434 :         if (r1->tkey)
    2393        7289 :                 r1 = virtualize(r1);
    2394        7430 :         if (r2) {
    2395        1581 :                 BATsetcount(r2, BATcount(r2));
    2396        1587 :                 assert(BATcount(r1) == BATcount(r2));
    2397        1587 :                 r2->tseqbase = oid_nil;
    2398        1587 :                 if (BATcount(r2) <= 1) {
    2399         831 :                         r2->tkey = true;
    2400         831 :                         r2 = virtualize(r2);
    2401             :                 }
    2402             :         }
    2403        7437 :         bat_iterator_end(&li);
    2404        7423 :         bat_iterator_end(&ri);
    2405        7434 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
    2406             :                   "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
    2407             :                   "sr=" ALGOOPTBATFMT ","
    2408             :                   "nil_on_miss=%s,semi=%s,only_misses=%s,not_in=%s;%s %s "
    2409             :                   "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
    2410             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    2411             :                   ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
    2412             :                   nil_on_miss ? "true" : "false",
    2413             :                   semi ? "true" : "false",
    2414             :                   only_misses ? "true" : "false",
    2415             :                   not_in ? "true" : "false",
    2416             :                   swapped ? " swapped" : "", reason,
    2417             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    2418             :                   GDKusec() - t0);
    2419             : 
    2420             :         return GDK_SUCCEED;
    2421             : 
    2422          35 :   bailout:
    2423          35 :         bat_iterator_end(&li);
    2424          35 :         bat_iterator_end(&ri);
    2425          35 :         BBPreclaim(r1);
    2426          35 :         BBPreclaim(r2);
    2427          35 :         return GDK_FAIL;
    2428             : }
    2429             : 
    2430             : #define HASHLOOPBODY()                                                  \
    2431             :         do {                                                            \
    2432             :                 if (nr >= 1 && max_one) {                            \
    2433             :                         GDKerror("more than one match");              \
    2434             :                         goto bailout;                                   \
    2435             :                 }                                                       \
    2436             :                 if (maybeextend(r1, r2, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
    2437             :                         goto bailout;                                   \
    2438             :                 APPEND(r1, lo);                                         \
    2439             :                 if (r2)                                                 \
    2440             :                         APPEND(r2, ro);                                 \
    2441             :                 nr++;                                                   \
    2442             :         } while (false)
    2443             : 
    2444             : #define EQ_int(a, b)    ((a) == (b))
    2445             : #define EQ_lng(a, b)    ((a) == (b))
    2446             : #ifdef HAVE_HGE
    2447             : #define EQ_uuid(a, b)   ((a).h == (b).h)
    2448             : #else
    2449             : #define EQ_uuid(a, b)   (memcmp((a).u, (b).u, UUID_SIZE) == 0)
    2450             : #endif
    2451             : 
    2452             : #define HASHJOIN(TYPE)                                                  \
    2453             :         do {                                                            \
    2454             :                 TYPE *rvals = ri.base;                                  \
    2455             :                 TYPE *lvals = li.base;                                  \
    2456             :                 TYPE v;                                                 \
    2457             :                 while (lci->next < lci->ncand) {                       \
    2458             :                         lo = canditer_next(lci);                        \
    2459             :                         v = lvals[lo - l->hseqbase];                 \
    2460             :                         nr = 0;                                         \
    2461             :                         if ((!nil_matches || not_in) && is_##TYPE##_nil(v)) { \
    2462             :                                 /* no match */                          \
    2463             :                                 if (not_in) {                           \
    2464             :                                         lskipped = BATcount(r1) > 0; \
    2465             :                                         continue;                       \
    2466             :                                 }                                       \
    2467             :                         } else if (hash_cand) {                         \
    2468             :                                 /* private hash: no locks */            \
    2469             :                                 for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
    2470             :                                      rb != BUN_NONE;                    \
    2471             :                                      rb = HASHgetlink(hsh, rb)) {       \
    2472             :                                         ro = canditer_idx(rci, rb);     \
    2473             :                                         if (!EQ_##TYPE(v, rvals[ro - r->hseqbase])) \
    2474             :                                                 continue;               \
    2475             :                                         if (only_misses) {              \
    2476             :                                                 nr++;                   \
    2477             :                                                 break;                  \
    2478             :                                         }                               \
    2479             :                                         HASHLOOPBODY();                 \
    2480             :                                         if (semi && !max_one)           \
    2481             :                                                 break;                  \
    2482             :                                 }                                       \
    2483             :                         } else if (rci->tpe != cand_dense) {         \
    2484             :                                 for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
    2485             :                                      rb != BUN_NONE;                    \
    2486             :                                      rb = HASHgetlink(hsh, rb)) {       \
    2487             :                                         if (rb >= rl && rb < rh &&        \
    2488             :                                             EQ_##TYPE(v, rvals[rb]) &&  \
    2489             :                                             canditer_contains(rci, ro = (oid) (rb - roff + rseq))) { \
    2490             :                                                 if (only_misses) {      \
    2491             :                                                         nr++;           \
    2492             :                                                         break;          \
    2493             :                                                 }                       \
    2494             :                                                 HASHLOOPBODY();         \
    2495             :                                                 if (semi && !max_one)   \
    2496             :                                                         break;          \
    2497             :                                         }                               \
    2498             :                                 }                                       \
    2499             :                         } else {                                        \
    2500             :                                 for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
    2501             :                                      rb != BUN_NONE;                    \
    2502             :                                      rb = HASHgetlink(hsh, rb)) {       \
    2503             :                                         if (rb >= rl && rb < rh &&        \
    2504             :                                             EQ_##TYPE(v, rvals[rb])) {  \
    2505             :                                                 if (only_misses) {      \
    2506             :                                                         nr++;           \
    2507             :                                                         break;          \
    2508             :                                                 }                       \
    2509             :                                                 ro = (oid) (rb - roff + rseq); \
    2510             :                                                 HASHLOOPBODY();         \
    2511             :                                                 if (semi && !max_one)   \
    2512             :                                                         break;          \
    2513             :                                         }                               \
    2514             :                                 }                                       \
    2515             :                         }                                               \
    2516             :                         if (nr == 0) {                                  \
    2517             :                                 if (only_misses) {                      \
    2518             :                                         nr = 1;                         \
    2519             :                                         if (maybeextend(r1, r2, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
    2520             :                                                 goto bailout;           \
    2521             :                                         APPEND(r1, lo);                 \
    2522             :                                         if (lskipped)                   \
    2523             :                                                 r1->tseqbase = oid_nil;      \
    2524             :                                 } else if (nil_on_miss) {               \
    2525             :                                         nr = 1;                         \
    2526             :                                         r2->tnil = true;             \
    2527             :                                         r2->tnonil = false;          \
    2528             :                                         r2->tkey = false;            \
    2529             :                                         if (maybeextend(r1, r2, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
    2530             :                                                 goto bailout;           \
    2531             :                                         APPEND(r1, lo);                 \
    2532             :                                         APPEND(r2, oid_nil);            \
    2533             :                                 } else if (min_one) {                   \
    2534             :                                         GDKerror("not enough matches");       \
    2535             :                                         goto bailout;                   \
    2536             :                                 } else {                                \
    2537             :                                         lskipped = BATcount(r1) > 0; \
    2538             :                                 }                                       \
    2539             :                         } else if (only_misses) {                       \
    2540             :                                 lskipped = BATcount(r1) > 0;         \
    2541             :                         } else {                                        \
    2542             :                                 if (lskipped) {                         \
    2543             :                                         /* note, we only get here in an \
    2544             :                                          * iteration *after* lskipped was \
    2545             :                                          * first set to true, i.e. we did \
    2546             :                                          * indeed skip values in l */   \
    2547             :                                         r1->tseqbase = oid_nil;              \
    2548             :                                 }                                       \
    2549             :                                 if (nr > 1) {                                \
    2550             :                                         r1->tkey = false;            \
    2551             :                                         r1->tseqbase = oid_nil;              \
    2552             :                                 }                                       \
    2553             :                         }                                               \
    2554             :                         if (nr > 0 && BATcount(r1) > nr)          \
    2555             :                                 r1->trevsorted = false;                      \
    2556             :                 }                                                       \
    2557             :         } while (0)
    2558             : 
    2559             : /* Implementation of join using a hash lookup of values in the right
    2560             :  * column. */
    2561             : static gdk_return
    2562       14787 : hashjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
    2563             :          struct canditer *restrict lci, struct canditer *restrict rci,
    2564             :          bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
    2565             :          bool not_in, bool max_one, bool min_one,
    2566             :          BUN estimate, lng t0, bool swapped,
    2567             :          bool hash, bool phash, bool hash_cand,
    2568             :          const char *reason)
    2569             : {
    2570             :         oid lo, ro;
    2571             :         BATiter li, ri;
    2572             :         BUN rb, roff = 0;
    2573             :         /* rl, rh: lower and higher bounds for BUN values in hash table */
    2574             :         BUN rl, rh;
    2575             :         oid rseq;
    2576             :         BUN nr;
    2577             :         const char *lvals;
    2578             :         const char *lvars;
    2579       14787 :         const void *nil = ATOMnilptr(l->ttype);
    2580       14787 :         int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
    2581       14787 :         oid lval = oid_nil;     /* hold value if l is dense */
    2582             :         const char *v = (const char *) &lval;
    2583             :         bool lskipped = false;  /* whether we skipped values in l */
    2584             :         Hash *restrict hsh = NULL;
    2585             :         bool locked = false;
    2586             : 
    2587       44199 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    2588             : 
    2589       14787 :         li = bat_iterator(l);
    2590       14845 :         ri = bat_iterator(r);
    2591             : 
    2592       14839 :         int t = ATOMbasetype(r->ttype);
    2593       14839 :         if (BATtvoid(r) || BATtvoid(l))
    2594             :                 t = TYPE_void;
    2595             : 
    2596       14839 :         lvals = (const char *) li.base;
    2597       14839 :         if (l->tvarsized && l->ttype) {
    2598        1487 :                 assert(r->tvarsized && r->ttype);
    2599        1487 :                 lvars = li.vh->base;
    2600             :         } else {
    2601       13352 :                 assert(!r->tvarsized || !r->ttype);
    2602             :                 lvars = NULL;
    2603             :         }
    2604             :         /* offset to convert BUN to OID for value in right column */
    2605       14839 :         rseq = r->hseqbase;
    2606             : 
    2607       14839 :         if (lci->ncand == 0 || rci->ncand== 0) {
    2608           0 :                 bat_iterator_end(&li);
    2609           0 :                 bat_iterator_end(&ri);
    2610           0 :                 return nomatch(r1p, r2p, l, r, lci,
    2611             :                                nil_on_miss, only_misses, __func__, t0);
    2612             :         }
    2613             : 
    2614       14843 :         BUN maxsize = joininitresults(r1p, r2p, lci->ncand, rci->ncand,
    2615       14843 :                                       l->tkey, r->tkey, semi | max_one,
    2616             :                                       nil_on_miss, only_misses, min_one,
    2617             :                                       estimate);
    2618       14766 :         if (maxsize == BUN_NONE) {
    2619           0 :                 bat_iterator_end(&li);
    2620           0 :                 bat_iterator_end(&ri);
    2621           0 :                 return GDK_FAIL;
    2622             :         }
    2623             : 
    2624       14766 :         BAT *r1 = *r1p;
    2625       14766 :         BAT *r2 = r2p ? *r2p : NULL;
    2626             : 
    2627       14766 :         rl = rci->seq - r->hseqbase;
    2628       14766 :         rh = canditer_last(rci) + 1 - r->hseqbase;
    2629       14691 :         if (hash_cand) {
    2630             :                 /* we need to create a hash on r specific for the
    2631             :                  * candidate list */
    2632             :                 char ext[32];
    2633          60 :                 assert(rci->s);
    2634         108 :                 MT_thread_setalgorithm(swapped ? "hashjoin using candidate hash (swapped)" : "hashjoin using candidate hash");
    2635          60 :                 TRC_DEBUG(ALGO, ALGOBATFMT ": creating "
    2636             :                           "hash for candidate list " ALGOBATFMT "%s%s\n",
    2637             :                           ALGOBATPAR(r), ALGOBATPAR(rci->s),
    2638             :                           r->thash ? " ignoring existing hash" : "",
    2639             :                           swapped ? " (swapped)" : "");
    2640          60 :                 if (snprintf(ext, sizeof(ext), "thshjn%x",
    2641          60 :                              (unsigned) THRgettid()) >= (int) sizeof(ext))
    2642           0 :                         goto bailout;
    2643          60 :                 if ((hsh = BAThash_impl(r, rci, ext)) == NULL) {
    2644           0 :                         goto bailout;
    2645             :                 }
    2646       14631 :         } else if (phash) {
    2647             :                 /* there is a hash on the parent which we should use */
    2648        3085 :                 MT_thread_setalgorithm(swapped ? "hashjoin using parent hash (swapped)" : "hashjoin using parent hash");
    2649        2487 :                 BAT *b = BBP_cache(VIEWtparent(r));
    2650        2487 :                 TRC_DEBUG(ALGO, "%s(%s): using "
    2651             :                           "parent(" ALGOBATFMT ") for hash%s\n",
    2652             :                           __func__,
    2653             :                           BATgetId(r), ALGOBATPAR(b),
    2654             :                           swapped ? " (swapped)" : "");
    2655        2487 :                 roff = r->tbaseoff - b->tbaseoff;
    2656        2487 :                 rl += roff;
    2657        2487 :                 rh += roff;
    2658             :                 r = b;
    2659        2487 :                 bat_iterator_end(&ri);
    2660        2527 :                 ri = bat_iterator(r);
    2661        2550 :                 MT_rwlock_rdlock(&r->thashlock);
    2662        2550 :                 hsh = r->thash;
    2663             :                 locked = true;
    2664       12148 :         } else if (hash) {
    2665             :                 /* there is a hash on r which we should use */
    2666        9228 :                 MT_thread_setalgorithm(swapped ? "hashjoin using existing hash (swapped)" : "hashjoin using existing hash");
    2667        5491 :                 MT_rwlock_rdlock(&r->thashlock);
    2668        5495 :                 hsh = r->thash;
    2669             :                 locked = true;
    2670        5495 :                 TRC_DEBUG(ALGO, ALGOBATFMT ": using "
    2671             :                           "existing hash%s\n",
    2672             :                           ALGOBATPAR(r),
    2673             :                           swapped ? " (swapped)" : "");
    2674        6679 :         } else if (BATtdense(r)) {
    2675             :                 /* no hash, just dense lookup */
    2676           1 :                 MT_thread_setalgorithm(swapped ? "hashjoin on dense (swapped)" : "hashjoin on dense");
    2677             :         } else {
    2678             :                 /* we need to create a hash on r */
    2679        9512 :                 MT_thread_setalgorithm(swapped ? "hashjoin using new hash (swapped)" : "hashjoin using new hash");
    2680        6723 :                 TRC_DEBUG(ALGO, ALGOBATFMT ": creating hash%s\n",
    2681             :                           ALGOBATPAR(r),
    2682             :                           swapped ? " (swapped)" : "");
    2683        6723 :                 if (BAThash(r) != GDK_SUCCEED)
    2684           0 :                         goto bailout;
    2685        6671 :                 MT_rwlock_rdlock(&r->thashlock);
    2686        6741 :                 hsh = r->thash;
    2687             :                 locked = true;
    2688             :         }
    2689       14847 :         if (locked && hsh == NULL) {
    2690           0 :                 GDKerror("Hash disappeared for "ALGOBATFMT"\n", ALGOBATPAR(r));
    2691           0 :                 goto bailout;
    2692             :         }
    2693       14847 :         assert(hsh != NULL || BATtdense(r));
    2694       14847 :         if (hsh) {
    2695       14846 :                 TRC_DEBUG(ALGO, "hash for " ALGOBATFMT ": nbucket " BUNFMT ", nunique " BUNFMT ", nheads " BUNFMT "\n", ALGOBATPAR(r), hsh->nbucket, hsh->nunique, hsh->nheads);
    2696             :         }
    2697             : 
    2698       14750 :         if (not_in && !r->tnonil) {
    2699             :                 /* check whether there is a nil on the right, since if
    2700             :                  * so, we should return an empty result */
    2701         472 :                 if (hash_cand) {
    2702           0 :                         for (rb = HASHget(hsh, HASHprobe(hsh, nil));
    2703             :                              rb != BUN_NONE;
    2704           0 :                              rb = HASHgetlink(hsh, rb)) {
    2705           0 :                                 ro = canditer_idx(rci, rb);
    2706           0 :                                 if ((*cmp)(nil, BUNtail(ri, ro - r->hseqbase)) == 0) {
    2707           0 :                                         assert(!locked);
    2708           0 :                                         HEAPfree(&hsh->heaplink, true);
    2709           0 :                                         HEAPfree(&hsh->heapbckt, true);
    2710           0 :                                         GDKfree(hsh);
    2711           0 :                                         bat_iterator_end(&li);
    2712           0 :                                         bat_iterator_end(&ri);
    2713           0 :                                         return nomatch(r1p, r2p, l, r, lci,
    2714             :                                                        false, false, __func__, t0);
    2715             :                                 }
    2716             :                         }
    2717         472 :                 } else if (!BATtdense(r)) {
    2718         605 :                         for (rb = HASHget(hsh, HASHprobe(hsh, nil));
    2719             :                              rb != BUN_NONE;
    2720         133 :                              rb = HASHgetlink(hsh, rb)) {
    2721         136 :                                 if (rb >= rl && rb < rh &&
    2722         132 :                                     (cmp == NULL ||
    2723         134 :                                      (*cmp)(nil, BUNtail(ri, rb)) == 0)) {
    2724           1 :                                         if (locked)
    2725           1 :                                                 MT_rwlock_rdunlock(&r->thashlock);
    2726           1 :                                         bat_iterator_end(&li);
    2727           1 :                                         bat_iterator_end(&ri);
    2728           1 :                                         return nomatch(r1p, r2p, l, r, lci,
    2729             :                                                        false, false,
    2730             :                                                        __func__, t0);
    2731             :                                 }
    2732             :                         }
    2733             :                 }
    2734             :         }
    2735             : 
    2736             :         /* basic properties will be adjusted if necessary later on,
    2737             :          * they were initially set by joininitresults() */
    2738             : 
    2739       14746 :         if (r2) {
    2740       12760 :                 r2->tkey = l->tkey;
    2741             :                 /* r2 is not likely to be sorted (although it is
    2742             :                  * certainly possible) */
    2743       12760 :                 r2->tsorted = false;
    2744       12760 :                 r2->trevsorted = false;
    2745       12760 :                 r2->tseqbase = oid_nil;
    2746             :         }
    2747             : 
    2748       14746 :         if (lci->tpe != cand_dense)
    2749         248 :                 r1->tseqbase = oid_nil;
    2750             : 
    2751       14746 :         switch (t) {
    2752       10483 :         case TYPE_int:
    2753   300810351 :                 HASHJOIN(int);
    2754             :                 break;
    2755        2230 :         case TYPE_lng:
    2756    88659336 :                 HASHJOIN(lng);
    2757             :                 break;
    2758           0 :         case TYPE_uuid:
    2759           0 :                 HASHJOIN(uuid);
    2760             :                 break;
    2761             :         default:
    2762     2950607 :                 while (lci->next < lci->ncand) {
    2763     2948568 :                         lo = canditer_next(lci);
    2764     2967577 :                         if (BATtdense(l))
    2765         133 :                                 lval = lo - l->hseqbase + l->tseqbase;
    2766     2967444 :                         else if (l->ttype != TYPE_void)
    2767     2958395 :                                 v = VALUE(l, lo - l->hseqbase);
    2768             :                         nr = 0;
    2769     2967577 :                         if ((!nil_matches || not_in) && cmp(v, nil) == 0) {
    2770             :                                 /* no match */
    2771        2832 :                                 if (not_in) {
    2772          10 :                                         lskipped = BATcount(r1) > 0;
    2773          10 :                                         continue;
    2774             :                                 }
    2775     2965331 :                         } else if (hash_cand) {
    2776           0 :                                 for (rb = HASHget(hsh, HASHprobe(hsh, v));
    2777             :                                      rb != BUN_NONE;
    2778           0 :                                      rb = HASHgetlink(hsh, rb)) {
    2779           0 :                                         ro = canditer_idx(rci, rb);
    2780           0 :                                         if ((*cmp)(v, BUNtail(ri, ro - r->hseqbase)) != 0)
    2781           0 :                                                 continue;
    2782           0 :                                         if (only_misses) {
    2783           0 :                                                 nr++;
    2784           0 :                                                 break;
    2785             :                                         }
    2786           0 :                                         HASHLOOPBODY();
    2787           0 :                                         if (semi && !max_one)
    2788             :                                                 break;
    2789             :                                 }
    2790     2965331 :                         } else if (hsh == NULL) {
    2791           4 :                                 assert(BATtdense(r));
    2792           4 :                                 ro = *(const oid *) v;
    2793           4 :                                 if (ro >= r->tseqbase &&
    2794           4 :                                     ro < r->tseqbase + r->batCount) {
    2795           4 :                                         ro -= r->tseqbase;
    2796           4 :                                         ro += rseq;
    2797           4 :                                         if (canditer_contains(rci, ro)) {
    2798           4 :                                                 if (only_misses) {
    2799             :                                                         nr++;
    2800             :                                                         break;
    2801             :                                                 }
    2802           4 :                                                 HASHLOOPBODY();
    2803           4 :                                                 if (semi && !max_one)
    2804             :                                                         break;
    2805             :                                         }
    2806             :                                 }
    2807     2965327 :                         } else if (rci->tpe != cand_dense) {
    2808       24189 :                                 for (rb = HASHget(hsh, HASHprobe(hsh, v));
    2809             :                                      rb != BUN_NONE;
    2810        8058 :                                      rb = HASHgetlink(hsh, rb)) {
    2811       16075 :                                         if (rb >= rl && rb < rh &&
    2812        8489 :                                             (*(cmp))(v, BUNtail(ri, rb)) == 0 &&
    2813         472 :                                             canditer_contains(rci, ro = (oid) (rb - roff + rseq))) {
    2814         394 :                                                 if (only_misses) {
    2815           0 :                                                         nr++;
    2816           0 :                                                         break;
    2817             :                                                 }
    2818         394 :                                                 HASHLOOPBODY();
    2819         394 :                                                 if (semi && !max_one)
    2820             :                                                         break;
    2821             :                                         }
    2822             :                                 }
    2823             :                         } else {
    2824     5633368 :                                 for (rb = HASHget(hsh, HASHprobe(hsh, v));
    2825             :                                      rb != BUN_NONE;
    2826     2684172 :                                      rb = HASHgetlink(hsh, rb)) {
    2827     5830707 :                                         if (rb >= rl && rb < rh &&
    2828     3017068 :                                             (*(cmp))(v, BUNtail(ri, rb)) == 0) {
    2829     2597368 :                                                 if (only_misses) {
    2830       71947 :                                                         nr++;
    2831       71947 :                                                         break;
    2832             :                                                 }
    2833     2525421 :                                                 ro = (oid) (rb - roff + rseq);
    2834     2525421 :                                                 HASHLOOPBODY();
    2835     2468363 :                                                 if (semi && !max_one)
    2836             :                                                         break;
    2837             :                                         }
    2838             :                                 }
    2839             :                         }
    2840     2945738 :                         if (nr == 0) {
    2841      419591 :                                 if (only_misses) {
    2842             :                                         nr = 1;
    2843         244 :                                         if (maybeextend(r1, r2, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
    2844           0 :                                                 goto bailout;
    2845         244 :                                         APPEND(r1, lo);
    2846         244 :                                         if (lskipped)
    2847         210 :                                                 r1->tseqbase = oid_nil;
    2848      419347 :                                 } else if (nil_on_miss) {
    2849             :                                         nr = 1;
    2850           0 :                                         r2->tnil = true;
    2851           0 :                                         r2->tnonil = false;
    2852           0 :                                         r2->tkey = false;
    2853           0 :                                         if (maybeextend(r1, r2, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
    2854           0 :                                                 goto bailout;
    2855           0 :                                         APPEND(r1, lo);
    2856           0 :                                         APPEND(r2, oid_nil);
    2857      419347 :                                 } else if (min_one) {
    2858           0 :                                         GDKerror("not enough matches");
    2859           0 :                                         goto bailout;
    2860             :                                 } else {
    2861      419347 :                                         lskipped = BATcount(r1) > 0;
    2862             :                                 }
    2863     2528973 :                         } else if (only_misses) {
    2864       71904 :                                 lskipped = BATcount(r1) > 0;
    2865             :                         } else {
    2866     2457069 :                                 if (lskipped) {
    2867             :                                         /* note, we only get here in an
    2868             :                                          * iteration *after* lskipped was
    2869             :                                          * first set to true, i.e. we did
    2870             :                                          * indeed skip values in l */
    2871     2306727 :                                         r1->tseqbase = oid_nil;
    2872             :                                 }
    2873     2457069 :                                 if (nr > 1) {
    2874        4753 :                                         r1->tkey = false;
    2875        4753 :                                         r1->tseqbase = oid_nil;
    2876             :                                 }
    2877             :                         }
    2878     2948564 :                         if (nr > 0 && BATcount(r1) > nr)
    2879     2466480 :                                 r1->trevsorted = false;
    2880             :                 }
    2881             :                 break;
    2882             :         }
    2883       14798 :         if (locked) {
    2884             :                 locked = false;
    2885       14707 :                 MT_rwlock_rdunlock(&r->thashlock);
    2886             :         }
    2887       14868 :         bat_iterator_end(&li);
    2888       14834 :         bat_iterator_end(&ri);
    2889             : 
    2890       14833 :         if (hash_cand) {
    2891          60 :                 HEAPfree(&hsh->heaplink, true);
    2892          60 :                 HEAPfree(&hsh->heapbckt, true);
    2893          60 :                 GDKfree(hsh);
    2894             :         }
    2895             :         /* also set other bits of heap to correct value to indicate size */
    2896       14833 :         BATsetcount(r1, BATcount(r1));
    2897       14769 :         if (BATcount(r1) <= 1) {
    2898        5837 :                 r1->tsorted = true;
    2899        5837 :                 r1->trevsorted = true;
    2900        5837 :                 r1->tkey = true;
    2901        5837 :                 r1->tseqbase = 0;
    2902             :         }
    2903       14769 :         if (r2) {
    2904       12812 :                 BATsetcount(r2, BATcount(r2));
    2905       12821 :                 assert(BATcount(r1) == BATcount(r2));
    2906       12821 :                 if (BATcount(r2) <= 1) {
    2907        5063 :                         r2->tsorted = true;
    2908        5063 :                         r2->trevsorted = true;
    2909        5063 :                         r2->tkey = true;
    2910        5063 :                         r2->tseqbase = 0;
    2911             :                 }
    2912             :         }
    2913       14778 :         if (BATcount(r1) > 0) {
    2914       10162 :                 if (BATtdense(r1))
    2915        5376 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    2916       10162 :                 if (r2 && BATtdense(r2))
    2917        1157 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    2918             :         } else {
    2919        4616 :                 r1->tseqbase = 0;
    2920        4616 :                 if (r2) {
    2921        3869 :                         r2->tseqbase = 0;
    2922             :                 }
    2923             :         }
    2924       14778 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
    2925             :                   ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
    2926             :                   "nil_matches=%s,nil_on_miss=%s,semi=%s,only_misses=%s,"
    2927             :                   "not_in=%s,max_one=%s,min_one=%s;%s %s -> " ALGOBATFMT "," ALGOOPTBATFMT
    2928             :                   " (" LLFMT "usec)\n",
    2929             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    2930             :                   ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
    2931             :                   nil_matches ? "true" : "false",
    2932             :                   nil_on_miss ? "true" : "false",
    2933             :                   semi ? "true" : "false",
    2934             :                   only_misses ? "true" : "false",
    2935             :                   not_in ? "true" : "false",
    2936             :                   max_one ? "true" : "false",
    2937             :                   min_one ? "true" : "false",
    2938             :                   swapped ? " swapped" : "", reason,
    2939             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    2940             :                   GDKusec() - t0);
    2941             : 
    2942             :         return GDK_SUCCEED;
    2943             : 
    2944           6 :   bailout:
    2945           6 :         bat_iterator_end(&li);
    2946           6 :         bat_iterator_end(&ri);
    2947           6 :         if (locked)
    2948           6 :                 MT_rwlock_rdunlock(&r->thashlock);
    2949           6 :         if (hash_cand && hsh) {
    2950           0 :                 HEAPfree(&hsh->heaplink, true);
    2951           0 :                 HEAPfree(&hsh->heapbckt, true);
    2952           0 :                 GDKfree(hsh);
    2953             :         }
    2954           6 :         BBPreclaim(r1);
    2955           6 :         BBPreclaim(r2);
    2956           6 :         return GDK_FAIL;
    2957             : }
    2958             : 
    2959             : /* Count the number of unique values for the first half and the complete
    2960             :  * set (the sample s of b) and return the two values in *cnt1 and
    2961             :  * *cnt2. In case of error, both values are 0. */
    2962             : static void
    2963       14357 : count_unique(BAT *b, BAT *s, BUN *cnt1, BUN *cnt2)
    2964             : {
    2965             :         struct canditer ci;
    2966             :         BUN half;
    2967             :         BUN cnt = 0;
    2968             :         const void *v;
    2969             :         const char *bvals;
    2970             :         const char *bvars;
    2971             :         oid bval;
    2972             :         oid i, o;
    2973             :         const char *nme;
    2974             :         BUN hb;
    2975             :         BATiter bi;
    2976             :         int (*cmp)(const void *, const void *);
    2977             :         const char *algomsg = "";
    2978             :         lng t0 = 0;
    2979             : 
    2980       14357 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    2981       14357 :         canditer_init(&ci, b, s);
    2982       14362 :         half = ci.ncand / 2;
    2983             : 
    2984       14362 :         if (b->tkey || ci.ncand <= 1 || BATtdense(b)) {
    2985             :                 /* trivial: already unique */
    2986          70 :                 *cnt1 = half;
    2987          70 :                 *cnt2 = ci.ncand;
    2988          70 :                 return;
    2989             :         }
    2990             : 
    2991       14292 :         if ((BATordered(b) && BATordered_rev(b)) ||
    2992       14317 :             (b->ttype == TYPE_void && is_oid_nil(b->tseqbase))) {
    2993             :                 /* trivial: all values are the same */
    2994           0 :                 *cnt1 = *cnt2 = 1;
    2995           0 :                 return;
    2996             :         }
    2997             : 
    2998       14317 :         assert(b->ttype != TYPE_void);
    2999             : 
    3000       14317 :         bi = bat_iterator(b);
    3001       14469 :         bvals = bi.base;
    3002       14469 :         if (b->tvarsized && b->ttype)
    3003        1226 :                 bvars = bi.vh->base;
    3004             :         else
    3005             :                 bvars = NULL;
    3006       14469 :         cmp = ATOMcompare(b->ttype);
    3007             : 
    3008       14469 :         *cnt1 = *cnt2 = 0;
    3009             : 
    3010       14469 :         if (BATordered(b) || BATordered_rev(b)) {
    3011             :                 const void *prev = NULL;
    3012             :                 algomsg = "sorted";
    3013       98614 :                 for (i = 0; i < ci.ncand; i++) {
    3014       98077 :                         if (i == half)
    3015         537 :                                 *cnt1 = cnt;
    3016       98077 :                         o = canditer_next(&ci);
    3017       98065 :                         v = VALUE(b, o - b->hseqbase);
    3018       98065 :                         if (prev == NULL || (*cmp)(v, prev) != 0) {
    3019       43533 :                                 cnt++;
    3020             :                         }
    3021             :                         prev = v;
    3022             :                 }
    3023         537 :                 *cnt2 = cnt;
    3024       13840 :         } else if (ATOMbasetype(b->ttype) == TYPE_bte) {
    3025             :                 unsigned char val;
    3026             :                 uint32_t seen[256 / 32];
    3027             : 
    3028             :                 algomsg = "byte-sized atoms";
    3029          31 :                 assert(bvars == NULL);
    3030          31 :                 memset(seen, 0, sizeof(seen));
    3031        1418 :                 for (i = 0; i < ci.ncand; i++) {
    3032        1386 :                         if (i == ci.ncand/ 2) {
    3033             :                                 cnt = 0;
    3034         280 :                                 for (int j = 0; j < 256 / 32; j++)
    3035         248 :                                         cnt += candmask_pop(seen[j]);
    3036          32 :                                 *cnt1 = cnt;
    3037             :                         }
    3038        1386 :                         o = canditer_next(&ci);
    3039        1387 :                         val = ((const unsigned char *) bvals)[o - b->hseqbase];
    3040        1387 :                         if (!(seen[val >> 5] & (1U << (val & 0x1F)))) {
    3041         171 :                                 seen[val >> 5] |= 1U << (val & 0x1F);
    3042             :                         }
    3043             :                 }
    3044             :                 cnt = 0;
    3045         280 :                 for (int j = 0; j < 256 / 32; j++)
    3046         248 :                         cnt += candmask_pop(seen[j]);
    3047          32 :                 *cnt2 = cnt;
    3048       13809 :         } else if (ATOMbasetype(b->ttype) == TYPE_sht) {
    3049             :                 unsigned short val;
    3050             :                 uint32_t *seen = NULL;
    3051             : 
    3052             :                 algomsg = "short-sized atoms";
    3053         456 :                 assert(bvars == NULL);
    3054         456 :                 seen = GDKzalloc((65536 / 32) * sizeof(seen[0]));
    3055         458 :                 if (seen == NULL) {
    3056           0 :                         bat_iterator_end(&bi);
    3057           0 :                         return;
    3058             :                 }
    3059       73854 :                 for (i = 0; i < ci.ncand; i++) {
    3060       73396 :                         if (i == half) {
    3061             :                                 cnt = 0;
    3062      860619 :                                 for (int j = 0; j < 65536 / 32; j++)
    3063      860160 :                                         cnt += candmask_pop(seen[j]);
    3064         459 :                                 *cnt1 = cnt;
    3065             :                         }
    3066       73396 :                         o = canditer_next(&ci);
    3067       73396 :                         val = ((const unsigned short *) bvals)[o - b->hseqbase];
    3068       73396 :                         if (!(seen[val >> 5] & (1U << (val & 0x1F)))) {
    3069        1280 :                                 seen[val >> 5] |= 1U << (val & 0x1F);
    3070             :                         }
    3071             :                 }
    3072             :                 cnt = 0;
    3073      864714 :                 for (int j = 0; j < 65536 / 32; j++)
    3074      864256 :                         cnt += candmask_pop(seen[j]);
    3075         458 :                 *cnt2 = cnt;
    3076         458 :                 GDKfree(seen);
    3077             :                 seen = NULL;
    3078             :         } else {
    3079             :                 BUN prb;
    3080             :                 BUN p;
    3081             :                 BUN mask;
    3082       13353 :                 Hash hs = {0};
    3083             : 
    3084       13353 :                 GDKclrerr();    /* not interested in BAThash errors */
    3085             :                 algomsg = "new partial hash";
    3086       13365 :                 nme = BBP_physical(b->batCacheid);
    3087       13365 :                 mask = HASHmask(ci.ncand);
    3088             :                 if (mask < ((BUN) 1 << 16))
    3089             :                         mask = (BUN) 1 << 16;
    3090       13365 :                 if ((hs.heaplink.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0 ||
    3091       13366 :                     (hs.heapbckt.farmid = BBPselectfarm(TRANSIENT, b->ttype, hashheap)) < 0 ||
    3092       13383 :                     snprintf(hs.heaplink.filename, sizeof(hs.heaplink.filename), "%s.thshunil%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs.heaplink.filename) ||
    3093       26774 :                     snprintf(hs.heapbckt.filename, sizeof(hs.heapbckt.filename), "%s.thshunib%x", nme, (unsigned) THRgettid()) >= (int) sizeof(hs.heapbckt.filename) ||
    3094       13378 :                     HASHnew(&hs, b->ttype, BUNlast(b), mask, BUN_NONE, false) != GDK_SUCCEED) {
    3095           0 :                         GDKerror("cannot allocate hash table\n");
    3096           0 :                         HEAPfree(&hs.heaplink, true);
    3097           0 :                         HEAPfree(&hs.heapbckt, true);
    3098           0 :                         bat_iterator_end(&bi);
    3099           0 :                         return;
    3100             :                 }
    3101     3088602 :                 for (i = 0; i < ci.ncand; i++) {
    3102     3075175 :                         if (i == half)
    3103       13434 :                                 *cnt1 = cnt;
    3104     3075175 :                         o = canditer_next(&ci);
    3105     3068579 :                         v = VALUE(b, o - b->hseqbase);
    3106     3068579 :                         prb = HASHprobe(&hs, v);
    3107     3176736 :                         for (hb = HASHget(&hs, prb);
    3108             :                              hb != BUN_NONE;
    3109       88401 :                              hb = HASHgetlink(&hs, hb)) {
    3110     1152453 :                                 if (cmp(v, BUNtail(bi, hb)) == 0)
    3111             :                                         break;
    3112             :                         }
    3113     3094400 :                         if (hb == BUN_NONE) {
    3114     2021102 :                                 p = o - b->hseqbase;
    3115     2021102 :                                 cnt++;
    3116             :                                 /* enter into hash table */
    3117     2021102 :                                 HASHputlink(&hs, p, HASHget(&hs, prb));
    3118     2007416 :                                 HASHput(&hs, prb, p);
    3119             :                         }
    3120             :                 }
    3121       13427 :                 *cnt2 = cnt;
    3122       13427 :                 HEAPfree(&hs.heaplink, true);
    3123       13438 :                 HEAPfree(&hs.heapbckt, true);
    3124             :         }
    3125       14472 :         bat_iterator_end(&bi);
    3126             : 
    3127       14444 :         TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
    3128             :                   " -> " BUNFMT " " BUNFMT " (%s -- " LLFMT "usec)\n",
    3129             :                   ALGOBATPAR(b), ALGOOPTBATPAR(s),
    3130             :                   *cnt1, *cnt2, algomsg, GDKusec() - t0);
    3131             : 
    3132             :         return;
    3133             : }
    3134             : 
    3135             : static double
    3136       20377 : guess_uniques(BAT *b, struct canditer *ci)
    3137             : {
    3138             :         BUN cnt1, cnt2;
    3139             :         BAT *s1;
    3140             : 
    3141       20377 :         if (b->tkey)
    3142        4936 :                 return (double) ci->ncand;
    3143             : 
    3144       15441 :         if (ci->s == NULL ||
    3145       14403 :             (ci->tpe == cand_dense && ci->ncand == BATcount(b))) {
    3146       15298 :                 const ValRecord *p = BATgetprop(b, GDK_UNIQUE_ESTIMATE);
    3147       15326 :                 if (p) {
    3148         944 :                         TRC_DEBUG(ALGO, "b=" ALGOBATFMT " use cached value\n",
    3149             :                                   ALGOBATPAR(b));
    3150         943 :                         return p->val.dval;
    3151             :                 }
    3152       14382 :                 s1 = BATsample_with_seed(b, 1000, (uint64_t) GDKusec() * (uint64_t) b->batCacheid);
    3153             :         } else {
    3154         143 :                 BAT *s2 = BATsample_with_seed(ci->s, 1000, (uint64_t) GDKusec() * (uint64_t) b->batCacheid);
    3155         143 :                 s1 = BATproject(s2, ci->s);
    3156         143 :                 BBPreclaim(s2);
    3157             :         }
    3158       14403 :         BUN n2 = BATcount(s1);
    3159       14403 :         BUN n1 = n2 / 2;
    3160       14403 :         count_unique(b, s1, &cnt1, &cnt2);
    3161       14377 :         BBPreclaim(s1);
    3162             : 
    3163       14549 :         double A = (double) (cnt2 - cnt1) / (n2 - n1);
    3164       14549 :         double B = cnt1 - n1 * A;
    3165             : 
    3166       14549 :         B += A * ci->ncand;
    3167       14549 :         if (ci->s == NULL ||
    3168         143 :             (ci->tpe == cand_dense && ci->ncand == BATcount(b))) {
    3169       14406 :                 BATsetprop(b, GDK_UNIQUE_ESTIMATE, TYPE_dbl, &B);
    3170             :         }
    3171       14548 :         return B;
    3172             : }
    3173             : 
    3174             : BUN
    3175           0 : BATguess_uniques(BAT *b, struct canditer *ci)
    3176             : {
    3177             :         struct canditer lci;
    3178           0 :         if (ci == NULL) {
    3179           0 :                 canditer_init(&lci, b, NULL);
    3180             :                 ci = &lci;
    3181             :         }
    3182           0 :         return (BUN) guess_uniques(b, ci);
    3183             : }
    3184             : 
    3185             : /* estimate the cost of doing a hashjoin with a hash on r; return value
    3186             :  * is the estimated cost, the last three arguments receive some extra
    3187             :  * information */
    3188             : static double
    3189       31295 : joincost(BAT *r, struct canditer *lci, struct canditer *rci,
    3190             :          bool *hash, bool *phash, bool *cand)
    3191             : {
    3192             :         bool rhash;
    3193             :         bool prhash = false;
    3194             :         bool rcand = false;
    3195             :         double rcost = 1;
    3196             :         bat parent;
    3197             :         BAT *b;
    3198             :         BUN nheads;
    3199             :         BUN cnt;
    3200             : 
    3201       31295 :         (void) BATcheckhash(r);
    3202       31327 :         MT_rwlock_rdlock(&r->thashlock);
    3203       31443 :         rhash = r->thash != NULL;
    3204       31443 :         nheads = r->thash ? r->thash->nheads : 0;
    3205       31443 :         cnt = BATcount(r);
    3206       31443 :         MT_rwlock_rdunlock(&r->thashlock);
    3207             : 
    3208       31326 :         if ((rci->tpe == cand_materialized || rci->tpe == cand_except) &&
    3209         544 :             rci->nvals > 0) {
    3210             :                 /* if we need to do binary search on candidate list,
    3211             :                  * take that into account; note checking the other
    3212             :                  * candidate types is essentially free */
    3213         544 :                 rcost += log2((double) rci->nvals);
    3214             :         }
    3215       31326 :         rcost *= lci->ncand;
    3216       31326 :         if (BATtdense(r)) {
    3217             :                 /* no need for a hash, and lookup is free */
    3218             :                 rhash = false;  /* don't use it, even if it's there */
    3219             :         } else {
    3220       31324 :                 if (rhash) {
    3221             :                         /* average chain length */
    3222        7715 :                         rcost *= (double) cnt / nheads;
    3223       23609 :                 } else if ((parent = VIEWtparent(r)) != 0 &&
    3224       12727 :                            (b = BBP_cache(parent)) != NULL &&
    3225        6364 :                            BATcheckhash(b)) {
    3226        3572 :                         MT_rwlock_rdlock(&b->thashlock);
    3227        3603 :                         rhash = prhash = b->thash != NULL;
    3228        3603 :                         if (rhash) {
    3229             :                                 /* average chain length */
    3230        3603 :                                 rcost *= (double) BATcount(b) / b->thash->nheads;
    3231             :                         }
    3232        3603 :                         MT_rwlock_rdunlock(&b->thashlock);
    3233             :                 }
    3234       31354 :                 if (!rhash) {
    3235       20016 :                         const ValRecord *prop = BATgetprop(r, GDK_NUNIQUE);
    3236       20161 :                         if (prop) {
    3237             :                                 /* we know number of unique values, assume some
    3238             :                                  * collisions */
    3239           0 :                                 rcost *= 1.1 * ((double) BATcount(r) / prop->val.oval);
    3240             :                         } else {
    3241             :                                 /* guess number of unique value and work with that */
    3242       20161 :                                 rcost *= 1.1 * ((double) cnt / guess_uniques(r, &(struct canditer){.tpe=cand_dense, .ncand=BATcount(r)}));
    3243             :                         }
    3244             : #ifdef PERSISTENTHASH
    3245             :                         /* only count the cost of creating the hash for
    3246             :                          * non-persistent bats */
    3247       20148 :                         MT_lock_set(&r->theaplock);
    3248       20170 :                         if (!(BBP_status(r->batCacheid) & BBPEXISTING) /* || r->theap->dirty */ || GDKinmemory(r->theap->farmid))
    3249       19157 :                                 rcost += cnt * 2.0;
    3250       20170 :                         MT_lock_unset(&r->theaplock);
    3251             : #else
    3252             :                         rcost += cnt * 2.0;
    3253             : #endif
    3254             :                 }
    3255             :         }
    3256       31505 :         if (rci->ncand != BATcount(r) && rci->tpe != cand_mask) {
    3257             :                 /* instead of using the hash on r (cost in rcost), we
    3258             :                  * can build a new hash on r taking the candidate list
    3259             :                  * into account; don't do this for masked candidate
    3260             :                  * since the searching of the candidate list
    3261             :                  * (canditer_idx) will kill us */
    3262             :                 double rccost;
    3263         718 :                 if (rhash && !prhash) {
    3264         450 :                         rccost = (double) cnt / nheads;
    3265             :                 } else {
    3266         268 :                         ValPtr prop = BATgetprop(r, GDK_NUNIQUE);
    3267         268 :                         if (prop) {
    3268             :                                 /* we know number of unique values, assume some
    3269             :                                  * chains */
    3270           0 :                                 rccost = 1.1 * ((double) cnt / prop->val.oval);
    3271             :                         } else {
    3272             :                                 /* guess number of unique value and work with that */
    3273         268 :                                 rccost = 1.1 * ((double) cnt / guess_uniques(r, rci));
    3274             :                         }
    3275             :                 }
    3276         718 :                 rccost *= lci->ncand;
    3277         718 :                 rccost += rci->ncand * 2.0; /* cost of building the hash */
    3278         718 :                 if (rccost < rcost) {
    3279             :                         rcost = rccost;
    3280             :                         rcand = true;
    3281             :                 }
    3282             :         }
    3283       31505 :         *hash = rhash;
    3284       31505 :         *phash = prhash;
    3285       31505 :         *cand = rcand;
    3286       31505 :         return rcost;
    3287             : }
    3288             : 
    3289             : #define MASK_EQ         1
    3290             : #define MASK_LT         2
    3291             : #define MASK_GT         4
    3292             : #define MASK_LE         (MASK_EQ | MASK_LT)
    3293             : #define MASK_GE         (MASK_EQ | MASK_GT)
    3294             : #define MASK_NE         (MASK_LT | MASK_GT)
    3295             : 
    3296             : static gdk_return
    3297       62086 : thetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, int opcode, BUN estimate, const char *reason, lng t0)
    3298             : {
    3299             :         struct canditer lci, rci;
    3300             :         BUN lcnt, rcnt;
    3301             :         const char *lvals, *rvals;
    3302             :         const char *lvars, *rvars;
    3303       62086 :         const void *nil = ATOMnilptr(l->ttype);
    3304       62086 :         int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
    3305             :         const void *vl, *vr;
    3306             :         oid lastr = 0;          /* last value inserted into r2 */
    3307             :         BUN nr;
    3308             :         oid lo, ro;
    3309             :         int c;
    3310             :         bool lskipped = false;  /* whether we skipped values in l */
    3311             :         lng loff = 0, roff = 0;
    3312       62086 :         oid lval = oid_nil, rval = oid_nil;
    3313             : 
    3314      185888 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    3315       62086 :         assert((opcode & (MASK_EQ | MASK_LT | MASK_GT)) != 0);
    3316             : 
    3317       62086 :         BATiter li = bat_iterator(l);
    3318       62266 :         BATiter ri = bat_iterator(r);
    3319             : 
    3320       62272 :         lcnt = canditer_init(&lci, l, sl);
    3321       62088 :         rcnt = canditer_init(&rci, r, sr);
    3322             : 
    3323       61933 :         lvals = BATtvoid(l) ? NULL : (const char *) li.base;
    3324       61933 :         rvals = BATtvoid(r) ? NULL : (const char *) ri.base;
    3325       61933 :         if (l->tvarsized && l->ttype) {
    3326          16 :                 assert(r->tvarsized && r->ttype);
    3327          16 :                 lvars = li.vh->base;
    3328          16 :                 rvars = ri.vh->base;
    3329             :         } else {
    3330       61917 :                 assert(!r->tvarsized || !r->ttype);
    3331             :                 lvars = rvars = NULL;
    3332             :         }
    3333             : 
    3334       61933 :         if (BATtvoid(l)) {
    3335           0 :                 if (!BATtdense(l)) {
    3336             :                         /* trivial: nils don't match anything */
    3337           0 :                         bat_iterator_end(&li);
    3338           0 :                         bat_iterator_end(&ri);
    3339           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    3340             :                                        false, false, __func__, t0);
    3341             :                 }
    3342           0 :                 loff = (lng) l->tseqbase - (lng) l->hseqbase;
    3343             :         }
    3344       61933 :         if (BATtvoid(r)) {
    3345           0 :                 if (!BATtdense(r)) {
    3346             :                         /* trivial: nils don't match anything */
    3347           0 :                         bat_iterator_end(&li);
    3348           0 :                         bat_iterator_end(&ri);
    3349           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    3350             :                                        false, false, __func__, t0);
    3351             :                 }
    3352           0 :                 roff = (lng) r->tseqbase - (lng) r->hseqbase;
    3353             :         }
    3354             : 
    3355       61933 :         BUN maxsize = joininitresults(r1p, r2p, lcnt, rcnt, false, false,
    3356             :                                       false, false, false, false, estimate);
    3357       60853 :         if (maxsize == BUN_NONE) {
    3358           0 :                 bat_iterator_end(&li);
    3359           0 :                 bat_iterator_end(&ri);
    3360           0 :                 return GDK_FAIL;
    3361             :         }
    3362       60853 :         BAT *r1 = *r1p;
    3363       60853 :         BAT *r2 = r2p ? *r2p : NULL;
    3364             : 
    3365       60853 :         r1->tkey = true;
    3366       60853 :         r1->tsorted = true;
    3367       60853 :         r1->trevsorted = true;
    3368       60853 :         if (r2) {
    3369       16111 :                 r2->tkey = true;
    3370       16111 :                 r2->tsorted = true;
    3371       16111 :                 r2->trevsorted = true;
    3372             :         }
    3373             : 
    3374             :         /* nested loop implementation for theta join */
    3375             :         vl = &lval;
    3376             :         vr = &rval;
    3377      597215 :         for (BUN lidx = 0; lidx < lci.ncand; lidx++) {
    3378      535558 :                 lo = canditer_next(&lci);
    3379      516272 :                 if (lvals)
    3380      516272 :                         vl = VALUE(l, lo - l->hseqbase);
    3381             :                 else
    3382           0 :                         lval = (oid) ((lng) lo + loff);
    3383             :                 nr = 0;
    3384      516272 :                 if (cmp(vl, nil) != 0) {
    3385      504823 :                         canditer_reset(&rci);
    3386     1842317 :                         for (BUN ridx = 0; ridx < rci.ncand; ridx++) {
    3387     1341010 :                                 ro = canditer_next(&rci);
    3388     1212121 :                                 if (rvals)
    3389     1212121 :                                         vr = VALUE(r, ro - r->hseqbase);
    3390             :                                 else
    3391           0 :                                         rval = (oid) ((lng) ro + roff);
    3392     1212121 :                                 if (cmp(vr, nil) == 0)
    3393       73927 :                                         continue;
    3394     1150786 :                                 c = cmp(vl, vr);
    3395     1201217 :                                 if (!((opcode & MASK_LT && c < 0) ||
    3396     1023278 :                                       (opcode & MASK_GT && c > 0) ||
    3397      721703 :                                       (opcode & MASK_EQ && c == 0)))
    3398      721684 :                                         continue;
    3399      479533 :                                 if (maybeextend(r1, r2, 1, lci.next, lci.ncand, maxsize) != GDK_SUCCEED)
    3400           0 :                                         goto bailout;
    3401      541941 :                                 if (BATcount(r1) > 0) {
    3402      536910 :                                         if (r2 && lastr + 1 != ro)
    3403      118247 :                                                 r2->tseqbase = oid_nil;
    3404      536910 :                                         if (nr == 0) {
    3405      181960 :                                                 r1->trevsorted = false;
    3406      181960 :                                                 if (r2 == NULL) {
    3407             :                                                         /* nothing */
    3408      110887 :                                                 } else if (lastr > ro) {
    3409      102329 :                                                         r2->tsorted = false;
    3410      102329 :                                                         r2->tkey = false;
    3411        8558 :                                                 } else if (lastr < ro) {
    3412           0 :                                                         r2->trevsorted = false;
    3413             :                                                 } else {
    3414        8558 :                                                         r2->tkey = false;
    3415             :                                                 }
    3416             :                                         }
    3417             :                                 }
    3418      541941 :                                 APPEND(r1, lo);
    3419      541941 :                                 if (r2) {
    3420      354082 :                                         APPEND(r2, ro);
    3421             :                                 }
    3422             :                                 lastr = ro;
    3423      541941 :                                 nr++;
    3424             :                         }
    3425             :                 }
    3426      536362 :                 if (nr > 1) {
    3427      176011 :                         r1->tkey = false;
    3428      176011 :                         r1->tseqbase = oid_nil;
    3429      176011 :                         if (r2) {
    3430      117976 :                                 r2->trevsorted = false;
    3431             :                         }
    3432      360351 :                 } else if (nr == 0) {
    3433      319137 :                         lskipped = BATcount(r1) > 0;
    3434       41214 :                 } else if (lskipped) {
    3435       26780 :                         r1->tseqbase = oid_nil;
    3436             :                 }
    3437             :         }
    3438             :         /* also set other bits of heap to correct value to indicate size */
    3439       61657 :         BATsetcount(r1, BATcount(r1));
    3440       61588 :         if (r2) {
    3441       16625 :                 BATsetcount(r2, BATcount(r2));
    3442       16555 :                 assert(BATcount(r1) == BATcount(r2));
    3443             :         }
    3444       61518 :         if (BATcount(r1) > 0) {
    3445       33023 :                 if (BATtdense(r1))
    3446        1841 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    3447       33023 :                 if (r2 && BATtdense(r2))
    3448        1276 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    3449             :         } else {
    3450       28495 :                 r1->tseqbase = 0;
    3451       28495 :                 if (r2) {
    3452        2517 :                         r2->tseqbase = 0;
    3453             :                 }
    3454             :         }
    3455       61518 :         bat_iterator_end(&li);
    3456       62207 :         bat_iterator_end(&ri);
    3457       62142 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
    3458             :                   ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
    3459             :                   "opcode=%s%s%s; %s -> " ALGOBATFMT "," ALGOOPTBATFMT
    3460             :                   " (" LLFMT "usec)\n",
    3461             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    3462             :                   ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
    3463             :                   opcode & MASK_LT ? "<" : "",
    3464             :                   opcode & MASK_GT ? ">" : "",
    3465             :                   opcode & MASK_EQ ? "=" : "",
    3466             :                   reason,
    3467             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    3468             :                   GDKusec() - t0);
    3469             :         return GDK_SUCCEED;
    3470             : 
    3471             :   bailout:
    3472           0 :         bat_iterator_end(&li);
    3473           0 :         bat_iterator_end(&ri);
    3474           0 :         BBPreclaim(r1);
    3475           0 :         BBPreclaim(r2);
    3476           0 :         return GDK_FAIL;
    3477             : }
    3478             : 
    3479             : /* small ordered right, dense left, oid's only, do fetches */
    3480             : static gdk_return
    3481           0 : fetchjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
    3482             :           struct canditer *restrict lci, struct canditer *restrict rci,
    3483             :           const char *reason, lng t0)
    3484             : {
    3485           0 :         oid lo = lci->seq - l->hseqbase + l->tseqbase, hi = lo + lci->ncand;
    3486             :         BUN b, e, p;
    3487             :         BAT *r1, *r2 = NULL;
    3488             : 
    3489           0 :         MT_thread_setalgorithm(__func__);
    3490           0 :         if (r->tsorted) {
    3491           0 :                 b = SORTfndfirst(r, &lo);
    3492           0 :                 e = SORTfndfirst(r, &hi);
    3493             :         } else {
    3494           0 :                 assert(r->trevsorted);
    3495           0 :                 b = SORTfndlast(r, &hi);
    3496           0 :                 e = SORTfndlast(r, &lo);
    3497             :         }
    3498           0 :         if (b < rci->seq - r->hseqbase)
    3499             :                 b = rci->seq - r->hseqbase;
    3500           0 :         if (e > rci->seq + rci->ncand - r->hseqbase)
    3501             :                 e = rci->seq + rci->ncand - r->hseqbase;
    3502           0 :         if (e == b) {
    3503           0 :                 return nomatch(r1p, r2p, l, r, lci,
    3504             :                                false, false, __func__, t0);
    3505             :         }
    3506           0 :         r1 = COLnew(0, TYPE_oid, e - b, TRANSIENT);
    3507           0 :         if (r1 == NULL)
    3508             :                 return GDK_FAIL;
    3509           0 :         if (r2p) {
    3510           0 :                 if ((r2 = BATdense(0, r->hseqbase + b, e - b)) == NULL) {
    3511           0 :                         BBPreclaim(r1);
    3512           0 :                         return GDK_FAIL;
    3513             :                 }
    3514           0 :                 *r2p = r2;
    3515             :         }
    3516           0 :         *r1p = r1;
    3517           0 :         oid *op = (oid *) Tloc(r1, 0);
    3518           0 :         BATiter ri = bat_iterator(r);
    3519           0 :         const oid *rp = (const oid *) ri.base;
    3520           0 :         for (p = b; p < e; p++) {
    3521           0 :                 *op++ = rp[p] + l->hseqbase - l->tseqbase;
    3522             :         }
    3523           0 :         bat_iterator_end(&ri);
    3524           0 :         BATsetcount(r1, e - b);
    3525           0 :         r1->tkey = r->tkey;
    3526           0 :         r1->tsorted = r->tsorted || e - b <= 1;
    3527           0 :         r1->trevsorted = r->trevsorted || e - b <= 1;
    3528           0 :         r1->tseqbase = e == b ? 0 : e - b == 1 ? *(const oid *)Tloc(r1, 0) : oid_nil;
    3529           0 :         TRC_DEBUG(ALGO, "%s(l=" ALGOBATFMT ","
    3530             :                   "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
    3531             :                   "sr=" ALGOOPTBATFMT ") %s "
    3532             :                   "-> (" ALGOBATFMT "," ALGOOPTBATFMT ") " LLFMT "us\n",
    3533             :                   __func__,
    3534             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    3535             :                   ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
    3536             :                   reason,
    3537             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    3538             :                   GDKusec() - t0);
    3539             : 
    3540             :         return GDK_SUCCEED;
    3541             : }
    3542             : 
    3543             : static BAT *
    3544        7634 : bitmaskjoin(BAT *l, BAT *r,
    3545             :             struct canditer *restrict lci, struct canditer *restrict rci,
    3546             :             bool only_misses,
    3547             :             const char *reason, lng t0)
    3548             : {
    3549             :         BAT *r1;
    3550        7634 :         size_t nmsk = (lci->ncand + 31) / 32;
    3551        7634 :         uint32_t *mask = GDKzalloc(nmsk * sizeof(uint32_t));
    3552             :         BUN cnt = 0;
    3553             : 
    3554        7641 :         MT_thread_setalgorithm(__func__);
    3555        7646 :         if (mask == NULL)
    3556             :                 return NULL;
    3557             : 
    3558    21310616 :         for (BUN n = 0; n < rci->ncand; n++) {
    3559    21302968 :                 oid o = canditer_next(rci) - r->hseqbase;
    3560    21291560 :                 o = BUNtoid(r, o);
    3561    21302970 :                 if (is_oid_nil(o))
    3562           0 :                         continue;
    3563    21302970 :                 o += l->hseqbase;
    3564    21302970 :                 if (o < lci->seq + l->tseqbase)
    3565           2 :                         continue;
    3566    21302968 :                 o -= lci->seq + l->tseqbase;
    3567    21302968 :                 if (o >= lci->ncand)
    3568           0 :                         continue;
    3569    21302968 :                 if ((mask[o >> 5] & (1U << (o & 0x1F))) == 0) {
    3570    20255380 :                         cnt++;
    3571    20255380 :                         mask[o >> 5] |= 1U << (o & 0x1F);
    3572             :                 }
    3573             :         }
    3574        7648 :         if (only_misses)
    3575        3693 :                 cnt = lci->ncand - cnt;
    3576        7648 :         if (cnt == 0 || cnt == lci->ncand) {
    3577        3546 :                 GDKfree(mask);
    3578        3547 :                 if (cnt == 0)
    3579         358 :                         return BATdense(0, 0, 0);
    3580        3189 :                 return BATdense(0, lci->seq, lci->ncand);
    3581             :         }
    3582        4102 :         r1 = COLnew(0, TYPE_oid, cnt, TRANSIENT);
    3583        4099 :         if (r1 != NULL) {
    3584        4099 :                 oid *r1p = Tloc(r1, 0);
    3585             : 
    3586        4099 :                 r1->tkey = true;
    3587        4099 :                 r1->tnil = false;
    3588        4099 :                 r1->tnonil = true;
    3589        4099 :                 r1->tsorted = true;
    3590        4099 :                 r1->trevsorted = cnt <= 1;
    3591        4099 :                 if (only_misses) {
    3592             :                         /* set the bits for unused values at the
    3593             :                          * end so that we don't need special
    3594             :                          * code in the loop */
    3595        3334 :                         if (lci->ncand & 0x1F)
    3596        3290 :                                 mask[nmsk - 1] |= ~0U << (lci->ncand & 0x1F);
    3597     1798623 :                         for (size_t i = 0; i < nmsk; i++)
    3598     1795289 :                                 if (mask[i] != ~0U)
    3599    57178242 :                                         for (uint32_t j = 0; j < 32; j++)
    3600    55445568 :                                                 if ((mask[i] & (1U << j)) == 0)
    3601    49383377 :                                                         *r1p++ = i * 32 + j + lci->seq;
    3602             :                 } else {
    3603      466833 :                         for (size_t i = 0; i < nmsk; i++)
    3604      466068 :                                 if (mask[i] != 0U)
    3605    12824196 :                                         for (uint32_t j = 0; j < 32; j++)
    3606    12435584 :                                                 if ((mask[i] & (1U << j)) != 0)
    3607    11466326 :                                                         *r1p++ = i * 32 + j + lci->seq;
    3608             :                 }
    3609        4099 :                 BATsetcount(r1, cnt);
    3610        4102 :                 assert((BUN) (r1p - (oid*) Tloc(r1, 0)) == BATcount(r1));
    3611             : 
    3612        4102 :                 TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
    3613             :                           "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
    3614             :                           "sr=" ALGOOPTBATFMT ",only_misses=%s; %s "
    3615             :                           "-> " ALGOBATFMT " (" LLFMT "usec)\n",
    3616             :                           ALGOBATPAR(l), ALGOBATPAR(r),
    3617             :                           ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
    3618             :                           only_misses ? "true" : "false",
    3619             :                           reason,
    3620             :                           ALGOBATPAR(r1),
    3621             :                           GDKusec() - t0);
    3622             :         }
    3623        4102 :         GDKfree(mask);
    3624        4102 :         return r1;
    3625             : }
    3626             : 
    3627             : /* Make the implementation choices for various left joins.
    3628             :  * nil_matches: nil is an ordinary value that can match;
    3629             :  * nil_on_miss: outer join: fill in a nil value in case of no match;
    3630             :  * semi: semi join: return one of potentially more than one matches;
    3631             :  * only_misses: difference: list rows without match on the right;
    3632             :  * not_in: for implementing NOT IN: if nil on right then there are no matches;
    3633             :  * max_one: error if there is more than one match. */
    3634             : static gdk_return
    3635      159061 : leftjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
    3636             :          bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
    3637             :          bool not_in, bool max_one, bool min_one, BUN estimate,
    3638             :          const char *func, lng t0)
    3639             : {
    3640             :         BUN lcnt, rcnt;
    3641             :         struct canditer lci, rci;
    3642             :         bool rhash, prhash, rcand;
    3643             :         bat parent;
    3644             :         double rcost = 0;
    3645             :         gdk_return rc;
    3646             : 
    3647      159061 :         MT_thread_setalgorithm(__func__);
    3648             :         /* only_misses implies left output only */
    3649      159062 :         assert(!only_misses || r2p == NULL);
    3650             :         /* if nil_on_miss is set, we really need a right output */
    3651      159062 :         assert(!nil_on_miss || r2p != NULL);
    3652             :         /* if not_in is set, then so is only_misses */
    3653      159062 :         assert(!not_in || only_misses);
    3654      159062 :         *r1p = NULL;
    3655      159062 :         if (r2p)
    3656         881 :                 *r2p = NULL;
    3657             : 
    3658      159062 :         lcnt = canditer_init(&lci, l, sl);
    3659      159110 :         rcnt = canditer_init(&rci, r, sr);
    3660             : 
    3661      159054 :         if ((parent = VIEWtparent(l)) != 0) {
    3662        2878 :                 BAT *b = BBP_cache(parent);
    3663        2878 :                 if (l->hseqbase == b->hseqbase &&
    3664        2169 :                     BATcount(l) == BATcount(b) &&
    3665         898 :                     ATOMtype(l->ttype) == ATOMtype(b->ttype)) {
    3666             :                         l = b;
    3667             :                 }
    3668             :         }
    3669      159054 :         if ((parent = VIEWtparent(r)) != 0) {
    3670        3202 :                 BAT *b = BBP_cache(parent);
    3671        3202 :                 if (r->hseqbase == b->hseqbase &&
    3672        5421 :                     BATcount(r) == BATcount(b) &&
    3673        4441 :                     ATOMtype(r->ttype) == ATOMtype(b->ttype)) {
    3674             :                         r = b;
    3675             :                 }
    3676             :         }
    3677             : 
    3678      159054 :         if (l->ttype == TYPE_msk || mask_cand(l)) {
    3679           3 :                 if ((l = BATunmask(l)) == NULL)
    3680             :                         return GDK_FAIL;
    3681             :         } else {
    3682      159051 :                 BBPfix(l->batCacheid);
    3683             :         }
    3684      159297 :         if (r->ttype == TYPE_msk || mask_cand(r)) {
    3685           1 :                 if ((r = BATunmask(r)) == NULL) {
    3686           0 :                         BBPunfix(l->batCacheid);
    3687           0 :                         return GDK_FAIL;
    3688             :                 }
    3689             :         } else {
    3690      159296 :                 BBPfix(r->batCacheid);
    3691             :         }
    3692             : 
    3693      159322 :         if (joinparamcheck(l, r, NULL, sl, sr, func) != GDK_SUCCEED) {
    3694             :                 rc = GDK_FAIL;
    3695           0 :                 goto doreturn;
    3696             :         }
    3697             : 
    3698      159208 :         if (lcnt == 0 || rcnt == 0) {
    3699      119919 :                 TRC_DEBUG(ALGO, "%s(l=" ALGOBATFMT ","
    3700             :                           "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
    3701             :                           "sr=" ALGOOPTBATFMT ",nil_matches=%d,"
    3702             :                           "nil_on_miss=%d,semi=%d,only_misses=%d,"
    3703             :                           "not_in=%d,max_one=%d,min_one=%d)\n",
    3704             :                           func,
    3705             :                           ALGOBATPAR(l), ALGOBATPAR(r),
    3706             :                           ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
    3707             :                           nil_matches, nil_on_miss, semi, only_misses,
    3708             :                           not_in, max_one, min_one);
    3709      119919 :                 rc = nomatch(r1p, r2p, l, r, &lci,
    3710             :                              nil_on_miss, only_misses, func, t0);
    3711      119909 :                 goto doreturn;
    3712             :         }
    3713             : 
    3714       39289 :         if (!nil_on_miss && !semi && !max_one && !min_one && !only_misses && !not_in &&
    3715         199 :             (lcnt == 1 || (BATordered(l) && BATordered_rev(l)) ||
    3716         182 :              (l->ttype == TYPE_void && is_oid_nil(l->tseqbase)))) {
    3717             :                 /* single value to join, use select */
    3718          56 :                 rc = selectjoin(r1p, r2p, l, r, &lci, &rci,
    3719             :                                 nil_matches, t0, false, func);
    3720          56 :                 goto doreturn;
    3721       39233 :         } else if (BATtdense(r) && rci.tpe == cand_dense) {
    3722             :                 /* use special implementation for dense right-hand side */
    3723       25418 :                 rc = mergejoin_void(r1p, r2p, l, r, &lci, &rci,
    3724             :                                     nil_on_miss, only_misses, t0, false,
    3725             :                                     func);
    3726       25403 :                 goto doreturn;
    3727       13815 :         } else if (BATtdense(l)
    3728        7706 :                    && lci.tpe == cand_dense
    3729        7697 :                    && rci.tpe == cand_dense
    3730             :                    && !semi
    3731        7703 :                    && !max_one
    3732             :                    && !min_one
    3733        3693 :                    && !nil_matches
    3734             :                    && !only_misses
    3735        3692 :                    && !not_in
    3736             :                    /* && (rcnt * 1024) < lcnt */
    3737           0 :                    && (BATordered(r) || BATordered_rev(r))) {
    3738           0 :                 assert(ATOMtype(l->ttype) == TYPE_oid); /* tdense */
    3739           0 :                 rc = fetchjoin(r1p, r2p, l, r, sl, sr, &lci, &rci, func, t0);
    3740           0 :                 goto doreturn;
    3741       13815 :         } else if (BATtdense(l)
    3742        7691 :                    && lci.tpe == cand_dense
    3743        7682 :                    && r2p == NULL
    3744        7617 :                    && (semi || only_misses)
    3745             :                    && !nil_on_miss
    3746        7628 :                    && !not_in
    3747             :                    && !max_one
    3748        7647 :                    && !min_one) {
    3749        7640 :                 *r1p = bitmaskjoin(l, r, &lci, &rci, only_misses, func, t0);
    3750        7637 :                 rc = *r1p == NULL ? GDK_FAIL : GDK_SUCCEED;
    3751        7637 :                 goto doreturn;
    3752             :         } else {
    3753             :                 /* looking at r->tvheap, so we need a lock */
    3754        6175 :                 MT_lock_set(&r->theaplock);
    3755        6202 :                 BUN hsz = r->tvheap ? r->tvheap->size : 0;
    3756        6202 :                 MT_lock_unset(&r->theaplock);
    3757        6202 :                 if ((BATordered(r) || BATordered_rev(r))
    3758        5365 :                     && (BATordered(l)
    3759         616 :                         || BATordered_rev(l)
    3760         546 :                         || BATtdense(r)
    3761         546 :                         || lcnt < 1024
    3762         254 :                         || BATcount(r) * (Tsize(r) + hsz + 2 * sizeof(BUN)) > GDK_mem_maxsize / (GDKnr_threads ? GDKnr_threads : 1))) {
    3763        5238 :                         rc = mergejoin(r1p, r2p, l, r, &lci, &rci,
    3764             :                                        nil_matches, nil_on_miss, semi, only_misses,
    3765             :                                        not_in, max_one, min_one, estimate, t0, false, func);
    3766        5219 :                         goto doreturn;
    3767             :                 }
    3768             :         }
    3769         962 :         rcost = joincost(r, &lci, &rci, &rhash, &prhash, &rcand);
    3770             : 
    3771         959 :         if (!nil_on_miss && !only_misses && !not_in && !max_one && !min_one) {
    3772             :                 /* maybe do a hash join on the swapped operands; if we
    3773             :                  * do, we need to sort the output, so we take that into
    3774             :                  * account as well */
    3775             :                 bool lhash, plhash, lcand;
    3776             :                 double lcost;
    3777             : 
    3778         198 :                 lcost = joincost(l, &rci, &lci, &lhash, &plhash, &lcand);
    3779         197 :                 if (semi)
    3780          86 :                         lcost += rci.ncand; /* cost of BATunique(r) */
    3781             :                 /* add cost of sorting; obviously we don't know the
    3782             :                  * size, so we guess that the size of the output is
    3783             :                  * the same as the right input */
    3784         197 :                 lcost += rci.ncand * log((double) rci.ncand); /* sort */
    3785         197 :                 if (lcost < rcost) {
    3786          52 :                         BAT *tmp = sr;
    3787             :                         BAT *r1, *r2;
    3788          52 :                         if (semi) {
    3789          47 :                                 sr = BATunique(r, sr);
    3790          47 :                                 if (sr == NULL) {
    3791             :                                         rc = GDK_FAIL;
    3792           0 :                                         goto doreturn;
    3793             :                                 }
    3794          47 :                                 canditer_init(&rci, r, sr);
    3795             :                         }
    3796          52 :                         rc = hashjoin(&r2, &r1, r, l, &rci, &lci, nil_matches,
    3797             :                                       false, false, false, false, false, false, estimate,
    3798             :                                       t0, true, lhash, plhash, lcand, func);
    3799          52 :                         if (semi)
    3800          47 :                                 BBPunfix(sr->batCacheid);
    3801          52 :                         if (rc != GDK_SUCCEED)
    3802           0 :                                 goto doreturn;
    3803          52 :                         if (r2p == NULL) {
    3804          47 :                                 BBPunfix(r2->batCacheid);
    3805          47 :                                 r2 = NULL;
    3806             :                         }
    3807          52 :                         if (semi)
    3808          47 :                                 r1->tkey = true;
    3809          52 :                         if (!VIEWtparent(r1) &&
    3810          52 :                             r1->ttype == TYPE_oid &&
    3811          52 :                             BBP_refs(r1->batCacheid) == 1 &&
    3812          52 :                             (r2 == NULL ||
    3813           5 :                              (!VIEWtparent(r2) &&
    3814           5 :                               BBP_refs(r2->batCacheid) == 1 &&
    3815           5 :                               r2->ttype == TYPE_oid))) {
    3816             :                                 /* in-place sort if we can */
    3817          52 :                                 if (r2) {
    3818           5 :                                         GDKqsort(r1->theap->base, r2->theap->base,
    3819           5 :                                                  NULL, r1->batCount, r1->twidth,
    3820           5 :                                                  r2->twidth, TYPE_oid, false,
    3821             :                                                  false);
    3822           5 :                                         r2->tsorted = false;
    3823           5 :                                         r2->trevsorted = false;
    3824           5 :                                         r2->tseqbase = oid_nil;
    3825           5 :                                         *r2p = r2;
    3826             :                                 } else {
    3827          47 :                                         GDKqsort(r1->theap->base, NULL, NULL,
    3828          47 :                                                  r1->batCount, r1->twidth, 0,
    3829             :                                                  TYPE_oid, false, false);
    3830             :                                 }
    3831          52 :                                 r1->tsorted = true;
    3832          52 :                                 r1->trevsorted = false;
    3833          52 :                                 *r1p = r1;
    3834             :                         } else {
    3835             :                                 BAT *ob;
    3836           0 :                                 rc = BATsort(&tmp, r2p ? &ob : NULL, NULL,
    3837             :                                              r1, NULL, NULL, false, false, false);
    3838           0 :                                 BBPunfix(r1->batCacheid);
    3839           0 :                                 if (rc != GDK_SUCCEED) {
    3840           0 :                                         if (r2)
    3841           0 :                                                 BBPunfix(r2->batCacheid);
    3842           0 :                                         goto doreturn;
    3843             :                                 }
    3844           0 :                                 *r1p = r1 = tmp;
    3845           0 :                                 if (r2p) {
    3846           0 :                                         tmp = BATproject(ob, r2);
    3847           0 :                                         BBPunfix(r2->batCacheid);
    3848           0 :                                         BBPunfix(ob->batCacheid);
    3849           0 :                                         if (tmp == NULL) {
    3850           0 :                                                 BBPunfix(r1->batCacheid);
    3851             :                                                 rc = GDK_FAIL;
    3852           0 :                                                 goto doreturn;
    3853             :                                         }
    3854           0 :                                         *r2p = tmp;
    3855             :                                 }
    3856             :                         }
    3857             :                         rc = GDK_SUCCEED;
    3858          52 :                         goto doreturn;
    3859             :                 }
    3860             :         }
    3861         906 :         rc = hashjoin(r1p, r2p, l, r, &lci, &rci,
    3862             :                       nil_matches, nil_on_miss, semi, only_misses,
    3863             :                       not_in, max_one, min_one, estimate, t0, false, rhash, prhash,
    3864             :                       rcand, func);
    3865      159180 :   doreturn:
    3866      159180 :         BBPunfix(l->batCacheid);
    3867      159357 :         BBPunfix(r->batCacheid);
    3868      159329 :         return rc;
    3869             : }
    3870             : 
    3871             : /* Perform an equi-join over l and r.  Returns two new, aligned, bats
    3872             :  * with the oids of matching tuples.  The result is in the same order
    3873             :  * as l (i.e. r1 is sorted). */
    3874             : gdk_return
    3875         655 : BATleftjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
    3876             : {
    3877         655 :         return leftjoin(r1p, r2p, l, r, sl, sr, nil_matches,
    3878             :                         false, false, false, false, false, false,
    3879             :                         estimate, __func__,
    3880         655 :                         GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
    3881             : }
    3882             : 
    3883             : /* Performs a left outer join over l and r.  Returns two new, aligned,
    3884             :  * bats with the oids of matching tuples, or the oid in the first
    3885             :  * output bat and nil in the second output bat if the value in l does
    3886             :  * not occur in r.  The result is in the same order as l (i.e. r1 is
    3887             :  * sorted). */
    3888             : gdk_return
    3889           0 : BATouterjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool match_one, BUN estimate)
    3890             : {
    3891           0 :         return leftjoin(r1p, r2p, l, r, sl, sr, nil_matches,
    3892             :                         true, false, false, false, match_one, match_one,
    3893             :                         estimate, __func__,
    3894           0 :                         GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
    3895             : }
    3896             : 
    3897             : /* Perform a semi-join over l and r.  Returns one or two new, bats
    3898             :  * with the oids of matching tuples.  The result is in the same order
    3899             :  * as l (i.e. r1 is sorted).  If a single bat is returned, it is a
    3900             :  * candidate list. */
    3901             : gdk_return
    3902         226 : BATsemijoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
    3903             :             bool nil_matches, bool max_one, BUN estimate)
    3904             : {
    3905         226 :         return leftjoin(r1p, r2p, l, r, sl, sr, nil_matches,
    3906             :                         false, true, false, false, max_one, false,
    3907             :                         estimate, __func__,
    3908         226 :                         GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
    3909             : }
    3910             : 
    3911             : /* Return a candidate list with the list of rows in l whose value also
    3912             :  * occurs in r.  This is just the left output of a semi-join. */
    3913             : BAT *
    3914       11379 : BATintersect(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool max_one,
    3915             :              BUN estimate)
    3916             : {
    3917             :         BAT *bn;
    3918             : 
    3919       11379 :         if (leftjoin(&bn, NULL, l, r, sl, sr, nil_matches,
    3920             :                      false, true, false, false, max_one, false,
    3921             :                      estimate, __func__,
    3922       11379 :                      GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0) == GDK_SUCCEED)
    3923       11496 :                 return virtualize(bn);
    3924             :         return NULL;
    3925             : }
    3926             : 
    3927             : /* Return the difference of l and r.  The result is a BAT with the
    3928             :  * oids of those values in l that do not occur in r.  This is what you
    3929             :  * might call an anti-semi-join.  The result is a candidate list. */
    3930             : BAT *
    3931      146845 : BATdiff(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool not_in,
    3932             :         BUN estimate)
    3933             : {
    3934             :         BAT *bn;
    3935             : 
    3936      146845 :         if (leftjoin(&bn, NULL, l, r, sl, sr, nil_matches,
    3937             :                      false, false, true, not_in, false, false,
    3938             :                      estimate, __func__,
    3939      146845 :                      GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0) == GDK_SUCCEED)
    3940      146959 :                 return virtualize(bn);
    3941             :         return NULL;
    3942             : }
    3943             : 
    3944             : gdk_return
    3945       62011 : BATthetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, int op, bool nil_matches, BUN estimate)
    3946             : {
    3947             :         int opcode = 0;
    3948             :         lng t0 = 0;
    3949             : 
    3950             :         /* encode operator as a bit mask into opcode */
    3951       62011 :         switch (op) {
    3952           0 :         case JOIN_EQ:
    3953           0 :                 return BATjoin(r1p, r2p, l, r, sl, sr, nil_matches, estimate);
    3954             :         case JOIN_NE:
    3955             :                 opcode = MASK_NE;
    3956             :                 break;
    3957        8388 :         case JOIN_LT:
    3958             :                 opcode = MASK_LT;
    3959        8388 :                 break;
    3960          25 :         case JOIN_LE:
    3961             :                 opcode = MASK_LE;
    3962          25 :                 break;
    3963       53508 :         case JOIN_GT:
    3964             :                 opcode = MASK_GT;
    3965       53508 :                 break;
    3966          18 :         case JOIN_GE:
    3967             :                 opcode = MASK_GE;
    3968          18 :                 break;
    3969           0 :         default:
    3970           0 :                 GDKerror("unknown operator %d.\n", op);
    3971           0 :                 return GDK_FAIL;
    3972             :         }
    3973             : 
    3974       62011 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    3975       62011 :         *r1p = NULL;
    3976       62011 :         if (r2p) {
    3977       16517 :                 *r2p = NULL;
    3978             :         }
    3979       62011 :         if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED)
    3980             :                 return GDK_FAIL;
    3981             : 
    3982       62079 :         return thetajoin(r1p, r2p, l, r, sl, sr, opcode, estimate,
    3983             :                          __func__, t0);
    3984             : }
    3985             : 
    3986             : gdk_return
    3987      578518 : BATjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
    3988             : {
    3989             :         struct canditer lci, rci;
    3990      578518 :         bool lhash = false, rhash = false, lcand = false;
    3991      578518 :         bool plhash = false, prhash = false, rcand = false;
    3992             :         bool swap;
    3993             :         bat parent;
    3994             :         double rcost = 0;
    3995             :         double lcost = 0;
    3996             :         gdk_return rc;
    3997             :         lng t0 = 0;
    3998      578518 :         BAT *r2 = NULL;
    3999             : 
    4000      578518 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    4001             : 
    4002      578518 :         canditer_init(&lci, l, sl);
    4003      577210 :         canditer_init(&rci, r, sr);
    4004             : 
    4005      578571 :         if ((parent = VIEWtparent(l)) != 0) {
    4006      109990 :                 BAT *b = BBP_cache(parent);
    4007      109990 :                 if (l->hseqbase == b->hseqbase &&
    4008      102575 :                     BATcount(l) == BATcount(b) &&
    4009       32483 :                     ATOMtype(l->ttype) == ATOMtype(b->ttype))
    4010             :                         l = b;
    4011             :         }
    4012      578571 :         if ((parent = VIEWtparent(r)) != 0) {
    4013      354724 :                 BAT *b = BBP_cache(parent);
    4014      354724 :                 if (r->hseqbase == b->hseqbase &&
    4015      617096 :                     BATcount(r) == BATcount(b) &&
    4016      550207 :                     ATOMtype(r->ttype) == ATOMtype(b->ttype))
    4017             :                         r = b;
    4018             :         }
    4019             : 
    4020      578571 :         if (l->ttype == TYPE_msk || mask_cand(l)) {
    4021           0 :                 if ((l = BATunmask(l)) == NULL)
    4022             :                         return GDK_FAIL;
    4023             :         } else {
    4024      578571 :                 BBPfix(l->batCacheid);
    4025             :         }
    4026      579656 :         if (r->ttype == TYPE_msk || mask_cand(r)) {
    4027           1 :                 if ((r = BATunmask(r)) == NULL) {
    4028           0 :                         BBPunfix(l->batCacheid);
    4029           0 :                         return GDK_FAIL;
    4030             :                 }
    4031             :         } else {
    4032      579655 :                 BBPfix(r->batCacheid);
    4033             :         }
    4034             : 
    4035      579338 :         *r1p = NULL;
    4036      579338 :         if (r2p)
    4037      526837 :                 *r2p = NULL;
    4038             : 
    4039      579338 :         if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED) {
    4040             :                 rc = GDK_FAIL;
    4041           0 :                 goto doreturn;
    4042             :         }
    4043             : 
    4044      579538 :         if (lci.ncand == 0 || rci.ncand == 0) {
    4045      485941 :                 TRC_DEBUG(ALGO, "BATjoin(l=" ALGOBATFMT ","
    4046             :                           "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
    4047             :                           "sr=" ALGOOPTBATFMT ",nil_matches=%d)\n",
    4048             :                           ALGOBATPAR(l), ALGOBATPAR(r),
    4049             :                           ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
    4050             :                           nil_matches);
    4051      485941 :                 rc = nomatch(r1p, r2p, l, r, &lci,
    4052             :                              false, false, __func__, t0);
    4053      484015 :                 goto doreturn;
    4054             :         }
    4055             : 
    4056             :         swap = false;
    4057             : 
    4058       93597 :         if (lci.ncand == 1 || (BATordered(l) && BATordered_rev(l)) || (l->ttype == TYPE_void && is_oid_nil(l->tseqbase))) {
    4059             :                 /* single value to join, use select */
    4060       54143 :                 rc = selectjoin(r1p, r2p, l, r, &lci, &rci,
    4061             :                                 nil_matches, t0, false, __func__);
    4062       54093 :                 goto doreturn;
    4063       39388 :         } else if (rci.ncand == 1 || (BATordered(r) && BATordered_rev(r)) || (r->ttype == TYPE_void && is_oid_nil(r->tseqbase))) {
    4064             :                 /* single value to join, use select */
    4065       17112 :                 rc = selectjoin(r2p ? r2p : &r2, r1p, r, l, &rci, &lci,
    4066             :                                 nil_matches, t0, true, __func__);
    4067       12468 :                 if (rc == GDK_SUCCEED && r2p == NULL)
    4068        7854 :                         BBPunfix(r2->batCacheid);
    4069       12483 :                 goto doreturn;
    4070       26875 :         } else if (BATtdense(r) && rci.tpe == cand_dense) {
    4071             :                 /* use special implementation for dense right-hand side */
    4072        1723 :                 rc = mergejoin_void(r1p, r2p, l, r, &lci, &rci,
    4073             :                                     false, false, t0, false, __func__);
    4074        1737 :                 goto doreturn;
    4075       25152 :         } else if (BATtdense(l) && lci.tpe == cand_dense) {
    4076             :                 /* use special implementation for dense right-hand side */
    4077          53 :                 rc = mergejoin_void(r2p ? r2p : &r2, r1p, r, l, &rci, &lci,
    4078             :                                     false, false, t0, true, __func__);
    4079          33 :                 if (rc == GDK_SUCCEED && r2p == NULL)
    4080          13 :                         BBPunfix(r2->batCacheid);
    4081          33 :                 goto doreturn;
    4082       39415 :         } else if ((BATordered(l) || BATordered_rev(l)) &&
    4083       18903 :                    (BATordered(r) || BATordered_rev(r))) {
    4084             :                 /* both sorted */
    4085        9955 :                 rc = mergejoin(r1p, r2p, l, r, &lci, &rci,
    4086             :                                nil_matches, false, false, false, false, false, false,
    4087             :                                estimate, t0, false, __func__);
    4088        9910 :                 goto doreturn;
    4089             :         }
    4090             : 
    4091       15128 :         lcost = joincost(l, &rci, &lci, &lhash, &plhash, &lcand);
    4092       15101 :         rcost = joincost(r, &lci, &rci, &rhash, &prhash, &rcand);
    4093             : 
    4094             :         /* if the cost of doing searches on l is lower than the cost
    4095             :          * of doing searches on r, we swap */
    4096             :         swap = (lcost < rcost);
    4097             : 
    4098       30237 :         if ((r->ttype == TYPE_void && r->tvheap != NULL) ||
    4099       30365 :             ((BATordered(r) || BATordered_rev(r)) &&
    4100        4117 :              (lci.ncand * (log2((double) rci.ncand) + 1) < (swap ? lcost : rcost)))) {
    4101             :                 /* r is sorted and it is cheaper to do multiple binary
    4102             :                  * searches than it is to use a hash */
    4103         416 :                 rc = mergejoin(r1p, r2p, l, r, &lci, &rci,
    4104             :                                nil_matches, false, false, false, false, false, false,
    4105             :                                estimate, t0, false, __func__);
    4106       29467 :         } else if ((l->ttype == TYPE_void && l->tvheap != NULL) ||
    4107       29698 :             ((BATordered(l) || BATordered_rev(l)) &&
    4108        4328 :              (rci.ncand * (log2((double) lci.ncand) + 1) < (swap ? lcost : rcost)))) {
    4109             :                 /* l is sorted and it is cheaper to do multiple binary
    4110             :                  * searches than it is to use a hash */
    4111        1868 :                 rc = mergejoin(r2p ? r2p : &r2, r1p, r, l, &rci, &lci,
    4112             :                                nil_matches, false, false, false, false, false, false,
    4113             :                                estimate, t0, true, __func__);
    4114         942 :                 if (rc == GDK_SUCCEED && r2p == NULL)
    4115          22 :                         BBPunfix(r2->batCacheid);
    4116       13770 :         } else if (swap) {
    4117       14165 :                 rc = hashjoin(r2p ? r2p : &r2, r1p, r, l, &rci, &lci,
    4118             :                               nil_matches, false, false, false, false, false, false,
    4119             :                               estimate, t0, true, lhash, plhash, lcand,
    4120             :                               __func__);
    4121        7426 :                 if (rc == GDK_SUCCEED && r2p == NULL)
    4122         684 :                         BBPunfix(r2->batCacheid);
    4123             :         } else {
    4124        6350 :                 rc = hashjoin(r1p, r2p, l, r, &lci, &rci,
    4125             :                               nil_matches, false, false, false, false, false, false,
    4126             :                               estimate, t0, false, rhash, prhash, rcand,
    4127             :                               __func__);
    4128             :         }
    4129      577342 :   doreturn:
    4130      577342 :         BBPunfix(l->batCacheid);
    4131      579202 :         BBPunfix(r->batCacheid);
    4132      579975 :         return rc;
    4133             : }
    4134             : 
    4135             : gdk_return
    4136           0 : BATbandjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
    4137             :             const void *c1, const void *c2, bool linc, bool hinc, BUN estimate)
    4138             : {
    4139             :         lng t0 = 0;
    4140             :         BUN lcnt, rcnt;
    4141             :         struct canditer lci, rci;
    4142             :         const char *lvals, *rvals;
    4143             :         int t;
    4144           0 :         const void *nil = ATOMnilptr(l->ttype);
    4145           0 :         int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
    4146             :         const char *vl, *vr;
    4147             :         oid lastr = 0;          /* last value inserted into r2 */
    4148             :         BUN nr;
    4149             :         oid lo, ro;
    4150             :         bool lskipped = false;  /* whether we skipped values in l */
    4151             :         BUN nils = 0;           /* needed for XXX_WITH_CHECK macros */
    4152             : 
    4153           0 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    4154             : 
    4155           0 :         MT_thread_setalgorithm(__func__);
    4156           0 :         *r1p = NULL;
    4157           0 :         if (r2p) {
    4158           0 :                 *r2p = NULL;
    4159             :         }
    4160           0 :         if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED)
    4161             :                 return GDK_FAIL;
    4162             : 
    4163           0 :         assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
    4164             : 
    4165             :         t = ATOMtype(l->ttype);
    4166           0 :         t = ATOMbasetype(t);
    4167             : 
    4168           0 :         lcnt = canditer_init(&lci, l, sl);
    4169           0 :         rcnt = canditer_init(&rci, r, sr);
    4170             : 
    4171           0 :         if (lcnt == 0 || rcnt == 0)
    4172           0 :                 return nomatch(r1p, r2p, l, r, &lci,
    4173             :                                false, false, __func__, t0);
    4174             : 
    4175           0 :         switch (t) {
    4176           0 :         case TYPE_bte:
    4177           0 :                 if (is_bte_nil(*(const bte *)c1) ||
    4178           0 :                     is_bte_nil(*(const bte *)c2) ||
    4179           0 :                     -*(const bte *)c1 > *(const bte *)c2 ||
    4180           0 :                     ((!hinc || !linc) && -*(const bte *)c1 == *(const bte *)c2))
    4181           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4182             :                                        false, false, __func__, t0);
    4183             :                 break;
    4184           0 :         case TYPE_sht:
    4185           0 :                 if (is_sht_nil(*(const sht *)c1) ||
    4186           0 :                     is_sht_nil(*(const sht *)c2) ||
    4187           0 :                     -*(const sht *)c1 > *(const sht *)c2 ||
    4188           0 :                     ((!hinc || !linc) && -*(const sht *)c1 == *(const sht *)c2))
    4189           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4190             :                                        false, false, __func__, t0);
    4191             :                 break;
    4192           0 :         case TYPE_int:
    4193           0 :                 if (is_int_nil(*(const int *)c1) ||
    4194           0 :                     is_int_nil(*(const int *)c2) ||
    4195           0 :                     -*(const int *)c1 > *(const int *)c2 ||
    4196           0 :                     ((!hinc || !linc) && -*(const int *)c1 == *(const int *)c2))
    4197           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4198             :                                        false, false, __func__, t0);
    4199             :                 break;
    4200           0 :         case TYPE_lng:
    4201           0 :                 if (is_lng_nil(*(const lng *)c1) ||
    4202           0 :                     is_lng_nil(*(const lng *)c2) ||
    4203           0 :                     -*(const lng *)c1 > *(const lng *)c2 ||
    4204           0 :                     ((!hinc || !linc) && -*(const lng *)c1 == *(const lng *)c2))
    4205           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4206             :                                        false, false, __func__, t0);
    4207             :                 break;
    4208             : #ifdef HAVE_HGE
    4209           0 :         case TYPE_hge:
    4210           0 :                 if (is_hge_nil(*(const hge *)c1) ||
    4211           0 :                     is_hge_nil(*(const hge *)c2) ||
    4212           0 :                     -*(const hge *)c1 > *(const hge *)c2 ||
    4213           0 :                     ((!hinc || !linc) && -*(const hge *)c1 == *(const hge *)c2))
    4214           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4215             :                                        false, false, __func__, t0);
    4216             :                 break;
    4217             : #endif
    4218           0 :         case TYPE_flt:
    4219           0 :                 if (is_flt_nil(*(const flt *)c1) ||
    4220           0 :                     is_flt_nil(*(const flt *)c2) ||
    4221           0 :                     -*(const flt *)c1 > *(const flt *)c2 ||
    4222           0 :                     ((!hinc || !linc) && -*(const flt *)c1 == *(const flt *)c2))
    4223           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4224             :                                        false, false, __func__, t0);
    4225             :                 break;
    4226           0 :         case TYPE_dbl:
    4227           0 :                 if (is_dbl_nil(*(const dbl *)c1) ||
    4228           0 :                     is_dbl_nil(*(const dbl *)c2) ||
    4229           0 :                     -*(const dbl *)c1 > *(const dbl *)c2 ||
    4230           0 :                     ((!hinc || !linc) && -*(const dbl *)c1 == *(const dbl *)c2))
    4231           0 :                         return nomatch(r1p, r2p, l, r, &lci,
    4232             :                                        false, false, __func__, t0);
    4233             :                 break;
    4234           0 :         default:
    4235           0 :                 GDKerror("unsupported type\n");
    4236           0 :                 return GDK_FAIL;
    4237             :         }
    4238             : 
    4239           0 :         BUN maxsize = joininitresults(r1p, r2p, lcnt, rcnt, false, false,
    4240             :                                       false, false, false, false, estimate);
    4241           0 :         if (maxsize == BUN_NONE)
    4242             :                 return GDK_FAIL;
    4243           0 :         BAT *r1 = *r1p;
    4244           0 :         BAT *r2 = r2p ? *r2p : NULL;
    4245           0 :         BATiter li = bat_iterator(l);
    4246           0 :         BATiter ri = bat_iterator(r);
    4247             : 
    4248           0 :         lvals = (const char *) li.base;
    4249           0 :         rvals = (const char *) ri.base;
    4250           0 :         assert(!r->tvarsized);
    4251             : 
    4252           0 :         assert(lvals != NULL);
    4253           0 :         assert(rvals != NULL);
    4254             : 
    4255           0 :         r1->tkey = true;
    4256           0 :         r1->tsorted = true;
    4257           0 :         r1->trevsorted = true;
    4258           0 :         if (r2) {
    4259           0 :                 r2->tkey = true;
    4260           0 :                 r2->tsorted = true;
    4261           0 :                 r2->trevsorted = true;
    4262             :         }
    4263             : 
    4264             :         /* nested loop implementation for band join */
    4265           0 :         for (BUN lidx = 0; lidx < lcnt; lidx++) {
    4266           0 :                 lo = canditer_next(&lci);
    4267           0 :                 vl = FVALUE(l, lo - l->hseqbase);
    4268           0 :                 if (cmp(vl, nil) == 0)
    4269           0 :                         continue;
    4270             :                 nr = 0;
    4271           0 :                 canditer_reset(&rci);
    4272           0 :                 for (BUN ridx = 0; ridx < rcnt; ridx++) {
    4273           0 :                         ro = canditer_next(&rci);
    4274           0 :                         vr = FVALUE(r, ro - r->hseqbase);
    4275           0 :                         switch (ATOMtype(l->ttype)) {
    4276           0 :                         case TYPE_bte: {
    4277           0 :                                 if (is_bte_nil(*(const bte *) vr))
    4278           0 :                                         continue;
    4279             :                                 sht v1 = (sht) *(const bte *) vr, v2;
    4280             :                                 v2 = v1;
    4281           0 :                                 v1 -= *(const bte *)c1;
    4282           0 :                                 if (*(const bte *)vl <= v1 &&
    4283           0 :                                     (!linc || *(const bte *)vl != v1))
    4284           0 :                                         continue;
    4285           0 :                                 v2 += *(const bte *)c2;
    4286           0 :                                 if (*(const bte *)vl >= v2 &&
    4287           0 :                                     (!hinc || *(const bte *)vl != v2))
    4288           0 :                                         continue;
    4289             :                                 break;
    4290             :                         }
    4291           0 :                         case TYPE_sht: {
    4292           0 :                                 if (is_sht_nil(*(const sht *) vr))
    4293           0 :                                         continue;
    4294           0 :                                 int v1 = (int) *(const sht *) vr, v2;
    4295             :                                 v2 = v1;
    4296           0 :                                 v1 -= *(const sht *)c1;
    4297           0 :                                 if (*(const sht *)vl <= v1 &&
    4298           0 :                                     (!linc || *(const sht *)vl != v1))
    4299           0 :                                         continue;
    4300           0 :                                 v2 += *(const sht *)c2;
    4301           0 :                                 if (*(const sht *)vl >= v2 &&
    4302           0 :                                     (!hinc || *(const sht *)vl != v2))
    4303           0 :                                         continue;
    4304             :                                 break;
    4305             :                         }
    4306           0 :                         case TYPE_int: {
    4307           0 :                                 if (is_int_nil(*(const int *) vr))
    4308           0 :                                         continue;
    4309           0 :                                 lng v1 = (lng) *(const int *) vr, v2;
    4310             :                                 v2 = v1;
    4311           0 :                                 v1 -= *(const int *)c1;
    4312           0 :                                 if (*(const int *)vl <= v1 &&
    4313           0 :                                     (!linc || *(const int *)vl != v1))
    4314           0 :                                         continue;
    4315           0 :                                 v2 += *(const int *)c2;
    4316           0 :                                 if (*(const int *)vl >= v2 &&
    4317           0 :                                     (!hinc || *(const int *)vl != v2))
    4318           0 :                                         continue;
    4319             :                                 break;
    4320             :                         }
    4321             : #ifdef HAVE_HGE
    4322           0 :                         case TYPE_lng: {
    4323           0 :                                 if (is_lng_nil(*(const lng *) vr))
    4324           0 :                                         continue;
    4325           0 :                                 hge v1 = (hge) *(const lng *) vr, v2;
    4326             :                                 v2 = v1;
    4327           0 :                                 v1 -= *(const lng *)c1;
    4328           0 :                                 if (*(const lng *)vl <= v1 &&
    4329           0 :                                     (!linc || *(const lng *)vl != v1))
    4330           0 :                                         continue;
    4331           0 :                                 v2 += *(const lng *)c2;
    4332           0 :                                 if (*(const lng *)vl >= v2 &&
    4333           0 :                                     (!hinc || *(const lng *)vl != v2))
    4334           0 :                                         continue;
    4335             :                                 break;
    4336             :                         }
    4337             : #else
    4338             : #ifdef HAVE___INT128
    4339             :                         case TYPE_lng: {
    4340             :                                 if (is_lng_nil(*(const lng *) vr))
    4341             :                                         continue;
    4342             :                                 __int128 v1 = (__int128) *(const lng *) vr, v2;
    4343             :                                 v2 = v1;
    4344             :                                 v1 -= *(const lng *)c1;
    4345             :                                 if (*(const lng *)vl <= v1 &&
    4346             :                                     (!linc || *(const lng *)vl != v1))
    4347             :                                         continue;
    4348             :                                 v2 += *(const lng *)c2;
    4349             :                                 if (*(const lng *)vl >= v2 &&
    4350             :                                     (!hinc || *(const lng *)vl != v2))
    4351             :                                         continue;
    4352             :                                 break;
    4353             :                         }
    4354             : #else
    4355             :                         case TYPE_lng: {
    4356             :                                 if (is_lng_nil(*(const lng *) vr))
    4357             :                                         continue;
    4358             :                                 lng v1, v2;
    4359             :                                 bool abort_on_error = true;
    4360             :                                 SUB_WITH_CHECK(*(const lng *)vr,
    4361             :                                                *(const lng *)c1,
    4362             :                                                lng, v1,
    4363             :                                                GDK_lng_max,
    4364             :                                                do{if(*(const lng*)c1<0)goto nolmatch;else goto lmatch1;}while(false));
    4365             :                                 if (*(const lng *)vl <= v1 &&
    4366             :                                     (!linc || *(const lng *)vl != v1))
    4367             :                                         continue;
    4368             :                                   lmatch1:
    4369             :                                 ADD_WITH_CHECK(*(const lng *)vr,
    4370             :                                                *(const lng *)c2,
    4371             :                                                lng, v2,
    4372             :                                                GDK_lng_max,
    4373             :                                                do{if(*(const lng*)c2>0)goto nolmatch;else goto lmatch2;}while(false));
    4374             :                                 if (*(const lng *)vl >= v2 &&
    4375             :                                     (!hinc || *(const lng *)vl != v2))
    4376             :                                         continue;
    4377             :                                   lmatch2:
    4378             :                                 break;
    4379             :                                   nolmatch:
    4380             :                                 continue;
    4381             :                         }
    4382             : #endif
    4383             : #endif
    4384             : #ifdef HAVE_HGE
    4385           0 :                         case TYPE_hge: {
    4386           0 :                                 if (is_hge_nil(*(const hge *) vr))
    4387           0 :                                         continue;
    4388             :                                 hge v1, v2;
    4389             :                                 bool abort_on_error = true;
    4390           0 :                                 SUB_WITH_CHECK(*(const hge *)vr,
    4391             :                                                *(const hge *)c1,
    4392             :                                                hge, v1,
    4393             :                                                GDK_hge_max,
    4394             :                                                do{if(*(const hge*)c1<0)goto nohmatch;else goto hmatch1;}while(false));
    4395           0 :                                 if (*(const hge *)vl <= v1 &&
    4396           0 :                                     (!linc || *(const hge *)vl != v1))
    4397           0 :                                         continue;
    4398           0 :                                   hmatch1:
    4399           0 :                                 ADD_WITH_CHECK(*(const hge *)vr,
    4400             :                                                *(const hge *)c2,
    4401             :                                                hge, v2,
    4402             :                                                GDK_hge_max,
    4403             :                                                do{if(*(const hge*)c2>0)goto nohmatch;else goto hmatch2;}while(false));
    4404           0 :                                 if (*(const hge *)vl >= v2 &&
    4405           0 :                                     (!hinc || *(const hge *)vl != v2))
    4406           0 :                                         continue;
    4407           0 :                                   hmatch2:
    4408             :                                 break;
    4409           0 :                                   nohmatch:
    4410           0 :                                 continue;
    4411             :                         }
    4412             : #endif
    4413           0 :                         case TYPE_flt: {
    4414           0 :                                 if (is_flt_nil(*(const flt *) vr))
    4415           0 :                                         continue;
    4416           0 :                                 dbl v1 = (dbl) *(const flt *) vr, v2;
    4417             :                                 v2 = v1;
    4418           0 :                                 v1 -= *(const flt *)c1;
    4419           0 :                                 if (*(const flt *)vl <= v1 &&
    4420           0 :                                     (!linc || *(const flt *)vl != v1))
    4421           0 :                                         continue;
    4422           0 :                                 v2 += *(const flt *)c2;
    4423           0 :                                 if (*(const flt *)vl >= v2 &&
    4424           0 :                                     (!hinc || *(const flt *)vl != v2))
    4425           0 :                                         continue;
    4426             :                                 break;
    4427             :                         }
    4428           0 :                         case TYPE_dbl: {
    4429           0 :                                 if (is_dbl_nil(*(const dbl *) vr))
    4430           0 :                                         continue;
    4431             :                                 dbl v1, v2;
    4432             :                                 bool abort_on_error = true;
    4433           0 :                                 SUB_WITH_CHECK(*(const dbl *)vr,
    4434             :                                                *(const dbl *)c1,
    4435             :                                                dbl, v1,
    4436             :                                                GDK_dbl_max,
    4437             :                                                do{if(*(const dbl*)c1<0)goto nodmatch;else goto dmatch1;}while(false));
    4438           0 :                                 if (*(const dbl *)vl <= v1 &&
    4439           0 :                                     (!linc || *(const dbl *)vl != v1))
    4440           0 :                                         continue;
    4441           0 :                                   dmatch1:
    4442           0 :                                 ADD_WITH_CHECK(*(const dbl *)vr,
    4443             :                                                *(const dbl *)c2,
    4444             :                                                dbl, v2,
    4445             :                                                GDK_dbl_max,
    4446             :                                                do{if(*(const dbl*)c2>0)goto nodmatch;else goto dmatch2;}while(false));
    4447           0 :                                 if (*(const dbl *)vl >= v2 &&
    4448           0 :                                     (!hinc || *(const dbl *)vl != v2))
    4449           0 :                                         continue;
    4450           0 :                                   dmatch2:
    4451             :                                 break;
    4452           0 :                                   nodmatch:
    4453           0 :                                 continue;
    4454             :                         }
    4455             :                         }
    4456           0 :                         if (maybeextend(r1, r2, 1, lci.next, lci.ncand, maxsize) != GDK_SUCCEED)
    4457           0 :                                 goto bailout;
    4458           0 :                         if (BATcount(r1) > 0) {
    4459           0 :                                 if (r2 && lastr + 1 != ro)
    4460           0 :                                         r2->tseqbase = oid_nil;
    4461           0 :                                 if (nr == 0) {
    4462           0 :                                         r1->trevsorted = false;
    4463           0 :                                         if (r2 == NULL) {
    4464             :                                                 /* nothing */
    4465           0 :                                         } else if (lastr > ro) {
    4466           0 :                                                 r2->tsorted = false;
    4467           0 :                                                 r2->tkey = false;
    4468           0 :                                         } else if (lastr < ro) {
    4469           0 :                                                 r2->trevsorted = false;
    4470             :                                         } else {
    4471           0 :                                                 r2->tkey = false;
    4472             :                                         }
    4473             :                                 }
    4474             :                         }
    4475           0 :                         APPEND(r1, lo);
    4476           0 :                         if (r2) {
    4477           0 :                                 APPEND(r2, ro);
    4478             :                         }
    4479             :                         lastr = ro;
    4480           0 :                         nr++;
    4481             :                 }
    4482           0 :                 if (nr > 1) {
    4483           0 :                         r1->tkey = false;
    4484           0 :                         r1->tseqbase = oid_nil;
    4485           0 :                         if (r2) {
    4486           0 :                                 r2->trevsorted = false;
    4487             :                         }
    4488           0 :                 } else if (nr == 0) {
    4489           0 :                         lskipped = BATcount(r1) > 0;
    4490           0 :                 } else if (lskipped) {
    4491           0 :                         r1->tseqbase = oid_nil;
    4492             :                 }
    4493             :         }
    4494             :         /* also set other bits of heap to correct value to indicate size */
    4495           0 :         BATsetcount(r1, BATcount(r1));
    4496           0 :         if (r2) {
    4497           0 :                 BATsetcount(r2, BATcount(r2));
    4498           0 :                 assert(BATcount(r1) == BATcount(r2));
    4499             :         }
    4500           0 :         if (BATcount(r1) > 0) {
    4501           0 :                 if (BATtdense(r1))
    4502           0 :                         r1->tseqbase = ((oid *) r1->theap->base)[0];
    4503           0 :                 if (r2 && BATtdense(r2))
    4504           0 :                         r2->tseqbase = ((oid *) r2->theap->base)[0];
    4505             :         } else {
    4506           0 :                 r1->tseqbase = 0;
    4507           0 :                 if (r2) {
    4508           0 :                         r2->tseqbase = 0;
    4509             :                 }
    4510             :         }
    4511           0 :         bat_iterator_end(&li);
    4512           0 :         bat_iterator_end(&ri);
    4513           0 :         TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
    4514             :                   ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
    4515             :                   " -> " ALGOBATFMT "," ALGOOPTBATFMT
    4516             :                   " (" LLFMT "usec)\n",
    4517             :                   ALGOBATPAR(l), ALGOBATPAR(r),
    4518             :                   ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
    4519             :                   ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
    4520             :                   GDKusec() - t0);
    4521             :         return GDK_SUCCEED;
    4522             : 
    4523             :   bailout:
    4524           0 :         bat_iterator_end(&li);
    4525           0 :         bat_iterator_end(&ri);
    4526           0 :         BBPreclaim(r1);
    4527           0 :         BBPreclaim(r2);
    4528           0 :         return GDK_FAIL;
    4529             : }
    4530             : 
    4531             : gdk_return
    4532         156 : BATrangejoin(BAT **r1p, BAT **r2p, BAT *l, BAT *rl, BAT *rh,
    4533             :              BAT *sl, BAT *sr, bool linc, bool hinc, bool anti, bool symmetric,
    4534             :              BUN estimate)
    4535             : {
    4536             :         struct canditer lci, rci;
    4537         156 :         BAT *r1 = NULL, *r2 = NULL;
    4538             :         BUN maxsize;
    4539             :         lng t0 = 0;
    4540             : 
    4541         156 :         TRC_DEBUG_IF(ALGO) t0 = GDKusec();
    4542         156 :         *r1p = NULL;
    4543         156 :         if (r2p) {
    4544         131 :                 *r2p = NULL;
    4545             :         }
    4546         156 :         if (joinparamcheck(l, rl, rh, sl, sr, __func__) != GDK_SUCCEED)
    4547             :                 return GDK_FAIL;
    4548         297 :         if (canditer_init(&lci, l, sl) == 0 ||
    4549         141 :             canditer_init(&rci, rl, sr) == 0 ||
    4550         130 :             (l->ttype == TYPE_void && is_oid_nil(l->tseqbase)) ||
    4551         130 :             ((rl->ttype == TYPE_void && is_oid_nil(rl->tseqbase)) &&
    4552           0 :              (rh->ttype == TYPE_void && is_oid_nil(rh->tseqbase)))) {
    4553             :                 /* trivial: empty input */
    4554          26 :                 return nomatch(r1p, r2p, l, rl, &lci, false, false,
    4555             :                                __func__, t0);
    4556             :         }
    4557         130 :         if (rl->ttype == TYPE_void && is_oid_nil(rl->tseqbase)) {
    4558           0 :                 if (!anti)
    4559           0 :                         return nomatch(r1p, r2p, l, rl, &lci, false, false,
    4560             :                                        __func__, t0);
    4561           0 :                 return thetajoin(r1p, r2p, l, rh, sl, sr, MASK_GT, estimate,
    4562             :                                  __func__, t0);
    4563             :         }
    4564         130 :         if (rh->ttype == TYPE_void && is_oid_nil(rh->tseqbase)) {
    4565           0 :                 if (!anti)
    4566           0 :                         return nomatch(r1p, r2p, l, rl, &lci, false, false,
    4567             :                                        __func__, t0);
    4568           0 :                 return thetajoin(r1p, r2p, l, rl, sl, sr, MASK_LT, estimate,
    4569             :                                  __func__, t0);
    4570             :         }
    4571             : 
    4572         149 :         if ((maxsize = joininitresults(&r1, r2p ? &r2 : NULL, sl ? BATcount(sl) : BATcount(l), sr ? BATcount(sr) : BATcount(rl), false, false, false, false, false, false, estimate)) == BUN_NONE)
    4573             :                 return GDK_FAIL;
    4574         129 :         *r1p = r1;
    4575         129 :         if (r2p) {
    4576         110 :                 *r2p = r2;
    4577             :         }
    4578         129 :         if (maxsize == 0)
    4579             :                 return GDK_SUCCEED;
    4580             : 
    4581             :         /* note, the rangejoin implementation is in gdk_select.c since
    4582             :          * it uses the imprints code there */
    4583         130 :         return rangejoin(r1, r2, l, rl, rh, &lci, &rci, linc, hinc, anti, symmetric, maxsize);
    4584             : }

Generated by: LCOV version 1.14