Changeset: 62fb0d6419ab for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=62fb0d6419ab
Added Files:
gdk/gdk_hash.c
gdk/gdk_hash.h
Modified Files:
clients/Tests/exports.stable.out
gdk/Makefile.ag
gdk/gdk.h
gdk/gdk_bat.c
gdk/gdk_batop.c
gdk/gdk_group.c
gdk/gdk_join.c
gdk/gdk_logger.c
gdk/gdk_private.h
gdk/gdk_search.c
gdk/gdk_search.h
gdk/gdk_select.c
gdk/gdk_setop.c
gdk/gdk_unique.c
monetdb5/mal/mal_runtime.c
monetdb5/modules/kernel/bat5.c
monetdb5/modules/mal/cluster.c
monetdb5/modules/mal/tokenizer.c
sql/backends/monet5/sql.c
sql/storage/bat/bat_table.c
Branch: partioned-hash
Log Message:
Implemented partioned hash tables.
The hash table implementation is now in a separate file, gdk_hash.c.
The idea behind the hash table has not changed, except that now the
hash table is split into multiple pieces.
diffs (truncated from 2922 to 300 lines):
diff --git a/clients/Tests/exports.stable.out b/clients/Tests/exports.stable.out
--- a/clients/Tests/exports.stable.out
+++ b/clients/Tests/exports.stable.out
@@ -135,7 +135,7 @@ BAT *BATgroupsum(BAT *b, BAT *g, BAT *e,
BAT *BATgroupvariance_population(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
BAT *BATgroupvariance_sample(BAT *b, BAT *g, BAT *e, BAT *s, int tp, int
skip_nils, int abort_on_error);
BUN BATgrows(BAT *b);
-gdk_return BAThash(BAT *b, BUN masksize);
+gdk_return BAThash(BAT *b);
gdk_return BATimprints(BAT *b);
gdk_return BATins(BAT *b, BAT *c, bit force);
BAT *BATintersectcand(BAT *a, BAT *b);
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -26,6 +26,7 @@ lib_gdk = {
gdk_system.h gdk_system_private.h gdk_tm.h gdk_storage.h \
gdk_calc.c gdk_calc.h gdk_calc_compare.h gdk_calc_private.h \
gdk_aggr.c gdk_group.c gdk_mapreduce.c gdk_mapreduce.h \
+ gdk_hash.c gdk_hash.h \
gdk_imprints.c gdk_imprints.h \
gdk_join.c gdk_join_legacy.c \
gdk_unique.c \
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -622,12 +622,12 @@ typedef size_t BUN;
#endif
typedef uint16_t BUN2type;
typedef uint32_t BUN4type;
-#if SIZEOF_BUN > 4
+#ifdef BUN8
typedef uint64_t BUN8type;
#endif
#define BUN2_NONE ((BUN2type) 0xFFFF)
#define BUN4_NONE ((BUN4type) 0xFFFFFFFF)
-#if SIZEOF_BUN > 4
+#ifdef BUN8
#define BUN8_NONE ((BUN8type) LL_CONSTANT(0xFFFFFFFFFFFFFFFF))
#endif
@@ -663,16 +663,7 @@ typedef struct {
bat parentid; /* cache id of VIEW parent bat */
} Heap;
-typedef struct {
- int type; /* type of index entity */
- int width; /* width of hash entries */
- BUN nil; /* nil representation */
- BUN lim; /* collision list size */
- BUN mask; /* number of hash buckets-1 (power of 2) */
- void *Hash; /* hash table */
- void *Link; /* collision list */
- Heap *heap; /* heap where the hash is stored */
-} Hash;
+#include "gdk_hash.h"
typedef struct Imprints Imprints;
@@ -2072,7 +2063,8 @@ gdk_export oid OIDnew(oid inc);
* accelerator on the tail of the BAT exists. GDK_FAIL is returned
* upon failure to create the supportive structures.
*/
-gdk_export gdk_return BAThash(BAT *b, BUN masksize);
+
+gdk_export gdk_return BAThash(BAT *b);
/*
* @- Column Imprints Functions
@@ -2975,85 +2967,8 @@ gdk_export void ALIGNsetH(BAT *b1, BAT *
#define DELloop(b, p, q) \
for (q = (b)->batFirst, p = (b)->batDeleted; p < q; p++)
-/*
- * @- hash-table supported loop over BUNs
- * The first parameter `b' is a BAT, the second (`h') should point to
- * `b->H->hash', and `v' a pointer to an atomic value (corresponding
- * to the head column of `b'). The 'hb' is an integer index, pointing
- * out the `hb'-th BUN.
- */
#define GDK_STREQ(l,r) (*(char*) (l) == *(char*) (r) && !strcmp(l,r))
-#define HASHloop(bi, h, hb, v) \
- for (hb = HASHget(h, HASHprobe((h), v)); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (ATOMcmp(h->type, v, BUNtail(bi, hb)) == 0)
-#define HASHloop_str_hv(bi, h, hb, v) \
- for (hb = HASHget((h),((BUN *) (v))[-1]&(h)->mask); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (GDK_STREQ(v, BUNtvar(bi, hb)))
-#define HASHloop_str(bi, h, hb, v) \
- for (hb = HASHget((h),strHash(v)&(h)->mask); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (GDK_STREQ(v, BUNtvar(bi, hb)))
-
-/*
- * The following example shows how the hashloop is used:
- *
- * @verbatim
- * void
- * print_books(BAT *books_author, str author)
- * {
- * BAT *b = books_author;
- * BUN i;
- *
- * printf("%s\n==================\n", author);
- * HASHloop(b, (b)->T->hash, i, author)
- * printf("%s\n", ((str) BUNhead(b, i));
- * }
- * @end verbatim
- *
- * Note that for optimization purposes, we could have used a
- * HASHloop_str instead, and also a BUNhvar instead of a BUNhead
- * (since we know the head-type of books_author is string, hence
- * variable-sized). However, this would make the code less general.
- *
- * @- specialized hashloops
- * HASHloops come in various flavors, from the general HASHloop, as
- * above, to specialized versions (for speed) where the type is known
- * (e.g. HASHloop_int), or the fact that the atom is fixed-sized
- * (HASHlooploc) or variable-sized (HASHloopvar).
- */
-#define HASHlooploc(bi, h, hb, v) \
- for (hb = HASHget(h, HASHprobe(h, v)); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (ATOMcmp(h->type, v, BUNtloc(bi, hb)) == 0)
-#define HASHloopvar(bi, h, hb, v) \
- for (hb = HASHget(h,HASHprobe(h, v)); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (ATOMcmp(h->type, v, BUNtvar(bi, hb)) == 0)
-
-#define HASHloop_TYPE(bi, h, hb, v, TYPE) \
- for (hb = HASHget(h, hash_##TYPE(h, v)); \
- hb != HASHnil(h); \
- hb = HASHgetlink(h,hb)) \
- if (simple_EQ(v, BUNtloc(bi, hb), TYPE))
-
-#define HASHloop_bte(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, bte)
-#define HASHloop_sht(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, sht)
-#define HASHloop_int(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, int)
-#define HASHloop_lng(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, lng)
-#ifdef HAVE_HGE
-#define HASHloop_hge(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, hge)
-#endif
-#define HASHloop_flt(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, flt)
-#define HASHloop_dbl(bi, h, hb, v) HASHloop_TYPE(bi, h, hb, v, dbl)
-
/*
* @- loop over a BAT with ordered tail
* Here we loop over a BAT with an ordered tail column (see for
diff --git a/gdk/gdk_bat.c b/gdk/gdk_bat.c
--- a/gdk/gdk_bat.c
+++ b/gdk/gdk_bat.c
@@ -1815,7 +1815,6 @@ BUNlocate(BAT *b, const void *x, const v
lng l;
} hidx, tidx;
BUN p, q;
- BAT *v = NULL;
BATcheck(b, "BUNlocate: BAT parameter required", 0);
BATcheck(x, "BUNlocate: value parameter required", 0);
@@ -1840,7 +1839,7 @@ BUNlocate(BAT *b, const void *x, const v
}
/* positional lookup is always the best choice */
- if (BATtdense(b))
+ if (BATtdense(b) && !BAThdense(b))
usemirror();
if (BAThdense(b)) {
BUN i = (BUN) (*(oid *) x - b->hseqbase);
@@ -1871,61 +1870,12 @@ BUNlocate(BAT *b, const void *x, const v
if (p >= q)
return BUN_NONE; /* value combination cannot occur */
- /* if the range is still larger than 32 BUNs, consider
- * investing in a hash table */
- if ((q - p) > (1 << 5)) {
- /* regrettably MonetDB support only single-column hashes
- * strategy: create a hash on both columns, and select
- * the column with the best distribution
- */
- if ((b->T->hash && b->H->hash == NULL) || !dohash(b->H))
- usemirror();
- if (b->H->hash == NULL && (v = VIEWcreate_(b, b, TRUE)) !=
NULL) {
- /* As we are going to remove the worst hash
- * table later, we must do everything in a
- * view, as it is not permitted to remove a
- * hash table from a read-only operation (like
- * BUNlocate). Other threads might then crash.
- */
- if (dohash(v->H))
- (void) BAThash(BATmirror(v), 0);
- if (dohash(v->T))
- (void) BAThash(v, 0);
- if (v->H->hash && v->T->hash) { /* we can choose
between two hash tables */
- BUN hcnt = 0, tcnt = 0;
- BUN i;
-
- for (i = 0; i <= v->H->hash->mask; i++)
- hcnt += HASHget(v->H->hash,i) !=
HASHnil(v->H->hash);
- for (i = 0; i <= v->T->hash->mask; i++)
- tcnt += HASHget(v->T->hash,i) !=
HASHnil(v->T->hash);
- if (hcnt < tcnt) {
- usemirror();
- v = BATmirror(v);
- }
- /* remove the least selective hash table */
- HASHremove(v);
- }
- if (v->H->hash == NULL) {
- usemirror();
- v = BATmirror(v);
- }
- if (v->H->hash) {
- MT_lock_set(&GDKhashLock(abs(b->batCacheid)),
"BUNlocate");
- if (b->H->hash == NULL) { /* give it to
the parent */
- b->H->hash = v->H->hash;
- }
- MT_lock_unset(&GDKhashLock(abs(b->batCacheid)),
"BUNlocate");
- }
- BBPreclaim(v);
- v = NULL;
- }
- }
-
/* exploit string double elimination, when present */
htpe = ATOMbasetype(b->htype);
ttpe = ATOMbasetype(b->ttype);
- if (ATOMstorage(htpe) == TYPE_str && GDK_ELIMDOUBLES(b->H->vheap) &&
b->H->width > 2) {
+ if (ATOMstorage(htpe) == TYPE_str &&
+ GDK_ELIMDOUBLES(b->H->vheap) &&
+ b->H->width > 2) {
hidx.v = strLocate(b->H->vheap, x);
if (hidx.v == 0)
return BUN_NONE; /* x does not occur */
@@ -1950,7 +1900,9 @@ BUNlocate(BAT *b, const void *x, const v
}
}
}
- if (ATOMstorage(ttpe) == TYPE_str && GDK_ELIMDOUBLES(b->T->vheap) &&
b->T->width > 2) {
+ if (ATOMstorage(ttpe) == TYPE_str &&
+ GDK_ELIMDOUBLES(b->T->vheap) &&
+ b->T->width > 2) {
tidx.v = strLocate(b->T->vheap, y);
if (tidx.v == 0)
return BUN_NONE; /* y does not occur */
@@ -1998,26 +1950,28 @@ BUNlocate(BAT *b, const void *x, const v
/* hashloop over head values, check tail values */
if (b->H->hash) {
BUN h;
+ BUN prb = HASHprobe(b->H->hash, x);
+ int pcs;
bi = bat_iterator(BATmirror(b)); /* HASHloop works on tail */
if (hint && tint) {
- HASHloop_int(bi, b->H->hash, h, x)
+ HASHloop_int(bi, b->H->hash, prb, x, h, pcs)
if (*(int *) y == *(int *) BUNhloc(bi, h))
return h;
} else if (hint && tlng) {
- HASHloop_int(bi, b->H->hash, h, x)
+ HASHloop_int(bi, b->H->hash, prb, x, h, pcs)
if (*(lng *) y == *(lng *) BUNhloc(bi, h))
return h;
} else if (hlng && tint) {
- HASHloop_lng(bi, b->H->hash, h, x)
+ HASHloop_lng(bi, b->H->hash, prb, x, h, pcs)
if (*(int *) y == *(int *) BUNhloc(bi, h))
return h;
} else if (hlng && tlng) {
- HASHloop_lng(bi, b->H->hash, h, x)
+ HASHloop_lng(bi, b->H->hash, prb, x, h, pcs)
if (*(lng *) y == *(lng *) BUNhloc(bi, h))
return h;
} else {
- HASHloop(bi, b->H->hash, h, x)
+ HASHloop(bi, b->H->hash, prb, x, h, pcs)
if ((*tcmp) (y, BUNhead(bi, h)) == 0)
return h;
}
@@ -2850,7 +2804,7 @@ BATassertHeadProps(BAT *b)
}
PROPDEBUG { /* only do a scan if property checking is requested */
- if (b->hsorted || b->hrevsorted || !b->hkey) {
+ if (b->hsorted || b->hrevsorted || !b->hkey || BATcount(b) ==
0) {
/* if sorted (either way), or we don't have to
* prove uniqueness, we can do a simple
* scan */
@@ -2894,16 +2848,15 @@ BATassertHeadProps(BAT *b)
/* we need to check for uniqueness the hard
* way (i.e. using a hash table) */
const char *nme = BBP_physical(b->batCacheid);
- char *ext;
size_t nmelen = strlen(nme);
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
