(i)like generates batloop instead of algebra.likesubselect

[monetdb-team]

Date: 2013-09-26 10:52:35 +0200
From: @swingbit
To: SQL devs <>
Version: 11.15.19 (Feb2013-SP6)
CC: @njnes

Last updated: 2014-02-20 15:03:06 +0100

Comment 19178

Date: 2013-09-26 10:52:35 +0200
From: @swingbit

User-Agent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/29.0.1547.57 Safari/537.36
Build Identifier:

Take the following :

explain
with x as (select '%max%' as s)
select name from sys.functions, x
where name LIKE s;

I would expect a join, i.e. a bat-oriented like implementation to be called.
Instead, the like is computed in a loop as follows (only the relevant bit):

| barrier (X_78,X_79) := iterator.new(X_27); |
| X_81 := algebra.fetch(X_28,X_78); |
| X_83 := str.like(X_79,X_81,""); |
| X_84 := algebra.fetch(X_72,X_78); |
| bat.insert(X_74,X_84,X_83); |
| redo (X_78,X_79) := iterator.next(X_27); |
| exit (X_78,X_79); |

Looking at the available functions, I see:

| 5116 | like | create filter function "like"(val string, pat string, esc string) external name algebra.likesubselect;

A filter function is bound to give me a join, I thought.
However, if I rewrite my query as this:

explain
with x as (select '%max%' as s)
select name from sys.functions, x
where "ilike"(name,s,'');

I still get the same loop, and no algebra.likesubselect() call.

Reproducible: Always

Comment 19187

Date: 2013-09-27 09:24:45 +0200
From: @njnes

currently we don't rewrite joins into selects (ie where one side of the join is a single value).

Comment 19191

Date: 2013-09-27 10:00:40 +0200
From: @swingbit

I didn't mean a rewrite into select. On the contrary, it is exactly the join that I would expect (in this case with a singleton on one side, but that wasn't the point). Instead, I get loops with fetch, like, fetch, insert. These are literally killing the query.

Forget the singleton, an consider the following. I call the function "ilike" explicitly with 3 arguments, which should trigger algebra.likesubselect:

| 5116 | like | create filter function "like"(val string, pat string, esc string) external name algebra.likesubselect;

But even by just using the LIKE operator, this should be a join, not a loop.

start transaction;
create table x (s string);
insert into x values ('%max%'),('%min%');

explain
select name from sys.functions, x
where "ilike"(name,s,'');

+-----------------------------------------------------------------------+
| mal |
+=======================================================================+
| function user.s2_1(A0:str):void; |
| X_30:bat[:oid,:str] := nil:bat[:oid,:str]; |
| X_31:bat[:oid,:str] := nil:bat[:oid,:str]; |
| barrier X_62 := language.dataflow(); |
| X_2 := sql.mvc(); |
| X_3:bat[:oid,:oid] := sql.tid(X_2,"sys","functions"); |
| X_6 := sql.bind(X_2,"sys","functions","id",0); |
| (X_9,r1_9) := sql.bind(X_2,"sys","functions","id",2); |
| X_12 := sql.bind(X_2,"sys","functions","id",1); |
| X_14 := sql.delta(X_6,X_9,r1_9,X_12); |
| X_15 := algebra.leftfetchjoin(X_3,X_14); |
| X_16:bat[:oid,:oid] := sql.tid(X_2,"spinque","x"); |
| X_19 := sql.bind(X_2,"spinque","x","s",0); |
| X_21 := algebra.leftfetchjoin(X_16,X_19); |
| (X_22,r1_26) := algebra.crossproduct(X_15,X_21); |
| X_24 := sql.bind(X_2,"sys","functions","name",0); |
| (X_26,r1_30) := sql.bind(X_2,"sys","functions","name",2); |
| X_28 := sql.bind(X_2,"sys","functions","name",1); |
| X_29 := sql.delta(X_24,X_26,r1_30,X_28); |
| X_30:bat[:oid,:str] := algebra.leftfetchjoinPath(X_22,X_3,X_29); |
| X_31:bat[:oid,:str] := algebra.leftfetchjoin(r1_26,X_21); |
| language.pass(X_3); |
| language.pass(X_21); |
| exit X_62; |
| X_72:bat[:str,:oid] := bat.reverse(X_30); |
| X_74 := bat.new(nil:oid,nil:bit); |
| barrier (X_78,X_79) := iterator.new(X_30); |
| X_81 := algebra.fetch(X_31,X_78); |
| X_83 := str.ilike(X_79,X_81,A0); |
| X_84 := algebra.fetch(X_72,X_78); |
| bat.insert(X_74,X_84,X_83); |
| redo (X_78,X_79) := iterator.next(X_30); |
| exit (X_78,X_79); |
| X_31:bat[:oid,:str] := nil:bat[:oid,:str]; |
| X_72:bat[:str,:oid] := nil:bat[:str,:oid]; |
| X_32:bat[:oid,:bit] := X_74; |
| X_36 := algebra.subselect(X_32,true,true,true,true,false); |
| X_38 := algebra.leftfetchjoin(X_36,X_30); |
| X_40 := sql.resultSet(1,1,X_38); |
| sql.rsColumn(X_40,"sys.functions","name","varchar",256,0,X_38); |
| X_47 := io.stdout(); |
| sql.exportResult(X_47,X_40); |
| end s2_1; |
+-----------------------------------------------------------------------+
43 tuples (3.048ms)

Comment 19195

Date: 2013-09-27 10:44:57 +0200
From: @njnes

this case goes indeed wrong, but thats only the function. The ilike/like operator do get a join when the right hand side has more then one row.

Comment 19196

Date: 2013-09-27 10:48:18 +0200
From: @swingbit

True, the LIKE operator goes right.

Question: Why is the singleton case using a loop? Wouldn't a join still be faster, avoiding all the MAL overhead?

Comment 19197

Date: 2013-09-27 11:08:48 +0200
From: @njnes

sure the singleton case could be a join too, but we currently have a problem detecting the difference between join and select case in this part of the code (ie implementation short coming, which should be solvable somehow).

So basically we are looking at 2 problems

1. ilike/like = true -> ilike/like filter rewrites fail somehow for the join case
2. the join(a, const) isn't handled efficiently (falls back to an incorrect/inefficient select)

Comment 19198

Date: 2013-09-27 11:15:45 +0200
From: @swingbit

I see, thanks for the details.

Comment 19399

Date: 2013-12-08 21:10:58 +0100
From: @njnes

relational join's with between atleast one constant relation are now rewritten into select's.

Comment 19622

Date: 2014-02-20 15:03:06 +0100
From: @sjoerdmullender

Jan2014 has been released.