Wikidata:service des requêtes SPARQL/optimisation de la requête

< Wikidata:SPARQL query service

This page is a translated version of the page Wikidata:SPARQL query service/query optimization and the translation is 65% complete.

Outdated translations are marked like this.

L'optimisation des requêtes tente de trouver la manière optimale d'exécuter une requête donnée parmi les différentes possibilités d'exécution existantes. Blazegraph dispose d'un optimiseur de requêtes intégré qui fonctionne particulièrement bien. Néanmoins quelque fois il n'est pas aussi performant; dans ces situations les requêtes doivent être optimisées manuellement.

Stratégies d'optimisation

Optimisation de la requête (représentation symbolique)

Valeurs fixes et intervalles

La recherche de valeurs fixes, telles que wdt:P31 wd:Q5, est l'option la moins chère du service de requêtes, mais rechercher des intervalles de valeurs est habituellement tout aussi efficace, et souvent préférable aux autres options. Par exemple, pour rechercher les personnes nées en 1978, FILTER(YEAR(?dateOfBirth) = 1978) n'est même pas aussi efficace que :

SELECT ?item ?dateOfBirth WHERE {
  ?item wdt:P31 wd:Q5;
        wdt:P569 ?dateOfBirth.
  FILTER("1978-00-00"^^xsd:dateTime <= ?dateOfBirth &&
         ?dateOfBirth < "1979-00-00"^^xsd:dateTime)
}

Vous pouvez ensuite optimiser ceci en informant le service de requête que wdt:P569 est un prédicat range-safe :

SELECT ?item ?dateOfBirth WHERE {
  ?item wdt:P31 wd:Q5;
        wdt:P569 ?dateOfBirth. hint:Prior hint:rangeSafe true.
  FILTER("1978-00-00"^^xsd:dateTime <= ?dateOfBirth &&
         ?dateOfBirth < "1979-00-00"^^xsd:dateTime)
}

Ceci indique à l'optimiseur que ?dateOfBirth ne mélange pas les dates, les chaînes, les entiers ni les autres types de données, ce qui simplifie la comparaison des intervalles. Ceci est presque toujours vrai sur Wikidata, ainsi la principale raison qui ressort le plus souvent pour de ne pas utiliser cet optimiseur est son côté légèrement peu pratique. l(C'est peut être aussi une idée pas judicieuse de vous en servir lorsque vous travaillez avec des valeurs inconnues.)

Chemins des propriétés

En général, l'optimiseur suppose que le chemin des propriétés sont plus coûteux que les simples contrôles des valeurs, ce qui est d'habitude le cas : essayez donc d'ajouter quelques triplets simples pour réduire l'ensemble de valeurs qui doivent être vérifiées par rapport au nombre de chemins. Néanmoins, quelquefois les chemins peuvent être beaucoup plus efficaces et il est bon d'indiquer cela à l'optimiseur. Par exemple, considérez la requête suivante concernant toutes les villes d'Allemagne se trouvant en Basse Saxe :

