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_calc_private.h"
17 :
18 : /* BATfirstn select the smallest n elements from the input bat b (if
19 : * asc(ending) is set, else the largest n elements). Conceptually, b
20 : * is sorted in ascending or descending order (depending on the asc
21 : * argument) and then the OIDs of the first n elements are returned.
22 : * If there are NILs in the BAT, their relative ordering is set by
23 : * using the nilslast argument: if set, NILs come last (largest value
24 : * when ascending, smallest value when descending), so if there are
25 : * enough non-NIL values, no NILs will be returned. If unset (false),
26 : * NILs come first and will be returned.
27 : *
28 : * In addition to the input BAT b, there can be a standard candidate
29 : * list s. If s is specified (non-NULL), only elements in b that are
30 : * referred to in s are considered.
31 : *
32 : * If the third input bat g is non-NULL, then s must also be non-NULL
33 : * and must be aligned with g. G then specifies groups to which the
34 : * elements referred to in s belong. Conceptually, the group values
35 : * are sorted in ascending order together with the elements in b that
36 : * are referred to in s (in ascending or descending order depending on
37 : * asc), and the first n elements are then returned.
38 : *
39 : * If the output argument gids is NULL, only n elements are returned.
40 : * If the output argument gids is non-NULL, more than n elements may
41 : * be returned. If there are duplicate values (if g is given, the
42 : * group value counts in determining duplication), all duplicates are
43 : * returned.
44 : *
45 : * If distinct is set, the result contains n complete groups of values
46 : * instead of just n values (or slightly more than n if gids is set
47 : * since then the "last" group is returned completely).
48 : *
49 : * Note that BATfirstn can be called in cascading fashion to calculate
50 : * the first n values of a table of multiple columns:
51 : * BATfirstn(&s1, &g1, b1, NULL, NULL, n, asc, nilslast, distinct);
52 : * BATfirstn(&s2, &g2, b2, s1, g1, n, asc, nilslast, distinct);
53 : * BATfirstn(&s3, NULL, b3, s2, g2, n, asc, nilslast, distinct);
54 : * If the input BATs b1, b2, b3 are large enough, s3 will contain the
55 : * OIDs of the smallest (largest) n elements in the table consisting
56 : * of the columns b1, b2, b3 when ordered in ascending order with b1
57 : * the major key.
58 : */
59 :
60 : /* We use a binary heap for the implementation of the simplest form of
61 : * first-N. During processing, the oids list forms a heap with the
62 : * root at position 0 and the children of a node at position i at
63 : * positions 2*i+1 and 2*i+2. The parent node is always
64 : * smaller/larger (depending on the value of asc) than its children
65 : * (recursively). The heapify macro creates the heap from the input
66 : * in-place. We start off with a heap containing the first N elements
67 : * of the input, and then go over the rest of the input, replacing the
68 : * root of the heap with a new value if appropriate (if the new value
69 : * is among the first-N seen so far). The siftdown macro then
70 : * restores the heap property. */
71 : #define siftdown(OPER, START, SWAP) \
72 : do { \
73 : pos = (START); \
74 : childpos = (pos << 1) + 1; \
75 : while (childpos < n) { \
76 : /* find most extreme child */ \
77 : if (childpos + 1 < n && \
78 : !(OPER(childpos + 1, childpos))) \
79 : childpos++; \
80 : /* compare parent with most extreme child */ \
81 : if (!OPER(pos, childpos)) { \
82 : /* already correctly ordered */ \
83 : break; \
84 : } \
85 : /* exchange parent with child and sift child */ \
86 : /* further */ \
87 : SWAP(pos, childpos); \
88 : pos = childpos; \
89 : childpos = (pos << 1) + 1; \
90 : } \
91 : } while (0)
92 :
93 : #define heapify(OPER, SWAP) \
94 : do { \
95 : for (i = n / 2; i > 0; i--) \
96 : siftdown(OPER, i - 1, SWAP); \
97 : } while (0)
98 :
99 : /* we inherit LT and GT from gdk_calc_private.h */
100 :
101 : #define nLTbte(a, b) (!is_bte_nil(a) && (is_bte_nil(b) || (a) < (b)))
102 : #define nLTsht(a, b) (!is_sht_nil(a) && (is_sht_nil(b) || (a) < (b)))
103 : #define nLTint(a, b) (!is_int_nil(a) && (is_int_nil(b) || (a) < (b)))
104 : #define nLTlng(a, b) (!is_lng_nil(a) && (is_lng_nil(b) || (a) < (b)))
105 : #define nLThge(a, b) (!is_hge_nil(a) && (is_hge_nil(b) || (a) < (b)))
106 :
107 : #define nGTbte(a, b) (!is_bte_nil(b) && (is_bte_nil(a) || (a) > (b)))
108 : #define nGTsht(a, b) (!is_sht_nil(b) && (is_sht_nil(a) || (a) > (b)))
109 : #define nGTint(a, b) (!is_int_nil(b) && (is_int_nil(a) || (a) > (b)))
110 : #define nGTlng(a, b) (!is_lng_nil(b) && (is_lng_nil(a) || (a) > (b)))
111 : #define nGThge(a, b) (!is_hge_nil(b) && (is_hge_nil(a) || (a) > (b)))
112 :
113 : #define LTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), \
114 : BUNtail(*bi, oids[p2] - hseq)) < 0)
115 : #define GTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), \
116 : BUNtail(*bi, oids[p2] - hseq)) > 0)
117 :
118 : #define nLTany(p1, p2) (cmp(BUNtail(*bi, oids[p1] - hseq), nil) != 0 \
119 : && (cmp(BUNtail(*bi, oids[p2] - hseq), nil) == 0 \
120 : || cmp(BUNtail(*bi, oids[p1] - hseq), \
121 : BUNtail(*bi, oids[p2] - hseq)) < 0))
122 : #define nGTany(p1, p2) (cmp(BUNtail(*bi, oids[p2] - hseq), nil) != 0 \
123 : && (cmp(BUNtail(*bi, oids[p1] - hseq), nil) == 0 \
124 : || cmp(BUNtail(*bi, oids[p1] - hseq), \
125 : BUNtail(*bi, oids[p2] - hseq)) > 0))
126 :
127 : #define LTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) < (b)))
128 : #define LTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) < (b)))
129 : #define GTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) > (b)))
130 : #define GTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) > (b)))
131 :
132 : #define nLTflt(a, b) (!is_flt_nil(a) && (is_flt_nil(b) || (a) < (b)))
133 : #define nLTdbl(a, b) (!is_dbl_nil(a) && (is_dbl_nil(b) || (a) < (b)))
134 : #define nGTflt(a, b) (!is_flt_nil(b) && (is_flt_nil(a) || (a) > (b)))
135 : #define nGTdbl(a, b) (!is_dbl_nil(b) && (is_dbl_nil(a) || (a) > (b)))
136 :
137 : #define LTfltfix(p1, p2) LTflt(vals[oids[p1] - hseq], \
138 : vals[oids[p2] - hseq])
139 : #define GTfltfix(p1, p2) GTflt(vals[oids[p1] - hseq], \
140 : vals[oids[p2] - hseq])
141 : #define LTdblfix(p1, p2) LTdbl(vals[oids[p1] - hseq], \
142 : vals[oids[p2] - hseq])
143 : #define GTdblfix(p1, p2) GTdbl(vals[oids[p1] - hseq], \
144 : vals[oids[p2] - hseq])
145 : #define LTfix(p1, p2) LT(vals[oids[p1] - hseq], \
146 : vals[oids[p2] - hseq])
147 : #define GTfix(p1, p2) GT(vals[oids[p1] - hseq], \
148 : vals[oids[p2] - hseq])
149 :
150 : #define nLTfltfix(p1, p2) nLTflt(vals[oids[p1] - hseq], \
151 : vals[oids[p2] - hseq])
152 : #define nGTfltfix(p1, p2) nGTflt(vals[oids[p1] - hseq], \
153 : vals[oids[p2] - hseq])
154 : #define nLTdblfix(p1, p2) nLTdbl(vals[oids[p1] - hseq], \
155 : vals[oids[p2] - hseq])
156 : #define nGTdblfix(p1, p2) nGTdbl(vals[oids[p1] - hseq], \
157 : vals[oids[p2] - hseq])
158 : #define nLTbtefix(p1, p2) nLTbte(vals[oids[p1] - hseq], \
159 : vals[oids[p2] - hseq])
160 : #define nGTbtefix(p1, p2) nGTbte(vals[oids[p1] - hseq], \
161 : vals[oids[p2] - hseq])
162 : #define nLTshtfix(p1, p2) nLTsht(vals[oids[p1] - hseq], \
163 : vals[oids[p2] - hseq])
164 : #define nGTshtfix(p1, p2) nGTsht(vals[oids[p1] - hseq], \
165 : vals[oids[p2] - hseq])
166 : #define nLTintfix(p1, p2) nLTint(vals[oids[p1] - hseq], \
167 : vals[oids[p2] - hseq])
168 : #define nGTintfix(p1, p2) nGTint(vals[oids[p1] - hseq], \
169 : vals[oids[p2] - hseq])
170 : #define nLTlngfix(p1, p2) nLTlng(vals[oids[p1] - hseq], \
171 : vals[oids[p2] - hseq])
172 : #define nGTlngfix(p1, p2) nGTlng(vals[oids[p1] - hseq], \
173 : vals[oids[p2] - hseq])
174 : #define nLThgefix(p1, p2) nLThge(vals[oids[p1] - hseq], \
175 : vals[oids[p2] - hseq])
176 : #define nGThgefix(p1, p2) nGThge(vals[oids[p1] - hseq], \
177 : vals[oids[p2] - hseq])
178 :
179 : #define SWAP1(p1, p2) \
180 : do { \
181 : item = oids[p1]; \
182 : oids[p1] = oids[p2]; \
183 : oids[p2] = item; \
184 : } while (0)
185 :
186 : #define shuffle_unique(TYPE, OP) \
187 : do { \
188 : const TYPE *restrict vals = (const TYPE *) bi->base; \
189 : heapify(OP##fix, SWAP1); \
190 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) { \
191 : i = canditer_next(&ci); \
192 : if (OP(vals[i - hseq], \
193 : vals[oids[0] - hseq])) { \
194 : oids[0] = i; \
195 : siftdown(OP##fix, 0, SWAP1); \
196 : } \
197 : } \
198 : } while (0)
199 :
200 : /* This version of BATfirstn returns a list of N oids (where N is the
201 : * smallest among BATcount(b), BATcount(s), and n). The oids returned
202 : * refer to the N smallest/largest (depending on asc) tail values of b
203 : * (taking the optional candidate list s into account). If there are
204 : * multiple equal values to take us past N, we return a subset of those.
205 : *
206 : * If lastp is non-NULL, it is filled in with the oid of the "last"
207 : * value, i.e. the value of which there may be multiple occurrences
208 : * that are not all included in the first N.
209 : */
210 : static BAT *
211 1073 : BATfirstn_unique(BATiter *bi, BAT *s, BUN n, bool asc, bool nilslast, oid *lastp, lng t0)
212 : {
213 1073 : BAT *bn;
214 1073 : oid *restrict oids;
215 1073 : oid hseq = bi->b->hseqbase;
216 1073 : BUN i;
217 1073 : struct canditer ci;
218 1073 : int tpe = bi->type;
219 1073 : int (*cmp)(const void *, const void *);
220 1073 : const void *nil;
221 : /* variables used in heapify/siftdown macros */
222 1073 : oid item;
223 1073 : BUN pos, childpos;
224 :
225 1073 : MT_thread_setalgorithm(__func__);
226 1073 : canditer_init(&ci, bi->b, s);
227 :
228 1073 : if (n >= ci.ncand) {
229 : /* trivial: return all candidates */
230 639 : bn = canditer_slice(&ci, 0, ci.ncand);
231 632 : if (bn && lastp)
232 142 : *lastp = oid_nil;
233 632 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
234 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
235 : " (trivial -- " LLFMT " usec)\n",
236 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
237 : ALGOOPTBATPAR(bn), GDKusec() - t0);
238 632 : return bn;
239 : }
240 :
241 434 : if (BATtvoid(bi->b)) {
242 : /* nilslast doesn't make a difference: either all are
243 : * nil, or none are */
244 0 : if (asc || is_oid_nil(bi->tseq)) {
245 : /* return the first part of the candidate list
246 : * or of the BAT itself */
247 0 : bn = canditer_slice(&ci, 0, n);
248 0 : if (bn && lastp)
249 0 : *lastp = BUNtoid(bn, n - 1);
250 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
251 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
252 : " (initial slice -- " LLFMT " usec)\n",
253 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
254 : ALGOOPTBATPAR(bn), GDKusec() - t0);
255 0 : return bn;
256 : }
257 : /* return the last part of the candidate list or of
258 : * the BAT itself */
259 0 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
260 0 : if (bn && lastp)
261 0 : *lastp = BUNtoid(bn, 0);
262 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
263 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
264 : " (final slice -- " LLFMT " usec)\n",
265 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
266 : ALGOOPTBATPAR(bn), GDKusec() - t0);
267 0 : return bn;
268 : }
269 434 : if (bi->sorted || bi->revsorted) {
270 : /* trivial: b is sorted so we just need to return the
271 : * initial or final part of it (or of the candidate
272 : * list); however, if nilslast == asc, then the nil
273 : * values (if any) are in the wrong place, so we need
274 : * to do a little more work */
275 :
276 : /* after we create the to-be-returned BAT, we set pos
277 : * to the BUN in the new BAT whose value we should
278 : * return through *lastp */
279 272 : if (nilslast == asc && !bi->nonil) {
280 0 : pos = SORTfndlast(bi->b, ATOMnilptr(tpe));
281 0 : pos = canditer_search(&ci, hseq + pos, true);
282 : /* 0 <= pos <= ci.ncand
283 : * 0 < n < ci.ncand
284 : */
285 0 : if (bi->sorted) {
286 : /* [0..pos) -- nil
287 : * [pos..ci.ncand) -- non-nil <<<
288 : */
289 0 : if (asc) { /* i.e. nilslast */
290 : /* prefer non-nil and
291 : * smallest */
292 0 : if (ci.ncand - pos < n) {
293 0 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
294 0 : pos = 0;
295 : } else {
296 0 : bn = canditer_slice(&ci, pos, pos + n);
297 0 : pos = n - 1;
298 : }
299 : } else { /* i.e. !asc, !nilslast */
300 : /* prefer nil and largest */
301 0 : if (pos < n) {
302 0 : bn = canditer_slice2(&ci, 0, pos, ci.ncand - (n - pos), ci.ncand);
303 : /* pos = pos; */
304 : } else {
305 0 : bn = canditer_slice(&ci, 0, n);
306 0 : pos = 0;
307 : }
308 : }
309 : } else { /* i.e. trevsorted */
310 : /* [0..pos) -- non-nil >>>
311 : * [pos..ci.ncand) -- nil
312 : */
313 0 : if (asc) { /* i.e. nilslast */
314 : /* prefer non-nil and
315 : * smallest */
316 0 : if (pos < n) {
317 0 : bn = canditer_slice(&ci, 0, n);
318 : /* pos = pos; */
319 : } else {
320 0 : bn = canditer_slice(&ci, pos - n, pos);
321 0 : pos = 0;
322 : }
323 : } else { /* i.e. !asc, !nilslast */
324 : /* prefer nil and largest */
325 0 : if (ci.ncand - pos < n) {
326 0 : bn = canditer_slice2(&ci, 0, n - (ci.ncand - pos), pos, ci.ncand);
327 0 : pos = n - (ci.ncand - pos) - 1;
328 : } else {
329 0 : bn = canditer_slice(&ci, pos, pos + n);
330 0 : pos = 0;
331 : }
332 : }
333 : }
334 : } else {
335 : /* either there are no nils, or they are in
336 : * the appropriate position already, so we can
337 : * just slice */
338 272 : if (asc ? bi->sorted : bi->revsorted) {
339 : /* return copy of first part of
340 : * candidate list */
341 250 : bn = canditer_slice(&ci, 0, n);
342 250 : pos = n - 1;
343 : } else {
344 : /* return copy of last part of
345 : * candidate list */
346 22 : bn = canditer_slice(&ci, ci.ncand - n, ci.ncand);
347 22 : pos = 0;
348 : }
349 : }
350 272 : if (bn && lastp)
351 56 : *lastp = BUNtoid(bn, pos);
352 272 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
353 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
354 : " (ordered -- " LLFMT " usec)\n",
355 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
356 : ALGOOPTBATPAR(bn), GDKusec() - t0);
357 272 : return bn;
358 : }
359 :
360 162 : bn = COLnew(0, TYPE_oid, n, TRANSIENT);
361 162 : if (bn == NULL)
362 : return NULL;
363 162 : BATsetcount(bn, n);
364 162 : oids = (oid *) Tloc(bn, 0);
365 162 : cmp = ATOMcompare(tpe);
366 162 : nil = ATOMnilptr(tpe);
367 : /* if base type has same comparison function as type itself, we
368 : * can use the base type */
369 162 : tpe = ATOMbasetype(tpe); /* takes care of oid */
370 : /* if the input happens to be almost sorted in ascending order
371 : * (likely a common use case), it is more efficient to start
372 : * off with the first n elements when doing a firstn-ascending
373 : * and to start off with the last n elements when doing a
374 : * firstn-descending so that most values that we look at after
375 : * this will be skipped. However, when using a bitmask
376 : * candidate list, the manipulation of the canditer structure
377 : * doesn't work like this, so we still work from the
378 : * beginning. */
379 162 : if (asc || ci.tpe == cand_mask) {
380 305715 : for (i = 0; i < n; i++)
381 305616 : oids[i] = canditer_next(&ci);
382 : } else {
383 63 : item = canditer_idx(&ci, ci.ncand - n);
384 63 : ci.next = ci.ncand - n;
385 63 : ci.add = item - ci.seq - (ci.ncand - n);
386 654 : for (i = n; i > 0; i--)
387 591 : oids[i - 1] = canditer_next(&ci);
388 63 : canditer_reset(&ci);
389 : }
390 :
391 162 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
392 :
393 162 : if (asc) {
394 99 : if (nilslast && !bi->nonil) {
395 14 : switch (tpe) {
396 2 : case TYPE_bte:
397 24 : shuffle_unique(bte, nLTbte);
398 : break;
399 0 : case TYPE_sht:
400 0 : shuffle_unique(sht, nLTsht);
401 : break;
402 2 : case TYPE_int:
403 22 : shuffle_unique(int, nLTint);
404 : break;
405 4 : case TYPE_lng:
406 47 : shuffle_unique(lng, nLTlng);
407 : break;
408 : #ifdef HAVE_HGE
409 0 : case TYPE_hge:
410 0 : shuffle_unique(hge, nLThge);
411 : break;
412 : #endif
413 2 : case TYPE_flt:
414 25 : shuffle_unique(flt, nLTflt);
415 : break;
416 0 : case TYPE_dbl:
417 0 : shuffle_unique(dbl, nLTdbl);
418 : break;
419 4 : default:
420 29 : heapify(nLTany, SWAP1);
421 14 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
422 6 : i = canditer_next(&ci);
423 6 : if (cmp(BUNtail(*bi, i - hseq), nil) != 0
424 5 : && (cmp(BUNtail(*bi, oids[0] - hseq), nil) == 0
425 1 : || cmp(BUNtail(*bi, i - hseq),
426 1 : BUNtail(*bi, oids[0] - hseq)) < 0)) {
427 5 : oids[0] = i;
428 15 : siftdown(nLTany, 0, SWAP1);
429 : }
430 : }
431 : break;
432 : }
433 : } else {
434 85 : switch (tpe) {
435 1 : case TYPE_bte:
436 666 : shuffle_unique(bte, LT);
437 : break;
438 0 : case TYPE_sht:
439 0 : shuffle_unique(sht, LT);
440 : break;
441 37 : case TYPE_int:
442 15689 : shuffle_unique(int, LT);
443 : break;
444 5 : case TYPE_lng:
445 7451861 : shuffle_unique(lng, LT);
446 : break;
447 : #ifdef HAVE_HGE
448 8 : case TYPE_hge:
449 100256 : shuffle_unique(hge, LT);
450 : break;
451 : #endif
452 0 : case TYPE_flt:
453 0 : shuffle_unique(flt, LTflt);
454 : break;
455 3 : case TYPE_dbl:
456 77670 : shuffle_unique(dbl, LTdbl);
457 : break;
458 31 : default:
459 3492 : heapify(LTany, SWAP1);
460 142957 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
461 142893 : i = canditer_next(&ci);
462 142893 : if (cmp(BUNtail(*bi, i - hseq),
463 142893 : BUNtail(*bi, oids[0] - hseq)) < 0) {
464 5722 : oids[0] = i;
465 172739 : siftdown(LTany, 0, SWAP1);
466 : }
467 : }
468 : break;
469 : }
470 : }
471 : } else {
472 63 : if (nilslast || bi->nonil) {
473 42 : switch (tpe) {
474 0 : case TYPE_bte:
475 0 : shuffle_unique(bte, GT);
476 : break;
477 0 : case TYPE_sht:
478 0 : shuffle_unique(sht, GT);
479 : break;
480 25 : case TYPE_int:
481 8446 : shuffle_unique(int, GT);
482 : break;
483 1 : case TYPE_lng:
484 2085 : shuffle_unique(lng, GT);
485 : break;
486 : #ifdef HAVE_HGE
487 5 : case TYPE_hge:
488 1436 : shuffle_unique(hge, GT);
489 : break;
490 : #endif
491 0 : case TYPE_flt:
492 0 : shuffle_unique(flt, GTflt);
493 : break;
494 2 : case TYPE_dbl:
495 24 : shuffle_unique(dbl, GTdbl);
496 : break;
497 9 : default:
498 51 : heapify(GTany, SWAP1);
499 49 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
500 31 : i = canditer_next(&ci);
501 31 : if (cmp(BUNtail(*bi, i - hseq),
502 31 : BUNtail(*bi, oids[0] - hseq)) > 0) {
503 19 : oids[0] = i;
504 60 : siftdown(GTany, 0, SWAP1);
505 : }
506 : }
507 : break;
508 : }
509 : } else {
510 21 : switch (tpe) {
511 1 : case TYPE_bte:
512 10 : shuffle_unique(bte, nGTbte);
513 : break;
514 0 : case TYPE_sht:
515 0 : shuffle_unique(sht, nGTsht);
516 : break;
517 2 : case TYPE_int:
518 20 : shuffle_unique(int, nGTint);
519 : break;
520 8 : case TYPE_lng:
521 80 : shuffle_unique(lng, nGTlng);
522 : break;
523 : #ifdef HAVE_HGE
524 0 : case TYPE_hge:
525 0 : shuffle_unique(hge, nGThge);
526 : break;
527 : #endif
528 2 : case TYPE_flt:
529 20 : shuffle_unique(flt, nGTflt);
530 : break;
531 2 : case TYPE_dbl:
532 20 : shuffle_unique(dbl, nGTdbl);
533 : break;
534 6 : default:
535 38 : heapify(nGTany, SWAP1);
536 25 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
537 13 : i = canditer_next(&ci);
538 13 : if (cmp(BUNtail(*bi, oids[0] - hseq), nil) != 0
539 13 : && (cmp(BUNtail(*bi, i - hseq), nil) == 0
540 11 : || cmp(BUNtail(*bi, i - hseq),
541 11 : BUNtail(*bi, oids[0] - hseq)) > 0)) {
542 13 : oids[0] = i;
543 34 : siftdown(nGTany, 0, SWAP1);
544 : }
545 : }
546 : break;
547 : }
548 : }
549 : }
550 162 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
551 162 : if (lastp)
552 55 : *lastp = oids[0]; /* store id of largest value */
553 : /* output must be sorted since it's a candidate list */
554 162 : GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
555 162 : bn->tsorted = true;
556 162 : bn->trevsorted = n <= 1;
557 162 : bn->tkey = true;
558 162 : bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
559 162 : bn->tnil = false;
560 162 : bn->tnonil = true;
561 162 : bn = virtualize(bn);
562 162 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
563 : ",n=" BUNFMT " -> " ALGOOPTBATFMT
564 : " (" LLFMT " usec)\n",
565 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
566 : ALGOOPTBATPAR(bn), GDKusec() - t0);
567 : return bn;
568 :
569 0 : bailout:
570 0 : BBPreclaim(bn);
571 0 : return NULL;
572 : }
573 :
574 : #define LTfixgrp(p1, p2) \
575 : (goids[p1] < goids[p2] || \
576 : (goids[p1] == goids[p2] && \
577 : LTfix(p1, p2)))
578 : #define nLTbtefixgrp(p1, p2) \
579 : (goids[p1] < goids[p2] || \
580 : (goids[p1] == goids[p2] && \
581 : nLTbtefix(p1, p2)))
582 : #define nLTshtfixgrp(p1, p2) \
583 : (goids[p1] < goids[p2] || \
584 : (goids[p1] == goids[p2] && \
585 : nLTshtfix(p1, p2)))
586 : #define nLTintfixgrp(p1, p2) \
587 : (goids[p1] < goids[p2] || \
588 : (goids[p1] == goids[p2] && \
589 : nLTintfix(p1, p2)))
590 : #define nLTlngfixgrp(p1, p2) \
591 : (goids[p1] < goids[p2] || \
592 : (goids[p1] == goids[p2] && \
593 : nLTlngfix(p1, p2)))
594 : #define nLThgefixgrp(p1, p2) \
595 : (goids[p1] < goids[p2] || \
596 : (goids[p1] == goids[p2] && \
597 : nLThgefix(p1, p2)))
598 : #define LTfltfixgrp(p1, p2) \
599 : (goids[p1] < goids[p2] || \
600 : (goids[p1] == goids[p2] && \
601 : LTfltfix(p1, p2)))
602 : #define LTdblfixgrp(p1, p2) \
603 : (goids[p1] < goids[p2] || \
604 : (goids[p1] == goids[p2] && \
605 : LTdblfix(p1, p2)))
606 : #define nLTfltfixgrp(p1, p2) \
607 : (goids[p1] < goids[p2] || \
608 : (goids[p1] == goids[p2] && \
609 : nLTfltfix(p1, p2)))
610 : #define nLTdblfixgrp(p1, p2) \
611 : (goids[p1] < goids[p2] || \
612 : (goids[p1] == goids[p2] && \
613 : nLTdblfix(p1, p2)))
614 : #define GTfixgrp(p1, p2) \
615 : (goids[p1] < goids[p2] || \
616 : (goids[p1] == goids[p2] && \
617 : GTfix(p1, p2)))
618 : #define nGTbtefixgrp(p1, p2) \
619 : (goids[p1] < goids[p2] || \
620 : (goids[p1] == goids[p2] && \
621 : nGTbtefix(p1, p2)))
622 : #define nGTshtfixgrp(p1, p2) \
623 : (goids[p1] < goids[p2] || \
624 : (goids[p1] == goids[p2] && \
625 : nGTshtfix(p1, p2)))
626 : #define nGTintfixgrp(p1, p2) \
627 : (goids[p1] < goids[p2] || \
628 : (goids[p1] == goids[p2] && \
629 : nGTintfix(p1, p2)))
630 : #define nGTlngfixgrp(p1, p2) \
631 : (goids[p1] < goids[p2] || \
632 : (goids[p1] == goids[p2] && \
633 : nGTlngfix(p1, p2)))
634 : #define nGThgefixgrp(p1, p2) \
635 : (goids[p1] < goids[p2] || \
636 : (goids[p1] == goids[p2] && \
637 : nGThgefix(p1, p2)))
638 : #define GTfltfixgrp(p1, p2) \
639 : (goids[p1] < goids[p2] || \
640 : (goids[p1] == goids[p2] && \
641 : GTfltfix(p1, p2)))
642 : #define GTdblfixgrp(p1, p2) \
643 : (goids[p1] < goids[p2] || \
644 : (goids[p1] == goids[p2] && \
645 : GTdblfix(p1, p2)))
646 : #define nGTfltfixgrp(p1, p2) \
647 : (goids[p1] < goids[p2] || \
648 : (goids[p1] == goids[p2] && \
649 : nGTfltfix(p1, p2)))
650 : #define nGTdblfixgrp(p1, p2) \
651 : (goids[p1] < goids[p2] || \
652 : (goids[p1] == goids[p2] && \
653 : nGTdblfix(p1, p2)))
654 : #define LTvoidgrp(p1, p2) \
655 : (goids[p1] < goids[p2] || \
656 : (goids[p1] == goids[p2] && oids[p1] < oids[p2]))
657 : #define GTvoidgrp(p1, p2) \
658 : (goids[p1] < goids[p2] || \
659 : (goids[p1] == goids[p2] && oids[p1] > oids[p2]))
660 : #define LTanygrp(p1, p2) \
661 : (goids[p1] < goids[p2] || \
662 : (goids[p1] == goids[p2] && \
663 : LTany(p1, p2)))
664 : #define GTanygrp(p1, p2) \
665 : (goids[p1] < goids[p2] || \
666 : (goids[p1] == goids[p2] && \
667 : GTany(p1, p2)))
668 : #define nLTanygrp(p1, p2) \
669 : (goids[p1] < goids[p2] || \
670 : (goids[p1] == goids[p2] && \
671 : nLTany(p1, p2)))
672 : #define nGTanygrp(p1, p2) \
673 : (goids[p1] < goids[p2] || \
674 : (goids[p1] == goids[p2] && \
675 : nGTany(p1, p2)))
676 : #define SWAP2(p1, p2) \
677 : do { \
678 : item = oids[p1]; \
679 : oids[p1] = oids[p2]; \
680 : oids[p2] = item; \
681 : item = goids[p1]; \
682 : goids[p1] = goids[p2]; \
683 : goids[p2] = item; \
684 : } while (0)
685 :
686 : #define shuffle_unique_with_groups(TYPE, OP) \
687 : do { \
688 : const TYPE *restrict vals = (const TYPE *) bi->base; \
689 : heapify(OP##fixgrp, SWAP2); \
690 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) { \
691 : i = canditer_next(&ci); \
692 : if (gv[j] < goids[0] || \
693 : (gv[j] == goids[0] && \
694 : OP(vals[i - hseq], \
695 : vals[oids[0] - hseq]))) { \
696 : oids[0] = i; \
697 : goids[0] = gv[j]; \
698 : siftdown(OP##fixgrp, 0, SWAP2); \
699 : } \
700 : j++; \
701 : } \
702 : } while (0)
703 :
704 : /* This version of BATfirstn is like the one above, except that it
705 : * also looks at groups. The values of the group IDs are important:
706 : * we return only the smallest N (i.e., not dependent on asc which
707 : * refers only to the values in the BAT b).
708 : *
709 : * If lastp is non-NULL, it is filled in with the oid of the "last"
710 : * value, i.e. the value of which there may be multiple occurrences
711 : * that are not all included in the first N. If lastgp is non-NULL,
712 : * it is filled with the group ID (not the oid of the group ID) for
713 : * that same value.
714 : */
715 : static BAT *
716 570 : BATfirstn_unique_with_groups(BATiter *bi, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, oid *lastp, oid *lastgp, lng t0)
717 : {
718 570 : BAT *bn;
719 570 : oid *restrict oids, *restrict goids;
720 570 : oid hseq = bi->b->hseqbase;
721 570 : const oid *restrict gv;
722 570 : BUN i, j;
723 570 : struct canditer ci;
724 570 : int tpe = bi->type;
725 570 : int (*cmp)(const void *, const void *);
726 570 : const void *nil;
727 : /* variables used in heapify/siftdown macros */
728 570 : oid item;
729 570 : BUN pos, childpos;
730 :
731 570 : MT_thread_setalgorithm(__func__);
732 570 : canditer_init(&ci, bi->b, s);
733 :
734 569 : if (n > ci.ncand)
735 : n = ci.ncand;
736 :
737 569 : if (n == 0) {
738 : /* candidate list might refer only to values outside
739 : * of the bat and hence be effectively empty */
740 0 : if (lastp)
741 0 : *lastp = 0;
742 0 : if (lastgp)
743 0 : *lastgp = 0;
744 0 : bn = BATdense(0, 0, 0);
745 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
746 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
747 : " (empty -- " LLFMT " usec)\n",
748 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
749 : ALGOOPTBATPAR(bn), GDKusec() - t0);
750 0 : return bn;
751 : }
752 :
753 569 : if (BATtdense(g)) {
754 : /* trivial: g determines ordering, return reference to
755 : * initial part of b (or slice of s) */
756 49 : if (lastgp)
757 18 : *lastgp = g->tseqbase + n - 1;
758 49 : bn = canditer_slice(&ci, 0, n);
759 49 : if (bn && lastp)
760 18 : *lastp = BUNtoid(bn, n - 1);
761 49 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
762 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
763 : " (dense group -- " LLFMT " usec)\n",
764 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
765 : ALGOOPTBATPAR(bn), GDKusec() - t0);
766 49 : return bn;
767 : }
768 :
769 520 : bn = COLnew(0, TYPE_oid, n, TRANSIENT);
770 521 : if (bn == NULL)
771 : return NULL;
772 521 : BATsetcount(bn, n);
773 521 : oids = (oid *) Tloc(bn, 0);
774 521 : gv = (const oid *) Tloc(g, 0);
775 521 : goids = GDKmalloc(n * sizeof(oid));
776 521 : if (goids == NULL) {
777 0 : BBPreclaim(bn);
778 0 : return NULL;
779 : }
780 :
781 521 : cmp = ATOMcompare(tpe);
782 521 : nil = ATOMnilptr(tpe);
783 : /* if base type has same comparison function as type itself, we
784 : * can use the base type */
785 521 : tpe = ATOMbasetype(tpe); /* takes care of oid */
786 521 : j = 0;
787 10901912 : for (i = 0; i < n; i++) {
788 10901391 : oids[i] = canditer_next(&ci);
789 10901391 : goids[i] = gv[j++];
790 : }
791 :
792 521 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
793 :
794 519 : if (BATtvoid(bi->b)) {
795 : /* nilslast doesn't make a difference (all nil, or no nil) */
796 0 : if (asc) {
797 0 : heapify(LTvoidgrp, SWAP2);
798 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
799 0 : i = canditer_next(&ci);
800 0 : if (gv[j] < goids[0]
801 : /* || (gv[j] == goids[0]
802 : && i < oids[0]) -- always false */) {
803 0 : oids[0] = i;
804 0 : goids[0] = gv[j];
805 0 : siftdown(LTvoidgrp, 0, SWAP2);
806 : }
807 0 : j++;
808 : }
809 : } else {
810 0 : heapify(GTvoidgrp, SWAP2);
811 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
812 0 : i = canditer_next(&ci);
813 0 : if (gv[j] < goids[0]
814 0 : || (gv[j] == goids[0]
815 : /* && i > oids[0] -- always true */)) {
816 0 : oids[0] = i;
817 0 : goids[0] = gv[j];
818 0 : siftdown(GTvoidgrp, 0, SWAP2);
819 : }
820 0 : j++;
821 : }
822 : }
823 519 : } else if (asc) {
824 446 : if (nilslast && !bi->nonil) {
825 0 : switch (tpe) {
826 0 : case TYPE_bte:
827 0 : shuffle_unique_with_groups(bte, nLTbte);
828 : break;
829 0 : case TYPE_sht:
830 0 : shuffle_unique_with_groups(sht, nLTsht);
831 : break;
832 0 : case TYPE_int:
833 0 : shuffle_unique_with_groups(int, nLTint);
834 : break;
835 0 : case TYPE_lng:
836 0 : shuffle_unique_with_groups(lng, nLTlng);
837 : break;
838 : #ifdef HAVE_HGE
839 0 : case TYPE_hge:
840 0 : shuffle_unique_with_groups(hge, nLThge);
841 : break;
842 : #endif
843 0 : case TYPE_flt:
844 0 : shuffle_unique_with_groups(flt, nLTflt);
845 : break;
846 0 : case TYPE_dbl:
847 0 : shuffle_unique_with_groups(dbl, nLTdbl);
848 : break;
849 0 : default:
850 0 : heapify(nLTanygrp, SWAP2);
851 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
852 0 : i = canditer_next(&ci);
853 0 : if (gv[j] < goids[0]
854 0 : || (gv[j] == goids[0]
855 0 : && cmp(BUNtail(*bi, i - hseq), nil) != 0
856 0 : && (cmp(BUNtail(*bi, oids[0] - hseq), nil) == 0
857 0 : || cmp(BUNtail(*bi, i - hseq),
858 0 : BUNtail(*bi, oids[0] - hseq)) < 0))) {
859 0 : oids[0] = i;
860 0 : goids[0] = gv[j];
861 0 : siftdown(nLTanygrp, 0, SWAP2);
862 : }
863 0 : j++;
864 : }
865 : break;
866 : }
867 : } else {
868 446 : switch (tpe) {
869 23 : case TYPE_bte:
870 1563112 : shuffle_unique_with_groups(bte, LT);
871 : break;
872 14 : case TYPE_sht:
873 1000077 : shuffle_unique_with_groups(sht, LT);
874 : break;
875 162 : case TYPE_int:
876 34988 : shuffle_unique_with_groups(int, LT);
877 : break;
878 11 : case TYPE_lng:
879 600633 : shuffle_unique_with_groups(lng, LT);
880 : break;
881 : #ifdef HAVE_HGE
882 34 : case TYPE_hge:
883 2747 : shuffle_unique_with_groups(hge, LT);
884 : break;
885 : #endif
886 0 : case TYPE_flt:
887 0 : shuffle_unique_with_groups(flt, LTflt);
888 : break;
889 4 : case TYPE_dbl:
890 19 : shuffle_unique_with_groups(dbl, LTdbl);
891 : break;
892 198 : default:
893 258331 : heapify(LTanygrp, SWAP2);
894 16068 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
895 15671 : i = canditer_next(&ci);
896 15671 : if (gv[j] < goids[0] ||
897 15507 : (gv[j] == goids[0] &&
898 15507 : cmp(BUNtail(*bi, i - hseq),
899 15507 : BUNtail(*bi, oids[0] - hseq)) < 0)) {
900 2312 : oids[0] = i;
901 2312 : goids[0] = gv[j];
902 14417 : siftdown(LTanygrp, 0, SWAP2);
903 : }
904 15671 : j++;
905 : }
906 : break;
907 : }
908 : }
909 73 : } else if (nilslast || bi->nonil) {
910 48 : switch (tpe) {
911 7 : case TYPE_bte:
912 204539 : shuffle_unique_with_groups(bte, GT);
913 : break;
914 0 : case TYPE_sht:
915 0 : shuffle_unique_with_groups(sht, GT);
916 : break;
917 17 : case TYPE_int:
918 5233355 : shuffle_unique_with_groups(int, GT);
919 : break;
920 0 : case TYPE_lng:
921 0 : shuffle_unique_with_groups(lng, GT);
922 : break;
923 : #ifdef HAVE_HGE
924 5 : case TYPE_hge:
925 722 : shuffle_unique_with_groups(hge, GT);
926 : break;
927 : #endif
928 0 : case TYPE_flt:
929 0 : shuffle_unique_with_groups(flt, GTflt);
930 : break;
931 10 : case TYPE_dbl:
932 230578 : shuffle_unique_with_groups(dbl, GTdbl);
933 : break;
934 9 : default:
935 54 : heapify(GTanygrp, SWAP2);
936 21 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
937 3 : i = canditer_next(&ci);
938 3 : if (gv[j] < goids[0] ||
939 2 : (gv[j] == goids[0] &&
940 2 : cmp(BUNtail(*bi, i - hseq),
941 2 : BUNtail(*bi, oids[0] - hseq)) > 0)) {
942 2 : oids[0] = i;
943 2 : goids[0] = gv[j];
944 5 : siftdown(GTanygrp, 0, SWAP2);
945 : }
946 3 : j++;
947 : }
948 : break;
949 : }
950 : } else {
951 25 : switch (tpe) {
952 2 : case TYPE_bte:
953 430116 : shuffle_unique_with_groups(bte, nGTbte);
954 : break;
955 0 : case TYPE_sht:
956 0 : shuffle_unique_with_groups(sht, nGTsht);
957 : break;
958 0 : case TYPE_int:
959 0 : shuffle_unique_with_groups(int, nGTint);
960 : break;
961 0 : case TYPE_lng:
962 0 : shuffle_unique_with_groups(lng, nGTlng);
963 : break;
964 : #ifdef HAVE_HGE
965 23 : case TYPE_hge:
966 1567068 : shuffle_unique_with_groups(hge, nGThge);
967 : break;
968 : #endif
969 0 : case TYPE_flt:
970 0 : shuffle_unique_with_groups(flt, nGTflt);
971 : break;
972 0 : case TYPE_dbl:
973 0 : shuffle_unique_with_groups(dbl, nGTdbl);
974 : break;
975 0 : default:
976 0 : heapify(nGTanygrp, SWAP2);
977 0 : TIMEOUT_LOOP(ci.ncand - n, qry_ctx) {
978 0 : i = canditer_next(&ci);
979 0 : if (gv[j] < goids[0]
980 0 : || (gv[j] == goids[0]
981 0 : && cmp(BUNtail(*bi, oids[0] - hseq), nil) != 0
982 0 : && (cmp(BUNtail(*bi, i - hseq), nil) == 0
983 0 : || cmp(BUNtail(*bi, i - hseq),
984 0 : BUNtail(*bi, oids[0] - hseq)) > 0))) {
985 0 : oids[0] = i;
986 0 : goids[0] = gv[j];
987 0 : siftdown(nGTanygrp, 0, SWAP2);
988 : }
989 0 : j++;
990 : }
991 : break;
992 : }
993 : }
994 520 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
995 519 : if (lastp)
996 313 : *lastp = oids[0];
997 519 : if (lastgp)
998 313 : *lastgp = goids[0];
999 519 : GDKfree(goids);
1000 : /* output must be sorted since it's a candidate list */
1001 521 : GDKqsort(oids, NULL, NULL, (size_t) n, sizeof(oid), 0, TYPE_oid, false, false);
1002 518 : bn->tsorted = true;
1003 518 : bn->trevsorted = n <= 1;
1004 518 : bn->tkey = true;
1005 518 : bn->tseqbase = n <= 1 ? oids[0] : oid_nil;
1006 518 : bn->tnil = false;
1007 518 : bn->tnonil = true;
1008 518 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1009 : ",g=" ALGOBATFMT ",n=" BUNFMT " -> " ALGOOPTBATFMT
1010 : " (" LLFMT " usec)\n",
1011 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1012 : ALGOOPTBATPAR(bn), GDKusec() - t0);
1013 : return bn;
1014 :
1015 0 : bailout:
1016 0 : GDKfree(goids);
1017 0 : BBPreclaim(bn);
1018 0 : return NULL;
1019 : }
1020 :
1021 : static gdk_return
1022 253 : BATfirstn_grouped(BAT **topn, BAT **gids, BATiter *bi, BAT *s, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
1023 : {
1024 253 : BAT *bn, *gn = NULL, *su = NULL;
1025 253 : oid last;
1026 253 : gdk_return rc;
1027 :
1028 253 : MT_thread_setalgorithm(__func__);
1029 253 : if (distinct && !bi->key) {
1030 0 : su = s;
1031 0 : s = BATunique(bi->b, s);
1032 0 : if (s == NULL)
1033 : return GDK_FAIL;
1034 : }
1035 253 : bn = BATfirstn_unique(bi, s, n, asc, nilslast, &last, t0);
1036 253 : if (bn == NULL)
1037 : return GDK_FAIL;
1038 253 : if (BATcount(bn) == 0) {
1039 0 : if (gids) {
1040 0 : gn = BATdense(0, 0, 0);
1041 0 : if (gn == NULL) {
1042 0 : BBPunfix(bn->batCacheid);
1043 0 : return GDK_FAIL;
1044 : }
1045 0 : *gids = gn;
1046 : }
1047 0 : *topn = bn;
1048 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1049 : ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1050 : " (empty -- " LLFMT " usec)\n",
1051 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
1052 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1053 0 : return GDK_SUCCEED;
1054 : }
1055 253 : if (!bi->key) {
1056 218 : if (distinct) {
1057 0 : BAT *bn1;
1058 :
1059 0 : bn1 = bn;
1060 0 : BBPunfix(s->batCacheid);
1061 0 : bn = BATintersect(bi->b, bi->b, su, bn1, true, false, BUN_NONE);
1062 0 : BBPunfix(bn1->batCacheid);
1063 0 : if (bn == NULL)
1064 : return GDK_FAIL;
1065 218 : } else if (last != oid_nil) {
1066 110 : BAT *bn1, *bn2;
1067 :
1068 110 : bn1 = bn;
1069 110 : bn2 = BATselect(bi->b, s, BUNtail(*bi, last - bi->b->hseqbase), NULL, true, false, false, false);
1070 110 : if (bn2 == NULL) {
1071 0 : BBPunfix(bn1->batCacheid);
1072 0 : return GDK_FAIL;
1073 : }
1074 110 : bn = BATmergecand(bn1, bn2);
1075 110 : BBPunfix(bn1->batCacheid);
1076 110 : BBPunfix(bn2->batCacheid);
1077 110 : if (bn == NULL)
1078 : return GDK_FAIL;
1079 : }
1080 : }
1081 253 : if (gids) {
1082 253 : BAT *bn1, *bn2, *bn3, *bn4;
1083 253 : bn1 = BATproject(bn, bi->b);
1084 253 : if (bn1 == NULL) {
1085 0 : BBPunfix(bn->batCacheid);
1086 0 : return GDK_FAIL;
1087 : }
1088 253 : rc = BATsort(NULL, &bn2, &bn3, bn1, NULL, NULL, !asc, !asc, false);
1089 253 : BBPunfix(bn1->batCacheid);
1090 253 : if (rc != GDK_SUCCEED) {
1091 0 : BBPunfix(bn->batCacheid);
1092 0 : return GDK_FAIL;
1093 : }
1094 253 : rc = BATsort(NULL, &bn4, NULL, bn2, NULL, NULL, false, false, false);
1095 253 : BBPunfix(bn2->batCacheid);
1096 253 : if (rc != GDK_SUCCEED) {
1097 0 : BBPunfix(bn->batCacheid);
1098 0 : BBPunfix(bn3->batCacheid);
1099 0 : return GDK_FAIL;
1100 : }
1101 253 : gn = BATproject(bn4, bn3);
1102 253 : BBPunfix(bn3->batCacheid);
1103 251 : BBPunfix(bn4->batCacheid);
1104 253 : if (gn == NULL) {
1105 0 : BBPunfix(bn->batCacheid);
1106 0 : return GDK_FAIL;
1107 : }
1108 253 : *gids = gn;
1109 253 : assert(BATcount(gn) == BATcount(bn));
1110 : }
1111 253 : *topn = bn;
1112 253 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1113 : ",n=" BUNFMT " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1114 : " (" LLFMT " usec)\n",
1115 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), n,
1116 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1117 : return GDK_SUCCEED;
1118 : }
1119 :
1120 : static gdk_return
1121 333 : BATfirstn_grouped_with_groups(BAT **topn, BAT **gids, BATiter *bi, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct, lng t0)
1122 : {
1123 333 : BAT *bn, *gn = NULL;
1124 333 : oid hseq = bi->b->hseqbase;
1125 333 : oid last, lastg;
1126 333 : gdk_return rc;
1127 :
1128 333 : MT_thread_setalgorithm(__func__);
1129 333 : if (distinct) {
1130 0 : BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7;
1131 0 : if (BATgroup(&bn1, &bn2, NULL, bi->b, s, g, NULL, NULL) != GDK_SUCCEED)
1132 0 : return GDK_FAIL;
1133 0 : bn3 = BATproject(bn2, bi->b);
1134 0 : if (bn3 == NULL) {
1135 0 : BBPunfix(bn1->batCacheid);
1136 0 : BBPunfix(bn2->batCacheid);
1137 0 : return GDK_FAIL;
1138 : }
1139 0 : bn4 = BATintersect(s, bn2, NULL, NULL, false, false, BUN_NONE);
1140 0 : BBPunfix(bn2->batCacheid);
1141 0 : if (bn4 == NULL) {
1142 0 : BBPunfix(bn1->batCacheid);
1143 0 : return GDK_FAIL;
1144 : }
1145 0 : bn5 = BATproject(bn4, g);
1146 0 : BBPunfix(bn4->batCacheid);
1147 0 : if (bn5 == NULL) {
1148 0 : BBPunfix(bn1->batCacheid);
1149 0 : return GDK_FAIL;
1150 : }
1151 0 : BATiter bn3i = bat_iterator(bn3);
1152 0 : bn6 = BATfirstn_unique_with_groups(&bn3i, NULL, bn5, n, asc, nilslast, NULL, NULL, t0);
1153 0 : bat_iterator_end(&bn3i);
1154 0 : BBPunfix(bn3->batCacheid);
1155 0 : BBPunfix(bn5->batCacheid);
1156 0 : if (bn6 == NULL) {
1157 0 : BBPunfix(bn1->batCacheid);
1158 0 : return GDK_FAIL;
1159 : }
1160 0 : rc = BATleftjoin(&bn7, NULL, bn1, bn6, NULL, NULL, false, BUN_NONE);
1161 0 : BBPunfix(bn6->batCacheid);
1162 0 : if (rc != GDK_SUCCEED)
1163 : return GDK_FAIL;
1164 0 : bn = BATproject(bn7, s);
1165 0 : BBPunfix(bn7->batCacheid);
1166 0 : if (bn == NULL)
1167 : return GDK_FAIL;
1168 : } else {
1169 333 : bn = BATfirstn_unique_with_groups(bi, s, g, n, asc, nilslast, &last, &lastg, t0);
1170 331 : if (bn == NULL)
1171 : return GDK_FAIL;
1172 : }
1173 331 : if (BATcount(bn) == 0) {
1174 0 : if (gids) {
1175 0 : gn = BATdense(0, 0, 0);
1176 0 : if (gn == NULL) {
1177 0 : BBPunfix(bn->batCacheid);
1178 0 : return GDK_FAIL;
1179 : }
1180 0 : *gids = gn;
1181 : }
1182 0 : *topn = bn;
1183 0 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1184 : ",g=" ALGOBATFMT ",n=" BUNFMT
1185 : " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1186 : " (empty -- " LLFMT " usec)\n",
1187 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1188 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1189 0 : return GDK_SUCCEED;
1190 : }
1191 331 : if (!distinct && !bi->key) {
1192 307 : BAT *bn1, *bn2, *bn3, *bn4;
1193 :
1194 307 : bn1 = bn;
1195 307 : bn2 = BATselect(g, NULL, &lastg, NULL, true, false, false, false);
1196 303 : if (bn2 == NULL) {
1197 0 : BBPunfix(bn1->batCacheid);
1198 0 : return GDK_FAIL;
1199 : }
1200 303 : bn3 = BATproject(bn2, s);
1201 305 : BBPunfix(bn2->batCacheid);
1202 305 : if (bn3 == NULL) {
1203 0 : BBPunfix(bn1->batCacheid);
1204 0 : return GDK_FAIL;
1205 : }
1206 305 : bn4 = BATselect(bi->b, bn3, BUNtail(*bi, last - hseq), NULL, true, false, false, false);
1207 305 : BBPunfix(bn3->batCacheid);
1208 307 : if (bn4 == NULL) {
1209 0 : BBPunfix(bn1->batCacheid);
1210 0 : return GDK_FAIL;
1211 : }
1212 307 : bn = BATmergecand(bn1, bn4);
1213 307 : BBPunfix(bn1->batCacheid);
1214 308 : BBPunfix(bn4->batCacheid);
1215 308 : if (bn == NULL)
1216 : return GDK_FAIL;
1217 : }
1218 332 : if (gids) {
1219 333 : BAT *bn1, *bn2, *bn3, *bn4, *bn5, *bn6, *bn7, *bn8;
1220 :
1221 333 : if ((bn1 = BATintersect(s, bn, NULL, NULL, false, false, BUN_NONE)) == NULL) {
1222 0 : BBPunfix(bn->batCacheid);
1223 0 : return GDK_FAIL;
1224 : }
1225 330 : bn2 = BATproject(bn1, g);
1226 331 : BBPunfix(bn1->batCacheid);
1227 332 : if (bn2 == NULL) {
1228 0 : BBPunfix(bn->batCacheid);
1229 0 : return GDK_FAIL;
1230 : }
1231 332 : bn3 = BATproject(bn, bi->b);
1232 332 : if (bn3 == NULL) {
1233 0 : BBPunfix(bn2->batCacheid);
1234 0 : return GDK_FAIL;
1235 : }
1236 332 : rc = BATsort(NULL, &bn4, &bn5, bn2, NULL, NULL, false, false, false);
1237 330 : BBPunfix(bn2->batCacheid);
1238 331 : if (rc != GDK_SUCCEED) {
1239 0 : BBPunfix(bn->batCacheid);
1240 0 : BBPunfix(bn3->batCacheid);
1241 0 : return GDK_FAIL;
1242 : }
1243 331 : rc = BATsort(NULL, &bn6, &bn7, bn3, bn4, bn5, !asc, !asc, false);
1244 332 : BBPunfix(bn3->batCacheid);
1245 333 : BBPunfix(bn4->batCacheid);
1246 332 : BBPunfix(bn5->batCacheid);
1247 331 : if (rc != GDK_SUCCEED) {
1248 0 : BBPunfix(bn->batCacheid);
1249 0 : return GDK_FAIL;
1250 : }
1251 331 : rc = BATsort(NULL, &bn8, NULL, bn6, NULL, NULL, false, false, false);
1252 330 : BBPunfix(bn6->batCacheid);
1253 333 : if (rc != GDK_SUCCEED) {
1254 0 : BBPunfix(bn->batCacheid);
1255 0 : BBPunfix(bn7->batCacheid);
1256 0 : return GDK_FAIL;
1257 : }
1258 333 : gn = BATproject(bn8, bn7);
1259 329 : BBPunfix(bn7->batCacheid);
1260 333 : BBPunfix(bn8->batCacheid);
1261 333 : if (gn == NULL) {
1262 0 : BBPunfix(bn->batCacheid);
1263 0 : return GDK_FAIL;
1264 : }
1265 333 : *gids = gn;
1266 333 : assert(BATcount(gn) == BATcount(bn));
1267 : }
1268 332 : *topn = bn;
1269 332 : TRC_DEBUG(ALGO, "b=" ALGOBATFMT ",s=" ALGOOPTBATFMT
1270 : ",g=" ALGOBATFMT ",n=" BUNFMT
1271 : " -> " ALGOOPTBATFMT "," ALGOOPTBATFMT
1272 : " (" LLFMT " usec)\n",
1273 : ALGOBATPAR(bi->b), ALGOOPTBATPAR(s), ALGOBATPAR(g), n,
1274 : ALGOOPTBATPAR(bn), ALGOOPTBATPAR(gn), GDKusec() - t0);
1275 : return GDK_SUCCEED;
1276 : }
1277 :
1278 : gdk_return
1279 1714 : BATfirstn(BAT **topn, BAT **gids, BAT *b, BAT *s, BAT *g, BUN n, bool asc, bool nilslast, bool distinct)
1280 : {
1281 1714 : lng t0 = 0;
1282 1714 : gdk_return rc = GDK_SUCCEED;
1283 :
1284 1714 : assert(topn != NULL);
1285 1714 : if (b == NULL) {
1286 0 : *topn = NULL;
1287 0 : return GDK_SUCCEED;
1288 : }
1289 :
1290 1714 : TRC_DEBUG_IF(ALGO) t0 = GDKusec();
1291 :
1292 1714 : (void) BATordered(b);
1293 1723 : (void) BATordered_rev(b);
1294 :
1295 1723 : BATiter bi = bat_iterator(b);
1296 :
1297 : /* if g specified, then so must s */
1298 1722 : assert(g == NULL || s != NULL);
1299 : /* g and s must be aligned (same size, same hseqbase) */
1300 1722 : assert(g == NULL || BATcount(s) == BATcount(g));
1301 604 : assert(g == NULL || BATcount(g) == 0 || s->hseqbase == g->hseqbase);
1302 :
1303 1722 : if (n == 0 || BATcount(b) == 0 || (s != NULL && BATcount(s) == 0)) {
1304 : /* trivial: empty result */
1305 80 : *topn = BATdense(0, 0, 0);
1306 80 : if (*topn == NULL) {
1307 : rc = GDK_FAIL;
1308 80 : } else if (gids) {
1309 37 : *gids = BATdense(0, 0, 0);
1310 37 : if (*gids == NULL) {
1311 0 : BBPreclaim(*topn);
1312 : rc = GDK_FAIL;
1313 : }
1314 : }
1315 1642 : } else if (g == NULL) {
1316 1072 : if (gids == NULL && !distinct) {
1317 819 : *topn = BATfirstn_unique(&bi, s, n, asc, nilslast, NULL, t0);
1318 808 : rc = *topn ? GDK_SUCCEED : GDK_FAIL;
1319 : } else {
1320 253 : rc = BATfirstn_grouped(topn, gids, &bi, s, n, asc, nilslast, distinct, t0);
1321 : }
1322 570 : } else if (gids == NULL && !distinct) {
1323 237 : *topn = BATfirstn_unique_with_groups(&bi, s, g, n, asc, nilslast, NULL, NULL, t0);
1324 236 : rc = *topn ? GDK_SUCCEED : GDK_FAIL;
1325 : } else {
1326 333 : rc = BATfirstn_grouped_with_groups(topn, gids, &bi, s, g, n, asc, nilslast, distinct, t0);
1327 : }
1328 1706 : bat_iterator_end(&bi);
1329 1706 : return rc;
1330 : }
1331 :
1332 : /* Calculate the first N values for each group given in G of the bats in
1333 : * BATS (of which there are NBATS), but only considering the candidates
1334 : * in S.
1335 : *
1336 : * Conceptually, the bats in BATS are sorted per group, taking the
1337 : * candidate list S and the values in ASC and NILSLAST into account.
1338 : * For each group, the first N rows are then returned.
1339 : *
1340 : * For each bat, the sort order that is to be used is specified in the
1341 : * array ASC. The first N values means the smallest N values if asc is
1342 : * set, the largest if not set. If NILSLAST for a bat is set, nils are
1343 : * only returned if there are not enough non-nil values; if nilslast is
1344 : * not set, nils are returned preferentially.
1345 : *
1346 : * The return value is a bat with N consecutive values for each group in
1347 : * G. Values are nil if there are not enough values in the group, else
1348 : * they are row ids of the first rows.
1349 : */
1350 : BAT *
1351 6 : BATgroupedfirstn(BUN n, BAT *s, BAT *g, int nbats, BAT **bats, bool *asc, bool *nilslast)
1352 : {
1353 6 : const char *err;
1354 6 : oid min, max;
1355 6 : BUN ngrp;
1356 6 : struct canditer ci;
1357 6 : QryCtx *qry_ctx = MT_thread_get_qry_ctx();
1358 6 : struct batinfo {
1359 : BATiter bi1;
1360 : BATiter bi2;
1361 : oid hseq;
1362 : bool asc;
1363 : bool nilslast;
1364 : const void *nil;
1365 : int (*cmp)(const void *, const void *);
1366 : } *batinfo;
1367 :
1368 6 : assert(nbats > 0);
1369 :
1370 6 : if (n == 0 || BATcount(bats[0]) == 0) {
1371 1 : return BATdense(0, 0, 0);
1372 : }
1373 5 : if (n > BATcount(bats[0]))
1374 : n = BATcount(bats[0]);
1375 :
1376 5 : if ((err = BATgroupaggrinit(bats[0], g, NULL /* e */, s, &min, &max, &ngrp, &ci)) != NULL) {
1377 0 : GDKerror("%s\n", err);
1378 0 : return NULL;
1379 : }
1380 :
1381 5 : batinfo = GDKmalloc(nbats * sizeof(struct batinfo));
1382 5 : if (batinfo == NULL)
1383 : return NULL;
1384 :
1385 5 : BAT *bn = BATconstant(0, TYPE_oid, &oid_nil, ngrp * n, TRANSIENT);
1386 5 : if (bn == NULL) {
1387 0 : GDKfree(batinfo);
1388 0 : return NULL;
1389 : }
1390 : /* result is unlikely to be sorted, and there may be nils if
1391 : * there are groups that are too small */
1392 5 : bn->tsorted = bn->trevsorted = bn->batCount <= 1;
1393 5 : bn->tnil = false;
1394 5 : bn->tnonil = false;
1395 :
1396 10 : for (int i = 0; i < nbats; i++) {
1397 10 : batinfo[i] = (struct batinfo) {
1398 5 : .bi1 = bat_iterator(bats[i]),
1399 5 : .bi2 = bat_iterator(bats[i]),
1400 5 : .asc = asc ? asc[i] : false,
1401 5 : .nilslast = nilslast ? nilslast[i] : true,
1402 5 : .cmp = ATOMcompare(bats[i]->ttype),
1403 5 : .hseq = bats[i]->hseqbase,
1404 5 : .nil = ATOMnilptr(bats[i]->ttype),
1405 : };
1406 : }
1407 :
1408 : /* For each group we maintain a "heap" of N values inside the
1409 : * return bat BN. The heap for group GRP is located in BN at
1410 : * BUN [grp*N..(grp+1)*N). The first value in this heap is the
1411 : * "largest" (assuming all ASC bits are set) value so far. */
1412 5 : oid *oids = Tloc(bn, 0);
1413 1020146 : TIMEOUT_LOOP(ci.ncand, qry_ctx) {
1414 1020076 : oid o = canditer_next(&ci);
1415 1020076 : oid grp = g ? BUNtoid(g, o - g->hseqbase) : 0;
1416 1020076 : BUN goff = grp * n;
1417 1020076 : int comp = -1;
1418 : /* compare new value with root of heap to see if we must
1419 : * keep or replace */
1420 1020076 : if (!is_oid_nil(oids[goff])) {
1421 1017583 : for (int i = 0; i < nbats; i++) {
1422 1017574 : comp = batinfo[i].cmp(BUNtail(batinfo[i].bi1, o - batinfo[i].hseq),
1423 1017574 : BUNtail(batinfo[i].bi2, oids[goff] - batinfo[i].hseq));
1424 1017574 : if (comp == 0)
1425 9 : continue;
1426 1017565 : if (!batinfo[i].asc)
1427 1017565 : comp = -comp;
1428 1017565 : if (!batinfo[i].bi1.nonil) {
1429 0 : if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, o - batinfo[i].hseq),
1430 : batinfo[i].nil) == 0) {
1431 0 : if (batinfo[i].nilslast)
1432 : comp = 1;
1433 : else
1434 : comp = -1;
1435 0 : } else if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff] - batinfo[i].hseq),
1436 : batinfo[i].nil) == 0) {
1437 0 : if (batinfo[i].nilslast)
1438 : comp = -1;
1439 : else
1440 : comp = 1;
1441 : }
1442 : }
1443 : break;
1444 : }
1445 : }
1446 : /* at this point, if comp==0, the incoming value is
1447 : * equal to what we currently have as the last of the
1448 : * first-n and so we skip it; if comp<0, the incoming
1449 : * value is better than the worst so far, so it replaces
1450 : * that one, and if comp>0, the incoming value is
1451 : * definitely not in the first-n */
1452 1017574 : if (comp >= 0)
1453 999033 : continue;
1454 21043 : oids[goff] = o;
1455 : /* we replaced the root of the heap, but now we need to
1456 : * restore the heap property */
1457 21043 : BUN pos = 0;
1458 21043 : BUN childpos = 1;
1459 120073 : while (childpos < n) {
1460 : /* find most extreme child */
1461 107654 : if (childpos + 1 < n) {
1462 107204 : if (!is_oid_nil(oids[goff + childpos])) {
1463 101384 : if (is_oid_nil(oids[goff + childpos + 1]))
1464 : childpos++;
1465 : else {
1466 97004 : for (int i = 0; i < nbats; i++) {
1467 96466 : if ((comp = batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + childpos] - batinfo[i].hseq),
1468 96466 : BUNtail(batinfo[i].bi2, oids[goff + childpos + 1] - batinfo[i].hseq))) == 0)
1469 538 : continue;
1470 95928 : if (!batinfo[i].bi1.nonil) {
1471 0 : if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + childpos] - batinfo[i].hseq), batinfo[i].nil) == 0) {
1472 0 : if (!batinfo[i].nilslast)
1473 45103 : childpos++;
1474 : break;
1475 : }
1476 0 : if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + childpos + 1] - batinfo[i].hseq), batinfo[i].nil) == 0) {
1477 0 : if (batinfo[i].nilslast)
1478 45103 : childpos++;
1479 : break;
1480 : }
1481 : }
1482 95928 : if (batinfo[i].asc ? comp < 0 : comp > 0)
1483 45103 : childpos++;
1484 : break;
1485 : }
1486 : }
1487 : }
1488 : }
1489 : /* compare parent with most extreme child */
1490 107654 : if (!is_oid_nil(oids[goff + childpos])) {
1491 96967 : for (int i = 0; i < nbats; i++) {
1492 96894 : if ((comp = batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + pos] - batinfo[i].hseq),
1493 96894 : BUNtail(batinfo[i].bi2, oids[goff + childpos] - batinfo[i].hseq))) == 0)
1494 73 : continue;
1495 96821 : if (batinfo[i].asc ? comp > 0 : comp < 0)
1496 8551 : comp = 0;
1497 96821 : if (!batinfo[i].bi1.nonil) {
1498 0 : if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + pos] - batinfo[i].hseq), batinfo[i].nil) == 0)
1499 0 : comp = !batinfo[i].nilslast;
1500 0 : else if (batinfo[i].cmp(BUNtail(batinfo[i].bi1, oids[goff + childpos] - batinfo[i].hseq), batinfo[i].nil) == 0)
1501 0 : comp = batinfo[i].nilslast;
1502 : }
1503 : break;
1504 : }
1505 96894 : if (comp == 0) {
1506 : /* already correctly ordered */
1507 : break;
1508 : }
1509 : }
1510 99030 : oid o = oids[goff + pos];
1511 99030 : oids[goff + pos] = oids[goff + childpos];
1512 99030 : oids[goff + childpos] = o;
1513 99030 : pos = childpos;
1514 99030 : childpos = (pos << 1) + 1;
1515 : }
1516 : }
1517 10 : for (int i = 0; i < nbats; i++) {
1518 5 : bat_iterator_end(&batinfo[i].bi1);
1519 5 : bat_iterator_end(&batinfo[i].bi2);
1520 : }
1521 5 : GDKfree(batinfo);
1522 5 : TIMEOUT_CHECK(qry_ctx, GOTO_LABEL_TIMEOUT_HANDLER(bailout, qry_ctx));
1523 : return bn;
1524 :
1525 0 : bailout:
1526 0 : BBPreclaim(bn);
1527 0 : return NULL;
1528 : }
|
