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 : /*
14 : * @a Lefteris Sidirourgos, Hannes Muehleisen
15 : * @* Low level sample facilities
16 : *
17 : * This sampling implementation generates a sorted set of OIDs by
18 : * calling the random number generator, and uses a binary tree to
19 : * eliminate duplicates. The elements of the tree are then used to
20 : * create a sorted sample BAT. This implementation has a logarithmic
21 : * complexity that only depends on the sample size.
22 : *
23 : * There is a pathological case when the sample size is almost the
24 : * size of the BAT. Then, many collisions occur and performance
25 : * degrades. To catch this, we switch to antiset semantics when the
26 : * sample size is larger than half the BAT size. Then, we generate the
27 : * values that should be omitted from the sample.
28 : */
29 :
30 : #include "monetdb_config.h"
31 : #include "gdk.h"
32 : #include "gdk_private.h"
33 : #include "xoshiro256starstar.h"
34 :
35 : /* this is a straightforward implementation of a binary tree */
36 : struct oidtreenode {
37 : union {
38 : struct { /* use as a binary tree */
39 : oid o;
40 : struct oidtreenode *left;
41 : struct oidtreenode *right;
42 : };
43 : uint64_t r; /* temporary storage for random numbers */
44 : };
45 : };
46 :
47 : static bool
48 41482227 : OIDTreeMaybeInsert(struct oidtreenode *tree, oid o, BUN allocated)
49 : {
50 41482227 : struct oidtreenode **nodep;
51 :
52 41482227 : if (allocated == 0) {
53 128525 : tree->left = tree->right = NULL;
54 128525 : tree->o = o;
55 128525 : return true;
56 : }
57 : nodep = &tree;
58 440954992 : while (*nodep) {
59 403810746 : if (o == (*nodep)->o)
60 : return false;
61 399601290 : if (o < (*nodep)->o)
62 199706684 : nodep = &(*nodep)->left;
63 : else
64 199894606 : nodep = &(*nodep)->right;
65 : }
66 37144246 : *nodep = &tree[allocated];
67 37144246 : tree[allocated].left = tree[allocated].right = NULL;
68 37144246 : tree[allocated].o = o;
69 37144246 : return true;
70 : }
71 :
72 : /* inorder traversal, gives us a sorted BAT */
73 : static void
74 11498887 : OIDTreeToBAT(struct oidtreenode *node, BAT *bn)
75 : {
76 22980362 : if (node->left != NULL)
77 11475900 : OIDTreeToBAT(node->left, bn);
78 22980362 : ((oid *) bn->theap->base)[bn->batCount++] = node->o;
79 22980362 : if (node->right != NULL )
80 : OIDTreeToBAT(node->right, bn);
81 11498887 : }
82 :
83 : /* Antiset traversal, give us all values but the ones in the tree */
84 : static void
85 7200132 : OIDTreeToBATAntiset(struct oidtreenode *node, BAT *bn, oid start, oid stop)
86 : {
87 14292409 : oid noid;
88 :
89 14292409 : if (node->left != NULL)
90 7094594 : OIDTreeToBATAntiset(node->left, bn, start, node->o);
91 : else
92 59950879 : for (noid = start; noid < node->o; noid++)
93 52753064 : ((oid *) bn->theap->base)[bn->batCount++] = noid;
94 :
95 14292409 : if (node->right != NULL)
96 7092277 : OIDTreeToBATAntiset(node->right, bn, node->o + 1, stop);
97 : else
98 59980188 : for (noid = node->o+1; noid < stop; noid++)
99 52780056 : ((oid *) bn->theap->base)[bn->batCount++] = noid;
100 7200132 : }
101 :
102 : static BAT *
103 1026876 : do_batsample(oid hseq, BUN cnt, BUN n, random_state_engine rse, MT_Lock *lock)
104 : {
105 1026876 : BAT *bn;
106 1026876 : BUN slen;
107 1026876 : BUN rescnt;
108 1026876 : struct oidtreenode *tree = NULL;
109 :
110 1026876 : ERRORcheck(n > BUN_MAX, "sample size larger than BUN_MAX\n", NULL);
111 : /* empty sample size */
112 1026876 : if (n == 0) {
113 2 : bn = BATdense(0, 0, 0);
114 1026874 : } else if (cnt <= n) {
115 : /* sample size is larger than the input BAT, return
116 : * all oids */
117 898354 : bn = BATdense(0, hseq, cnt);
118 : } else {
119 128520 : oid minoid = hseq;
120 128520 : oid maxoid = hseq + cnt;
121 :
122 : /* if someone samples more than half of our tree, we
123 : * do the antiset */
124 128520 : bool antiset = n > cnt / 2;
125 128520 : slen = n;
126 128520 : if (antiset)
127 105538 : n = cnt - n;
128 :
129 128520 : tree = GDKmalloc(n * sizeof(struct oidtreenode));
130 128522 : if (tree == NULL) {
131 : return NULL;
132 : }
133 128522 : bn = COLnew(0, TYPE_oid, slen, TRANSIENT);
134 128513 : if (bn == NULL) {
135 0 : GDKfree(tree);
136 0 : return NULL;
137 : }
138 :
139 128513 : if (lock)
140 128503 : MT_lock_set(lock);
141 : /* generate a list of random numbers; note we use the
142 : * "tree" array, but we use the value from each location
143 : * before it is overwritten by the use as part of the
144 : * binary tree */
145 37401296 : for (rescnt = 0; rescnt < n; rescnt++)
146 37272771 : tree[rescnt].r = next(rse);
147 :
148 : /* while we do not have enough sample OIDs yet */
149 : BUN rnd = 0;
150 37401296 : for (rescnt = 0; rescnt < n; rescnt++) {
151 41482227 : oid candoid;
152 41482227 : do {
153 41482227 : if (rnd == n) {
154 : /* we ran out of random numbers,
155 : * so generate more */
156 4462657 : for (rnd = rescnt; rnd < n; rnd++)
157 4209456 : tree[rnd].r = next(rse);
158 : rnd = rescnt;
159 : }
160 41482227 : candoid = minoid + tree[rnd++].r % cnt;
161 : /* if that candidate OID was already
162 : * generated, try again */
163 41482227 : } while (!OIDTreeMaybeInsert(tree, candoid, rescnt));
164 : }
165 128525 : if (lock)
166 128515 : MT_lock_unset(lock);
167 128525 : if (!antiset) {
168 22987 : OIDTreeToBAT(tree, bn);
169 : } else {
170 105538 : OIDTreeToBATAntiset(tree, bn, minoid, maxoid);
171 : }
172 128525 : GDKfree(tree);
173 :
174 128525 : BATsetcount(bn, slen);
175 128525 : bn->trevsorted = bn->batCount <= 1;
176 128525 : bn->tsorted = true;
177 128525 : bn->tkey = true;
178 128525 : bn->tseqbase = bn->batCount == 0 ? 0 : bn->batCount == 1 ? *(oid *) Tloc(bn, 0) : oid_nil;
179 : }
180 : return bn;
181 : }
182 :
183 : /* BATsample implements sampling for BATs */
184 : BAT *
185 10 : BATsample_with_seed(BAT *b, BUN n, uint64_t seed)
186 : {
187 10 : random_state_engine rse;
188 :
189 10 : init_random_state_engine(rse, seed);
190 :
191 10 : BAT *bn = do_batsample(b->hseqbase, BATcount(b), n, rse, NULL);
192 10 : TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT "\n",
193 : ALGOBATPAR(b), n, ALGOOPTBATPAR(bn));
194 10 : return bn;
195 : }
196 :
197 : static MT_Lock rse_lock = MT_LOCK_INITIALIZER(rse_lock);
198 : BAT *
199 1026537 : BATsample(BAT *b, BUN n)
200 : {
201 1026537 : static random_state_engine rse;
202 :
203 1026537 : MT_lock_set(&rse_lock);
204 1026872 : if (rse[0] == 0 && rse[1] == 0 && rse[2] == 0 && rse[3] == 0)
205 319 : init_random_state_engine(rse, (uint64_t) GDKusec());
206 1026872 : MT_lock_unset(&rse_lock);
207 1026872 : BAT *bn = do_batsample(b->hseqbase, BATcount(b), n, rse, &rse_lock);
208 1026578 : TRC_DEBUG(ALGO, ALGOBATFMT "," BUNFMT " -> " ALGOOPTBATFMT "\n",
209 : ALGOBATPAR(b), n, ALGOOPTBATPAR(bn));
210 1026578 : return bn;
211 : }
|
