MonetDB- Why doubling self-joins can cause query execution time to go from milliseconds to hours on the same data?

Question

I'm running SQL queries on pretty simple table. Those tables model the RDF graph using the 'vertical partition' introduced here. Thus, they all have the following model where s is the 'subject' and o is the object.

CREATE TABLE a_table (BIGINT s, BIGINT o)

Given that I have 449669 tuples store in the table prop_eventPrecedeInTask. The following query (with 4 self-join on the table prop_eventPrecedeInTask) ran in 353 ms

SELECT t1.s AS event1, t2.o AS event2, t3.o AS event3, 
       t4.o AS event4, t5.o AS event5, t6.o AS event6 
FROM "prop_SystemCallIsExecutedDuringTask" t1,
     "prop_eventPrecedeInTask" t2,
     "prop_eventPrecedeInTask" t3,
     "prop_eventPrecedeInTask" t4,
     "prop_eventPrecedeInTask" t5,
     "prop_eventPrecedeInTask" t6          
WHERE t1.o = 15667
  AND t1.s = t2.s 
  AND t2.o = t3.s
  AND t3.o = t4.s
  AND t4.o = t5.s
  AND t5.o = t6.s;

But when I double the number of self-joins on the same table as the following query do (with 9 self joins), the query did not finish after an hour.

SELECT t1.s AS event1, t2.o AS event2, t3.o AS event3, 
       t4.o AS event4, t5.o AS event5, t6.o AS event6, 
       t7.o AS event7, t8.o AS event8, t9.o AS event9, 
       t10.o AS event10, t11.o AS event11 
FROM "prop_SystemCallIsExecutedDuringTask" t1,
     "prop_eventPrecedeInTask" t2,
     "prop_eventPrecedeInTask" t3,
     "prop_eventPrecedeInTask" t4,
     "prop_eventPrecedeInTask" t5,
     "prop_eventPrecedeInTask" t6,
     "prop_eventPrecedeInTask" t7,
     "prop_eventPrecedeInTask" t8,
     "prop_eventPrecedeInTask" t9,
     "prop_eventPrecedeInTask" t10,
     "prop_eventPrecedeInTask" t11 
WHERE t1.o = 15667
  AND t1.s = t2.s 
  AND t2.o = t3.s
  AND t3.o = t4.s
  AND t4.o = t5.s
  AND t5.o = t6.s
  AND t6.o = t7.s
  AND t7.o = t8.s
  AND t8.o = t9.s
  AND t9.o = t10.s
  AND t10.o = t11.s;

What is the explanation of drawbak in performances ? can I improve the query ?

configuration

I'm working on Ubuntu 12.0.4, with MonetDB Database Server v1.7 (Jan2014) on a 64G of RAM machine.

Adding the query execution trace (TRACE SELECT ...) of the query on a small dataset

