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 538882 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
29 : {
30 538882 : InstrPtr p;
31 538882 : int i;
32 115996587 : for (i = mb->stop; i < mb->ssize; i++) {
33 115457705 : p = getInstrPtr(mb, i);
34 115457705 : 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 540822 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
47 : {
48 540822 : int i;
49 540822 : InstrPtr q;
50 :
51 10921443 : for (i = mb->stop - 1; i > 0; i--) {
52 10921443 : q = getInstrPtr(mb, i);
53 10921443 : if (q->token == ENDsymbol)
54 : break;
55 10758171 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
56 9416185 : && 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 1622050 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
67 : {
68 1622050 : bool p_found = false;
69 :
70 27181553 : for (int i = mb->stop - 1; i > 0; i--) {
71 27181814 : InstrPtr q = getInstrPtr(mb, i);
72 :
73 27181814 : p_found |= q == p; /* the optimizer to find must come before p */
74 27181814 : if (q && q->token == ENDsymbol)
75 : return 0;
76 27082290 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
77 7667773 : && 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 1113506 : isSimpleSQL(MalBlkPtr mb)
86 : {
87 1113506 : int cnt = 0;
88 :
89 49980759 : for (int i = 0; i < mb->stop; i++) {
90 49453234 : InstrPtr p = getInstrPtr(mb, i);
91 :
92 49453234 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
93 1232141 : cnt++;
94 49453234 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
95 : return 1;
96 49452481 : if (p && getModuleId(p) == sqlcatalogRef)
97 : return 1;
98 : }
99 527525 : return cnt > 0.63 * mb->stop;
100 : }
101 :
102 : /* Only used by opt_commonTerms! */
103 : int
104 316257 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
105 : {
106 316257 : int i;
107 :
108 316257 : if (q->retc != p->retc || q->argc != p->argc)
109 : return FALSE;
110 1810759 : for (i = 0; i < p->argc; i++)
111 1494510 : 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 77466451 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
119 : {
120 77466451 : int k;
121 77466451 : int (*cmp)(const void *, const void *);
122 77466451 : VarPtr w, u;
123 :
124 77466451 : (void) mb;
125 77466451 : if (p->retc != q->retc || p->argc != q->argc)
126 : return FALSE;
127 : /* heuristic, because instructions are linked using last constant argument */
128 109563463 : for (k = p->argc - 1; k >= p->retc; k--)
129 109247196 : if (q->argv[k] != p->argv[k]) {
130 87602579 : if (isVarConstant(mb, getArg(p, k))
131 82082920 : && isVarConstant(mb, getArg(q, k))) {
132 82082759 : w = getVar(mb, getArg(p, k));
133 82082759 : u = getVar(mb, getArg(q, k));
134 82082759 : cmp = ATOMcompare(w->value.vtype);
135 82082759 : if (w->value.vtype == u->value.vtype
136 81633430 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
137 39355028 : continue;
138 : }
139 48250395 : 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 316236 : hasCommonResults(InstrPtr p, InstrPtr q)
151 : {
152 316236 : int k, l;
153 :
154 644952 : for (k = 0; k < p->retc; k++)
155 683734 : for (l = 0; l < q->retc; l++)
156 355018 : 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 295021 : isDependent(InstrPtr p, InstrPtr q)
167 : {
168 295021 : int i, j;
169 602528 : for (i = 0; i < q->retc; i++)
170 1498384 : for (j = p->retc; j < p->argc; j++)
171 1190877 : 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 183497578 : isUnsafeFunction(InstrPtr q)
183 : {
184 183497578 : InstrPtr p;
185 :
186 183497578 : if (q->unsafeProp)
187 : return TRUE;
188 181451371 : 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 295043 : safetyBarrier(InstrPtr p, InstrPtr q)
237 : {
238 295043 : int i, j;
239 295043 : if (isDependent(q, p))
240 : return TRUE;
241 295043 : 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 206922239 : isUpdateInstruction(InstrPtr p)
254 : {
255 206922239 : if (getModuleId(p) == sqlRef &&
256 57326221 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
257 54308258 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
258 54223817 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
259 54223364 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
260 54134075 : || getFunctionId(p) == predicateRef))
261 : return TRUE;
262 203681365 : if (getModuleId(p) == batRef
263 12465076 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
264 10254704 : || getFunctionId(p) == deleteRef))
265 2210416 : return TRUE;
266 : return FALSE;
267 : }
268 :
269 : int
270 150938610 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
271 : {
272 150938610 : 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 147741013 : 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 140098912 : if (isUnsafeFunction(p))
288 : return TRUE;
289 :
290 : /* update instructions have side effects, they can be marked as unsafe */
291 138827893 : if (isUpdateInstruction(p))
292 : return TRUE;
293 :
294 135799246 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
295 24512839 : && (getFunctionId(p) == setAccessRef))
296 : return TRUE;
297 :
298 135799246 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
299 : return FALSE;
300 :
301 135783061 : if (getModuleId(p) == ioRef ||
302 135783061 : getModuleId(p) == streamsRef ||
303 135783061 : getModuleId(p) == bstreamRef ||
304 135783056 : getModuleId(p) == mdbRef ||
305 135782285 : getModuleId(p) == malRef ||
306 135782285 : getModuleId(p) == remapRef ||
307 83346396 : getModuleId(p) == optimizerRef ||
308 83346396 : getModuleId(p) == lockRef ||
309 83346396 : getModuleId(p) == semaRef ||
310 : getModuleId(p) == alarmRef)
311 : return TRUE;
312 :
313 83346396 : if( getModuleId(p) == pyapi3Ref ||
314 83346256 : getModuleId(p) == rapiRef ||
315 : getModuleId(p) == capiRef)
316 : return TRUE;
317 :
318 83346098 : if (getModuleId(p) == sqlcatalogRef)
319 : return TRUE;
320 83346098 : if (getModuleId(p) == sqlRef) {
321 19463181 : if (getFunctionId(p) == tidRef)
322 : return FALSE;
323 16598948 : if (getFunctionId(p) == deltaRef)
324 : return FALSE;
325 14651124 : if (getFunctionId(p) == subdeltaRef)
326 : return FALSE;
327 14284140 : if (getFunctionId(p) == projectdeltaRef)
328 : return FALSE;
329 13231278 : if (getFunctionId(p) == bindRef)
330 : return FALSE;
331 1221736 : if (getFunctionId(p) == bindidxRef)
332 : return FALSE;
333 1200685 : if (getFunctionId(p) == binddbatRef)
334 : return FALSE;
335 1200685 : if (getFunctionId(p) == columnBindRef)
336 : return FALSE;
337 1200685 : if (getFunctionId(p) == copy_fromRef)
338 : return FALSE;
339 : /* assertions are the end-point of a flow path */
340 1200685 : if (getFunctionId(p) == not_uniqueRef)
341 : return FALSE;
342 1200685 : if (getFunctionId(p) == zero_or_oneRef)
343 : return FALSE;
344 1200685 : if (getFunctionId(p) == mvcRef)
345 : return FALSE;
346 19176 : if (getFunctionId(p) == singleRef)
347 : return FALSE;
348 19176 : if (getFunctionId(p) == importColumnRef)
349 : return FALSE;
350 18096 : return TRUE;
351 : }
352 63882917 : 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 63882917 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
361 : return TRUE;
362 :
363 63560128 : if (getModuleId(p) == sqlcatalogRef)
364 : return TRUE;
365 63560128 : 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 29825818 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
374 : {
375 29825818 : int tpe;
376 29825818 : tpe = getVarType(mb, getArg(p, 0));
377 29825818 : if (tpe == TYPE_void)
378 : return TRUE;
379 29268800 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
380 29263110 : 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 5690 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
385 : return TRUE;
386 5690 : 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 265015 : isOrderDepenent(InstrPtr p)
432 : {
433 265015 : if (getModuleId(p) != batsqlRef)
434 : return 0;
435 971 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
436 863 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
437 726 : || getFunctionId(p) == dense_rankRef
438 714 : || getFunctionId(p) == percent_rankRef
439 709 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
440 697 : || getFunctionId(p) == first_valueRef
441 689 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
442 686 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
443 684 : || getFunctionId(p) == corrRef)
444 295 : return 1;
445 : return 0;
446 : }
447 :
448 : inline int
449 17258115 : isMapOp(InstrPtr p)
450 : {
451 17258115 : if (isUnsafeFunction(p))
452 : return 0;
453 17070519 : return getModuleId(p)
454 16653400 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
455 1173 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
456 16652227 : || (getModuleId(p) == batcalcRef)
457 16478386 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
458 15807051 : && strncmp(getModuleId(p), "bat", 3) == 0)
459 16653400 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
460 191423 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
461 17261929 : && getModuleId(p) != batcapiRef;
462 : }
463 :
464 : inline int
465 230941 : isMap2Op(InstrPtr p)
466 : {
467 230941 : if (isUnsafeFunction(p))
468 : return 0;
469 230871 : return getModuleId(p)
470 230870 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
471 580 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
472 230290 : || (getModuleId(p) == batcalcRef)
473 162637 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
474 115745 : && strncmp(getModuleId(p), "bat", 3) == 0)
475 230870 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
476 73297 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
477 304164 : && getModuleId(p) != batcapiRef;
478 : }
479 :
480 : inline int
481 20361035 : isLikeOp(InstrPtr p)
482 : {
483 20361035 : return (getModuleId(p) == batalgebraRef
484 20361035 : && (getFunctionId(p) == likeRef
485 132 : || getFunctionId(p) == not_likeRef));
486 : }
487 :
488 : inline int
489 217843 : isTopn(InstrPtr p)
490 : {
491 74920 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
492 217843 : || isSlice(p));
493 : }
494 :
495 : inline int
496 41090283 : isSlice(InstrPtr p)
497 : {
498 41090283 : return (getModuleId(p) == algebraRef
499 41090283 : && (getFunctionId(p) == subsliceRef
500 3608314 : || getFunctionId(p) == sliceRef));
501 : }
502 :
503 : int
504 22552701 : isSample(InstrPtr p)
505 : {
506 22552701 : 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 1614086 : isMatJoinOp(InstrPtr p)
517 : {
518 1614086 : return (isSubJoin(p)
519 1614086 : || (getModuleId(p) == algebraRef
520 1021098 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
521 1003001 : || getFunctionId(p) == thetajoinRef
522 1003001 : || getFunctionId(p) == bandjoinRef
523 1003001 : || getFunctionId(p) == rangejoinRef)
524 : ));
525 : }
526 :
527 : inline int
528 1428689 : isMatLeftJoinOp(InstrPtr p)
529 : {
530 1428689 : return (getModuleId(p) == algebraRef
531 1428689 : && (getFunctionId(p) == leftjoinRef
532 1122878 : || getFunctionId(p) == outerjoinRef
533 1122860 : || getFunctionId(p) == markjoinRef));
534 : }
535 :
536 : inline int
537 141602 : isDelta(InstrPtr p)
538 : {
539 141602 : return (getModuleId(p) == sqlRef
540 141602 : && (getFunctionId(p) == deltaRef
541 47459 : || getFunctionId(p) == projectdeltaRef
542 16434 : || getFunctionId(p) == subdeltaRef)
543 : );
544 : }
545 :
546 : int
547 35990 : isFragmentGroup2(InstrPtr p)
548 : {
549 35990 : 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 40206416 : isSelect(InstrPtr p)
561 : {
562 40206416 : const char *func = getFunctionId(p);
563 77547316 : size_t l = func ? strlen(func) : 0;
564 :
565 38727988 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
566 : }
567 :
568 : inline int
569 1614062 : isSubJoin(InstrPtr p)
570 : {
571 1614062 : const char *func = getFunctionId(p);
572 3106178 : size_t l = func ? strlen(func) : 0;
573 :
574 1613985 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
575 : }
576 :
577 : inline int
578 69037614 : isMultiplex(InstrPtr p)
579 : {
580 69004634 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
581 69037675 : && getFunctionId(p) == multiplexRef);
582 : }
583 :
584 : inline int
585 3565995 : isUnion(InstrPtr p)
586 : {
587 3373221 : return ((getModuleId(p) == malRef || getModuleId(p) == batmalRef)
588 6939216 : && getFunctionId(p) == multiplexRef) ||
589 646985 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
590 : }
591 :
592 : int
593 157499 : isFragmentGroup(InstrPtr p)
594 : {
595 157499 : return (getModuleId(p) == algebraRef
596 107370 : && (getFunctionId(p) == projectRef
597 127754 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
598 207622 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
599 : }
|
