基于Memo-based(日志)的查询执行

现代以代价为基础的查询优化器使用备忘录结构为一个有效的查询运行计划组织搜索空间。例如，考虑一个oid连接路径‘A.B.C.D’.我们可以在这条路径任何点启动计算。它的备忘录结构可以用一个（大）MAL程序来表示。备忘录的水平用choice运算封装。第二个参数指示哪些指令去被考虑代价计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

...
scheduler.choice("getVolume");
T1:= algebra.join(A,B);
T2:= algebra.join(B,C);
T3:= algebra.join(C,D);
scheduler.choice("getVolume",T1,T2,T3);
T4:= algebra.join(T1,C);
T5:= algebra.join(A,T2);
T6:= algebra.join(T2,D);
T7:= algebra.join(B,T3);
T8:= algebra.join(C,D);
scheduler.choice("getVolume",T4,T5,T6,T7,T8);
T9:= algebra.join(T4,D);
T10:= algebra.join(T5,D);
T11:= algebra.join(A,T6);
T12:= algebra.join(A,T7);
T13:= algebra.join(T1,T8);
scheduler.choice("getVolume",T9,T10,T11,T12,T13);
answer:= scheduler.pick(T9, T10, T11, T12, T13);

scheduler.choice()操作为每个目标变量调用内置的getVolume且期待一个整数值代价。在这个事例里它返回总共参数使用的字节数。具有最低代价的目标变量被选择运行和剩余的变量被变成临时NOOP操作（你可能想重用备忘录）。它们会被解析器遗漏，同时在接下的调用中被调度器忽略。它减少了替换当我们在计划中处理时。一个内置朴素的代价函数会被使用。使用者可以提供一个私有的代价函数被定义为目标和a :lng结果带有多态参数的模式。它的实现可以使用完全的上下文信息去做决定。如，它可以跟踪在接下的语句中对目标变量的潜在使用去决定总代价当这一步被考虑到最后的结果。

在达到下个选择点前，一个完整计划很可能包含其他表达式去准备或使用目标变量。choice运算的任务是避免不必要的操作。MAL块应该被调用者私有拥有，这样确保了scheduler.isolation()。模式的细化也组成部分计划代价分析。然后你不再需要包含一个固定的代价函数。

1
2
3
4
5
6
7
8
9
10

Acost:= aggr.count(A);
Bcost:= aggr.count(B);
Ccost:= aggr.count(C);
T1cost:= Acost+Bcost;
T2cost:= Bcost+Ccost;
T3cost:= Ccost+Dcost;
scheduler.choice(T1cost,T1, T2cost,T2, T3cost,T3);
T1:= algebra.join(A,B);
T2:= algebra.join(B,C);
T3:= algebra.join(C,D);
MonetDB中RunChoice的实现代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

/*THe choice operator first searches the next one to identify
  the fragment to be optimized and to gain access to the variables
  without the need to declare them upfront.*/
str  RUNchoice(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
  int target;
  lng cost, mincost;
  int i, j, pc;
  char *nme;
  InstrPtr q;

  pc = getPC(mb, p);
  for (i = pc + 1; i < mb->stop; i++) {
      q = getInstrPtr(mb, i);
      if (getModuleId(p) == getModuleId(q) &&
          getFunctionId(p) == getFunctionId(q)) {
          p = q;
          break;
      }
  }
  if (i == mb->stop)
      return MAL_SUCCEED;
  target = getArg(p, 2);
  if (getArgType(mb, p, 1) == TYPE_int && p->argc >= 3 && (p->argc - 1) % 2 == 0) {
      /* choice pairs */
      mincost = *(int *) getArgReference(stk, p, 1);
      for (i = 3; i < p->argc; i += 2) {
          cost = *(int *) getArgReference(stk, p, i);
          if (cost < mincost && !isVarDisabled(mb, getArg(p, i + 1))) {
              mincost = cost;
              target = getArg(p, i + 1);
          }
      }
  } else if (getArgType(mb, p, 1) == TYPE_str) {
      nme = *(str *) getArgReference(stk, p, 1);
      /* should be generalized to allow an arbitrary user defined function */
      if (strcmp(nme, "getVolume") != 0)
          throw(MAL, "scheduler.choice", ILLEGAL_ARGUMENT "Illegal cost function");

      mincost = -1;
      for (j = 2; j < p->argc; j++) {
          if (!isVarDisabled(mb, getArg(p, j)))
              for (i = pc + 1; i < mb->stop; i++) {
                  InstrPtr q = getInstrPtr(mb, i);
                  if (p->token >= 0 && getArg(q, 0) == getArg(p, j)) {
                      cost = getVolume(stk, q, 1);
                      if (cost > 0 && (cost < mincost || mincost == -1)) {
                          mincost = cost;
                          target = getArg(p, j);
                      }
                      break;
                  }
              }

      }
  }
#ifdef DEBUG_RUN_MEMORUN
  mnstr_printf(cntxt->fdout, "#function target %s cost %d\n", getVarName(mb, target), mincost);
#else
  (void) cntxt;
#endif
  /* remove non-qualifying variables */
  for (i = 2; i < p->argc; i += 2)
      if (getArg(p, i) != target) {
          setVarDisabled(mb, getArg(p, i - 1));
          setVarDisabled(mb, getArg(p, i));
      }

  propagateNonTarget(mb, pc + 1);
#ifdef DEBUG_RUN_MEMORUN
  mnstr_printf(cntxt->fdout, "#cost choice selected %s %d\n",
          getVarName(mb, target), mincost);
  printFunction(cntxt->fdout, mb, 1);
#endif
  return MAL_SUCCEED;
}

1.合并表优化：

一个合并相关表（MAT）描述符定义了一个可兼容BAT的有序的类型集合，它的并代表一个单一（虚）BAT。MAL可能代表一个分区的BAT（看BPM），也可以是一个在一个程序块中临时BATs的任意集合。MAL的定义存在于一个单代码块的范围。MAT优化简单地扩展计划去基于指令的基础上处理它的模块。只有当遇上一个blocking操作时，相关的BAT才会被实例化。当没有被实例化，MAL对象不能作为参数传入到任何函数。简单地说，因为MAL不被类型系统所知道和没有底层的操作意识到它的存在。

在MAL优化器的第一种方法中，我们假设在MAT序列中第一个BAT被使用累加器。进一步，没有语义知识被使用去减少可能无用的连接。然而，我们限制对一个简单参数的扩展。这在后阶段被改变当一个以代价为基础的计算被用于区分不同的。为了说明，考虑：

1
2
3
4
5
6
7
8
9
10
11
12
13

m0:= bat.new(:oid,:int);
m1:= bat.new(:oid,:int);
m2:= bat.new(:oid,:int);
b := mat.new(m0,m1,m2);
s := algebra.select(b,1,3);
i := aggr.count(s);
io.print(s);
io.print(i);
c0 := bat.new(:int,:int);
c1 := bat.new(:int,:int);
c := mat.new(c0,c1);
j := algebra.join(b,c);
io.print(j);

