1/* hyperloglog.c - Redis HyperLogLog probabilistic cardinality approximation.
2 * This file implements the algorithm and the exported Redis commands.
3 *
4 * Copyright (c) 2014, Salvatore Sanfilippo <antirez at gmail dot com>
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are met:
9 *
10 * * Redistributions of source code must retain the above copyright notice,
11 * this list of conditions and the following disclaimer.
12 * * Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * * Neither the name of Redis nor the names of its contributors may be used
16 * to endorse or promote products derived from this software without
17 * specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
23 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#include "duckdb/common/vector.hpp"
33#include "duckdb/common/types/hyperloglog.hpp"
34
35#include "hyperloglog.hpp"
36#include "sds.hpp"
37
38#include <assert.h>
39#include <stdint.h>
40#include <math.h>
41#include <stddef.h>
42#include <string.h>
43#include <stdlib.h>
44
45
46
47namespace duckdb_hll {
48
49#define HLL_SPARSE_MAX_BYTES 3000
50
51/* The Redis HyperLogLog implementation is based on the following ideas:
52 *
53 * * The use of a 64 bit hash function as proposed in [1], in order to don't
54 * limited to cardinalities up to 10^9, at the cost of just 1 additional
55 * bit per register.
56 * * The use of 16384 6-bit registers for a great level of accuracy, using
57 * a total of 12k per key.
58 * * The use of the Redis string data type. No new type is introduced.
59 * * No attempt is made to compress the data structure as in [1]. Also the
60 * algorithm used is the original HyperLogLog Algorithm as in [2], with
61 * the only difference that a 64 bit hash function is used, so no correction
62 * is performed for values near 2^32 as in [1].
63 *
64 * [1] Heule, Nunkesser, Hall: HyperLogLog in Practice: Algorithmic
65 * Engineering of a State of The Art Cardinality Estimation Algorithm.
66 *
67 * [2] P. Flajolet, Éric Fusy, O. Gandouet, and F. Meunier. Hyperloglog: The
68 * analysis of a near-optimal cardinality estimation algorithm.
69 *
70 * Redis uses two representations:
71 *
72 * 1) A "dense" representation where every entry is represented by
73 * a 6-bit integer.
74 * 2) A "sparse" representation using run length compression suitable
75 * for representing HyperLogLogs with many registers set to 0 in
76 * a memory efficient way.
77 *
78 *
79 * HLL header
80 * ===
81 *
82 * Both the dense and sparse representation have a 16 byte header as follows:
83 *
84 * +------+---+-----+----------+
85 * | HYLL | E | N/U | Cardin. |
86 * +------+---+-----+----------+
87 *
88 * The first 4 bytes are a magic string set to the bytes "HYLL".
89 * "E" is one byte encoding, currently set to HLL_DENSE or
90 * HLL_SPARSE. N/U are three not used bytes.
91 *
92 * The "Cardin." field is a 64 bit integer stored in little endian format
93 * with the latest cardinality computed that can be reused if the data
94 * structure was not modified since the last computation (this is useful
95 * because there are high probabilities that HLLADD operations don't
96 * modify the actual data structure and hence the approximated cardinality).
97 *
98 * When the most significant bit in the most significant byte of the cached
99 * cardinality is set, it means that the data structure was modified and
100 * we can't reuse the cached value that must be recomputed.
101 *
102 * Dense representation
103 * ===
104 *
105 * The dense representation used by Redis is the following:
106 *
107 * +--------+--------+--------+------// //--+
108 * |11000000|22221111|33333322|55444444 .... |
109 * +--------+--------+--------+------// //--+
110 *
111 * The 6 bits counters are encoded one after the other starting from the
112 * LSB to the MSB, and using the next bytes as needed.
113 *
114 * Sparse representation
115 * ===
116 *
117 * The sparse representation encodes registers using a run length
118 * encoding composed of three opcodes, two using one byte, and one using
119 * of two bytes. The opcodes are called ZERO, XZERO and VAL.
120 *
121 * ZERO opcode is represented as 00xxxxxx. The 6-bit integer represented
122 * by the six bits 'xxxxxx', plus 1, means that there are N registers set
123 * to 0. This opcode can represent from 1 to 64 contiguous registers set
124 * to the value of 0.
125 *
126 * XZERO opcode is represented by two bytes 01xxxxxx yyyyyyyy. The 14-bit
127 * integer represented by the bits 'xxxxxx' as most significant bits and
128 * 'yyyyyyyy' as least significant bits, plus 1, means that there are N
129 * registers set to 0. This opcode can represent from 0 to 16384 contiguous
130 * registers set to the value of 0.
131 *
132 * VAL opcode is represented as 1vvvvvxx. It contains a 5-bit integer
133 * representing the value of a register, and a 2-bit integer representing
134 * the number of contiguous registers set to that value 'vvvvv'.
135 * To obtain the value and run length, the integers vvvvv and xx must be
136 * incremented by one. This opcode can represent values from 1 to 32,
137 * repeated from 1 to 4 times.
138 *
139 * The sparse representation can't represent registers with a value greater
140 * than 32, however it is very unlikely that we find such a register in an
141 * HLL with a cardinality where the sparse representation is still more
142 * memory efficient than the dense representation. When this happens the
143 * HLL is converted to the dense representation.
144 *
145 * The sparse representation is purely positional. For example a sparse
146 * representation of an empty HLL is just: XZERO:16384.
147 *
148 * An HLL having only 3 non-zero registers at position 1000, 1020, 1021
149 * respectively set to 2, 3, 3, is represented by the following three
150 * opcodes:
151 *
152 * XZERO:1000 (Registers 0-999 are set to 0)
153 * VAL:2,1 (1 register set to value 2, that is register 1000)
154 * ZERO:19 (Registers 1001-1019 set to 0)
155 * VAL:3,2 (2 registers set to value 3, that is registers 1020,1021)
156 * XZERO:15362 (Registers 1022-16383 set to 0)
157 *
158 * In the example the sparse representation used just 7 bytes instead
159 * of 12k in order to represent the HLL registers. In general for low
160 * cardinality there is a big win in terms of space efficiency, traded
161 * with CPU time since the sparse representation is slower to access:
162 *
163 * The following table shows average cardinality vs bytes used, 100
164 * samples per cardinality (when the set was not representable because
165 * of registers with too big value, the dense representation size was used
166 * as a sample).
167 *
168 * 100 267
169 * 200 485
170 * 300 678
171 * 400 859
172 * 500 1033
173 * 600 1205
174 * 700 1375
175 * 800 1544
176 * 900 1713
177 * 1000 1882
178 * 2000 3480
179 * 3000 4879
180 * 4000 6089
181 * 5000 7138
182 * 6000 8042
183 * 7000 8823
184 * 8000 9500
185 * 9000 10088
186 * 10000 10591
187 *
188 * The dense representation uses 12288 bytes, so there is a big win up to
189 * a cardinality of ~2000-3000. For bigger cardinalities the constant times
190 * involved in updating the sparse representation is not justified by the
191 * memory savings. The exact maximum length of the sparse representation
192 * when this implementation switches to the dense representation is
193 * configured via the define server.hll_sparse_max_bytes.
194 */
195
196struct hllhdr {
197 char magic[4]; /* "HYLL" */
198 uint8_t encoding; /* HLL_DENSE or HLL_SPARSE. */
199 uint8_t notused[3]; /* Reserved for future use, must be zero. */
200 uint8_t card[8]; /* Cached cardinality, little endian. */
201 uint8_t registers[1]; /* Data bytes. */
202};
203
204/* The cached cardinality MSB is used to signal validity of the cached value. */
205#define HLL_INVALIDATE_CACHE(hdr) (hdr)->card[7] |= (1<<7)
206#define HLL_VALID_CACHE(hdr) (((hdr)->card[7] & (1<<7)) == 0)
207
208#define HLL_P 12 /* The greater is P, the smaller the error. */
209#define HLL_Q (64-HLL_P) /* The number of bits of the hash value used for
210 determining the number of leading zeros. */
211#define HLL_REGISTERS (1<<HLL_P) /* With P=14, 16384 registers. */
212#define HLL_P_MASK (HLL_REGISTERS-1) /* Mask to index register. */
213#define HLL_BITS 6 /* Enough to count up to 63 leading zeroes. */
214#define HLL_REGISTER_MAX ((1<<HLL_BITS)-1)
215#define HLL_HDR_SIZE sizeof(struct hllhdr)
216#define HLL_DENSE_SIZE (HLL_HDR_SIZE+((HLL_REGISTERS*HLL_BITS+7)/8))
217#define HLL_DENSE 0 /* Dense encoding. */
218#define HLL_SPARSE 1 /* Sparse encoding. */
219#define HLL_RAW 255 /* Only used internally, never exposed. */
220#define HLL_MAX_ENCODING 1
221
222/* =========================== Low level bit macros ========================= */
223
224/* Macros to access the dense representation.
225 *
226 * We need to get and set 6 bit counters in an array of 8 bit bytes.
227 * We use macros to make sure the code is inlined since speed is critical
228 * especially in order to compute the approximated cardinality in
229 * HLLCOUNT where we need to access all the registers at once.
230 * For the same reason we also want to avoid conditionals in this code path.
231 *
232 * +--------+--------+--------+------//
233 * |11000000|22221111|33333322|55444444
234 * +--------+--------+--------+------//
235 *
236 * Note: in the above representation the most significant bit (MSB)
237 * of every byte is on the left. We start using bits from the LSB to MSB,
238 * and so forth passing to the next byte.
239 *
240 * Example, we want to access to counter at pos = 1 ("111111" in the
241 * illustration above).
242 *
243 * The index of the first byte b0 containing our data is:
244 *
245 * b0 = 6 * pos / 8 = 0
246 *
247 * +--------+
248 * |11000000| <- Our byte at b0
249 * +--------+
250 *
251 * The position of the first bit (counting from the LSB = 0) in the byte
252 * is given by:
253 *
254 * fb = 6 * pos % 8 -> 6
255 *
256 * Right shift b0 of 'fb' bits.
257 *
258 * +--------+
259 * |11000000| <- Initial value of b0
260 * |00000011| <- After right shift of 6 pos.
261 * +--------+
262 *
263 * Left shift b1 of bits 8-fb bits (2 bits)
264 *
265 * +--------+
266 * |22221111| <- Initial value of b1
267 * |22111100| <- After left shift of 2 bits.
268 * +--------+
269 *
270 * OR the two bits, and finally AND with 111111 (63 in decimal) to
271 * clean the higher order bits we are not interested in:
272 *
273 * +--------+
274 * |00000011| <- b0 right shifted
275 * |22111100| <- b1 left shifted
276 * |22111111| <- b0 OR b1
277 * | 111111| <- (b0 OR b1) AND 63, our value.
278 * +--------+
279 *
280 * We can try with a different example, like pos = 0. In this case
281 * the 6-bit counter is actually contained in a single byte.
282 *
283 * b0 = 6 * pos / 8 = 0
284 *
285 * +--------+
286 * |11000000| <- Our byte at b0
287 * +--------+
288 *
289 * fb = 6 * pos % 8 = 0
290 *
291 * So we right shift of 0 bits (no shift in practice) and
292 * left shift the next byte of 8 bits, even if we don't use it,
293 * but this has the effect of clearing the bits so the result
294 * will not be affacted after the OR.
295 *
296 * -------------------------------------------------------------------------
297 *
298 * Setting the register is a bit more complex, let's assume that 'val'
299 * is the value we want to set, already in the right range.
300 *
301 * We need two steps, in one we need to clear the bits, and in the other
302 * we need to bitwise-OR the new bits.
303 *
304 * Let's try with 'pos' = 1, so our first byte at 'b' is 0,
305 *
306 * "fb" is 6 in this case.
307 *
308 * +--------+
309 * |11000000| <- Our byte at b0
310 * +--------+
311 *
312 * To create a AND-mask to clear the bits about this position, we just
313 * initialize the mask with the value 63, left shift it of "fs" bits,
314 * and finally invert the result.
315 *
316 * +--------+
317 * |00111111| <- "mask" starts at 63
318 * |11000000| <- "mask" after left shift of "ls" bits.
319 * |00111111| <- "mask" after invert.
320 * +--------+
321 *
322 * Now we can bitwise-AND the byte at "b" with the mask, and bitwise-OR
323 * it with "val" left-shifted of "ls" bits to set the new bits.
324 *
325 * Now let's focus on the next byte b1:
326 *
327 * +--------+
328 * |22221111| <- Initial value of b1
329 * +--------+
330 *
331 * To build the AND mask we start again with the 63 value, right shift
332 * it by 8-fb bits, and invert it.
333 *
334 * +--------+
335 * |00111111| <- "mask" set at 2&6-1
336 * |00001111| <- "mask" after the right shift by 8-fb = 2 bits
337 * |11110000| <- "mask" after bitwise not.
338 * +--------+
339 *
340 * Now we can mask it with b+1 to clear the old bits, and bitwise-OR
341 * with "val" left-shifted by "rs" bits to set the new value.
342 */
343
344/* Note: if we access the last counter, we will also access the b+1 byte
345 * that is out of the array, but sds strings always have an implicit null
346 * term, so the byte exists, and we can skip the conditional (or the need
347 * to allocate 1 byte more explicitly). */
348
349/* Store the value of the register at position 'regnum' into variable 'target'.
350 * 'p' is an array of unsigned bytes. */
351#define HLL_DENSE_GET_REGISTER(target,p,regnum) do { \
352 uint8_t *_p = (uint8_t*) p; \
353 unsigned long _byte = regnum*HLL_BITS/8; \
354 unsigned long _fb = regnum*HLL_BITS&7; \
355 unsigned long _fb8 = 8 - _fb; \
356 unsigned long b0 = _p[_byte]; \
357 unsigned long b1 = _p[_byte+1]; \
358 target = ((b0 >> _fb) | (b1 << _fb8)) & HLL_REGISTER_MAX; \
359} while(0)
360
361/* Set the value of the register at position 'regnum' to 'val'.
362 * 'p' is an array of unsigned bytes. */
363#define HLL_DENSE_SET_REGISTER(p,regnum,val) do { \
364 uint8_t *_p = (uint8_t*) p; \
365 unsigned long _byte = regnum*HLL_BITS/8; \
366 unsigned long _fb = regnum*HLL_BITS&7; \
367 unsigned long _fb8 = 8 - _fb; \
368 unsigned long _v = val; \
369 _p[_byte] &= ~(HLL_REGISTER_MAX << _fb); \
370 _p[_byte] |= _v << _fb; \
371 _p[_byte+1] &= ~(HLL_REGISTER_MAX >> _fb8); \
372 _p[_byte+1] |= _v >> _fb8; \
373} while(0)
374
375/* Macros to access the sparse representation.
376 * The macros parameter is expected to be an uint8_t pointer. */
377#define HLL_SPARSE_XZERO_BIT 0x40 /* 01xxxxxx */
378#define HLL_SPARSE_VAL_BIT 0x80 /* 1vvvvvxx */
379#define HLL_SPARSE_IS_ZERO(p) (((*(p)) & 0xc0) == 0) /* 00xxxxxx */
380#define HLL_SPARSE_IS_XZERO(p) (((*(p)) & 0xc0) == HLL_SPARSE_XZERO_BIT)
381#define HLL_SPARSE_IS_VAL(p) ((*(p)) & HLL_SPARSE_VAL_BIT)
382#define HLL_SPARSE_ZERO_LEN(p) (((*(p)) & 0x3f)+1)
383#define HLL_SPARSE_XZERO_LEN(p) (((((*(p)) & 0x3f) << 8) | (*((p)+1)))+1)
384#define HLL_SPARSE_VAL_VALUE(p) ((((*(p)) >> 2) & 0x1f)+1)
385#define HLL_SPARSE_VAL_LEN(p) (((*(p)) & 0x3)+1)
386#define HLL_SPARSE_VAL_MAX_VALUE 32
387#define HLL_SPARSE_VAL_MAX_LEN 4
388#define HLL_SPARSE_ZERO_MAX_LEN 64
389#define HLL_SPARSE_XZERO_MAX_LEN 16384
390#define HLL_SPARSE_VAL_SET(p,val,len) do { \
391 *(p) = (((val)-1)<<2|((len)-1))|HLL_SPARSE_VAL_BIT; \
392} while(0)
393#define HLL_SPARSE_ZERO_SET(p,len) do { \
394 *(p) = (len)-1; \
395} while(0)
396#define HLL_SPARSE_XZERO_SET(p,len) do { \
397 int _l = (len)-1; \
398 *(p) = (_l>>8) | HLL_SPARSE_XZERO_BIT; \
399 *((p)+1) = (_l&0xff); \
400} while(0)
401#define HLL_ALPHA_INF 0.721347520444481703680 /* constant for 0.5/ln(2) */
402
403/* ========================= HyperLogLog algorithm ========================= */
404
405/* Our hash function is MurmurHash2, 64 bit version.
406 * It was modified for Redis in order to provide the same result in
407 * big and little endian archs (endian neutral). */
408uint64_t MurmurHash64A (const void * key, int len, unsigned int seed) {
409 const uint64_t m = 0xc6a4a7935bd1e995;
410 const int r = 47;
411 uint64_t h = seed ^ (len * m);
412 const uint8_t *data = (const uint8_t *)key;
413 const uint8_t *end = data + (len-(len&7));
414
415 while(data != end) {
416 uint64_t k;
417
418#if (BYTE_ORDER == LITTLE_ENDIAN)
419 #ifdef USE_ALIGNED_ACCESS
420 memcpy(&k,data,sizeof(uint64_t));
421 #else
422 k = *((uint64_t*)data);
423 #endif
424#else
425 k = (uint64_t) data[0];
426 k |= (uint64_t) data[1] << 8;
427 k |= (uint64_t) data[2] << 16;
428 k |= (uint64_t) data[3] << 24;
429 k |= (uint64_t) data[4] << 32;
430 k |= (uint64_t) data[5] << 40;
431 k |= (uint64_t) data[6] << 48;
432 k |= (uint64_t) data[7] << 56;
433#endif
434
435 k *= m;
436 k ^= k >> r;
437 k *= m;
438 h ^= k;
439 h *= m;
440 data += 8;
441 }
442
443 switch(len & 7) {
444 case 7: h ^= (uint64_t)data[6] << 48; /* fall-thru */
445 case 6: h ^= (uint64_t)data[5] << 40; /* fall-thru */
446 case 5: h ^= (uint64_t)data[4] << 32; /* fall-thru */
447 case 4: h ^= (uint64_t)data[3] << 24; /* fall-thru */
448 case 3: h ^= (uint64_t)data[2] << 16; /* fall-thru */
449 case 2: h ^= (uint64_t)data[1] << 8; /* fall-thru */
450 case 1: h ^= (uint64_t)data[0];
451 h *= m; /* fall-thru */
452 };
453
454 h ^= h >> r;
455 h *= m;
456 h ^= h >> r;
457 return h;
458}
459
460/* Given a string element to add to the HyperLogLog, returns the length
461 * of the pattern 000..1 of the element hash. As a side effect 'regp' is
462 * set to the register index this element hashes to. */
463int hllPatLen(unsigned char *ele, size_t elesize, long *regp) {
464 uint64_t hash, bit, index;
465 int count;
466
467 /* Count the number of zeroes starting from bit HLL_REGISTERS
468 * (that is a power of two corresponding to the first bit we don't use
469 * as index). The max run can be 64-P+1 = Q+1 bits.
470 *
471 * Note that the final "1" ending the sequence of zeroes must be
472 * included in the count, so if we find "001" the count is 3, and
473 * the smallest count possible is no zeroes at all, just a 1 bit
474 * at the first position, that is a count of 1.
475 *
476 * This may sound like inefficient, but actually in the average case
477 * there are high probabilities to find a 1 after a few iterations. */
478 hash = MurmurHash64A(key: ele,len: elesize,seed: 0xadc83b19ULL);
479 index = hash & HLL_P_MASK; /* Register index. */
480 hash >>= HLL_P; /* Remove bits used to address the register. */
481 hash |= ((uint64_t)1<<HLL_Q); /* Make sure the loop terminates
482 and count will be <= Q+1. */
483 bit = 1;
484 count = 1; /* Initialized to 1 since we count the "00000...1" pattern. */
485 while((hash & bit) == 0) {
486 count++;
487 bit <<= 1;
488 }
489 *regp = (int) index;
490 return count;
491}
492
493/* ================== Dense representation implementation ================== */
494
495/* Low level function to set the dense HLL register at 'index' to the
496 * specified value if the current value is smaller than 'count'.
497 *
498 * 'registers' is expected to have room for HLL_REGISTERS plus an
499 * additional byte on the right. This requirement is met by sds strings
500 * automatically since they are implicitly null terminated.
501 *
502 * The function always succeed, however if as a result of the operation
503 * the approximated cardinality changed, 1 is returned. Otherwise 0
504 * is returned. */
505static inline int hllDenseSet(uint8_t *registers, long index, uint8_t count) {
506 uint8_t oldcount;
507
508 HLL_DENSE_GET_REGISTER(oldcount,registers,index);
509 if (count > oldcount) {
510 HLL_DENSE_SET_REGISTER(registers,index,count);
511 return 1;
512 } else {
513 return 0;
514 }
515}
516
517/* "Add" the element in the dense hyperloglog data structure.
518 * Actually nothing is added, but the max 0 pattern counter of the subset
519 * the element belongs to is incremented if needed.
520 *
521 * This is just a wrapper to hllDenseSet(), performing the hashing of the
522 * element in order to retrieve the index and zero-run count. */
523int hllDenseAdd(uint8_t *registers, unsigned char *ele, size_t elesize) {
524 long index;
525 uint8_t count = hllPatLen(ele,elesize,regp: &index);
526 /* Update the register if this element produced a longer run of zeroes. */
527 return hllDenseSet(registers,index,count);
528}
529
530/* Compute the register histogram in the dense representation. */
531void hllDenseRegHisto(uint8_t *registers, int* reghisto) {
532 int j;
533
534 /* Redis default is to use 16384 registers 6 bits each. The code works
535 * with other values by modifying the defines, but for our target value
536 * we take a faster path with unrolled loops. */
537 if (HLL_REGISTERS == 16384 && HLL_BITS == 6) {
538 uint8_t *r = registers;
539 unsigned long r0, r1, r2, r3, r4, r5, r6, r7, r8, r9,
540 r10, r11, r12, r13, r14, r15;
541 for (j = 0; j < 1024; j++) {
542 /* Handle 16 registers per iteration. */
543 r0 = r[0] & 63;
544 r1 = (r[0] >> 6 | r[1] << 2) & 63;
545 r2 = (r[1] >> 4 | r[2] << 4) & 63;
546 r3 = (r[2] >> 2) & 63;
547 r4 = r[3] & 63;
548 r5 = (r[3] >> 6 | r[4] << 2) & 63;
549 r6 = (r[4] >> 4 | r[5] << 4) & 63;
550 r7 = (r[5] >> 2) & 63;
551 r8 = r[6] & 63;
552 r9 = (r[6] >> 6 | r[7] << 2) & 63;
553 r10 = (r[7] >> 4 | r[8] << 4) & 63;
554 r11 = (r[8] >> 2) & 63;
555 r12 = r[9] & 63;
556 r13 = (r[9] >> 6 | r[10] << 2) & 63;
557 r14 = (r[10] >> 4 | r[11] << 4) & 63;
558 r15 = (r[11] >> 2) & 63;
559
560 reghisto[r0]++;
561 reghisto[r1]++;
562 reghisto[r2]++;
563 reghisto[r3]++;
564 reghisto[r4]++;
565 reghisto[r5]++;
566 reghisto[r6]++;
567 reghisto[r7]++;
568 reghisto[r8]++;
569 reghisto[r9]++;
570 reghisto[r10]++;
571 reghisto[r11]++;
572 reghisto[r12]++;
573 reghisto[r13]++;
574 reghisto[r14]++;
575 reghisto[r15]++;
576
577 r += 12;
578 }
579 } else {
580 for(j = 0; j < HLL_REGISTERS; j++) {
581 unsigned long reg;
582 HLL_DENSE_GET_REGISTER(reg,registers,j);
583 reghisto[reg]++;
584 }
585 }
586}
587
588/* ================== Sparse representation implementation ================= */
589
590/* Convert the HLL with sparse representation given as input in its dense
591 * representation. Both representations are represented by SDS strings, and
592 * the input representation is freed as a side effect.
593 *
594 * The function returns C_OK if the sparse representation was valid,
595 * otherwise C_ERR is returned if the representation was corrupted. */
596int hllSparseToDense(robj *o) {
597 sds sparse = (sds) o->ptr, dense;
598 struct hllhdr *hdr, *oldhdr = (struct hllhdr*)sparse;
599 int idx = 0, runlen, regval;
600 uint8_t *p = (uint8_t*)sparse, *end = p+sdslen(s: sparse);
601
602 /* If the representation is already the right one return ASAP. */
603 hdr = (struct hllhdr*) sparse;
604 if (hdr->encoding == HLL_DENSE) return HLL_C_OK;
605
606 /* Create a string of the right size filled with zero bytes.
607 * Note that the cached cardinality is set to 0 as a side effect
608 * that is exactly the cardinality of an empty HLL. */
609 dense = sdsnewlen(NULL,HLL_DENSE_SIZE);
610 hdr = (struct hllhdr*) dense;
611 *hdr = *oldhdr; /* This will copy the magic and cached cardinality. */
612 hdr->encoding = HLL_DENSE;
613
614 /* Now read the sparse representation and set non-zero registers
615 * accordingly. */
616 p += HLL_HDR_SIZE;
617 while(p < end) {
618 if (HLL_SPARSE_IS_ZERO(p)) {
619 runlen = HLL_SPARSE_ZERO_LEN(p);
620 idx += runlen;
621 p++;
622 } else if (HLL_SPARSE_IS_XZERO(p)) {
623 runlen = HLL_SPARSE_XZERO_LEN(p);
624 idx += runlen;
625 p += 2;
626 } else {
627 runlen = HLL_SPARSE_VAL_LEN(p);
628 regval = HLL_SPARSE_VAL_VALUE(p);
629 while(runlen--) {
630 HLL_DENSE_SET_REGISTER(hdr->registers + 1,idx,regval);
631 idx++;
632 }
633 p++;
634 }
635 }
636
637 /* If the sparse representation was valid, we expect to find idx
638 * set to HLL_REGISTERS. */
639 if (idx != HLL_REGISTERS) {
640 sdsfree(s: dense);
641 return HLL_C_ERR;
642 }
643
644 /* Free the old representation and set the new one. */
645 sdsfree(s: (sds) o->ptr);
646 o->ptr = dense;
647 return HLL_C_OK;
648}
649
650/* Low level function to set the sparse HLL register at 'index' to the
651 * specified value if the current value is smaller than 'count'.
652 *
653 * The object 'o' is the String object holding the HLL. The function requires
654 * a reference to the object in order to be able to enlarge the string if
655 * needed.
656 *
657 * On success, the function returns 1 if the cardinality changed, or 0
658 * if the register for this element was not updated.
659 * On error (if the representation is invalid) -1 is returned.
660 *
661 * As a side effect the function may promote the HLL representation from
662 * sparse to dense: this happens when a register requires to be set to a value
663 * not representable with the sparse representation, or when the resulting
664 * size would be greater than server.hll_sparse_max_bytes. */
665int hllSparseSet(robj *o, long index, uint8_t count) {
666 struct hllhdr *hdr;
667 uint8_t oldcount, *sparse, *end, *p, *prev, *next;
668 long first, span;
669 long is_zero = 0, is_xzero = 0, is_val = 0, runlen = 0;
670 uint8_t seq[5], *n;
671 int last;
672 int len;
673 int seqlen;
674 int oldlen;
675 int deltalen;
676
677 /* If the count is too big to be representable by the sparse representation
678 * switch to dense representation. */
679 if (count > HLL_SPARSE_VAL_MAX_VALUE) goto promote;
680
681 /* When updating a sparse representation, sometimes we may need to
682 * enlarge the buffer for up to 3 bytes in the worst case (XZERO split
683 * into XZERO-VAL-XZERO). Make sure there is enough space right now
684 * so that the pointers we take during the execution of the function
685 * will be valid all the time. */
686 o->ptr = (sds) sdsMakeRoomFor(s: (sds) o->ptr,addlen: 3);
687
688 /* Step 1: we need to locate the opcode we need to modify to check
689 * if a value update is actually needed. */
690 sparse = p = ((uint8_t*)o->ptr) + HLL_HDR_SIZE;
691 end = p + sdslen(s: (sds) o->ptr) - HLL_HDR_SIZE;
692
693 first = 0;
694 prev = NULL; /* Points to previous opcode at the end of the loop. */
695 next = NULL; /* Points to the next opcode at the end of the loop. */
696 span = 0;
697 while(p < end) {
698 long oplen;
699
700 /* Set span to the number of registers covered by this opcode.
701 *
702 * This is the most performance critical loop of the sparse
703 * representation. Sorting the conditionals from the most to the
704 * least frequent opcode in many-bytes sparse HLLs is faster. */
705 oplen = 1;
706 if (HLL_SPARSE_IS_ZERO(p)) {
707 span = HLL_SPARSE_ZERO_LEN(p);
708 } else if (HLL_SPARSE_IS_VAL(p)) {
709 span = HLL_SPARSE_VAL_LEN(p);
710 } else { /* XZERO. */
711 span = HLL_SPARSE_XZERO_LEN(p);
712 oplen = 2;
713 }
714 /* Break if this opcode covers the register as 'index'. */
715 if (index <= first+span-1) break;
716 prev = p;
717 p += oplen;
718 first += span;
719 }
720 if (span == 0) return -1; /* Invalid format. */
721
722 next = HLL_SPARSE_IS_XZERO(p) ? p+2 : p+1;
723 if (next >= end) next = NULL;
724
725 /* Cache current opcode type to avoid using the macro again and
726 * again for something that will not change.
727 * Also cache the run-length of the opcode. */
728 if (HLL_SPARSE_IS_ZERO(p)) {
729 is_zero = 1;
730 runlen = HLL_SPARSE_ZERO_LEN(p);
731 } else if (HLL_SPARSE_IS_XZERO(p)) {
732 is_xzero = 1;
733 runlen = HLL_SPARSE_XZERO_LEN(p);
734 } else {
735 is_val = 1;
736 runlen = HLL_SPARSE_VAL_LEN(p);
737 }
738
739 /* Step 2: After the loop:
740 *
741 * 'first' stores to the index of the first register covered
742 * by the current opcode, which is pointed by 'p'.
743 *
744 * 'next' ad 'prev' store respectively the next and previous opcode,
745 * or NULL if the opcode at 'p' is respectively the last or first.
746 *
747 * 'span' is set to the number of registers covered by the current
748 * opcode.
749 *
750 * There are different cases in order to update the data structure
751 * in place without generating it from scratch:
752 *
753 * A) If it is a VAL opcode already set to a value >= our 'count'
754 * no update is needed, regardless of the VAL run-length field.
755 * In this case PFADD returns 0 since no changes are performed.
756 *
757 * B) If it is a VAL opcode with len = 1 (representing only our
758 * register) and the value is less than 'count', we just update it
759 * since this is a trivial case. */
760 if (is_val) {
761 oldcount = HLL_SPARSE_VAL_VALUE(p);
762 /* Case A. */
763 if (oldcount >= count) return 0;
764
765 /* Case B. */
766 if (runlen == 1) {
767 HLL_SPARSE_VAL_SET(p,count,1);
768 goto updated;
769 }
770 }
771
772 /* C) Another trivial to handle case is a ZERO opcode with a len of 1.
773 * We can just replace it with a VAL opcode with our value and len of 1. */
774 if (is_zero && runlen == 1) {
775 HLL_SPARSE_VAL_SET(p,count,1);
776 goto updated;
777 }
778
779 /* D) General case.
780 *
781 * The other cases are more complex: our register requires to be updated
782 * and is either currently represented by a VAL opcode with len > 1,
783 * by a ZERO opcode with len > 1, or by an XZERO opcode.
784 *
785 * In those cases the original opcode must be split into multiple
786 * opcodes. The worst case is an XZERO split in the middle resuling into
787 * XZERO - VAL - XZERO, so the resulting sequence max length is
788 * 5 bytes.
789 *
790 * We perform the split writing the new sequence into the 'new' buffer
791 * with 'newlen' as length. Later the new sequence is inserted in place
792 * of the old one, possibly moving what is on the right a few bytes
793 * if the new sequence is longer than the older one. */
794 n = seq;
795 last = first+span-1; /* Last register covered by the sequence. */
796
797 if (is_zero || is_xzero) {
798 /* Handle splitting of ZERO / XZERO. */
799 if (index != first) {
800 len = index-first;
801 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
802 HLL_SPARSE_XZERO_SET(n,len);
803 n += 2;
804 } else {
805 HLL_SPARSE_ZERO_SET(n,len);
806 n++;
807 }
808 }
809 HLL_SPARSE_VAL_SET(n,count,1);
810 n++;
811 if (index != last) {
812 len = last-index;
813 if (len > HLL_SPARSE_ZERO_MAX_LEN) {
814 HLL_SPARSE_XZERO_SET(n,len);
815 n += 2;
816 } else {
817 HLL_SPARSE_ZERO_SET(n,len);
818 n++;
819 }
820 }
821 } else {
822 /* Handle splitting of VAL. */
823 int curval = HLL_SPARSE_VAL_VALUE(p);
824
825 if (index != first) {
826 len = index-first;
827 HLL_SPARSE_VAL_SET(n,curval,len);
828 n++;
829 }
830 HLL_SPARSE_VAL_SET(n,count,1);
831 n++;
832 if (index != last) {
833 len = last-index;
834 HLL_SPARSE_VAL_SET(n,curval,len);
835 n++;
836 }
837 }
838
839 /* Step 3: substitute the new sequence with the old one.
840 *
841 * Note that we already allocated space on the sds string
842 * calling sdsMakeRoomFor(). */
843 seqlen = n-seq;
844 oldlen = is_xzero ? 2 : 1;
845 deltalen = seqlen-oldlen;
846
847 if (deltalen > 0 &&
848 sdslen(s: (sds) o->ptr)+deltalen > HLL_SPARSE_MAX_BYTES) goto promote;
849 if (deltalen && next) memmove(dest: next+deltalen,src: next,n: end-next);
850 sdsIncrLen(s: (sds) o->ptr,incr: deltalen);
851 memcpy(dest: p,src: seq,n: seqlen);
852 end += deltalen;
853
854updated: {
855 /* Step 4: Merge adjacent values if possible.
856 *
857 * The representation was updated, however the resulting representation
858 * may not be optimal: adjacent VAL opcodes can sometimes be merged into
859 * a single one. */
860 p = prev ? prev : sparse;
861 int scanlen = 5; /* Scan up to 5 upcodes starting from prev. */
862 while (p < end && scanlen--) {
863 if (HLL_SPARSE_IS_XZERO(p)) {
864 p += 2;
865 continue;
866 } else if (HLL_SPARSE_IS_ZERO(p)) {
867 p++;
868 continue;
869 }
870 /* We need two adjacent VAL opcodes to try a merge, having
871 * the same value, and a len that fits the VAL opcode max len. */
872 if (p+1 < end && HLL_SPARSE_IS_VAL(p+1)) {
873 int v1 = HLL_SPARSE_VAL_VALUE(p);
874 int v2 = HLL_SPARSE_VAL_VALUE(p+1);
875 if (v1 == v2) {
876 int len = HLL_SPARSE_VAL_LEN(p)+HLL_SPARSE_VAL_LEN(p+1);
877 if (len <= HLL_SPARSE_VAL_MAX_LEN) {
878 HLL_SPARSE_VAL_SET(p+1,v1,len);
879 memmove(dest: p,src: p+1,n: end-p);
880 sdsIncrLen(s: (sds) o->ptr,incr: -1);
881 end--;
882 /* After a merge we reiterate without incrementing 'p'
883 * in order to try to merge the just merged value with
884 * a value on its right. */
885 continue;
886 }
887 }
888 }
889 p++;
890 }
891
892 /* Invalidate the cached cardinality. */
893 hdr = (struct hllhdr *) o->ptr;
894 HLL_INVALIDATE_CACHE(hdr);
895 return 1;
896}
897promote: /* Promote to dense representation. */
898 if (hllSparseToDense(o) == HLL_C_ERR) return -1; /* Corrupted HLL. */
899 hdr = (struct hllhdr *) o->ptr;
900
901 /* We need to call hllDenseAdd() to perform the operation after the
902 * conversion. However the result must be 1, since if we need to
903 * convert from sparse to dense a register requires to be updated.
904 *
905 * Note that this in turn means that PFADD will make sure the command
906 * is propagated to slaves / AOF, so if there is a sparse -> dense
907 * conversion, it will be performed in all the slaves as well. */
908 int dense_retval = hllDenseSet(registers: hdr->registers + 1,index,count);
909 assert(dense_retval == 1);
910 return dense_retval;
911}
912
913/* "Add" the element in the sparse hyperloglog data structure.
914 * Actually nothing is added, but the max 0 pattern counter of the subset
915 * the element belongs to is incremented if needed.
916 *
917 * This function is actually a wrapper for hllSparseSet(), it only performs
918 * the hashshing of the elmenet to obtain the index and zeros run length. */
919int hllSparseAdd(robj *o, unsigned char *ele, size_t elesize) {
920 long index;
921 uint8_t count = hllPatLen(ele,elesize,regp: &index);
922 /* Update the register if this element produced a longer run of zeroes. */
923 return hllSparseSet(o,index,count);
924}
925
926/* Compute the register histogram in the sparse representation. */
927void hllSparseRegHisto(uint8_t *sparse, int sparselen, int *invalid, int* reghisto) {
928 int idx = 0, runlen, regval;
929 uint8_t *end = sparse+sparselen, *p = sparse;
930
931 while(p < end) {
932 if (HLL_SPARSE_IS_ZERO(p)) {
933 runlen = HLL_SPARSE_ZERO_LEN(p);
934 idx += runlen;
935 reghisto[0] += runlen;
936 p++;
937 } else if (HLL_SPARSE_IS_XZERO(p)) {
938 runlen = HLL_SPARSE_XZERO_LEN(p);
939 idx += runlen;
940 reghisto[0] += runlen;
941 p += 2;
942 } else {
943 runlen = HLL_SPARSE_VAL_LEN(p);
944 regval = HLL_SPARSE_VAL_VALUE(p);
945 idx += runlen;
946 reghisto[regval] += runlen;
947 p++;
948 }
949 }
950 if (idx != HLL_REGISTERS && invalid) *invalid = 1;
951}
952
953/* ========================= HyperLogLog Count ==============================
954 * This is the core of the algorithm where the approximated count is computed.
955 * The function uses the lower level hllDenseRegHisto() and hllSparseRegHisto()
956 * functions as helpers to compute histogram of register values part of the
957 * computation, which is representation-specific, while all the rest is common. */
958
959/* Implements the register histogram calculation for uint8_t data type
960 * which is only used internally as speedup for PFCOUNT with multiple keys. */
961void hllRawRegHisto(uint8_t *registers, int* reghisto) {
962 uint64_t *word = (uint64_t*) registers;
963 uint8_t *bytes;
964 int j;
965
966 for (j = 0; j < HLL_REGISTERS/8; j++) {
967 if (*word == 0) {
968 reghisto[0] += 8;
969 } else {
970 bytes = (uint8_t*) word;
971 reghisto[bytes[0]]++;
972 reghisto[bytes[1]]++;
973 reghisto[bytes[2]]++;
974 reghisto[bytes[3]]++;
975 reghisto[bytes[4]]++;
976 reghisto[bytes[5]]++;
977 reghisto[bytes[6]]++;
978 reghisto[bytes[7]]++;
979 }
980 word++;
981 }
982}
983
984// somehow this is missing on some platforms
985#ifndef INFINITY
986// from math.h
987#define INFINITY 1e50f
988#endif
989
990
991/* Helper function sigma as defined in
992 * "New cardinality estimation algorithms for HyperLogLog sketches"
993 * Otmar Ertl, arXiv:1702.01284 */
994double hllSigma(double x) {
995 if (x == 1.) return INFINITY;
996 double zPrime;
997 double y = 1;
998 double z = x;
999 do {
1000 x *= x;
1001 zPrime = z;
1002 z += x * y;
1003 y += y;
1004 } while(zPrime != z);
1005 return z;
1006}
1007
1008/* Helper function tau as defined in
1009 * "New cardinality estimation algorithms for HyperLogLog sketches"
1010 * Otmar Ertl, arXiv:1702.01284 */
1011double hllTau(double x) {
1012 if (x == 0. || x == 1.) return 0.;
1013 double zPrime;
1014 double y = 1.0;
1015 double z = 1 - x;
1016 do {
1017 x = sqrt(x: x);
1018 zPrime = z;
1019 y *= 0.5;
1020 z -= pow(x: 1 - x, y: 2)*y;
1021 } while(zPrime != z);
1022 return z / 3;
1023}
1024
1025/* Return the approximated cardinality of the set based on the harmonic
1026 * mean of the registers values. 'hdr' points to the start of the SDS
1027 * representing the String object holding the HLL representation.
1028 *
1029 * If the sparse representation of the HLL object is not valid, the integer
1030 * pointed by 'invalid' is set to non-zero, otherwise it is left untouched.
1031 *
1032 * hllCount() supports a special internal-only encoding of HLL_RAW, that
1033 * is, hdr->registers will point to an uint8_t array of HLL_REGISTERS element.
1034 * This is useful in order to speedup PFCOUNT when called against multiple
1035 * keys (no need to work with 6-bit integers encoding). */
1036uint64_t hllCount(struct hllhdr *hdr, int *invalid) {
1037 double m = HLL_REGISTERS;
1038 double E;
1039 int j;
1040 int reghisto[HLL_Q+2] = {0};
1041
1042 /* Compute register histogram */
1043 if (hdr->encoding == HLL_DENSE) {
1044 hllDenseRegHisto(registers: hdr->registers + 1,reghisto);
1045 } else if (hdr->encoding == HLL_SPARSE) {
1046 hllSparseRegHisto(sparse: hdr->registers + 1,
1047 sparselen: sdslen(s: (sds)hdr)-HLL_HDR_SIZE,invalid,reghisto);
1048 } else if (hdr->encoding == HLL_RAW) {
1049 hllRawRegHisto(registers: hdr->registers + 1,reghisto);
1050 } else {
1051 *invalid = 1;
1052 return 0;
1053 //serverPanic("Unknown HyperLogLog encoding in hllCount()");
1054 }
1055
1056 /* Estimate cardinality form register histogram. See:
1057 * "New cardinality estimation algorithms for HyperLogLog sketches"
1058 * Otmar Ertl, arXiv:1702.01284 */
1059 double z = m * hllTau(x: (m-reghisto[HLL_Q+1])/(double)m);
1060 for (j = HLL_Q; j >= 1; --j) {
1061 z += reghisto[j];
1062 z *= 0.5;
1063 }
1064 z += m * hllSigma(x: reghisto[0]/(double)m);
1065 E = llroundl(HLL_ALPHA_INF*m*m/z);
1066
1067 return (uint64_t) E;
1068}
1069
1070/* Call hllDenseAdd() or hllSparseAdd() according to the HLL encoding. */
1071int hll_add(robj *o, unsigned char *ele, size_t elesize) {
1072 struct hllhdr *hdr = (struct hllhdr *) o->ptr;
1073 switch(hdr->encoding) {
1074 case HLL_DENSE: return hllDenseAdd(registers: hdr->registers + 1,ele,elesize);
1075 case HLL_SPARSE: return hllSparseAdd(o,ele,elesize);
1076 default: return -1; /* Invalid representation. */
1077 }
1078}
1079
1080/* Merge by computing MAX(registers[i],hll[i]) the HyperLogLog 'hll'
1081 * with an array of uint8_t HLL_REGISTERS registers pointed by 'max'.
1082 *
1083 * The hll object must be already validated via isHLLObjectOrReply()
1084 * or in some other way.
1085 *
1086 * If the HyperLogLog is sparse and is found to be invalid, C_ERR
1087 * is returned, otherwise the function always succeeds. */
1088int hllMerge(uint8_t *max, robj *hll) {
1089 struct hllhdr *hdr = (struct hllhdr *) hll->ptr;
1090 int i;
1091
1092 if (hdr->encoding == HLL_DENSE) {
1093 uint8_t val;
1094
1095 for (i = 0; i < HLL_REGISTERS; i++) {
1096 HLL_DENSE_GET_REGISTER(val,hdr->registers + 1,i);
1097 if (val > max[i]) max[i] = val;
1098 }
1099 } else {
1100 uint8_t *p = (uint8_t *) hll->ptr, *end = p + sdslen(s: (sds) hll->ptr);
1101 long runlen, regval;
1102
1103 p += HLL_HDR_SIZE;
1104 i = 0;
1105 while(p < end) {
1106 if (HLL_SPARSE_IS_ZERO(p)) {
1107 runlen = HLL_SPARSE_ZERO_LEN(p);
1108 i += runlen;
1109 p++;
1110 } else if (HLL_SPARSE_IS_XZERO(p)) {
1111 runlen = HLL_SPARSE_XZERO_LEN(p);
1112 i += runlen;
1113 p += 2;
1114 } else {
1115 runlen = HLL_SPARSE_VAL_LEN(p);
1116 regval = HLL_SPARSE_VAL_VALUE(p);
1117 while(runlen--) {
1118 if (regval > max[i]) max[i] = regval;
1119 i++;
1120 }
1121 p++;
1122 }
1123 }
1124 if (i != HLL_REGISTERS) return HLL_C_ERR;
1125 }
1126 return HLL_C_OK;
1127}
1128
1129/* ========================== robj creation ========================== */
1130robj *createObject(void *ptr) {
1131 robj *result = (robj*) malloc(size: sizeof(robj));
1132 result->ptr = ptr;
1133 return result;
1134}
1135
1136void destroyObject(robj *obj) {
1137 free(ptr: obj);
1138}
1139
1140/* ========================== HyperLogLog commands ========================== */
1141
1142/* Create an HLL object. We always create the HLL using sparse encoding.
1143 * This will be upgraded to the dense representation as needed. */
1144robj *hll_create(void) {
1145 robj *o;
1146 struct hllhdr *hdr;
1147 sds s;
1148 uint8_t *p;
1149 int sparselen = HLL_HDR_SIZE +
1150 (((HLL_REGISTERS+(HLL_SPARSE_XZERO_MAX_LEN-1)) /
1151 HLL_SPARSE_XZERO_MAX_LEN)*2);
1152 int aux;
1153
1154 /* Populate the sparse representation with as many XZERO opcodes as
1155 * needed to represent all the registers. */
1156 aux = HLL_REGISTERS;
1157 s = sdsnewlen(NULL,initlen: sparselen);
1158 p = (uint8_t*)s + HLL_HDR_SIZE;
1159 while(aux) {
1160 int xzero = HLL_SPARSE_XZERO_MAX_LEN;
1161 if (xzero > aux) xzero = aux;
1162 HLL_SPARSE_XZERO_SET(p,xzero);
1163 p += 2;
1164 aux -= xzero;
1165 }
1166 assert((p-(uint8_t*)s) == sparselen);
1167
1168 /* Create the actual object. */
1169 o = createObject(ptr: s);
1170 hdr = (struct hllhdr *) o->ptr;
1171 memcpy(dest: hdr->magic,src: "HYLL",n: 4);
1172 hdr->encoding = HLL_SPARSE;
1173 return o;
1174}
1175
1176void hll_destroy(robj *obj) {
1177 if (!obj) {
1178 return;
1179 }
1180 sdsfree(s: (sds) obj->ptr);
1181 destroyObject(obj);
1182}
1183
1184
1185
1186int hll_count(robj *o, size_t *result) {
1187 int invalid = 0;
1188 *result = hllCount(hdr: (struct hllhdr*) o->ptr, invalid: &invalid);
1189 return invalid == 0 ? HLL_C_OK : HLL_C_ERR;
1190}
1191
1192robj *hll_merge(robj **hlls, size_t hll_count) {
1193 uint8_t max[HLL_REGISTERS];
1194 struct hllhdr *hdr;
1195 size_t j;
1196 /* Use dense representation as target? */
1197 int use_dense = 0;
1198
1199 /* Compute an HLL with M[i] = MAX(M[i]_j).
1200 * We store the maximum into the max array of registers. We'll write
1201 * it to the target variable later. */
1202 memset(s: max, c: 0, n: sizeof(max));
1203 for (j = 0; j < hll_count; j++) {
1204 /* Check type and size. */
1205 robj *o = hlls[j];
1206 if (o == NULL) continue; /* Assume empty HLL for non existing var. */
1207
1208 /* If at least one involved HLL is dense, use the dense representation
1209 * as target ASAP to save time and avoid the conversion step. */
1210 hdr = (struct hllhdr *) o->ptr;
1211 if (hdr->encoding == HLL_DENSE) use_dense = 1;
1212
1213 /* Merge with this HLL with our 'max' HHL by setting max[i]
1214 * to MAX(max[i],hll[i]). */
1215 if (hllMerge(max, hll: o) == HLL_C_ERR) {
1216 return NULL;
1217 }
1218 }
1219
1220 /* Create the destination key's value. */
1221 robj *result = hll_create();
1222 if (!result) {
1223 return NULL;
1224 }
1225
1226 /* Convert the destination object to dense representation if at least
1227 * one of the inputs was dense. */
1228 if (use_dense && hllSparseToDense(o: result) == HLL_C_ERR) {
1229 hll_destroy(obj: result);
1230 return NULL;
1231 }
1232
1233 /* Write the resulting HLL to the destination HLL registers and
1234 * invalidate the cached value. */
1235 for (j = 0; j < HLL_REGISTERS; j++) {
1236 if (max[j] == 0) continue;
1237 hdr = (struct hllhdr *) result->ptr;
1238 switch(hdr->encoding) {
1239 case HLL_DENSE: hllDenseSet(registers: hdr->registers + 1,index: j,count: max[j]); break;
1240 case HLL_SPARSE: hllSparseSet(o: result,index: j,count: max[j]); break;
1241 }
1242 }
1243 return result;
1244}
1245
1246uint64_t get_size() {
1247 return HLL_DENSE_SIZE;
1248}
1249
1250}
1251
1252namespace duckdb {
1253
1254static inline int AddToLog(void *log, const uint64_t &index, const uint8_t &count) {
1255 auto o = (duckdb_hll::robj *)log;
1256 duckdb_hll::hllhdr *hdr = (duckdb_hll::hllhdr *)o->ptr;
1257 D_ASSERT(hdr->encoding == HLL_DENSE);
1258 return duckdb_hll::hllDenseSet(registers: hdr->registers + 1, index, count);
1259}
1260
1261void AddToLogsInternal(UnifiedVectorFormat &vdata, idx_t count, uint64_t indices[], uint8_t counts[], void ***logs[],
1262 const SelectionVector *log_sel) {
1263 // 'logs' is an array of pointers to AggregateStates
1264 // AggregateStates have a pointer to a HyperLogLog object
1265 // HyperLogLog objects have a pointer to a 'robj', which we need
1266 for (idx_t i = 0; i < count; i++) {
1267 auto log = logs[log_sel->get_index(idx: i)];
1268 if (log && vdata.validity.RowIsValid(row_idx: vdata.sel->get_index(idx: i))) {
1269 AddToLog(log: **log, index: indices[i], count: counts[i]);
1270 }
1271 }
1272}
1273
1274void AddToSingleLogInternal(UnifiedVectorFormat &vdata, idx_t count, uint64_t indices[], uint8_t counts[], void *log) {
1275 const auto o = (duckdb_hll::robj *)log;
1276 duckdb_hll::hllhdr *hdr = (duckdb_hll::hllhdr *)o->ptr;
1277 D_ASSERT(hdr->encoding == HLL_DENSE);
1278
1279 const auto registers = hdr->registers + 1;
1280 for (idx_t i = 0; i < count; i++) {
1281 if (vdata.validity.RowIsValid(row_idx: vdata.sel->get_index(idx: i))) {
1282 duckdb_hll::hllDenseSet(registers, index: indices[i], count: counts[i]);
1283 }
1284 }
1285}
1286
1287} // namespace duckdb
1288