Changeset: 432db0aba3fe for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=432db0aba3fe
Modified Files:
MonetDB5/src/modules/kernel/aggr.mx
MonetDB5/src/modules/kernel/aggr_be_avg.mx
MonetDB5/src/modules/kernel/aggr_be_count.mx
MonetDB5/src/modules/kernel/aggr_be_minmax.mx
MonetDB5/src/modules/kernel/aggr_be_prod.mx
MonetDB5/src/modules/kernel/aggr_be_sum.mx
MonetDB5/src/modules/kernel/aggr_bge_avg.mx
MonetDB5/src/modules/kernel/aggr_bge_count.mx
MonetDB5/src/modules/kernel/aggr_bge_minmax.mx
MonetDB5/src/modules/kernel/aggr_bge_prod.mx
MonetDB5/src/modules/kernel/aggr_bge_sum.mx
Branch: Jun2010
Log Message:
refining changeset 647c99679171 to avoid performance degradation:
changeset 36465:647c99679171 said:
"
avoid hash overhead when looking up group IDs in group extend
Using hasing to lookup group IDs in the group extend --- basically
performing a foreign-key join between group map an group extend ---
is rather expensive, not only because both creating the hash table
and probing the hash table inherently require random access, but also
because the "hash table" (mask & linked list) are rather large.
However, in practice, the group extend is often sorted, and the group
map "almost sorted" or at least clustered such that group IDs in
cluster i are smaller than those in cluster i+1 (this is the case if
the first grouping attribute (column/BAT) is sorted).
In this case, performing a "layman's merge" by keeping a cursor
into the group extend that simply performs a local forward/backward
scan starting from the position of the last lookup, turned out to
perform significantly better than a hash lookup.
"
However, the assumption that with the group extend BAT (e) being sorted
on head also the group map BAT (g) is "almost sorted" or "mostly ascending"
or at least clustered such that group IDs in cluster i are smaller than
those in cluster i+1, does not appear to be true in all cases.
In case the group extend BAT (e) is sorted on head but the group map BAT (g)
is not "almost sorted" / "mostly ascending" but rather randomly ordered,
the newly introduced "layman's merge" performs sugnificanly worse than
standard hash-lookup.
Lacking a suitable and efficient way to detect that the tail of the group
map (g) is "almost sorted" or "mostly ascending", for the time being, we
deploy the "layman's merge" only in case the tail of the group map (g)
is fully sorted (which is most probably only the case in case the table
is sorted on all group-by columns) to avoid a performance degradation.
The "layman's merge" optimization will be re-enabled once we have a
suitable and efficient way to detect that the tail of the group map (g)
is "almost sorted" or "mostly ascending".
diffs (144 lines):
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr.mx
--- a/MonetDB5/src/modules/kernel/aggr.mx Mon Jul 05 08:20:48 2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr.mx Mon Jul 05 09:46:39 2010 +0200
@@ -196,11 +196,15 @@
@-
In case the head of the group extend (e) is sorted, we assume that also the
-the tail of group map (g) "almost" sorted --- or at least clustered such
-that group IDs in cluster i are smaller than those in cluster i+1; this is
-the case if the first grouping attribute (column/BAT) is sorted --- and
-resorted to "local scanning" rather than (inherently random and expensive)
-hash-lookups.
+the tail of the group map (g) is "almost" sorted or "mostly ascending" ---
+or at least clustered such that group IDs in cluster i are smaller than
+those in cluster i+1; this is the case if the first grouping attribute
+(column/BAT) is sorted --- and resorted to "local scanning" rather than
+(inherently random and expensive) hash-lookups.
+Lacking a suitable and efficient way to detect that the tail of the group
+map (g) is "almost sorted" or "mostly ascending", we require that the tail
+of the group map (g) is sorted --- the "local scanning" performs much worse
+than hash-lookups in case the tail of the group map (g) is in random order.
@h
#define MERGE_aggr_init \
BUN _i = 0, _j = BATcount(bn), _r = BUNfirst(bn); \
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr_be_avg.mx
--- a/MonetDB5/src/modules/kernel/aggr_be_avg.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_be_avg.mx Mon Jul 05 09:46:39
2010 +0200
@@ -236,7 +236,7 @@
} else {
@:aggrX3_avg(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,@2,b...@2(bni,r),r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(b)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe
MonetDB5/src/modules/kernel/aggr_be_count.mx
--- a/MonetDB5/src/modules/kernel/aggr_be_count.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_be_count.mx Mon Jul 05 09:46:39
2010 +0200
@@ -232,7 +232,7 @@
} else {
@:aggrX3_count(0,0,SCANfndOID,loc,BUNhloc(bi,p),BUNtloc(bni,r))@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(b)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe
MonetDB5/src/modules/kernel/aggr_be_minmax.mx
--- a/MonetDB5/src/modules/kernel/aggr_be_minmax.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_be_minmax.mx Mon Jul 05 09:46:39
2010 +0200
@@ -293,7 +293,7 @@
} else {
@:aggrx3_minm...@5(@2,0,SCANfndOID,loc,BUNhloc(bi,p),@3,@4,r-off,@6)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(b)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr_be_prod.mx
--- a/MonetDB5/src/modules/kernel/aggr_be_prod.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_be_prod.mx Mon Jul 05 09:46:39
2010 +0200
@@ -234,7 +234,7 @@
} else {
@:aggrX3_prod(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,@2,b...@2(bni,r),@3,r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(b)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr_be_sum.mx
--- a/MonetDB5/src/modules/kernel/aggr_be_sum.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_be_sum.mx Mon Jul 05 09:46:39
2010 +0200
@@ -232,7 +232,7 @@
} else {
@:aggrX3_sum(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,@2,b...@2(bni,r),@3,r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(b)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr_bge_avg.mx
--- a/MonetDB5/src/modules/kernel/aggr_bge_avg.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_bge_avg.mx Mon Jul 05 09:46:39
2010 +0200
@@ -279,7 +279,7 @@
} else {
@:aggrX3_avg3(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,@2,b...@2(bni,r),r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(g)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe
MonetDB5/src/modules/kernel/aggr_bge_count.mx
--- a/MonetDB5/src/modules/kernel/aggr_bge_count.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_bge_count.mx Mon Jul 05 09:46:39
2010 +0200
@@ -268,7 +268,7 @@
} else {
@:aggrX3_count3(0,0,SCANfndOID,loc,BUNhloc(bi,p),BUNtloc(bni,r))@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(g)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe
MonetDB5/src/modules/kernel/aggr_bge_minmax.mx
--- a/MonetDB5/src/modules/kernel/aggr_bge_minmax.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_bge_minmax.mx Mon Jul 05 09:46:39
2010 +0200
@@ -361,7 +361,7 @@
} else {
@:aggrx3_minma...@5(@2,0,SCANfndOID,loc,BUNhloc(bi,p),@3,@4,r-off,@6)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(g)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe
MonetDB5/src/modules/kernel/aggr_bge_prod.mx
--- a/MonetDB5/src/modules/kernel/aggr_bge_prod.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_bge_prod.mx Mon Jul 05 09:46:39
2010 +0200
@@ -320,7 +320,7 @@
} else {
@:aggrX3_prod3(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,BUNtloc(bni,r),if (w >= base
&& w < end),@2,r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(g)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
diff -r 1d6478c072b6 -r 432db0aba3fe MonetDB5/src/modules/kernel/aggr_bge_sum.mx
--- a/MonetDB5/src/modules/kernel/aggr_bge_sum.mx Mon Jul 05 08:20:48
2010 +0200
+++ b/MonetDB5/src/modules/kernel/aggr_bge_sum.mx Mon Jul 05 09:46:39
2010 +0200
@@ -316,7 +316,7 @@
} else {
@:aggrX3_sum3(0,0,SCANfndOID,loc,BUNhloc(bi,p),@1,BUNtloc(bni,r),if (w >= base
&& w < end),@2,r-off)@
}
- } else if (BAThordered(e)&1) {
+ } else if (BATtordered(g)&BAThordered(e)&1) {
/* merge lookup */
MERGE_aggr_init;
if (BAThdense(b)) {
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