选择和聚集操作可以使用MAT简单地重写：

1
2
3
4
5
6
7
8
9
10
11
12

_33 := algebra.select(m0,1,3);
_34 := algebra.select(m1,1,3);
_35 := algebra.select(m2,1,3);
s := mat.new(_33,_34,_35);
i := 0:int;
_36 := aggr.count(_33);
i := calc.+(i,_36);
_37 := aggr.count(_34);
i := calc.+(i,_37);
_38 := aggr.count(_35);
i := calc.+(i,_38);
io.print(i);

print操作还没有MAT语义。它需要一个在调用时不会产生头的函数。然而，在输出前，我们可以打包元素：

1
2

s := mat.pack(_33,_34,_35);
io.print(s);

对于连接，在不知道人和关于组件属性的情况下，我们必须生成所有可能的组合。当前的启发是限制扩展一个简单的参数。这导致：

1
2
3
4

b := mat.pack(m0,m1,m2);
_39 := algebra.join(b,c0);
_40 := algebra.join(b,c1);
j := mat.new(_39,_40);

这模式的不足是在MAL语句中隐藏爆炸。优化器的挑战从对MAT元素的属性的监测中找出最小的。如，在处理前，它可能尝试去部分地打包元素。这是一个运行调度的决定。相反的，在更复杂的程序分析中毕竟系统可以使用MAT迭代器去避免打包.

1
2
3
4
5
6
7
8
9

ji:= bat.new(:oid,:int);
barrier b:= mat.newIterator(m0,m1,m2);
barrier c:= mat.newIterator(c0,c1);
ji := algebra.join(b,c);
bat.insert(j,ji);
redo c:= mat.newIterator(c0,c1);
redo b:= mat.newIterator(m0,m1,m2);
exit c;
exit b;
MonetDB合并表优化实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472

