Changeset: ecd147e791e0 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=ecd147e791e0
Modified Files:
gdk/gdk_join.c
Branch: Mar2018
Log Message:
If both sides of a join have a hash, put probe shortest collision chain.
diffs (67 lines):
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -3793,6 +3793,7 @@ BATjoin(BAT **r1p, BAT **r2p, BAT *l, BA
BUN maxsize;
bool lhash = false, rhash = false;
bool plhash = false, prhash = false;
+ BUN lslots = 0, rslots = 0;
bool swap;
bat parent;
size_t mem_size;
@@ -3873,13 +3874,16 @@ BATjoin(BAT **r1p, BAT **r2p, BAT *l, BA
* length times the number of required probes
* is less than the cost for creating and
* probing a new hash on the view */
- lhash = BATcheckhash(b) &&
- (BATcount(b) == BATcount(l) ||
- BATcount(b) / ((size_t *)
b->thash->heap.base)[5] * rcount < lcount + rcount);
+ if (BATcheckhash(b)) {
+ lslots = ((size_t *) b->thash->heap.base)[5];
+ lhash = (BATcount(b) == BATcount(l) ||
+ BATcount(b) / lslots * rcount < lcount
+ rcount);
+ }
plhash = lhash;
}
} else if (BATtdense(sl) && BATcheckhash(l)) {
- lhash = BATcount(l) / ((size_t *) l->thash->heap.base)[5] *
rcount < lcount + rcount;
+ lslots = ((size_t *) l->thash->heap.base)[5];
+ lhash = BATcount(l) / lslots * rcount < lcount + rcount;
}
if (sr == NULL) {
rhash = BATcheckhash(r);
@@ -3889,17 +3893,28 @@ BATjoin(BAT **r1p, BAT **r2p, BAT *l, BA
* length times the number of required probes
* is less than the cost for creating and
* probing a new hash on the view */
- rhash = BATcheckhash(b) &&
- (BATcount(b) == BATcount(r) ||
- BATcount(b) / ((size_t *)
b->thash->heap.base)[5] * lcount < lcount + rcount);
+ if (BATcheckhash(b)) {
+ rslots = ((size_t *) b->thash->heap.base)[5];
+ rhash = (BATcount(b) == BATcount(r) ||
+ BATcount(b) / rslots * lcount < lcount
+ rcount);
+ }
prhash = rhash;
}
} else if (BATtdense(sr) && BATcheckhash(r)) {
- rhash = BATcount(r) / ((size_t *) r->thash->heap.base)[5] *
lcount < lcount + rcount;
+ rslots = ((size_t *) r->thash->heap.base)[5];
+ rhash = BATcount(r) / rslots * rcount < lcount + rcount;
}
if (lhash && rhash) {
- /* both have hash, smallest on right */
- swap = lcount < rcount;
+ if (lcount == lslots && rcount == rslots) {
+ /* both perfect hashes, smallest on right */
+ swap = lcount < rcount;
+ } else if (lcount == lslots) {
+ /* left is perfect (right isn't): swap */
+ swap = true;
+ } else if (rcount != rslots) {
+ /* neither is perfect, shortest chains on right */
+ swap = lcount / lslots < rcount / rslots;
+ } /* else: right is perfect */
reason = "both have hash";
} else if (lhash) {
/* only left has hash, swap */
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
