{"action":"opened","issue":{"url":"https://api.github.com/repos/dotnetrdf/dotnetrdf/issues/8","repository_url":"https://api.github.com/repos/dotnetrdf/dotnetrdf","labels_url":"https://api.github.com/repos/dotnetrdf/dotnetrdf/issues/8/labels{/name}","comments_url":"https://api.github.com/repos/dotnetrdf/dotnetrdf/issues/8/comments","events_url":"https://api.github.com/repos/dotnetrdf/dotnetrdf/issues/8/events","html_url":"https://github.com/dotnetrdf/dotnetrdf/issues/8","id":153602797,"number":8,"title":"Cross Products/Large Joins cause extremely long run times","user":{"login":"kal","id":70985,"avatar_url":"https://avatars.githubusercontent.com/u/70985?v=3","gravatar_id":"","url":"https://api.github.com/users/kal","html_url":"https://github.com/kal","followers_url":"https://api.github.com/users/kal/followers","following_url":"https://api.github.com/users/kal/following{/other_user}","gists_url":"https://api.github.com/users/kal/gists{/gist_id}","starred_url":"https://api.github.com/users/kal/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kal/subscriptions","organizations_url":"https://api.github.com/users/kal/orgs","repos_url":"https://api.github.com/users/kal/repos","events_url":"https://api.github.com/users/kal/events{/privacy}","received_events_url":"https://api.github.com/users/kal/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/dotnetrdf/dotnetrdf/labels/enhancement","name":"enhancement","color":"84b6eb"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-05-07T16:19:53Z","updated_at":"2016-05-07T16:19:53Z","closed_at":null,"body":"*Imported from http://www.dotnetrdf.org/tracker/Issues/IssueDetail.aspx?id=457*\r\n\r\nWe're experiencing serious performance issues with leviathan in-memory SPARQL processor. For relatively simple queries the processor takes minutes to process or completely times out.\r\nThe only version that actually can run the example queries below is 1.0.3. Newer versions timeouts after 3 minutes. Test store (schema.org NQuads dump, around 10000 triples in two named graphs) attached.\r\nIn general, we've noticed that working with graphs and having EXISTS or OPTIONAL statements completely breaks the processor.\r\nExample queries:\r\n\r\n    SELECT ?s ?p ?o ?G ?entity ?entity\r\n    WHERE {\r\n     GRAPH ?G {\r\n      ?s ?p ?o .\r\n      OPTIONAL { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2000/01/rdf-schema#Class> . }\r\n     }\r\n    }\r\n    SELECT ?s ?p ?o ?G ?entity ?entity\r\n    WHERE {\r\n     GRAPH <meta://graph/> { ?G <http://xmlns.com/foaf/0.1/primaryTopic> ?entity . }\r\n     GRAPH ?G {\r\n      ?s ?p ?o .\r\n      FILTER (\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2000/01/rdf-schema#Class> . } ||\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2002/07/owl#Class> . } ||\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2002/07/owl#Restriction> . }\r\n      )\r\n     }\r\n    }\r\n\r\n---\r\nRob Vesse (Tuesday, October 13, 2015 9:45 AM)\r\n\r\nBoth these queries look strange since the two graph patterns have no common variables so in both cases you are asking the engine to compute cross products of some form which can be very expensive even at very small scales.\r\n\r\nIn the OPTIONAL query the required pattern is not connected to the OPTIONAL pattern and the same is true of the EXISTS query since the ?entity in the FILTER is in a different scope to the ?entity in the first GRAPH clause.  So first I would look at whether you are actually expressing the query you mean to.\r\n\r\n1.0.3 performed a faster but incorrect query evaluation (in both these cases) which has since been bug fixed to do a slower but correct evaluation.  I'm not sure if the engine can be tuned to deal with these queries faster \r\n\r\n---\r\n\r\nRob Vesse (Tuesday, October 13, 2015 3:17 PM)\r\n\r\nConfirmed that the problem is actually the queries.  If I modify the queries to avoid the cross product then both queries complete almost immediatedly.\r\n\r\nWith the cross product the query is never going to be solvable in a reasonable time frame.  For example for the OPTIONAL you have 8727 solutions from the ?s ?p ?o multiplied by 548 solutions from the OPTIONAL which means 4782396 total solutions i.e. ~4.7 million solutions to generate.  With the cross product removed you get just a few thousand results which I suspect is what you actually want.\r\n\r\n---\r\n\r\nKarol Szczepański (Monday, October 26, 2015 8:14 AM)\r\n\r\nHi Rob\r\n \r\nThank you for your comment. I'm somehow stunned that we're talking about cross products. In the second query (which actually is the one that I need to work) only variables ?G and ?entity are bound in the query and ?s ?p ?o is only used in the resultset of all graphs matching the query.\r\n\r\nI made a quick test with Virtuoso community and same query on same dataset and the whole HTTP roundtrip is below 0.5s. I'm somehow unfrair by comparing a few man's great job with an enterprise solution, but still I expect tha in-memory store to return a result at last a level of magnitude worse.\r\n\r\nMy understaning of the second query is: give me contents of all graphs ?G that contains any of the statements in the Filter clause and are mentioned in another graph meta://graph.\r\n\r\nAs for temporary solutions - this query is a result of an automatic LINQ to SPARQL transformation of a library called RomanticWeb which me and Tomasz Pluskiewicz commited some time ago (see https://github.com/MakoLab/RomanticWeb). If there is any way we could modify the transformation so it runs smoothly I'm interested on some hints on how to do this. We're trying to have a single SPARQL query per LINQ expression. Separate queries for meta://graph and actual data is a last resort soltion.\r\n\r\n---\r\n\r\nRob Vesse (Wednesday, November 04, 2015 10:11 PM)\r\n\r\nDid some more digging and understand more what is happening now.  So there isn't a cross product per-se but there is a very large join being produced so much the same problem and symptoms.\r\nThe problem is the fact that you first select the graph names from the meta-graph which gives 1259 graph names which all have the same value.  You then select all triples from graphs that match your exist clause (which gives 8727 triples).  We are then joining these on ?G, however every row on both sides of the join has the same value for ?G so we end up having to compute 1259*8727 which is ~10 million solutions so even worse than the OPTIONAL query and again likely not what you meant.  Since you only care about each graph once one possible optimization is to wrap the first query in a SELECT DISTINCT sub-query e.g.\r\n\r\n    SELECT ?s ?p ?o ?G ?entity ?entity\r\n    WHERE {\r\n     { SELECT DISTINCT ?G WHERE { GRAPH <meta://graph/> { ?G <http://xmlns.com/foaf/0.1/primaryTopic> ?entity . } } }\r\n     GRAPH ?G {\r\n      ?s ?p ?o .\r\n      FILTER (\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2000/01/rdf-schema#Class> . } ||\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2002/07/owl#Class> . } ||\r\n       EXISTS { ?entity <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://www.w3.org/2002/07/owl#Restriction> . }\r\n      )\r\n     }\r\n    }\r\n\r\nWhich will run just fine.\r\n\r\nAs for Virtuoso note that the default Virtuoso setup applies a limit on the number of results returned from a SPARQL query (of ~10,000 if memory serves) and they are likely lazily evaluating the query so they only produce the first 10,000 results hence why they are so fast.  If you were to remove that limit then I suspect the query would take a long time on Virtuoso as well.\r\n\r\nIf you want a reference SPARQL implementation to test dotNetRDF against I would recommend that you download Apache Jena Fuseki and use that as a test-bed\r\n\r\n---\r\n\r\nKarol Szczepański (Tuesday, February 09, 2016 8:23 PM) \r\n\r\nHi Rob\r\n \r\nFinally I had time to experiment a bit with your optimization (lot of things happened on my side). =\r\n\r\nAnyway, it seems that the way you changed the query makes it return a different set of rows. The graph variable in DISTINCT clause seems to be not enough as the result contains triples not matching the criteria (the filter to be specific - this applies to another set of triples I'm using for experiments where there are many graphs with resources).\r\n\r\nIt looks like the ?entity variable is not bound to the ?Gentity variable from the meta graph. It can be corrected by adding the ?entity variable to the DISTINCT clause with the ?Gentity variable altogether, but in result it ends up with same number of rows as in the beginning.\r\nI'll try to play with the query, but seems that the issue is still there."}}