Question about query planning

[D063520]

Hi,

I'm really impressed by the computation speed of this query over Wikidata:

PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX wd: <http://www.wikidata.org/entity/>
PREFIX wdt: <http://www.wikidata.org/prop/direct/>
SELECT ?person_id ?person (COUNT(?profession_id) AS ?count) (GROUP_CONCAT(?profession; separator=", ") AS ?professions) WHERE {
  ?person_id wdt:P31 wd:Q5 .
  ?person_id wdt:P106 ?profession_id .
  ?profession_id rdfs:label ?profession .
  ?person_id rdfs:label ?person .
  FILTER (LANG(?person) = "en") .
  FILTER (LANG(?profession) = "en")
}
GROUP BY ?person_id ?person
ORDER BY DESC(?count)

I would like to know a bit more of the internals to understand how you are able to compute it so quickly. My question can be formulated as: "What is the query plan of this query?" I would compute the joints in the where clause (giving huge intermediate results) and then execute the group by query. But this would not scale, or? How do you do it?!? : )

[hannahbast]

For the protocol, here is a link to the query on the QLever public endpoint: https://qlever.cs.uni-freiburg.de/wikidata/sggFqw

If you execute the query and then click on the "Analysis" button (below the field with the query), you see a pretty self-explanatory depiction of the query plan.

The QLever Wiki (work in progress) contains more information about the basic principles of QLever: https://github.com/ad-freiburg/qlever/wiki

[D063520]

Hi, thank you. Are the joins "merge joins" or "nested joins"?

[joka921]

Hi, QLever currently supports merge joins and galloping joins (for the case where one input is much larger than the other).
This means that the inputs to the join always has to be sorted on the input, so you often see tthat the children of a join operation are sort operations. We are planning to implement additional join algorithms that don't require at least the larger input to be sorted when the inputs have different sizes.

[D063520]

thank you!