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_prelude.h"
17 : #include "opt_support.h"
18 : #include "mal_interpreter.h"
19 : #include "mal_listing.h"
20 : #include "opt_multiplex.h"
21 : #include "optimizer_private.h"
22 : #include "manifold.h"
23 :
24 : /* Some optimizers can/need only be applied once.
25 : * The optimizer trace at the end of the MAL block
26 : * can be used to check for this.
27 : */
28 : int
29 491563 : optimizerIsApplied(MalBlkPtr mb, const char *opt)
30 : {
31 491563 : InstrPtr p;
32 491563 : int i;
33 105641151 : for (i = mb->stop; i < mb->ssize; i++) {
34 105149588 : p = getInstrPtr(mb, i);
35 105149588 : if (p && getModuleId(p) == optimizerRef && p->token == REMsymbol
36 0 : && getFunctionId(p) == opt)
37 : return 1;
38 : }
39 : return 0;
40 : }
41 :
42 : /*
43 : * Some optimizers are interdependent (e.g. mitosis ), which
44 : * requires inspection of the pipeline attached to a MAL block.
45 : */
46 : int
47 493416 : isOptimizerEnabled(MalBlkPtr mb, const char *opt)
48 : {
49 493416 : int i;
50 493416 : InstrPtr q;
51 :
52 10052826 : for (i = mb->stop - 1; i > 0; i--) {
53 10052826 : q = getInstrPtr(mb, i);
54 10052826 : if (q->token == ENDsymbol)
55 : break;
56 9890872 : if (q->token != REMsymbol && getModuleId(q) == optimizerRef
57 8562034 : && getFunctionId(q) == opt)
58 : return 1;
59 : }
60 : return 0;
61 : }
62 :
63 : /*
64 : * Find if an optimizer 'opt' has run before the instruction 'p'.
65 : */
66 : int
67 1480030 : isOptimizerUsed(MalBlkPtr mb, InstrPtr p, const char *opt)
68 : {
69 1480030 : bool p_found = false;
70 :
71 24676956 : for (int i = mb->stop - 1; i > 0; i--) {
72 24677142 : InstrPtr q = getInstrPtr(mb, i);
73 :
74 24677142 : p_found |= q == p; /* the optimizer to find must come before p */
75 24677142 : if (q && q->token == ENDsymbol)
76 : return 0;
77 24577661 : if (p_found && q && q != p && getModuleId(q) == optimizerRef
78 6958865 : && getFunctionId(q) == opt)
79 : return 1;
80 : }
81 : return 0;
82 : }
83 :
84 : /* Simple insertion statements do not require complex optimizer steps */
85 : int
86 1018810 : isSimpleSQL(MalBlkPtr mb)
87 : {
88 1018810 : int cnt = 0;
89 :
90 44121695 : for (int i = 0; i < mb->stop; i++) {
91 43670449 : InstrPtr p = getInstrPtr(mb, i);
92 :
93 43670449 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == appendRef)
94 1142575 : cnt++;
95 43670449 : if (p && getModuleId(p) == sqlRef && getFunctionId(p) == setVariableRef)
96 : return 1;
97 43669702 : if (p && getModuleId(p) == sqlcatalogRef)
98 : return 1;
99 : }
100 451246 : return cnt > 0.63 * mb->stop;
101 : }
102 :
103 : /* Only used by opt_commonTerms! */
104 : int
105 236645 : hasSameSignature(MalBlkPtr mb, InstrPtr p, InstrPtr q)
106 : {
107 236645 : int i;
108 :
109 236645 : if (q->retc != p->retc || q->argc != p->argc)
110 : return FALSE;
111 1335516 : for (i = 0; i < p->argc; i++)
112 1098885 : if (getArgType(mb, p, i) != getArgType(mb, q, i))
113 : return FALSE;
114 : return TRUE;
115 : }
116 :
117 : /* Only used by opt_commonTerms! */
118 : int
119 72029202 : hasSameArguments(MalBlkPtr mb, InstrPtr p, InstrPtr q)
120 : {
121 72029202 : int k;
122 72029202 : int (*cmp)(const void *, const void *);
123 72029202 : VarPtr w, u;
124 :
125 72029202 : (void) mb;
126 72029202 : if (p->retc != q->retc || p->argc != q->argc)
127 : return FALSE;
128 : /* heuristic, because instructions are linked using last constant argument */
129 101189900 : for (k = p->argc - 1; k >= p->retc; k--)
130 100953255 : if (q->argv[k] != p->argv[k]) {
131 81932482 : if (isVarConstant(mb, getArg(p, k))
132 77026653 : && isVarConstant(mb, getArg(q, k))) {
133 77026478 : w = getVar(mb, getArg(p, k));
134 77026478 : u = getVar(mb, getArg(q, k));
135 77026478 : cmp = ATOMcompare(w->value.vtype);
136 77026478 : if (w->value.vtype == u->value.vtype
137 76615064 : && (*cmp) (VALptr(&w->value), VALptr(&u->value)) == 0)
138 36954710 : continue;
139 : }
140 44982128 : return FALSE;
141 : }
142 : return TRUE;
143 : }
144 :
145 : /*
146 : * If two instructions have elements in common in their target list,
147 : * it means a variable is re-initialized and should not be considered
148 : * an alias.
149 : */
150 : int
151 236631 : hasCommonResults(InstrPtr p, InstrPtr q)
152 : {
153 236631 : int k, l;
154 :
155 485019 : for (k = 0; k < p->retc; k++)
156 521582 : for (l = 0; l < q->retc; l++)
157 273194 : if (p->argv[k] == q->argv[l])
158 : return TRUE;
159 : return FALSE;
160 : }
161 :
162 : /*
163 : * Dependency between target variables and arguments can be
164 : * checked with isDependent().
165 : */
166 : static int
167 216733 : isDependent(InstrPtr p, InstrPtr q)
168 : {
169 216733 : int i, j;
170 445223 : for (i = 0; i < q->retc; i++)
171 1102191 : for (j = p->retc; j < p->argc; j++)
172 873701 : if (getArg(q, i) == getArg(p, j))
173 : return TRUE;
174 : return FALSE;
175 : }
176 :
177 : /*
178 : * The safety property should be relatively easy to determine for
179 : * each MAL function. This calls for accessing the function MAL block
180 : * and to inspect the arguments of the signature.
181 : */
182 : inline int
183 165609993 : isUnsafeFunction(InstrPtr q)
184 : {
185 165609993 : InstrPtr p;
186 :
187 165609993 : if (q->unsafeProp)
188 : return TRUE;
189 163669432 : if (q->fcn == 0 || getFunctionId(q) == 0 || q->blk == NULL)
190 : return FALSE;
191 0 : p = getInstrPtr(q->blk, 0);
192 0 : if (p->retc == 0)
193 0 : return TRUE;
194 : return FALSE;
195 : }
196 :
197 : /*
198 : * Instructions are unsafe if one of the arguments is also mentioned
199 : * in the result list. Alternatively, the 'unsafe' property is set
200 : * for the function call itself.
201 : */
202 : int
203 0 : isUnsafeInstruction(InstrPtr q)
204 : {
205 0 : int j, k;
206 :
207 0 : for (j = 0; j < q->retc; j++)
208 0 : for (k = q->retc; k < q->argc; k++)
209 0 : if (q->argv[k] == q->argv[j])
210 : return TRUE;
211 : return FALSE;
212 : }
213 :
214 : /*
215 : * Any instruction may block identification of a common
216 : * subexpression. It suffices to stumble upon an unsafe function
217 : * whose parameter lists has a non-empty intersection with the
218 : * targeted instruction.
219 : * To illustrate, consider the sequence
220 : * @example
221 : * L1 := f(A,B,C);
222 : * ...
223 : * G1 := g(D,E,F);
224 : * ...
225 : * l2:= f(A,B,C);
226 : * ...
227 : * L2:= h()
228 : * @end example
229 : *
230 : * The instruction G1:=g(D,E,F) is blocking if G1 is an alias
231 : * for @verb{ { }A,B,C@verb{ } }.
232 : * Alternatively, function g() may be unsafe and @verb{ { }D,E,F@verb{ } }
233 : * has a non-empty intersection with @verb{ { }A,B,C@verb{ } }.
234 : * An alias can only be used later on for readonly (and not be used for a function with side effects).
235 : */
236 : int
237 216733 : safetyBarrier(InstrPtr p, InstrPtr q)
238 : {
239 216733 : int i, j;
240 216733 : if (isDependent(q, p))
241 : return TRUE;
242 216733 : if (isUnsafeFunction(q)) {
243 0 : for (i = p->retc; i < p->argc; i++)
244 0 : for (j = q->retc; j < q->argc; j++)
245 0 : if (p->argv[i] == q->argv[j]) {
246 : /* TODO check safety property of the argument */
247 : return TRUE;
248 : }
249 : }
250 : return FALSE;
251 : }
252 :
253 : inline int
254 181870764 : isUpdateInstruction(InstrPtr p)
255 : {
256 181870764 : if (getModuleId(p) == sqlRef &&
257 47565858 : (getFunctionId(p) == appendRef || getFunctionId(p) == updateRef
258 44772576 : || getFunctionId(p) == deleteRef || getFunctionId(p) == claimRef
259 44688704 : || getFunctionId(p) == growRef || getFunctionId(p) == clear_tableRef
260 44688251 : || getFunctionId(p) == setVariableRef || getFunctionId(p) == dependRef
261 44599736 : || getFunctionId(p) == predicateRef))
262 : return TRUE;
263 178856315 : if (getModuleId(p) == batRef
264 10331506 : && (getFunctionId(p) == appendRef || getFunctionId(p) == replaceRef
265 8723099 : || getFunctionId(p) == deleteRef))
266 1608451 : return TRUE;
267 : return FALSE;
268 : }
269 :
270 : int
271 136285669 : hasSideEffects(MalBlkPtr mb, InstrPtr p, int strict)
272 : {
273 136285669 : if (getFunctionId(p) == NULL)
274 : return FALSE;
275 :
276 : /*
277 : * Void-returning operations have side-effects and
278 : * should be considered as such
279 : */
280 133356273 : if (p->retc == 0 || (p->retc == 1 && getArgType(mb, p, 0) == TYPE_void))
281 : return TRUE;
282 :
283 : /*
284 : * Any function marked as unsafe can not be moved around without
285 : * affecting its behavior on the program. For example, because they
286 : * check for volatile resource levels.
287 : */
288 126684851 : if (isUnsafeFunction(p))
289 : return TRUE;
290 :
291 : /* update instructions have side effects, they can be marked as unsafe */
292 125436677 : if (isUpdateInstruction(p))
293 : return TRUE;
294 :
295 122784869 : if ((getModuleId(p) == batRef || getModuleId(p) == sqlRef)
296 22098005 : && (getFunctionId(p) == setAccessRef))
297 : return TRUE;
298 :
299 122784869 : if (getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
300 : return FALSE;
301 :
302 122769525 : if (getModuleId(p) == ioRef ||
303 122769525 : getModuleId(p) == streamsRef ||
304 122769525 : getModuleId(p) == bstreamRef ||
305 122769525 : getModuleId(p) == mdbRef ||
306 122768754 : getModuleId(p) == malRef ||
307 122768754 : getModuleId(p) == remapRef ||
308 122768754 : getModuleId(p) == optimizerRef ||
309 75712696 : getModuleId(p) == lockRef ||
310 75712696 : getModuleId(p) == semaRef ||
311 75712696 : getModuleId(p) == alarmRef)
312 : return TRUE;
313 :
314 75712696 : if( getModuleId(p) == pyapi3Ref ||
315 75712696 : getModuleId(p) == rapiRef ||
316 75712556 : getModuleId(p) == capiRef)
317 : return TRUE;
318 :
319 75712398 : if (getModuleId(p) == sqlcatalogRef)
320 : return TRUE;
321 75712398 : if (getModuleId(p) == sqlRef) {
322 17757067 : if (getFunctionId(p) == tidRef)
323 : return FALSE;
324 15762985 : if (getFunctionId(p) == deltaRef)
325 : return FALSE;
326 13896911 : if (getFunctionId(p) == subdeltaRef)
327 : return FALSE;
328 13631245 : if (getFunctionId(p) == projectdeltaRef)
329 : return FALSE;
330 12830569 : if (getFunctionId(p) == bindRef)
331 : return FALSE;
332 1164348 : if (getFunctionId(p) == bindidxRef)
333 : return FALSE;
334 1143026 : if (getFunctionId(p) == binddbatRef)
335 : return FALSE;
336 1143026 : if (getFunctionId(p) == columnBindRef)
337 : return FALSE;
338 1143026 : if (getFunctionId(p) == copy_fromRef)
339 : return FALSE;
340 : /* assertions are the end-point of a flow path */
341 1143026 : if (getFunctionId(p) == not_uniqueRef)
342 : return FALSE;
343 1143026 : if (getFunctionId(p) == zero_or_oneRef)
344 : return FALSE;
345 1143026 : if (getFunctionId(p) == mvcRef)
346 : return FALSE;
347 18323 : if (getFunctionId(p) == singleRef)
348 : return FALSE;
349 18323 : if (getFunctionId(p) == importColumnRef)
350 : return FALSE;
351 17243 : return TRUE;
352 : }
353 57955331 : if (getModuleId(p) == mapiRef) {
354 0 : if (getFunctionId(p) == rpcRef)
355 : return TRUE;
356 0 : if (getFunctionId(p) == reconnectRef)
357 : return TRUE;
358 0 : if (getFunctionId(p) == disconnectRef)
359 : return TRUE;
360 : }
361 57955331 : if (strict && getFunctionId(p) == newRef && getModuleId(p) != groupRef)
362 : return TRUE;
363 :
364 57668542 : if (getModuleId(p) == sqlcatalogRef)
365 : return TRUE;
366 57668542 : if (getModuleId(p) == remoteRef)
367 36999 : return TRUE;
368 : return FALSE;
369 : }
370 :
371 : /* Void returning functions always have side-effects.
372 : */
373 : int
374 26918735 : mayhaveSideEffects(Client cntxt, MalBlkPtr mb, InstrPtr p, int strict)
375 : {
376 26918735 : int tpe;
377 26918735 : tpe = getVarType(mb, getArg(p, 0));
378 26918735 : if (tpe == TYPE_void)
379 : return TRUE;
380 26470440 : if (getModuleId(p) != malRef || getFunctionId(p) != multiplexRef)
381 26465008 : return hasSideEffects(mb, p, strict);
382 : // a manifold instruction can also have side effects.
383 : // for this to check we need the function signature, not its function address.
384 : // The easy way out now is to consider all manifold instructions as potentially having side effects.
385 5432 : if (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
386 : return TRUE;
387 5432 : if (MANIFOLDtypecheck(cntxt, mb, p, 1) == NULL)
388 : return TRUE;
389 : return FALSE;
390 : }
391 :
392 : /*
393 : * Side-effect free functions are crucial for several operators.
394 : */
395 : int
396 262 : isSideEffectFree(MalBlkPtr mb)
397 : {
398 262 : int i;
399 4228 : for (i = 1; i < mb->stop && getInstrPtr(mb, i)->token != ENDsymbol; i++) {
400 4013 : if (hasSideEffects(mb, getInstrPtr(mb, i), TRUE))
401 : return FALSE;
402 : }
403 : return TRUE;
404 : }
405 :
406 : /*
407 : * Breaking up a MAL program into pieces for distributed processing requires
408 : * identification of (partial) blocking instructions. A conservative
409 : * definition can be used.
410 : */
411 : inline int
412 0 : isBlocking(InstrPtr p)
413 : {
414 0 : if (blockStart(p) || blockExit(p) || blockCntrl(p))
415 : return TRUE;
416 :
417 0 : if (getFunctionId(p) == sortRef)
418 : return TRUE;
419 :
420 0 : if (getModuleId(p) == aggrRef || getModuleId(p) == groupRef
421 0 : || getModuleId(p) == sqlcatalogRef)
422 0 : return TRUE;
423 : return FALSE;
424 : }
425 :
426 : /*
427 : * Used in the merge table optimizer. It is built incrementally
428 : * and should be conservative.
429 : */
430 :
431 : static int
432 232989 : isOrderDepenent(InstrPtr p)
433 : {
434 232989 : if (getModuleId(p) != batsqlRef)
435 : return 0;
436 794 : if (getFunctionId(p) == differenceRef || getFunctionId(p) == window_boundRef
437 710 : || getFunctionId(p) == row_numberRef || getFunctionId(p) == rankRef
438 575 : || getFunctionId(p) == dense_rankRef
439 568 : || getFunctionId(p) == percent_rankRef
440 563 : || getFunctionId(p) == cume_distRef || getFunctionId(p) == ntileRef
441 557 : || getFunctionId(p) == first_valueRef
442 549 : || getFunctionId(p) == last_valueRef || getFunctionId(p) == nth_valueRef
443 546 : || getFunctionId(p) == lagRef || getFunctionId(p) == leadRef
444 544 : || getFunctionId(p) == corrRef)
445 258 : return 1;
446 : return 0;
447 : }
448 :
449 : inline int
450 15422186 : isMapOp(InstrPtr p)
451 : {
452 15422186 : if (isUnsafeFunction(p))
453 : return 0;
454 15272380 : return getModuleId(p)
455 14903398 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
456 1058 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
457 14902340 : || (getModuleId(p) == batcalcRef)
458 14749441 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
459 14181725 : && strncmp(getModuleId(p), "bat", 3) == 0)
460 14903398 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
461 169701 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
462 15442068 : && getModuleId(p) != batcapiRef;
463 : }
464 :
465 : inline int
466 169147 : isMap2Op(InstrPtr p)
467 : {
468 169147 : if (isUnsafeFunction(p))
469 : return 0;
470 169077 : return getModuleId(p)
471 169076 : && ((getModuleId(p) == malRef && getFunctionId(p) == multiplexRef)
472 548 : || (getModuleId(p) == malRef && getFunctionId(p) == manifoldRef)
473 168528 : || (getModuleId(p) == batcalcRef)
474 110149 : || (getModuleId(p) != batcalcRef && getModuleId(p) != batRef
475 84193 : && strncmp(getModuleId(p), "bat", 3) == 0)
476 169076 : || (getModuleId(p) == batmkeyRef)) && !isOrderDepenent(p)
477 63030 : && getModuleId(p) != batrapiRef && getModuleId(p) != batpyapi3Ref
478 232103 : && getModuleId(p) != batcapiRef;
479 : }
480 :
481 : inline int
482 18609297 : isLikeOp(InstrPtr p)
483 : {
484 18609297 : return (getModuleId(p) == batalgebraRef
485 18609297 : && (getFunctionId(p) == likeRef
486 127 : || getFunctionId(p) == not_likeRef));
487 : }
488 :
489 : inline int
490 169383 : isTopn(InstrPtr p)
491 : {
492 52999 : return ((getModuleId(p) == algebraRef && getFunctionId(p) == firstnRef)
493 222259 : || isSlice(p));
494 : }
495 :
496 : inline int
497 37555089 : isSlice(InstrPtr p)
498 : {
499 37555089 : return (getModuleId(p) == algebraRef
500 37555089 : && (getFunctionId(p) == subsliceRef
501 3496396 : || getFunctionId(p) == sliceRef));
502 : }
503 :
504 : int
505 20639627 : isSample(InstrPtr p)
506 : {
507 20639627 : return (getModuleId(p) == sampleRef && getFunctionId(p) == subuniformRef);
508 : }
509 :
510 : inline int
511 0 : isOrderby(InstrPtr p)
512 : {
513 0 : return getModuleId(p) == algebraRef && getFunctionId(p) == sortRef;
514 : }
515 :
516 : inline int
517 1459493 : isMatJoinOp(InstrPtr p)
518 : {
519 1459493 : return (isSubJoin(p)
520 1459493 : || (getModuleId(p) == algebraRef
521 930141 : && (getFunctionId(p) == crossRef || getFunctionId(p) == joinRef
522 912924 : || getFunctionId(p) == thetajoinRef
523 912924 : || getFunctionId(p) == bandjoinRef
524 912924 : || getFunctionId(p) == rangejoinRef)
525 : ));
526 : }
527 :
528 : inline int
529 1271365 : isMatLeftJoinOp(InstrPtr p)
530 : {
531 1271365 : return (getModuleId(p) == algebraRef
532 1271365 : && (getFunctionId(p) == leftjoinRef
533 1012280 : || getFunctionId(p) == outerjoinRef
534 1012274 : || getFunctionId(p) == markjoinRef));
535 : }
536 :
537 : inline int
538 110012 : isDelta(InstrPtr p)
539 : {
540 110012 : return (getModuleId(p) == sqlRef
541 110012 : && (getFunctionId(p) == deltaRef
542 32434 : || getFunctionId(p) == projectdeltaRef
543 11440 : || getFunctionId(p) == subdeltaRef)
544 : );
545 : }
546 :
547 : int
548 21427 : isFragmentGroup2(InstrPtr p)
549 : {
550 21427 : if (getModuleId(p) == batRef && getFunctionId(p) == replaceRef)
551 : return TRUE;
552 10 : return (getModuleId(p) == algebraRef && (getFunctionId(p) == projectionRef))
553 11199 : || (getModuleId(p) == batRef
554 8733 : && (getFunctionId(p) == mergecandRef
555 0 : || getFunctionId(p) == intersectcandRef
556 0 : || getFunctionId(p) == diffcandRef)
557 : );
558 : }
559 :
560 : inline int
561 36657849 : isSelect(InstrPtr p)
562 : {
563 36657849 : const char *func = getFunctionId(p);
564 70665931 : size_t l = func ? strlen(func) : 0;
565 :
566 35273805 : return (l >= 6 && strcmp(func + l - 6, "select") == 0);
567 : }
568 :
569 : inline int
570 1459483 : isSubJoin(InstrPtr p)
571 : {
572 1459483 : const char *func = getFunctionId(p);
573 2807287 : size_t l = func ? strlen(func) : 0;
574 :
575 1459399 : return (l >= 4 && strcmp(func + l - 4, "join") == 0);
576 : }
577 :
578 : inline int
579 62798953 : isMultiplex(InstrPtr p)
580 : {
581 62798953 : return (malRef && (getModuleId(p) == malRef || getModuleId(p) == batmalRef)
582 62830573 : && getFunctionId(p) == multiplexRef);
583 : }
584 :
585 : inline int
586 3431742 : isUnion(InstrPtr p)
587 : {
588 3431742 : return (malRef && (getModuleId(p) == malRef || getModuleId(p) == batmalRef)
589 3587571 : && getFunctionId(p) == multiplexRef) ||
590 3275913 : (getModuleId(p) == sqlRef && getFunctionId(p) == unionfuncRef);
591 : }
592 :
593 : int
594 105972 : isFragmentGroup(InstrPtr p)
595 : {
596 105972 : return (getModuleId(p) == algebraRef
597 77560 : && (getFunctionId(p) == projectRef
598 88711 : || getFunctionId(p) == selectNotNilRef)) || isSelect(p)
599 134382 : || (getModuleId(p) == batRef && (getFunctionId(p) == mirrorRef));
600 : }
|
