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 37889867 : rev(oid x)
438 : {
439 : #if SIZEOF_OID == 8
440 37889867 : x = ((x & 0x5555555555555555) << 1) | ((x >> 1) & 0x5555555555555555);
441 37889867 : x = ((x & 0x3333333333333333) << 2) | ((x >> 2) & 0x3333333333333333);
442 37889867 : x = ((x & 0x0F0F0F0F0F0F0F0F) << 4) | ((x >> 4) & 0x0F0F0F0F0F0F0F0F);
443 37889867 : x = ((x & 0x00FF00FF00FF00FF) << 8) | ((x >> 8) & 0x00FF00FF00FF00FF);
444 37889867 : x = ((x & 0x0000FFFF0000FFFF) << 16) | ((x >> 16) & 0x0000FFFF0000FFFF);
445 37889867 : 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 37889867 : return x;
454 : }
455 :
456 : /* count trailing zeros, also see candmask_lobit in gdk_cand.h */
457 : static inline int __attribute__((__const__))
458 12935 : ctz(oid x)
459 : {
460 : #if defined(__GNUC__)
461 : #if SIZEOF_OID == SIZEOF_INT
462 : return __builtin_ctz(x);
463 : #else
464 12935 : 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, qry_ctx) { \
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(qry_ctx, \
531 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
532 : } else { \
533 : MT_thread_setalgorithm("GRP_create_partial_hash_table, !dense"); \
534 : TIMEOUT_LOOP_IDX(r, ci.ncand, qry_ctx) { \
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(qry_ctx, \
565 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
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, qry_ctx) { \
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, qry_ctx) { \
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(qry_ctx, \
647 : GOTO_LABEL_TIMEOUT_HANDLER(error, qry_ctx)); \
648 : } while (0)
649 :
650 : gdk_return
651 92310 : BATgroup_internal(BAT **groups, BAT **extents, BAT **histo,
652 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h, bool subsorted)
653 : {
654 92310 : BAT *gn = NULL, *en = NULL, *hn = NULL;
655 92310 : int t;
656 92310 : int (*cmp)(const void *, const void *);
657 92310 : const oid *grps = NULL;
658 92310 : oid *restrict ngrps, ngrp, prev = 0, hseqb = 0;
659 92310 : oid *restrict exts = NULL;
660 92310 : lng *restrict cnts = NULL;
661 92310 : BUN p, q, r;
662 92310 : const void *v, *pv;
663 92310 : BATiter bi;
664 92310 : Hash *hs = NULL;
665 92310 : BUN hb;
666 92310 : BUN maxgrps;
667 92310 : BUN maxgrppos = BUN_NONE;
668 92310 : bat parent;
669 92310 : BUN lo = 0;
670 92310 : struct canditer ci;
671 92310 : oid maxgrp = oid_nil; /* maximum value of g BAT (if subgrouping) */
672 92310 : lng t0 = 0;
673 92310 : const char *algomsg = "";
674 92310 : bool locked = false;
675 :
676 92310 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
677 :
678 92332 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
679 92332 : if (b == NULL) {
680 0 : GDKerror("b must exist\n");
681 0 : return GDK_FAIL;
682 : }
683 92332 : assert(s == NULL || BATttype(s) == TYPE_oid);
684 92332 : canditer_init(&ci, b, s);
685 92803 : bi = bat_iterator(b);
686 :
687 : /* g is NULL or [oid(dense),oid] and same size as b or s */
688 92364 : assert(g == NULL || BATttype(g) == TYPE_oid || BATcount(g) == 0);
689 28071 : assert(g == NULL || BATcount(g) == ci.ncand);
690 28071 : assert(g == NULL || BATcount(b) == 0 || (s ? g->hseqbase == s->hseqbase : g->hseqbase == b->hseqbase));
691 : /* e is NULL or [oid(dense),oid] */
692 92364 : assert(e == NULL || BATttype(e) == TYPE_oid);
693 : /* h is NULL or [oid(dense),lng] */
694 92364 : assert(h == NULL || h->ttype == TYPE_lng);
695 : /* e and h are aligned */
696 92364 : assert(e == NULL || h == NULL || BATcount(e) == BATcount(h));
697 92364 : assert(e == NULL || h == NULL || e->hseqbase == h->hseqbase);
698 : /* we want our output to go somewhere */
699 92364 : assert(groups != NULL);
700 :
701 92364 : if (ci.ncand == 0) {
702 : hseqb = 0;
703 : } else {
704 59433 : hseqb = ci.seq;
705 : }
706 92364 : if (bi.key || ci.ncand <= 1 || (g && (g->tkey || BATtdense(g)))) {
707 : /* grouping is trivial: 1 element per group */
708 52846 : gn = BATdense(hseqb, 0, BATcount(b));
709 52832 : if (gn == NULL)
710 0 : goto error;
711 52832 : *groups = gn;
712 52832 : if (extents) {
713 52420 : en = canditer_slice(&ci, 0, ci.ncand);
714 52388 : if (en == NULL)
715 0 : goto error;
716 52388 : *extents = en;
717 : }
718 52800 : if (histo) {
719 3130 : hn = BATconstant(0, TYPE_lng, &(lng){1}, ci.ncand, TRANSIENT);
720 3129 : if (hn == NULL)
721 0 : goto error;
722 3129 : *histo = hn;
723 : }
724 52799 : bat_iterator_end(&bi);
725 52933 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
726 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
727 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
728 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
729 : ",histo=" ALGOOPTBATFMT " (1 element per group -- "
730 : LLFMT " usec)\n",
731 : ALGOBATPAR(b), ALGOOPTBATPAR(s), ALGOOPTBATPAR(g),
732 : ALGOOPTBATPAR(e), ALGOOPTBATPAR(h),
733 : subsorted ? "true" : "false", ALGOOPTBATPAR(gn),
734 : ALGOOPTBATPAR(en), ALGOOPTBATPAR(hn), GDKusec() - t0);
735 52933 : return GDK_SUCCEED;
736 : }
737 39518 : assert(!BATtdense(b));
738 39518 : if (g) {
739 7205 : assert(!BATtdense(g));
740 7205 : if (g->tsorted)
741 5024 : maxgrp = * (oid *) Tloc(g, BATcount(g) - 1);
742 2181 : else if (g->trevsorted)
743 0 : maxgrp = * (oid *) Tloc(g, 0);
744 : else {
745 : /* group bats are not modified in parallel, so
746 : * no need for locks */
747 2181 : if (g->tmaxpos != BUN_NONE)
748 2178 : maxgrp = BUNtoid(g, g->tmaxpos);
749 2184 : if (is_oid_nil(maxgrp) /* && BATcount(g) < 10240 */) {
750 3 : BATmax(g, &maxgrp);
751 : }
752 : }
753 7208 : if (maxgrp == 0)
754 : g = NULL; /* single group */
755 : else
756 5187 : grps = (const oid *) Tloc(g, 0);
757 : }
758 39521 : (void) BATordered(b);
759 39933 : (void) BATordered_rev(b);
760 39952 : bat_iterator_end(&bi);
761 39920 : bi = bat_iterator(b);
762 39498 : if (bi.sorted && bi.revsorted) {
763 : /* all values are equal */
764 4169 : if (g == NULL || (BATordered(g) && BATordered_rev(g))) {
765 : /* there's only a single group: 0 */
766 3797 : gn = BATconstant(hseqb, TYPE_oid, &(oid){0}, ci.ncand, TRANSIENT);
767 3783 : if (gn == NULL)
768 0 : goto error;
769 3783 : *groups = gn;
770 3783 : if (extents) {
771 2830 : en = BATdense(0, canditer_next(&ci), 1);
772 2838 : if (en == NULL)
773 0 : goto error;
774 2838 : *extents = en;
775 : }
776 3791 : if (histo) {
777 46 : hn = BATconstant(0, TYPE_lng, &(lng){(lng)ci.ncand}, 1, TRANSIENT);
778 46 : if (hn == NULL)
779 0 : goto error;
780 46 : *histo = hn;
781 : }
782 3791 : bat_iterator_end(&bi);
783 3797 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
784 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
785 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
786 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
787 : ",histo=" ALGOOPTBATFMT " (single group -- "
788 : LLFMT " usec)\n",
789 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
790 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
791 : ALGOOPTBATPAR(h),
792 : subsorted ? "true" : "false",
793 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
794 : ALGOOPTBATPAR(hn), GDKusec() - t0);
795 3797 : return GDK_SUCCEED;
796 : }
797 372 : if ((extents == NULL || e != NULL) &&
798 130 : (histo == NULL || h != NULL) &&
799 130 : ci.ncand == BATcount(b)) {
800 : /* inherit given grouping; note that if
801 : * extents/histo is to be returned, we need
802 : * e/h available in order to copy them,
803 : * otherwise we will need to calculate them
804 : * which we will do using the "normal" case */
805 130 : gn = COLcopy(g, g->ttype, false, TRANSIENT);
806 130 : if (gn == NULL)
807 0 : goto error;
808 :
809 130 : *groups = gn;
810 130 : if (extents) {
811 0 : en = COLcopy(e, e->ttype, false, TRANSIENT);
812 0 : if (en == NULL)
813 0 : goto error;
814 0 : *extents = en;
815 : }
816 130 : if (histo) {
817 0 : hn = COLcopy(h, h->ttype, false, TRANSIENT);
818 0 : if (hn == NULL)
819 0 : goto error;
820 0 : *histo = hn;
821 : }
822 130 : bat_iterator_end(&bi);
823 130 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
824 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
825 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
826 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
827 : ",histo=" ALGOOPTBATFMT " (copy groups -- "
828 : LLFMT " usec)\n",
829 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
830 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
831 : ALGOOPTBATPAR(h),
832 : subsorted ? "true" : "false",
833 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
834 : ALGOOPTBATPAR(hn), GDKusec() - t0);
835 130 : return GDK_SUCCEED;
836 : }
837 : }
838 35571 : assert(g == NULL || !BATtdense(g)); /* i.e. g->ttype == TYPE_oid */
839 35571 : cmp = ATOMcompare(bi.type);
840 35571 : gn = COLnew(hseqb, TYPE_oid, ci.ncand, TRANSIENT);
841 35901 : if (gn == NULL)
842 0 : goto error;
843 35901 : ngrps = (oid *) Tloc(gn, 0);
844 35901 : maxgrps = BUN_NONE;
845 35901 : MT_rwlock_rdlock(&b->thashlock);
846 36013 : if (b->thash && b->thash != (Hash *) 1)
847 3 : maxgrps = b->thash->nunique;
848 36013 : MT_rwlock_rdunlock(&b->thashlock);
849 35675 : if (maxgrps == BUN_NONE) {
850 35726 : if (bi.unique_est != 0) {
851 4646 : maxgrps = (BUN) bi.unique_est;
852 4646 : if (maxgrps > ci.ncand)
853 : maxgrps = ci.ncand;
854 : } else
855 31080 : maxgrps = ci.ncand / 10;
856 : }
857 35675 : if (!is_oid_nil(maxgrp) && maxgrps < maxgrp)
858 3171 : maxgrps += maxgrp;
859 35675 : if (e && maxgrps < BATcount(e))
860 12 : maxgrps += BATcount(e);
861 35675 : if (h && maxgrps < BATcount(h))
862 0 : maxgrps += BATcount(h);
863 35675 : if (maxgrps < GROUPBATINCR)
864 : maxgrps = GROUPBATINCR;
865 :
866 35675 : if (bi.width <= 2) {
867 5910 : maxgrps = (BUN) 1 << (8 * bi.width);
868 5910 : if (bi.width == 1 && maxgrp < 256)
869 736 : maxgrps *= maxgrp;
870 : }
871 35675 : if (extents) {
872 29441 : en = COLnew(0, TYPE_oid, maxgrps, TRANSIENT);
873 29747 : if (en == NULL)
874 0 : goto error;
875 29747 : exts = (oid *) Tloc(en, 0);
876 : }
877 35981 : if (histo) {
878 6453 : hn = COLnew(0, TYPE_lng, maxgrps, TRANSIENT);
879 6453 : if (hn == NULL)
880 0 : goto error;
881 6453 : cnts = (lng *) Tloc(hn, 0);
882 : }
883 35981 : ngrp = 0;
884 35981 : BATsetcount(gn, ci.ncand);
885 :
886 35515 : hseqb = b->hseqbase; /* abbreviation */
887 :
888 : /* figure out if we can use the storage type also for
889 : * comparing values */
890 35515 : t = ATOMbasetype(bi.type);
891 : /* for strings we can use the offset instead of the actual
892 : * string values if we know that the strings in the string
893 : * heap are unique */
894 35515 : if (t == TYPE_str && GDK_ELIMDOUBLES(bi.vh)) {
895 5185 : switch (bi.width) {
896 : case 1:
897 : t = TYPE_bte;
898 : break;
899 2087 : case 2:
900 2087 : t = TYPE_sht;
901 2087 : break;
902 53 : case 4:
903 53 : t = TYPE_int;
904 53 : break;
905 : #if SIZEOF_VAR_T == 8
906 0 : case 8:
907 0 : t = TYPE_lng;
908 0 : break;
909 : #endif
910 : default:
911 0 : MT_UNREACHABLE();
912 : }
913 : }
914 :
915 35515 : if (g == NULL && t == TYPE_bte) {
916 : /* byte-sized values, use 256 entry array to keep
917 : * track of doled out group ids; note that we can't
918 : * possibly have more than 256 groups, so the group id
919 : * fits in a uint8_t */
920 8543956 : GRP_small_values(8, 8, w[p]);
921 32877 : } else if (t == TYPE_bte && maxgrp < 256) {
922 : /* subgrouping byte-sized values with a limited number
923 : * of groups, use 65536 entry array to keep track of
924 : * doled out group ids; note that we can't possibly have
925 : * more than 65536 goups, so the group id fits in a
926 : * uint16_t */
927 17207034 : GRP_small_values(16, 8, (uint16_t) (w[p] | (grps[p] << 8)));
928 32271 : } else if (g == NULL && t == TYPE_sht) {
929 : /* short-sized values, use 65536 entry array to keep
930 : * track of doled out group ids; note that we can't
931 : * possibly have more than 65536 groups, so the group
932 : * id fits in a uint16_t */
933 6777636 : GRP_small_values(16, 16, w[p]);
934 30861 : } else if (subsorted ||
935 25795 : ((bi.sorted || bi.revsorted) &&
936 405 : (g == NULL || BATordered(g) || BATordered_rev(g)))) {
937 : /* we only need to compare each entry with the previous */
938 17647 : algomsg = "compare consecutive values -- ";
939 17647 : switch (t) {
940 185 : case TYPE_bte:
941 431275 : GRP_compare_consecutive_values_tpe(bte);
942 : break;
943 386 : case TYPE_sht:
944 358422 : GRP_compare_consecutive_values_tpe(sht);
945 : break;
946 15569 : case TYPE_int:
947 79938179 : GRP_compare_consecutive_values_tpe(int);
948 : break;
949 1342 : case TYPE_lng:
950 789929 : GRP_compare_consecutive_values_tpe(lng);
951 : break;
952 : #ifdef HAVE_HGE
953 68 : case TYPE_hge:
954 4710 : GRP_compare_consecutive_values_tpe(hge);
955 : break;
956 : #endif
957 9 : case TYPE_flt:
958 108 : GRP_compare_consecutive_values_tpe(flt);
959 : break;
960 77 : case TYPE_dbl:
961 402877 : GRP_compare_consecutive_values_tpe(dbl);
962 : break;
963 11 : default:
964 29224 : GRP_compare_consecutive_values_any();
965 : break;
966 : }
967 :
968 17919 : gn->tsorted = true;
969 17919 : *groups = gn;
970 13214 : } else if (bi.sorted || bi.revsorted) {
971 287 : BUN i, j;
972 287 : BUN *pgrp;
973 :
974 287 : assert(g); /* if g == NULL or if there is a single */
975 287 : assert(grps); /* group, we used the code above */
976 : /* for each value, we need to scan all previous equal
977 : * values (a consecutive, possibly empty, range) to
978 : * see if we can find one in the same old group
979 : *
980 : * we do this by maintaining for each old group the
981 : * last time we saw that group, so if the last time we
982 : * saw the old group of the current value is within
983 : * this range, we can reuse the new group */
984 287 : algomsg = "subscan old groups -- ";
985 : /* determine how many old groups there are */
986 287 : if (e) {
987 0 : j = BATcount(e) + (BUN) e->hseqbase;
988 287 : } else if (h) {
989 0 : j = BATcount(h) + (BUN) h->hseqbase;
990 : } else {
991 287 : oid m = 0;
992 23334853 : for (i = 0, j= BATcount(g); i < j; i++)
993 23334566 : m = MAX(m , grps[i]);
994 287 : j = (BUN) m + 1;
995 : }
996 : /* array to maintain last time we saw each old group */
997 287 : pgrp = GDKmalloc(sizeof(BUN) * j);
998 287 : if (pgrp == NULL)
999 0 : goto error;
1000 : /* initialize to impossible position */
1001 287 : memset(pgrp, ~0, sizeof(BUN) * j);
1002 :
1003 287 : gn->tsorted = true; /* be optimistic */
1004 :
1005 287 : switch (t) {
1006 1 : case TYPE_bte:
1007 6920 : GRP_subscan_old_groups_tpe(bte);
1008 : break;
1009 11 : case TYPE_sht:
1010 124 : GRP_subscan_old_groups_tpe(sht);
1011 : break;
1012 263 : case TYPE_int:
1013 23329237 : GRP_subscan_old_groups_tpe(int);
1014 : break;
1015 2 : case TYPE_lng:
1016 98 : GRP_subscan_old_groups_tpe(lng);
1017 : break;
1018 : #ifdef HAVE_HGE
1019 0 : case TYPE_hge:
1020 0 : GRP_subscan_old_groups_tpe(hge);
1021 : break;
1022 : #endif
1023 2 : case TYPE_flt:
1024 26 : GRP_subscan_old_groups_tpe(flt);
1025 : break;
1026 8 : case TYPE_dbl:
1027 346 : GRP_subscan_old_groups_tpe(dbl);
1028 : break;
1029 0 : default:
1030 0 : GRP_subscan_old_groups_any();
1031 : break;
1032 : }
1033 :
1034 288 : GDKfree(pgrp);
1035 12927 : } else if (g == NULL &&
1036 10889 : (BATcheckhash(b) ||
1037 10897 : ((!bi.transient ||
1038 10897 : (b->batRole == PERSISTENT && GDKinmemory(0))) &&
1039 0 : BAThash(b) == GDK_SUCCEED) ||
1040 : (/* DISABLES CODE */ (0) &&
1041 : (parent = VIEWtparent(b)) != 0 &&
1042 : /* if enabled, need to fix/unfix parent bat */
1043 0 : BATcheckhash(BBP_desc(parent))))) {
1044 : /* we already have a hash table on b, or b is
1045 : * persistent and we could create a hash table, or b
1046 : * is a view on a bat that already has a hash table;
1047 : * but don't do this if we're checking for subgroups
1048 : * since we may have to go through long lists of
1049 : * duplicates in the hash table to find an old
1050 : * group */
1051 0 : bool phash = false;
1052 0 : algomsg = "existing hash -- ";
1053 0 : MT_rwlock_rdlock(&b->thashlock);
1054 0 : if (b->thash == NULL &&
1055 : /* DISABLES CODE */ (0) &&
1056 : (parent = VIEWtparent(b)) != 0) {
1057 : /* b is a view on another bat (b2 for now).
1058 : * calculate the bounds [lo, lo+BATcount(b))
1059 : * in the parent that b uses */
1060 : /* if enabled, need to fix/unfix parent bat */
1061 : BAT *b2 = BBP_desc(parent);
1062 : MT_rwlock_rdunlock(&b->thashlock);
1063 : lo = b->tbaseoff - b2->tbaseoff;
1064 : b = b2;
1065 : bat_iterator_end(&bi);
1066 : bi = bat_iterator(b);
1067 : MT_rwlock_rdlock(&b->thashlock);
1068 : algomsg = "existing parent hash -- ";
1069 : phash = true;
1070 : }
1071 0 : hs = b->thash;
1072 0 : if (hs == NULL) {
1073 0 : MT_rwlock_rdunlock(&b->thashlock);
1074 0 : goto lost_hash;
1075 : }
1076 0 : locked = true;
1077 0 : gn->tsorted = true; /* be optimistic */
1078 :
1079 0 : switch (t) {
1080 0 : case TYPE_bte:
1081 0 : GRP_use_existing_hash_table_tpe(bte);
1082 : break;
1083 0 : case TYPE_sht:
1084 0 : GRP_use_existing_hash_table_tpe(sht);
1085 : break;
1086 0 : case TYPE_int:
1087 0 : GRP_use_existing_hash_table_tpe(int);
1088 : break;
1089 0 : case TYPE_lng:
1090 0 : GRP_use_existing_hash_table_tpe(lng);
1091 : break;
1092 : #ifdef HAVE_HGE
1093 0 : case TYPE_hge:
1094 0 : GRP_use_existing_hash_table_tpe(hge);
1095 : break;
1096 : #endif
1097 0 : case TYPE_flt:
1098 0 : GRP_use_existing_hash_table_tpe(flt);
1099 : break;
1100 0 : case TYPE_dbl:
1101 0 : GRP_use_existing_hash_table_tpe(dbl);
1102 : break;
1103 0 : case TYPE_uuid:
1104 0 : GRP_use_existing_hash_table_tpe(uuid);
1105 : break;
1106 0 : default:
1107 0 : GRP_use_existing_hash_table_any();
1108 : break;
1109 : }
1110 0 : MT_rwlock_rdunlock(&b->thashlock);
1111 0 : locked = false;
1112 : } else {
1113 2038 : bool gc;
1114 2038 : const char *nme;
1115 2038 : BUN prb;
1116 2038 : int bits;
1117 2038 : BUN nbucket;
1118 2038 : oid grp;
1119 :
1120 2038 : lost_hash:
1121 2038 : gc = g != NULL && (BATordered(g) || BATordered_rev(g));
1122 12933 : bits = 0;
1123 12933 : GDKclrerr(); /* not interested in BAThash errors */
1124 :
1125 : /* not sorted, and no pre-existing hash table: we'll
1126 : * build an incomplete hash table on the fly--also see
1127 : * BATassertProps for similar code; we also exploit if
1128 : * g is clustered */
1129 12930 : algomsg = "new partial hash -- ";
1130 12930 : nme = GDKinmemory(bi.h->farmid) ? ":memory:" : BBP_physical(b->batCacheid);
1131 12935 : if (grps && !gc) {
1132 : /* we manipulate the hash value after having
1133 : * calculated it, and when doing that, we
1134 : * assume the mask (i.e. nbucket-1) is a
1135 : * power-of-two minus one, so make sure it
1136 : * is */
1137 1540 : nbucket = ci.ncand | ci.ncand >> 1;
1138 1540 : nbucket |= nbucket >> 2;
1139 1540 : nbucket |= nbucket >> 4;
1140 1540 : nbucket |= nbucket >> 8;
1141 1540 : nbucket |= nbucket >> 16;
1142 : #if SIZEOF_BUN == 8
1143 1540 : nbucket |= nbucket >> 32;
1144 : #endif
1145 1540 : nbucket++;
1146 : } else {
1147 21707 : nbucket = MAX(HASHmask(ci.ncand), 1 << 16);
1148 : }
1149 12935 : if (grps == NULL || is_oid_nil(maxgrp)
1150 : #if SIZEOF_OID == SIZEOF_LNG
1151 2041 : || maxgrp >= ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1152 : #endif
1153 : ) {
1154 10894 : switch (t) {
1155 : case TYPE_bte:
1156 12935 : nbucket = 256;
1157 : break;
1158 0 : case TYPE_sht:
1159 0 : nbucket = 65536;
1160 0 : break;
1161 : default:
1162 : break;
1163 : }
1164 : }
1165 : /* nbucket is a power of two, so ctz(nbucket)
1166 : * tells us which power of two */
1167 12935 : bits = 8 * SIZEOF_OID - ctz(nbucket);
1168 12935 : if ((hs = GDKzalloc(sizeof(Hash))) == NULL ||
1169 12943 : (hs->heaplink.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0 ||
1170 12940 : (hs->heapbckt.farmid = BBPselectfarm(TRANSIENT, bi.type, hashheap)) < 0) {
1171 0 : GDKfree(hs);
1172 0 : hs = NULL;
1173 0 : GDKerror("cannot allocate hash table\n");
1174 0 : goto error;
1175 : }
1176 12940 : hs->heapbckt.parentid = b->batCacheid;
1177 12940 : hs->heaplink.parentid = b->batCacheid;
1178 12940 : if (snprintf(hs->heaplink.filename, sizeof(hs->heaplink.filename), "%s.thshgrpl%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heaplink.filename) ||
1179 25873 : snprintf(hs->heapbckt.filename, sizeof(hs->heapbckt.filename), "%s.thshgrpb%x", nme, (unsigned) MT_getpid()) >= (int) sizeof(hs->heapbckt.filename) ||
1180 12938 : HASHnew(hs, bi.type, BATcount(b), nbucket, BUN_NONE, false) != GDK_SUCCEED) {
1181 11 : GDKfree(hs);
1182 0 : hs = NULL;
1183 0 : GDKerror("cannot allocate hash table\n");
1184 0 : goto error;
1185 : }
1186 12933 : gn->tsorted = true; /* be optimistic */
1187 :
1188 12933 : switch (t) {
1189 23 : case TYPE_bte:
1190 23 : if (grps && !is_oid_nil(maxgrp)
1191 : #if SIZEOF_OID == SIZEOF_LNG
1192 23 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 8))
1193 : #endif
1194 : ) {
1195 23 : ulng v;
1196 23 : const bte *w = (bte *) bi.base;
1197 230435 : GRP_create_partial_hash_table_core(
1198 : (void) 0,
1199 : (v = ((ulng)grps[r]<<8)|(uint8_t)w[p], hash_lng(hs, &v)),
1200 : w[p] == w[hb] && grps[r] == grps[q],
1201 : (void) 0,
1202 : NOGRPTST);
1203 : } else
1204 0 : GRP_create_partial_hash_table_tpe(bte);
1205 : break;
1206 656 : case TYPE_sht:
1207 656 : if (grps && !is_oid_nil(maxgrp)
1208 : #if SIZEOF_OID == SIZEOF_LNG
1209 656 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 16))
1210 : #endif
1211 : ) {
1212 656 : ulng v;
1213 656 : const sht *w = (sht *) bi.base;
1214 31335386 : GRP_create_partial_hash_table_core(
1215 : (void) 0,
1216 : (v = ((ulng)grps[r]<<16)|(uint16_t)w[p], hash_lng(hs, &v)),
1217 : w[p] == w[hb] && grps[r] == grps[q],
1218 : (void) 0,
1219 : NOGRPTST);
1220 : } else
1221 0 : GRP_create_partial_hash_table_tpe(sht);
1222 : break;
1223 11576 : case TYPE_int:
1224 11576 : if (grps && !is_oid_nil(maxgrp)
1225 : #if SIZEOF_OID == SIZEOF_LNG
1226 1079 : && maxgrp < ((oid) 1 << (SIZEOF_LNG * 8 - 32))
1227 : #endif
1228 : ) {
1229 1081 : ulng v;
1230 1081 : const int *w = (int *) bi.base;
1231 120077778 : GRP_create_partial_hash_table_core(
1232 : (void) 0,
1233 : (v = ((ulng)grps[r]<<32)|(unsigned int)w[p], hash_lng(hs, &v)),
1234 : w[p] == w[hb] && grps[r] == grps[q],
1235 : (void) 0,
1236 : NOGRPTST);
1237 : } else
1238 78997050 : GRP_create_partial_hash_table_tpe(int);
1239 : break;
1240 193 : case TYPE_lng:
1241 : #ifdef HAVE_HGE
1242 193 : if (grps) {
1243 15 : uhge v;
1244 15 : const lng *w = (lng *) bi.base;
1245 2068993 : GRP_create_partial_hash_table_core(
1246 : (void) 0,
1247 : (v = ((uhge)grps[r]<<64)|(ulng)w[p], hash_hge(hs, &v)),
1248 : w[p] == w[hb] && grps[r] == grps[q],
1249 : (void) 0,
1250 : NOGRPTST);
1251 : } else
1252 : #endif
1253 98360 : GRP_create_partial_hash_table_tpe(lng);
1254 : break;
1255 : #ifdef HAVE_HGE
1256 21 : case TYPE_hge:
1257 57801314 : GRP_create_partial_hash_table_tpe(hge);
1258 : break;
1259 : #endif
1260 23 : case TYPE_flt:
1261 754 : GRP_create_partial_hash_table_tpe(flt);
1262 : break;
1263 115 : case TYPE_dbl:
1264 19817 : GRP_create_partial_hash_table_tpe(dbl);
1265 : break;
1266 8 : case TYPE_uuid:
1267 86 : GRP_create_partial_hash_table_tpe(uuid);
1268 : break;
1269 318 : default:
1270 72953233 : GRP_create_partial_hash_table_any();
1271 : }
1272 :
1273 12938 : HEAPfree(&hs->heapbckt, true);
1274 12933 : HEAPfree(&hs->heaplink, true);
1275 12941 : GDKfree(hs);
1276 : }
1277 35801 : bat_iterator_end(&bi);
1278 35799 : if (extents) {
1279 29502 : BATsetcount(en, (BUN) ngrp);
1280 29524 : en->tkey = true;
1281 29524 : en->tsorted = true;
1282 29524 : en->trevsorted = ngrp == 1;
1283 29524 : en->tnonil = true;
1284 29524 : en->tnil = false;
1285 29524 : *extents = virtualize(en);
1286 : }
1287 35817 : if (histo) {
1288 6453 : BATsetcount(hn, (BUN) ngrp);
1289 6452 : if (ngrp == ci.ncand || ngrp == 1) {
1290 4017 : hn->tkey = ngrp == 1;
1291 4017 : hn->tsorted = true;
1292 4017 : hn->trevsorted = true;
1293 : } else {
1294 2435 : hn->tkey = false;
1295 2435 : hn->tsorted = false;
1296 2435 : hn->trevsorted = false;
1297 : }
1298 6452 : hn->tnonil = true;
1299 6452 : hn->tnil = false;
1300 6452 : *histo = hn;
1301 : }
1302 35816 : gn->tkey = ngrp == BATcount(gn);
1303 35816 : gn->trevsorted = ngrp == 1 || BATcount(gn) <= 1;
1304 35816 : gn->tnonil = true;
1305 35816 : gn->tnil = false;
1306 35816 : gn->tmaxpos = maxgrppos;
1307 35816 : *groups = gn;
1308 35816 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1309 : ",g=" ALGOOPTBATFMT ",e=" ALGOOPTBATFMT
1310 : ",h=" ALGOOPTBATFMT ",subsorted=%s -> groups="
1311 : ALGOOPTBATFMT ",extents=" ALGOOPTBATFMT
1312 : ",histo=" ALGOOPTBATFMT " (%s" LLFMT " usec)\n",
1313 : ALGOBATPAR(b), ALGOOPTBATPAR(s),
1314 : ALGOOPTBATPAR(g), ALGOOPTBATPAR(e),
1315 : ALGOOPTBATPAR(h),
1316 : subsorted ? "true" : "false",
1317 : ALGOOPTBATPAR(gn), ALGOOPTBATPAR(en),
1318 : ALGOOPTBATPAR(hn), algomsg, GDKusec() - t0);
1319 : return GDK_SUCCEED;
1320 0 : error:
1321 0 : bat_iterator_end(&bi);
1322 0 : if (hs != NULL && hs != b->thash) {
1323 0 : HEAPfree(&hs->heaplink, true);
1324 0 : HEAPfree(&hs->heapbckt, true);
1325 0 : GDKfree(hs);
1326 : }
1327 0 : if (locked)
1328 0 : MT_rwlock_rdunlock(&b->thashlock);
1329 0 : BBPreclaim(gn);
1330 0 : BBPreclaim(en);
1331 0 : BBPreclaim(hn);
1332 : return GDK_FAIL;
1333 : }
1334 :
1335 : gdk_return
1336 84596 : BATgroup(BAT **groups, BAT **extents, BAT **histo,
1337 : BAT *b, BAT *s, BAT *g, BAT *e, BAT *h)
1338 : {
1339 84596 : return BATgroup_internal(groups, extents, histo, b, s, g, e, h, false);
1340 : }
|
