Update of /cvsroot/monetdb/MonetDB5/src/modules/kernel
In directory sc8-pr-cvs16.sourceforge.net:/tmp/cvs-serv15857/src/modules/kernel
Modified Files:
algebra.mx bat5.mx batcalc.mx calc.mx counters.mx group.mx
logger.mx mkey.mx
Log Message:
propagated changes of Sunday Feb 03 2008 - Friday Feb 08 2008
from the MonetDB_5-4 branch to the development trunk
Index: calc.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/calc.mx,v
retrieving revision 1.70
retrieving revision 1.71
diff -u -d -r1.70 -r1.71
--- calc.mx 16 Jan 2008 11:27:35 -0000 1.70
+++ calc.mx 8 Feb 2008 22:36:32 -0000 1.71
@@ -47,7 +47,7 @@
An error message is given when the input value is zero.
@item [bitwise operators]
-For integers there are some additional operations. The @emph{\%} operator
+For integers there are some additional operations. The @emph{%} operator
implements the congruent modulo operation. The @emph{<<} and @emph{>>}
are the left and right bit shift. The @emph{or}, @emph{and}, @emph{xor} and
@emph{not} for integers are implemented as bitwise boolean operations.
Index: bat5.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/bat5.mx,v
retrieving revision 1.28
retrieving revision 1.29
diff -u -d -r1.28 -r1.29
--- bat5.mx 11 Jan 2008 10:41:35 -0000 1.28
+++ bat5.mx 8 Feb 2008 22:36:31 -0000 1.29
@@ -1804,22 +1804,22 @@
@T
The XML node storage scheme of MonetDB/XQuery needs some extra kernel support.
-\begin{itemize}
-\item
[EMAIL PROTECTED]
[EMAIL PROTECTED]
we introduce a fast way to create BATs with the VM pages in a different order
(to cheaply support inserting new pages halfway).
-\item
[EMAIL PROTECTED]
for other bats, there is a new rcopy(), that copies large heaps using
copy-on-write memory maps. This is also done for string heaps, if they are
no longer double eliminated.
-\item
[EMAIL PROTECTED]
we introduce a primitive to swizzle OIDs for such remappings between RIDs
(the real
voids on disk) and PREs (the voids of the remapped copy).
-\item
[EMAIL PROTECTED]
we introduce 'isolate()' a primitive that executes a number of idempotent
updates
on a bat, such that all modified logical pages have received physical page
copies (transparently by the MMU page faults it generates).
-\end{itemize}
[EMAIL PROTECTED] itemize
Also, we use copy-on-write maps for transaction isolation. Contrary to
intuition, we
write into STORE_MMAP read-only master bats (overriding the read-only
protection
@@ -1840,26 +1840,26 @@
other changes were:
-\begin{itemize}
-\item
+@ itemize
[EMAIL PROTECTED]
gdk_bat.mx/gdk_batop.mx: a 'force' flag in update operations that allow to
update
read-only/append-only BATs anyway. Note that if used, another (WAL-based)
recovery
mechanism must be used to repair BATs after a system crash!! This is a user
respsonability (in this case, of the MonetDB/XQuery frontend).
-\item
[EMAIL PROTECTED]
gdk_bat.mx: make a true copy of remapped/rcopied BUN heaps if the bat
becomes persistent
or updatable.
-\item
[EMAIL PROTECTED]
gdk_batop.mx: optimized fetchjoin for idempotent positional joins (into a
bat[void,void]
with equal seqbase and all tuples hitting). To keep semantics consistent, it
is now
an error if a fetchjoin is performed with a key that is out-of-range.
Everything *must* match!
-\item
[EMAIL PROTECTED]
gdk_storage.mx: batload. To preserve the integritry of string heaps with
such forced updates,
the kernel zaps the internal hash table of string heaps. Note that this is
only allowed if
double-elimination inside the string heap is disabled (in that case the hash
table is not
required to be complete). To prevent problems, the rcopy() does not do
mmap-tricks for
double-eliminating heaps.
-\end{itemize}
[EMAIL PROTECTED] itemize
In swizzling as well as in positional join, specific optimizations are made for
the common case where all pages appear in order (this occurs in XML tables
that have
Index: batcalc.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/batcalc.mx,v
retrieving revision 1.148
retrieving revision 1.149
diff -u -d -r1.148 -r1.149
--- batcalc.mx 11 Jan 2008 10:41:35 -0000 1.148
+++ batcalc.mx 8 Feb 2008 22:36:31 -0000 1.149
@@ -52,7 +52,7 @@
being. If it turns out to be effective, we will derive a new
version of batcalc.
-Experiments show that ignoring the NULLS saves about 15\%
+Experiments show that ignoring the NULLS saves about 15%
for larger instructions.
@{
@mal
@@ -517,7 +517,18 @@
} else {
@:accumCst(@3,@1,@4,@5)@
}
- bn->tsorted = 0;
+ if (@6 == 2)
+ bn->tsorted = BATtordered(b);
+#if @7
+ else if (@6 == 3) {
+ if (*(@5*)cst >= 0)
+ bn->tsorted = BATtordered(b);
+ else
+ bn->tsorted = REVERT_SORTED(BATtordered(b));
+ }
+#endif
+ else
+ bn->tsorted = 0;
BATkey(BATmirror(bn),FALSE);
BBPkeepref(*ret = bn->batCacheid);
@@ -540,7 +551,18 @@
} else {
@:accumCstLeft(@3,@1,@4,@5)@
}
- bn->tsorted = 0;
+ if (@6 == 2)
+ bn->tsorted = BATtordered(b);
+#if @7
+ else if (@6 == 3) {
+ if (*(@4*)cst >= 0)
+ bn->tsorted = BATtordered(b);
+ else
+ bn->tsorted = REVERT_SORTED(BATtordered(b));
+ }
+#endif
+ else
+ bn->tsorted = 0;
BATkey(BATmirror(bn),FALSE);
BBPkeepref(*ret = bn->batCacheid);
@@ -567,7 +589,18 @@
@:accumCst(@3,@1,@4,@5)@
}
BATsetcount(bn, BATcount(b));
- bn->tsorted = 0;
+ if (@6 == 2)
+ bn->tsorted = BATtordered(b);
+#if @7
+ else if (@6 == 3) {
+ if (*(@5*)cst >= 0)
+ bn->tsorted = BATtordered(b);
+ else
+ bn->tsorted = REVERT_SORTED(BATtordered(b));
+ }
+#endif
+ else
+ bn->tsorted = 0;
BATkey(BATmirror(bn),FALSE);
if (!(bn->batDirty&2)) bn = BATsetaccess(bn, BAT_READ);
@@ -597,7 +630,18 @@
@:accumCstLeft(@3,@1,@4,@5)@
}
BATsetcount(bn, BATcount(b));
- bn->tsorted = 0;
+ if (@6 == 2)
+ bn->tsorted = BATtordered(b);
+#if @7
+ else if (@6 == 3) {
+ if (*(@5*)cst >= 0)
+ bn->tsorted = BATtordered(b);
+ else
+ bn->tsorted = REVERT_SORTED(BATtordered(b));
+ }
+#endif
+ else
+ bn->tsorted = 0;
BATkey(BATmirror(bn),FALSE);
if (!(bn->batDirty&2)) bn = BATsetaccess(bn, BAT_READ);
@@ -617,32 +661,32 @@
#include "batcalc.h"
@= arithGrpImpl
-@:arithmeticImpl(@1,@2,flt,flt,flt)@
-@:arithmeticImpl(@1,@2,dbl,dbl,dbl)@
-@:arithmeticImpl(@1,@2,oid,oid,oid)@
+@:arithmeticImpl(@1,@2,flt,flt,flt,@3,1)@
+@:arithmeticImpl(@1,@2,dbl,dbl,dbl,@3,1)@
+@:arithmeticImpl(@1,@2,oid,oid,oid,@3,0)@
-@:arithmeticImpl(@1,@2,int,int,sht)@
-@:arithmeticImpl(@1,@2,int,sht,int)@
-@:arithmeticImpl(@1,@2,int,sht,sht)@
-@:arithmeticImpl(@1,@2,sht,sht,sht)@
+@:arithmeticImpl(@1,@2,int,int,sht,@3,1)@
+@:arithmeticImpl(@1,@2,int,sht,int,@3,1)@
+@:arithmeticImpl(@1,@2,int,sht,sht,@3,1)@
+@:arithmeticImpl(@1,@2,sht,sht,sht,@3,1)@
-@:arithmeticImpl(@1,@2,lng,lng,lng)@
-@:arithmeticImpl(@1,@2,lng,sht,lng)@
-@:arithmeticImpl(@1,@2,lng,lng,sht)@
-@:arithmeticImpl(@1,@2,lng,sht,sht)@
-@:arithmeticImpl(@1,@2,lng,sht,int)@
-@:arithmeticImpl(@1,@2,lng,int,sht)@
-@:arithmeticImpl(@1,@2,lng,int,lng)@
-@:arithmeticImpl(@1,@2,lng,lng,int)@
+@:arithmeticImpl(@1,@2,lng,lng,lng,@3,1)@
+@:arithmeticImpl(@1,@2,lng,sht,lng,@3,1)@
+@:arithmeticImpl(@1,@2,lng,lng,sht,@3,1)@
+@:arithmeticImpl(@1,@2,lng,sht,sht,@3,1)@
+@:arithmeticImpl(@1,@2,lng,sht,int,@3,1)@
+@:arithmeticImpl(@1,@2,lng,int,sht,@3,1)@
+@:arithmeticImpl(@1,@2,lng,int,lng,@3,1)@
+@:arithmeticImpl(@1,@2,lng,lng,int,@3,1)@
-@:arithmeticImpl(@1,@2,lng,int,int)@
-@:arithmeticImpl(@1,@2,int,int,int)@
+@:arithmeticImpl(@1,@2,lng,int,int,@3,1)@
+@:arithmeticImpl(@1,@2,int,int,int,@3,1)@
@c
-@:arithGrpImpl(/,DIV)@
-@:arithGrpImpl(*,MUL)@
-@:arithGrpImpl(-,SUB)@
-@:arithGrpImpl(+,ADD)@
+@:arithGrpImpl(/,DIV,0)@
+@:arithGrpImpl(*,MUL,3)@
+@:arithGrpImpl(-,SUB,2)@
+@:arithGrpImpl(+,ADD,2)@
@- Modulo arithmetic
The Modulo function doesn;t work on all types. Therefore we
Index: algebra.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/algebra.mx,v
retrieving revision 1.192
retrieving revision 1.193
diff -u -d -r1.192 -r1.193
--- algebra.mx 11 Jan 2008 10:41:35 -0000 1.192
+++ algebra.mx 8 Feb 2008 22:36:31 -0000 1.193
@@ -246,9 +246,13 @@
@+ Set operations
Sets in Monet can be viewed in two ways:
-(1) by looking at both columns of a BAT together (Set-, or s-operators).
-(2) by looking at the head column only (Key- or k-operators).
-(3) by looking at the tail column only (Tail key- or t-operators).
[EMAIL PROTECTED]
[EMAIL PROTECTED]
+by looking at both columns of a BAT together (Set-, or s-operators).
[EMAIL PROTECTED]
+by looking at the head column only (Key- or k-operators).
+by looking at the tail column only (Tail key- or t-operators).
[EMAIL PROTECTED] itemize
For this reason, all standard set operations come in three flavors:
[EMAIL PROTECTED] series, which look only at the head column,
[EMAIL PROTECTED] series, which look only at the tail column, and
@@ -267,14 +271,14 @@
@end itemize
Implementations typically take two forms: if the input relation(s) is/are
ordered, a merge-algorithm is used. Otherwise, hash-indices are produced
-on demand for the hash-based [EMAIL PROTECTED]
+on demand for the hash-based algorithms.
The [k,s]intersect(l,r) operations result in all BUNs of @emph{l} that
-are also in @emph{r}. They do not do double-elimination over the @emph{l}
[EMAIL PROTECTED]
+are also in @emph{r}. They do not do double-elimination over the @emph{l} BUNs.
The [k,s]difference(l,r) operations result in all BUNs of @emph{l} that are
-not in @emph{r}. They do not do double-elimination over the @emph{l} [EMAIL
PROTECTED]
-The [k,s]union(l,r) operations result in all BUNs of l that are
-not in @emph{r}, plus all BUNs of @emph{r}. They do not do double-elimination
-over the @emph{l} nor @emph{r} [EMAIL PROTECTED]
+not in @emph{r}. They do not do double-elimination over the @emph{l} BUNs.
+The [k,s]union(l,r) operations result in all BUNs of l, plus all BUNs
+of @emph{r} that are not in @emph{l}. They do not do double-elimination
+over the @emph{l} nor @emph{r} BUNs.
Operations with double-elimination can be formed by performing
[k,s]unique(l) on their operands.
The kintersect(l,r) is used also as implementation for the
@@ -658,7 +662,7 @@
@- Default Min and Max
Implementations a generic Min and Max routines get declared first. The
[EMAIL PROTECTED] min()} and @emph{ max()} routines below catch any tail-type.
[EMAIL PROTECTED]()} and @emph{max()} routines below catch any tail-type.
The type-specific routines defined later are faster, and will
override these any implementations.
@mal
@@ -765,35 +769,36 @@
column (ordered(BAT)). Tail columns can be described by
using the mirror BAT with the minus operator (ordered(-BAT)).
[EMAIL PROTECTED] Column Properties
@table @code
[EMAIL PROTECTED](BAT) :bit]
[EMAIL PROTECTED] [ordered(BAT) :bit]
TRUE if the head column is stored in ascending order, else FALSE.
[EMAIL PROTECTED](BAT) :bit]
[EMAIL PROTECTED] [keyed(BAT) :bit]
TRUE if no duplicates are present in the head column, else FALSE.
[EMAIL PROTECTED](BAT) :bit]
[EMAIL PROTECTED] [idx(BAT) :bit]
TRUE if a binary index tree search accelerator is present on
the head column of the BAT, else FALSE.
[EMAIL PROTECTED](BAT) :bit]
- presence of hash table on the head column of
- a BAT. TRUE if a bucket-chained hash table search accelerator is
- present on the head column of the BAT, else FALSE.
[EMAIL PROTECTED](BAT, BAT) :bit]
[EMAIL PROTECTED] [hashtab(BAT) :bit]
+ presence of hash table on the head column of
+ a BAT. TRUE if a bucket-chained hash table search accelerator is
+ present on the head column of the BAT, else FALSE.
[EMAIL PROTECTED] [subcol(BAT, BAT) :bit]
TRUE if the bag of all values in the head column of the left BAT is
a bag-subset of the bag of all values in the head column of the
right BAT, else FALSE.
[EMAIL PROTECTED](BAT) :oid]
[EMAIL PROTECTED] [sync(BAT) :oid]
Sync-OID on the head column of a BAT. A sync-OID denotes some unique
sequence of values. If two columns have the same sync-OID, then they
are guaranteed to contain the same values, in the same sequence.
[EMAIL PROTECTED](BAT) :int]
[EMAIL PROTECTED] [size(BAT) :int]
The (estimated) length of a column.
[EMAIL PROTECTED](BAT) :int]
[EMAIL PROTECTED] [unique(BAT) :int]
The (estimated) number of distinct values in one column.
[EMAIL PROTECTED](BAT, BAT) :bit]
[EMAIL PROTECTED] [subset(BAT, BAT) :bit]
TRUE if the left BAT is a subset of the BUNs of the right BAT,
else FALSE.
[EMAIL PROTECTED](BAT) :bit]
[EMAIL PROTECTED] [setunique(BAT) :bit]
TRUE if the BAT contains no duplicate BUNs, else FALSE.
@end table
Index: group.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/group.mx,v
retrieving revision 1.105
retrieving revision 1.106
diff -u -d -r1.105 -r1.106
--- group.mx 27 Jan 2008 09:48:22 -0000 1.105
+++ group.mx 8 Feb 2008 22:36:33 -0000 1.106
@@ -40,7 +40,7 @@
schemes at the MAL level.
The prime limitation of the current implementation is that an
-underlying database of @{oid->[EMAIL PROTECTED] BATs is assumed.
+underlying database of @code{oid->any} BATs is assumed.
This enables representation of each group using an oid,
and the value representation of the group can be accordingly be
retrieved easily. An optimized implementation in which we use positional
@@ -70,8 +70,8 @@
to derive a new GRP BAT for the subgroups. After all groups have been
identified this way, a BAT histogram operation can be used to obtain
the counts of each data cube. Other aggregation operations using the MIL
-set aggregate construct @[EMAIL PROTECTED](bat)
-can be used as well; note for instance that histogram == @[EMAIL
PROTECTED](b.reverse()).
+set aggregate construct @[EMAIL PROTECTED]@}(bat)}
+can be used as well; note for instance that @code{histogram == @[EMAIL
PROTECTED](b.reverse())}.
The Monet interface module specification is shown below.
Ideally we should defined stronger type constraints, e.g.
@@ -410,9 +410,9 @@
Values @{standard and [EMAIL PROTECTED],
choosing between a fixed predefined and a custom hashmask. Custom
allows the user to determine the size of the hashmask (and indirectly
-the estimated size of the result). The hashmask is $2^n - 1$ where $n$
+the estimated size of the result). The hashmask is @math{2^n - 1} where
@math{n}
is given by the user, or 1023 otherwise, and the derived result
-size is $4 \cdot 2^n$.
+size is @math{4 @dots{} 2^n}.
@end multitable
Further research should point out whether fitting a simple statistical
Index: logger.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/logger.mx,v
retrieving revision 1.26
retrieving revision 1.27
diff -u -d -r1.26 -r1.27
--- logger.mx 11 Jan 2008 10:41:36 -0000 1.26
+++ logger.mx 8 Feb 2008 22:36:34 -0000 1.27
@@ -30,7 +30,7 @@
The logger uses a directory to store its log files. One master log file
stores information about the version of the logger and the transaction
log files. This file is a simple ascii file with the following format:
- 6DIGIT-VERSION\n[log file number \n]*]*
+ @code{6DIGIT-VERSION\n[log file number \n]*]*}
The transaction log files have a binary format, which stores fixed size
logformat headers (flag,nr,bid), where the flag is the type of update logged.
The nr field indicates how many changes there were (in case of
inserts/deletes).
Index: counters.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/counters.mx,v
retrieving revision 1.23
retrieving revision 1.24
diff -u -d -r1.23 -r1.24
--- counters.mx 11 Jan 2008 10:41:36 -0000 1.23
+++ counters.mx 8 Feb 2008 22:36:33 -0000 1.24
@@ -33,13 +33,10 @@
@itemize
@item @url{http://www.cse.msu.edu/~enbody/perfmon.html,libperfmon } libperfex
(IRIX) for R10000/R12000,
@item (Solaris <= 7) by Richard Enbody, libcpc (Solaris >= 8) for
UltraSparcI/II,
[EMAIL PROTECTED] @[<a href="http://qso.lanl.gov/~mpg/pperf.html";> libpperf
</a>@
-(Linux-i?86 <= 2.2), by M. Patrick Goda and Michael S. Warren,
[EMAIL PROTECTED] @url{http://www.csd.uu.se/~mikpe/linux/perfctr/,libperfctr}
(Linux-i?86 >= 2.4), by M. Pettersson for Pentiums \& Athlons.
[EMAIL PROTECTED] @url{http://user.it.uu.se/~mikpe/linux/perfctr/,libperfctr}
(Linux-i?86 >= 2.4), by M. Pettersson for Pentiums & Athlons.
@item @url{http://www.hpl.hp.com/research/linux/perfmon/, libpfm} (Linux-ia64
>= 2.4), by HP for Itanium[2].
@end itemize
-
Module counters provides similar interface and facilities as Peter's
R10000 perfex module, but it offers no multiplexing of several events;
only two events can be monitored at a time.
Index: mkey.mx
===================================================================
RCS file: /cvsroot/monetdb/MonetDB5/src/modules/kernel/mkey.mx,v
retrieving revision 1.37
retrieving revision 1.38
diff -u -d -r1.37 -r1.38
--- mkey.mx 11 Jan 2008 10:41:36 -0000 1.37
+++ mkey.mx 8 Feb 2008 22:36:34 -0000 1.38
@@ -61,7 +61,7 @@
comment "pre: h and b should be synced on head
post: [:xor=]([:rotate=](h, nbits), [hash](b))";
[EMAIL PROTECTED]
[EMAIL PROTECTED] The Problem
@}
When creating a join, we want to make a unique key of the attributes on both
sides and then join these keys. Consider the following BATs.
@@ -104,7 +104,7 @@
by the command hash(). Hence, we do hash on both sides, and join
that together with a simple join:
-join(hash(keys), hash(keys.reverse);
[EMAIL PROTECTED](hash(keys), hash(keys.reverse);}
One complication of this procedure are nil values:
@table
-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
_______________________________________________
Monetdb-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-checkins
