Changeset: 49e9e337efef for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=49e9e337efef
Modified Files:
gdk/gdk_firstn.c
monetdb5/modules/mal/Tests/pqueue3.stable.out
monetdb5/tests/gdkTests/Tests/firstn.stable.out
Branch: Oct2014
Log Message:
Optimize for the case that the input bat is nearly sorted in ascending order.
It is probably a common use case that the input bat is "almost"
sorted in ascending order, so we will optimize for this. If the bat
is in random order, the optimization doesn't help but also doesn't
hinder. If the bat happens to be almost ordered in descending order,
we loose out when asking for the first n. But we don't expect that to
happen often.
Suggested by Richard Hughes.
diffs (109 lines):
diff --git a/gdk/gdk_firstn.c b/gdk/gdk_firstn.c
--- a/gdk/gdk_firstn.c
+++ b/gdk/gdk_firstn.c
@@ -212,12 +212,28 @@ BATfirstn_unique(BAT *b, BAT *s, BUN n,
/* note, this takes care of types oid and wrd */
tpe = ATOMstorage(tpe);
}
+ /* if the input happens to be almost sorted in ascending order
+ * (likely a common use case), it is more efficient to start
+ * off with the first n elements when doing a firstn-ascending
+ * and to start off with the last n elements when doing a
+ * firstn-descending so that most values that we look at after
+ * this will be skipped. */
if (cand) {
- for (i = 0; i < n; i++)
- oids[i] = *cand++;
+ if (asc) {
+ for (i = 0; i < n; i++)
+ oids[i] = *cand++;
+ } else {
+ for (i = 0; i < n; i++)
+ oids[i] = *--candend;
+ }
} else {
- for (i = 0; i < n; i++)
- oids[i] = start++ + b->hseqbase;
+ if (asc) {
+ for (i = 0; i < n; i++)
+ oids[i] = start++ + b->hseqbase;
+ } else {
+ for (i = 0; i < n; i++)
+ oids[i] = --end + b->hseqbase;
+ }
}
if (asc) {
switch (tpe) {
diff --git a/monetdb5/modules/mal/Tests/pqueue3.stable.out
b/monetdb5/modules/mal/Tests/pqueue3.stable.out
--- a/monetdb5/modules/mal/Tests/pqueue3.stable.out
+++ b/monetdb5/modules/mal/Tests/pqueue3.stable.out
@@ -148,13 +148,13 @@ end main;
# h t # name
# void oid # type
#--------------------------#
-[ 0@0, 2@0 ]
+[ 0@0, 6@0 ]
#--------------------------#
# h t # name
# void oid # type
#--------------------------#
[ 0@0, 2@0 ]
-[ 1@0, 3@0 ]
+[ 1@0, 6@0 ]
#--------------------------#
# h t # name
# void oid # type
diff --git a/monetdb5/tests/gdkTests/Tests/firstn.stable.out
b/monetdb5/tests/gdkTests/Tests/firstn.stable.out
--- a/monetdb5/tests/gdkTests/Tests/firstn.stable.out
+++ b/monetdb5/tests/gdkTests/Tests/firstn.stable.out
@@ -629,36 +629,36 @@ end main;
# h t # name
# void oid # type
#--------------------------#
-[ 0@0, 0@0 ]
-[ 1@0, 1@0 ]
-[ 2@0, 3@0 ]
+[ 0@0, 1@0 ]
+[ 1@0, 3@0 ]
+[ 2@0, 5@0 ]
[ 3@0, 6@0 ]
#--------------------------#
# h t # name
# void str # type
#--------------------------#
-[ 0@0, "2" ]
+[ 0@0, "3" ]
[ 1@0, "3" ]
-[ 2@0, "3" ]
+[ 2@0, "2" ]
[ 3@0, "3" ]
#--------------------------#
# h t # name
# void oid # type
#--------------------------#
-[ 0@0, 0@0 ]
-[ 1@0, 1@0 ]
-[ 2@0, 3@0 ]
-[ 3@0, 5@0 ]
-[ 4@0, 6@0 ]
+[ 0@0, 1@0 ]
+[ 1@0, 3@0 ]
+[ 2@0, 5@0 ]
+[ 3@0, 6@0 ]
+[ 4@0, 7@0 ]
#--------------------------#
# h t # name
# void str # type
#--------------------------#
-[ 0@0, "2" ]
+[ 0@0, "3" ]
[ 1@0, "3" ]
-[ 2@0, "3" ]
-[ 3@0, "2" ]
-[ 4@0, "3" ]
+[ 2@0, "2" ]
+[ 3@0, "3" ]
+[ 4@0, "2" ]
#--------------------------#
# h t # name
# void oid # type
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
