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, 2025 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 540790 : OPTreorderImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk,
48 : InstrPtr pci)
49 : {
50 540790 : int i, j, k, blkcnt = 1, pc = 0, actions = 0;
51 540790 : InstrPtr p = NULL, *old = NULL;
52 540790 : int limit, slimit, *depth = NULL;
53 540790 : str msg = MAL_SUCCEED;
54 540790 : InstrPtr *blocks[MAXSLICES] = { 0 };
55 540790 : int top[MAXSLICES] = { 0 };
56 540790 : int barriers[MAXSLICES] = { 0 }, btop = 0, off = 0;
57 :
58 540790 : for (i = 0; i < MAXSLICES; i++)
59 : top[i] = 0;
60 540790 : if (isOptimizerUsed(mb, pci, mitosisRef) <= 0) {
61 33757 : goto wrapup;
62 : }
63 506993 : (void) cntxt;
64 506993 : (void) stk;
65 :
66 506993 : limit = mb->stop;
67 506993 : slimit = mb->ssize;
68 506993 : old = mb->stmt;
69 :
70 506993 : depth = (int *) GDKzalloc(mb->vtop * sizeof(int));
71 507007 : if (depth == NULL) {
72 0 : throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
73 : }
74 :
75 507007 : if (newMalBlkStmt(mb, mb->ssize) < 0) {
76 0 : GDKfree(depth);
77 0 : throw(MAL, "optimizer.reorder", SQLSTATE(HY013) MAL_MALLOC_FAIL);
78 : }
79 :
80 12356051 : actions = 1;
81 : /* Mark the parameters as constants as belonging to depth 0; */
82 12356051 : for (i = 0; i < limit; i++) {
83 12356084 : p = old[i];
84 12356084 : if (!p) {
85 : //mnstr_printf(cntxt->fdout, "empty stmt:pc %d \n", i);
86 0 : continue;
87 : }
88 12356084 : if (p->token == ENDsymbol)
89 : break;
90 11849105 : k = off;
91 11849105 : if (getModuleId(p) == sqlRef && getFunctionId(p) == tidRef
92 308009 : && p->argc == 6) {
93 210742 : if (depth[getArg(p, 0)] == 0) {
94 210742 : k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
95 210742 : assert(k < MAXSLICES);
96 210742 : depth[getArg(p, 0)] = k;
97 210742 : depth[getArg(p, p->retc)] = k; /* keep order of mvc input var */
98 : }
99 11638363 : } else if (getModuleId(p) == sqlRef && getFunctionId(p) == bindRef
100 1567088 : && p->argc == 8) {
101 730848 : if (depth[getArg(p, 0)] == 0) {
102 730848 : k = getVarConstant(mb, getArg(p, p->argc - 2)).val.ival;
103 730848 : assert(k < MAXSLICES);
104 730848 : depth[getArg(p, 0)] = k;
105 730848 : depth[getArg(p, p->retc)] = k; /* keep order of mvc input var */
106 : }
107 : } else {
108 51753282 : for (j = p->retc; j < p->argc; j++) {
109 40845767 : if (depth[getArg(p, j)] > k)
110 : k = depth[getArg(p, j)];
111 : }
112 10907515 : assert(k < MAXSLICES);
113 23262895 : for (j = 0; j < p->retc; j++)
114 12355380 : if (depth[getArg(p, j)] == 0)
115 12355274 : 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 10907515 : if (blockStart(p)) {
119 863 : assert(btop < MAXSLICES);
120 863 : barriers[btop++] = k;
121 863 : off = k;
122 : }
123 10907515 : if (blockExit(p)) {
124 863 : off = 0;
125 863 : if (btop--)
126 863 : off = barriers[btop];
127 : }
128 : }
129 :
130 11849105 : if (top[k] == 0) {
131 685908 : blocks[k] = GDKzalloc(limit * sizeof(InstrPtr));
132 685844 : 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 11849041 : blocks[k][top[k]] = p;
146 11849041 : 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 11849041 : if (k > blkcnt)
150 : blkcnt = k;
151 : }
152 :
153 1668023 : for (k = 0; k <= blkcnt; k++)
154 13010013 : for (j = 0; j < top[k]; j++) {
155 11848936 : p = blocks[k][j];
156 11848936 : p->pc = pc++;
157 11848936 : pushInstruction(mb, p);
158 : }
159 :
160 16220522 : for (; i < limit; i++)
161 15713523 : if (old[i])
162 15713523 : pushInstruction(mb, old[i]);
163 109181266 : for (; i < slimit; i++)
164 108674261 : if (old[i])
165 0 : pushInstruction(mb, old[i]);
166 :
167 : /* Defense line against incorrect plans */
168 507005 : msg = chkTypes(cntxt->usermodule, mb, FALSE);
169 506990 : if (!msg)
170 506976 : msg = chkFlow(mb);
171 506946 : if (!msg)
172 506946 : 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 1769395 : for (i = 0; i <= blkcnt; i++)
178 1228618 : if (top[i])
179 685874 : GDKfree(blocks[i]);
180 :
181 : /* keep actions taken as a fake argument */
182 540777 : (void) pushInt(mb, pci, actions);
183 540744 : GDKfree(depth);
184 540779 : GDKfree(old);
185 540779 : return msg;
186 : }
|
