Jump to content

Wikidata Query Service/WDQS Graph Split Impact Analysis

The scope of this analysis is to assess the impact (on existing SPARQL queries) of splitting the Wikidata graph into two subgraphs: scientific articles (also referred to as scholarly articles) on one side and the rest (called Wikidata main) on the other. We will refer to the existing graph served by WDQS as the full graph.

TL/DR: Data shows that less than 10% of the queries might be affected by the graph split but this only affects a few user-agents. The top 5 of the most impacted user-agents accounts for more than 90% of the total impact. In other other words it sounds possible to drastically reduce the impact of the split by addressing a few user-agents.

Dataset

We used 6 different samples gathered from the WDQS query logs. Five from known tools used to access WDQS by the Wikidata community:

  • Listeria
  • MixNMatch
  • Pywikibot
  • WikidataIntegrator
  • SPARQLWrapper

10,000 queries collected in October and November 2023 were extracted from each (except for MixNMatch where only 8396 queries were found in the query logs during this period). Another sample called random with 100,000 queries representative of the various query lengths and execution times we see in our query logs was also extracted[1].

Basic sample statistics

Below is a table showing the number of queries per sample versus the number of unique queries.

SampleTotalUnique
Listeria10000101
MixNMatch8396626
Pywikibot100005455
SPARQLWrapper100009919
WikidataIntegrator100002507
random10000085838

For some samples a non-negligible number of queries are repeated. The total could be used as a base to assess the impact on a per-query-execution basis, the unique counts to assess the impact per use-case (boldly considering a unique query to be a use-case). Since both might have value, most metrics analyzed here will be compared against both the total and the de-duplicated view of the samples.

Collecting SPARQL query results

For all the queries we collected the results (results) returned from the full graph and the main graph. For various reasons not all queries successfully ran and some failed either originally (when they initially hit the production servers) or during the analysis when they ran on our experimental endpoints.

SampleTotalsuccessful (originally)successful (full)successful (main)% successful (originally)% successful (full)% successful (main)
Listeria10 0001339 4669 4661.3394.6694.66
MixNMatch8 3967 4778 3698 36989.0599.6899.68
Pywikibot10 0009 8129 9499 95198.1299.4999.51
SPARQLWrapper10 0009 8649 9079 91298.6499.0799.12
WikidataIntegrator10 0009 9979 9989 99999.9799.9899.99
random100 00097 90999 88799 86997.9199.8999.87

The success rate is generally good (except for Listeria which has a very low 1.33%[2]). For simplicity and given the high success rate of the queries on the experimental endpoints the analysis will focus solely on the successful queries.

Methodology

Assessing the impact requires knowing the intent of the SPARQL query. In other words, does the author of the query expect/want scientific articles to impact the results of their queries or not. Knowing this with certainty is not possible without a confirmation from the author itself but we can try to approximate this by:

  1. Determining the presence of a scientific article in the query or one of its results[3]
  2. Running the query against the full graph and the Wikidata main graph (loaded from the exact same dump) and finding differences in the results returned. If there is a difference it is perhaps because the result was dependent on the presence of scientific articles.

Assessing the first point might give a good confidence of the intent of the query but spotting differences is a less direct signal and might need adjustments to take false positives into account.

Unfortunately some SPARQL queries might return varying results not because scientific articles are missing but because of some of the SPARQL features being used, and thus might be a cause of many false positives. In the samples used for this analysis we identified 6 SPARQL features[4] that cause possible false positives.

Similarly comparing the query results might yield false positives because of the order in which the results are returned by Blazegraph (many queries do not include sorting criteria).

A quick note should be made regarding queries that return zero results, without any results we only have the SPARQL query string to detect the presence of a scientific article and it is also "easier" to have similar results.

Overall we combine four criteria that we name as:

  • true positives: for queries where we identified a direct reference to scientific article
  • same: for queries returning the same results on both graphs (regardless of the order)
  • zero results: for queries returning zero results on both graphs
  • deterministic: for queries without a feature that might affect the results for unrelated reasons

Combining these we can classify the queries into four buckets[5]

  • unimpacted: for queries with high confidence that they are not impacted by the split (not a true positive, same, no zero results, deterministic or not)
  • zeros: for queries returning zero results with relatively good confidence that they are not impacted (not a true positives, returning zero results, deterministic or not)
  • unsure: for queries with some uncertainty whether they might be impacted or not (not a true positive, returning different results, not deterministic)
  • impacted: for the queries that are impacted (all other combination of the criteria above, mainly all true positives and deterministic queries returning different results)

Results

Below is a graph showing the impact in % compared to the total number of successful queries:

and this version shows the impact in % compared to the number of unique queries:

Proper interpretation of these results will require a more qualitative analysis but we can see that except MixNMatch[6] the ratios are roughly identical when compared to the plain samples or when using the de-duplicated ones.

