Changeset: 5defb50dee76 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=5defb50dee76
Modified Files:
monetdb5/modules/kernel/group.mx
Branch: Apr2011
Log Message:
fixed "hanging" group.derive():
In some data constallations,
e.g., a table with two integer columns such that
the first one only contains two distinct values and
the second one is unique, sorted, and dense with values starting from 10,
it apparently could happen that with a two-column primary key check,
after the initial group.new() on the combined hash-value
and the subsequent group.derive() on the first column,
the all groups are found (and of size 1)
(but the tail of the map-BAT is not marked as unique),
and then during the final group.derive() (group.done())
on the second column,
the existing group IDs (hcur) and
the values of the second column (tcur)
are correlated in such a way that
c = (((BUN) hcur) ^ HASH_@2(tcur)) is constant for all BUNs,
and consequently, the ("pseudo") hash-lookup
degenerates into a nested loop,
resulting in quadratic cost for the group.derive().
Not XORing the two values directly
(c = (((BUN) hcur) ^ HASH_@2(tcur))),
but rather shuffling the bit of the second values first
(c = (((BUN) hcur) ^ mix_BUN(HASH_@2(tcur))))
appears to fix the problem (in the given case).
diffs (12 lines):
diff --git a/monetdb5/modules/kernel/group.mx b/monetdb5/modules/kernel/group.mx
--- a/monetdb5/modules/kernel/group.mx
+++ b/monetdb5/modules/kernel/group.mx
@@ -827,7 +827,7 @@
hcur = *(oid*) BUNtloc(ct_mapi,cp);
/* hash-lookup of [hcur,tcur] in map */
- c = (((BUN) hcur) ^ HASH_@2(tcur));
+ c = (((BUN) hcur) ^ mix_BUN(HASH_@2(tcur)));
c = mix_BUN(c) & mask;
chain_@5 {
r = zz;
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
