LCOV - code coverage report
Current view: top level - monetdb5/optimizer - opt_projectionpath.c (source / functions) Hit Total Coverage
Test: coverage.info Lines: 71 81 87.7 %
Date: 2021-10-13 02:24:04 Functions: 1 1 100.0 %

          Line data    Source code
       1             : /*
       2             :  * This Source Code Form is subject to the terms of the Mozilla Public
       3             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       4             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       5             :  *
       6             :  * Copyright 1997 - July 2008 CWI, August 2008 - 2021 MonetDB B.V.
       7             :  */
       8             : 
       9             : /* author: M Kersten
      10             :  * Post-optimization of projection lists.
      11             :  */
      12             : #include "monetdb_config.h"
      13             : #include "opt_deadcode.h"
      14             : #include "opt_projectionpath.h"
      15             : 
      16             : 
      17             : // Common prefix reduction was not effective it is retained for
      18             : // future experiments.
      19             : //#define ELIMCOMMONPREFIX
      20             : 
      21             : #ifdef ELIMCOMMONPREFIX
      22             : static int
      23             : OPTprojectionPrefix(Client cntxt, MalBlkPtr mb)
      24             : {
      25             :         int i, j, k, maxmatch, actions=0;
      26             :         InstrPtr p,q,*old = NULL;
      27             :         int limit, slimit;
      28             :         InstrPtr *paths = NULL;
      29             :         int *alias = NULL;
      30             : 
      31             :         (void) cntxt;
      32             :         limit = mb->stop;
      33             :         slimit= mb->ssize;
      34             : 
      35             :         paths = (InstrPtr *) GDKzalloc(mb->vsize * sizeof(InstrPtr));
      36             :         if (paths == NULL)
      37             :                 return 0;
      38             :         alias = (int*) GDKzalloc(mb->vsize * sizeof(int));
      39             :         if( alias == NULL){
      40             :                 GDKfree(paths);
      41             :                 return 0;
      42             :         }
      43             : 
      44             :         maxmatch = 0; // to collect maximum common paths
      45             :         old = mb->stmt;
      46             :         /* Collect the projection paths achored at the same start */
      47             :         for( i=0; i< limit; i++){
      48             :                 p = old[i];
      49             :                 if ( getFunctionId(p) == projectionpathRef && p->argc > 3){
      50             :                         k = getArg(p,1);
      51             :                         if( paths[k] == 0)
      52             :                                 paths[k] = p;
      53             :                         q = paths[k];
      54             :                         // Calculate the number of almost identical paths
      55             :                         if( q->argc == p->argc){
      56             :                                 for(j = q->retc; j<q->argc - 1; j++)
      57             :                                         if( getArg(p,j) != getArg(q,j))
      58             :                                                 break;
      59             :                                 if( j == q->argc -1 ){
      60             :                                         alias[k] = alias[k] -1;
      61             :                                         if (alias[k] < maxmatch)
      62             :                                                 maxmatch = alias[k];
      63             :                                 }
      64             :                         }
      65             :                 }
      66             :         }
      67             :         if (maxmatch == -1){
      68             :                 GDKfree(alias);
      69             :                 GDKfree(paths);
      70             :                 return 0;
      71             :         }
      72             : 
      73             :         if (newMalBlkStmt(mb,mb->ssize) < 0){
      74             :                 GDKfree(paths);
      75             :                 GDKfree(alias);
      76             :                 return 0;
      77             :         }
      78             : 
      79             : 
      80             :         for( i = 0; i < limit; i++){
      81             :                 p = old[i];
      82             :                 if ( getFunctionId(p) != projectionpathRef ){
      83             :                         pushInstruction(mb,p);
      84             :                         continue;
      85             :                 }
      86             :                 if( p->argc < 3){
      87             :                         pushInstruction(mb,p);
      88             :                         continue;
      89             :                 }
      90             : 
      91             :                 actions++;
      92             :                 // the first one should be split if there is interest
      93             :                 k = getArg(p,1);
      94             :                 q = paths[k];
      95             :                 if( alias[k] < 0){
      96             :                         // inject the join prefix calculation
      97             :                         q= copyInstruction(q);
      98             :                         q->argc = q->argc -1;
      99             :                         getArg(q,0) = newTmpVariable(mb, getArgType(mb,q, q->argc -1));
     100             :                         pushInstruction(mb, q);
     101             :                         alias[k] = getArg(q,0);
     102             :                         q = copyInstruction(p);
     103             :                         getArg(q,1) = alias[k];
     104             :                         getArg(q,2) = getArg(q, q->argc -1);
     105             :                         q->argc = 3;
     106             :                         pushInstruction(mb,q);
     107             :                         continue;
     108             :                 }
     109             :                 // check if we can replace the projectionpath with an alias
     110             :                 k = getArg(p,1);
     111             :                 q = paths[k];
     112             :                 if( alias[k] >  0 && q->argc == p->argc){
     113             :                         for(j = q->retc; j<q->argc - 1; j++)
     114             :                                 if( getArg(p,j) != getArg(q,j))
     115             :                                         break;
     116             :                         if( j == q->argc - 1){
     117             :                                 // we found a common prefix, and it is the first one?
     118             :                                 getArg(p,1) = alias[k];
     119             :                                 getArg(p,2) = getArg(p, p->argc -1);
     120             :                                 p->argc = 3;
     121             :                                 pushInstruction(mb,p);
     122             :                         }
     123             :                 } else {
     124             :                         pushInstruction(mb,p);
     125             :                         continue;
     126             :                 }
     127             : 
     128             :         }
     129             : 
     130             :         for(; i<slimit; i++)
     131             :                 if(old[i])
     132             :                         freeInstruction(old[i]);
     133             :         GDKfree(old);
     134             :         GDKfree(paths);
     135             :         GDKfree(alias);
     136             :         //if(actions)
     137             :                 //printFunction(cntxt->fdout, mb, 0, LIST_MAL_ALL);
     138             :         return actions;
     139             : }
     140             : #endif
     141             : 
     142             : str
     143      353098 : OPTprojectionpathImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
     144             : {
     145             :         int i,j,k, actions=0, maxprefixlength=0;
     146             :         int *pc = NULL;
     147             :         InstrPtr p, q, r;
     148             :         InstrPtr *old=0;
     149             :         int *varcnt=  NULL;             /* use count */
     150             :         int limit,slimit;
     151             :         str msg = MAL_SUCCEED;
     152             : 
     153             :         (void) cntxt;
     154             :         (void) stk;
     155      353098 :         if ( mb->inlineProp)
     156           0 :                 goto wrapupall;
     157             : 
     158    13484103 :         for( i = 0; i < mb->stop ; i++){
     159    13183676 :                 p = getInstrPtr(mb,i);
     160    13183676 :                 if ( getModuleId(p) == algebraRef && ((getFunctionId(p) == projectionRef && p->argc == 3) || getFunctionId(p) == projectionpathRef) ){
     161             :                         break;
     162             :                 }
     163             :         }
     164      353098 :         if ( i == mb->stop){
     165      300427 :                 goto wrapupall;
     166             :         }
     167             : 
     168             :         limit= mb->stop;
     169       52671 :         slimit= mb->ssize;
     170       52671 :         old= mb->stmt;
     171       52671 :         if ( newMalBlkStmt(mb, 2 * mb->stop) < 0)
     172           0 :                 throw(MAL,"optimizer.projectionpath", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     173             : 
     174             :         /* beware, new variables and instructions are introduced */
     175       52671 :         pc= (int*) GDKzalloc(sizeof(int)* mb->vtop * 2); /* to find last assignment */
     176       52671 :         varcnt= (int*) GDKzalloc(sizeof(int)* mb->vtop * 2);
     177       52671 :         if (pc == NULL || varcnt == NULL ){
     178           0 :                 if(pc) GDKfree(pc);
     179           0 :                 if(varcnt) GDKfree(varcnt);
     180           0 :                 throw(MAL,"optimizer.projectionpath", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     181             :         }
     182             : 
     183             :         /*
     184             :          * Count the variable re-use  used as arguments first.
     185             :          * A pass operation is not a real re-use
     186             :          */
     187    12146027 :         for (i = 0; i<limit; i++){
     188    12093356 :                 p= old[i];
     189    47279926 :                 for(j=p->retc; j<p->argc; j++)
     190    35186570 :                 if( ! (getModuleId(p) == languageRef && getFunctionId(p)== passRef))
     191    35186570 :                         varcnt[getArg(p,j)]++;
     192             :         }
     193             : 
     194             :         /* assume a single pass over the plan, and only consider projection sequences
     195             :          * beware, we are only able to deal with projections without candidate lists. (argc=3)
     196             :          * We also should not change the type of the outcome, i.e. leaving the last argument untouched.
     197             :          */
     198    12146027 :         for (i = 0; i<limit; i++){
     199    12093356 :                 p= old[i];
     200    12093356 :                 if( getModuleId(p)== algebraRef && getFunctionId(p) == projectionRef && p->argc == 3){
     201             :                         /*
     202             :                          * Try to expand its argument list with what we have found so far.
     203             :                          */
     204     4726539 :                         int args = p->retc;
     205    14179617 :                         for (j = p->retc; j < p->argc; j++) {
     206     9453078 :                                 if (pc[getArg(p,j)] &&
     207     3729574 :                                         (r = getInstrPtr(mb, pc[getArg(p, j)])) != NULL &&
     208     3729574 :                                         varcnt[getArg(p,j)] <= 1 &&
     209     2619502 :                                         getModuleId(r)== algebraRef &&
     210     2619502 :                                         (getFunctionId(r)== projectionRef ||
     211     2199730 :                                          getFunctionId(r) == projectionpathRef))
     212     2619502 :                                         args += r->argc - r->retc;
     213             :                                 else
     214     6833576 :                                         args++;
     215             :                         }
     216     4726539 :                         if((q = copyInstructionArgs(p, args)) == NULL) {
     217           0 :                                 msg = createException(MAL,"optimizer.projectionpath", SQLSTATE(HY013) MAL_MALLOC_FAIL);
     218           0 :                                 goto wrapupall;
     219             :                         }
     220             : 
     221     4726539 :                         q->argc=p->retc;
     222    14179617 :                         for(j=p->retc; j<p->argc; j++){
     223     9453078 :                                 if (pc[getArg(p,j)] )
     224     3729574 :                                         r = getInstrPtr(mb,pc[getArg(p,j)]);
     225             :                                 else
     226             :                                         r = 0;
     227     3729574 :                                 if (r && varcnt[getArg(p,j)] > 1 )
     228             :                                         r = 0;
     229             : 
     230             :                                 /* inject the complete sub-path */
     231             : 
     232     9453078 :                                 if ( getFunctionId(p) == projectionRef){
     233     9453078 :                                         if( r &&  getModuleId(r)== algebraRef && ( getFunctionId(r)== projectionRef  || getFunctionId(r)== projectionpathRef) ){
     234    40737366 :                                                 for(k= r->retc; k<r->argc; k++)
     235    38117864 :                                                         q = addArgument(mb,q,getArg(r,k));
     236             :                                         } else
     237     6833576 :                                                 q = addArgument(mb,q,getArg(p,j));
     238             :                                 }
     239             :                         }
     240     4726539 :                         if(q->argc<= p->argc){
     241             :                                 /* no change */
     242     2117489 :                                 freeInstruction(q);
     243     2117489 :                                 goto wrapup;
     244             :                         }
     245             :                         /*
     246             :                          * Final type check and hardwire the result type, because that  can not be inferred directly from the signature
     247             :                          * We already know that all heads are void. Only the last element may have a non-oid type.
     248             :                          */
     249    40716462 :                         for(j=1; j<q->argc-1; j++)
     250    38107412 :                                 if( getBatType(getArgType(mb,q,j)) != TYPE_oid  && getBatType(getArgType(mb,q,j)) != TYPE_void ){
     251             :                                         /* don't use the candidate list */
     252           0 :                                         freeInstruction(q);
     253           0 :                                         goto wrapup;
     254             :                                 }
     255             : 
     256             :                         /* fix the type */
     257     2609050 :                         setVarType(mb, getArg(q,0), newBatType(getBatType(getArgType(mb,q,q->argc-1))));
     258     2609050 :                         if ( getFunctionId(q) == projectionRef )
     259     2609050 :                                 setFunctionId(q,projectionpathRef);
     260     2609050 :                         q->typechk = TYPE_UNKNOWN;
     261             : 
     262     2609050 :                         freeInstruction(p);
     263             :                         p = q;
     264             :                         /* keep track of the longest projection path */
     265             :                         if ( p->argc  > maxprefixlength)
     266             :                                 maxprefixlength = p->argc;
     267     2609050 :                         actions++;
     268             :                 }
     269     7366817 :         wrapup:
     270    12093356 :                 pushInstruction(mb,p);
     271    25255962 :                 for(j=0; j< p->retc; j++)
     272    13162606 :                 if( getModuleId(p)== algebraRef && ( getFunctionId(p)== projectionRef  || getFunctionId(p)== projectionpathRef) ){
     273     4726541 :                         pc[getArg(p,j)]= mb->stop-1;
     274             :                 }
     275             :         }
     276             : 
     277     7719187 :         for(; i<slimit; i++)
     278     7666516 :                 if(old[i])
     279           0 :                         pushInstruction(mb, old[i]);
     280             : 
     281             :         /* All complete projection paths have been constructed.
     282             :          * There may be cases where there is a common prefix used multiple times.
     283             :          * Especially in wide table projections and lengthy paths
     284             :          * They can be located and replaced in the plan by factoring the common part out
     285             :          * First experiments on tpch SF10- Q7, showed significant decrease in performance
     286             :          * Also a run against SF-100 did not show improvement in Q7
     287             :          * Also there are collateral damages in the testweb.
     288             :          */
     289             : #ifdef ELIMCOMMONPREFIX
     290             :          if( OPTdeadcodeImplementation(cntxt, mb, 0, 0) == MAL_SUCCEED){
     291             :                 actions += OPTprojectionPrefix(cntxt, mb);
     292             :         }
     293             : #endif
     294             : 
     295             :         /* Defense line against incorrect plans */
     296       52671 :         if( actions > 0){
     297       23532 :                 msg = chkTypes(cntxt->usermodule, mb, FALSE);
     298       23532 :                 if (!msg)
     299       23532 :                         msg = chkFlow(mb);
     300       23532 :                 if (!msg)
     301       23532 :                         msg = chkDeclarations(mb);
     302             :         }
     303       29139 : wrapupall:
     304             :         /* keep actions taken as a fake argument*/
     305      353098 :         (void) pushInt(mb, pci, actions);
     306             : 
     307      353098 :         if (pc ) GDKfree(pc);
     308      353098 :         if (varcnt ) GDKfree(varcnt);
     309      353098 :         if(old) GDKfree(old);
     310             : 
     311             :         return msg;
     312             : }

Generated by: LCOV version 1.14