Line data Source code
1 : /*
2 : * SPDX-License-Identifier: MPL-2.0
3 : *
4 : * This Source Code Form is subject to the terms of the Mozilla Public
5 : * License, v. 2.0. If a copy of the MPL was not distributed with this
6 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 : *
8 : * Copyright 2024, 2025 MonetDB Foundation;
9 : * Copyright August 2008 - 2023 MonetDB B.V.;
10 : * Copyright 1997 - July 2008 CWI.
11 : */
12 :
13 : #include "monetdb_config.h"
14 : #include "gdk.h"
15 : #include "gdk_private.h"
16 : #include "gdk_calc_private.h"
17 :
18 : /*
19 : * All join variants produce some sort of join on two input BATs,
20 : * optionally subject to up to two candidate lists. Only values in
21 : * the input BATs that are mentioned in the associated candidate list
22 : * (if provided) are eligible. They all return two output BATs in the
23 : * first two arguments. The join operations differ in the way in
24 : * which tuples from the two inputs are matched.
25 : *
26 : * The outputs consist of two aligned BATs (i.e. same length and same
27 : * hseqbase (0@0)) that contain the OIDs of the input BATs that match.
28 : * The candidate lists, if given, contain the OIDs of the associated
29 : * input BAT which must be considered for matching. The input BATs
30 : * must have the same type.
31 : *
32 : * All functions also have a parameter nil_matches which indicates
33 : * whether NIL must be considered an ordinary value that can match, or
34 : * whether NIL must be considered to never match.
35 : *
36 : * The join functions that are provided here are:
37 : * BATjoin
38 : * normal equi-join
39 : * BATleftjoin
40 : * normal equi-join, but the left output is sorted
41 : * BATouterjoin
42 : * equi-join, but the left output is sorted, and if there is no
43 : * match for a value in the left input, there is still an output
44 : * with NIL in the right output
45 : * BATsemijoin
46 : * equi-join, but the left output is sorted, and if there are
47 : * multiple matches, only one is returned (i.e., the left output
48 : * is also key, making it a candidate list)
49 : * BATmarkjoin
50 : * equi-join, but the left output is sorted, if there is no
51 : * match for a value in the left input, there is still an output
52 : * with NIL in the right output, and there is a third output column
53 : * containing a flag that indicates the "certainty" of the match: 1
54 : * there is a match, 0, there is no match and there are no NIL
55 : * values, NIL, there is no match but there are NIL values
56 : * BATthetajoin
57 : * theta-join: an extra operator must be provided encoded as an
58 : * integer (macros JOIN_EQ, JOIN_NE, JOIN_LT, JOIN_LE, JOIN_GT,
59 : * JOIN_GE); values match if the left input has the given
60 : * relationship with the right input; order of the outputs is not
61 : * guaranteed
62 : * BATbandjoin
63 : * band-join: two extra input values (c1, c2) must be provided as
64 : * well as Booleans (li, hi) that indicate whether the value
65 : * ranges are inclusive or not; values in the left and right
66 : * inputs match if right - c1 <[=] left <[=] right + c2; if c1 or
67 : * c2 is NIL, there are no matches
68 : * BATrangejoin
69 : * range-join: the right input consists of two aligned BATs,
70 : * values match if the left value is between two corresponding
71 : * right values; two extra Boolean parameters, li and hi,
72 : * indicate whether equal values match
73 : *
74 : * In addition to these functions, there are two more functions that
75 : * are closely related:
76 : * BATintersect
77 : * intersection: return a candidate list with OIDs of tuples in
78 : * the left input whose value occurs in the right input
79 : * BATdiff
80 : * difference: return a candidate list with OIDs of tuples in the
81 : * left input whose value does not occur in the right input
82 : */
83 :
84 : /* Perform a bunch of sanity checks on the inputs to a join. */
85 : static gdk_return
86 663483 : joinparamcheck(BAT *l, BAT *r1, BAT *r2, BAT *sl, BAT *sr, const char *func)
87 : {
88 1678289 : if (ATOMtype(l->ttype) != ATOMtype(r1->ttype) ||
89 294 : (r2 && ATOMtype(l->ttype) != ATOMtype(r2->ttype))) {
90 0 : GDKerror("%s: inputs not compatible.\n", func);
91 0 : return GDK_FAIL;
92 : }
93 147 : if (r2 &&
94 147 : (BATcount(r1) != BATcount(r2) || r1->hseqbase != r2->hseqbase)) {
95 0 : GDKerror("%s: right inputs not aligned.\n", func);
96 0 : return GDK_FAIL;
97 : }
98 663483 : if ((sl && !BATiscand(sl)) || (sr && !BATiscand(sr))) {
99 0 : GDKerror("%s: argument not a candidate list.\n", func);
100 0 : return GDK_FAIL;
101 : }
102 : return GDK_SUCCEED;
103 : }
104 :
105 : #define INCRSIZELOG (8 + (SIZEOF_OID / 2))
106 : #define INCRSIZE (1 << INCRSIZELOG)
107 :
108 : /* Create the result bats for a join, returns the absolute maximum
109 : * number of outputs that could possibly be generated. */
110 : static BUN
111 86218 : joininitresults(BAT **r1p, BAT **r2p, BAT **r3p, BUN lcnt, BUN rcnt,
112 : bool lkey, bool rkey, bool semi, bool nil_on_miss,
113 : bool only_misses, bool min_one, BUN estimate)
114 : {
115 86218 : BAT *r1 = NULL, *r2 = NULL, *r3 = NULL;
116 86218 : BUN maxsize, size;
117 :
118 : /* if nil_on_miss is set, we really need a right output */
119 86218 : assert(!nil_on_miss || r2p != NULL || r3p != NULL);
120 :
121 86218 : lkey |= lcnt <= 1;
122 86218 : rkey |= rcnt <= 1;
123 :
124 86218 : *r1p = NULL;
125 86218 : if (r2p)
126 32399 : *r2p = NULL;
127 86218 : if (r3p)
128 326 : *r3p = NULL;
129 86218 : if (lcnt == 0) {
130 : /* there is nothing to match */
131 : maxsize = 0;
132 71380 : } else if (!only_misses && !nil_on_miss && rcnt == 0) {
133 : /* if right is empty, we have no hits, so if we don't
134 : * want misses, the result is empty */
135 : maxsize = 0;
136 71434 : } else if (rkey | semi | only_misses) {
137 : /* each entry left matches at most one on right, in
138 : * case nil_on_miss is also set, each entry matches
139 : * exactly one (see below) */
140 : maxsize = lcnt;
141 46904 : } else if (lkey) {
142 : /* each entry on right is matched at most once */
143 11467 : if (nil_on_miss) {
144 : /* one entry left could match all right, and
145 : * all other entries left match nil */
146 15 : maxsize = lcnt + rcnt - 1;
147 : } else {
148 : maxsize = rcnt;
149 : }
150 35437 : } else if (rcnt == 0) {
151 : /* nil_on_miss must be true due to previous checks, so
152 : * all values on left miss */
153 : maxsize = lcnt;
154 35473 : } else if (BUN_MAX / lcnt >= rcnt) {
155 : /* in the worst case we have a full cross product */
156 35514 : maxsize = lcnt * rcnt;
157 : } else {
158 : /* a BAT cannot grow larger than BUN_MAX */
159 : maxsize = BUN_MAX;
160 : }
161 86218 : size = estimate == BUN_NONE ? lcnt < rcnt ? lcnt : rcnt : estimate;
162 86218 : if (size < INCRSIZE)
163 : size = INCRSIZE;
164 86218 : if (size > maxsize)
165 : size = maxsize;
166 86218 : if ((rkey | semi | only_misses) & nil_on_miss) {
167 : /* see comment above: each entry left matches exactly
168 : * once */
169 126 : size = maxsize;
170 : }
171 86218 : if (min_one && size < lcnt)
172 0 : size = lcnt;
173 :
174 86218 : if (maxsize == 0) {
175 14762 : r1 = BATdense(0, 0, 0);
176 14671 : if (r1 == NULL) {
177 : return BUN_NONE;
178 : }
179 14671 : if (r2p) {
180 644 : r2 = BATdense(0, 0, 0);
181 668 : if (r2 == NULL) {
182 0 : BBPreclaim(r1);
183 0 : return BUN_NONE;
184 : }
185 668 : *r2p = r2;
186 : }
187 14695 : if (r3p) {
188 0 : r3 = COLnew(0, TYPE_bit, 0, TRANSIENT);
189 0 : if (r3 == NULL) {
190 0 : BBPreclaim(r1);
191 0 : BBPreclaim(r2);
192 0 : if (r2p)
193 0 : *r2p = NULL;
194 0 : return BUN_NONE;
195 : }
196 0 : *r3p = r3;
197 : }
198 14695 : *r1p = r1;
199 14695 : return 0;
200 : }
201 :
202 71456 : r1 = COLnew(0, TYPE_oid, size, TRANSIENT);
203 71188 : if (r1 == NULL) {
204 : return BUN_NONE;
205 : }
206 71188 : r1->tnil = false;
207 71188 : r1->tnonil = true;
208 71188 : r1->tkey = true;
209 71188 : r1->tsorted = true;
210 71188 : r1->trevsorted = true;
211 71188 : r1->tseqbase = 0;
212 71188 : r1->theap->dirty = true;
213 71188 : *r1p = r1;
214 71188 : if (r2p) {
215 31555 : r2 = COLnew(0, TYPE_oid, size, TRANSIENT);
216 31596 : if (r2 == NULL) {
217 0 : BBPreclaim(r1);
218 0 : return BUN_NONE;
219 : }
220 31596 : r2->tnil = false;
221 31596 : r2->tnonil = true;
222 31596 : r2->tkey = true;
223 31596 : r2->tsorted = true;
224 31596 : r2->trevsorted = true;
225 31596 : r2->tseqbase = 0;
226 31596 : r2->theap->dirty = true;
227 31596 : *r2p = r2;
228 : }
229 71229 : if (r3p) {
230 120 : BAT *r3 = COLnew(0, TYPE_bit, size, TRANSIENT);
231 119 : if (r3 == NULL) {
232 0 : BBPreclaim(r1);
233 0 : BBPreclaim(r2);
234 0 : return BUN_NONE;
235 : }
236 119 : r3->tnil = false;
237 119 : r3->tnonil = true;
238 119 : r3->tkey = false;
239 119 : r3->tsorted = false;
240 119 : r3->trevsorted = false;
241 119 : r3->tseqbase = oid_nil;
242 119 : r3->theap->dirty = true;
243 119 : *r3p = r3;
244 : }
245 : return maxsize;
246 : }
247 :
248 : #define VALUE(s, x) (s##vars ? \
249 : s##vars + VarHeapVal(s##vals, (x), s##i.width) : \
250 : s##vals ? (const char *) s##vals + ((x) * s##i.width) : \
251 : (s##val = BUNtoid(s, (x)), (const char *) &s##val))
252 : #define FVALUE(s, x) ((const char *) s##vals + ((x) * s##i.width))
253 :
254 : #define APPEND(b, o) (((oid *) b->theap->base)[b->batCount++] = (o))
255 :
256 : static inline gdk_return
257 187655085 : maybeextend(BAT *restrict r1, BAT *restrict r2, BAT *restrict r3,
258 : BUN cnt, BUN lcur, BUN lcnt, BUN maxsize)
259 : {
260 187655085 : if (BATcount(r1) + cnt > BATcapacity(r1)) {
261 : /* make some extra space by extrapolating how much more
262 : * we need (fraction of l we've seen so far is used to
263 : * estimate a new size but with a shallow slope so that
264 : * a skewed join doesn't overwhelm, whilst making sure
265 : * there is somewhat significant progress) */
266 2148 : BUN newcap = (BUN) (lcnt / (lcnt / 4.0 + lcur * .75) * (BATcount(r1) + cnt));
267 2148 : newcap = (newcap + INCRSIZE - 1) & ~(((BUN) 1 << INCRSIZELOG) - 1);
268 2148 : if (newcap < cnt + BATcount(r1))
269 0 : newcap = cnt + BATcount(r1) + INCRSIZE;
270 : /* if close to maxsize, then just use maxsize */
271 2148 : if (newcap + INCRSIZE > maxsize)
272 163 : newcap = maxsize;
273 : /* make sure heap.free is set properly before
274 : * extending */
275 2148 : BATsetcount(r1, BATcount(r1));
276 2149 : if (BATextend(r1, newcap) != GDK_SUCCEED)
277 : return GDK_FAIL;
278 2150 : if (r2) {
279 1348 : BATsetcount(r2, BATcount(r2));
280 1348 : if (BATextend(r2, newcap) != GDK_SUCCEED)
281 : return GDK_FAIL;
282 1348 : assert(BATcapacity(r1) == BATcapacity(r2));
283 : }
284 2150 : if (r3) {
285 0 : BATsetcount(r3, BATcount(r3));
286 0 : if (BATextend(r3, newcap) != GDK_SUCCEED)
287 : return GDK_FAIL;
288 0 : assert(BATcapacity(r1) == BATcapacity(r3));
289 : }
290 : }
291 : return GDK_SUCCEED;
292 : }
293 :
294 : /* Return BATs through r1p, r2p, and r3p for the case that there is no
295 : * match between l and r, taking all flags into consideration.
296 : *
297 : * This means, if nil_on_miss is set or only_misses is set, *r1p is a
298 : * copy of the left candidate list or a dense list of all "head"
299 : * values of l, and *r2p (if r2p is not NULL) is all nil. If neither
300 : * of those flags is set, the result is two empty BATs. */
301 : static gdk_return
302 505441 : nomatch(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
303 : struct canditer *restrict lci, bit defmark,
304 : bool nil_on_miss, bool only_misses, const char *func, lng t0)
305 : {
306 505441 : BAT *r1, *r2 = NULL, *r3 = NULL;
307 :
308 505441 : MT_thread_setalgorithm(__func__);
309 505827 : if (lci->ncand == 0 || !(nil_on_miss | only_misses)) {
310 : /* return empty BATs */
311 486651 : if ((r1 = BATdense(0, 0, 0)) == NULL)
312 : return GDK_FAIL;
313 486110 : if (r2p) {
314 320041 : if ((r2 = BATdense(0, 0, 0)) == NULL) {
315 0 : BBPreclaim(r1);
316 0 : return GDK_FAIL;
317 : }
318 320839 : *r2p = r2;
319 : }
320 486908 : if (r3p) {
321 18976 : if ((r3 = COLnew(0, TYPE_bit, 0, TRANSIENT)) == NULL) {
322 0 : BBPreclaim(r1);
323 0 : BBPreclaim(r2);
324 0 : return GDK_FAIL;
325 : }
326 19081 : *r3p = r3;
327 : }
328 : } else {
329 19176 : r1 = canditer_slice(lci, 0, lci->ncand);
330 19173 : if (r2p) {
331 23 : if ((r2 = BATconstant(0, TYPE_void, &oid_nil, lci->ncand, TRANSIENT)) == NULL) {
332 0 : BBPreclaim(r1);
333 0 : return GDK_FAIL;
334 : }
335 23 : *r2p = r2;
336 : }
337 19173 : if (r3p) {
338 67 : if ((r3 = BATconstant(0, TYPE_bit, &defmark, lci->ncand, TRANSIENT)) == NULL) {
339 0 : BBPreclaim(r1);
340 0 : BBPreclaim(r2);
341 0 : return GDK_FAIL;
342 : }
343 68 : *r3p = r3;
344 : }
345 : }
346 506187 : *r1p = r1;
347 506187 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ",r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT
348 : ",nil_on_miss=%s,only_misses=%s"
349 : " - > " ALGOBATFMT "," ALGOOPTBATFMT "," ALGOOPTBATFMT
350 : " (%s -- " LLFMT "usec)\n",
351 : ALGOBATPAR(l), ALGOBATPAR(r), ALGOOPTBATPAR(lci->s),
352 : nil_on_miss ? "true" : "false",
353 : only_misses ? "true" : "false",
354 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2), ALGOOPTBATPAR(r3),
355 : func, GDKusec() - t0);
356 : return GDK_SUCCEED;
357 : }
358 :
359 : /* Implementation of join where there is a single value (possibly
360 : * repeated multiple times) on the left. This means we can use a
361 : * point select to find matches in the right column. */
362 : static gdk_return
363 52992 : selectjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
364 : struct canditer *lci, struct canditer *rci,
365 : bool nil_matches, bool nil_on_miss, bool semi, bool max_one, bool min_one,
366 : lng t0, bool swapped, const char *reason)
367 : {
368 52992 : BATiter li = bat_iterator(l);
369 53011 : const void *v;
370 53011 : BAT *bn = NULL;
371 53011 : BAT *r1 = NULL;
372 53011 : BAT *r2 = NULL;
373 53011 : BUN bncount;
374 :
375 53011 : assert(lci->ncand > 0);
376 53011 : assert(lci->ncand == 1 || (li.sorted && li.revsorted));
377 :
378 53011 : size_t counter = 0;
379 53011 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
380 :
381 53013 : MT_thread_setalgorithm(__func__);
382 53008 : oid o = canditer_next(lci);
383 52986 : v = BUNtail(li, o - l->hseqbase);
384 :
385 103113 : if (!nil_matches &&
386 50125 : (*ATOMcompare(li.type))(v, ATOMnilptr(li.type)) == 0) {
387 : /* NIL doesn't match anything */
388 196 : bat_iterator_end(&li);
389 196 : gdk_return rc = nomatch(r1p, r2p, r3p, l, r, lci, bit_nil, nil_on_miss,
390 : false, reason, t0);
391 196 : return rc;
392 : }
393 :
394 52792 : bn = BATselect(r, rci->s, v, NULL, true, true, false, false);
395 52688 : bat_iterator_end(&li);
396 52778 : if (bn == NULL) {
397 : return GDK_FAIL;
398 : }
399 52778 : bncount = BATcount(bn);
400 52778 : if (bncount == 0) {
401 14106 : BBPreclaim(bn);
402 14086 : if (min_one) {
403 0 : GDKerror("not enough matches");
404 0 : return GDK_FAIL;
405 : }
406 14086 : if (!nil_on_miss) {
407 13891 : assert(r3p == NULL);
408 13891 : return nomatch(r1p, r2p, r3p, l, r, lci, 0, nil_on_miss,
409 : false, reason, t0);
410 : }
411 : /* special case: return nil on RHS */
412 : bncount = 1;
413 : bn = NULL;
414 : }
415 38672 : if (bncount > 1) {
416 1940 : if (semi)
417 713 : bncount = 1;
418 1940 : if (max_one) {
419 16 : GDKerror("more than one match");
420 16 : goto bailout;
421 : }
422 : }
423 38851 : r1 = COLnew(0, TYPE_oid, lci->ncand * bncount, TRANSIENT);
424 38847 : if (r1 == NULL)
425 0 : goto bailout;
426 38847 : r1->tsorted = true;
427 38847 : r1->trevsorted = lci->ncand == 1;
428 38847 : r1->tseqbase = bncount == 1 && lci->tpe == cand_dense ? o : oid_nil;
429 38847 : r1->tkey = bncount == 1;
430 38847 : r1->tnil = false;
431 38847 : r1->tnonil = true;
432 38847 : if (bn == NULL) {
433 : /* left outer join, no match, we're returning nil in r2 */
434 195 : oid *o1p = (oid *) Tloc(r1, 0);
435 195 : BUN p, q = bncount;
436 :
437 195 : if (r2p) {
438 2 : r2 = BATconstant(0, TYPE_void, &oid_nil, lci->ncand * bncount, TRANSIENT);
439 2 : if (r2 == NULL)
440 0 : goto bailout;
441 2 : *r2p = r2;
442 : }
443 390 : do {
444 390 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
445 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
446 780 : for (p = 0; p < q; p++) {
447 390 : *o1p++ = o;
448 : }
449 390 : o = canditer_next(lci);
450 390 : } while (!is_oid_nil(o));
451 : } else {
452 38652 : oid *o1p = (oid *) Tloc(r1, 0);
453 38652 : oid *o2p;
454 38652 : BUN p, q = bncount;
455 :
456 38652 : if (r2p) {
457 33145 : r2 = COLnew(0, TYPE_oid, lci->ncand * bncount, TRANSIENT);
458 33156 : if (r2 == NULL)
459 0 : goto bailout;
460 33156 : r2->tsorted = lci->ncand == 1 || bncount == 1;
461 33156 : r2->trevsorted = bncount == 1;
462 33156 : r2->tseqbase = lci->ncand == 1 && BATtdense(bn) ? bn->tseqbase : oid_nil;
463 33156 : r2->tkey = lci->ncand == 1;
464 33156 : r2->tnil = false;
465 33156 : r2->tnonil = true;
466 33156 : *r2p = r2;
467 33156 : o2p = (oid *) Tloc(r2, 0);
468 : } else {
469 : o2p = NULL;
470 : }
471 :
472 38663 : if (BATtdense(bn)) {
473 : oid bno = bn->tseqbase;
474 :
475 1345325 : do {
476 1345325 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
477 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
478 2744436 : for (p = 0; p < q; p++) {
479 1399111 : *o1p++ = o;
480 : }
481 1345325 : if (o2p) {
482 435644 : for (p = 0; p < q; p++) {
483 244639 : *o2p++ = bno + p;
484 : }
485 : }
486 1345325 : o = canditer_next(lci);
487 1345326 : } while (!is_oid_nil(o));
488 : } else {
489 293 : const oid *bnp = (const oid *) Tloc(bn, 0);
490 :
491 148762 : do {
492 148762 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
493 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
494 6224579 : for (p = 0; p < q; p++) {
495 6075817 : *o1p++ = o;
496 : }
497 148762 : if (o2p) {
498 6336240 : for (p = 0; p < q; p++) {
499 6180827 : *o2p++ = bnp[p];
500 : }
501 : }
502 148762 : o = canditer_next(lci);
503 148766 : } while (!is_oid_nil(o));
504 : }
505 38668 : if (r2)
506 33155 : BATsetcount(r2, lci->ncand * bncount);
507 : }
508 38866 : BATsetcount(r1, lci->ncand * bncount);
509 38868 : *r1p = r1;
510 38868 : BAT *r3 = NULL;
511 38868 : if (r3p) {
512 240 : bit mark;
513 240 : if (bn) {
514 : /* there is a match */
515 47 : mark = 1;
516 193 : } else if (r->tnonil) {
517 : /* no match, no NIL in r */
518 185 : mark = 0;
519 : } else {
520 : /* no match, search for NIL in r */
521 8 : BAT *n = BATselect(r, rci->s, ATOMnilptr(r->ttype), NULL, true, true, false, false);
522 9 : if (n == NULL)
523 0 : goto bailout;
524 9 : mark = BATcount(n) == 0 ? 0 : bit_nil;
525 9 : BBPreclaim(n);
526 : }
527 241 : r3 = BATconstant(0, TYPE_bit, &mark, lci->ncand, TRANSIENT);
528 241 : if (r3 == NULL)
529 0 : goto bailout;
530 241 : *r3p = r3;
531 : }
532 38869 : BBPreclaim(bn);
533 38847 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
534 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
535 : "sr=" ALGOOPTBATFMT ",nil_matches=%s;%s %s "
536 : "-> " ALGOBATFMT "," ALGOOPTBATFMT "," ALGOOPTBATFMT
537 : " (" LLFMT "usec)\n",
538 : ALGOBATPAR(l), ALGOBATPAR(r),
539 : ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
540 : nil_matches ? "true" : "false",
541 : swapped ? " swapped" : "", reason,
542 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2), ALGOOPTBATPAR(r3),
543 : GDKusec() - t0);
544 :
545 : return GDK_SUCCEED;
546 :
547 16 : bailout:
548 16 : BBPreclaim(bn);
549 16 : BBPreclaim(r1);
550 16 : BBPreclaim(r2);
551 16 : if (r2p)
552 15 : *r2p = NULL;
553 : return GDK_FAIL;
554 : }
555 :
556 : #if SIZEOF_OID == SIZEOF_INT
557 : #define binsearch_oid(indir, offset, vals, lo, hi, v, ordering, last) binsearch_int(indir, offset, (const int *) vals, lo, hi, (int) (v), ordering, last)
558 : #endif
559 : #if SIZEOF_OID == SIZEOF_LNG
560 : #define binsearch_oid(indir, offset, vals, lo, hi, v, ordering, last) binsearch_lng(indir, offset, (const lng *) vals, lo, hi, (lng) (v), ordering, last)
561 : #endif
562 :
563 : /* Implementation of join where the right-hand side is dense, and if
564 : * there is a right candidate list, it too is dense. This means there
565 : * are no NIL values in r. In case nil_on_miss is not set, we use a
566 : * range select (BATselect) to find the matching values in the left
567 : * column and then calculate the corresponding matches from the right.
568 : * If nil_on_miss is set, we need to do some more work. The latter is
569 : * also the only case in which r3p van be set. */
570 : static gdk_return
571 26825 : mergejoin_void(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
572 : struct canditer *restrict lci, struct canditer *restrict rci,
573 : bool nil_on_miss, bool only_misses, lng t0, bool swapped,
574 : const char *reason)
575 : {
576 26825 : oid lo, hi;
577 26825 : BUN i;
578 26825 : oid o, *o1p = NULL, *o2p = NULL;
579 26825 : bit *m3p = NULL;
580 26825 : BAT *r1 = NULL, *r2 = NULL, *r3 = NULL;
581 26825 : bool ltsorted = false, ltrevsorted = false, ltkey = false;
582 :
583 : /* r is dense, and if there is a candidate list, it too is
584 : * dense. This means we don't have to do any searches, we
585 : * only need to compare ranges to know whether a value from l
586 : * has a match in r */
587 38672 : assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
588 26825 : assert(r->tsorted || r->trevsorted);
589 26825 : assert(BATcount(l) > 0);
590 26825 : assert(rci->tpe == cand_dense);
591 26825 : assert(BATcount(r) > 0);
592 :
593 26825 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
594 :
595 26835 : MT_thread_setalgorithm(__func__);
596 : /* figure out range [lo..hi) of values in r that we need to match */
597 26849 : lo = r->tseqbase;
598 26849 : hi = lo + BATcount(r);
599 : /* restrict [lo..hi) range further using candidate list */
600 26849 : if (rci->seq > r->hseqbase)
601 0 : lo += rci->seq - r->hseqbase;
602 26849 : if (rci->seq + rci->ncand < r->hseqbase + BATcount(r))
603 0 : hi -= r->hseqbase + BATcount(r) - rci->seq - rci->ncand;
604 :
605 : /* at this point, the matchable values in r are [lo..hi) */
606 26849 : if (!nil_on_miss) {
607 26849 : assert(r3p == NULL);
608 26849 : r1 = BATselect(l, lci->s, &lo, &hi, true, false, only_misses, false);
609 26773 : if (r1 == NULL)
610 : return GDK_FAIL;
611 26773 : if (only_misses && !l->tnonil) {
612 : /* also look for NILs */
613 0 : r2 = BATselect(l, lci->s, &oid_nil, NULL, true, false, false, false);
614 0 : if (r2 == NULL) {
615 0 : BBPreclaim(r1);
616 0 : return GDK_FAIL;
617 : }
618 0 : if (BATcount(r2) > 0) {
619 0 : BAT *mg = BATmergecand(r1, r2);
620 0 : BBPunfix(r1->batCacheid);
621 0 : BBPunfix(r2->batCacheid);
622 0 : r1 = mg;
623 0 : if (r1 == NULL)
624 : return GDK_FAIL;
625 : } else {
626 0 : BBPunfix(r2->batCacheid);
627 : }
628 : r2 = NULL;
629 : }
630 26773 : *r1p = r1;
631 26773 : if (r2p == NULL)
632 25608 : goto doreturn2;
633 1165 : if (BATcount(r1) == 0) {
634 52 : r2 = BATdense(0, 0, 0);
635 52 : if (r2 == NULL) {
636 0 : BBPreclaim(r1);
637 0 : return GDK_FAIL;
638 : }
639 1113 : } else if (BATtdense(r1) && BATtdense(l)) {
640 83 : r2 = BATdense(0, l->tseqbase + r1->tseqbase - l->hseqbase + r->hseqbase - r->tseqbase, BATcount(r1));
641 83 : if (r2 == NULL) {
642 0 : BBPreclaim(r1);
643 0 : return GDK_FAIL;
644 : }
645 : } else {
646 1030 : r2 = COLnew(0, TYPE_oid, BATcount(r1), TRANSIENT);
647 1053 : if (r2 == NULL) {
648 0 : BBPreclaim(r1);
649 0 : return GDK_FAIL;
650 : }
651 1053 : BATiter li = bat_iterator(l);
652 1035 : const oid *lp = (const oid *) li.base;
653 1035 : const oid *o1p = (const oid *) Tloc(r1, 0);
654 1035 : oid *o2p = (oid *) Tloc(r2, 0);
655 1035 : hi = BATcount(r1);
656 1035 : if (complex_cand(l)) {
657 : /* this is actually generic code */
658 0 : for (o = 0; o < hi; o++)
659 0 : o2p[o] = BUNtoid(l, BUNtoid(r1, o) - l->hseqbase) - r->tseqbase + r->hseqbase;
660 1035 : } else if (BATtdense(r1)) {
661 475 : lo = r1->tseqbase - l->hseqbase;
662 475 : if (r->tseqbase == r->hseqbase) {
663 466 : memcpy(o2p, lp + lo, hi * SIZEOF_OID);
664 : } else {
665 9 : hi += lo;
666 5085015 : for (o = 0; lo < hi; o++, lo++) {
667 5085006 : o2p[o] = lp[lo] - r->tseqbase + r->hseqbase;
668 : }
669 : }
670 560 : } else if (BATtdense(l)) {
671 0 : for (o = 0; o < hi; o++) {
672 0 : o2p[o] = o1p[o] - l->hseqbase + li.tseq - r->tseqbase + r->hseqbase;
673 : }
674 : } else {
675 46627700 : for (o = 0; o < hi; o++) {
676 46627140 : o2p[o] = lp[o1p[o] - l->hseqbase] - r->tseqbase + r->hseqbase;
677 : }
678 : }
679 1035 : r2->tkey = li.key;
680 1035 : r2->tsorted = li.sorted;
681 1035 : r2->trevsorted = li.revsorted;
682 1035 : bat_iterator_end(&li);
683 1047 : r2->tnil = false;
684 1047 : r2->tnonil = true;
685 1047 : BATsetcount(r2, BATcount(r1));
686 : }
687 1184 : *r2p = r2;
688 1184 : goto doreturn2;
689 : }
690 : /* nil_on_miss is set, this means we must have a second or third
691 : * output */
692 0 : assert(r2p || r3p);
693 0 : if (BATtdense(l)) {
694 : /* if l is dense, we can further restrict the [lo..hi)
695 : * range to values in l that match with values in r */
696 0 : o = lo;
697 0 : i = lci->seq - l->hseqbase;
698 0 : if (l->tseqbase + i > lo)
699 0 : lo = l->tseqbase + i;
700 0 : i = canditer_last(lci) + 1 - l->hseqbase;
701 0 : if (l->tseqbase + i < hi)
702 0 : hi = l->tseqbase + i;
703 0 : if (lci->tpe == cand_dense) {
704 : /* l is dense, and so is the left candidate
705 : * list (if it exists); this means we don't
706 : * have to actually look at any values in l:
707 : * we can just do some arithmetic; it also
708 : * means that r1 will be dense, and if
709 : * nil_on_miss is not set, or if all values in
710 : * l match, r2 will too */
711 0 : if (hi <= lo) {
712 0 : return nomatch(r1p, r2p, r3p, l, r, lci, 0,
713 : nil_on_miss, only_misses,
714 : __func__, t0);
715 : }
716 :
717 : /* at this point, the matched values in l and
718 : * r (taking candidate lists into account) are
719 : * [lo..hi) which we can translate back to the
720 : * respective OID values that we can store in
721 : * r1 and r2; note that r1 will be dense since
722 : * all values in l will match something (even
723 : * if nil since nil_on_miss is set) */
724 0 : *r1p = r1 = BATdense(0, lci->seq, lci->ncand);
725 0 : if (r1 == NULL)
726 : return GDK_FAIL;
727 0 : if (r2p) {
728 0 : if (hi - lo < lci->ncand) {
729 : /* we need to fill in nils in r2 for
730 : * missing values */
731 0 : *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
732 0 : if (r2 == NULL) {
733 0 : BBPreclaim(*r1p);
734 0 : return GDK_FAIL;
735 : }
736 0 : o2p = (oid *) Tloc(r2, 0);
737 0 : i = l->tseqbase + lci->seq - l->hseqbase;
738 0 : lo -= i;
739 0 : hi -= i;
740 0 : i += r->hseqbase - r->tseqbase;
741 0 : for (o = 0; o < lo; o++)
742 0 : *o2p++ = oid_nil;
743 0 : for (o = lo; o < hi; o++)
744 0 : *o2p++ = o + i;
745 0 : for (o = hi; o < lci->ncand; o++)
746 0 : *o2p++ = oid_nil;
747 0 : r2->tnonil = false;
748 0 : r2->tnil = true;
749 : /* sorted of no nils at end */
750 0 : r2->tsorted = hi == lci->ncand;
751 : /* reverse sorted if single non-nil at start */
752 0 : r2->trevsorted = lo == 0 && hi == 1;
753 0 : r2->tseqbase = oid_nil;
754 : /* (hi - lo) different OIDs in r2,
755 : * plus one for nil */
756 0 : r2->tkey = hi - lo + 1 == lci->ncand;
757 0 : BATsetcount(r2, lci->ncand);
758 : } else {
759 : /* no missing values */
760 0 : *r2p = r2 = BATdense(0, r->hseqbase + lo - r->tseqbase, lci->ncand);
761 0 : if (r2 == NULL) {
762 0 : BBPreclaim(*r1p);
763 0 : return GDK_FAIL;
764 : }
765 : }
766 : }
767 0 : if (r3p) {
768 0 : if (hi - lo < lci->ncand) {
769 0 : *r3p = r3 = COLnew(0, TYPE_bit, lci->ncand, TRANSIENT);
770 0 : if (r3 == NULL) {
771 0 : BBPreclaim(*r1p);
772 0 : BBPreclaim(r2);
773 0 : return GDK_FAIL;
774 : }
775 0 : m3p = (bit *) Tloc(r3, 0);
776 0 : for (o = 0; o < lo; o++)
777 0 : *m3p++ = 0;
778 0 : for (o = lo; o < hi; o++)
779 0 : *m3p++ = 1;
780 0 : for (o = hi; o < lci->ncand; o++)
781 0 : *m3p++ = 0;
782 0 : r3->tnonil = true;
783 0 : r3->tnil = false;
784 0 : r3->tsorted = hi == lci->ncand;
785 0 : r3->trevsorted = lo == 0;
786 0 : r3->tkey = false;
787 0 : BATsetcount(r3, lci->ncand);
788 : }
789 : }
790 0 : goto doreturn;
791 : }
792 : /* l is dense, but the candidate list exists and is
793 : * not dense; we can, by manipulating the range
794 : * [lo..hi), just look at the candidate list values */
795 :
796 : /* translate lo and hi to l's OID values that now need
797 : * to match */
798 0 : lo = lo - l->tseqbase + l->hseqbase;
799 0 : hi = hi - l->tseqbase + l->hseqbase;
800 :
801 0 : *r1p = r1 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
802 0 : if (r2p)
803 0 : *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
804 0 : if (r3p)
805 0 : *r3p = r3 = COLnew(0, TYPE_bit, lci->ncand, TRANSIENT);
806 0 : if (r1 == NULL || (r2p != NULL && r2 == NULL) || (r3p != NULL && r3 == NULL)) {
807 0 : BBPreclaim(r1);
808 0 : BBPreclaim(r2);
809 0 : BBPreclaim(r3);
810 0 : return GDK_FAIL;
811 : }
812 0 : o1p = (oid *) Tloc(r1, 0);
813 0 : if (r2) {
814 0 : o2p = (oid *) Tloc(r2, 0);
815 0 : r2->tnil = false;
816 0 : r2->tnonil = true;
817 0 : r2->tkey = true;
818 0 : r2->tsorted = true;
819 : }
820 0 : if (r3) {
821 0 : m3p = (bit *) Tloc(r3, 0);
822 0 : r3->tnil = false;
823 0 : r3->tnonil = true;
824 0 : r3->tkey = false;
825 0 : r3->tsorted = false;
826 : }
827 0 : o = canditer_next(lci);
828 0 : for (i = 0; i < lci->ncand && o < lo; i++) {
829 0 : *o1p++ = o;
830 0 : if (r2)
831 0 : *o2p++ = oid_nil;
832 0 : if (r3)
833 0 : *m3p++ = 0;
834 0 : o = canditer_next(lci);
835 : }
836 0 : if (i > 0 && r2) {
837 0 : r2->tnil = true;
838 0 : r2->tnonil = false;
839 0 : r2->tkey = i == 1;
840 : }
841 0 : for (; i < lci->ncand && o < hi; i++) {
842 0 : *o1p++ = o;
843 0 : if (r2)
844 0 : *o2p++ = o - l->hseqbase + l->tseqbase - r->tseqbase + r->hseqbase;
845 0 : if (r3)
846 0 : *m3p++ = 1;
847 0 : o = canditer_next(lci);
848 : }
849 0 : if (i < lci->ncand) {
850 0 : if (r2) {
851 0 : r2->tkey = !r2->tnil && lci->ncand - i == 1;
852 0 : r2->tnil = true;
853 0 : r2->tnonil = false;
854 0 : r2->tsorted = false;
855 : }
856 0 : for (; i < lci->ncand; i++) {
857 0 : *o1p++ = o;
858 0 : if (r2)
859 0 : *o2p++ = oid_nil;
860 0 : if (r1)
861 0 : *m3p++ = 0;
862 0 : o = canditer_next(lci);
863 : }
864 : }
865 0 : BATsetcount(r1, lci->ncand);
866 0 : r1->tseqbase = BATcount(r1) == 1 ? *(oid*)Tloc(r1, 0) : oid_nil;
867 0 : r1->tsorted = true;
868 0 : r1->trevsorted = BATcount(r1) <= 1;
869 0 : r1->tnil = false;
870 0 : r1->tnonil = true;
871 0 : r1->tkey = true;
872 0 : if (r2) {
873 0 : BATsetcount(r2, BATcount(r1));
874 0 : r2->tseqbase = r2->tnil || BATcount(r2) > 1 ? oid_nil : BATcount(r2) == 1 ? *(oid*)Tloc(r2, 0) : 0;
875 0 : r2->trevsorted = BATcount(r2) <= 1;
876 : }
877 0 : if (r3) {
878 0 : BATsetcount(r3, BATcount(r1));
879 : }
880 0 : goto doreturn;
881 : }
882 : /* l is not dense, so we need to look at the values and check
883 : * whether they are in the range [lo..hi) */
884 :
885 : /* do indirection through the candidate list to look at the
886 : * value */
887 :
888 0 : *r1p = r1 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
889 0 : if (r2p)
890 0 : *r2p = r2 = COLnew(0, TYPE_oid, lci->ncand, TRANSIENT);
891 0 : if (r3p)
892 0 : *r3p = r3 = COLnew(0, TYPE_bit, lci->ncand, TRANSIENT);
893 0 : if (r1 == NULL || (r2p != NULL && r2 == NULL) || (r3p != NULL && r3 == NULL)) {
894 0 : BBPreclaim(r1);
895 0 : BBPreclaim(r2);
896 0 : BBPreclaim(r3);
897 0 : return GDK_FAIL;
898 : }
899 0 : o1p = (oid *) Tloc(r1, 0);
900 0 : if (r2) {
901 0 : o2p = (oid *) Tloc(r2, 0);
902 0 : r2->tnil = false;
903 0 : r2->tnonil = true;
904 : }
905 0 : if (r3) {
906 0 : m3p = (bit *) Tloc(r3, 0);
907 0 : r3->tnil = false;
908 0 : r3->tnonil = true;
909 : }
910 0 : if (complex_cand(l)) {
911 0 : ltsorted = l->tsorted;
912 0 : ltrevsorted = l->trevsorted;
913 0 : ltkey = l->tkey;
914 0 : TIMEOUT_LOOP(lci->ncand, qry_ctx) {
915 0 : oid c = canditer_next(lci);
916 :
917 0 : o = BUNtoid(l, c - l->hseqbase);
918 0 : *o1p++ = c;
919 0 : if (r2) {
920 0 : if (o >= lo && o < hi) {
921 0 : *o2p++ = o - r->tseqbase + r->hseqbase;
922 : } else {
923 0 : *o2p++ = oid_nil;
924 0 : r2->tnil = true;
925 0 : r2->tnonil = false;
926 : }
927 : }
928 0 : if (r3) {
929 0 : if (is_oid_nil(o)) {
930 0 : *m3p++ = bit_nil;
931 0 : r3->tnil = true;
932 0 : r3->tnonil = false;
933 : } else {
934 0 : *m3p++ = (o >= lo && o < hi);
935 : }
936 : }
937 : }
938 0 : TIMEOUT_CHECK(qry_ctx,
939 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
940 : } else {
941 0 : BATiter li = bat_iterator(l);
942 0 : const oid *lvals = (const oid *) li.base;
943 0 : ltsorted = li.sorted;
944 0 : ltrevsorted = li.revsorted;
945 0 : ltkey = li.key;
946 0 : TIMEOUT_LOOP(lci->ncand, qry_ctx) {
947 0 : oid c = canditer_next(lci);
948 :
949 0 : o = lvals[c - l->hseqbase];
950 0 : *o1p++ = c;
951 0 : if (r2) {
952 0 : if (o >= lo && o < hi) {
953 0 : *o2p++ = o - r->tseqbase + r->hseqbase;
954 : } else {
955 0 : *o2p++ = oid_nil;
956 0 : r2->tnil = true;
957 0 : r2->tnonil = false;
958 : }
959 : }
960 0 : if (r3) {
961 0 : if (is_oid_nil(o)) {
962 0 : *m3p++ = bit_nil;
963 0 : r3->tnil = true;
964 0 : r3->tnonil = false;
965 : } else {
966 0 : *m3p++ = (o >= lo && o < hi);
967 : }
968 : }
969 : }
970 0 : bat_iterator_end(&li);
971 0 : TIMEOUT_CHECK(qry_ctx,
972 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
973 : }
974 0 : r1->tsorted = true;
975 0 : r1->trevsorted = BATcount(r1) <= 1;
976 0 : r1->tkey = true;
977 0 : r1->tseqbase = oid_nil;
978 0 : r1->tnil = false;
979 0 : r1->tnonil = true;
980 0 : BATsetcount(r1, lci->ncand);
981 0 : if (r2) {
982 0 : BATsetcount(r2, lci->ncand);
983 0 : r2->tsorted = ltsorted || BATcount(r2) <= 1;
984 0 : r2->trevsorted = ltrevsorted || BATcount(r2) <= 1;
985 0 : r2->tkey = ltkey || BATcount(r2) <= 1;
986 0 : r2->tseqbase = oid_nil;
987 : }
988 0 : if (r3) {
989 0 : BATsetcount(r3, lci->ncand);
990 : }
991 :
992 0 : doreturn:
993 0 : if (r1->tkey)
994 0 : virtualize(r1);
995 0 : if (r2 && r2->tkey && r2->tsorted)
996 0 : virtualize(r2);
997 0 : doreturn2:
998 26792 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
999 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
1000 : "sr=" ALGOOPTBATFMT ","
1001 : "nil_on_miss=%s,only_misses=%s;%s %s "
1002 : "-> " ALGOBATFMT "," ALGOOPTBATFMT "," ALGOOPTBATFMT
1003 : " (" LLFMT "usec)\n",
1004 : ALGOBATPAR(l), ALGOBATPAR(r),
1005 : ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
1006 : nil_on_miss ? "true" : "false",
1007 : only_misses ? "true" : "false",
1008 : swapped ? " swapped" : "", reason,
1009 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2), ALGOOPTBATPAR(r3),
1010 : GDKusec() - t0);
1011 :
1012 : return GDK_SUCCEED;
1013 :
1014 0 : bailout:
1015 0 : BBPreclaim(r1);
1016 0 : BBPreclaim(r2);
1017 : return GDK_FAIL;
1018 : }
1019 :
1020 : /* Implementation of mergejoin (see below) for the special case that
1021 : * the values are of type int, and some more conditions are met. */
1022 : static gdk_return
1023 9149 : mergejoin_int(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
1024 : bool nil_matches, BUN estimate, lng t0, bool swapped,
1025 : const char *reason)
1026 : {
1027 9149 : BAT *r1, *r2;
1028 9149 : BUN lstart, lend, lcnt;
1029 9149 : BUN rstart, rend;
1030 9149 : BUN lscan, rscan; /* opportunistic scan window */
1031 9149 : BUN maxsize;
1032 9149 : const int *lvals, *rvals;
1033 9149 : int v;
1034 9149 : BUN nl, nr;
1035 9149 : oid lv;
1036 9149 : BUN i;
1037 9149 : BATiter li = bat_iterator(l);
1038 9176 : BATiter ri = bat_iterator(r);
1039 :
1040 27539 : assert(ATOMtype(li.type) == ATOMtype(ri.type));
1041 9179 : assert(ri.sorted || ri.revsorted);
1042 :
1043 9179 : MT_thread_setalgorithm(__func__);
1044 9179 : lstart = rstart = 0;
1045 9179 : lend = BATcount(l);
1046 9179 : lcnt = lend - lstart;
1047 9179 : rend = BATcount(r);
1048 9179 : lvals = (const int *) li.base;
1049 9179 : rvals = (const int *) ri.base;
1050 9179 : size_t counter = 0;
1051 9179 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
1052 :
1053 : /* basic properties will be adjusted if necessary later on,
1054 : * they were initially set by joininitresults() */
1055 :
1056 9178 : if (lend == 0 || rend == 0) {
1057 : /* there are no matches */
1058 0 : bat_iterator_end(&li);
1059 0 : bat_iterator_end(&ri);
1060 0 : return nomatch(r1p, r2p, NULL, l, r,
1061 0 : &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
1062 : 0, false, false, __func__, t0);
1063 : }
1064 :
1065 9127 : if ((maxsize = joininitresults(r1p, r2p, NULL, BATcount(l), BATcount(r),
1066 9178 : li.key, ri.key, false, false,
1067 : false, false, estimate)) == BUN_NONE) {
1068 0 : bat_iterator_end(&li);
1069 0 : bat_iterator_end(&ri);
1070 0 : return GDK_FAIL;
1071 : }
1072 9127 : r1 = *r1p;
1073 9127 : r2 = r2p ? *r2p : NULL;
1074 :
1075 : /* determine opportunistic scan window for l and r */
1076 55054 : for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
1077 45927 : nl >>= 1;
1078 68950 : for (nr = rend - rstart, rscan = 4; nr > 0; rscan++)
1079 59823 : nr >>= 1;
1080 :
1081 9127 : if (!nil_matches) {
1082 : /* skip over nils at the start of the columns */
1083 6091 : if (lscan < lend - lstart && is_int_nil(lvals[lstart + lscan])) {
1084 0 : lstart = binsearch_int(NULL, 0, lvals, lstart + lscan,
1085 : lend - 1, int_nil, 1, 1);
1086 : } else {
1087 6091 : while (is_int_nil(lvals[lstart]))
1088 0 : lstart++;
1089 : }
1090 6091 : if (rscan < rend - rstart && is_int_nil(rvals[rstart + rscan])) {
1091 0 : rstart = binsearch_int(NULL, 0, rvals, rstart + rscan,
1092 : rend - 1, int_nil, 1, 1);
1093 : } else {
1094 6091 : while (is_int_nil(rvals[rstart]))
1095 0 : rstart++;
1096 : }
1097 : }
1098 : /* from here on we don't have to worry about nil values */
1099 :
1100 378813 : while (lstart < lend && rstart < rend) {
1101 372387 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
1102 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
1103 :
1104 372387 : v = rvals[rstart];
1105 :
1106 372387 : if (lscan < lend - lstart && lvals[lstart + lscan] < v) {
1107 2282 : lstart = binsearch_int(NULL, 0, lvals, lstart + lscan,
1108 : lend - 1, v, 1, 0);
1109 : } else {
1110 : /* scan l for v */
1111 377896 : while (lstart < lend && lvals[lstart] < v)
1112 7791 : lstart++;
1113 : }
1114 371959 : if (lstart >= lend) {
1115 : /* nothing found */
1116 : break;
1117 : }
1118 :
1119 : /* Here we determine the next value in l that we are
1120 : * going to try to match in r. We will also count the
1121 : * number of occurrences in l of that value.
1122 : * Afterwards, v points to the value and nl is the
1123 : * number of times it occurs. Also, lstart will
1124 : * point to the next value to be considered (ready for
1125 : * the next iteration).
1126 : * If there are many equal values in l (more than
1127 : * lscan), we will use binary search to find the end
1128 : * of the sequence. Obviously, we can do this only if
1129 : * l is actually sorted (lscan > 0). */
1130 371159 : nl = 1; /* we'll match (at least) one in l */
1131 371159 : nr = 0; /* maybe we won't match anything in r */
1132 371159 : v = lvals[lstart];
1133 371159 : if (li.key) {
1134 : /* if l is key, there is a single value */
1135 57476 : lstart++;
1136 313683 : } else if (lscan < lend - lstart &&
1137 306002 : v == lvals[lstart + lscan]) {
1138 : /* lots of equal values: use binary search to
1139 : * find end */
1140 25676 : nl = binsearch_int(NULL, 0, lvals, lstart + lscan,
1141 : lend - 1, v, 1, 1);
1142 25694 : nl -= lstart;
1143 25694 : lstart += nl;
1144 : } else {
1145 : /* just scan */
1146 1378526 : while (++lstart < lend && v == lvals[lstart])
1147 1090519 : nl++;
1148 : }
1149 : /* lstart points one beyond the value we're
1150 : * going to match: ready for the next iteration. */
1151 :
1152 : /* First we find the first value in r that is at
1153 : * least as large as v, then we find the first
1154 : * value in r that is larger than v. The difference
1155 : * is the number of values equal to v and is stored in
1156 : * nr.
1157 : * We will use binary search on r to find both ends of
1158 : * the sequence of values that are equal to v in case
1159 : * the position is "too far" (more than rscan
1160 : * away). */
1161 :
1162 : /* first find the location of the first value in r
1163 : * that is >= v, then find the location of the first
1164 : * value in r that is > v; the difference is the
1165 : * number of values equal to v */
1166 :
1167 : /* look ahead a little (rscan) in r to see whether
1168 : * we're better off doing a binary search */
1169 371177 : if (rscan < rend - rstart && rvals[rstart + rscan] < v) {
1170 : /* value too far away in r: use binary
1171 : * search */
1172 20201 : rstart = binsearch_int(NULL, 0, rvals, rstart + rscan,
1173 : rend - 1, v, 1, 0);
1174 : } else {
1175 : /* scan r for v */
1176 380179 : while (rstart < rend && rvals[rstart] < v)
1177 29203 : rstart++;
1178 : }
1179 373153 : if (rstart == rend) {
1180 : /* nothing found */
1181 : break;
1182 : }
1183 :
1184 : /* now find the end of the sequence of equal values v */
1185 :
1186 : /* if r is key, there is zero or one match, otherwise
1187 : * look ahead a little (rscan) in r to see whether
1188 : * we're better off doing a binary search */
1189 371243 : if (ri.key) {
1190 169209 : if (rstart < rend && v == rvals[rstart]) {
1191 169006 : nr = 1;
1192 169006 : rstart++;
1193 : }
1194 202034 : } else if (rscan < rend - rstart &&
1195 200670 : v == rvals[rstart + rscan]) {
1196 : /* range too large: use binary search */
1197 70923 : nr = binsearch_int(NULL, 0, rvals, rstart + rscan,
1198 : rend - 1, v, 1, 1);
1199 70932 : nr -= rstart;
1200 70932 : rstart += nr;
1201 : } else {
1202 : /* scan r for end of range */
1203 1046919 : while (rstart < rend && v == rvals[rstart]) {
1204 915808 : nr++;
1205 915808 : rstart++;
1206 : }
1207 : }
1208 : /* rstart points to first value > v or end of
1209 : * r, and nr is the number of values in r that
1210 : * are equal to v */
1211 371049 : if (nr == 0) {
1212 : /* no entries in r found */
1213 139 : continue;
1214 : }
1215 : /* make space: nl values in l match nr values in r, so
1216 : * we need to add nl * nr values in the results */
1217 371113 : if (maybeextend(r1, r2, NULL, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
1218 0 : goto bailout;
1219 :
1220 : /* maintain properties */
1221 369547 : if (nl > 1) {
1222 : /* value occurs multiple times in l, so entry
1223 : * in r will be repeated multiple times: hence
1224 : * r2 is not key and not dense */
1225 246149 : if (r2) {
1226 213274 : r2->tkey = false;
1227 213274 : r2->tseqbase = oid_nil;
1228 : }
1229 : /* multiple different values will be inserted
1230 : * in r1 (always in order), so not reverse
1231 : * ordered anymore */
1232 246149 : r1->trevsorted = false;
1233 : }
1234 369547 : if (nr > 1) {
1235 : /* value occurs multiple times in r, so entry
1236 : * in l will be repeated multiple times: hence
1237 : * r1 is not key and not dense */
1238 160782 : r1->tkey = false;
1239 160782 : r1->tseqbase = oid_nil;
1240 : /* multiple different values will be inserted
1241 : * in r2 (in order), so not reverse ordered
1242 : * anymore */
1243 160782 : if (r2) {
1244 109657 : r2->trevsorted = false;
1245 109657 : if (nl > 1) {
1246 : /* multiple values in l match
1247 : * multiple values in r, so an
1248 : * ordered sequence will be
1249 : * inserted multiple times in
1250 : * r2, so r2 is not ordered
1251 : * anymore */
1252 83084 : r2->tsorted = false;
1253 : }
1254 : }
1255 : }
1256 369547 : if (BATcount(r1) > 0) {
1257 : /* a new, higher value will be inserted into
1258 : * r1, so r1 is not reverse ordered anymore */
1259 361576 : r1->trevsorted = false;
1260 : /* a new higher value will be added to r2 */
1261 361576 : if (r2) {
1262 297040 : r2->trevsorted = false;
1263 : }
1264 361576 : if (BATtdense(r1) &&
1265 196735 : ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
1266 176 : r1->tseqbase = oid_nil;
1267 : }
1268 : }
1269 :
1270 369547 : if (r2 &&
1271 303847 : BATcount(r2) > 0 &&
1272 296810 : BATtdense(r2) &&
1273 74579 : ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rstart - nr) {
1274 747 : r2->tseqbase = oid_nil;
1275 : }
1276 :
1277 : /* insert values */
1278 369547 : lv = l->hseqbase + lstart - nl;
1279 15770159 : for (i = 0; i < nl; i++) {
1280 : BUN j;
1281 :
1282 113320430 : for (j = 0; j < nr; j++) {
1283 97919818 : APPEND(r1, lv);
1284 : }
1285 15400612 : if (r2) {
1286 15240580 : oid rv = r->hseqbase + rstart - nr;
1287 :
1288 103758095 : for (j = 0; j < nr; j++) {
1289 88517515 : APPEND(r2, rv);
1290 88517515 : rv++;
1291 : }
1292 : }
1293 15400612 : lv++;
1294 : }
1295 : }
1296 : /* also set other bits of heap to correct value to indicate size */
1297 9136 : BATsetcount(r1, BATcount(r1));
1298 9101 : if (r2) {
1299 6920 : BATsetcount(r2, BATcount(r2));
1300 6929 : assert(BATcount(r1) == BATcount(r2));
1301 : }
1302 9110 : if (BATcount(r1) > 0) {
1303 7090 : if (BATtdense(r1))
1304 5564 : r1->tseqbase = ((oid *) r1->theap->base)[0];
1305 7090 : if (r2 && BATtdense(r2))
1306 3853 : r2->tseqbase = ((oid *) r2->theap->base)[0];
1307 : } else {
1308 2020 : r1->tseqbase = 0;
1309 2020 : if (r2) {
1310 942 : r2->tseqbase = 0;
1311 : }
1312 : }
1313 9110 : bat_iterator_end(&li);
1314 9163 : bat_iterator_end(&ri);
1315 9067 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
1316 : "nil_matches=%s;%s %s "
1317 : "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
1318 : ALGOBATPAR(l), ALGOBATPAR(r),
1319 : nil_matches ? "true" : "false",
1320 : swapped ? " swapped" : "", reason,
1321 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
1322 : GDKusec() - t0);
1323 :
1324 : return GDK_SUCCEED;
1325 :
1326 0 : bailout:
1327 0 : bat_iterator_end(&li);
1328 0 : bat_iterator_end(&ri);
1329 0 : BBPreclaim(r1);
1330 0 : BBPreclaim(r2);
1331 : return GDK_FAIL;
1332 : }
1333 :
1334 : /* Implementation of mergejoin (see below) for the special case that
1335 : * the values are of type lng, and some more conditions are met. */
1336 : static gdk_return
1337 261 : mergejoin_lng(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
1338 : bool nil_matches, BUN estimate, lng t0, bool swapped,
1339 : const char *reason)
1340 : {
1341 261 : BAT *r1, *r2;
1342 261 : BUN lstart, lend, lcnt;
1343 261 : BUN rstart, rend;
1344 261 : BUN lscan, rscan; /* opportunistic scan window */
1345 261 : BUN maxsize;
1346 261 : const lng *lvals, *rvals;
1347 261 : lng v;
1348 261 : BUN nl, nr;
1349 261 : oid lv;
1350 261 : BUN i;
1351 261 : BATiter li = bat_iterator(l);
1352 261 : BATiter ri = bat_iterator(r);
1353 :
1354 783 : assert(ATOMtype(li.type) == ATOMtype(ri.type));
1355 261 : assert(ri.sorted || ri.revsorted);
1356 :
1357 261 : MT_thread_setalgorithm(__func__);
1358 261 : lstart = rstart = 0;
1359 261 : lend = BATcount(l);
1360 261 : lcnt = lend - lstart;
1361 261 : rend = BATcount(r);
1362 261 : lvals = (const lng *) li.base;
1363 261 : rvals = (const lng *) ri.base;
1364 261 : size_t counter = 0;
1365 261 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
1366 :
1367 : /* basic properties will be adjusted if necessary later on,
1368 : * they were initially set by joininitresults() */
1369 :
1370 261 : if (lend == 0 || rend == 0) {
1371 : /* there are no matches */
1372 0 : bat_iterator_end(&li);
1373 0 : bat_iterator_end(&ri);
1374 0 : return nomatch(r1p, r2p, NULL, l, r,
1375 0 : &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
1376 : 0, false, false, __func__, t0);
1377 : }
1378 :
1379 260 : if ((maxsize = joininitresults(r1p, r2p, NULL, BATcount(l), BATcount(r),
1380 261 : li.key, ri.key, false, false,
1381 : false, false, estimate)) == BUN_NONE) {
1382 0 : bat_iterator_end(&li);
1383 0 : bat_iterator_end(&ri);
1384 0 : return GDK_FAIL;
1385 : }
1386 260 : r1 = *r1p;
1387 260 : r2 = r2p ? *r2p : NULL;
1388 :
1389 : /* determine opportunistic scan window for l and r */
1390 1818 : for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
1391 1558 : nl >>= 1;
1392 1807 : for (nr = rend - rstart, rscan = 4; nr > 0; rscan++)
1393 1547 : nr >>= 1;
1394 :
1395 260 : if (!nil_matches) {
1396 : /* skip over nils at the start of the columns */
1397 141 : if (lscan < lend - lstart && is_lng_nil(lvals[lstart + lscan])) {
1398 0 : lstart = binsearch_lng(NULL, 0, lvals, lstart + lscan,
1399 : lend - 1, lng_nil, 1, 1);
1400 : } else {
1401 141 : while (is_lng_nil(lvals[lstart]))
1402 0 : lstart++;
1403 : }
1404 141 : if (rscan < rend - rstart && is_lng_nil(rvals[rstart + rscan])) {
1405 0 : rstart = binsearch_lng(NULL, 0, rvals, rstart + rscan,
1406 : rend - 1, lng_nil, 1, 1);
1407 : } else {
1408 141 : while (is_lng_nil(rvals[rstart]))
1409 0 : rstart++;
1410 : }
1411 : }
1412 : /* from here on we don't have to worry about nil values */
1413 :
1414 414716 : while (lstart < lend && rstart < rend) {
1415 414563 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
1416 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
1417 414562 : v = rvals[rstart];
1418 :
1419 414562 : if (lscan < lend - lstart && lvals[lstart + lscan] < v) {
1420 949 : lstart = binsearch_lng(NULL, 0, lvals, lstart + lscan,
1421 : lend - 1, v, 1, 0);
1422 : } else {
1423 : /* scan l for v */
1424 492178 : while (lstart < lend && lvals[lstart] < v)
1425 78565 : lstart++;
1426 : }
1427 414255 : if (lstart >= lend) {
1428 : /* nothing found */
1429 : break;
1430 : }
1431 :
1432 : /* Here we determine the next value in l that we are
1433 : * going to try to match in r. We will also count the
1434 : * number of occurrences in l of that value.
1435 : * Afterwards, v points to the value and nl is the
1436 : * number of times it occurs. Also, lstart will
1437 : * point to the next value to be considered (ready for
1438 : * the next iteration).
1439 : * If there are many equal values in l (more than
1440 : * lscan), we will use binary search to find the end
1441 : * of the sequence. Obviously, we can do this only if
1442 : * l is actually sorted (lscan > 0). */
1443 414176 : nl = 1; /* we'll match (at least) one in l */
1444 414176 : nr = 0; /* maybe we won't match anything in r */
1445 414176 : v = lvals[lstart];
1446 414176 : if (li.key) {
1447 : /* if l is key, there is a single value */
1448 370209 : lstart++;
1449 43967 : } else if (lscan < lend - lstart &&
1450 43863 : v == lvals[lstart + lscan]) {
1451 : /* lots of equal values: use binary search to
1452 : * find end */
1453 395 : nl = binsearch_lng(NULL, 0, lvals, lstart + lscan,
1454 : lend - 1, v, 1, 1);
1455 395 : nl -= lstart;
1456 395 : lstart += nl;
1457 : } else {
1458 : /* just scan */
1459 66648 : while (++lstart < lend && v == lvals[lstart])
1460 23076 : nl++;
1461 : }
1462 : /* lstart points one beyond the value we're
1463 : * going to match: ready for the next iteration. */
1464 :
1465 : /* First we find the first value in r that is at
1466 : * least as large as v, then we find the first
1467 : * value in r that is larger than v. The difference
1468 : * is the number of values equal to v and is stored in
1469 : * nr.
1470 : * We will use binary search on r to find both ends of
1471 : * the sequence of values that are equal to v in case
1472 : * the position is "too far" (more than rscan
1473 : * away). */
1474 :
1475 : /* first find the location of the first value in r
1476 : * that is >= v, then find the location of the first
1477 : * value in r that is > v; the difference is the
1478 : * number of values equal to v */
1479 :
1480 : /* look ahead a little (rscan) in r to see whether
1481 : * we're better off doing a binary search */
1482 414176 : if (rscan < rend - rstart && rvals[rstart + rscan] < v) {
1483 : /* value too far away in r: use binary
1484 : * search */
1485 2326 : rstart = binsearch_lng(NULL, 0, rvals, rstart + rscan,
1486 : rend - 1, v, 1, 0);
1487 : } else {
1488 : /* scan r for v */
1489 1488153 : while (rstart < rend && rvals[rstart] < v)
1490 1076303 : rstart++;
1491 : }
1492 414344 : if (rstart == rend) {
1493 : /* nothing found */
1494 : break;
1495 : }
1496 :
1497 : /* now find the end of the sequence of equal values v */
1498 :
1499 : /* if r is key, there is zero or one match, otherwise
1500 : * look ahead a little (rscan) in r to see whether
1501 : * we're better off doing a binary search */
1502 414316 : if (ri.key) {
1503 376369 : if (rstart < rend && v == rvals[rstart]) {
1504 82275 : nr = 1;
1505 82275 : rstart++;
1506 : }
1507 37947 : } else if (rscan < rend - rstart &&
1508 37899 : v == rvals[rstart + rscan]) {
1509 : /* range too large: use binary search */
1510 0 : nr = binsearch_lng(NULL, 0, rvals, rstart + rscan,
1511 : rend - 1, v, 1, 1);
1512 0 : nr -= rstart;
1513 0 : rstart += nr;
1514 : } else {
1515 : /* scan r for end of range */
1516 92138 : while (rstart < rend && v == rvals[rstart]) {
1517 54191 : nr++;
1518 54191 : rstart++;
1519 : }
1520 : }
1521 : /* rstart points to first value > v or end of
1522 : * r, and nr is the number of values in r that
1523 : * are equal to v */
1524 120222 : if (nr == 0) {
1525 : /* no entries in r found */
1526 293947 : continue;
1527 : }
1528 : /* make space: nl values in l match nr values in r, so
1529 : * we need to add nl * nr values in the results */
1530 120369 : if (maybeextend(r1, r2, NULL, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
1531 0 : goto bailout;
1532 :
1533 : /* maintain properties */
1534 120509 : if (nl > 1) {
1535 : /* value occurs multiple times in l, so entry
1536 : * in r will be repeated multiple times: hence
1537 : * r2 is not key and not dense */
1538 6810 : if (r2) {
1539 1806 : r2->tkey = false;
1540 1806 : r2->tseqbase = oid_nil;
1541 : }
1542 : /* multiple different values will be inserted
1543 : * in r1 (always in order), so not reverse
1544 : * ordered anymore */
1545 6810 : r1->trevsorted = false;
1546 : }
1547 120509 : if (nr > 1) {
1548 : /* value occurs multiple times in r, so entry
1549 : * in l will be repeated multiple times: hence
1550 : * r1 is not key and not dense */
1551 4710 : r1->tkey = false;
1552 4710 : r1->tseqbase = oid_nil;
1553 : /* multiple different values will be inserted
1554 : * in r2 (in order), so not reverse ordered
1555 : * anymore */
1556 4710 : if (r2) {
1557 4710 : r2->trevsorted = false;
1558 4710 : if (nl > 1) {
1559 : /* multiple values in l match
1560 : * multiple values in r, so an
1561 : * ordered sequence will be
1562 : * inserted multiple times in
1563 : * r2, so r2 is not ordered
1564 : * anymore */
1565 51 : r2->tsorted = false;
1566 : }
1567 : }
1568 : }
1569 120509 : if (BATcount(r1) > 0) {
1570 : /* a new, higher value will be inserted into
1571 : * r1, so r1 is not reverse ordered anymore */
1572 119972 : r1->trevsorted = false;
1573 : /* a new higher value will be added to r2 */
1574 119972 : if (r2) {
1575 113268 : r2->trevsorted = false;
1576 : }
1577 119972 : if (BATtdense(r1) &&
1578 52832 : ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
1579 68 : r1->tseqbase = oid_nil;
1580 : }
1581 : }
1582 :
1583 120509 : if (r2 &&
1584 113793 : BATcount(r2) > 0 &&
1585 113207 : BATtdense(r2) &&
1586 51686 : ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rstart - nr) {
1587 36 : r2->tseqbase = oid_nil;
1588 : }
1589 :
1590 : /* insert values */
1591 120509 : lv = l->hseqbase + lstart - nl;
1592 271004 : for (i = 0; i < nl; i++) {
1593 : BUN j;
1594 :
1595 317025 : for (j = 0; j < nr; j++) {
1596 166530 : APPEND(r1, lv);
1597 : }
1598 150495 : if (r2) {
1599 132160 : oid rv = r->hseqbase + rstart - nr;
1600 :
1601 280321 : for (j = 0; j < nr; j++) {
1602 148161 : APPEND(r2, rv);
1603 148161 : rv++;
1604 : }
1605 : }
1606 150495 : lv++;
1607 : }
1608 : }
1609 : /* also set other bits of heap to correct value to indicate size */
1610 260 : BATsetcount(r1, BATcount(r1));
1611 259 : if (r2) {
1612 234 : BATsetcount(r2, BATcount(r2));
1613 234 : assert(BATcount(r1) == BATcount(r2));
1614 : }
1615 259 : if (BATcount(r1) > 0) {
1616 224 : if (BATtdense(r1))
1617 132 : r1->tseqbase = ((oid *) r1->theap->base)[0];
1618 224 : if (r2 && BATtdense(r2))
1619 130 : r2->tseqbase = ((oid *) r2->theap->base)[0];
1620 : } else {
1621 35 : r1->tseqbase = 0;
1622 35 : if (r2) {
1623 22 : r2->tseqbase = 0;
1624 : }
1625 : }
1626 259 : bat_iterator_end(&li);
1627 260 : bat_iterator_end(&ri);
1628 259 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
1629 : "nil_matches=%s;%s %s "
1630 : "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
1631 : ALGOBATPAR(l), ALGOBATPAR(r),
1632 : nil_matches ? "true" : "false",
1633 : swapped ? " swapped" : "", reason,
1634 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
1635 : GDKusec() - t0);
1636 :
1637 : return GDK_SUCCEED;
1638 :
1639 1 : bailout:
1640 1 : bat_iterator_end(&li);
1641 1 : bat_iterator_end(&ri);
1642 1 : BBPreclaim(r1);
1643 1 : BBPreclaim(r2);
1644 : return GDK_FAIL;
1645 : }
1646 :
1647 : /* Implementation of mergejoin (see below) for the special case that
1648 : * the values are of type oid, and the right-hand side is a candidate
1649 : * list with exception, and some more conditions are met. */
1650 : static gdk_return
1651 0 : mergejoin_cand(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
1652 : bool nil_matches, BUN estimate, lng t0, bool swapped,
1653 : const char *reason)
1654 : {
1655 : /* the comments in this function have not been checked after making a
1656 : * copy of mergejoin below and adapting it to a mask right-hand side */
1657 0 : BAT *r1, *r2;
1658 0 : BUN lstart, lend, lcnt;
1659 0 : struct canditer lci, rci;
1660 0 : BUN lscan; /* opportunistic scan window */
1661 0 : BUN maxsize;
1662 0 : const oid *lvals;
1663 0 : oid v;
1664 0 : BUN nl, nr;
1665 0 : oid lv;
1666 0 : BUN i;
1667 0 : BATiter li = bat_iterator(l);
1668 0 : BATiter ri = bat_iterator(r);
1669 :
1670 0 : assert(ATOMtype(li.type) == ATOMtype(ri.type));
1671 :
1672 0 : MT_thread_setalgorithm(__func__);
1673 0 : lstart = 0;
1674 0 : lend = BATcount(l);
1675 0 : lcnt = lend - lstart;
1676 0 : if (li.type == TYPE_void) {
1677 0 : assert(!is_oid_nil(l->tseqbase));
1678 0 : canditer_init(&lci, NULL, l);
1679 0 : lcnt = lci.ncand;
1680 0 : lvals = NULL;
1681 : } else {
1682 0 : lci = (struct canditer) {.tpe = cand_dense}; /* not used */
1683 0 : lvals = (const oid *) li.base;
1684 0 : assert(lvals != NULL);
1685 : }
1686 :
1687 0 : assert(complex_cand(r));
1688 0 : canditer_init(&rci, NULL, r);
1689 0 : size_t counter = 0;
1690 0 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
1691 :
1692 : /* basic properties will be adjusted if necessary later on,
1693 : * they were initially set by joininitresults() */
1694 :
1695 0 : if (lend == 0 || rci.ncand == 0) {
1696 : /* there are no matches */
1697 0 : bat_iterator_end(&li);
1698 0 : bat_iterator_end(&ri);
1699 0 : return nomatch(r1p, r2p, NULL, l, r,
1700 0 : &(struct canditer) {.tpe = cand_dense, .ncand = lcnt,},
1701 : 0, false, false, __func__, t0);
1702 : }
1703 :
1704 0 : if ((maxsize = joininitresults(r1p, r2p, NULL, BATcount(l), BATcount(r),
1705 0 : li.key, ri.key, false, false,
1706 : false, false, estimate)) == BUN_NONE) {
1707 0 : bat_iterator_end(&li);
1708 0 : bat_iterator_end(&ri);
1709 0 : return GDK_FAIL;
1710 : }
1711 0 : r1 = *r1p;
1712 0 : r2 = r2p ? *r2p : NULL;
1713 :
1714 : /* determine opportunistic scan window for l and r */
1715 0 : for (nl = lend - lstart, lscan = 4; nl > 0; lscan++)
1716 0 : nl >>= 1;
1717 :
1718 0 : if (!nil_matches) {
1719 : /* skip over nils at the start of the columns */
1720 0 : if (lscan < lend - lstart && lvals && is_oid_nil(lvals[lstart + lscan])) {
1721 0 : lstart = binsearch_oid(NULL, 0, lvals, lstart + lscan,
1722 : lend - 1, oid_nil, 1, 1);
1723 0 : } else if (lvals) {
1724 0 : while (is_oid_nil(lvals[lstart]))
1725 0 : lstart++;
1726 : } /* else l is candidate list: no nils */
1727 : }
1728 : /* from here on we don't have to worry about nil values */
1729 :
1730 0 : while (lstart < lend && rci.next < rci.ncand) {
1731 0 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
1732 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
1733 0 : v = canditer_peek(&rci);
1734 :
1735 0 : if (lvals) {
1736 0 : if (lscan < lend - lstart &&
1737 0 : lvals[lstart + lscan] < v) {
1738 0 : lstart = binsearch_oid(NULL, 0, lvals,
1739 : lstart + lscan,
1740 : lend - 1, v, 1, 0);
1741 : } else {
1742 : /* scan l for v */
1743 0 : while (lstart < lend && lvals[lstart] < v)
1744 0 : lstart++;
1745 : }
1746 : } else {
1747 0 : lstart = canditer_search(&lci, v, true);
1748 0 : canditer_setidx(&lci, lstart);
1749 : }
1750 0 : if (lstart >= lend) {
1751 : /* nothing found */
1752 : break;
1753 : }
1754 :
1755 : /* Here we determine the next value in l that we are
1756 : * going to try to match in r. We will also count the
1757 : * number of occurrences in l of that value.
1758 : * Afterwards, v points to the value and nl is the
1759 : * number of times it occurs. Also, lstart will
1760 : * point to the next value to be considered (ready for
1761 : * the next iteration).
1762 : * If there are many equal values in l (more than
1763 : * lscan), we will use binary search to find the end
1764 : * of the sequence. Obviously, we can do this only if
1765 : * l is actually sorted (lscan > 0). */
1766 0 : nl = 1; /* we'll match (at least) one in l */
1767 0 : nr = 0; /* maybe we won't match anything in r */
1768 0 : v = lvals ? lvals[lstart] : canditer_next(&lci);
1769 0 : if (li.key || lvals == NULL) {
1770 : /* if l is key, there is a single value */
1771 0 : lstart++;
1772 0 : } else if (lscan < lend - lstart &&
1773 0 : v == lvals[lstart + lscan]) {
1774 : /* lots of equal values: use binary search to
1775 : * find end */
1776 0 : nl = binsearch_oid(NULL, 0, lvals, lstart + lscan,
1777 : lend - 1, v, 1, 1);
1778 0 : nl -= lstart;
1779 0 : lstart += nl;
1780 : } else {
1781 : /* just scan */
1782 0 : while (++lstart < lend && v == lvals[lstart])
1783 0 : nl++;
1784 : }
1785 : /* lstart points one beyond the value we're
1786 : * going to match: ready for the next iteration. */
1787 :
1788 : /* First we find the first value in r that is at
1789 : * least as large as v, then we find the first
1790 : * value in r that is larger than v. The difference
1791 : * is the number of values equal to v and is stored in
1792 : * nr.
1793 : * We will use binary search on r to find both ends of
1794 : * the sequence of values that are equal to v in case
1795 : * the position is "too far" (more than rscan
1796 : * away). */
1797 :
1798 : /* first find the location of the first value in r
1799 : * that is >= v, then find the location of the first
1800 : * value in r that is > v; the difference is the
1801 : * number of values equal to v */
1802 0 : nr = canditer_search(&rci, v, true);
1803 0 : canditer_setidx(&rci, nr);
1804 0 : if (nr == rci.ncand) {
1805 : /* nothing found */
1806 : break;
1807 : }
1808 :
1809 : /* now find the end of the sequence of equal values v */
1810 :
1811 : /* if r is key, there is zero or one match, otherwise
1812 : * look ahead a little (rscan) in r to see whether
1813 : * we're better off doing a binary search */
1814 0 : if (canditer_peek(&rci) == v) {
1815 0 : nr = 1;
1816 0 : canditer_next(&rci);
1817 : } else {
1818 : /* rci points to first value > v or end of
1819 : * r, and nr is the number of values in r that
1820 : * are equal to v */
1821 : /* no entries in r found */
1822 0 : continue;
1823 : }
1824 : /* make space: nl values in l match nr values in r, so
1825 : * we need to add nl * nr values in the results */
1826 0 : if (maybeextend(r1, r2, NULL, nl * nr, lstart, lend, maxsize) != GDK_SUCCEED)
1827 0 : goto bailout;
1828 :
1829 : /* maintain properties */
1830 0 : if (nl > 1) {
1831 : /* value occurs multiple times in l, so entry
1832 : * in r will be repeated multiple times: hence
1833 : * r2 is not key and not dense */
1834 0 : if (r2) {
1835 0 : r2->tkey = false;
1836 0 : r2->tseqbase = oid_nil;
1837 : }
1838 : /* multiple different values will be inserted
1839 : * in r1 (always in order), so not reverse
1840 : * ordered anymore */
1841 0 : r1->trevsorted = false;
1842 : }
1843 0 : if (BATcount(r1) > 0) {
1844 : /* a new, higher value will be inserted into
1845 : * r1, so r1 is not reverse ordered anymore */
1846 0 : r1->trevsorted = false;
1847 : /* a new higher value will be added to r2 */
1848 0 : if (r2) {
1849 0 : r2->trevsorted = false;
1850 : }
1851 0 : if (BATtdense(r1) &&
1852 0 : ((oid *) r1->theap->base)[r1->batCount - 1] + 1 != l->hseqbase + lstart - nl) {
1853 0 : r1->tseqbase = oid_nil;
1854 : }
1855 : }
1856 :
1857 0 : if (r2 &&
1858 0 : BATcount(r2) > 0 &&
1859 0 : BATtdense(r2) &&
1860 0 : ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != r->hseqbase + rci.next - nr) {
1861 0 : r2->tseqbase = oid_nil;
1862 : }
1863 :
1864 : /* insert values */
1865 0 : lv = l->hseqbase + lstart - nl;
1866 0 : for (i = 0; i < nl; i++) {
1867 : BUN j;
1868 :
1869 0 : for (j = 0; j < nr; j++) {
1870 0 : APPEND(r1, lv);
1871 : }
1872 0 : if (r2) {
1873 0 : oid rv = r->hseqbase + rci.next - nr;
1874 :
1875 0 : for (j = 0; j < nr; j++) {
1876 0 : APPEND(r2, rv);
1877 0 : rv++;
1878 : }
1879 : }
1880 0 : lv++;
1881 : }
1882 : }
1883 : /* also set other bits of heap to correct value to indicate size */
1884 0 : BATsetcount(r1, BATcount(r1));
1885 0 : if (r2) {
1886 0 : BATsetcount(r2, BATcount(r2));
1887 0 : assert(BATcount(r1) == BATcount(r2));
1888 : }
1889 0 : if (BATcount(r1) > 0) {
1890 0 : if (BATtdense(r1))
1891 0 : r1->tseqbase = ((oid *) r1->theap->base)[0];
1892 0 : if (r2 && BATtdense(r2))
1893 0 : r2->tseqbase = ((oid *) r2->theap->base)[0];
1894 : } else {
1895 0 : r1->tseqbase = 0;
1896 0 : if (r2) {
1897 0 : r2->tseqbase = 0;
1898 : }
1899 : }
1900 0 : bat_iterator_end(&li);
1901 0 : bat_iterator_end(&ri);
1902 0 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT ","
1903 : "nil_matches=%s;%s %s "
1904 : "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
1905 : ALGOBATPAR(l), ALGOBATPAR(r),
1906 : nil_matches ? "true" : "false",
1907 : swapped ? " swapped" : "", reason,
1908 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
1909 : GDKusec() - t0);
1910 :
1911 : return GDK_SUCCEED;
1912 :
1913 0 : bailout:
1914 0 : bat_iterator_end(&li);
1915 0 : bat_iterator_end(&ri);
1916 0 : BBPreclaim(r1);
1917 0 : BBPreclaim(r2);
1918 : return GDK_FAIL;
1919 : }
1920 :
1921 : /* Perform a "merge" join on l and r (if both are sorted) with
1922 : * optional candidate lists, or join using binary search on r if l is
1923 : * not sorted.
1924 : *
1925 : * If nil_matches is set, nil values are treated as ordinary values
1926 : * that can match; otherwise nil values never match.
1927 : *
1928 : * If nil_on_miss is set, a nil value is returned in r2 if there is no
1929 : * match in r for a particular value in l (left outer join).
1930 : *
1931 : * If semi is set, only a single set of values in r1/r2 is returned if
1932 : * there is a match of l in r, no matter how many matches there are in
1933 : * r; otherwise all matches are returned.
1934 : *
1935 : * If max_one is set, only a single match is allowed. This is like
1936 : * semi, but enforces the single match.
1937 : *
1938 : * t0, swapped, and reason are only for debugging (ALGOMASK set in
1939 : * GDKdebug).
1940 : */
1941 : static gdk_return
1942 17682 : mergejoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
1943 : struct canditer *restrict lci, struct canditer *restrict rci,
1944 : bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
1945 : bool not_in, bool max_one, bool min_one, BUN estimate,
1946 : lng t0, bool swapped,
1947 : const char *reason)
1948 : {
1949 : /* [lr]scan determine how far we look ahead in l/r in order to
1950 : * decide whether we want to do a binary search or a scan */
1951 17682 : BUN lscan, rscan;
1952 17682 : const void *lvals, *rvals; /* the values of l/r (NULL if dense) */
1953 17682 : const char *lvars, *rvars; /* the indirect values (NULL if fixed size) */
1954 17682 : const void *nil = ATOMnilptr(l->ttype);
1955 17682 : int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
1956 17682 : const void *v; /* points to value under consideration */
1957 17682 : const void *prev = NULL;
1958 17682 : BUN nl, nr;
1959 17682 : bool insert_nil;
1960 : /* equal_order is set if we can scan both BATs in the same
1961 : * order, so when both are sorted or both are reverse sorted
1962 : * -- important to know in order to skip over values; if l is
1963 : * not sorted, this must be set to true and we will always do a
1964 : * binary search on all of r */
1965 17682 : bool equal_order;
1966 : /* [lr]ordering is either 1 or -1 depending on the order of
1967 : * l/r: it determines the comparison function used */
1968 17682 : int lordering, rordering;
1969 17682 : oid lv;
1970 17682 : BUN i, j; /* counters */
1971 17682 : oid lval = oid_nil, rval = oid_nil; /* temporary space to point v to */
1972 17682 : struct canditer llci, rrci;
1973 17682 : struct canditer *mlci, xlci;
1974 17682 : struct canditer *mrci, xrci;
1975 :
1976 17682 : if (lci->tpe == cand_dense && lci->ncand == BATcount(l) &&
1977 17599 : rci->tpe == cand_dense && rci->ncand == BATcount(r) &&
1978 16803 : !nil_on_miss && !semi && !max_one && !min_one && !only_misses &&
1979 11892 : !not_in &&
1980 9575 : l->tsorted && r->tsorted) {
1981 : /* special cases with far fewer options */
1982 9519 : if (complex_cand(r))
1983 0 : return mergejoin_cand(r1p, r2p, l, r, nil_matches,
1984 : estimate, t0, swapped, __func__);
1985 18962 : switch (ATOMbasetype(l->ttype)) {
1986 9167 : case TYPE_int:
1987 9167 : return mergejoin_int(r1p, r2p, l, r, nil_matches,
1988 : estimate, t0, swapped, __func__);
1989 261 : case TYPE_lng:
1990 261 : return mergejoin_lng(r1p, r2p, l, r, nil_matches,
1991 : estimate, t0, swapped, __func__);
1992 : }
1993 : }
1994 :
1995 24616 : assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
1996 8254 : assert(r->tsorted || r->trevsorted);
1997 :
1998 8254 : size_t counter = 0;
1999 8254 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
2000 :
2001 8252 : BATiter li = bat_iterator(l);
2002 8256 : BATiter ri = bat_iterator(r);
2003 8256 : MT_thread_setalgorithm(__func__);
2004 8251 : if (BATtvoid(l)) {
2005 : /* l->ttype == TYPE_void && is_oid_nil(l->tseqbase) is
2006 : * handled by selectjoin */
2007 74 : assert(!is_oid_nil(l->tseqbase));
2008 74 : canditer_init(&llci, NULL, l);
2009 74 : lvals = NULL;
2010 : } else {
2011 8177 : lvals = li.base; /* non NULL */
2012 8177 : llci = (struct canditer) {.tpe = cand_dense}; /* not used */
2013 : }
2014 8252 : rrci = (struct canditer) {.tpe = cand_dense};
2015 8252 : if (BATtvoid(r)) {
2016 53 : if (!is_oid_nil(r->tseqbase))
2017 53 : canditer_init(&rrci, NULL, r);
2018 : rvals = NULL;
2019 : } else {
2020 8199 : rvals = ri.base;
2021 : }
2022 8246 : if (li.vh && li.type) {
2023 171 : assert(ri.vh && ri.type);
2024 171 : lvars = li.vh->base;
2025 171 : rvars = ri.vh->base;
2026 : } else {
2027 8075 : assert(ri.vh == NULL || ri.type == TYPE_void);
2028 : lvars = rvars = NULL;
2029 : }
2030 : /* if the var pointer is not NULL, then so is the val pointer */
2031 8246 : assert(lvars == NULL || lvals != NULL);
2032 8246 : assert(rvars == NULL || rvals != NULL);
2033 :
2034 8246 : const bool rhasnil = !ri.nonil &&
2035 987 : ((BATtvoid(r) && r->tseqbase == oid_nil) ||
2036 987 : (rvals && cmp(nil, VALUE(r, (ri.sorted ? rci->seq : canditer_last(rci)) - r->hseqbase)) == 0));
2037 10 : const bit defmark = rhasnil ? bit_nil : 0;
2038 :
2039 8246 : if (not_in && (rhasnil || (BATtvoid(l) && l->tseqbase == oid_nil))) {
2040 0 : bat_iterator_end(&li);
2041 0 : bat_iterator_end(&ri);
2042 0 : return nomatch(r1p, r2p, r3p, l, r, lci, defmark, false, false,
2043 : __func__, t0);
2044 : }
2045 :
2046 8246 : if ((!nil_matches &&
2047 7943 : ((li.type == TYPE_void && is_oid_nil(l->tseqbase)) ||
2048 7943 : (ri.type == TYPE_void && is_oid_nil(r->tseqbase)))) ||
2049 8246 : (li.type == TYPE_void && is_oid_nil(l->tseqbase) &&
2050 0 : (ri.nonil ||
2051 0 : (ri.type == TYPE_void && !is_oid_nil(r->tseqbase)))) ||
2052 8246 : (ri.type == TYPE_void && is_oid_nil(r->tseqbase) &&
2053 0 : (li.nonil ||
2054 0 : (li.type == TYPE_void && !is_oid_nil(l->tseqbase))))) {
2055 : /* there are no matches */
2056 0 : bat_iterator_end(&li);
2057 0 : bat_iterator_end(&ri);
2058 0 : return nomatch(r1p, r2p, r3p, l, r, lci, defmark,
2059 : nil_on_miss, only_misses, __func__, t0);
2060 : }
2061 :
2062 16464 : BUN maxsize = joininitresults(r1p, r2p, r3p, lci->ncand, rci->ncand,
2063 8246 : li.key, ri.key, semi | max_one,
2064 : nil_on_miss, only_misses, min_one,
2065 : estimate);
2066 8218 : if (maxsize == BUN_NONE) {
2067 0 : bat_iterator_end(&li);
2068 0 : bat_iterator_end(&ri);
2069 0 : return GDK_FAIL;
2070 : }
2071 8218 : BAT *r1 = *r1p;
2072 8218 : BAT *r2 = r2p ? *r2p : NULL;
2073 8218 : BAT *r3 = r3p ? *r3p : NULL;
2074 :
2075 8218 : if (lci->tpe == cand_mask) {
2076 0 : mlci = lci;
2077 0 : canditer_init(&xlci, l, NULL);
2078 0 : lci = &xlci;
2079 : } else {
2080 8218 : mlci = NULL;
2081 8218 : xlci = (struct canditer) {.tpe = cand_dense}; /* not used */
2082 : }
2083 8218 : if (rci->tpe == cand_mask) {
2084 0 : mrci = rci;
2085 0 : canditer_init(&xrci, r, NULL);
2086 0 : rci = &xrci;
2087 : } else {
2088 8218 : mrci = NULL;
2089 8218 : xrci = (struct canditer) {.tpe = cand_dense}; /* not used */
2090 : }
2091 :
2092 8218 : if (li.sorted || li.revsorted) {
2093 5705 : equal_order = (li.sorted && ri.sorted) ||
2094 393 : (li.revsorted && ri.revsorted &&
2095 115 : !BATtvoid(l) && !BATtvoid(r));
2096 5705 : lordering = li.sorted && (ri.sorted || !equal_order) ? 1 : -1;
2097 5611 : rordering = equal_order ? lordering : -lordering;
2098 5705 : if (!li.nonil && !nil_matches && !nil_on_miss && lvals != NULL) {
2099 : /* find first non-nil */
2100 546 : nl = binsearch(NULL, 0, li.type, lvals, lvars, li.width, 0, BATcount(l), nil, li.sorted ? 1 : -1, li.sorted ? 1 : 0);
2101 485 : nl = canditer_search(lci, nl + l->hseqbase, true);
2102 485 : if (li.sorted) {
2103 433 : canditer_setidx(lci, nl);
2104 52 : } else if (li.revsorted) {
2105 52 : lci->ncand = nl;
2106 : }
2107 : }
2108 : /* determine opportunistic scan window for l */
2109 11394 : lscan = 4 + ilog2(lci->ncand);
2110 : } else {
2111 : /* if l not sorted, we will always use binary search
2112 : * on r */
2113 2513 : assert(!BATtvoid(l)); /* void is always sorted */
2114 2513 : lscan = 0;
2115 2513 : equal_order = true;
2116 2513 : lordering = 1;
2117 2513 : rordering = ri.sorted ? 1 : -1;
2118 : }
2119 : /* determine opportunistic scan window for r; if l is not
2120 : * sorted this is only used to find range of equal values */
2121 8210 : rscan = 4 + ilog2(rci->ncand);
2122 :
2123 8210 : if (!equal_order) {
2124 : /* we go through r backwards */
2125 275 : canditer_setidx(rci, rci->ncand);
2126 : }
2127 : /* At this point the various variables that help us through
2128 : * the algorithm have been set. The table explains them. The
2129 : * first two columns are the inputs, the next three columns
2130 : * are the variables, the final two columns indicate how the
2131 : * variables can be used.
2132 : *
2133 : * l/r sl/sr | vals cand off | result value being matched
2134 : * -------------+-----------------+----------------------------------
2135 : * dense NULL | NULL NULL set | i off==nil?nil:i+off
2136 : * dense dense | NULL NULL set | i off==nil?nil:i+off
2137 : * dense set | NULL set set | cand[i] off==nil?nil:cand[i]+off
2138 : * set NULL | set NULL 0 | i vals[i]
2139 : * set dense | set NULL 0 | i vals[i]
2140 : * set set | set set 0 | cand[i] vals[cand[i]]
2141 : *
2142 : * If {l,r}off is lng_nil, all values in the corresponding bat
2143 : * are oid_nil because the bat has type VOID and the tseqbase
2144 : * is nil.
2145 : */
2146 :
2147 :
2148 : /* Before we start adding values to r1 and r2, the properties
2149 : * are as follows:
2150 : * tseqbase - 0
2151 : * tkey - true
2152 : * tsorted - true
2153 : * trevsorted - true
2154 : * tnil - false
2155 : * tnonil - true
2156 : * We will modify these as we go along.
2157 : */
2158 461639 : while (lci->next < lci->ncand) {
2159 455998 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
2160 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
2161 455998 : bit mark = defmark;
2162 455998 : if (lscan == 0) {
2163 : /* always search r completely */
2164 181535 : assert(equal_order);
2165 181535 : canditer_reset(rci);
2166 : } else {
2167 : /* If l is sorted (lscan > 0), we look at the
2168 : * next value in r to see whether we can jump
2169 : * over a large section of l using binary
2170 : * search. We do this by looking ahead in l
2171 : * (lscan far, to be precise) and seeing if
2172 : * the value there is still too "small"
2173 : * (definition depends on sort order of l).
2174 : * If it is, we use binary search on l,
2175 : * otherwise we scan l for the next position
2176 : * with a value greater than or equal to the
2177 : * value in r.
2178 : * The next value to match in r is the first
2179 : * if equal_order is set, the last
2180 : * otherwise.
2181 : * When skipping over values in l, we count
2182 : * how many we skip in nlx. We need this in
2183 : * case only_misses or nil_on_miss is set, and
2184 : * to properly set the dense property in the
2185 : * first output BAT. */
2186 274463 : BUN nlx = 0; /* number of non-matching values in l */
2187 :
2188 274463 : if (equal_order) {
2189 273300 : if (rci->next == rci->ncand)
2190 : v = NULL; /* no more values */
2191 270965 : else if (mrci) {
2192 0 : oid rv = canditer_mask_next(mrci, canditer_peek(rci), true);
2193 0 : v = rv == oid_nil ? NULL : VALUE(r, rv - r->hseqbase);
2194 : } else
2195 270965 : v = VALUE(r, canditer_peek(rci) - r->hseqbase);
2196 : } else {
2197 1163 : if (rci->next == 0)
2198 : v = NULL; /* no more values */
2199 1110 : else if (mrci) {
2200 0 : oid rv = canditer_mask_next(mrci, canditer_peekprev(rci), false);
2201 0 : v = rv == oid_nil ? NULL : VALUE(r, rv - r->hseqbase);
2202 : } else
2203 1110 : v = VALUE(r, canditer_peekprev(rci) - r->hseqbase);
2204 : }
2205 : /* here, v points to next value in r, or if
2206 : * we're at the end of r, v is NULL */
2207 11206 : if (v == NULL) {
2208 2388 : nlx = lci->ncand - lci->next;
2209 : } else {
2210 272075 : if (lscan < lci->ncand - lci->next) {
2211 249507 : lv = canditer_idx(lci, lci->next + lscan);
2212 249507 : lv -= l->hseqbase;
2213 249507 : if (lvals) {
2214 243533 : if (lordering * cmp(VALUE(l, lv), v) < 0) {
2215 2853 : nlx = binsearch(NULL, 0, li.type, lvals, lvars, li.width, lv, BATcount(l), v, lordering, 0);
2216 2853 : nlx = canditer_search(lci, nlx + l->hseqbase, true);
2217 2853 : nlx -= lci->next;
2218 : }
2219 : } else {
2220 5974 : assert(lordering == 1);
2221 5974 : if (canditer_idx(&llci, lv) < *(const oid *)v) {
2222 7 : nlx = canditer_search(&llci, *(const oid *)v, true);
2223 7 : nlx = canditer_search(lci, nlx + l->hseqbase, true);
2224 7 : nlx -= lci->next;
2225 : }
2226 : }
2227 249543 : if (mlci) {
2228 0 : lv = canditer_mask_next(mlci, lci->seq + lci->next + nlx, true);
2229 0 : if (lv == oid_nil)
2230 0 : nlx = lci->ncand - lci->next;
2231 : else
2232 0 : nlx = lv - lci->seq - lci->next;
2233 : }
2234 249543 : if (lci->next + nlx == lci->ncand)
2235 11 : v = NULL;
2236 : }
2237 : }
2238 251931 : if (nlx > 0) {
2239 5248 : if (only_misses) {
2240 2751 : if (maybeextend(r1, r2, r3, nlx, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
2241 0 : goto bailout;
2242 233039 : while (nlx > 0) {
2243 230287 : lv = canditer_next(lci);
2244 230288 : if (mlci == NULL || canditer_contains(mlci, lv))
2245 230300 : APPEND(r1, lv);
2246 230288 : nlx--;
2247 : }
2248 2752 : if (r1->trevsorted && BATcount(r1) > 1)
2249 647 : r1->trevsorted = false;
2250 2497 : } else if (nil_on_miss) {
2251 19 : if (r2 && r2->tnonil) {
2252 2 : r2->tnil = true;
2253 2 : r2->tnonil = false;
2254 2 : r2->tseqbase = oid_nil;
2255 2 : r2->tsorted = false;
2256 2 : r2->trevsorted = false;
2257 2 : r2->tkey = false;
2258 : }
2259 19 : if (maybeextend(r1, r2, r3, nlx, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
2260 0 : goto bailout;
2261 19 : if (r3)
2262 18 : r3->tnil = false;
2263 2077 : while (nlx > 0) {
2264 2058 : lv = canditer_next(lci);
2265 2058 : if (mlci == NULL || canditer_contains(mlci, lv)) {
2266 2058 : APPEND(r1, lv);
2267 2058 : if (r2)
2268 2 : APPEND(r2, oid_nil);
2269 2058 : if (r3) {
2270 2057 : if (rhasnil || cmp(VALUE(l, lv - l->hseqbase), nil) == 0) {
2271 0 : ((bit *) r3->theap->base)[r3->batCount++] = bit_nil;
2272 0 : r3->tnil = true;
2273 : } else {
2274 2057 : ((bit *) r3->theap->base)[r3->batCount++] = 0;
2275 : }
2276 : }
2277 : }
2278 2058 : nlx--;
2279 : }
2280 19 : if (r1->trevsorted && BATcount(r1) > 1)
2281 6 : r1->trevsorted = false;
2282 : } else {
2283 2478 : canditer_setidx(lci, lci->next + nlx);
2284 : }
2285 : }
2286 274500 : if (v == NULL) {
2287 : /* we have exhausted the inputs */
2288 : break;
2289 : }
2290 : }
2291 :
2292 : /* Here we determine the next value in l that we are
2293 : * going to try to match in r. We will also count the
2294 : * number of occurrences in l of that value.
2295 : * Afterwards, v points to the value and nl is the
2296 : * number of times it occurs. Also, lci will point to
2297 : * the next value to be considered (ready for the next
2298 : * iteration).
2299 : * If there are many equal values in l (more than
2300 : * lscan), we will use binary search to find the end
2301 : * of the sequence. Obviously, we can do this only if
2302 : * l is actually sorted (lscan > 0). */
2303 448255 : nl = 1; /* we'll match (at least) one in l */
2304 448255 : nr = 0; /* maybe we won't match anything in r */
2305 448255 : lv = canditer_peek(lci);
2306 448255 : if (mlci) {
2307 0 : lv = canditer_mask_next(mlci, lv, true);
2308 0 : if (lv == oid_nil)
2309 : break;
2310 0 : canditer_setidx(lci, canditer_search(lci, lv, true));
2311 : }
2312 451435 : v = VALUE(l, lv - l->hseqbase);
2313 451435 : if (li.key) {
2314 : /* if l is key, there is a single value */
2315 227230 : } else if (lscan > 0 &&
2316 135044 : lscan < lci->ncand - lci->next &&
2317 66791 : cmp(v, VALUE(l, canditer_idx(lci, lci->next + lscan) - l->hseqbase)) == 0) {
2318 : /* lots of equal values: use binary search to
2319 : * find end */
2320 1398 : assert(lvals != NULL);
2321 2792 : nl = binsearch(NULL, 0,
2322 1398 : li.type, lvals, lvars,
2323 1398 : li.width, lci->next + lscan,
2324 : BATcount(l),
2325 : v, lordering, 1);
2326 1394 : nl = canditer_search(lci, nl + l->hseqbase, true);
2327 1394 : nl -= lci->next;
2328 : } else {
2329 225715 : struct canditer ci = *lci; /* work on copy */
2330 225715 : nl = 0; /* it will be incremented again */
2331 402984 : do {
2332 402984 : canditer_next(&ci);
2333 399168 : nl++;
2334 792615 : } while (ci.next < ci.ncand &&
2335 396873 : cmp(v, VALUE(l, canditer_peek(&ci) - l->hseqbase)) == 0);
2336 : }
2337 : /* lci->next + nl is the position for the next iteration */
2338 :
2339 444072 : if ((!nil_matches || not_in) && !li.nonil && cmp(v, nil) == 0) {
2340 969 : if (not_in) {
2341 : /* just skip the whole thing: nils
2342 : * don't cause any output */
2343 1 : canditer_setidx(lci, lci->next + nl);
2344 1 : continue;
2345 : }
2346 : /* v is nil and nils don't match anything, set
2347 : * to NULL to indicate nil */
2348 968 : v = NULL;
2349 968 : mark = bit_nil;
2350 968 : if (r3)
2351 54 : r3->tnil = true;
2352 : }
2353 :
2354 : /* First we find the "first" value in r that is "at
2355 : * least as large" as v, then we find the "first"
2356 : * value in r that is "larger" than v. The difference
2357 : * is the number of values equal to v and is stored in
2358 : * nr. The definitions of "larger" and "first" depend
2359 : * on the orderings of l and r. If equal_order is
2360 : * set, we go through r from low to high (this
2361 : * includes the case that l is not sorted); otherwise
2362 : * we go through r from high to low.
2363 : * In either case, we will use binary search on r to
2364 : * find both ends of the sequence of values that are
2365 : * equal to v in case the position is "too far" (more
2366 : * than rscan away). */
2367 54 : if (v == NULL) {
2368 : nr = 0; /* nils don't match anything */
2369 441776 : } else if (ri.type == TYPE_void && is_oid_nil(r->tseqbase)) {
2370 0 : if (is_oid_nil(*(const oid *) v)) {
2371 : /* all values in r match */
2372 0 : nr = rci->ncand;
2373 : } else {
2374 : /* no value in r matches */
2375 : nr = 0;
2376 : }
2377 : /* in either case, we're done after this */
2378 0 : canditer_setidx(rci, equal_order ? rci->ncand : 0);
2379 441776 : } else if (equal_order) {
2380 : /* first find the location of the first value
2381 : * in r that is >= v, then find the location
2382 : * of the first value in r that is > v; the
2383 : * difference is the number of values equal
2384 : * v; we change rci */
2385 :
2386 : /* look ahead a little (rscan) in r to
2387 : * see whether we're better off doing
2388 : * a binary search */
2389 440666 : if (rvals) {
2390 429460 : if (rscan < rci->ncand - rci->next &&
2391 383519 : rordering * cmp(v, VALUE(r, canditer_idx(rci, rci->next + rscan) - r->hseqbase)) > 0) {
2392 : /* value too far away in r:
2393 : * use binary search */
2394 119579 : lv = binsearch(NULL, 0, ri.type, rvals, rvars, ri.width, rci->next + rscan, BATcount(r), v, rordering, 0);
2395 131494 : lv = canditer_search(rci, lv + r->hseqbase, true);
2396 131494 : canditer_setidx(rci, lv);
2397 : } else {
2398 : /* scan r for v */
2399 332209 : while (rci->next < rci->ncand) {
2400 331465 : if (rordering * cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) <= 0)
2401 : break;
2402 21474 : canditer_next(rci);
2403 : }
2404 : }
2405 844200 : if (rci->next < rci->ncand &&
2406 407133 : cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) == 0) {
2407 : /* if we found an equal value,
2408 : * look for the last equal
2409 : * value */
2410 291772 : if (ri.key) {
2411 : /* r is key, there can
2412 : * only be a single
2413 : * equal value */
2414 163194 : nr = 1;
2415 163194 : canditer_next(rci);
2416 254983 : } else if (rscan < rci->ncand - rci->next &&
2417 126407 : cmp(v, VALUE(r, canditer_idx(rci, rci->next + rscan) - r->hseqbase)) == 0) {
2418 : /* many equal values:
2419 : * use binary search
2420 : * to find the end */
2421 43412 : nr = binsearch(NULL, 0, ri.type, rvals, rvars, ri.width, rci->next + rscan, BATcount(r), v, rordering, 1);
2422 43412 : nr = canditer_search(rci, nr + r->hseqbase, true);
2423 43412 : nr -= rci->next;
2424 43412 : canditer_setidx(rci, rci->next + nr);
2425 : } else {
2426 : /* scan r for end of
2427 : * range */
2428 233544 : do {
2429 233544 : nr++;
2430 233544 : canditer_next(rci);
2431 466575 : } while (rci->next < rci->ncand &&
2432 233043 : cmp(v, VALUE(r, canditer_peek(rci) - r->hseqbase)) == 0);
2433 : }
2434 : }
2435 : } else {
2436 11206 : assert(rordering == 1);
2437 11206 : rval = canditer_search(&rrci, *(const oid*)v, true) + r->hseqbase;
2438 11206 : lv = canditer_search(rci, rval, true);
2439 11206 : canditer_setidx(rci, lv);
2440 11206 : nr = (canditer_idx(&rrci, canditer_peek(rci) - r->hseqbase) == *(oid*)v);
2441 11206 : if (nr == 1)
2442 11206 : canditer_next(rci);
2443 : }
2444 : /* rci points to first value > v or end of r,
2445 : * and nr is the number of values in r that
2446 : * are equal to v */
2447 : } else {
2448 : /* first find the location of the first value
2449 : * in r that is > v, then find the location
2450 : * of the first value in r that is >= v; the
2451 : * difference is the number of values equal
2452 : * v; we change rci */
2453 :
2454 : /* look back from the end a little
2455 : * (rscan) in r to see whether we're
2456 : * better off doing a binary search */
2457 1110 : if (rvals) {
2458 1110 : if (rci->next > rscan &&
2459 627 : rordering * cmp(v, VALUE(r, canditer_idx(rci, rci->next - rscan) - r->hseqbase)) < 0) {
2460 : /* value too far away
2461 : * in r: use binary
2462 : * search */
2463 30 : lv = binsearch(NULL, 0, ri.type, rvals, rvars, ri.width, 0, rci->next - rscan, v, rordering, 1);
2464 30 : lv = canditer_search(rci, lv + r->hseqbase, true);
2465 30 : canditer_setidx(rci, lv);
2466 : } else {
2467 : /* scan r for v */
2468 2267 : while (rci->next > 0 &&
2469 2261 : rordering * cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) < 0)
2470 1187 : canditer_prev(rci);
2471 : }
2472 2199 : if (rci->next > 0 &&
2473 1089 : cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) == 0) {
2474 : /* if we found an equal value,
2475 : * look for the last equal
2476 : * value */
2477 1001 : if (ri.key) {
2478 : /* r is key, there can only be a single equal value */
2479 413 : nr = 1;
2480 413 : canditer_prev(rci);
2481 1077 : } else if (rci->next > rscan &&
2482 489 : cmp(v, VALUE(r, canditer_idx(rci, rci->next - rscan) - r->hseqbase)) == 0) {
2483 : /* use binary search to find the start */
2484 42 : nr = binsearch(NULL, 0, ri.type, rvals, rvars, ri.width, 0, rci->next - rscan, v, rordering, 0);
2485 42 : nr = canditer_search(rci, nr + r->hseqbase, true);
2486 42 : nr = rci->next - nr;
2487 42 : canditer_setidx(rci, rci->next - nr);
2488 : } else {
2489 : /* scan r for start of range */
2490 650 : do {
2491 650 : canditer_prev(rci);
2492 650 : nr++;
2493 1244 : } while (rci->next > 0 &&
2494 594 : cmp(v, VALUE(r, canditer_peekprev(rci) - r->hseqbase)) == 0);
2495 : }
2496 : }
2497 : } else {
2498 0 : lv = canditer_search(&rrci, *(const oid *)v, true);
2499 0 : lv = canditer_search(rci, lv + r->hseqbase, true);
2500 0 : nr = (canditer_idx(rci, lv) == *(const oid*)v);
2501 0 : canditer_setidx(rci, lv);
2502 : }
2503 : /* rci points to first value > v
2504 : * or end of r, and nr is the number of values
2505 : * in r that are equal to v */
2506 : }
2507 :
2508 307544 : if (nr == 0) {
2509 : /* no entries in r found */
2510 149885 : if (!(nil_on_miss | only_misses)) {
2511 108781 : if (min_one) {
2512 0 : GDKerror("not enough matches");
2513 0 : goto bailout;
2514 : }
2515 114054 : if (lscan > 0 &&
2516 5273 : (equal_order ? rci->next == rci->ncand : rci->next == 0)) {
2517 : /* nothing more left to match
2518 : * in r */
2519 : break;
2520 : }
2521 108635 : canditer_setidx(lci, lci->next + nl);
2522 107863 : continue;
2523 : }
2524 : /* insert a nil to indicate a non-match */
2525 41104 : insert_nil = true;
2526 41104 : nr = 1;
2527 41104 : if (r2) {
2528 4 : r2->tnil = true;
2529 4 : r2->tnonil = false;
2530 4 : r2->tsorted = false;
2531 4 : r2->trevsorted = false;
2532 4 : r2->tseqbase = oid_nil;
2533 4 : r2->tkey = false;
2534 : }
2535 303923 : } else if (nr > 1 && max_one) {
2536 23 : GDKerror("more than one match");
2537 23 : goto bailout;
2538 303900 : } else if (only_misses) {
2539 : /* we had a match, so we're not interested */
2540 144736 : canditer_setidx(lci, lci->next + nl);
2541 144933 : continue;
2542 : } else {
2543 159164 : insert_nil = false;
2544 159164 : if (semi) {
2545 : /* for semi-join, only insert single
2546 : * value */
2547 35936 : nr = 1;
2548 : }
2549 : }
2550 : /* make space: nl values in l match nr values in r, so
2551 : * we need to add nl * nr values in the results */
2552 200268 : if (maybeextend(r1, r2, r3, nl * nr, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
2553 0 : goto bailout;
2554 :
2555 : /* maintain properties */
2556 200534 : if (nl > 1) {
2557 63286 : if (r2) {
2558 : /* value occurs multiple times in l,
2559 : * so entry in r will be repeated
2560 : * multiple times: hence r2 is not key
2561 : * and not dense */
2562 11616 : r2->tkey = false;
2563 11616 : r2->tseqbase = oid_nil;
2564 : }
2565 : /* multiple different values will be inserted
2566 : * in r1 (always in order), so not reverse
2567 : * ordered anymore */
2568 63286 : r1->trevsorted = false;
2569 : }
2570 200534 : if (nr > 1) {
2571 : /* value occurs multiple times in r, so entry
2572 : * in l will be repeated multiple times: hence
2573 : * r1 is not key and not dense */
2574 43202 : r1->tkey = false;
2575 43202 : if (r2) {
2576 : /* multiple different values will be
2577 : * inserted in r2 (in order), so not
2578 : * reverse ordered anymore */
2579 42786 : r2->trevsorted = false;
2580 42786 : if (nl > 1) {
2581 : /* multiple values in l match
2582 : * multiple values in r, so an
2583 : * ordered sequence will be
2584 : * inserted multiple times in
2585 : * r2, so r2 is not ordered
2586 : * anymore */
2587 3964 : r2->tsorted = false;
2588 : }
2589 : }
2590 : }
2591 200534 : if (lscan == 0) {
2592 : /* deduce relative positions of r matches for
2593 : * this and previous value in v */
2594 65411 : if (prev && r2) {
2595 : /* keyness or r2 can only be assured
2596 : * as long as matched values are
2597 : * ordered */
2598 64167 : int ord = rordering * cmp(prev, v ? v : nil);
2599 64731 : if (ord < 0) {
2600 : /* previous value in l was
2601 : * less than current */
2602 26462 : r2->trevsorted = false;
2603 26462 : r2->tkey &= r2->tsorted;
2604 38269 : } else if (ord > 0) {
2605 : /* previous value was
2606 : * greater */
2607 25557 : r2->tsorted = false;
2608 25557 : r2->tkey &= r2->trevsorted;
2609 : } else {
2610 : /* value can be equal if
2611 : * intervening values in l
2612 : * didn't match anything; if
2613 : * multiple values match in r,
2614 : * r2 won't be sorted */
2615 12712 : r2->tkey = false;
2616 12712 : if (nr > 1) {
2617 12670 : r2->tsorted = false;
2618 12670 : r2->trevsorted = false;
2619 : }
2620 : }
2621 : }
2622 65975 : prev = v ? v : nil;
2623 : }
2624 201098 : if (BATcount(r1) > 0) {
2625 : /* a new, higher value will be inserted into
2626 : * r1, so r1 is not reverse ordered anymore */
2627 196263 : r1->trevsorted = false;
2628 196263 : if (r2) {
2629 : /* depending on whether l and r are
2630 : * ordered the same or not, a new
2631 : * higher or lower value will be added
2632 : * to r2 */
2633 69479 : if (equal_order)
2634 69324 : r2->trevsorted = false;
2635 : else {
2636 155 : r2->tsorted = false;
2637 155 : r2->tseqbase = oid_nil;
2638 : }
2639 : }
2640 : }
2641 :
2642 : /* insert values: first the left output */
2643 : BUN nladded = 0;
2644 564839 : for (i = 0; i < nl; i++) {
2645 364500 : lv = canditer_next(lci);
2646 363741 : if (mlci == NULL || canditer_contains(mlci, lv)) {
2647 363680 : nladded++;
2648 39857053 : for (j = 0; j < nr; j++)
2649 39493373 : APPEND(r1, lv);
2650 : }
2651 : }
2652 200339 : nl = nladded;
2653 : /* then the right output, various different ways of
2654 : * doing it */
2655 200339 : if (r2) {
2656 70032 : if (insert_nil) {
2657 11 : for (i = 0; i < nl; i++) {
2658 14 : for (j = 0; j < nr; j++) {
2659 7 : APPEND(r2, oid_nil);
2660 : }
2661 : }
2662 70028 : } else if (equal_order) {
2663 69719 : struct canditer ci = *rci; /* work on copy */
2664 69719 : if (r2->batCount > 0 &&
2665 69127 : BATtdense(r2) &&
2666 5375 : ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != canditer_idx(&ci, ci.next - nr))
2667 104 : r2->tseqbase = oid_nil;
2668 166122 : for (i = 0; i < nl; i++) {
2669 96110 : canditer_setidx(&ci, ci.next - nr);
2670 39417047 : for (j = 0; j < nr; j++) {
2671 39224534 : APPEND(r2, canditer_next(&ci));
2672 : }
2673 : }
2674 : } else {
2675 309 : if (r2->batCount > 0 &&
2676 155 : BATtdense(r2) &&
2677 0 : ((oid *) r2->theap->base)[r2->batCount - 1] + 1 != canditer_peek(rci))
2678 0 : r2->tseqbase = oid_nil;
2679 8268 : for (i = 0; i < nl; i++) {
2680 7959 : struct canditer ci = *rci; /* work on copy */
2681 16600 : for (j = 0; j < nr; j++) {
2682 8641 : APPEND(r2, canditer_next(&ci));
2683 : }
2684 : }
2685 : }
2686 : }
2687 : /* finally the mark output */
2688 200632 : if (r3) {
2689 2677 : if (insert_nil) {
2690 340 : r3->tnil |= rhasnil;
2691 852 : for (i = 0; i < nl; i++) {
2692 1024 : for (j = 0; j < nr; j++) {
2693 512 : ((bit *) r3->theap->base)[r3->batCount++] = mark;
2694 : }
2695 : }
2696 : } else {
2697 8139 : for (i = 0; i < nl; i++) {
2698 11604 : for (j = 0; j < nr; j++) {
2699 5802 : ((bit *) r3->theap->base)[r3->batCount++] = 1;
2700 : }
2701 : }
2702 : }
2703 : }
2704 : }
2705 : /* also set other bits of heap to correct value to indicate size */
2706 8186 : BATsetcount(r1, BATcount(r1));
2707 8219 : r1->tseqbase = oid_nil;
2708 8219 : if (r1->tkey)
2709 8112 : r1 = virtualize(r1);
2710 8100 : if (r2) {
2711 2387 : BATsetcount(r2, BATcount(r2));
2712 2394 : assert(BATcount(r1) == BATcount(r2));
2713 2394 : r2->tseqbase = oid_nil;
2714 2394 : if (BATcount(r2) <= 1) {
2715 1486 : r2->tkey = true;
2716 1486 : r2 = virtualize(r2);
2717 : }
2718 : }
2719 8120 : if (r3) {
2720 71 : BATsetcount(r3, BATcount(r3));
2721 71 : assert(BATcount(r1) == BATcount(r3));
2722 71 : r3->tseqbase = oid_nil;
2723 71 : r3->tnonil = !r3->tnil;
2724 71 : if (BATcount(r3) <= 1) {
2725 0 : r3->tkey = true;
2726 0 : r3->tsorted = true;
2727 0 : r3->trevsorted = true;
2728 : }
2729 : }
2730 8120 : bat_iterator_end(&li);
2731 8204 : bat_iterator_end(&ri);
2732 8106 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
2733 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
2734 : "sr=" ALGOOPTBATFMT ","
2735 : "nil_on_miss=%s,semi=%s,only_misses=%s,not_in=%s;%s %s "
2736 : "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
2737 : ALGOBATPAR(l), ALGOBATPAR(r),
2738 : ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
2739 : nil_on_miss ? "true" : "false",
2740 : semi ? "true" : "false",
2741 : only_misses ? "true" : "false",
2742 : not_in ? "true" : "false",
2743 : swapped ? " swapped" : "", reason,
2744 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
2745 : GDKusec() - t0);
2746 :
2747 : return GDK_SUCCEED;
2748 :
2749 23 : bailout:
2750 23 : bat_iterator_end(&li);
2751 23 : bat_iterator_end(&ri);
2752 23 : BBPreclaim(r1);
2753 23 : BBPreclaim(r2);
2754 23 : BBPreclaim(r3);
2755 : return GDK_FAIL;
2756 : }
2757 :
2758 : #define HASHLOOPBODY() \
2759 : do { \
2760 : if (nr >= 1 && max_one) { \
2761 : GDKerror("more than one match"); \
2762 : goto bailout; \
2763 : } \
2764 : if (maybeextend(r1, r2, r3, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
2765 : goto bailout; \
2766 : APPEND(r1, lo); \
2767 : if (r2) \
2768 : APPEND(r2, ro); \
2769 : if (r3) \
2770 : ((bit *) r3->theap->base)[r3->batCount++] = 1; \
2771 : nr++; \
2772 : } while (false)
2773 :
2774 : #define EQ_int(a, b) ((a) == (b))
2775 : #define EQ_lng(a, b) ((a) == (b))
2776 : #ifdef HAVE_HGE
2777 : #define EQ_uuid(a, b) ((a).h == (b).h)
2778 : #else
2779 : #define EQ_uuid(a, b) (memcmp((a).u, (b).u, UUID_SIZE) == 0)
2780 : #endif
2781 :
2782 : #define HASHJOIN(TYPE) \
2783 : do { \
2784 : TYPE *rvals = ri.base; \
2785 : TYPE *lvals = li.base; \
2786 : TYPE v; \
2787 : while (lci->next < lci->ncand) { \
2788 : GDK_CHECK_TIMEOUT(qry_ctx, counter, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx)); \
2789 : lo = canditer_next(lci); \
2790 : v = lvals[lo - l->hseqbase]; \
2791 : nr = 0; \
2792 : bit mark = defmark; \
2793 : if ((!nil_matches || not_in) && is_##TYPE##_nil(v)) { \
2794 : /* no match */ \
2795 : if (not_in) { \
2796 : lskipped = BATcount(r1) > 0; \
2797 : continue; \
2798 : } \
2799 : mark = bit_nil; \
2800 : } else if (hash_cand) { \
2801 : /* private hash: no locks */ \
2802 : for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
2803 : rb != BUN_NONE; \
2804 : rb = HASHgetlink(hsh, rb)) { \
2805 : ro = canditer_idx(rci, rb); \
2806 : if (!EQ_##TYPE(v, rvals[ro - r->hseqbase])) \
2807 : continue; \
2808 : if (only_misses) { \
2809 : nr++; \
2810 : break; \
2811 : } \
2812 : HASHLOOPBODY(); \
2813 : if (semi && !max_one) \
2814 : break; \
2815 : } \
2816 : } else if (rci->tpe != cand_dense) { \
2817 : for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
2818 : rb != BUN_NONE; \
2819 : rb = HASHgetlink(hsh, rb)) { \
2820 : if (rb >= rl && rb < rh && \
2821 : EQ_##TYPE(v, rvals[rb]) && \
2822 : canditer_contains(rci, ro = (oid) (rb - roff + rseq))) { \
2823 : if (only_misses) { \
2824 : nr++; \
2825 : break; \
2826 : } \
2827 : HASHLOOPBODY(); \
2828 : if (semi && !max_one) \
2829 : break; \
2830 : } \
2831 : } \
2832 : } else { \
2833 : for (rb = HASHget(hsh, hash_##TYPE(hsh, &v)); \
2834 : rb != BUN_NONE; \
2835 : rb = HASHgetlink(hsh, rb)) { \
2836 : if (rb >= rl && rb < rh && \
2837 : EQ_##TYPE(v, rvals[rb])) { \
2838 : if (only_misses) { \
2839 : nr++; \
2840 : break; \
2841 : } \
2842 : ro = (oid) (rb - roff + rseq); \
2843 : HASHLOOPBODY(); \
2844 : if (semi && !max_one) \
2845 : break; \
2846 : } \
2847 : } \
2848 : } \
2849 : if (nr == 0) { \
2850 : if (only_misses) { \
2851 : nr = 1; \
2852 : if (maybeextend(r1, r2, r3, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
2853 : goto bailout; \
2854 : APPEND(r1, lo); \
2855 : if (lskipped) \
2856 : r1->tseqbase = oid_nil; \
2857 : } else if (nil_on_miss) { \
2858 : nr = 1; \
2859 : if (maybeextend(r1, r2, r3, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED) \
2860 : goto bailout; \
2861 : APPEND(r1, lo); \
2862 : if (r2) { \
2863 : r2->tnil = true; \
2864 : r2->tnonil = false; \
2865 : r2->tkey = false; \
2866 : APPEND(r2, oid_nil); \
2867 : } \
2868 : if (r3) { \
2869 : r3->tnil |= mark == bit_nil; \
2870 : ((bit *) r3->theap->base)[r3->batCount++] = mark; \
2871 : } \
2872 : } else if (min_one) { \
2873 : GDKerror("not enough matches"); \
2874 : goto bailout; \
2875 : } else { \
2876 : lskipped = BATcount(r1) > 0; \
2877 : } \
2878 : } else if (only_misses) { \
2879 : lskipped = BATcount(r1) > 0; \
2880 : } else { \
2881 : if (lskipped) { \
2882 : /* note, we only get here in an \
2883 : * iteration *after* lskipped was \
2884 : * first set to true, i.e. we did \
2885 : * indeed skip values in l */ \
2886 : r1->tseqbase = oid_nil; \
2887 : } \
2888 : if (nr > 1) { \
2889 : r1->tkey = false; \
2890 : r1->tseqbase = oid_nil; \
2891 : } \
2892 : } \
2893 : if (nr > 0 && BATcount(r1) > nr) \
2894 : r1->trevsorted = false; \
2895 : } \
2896 : } while (0)
2897 :
2898 : /* Implementation of join using a hash lookup of values in the right
2899 : * column. */
2900 : static gdk_return
2901 17626 : hashjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
2902 : struct canditer *restrict lci, struct canditer *restrict rci,
2903 : bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
2904 : bool not_in, bool max_one, bool min_one,
2905 : BUN estimate, lng t0, bool swapped,
2906 : bool hash, bool phash, bool hash_cand,
2907 : const char *reason)
2908 : {
2909 17626 : oid lo, ro;
2910 17626 : BATiter li, ri;
2911 17626 : BUN rb, roff = 0;
2912 : /* rl, rh: lower and higher bounds for BUN values in hash table */
2913 17626 : BUN rl, rh;
2914 17626 : oid rseq;
2915 17626 : BUN nr;
2916 17626 : const char *lvals;
2917 17626 : const char *lvars;
2918 17626 : const void *nil = ATOMnilptr(l->ttype);
2919 17626 : int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
2920 17626 : oid lval = oid_nil; /* hold value if l is dense */
2921 17626 : const char *v = (const char *) &lval;
2922 17626 : bool lskipped = false; /* whether we skipped values in l */
2923 17626 : Hash *restrict hsh = NULL;
2924 17626 : bool locked = false;
2925 17626 : BUN maxsize;
2926 17626 : BAT *r1 = NULL;
2927 17626 : BAT *r2 = NULL;
2928 17626 : BAT *r3 = NULL;
2929 17626 : BAT *b = NULL;
2930 :
2931 52839 : assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
2932 :
2933 17626 : size_t counter = 0;
2934 17626 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
2935 :
2936 17629 : li = bat_iterator(l);
2937 17642 : ri = bat_iterator(r);
2938 :
2939 17630 : int t = ATOMbasetype(ri.type);
2940 17630 : if (BATtvoid(r) || BATtvoid(l))
2941 5 : t = TYPE_void;
2942 :
2943 17630 : lvals = (const char *) li.base;
2944 17630 : if (li.vh && li.type) {
2945 1141 : assert(ri.vh && ri.type);
2946 1141 : lvars = li.vh->base;
2947 : } else {
2948 16489 : assert(ri.vh == NULL);
2949 : lvars = NULL;
2950 : }
2951 : /* offset to convert BUN to OID for value in right column */
2952 17630 : rseq = r->hseqbase;
2953 :
2954 17630 : rl = rci->seq - r->hseqbase;
2955 17630 : rh = canditer_last(rci) + 1 - r->hseqbase;
2956 17630 : if (hash_cand) {
2957 : /* we need to create a hash on r specific for the
2958 : * candidate list */
2959 184 : char ext[32];
2960 184 : assert(rci->s);
2961 236 : MT_thread_setalgorithm(swapped ? "hashjoin using candidate hash (swapped)" : "hashjoin using candidate hash");
2962 184 : TRC_DEBUG(ALGO, ALGOBATFMT ": creating "
2963 : "hash for candidate list " ALGOBATFMT "%s%s\n",
2964 : ALGOBATPAR(r), ALGOBATPAR(rci->s),
2965 : r->thash ? " ignoring existing hash" : "",
2966 : swapped ? " (swapped)" : "");
2967 184 : if (snprintf(ext, sizeof(ext), "thshjn%x",
2968 184 : (unsigned) MT_getpid()) >= (int) sizeof(ext))
2969 0 : goto bailout;
2970 184 : if ((hsh = BAThash_impl(r, rci, ext)) == NULL) {
2971 0 : goto bailout;
2972 : }
2973 17446 : } else if (phash) {
2974 : /* there is a hash on the parent which we should use */
2975 1929 : MT_thread_setalgorithm(swapped ? "hashjoin using parent hash (swapped)" : "hashjoin using parent hash");
2976 1677 : b = BATdescriptor(VIEWtparent(r));
2977 1678 : if (b == NULL)
2978 0 : goto bailout;
2979 1678 : TRC_DEBUG(ALGO, "%s: using "
2980 : "parent(" ALGOBATFMT ") for hash%s\n",
2981 : BATgetId(r), ALGOBATPAR(b),
2982 : swapped ? " (swapped)" : "");
2983 1678 : roff = r->tbaseoff - b->tbaseoff;
2984 1678 : rl += roff;
2985 1678 : rh += roff;
2986 1678 : r = b;
2987 1678 : bat_iterator_end(&ri);
2988 1677 : ri = bat_iterator(r);
2989 1678 : MT_rwlock_rdlock(&r->thashlock);
2990 1678 : hsh = r->thash;
2991 1678 : locked = true;
2992 15769 : } else if (hash) {
2993 : /* there is a hash on r which we should use */
2994 13313 : MT_thread_setalgorithm(swapped ? "hashjoin using existing hash (swapped)" : "hashjoin using existing hash");
2995 7714 : MT_rwlock_rdlock(&r->thashlock);
2996 7715 : hsh = r->thash;
2997 7715 : locked = true;
2998 7715 : TRC_DEBUG(ALGO, ALGOBATFMT ": using "
2999 : "existing hash%s\n",
3000 : ALGOBATPAR(r),
3001 : swapped ? " (swapped)" : "");
3002 8057 : } else if (BATtdensebi(&ri)) {
3003 : /* no hash, just dense lookup */
3004 0 : MT_thread_setalgorithm(swapped ? "hashjoin on dense (swapped)" : "hashjoin on dense");
3005 : } else {
3006 : /* we need to create a hash on r */
3007 11255 : MT_thread_setalgorithm(swapped ? "hashjoin using new hash (swapped)" : "hashjoin using new hash");
3008 8061 : TRC_DEBUG(ALGO, ALGOBATFMT ": creating hash%s\n",
3009 : ALGOBATPAR(r),
3010 : swapped ? " (swapped)" : "");
3011 8061 : if (BAThash(r) != GDK_SUCCEED)
3012 0 : goto bailout;
3013 8010 : MT_rwlock_rdlock(&r->thashlock);
3014 8059 : hsh = r->thash;
3015 8059 : locked = true;
3016 : }
3017 17636 : if (locked && hsh == NULL) {
3018 0 : GDKerror("Hash disappeared for "ALGOBATFMT"\n", ALGOBATPAR(r));
3019 0 : goto bailout;
3020 : }
3021 17636 : assert(hsh != NULL || BATtdensebi(&ri));
3022 : if (hsh) {
3023 17636 : TRC_DEBUG(ALGO, "hash for " ALGOBATFMT ": nbucket " BUNFMT ", nunique " BUNFMT ", nheads " BUNFMT "\n", ALGOBATPAR(r), hsh->nbucket, hsh->nunique, hsh->nheads);
3024 : }
3025 :
3026 17636 : bit defmark = 0;
3027 17636 : if ((not_in || r3p) && !ri.nonil) {
3028 : /* check whether there is a nil on the right, since if
3029 : * so, we should return an empty result if not_in is
3030 : * set, or use a NIL mark for non-matches if r3p is
3031 : * set */
3032 481 : if (hash_cand) {
3033 0 : for (rb = HASHget(hsh, HASHprobe(hsh, nil));
3034 0 : rb != BUN_NONE;
3035 0 : rb = HASHgetlink(hsh, rb)) {
3036 0 : ro = canditer_idx(rci, rb);
3037 0 : if ((*cmp)(nil, BUNtail(ri, ro - r->hseqbase)) == 0) {
3038 0 : assert(!locked);
3039 0 : if (r3p) {
3040 0 : defmark = bit_nil;
3041 0 : break;
3042 : }
3043 0 : HEAPfree(&hsh->heaplink, true);
3044 0 : HEAPfree(&hsh->heapbckt, true);
3045 0 : GDKfree(hsh);
3046 0 : bat_iterator_end(&li);
3047 0 : bat_iterator_end(&ri);
3048 0 : BBPreclaim(b);
3049 0 : return nomatch(r1p, r2p, r3p, l, r, lci,
3050 : bit_nil, false, false,
3051 : __func__, t0);
3052 : }
3053 : }
3054 481 : } else if (!BATtdensebi(&ri)) {
3055 481 : for (rb = HASHget(hsh, HASHprobe(hsh, nil));
3056 5071 : rb != BUN_NONE;
3057 4593 : rb = HASHgetlink(hsh, rb)) {
3058 4625 : if (rb >= rl && rb < rh &&
3059 4617 : (cmp == NULL ||
3060 4621 : (*cmp)(nil, BUNtail(ri, rb)) == 0)) {
3061 28 : if (r3p) {
3062 27 : defmark = bit_nil;
3063 27 : break;
3064 : }
3065 1 : if (locked)
3066 1 : MT_rwlock_rdunlock(&r->thashlock);
3067 1 : bat_iterator_end(&li);
3068 1 : bat_iterator_end(&ri);
3069 1 : BBPreclaim(b);
3070 1 : return nomatch(r1p, r2p, r3p, l, r, lci,
3071 : bit_nil, false, false,
3072 : __func__, t0);
3073 : }
3074 : }
3075 : }
3076 : }
3077 :
3078 35185 : maxsize = joininitresults(r1p, r2p, r3p, lci->ncand, rci->ncand,
3079 17628 : li.key, ri.key, semi | max_one,
3080 : nil_on_miss, only_misses, min_one,
3081 : estimate);
3082 17557 : if (maxsize == BUN_NONE) {
3083 0 : goto bailout;
3084 : }
3085 :
3086 17557 : r1 = *r1p;
3087 17557 : r2 = r2p ? *r2p : NULL;
3088 17557 : r3 = r3p ? *r3p : NULL;
3089 :
3090 : /* basic properties will be adjusted if necessary later on,
3091 : * they were initially set by joininitresults() */
3092 :
3093 17557 : if (r2) {
3094 14099 : r2->tkey = li.key;
3095 : /* r2 is not likely to be sorted (although it is
3096 : * certainly possible) */
3097 14099 : r2->tsorted = false;
3098 14099 : r2->trevsorted = false;
3099 14099 : r2->tseqbase = oid_nil;
3100 : }
3101 :
3102 17557 : if (lci->tpe != cand_dense)
3103 405 : r1->tseqbase = oid_nil;
3104 :
3105 :
3106 17557 : switch (t) {
3107 14178 : case TYPE_int:
3108 362697648 : HASHJOIN(int);
3109 : break;
3110 1500 : case TYPE_lng:
3111 113668423 : HASHJOIN(lng);
3112 : break;
3113 0 : case TYPE_uuid:
3114 0 : HASHJOIN(uuid);
3115 0 : break;
3116 : default:
3117 2580082 : while (lci->next < lci->ncand) {
3118 2578204 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
3119 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
3120 2578204 : lo = canditer_next(lci);
3121 2579323 : if (BATtdensebi(&li))
3122 323 : lval = lo - l->hseqbase + l->tseqbase;
3123 2579000 : else if (li.type != TYPE_void)
3124 2603284 : v = VALUE(l, lo - l->hseqbase);
3125 2579323 : nr = 0;
3126 2579323 : bit mark = defmark;
3127 2579323 : if ((!nil_matches || not_in) && cmp(v, nil) == 0) {
3128 : /* no match */
3129 2982 : if (not_in) {
3130 10 : lskipped = BATcount(r1) > 0;
3131 10 : continue;
3132 : }
3133 2972 : mark = bit_nil;
3134 2578382 : } else if (hash_cand) {
3135 0 : for (rb = HASHget(hsh, HASHprobe(hsh, v));
3136 0 : rb != BUN_NONE;
3137 0 : rb = HASHgetlink(hsh, rb)) {
3138 0 : ro = canditer_idx(rci, rb);
3139 0 : if ((*cmp)(v, BUNtail(ri, ro - r->hseqbase)) != 0)
3140 0 : continue;
3141 0 : if (only_misses) {
3142 0 : nr++;
3143 0 : break;
3144 : }
3145 0 : HASHLOOPBODY();
3146 0 : if (semi && !max_one)
3147 : break;
3148 : }
3149 2578382 : } else if (hsh == NULL) {
3150 0 : assert(BATtdensebi(&ri));
3151 0 : ro = *(const oid *) v;
3152 0 : if (ro >= r->tseqbase &&
3153 0 : ro < r->tseqbase + r->batCount) {
3154 0 : ro -= r->tseqbase;
3155 0 : ro += rseq;
3156 0 : if (canditer_contains(rci, ro)) {
3157 0 : if (only_misses) {
3158 17574 : nr++;
3159 : break;
3160 : }
3161 0 : HASHLOOPBODY();
3162 0 : if (semi && !max_one)
3163 : break;
3164 : }
3165 : }
3166 2578382 : } else if (rci->tpe != cand_dense) {
3167 0 : for (rb = HASHget(hsh, HASHprobe(hsh, v));
3168 0 : rb != BUN_NONE;
3169 0 : rb = HASHgetlink(hsh, rb)) {
3170 0 : if (rb >= rl && rb < rh &&
3171 0 : (*(cmp))(v, BUNtail(ri, rb)) == 0 &&
3172 0 : canditer_contains(rci, ro = (oid) (rb - roff + rseq))) {
3173 0 : if (only_misses) {
3174 0 : nr++;
3175 0 : break;
3176 : }
3177 0 : HASHLOOPBODY();
3178 0 : if (semi && !max_one)
3179 : break;
3180 : }
3181 : }
3182 : } else {
3183 2578382 : for (rb = HASHget(hsh, HASHprobe(hsh, v));
3184 5041902 : rb != BUN_NONE;
3185 2418230 : rb = HASHgetlink(hsh, rb)) {
3186 5157333 : if (rb >= rl && rb < rh &&
3187 2616107 : (*(cmp))(v, BUNtail(ri, rb)) == 0) {
3188 2198837 : if (only_misses) {
3189 49129 : nr++;
3190 49129 : break;
3191 : }
3192 2149708 : ro = (oid) (rb - roff + rseq);
3193 2149708 : HASHLOOPBODY();
3194 2076464 : if (semi && !max_one)
3195 : break;
3196 : }
3197 : }
3198 : }
3199 2578355 : if (nr == 0) {
3200 393256 : if (only_misses) {
3201 260 : nr = 1;
3202 260 : if (maybeextend(r1, r2, r3, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
3203 0 : goto bailout;
3204 260 : APPEND(r1, lo);
3205 260 : if (lskipped)
3206 231 : r1->tseqbase = oid_nil;
3207 392996 : } else if (nil_on_miss) {
3208 19430 : nr = 1;
3209 19430 : if (maybeextend(r1, r2, r3, 1, lci->next, lci->ncand, maxsize) != GDK_SUCCEED)
3210 0 : goto bailout;
3211 19268 : APPEND(r1, lo);
3212 19268 : if (r2) {
3213 0 : r2->tnil = true;
3214 0 : r2->tnonil = false;
3215 0 : r2->tkey = false;
3216 0 : APPEND(r2, oid_nil);
3217 : }
3218 19268 : if (r3) {
3219 19268 : r3->tnil |= mark == bit_nil;
3220 19268 : ((bit *) r3->theap->base)[r3->batCount++] = mark;
3221 : }
3222 373566 : } else if (min_one) {
3223 0 : GDKerror("not enough matches");
3224 0 : goto bailout;
3225 : } else {
3226 373566 : lskipped = BATcount(r1) > 0;
3227 : }
3228 2185099 : } else if (only_misses) {
3229 49109 : lskipped = BATcount(r1) > 0;
3230 : } else {
3231 2135990 : if (lskipped) {
3232 : /* note, we only get here in an
3233 : * iteration *after* lskipped was
3234 : * first set to true, i.e. we did
3235 : * indeed skip values in l */
3236 1972454 : r1->tseqbase = oid_nil;
3237 : }
3238 2135990 : if (nr > 1) {
3239 2490 : r1->tkey = false;
3240 2490 : r1->tseqbase = oid_nil;
3241 : }
3242 : }
3243 2578193 : if (nr > 0 && BATcount(r1) > nr)
3244 2216143 : r1->trevsorted = false;
3245 : }
3246 : break;
3247 : }
3248 17574 : if (locked) {
3249 17378 : locked = false;
3250 17378 : MT_rwlock_rdunlock(&r->thashlock);
3251 : }
3252 17641 : bat_iterator_end(&li);
3253 17631 : bat_iterator_end(&ri);
3254 :
3255 17627 : if (hash_cand) {
3256 184 : HEAPfree(&hsh->heaplink, true);
3257 184 : HEAPfree(&hsh->heapbckt, true);
3258 184 : GDKfree(hsh);
3259 : }
3260 : /* also set other bits of heap to correct value to indicate size */
3261 17627 : BATsetcount(r1, BATcount(r1));
3262 17553 : r1->tunique_est = MIN(l->tunique_est, r->tunique_est);
3263 17553 : if (BATcount(r1) <= 1) {
3264 6451 : r1->tsorted = true;
3265 6451 : r1->trevsorted = true;
3266 6451 : r1->tkey = true;
3267 6451 : r1->tseqbase = 0;
3268 : }
3269 17553 : if (r2) {
3270 14130 : BATsetcount(r2, BATcount(r2));
3271 14142 : assert(BATcount(r1) == BATcount(r2));
3272 14142 : if (BATcount(r2) <= 1) {
3273 5260 : r2->tsorted = true;
3274 5260 : r2->trevsorted = true;
3275 5260 : r2->tkey = true;
3276 5260 : r2->tseqbase = 0;
3277 : }
3278 21058 : r2->tunique_est = MIN(l->tunique_est, r->tunique_est);
3279 : }
3280 17565 : if (r3) {
3281 49 : r3->tnonil = !r3->tnil;
3282 49 : BATsetcount(r3, BATcount(r3));
3283 49 : assert(BATcount(r1) == BATcount(r3));
3284 86 : r3->tunique_est = MIN(l->tunique_est, r->tunique_est);
3285 : }
3286 17565 : if (BATcount(r1) > 0) {
3287 12457 : if (BATtdense(r1))
3288 6404 : r1->tseqbase = ((oid *) r1->theap->base)[0];
3289 12457 : if (r2 && BATtdense(r2))
3290 1257 : r2->tseqbase = ((oid *) r2->theap->base)[0];
3291 : } else {
3292 5108 : r1->tseqbase = 0;
3293 5108 : if (r2) {
3294 3975 : r2->tseqbase = 0;
3295 : }
3296 : }
3297 17565 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
3298 : ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
3299 : "nil_matches=%s,nil_on_miss=%s,semi=%s,only_misses=%s,"
3300 : "not_in=%s,max_one=%s,min_one=%s;%s %s -> " ALGOBATFMT "," ALGOOPTBATFMT
3301 : " (" LLFMT "usec)\n",
3302 : ALGOBATPAR(l), ALGOBATPAR(r),
3303 : ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
3304 : nil_matches ? "true" : "false",
3305 : nil_on_miss ? "true" : "false",
3306 : semi ? "true" : "false",
3307 : only_misses ? "true" : "false",
3308 : not_in ? "true" : "false",
3309 : max_one ? "true" : "false",
3310 : min_one ? "true" : "false",
3311 : swapped ? " swapped" : "", reason,
3312 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
3313 : GDKusec() - t0);
3314 :
3315 17565 : BBPreclaim(b);
3316 : return GDK_SUCCEED;
3317 :
3318 6 : bailout:
3319 6 : bat_iterator_end(&li);
3320 6 : bat_iterator_end(&ri);
3321 6 : if (locked)
3322 6 : MT_rwlock_rdunlock(&r->thashlock);
3323 6 : if (hash_cand && hsh) {
3324 0 : HEAPfree(&hsh->heaplink, true);
3325 0 : HEAPfree(&hsh->heapbckt, true);
3326 0 : GDKfree(hsh);
3327 : }
3328 6 : BBPreclaim(r1);
3329 6 : BBPreclaim(r2);
3330 6 : BBPreclaim(b);
3331 : return GDK_FAIL;
3332 : }
3333 :
3334 : /* Count the number of unique values for the first half and the complete
3335 : * set (the sample s of b) and return the two values in *cnt1 and
3336 : * *cnt2. In case of error, both values are 0. */
3337 : static gdk_return
3338 1061063 : count_unique(BAT *b, BAT *s, BUN *cnt1, BUN *cnt2)
3339 : {
3340 1061063 : struct canditer ci;
3341 1061063 : BUN half;
3342 1061063 : BUN cnt = 0;
3343 1061063 : const void *v;
3344 1061063 : const char *bvals;
3345 1061063 : const char *bvars;
3346 1061063 : oid bval;
3347 1061063 : oid i, o;
3348 1061063 : const char *nme;
3349 1061063 : BUN hb;
3350 1061063 : BATiter bi;
3351 1061063 : int (*cmp)(const void *, const void *);
3352 1061063 : const char *algomsg = "";
3353 1061063 : lng t0 = 0;
3354 :
3355 1061063 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
3356 1061063 : canditer_init(&ci, b, s);
3357 1061461 : half = ci.ncand / 2;
3358 :
3359 1061461 : MT_lock_set(&b->theaplock);
3360 1061584 : if (b->tkey || ci.ncand <= 1 || BATtdense(b)) {
3361 : /* trivial: already unique */
3362 1424 : MT_lock_unset(&b->theaplock);
3363 1425 : *cnt1 = half;
3364 1425 : *cnt2 = ci.ncand;
3365 1425 : return GDK_SUCCEED;
3366 : }
3367 1060160 : MT_lock_unset(&b->theaplock);
3368 :
3369 1060265 : (void) BATordered(b);
3370 1060163 : (void) BATordered_rev(b);
3371 1060258 : bi = bat_iterator(b);
3372 1059935 : if ((bi.sorted && bi.revsorted) ||
3373 995211 : (bi.type == TYPE_void && is_oid_nil(bi.tseq))) {
3374 : /* trivial: all values are the same */
3375 64724 : *cnt1 = *cnt2 = 1;
3376 64724 : bat_iterator_end(&bi);
3377 64724 : return GDK_SUCCEED;
3378 : }
3379 :
3380 995211 : assert(bi.type != TYPE_void);
3381 :
3382 995211 : bvals = bi.base;
3383 995211 : if (bi.vh && bi.type)
3384 71058 : bvars = bi.vh->base;
3385 : else
3386 : bvars = NULL;
3387 995211 : cmp = ATOMcompare(bi.type);
3388 :
3389 995211 : *cnt1 = *cnt2 = 0;
3390 :
3391 995211 : BAT *pb = BATdescriptor(bi.h->parentid);
3392 995504 : MT_rwlock_rdlock(&pb->thashlock);
3393 995514 : if (bi.sorted || bi.revsorted) {
3394 : const void *prev = NULL;
3395 9473151 : algomsg = "sorted";
3396 9473151 : for (i = 0; i < ci.ncand; i++) {
3397 9388542 : if (i == half)
3398 84540 : *cnt1 = cnt;
3399 9388542 : o = canditer_next(&ci);
3400 9388496 : v = VALUE(b, o - b->hseqbase);
3401 9388496 : if (prev == NULL || (*cmp)(v, prev) != 0) {
3402 3921377 : cnt++;
3403 : }
3404 9388446 : prev = v;
3405 : }
3406 84609 : *cnt2 = cnt;
3407 910809 : } else if (ATOMbasetype(bi.type) == TYPE_bte) {
3408 42655 : unsigned char val;
3409 42655 : uint32_t seen[256 / 32];
3410 :
3411 42655 : algomsg = "byte-sized atoms";
3412 42655 : assert(bvars == NULL);
3413 42655 : memset(seen, 0, sizeof(seen));
3414 7459212 : for (i = 0; i < ci.ncand; i++) {
3415 7416503 : if (i == ci.ncand/ 2) {
3416 : cnt = 0;
3417 382766 : for (int j = 0; j < 256 / 32; j++)
3418 340048 : cnt += candmask_pop(seen[j]);
3419 42718 : *cnt1 = cnt;
3420 : }
3421 7416503 : o = canditer_next(&ci);
3422 7416557 : val = ((const unsigned char *) bvals)[o - b->hseqbase];
3423 7416557 : if (!(seen[val >> 5] & (1U << (val & 0x1F)))) {
3424 105151 : seen[val >> 5] |= 1U << (val & 0x1F);
3425 : }
3426 : }
3427 : cnt = 0;
3428 383125 : for (int j = 0; j < 256 / 32; j++)
3429 340416 : cnt += candmask_pop(seen[j]);
3430 42709 : *cnt2 = cnt;
3431 868154 : } else if (ATOMbasetype(bi.type) == TYPE_sht) {
3432 45356 : unsigned short val;
3433 45356 : uint32_t *seen = NULL;
3434 :
3435 45356 : algomsg = "short-sized atoms";
3436 45356 : assert(bvars == NULL);
3437 45356 : seen = GDKzalloc((65536 / 32) * sizeof(seen[0]));
3438 45357 : if (seen == NULL) {
3439 0 : MT_rwlock_rdunlock(&pb->thashlock);
3440 0 : BBPreclaim(pb);
3441 0 : bat_iterator_end(&bi);
3442 0 : return GDK_FAIL;
3443 : }
3444 7120747 : for (i = 0; i < ci.ncand; i++) {
3445 7075392 : if (i == half) {
3446 : cnt = 0;
3447 92670252 : for (int j = 0; j < 65536 / 32; j++)
3448 92624896 : cnt += candmask_pop(seen[j]);
3449 45356 : *cnt1 = cnt;
3450 : }
3451 7075392 : o = canditer_next(&ci);
3452 7075390 : val = ((const unsigned short *) bvals)[o - b->hseqbase];
3453 7075390 : if (!(seen[val >> 5] & (1U << (val & 0x1F)))) {
3454 137846 : seen[val >> 5] |= 1U << (val & 0x1F);
3455 : }
3456 : }
3457 : cnt = 0;
3458 92684587 : for (int j = 0; j < 65536 / 32; j++)
3459 92639232 : cnt += candmask_pop(seen[j]);
3460 45355 : *cnt2 = cnt;
3461 45355 : GDKfree(seen);
3462 45355 : seen = NULL;
3463 : } else {
3464 822798 : BUN prb;
3465 822798 : BUN mask;
3466 822798 : Hash hs = {
3467 : .heapbckt.parentid = b->batCacheid,
3468 822798 : .heaplink.parentid = b->batCacheid,
3469 : };
3470 :
3471 822798 : GDKclrerr(); /* not interested in BAThash errors */
3472 822801 : algomsg = "new partial hash";
3473 822801 : nme = BBP_physical(b->batCacheid);
3474 822801 : mask = HASHmask(ci.ncand);
3475 604380 : if (mask < ((BUN) 1 << 16))
3476 822801 : mask = (BUN) 1 << 16;
3477 822801 : if ((hs.heaplink.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
3478 822803 : (hs.heapbckt.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
3479 822804 : snprintf(hs.heaplink.filename, sizeof(hs.heaplink.filename), "%s.thshjnl%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs.heaplink.filename) ||
3480 1645586 : snprintf(hs.heapbckt.filename, sizeof(hs.heapbckt.filename), "%s.thshjnb%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs.heapbckt.filename) ||
3481 822801 : HASHnew(&hs, bi.type, ci.ncand, mask, BUN_NONE, false) != GDK_SUCCEED) {
3482 14 : MT_rwlock_rdunlock(&pb->thashlock);
3483 0 : BBPreclaim(pb);
3484 0 : GDKerror("cannot allocate hash table\n");
3485 0 : HEAPfree(&hs.heaplink, true);
3486 0 : HEAPfree(&hs.heapbckt, true);
3487 0 : bat_iterator_end(&bi);
3488 0 : return GDK_FAIL;
3489 : }
3490 414274367 : for (i = 0; i < ci.ncand; i++) {
3491 413451570 : if (i == half)
3492 822799 : *cnt1 = cnt;
3493 413451570 : o = canditer_next(&ci);
3494 413445383 : v = VALUE(b, o - b->hseqbase);
3495 413445383 : prb = HASHprobe(&hs, v);
3496 413459775 : for (hb = HASHget(&hs, prb);
3497 413482776 : hb != BUN_NONE;
3498 23001 : hb = HASHgetlink(&hs, hb)) {
3499 243868991 : BUN p = canditer_idx(&ci, hb) - b->hseqbase;
3500 243868991 : if (cmp(v, BUNtail(bi, p)) == 0)
3501 : break;
3502 : }
3503 413437680 : if (hb == BUN_NONE) {
3504 169598655 : cnt++;
3505 : /* enter into hash table */
3506 169598655 : HASHputlink(&hs, i, HASHget(&hs, prb));
3507 169614175 : HASHput(&hs, prb, i);
3508 : }
3509 : }
3510 822797 : *cnt2 = cnt;
3511 822797 : HEAPfree(&hs.heaplink, true);
3512 822773 : HEAPfree(&hs.heapbckt, true);
3513 : }
3514 995460 : MT_rwlock_rdunlock(&pb->thashlock);
3515 995301 : BBPreclaim(pb);
3516 995464 : bat_iterator_end(&bi);
3517 :
3518 995418 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
3519 : " -> " BUNFMT " " BUNFMT " (%s -- " LLFMT "usec)\n",
3520 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
3521 : *cnt1, *cnt2, algomsg, GDKusec() - t0);
3522 :
3523 : return GDK_SUCCEED;
3524 : }
3525 :
3526 : static double
3527 2087395 : guess_uniques(BAT *b, struct canditer *ci)
3528 : {
3529 2087395 : BUN cnt1, cnt2;
3530 2087395 : BAT *s1;
3531 :
3532 2087395 : MT_lock_set(&b->theaplock);
3533 2087951 : bool key = b->tkey;
3534 2087951 : double unique_est = b->tunique_est;
3535 2087951 : BUN batcount = BATcount(b);
3536 2087951 : MT_lock_unset(&b->theaplock);
3537 2088178 : if (key)
3538 1026379 : return (double) ci->ncand;
3539 :
3540 1061799 : if (ci->s == NULL ||
3541 1 : (ci->tpe == cand_dense && ci->ncand == batcount)) {
3542 1061798 : if (unique_est != 0) {
3543 194 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT " use cached value\n",
3544 : ALGOBATPAR(b));
3545 194 : return unique_est;
3546 : }
3547 1061604 : s1 = BATsample(b, 1000);
3548 : } else {
3549 1 : BAT *s2 = BATsample(ci->s, 1000);
3550 1 : if (s2 == NULL)
3551 : return -1;
3552 1 : s1 = BATproject(s2, ci->s);
3553 1 : BBPreclaim(s2);
3554 : }
3555 1061237 : if (s1 == NULL)
3556 : return -1;
3557 1061237 : BUN n2 = BATcount(s1);
3558 1061237 : BUN n1 = n2 / 2;
3559 1061237 : if (count_unique(b, s1, &cnt1, &cnt2) != GDK_SUCCEED) {
3560 0 : BBPreclaim(s1);
3561 0 : return -1;
3562 : }
3563 1061449 : BBPreclaim(s1);
3564 :
3565 1061576 : double A = (double) (cnt2 - cnt1) / (n2 - n1);
3566 1061576 : double B = cnt1 - n1 * A;
3567 :
3568 1061576 : B += A * ci->ncand;
3569 1061576 : MT_lock_set(&b->theaplock);
3570 1061493 : if (ci->s == NULL ||
3571 1 : (ci->tpe == cand_dense && ci->ncand == BATcount(b) && ci->ncand == batcount)) {
3572 1061492 : if (b->tunique_est == 0)
3573 1059550 : b->tunique_est = B;
3574 : }
3575 1061493 : MT_lock_unset(&b->theaplock);
3576 1061513 : return B;
3577 : }
3578 :
3579 : BUN
3580 1295322 : BATguess_uniques(BAT *b, struct canditer *ci)
3581 : {
3582 1295322 : struct canditer lci;
3583 1295322 : if (ci == NULL) {
3584 1295626 : canditer_init(&lci, b, NULL);
3585 1295626 : ci = &lci;
3586 : }
3587 1295894 : double uniques = guess_uniques(b, ci);
3588 1296245 : return uniques < 0 ? 0 : (BUN) uniques;
3589 : }
3590 :
3591 : /* estimate the cost of doing a hashjoin with a hash on r; return value
3592 : * is the estimated cost, the last three arguments receive some extra
3593 : * information */
3594 : double
3595 1484634 : joincost(BAT *r, BUN lcount, struct canditer *rci,
3596 : bool *hash, bool *phash, bool *cand)
3597 : {
3598 1484634 : bool rhash;
3599 1484634 : bool prhash = false;
3600 1484634 : bool rcand = false;
3601 1484634 : double rcost = 1;
3602 1484634 : bat parent;
3603 1484634 : BAT *b;
3604 1484634 : BUN nheads;
3605 1484634 : BUN cnt;
3606 :
3607 1484634 : (void) BATcheckhash(r);
3608 1485241 : MT_rwlock_rdlock(&r->thashlock);
3609 1485486 : rhash = r->thash != NULL;
3610 1485486 : nheads = r->thash ? r->thash->nheads : 0;
3611 1485486 : cnt = BATcount(r);
3612 1485486 : MT_rwlock_rdunlock(&r->thashlock);
3613 :
3614 1484621 : if ((rci->tpe == cand_materialized || rci->tpe == cand_except) &&
3615 324861 : rci->nvals > 0) {
3616 : /* if we need to do binary search on candidate list,
3617 : * take that into account; note checking the other
3618 : * candidate types is essentially free */
3619 324862 : rcost += log2((double) rci->nvals);
3620 : }
3621 1484621 : rcost *= lcount;
3622 1484621 : if (BATtdense(r)) {
3623 : /* no need for a hash, and lookup is free */
3624 : rhash = false; /* don't use it, even if it's there */
3625 : } else {
3626 1484620 : if (rhash) {
3627 : /* average chain length */
3628 10573 : rcost *= (double) cnt / nheads;
3629 1474047 : } else if ((parent = VIEWtparent(r)) != 0 &&
3630 1340215 : (b = BATdescriptor(parent)) != NULL) {
3631 1340524 : if (BATcheckhash(b)) {
3632 65582 : MT_rwlock_rdlock(&b->thashlock);
3633 65578 : rhash = prhash = b->thash != NULL;
3634 65578 : if (rhash) {
3635 : /* average chain length */
3636 65578 : rcost *= (double) BATcount(b) / b->thash->nheads;
3637 : }
3638 65578 : MT_rwlock_rdunlock(&b->thashlock);
3639 : }
3640 1340556 : BBPunfix(b->batCacheid);
3641 : }
3642 1484895 : if (!rhash) {
3643 1408746 : MT_lock_set(&r->theaplock);
3644 1409327 : double unique_est = r->tunique_est;
3645 1409327 : MT_lock_unset(&r->theaplock);
3646 1409543 : if (unique_est == 0) {
3647 791896 : unique_est = guess_uniques(r, &(struct canditer){.tpe=cand_dense, .ncand=BATcount(r)});
3648 791772 : if (unique_est <= 0)
3649 0 : return -1;
3650 : }
3651 : /* we have an estimate of the number of unique
3652 : * values, assume some collisions */
3653 1409419 : rcost *= 1.1 * ((double) cnt / unique_est);
3654 : /* only count the cost of creating the hash for
3655 : * non-persistent bats */
3656 1409419 : MT_lock_set(&r->theaplock);
3657 1409307 : if (r->batRole != PERSISTENT /* || r->theap->dirty */ || GDKinmemory(r->theap->farmid))
3658 1381242 : rcost += cnt * 2.0;
3659 1409307 : MT_lock_unset(&r->theaplock);
3660 : }
3661 : }
3662 1485685 : if (cand) {
3663 38295 : if (rci->ncand != BATcount(r) && rci->tpe != cand_mask) {
3664 : /* instead of using the hash on r (cost in
3665 : * rcost), we can build a new hash on r taking
3666 : * the candidate list into account; don't do
3667 : * this for masked candidate since the searching
3668 : * of the candidate list (canditer_idx) will
3669 : * kill us */
3670 2284 : double rccost;
3671 2284 : if (rhash && !prhash) {
3672 884 : rccost = (double) cnt / nheads;
3673 : } else {
3674 1400 : MT_lock_set(&r->theaplock);
3675 1400 : double unique_est = r->tunique_est;
3676 1400 : MT_lock_unset(&r->theaplock);
3677 1400 : if (unique_est == 0) {
3678 84 : unique_est = guess_uniques(r, rci);
3679 84 : if (unique_est <= 0)
3680 : return -1;
3681 : }
3682 : /* we have an estimate of the number of unique
3683 : * values, assume some chains */
3684 1400 : rccost = 1.1 * ((double) cnt / unique_est);
3685 : }
3686 2284 : rccost *= lcount;
3687 2284 : rccost += rci->ncand * 2.0; /* cost of building the hash */
3688 2284 : if (rccost < rcost) {
3689 38295 : rcost = rccost;
3690 38295 : rcand = true;
3691 : }
3692 : }
3693 38295 : *cand = rcand;
3694 : }
3695 1485685 : *hash = rhash;
3696 1485685 : *phash = prhash;
3697 1485685 : return rcost;
3698 : }
3699 :
3700 : #define MASK_EQ 1
3701 : #define MASK_LT 2
3702 : #define MASK_GT 4
3703 : #define MASK_LE (MASK_EQ | MASK_LT)
3704 : #define MASK_GE (MASK_EQ | MASK_GT)
3705 : #define MASK_NE (MASK_LT | MASK_GT)
3706 :
3707 : static gdk_return
3708 50841 : thetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, int opcode,
3709 : BUN estimate, bool nil_matches, const char *reason, lng t0)
3710 : {
3711 50841 : struct canditer lci, rci;
3712 50841 : const char *lvals, *rvals;
3713 50841 : const char *lvars, *rvars;
3714 50841 : const void *nil = ATOMnilptr(l->ttype);
3715 50841 : int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
3716 50841 : const void *vl, *vr;
3717 50841 : oid lastr = 0; /* last value inserted into r2 */
3718 50841 : BUN nr;
3719 50841 : oid lo, ro;
3720 50841 : int c;
3721 50841 : bool lskipped = false; /* whether we skipped values in l */
3722 50841 : lng loff = 0, roff = 0;
3723 50841 : oid lval = oid_nil, rval = oid_nil;
3724 :
3725 50841 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
3726 :
3727 152544 : assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
3728 50848 : assert((opcode & (MASK_EQ | MASK_LT | MASK_GT)) != 0);
3729 :
3730 50848 : BATiter li = bat_iterator(l);
3731 50951 : BATiter ri = bat_iterator(r);
3732 :
3733 50957 : canditer_init(&lci, l, sl);
3734 50934 : canditer_init(&rci, r, sr);
3735 :
3736 50817 : lvals = BATtvoid(l) ? NULL : (const char *) li.base;
3737 50817 : rvals = BATtvoid(r) ? NULL : (const char *) ri.base;
3738 50817 : if (li.vh && li.type) {
3739 16 : assert(ri.vh && ri.type);
3740 16 : lvars = li.vh->base;
3741 16 : rvars = ri.vh->base;
3742 : } else {
3743 50801 : assert(ri.vh == NULL);
3744 : lvars = rvars = NULL;
3745 : }
3746 :
3747 50817 : if (BATtvoid(l)) {
3748 0 : if (!BATtdensebi(&li)) {
3749 0 : if (!nil_matches) {
3750 : /* trivial: nils don't match anything */
3751 0 : bat_iterator_end(&li);
3752 0 : bat_iterator_end(&ri);
3753 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
3754 : 0, false, false, __func__, t0);
3755 : }
3756 : } else {
3757 0 : loff = (lng) l->tseqbase - (lng) l->hseqbase;
3758 : }
3759 : }
3760 50817 : if (BATtvoid(r)) {
3761 1 : if (!BATtdensebi(&ri)) {
3762 0 : if (!nil_matches) {
3763 : /* trivial: nils don't match anything */
3764 0 : bat_iterator_end(&li);
3765 0 : bat_iterator_end(&ri);
3766 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
3767 : 0, false, false, __func__, t0);
3768 : }
3769 : } else {
3770 1 : roff = (lng) r->tseqbase - (lng) r->hseqbase;
3771 : }
3772 : }
3773 :
3774 50817 : BUN maxsize = joininitresults(r1p, r2p, NULL, lci.ncand, rci.ncand, false, false,
3775 : false, false, false, false, estimate);
3776 50160 : if (maxsize == BUN_NONE) {
3777 0 : bat_iterator_end(&li);
3778 0 : bat_iterator_end(&ri);
3779 0 : return GDK_FAIL;
3780 : }
3781 50160 : BAT *r1 = *r1p;
3782 50160 : BAT *r2 = r2p ? *r2p : NULL;
3783 :
3784 50160 : r1->tkey = true;
3785 50160 : r1->tsorted = true;
3786 50160 : r1->trevsorted = true;
3787 50160 : if (r2) {
3788 8254 : r2->tkey = true;
3789 8254 : r2->tsorted = true;
3790 8254 : r2->trevsorted = true;
3791 : }
3792 :
3793 : /* nested loop implementation for theta join */
3794 : vl = &lval;
3795 : vr = &rval;
3796 349183 : for (BUN lidx = 0; lidx < lci.ncand; lidx++) {
3797 298575 : lo = canditer_next(&lci);
3798 288669 : if (lvals)
3799 288669 : vl = VALUE(l, lo - l->hseqbase);
3800 0 : else if (BATtdensebi(&li))
3801 0 : lval = (oid) ((lng) lo + loff);
3802 288669 : nr = 0;
3803 288669 : if (nil_matches || cmp(vl, nil) != 0) {
3804 281734 : canditer_reset(&rci);
3805 3589492 : TIMEOUT_LOOP(rci.ncand, qry_ctx) {
3806 3031987 : ro = canditer_next(&rci);
3807 2970792 : if (rvals)
3808 2970788 : vr = VALUE(r, ro - r->hseqbase);
3809 4 : else if (BATtdensebi(&ri))
3810 4 : rval = (oid) ((lng) ro + roff);
3811 2970792 : if (!nil_matches && cmp(vr, nil) == 0)
3812 59355 : continue;
3813 2911584 : c = cmp(vl, vr);
3814 2944505 : if (!((opcode & MASK_LT && c < 0) ||
3815 2741690 : (opcode & MASK_GT && c > 0) ||
3816 1488280 : (opcode & MASK_EQ && c == 0)))
3817 1488259 : continue;
3818 1456246 : if (maybeextend(r1, r2, NULL, 1, lci.next, lci.ncand, maxsize) != GDK_SUCCEED)
3819 0 : goto bailout;
3820 1479807 : if (BATcount(r1) > 0) {
3821 1458995 : if (r2 && lastr + 1 != ro)
3822 53642 : r2->tseqbase = oid_nil;
3823 1458995 : if (nr == 0) {
3824 151068 : r1->trevsorted = false;
3825 151068 : if (r2 == NULL) {
3826 : /* nothing */
3827 43703 : } else if (lastr > ro) {
3828 40315 : r2->tsorted = false;
3829 40315 : r2->tkey = false;
3830 3388 : } else if (lastr < ro) {
3831 0 : r2->trevsorted = false;
3832 : } else {
3833 3388 : r2->tkey = false;
3834 : }
3835 : }
3836 : }
3837 1479807 : APPEND(r1, lo);
3838 1479807 : if (r2) {
3839 1202204 : APPEND(r2, ro);
3840 : }
3841 1479807 : lastr = ro;
3842 1479807 : nr++;
3843 : }
3844 280151 : TIMEOUT_CHECK(qry_ctx,
3845 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
3846 : }
3847 299023 : if (nr > 1) {
3848 144743 : r1->tkey = false;
3849 144743 : r1->tseqbase = oid_nil;
3850 144743 : if (r2) {
3851 46632 : r2->trevsorted = false;
3852 : }
3853 154280 : } else if (nr == 0) {
3854 121190 : lskipped = BATcount(r1) > 0;
3855 33090 : } else if (lskipped) {
3856 20539 : r1->tseqbase = oid_nil;
3857 : }
3858 : }
3859 : /* also set other bits of heap to correct value to indicate size */
3860 50608 : BATsetcount(r1, BATcount(r1));
3861 50452 : if (r2) {
3862 8336 : BATsetcount(r2, BATcount(r2));
3863 8346 : assert(BATcount(r1) == BATcount(r2));
3864 : }
3865 50462 : if (BATcount(r1) > 0) {
3866 25389 : if (BATtdense(r1))
3867 1237 : r1->tseqbase = ((oid *) r1->theap->base)[0];
3868 25389 : if (r2 && BATtdense(r2))
3869 1012 : r2->tseqbase = ((oid *) r2->theap->base)[0];
3870 : } else {
3871 25073 : r1->tseqbase = 0;
3872 25073 : if (r2) {
3873 1666 : r2->tseqbase = 0;
3874 : }
3875 : }
3876 50462 : bat_iterator_end(&li);
3877 50703 : bat_iterator_end(&ri);
3878 49623 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
3879 : ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
3880 : "opcode=%s%s%s; %s -> " ALGOBATFMT "," ALGOOPTBATFMT
3881 : " (" LLFMT "usec)\n",
3882 : ALGOBATPAR(l), ALGOBATPAR(r),
3883 : ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
3884 : opcode & MASK_LT ? "<" : "",
3885 : opcode & MASK_GT ? ">" : "",
3886 : opcode & MASK_EQ ? "=" : "",
3887 : reason,
3888 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
3889 : GDKusec() - t0);
3890 : return GDK_SUCCEED;
3891 :
3892 0 : bailout:
3893 0 : bat_iterator_end(&li);
3894 0 : bat_iterator_end(&ri);
3895 0 : BBPreclaim(r1);
3896 0 : BBPreclaim(r2);
3897 : return GDK_FAIL;
3898 : }
3899 :
3900 : /* small ordered right, dense left, oid's only, do fetches */
3901 : static gdk_return
3902 0 : fetchjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
3903 : struct canditer *restrict lci, struct canditer *restrict rci,
3904 : const char *reason, lng t0)
3905 : {
3906 0 : oid lo = lci->seq - l->hseqbase + l->tseqbase, hi = lo + lci->ncand;
3907 0 : BUN b, e, p;
3908 0 : BAT *r1, *r2 = NULL;
3909 :
3910 0 : MT_thread_setalgorithm(__func__);
3911 0 : if (r->tsorted) {
3912 0 : b = SORTfndfirst(r, &lo);
3913 0 : e = SORTfndfirst(r, &hi);
3914 : } else {
3915 0 : assert(r->trevsorted);
3916 0 : b = SORTfndlast(r, &hi);
3917 0 : e = SORTfndlast(r, &lo);
3918 : }
3919 0 : if (b < rci->seq - r->hseqbase)
3920 : b = rci->seq - r->hseqbase;
3921 0 : if (e > rci->seq + rci->ncand - r->hseqbase)
3922 : e = rci->seq + rci->ncand - r->hseqbase;
3923 0 : if (e == b) {
3924 0 : return nomatch(r1p, r2p, NULL, l, r, lci,
3925 : 0, false, false, __func__, t0);
3926 : }
3927 0 : r1 = COLnew(0, TYPE_oid, e - b, TRANSIENT);
3928 0 : if (r1 == NULL)
3929 : return GDK_FAIL;
3930 0 : if (r2p) {
3931 0 : if ((r2 = BATdense(0, r->hseqbase + b, e - b)) == NULL) {
3932 0 : BBPreclaim(r1);
3933 0 : return GDK_FAIL;
3934 : }
3935 0 : *r2p = r2;
3936 : }
3937 0 : *r1p = r1;
3938 0 : oid *op = (oid *) Tloc(r1, 0);
3939 0 : BATiter ri = bat_iterator(r);
3940 0 : const oid *rp = (const oid *) ri.base;
3941 0 : for (p = b; p < e; p++) {
3942 0 : *op++ = rp[p] + l->hseqbase - l->tseqbase;
3943 : }
3944 0 : BATsetcount(r1, e - b);
3945 0 : r1->tkey = ri.key;
3946 0 : r1->tsorted = ri.sorted || e - b <= 1;
3947 0 : r1->trevsorted = ri.revsorted || e - b <= 1;
3948 0 : r1->tseqbase = e == b ? 0 : e - b == 1 ? *(const oid *)Tloc(r1, 0) : oid_nil;
3949 0 : bat_iterator_end(&ri);
3950 0 : TRC_DEBUG(ALGO, "%s(l=" ALGOBATFMT ","
3951 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
3952 : "sr=" ALGOOPTBATFMT ") %s "
3953 : "-> (" ALGOBATFMT "," ALGOOPTBATFMT ") " LLFMT "us\n",
3954 : __func__,
3955 : ALGOBATPAR(l), ALGOBATPAR(r),
3956 : ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
3957 : reason,
3958 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
3959 : GDKusec() - t0);
3960 :
3961 : return GDK_SUCCEED;
3962 : }
3963 :
3964 : static BAT *
3965 5192 : bitmaskjoin(BAT *l, BAT *r,
3966 : struct canditer *restrict lci, struct canditer *restrict rci,
3967 : bool only_misses,
3968 : const char *reason, lng t0)
3969 : {
3970 5192 : BAT *r1;
3971 5192 : size_t nmsk = (lci->ncand + 31) / 32;
3972 5192 : uint32_t *mask = GDKzalloc(nmsk * sizeof(uint32_t));
3973 5200 : BUN cnt = 0;
3974 :
3975 5200 : MT_thread_setalgorithm(__func__);
3976 5195 : if (mask == NULL)
3977 : return NULL;
3978 :
3979 21810675 : for (BUN n = 0; n < rci->ncand; n++) {
3980 21805475 : oid o = canditer_next(rci) - r->hseqbase;
3981 21805480 : o = BUNtoid(r, o);
3982 21805480 : if (is_oid_nil(o))
3983 0 : continue;
3984 21805480 : o += l->hseqbase;
3985 21805480 : if (o < lci->seq + l->tseqbase)
3986 2 : continue;
3987 21805478 : o -= lci->seq + l->tseqbase;
3988 21805478 : if (o >= lci->ncand)
3989 0 : continue;
3990 21805478 : if ((mask[o >> 5] & (1U << (o & 0x1F))) == 0) {
3991 16546634 : cnt++;
3992 16546634 : mask[o >> 5] |= 1U << (o & 0x1F);
3993 : }
3994 : }
3995 5200 : if (only_misses)
3996 3690 : cnt = lci->ncand - cnt;
3997 5200 : if (cnt == 0 || cnt == lci->ncand) {
3998 1519 : GDKfree(mask);
3999 1519 : if (cnt == 0)
4000 367 : return BATdense(0, 0, 0);
4001 1152 : return BATdense(0, lci->seq, lci->ncand);
4002 : }
4003 3681 : r1 = COLnew(0, TYPE_oid, cnt, TRANSIENT);
4004 3681 : if (r1 != NULL) {
4005 3681 : oid *r1p = Tloc(r1, 0);
4006 :
4007 3681 : r1->tkey = true;
4008 3681 : r1->tnil = false;
4009 3681 : r1->tnonil = true;
4010 3681 : r1->tsorted = true;
4011 3681 : r1->trevsorted = cnt <= 1;
4012 3681 : if (only_misses) {
4013 : /* set the bits for unused values at the
4014 : * end so that we don't need special
4015 : * code in the loop */
4016 3323 : if (lci->ncand & 0x1F)
4017 3259 : mask[nmsk - 1] |= ~0U << (lci->ncand & 0x1F);
4018 1942569 : for (size_t i = 0; i < nmsk; i++)
4019 1939246 : if (mask[i] != ~0U)
4020 61249683 : for (uint32_t j = 0; j < 32; j++)
4021 59393632 : if ((mask[i] & (1U << j)) == 0)
4022 52839879 : *r1p++ = i * 32 + j + lci->seq;
4023 : } else {
4024 308440 : for (size_t i = 0; i < nmsk; i++)
4025 308082 : if (mask[i] != 0U)
4026 7786416 : for (uint32_t j = 0; j < 32; j++)
4027 7550464 : if ((mask[i] & (1U << j)) != 0)
4028 6799084 : *r1p++ = i * 32 + j + lci->seq;
4029 : }
4030 3681 : BATsetcount(r1, cnt);
4031 3681 : assert((BUN) (r1p - (oid*) Tloc(r1, 0)) == BATcount(r1));
4032 :
4033 3681 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
4034 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
4035 : "sr=" ALGOOPTBATFMT ",only_misses=%s; %s "
4036 : "-> " ALGOBATFMT " (" LLFMT "usec)\n",
4037 : ALGOBATPAR(l), ALGOBATPAR(r),
4038 : ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
4039 : only_misses ? "true" : "false",
4040 : reason,
4041 : ALGOBATPAR(r1),
4042 : GDKusec() - t0);
4043 : }
4044 3681 : GDKfree(mask);
4045 3681 : return r1;
4046 : }
4047 :
4048 : /* Make the implementation choices for various left joins.
4049 : * If r3p is set, this is a "mark join" and *r3p will be a third return value containing a bat with type msk with a bit set for each
4050 : * nil_matches: nil is an ordinary value that can match;
4051 : * nil_on_miss: outer join: fill in a nil value in case of no match;
4052 : * semi: semi join: return one of potentially more than one matches;
4053 : * only_misses: difference: list rows without match on the right;
4054 : * not_in: for implementing NOT IN: if nil on right then there are no matches;
4055 : * max_one: error if there is more than one match;
4056 : * min_one: error if there are no matches. */
4057 : static gdk_return
4058 193192 : leftjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r, BAT *sl, BAT *sr,
4059 : bool nil_matches, bool nil_on_miss, bool semi, bool only_misses,
4060 : bool not_in, bool max_one, bool min_one, BUN estimate,
4061 : const char *func, lng t0)
4062 : {
4063 193192 : struct canditer lci, rci;
4064 193192 : bool rhash, prhash, rcand;
4065 193192 : bat parent;
4066 193192 : double rcost = 0;
4067 193192 : gdk_return rc;
4068 193192 : BAT *lp = NULL;
4069 193192 : BAT *rp = NULL;
4070 :
4071 193192 : MT_thread_setalgorithm(__func__);
4072 : /* only_misses implies left output only */
4073 193122 : assert(!only_misses || r2p == NULL);
4074 : /* if nil_on_miss is set, we really need a right output */
4075 193122 : assert(!nil_on_miss || r2p != NULL || r3p != NULL);
4076 : /* if not_in is set, then so is only_misses */
4077 193122 : assert(!not_in || only_misses);
4078 : /* if r3p is set, then so is nil_on_miss */
4079 193122 : assert(r3p == NULL || nil_on_miss);
4080 193122 : *r1p = NULL;
4081 193122 : if (r2p)
4082 1054 : *r2p = NULL;
4083 193122 : if (r3p)
4084 19406 : *r3p = NULL;
4085 :
4086 193122 : canditer_init(&lci, l, sl);
4087 193838 : canditer_init(&rci, r, sr);
4088 :
4089 193840 : if ((parent = VIEWtparent(l)) != 0) {
4090 4166 : lp = BATdescriptor(parent);
4091 4168 : if (lp == NULL)
4092 : return GDK_FAIL;
4093 4168 : if (l->hseqbase == lp->hseqbase &&
4094 4737 : BATcount(l) == BATcount(lp) &&
4095 3274 : ATOMtype(l->ttype) == ATOMtype(lp->ttype)) {
4096 : l = lp;
4097 : } else {
4098 2531 : BBPunfix(lp->batCacheid);
4099 2531 : lp = NULL;
4100 : }
4101 : }
4102 193841 : if ((parent = VIEWtparent(r)) != 0) {
4103 4366 : rp = BATdescriptor(parent);
4104 4365 : if (rp == NULL) {
4105 0 : BBPreclaim(lp);
4106 0 : return GDK_FAIL;
4107 : }
4108 4365 : if (r->hseqbase == rp->hseqbase &&
4109 7204 : BATcount(r) == BATcount(rp) &&
4110 5678 : ATOMtype(r->ttype) == ATOMtype(rp->ttype)) {
4111 : r = rp;
4112 : } else {
4113 1528 : BBPunfix(rp->batCacheid);
4114 1528 : rp = NULL;
4115 : }
4116 : }
4117 :
4118 193840 : if (l->ttype == TYPE_msk || mask_cand(l)) {
4119 5 : l = BATunmask(l);
4120 5 : BBPreclaim(lp);
4121 5 : if (l == NULL) {
4122 0 : BBPreclaim(rp);
4123 0 : return GDK_FAIL;
4124 : }
4125 : lp = l;
4126 : }
4127 193840 : if (r->ttype == TYPE_msk || mask_cand(r)) {
4128 66 : r = BATunmask(r);
4129 66 : BBPreclaim(rp);
4130 66 : if (r == NULL) {
4131 0 : BBPreclaim(lp);
4132 0 : return GDK_FAIL;
4133 : }
4134 : rp = r;
4135 : }
4136 :
4137 193840 : if (joinparamcheck(l, r, NULL, sl, sr, func) != GDK_SUCCEED) {
4138 0 : rc = GDK_FAIL;
4139 0 : goto doreturn;
4140 : }
4141 :
4142 193534 : if (lci.ncand == 0 || rci.ncand == 0) {
4143 154323 : TRC_DEBUG(ALGO, "%s(l=" ALGOBATFMT ","
4144 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
4145 : "sr=" ALGOOPTBATFMT ",nil_matches=%d,"
4146 : "nil_on_miss=%d,semi=%d,only_misses=%d,"
4147 : "not_in=%d,max_one=%d,min_one=%d)\n",
4148 : func,
4149 : ALGOBATPAR(l), ALGOBATPAR(r),
4150 : ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
4151 : nil_matches, nil_on_miss, semi, only_misses,
4152 : not_in, max_one, min_one);
4153 154323 : rc = nomatch(r1p, r2p, r3p, l, r, &lci,
4154 : 0, nil_on_miss, only_misses, func, t0);
4155 154327 : goto doreturn;
4156 : }
4157 :
4158 39211 : if (!only_misses && !not_in &&
4159 4305 : (lci.ncand == 1 || (BATordered(l) && BATordered_rev(l)) ||
4160 4234 : (l->ttype == TYPE_void && is_oid_nil(l->tseqbase)))) {
4161 : /* single value to join, use select */
4162 1750 : rc = selectjoin(r1p, r2p, r3p, l, r, &lci, &rci,
4163 : nil_matches, nil_on_miss, semi, max_one, min_one,
4164 : t0, false, func);
4165 1751 : goto doreturn;
4166 37465 : } else if (BATtdense(r) && rci.tpe == cand_dense) {
4167 : /* use special implementation for dense right-hand side */
4168 25124 : rc = mergejoin_void(r1p, r2p, r3p, l, r, &lci, &rci,
4169 : nil_on_miss, only_misses, t0, false,
4170 : func);
4171 25089 : goto doreturn;
4172 12341 : } else if (BATtdense(l)
4173 5279 : && lci.tpe == cand_dense
4174 5258 : && rci.tpe == cand_dense
4175 : && !semi
4176 5259 : && !max_one
4177 : && !min_one
4178 3704 : && !nil_matches
4179 : && !only_misses
4180 3704 : && !not_in
4181 : /* && (rci.ncand * 1024) < lci.ncand */
4182 0 : && (BATordered(r) || BATordered_rev(r))) {
4183 0 : assert(ATOMtype(l->ttype) == TYPE_oid); /* tdense */
4184 0 : rc = fetchjoin(r1p, r2p, l, r, sl, sr, &lci, &rci, func, t0);
4185 0 : goto doreturn;
4186 12341 : } else if (BATtdense(l)
4187 5278 : && lci.tpe == cand_dense
4188 5257 : && r2p == NULL
4189 5215 : && (semi || only_misses)
4190 : && !nil_on_miss
4191 5214 : && !not_in
4192 : && !max_one
4193 5198 : && !min_one) {
4194 5199 : *r1p = bitmaskjoin(l, r, &lci, &rci, only_misses, func, t0);
4195 5196 : rc = *r1p == NULL ? GDK_FAIL : GDK_SUCCEED;
4196 5196 : goto doreturn;
4197 : } else {
4198 : /* looking at r->tvheap, so we need a lock */
4199 7142 : MT_lock_set(&r->theaplock);
4200 7155 : BUN hsz = r->tvheap ? r->tvheap->size : 0;
4201 7155 : MT_lock_unset(&r->theaplock);
4202 7157 : if ((BATordered(r) || BATordered_rev(r))
4203 5137 : && (BATordered(l)
4204 584 : || BATordered_rev(l)
4205 538 : || BATtdense(r)
4206 538 : || lci.ncand < 1024
4207 248 : || BATcount(r) * (r->twidth + hsz + 2 * sizeof(BUN)) > GDK_mem_maxsize / (GDKnr_threads ? GDKnr_threads : 1))) {
4208 5010 : rc = mergejoin(r1p, r2p, r3p, l, r, &lci, &rci,
4209 : nil_matches, nil_on_miss, semi, only_misses,
4210 : not_in, max_one, min_one, estimate, t0, false, func);
4211 4934 : goto doreturn;
4212 : }
4213 : }
4214 2143 : rcost = joincost(r, lci.ncand, &rci, &rhash, &prhash, &rcand);
4215 2140 : if (rcost < 0) {
4216 0 : rc = GDK_FAIL;
4217 0 : goto doreturn;
4218 : }
4219 :
4220 2140 : if (!nil_on_miss && !only_misses && !not_in && !max_one && !min_one) {
4221 : /* maybe do a hash join on the swapped operands; if we
4222 : * do, we need to sort the output, so we take that into
4223 : * account as well */
4224 958 : bool lhash, plhash, lcand, rkey = r->tkey;
4225 958 : double lcost;
4226 :
4227 958 : lcost = joincost(l, rci.ncand, &lci, &lhash, &plhash, &lcand);
4228 958 : if (lcost < 0) {
4229 0 : rc = GDK_FAIL;
4230 824 : goto doreturn;
4231 : }
4232 958 : if (semi && !rkey)
4233 840 : lcost += rci.ncand; /* cost of BATunique(r) */
4234 : /* add cost of sorting; obviously we don't know the
4235 : * size, so we guess that the size of the output is
4236 : * the same as the right input */
4237 958 : lcost += rci.ncand * log((double) rci.ncand); /* sort */
4238 958 : if (lcost < rcost) {
4239 824 : BAT *tmp = sr;
4240 824 : BAT *r1, *r2;
4241 824 : if (semi && !rkey) {
4242 818 : sr = BATunique(r, sr);
4243 818 : if (sr == NULL) {
4244 0 : rc = GDK_FAIL;
4245 0 : goto doreturn;
4246 : }
4247 818 : canditer_init(&rci, r, sr);
4248 : }
4249 824 : rc = hashjoin(&r2, &r1, NULL, r, l, &rci, &lci, nil_matches,
4250 : false, false, false, false, false, false, estimate,
4251 : t0, true, lhash, plhash, lcand, func);
4252 824 : if (semi && !rkey)
4253 818 : BBPunfix(sr->batCacheid);
4254 824 : if (rc != GDK_SUCCEED)
4255 0 : goto doreturn;
4256 824 : if (r2p == NULL) {
4257 819 : BBPunfix(r2->batCacheid);
4258 819 : r2 = NULL;
4259 : }
4260 824 : if (semi)
4261 819 : r1->tkey = true;
4262 824 : if (!VIEWtparent(r1) &&
4263 824 : r1->ttype == TYPE_oid &&
4264 824 : BBP_refs(r1->batCacheid) == 1 &&
4265 824 : (r2 == NULL ||
4266 5 : (!VIEWtparent(r2) &&
4267 5 : BBP_refs(r2->batCacheid) == 1 &&
4268 5 : r2->ttype == TYPE_oid))) {
4269 : /* in-place sort if we can */
4270 824 : if (r2) {
4271 5 : GDKqsort(r1->theap->base, r2->theap->base,
4272 5 : NULL, r1->batCount, r1->twidth,
4273 5 : r2->twidth, TYPE_oid, false,
4274 : false);
4275 5 : r2->tsorted = false;
4276 5 : r2->trevsorted = false;
4277 5 : r2->tseqbase = oid_nil;
4278 5 : *r2p = r2;
4279 : } else {
4280 819 : GDKqsort(r1->theap->base, NULL, NULL,
4281 819 : r1->batCount, r1->twidth, 0,
4282 : TYPE_oid, false, false);
4283 : }
4284 824 : r1->tsorted = true;
4285 824 : r1->trevsorted = false;
4286 824 : *r1p = r1;
4287 : } else {
4288 0 : BAT *ob;
4289 0 : rc = BATsort(&tmp, r2p ? &ob : NULL, NULL,
4290 : r1, NULL, NULL, false, false, false);
4291 0 : BBPunfix(r1->batCacheid);
4292 0 : if (rc != GDK_SUCCEED) {
4293 0 : BBPreclaim(r2);
4294 0 : goto doreturn;
4295 : }
4296 0 : *r1p = r1 = tmp;
4297 0 : if (r2p) {
4298 0 : tmp = BATproject(ob, r2);
4299 0 : BBPunfix(r2->batCacheid);
4300 0 : BBPunfix(ob->batCacheid);
4301 0 : if (tmp == NULL) {
4302 0 : BBPunfix(r1->batCacheid);
4303 0 : rc = GDK_FAIL;
4304 0 : goto doreturn;
4305 : }
4306 0 : *r2p = tmp;
4307 : }
4308 : }
4309 824 : rc = GDK_SUCCEED;
4310 824 : goto doreturn;
4311 : }
4312 : }
4313 1316 : rc = hashjoin(r1p, r2p, r3p, l, r, &lci, &rci,
4314 : nil_matches, nil_on_miss, semi, only_misses,
4315 : not_in, max_one, min_one, estimate, t0, false, rhash, prhash,
4316 : rcand, func);
4317 193422 : doreturn:
4318 193422 : BBPreclaim(lp);
4319 193394 : BBPreclaim(rp);
4320 193610 : if (rc == GDK_SUCCEED && (semi | only_misses))
4321 192779 : *r1p = virtualize(*r1p);
4322 : return rc;
4323 : }
4324 :
4325 : /* Perform an equi-join over l and r. Returns two new, aligned, bats
4326 : * with the oids of matching tuples. The result is in the same order
4327 : * as l (i.e. r1 is sorted). */
4328 : gdk_return
4329 647 : BATleftjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
4330 : {
4331 647 : return leftjoin(r1p, r2p, NULL, l, r, sl, sr, nil_matches,
4332 : false, false, false, false, false, false,
4333 : estimate, __func__,
4334 647 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
4335 : }
4336 :
4337 : /* Performs a left outer join over l and r. Returns two new, aligned,
4338 : * bats with the oids of matching tuples, or the oid in the first
4339 : * output bat and nil in the second output bat if the value in l does
4340 : * not occur in r. The result is in the same order as l (i.e. r1 is
4341 : * sorted). */
4342 : gdk_return
4343 124 : BATouterjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool match_one, BUN estimate)
4344 : {
4345 124 : return leftjoin(r1p, r2p, NULL, l, r, sl, sr, nil_matches,
4346 : true, false, false, false, match_one, match_one,
4347 : estimate, __func__,
4348 124 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
4349 : }
4350 :
4351 : /* Perform a semi-join over l and r. Returns one or two new bats
4352 : * with the oids of matching tuples. The result is in the same order
4353 : * as l (i.e. r1 is sorted). If a single bat is returned, it is a
4354 : * candidate list. */
4355 : gdk_return
4356 1085 : BATsemijoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
4357 : bool nil_matches, bool max_one, BUN estimate)
4358 : {
4359 1085 : return leftjoin(r1p, r2p, NULL, l, r, sl, sr, nil_matches,
4360 : false, true, false, false, max_one, false,
4361 : estimate, __func__,
4362 1085 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
4363 : }
4364 :
4365 : /* Perform a mark-join over l and r. Returns one or two new bats with
4366 : * the oids of matching tuples. In addition, returns a bat with "marks"
4367 : * that indicate the type of match. This is an outer join, so returns
4368 : * at least one value for each row on the left. If the second output
4369 : * pointer (r2p) is NULL, this is also a semi-join, so returns exactly
4370 : * one row for each row on the left. If there is a match, the mark
4371 : * column will be TRUE, of there is no match, the second output is NIL,
4372 : * and the mark output is FALSE if there are no NILs in the right input,
4373 : * and the left input is also not NIL, otherwise the mark output is
4374 : * NIL. */
4375 : gdk_return
4376 19518 : BATmarkjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r, BAT *sl, BAT *sr,
4377 : BUN estimate)
4378 : {
4379 19518 : return leftjoin(r1p, r2p, r3p, l, r, sl, sr, false, true, r2p == NULL,
4380 : false, false, false, false, estimate, __func__,
4381 19518 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0);
4382 : }
4383 :
4384 : /* Return a candidate list with the list of rows in l whose value also
4385 : * occurs in r. This is just the left output of a semi-join. */
4386 : BAT *
4387 10121 : BATintersect(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool max_one,
4388 : BUN estimate)
4389 : {
4390 10121 : BAT *bn;
4391 :
4392 10121 : if (leftjoin(&bn, NULL, NULL, l, r, sl, sr, nil_matches,
4393 : false, true, false, false, max_one, false,
4394 : estimate, __func__,
4395 10121 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0) == GDK_SUCCEED)
4396 10102 : return bn;
4397 : return NULL;
4398 : }
4399 :
4400 : /* Return the difference of l and r. The result is a BAT with the
4401 : * oids of those values in l that do not occur in r. This is what you
4402 : * might call an anti-semi-join. The result is a candidate list. */
4403 : BAT *
4404 161905 : BATdiff(BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, bool not_in,
4405 : BUN estimate)
4406 : {
4407 161905 : BAT *bn;
4408 :
4409 161905 : if (leftjoin(&bn, NULL, NULL, l, r, sl, sr, nil_matches,
4410 : false, false, true, not_in, false, false,
4411 : estimate, __func__,
4412 161905 : GDK_TRACER_TEST(M_DEBUG, ALGO) ? GDKusec() : 0) == GDK_SUCCEED)
4413 161776 : return bn;
4414 : return NULL;
4415 : }
4416 :
4417 : gdk_return
4418 50906 : BATthetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, int op, bool nil_matches, BUN estimate)
4419 : {
4420 50906 : int opcode = 0;
4421 50906 : lng t0 = 0;
4422 :
4423 : /* encode operator as a bit mask into opcode */
4424 50906 : switch (op) {
4425 0 : case JOIN_EQ:
4426 0 : return BATjoin(r1p, r2p, l, r, sl, sr, nil_matches, estimate);
4427 : case JOIN_NE:
4428 : opcode = MASK_NE;
4429 : break;
4430 8366 : case JOIN_LT:
4431 8366 : opcode = MASK_LT;
4432 8366 : break;
4433 11 : case JOIN_LE:
4434 11 : opcode = MASK_LE;
4435 11 : break;
4436 42432 : case JOIN_GT:
4437 42432 : opcode = MASK_GT;
4438 42432 : break;
4439 34 : case JOIN_GE:
4440 34 : opcode = MASK_GE;
4441 34 : break;
4442 0 : default:
4443 0 : GDKerror("unknown operator %d.\n", op);
4444 0 : return GDK_FAIL;
4445 : }
4446 :
4447 50906 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
4448 50906 : *r1p = NULL;
4449 50906 : if (r2p) {
4450 8444 : *r2p = NULL;
4451 : }
4452 50906 : if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED)
4453 : return GDK_FAIL;
4454 :
4455 50893 : return thetajoin(r1p, r2p, l, r, sl, sr, opcode, estimate, nil_matches,
4456 : __func__, t0);
4457 : }
4458 :
4459 : gdk_return
4460 418905 : BATjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr, bool nil_matches, BUN estimate)
4461 : {
4462 418905 : struct canditer lci, rci;
4463 418905 : bool lhash = false, rhash = false, lcand = false;
4464 418905 : bool plhash = false, prhash = false, rcand = false;
4465 418905 : bool swap;
4466 418905 : bat parent;
4467 418905 : double rcost = 0;
4468 418905 : double lcost = 0;
4469 418905 : gdk_return rc;
4470 418905 : lng t0 = 0;
4471 418905 : BAT *r2 = NULL;
4472 418905 : BAT *lp = NULL;
4473 418905 : BAT *rp = NULL;
4474 :
4475 418905 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
4476 :
4477 418905 : canditer_init(&lci, l, sl);
4478 419523 : canditer_init(&rci, r, sr);
4479 :
4480 419347 : if ((parent = VIEWtparent(l)) != 0) {
4481 69075 : lp = BATdescriptor(parent);
4482 69092 : if (lp == NULL)
4483 : return GDK_FAIL;
4484 69092 : if (l->hseqbase == lp->hseqbase &&
4485 70987 : BATcount(l) == BATcount(lp) &&
4486 26817 : ATOMtype(l->ttype) == ATOMtype(lp->ttype)) {
4487 : l = lp;
4488 : } else {
4489 55683 : BBPunfix(lp->batCacheid);
4490 55683 : lp = NULL;
4491 : }
4492 : }
4493 419363 : if ((parent = VIEWtparent(r)) != 0) {
4494 324653 : rp = BATdescriptor(parent);
4495 324584 : if (rp == NULL) {
4496 0 : BBPreclaim(lp);
4497 0 : return GDK_FAIL;
4498 : }
4499 324584 : if (r->hseqbase == rp->hseqbase &&
4500 548723 : BATcount(r) == BATcount(rp) &&
4501 488974 : ATOMtype(r->ttype) == ATOMtype(rp->ttype)) {
4502 : r = rp;
4503 : } else {
4504 80123 : BBPunfix(rp->batCacheid);
4505 80123 : rp = NULL;
4506 : }
4507 : }
4508 :
4509 419304 : if (l->ttype == TYPE_msk || mask_cand(l)) {
4510 0 : l = BATunmask(l);
4511 0 : BBPreclaim(lp);
4512 0 : if (l == NULL) {
4513 0 : BBPreclaim(rp);
4514 0 : return GDK_FAIL;
4515 : }
4516 : lp = l;
4517 : }
4518 419304 : if (r->ttype == TYPE_msk || mask_cand(r)) {
4519 24 : r = BATunmask(r);
4520 24 : BBPreclaim(rp);
4521 24 : if (r == NULL) {
4522 0 : BBPreclaim(lp);
4523 0 : return GDK_FAIL;
4524 : }
4525 : rp = r;
4526 : }
4527 :
4528 419304 : *r1p = NULL;
4529 419304 : if (r2p)
4530 374026 : *r2p = NULL;
4531 :
4532 419304 : if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED) {
4533 0 : rc = GDK_FAIL;
4534 0 : goto doreturn;
4535 : }
4536 :
4537 419024 : if (lci.ncand == 0 || rci.ncand == 0) {
4538 337901 : TRC_DEBUG(ALGO, "BATjoin(l=" ALGOBATFMT ","
4539 : "r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
4540 : "sr=" ALGOOPTBATFMT ",nil_matches=%d)\n",
4541 : ALGOBATPAR(l), ALGOBATPAR(r),
4542 : ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
4543 : nil_matches);
4544 337901 : rc = nomatch(r1p, r2p, NULL, l, r, &lci,
4545 : 0, false, false, __func__, t0);
4546 337538 : goto doreturn;
4547 : }
4548 :
4549 81123 : swap = false;
4550 :
4551 81123 : if (lci.ncand == 1 || (BATordered(l) && BATordered_rev(l)) || (l->ttype == TYPE_void && is_oid_nil(l->tseqbase))) {
4552 : /* single value to join, use select */
4553 41224 : rc = selectjoin(r1p, r2p, NULL, l, r, &lci, &rci,
4554 : nil_matches, false, false, false, false,
4555 : t0, false, __func__);
4556 41163 : goto doreturn;
4557 39900 : } else if (rci.ncand == 1 || (BATordered(r) && BATordered_rev(r)) || (r->ttype == TYPE_void && is_oid_nil(r->tseqbase))) {
4558 : /* single value to join, use select */
4559 17152 : rc = selectjoin(r2p ? r2p : &r2, r1p, NULL, r, l, &rci, &lci,
4560 : nil_matches, false, false, false, false,
4561 : t0, true, __func__);
4562 9990 : if (rc == GDK_SUCCEED && r2p == NULL)
4563 2897 : BBPunfix(r2->batCacheid);
4564 9995 : goto doreturn;
4565 29879 : } else if (BATtdense(r) && rci.tpe == cand_dense) {
4566 : /* use special implementation for dense right-hand side */
4567 1657 : rc = mergejoin_void(r1p, r2p, NULL, l, r, &lci, &rci,
4568 : false, false, t0, false, __func__);
4569 1642 : goto doreturn;
4570 28222 : } else if (BATtdense(l) && lci.tpe == cand_dense) {
4571 : /* use special implementation for dense right-hand side */
4572 79 : rc = mergejoin_void(r2p ? r2p : &r2, r1p, NULL, r, l, &rci, &lci,
4573 : false, false, t0, true, __func__);
4574 54 : if (rc == GDK_SUCCEED && r2p == NULL)
4575 27 : BBPunfix(r2->batCacheid);
4576 54 : goto doreturn;
4577 43270 : } else if ((BATordered(l) || BATordered_rev(l)) &&
4578 19695 : (BATordered(r) || BATordered_rev(r))) {
4579 : /* both sorted */
4580 10577 : rc = mergejoin(r1p, r2p, NULL, l, r, &lci, &rci,
4581 : nil_matches, false, false, false, false, false, false,
4582 : estimate, t0, false, __func__);
4583 10442 : goto doreturn;
4584 : }
4585 :
4586 17602 : lcost = joincost(l, rci.ncand, &lci, &lhash, &plhash, &lcand);
4587 17592 : rcost = joincost(r, lci.ncand, &rci, &rhash, &prhash, &rcand);
4588 17595 : if (lcost < 0 || rcost < 0) {
4589 0 : rc = GDK_FAIL;
4590 0 : goto doreturn;
4591 : }
4592 :
4593 : /* if the cost of doing searches on l is lower than the cost
4594 : * of doing searches on r, we swap */
4595 17595 : swap = (lcost < rcost);
4596 :
4597 35190 : if ((r->ttype == TYPE_void && r->tvheap != NULL) ||
4598 35322 : ((BATordered(r) || BATordered_rev(r)) &&
4599 5181 : (lci.ncand * (log2((double) rci.ncand) + 1) < (swap ? lcost : rcost)))) {
4600 : /* r is sorted and it is cheaper to do multiple binary
4601 : * searches than it is to use a hash */
4602 344 : rc = mergejoin(r1p, r2p, NULL, l, r, &lci, &rci,
4603 : nil_matches, false, false, false, false, false, false,
4604 : estimate, t0, false, __func__);
4605 34523 : } else if ((l->ttype == TYPE_void && l->tvheap != NULL) ||
4606 34742 : ((BATordered(l) || BATordered_rev(l)) &&
4607 4521 : (rci.ncand * (log2((double) lci.ncand) + 1) < (swap ? lcost : rcost)))) {
4608 : /* l is sorted and it is cheaper to do multiple binary
4609 : * searches than it is to use a hash */
4610 3535 : rc = mergejoin(r2p ? r2p : &r2, r1p, NULL, r, l, &rci, &lci,
4611 : nil_matches, false, false, false, false, false, false,
4612 : estimate, t0, true, __func__);
4613 1728 : if (rc == GDK_SUCCEED && r2p == NULL)
4614 3 : BBPunfix(r2->batCacheid);
4615 15493 : } else if (swap) {
4616 14770 : rc = hashjoin(r2p ? r2p : &r2, r1p, NULL, r, l, &rci, &lci,
4617 : nil_matches, false, false, false, false, false, false,
4618 : estimate, t0, true, lhash, plhash, lcand,
4619 : __func__);
4620 7675 : if (rc == GDK_SUCCEED && r2p == NULL)
4621 636 : BBPunfix(r2->batCacheid);
4622 : } else {
4623 7789 : rc = hashjoin(r1p, r2p, NULL, l, r, &lci, &rci,
4624 : nil_matches, false, false, false, false, false, false,
4625 : estimate, t0, false, rhash, prhash, rcand,
4626 : __func__);
4627 : }
4628 418341 : doreturn:
4629 418341 : BBPreclaim(lp);
4630 417947 : BBPreclaim(rp);
4631 : return rc;
4632 : }
4633 :
4634 : gdk_return
4635 0 : BATbandjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT *sl, BAT *sr,
4636 : const void *c1, const void *c2, bool linc, bool hinc, BUN estimate)
4637 : {
4638 0 : lng t0 = 0;
4639 0 : struct canditer lci, rci;
4640 0 : const char *lvals, *rvals;
4641 0 : int t;
4642 0 : const void *nil = ATOMnilptr(l->ttype);
4643 0 : int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
4644 0 : const char *vl, *vr;
4645 0 : oid lastr = 0; /* last value inserted into r2 */
4646 0 : BUN nr;
4647 0 : oid lo, ro;
4648 0 : bool lskipped = false; /* whether we skipped values in l */
4649 :
4650 0 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
4651 :
4652 0 : size_t counter = 0;
4653 0 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
4654 :
4655 :
4656 0 : MT_thread_setalgorithm(__func__);
4657 0 : *r1p = NULL;
4658 0 : if (r2p) {
4659 0 : *r2p = NULL;
4660 : }
4661 0 : if (joinparamcheck(l, r, NULL, sl, sr, __func__) != GDK_SUCCEED)
4662 : return GDK_FAIL;
4663 :
4664 0 : assert(ATOMtype(l->ttype) == ATOMtype(r->ttype));
4665 :
4666 0 : t = ATOMtype(l->ttype);
4667 0 : t = ATOMbasetype(t);
4668 :
4669 0 : canditer_init(&lci, l, sl);
4670 0 : canditer_init(&rci, r, sr);
4671 :
4672 0 : if (lci.ncand == 0 || rci.ncand == 0)
4673 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4674 : 0, false, false, __func__, t0);
4675 :
4676 0 : switch (t) {
4677 0 : case TYPE_bte:
4678 0 : if (is_bte_nil(*(const bte *)c1) ||
4679 0 : is_bte_nil(*(const bte *)c2) ||
4680 0 : -*(const bte *)c1 > *(const bte *)c2 ||
4681 0 : ((!hinc || !linc) && -*(const bte *)c1 == *(const bte *)c2))
4682 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4683 : 0, false, false, __func__, t0);
4684 : break;
4685 0 : case TYPE_sht:
4686 0 : if (is_sht_nil(*(const sht *)c1) ||
4687 0 : is_sht_nil(*(const sht *)c2) ||
4688 0 : -*(const sht *)c1 > *(const sht *)c2 ||
4689 0 : ((!hinc || !linc) && -*(const sht *)c1 == *(const sht *)c2))
4690 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4691 : 0, false, false, __func__, t0);
4692 : break;
4693 0 : case TYPE_int:
4694 0 : if (is_int_nil(*(const int *)c1) ||
4695 0 : is_int_nil(*(const int *)c2) ||
4696 0 : -*(const int *)c1 > *(const int *)c2 ||
4697 0 : ((!hinc || !linc) && -*(const int *)c1 == *(const int *)c2))
4698 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4699 : 0, false, false, __func__, t0);
4700 : break;
4701 0 : case TYPE_lng:
4702 0 : if (is_lng_nil(*(const lng *)c1) ||
4703 0 : is_lng_nil(*(const lng *)c2) ||
4704 0 : -*(const lng *)c1 > *(const lng *)c2 ||
4705 0 : ((!hinc || !linc) && -*(const lng *)c1 == *(const lng *)c2))
4706 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4707 : 0, false, false, __func__, t0);
4708 : break;
4709 : #ifdef HAVE_HGE
4710 0 : case TYPE_hge:
4711 0 : if (is_hge_nil(*(const hge *)c1) ||
4712 0 : is_hge_nil(*(const hge *)c2) ||
4713 0 : -*(const hge *)c1 > *(const hge *)c2 ||
4714 0 : ((!hinc || !linc) && -*(const hge *)c1 == *(const hge *)c2))
4715 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4716 : 0, false, false, __func__, t0);
4717 : break;
4718 : #endif
4719 0 : case TYPE_flt:
4720 0 : if (is_flt_nil(*(const flt *)c1) ||
4721 0 : is_flt_nil(*(const flt *)c2) ||
4722 0 : -*(const flt *)c1 > *(const flt *)c2 ||
4723 0 : ((!hinc || !linc) && -*(const flt *)c1 == *(const flt *)c2))
4724 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4725 : 0, false, false, __func__, t0);
4726 : break;
4727 0 : case TYPE_dbl:
4728 0 : if (is_dbl_nil(*(const dbl *)c1) ||
4729 0 : is_dbl_nil(*(const dbl *)c2) ||
4730 0 : -*(const dbl *)c1 > *(const dbl *)c2 ||
4731 0 : ((!hinc || !linc) && -*(const dbl *)c1 == *(const dbl *)c2))
4732 0 : return nomatch(r1p, r2p, NULL, l, r, &lci,
4733 : 0, false, false, __func__, t0);
4734 : break;
4735 0 : default:
4736 0 : GDKerror("unsupported type\n");
4737 0 : return GDK_FAIL;
4738 : }
4739 :
4740 0 : BUN maxsize = joininitresults(r1p, r2p, NULL, lci.ncand, rci.ncand, false, false,
4741 : false, false, false, false, estimate);
4742 0 : if (maxsize == BUN_NONE)
4743 : return GDK_FAIL;
4744 0 : BAT *r1 = *r1p;
4745 0 : BAT *r2 = r2p ? *r2p : NULL;
4746 0 : BATiter li = bat_iterator(l);
4747 0 : BATiter ri = bat_iterator(r);
4748 :
4749 0 : lvals = (const char *) li.base;
4750 0 : rvals = (const char *) ri.base;
4751 0 : assert(ri.vh == NULL);
4752 :
4753 0 : assert(lvals != NULL);
4754 0 : assert(rvals != NULL);
4755 :
4756 0 : r1->tkey = true;
4757 0 : r1->tsorted = true;
4758 0 : r1->trevsorted = true;
4759 0 : if (r2) {
4760 0 : r2->tkey = true;
4761 0 : r2->tsorted = true;
4762 0 : r2->trevsorted = true;
4763 : }
4764 :
4765 : /* nested loop implementation for band join */
4766 0 : for (BUN lidx = 0; lidx < lci.ncand; lidx++) {
4767 0 : GDK_CHECK_TIMEOUT(qry_ctx, counter,
4768 : GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
4769 0 : lo = canditer_next(&lci);
4770 0 : vl = FVALUE(l, lo - l->hseqbase);
4771 0 : if (cmp(vl, nil) == 0)
4772 0 : continue;
4773 0 : nr = 0;
4774 0 : canditer_reset(&rci);
4775 0 : for (BUN ridx = 0; ridx < rci.ncand; ridx++) {
4776 0 : ro = canditer_next(&rci);
4777 0 : vr = FVALUE(r, ro - r->hseqbase);
4778 0 : switch (ATOMtype(li.type)) {
4779 0 : case TYPE_bte: {
4780 0 : if (is_bte_nil(*(const bte *) vr))
4781 0 : continue;
4782 0 : sht v1 = (sht) *(const bte *) vr, v2;
4783 0 : v2 = v1;
4784 0 : v1 -= *(const bte *)c1;
4785 0 : if (*(const bte *)vl <= v1 &&
4786 0 : (!linc || *(const bte *)vl != v1))
4787 0 : continue;
4788 0 : v2 += *(const bte *)c2;
4789 0 : if (*(const bte *)vl >= v2 &&
4790 0 : (!hinc || *(const bte *)vl != v2))
4791 0 : continue;
4792 : break;
4793 : }
4794 0 : case TYPE_sht: {
4795 0 : if (is_sht_nil(*(const sht *) vr))
4796 0 : continue;
4797 0 : int v1 = (int) *(const sht *) vr, v2;
4798 0 : v2 = v1;
4799 0 : v1 -= *(const sht *)c1;
4800 0 : if (*(const sht *)vl <= v1 &&
4801 0 : (!linc || *(const sht *)vl != v1))
4802 0 : continue;
4803 0 : v2 += *(const sht *)c2;
4804 0 : if (*(const sht *)vl >= v2 &&
4805 0 : (!hinc || *(const sht *)vl != v2))
4806 0 : continue;
4807 : break;
4808 : }
4809 0 : case TYPE_int: {
4810 0 : if (is_int_nil(*(const int *) vr))
4811 0 : continue;
4812 0 : lng v1 = (lng) *(const int *) vr, v2;
4813 0 : v2 = v1;
4814 0 : v1 -= *(const int *)c1;
4815 0 : if (*(const int *)vl <= v1 &&
4816 0 : (!linc || *(const int *)vl != v1))
4817 0 : continue;
4818 0 : v2 += *(const int *)c2;
4819 0 : if (*(const int *)vl >= v2 &&
4820 0 : (!hinc || *(const int *)vl != v2))
4821 0 : continue;
4822 : break;
4823 : }
4824 : #ifdef HAVE_HGE
4825 0 : case TYPE_lng: {
4826 0 : if (is_lng_nil(*(const lng *) vr))
4827 0 : continue;
4828 0 : hge v1 = (hge) *(const lng *) vr, v2;
4829 0 : v2 = v1;
4830 0 : v1 -= *(const lng *)c1;
4831 0 : if (*(const lng *)vl <= v1 &&
4832 0 : (!linc || *(const lng *)vl != v1))
4833 0 : continue;
4834 0 : v2 += *(const lng *)c2;
4835 0 : if (*(const lng *)vl >= v2 &&
4836 0 : (!hinc || *(const lng *)vl != v2))
4837 0 : continue;
4838 : break;
4839 : }
4840 : #else
4841 : #ifdef HAVE___INT128
4842 : case TYPE_lng: {
4843 : if (is_lng_nil(*(const lng *) vr))
4844 : continue;
4845 : __int128 v1 = (__int128) *(const lng *) vr, v2;
4846 : v2 = v1;
4847 : v1 -= *(const lng *)c1;
4848 : if (*(const lng *)vl <= v1 &&
4849 : (!linc || *(const lng *)vl != v1))
4850 : continue;
4851 : v2 += *(const lng *)c2;
4852 : if (*(const lng *)vl >= v2 &&
4853 : (!hinc || *(const lng *)vl != v2))
4854 : continue;
4855 : break;
4856 : }
4857 : #else
4858 : #ifdef HAVE___INT128_T
4859 : case TYPE_lng: {
4860 : if (is_lng_nil(*(const lng *) vr))
4861 : continue;
4862 : __int128_t v1 = (__int128_t) *(const lng *) vr, v2;
4863 : v2 = v1;
4864 : v1 -= *(const lng *)c1;
4865 : if (*(const lng *)vl <= v1 &&
4866 : (!linc || *(const lng *)vl != v1))
4867 : continue;
4868 : v2 += *(const lng *)c2;
4869 : if (*(const lng *)vl >= v2 &&
4870 : (!hinc || *(const lng *)vl != v2))
4871 : continue;
4872 : break;
4873 : }
4874 : #else
4875 : case TYPE_lng: {
4876 : if (is_lng_nil(*(const lng *) vr))
4877 : continue;
4878 : lng v1, v2;
4879 : SUBI_WITH_CHECK(*(const lng *)vr,
4880 : *(const lng *)c1,
4881 : lng, v1,
4882 : GDK_lng_max,
4883 : do{if(*(const lng*)c1<0)goto nolmatch;else goto lmatch1;}while(false));
4884 : if (*(const lng *)vl <= v1 &&
4885 : (!linc || *(const lng *)vl != v1))
4886 : continue;
4887 : lmatch1:
4888 : ADDI_WITH_CHECK(*(const lng *)vr,
4889 : *(const lng *)c2,
4890 : lng, v2,
4891 : GDK_lng_max,
4892 : do{if(*(const lng*)c2>0)goto nolmatch;else goto lmatch2;}while(false));
4893 : if (*(const lng *)vl >= v2 &&
4894 : (!hinc || *(const lng *)vl != v2))
4895 : continue;
4896 : lmatch2:
4897 : break;
4898 : nolmatch:
4899 : continue;
4900 : }
4901 : #endif
4902 : #endif
4903 : #endif
4904 : #ifdef HAVE_HGE
4905 0 : case TYPE_hge: {
4906 0 : if (is_hge_nil(*(const hge *) vr))
4907 0 : continue;
4908 0 : hge v1, v2;
4909 0 : SUBI_WITH_CHECK(*(const hge *)vr,
4910 : *(const hge *)c1,
4911 : hge, v1,
4912 : GDK_hge_max,
4913 : do{if(*(const hge*)c1<0)goto nohmatch;else goto hmatch1;}while(false));
4914 0 : if (*(const hge *)vl <= v1 &&
4915 0 : (!linc || *(const hge *)vl != v1))
4916 0 : continue;
4917 0 : hmatch1:
4918 0 : ADDI_WITH_CHECK(*(const hge *)vr,
4919 : *(const hge *)c2,
4920 : hge, v2,
4921 : GDK_hge_max,
4922 : do{if(*(const hge*)c2>0)goto nohmatch;else goto hmatch2;}while(false));
4923 0 : if (*(const hge *)vl >= v2 &&
4924 0 : (!hinc || *(const hge *)vl != v2))
4925 0 : continue;
4926 0 : hmatch2:
4927 : break;
4928 0 : nohmatch:
4929 0 : continue;
4930 : }
4931 : #endif
4932 0 : case TYPE_flt: {
4933 0 : if (is_flt_nil(*(const flt *) vr))
4934 0 : continue;
4935 0 : dbl v1 = (dbl) *(const flt *) vr, v2;
4936 0 : v2 = v1;
4937 0 : v1 -= *(const flt *)c1;
4938 0 : if (*(const flt *)vl <= v1 &&
4939 0 : (!linc || *(const flt *)vl != v1))
4940 0 : continue;
4941 0 : v2 += *(const flt *)c2;
4942 0 : if (*(const flt *)vl >= v2 &&
4943 0 : (!hinc || *(const flt *)vl != v2))
4944 0 : continue;
4945 : break;
4946 : }
4947 0 : case TYPE_dbl: {
4948 0 : if (is_dbl_nil(*(const dbl *) vr))
4949 0 : continue;
4950 0 : dbl v1, v2;
4951 0 : SUBF_WITH_CHECK(*(const dbl *)vr,
4952 : *(const dbl *)c1,
4953 : dbl, v1,
4954 : GDK_dbl_max,
4955 : do{if(*(const dbl*)c1<0)goto nodmatch;else goto dmatch1;}while(false));
4956 0 : if (*(const dbl *)vl <= v1 &&
4957 0 : (!linc || *(const dbl *)vl != v1))
4958 0 : continue;
4959 0 : dmatch1:
4960 0 : ADDF_WITH_CHECK(*(const dbl *)vr,
4961 : *(const dbl *)c2,
4962 : dbl, v2,
4963 : GDK_dbl_max,
4964 : do{if(*(const dbl*)c2>0)goto nodmatch;else goto dmatch2;}while(false));
4965 0 : if (*(const dbl *)vl >= v2 &&
4966 0 : (!hinc || *(const dbl *)vl != v2))
4967 0 : continue;
4968 0 : dmatch2:
4969 : break;
4970 0 : nodmatch:
4971 0 : continue;
4972 : }
4973 : }
4974 0 : if (maybeextend(r1, r2, NULL, 1, lci.next, lci.ncand, maxsize) != GDK_SUCCEED)
4975 0 : goto bailout;
4976 0 : if (BATcount(r1) > 0) {
4977 0 : if (r2 && lastr + 1 != ro)
4978 0 : r2->tseqbase = oid_nil;
4979 0 : if (nr == 0) {
4980 0 : r1->trevsorted = false;
4981 0 : if (r2 == NULL) {
4982 : /* nothing */
4983 0 : } else if (lastr > ro) {
4984 0 : r2->tsorted = false;
4985 0 : r2->tkey = false;
4986 0 : } else if (lastr < ro) {
4987 0 : r2->trevsorted = false;
4988 : } else {
4989 0 : r2->tkey = false;
4990 : }
4991 : }
4992 : }
4993 0 : APPEND(r1, lo);
4994 0 : if (r2) {
4995 0 : APPEND(r2, ro);
4996 : }
4997 0 : lastr = ro;
4998 0 : nr++;
4999 : }
5000 0 : if (nr > 1) {
5001 0 : r1->tkey = false;
5002 0 : r1->tseqbase = oid_nil;
5003 0 : if (r2) {
5004 0 : r2->trevsorted = false;
5005 : }
5006 0 : } else if (nr == 0) {
5007 0 : lskipped = BATcount(r1) > 0;
5008 0 : } else if (lskipped) {
5009 0 : r1->tseqbase = oid_nil;
5010 : }
5011 : }
5012 : /* also set other bits of heap to correct value to indicate size */
5013 0 : BATsetcount(r1, BATcount(r1));
5014 0 : if (r2) {
5015 0 : BATsetcount(r2, BATcount(r2));
5016 0 : assert(BATcount(r1) == BATcount(r2));
5017 : }
5018 0 : if (BATcount(r1) > 0) {
5019 0 : if (BATtdense(r1))
5020 0 : r1->tseqbase = ((oid *) r1->theap->base)[0];
5021 0 : if (r2 && BATtdense(r2))
5022 0 : r2->tseqbase = ((oid *) r2->theap->base)[0];
5023 : } else {
5024 0 : r1->tseqbase = 0;
5025 0 : if (r2) {
5026 0 : r2->tseqbase = 0;
5027 : }
5028 : }
5029 0 : bat_iterator_end(&li);
5030 0 : bat_iterator_end(&ri);
5031 0 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT "," "r=" ALGOBATFMT
5032 : ",sl=" ALGOOPTBATFMT "," "sr=" ALGOOPTBATFMT ","
5033 : " -> " ALGOBATFMT "," ALGOOPTBATFMT
5034 : " (" LLFMT "usec)\n",
5035 : ALGOBATPAR(l), ALGOBATPAR(r),
5036 : ALGOOPTBATPAR(sl), ALGOOPTBATPAR(sr),
5037 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
5038 : GDKusec() - t0);
5039 : return GDK_SUCCEED;
5040 :
5041 0 : bailout:
5042 0 : bat_iterator_end(&li);
5043 0 : bat_iterator_end(&ri);
5044 0 : BBPreclaim(r1);
5045 0 : BBPreclaim(r2);
5046 : return GDK_FAIL;
5047 : }
5048 :
5049 : #define LTany(a,b) ((*cmp)(a, b) < 0)
5050 : #define EQany(a,b) ((*cmp)(a, b) == 0)
5051 : #define is_any_nil(v) ((v) == NULL || (*cmp)((v), nil) == 0)
5052 :
5053 : #define less3(a,b,i,t) (is_##t##_nil(a) || is_##t##_nil(b) ? bit_nil : LT##t(a, b) || (i && EQ##t(a, b)))
5054 : #define grtr3(a,b,i,t) (is_##t##_nil(a) || is_##t##_nil(b) ? bit_nil : LT##t(b, a) || (i && EQ##t(a, b)))
5055 : #define or3(a,b) ((a) == 1 || (b) == 1 ? 1 : is_bit_nil(a) || is_bit_nil(b) ? bit_nil : 0)
5056 : #define and3(a,b) ((a) == 0 || (b) == 0 ? 0 : is_bit_nil(a) || is_bit_nil(b) ? bit_nil : 1)
5057 : #define not3(a) (is_bit_nil(a) ? bit_nil : !(a))
5058 :
5059 : #define between3(v, lo, linc, hi, hinc, TYPE) \
5060 : and3(grtr3(v, lo, linc, TYPE), less3(v, hi, hinc, TYPE))
5061 :
5062 : #define BETWEEN(v, lo, linc, hi, hinc, TYPE) \
5063 : (is_##TYPE##_nil(v) \
5064 : ? bit_nil \
5065 : : (bit) (anti \
5066 : ? (symmetric \
5067 : ? not3(or3(between3(v, lo, linc, hi, hinc, TYPE), \
5068 : between3(v, hi, hinc, lo, linc, TYPE))) \
5069 : : not3(between3(v, lo, linc, hi, hinc, TYPE))) \
5070 : : (symmetric \
5071 : ? or3(between3(v, lo, linc, hi, hinc, TYPE), \
5072 : between3(v, hi, hinc, lo, linc, TYPE)) \
5073 : : between3(v, lo, linc, hi, hinc, TYPE))))
5074 :
5075 : static gdk_return
5076 123 : rangejoin(BAT *r1, BAT *r2, BAT *l, BAT *rl, BAT *rh,
5077 : struct canditer *lci, struct canditer *rci,
5078 : bool linc, bool hinc, bool anti, bool symmetric, BUN maxsize)
5079 : {
5080 123 : if (!anti && !symmetric) {
5081 : /* we'll need these */
5082 112 : (void) BATordered(l);
5083 114 : (void) BATordered_rev(l);
5084 : }
5085 125 : BATiter li = bat_iterator(l);
5086 125 : BATiter rli = bat_iterator(rl);
5087 125 : BATiter rhi = bat_iterator(rh);
5088 125 : const char *rlvals, *rhvals;
5089 125 : const char *lvars, *rlvars, *rhvars;
5090 125 : const void *nil = ATOMnilptr(li.type);
5091 125 : int (*cmp)(const void *, const void *) = ATOMcompare(li.type);
5092 125 : int t;
5093 125 : BUN cnt, ncnt, lncand = lci->ncand, rncand = rci->ncand;
5094 125 : oid *restrict dst1, *restrict dst2;
5095 125 : const void *vrl, *vrh;
5096 125 : oid ro;
5097 125 : oid rlval = oid_nil, rhval = oid_nil;
5098 125 : int sorted = 0; /* which output column is sorted */
5099 125 : Heap *oidxh = NULL;
5100 :
5101 125 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
5102 :
5103 375 : assert(ATOMtype(li.type) == ATOMtype(rli.type));
5104 250 : assert(ATOMtype(li.type) == ATOMtype(rhi.type));
5105 125 : assert(BATcount(rl) == BATcount(rh));
5106 125 : assert(rl->hseqbase == rh->hseqbase);
5107 125 : assert(r1->ttype == TYPE_oid);
5108 125 : assert(r2 == NULL || r2->ttype == TYPE_oid);
5109 106 : assert(r2 == NULL || BATcount(r1) == BATcount(r2));
5110 125 : assert(li.type != TYPE_void || !is_oid_nil(l->tseqbase));
5111 125 : assert(rli.type != TYPE_void || !is_oid_nil(rl->tseqbase));
5112 125 : assert(rhi.type != TYPE_void || !is_oid_nil(rh->tseqbase));
5113 :
5114 125 : TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
5115 : "rl=" ALGOBATFMT ",rh=" ALGOBATFMT ","
5116 : "sl=" ALGOOPTBATFMT ",sr=" ALGOOPTBATFMT ","
5117 : "anti=%s,symmetric=%s\n",
5118 : ALGOBATPAR(l),
5119 : ALGOBATPAR(rl),
5120 : ALGOBATPAR(rh),
5121 : ALGOOPTBATPAR(lci->s),
5122 : ALGOOPTBATPAR(rci->s),
5123 : anti ? "true" : "false",
5124 : symmetric ? "true" : "false");
5125 :
5126 125 : rlvals = rli.type == TYPE_void ? NULL : (const char *) rli.base;
5127 125 : rhvals = rhi.type == TYPE_void ? NULL : (const char *) rhi.base;
5128 125 : dst1 = (oid *) Tloc(r1, 0);
5129 125 : dst2 = r2 ? (oid *) Tloc(r2, 0) : NULL;
5130 :
5131 125 : t = ATOMtype(li.type);
5132 125 : t = ATOMbasetype(t);
5133 :
5134 125 : if (li.vh && li.type) {
5135 17 : assert(rli.vh && rli.type);
5136 17 : assert(rhi.vh && rhi.type);
5137 17 : lvars = li.vh->base;
5138 17 : rlvars = rli.vh->base;
5139 17 : rhvars = rhi.vh->base;
5140 : } else {
5141 108 : assert(rli.vh == NULL);
5142 108 : assert(rhi.vh == NULL);
5143 : lvars = rlvars = rhvars = NULL;
5144 : }
5145 :
5146 125 : if (!anti && !symmetric && !li.sorted && !li.revsorted) {
5147 13 : (void) BATcheckorderidx(l);
5148 13 : MT_lock_set(&l->batIdxLock);
5149 13 : if ((oidxh = l->torderidx) != NULL)
5150 0 : HEAPincref(oidxh);
5151 13 : MT_lock_unset(&l->batIdxLock);
5152 : #if 0 /* needs checking */
5153 : if (oidxh == NULL && VIEWtparent(l)) {
5154 : /* if enabled, need to fix/unfix parent bat */
5155 : BAT *pb = BBP_desc(VIEWtparent(l));
5156 : (void) BATcheckorderidx(pb);
5157 : MT_lock_set(&pb->batIdxLock);
5158 : if ((oidxh = pb->torderidx) != NULL) {
5159 : HEAPincref(oidxh);
5160 : l = pb;
5161 : }
5162 : MT_lock_unset(&pb->batIdxLock);
5163 : }
5164 : #endif
5165 : }
5166 :
5167 125 : vrl = &rlval;
5168 125 : vrh = &rhval;
5169 125 : if (!anti && !symmetric && (li.sorted || li.revsorted || oidxh)) {
5170 : /* left column is sorted, use binary search */
5171 101 : sorted = 2;
5172 611 : TIMEOUT_LOOP(rncand, qry_ctx) {
5173 411 : BUN low, high;
5174 :
5175 411 : ro = canditer_next(rci);
5176 398 : if (rlvals) {
5177 398 : vrl = VALUE(rl, ro - rl->hseqbase);
5178 : } else {
5179 : /* TYPE_void */
5180 0 : rlval = ro - rl->hseqbase + rl->tseqbase;
5181 : }
5182 398 : if (rhvals) {
5183 398 : vrh = VALUE(rh, ro - rh->hseqbase);
5184 : } else {
5185 : /* TYPE_void */
5186 0 : rhval = ro - rh->hseqbase + rh->tseqbase;
5187 : }
5188 398 : if (cmp(vrl, nil) == 0 || cmp(vrh, nil) == 0)
5189 9 : continue;
5190 385 : if (li.sorted) {
5191 382 : if (linc)
5192 271 : low = SORTfndfirst(l, vrl);
5193 : else
5194 111 : low = SORTfndlast(l, vrl);
5195 404 : if (hinc)
5196 345 : high = SORTfndlast(l, vrh);
5197 : else
5198 59 : high = SORTfndfirst(l, vrh);
5199 3 : } else if (li.revsorted) {
5200 3 : if (hinc)
5201 3 : low = SORTfndfirst(l, vrh);
5202 : else
5203 0 : low = SORTfndlast(l, vrh);
5204 3 : if (linc)
5205 3 : high = SORTfndlast(l, vrl);
5206 : else
5207 0 : high = SORTfndfirst(l, vrl);
5208 : } else {
5209 0 : assert(oidxh);
5210 0 : if (linc)
5211 0 : low = ORDERfndfirst(l, oidxh, vrl);
5212 : else
5213 0 : low = ORDERfndlast(l, oidxh, vrl);
5214 0 : if (hinc)
5215 0 : high = ORDERfndlast(l, oidxh, vrh);
5216 : else
5217 0 : high = ORDERfndfirst(l, oidxh, vrh);
5218 : }
5219 406 : if (high <= low)
5220 222 : continue;
5221 184 : if (li.sorted || li.revsorted) {
5222 184 : low = canditer_search(lci, low + l->hseqbase, true);
5223 184 : high = canditer_search(lci, high + l->hseqbase, true);
5224 184 : assert(high >= low);
5225 :
5226 184 : if (BATcapacity(r1) < BATcount(r1) + high - low) {
5227 0 : cnt = BATcount(r1) + high - low + 1024;
5228 0 : if (cnt > maxsize)
5229 : cnt = maxsize;
5230 0 : BATsetcount(r1, BATcount(r1));
5231 0 : if (BATextend(r1, cnt) != GDK_SUCCEED)
5232 0 : goto bailout;
5233 0 : dst1 = (oid *) Tloc(r1, 0);
5234 0 : if (r2) {
5235 0 : BATsetcount(r2, BATcount(r2));
5236 0 : if (BATextend(r2, cnt) != GDK_SUCCEED)
5237 0 : goto bailout;
5238 0 : assert(BATcapacity(r1) == BATcapacity(r2));
5239 0 : dst2 = (oid *) Tloc(r2, 0);
5240 : }
5241 : }
5242 184 : canditer_setidx(lci, low);
5243 1002 : while (low < high) {
5244 821 : dst1[r1->batCount++] = canditer_next(lci);
5245 818 : if (r2) {
5246 806 : dst2[r2->batCount++] = ro;
5247 : }
5248 818 : low++;
5249 : }
5250 : } else {
5251 0 : const oid *ord;
5252 :
5253 0 : assert(oidxh);
5254 0 : ord = (const oid *) oidxh->base + ORDERIDXOFF;
5255 :
5256 0 : if (BATcapacity(r1) < BATcount(r1) + high - low) {
5257 0 : cnt = BATcount(r1) + high - low + 1024;
5258 0 : if (cnt > maxsize)
5259 : cnt = maxsize;
5260 0 : BATsetcount(r1, BATcount(r1));
5261 0 : if (BATextend(r1, cnt) != GDK_SUCCEED)
5262 0 : goto bailout;
5263 0 : dst1 = (oid *) Tloc(r1, 0);
5264 0 : if (r2) {
5265 0 : BATsetcount(r2, BATcount(r2));
5266 0 : if (BATextend(r2, cnt) != GDK_SUCCEED)
5267 0 : goto bailout;
5268 0 : assert(BATcapacity(r1) == BATcapacity(r2));
5269 0 : dst2 = (oid *) Tloc(r2, 0);
5270 : }
5271 : }
5272 :
5273 0 : while (low < high) {
5274 0 : if (canditer_contains(lci, ord[low])) {
5275 0 : dst1[r1->batCount++] = ord[low];
5276 0 : if (r2) {
5277 0 : dst2[r2->batCount++] = ro;
5278 : }
5279 : }
5280 0 : low++;
5281 : }
5282 : }
5283 : }
5284 100 : if (oidxh)
5285 0 : HEAPdecref(oidxh, false);
5286 100 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
5287 99 : cnt = BATcount(r1);
5288 99 : assert(r2 == NULL || BATcount(r1) == BATcount(r2));
5289 : } else {
5290 : /* nested loop implementation */
5291 24 : const void *vl;
5292 24 : const char *lvals;
5293 24 : oid lval;
5294 :
5295 24 : sorted = 1;
5296 24 : lvals = li.type == TYPE_void ? NULL : (const char *) li.base;
5297 24 : vl = &lval;
5298 286 : TIMEOUT_LOOP(lncand, qry_ctx) {
5299 238 : oid lo;
5300 :
5301 238 : lo = canditer_next(lci);
5302 238 : if (lvals) {
5303 238 : vl = VALUE(l, lo - l->hseqbase);
5304 238 : if (cmp(vl, nil) == 0)
5305 8 : continue;
5306 : } else {
5307 0 : lval = lo - l->hseqbase + l->tseqbase;
5308 : }
5309 229 : canditer_reset(rci);
5310 30724 : for (BUN j = 0; j < rncand; j++) {
5311 30495 : ro = canditer_next(rci);
5312 23400 : if (rlvals) {
5313 23400 : vrl = VALUE(rl, ro - rl->hseqbase);
5314 : } else {
5315 : /* TYPE_void */
5316 0 : rlval = ro - rl->hseqbase + rl->tseqbase;
5317 : }
5318 23400 : if (rhvals) {
5319 23400 : vrh = VALUE(rh, ro - rh->hseqbase);
5320 : } else {
5321 : /* TYPE_void */
5322 0 : rhval = ro - rh->hseqbase + rh->tseqbase;
5323 : }
5324 23403 : if (BETWEEN(vl, vrl, linc, vrh, hinc, any) != 1)
5325 18526 : continue;
5326 11969 : if (BATcount(r1) == BATcapacity(r1)) {
5327 2 : BUN newcap = BATgrows(r1);
5328 2 : if (newcap > maxsize)
5329 : newcap = maxsize;
5330 2 : BATsetcount(r1, BATcount(r1));
5331 2 : if (BATextend(r1, newcap) != GDK_SUCCEED)
5332 0 : goto bailout;
5333 2 : dst1 = (oid *) Tloc(r1, 0);
5334 2 : if (r2) {
5335 2 : BATsetcount(r2, BATcount(r2));
5336 2 : if (BATextend(r2, newcap) != GDK_SUCCEED)
5337 0 : goto bailout;
5338 2 : assert(BATcapacity(r1) == BATcapacity(r2));
5339 2 : dst2 = (oid *) Tloc(r2, 0);
5340 : }
5341 : }
5342 11969 : dst1[r1->batCount++] = lo;
5343 11969 : if (r2) {
5344 11960 : dst2[r2->batCount++] = ro;
5345 : }
5346 : }
5347 : }
5348 24 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
5349 23 : cnt = BATcount(r1);
5350 23 : assert(r2 == NULL || BATcount(r1) == BATcount(r2));
5351 : }
5352 :
5353 : /* also set other bits of heap to correct value to indicate size */
5354 122 : BATsetcount(r1, cnt);
5355 :
5356 : /* set properties using an extra scan (usually not complete) */
5357 123 : dst1 = (oid *) Tloc(r1, 0);
5358 123 : r1->tkey = true;
5359 123 : r1->tsorted = true;
5360 123 : r1->trevsorted = true;
5361 123 : r1->tseqbase = 0;
5362 123 : r1->tnil = false;
5363 123 : r1->tnonil = true;
5364 591 : for (ncnt = 1; ncnt < cnt; ncnt++) {
5365 479 : if (dst1[ncnt - 1] == dst1[ncnt]) {
5366 425 : r1->tseqbase = oid_nil;
5367 425 : r1->tkey = false;
5368 54 : } else if (dst1[ncnt - 1] < dst1[ncnt]) {
5369 52 : r1->trevsorted = false;
5370 52 : if (dst1[ncnt - 1] + 1 != dst1[ncnt])
5371 3 : r1->tseqbase = oid_nil;
5372 : } else {
5373 2 : assert(sorted != 1);
5374 2 : r1->tsorted = false;
5375 2 : r1->tseqbase = oid_nil;
5376 2 : r1->tkey = false;
5377 : }
5378 520 : if (!(r1->trevsorted | BATtdense(r1) | r1->tkey | ((sorted != 1) & r1->tsorted)))
5379 : break;
5380 : }
5381 123 : if (BATtdense(r1))
5382 102 : r1->tseqbase = cnt > 0 ? dst1[0] : 0;
5383 123 : if (r2) {
5384 105 : BATsetcount(r2, cnt);
5385 103 : dst2 = (oid *) Tloc(r2, 0);
5386 103 : r2->tkey = true;
5387 103 : r2->tsorted = true;
5388 103 : r2->trevsorted = true;
5389 103 : r2->tseqbase = 0;
5390 103 : r2->tnil = false;
5391 103 : r2->tnonil = true;
5392 565 : for (ncnt = 1; ncnt < cnt; ncnt++) {
5393 475 : if (dst2[ncnt - 1] == dst2[ncnt]) {
5394 36 : r2->tseqbase = oid_nil;
5395 36 : r2->tkey = false;
5396 439 : } else if (dst2[ncnt - 1] < dst2[ncnt]) {
5397 429 : r2->trevsorted = false;
5398 429 : if (dst2[ncnt - 1] + 1 != dst2[ncnt])
5399 127 : r2->tseqbase = oid_nil;
5400 : } else {
5401 10 : assert(sorted != 2);
5402 10 : r2->tsorted = false;
5403 10 : r2->tseqbase = oid_nil;
5404 10 : r2->tkey = false;
5405 : }
5406 646 : if (!(r2->trevsorted | BATtdense(r2) | r2->tkey | ((sorted != 2) & r2->tsorted)))
5407 : break;
5408 : }
5409 103 : if (BATtdense(r2))
5410 76 : r2->tseqbase = cnt > 0 ? dst2[0] : 0;
5411 : }
5412 121 : TRC_DEBUG(ALGO, "l=%s,rl=%s,rh=%s -> "
5413 : "(" ALGOBATFMT "," ALGOOPTBATFMT ")\n",
5414 : BATgetId(l), BATgetId(rl), BATgetId(rh),
5415 : ALGOBATPAR(r1), ALGOOPTBATPAR(r2));
5416 121 : bat_iterator_end(&li);
5417 123 : bat_iterator_end(&rli);
5418 124 : bat_iterator_end(&rhi);
5419 124 : return GDK_SUCCEED;
5420 :
5421 0 : bailout:
5422 0 : bat_iterator_end(&li);
5423 0 : bat_iterator_end(&rli);
5424 0 : bat_iterator_end(&rhi);
5425 0 : BBPreclaim(r1);
5426 0 : BBPreclaim(r2);
5427 : return GDK_FAIL;
5428 : }
5429 :
5430 : gdk_return
5431 147 : BATrangejoin(BAT **r1p, BAT **r2p, BAT *l, BAT *rl, BAT *rh,
5432 : BAT *sl, BAT *sr, bool linc, bool hinc, bool anti, bool symmetric,
5433 : BUN estimate)
5434 : {
5435 147 : struct canditer lci, rci;
5436 147 : BAT *r1 = NULL, *r2 = NULL;
5437 147 : BUN maxsize;
5438 147 : lng t0 = 0;
5439 :
5440 147 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
5441 147 : *r1p = NULL;
5442 147 : if (r2p) {
5443 122 : *r2p = NULL;
5444 : }
5445 147 : if (joinparamcheck(l, rl, rh, sl, sr, __func__) != GDK_SUCCEED)
5446 : return GDK_FAIL;
5447 147 : canditer_init(&lci, l, sl);
5448 147 : canditer_init(&rci, rl, sr);
5449 147 : if (lci.ncand == 0 ||
5450 137 : rci.ncand == 0 ||
5451 125 : (l->ttype == TYPE_void && is_oid_nil(l->tseqbase)) ||
5452 125 : ((rl->ttype == TYPE_void && is_oid_nil(rl->tseqbase)) &&
5453 0 : (rh->ttype == TYPE_void && is_oid_nil(rh->tseqbase)))) {
5454 : /* trivial: empty input */
5455 22 : return nomatch(r1p, r2p, NULL, l, rl, &lci, 0, false, false,
5456 : __func__, t0);
5457 : }
5458 125 : if (rl->ttype == TYPE_void && is_oid_nil(rl->tseqbase)) {
5459 0 : if (!anti)
5460 0 : return nomatch(r1p, r2p, NULL, l, rl, &lci, 0, false, false,
5461 : __func__, t0);
5462 0 : return thetajoin(r1p, r2p, l, rh, sl, sr, MASK_GT, estimate, false,
5463 : __func__, t0);
5464 : }
5465 125 : if (rh->ttype == TYPE_void && is_oid_nil(rh->tseqbase)) {
5466 0 : if (!anti)
5467 0 : return nomatch(r1p, r2p, NULL, l, rl, &lci, 0, false, false,
5468 : __func__, t0);
5469 0 : return thetajoin(r1p, r2p, l, rl, sl, sr, MASK_LT, estimate, false,
5470 : __func__, t0);
5471 : }
5472 :
5473 144 : if ((maxsize = joininitresults(&r1, r2p ? &r2 : NULL, NULL, sl ? BATcount(sl) : BATcount(l), sr ? BATcount(sr) : BATcount(rl), false, false, false, false, false, false, estimate)) == BUN_NONE)
5474 : return GDK_FAIL;
5475 125 : *r1p = r1;
5476 125 : if (r2p) {
5477 106 : *r2p = r2;
5478 : }
5479 125 : if (maxsize == 0)
5480 : return GDK_SUCCEED;
5481 :
5482 125 : return rangejoin(r1, r2, l, rl, rh, &lci, &rci, linc, hinc, anti, symmetric, maxsize);
5483 : }
|
