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