EMMA Coverage Report (generated Tue Aug 23 05:57:12 CDT 2011)
[all classes][felix.optimizer]

COVERAGE SUMMARY FOR SOURCE FILE [DMOOptimizer.java]

nameclass, %method, %block, %line, %
DMOOptimizer.java100% (1/1)67%  (4/6)63%  (887/1413)64%  (157.7/245)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class DMOOptimizer100% (1/1)67%  (4/6)63%  (887/1413)64%  (157.7/245)
close (): void 0%   (0/1)0%   (0/4)0%   (0/2)
giveMeTheSignatureOfTwoQuery (HashMap): String 0%   (0/1)0%   (0/110)0%   (0/16)
optimizeMateralization (DataMovementOperator): void 100% (1/1)46%  (342/750)51%  (67.7/134)
optimizeDMO (ConcurrentOperatorsBucket): void 100% (1/1)93%  (40/43)82%  (9/11)
generateAllPossiblePlans (Literal, ArrayList, ArrayList, HashMap): HashMap 100% (1/1)100% (492/493)99%  (76/77)
DMOOptimizer (CostModel): void 100% (1/1)100% (13/13)100% (5/5)

1package felix.optimizer;
2 
3import java.util.ArrayList;
4import java.util.Arrays;
5import java.util.HashMap;
6import java.util.HashSet;
7import java.util.Iterator;
8import java.util.concurrent.ExecutorService;
9import java.util.concurrent.Executors;
10 
11 
12import tuffy.db.RDB;
13import tuffy.mln.Literal;
14import tuffy.mln.Term;
15import tuffy.mln.Type;
16import tuffy.ra.ConjunctiveQuery;
17import tuffy.ra.Expression;
18import tuffy.util.Config;
19import tuffy.util.Timer;
20import tuffy.util.UIMan;
21 
22import felix.dstruct.ConcurrentOperatorsBucket;
23import felix.dstruct.DataMovementOperator;
24import felix.dstruct.FelixPredicate;
25import felix.dstruct.StatOperator;
26import felix.optimizer.CostModel;
27import felix.optimizer.CostModel.resultTuple;
28import felix.society.TaskList;
29import felix.society.TaskSet;
30import felix.task.OptimizeDMOTask;
31import felix.util.FelixConfig;
32import felix.util.FelixUIMan;
33 
34/**
35 * An object of DMOOptimer takes inputs as a DMO, analyzes its
36 * logic plan, and fill in its physical plan. Current version of the
37 * DMOOptimizer will only optimize the materialization trade-off.
38 * Note that, this class does not touch the DB directly, instead
39 * it uses an instance of {@link CostModel}.
40 * 
41 * @author Ce Zhang
42 *
43 */
44public class DMOOptimizer {
45 
46        /**
47         * Cost model used to optimize the DMO.
48         */
49        public CostModel cm;
50        
51        /**
52         * Database connection.
53         */
54        RDB db;
55        
56        /**
57         * The constructor.
58         * @param _cm
59         */
60        public DMOOptimizer(CostModel _cm){
61                cm = _cm;
62                db = RDB.getRDBbyConfig(Config.db_schema);
63        }
64        
65        /**
66         * Close the database connection used in this DMOOptimizer.
67         */
68        public void close(){
69                db.close();
70        }
71        
72        boolean picasso = false;
73        
74        
75        /**
76         * Optimize all DMOs appearing in the given {@link ConcurrentOperatorsBucket}.
77         * @param cob
78         */
79        public void optimizeDMO(ConcurrentOperatorsBucket cob){
80                
81                // optimize their DMOs
82                ExecutorService pool = Executors.newFixedThreadPool(Config.getNumThreads());
83                
84                TaskList tasks = new TaskList();
85                
86                TaskSet taskset1 = new TaskSet();
87                        
88                for(StatOperator op : cob.getOperators()){
89                        taskset1.addSubTask(new OptimizeDMOTask(op, this));
90                }        
91                
92                tasks.addSubTask(taskset1);
93                try {
94                        tasks.execute(pool);
95                } catch (Exception e) {
96                        e.printStackTrace();
97                }
98                
99                pool.shutdown();
100        }
101        
102        /**
103         * Returns signature of query set.
104         * @param sets
105         * @return
106         */
107        public String giveMeTheSignatureOfTwoQuery(HashMap<Literal, ConjunctiveQuery> sets){
108                
109                String signature = "";
110                
111                String[] qs = new String[sets.values().size()];
112                int ct = 0;
113                for(ConjunctiveQuery query : sets.values()){
114                        
115                        String[] l = new String[query.body.size()];
116                        
117                        for(int i=0;i<l.length;i++){
118                                l[i] = query.body.get(i).toString();
119                        }
120                        
121                        Arrays.sort(l);
122                        String ss = "";
123                        for(String s : l){
124                                ss = ss + s + ",";
125                        }
126                        
127                        qs[ct++] = ss;
128                        
129                }
130                
131                Arrays.sort(qs);
132                for(String s : qs){
133                        signature = signature + s + "  |  ";
134                }
135                        
136                return signature;
137        }
138        
139        /**
140         * Optimize the materialization trade-off of the given DMO.
141         * @param dmo
142         */
143        public void optimizeMateralization(DataMovementOperator dmo){
144                try{
145                        
146                        ConjunctiveQuery rule = dmo.logicQueryPlan.objectConjunctiveQuery;
147                                                
148                        double bb = dmo.predictedBB;
149                        double bf = dmo.PredictedBF;
150                        double ff = dmo.PredictedFF;
151                        
152                        // cost for full view.
153                        double view = cm.getFullViewCost(rule, bb, bf, ff, dmo.whichToBound);
154                        
155                        // cost for full materalization.
156                        double full = cm.getFullMatCost(rule, bb, bf, ff, dmo.whichToBound);
157                                                                                
158                        HashMap<ConjunctiveQuery, HashMap<Literal, ConjunctiveQuery>> comb = 
159                                new HashMap<ConjunctiveQuery, HashMap<Literal, ConjunctiveQuery>>();
160                        ArrayList<String> additionalSelList = new ArrayList<String>();
161                        HashMap<String, String> typeMapping = new HashMap<String, String>();
162                        
163                        for(String s : dmo.additionalSelList){
164                                if(s.equals("weight")){
165                                        if(rule.sourceClause.hasEmbeddedWeight()){
166                                                additionalSelList.add(rule.sourceClause.getVarWeight());
167                                                typeMapping.put(rule.sourceClause.getVarWeight(), "double_");
168                                        }
169                                }
170                        }
171                        
172                        // all binary decomposition of this conjunctive query.
173                        comb = this.generateAllPossiblePlans(rule.head, rule.body, additionalSelList, typeMapping);
174                        
175                        ConjunctiveQuery bestQuery = null;
176                        HashMap<Literal, ConjunctiveQuery> fullplan = null;
177                        ConjunctiveQuery fullQuery = null;
178                        
179                        resultTuple smallestCost = cm.getNewEmptyResultTuple();
180                        smallestCost.totalCost = Double.MAX_VALUE;
181                        
182                        if(comb != null){
183                                for(ConjunctiveQuery cq : comb.keySet()){
184                
185                                        ConjunctiveQuery q1 = null;
186                                        ConjunctiveQuery q2 = null;
187                                        
188                                        for(Literal sub : cq.body){
189                                                if(q1 == null)
190                                                        q1 = comb.get(cq).get(sub);
191                                                else
192                                                        q2 = comb.get(cq).get(sub);
193                                        }
194                                        
195                                        if(q1 != null){
196                                                q1.addConstraintAll(rule.getConstraint(q1.allVariable));
197                                        }
198                                        
199                                        if(q2 != null){
200                                                q2.addConstraintAll(rule.getConstraint(q2.allVariable));
201                                        }
202                                        
203                                        if(q2 == null){
204                                                fullQuery = cq;
205                                                fullplan = comb.get(cq);
206                                                continue;
207                                        }
208                                        
209                                        //TODO:
210                                        HashSet<Expression> cons = new HashSet<Expression>();
211                                        cons.addAll(q1.getConstraint());
212                                        cons.addAll(q2.getConstraint());
213                                        if(rule.getConstraint().size() > cons.size()){
214                                                continue;
215                                        }
216                                        
217                                        resultTuple cost = cm.getJoinCostBetweenTwoMaterializedTable(
218                                                        cq.head, q1, q2, bb, bf, ff, dmo.whichToBound);
219                                        
220                                        if(cost == null){
221                                                continue;
222                                        }
223                                        
224                                        if(FelixConfig.pickRandom== false && (smallestCost.totalCost == Double.MAX_VALUE || 
225                                                (cost.totalCost <= smallestCost.totalCost/1)) ){
226                                                                                
227                                                bestQuery = cq;
228                                                smallestCost = cost;
229                                        }                                        
230                                        
231                                        if(FelixConfig.pickRandom==true && Math.random()<0.8 && cost.totalCost < 300000){
232                                                
233                                                bestQuery = cq;
234                                                smallestCost = cost;
235                                        }
236                                        
237                                }
238                        }else{
239                                fullplan = new HashMap<Literal, ConjunctiveQuery>();
240                                fullQuery = new ConjunctiveQuery();
241                                fullQuery.setHead(rule.head);
242                        }
243                                                
244                        if(picasso == true){
245                                
246                                System.out.print("postgreUnit=" + cm.postgreUnit + "\tmemoryTradeOff=" + cm.memoryTradeOff + "\t");
247                                
248                                if(smallestCost.totalCost <= view && smallestCost.totalCost <= full){
249                                        
250                                        System.out.println(this.giveMeTheSignatureOfTwoQuery(comb.get(bestQuery)));
251                                        
252                                }else if (view <= smallestCost.totalCost && view <= full){
253                                        System.out.println("VIEW");
254                                }else{
255                                        System.out.println("FULL");
256                                }
257                                
258                                
259                        }else{
260                                
261                                //TODO:
262                                //if(Config.gp == true){
263                                //        FelixConfig.allMat = true;
264                                //}
265                                
266                                
267                                // select the best one from hybrid/full-mat/full-view
268                                FelixUIMan.printobj(2,0,rule);
269                                if(comb != null){
270                                        FelixUIMan.printobj(2,0,smallestCost);
271                                        if(bestQuery != null){
272                                                FelixUIMan.printobj(2,0,comb.get(bestQuery));
273                                        }
274                                }
275                                FelixUIMan.println(2,0,"full = " + full);
276                                FelixUIMan.println(2,0,"view = " + view);
277                                
278                                if(FelixConfig.allView){
279                                        
280                                        FelixUIMan.println(1,0,">>> Regard the following query as view: \n" + "\t" + rule);
281                                        
282                                //        SchedulerTest.planCosts.add(view);
283                                        rule.isView = true;
284                                        dmo.physicalQueryPlan.objectConjunctiveQuery = rule;
285                                }else{
286                                
287                                        if(FelixConfig.allMat){
288                                                
289                                                FelixUIMan.println(1,0,">>> Regard the following query as materialized table: \n" + "\t" + rule);
290                                                
291                                                //        SchedulerTest.planCosts.add(full);
292                                                        
293                                                rule.isView = false;
294                                                
295                                                fullQuery.isView = true;
296                                                fullQuery.type = rule.type;
297                                                fullQuery.setWeight(rule.getWeight());
298                                                fullQuery.sourceClause = rule.sourceClause;
299                                                
300                                                fullQuery.inverseEmbededWeight = rule.inverseEmbededWeight;
301                                                
302                                                dmo.physicalQueryPlan.objectConjunctiveQuery = fullQuery;
303                                                if(fullplan.size() > 0){
304                                                        dmo.physicalQueryPlan.datalogQueries.add(fullplan.get(fullQuery.body.get(0)));
305                                                        fullplan.get(fullQuery.body.get(0)).head.getPred().prepareDB(db);
306                                                }
307                                                
308                                        }else{
309                                        
310                                                if(smallestCost.totalCost <= view && smallestCost.totalCost <= full){
311                                                        
312                                        //                SchedulerTest.planCosts.add(smallestCost.totalCost);
313                                                        
314                                                        ConjunctiveQuery q1 = null;
315                                                        ConjunctiveQuery q2 = null;
316                                                        
317                                                        if(bestQuery == null){
318                                                                throw new Exception("Errors!");
319                                                        }
320                                                        
321                                                        for(Literal sub : comb.get(bestQuery).keySet()){
322                                                                if(q1 == null) q1 = comb.get(bestQuery).get(sub);
323                                                                else q2 = comb.get(bestQuery).get(sub);
324                                                        }
325                                                        
326                                                        ConjunctiveQuery rsCQ = new ConjunctiveQuery();
327                                                        rsCQ.isView = true;
328                                                        rsCQ.type = rule.type;
329                                                        rsCQ.setWeight(rule.getWeight());
330                                                        rsCQ.sourceClause = rule.sourceClause;
331                                                        rsCQ.inverseEmbededWeight = rule.inverseEmbededWeight;
332                                                        
333                                                        rsCQ.setHead(bestQuery.head);
334                                                        
335                                                        if(q1.body.size() == 1){
336                                                                rsCQ.addBodyLit(q1.body.get(0));
337                                                        }else{
338                                                                rsCQ.addBodyLit(q1.head);
339                                                                dmo.physicalQueryPlan.datalogQueries.add(q1);
340                                                                //q1.head.getPred().createTable();
341                                                                q1.head.getPred().prepareDB(db);
342                                                        }
343                                                        
344                                                        if(q2.body.size() == 1){
345                                                                rsCQ.addBodyLit(q2.body.get(0));
346                                                        }else{
347                                                                rsCQ.addBodyLit(q2.head);
348                                                                dmo.physicalQueryPlan.datalogQueries.add(q2);
349                                                                q2.head.getPred().prepareDB(db);
350                                                        }
351                                                        
352                                                        dmo.physicalQueryPlan.objectConjunctiveQuery = rsCQ;
353                                                        
354                                                        q1.sourceClause = rule.sourceClause;
355                                                        q2.sourceClause = rule.sourceClause;
356                                                        
357                                                        FelixUIMan.println(1,0,">>> Regard the following query as partially materialized view: \n" 
358                                                                        + "\t" + rule + "\n" + "\t" + q1 + "\n" + "\t" + q2);
359                                                        
360                                                }else if (view <= smallestCost.totalCost && view <= full){
361                                                        
362                                                        FelixUIMan.println(1,0,">>> Regard the following query as view: \n" + "\t" + rule);
363                                                        
364                                                //        SchedulerTest.planCosts.add(view);
365                                                        
366                                                        rule.isView = true;
367                                                        dmo.physicalQueryPlan.objectConjunctiveQuery = rule;
368                                                        
369                                                }else{
370                                                        
371                                                        FelixUIMan.println(1,0,">>> Regard the following query as materialized table: \n" + "\t" + rule);
372                                                        
373                                                //        SchedulerTest.planCosts.add(full);
374                                                        
375                                                        rule.isView = false;
376                                                        
377                                                        fullQuery.isView = true;
378                                                        fullQuery.type = rule.type;
379                                                        fullQuery.setWeight(rule.getWeight());
380                                                        fullQuery.sourceClause = rule.sourceClause;
381                                                        
382                                                        fullQuery.inverseEmbededWeight = rule.inverseEmbededWeight;
383                                                        
384                                                        dmo.physicalQueryPlan.objectConjunctiveQuery = fullQuery;
385                                                        if(fullplan.size() > 0){
386                                                                dmo.physicalQueryPlan.datalogQueries.add(fullplan.get(fullQuery.body.get(0)));
387                                                                fullplan.get(fullQuery.body.get(0)).head.getPred().prepareDB(db);
388                                                        }
389                                                }
390                                        }
391                                }
392                        }
393                        
394                        
395                        
396                }catch(Exception e){
397                        e.printStackTrace();
398                }
399        }
400        
401        
402        /**
403         * Given a literal as goal, a set of literals as subgoals, generate all possible binary decompositions
404         * of this set of subgoals. The decomposition looks like:
405         * 
406         * <br/>
407         * 
408         * Q(...) :- Q1(...), Q2(...) <br/>
409         * Q1(...) :- g1, g2, ... <br/>
410         * Q2(...) :- g1', g2', ... <br/>
411         * 
412         * <br/>
413         * 
414         * Q1 and Q2 are materialized, and Q will be regarded as a view. If Q2 is null, this
415         * is equivalent to the fully-materialized case.
416         * 
417         * @param head goal
418         * @param subgoals set of subgoals
419         * @param additionalSelList terms needed to be maintained in the variable list of Q1 and Q2.
420         * By default all variables needed to compute Q from Q1 and Q2 will be automatically maintained,
421         * however, if you want to maintain others, add them in this list.
422         * @param typeMapping If you want some variables in Q1 and Q2 have special types (e.g., double instead
423         * of constant ID), put them in this map.
424         * @return Mappings from Q to Q1 and Q2.
425         */
426        public HashMap<ConjunctiveQuery, HashMap<Literal, ConjunctiveQuery>> generateAllPossiblePlans(Literal head, 
427                        ArrayList<Literal> subgoals, ArrayList<String> additionalSelList, HashMap<String, String> typeMapping){
428                
429                HashMap<ConjunctiveQuery, HashMap<Literal, ConjunctiveQuery>> forReturn = 
430                        new HashMap<ConjunctiveQuery, HashMap<Literal, ConjunctiveQuery>>();
431                
432                //ONLY CONSIDERING BI-PARTITIONING NOW
433                Integer[] biPar = new Integer[subgoals.size()];
434                for(int i=0;i<biPar.length;i++) biPar[i] = 0;
435                
436                if(subgoals.size() == 0){
437                        return null;
438                }
439                
440                Integer ct = (int) Math.pow(2, subgoals.size());
441                while(--ct >= 0){
442 
443                                                
444                        HashMap<Literal, ConjunctiveQuery> list = new HashMap<Literal, ConjunctiveQuery>();
445                        
446                        ConjunctiveQuery q1 = new ConjunctiveQuery();
447                        ConjunctiveQuery q2 = new ConjunctiveQuery();
448                        ConjunctiveQuery q = new ConjunctiveQuery();
449                        q.setHead(head);//q.head = head;
450                        
451                        HashSet<Term> varSet1 = new HashSet<Term>();
452                        HashSet<Term> varSet2 = new HashSet<Term>();
453                        HashSet<String> termName1 = new HashSet<String>();
454                        HashSet<String> termName2 = new HashSet<String>();
455                        FelixPredicate p1 = new FelixPredicate(FelixPredicate.getNextTmpPredicateName(), false);
456                        FelixPredicate p2 = new FelixPredicate(FelixPredicate.getNextTmpPredicateName(), false);
457                        
458                        HashMap<Term, Type> term2TypeMapping = new HashMap<Term, Type>();
459                        
460                        for(int i=0;i<biPar.length;i++){
461                                if(biPar[i] == 0){
462                                        //q1.body.add(subgoals.get(i));
463                                        q1.addBodyLit(subgoals.get(i));
464                                        varSet1.addAll(subgoals.get(i).getTerms());
465                                        for(int j=0;j<subgoals.get(i).getTerms().size();j++){
466                                                term2TypeMapping.put(subgoals.get(i).getTerms().get(j), subgoals.get(i).getPred().getTypeAt(j));
467                                        }
468                                        
469                                }else{
470                                        //q2.body.add(subgoals.get(i));
471                                        q2.addBodyLit(subgoals.get(i));
472                                        varSet2.addAll(subgoals.get(i).getTerms());
473                                        for(int j=0;j<subgoals.get(i).getTerms().size();j++){
474                                                term2TypeMapping.put(subgoals.get(i).getTerms().get(j), subgoals.get(i).getPred().getTypeAt(j));
475                                        }
476                                }
477                        }
478                        
479                        // generate next 0-1 combination.
480                        biPar[0] ++;
481                        for(int i=0;i<biPar.length-1;i++){
482                                if(biPar[i] == 2){
483                                        biPar[i] = 0;
484                                        biPar[i+1] ++;
485                                }
486                        }
487                        
488                        if(q1.body.size() == 0){
489                                continue;
490                        }
491                        
492                        
493                        HashSet<String> allIntermediateTerms = new HashSet<String>();
494                        HashSet<String> allIntermediateTerms2 = new HashSet<String>();
495                        
496                        for(Term t : varSet1) allIntermediateTerms.add(t.var());
497                        for(Term t : varSet2) allIntermediateTerms2.add(t.var());
498                        allIntermediateTerms.retainAll(allIntermediateTerms2);
499                        for(Term t : head.getTerms()) allIntermediateTerms.add(t.var());
500                        allIntermediateTerms.addAll(additionalSelList);
501                        
502                        Literal q1Head = new Literal(p1, true);
503                        for(Term t : varSet1){
504                                if(t.isVariable() == true && allIntermediateTerms.contains(t.var())){
505                                        if(!termName1.contains(t.var())){
506                                                q1Head.appendTerm(t);
507                                                termName1.add(t.var());
508                                                if(typeMapping.containsKey(t.var())){
509                                                        p1.appendArgument(new Type(typeMapping.get(t.var())));
510                                                }else{
511                                                        p1.appendArgument(term2TypeMapping.get(t));
512                                                }
513                                        }
514                                }
515                        }
516                        q1.setHead(q1Head);
517                        
518                        
519                        Literal q2Head =  new Literal(p2, true);
520                        for(Term t : varSet2){
521                                if(t.isVariable() == true && allIntermediateTerms.contains(t.var())){
522                                        if(!termName2.contains(t.var())){
523                                                q2Head.appendTerm(t);
524                                                termName2.add(t.var());
525                                                if(typeMapping.containsKey(t.var())){
526                                                        p2.appendArgument(new Type(typeMapping.get(t.var())));
527                                                }else{
528                                                        p2.appendArgument(term2TypeMapping.get(t));
529                                                }
530                                        }
531                                        
532                                }
533                        }
534                        q2.setHead(q2Head);
535                        
536                        if(q2.head.getTerms().size() == 0 && q1.head.getTerms().size() == 0){
537                                continue;
538                        }
539                        
540                        // full
541                        if(q2.head.getTerms().size() == 0){
542                                list.put(q1.head, q1);
543                                q.addBodyLit(q1.head);
544                                forReturn.put(q, list);
545                                continue;
546                        }
547                        
548                        list.put(q1.head, q1);
549                        list.put(q2.head, q2);
550                        
551                        q.addBodyLit(q1.head);
552                        q.addBodyLit(q2.head);
553                        
554                        forReturn.put(q, list);
555                        
556 
557                }
558                
559                
560                return forReturn;
561        }
562}

[all classes][felix.optimizer]
EMMA 2.0.5312 EclEmma Fix 2 (C) Vladimir Roubtsov