+-------+------------------------------------------------------------------------------------------------------------+
| ticks | stmt                                                                                                           |
+=======+================================================================= ===========================================+
|    16 | X_3 := sql.mvc();                                                                                              |
|    28 | X_7=<tmp_1326>[3939] := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","o",0);                     |
|    36 | (X_59=<tmp_21>[0],r1_129=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",2);            |
|    20 | X_72=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",1);                                 |
|    13 | X_62=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",1);                                 |
|    30 | X_55:bat[:oid,:oid] =<tmp_17710>[78450] := sql.tid(X_3=0,"sys","prop_eventPrecedeInTask");                 |
|    16 | X_37=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",1);                                 |
|    16 | (X_34=<tmp_21>[0],r1_40=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",2);             |
|    14 | X_32=<tmp_2063>[78450] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",0);                           |
|    15 | X_28=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",1);                                 |
|    13 | (X_26=<tmp_21>[0],r1_31=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",2);             |
|    13 | X_25=<tmp_2055>[78450] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",0);                          |
|    21 | X_23:bat[:oid,:oid] =<tmp_25746>[78450] := sql.tid(X_3=0,"sys","prop_eventPrecedeInTask");                 |
|    30 | X_29=<tmp_33332>[78450] := sql.projectdelta(X_23=<tmp_25746>:bat[:oid,:oid][78450],X_25=<tmp_2055>[78450], 
| 
:       : X_26=<tmp_21>[0],r1_31=<tmp_33>[0],X_28=<tmp_33>[0]);                                                      :
|    21 | (X_69=<tmp_21>[0],r1_140=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",2);            |
|    21 | X_21=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","s",1);                     |
|    14 | (X_19=<tmp_21>[0],r1_22=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","s",2); |
|    12 | X_17=<tmp_1320>[3939] := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","s",0);                |
|    11 | X_13=<tmp_33>[0] := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","o",1);                     |
|    20 | (X_10=<tmp_21>[0],r1_10=<tmp_33>[0]) := sql.bind(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask","o",2); |
|    24 | X_149=<tmp_34471>[0] := algebra.subselect(r1_10=<tmp_33>    [0],A0=15667:lng,A0=15667:lng,true,true,false);    |
|    18 | X_4:bat[:oid,:oid] =<tmp_4731>[3939] := sql.tid(X_3=0,"sys","prop_SystemCallIsExecutedDuringTask");        |
|   113 | X_148=<tmp_21746>[0] := algebra.subselect(X_7=<tmp_1326>[3939],X_4=<tmp_4731>:bat[:oid,:oid][3939],A0=1566 |
:       : 7:lng,A0=15667:lng,true,true,false);                                                                       :
|    24 | X_150=<tmp_6675>[0] := algebra.subselect(X_13=<tmp_33>[0],X_4=<tmp_4731>:bat[:oid,:oid][3939],A0=15667:lng |
:       : ,A0=15667:lng,true,true,false);                                                                            :
|    27 | X_38=<tmp_32620>[78450] := sql.projectdelta(X_23=<tmp_25746>:bat[:oid,:oid][78450],X_32=<tmp_2063>[78450], |
:       : X_34=<tmp_21>[0],r1_40=<tmp_33>[0],X_37=<tmp_33>[0]);                                                      :
|     8 | language.pass(X_23=<tmp_25746>:bat[:oid,:oid][78450]);                                                     |
|    15 | X_56=<tmp_2055>[78450] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","s",0);                           |
|    31 | X_65=<tmp_33344>[78450] := sql.projectdelta(X_55=<tmp_17710>:bat[:oid,:oid][78450],X_56=<tmp_2055>[78450], |
:       : X_59=<tmp_21>[0],r1_129=<tmp_33>[0],X_62=<tmp_33>[0]);                                                     :
|    17 | X_68=<tmp_2063>[78450] := sql.bind(X_3=0,"sys","prop_eventPrecedeInTask","o",0);                           |
|    11 | X_15=<tmp_21746>[0] := sql.subdelta(X_148=<tmp_21746>[0],X_4=<tmp_4731>:bat[:oid,:oid][3939],X_10=<tmp_21> |
:       : [0],X_149=<tmp_34471>[0],X_150=<tmp_6675>[0]);                                                             :
|    13 | language.pass(X_4=<tmp_4731>:bat[:oid,:oid][3939]);                                                        |
|    43 | X_22=<tmp_25746>[0] := sql.projectdelta(X_15=<tmp_21746>[0],X_17=<tmp_1320>[3939],X_19=<tmp_21>[0],r1_22=< |
:       : tmp_33>[0],X_21=<tmp_33>[0]);                                                                              :
|    33 | (X_30=<tmp_21746>[0],r1_36=<tmp_12754>[0]) := algebra.join(X_22=<tmp_25746>[0],X_29=<tmp_33332>[78450]);   |
|    38 | X_39=<tmp_23566>[0] := algebra.leftfetchjoin(r1_36=<tmp_12754>[0],X_38=<tmp_32620>[78450]);                |
|    28 | (X_40=<tmp_12754>[0],r1_58=<tmp_4661>[0]) := algebra.join(X_39=<tmp_23566>[0],X_29=<tmp_33332>[78450]);    |
|    29 | X_42=<tmp_10412>[0] := algebra.leftfetchjoin(r1_58=<tmp_4661>[0],X_38=<tmp_32620>[78450]);                 |
|    18 | (X_43=<tmp_4661>[0],r1_76=<tmp_4056>[0]) := algebra.join(X_42=<tmp_10412>[0],X_29=<tmp_33332>[78450]);     |
|    18 | X_45=<tmp_11601>[0] := algebra.leftfetchjoin(r1_76=<tmp_4056>[0],X_38=<tmp_32620>[78450]);                 |
|    14 | (X_46=<tmp_4056>[0],r1_97=<tmp_14043>[0]) := algebra.join(X_45=<tmp_11601>[0],X_29=<tmp_33332>[78450]);    |
|    26 | X_73=<tmp_33524>[78450] := sql.projectdelta(X_55=<tmp_17710>:bat[:oid,:oid][78450],X_68=<tmp_2063>[78450], |
:       : X_69=<tmp_21>[0],r1_140=<tmp_33>[0],X_72=<tmp_33>[0]);                                                     :
|    10 | language.pass(X_55=<tmp_17710>:bat[:oid,:oid][78450]);                                                     |
|  9434 | X_49=<tmp_13521>[0] := algebra.leftfetchjoin(r1_97=<tmp_14043>[0],X_38=<tmp_32620>[78450]);                |
|    47 | (X_51=<tmp_14043>[0],r1_115=<tmp_36607>[0]) := algebra.join(X_49=<tmp_13521>[0],X_29=<tmp_33332>[78450]);  |
|     6 | language.pass(X_29=<tmp_33332>[78450]);                                                                    |
|    23 | X_54=<tmp_33332>[0] := algebra.leftfetchjoin(r1_115=<tmp_36607>[0],X_38=<tmp_32620>[78450]);               |
|     7 | language.pass(X_38=<tmp_32620>[78450]);                                                                    |
|    30 | (X_66=<tmp_4731>[0],r1_137=<tmp_6675>[0]) := algebra.join(X_54=<tmp_33332>[0],X_65=<tmp_33344>[78450]);    |
|    19 | X_74=<tmp_34471>[0] := algebra.leftfetchjoin(r1_137=<tmp_6675>[0],X_73=<tmp_33524>[78450]);                |
|    17 | (X_75=<tmp_6675>[0],r1_154=<tmp_4677>[0]) := algebra.join(X_74=<tmp_34471>[0],X_65=<tmp_33344>[78450]);    |
|    14 | X_77=<tmp_11503>[0] := algebra.leftfetchjoin(r1_154=<tmp_4677>[0],X_73=<tmp_33524>[78450]);                |
|    13 | (X_78=<tmp_4677>[0],r1_176=<tmp_6501>[0]) := algebra.join(X_77=<tmp_11503>[0],X_65=<tmp_33344>[78450]);    |
|    15 | X_80=<tmp_24055>[0] := algebra.leftfetchjoin(r1_176=<tmp_6501>[0],X_73=<tmp_33524>[78450]);                |
|    14 | (X_81=<tmp_6501>[0],r1_193=<tmp_7616>[0]) := algebra.join(X_80=<tmp_24055>[0],X_65=<tmp_33344>[78450]);    |
|    16 | X_83=<tmp_25373>[0] := algebra.leftfetchjoin(r1_193=<tmp_7616>[0],X_73=<tmp_33524>[78450]);                |
|    29 | (X_84=<tmp_7616>[0],r1_216=<tmp_7215>[0]) := algebra.join(X_83=<tmp_25373>[0],X_65=<tmp_33344>[78450]);    |
|     7 | language.pass(X_65=<tmp_33344>[78450]);                                                                    |
|    67 | X_98=<tmp_17710>[0] := algebra.leftfetchjoin(r1_216=<tmp_7215>[0],X_73=<tmp_33524>[78450]);                |
|     2 | language.pass(X_73=<tmp_33524>[78450]);                                                                    |
|  1129 | X_151=<tmp_26246>[0] := algebra.leftfetchjoin(X_84=<tmp_7616>[0],X_81=<tmp_6501>[0]);                      |
|    85 | X_86:bat[:oid,:lng] =<tmp_6501>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X_ |
:       : 75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_51=<tmp_14043>[0],X_46=<tmp_4056>[0],X_43=<tmp_4661>[0],X_40=<tmp_12 :
:       : 754>[0],X_30=<tmp_21746>[0],X_22=<tmp_25746>[0]);                                                          :
|    67 | X_95=<tmp_32620>[0] := algebra.leftfetchjoin(X_84=<tmp_7616>[0],X_83=<tmp_25373>[0]);                      |
|     3 | language.pass(X_84=<tmp_7616>[0]);                                                                         |
|     2 | language.pass(X_83=<tmp_25373>[0]);                                                                        |
|    14 | X_89:bat[:oid,:lng] =<tmp_7616>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X_ |
:       : 75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_51=<tmp_14043>[0],X_46=<tmp_4056>[0],X_45=<tmp_11601>[0]);           :
|     2 | language.pass(X_45=<tmp_11601>[0]);                                                                        |
|    79 | X_87:bat[:oid,:lng] =<tmp_10432>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X |
:       : _75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_51=<tmp_14043>[0],X_46=<tmp_4056>[0],X_43=<tmp_4661>[0],X_40=<tmp_1 :
:       : 2754>[0],X_39=<tmp_23566>[0]);                                                                             :
|     2 | language.pass(X_40=<tmp_12754>[0]);                                                                        |
|     7 | language.pass(X_22=<tmp_25746>[0]);                                                                        |
|  6902 | X_88:bat[:oid,:lng] =<tmp_33524>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X |
:       : _75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_51=<tmp_14043>[0],X_46=<tmp_4056>[0],X_43=<tmp_4661>[0],X_42=<tmp_1 :
:       : 0412>[0]);                                                                                                 :
|     2 | language.pass(X_46=<tmp_4056>[0]);                                                                         |
| 27091 | X_90:bat[:oid,:lng] =<tmp_11601>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X |
:       : _75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_51=<tmp_14043>[0],X_49=<tmp_13521>[0]);                             :
|     5 | language.pass(X_43=<tmp_4661>[0]);                                                                         |
|     3 | language.pass(X_51=<tmp_14043>[0]);                                                                        |
|     2 | language.pass(X_49=<tmp_13521>[0]);                                                                        |
|    26 | X_91:bat[:oid,:lng] =<tmp_25746>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X |
:       : _75=<tmp_6675>[0],X_66=<tmp_4731>[0],X_54=<tmp_33332>[0]);                                                 :
|    24 | X_92:bat[:oid,:lng] =<tmp_13521>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X |
:       : _75=<tmp_6675>[0],X_74=<tmp_34471>[0]);                                                                    :
|     2 | language.pass(X_75=<tmp_6675>[0]);                                                                         |
|     1 | language.pass(X_54=<tmp_33332>[0]);                                                                        |
|    10 | X_93:bat[:oid,:lng] =<tmp_6675>[0] := algebra.leftfetchjoinPath(X_151=<tmp_26246>[0],X_78=<tmp_4677>[0],X_ |
:       : 77=<tmp_11503>[0]);                                                                                        :
|     1 | language.pass(X_78=<tmp_4677>[0]);                                                                         |
|     1 | language.pass(X_74=<tmp_34471>[0]);                                                                        |
|     7 | X_94:bat[:oid,:lng] =<tmp_34471>[0] := algebra.leftfetchjoin(X_151=<tmp_26246>[0],X_80=<tmp_24055>[0]);    |
|     1 | language.pass(X_151=<tmp_26246>[0]);                                                                       |
|     2 | language.pass(X_77=<tmp_11503>[0]);                                                                        |
|     2 | language.pass(X_80=<tmp_24055>[0]);                                                                        |
|     9 | language.pass(X_42=<tmp_10412>[0]);                                                                        |
|     3 | language.pass(X_66=<tmp_4731>[0]);                                                                         |
|     4 | language.pass(X_39=<tmp_23566>[0]);                                                                        |
| 65664 | barrier X_178 := language.dataflow();                                                                      |
|     9 | X_99 := sql.resultSet(11,1,X_86=<tmp_6501>:bat[:oid,:lng][0]);                                             |
|     6 | sql.rsColumn(X_99=4,"sys.L","event1","bigint",64,0,X_86=<tmp_6501>:bat[:oid,:lng][0]);                     |
|     4 | sql.rsColumn(X_99=4,"sys.L","event2","bigint",64,0,X_87=<tmp_10432>:bat[:oid,:lng][0]);                    |
|     4 | sql.rsColumn(X_99=4,"sys.L","event3","bigint",64,0,X_88=<tmp_33524>:bat[:oid,:lng][0]);                    |
|     3 | sql.rsColumn(X_99=4,"sys.L","event4","bigint",64,0,X_89=<tmp_7616>:bat[:oid,:lng][0]);                     |
|     3 | sql.rsColumn(X_99=4,"sys.L","event5","bigint",64,0,X_90=<tmp_11601>:bat[:oid,:lng][0]);                    |
|     3 | sql.rsColumn(X_99=4,"sys.L","event6","bigint",64,0,X_91=<tmp_25746>:bat[:oid,:lng][0]);                    |
|     2 | sql.rsColumn(X_99=4,"sys.L","event7","bigint",64,0,X_92=<tmp_13521>:bat[:oid,:lng][0]);                    |
|     3 | sql.rsColumn(X_99=4,"sys.L","event8","bigint",64,0,X_93=<tmp_6675>:bat[:oid,:lng][0]);                     |
|     5 | sql.rsColumn(X_99=4,"sys.L","event9","bigint",64,0,X_94=<tmp_34471>:bat[:oid,:lng][0]);                    |
|     5 | sql.rsColumn(X_99=4,"sys.L","event10","bigint",64,0,X_95=<tmp_32620>[0]);                                  |
|     5 | sql.rsColumn(X_99=4,"sys.L","event11","bigint",64,0,X_98=<tmp_17710>[0]);                                  |
|     2 | X_127 := io.stdout();                                                                                      |
|    30 | sql.exportResult(X_127=="104d2":streams,X_99=4);                                                           |
|     1 | end s3_3;                                                                                                  |
| 66047 | function user.s3_3(A0=15667:lng);                                                                          |
| 66145 | X_5:void  := user.s3_3(15667:lng);                                                                         |
+-------+------------------------------------------------------------------------------------------------------------+

