Feat subquery

[floriankramer]

This pr adds support for subqueries. The handling of subqueries in the optimizer is currently very simplistic, as they are simply optimized separately, and the resulting QueryExecutionTree then added to the parents optimization. A simple improvement would be to compute the result of a separately optimized query part before optimizing the parent query to get correct size and multiplicity of the result (the same way scans are currently handled). As that is a change not only related to subqueries I wanted to create a separate pr for it.

[niklas88]

LGTM with some clarification questions mainly because I'm not too familiar with C++ class instances in union. I've only ever used union in pure C.

Also congrats you really did get this done fast, color me truly impressed.

[niklas88]

I guess there is nothing in scientists which would allow to test this with ql:has-predicate? I'm currently looking into creating a smallish Wikidata subset which should allow us to create much better test queries.

[floriankramer]

I used bash (for p in $(cat ./scientists.nt | cut -d' ' -f 2 | sort | uniq); do cat ./scientists.nt | cut -d' ' -f 1 | uniq | grep $p; done) to check for predicates that occur as subjects int the scientists nt file, but didn't find any.

[niklas88]

Do you really need placement new to initialize an object in a union can't one just call the constructor explicitly?

[floriankramer]

The problem is, that only the vector or the subquery may be initialized due to the union. As far as I know, any form of calling the constructor explicitly includes then using the assignment operator, which would then operate on uninitialized memory (as _childGraphPattern does not get default constructed in the union). I haven't done anything like this before though, so I'm happy for feedback on how to handle this in a better way.

[niklas88]

Looking at the second example here the std::string in the union is constructed using operator=() wand the std::vector<int> is constructed with placement new just as in your code. So maybe both works and operator=() doesn't care if the memory is uninitialized but maybe that's only true for std::string? Looking at that code we may also need to add explicit destructor calls for the std::vector<GraphPattern*> though.

[niklas88]

Looks like S s = "str"; only works because it also constructs. The following fails:

#include <iostream>
#include <string>
#include <vector>
 
union S
{
    std::string str;
    std::vector<int> vec;
};

int main()
{
    S s;
    s.str = {"Hello, world"};
    // at this point, reading from s.vec is undefined behavior
    std::cout << "s.str = " << s.str << '\n';
    s.str.~basic_string();
    new (&s.vec) std::vector<int>;
    // now, s.vec is the active member of the union
    s.vec.push_back(10);
    std::cout << s.vec.size() << '\n';
    s.vec.~vector();
}

[floriankramer]

I added the missing destructor calls for the vector

[niklas88]

@floriankramer great. I think it's ready to merge