Changeset: 6a11e98b2a6a for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=6a11e98b2a6a
Modified Files:
monetdb5/extras/crackers/Makefile.ag
monetdb5/extras/crackers/crackers.mx
monetdb5/extras/crackers/crackers_AVL_tree.mx
monetdb5/extras/crackers/opt_selcrackst.mx
Branch: holindex
Log Message:
Changes in the stochastic cracking optimizer.
diffs (truncated from 416 to 300 lines):
diff --git a/monetdb5/extras/crackers/Makefile.ag
b/monetdb5/extras/crackers/Makefile.ag
--- a/monetdb5/extras/crackers/Makefile.ag
+++ b/monetdb5/extras/crackers/Makefile.ag
@@ -40,9 +40,10 @@ lib_crackers = {
crackers_holistic.h \
crackers_selectst_ops.mx \
crackers_selecthol_ops.mx \
+ crackers_updates.mx \
opt_selcrack.mx \
opt_selcrackst.mx \
- opt_selcrackhol.mx
+ opt_selcrackhol.mx
LIBS = ../../tools/libmonetdb5 \
../../../gdk/libbat \
../../../common/stream/libstream \
diff --git a/monetdb5/extras/crackers/crackers.mx
b/monetdb5/extras/crackers/crackers.mx
--- a/monetdb5/extras/crackers/crackers.mx
+++ b/monetdb5/extras/crackers/crackers.mx
@@ -152,6 +152,8 @@ module crackers;
@:TypeSwitch_1(Select)@
@:TypeSwitch_1(Index)@
@:TypeSwitch_1(CoreUnordered)@
+@:TypeSwitch_1(Updates)@
+
#
@= Select
@@ -278,7 +280,71 @@ comment "Retrieve the subset using a cra
index producing preferably a BATview.";
@
+@= Updates
+command insertionsPartiallyForget(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeInsertions_PartiallyForget_@2
+comment "Append c to the cracked BAT of b and partially forget
+ the cracker index, i.e., forget only what is affected";
+command insertionsBForce(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeInsertionsB_Force_@2
+comment "Merge the insertions BAT with the cracker bat and update the cracker
index";
+
+
+command printCrackerInsertions(b:bat[:any_1,:@2]):void
+address CRKprintCrackerInsertions
+comment "Print the pending insertions of the cracker BAT of b";
+
+command printCrackerDeletions(b:bat[:any_1,:@2]):void
+address CRKprintCrackerDeletions
+comment "Print the pending deletions of the cracker BAT of b";
+
+command sizeCrackerInsertions(b:bat[:any_1,:@2]):void
+address CRKsizeCrackerInsertions
+comment "Get the size of the pending insertions of the cracker BAT of b";
+
+command sizeCrackerDeletions(b:bat[:any_1,:@2]):void
+address CRKsizeCrackerDeletions
+comment "Get the size of the pending deletions of the cracker BAT of b";
+
+command insertionsForget(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeInsertions_Forget
+comment "Append c to the cracked BAT of b and completelly forget the cracker
index";
+
+command insertionsBOnNeed(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeInsertionsB_OnNeed
+comment "Keep the insertions BAT separatelly and do a complete merge
+ only if a relevant query arrives in the future";
+
+command insertionsBOnNeedGradually(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeInsertionsB_OnNeedGradually
+comment "Keep the insertions BAT separatelly and merge only what is
+ needed if a relevant query arrives in the future";
+
+command insertionsBOnNeedGraduallyRipple(b:bat[:any_1,:@2],
c:bat[:any_1,:@2]):void
+address CRKmergeInsertionsB_OnNeedGraduallyRipple
+comment "Keep the insertions BAT separatelly and merge only what is needed
+ using the ripple strategy if a relevant query arrives in the future";
+
+command deletionsOnNeed(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeDeletions_OnNeed
+comment "Keep the deletions BAT separatelly and do a complete merge only
+ if a relevant query arrives in the future";
+
+command deletionsOnNeedGradually(b:bat[:any_1,:@2], c:bat[:any_1,:@2]):void
+address CRKmergeDeletions_OnNeedGradually
+comment "Keep the deletions BAT separatelly and merge only what is
+ needed if a relevant query arrives in the future";
+
+command deletionsOnNeedGraduallyRipple(b:bat[:any_1,:@2],
c:bat[:any_1,:@2]):void
+address CRKmergeDeletions_OnNeedGraduallyRipple
+comment "Keep the deletions BAT separatelly and merge only what is
+ needed using ripple if a relevant query arrives in the future";
+
+command extendCrackerBAT(b:bat[:any_1,:@2], P:lng):void
+address CRKextendCrackerBAT
+comment "Extend the cracker column by P positions";
+@
@= Index
command printCrackerIndexBATpart(b:bat[:any_1,:@2]):void
address CRKprintCrackerIndexBATpart
@@ -339,6 +405,7 @@ comment "Break a BAT into three pieces w
#include "crackers_holistic.h"
#include "crackers_core_unordered.h"
#include "crackers_AVL_tree.h"
+#include "crackers_updates.h"
#ifdef LIBCRACKERS
extern int maxCrackMap;
diff --git a/monetdb5/extras/crackers/crackers_AVL_tree.mx
b/monetdb5/extras/crackers/crackers_AVL_tree.mx
--- a/monetdb5/extras/crackers/crackers_AVL_tree.mx
+++ b/monetdb5/extras/crackers/crackers_AVL_tree.mx
@@ -82,6 +82,7 @@ bit GetHghNodes_@1(@1 x, bit inclusive,
struct Node * InsertTree_@1(int m, oid indexPosition, @1 value, bit inclusive,
oid crackPosition, struct Node * current, BAT * b, BUN base, struct Node
**newNode);
struct Node * findNodeH_@1(@1 x, bit inclusive, struct Node * current, BAT
*b, BUN base, struct Node * next);
struct Node * findNodeL_@1(@1 x, bit inclusive, struct Node * current, BAT
*b, BUN base, struct Node * prev);
+void PartiallyLazyFreeAVLTree_@1(struct Node * current, @1 value, BAT *b, BUN
base);
struct NodeSimple * InsertTreeSimple_@1(struct NodeSimple ** head, oid
position, @1 value, struct NodeSimple * current, BAT * b);
@
@c
@@ -816,6 +817,24 @@ findNodeL_@1(@1 x, bit inclusive, struc
return findNodeL_@1(x, inclusive, current->right, b, base,
(current->deleted == TRUE) ? getPreviousNode(current, prev) : current);
}
+void
+PartiallyLazyFreeAVLTree_@1(struct Node * current, @1 value, BAT *b, BUN base){
+ BUN cur;
+ @1 *curValue;
+
+ cur = base + current->position;
+ curValue = (@1*)Tloc(b, cur);
+
+ if (current->left != NULL)
+ PartiallyLazyFreeAVLTree_@1(current->left, value, b, base);
+
+ if (current->right != NULL)
+ PartiallyLazyFreeAVLTree_@1(current->right, value, b, base);
+
+ if( @2_LT(&value,curValue,@3@1) || (@2_EQ(&value,curValue,@3@1) &&
current->inclusive == FALSE) )
+ current->deleted = TRUE;
+ return;
+}
struct NodeSimple *
diff --git a/monetdb5/extras/crackers/opt_selcrackst.mx
b/monetdb5/extras/crackers/opt_selcrackst.mx
--- a/monetdb5/extras/crackers/opt_selcrackst.mx
+++ b/monetdb5/extras/crackers/opt_selcrackst.mx
@@ -29,12 +29,13 @@ pattern optimizer.selcrackst():str
address OPTselcrackst;
pattern optimizer.selcrackst(mod:str, fcn:str):str
address OPTselcrackst
-comment "Selection cracking";
+comment "Stochastic Selection cracking";
module crackers;
pattern crackers.selcrackstprelude():void
address SCSprelude;
crackers.selcrackstprelude();
+
@h
#ifndef _OPT_SELCRACKST_
#define _OPT_SELCRACKST_
@@ -44,7 +45,8 @@ crackers.selcrackstprelude();
#define OPTDEBUGselcrackst if ( optDebug & ((lng)1 <<DEBUG_OPT_SELCRACKST) )
opt_export str SCSprelude(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr
pci);
-opt_export str OPTselcrackst(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
InstrPtr pci);
+opt_export str OPTselcrackst(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
InstrPtr p);
+
#endif
@c
@@ -58,7 +60,6 @@ opt_export str OPTselcrackst(Client cntx
#define match2(X,M,F) ( (X) && getFunctionId(X) && getFunctionId(X)==F && \
getModuleId(X) && getModuleId(X)==M)
-
str
SCSprelude(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
@@ -67,25 +68,25 @@ SCSprelude(Client cntxt, MalBlkPtr mb, M
(void) pci;
addPipeDefinition(cntxt, "crackerst_pipe",
- "optimizer.inline();"
- "optimizer.remap();"
- "optimizer.evaluate();"
- "optimizer.costModel();"
- "optimizer.coercions();"
- "optimizer.emptySet();"
- "optimizer.aliases();"
- "optimizer.selcrackst();"
- "optimizer.deadcode();"
- "optimizer.commonTerms();"
- "optimizer.groups();"
- "optimizer.joinPath();"
- "optimizer.reorder();"
- "optimizer.deadcode();"
- "optimizer.reduce();"
- "optimizer.dataflow();"
- "optimizer.history();"
- "optimizer.multiplex();"
- "optimizer.garbageCollector();");
+ "optimizer.inline();"
+ "optimizer.remap();"
+ "optimizer.evaluate();"
+ "optimizer.costModel();"
+ "optimizer.coercions();"
+ "optimizer.emptySet();"
+ "optimizer.aliases();"
+ "optimizer.selcrackst();"
+ "optimizer.deadcode();"
+ "optimizer.commonTerms();"
+ "optimizer.groups();"
+ "optimizer.joinPath();"
+ "optimizer.reorder();"
+ "optimizer.deadcode();"
+ "optimizer.reduce();"
+ "optimizer.dataflow();"
+ "optimizer.history();"
+ "optimizer.multiplex();"
+ "optimizer.garbageCollector();");
return MAL_SUCCEED;
}
@@ -97,31 +98,20 @@ OPTselcrackstImplementation(Client cntxt
{
InstrPtr p, *old;
int update= 0, i, limit, actions=0, j;
- int no_of_leftjoins=0;
+
str tables[maxTables];
int crackedTables=0;
for(j=0;j<maxTables;j++)
tables[j] = NULL;
+
OPTDEBUGselcrackst
- printf("Stochastic crack optimizer started\n");
-
- (void) cntxt;/* Tell compilers that we know that we do not */
- (void) stk; /* use these function parameters, here. */
+ printf("Stochastic Crack optimizer started\n");
+ (void) cntxt;
+ (void) stk;
(void) pci;
- /* In general, a MAL optimizer transforms a given MAL program into a
- * modified one by sequentially walking through the given program
- * and concurrently creating a new one from scratch by
- * (1) copying statements as is, modified, or in a different order,
- * or (2) omitting statements or (3) introducing new statements.
- */
-
- /* check for logical error: mb must never be NULL */
- assert (mb != NULL);
-
- /* safe the old stage of the MAL block */
limit = mb->stop;
old = mb->stmt;
@@ -134,15 +124,7 @@ OPTselcrackstImplementation(Client cntxt
}
if (update)
return 0;
- /*If there are more than one leftjoins in the plan, we do not want to
replace or delete none of them*/
- for (i = 0; i < limit; i++) {
- p = old[i];
- if (match2(old[j], algebraRef, leftjoinRef))
- no_of_leftjoins++;
- }
-
- /* iterate over the instructions of the input MAL program */
for (i = 0; i < limit; i++) {
p = old[i];
@@ -167,12 +149,10 @@ OPTselcrackstImplementation(Client cntxt
if (mb->var[getArg(p,5)]->value.val.ival != 0 )
continue;
- varSetProp(mb, getArg(p, 0), canBeCrackedProp, 0,
NULL); /* add a property "can be cracked" to every base relation that is a
candidate for selection cracking */
+ varSetProp(mb, getArg(p, 0), canBeCrackedProp, 0, NULL);
-
- vp = VALset(&v, TYPE_str,
GDKstrdup(getVar(mb,getArg(p,2))->value.val.sval)); /* also, for every
candidate bat, maintain the table name */
+ vp = VALset(&v, TYPE_str,
GDKstrdup(getVar(mb,getArg(p,2))->value.val.sval));
varSetProp(mb, getArg(p,0), tableProp, op_eq, vp);
-
continue;
}
@@ -206,11 +186,6 @@ OPTselcrackstImplementation(Client cntxt
if (match2(p, algebraRef, selectRef) ||
match2(p, algebraRef, uselectRef) ||
match2(p, algebraRef, thetauselectRef)){
-
-
- int j=0,k=0,m=0;
- bit found = FALSE;
_______________________________________________
checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
