OPTIONAL leads to no results

[niklas88]

The following query generated by Aqqu for the "start of Hoover's (fb:m.03kdl) presidency" yields no results.

PREFIX fb: <http://rdf.freebase.com/ns/>

SELECT  ?1 ?1name WHERE {
 fb:m.060d2 fb:government.government_office_or_title.office_holders ?0 .
 ?0 fb:government.government_position_held.office_holder fb:m.03kdl .
 ?0 fb:government.government_position_held.from ?1 .
 OPTIONAL {?1 fb:type.object.name ?1name} .
 FILTER (?1 != fb:m.060d2 && ?1 != fb:m.03kdl) 
} LIMIT 300

Removing the OPTIONAL line however reveals there should be a result.

It doesn't seem to be related to ?1 not having that relation at all however as removing

fb:m.060d2 fb:government.government_office_or_title.office_holders ?0 .

which restricts to the "President of the United States" also yields the result.

This is the QLever log: qlever_log_optional_sort.txt
my guess would be that the SORT operation is not propagating the _isOptional flag correctly. I'll investigate later.

[niklas88]

So here is what I could gather so far. It doesn't seem to be the SORT as the following working query

PREFIX fb: <http://rdf.freebase.com/ns/>

SELECT ?1  ?1name WHERE {
 ?0 fb:government.government_position_held.office_holder fb:m.03kdl .
 ?0 fb:government.government_position_held.from ?1 .
 OPTIONAL {?1 fb:type.object.name ?1name} .
}
LIMIT 300
ORDER BY ?0

gives the exact execution plan of the right side of the following queries' outer most JOIN (the same as the first query just withput FILTER)

PREFIX fb: <http://rdf.freebase.com/ns/>

SELECT ?1  ?1name WHERE {
 fb:m.060d2 fb:government.government_office_or_title.office_holders ?0 .
 ?0 fb:government.government_position_held.office_holder fb:m.03kdl .
 ?0 fb:government.government_position_held.from ?1 .
 OPTIONAL {?1 fb:type.object.name ?1name} .
}
LIMIT 300

qlever_log_optional_sort_2.txt

So to me it looks like JOIN on results of OPTIONAL_JOIN is broken. We really need some e2e Test queries with OPTIONAL (i.e. #68)

[niklas88]

Ok so the problem is that the result of the OPTIONAL_JOIN estimates it's size as 0 because somehow we know that the OPTIONAL part is indeed empty. Then this function literally takes the size estimate at face value

bool QueryExecutionTree::knownEmptyResult() { return getSizeEstimate() == 0; }

and the JOIN takes it as known empty.

So @floriankramer @Buchhold we should either document that the size estimate may only be 0 iff it is exactly known. Or we need to change the test for knownEmptyResult().