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 : /* (c) M. Kersten
14 : */
15 : #include "monetdb_config.h"
16 : #include "opt_prelude.h"
17 : #include "opt_support.h"
18 : #include "mal_interpreter.h"
19 : #include "mal_listing.h"
20 : #include "opt_multiplex.h"
21 : #include "optimizer_private.h"
22 : #include "manifold.h"
23 :
24 : /* Some optimizers can/need only be applied once.
25 : * The optimizer trace at the end of the MAL block
26 : * can be used to check for this.
27 : */
28 : int
29 465895 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
30 : {
31 465895 : InstrPtr p;
32 465895 : int i;
33 100941841 : for (i = mb->stop; i < mb->ssize; i++) {
34 100475946 : p = getInstrPtr(mb, i);
35 100475946 : if (p && getModuleId(p) == optimizerRef && p->token == REMsymbol
36 0 : && getFunctionId(p) == opt)
37 : return 1;
38 : }
39 : return 0;
40 : }
41 :
42 : /*
43 : * Some optimizers are interdependent (e.g. mitosis ), which
44 : * requires inspection of the pipeline attached to a MAL block.
45 : */
46 : int
47 467666 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
48 : {
49 467666 : int i;
50 467666 : InstrPtr q;
51 :
52 9506107 : for (i = mb->stop - 1; i > 0; i--) {
53 9506107 : q = getInstrPtr(mb, i);
54 9506107 : if (q->token == ENDsymbol)
55 : break;
56 9350706 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
57 8086676 : && getFunctionId(q) == opt)
58 : return 1;
59 : }
60 : return 0;
61 : }
62 :
63 : /*
64 : * Find if an optimizer 'opt' has run before the instruction 'p'.
65 : */
66 : int
67 1402945 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
68 : {
69 1402945 : bool p_found = false;
70 :
71 23316892 : for (int i = mb->stop - 1; i > 0; i--) {
72 23316924 : InstrPtr q = getInstrPtr(mb, i);
73 :
74 23316924 : p_found |= q == p; /* the optimizer to find must come before p */
75 23316924 : if (q && q->token == ENDsymbol)
76 : return 0;
77 23217374 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
78 6573280 : && getFunctionId(q) == opt)
79 : return 1;
80 : }
81 : return 0;
82 : }
83 :
84 : /* Simple insertion statements do not require complex optimizer steps */
85 : int
86 967343 : isSimpleSQL(MalBlkPtr mb)
87 : {
88 967343 : int cnt = 0;
89 :
90 32132266 : for (int i = 0; i < mb->stop; i++) {
91 31698720 : InstrPtr p = getInstrPtr(mb, i);
92 :
93 31698720 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
94 1039430 : cnt++;
95 31698720 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
96 : return 1;
97 31698013 : if (p && getModuleId(p) == sqlcatalogRef)
98 : return 1;
99 : }
100 433546 : return cnt > 0.63 * mb->stop;
101 : }
102 :
103 : /* Only used by opt_commonTerms! */
104 : int
105 161721 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
106 : {
107 161721 : int i;
108 :
109 161721 : if (q->retc != p->retc || q->argc != p->argc)
110 : return FALSE;
111 877064 : for (i = 0; i < p->argc; i++)
112 715343 : if (getArgType(mb, p, i) != getArgType(mb, q, i))
113 : return FALSE;
114 : return TRUE;
115 : }
116 :
117 : /* Only used by opt_commonTerms! */
118 : int
119 25854683 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
120 : {
121 25854683 : int k;
122 25854683 : int (*cmp)(const void *, const void *);
123 25854683 : VarPtr w, u;
124 :
125 25854683 : (void) mb;
126 25854683 : if (p->retc != q->retc || p->argc != q->argc)
127 : return FALSE;
128 : /* heuristic, because instructions are linked using last constant argument */
129 36819482 : for (k = p->argc - 1; k >= p->retc; k--)
130 36657761 : if (q->argv[k] != p->argv[k]) {
131 29561742 : if (isVarConstant(mb, getArg(p, k))
132 28219531 : && isVarConstant(mb, getArg(q, k))) {
133 28219399 : w = getVar(mb, getArg(p, k));
134 28219399 : u = getVar(mb, getArg(q, k));
135 28219399 : cmp = ATOMcompare(w->value.vtype);
136 28219399 : if (w->value.vtype == u->value.vtype
137 27836222 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
138 13004356 : continue;
139 : }
140 16555833 : return FALSE;
141 : }
142 : return TRUE;
143 : }
144 :
145 : /*
146 : * If two instructions have elements in common in their target list,
147 : * it means a variable is re-initialized and should not be considered
148 : * an alias.
149 : */
150 : int
151 161721 : hasCommonResults(InstrPtr p, InstrPtr q)
152 : {
153 161721 : int k, l;
154 :
155 331200 : for (k = 0; k < p->retc; k++)
156 355652 : for (l = 0; l < q->retc; l++)
157 186173 : if (p->argv[k] == q->argv[l])
158 : return TRUE;
159 : return FALSE;
160 : }
161 :
162 : /*
163 : * Dependency between target variables and arguments can be
164 : * checked with isDependent().
165 : */
166 : static int
167 148253 : isDependent(InstrPtr p, InstrPtr q)
168 : {
169 148253 : int i, j;
170 304264 : for (i = 0; i < q->retc; i++)
171 712652 : for (j = p->retc; j < p->argc; j++)
172 556641 : if (getArg(q, i) == getArg(p, j))
173 : return TRUE;
174 : return FALSE;
175 : }
176 :
177 : /*
178 : * The safety property should be relatively easy to determine for
179 : * each MAL function. This calls for accessing the function MAL block
180 : * and to inspect the arguments of the signature.
181 : */
182 : inline int
183 125011511 : isUnsafeFunction(InstrPtr q)
184 : {
185 125011511 : InstrPtr p;
186 :
187 125011511 : if (q->fcn == 0 || getFunctionId(q) == 0 || q->blk == NULL)
188 : return FALSE;
189 123316014 : p = getInstrPtr(q->blk, 0);
190 123316014 : if (p->retc == 0)
191 : return TRUE;
192 123316014 : return q->blk->unsafeProp;
193 : }
194 :
195 : /*
196 : * Instructions are unsafe if one of the arguments is also mentioned
197 : * in the result list. Alternatively, the 'unsafe' property is set
198 : * for the function call itself.
199 : */
200 : int
201 0 : isUnsafeInstruction(InstrPtr q)
202 : {
203 0 : int j, k;
204 :
205 0 : for (j = 0; j < q->retc; j++)
206 0 : for (k = q->retc; k < q->argc; k++)
207 0 : if (q->argv[k] == q->argv[j])
208 : return TRUE;
209 : return FALSE;
210 : }
211 :
212 : /*
213 : * Any instruction may block identification of a common
214 : * subexpression. It suffices to stumble upon an unsafe function
215 : * whose parameter lists has a non-empty intersection with the
216 : * targeted instruction.
217 : * To illustrate, consider the sequence
218 : * @example
219 : * L1 := f(A,B,C);
220 : * ...
221 : * G1 := g(D,E,F);
222 : * ...
223 : * l2:= f(A,B,C);
224 : * ...
225 : * L2:= h()
226 : * @end example
227 : *
228 : * The instruction G1:=g(D,E,F) is blocking if G1 is an alias
229 : * for @verb{ { }A,B,C@verb{ } }.
230 : * Alternatively, function g() may be unsafe and @verb{ { }D,E,F@verb{ } }
231 : * has a non-empty intersection with @verb{ { }A,B,C@verb{ } }.
232 : * An alias can only be used later on for readonly (and not be used for a function with side effects).
233 : */
234 : int
235 148253 : safetyBarrier(InstrPtr p, InstrPtr q)
236 : {
237 148253 : int i, j;
238 148253 : if (isDependent(q, p))
239 : return TRUE;
240 148253 : if (isUnsafeFunction(q)) {
241 0 : for (i = p->retc; i < p->argc; i++)
242 0 : for (j = q->retc; j < q->argc; j++)
243 0 : if (p->argv[i] == q->argv[j]) {
244 : /* TODO check safety property of the argument */
245 : return TRUE;
246 : }
247 : }
248 : return FALSE;
249 : }
250 :
251 : inline int
252 128790786 : isUpdateInstruction(InstrPtr p)
253 : {
254 128790786 : if (getModuleId(p) == sqlRef &&
255 28802166 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
256 26264942 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
257 26188231 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
258 26187803 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
259 26107475 : || getFunctionId(p) == predicateRef))
260 : return TRUE;
261 126050221 : if (getModuleId(p) == batRef
262 9215086 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
263 7730077 : || getFunctionId(p) == deleteRef))
264 1485053 : return TRUE;
265 : return FALSE;
266 : }
267 :
268 : int
269 104033340 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
270 : {
271 104033340 : if (getFunctionId(p) == NULL)
272 : return FALSE;
273 :
274 : /*
275 : * Void-returning operations have side-effects and
276 : * should be considered as such
277 : */
278 101271009 : if (p->retc == 0 || (p->retc == 1 && getArgType(mb, p, 0) == TYPE_void))
279 : return TRUE;
280 :
281 : /*
282 : * Any function marked as unsafe can not be moved around without
283 : * affecting its behavior on the program. For example, because they
284 : * check for volatile resource levels.
285 : */
286 95694962 : if (isUnsafeFunction(p))
287 : return TRUE;
288 :
289 : /* update instructions have side effects, they can be marked as unsafe */
290 94506017 : if (isUpdateInstruction(p))
291 : return TRUE;
292 :
293 92112732 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
294 15181142 : && (getFunctionId(p) == setAccessRef))
295 : return TRUE;
296 :
297 92112732 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
298 : return FALSE;
299 :
300 92108529 : if (getModuleId(p) == ioRef ||
301 92108529 : getModuleId(p) == streamsRef ||
302 92108529 : getModuleId(p) == bstreamRef ||
303 92108529 : getModuleId(p) == mdbRef ||
304 92107900 : getModuleId(p) == malRef ||
305 92107900 : getModuleId(p) == remapRef ||
306 92107900 : getModuleId(p) == optimizerRef ||
307 47627233 : getModuleId(p) == lockRef ||
308 47627233 : getModuleId(p) == semaRef ||
309 47627233 : getModuleId(p) == alarmRef)
310 : return TRUE;
311 :
312 47627233 : if( getModuleId(p) == pyapi3Ref ||
313 47627232 : getModuleId(p) == rapiRef ||
314 47627092 : getModuleId(p) == capiRef)
315 : return TRUE;
316 :
317 47626941 : if (getModuleId(p) == sqlcatalogRef)
318 : return TRUE;
319 47626941 : if (getModuleId(p) == sqlRef) {
320 11315927 : if (getFunctionId(p) == tidRef)
321 : return FALSE;
322 9862631 : if (getFunctionId(p) == deltaRef)
323 : return FALSE;
324 8807874 : if (getFunctionId(p) == subdeltaRef)
325 : return FALSE;
326 8607224 : if (getFunctionId(p) == projectdeltaRef)
327 : return FALSE;
328 8069390 : if (getFunctionId(p) == bindRef)
329 : return FALSE;
330 1097930 : if (getFunctionId(p) == bindidxRef)
331 : return FALSE;
332 1082099 : if (getFunctionId(p) == binddbatRef)
333 : return FALSE;
334 1082099 : if (getFunctionId(p) == columnBindRef)
335 : return FALSE;
336 1082099 : if (getFunctionId(p) == copy_fromRef)
337 : return FALSE;
338 : /* assertions are the end-point of a flow path */
339 1082099 : if (getFunctionId(p) == not_uniqueRef)
340 : return FALSE;
341 1082099 : if (getFunctionId(p) == zero_or_oneRef)
342 : return FALSE;
343 1082099 : if (getFunctionId(p) == mvcRef)
344 : return FALSE;
345 13559 : if (getFunctionId(p) == singleRef)
346 : return FALSE;
347 13559 : if (getFunctionId(p) == importColumnRef)
348 : return FALSE;
349 12474 : return TRUE;
350 : }
351 36311014 : if (getModuleId(p) == mapiRef) {
352 0 : if (getFunctionId(p) == rpcRef)
353 : return TRUE;
354 0 : if (getFunctionId(p) == reconnectRef)
355 : return TRUE;
356 0 : if (getFunctionId(p) == disconnectRef)
357 : return TRUE;
358 : }
359 36311014 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
360 : return TRUE;
361 :
362 36003653 : if (getModuleId(p) == sqlcatalogRef)
363 : return TRUE;
364 36003653 : if (getModuleId(p) == remoteRef)
365 36856 : return TRUE;
366 : return FALSE;
367 : }
368 :
369 : /* Void returning functions always have side-effects.
370 : */
371 : int
372 16327569 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
373 : {
374 16327569 : int tpe;
375 16327569 : tpe = getVarType(mb, getArg(p, 0));
376 16327569 : if (tpe == TYPE_void)
377 : return TRUE;
378 15897382 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
379 15895639 : return hasSideEffects(mb, p, strict);
380 : // a manifold instruction can also have side effects.
381 : // for this to check we need the function signature, not its function address.
382 : // The easy way out now is to consider all manifold instructions as potentially having side effects.
383 1743 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
384 : return TRUE;
385 1743 : if (MANIFOLDtypecheck(cntxt, mb, p, 1) == NULL)
386 : return TRUE;
387 : return FALSE;
388 : }
389 :
390 : /*
391 : * Side-effect free functions are crucial for several operators.
392 : */
393 : int
394 227 : isSideEffectFree(MalBlkPtr mb)
395 : {
396 227 : int i;
397 10334 : for (i = 1; i < mb->stop && getInstrPtr(mb, i)->token != ENDsymbol; i++) {
398 10116 : if (hasSideEffects(mb, getInstrPtr(mb, i), TRUE))
399 : return FALSE;
400 : }
401 : return TRUE;
402 : }
403 :
404 : /*
405 : * Breaking up a MAL program into pieces for distributed processing requires
406 : * identification of (partial) blocking instructions. A conservative
407 : * definition can be used.
408 : */
409 : inline int
410 0 : isBlocking(InstrPtr p)
411 : {
412 0 : if (blockStart(p) || blockExit(p) || blockCntrl(p))
413 : return TRUE;
414 :
415 0 : if (getFunctionId(p) == sortRef)
416 : return TRUE;
417 :
418 0 : if (getModuleId(p) == aggrRef || getModuleId(p) == groupRef
419 0 : || getModuleId(p) == sqlcatalogRef)
420 0 : return TRUE;
421 : return FALSE;
422 : }
423 :
424 : /*
425 : * Used in the merge table optimizer. It is built incrementally
426 : * and should be conservative.
427 : */
428 :
429 : static int
430 301182 : isOrderDepenent(InstrPtr p)
431 : {
432 301182 : if (getModuleId(p) != batsqlRef)
433 : return 0;
434 1096 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
435 994 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
436 851 : || getFunctionId(p) == dense_rankRef
437 838 : || getFunctionId(p) == percent_rankRef
438 833 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
439 813 : || getFunctionId(p) == first_valueRef
440 805 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
441 802 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
442 797 : || getFunctionId(p) == corrRef)
443 307 : return 1;
444 : return 0;
445 : }
446 :
447 : inline int
448 14617970 : isMapOp(InstrPtr p)
449 : {
450 14617970 : if (isUnsafeFunction(p))
451 : return 0;
452 14471485 : return getModuleId(p)
453 14122099 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
454 518 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
455 14121581 : || (getModuleId(p) == batcalcRef)
456 13920890 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
457 13363368 : && strncmp(getModuleId(p), "bat", 3) == 0)
458 14122099 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
459 215675 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
460 14687147 : && getModuleId(p) != batcapiRef;
461 : }
462 :
463 : inline int
464 184263 : isMap2Op(InstrPtr p)
465 : {
466 184263 : if (isUnsafeFunction(p))
467 : return 0;
468 184193 : return getModuleId(p)
469 184192 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
470 158 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
471 184034 : || (getModuleId(p) == batcalcRef)
472 102226 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
473 78003 : && strncmp(getModuleId(p), "bat", 3) == 0)
474 184192 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
475 85200 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
476 269389 : && getModuleId(p) != batcapiRef;
477 : }
478 :
479 : inline int
480 17655140 : isLikeOp(InstrPtr p)
481 : {
482 17655140 : return (getModuleId(p) == batalgebraRef
483 17655140 : && (getFunctionId(p) == likeRef
484 19 : || getFunctionId(p) == not_likeRef));
485 : }
486 :
487 : inline int
488 176049 : isTopn(InstrPtr p)
489 : {
490 49833 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
491 225757 : || isSlice(p));
492 : }
493 :
494 : inline int
495 35752553 : isSlice(InstrPtr p)
496 : {
497 35752553 : return (getModuleId(p) == algebraRef
498 35752553 : && (getFunctionId(p) == subsliceRef
499 3428504 : || getFunctionId(p) == sliceRef));
500 : }
501 :
502 : int
503 18891446 : isSample(InstrPtr p)
504 : {
505 18891446 : return (getModuleId(p) == sampleRef && getFunctionId(p) == subuniformRef);
506 : }
507 :
508 : inline int
509 0 : isOrderby(InstrPtr p)
510 : {
511 0 : return getModuleId(p) == algebraRef && getFunctionId(p) == sortRef;
512 : }
513 :
514 : inline int
515 1419020 : isMatJoinOp(InstrPtr p)
516 : {
517 1419020 : return (isSubJoin(p)
518 1419020 : || (getModuleId(p) == algebraRef
519 901490 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
520 884113 : || getFunctionId(p) == thetajoinRef
521 884113 : || getFunctionId(p) == bandjoinRef
522 884113 : || getFunctionId(p) == rangejoinRef)
523 : ));
524 : }
525 :
526 : inline int
527 1249601 : isMatLeftJoinOp(InstrPtr p)
528 : {
529 1249601 : return (getModuleId(p) == algebraRef
530 1249601 : && (getFunctionId(p) == leftjoinRef
531 978857 : || getFunctionId(p) == outerjoinRef
532 978852 : || getFunctionId(p) == markjoinRef));
533 : }
534 :
535 : inline int
536 100403 : isDelta(InstrPtr p)
537 : {
538 100403 : return (getModuleId(p) == sqlRef
539 100403 : && (getFunctionId(p) == deltaRef
540 31656 : || getFunctionId(p) == projectdeltaRef
541 11563 : || getFunctionId(p) == subdeltaRef)
542 : );
543 : }
544 :
545 : int
546 18149 : isFragmentGroup2(InstrPtr p)
547 : {
548 18149 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
549 : return TRUE;
550 12 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
551 8975 : || (getModuleId(p) == batRef
552 8787 : && (getFunctionId(p) == mergecandRef
553 0 : || getFunctionId(p) == intersectcandRef
554 0 : || getFunctionId(p) == diffcandRef)
555 : );
556 : }
557 :
558 : inline int
559 34872713 : isSelect(InstrPtr p)
560 : {
561 34872713 : const char *func = getFunctionId(p);
562 67201143 : size_t l = func ? strlen(func) : 0;
563 :
564 33537601 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
565 : }
566 :
567 : inline int
568 1419020 : isSubJoin(InstrPtr p)
569 : {
570 1419020 : const char *func = getFunctionId(p);
571 2732265 : size_t l = func ? strlen(func) : 0;
572 :
573 1418934 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
574 : }
575 :
576 : inline int
577 77404781 : isMultiplex(InstrPtr p)
578 : {
579 77404781 : return (malRef && (getModuleId(p) == malRef || getModuleId(p) == batmalRef)
580 77720662 : && getFunctionId(p) == multiplexRef);
581 : }
582 :
583 : int
584 98917 : isFragmentGroup(InstrPtr p)
585 : {
586 98917 : return (getModuleId(p) == algebraRef
587 74527 : && (getFunctionId(p) == projectRef
588 83436 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
589 123313 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
590 : }
|
