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 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_cand.h"
17 :
18 : /* how much to extend the extent and histo bats when we run out of space */
19 : #define GROUPBATINCR 8192
20 :
21 : /* BATgroup returns three bats that indicate the grouping of the input
22 : * bat.
23 : *
24 : * Grouping means that all equal values are in the same group, and
25 : * differing values are in different groups. If specified, the input
26 : * bat g gives a pre-existing grouping which is then subdivided. If a
27 : * candidate list s is specified, groups (both the pre-existing
28 : * grouping in g and the output grouping) are aligned with the
29 : * candidate list, else they are aligned with b.
30 : *
31 : * The outputs are as follows.
32 : *
33 : * The groups bat is aligned with the candidate list s, or the input
34 : * bat b if there is no candidate list, and the tail has group id's
35 : * (type oid).
36 : *
37 : * The extents and histo bats are indexed by group id. The tail of
38 : * extents is the head oid from b of a representative of the group.
39 : * The tail of histo is of type lng and contains the number of
40 : * elements from b that are member of the group. The extents BAT can
41 : * be used as a candidate list (sorted and unique).
42 : *
43 : * The extents and histo bats are optionally created. The groups bat
44 : * is always created. In other words, the groups argument may not be
45 : * NULL, but the extents and histo arguments may be NULL.
46 : *
47 : * There are six different implementations of the grouping code.
48 : *
49 : * If it can be trivially determined that all groups are singletons,
50 : * we can produce the outputs trivially.
51 : *
52 : * If all values in b are known to be equal (both sorted and reverse
53 : * sorted), we produce a single group or copy the input group.
54 : *
55 : * If the input bats b and g are sorted (either direction) or g is not
56 : * specified and b is sorted, or if the subsorted flag is set (only
57 : * used by BATsort), we only need to compare consecutive values.
58 : *
59 : * If the input bat b is sorted, but g is not, we can compare
60 : * consecutive values in b and need to scan sections of g for equal
61 : * groups.
62 : *
63 : * If a hash table already exists on b, we can make use of it.
64 : *
65 : * Otherwise we build a partial hash table on the fly.
66 : *
67 : * A decision should be made on the order in which grouping occurs.
68 : * Let |b| have << different values than |g| then the linked lists
69 : * gets extremely long, leading to a n^2 algorithm.
70 : * At the MAL level, the multigroup function would perform the dynamic
71 : * optimization.
72 : */
73 :
74 : #define GRPnotfound() \
75 : do { \
76 : /* no equal found: start new group */ \
77 : if (ngrp == maxgrps) { \
78 : /* we need to extend extents and histo bats, */ \
79 : /* do it at most once */ \
80 : maxgrps = bi.count; \
81 : if (extents) { \
82 : BATsetcount(en, ngrp); \
83 : if (BATextend(en, maxgrps) != GDK_SUCCEED) \
84 : goto error; \
85 : exts = (oid *) Tloc(en, 0); \
86 : } \
87 : if (histo) { \
88 : BATsetcount(hn, ngrp); \
89 : if (BATextend(hn, maxgrps) != GDK_SUCCEED) \
90 : goto error; \
91 : cnts = (lng *) Tloc(hn, 0); \
92 : } \
93 : } \
94 : if (extents) \
95 : exts[ngrp] = hseqb + p - lo; \
96 : if (histo) \
97 : cnts[ngrp] = 1; \
98 : ngrps[r] = ngrp++; \
99 : maxgrppos = r; \
100 : } while (0)
101 :
102 :
103 : #define GRP_compare_consecutive_values(INIT_0,INIT_1,DIFFER,KEEP) \
104 : do { \
105 : INIT_0; \
106 : if (ci.tpe == cand_dense) { \
107 : if (grps) { \
108 : MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, groups"); \
109 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
110 : p = canditer_next_dense(&ci) - hseqb; \
111 : INIT_1; \
112 : if (ngrp == 0 || grps[r] != prev || DIFFER) { \
113 : GRPnotfound(); \
114 : } else { \
115 : ngrps[r] = ngrp - 1; \
116 : if (histo) \
117 : cnts[ngrp - 1]++; \
118 : } \
119 : KEEP; \
120 : prev = grps[r]; \
121 : } \
122 : TIMEOUT_CHECK(timeoffset, \
123 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
124 : } else { \
125 : MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, !groups"); \
126 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
127 : p = canditer_next_dense(&ci) - hseqb; \
128 : INIT_1; \
129 : if (ngrp == 0 || DIFFER) { \
130 : GRPnotfound(); \
131 : } else { \
132 : ngrps[r] = ngrp - 1; \
133 : if (histo) \
134 : cnts[ngrp - 1]++; \
135 : } \
136 : KEEP; \
137 : } \
138 : TIMEOUT_CHECK(timeoffset, \
139 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
140 : } \
141 : } else { \
142 : if (grps) { \
143 : MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, groups"); \
144 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
145 : p = canditer_next(&ci) - hseqb; \
146 : INIT_1; \
147 : if (ngrp == 0 || grps[r] != prev || DIFFER) { \
148 : GRPnotfound(); \
149 : } else { \
150 : ngrps[r] = ngrp - 1; \
151 : if (histo) \
152 : cnts[ngrp - 1]++; \
153 : } \
154 : KEEP; \
155 : prev = grps[r]; \
156 : } \
157 : TIMEOUT_CHECK(timeoffset, \
158 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
159 : } else { \
160 : MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, !groups"); \
161 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
162 : p = canditer_next(&ci) - hseqb; \
163 : INIT_1; \
164 : if (ngrp == 0 || DIFFER) { \
165 : GRPnotfound(); \
166 : } else { \
167 : ngrps[r] = ngrp - 1; \
168 : if (histo) \
169 : cnts[ngrp - 1]++; \
170 : } \
171 : KEEP; \
172 : } \
173 : TIMEOUT_CHECK(timeoffset, \
174 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
175 : } \
176 : } \
177 : } while(0)
178 :
179 : #define flt_neq(a, b) (is_flt_nil(a) ? !is_flt_nil(b) : is_flt_nil(b) || (a) != (b))
180 : #define dbl_neq(a, b) (is_dbl_nil(a) ? !is_dbl_nil(b) : is_dbl_nil(b) || (a) != (b))
181 : #define bte_neq(a, b) ((a) != (b))
182 : #define sht_neq(a, b) ((a) != (b))
183 : #define int_neq(a, b) ((a) != (b))
184 : #define lng_neq(a, b) ((a) != (b))
185 : #define hge_neq(a, b) ((a) != (b))
186 :
187 : #define GRP_compare_consecutive_values_tpe(TYPE) \
188 : GRP_compare_consecutive_values( \
189 : /* INIT_0 */ const TYPE *w = (TYPE *) bi.base; \
190 : TYPE pw = 0 , \
191 : /* INIT_1 */ , \
192 : /* DIFFER */ TYPE##_neq(w[p], pw) , \
193 : /* KEEP */ pw = w[p] \
194 : )
195 :
196 : #define GRP_compare_consecutive_values_any() \
197 : GRP_compare_consecutive_values( \
198 : /* INIT_0 */ pv = NULL , \
199 : /* INIT_1 */ v = BUNtail(bi, p) , \
200 : /* DIFFER */ cmp(v, pv) != 0 , \
201 : /* KEEP */ pv = v \
202 : )
203 :
204 :
205 : #define GRP_subscan_old_groups(INIT_0,INIT_1,EQUAL,KEEP) \
206 : do { \
207 : INIT_0; \
208 : pgrp[grps[0]] = 0; \
209 : j = 0; \
210 : if (ci.tpe == cand_dense) { \
211 : MT_thread_setalgorithm("GRP_subscan_old_groups, dense"); \
212 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
213 : p = canditer_next_dense(&ci) - hseqb; \
214 : INIT_1; \
215 : if (ngrp != 0 && EQUAL) { \
216 : /* range [j, r) is all same value */ \
217 : /* i is position where we saw r's */ \
218 : /* old group last */ \
219 : i = pgrp[grps[r]]; \
220 : /* p is new position where we saw this \
221 : * group */ \
222 : pgrp[grps[r]] = r; \
223 : if (j <= i && i < r) { \
224 : /* i is position of equal */ \
225 : /* value in same old group */ \
226 : /* as r, so r gets same new */ \
227 : /* group as i */ \
228 : oid grp = ngrps[i]; \
229 : ngrps[r] = grp; \
230 : if (histo) \
231 : cnts[grp]++; \
232 : if (gn->tsorted && \
233 : grp != ngrp - 1) \
234 : gn->tsorted = false; \
235 : /* we found the value/group */ \
236 : /* combination, go to next */ \
237 : /* value */ \
238 : continue; \
239 : } \
240 : } else { \
241 : /* value differs from previous value */ \
242 : /* (or is the first) */ \
243 : j = r; \
244 : KEEP; \
245 : pgrp[grps[r]] = r; \
246 : } \
247 : /* start a new group */ \
248 : GRPnotfound(); \
249 : } \
250 : TIMEOUT_CHECK(timeoffset, \
251 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
252 : } else { \
253 : MT_thread_setalgorithm("GRP_subscan_old_groups, !dense"); \
254 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
255 : p = canditer_next(&ci) - hseqb; \
256 : INIT_1; \
257 : if (ngrp != 0 && EQUAL) { \
258 : /* range [j, r) is all same value */ \
259 : /* i is position where we saw r's */ \
260 : /* old group last */ \
261 : i = pgrp[grps[r]]; \
262 : /* p is new position where we saw this \
263 : * group */ \
264 : pgrp[grps[r]] = r; \
265 : if (j <= i && i < r) { \
266 : /* i is position of equal */ \
267 : /* value in same old group */ \
268 : /* as r, so r gets same new */ \
269 : /* group as i */ \
270 : oid grp = ngrps[i]; \
271 : ngrps[r] = grp; \
272 : if (histo) \
273 : cnts[grp]++; \
274 : if (gn->tsorted && \
275 : grp != ngrp - 1) \
276 : gn->tsorted = false; \
277 : /* we found the value/group */ \
278 : /* combination, go to next */ \
279 : /* value */ \
280 : continue; \
281 : } \
282 : } else { \
283 : /* value differs from previous value */ \
284 : /* (or is the first) */ \
285 : j = r; \
286 : KEEP; \
287 : pgrp[grps[r]] = r; \
288 : } \
289 : /* start a new group */ \
290 : GRPnotfound(); \
291 : } \
292 : TIMEOUT_CHECK(timeoffset, \
293 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
294 : } \
295 : } while(0)
296 :
297 : #define flt_equ(a, b) (is_flt_nil(a) ? is_flt_nil(b) : !is_flt_nil(b) && (a) == (b))
298 : #define dbl_equ(a, b) (is_dbl_nil(a) ? is_dbl_nil(b) : !is_dbl_nil(b) && (a) == (b))
299 : #define bte_equ(a, b) ((a) == (b))
300 : #define sht_equ(a, b) ((a) == (b))
301 : #define int_equ(a, b) ((a) == (b))
302 : #define lng_equ(a, b) ((a) == (b))
303 : #define hge_equ(a, b) ((a) == (b))
304 : #ifdef HAVE_HGE
305 : #define uuid_equ(a, b) ((a).h == (b).h)
306 : #else
307 : #define uuid_equ(a, b) (memcmp((a).u, (b).u, UUID_SIZE) == 0)
308 : #endif
309 :
310 : #define GRP_subscan_old_groups_tpe(TYPE) \
311 : GRP_subscan_old_groups( \
312 : /* INIT_0 */ const TYPE *w = (TYPE *) bi.base; \
313 : TYPE pw = 0 , \
314 : /* INIT_1 */ , \
315 : /* EQUAL */ TYPE##_equ(w[p], pw) , \
316 : /* KEEP */ pw = w[p] \
317 : )
318 :
319 : #define GRP_subscan_old_groups_any() \
320 : GRP_subscan_old_groups( \
321 : /* INIT_0 */ pv = NULL , \
322 : /* INIT_1 */ v = BUNtail(bi, p) , \
323 : /* EQUAL */ cmp(v, pv) == 0 , \
324 : /* KEEP */ pv = v \
325 : )
326 :
327 : /* If a hash table exists on b we use it.
328 : *
329 : * The algorithm is simple. We go through b and for each value we
330 : * follow the hash chain starting at the next element after that value
331 : * to find one that is equal to the value we're currently looking at.
332 : * If we found such a value, we add the value to the same group. If
333 : * we reach the end of the chain, we create a new group.
334 : *
335 : * If b (the original, that is) is a view on another BAT, and this
336 : * other BAT has a hash, we use that. The lo and hi values are the
337 : * bounds of the parent BAT that we're considering.
338 : *
339 : * Note this algorithm depends critically on the fact that our hash
340 : * chains go from higher to lower BUNs.
341 : */
342 : #define GRP_use_existing_hash_table(INIT_0,INIT_1,EQUAL) \
343 : do { \
344 : INIT_0; \
345 : assert(grps == NULL); \
346 : if (ci.tpe == cand_dense) { \
347 : MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, dense, parent hash" : "GRP_use_existing_hash_table, dense"); \
348 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
349 : oid o = canditer_next_dense(&ci); \
350 : p = o - hseqb + lo; \
351 : INIT_1; \
352 : /* this loop is similar, but not */ \
353 : /* equal, to HASHloop: the difference */ \
354 : /* is that we only consider BUNs */ \
355 : /* smaller than the one we're looking */ \
356 : /* up (p) */ \
357 : for (hb = HASHgetlink(hs, p); \
358 : hb != BUN_NONE && hb >= lo; \
359 : hb = HASHgetlink(hs, hb)) { \
360 : oid grp; \
361 : assert(hb < p); \
362 : q = canditer_search_dense(&ci, hb + hseqb - lo, false); \
363 : if (q == BUN_NONE) \
364 : continue; \
365 : if (EQUAL) { \
366 : grp = ngrps[q]; \
367 : ngrps[r] = grp; \
368 : if (histo) \
369 : cnts[grp]++; \
370 : if (gn->tsorted && \
371 : grp != ngrp - 1) \
372 : gn->tsorted = false; \
373 : break; \
374 : } \
375 : } \
376 : if (hb == BUN_NONE || hb < lo) { \
377 : GRPnotfound(); \
378 : } \
379 : } \
380 : TIMEOUT_CHECK(timeoffset, \
381 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
382 : } else { \
383 : MT_thread_setalgorithm(phash ? "GRP_use_existing_hash_table, !dense, parent hash" : "GRP_use_existing_hash_table, !dense"); \
384 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
385 : oid o = canditer_next(&ci); \
386 : p = o - hseqb + lo; \
387 : INIT_1; \
388 : /* this loop is similar, but not */ \
389 : /* equal, to HASHloop: the difference */ \
390 : /* is that we only consider BUNs */ \
391 : /* smaller than the one we're looking */ \
392 : /* up (p) */ \
393 : for (hb = HASHgetlink(hs, p); \
394 : hb != BUN_NONE && hb >= lo; \
395 : hb = HASHgetlink(hs, hb)) { \
396 : oid grp; \
397 : assert(hb < p); \
398 : q = canditer_search(&ci, hb + hseqb - lo, false); \
399 : if (q == BUN_NONE) \
400 : continue; \
401 : if (EQUAL) { \
402 : grp = ngrps[q]; \
403 : ngrps[r] = grp; \
404 : if (histo) \
405 : cnts[grp]++; \
406 : if (gn->tsorted && \
407 : grp != ngrp - 1) \
408 : gn->tsorted = false; \
409 : break; \
410 : } \
411 : } \
412 : if (hb == BUN_NONE || hb < lo) { \
413 : GRPnotfound(); \
414 : } \
415 : } \
416 : TIMEOUT_CHECK(timeoffset, \
417 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
418 : } \
419 : } while(0)
420 :
421 : #define GRP_use_existing_hash_table_tpe(TYPE) \
422 : GRP_use_existing_hash_table( \
423 : /* INIT_0 */ const TYPE *w = (TYPE *) bi.base, \
424 : /* INIT_1 */ , \
425 : /* EQUAL */ TYPE##_equ(w[p], w[hb]) \
426 : )
427 :
428 : #define GRP_use_existing_hash_table_any() \
429 : GRP_use_existing_hash_table( \
430 : /* INIT_0 */ , \
431 : /* INIT_1 */ v = BUNtail(bi, p) , \
432 : /* EQUAL */ cmp(v, BUNtail(bi, hb)) == 0 \
433 : )
434 :
435 : /* reverse the bits of an OID value */
436 : static inline oid
437 42870807 : rev(oid x)
438 : {
439 : #if SIZEOF_OID == 8
440 42870807 : x = ((x & 0x5555555555555555) << 1) | ((x >> 1) & 0x5555555555555555);
441 42870807 : x = ((x & 0x3333333333333333) << 2) | ((x >> 2) & 0x3333333333333333);
442 42870807 : x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F0F0F0F0F);
443 42870807 : x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF00FF00FF);
444 42870807 : x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF0000FFFF);
445 42870807 : x = ((x & 0x00000000FFFFFFFF) << 32) | ((x >> 32) & 0x00000000FFFFFFFF);
446 : #else
447 : x = ((x & 0x55555555) << 1) | ((x >> 1) & 0x55555555);
448 : x = ((x & 0x33333333) << 2) | ((x >> 2) & 0x33333333);
449 : x = ((x & 0x0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F);
450 : x = ((x & 0x00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF);
451 : x = ((x & 0x0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF);
452 : #endif
453 42870807 : return x;
454 : }
455 :
456 : /* count trailing zeros, also see candmask_lobit in gdk_cand.h */
457 : static inline int __attribute__((__const__))
458 12440 : ctz(oid x)
459 : {
460 : #if defined(__GNUC__)
461 : #if SIZEOF_OID == SIZEOF_INT
462 : return __builtin_ctz(x);
463 : #else
464 12440 : return __builtin_ctzl(x);
465 : #endif
466 : #elif defined(_MSC_VER)
467 : #if SIZEOF_OID == SIZEOF_INT
468 : unsigned long idx;
469 : if (_BitScanForward(&idx, (unsigned long) x))
470 : return (int) idx;
471 : #else
472 : unsigned long idx;
473 : if (_BitScanForward64(&idx, (unsigned __int64) x))
474 : return (int) idx;
475 : #endif
476 : return -1;
477 : #else
478 : /* use binary search for the lowest set bit */
479 : int n = 1;
480 : #if SIZEOF_OID == SIZEOF_INT
481 : if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
482 : if ((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
483 : if ((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
484 : if ((x & 0x00000003) == 0) { n += 2; x >>= 2; }
485 : #else
486 : if ((x & UINT64_C(0x00000000FFFFFFFF)) == 0) { n += 32; x >>= 32; }
487 : if ((x & UINT64_C(0x000000000000FFFF)) == 0) { n += 16; x >>= 16; }
488 : if ((x & UINT64_C(0x00000000000000FF)) == 0) { n += 8; x >>= 8; }
489 : if ((x & UINT64_C(0x000000000000000F)) == 0) { n += 4; x >>= 4; }
490 : if ((x & UINT64_C(0x0000000000000003)) == 0) { n += 2; x >>= 2; }
491 : #endif
492 : return n - (x & 1);
493 : #endif
494 : }
495 :
496 : #define GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,ASSERT,GRPTST) \
497 : do { \
498 : if (ci.tpe == cand_dense) { \
499 : MT_thread_setalgorithm("GRP_create_partial_hash_table, dense"); \
500 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
501 : p = canditer_next_dense(&ci) - hseqb; \
502 : INIT_1; \
503 : prb = HASH; \
504 : for (hb = HASHget(hs, prb); \
505 : hb != BUN_NONE; \
506 : hb = HASHgetlink(hs, hb)) { \
507 : ASSERT; \
508 : q = canditer_search_dense(&ci, hb + hseqb, false); \
509 : if (q == BUN_NONE) \
510 : continue; \
511 : GRPTST(q, r); \
512 : if (EQUAL) { \
513 : grp = ngrps[q]; \
514 : ngrps[r] = grp; \
515 : if (histo) \
516 : cnts[grp]++; \
517 : if (gn->tsorted && \
518 : grp != ngrp - 1) \
519 : gn->tsorted = false; \
520 : break; \
521 : } \
522 : } \
523 : if (hb == BUN_NONE) { \
524 : GRPnotfound(); \
525 : /* enter new group into hash table */ \
526 : HASHputlink(hs, p, HASHget(hs, prb)); \
527 : HASHput(hs, prb, p); \
528 : } \
529 : } \
530 : TIMEOUT_CHECK(timeoffset, \
531 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
532 : } else { \
533 : MT_thread_setalgorithm("GRP_create_partial_hash_table, !dense"); \
534 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
535 : p = canditer_next(&ci) - hseqb; \
536 : INIT_1; \
537 : prb = HASH; \
538 : for (hb = HASHget(hs, prb); \
539 : hb != BUN_NONE; \
540 : hb = HASHgetlink(hs, hb)) { \
541 : ASSERT; \
542 : q = canditer_search(&ci, hb + hseqb, false); \
543 : if (q == BUN_NONE) \
544 : continue; \
545 : GRPTST(q, r); \
546 : if (EQUAL) { \
547 : grp = ngrps[q]; \
548 : ngrps[r] = grp; \
549 : if (histo) \
550 : cnts[grp]++; \
551 : if (gn->tsorted && \
552 : grp != ngrp - 1) \
553 : gn->tsorted = false; \
554 : break; \
555 : } \
556 : } \
557 : if (hb == BUN_NONE) { \
558 : GRPnotfound(); \
559 : /* enter new group into hash table */ \
560 : HASHputlink(hs, p, HASHget(hs, prb)); \
561 : HASHput(hs, prb, p); \
562 : } \
563 : } \
564 : TIMEOUT_CHECK(timeoffset, \
565 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
566 : } \
567 : } while (0)
568 : #define GCGRPTST(i, j) if (grps[i] != grps[j]) { hb = BUN_NONE; break; }
569 : #define GRPTST(i, j) if (grps[i] != grps[j]) continue
570 : #define NOGRPTST(i, j) (void) 0
571 : #define GRP_create_partial_hash_table(INIT_0,INIT_1,HASH,EQUAL) \
572 : do { \
573 : INIT_0; \
574 : if (grps) { \
575 : if (gc) { \
576 : GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,assert(HASHgetlink(hs, hb) == BUN_NONE || HASHgetlink(hs, hb) < hb),GCGRPTST); \
577 : } else { \
578 : GRP_create_partial_hash_table_core(INIT_1,HASH ^ (rev(grps[r]) >> bits),EQUAL,(void)0,GRPTST); \
579 : } \
580 : } else { \
581 : GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,(void)0,NOGRPTST); \
582 : } \
583 : } while (0)
584 :
585 : #define GRP_create_partial_hash_table_tpe(TYPE) \
586 : GRP_create_partial_hash_table( \
587 : /* INIT_0 */ const TYPE *w = (TYPE *) bi.base, \
588 : /* INIT_1 */ , \
589 : /* HASH */ hash_##TYPE(hs, &w[p]) , \
590 : /* EQUAL */ TYPE##_equ(w[p], w[hb]) \
591 : )
592 :
593 : #define GRP_create_partial_hash_table_any() \
594 : GRP_create_partial_hash_table( \
595 : /* INIT_0 */ , \
596 : /* INIT_1 */ v = BUNtail(bi, p) , \
597 : /* HASH */ hash_any(hs, v) , \
598 : /* EQUAL */ cmp(v, BUNtail(bi, hb)) == 0 \
599 : )
600 :
601 : #define GRP_small_values(BG, BV, GV) \
602 : do { \
603 : uint##BG##_t sgrps[1 << BG]; \
604 : const uint##BV##_t *restrict w = (const uint##BV##_t *) bi.base; \
605 : uint##BG##_t v; \
606 : memset(sgrps, 0xFF, sizeof(sgrps)); \
607 : if (histo) \
608 : memset(cnts, 0, maxgrps * sizeof(lng)); \
609 : ngrp = 0; \
610 : gn->tsorted = true; \
611 : if (ci.tpe == cand_dense) { \
612 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
613 : oid o = canditer_next_dense(&ci); \
614 : p = o - hseqb; \
615 : uint##BG##_t x = GV; \
616 : if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
617 : sgrps[x] = v = (uint##BG##_t) ngrp++; \
618 : maxgrppos = r; \
619 : if (extents) \
620 : exts[v] = o; \
621 : } \
622 : ngrps[r] = v; \
623 : if (r > 0 && v < ngrps[r - 1]) \
624 : gn->tsorted = false; \
625 : if (histo) \
626 : cnts[v]++; \
627 : } \
628 : } else { \
629 : TIMEOUT_LOOP_IDX(r, ci.ncand, timeoffset) { \
630 : oid o = canditer_next(&ci); \
631 : p = o - hseqb; \
632 : uint##BG##_t x = GV; \
633 : if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
634 : sgrps[x] = v = (uint##BG##_t) ngrp++; \
635 : maxgrppos = r; \
636 : if (extents) \
637 : exts[v] = o; \
638 : } \
639 : ngrps[r] = v; \
640 : if (r > 0 && v < ngrps[r - 1]) \
641 : gn->tsorted = false; \
642 : if (histo) \
643 : cnts[v]++; \
644 : } \
645 : } \
646 : TIMEOUT_CHECK(timeoffset, \
647 : GOTO_LABEL_TIMEOUT_HANDLER(error)); \
648 : } while (0)
649 :
650 : gdk_return
651 63810 : BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
652 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h, bool subsorted)
653 : {
654 63810 : BAT *gn = NULL, *en = NULL, *hn = NULL;
655 63810 : int t;
656 63810 : int (*cmp)(const void *, const void *);
657 63810 : const oid *grps = NULL;
658 63810 : oid *restrict ngrps, ngrp, prev = 0, hseqb = 0;
659 63810 : oid *restrict exts = NULL;
660 63810 : lng *restrict cnts = NULL;
661 63810 : BUN p, q, r;
662 63810 : const void *v, *pv;
663 63810 : BATiter bi;
664 63810 : Hash *hs = NULL;
665 63810 : BUN hb;
666 63810 : BUN maxgrps;
667 63810 : BUN maxgrppos = BUN_NONE;
668 63810 : bat parent;
669 63810 : BUN lo = 0;
670 63810 : struct canditer ci;
671 63810 : oid maxgrp = oid_nil; /* maximum value of g BAT (if subgrouping) */
672 63810 : lng t0 = 0;
673 63810 : const char *algomsg = "";
674 63810 : bool locked = false;
675 :
676 63810 : lng timeoffset = 0;
677 63810 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
678 63810 : if (qry_ctx != NULL) {
679 58083 : timeoffset = (qry_ctx->starttime && qry_ctx->querytimeout) ? (qry_ctx->starttime + qry_ctx->querytimeout) : 0;
680 : }
681 :
682 63810 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
683 63810 : if (b == NULL) {
684 0 : GDKerror("b must exist\n");
685 0 : return GDK_FAIL;
686 : }
687 63810 : assert(s == NULL || BATttype(s) == TYPE_oid);
688 63810 : canditer_init(&ci, b, s);
689 63809 : bi = bat_iterator(b);
690 :
691 : /* g is NULL or [oid(dense),oid] and same size as b or s */
692 63801 : assert(g == NULL || BATttype(g) == TYPE_oid || BATcount(g) == 0);
693 19272 : assert(g == NULL || BATcount(g) == ci.ncand);
694 19272 : assert(g == NULL || BATcount(b) == 0 || (s ? g->hseqbase == s->hseqbase : g->hseqbase == b->hseqbase));
695 : /* e is NULL or [oid(dense),oid] */
696 63801 : assert(e == NULL || BATttype(e) == TYPE_oid);
697 : /* h is NULL or [oid(dense),lng] */
698 63801 : assert(h == NULL || h->ttype == TYPE_lng);
699 : /* e and h are aligned */
700 63801 : assert(e == NULL || h == NULL || BATcount(e) == BATcount(h));
701 63801 : assert(e == NULL || h == NULL || e->hseqbase == h->hseqbase);
702 : /* we want our output to go somewhere */
703 63801 : assert(groups != NULL);
704 :
705 63801 : if (ci.ncand == 0) {
706 : hseqb = 0;
707 : } else {
708 48260 : hseqb = ci.seq;
709 : }
710 63801 : if (bi.key || ci.ncand <= 1 || (g && (g->tkey || BATtdense(g)))) {
711 : /* grouping is trivial: 1 element per group */
712 31602 : gn = BATdense(hseqb, 0, BATcount(b));
713 31614 : if (gn == NULL)
714 0 : goto error;
715 31614 : *groups = gn;
716 31614 : if (extents) {
717 31177 : en = canditer_slice(&ci, 0, ci.ncand);
718 31177 : if (en == NULL)
719 0 : goto error;
720 31177 : *extents = en;
721 : }
722 31614 : if (histo) {
723 3203 : hn = BATconstant(0, TYPE_lng, &(lng){1}, ci.ncand, TRANSIENT);
724 3203 : if (hn == NULL)
725 0 : goto error;
726 3203 : *histo = hn;
727 : }
728 31614 : bat_iterator_end(&bi);
729 31614 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
730 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
731 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
732 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
733 : ",histo=" ALGOOPTBATFMT " (1 element per group -- "
734 : LLFMT " usec)\n",
735 : ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOOPTBATPAR(g),
736 : ALGOOPTBATPAR(e), ALGOOPTBATPAR(h),
737 : subsorted ? "true" : "false", ALGOOPTBATPAR(gn),
738 : ALGOOPTBATPAR(en), ALGOOPTBATPAR(hn), GDKusec() - t0);
739 31614 : return GDK_SUCCEED;
740 : }
741 32199 : assert(!BATtdense(b));
742 32199 : if (g) {
743 6275 : assert(!BATtdense(g));
744 6275 : if (g->tsorted)
745 4691 : maxgrp = * (oid *) Tloc(g, BATcount(g) - 1);
746 1584 : else if (g->trevsorted)
747 0 : maxgrp = * (oid *) Tloc(g, 0);
748 : else {
749 : /* group bats are not modified in parallel, so
750 : * no need for locks */
751 1584 : if (g->tmaxpos != BUN_NONE)
752 1581 : maxgrp = BUNtoid(g, g->tmaxpos);
753 1584 : if (is_oid_nil(maxgrp) /* && BATcount(g) < 10240 */) {
754 3 : BATmax(g, &maxgrp);
755 : }
756 : }
757 6275 : if (maxgrp == 0)
758 : g = NULL; /* single group */
759 : else
760 4480 : grps = (const oid *) Tloc(g, 0);
761 : }
762 32199 : (void) BATordered(b);
763 32199 : (void) BATordered_rev(b);
764 32200 : bat_iterator_end(&bi);
765 32200 : bi = bat_iterator(b);
766 32199 : if (bi.sorted && bi.revsorted) {
767 : /* all values are equal */
768 3204 : if (g == NULL || (BATordered(g) && BATordered_rev(g))) {
769 : /* there's only a single group: 0 */
770 2881 : gn = BATconstant(hseqb, TYPE_oid, &(oid){0}, ci.ncand, TRANSIENT);
771 2881 : if (gn == NULL)
772 0 : goto error;
773 2881 : *groups = gn;
774 2881 : if (extents) {
775 1961 : en = BATdense(0, canditer_next(&ci), 1);
776 1961 : if (en == NULL)
777 0 : goto error;
778 1961 : *extents = en;
779 : }
780 2881 : if (histo) {
781 45 : hn = BATconstant(0, TYPE_lng, &(lng){(lng)ci.ncand}, 1, TRANSIENT);
782 45 : if (hn == NULL)
783 0 : goto error;
784 45 : *histo = hn;
785 : }
786 2881 : bat_iterator_end(&bi);
787 2882 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
788 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
789 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
790 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
791 : ",histo=" ALGOOPTBATFMT " (single group -- "
792 : LLFMT " usec)\n",
793 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
794 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
795 : ALGOOPTBATPAR(h),
796 : subsorted ? "true" : "false",
797 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
798 : ALGOOPTBATPAR(hn), GDKusec() - t0);
799 2882 : return GDK_SUCCEED;
800 : }
801 323 : if ((extents == NULL || e != NULL) &&
802 142 : (histo == NULL || h != NULL) &&
803 142 : ci.ncand == BATcount(b)) {
804 : /* inherit given grouping; note that if
805 : * extents/histo is to be returned, we need
806 : * e/h available in order to copy them,
807 : * otherwise we will need to calculate them
808 : * which we will do using the "normal" case */
809 142 : gn = COLcopy(g, g->ttype, false, TRANSIENT);
810 142 : if (gn == NULL)
811 0 : goto error;
812 :
813 142 : *groups = gn;
814 142 : if (extents) {
815 0 : en = COLcopy(e, e->ttype, false, TRANSIENT);
816 0 : if (en == NULL)
817 0 : goto error;
818 0 : *extents = en;
819 : }
820 142 : if (histo) {
821 0 : hn = COLcopy(h, h->ttype, false, TRANSIENT);
822 0 : if (hn == NULL)
823 0 : goto error;
824 0 : *histo = hn;
825 : }
826 142 : bat_iterator_end(&bi);
827 142 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
828 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
829 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
830 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
831 : ",histo=" ALGOOPTBATFMT " (copy groups -- "
832 : LLFMT " usec)\n",
833 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
834 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
835 : ALGOOPTBATPAR(h),
836 : subsorted ? "true" : "false",
837 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
838 : ALGOOPTBATPAR(hn), GDKusec() - t0);
839 142 : return GDK_SUCCEED;
840 : }
841 : }
842 29176 : assert(g == NULL || !BATtdense(g)); /* i.e. g->ttype == TYPE_oid */
843 29176 : cmp = ATOMcompare(bi.type);
844 29176 : gn = COLnew(hseqb, TYPE_oid, ci.ncand, TRANSIENT);
845 29176 : if (gn == NULL)
846 0 : goto error;
847 29176 : ngrps = (oid *) Tloc(gn, 0);
848 29176 : maxgrps = BUN_NONE;
849 29176 : MT_rwlock_rdlock(&b->thashlock);
850 29176 : if (b->thash && b->thash != (Hash *) 1)
851 2 : maxgrps = b->thash->nunique;
852 29176 : MT_rwlock_rdunlock(&b->thashlock);
853 29176 : if (maxgrps == BUN_NONE) {
854 29174 : if (bi.unique_est != 0) {
855 2749 : maxgrps = (BUN) bi.unique_est;
856 2749 : if (maxgrps > ci.ncand)
857 : maxgrps = ci.ncand;
858 : } else
859 26425 : maxgrps = ci.ncand / 10;
860 : }
861 29176 : if (!is_oid_nil(maxgrp) && maxgrps < maxgrp)
862 2811 : maxgrps += maxgrp;
863 29176 : if (e && maxgrps < BATcount(e))
864 12 : maxgrps += BATcount(e);
865 29176 : if (h && maxgrps < BATcount(h))
866 0 : maxgrps += BATcount(h);
867 29176 : if (maxgrps < GROUPBATINCR)
868 : maxgrps = GROUPBATINCR;
869 :
870 29176 : if (bi.width <= 2) {
871 5416 : maxgrps = (BUN) 1 << (8 * bi.width);
872 5416 : if (bi.width == 1 && maxgrp < 256)
873 593 : maxgrps *= maxgrp;
874 : }
875 29176 : if (extents) {
876 22921 : en = COLnew(0, TYPE_oid, maxgrps, TRANSIENT);
877 22920 : if (en == NULL)
878 0 : goto error;
879 22920 : exts = (oid *) Tloc(en, 0);
880 : }
881 29175 : if (histo) {
882 6476 : hn = COLnew(0, TYPE_lng, maxgrps, TRANSIENT);
883 6476 : if (hn == NULL)
884 0 : goto error;
885 6476 : cnts = (lng *) Tloc(hn, 0);
886 : }
887 29175 : ngrp = 0;
888 29175 : BATsetcount(gn, ci.ncand);
889 :
890 29176 : hseqb = b->hseqbase; /* abbreviation */
891 :
892 : /* figure out if we can use the storage type also for
893 : * comparing values */
894 29176 : t = ATOMbasetype(bi.type);
895 : /* for strings we can use the offset instead of the actual
896 : * string values if we know that the strings in the string
897 : * heap are unique */
898 29176 : if (t == TYPE_str && GDK_ELIMDOUBLES(bi.vh)) {
899 4764 : switch (bi.width) {
900 : case 1:
901 : t = TYPE_bte;
902 : break;
903 1819 : case 2:
904 1819 : t = TYPE_sht;
905 1819 : break;
906 66 : case 4:
907 66 : t = TYPE_int;
908 66 : break;
909 : #if SIZEOF_VAR_T == 8
910 0 : case 8:
911 0 : t = TYPE_lng;
912 0 : break;
913 : #endif
914 : default:
915 0 : MT_UNREACHABLE();
916 : }
917 : }
918 :
919 29176 : if (g == NULL && t == TYPE_bte) {
920 : /* byte-sized values, use 256 entry array to keep
921 : * track of doled out group ids; note that we can't
922 : * possibly have more than 256 groups, so the group id
923 : * fits in a uint8_t */
924 9626900 : GRP_small_values(8, 8, w[p]);
925 26650 : } else if (t == TYPE_bte && maxgrp < 256) {
926 : /* subgrouping byte-sized values with a limited number
927 : * of groups, use 65536 entry array to keep track of
928 : * doled out group ids; note that we can't possibly have
929 : * more than 65536 goups, so the group id fits in a
930 : * uint16_t */
931 18332353 : GRP_small_values(16, 8, (uint16_t) (w[p] | (grps[p] << 8)));
932 26159 : } else if (g == NULL && t == TYPE_sht) {
933 : /* short-sized values, use 65536 entry array to keep
934 : * track of doled out group ids; note that we can't
935 : * possibly have more than 65536 groups, so the group
936 : * id fits in a uint16_t */
937 5967869 : GRP_small_values(16, 16, w[p]);
938 24921 : } else if (subsorted ||
939 19562 : ((bi.sorted || bi.revsorted) &&
940 241 : (g == NULL || BATordered(g) || BATordered_rev(g)))) {
941 : /* we only need to compare each entry with the previous */
942 12338 : algomsg = "compare consecutive values -- ";
943 12338 : switch (t) {
944 185 : case TYPE_bte:
945 448913 : GRP_compare_consecutive_values_tpe(bte);
946 : break;
947 417 : case TYPE_sht:
948 367167 : GRP_compare_consecutive_values_tpe(sht);
949 : break;
950 9484 : case TYPE_int:
951 82404890 : GRP_compare_consecutive_values_tpe(int);
952 : break;
953 1520 : case TYPE_lng:
954 1001822 : GRP_compare_consecutive_values_tpe(lng);
955 : break;
956 : #ifdef HAVE_HGE
957 645 : case TYPE_hge:
958 417563 : GRP_compare_consecutive_values_tpe(hge);
959 : break;
960 : #endif
961 9 : case TYPE_flt:
962 108 : GRP_compare_consecutive_values_tpe(flt);
963 : break;
964 67 : case TYPE_dbl:
965 36640 : GRP_compare_consecutive_values_tpe(dbl);
966 : break;
967 11 : default:
968 29833 : GRP_compare_consecutive_values_any();
969 : break;
970 : }
971 :
972 12332 : gn->tsorted = true;
973 12332 : *groups = gn;
974 12583 : } else if (bi.sorted || bi.revsorted) {
975 142 : BUN i, j;
976 142 : BUN *pgrp;
977 :
978 142 : assert(g); /* if g == NULL or if there is a single */
979 142 : assert(grps); /* group, we used the code above */
980 : /* for each value, we need to scan all previous equal
981 : * values (a consecutive, possibly empty, range) to
982 : * see if we can find one in the same old group
983 : *
984 : * we do this by maintaining for each old group the
985 : * last time we saw that group, so if the last time we
986 : * saw the old group of the current value is within
987 : * this range, we can reuse the new group */
988 142 : algomsg = "subscan old groups -- ";
989 : /* determine how many old groups there are */
990 142 : if (e) {
991 0 : j = BATcount(e) + (BUN) e->hseqbase;
992 142 : } else if (h) {
993 0 : j = BATcount(h) + (BUN) h->hseqbase;
994 : } else {
995 142 : oid m = 0;
996 23086373 : for (i = 0, j= BATcount(g); i < j; i++)
997 23086231 : m = MAX(m , grps[i]);
998 142 : j = (BUN) m + 1;
999 : }
1000 : /* array to maintain last time we saw each old group */
1001 142 : pgrp = GDKmalloc(sizeof(BUN) * j);
1002 142 : if (pgrp == NULL)
1003 0 : goto error;
1004 : /* initialize to impossible position */
1005 142 : memset(pgrp, ~0, sizeof(BUN) * j);
1006 :
1007 142 : gn->tsorted = true; /* be optimistic */
1008 :
1009 142 : switch (t) {
1010 4 : case TYPE_bte:
1011 10193 : GRP_subscan_old_groups_tpe(bte);
1012 : break;
1013 13 : case TYPE_sht:
1014 133 : GRP_subscan_old_groups_tpe(sht);
1015 : break;
1016 114 : case TYPE_int:
1017 23076909 : GRP_subscan_old_groups_tpe(int);
1018 : break;
1019 3 : case TYPE_lng:
1020 104 : GRP_subscan_old_groups_tpe(lng);
1021 : break;
1022 : #ifdef HAVE_HGE
1023 0 : case TYPE_hge:
1024 0 : GRP_subscan_old_groups_tpe(hge);
1025 : break;
1026 : #endif
1027 2 : case TYPE_flt:
1028 26 : GRP_subscan_old_groups_tpe(flt);
1029 : break;
1030 6 : case TYPE_dbl:
1031 372 : GRP_subscan_old_groups_tpe(dbl);
1032 : break;
1033 0 : default:
1034 0 : GRP_subscan_old_groups_any();
1035 : break;
1036 : }
1037 :
1038 142 : GDKfree(pgrp);
1039 12441 : } else if (g == NULL &&
1040 10869 : (BATcheckhash(b) ||
1041 10869 : ((!bi.transient ||
1042 10869 : (b->batRole == PERSISTENT && GDKinmemory(0))) &&
1043 0 : BAThash(b) == GDK_SUCCEED) ||
1044 : (/* DISABLES CODE */ (0) &&
1045 : (parent = VIEWtparent(b)) != 0 &&
1046 : /* if enabled, need to fix/unfix parent bat */
1047 0 : BATcheckhash(BBP_cache(parent))))) {
1048 : /* we already have a hash table on b, or b is
1049 : * persistent and we could create a hash table, or b
1050 : * is a view on a bat that already has a hash table;
1051 : * but don't do this if we're checking for subgroups
1052 : * since we may have to go through long lists of
1053 : * duplicates in the hash table to find an old
1054 : * group */
1055 0 : bool phash = false;
1056 0 : algomsg = "existing hash -- ";
1057 0 : MT_rwlock_rdlock(&b->thashlock);
1058 0 : if (b->thash == NULL &&
1059 : /* DISABLES CODE */ (0) &&
1060 : (parent = VIEWtparent(b)) != 0) {
1061 : /* b is a view on another bat (b2 for now).
1062 : * calculate the bounds [lo, lo+BATcount(b))
1063 : * in the parent that b uses */
1064 : /* if enabled, need to fix/unfix parent bat */
1065 : BAT *b2 = BBP_cache(parent);
1066 : MT_rwlock_rdunlock(&b->thashlock);
1067 : lo = b->tbaseoff - b2->tbaseoff;
1068 : b = b2;
1069 : bat_iterator_end(&bi);
1070 : bi = bat_iterator(b);
1071 : MT_rwlock_rdlock(&b->thashlock);
1072 : algomsg = "existing parent hash -- ";
1073 : phash = true;
1074 : }
1075 0 : hs = b->thash;
1076 0 : if (hs == NULL) {
1077 0 : MT_rwlock_rdunlock(&b->thashlock);
1078 0 : goto lost_hash;
1079 : }
1080 0 : locked = true;
1081 0 : gn->tsorted = true; /* be optimistic */
1082 :
1083 0 : switch (t) {
1084 0 : case TYPE_bte:
1085 0 : GRP_use_existing_hash_table_tpe(bte);
1086 : break;
1087 0 : case TYPE_sht:
1088 0 : GRP_use_existing_hash_table_tpe(sht);
1089 : break;
1090 0 : case TYPE_int:
1091 0 : GRP_use_existing_hash_table_tpe(int);
1092 : break;
1093 0 : case TYPE_lng:
1094 0 : GRP_use_existing_hash_table_tpe(lng);
1095 : break;
1096 : #ifdef HAVE_HGE
1097 0 : case TYPE_hge:
1098 0 : GRP_use_existing_hash_table_tpe(hge);
1099 : break;
1100 : #endif
1101 0 : case TYPE_flt:
1102 0 : GRP_use_existing_hash_table_tpe(flt);
1103 : break;
1104 0 : case TYPE_dbl:
1105 0 : GRP_use_existing_hash_table_tpe(dbl);
1106 : break;
1107 0 : case TYPE_uuid:
1108 0 : GRP_use_existing_hash_table_tpe(uuid);
1109 : break;
1110 0 : default:
1111 0 : GRP_use_existing_hash_table_any();
1112 : break;
1113 : }
1114 0 : MT_rwlock_rdunlock(&b->thashlock);
1115 0 : locked = false;
1116 : } else {
1117 1572 : bool gc;
1118 1572 : const char *nme;
1119 1572 : BUN prb;
1120 1572 : int bits;
1121 1572 : BUN nbucket;
1122 1572 : oid grp;
1123 :
1124 1572 : lost_hash:
1125 1572 : gc = g != NULL && (BATordered(g) || BATordered_rev(g));
1126 12440 : bits = 0;
1127 12440 : GDKclrerr(); /* not interested in BAThash errors */
1128 :
1129 : /* not sorted, and no pre-existing hash table: we'll
1130 : * build an incomplete hash table on the fly--also see
1131 : * BATassertProps for similar code; we also exploit if
1132 : * g is clustered */
1133 12441 : algomsg = "new partial hash -- ";
1134 12441 : nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
1135 12440 : if (grps && !gc) {
1136 : /* we manipulate the hash value after having
1137 : * calculated it, and when doing that, we
1138 : * assume the mask (i.e. nbucket-1) is a
1139 : * power-of-two minus one, so make sure it
1140 : * is */
1141 1170 : nbucket = ci.ncand | ci.ncand >> 1;
1142 1170 : nbucket |= nbucket >> 2;
1143 1170 : nbucket |= nbucket >> 4;
1144 1170 : nbucket |= nbucket >> 8;
1145 1170 : nbucket |= nbucket >> 16;
1146 : #if SIZEOF_BUN == 8
1147 1170 : nbucket |= nbucket >> 32;
1148 : #endif
1149 1170 : nbucket++;
1150 : } else {
1151 11270 : nbucket = MAX(HASHmask(ci.ncand), 1 << 16);
1152 : }
1153 12440 : if (grps == NULL || is_oid_nil(maxgrp)
1154 : #if SIZEOF_OID == SIZEOF_LNG
1155 1572 : || maxgrp >= ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1156 : #endif
1157 : ) {
1158 10868 : switch (t) {
1159 : case TYPE_bte:
1160 12440 : nbucket = 256;
1161 : break;
1162 0 : case TYPE_sht:
1163 0 : nbucket = 65536;
1164 0 : break;
1165 : default:
1166 : break;
1167 : }
1168 : }
1169 : /* nbucket is a power of two, so ctz(nbucket)
1170 : * tells us which power of two */
1171 12440 : bits = 8 * SIZEOF_OID - ctz(nbucket);
1172 12440 : if ((hs = GDKzalloc(sizeof(Hash))) == NULL ||
1173 12441 : (hs->heaplink.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
1174 12440 : (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0) {
1175 0 : GDKfree(hs);
1176 0 : hs = NULL;
1177 0 : GDKerror("cannot allocate hash table\n");
1178 0 : goto error;
1179 : }
1180 12440 : hs->heapbckt.parentid = b->batCacheid;
1181 12440 : hs->heaplink.parentid = b->batCacheid;
1182 12440 : if (snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshgrpl%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heaplink.filename) ||
1183 24881 : snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshgrpb%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heapbckt.filename) ||
1184 12441 : HASHnew(hs, bi.type, BATcount(b), nbucket, BUN_NONE, false) != GDK_SUCCEED) {
1185 0 : GDKfree(hs);
1186 0 : hs = NULL;
1187 0 : GDKerror("cannot allocate hash table\n");
1188 0 : goto error;
1189 : }
1190 12439 : gn->tsorted = true; /* be optimistic */
1191 :
1192 12439 : switch (t) {
1193 24 : case TYPE_bte:
1194 24 : if (grps && !is_oid_nil(maxgrp)
1195 : #if SIZEOF_OID == SIZEOF_LNG
1196 24 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1197 : #endif
1198 : ) {
1199 24 : ulng v;
1200 24 : const bte *w = (bte *) bi.base;
1201 257614 : GRP_create_partial_hash_table_core(
1202 : (void) 0,
1203 : (v = ((ulng)grps[r]<<8)|(uint8_t)w[p], hash_lng(hs, &v)),
1204 : w[p] == w[hb] && grps[r] == grps[q],
1205 : (void) 0,
1206 : NOGRPTST);
1207 : } else
1208 0 : GRP_create_partial_hash_table_tpe(bte);
1209 : break;
1210 513 : case TYPE_sht:
1211 513 : if (grps && !is_oid_nil(maxgrp)
1212 : #if SIZEOF_OID == SIZEOF_LNG
1213 513 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 16))
1214 : #endif
1215 : ) {
1216 513 : ulng v;
1217 513 : const sht *w = (sht *) bi.base;
1218 32421737 : GRP_create_partial_hash_table_core(
1219 : (void) 0,
1220 : (v = ((ulng)grps[r]<<16)|(uint16_t)w[p], hash_lng(hs, &v)),
1221 : w[p] == w[hb] && grps[r] == grps[q],
1222 : (void) 0,
1223 : NOGRPTST);
1224 : } else
1225 0 : GRP_create_partial_hash_table_tpe(sht);
1226 : break;
1227 11313 : case TYPE_int:
1228 11313 : if (grps && !is_oid_nil(maxgrp)
1229 : #if SIZEOF_OID == SIZEOF_LNG
1230 822 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 32))
1231 : #endif
1232 : ) {
1233 822 : ulng v;
1234 822 : const int *w = (int *) bi.base;
1235 120274492 : GRP_create_partial_hash_table_core(
1236 : (void) 0,
1237 : (v = ((ulng)grps[r]<<32)|(unsigned int)w[p], hash_lng(hs, &v)),
1238 : w[p] == w[hb] && grps[r] == grps[q],
1239 : (void) 0,
1240 : NOGRPTST);
1241 : } else
1242 83678396 : GRP_create_partial_hash_table_tpe(int);
1243 : break;
1244 197 : case TYPE_lng:
1245 : #ifdef HAVE_HGE
1246 197 : if (grps) {
1247 16 : uhge v;
1248 16 : const lng *w = (lng *) bi.base;
1249 1999919 : GRP_create_partial_hash_table_core(
1250 : (void) 0,
1251 : (v = ((uhge)grps[r]<<64)|(ulng)w[p], hash_hge(hs, &v)),
1252 : w[p] == w[hb] && grps[r] == grps[q],
1253 : (void) 0,
1254 : NOGRPTST);
1255 : } else
1256 : #endif
1257 107024 : GRP_create_partial_hash_table_tpe(lng);
1258 : break;
1259 : #ifdef HAVE_HGE
1260 21 : case TYPE_hge:
1261 57801810 : GRP_create_partial_hash_table_tpe(hge);
1262 : break;
1263 : #endif
1264 15 : case TYPE_flt:
1265 729 : GRP_create_partial_hash_table_tpe(flt);
1266 : break;
1267 115 : case TYPE_dbl:
1268 36405 : GRP_create_partial_hash_table_tpe(dbl);
1269 : break;
1270 8 : case TYPE_uuid:
1271 86 : GRP_create_partial_hash_table_tpe(uuid);
1272 : break;
1273 233 : default:
1274 79471445 : GRP_create_partial_hash_table_any();
1275 : }
1276 :
1277 12440 : HEAPfree(&hs->heapbckt, true);
1278 12441 : HEAPfree(&hs->heaplink, true);
1279 12441 : GDKfree(hs);
1280 : }
1281 29170 : bat_iterator_end(&bi);
1282 29174 : if (extents) {
1283 22920 : BATsetcount(en, (BUN) ngrp);
1284 22921 : en->tkey = true;
1285 22921 : en->tsorted = true;
1286 22921 : en->trevsorted = ngrp == 1;
1287 22921 : en->tnonil = true;
1288 22921 : en->tnil = false;
1289 22921 : *extents = virtualize(en);
1290 : }
1291 29175 : if (histo) {
1292 6475 : BATsetcount(hn, (BUN) ngrp);
1293 6476 : if (ngrp == ci.ncand || ngrp == 1) {
1294 4039 : hn->tkey = ngrp == 1;
1295 4039 : hn->tsorted = true;
1296 4039 : hn->trevsorted = true;
1297 : } else {
1298 2437 : hn->tkey = false;
1299 2437 : hn->tsorted = false;
1300 2437 : hn->trevsorted = false;
1301 : }
1302 6476 : hn->tnonil = true;
1303 6476 : hn->tnil = false;
1304 6476 : *histo = hn;
1305 : }
1306 29176 : gn->tkey = ngrp == BATcount(gn);
1307 29176 : gn->trevsorted = ngrp == 1 || BATcount(gn) <= 1;
1308 29176 : gn->tnonil = true;
1309 29176 : gn->tnil = false;
1310 29176 : gn->tmaxpos = maxgrppos;
1311 29176 : *groups = gn;
1312 29176 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1313 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
1314 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
1315 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
1316 : ",histo=" ALGOOPTBATFMT " (%s" LLFMT " usec)\n",
1317 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
1318 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
1319 : ALGOOPTBATPAR(h),
1320 : subsorted ? "true" : "false",
1321 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
1322 : ALGOOPTBATPAR(hn), algomsg, GDKusec() - t0);
1323 : return GDK_SUCCEED;
1324 0 : error:
1325 0 : bat_iterator_end(&bi);
1326 0 : if (hs != NULL && hs != b->thash) {
1327 0 : HEAPfree(&hs->heaplink, true);
1328 0 : HEAPfree(&hs->heapbckt, true);
1329 0 : GDKfree(hs);
1330 : }
1331 0 : if (locked)
1332 0 : MT_rwlock_rdunlock(&b->thashlock);
1333 0 : BBPreclaim(gn);
1334 0 : BBPreclaim(en);
1335 0 : BBPreclaim(hn);
1336 : return GDK_FAIL;
1337 : }
1338 :
1339 : gdk_return
1340 56056 : BATgroup(BAT **groups, BAT **extents, BAT **histo,
1341 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
1342 : {
1343 56056 : return BATgroup_internal(groups, extents, histo, b, s, g, e, h, false);
1344 : }
|
