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, qry_ctx) { \
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(qry_ctx, \
123 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
124 : } else { \
125 : MT_thread_setalgorithm("GRP_compare_consecutive_values, dense, !groups"); \
126 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
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(qry_ctx, \
139 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
140 : } \
141 : } else { \
142 : if (grps) { \
143 : MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, groups"); \
144 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
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(qry_ctx, \
158 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
159 : } else { \
160 : MT_thread_setalgorithm("GRP_compare_consecutive_values, !dense, !groups"); \
161 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
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(qry_ctx, \
174 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
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, qry_ctx) { \
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(qry_ctx, \
251 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
252 : } else { \
253 : MT_thread_setalgorithm("GRP_subscan_old_groups, !dense"); \
254 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
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(qry_ctx, \
293 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
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, qry_ctx) { \
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(qry_ctx, \
381 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
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, qry_ctx) { \
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(qry_ctx, \
417 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
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 38978005 : rev(oid x)
438 : {
439 : #if SIZEOF_OID == 8
440 38978005 : x = ((x & 0x5555555555555555) << 1) | ((x >> 1) & 0x5555555555555555);
441 38978005 : x = ((x & 0x3333333333333333) << 2) | ((x >> 2) & 0x3333333333333333);
442 38978005 : x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F0F0F0F0F);
443 38978005 : x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF00FF00FF);
444 38978005 : x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF0000FFFF);
445 38978005 : 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 38978005 : return x;
454 : }
455 :
456 : /* count trailing zeros, also see candmask_lobit in gdk_cand.h */
457 : static inline int __attribute__((__const__))
458 13943 : ctz(oid x)
459 : {
460 : #ifdef __has_builtin
461 : #if SIZEOF_OID == SIZEOF_INT && __has_builtin(__builtin_ctz)
462 : return __builtin_ctz(x);
463 : #define BUILTIN_USED
464 : #elif __has_builtin(__builtin_ctzl)
465 13943 : return __builtin_ctzl(x);
466 : #define BUILTIN_USED
467 : #endif
468 : #endif
469 : #ifndef BUILTIN_USED
470 : #if defined(_MSC_VER)
471 : #if SIZEOF_OID == SIZEOF_INT
472 : unsigned long idx;
473 : if (_BitScanForward(&idx, (unsigned long) x))
474 : return (int) idx;
475 : #else
476 : unsigned long idx;
477 : if (_BitScanForward64(&idx, (unsigned __int64) x))
478 : return (int) idx;
479 : #endif
480 : return -1;
481 : #else
482 : /* use binary search for the lowest set bit */
483 : int n = 1;
484 : #if SIZEOF_OID == SIZEOF_INT
485 : if ((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
486 : if ((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
487 : if ((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
488 : if ((x & 0x00000003) == 0) { n += 2; x >>= 2; }
489 : #else
490 : if ((x & UINT64_C(0x00000000FFFFFFFF)) == 0) { n += 32; x >>= 32; }
491 : if ((x & UINT64_C(0x000000000000FFFF)) == 0) { n += 16; x >>= 16; }
492 : if ((x & UINT64_C(0x00000000000000FF)) == 0) { n += 8; x >>= 8; }
493 : if ((x & UINT64_C(0x000000000000000F)) == 0) { n += 4; x >>= 4; }
494 : if ((x & UINT64_C(0x0000000000000003)) == 0) { n += 2; x >>= 2; }
495 : #endif
496 : return n - (x & 1);
497 : #endif
498 : #endif
499 : #undef BUILTIN_USED
500 : }
501 :
502 : #define GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,ASSERT,GRPTST) \
503 : do { \
504 : if (ci.tpe == cand_dense) { \
505 : MT_thread_setalgorithm("GRP_create_partial_hash_table, dense"); \
506 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
507 : p = canditer_next_dense(&ci) - hseqb; \
508 : INIT_1; \
509 : prb = HASH; \
510 : for (hb = HASHget(hs, prb); \
511 : hb != BUN_NONE; \
512 : hb = HASHgetlink(hs, hb)) { \
513 : ASSERT; \
514 : q = canditer_search_dense(&ci, hb + hseqb, false); \
515 : if (q == BUN_NONE) \
516 : continue; \
517 : GRPTST(q, r); \
518 : if (EQUAL) { \
519 : grp = ngrps[q]; \
520 : ngrps[r] = grp; \
521 : if (histo) \
522 : cnts[grp]++; \
523 : if (gn->tsorted && \
524 : grp != ngrp - 1) \
525 : gn->tsorted = false; \
526 : break; \
527 : } \
528 : } \
529 : if (hb == BUN_NONE) { \
530 : GRPnotfound(); \
531 : /* enter new group into hash table */ \
532 : HASHputlink(hs, p, HASHget(hs, prb)); \
533 : HASHput(hs, prb, p); \
534 : } \
535 : } \
536 : TIMEOUT_CHECK(qry_ctx, \
537 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
538 : } else { \
539 : MT_thread_setalgorithm("GRP_create_partial_hash_table, !dense"); \
540 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
541 : p = canditer_next(&ci) - hseqb; \
542 : INIT_1; \
543 : prb = HASH; \
544 : for (hb = HASHget(hs, prb); \
545 : hb != BUN_NONE; \
546 : hb = HASHgetlink(hs, hb)) { \
547 : ASSERT; \
548 : q = canditer_search(&ci, hb + hseqb, false); \
549 : if (q == BUN_NONE) \
550 : continue; \
551 : GRPTST(q, r); \
552 : if (EQUAL) { \
553 : grp = ngrps[q]; \
554 : ngrps[r] = grp; \
555 : if (histo) \
556 : cnts[grp]++; \
557 : if (gn->tsorted && \
558 : grp != ngrp - 1) \
559 : gn->tsorted = false; \
560 : break; \
561 : } \
562 : } \
563 : if (hb == BUN_NONE) { \
564 : GRPnotfound(); \
565 : /* enter new group into hash table */ \
566 : HASHputlink(hs, p, HASHget(hs, prb)); \
567 : HASHput(hs, prb, p); \
568 : } \
569 : } \
570 : TIMEOUT_CHECK(qry_ctx, \
571 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
572 : } \
573 : } while (0)
574 : #define GCGRPTST(i, j) if (grps[i] != grps[j]) { hb = BUN_NONE; break; }
575 : #define GRPTST(i, j) if (grps[i] != grps[j]) continue
576 : #define NOGRPTST(i, j) (void) 0
577 : #define GRP_create_partial_hash_table(INIT_0,INIT_1,HASH,EQUAL) \
578 : do { \
579 : INIT_0; \
580 : if (grps) { \
581 : if (gc) { \
582 : GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,assert(HASHgetlink(hs, hb) == BUN_NONE || HASHgetlink(hs, hb) < hb),GCGRPTST); \
583 : } else { \
584 : GRP_create_partial_hash_table_core(INIT_1,HASH ^ (rev(grps[r]) >> bits),EQUAL,(void)0,GRPTST); \
585 : } \
586 : } else { \
587 : GRP_create_partial_hash_table_core(INIT_1,HASH,EQUAL,(void)0,NOGRPTST); \
588 : } \
589 : } while (0)
590 :
591 : #define GRP_create_partial_hash_table_tpe(TYPE) \
592 : GRP_create_partial_hash_table( \
593 : /* INIT_0 */ const TYPE *w = (TYPE *) bi.base, \
594 : /* INIT_1 */ , \
595 : /* HASH */ hash_##TYPE(hs, &w[p]) , \
596 : /* EQUAL */ TYPE##_equ(w[p], w[hb]) \
597 : )
598 :
599 : #define GRP_create_partial_hash_table_any() \
600 : GRP_create_partial_hash_table( \
601 : /* INIT_0 */ , \
602 : /* INIT_1 */ v = BUNtail(bi, p) , \
603 : /* HASH */ hash_any(hs, v) , \
604 : /* EQUAL */ cmp(v, BUNtail(bi, hb)) == 0 \
605 : )
606 :
607 : #define GRP_small_values(BG, BV, GV) \
608 : do { \
609 : uint##BG##_t sgrps[1 << BG]; \
610 : const uint##BV##_t *restrict w = (const uint##BV##_t *) bi.base; \
611 : uint##BG##_t v; \
612 : memset(sgrps, 0xFF, sizeof(sgrps)); \
613 : if (histo) \
614 : memset(cnts, 0, maxgrps * sizeof(lng)); \
615 : ngrp = 0; \
616 : gn->tsorted = true; \
617 : if (ci.tpe == cand_dense) { \
618 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
619 : oid o = canditer_next_dense(&ci); \
620 : p = o - hseqb; \
621 : uint##BG##_t x = GV; \
622 : if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
623 : sgrps[x] = v = (uint##BG##_t) ngrp++; \
624 : maxgrppos = r; \
625 : if (extents) \
626 : exts[v] = o; \
627 : } \
628 : ngrps[r] = v; \
629 : if (r > 0 && v < ngrps[r - 1]) \
630 : gn->tsorted = false; \
631 : if (histo) \
632 : cnts[v]++; \
633 : } \
634 : } else { \
635 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
636 : oid o = canditer_next(&ci); \
637 : p = o - hseqb; \
638 : uint##BG##_t x = GV; \
639 : if ((v = sgrps[x]) == (uint##BG##_t) ~0 && ngrp < (1 << BG)) { \
640 : sgrps[x] = v = (uint##BG##_t) ngrp++; \
641 : maxgrppos = r; \
642 : if (extents) \
643 : exts[v] = o; \
644 : } \
645 : ngrps[r] = v; \
646 : if (r > 0 && v < ngrps[r - 1]) \
647 : gn->tsorted = false; \
648 : if (histo) \
649 : cnts[v]++; \
650 : } \
651 : } \
652 : TIMEOUT_CHECK(qry_ctx, \
653 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
654 : } while (0)
655 :
656 : gdk_return
657 97102 : BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
658 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h, bool subsorted)
659 : {
660 97102 : BAT *gn = NULL, *en = NULL, *hn = NULL;
661 97102 : int t;
662 97102 : int (*cmp)(const void *, const void *);
663 97102 : const oid *grps = NULL;
664 97102 : oid *restrict ngrps, ngrp, prev = 0, hseqb = 0;
665 97102 : oid *restrict exts = NULL;
666 97102 : lng *restrict cnts = NULL;
667 97102 : BUN p, q, r;
668 97102 : const void *v, *pv;
669 97102 : BATiter bi;
670 97102 : Hash *hs = NULL;
671 97102 : BUN hb;
672 97102 : BUN maxgrps;
673 97102 : BUN maxgrppos = BUN_NONE;
674 97102 : bat parent;
675 97102 : BUN lo = 0;
676 97102 : struct canditer ci;
677 97102 : oid maxgrp = oid_nil; /* maximum value of g BAT (if subgrouping) */
678 97102 : lng t0 = 0;
679 97102 : const char *algomsg = "";
680 97102 : bool locked = false;
681 :
682 97102 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
683 :
684 97119 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
685 97119 : if (b == NULL) {
686 0 : GDKerror("b must exist\n");
687 0 : return GDK_FAIL;
688 : }
689 97119 : assert(s == NULL || BATttype(s) == TYPE_oid);
690 97119 : canditer_init(&ci, b, s);
691 97555 : bi = bat_iterator(b);
692 :
693 : /* g is NULL or [oid(dense),oid] and same size as b or s */
694 97231 : assert(g == NULL || BATttype(g) == TYPE_oid || BATcount(g) == 0);
695 30094 : assert(g == NULL || BATcount(g) == ci.ncand);
696 30094 : assert(g == NULL || BATcount(b) == 0 || (s ? g->hseqbase == s->hseqbase : g->hseqbase == b->hseqbase));
697 : /* e is NULL or [oid(dense),oid] */
698 97231 : assert(e == NULL || BATttype(e) == TYPE_oid);
699 : /* h is NULL or [oid(dense),lng] */
700 97231 : assert(h == NULL || h->ttype == TYPE_lng);
701 : /* e and h are aligned */
702 97231 : assert(e == NULL || h == NULL || BATcount(e) == BATcount(h));
703 97231 : assert(e == NULL || h == NULL || e->hseqbase == h->hseqbase);
704 : /* we want our output to go somewhere */
705 97231 : assert(groups != NULL);
706 :
707 97231 : if (ci.ncand == 0) {
708 : hseqb = 0;
709 : } else {
710 63358 : hseqb = ci.seq;
711 : }
712 97231 : if (bi.key || ci.ncand <= 1 || (g && (g->tkey || BATtdense(g)))) {
713 : /* grouping is trivial: 1 element per group */
714 53240 : gn = BATdense(hseqb, 0, BATcount(b));
715 53246 : if (gn == NULL)
716 0 : goto error;
717 53246 : *groups = gn;
718 53246 : if (extents) {
719 52862 : en = canditer_slice(&ci, 0, ci.ncand);
720 52861 : if (en == NULL)
721 0 : goto error;
722 52861 : *extents = en;
723 : }
724 53245 : if (histo) {
725 1379 : hn = BATconstant(0, TYPE_lng, &(lng){1}, ci.ncand, TRANSIENT);
726 1379 : if (hn == NULL)
727 0 : goto error;
728 1379 : *histo = hn;
729 : }
730 53245 : bat_iterator_end(&bi);
731 53281 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
732 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
733 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
734 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
735 : ",histo=" ALGOOPTBATFMT " (1 element per group -- "
736 : LLFMT " usec)\n",
737 : ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOOPTBATPAR(g),
738 : ALGOOPTBATPAR(e), ALGOOPTBATPAR(h),
739 : subsorted ? "true" : "false", ALGOOPTBATPAR(gn),
740 : ALGOOPTBATPAR(en), ALGOOPTBATPAR(hn), GDKusec() - t0);
741 53281 : return GDK_SUCCEED;
742 : }
743 43991 : assert(!BATtdense(b));
744 43991 : if (g) {
745 8432 : assert(!BATtdense(g));
746 8432 : if (g->tsorted)
747 5681 : maxgrp = * (oid *) Tloc(g, BATcount(g) - 1);
748 2751 : else if (g->trevsorted)
749 0 : maxgrp = * (oid *) Tloc(g, 0);
750 : else {
751 : /* group bats are not modified in parallel, so
752 : * no need for locks */
753 2751 : if (g->tmaxpos != BUN_NONE)
754 2749 : maxgrp = BUNtoid(g, g->tmaxpos);
755 2754 : if (is_oid_nil(maxgrp) /* && BATcount(g) < 10240 */) {
756 3 : BATmax(g, &maxgrp);
757 : }
758 : }
759 8435 : if (maxgrp == 0)
760 : g = NULL; /* single group */
761 : else
762 6300 : grps = (const oid *) Tloc(g, 0);
763 : }
764 43994 : (void) BATordered(b);
765 44237 : (void) BATordered_rev(b);
766 44242 : bat_iterator_end(&bi);
767 44247 : bi = bat_iterator(b);
768 44006 : if (bi.sorted && bi.revsorted) {
769 : /* all values are equal */
770 4427 : if (g == NULL || (BATordered(g) && BATordered_rev(g))) {
771 : /* there's only a single group: 0 */
772 3955 : gn = BATconstant(hseqb, TYPE_oid, &(oid){0}, ci.ncand, TRANSIENT);
773 3935 : if (gn == NULL)
774 0 : goto error;
775 3935 : *groups = gn;
776 3935 : if (extents) {
777 3031 : en = BATdense(0, canditer_next(&ci), 1);
778 3047 : if (en == NULL)
779 0 : goto error;
780 3047 : *extents = en;
781 : }
782 3951 : if (histo) {
783 49 : hn = BATconstant(0, TYPE_lng, &(lng){(lng)ci.ncand}, 1, TRANSIENT);
784 49 : if (hn == NULL)
785 0 : goto error;
786 49 : *histo = hn;
787 : }
788 3951 : bat_iterator_end(&bi);
789 3956 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
790 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
791 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
792 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
793 : ",histo=" ALGOOPTBATFMT " (single group -- "
794 : LLFMT " usec)\n",
795 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
796 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
797 : ALGOOPTBATPAR(h),
798 : subsorted ? "true" : "false",
799 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
800 : ALGOOPTBATPAR(hn), GDKusec() - t0);
801 3956 : return GDK_SUCCEED;
802 : }
803 472 : if ((extents == NULL || e != NULL) &&
804 134 : (histo == NULL || h != NULL) &&
805 134 : ci.ncand == BATcount(b)) {
806 : /* inherit given grouping; note that if
807 : * extents/histo is to be returned, we need
808 : * e/h available in order to copy them,
809 : * otherwise we will need to calculate them
810 : * which we will do using the "normal" case */
811 134 : gn = COLcopy(g, g->ttype, false, TRANSIENT);
812 134 : if (gn == NULL)
813 0 : goto error;
814 :
815 134 : *groups = gn;
816 134 : if (extents) {
817 0 : en = COLcopy(e, e->ttype, false, TRANSIENT);
818 0 : if (en == NULL)
819 0 : goto error;
820 0 : *extents = en;
821 : }
822 134 : if (histo) {
823 0 : hn = COLcopy(h, h->ttype, false, TRANSIENT);
824 0 : if (hn == NULL)
825 0 : goto error;
826 0 : *histo = hn;
827 : }
828 134 : bat_iterator_end(&bi);
829 134 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
830 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
831 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
832 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
833 : ",histo=" ALGOOPTBATFMT " (copy groups -- "
834 : LLFMT " usec)\n",
835 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
836 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
837 : ALGOOPTBATPAR(h),
838 : subsorted ? "true" : "false",
839 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
840 : ALGOOPTBATPAR(hn), GDKusec() - t0);
841 134 : return GDK_SUCCEED;
842 : }
843 : }
844 39917 : assert(g == NULL || !BATtdense(g)); /* i.e. g->ttype == TYPE_oid */
845 39917 : cmp = ATOMcompare(bi.type);
846 39917 : gn = COLnew(hseqb, TYPE_oid, ci.ncand, TRANSIENT);
847 40115 : if (gn == NULL)
848 0 : goto error;
849 40115 : ngrps = (oid *) Tloc(gn, 0);
850 40115 : maxgrps = BUN_NONE;
851 40115 : MT_rwlock_rdlock(&b->thashlock);
852 40178 : if (b->thash && b->thash != (Hash *) 1)
853 3 : maxgrps = b->thash->nunique;
854 40178 : MT_rwlock_rdunlock(&b->thashlock);
855 39910 : if (maxgrps == BUN_NONE) {
856 40041 : if (bi.unique_est != 0) {
857 5249 : maxgrps = (BUN) bi.unique_est;
858 5249 : if (maxgrps > ci.ncand)
859 : maxgrps = ci.ncand;
860 : } else
861 34792 : maxgrps = ci.ncand / 10;
862 : }
863 39910 : if (!is_oid_nil(maxgrp) && maxgrps < maxgrp)
864 3797 : maxgrps += maxgrp;
865 39910 : if (e && maxgrps < BATcount(e))
866 12 : maxgrps += BATcount(e);
867 39910 : if (h && maxgrps < BATcount(h))
868 0 : maxgrps += BATcount(h);
869 39910 : if (maxgrps < GROUPBATINCR)
870 : maxgrps = GROUPBATINCR;
871 :
872 39910 : if (bi.width <= 2) {
873 8836 : maxgrps = (BUN) 1 << (8 * bi.width);
874 8836 : if (bi.width == 1 && maxgrp < 256)
875 831 : maxgrps *= maxgrp;
876 : }
877 39910 : if (extents) {
878 33467 : en = COLnew(0, TYPE_oid, maxgrps, TRANSIENT);
879 33706 : if (en == NULL)
880 0 : goto error;
881 33706 : exts = (oid *) Tloc(en, 0);
882 : }
883 40149 : if (histo) {
884 8380 : hn = COLnew(0, TYPE_lng, maxgrps, TRANSIENT);
885 8380 : if (hn == NULL)
886 0 : goto error;
887 8380 : cnts = (lng *) Tloc(hn, 0);
888 : }
889 40149 : ngrp = 0;
890 40149 : BATsetcount(gn, ci.ncand);
891 :
892 39954 : hseqb = b->hseqbase; /* abbreviation */
893 :
894 : /* figure out if we can use the storage type also for
895 : * comparing values */
896 39954 : t = ATOMbasetype(bi.type);
897 : /* for strings we can use the offset instead of the actual
898 : * string values if we know that the strings in the string
899 : * heap are unique */
900 39954 : if (t == TYPE_str && GDK_ELIMDOUBLES(bi.vh)) {
901 6419 : switch (bi.width) {
902 : case 1:
903 : t = TYPE_bte;
904 : break;
905 3043 : case 2:
906 3043 : t = TYPE_sht;
907 3043 : break;
908 54 : case 4:
909 54 : t = TYPE_int;
910 54 : break;
911 : #if SIZEOF_VAR_T == 8
912 0 : case 8:
913 0 : t = TYPE_lng;
914 0 : break;
915 : #endif
916 : default:
917 0 : MT_UNREACHABLE();
918 : }
919 : }
920 :
921 39954 : if (g == NULL && t == TYPE_bte) {
922 : /* byte-sized values, use 256 entry array to keep
923 : * track of doled out group ids; note that we can't
924 : * possibly have more than 256 groups, so the group id
925 : * fits in a uint8_t */
926 8656423 : GRP_small_values(8, 8, w[p]);
927 37157 : } else if (t == TYPE_bte && maxgrp < 256) {
928 : /* subgrouping byte-sized values with a limited number
929 : * of groups, use 65536 entry array to keep track of
930 : * doled out group ids; note that we can't possibly have
931 : * more than 65536 groups, so the group id fits in a
932 : * uint16_t */
933 17952099 : GRP_small_values(16, 8, (uint16_t) (w[p] | (grps[p] << 8)));
934 36476 : } else if (g == NULL && t == TYPE_sht) {
935 : /* short-sized values, use 65536 entry array to keep
936 : * track of doled out group ids; note that we can't
937 : * possibly have more than 65536 groups, so the group
938 : * id fits in a uint16_t */
939 7820805 : GRP_small_values(16, 16, w[p]);
940 32796 : } else if (subsorted ||
941 27413 : ((bi.sorted || bi.revsorted) &&
942 502 : (g == NULL || BATordered(g) || BATordered_rev(g)))) {
943 : /* we only need to compare each entry with the previous */
944 18498 : algomsg = "compare consecutive values -- ";
945 18498 : switch (t) {
946 325 : case TYPE_bte:
947 606855 : GRP_compare_consecutive_values_tpe(bte);
948 : break;
949 460 : case TYPE_sht:
950 442431 : GRP_compare_consecutive_values_tpe(sht);
951 : break;
952 16218 : case TYPE_int:
953 81611846 : GRP_compare_consecutive_values_tpe(int);
954 : break;
955 1333 : case TYPE_lng:
956 783870 : GRP_compare_consecutive_values_tpe(lng);
957 : break;
958 : #ifdef HAVE_HGE
959 68 : case TYPE_hge:
960 4710 : GRP_compare_consecutive_values_tpe(hge);
961 : break;
962 : #endif
963 9 : case TYPE_flt:
964 108 : GRP_compare_consecutive_values_tpe(flt);
965 : break;
966 69 : case TYPE_dbl:
967 385094 : GRP_compare_consecutive_values_tpe(dbl);
968 : break;
969 16 : default:
970 34269 : GRP_compare_consecutive_values_any();
971 : break;
972 : }
973 :
974 18649 : gn->tsorted = true;
975 18649 : *groups = gn;
976 14298 : } else if (bi.sorted || bi.revsorted) {
977 361 : BUN i, j;
978 361 : BUN *pgrp;
979 :
980 361 : assert(g); /* if g == NULL or if there is a single */
981 361 : assert(grps); /* group, we used the code above */
982 : /* for each value, we need to scan all previous equal
983 : * values (a consecutive, possibly empty, range) to
984 : * see if we can find one in the same old group
985 : *
986 : * we do this by maintaining for each old group the
987 : * last time we saw that group, so if the last time we
988 : * saw the old group of the current value is within
989 : * this range, we can reuse the new group */
990 361 : algomsg = "subscan old groups -- ";
991 : /* determine how many old groups there are */
992 361 : if (e) {
993 0 : j = BATcount(e) + (BUN) e->hseqbase;
994 361 : } else if (h) {
995 0 : j = BATcount(h) + (BUN) h->hseqbase;
996 : } else {
997 361 : oid m = 0;
998 23411139 : for (i = 0, j= BATcount(g); i < j; i++)
999 23410778 : m = MAX(m , grps[i]);
1000 361 : j = (BUN) m + 1;
1001 : }
1002 : /* array to maintain last time we saw each old group */
1003 361 : pgrp = GDKmalloc(sizeof(BUN) * j);
1004 361 : if (pgrp == NULL)
1005 0 : goto error;
1006 : /* initialize to impossible position */
1007 361 : memset(pgrp, ~0, sizeof(BUN) * j);
1008 :
1009 361 : gn->tsorted = true; /* be optimistic */
1010 :
1011 361 : switch (t) {
1012 6 : case TYPE_bte:
1013 59154 : GRP_subscan_old_groups_tpe(bte);
1014 : break;
1015 5 : case TYPE_sht:
1016 62 : GRP_subscan_old_groups_tpe(sht);
1017 : break;
1018 338 : case TYPE_int:
1019 23353434 : GRP_subscan_old_groups_tpe(int);
1020 : break;
1021 2 : case TYPE_lng:
1022 98 : GRP_subscan_old_groups_tpe(lng);
1023 : break;
1024 : #ifdef HAVE_HGE
1025 0 : case TYPE_hge:
1026 0 : GRP_subscan_old_groups_tpe(hge);
1027 : break;
1028 : #endif
1029 2 : case TYPE_flt:
1030 26 : GRP_subscan_old_groups_tpe(flt);
1031 : break;
1032 8 : case TYPE_dbl:
1033 346 : GRP_subscan_old_groups_tpe(dbl);
1034 : break;
1035 0 : default:
1036 0 : GRP_subscan_old_groups_any();
1037 : break;
1038 : }
1039 :
1040 362 : GDKfree(pgrp);
1041 13937 : } else if (g == NULL &&
1042 11294 : (BATcheckhash(b) ||
1043 11300 : ((!bi.transient ||
1044 11300 : (b->batRole == PERSISTENT && GDKinmemory(0))) &&
1045 0 : BAThash(b) == GDK_SUCCEED) ||
1046 : (/* DISABLES CODE */ (0) &&
1047 : (parent = VIEWtparent(b)) != 0 &&
1048 : /* if enabled, need to fix/unfix parent bat */
1049 0 : BATcheckhash(BBP_desc(parent))))) {
1050 : /* we already have a hash table on b, or b is
1051 : * persistent and we could create a hash table, or b
1052 : * is a view on a bat that already has a hash table;
1053 : * but don't do this if we're checking for subgroups
1054 : * since we may have to go through long lists of
1055 : * duplicates in the hash table to find an old
1056 : * group */
1057 0 : bool phash = false;
1058 0 : algomsg = "existing hash -- ";
1059 0 : MT_rwlock_rdlock(&b->thashlock);
1060 0 : if (b->thash == NULL &&
1061 : /* DISABLES CODE */ (0) &&
1062 : (parent = VIEWtparent(b)) != 0) {
1063 : /* b is a view on another bat (b2 for now).
1064 : * calculate the bounds [lo, lo+BATcount(b))
1065 : * in the parent that b uses */
1066 : /* if enabled, need to fix/unfix parent bat */
1067 : BAT *b2 = BBP_desc(parent);
1068 : MT_rwlock_rdunlock(&b->thashlock);
1069 : lo = b->tbaseoff - b2->tbaseoff;
1070 : b = b2;
1071 : bat_iterator_end(&bi);
1072 : bi = bat_iterator(b);
1073 : MT_rwlock_rdlock(&b->thashlock);
1074 : algomsg = "existing parent hash -- ";
1075 : phash = true;
1076 : }
1077 0 : hs = b->thash;
1078 0 : if (hs == NULL) {
1079 0 : MT_rwlock_rdunlock(&b->thashlock);
1080 0 : goto lost_hash;
1081 : }
1082 0 : locked = true;
1083 0 : gn->tsorted = true; /* be optimistic */
1084 :
1085 0 : switch (t) {
1086 0 : case TYPE_bte:
1087 0 : GRP_use_existing_hash_table_tpe(bte);
1088 : break;
1089 0 : case TYPE_sht:
1090 0 : GRP_use_existing_hash_table_tpe(sht);
1091 : break;
1092 0 : case TYPE_int:
1093 0 : GRP_use_existing_hash_table_tpe(int);
1094 : break;
1095 0 : case TYPE_lng:
1096 0 : GRP_use_existing_hash_table_tpe(lng);
1097 : break;
1098 : #ifdef HAVE_HGE
1099 0 : case TYPE_hge:
1100 0 : GRP_use_existing_hash_table_tpe(hge);
1101 : break;
1102 : #endif
1103 0 : case TYPE_flt:
1104 0 : GRP_use_existing_hash_table_tpe(flt);
1105 : break;
1106 0 : case TYPE_dbl:
1107 0 : GRP_use_existing_hash_table_tpe(dbl);
1108 : break;
1109 0 : case TYPE_uuid:
1110 0 : GRP_use_existing_hash_table_tpe(uuid);
1111 : break;
1112 0 : default:
1113 0 : GRP_use_existing_hash_table_any();
1114 : break;
1115 : }
1116 0 : MT_rwlock_rdunlock(&b->thashlock);
1117 0 : locked = false;
1118 : } else {
1119 2643 : bool gc;
1120 2643 : const char *nme;
1121 2643 : BUN prb;
1122 2643 : int bits;
1123 2643 : BUN nbucket;
1124 2643 : oid grp;
1125 :
1126 2643 : lost_hash:
1127 2643 : gc = g != NULL && (BATordered(g) || BATordered_rev(g));
1128 13939 : bits = 0;
1129 13939 : GDKclrerr(); /* not interested in BAThash errors */
1130 :
1131 : /* not sorted, and no pre-existing hash table: we'll
1132 : * build an incomplete hash table on the fly--also see
1133 : * BATassertProps for similar code; we also exploit if
1134 : * g is clustered */
1135 13940 : algomsg = "new partial hash -- ";
1136 13940 : nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
1137 13943 : if (grps && !gc) {
1138 : /* we manipulate the hash value after having
1139 : * calculated it, and when doing that, we
1140 : * assume the mask (i.e. nbucket-1) is a
1141 : * power-of-two minus one, so make sure it
1142 : * is */
1143 1989 : nbucket = ci.ncand | ci.ncand >> 1;
1144 1989 : nbucket |= nbucket >> 2;
1145 1989 : nbucket |= nbucket >> 4;
1146 1989 : nbucket |= nbucket >> 8;
1147 1989 : nbucket |= nbucket >> 16;
1148 : #if SIZEOF_BUN == 8
1149 1989 : nbucket |= nbucket >> 32;
1150 : #endif
1151 1989 : nbucket++;
1152 : } else {
1153 22706 : nbucket = MAX(HASHmask(ci.ncand), 1 << 16);
1154 : }
1155 13943 : if (grps == NULL || is_oid_nil(maxgrp)
1156 : #if SIZEOF_OID == SIZEOF_LNG
1157 2644 : || maxgrp >= ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1158 : #endif
1159 : ) {
1160 11299 : switch (t) {
1161 : case TYPE_bte:
1162 13943 : nbucket = 256;
1163 : break;
1164 0 : case TYPE_sht:
1165 0 : nbucket = 65536;
1166 0 : break;
1167 : default:
1168 : break;
1169 : }
1170 : }
1171 : /* nbucket is a power of two, so ctz(nbucket)
1172 : * tells us which power of two */
1173 13943 : bits = 8 * SIZEOF_OID - ctz(nbucket);
1174 13943 : if ((hs = GDKzalloc(sizeof(Hash))) == NULL ||
1175 13951 : (hs->heaplink.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
1176 13951 : (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0) {
1177 0 : GDKfree(hs);
1178 0 : hs = NULL;
1179 0 : GDKerror("cannot allocate hash table\n");
1180 0 : goto error;
1181 : }
1182 13952 : hs->heapbckt.parentid = b->batCacheid;
1183 13952 : hs->heaplink.parentid = b->batCacheid;
1184 13952 : if (snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshgrpl%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heaplink.filename) ||
1185 27892 : snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshgrpb%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heapbckt.filename) ||
1186 13953 : HASHnew(hs, bi.type, BATcount(b), nbucket, BUN_NONE, false) != GDK_SUCCEED) {
1187 5 : GDKfree(hs);
1188 0 : hs = NULL;
1189 0 : GDKerror("cannot allocate hash table\n");
1190 0 : goto error;
1191 : }
1192 13938 : gn->tsorted = true; /* be optimistic */
1193 :
1194 13938 : switch (t) {
1195 18 : case TYPE_bte:
1196 18 : if (grps && !is_oid_nil(maxgrp)
1197 : #if SIZEOF_OID == SIZEOF_LNG
1198 18 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1199 : #endif
1200 : ) {
1201 18 : ulng v;
1202 18 : const bte *w = (bte *) bi.base;
1203 162881 : GRP_create_partial_hash_table_core(
1204 : (void) 0,
1205 : (v = ((ulng)grps[r]<<8)|(uint8_t)w[p], hash_lng(hs, &v)),
1206 : w[p] == w[hb] && grps[r] == grps[q],
1207 : (void) 0,
1208 : NOGRPTST);
1209 : } else
1210 0 : GRP_create_partial_hash_table_tpe(bte);
1211 : break;
1212 860 : case TYPE_sht:
1213 860 : if (grps && !is_oid_nil(maxgrp)
1214 : #if SIZEOF_OID == SIZEOF_LNG
1215 860 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 16))
1216 : #endif
1217 : ) {
1218 860 : ulng v;
1219 860 : const sht *w = (sht *) bi.base;
1220 28253747 : GRP_create_partial_hash_table_core(
1221 : (void) 0,
1222 : (v = ((ulng)grps[r]<<16)|(uint16_t)w[p], hash_lng(hs, &v)),
1223 : w[p] == w[hb] && grps[r] == grps[q],
1224 : (void) 0,
1225 : NOGRPTST);
1226 : } else
1227 0 : GRP_create_partial_hash_table_tpe(sht);
1228 : break;
1229 12382 : case TYPE_int:
1230 12382 : if (grps && !is_oid_nil(maxgrp)
1231 : #if SIZEOF_OID == SIZEOF_LNG
1232 1483 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 32))
1233 : #endif
1234 : ) {
1235 1484 : ulng v;
1236 1484 : const int *w = (int *) bi.base;
1237 119861844 : GRP_create_partial_hash_table_core(
1238 : (void) 0,
1239 : (v = ((ulng)grps[r]<<32)|(unsigned int)w[p], hash_lng(hs, &v)),
1240 : w[p] == w[hb] && grps[r] == grps[q],
1241 : (void) 0,
1242 : NOGRPTST);
1243 : } else
1244 76450390 : GRP_create_partial_hash_table_tpe(int);
1245 : break;
1246 187 : case TYPE_lng:
1247 : #ifdef HAVE_HGE
1248 187 : if (grps) {
1249 16 : uhge v;
1250 16 : const lng *w = (lng *) bi.base;
1251 2061579 : GRP_create_partial_hash_table_core(
1252 : (void) 0,
1253 : (v = ((uhge)grps[r]<<64)|(ulng)w[p], hash_hge(hs, &v)),
1254 : w[p] == w[hb] && grps[r] == grps[q],
1255 : (void) 0,
1256 : NOGRPTST);
1257 : } else
1258 : #endif
1259 93458 : GRP_create_partial_hash_table_tpe(lng);
1260 : break;
1261 : #ifdef HAVE_HGE
1262 21 : case TYPE_hge:
1263 57796122 : GRP_create_partial_hash_table_tpe(hge);
1264 : break;
1265 : #endif
1266 22 : case TYPE_flt:
1267 755 : GRP_create_partial_hash_table_tpe(flt);
1268 : break;
1269 116 : case TYPE_dbl:
1270 5489 : GRP_create_partial_hash_table_tpe(dbl);
1271 : break;
1272 8 : case TYPE_uuid:
1273 86 : GRP_create_partial_hash_table_tpe(uuid);
1274 : break;
1275 324 : default:
1276 74702294 : GRP_create_partial_hash_table_any();
1277 : }
1278 :
1279 13950 : HEAPfree(&hs->heapbckt, true);
1280 13939 : HEAPfree(&hs->heaplink, true);
1281 13950 : GDKfree(hs);
1282 : }
1283 40111 : bat_iterator_end(&bi);
1284 39931 : if (extents) {
1285 33538 : BATsetcount(en, (BUN) ngrp);
1286 33558 : en->tkey = true;
1287 33558 : en->tsorted = true;
1288 33558 : en->trevsorted = ngrp == 1;
1289 33558 : en->tnonil = true;
1290 33558 : en->tnil = false;
1291 33558 : *extents = virtualize(en);
1292 : }
1293 39960 : if (histo) {
1294 8380 : BATsetcount(hn, (BUN) ngrp);
1295 8380 : if (ngrp == ci.ncand || ngrp == 1) {
1296 5944 : hn->tkey = ngrp == 1;
1297 5944 : hn->tsorted = true;
1298 5944 : hn->trevsorted = true;
1299 : } else {
1300 2436 : hn->tkey = false;
1301 2436 : hn->tsorted = false;
1302 2436 : hn->trevsorted = false;
1303 : }
1304 8380 : hn->tnonil = true;
1305 8380 : hn->tnil = false;
1306 8380 : *histo = hn;
1307 : }
1308 39960 : gn->tkey = ngrp == BATcount(gn);
1309 39960 : gn->trevsorted = ngrp == 1 || BATcount(gn) <= 1;
1310 39960 : gn->tnonil = true;
1311 39960 : gn->tnil = false;
1312 39960 : gn->tmaxpos = maxgrppos;
1313 39960 : *groups = gn;
1314 39960 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1315 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
1316 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
1317 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
1318 : ",histo=" ALGOOPTBATFMT " (%s" LLFMT " usec)\n",
1319 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
1320 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
1321 : ALGOOPTBATPAR(h),
1322 : subsorted ? "true" : "false",
1323 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
1324 : ALGOOPTBATPAR(hn), algomsg, GDKusec() - t0);
1325 : return GDK_SUCCEED;
1326 0 : error:
1327 0 : bat_iterator_end(&bi);
1328 0 : if (hs != NULL && hs != b->thash) {
1329 0 : HEAPfree(&hs->heaplink, true);
1330 0 : HEAPfree(&hs->heapbckt, true);
1331 0 : GDKfree(hs);
1332 : }
1333 0 : if (locked)
1334 0 : MT_rwlock_rdunlock(&b->thashlock);
1335 0 : BBPreclaim(gn);
1336 0 : BBPreclaim(en);
1337 0 : BBPreclaim(hn);
1338 : return GDK_FAIL;
1339 : }
1340 :
1341 : gdk_return
1342 89226 : BATgroup(BAT **groups, BAT **extents, BAT **histo,
1343 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
1344 : {
1345 89226 : return BATgroup_internal(groups, extents, histo, b, s, g, e, h, false);
1346 : }
|
