Changeset: d316e449dcab for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d316e449dcab
Modified Files:
gdk/gdk_group.c
Branch: Feb2013
Log Message:
improved multi-column grouping, in particular compound key checks:
when combining value and group-id hashes,
left-shift them by, respectively,
1/3 & 2/3 of the hash-mask width
to better spread bits and use entire hash-mask,
and thus reduce collisions
brings TPCH SF-100 key checking on bricks
from ~2 h (~120 min) down to ~20 min
diffs (56 lines):
diff --git a/gdk/gdk_group.c b/gdk/gdk_group.c
--- a/gdk/gdk_group.c
+++ b/gdk/gdk_group.c
@@ -74,7 +74,10 @@
do { \
v = BUNtail(bi, p); \
if (grps) { \
- prb = hash_##TYPE(hs, v) ^ hash_oid(hs, &grps[p-r]); \
+ BUN hv = hash_##TYPE(hs, v); \
+ BUN hg = hash_oid(hs, &grps[p-r]); \
+ prb = (hv ^ (hv << bits1) ^ \
+ hg ^ (hg << bits2)) & hs->mask; \
for (hb = hs->hash[prb]; \
hb != BUN_NONE; \
hb = hs->link[hb]) { \
@@ -485,6 +488,18 @@ BATgroup_internal(BAT **groups, BAT **ex
size_t nmelen;
Heap *hp = NULL;
BUN prb;
+ BUN mask = HASHmask(b->batCount) >> 3;
+ int bits1 = 3, bits2;
+
+ /* when combining value and group-id hashes,
+ * left-shift them by, respectively,
+ * 1/3 & 2/3 of the hash-mask width
+ * to better spread bits and use entire hash-mask,
+ * and thus reduce collisions */
+ while (mask>>=1)
+ bits1++;
+ bits1 /= 3;
+ bits2 = 2 * bits1;
/* not sorted, and no pre-existing hash table: we'll
* build an incomplete hash table on the fly--also see
@@ -544,9 +559,11 @@ BATgroup_internal(BAT **groups, BAT **ex
break;
default:
v = BUNtail(bi, p);
- prb = hash_any(hs, v);
if (grps) {
- prb ^= hash_oid(hs, &grps[p-r]);
+ BUN hv = hash_any(hs, v);
+ BUN hg = hash_oid(hs, &grps[p-r]);
+ prb = (hv ^ (hv << bits1) ^
+ hg ^ (hg << bits2)) & hs->mask;
for (hb = hs->hash[prb];
hb != BUN_NONE;
hb = hs->link[hb]) {
@@ -559,6 +576,7 @@ BATgroup_internal(BAT **groups, BAT **ex
}
}
} else {
+ prb = hash_any(hs, v);
for (hb = hs->hash[prb];
hb != BUN_NONE;
hb = hs->link[hb]) {
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
