Changeset: 638d8ccaaee4 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/638d8ccaaee4
Branch: pp_hashjoin
Log Message:
Merge with cnting_sketches branch.
diffs (truncated from 8193 to 300 lines):
diff --git a/gdk/CMakeLists.txt b/gdk/CMakeLists.txt
--- a/gdk/CMakeLists.txt
+++ b/gdk/CMakeLists.txt
@@ -91,6 +91,9 @@ target_sources(bat
gdk_tracer.c gdk_tracer.h
gdk_rtree.c
gdk_strimps.c
+ murmurhash3.h
+ xxhash.h
+ gdk_sketch.c
PUBLIC
${gdk_public_headers})
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -367,6 +367,13 @@ typedef struct pipeline_io {
#define ORDERIDXOFF 3
+#define HLL_BITS 6
+#define BITS_MASK ((1ULL << HLL_BITS) - 1)
+#define MAX_CLZ (64 - HLL_BITS)
+#define BUCKETS (1U << HLL_BITS)
+#define CLZ_BUCKETS (MAX_CLZ + 1)
+#define HLLSEED 0xadc83b19ULL
+
/* assert that atom width is power of 2, i.e., width == 1<<shift */
#define assert_shift_width(shift,width) assert(((shift) == 0 && (width) == 0)
|| ((unsigned)1<<(shift)) == (unsigned)(width))
@@ -1427,6 +1434,11 @@ gdk_export void STRMPdestroy(BAT *b);
gdk_export bool BAThasstrimps(BAT *b);
gdk_export gdk_return BATsetstrimps(BAT *b);
+gdk_export void sketch_populate(BAT* n, BATiter *ni, struct canditer *nci,
uint8_t cnting_sketch[BUCKETS][CLZ_BUCKETS]);
+/* gdk_export void sketch_merge(BAT* b, BAT* n); */
+gdk_export double sketch_estimate(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS]);
+gdk_export double bat_guess_uniques(BAT *b, BATiter *bi, struct canditer *bci);
+
/* Rtree structure functions */
#ifdef HAVE_RTREE
gdk_export bool RTREEexists(BAT *b);
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -3635,7 +3635,8 @@ BATguess_uniques(BAT *b, struct canditer
canditer_init(&lci, b, NULL);
ci = &lci;
}
- double uniques = guess_uniques(b, ci);
+ /* double uniques = guess_uniques(b, ci); */
+ double uniques = bat_guess_uniques(b, NULL, ci);
return uniques < 0 ? 0 : (BUN) uniques;
}
diff --git a/gdk/gdk_sketch.c b/gdk/gdk_sketch.c
new file mode 100644
--- /dev/null
+++ b/gdk/gdk_sketch.c
@@ -0,0 +1,168 @@
+/*
+ * SPDX-License-Identifier: MPL-2.0
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/.
+ *
+ * For copyright information, see the file debian/copyright.
+ */
+
+#include "gdk.h"
+
+#include <sys/random.h>
+// #include "murmurhash3.h"
+#define XXH_STATIC_LINKING_ONLY
+#define XXH_IMPLEMENTATION
+#include "xxhash.h"
+
+// Helper function sigma as defined in
+// "New cardinality estimation algorithms for HyperLogLog sketches"
+// Otmar Ertl, arXiv:1702.01284
+static inline double
+sigma(double x)
+{
+ if (x == 1.) return INFINITY;
+ double y = 1;
+ double z = x;
+ double z_prime;
+ do {
+ x *= x;
+ z_prime = z;
+ z += x * y;
+ y += y;
+ } while(z_prime != z);
+ return z;
+}
+
+// Helper function tau as defined in
+// "New cardinality estimation algorithms for HyperLogLog sketches"
+// Otmar Ertl, arXiv:1702.01284
+static inline double
+tau(double x)
+{
+ if (x == 0. || x == 1.) return 0.;
+ double y = 1.0;
+ double z = 1 - x;
+ double z_prime;
+ do {
+ x = sqrt(x);
+ z_prime = z;
+ y *= 0.5;
+ z -= pow(1 - x, 2) * y;
+ } while(z_prime != z);
+ return z / 3;
+}
+
+/// Estimator as defined in
+/// "New cardinality estimation algorithms for HyperLogLog sketches"
+/// Otmar Ertl, arXiv:1702.01284.
+/// Only difference is how the multiplicity array is computed
+double
+sketch_estimate(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS])
+{
+ int8_t C[CLZ_BUCKETS + 1] = {0};
+ for (size_t bucket = 0; bucket < BUCKETS; bucket++) {
+ int K = -1;
+ for (size_t clz = 0; clz < CLZ_BUCKETS; clz++)
+ if (cnt_sketch[bucket][clz] > 0)
+ K = clz;
+ K == -1 ? C[0]++ : C[K + 1]++;
+ }
+ double t = tau(1.0 - ((double)C[CLZ_BUCKETS] / BUCKETS));
+ double z = (double)BUCKETS * t;
+ for (int k = CLZ_BUCKETS; k >= 1; k--)
+ z = 0.5 * (z + (double)C[k]);
+ double s = sigma((double)C[0] / BUCKETS);
+ z += (double)BUCKETS * s;
+ const double alpha = 0.7213475204444817;
+ return alpha * (double)BUCKETS * BUCKETS / z;
+}
+
+void
+sketch_populate(BAT* b, BATiter *bi, struct canditer *bci,
+ uint8_t cnting_sketch[BUCKETS][CLZ_BUCKETS])
+{
+ oid hseq = b->hseqbase;
+ /* uint64_t murmur3_out[2]; */
+ uint64_t hash;
+ uint8_t bucket;
+
+ uint8_t clz;
+
+ QryCtx *qry_ctx = MT_thread_get_qry_ctx();
+ canditer_reset(bci);
+ TIMEOUT_LOOP(bci->ncand, qry_ctx) {
+ BUN p = canditer_next(bci) - hseq;
+ const void *ptr = BUNtail(bi, p);
+ switch (bi->type) {
+ case TYPE_int:
+ if (is_int_nil(*(int *)ptr))
+ continue;
+ else
+ /* MurmurHash3_x64_128(ptr, sizeof(int),
HLLSEED, murmur3_out); */
+ /* hash = murmur3_out[1]; */
+ hash = XXH64(ptr, sizeof(int), HLLSEED);
+ break;
+ case TYPE_lng:
+ if (is_lng_nil(*(lng *)ptr))
+ continue;
+ else
+ /* MurmurHash3_x64_128(ptr, sizeof(lng),
HLLSEED, murmur3_out); */
+ /* hash = murmur3_out[1]; */
+ hash = XXH64(ptr, sizeof(lng), HLLSEED);
+ break;
+ case TYPE_str:
+ if (strNil(ptr))
+ continue;
+ else
+ /* MurmurHash3_x64_128(ptr, strlen(ptr),
HLLSEED, murmur3_out); */
+ /* hash = murmur3_out[1]; */
+ hash = XXH64(ptr, strlen(ptr), HLLSEED);
+ break;
+ default:
+ return;
+ }
+ bucket = hash & BITS_MASK;
+ hash |= BITS_MASK;
+ clz = __builtin_clzll(hash);
+ assert(clz <= 58);
+ if (cnting_sketch[bucket][clz] <= 128) {
+ cnting_sketch[bucket][clz]++;
+ } else {
+ uint8_t k = cnting_sketch[bucket][clz] - 128;
+ uint64_t rng;
+ getrandom(&rng, sizeof(rng), 0);
+ if ((rng & ((1ULL << k) - 1)) == 0)
+ cnting_sketch[bucket][clz]++;
+ }
+ }
+}
+
+/* void */
+/* sketch_merge(BAT* b, BAT* n) */
+/* { */
+/* MT_lock_set(&b->batIdxLock); */
+/* for (size_t i = 0; i < BUCKETS; i++) */
+/* for (size_t j = 0; j < CLZ_BUCKETS; j++) */
+/* if (n->cnting_sketch[i][j] > b->cnting_sketch[i][j]) */
+/* b->cnting_sketch[i][j] =
n->cnting_sketch[i][j]; */
+/* b->unique_guess = sketch_estimate(b->cnting_sketch); */
+/* MT_lock_unset(&b->batIdxLock); */
+/* } */
+
+double
+bat_guess_uniques(BAT *b, BATiter *bi, struct canditer *bci)
+{
+ uint8_t cnting_sketch[BUCKETS][CLZ_BUCKETS] = {0};
+
+ BATiter nbi = bi ? *bi : bat_iterator(b);
+
+ sketch_populate(b, &nbi, bci, cnting_sketch);
+ double unique_guess = sketch_estimate(cnting_sketch);
+
+ if (bi == NULL)
+ bat_iterator_end(&nbi);
+
+ return unique_guess;
+}
diff --git a/gdk/murmurhash3.h b/gdk/murmurhash3.h
new file mode 100644
--- /dev/null
+++ b/gdk/murmurhash3.h
@@ -0,0 +1,374 @@
+//-----------------------------------------------------------------------------
+// MurmurHash3 was written by Austin Appleby, and is placed in the public
+// domain. The author hereby disclaims copyright to this source code.
+
+// Note - The x86 and x64 versions do _not_ produce the same results, as the
+// algorithms are optimized for their respective platforms. You can still
+// compile and run any of them on any platform, but your performance with the
+// non-native version will be less than optimal.
+
+#ifndef _MURMURHASH3_H_
+#define _MURMURHASH3_H_
+
+//-----------------------------------------------------------------------------
+// Platform-specific functions and macros
+
+// Microsoft Visual Studio
+
+#if defined(_MSC_VER) && (_MSC_VER < 1600)
+
+typedef unsigned char uint8_t;
+typedef unsigned int uint32_t;
+typedef unsigned __int64 uint64_t;
+
+// Other compilers
+
+#else // defined(_MSC_VER)
+
+#include <stdint.h>
+
+#endif // !defined(_MSC_VER)
+
+//-----------------------------------------------------------------------------
+
+void MurmurHash3_x86_32 ( const void * key, int len, uint32_t seed, void *
out );
+
+void MurmurHash3_x86_128 ( const void * key, int len, uint32_t seed, void *
out );
+
+void MurmurHash3_x64_128 ( const void * key, int len, uint32_t seed, void *
out );
+
+//-----------------------------------------------------------------------------
+// Platform-specific functions and macros
+
+// Microsoft Visual Studio
+
+#if defined(_MSC_VER)
+
+#define FORCE_INLINE __forceinline
+
+#include <stdlib.h>
+
+#define ROTL32(x,y) _rotl(x,y)
+#define ROTL64(x,y) _rotl64(x,y)
+
+#define BIG_CONSTANT(x) (x)
+
+// Other compilers
+
+#else // defined(_MSC_VER)
+
+#define FORCE_INLINE inline __attribute__((always_inline))
+
+static inline uint32_t
+rotl32 ( uint32_t x, int8_t r )
+{
+ return (x << r) | (x >> (32 - r));
+}
+
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