SELECT ?item ?itemLabel WHERE {
  ?item wdt:P31/wdt:P279* wd:Q262166;
        wdt:P131+ wd:Q1197.
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

Tel que c'est écrit, cela dépassera le temps maximal d'exécution autorisé car le service de requête essaiera de commencer par tous les instance of (P31)municipality in Germany (Q262166) (y compris les sous-classes) avant de les limiter à located in the administrative territorial entity (P131)Lower Saxony (Q1197) (récursivement). Il est beaucoup plus efficace de contourner cela autrement :

SELECT ?item ?itemLabel WHERE {
  hint:Query hint:optimizer "None".
  ?item wdt:P131+ wd:Q1197;
        wdt:P31/wdt:P279* wd:Q262166.
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

Tracked in Phabricator
Task T168973

Vous pouvez également dire à l'optimiseur dans quelle direction traverser un chemin. Par exemple, dire que vous voulez tester si Moby-Dick (Q174596) est un creative work (Q17537576):

ASK {
  wd:Q174596 wdt:P31/wdt:P279* wd:Q17537576.
}

Ceci prend plusieurs secondes car l'optimiseur décide de commencer par creative work (Q17537576) et cheminer en remontant les liens subclass of (P279). Vous pouvez lui dire d'utiliser le sens inverse, en commençant par Moby-Dick (Q174596), en suivant un lien instance of (P31) puis en avançant sur le lien subclass of (P279) :

ASK {
  wd:Q174596 wdt:P31/wdt:P279* wd:Q17537576.
  hint:Prior hint:gearing "forward".
}

Ceci est beaucoup plus efficace. Pour faire de l'autre manière, utilisez "reverse" au lieu de "forward".

Chemins des propriétés inverses

Une autre technique pour convaincre l’optimiseur à plus d’efficacité est d’inverser le chemin de propriété ; c’est potentiellement particulièrement utile pour gérer des requêtes qui prennent trop de temps pour terminer. Voir les exemples suivants — le premier est hors-limites de temps, et le second est rapide :

# Museums in Northern Ireland - TIMES OUT
SELECT distinct ?museum ?museumLabel WHERE {
  ?museum wdt:P131* wd:Q26 .
  ?museum wdt:P31/wdt:P279* wd:Q33506 .
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

# Museums in Northern Ireland - SUCCEEDS
SELECT distinct ?museum ?museumLabel WHERE {
  ?museum wdt:P131* wd:Q26 .
  wd:Q33506 ^wdt:P279*/^wdt:P31 ?museum .
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

D'autres détails à propos du chemin de la propriété se trouvent dans la définition SPARQL.

Modification de l'ordre

Nous avons déjà désactivé l'optimiseur plusieurs fois, lorsqu'il essayait de réordonner la requête d'une mauvaise façon. Vous pouvez aussi opter pour un contrôle plus poussé de l'optimiseuren lui indiquant quelles sont les jointures à exécuter en premier ou en dernier, en utilisant les règles hint:Prior hint:runFirst true ou hint:Prior hint:runLast true.

Une chose importante à ne pas perdre de vue, est que ce contrôle, le premier join ou le dernier, est plus ou moins le . entre deux triplets – et non pas un triplet directement. En particulier, vous ne pouvez pas dans un groupe, placer cette règle après le premier triplet, ni (je pense) après un triplet contenant un chemin de propriété. Voir aussi les sections à propos des sous-requêtes nommées ci-dessous pour d'autres options de contrôle de l'ordre d'exécution de la requête.

Service des étiquettes

Le service des libellés (SERVICE wikibase:label { … }) peut faire des requêtes encore moins efficaces lorsqu'il a affaire à une requête couteuse. Il est préférable de désactiver d'abord ce service, d'optimiser la requête le plus possible, puis de le remettre en service. Avec un peu de chance, la requête sera assez plausible pour que le service de requête ne la fasse pas expirer maintenant.

Si la requête fonctionne sans le service de libellé, mais que le temps limite est atteint lorsqu’il est ajouté, parfois la solution est de positionner la requête dans une sous-requête, et d’appliquer le service de requête uniquement dans une requête englobante. C’est possible par exemple de la manière suivante, en utilisant une sous-requête SPARQL normale :

SELECT ?foo ?fooLabel ?bar ?barLabel … WHERE {
  { # Wrapper for label-less subquery
    SELECT ?foo ?bar … WHERE {
      …
    }
  }
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

Ceci peut être particulièrement important si vous utilisez LIMIT pour obtenir quelques résultats rapides d'une requête qui dans d'autres cas s'avèrerait très coûteuse.

Le service de libellé tente de s’exécuter en dernier, ce qui veut dire que Blazegraph tente de calculer tous les résultats d’une requête avant d’ajouter les libellés, et seulement ensuite de tronquer en appliquant la directive LIMIT. On peut l’éviter si la partie longue à calculer de la requête est mise dans une sous-requête, comme ci-dessus, conjointement avec la LIMIT, de manière à ce que les libellés soient calculés seulement pour la partie tronquée des résultats.

Un autre moyen pour réduire l'utilisation du service des étiquettes est d'utiliser rdfs:label. Pour obtenir toutes les protéines et leurs étiquettes:

SELECT ?item ?itemLabel WHERE {
  ?item wdt:P31 wd:Q8054 .
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en" . }
}

will timeout because 1 million hits the limit for the label service. Instead get all proteins with labels:

SELECT ?item ?itemLabel WHERE {
  ?item wdt:P31 wd:Q8054 .
  ?item rdfs:label ?itemLabel. FILTER( LANG(?itemLabel)="en" )
}

Notez que ceci va sortir uniquement les éléments qui ont une étiquette en anglais quand même.

Sous-requêtes nommées

Comme évoqué ci-dessus, l’optimiseur essaye parfois de s’appliquer en tenant compte des sous-requête, donc parfois la méthode des sous-requêtes ne fonctionne pas. Vous pouvez corriger cela en utilisant une extension BlazeGraph appelée sous-requêtes nommées (named subqueries) :

SELECT ?item ?itemLabel… 

WITH {
  SELECT ?item … WHERE {
    … 
  }
} AS %results 

WHERE {
  INCLUDE %results.
    … 
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}

Les sous-requêtes nommées sont garanties de pouvoir s'exécuter seulement une fois, d'elles-mêmes, et c'est ce que l'on veut ici.

Autres utilisations des sous-requêtes nommées

L’exemple ci-dessus utilise une seule sous-requête nommée (

named subquery

), mais il est possible d’en utiliser autant que nécessaire.

Ça peut être utile pour imposer un ordre de calcul général ou la structure d’une reqûete, tout en laissant l’optimiseur réarranger les instructions à l’intérieur de chaque sous-requête le mieux possible.

Vous pouvez également désactiver l’optimiseur de requête dans une sous-requête précise, sans qu’il soit désactivé dans le reste de la requête. Pour ce faire, ajouter hint:SubQuery hint:optimizer "None" dans cette sous-requête à la place de l’habituel hint:Query hint:optimizer "None".

Voir les phrases nommées pour un exemple utilisant cette technique.

Les sous-requêtes nommées sont également utiles lorsque vous voulez utiliser les résultats d’une sous-requête plusieurs fois, ou que vous voulez regrouper les résultats de plusieurs manière. Vous pouvez inclure ( INCLUDE ) la même sous-requête dans autant de parties de la requête principale ou sous-requête si nécessaire. Les résultats d’une sous-requêtes nommées sont calculées une seule fois, quelque soit le nombre de fois ou elle est incluse. Voir User:TweetsFactsAndQueries/Queries/most common election days pour un exemple.

Chercher les libellés

Si vous essayez de trouver tous les éléments dont le libellé contient un certain mot, comme « Frankfurt », vous pourriez tenter la requête suivante :

SELECT ?item ?label
WHERE
{
  ?item rdfs:label ?label.
  FILTER CONTAINS(?label, "Frankfurt")
}

But that query will timeout because the query engine would have to the read hundreds of millions of labels to find the word. But Wikidata's normal search function have all words in labels indexed and can make the search very fast. It is possible for a query to access Wikidata's search function with the MediaWiki API Query Service. The query below also finds items with the word "Frankfurt" in a label but uses the MediaWiki API, and can therefore run without timeout:

SELECT ?item ?label
WHERE
{
  SERVICE wikibase:mwapi
  {
    bd:serviceParam wikibase:endpoint "www.wikidata.org";
                    wikibase:api "Generator";
                    mwapi:generator "search";
                    mwapi:gsrsearch "inlabel:Frankfurt";
                    mwapi:gsrlimit "max".
    ?item wikibase:apiOutputItem mwapi:title.
  }
  ?item rdfs:label ?label.
  FILTER CONTAINS(?label, "Frankfurt")
}

The MWAPI search can also include search for labels in selected languages only, and search statements and qualifiers and more. Please see mw:Help:Extension:WikibaseCirrusSearch for a description of the search options.

Utiliser COUNT(*) si possible

Si vous souhaitez connaître le nombre de personnes dans Wikidata, vous pouvez faire la requête suivante :

SELECT (COUNT(?item) AS ?count)
{
  ?item wdt:P31 wd:Q5 .
}

Elle semble simple mais son exécution est longue. Le moteur SPARQL doit d’abord vérifier si ?item est affectée, en valeur ordinaire et pas en erreur, environ 8 millions de fois. L’exécution de la requête prend donc environ 29-30 seconde. Mais nous savons que ?item est toujours affectée et que sa valeur est toujours un élément, donc il est mieux de simplement compter le nombre de résultats sans conditions avec cette requête :

SELECT (COUNT(*) AS ?count)
{
  ?item wdt:P31 wd:Q5 .
}

Ici, le moteur n'a pas besoin d'examiner chaque résultat pour comptabiliser, et la requête prend moins d'une seconde d'exécution.

While counting the number of results is faster than counting the number of a specific binding in general, the reason this example is particularly fast is that the optimizer will rewrite a count over a single triple pattern to use fast range counts. This optimization will not fire if you try to count a set that consists of more than one single triple pattern.

Distinct term scan, and group by and count optimization

If you try to list unique predicates like so, the operation will time out.

SELECT ?p
WHERE { [] ?p [] . }
GROUP BY ?p

However, if you alter this query slightly, it will be rewritten by the optimizer to use a distinct term scan, which is quite fast. This only works on a single triple pattern.

SELECT DISTINCT ?p
WHERE { [] ?p [] . }

There is also a simple group by and count optimization that will combine both the distinct term scan and the fast range count optimizations, the latter for every predicate. This is a lightningly fast way to get counts for all the different predicates. If you need only counts for a subset of the predicates it will most likely be fastest to start with this, wrap it unchanged in a named subquery, then reduce the set down to what you want.

SELECT ?p (COUNT(?p) AS ?count)
WHERE { [] ?p [] . }
GROUP BY ?p

This optimization should work for any component of the triple.

SELECT ?o (COUNT(*) as ?count)
WHERE { ?s wdt:P31 ?o }
GROUP BY ?o

Taille des compteurs pour les intersections de gros sous-ensembles avec WikibaseCirrusSearch

Blazegraph often fails when counting sizes of intersections of huge subsets, for example, it is impossible to count number of humans without gender property set with only SPARQL-based optimizations. However with MWAPI and WikibaseCirrusSearch it works extremely fast.

SELECT ?label ?count WHERE {
  {
    BIND("People without gender" AS ?label)
    SERVICE wikibase:mwapi {
      bd:serviceParam wikibase:endpoint "www.wikidata.org";
                      wikibase:api "Search"; wikibase:limit "once" ;
                      mwapi:srsearch "haswbstatement:P31=Q5 -haswbstatement:P21" ;
                      mwapi:srlimit "1" ; mwapi:srprop "" ; mwapi:srsort "none" ; mwapi:srnamespace "0" .
      ?count wikibase:apiOutput '//searchinfo[1]/@totalhits'.
    }
  } UNION {
    BIND("Male" AS ?label)
    SERVICE wikibase:mwapi {
      bd:serviceParam wikibase:endpoint "www.wikidata.org";
                      wikibase:api "Search"; wikibase:limit "once" ;
                      mwapi:srsearch "haswbstatement:P31=Q5 haswbstatement:P21=Q6581097" ;
                      mwapi:srlimit "1" ; mwapi:srprop "" ; mwapi:srsort "none" ; mwapi:srnamespace "0" .
      ?count wikibase:apiOutput '//searchinfo[1]/@totalhits'.
    }
  } UNION {
    BIND("Female" AS ?label)
    SERVICE wikibase:mwapi {
      bd:serviceParam wikibase:endpoint "www.wikidata.org";
                      wikibase:api "Search"; wikibase:limit "once" ;
                      mwapi:srsearch "haswbstatement:P31=Q5 haswbstatement:P21=Q6581072" ;
                      mwapi:srlimit "1" ; mwapi:srprop "" ; mwapi:srsort "none" ; mwapi:srnamespace "0" .
      ?count wikibase:apiOutput '//searchinfo[1]/@totalhits'.
    }
  } UNION {
    BIND("Other" AS ?label)
    SERVICE wikibase:mwapi {
      bd:serviceParam wikibase:endpoint "www.wikidata.org";
                      wikibase:api "Search"; wikibase:limit "once" ;
                      mwapi:srsearch "haswbstatement:P31=Q5 haswbstatement:P21 -haswbstatement:P21=Q6581097 -haswbstatement:P21=Q6581072" ;
                      mwapi:srlimit "1" ; mwapi:srprop "" ; mwapi:srsort "none" ; mwapi:srnamespace "0" .
      ?count wikibase:apiOutput '//searchinfo[1]/@totalhits'.
    }
  }
}

Services

Service GAS

The Gather, Apply, and Scatter (GAS) service provides graph traversal, graph mining, and similar classes of algorithms for SPARQL. In practical terms, it enables a series of relations to be followed through the graph; for instance the chain of father, grandfather, great-grandfather &c - tracing the father (P22) line - of a subject item, or a chain of connected railway stations through adjacent station (P197) statements. It is documented here & here.

In essence, GAS takes two parameters: gas:in wd:Qnnn - the node or item from which to start, and gas:linkType wdt:Pnnn - the property to be followed. It outputs gas:out - the next item; gas:out1 - the number of hops from the input item and gas:out2 - the item immediately preceding the gas:out item in the queried chain.

# Male lineage of Elizabeth II (Q9682)
SELECT ?father ?fatherLabel ?child ?childLabel ?depth WHERE
 {
  SERVICE gas:service {
       gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ; gas:in wd:Q9682 ; gas:linkType wdt:P22 ; gas:out ?father ; gas:out1 ?depth ; gas:out2 ?child . }

SERVICE wikibase:label { bd:serviceParam wikibase:language "en". }
} order by ?depth

# UK railway stations connected from Topsham railway station (Q1990205) 
#defaultView:Map{"hide":["?cds","?line","?layer"],"layer":"?trackLabel"}
SELECT ?station ?stationLabel ?cds ?line ?trackLabel ?track ?image {
{SELECT * {
  SERVICE gas:service {
       gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ; gas:in wd:Q1990205 ; gas:linkType wdt:P197 ; gas:out ?station ; gas:out1 ?depth ; gas:out2 ?pred . }
  FILTER(?station != wd:Q1990205)
                      ?station wdt:P625 ?cds ;
                               wdt:P17 wd:Q145 .
                             
  ?station p:P197 ?adjST .
  ?adjST ps:P197 ?adj ;
                pq:P81 ?track .

  ?adj p:P625/psv:P625/wikibase:geoLatitude ?lat1 ; p:P625/psv:P625/wikibase:geoLongitude ?lon1 .
  ?station p:P625/psv:P625/wikibase:geoLatitude ?lat2 ; p:P625/psv:P625/wikibase:geoLongitude ?lon2 .
  BIND(CONCAT('LINESTRING(', STR(?lon1), ' ', STR(?lat1), ',', STR(?lon2), ' ', STR(?lat2), ')') AS ?str) . BIND(STRDT(?str, geo:wktLiteral) AS ?line)}
 
}
  OPTIONAL { ?station wdt:P18 ?image .}
SERVICE wikibase:label { bd:serviceParam wikibase:language "en". }
}

It is possible to look at inverse paths to a subject item, for instance, people in a matrilineal line descended from Elizabeth II (Q9682), by adding the parameter gas:traversalDirection "Reverse".

# Female lines descended from Elizabeth II (Q9682)
SELECT ?child ?childLabel ?mother ?motherLabel ?depth WHERE
 {
  SERVICE gas:service {
       gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ; gas:in wd:Q9682 ; gas:linkType wdt:P25 ; gas:traversalDirection "Reverse"; gas:out ?child ; gas:out1 ?depth ; gas:out2 ?mother . 
  }

SERVICE wikibase:label { bd:serviceParam wikibase:language "en". }
} order by ?depth

Il est également possible de suivre les deux directions : à partir de, et vers l'élément en utilisant gas:traversalDirection "Undirected" bien que comme dans l'exemple ci-dessous cela apporte de la confusion entre les colonnes parent et enfant.

# Female line leading to, and descended from, Elizabeth II (Q9682)
SELECT ?child ?childLabel ?mother ?motherLabel ?depth WHERE
 {
  SERVICE gas:service {
       gas:program gas:gasClass "com.bigdata.rdf.graph.analytics.BFS" ; gas:in wd:Q9682 ; gas:linkType wdt:P25 ; gas:traversalDirection "Undirected"; gas:out ?child ; gas:out1 ?depth ; gas:out2 ?mother . 
  }

SERVICE wikibase:label { bd:serviceParam wikibase:language "en". }
} order by ?depth

La documentation introduit quelques paramètres supplémentaires et algorithmes GAS.

Optimisation automatique -- aperçu d'arrière plan

L’approche de base pour l’optimisation de requête est d’essayer de réduire la taille de l’ensemble des solutions le plus petit possible le plus tôt possible lors de l’exécution de la requête. Ainsi le travail à faire pour les jointures suivantes est le plus petit possible. Un but annexe peut être de maximiser les possibilités d’ordonnancement et de parallélisation. C’est ce que l’optimiseur intégré de Blazegraph tente de réaliser.

Par exemple : voici une requête pour retourner une liste des présidents des Etats-Unis et leurs épouses :

SELECT ?pres ?presLabel ?spouse ?spouseLabel WHERE {
   ?pres wdt:P31 wd:Q5 .
   ?pres wdt:P39 wd:Q11696 .
   ?pres wdt:P26 ?spouse .
   SERVICE wikibase:label {
    bd:serviceParam wikibase:language "en" .
   }
 }

Le détails des plans qu’a créé Blazegraph pour exécuter une requête donnée (et les raisons de ce plan) peuvent être obtenus grâce au mode « EXPLAIN » du moteur de requête. C’est faisable en remplaçant ce qui suit au début de l’URL de l’éditeur de requête

https://query.wikidata.org/#

par

https://query.wikidata.org/bigdata/namespace/wdq/sparql?explain&query=

pour poster la requête directement au point d’accès SPARQL (sans passer par l’éditeur de requête), avec un explain& additionnel dans l’URL positionné devant la chaîne query=.

URL résultante, envoi de la requête ci-dessus directement au point de terminaison, avec l'option 'explain', produit ce rapport de la requête et de son optimisation.

Sans optimisation, une requête s’exécuterait de haut en bas, avec les jointures des ensembles de solutions calculées dans l’ordre donné. C’est ce qui s’affiche comme le plan de l’« Original AST » (arbre de syntaxe initial). Cependant, le service de requête estime (en Septembre 2015) qu’il y a

2.900.146 humains dans la base de données avec instance of (P31) human (Q5),
76 présidents des USA (y compris les fictifs !) avec position held (P39) President of the United States (Q11696), et
38.836 triplets avec le prédicat spouse (P26).

It therefore concludes that the most efficient way to run the query, rather than the order specified, is instead to first find the presidents (76), then see how many of them have spouses (51 solutions), then see how many are human (47 solutions), before sending this solution set to the labelling service. This rearrangement is typical of successful query optimisation.

Une requête qui a des difficultés

Les requêtes suivantes essaient de trouver toutes les déclarations faisant référence au site Web "Le Figaro", et retournent leur sujet, prédicat et objet. Cependant, comme elles sont écrites, elles ne fonctionnent pas.

SELECT ?statement ?subject ?subjectLabel ?property ?propertyLabel ?object ?objectLabel ?refURL WHERE {
  ?statement prov:wasDerivedFrom ?ref .
  ?ref pr:P854 ?refURL 
  FILTER (CONTAINS(str(?refURL),'lefigaro.fr')) .       
  ?subject ?p ?statement .
  ?property wikibase:claim ?p .
  ?property wikibase:statementProperty ?ps .
  ?statement ?ps ?object
  SERVICE wikibase:label {
    bd:serviceParam wikibase:language "en" .
  }
}

La raison de cela peut être investiguée en cherchant dans le rapport explicatif de la requête.

It appears that the query optimiser is seduced by the low cardinality of the statements ?property wikibase:claim ?p and ?property wikibase:statementProperty ?ps, with only 1756 properties that take items as their objects, without anticipating that (i) the second condition will do nothing to reduce the solution set from the first condition; and (ii) these conditions will do very little to reduce the cardinality of the statement ?subject ?p ?statement (764,223,907), which the optimiser proposes to join before looking at ?statement prov:wasDerivedFrom ?ref and then ?ref pr:P854 ?refURL.

The query optimiser may also be trying to defer testing the statement FILTER (CONTAINS(str(?refURL),'lefigaro.fr')) for as long as possible, as this requires materialisation of actual string values, rather than proceeding solely with joins based on whether items exist in statements or not.

Mise à jour : depuis 2020, il y a plus de 47000000 références d'URLs dans Wikidata. Comme Blazegraph dans la configuration actuelle ne réalise pas l'indexation en texte plein pour les valeurs textuelles, il n'est pas possible de créer des requêtes « natives  » rapides sans ajouter de filtre supplémentaire (par exemple « trouver toutes les déclarations qui ont rapport avec Le Figaro, mais seulement pour les présidents  »). Heureusement, il existe une solution hors de la boîte, qui utilise MWAPI. Notez-bien que cette requête est un peu différente de l'originale : elle renvoie des liens sur les domaines qui correspondent à *.lefigaro.fr, elle ne ramène pas les liens du type http://web.archive.org/web/20200904002919/http://www.lefigaro.fr/. Cette requête est similaire à :

SELECT ?statement ?subject ?subjectLabel ?property ?propertyLabel ?object ?objectLabel ?refURL WITH
{
  SELECT DISTINCT ?subject WHERE {
    {
      SERVICE wikibase:mwapi {
        bd:serviceParam wikibase:endpoint "www.wikidata.org"; wikibase:api "Generator"; mwapi:generator "exturlusage"; mwapi:geulimit "500"; mwapi:geuquery "*.lefigaro.fr"; mwapi:geuprotocol "http"; mwapi:geunamespace "0" .
        ?title wikibase:apiOutput mwapi:title.
      }
    } UNION {
      SERVICE wikibase:mwapi {
        bd:serviceParam wikibase:endpoint "www.wikidata.org"; wikibase:api "Generator"; mwapi:generator "exturlusage"; mwapi:geulimit "500"; mwapi:geuquery "*.lefigaro.fr"; mwapi:geuprotocol "https"; mwapi:geunamespace "0" .
        ?title wikibase:apiOutput mwapi:title.
      }
    }
    BIND(IRI(CONCAT(STR(wd:), ?title)) AS ?subject)
  }
} AS %items {
  INCLUDE %items .
  
  hint:Query hint:optimizer "None".
  
  ?subject ?p ?statement .
  ?statement prov:wasDerivedFrom/pr:P854 ?refURL .
  FILTER (CONTAINS(str(?refURL), 'lefigaro.fr')) .
  
  ?property wikibase:claim ?p .
  ?property wikibase:statementProperty ?ps .
  ?statement ?ps ?object .
  
  SERVICE wikibase:label { bd:serviceParam wikibase:language "en" }
}

Autres modes d'optimisation

Blazegraph offers a handful of other optimisation directives including the more expensive "runtime optimisation", based on using sampling to more precisely estimate the likely development in the size of the solution set by a particular sequence of joins; and a directive to run a particular join first.

However, examining the corresponding query report, it appears that runtime optimisation has proceeded with the same query sequence as the static optimisation, and similarly times out.

Comme pour la directive runFirst, je n'ai pas encore pu travailler sur la manière de l'appliquer.

Autres requêtes posant problème à l'optimiseur

Les performances dégringolent quand le nombre dans un groupe d'intérêt dépasse un certain seuil

Ceci apparait en rapport avec une requête pour trouver les humains avec des dates qui apparemment correspondent aux naissance et aux décès, ou aux humains d'un pays particulier

France (N=125,223): tinyurl.com/obxk9av -- rapport de requête (succès)
Allemagne (N=194,098): tinyurl.com/pwthc9d rapport de requête (temps dépassé)

Ce qui ne marche pas ici c'est lorsque le nombre d'éléments avec la valeur donnée de country of citizenship (P27), par exemple 194.098 pour l'Allemagne, excède les éléments (en fait, les noeuds temps-valeur) avec wikibase:timePrecision "11"^^xsd:integer (169.902).

Pour la France, avec N=125.223, la taille de l'ensemble de solutions décroit de manière vertigineuse : avec une date de décès, puis une précision spécifique au jour, puis une date de naissance, puis une précision spécifique au jour, on arrive à 48.537, qui est ensuite réduit à 10 lorsque l'on demande la correspondance des date de naissance et de décès (une opération très rapide).

However for Germany, with N=194,098, the query optimiser attempts to start with the 169,902 date-nodes with day-specific dates; but the query then explodes when the system tries to match these to all the people with such day-specific birthdates (1,560,806), a number which reduces when the nationality filter kicks in; but which still eats up the available query time.

(In fact, having looked at the performance data and seen just how fast Blazegraph can do all-against-all matching for really very big sets, it turns out that (with a query rewrite) the system is fast enough to run this kind of query for everything -- see tinyurl.com/pn9xyye -- by matching on date-nodes first, which knocks down the size of the solution set, and not checking until after that the requirement that the date be day-specific).

Ajouter un conteneur de noms et d'étiquettes de noms à une requête pour les événements de la vie provoque l'expiration du délai d'exécution

Tracked by Blazegraph

Adding an apparently trivial wrapper, to find the name and name-label, causes the query in the immediately previous section to time out, even when without the wrapper it ran with no difficulty.

La requête telle qu'elle se présente : tinyurl.com/p8wzb74 -- rapport de requête
Requête triée manuellement : tinyurl.com/o7z95vb -- rapport de requête (succès)
Requête sans chercher le nom : tinyurl.com/obxk9av -- rapport de requête (succès)

With the outer-layer in place, the inner layer now starts (even for France) by extracting the birth-nodes that are connected to birth-dates, and then keeping those which have precision=11.

La situation peut être corrigée en désactivant l'optimiseur de requête et en réorganisant la requête manuellement.

It seems this may be a general feature of queries with sub-select clauses: both here and in the next query the optimiser seems to want to start the sub-query with a requirement that includes one of the variable that will be projected to the outer layer.

Ajouter un conteneur de libellés de propriété à une requête de propriétés fait déborder la temporisation

La requête telle qu'elle se présente : tinyurl.com/oex59qr -- demande de rapport
Requête demandée manuellement : tinyurl.com/ppkmb3v -- demande de rapport (succès)
Requête sans recherche d'étiquette de propriété : tinyurl.com/qe4ukbx -- rapport de la requête (succès)

Same as the above: for the query including property look-ups, the optimiser apparently wants to start with all triples ?a ?p ?b and then join ?b wdt:P31 wd:Q4167410, rather than the other way round (which is what it manages to successfully do for the smaller query with no property look-up).

This doesn't appear to an artifact caused by BIND, nor the order the clauses are presented -- even if these are changed, the query still runs slow with the built-in optimiser

Requête alternative : tinyurl.com/q97a8sh -- rapport demandé (échoue encore)

Il est encore plus préférable de commencer avec l'assertion ?a ?p ?b, même ci cela est moins spécifique -- apparemment parce que ?p est l'une des variables projetées hors de la commande SELECT interne.

Requêtes avec « filter not exists »

To work fine, queries with “filter not exists” often seem to have to be rewritten.

The “filter not exists” clause seems to often be inefficient for unclear reasons. For example a query like this one, featured articles in frwiki which does not exists at all on enwiki times out expressed as a query with “filter not exists”

select ?articleFr ?item ?itemLabel ?some ?someLabel {
    select * {?articleFr schema:about ?item ;
             wikibase:badge ?some ;
             schema:isPartOf <https://fr.wikipedia.org/>
  
    filter not exists {
      ?articleEn schema:about ?item ;
               schema:isPartOf <https://en.wikipedia.org/>
    }
   }
}

however are fine just rewriting using an “optional”, with filtering on a unbound variable

select ?articleFr ?item ?itemLabel ?some ?someLabel {
  {
    select * {?articleFr schema:about ?item ;
             wikibase:badge ?some ;
             schema:isPartOf <https://fr.wikipedia.org/>
  
      optional { ?articleEn schema:about ?item ;
               schema:isPartOf <https://en.wikipedia.org/> .
      }
      filter (!bound(?articleEn))
   }
  }
}

Using MINUS() also works well in this instance. These three methods of removing results all does something similar but goes about it differently. There is not one method which is consistently better/worse, they will all perform differently given the circumstances. In other words you ought to try them all if you are serious about performance.

Rules of Thumb

Here's my explanation of the situation:

FILTER NOT EXISTS needs to check a condition on each solution of the subquery. These conditions are checked in sequence, not by join
OPTIONAL fetches an extra triple pattern related to each solution. This is done by join, i.e. all at once. The FILTER NOT BOUND then can quickly check each row of this extended resultset
MINUS computes the second subquery, then finds the set difference of the first and second subqueries. If both are relatively small, the difference can be computed quickly

So a rule of thumb is:

Use FILTER NOT EXISTS when the negative condition to check produces a huge resultset, so the NOT EXISTS may be less expensive
Use OPTIONAL... FILTER NOT BOUND when the negative condition extends the positive resultset with only a few more rows (or keeps the same rows)
Use MINUS when the negative condition, taken on its own, produces a small resultset

Gérer les requêtes en cache

This post may be useful for folks who want to makes sure queries are freshly executed:

https://byabbe.se/2018/01/26/cache-busting-wikidata-sparql-queries

Short retell: to disable query caching add cache-control: no-cache header. Alternatively you can just replace GET method with POST. Results of POST requests are never cached: if you want to get a cached response, switch from POST to GET.

Davantage... ?

Ajoutez d'autres cas ici

Retrieved from "https://www.wikidata.org/w/index.php?title=Wikidata:SPARQL_query_service/query_optimization/fr&oldid=1982436700"