Changeset: 0a6586678e39 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=0a6586678e39
Modified Files:
gdk/gdk_join.c
Branch: default
Log Message:
In hashjoin, build hash on *larger* of the two BATs.
When doing a hash join, we need to go through both BATs once: once
through the one on the right to create the hash, and once through the
one on the left to try to match values. The question is, which of the
two scans is more expensive. With an observed average of 4 links in
the hash chain, building the hash is cheaper than probing. This means
it is better to build the hash on the larger of the two BATs.
diffs (25 lines):
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -2267,8 +2267,8 @@ BATsubjoin(BAT **r1p, BAT **r2p, BAT *l,
else
return mergejoin(r2, r1, r, l, sr, sl, nil_matches, 0,
0, 0);
} else if (l->T->hash && r->T->hash) {
- /* both have hash, smallest on right */
- swap = lcount < rcount;
+ /* both have hash, largest on right */
+ swap = lcount > rcount;
} else if (l->T->hash) {
/* only left has hash, swap */
swap = 1;
@@ -2289,8 +2289,8 @@ BATsubjoin(BAT **r1p, BAT **r2p, BAT *l,
* large (i.e. prefer hash over binary search, but
* only if the hash table doesn't cause thrashing) */
return mergejoin(r1, r2, l, r, sl, sr, nil_matches, 0, 0, 0);
- } else if (BATcount(l) < BATcount(r)) {
- /* no hashes, not sorted, create hash on smallest BAT */
+ } else if (BATcount(l) > BATcount(r)) {
+ /* no hashes, not sorted, create hash on largest BAT */
swap = 1;
}
if (swap) {
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
