QueryPlannerTest flakyness

[niklas88]

The QueryPlannerTest seems to rely on an exact match of test query plans. In reality which plan is chosen (among equivalent ones) seems to depend on some random factor such as the exact order of hash map entries or some other detail (haven't found the exact cause yet).

I remember seeing this on different Linux distributions @floriankramer can you confirm?

However more importantly this currently breaks the test and thus the docker build on IBM Z (s390x). The log for shows the test failures that look like equivalent trees to me but I'd like to hear @floriankramer or @joka921 opinion before changing the test without knowing what exactly causes this.

Note: One important difference between IBM Z and (almost) all other Linux platforms is that it is natively Big Endian so for example ordering ints by their byte representation will yield a different (though consistent) ordering. Also note that when the QueryPlannerTest is skipped the End-to-End Tests work perfectly so we do get a functional system.

[ RUN      ] QueryPlannerTest.testStarTwoFree
Mon Nov 18 19:37:17.500	- DEBUG: Parsing PREFIX : <http://rdf.myprefix.com/>
PREFIX ns: <http://rdf.myprefix.com/ns/>
PREFIX xxx: <http://rdf.myprefix.com/xxx/>
SELECT ?x ?z 
 WHERE 	 {?x :myrel ?y. ?y ns:myrel ?z. ?y xxx:rel2 <http://abc.de>}
Mon Nov 18 19:37:17.502	- DEBUG: Got 1 subplans to create.
Mon Nov 18 19:37:17.503	- DEBUG: Done creating execution plan.
/home/nschnelle/projects/QLever/test/QueryPlannerTest.cpp:682: Failure
      Expected: "{\n  JOIN\n  {\n    JOIN\n    {\n      SCAN POS with P = \"" "<http://rdf.myprefix.com/myrel>\"\n      qet-width: 2 \n " "   } join-column: [0]\n    |X|\n    {\n      SCAN PSO wit" "h P = \"<http://rdf.myprefix.com/ns/myrel>\"\n      qet-" "width: 2 \n    } join-column: [0]\n    qet-width: 3 \n  " "} join-column: [0]\n  |X|\n  {\n    SCAN POS with P = " "\"<http://rdf.myprefix.com/xxx/rel2>\", O = \"<http://a" "bc.de>\"\n    qet-width: 1 \n  } join-column: [0]\n  qet" "-width: 3 \n}"
      Which is: "{\n  JOIN\n  {\n    JOIN\n    {\n      SCAN POS with P = \"<http://rdf.myprefix.com/myrel>\"\n      qet-width: 2 \n    } join-column: [0]\n    |X|\n    {\n      SCAN PSO with P = \"<http://rdf.myprefix.com/ns/myrel>\"\n      qet-width: 2 \n    } join-column: [0]\n    qet-width: 3 \n  } join-column: [0]\n  |X|\n  {\n    SCAN POS with P = \"<http://rdf.myprefix.com/xxx/rel2>\", O = \"<http://abc.de>\"\n    qet-width: 1 \n  } join-column: [0]\n  qet-width: 3 \n}"
To be equal to: qet.asString()
      Which is: "{\n  JOIN\n  {\n    JOIN\n    {\n      SCAN POS with P = \"<http://rdf.myprefix.com/myrel>\"\n      qet-width: 2 \n    } join-column: [0]\n    |X|\n    {\n      SCAN POS with P = \"<http://rdf.myprefix.com/xxx/rel2>\", O = \"<http://abc.de>\"\n      qet-width: 1 \n    } join-column: [0]\n    qet-width: 2 \n  } join-column: [0]\n  |X|\n  {\n    SCAN PSO with P = \"<http://rdf.myprefix.com/ns/myrel>\"\n    qet-width: 2 \n  } join-column: [0]\n  qet-width: 3 \n}"
With diff:
@@ -9,13 +9,13 @@
     |X|
     {
-      SCAN PSO with P = \"<http://rdf.myprefix.com/ns/myrel>\"
-      qet-width: 2 
+      SCAN POS with P = \"<http://rdf.myprefix.com/xxx/rel2>\", O = \"<http://abc.de>\"
+      qet-width: 1 
     } join-column: [0]
-    qet-width: 3 
+    qet-width: 2 
   } join-column: [0]
   |X|
   {
-    SCAN POS with P = \"<http://rdf.myprefix.com/xxx/rel2>\", O = \"<http://abc.de>\"
-    qet-width: 1 
+    SCAN PSO with P = \"<http://rdf.myprefix.com/ns/myrel>\"
+    qet-width: 2 
   } join-column: [0]
   qet-width: 3 

[  FAILED  ] QueryPlannerTest.testStarTwoFree (5 ms)
…
[ RUN      ] QueryPlannerTest.threeVarTriples
Mon Nov 18 19:37:17.506	- DEBUG: Parsing SELECT ?x ?p ?o WHERE {<s> <p> ?x . ?x ?p ?o }
Mon Nov 18 19:37:17.507	- DEBUG: Got 1 subplans to create.
Mon Nov 18 19:37:17.507	- DEBUG: Done creating execution plan.
/home/nschnelle/projects/QLever/test/QueryPlannerTest.cpp:763: Failure
      Expected: "{\n  JOIN\n  {\n    SCAN FOR FULL INDEX SPO (DUMMY OPERATION)\n   " " qet-width: 3 \n  } join-column: [0]\n  |X|\n  {\n    SCAN" " PSO with P = \"<p>\", S = \"<s>\"\n    qet-width: 1 \n  }" " join-column: [0]\n  qet-width: 3 \n}"
      Which is: "{\n  JOIN\n  {\n    SCAN FOR FULL INDEX SPO (DUMMY OPERATION)\n    qet-width: 3 \n  } join-column: [0]\n  |X|\n  {\n    SCAN PSO with P = \"<p>\", S = \"<s>\"\n    qet-width: 1 \n  } join-column: [0]\n  qet-width: 3 \n}"
To be equal to: qet.asString()
      Which is: "{\n  JOIN\n  {\n    SCAN FOR FULL INDEX SOP (DUMMY OPERATION)\n    qet-width: 3 \n  } join-column: [0]\n  |X|\n  {\n    SCAN PSO with P = \"<p>\", S = \"<s>\"\n    qet-width: 1 \n  } join-column: [0]\n  qet-width: 3 \n}"
With diff:
@@ -2,5 +2,5 @@
   JOIN
   {
-    SCAN FOR FULL INDEX SPO (DUMMY OPERATION)
+    SCAN FOR FULL INDEX SOP (DUMMY OPERATION)
     qet-width: 3 
   } join-column: [0]

[  FAILED  ] QueryPlannerTest.threeVarTriples (1 ms)
…
[ RUN      ] QueryPlannerTest.threeVarTriplesTCJ
Mon Nov 18 19:37:17.507	- DEBUG: Parsing SELECT ?x ?p ?o WHERE {<s> ?p ?x . ?x ?p ?o }
Mon Nov 18 19:37:17.508	- DEBUG: Got 1 subplans to create.
Mon Nov 18 19:37:17.511	- DEBUG: Done creating execution plan.
/home/nschnelle/projects/QLever/test/QueryPlannerTest.cpp:828: Failure
      Expected: "{\n  TWO_COLUMN_JOIN\n    {\n    " "SCAN FOR FULL INDEX SPO (DUMMY OPERATION)\n    qet-width: 3 \n  }" "\n  join-columns: [0 & 1]\n  |X|\n    {\n    SCAN SOP with S =" " \"<s>\"\n    qet-width: 2 \n  }\n  join-columns: [0 & 1]\n " " qet-width: 3 \n}"
      Which is: "{\n  TWO_COLUMN_JOIN\n    {\n    SCAN FOR FULL INDEX SPO (DUMMY OPERATION)\n    qet-width: 3 \n  }\n  join-columns: [0 & 1]\n  |X|\n    {\n    SCAN SOP with S = \"<s>\"\n    qet-width: 2 \n  }\n  join-columns: [0 & 1]\n  qet-width: 3 \n}"
To be equal to: qet.asString()
      Which is: "{\n  TWO_COLUMN_JOIN\n    {\n    SCAN FOR FULL INDEX POS (DUMMY OPERATION)\n    qet-width: 3 \n  }\n  join-columns: [0 & 2]\n  |X|\n    {\n    SCAN SPO with S = \"<s>\"\n    qet-width: 2 \n  }\n  join-columns: [0 & 1]\n  qet-width: 3 \n}"
With diff:
@@ -2,11 +2,11 @@
   TWO_COLUMN_JOIN
     {
-    SCAN FOR FULL INDEX SPO (DUMMY OPERATION)
+    SCAN FOR FULL INDEX POS (DUMMY OPERATION)
     qet-width: 3 
   }
-  join-columns: [0 & 1]
+  join-columns: [0 & 2]
   |X|
     {
-    SCAN SOP with S = \"<s>\"
+    SCAN SPO with S = \"<s>\"
     qet-width: 2 
   }

[  FAILED  ] QueryPlannerTest.threeVarTriplesTCJ (5 ms)

[joka921]

I recently watched I talk by a google HashMap implementer. They randomize everything in their implementations so that no one ever relies on observable but unspecified behavior.

IMHO the correct way to test the query planner would be:

• Test that the cost estimate works correctly.
• Test that the cost estimate of the returned Execution Tree is <= the manually specified minimum.

Alternatively one would have to define test cases where the optimum is unique, but I strongly prefer the way stated above.