1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9#include "monetdb_config.h"
10#include "gdk.h"
11#include "gdk_private.h"
12#include <math.h>
13
14/* auxiliary functions and structs for imprints */
15#include "gdk_imprints.h"
16
17#define buninsfix(B,A,I,V,G,M,R) \
18 do { \
19 if ((I) == BATcapacity(B)) { \
20 BATsetcount((B), (I)); \
21 if (BATextend((B), \
22 MIN(BATcapacity(B) + (G), \
23 (M))) != GDK_SUCCEED) { \
24 BBPreclaim(B); \
25 return (R); \
26 } \
27 A = (oid *) Tloc((B), 0); \
28 } \
29 A[(I)] = (V); \
30 } while (false)
31
32BAT *
33virtualize(BAT *bn)
34{
35 /* input must be a valid candidate list or NULL */
36 assert(bn == NULL ||
37 (((bn->ttype == TYPE_void && !is_oid_nil(bn->tseqbase)) ||
38 bn->ttype == TYPE_oid) &&
39 bn->tkey && bn->tsorted));
40 /* since bn has unique and strictly ascending values, we can
41 * easily check whether the column is dense */
42 if (bn && bn->ttype == TYPE_oid &&
43 (BATcount(bn) <= 1 ||
44 * (const oid *) Tloc(bn, 0) + BATcount(bn) - 1 ==
45 * (const oid *) Tloc(bn, BUNlast(bn) - 1))) {
46 /* column is dense, replace by virtual oid */
47 ALGODEBUG fprintf(stderr, "#%s: %s(bn=" ALGOBATFMT ",seq="OIDFMT")\n",
48 MT_thread_getname(), __func__,
49 ALGOBATPAR(bn),
50 BATcount(bn) > 0 ? * (const oid *) Tloc(bn, 0) : 0);
51 if (BATcount(bn) == 0)
52 bn->tseqbase = 0;
53 else
54 bn->tseqbase = * (const oid *) Tloc(bn, 0);
55 if (VIEWtparent(bn)) {
56 BBPunshare(VIEWtparent(bn));
57 BBPunfix(VIEWtparent(bn));
58 bn->theap.parentid = 0;
59 bn->theap.base = NULL;
60 } else {
61 HEAPfree(&bn->theap, true);
62 }
63 bn->theap.storage = bn->theap.newstorage = STORE_MEM;
64 bn->theap.size = 0;
65 bn->ttype = TYPE_void;
66 bn->tvarsized = true;
67 bn->twidth = 0;
68 bn->tshift = 0;
69 }
70
71 return bn;
72}
73
74#define HASHloop_bound(bi, h, hb, v, lo, hi) \
75 for (hb = HASHget(h, HASHprobe((h), v)); \
76 hb != HASHnil(h); \
77 hb = HASHgetlink(h,hb)) \
78 if (hb >= (lo) && hb < (hi) && \
79 (cmp == NULL || \
80 (*cmp)(v, BUNtail(bi, hb)) == 0))
81
82static BAT *
83hashselect(BAT *b, struct canditer *restrict ci, BAT *bn,
84 const void *tl, BUN maximum, bool phash, const char **algo)
85{
86 BATiter bi;
87 BUN i, cnt;
88 oid o, *restrict dst;
89 BUN l, h, d = 0;
90 oid seq;
91 int (*cmp)(const void *, const void *);
92
93 assert(bn->ttype == TYPE_oid);
94 seq = b->hseqbase;
95 l = ci->seq - seq;
96 h = canditer_last(ci) + 1 - seq;
97
98 *algo = "hashselect";
99 if (phash) {
100 BAT *b2 = BBPdescriptor(VIEWtparent(b));
101 *algo = "hashselect on parent";
102 ALGODEBUG fprintf(stderr, "#%s: %s(" ALGOBATFMT "): "
103 "using parent(" ALGOBATFMT ") "
104 "for hash\n",
105 MT_thread_getname(), __func__,
106 ALGOBATPAR(b),
107 ALGOBATPAR(b2));
108 d = (BUN) ((b->theap.base - b2->theap.base) >> b->tshift);
109 l += d;
110 h += d;
111 b = b2;
112 }
113
114 if (BAThash(b) != GDK_SUCCEED) {
115 BBPreclaim(bn);
116 return NULL;
117 }
118 switch (ATOMbasetype(b->ttype)) {
119 case TYPE_bte:
120 case TYPE_sht:
121 cmp = NULL; /* no need to compare: "hash" is perfect */
122 break;
123 default:
124 cmp = ATOMcompare(b->ttype);
125 break;
126 }
127 bi = bat_iterator(b);
128 dst = (oid *) Tloc(bn, 0);
129 cnt = 0;
130 if (ci->tpe != cand_dense) {
131 HASHloop_bound(bi, b->thash, i, tl, l, h) {
132 o = (oid) (i + seq - d);
133 if (canditer_search(ci, o, false) != BUN_NONE) {
134 buninsfix(bn, dst, cnt, o,
135 maximum - BATcapacity(bn),
136 maximum, NULL);
137 cnt++;
138 }
139 }
140 } else {
141 HASHloop_bound(bi, b->thash, i, tl, l, h) {
142 o = (oid) (i + seq - d);
143 buninsfix(bn, dst, cnt, o,
144 maximum - BATcapacity(bn),
145 maximum, NULL);
146 cnt++;
147 }
148 }
149 BATsetcount(bn, cnt);
150 bn->tkey = true;
151 if (cnt > 1) {
152 /* hash chains produce results in the order high to
153 * low, so we just need to reverse */
154 for (l = 0, h = BUNlast(bn) - 1; l < h; l++, h--) {
155 o = dst[l];
156 dst[l] = dst[h];
157 dst[h] = o;
158 }
159 }
160 bn->tsorted = true;
161 bn->trevsorted = bn->batCount <= 1;
162 bn->tseqbase = bn->batCount == 0 ? 0 : bn->batCount == 1 ? *dst : oid_nil;
163 return bn;
164}
165
166/* Imprints select code */
167
168/* inner check */
169#define impscheck(canditer_next,TEST,ADD) \
170 do { \
171 const oid e = (oid) (i+limit-pr_off+hseq); \
172 if (im[icnt] & mask) { \
173 if ((im[icnt] & ~innermask) == 0) { \
174 while (p < ci->ncand && o < e) { \
175 v = src[o-hseq]; \
176 ADD; \
177 cnt++; \
178 p++; \
179 o = canditer_next(ci); \
180 } \
181 } else { \
182 while (p < ci->ncand && o < e) { \
183 v = src[o-hseq]; \
184 ADD; \
185 cnt += (TEST) != 0; \
186 p++; \
187 o = canditer_next(ci); \
188 } \
189 } \
190 } else { \
191 while (p < ci->ncand && o < e) { \
192 p++; \
193 o = canditer_next(ci); \
194 } \
195 } \
196 } while (false)
197
198/* main loop for imprints */
199/*
200 * icnt is the iterator for imprints
201 * dcnt is the iterator for dictionary entries
202 * i is the iterator for the values in imprints
203 */
204#define impsloop(canditer_next,TEST,ADD) \
205 do { \
206 BUN dcnt, icnt, limit, i; \
207 const cchdc_t *restrict d = (cchdc_t *) imprints->dict; \
208 const uint8_t rpp = ATOMelmshift(IMPS_PAGE >> b->tshift); \
209 o = canditer_next(ci); \
210 for (i = 0, dcnt = 0, icnt = 0, p = 0; \
211 dcnt < imprints->dictcnt && i <= w - hseq + pr_off && p < ci->ncand; \
212 dcnt++) { \
213 limit = ((BUN) d[dcnt].cnt) << rpp; \
214 while (i + limit <= o - hseq + pr_off) { \
215 i += limit; \
216 icnt += d[dcnt].repeat ? 1 : d[dcnt].cnt; \
217 dcnt++; \
218 limit = ((BUN) d[dcnt].cnt) << rpp; \
219 } \
220 if (!d[dcnt].repeat) { \
221 const BUN l = icnt + d[dcnt].cnt; \
222 limit = (BUN) 1 << rpp; \
223 while (i + limit <= o - hseq + pr_off) { \
224 icnt++; \
225 i += limit; \
226 } \
227 for (; \
228 icnt < l && i <= w - hseq + pr_off; \
229 icnt++) { \
230 impscheck(canditer_next,TEST,ADD); \
231 i += limit; \
232 } \
233 } \
234 else { \
235 impscheck(canditer_next,TEST,ADD); \
236 i += limit; \
237 icnt++; \
238 } \
239 } \
240 } while (false)
241
242#define quickins(dst, cnt, o, bn) \
243 do { \
244 assert((cnt) < BATcapacity(bn)); \
245 dst[cnt] = (o); \
246 } while (false)
247
248/* construct the mask */
249#define impsmask(canditer_next,TEST,B) \
250 do { \
251 const uint##B##_t *restrict im = (uint##B##_t *) imprints->imps; \
252 uint##B##_t mask = 0, innermask; \
253 const int tpe = ATOMbasetype(b->ttype); \
254 const int lbin = IMPSgetbin(tpe, imprints->bits, imprints->bins, tl); \
255 const int hbin = IMPSgetbin(tpe, imprints->bits, imprints->bins, th); \
256 /* note: (1<<n)-1 gives a sequence of n one bits */ \
257 /* to set bits hbin..lbin inclusive, we would do: */ \
258 /* mask = ((1 << (hbin + 1)) - 1) - ((1 << lbin) - 1); */ \
259 /* except ((1 << (hbin + 1)) - 1) is not defined if */ \
260 /* hbin == sizeof(uint##B##_t)*8 - 1 */ \
261 /* the following does work, however */ \
262 mask = (((((uint##B##_t) 1 << hbin) - 1) << 1) | 1) - (((uint##B##_t) 1 << lbin) - 1); \
263 innermask = mask; \
264 if (vl != minval) \
265 innermask = IMPSunsetBit(B, innermask, lbin); \
266 if (vh != maxval) \
267 innermask = IMPSunsetBit(B, innermask, hbin); \
268 if (anti) { \
269 uint##B##_t tmp = mask; \
270 mask = ~innermask; \
271 innermask = ~tmp; \
272 } \
273 /* if there are nils, we may need to check bin 0 */ \
274 if (!b->tnonil) \
275 innermask = IMPSunsetBit(B, innermask, 0); \
276 \
277 if (BATcapacity(bn) < maximum) { \
278 impsloop(canditer_next, TEST, \
279 buninsfix(bn, dst, cnt, o, \
280 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p) \
281 * (dbl) (ci->ncand-p) * 1.1 + 1024), \
282 BATcapacity(bn) + ci->ncand - p, BUN_NONE)); \
283 } else { \
284 impsloop(canditer_next, TEST, quickins(dst, cnt, o, bn)); \
285 } \
286 } while (false)
287
288#define checkMINMAX(B, TYPE) \
289 do { \
290 const BUN *restrict imp_cnt = imprints->stats + 128; \
291 imp_min = imp_max = nil; \
292 for (BUN ii = 0; ii < B; ii++) { \
293 if (is_##TYPE##_nil(imp_min) && imp_cnt[ii]) { \
294 imp_min = basesrc[imprints->stats[ii]]; \
295 } \
296 if (is_##TYPE##_nil(imp_max) && imp_cnt[B-1-ii]) { \
297 imp_max = basesrc[imprints->stats[64+B-1-ii]]; \
298 } \
299 } \
300 assert(!is_##TYPE##_nil(imp_min) && \
301 !is_##TYPE##_nil(imp_max)); \
302 if (anti ? \
303 vl < imp_min && vh > imp_max : \
304 vl > imp_max || vh < imp_min) { \
305 return 0; \
306 } \
307 } while (false)
308
309/* choose number of bits */
310#define bitswitch(canditer_next, TEST, TYPE) \
311 do { \
312 assert(imprints); \
313 *algo = "imprints select " #TEST " (" #canditer_next ")"; \
314 switch (imprints->bits) { \
315 case 8: checkMINMAX(8, TYPE); impsmask(canditer_next,TEST,8); break; \
316 case 16: checkMINMAX(16, TYPE); impsmask(canditer_next,TEST,16); break; \
317 case 32: checkMINMAX(32, TYPE); impsmask(canditer_next,TEST,32); break; \
318 case 64: checkMINMAX(64, TYPE); impsmask(canditer_next,TEST,64); break; \
319 default: assert(0); break; \
320 } \
321 } while (false)
322
323/* scan select without imprints */
324
325/* core scan select loop with & without candidates */
326#define scanloop(NAME,canditer_next,TEST) \
327 do { \
328 *algo = #NAME " " #TEST " (" #canditer_next ")"; \
329 if (BATcapacity(bn) < maximum) { \
330 for (p = 0; p < ci->ncand; p++) { \
331 o = canditer_next(ci); \
332 v = src[o-hseq]; \
333 if (TEST) { \
334 buninsfix(bn, dst, cnt, o, \
335 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p) \
336 * (dbl) (ci->ncand-p) * 1.1 + 1024), \
337 BATcapacity(bn) + ci->ncand - p, BUN_NONE); \
338 cnt++; \
339 } \
340 } \
341 } else { \
342 for (p = 0; p < ci->ncand; p++) { \
343 o = canditer_next(ci); \
344 v = src[o-hseq]; \
345 assert(cnt < BATcapacity(bn)); \
346 dst[cnt] = o; \
347 cnt += (TEST) != 0; \
348 } \
349 } \
350 } while (false)
351
352/* argument list for type-specific core scan select function call */
353#define scanargs \
354 b, ci, bn, tl, th, li, hi, equi, anti, lval, hval, lnil, \
355 cnt, b->hseqbase, dst, maximum, use_imprints, algo
356
357#define PREVVALUEbte(x) ((x) - 1)
358#define PREVVALUEsht(x) ((x) - 1)
359#define PREVVALUEint(x) ((x) - 1)
360#define PREVVALUElng(x) ((x) - 1)
361#ifdef HAVE_HGE
362#define PREVVALUEhge(x) ((x) - 1)
363#endif
364#define PREVVALUEoid(x) ((x) - 1)
365#define PREVVALUEflt(x) nextafterf((x), -GDK_flt_max)
366#define PREVVALUEdbl(x) nextafter((x), -GDK_dbl_max)
367
368#define NEXTVALUEbte(x) ((x) + 1)
369#define NEXTVALUEsht(x) ((x) + 1)
370#define NEXTVALUEint(x) ((x) + 1)
371#define NEXTVALUElng(x) ((x) + 1)
372#ifdef HAVE_HGE
373#define NEXTVALUEhge(x) ((x) + 1)
374#endif
375#define NEXTVALUEoid(x) ((x) + 1)
376#define NEXTVALUEflt(x) nextafterf((x), GDK_flt_max)
377#define NEXTVALUEdbl(x) nextafter((x), GDK_dbl_max)
378
379#define MINVALUEbte GDK_bte_min
380#define MINVALUEsht GDK_sht_min
381#define MINVALUEint GDK_int_min
382#define MINVALUElng GDK_lng_min
383#ifdef HAVE_HGE
384#define MINVALUEhge GDK_hge_min
385#endif
386#define MINVALUEoid GDK_oid_min
387#define MINVALUEflt GDK_flt_min
388#define MINVALUEdbl GDK_dbl_min
389
390#define MAXVALUEbte GDK_bte_max
391#define MAXVALUEsht GDK_sht_max
392#define MAXVALUEint GDK_int_max
393#define MAXVALUElng GDK_lng_max
394#ifdef HAVE_HGE
395#define MAXVALUEhge GDK_hge_max
396#endif
397#define MAXVALUEoid GDK_oid_max
398#define MAXVALUEflt GDK_flt_max
399#define MAXVALUEdbl GDK_dbl_max
400
401#define choose(NAME, canditer_next, TEST, TYPE) \
402 do { \
403 if (use_imprints) { \
404 bitswitch(canditer_next, TEST, TYPE); \
405 } else { \
406 scanloop(NAME, canditer_next, TEST); \
407 } \
408 } while (false)
409
410/* definition of type-specific core scan select function */
411#define scanfunc(NAME, TYPE, canditer_next) \
412static BUN \
413NAME##_##TYPE(BAT *b, struct canditer *restrict ci, BAT *bn, \
414 const TYPE *tl, const TYPE *th, bool li, bool hi, \
415 bool equi, bool anti, bool lval, bool hval, \
416 bool lnil, BUN cnt, const oid hseq, oid *restrict dst, \
417 BUN maximum, bool use_imprints, const char **algo) \
418{ \
419 TYPE vl = *tl; \
420 TYPE vh = *th; \
421 TYPE imp_min; \
422 TYPE imp_max; \
423 TYPE v; \
424 const TYPE nil = TYPE##_nil; \
425 const TYPE minval = MINVALUE##TYPE; \
426 const TYPE maxval = MAXVALUE##TYPE; \
427 const TYPE *src = (const TYPE *) Tloc(b, 0); \
428 const TYPE *basesrc; \
429 oid o, w; \
430 BUN p; \
431 BUN pr_off = 0; \
432 Imprints *imprints; \
433 (void) li; \
434 (void) hi; \
435 (void) lval; \
436 (void) hval; \
437 assert(li == !anti); \
438 assert(hi == !anti); \
439 assert(lval); \
440 assert(hval); \
441 if (use_imprints && VIEWtparent(b)) { \
442 BAT *parent = BBPdescriptor(VIEWtparent(b)); \
443 assert(parent); \
444 basesrc = (const TYPE *) Tloc(parent, 0); \
445 imprints = parent->timprints; \
446 pr_off = (BUN) (src - basesrc); \
447 } else { \
448 imprints = b->timprints; \
449 basesrc = src; \
450 } \
451 w = canditer_last(ci); \
452 if (equi) { \
453 assert(!use_imprints); \
454 if (lnil) \
455 scanloop(NAME, canditer_next, is_##TYPE##_nil(v)); \
456 else \
457 scanloop(NAME, canditer_next, v == vl); \
458 } else if (anti) { \
459 if (b->tnonil) { \
460 choose(NAME, canditer_next, (v <= vl || v >= vh), TYPE); \
461 } else { \
462 choose(NAME, canditer_next, !is_##TYPE##_nil(v) && (v <= vl || v >= vh), TYPE); \
463 } \
464 } else if (b->tnonil && vl == minval) { \
465 choose(NAME, canditer_next, v <= vh, TYPE); \
466 } else if (vh == maxval) { \
467 choose(NAME, canditer_next, v >= vl, TYPE); \
468 } else { \
469 choose(NAME, canditer_next, v >= vl && v <= vh, TYPE); \
470 } \
471 return cnt; \
472}
473
474static BUN
475fullscan_any(BAT *b, struct canditer *restrict ci, BAT *bn,
476 const void *tl, const void *th,
477 bool li, bool hi, bool equi, bool anti, bool lval, bool hval,
478 bool lnil, BUN cnt, const oid hseq, oid *restrict dst,
479 BUN maximum, bool use_imprints, const char **algo)
480{
481 const void *v;
482 const void *restrict nil = ATOMnilptr(b->ttype);
483 int (*cmp)(const void *, const void *) = ATOMcompare(b->ttype);
484 BATiter bi = bat_iterator(b);
485 oid o;
486 BUN p;
487 int c;
488
489 (void) maximum;
490 (void) use_imprints;
491 (void) lnil;
492
493 if (equi) {
494 *algo = "fullscan equi";
495 for (p = 0; p < ci->ncand; p++) {
496 o = canditer_next(ci);
497 v = BUNtail(bi,(BUN)(o-hseq));
498 if ((*cmp)(tl, v) == 0) {
499 buninsfix(bn, dst, cnt, o,
500 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
501 * (dbl) (ci->ncand-p) * 1.1 + 1024),
502 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
503 cnt++;
504 }
505 }
506 } else if (anti) {
507 *algo = "fullscan anti";
508 for (p = 0; p < ci->ncand; p++) {
509 o = canditer_next(ci);
510 v = BUNtail(bi,(BUN)(o-hseq));
511 if ((nil == NULL || (*cmp)(v, nil) != 0) &&
512 ((lval &&
513 ((c = (*cmp)(tl, v)) > 0 ||
514 (!li && c == 0))) ||
515 (hval &&
516 ((c = (*cmp)(th, v)) < 0 ||
517 (!hi && c == 0))))) {
518 buninsfix(bn, dst, cnt, o,
519 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
520 * (dbl) (ci->ncand-p) * 1.1 + 1024),
521 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
522 cnt++;
523 }
524 }
525 } else {
526 *algo = "fullscan range";
527 for (p = 0; p < ci->ncand; p++) {
528 o = canditer_next(ci);
529 v = BUNtail(bi,(BUN)(o-hseq));
530 if ((nil == NULL || (*cmp)(v, nil) != 0) &&
531 ((!lval ||
532 (c = cmp(tl, v)) < 0 ||
533 (li && c == 0)) &&
534 (!hval ||
535 (c = cmp(th, v)) > 0 ||
536 (hi && c == 0)))) {
537 buninsfix(bn, dst, cnt, o,
538 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
539 * (dbl) (ci->ncand-p) * 1.1 + 1024),
540 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
541 cnt++;
542 }
543 }
544 }
545 return cnt;
546}
547
548static BUN
549fullscan_str(BAT *b, struct canditer *restrict ci, BAT *bn,
550 const char *tl, const char *th,
551 bool li, bool hi, bool equi, bool anti, bool lval, bool hval,
552 bool lnil, BUN cnt, const oid hseq, oid *restrict dst,
553 BUN maximum, bool use_imprints, const char **algo)
554{
555 var_t pos;
556 BUN p;
557 oid o;
558
559 if (!equi || !GDK_ELIMDOUBLES(b->tvheap))
560 return fullscan_any(b, ci, bn, tl, th, li, hi, equi, anti,
561 lval, hval, lnil, cnt, hseq, dst,
562 maximum, use_imprints, algo);
563 if ((pos = strLocate(b->tvheap, tl)) == 0) {
564 *algo = "fullscan equi strelim (nomatch)";
565 return 0;
566 }
567 *algo = "fullscan equi strelim";
568 assert(pos >= GDK_VAROFFSET);
569 switch (b->twidth) {
570 case 1: {
571 const unsigned char *ptr = (const unsigned char *) Tloc(b, 0);
572 pos -= GDK_VAROFFSET;
573 for (p = 0; p < ci->ncand; p++) {
574 o = canditer_next(ci);
575 if (ptr[o - hseq] == pos) {
576 buninsfix(bn, dst, cnt, o,
577 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
578 * (dbl) (ci->ncand-p) * 1.1 + 1024),
579 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
580 cnt++;
581 }
582 }
583 break;
584 }
585 case 2: {
586 const unsigned short *ptr = (const unsigned short *) Tloc(b, 0);
587 pos -= GDK_VAROFFSET;
588 for (p = 0; p < ci->ncand; p++) {
589 o = canditer_next(ci);
590 if (ptr[o - hseq] == pos) {
591 buninsfix(bn, dst, cnt, o,
592 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
593 * (dbl) (ci->ncand-p) * 1.1 + 1024),
594 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
595 cnt++;
596 }
597 }
598 break;
599 }
600#if SIZEOF_VAR_T == 8
601 case 4: {
602 const unsigned int *ptr = (const unsigned int *) Tloc(b, 0);
603 for (p = 0; p < ci->ncand; p++) {
604 o = canditer_next(ci);
605 if (ptr[o - hseq] == pos) {
606 buninsfix(bn, dst, cnt, o,
607 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
608 * (dbl) (ci->ncand-p) * 1.1 + 1024),
609 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
610 cnt++;
611 }
612 }
613 break;
614 }
615#endif
616 default: {
617 const var_t *ptr = (const var_t *) Tloc(b, 0);
618 for (p = 0; p < ci->ncand; p++) {
619 o = canditer_next(ci);
620 if (ptr[o - hseq] == pos) {
621 buninsfix(bn, dst, cnt, o,
622 (BUN) ((dbl) cnt / (dbl) (p == 0 ? 1 : p)
623 * (dbl) (ci->ncand-p) * 1.1 + 1024),
624 BATcapacity(bn) + ci->ncand - p, BUN_NONE);
625 cnt++;
626 }
627 }
628 break;
629 }
630 }
631 return cnt;
632}
633
634/* scan select type switch */
635#ifdef HAVE_HGE
636#define scanfunc_hge(NAME, canditer_next) \
637 scanfunc(NAME, hge, canditer_next)
638#else
639#define scanfunc_hge(NAME, canditer_next)
640#endif
641#define scan_sel(NAME, canditer_next) \
642 scanfunc(NAME, bte, canditer_next) \
643 scanfunc(NAME, sht, canditer_next) \
644 scanfunc(NAME, int, canditer_next) \
645 scanfunc(NAME, flt, canditer_next) \
646 scanfunc(NAME, dbl, canditer_next) \
647 scanfunc(NAME, lng, canditer_next) \
648 scanfunc_hge(NAME, canditer_next)
649
650/* scan/imprints select */
651scan_sel(fullscan, canditer_next)
652scan_sel(densescan, canditer_next_dense)
653
654
655static BAT *
656scanselect(BAT *b, struct canditer *restrict ci, BAT *bn,
657 const void *tl, const void *th,
658 bool li, bool hi, bool equi, bool anti, bool lval, bool hval,
659 bool lnil, BUN maximum, bool use_imprints, const char **algo)
660{
661#ifndef NDEBUG
662 int (*cmp)(const void *, const void *);
663#endif
664 int t;
665 BUN cnt = 0;
666 oid *restrict dst;
667
668 assert(b != NULL);
669 assert(bn != NULL);
670 assert(bn->ttype == TYPE_oid);
671 assert(!lval || tl != NULL);
672 assert(!hval || th != NULL);
673 assert(!equi || (li && hi && !anti));
674 assert(!anti || lval || hval);
675 assert( anti || lval || hval || !b->tnonil);
676 assert(b->ttype != TYPE_void || equi || b->tnonil);
677
678#ifndef NDEBUG
679 cmp = ATOMcompare(b->ttype);
680#endif
681
682 assert(!lval || !hval || (*cmp)(tl, th) <= 0);
683
684 /* build imprints if they do not exist */
685 if (use_imprints && (BATimprints(b) != GDK_SUCCEED)) {
686 GDKclrerr(); /* not interested in BATimprints errors */
687 use_imprints = false;
688 }
689
690 dst = (oid *) Tloc(bn, 0);
691
692 t = ATOMbasetype(b->ttype);
693
694 /* call type-specific core scan select function */
695 switch (t) {
696 case TYPE_bte:
697 if (ci->tpe == cand_dense)
698 cnt = densescan_bte(scanargs);
699 else
700 cnt = fullscan_bte(scanargs);
701 break;
702 case TYPE_sht:
703 if (ci->tpe == cand_dense)
704 cnt = densescan_sht(scanargs);
705 else
706 cnt = fullscan_sht(scanargs);
707 break;
708 case TYPE_int:
709 if (ci->tpe == cand_dense)
710 cnt = densescan_int(scanargs);
711 else
712 cnt = fullscan_int(scanargs);
713 break;
714 case TYPE_flt:
715 if (ci->tpe == cand_dense)
716 cnt = densescan_flt(scanargs);
717 else
718 cnt = fullscan_flt(scanargs);
719 break;
720 case TYPE_dbl:
721 if (ci->tpe == cand_dense)
722 cnt = densescan_dbl(scanargs);
723 else
724 cnt = fullscan_dbl(scanargs);
725 break;
726 case TYPE_lng:
727 if (ci->tpe == cand_dense)
728 cnt = densescan_lng(scanargs);
729 else
730 cnt = fullscan_lng(scanargs);
731 break;
732#ifdef HAVE_HGE
733 case TYPE_hge:
734 if (ci->tpe == cand_dense)
735 cnt = densescan_hge(scanargs);
736 else
737 cnt = fullscan_hge(scanargs);
738 break;
739#endif
740 case TYPE_str:
741 cnt = fullscan_str(scanargs);
742 break;
743 default:
744 cnt = fullscan_any(scanargs);
745 break;
746 }
747 if (cnt == BUN_NONE) {
748 return NULL;
749 }
750 assert(bn->batCapacity >= cnt);
751
752 BATsetcount(bn, cnt);
753 bn->tsorted = true;
754 bn->trevsorted = bn->batCount <= 1;
755 bn->tkey = true;
756 bn->tseqbase = cnt == 0 ? 0 : cnt == 1 || cnt == b->batCount ? b->hseqbase : oid_nil;
757
758 return bn;
759}
760
761/* calculate the integer 2 logarithm (i.e. position of highest set
762 * bit) of the argument (with a slight twist: 0 gives 0, 1 gives 1,
763 * 0x8 to 0xF give 4, etc.) */
764static unsigned
765ilog2(BUN x)
766{
767 unsigned n = 0;
768 BUN y;
769
770 /* use a "binary search" method */
771#if SIZEOF_BUN == 8
772 if ((y = x >> 32) != 0) {
773 x = y;
774 n += 32;
775 }
776#endif
777 if ((y = x >> 16) != 0) {
778 x = y;
779 n += 16;
780 }
781 if ((y = x >> 8) != 0) {
782 x = y;
783 n += 8;
784 }
785 if ((y = x >> 4) != 0) {
786 x = y;
787 n += 4;
788 }
789 if ((y = x >> 2) != 0) {
790 x = y;
791 n += 2;
792 }
793 if ((y = x >> 1) != 0) {
794 x = y;
795 n += 1;
796 }
797 return n + (x != 0);
798}
799
800/* Normalize the variables li, hi, lval, hval, possibly changing anti
801 * in the process. This works for all (and only) numeric types.
802 *
803 * Note that the expression x < v is equivalent to x <= v' where v' is
804 * the next smaller value in the domain of v (similarly for x > v).
805 * Also note that for floating point numbers there actually is such a
806 * value. In fact, there is a function in standard C that calculates
807 * that value.
808 *
809 * The result of this macro is:
810 * li == !anti, hi == !anti, lval == true, hval == true
811 * This means that all ranges that we check for are closed ranges. If
812 * a range is one-sided, we fill in the minimum resp. maximum value in
813 * the domain so that we create a closed range. */
814#define NORMALIZE(TYPE) \
815 do { \
816 if (anti && li) { \
817 /* -inf < x < vl === -inf < x <= vl-1 */ \
818 if (*(TYPE*)tl == MINVALUE##TYPE) { \
819 /* -inf < x < MIN || *th <[=] x < +inf */ \
820 /* degenerates into half range */ \
821 /* *th <[=] x < +inf */ \
822 anti = false; \
823 tl = th; \
824 li = !hi; \
825 hval = false; \
826 /* further dealt with below */ \
827 } else { \
828 vl.v_##TYPE = PREVVALUE##TYPE(*(TYPE*)tl); \
829 tl = &vl.v_##TYPE; \
830 li = false; \
831 } \
832 } \
833 if (anti && hi) { \
834 /* vl < x < +inf === vl+1 <= x < +inf */ \
835 if (*(TYPE*)th == MAXVALUE##TYPE) { \
836 /* -inf < x <[=] *tl || MAX > x > +inf */ \
837 /* degenerates into half range */ \
838 /* -inf < x <[=] *tl */ \
839 anti = false; \
840 th = tl; \
841 hi = !li; \
842 lval = false; \
843 /* further dealt with below */ \
844 } else { \
845 vh.v_##TYPE = NEXTVALUE##TYPE(*(TYPE*)th); \
846 th = &vh.v_##TYPE; \
847 hi = false; \
848 } \
849 } \
850 if (!anti) { \
851 if (lval) { \
852 /* range bounded on left */ \
853 if (!li) { \
854 /* open range on left */ \
855 if (*(TYPE*)tl == MAXVALUE##TYPE) \
856 return BATdense(0, 0, 0); \
857 /* vl < x === vl+1 <= x */ \
858 vl.v_##TYPE = NEXTVALUE##TYPE(*(TYPE*)tl); \
859 li = true; \
860 tl = &vl.v_##TYPE; \
861 } \
862 } else { \
863 /* -inf, i.e. smallest value */ \
864 vl.v_##TYPE = MINVALUE##TYPE; \
865 li = true; \
866 tl = &vl.v_##TYPE; \
867 lval = true; \
868 } \
869 if (hval) { \
870 /* range bounded on right */ \
871 if (!hi) { \
872 /* open range on right */ \
873 if (*(TYPE*)th == MINVALUE##TYPE) \
874 return BATdense(0, 0, 0); \
875 /* x < vh === x <= vh-1 */ \
876 vh.v_##TYPE = PREVVALUE##TYPE(*(TYPE*)th); \
877 hi = true; \
878 th = &vh.v_##TYPE; \
879 } \
880 } else { \
881 /* +inf, i.e. largest value */ \
882 vh.v_##TYPE = MAXVALUE##TYPE; \
883 hi = true; \
884 th = &vh.v_##TYPE; \
885 hval = true; \
886 } \
887 if (*(TYPE*)tl > *(TYPE*)th) \
888 return BATdense(0, 0, 0); \
889 } \
890 assert(lval); \
891 assert(hval); \
892 assert(li != anti); \
893 assert(hi != anti); \
894 /* if anti is set, we can now check */ \
895 /* (x <= *tl || x >= *th) && x != nil */ \
896 /* if equi==true, the check is x != *tl && x != nil */ \
897 /* if anti is not set, we can check just */ \
898 /* *tl <= x && x <= *th */ \
899 /* if equi==true, the check is x == *tl */ \
900 /* note that this includes the check for != nil */ \
901 /* in the case where equi==true, the check is x == *tl */ \
902 } while (false)
903
904/* generic range select
905 *
906 * Return a BAT with the OID values of b for qualifying tuples. The
907 * return BAT is sorted (i.e. in the same order as the input BAT).
908 *
909 * If s is non-NULL, it is a list of candidates. s must be sorted.
910 *
911 * tl may not be NULL, li, hi, and anti must be either 0 or 1.
912 *
913 * If th is NULL, hi is ignored.
914 *
915 * If anti is 0, qualifying tuples are those whose value is between tl
916 * and th (as in x >[=] tl && x <[=] th, where equality depends on li
917 * and hi--so if tl > th, nothing will be returned). If li or hi is
918 * 1, the respective boundary is inclusive, otherwise exclusive. If
919 * th is NULL it is taken to be equal to tl, turning this into an
920 * equi- or point-select. Note that for a point select to return
921 * anything, li (and hi if th was not NULL) must be 1. There is a
922 * special case if tl is nil and th is NULL. This is the only way to
923 * select for nil values.
924 *
925 * If anti is 1, the result is the complement of what the result would
926 * be if anti were 0, except that nils are filtered out.
927 *
928 * In brief:
929 * - if tl==nil and th==NULL and anti==0, return all nils (only way to
930 * get nils);
931 * - it tl==nil and th==nil, return all but nils;
932 * - if tl==nil and th!=NULL, no lower bound;
933 * - if th==NULL or tl==th, point (equi) select;
934 * - if th==nil, no upper bound
935 *
936 * A complete breakdown of the various arguments follows. Here, v, v1
937 * and v2 are values from the appropriate domain, and
938 * v != nil, v1 != nil, v2 != nil, v1 < v2.
939 * tl th li hi anti result list of OIDs for values
940 * -----------------------------------------------------------------
941 * nil NULL true ignored false x == nil (only way to get nil)
942 * nil NULL false ignored false NOTHING
943 * nil NULL ignored ignored true x != nil
944 * nil nil ignored ignored false x != nil
945 * nil nil ignored ignored true NOTHING
946 * nil v ignored false false x < v
947 * nil v ignored true false x <= v
948 * nil v ignored false true x >= v
949 * nil v ignored true true x > v
950 * v nil false ignored false x > v
951 * v nil true ignored false x >= v
952 * v nil false ignored true x <= v
953 * v nil true ignored true x < v
954 * v NULL false ignored false NOTHING
955 * v NULL true ignored false x == v
956 * v NULL false ignored true x != nil
957 * v NULL true ignored true x != v
958 * v v false false false NOTHING
959 * v v true false false NOTHING
960 * v v false true false NOTHING
961 * v v true true false x == v
962 * v v false false true x != nil
963 * v v true false true x != nil
964 * v v false true true x != nil
965 * v v true true true x != v
966 * v1 v2 false false false v1 < x < v2
967 * v1 v2 true false false v1 <= x < v2
968 * v1 v2 false true false v1 < x <= v2
969 * v1 v2 true true false v1 <= x <= v2
970 * v1 v2 false false true x <= v1 or x >= v2
971 * v1 v2 true false true x < v1 or x >= v2
972 * v1 v2 false true true x <= v1 or x > v2
973 * v1 v2 true true true x < v1 or x > v2
974 * v2 v1 ignored ignored false NOTHING
975 * v2 v1 ignored ignored true x != nil
976 */
977BAT *
978BATselect(BAT *b, BAT *s, const void *tl, const void *th,
979 bool li, bool hi, bool anti)
980{
981 bool lval; /* low value used for comparison */
982 bool lnil; /* low value is nil */
983 bool hval; /* high value used for comparison */
984 bool equi; /* select for single value (not range) */
985 bool hash; /* use hash (equi must be true) */
986 bool phash = false; /* use hash on parent BAT (if view) */
987 int t; /* data type */
988 bat parent; /* b's parent bat (if b is a view) */
989 const void *nil;
990 BAT *bn, *tmp;
991 struct canditer ci;
992 BUN estimate = BUN_NONE, maximum = BUN_NONE;
993 oid vwl = 0, vwh = 0;
994 lng vwo = 0;
995 bool use_orderidx = false;
996 const char *algo;
997 union {
998 bte v_bte;
999 sht v_sht;
1000 int v_int;
1001 lng v_lng;
1002#ifdef HAVE_HGE
1003 hge v_hge;
1004#endif
1005 flt v_flt;
1006 dbl v_dbl;
1007 oid v_oid;
1008 } vl, vh;
1009 lng t0 = 0;
1010
1011 ALGODEBUG t0 = GDKusec();
1012
1013 BATcheck(b, "BATselect", NULL);
1014 BATcheck(tl, "BATselect: tl value required", NULL);
1015
1016 if (s && !BATtordered(s)) {
1017 GDKerror("BATselect: invalid argument: "
1018 "s must be sorted.\n");
1019 return NULL;
1020 }
1021
1022 if (canditer_init(&ci, b, s) == 0) {
1023 /* trivially empty result */
1024 bn = BATdense(0, 0, 0);
1025 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1026 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1027 " (" LLFMT " usec): "
1028 "trivially empty\n",
1029 MT_thread_getname(), __func__,
1030 ALGOBATPAR(b), ALGOOPTBATPAR(s), anti,
1031 ALGOOPTBATPAR(bn), GDKusec() - t0);
1032 return bn;
1033 }
1034
1035 t = b->ttype;
1036 nil = ATOMnilptr(t);
1037 /* can we use the base type? */
1038 t = ATOMbasetype(t);
1039 lnil = ATOMcmp(t, tl, nil) == 0; /* low value = nil? */
1040
1041 if (!lnil && th != NULL && (!li || !hi) && !anti && ATOMcmp(t, tl, th) == 0) {
1042 /* upper and lower bound of range are equal and we
1043 * want an interval that's open on at least one
1044 * side */
1045 bn = BATdense(0, 0, 0);
1046 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1047 ",s=" ALGOOPTBATFMT ",li=%d,hi=%d,anti=%d)=" ALGOOPTBATFMT
1048 " (" LLFMT " usec): "
1049 "empty interval\n",
1050 MT_thread_getname(), __func__,
1051 ALGOBATPAR(b), ALGOOPTBATPAR(s),
1052 li, hi, anti, ALGOOPTBATPAR(bn), GDKusec() - t0);
1053 return bn;
1054 }
1055
1056 lval = !lnil || th == NULL; /* low value used for comparison */
1057 equi = th == NULL || (lval && ATOMcmp(t, tl, th) == 0); /* point select? */
1058 if (equi) {
1059 assert(lval);
1060 if (th == NULL)
1061 hi = li;
1062 th = tl;
1063 hval = true;
1064 } else {
1065 hval = ATOMcmp(t, th, nil) != 0;
1066 }
1067 if (anti) {
1068 if (lval != hval) {
1069 /* one of the end points is nil and the other
1070 * isn't: swap sub-ranges */
1071 const void *tv;
1072 bool ti;
1073 assert(!equi);
1074 ti = li;
1075 li = !hi;
1076 hi = !ti;
1077 tv = tl;
1078 tl = th;
1079 th = tv;
1080 ti = lval;
1081 lval = hval;
1082 hval = ti;
1083 lnil = ATOMcmp(t, tl, nil) == 0;
1084 anti = false;
1085 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1086 ",s=" ALGOOPTBATFMT ",anti=%d): "
1087 "anti: switch ranges...\n",
1088 MT_thread_getname(), __func__,
1089 ALGOBATPAR(b), ALGOOPTBATPAR(s),
1090 anti);
1091 } else if (!lval && !hval) {
1092 /* antiselect for nil-nil range: all non-nil
1093 * values are in range; we must return all
1094 * other non-nil values, i.e. nothing */
1095 bn = BATdense(0, 0, 0);
1096 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1097 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1098 " (" LLFMT " usec): "
1099 "anti: nil-nil range, nonil\n",
1100 MT_thread_getname(), __func__,
1101 ALGOBATPAR(b), ALGOOPTBATPAR(s),
1102 anti, ALGOOPTBATPAR(bn), GDKusec() - t0);
1103 return bn;
1104 } else if (equi && lnil) {
1105 /* antiselect for nil value: turn into range
1106 * select for nil-nil range (i.e. everything
1107 * but nil) */
1108 equi = false;
1109 anti = false;
1110 lval = false;
1111 hval = false;
1112 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1113 ",s=" ALGOOPTBATFMT ",anti=0): "
1114 "anti-nil...\n",
1115 MT_thread_getname(), __func__,
1116 ALGOBATPAR(b), ALGOOPTBATPAR(s));
1117 } else if (equi) {
1118 equi = false;
1119 if (!(li && hi)) {
1120 /* antiselect for nothing: turn into
1121 * range select for nil-nil range
1122 * (i.e. everything but nil) */
1123 anti = false;
1124 lval = false;
1125 hval = false;
1126 ALGODEBUG fprintf(stderr, "#%s: %s(b="
1127 ALGOBATFMT ",s="
1128 ALGOOPTBATFMT ",anti=0): "
1129 "anti-nothing...\n",
1130 MT_thread_getname(), __func__,
1131 ALGOBATPAR(b),
1132 ALGOOPTBATPAR(s));
1133 }
1134 } else if (ATOMcmp(t, tl, th) > 0) {
1135 /* empty range: turn into range select for
1136 * nil-nil range (i.e. everything but nil) */
1137 equi = false;
1138 anti = false;
1139 lval = false;
1140 hval = false;
1141 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1142 ",s=" ALGOOPTBATFMT ",anti=0): "
1143 "anti-nil...\n",
1144 MT_thread_getname(), __func__,
1145 ALGOBATPAR(b), ALGOOPTBATPAR(s));
1146 }
1147 }
1148
1149 /* if equi set, then so are both lval and hval */
1150 assert(!equi || (lval && hval));
1151
1152 if (hval && ((equi && !(li && hi)) || ATOMcmp(t, tl, th) > 0)) {
1153 /* empty range */
1154 bn = BATdense(0, 0, 0);
1155 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1156 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1157 " (" LLFMT " usec): "
1158 "empty range\n",
1159 MT_thread_getname(), __func__,
1160 ALGOBATPAR(b), ALGOOPTBATPAR(s), anti,
1161 ALGOOPTBATPAR(bn), GDKusec() - t0);
1162 return bn;
1163 }
1164 if (equi && lnil && b->tnonil) {
1165 /* return all nils, but there aren't any */
1166 bn = BATdense(0, 0, 0);
1167 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1168 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1169 " (" LLFMT " usec): "
1170 "equi-nil, nonil\n",
1171 MT_thread_getname(), __func__,
1172 ALGOBATPAR(b), ALGOOPTBATPAR(s), anti,
1173 ALGOOPTBATPAR(bn), GDKusec() - t0);
1174 return bn;
1175 }
1176
1177 if (!equi && !lval && !hval && lnil && b->tnonil) {
1178 /* return all non-nils from a BAT that doesn't have
1179 * any: i.e. return everything */
1180 bn = canditer_slice(&ci, 0, ci.ncand);
1181 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1182 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1183 " (" LLFMT " usec): "
1184 "everything, nonil\n",
1185 MT_thread_getname(), __func__,
1186 ALGOBATPAR(b), ALGOOPTBATPAR(s), anti,
1187 ALGOOPTBATPAR(bn), GDKusec() - t0);
1188 return bn;
1189 }
1190
1191 if (anti) {
1192 PROPrec *prop;
1193 int c;
1194
1195 if ((prop = BATgetprop(b, GDK_MIN_VALUE)) != NULL) {
1196 c = ATOMcmp(t, tl, VALptr(&prop->v));
1197 if (c < 0 || (li && c == 0)) {
1198 if ((prop = BATgetprop(b, GDK_MAX_VALUE)) != NULL) {
1199 c = ATOMcmp(t, th, VALptr(&prop->v));
1200 if (c > 0 || (hi && c == 0)) {
1201 /* tl..th range fully
1202 * inside MIN..MAX
1203 * range of values in
1204 * BAT, so nothing
1205 * left over for
1206 * anti */
1207 bn = BATdense(0, 0, 0);
1208 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT
1209 ",s=" ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1210 " (" LLFMT " usec): "
1211 "nothing, out of range\n",
1212 MT_thread_getname(), __func__,
1213 ALGOBATPAR(b), ALGOOPTBATPAR(s), anti, ALGOOPTBATPAR(bn), GDKusec() - t0);
1214 return bn;
1215 }
1216 }
1217 }
1218 }
1219 } else if (!equi || !lnil) {
1220 PROPrec *prop;
1221 int c;
1222
1223 if (hval && (prop = BATgetprop(b, GDK_MIN_VALUE)) != NULL) {
1224 c = ATOMcmp(t, th, VALptr(&prop->v));
1225 if (c < 0 || (!hi && c == 0)) {
1226 /* smallest value in BAT larger than
1227 * what we're looking for */
1228 bn = BATdense(0, 0, 0);
1229 ALGODEBUG fprintf(stderr, "#%s: %s(b="
1230 ALGOBATFMT ",s="
1231 ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1232 " (" LLFMT " usec): "
1233 "nothing, out of range\n",
1234 MT_thread_getname(), __func__,
1235 ALGOBATPAR(b),
1236 ALGOOPTBATPAR(s), anti,
1237 ALGOOPTBATPAR(bn), GDKusec() - t0);
1238 return bn;
1239 }
1240 }
1241 if (lval && (prop = BATgetprop(b, GDK_MAX_VALUE)) != NULL) {
1242 c = ATOMcmp(t, tl, VALptr(&prop->v));
1243 if (c > 0 || (!li && c == 0)) {
1244 /* largest value in BAT smaller than
1245 * what we're looking for */
1246 bn = BATdense(0, 0, 0);
1247 ALGODEBUG fprintf(stderr, "#%s: %s(b="
1248 ALGOBATFMT ",s="
1249 ALGOOPTBATFMT ",anti=%d)=" ALGOOPTBATFMT
1250 " (" LLFMT " usec): "
1251 "nothing, out of range\n",
1252 MT_thread_getname(), __func__,
1253 ALGOBATPAR(b),
1254 ALGOOPTBATPAR(s), anti,
1255 ALGOOPTBATPAR(bn), GDKusec() - t0);
1256 return bn;
1257 }
1258 }
1259 }
1260
1261 if (ATOMtype(b->ttype) == TYPE_oid) {
1262 NORMALIZE(oid);
1263 } else {
1264 switch (t) {
1265 case TYPE_bte:
1266 NORMALIZE(bte);
1267 break;
1268 case TYPE_sht:
1269 NORMALIZE(sht);
1270 break;
1271 case TYPE_int:
1272 NORMALIZE(int);
1273 break;
1274 case TYPE_lng:
1275 NORMALIZE(lng);
1276 break;
1277#ifdef HAVE_HGE
1278 case TYPE_hge:
1279 NORMALIZE(hge);
1280 break;
1281#endif
1282 case TYPE_flt:
1283 NORMALIZE(flt);
1284 break;
1285 case TYPE_dbl:
1286 NORMALIZE(dbl);
1287 break;
1288 }
1289 }
1290
1291 /* make sure tsorted and trevsorted flags are set */
1292 (void) BATordered(b);
1293 (void) BATordered_rev(b);
1294
1295 /* If there is an order index or it is a view and the parent has an ordered
1296 * index, and the bat is not tsorted or trevstorted then use the order
1297 * index.
1298 * And there is no cand list or if there is one, it is dense.
1299 * TODO: we do not support anti-select with order index */
1300 if (!anti &&
1301 !(b->tsorted || b->trevsorted) &&
1302 ci.tpe == cand_dense &&
1303 (BATcheckorderidx(b) ||
1304 (VIEWtparent(b) &&
1305 BATcheckorderidx(BBPquickdesc(VIEWtparent(b), false))))) {
1306 BAT *view = NULL;
1307 if (VIEWtparent(b) && !BATcheckorderidx(b)) {
1308 view = b;
1309 b = BBPdescriptor(VIEWtparent(b));
1310 }
1311 /* Is query selective enough to use the ordered index ? */
1312 /* TODO: Test if this heuristic works in practice */
1313 /*if ((ORDERfnd(b, th) - ORDERfnd(b, tl)) < ((BUN)1000 < b->batCount/1000 ? (BUN)1000: b->batCount/1000))*/
1314 if ((ORDERfnd(b, th) - ORDERfnd(b, tl)) < b->batCount/3) {
1315 use_orderidx = true;
1316 if (view) {
1317 vwo = (lng) ((view->theap.base - b->theap.base) >> b->tshift);
1318 vwl = b->hseqbase + (oid) vwo + ci.seq - view->hseqbase;
1319 vwh = vwl + canditer_last(&ci) - ci.seq;
1320 vwo = (lng) view->hseqbase - (lng) b->hseqbase - vwo;
1321 } else {
1322 vwl = ci.seq;
1323 vwh = canditer_last(&ci);
1324 }
1325 } else if (view) {
1326 b = view;
1327 view = NULL;
1328 }
1329 ALGODEBUG if (view) fprintf(stderr, "#%s: %s: switch from " ALGOBATFMT " to " ALGOBATFMT " " OIDFMT "-" OIDFMT " hseq " LLFMT "\n", MT_thread_getname(), __func__, ALGOBATPAR(view), ALGOBATPAR(b), vwl, vwh, vwo);
1330 }
1331
1332 if (b->tsorted || b->trevsorted || use_orderidx) {
1333 BUN low = 0;
1334 BUN high = b->batCount;
1335
1336 if (BATtdense(b)) {
1337 /* positional */
1338 /* we expect nonil to be set, in which case we
1339 * already know that we're not dealing with a
1340 * nil equiselect (dealt with above) */
1341 oid h, l;
1342 assert(b->tnonil);
1343 assert(b->tsorted);
1344 algo = "dense";
1345 h = * (oid *) th + hi;
1346 if (h > b->tseqbase)
1347 h -= b->tseqbase;
1348 else
1349 h = 0;
1350 if ((BUN) h < high)
1351 high = (BUN) h;
1352
1353 l = *(oid *) tl + !li;
1354 if (l > b->tseqbase)
1355 l -= b->tseqbase;
1356 else
1357 l = 0;
1358 if ((BUN) l > low)
1359 low = (BUN) l;
1360 if (low > high)
1361 low = high;
1362 } else if (b->tsorted) {
1363 algo = "sorted";
1364 if (lval) {
1365 if (li)
1366 low = SORTfndfirst(b, tl);
1367 else
1368 low = SORTfndlast(b, tl);
1369 } else {
1370 /* skip over nils at start of column */
1371 low = SORTfndlast(b, nil);
1372 }
1373 if (hval) {
1374 if (hi)
1375 high = SORTfndlast(b, th);
1376 else
1377 high = SORTfndfirst(b, th);
1378 }
1379 } else if (b->trevsorted) {
1380 algo = "reverse sorted";
1381 if (lval) {
1382 if (li)
1383 high = SORTfndlast(b, tl);
1384 else
1385 high = SORTfndfirst(b, tl);
1386 } else {
1387 /* skip over nils at end of column */
1388 high = SORTfndfirst(b, nil);
1389 }
1390 if (hval) {
1391 if (hi)
1392 low = SORTfndfirst(b, th);
1393 else
1394 low = SORTfndlast(b, th);
1395 }
1396 } else {
1397 assert(use_orderidx);
1398 algo = "orderidx";
1399 if (lval) {
1400 if (li)
1401 low = ORDERfndfirst(b, tl);
1402 else
1403 low = ORDERfndlast(b, tl);
1404 } else {
1405 /* skip over nils at start of column */
1406 low = ORDERfndlast(b, nil);
1407 }
1408 if (hval) {
1409 if (hi)
1410 high = ORDERfndlast(b, th);
1411 else
1412 high = ORDERfndfirst(b, th);
1413 }
1414 }
1415 if (anti) {
1416 if (b->tsorted) {
1417 BUN first = SORTfndlast(b, nil);
1418 /* match: [first..low) + [high..last) */
1419 bn = canditer_slice2(&ci,
1420 canditer_search(&ci, first + b->hseqbase, true),
1421 canditer_search(&ci, low + b->hseqbase, true),
1422 canditer_search(&ci, high + b->hseqbase, true),
1423 ci.ncand);
1424 } else {
1425 BUN last = SORTfndfirst(b, nil);
1426 /* match: [first..low) + [high..last) */
1427 bn = canditer_slice2(&ci,
1428 0,
1429 canditer_search(&ci, low + b->hseqbase, true),
1430 canditer_search(&ci, high + b->hseqbase, true),
1431 canditer_search(&ci, last + b->hseqbase, true));
1432 }
1433 } else {
1434 if (b->tsorted || b->trevsorted) {
1435 /* match: [low..high) */
1436 bn = canditer_slice(&ci,
1437 canditer_search(&ci, low + b->hseqbase, true),
1438 canditer_search(&ci, high + b->hseqbase, true));
1439 } else {
1440 BUN i;
1441 BUN cnt = 0;
1442 const oid *rs;
1443 oid *rbn;
1444
1445 rs = (const oid *) b->torderidx->base + ORDERIDXOFF;
1446 rs += low;
1447 bn = COLnew(0, TYPE_oid, high-low, TRANSIENT);
1448 if (bn == NULL)
1449 return NULL;
1450
1451 rbn = (oid *) Tloc((bn), 0);
1452
1453 for (i = low; i < high; i++) {
1454 if (vwl <= *rs && *rs <= vwh) {
1455 *rbn++ = (oid) ((lng) *rs + vwo);
1456 cnt++;
1457 }
1458 rs++;
1459 }
1460 BATsetcount(bn, cnt);
1461
1462 /* output must be sorted */
1463 GDKqsort(Tloc(bn, 0), NULL, NULL, (size_t) bn->batCount, sizeof(oid), 0, TYPE_oid, false, false);
1464 bn->tsorted = true;
1465 bn->trevsorted = bn->batCount <= 1;
1466 bn->tkey = true;
1467 bn->tseqbase = bn->batCount == 0 ? 0 : bn->batCount == 1 ? * (oid *) Tloc(bn, 0) : oid_nil;
1468 bn->tnil = false;
1469 bn->tnonil = true;
1470 if (s) {
1471 s = BATintersectcand(bn, s);
1472 BBPunfix(bn->batCacheid);
1473 bn = s;
1474 }
1475 }
1476 }
1477
1478 bn = virtualize(bn);
1479 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT ",anti=%s)="
1480 ALGOOPTBATFMT " %s (" LLFMT " usec)\n",
1481 MT_thread_getname(), __func__,
1482 ALGOBATPAR(b), anti ? "true" : "false",
1483 ALGOOPTBATPAR(bn), algo,
1484 GDKusec() - t0);
1485
1486 return bn;
1487 }
1488
1489 /* upper limit for result size */
1490 maximum = ci.ncand;
1491 if (b->tkey) {
1492 /* exact result size in special cases */
1493 if (equi) {
1494 estimate = 1;
1495 } else if (!anti && lval && hval) {
1496 switch (t) {
1497 case TYPE_bte:
1498 estimate = (BUN) (*(bte *) th - *(bte *) tl);
1499 break;
1500 case TYPE_sht:
1501 estimate = (BUN) (*(sht *) th - *(sht *) tl);
1502 break;
1503 case TYPE_int:
1504 estimate = (BUN) (*(int *) th - *(int *) tl);
1505 break;
1506 case TYPE_lng:
1507 estimate = (BUN) (*(lng *) th - *(lng *) tl);
1508 break;
1509#ifdef HAVE_HGE
1510 case TYPE_hge:
1511 if (*(hge *) th - *(hge *) tl < (hge) BUN_MAX)
1512 estimate = (BUN) (*(hge *) th - *(hge *) tl);
1513 break;
1514#endif
1515 }
1516 if (estimate != BUN_NONE)
1517 estimate += li + hi - 1;
1518 }
1519 }
1520 /* refine upper limit by exact size (if known) */
1521 maximum = MIN(maximum, estimate);
1522 parent = VIEWtparent(b);
1523 assert(parent >= 0);
1524 /* use hash only for equi-join, and then only if b or its
1525 * parent already has a hash, or if b or its parent is
1526 * persistent and the total size wouldn't be too large; check
1527 * for existence of hash last since that may involve I/O */
1528 hash = equi &&
1529 ((!b->batTransient &&
1530 ATOMsize(b->ttype) >= sizeof(BUN) / 4 &&
1531 BATcount(b) * (ATOMsize(b->ttype) + 2 * sizeof(BUN)) < GDK_mem_maxsize / 2) ||
1532 BATcheckhash(b));
1533 if (equi && !hash && parent != 0) {
1534 /* use parent hash if it already exists and if either
1535 * a quick check shows the value we're looking for
1536 * does not occur, or if it is cheaper to check the
1537 * candidate list for each value in the hash chain
1538 * than to scan (cost for probe is average length of
1539 * hash chain (count divided by #slots) times the cost
1540 * to do a binary search on the candidate list (or 1
1541 * if no need for search)) */
1542 tmp = BBPquickdesc(parent, false);
1543 hash = phash = BATcheckhash(tmp) &&
1544 (BATcount(tmp) == BATcount(b) ||
1545 BATcount(tmp) / ((size_t *) tmp->thash->heap.base)[5] * (ci.tpe != cand_dense ? ilog2(ci.noids) : 1) < ci.ncand ||
1546 HASHget(tmp->thash, HASHprobe(tmp->thash, tl)) == HASHnil(tmp->thash));
1547 }
1548 if (hash &&
1549 !phash && /* phash implies there is a hash table already */
1550 estimate == BUN_NONE &&
1551 !BATcheckhash(b)) {
1552 /* no exact result size, but we need estimate to
1553 * choose between hash- & scan-select (if we already
1554 * have a hash, it's a no-brainer: we use it) */
1555 if (ci.ncand <= 10000) {
1556 /* "small" input: don't bother about more accurate
1557 * estimate */
1558 estimate = maximum;
1559 } else {
1560 /* layman's quick "pseudo-sample" of 1000 tuples,
1561 * i.e., 333 from begin, middle & end of BAT */
1562 BUN smpl_cnt = 0, slct_cnt = 0, pos, skip, delta;
1563 BAT *smpl, *slct;
1564
1565 delta = 1000 / 3 / 2;
1566 skip = (BATcount(b) - (2 * delta)) / 2;
1567 for (pos = delta; pos < BATcount(b); pos += skip) {
1568 smpl = BATslice(b, pos - delta, pos + delta);
1569 if (smpl) {
1570 slct = BATselect(smpl, NULL, tl,
1571 th, li, hi, anti);
1572 if (slct) {
1573 smpl_cnt += BATcount(smpl);
1574 slct_cnt += BATcount(slct);
1575 BBPreclaim(slct);
1576 }
1577 BBPreclaim(smpl);
1578 }
1579 }
1580 if (smpl_cnt > 0 && slct_cnt > 0) {
1581 /* linear extrapolation plus 10% margin */
1582 estimate = (BUN) ((dbl) slct_cnt / (dbl) smpl_cnt
1583 * (dbl) BATcount(b) * 1.1);
1584 } else if (smpl_cnt > 0 && slct_cnt == 0) {
1585 /* estimate low enough to trigger hash select */
1586 estimate = (BATcount(b) / 100) - 1;
1587 }
1588 }
1589 hash = estimate < ci.ncand / 100;
1590 }
1591 if (estimate == BUN_NONE) {
1592 /* no better estimate possible/required:
1593 * (pre-)allocate 1M tuples, i.e., avoid/delay extend
1594 * without too much overallocation */
1595 estimate = 1000000;
1596 }
1597 /* limit estimation by upper limit */
1598 estimate = MIN(estimate, maximum);
1599
1600 bn = COLnew(0, TYPE_oid, estimate, TRANSIENT);
1601 if (bn == NULL)
1602 return NULL;
1603
1604 if (hash) {
1605 bn = hashselect(b, &ci, bn, tl, maximum, phash, &algo);
1606 } else {
1607 /* use imprints if
1608 * i) bat is persistent, or parent is persistent
1609 * ii) it is not an equi-select, and
1610 * iii) is not var-sized.
1611 */
1612 bool use_imprints = !equi &&
1613 !b->tvarsized &&
1614 (!b->batTransient ||
1615 (parent != 0 &&
1616 (tmp = BBPquickdesc(parent, false)) != NULL &&
1617 !tmp->batTransient));
1618 bn = scanselect(b, &ci, bn, tl, th, li, hi, equi, anti,
1619 lval, hval, lnil, maximum, use_imprints, &algo);
1620 }
1621
1622 bn = virtualize(bn);
1623 ALGODEBUG fprintf(stderr, "#%s: %s(b=" ALGOBATFMT ",s=" ALGOOPTBATFMT",anti=%s)=" ALGOOPTBATFMT
1624 " %s (" LLFMT " usec)\n",
1625 MT_thread_getname(), __func__,
1626 ALGOBATPAR(b), ALGOOPTBATPAR(s),
1627 anti ? "true" : "false",
1628 ALGOOPTBATPAR(bn), algo,
1629 GDKusec() - t0);
1630
1631 return bn;
1632}
1633
1634/* theta select
1635 *
1636 * Returns a BAT with the OID values of b for qualifying tuples. The
1637 * return BAT is sorted (i.e. in the same order as the input BAT).
1638 *
1639 * If s is not NULL, it is a list of candidates. s must be sorted.
1640 *
1641 * Theta select returns all values from b which are less/greater than
1642 * or (not) equal to the provided value depending on the value of op.
1643 * Op is a string with one of the values: "=", "==", "<", "<=", ">",
1644 * ">=", "<>", "!=" (the first two are equivalent and the last two are
1645 * equivalent). Theta select never returns nils.
1646 *
1647 * If value is nil, the result is empty.
1648 */
1649BAT *
1650BATthetaselect(BAT *b, BAT *s, const void *val, const char *op)
1651{
1652 const void *nil;
1653
1654 BATcheck(b, "BATthetaselect", NULL);
1655 BATcheck(val, "BATthetaselect", NULL);
1656 BATcheck(op, "BATthetaselect", NULL);
1657
1658 nil = ATOMnilptr(b->ttype);
1659 if (ATOMcmp(b->ttype, val, nil) == 0)
1660 return BATdense(0, 0, 0);
1661 if (op[0] == '=' && ((op[1] == '=' && op[2] == 0) || op[1] == 0)) {
1662 /* "=" or "==" */
1663 return BATselect(b, s, val, NULL, true, true, false);
1664 }
1665 if (op[0] == '!' && op[1] == '=' && op[2] == 0) {
1666 /* "!=" (equivalent to "<>") */
1667 return BATselect(b, s, val, NULL, true, true, true);
1668 }
1669 if (op[0] == '<') {
1670 if (op[1] == 0) {
1671 /* "<" */
1672 return BATselect(b, s, nil, val, false, false, false);
1673 }
1674 if (op[1] == '=' && op[2] == 0) {
1675 /* "<=" */
1676 return BATselect(b, s, nil, val, false, true, false);
1677 }
1678 if (op[1] == '>' && op[2] == 0) {
1679 /* "<>" (equivalent to "!=") */
1680 return BATselect(b, s, val, NULL, true, true, true);
1681 }
1682 }
1683 if (op[0] == '>') {
1684 if (op[1] == 0) {
1685 /* ">" */
1686 return BATselect(b, s, val, nil, false, false, false);
1687 }
1688 if (op[1] == '=' && op[2] == 0) {
1689 /* ">=" */
1690 return BATselect(b, s, val, nil, true, false, false);
1691 }
1692 }
1693 GDKerror("BATthetaselect: unknown operator.\n");
1694 return NULL;
1695}
1696
1697#define VALUE(s, x) (s##vars ? \
1698 s##vars + VarHeapVal(s##vals, (x), s##width) : \
1699 s##vals + ((x) * s##width))
1700#define FVALUE(s, x) (s##vals + ((x) * s##width))
1701
1702#define LTany(a,b) ((*cmp)(a, b) < 0)
1703#define EQany(a,b) ((*cmp)(a, b) == 0)
1704#define is_any_nil(v) ((v) == NULL || (*cmp)((v), nil) == 0)
1705
1706#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)))
1707#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)))
1708#define or3(a,b) ((a) == 1 || (b) == 1 ? 1 : is_bit_nil(a) || is_bit_nil(b) ? bit_nil : 0)
1709#define and3(a,b) ((a) == 0 || (b) == 0 ? 0 : is_bit_nil(a) || is_bit_nil(b) ? bit_nil : 1)
1710#define not3(a) (is_bit_nil(a) ? bit_nil : !(a))
1711
1712#define between3(v, lo, linc, hi, hinc, TYPE) \
1713 and3(grtr3(v, lo, linc, TYPE), less3(v, hi, hinc, TYPE))
1714
1715#define BETWEEN(v, lo, linc, hi, hinc, TYPE) \
1716 (is_##TYPE##_nil(v) \
1717 ? bit_nil \
1718 : (bit) (anti \
1719 ? (symmetric \
1720 ? not3(or3(between3(v, lo, linc, hi, hinc, TYPE), \
1721 between3(v, hi, hinc, lo, linc, TYPE))) \
1722 : not3(between3(v, lo, linc, hi, hinc, TYPE))) \
1723 : (symmetric \
1724 ? or3(between3(v, lo, linc, hi, hinc, TYPE), \
1725 between3(v, hi, hinc, lo, linc, TYPE)) \
1726 : between3(v, lo, linc, hi, hinc, TYPE))))
1727
1728gdk_return
1729rangejoin(BAT *r1, BAT *r2, BAT *l, BAT *rl, BAT *rh,
1730 struct canditer *lci, struct canditer *rci,
1731 bool li, bool hi, bool anti, bool symmetric, BUN maxsize)
1732{
1733 const char *rlvals, *rhvals;
1734 const char *lvars, *rlvars, *rhvars;
1735 int rlwidth, rhwidth;
1736 int lwidth;
1737 const void *nil = ATOMnilptr(l->ttype);
1738 int (*cmp)(const void *, const void *) = ATOMcompare(l->ttype);
1739 int t;
1740 BUN cnt, ncnt;
1741 oid *restrict dst1, *restrict dst2;
1742 const void *vrl, *vrh;
1743 oid ro;
1744 oid rlval = oid_nil, rhval = oid_nil;
1745 int sorted = 0; /* which output column is sorted */
1746 BAT *tmp;
1747 bool use_orderidx = false;
1748 const char *algo = NULL;
1749
1750 assert(ATOMtype(l->ttype) == ATOMtype(rl->ttype));
1751 assert(ATOMtype(l->ttype) == ATOMtype(rh->ttype));
1752 assert(BATcount(rl) == BATcount(rh));
1753 assert(rl->hseqbase == rh->hseqbase);
1754 assert(r1->ttype == TYPE_oid);
1755 assert(r2 == NULL || r2->ttype == TYPE_oid);
1756 assert(r2 == NULL || BATcount(r1) == BATcount(r2));
1757 assert(l->ttype != TYPE_void || !is_oid_nil(l->tseqbase));
1758 assert(rl->ttype != TYPE_void || !is_oid_nil(rl->tseqbase));
1759 assert(rh->ttype != TYPE_void || !is_oid_nil(rh->tseqbase));
1760
1761 ALGODEBUG fprintf(stderr, "#%s: %s(l=" ALGOBATFMT ","
1762 "rl=" ALGOBATFMT ",rh=" ALGOBATFMT ","
1763 "sl=" ALGOOPTBATFMT ",sr=" ALGOOPTBATFMT ","
1764 "anti=%s,symmetric=%s)\n",
1765 MT_thread_getname(), __func__,
1766 ALGOBATPAR(l),
1767 ALGOBATPAR(rl),
1768 ALGOBATPAR(rh),
1769 ALGOOPTBATPAR(lci->s),
1770 ALGOOPTBATPAR(rci->s),
1771 anti ? "true" : "false",
1772 symmetric ? "true" : "false");
1773
1774 rlvals = rl->ttype == TYPE_void ? NULL : (const char *) Tloc(rl, 0);
1775 rhvals = rh->ttype == TYPE_void ? NULL : (const char *) Tloc(rh, 0);
1776 lwidth = l->twidth;
1777 rlwidth = rl->twidth;
1778 rhwidth = rh->twidth;
1779 dst1 = (oid *) Tloc(r1, 0);
1780 dst2 = r2 ? (oid *) Tloc(r2, 0) : NULL;
1781
1782 t = ATOMtype(l->ttype);
1783 t = ATOMbasetype(t);
1784
1785 if (l->tvarsized && l->ttype) {
1786 assert(rl->tvarsized && rl->ttype);
1787 assert(rh->tvarsized && rh->ttype);
1788 lvars = l->tvheap->base;
1789 rlvars = rl->tvheap->base;
1790 rhvars = rh->tvheap->base;
1791 } else {
1792 assert(!rl->tvarsized || !rl->ttype);
1793 assert(!rh->tvarsized || !rh->ttype);
1794 lvars = rlvars = rhvars = NULL;
1795 }
1796
1797 if (!BATordered(l) && !BATordered_rev(l) &&
1798 (BATcheckorderidx(l) || (VIEWtparent(l) && BATcheckorderidx(BBPquickdesc(VIEWtparent(l), false))))) {
1799 use_orderidx = true;
1800 if (VIEWtparent(l) && !BATcheckorderidx(l)) {
1801 l = BBPdescriptor(VIEWtparent(l));
1802 }
1803 }
1804
1805 vrl = &rlval;
1806 vrh = &rhval;
1807 if (!anti && !symmetric && (BATordered(l) || BATordered_rev(l) || use_orderidx)) {
1808 /* left column is sorted, use binary search */
1809 sorted = 2;
1810 for (BUN i = 0; i < rci->ncand; i++) {
1811 BUN low, high;
1812
1813 ro = canditer_next(rci);
1814 if (rlvals) {
1815 vrl = VALUE(rl, ro - rl->hseqbase);
1816 } else {
1817 /* TYPE_void */
1818 rlval = ro - rl->hseqbase + rl->tseqbase;
1819 }
1820 if (rhvals) {
1821 vrh = VALUE(rh, ro - rh->hseqbase);
1822 } else {
1823 /* TYPE_void */
1824 rhval = ro - rh->hseqbase + rh->tseqbase;
1825 }
1826 if (cmp(vrl, nil) == 0 || cmp(vrh, nil) == 0)
1827 continue;
1828 if (l->tsorted) {
1829 if (li)
1830 low = SORTfndfirst(l, vrl);
1831 else
1832 low = SORTfndlast(l, vrl);
1833 if (hi)
1834 high = SORTfndlast(l, vrh);
1835 else
1836 high = SORTfndfirst(l, vrh);
1837 } else if (l->trevsorted) {
1838 if (hi)
1839 low = SORTfndfirst(l, vrh);
1840 else
1841 low = SORTfndlast(l, vrh);
1842 if (li)
1843 high = SORTfndlast(l, vrl);
1844 else
1845 high = SORTfndfirst(l, vrl);
1846 } else {
1847 assert(use_orderidx);
1848 if (li)
1849 low = ORDERfndfirst(l, vrl);
1850 else
1851 low = ORDERfndlast(l, vrl);
1852 if (hi)
1853 high = ORDERfndlast(l, vrh);
1854 else
1855 high = ORDERfndfirst(l, vrh);
1856 }
1857 if (high <= low)
1858 continue;
1859 if (l->tsorted || l->trevsorted) {
1860 low = canditer_search(lci, low + l->hseqbase, true);
1861 high = canditer_search(lci, high + l->hseqbase, true);
1862 assert(high >= low);
1863
1864 if (BATcapacity(r1) < BUNlast(r1) + high - low) {
1865 cnt = BUNlast(r1) + high - low + 1024;
1866 if (cnt > maxsize)
1867 cnt = maxsize;
1868 BATsetcount(r1, BATcount(r1));
1869 if (BATextend(r1, cnt) != GDK_SUCCEED)
1870 goto bailout;
1871 dst1 = (oid *) Tloc(r1, 0);
1872 if (r2) {
1873 BATsetcount(r2, BATcount(r2));
1874 if (BATextend(r2, cnt) != GDK_SUCCEED)
1875 goto bailout;
1876 assert(BATcapacity(r1) == BATcapacity(r2));
1877 dst2 = (oid *) Tloc(r2, 0);
1878 }
1879 }
1880 canditer_setidx(lci, low);
1881 while (low < high) {
1882 dst1[r1->batCount++] = canditer_next(lci);
1883 if (r2) {
1884 dst2[r2->batCount++] = ro;
1885 }
1886 low++;
1887 }
1888 } else {
1889 const oid *ord;
1890
1891 assert(use_orderidx);
1892 ord = (const oid *) l->torderidx->base + ORDERIDXOFF;
1893
1894 if (BATcapacity(r1) < BUNlast(r1) + high - low) {
1895 cnt = BUNlast(r1) + high - low + 1024;
1896 if (cnt > maxsize)
1897 cnt = maxsize;
1898 BATsetcount(r1, BATcount(r1));
1899 if (BATextend(r1, cnt) != GDK_SUCCEED)
1900 goto bailout;
1901 dst1 = (oid *) Tloc(r1, 0);
1902 if (r2) {
1903 BATsetcount(r2, BATcount(r2));
1904 if (BATextend(r2, cnt) != GDK_SUCCEED)
1905 goto bailout;
1906 assert(BATcapacity(r1) == BATcapacity(r2));
1907 dst2 = (oid *) Tloc(r2, 0);
1908 }
1909 }
1910
1911 while (low < high) {
1912 if (canditer_search(lci, ord[low], false) != BUN_NONE) {
1913 dst1[r1->batCount++] = ord[low];
1914 if (r2) {
1915 dst2[r2->batCount++] = ro;
1916 }
1917 }
1918 low++;
1919 }
1920 }
1921 }
1922 cnt = BATcount(r1);
1923 assert(r2 == NULL || BATcount(r1) == BATcount(r2));
1924 } else if (!anti && !symmetric &&
1925 (BATcount(rl) > 2 ||
1926 !l->batTransient ||
1927 (VIEWtparent(l) != 0 &&
1928 (tmp = BBPquickdesc(VIEWtparent(l), false)) != NULL &&
1929 !tmp->batTransient) ||
1930 BATcheckimprints(l)) &&
1931 BATimprints(l) == GDK_SUCCEED) {
1932 /* implementation using imprints on left column
1933 *
1934 * we use imprints if we can (the type is right for
1935 * imprints) and either the left bat is persistent or
1936 * already has imprints, or the right bats are long
1937 * enough (for creating imprints being worth it) */
1938 BUN maximum;
1939
1940 sorted = 2;
1941 cnt = 0;
1942 maximum = lci->ncand;
1943 for (BUN i = 0; i < rci->ncand; i++) {
1944 ro = canditer_next(rci);
1945 if (rlvals) {
1946 vrl = FVALUE(rl, ro - rl->hseqbase);
1947 } else {
1948 /* TYPE_void */
1949 rlval = ro - rl->hseqbase + rl->tseqbase;
1950 }
1951 if (rhvals) {
1952 vrh = FVALUE(rh, ro - rh->hseqbase);
1953 } else {
1954 /* TYPE_void */
1955 rhval = ro - rl->hseqbase + rl->tseqbase;
1956 }
1957 dst1 = (oid *) Tloc(r1, 0);
1958 switch (t) {
1959 case TYPE_bte: {
1960 bte vl, vh;
1961 if (is_bte_nil((vl = *(bte *) vrl)))
1962 continue;
1963 if (is_bte_nil((vh = *(bte *) vrh)))
1964 continue;
1965 if (!li) {
1966 if (vl == MAXVALUEbte)
1967 continue;
1968 vl = NEXTVALUEbte(vl);
1969 }
1970 if (!hi) {
1971 if (vh == MINVALUEbte)
1972 continue;
1973 vh = PREVVALUEbte(vh);
1974 }
1975 if (vl > vh)
1976 continue;
1977 ncnt = fullscan_bte(l, lci, r1, &vl, &vh,
1978 true, true, false,
1979 false, true, true,
1980 false, cnt,
1981 l->hseqbase, dst1,
1982 cnt + maximum,
1983 true, &algo);
1984 break;
1985 }
1986 case TYPE_sht: {
1987 sht vl, vh;
1988 if (is_sht_nil((vl = *(sht *) vrl)))
1989 continue;
1990 if (is_sht_nil((vh = *(sht *) vrh)))
1991 continue;
1992 if (!li) {
1993 if (vl == MAXVALUEsht)
1994 continue;
1995 vl = NEXTVALUEsht(vl);
1996 }
1997 if (!hi) {
1998 if (vh == MINVALUEsht)
1999 continue;
2000 vh = PREVVALUEsht(vh);
2001 }
2002 if (vl > vh)
2003 continue;
2004 ncnt = fullscan_sht(l, lci, r1, &vl, &vh,
2005 true, true, false,
2006 false, true, true,
2007 false, cnt,
2008 l->hseqbase, dst1,
2009 cnt + maximum,
2010 true, &algo);
2011 break;
2012 }
2013 case TYPE_int:
2014#if SIZEOF_OID == SIZEOF_INT
2015 case TYPE_oid:
2016#endif
2017 {
2018 int vl, vh;
2019 if (is_int_nil((vl = *(int *) vrl)))
2020 continue;
2021 if (is_int_nil((vh = *(int *) vrh)))
2022 continue;
2023 if (!li) {
2024 if (vl == MAXVALUEint)
2025 continue;
2026 vl = NEXTVALUEint(vl);
2027 }
2028 if (!hi) {
2029#if SIZEOF_OID == SIZEOF_INT
2030 if (t == TYPE_oid) {
2031 if (vh == MINVALUEoid)
2032 continue;
2033 vh = PREVVALUEoid(vh);
2034 } else
2035#endif
2036 {
2037 if (vh == MINVALUEint)
2038 continue;
2039 vh = PREVVALUEint(vh);
2040 }
2041 }
2042 if (vl > vh)
2043 continue;
2044 ncnt = fullscan_int(l, lci, r1, &vl, &vh,
2045 true, true, false,
2046 false, true, true,
2047 false, cnt,
2048 l->hseqbase, dst1,
2049 cnt + maximum,
2050 true, &algo);
2051 break;
2052 }
2053 case TYPE_lng:
2054#if SIZEOF_OID == SIZEOF_LNG
2055 case TYPE_oid:
2056#endif
2057 {
2058 lng vl, vh;
2059 if (is_lng_nil((vl = *(lng *) vrl)))
2060 continue;
2061 if (is_lng_nil((vh = *(lng *) vrh)))
2062 continue;
2063 if (!li) {
2064 if (vl == MAXVALUElng)
2065 continue;
2066 vl = NEXTVALUElng(vl);
2067 }
2068 if (!hi) {
2069#if SIZEOF_OID == SIZEOF_LNG
2070 if (t == TYPE_oid) {
2071 if (vh == MINVALUEoid)
2072 continue;
2073 vh = PREVVALUEoid(vh);
2074 } else
2075#endif
2076 {
2077 if (vh == MINVALUElng)
2078 continue;
2079 vh = PREVVALUElng(vh);
2080 }
2081 }
2082 if (vl > vh)
2083 continue;
2084 ncnt = fullscan_lng(l, lci, r1, &vl, &vh,
2085 true, true, false,
2086 false, true, true,
2087 false, cnt,
2088 l->hseqbase, dst1,
2089 cnt + maximum,
2090 true, &algo);
2091 break;
2092 }
2093#ifdef HAVE_HGE
2094 case TYPE_hge: {
2095 hge vl, vh;
2096 if (is_hge_nil((vl = *(hge *) vrl)))
2097 continue;
2098 if (is_hge_nil((vh = *(hge *) vrh)))
2099 continue;
2100 if (!li) {
2101 if (vl == MAXVALUEhge)
2102 continue;
2103 vl = NEXTVALUEhge(vl);
2104 }
2105 if (!hi) {
2106 if (vh == MINVALUEhge)
2107 continue;
2108 vh = PREVVALUEhge(vh);
2109 }
2110 if (vl > vh)
2111 continue;
2112 ncnt = fullscan_hge(l, lci, r1, &vl, &vh,
2113 true, true, false,
2114 false, true, true,
2115 false, cnt,
2116 l->hseqbase, dst1,
2117 cnt + maximum,
2118 true, &algo);
2119 break;
2120 }
2121#endif
2122 case TYPE_flt: {
2123 flt vl, vh;
2124 vl = *(flt *) vrl;
2125 if (is_flt_nil(vl))
2126 continue;
2127 vh = *(flt *) vrh;
2128 if (is_flt_nil(vh))
2129 continue;
2130 if (!li) {
2131 if (vl == MAXVALUEflt)
2132 continue;
2133 vl = NEXTVALUEflt(vl);
2134 }
2135 if (!hi) {
2136 if (vh == MINVALUEflt)
2137 continue;
2138 vh = PREVVALUEflt(vh);
2139 }
2140 if (vl > vh)
2141 continue;
2142 ncnt = fullscan_flt(l, lci, r1, &vl, &vh,
2143 true, true, false,
2144 false, true, true,
2145 false, cnt,
2146 l->hseqbase, dst1,
2147 cnt + maximum,
2148 true, &algo);
2149 break;
2150 }
2151 case TYPE_dbl: {
2152 dbl vl, vh;
2153 vl = *(dbl *) vrl;
2154 if (is_dbl_nil(vl))
2155 continue;
2156 vh = *(dbl *) vrh;
2157 if (is_dbl_nil(vh))
2158 continue;
2159 if (!li) {
2160 if (vl == MAXVALUEdbl)
2161 continue;
2162 vl = NEXTVALUEdbl(vl);
2163 }
2164 if (!hi) {
2165 if (vh == MINVALUEdbl)
2166 continue;
2167 vh = PREVVALUEdbl(vh);
2168 }
2169 if (vl > vh)
2170 continue;
2171 ncnt = fullscan_dbl(l, lci, r1, &vl, &vh,
2172 true, true, false,
2173 false, true, true,
2174 false, cnt,
2175 l->hseqbase, dst1,
2176 cnt + maximum,
2177 true, &algo);
2178 break;
2179 }
2180 default:
2181 ncnt = BUN_NONE;
2182 GDKerror("BATrangejoin: unsupported type\n");
2183 assert(0);
2184 }
2185 if (ncnt == BUN_NONE)
2186 goto bailout;
2187 assert(ncnt >= cnt || ncnt == 0);
2188 if (ncnt == cnt || ncnt == 0)
2189 continue;
2190 if (r2) {
2191 if (BATcapacity(r2) < ncnt) {
2192 BATsetcount(r2, cnt);
2193 if (BATextend(r2, BATcapacity(r1)) != GDK_SUCCEED)
2194 goto bailout;
2195 dst2 = (oid *) Tloc(r2, 0);
2196 }
2197 while (cnt < ncnt)
2198 dst2[cnt++] = ro;
2199 } else {
2200 cnt = ncnt;
2201 }
2202 }
2203 } else {
2204 /* nested loop implementation */
2205 const void *vl;
2206 const char *lvals;
2207 oid lval;
2208
2209 GDKclrerr(); /* not interested in BATimprints errors */
2210 sorted = 1;
2211 lvals = l->ttype == TYPE_void ? NULL : (const char *) Tloc(l, 0);
2212 vl = &lval;
2213 for (BUN i = 0; i < lci->ncand; i++) {
2214 oid lo;
2215
2216 lo = canditer_next(lci);
2217 if (lvals) {
2218 vl = VALUE(l, lo - l->hseqbase);
2219 if (cmp(vl, nil) == 0)
2220 continue;
2221 } else {
2222 lval = lo - l->hseqbase + l->tseqbase;
2223 }
2224 canditer_reset(rci);
2225 for (BUN j = 0; j < rci->ncand; j++) {
2226 ro = canditer_next(rci);
2227 if (rlvals) {
2228 vrl = VALUE(rl, ro - rl->hseqbase);
2229 if (cmp(vrl, nil) == 0)
2230 continue;
2231 } else {
2232 /* TYPE_void */
2233 rlval = ro - rl->hseqbase + rl->tseqbase;
2234 }
2235 if (rhvals) {
2236 vrh = VALUE(rh, ro - rh->hseqbase);
2237 if (cmp(vrh, nil) == 0)
2238 continue;
2239 } else {
2240 /* TYPE_void */
2241 rhval = ro - rh->hseqbase + rh->tseqbase;
2242 }
2243 if (BETWEEN(vl, vrl, li, vrh, hi, any) != 1)
2244 continue;
2245 if (BUNlast(r1) == BATcapacity(r1)) {
2246 BUN newcap = BATgrows(r1);
2247 if (newcap > maxsize)
2248 newcap = maxsize;
2249 BATsetcount(r1, BATcount(r1));
2250 if (BATextend(r1, newcap) != GDK_SUCCEED)
2251 goto bailout;
2252 dst1 = (oid *) Tloc(r1, 0);
2253 if (r2) {
2254 BATsetcount(r2, BATcount(r2));
2255 if (BATextend(r2, newcap) != GDK_SUCCEED)
2256 goto bailout;
2257 assert(BATcapacity(r1) == BATcapacity(r2));
2258 dst2 = (oid *) Tloc(r2, 0);
2259 }
2260 }
2261 dst1[r1->batCount++] = lo;
2262 if (r2) {
2263 dst2[r2->batCount++] = ro;
2264 }
2265 }
2266 }
2267 cnt = BATcount(r1);
2268 assert(r2 == NULL || BATcount(r1) == BATcount(r2));
2269 }
2270
2271 /* also set other bits of heap to correct value to indicate size */
2272 BATsetcount(r1, cnt);
2273
2274 /* set properties using an extra scan (usually not complete) */
2275 dst1 = (oid *) Tloc(r1, 0);
2276 r1->tkey = true;
2277 r1->tsorted = true;
2278 r1->trevsorted = true;
2279 r1->tseqbase = 0;
2280 r1->tnil = false;
2281 r1->tnonil = true;
2282 for (ncnt = 1; ncnt < cnt; ncnt++) {
2283 if (dst1[ncnt - 1] == dst1[ncnt]) {
2284 r1->tseqbase = oid_nil;
2285 r1->tkey = false;
2286 } else if (dst1[ncnt - 1] < dst1[ncnt]) {
2287 r1->trevsorted = false;
2288 if (dst1[ncnt - 1] + 1 != dst1[ncnt])
2289 r1->tseqbase = oid_nil;
2290 } else {
2291 assert(sorted != 1);
2292 r1->tsorted = false;
2293 r1->tseqbase = oid_nil;
2294 r1->tkey = false;
2295 }
2296 if (!(r1->trevsorted | BATtdense(r1) | r1->tkey | ((sorted != 1) & r1->tsorted)))
2297 break;
2298 }
2299 if (BATtdense(r1))
2300 r1->tseqbase = cnt > 0 ? dst1[0] : 0;
2301 if (r2) {
2302 BATsetcount(r2, cnt);
2303 dst2 = (oid *) Tloc(r2, 0);
2304 r2->tkey = true;
2305 r2->tsorted = true;
2306 r2->trevsorted = true;
2307 r2->tseqbase = 0;
2308 r2->tnil = false;
2309 r2->tnonil = true;
2310 for (ncnt = 1; ncnt < cnt; ncnt++) {
2311 if (dst2[ncnt - 1] == dst2[ncnt]) {
2312 r2->tseqbase = oid_nil;
2313 r2->tkey = false;
2314 } else if (dst2[ncnt - 1] < dst2[ncnt]) {
2315 r2->trevsorted = false;
2316 if (dst2[ncnt - 1] + 1 != dst2[ncnt])
2317 r2->tseqbase = oid_nil;
2318 } else {
2319 assert(sorted != 2);
2320 r2->tsorted = false;
2321 r2->tseqbase = oid_nil;
2322 r2->tkey = false;
2323 }
2324 if (!(r2->trevsorted | BATtdense(r2) | r2->tkey | ((sorted != 2) & r2->tsorted)))
2325 break;
2326 }
2327 if (BATtdense(r2))
2328 r2->tseqbase = cnt > 0 ? dst2[0] : 0;
2329 }
2330 ALGODEBUG fprintf(stderr, "#%s: %s(l=%s,rl=%s,rh=%s)="
2331 "(" ALGOBATFMT "," ALGOOPTBATFMT ")\n",
2332 MT_thread_getname(), __func__,
2333 BATgetId(l), BATgetId(rl), BATgetId(rh),
2334 ALGOBATPAR(r1), ALGOOPTBATPAR(r2));
2335 return GDK_SUCCEED;
2336
2337 bailout:
2338 BBPreclaim(r1);
2339 BBPreclaim(r2);
2340 return GDK_FAIL;
2341}
2342