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 : /* (c) M. Kersten
14 : */
15 : #include "monetdb_config.h"
16 : #include "opt_support.h"
17 : #include "mal_interpreter.h"
18 : #include "mal_listing.h"
19 : #include "opt_multiplex.h"
20 : #include "optimizer_private.h"
21 : #include "manifold.h"
22 :
23 : /* Some optimizers can/need only be applied once.
24 : * The optimizer trace at the end of the MAL block
25 : * can be used to check for this.
26 : */
27 : int
28 534643 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
29 : {
30 534643 : InstrPtr p;
31 534643 : int i;
32 116229412 : for (i = mb->stop; i < mb->ssize; i++) {
33 115694769 : p = getInstrPtr(mb, i);
34 115694769 : if (p && getModuleId(p) == optimizerRef && p->token == REMsymbol
35 0 : && getFunctionId(p) == opt)
36 : return 1;
37 : }
38 : return 0;
39 : }
40 :
41 : /*
42 : * Some optimizers are interdependent (e.g. mitosis ), which
43 : * requires inspection of the pipeline attached to a MAL block.
44 : */
45 : int
46 536484 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
47 : {
48 536484 : int i;
49 536484 : InstrPtr q;
50 :
51 10842506 : for (i = mb->stop - 1; i > 0; i--) {
52 10842506 : q = getInstrPtr(mb, i);
53 10842506 : if (q->token == ENDsymbol)
54 : break;
55 10679512 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
56 9339727 : && getFunctionId(q) == opt)
57 : return 1;
58 : }
59 : return 0;
60 : }
61 :
62 : /*
63 : * Find if an optimizer 'opt' has run before the instruction 'p'.
64 : */
65 : int
66 1609304 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
67 : {
68 1609304 : bool p_found = false;
69 :
70 26960907 : for (int i = mb->stop - 1; i > 0; i--) {
71 26960968 : InstrPtr q = getInstrPtr(mb, i);
72 :
73 26960968 : p_found |= q == p; /* the optimizer to find must come before p */
74 26960968 : if (q && q->token == ENDsymbol)
75 : return 0;
76 26861341 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
77 7605130 : && getFunctionId(q) == opt)
78 : return 1;
79 : }
80 : return 0;
81 : }
82 :
83 : /* Simple insertion statements do not require complex optimizer steps */
84 : int
85 1104910 : isSimpleSQL(MalBlkPtr mb)
86 : {
87 1104910 : int cnt = 0;
88 :
89 37222113 : for (int i = 0; i < mb->stop; i++) {
90 36700102 : InstrPtr p = getInstrPtr(mb, i);
91 :
92 36700102 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
93 1163627 : cnt++;
94 36700102 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
95 : return 1;
96 36699349 : if (p && getModuleId(p) == sqlcatalogRef)
97 : return 1;
98 : }
99 522011 : return cnt > 0.63 * mb->stop;
100 : }
101 :
102 : /* Only used by opt_commonTerms! */
103 : int
104 152823 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
105 : {
106 152823 : int i;
107 :
108 152823 : if (q->retc != p->retc || q->argc != p->argc)
109 : return FALSE;
110 841120 : for (i = 0; i < p->argc; i++)
111 688315 : if (getArgType(mb, p, i) != getArgType(mb, q, i))
112 : return FALSE;
113 : return TRUE;
114 : }
115 :
116 : /* Only used by opt_commonTerms! */
117 : int
118 28464849 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
119 : {
120 28464849 : int k;
121 28464849 : int (*cmp)(const void *, const void *);
122 28464849 : VarPtr w, u;
123 :
124 28464849 : (void) mb;
125 28464849 : if (p->retc != q->retc || p->argc != q->argc)
126 : return FALSE;
127 : /* heuristic, because instructions are linked using last constant argument */
128 39882468 : for (k = p->argc - 1; k >= p->retc; k--)
129 39729645 : if (q->argv[k] != p->argv[k]) {
130 31749064 : if (isVarConstant(mb, getArg(p, k))
131 30123547 : && isVarConstant(mb, getArg(q, k))) {
132 30123416 : w = getVar(mb, getArg(p, k));
133 30123416 : u = getVar(mb, getArg(q, k));
134 30123416 : cmp = ATOMcompare(w->value.vtype);
135 30123416 : if (w->value.vtype == u->value.vtype
136 29700459 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
137 13827688 : continue;
138 : }
139 17919653 : return FALSE;
140 : }
141 : return TRUE;
142 : }
143 :
144 : /*
145 : * If two instructions have elements in common in their target list,
146 : * it means a variable is re-initialized and should not be considered
147 : * an alias.
148 : */
149 : int
150 152805 : hasCommonResults(InstrPtr p, InstrPtr q)
151 : {
152 152805 : int k, l;
153 :
154 315522 : for (k = 0; k < p->retc; k++)
155 346530 : for (l = 0; l < q->retc; l++)
156 183813 : if (p->argv[k] == q->argv[l])
157 : return TRUE;
158 : return FALSE;
159 : }
160 :
161 : /*
162 : * Dependency between target variables and arguments can be
163 : * checked with isDependent().
164 : */
165 : static int
166 137686 : isDependent(InstrPtr p, InstrPtr q)
167 : {
168 137686 : int i, j;
169 285284 : for (i = 0; i < q->retc; i++)
170 692796 : for (j = p->retc; j < p->argc; j++)
171 545198 : if (getArg(q, i) == getArg(p, j))
172 : return TRUE;
173 : return FALSE;
174 : }
175 :
176 : /*
177 : * The safety property should be relatively easy to determine for
178 : * each MAL function. This calls for accessing the function MAL block
179 : * and to inspect the arguments of the signature.
180 : */
181 : inline int
182 141470477 : isUnsafeFunction(InstrPtr q)
183 : {
184 141470477 : InstrPtr p;
185 :
186 141470477 : if (q->unsafeProp)
187 : return TRUE;
188 139446871 : if (q->fcn == 0 || getFunctionId(q) == 0 || q->blk == NULL)
189 : return FALSE;
190 0 : p = getInstrPtr(q->blk, 0);
191 0 : if (p->retc == 0)
192 0 : return TRUE;
193 : return FALSE;
194 : }
195 :
196 : /*
197 : * Instructions are unsafe if one of the arguments is also mentioned
198 : * in the result list. Alternatively, the 'unsafe' property is set
199 : * for the function call itself.
200 : */
201 : int
202 0 : isUnsafeInstruction(InstrPtr q)
203 : {
204 0 : int j, k;
205 :
206 0 : for (j = 0; j < q->retc; j++)
207 0 : for (k = q->retc; k < q->argc; k++)
208 0 : if (q->argv[k] == q->argv[j])
209 : return TRUE;
210 : return FALSE;
211 : }
212 :
213 : /*
214 : * Any instruction may block identification of a common
215 : * subexpression. It suffices to stumble upon an unsafe function
216 : * whose parameter lists has a non-empty intersection with the
217 : * targeted instruction.
218 : * To illustrate, consider the sequence
219 : * @example
220 : * L1 := f(A,B,C);
221 : * ...
222 : * G1 := g(D,E,F);
223 : * ...
224 : * l2:= f(A,B,C);
225 : * ...
226 : * L2:= h()
227 : * @end example
228 : *
229 : * The instruction G1:=g(D,E,F) is blocking if G1 is an alias
230 : * for @verb{ { }A,B,C@verb{ } }.
231 : * Alternatively, function g() may be unsafe and @verb{ { }D,E,F@verb{ } }
232 : * has a non-empty intersection with @verb{ { }A,B,C@verb{ } }.
233 : * An alias can only be used later on for readonly (and not be used for a function with side effects).
234 : */
235 : int
236 137686 : safetyBarrier(InstrPtr p, InstrPtr q)
237 : {
238 137686 : int i, j;
239 137686 : if (isDependent(q, p))
240 : return TRUE;
241 137686 : if (isUnsafeFunction(q)) {
242 0 : for (i = p->retc; i < p->argc; i++)
243 0 : for (j = q->retc; j < q->argc; j++)
244 0 : if (p->argv[i] == q->argv[j]) {
245 : /* TODO check safety property of the argument */
246 : return TRUE;
247 : }
248 : }
249 : return FALSE;
250 : }
251 :
252 : inline int
253 145981300 : isUpdateInstruction(InstrPtr p)
254 : {
255 145981300 : if (getModuleId(p) == sqlRef &&
256 33280416 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
257 30431020 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
258 30347118 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
259 30346667 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
260 30257881 : || getFunctionId(p) == predicateRef))
261 : return TRUE;
262 142910064 : if (getModuleId(p) == batRef
263 10101055 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
264 8463016 : || getFunctionId(p) == deleteRef))
265 1638083 : return TRUE;
266 : return FALSE;
267 : }
268 :
269 : int
270 117893215 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
271 : {
272 117893215 : if (getFunctionId(p) == NULL)
273 : return FALSE;
274 :
275 : /*
276 : * Void-returning operations have side-effects and
277 : * should be considered as such
278 : */
279 114872138 : if (p->retc == 0 || (p->retc == 1 && getArgType(mb, p, 0) == TYPE_void))
280 : return TRUE;
281 :
282 : /*
283 : * Any function marked as unsafe can not be moved around without
284 : * affecting its behavior on the program. For example, because they
285 : * check for volatile resource levels.
286 : */
287 108327729 : if (isUnsafeFunction(p))
288 : return TRUE;
289 :
290 : /* update instructions have side effects, they can be marked as unsafe */
291 107069672 : if (isUpdateInstruction(p))
292 : return TRUE;
293 :
294 104365231 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
295 17012666 : && (getFunctionId(p) == setAccessRef))
296 : return TRUE;
297 :
298 104365231 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
299 : return FALSE;
300 :
301 104354927 : if (getModuleId(p) == ioRef ||
302 104354927 : getModuleId(p) == streamsRef ||
303 104354927 : getModuleId(p) == bstreamRef ||
304 104354922 : getModuleId(p) == mdbRef ||
305 104354287 : getModuleId(p) == malRef ||
306 104354287 : getModuleId(p) == remapRef ||
307 52355782 : getModuleId(p) == optimizerRef ||
308 52355782 : getModuleId(p) == lockRef ||
309 52355782 : getModuleId(p) == semaRef ||
310 : getModuleId(p) == alarmRef)
311 : return TRUE;
312 :
313 52355782 : if( getModuleId(p) == pyapi3Ref ||
314 52355642 : getModuleId(p) == rapiRef ||
315 : getModuleId(p) == capiRef)
316 : return TRUE;
317 :
318 52355484 : if (getModuleId(p) == sqlcatalogRef)
319 : return TRUE;
320 52355484 : if (getModuleId(p) == sqlRef) {
321 12809982 : if (getFunctionId(p) == tidRef)
322 : return FALSE;
323 10912251 : if (getFunctionId(p) == deltaRef)
324 : return FALSE;
325 9656596 : if (getFunctionId(p) == subdeltaRef)
326 : return FALSE;
327 9411444 : if (getFunctionId(p) == projectdeltaRef)
328 : return FALSE;
329 8746050 : if (getFunctionId(p) == bindRef)
330 : return FALSE;
331 1209289 : if (getFunctionId(p) == bindidxRef)
332 : return FALSE;
333 1193578 : if (getFunctionId(p) == binddbatRef)
334 : return FALSE;
335 1193578 : if (getFunctionId(p) == columnBindRef)
336 : return FALSE;
337 1193578 : if (getFunctionId(p) == copy_fromRef)
338 : return FALSE;
339 : /* assertions are the end-point of a flow path */
340 1193578 : if (getFunctionId(p) == not_uniqueRef)
341 : return FALSE;
342 1193578 : if (getFunctionId(p) == zero_or_oneRef)
343 : return FALSE;
344 1193578 : if (getFunctionId(p) == mvcRef)
345 : return FALSE;
346 17119 : if (getFunctionId(p) == singleRef)
347 : return FALSE;
348 17119 : if (getFunctionId(p) == importColumnRef)
349 : return FALSE;
350 16039 : return TRUE;
351 : }
352 39545502 : if (getModuleId(p) == mapiRef) {
353 0 : if (getFunctionId(p) == rpcRef)
354 : return TRUE;
355 0 : if (getFunctionId(p) == reconnectRef)
356 : return TRUE;
357 0 : if (getFunctionId(p) == disconnectRef)
358 : return TRUE;
359 : }
360 39545502 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
361 : return TRUE;
362 :
363 39220564 : if (getModuleId(p) == sqlcatalogRef)
364 : return TRUE;
365 39220564 : if (getModuleId(p) == remoteRef)
366 37417 : return TRUE;
367 : return FALSE;
368 : }
369 :
370 : /* Void returning functions always have side-effects.
371 : */
372 : int
373 17910143 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
374 : {
375 17910143 : int tpe;
376 17910143 : tpe = getVarType(mb, getArg(p, 0));
377 17910143 : if (tpe == TYPE_void)
378 : return TRUE;
379 17358946 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
380 17355352 : return hasSideEffects(mb, p, strict);
381 : // a manifold instruction can also have side effects.
382 : // for this to check we need the function signature, not its function address.
383 : // The easy way out now is to consider all manifold instructions as potentially having side effects.
384 3594 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
385 : return TRUE;
386 3594 : if (MANIFOLDtypecheck(cntxt, mb, p, 1) == NULL)
387 : return TRUE;
388 : return FALSE;
389 : }
390 :
391 : /*
392 : * Side-effect free functions are crucial for several operators.
393 : */
394 : int
395 266 : isSideEffectFree(MalBlkPtr mb)
396 : {
397 266 : int i;
398 4256 : for (i = 1; i < mb->stop && getInstrPtr(mb, i)->token != ENDsymbol; i++) {
399 4037 : if (hasSideEffects(mb, getInstrPtr(mb, i), TRUE))
400 : return FALSE;
401 : }
402 : return TRUE;
403 : }
404 :
405 : /*
406 : * Breaking up a MAL program into pieces for distributed processing requires
407 : * identification of (partial) blocking instructions. A conservative
408 : * definition can be used.
409 : */
410 : inline int
411 0 : isBlocking(InstrPtr p)
412 : {
413 0 : if (blockStart(p) || blockExit(p) || blockCntrl(p))
414 : return TRUE;
415 :
416 0 : if (getFunctionId(p) == sortRef)
417 : return TRUE;
418 :
419 0 : if (getModuleId(p) == aggrRef || getModuleId(p) == groupRef
420 0 : || getModuleId(p) == sqlcatalogRef)
421 0 : return TRUE;
422 : return FALSE;
423 : }
424 :
425 : /*
426 : * Used in the merge table optimizer. It is built incrementally
427 : * and should be conservative.
428 : */
429 :
430 : static int
431 264808 : isOrderDepenent(InstrPtr p)
432 : {
433 264808 : if (getModuleId(p) != batsqlRef)
434 : return 0;
435 950 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
436 842 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
437 706 : || getFunctionId(p) == dense_rankRef
438 694 : || getFunctionId(p) == percent_rankRef
439 689 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
440 677 : || getFunctionId(p) == first_valueRef
441 669 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
442 666 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
443 664 : || getFunctionId(p) == corrRef)
444 294 : return 1;
445 : return 0;
446 : }
447 :
448 : inline int
449 17012965 : isMapOp(InstrPtr p)
450 : {
451 17012965 : if (isUnsafeFunction(p))
452 : return 0;
453 16828600 : return getModuleId(p)
454 16415551 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
455 1172 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
456 16414379 : || (getModuleId(p) == batcalcRef)
457 16240650 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
458 15640184 : && strncmp(getModuleId(p), "bat", 3) == 0)
459 16415551 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
460 191282 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
461 17019869 : && getModuleId(p) != batcapiRef;
462 : }
463 :
464 : inline int
465 229289 : isMap2Op(InstrPtr p)
466 : {
467 229289 : if (isUnsafeFunction(p))
468 : return 0;
469 229219 : return getModuleId(p)
470 229218 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
471 580 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
472 228638 : || (getModuleId(p) == batcalcRef)
473 161049 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
474 114210 : && strncmp(getModuleId(p), "bat", 3) == 0)
475 229218 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
476 73232 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
477 302447 : && getModuleId(p) != batcapiRef;
478 : }
479 :
480 : inline int
481 20096782 : isLikeOp(InstrPtr p)
482 : {
483 20096782 : return (getModuleId(p) == batalgebraRef
484 20096782 : && (getFunctionId(p) == likeRef
485 132 : || getFunctionId(p) == not_likeRef));
486 : }
487 :
488 : inline int
489 215492 : isTopn(InstrPtr p)
490 : {
491 73984 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
492 215492 : || isSlice(p));
493 : }
494 :
495 : inline int
496 40557177 : isSlice(InstrPtr p)
497 : {
498 40557177 : return (getModuleId(p) == algebraRef
499 40557177 : && (getFunctionId(p) == subsliceRef
500 3555978 : || getFunctionId(p) == sliceRef));
501 : }
502 :
503 : int
504 21556015 : isSample(InstrPtr p)
505 : {
506 21556015 : return (getModuleId(p) == sampleRef && getFunctionId(p) == subuniformRef);
507 : }
508 :
509 : inline int
510 0 : isOrderby(InstrPtr p)
511 : {
512 0 : return getModuleId(p) == algebraRef && getFunctionId(p) == sortRef;
513 : }
514 :
515 : inline int
516 1602094 : isMatJoinOp(InstrPtr p)
517 : {
518 1602094 : return (isSubJoin(p)
519 1602094 : || (getModuleId(p) == algebraRef
520 1014645 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
521 996545 : || getFunctionId(p) == thetajoinRef
522 996545 : || getFunctionId(p) == bandjoinRef
523 996545 : || getFunctionId(p) == rangejoinRef)
524 : ));
525 : }
526 :
527 : inline int
528 1418325 : isMatLeftJoinOp(InstrPtr p)
529 : {
530 1418325 : return (getModuleId(p) == algebraRef
531 1418325 : && (getFunctionId(p) == leftjoinRef
532 1115490 : || getFunctionId(p) == outerjoinRef
533 1115472 : || getFunctionId(p) == markjoinRef));
534 : }
535 :
536 : inline int
537 138759 : isDelta(InstrPtr p)
538 : {
539 138759 : return (getModuleId(p) == sqlRef
540 138759 : && (getFunctionId(p) == deltaRef
541 46009 : || getFunctionId(p) == projectdeltaRef
542 15571 : || getFunctionId(p) == subdeltaRef)
543 : );
544 : }
545 :
546 : int
547 35942 : isFragmentGroup2(InstrPtr p)
548 : {
549 35942 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
550 : return TRUE;
551 10 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
552 12178 : || (getModuleId(p) == batRef
553 8937 : && (getFunctionId(p) == mergecandRef
554 0 : || getFunctionId(p) == intersectcandRef
555 0 : || getFunctionId(p) == diffcandRef)
556 : );
557 : }
558 :
559 : inline int
560 39679862 : isSelect(InstrPtr p)
561 : {
562 39679862 : const char *func = getFunctionId(p);
563 76516714 : size_t l = func ? strlen(func) : 0;
564 :
565 38207431 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
566 : }
567 :
568 : inline int
569 1602094 : isSubJoin(InstrPtr p)
570 : {
571 1602094 : const char *func = getFunctionId(p);
572 3082818 : size_t l = func ? strlen(func) : 0;
573 :
574 1602017 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
575 : }
576 :
577 : inline int
578 59361592 : isMultiplex(InstrPtr p)
579 : {
580 59332553 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
581 59361653 : && getFunctionId(p) == multiplexRef);
582 : }
583 :
584 : inline int
585 3534661 : isUnion(InstrPtr p)
586 : {
587 3342015 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
588 6876676 : && getFunctionId(p) == multiplexRef) ||
589 643169 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
590 : }
591 :
592 : int
593 155912 : isFragmentGroup(InstrPtr p)
594 : {
595 155912 : return (getModuleId(p) == algebraRef
596 105838 : && (getFunctionId(p) == projectRef
597 126206 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
598 205980 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
599 : }
|
