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      487572 : OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
      48             :                                                  InstrPtr pci)
      49             : {
      50      487572 :         int i, j, k, blkcnt = 1, pc = 0, actions = 0;
      51      487572 :         InstrPtr p = NULL, *old = NULL;
      52      487572 :         int limit, slimit, *depth = NULL;
      53      487572 :         str msg = MAL_SUCCEED;
      54      487572 :         InstrPtr *blocks[MAXSLICES] = { 0 };
      55      487572 :         int top[MAXSLICES] = { 0 };
      56      487572 :         int barriers[MAXSLICES] = { 0 }, btop = 0, off = 0;
      57             : 
      58      487572 :         for (i = 0; i < MAXSLICES; i++)
      59             :                 top[i] = 0;
      60      487572 :         if (isOptimizerUsed(mb, pci, mitosisRef) <= 0) {
      61       33770 :                 goto wrapup;
      62             :         }
      63      453787 :         (void) cntxt;
      64      453787 :         (void) stk;
      65             : 
      66      453787 :         limit = mb->stop;
      67      453787 :         slimit = mb->ssize;
      68      453787 :         old = mb->stmt;
      69             : 
      70      453787 :         depth = (int *) GDKzalloc(mb->vtop * sizeof(int));
      71      453799 :         if (depth == NULL) {
      72           0 :                 throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      73             :         }
      74             : 
      75      453799 :         if (newMalBlkStmt(mb, mb->ssize) < 0) {
      76           0 :                 GDKfree(depth);
      77           0 :                 throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
      78             :         }
      79             : 
      80     7628836 :         actions = 1;
      81             :         /* Mark the parameters as constants as beloning to depth 0; */
      82     7628836 :         for (i = 0; i < limit; i++) {
      83     7628836 :                 p = old[i];
      84     7628836 :                 if (!p) {
      85             :                         //mnstr_printf(cntxt->fdout, "empty stmt:pc %d \n", i);
      86           0 :                         continue;
      87             :                 }
      88     7628836 :                 if (p->token == ENDsymbol)
      89             :                         break;
      90     7175038 :                 k = off;
      91     7175038 :                 if (getModuleId(p) == sqlRef && getFunctionId(p) == tidRef
      92      187064 :                         && p->argc == 6) {
      93       86317 :                         if (depth[getArg(p, 0)] == 0) {
      94       86317 :                                 k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
      95       86317 :                                 assert(k < MAXSLICES);
      96       86317 :                                 depth[getArg(p, 0)] = k;
      97       86317 :                                 depth[getArg(p, p->retc)] = k;       /* keep order of mvc input var */
      98             :                         }
      99     7088721 :                 } else if (getModuleId(p) == sqlRef && getFunctionId(p) == bindRef
     100      930254 :                                    && p->argc == 8) {
     101      363372 :                         if (depth[getArg(p, 0)] == 0) {
     102      363372 :                                 k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
     103      363372 :                                 assert(k < MAXSLICES);
     104      363372 :                                 depth[getArg(p, 0)] = k;
     105      363372 :                                 depth[getArg(p, p->retc)] = k;       /* keep order of mvc input var */
     106             :                         }
     107             :                 } else {
     108    31690264 :                         for (j = p->retc; j < p->argc; j++) {
     109    24964915 :                                 if (depth[getArg(p, j)] > k)
     110             :                                         k = depth[getArg(p, j)];
     111             :                         }
     112     6725349 :                         assert(k < MAXSLICES);
     113    14257679 :                         for (j = 0; j < p->retc; j++)
     114     7532330 :                                 if (depth[getArg(p, j)] == 0)
     115     7532248 :                                         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     6725349 :                         if (blockStart(p)) {
     119         791 :                                 assert(btop < MAXSLICES);
     120         791 :                                 barriers[btop++] = k;
     121         791 :                                 off = k;
     122             :                         }
     123     6725349 :                         if (blockExit(p)) {
     124         791 :                                 off = 0;
     125         791 :                                 if (btop--)
     126         791 :                                         off = barriers[btop];
     127             :                         }
     128             :                 }
     129             : 
     130     7175038 :                 if (top[k] == 0) {
     131      536147 :                         blocks[k] = GDKzalloc(limit * sizeof(InstrPtr));
     132      536145 :                         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     7175036 :                 blocks[k][top[k]] = p;
     146     7175036 :                 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     7175036 :                 if (k > blkcnt)
     150             :                         blkcnt = k;
     151             :         }
     152             : 
     153     1413474 :         for (k = 0; k <= blkcnt; k++)
     154     8134750 :                 for (j = 0; j < top[k]; j++) {
     155     7175074 :                         p = blocks[k][j];
     156     7175074 :                         p->pc = pc++;
     157     7175074 :                         pushInstruction(mb, p);
     158             :                 }
     159             : 
     160    14520832 :         for (; i < limit; i++)
     161    14067038 :                 if (old[i])
     162    14067038 :                         pushInstruction(mb, old[i]);
     163    97969954 :         for (; i < slimit; i++)
     164    97516154 :                 if (old[i])
     165           0 :                         pushInstruction(mb, old[i]);
     166             : 
     167             :         /* Defense line against incorrect plans */
     168      453800 :         msg = chkTypes(cntxt->usermodule, mb, FALSE);
     169      453799 :         if (!msg)
     170      453799 :                 msg = chkFlow(mb);
     171      453795 :         if (!msg)
     172      453795 :                 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     1514786 :         for (i = 0; i <= blkcnt; i++)
     178     1027216 :                 if (top[i])
     179      536143 :                         GDKfree(blocks[i]);
     180             : 
     181             :         /* keep actions taken as a fake argument */
     182      487570 :         (void) pushInt(mb, pci, actions);
     183      487566 :         GDKfree(depth);
     184      487567 :         GDKfree(old);
     185      487567 :         return msg;
     186             : }