Slow property path query for disjunctive form

[rubensworks]

Issue type:

• 🐌 Performance issue

---

Description:

This property path query is very slow:
http://query.linkeddatafragments.org/#transientDatasources=http%3A%2F%2Ffragments.dbpedia.org%2F2016-04%2Fen&query=SELECT%20%3Fperson%0AWHERE%20%7B%0A%20%20%5B%20rdfs%3Alabel%20%22Bruce%20Willis%22%40en%20%5D%0A%20%20%20%20(dbpedia-owl%3Aspouse%7Cdbpedia-owl%3Achild)%20%5B%20rdfs%3Alabel%20%3Fperson%20%5D.%0A%7D

Related to #709.

---

Environment:

Comunica version: 1.16.2

[rubensworks]

Just looked into this some more, and it's not a problem after all.
The identification of file source is intended after the first page.
The issue is simply performance due to a sub-optimal query plan.
So I'm changing the scope of this issue.

[github-actions]

Thanks for reporting!

[github-actions]

Thanks for reporting!

[github-actions]

Thanks for reporting!

[sroze]

The issue is simply performance due to a sub-optimal query plan.

@rubensworks I'm currently exploring using Comunica and I have sub-optimal query plans and can't find any documentation about anything that would enable me to tell Cumunica specific costs, is that even a thing? If yes/no, how would you advise I explore having more optimal plans?

To be more specific, I have the following query:

SELECT ?foo WHERE {
  ?foo edge:one ?something.
  ?identity edge:two ?something.
}

?identity is a bound variable. I'm expecting the following matches:

• <identity-value> edge:two {null}
• {null} edge:one {values-from-above}

However, I get the following first match instead:

• {null} edge:two {null}.

Given the cardinality is very high, it results in very slow queries.

[rubensworks]

@sroze Your issues sounds more related to #548.

Comunica internally has a cost-based plan optimizer using the totalItems cardinality estimate metadata.
This can not be influenced by end-users though.
So this issue essentially requires the implementation of one or more actors to more intelligently plan the query.

Currently, BGPs are always handled by this actor: https://github.com/comunica/comunica/tree/master/packages/actor-query-operation-bgp-left-deep-smallest

[sroze]

@rubensworks thank you for your answer; I've managed to make it work well with cost metadata for the above query 🎉

However, I end up with the same problem with the following query:

SELECT ?foo WHERE {
  ?foo edge:one ?something.
  ?identity edge:two | edge:three ?something.
}

Am I right thinking that this is because the join operation (between the 1st bgp and 2nd path) does not take cost into account? If so, is it a matter of implementing another join strategy like described in #552?

[rubensworks]

I've managed to make it work well with cost metadata for the above query 🎉

Nice, how did you end up doing it?

Am I right thinking that this is because the join operation (between the 1st bgp and 2nd path) does not take cost into account? If so, is it a matter of implementing another join strategy like described in #552?

Indeed, that join will likely be sub-optimal. #552 will indeed be required to optimize that (many good techniques exist already, so it's just a matter of implementing them here).

[sroze]

Nice, how did you end up doing it?

I'm using a RDF/JS store so I had to implement the countQuads method on it (to return rough estimates, given I know the shape of my data) and it did the trick (as well as never starting to produce the stream until it's actually being read).

many good techniques exist already, so it's just a matter of implementing them here

Do you have anything to point me towards? I'd be very keen to work on such an implementation. In terms of concrete steps, shall I be looking at replacing ActorQueryOperationJoin with another implementation?

[rubensworks]

I'm using a RDF/JS store so I had to implement the countQuads method on it (to return rough estimates, given I know the shape of my data) and it did the trick (as well as never starting to produce the stream until it's actually being read).

Great, that's a good way to do it indeed.

Do you have anything to point me towards? I'd be very keen to work on such an implementation.

Not sure what your background is, but this may be helpfull to get started in the domain of query optimization: https://www.rubensworks.net/raw/slides/2021/ugent-webfundamentals-sparqlengines/

I think a good first step would be create a new BGP actor that is able to work using different join algorithms (#427).

Happy to give you further guidance if your willing to take this up! (other communication mediums may be better in that case...)

[sroze]

Happy to give you further guidance if your willing to take this up! (other communication mediums may be better in that case...)

@rubensworks that's wonderful, I reached out to you on Gitter.

[rubensworks]

Will be much faster in Comunica 2.x