Feat optional #43

floriankramer · 2018-03-07T10:51:59Z

Added support for OPTIONAL query parts. Fixes #22
I changed the query parsing to be able to recursively parse optional parts, storing them in a new GraphPattern struct. The QueryPlanner then adds optional parts to the optimiations dp table during the seeding phase. There is a new OptionalJoin Operation, that joins two ResultTables on any number of columns, adding new ID_NO_VALUE constants to represent fields empty due to optional sides.

niklas88 · 2018-03-13T11:27:44Z

Will start reviewing now, in the meantime can you rebase against master? This should pull in the .travis.yml and give us CI testing of these changes. I propose to do the rebase as follows:

git fetch upstream/master
git checkout feat_optional
git rebase upstream/master
git push --force

Note that for rebasing --force is both needed and ok.

…optional blocks

…ariable columns

…er by for simple queries

niklas88

Thank you for this work, I'm really impressed how fast you got a grasp of the code base. I don't really have the expertise to review this adequately to be honest. So added only some nitpicking comments.

Do I see this right, that we don't have any end-to-end tests that actually parse⇒plan⇒execute some queries? Maybe we could add those as an external script using SparqlEngineMain. I found some query lists that look like an attempt of this in misc/ but some look like they still use an older text search syntax so they are definitely not run

niklas88 · 2018-03-13T17:45:27Z

src/SparqlEngineMain.cpp

