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 496288 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
29 : {
30 496288 : InstrPtr p;
31 496288 : int i;
32 106629774 : for (i = mb->stop; i < mb->ssize; i++) {
33 106133486 : p = getInstrPtr(mb, i);
34 106133486 : 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 498188 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
47 : {
48 498188 : int i;
49 498188 : InstrPtr q;
50 :
51 10147727 : for (i = mb->stop - 1; i > 0; i--) {
52 10147727 : q = getInstrPtr(mb, i);
53 10147727 : if (q->token == ENDsymbol)
54 : break;
55 9985064 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
56 8649244 : && 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 1494324 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
67 : {
68 1494324 : bool p_found = false;
69 :
70 24930778 : for (int i = mb->stop - 1; i > 0; i--) {
71 24930944 : InstrPtr q = getInstrPtr(mb, i);
72 :
73 24930944 : p_found |= q == p; /* the optimizer to find must come before p */
74 24930944 : if (q && q->token == ENDsymbol)
75 : return 0;
76 24831358 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
77 7030563 : && 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 1028264 : isSimpleSQL(MalBlkPtr mb)
86 : {
87 1028264 : int cnt = 0;
88 :
89 46902706 : for (int i = 0; i < mb->stop; i++) {
90 46447177 : InstrPtr p = getInstrPtr(mb, i);
91 :
92 46447177 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
93 1166770 : cnt++;
94 46447177 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
95 : return 1;
96 46446430 : if (p && getModuleId(p) == sqlcatalogRef)
97 : return 1;
98 : }
99 455529 : return cnt > 0.63 * mb->stop;
100 : }
101 :
102 : /* Only used by opt_commonTerms! */
103 : int
104 248147 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
105 : {
106 248147 : int i;
107 :
108 248147 : if (q->retc != p->retc || q->argc != p->argc)
109 : return FALSE;
110 1394268 : for (i = 0; i < p->argc; i++)
111 1146139 : 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 74747301 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
119 : {
120 74747301 : int k;
121 74747301 : int (*cmp)(const void *, const void *);
122 74747301 : VarPtr w, u;
123 :
124 74747301 : (void) mb;
125 74747301 : if (p->retc != q->retc || p->argc != q->argc)
126 : return FALSE;
127 : /* heuristic, because instructions are linked using last constant argument */
128 106351862 : for (k = p->argc - 1; k >= p->retc; k--)
129 106103715 : if (q->argv[k] != p->argv[k]) {
130 85014117 : if (isVarConstant(mb, getArg(p, k))
131 79534188 : && isVarConstant(mb, getArg(q, k))) {
132 79533954 : w = getVar(mb, getArg(p, k));
133 79533954 : u = getVar(mb, getArg(q, k));
134 79533954 : cmp = ATOMcompare(w->value.vtype);
135 79533954 : if (w->value.vtype == u->value.vtype
136 79106819 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
137 38026594 : continue;
138 : }
139 46966298 : 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 248129 : hasCommonResults(InstrPtr p, InstrPtr q)
151 : {
152 248129 : int k, l;
153 :
154 508732 : for (k = 0; k < p->retc; k++)
155 547508 : for (l = 0; l < q->retc; l++)
156 286905 : 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 227093 : isDependent(InstrPtr p, InstrPtr q)
167 : {
168 227093 : int i, j;
169 466660 : for (i = 0; i < q->retc; i++)
170 1150339 : for (j = p->retc; j < p->argc; j++)
171 910772 : 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 175268957 : isUnsafeFunction(InstrPtr q)
183 : {
184 175268957 : InstrPtr p;
185 :
186 175268957 : if (q->unsafeProp)
187 : return TRUE;
188 173313362 : 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 227093 : safetyBarrier(InstrPtr p, InstrPtr q)
237 : {
238 227093 : int i, j;
239 227093 : if (isDependent(q, p))
240 : return TRUE;
241 227093 : 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 199747584 : isUpdateInstruction(InstrPtr p)
254 : {
255 199747584 : if (getModuleId(p) == sqlRef &&
256 56641520 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
257 53787479 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
258 53703426 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
259 53702975 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
260 53614088 : || getFunctionId(p) == predicateRef))
261 : return TRUE;
262 196671706 : if (getModuleId(p) == batRef
263 11810910 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
264 9615814 : || getFunctionId(p) == deleteRef))
265 2195140 : return TRUE;
266 : return FALSE;
267 : }
268 :
269 : int
270 143998531 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
271 : {
272 143998531 : 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 141036358 : 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 133917372 : if (isUnsafeFunction(p))
288 : return TRUE;
289 :
290 : /* update instructions have side effects, they can be marked as unsafe */
291 132661279 : if (isUpdateInstruction(p))
292 : return TRUE;
293 :
294 129767683 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
295 23949880 : && (getFunctionId(p) == setAccessRef))
296 : return TRUE;
297 :
298 129767683 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
299 : return FALSE;
300 :
301 129751570 : if (getModuleId(p) == ioRef ||
302 129751570 : getModuleId(p) == streamsRef ||
303 129751570 : getModuleId(p) == bstreamRef ||
304 129751565 : getModuleId(p) == mdbRef ||
305 129750795 : getModuleId(p) == malRef ||
306 129750795 : getModuleId(p) == remapRef ||
307 82201042 : getModuleId(p) == optimizerRef ||
308 82201042 : getModuleId(p) == lockRef ||
309 82201042 : getModuleId(p) == semaRef ||
310 : getModuleId(p) == alarmRef)
311 : return TRUE;
312 :
313 82201042 : if( getModuleId(p) == pyapi3Ref ||
314 82200902 : getModuleId(p) == rapiRef ||
315 : getModuleId(p) == capiRef)
316 : return TRUE;
317 :
318 82200744 : if (getModuleId(p) == sqlcatalogRef)
319 : return TRUE;
320 82200744 : if (getModuleId(p) == sqlRef) {
321 19231134 : if (getFunctionId(p) == tidRef)
322 : return FALSE;
323 16368283 : if (getFunctionId(p) == deltaRef)
324 : return FALSE;
325 14454192 : if (getFunctionId(p) == subdeltaRef)
326 : return FALSE;
327 14112516 : if (getFunctionId(p) == projectdeltaRef)
328 : return FALSE;
329 13076370 : if (getFunctionId(p) == bindRef)
330 : return FALSE;
331 1176659 : if (getFunctionId(p) == bindidxRef)
332 : return FALSE;
333 1155593 : if (getFunctionId(p) == binddbatRef)
334 : return FALSE;
335 1155593 : if (getFunctionId(p) == columnBindRef)
336 : return FALSE;
337 1155593 : if (getFunctionId(p) == copy_fromRef)
338 : return FALSE;
339 : /* assertions are the end-point of a flow path */
340 1155593 : if (getFunctionId(p) == not_uniqueRef)
341 : return FALSE;
342 1155593 : if (getFunctionId(p) == zero_or_oneRef)
343 : return FALSE;
344 1155593 : 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 62969610 : 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 62969610 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
361 : return TRUE;
362 :
363 62647923 : if (getModuleId(p) == sqlcatalogRef)
364 : return TRUE;
365 62647923 : 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 29328024 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
374 : {
375 29328024 : int tpe;
376 29328024 : tpe = getVarType(mb, getArg(p, 0));
377 29328024 : if (tpe == TYPE_void)
378 : return TRUE;
379 28875706 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
380 28870035 : 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 5671 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
385 : return TRUE;
386 5671 : 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 262 : isSideEffectFree(MalBlkPtr mb)
396 : {
397 262 : int i;
398 4228 : for (i = 1; i < mb->stop && getInstrPtr(mb, i)->token != ENDsymbol; i++) {
399 4013 : 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 246036 : isOrderDepenent(InstrPtr p)
432 : {
433 246036 : if (getModuleId(p) != batsqlRef)
434 : return 0;
435 946 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
436 838 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
437 702 : || getFunctionId(p) == dense_rankRef
438 690 : || getFunctionId(p) == percent_rankRef
439 685 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
440 673 : || getFunctionId(p) == first_valueRef
441 665 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
442 662 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
443 660 : || getFunctionId(p) == corrRef)
444 294 : return 1;
445 : return 0;
446 : }
447 :
448 : inline int
449 15668188 : isMapOp(InstrPtr p)
450 : {
451 15668188 : if (isUnsafeFunction(p))
452 : return 0;
453 15516420 : return getModuleId(p)
454 15143340 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
455 1155 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
456 15142185 : || (getModuleId(p) == batcalcRef)
457 14987060 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
458 14387917 : && strncmp(getModuleId(p), "bat", 3) == 0)
459 15143340 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
460 172612 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
461 15689019 : && getModuleId(p) != batcapiRef;
462 : }
463 :
464 : inline int
465 228969 : isMap2Op(InstrPtr p)
466 : {
467 228969 : if (isUnsafeFunction(p))
468 : return 0;
469 228899 : return getModuleId(p)
470 228898 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
471 580 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
472 228318 : || (getModuleId(p) == batcalcRef)
473 160813 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
474 114093 : && strncmp(getModuleId(p), "bat", 3) == 0)
475 228898 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
476 73130 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
477 302025 : && getModuleId(p) != batcapiRef;
478 : }
479 :
480 : inline int
481 18820574 : isLikeOp(InstrPtr p)
482 : {
483 18820574 : return (getModuleId(p) == batalgebraRef
484 18820574 : && (getFunctionId(p) == likeRef
485 127 : || getFunctionId(p) == not_likeRef));
486 : }
487 :
488 : inline int
489 215320 : isTopn(InstrPtr p)
490 : {
491 73880 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
492 215320 : || isSlice(p));
493 : }
494 :
495 : inline int
496 38011413 : isSlice(InstrPtr p)
497 : {
498 38011413 : return (getModuleId(p) == algebraRef
499 38011413 : && (getFunctionId(p) == subsliceRef
500 3557767 : || getFunctionId(p) == sliceRef));
501 : }
502 :
503 : int
504 20970558 : isSample(InstrPtr p)
505 : {
506 20970558 : 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 1601559 : isMatJoinOp(InstrPtr p)
517 : {
518 1601559 : return (isSubJoin(p)
519 1601559 : || (getModuleId(p) == algebraRef
520 1014279 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
521 995957 : || getFunctionId(p) == thetajoinRef
522 995957 : || getFunctionId(p) == bandjoinRef
523 995957 : || getFunctionId(p) == rangejoinRef)
524 : ));
525 : }
526 :
527 : inline int
528 1417663 : isMatLeftJoinOp(InstrPtr p)
529 : {
530 1417663 : return (getModuleId(p) == algebraRef
531 1417663 : && (getFunctionId(p) == leftjoinRef
532 1114925 : || getFunctionId(p) == outerjoinRef
533 1114907 : || getFunctionId(p) == markjoinRef));
534 : }
535 :
536 : inline int
537 138915 : isDelta(InstrPtr p)
538 : {
539 138915 : return (getModuleId(p) == sqlRef
540 138915 : && (getFunctionId(p) == deltaRef
541 46151 : || getFunctionId(p) == projectdeltaRef
542 15610 : || getFunctionId(p) == subdeltaRef)
543 : );
544 : }
545 :
546 : int
547 35852 : isFragmentGroup2(InstrPtr p)
548 : {
549 35852 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
550 : return TRUE;
551 10 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
552 12162 : || (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 37137391 : isSelect(InstrPtr p)
561 : {
562 37137391 : const char *func = getFunctionId(p);
563 71579856 : size_t l = func ? strlen(func) : 0;
564 :
565 35743933 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
566 : }
567 :
568 : inline int
569 1601545 : isSubJoin(InstrPtr p)
570 : {
571 1601545 : const char *func = getFunctionId(p);
572 3081910 : size_t l = func ? strlen(func) : 0;
573 :
574 1601461 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
575 : }
576 :
577 : inline int
578 65566339 : isMultiplex(InstrPtr p)
579 : {
580 65533452 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
581 65566400 : && getFunctionId(p) == multiplexRef);
582 : }
583 :
584 : inline int
585 3514320 : isUnion(InstrPtr p)
586 : {
587 3355505 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
588 6869825 : && getFunctionId(p) == multiplexRef) ||
589 643108 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
590 : }
591 :
592 : int
593 155694 : isFragmentGroup(InstrPtr p)
594 : {
595 155694 : return (getModuleId(p) == algebraRef
596 105754 : && (getFunctionId(p) == projectRef
597 126058 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
598 205628 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
599 : }
|
