Changeset: ce20681a7944 for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=ce20681a7944 Modified Files: monetdb5/extras/bwd/operations.c monetdb5/extras/bwd/utilities.c monetdb5/extras/bwd/utilities.h Branch: bwd Log Message:
* fixed false positive/negative problems
turns out the bounds were the problem but not the way I thought (see
commit b81fe596630b): the prefix-compression offset was not taken into account
Unterschiede (gekürzt von 330 auf 300 Zeilen):
diff --git a/monetdb5/extras/bwd/operations.c b/monetdb5/extras/bwd/operations.c
--- a/monetdb5/extras/bwd/operations.c
+++ b/monetdb5/extras/bwd/operations.c
@@ -164,6 +164,7 @@ str BWDLeftJoinApproximate(bat * res, ba
BATsetprop(result, batRegistryIndex, TYPE_int,
(int[]){newIndex});
slot->approximationBits =
batTailApproximationBits(right);
slot->tailOffsetBits = batTailOffsetBits(right);
+ slot->tailOffsetValue = batTailOffsetValue(right);
slot->residuals = NULL;
slot->tailPositions = leftColumn;
if(CL_REFCOUNT_DEBUG) printf ("retaining %p\n",
leftColumn);
@@ -336,6 +337,7 @@ static inline str uselect(bat *res, bat
BATsetprop(result, batRegistryIndex, TYPE_int,
(int[]){newIndex});
slot->approximationBits =
batTailApproximationBits(data);
slot->tailOffsetBits = batTailOffsetBits(data);
+ slot->tailOffsetValue =
batTailOffsetValue(data);
slot->residuals = NULL;
slot->tailApproximation =
bwdClCreateBuffer(getCLContext(), CL_MEM_READ_WRITE,
MIN(dataCount,MAX_INTERMEDIATE_RESULT_SIZE)*slot->approximationBits/8+sizeof(clTail),
NULL, &err);
if(err) printf("#%s, bwdClCreateBuffer: %s;\n",
__func__, clError(err));
@@ -373,9 +375,11 @@ static inline str uselect(bat *res, bat
}
{
+ int base = batTailOffsetValue(data);
const int parameters[2] = {
-
((((*(int*)val)>>batTailResidualBits(data))<<batTailResidualBits(data)) -
(OP[1]=='='?(1<<batTailResidualBits(data)):0)),
-
val2?((((*(int*)val2)>>batTailResidualBits(data))<<batTailResidualBits(data)) +
(OP2[1]=='='?(1<<batTailResidualBits(data)):0)):0};
+
(((((*(int*)val)-base)>>batTailResidualBits(data))<<batTailResidualBits(data))
+ base),
+
val2?(((((*(int*)val2)-base)>>batTailResidualBits(data))<<batTailResidualBits(data))
+ base):0};
+ printf ("relaxed conditions from (%d,
%d) to (%d, %d)\n", *(int*)val, *(int*)val2, parameters[0], parameters[1]);
int i;
for (i = 0; i < 2; ++i)
if((err =
clSetKernelArg(selectKernel, bufferI+i, sizeof(int), &(parameters[i])))) //
type specific
@@ -413,87 +417,108 @@ str BWDThetauselectApproximate(bat *res,
return uselect(res, bid, val, *OP, 0, NULL, context);
}
-static inline unsigned int refinementLoop(str OP, str OP2, const int value1,
const int value2, size_t candidateCount,
-
clHead* compressedHead,
clTail* compressedTail, const unsigned char* residuals,
-
const int
tailApproximationBytes, const int tailResidualBits,
-
oid* positionRegion){
-/* use cpp | egrep -v "^#" | indent to expand */
-
+static inline unsigned int refinementLoop(str OP, str OP2, const int value1,
const int value2, const size_t candidateCount,
+
const clHead* compressedHead, const clTail* compressedTail, const
unsigned char* residuals, const oid* inputPositions,
+
const int tailApproximationBytes, const int tailResidualBits,
+
oid* positionRegion){
+/* use cpp | egrep -v "^#" | indent | pbcopy to expand */
const int tailApproximationMask = (1<<(tailApproximationBytes*8))-1;
const unsigned int residualMask = (1 << tailResidualBits)-1;
const unsigned int residualBytes = tailResidualBits/8;
- unsigned int i, j;
-#define refineLoopDoubleOperator(comparator, comparator2)
\
+ unsigned int i=0, j=0, inputPositionsI = 0;
+#define refineLoopDoubleOperator(comparator, comparator2,
positionIsTruePositiveCondition, residualPosition) \
while(i < candidateCount) {
\
- const int index = compressedHead->positions[i];
\
- const int offset = tailApproximationBytes*i++;
\
+ const unsigned int index = compressedHead->positions[i];
\
+ const int offset = tailApproximationBytes*i;
\
const int compressedValue =
*(int*)&(compressedTail->elements[offset]) & tailApproximationMask; \
const int deCompressedValue = compressedTail->base+
\
(compressedValue << tailResidualBits)
\
- + (*(int*)&residuals[i*residualBytes] & residualMask);
\
+ + (*(unsigned
int*)&residuals[residualPosition*residualBytes] & residualMask); \
{
\
+ const int positionIsCorrectPositive =
\
+ (positionIsTruePositiveCondition);
\
positionRegion[j] = index;
\
j+= ((deCompressedValue comparator value1) &
\
- (deCompressedValue comparator2
value2));
\
+ (deCompressedValue comparator2 value2)
&
\
+ (positionIsCorrectPositive));
\
+ inputPositionsI += positionIsCorrectPositive;
\
+ i++;
\
}
\
}
-#define refineLoopSingleOperator(comparator)
\
+#define refineLoopSingleOperator(comparator, positionIsTruePositiveCondition,
residualPosition) \
while(i < candidateCount) {
\
- const unsigned int index = compressedHead->positions[i];
\
- const unsigned int offset = (tailApproximationBytes)*i++;
\
- const int compressedValue =
*(int*)&(compressedTail->elements[offset]) & tailApproximationMask; \
- const int deCompressedValue = compressedTail->base+
\
- (compressedValue << tailResidualBits)
\
- + (*(int*)&residuals[index*residualBytes] &
residualMask); \
- if(deCompressedValue comparator value1) {
\
- positionRegion[j++] = index;
\
+ const unsigned int index = compressedHead->positions[i];
\
+ const unsigned int offset = (tailApproximationBytes)*i;
\
+ const int compressedValue = *(int*)&(compressedTail->elements[offset])
& tailApproximationMask; \
+ const int deCompressedValue = compressedTail->base+
\
+ (compressedValue << tailResidualBits)
\
+ + (*(unsigned int*)&residuals[residualPosition*residualBytes] &
residualMask); \
+ {
\
+ const int positionIsCorrectPositive =
\
+ (positionIsTruePositiveCondition);
\
+ positionRegion[j] = index;
\
+ j += ((deCompressedValue comparator value1) &
\
+ (positionIsCorrectPositive));
\
+ inputPositionsI += positionIsCorrectPositive;
\
+ i++;
\
+}
\
+}
+#define refineLoop(comparator, comparator2, positionIsTruePositiveCondition,
residualPosition) \
+ if(comparator2 == NULL) {
\
+ refineLoopSingleOperator(comparator,
positionIsTruePositiveCondition, residualPosition); \
+ } else {
\
+ switch (comparator2[0]){
\
+ case '<':
\
+ switch((comparator2)[1]){
\
+ case '\0':
\
+ refineLoopDoubleOperator(comparator, <,
positionIsTruePositiveCondition, residualPosition); \
+ case '=':
\
+ refineLoopDoubleOperator(comparator, <=,
positionIsTruePositiveCondition, residualPosition); \
+ }
\
+ case '>':
\
+ switch((comparator2)[1]){
\
+ case '\0':
\
+ refineLoopDoubleOperator(comparator, >,
positionIsTruePositiveCondition, residualPosition); \
+ case '=':
\
+ refineLoopDoubleOperator(comparator, <=,
positionIsTruePositiveCondition, residualPosition); \
+ }
\
+ case '=':
\
+ refineLoopDoubleOperator(comparator, ==,
positionIsTruePositiveCondition, residualPosition); \
}
\
}
-#define refineLoop(comparator, comparator2) \
- if(comparator2 == NULL) {
\
- refineLoopSingleOperator(comparator);
\
- } else {
\
- switch (comparator2[0]){
\
- case '<':
\
- switch((comparator2)[1]){
\
- case '\0':
\
- refineLoopDoubleOperator(comparator, <);
\
- case '=':
\
- refineLoopDoubleOperator(comparator, <=);
\
- }
\
- case '>':
\
- switch((comparator2)[1]){
\
- case '\0':
\
- refineLoopDoubleOperator(comparator, >);
\
- case '=':
\
- refineLoopDoubleOperator(comparator, <=);
\
- }
\
- case '=':
\
- refineLoopDoubleOperator(comparator, ==);
\
- }
\
- }
switch (OP[0]){
- case '<':
- switch(OP[1]){
- case '\0':
- refineLoop(<, OP2);
- case '=':
- refineLoop(<=, OP2);
- }
- case '>':
- switch(OP[1]){
- case '\0':
- refineLoop(>, OP2);
- case '=':
- refineLoop(>=, OP2);
- }
- case '=':
- refineLoop(==, OP2);
- }
+case '<':
+ switch(OP[1]){
+case '\0': {
+ if(inputPositions == NULL) { refineLoop(<, OP2, 1, index);}
+ else { refineLoop(<, OP2, (index == inputPositions[inputPositionsI]),
inputPositionsI) };
+}
+case '=': {
+ if(inputPositions == NULL) {refineLoop(<=, OP2, 1, index);}
+ else {refineLoop(<=, OP2, (index == inputPositions[inputPositionsI]),
inputPositionsI)};
+}
+}
+case '>':
+ switch(OP[1]){
+case '\0': {
+ if(inputPositions == NULL) {refineLoop(>, OP2, 1, index);}
+ else {refineLoop(>, OP2, (index == inputPositions[inputPositionsI]),
inputPositionsI)};
+}
+case '=': {
+ if(inputPositions == NULL) {refineLoop(>=, OP2, 1, index);}
+ else {refineLoop(>=, OP2, (index == inputPositions[inputPositionsI]),
inputPositionsI)};
+}
+}
+case '=': {
+ if(inputPositions == NULL) {refineLoop(==, OP2, 1, index);}
+ else {refineLoop(==, OP2, (index == inputPositions[inputPositionsI]),
inputPositionsI)};
+}
+}
#undef refineLoop
#undef refineLoopSingleOperator
#undef refineLoopDoubleOperator
return j;
+
}
str uselectrefine(bat *res, bat *bid, ptr val, str OP, ptr val2, str OP2, bat
*approx, Client context) {
@@ -557,12 +582,12 @@ str uselectrefine(bat *res, bat *bid, pt
{
unsigned int j =
refinementLoop(OP, OP2, *(int*)val, val2?*(int*)val2:0, candidateCount,
-
compressedHead, compressedTail, residuals,
-
batTailApproximationBits(approximation)/8 -
batTailOffsetBits(approximation)/8,
-
batTailResidualBits(approximation),
-
positionRegion);
+
compressedHead, compressedTail, residuals, (oid*) Hloc(data,
BUNfirst(data)),
+
batTailApproximationBits(approximation)/8 -
batTailOffsetBits(approximation)/8,
+
batTailResidualBits(approximation),
+
positionRegion);
- printf ("%s reduced the result
from %zd to %d\n", __func__, candidateCount, j);
+ if(0) printf ("%s reduced the
result from %zd to %d\n", __func__, Hloc(data,
BUNfirst(data))?MIN(candidateCount, BATcount(data)):candidateCount, j);
BATsetcount(result, j);
}
BATseqbase(BATmirror(result), oid_nil);
@@ -661,6 +686,7 @@ str BWDSemijoinApproximate(int *res, int
BATsetprop(result, batRegistryIndex, TYPE_int,
(int[]){newIndex});
slot->approximationBits =
batTailApproximationBits(left);
slot->tailOffsetBits = batTailOffsetBits(left);
+ slot->tailOffsetValue =
batTailOffsetValue(left);
slot->residuals = NULL;
slot->tailPositions = positionColumn;
slot->headApproximation = positionColumn;
@@ -764,18 +790,35 @@ str BWDSemijoinRefine(int *res, int *lid
int* refinementRegion = (int*)
Tloc(refinement, BUNfirst(refinement));
const unsigned char* residuals
= batTailResiduals(left);
const unsigned int
residualBytes = Tsize(left)-approximationBits/8;
+
+ const unsigned int residualMask
= (1 << (32-approximationBits))-1;
+
if(residualBytes > 0){
unsigned int i,j;
size_t refinementCount
= 0;
filteredResiduals =
calloc((supersetPositionsColumn->count)*residualBytes + sizeof(size_t), 1);
-
- for ( i = j = 0; j <
BATcount(right); ++j) {
-
while(supersetPositionsColumn->positions[i] != ((oid*)right->H->heap.base)[j])
- i++;
-
refinementRegion[refinementCount++] = decompressIntValue(i, approximationBits,
offsetBits, supersetApproximateValuesColumn, residuals,
supersetPositionsColumn->positions[i]);
+ {
+#define projectResidualsLoop(residualPosition)
\
+ for ( i = j =
0; j < BATcount(right); ++j) { \
+
while(supersetPositionsColumn->positions[i]
\
+
!= ((oid*)right->H->heap.base)[j])
\
+
i++;
\
+
filteredResiduals[refinementCount] |=
\
+
(*(int*)&residuals[residualPosition*residualBytes] & residualMask); \
+
refinementRegion[refinementCount++] =
\
+
decompressIntValue(i, approximationBits,
\
+
offsetBits, supersetApproximateValuesColumn, \
+
residuals, supersetPositionsColumn->positions[i]); \
}
- BATsetcount(refinement,
refinementCount);
+ if
(BAThdense(left)) { // dense headed but, thus we use the positions for residual
lookups
+
projectResidualsLoop(supersetPositionsColumn->positions[i]);
+ } else { // bat
is oid-headed, thus we use the iterator
+
projectResidualsLoop(i)
+ }
+#undef projectResidualsLoop
+ }
+ BATsetcount(refinement,
refinementCount);
} else {
const int count =
BATcount(right);
diff --git a/monetdb5/extras/bwd/utilities.c b/monetdb5/extras/bwd/utilities.c
--- a/monetdb5/extras/bwd/utilities.c
+++ b/monetdb5/extras/bwd/utilities.c
@@ -235,6 +235,15 @@ const char* batRegistryIndex = "bwd.batR
return
bwdRegistry[rightTailApproximationProperty->v.val.ival].tailOffsetBits;
}
+int batTailOffsetValue(const BAT* subject){
+ PROPrec* rightTailApproximationProperty;
+ if(!(rightTailApproximationProperty = BATgetprop(subject,
batRegistryIndex))){
+ if(0) printf("%s: bat hasn't been decomposed;\n",
__func__);
+ return 0;
+ }
+ return
bwdRegistry[rightTailApproximationProperty->v.val.ival].tailOffsetValue;
+}
+
int isPersistentBAT(const BAT* subject){
PROPrec* rightTailApproximationProperty;
if(!(rightTailApproximationProperty = BATgetprop(subject,
batRegistryIndex))){
@@ -338,7 +347,8 @@ unsigned int decomposeIntArray(const int
printf ("using %s for approximation and %s for residuals \n",
humanreadablesize(approximationBytes*(size+1)+ sizeof(clTail), alloca(64), 64),
humanreadablesize(residualBytes*(size+1), alloca(64), 64));
slot->residuals = calloc((size+1)*residualBytes, sizeof(char));
- approximation->base = subjectBounds.min;
+ approximation->base = subjectBounds.min;
+ slot->tailOffsetValue = approximation->base;
approximation->count = size;
for (i = 0; i < size; ++i){
_______________________________________________
checkin-list mailing list
[email protected]
https://www.monetdb.org/mailman/listinfo/checkin-list