@@ -88,20 +123,34 @@ int main(int argc, char** argv) {
      case 'a':
        allPermutations = true;
        break;
+      case 'h':
+        printUsage(argv[0]);


Thanks for cleaning this up!

niklas88 · 2018-03-13T17:47:55Z

src/ServerMain.cpp

+      cerr << "ERROR: No index specified, but an index is required." << endl;
+    }
+    if (port == -1) {
+      cerr << "ERROR: No port specified, but the port is required." << endl;


niklas88 · 2018-03-13T17:54:41Z

src/parser/ParsedQuery.cpp

+  os << "{\n";
+  for (size_t i = 0; i < _whereClauseTriples.size(); ++i) {
+    os << "\n\t" << _whereClauseTriples[i].asString();
+    if (i + 1 < _whereClauseTriples.size()) { os << ','; }


If you don't like the if in the loop I personally prefer the following pattern.

for (size_t i = 0; i < vec.size() - 1; i++) { out << vec[i] << ", "; } out << vec.back();

I switched to your definitely nicer style in the latest commit, and added some proper indentation to the output.

niklas88 · 2018-03-13T17:56:41Z

src/parser/SparqlParser.cpp

@@ -121,7 +125,46 @@ void SparqlParser::parseWhere(const string& str, ParsedQuery& query) {
  while (start < inner.size()) {
    size_t k = start;
    while (inner[k] == ' ' || inner[k] == '\t' || inner[k] == '\n') { ++k; }
-    if (inner[k] == 'F') {
+    if (inner[k] == 'O' || inner[k] == 'o') {
+      if (inner.substr(k, 8) == "OPTIONAL"


Are we case insensitve or only all-upper or all-lower? Would maybe prefer a toLower() and then check

Currently only all upper and all lower case are supported. The standard says most keywords are case insensitive (apart from the keyword 'a' which may only be lower case). It may be cleaner to change that in another pull request /. commit though.

niklas88 · 2018-03-13T18:00:14Z

src/engine/Engine.h

+      jcls_a |= (1 << jc[0]);
+      jcls_b |= (1 << jc[1]);
+    }
+    // avoid compiler warnings


which warning exactly and how?

niklas88 · 2018-03-13T18:15:39Z

src/engine/Engine.h

+  template<typename A, typename B, typename R, int K>
+  static void optionalJoin(const A& a, const B& b,
+                           bool aOptional, bool bOptional,
+                           const vector<array<size_t, 2>>& jcls,


can you provide more desriptive names here? I have no idea what jcls stands for

I replaced all mentions of jcl and jcls with joinColumn and joinColumns respectively.

niklas88 · 2018-03-13T18:16:45Z

src/engine/Engine.h

+      for (size_t ib = 0; ib < b.size(); ib++) {
+        R res = newOptionalResult<R, K>()(resultSize);
+        createOptionalResult<A, B, R, true, false>(
+              static_cast<typename A::value_type*>(0), &b[ib],


nullptr should work without a cast, right?

I originally relied on the compiler deducing the template arguments, thats why I had to cast the nullptrs to be pointers of the right type. Replaced them with actual nullptrs now.

niklas88 · 2018-03-13T18:19:32Z

src/SparqlEngineMain.cpp

@@ -60,11 +94,12 @@ int main(int argc, char** argv) {
  bool interactive = false;
  bool onDiskLiterals = false;
  bool allPermutations = false;
+  bool optimizeOptionals = true;


Hannah said this currently slows down queries? I assume this only happens if there is an OPTIONAL? Is this the right default at the moment?

The slowdown happens due to the query optimizer effectively having to optimize a query with another triple, representing the optional part. For queries with many triples (around 9 or more) the slowdown starts becoming noticeable. For queries with fewer triples the change in speed is minmal, and using the optimizer can of course lead to significantly faster execution time. If the default use case includes queries which, on average, have many triples changing the setting to false by default would be better.

You are right, this case is actually more non-trivial than I thought.

niklas88 · 2018-03-13T18:23:46Z

src/engine/Engine.h

+    }
+
+    // add sentinels
+    A& l1 = const_cast<A&>(a);


The comment should explain why it's ok to cast away the const here

niklas88 · 2018-03-13T18:26:51Z

src/engine/OptionalJoin.cpp

+  return os.str();
+}
+
+// Used to generate all up to 125 combinations of left, right and result size.


If we allowed C++14/17 constexpr with loops this could be done much nicer, right? If yes, then we probably should.

I think you are right. I'll have to look into that later today or tomorrow.

I did a bit of googling for the uses of constexpr in c++ 14 and 17, as I've never used it extensively before.
As far as I could find out, there is no way, apart from the same recursion that is implemented with the templates right now, to create a constexpr loop. As the problem with finding the right template parameters is, that we need to transform a runtime value with a limited number of values into a compile time constant, I didn't find a nicer solution using constexpr, as any assignment of a constexpr would depend on a runtime value.
Was there a specific trick you were thinking of, or is there a feature of constexpr I didn't find, that would help with these problems?

niklas88 · 2018-03-14T17:34:30Z

src/engine/Engine.h

@@ -389,25 +389,25 @@ class Engine {
  static void createOptionalResult(const typename A::value_type* a,
                                   const typename B::value_type* b,
                                   size_t sizeA,
-                                   int jcls_a, int jcls_b,
-                                   const std::vector<size_t>& jclAToB,
+                                   int joinColumBitmap_a, int joinColumBitmap_b,


It's "column" so use either "..Col" or "..Column"

floriankramer added 21 commits March 13, 2018 15:57

Added tree structure to ParsedQueries to allow for representation of …

28c6dc6

…optional blocks

added basic OptionalJoin

79ff462

First partially working optional implementation

7db469a

Added proper cross product computation to the optional join.

d10fdb9

Fixed handling of cases where one table is empty, added handling of v…

467c2ee

…ariable columns

fixed wrong template arguments for test and reactivated optimized ord…

461f68b

…er by for simple queries

fixed corner case and added more optional join tests

661c95a

added basic support for blank nodes in nt files

6112fda

fixed several bugs and cleaned up code

8ba257e

removed debugging code

8ce01a9

improved size and multiplicity estimation

c7f7d8c

Implemented basic usage of the optimizer for optional queries

f184662

Fixed reference style

7e24a9f

added basic cost estimation

8cfdc13

Fixed several bugs and changed multiplicity computation

932c5ff

Added sentinels to the optional join

3db0667

Made bools for empty sides template parameters for createOptionalResult

25d68c5

Fixed bug ignoring first join column, added more output

6eda370

resolved todos

4165b78

Added flag to disable optional optimization and readded comments

625d827

Added unoptimized optionals option to SparqlEngineMain

39e2425

floriankramer force-pushed the feat_optional branch from 2b29478 to 39e2425 Compare March 13, 2018 15:08

niklas88 approved these changes Mar 13, 2018

View reviewed changes

Code cleanup

17fd126

niklas88 reviewed Mar 14, 2018

View reviewed changes

fixed typos

b5610f0

niklas88 merged commit 124ae54 into ad-freiburg:master Mar 15, 2018

floriankramer deleted the feat_optional branch March 15, 2018 13:24

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Feat optional #43

Feat optional #43

floriankramer commented Mar 7, 2018

niklas88 commented Mar 13, 2018

niklas88 left a comment

niklas88 Mar 13, 2018

niklas88 Mar 13, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

niklas88 Mar 13, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

niklas88 Mar 15, 2018

niklas88 Mar 13, 2018

niklas88 Mar 13, 2018

floriankramer Mar 14, 2018

floriankramer Mar 15, 2018

niklas88 Mar 14, 2018

floriankramer Mar 15, 2018

Feat optional #43

Feat optional #43

Conversation

floriankramer commented Mar 7, 2018

niklas88 commented Mar 13, 2018

niklas88 left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment