Bug 3992

Summary: unions not reusable -> plans explode
Product: SQL Reporter: Roberto Cornacchia <roberto.cornacchia>
Component: allAssignee: SQL devs <bugs-sql>
Status: ASSIGNED ---    
Severity: normal CC: mk
Priority: Normal    
Version: 11.21.19 (Jul2015-SP4)   
Hardware: Other   
OS: Linux   

Description Roberto Cornacchia 2016-04-25 18:06:25 CEST
User-Agent:       Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/50.0.2661.86 Safari/537.36
Build Identifier: 

If I'm not mistaken, the bat.new() + bat.append() pattern that is used to implement union is marked as "side effect" and thus not reusable. However, at least within the same transaction, I don't see why it shouldn't. This can have a serious performance impact. 


start transaction;

-- a small table
create table t(value int);
insert into t values (0),(1);

-- a union
create view x as 
select * from t
union all
select * from t;

-- use the previous union twice, it actually creates two copies of it
explain select x1.value
from x x1,x x2
where x1.value = x2.value;

| mal                                                                                                                        |
| function user.s8_1():void;                                                                                                 |
|     X_43:void := querylog.define("explain select x1.value\nfrom x x1,x x2\nwhere x1.value = x2.value;","default_pipe",30); |
| barrier X_57 := language.dataflow();                                                                                       |
|     X_25 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_33 := bat.append(X_25,".x1");                                                                                        |
|     X_27 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_35 := bat.append(X_27,"value");                                                                                      |
|     X_29 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_37 := bat.append(X_29,"int");                                                                                        |
|     X_30 := bat.new(nil:oid,nil:int);                                                                                      |
|     X_39 := bat.append(X_30,32);                                                                                           |
|     X_32 := bat.new(nil:oid,nil:int);                                                                                      |
|     X_41 := bat.append(X_32,0);                                                                                            |
|     X_2:bat[:oid,:int] := bat.new(nil:oid,nil:int);                                                                        |
|     X_1 := sql.mvc();                                                                                                      |
|     X_5:bat[:oid,:oid] := sql.tid(X_1,"spinque","t");                                                                      |
|     X_8:bat[:oid,:int] := sql.bind(X_1,"spinque","t","value",0);                                                           |
|     X_11 := algebra.leftfetchjoin(X_5,X_8);                                                                                |
|     X_12 := bat.append(X_2,X_11,true);                                                                                     |
|     X_14 := bat.append(X_12,X_11,true);                                                                                    |
|     X_15:bat[:oid,:int] := bat.new(nil:oid,nil:int);                                                                       |
|     X_16 := bat.append(X_15,X_11,true);                                                                                    |
|     X_17 := bat.append(X_16,X_11,true);                                                                                    |
|     (X_18,r1_27) := algebra.subjoin(X_14,X_17,nil:BAT,nil:BAT,false,nil:lng);                                              |
|     X_23 := algebra.leftfetchjoin(X_18,X_14);                                                                              |
|     language.pass(X_11);                                                                                                   |
|     language.pass(X_14);                                                                                                   |
| exit X_57;                                                                                                                 |
|     sql.resultSet(X_33,X_35,X_37,X_39,X_41,X_23);                                                                          |
| end user.s8_1;                                                                                                             |

In the explain above it is guaranteed that X_16 = X_12 and X_17 = X_14.
However they get recomputed. 

When this happens at the beginning of a plan, the plan becomes almost 2x bigger. Every times this happens again, the plan forks into two identical branches. The growth becomes exponential and quickly out of control for plans not as trivial as the one above. Not only the same results get recomputed, but the plan becomes so big that it takes even seconds to generate, for queries that should be built + executed in less that 100ms.

This is strictly related to bug 3361. Different causes, but same effect.

Reproducible: Always
Comment 1 Martin Kersten cwiconfidential 2016-04-25 20:24:57 CEST
In this particular case, a human may detect the recurring macro pattern involving 4 MAL instructions. Algorithmically it is a much harder case, most likely NP-complete, because you have to be prepared for arbitrary long/complex patterns. 
Also notice that you plan is not parallel, which aggravates the performance impact. 

The recycler optimizer may detect it, but sure how it will work out currently.
Comment 2 Roberto Cornacchia 2016-04-26 09:30:57 CEST
I suppose it all stems from the fact that C := bat.append(A,B) modifies A (appends in place), and this is probably done to avoid data copying that would instead happen with something like C := concat(A,B) (where A and B are not modified). 

Obviously the two patterns

A' := bat.new(..);
C' := bat.append(A',A);
C := bat.append(C',B);


C := bat.concat(A,B);

are fully equivalent in terms of data copying, but the first pattern is faster for any subsequent append.

Even so, isn't it the case that any of the results in the first pattern (in any pattern, actually) can be considered reusable as long as it is not used by instructions with side-effects?

- A' cannot be reused, because it is modified by the first append
- C' cannot be reused, because it is modified by the second append
- C can be reused, because it isn't used by any instruction with side-effect.

In the worst case I see a quadratic search space, which is the same as the standard commonTerms optimizer. 
Am I missing something?
Comment 3 Roberto Cornacchia 2016-05-06 19:00:34 CEST
As a quick proof of concept, I changed the translation of UNION, to use a side-effect-free operation.
UNION now maps to algebra.tconcat() command (see below, X_9). For now I have implemented this naively as two BATloops that append all tuples from the two arguments into a new bat (similar to tunion, except that it does not remove duplicates and produce a void head).

The example I originally posted is no longer duplicating work:

| mal                                                                                                                        |
| function user.s5_1():void;                                                                                                 |
|     X_34:void := querylog.define("explain select x1.value\nfrom x x1,x x2\nwhere x1.value = x2.value;","default_pipe",25); |
| barrier X_48 := language.dataflow();                                                                                       |
|     X_17 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_25 := bat.append(X_17,"spinque.x1");                                                                                 |
|     X_20 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_27 := bat.append(X_20,"value");                                                                                      |
|     X_21 := bat.new(nil:oid,nil:str);                                                                                      |
|     X_28 := bat.append(X_21,"int");                                                                                        |
|     X_22 := bat.new(nil:oid,nil:int);                                                                                      |
|     X_30 := bat.append(X_22,32);                                                                                           |
|     X_24 := bat.new(nil:oid,nil:int);                                                                                      |
|     X_32 := bat.append(X_24,0);                                                                                            |
|     X_1 := sql.mvc();                                                                                                      |
|     X_2:bat[:oid,:oid] := sql.tid(X_1,"spinque","t");                                                                      |
|     X_5:bat[:oid,:int] := sql.bind(X_1,"spinque","t","value",0);                                                           |
|     X_8 := algebra.leftfetchjoin(X_2,X_5);                                                                                 |
|     X_9 := algebra.tconcat(X_8,X_8);                                                                                       |
|     (X_10,r1_20) := algebra.subjoin(X_9,X_9,nil:BAT,nil:BAT,false,nil:lng);                                                |
|     X_15 := algebra.leftfetchjoin(X_10,X_9);                                                                               |
|     language.pass(X_8);                                                                                                    |
|     language.pass(X_9);                                                                                                    |
| exit X_48;                                                                                                                 |
|     sql.resultSet(X_25,X_27,X_28,X_30,X_32,X_15);                                                                          |
| end user.s5_1;                                                                                                             |

I tried this on one of our long queries, obtaining the same results for:
- UNION -> bat.append() : 2517 MAL instructions
- UNION -> algebra.tconcat() : 694 MAL instructions
Comment 4 Roberto Cornacchia 2016-05-08 11:18:04 CEST
The solution above (tconcat) is, as far as I can tell, simple, safe, and effective. The advantages of in-place append can be exploited only when unioning at least 3 (large) tables in the same query. The benefit balance is for me clearly on the tconcat side, so we will most likely keep it in our codebase.

About this report: I have a working solution now - feel free to close as won't fix if the existing translation fits better the patterns you observe. 

I would be still interested to learn whether you guys would consider this as a viable option in general, and if not, why.
Comment 5 Martin Kersten cwiconfidential 2017-08-12 17:56:53 CEST
I contrived example which is hard to detect in general.

I would say that this view is an application error:
create view x as 
select * from t
union all
select * from t;

In most cases the view components will identify a different part of the database.

create view x as 
select * from t where value > 0
union all
select * from t where value < 0;

The same holds for the multiple uses:
explain select x1.value
from x x1,x x2
where x1.value = x2.value and x1.value == 0 and x2.value >1

Detecting repetition at the MAL level is practically impossible and
calculation of a view only once within a query kills potential
other optimizations.
Comment 6 Roberto Cornacchia 2017-08-13 02:29:12 CEST
Martin, based on my experience and my experiments I cannot agree with your last comment. 
However I think this needs a more in-depth discussion than what is allowed on this platform. As you know I am keen to come and show some results soon.
Comment 7 Martin Kersten cwiconfidential 2019-07-27 23:30:30 CEST
Combining a serial append operation into a single multi-concat bears with it
the consequence that temporary variables are kept around longer than strictly
necessary. This means that the footprint becomes twice the final result

A' := bat.new(..);
B' := bat.append(A',A);
C' := bat.append(B', B);
D  := bat.append(C', C);
N := bat.append(M', M)

N = tconcat(B,C,D,...,M)

which looks like a mat.pack where we also do it incremental to avoid this
enlarged footprint.

A side issue is that we don't know the size of the components and we have to
keep in mind that their oid ranges may be used as well in the query.

A nested construction ( concat(concat(A,B), concat(C,D)) would become more expensive as you would copy too much around.

Relaxing the side-effect is something to look into further. For simple cases it does not hold and could this program be executed in parallel.
The following might work

B' := mat.packincrement(A,<unknown>);
C' := mat.packincrement(B', B);
D  := mat.packincrement(C', C);
N := mat.packincrement(M', M)