Changeset: 5567a6a30649 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/5567a6a30649
Modified Files:
gdk/gdk.h
gdk/gdk_bat.c
gdk/gdk_batop.c
gdk/gdk_join.c
gdk/gdk_sketch.c
monetdb5/modules/kernel/aggr.c
sql/backends/monet5/sql_statistics.c
Branch: cnting_sketches
Log Message:
Compute estimate through analyze only for now. Also set it properly.
diffs (288 lines):
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -449,9 +449,6 @@ typedef struct BAT {
struct pipeline_io *pl_io;
- uint8_t cnting_sketch[BUCKETS][CLZ_BUCKETS];
- double unique_guess;
-
MT_Lock theaplock; /* lock protecting heap reference changes */
MT_RWLock thashlock; /* lock specifically for hash management */
MT_Lock batIdxLock; /* lock to manipulate other indexes/properties
*/
@@ -1425,10 +1422,10 @@ 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);
-gdk_export void sketch_merge(BAT* b, BAT* n);
-gdk_export double sketch_estimator(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS]);
-gdk_export double BATsketch_estimator(BAT *b, BATiter *bi, struct canditer
*bci);
+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
diff --git a/gdk/gdk_bat.c b/gdk/gdk_bat.c
--- a/gdk/gdk_bat.c
+++ b/gdk/gdk_bat.c
@@ -177,7 +177,6 @@ BATcreatedesc(oid hseq, int tt, bool hea
.tvheap = vh,
.creator_tid = MT_getpid(),
.qc = role == TRANSIENT ? MT_thread_get_qry_ctx() : NULL,
- .cnting_sketch = {0},
};
if (bn->theap) {
diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c
--- a/gdk/gdk_batop.c
+++ b/gdk/gdk_batop.c
@@ -1085,9 +1085,6 @@ BATappend2(BAT *b, BAT *n, BAT *s, bool
hlocked = false;
}
- sketch_populate(n, &ni, &ci);
- sketch_merge(b, n);
-
doreturn:
bat_iterator_end(&ni);
if (minbound)
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -3542,9 +3542,6 @@ count_unique(BAT *b, BAT *s, BUN *cnt1,
static double
guess_uniques(BAT *b, struct canditer *ci)
{
- if (b->unique_guess)
- return b->unique_guess;
-
BUN cnt1 = 0, cnt2;
BUN max = b->twidth < SIZEOF_BUN ? (BUN) 1 << (8*b->twidth) : BUN_MAX;
BAT *s1;
@@ -3630,8 +3627,6 @@ BATguess_uniques(BAT *b, struct canditer
n = 0;
else if (b->batCount == 1 || (ci && ci->ncand == 1))
n = 1;
- if (b->unique_guess)
- return b->unique_guess;
MT_lock_unset(&b->theaplock);
if (n != BUN_NONE)
return n;
@@ -3640,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
--- a/gdk/gdk_sketch.c
+++ b/gdk/gdk_sketch.c
@@ -11,14 +11,14 @@
#include "gdk.h"
#include <sys/random.h>
-/// #include "murmurhash3.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
+// Helper function sigma as defined in
+// "New cardinality estimation algorithms for HyperLogLog sketches"
+// Otmar Ertl, arXiv:1702.01284
static inline double
sigma(double x)
{
@@ -35,9 +35,9 @@ sigma(double x)
return z;
}
-/// Helper function tau as defined in
-/// "New cardinality estimation algorithms for HyperLogLog sketches"
-/// Otmar Ertl, arXiv:1702.01284
+// Helper function tau as defined in
+// "New cardinality estimation algorithms for HyperLogLog sketches"
+// Otmar Ertl, arXiv:1702.01284
static inline double
tau(double x)
{
@@ -59,11 +59,10 @@ tau(double x)
/// Otmar Ertl, arXiv:1702.01284.
/// Only difference is how the multiplicity array is computed
double
-sketch_estimator(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS])
+sketch_estimate(uint8_t cnt_sketch[BUCKETS][CLZ_BUCKETS])
{
int8_t C[CLZ_BUCKETS + 1] = {0};
- for (size_t bucket = 0; bucket < BUCKETS; bucket++)
- {
+ 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)
@@ -73,9 +72,7 @@ sketch_estimator(uint8_t cnt_sketch[BUCK
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;
@@ -83,13 +80,14 @@ sketch_estimator(uint8_t cnt_sketch[BUCK
}
void
-sketch_populate(BAT* b, BATiter *bi, struct canditer *bci)
+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 cnting_sketch[BUCKETS][CLZ_BUCKETS] = {0}; */
+
uint8_t clz;
QryCtx *qry_ctx = MT_thread_get_qry_ctx();
@@ -129,45 +127,42 @@ sketch_populate(BAT* b, BATiter *bi, str
hash |= BITS_MASK;
clz = __builtin_clzll(hash);
assert(clz <= 58);
- if (b->cnting_sketch[bucket][clz] <= 128) {
- b->cnting_sketch[bucket][clz]++;
+ if (cnting_sketch[bucket][clz] <= 128) {
+ cnting_sketch[bucket][clz]++;
} else {
- uint8_t k = b->cnting_sketch[bucket][clz] - 128;
+ uint8_t k = cnting_sketch[bucket][clz] - 128;
uint64_t rng;
getrandom(&rng, sizeof(rng), 0);
if ((rng & ((1ULL << k) - 1)) == 0)
- b->cnting_sketch[bucket][clz]++;
+ 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_estimator(b->cnting_sketch);
- MT_lock_unset(&b->batIdxLock);
-}
+/* 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
-BATsketch_estimator(BAT *b, BATiter *bi, struct canditer *bci)
+bat_guess_uniques(BAT *b, BATiter *bi, struct canditer *bci)
{
- if (b->unique_guess)
- return b->unique_guess;
- BATiter nbi;
- struct canditer nbci;
- if (bi == NULL) {
- nbi = bat_iterator(b);
- canditer_init(&nbci, b, NULL);
- }
- sketch_populate(b, bi ? bi : &nbi, bci ? bci : &nbci);
- double unique_guess = sketch_estimator(b->cnting_sketch);
- b->unique_guess = unique_guess;
+ 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/monetdb5/modules/kernel/aggr.c b/monetdb5/modules/kernel/aggr.c
--- a/monetdb5/modules/kernel/aggr.c
+++ b/monetdb5/modules/kernel/aggr.c
@@ -1543,6 +1543,7 @@ static str
AGGRcde(Client c, int *estimate, const bat *bid)
{
(void) c;
+
BAT *b = BATdescriptor(*bid);
if (b == NULL)
throw(MAL, "AGGRcde", SQLSTATE(HY002) RUNTIME_OBJECT_MISSING);
@@ -1550,13 +1551,7 @@ AGGRcde(Client c, int *estimate, const b
struct canditer bci;
canditer_init(&bci, b, NULL);
- if (VIEWtparent(b)) {
- BAT *pb = BATdescriptor(VIEWtparent(b));
- printf("cnt dist est prop %f\n", pb->unique_guess);
- BBPreclaim(pb);
- }
-
- double est = BATsketch_estimator(b, &bi, &bci);
+ double est = bat_guess_uniques(b, &bi, &bci);
bat_iterator_end(&bi);
BBPreclaim(b);
diff --git a/sql/backends/monet5/sql_statistics.c
b/sql/backends/monet5/sql_statistics.c
--- a/sql/backends/monet5/sql_statistics.c
+++ b/sql/backends/monet5/sql_statistics.c
@@ -175,6 +175,7 @@ sql_analyze(Client cntxt, MalBlkPtr mb,
continue;
BAT *b, *unq;
ptr mn, mx;
+ double unique_est;
if (col && strcmp(c->base.name, col))
continue;
@@ -202,10 +203,8 @@ sql_analyze(Client cntxt, MalBlkPtr mb,
BBPunfix(unq->batCacheid);
/* Guess number of uniques if not
entirely unique */
- (void) BATguess_uniques(b, NULL);
+ unique_est =
(double)BATguess_uniques(b, NULL);
- if (b->unique_guess == 0)
- (void) BATsketch_estimator(b,
NULL, NULL);
/* Collect min and max values */
mn = BATmin(b, NULL);
@@ -213,6 +212,8 @@ sql_analyze(Client cntxt, MalBlkPtr mb,
mx = BATmax(b, NULL);
GDKfree(mx);
BBPunfix(b->batCacheid);
+
+ store->storage_api.set_stats_col(tr, c,
&unique_est, NULL, NULL);
}
}
}
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
