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_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 497198 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
29 : {
30 497198 : InstrPtr p;
31 497198 : int i;
32 106795241 : for (i = mb->stop; i < mb->ssize; i++) {
33 106298043 : p = getInstrPtr(mb, i);
34 106298043 : 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 499133 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
47 : {
48 499133 : int i;
49 499133 : InstrPtr q;
50 :
51 10163114 : for (i = mb->stop - 1; i > 0; i--) {
52 10163114 : q = getInstrPtr(mb, i);
53 10163114 : if (q->token == ENDsymbol)
54 : break;
55 10000470 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
56 8665313 : && 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 1497064 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
67 : {
68 1497064 : bool p_found = false;
69 :
70 24977933 : for (int i = mb->stop - 1; i > 0; i--) {
71 24978196 : InstrPtr q = getInstrPtr(mb, i);
72 :
73 24978196 : p_found |= q == p; /* the optimizer to find must come before p */
74 24978196 : if (q && q->token == ENDsymbol)
75 : return 0;
76 24878634 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
77 7044155 : && 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 1030167 : isSimpleSQL(MalBlkPtr mb)
86 : {
87 1030167 : int cnt = 0;
88 :
89 46952847 : for (int i = 0; i < mb->stop; i++) {
90 46497319 : InstrPtr p = getInstrPtr(mb, i);
91 :
92 46497319 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
93 1161480 : cnt++;
94 46497319 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
95 : return 1;
96 46496576 : if (p && getModuleId(p) == sqlcatalogRef)
97 : return 1;
98 : }
99 455528 : return cnt > 0.63 * mb->stop;
100 : }
101 :
102 : /* Only used by opt_commonTerms! */
103 : int
104 248189 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
105 : {
106 248189 : int i;
107 :
108 248189 : if (q->retc != p->retc || q->argc != p->argc)
109 : return FALSE;
110 1394590 : for (i = 0; i < p->argc; i++)
111 1146419 : 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 74993923 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
119 : {
120 74993923 : int k;
121 74993923 : int (*cmp)(const void *, const void *);
122 74993923 : VarPtr w, u;
123 :
124 74993923 : (void) mb;
125 74993923 : if (p->retc != q->retc || p->argc != q->argc)
126 : return FALSE;
127 : /* heuristic, because instructions are linked using last constant argument */
128 106904838 : for (k = p->argc - 1; k >= p->retc; k--)
129 106656649 : if (q->argv[k] != p->argv[k]) {
130 85492144 : if (isVarConstant(mb, getArg(p, k))
131 80012334 : && isVarConstant(mb, getArg(q, k))) {
132 80012100 : w = getVar(mb, getArg(p, k));
133 80012100 : u = getVar(mb, getArg(q, k));
134 80012100 : cmp = ATOMcompare(w->value.vtype);
135 80012100 : if (w->value.vtype == u->value.vtype
136 79582964 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
137 38251484 : continue;
138 : }
139 47219649 : 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 248171 : hasCommonResults(InstrPtr p, InstrPtr q)
151 : {
152 248171 : int k, l;
153 :
154 508816 : for (k = 0; k < p->retc; k++)
155 547592 : for (l = 0; l < q->retc; l++)
156 286947 : 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 227135 : isDependent(InstrPtr p, InstrPtr q)
167 : {
168 227135 : int i, j;
169 466744 : for (i = 0; i < q->retc; i++)
170 1150619 : for (j = p->retc; j < p->argc; j++)
171 911010 : 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 175555119 : isUnsafeFunction(InstrPtr q)
183 : {
184 175555119 : InstrPtr p;
185 :
186 175555119 : if (q->unsafeProp)
187 : return TRUE;
188 173602323 : 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 227135 : safetyBarrier(InstrPtr p, InstrPtr q)
237 : {
238 227135 : int i, j;
239 227135 : if (isDependent(q, p))
240 : return TRUE;
241 227135 : 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 200135855 : isUpdateInstruction(InstrPtr p)
254 : {
255 200135855 : if (getModuleId(p) == sqlRef &&
256 56879826 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
257 54034513 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
258 53950797 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
259 53950346 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
260 53861796 : || getFunctionId(p) == predicateRef))
261 : return TRUE;
262 197069472 : if (getModuleId(p) == batRef
263 11834614 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
264 9639610 : || getFunctionId(p) == deleteRef))
265 2195048 : return TRUE;
266 : return FALSE;
267 : }
268 :
269 : int
270 144218550 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
271 : {
272 144218550 : 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 141251458 : 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 134126226 : if (isUnsafeFunction(p))
288 : return TRUE;
289 :
290 : /* update instructions have side effects, they can be marked as unsafe */
291 132871472 : if (isUpdateInstruction(p))
292 : return TRUE;
293 :
294 129984955 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
295 24047510 : && (getFunctionId(p) == setAccessRef))
296 : return TRUE;
297 :
298 129984955 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
299 : return FALSE;
300 :
301 129968838 : if (getModuleId(p) == ioRef ||
302 129968838 : getModuleId(p) == streamsRef ||
303 129968838 : getModuleId(p) == bstreamRef ||
304 129968833 : getModuleId(p) == mdbRef ||
305 129968062 : getModuleId(p) == malRef ||
306 129968062 : getModuleId(p) == remapRef ||
307 82331676 : getModuleId(p) == optimizerRef ||
308 82331676 : getModuleId(p) == lockRef ||
309 82331676 : getModuleId(p) == semaRef ||
310 : getModuleId(p) == alarmRef)
311 : return TRUE;
312 :
313 82331676 : if( getModuleId(p) == pyapi3Ref ||
314 82331536 : getModuleId(p) == rapiRef ||
315 : getModuleId(p) == capiRef)
316 : return TRUE;
317 :
318 82331378 : if (getModuleId(p) == sqlcatalogRef)
319 : return TRUE;
320 82331378 : if (getModuleId(p) == sqlRef) {
321 19316718 : if (getFunctionId(p) == tidRef)
322 : return FALSE;
323 16437341 : if (getFunctionId(p) == deltaRef)
324 : return FALSE;
325 14523291 : if (getFunctionId(p) == subdeltaRef)
326 : return FALSE;
327 14181503 : if (getFunctionId(p) == projectdeltaRef)
328 : return FALSE;
329 13145709 : if (getFunctionId(p) == bindRef)
330 : return FALSE;
331 1177169 : if (getFunctionId(p) == bindidxRef)
332 : return FALSE;
333 1156103 : if (getFunctionId(p) == binddbatRef)
334 : return FALSE;
335 1156103 : if (getFunctionId(p) == columnBindRef)
336 : return FALSE;
337 1156103 : if (getFunctionId(p) == copy_fromRef)
338 : return FALSE;
339 : /* assertions are the end-point of a flow path */
340 1156103 : if (getFunctionId(p) == not_uniqueRef)
341 : return FALSE;
342 1156103 : if (getFunctionId(p) == zero_or_oneRef)
343 : return FALSE;
344 1156103 : if (getFunctionId(p) == mvcRef)
345 : return FALSE;
346 18956 : if (getFunctionId(p) == singleRef)
347 : return FALSE;
348 18956 : if (getFunctionId(p) == importColumnRef)
349 : return FALSE;
350 17876 : return TRUE;
351 : }
352 63014660 : 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 63014660 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
361 : return TRUE;
362 :
363 62688840 : if (getModuleId(p) == sqlcatalogRef)
364 : return TRUE;
365 62688840 : if (getModuleId(p) == remoteRef)
366 36999 : return TRUE;
367 : return FALSE;
368 : }
369 :
370 : /* Void returning functions always have side-effects.
371 : */
372 : int
373 29369808 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
374 : {
375 29369808 : int tpe;
376 29369808 : tpe = getVarType(mb, getArg(p, 0));
377 29369808 : if (tpe == TYPE_void)
378 : return TRUE;
379 28917884 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
380 28912211 : 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 5673 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
385 : return TRUE;
386 5673 : 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 246098 : isOrderDepenent(InstrPtr p)
432 : {
433 246098 : 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 15706574 : isMapOp(InstrPtr p)
450 : {
451 15706574 : if (isUnsafeFunction(p))
452 : return 0;
453 15555492 : return getModuleId(p)
454 15181449 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
455 1156 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
456 15180293 : || (getModuleId(p) == batcalcRef)
457 15025094 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
458 14424191 : && strncmp(getModuleId(p), "bat", 3) == 0)
459 15181449 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
460 172692 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
461 15728171 : && getModuleId(p) != batcapiRef;
462 : }
463 :
464 : inline int
465 228911 : isMap2Op(InstrPtr p)
466 : {
467 228911 : if (isUnsafeFunction(p))
468 : return 0;
469 228841 : return getModuleId(p)
470 228840 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
471 580 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
472 228260 : || (getModuleId(p) == batcalcRef)
473 160775 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
474 114070 : && strncmp(getModuleId(p), "bat", 3) == 0)
475 228840 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
476 73112 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
477 301949 : && getModuleId(p) != batcapiRef;
478 : }
479 :
480 : inline int
481 18858173 : isLikeOp(InstrPtr p)
482 : {
483 18858173 : return (getModuleId(p) == batalgebraRef
484 18858173 : && (getFunctionId(p) == likeRef
485 127 : || getFunctionId(p) == not_likeRef));
486 : }
487 :
488 : inline int
489 215260 : isTopn(InstrPtr p)
490 : {
491 73860 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
492 215260 : || isSlice(p));
493 : }
494 :
495 : inline int
496 38090170 : isSlice(InstrPtr p)
497 : {
498 38090170 : return (getModuleId(p) == algebraRef
499 38090170 : && (getFunctionId(p) == subsliceRef
500 3564901 : || getFunctionId(p) == sliceRef));
501 : }
502 :
503 : int
504 21000037 : isSample(InstrPtr p)
505 : {
506 21000037 : 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 1601179 : isMatJoinOp(InstrPtr p)
517 : {
518 1601179 : return (isSubJoin(p)
519 1601179 : || (getModuleId(p) == algebraRef
520 1014270 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
521 995921 : || getFunctionId(p) == thetajoinRef
522 995921 : || getFunctionId(p) == bandjoinRef
523 995921 : || getFunctionId(p) == rangejoinRef)
524 : ));
525 : }
526 :
527 : inline int
528 1417546 : isMatLeftJoinOp(InstrPtr p)
529 : {
530 1417546 : return (getModuleId(p) == algebraRef
531 1417546 : && (getFunctionId(p) == leftjoinRef
532 1114881 : || getFunctionId(p) == outerjoinRef
533 1114863 : || getFunctionId(p) == markjoinRef));
534 : }
535 :
536 : inline int
537 138855 : isDelta(InstrPtr p)
538 : {
539 138855 : return (getModuleId(p) == sqlRef
540 138855 : && (getFunctionId(p) == deltaRef
541 46125 : || getFunctionId(p) == projectdeltaRef
542 15600 : || getFunctionId(p) == subdeltaRef)
543 : );
544 : }
545 :
546 : int
547 35847 : isFragmentGroup2(InstrPtr p)
548 : {
549 35847 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
550 : return TRUE;
551 10 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
552 12169 : || (getModuleId(p) == batRef
553 8936 : && (getFunctionId(p) == mergecandRef
554 0 : || getFunctionId(p) == intersectcandRef
555 0 : || getFunctionId(p) == diffcandRef)
556 : );
557 : }
558 :
559 : inline int
560 37212046 : isSelect(InstrPtr p)
561 : {
562 37212046 : const char *func = getFunctionId(p);
563 71721966 : size_t l = func ? strlen(func) : 0;
564 :
565 35813273 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
566 : }
567 :
568 : inline int
569 1601165 : isSubJoin(InstrPtr p)
570 : {
571 1601165 : const char *func = getFunctionId(p);
572 3081153 : size_t l = func ? strlen(func) : 0;
573 :
574 1601081 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
575 : }
576 :
577 : inline int
578 65660735 : isMultiplex(InstrPtr p)
579 : {
580 65627823 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
581 65660796 : && getFunctionId(p) == multiplexRef);
582 : }
583 :
584 : inline int
585 3517612 : isUnion(InstrPtr p)
586 : {
587 3358753 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
588 6876365 : && getFunctionId(p) == multiplexRef) ||
589 643907 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
590 : }
591 :
592 : int
593 155654 : isFragmentGroup(InstrPtr p)
594 : {
595 155654 : return (getModuleId(p) == algebraRef
596 105722 : && (getFunctionId(p) == projectRef
597 126023 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
598 205580 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
599 : }
|