int  OPTmergetableImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
  InstrPtr *old=0, q;
  mat_t *mat;
  int oldtop, fm, i, k, m, mtop=0, slimit;
  int size, match, actions=0, error=0;

  (void) cntxt;
  /* the number of MATs is limited to the variable stack*/
  mat = (mat_t*) GDKzalloc(mb->vtop * sizeof(mat_t));
  if ( mat == NULL)
      return 0;

  old = mb->stmt;
  oldtop= mb->stop;
  slimit = mb->ssize;
  size = (mb->stop * 1.2 < mb->ssize)? mb->ssize:(int)(mb->stop * 1.2);
  mb->stmt = (InstrPtr *) GDKzalloc(size * sizeof(InstrPtr));
  if ( mb->stmt == NULL){
      mb->stmt = old;
      return 0;
  }
  mb->ssize = size;
  mb->stop = 0;

  for( i=0; i<oldtop; i++){
      int n = -1, o = -1;

      p = old[i];
      if (getModuleId(p) == matRef &&
         (getFunctionId(p) == newRef || getFunctionId(p) == packRef)){
          mtop = mat_add(mat, mtop, p, NULL, mat_none, 1);
          continue;
      }

      if (getModuleId(p) == batcalcRef &&
         (getFunctionId(p) == mark_grpRef ||
         getFunctionId(p) == dense_rank_grpRef)) {
          /* Mergetable cannot handle 
            order related batcalc operations */
          error++;
          goto fail;
      }
      /*
      * @-
      * If the instruction does not contain MAT references it can simply be added.
      * Otherwise we have to decide on either packing them or replacement.
      */
      if ((match = MATcount(p, mat, mtop)) == 0) {
          if (p->argc >= 2) {
              if (getFunctionId(p) == markHRef||
                  getFunctionId(p) == markTRef) {
                  propagateMarkProp(mb, p, getArg(p,1), 0, oid_nil);
              } else if (getFunctionId(p) == leftjoinRef||
                     getFunctionId(p) == joinRef||
                         getFunctionId(p) == kunionRef) {
                  propagateBinProp(mb, p, getArg(p,1), getArg(p,2));
              } else {
                  propagateProp(mb, p, getArg(p,1));
              }
          }
          pushInstruction(mb, copyInstruction(p));
          continue;
      }
      /*
      * @-
      * Here we handle horizontal aligned mats. This information is passed using
      * the properties hlb <= x < hub.
      * So if this is available, we can simplify
      * batcalc operations and for fetch joins we can use this information to do
      * per part joins only.
      *
      * Also we should translate the mirror().join() (a groupby attribute) into
      * UNION(mirror().join()).
      */

      /* only handle simple joins, ie not range/band joins */
      /* For range/band joins (argc == 4), the propagation of oids
        is different, ie result-head equals head-1st arg,    
                 result-tail equals head-2nd/3rd arg */
      
      /* TODO:
        If a value join with mats on both sides fails (ie unknown
        how to handle) we should bail out, ie stop any further
        processing of any mats. This is needed because the needed 
        mas-crossproduct handling of projections fails. 
                 */
      if (match > 0 && match <= 2 && isMatJoinOp(p) &&
         (p->argc == 3 || (p->argc == 4 && getFunctionId(p) == thetajoinRef))) {
          int om, tpe = mat_none;
      
          om = m = isMATalias(getArg(p,1), mat, mtop);
          if (om < 0) { /* range join with parts on the right */
              error++;
              goto fail;
          }

          n = isMATalias(getArg(p,2), mat, mtop);
          if (isProjection(p) && m >= 0 && mat_is_topn(mat[m].type))
              tpe = mat_tpn;
          if (isProjection(p) && m >= 0 && mat_is_orderby(mat[m].type))
              tpe = mat_rdr;

          if ((m = mat_join(mb, p, mat, mtop, m, n)) < 0) {
              error++;
              goto fail;
          } else
              mtop = m;
          /* after topn projection we should merge */
          /* slice marks the end of a sequence of topn's */
          if (tpe == mat_tpn && (getFunctionId(old[i+1]) == sliceRef || mat[om].type == mat_slc))
              mtop = mat_pack_topn(mb, p, mat, mtop, om);
          else if (tpe == mat_tpn && mat[om].mm)
              mtop = mat_pack_topn_project(mb, p, mat, mtop, om);

          /* after sort projection we should mat.merge */
          if (tpe == mat_rdr && !mat[om].mm)
              mtop = mat_pack_sort(mb, p, mat, mtop, om, 1);
          else if (tpe == mat_rdr && mat[om].mm)
              mtop = mat_pack_sort_project(mb, p, mat, mtop, om);
          actions++;
          continue;
      }
      /* all map operations assume aligned bats */
      if (match >= 1 && all_mats_and_aligned(mb, p, mat, mtop) &&
         isMapOp(p)) {
          mtop = mat_map(mb, p, mat, mtop);
          actions++;
          continue;
      }
      if (match >= 1 &&
          getModuleId(p) == algebraRef &&
          getFunctionId(p)== kunionRef) {
          m = isMATalias(getArg(p,1), mat, mtop);
          n = isMATalias(getArg(p,2), mat, mtop);
          mtop = mat_union(mb, p, mat, mtop, m, n);
          actions++;
          continue;
      }
      if (match >= 1 &&
          (getModuleId(p) == algebraRef &&
           ((getFunctionId(p) == semijoinRef && match == 2) ||
            (getFunctionId(p) == kdifferenceRef)))) {
          i += mat_setop(mb, p, mat, &mtop);
          actions++;
          continue;
      }
      /*
      * @-
      * Now we handle group, derive and aggregation statements.
      */
      if (match == 1 && p->argc == 3 && getModuleId(p) == groupRef &&
         (getFunctionId(p) == newRef || getFunctionId(p) == doneRef) &&
         ((m=isMATalias(getArg(p,2), mat, mtop)) >= 0)) {
          if (mat[m].mi1 || mat[m].mm) {
              /* group on finished group is fine */
              if (mat[m].mm) {
                  pushInstruction(mb, copyInstruction(p));
                  actions++;
                  continue;
              }
              /* two phase group.new on group result */
              error++;
              goto fail;
          }
          mtop = mat_group_new(mb, p, mat, mtop, m);
          actions++;
          continue;
      }
      if (match == 3 && p->argc == 5 && getModuleId(p) == groupRef &&
          (getFunctionId(p) == deriveRef || getFunctionId(p) == doneRef )
&&
         ((m=isMATalias(getArg(p,2), mat, mtop)) >= 0) &&
         ((n=isMATalias(getArg(p,3), mat, mtop)) >= 0) &&
         ((o=isMATalias(getArg(p,4), mat, mtop)) >= 0)) {
      
          /* Found a derive after an aggr statement (distinct). */
          if (mat[m].mm) {
              error++;
              goto fail;
          }

          mtop = mat_group_derive(mb, p, mat, mtop, m, n, o);
          actions++;
          continue;
      }
      if (match == 3 && getModuleId(p) == aggrRef && p->argc == 4 &&
         (getFunctionId(p) == countRef ||
          getFunctionId(p) == count_no_nilRef ||
          getFunctionId(p) == minRef ||
          getFunctionId(p) == maxRef ||
          getFunctionId(p) == sumRef ||
          getFunctionId(p) == prodRef) &&
         ((m=isMATalias(getArg(p,1), mat, mtop)) >= 0) &&
         ((n=isMATalias(getArg(p,2), mat, mtop)) >= 0) &&
         ((o=isMATalias(getArg(p,3), mat, mtop)) >= 0)) {
          if (!mat_group_aggr(mb, p, mat, m, n, o)){
              error++;
              goto fail;
          }
          actions++;
          continue;
      }
      /* median */
      if (match == 3 && getModuleId(p) == aggrRef && p->argc == 4) {
          error++;
          goto fail;
      }
      /*
      * @-
      * Aggregate handling is a prime target for optimization.
      * The simple cases are dealt with first.
      * Handle the rewrite v:=aggr.count(b) and sum()
      * And the min/max is as easy
      */
      if (match == 1 && p->argc == 2 &&
         ((getModuleId(p)==aggrRef &&
          (getFunctionId(p)== countRef ||
           getFunctionId(p)== count_no_nilRef ||
           getFunctionId(p)== minRef ||
           getFunctionId(p)== maxRef ||
           getFunctionId(p)== sumRef ||
               getFunctionId(p) == prodRef)) ||
          (getModuleId(p) == algebraRef &&
           getFunctionId(p) == tuniqueRef)) &&
          (m=isMATalias(getArg(p,1), mat, mtop)) >= 0) {
          mat_aggr(mb, p, mat, m);
          actions++;
          continue;
      }
      if (match == 1 && p->argc == 3 && isTopn(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >= 0 &&
         mat[m].type == mat_none) {
          mtop = mat_topn(mb, p, mat, mtop, m);
          actions++;
          continue;
      }
      if (match == 1 && p->argc == 4 && isSlice(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >= 0 &&
         mat[m].type == mat_none) {
          mtop = mat_topn(mb, p, mat, mtop, m);
          actions++;
          continue;
      }
      if (match == 2 && p->argc == 4 && isTopn(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >= 0 &&
         (n=isMATalias(getArg(p,2), mat, mtop)) >= 0 &&
          mat_is_topn(mat[n].type) &&
          mat_is_topn(mat[m].type) && !mat[m].mm) {
          mtop = mat_topn2(mb, p, mat, mtop, m, n);
          actions++;
          continue;
      }
      if (match == 1 && p->argc == 2 && isOrderby(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >=0 &&
         mat[m].type == mat_none) {
          mtop = mat_sort(mb, p, mat, mtop, m);
          actions++;
          continue;
      }
      /* TODO: grp before sorting, isn't handled */
      if (match == 1 && p->argc == 2 && isOrderby(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >=0 &&
         mat[m].type == mat_grp) {
          assert(mat[m].mm); /* should be packed */
          error++;
          goto fail;
      }
      if (match == 2 && p->argc == 3 && isOrderby(p) &&
         (m=isMATalias(getArg(p,1), mat, mtop)) >= 0 &&
         (n=isMATalias(getArg(p,2), mat, mtop)) >= 0 &&
          /*mat_is_orderby(mat[n].type) &&*/
          mat_is_orderby(mat[m].type) && !mat[m].mm) {
          mtop = mat_sort2(mb, p, mat, mtop, m, n);
          actions++;
          continue;
      }
      if (match == 1 && p->argc == 4 && getModuleId(p) == sqlRef &&
          getFunctionId(p) == resultSetRef &&
         (m=isMATalias(getArg(p,3), mat, mtop)) >= 0 &&
          mat_is_orderby(mat[m].type) && !mat[m].mm) {
          mtop = mat_pack_sort(mb, p, mat, mtop, m, 0);
          actions++;
          continue;
      }
      /*
      * @-
      * The slice operation can also be piggy backed onto the mat.pack using it
      * as a property of the MAT. Pushing it through
      * would be feasible as well, provided the start of the slice is a constant 0.
      */
      if (match > 0 && getModuleId(p) == algebraRef &&
              getFunctionId(p) == sliceRef &&
              (m = isMATalias(getArg(p, 1), mat, mtop)) >= 0)
      {
          assert(0);
          /* inject new mat.pack() operation */
          q = MATpackAll(mb, NULL, mat, m, &mtop);
          /* rename mat.pack() to mat.slice() */
          setFunctionId(q, sliceRef);
          /* insert bounds from algebra.slice() into mat.slice() */
          /* (setArgument() seems to shift the remaining arguments,
          *  i.e., insert a new argument, not overwrite an existing one) */
          q = setArgument(mb, q, 1, getArg(p, 2));
          q = setArgument(mb, q, 2, getArg(p, 3));
          /* reuse result variable of algebra.slice() for mat.slice() */
          /* (we do not explicitly keep, and thus drop, the original algebra.slice()) */
          getArg(q, 0) = getArg(p, 0);

          actions++;
          continue;
      }
      /*
      * @-
      * The mark operators are a special case of apply on parts as we need to
      * correct the mark base oid's
      */
      if (match == 1 &&
          getModuleId(p) == algebraRef &&
          (getFunctionId(p) == markTRef ||
           getFunctionId(p) == markHRef)) {
          InstrPtr mark;

          m = isMATalias(getArg(p,1), mat, mtop);
          mark = mat_mark(mb, p, mat, m);
          mtop = mat_add(mat, mtop, mark, NULL, useMatType(mat, m), 0);
          actions++;
          continue;
      }
      /*
      * @-
      * Pack MAT arguments, except one, to limit plan explosion.
      * The preferred partitioned one is the first argment as it
      * often reflects a base table.
      * Look at the depth of the MAT definition to limit the explosion.
      */
      for( fm= p->argc-1; fm>p->retc ; fm--)
          if ((m=isMATalias(getArg(p,fm), mat, mtop)) >= 0)
              break;
      /*
      * @-
      * Not all instructions can be replaced by the sequence. We have to
      * group them and check for them individually.
      */
      if (match == 1 && isDiffOp(p) && fm == 1 &&
         (m=isMATalias(getArg(p,fm), mat, mtop)) >= 0){
          InstrPtr r;

          if ((r = mat_apply1(mb, p, mat, m, fm, 0)) != NULL)
              mtop = mat_add(mat, mtop, r, NULL, mat_none, 0);
          actions++;
          continue;
      }
      if (match == 1 &&
         isUpdateInstruction(p) && getModuleId(p) == sqlRef &&
         (m=isMATalias(getArg(p,fm), mat, mtop)) >= 0) {
          mat_update(mb, p, mat, m, fm);
          actions++;
          continue;
      }
      if (match == 1 &&
         isFragmentGroup(p) &&
         (m=isMATalias(getArg(p,fm), mat, mtop)) >= 0){
          int pack_mirror = 0;
          InstrPtr r;

          OPTDEBUGmergetable mnstr_printf(GDKout, "# %s.%s\n", getModuleId(p), getFunctionId(p));

          if (getFunctionId(p) == mirrorRef &&
                  mat[m].type == mat_grp/* && mat[m].mm */) {
              assert(mat[m].mm != NULL);
              pack_mirror = 1;
          }

          if (group_broken(p, mat[m].type, pack_mirror)) {
              error++;
              goto fail;
          }

          if ((r = mat_apply1(mb, p, mat, m, fm, 0)) != NULL)
              mtop = mat_add(mat, mtop, r, NULL, useMatType(mat, m), 0);

          /* packed group should include the mirror statement */
          if (pack_mirror) {
              if (mat[m].mv1 == p->argv[1])  {
                  assert(0);
                  mat[mtop-1].type = mat_grp;
              } else
                  mat[mtop-1].type = mat_ext;
              mat_pack_group(mb, mat, m, mtop-1);
          }
          actions++;
          continue;
      }
      /*
      * @-
      * All other instructions should be checked for remaining MAT dependencies.
      * It requires MAT materialization.
      */
      OPTDEBUGmergetable mnstr_printf(GDKout, "# %s.%s %d\n", getModuleId(p), getFunctionId(p), match);


      for (k = p->retc; k<p->argc; k++) {
          if((m=isMATalias(getArg(p,k), mat, mtop)) >= 0){
              if (MATpackAll2(mb, NULL, mat, m, &mtop) < 0){
                  error++;
                  goto fail;
              }
              actions++;
          }
      }
      pushInstruction(mb, copyInstruction(p));
      if (p->argc >= 2)
          propagateProp(mb, p, getArg(p,1));
  }
  /*
  * @-
  * As a final optimization, we could remove the mal.new definitions,
  * because they are not needed for the execution.
  * For the time being, they are no-ops.
  */
  (void) stk;
  chkTypes(cntxt->fdout, cntxt->nspace,mb, TRUE);

  OPTDEBUGmergetable {
      mnstr_printf(GDKout,"#Result of multi table optimizer\n");
      (void) optimizerCheck(cntxt,mb,"merge test",1,0,0);
      printFunction(GDKout, mb, 0, LIST_MAL_ALL);
  }

  if ( mb->errors == 0) {
      for(i=0; i<slimit; i++)
          if (old[i])
              freeInstruction(old[i]);
      GDKfree(old);
  }

fail:
  if( error || mb->errors){
      actions= 0;
      OPTDEBUGmergetable
          mnstr_printf(GDKout, "## %s.%s\n", getModuleId(p), getFunctionId(p));

      for(i=0; i<mb->stop; i++)
          if (mb->stmt[i])
              freeInstruction(mb->stmt[i]);
      GDKfree(mb->stmt);
      mb->stmt = old;
      mb->ssize = slimit;
      mb->stop = oldtop;
      for(i=0; i<mb->stop; i++) {
          InstrPtr p = mb->stmt[i];
          if (p && getModuleId(p) == matRef && getFunctionId(p) == newRef){
              /* simply drop this function, for the base binding is available */
              p->token = NOOPsymbol;
          }
      }
      OPTDEBUGmergetable mnstr_printf(GDKout,"Result of multi table optimizer FAILED\n");
  }
  DEBUGoptimizers
      mnstr_printf(cntxt->fdout,"#opt_mergetable: %d merge actions\n",actions);
  for (i =0; i<mtop; i++) {
      if (mat[i].pushed == 1)
          continue;
      if (mat[i].mi && mat[i].mi->token != NOOPsymbol)
          freeInstruction(mat[i].mi);
      if (mat[i].mi1 && mat[i].mi1->token != NOOPsymbol)
          freeInstruction(mat[i].mi1);
  }
  GDKfree(mat);
  return actions;
}

2.多道编译优化：

MonetDB 操作多道概念是中轴的简单运用任何标量的函数的元素在一个容器里。任何操作CMD和它的多道转变【CMD】一起出现。给出CMD(T1，..,Tn)的标记：TR，它可以被使用同时【CMD】(bat[:any 1,:T1],…,bat[any 1,Tn]) :bat[any 1,Tr]。多道的语义在所有Bat值参数执行定位连接和对匹配的元组的每个组合执行CMD。所有的结果被收集在一个结果的BAT。所有但除一个参数外可能会被一个标量值替换。对多道操作通用的解决方案是把它们翻译成MAL循环。一个片段关于其行为：

1
2
3
4

b:= bat.new(:int,:int);
bat.insert(b,1,1);
c:bat[:int,:int]:= mal.multiplex("calc.+",b,1);
optimizer.multiplex();

当前的实现需要目标类型要被清晰地被提到。由优化器产生的结果：

1
2
3
4
5
6
7
8
9

b := bat.new(:int,:int);
bat.insert(b,1,1);
_8 := bat.new(:int,:int);
barrier (_11,_12,_13):= bat.newIterator(b);
_15 := calc.+(_13,1);
bat.insert(_8,_12,_15);
redo (_11,_12,_13):= bat.hasMoreElements(b);
exit (_11,_12,_13);
c := _8;
MonetDB多道优化的代码实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

int OPTmultiplexImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
  InstrPtr *old, p;
  int i, limit, slimit, actions= 0;
  str msg= MAL_SUCCEED;

  (void) stk;
  (void) pci;

  old = mb->stmt;
  limit = mb->stop;
  slimit = mb->ssize;
  if ( newMalBlkStmt(mb, mb->ssize) < 0 )
      return 0;

  for (i = 0; i < limit; i++) {
      p = old[i];
      if (msg == MAL_SUCCEED &&
                    getModuleId(p) == malRef &&
          getFunctionId(p) == multiplexRef) {
          msg = OPTexpandMultiplex(cntxt, mb, stk, p);
          if( msg== MAL_SUCCEED){
              freeInstruction(p);
              old[i]=0;
          } else {
              pushInstruction(mb, p);
          }
          actions++;
      } else if( old[i])
          pushInstruction(mb, p);
  }
  for(;i<slimit; i++)
      if( old[i])
          freeInstruction(old[i]);
  GDKfree(old);
  DEBUGoptimizers {
      mnstr_printf(cntxt->fdout,"#opt_multiplex: %d expansions\n", actions);
      mnstr_printf(cntxt->fdout,"#mal program: %d MAL instr %d vars (" SZFMT " K)\n",mb->stop,mb->vtop,
      ((sizeof( MalBlkRecord) +mb->ssize * sizeof(InstrRecord)+ mb->vtop* sizeof(VarRecord) + mb->vsize*sizeof(VarPtr)+1023)/1024));
  }
  if (mb->errors){
      /* rollback */
  }
  return mb->errors? 0: actions;
}

3.BAT分区优化

在老的PC地址空间受限和分布的存储的需要使BATs理想地被看重作为更小的BATs的并集，在给定有限的内存中处理。带有支持性的bat分区库bmp的PARTITION()优化器用可适配的数据库分段算法解决这问题。它被递增地设计带有一个中心是支持SQL front-end。特别是，被考虑的操作被限制为MAL的子集。一个在这集合外面的操作的出现终止优化器的活动。OPTIMIZER.PARTITIONS()操作寻找SQL列BAT的绑定和为了使用分区版本而准备代码。

我们使用两种是吸纳。第一种尝试寻找线性依赖数据的片段和在其构造一个迭代器。这种方法有些棘手，因为你必须对特殊的情况进行关照。特别是，在顺序构建操作的语义造成一些问题。navie（）方法简单地看自个儿的操作和用迭代器围绕它们。一个别名的表被保留用来重用和探测已经分区的操作符。不足之处一个分区的BAT潜伏要读几次【这取决于变量可计算的重使用】和中间的读写。实验应该指明一个优化的一个。

4.窥孔优化

递归下降查询器很容易对产生更好的代码错失机会，因为有限的上下文被保留或向前看可用。窥孔优化器在这样递归的模式下建立和对优化器的‘错误’补救。窥孔模式的集合随着时间增长和front-end详细的变化应该可以预见。SQL frontend 严重依赖于一个中轴的生成oid序列的表。不幸的是，这是不能被看见和模式’$i := calc.oid(0@0); $j:= algebra.markT($k,$i);经常发生。这可以被’$j:= algebra.markT($k)’替换。另一个产生2-way指令序列例子是’$j:= algebra.markT($k); $l:= bat.reverse($j);’,这都可以用’$l:= algebra.markH($k);’替换。

reverse-reverse 操作也落入这个目录。相反的pairs 可能起因于front-end编译器的处理模式或者其它优化器步骤的副影响。这样的相反对应该越快去除越好，这样可以减小找到另外优化机会的复杂度。因所有的情况下我们应该保证被丢掉的中间结果不会被用于其他用途。

1
2
3
4
5
6
7
8

r:bat[:int,:int]:= bat.new(:int,:int);
o:= calc.oid(0@0);
z:= algebra.markT(r,o);
rr:= bat.reverse(z);
s := bat.reverse(r);
t := bat.reverse(s);
io.print(t);
optimizer.peephole();

这被窥孔优化器转化为：

1
2
3

r:bat[:int,:int] := bat.new(:int,:int);
rr := algebra.markH(r);
io.print(r);

5.查询执行计划

一个普遍使用的数据结构去表示和操作一个查询是树(或图）。它的节点表示操作符和叶子表示操作数。这样的视图随手拈来当你要重组整块代码或者去建立一个从底到上建立优化计划，如使用备忘录结构。MAL优化器工具箱提供函数用树（图）结构覆盖任何的MAL块和线性化回MAL块。线性化顺序被一个递归调用的从支撑点遍历树的决定。为了说明，考虑下列代码块：

1
2
3
4
5
6
7
8
9
10
11
12

//T1:= bat.new(:int,:int);
//T2:= bat.new(:int,:int);
//T3:= bat.new(:int,:int);
//T4:= bat.new(:int,:int);
a:= algebra.select(T1,1,3);
b:= algebra.select(T2,1,3);
c:= algebra.select(T3,0,5);
d:= algebra.select(T4,0,5);
e:= algebra.join(a,c);
f:= algebra.join(b,d);
h:= algebra.join(e,f);
optimizer.dumpQEP();

这产生一个目的查询计划的结构

1
2
3
4
5
6
7
8
9
10
11

h := algebra.join(e,f);
  e := algebra.join(a,c);
      a := algebra.select(T1,1,3);
          T1 := bat.new(:int,:int);
  c := algebra.select(T3,0,5);
      T3 := bat.new(:int,:int);
  f := algebra.join(b,d);
      b := algebra.select(T2,1,3);
          T2 := bat.new(:int,:int);
      d := algebra.select(T4,0,5);
          T4 := bat.new(:int,:int);

任何有效的MAL任务都可以被基于流依赖的树或图结构的视图覆盖，但不是所有的MAL程序都可以从一棵简单的树继承。如，上面的程序块片段被解释为线性的序列不能被表示除非执行指令自身成为操作符节点。然而，因为我们没有增加或者改变根源的MAL程序，qep.progagate任务产生原有的先行次序有优先级的程序。如果，然而，我们进入树的新的指令，它们会被放置到邻近的其它树的节点。对块的流控制给予特殊的关照，因为产生一个查询计划块不是很容易就能环绕。

MonetDB dumpQEP的实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/* The core of the work is focused on building the tree using a flow analysis. 
 * Building the tree means that we should not allow the same variable can not be used twice.*/
#define LEAFNODE 2
#define TOPNODE 3
static QEP
QEPbuilt(MalBlkPtr mb){
  QEP qroot= NULL, q= NULL, *vq;
  InstrPtr p;
  int i, j, k, *status;

  vq= (QEP*) GDKmalloc( mb->vtop * sizeof(QEP));
  if (vq == NULL)
      return NULL;
  status= (int*) GDKmalloc( mb->vtop * sizeof(int));
  if (status == NULL){
      GDKfree(vq);
      return NULL;
  }
  for(i=0; i<mb->vtop; i++) {
      status[i]= 0;
      vq[i] = 0;
  }

  for(i=1; i< mb->stop-1; i++){
      p= getInstrPtr(mb,i);
      q= QEPnewNode(mb,p);
      for( k=p->retc; k<p->argc; k++)
      if( ! isVarConstant(mb, getArg(p,k)) ){
          status[getArg(p,k)]= LEAFNODE;
          if( vq[getArg(p,k)] )
              QEPappend(q, vq[getArg(p,k)]);
      }
      for( k=0; k<p->retc; k++){
          if(   vq[getArg(p,k)] == 0)
              vq[getArg(p,k)] = q;
          status[getArg(p,k)]= TOPNODE;
      }

  }
/* We may end up with multiple variables not yet bound to a QEP. */
  qroot= QEPnew(MAXPARENT,mb->stop);
  for(i=1; i< mb->stop-1; i++){
      p= getInstrPtr(mb,i);
  
      k=0;
      if( p->barrier){
          k++;
          q= QEPnewNode(mb,p);
      } else
      for( j=0; j< p->retc; j++)
      if( status[getArg(p,j)] == TOPNODE){
          q= vq[getArg(p,j)];
          k++;
          break;
      }
      if(k)
          QEPappend(qroot,q);
  }
  GDKfree(vq);
  GDKfree(status);
  return qroot;
}
/* It may be handy to dump the graph for inspection
 * or to prepare for the dot program.*/
static void
QEPdump(stream *f, QEP qep, int indent){
  int i,inc = 0;
  str s;
  if( qep->p){
      for(i=0;i<indent; i++) mnstr_printf(f," ");
      s= instruction2str(qep->mb, 0,qep->p, LIST_MAL_STMT | LIST_MAPI);
      mnstr_printf(f,"%s\n",s);
      GDKfree(s);
      inc = 4;
  }
  for(i=0; i< qep->climit; i++)
  if( qep->children[i])
      QEPdump(f,qep->children[i], indent+ inc);
}

int
OPTdumpQEPImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p){
  QEP qep;
  (void) cntxt;
  (void) stk;
  (void) p;

  qep= QEPbuilt(mb);
  QEPdump(cntxt->fdout,qep,0);
  return 1;
}

6.范围传播

几乎所有的查询对表中的几个段有兴趣。如果用视图表示，查询计划经常含有对同一个列的选择。它们可能也修补了从碎片标准来的参数。 PUSHRANGES优化器的目的是最小化对表的范围的扫描。除非指令被移出计划。

1
2
3
4
5
6

b := bat.new(:oid,:int);
s1:= algebra.select(b,1,100);
s2:= algebra.select(s1,5,95);
s3:= algebra.select(s2,50,nil);
s4:= algebra.select(s3,nil,75);
optimizer.pushranges();

这么长的序列可以被压缩成一条：

1
2

b := bat.new(:oid,:int);
s1:= algebra.select(b,50,75);

从同一源码对两个范围的选择的并集可能是一个目标：

1
2
3

t1:= algebra.select(b,1,10);
t2:= algebra.select(b,0,5);
t3:= algebra.union(t1,t2);

会变为：

1

t3:= algebra.select(0,10);
MonetDB范围传播的优化代码实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

int OPTpushrangesImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr pci)
{
  int i,j, limit,actions=0;
  InstrPtr p, *old;
  int x,y,z;
  Range range;

  if( mb->errors)
      return 0;
  range= (Range) GDKzalloc(mb->vtop * sizeof(RangeRec));
  if (range == NULL)
      return 0;
  OPTDEBUGpushranges
      mnstr_printf(cntxt->fdout,"#Range select optimizer started\n");
  (void) stk;
  (void) pci;
  
  limit = mb->stop;
  old = mb->stmt;
  /* In phase I we collect information about constants*/
  for (i = 0; i < limit; i++) {
      p = old[i];
      if( p->barrier)
          break; /* end of optimizer */
      for(j=p->retc; j< p->argc; j++)
          range[getArg(p,j)].used++;
      for(j=0; j<p->retc; j++){
          range[getArg(p,j)].lastupdate= i;
          if( range[getArg(p,j)].lastrange == 0)
              range[getArg(p,j)].lastrange= i;
      } if( getModuleId(p)== algebraRef &&
          ( getFunctionId(p)== selectRef || getFunctionId(p)== uselectRef) ){
          /*
          * The operation X:= algebra.select(Y,L,H,Li,Hi) is analysed.
          * First, we attempt to propagate the range known for Y onto the
          * requested range of X. This may lead to smaller range of
          * even the conclusion that X is necessarily empty.
          * Of course, only under the condition that Y has not been changed by a
          * side-effect since it was bound to X.
          */
          x= getArg(p,1);
          y= getArg(p,2);
          if( range[x].lcst && isVarConstant(mb,y) ){
              /* merge lowerbound */
              if( ATOMcmp( getVarGDKType(mb,y),
                      VALptr( &getVarConstant(mb,range[x].lcst)),
                      VALptr( &getVarConstant(mb,y)) ) > 0){
                  getArg(p,2)= range[x].lcst;
                  z= range[x].srcvar;
                  if( getArg(p,1) == x &&
                      range[z].lastupdate == range[z].lastrange){
                      getArg(p,1) = z;
                      actions++;
                  }
              }
              y= getArg(p,3);
              /* merge higherbound */
              if( ATOMcmp( getVarGDKType(mb,y),
                      VALptr( &getVarConstant(mb,range[x].hcst)),
                      VALptr( &getVarConstant(mb,y)) ) < 0 ||
                  ATOMcmp( getVarGDKType(mb,y),
                      VALptr( &getVarConstant(mb,y)),
                       ATOMnilptr(getVarType(mb,y)) ) == 0){
                  getArg(p,3)= range[x].hcst;
                  z= range[x].srcvar;
                  if( getArg(p,1) == x && range[z].lastupdate == range[z].lastrange){
                      getArg(p,1) = z;
                      actions++;
                  }
              }
          }
          /*
          * The second step is to assign the result of this exercise to the
          * result variable.
          */
          x= getArg(p,0);
          if( isVarConstant(mb, getArg(p,2)) ){
              range[x].lcst = getArg(p,2);
              range[x].srcvar= getArg(p,1);
              range[x].lastupdate= range[x].lastrange = i;
          }
          if( isVarConstant(mb, getArg(p,3)) ){
              range[x].hcst = getArg(p,3);
              range[x].srcvar= getArg(p,1);
              range[x].lastupdate= range[x].lastrange = i;
          }
          /*
          * If both range bounds are constant, we can also detect empty results.
          * It is empty if L> H or when L=H and the bounds are !(true,true).
          */
          x= getArg(p,2);
          y= getArg(p,3);
          if( isVarConstant(mb, x)  &&
              isVarConstant(mb, y)  ){
              z =ATOMcmp( getVarGDKType(mb,y),
                        VALptr( &getVarConstant(mb,x)),
                        VALptr( &getVarConstant(mb,y)));
              x=  p->argc > 4;
              x= x && isVarConstant(mb,getArg(p,4));
              x= x && isVarConstant(mb,getArg(p,5));
              x= x && getVarConstant(mb,getArg(p,4)).val.btval;
              x= x && getVarConstant(mb,getArg(p,5)).val.btval;
              if( z > 0 || (z==0 && p->argc>4 && !x)) {
                  int var = getArg(p, 0);
                  wrd zero = 0;
                  ValRecord v, *vp;

                  vp = VALset(&v, TYPE_wrd, &zero);
                  varSetProp(mb, var, rowsProp, op_eq, vp);
                  /* create an empty replacement */
                  x = getArgType(mb, p, 1);
                  p->argc=1;
                  getModuleId(p)= batRef;
                  getFunctionId(p)= newRef;
                  p= pushArgument(mb,p, newTypeVariable(mb, getHeadType(x)));
                  (void) pushArgument(mb,p, newTypeVariable(mb, getTailType(x)));
                  actions++;
              }
          }
      }
  }
  OPTDEBUGpushranges
      for(j=0; j< mb->vtop; j++)
      if( range[j].used )
          printRange(cntxt, mb,range,j);
  /*
  * Phase II, if we succeeded in pushing constants around and
  * changing instructions, we might as well try once more to perform
  * aliasRemoval, constantExpression, and pushranges.
  */
  GDKfree(range);
  return actions;

7.循环再生器

在现有的数据库系统中查询优化和处理经常仍集中在各自的查询。查询分开地被分析和和内核赛跑不管并行或之前的调用提供的机遇。这种方法远离最优和两个方向被发现可以改善：物理化视图和（部分）结果集重使用。物理化视图从查询日志中继承。它们代表公共的子查询，其物理化改善接下来查询时间。重用部分结果被用于放大或导航应用处于危急关头的情况。循环再生优化器和模块扩展这with a middle out approach.它们利用MonetDB的materialize-all-intermediate方法来决定保留它们只要被认为有利。

采用的方法是在MAL程序中使用recycler优化器调用标记指令，以至它们的结果被保留在一个全局的再生寄宿于MAL解析器的缓冲。指令受Recycler管制如果至少它其中一个参数是BAT和其他不是常数或者变量，且在Recycler已知。在运行的时候，在没有代价下，Recycler被MAL解析器最里层的循环调用去检查一个更新的会被保留的结果。否则，它计算指令和调用policy functions去决定是否这值得保留。

Recycler有几个policy控制操作在具体的设置下实验它的效果。retain policy控制什么时候保留结果，reuse policy照看具体复制的指令或者使用语义知识在MAL指令去探测潜在的使用（例如，重用select 结果）。最后，cache policy照管中间结果pool的存储空间。具体的细节在重用模块描述：

MonetDB Recycler代码实现 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303

/** The variables are all checked for being eligible as a variable
 * subject to recycling control. A variable may only be assigned
 * a value once. The target function is a sql.bind(-,-,-,0) or all arguments
 * are already recycle enabled or constant.
 *
 * The arguments of a function call cannot be recycled.
 * They change with each call. This does not mean
 * that the instructions using them can not be a
 * target of recycling.
 *
 * Just looking at a target result kept is not good enough.
 * You have to sure that the arguments are also the same.
 * This rules out function arguments.
 *
 * The recycler is targeted towards a read-only database.
 * The best effect is obtained for a single-user mode (sql_debug=32 )
 * when the delta-bats are not processed which allows longer instruction
 * chains to be recycled.
 * Update statements are not recycled. They trigger cleaning of
 * the recycle cache at the end of the query. Only intermediates
 * derived from the updated columns are invalidated.
 * Separate update instructions in queries, such as bat.append implementing 'OR',
 * are monitored and also trigger cleaning the cache.*/
#include "monetdb_config.h"
#include "opt_recycler.h"
#include "mal_instruction.h"

static lng recycleSeq = 0;     /* should become part of MAL block basics */
static bte baseTableMode = 0;  /* only recycle base tables */
int OPTrecyclerImplementation(Client cntxt, MalBlkPtr mb, MalStkPtr stk, InstrPtr p)
{
  int i, j, cnt, tp, c, actions = 0, marks = 0, delta = 0;
  Lifespan span;
  InstrPtr *old, q;
  int limit, updstmt = 0;
  char *recycled;
  short app_sc = -1, in = 0;
  ValRecord cst;

  (void) cntxt;
  (void) stk;

  limit = mb->stop;
  old = mb->stmt;

  for (i = 1; i < limit; i++) {
      p = old[i];
      if (getModuleId(p) == sqlRef &&
              (getFunctionId(p) == affectedRowsRef ||
               getFunctionId(p) == exportOperationRef ||
               getFunctionId(p) == appendRef ||
               getFunctionId(p) == updateRef ||
               getFunctionId(p) == deleteRef))
          updstmt = 1;
  }

  span = setLifespan(mb);
  if (span == NULL)
      return 0;

  /* watch out, newly created instructions may introduce new variables */
  recycled = GDKzalloc(sizeof(char) * mb->vtop * 2);
  if (recycled == NULL)
      return 0;
  if (newMalBlkStmt(mb, mb->ssize) < 0) {
      GDKfree(recycled);
      return 0;
  }
  pushInstruction(mb, old[0]);
  mb->recid = recycleSeq++;

  /* create a handle for recycler */
  (void) newFcnCall(mb, "recycle", "prelude");
  in = 1;
  for (i = 1; i < limit; i++) {
      p = old[i];
      if (hasSideEffects(p, TRUE) || isUpdateInstruction(p) || isUnsafeFunction(p)) {
          if (getModuleId(p) == recycleRef) { /*don't inline recycle instr. */
              freeInstruction(p);
              continue;
          }
          pushInstruction(mb, p);
          /*  update instructions are not recycled but monitored*/
          if (isUpdateInstruction(p)) {
              if (getModuleId(p) == batRef &&
                  (getArgType(mb, p, 1) == TYPE_bat
                   || isaBatType(getArgType(mb, p, 1)))) {
                  recycled[getArg(p, 1)] = 0;
                  q = newFcnCall(mb, "recycle", "reset");
                  pushArgument(mb, q, getArg(p, 1));
                  actions++;
              }
              if (getModuleId(p) == sqlRef) {
                  if (getFunctionId(p) == appendRef) {
                      if (app_sc >= 0)
                          continue;
                      else
                          app_sc = getArg(p, 2);
                  }
                  VALset(&cst, TYPE_int, &delta);
                  c = defConstant(mb, TYPE_int, &cst);
                  q = newFcnCall(mb, "recycle", "reset");
                  pushArgument(mb, q, c);
                  pushArgument(mb, q, getArg(p, 2));
                  pushArgument(mb, q, getArg(p, 3));
                  if (getFunctionId(p) == updateRef)
                      pushArgument(mb, q, getArg(p, 4));
                  actions++;
              }
          }
          /* take care of SQL catalog update instructions */
          if (getModuleId(p) == sqlRef && getFunctionId(p) == catalogRef) {
              tp = *(int *) getVarValue(mb, getArg(p, 1));
              if (tp == 22 || tp == 25) {
                  delta = 2;
                  VALset(&cst, TYPE_int, &delta);
                  c = defConstant(mb, TYPE_int, &cst);
                  q = newFcnCall(mb, "recycle", "reset");
                  pushArgument(mb, q, c);
                  pushArgument(mb, q, getArg(p, 2));
                  if (tp == 25)
                      pushArgument(mb, q, getArg(p, 3));
                  actions++;
              }
          }
          continue;
      }
      if (p->token == ENDsymbol || p->barrier == RETURNsymbol) {
          if (in) {
              /*
             if (updstmt && app_sc >= 0) {
                 q = newFcnCall(mb, "recycle", "reset");
                 pushArgument(mb, q, app_sc);
                 pushArgument(mb, q, app_tbl);
             }
              */
              (void) newFcnCall(mb, "recycle", "epilogue");
              in = 0;
          }
          pushInstruction(mb, p);
          continue;
      }

      if (p->barrier && p->token != CMDcall) {
          /* never save a barrier unless it is a command and side-effect free */
          pushInstruction(mb, p);
          continue;
      }

      /* don't change instructions in update statements */
      if (updstmt) {
          pushInstruction(mb, p);
          continue;
      }

      /* skip simple assignments */
      if (p->token == ASSIGNsymbol) {
          pushInstruction(mb, p);
          continue;
      }

      if (getModuleId(p) == octopusRef &&
          (getFunctionId(p) == bindRef || getFunctionId(p) == bindidxRef)) {
          recycled[getArg(p, 0)] = 1;
          p->recycle = recycleMaxInterest;
          marks++;
      }
      /* During base table recycling skip marking instructions other than octopus.bind */
      if (baseTableMode) {
          pushInstruction(mb, p);
          continue;
      }

      /* general rule: all arguments are constants or recycled,
        ignore C pointer arguments from mvc */
      cnt = 0;
      for (j = p->retc; j < p->argc; j++)
          if (recycled[getArg(p, j)] || isVarConstant(mb, getArg(p, j))
                  || ignoreVar(mb, getArg(p, j)))
              cnt++;
      if (cnt == p->argc - p->retc) {
          OPTDEBUGrecycle {
              mnstr_printf(cntxt->fdout, "#recycle instruction\n");
              printInstruction(cntxt->fdout, mb, 0, p, LIST_MAL_ALL);
          }
          marks++;
          p->recycle = recycleMaxInterest; /* this instruction is to be monitored */
          for (j = 0; j < p->retc; j++)
              if (getLastUpdate(span, getArg(p, j)) == i)
                  recycled[getArg(p, j)] = 1;
      }
      /*
      * The expected gain is largest if we can re-use selections
      * on the base tables in SQL. These, however, are marked as
      * uselect() calls, which only produce the oid head.
      * For cheap types we preselect using select() and re-map uselect() back
      * over this temporary.
      * For the time being for all possible selects encountered
      * are marked for re-use.
      */
      /* take care of semantic driven recyling */
      /* for selections check the bat argument only
        the range is often template parameter*/
      if ((getFunctionId(p) == selectRef ||
                  getFunctionId(p) == antiuselectRef ||
                  getFunctionId(p) == likeselectRef ||
                  getFunctionId(p) == likeRef ||
                  getFunctionId(p) == thetaselectRef) &&
              recycled[getArg(p, 1)])
      {
          p->recycle = recycleMaxInterest;
          marks++;
          if (getLastUpdate(span, getArg(p, 0)) == i)
              recycled[getArg(p, 0)] = 1;
      }
      if ((getFunctionId(p) == uselectRef || getFunctionId(p) == thetauselectRef)
              && recycled[getArg(p, 1)])
      {
          if (!ATOMvarsized(getGDKType(getArgType(mb, p, 2)))) {
              q = copyInstruction(p);
              getArg(q, 0) = newTmpVariable(mb, TYPE_any);
              if (getFunctionId(p) == uselectRef)
                  setFunctionId(q, selectRef);
              else
                  setFunctionId(q, thetaselectRef);
              q->recycle = recycleMaxInterest;
              marks++;
              recycled[getArg(q, 0)] = 1;
              pushInstruction(mb, q);
              getArg(p, 1) = getArg(q, 0);
              setFunctionId(p, projectRef);
              p->argc = 2;
          }
          p->recycle = recycleMaxInterest;
          marks++;
          if (getLastUpdate(span, getArg(p, 0)) == i)
              recycled[getArg(p, 0)] = 1;
      }

      if (getModuleId(p) == pcreRef) {
          if ((getFunctionId(p) == selectRef && recycled[getArg(p, 2)]) ||
              (getFunctionId(p) == uselectRef && recycled[getArg(p, 2)])) {
              p->recycle = recycleMaxInterest;
              marks++;
              if (getLastUpdate(span, getArg(p, 0)) == i)
                  recycled[getArg(p, 0)] = 1;
          } else if (getFunctionId(p) == likeuselectRef && recycled[getArg(p, 1)]) {
              q = copyInstruction(p);
              getArg(q, 0) = newTmpVariable(mb, TYPE_any);
              setFunctionId(q, likeselectRef);
              q->recycle = recycleMaxInterest;
              recycled[getArg(q, 0)] = 1;
              pushInstruction(mb, q);
              getArg(p, 1) = getArg(q, 0);
              setFunctionId(p, projectRef);
              setModuleId(p, algebraRef);
              p->argc = 2;
              p->recycle = recycleMaxInterest;
              marks += 2;
              if (getLastUpdate(span, getArg(p, 0)) == i)
                  recycled[getArg(p, 0)] = 1;
          }
      }

      /*
      * The sql.bind instructions should be handled carefully
      * The delete and update BATs should not be recycled,
      * because they may lead to view dependencies that later interferes
      * with the transaction commits.
      */
      /* enable recycling of delta-bats
     if (getModuleId(p) == sqlRef &&
             (((getFunctionId(p) == bindRef || getFunctionId(p) == putName("bind_idxbat", 11)) &&
               getVarConstant(mb, getArg(p, 5)).val.ival != 0) ||
              getFunctionId(p) == binddbatRef)) {
         recycled[getArg(p, 0)] = 0;
         p->recycle = REC_NO_INTEREST;
     }
     */

/*
 * The sql.bind instructions should be handled carefully
 * The delete and update BATs should not be recycled,
 * because they may lead to view dependencies that later interferes
 * with the transaction commits.
 */
/* enable recycling of delta-bats
     if (getModuleId(p)== sqlRef && 
         (((getFunctionId(p)==bindRef || getFunctionId(p) == putName("bind_idxbat",11)) && 
             getVarConstant(mb, getArg(p,5)).val.ival != 0) ||
             getFunctionId(p)== binddbatRef) ) {
             recycled[getArg(p,0)]=0;
             p->recycle = REC_NO_INTEREST; 
         }
*/

      pushInstruction(mb, p);
  }
  GDKfree(span);
  GDKfree(old);
  GDKfree(recycled);
  mb->recycle = marks > 0;
  return actions + marks;

Comments