EDIT 2 Modification of tuple type from INT to BIGINT

If you run your queries with `TRACE` (e.g. `TRACE SELECT ...`), you will get breakdown of the runtime and cardinality of all operators that are run for this query. You should be able to see where time goes. If you post the output, I can say more. — Hannes Mühleisen, Mar 22 '15 at 07:37
hi @HannesMühleisen I added the trace of the query execution on a smaller dataset. the execution of the TRACE SELECT .... on the bigger dataset take as much time as the query itself wishing that it helps. — Fopa Léon Constantin, Mar 22 '15 at 13:37
My guess would be that the intermediate result of the join exceeds the amount of available main memory. Can you try increasing the amount of selfjoins one at a time? — Hannes Mühleisen, Mar 24 '15 at 11:46
@HannesMühleisen i'm not sure to understand your suggestion. Do you mean that I execute multiple queries with increasing number of self-join ? What will be the difference in this case since the amount of memory needed will still be greater than the available memory ? — Fopa Léon Constantin, Mar 24 '15 at 12:32
Yes, but you will find out where it goes from very fast to very slow. I think the intermediate results of that query are simply too large. — Hannes Mühleisen, Mar 24 '15 at 12:50
This Problem occur when Memory reserved for Query reached, instead of increasing Query memory, split query in multiples, like have query self joins limit to 6, now join resultant queries. — sharafjaffri, Mar 31 '15 at 07:20
@sharafjaffri, thank for your comment but I'm not getting it well. I did not know that there were a query memory limitation. Is it possible to change it and does this change actually impact query performance ? Alson, I did not get how to perform your idea of splitting the query in multiple. Do you have any resources (links, pdf, ...) where I can find more details ? — Fopa Léon Constantin, Mar 31 '15 at 09:58
That's called work_mem(working memory) in postgesql, Don't know if this is available to change in Monetdb. — sharafjaffri, Mar 31 '15 at 11:18

MonetDB- Why doubling self-joins can cause query execution time to go from milliseconds to hours on the same data?

0 Answers0