Understanding how the impact is shared by various use-cases/user-agents might be interesting to visualize. One of the goals of the community consultation phase (tracked under phab:T356773) of the wikidata:Wikidata:SPARQL_query_service/WDQS_graph_split project is to collect use-cases and help/guide the impacted tools & clients to evaluate the feasibility of using SPARQL federation to make their use-cases compatible with the split.

While we cannot display specific user-agents for privacy reasons we can graph the cumulative proportion the various user-agents might have on the overall impact. This way we can get a sense of how quickly we could reduce the overall impact of this project if we address such clients/use-cases (the x axis is the number of user-agents, the y axis is the cumulative proportion in % of the queries that are considered as impacted in the bar charts above).

The above graph says that the most impacted user-agent accounts for 45% of the total impact, the top 5 account for more than 90% of the impacted queries.

And the version on de-duplicated queries which shows roughly the same trend:

In other words it does seem plausible to drastically reduce the negative impact of the graph split. This assumes that we can get in touch with the maintainers of such client/tools, which might not be possible for those that do not set a proper user-agent.

The tail is not particularly long with 56 user-agents[7] in these samples.

Annex

Query execution error statistics

In order to understand why a query might have failed when it initially hit WDQS we can interpret the HTTP status code returned by WDQS. The table below shows the number of queries per sample and status code:

Sample200400403429500503
Listeria133<1009 829<100<1000
MixNMatch7 4770009190
Pywikibot9 812<1000<1001720
SPARQLWrapper9 864<100<100<100<1000
WikidataIntegrator9 99700<100<1000
random97 909<1001 979<100<100<100
  • 200 is a success
  • 400 is a bad request, generally a SPARQL syntax error or a misbehaving HTTP client
  • 403 forbidden, used by WDQS when a client is banned after making too many requests
  • 429 to warn a client and ask it to slowdown when it is making too many requests
  • 500 a server failure (a timeout, an internal error)
  • 503 service unavailable (when Blazegraph is unable to respond, could be a timeout or an internal error)

This does seem to indicate that the high failure rate of Listeria is due to the throttling mechanism protecting WDQS.

Detecting a reference to a scientific article

Since we know the list of Wikidata items that are scientific articles we can search for a reference in the SPARQL query or within the results returned by the query when running against the full graph. The table below shows how many of these we found:

Queries with a reference to a scientific article
SampletotalScientific article in queryScientific article in resultstotal
Listeria10 000000
MixNMatch8 39607 1507 150
Pywikibot10 000<100<100100
SPARQLWrapper10 000<100<100<100
WikidataIntegrator10 000<100<100<100
random100 0004 4824 2987 201
Queries (de-duplicated) with a reference to a scientific article
SampletotalScientific article in queryScientific article in resultstotal
Listeria101000
MixNMatch6260<100<100
Pywikibot5 455<100<100<100
SPARQLWrapper9 919<100<100<100
WikidataIntegrator2 507<100<100<100
random85 8384 4824 2877 190

Non deterministic SPARQL features

We consider a SPARQL feature to be non-deterministic if for multiple executions the results returned are not guaranteed to be the same when running on the exact same graph.

The non-deterministic SPARQL features that we identified are:

wikibase:mwapi service EntitySearch

