Force join order

[D063520]

Hi, given a SPARQL query like this:

select ?pub where{
?cancer_type wdt:P279* wd:Q12078 .
?pub wdt:P921 ?cancer_type.
?pub wdt:P31 ?class.
?class wdt:P279* wd:Q591041 .
}

is there a way to force the triple pattern join order. Basically I would like to force him to the one that is given but he chooses:

Projection
╠══ProjectionElemList
║     ProjectionElem "pub"
╚══Join (JoinIterator)
   ├──ArbitraryLengthPath (costEstimate=14.0K, resultSizeEstimate=28.0K)
   │     Var (name=cancer_type)
   │     StatementPattern (resultSizeEstimate=22)
   │        Var (name=cancer_type)
   │        Var (name=_const_d85f4df4_uri, value=http://www.wikidata.org/prop/direct/P279, anonymous)
   │        Var (name=_const_24c6ef15_uri, value=http://www.wikidata.org/entity/Q12078, anonymous)
   │     Var (name=_const_24c6ef15_uri, value=http://www.wikidata.org/entity/Q12078, anonymous)
   └──Join (JoinIterator)
      ╠══StatementPattern (costEstimate=1.4K, resultSizeEstimate=7.9M)
      ║     Var (name=pub)
      ║     Var (name=_const_d85f6798_uri, value=http://www.wikidata.org/prop/direct/P921, anonymous)
      ║     Var (name=cancer_type)
      ╚══Join (JoinIterator)
         ├──StatementPattern (costEstimate=12.8K, resultSizeEstimate=651.4M)
         │     Var (name=pub)
         │     Var (name=_const_e5f28efe_uri, value=http://www.wikidata.org/prop/direct/P31, anonymous)
         │     Var (name=class)
         └──ArbitraryLengthPath (costEstimate=1, resultSizeEstimate=44.3M)
               Var (name=class)
               StatementPattern (resultSizeEstimate=11)
                  Var (name=class)
                  Var (name=_const_d85f4df4_uri, value=http://www.wikidata.org/prop/direct/P279, anonymous)
                  Var (name=_const_7b4d545b_uri, value=http://www.wikidata.org/entity/Q591041, anonymous)
               Var (name=_const_7b4d545b_uri, value=http://www.wikidata.org/entity/Q591041, anonymous)

Which I guess is far from ideal ..... because:

and

and even:

[hmottestad]

Unfortunately not.

Could you run the query with explanation level Executed? That way we can see how the query actually performs. https://rdf4j.org/documentation/programming/repository/#explaining-queries

If the query is sub-optimal we could look into possible rewrites to attempt to force the query optimizer to choose a better approach, or possibly consider it a bug in the query optimizer that should be fixed.

[D063520]

Not super familiar with this .... what is the difference between left and right?

[pulquero]

Currently, JoinIteration evaluates its left argument first, and then for each left bindingset, evaluate the right argument. To my mind, the right recursive join structure created by the queryoptimiser would favour the opposite evaluation order.

[D063520]

Ah, i think I understand. But then choosing between left and right would depend on the index structure, i.e. which one the index is quicker to resolve. Not sure what the current native rdf4j index prefers ....

[hmottestad]

I think by "right recursive" it means that the nested join should be placed in the right argument.

[hmottestad]

The query is optimized based on statistics provided by the store. The Native Store accounts for the different indexes when calculating the statistics. During evaluation it might be more beneficial to use a different index because more variables are bound, this is accounted for by the Native Store.

[D063520]

Hi,

thank you for this! In fact the query is running over whole Wikidata, so we do not use rdf4j as a backend, but only rdf4j as a query planner and preparer. If it is not possible we can somehow hack our planner to not do anything. Would be a nice and useful feature though ; ), no?

Salut
Dennis

[hmottestad]

How exactly do you store your data?

[D063520]

We are storing it in HDT ....

[hmottestad]

How do you expose statistics from your HDT files to the query planner?