Line data    Source code

       1             : /*
       2             :  * SPDX-License-Identifier: MPL-2.0
       3             :  *
       4             :  * This Source Code Form is subject to the terms of the Mozilla Public
       5             :  * License, v. 2.0.  If a copy of the MPL was not distributed with this
       6             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
       7             :  *
       8             :  * Copyright 2024 MonetDB Foundation;
       9             :  * Copyright August 2008 - 2023 MonetDB B.V.;
      10             :  * Copyright 1997 - July 2008 CWI.
      11             :  */
      12             : 
      13             : /*
      14             :  * The dataflow reorder
      15             :  * MAL programs are largely logical descriptions of an execution plan.
      16             :  * After the mitosis and mergetable optimizers we have a large program, which when
      17             :  * executed as is, does not necessarily benefit from the locality
      18             :  * of data and operations. The problem is that the execution plan is
      19             :  * a DAG for which a topological order should be found that
      20             :  * minimizes the life time of variables and maximizes parallel execution.
      21             :  * This is an NP hard optimization problem. Therefore, we have
      22             :  * to rely on an affordable heuristic steps.
      23             :  *
      24             :  * The reorder optimizer transfers the breadth-first plans of
      25             :  * the mergetable into a multi-phase execution plan.
      26             :  * This increases cohesion for parallel execution.
      27             :  * A subquery is processed completely as quickly as possible.
      28             :  * Only when the subquery is stalled for available input, the
      29             :  * threads may start working on another subquery.
      30             :  *
      31             :  */
      32             : #include "monetdb_config.h"
      33             : #include "opt_reorder.h"
      34             : #include "mal_instruction.h"
      35             : #include "mal_interpreter.h"
      36             : #include "opt_mitosis.h"
      37             : 
      38             : 
      39             : #define MAXSLICES 1024                  /* to be refined */
      40             : 
      41             : /* Insert the instruction immediately after a previous instruction that
      42             :  * generated an argument needed.
      43             :  * If non can be found, add it to the end.
      44             :  * Be aware of side-effect instructions, they may not be skipped.
      45             :  */
      46             : str
      47      483988 : OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
      48             :                                                  InstrPtr pci)
      49             : {
      50      483988 :         int i, j, k, blkcnt = 1, pc = 0, actions = 0;
      51      483988 :         InstrPtr p = NULL, *old = NULL;
      52      483988 :         int limit, slimit, *depth = NULL;
      53      483988 :         str msg = MAL_SUCCEED;
      54      483988 :         InstrPtr *blocks[MAXSLICES] = { 0 };
      55      483988 :         int top[MAXSLICES] = { 0 };
      56      483988 :         int barriers[MAXSLICES] = { 0 }, btop = 0, off = 0;
      57             : 
      58      483988 :         for (i = 0; i < MAXSLICES; i++)
      59             :                 top[i] = 0;
      60      483988 :         if (isOptimizerUsed(mb, pci, mitosisRef) <= 0) {
      61       33783 :                 goto wrapup;
      62             :         }
      63      450204 :         (void) cntxt;
      64      450204 :         (void) stk;
      65             : 
      66      450204 :         limit = mb->stop;
      67      450204 :         slimit = mb->ssize;
      68      450204 :         old = mb->stmt;
      69             : 
      70      450204 :         depth = (int *) GDKzalloc(mb->vtop * sizeof(int));
      71      450204 :         if (depth == NULL) {
      72           0 :                 throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      73             :         }
      74             : 
      75      450204 :         if (newMalBlkStmt(mb, mb->ssize) < 0) {
      76           0 :                 GDKfree(depth);
      77           0 :                 throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      78             :         }
      79             : 
      80     8055803 :         actions = 1;
      81             :         /* Mark the parameters as constants as belonging to depth 0; */
      82     8055803 :         for (i = 0; i < limit; i++) {
      83     8055803 :                 p = old[i];
      84     8055803 :                 if (!p) {
      85             :                         //mnstr_printf(cntxt->fdout, "empty stmt:pc %d \n", i);
      86           0 :                         continue;
      87             :                 }
      88     8055803 :                 if (p->token == ENDsymbol)
      89             :                         break;
      90     7605599 :                 k = off;
      91     7605599 :                 if (getModuleId(p) == sqlRef && getFunctionId(p) == tidRef
      92      211700 :                         && p->argc == 6) {
      93      116065 :                         if (depth[getArg(p, 0)] == 0) {
      94      116065 :                                 k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
      95      116065 :                                 assert(k < MAXSLICES);
      96      116065 :                                 depth[getArg(p, 0)] = k;
      97      116065 :                                 depth[getArg(p, p->retc)] = k;       /* keep order of mvc input var */
      98             :                         }
      99     7489534 :                 } else if (getModuleId(p) == sqlRef && getFunctionId(p) == bindRef
     100      970105 :                                    && p->argc == 8) {
     101      375738 :                         if (depth[getArg(p, 0)] == 0) {
     102      375738 :                                 k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
     103      375738 :                                 assert(k < MAXSLICES);
     104      375738 :                                 depth[getArg(p, 0)] = k;
     105      375738 :                                 depth[getArg(p, p->retc)] = k;       /* keep order of mvc input var */
     106             :                         }
     107             :                 } else {
     108    33176163 :                         for (j = p->retc; j < p->argc; j++) {
     109    26062367 :                                 if (depth[getArg(p, j)] > k)
     110             :                                         k = depth[getArg(p, j)];
     111             :                         }
     112     7113796 :                         assert(k < MAXSLICES);
     113    15091746 :                         for (j = 0; j < p->retc; j++)
     114     7977950 :                                 if (depth[getArg(p, j)] == 0)
     115     7977881 :                                         depth[getArg(p, j)] = k;
     116             :                         /* In addition to the input variables of the statements al statements within a barrier also
     117             :                          * depend on the barriers variable */
     118     7113796 :                         if (blockStart(p)) {
     119         852 :                                 assert(btop < MAXSLICES);
     120         852 :                                 barriers[btop++] = k;
     121         852 :                                 off = k;
     122             :                         }
     123     7113796 :                         if (blockExit(p)) {
     124         852 :                                 off = 0;
     125         852 :                                 if (btop--)
     126         852 :                                         off = barriers[btop];
     127             :                         }
     128             :                 }
     129             : 
     130     7605599 :                 if (top[k] == 0) {
     131      534719 :                         blocks[k] = GDKzalloc(limit * sizeof(InstrPtr));
     132      534717 :                         if (blocks[k] == NULL) {
     133           0 :                                 for (i = 0; i < blkcnt; i++)
     134           0 :                                         if (top[i])
     135           0 :                                                 GDKfree(blocks[i]);
     136           0 :                                 GDKfree(depth);
     137           0 :                                 GDKfree(mb->stmt);
     138           0 :                                 mb->stop = limit;
     139           0 :                                 mb->ssize = slimit;
     140           0 :                                 mb->stmt = old;
     141           0 :                                 throw(MAL, "optimizer.reorder",
     142             :                                           SQLSTATE(HY013) MAL_MALLOC_FAIL);
     143             :                         }
     144             :                 }
     145     7605597 :                 blocks[k][top[k]] = p;
     146     7605597 :                 top[k] = top[k] + 1;
     147             :                 //mnstr_printf(cntxt->fdout, "block[%d] :%d:",i, k);
     148             :                 //printInstruction(cntxt->fdout, mb, stk, p, LIST_MAL_DEBUG);
     149     7605597 :                 if (k > blkcnt)
     150             :                         blkcnt = k;
     151             :         }
     152             : 
     153     1403589 :         for (k = 0; k <= blkcnt; k++)
     154     8559005 :                 for (j = 0; j < top[k]; j++) {
     155     7605620 :                         p = blocks[k][j];
     156     7605620 :                         p->pc = pc++;
     157     7605620 :                         pushInstruction(mb, p);
     158             :                 }
     159             : 
     160    14406244 :         for (; i < limit; i++)
     161    13956039 :                 if (old[i])
     162    13956039 :                         pushInstruction(mb, old[i]);
     163    97448126 :         for (; i < slimit; i++)
     164    96997920 :                 if (old[i])
     165           0 :                         pushInstruction(mb, old[i]);
     166             : 
     167             :         /* Defense line against incorrect plans */
     168      450206 :         msg = chkTypes(cntxt->usermodule, mb, FALSE);
     169      450206 :         if (!msg)
     170      450206 :                 msg = chkFlow(mb);
     171      450205 :         if (!msg)
     172      450205 :                 msg = chkDeclarations(mb);
     173             :         /* keep all actions taken as a post block comment */
     174             :         //mnstr_printf(cntxt->fdout,"REORDER RESULT ");
     175             :         //printFunction(cntxt->fdout, mb, 0, LIST_MAL_ALL);
     176           0 :   wrapup:
     177     1504938 :         for (i = 0; i <= blkcnt; i++)
     178     1020949 :                 if (top[i])
     179      534717 :                         GDKfree(blocks[i]);
     180             : 
     181             :         /* keep actions taken as a fake argument */
     182      483989 :         (void) pushInt(mb, pci, actions);
     183      483988 :         GDKfree(depth);
     184      483989 :         GDKfree(old);
     185      483989 :         return msg;
     186             : }