The use of the MW API may yield different results depending on when the API request is performed (since it's calling the Wikidata API which is consistently being updated)

 SELECT ?item ?itemLabel ?type ?typeLabel WHERE {
   SERVICE wikibase:mwapi {
       bd:serviceParam wikibase:api "EntitySearch" .
       bd:serviceParam wikibase:endpoint "www.wikidata.org" .
       bd:serviceParam mwapi:search "something" .
       bd:serviceParam mwapi:language "en" .
       ?item wikibase:apiOutputItem mwapi:item .
       ?num wikibase:apiOrdinal true .
   }   ?item (wdt:P31|wdt:P279|wdt:P366) ?type
   SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
  } ORDER BY ASC(?num) LIMIT 10

GROUP_CONCAT

The GROUP_CONCAT SPARQL feature does not provide a stable ordering when it concatenates the group.

SELECT ?extid (count(?q) AS ?cnt) (GROUP_CONCAT(?q; SEPARATOR = '|') AS ?items)
WHERE { ?q wdt:P973 ?extid }
GROUP BY ?extid HAVING (?cnt>1)
ORDER BY ?extid

Label service AltLabel (lbl_srv_alt_label)

Asking for aliases with the mw:Wikidata_Query_Service/User_Manual#Label_service is not deterministic when there are multiple aliases for the entity

SELECT ?property ?propertyType ?propertyLabel ?propertyDescription ?propertyAltLabel WHERE {
  ?property wikibase:propertyType ?propertyType .
  SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
}
ORDER BY ASC(xsd:integer(STRAFTER(STR(?property), 'P')))

SAMPLE

The SPARQL SAMPLE is not required to be deterministic

SELECT ?universe (SAMPLE(?label) AS ?label) (COUNT(?planet) AS ?count)
WHERE
{
  ?planet wdt:P31 wd:Q2775969;
          wdt:P1080 ?universe.
  ?universe rdfs:label ?label.
  FILTER(LANG(?label) = "en").
}
GROUP BY ?universe
ORDER BY DESC(?count)

Blazegraph bd:slice service slice.offset

Blazegraph bd:slice with bd:slice.offset cannot operate similarly between two different Blazegraph instances

SELECT ?item $ddate_st WHERE {
  SERVICE bd:slice { ?item p:P570 ?ddate_st . bd:serviceParam bd:slice.offset 100 . bd:serviceParam bd:slice.limit 200 . }
  ?item wdt:P31 wd:Q5 .
}

Using a top level limit on a large result set (top_level_limit)

A SPARQL query using top level LIMIT X produces X results without deterministic ordering clauses and might yield different results

SELECT ?item {
  ?item wdt:P31 wd:Q5 .
  FILTER NOT EXISTS { ?item wdt:P570 [] }
} LIMIT 100

Distribution in the samples

Number of non-deterministic query features
SampleTotalTotal deterministicEntitySearchgroup_concatlbl_srv_alt_labellimit_offsetsampleslice_offsettop_level_limit
Listeria10 0001 3800005 16901 9954 080
MixNMatch8 39665907 73700000
Pywikibot10 0007 3671 138001 028<100428530
SPARQLWrapper10 0009 434<100359<100<100<1000205
WikidataIntegrator10 0001 7650<1008 225<10000<100
random100 00067 55971217 99710 543<1002 465<1002 097
Number of non-deterministic query features over de-duplicated queries
SampleTotalTotal deterministicEntitySearchgroup_concatlbl_srv_alt_labellimit_offsetsampleslice_offsettop_level_limit
Listeria<100<100000<1000<100<100
MixNMatch626313031300000
Pywikibot5 4553 21286300939<100428327
SPARQLWrapper9 9199 357<100359<100<100<1000201
WikidataIntegrator2 5071 5590<100938<10000<100
random85 83863 96963716 5262 102<1002 422<1001 469

Combining 4 criteria of a SPARQL query

The 4 criteria of a query can be combined in 12 different ways (4 combinations are not possible, e.g. having different results and zeros results), to help the analysis we use a simple notation mechanism encoded over four characters:

  • s: same
  • t: true positives
  • z: zero results
  • d: deterministic

and using the case to determine if the query has this criterion or not.

For instance Stzd means that a query has obtained similar results on both graphs, has no direct reference to a scientific article, has obtained at least one result, and is not deterministic.

The distribution of these classes over the successful queries is:

Number of queries by criteria group
SampleTotalSTZDSTZdSTzDSTzdStZDStZdStzDStzdsTzDsTzdstzDstzd
Listeria9 4660000<10007655 557001902 857
MixNMatch8 3690000<100331572260<1007 1110<100
Pywikibot9 94500<10008881 0366 4401 032<100<100<100442
SPARQLWrapper9 906<1000<10005 3633263 905202<100<100<100<100
WikidataIntegrator9 9980000371<1001 3127 139<100001 086
random99 8651 191<100<100<10021 82516 33337 04413 7975 7961771 5842 081
Number of queries (de-duplicated) by criteria group
SampleTotalSTZDSTZdSTzDSTzdStZDStZdStzDStzdsTzDsTzdstzDstzd
Listeria<1000000<1000<100<10000<100<100
MixNMatch6190000<100150266135<100<1000<100
Pywikibot5 41000<10007729792 405783<100<100<100403
SPARQLWrapper9 831<1000<10005 3593263 838198<100<100<100<100
WikidataIntegrator2 5050000218<1001 259870<10000<100
random85 7531 191<100<100<10021 25915 41935 4125 5455 796166241687

MixNMatch impact

One query is the cause of most of the impact on MixNMatch (7000+ hits):

SELECT ?extid (count(?q) AS ?cnt) (GROUP_CONCAT(?q; SEPARATOR = '|') AS ?items)
{ ?q wdt:P973 ?extid }
GROUP BY ?extid HAVING (?cnt>1)            ORDER BY ?extid

P973 is pretty generic so the query alone does not allow us to identify what MixNMatch catalogs could be the source. Looking at the source code[8] this query does seem useful for identifying issues in Wikidata. The individual issues do seem to be ignored when they are too numerous (400) so the individual results of this particular query on P973 do not seem to matter.

Notes

  1. ↑ Please see T349512_representative_wikidata_query_samples for more details on the samples
  2. ↑ Listeria does appear to be heavily throttled/banned by WDQS protection measures, see details in § Query execution error statistics
  3. ↑ see § Detecting a reference to a scientific article
  4. ↑ see § Non_deterministic_SPARQL_features
  5. ↑ see section § Combining 4 criteria of a SPARQL query for more details
  6. ↑ A unique MixNMatch query is the cause of 7000+ impacted query executions, see § MixNMatch impact
  7. ↑ to ease the analysis some grouping was made, e.g. by removing the version number of some UA or group web browsers into a single group
  8. ↑ MicroSync.php