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 537574 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
29 : {
30 537574 : InstrPtr p;
31 537574 : int i;
32 115674922 : for (i = mb->stop; i < mb->ssize; i++) {
33 115137348 : p = getInstrPtr(mb, i);
34 115137348 : 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 539494 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
47 : {
48 539494 : int i;
49 539494 : InstrPtr q;
50 :
51 10895954 : for (i = mb->stop - 1; i > 0; i--) {
52 10895954 : q = getInstrPtr(mb, i);
53 10895954 : if (q->token == ENDsymbol)
54 : break;
55 10732728 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
56 9391363 : && 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 1618133 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
67 : {
68 1618133 : bool p_found = false;
69 :
70 27110463 : for (int i = mb->stop - 1; i > 0; i--) {
71 27110696 : InstrPtr q = getInstrPtr(mb, i);
72 :
73 27110696 : p_found |= q == p; /* the optimizer to find must come before p */
74 27110696 : if (q && q->token == ENDsymbol)
75 : return 0;
76 27011160 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
77 7647748 : && 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 1110914 : isSimpleSQL(MalBlkPtr mb)
86 : {
87 1110914 : int cnt = 0;
88 :
89 50021608 : for (int i = 0; i < mb->stop; i++) {
90 49494211 : InstrPtr p = getInstrPtr(mb, i);
91 :
92 49494211 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
93 1226261 : cnt++;
94 49494211 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
95 : return 1;
96 49493458 : if (p && getModuleId(p) == sqlcatalogRef)
97 : return 1;
98 : }
99 527397 : return cnt > 0.63 * mb->stop;
100 : }
101 :
102 : /* Only used by opt_commonTerms! */
103 : int
104 316609 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
105 : {
106 316609 : int i;
107 :
108 316609 : if (q->retc != p->retc || q->argc != p->argc)
109 : return FALSE;
110 1813511 : for (i = 0; i < p->argc; i++)
111 1496913 : 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 77782285 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
119 : {
120 77782285 : int k;
121 77782285 : int (*cmp)(const void *, const void *);
122 77782285 : VarPtr w, u;
123 :
124 77782285 : (void) mb;
125 77782285 : if (p->retc != q->retc || p->argc != q->argc)
126 : return FALSE;
127 : /* heuristic, because instructions are linked using last constant argument */
128 110272400 : for (k = p->argc - 1; k >= p->retc; k--)
129 109955781 : if (q->argv[k] != p->argv[k]) {
130 88206296 : if (isVarConstant(mb, getArg(p, k))
131 82685813 : && isVarConstant(mb, getArg(q, k))) {
132 82685652 : w = getVar(mb, getArg(p, k));
133 82685652 : u = getVar(mb, getArg(q, k));
134 82685652 : cmp = ATOMcompare(w->value.vtype);
135 82685652 : if (w->value.vtype == u->value.vtype
136 82234311 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
137 39633390 : continue;
138 : }
139 48573917 : 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 316592 : hasCommonResults(InstrPtr p, InstrPtr q)
151 : {
152 316592 : int k, l;
153 :
154 645683 : for (k = 0; k < p->retc; k++)
155 684522 : for (l = 0; l < q->retc; l++)
156 355431 : 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 295384 : isDependent(InstrPtr p, InstrPtr q)
167 : {
168 295384 : int i, j;
169 603269 : for (i = 0; i < q->retc; i++)
170 1500910 : for (j = p->retc; j < p->argc; j++)
171 1193025 : 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 183510312 : isUnsafeFunction(InstrPtr q)
183 : {
184 183510312 : InstrPtr p;
185 :
186 183510312 : if (q->unsafeProp)
187 : return TRUE;
188 181467944 : 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 295399 : safetyBarrier(InstrPtr p, InstrPtr q)
237 : {
238 295399 : int i, j;
239 295399 : if (isDependent(q, p))
240 : return TRUE;
241 295399 : 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 207130721 : isUpdateInstruction(InstrPtr p)
254 : {
255 207130721 : if (getModuleId(p) == sqlRef &&
256 57583582 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
257 54575675 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
258 54491664 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
259 54491213 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
260 54402348 : || getFunctionId(p) == predicateRef))
261 : return TRUE;
262 203900843 : if (getModuleId(p) == batRef
263 12488160 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
264 10279835 : || getFunctionId(p) == deleteRef))
265 2208369 : return TRUE;
266 : return FALSE;
267 : }
268 :
269 : int
270 150928921 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
271 : {
272 150928921 : 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 147732442 : 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 140100716 : if (isUnsafeFunction(p))
288 : return TRUE;
289 :
290 : /* update instructions have side effects, they can be marked as unsafe */
291 138831609 : if (isUpdateInstruction(p))
292 : return TRUE;
293 :
294 135811520 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
295 24614886 : && (getFunctionId(p) == setAccessRef))
296 : return TRUE;
297 :
298 135811520 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
299 : return FALSE;
300 :
301 135795339 : if (getModuleId(p) == ioRef ||
302 135795339 : getModuleId(p) == streamsRef ||
303 135795339 : getModuleId(p) == bstreamRef ||
304 135795334 : getModuleId(p) == mdbRef ||
305 135794563 : getModuleId(p) == malRef ||
306 135794563 : getModuleId(p) == remapRef ||
307 83479731 : getModuleId(p) == optimizerRef ||
308 83479731 : getModuleId(p) == lockRef ||
309 83479731 : getModuleId(p) == semaRef ||
310 : getModuleId(p) == alarmRef)
311 : return TRUE;
312 :
313 83479731 : if( getModuleId(p) == pyapi3Ref ||
314 83479591 : getModuleId(p) == rapiRef ||
315 : getModuleId(p) == capiRef)
316 : return TRUE;
317 :
318 83479433 : if (getModuleId(p) == sqlcatalogRef)
319 : return TRUE;
320 83479433 : if (getModuleId(p) == sqlRef) {
321 19553594 : if (getFunctionId(p) == tidRef)
322 : return FALSE;
323 16671617 : if (getFunctionId(p) == deltaRef)
324 : return FALSE;
325 14724983 : if (getFunctionId(p) == subdeltaRef)
326 : return FALSE;
327 14358067 : if (getFunctionId(p) == projectdeltaRef)
328 : return FALSE;
329 13306169 : if (getFunctionId(p) == bindRef)
330 : return FALSE;
331 1220077 : if (getFunctionId(p) == bindidxRef)
332 : return FALSE;
333 1199026 : if (getFunctionId(p) == binddbatRef)
334 : return FALSE;
335 1199026 : if (getFunctionId(p) == columnBindRef)
336 : return FALSE;
337 1199026 : if (getFunctionId(p) == copy_fromRef)
338 : return FALSE;
339 : /* assertions are the end-point of a flow path */
340 1199026 : if (getFunctionId(p) == not_uniqueRef)
341 : return FALSE;
342 1199026 : if (getFunctionId(p) == zero_or_oneRef)
343 : return FALSE;
344 1199026 : if (getFunctionId(p) == mvcRef)
345 : return FALSE;
346 19072 : if (getFunctionId(p) == singleRef)
347 : return FALSE;
348 19072 : if (getFunctionId(p) == importColumnRef)
349 : return FALSE;
350 17992 : return TRUE;
351 : }
352 63925839 : 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 63925839 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
361 : return TRUE;
362 :
363 63598711 : if (getModuleId(p) == sqlcatalogRef)
364 : return TRUE;
365 63598711 : 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 29870588 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
374 : {
375 29870588 : int tpe;
376 29870588 : tpe = getVarType(mb, getArg(p, 0));
377 29870588 : if (tpe == TYPE_void)
378 : return TRUE;
379 29314150 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
380 29308461 : 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 5689 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
385 : return TRUE;
386 5689 : 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 264991 : isOrderDepenent(InstrPtr p)
432 : {
433 264991 : if (getModuleId(p) != batsqlRef)
434 : return 0;
435 954 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
436 846 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
437 710 : || getFunctionId(p) == dense_rankRef
438 698 : || getFunctionId(p) == percent_rankRef
439 693 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
440 681 : || getFunctionId(p) == first_valueRef
441 673 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
442 670 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
443 668 : || getFunctionId(p) == corrRef)
444 294 : return 1;
445 : return 0;
446 : }
447 :
448 : inline int
449 17218830 : isMapOp(InstrPtr p)
450 : {
451 17218830 : if (isUnsafeFunction(p))
452 : return 0;
453 17032102 : return getModuleId(p)
454 16616294 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
455 1172 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
456 16615122 : || (getModuleId(p) == batcalcRef)
457 16441297 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
458 15768188 : && strncmp(getModuleId(p), "bat", 3) == 0)
459 16616294 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
460 191400 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
461 17223489 : && getModuleId(p) != batcapiRef;
462 : }
463 :
464 : inline int
465 230845 : isMap2Op(InstrPtr p)
466 : {
467 230845 : if (isUnsafeFunction(p))
468 : return 0;
469 230775 : return getModuleId(p)
470 230774 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
471 580 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
472 230194 : || (getModuleId(p) == batcalcRef)
473 162548 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
474 115690 : && strncmp(getModuleId(p), "bat", 3) == 0)
475 230774 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
476 73297 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
477 304068 : && getModuleId(p) != batcapiRef;
478 : }
479 :
480 : inline int
481 20326389 : isLikeOp(InstrPtr p)
482 : {
483 20326389 : return (getModuleId(p) == batalgebraRef
484 20326389 : && (getFunctionId(p) == likeRef
485 132 : || getFunctionId(p) == not_likeRef));
486 : }
487 :
488 : inline int
489 217713 : isTopn(InstrPtr p)
490 : {
491 74876 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
492 217713 : || isSlice(p));
493 : }
494 :
495 : inline int
496 41024698 : isSlice(InstrPtr p)
497 : {
498 41024698 : return (getModuleId(p) == algebraRef
499 41024698 : && (getFunctionId(p) == subsliceRef
500 3615170 : || getFunctionId(p) == sliceRef));
501 : }
502 :
503 : int
504 22507342 : isSample(InstrPtr p)
505 : {
506 22507342 : 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 1613262 : isMatJoinOp(InstrPtr p)
517 : {
518 1613262 : return (isSubJoin(p)
519 1613262 : || (getModuleId(p) == algebraRef
520 1020974 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
521 1002874 : || getFunctionId(p) == thetajoinRef
522 1002874 : || getFunctionId(p) == bandjoinRef
523 1002874 : || getFunctionId(p) == rangejoinRef)
524 : ));
525 : }
526 :
527 : inline int
528 1428372 : isMatLeftJoinOp(InstrPtr p)
529 : {
530 1428372 : return (getModuleId(p) == algebraRef
531 1428372 : && (getFunctionId(p) == leftjoinRef
532 1122727 : || getFunctionId(p) == outerjoinRef
533 1122709 : || getFunctionId(p) == markjoinRef));
534 : }
535 :
536 : inline int
537 141473 : isDelta(InstrPtr p)
538 : {
539 141473 : return (getModuleId(p) == sqlRef
540 141473 : && (getFunctionId(p) == deltaRef
541 47405 : || getFunctionId(p) == projectdeltaRef
542 16418 : || getFunctionId(p) == subdeltaRef)
543 : );
544 : }
545 :
546 : int
547 35966 : isFragmentGroup2(InstrPtr p)
548 : {
549 35966 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
550 : return TRUE;
551 10 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
552 12149 : || (getModuleId(p) == batRef
553 8906 : && (getFunctionId(p) == mergecandRef
554 0 : || getFunctionId(p) == intersectcandRef
555 0 : || getFunctionId(p) == diffcandRef)
556 : );
557 : }
558 :
559 : inline int
560 40137381 : isSelect(InstrPtr p)
561 : {
562 40137381 : const char *func = getFunctionId(p);
563 77410817 : size_t l = func ? strlen(func) : 0;
564 :
565 38657912 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
566 : }
567 :
568 : inline int
569 1613251 : isSubJoin(InstrPtr p)
570 : {
571 1613251 : const char *func = getFunctionId(p);
572 3104594 : size_t l = func ? strlen(func) : 0;
573 :
574 1613174 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
575 : }
576 :
577 : inline int
578 68965640 : isMultiplex(InstrPtr p)
579 : {
580 68932668 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
581 68965701 : && getFunctionId(p) == multiplexRef);
582 : }
583 :
584 : inline int
585 3565065 : isUnion(InstrPtr p)
586 : {
587 3372304 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
588 6937369 : && getFunctionId(p) == multiplexRef) ||
589 646797 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
590 : }
591 :
592 : int
593 157403 : isFragmentGroup(InstrPtr p)
594 : {
595 157403 : return (getModuleId(p) == algebraRef
596 107308 : && (getFunctionId(p) == projectRef
597 127679 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
598 207492 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
599 : }
|
